Esercizio - Collisione tra due stazioni CSMA 1-persistente

Testo. Le stazioni A e B usano a livello DLL il protocollo CSMA 1-persistente. Il collegamento punto-punto tra le due stazioni ha bitrate $R=2{,}5$ Mbit/s e tempo di propagazione $t_P=2$ ms. I pacchetti DLL sono lunghi $30$ kbit. La stazione A genera due pacchetti agli istanti $t_{A,1}=230$ ms e $t_{A,2}=245$ ms; la stazione B ne genera uno all'istante $t_{B,1}=233$ ms.

1. Ci sono collisioni tra pacchetti?
2. A quali istanti A e B rilevano le collisioni (se ci sono)?

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 → (tempo vulnerabile $\tau_p$ del 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 →, 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 →.

Regole del modello

Per rispondere bisogna fissare con precisione il comportamento delle stazioni.

• CSMA 1-persistente: quando una stazione ha un pacchetto ascolta il canale. Se lo trova libero trasmette subito; se lo trova occupato continua ad ascoltarlo e trasmette nell'istante in cui lo sente tornare libero (con probabilità 1, da cui "1-persistente").
• Il canale è "visto" con ritardo: una stazione sente il canale occupato solo quando il primo bit dell'altra la raggiunge, cioè $t_P$ dopo l'inizio della trasmissione; lo sente tornare libero quando l'ultimo bit la raggiunge, $t_P$ dopo la fine. Questo è il motivo per cui il CSMA può avere collisioni.
• Rilevazione della collisione: una stazione che sta trasmettendo si accorge della collisione quando il primo bit dell'altra frame la raggiunge, e a quel punto smette. Questo comportamento è quello del CSMA/CD, che si assume per rispondere alla domanda 2 (il testo chiede l'istante di rilevazione).

Tempo di trasmissione

$$T_{fr}=\frac{L}{R}=\frac{30\,000\ \text{bit}}{2{,}5\cdot10^6\ \text{bit/s}}=12\ \text{ms}.$$

Cronologia degli eventi

Senza collisione i due pacchetti sarebbero finiti alle $257$ (A) e alle $256$ (B), ma le trasmissioni vengono interrotte alle $246$ (A) e alle $247$ (B).

Il diagramma spazio-tempo (posizione sull'asse x, con A in $0$ e B in $1$; tempo in ms sull'asse y, verso l'alto) mostra perché: le diagonali sono i segnali che si propagano, e ci mettono $t_P=2$ ms ad andare da A a B.

Risposte

1. Sì, c'è una collisione, tra il pacchetto 2 di A e il pacchetto di B. Il pacchetto 1 di A arriva integro (B lo ha aspettato). La collisione avviene perché A ha generato il pacchetto 2 a $245$ ms, solo $1$ ms dopo che B aveva iniziato a trasmettere, quando il segnale di B non aveva ancora percorso il collegamento ($t_P=2$ ms): il vulnerable time del CSMA è $t_P$ e qui $245-244=1\ \text{ms}<2$ ms.
2. A rileva la collisione a $t=246$ ms, B a $t=247$ ms. Ognuno la rileva quando riceve il primo bit dell'altra frame.

Confronto con la soluzione ufficiale

Ufficiale: "c'è collisione, rilevata a $t=246$ ms"; la figura di corredo riporta gli istanti $230, 232, 242, 244, 245, 246, 247$, cioè esattamente quelli della tabella sopra (rilevazione di A a $246$, di B a $247$). Coincide: il testo ufficiale cita solo la prima rilevazione (quella di A), la figura anche la seconda.

Errori comuni

• Credere che B trasmetta a $233$ ms: in quell'istante sente il canale occupato (il primo bit di A è arrivato a $232$) e deve aspettare.
• Dimenticare che B sente il canale libero a $244$ ms (fine di A più $t_P$) e non a $242$ ms: con $242$ si ottiene una cronologia sbagliata.
• Pensare che A abbia trasmesso a $245$ ms "sapendo" che B stava trasmettendo: il segnale di B arriva ad A solo a $246$ ms, quindi A ha sentito il canale libero.
• Scambiare le due rilevazioni: A rileva a $246$ ms (primo bit di B), B a $247$ ms (primo bit di A).

(Verificato con Python: $T_{fr}=12$ ms; B parte a $230+12+2=244$; A rileva a $244+2=246$; B rileva a $245+2=247$.)