Sistemi e Tecnologie della
Comunicazione
Lezione 14: data link layer: sottostrato MAC (definizione, protocolli di assegnazione del canale)
1
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, …
2
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
3
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)
4
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
5
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
6
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)
7
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.
8
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)
9
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
10
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’
S  Ge

2 G
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%
11
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
12
Aloha a slot temporali (cont.)

L’efficienza dell’utilizzo del canale con questo protocollo e’
data da
S  Ge
G
e per G = 1 raggiunge il suo valore massimo (37%) che
e’ doppio rispetto ad aloha puro
13
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
14
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)
15
CSMA 1-persistente (cont.)

Con questo protocollo acquista grande importanza il ritardo di
propagazione del segnale tra due stazioni



Maggiore e’ il ritardo di propagazione, piu’ numerose saranno le
collisioni dovute alla eventualita’ sopra descritta


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
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
16
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
17
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
18
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
19
Confronto tra protocolli CSMA
20
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
21
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
22
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
23
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
24
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
25
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
26
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
27
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
28
Protocollo round robin: token ring

Il protocollo token ring (come tutti quelli a turno) e’ poco efficiente in
condizioni di basso carico


In condizioni di carico elevato, quando tutti vogliono trasmettere,
l’efficienza del protocollo sfiora il 100%



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
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)
29