Capa d'enllaç i xarxes d'àrea local

Com s'encapsulen els datagrames de la capa de xarxa en les trames de la capa 2 per transmetre-les a través d'un enllaç? Els protocols de la capa d'enllaç ofereixen transferència de dades fiable entre routers/nodes? Es poden utilizar diferents protocols de capa 2 en els diferents enllaços al llarg d'un camí de comunicació? Aquestes són algunes de les preguntes que s'intentarà respondre en aquest apartat.

S'utilitzarà una sèrie de generalitzacions de vocabulari que cal comentar:

• Node : Màquina final o router. Desde la capa d'enllaç no hi ha diferència entre ambdós dispositius.
• Link : Canal de comunicació que connecta nodes adjacents en un camí(path) de comunicació.

És important diferenciar els dos tipus de canals existents en la capa d'enllaç, com són:

• Canals Broadcast (comuns): Un únic canal amb diferents nodes receptors i transmissors. Com per exemple en xarxes locals sense fils (WLAN) o bé en una LAN connectada amb concentradors.
• Enllaços de comunicació punt a punt (Point-to-Point): Només hi intervenen dos nodes, com en el cas de nodes connectats a través d'un switch.

Serveis de la capa d'enllaç

Una de les principals funcionalitats que ha d'implementar la capa d'enllaç és encapsular un datagrama de la capa superior en una trama quan un node vol transmetre. Enviar la trama per un camí de comunicació sempre assegurant la correcta comunicació entre els nodes d'aquest camí. És a dir, té la feina de moure aquests datagrames entre tots els nodes que conformen el camí de comunicació entre el node origen i el destí.

Alguns dels serveis que també pot proporcionar són:

• Framing : empaquetar les dades proporcionades per la capa superior en una trama. Headers + Dades = Trama.
• Link access : Coordinar els accessos a transmissió i recepció quan hi intervenen molts nodes d'una forma equitativa, funcional i equilibrada.
• Reliable delivery : moure un datagrama al llarg d'un enllaç sense errors.
• Control de fluxe : Per tal de prevenir pèrdues de paquets.
• Detecció i correcció d'errors
• Full-duplex : els nodes poden rebre i transmetre simultaniament.
• Half-duplex : els nodes NO poden rebre i transmetre simultaniament.

Detecció i correcció d'errors

Com ja s'ha dit, la detecció i correcció d'errors són dos serveis que la capa d'enllaç sovint proporciona. Aquests serveis també s'ofereixen a la capa de transport, com es veurà en apartats posteriors.

Així doncs, estudiarem els tres mètodes més utilitzats per a la comprovació d'errors, que són:

• Parity check
• Checksum
• Cyclic Redundancy Check

Parity Check

Si es vol transmetre unes dades D que consten de d bits, s'afegeix un bit adicional anomerat bit de paritat. Si s'utilitza un esquema de paritat parell, es tria el valor del bit de paritat tal que el nombre de 1's de D+d sigui parell.

El mateix per a l'esquema de paritat imparell, s'estria el valor de d tal que el nombre de 1's sigui imparell.

En recepció, només cal saber quin esquema s'utilitza i comprovar que el nombre de 1's sigui el que correspon.

Checksum

Si les dades a transmetre D estan formades per una sèrie de k-bits, s'afegeix un altre k-bit al final, amb valor el complement a 1 de la suma de la resta de bits (sumant també el carry final).

En recepció, cal fer la suma de tots els k-bits rebuts, incloent el de checksum, i comprovant que tot són 1's. Si algun d'ells és 0, indica que hi ha error.

CRC - Cyclic Redundancy Check

Trama a transmetre D amb d bits, amb polinomi generador G amb r+1 bits. Es requereix que el bit més significatiu de G sigui un 1.

Donades unes dades D, el transmissor escollirà r bits adicionals, R, i els afegira al final de D per tal que els d+r bits siguin exactament divisibles per G en mòdul 2.

En recepció és senzill, el receptor divideix els d+r bits per G. Si el residuu és diferent de zero, hi ha hagut un error. Si el residuu és zero, les dades són acceptades.

En aritmètica mòdul dos, la suma i la resta són idèntiques i equivalents a efectuar la funció lògica XOR bit a bit.

Així doncs, el que s'enviarà serà T = (D*2^{r})XOR(R). Com que volem trobar una R tal que compleixi (D*2^{r})XOR(R) = nG, observem que R = remainder(\frac{D*2^{r}}{G}).

Detecció d'errors

Les dades que es transmeten són : T = (D*2^{r})XOR(R) on T=nG. El receptor, però, rebrà U = T XOR E, on E és el vector d'errors i indica les posicions on hi ha hagut canvi de bit.

Poden passar els següents casos:

• Si no hi ha errors, aleshores E = 0 i T/G = n + R, per tant, tot correcte.
• Si E és un múltiple de G, no es detectarà error.
• Si E = x^{i}, es detecta error si G té 2 o més 1's.

• Si E = x^{{i} + x}{j}, es detecta l'error si G és un polinomi primitiu.

• Si G(x) = (x+1)Q(x), es detecten tots els vectors E amb un número d'errors imparell. És a dir, si dividim G entre 0b11 i el residuu és zero, es detecten errors imparells.
• Si tenim r bits de redundància i el polinomi comença i acaba en 1, si l'amplada de la ràfega d'errors e \leq r, en qualsevol posició de E es detectarà error.
• Si e = r+1, la única ràfega d'errors que no detectarà serà quan E = G, la resta es detectaran.

• Si e > r+1, la probabilitat de no detectar un error és de 1/2^{r}

Per últim, només comentar que un polinomi G és primitiu si no és múltiple de cap x^{{k}+1 per 1 < k \leq 2}{n}-1 on n és l'ordre de G, i sí ho és per k = 2^{n}-1.

Protocols d'Accés Múltiple

Aquests tipus de protocols van dirigits per als tipus de comunicació de broadcast, ja que cal arbitrar com interactuen els diferents nodes receptors i transmissors en un mateix canal de comunicació.

Com que tots els nodes poden transmetre trames, dos d'ells poden transmetre al mateix temps. Quan això passa, les trames transmeses co\l.lisionen, derivant en una pèrdua de la informació que transportaven.

D'alguna manera, és necessari coordinar les transmissions dels múltiples nodes per evitar aquest efecte.

Podem distingir tres tipus de protocols d'accés múltiple:

• Comartició de canal
• Accés aleatori
• Per torns

No obstant, és desitjable que un protocol d'accés múltiple aplicat a un canal amb amplada de banda màxima R bps, per ser designat com a tal, compleixi amb els següents requisits:

• Si només està actuant un transmissor en un moment donat, cal que transmeti a R bps.
• Si hi ha M nodes transmetent a la vegada, cadascun d'ells ha de fer-ho a una mitjana de R/M bps.
• Cal que sigui descentralitzat i que no depengui d'un node central tot el seu funcionament.
• Ha de ser simple i fàcilment implementable.

Compartició de canal

Hi ha dos tipus de compartició de canal, per temps i per freqüència.

Time Division Multiplexing

Cada node té una porció del temps en un període de transmissió. En general, si hi ha N nodes, hi haurà N porcions del temps mig que es tarda en enviar una trama. Aquesta porció s'anomena slot.

En mitjana, cada node segueix tenint R/N bps d'amplada de banda encara que siguin els únics transmetent, la qual cosa és una feblesa del sistema. No obstant, amb aquest sistema s'aconsegueixen eliminar les co\l.lisions.

Un altre inconvenient d'aquest sistema és que un node sempre ha d'esperar al seu torn per transmetre, encara que sigui l'únic que vulgui fer-ho, la qual cosa és bastant ineficient.

Frequency Division Multiplexing

És la mateixa idea de dividir el canal però ara es divideix l'espectre de freqüències a les quals els nodes envien les dades. Per tant, podràn enviar tots simultàniament però amb una amplada de banda R/N fixa.

D'aquesta manera es soluciona un dels aspectes negatius del TDM, com és que els nodes s'hagin d'esperar al seu torn per transmetre. No obstant, no permet utilitzar la totalitat de l'amplada de banda quan hauria de ser possible.

Accés aleatori

Un node transmissor sempre utilitza la màxima velocitat de transmissió del canal R. Quan hi ha co\l.lisió, s'espera un temps aleatori i es torna a retransmetre, així successivament fins que no n'hi hagi.

Hi ha tres tipus de protocols d'accés aleatori:

Slotted Aloha

Totes les trames tenen una llargada de L bits. El temps es divideix en slots de L/R segons. Els nodes començen a transmetre al inici de cada slot. Com que estàn sincronitzats, tots saben quan comença un slot.

Quan un node té dades a transmetre, s'espera al inici del slot més proper i transmet la trama en el temps que dura l'slot. Si no hi ha collisió tot correcte.

Si dos trames co\l.lisionen en un slot, tots els nodes detecten la co\l.lisió abans que l'slot s'acabi. El node retransmet la trama en els següents slots amb una probabilitat p fins que la trama es transmet sense collisió.

Pure Aloha

Quan un node té dades per enviar les transmet en la seva totalitat en el canal compartit. Si la trama collisiona, quan acabi de transmetre's tota s'intentarà retransmetre-la amb una probabilitat p.

En cas que no hi hagi collisió, el node s'esperarà un temps de de transmissió de trama determinat. Després d'aquesta espera ... PREGUNTAR PACO.

CSMA, CSMA/CD

Tenen detecció de portadora. Cada node, quan vol transmetre, escolta el canal abans de fer-ho i és capaç de dir si hi ha altres nodes transmetent.

Si una trama d'un altre node s'està transmetent en l'instant que un node vol fer-ho, aquest s'espera un temps aleatori i acte següit torna a consultar l'estat del canal. Aleshores, si el canal és lliure, el node transmet. En altre cas, torna a repetir el cicle.

A més a més, si el protocol implementa detecció de co\l.lisió se'n diu CSMA/CD. La detecció de co\l.lisió consisteix en escoltar el canal mentre s'està transmetent. Si detecte una trama d'un altre node, aquest para de transmetre i utilitza algun protocol que li dirà quan pot tornar a provar de transmetre (per exemple, exponential backoff).

Un dels inconvenients d'aquest sistema és el temps de propagació entre nodes, que si és molt gran augmenta la probabilitat de co\l.lisió.

Per torns

Hi ha dos tipus de protocols de múltiple accés basants en la transmissió per torns.

Polling

Un node es el node mestre, i va dient cíclicament a tots els nodes que té permís per transmetre fins a un nombre màxim de trames.

Elimina collisions i espais de temps inútils, la qual cosa és bona. No obstant, quan un node té dades per transmetre ha d'esperar a rebre el torn.

A més a més, aquest sistema és centralitzat, si cau el node mestre cau tot. Incompleix un dels principis essencials que havia de complir qualsevol protocol d'accés múltiple.

Token-passing

No hi ha node mestre. Els nodes es van passant una trama especial que indica que tenen el torn per transmetre. Aquesta trama s'anomena token. Quan un node rep el token, el manté només si té dades a transmetre. En altre cas, el passa immediatament.

Un dels inconvenients és que la caiguda de qualsevol node pot fer caure tot el canal.

Adreçament a la capa d'enllaç

Els nodes, tant els hosts com els routers, tenen adreçes de la capa d'enllaç, i s'anomenen adreçes MAC.

Adreçes MAC

Adreçes de la capa d'enllaç, adreçes LAN, adreça física i adreça MAC són sinònims.

Tenen una llargada de 6 bytes, la qual cosa implica que poden haver-hi 2^{48} adreçes diferents. De fet, les adreçes MAC són úniques i van associades als adaptadors de capa d'enllaç. Quan es fabrica l'adaptador, es graba l'adreça MAC a la seva ROM.

Protocol de resolució d'adreçes (ARP)

És un servei que proveeix d'un mecanisme als nodes per traduïr adreçes IP a adreçes MAC.

Resol les adreçes IP només per nodes de la mateixa subxarxa! Cada node té la seva ARP table, on guarda una relació de IP, MAC i TTL, que significa el temps de vida d'aquella adreça IP.

Si volem enviar un paquet a algu de la xarxa local i no sabem la seva MAC, només sabem la IP, què passa?

• El node transmissor crea un ARP query packet, amb el propòsit de
  • preguntar als altres nodes de la subxarxa que determinin la MAC de la corresponent IP.
• Per fer-ho, envia aquest paquet amb adreça MAC destí :
  • FF-FF-FF-FF-FF-FF
• El node que se senti identificat i encaixi amb la seva IP,
  • respondrà amb un response ARP packet amb la seva pròpia MAC.
• El node que preguntava ja pot actualitzar la seva ARP table i
  • enviar la trama.

En canvi, què passa si volem enviar un paquet a algun node fora de la nostra xarxa local?(Exemple de dos sun-LAN's interconnectades amb un router)

• Un node de la subLAN A envia un query ARP paket demanant per la
  • MAC d'una IP d'un host que està a la subLAN B.
• Ha d'enviar a la MAC de l'adaptador del router que fa de pont
  • amb l'altre subLAN. Com l'aconsegueix? doncs amb el protocol ARP.
• Quan ja té la MAC del router, envia el paquet i és rebut pel
  • router. Un cop en aquest punt el router és el responsable que arribi al host de la subLAN B amb la corresponent IP.
• Consulta la seva forwarding table, i la envia a la interfície
  • corresponent. Aquesta passa el datagrama cap al adaptador d'enllaç, que encapsula el datagrama en una nova trama.
• Ara, l'adreça MAC de destí de la trama ja és la del node destí
  • inicial. Com l'aconsegueix? doncs mitjançant el protocol ARP!

Ethernet

Wired LAN. Si un adaptador amb adreça MAC BB-BB-BB-BB-BB-BB rep una trama de dades amb adreça destí BB-BB-BB-BB-BB-BB o FF-FF-FF-FF-FF-FF, entrega el datagrama a la capa superior. En cas contrari, el descarta.

Ofereix un servei no fiable a la capa de xarxa. En tot cas, depen de l'aplicació si creu convenient implementar un mecanisme de retransmissió de paquets.

Quan els nodes d'una xarxa local estàn connectats a través de concentradors, Ethernet es converteix en una Broadcast LAN i és implescindible implementar un protocol d'accés multiple.

En aquest cas, s'utilitza CSMA/CD amb exponential backoff. Quan s'aborta per co\l.lisió la n-éssima vegada, s'escull un valor d'espera V = k*512 bits, on k pertany a {0,1,...,2^{m}-1}, on m = min(n,10).

Dispositius de la capa d'enllaç

Hubs

En català anomenats concentradors, són un tipus de dispositiu que s'utilitza normalment per crear una LAN més gran a partir de diferents sub-LAN's. És la forma més simple d'interconnectar una xarxa d'àrea local.

Malgrat s'utilitzi en xarxes d'àrea local es diu que són dispositius de la capa física, ja que actuen a nivell de bit. En cap cas treballa a nivell de trama d'enllaç.

El seu funcionament és senzill, quan reben un bit en algun de les seves interfícies li augmenten el nivell d'energia i el retransmeten a totes les altres interfícies.

Permeten extendre la màxima distància a la qual poden estar dos màquines finals d'una LAN. No obstant, amplien el domini de co\l.lisió.

No implementa detector de portadora, és a dir, no consulta que el canal estigui lliure abans de transmetre. Això no obstant, és capaç de detectar si en una interfície per la qual està transmetent hi ha col·lisió.

A més a més, si un dels adaptadors o interfícies falla és capaç de detectar-ho i desconnectar-la internament. També són capaços d'acumular informació sobre l'estat del canal i informar a les màquines finals.

Switches

També anomenats commutadors, són dispositius que operen amb trames Ethernet, és per això que són clarament dispositius de capa d'enllaç.

La seva missió és encaminar trames de dades basades en adreçes de destí de les LAN, és a dir, adreçes MAC. Quan una trama arriba a alguna de les seves interfícies, examina el destinatari de la trama (adreça MAC de destí) i intenta encaminar la trama cap a la interfície que porta cap al seu destí.

Permet que cadascuna de les seves interfícies sigui un domini de co\l.lisió aïllat alhora que permeten la intercomunicació entre màquines de diferents sub-LAN's.

És important saber que els switchs no tenen adreçes MAC associades a les seves interfícies, ja que en cap cas canvia l'adreça de destí de les trames (com sí ho fan els routers). Simplement es limiten a encaminar les trames rebudes.

Executen un algoritme de CSMA/CD alhora de transmetre, és a dir, tenen detector de portadora i de co\l.lisió. En cas d'entrar en co\l.lisió mentre alguna de les seves interfícies transmet aquesta entrarà en exponential backoff.

És important saber que els switches són dispositius self-learning: inicialment la seva taula d'encaminament és buida. Quan reben una trama per alguna de les seves interfícies s'apunten l'adreça d'origen i el número d'interfície. Així, quan algú per una altra interfície es vulgui comunicar amb aquest primer host ja sabrà per on encaminar-lo.

També implementen el cut-through-switching, que fa referència a que quan el buffer d'enviament és buit i s'inicia el buffering d'un paquet, immediatament es comença a transmetre en comptes d'esperar-se a que es rebi tot el paquet per després ser enviat.

Point-to-Point Protocol

Aquest protocol, com el nom indica, funciona en enllaços punt a punt. L'únic que cal saber en aquest tipus de protocols és que afegeixen un byte de flag a l'inici i al final de cada trama, normalment és 0b01111110. Però què passa si en les dades també apareix aquest valor? Doncs que abans d'enviar cal revisar les dades i, si es troba un valor igual que el byte de flag, aleshores es repeteix. Amb això s'indicarà al receptor que són dades i no fa referència al flag d'stop.