Lostratodatalink(livello2ISO/OSI) Ringraziamenti Premessa Appuntidelcorso RetiditelecomunicazioneeInternet 

Appunti del corso Reti di telecomunicazione e Internet ^∗

< daniele.iamartino at mail.polimi.it >

Revisione del 2 Marzo 2012

Premessa

Questo documento contiene i miei appunti relativi al corso di Reti di telecomunicazione ed Internet seguito presso il Politecnico di Milano nel primo semestre dell'anno scolastico 2011/2012. Ho pensato, man mano che seguivo il corso, che sarebbe stato molto utile preparare degli appunti chiari, utili non solo a me ma anche eventualmente ad altri.

Mi sono reso conto che nella mia carriera potrebbe essermi molto utile anche avere una semplice reference per questi argomenti, motivo in più per scrivere. Ho pensato quindi di renderlo più approfondito possibile integrando il materiale di vari libri, che trovate nella bibliograa.

Sono ben consapevole che potrebbero esserci svariati errori (avendo scritto questo documento tra notti insonni e la sera dopo le lezioni), non vi do quindi nessuna garanzia sulla correttezza dei contenuti. Segnalatemi pure eventuali errori se ne trovate. Se volete inserire un paragrafo o fare grosse modiche sono ovviamente (in pieno spirito open source) disponibile per integrare le vostre modiche e aggiungere un vostro riferimento negli autori.

Vi prego di ricordare le regole di licenza Creative Commons nel caso voleste ridistribuire questo documento.

Ringraziamenti

Ringrazio Eugenio Guidetti per la realizzazione delle immagini vettoriali dei primi paragra e la segnalazione di alcuni errori.

Lo strato datalink (livello 2 ISO/OSI)

Servizi oerti agli strati superiori

ˆ Gestione del collegamento dati per lo scambio di trame

ˆ Delimitazione delle trame

ˆ Indirizzamento a livello di rete interna (tra gli altri che possono ricevere la stessa trama)

ˆ Controllo di errore: mostrare agli strati superiori un canale di comunicazione ideale senza errori

ˆ Controllo di usso: Evitare la perdita di trame a causa di saturazione della destinazione

ˆ Buer di ritrasmissione

Procedure per il controllo d'errore

Esistono due metodi per il controllo di errore:

ˆ FEC - Forward Error Correction (Correzione dell'errore in avanti)

ˆ ARQ - Automatic Repeat reQuest (Richiesta di ripetizione automatica)

∗Quest'opera è sotto licenza Creative Commons Attribuzione - Condividi allo stesso modo 2.5 Italia License.

FEC - Forward Error Correction

Viene aggiunta dell'informazione a livello 2 per correggere gli errori. Si parla di codice a correzione d'errore. Non è prevista la necessità di invio di un riscontro per confermare la corretta ricezione. La quantità di informazione trasferita sul collegamento dati è indipendente dal tasso di errore.

Un esempio di tecnica FEC utilizzabile con canali con tassi di errore di 1 bit per pacchetto dati è l'utilizzo di un bit di parità.

ARQ - Automatic Repeat reQuest

Ai dati in ogni pacchetto si aggiunge un campo che contiene un codice a rivelazione d'errore, capace di rilevare la presenza di errore ma non di correggerlo. Si richiede poi al trasmettitore di rinviare il pacchetto corrotto. È necessario un canale di ritorno anche per comunicazioni monodirezionali. La quantità di dati trasferiti sul canale è dipendente dal tasso di errore. È inoltre necessario un buer di ritrasmissione.

I protocolli di tipo ARQ sono così suddivisi:

ˆ Stop & Wait

ˆ Continuous ARQ

 Go-back-n

 Selective repeat

Tassonomia sui tempi di trasmissione

I vari tempi sono quindi:

ˆ Tf tempo di trasmissione della trama

ˆ τ tempo di propagazione del segnale

ˆ Tp tempo di processing della trama

ˆ Tatempo di trasmissione del riscontro Tf =Lf

C =



TON =Lf

P



τ = d v dove v ∼= ²₃· c = 2 · 10^{8 m}_s per segnali guidati all'interno di un mezzo

T_p e Ta sono spesso approssimati a 0

Il tempo totale viene spesso espresso come

T_{T OT} = N_f· (T_f+ T_a+ 2 · T_p+ 2 · τ ) dove Nf è il numero delle trame.

Il tempo di propagazione normalizzato viene spesso utilizzato per comodità ed è denito come:

a = τ Tf

Protocolli Stop & Wait

ˆ Trasmetto una trama e aspetto il riscontro positivo (ACK) (Non esiste NACK)

ˆ Il destinatario eettua controllo di usso rallentando i riscontri

In assenza di errori:

Calcoliamo le prestazioni tenendo conto della quantità di tempo in cui stiamo eettivamente inviando dati utili In generale abbiamo che l'ecienza del protocollo è data quindi da:

η = Tf

TT OT

E quindi in questo caso particolare:

η = Tf

Tf+ Ta+ 2 · Tp+ 2 · τ Supponendo Tp= Ta' 0allora

η = Tf

Tf+ 2 · τ = 1 1 + 2 · a

ˆ Aumentiamo l'ecienza aumentando la lunghezza della trama.

ˆ Un'altra stima di ecienza, il throughtput viene fatta tenendo conto anche della frequenza di cifra:

T HR = η · C

In presenza di errori:

ˆ Denisco un tempo di timeout To tra l'invio della trama e un suo nuovo reinvio.

ˆ Utilizzando un timeout risolviamo il problema dei riscontri persi o trame totalmente perse (e non corrotte)

ˆ Il tempo di timeout non può essere scelto a caso ma deve essere almeno di un valore minimo To≥ Ta+ 2 · Tp+ 2 · τ

che considerando Tp= Ta ' 0diventa:

To≥ 2 · τ

ˆ Per denizione il tempo di timeout parte ad essere conteggiato dopo il completo invio del pacchetto (Tf)

ˆ Per evitare di ricevere due volte la stessa trama e pensare che la seconda sia nuova (se viene perso il riscontro), è necessaria una numerazione di pacchetti ad almeno 1 bit.

ˆ Calcoliamo le prestazioni:

 p è la probabilità di errore sul singolo bit.

 P è la probabilità di errore nella trasmissione di una trama.

 ai è la probabilità di successo alla trasmissione della i-esima trama.

 NS è il numero medio di tentativi di trasmissione per trama ricevuta con successo.

 Ipotizzando gli errori sui bit statisticamente indipendenti, sappiamo che una trama sarà ritrasmessa quando c'è almeno un bit sbagliato nella trama o nel riscontro. Abbiamo quindi che:

P = 1 − (1 − p)^Lf+La

* Lf è la lunghezza della trama

* La è la lunghezza del riscontro

* (1 − p) è la probabilità di successo nell'invio di 1 bit, (1 − p)^Lf+La è la probabilità di successo nell'invio di trame e riscontri, sottraendo a 1 si ottengono tutti gli altri casi.

 Calcoliamo ora il numero medio NS di tentativi di trasmissione per trama trasmessa (di cui solo l'ultimo tentativo ha successo):

NS =

∞

X

i=0

i · ai =

∞

X

i=1

i · Pⁱ⁻¹· (1 − P ) = (1 − P ) ·

∞

X

i=1

i · Pⁱ⁻¹= (1 − P ) · 1

(1 − P )² = 1 (1 − P )

* La prima sommatoria P^∞i=0i · ai è la somma pesata del numero di tentativo e la relativa probabilità di successo.

* Pⁱ⁻¹è la probabilità di fallimento per le precedenti, (1 − P ) è la probabilità di successo per l'ultima

* La serie P^∞

i=1

i · Pⁱ⁻¹è una serie nota: è la derivata della somma della serie geometrica.

 Quindi il tempo di invio di una trama lunga Lf è:

TT OT = (NS− 1) · (Tf+ To) + Tf+ Ta+ 2 · Tp+ 2 · τ

* Dove (NS− 1) · (Tf+ T_o)sono tutti i tentativi precedenti in cui scatta il timeout.

 L'ecienza è quindi:

η = Tf

TT OT

= Tf

(NS− 1) · (Tf+ To) + Tf+ Ta+ 2 · Tp+ 2 · τ dove considerando che NS = _{(1−P )}¹ :

η = T_f· (1 − P )

Tf+ To· P + (Ta+ 2 · Tp+ 2 · τ ) · (1 − P )

 Per calcolare l'ecienza massima ci poniamo nella condizione limite di timeout (To= Ta+ 2 · Tp+ 2 · τ ). L'ecienza diventa quindi:

η = η_{M AX} = Tf· (1 − P ) T_f+ T_a+ 2 · T_p+ 2 · τ ipotizzando poi come al solito Ta= T_p' 0abbiamo che

ηM AX = 1 − P 1 + 2 · a

 Notiamo che l'ecienza è fortemente legata al timeout scelto.

Protocolli Continuous ARQ:

ˆ Tentiamo di aumentare l'ecienza permettendo la trasmissione di più trame consecutive in attesa dei riscontri delle prime trasmesse.

ˆ È necessaria una numerazione delle trame in modulo N. Di solito N = 2^b

ˆ TT OT = N_f· T_f+ T_a+ 2 · τ

 L'ecienza può quindi essere calcolata come

η = T_f TT OT

= T_f

Nf· Tf+ Ta+ 2 · τ

 Come sempre il throughtput è calcolato come:

T HR = η · C

Sliding Window

ˆ Si stabiliscono due nestre di trasmissione e ricezione che memorizzano la lista di trame che possono essere ricevute e inviate:

WS =Numero di trame che posso inviare (send)

WR=Numero di trame che posso ricevere (recive)

ˆ Dobbiamo tenere conto anche degli estremi delle due nestre:

L_R=Estremo inferiore della nestra di ricezione

L_S=Estremo inferiore della nestra d'invio

ˆ Il trasmittente è autorizzato ad inviare tante trame n tali che:

LS ≤ n ≤ (LS+ WS− 1)_{(mod N)}

ˆ Il ricevente è autorizzato a ricevere le trame n tali che:

LR≤ n ≤ (LR+ WR− 1)_{(mod N)}

ˆ Il ricevitore all'invio del riscontro relativo alla trama numero LS, incrementa il valore di LS di una unità (in modulo N ).

ˆ Il trasmettitore alla ricezione del riscontro per la trama numero LR, incrementa il valore di LRdi una unità (in modulo N ).

ˆ L'incremento di LR e LS fa ruotare le rispettive nestre (in senso antiorario).

ˆ Solitamente nel caso n = 2³si rappresenta così:

ˆ Per garantire che ci sia un invio continuo di trame no all'arrivo del primo riscontro, è necessario imporre un valore minimo per WS:

WS· Tf ≥ Tf+ Ta+ 2 · τ

 WS· Tf è il tempo totale di trasmissione di tutte le trame della nestra

 Tf+ Ta+ 2 · τ è il tempo necessario alla ricezione del primo riscontro

 Se questa relazione non è soddisfatta, si dice che il meccanismo a nestra strozza la piena utilizzazione del collegamento.

 Nel caso in cui Ta' 0abbiamo:

W_S· Tf ≥ Tf+ 2 · τ

e ricordando ancora che a = _T^τ_f , riscriviamo più semplicemente che la condizione per evitare la strozzatura è:

W_S ≥ 1 + 2 · a

Piggybacking Notare che nei canali bidirezionali non è sempre necessario inviare un riscontro separato, ma è possibile semplicemente inserirlo insieme ai dati che si stanno inviando, in questo modo il riscontro si procura un

passaggio gratis a bordo di un pacchetto dati già in trasmissione.

Vincolo sulla apertura delle nestre Per evitare ambiguità sui numeri di sequenza ricevuti ed evitare di confondere quindi una ritrasmissione con un nuovo pacchetto, è necessario soddisfare la relazione:

WS+ WR≤ N

Protocolli go-back-n

Accetto le trame inviate solo se le ho ricevute strettamente in sequenza ciclica modulo N. Quindi sempre WR= 1.

ˆ Per il vincolo prima discusso abbiamo quindi: WS ≤ N − 1 ⇒ W_S ≤ 2^b− 1, dove il caso migliore da scegliere è sempre

WS = 2^b− 1

ˆ ACK i: sinica ho ricevuto la trama i è tutte le precedenti.

ˆ NACK i signica non ho ricevuto i ma ho ricevuto le precedenti no a i-1, ora aspetto che mi rimandi i e scarto eventuale altra roba in arrivo no a quando non mi arriva i.

ˆ C'è un timeout che scatta alla sorgente dopo che un pacchetto non ha ancora ricevuto un ACK dopo Tosecondi.

ˆ La sorgente non ruota la nestra no a quando non riceve l'ACK di LS alla destinazione.

ˆ Ipotizzeremo che la trasmissione di una trama venga sempre portata a termine, anche se intanto mi sta arrivando un NACK o altro.

Protocollo selective repeat

ˆ WR> 1e ricordiamo che WS+ WR≤ N.

ˆ Per l'ecienza massima del protocollo conviene scegliere

W_S = W_R= N 2

ˆ ACK i: Ho ricevuto i e anche tutte le precedenti

ˆ NACK i: Non ho ricevuto la trama i, non ti dico niente sulle precedenti. Accetto eventuali trame seguenti che rientrano nella nestra (senza però ruotarla quando le ricevo).

ˆ Timeout che scatta dopo Tosecondi dall'invio della trama come per il protocollo go-back-n.

Ecienza dei protocolli Continuous ARQ

In assenza di errori:

In base alla condizione di strozzatura (che in questo caso è l'unico vincolo di ecienza):

ˆ η =

(1 se WS ≥ 1 + 2a

WS·T_f

Tf+2·τ se WS < 1 + 2a

In presenza di errori:

Ricordiamoci che P = 1 − (1 − p)^Lf+La.

η = T_f NS· Tf

= 1 NS

NS è il numero medio di trasmissioni per trasmettere una trama.

Selective repeat

ˆ Non c'è perdita di ecienza legata alla latenza (a dierenza di Stop & Wait)

ˆ Poichè la ritrasmissione interessa solo una trama e non altre:

N_S= 1 (1 − P ) e quindi

η = (1 − P ) Go-back-n

ˆ K =Numero di trame consecutive che devono essere ritrasmesse in seguito ad un errore (è esclusa dal conto la trama con successo).

 Con 1 errore: k+1 trame

 Con 2 errori: k+2 trame

 ...

ˆ Pⁱ· (1 − P ) =Probabilità di accumulare i errori su i trasmissioni ripetute della stessa trama.

NS = 1 · (1 − P ) + (K + 1) · P · (1 − P ) + (2K + 1) · P²· (1 − P ) + ...

N_S =

∞

X

i=0

(i · K + 1) · Pⁱ· (1 − P ) = K · P

1 − P + 1 = 1 + (K + 1) · P 1 − P

ˆ con K ' 2 + 2 · a si ottiene

η = 1 − P

1 − P + 2 · a · P

ˆ Otteniamo quindi in ne che:

η =

( _1−P

1+P +2·a·P se WS ≥ 1 + 2a

W_S·(1−P )

(1+2·a)·[1+(W_S−1)·P ] se WS < 1 + 2a

Conclusioni sull'ecienza in caso di errori:

ˆ Sotto ipotesi di non strozzatura WS ≥ 1 + 2a:

η =

((1 − P ) Selective Repeat

(1−P )

1+P +2·a·P Go-back-n

ˆ Sotto ipotesi di strozzatura WS < 1 + 2a :

η =

(_{WS·(1−P )}

1+2·a Selective Repeat

W_S·(1−P )

(1+2·a)·[1+(WS−1)·P ] Go-back-n

ˆ Selective repeat è meglio di go-back-n ma la dierenza tra i due si riduce man mano che diminuisce la distanza.

ˆ In caso di tasso di errore particolarmente basso però go-back-n diventa paragonabile o anche meglio di Selective repeat, a causa della WS maggiore.

ˆ Stop & Wait ha praticamente sempre pessime prestazioni.

Protocollo HDLC

Tipi di stazioni

ˆ Stazione primaria (controllo del collegamento mediante comandi)

ˆ Stazione secondaria (Opera sotto una stazione primaria ed emette risposte)

ˆ Stazione combinata (Combina operazione primaria e secondaria, emette comandi e risposte)

Tipi di congurazione

ˆ Congurazione bilanciata: Sono presenti due stazioni combinate

ˆ Congurazione sbilanciata: Sono presenti una stazione primaria e una o più stazioni secondarie Tre modalità di trasferimento

ˆ ABM - Asynchronous Balanced Mode (Full-Duplex)

 Utilizzato in congurazioni bilanciate

 Ognuna delle due stazioni combinate può iniziare a trasmettere

ˆ NRM - Normal Response Mode (Half-Duplex)

 Utilizzato in congurazioni sbilanciate

 La primaria può iniziare a trasmettere, una secondaria può solo rispondere

ˆ ARM - Asyncronous Response Mode (chiamato anche LAP-B)

 Utilizzato in congurazioni sbilanciate

 La primaria e le secondaria possono iniziare a trasmettere

ˆ In tutte le modalità è sempre la stazione primaria ad essere responsabile dell'inizializzazione del collegamento Struttura della trama HDLC

Flag Address Control Information FCS Flag

 (8 bit)   (8 · n bit)   (8/16 bit)   (8 · n bit)   (16/32 bit)   (8 bit) 

ˆ Flag (8 bit): Presente in testa e in coda, svolge la funzione di delimitatore della trama, vale 01111110.

ˆ Address (8 · n bit): Campo a 8 bit, estendibile a multipli di 8, specica la stazione secondaria ricevente (nel caso di comandi emessi dalla primaria), oppure la stazione secondaria trasmittente nel caso di risposte.

 L'indirizzo composto da tutti 1 è un indirizzo di broadcast

 Possiamo indirizzare no a 128 stazioni

 Il campo address diventa ridondante per congurazioni punto-punto

ˆ Control (8/16 bit): Campo a 8 bit, estendibile a 16

 Specica il tipo di trama in trasmissione

 Gestisce i meccanismi di numerazione e riscontro

 Ci sono tre tipi di campo di controllo, a seconda dei primi due bit:

* Information (I): Informazione utente, contiene il numero della trama trasmessa e il numero della prossima trama che si aspetta di ricevere, N(R), mandando l'acknowledge implicito di N(R)-1. Il campo P/F sarà descritto in seguito

· Nella versione a 8 bit:

Contenuto: 0 N(S) P/F N(R)

Numerazione: 0 1 2 3 4 5 6 7

· Nella versione a 16 bit:

Contenuto: 0 N(S) P/F N(R)

Numerazione: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

* Supervisory (S): Utilizzato per gestire i riscontri di trama ed eventuale stato di fuori servizio. N(R) indica la prossima trama in attesa di essere ricevuta. A seconda del protocollo ARQ può signicare anche ACK no a N(R)-1. S è un campo utilizzato per specicare altre informazioni che verranno descritte in seguito.

· Nella versione a 8 bit:

Contenuto: 1 0 S P/F N(R)

Numerazione: 0 1 2 3 4 5 6 7

· Nella versione a 16 bit:

Contenuto: 1 0 S 0 0 0 0 P/F N(R)

Numerazione: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

* Unnumbered (U): Gestione del collegamento dati: inizializzazione, chiusura, reset per errore.

· Nella versione a 8 bit:

Contenuto: 1 1 M P/F M

Numerazione: 0 1 2 3 4 5 6 7

· Nella versione a 16 bit:

Contenuto: 1 1 M 0 0 0 0 P/F M

Numerazione: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

 Il campo P/F presente in varie trame del campo Control serve a identicare se il messaggio signica domanda o risposta:

* P/F posto ad 1 serve a sollecitare una risposta (poll) da parte della stazione primaria.

* P/F posto a 0 serve per segnalare una risposta ad un poll (nal) da parte di una stazione secondaria.

ˆ Information ( 8 · n bit ): Può avere lunghezza variabile multipla di 8 bit. È sempre presente in trame di tipo I .

ˆ FCS (16 o 32 bit): Campo a 16 o 32 bit che svolte la funzione di rivelazione d'errore per la trama, utilizzando il checksum di tipo CRC .

ˆ Nota: Il piggybacking viene sempre eettuato quando possibile.

Bit stung per il ag Per poter riconoscere l'inizio di una trama viene utilizzata una sequenza di sei 1 consecutivi, preceduta e seguita da zeri. Cosa accade se questa sequenza è però già presente nella trama o nei dati? Come evitiamo di confondere la ne della trama con un dato? Ci sono vari modi per risolvere questo problema. Quello scelto da HDLC è il bit stung, che funziona nel seguente modo:

ˆ In invio, aggiungo un bit 0 dopo ogni occorrenza di 5 bit 1 (eccetto che nel ag)

ˆ In ricezione, dopo ogni gruppo di cinque 1, tolgo lo zero (se c'è) che segue.

CRC - Cyclic redundancy check

ˆ k = Lunghezza in bit del checksum CRC

ˆ n = Lunghezza in bit del messaggio da proteggere

ˆ Messaggio: [bn, bn−1, bn−2, ..., b2, b1, b0]

ˆ Deniamo un polinomio P (x) di grado n − 1

P (x) = bn· Xⁿ⁻¹+ bn−1· Xⁿ⁻²+ ... + b1· X + b0· 1

ˆ Polinomio divisore D (x) di grado k, preassegnato dal protocollo.

 Esempio per k = 4 abbiamo D (x) = x⁴+ x³+ 1

 Per k = 16:

* D (x) = x¹⁶+ x¹²+ x⁵+ 1CRC-16EU

* D (x) = x¹⁶+ x¹⁵+ x²+ 1CRC-16US 1. Moltiplico: P (x) · x^k

2. Divido il risultato per D (x) con l'operazione di divisione tra polinomi e mi segno il resto R (x). Il mio checksum è R (x).

(a) Possiamo esprimere l'intero messaggio (checksum compreso) con la notazione:

P⁰(x) = P (x) · x^k+ R (x)

3. In ricezione al posto di ricalcolare e confrontare, posso dividere P⁰(x)per D (x), se R (x) = 0 allora il checksum è corretto.

ˆ Nella divisione tra polinomi in modulo 2, i segni non contano nulla (1 + 1 = 0 , 0 − 1 = 1).

ˆ Ricordarsi di sottrarre gli esponenti nella divisione tra polinomi.

Esempio k = 4 , n = 10 , Messaggio: 1001000101 , Divisore D (x) = x⁴+ x³+ 1

ˆ Il nostro polinomio è quindi P (x) = x⁹+ x⁶+ x²+ 1

ˆ P (x) · x^k= x¹³+ x¹⁰+ x⁶+ x⁴

x¹³ x¹⁰ x⁶ x⁴ x⁴ x³ 1

x¹³ x¹² x⁹

\ x¹² x¹⁰ x⁹ x⁶ x⁴ x⁹ x⁸ x⁷ x⁵ x³ x¹

x¹² x¹¹ x⁸

\ x¹¹ x¹⁰ x⁹ x⁸ x⁶ x⁴

x¹¹ x¹⁰ x⁷

\ \ x⁹ x⁸ x⁷ x⁶ x⁴

x⁹ x⁸ x⁵

\ \ x⁷ x⁶ x⁵ x⁴

x⁷ x⁶ x³

\ \ x⁵ x⁴ x³

x⁵ x⁴ x

\ \ x³ x

ˆ Dunque il resto è R (x) = x³+ x e quindi l'FCS è 01010

ˆ P⁰(x) = x¹³+ x¹⁰+ x⁶+ x⁴+ x³+ x Divisore D (x) = x⁴+ x³+ 1

x¹³ x¹⁰ x⁶ x⁴ x³ x x⁴ x³ 1

x¹³ x¹² x⁹

\ x¹² x¹⁰ x⁹ x⁶ x⁴ x³ x x⁹ x⁸ x⁷ x⁵ x³ x¹

x¹² x¹¹ x⁸

\ x¹¹ x¹⁰ x⁹ x⁸ x⁶ x⁴ x³ x

x¹¹ x¹⁰ x⁷

\ \ x⁹ x⁸ x⁷ x⁶ x⁴ x³ x

x⁹ x⁸ x⁵

\ \ x⁷ x⁶ x⁵ x⁴ x³ x

x⁷ x⁶ x³

\ \ x⁵ x⁴ \ x

x⁵ x⁴ x

\ \ \

ˆ Avendo quindi R (x) = 0 il checksum è corretto.

Tipi di errori rilevabili

ˆ Errori su singolo bit, se D (X) ha almeno due termini

ˆ Errori su due bit, se D (X) non rappresenta un fattore di X^m+ 1 per ogni valore di m minore della massima lunghezza di trama ( 1 ≤ m < n + k )

ˆ Errori su un numero dispari di bit, se D (X) è esprimibile come fattore di X + 1

ˆ Errori a burst, con lunghezza del burst inferiore o uguale a quella dell'FCS, cioè a k bit.

Tipi di trame S nel protocollo HDLC

Vengono utilizzate per il controllo di usso e di errore.

ˆ Recive ready (RR): Si tratta del messaggio di acknowledgement/riscontro utilizzato quando non faccio piggybacking. Indico un ACK di N(R), cioè ho ricevuto no a N (R) − 1 e ora mi aspetto l'arrivo di N (R)

ˆ Recive not ready (RNR): Si tratta del messaggio di acknowledgement/riscontro no a N (R) − 1 , però non posso più ricevere! (Ad esempio perché ho il buer pieno)

ˆ Reject (REJ): Messaggio NACK : mi manca la trama N (R), ma ho ricevuto no a N (R) − 1 . Messaggio utilizzato nel protocollo go-back-n

ˆ Selective Reject (SREJ): NACK , mi manca la trama N (R), rimandala! Non ti dico niente sulle trame precedenti. È possibile richiedere la ritrasmissione di più trame (ad esempio SREJ,7,0: rimandami le trame tra 0 e 7)

Tipi di trame U nel protocollo HDLC

ˆ SNRM/SNRME  Abilita NRM o NRM esteso (la versione estesa utilizza numerazione delle trame a 7 bit)

ˆ SARM/SARME  Abilita ARM o ARM esteso

ˆ DISC  Richiesta di disconnessione

ˆ UA  Informazioni di conferma (riscontro per messaggi di inizializzazione)

Protocollo ABM

ˆ È di tipo full duplex.

ˆ Si fa piggybacking dei riscontri sulle unità informative

ˆ I, 0, 1 signica trama informativa con N (S) = 0 e N (R) = 1

ˆ È possibile scegliere di sfruttare un protocollo go-back-n oppure selective repeat.

ˆ C'è il solito timeout To

ˆ È un protocollo pensato per una comunicazione punto-punto tra due stazioni

Protocollo NRM

ˆ È un protocollo half-duplex multiplato, dove c'è una stazione primaria e altre secondartie

ˆ L'inizializzazione del protocollo viene fatta con ciascun client della rete

ˆ Il bit P/F viene settato a P (poll) dalla sorgente quando si aspetta una risposta dalla destinazione, viene invece inviato il bit F (nal) quando la destinazione manda l'ultimo pacchetto di risposta.

ˆ Una stazione secondaria aspetta di essere interrogata da una stazione primaria.

ˆ La scelta go-back-n/selective repeat è arbitraria.

Ecienza dei collegamenti HDLC ABM

Prendiamo a confronto l'utilizzo di go-back-n e selective repeat su un collegamento terrestre e uno satellitare.

ˆ Caso 1:

 b = 3 bit ⇒ N = 2³= 8

 Con go-back-n WR= 1e WS= 7

 Con selective repeat WR= W_S = 4

ˆ Caso 2:

 b = 7 bit ⇒ N = 2⁷= 128

 Con go-back-n WR= 1e WS= 127

 Con selective repeat WR= WS = 64

Caso di un collegamento terrestre con probabilità di errore media

ˆ Per b = 3 il protocollo di tipo go-back-n risulta leggermente più eciente di selective repeat perché la sua

nestra d'invio WS è più ampia.

ˆ Per b = 7 il protocollo di tipo selective repeat è sempre meglio di go-back-n. I due protocolli tuttavia si eguagliano all'eccessivo aumento della lunghezza della trama.

Caso di un collegamento satellitare con probabilità di errore media Per la lunghezza di trama molto piccole o molto grandi, go-back-n e selective repeat si eguagliano, però per b = 7 selective repeat è nettamente superiore.

Go-back-n ha prestazioni pessime perché manda un molte trame inutili perdendo parecchio tempo.

Caso di un collegamento con bassa probabilità di errore In caso di bassa probabilità di errore (ad esempio p = 10⁻⁶), go-back-n è peggio di selective repeat ma non moltissimo. Per lunghezze di trama brevi go-back-n è migliore.

Reti locali LAN (Local Area Network)

Spesso sono implementate con mezzo trasmissivo condiviso.

Tecniche ad accesso multiplo

ˆ Canalizzazione

 FDMA (Suddivisione delle frequenze)

 TDMA (Suddivisione a slot di tempo)

 CDMA (Suddivisione a divisione di codice)

ˆ Accesso dinamico

 Prenotazione: Si suddivide il tempo in slot in cui ciascuna stazione può segnalare la propria volontà di trasmettere prenotandosi, poi ogni stazione in ordine inizia a trasmettere. È eciente ma richiede una buona sincronia (costosa).

 Trasferimento di permesso: Usato nelle arcaiche reti token ring. C'è un gettone di permesso che ruota tra i vari client e gli dà il permesso di trasmettere sulla rete.

 Accesso a contesa (o anche accesso casuale) Ogni stazione ha la liberà di decidere quando trasmettere, se avviene una collisione di dati è necessario fermarsi è riprovare. Il canale di comunicazione è solitamente a bus.

CSMA/CD (Carrier Sense Multiple Access / Collision Detection)

ˆ Il canale viene utilizzato in modo half-duplex.

ˆ Prima di iniziare qualunque comunicazione, la stazione ascolta il canale di comunicazione per vedere se è già occupato (funzionalità di carrier sense).

ˆ Rivelazione di collisioni dei segnali sul bus ed emissione di una sequenza di jamming.

ˆ Algoritmo di backo esponenziale binario:

 In seguito ad una collisione aspetto i · T secondi prima di trasmettere nuovamente. T = 51, 2µs è il tempo di slot. i è un numero scelto a caso tra 0, ..., 2^k− 1 dove k è il numero di collisioni avvenute.

 k resta sso a 10 come valore massimo. Dopo 16 collisioni consecutive viene dichiarato errore.

ˆ Se la trama trasmessa dalla sorgente non è abbastanza lunga, si rischia che la collisione torni quando ormai ho terminato la trasmissione della trama e quindi penso che quella collisione non la riguardi.

ˆ Per evitare questo problema la condizione che deve essere soddisfatta, è che:

Lmin

C = 2 · τ = 2 · dmax

v

dove dmax è la distanza massima tra due stazioni e Lmin è la lunghezza minima delle trame trasmesse.

ˆ Nel caso di Ethernet classico abbiamo Lmin= 64Byte, C = 10^{M b}_s e quindi dmax= 5, 12Km

Progetto IEEE802

Strati superiori Rete

(802.2) LLC Collegamento dati

802.3 802.5 802.11 altro

CSMA/CD Token ringUTP,STP,bra ottica,radio,...WiFi ... Fisico

ˆ Nel documento 802.1 viene denita la struttura generale delle trame 802 e lo schema qui sopra disegnato

ˆ LLC - Logical Link Control: Ha il compito della gestione dei collegamenti logici tra i vari protocolli di livello 2.

ˆ MAC - Medium Access Control: È specico per ogni tipo di LAN, anche se hanno caratteristiche comuni tra loro (vedi MAC address in 802.3 e 802.11). Governa le procedure di accesso al mezzo trasmissivo.

Strato LLC (Logical Link Control)

ˆ Ha il compito di mostrare allo strato network una interfaccia unicata per tutti i vari protocolli di livello 2.

ˆ Il livello LLC è implementato a software (mentre il livello MAC solitamente è implementato in hardware)

ˆ Prende spunto da HDLC.

ˆ Fornisce servizi di:

 Servizio connectionless senza riscontro

 Servizio connection-oriented

 Servizio connectionless con riscontro Struttura della trama

LLC DA LLC SA Control Information 1 Byte 1 Byte 1/2 Byte Variable

ˆ LLC DA (1 Byte): Indirizzo LLC di destinazione. Si tratta di indirizzi a livello applicativo all'interno delle stazioni

ˆ LLC SA (1 Byte): Indirizzo LLC sorgente

ˆ Control (1 o 2 Byte a seconda del tipo di PDU): Sono denite PDU informative e supervisive, in cui il campo di controllo è di 2 byte, mentre le PDU non numerate sono caratterizzate da un campo di controllo di 1 byte.

La struttura di questo campo è uguale a quella del protocollo HDLC

ˆ Information: Payload

Strato MAC (Medium Access Control) generico

ˆ Provvede alla consegna delle unità informative LLC sulla rete

ˆ Gestisce l'indirizzamento tramite un indirizzo univoco chiamato MAC Address

Struttura della trama

MAC DA MAC SA Information FCS 6 Byte 6 Byte Variable 4 Byte

ˆ MAC DA: Indirizzo MAC di destinazione

ˆ MAC SA: Indirizzo MAC sorgente

ˆ Information: Payload

ˆ FCS: checksum Indirizzi MAC

I MAC address sono indirizzi da 6 Byte (48 bit) univoci per ciascuna scheda di rete al mondo. Il mac address è suddiviso in due parti:

 (48 bit) 

OUI Serial number

ˆ OUI: È l'identicatore del produttore della scheda di rete (24 bit)

ˆ Serial number: È un numero di serie univoco assegnato dal produttore alla scheda di rete (24 bit).

ˆ L'ultimo bit consente di distringuere tra indirizzi singoli di broadcast, globali o locali. F F : F F : F F : F F : F F : F F è l'indirizzo di broadcast per inviare a tutte le stazioni della rete locale.

ˆ L'ordine di trasmissione è dal bit meno signicativo

ˆ Gli indirizzi universally administered e locally administered si distinguono per mezzo del settaggio del secondo bit meno signicativo del byte più signicativo dell'indirizzo. Se il bit è a 0, l'indirizzo è universally locally administered o local scope; se viceversa è a 1, esso è globally administered o global scope.

Ethernet 802.3

Contenuto: Preamble SFD Destination Address Source Address Lenght LLC/PDU Padding FCS

Dimensione (Byte): 7 1 6 6 2 0-1500 0-46 4

ˆ Preamble: è una sequenza di bit stabilita a priori, destinata alla sincronizzazione del segnale.

ˆ SFD: è la sequenza 10101011 che contiene una violazione della codica Manchester. Viene utilizzato come Flag per indentifcare l'inizio del frame.

ˆ Destination/Source Address: sono i MAC address destinazione e sorgente.

ˆ Lenght: è la lunghezza del campo informativo seguente. Se il valore rappresentato è maggiore di 1500, si assume PDU pari a 1500 e si ignora Lenght.

ˆ Padding: è un campo utilizzato per garantire che la lunghezza delle trame inviate sia sempre pari alla lunghezza minima di 64 Byte .

ˆ FCS: è un codice a controllo di errore (checksum) di tipo CRC-32.

ˆ IFG (Inter Frame Gap): Non si tratta di un campo della trama. È il tempo di attesa tra la ne di una trama e l'inizio della seguente. Per Ethernet classico abbiamo IF G = 9, 6µs

Mezzi trasmissivi per Ethernet a 10Mb/s (802.3)

XBaseY dove X =velocità in Mb/s , Base signica in banda base, Y è la lunghezza massima del cavo o altro.

10Base5 10Base2 10Base-T 10Base-FP 10Base-FL 10Base-FB

Cavo coassiale Cavo coassiale Doppino UTP Fibra ottica Fibra ottica Fibra ottica

500m max. 185m max. 100m max. 500m max. 2000m max. 2000m max.

100 stazioni max 30 stazioni max. 2 senza hub 33 con hub 2 stazioni max 2 stazioni max

Link segment Link segment Link segment

Dettagli per 10Base5

ˆ Due stazioni devono essere distanti almeno 2,5m tra di loro

ˆ Il cavo che collega la stazione al bus (cavo AUI ) non può essere più lungo di 50m.

Dettagli per 10Base2

ˆ Due stazioni devono essere distanti almeno 0,5m tra di loro.

ˆ Il cavo che collega la stazione al bus (cavo AUI ) non può essere più lungo di 50m.

Regole di interconnessione

ˆ Nel seguito considereremo un hub come un repeater con più porte. In realtà l'hub emette anche jamming per aiutare CSMA/CD.

ˆ Ethernet classico utilizza sempre la codica manchester

ˆ Un dominio di collissione è una zona dove sicamente le stesse trame ethernet possono collidere tra loro.

ˆ In base ad alcune regole empiriche:

 Tra due stazioni qualunque ci possono essere al massimo:

* 5 segmenti

* 4 repeater

* 2 transreciver

 Nel caso di 5 segmenti e 4 ripetitori:

* Massimo 3 mixing segmenti

Fast Ethernet (802.3u) - Ethernet a 100Mb/s (1995)

ˆ Trama uguale a Ethernet classimo, cambiano i tempi:

 Tf M IN = 5, 12µs, Lf M IN = 64Byte , Slot time = 5, 12µs , C = 100^{M b}_s

 Limite teorico: 500m , limite reale: 250m

ˆ Introdotto il full-duplex utilizzando due canali di comunicazione con switch

ˆ Viene aggiunto uno strato di riconciliazione dei mezzi sici sotto a CSMA/CD

ˆ

100Base-TX 100Base-FX 100Base-T4 100Base-T2 2 UTP CAT5 Fibra ottica 4 UTP CAT3 2 UTP CAT3

Stella Stella Stella Stella

4B5B-MLT-3 4B5B-NRZ-I 8B6T PAM5x5

Full-duplex Full-duplex Half-duplex Full-duplex

100m 100m 100m 100m

Gigabit Ethernet (802.3z) - Ethernet a 1Gb/s (1998)

ˆ Viene aggiunto alla trama ethernet un campo extension dopo FCS, per garantire una lunghezza minima della trama di 512 Byte.

ˆ Lf M IN = 512Byte , Tf M IN = 4, 096µs , dteorica= 400m

ˆ La distanza massima reale è 200m

ˆ È possibile trasmettere più trame consecutive senza interporre l'IFG.

ˆ Full duplex solo se uso switch-switch oppure switch-endsys.

ˆ 1000Base-T = 25m

ˆ 1000Base-SX = 550m

10 Gigabit Ethernet (802.3ae) - Ethernet a 10Gb/s (2003)

ˆ Solo full-duplex

ˆ Vietato l'uso di hub

ˆ Permesso solo l'utilizzo di bra ottica come mezzo trasmissivo.

100 Gigabit Ethernet (802.ba) - Ethernet a 100Gb/s e 40Gb/s (2010)

ˆ Richiede apparati molto potenti, permette di scegliere tra 40Gb/s e 100Gb/s.

LAN Wireless - WiFi (802.11)

Con la diusione di dispositivi mobili, si è pensato di standardizzare dei protocolli a livello 2 per utilizzare le onde radio come mezzo trasmissivo. L'utilizzo delle onde radio porta numerosi problemi che non è possibile risolvere applicando le stesse idee utilizzate per Ethernet standard. Basti pensare ai problemi dei disturbi e delle interferenze elettromagnetiche, alla piccola quantità di spettro elettromagnetico a disposizione, la variabilità della potenza del segnale e la necessità di gestire problemi relativi al risparmio di energia.

Lo sviluppo delle wireless LAN ha avuto luogo facendo uso di porzioni dello spettro elettromagnetico non soggette per denizione a regolamentazione e quindi utilizzabili da chiunque (senza bisogno di licenze). Queste porzioni di spettro sono chiamate ISM (Instrumental, Scientic, Medical) e sono in tre gruppi: 900 MHz, 2.4GHz, 5GHz.

Gli standard sviluppati per le reti wireless sono tutti sottostandard del più generale IEEE 802.11 (la cui prima versione risale al 1997), spesso chiamato informalmente WiFi (Wireless Fidelity).

Strato sico di 802.11

Lo strato sico di 802.11 è stato suddiviso concettualmente in due parti:

ˆ Physical Layer Convergence Procedure (PLCP)

ˆ Physical Medium Dependent (PMD)

Phyisical Layer Convergence Procedure

In questa parte dello strato sico si specica come riuscire a trasmettere ecaciemente le trame MAC sul mezzo sico.

A dierenza di Ethernet, sul mezzo sico non viene inviata la trama MAC direttamente, ma è incapsulata a sua volta all'interno di una PLCP PDU strutturata come segue:

PLCP Preamble PLCP Header PLCP SDU

ˆ PLCP Preamble: realizza la funzione di sincronizzazione in ricezione e segnala l'inizio della trama

ˆ PLCP Header: specica i parametri utilizzati nella trasmissione, come ad esempio la frequenza di cifra, la lunghezza della PLCP SDU e fornisce funzionalità di controllo d'errore.

ˆ PLCP SDU (Physical Layer Convergence Procedure - Service Data Unit): è la parte che contiene la trama del sottostrato MAC.

Si noti che l'header della trama PLCP svolge funzioni speciche ed aggiuntive rispetto a quelle svolte a livello MAC.

Physical Medium Dependent

In questa parte dello strato sico si descrivono i vari metodi di trasmissione sica.

Come già accennato, IEEE 802.11 utilizza come bande radio le frequenze ISM; in particolare sono utilizzate le frequenze 2,4GHz e 5GHz.

Nel primo standard IEEE 802.11 i metodi di trasmissione erano tre e operavano nell'ordine dei 1-2Mb/s:

ˆ Infrared

ˆ Frequency Hopping Spread Spectrum ( FHSS)

ˆ Direct Sequence Spread Spectrum ( DSSS)

I due metodi a spettro diuso (spread spectrum) eettuano la trasmissione di un usso di dati di B bit/s utilizzando una banda W molto più grande della frequenza di cifra del segnale numerico da trasmettere. Questo signica che il rapporto ^W_B è molto maggiore di 1 . Il motivo di questa scelta è tentare di combattere le interferenze che possono interessare il segnale trasmesso.

Infrared È un metodo di trasmissione a infrarossi che funziona in modo simile ai telecomandi operando su lunghezza d'onda 850-950 nm con modulazione PPM (Pulse Position Modulation) ed uno schema di codica chiamato codice Gray che riduce gli errori dovuti alla sincronizzazione. La trasmissione può avvenire in modalità punto-punto o in modalità diusa. In questo secondo caso si ha lo svantaggio di una bassa copertura (10-20 metri) e l'interferenza dovuta ai raggi solari.

Frequency Hopping Spread Spectrum (FHSS) Vengono utilizzati 79 canali larghi 1Mhz ciascuno, che iniziano dal margine inferiore della banda ISM a 2,4GHz. La sequenza numerica da trasmettere viene modulata con tecnica FSK (Frequency Shift Keying) su una portante che viene cambiata frequentemente in modo pseudocasuale. Tutte le stazioni conoscono il seme casuale utilizzato per generare le frequenze, quindi possono mantenere la sincronizzazione.

La quantità di tempo spesa in ogni frequenza, ossia il tempo di rotazione, è un parametro regolabile che deve essere minore di 400 msec. La rotazione della frequenza portante permette di ottenere un po' di sicurezza contro inter- cettazioni (un attaccante deve conoscere il seme di rotazione) e rende il sistema abbastanza insensibile alle interferenze radio. Ha buone prestazioni anche per collegamenti su lunghe distanze. Il suo svantaggio principale è la banda ridotta.

Direct Sequence Spread Spectrum (DSSS) In questa tecnica ogni bit viene trasformato in una sequenza di segnali elementari chiamati chip (utilizzando la sequenza Barker), che vengono trasmessi mediante modulazione PSK (Phase Shift Keying). Per la trasmissione dei ussi a 2Mb/s viene utilizzata la modulazione QPSK (Quaternary Phase Shift Keying).

Physical Medium Dependent - I nuovi standard

Successivamente a questi primi metodi di trasmissione, sono stati standardizzati nuovi metodi che utilizzano velocità superiori: 802.11a, 802.11b, 802.11g, 802.11n.

802.11a Utilizza la banda ISM intorno ai 5 GHz per distribuire no a 54 Mb/s. La tecnica di modulazione multiportante utilizzata è OFDM (Orthogonal Frequency Division Multiplexing), che utilizza 52 frequenze (48 dati e 4 per la sincronizzazione) e trasmette contemporaneamente su più frequenze nello stesso momento. Anche se la velocità massima è 54Mb/s, sono state denite altre velocità operative tra cui scegliere, ed è possibile operare anche a 6Mb/s.

Viene utilizzata la modulazione PSK per le velocità no a 18Mb/s, QAM (Quadrature Amplitude Modulation) per velocità superiori. OFDM era stato scelto per garantire la compatibilità con un altro standard europeo chiamato HiperLAN/2.

802.11b Nonostante il nome, questo standard è stato approvato e messo sul mercato prima di 802.11a. Questo standard viene chiamato anche HR-DSSS (High Rate Direct Sequence Spread Spectrum).

Si basa sulla modulazione spread spectrum come DSSS, utilizza però una tecnica di codica più complessa chiamata CCK (Complementary Code Keying).

Sono denite quattro velocità possibili per il usso dati: 1, 2, 5.5 e 11 Mb/s. La velocità da utilizzare viene scelta automaticamente analizzando la qualità del canale. Per garantire la retrocompatiblità con DSSS, alle velocità 1 e 2 Mb/s si utilizza lo stesso metodo di codica di DSSS. Per le ultime due velocità si opera a 1,375 Mbaud con 4 e 8 bit per baud, usando i codici Walsh/Hadamard.

802.11b è più lenta di 802.11a, ma il suo campo d'azione è circa sette volte più ampio.

802.11g Nel Novembre 2001 è stato pubblicato questo nuovo standard, derivato da 802.11b.

Viene utilizzato il metodo di modulazione OFDM (come in 802.11a) ma opera nella più ristretta banda ISM del 2,4 GHz. La velocità massima utilizzabile è 54 Mb/s.

Struttura della rete

In una rete radiomobile si distinguono due tipi di congurazioni: servizio radiomobile base e il servizio radiomobile esteso.

Nel servizio di tipo base le stazioni, il cui insieme è chiamato BSS (Basic Service Set), possono comunicare l'una con l'altra senza restrizioni. Se presente, un'altra stazione chiamata AP (Access Point) agisce da stazione radio base che consente la comunicazione delle altre stazioni con altri apparati remoti di rete. Se non è presente nessun Access Point, la rete prende il nome di rete ad-hoc.

È possibile collegare tra loro più insiemi di BSS in un ESS (Extended Service Set). Ciò viene realizzato con l'interconnessione degli AP delle varie BSS mediante un sistema di distribuzione (DS, Distribution System), che è tipicamente una LAN cablata (per esempio una rete Ethernet).

Il problema della stazione nascosta/esposta

Nonostante il successo delle reti Ethernet, le reti wireless non utilizzano il protocollo CSMA/CD. Il motivo principale è che con i collegamenti radio, la potenza del segnale ricevuto è strettamente dipendente dalla positizione del terminale e quindi non si ha più la certezza di poter rilevare collisioni.

Il problema più noto nelle reti radiomobili è il problema della stazione nascosta. Poiché non tutte le stazionisono all'interno del campo radio delle altre, le trasmissioni che avvengono in una parte della cella possono non essere ricevute in un'altra parte della stessa cella. Può dunque succedere che una stazione, che non riceve i segnali di altre che stanno comunicando tra loro, pensi erroneamente che il canale di comunicazione sia libero e inizi a trasmettere.

Il problema complementare, cioè quello della stazione esposta accade quando una stazione rileva del traco adia- cente e decide di non trasmettere, anche se la sua destinazione è pronta a ricevere e la trasmissione non inuenzerebbe il traco adiacente.

Protocollo CSMA/CA

È un protocollo di accesso diverso che cerca di prevenire le collisioni. Il nome CSMA/CA signica Carrier Sense Multiple Access with Collision Avoidance.

Dunque abbiamo ancora la funzione di sensing del canale ma la possibile presenza di collisioni viene gestita in modo diverso. CSMA/CA supporta due modalità operative:

ˆ Nella prima modalità la stazione controlla se il canale è libero prima di trasmettere. Durante la trasmissione la stazione non controlla il canale ma emette l'intero frame, che può comunque rimanere danneggiato. Se il canale è occupato la stazione rimanda l'operazione no a quando il canale non diventa libero e poi invia i dati. In caso di collisione, le stazione coinvolte rimangono in attesa per un tempo casuale adottando l'agoritmo di backo

esponenziale binario, quindi ritentano.

ˆ Nell'altra modalità operativa di CSMA/CA (basata su MACAW ), viene utilizzato un meccanismo di controllo di presenza del canale virtuale più sosticato. Viene introdotta la procedura di esplicita autorizzazione alla trasmissione da una stazione all'altra, eseguita mediante l'invio di una trama Request To Send (RTS) , cioè

richiedo invio e risposta positiva con una trama Clear To Send (CTS) cioè puoi inviare. Naturalmente pur adottando questo meccanismo le collisioni possono comunque avvenire. Si prevede quindi che le trame dati ricevute correttamente siano esplicitamente riscontrate inviando una trama di acknowledgement (ACK ) cioè di riscontro. Di seguito ci riferiremo sempre a questa seconda modalità operativa (la prima è poco utilizzata).

A causa di svariati motivi, il tasso di errore sulle reti wireless è nettamente superiore a quelle cablate. Per questo motivo si prevede che le trame dati di lunghezza superiore ad una data soglia vengano suddivise in frammenti consecutivi.

In questo modo si limita il numero delle trame da ritrasmettere in caso di errore. Ogni trama ha il proprio checksum, i frammenti sono numerati e inviati con una sorta di protocollo stop-and-wait.

Protocollo di accesso

Lo standard 802.11 prevede due modalità di accesso al canale radio condiviso:

ˆ Distributed Coordination Function (DCF): Modalità distribuita di accesso al mezzo secondo il protocollo CSMA/CA che può dar luogo a collisioni.

ˆ Point Coordination Function (PCF): Procedura aggiuntiva che può essere eettuata in presenza di un Access Point per evitare l'occorrenza di collisioni. Questa seconda modalità è utilizzata molto raramente.

La seconda modalità operativa prima discussa si basa tutta su un discorso di dierenziazione dei tempi di ritardo, per gestire la priorità nell'accesso al mezzo trasmissivo. Vengono identicati quattro diversi intervalli minimi di tempo tra le trasmissioni di trame consecutive, detti InterFrame Spacing (IFS) che elenchiamo qui dal più breve al più lungo:

ˆ Short Interframe Spacing (SIFS): Minimo tempo di attesa dopo la rivelazione della ne trasmissione di una trama. È anche il tempo atteso prima di trasmettere trame ad alta priorità, che sono:

 Trame CTS, ACK

 Trame di risposta a interrogazioni dell' AP

 Frammenti successivi di altri frammenti trasmessi con successo

ˆ PCF InterFrame Spacing (PIFS): Intervallo di tempo intermedio utilizzato per garantire priorità di accesso al mezzo nella modalità PCF.

ˆ DCF InterFrame Spacing (DIFS): Intervallo di tempo più lungo adottato dalle stazioni che operano in modalità DCF per trasmettere il primo frammento delle trame dati e trame di gestione.

ˆ Extended InterFrame Spacing (EIFS): L'intervallo di tempo dopo cui una stazione che ha ricevuto un frammento danneggiato/sconosciuto può annunciarlo alle altre stazioni.

Questi tre tipi di ritardi sono calcolati a partire dal momento in cui termina l'occupazione del canale. All'intervallo di tempo DIFS soltanto segue un intervallo di tempo, detto nestra di contesa, in cui le stazioni che operano in modalità DCF tentano di prendere il controllo del canale mediante l'utilizzo del protocollo CSMA/CA. Lo slot di contesa τ è nell'ordine dei 5 − 50µs.

Di seguito è illustrato il diagramma a stati delle operazioni su CSMA/CA (riferito alla modalità DCF):

Descriamo ora il funzionamento del protocollo nei due casi DCF e PCF Modalità DCF

È la modalità maggiormente utilizzata.

Partiamo dall'esempio della comunicazione rappresentato in gura:

In questo esempio ipotizzeremo l'assenza di collisioni di cui comunque parleremo dopo.

ˆ La stazione A ha una trama da inviare alla stazione B. Aspetta un intervallo di tempo DIFS in cui si assicura che il canale sia libero e poi trasmette una trama RTS di richiesta trasmissione destinata alla stazione B.

ˆ La stazione B attende un tempo SIFS e acconsente alla trasmissione inviando ad A una trama CTS.

ˆ La stazione A attende un tempo SIFS dalla ricezione della trama CTS e inivia i dati.

ˆ Dopo un intervallo di tempo SIFS successivo all'invio dei dati, la stazione B invia una trama ACK per confermare l'avvenuta ricezione dei dati.

Al ne di evitare altre trasmissioni mentre la stazione A sta inviando, che possono provocare collisioni, le trame RTS e CTS contengono al loro interno l'informazione sull'intervallo di tempo di occupazione del mezzo trasmissivo per l'invio e il riscontro della trama in questione (compresi gli intervalli SIFS). Questa informazione di occupazione è chiamata NAV (Network Allocation Vector).

Le altre stazioni che ricevono queste trame (RTS e CTS) restano inattive durante l'intervallo di tempo NAV (signicato dei blocchi NAV per le stazioni C e D nella gura precedente). Il fatto che l'indicazione del tempo sia anche all'interno della trama CTS (oltre a quella RTS) permette di fare in modo che se ad esempio D non riceve il segnale di A ma riceve quello di B, riesce ad accorgersi comunque che è in corso una trasmissione. Questo meccanismo risolve il problema della stazione nascosta.

Caso del canale occupato Una stazione che rivela il canale occupato, attende che il canale permanga libero per un tempo DIFS. Ciò garantisce che le trasmissioni a priorità superiore (cioè tutte quelle che attendono un intervallo di tempo inferiore a DIFS) possano essere eettuate. Se il canale risulta libero dopo un tempo DIFS, viene trasmessa la trama RTS di richiesta di trasmissione. Altrimenti la stazione applica l'algoritmo di backo.

Algoritmo di backo di CSMA/CA Se si entra in fase di backo, la trasmissione viene ritardata di un tempo casuale di i slot, selezionato a caso all'interno di un intervallo di durata massima di K slot. K cresce man mano con il numero di tentativi di trasmissione che non hanno successo. Il valore iniziale dell'intervallo è K = 7 slot, così che il ritardo iniziale è un numero di slot tra 0 e 7. Al tentativo i-esimo, l'intervallo ha ampiezza massima 2²⁺ⁱ− 1slot.

Una particolarità dell'algoritmo di backo utilizzato da CSMA/CA è che gli slot di attesa vengono calcolati solo durante le eettive nestre di contesa, cioè quando il mezzo è libero. Il conteggio degli slot di attesa viene sospeso se si rivela una nuova trasmissione in corso. Il conteggio viene ripreso un intervallo di tempo DIFS dopo la ne dell'occupazione del canale. Esaurito il backo si trasmette la trama RTS.

Collisioni Nonostante il protocollo implementi i meccanismi di permesso con RTS, CTS e il backo, possono comunque avvenire delle collisioni tra le trame. Può infatti succedere che due stazioni emettano una trama RTS nello stesso slot temporale. In questo caso la stazione destinataria non emette (come previsto) la trama CTS entro un tempo SIFS e quindi la stazione che ha emesso la trama RTS applica l'algoritmo di backo.

Questo meccanismo si applica anche quando una trama dati non viene riscontrata da una trama ACK dopo un tempo SIFS. In quest'ultimo caso si noti che è possibile che ci sia un errore sulla trama dati (quindi scartata dalla destinazione ricevente che non conferma con ACK), sia una collisione che ha interessato la trama di riscontro ACK, che non torna al mittente.

Per risolvere questi problemi le trame e i frammenti sono numerati, cosa che permette di riconoscere duplicati in caso di ritrasmissioni.

Frammenti Come già accennato prima, la trasmissione del primo frammento dati richiede un tempo di attesa DIFS, mentre i successivi frammenti vengono inviati dopo un intervallo di tempo libero SIFS. In questo modo si dà priorità al completamento della trasmissione di tutti i frammenti di una trama rispetto all'invio di nuove trame.

Modalità PCF

Nella modalità PCF (raramente utilizzata), una stazione agisce da coordinatore (Coordination Point, PC) e controlla in modo centralizzato l'accesso al mezzo trasmissivo. Questo meccanismo di controllo centralizzato avviene in modo simile a quanto già visto per la modalità NRM del protocollo HDLC. Quindi in modalità PCF non possono vericarsi collisioni a priori, dato che è la stazione centrale a gestire tutti i permessi. La stazione PC risiede su un Access Point e attiva la modalità PCF inviando una trama speciale dopo un tempo PIFS dall'ultima occupazione del canale. La stazione PC invia poi delle trame di interrogazione poll a cui le stazioni rispondono con una distanza temporale pari ad un intervallo SIFS.

Servizi e trama di 802.11

Nel protocollo 802.11 ci sono tre tipi principali di trame:

ˆ Trame di gestione

 Autenticazione

 Associazione

 Sincronizzazione

 ...

ˆ Trame di controllo

 RTS, CTS, ACK

ˆ Trame dati Servizi oerti

Lo standard 802.11 stabilisce nove servizi che ogni LAN wireless deve fornire. I primi cinque sono servizi di dis- tribuzione (riguardano la gestione dell'appartenenza alla cella), gli altri quattro sono servizi stazione (si occupano dell'attività all'interno della singola cella).

1. Associazione: Servizio utilizzato dalle stazioni mobili per eettuare la connessione alla stazione base. La stazione annuncia la propria identità e le funzionalità (velocità, servizi PCF, gestione alimentazione), la stazione base può decidere se accettare o meno. Se accetta il passo successivo è l'autenticazione

2. Separazione: La stazione mobile o quella base possono separarsi interrompendo la relazione. Una stazione mobile dovrebbe utilizzare questo tipo di messaggio per avvisare la stazione base prima di lasciare la cella.

3. Riassociazione: Con questo servizio una stazione mobile può cambiare la propria stazione base da una cella all'altra. Se viene sfruttata correttamente, questa funzionalità permette di evitare la perdita di dati nel passaggio da un access point all'altro.

4. Distribuzione: Servizio che stabilisce come instradare i frame verso la stazione base. Se la stazione base è direttamente accessibile verranno inviati via radio, altrimenti via rete cablata.

5. Integrazione: Servizio che permette la traduzione tra indirizzi di tipo diverso per instradare un frame attraverso una rete non 802.11.

(seguono le operazioni interne alle celle aettuate solo dopo l'associazione)

1. Autenticazione: Per garantire la sicurezza nell'accesso alla rete, la stazione base manda un frame challenge per vedere se la stazione mobile conosce la risposta, se la conosce la stazione mobile risponde con un frame cifrato alla stazione base, per confermare di conoscere il segreto condiviso. Se il risultato è corretto la stazione mobile viene denitivamente registrata all'interno della cella.

2. Invalidamento: Quando si desidera abbandonare la rete, si invalida l'autenticazione precedentemente eettuata.

3. Riservatezza: Le informazioni trasmesse sulla LAN wireless possono essere cifrate per garantirne la riservatezza.

Questo servizio gestisce la codica e decodica dei dati. Il sistema che gestisce la riservatezza, integrato nello standard 802.11 è WEP (Wired Equivalent Privacy) che fa uso di RC4 come algoritmo di cifratura. Questo sistema ha soerto di seri problemi di progettazione, che permettono ad un attaccante di violare la sicurezza di una rete WEP nel giro di pochi minuti. In risposta a questi problemi di sicurezza sono stati inventati i sistemi WPA (Wi-Fi Protected Access).

4. Trasferimento dei dati: 802.11 fornisce ovviamente un modo per trasmettere e ricevere dati. Così come Ethernet però la trasmissione non è adabile e gli strati superiori devono gestire il rilevamento e la correzione degli errori.

Formato di trama

La trama del sottostrato MAC del protcollo 802.11 è strutturata come segue:

Contenuto: FC Duration/ID Address 1 Address 2 Address 3 Seq.Control Address 4 Info FCS

Byte 2 2 6 6 6 2 6 0-2312 4

Discuteremo dei vari campi Address nel segito, vediamo il signicato dei vari campi:

ˆ FC, Frame Control (2 Byte): Comprende un sottinsieme di informazioni strutturate come segue:

Prot.Ver. Type Sub Type To DS From DS More Flag Retry Pwr Mng More Data WEP Order

2 bit 2 bit 4 bit 1 bit 1 bit 1 bit 1 bit 1 bit 1 bit 1 bit 1 bit

ˆ I cui campi sono:

 Protocol Version (2 bit): Specica la versione del protocollo (quella corrente è la 0)

 Type (2 bit): Distingue tra 3 tipi di trama: gestione (00), controllo (01) e dati (10)

 SubType (4 bit): Specica ulteriormente il sotto tipo di trama: (sotto-)trama di assocazione (trama di gestione), (sotto-)trama RTS (trama di controllo)

 To DS (1 bit): Specica come interpretare i campi indirizzo

 From DS (1 bit): Specica come interpretare i campi indirizzo

 More Flag (1 bit): Settato se si tratta di un frame frammento

 Retry (1 bit): Specica se la trama è una ritrasmissione o è la prima volta che viene trasmessa

 Power Management (1 bit): Indica lo stato attivo o in risparmio energetico della stazione radiomobile.

 More Data (1 bit): Indica alla stazione in stato di risparmio energia che ci sono altre trame in attesa nell'AP indirizzate alla stessa stazione.

 WEP (1 bit): Indica che l'informazione trasportata dalla trama è cifrata mediante il sistema WEP.

 Order (1 bit): Specica alla stazione destinazione che le trame devono essere elaborate nell'ordine inviato.

ˆ Duration/ID (2 Byte): Indica la durata di occupazione prevista del canale (NAV ), espressa in microsecondi. Se si utilizza la modalità PCF, nel caso di trame di controllo per interrogazione (poll) indica invece l'identicazione dell stazione sorgente della trama che sta rispondendo ad una interrogazione.

ˆ Sequence Control (2 Byte): Indica, con i primi 4 bit il numero del frammento della trama in corso di trasmissione e con i successivi 12 bit il numero di sequenza (tra 0 e 4095). Ovviamente il numero di trama è lo stesso per più frammenti della stessa trama.

ˆ Information (0-2312 Byte): Contiene le informazioni del protocollo superiore trasportate dalla trama (il livello LLC ).

ˆ FCS, Frame Check Sequence (4 Byte): Contiene il codice di controllo d'errore (checksum) di tipo CRC-32.

I diversi signicati dei quattro campi Address dipendono dai valori assunti dai campi to DS e From DS. In ogni caso gli indirizzi sono MAC address a 48 bit, strutturati allo stesso modo di quelli Ethernet.

Di seguito una tabella riassuntiva con le varie congurazioni:

Caso To DS From DS Address 1 Address 2 Address 3 Address 4 Tipo di trama

A 0 0 Dest. Addr. Source Addr. BSS ID - punto-punto

B 0 1 Dest. Addr. BSS ID Source Addr. - Uscente dal DS

C 1 0 BSS ID Source Addr. Dest. Addr. - Entrante nel DS

D 1 1 Reciver Addr. Transmitter Addr. Dest. Addr. Source Addr. Da BSS a BSS

ˆ Nel caso A il trasferimento della trama avviene all'interno della BSS, di cui viene specicato l'identicatore.

ˆ Il caso B si riferisce ad una trama inviata dal sistema di distribuzione (DS) a una stazione di cui si specica l'indirizzo all'interno di un dato BSS.

ˆ Il caso C, speculare al precedente, si riferisce ad una trama inviata da una stazione all'interno di un dato BSS verso il sistema di distribuzione (DS)

ˆ Il caso D si riferisce alla trasmissione di una trama tra stazioni di BSS dierenti. Il reciver address indica l'indirizzo MAC dell'AP di transito nel BSS sorgente che riceve, allo stesso modo trasmitter address indica l'indirizzo dell'AP del BSS di destinazione.

Prestazioni delle reti LAN

Metriche

ˆ Traco smaltito

ˆ Probabilità di perdita

ˆ Tempo di attraversamento

 Ritardo causato dal buer

 Ritardo di trasmissione

 Ritardo di propagazione

Parametri

ˆ N = Numero dei nodi (esclusi i punti di attraversamento)

ˆ λ = Frequenza media di arrivo in una generica stazione delle unità informative

ˆ C = Velocità della rete ^bit_s

ˆ L = Lunghezza ssa del pacchetto trasmesso

Conseguenze

ˆ Traco oerto alla rete (da tutti): Ao= N · (λ · L) _bit

s



ˆ Traco smaltito dalla rete: AS= (N · λ · L) · (1 − π_p)

 πpè la proababilità di errore per pacchetto

ˆ Se ipotizziamo πp= 0allora il throughtput di rete normalizzato è S = ρ = ^{(N ·λ·L)}_C [Erlang] = [1]

 0 ≤ ρ ≤ 1 indica la quantità di tempo in cui la rete è occupata

 T HR = S · C ^bit_s 

ˆ Nel seguito considereremo il mezzo trasmissimo ideale e privo di errori

Traco su una rete TDMA

Trama 1 Trama 2 Trama 3

1 2 3 ... N 1 2 3 ... N 1 2 ...

 ^{N L}_C   ^{N L}_C 

ˆ Per ogni slot il tempo di trasmissione è TT =_C^L

ˆ S = ρ = ^{N ·λ·L}_C

ˆ Trascurando il tempo di propagazione, abbiamo 3 componenti di ritardo:

 TT tempo di trasmissione nel mezzo

 TW tempo di attesa nella stazione (attesa che i pacchetti nel buer vengano inviati)

 TSync tempo di sincronizzazione, di attesa per l'arrivo dello slot assegnato

ˆ Il tempo TW è determinato da una coda di tipo M/D/1

ˆ TW =_2·(1−ρ)^ρ ·_µ¹ = _2·(1−ρ)^ρ ·^{N ·L}_C

ˆ TSync=^{N ·L}_C ·¹₂ mediamente

ˆ Delay di attraversamento medio:

DT DM A= L

C+ ρ

2 · (1 − ρ) ·N · L

C +N · L 2 · C

ˆ Delay di attraversamento medio normalizzato:

DˆT DM A= DT DM A

TT

= 1 + N · ρ 2 · (1 − ρ)+N

2

Traco su una rete FDMA

Stazione 1 Stazione 2 ... ... Stazione N

 ^C_N   _N^C   _N^C  t

 C 

ˆ Assumiamo 1_Hz^bit

ˆ TT = _{V elocit`}^L _a = ^LC N

=^{N ·L}_C [s]

ˆ S = ρ = λ · TT = λ ·^{N ·L}_C [Erlang] = [1] con sempre 0 ≤ ρ ≤ 1

ˆ Ipotizziamo ancora una coda di tipo M/D/1

ˆ Delay di attraversamento medio:

D_{F DM A}= N · L

C + ρ

2 · (1 − ρ) ·N · L C

 Il termine ^{N ·L}_C è da intendere come il tempo di trasmissione TT

 Il termine _2·(1−ρ)^ρ ·^{N ·L}_C è il tempo TW nel buer

 Non c'è tempo di sync

ˆ Delay di attraversamento medio normalizzato:

DˆF DM A=N · (2 − ρ) 2 · (2 − ρ) osserviamo quindi che rispetto al caso TDMA:

Dˆ_{F DM A}= ˆD_{T DM A}+N 2 − 1

ˆ Quindi TDMA è soprendentemente più eciente di FDMA.

Protocollo ALOHA

ˆ Niente carrier sensing, niente collision detection

ˆ TT =Tempo di trasmissione del pacchetto

ˆ S = Numero medio di trasmissioni con successo in un intervallo di tempo T

ˆ G = Numero medio di trasmissioni tentate in un intervallo di tempo T

ˆ Arrivo dei pacchetti con distribuzione di Poisson con Λ = ^G_T

ˆ S = {Probabilità di passare} = G · {Probabilità che in 2 · T non trasmette nessuno} = G · e^−2·G

 Il massimo si ottiene per G = ¹₂ ⇒ S = 0, 184cioè passa al massimo solo il 18% del traco!

ˆ In base alla metrica del ritardo:

 DALOHA= e^2·G− 1
· TT+ 2 · τ + ^k−1₂ · TT
+ TT + τ

* Il termine e^2·G− 1

rappresenta il numero di tentativi senza successo per ottenere una trasmissione che vada a buon ne.

* Il termine ^k−1₂ · T_T rappresenta la media del tempo di backo.

 Abbiamo quindi un delay di attraversamento medio normalizzato pari a ˆD_ALOHA = e^2·G− 1
·

k+1

2 + 2 · a
+ 1 + a

 Se aumento S e k , D tende ad esplodere