03 nivel legatura date

7/22/2019 03 Nivel Legatura Date

http://slidepdf.com/reader/full/03-nivel-legatura-date 1/53

Universitatea Politehnica Bucureşti - Facultatea de Automatică şi Calculatoare

Protocoale de comunicaţie – Curs 2 1

Nivelul legătură de date





Funcţiile nivelului legăturii de date

• Încadrarea.

• Transmisia transparentă.• Controlul erorilor.• Controlul fluxului.• Gestiunea legăturii.





Încadrarea

• Adăugarea de informaţie de control pentru a încadra datele:





Metode de încadrare

• Caractere de control (BSC – Binary Synchronous Communication) – Exemplu:

SYN SYN SOH header STX text ETX CRC

SOH - start of heading STX - start of textETX - end of text ETB - end of transmission blockEOT - end of transmission ENQ - enquiry

ACK - acknowledge NAK - not acknowledgeSYN - synchronous idle DLE - data link escapeCRC - cyclic redundancy check

• Numărarea caracterelor (DDCMP – Digital Data CommunicationsMessage Protocol) – Exemplu (CRC Cyclical Redundancy Check):SYN SYN SOH count flag resp seq address CRC data CRC

• Indicatori de încadrare (HDLC – High Level Data Link Control) – Exemplu (FCS = Frame Check Sequence):

flag address command data FCS flag





Transmisia transparentă (1)

• În zona de date pot apărea secvenţe de control: – Text alfanumeric (Ok): STX Text ETX – Text binar (Nok, apare un fals ETX): STX Text…ETX…Text ETX

• Rezolvare prin umplere cu caractere: – Se prefixează la emisie caracterele de control cu caracterul DLE. – Se definesc combinaţiile permise:

• DLE STX pentru început text transparent.• DLE ETX pentru sfârşit text transparent.

– Dublează DLE la emisie şi elimină la recepţie. – Exemplu:DLE STX Text...ETX...Text...DLE DLE...DLE ETX CRC

– Se consideră eroare recepţia caracterului DLE urmat de altcevadecât STX, ETX, DLE.





Transmisia transparentă (2)

• Datele de trimis conţin un flag fals de terminare cadru:01111110 011011111101111111111010 01111110Flag Flag fals Flag

• Rezolvare prin umplere cu biţi: – Emisie: inserare bit 0 după 5 biţi consecutivi 1 în interiorul cadrului,

indiferent ce urmează după cei 5 biţi 1.

– Recepţie: eliminare bit 0 care urmează după 5 biţi consecutivi 1. – Exemplu:01111110 ... 0111110 {0 sau 1} ... 01111110





Alte funcţii

• Controlul erorilor :

– Secvenţa (suma) de control a cadrului (FCS). – Mesaje de confirmare. – Ceasuri. – Numere de secvenţă.

• Controlul fluxului: – Utilizarea mesajelor de permisiune pentru transmiţător.

• Gestiunea legăturii: – Stabilirea şi desfiinţarea legăturii. – Re-iniţializare după erori. – Configurarea legăturii (staţii primare şi secundare, legături

multipunct, etc.).





Detecţia şi corecţia erorilor

• Coduri corectoare de erori

– Fie A = {0, 1} alfabet binar – Fie Wn mulţimea cuvintelor w de lungime n peste A

w[0] w[1] ... w[n-1] , cu w[i] A. – Ponderea Hamming a lui w – Distanţa Hamming‚ d(u,v) dintre u şi v

– Wn = Sn U Fn – Pentru u, v Sn şi r erori:

d(u,v) >= r+1 detecţie d(u,v) >= 2r+1 corecţie

– Exemplu:

Fie S10 = {0000000000, 0000011111, 1111100000, 111111111}

D(u,v) = 5 => putem corecta erori duble0000000111 Se corectează la 00000111110000000111 Poate proveni din 0000000000





Metoda Hamming

• Biţi numerotaţi de la 1 (stânga) la n (dreapta) .• Codificare:

– Biţii 1, 2, 4, 8, ... (puteri ale lui 2) sunt de control. – Control paritate (pară sau impară). – Bitul k este controlat de biţii ale căror poziţii însumate dau k; reciproc:

• Bitul 1 controlează biţii 1, 3, 5, 7, 9, 11.

• Bitul 2 controlează biţii 2, 3, 6, 7, 10, 11.• Bitul 4 controlează biţii 4, 5, 6, 7.• Bitul 8 controlează biţii 8, 9, 10, 11.

• Exemplu ‘W’, 0x57, cu paritate pară:

1 2 3 4 5 6 7 8 9 10 111110101 => 0 1 1 0 1 1 0 0 1 0 1Se primeşte eronat 0 1 1 0 1 1 0 0 1 1 1

Biţii de control eronaţi sunt 2, 88 + 2 = 10

=> bitul din poziţia 10 a fost inversat.

Pentru paritate pară:

dacă există număr par de biți 1 între biții 3, 5, 7, 9 și 11, atuncibitul 1 va fi 0.

dacă există număr impar de biți 1 între biții 3, 5, 7, 9 și 11, atuncibitul 1 va fi 1.





Coduri corectoare de erori

• Codul Hamming corectează erorile de 1 bit!

• Utilizarea unui cod Hamming pentru corecţia erorilor î n rafală: – Matricea de biţ i este transmisă coloană cu coloană. – Poate corecta erori în rafală dintr-o coloană.





Coduri detectoare de erori (1)

• Coduri polinomiale:

– k biţi de informaţie (date), i(X) polinomul corespunzător . – n-k biţi de control, r(X). – n biţi în total, w(X) = Xn-k.i(X) + r(X).

• r(X) se alege astfel ca w(X) să fie multiplu de g(X): w(X) = g(X).q(X) Xn-k.i(X) + r(X) = g(X).q(X) Xn-k.i(X) = g(X).q(X) + r(X)

r(X) = rest împărţire Xn-k

.i(X) la g(X)





Coduri detectoare de erori (2)

• Calculul sumei de control

pentru un cod polinomial: – 10 biţ i informaţ ie. – 4 biţ i control.

• Împarte 11010110110000 la 10011.





Ce erori pot fi detectate?

• Probabilitatea de detecţ ie depinde de lungimea codului de

control.• CRC – sume de control pe: – 8 biţi detectează 99.6094% din erori. – 16 biţi detectează 99.9985% din erori. – 32 biţi detectează 99.9999% din erori.

• În plus, CRC detectează 100% erori de – 1 bit. – 2 biţ i. – Un număr impar de biţ i. – Erori în rafală de lungimea codului CRC.





Protocoale elementare pentru legătura de date

• Protocoale start-stop:





Protocoale elementare pentru legătura de date

• Protocoale cu ferestre glisante:

U i it t P lit h i B ti F lt t d A t ti ă i C l l t





Protocol start-stop

Staţia 1

Staţia

2

PDU1

Ack1

PDU2

Timp






Protocol start-stop

Staţia 1

Staţia

2

Timp

PDU1

PDU1 Ack1

Ack1 PDU2

PDU2






Timeout

Protocol cu fereastră glisantă şi retrimitereneselectivă

Staţia 1

Staţia

2

Timp

PDU1 PDU2 PDU3

Err 3

PDU4 PDU5 PDU6

Ack1 Ack2 Del4 Del5

PDU3

Del6

PDU4

Ack3

PDU5

Universitatea Politehnica Bucureşti Facultatea de Automatică şi Calculatoare





Timeout

Protocol cu fereastră glisantă şi retrimitereneselectivă

Staţia 1

Staţia

2

Timp

PDU1 PDU2 PDU3

Err 3

PDU4 PDU5 PDU6

Ack1 Ack2 Del4 Del5

PDU3

Del6

PDU4

Ack3

PDU5

Cadre recepţionatecorect, însă trimise

inutil pentru căprotocolul le ignoră





Buf 4 Buf 5


Protocol cu fereastră glisantă şi retrimitereselectivă

Staţia 1

Staţia

2

Timp

PDU1 PDU2 PDU3

Err 3

PDU6

Ack1 Ack2

PDU3

Buf 6

PDU7

Ack6

PDU4 PDU5

Nak3 Ack2 Ack2

PDU8






Protocol cu fereastră glisantă şi retrimitereselectivă

Staţia 1

Staţia

2

Timp

PDU1 PDU2 PDU3

Err 3

PDU6

Ack1 Ack2

PDU3

Buf 6

PDU7

Ack6

PDU4 PDU5

Buf 4 Buf 5

PDU8

Cadre recepţionatecorect, memorate deprotocol până devin

utile






Protocoalele legăturii de date

• Configuraţia entităţilor de protocol:

Utilizator A Utilizator B

Entitate A Entitate B

Nivelul reţea

Nivelul legăturăde date

Nivelul fizic






Datele

• Datele:

typedef struct {void far* adresa; word lungime;} pachet;

enum FelCadru {data, ack, nak};typedef unsigned char byte;typedef unsigned int word;typedef byte NrSecv;

typedef struct {FelCadru fel; NrSecv secv, conf; pachet info;

} cadru;






Primitivele de serviciu

• Primitive de serviciu:

– preluarea unui pachet de la retea pentru transmitere pe canal pachet DeLaRetea();

– livrarea cãtre retea a unui pachetvoid LaRetea (pachet); – trecerea unui cadru nivelului fizic pentru transmisie

void LaFizic (cadru); – preluarea unui cadru de la nivelul fiziccadru DeLaFizic();

• Altele: – Lista evenimente:enum TipEven{SosireCadru,EroareControl,TimeOut,ReteaPregatita};

– Aşteptare producere eveniment: TipEven wait();






Protocoale start-stop

• Protocol simplex fără restricţii (caz ideal):

– utilizatorul A vrea să transmită date utilizatorului B folosind olegătură sigură, simplex. – A reprezintă o sursă inepuizabilă de date. – B reprezintă un consumator ideal. – canalul fizic de comunicaţie este fără erori.






Protocol simplex fără restricţii

# define forever while(1) // entitatea din sistemul transmitatoruluivoid transmit1()

{cadru s;do{s.info=DeLaRetea(); //preia pachetLaFizic(s); //transmite cadru

}forever;}

// entitatea din sistemul receptoruluivoid recept1()

{cadru r;

TipEven even;do{even=wait(); //aşteaptă cadru r=DeLaFizic(); //primeşte cadruLaRetea(r.info); //predă pachet

}forever;

}




ş ş


Protocol simplex start-stop (1)

• Canalul este fără erori.

• Utilizatorul B nu poate accepta date în orice ritm.


Entitate A(emiţător)

Entitate B(receptor)

Nivelul reţea


Nivelul fizicDate

Confirmări(reacţie)




ş ş


Protocol simplex start-stop (2)

void transmit2(){cadru s;TipEven even;do{s.info=DeLaRetea();LaFizic(s);even=wait(); //aşteaptă confirmarea} forever;

}

void recept2(){cadru s,r;TipEven even;do{even=wait(); //poate fi doar SosireCadru

r=DeLaFizic();LaRetea(r.info);LaFizic(s); //transmite confirmarea} forever;

}




ş ş


Protocol simplex pentru un canal cu erori (1)

• Canalul este cu erori (ca în situațiile din practică).

• Primitive pentru controlul ceasului: – void StartCeas(NrSecv); – void StopCeas (NrSecv);

• Justificare numere de secvenţă: – cadrele succesive m, m+1, m+2 cu numerele de secvenţă respectiv

0, 1 şi 0 (protocol cu bit alternat).• Alte primitive:

– void inc (NrSecv&); – #define MaxSecv 1 – void inc(NrSecv& k) {k==MaxSecv ? k=0 : k++;}






void transmit3(){ NrSecv CadruUrmator=0;cadru s;TipEven even;

s.info=DeLaRetea();

do{s.secv=CadruUrmator;LaFizic(s);StartCeas(s.secv);even=wait(); // poate fi SosireCadru ,

// TimeOut sau EroareControl

if(even==SosireCadru){ // confirmare intactaStopCeas(s.secv);

s.info=DeLaRetea();inc(CadruUrmator);}

}forever;}






void recept3(){ NrSecv CadruAsteptat=0;cadru r,s;TipEven even;

do{even=wait(); //SosireCadru sau EroareControl

if(even==SosireCadru){r=DeLaFizic();if(r.secv==CadruAsteptat){LaRetea(r.info); //cadru în secventainc(CadruAsteptat);}

LaFizic(s); //transmite oricum confirmarea}

}forever;}





Protocoale cu fereastră glisantă (1)

• Protocol cu fereastră de dimensiune unu.

• Configuraţia:


Entitate A(emiţător şi receptor)

Entitate B(emiţător şi receptor)

Nivelul reţea


Nivelul fizicdate şi confirmări

date şi confirmări






• O fereastră de dimensiune 1, cu număr de secvenţă de 3 biţi:

– (a) Iniţial. – (b) După transmiterea primului cadru. – (c) După recepţia primului cadru. – (d) După recepţia primei confirmări.






• Fiecare staţie realizează ciclic următoarele operaţii:

– Recepţia unui cadru. – Prelucrarea şirului de cadre recepţionate. – Prelucrarea şirului de cadre transmise. – Transmiterea sau retransmiterea unui cadru împreună cu

confirmarea cadrului recepţionat corect.

void protocol4(){ NrSecv CadruUrmator=0; NrSecv CadruAsteptat=0;cadru r,s;

TipEven even; //SosireCadru

,TimeOut

,EroareControl

s.info=DeLaRetea();s.secv=CadruUrmator;s.conf=1-CadruAsteptat;LaFizic(s);StartCeas(s.secv);






do{

even=wait();if(even==SosireCadru){r=DeLaFizic();

if(r.secv==CadruAsteptat){ // prel. cadre receptionateLaRetea(r.info);inc(CadruAsteptat);

}if(r.conf==CadruUrmator){ // prel. cadre transmisieStopCeas(r.conf);s.info=DeLaRetea();inc(CadruUrmator);}

}

s.secv=CadruUrmator;s.conf=1-CadruAsteptat;LaFizic(s);StartCeas(s.secv);

}forever;}





Un protocol cu fereastră de un bit

• Două scenarii pentru protocolul 4:

– (a) Cazul normal. – (b) Caz anormal.

• Notaţia este (seq, ack, packet number).• Un asterisk (*) arată că nivelul reţea acceptă pachetul.





Un protocol “Go Back N”

• Banda de asamblare şi refacerea erorilor.

• Efectul erorii când: – (a) Fereastra receptorului este 1.

– (b) Fereastra receptorului este mai mare ca 1.





Protocoale cu fereastră supraunitară detransmisie (1)

• Protocol cu retransmitere neselectivă.

• Fereastra maximă a transmiţătorului poate fi de MaxSecv cadre.• Scenariu pentru MaxSecv = 7:

– 1. Transmiţătorul trimite cadrele 0..7. – 2. Toate cadrele sunt recepţionate şi confirmate. – 3. Toate confirmările sunt pierdute.

– 4. Transmiţătorul retrimite la time-out toate cadrele. – 5. Receptorul acceptă duplicatele.






#define MaxSecv 7

void ActivRetea();void DezactivRetea();

NrSecv CadruUrmator, // urmatorul cadru de transmisCadruAsteptat, // urmatorul cadru asteptatConfAsteptata; // c.m. vechi cadru neconfirmat

cadru r,s;

pachet tampon[MaxSecv+1]; NrSecv ntampon,i;TipEven even;

short intre(NrSecv a, NrSecv b, NrSecv c){//intoarce 1 daca a<=b<c circular

return a<=b && b<c || c<a && a<=b || b<c && c<a;}

void transmite(NrSecv nrcadru){//construieste si transmite un cadru de dates.info=tampon[nrcadru];s.secv=nrcadru;s.conf=(CadruAsteptat+MaxSecv)%(MaxSecv+1);LaFizic(s);StartCeas(nrcadru);

}






void protocol5(){

ActivRetea();

CadruUrmator=0;CadruAsteptat=0;ConfAsteptata=0;ntampon=0;

do{even=wait();

switch(even){

case ReteaPregatita:

tampon[CadruUrmator]=DeLaRetea();ntampon++;transmite(CadruUrmator);inc(CadruUrmator);

break;






case SosireCadru:r=DeLaFizic();if(r.secv==CadruAsteptat){

LaRetea(r.info);inc(CadruAsteptat);

} while(intre(ConfAsteptata,r.conf, CadruUrmator)){

ntampon--;StopCeas(ConfAsteptata);inc(ConfAsteptata);

} break;

case EroareControl: break;

case TimeOut:CadruUrmator=ConfAsteptata;for(i=1;i<=ntampon;i++){

transmite(CadruUrmator);

inc(CadruUrmator);}} // switch

if(ntampon<MaxSecv) ActivRetea();else DezactivRetea();

}forever;

}





Protocol cu retransmitere selectivă (1)

• Fereastra receptorului nu poate fi egală cu cea a

transmiţătorului: – 1. Transmiţătorul trimite cadrele 0..6. – 2. Cadrele sunt recepţionate şi confirmate. Fereastra receptorului

devine 7, 0, 1, 2, 3, 4, 5. – 3. Toate confirmările sunt pierdute (se strică sincronizarea între

transmiţător şi receptor). – 4. Transmiţătorul retrimite cadrul 0 la time-out. – 5. Receptorul acceptă cadrul 0 aflat în fereastr ă drept cadru nou şi

cere cadrul 7 de dinaintea lui 0 (și care lipsește). – 6. Transmiţătorul interpretează că a trimis corect cadrele 0..6 şi

trimite 7, 0, 1, 2, 3, 4, 5.

– 7. Receptorul acceptă cadrele, cu excepţia lui 0, pentru care aredeja un cadru recepţionat. Ca urmare, ignoră acest cadru, luând înlocul lui duplicatul cadrului 0 anterior.





Protocol cu retransmitere selectivă (2) void protocol6(){

initializari_contoare;

do{ even=wait();switch (even)

case ReteaPregatita:accepta_salveaza_si_transmite_un_cadru; break;

case SosireCadru:r=DeLaFizic();if (r.fel == data){

transm_nak_daca_r_dif_de_cadru_asteptat;accepta_cadru_daca_in_fereastra_receptie;livreaza_pachetele_sosite;actualizeaza_fereastra_receptie;

}if (r.fel == nak) retransmite_cadru_cerut;trateaza_confirmare_cadre_eliberind_buffere;

break;

case EroareControl: transmite_nak; break;

case TimeOut: retransmite_cadrul_corespunzator; break;

case ReteaLibera: transmite_confirmare_ack;}activeaza_sau_dezactiveaza_nivel_retea;

}forever;}





Exemple de protocoale

• HDLC – High-Level Data Link Control.

• Folosite pentru legătura de date în Internet: – SLIP. – PPP.





HDLC procedura LAPB

• HDLC este o familie de protocoale.

• Tipuri de staţii – Primară, generează comenzi. – Secundară, generează răspunsuri. – Combinată, generează atât comenzi cât şi răspunsuri.

• Tipuri de legatură:

– Echilibr ată, cu două staţii combinate. – Neechilibrată, o staţie primară, una sau mai multe secundare.

• Moduri de transfer: – NRM, Normal Response Mode (legatură neechilibrată). – ABM, Asynchronous Balanced Mode.

– ARM, Asynchronous Response Mode.• Procedura LAPB (Link Access Protocol Balanced) corespunde

une legături echilibrate cu staţii combinate.





High-Level Data Link Control

• Format cadru:

• Câmp de control pentru: – (a) Cadru de informaţie. – (b) Cadru supervizor. – (c) Cadru nenumerotat.

• Semnificaţie: – Seq: număr de secvenţă cadru transmis (mod 8 sau 128). – Next: număr de secvenţă pentru urmatorul cadru aşteptat. – P/F (poll/final): invitaţ ie la transmisie sau sfâr şit de transmisie.





Comenzi şi răspunsuri





Legătura de date în Internet

• Un calculator casnic acţionând drept gazdă Internet:





SLIP – Serial Line Internet Protocol

• Nu este standard Internet.

• Protocol de încadrare a pachetelor.• Folosit pentru conexiuni seriale punct la punct peste care

rulează TCP/IP între gazde şi rutere.• Reguli de protocol:

– defineşte două caractere speciale: END (0300) şi ESC (0333).

– o gazdă SLIP trimite date în pachet. – END în pachet (zona date) e înlocuit cu ESC şi ESC_END (0334). – ESC în packet (zona date) e înlocuit cu ESC şi ESC_ESC (0335). – după ultimul octet din pachet se transmite END.





PPP – Point to Point Protocol (1)

• Oferă:

– Încadrare. – Link Control Protocol, LCP. – Network Control Protocol, NCP.

• Format de cadru PPP pentru modul nenumerotat: – Adresa 11111111, toate staţiile acceptă cadrul.

– Control 00000011, nenumerotat. – Protocol, selectează dintre:

• LCP, NCP.• IP, IPX, OSI CLNP, XNS.






• Diagrama simplificată pentru activare/dezactivare linie: Configure-request Code-reject

Configure-ack Protocol-rejectConfigure-nakConfigure-reject

Terminate-requestTerminate-ack

protocolul de retea esteconfigurat folosind NCP(de exemplu pentru IP seface alocare adresa IP)

PPP transporta pachete(de exemplu IP)




• Tipuri de cadre LCP (I Initiator, R Responder):






Sumar

• Funcţiile legăturii de date>

– Încadrare. – Transmisie transparentă. – Control erori. – Control flux. – Gestiune legături.

• Mecanisme folosite (numere de secvenţă, confirmări, ceasuri,sume de control).• Coduri detectoare / corectoare de erori (CRC / Hamming).• Protocoale elementare (date, funcţii, entităţi).• Protocoale start-stop şi cu fereastră glisantă.

• Exemple de protocoale – HDLC (High-Level Data Link Control). – Folosite în Internet:

• SLIP (Serial Line Internet Protocol).• PPP (Point to Point Protocol).

03 nivel legatura date

Documents