Esercizio - Pacchetti su BSC, stabilità e traffico offerto

Questa pagina non ha ancora la versione ripasso: qui sotto c'è il testo completo.

Testo (esempio numerico degli appunti di Bressanone, esteso). Un collegamento a $R_b=1$ Mbit/s trasmette pacchetti di $L=10\,000$ bit su un BSC senza memoria con $P_{bit}=10^{-5}$. I pacchetti arrivano secondo un processo di Poisson con $\lambda=50$ pkt/s. a. Probabilità che un pacchetto sia errato e distribuzione del numero di bit errati. b. Il sistema è stabile? Quali sono fattore di carico, traffico offerto e throughput se non ci sono errori? c. Con gli errori e un ARQ Selective Repeat: numero medio di trasmissioni, condizione di stabilità, traffico offerto effettivo. d. Cosa cambia se $\lambda=95$ pkt/s?

Teoria usata: Livello di collegamento - LLC, MAC e ipotesi di lavoroIl livello di collegamento vede un canale fisico con errori residui e deve offrire ai livelli superiori un canale affidabile; ha due sottolivelli: LLC (correzione residua, ARQ con ACK/NACK) e MAC (chi trasmette, perché con più trasmettitori il rapporto giusto è la SINR e non l'SNR e la capacità cala). Per analizzarlo si usano ipotesi standard: pacchetti di $L$ bit, probabilità $p$ di pacchetto errato (i.i.d., $p=1-(1-P_{bit})^L\simeq LP_{bit}$), coda sempre piena (heavy traffic), tempo di pacchetto $t_P=L/R_b$, $t_{RTT}=t_P+t_A+2\tau_P$, timeout stringente, ACK/NACK senza errori, ritrasmissioni illimitate ($E[#tx]=1/(1-p)$). Le metriche sono throughput (frazione di tempo d'aria) e ritardo (fino alla ricezione corretta). Una collisione è la sovrapposizione, anche minima, di due pacchetti.Livello di collegamento - LLC, MAC e ipotesi di lavoro →, Tecniche ARQ e loro prestazioniARQ (Automatic Repeat reQuest) rende affidabile un collegamento che sbaglia: il ricevitore risponde a ogni pacchetto con ACK (corretto) o NACK (errato), e il trasmettitore ritrasmette. Con probabilità di pacchetto errato $p$, $t_{RTT}=t_P+t_A+2\tau_P$ e coda sempre piena, il throughput massimo (frazione di tempo d'aria) è: Stop-and-Wait $S=\frac{t_P(1-p)}{t_{RTT}}$; Go-Back-N con $N=t_{RTT}/t_P$ $S=\frac{1-p}{(N-1)p+1}$; Selective Repeat $S=1-p$. Il ritardo medio è $m_{delay}=t_P+\tau_P+\frac p{1-p}t_{RTT}$ (a coda vuota). Sono solo valori massimi: la coda ARQ è stabile solo se $\lambda$ è minore della velocità di servizio, $\lambda<1/m_y$; altrimenti il throughput è $\min(\lambda,\mu)$. L'efficienza (payload) è $\eta=S,L_D/L$.Tecniche ARQ e loro prestazioni →, Prove ripetute e modello binomialen prove indipendenti, ciascuna con probabilità di successo p: una sequenza con k successi ha probabilità p^k (1−p)^(n−k), e la probabilità di esattamente k successi è (n su k) p^k (1−p)^(n−k) (modello binomiale); il primo successo alla prova k ha probabilità (1−p)^(k−1) p.Prove ripetute e modello binomiale →, Capacità di canaleLa capacità di un canale è il massimo, sulle statistiche di ingresso, della velocità di informazione $R=F,I_s(\mathbf c,\tilde{\mathbf c})$ (informazione mutua per simbolo per la velocità di simbolo). Teorema di Shannon: se la velocità informativa è $R<C$ esistono codici con probabilità d'errore residua piccola a piacere; se $R>C$ no. BSC senza memoria: $C_s=1+P\log_2P+(1-P)\log_2(1-P)$ bit/simbolo. Canale AWGN: $C=B\log_2(1+\mathrm{SNR})$ con $\mathrm{SNR}=P_{rx}/(N_0B)$; per $B\to\infty$ la capacità non cresce indefinitamente ma tende a $P_{rx}/(N_0\ln2)$. Limite per il rapporto $E_b/N_0$: $\ge\ln2=-1{,}59$ dB.Capacità di canale →.

a. Errori sul pacchetto

Il pacchetto è corretto se tutti gli $L$ bit lo sono: $$P[0\ \text{errori}]=(1-P_{bit})^L=(1-10^{-5})^{10^4}=0{,}9048,\qquad p=1-(1-P_{bit})^L=0{,}0952.$$ L'approssimazione $p\simeq LP_{bit}=0{,}1$ è qui piuttosto grossolana perché $LP_{bit}=0{,}1$ non è abbastanza piccolo (sviluppo $(1-P)^L=1-LP+\dots$ e il termine successivo, $\binom L2P^2=0{,}005$, non è trascurabile); meglio $e^{-LP_{bit}}=0{,}9048$. Il numero $h$ di bit errati in un pacchetto è una binomiale (Prove ripetute e modello binomialen prove indipendenti, ciascuna con probabilità di successo p: una sequenza con k successi ha probabilità p^k (1−p)^(n−k), e la probabilità di esattamente k successi è (n su k) p^k (1−p)^(n−k) (modello binomiale); il primo successo alla prova k ha probabilità (1−p)^(k−1) p.Prove ripetute e modello binomiale →): $P[h]=\binom LhP_{bit}^h(1-P_{bit})^{L-h}$, quindi $P[1]=0{,}0905$, $P[2]=0{,}00452$, $P[3]=1{,}5\cdot10^{-4}$ (somma con $P[0]$: $0{,}99999$): quasi tutti i pacchetti errati hanno un solo bit sbagliato. Il canale ha capacità $C_s=1-h(10^{-5})=0{,}99982$ bit/simbolo (Capacità di canaleLa capacità di un canale è il massimo, sulle statistiche di ingresso, della velocità di informazione $R=F,I_s(\mathbf c,\tilde{\mathbf c})$ (informazione mutua per simbolo per la velocità di simbolo). Teorema di Shannon: se la velocità informativa è $R<C$ esistono codici con probabilità d'errore residua piccola a piacere; se $R>C$ no. BSC senza memoria: $C_s=1+P\log_2P+(1-P)\log_2(1-P)$ bit/simbolo. Canale AWGN: $C=B\log_2(1+\mathrm{SNR})$ con $\mathrm{SNR}=P_{rx}/(N_0B)$; per $B\to\infty$ la capacità non cresce indefinitamente ma tende a $P_{rx}/(N_0\ln2)$. Limite per il rapporto $E_b/N_0$: $\ge\ln2=-1{,}59$ dB.Capacità di canale →), quasi perfetta: ma il pacchetto è comunque errato quasi una volta su dieci.

b. Senza errori

Tempo di pacchetto $t_P=L/R_b=10^4/10^6=10$ ms; tasso di servizio $\mu=1/t_P=100$ pkt/s. Con $\lambda=50<\mu=100$ il sistema è stabile, il fattore di carico è $\rho=\lambda/\mu=0{,}5$, il traffico offerto $G=\lambda/\mu=0{,}5$ e il throughput (stabile) $\lambda=50$ pkt/s ($S=\rho=G=0{,}5$, cioè $0{,}5$ Mbit/s).

c. Con gli errori, SR-ARQ

Ogni pacchetto richiede in media $E[\#tx]=\frac1{1-p}=1{,}105$ trasmissioni ($E[\#retx]=\frac p{1-p}=0{,}105$). Il tasso totale di pacchetti trasmessi, nuovi più ritrasmessi, è $\lambda_T=\frac{\lambda}{1-p}=55{,}3$ pkt/s e il traffico offerto effettivo è $G=\lambda_Tt_P=0{,}553$ (maggiore del $0{,}5$ di prima). Il throughput normalizzato resta $S=\lambda t_P=0{,}5$ (tutto ciò che entra esce, se stabile). Condizione di stabilità: $\lambda_T<\frac1{t_P}$, cioè $$\lambda<\frac{1-p}{t_P}=0{,}9048\cdot100=90{,}5\ \text{pkt/s}.$$ $50<90{,}5$: stabile. (Controllo: $S=P_{success}G=0{,}9048\cdot0{,}553=0{,}5$.)

d. $\lambda=95$ pkt/s

Senza errori sarebbe stabile ($95<100$, $\rho=0{,}95$), ma con gli errori $95>90{,}5$: la coda ARQ è instabile. Il throughput è quello massimo del canale saturo, $S=1-p=0{,}9048$, cioè $90{,}5$ pkt/s ($0{,}905$ Mbit/s): il $5\,\%$ circa del traffico offerto ($95-90{,}5=4{,}5$ pkt/s) si accumula in coda senza mai uscire, e il ritardo cresce senza limite. Lezione: la stabilità va controllata con il tasso effettivo che tiene conto delle ritrasmissioni, non con $\lambda<1/t_P$.