Livello di collegamento e framing

Dove siamo e di che cosa si occupa

Il livello di collegamento (Data Link Layer, DLL) sta sopra il fisico e sotto la rete (Modello ISO-OSI e pila TCP-IPUna comunicazione tra due calcolatori è un problema troppo vario (segnali, errori, accesso al mezzo, instradamento, controllo di flusso, rappresentazione dei dati) per un solo protocollo, quindi si divide in strati (layer). Il modello ISO/OSI ha 7 livelli (fisico, collegamento, rete, trasporto, sessione, presentazione, applicazione); la pila TCP/IP riunisce gli ultimi tre in un solo livello applicazione, quindi ne ha 5. Ogni livello offre un servizio a quello sopra e parla solo con il livello pari dell'altro nodo tramite PDU; scendendo si aggiunge un'intestazione (PCI): incapsulamento. Indirizzi: MAC (collegamento, locale), IP (rete, globale).Modello ISO-OSI e pila TCP-IP →). I suoi protocolli del corso: ARP, ARQ, HDLC, PPP, LLC, per l'accesso al mezzo ALOHA, slotted ALOHA, CSMA, CSMA/CD, CSMA/CA, e TDMA, FDMA, SDMA, CDMA, OFDMA.

Terminologia.

• Nodi (nodes): host e router.
• Collegamenti (links): canali di comunicazione che uniscono nodi adiacenti lungo il percorso. Un'unità di dati deve attraversare molte reti (LAN e WAN) collegate da router; ogni tratto è un collegamento, anche punto-punto.
• Frame: la PDU del livello di collegamento. Incapsula il datagramma ricevuto dal livello rete: la sua intestazione (PCI) e l'eventuale coda circondano il datagramma IP, che è la SDU del frame.

Definizione (compito del DLL). Consegnare un frame da un nodo a un nodo fisicamente adiacente attraverso un collegamento, possibilmente in modo affidabile. Frame diversi possono essere trasportati da protocolli di collegamento diversi su collegamenti diversi.

Esempio (analogia del viaggio Padova - New York). Auto da Padova all'aeroporto di Venezia, aereo fino a New York JFK, metropolitana fino al centro. Il turista è il frame, ogni tratto è un collegamento, il mezzo di trasporto è il protocollo di collegamento, l'agenzia di viaggio è l'algoritmo di instradamento (livello rete).

Servizi del livello di collegamento

• Framing: incapsulare il datagramma in un frame, aggiungendo intestazione e coda.
• Accesso al collegamento (MAC): se il mezzo è condiviso, regolare l'accesso; gli indirizzi MAC nelle intestazioni identificano sorgente e destinazione.
• Controllo di flusso: adattare il ritmo tra nodo trasmittente e ricevente adiacenti (il ricevitore non deve essere sommerso).
• Rilevazione degli errori: gli errori sono causati da attenuazione e rumore; il ricevitore rileva la presenza di un errore e chiede la ritrasmissione al trasmettitore oppure scarta il frame.
• Correzione degli errori: il ricevitore identifica e corregge i bit errati senza ritrasmissione.

I due sottolivelli

Il DLL si divide in due sottolivelli:

• Data Link Control (DLC): gestisce i problemi comuni sia ai collegamenti punto-punto sia a quelli broadcast: framing, controllo di errore e controllo di flusso;
• Medium Access Control (MAC): gestisce i problemi specifici dei collegamenti broadcast (mezzo condiviso): accesso casuale, accesso controllato, canalizzazione (Protocolli di accesso multiplo - ALOHA e CSMAQuando più stazioni condividono lo stesso mezzo serve un protocollo di accesso (MAC) che decida chi trasmette. Accesso casuale: ALOHA puro (si trasmette subito, tempo vulnerabile $2t_F$), slotted ALOHA (si parte solo a inizio slot, vulnerabile $t_F$), CSMA (si ascolta prima di parlare, vulnerabile $\tau_p$) con le varianti 1-persistent, non persistent e p-persistent, CSMA/CD (rileva la collisione mentre trasmette: serve $t_F\ge2\tau_p$, quindi un frame minimo) e CSMA/CA del Wi-Fi (IFS, finestra di contesa con backoff esponenziale, ACK, RTS/CTS e NAV). Accesso controllato: prenotazione, polling, token. Canalizzazione: FDMA, TDMA, OFDMA, CDMA, SDMA.Protocolli di accesso multiplo - ALOHA e CSMA →).

(In altre descrizioni il sottolivello LLC, Logical Link Control, fa controllo di flusso e di errore su base locale.)

Controllo di errore. Si può fare in due modi: correzione (aggiungere abbastanza ridondanza per correggere gli errori: FEC, Forward Error Correction) oppure rilevazione con ritrasmissione (la ridondanza basta a scoprire che c'è un errore e il pacchetto sbagliato viene ritrasmesso: ARQ, Protocolli ARQ - Stop-and-Wait, Go-Back-N e Selective RepeatARQ (Automatic Repeat reQuest) rende affidabile un collegamento che sbaglia: il ricevitore conferma (ACK) i frame ricevuti bene, il trasmettitore ritrasmette allo scadere del timeout. Servono timeout (contro il deadlock) e numeri di sequenza (contro i duplicati). Con $t_G=t_F+2\tau_p+t_A$ e probabilità di errore $p$: Stop-and-Wait $\rho=\frac{t_F(1-p)}{t_G}$; Go-Back-N con finestra $N\ge t_G/t_F$ $\rho=\frac{1-p}{1+(N-1)p}$; Selective Repeat $\rho=1-p$. Efficienza $\eta=\rho,I/F$. La finestra ottima è la capacità del tubo in pacchetti. In Selective Repeat esiste anche una lunghezza ottima del frame: con overhead $o$ e probabilità di errore sul bit $P_b$, $x_{ott}\simeq\frac o2+\sqrt{o/P_b}$ (frame più corti se il canale sbaglia di più).Protocolli ARQ - Stop-and-Wait, Go-Back-N e Selective Repeat →; la teoria è in Tecniche ARQ - stop-and-wait, go-back-N e selective repeatL'ARQ (automatic repeat request) usa un codice che rivela gli errori e fa ritrasmettere i pacchetti sbagliati, con conferme ACK/NACK. Con $p=1-(1-P_{bit})^L$ la probabilità che un pacchetto sia errato, $t_P$ il tempo di pacchetto, $t_A$ quello dell'ACK e $\tau_P$ il ritardo di propagazione: stop-and-wait $S=\frac{t_P(1-p)}{t_P+t_A+2\tau_P}$; go-back-N $S=\frac{(1-p),t_P}{1+(N-1)p}$ con $N-1=\left\lceil\frac{2\tau_P}{t_P+t_A}\right\rceil$; selective repeat $S=(1-p)\frac{t_P}{t_P+t_A}$. Il numero medio di trasmissioni di un pacchetto è $\frac1{1-p}$.Tecniche ARQ - stop-and-wait, go-back-N e selective repeat →). La rilevazione usa un codice CRC (Cyclic Redundancy Check). Perché le due strade esistono: un codice con distanza minima $d_{min}$ rivela fino a $d_{min}-1$ errori ma ne corregge solo circa la metà, $\lfloor(d_{min}-1)/2\rfloor$, quindi correggere costa molta più ridondanza che rivelare (Codifica di canale - codici a blocco, distanza minima, rivelazione e correzioneLa codifica di canale aggiunge ridondanza ai bit per rivelare o correggere gli errori del canale. Un codice a blocco $(n,k)$ trasforma $k$ bit in $n$ bit (rendimento $R_c=\frac kn$). Con la distanza di Hamming minima $d_{min}$ il codice rivela fino a $d_{min}-1$ errori e ne corregge $t=\left\lfloor\frac{d_{min}-1}2\right\rfloor$ (decodifica a minima distanza). Vale il limite di Singleton $d_{min}\le n-k+1$. Su un canale binario simmetrico con errore $p$, la probabilità di parola sbagliata è $P_w\le\sum_{i>t}\binom nip^i(1-p)^{n-i}$ e, con $p$ piccola, $P_{bit}\approx\frac{d_{min}}n\binom n{t+1}p^{t+1}$.Codifica di canale - codici a blocco, distanza minima, rivelazione e correzione →); su un collegamento con pochi errori conviene rivelare e ritrasmettere.

Controllo di flusso. Il DLL del nodo trasmittente tenta di spingere frame al ricevente; se questo non riesce a elaborarli e consegnarli alla sua rete con lo stesso ritmo a cui arrivano, viene sommerso. Il ricevente può rimandare al trasmittente un'indicazione per fermarlo o rallentarlo.

Indirizzi MAC

Definizione (indirizzo MAC). Indirizzo del livello di collegamento di 48 bit ($2^{48}\approx2{,}8\cdot10^{14}$ indirizzi possibili, circa $280$ mila miliardi), scritto come $12$ cifre esadecimali separate da due punti, per esempio A3:34:45:11:92:F1.

Perché $12$ cifre: ogni cifra esadecimale vale $4$ bit ($16=2^4$ valori), quindi $48/4=12$ cifre, a gruppi di due (un byte): Basi di numerazione e conversioni - binario, ottale ed esadecimaleUn numero in base $r$ vale $\sum a_i r^i$ (cifre $a_i\in{0,\dots,r-1}$). Conversioni: base $r\to$ decimale con la somma pesata; decimale $\to$ base $r$ per divisioni successive (parte intera, resti letti dal basso) e moltiplicazioni successive (parte frazionaria, parti intere lette dall'alto); binario $\leftrightarrow$ ottale/esadecimale a gruppi di 3/4 bit. Somma, differenza e prodotto binari seguono le regole decimali con cifre 0 e 1; la differenza ha prestiti, il prodotto somma prodotti parziali traslati.Basi di numerazione e conversioni - binario, ottale ed esadecimale →. Quanti indirizzi: $2^{48}=2^{40}\cdot2^{8}\approx(1{,}0995\cdot10^{12})\cdot256=2{,}81\cdot10^{14}$ ($2^{10}\approx10^3$).

• I primi $24$ bit sono l'OUI (Organization Unique Identifier) assegnato al costruttore; gli ultimi $24$ sono specifici della scheda di rete (NIC).
• È locale (vale solo sul collegamento), prefissato per ciascuna scheda e unico al mondo: assegnato dal costruttore.
• Per l'indirizzo di destinazione si distinguono: unicast (seconda cifra esadecimale pari, per esempio A2:34:45:11:92:F1), multicast (seconda cifra dispari, per esempio A3:34:45:11:92:F1), broadcast (tutti 1, FF:FF:FF:FF:FF:FF).

Esempio. Su un PC Linux ifconfig mostra per l'interfaccia eth0 l'indirizzo hardware 28:d2:44:eb:bd:98 e per wlan0 38:b1:db:7c:78:c7: ogni scheda ha il suo. In 28:d2:... la seconda cifra è 8 (pari): indirizzo unicast.

Perché la seconda cifra? Il bit di gruppo è il bit meno significativo del primo byte, che sta nella seconda cifra esadecimale (le cifre sono i due mezzi byte da $4$ bit: la prima cifra sono i $4$ bit alti, la seconda i $4$ bit bassi): se è $1$ (cifra dispari) l'indirizzo è di gruppo. A3 $=1010\,0011$: bit finale $1$, multicast. Al contrario A2 $=1010\,0010$ ha bit finale $0$: unicast. Un numero è dispari se e solo se il suo ultimo bit binario è $1$, ed è per questo che basta guardare la parità della cifra.

Un'interfaccia di rete deve avere (almeno) un indirizzo di collegamento (MAC) e uno di rete (IP). Quando si inoltra, serve associare un MAC alla trasmissione secondo il nodo di destinazione: lo fa Protocollo ARPUn host ha tre «nomi»: nome DNS, indirizzo IP (rete) e indirizzo MAC (collegamento). Per spedire un datagramma IP in un frame serve il MAC del prossimo nodo, che si ottiene da quel nodo con ARP: richiesta in broadcast (MAC destinazione FF:FF:FF:FF:FF:FF, contiene IP e MAC del mittente e l'IP cercato) e risposta unicast con il MAC richiesto, memorizzata nella cache ARP. ARP risolve sempre il prossimo salto (host di destinazione o router), non la destinazione finale. Un broadcast non esce dalla sottorete: il proxy ARP del router risponde con il proprio MAC.Protocollo ARP →; quando un host si collega alla rete gli va assegnato un IP (BOOTP, DHCP).

Framing

Il livello fisico dà la sincronizzazione di bit (stessa durata e temporizzazione di bit per TX e RX), ma i bit arrivano in un flusso continuo. Il DLL deve impacchettarli in frame distinguibili l'uno dall'altro: il framing divide il messaggio in parti più piccole e aggiunge un indirizzo di sorgente e uno di destinazione (nell'intestazione).

Perché non spedire un solo frame enorme:

• un frame molto grande rende inefficienti controllo di flusso e di errore;
• un solo bit errato obbligherebbe a ritrasmettere tutto;
• con frame piccoli un errore di un bit colpisce solo quel piccolo frame.

Dimensione del frame

• Fissa: non servono delimitatori, la dimensione stessa serve da delimitatore (esempio: la WAN ATM).
• Variabile (la più usata): serve un modo per dire dove finisce un frame.
  • Orientato ai caratteri (character-oriented, a byte): i dati sono caratteri di 8 bit (ASCII: Codici binari - BCD, ASCII, Unicode, parità e GrayUn codice binario a $n$ bit distingue $2^n$ elementi. BCD: una cifra decimale ogni 4 bit (1010–1111 non usati; 10 richiede 8 bit, non è il binario del numero). ASCII: 7 bit per 128 caratteri, la cifra ASCII è 011 seguito dal BCD. Unicode/UTF-8: da 1 a 4 byte, compatibile con ASCII. Bit di parità: rileva errori su un numero dispari di bit. Distanza di Hamming = numero di bit diversi. Codice Gray: numeri consecutivi differiscono di un solo bit (sensori di posizione); si costruisce per riflessione o con $g_i=b_i\oplus b_{i+1}$.Codici binari - BCD, ASCII, Unicode, parità e Gray →); intestazione e coda sono multipli di 8 bit. Per separare un frame dal successivo si aggiunge un flag di 1 byte all'inizio e alla fine.
  • Orientato ai bit (bit-oriented): la parte dati è una sequenza di bit da interpretare come testo, grafica, audio, video. Anche qui serve un delimitatore: la maggior parte dei protocolli usa il flag da 8 bit 01111110.

Il problema del flag nei dati e la soluzione: stuffing

Un carattere uguale al flag può comparire anche nei dati, e il ricevitore lo scambierebbe per la fine del frame. La soluzione è inserire bit o byte di riempimento: lo stuffing.

Byte stuffing (orientato ai caratteri). Quando nei dati c'è un byte uguale al flag, si inserisce prima un byte speciale, il carattere di escape (ESC, un'indicazione fissa). Il ricevitore, quando trova ESC, lo elimina e tratta il byte seguente come dato, non come delimitatore. Anche un ESC presente nei dati va preceduto da un ESC (altrimenti il ricevitore non saprebbe distinguere un ESC «vero» da uno che precede un dato). Nel caso peggiore, con dati fatti solo di byte uguali al flag o all'ESC, ogni byte raddoppia: l'overhead può arrivare al $100\,\%$.

Esempio. Con flag 7E ed ESC 7D, i dati 41 7E 42 7D 43 diventano 41 7D 7E 42 7D 7D 43 (due byte aggiunti: uno per il 7E, uno per il 7D). Il ricevitore toglie ogni ESC e tiene il byte che lo segue, ricostruendo 41 7E 42 7D 43.

Bit stuffing (orientato ai bit). Se nei dati compaiono uno 0 e cinque 1 consecutivi, il trasmettitore inserisce subito dopo uno 0 in più. Così lo schema 01111110 del flag non compare mai nei dati: dopo lo stuffing nei dati non esistono mai sei 1 consecutivi (dopo ogni gruppo di cinque 1 c'è sempre uno 0 inserito), mentre il flag ne contiene sei; se nei dati apparisse 01111110 diventerebbe 011111010. Il vero flag non viene riempito dal trasmettitore ed è riconosciuto dal ricevitore. Lo 0 aggiunto viene tolto dal ricevitore: ogni 0 che segue cinque 1 consecutivi è uno 0 inserito.

Esempio. Dati: 0111111011111111 ($16$ bit). Si scorre da sinistra contando gli 1 consecutivi e, appena se ne contano cinque, si inserisce uno 0:

• 0 11111 $\to$ dopo i primi cinque 1 si inserisce 0 (che il dato non aveva): 011111 0; segue il sesto 1 del dato, poi il suo 0: 1 0;
• poi 11111 (altri cinque 1) $\to$ si inserisce 0: 111110; restano 111.

Il risultato è 011111010 111110 111 $=$ 011111010111110111 ($18$ bit: due bit di stuffing). Il ricevitore, vedendo cinque 1 seguiti da uno 0, toglie quello 0 e ricostruisce i $16$ bit originali. Nel caso peggiore (tutti 1) si aggiunge $1$ bit ogni $5$: dieci 1 diventano 111110111110 ($12$ bit). In generale $n$ bit tutti 1 diventano $n+\lfloor n/5\rfloor$ bit, con un overhead massimo del $1/5=20\,\%$: ben meno del byte stuffing.

Il framing è lo strumento che permette poi di numerare i frame e proteggerli con un controllo di errore: è il tema di Protocolli ARQ - Stop-and-Wait, Go-Back-N e Selective RepeatARQ (Automatic Repeat reQuest) rende affidabile un collegamento che sbaglia: il ricevitore conferma (ACK) i frame ricevuti bene, il trasmettitore ritrasmette allo scadere del timeout. Servono timeout (contro il deadlock) e numeri di sequenza (contro i duplicati). Con $t_G=t_F+2\tau_p+t_A$ e probabilità di errore $p$: Stop-and-Wait $\rho=\frac{t_F(1-p)}{t_G}$; Go-Back-N con finestra $N\ge t_G/t_F$ $\rho=\frac{1-p}{1+(N-1)p}$; Selective Repeat $\rho=1-p$. Efficienza $\eta=\rho,I/F$. La finestra ottima è la capacità del tubo in pacchetti. In Selective Repeat esiste anche una lunghezza ottima del frame: con overhead $o$ e probabilità di errore sul bit $P_b$, $x_{ott}\simeq\frac o2+\sqrt{o/P_b}$ (frame più corti se il canale sbaglia di più).Protocolli ARQ - Stop-and-Wait, Go-Back-N e Selective Repeat →. Quando più nodi condividono il mezzo, i frame possono scontrarsi: Protocolli di accesso multiplo - ALOHA e CSMAQuando più stazioni condividono lo stesso mezzo serve un protocollo di accesso (MAC) che decida chi trasmette. Accesso casuale: ALOHA puro (si trasmette subito, tempo vulnerabile $2t_F$), slotted ALOHA (si parte solo a inizio slot, vulnerabile $t_F$), CSMA (si ascolta prima di parlare, vulnerabile $\tau_p$) con le varianti 1-persistent, non persistent e p-persistent, CSMA/CD (rileva la collisione mentre trasmette: serve $t_F\ge2\tau_p$, quindi un frame minimo) e CSMA/CA del Wi-Fi (IFS, finestra di contesa con backoff esponenziale, ACK, RTS/CTS e NAV). Accesso controllato: prenotazione, polling, token. Canalizzazione: FDMA, TDMA, OFDMA, CDMA, SDMA.Protocolli di accesso multiplo - ALOHA e CSMA → e, per l'Ethernet, LAN - Ethernet e Wi-FiUna LAN copre un'area limitata ed è definita dalla famiglia IEEE 802.x (802.3 Ethernet, 802.11 Wi-Fi), che divide il livello di collegamento in LLC e MAC. Ethernet è senza connessione, senza controllo di flusso e senza ACK; usa CSMA/CD 1-persistent; il frame va da 64 a 1518 byte (indirizzi di 6 byte, tipo/lunghezza, dati 46-1500, CRC di 4) e il minimo di 64 B deriva da $t_F\ge2\tau_p$. Dal 10 Mbit/s a coassiale fino al 10 Gbit/s su fibra, con switch full-duplex che eliminano le collisioni. Il Wi-Fi (802.11) usa CSMA/CA, ha i modi BSS (con access point) e ad hoc, EBSS con sistema di distribuzione; adatta il bitrate all'SNR; ha problemi del terminale nascosto e del terminale esposto, risolti in parte da RTS/CTS e NAV.LAN - Ethernet e Wi-Fi →.