Protocolli ARQ - Stop-and-Wait, Go-Back-N e Selective Repeat

Il problema e la terminologia

Uno dei servizi del livello di collegamento è il controllo degli errori (Livello di collegamento e framingIl livello di collegamento (DLL) consegna un frame da un nodo a un nodo adiacente su un collegamento. Servizi: framing, accesso al mezzo (MAC) con indirizzi MAC a 48 bit, controllo di flusso, rilevazione e correzione degli errori. Si divide in DLC (framing, controllo di errore e di flusso) e MAC (accesso al mezzo condiviso). Il framing delimita i frame con un flag: nei protocolli a byte (flag di 8 bit, ESC) si usa il byte stuffing, in quelli a bit (flag 01111110) il bit stuffing, che inserisce uno 0 dopo ogni cinque 1 consecutivi.Livello di collegamento e framing →), in due forme:

• correzione con codici FEC (Forward Error Correction), cioè con i codici a blocco di 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 →;
• rilevazione con un codice CRC (Cyclic Redundancy Check, un codice a blocco che sa solo rivelare gli errori) combinata con ARQ (Automatic Repeat reQuest): se un frame arriva sbagliato lo si rimanda.

Definizione (ARQ). (Lo stesso argomento, visto con gli strumenti della teoria dell'informazione, è in 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 →.) Metodo di controllo degli errori che usa riscontri (ACK) per ottenere una trasmissione affidabile su un servizio inaffidabile. Se il trasmettitore non riceve l'ACK, ritrasmette il pacchetto finché non lo riceve o supera un numero massimo di ritrasmissioni.

Terminologia:

• ACK (acknowledgment): il ricevitore comunica al trasmettitore che un frame è stato ricevuto correttamente.
  • ACK selettivo (SACK): indica l'insieme dei frame ricevuti bene (per esempio con una maschera di bit).
  • ACK cumulativo ($ACK_i$): il frame $i$ è stato ricevuto bene e anche tutti i precedenti.
• NACK (negative acknowledgment): il ricevitore rifiuta il frame per ora (per esempio per overflow del buffer).

Schema: il trasmettitore ha un buffer di trasmissione (TX) e uno di ritrasmissione (RETX); il canale può sbagliare; il ricevitore controlla il frame (errore?) e rimanda ACK o NACK dopo un ritardo di retroazione; un buffer di risequenziamento rimette in ordine i pacchetti arrivati fuori sequenza prima di consegnarli ai livelli superiori.

Proprietà (requisiti di un protocollo ARQ). Accuratezza: i pacchetti devono essere consegnati al livello $N+1$ del ricevitore senza errori, una e una sola volta (niente duplicati). Efficienza: va evitata la perdita di capacità per ritrasmissioni inutili e il tempo sprecato ad aspettare pacchetti o ACK.

Deadlock e timeout

Problema (deadlock): il trasmettitore aspetta un ACK positivo. Se il frame non arriva, il ricevitore non può mandare nessun ACK e il trasmettitore può aspettare per sempre. È contro il requisito di efficienza. Soluzione: timeout dell'ACK. Dopo aver spedito il frame, il trasmettitore fa partire un conto alla rovescia entro cui l'ACK deve arrivare; se il timer scade prima, ritrasmette.

Duplicati e numero di sequenza

Problema (duplicati): il frame arriva bene e viene consegnato in alto; l'ACK si perde prima di raggiungere il trasmettitore; scade il timeout e il trasmettitore rimanda lo stesso frame; il ricevitore lo riceve ancora bene e lo consegna di nuovo: duplicato. È contro il requisito di accuratezza. Soluzione: numero di sequenza (Sequence Number, SN). Ogni nuovo frame inviato porta un identificatore; il ricevitore scarta i frame consecutivi con lo stesso SN (ma risponde comunque con l'ACK). L'intestazione del livello $N$ contiene allora campi come: tipo, SN, ACK, e in coda il CRC.

Grandezze usate nelle formule

Il tempo $t_G$ coincide con l'$RTT$ di Analisi delle prestazioni di reteLe prestazioni di una rete si misurano con tre famiglie di metriche: traffico (bitrate $R_0$ massimo del collegamento, throughput $S\le R_0$ dati consegnati con successo, goodput al livello applicazione), ritardo (end-to-end $d_{tot}=d_{proc}+d_{queue}+d_{trans}+d_{prop}$ con $d_{trans}=L/R$ e $d_{prop}=d/v$; jitter; RTT) e capacità del tubo (BDP $=R\cdot$ ritardo, bit che riempiono il collegamento), più l'affidabilità (PER, PDR, PLR). Il throughput di un percorso è quello del collegamento collo di bottiglia, $\min$ dei bitrate, ricordando che i collegamenti condivisi dividono la capacità.Analisi delle prestazioni di rete → (frame e ACK inclusi).

Definizione (utilizzazione ed efficienza). Con $E[t_T]$ valore medio del tempo per consegnare con successo un frame: $$\rho=\frac{t_F}{E[t_T]},\qquad \eta=\frac{t_I}{E[t_T]}=\rho\,\frac{t_I}{t_F}=\rho\,\frac IF.$$ $\rho$ è la frazione di tempo in cui il trasmettitore sta mandando frame, $\eta$ la frazione in cui sta mandando dati utili (senza intestazione).

Se le ritrasmissioni sono indipendentila riuscita di un tentativo non cambia la probabilità degli altri, quindi la probabilità di k fallimenti seguiti da un successo è il prodottoIndipendenza di eventi → con probabilità di fallimento $p$, il numero $X$ di fallimenti prima del primo successo è una variabile geometricaGeo(p) è il numero della prova in cui arriva il primo successo in prove indipendenti: P(X = n) = (1−p)^(n−1) p per n ≥ 1, P(X > n) = (1−p)^n (lunga attesa), media 1/p, varianza (1−p)/p², ed è senza memoria.Distribuzione geometrica → con $P(X=k)=p^k(1-p)$ ($k$ fallimenti, ciascuno di probabilità $p$, e poi un successo di probabilità $1-p$) e valore medioIl valore atteso E[X] = Σ x p_X(x) è la media dei valori di X pesata con le loro probabilità (esiste se la serie converge assolutamente); per una funzione g vale E[g(X)] = Σ g(x) p_X(x) senza trovare la legge di g(X), ed E è lineare: E[aX + bY + c] = aE[X] + bE[Y] + c.Valore atteso → $$E[X]=\frac p{1-p}.$$ Passaggio: per definizione $E[X]=\sum_{k=0}^{\infty}k\,p^k(1-p)=(1-p)\,p\sum_{k=1}^{\infty}k\,p^{k-1}$ (il termine $k=0$ vale $0$ e si è raccolto un fattore $p$). La somma $\sum_{k\ge1}k\,p^{k-1}$ è la derivata rispetto a $p$ della serie geometricaLe serie di cui si conosce il carattere e da usare come termine di paragone: geometrica (converge a 1/(1-q) se |q|<1), telescopiche (somma b_1 - lim b_n, come Mengoli), armonica generalizzata (1/n^alpha converge se e solo se alpha>1).Serie notevoli - geometrica, telescopica, armonica → $\sum_{k\ge0}p^k=\frac1{1-p}$ (valida per $|p|<1$), cioè $\frac1{(1-p)^2}$. Quindi $E[X]=(1-p)\,p\cdot\frac1{(1-p)^2}=\frac p{1-p}$. Controllo: con $p=0{,}1$ si hanno in media $0{,}1/0{,}9=0{,}11$ fallimenti per ogni frame consegnato; con $p=0{,}5$ in media $1$ fallimento.

Stop-and-Wait (S&W-ARQ)

Definizione (Stop-and-Wait). Il più semplice protocollo ARQ: il trasmettitore spedisce un frame alla volta e aspetta il riscontro prima di spedire il successivo. Semplice non vuol dire inefficace: sul collegamento punto-punto, dove la capacità del tubo è vicina a 1, è ottimo.

Stati del trasmettitore: pronto (arriva un frame $i$ dall'alto: lo invia, ne tiene una copia, avvia il timer) e attesa (se scade il timeout rimanda il frame $i$ e riavvia il timer; se arriva l'$ACK_i$ con checksum corretto ferma il timer, scarta la copia e torna pronto).

Numeri di sequenza e di ACK. Basta un bit (aritmetica modulo $2$). L'ACK numero $x+1$ annuncia che si aspetta il pacchetto $x+1$: il numero di ACK annuncia sempre il numero di sequenza del prossimo pacchetto atteso. Se il pacchetto $0$ è arrivato bene il ricevitore manda $ACK\,1$ (si aspetta l'$1$); se è arrivato l'$1$ manda $ACK\,0$.

Esempio (ACK perso). Il trasmettitore manda il frame SN $0$; il ricevitore lo riceve e genera $ACK\,1$, che si perde. Scade il timeout, il trasmettitore rimanda il frame SN $0$. Il ricevitore si aspetta l'$1$ ma riceve lo $0$: riconosce un duplicato, non lo consegna in alto, ma rimanda $ACK\,1$ (continua ad aspettare l'$1$). Il trasmettitore riceve finalmente l'$ACK\,1$ e può mandare il frame $1$.

Efficienza dello Stop-and-Wait

Una trasmissione riuscita occupa $t_G=t_F+2\tau_p+t_A$: il frame ($t_F$), la sua propagazione ($\tau_p$), l'ACK ($t_A$) e la sua propagazione di ritorno ($\tau_p$). Ogni fallimento costa esattamente $t_G$ se il timeout è il minimo possibile ($t_0=t_G$). Quindi $$E[t_T]=t_G+E[X]\,t_G=t_G+\frac p{1-p}\,t_G=\frac{t_G}{1-p}=\frac{t_F+2\tau_p+t_A}{1-p}.$$

Formula (Stop-and-Wait). $$\rho_{SW}=\frac{t_F}{E[t_T]}=\frac{t_F(1-p)}{t_F+2\tau_p+t_A}=\frac{t_F(1-p)}{t_G},\qquad \eta_{SW}=\rho_{SW}\frac IF.$$

Nota: l'ultima trasmissione (quella riuscita) è l'unica che conta come «utile»; per questo nell'espressione compare un solo $t_F$ al numeratore.

Esempio. $C=1$ Mbit/s, $F=10$ kbit ($t_F=10$ ms), $\tau_p=25$ ms, $t_A\approx0$: $t_G=10+50=60$ ms. Senza errori ($p=0$): $\rho=10/60=16{,}7\,\%$: il collegamento è usato un sesto del tempo. Con $p=0{,}1$: $E[t_T]=60/0{,}9=66{,}7$ ms, $\rho=0{,}9\cdot10/60=15\,\%$. Il collo di bottiglia è la capacità del tubo: $t_G/t_F=6$ pacchetti potrebbero stare in volo, ma se ne spedisce uno.

Finestre scorrevoli (sliding window)

Lo S&W permette un solo frame alla volta. La soluzione è il pipelining: spedire più frame non riscontrati uno dopo l'altro. Quanti dipende dal prodotto banda-ritardo (Analisi delle prestazioni di reteLe prestazioni di una rete si misurano con tre famiglie di metriche: traffico (bitrate $R_0$ massimo del collegamento, throughput $S\le R_0$ dati consegnati con successo, goodput al livello applicazione), ritardo (end-to-end $d_{tot}=d_{proc}+d_{queue}+d_{trans}+d_{prop}$ con $d_{trans}=L/R$ e $d_{prop}=d/v$; jitter; RTT) e capacità del tubo (BDP $=R\cdot$ ritardo, bit che riempiono il collegamento), più l'affidabilità (PER, PDR, PLR). Il throughput di un percorso è quello del collegamento collo di bottiglia, $\min$ dei bitrate, ricordando che i collegamenti condivisi dividono la capacità.Analisi delle prestazioni di rete →). Sono i protocolli a finestra scorrevole: Go-Back-N e Selective Repeat.

Trasmettitore. Ha una finestra di trasmissione di dimensione $N$: $[SN_{min},SN_{max}]$ con

• $SN_{min}$: SN del primo pacchetto non riscontrato;
• $SN_{nxt}$: SN del prossimo pacchetto che si può spedire;
• $SN_{max}=SN_{min}+N-1$: SN dell'ultimo pacchetto spedibile con la finestra attuale;
• $SN_{nxt}-SN_{min}$ pacchetti sono in volo (spediti ma non ancora riscontrati; sono tenuti nel buffer del trasmettitore), e al massimo $N$.

Ricevitore. Ha una finestra di ricezione di dimensione $M$: $[RN_{min},RN_{min}+M-1]$, gli SN che può accettare (dipende dal buffer).

• $RN_{min}$: SN del prossimo pacchetto atteso in ordine;
• $M$: numero massimo di pacchetti che si possono tenere nel buffer;
• i pacchetti vanno al livello superiore solo in sequenza, senza buchi: quelli nella finestra restano fermi finché non arriva il pacchetto con $SN=RN_{min}$.

Operazioni.

• Se il trasmettitore riceve $ACK(n)$ con $SN_{min}<n\le SN_{max}$ la finestra scorre: $SN_{min}=n$ (ACK cumulativo) e $SN_{max}=SN_{min}+N-1$.
• Quando al ricevitore arriva il pacchetto con $SN=x$: se $x$ è fuori dalla finestra di ricezione, è scartato; se $x>RN_{min}$ è memorizzato nel buffer; se $x=RN_{min}$, $RN_{min}$ passa all'SN del primo pacchetto mancante della sequenza e il ricevitore consegna in alto i pacchetti fino al nuovo $RN_{min}$.
• Il ricevitore risponde con $ACK(RN_{min})$ (l'ACK del prossimo pacchetto in ordine atteso).

Problema: che cosa succede se un frame della sequenza è corrotto? Molti frame arrivano al ricevitore prima che il trasmettitore se ne accorga. Il ricevitore scarta il frame corrotto: che fa dei successivi? Due soluzioni.

Go-Back-N (GBN-ARQ)

Definizione (Go-Back-N). Finestra di trasmissione $N$, finestra di ricezione $M=1$ (il ricevitore può memorizzare un solo pacchetto, quindi nessuna ricezione fuori ordine). Ricevitore: scarta tutti i pacchetti fuori ordine. Trasmettitore: allo scadere di un timeout ritrasmette tutti i frame dal primo non riscontrato in poi (l'intera finestra). Era la versione antica di TCP.

Esempio ($N=5$, il pacchetto SN 3 si perde). Il trasmettitore spedisce SN 1-5. Il ricevitore riceve 1 e 2 e risponde $ACK(2)$ e $ACK(3)$ (cioè «aspetto il 3»); il frame 3 è perso. Il trasmettitore, ricevuti gli ACK, fa scorrere la finestra e spedisce SN 6 e 7. Ma il ricevitore aspetta il 3: scarta 4, 5, 6, 7 (ognuno provoca un $ACK(3)$ ripetuto, che le slide chiamano NACK(3)). Scade il timeout relativo a SN 3: il trasmettitore torna indietro e rimanda 3, 4, 5, 6, 7. Il ricevitore ora li riceve in ordine e risponde $ACK(4)$,... Totale: ritrasmessi $5=N$ pacchetti, anche se 4-7 erano arrivati correttamente (inefficiente).

Efficienza. Perché la trasmissione sia continua (il trasmettitore non resta mai fermo ad aspettare), l'ACK del primo pacchetto della finestra deve tornare mentre sta ancora trasmettendo gli $N$ pacchetti: $N\,t_F\ge t_G$, cioè $$N\ge\frac{t_G}{t_F}\quad(\text{finestra almeno pari alla capacità del tubo in pacchetti}).$$ Anche il timeout deve valere almeno $t_0\ge N\,t_F$ (ma non meno di $t_G$).

Se un pacchetto fallisce, il suo recupero costa $N\,t_F$. Ragione: dopo aver spedito il frame guasto il trasmettitore continua a mandare i successivi (la finestra è di $N$ frame, quindi $N\,t_F$ secondi di trasmissione); solo allo scadere del timeout $t_0=N\,t_F$ si accorge dell'errore e riparte dal frame guasto, rimandando l'intera finestra. Il tempo speso per ogni tentativo fallito è quindi $N\,t_F$ e non $t_F$, mentre l'ultima trasmissione, quella riuscita, conta solo $t_F$. Con $E[X]$ fallimenti in media: $$E[t_T]=t_F+E[X]\,N\,t_F=t_F+\frac p{1-p}\,N\,t_F.$$

Formula (Go-Back-N, finestra $N\ge t_G/t_F$). $$\rho_{GBN}=\frac{t_F}{E[t_T]}=\frac{1-p}{1+(N-1)\,p},\qquad \eta_{GBN}=\rho_{GBN}\frac IF=\frac{I(1-p)}{F[(N-1)p+1]}.$$

Passaggio: si divide numeratore e denominatore per $t_F$, $\rho=\frac{t_F}{t_F+\frac p{1-p}Nt_F}=\frac{1}{1+\frac{pN}{1-p}}$, e si moltiplica sopra e sotto per $(1-p)$: $\rho=\frac{1-p}{(1-p)+pN}=\frac{1-p}{1+(N-1)p}$ (nel denominatore si è raccolto $p$ in $-p+pN=(N-1)p$). Senza errori ($p=0$) $\rho=1$: GBN è efficiente anche su collegamenti con grande capacità del tubo; con errori è inefficiente perché ritrasmette pacchetti già arrivati bene.

Esempio. $N=10$ (tubo di $10$ pacchetti), $p=0{,}1$: $\rho_{GBN}=0{,}9/(1+9\cdot0{,}1)=0{,}9/1{,}9=47{,}4\,\%$. Letto in tempo: $E[t_T]=t_F\,(1+\frac{0{,}1}{0{,}9}\cdot10)=2{,}11\,t_F$, di cui $1{,}11\,t_F$ sono ritrasmissioni di finestre intere.

Selective Repeat (SR-ARQ)

Definizione (Selective Repeat). Finestra di ricezione uguale a quella di trasmissione ($M=N$): il ricevitore accetta e memorizza anche i pacchetti fuori ordine (fino a $M$) e li consegna ai livelli superiori solo quando ha una sequenza consecutiva. Per ogni frame ricevuto bene (nuovo o duplicato) manda l'ACK con l'SN del primo pacchetto mancante (ACK cumulativo). Allo scadere di un timeout ritrasmette solo il frame corrispondente. Si può tenere un timeout (RTO) per ogni pacchetto in volo, oppure uno solo per tutta la finestra, riavviato a ogni ritrasmissione.

Esempio (stesso scenario, $N=5$). SN 3 perso. Il ricevitore salva in coda 4, 5, 6, 7 e continua a rispondere $ACK(3)$. Al timeout il trasmettitore rimanda solo SN 3. Appena il 3 arriva, il ricevitore ha 3-7 consecutivi: li riordina e li consegna tutti, e risponde $ACK(8)$. Totale: ritrasmesso $1$ pacchetto.

Efficienza. Una ritrasmissione dura soltanto $t_F$ (non si rimanda la finestra): ogni fallimento costa $t_F$ e non $N\,t_F$, cioè nella formula di GBN si pone $N=1$ nel termine di costo: $$E[t_T]=t_F+\frac p{1-p}\,t_F=t_F\,\frac{(1-p)+p}{1-p}=\frac{t_F}{1-p}.$$

Formula (Selective Repeat). $$\rho_{SR}=\frac{t_F}{E[t_T]}=1-p,\qquad \eta_{SR}=\rho_{SR}\frac IF=\frac{I(1-p)}{F}.$$

Con $p=0$, SR $=$ GBN e $\eta$ è massimo. Con $N>1$ e $p>0$ SR ha throughput maggiore di GBN, perché i PDU ricevuti correttamente non vengono mai ritrasmessi.

Esempio. Stesso caso ($p=0{,}1$): $\rho_{SR}=90\,\%$ contro $47{,}4\,\%$ di GBN e $9\,\%$ di S&W ($t_G/t_F=10$: $\rho_{SW}=0{,}9/10$).

Confronto

Con capacità del tubo $C=t_G/t_F$ pacchetti, trascurando $t_A$:

Il ruolo della finestra si vede anche senza errori ($p=0$): la trasmissione è continua solo se $N\ge C$. Per $N<C$ il trasmettitore spedisce $N$ frame, aspetta l'ACK per il resto del ciclo $t_G$ e lavora quindi per la frazione $N\,t_F/t_G=N/C$ del tempo; da $N=C$ in poi $\rho=1$ e altra finestra non serve ($N=1$ è lo Stop-and-Wait, $\rho=1/C$).

Conclusioni:

• le prestazioni dipendono dalla capacità del tubo;
• SR è sempre il migliore; S&W è il più semplice e peggiora rapidamente al crescere del tubo, ma è ottimo se la capacità del tubo è vicina a 1; nei collegamenti punto-punto è spesso $\approx1$, perciò S&W è comune a livello di collegamento;
• gli ARQ si usano anche ad altri livelli (trasporto con TCP, applicazione): lì il tubo può essere molto più grande e si preferiscono GBN e SR;
• nei protocolli a finestra la finestra di trasmissione ottima è uguale alla capacità del tubo (in pacchetti); una finestra maggiore va bene se il ritmo di invio è regolato dall'arrivo degli ACK;
• per SR la finestra di ricezione dovrebbe essere la più grande possibile, ma servono buffer grandi (costosi).

Dimensione ottima del frame in Selective Repeat

Finora la dimensione del frame $F$ era un dato. In realtà la si può scegliere, e c'è un compromesso:

• un frame lungo ha poche intestazioni per bit di dati (overhead relativo basso), ma ha più probabilità di contenere almeno un bit errato, e quindi di essere ritrasmesso per intero;
• un frame corto viene perso più di rado, ma l'intestazione e il CRC pesano molto sul totale.

Esiste un valore che massimizza il throughput utile. Si calcola per Selective Repeat (in cui l'unico costo di un errore è la ritrasmissione del frame sbagliato).

Grandezze. $R_{LL}$: bitrate disponibile al livello di collegamento [bit/s]; $x$: lunghezza del frame (dati più overhead) [bit]; $o$: overhead del frame (intestazione $H$ più CRC $C$) [bit]; $P_b$: probabilità di errore sul bit (si assume che gli errori sui bit siano indipendenti e identicamente distribuiti, i.i.d.); $p$: probabilità di errore sul frame.

Un frame di $x$ bit è corretto se tutti i suoi bit lo sono; con errori sui bit indipendentila probabilità che tutti i bit siano giusti è il prodotto delle probabilità dei singoli bitIndipendenza di eventi → la probabilità è $(1-P_b)^x$ (è il caso «zero errori in $x$ prove» del 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 →). Per $xP_b$ piccolo vale $(1-P_b)^x\simeq1-xP_b$, il primo termine del binomio di NewtonLa formula per sviluppare (a+b)^n con i coefficienti binomiali.Binomio di Newton →: $$p=1-(1-P_b)^x\ \ (\simeq xP_b\ \text{se}\ xP_b\ll1).$$ Con Selective Repeat il fattore di utilizzazione è $\rho=1-p$ e la frazione di bit utili è $\frac{x-o}{x}$: il goodput è

Formula (goodput di Selective Repeat in funzione di $x$). $$g(x)=R_{LL}\,\eta(x)=R_{LL}\,\frac{x-o}{x}\,(1-p)=R_{LL}\,\frac{x-o}{x}\,(1-P_b)^x.$$

Il primo fattore $(x-o)/x$ cresce con $x$ (meno overhead relativo); il secondo $(1-P_b)^x$ decresce (più errori). Il prodotto ha quindi un massimo. Per trovarlo si applica il teorema di Fermatx0 è punto di minimo (massimo) relativo se f(x0) ≤ f(x) (≥) per gli x del dominio vicini a x0. I candidati sono gli estremi del dominio, i punti dove f non è derivabile e i punti interni con f'(x0) = 0 (punti critici o stazionari). Teorema di Fermat: in un punto interno di minimo o massimo relativo dove f è derivabile, f'(x0) = 0. È solo una condizione necessaria: x³ in 0.Massimi e minimi relativi e teorema di Fermat →: si deriva $g$ rispetto a $x$ e si cerca dove la derivata si annulla. Con $a=1-P_b$ si ha $g(x)=R_{LL}\bigl(1-\frac ox\bigr)a^x$; con la regola del prodottoDerivate delle funzioni elementari e delle loro inverse (arcsin, arctan, settcosh...) e regole di calcolo: linearità, prodotto (Leibniz), quoziente, funzione composta (regola della catena), funzione inversa, f(x)^g(x).Regole di derivazione →, $\frac d{dx}\bigl(1-\frac ox\bigr)=\frac o{x^2}$ e $\frac{d}{dx}a^x=a^x\ln a$ (derivata di un esponenzialeLa funzione esponenziale a^x (base positiva diversa da 1) e la sua inversa, il logaritmo in base a, con grafici e proprietà.Esponenziale e logaritmo →; qui $\ln$ indica il logaritmo naturale, scritto «log» nelle slide): $$\frac{dg}{dx}=R_{LL}\Bigl[\frac o{x^2}\,a^x+\Bigl(1-\frac ox\Bigr)a^x\ln a\Bigr]=R_{LL}\,a^x\,\frac{o+x(x-o)\ln a}{x^2},$$ dove si è raccolto $a^x$ e si è portato tutto sul denominatore $x^2$ (il secondo addendo è $\frac{x-o}{x}\ln a=\frac{x(x-o)\ln a}{x^2}$). Sostituendo $a=1-P_b$: $$\frac{dg}{dx}=R_{LL}\,\frac{o+x(x-o)\ln(1-P_b)}{x^2}\,(1-P_b)^x.$$ Il segno è quello del numeratore, perché $x>0$, $x^2>0$, $(1-P_b)^x>0$. Ponendo $\xi\triangleq\ln(1-P_b)$ (negativo, perché $1-P_b<1$) e imponendo $dg/dx=0$ si annulla il numeratore: $o+\xi x(x-o)=0$, cioè (sviluppando il prodotto) $\xi x^2-\xi o\,x+o=0$. È un'equazione di secondo grado in $x$: dividendo per $\xi$ diventa $x^2-o\,x+\frac o\xi=0$ e la formula risolutiva dà $$x_{1,2}=\frac{o\pm\sqrt{o^2-\dfrac{4o}{\xi}}}{2}.$$ Poiché $\xi<0$, $-4o/\xi>0$ e la radice supera $o$: la soluzione con il segno $-$ è negativa e va scartata, resta quella con il $+$. Che sia un massimo lo si vede dal segno: il numeratore $o+\xi x(x-o)$ vale $o>0$ in $x=0$ ed è una parabola con coefficiente di $x^2$ negativo ($\xi<0$); è quindi positivo fino alla radice positiva e negativo dopo. La derivata cambia segno da $+$ a $-$: $g$ cresce e poi decresce, e $x_{ott}$ è il massimo.

Formula (dimensione ottima del frame). $$x_{ott}=\frac{o+\sqrt{o^2-\dfrac{4o}{\ln(1-P_b)}}}{2}\ \simeq\ \frac o2+\sqrt{\frac o{P_b}}\quad(P_b\ll1).$$

Passaggio dell'approssimazione: per $P_b\ll1$ lo sviluppo di Mac-LaurinTabella degli sviluppi di Mac-Laurin da sapere a memoria (e^x, sin, cos, log(1+x), (1+x)^alpha, arctan, sinh, cosh, tan) e regole per combinarli: algebra degli o piccoli, prodotti, funzioni composte, quanti termini tenere.Sviluppi di Mac-Laurin notevoli → $\ln(1-P_b)\simeq-P_b$ dà $-\frac{4o}{\xi}\simeq\frac{4o}{P_b}$, enorme rispetto a $o^2$ (per $o=50$ e $P_b=10^{-3}$: $2\cdot10^5$ contro $2500$). Allora $\sqrt{o^2+\frac{4o}{P_b}}\simeq\sqrt{\frac{4o}{P_b}}=2\sqrt{\frac o{P_b}}$ e, dividendo per $2$, resta $\frac o2+\sqrt{\frac o{P_b}}$.

Esempio (le curve delle slide). Overhead $o=50$ bit.

• $P_b=10^{-3}$: $\ln(1-P_b)=-1{,}0005\cdot10^{-3}$, $-4o/\xi=1{,}9990\cdot10^{5}$, $x_{ott}=\dfrac{50+\sqrt{2500+199\,900}}{2}=\dfrac{50+449{,}9}{2}\simeq250$ bit. L'approssimazione dà $25+\sqrt{50\,000}=248{,}6$. Efficienza massima: $\frac{200}{250}\cdot0{,}999^{250}=0{,}8\cdot0{,}779=0{,}62$.
• $P_b=10^{-2}$: $x_{ott}\simeq100$ bit (approssimazione: $25+\sqrt{5000}=95{,}7$), efficienza massima $\frac{50}{100}\cdot0{,}99^{100}=0{,}5\cdot0{,}366=0{,}18$.

Osservazioni: le prestazioni di un ARQ dipendono dalla dimensione del pacchetto; la scelta può essere adattiva in funzione del BER; i pacchetti corti sono preferibili quando il canale è soggetto a errori (BER alto), quelli lunghi quando il canale è buono. Nel grafico delle slide con MTU $=1500$, $300$ e $75$ byte, a BER molto basso vince l'MTU maggiore (meno overhead), a BER alto vince il minore.

Altre formule delle slide per lo stop-and-wait. In funzione di $p$ come probabilità di errore sul frame, con dati $I$, intestazione $H$ e ACK di $A$ bit (quindi $F=I+H$): $$\eta_{SW}=\frac IF\rho=\frac{I(1-p)}{I+H+A+2R_{LL}\tau_p}\ \simeq\ \frac{I\,[1-(I+H)P_b]}{I+H+A+2R_{LL}\tau_p}.$$ Per GBN con timeout «stringente» $t_o=N t_F$ (cioè $N t_F\approx RTT$) la stessa formula di prima si riscrive $\rho_{GBN}=\dfrac{F(1-p)}{F+(A+2R_{LL}\tau_p)\,p}$, che per $p\to0$ tende a $1$, mentre per lo S&W $\rho\to t_F/RTT<1$ anche senza errori. Per SR: $\rho=1-p\simeq1-(I+H)P_b$ e $\eta=\frac IF(1-p)$.

Esempio. $R_{LL}=1$ Mbit/s, $I=1000$ bit, $H=100$ bit, $A=100$ bit, $\tau_p=1$ ms, $P_b=10^{-5}$: $F=1100$ bit, $p=1-(1-10^{-5})^{1100}=0{,}01094$ ($\simeq FP_b=0{,}011$). Stop-and-wait: $\eta=\dfrac{1000\cdot0{,}98906}{1000+100+100+2000}=0{,}309$ (il denominatore è $RTT$ in bit: $2R_{LL}\tau_p=2000$ bit pesano più del frame). Selective Repeat: $\eta=\frac{1000}{1100}\cdot0{,}98906=0{,}899$. Il collegamento è lo stesso, la differenza è tutta nell'attesa degli ACK.

Dove si usano. Selective Repeat: livello di collegamento dei sistemi mobili (5G e le generazioni precedenti 4G, LTE, UMTS). TCP moderno (NewReno): Go-Back-N con ACK selettivi (SACK) per recuperare più errori nello stesso RTT; i nuovi Wi-Fi (802.11ax, Wi-Fi 6) usano S&W più SR (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 →). TCP usa ACK cumulativi nel funzionamento normale e una finestra di congestione $cwnd$ che varia dinamicamente (mai oltre $W_{max}$ fissato dal progetto).

Numeri di sequenza e dimensione della finestra

Con $k$ bit per l'SN esistono $2^k$ numeri (che si riusano ciclicamente). Il ricevitore non deve confondere un pacchetto nuovo con uno vecchio ritrasmesso: per GBN la finestra di trasmissione può arrivare al massimo a $N\le2^k-1$; per SR $N=M\le2^{k-1}$ (la finestra di ricezione sulle slide è $2^{m-1}$). Per S&W basta $k=1$.

Si vedano gli esercizi su ARQ a una e più tratte: Esercizio - Due collegamenti con switch, file da 1250 MB e ARQ stop-and-wait, Esercizio - Due collegamenti da 10 e 2 Gbps, 1000 pacchetti con S&W e GBN, Esercizio - Finestra scorrevole e buffer del ricevitore, Esercizio - Collegamento di 35 km, stop-and-wait e Go-Back-N con pacchetto perso. Per l'accesso al mezzo su collegamenti condivisi: 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 →.