Esercizio - Scelta del protocollo MAC su bus di 5 km

Testo. Più stazioni trasmettono pacchetti DLL di $100$ byte su un bus condiviso lungo $5$ km. Il bitrate al livello fisico è $100$ Mbit/s. Determinare il protocollo MAC più efficiente da implementare a livello DLL.

Teoria usata: Protocolli di accesso multiplo - ALOHA e CSMAQuando più stazioni condividono lo stesso mezzo serve un protocollo di accesso (MAC) che decida chi trasmette. Accesso casuale: ALOHA puro (si trasmette subito, tempo vulnerabile $2t_F$), slotted ALOHA (si parte solo a inizio slot, vulnerabile $t_F$), CSMA (si ascolta prima di parlare, vulnerabile $\tau_p$) con le varianti 1-persistent, non persistent e p-persistent, CSMA/CD (rileva la collisione mentre trasmette: serve $t_F\ge2\tau_p$, quindi un frame minimo) e CSMA/CA del Wi-Fi (IFS, finestra di contesa con backoff esponenziale, ACK, RTS/CTS e NAV). Accesso controllato: prenotazione, polling, token. Canalizzazione: FDMA, TDMA, OFDMA, CDMA, SDMA.Protocolli di accesso multiplo - ALOHA e CSMA →, LAN - Ethernet e Wi-FiUna LAN copre un'area limitata ed è definita dalla famiglia IEEE 802.x (802.3 Ethernet, 802.11 Wi-Fi), che divide il livello di collegamento in LLC e MAC. Ethernet è senza connessione, senza controllo di flusso e senza ACK; usa CSMA/CD 1-persistent; il frame va da 64 a 1518 byte (indirizzi di 6 byte, tipo/lunghezza, dati 46-1500, CRC di 4) e il minimo di 64 B deriva da $t_F\ge2\tau_p$. Dal 10 Mbit/s a coassiale fino al 10 Gbit/s su fibra, con switch full-duplex che eliminano le collisioni. Il Wi-Fi (802.11) usa CSMA/CA, ha i modi BSS (con access point) e ad hoc, EBSS con sistema di distribuzione; adatta il bitrate all'SNR; ha problemi del terminale nascosto e del terminale esposto, risolti in parte da RTS/CTS e NAV.LAN - Ethernet e Wi-Fi →, Analisi delle prestazioni di reteLe prestazioni di una rete si misurano con tre famiglie di metriche: traffico (bitrate $R_0$ massimo del collegamento, throughput $S\le R_0$ dati consegnati con successo, goodput al livello applicazione), ritardo (end-to-end $d_{tot}=d_{proc}+d_{queue}+d_{trans}+d_{prop}$ con $d_{trans}=L/R$ e $d_{prop}=d/v$; jitter; RTT) e capacità del tubo (BDP $=R\cdot$ ritardo, bit che riempiono il collegamento), più l'affidabilità (PER, PDR, PLR). Il throughput di un percorso è quello del collegamento collo di bottiglia, $\min$ dei bitrate, ricordando che i collegamenti condivisi dividono la capacità.Analisi delle prestazioni di rete →; le formule di throughput sono in Prestazioni dei protocolli di accesso - ALOHA, CSMA, TDMA e FDMACon arrivi di Poisson, la probabilità di successo di un frame è la probabilità che nessun altro frame arrivi nel tempo vulnerabile: ALOHA puro $P_S=e^{-2G}$, throughput $S=Ge^{-2G}$ con massimo $1/(2e)\approx0{,}18$ in $G=1/2$; slotted ALOHA $S=Ge^{-G}$ con massimo $1/e\approx0{,}37$ in $G=1$. CSMA non persistente con $a=\tau_p/t_F$: $S=\frac{Ge^{-aG}}{G(1+2a)+e^{-aG}}$, che tende a 1 per $a\to0$ ma crolla per $a$ grande, dove lo slotted ALOHA è migliore. Per TDMA ($M/D/1$) $E[T]=t_F\left(\frac{N_u}2+\frac{SN_u}{2(1-S)}+1+a\right)$ e per FDMA $E[T]=t_F\left(N_u+\frac{SN_u}{2(1-S)}+a\right)$: FDMA è più lento di $t_F(N_u/2-1)$.Prestazioni dei protocolli di accesso - ALOHA, CSMA, TDMA e FDMA →.

Come si confrontano i protocolli ad accesso casuale

L'efficienza di un protocollo ad accesso casuale dipende dal suo tempo di vulnerabilità: la finestra in cui un pacchetto già iniziato può essere distrutto da un altro. Più è corta, meno collisioni ci sono.

Il confronto fra CSMA e ALOHA si fa tramite il ritardo di propagazione normalizzato $$\tau=\frac{T_p}{T_{fr}}.$$ Il CSMA batte l'ALOHA solo se $\tau$ è piccolo ($T_p\ll T_{fr}$): in quel caso ascoltare il canale prima di parlare evita quasi tutte le collisioni. Se $\tau$ è grande l'ascolto è inutile, perché quando una stazione sente il canale libero il segnale di un'altra non l'ha ancora raggiunta.

Calcolo dei tempi

Tempo di trasmissione di un pacchetto. $L=100\ \text{byte}=800\ \text{bit}$: $$T_{fr}=\frac{L}{R}=\frac{800}{100\cdot10^6}=8\ \mu\text{s}.$$

Tempo di propagazione. Il testo non dà la velocità del segnale. Si usa la stessa dell'esercizio precedente sul bus ($5$ ns/m, cioè $2\cdot10^8$ m/s, la velocità tipica di un cavo): i due modi di scriverla coincidono. $$T_p=5000\ \text{m}\cdot5\ \text{ns/m}=25\ \mu\text{s}=\frac{5000}{2\cdot10^8}\ \text{s}.$$

Ritardo normalizzato. $$\tau=\frac{T_p}{T_{fr}}=\frac{25\ \mu\text{s}}{8\ \mu\text{s}}=3{,}125.$$ Le due grandezze hanno la stessa unità e il rapporto è un numero puro: $\tau>1$ significa che il segnale impiega più tempo ad attraversare il bus di quanto ne serva a trasmettere un intero pacchetto.

Confronto

• CSMA/CD richiede $T_{fr}\ge2T_p=50\ \mu\text{s}$, ma $T_{fr}=8\ \mu\text{s}$: le collisioni non verrebbero rilevate (stessa condizione dell'esercizio precedente, bitrate massimo $800/50\ \mu\text{s}=16$ Mbit/s). Va scartato, oppure servirebbero pacchetti di almeno $100\cdot10^6\cdot50\cdot10^{-6}=5000$ bit.
• CSMA ha vulnerabilità $T_p=25\ \mu\text{s}=3{,}1\,T_{fr}$: più lunga di quella dell'ALOHA puro ($2T_{fr}=16\ \mu\text{s}$) e di quella dell'ALOHA slotted ($8\ \mu\text{s}$). Con $\tau>1$ il suo throughput, già per $\tau=1$, ha un picco intorno a $0{,}14$ (grafico del confronto CSMA/ALOHA), cioè sotto i $0{,}18$ dell'ALOHA puro e molto sotto i $0{,}37$ dello slotted; a $\tau=3{,}125$ è ancora peggio. Si calcola con la formula del CSMA non persistente, $S=\dfrac{Ge^{-aG}}{G(1+2a)+e^{-aG}}$ con $a=\tau=3{,}125$: il massimo, trovato numericamente, è $S_{max}\approx0{,}055$ (in $G\approx0{,}16$), meno di un terzo dell'ALOHA puro.

• ALOHA puro: vulnerabilità $16\ \mu\text{s}$, $S_{max}\approx0{,}18$.
• ALOHA slotted: vulnerabilità $8\ \mu\text{s}$ (la più corta), $S_{max}\approx0{,}37$.

Il protocollo più efficiente è quindi lo slotted ALOHA: ha il tempo di vulnerabilità più breve e il doppio del throughput massimo dell'ALOHA puro. (Nella pratica servirebbe sincronizzare le stazioni sugli slot, difficile con $25\ \mu$s di propagazione, ma l'esercizio chiede il confronto tra protocolli sull'efficienza.)

Confronto con la soluzione ufficiale

Ufficiale: "Slotted-ALOHA è il protocollo MAC più efficiente perché ha il tempo/finestra di vulnerabilità più breve". Coincide. Il testo ufficiale non cita CSMA, ma la scelta si giustifica come sopra, con $\tau=3{,}125$.

Errori comuni

• Scegliere CSMA/CD "perché è il migliore": vale solo se $\tau\ll1$ e $T_{fr}\ge2T_p$; qui $T_p$ è più di tre volte $T_{fr}$.
• Usare $T_{fr}=8$ ms (errore di conversione: $800\ \text{bit}/10^8\ \text{bit/s}=8\ \mu$s).
• Confrontare solo $T_{fr}$ e dimenticare $T_p$: a $100$ Mbit/s su $5$ km la propagazione domina la trasmissione.
• Dimenticare che il tempo di vulnerabilità dello slotted è $T_{fr}$ e quello del puro $2T_{fr}$.

(Verificato con Python: $T_{fr}=8\ \mu$s, $T_p=25\ \mu$s, $\tau=3{,}125$, $2T_p=50\ \mu$s, bitrate massimo per CSMA/CD $16$ Mbit/s.)