Multiple Access Protocols

Protocolli ad accesso multiplo
Crediti
Parte delle slide seguenti sono adattate dalla
versione originale di J.F Kurose and K.W. Ross
(© 1996-2003 All Rights Reserved)
5-1
Protocolli ad accesso multiplo
 Utilizzati (a livello MAC) quando si ha un singolo canale
broadcast condiviso
 Due o più trasmissioni simultanee dai nodi: interferenza

solo un nodo può trasmettere con successo ad ogni istante
multiple access protocol
 algoritmo distribuito che determina come i nodi
condividono il canale, cioè determina quando un nodo
può trasmettere
 la comunicazione per la condivisione del canale deve
utilizzare il canale stesso!
5-2
Protocolli ad accesso multiplo: Tassonomia
Tre classi principali:
 Channel Partitioning



divide il canale in “parti” (time slot, frequency, code)
TDMA, FDMA, CDMA
alloca le parti al nodo per un uso esclusivo
 Random Access
 canale non è diviso, permette collisioni
 “recupera” dalle collisioni
 “Taking turns”
 coordina l’accesso al mezzo condiviso in modo preciso per
evitare le collisioni
Obiettivo: protocollo efficiente, equo, semplice e
decentralizzato
5-3
Protocolli ad accesso casuale
 Quando un nodo ha un pacchetto da inviare
 trasmette alla velocità massima del canale R
 nessuna coordinazione a priori tra i nodi
 due o più nodi trasmettono contemporaneamente ->
“collisione”
 Random access MAC protocol specifica:


come scoprire una collisione
come recuperare dalle collisioni (es. via ritrasmissioni
ritardate)
 Esempi di random access MAC protocols:
 slotted ALOHA
 ALOHA
 CSMA e CSMA/CD
5-4
Slotted Aloha
 tempo diviso in slot di dimensione uguale (= frame
transmission time= L/R); nodi sincronizzati
 quando arriva una nuova frame al nodo: trasmette
all’inizio dello slot successivo
 se avviene collisione: ritrasmetti frame negli slot
futuri con probabilità p, finchè si ha successo
Success (S), Collision (C), Empty (E) slots
5-5
Slotted Aloha: Efficienza
Q: Quale è la frazione massima di slot con
successo?
R: Ipotesi: N stazioni hanno pacchetti da inviare
 ognuna trasmette in uno slot con probabilità p
 probabilità di trasmissione con successo S è:
per singolo nodo:
S= p (1-p)N-1
per gli N nodi
S = N p (1-p)N-1
Al più: canale utilizzato
per trasmissioni
utili 37% del tempo!
… scegliendo l’ottimo p con N -> ∞ ...
= 1/e = 0.37
5-6
ALOHA puro (unslotted)
 Unslotted Aloha: più semplice, nessuna sincronizzazione
 quando frame necessita trasmissione:
 invia senza aspettare inizio dello slot
 unità di tempo = frame transmission time
 probabilità di collisione cresce:
 frame inviata a t0 collide con altre frame inviate a [t0-1, t0+1]
5-7
ALOHA puro (cont.)
P(successo per un nodo) = P(nodo trasmette) .
P(nessun altro nodo trasmette in [t0-1,t0] .
P(nessun altro nodo trasmette in [t0,t0+1]
= p . (1-p)N-1 . (1-p)N-1
P(successo per ognuno degli N nodi) = N p . (1-p)N-1 . (1-p)N-1
… scegliendo l’ottimo p per N -> ∞...
= 1/(2e) = 0.18
protocollo restringe il
trhoughput effettivo
del canale
5-8
CSMA (Carrier Sense Multiple Access)
CSMA: ascolta (rilevazione di portante) prima di
trasmettere:
 Se il canale è “silenzioso”: trasmetti l’intera
frame
 Se il canale è “occupato”: rinvia la trasmissione
Persistent CSMA: riprova immediatamente con
probabilità p (può causare instabilità)
 Non-persistent CSMA: riprova dopo un intervallo
casuale

 Analogia umana: non interrompere gli altri!
5-9
CSMA: Collisioni
spatial layout of nodes
possono verificarsi
collisioni:
ritardo di propagazione
comporta che due nodi
possono non accorgersi della
trasmissione dell’altro
collisione:
intero tempo di trasmissione
di frame sciupato
nota:
distanza e ritardo di propagazione
determinanti per la probabilità di
collisione
5-10
CSMA/CD (Collision Detection)
CSMA/CD: rilevazione portante, rinvio come in
CSMA
collisioni scoperte in un breve intervallo
 trasmissioni in collisione abortite, riduce spreco di
canale

 Collision detection:
 facile nelle wired LAN: misura intensità del
segnale, paragona segnale trasmesso e ricevuto
 difficile nelle wireless LAN: receiver può non
percepire la collisione
 Analogia umana: conversare con educazione!
5-11
CSMA/CD (Collision Detection)
5-12
Protocolli MAC “a turni” (taking turns)
Channel partitioning MAC protocols:
 suddividono il canale efficientemente ed
equamente per alti carichi
 inefficienti per i bassi carichi: ritardo
nell’accesso al canale, 1/N banda allocata anche se
un solo nodo attivo!
Random access MAC protocols
 efficiente per i bassi carichi: singolo nodo può
utilizzare pienamente il canale
 carichi alti: collision overhead
“Taking turns” protocols
 cercano di utilizzare le parti migliori delle due
precedenti tecnologie!
5-13
“Taking Turns” MAC protocols
Polling:
 master node “invita”
i nodi slave a
trasmettere a turno
(numero max di
frame)
 problemi:



polling overhead
minore sfruttamento
del canale
singolo punto di
rottura (master)
Token passing:
 token di controllo passato da
un nodo al successivo
sequenzialmente
 chi ha il token può trasmettere
 problemi:



token overhead
minore sfruttamento del canale
singolo punto di rottura (token)
5-14
Riassunto dei protocolli MAC
 Cosa fare con un media condiviso?
 Channel Partitioning, a divisione di tempo,
frequenza o codice
• TDMA, FDMA, CDMA

Random partitioning (dinamico)
• ALOHA, S-ALOHA, CSMA, CSMA/CD
• collision detection: facile con alcune tecnologie (wire),
difficile con altre (wireless)
• CSMA/CD usata in Ethernet (IEEE 802.3)

Taking Turns
• polling da una stazione centrale, token passing
• Token Ring (IEEE 802.5), FDDI
Protocolli ad accesso multiplo usati ampiamente nelle LAN
5-15
Tecnologie LAN
Differenti componenti:
Protocolli MAC: Ethernet, Token Ring, FDDI
 Indirizzamento
 Hub, bridge, switch
 Wireless LAN

5-16
IEEE 802
5-17