1

Sistemi e Tecnologie della Comunicazione

Lezione 14: data link layer: sottostrato MAC (definizione, protocolli di assegnazione del canale)

2

Reti geografiche e reti locali

Quanto visto fin’ora e’ relativo a comunicazioni a livello due tra stazioni connesse da una linea punto-punto

La totalita’ delle reti geografiche e la quasi totalita’ delle reti metropolitane sono costituite da connessioni punto-punto, per motivi tecnici, economici o legali

la impossibilita’ di stendere un cavo proprietario lungo una tratta geografica di fatto obbliga il progettista della rete geografica ad appoggiarsi alle linee delle compagnie di telecomunicazione

quando anche fosse possibile l’utilizzo di una linea proprietaria, in molti casi entrano in gioco fattori economici che fanno preferire l’affitto di linee gia’ esistenti alla realizzazione di una infrastruttura proprietaria

Nel caso delle reti locali questi limiti non esistono: spesso l’area da interconnettere e’ tutta sotto il controllo della azienda o ente interessato, come il piano di un edificio, un palazzo o un campus

In questa condizione il progettista ha molta liberta’ nello scegliere la tecnologia ed il protocollo migliore, in base a costi, prestazioni, semplicita’ di gestione, robustezza, …

3

Canali broadcast L’estensione limitata delle reti locali permette l’utilizzo di

protocolli che sfruttano un mezzo trasmissivo comune a tutte le stazioni interconnesse (canali broadcast)

reti locali con bus trasmissivo (Ethernet, token-bus) reti locali ad anello condiviso (FDDI, token ring) reti wireless a comunicazione broadcast, cioe’ non direzionale

(802.11a/b/g) Caratteristica di queste tecnologie e’ la disponibilita’ a costi

contenuti di una rete ad alte prestazioni e bassissimi tassi di errore

sono normali rapporti di 1 a 1000 sui tassi di errore dei canali in uso su rete locale rispetto ai canali tipici delle reti geografiche

questo permette di realizzare, come in effetti si fa, protocolli di livello 2 che forniscono servizi non affidabili, demandando ai livelli superiori i controlli sulla integrita’ dei dati

questa considerazione non si applica alle connessioni wireless, che anzi sono molto rumorose, a fronte pero’ della loro caratteristica unica che e’ il supporto alla mobilita’ della stazione connessa

4

Allocazione del canale condiviso

In queste reti esiste un problema che nelle reti punto-punto non esiste: stabilire quale stazione acquisisce il diritto di utilizzare il mezzo trasmissivo in condizioni di competizione (cioe’ quando piu’ di uno vuole trasmettere dati nello stesso intervallo di tempo)

Il problema e’ analogo alla gestione della comunicazione verbale tra gruppi di persone: deve esistere un meccanismo per regolare la comunicazione in quanto la sovrapposizione delle trasmissioni rende tutte le trasmissioni incomprensibili

La funzione di definire l’assegnazione del canale condiviso e’ svolta da protocolli che fanno parte del data link layer

La complessita’ di questo problema e la sua relativa indipendenza dalle questioni relative al trasferimento dei frame fanno si che l’argomento sia trattato come sottostrato indipendente del livello 2, chiamato MAC (Medium Access Control)

5

Assegnazione statica del canale

Studiando lo strato fisico abbiamo visto come lo stesso canale possa essere utilizzato da diversi utenti tramite tecniche di multiplexing FDM o TDM

Queste tecniche hanno la caratteristica di risultare efficienti e funzionali quando il traffico degli utenti e’ regolare e prevedibile, in modo da poter allocare per ogni trasmissione le risorse che questa richiede e che generalmente utilizzera’ per la maggior parte del tempo

In condizioni di traffico irregolare, le utenze che hanno allocato banda o slot temporali e che non le utilizzano costituiscono una inefficienza per l’utilizzo del canale

In genere i calcolatori connessi ad una rete locale non producono un flusso regolare di dati da trasmettere, ma piuttosto alternano periodi di inattivita’ a momenti in cui la quantita’ di dati da trasferire e’ elevata: si possono facilmente trovare differenze di tre ordini di grandezza tra i picchi di traffico ed il rate medio prodotto da una stazione

6

Assegnazione statica del canale (cont.)

In questo ambito la tecnica di multiplexing risulta essere molto inefficiente

Altro motivo di inadeguatezza e’ dato dalla complessita’ da affrontare per aggiungere nuove stazioni alla rete locale se il multiplexing di una configurazione e’ tale

da sfruttare al meglio le risorse del mezzo trasmissivo, un nuovo inserimento comporta la necessita’ di una riconfigurazione complessiva della distribuzione delle slot temporali o delle bande di frequenza

7

Assegnazione dinamica del canale

Per assegnazione dinamica si intende un meccanismo grazie al quale il canale viene assegnato al volo a chi ne ha bisogno, secondo criteri specifici dei protocolli, cercando un modo efficiente di risolvere le contese

L’analisi – sia dal punto di vista logico che quantitativo - di questi protocolli si basa su alcuni presupposti

Modello della stazione: ci sono N stazioni indipendenti, ciascuna con un programma utente che genera frame a frequenza costante; quando il frame e’ generato, la stazione non fa nulla fino a che il frame non e’ stato trasmesso con successo (l’analisi di modelli in cui la stazione puo’ utilizzare il tempo di attesa per eseguire altri programmi, modificandoquindi la frequenza di generazione dei frame in funzione del ritardo in trasmissione risulta enormemente piu’ complessa)

8

Assegnazione dinamica del canale (cont)

Presupposto di canale singolo: esiste un unico canale trasmissivo, attraverso il quale transitano tutte le comunicazioni; non c’e’ modo per una stazione per poter avere informazioni se non attraverso questo canale (non e’ possibile instaurare un meccanismo per richiedere l’allocazione del canale del tipo: “alzo la mano”)

Presupposto della collisione: due frame trasmessi contemporaneamente si sovrappongono, il segnale diventa distorto ed incomprensibile; anche la sovrapposizione di un solo bit provoca il fallimento della trasmissione di entrambi i frame. Questo evento si chiama collisione, ed e’ l’unica causa di errore trasmissivo considerata. Le collisioni, se rilevate, possono essere rilevate da tutte le stazioni connesse al mezzo.

9

Assegnazione dinamica del canale (cont)

Presupposto sull’istante di inizio della trasmissione. Esistono due alternative mutuamente esclusive:

tempo continuo: una stazione puo’ iniziare a trasmettere un frame in qualsiasi istante

tempo suddiviso in slot: le stazioni sono sincronizzate tra loro, ed i frame possono essere inviati solo all’inizio delle slot temporali. In questa situazione una slot puo’ contenere 0, 1 o piu’ frame interi: nel primo caso nessuno trasmette, nel secondo caso la trasmissione ha successo, nel terzo caso si verifica una collisione

Presupporto di rilevamento di occupazione del canale. Anche in questo caso esistono due alternative:

le stazioni, prima di iniziare la trasmissione, sono in grado di capire se qualcuno sta’ gia’ trasmettendo (ad esempio: ethernet)

le stazioni non effettuano la rilevazione di occupazione del canale; solo dopo aver trasmesso possono capire se la trasmissione ha avuto successo (ad esempio: wireless)

10

Protocolli ad accesso multiplo

Aloha puro il protocollo prevede semplicemente che la stazione che

deve trasmettere un frame lo trasmetta immediatamente i frame sono di lunghezza uguale e fissata le trasmissioni potranno sovrapporsi, generando una

collisione; le stazioni sono in grado di verificare l’evento di una collisione ascoltando il canale e verificando se qualcun altro trasmette durante la propria trasmissione

in caso di collisione, la stazione attende un tempo casuale e poi ritrasmette

11

Aloha puro in generale il protocollo avra’ una buona probabilita’ di

riuscita quando il traffico e’ molto basso (poche stazioni, e trasmissioni rarefatte)

in caso di alti carichi, le collisioni cresceranno, e con esse le ritrasmissioni, fino a rendere la trasmissione di fatto impossibile

Il calcolo della capacita’ di trasporto (S) del canale in funzione del numero di tentativi di trasmissione per tempo di frame (G) e’

Il protocollo ha quindi una efficienza massima quando per ogni tempo di frame ci sono G = 0.5 tentativi di trasmissione; in questa condizione l’efficienza di utilizzo del canale e’ pari circa al 18%

GGeS 2

12

Aloha a slot temporali

Slotted aloha questo protocollo migliora il precedente introducendo il

concetto di tempo diviso in slot ciascuna slot contiene esattamente un frame ogni stazione che vuole trasmettere un frame, deve

aspettare la successiva slot temporale per trasmettere in questo modo si riduce il numero di collisioni

nel protocollo aloha puro un frame trasmesso all’istante 0 andra’ in collisione se c’e’ stata un’altra stazione a voler trasmettere un frame nell’intervallo tra [-T, T]

nel protocollo slotted aloha un frame trasmesso andra’ in collisione se c’e’ stata un’altra stazione a voler trasmettere un frame nell’intervallo [-T,0], in quanto le stazioni che desiderano trasmettere un frame dopo l’istante 0 devono aspettare la slot successiva

questo protocollo richiede che le stazioni siano tutte sincronizzate temporalmente

13

Aloha a slot temporali (cont.)

L’efficienza dell’utilizzo del canale con questo protocollo e’ data da

e per G = 1 raggiunge il suo valore massimo (37%) che e’ doppio rispetto ad aloha puro

GGeS

14

Protocolli con rilevamento della portante

Una delle maggiori inefficienze dei protocolli aloha e’ determinato dal fatto che la trasmissione viene fatta senza controllare prima se il canale e’ libero

Vediamo una classe di protocolli che migliora la situazione: protocolli con rilevamento della portante (CSMA: Carrier Sense Multiple Access) in questo contesto il termine portante indica in

generale il livello del segnale presente sul mezzo trasmissivo

il segnale non e’ necessariamente un segnale costituito dalla modulazione di una portante, ma anche, ad esempio, un segnale in banda base

15

CSMA 1-persistente

Il piu’ semplice di questi protocolli ha il seguente funzionamento: quando un calcolatore ha dati da trasmettere,

ascolta il segnale presente sul mezzo trasmissivo se trova il canale libero, trasmette il frame se trova il canale occupato, continua ad ascoltare fino a

che il canale non si libera, e poi trasmette il frame in caso di collisione, la stazione aspetta un

tempo casuale e ripete l’algoritmo Il protocollo si chiama 1-persistente perche’

quando trova il canale occupato, resta in ascolto continuamente, ed appena il canale si libera trasmette con probabilita’ 1 (sempre)

16

CSMA 1-persistente (cont.) Con questo protocollo acquista grande importanza il ritardo

di propagazione del segnale tra due stazioni infatti, quando una stazione inizia a trasmettere, una seconda

stazione potrebbe voler trasmettere, ed ascolta il canale se il segnale trasmesso dalla prima stazione non ha ancora

avuto il tempo di propagarsi fino alla seconda stazione, questa trovera’ il canale libero e trasmettera’, generando una collisione

Maggiore e’ il ritardo di propagazione, piu’ numerose saranno le collisioni dovute alla eventualita’ sopra descritta

questo implica una maggiore inefficienza con l’aumento della lunghezza del canale condiviso

nota: la collisione si presentera’ sempre ed indipendentemente dal ritardo di propagazione qualora due stazioni volessero trasmettere mentre una terza sta’ trasmettendo: alla fine della trasmissione della terza stazione, le due stazioni in attesa si metteranno sempre a trasmettere contemporaneamente

17

CSMA 1-persistente (cont.)

Come slotted aloha, questo protocollo non interferisce con le trasmissioni gia’ in atto

A differenza di slotted aloha, questo protocollo non richiede di dover attendere la time slot successiva, evitando ad esempio di lasciare inutilizzata una slot temporale per il tempo di durata della slot stessa se una stazione desidera trasmettere ed il canale

e’ libero non deve attendere la fine della slot Inoltre CSMA 1-persistente non richiede la

sincronizzazione delle stazioni connesse alla rete

18

CSMA non persistente Si differenzia dal precedente per il fatto che una stazione,

quando vuole trasmettere ma trova il canale occupato, non resta ad ascoltare in continuazione, ma attende un tempo casuale e riprova

Questo meccanismo riduce sensibilmente le collisioni dovute al fatto che due stazioni vogliano trasmettere durante la trasmissione di una terza:

ora le stazioni attenderanno generalmente tempi diversi prima di ritentare

la prima che ritenta trovera’ il canale libero e trasmettera’ la seconda trovera’ nuovamente il canale occupato, quindi non

interferira’ ed aspettera’ ancora Questo protocollo alza notevolmente l’efficienza di utilizzo del

canale con l’aumento del carico, cioe’ delle stazioni connesse alla rete

Il problema principale di questo protocollo e’ che in condizioni di elevato carico il tempo che intercorre tra l’istante in cui la stazione vuole trasmettere e l’istante in cui riesce a trasmettere puo’ crescere indefinitamente

19

CSMA p-persistente In questa ultima versione del protocollo a rilevamento della

portante, il tempo e’ suddiviso in slot temporali come nello slotted aloha

In questo caso, chi desidera trasmettere ascolta il canale continuamente e quando lo trova libero

trasmette con probabilita’ p, oppure attende la slot successiva con probabilita’ (1-p)

alla slot successiva, se libera, trasmette nuovamente con probabilita’ p o aspetta la successiva con probabilita’ 1-p, e cosi’ via

in caso di collisione, o se durante i tentativi di trasmissione qualche altra stazione inizia a trasmettere, la stazione attende un tempo casuale e ripete l’algoritmo

Questo protocollo e’ una via di mezzo tra il protocollo 1-persistente (a cui tende per p che tende ad 1) e quello non persistente

Come nel caso di CSMA non persistente, ad elevato carico e per bassi valori di p cresce l’efficienza di utilizzo della linea ma cresce il ritardo di trasmissione rispetto all’arrivo dei dati dallo strato di rete

Per alti valori di p l’efficienza di utilizzo della linea decresce rapidamente con l’aumentare del carico

20

Confronto tra protocolli CSMA

21

Rilevamento delle collisioni

Un ulteriore miglioramento delle prestazioni si ha con i protocolli CSMA/CD (Carrier Sense, Multiple Access, Collision Detection)

Questi protocolli prevedono che una stazione, rilevata una collisione sul frame che sta’ trasmettendo, interrompa la trasmissione del frame, riducendo in questo modo l’ occupazione del canale con frame comunque invalidi

in caso di collisione, la stazione attendera’ un tempo casuae e ritentera’

Questi protocolli sono alla base di molti protocolli utilizzati sulla LAN, tra cui Ethernet

La caratteristica principale di questi protocolli e’ la durata del tempo in cui il canale e’ conteso tra stazioni pronte a trasmettere

22

Intervallo di contesa

Dopo quanto tempo una stazione e’ certa di avere allocato il canale per la sua trasmissione? Detto T il tempo necessario alla propagazione del segnale tra le due stazioni piu’ lontane, si ha:

se la stazione A trasmette un frame al tempo 0, la stazione B potrebbe iniziare una trasmissione fino al tempo T-ε (con ε piccolo, T- ε e’ l’ultimo istante in cui il canale apparira’ libero a B)

la stazione B si accorgera’ della collisione al tempo T, mentre la stazione A dovra’ aspettare che il segnale trasmesso da B la raggiunga prima di accorgersi della collisione

quindi una stazione potra’ essere certa di avere allocato il canale se non compaiono collisioni per un tempo 2T

ad esempio, su un canale lungo 1 Km si ha 2T = 10μs, che a 10 Mbps corrisponde al tempo di 100 bit

23

Intervallo di contesa (cont.)

La trasmissione con protocolli CSMA/CD consiste in una alternanza tra intervalli di contesa, ciascuno dei quali lunghi 2T, intervalli di trasmissione, in cui una stazione e’ riuscita ad allocare il mezzo trasmissivo, ed intervalli di inattivita’, in cui nessuno vuole trasmettere dati

L’efficienza del canale dipendera’ dalla durata degli intervalli di contesa, che crescera’ con la durata del tempo di propagazione T e crescera’ col numero di trasmissioni tentate per unita’ di tempo

Anche in questo caso l’aumento del carico trasmissivo produce un crollo della efficienza oltre un certo limite, in modo analogo ai protocolli precedenti

24

Codifiche per i protocolli a contesa

In tutti i protocolli fin qui analizzati esiste il presupposto che chi trasmette sia in grado di rilevare una collisione questo richiede che la codifica fornisca un metodo

per identificare una sovrapposizione di trasmissioni ad esempio codifiche che assegnano una tensione

di 0 volt al simbolo 0 non sempre sono in grado di identificare la collisione: due sequenze 01010101… e 10101010… contemporanee potrebbero non essere rilevate come collisione, ma come sequenza 111111…

i protocolli a contesa su cavo utilizzano normalmente la codifica Manchester, che accomuna a questa caratteristica la trasmissione implicita delle informazioni di sincronismo

25

Caratteristiche dei protocolli a contesa

Date le caratteristiche dei protocolli e’ evidente che il tipo di trasmissione a livello due non potra’ essere altro che half-duplex, in quanto non possono coesistere due trasmissioni contemporanee sul mezzo trasmissivo

Si puo’ anche osservare come i protocolli fin qui visti non saranno in grado di offrire servizi affidabili

evitare la collisione di per se non garantisce che il frame arrivi integro

in linea di principio si potrebbe utilizzare una tecnica di riscontro, ma questi protocolli hanno una efficienza che crolla in funzione del numero di frame trasmessi nell’unita’ di tempo

per le comunicazioni su cavo, l’elevata affidabilita’ del mezzo fisico (dovuta alle brevi distanze) rende piu’ efficiente demandare il controllo ai livelli superiori piuttosto che appesantire il carico con frame di acknowledge

26

Protocolli senza collisione

Sono stati sviluppati protocolli per regolare l’accesso al mezzo che non comportano collisioni

Vedremo due esempi: protocollo a prenotazione

per protocollo a prenotazione si indica un protocollo per cui una stazione annuncia a tutti il suo desiderio di comunicare, prima di iniziare la trasmissione vera e propria

poiche’ tutti vengono a conoscenza a priori che la stazione deve trasmettere, nessuno interferisce con la trasmissione

protocollo a turno (round robin) in questo caso ad ogni stazione e’ data a turno la possibilita’

di trasmettere al proprio turno, una stazione trasmette i frame disponibili,

generalmente per un periodo di tempo massimo predeterminato, quindi il turno passa alla stazione successiva

il controllo della sequenza puo’ essere centralizzato (una stazione master che fa un polling delle altre stazioni) o distribuito (tramite lo scambio di un gettone), in entrambi i casi seguendo un ordine sequenziale predeterminato

27

Protocollo a prenotazione Un esempio di protocollo a prenotazione e’ il protocollo a mappa di bit

elementare: sulla rete ci sono N stazioni, numerate da 0 a N-1 alla fine della trasmissione di un frame inizia un periodo di prenotazione, in

cui ogni stazione, andando per ordine di indirizzo, trasmette un bit che vale 1 se la stazione deve trasmettere, 0 altrimenti

al termine del periodo di prenotazione (privo di collisioni in quanto ogni stazione aspetta il suo turno) tutti hanno appreso quali stazioni devono trasmettere, e le trasmissioni procedono un frame alla volta sempre andando per ordine

se una stazione riceve dati da trasmettere quando la fase di prenotazione e’ terminata, deve attendere il successivo periodo di prenotazione per annunciare la volonta’ di trasmettere

L’efficienza di questo protocollo e’ bassa per grandi valori di N e basso carico trasmissivo; in queste condizioni una stazione deve attendere tutti gli N bit delle altre stazioni (delle quali la maggior parte o la totalita’ non desidera trasmettere) prima di poter trasmettere

In condizioni di carico elevato l’overhead dovuto agli N bit di prenotazione si distribuisce sui ~N frame da trasmettere, riducendo l’inefficienza complessiva del protocollo

Questo meccanismo definisce un ritardo massimo sulla trasmissione

28

Protocollo round robin: token ring

Token ring (standard IEEE 802.5) questo protocollo prevede l’utilizzo di una topologia ad anello sull’anello circola un piccolo frame, detto token (gettone) che le

stazioni ricevono da una parte e ritrasmettono dall’altra in continuazione

una stazione e’ autorizzata a trasmettere dati solo quando e’ in possesso del token

la stazione riceve il token, lo trattiene ed inizia a trasmettere dati terminata la trasmissione, ritrasmette il token in coda ai frame di

dati esistono specifiche a 4 e 16 Mbps

Esiste una versione modificata del token ring standardizzata per trasmissione su doppio anello in fibra ottica, detto FDDI (Fiber Distributed Data Interface) a 100 Mbps

L’IEEE ha sviluppato uno standard molto simile, dedicato alle topologie a bus (token bus: IEEE 802.4)

in questo protocollo il problema aggiuntivo e’ determinato dalla necessita’ di configurare un ordine sequenziale delle stazioni, che viene fatto in una fase di inizializzazione del protocollo

29

Protocollo round robin: token ring

Il protocollo token ring (come tutti quelli a turno) e’ poco efficiente in condizioni di basso carico

la stazione che deve trasmettere deve attendere di ricevere il token (o in generale deve attendere il suo turno) prima di poterlo fare, anche se il canale non e’ occupato

In condizioni di carico elevato, quando tutti vogliono trasmettere, l’efficienza del protocollo sfiora il 100%

il solo overhead e’ dovuto alla necessita’ che ha una stazione di identificare il token prima di poter trasmettere

in questi protocolli il token e’ scelto in modo opportuno per minimizzare l’overhead

Una importante caratteristica di questo genere di protocolli e’ la possibilita’ di valutare un tempo massimo di ritardo per le trasmissioni

una stazione che desidera trasmettere dovra’ attendere al piu’ N tempi di trasmissione (uno per stazione, nel caso tutti debbano trasmettere) prima che tocchi nuovamente ad essa

questo permette l’utilizzo del protocollo in situazioni in cui i tempi di risposta possono essere determinanti (ad esempio una catena di montaggio)