Lo strato di collegamento (Parte 1) PDF

1 Lo strato di collegamento Parte 1  2 Strato di collegamento (Data Link) Gli host e i router sono i nodi link i canali di comunicazione che collegano nodi adiacenti lungo un cammino sono i collegamenti...

1 Lo strato di collegamento Parte 1  2 Strato di collegamento (Data Link) Gli host e i router sono i nodi link i canali di comunicazione che collegano nodi adiacenti lungo un cammino sono i collegamenti (link) collegamenti cablati collegamenti wireless LAN Le unità di dati scambiate dai protocolli a livello di link sono chiamate frame. I protocolli di strato di collegamento si occupano del trasporto dei pacchetti lungo un singolo canale di comunicazione (link)  3 Strato di collegamento Un pacchetto può essere gestito da diversi protocolli su collegamenti differenti Es., un pacchetto può essere gestito da Ethernet sul primo collegamento, da PPP sull’ultimo e da un protocollo WAN nel collegamento intermedio I servizi erogati dai protocolli del livello di link possono essere differenti Ad esempio, non tutti i protocolli forniscono un servizio di consegna affidabile (controllo d’errore)  4 Servizi offerti dallo strato di link Framing I protocolli incapsulano i pacchetti del livello di rete all’interno di un frame a livello di link Se necessario (reti ad accesso multiplo) il protocollo MAC controlla l’accesso al mezzo Per identificare origine e destinatario vengono utilizzati indirizzi “MAC” Rivelazione e correzione degli errori Gli errori sono causati dal transito del segnale nel mezzo trasmissivo Il nodo ricevente individua la presenza di errori è possibile grazie all’inserimento, da parte del nodo trasmittente, di bit di controllo di errore all’interno del frame Il nodo ricevente oltre a rivelare l’errore e lo corregge  5 Servizi offerti dal livello di collegamento Controllo di flusso Evita che il nodo trasmittente saturi quello ricevente Consegna affidabile dei dati e ritrasmissione Nel caso i requisiti dell’applicazione impongano una consegna affidabile dei dati il protocollo di link può effettuare la ritrasmissione delle frame affette da errore Questa funzione può essere eseguita anche nello strato di trasporto (es. TCP) È normalmente utilizzata nei collegamenti soggetti a elevati tassi di errori (es.: collegamenti wireless) Half-duplex e full-duplex Nella modalità full-duplex gli estremi di un collegamento possono trasmettere contemporaneamente nella modalità half-duplex la trasmissione nei due versi è alternata  6 Esempio di implementazione In tutti gli host È realizzato in una applicazione Network Interface trasporto rete CPU Memoria Card (NIC) collegamento Es. scheda Ethernet, host bus PCMCI, 802.11 (es, PCI) Controllore Implementa il livello di collegamento fisico collegamento e fisico Trasmissione E’ una combinazione di hardware, software e Network adaptor firmware  7 Esempio di implementazione pacchetto pacchetto Control- Control- lore lore host host mittente frame pacchetto ricevente Lato mittente: Lato ricevente: Incapsula un pacchetto in Individua gli errori, un frame. trasferimento dati affidabile, controllo di Imposta il bit rilevazione flusso, etc. degli errori, trasferimento dati affidabile, controllo di Estrae i pacchetti e li flusso, etc. passa al nodo ricevente  8 Framing  9 Framing Ha lo scopo di formare la PDU di strato (frame) incapsulando la PDU di strato superiore (pacchetto) L’entità ricevente deve essere in grado di riconoscere senza ambiguità l’inizio e la fine di ogni frame (funzione di delimitazione) Ad ogni frame viene aggiunto all’inizio e alla fine una sequenza fissa di bit, denominata flag L’entità ricevente esamina il flusso binario entrante e delimita le frame riconoscendo i flag di apertura e di chiusura Problema della simulazione del flag all’interno della frame  10 Esempio di funzione di delimitazione Una possibile configurazione del Flag di delimitazione è 01111110 Per evitare la simulazione si utilizzano le funzioni di Bit stuffing In emissione, si aggiunge uno “0” dopo ogni sequenza di cinque “1” consecutivi all’interno della frame indipendentemente da quale sia il bit successivo Bit destuffing In ricezione si contano gli “1” consecutivi Quando sono ricevuti cinque “1” consecutivi, si esamina la cifra successiva se è un “1”: la sequenza di cifre binarie è un Flag se è un “0”: questo è un bit di stuffing e deve quindi essere eliminato  11 Esempio bit stuffing Sequenza originale 1 0 1 1 1 1 1 1 1 1 1 1 1 0 1 1 0 1 1 1 1 1 0 0 1 1 1 1 1 1 0 0 Sequenza trasmessa 1 0 1 1 1 1 1 0 1 1 1 1 1 0 1 0 1 1 0 1 1 1 1 1 0 0 0 1 1 1 1 1 0 1 0 0 Sequenza ricevuta bit di stuffing 1 0 1 1 1 1 1 0 1 1 1 1 1 0 1 0 1 1 0 1 1 1 1 1 0 0 0 1 1 1 1 1 0 1 0 0 0 dopo cinque “1” bit di bit di bit di consecutivi: stuffing stuffing stuffing bit di stuffing bit eliminato bit eliminato bit eliminato bit eliminato  12 Byte stuffing e de-stuffing Utilizzata nel protocollo PPP (Point to Point Protocol) Byte stuffing (si usa una sequenza nota come «control escape» 01111101) In emissione, se in una parte della frame compare la sequenza “01111110” (ad eccezione del flag”) o la sequenza “01111101” viene premesso il byte “01111101” Byte destuffing In ricezione Se si ricevono due byte consecutivi “01111101” uno dei due viene eliminato Se si riceve un “01111101” seguito da un “01111110” il primo viene eliminato Se si riceve un solo “01111110” viene riconosciuto come flag Esempio Sequenza originale 1 0 1 1 1 1 1 1 1 0 1 1 0 1 1 1 1 1 0 1 0 1 1 1 1 1 0 0 Sequenza trasmessa 1 0 1 1 1 1 1 1 1 0 1 1 0 1 1 1 1 1 0 1 0 1 1 1 1 1 0 1 0 1 1 1 1 1 0 0  13 Rivelazione e correzione d’errore  14 Controllo d’errore La trasmissione introduce errori Bit Error Rate (BER) Il controllo d’errore si usa quando il livello trasmissivo non soddisfa i requisiti dell’applicazione Il controllo d’errore assicura un determinato livello di accuratezza nella trasferimento di uno stream dati Due approcci possibili Error detection & retransmission (ARQ) Forward Error Correction (FEC)  15 Principio base del controllo d’errore Si organizza la trasmissione in modo da trasformare i blocchi di dati trasmessi in particolari “parole di codice” (codeword) Se il blocco ricevuto non è una parola di codice è considerato in errore E’ necessaria una ridondanza (overhead) costituita da un insieme di bit di controllo da aggiungere al blocco dati d’utente E’ possibile che il canale trasformi la parola di codice trasmessa in una stringa di bit che è ugualmente una parola di codice Informazione Controllo della d’utente Codificatore Canale codeword Codeword  16 Rivelazione di errore (2/4) Se k è la lunghezza del blocco da proteggere; n-k è il numero di bit di controllo Le codeword sono di lunghezza uguale a n bit Se una PDU è colpita da errore e se questi sono in configurazione tale da non essere rivelati (sostituzione di codeword), si verifica l’evento di “errori non rivelati” I metodi di codifica per rivelare errori rientrano usualmente nella categoria dei codici con controllo di parità (parity check codes) codici a parità singola codici a parità a blocchi codici a ridondanza ciclica (CRC, Cyclic Redundancy Check)  17 Funzione di Error Detection Bit informativi Bit ricevuti Calcolo dei k bit di controllo bits Calcolo Canale dei bit Comparatore di controllo Bit di Bit di controllo La frame è controllo ricevuti accettata solo se i trasmessi n-k bit bit di controllo ricevuti sono uguali a quelli calcolati  18 Controllo di parità singola Aggiunge un bit di parità a k bit informativi Info Bit b1, b2, b3, …, bk Check Bit bk+1= (b1+ b2+ b3+ …+ bk ) modulo 2 Codeword (b1, b2, b3, …, bk,, bk+1) Un blocco dati trasmesso ha un numero pari di “1” Il ricevitore controlla se il numero di “1” è pari E’ rivelabile una qualsiasi configurazione di errore che modifica un numero dispari di bit Tutte le configurazione di errore che modificano un numero pari di bit non sono rilevabili  19 Esempio Bit informativi (7 bit): (0, 1, 0, 1, 1, 0, 0) Bit di parità: b8 = 0 + 1 + 0 + 1 +1 + 0 + 0 = 1 Codeword (8 bit): (0, 1, 0, 1, 1, 0, 0, 1) Errore singolo nel bit 3 : (0, 1, 1, 1, 1, 0, 0, 1) Numero di “1” è uguale a 5 (dispari) Errore rivelato Errore nei bit 3 and 5: (0, 1, 1, 1, 0, 0, 0, 1) Numero di “1” = 4 (pari) Errore non rivelato  20 Prestazioni del controllo di parità Ridondanza Il controllo di parità aggiunge 1 bit di ridondanza ogni k bit informativi overhead = 1/(k + 1) Errori rivelati Una configurazione di errore è una stringa binaria composta da (n=k+1) bit [(k+1)-tuple], in cui sono presenti bit “1” nelle posizioni in cui si sono verificati gli errori, mentre gli altri bit sono uguali a “0” Tutte le configurazioni di errore con un numero dispari di bit modificati sono rivelati Tra tutte le 2k+1 (k + 1)-tuple binarie, ½ hanno un numero dispari di “1” Solo il 50% delle configurazioni di errore possono essere rivelate  21 Prestazioni del controllo di parità Normalmente si assume l’ipotesi che i canali introducono errori sui bit in modo indipendente con probabilità p una statistica più attendibile prevede errori a burst Alcune configurazioni di errore sono più probabili di altre p P = p (1 − p ) = (1 − p ) 7 8 1−p 2  p  P = p (1 − p ) = (1 − p )  2 6 8    1 − p  Poichè si può assumere p