Esercizio - Bitrate oltre il quale CSMA-CD non rileva le collisioni

Testo. Più stazioni condividono lo stesso bus lungo $1$ km e implementano il protocollo CSMA/CD a livello DLL. Sapendo che il tempo di propagazione sul bus è $5$ ns/m e che le stazioni trasmettono pacchetti di $100$ byte, determinare il valore (o i valori) di bitrate al livello fisico per cui le collisioni di accesso non possono essere rilevate.

Teoria usata: 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 →, 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 →, 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 → (ritardi di trasmissione e di propagazione).

Cosa deve succedere perché CSMA/CD funzioni

Nel CSMA/CD la stazione ascolta il canale mentre trasmette e, se rileva energia anomala, interrompe la trasmissione. Perché possa accorgersi di una collisione deve essere ancora in trasmissione quando la notizia della collisione le arriva. Nel caso peggiore le due stazioni sono agli estremi opposti del bus:

• il segnale della prima impiega $T_p$ per arrivare alla seconda;
• la seconda, che nel frattempo (un attimo prima dell'arrivo) ha cominciato a trasmettere, causa subito la collisione, e l'effetto impiega altri $T_p$ per tornare alla prima.

La prima stazione deve quindi trasmettere per almeno $2T_p$ prima di finire l'ultimo bit: $$T_{fr}\ge2T_p,\qquad T_{fr}=\frac{L}{R}.$$ Se invece $T_{fr}<2T_p$ la stazione ha già finito di trasmettere quando arriva l'eco della collisione, crede che il pacchetto sia andato bene e non lo ritrasmette: la collisione non viene rilevata.

Calcolo

Tempo di propagazione sul bus. $T_p=1000\ \text{m}\cdot5\ \text{ns/m}=5000\ \text{ns}=5\ \mu\text{s}$, quindi $2T_p=10\ \mu\text{s}$. (I $5$ ns/m equivalgono a una velocità del segnale $v=1/(5\cdot10^{-9})=2\cdot10^{8}$ m/s, quella tipica in un cavo: Mezzi di trasmissione - cavi, fibre e collegamenti radioIl mezzo di trasmissione fissa l'attenuazione $a_{ch}$ nel link budget. Nei cavi $H_{ch}=e^{-\gamma d}$ e l'attenuazione in dB cresce con la distanza ($a=\tilde a,d$, dB/km) e con $\sqrt f$. Le fibre ottiche hanno banda larghissima (10¹⁴-10¹⁵ Hz), attenuazione bassa in tre finestre di lunghezza d'onda e limitazione dalla dispersione. Nei collegamenti radio vale la formula di Friis, $g_{ch}=g_{tx}g_{rx}\left(\frac\lambda{4\pi d}\right)^2$, cioè $a_{ch}=32{,}4+20\log_{10}d_{km}+20\log_{10}f_{MHz}-G_{tx}-G_{rx}$ dB.Mezzi di trasmissione - cavi, fibre e collegamenti radio →.)

Lunghezza del pacchetto. $L=100\ \text{byte}=800\ \text{bit}$.

Condizione di rilevabilità. $$\frac{L}{R}\ge2T_p\ \Longrightarrow\ R\le\frac{L}{2T_p}=\frac{800\ \text{bit}}{10\ \mu\text{s}}=80\ \text{Mbit/s}.$$ Passaggio: si moltiplica entrambi i membri per $R>0$ (il verso non cambia) ottenendo $L\ge2T_pR$, poi si divide per $2T_p>0$. L'unità: $800\ \text{bit}/10\ \mu\text{s}=800/(10\cdot10^{-6})=8\cdot10^{7}$ bit/s.

Conclusione. Le collisioni sono rilevabili solo per $R\le80$ Mbit/s. Quindi non sono rilevabili per ogni $R>80$ Mbit/s (per esempio a $100$ Mbit/s: $T_{fr}=8\ \mu\text{s}<10\ \mu\text{s}$).

Si noti che aumentare il bitrate accorcia $T_{fr}$ ma non cambia $T_p$ (dipende solo dalla lunghezza del bus e dalla velocità del segnale): per questo Ethernet a velocità maggiori deve ridurre la lunghezza massima del cavo o aumentare la lunghezza minima del pacchetto.

Confronto con la soluzione ufficiale

Ufficiale: le collisioni non possono essere rilevate se il bitrate è maggiore di $80$ Mbit/s. Coincide. (Al valore limite esatto $R=80$ Mbit/s si ha $T_{fr}=2T_p$ e la collisione è ancora rilevabile.)

Errori comuni

• Usare $T_{fr}\ge T_p$ invece di $T_{fr}\ge2T_p$: si troverebbe $160$ Mbit/s. Serve l'andata e il ritorno del segnale.
• Dimenticare di convertire i byte in bit ($100$ byte $=800$ bit, non $100$).
• Rispondere "$R<80$ Mbit/s": è la condizione in cui le collisioni sono rilevabili, quella chiesta è la sua negazione.
• Convertire male i $5$ ns/m: $1$ km $=1000$ m dà $5\ \mu$s, non $5$ ms.

(Verificato con Python: $T_p=5\ \mu\text{s}$, $R_{lim}=800/(2\cdot5\cdot10^{-6})=80$ Mbit/s.)