7. Nivelul Legătură Date

Nivelul Legătură Date: Introducere
Control Legătură Date punct-la-punct
HDLC: câmpul de control
Legături de difuzare: Protocoale de acces multiplu
Protocoale de acces multiplu
Câteva protocoale de acces multiplu
Studiu de caz: Ethernet
Protocoale de acces întâmplător al grupului
Acces multiplu prin diviziunea timpului: protocol de rezervare
Evaluarea critică a protocoalelor cu acces multiplu
ARP: Protocolul de rezoluţie a adresei (Address Resolution Protocol)
Rutarea şi adresele nivelului fizic: sinteze
Interconectarea LAN-urilor
Punţi versus rutere
LAN-uri comutate 802.3

Nivelul Legătură Date: Introducere

Servicii: livrare sigură a unui pachet de legătură date între două maşini conectate fizic

Două tipuri de legături: punct-la-punct, difuzare

Legături punct-la-punct: un expeditor, un destinatar

• cadru: recunoaşterea biţilor pe fir ca pachete

• comunicaţii sigure

Legături de difuzare: mai mulţi expeditori, mai mulţi destinatari potenţiali

• încadrare

• comunicaţii sigure

• accesarea unui mediu partajat

• adresare

Multe probleme de la nivele superioare apar şi aici.

• comunicaţii sigure: ARQ, verificarea sumei, timere, numere secvenţiale

• adresare

  • adresele nivelului legătură date sunt diferite de cele ale nivelului reţea!

Control Legătură Date punct-la-punct

Foloseşte aceleaşi tehnici ca în nivelul transport

HDLC: high level data link protocol (protocol legătură date de înalt nivel)

• (este învechit)

Formatul cadru HDLC:

• steagul (01111110) este folosit pentru a marca începutul/sfârşitul cadrului

  • umplerea biţilor: dacă sunt cinci de 1 consecutivi în date, expeditorul adaugă un 0, pe care destinatarul îl înlătură

• adresa nodului receptor (pentru legături de difuzare)

HDLC: câmpul de control

Formatul câmpului de control pentru cadrele "data":

• număr secvenţă 3-bit

• număr recunoaştere 3-bit

• P/F 1 bit pentru a indica expeditor-către-destinatar sau invers.

Formatul câmpului de control pentru cadre "supraveghere":

Legături de difuzare: Protocoale de acces multiplu

Canal de comunicaţii unic partajat

• două sau mai multe transmisii simultane prin noduri: interferenţă
• numai un nod poate transmite cu succes la un moment dat
• exemplu de medii cu acces multiplu:

Protocoale de acces multiplu

Algoritm distribuit care determină modul de partajare a canalului de către staţii, respectiv când va transmite staţia.

Comunicaţiile cu canal partajat trebuie să folosească insuşi canalul!

La ce trebuie să ne uităm ân cazul protocoalelor cu acces multiplu:

• sunt sincrone sau asincrone

• informaţiile necesare despre celelalte staţii

• robusteţea (de ex., erori de canal)

• performanţa.

Câteva protocoale de acces multiplu

O taxonomie a protocoalelor de acces multiplu

Protocoale cu acces întâmplător: staţiile îşi dispută canalul, coliziune (pot apare transmisii suprapuse):

• Aloha

• Aloha discretizat

• expeditorul simte accesul multiplu: Ethernet

• acces întâmplător la grup

Protocoale cu acces controlat: staţiile rezervă sau au canal asignat, fără coliziune

• alocarea canalelor predeterminate: acces multiplu cu diviziune de timp

• alocarea adaptivă la cerere a canalului

  • protocoale de rezervare

  • trecerea jetoanelor (magistrală de jetoane, inel de jetoane)

Protocolul Aloha

• simplu: dacă ai pachete de transmis, "transmite pur şi simplu"

• dacă pachetele suferă coliziune, se va încerca retransmiterea lor mai târziu

Analiza protocolului Aloha

Scop: înţelegerea cantitativă a performanţelor protocolului Aloha

• pachete de lungime fixă

• timpul de transmisie a pachetului este unitatea de timp

• trec: S: numărul pachetelor transmise cu succes (fără coliziune) per unitatea de timp

  • în exemplul anterior, S = 0.2 pachete/unitatea de timp

• sarcina oferită: G: numărul de încercări de transmisie de pachete per unitatea de timp

  • notă: S<G, dar S depinde de G

  • modelul Poisson: probabilitatea a k încercări de transmisie în t unităţi de timp:

Prob[k trans în t] = ((Gt)**k )(e**(-Gt))/(k!)

• capacitatea protocolului de acces multiplu: valoarea maximă a lui S peste toate valorile lui G.

Focalizare pe o încercare dată de transmisie de pachet

S = viteza încerării de trans. a pach. * prob[trans reuşite]

= G*prob[niciun alt pach nu se suprapune cu încercarea de trans]

= G*prob[0 alte încercări de trans în 2 unităţi de timp]

= Ge*(-2G)

Treceri Aloha

Notă: trecerea maximă este 18% din capacitatea fizică a canalului

• cumperi o legătură de1 Mb, deşi nu va fi niciodată mai bună de 180Kb!

Aloha discret

Sistem sincron: timp divizat în sloturi.

Dimensiunea slotului egală cu timpul de transmisie a pachetului dat.

Cînd pachetul este gata pentru transmisie, aşteaptă până când începe următorul slot.

Pachetele se pot suprapune complet sau nu.

Performanţa în cazul Aloha discret

S = G*prob[nicio altă transmisie să nu se suprapună]

= G*prob[0 alte încercări de transmisie]

= G*prob[0 alte sosiri în slotul anterior]

= Ge**(-G)

Protocoale de înţelegere a expeditorului

• Aloha este ineficient (şi prost crescut!): nu ascultă înainte de a vorbi!

• Accesul multiplu cu înţelegera expeditorului (Carrier Sense Multiple Access: CSMA)

CSMA ne-persistent:

1. înţelege (ascultă) canalul

2. if {canalul acsultat este ocupat}

then wait random time; go to 1

else transmit packet

CSMA p-persistent:

1. înţelege (ascultă) canalul

2. when {channel sensed idle}

transmit with probability p

else wait random time, go to 1

Canalul respectiv nu va elimina toate coliziunile.

Performanţa va depinde de lungimea canalului

• înârzieri mari de propagare: performanţă slabă
• lungimea reţelelor CSMA trebuie limitată.

CSMA/CD

CSMA cu detecţia coliziunii (CD):

• ascultă în timp ce vorbeşte!

• opreşte transmisiunea când un alt pachet s+a ciocnit cu pachetul dvs.

Aşteaptă un timp arbitrar înainte de a încerca să retransmită.

Performanţa depinde (ca şi în cazul CSMA) de lungimea canalului.

Studiu de caz: Ethernet

CSMA/CD, 1-persistent

Standardul IEEE 802.3

Canalul: cablu coaxial (de obicei)

T: intervalul arbitrar minim

Rezoluţia coliziunii: binar: pachetele sosesc (de la nivelul superior) pentru transmisie.

1. Setează L=1, marchează pachetul ca "gata"

2. după transmisia reuşită, toate gazdele cu pachete "gata" pot transmite

3. if {coliziune}

   • L=L*2, până la 1024

   • aşteaptă cantitatea arbitrară de timp peste L*T unităţi de timp

   • după aşteptare, pachetul este din nou "gata"

   • go to 2

Notă: intervalul de backoff este ajustat dinamic în funcţie de sarcină

• gazde diferite vor avea valori L diferite

• încărcare uşoară: de obicei L mic

• încărcare grea: L mai mare.

Ethernet: exemplu

Mai multe despre ethernet

• Standarde 10 Mb/sec 100 Mb/sec
• Formatul pachetului:

• preambul: 7 biţi care permit sincronizarea ceasurilor expeditor/destinatar

• startul cadrului: 1 byte, desemnează startul cadrului (precum HDLC)

• adresa de destinaţie:

  • "adresă fizică" de 48 bit

  • diferită de adreasa IP!!!!

  • fiecare placă Ethernet din lume are propria sa adresa unică la nivel de hard (asignată de IEEE sau vânzător)

  • adresa destinatarului pentru pachetele de difuzie: va fi primită de toate gazdele ataşate LAN-ului

• adresa sursei: adresă fizică 48 bit

• lungimea: 2 bytes, lungimea maximă a pachetului în 1500 bytes

  • reapelează fragmentarea IP

• data: conţine (este) un pachet (de ex., pachet IP) trimis în jos de la nivelul superior

• tamponul: utilizat pentru a asigura umplerea suplimentară a datelor > 46 bytes

• verificarea sumei.

Protocoale de acces întâmplător al grupului

Mai bune decât backofful arbitrar pentru a separa staţiile care intră în coliziune, căutare structurată pentru exact o staţie.

Permite grup de staţii.

Dacă apare coliziunea, divide grupul până când numai o staţie pregătita este permisă.

Structură arborescentă.

1. toate staţiile rutate la nodul de rutare disponibile

2. if {nicio staţie nu transmite)

return

else if (one station sends)

return

else /* collision */

resolve(leftchild(rootnode))

resolve(rightchild(rootnode))

Acces întâmplător în grup: exemplu

Presupunem staţiile 2, 3, 7, 8 gata cu pachetele

A disponibil, coliziuni

B disponibil, coliziuni

D disponibil, SUCCES cu 2

E disponibil SUCCES cu 2

C disponibil, coliziuni

F disponibil, inactiv

G disponibil, coliziuni )puteau fi evitate!)

7 disponibil, SUCCES

8 disponibil, SUCCES

Protocoale de trecere a jetoanelor

Jetoanele circulă printre staţii

Media:

• conexiunea inel jetoane: IEEE802.5, FDDI
• magistrală jetoane, IEEE802.4

Pentru a transmite

• staţia trebuie să cpatureze jetonul
• transmite pachetul în timp ce păstrează jetonul
• eliberează (trimite în afară) jetonul

Protocoale, Punti