Esercizio - Throughput di SR-ARQ e stabilità della coda ARQ

Testo (scheda "Data link layer", esercizio 1). Un sistema ARQ opera su un canale a velocità fissa di $2$ Mbit/s con $P_{bit}=10^{-6}$. Si trasmettono pacchetti di dimensione fissa con payload di $4096$ bit e intestazione di $12$ byte. Calcolare il throughput dell'ARQ SR se il tasso di arrivo $\lambda$ è: a. $100$ pacchetti/s; b. $1000$ pacchetti/s. Infine c. discutere, per un $\lambda$ generico, la stabilità della coda ARQ per Stop-and-Wait, Go-Back-N, Selective-Repeat.

Teoria usata: 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 →, 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 →.

1. Dati del pacchetto e probabilità di errore

Payload $L_D=4096$ bit; intestazione $L_H=12\cdot8=96$ bit; lunghezza totale $L=L_D+L_H=4192$ bit. Su un BSC senza memoria il pacchetto è sbagliato se almeno un bit è sbagliato: $$p=P_{loss}=1-(1-P_{bit})^L=1-(1-10^{-6})^{4192}=4{,}18\cdot10^{-3}\ (0{,}418\,\%).$$ ($LP_{bit}=4{,}192\cdot10^{-3}$: l'approssimazione è praticamente identica.) $P_{success}=1-p=0{,}99582$.

Tempo di pacchetto e velocità massima di trasmissione dei pacchetti: $$t_P=\frac L{R_b}=\frac{4192}{2\cdot10^6}=2{,}096\ \text{ms},\qquad\frac1{t_P}=477\ \text{pkt/s}.$$

2. Attenzione: è una trappola

Il throughput dell'ARQ SR è $S=1-p$, ma solo se la coda è sempre piena, cioè se la sorgente offre più traffico di quanto il canale smaltisce. Bisogna prima verificare se il sistema è stabile, cioè se $\lambda<\mu$ con $\mu$ la velocità di servizio.

Per l'SR la velocità di servizio, tenendo conto delle ritrasmissioni (trucco ispirato all'ALOHA: ogni pacchetto è trasmesso in media $\frac1{1-p}$ volte, quindi il tasso totale di pacchetti trasmessi è $\lambda_T=\lambda+\lambda p+\lambda p^2+\dots=\frac{\lambda}{1-p}$), è la velocità totale del canale: il sistema regge se $\lambda_T<\frac1{t_P}$, cioè $$\lambda<\frac{1-p}{t_P}=\frac{0{,}99582}{2{,}096\ \text{ms}}=475\ \text{pkt/s}$$ (il corso confronta con $\frac1{t_P}=477$ pkt/s, il tasso totale del canale al lordo delle ritrasmissioni; la differenza è irrilevante qui).

3. Caso a. $\lambda=100$ pkt/s

$100<475$: stabile. Tutto ciò che arriva esce (e le ritrasmissioni sono assorbite), quindi $$\text{throughput}=\lambda=100\ \text{pkt/s}\ \Rightarrow\ 100\cdot4192=419{,}2\ \text{kbit/s}$$ (di cui $100\cdot4096=409{,}6$ kbit/s di payload). Non si usa $1-p$: quella è la frazione di tempo d'aria utile se il canale fosse saturo.

4. Caso b. $\lambda=1000$ pkt/s

$1000>475$: instabile. Il traffico offerto è $1000\cdot4192=4{,}192$ Mbit/s, più del doppio del canale ($2$ Mbit/s): la coda cresce senza limite. Il canale è saturo e il throughput è quello massimo, $S=1-p$ (frazione di tempo d'aria utile): $$S=1-p=0{,}99582,\qquad\text{throughput}=0{,}99582\cdot2\ \text{Mbit/s}=1{,}991\ \text{Mbit/s}$$ (di cui $1{,}991\cdot\frac{4096}{4192}=1{,}946$ Mbit/s di payload).

5. Caso c. Stabilità in generale

In generale il throughput vale $\min(\lambda,\mu)$: se $\lambda<\mu$ la coda è stabile e il throughput è $\lambda$, altrimenti è instabile e il throughput è il valore massimo di prima. Per calcolare $\mu$ si usa il tempo di servizio $y$ medio per pacchetto, $\mu=1/m_y$:

• Stop-and-Wait: ogni tentativo occupa un round-trip, $y=t_{RTT}(1+i)$ con $i=\#retx$ e $E[i]=\frac1{P_{success}}-1$: $m_y=\dfrac{t_{RTT}}{P_{success}}$, quindi $\mu_{SW}=\dfrac{1-p}{t_{RTT}}$ e la condizione è $\lambda<\dfrac{1-p}{t_{RTT}}$.
• Go-Back-N: con probabilità $P_{success}$ si spende $t_P$, con probabilità $1-P_{success}$ un $t_{RTT}$ e poi si ricomincia: $m_y=t_PP_{success}+p\,(t_{RTT}+m_y)$, da cui $m_y=t_P+t_{RTT}\dfrac p{1-p}$ e $\mu_{GBN}=\dfrac1{t_P+t_{RTT}\,p/(1-p)}$.
• Selective Repeat: $\lambda_T=\lambda/(1-p)<1/t_P$, cioè $\lambda<\dfrac{1-p}{t_P}$.

Questi valori non sono i ritardi: il ritardo è $t_{RTT}$ per ogni ritrasmissione più $t_P+\tau_P$ quando il pacchetto è finalmente corretto.

Variante numerica (parametri nostri, non nel testo). Con $t_A=0$ e $\tau_P=5$ ms: $t_{RTT}=2{,}096+10=12{,}096$ ms ($N=t_{RTT}/t_P=5{,}77$). Allora $\mu_{SW}=\frac{0{,}99582}{12{,}096\ \text{ms}}=82{,}3$ pkt/s, $m_y^{GBN}=2{,}096+12{,}096\cdot0{,}004200=2{,}147$ ms $\Rightarrow\mu_{GBN}=465{,}8$ pkt/s, $\mu_{SR}=475{,}1$ pkt/s. Con $\lambda=100$ pkt/s SW è instabile ($100>82{,}3$) mentre GBN e SR sono stabili: lo stesso carico dà risultati opposti a seconda del protocollo.