Lezione 06 - Accesso al canale, code e prestazioni

Date: giovedì 6 marzo 2025 (accesso al canale parte 2, teoria delle code) e martedì 11 marzo 2025 (prestazioni dei protocolli di accesso) · Fonte: slide del corso Internet, UniPD (L05, L06a, L06b)

Argomenti trattati

6 marzo.

1. Accesso al canale, parte 2: CSMA/CD (rilevazione di collisione, durata minima della trasmissione, dimensione minima del frame); CSMA/CA (IFS, finestra di contesa, backoff, ACK, RTS/CTS e NAV); riepilogo con i tempi vulnerabili; accesso controllato (prenotazione, polling, passaggio del testimone); canalizzazione (FDMA, TDMA, OFDMA, CDMA, SDMA).
2. Introduzione alla teoria delle code: processo di arrivo di Poisson e di servizio, struttura della coda, notazione di Kendall, misure di occupazione e di tempo, traffico offerto, utile e fattore di carico, stabilità, legge di Little, code M/M/1 e M/G/1.

11 marzo.

3. Prestazioni dei protocolli di accesso: ALOHA puro e slotted ALOHA (probabilità di successo, throughput, ritardo, instabilità); CSMA non persistente (periodi di inattività e di occupazione, throughput, ritardo) e confronto con lo slotted ALOHA; TDMA come coda M/D/1 e FDMA come coda M/G/1 (throughput e ritardo).

Teoria

• 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 → — CSMA/CD, CSMA/CA, accesso controllato, canalizzazione
• Introduzione alla teoria delle codeUn sistema a coda (QS) è fatto da un processo di arrivi (di Poisson, tasso $\lambda$), una coda e uno o più servitori con tasso di servizio $\mu$. Carico offerto $G=\lambda/\mu$, fattore di carico $\rho=\lambda/(m\mu)$: il sistema è stabile solo se $\rho<1$, e allora il throughput è $\lambda$ (altrimenti è $m\mu$). Legge di Little: $E[x]=\lambda E[s]$, valida per qualsiasi disciplina. Coda M/M/1: $E[x]=\frac{\rho}{1-\rho}$, $E[s]=\frac{1/\mu}{1-\rho}$, $E[w]=\frac{\rho/\mu}{1-\rho}$. Con servizio deterministico (M/D/1, caso particolare di Pollaczek-Khinchin): $E[w]=\frac{\rho}{2\mu(1-\rho)}$. Il ritardo cresce senza limite quando $\rho\to1$.Introduzione alla teoria delle code → — Poisson, stabilità, Little, M/M/1, M/G/1
• 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 → — formule di throughput e ritardo, grafici

Esercizi collegati

• Esercizio - Bitrate oltre il quale CSMA-CD non rileva le collisioni
• Esercizio - Scelta del protocollo MAC su bus di 5 km
• Esercizio - Collisione tra due stazioni CSMA 1-persistente

Lezione precedente: Lezione 5 · Selective Repeat e accesso al canale · Lezione successiva: Lezione 7 · ARP, framing ed Ethernet