Esercizio 28codifica a correzione d'errore e ARQ selective repeat per un server (tema d'esame luglio 2021)

---

Teoria usata: Codifica di canale - codici a blocco, distanza minima, rivelazione e correzioneLa codifica di canale aggiunge ridondanza ai bit per rivelare o correggere gli errori del canale. Un codice a blocco $(n,k)$ trasforma $k$ bit in $n$ bit (rendimento $R_c=\frac kn$). Con la distanza di Hamming minima $d_{min}$ il codice rivela fino a $d_{min}-1$ errori e ne corregge $t=\left\lfloor\frac{d_{min}-1}2\right\rfloor$ (decodifica a minima distanza). Vale il limite di Singleton $d_{min}\le n-k+1$. Su un canale binario simmetrico con errore $p$, la probabilità di parola sbagliata è $P_w\le\sum_{i>t}\binom nip^i(1-p)^{n-i}$ e, con $p$ piccola, $P_{bit}\approx\frac{d_{min}}n\binom n{t+1}p^{t+1}$.Codifica di canale - codici a blocco, distanza minima, rivelazione e correzione →, Tecniche ARQ - stop-and-wait, go-back-N e selective repeatL'ARQ (automatic repeat request) usa un codice che rivela gli errori e fa ritrasmettere i pacchetti sbagliati, con conferme ACK/NACK. Con $p=1-(1-P_{bit})^L$ la probabilità che un pacchetto sia errato, $t_P$ il tempo di pacchetto, $t_A$ quello dell'ACK e $\tau_P$ il ritardo di propagazione: stop-and-wait $S=\frac{t_P(1-p)}{t_P+t_A+2\tau_P}$; go-back-N $S=\frac{(1-p),t_P}{1+(N-1)p}$ con $N-1=\left\lceil\frac{2\tau_P}{t_P+t_A}\right\rceil$; selective repeat $S=(1-p)\frac{t_P}{t_P+t_A}$. Il numero medio di trasmissioni di un pacchetto è $\frac1{1-p}$.Tecniche ARQ - stop-and-wait, go-back-N e selective repeat →, Sistemi a coda - processo di Poisson, M/M/1 e formula di LittleUn sistema a coda ha arrivi (di pacchetti, file) e un servitore (il collegamento). Con arrivi di Poisson di intensità $\lambda$ e tempi di servizio esponenziali di media $\frac1\mu$ (coda M/M/1) e $\rho=\frac\lambda\mu<1$: $P[N=n]=(1-\rho)\rho^n$, numero medio nel sistema $\bar N=\frac\rho{1-\rho}$, tempo medio di permanenza $\bar W=\frac1{\mu-\lambda}$, attesa in coda $\bar W_q=\frac\rho{\mu-\lambda}$. La formula di Little $\bar N=\lambda\bar W$ vale in generale. Con buffer finito (M/M/1/K) i pacchetti sono persi con $P_K=\frac{(1-\rho)\rho^K}{1-\rho^{K+1}}$.Sistemi a coda - processo di Poisson, M/M/1 e formula di Little →, Informazione ed entropiaL'informazione di un evento di probabilità $p$ è $\log_2\frac1p$ bit; l'entropia $H(x)=\sum p\log_2\frac1p$ è l'informazione media e misura l'incertezza della sorgente: $0\le H\le\log_2M$, con il massimo quando i simboli sono equiprobabili. Per più simboli: $H(x,y)\le H(x)+H(y)$ (uguaglianza se indipendenti), $H(x|y)=H(x,y)-H(y)$. Per una sorgente con $F_s$ simboli al secondo il rate di informazione è $F_sH_s$, il rate nominale $F_s\log_2M$ e l'efficienza $\eta=\frac{H_s}{\log_2M}$.Informazione ed entropia →.

(1) Bit-rate medio di arrivo

I file arrivano con intervallo medio $m_{T_f}=10$ ms ($\lambda=100$ file/s) e ognuno porta in media $m_\ell=40$ kbit. Il bit-rate medio è il bit medio per arrivo diviso l'intervallo medio (media di un processo con arrivi indipendenti): $$R_c=\frac{m_\ell}{m_{T_f}}=\frac{40\cdot10^3}{10\cdot10^{-3}}=4\ \text{Mbit/s}.$$

(2) FEC con codice a massima distanza

Parola di codice lunga come il pacchetto: $n=L=800$. Si devono correggere $t=1\%\cdot800=8$ errori, quindi $$d_{min}\ge2t+1=17.$$ Limite di Singleton: $d_{min}\le n-k+1$, cioè $k\le n-d_{min}+1=800-17+1=784$. Il numero massimo di bit di informazione per parola è $k=784$ (rendimento $\frac{784}{800}=0{,}98$). Per smaltire i $4$ Mbit/s di informazione il collegamento deve trasmettere $\frac nk$ volte tanto: $$R_b\ge R_c\cdot\frac nk=4\cdot\frac{800}{784}=4{,}082\ \text{Mbit/s}.$$ (Nella soluzione a mano del Drive si usa $d_{min}=18$ e $k\le783$, che dà $4{,}081$ Mbit/s: la differenza è irrilevante, ma per correggere $8$ errori basta $d_{min}=17$.)

Osservazione. A $R_b=4{,}082$ Mbit/s il collegamento è saturo ($\rho=1$): il buffer non sarebbe stabile. Per un buffer che si comporta come una coda M/M/1 (Sistemi a coda - processo di Poisson, M/M/1 e formula di LittleUn sistema a coda ha arrivi (di pacchetti, file) e un servitore (il collegamento). Con arrivi di Poisson di intensità $\lambda$ e tempi di servizio esponenziali di media $\frac1\mu$ (coda M/M/1) e $\rho=\frac\lambda\mu<1$: $P[N=n]=(1-\rho)\rho^n$, numero medio nel sistema $\bar N=\frac\rho{1-\rho}$, tempo medio di permanenza $\bar W=\frac1{\mu-\lambda}$, attesa in coda $\bar W_q=\frac\rho{\mu-\lambda}$. La formula di Little $\bar N=\lambda\bar W$ vale in generale. Con buffer finito (M/M/1/K) i pacchetti sono persi con $P_K=\frac{(1-\rho)\rho^K}{1-\rho^{K+1}}$.Sistemi a coda - processo di Poisson, M/M/1 e formula di Little →) serve $\rho<1$. Con $R_b=5$ Mbit/s la capacità utile è $5\cdot\frac{784}{800}=4{,}9$ Mbit/s, cioè $\mu=\frac{4{,}9\cdot10^6}{40\cdot10^3}=122{,}5$ file/s, $\rho=\frac{100}{122{,}5}=0{,}816$ e il tempo medio di un file nel buffer sarebbe $\bar W=\frac1{\mu-\lambda}=44{,}4$ ms.

(3) Selective repeat ARQ

Probabilità d'errore sul pacchetto: un pacchetto da $L=800$ bit è errato se almeno un bit lo è, $$p=1-(1-P_{bit})^L=1-(1-10^{-4})^{800}=0{,}0769.$$ Con selective repeat si ritrasmette solo il pacchetto errato; il numero medio di trasmissioni di un pacchetto è $\frac1{1-p}$ (Tecniche ARQ - stop-and-wait, go-back-N e selective repeatL'ARQ (automatic repeat request) usa un codice che rivela gli errori e fa ritrasmettere i pacchetti sbagliati, con conferme ACK/NACK. Con $p=1-(1-P_{bit})^L$ la probabilità che un pacchetto sia errato, $t_P$ il tempo di pacchetto, $t_A$ quello dell'ACK e $\tau_P$ il ritardo di propagazione: stop-and-wait $S=\frac{t_P(1-p)}{t_P+t_A+2\tau_P}$; go-back-N $S=\frac{(1-p),t_P}{1+(N-1)p}$ con $N-1=\left\lceil\frac{2\tau_P}{t_P+t_A}\right\rceil$; selective repeat $S=(1-p)\frac{t_P}{t_P+t_A}$. Il numero medio di trasmissioni di un pacchetto è $\frac1{1-p}$.Tecniche ARQ - stop-and-wait, go-back-N e selective repeat →). Si adotta un modello semplice: il pacchetto, appena uscito dal buffer, viene trasmesso più volte consecutivamente fino al successo, ciascuna trasmissione durando $t_P=\frac L{R_b}$, e al tempo si aggiunge il ritardo di propagazione $\tau_P$ dell'ultima: $$E[T]=\frac{t_P}{1-p}+\tau_P\le150\ \mu\text{s}\ \Longrightarrow\ t_P\le(150-5)\ \mu\text{s}\cdot(1-p)=145\cdot0{,}9231=133{,}9\ \mu\text{s}.$$ Quindi $$R_b=\frac L{t_P}\ge\frac{800}{133{,}9\cdot10^{-6}}=5{,}98\ \text{Mbit/s}.$$ (Se si trascura $\tau_P$, come fa la soluzione a mano del Drive, $t_P\le150\cdot0{,}9231=138{,}5\ \mu$s e $R_b\ge5{,}78$ Mbit/s. La capacità di smaltire il traffico, $R_b\ge\frac{R_c}{1-p}=\frac4{0{,}9231}=4{,}33$ Mbit/s, è un vincolo meno stretto.)

Confronto. La FEC richiede solo $4{,}08$ Mbit/s per sostenere il traffico, l'ARQ $4{,}33$ Mbit/s di capacità (e $5{,}98$ Mbit/s per rispettare anche il ritardo): con $p=7{,}7\%$ la FEC ha un overhead fisso del $2\%$, l'ARQ ritrasmette il $8\%$ dei pacchetti e aggiunge ritardo variabile.

(Verificato con Python: $t=8$, $d_{min}=17$, $k_{max}=784$, $R_b=4{,}0816$ Mbit/s; $p=0{,}076887$, $R_b=5{,}977$ e $5{,}778$ Mbit/s.)

Errori comuni

• Usare $d_{min}=2t$ ($=16$): per correggere $t$ errori servono $2t+1$.
• Dimenticare di moltiplicare per $\frac nk$: la FEC trasmette più bit di quelli utili.
• Calcolare $p=800\,P_{bit}=0{,}08$ al posto di $1-(1-P_{bit})^{800}=0{,}0769$ (qui l'approssimazione ha un errore del $4\%$).
• Confondere il tempo di trasmissione $t_P=\frac L{R_b}$ con il tempo di propagazione $\tau_P$.