22.6 Protocolli a richiesta automatica
Le trasmissioni
arq (pag.
1) prevedono l’esistenza di un canale di ritorno, mediante il quale chiedere la ri-trasmissione delle trame ricevute con errori; pertanto i dati anche se già trasmessi, devono essere temporaneamente memorizzati al trasmettitore, per rispondere alle eventuali richieste del ricevitore. Viene illustrato per primo un metodo molto semplice, ma potenzialmente inefficiente. Adottando invece buffer (detti
finestre) di ricezione e trasmissione di dimensioni opportune, si riesce a conseguire una efficienza maggiore.
22.6.1 Send and wait
Viene trasmessa una trama alla volta, e si attende un riscontro (
ACKnowledgment) di corretta ricezione prima di trasmettere la seguente. Nel caso in cui il ricevitore rilevi un errore, si genera invece un riscontro negativo (NACK
), che causa la ritrasmissione della trama trasmessa in precedenza. Se il
nack giunge illeggibile, il trasmettitore attende fino allo scadere di un
allarme a tempo (
timeout) e quindi ritrasmette comunque l’ultimo dato inviato.
In figura
22.24 è riportata una tipica sequenza di passaggi, in cui (a) la trama
N + 2 è ricevuta con errore, causando un primo
nack; quindi (b) è l’
ack(
N + 3) ad arrivare errato, causando lo scadere del timeout, e la ritrasmissione della trama
N + 3. Notiamo che le trame devono essere etichettate con un numero di sequenza, in modo da permettere al ricevitore, nel caso (b), di riconoscere la trama come duplicata, e scartarla (l’
ack è inviato comunque per permettere la risincronizzazione del trasmettitore).
Utilizzo del collegamento
Considerando l’intervallo di tempo
tT che intercorre tra la trasmissione di due trame consecutive, la trasmissione vera e propria dura solamente
tTx istanti, dopodiché occorre attendere
2 ⋅ tp istanti (
tp è il tempo di
propagazione) prima di ricevere l’
ack. Trascurando gli altri tempi (di trasmissione dell’
ack, e di elaborazione delle trame), si definisce una efficienza di utilizzo
U = tTxtT ≃ tTxtTx + 2 ⋅ tp = 11 + 2 ⋅ tp ⁄ tTx = 11 + 2 ⋅ a
in cui il parametro
a che determina il risultato, può assumere valori molto diversi, in funzione della velocità di trasmissione e della lunghezza del collegamento.
Esempio Una serie di trame di N = 1000 bit viene trasmessa utilizzando un protocollo send-and-wait, su tre diversi collegamenti:
-
a) un cavo ritorto di 1 km,
b) una linea dedicata di 200 km,
c) un collegamento satellitare di 50000 km.
Sapendo che la velocità di propagazione è di 2 ⋅ 108 m/sec per i casi (a) e (b), e di 3 ⋅ 108 m/sec per il caso (c), determinare l’efficienza di utilizzo U = 11 + 2 ⋅ a, per le due possibili velocità di trasmissione fb di 1 kbps ed 1 Mbps.
R: Il tempo necessario alla trasmissione tTx = Nfb risulta pari ad 1 sec ed 1 msec alle velocità di 103 e 106 bps rispettivamente. Il tempo di propagazione tp = spaziovelocità risulta pari a 5 ⋅ 10 − 6 sec, 1 ⋅ 10 − 3 sec e 0.167 sec nei tre casi (a), (b), e (c) rispettivamente. Pertanto:
a) si ottiene a = tptTX = 5 ⋅ 10 − 6 e a = 5 ⋅ 10 − 3 per le velocità di 1 kbps ed 1 Mbps rispettivamente, e quindi per entrambe U ≃ 1;
b) per fb = 1 kbps si ottiene a = 10 − 3 e quindi U ≃ 1, per fb = 1 Mbps risulta a = 1 e quindi U = 0.33;
c) per le velocità di 1 kbps ed 1 Mbps si ottiene a = 0.167 ed a = 167 rispettivamente, a cui corrispondono efficienze pari a U = 0.75 e U = 0.003.
Sulla base del risultato dell’esempio notiamo che, considerando fissa la dimensione di trama, le prestazioni di un collegamento nei confronti di un protocollo arq possono essere caratterizzate, oltre che dal parametro a, anche dal cosiddetto Prodotto Banda-Ritardo PBR = fb ⋅ tp, che infatti nei sei casi in esame vale 5 ⋅ 10 − 3, 5, 1, 103, 160, 1.6 ⋅ 105. Pertanto, abbiamo dimostrato come la trasmissione send and wait possa essere idonea per basse velocità e/o collegamenti brevi, in virtù della sua semplicità realizzativa; in caso contrario, è opportuno ricorrere ad uno dei metodi seguenti.
22.6.2 Continuous RQ
A differenza del protocollo
send-and-wait ora il trasmettitore invia le trame ininterrottamente,
senza attendere la ricezione degli
ack. In presenza di trame ricevute correttamente, il ricevitore riscontra positivamente le stesse, consentendo al trasmettitore di liberare i buffer di trasmissione. In presenza di trame ricevute con errori, la quantità di memoria tampone utilizzata al ricevitore determina la scelta di due possibili strategie di richiesta di ritrasmissione, denominate
go-back-N e
selective-repeat.
In questo caso il ricevitore dispone di una sola posizione di memoria, dove trattiene la trama appena ricevuta per il tempo necessario al controllo di errore. In presenza di un errore di ricezione della trama N + i, rilevato dopo la corretta ricezione di N + i + 1, il ricevitore invia un nack(N + i), chiedendo con ciò al trasmettitore di andare indietro, ed inizia a scartare tutte le trame con numeri maggiori di N + i, finché non riceve la N + i, e riprende le normali operazioni.
Se, trascorso un timeout, la N + i non è arrivata, si invia di nuovo un nack(N + i). Nel caso in cui invece si corrompa un ack, le operazioni continuano regolarmente, e l’ack successivo agisce da riscontro positivo anche per le trame per le quali non si sono ricevuti riscontri. Il trasmettitore deve quindi mantenere memorizzate tutte le trame trasmesse e non ancora riscontrate, fino ad un numero massimo, raggiunto il quale la trasmissione si arresta.
Una variante del metodo, idonea al caso in cui fenomeni di congestione di rete possano determinare la perdita dei nack, prevede l’uso di un timer al trasmettitore, per re-inviare le trame non riscontrate.
22.6.2.2 Selective repeat
L’origine di questo nome deriva dal fatto che non è più richiesto al trasmettitore di tornare indietro completamente, ma è sufficiente ritrasmettere solamente la trama che ha dato origine ad errore in ricezione, grazie alla capacità del ricevitore di memorizzare temporaneamente più trame, anche se ricevute fuori sequenza.
Come si nota alla figura
22.26, a seguito della ritrasmissione della trama
N + 2 per cui si è ricevuto il
nack, il trasmettitore continua ad inviare nuove trame, fino al numero massimo previsto; in assenza di ulteriori
ack, un timer determina la ritrasmissione delle trame non riscontrate.
Quando al ricevitore perviene la trama
N + 2, questo emette un
ack(
N + 5), consentendo al trasmettitore di rilasciare tutta la memoria occupata dalle trame in sospeso, e di proseguire la trasmissione. La perdita di uno o più
ack è gestita allo stesso modo che per
go-back-N, così come per ogni
nack inviato si inizializza un timer, allo scadere del quale ed in assenza di nuove trame ricevute, il
nack è re-inviato.
Dal punto di vista del ricevitore, questo è più complicato che nel caso go-back-N, dato che adesso occorre riordinare le trame ricevute, che possono arrivare sequenziate con un ordine diverso da quello naturale. Per questo motivo, anche il ricevitore deve predisporre delle memorie temporanee dove salvare le trame correttamente arrivate, successivamente a quella che invece conteneva errori, e di cui si attende la ritrasmissione.
22.6.2.3 Efficienza dei protocolli a richiesta automatica
Mentre con le tecniche fec siamo obbligati ad aumentare la fb dei dati trasmessi per poter inserire i bit di ridondanza, potrebbe sembrare che nel caso arq ciò non si verifichi. Ma anche se la ridondanza introdotta è effettivamente inferiore, la necessità di dover ritrasmettere l’intero pacchetto ricevuto errato è anch’essa fonte di riduzione della velocità trasmissiva. Valutiamo di quanto.
Indichiamo con
p la probabilità di dover chiedere la ritrasmissione di una trama per la quale si sono rilevati errori di trasmissione, e con
m il numero totale di trasmissioni necessarie alla sua corretta ricezione. Osserviamo quindi che
m è una variabile aleatoria discreta, caratterizzata dalle probabilità
pM(1) = Pr(m = 1) = 1 − p pM(2) = p(1 − p) pM(3) = p2(1 − p) ⋮ pM(m) = pm − 1(1 − p)
che descrivono come sia possibile ricevere la stessa trama come errata
m − 1 volte, finché all’
m − esima trasmissione non si rilevano più errori. Pertanto, il numero medio di trasmissioni per una stessa trama è pari a
m = E{m} = ∞⎲⎳m = 1m pM(m) = ∞⎲⎳m = 1m pm − 1(1 − p) = = (1 − p) ∞⎲⎳n = 0(n + 1) ⋅ pn = (1 − p) 1(1 − p)2 = 11 − p
in cui alla quarta eguaglianza si è posto
n = m − 1, ed alla quinta si è utilizzato il risultato noto della serie geometrica per ottenere
∞⎲⎳n = 0 (n + 1) pn = ∞⎲⎳n = 1n pn − 1 = ∞⎲⎳n = 0n pn − 1 = ∞⎲⎳n = 0∂∂p pn = = ∂∂p ∞⎲⎳n = 0pn = ∂∂p 11 − p = 1(1 − p)2
Quindi, per trasmettere una frequenza binaria di
fb bps (comprensivi di
crc e
overhead dei numeri di sequenza, vedi §
22.6.3.3), occorre in realtà inviare dati ad una velocità
media pari a
fb ⁄ (1 − p) bps. Questo risultato approssimato si applica ad un protocollo di tipo
selective repeat, e trascurando gli errori sul canale a ritroso.
22.6.3 Controllo di flusso
Si è illustrato come nei protocolli arq il trasmettitore, dopo un po’ che non riceve nuovi ack, cessa a sua volta di inviare trame, dato che esaurisce la memoria temporanea in cui memorizzare le trame già inviate ed in attesa di riscontro. Nel caso in cui il ricevitore non sia in grado di smaltire per tempo i dati ricevuti, può scegliere di sospendere temporaneamente l’invio di riscontri, con il risultato di rallentare la velocità di invio dei dati. Questo meccanismo prende il nome di controllo di flusso, per l’evidente analogia idraulica, in cui una conduttura viene ristretta al fine di ridurre il flusso di liquido in transito.
Dato che il ritardo tra la sospensione dell’invio degli ack e l’interruzione dell’invio di trame dipende dalla dimensione delle memorie temporanee, e che questa dimensione incide allo stesso tempo anche sulla efficienza di utilizzo temporale del collegamento in condizioni di ricezione a piena velocità, svolgiamo alcune riflessioni sull’argomento.
Potrebbe esssere tradotto come
tempo di girotondo, ed è il tempo che intercorre tra l’inizio della trasmissione di una trama e l’arrivo del relativo
ack. La sua valutazione spesso si avvale della ipotesi di poter trascurare il tempo di trasmissione dell’
ack, e quindi si ottiene
RTT ≃ tTx + 2tp
dove
tTx è il tempo necessario a trasmettere il pacchetto, e
tp è il ritardo di propagazione.. Se la trasmissione avviene a velocità
fb allora in un tempo pari a
RTT possono essere trasmessi
Nba = fb ⋅ RTT bit, che possono essere pensati come il numero di
bit in aria. Se la memoria temporanea del trasmettitore ha dimensioni
W ≥ Nba, allora la trasmissione (senza errori) può avvenire senza soluzione di continuità, impegnando costantemente il collegamento.
22.6.3.2 Finestra scorrevole
La quantità massima di dati
W che è possibile trasmettere senza ricevere un riscontro è indicata come
finestra di trasmissione per il motivo che ora illustriamo. In figura
si mostra un gruppo di trame oggetto di una trasmissione; quelle già trasmesse ed in attesa di riscontro (da
N + 3 a
N + 6 in figura) sono racchiuse tra due confini, i
bordi della finestra. Ogni volta che ne viene trasmessa una, il bordo
superiore della finestra è spostato a destra,
allargandola; ogni volta che si riceve un riscontro, è il bordo
inferiore ad essere spostato a destra,
restringendo così la finestra. In definitiva, il termine finestra trae origine dal fatto che, allo spostarsi dei bordi inferiore e superiore, la finestra
si apre e si chiude.
La condizione di
massima apertura della finestra identifica la quantità di memoria necessaria al trasmettitore per realizzare un protocollo
arq, che quindi può essere ri-classificato in questi termini come mostrato in tabella,
dove la colonna
finestra di ricezione indica anche i requisiti di memoria al lato ricevente. Notiamo quindi che mentre per
send-and-wait è sufficiente la memoria di una sola trama, per
go-back-N il trasmettitore deve ricordare fino ad un massimo di
W trame in attesa di riscontro, e per
selective repeat anche il ricevitore ha lo stesso vincolo, allo scopo di riordinare le trame ricevute fuori sequenza.
22.6.3.3 Numero di sequenza
Dato che non possono essere inviate più trame della dimensione della finestra, la loro numerazione può avvenire in forma ciclica, ossia utilizzando un contatore modulo NMax, come indicato alla tabella precedente. Ad esempio, per send-and-wait è sufficiente un contatore binario (0 − 1) perché, nel caso in cui l’ack sia corrotto, il ricevitore possa riconoscere la trama ricevuta come duplicata anziché nuova; un ragionamento simile determina la necessità di usare W + 1 numeri (0 − W) nel caso go-back-N, e 2W + 1 numeri (0 − 2W) nel caso selective repeat.
L’uso di un numero di bit ridotto per indicare il numero di sequenza permette di limitare la dimensione dell’overhead di trama; ad esempio, con una finestra di dimensione 7, l’uso di go-back-N richiede 8 diversi numeri di sequenza, che quindi possono essere codificati utilizzando 3 bit.
scegli
