Reti di Elaboratori e Architettura di Internet

TIMEOUT

create(pkt, pktout);

start timer(pktout);

send(pkt);

end

end

if event == then

ACK

stop timer(acked);

end

Notare che bisogna tenere conto del fatto che il tempo di un timer non può

essere impostato con un valore qualsiasi. Se un timer ha un valore troppo ele-

24

vato, si rischia di accorgersi troppo tardi di aver perso un segmento, mentre se

il timer è troppo corto, si richia di reinviare un segmento che è stato ricevuto

correttamente, ma di cui l’ACK è ancora in viaggio.

Per impostare correttamente il valore di un timer è necessario stimare il tem-

po di RTT e stimare di quanto questo tempo varia tra un segmento e l’altro.

Siano RT T , RT T , rispettivamente, l’RTT stimato fino a questo momento e

s r

l’RTT registrato per l’ultimo segmento. Si può utilizzare la seguente formula di

aggiornamento, che per oculati valori di α (solitamente α = 1/8) tiene in consi-

derazione il valore stimato fino a quel momento, ma in misura esponenzialmente

minore ad ogni segmento. −

RT T = (1 α)RT T + α RT T

s s r

La variazione RT T viene calcolata in modo analogo, anche se con un coefficiente

v

solitamente maggiore (generalmente β = 1/4):

− − |

RT T = (1 β)RT T + β|RT T RT T

v v r s

A questo punto diventa semplice stimare un valore per il timeout, tenendo conto

della variazione possibile nel traffico della rete:

T imeout = RT T + 4 RT T

s v

3.2.2 Pipelining

Come già accennato in precedenza, attendere l’acqiusizione del messaggio di

ACK per trasmettere il segmento successivo, implicherebbe uno spreco di tempo

enorme. Per ovviare a questo problema, viene introdotta la tecnica del pipeli-

ning. L’idea di fondo è quella di trasmettere i segmenti uno dietro l’altro, senza

preoccuparsi, temporaneamente, dell’ACK. Se non si riceve un ACK per un de-

terminato segmento, allora il segmento viene reinviato nuovamente. Tenendo

conto che il buffer in cui immagazzinare i segmenti per ricostruire il messaggio

ha una capienza limitata, esistono due protocolli principali che permettono di

realizzare il pipelining: il Go-Back-N e il Selective Repeat.

Il protocollo Go-Back-N è il più semplice dei due. Il mittente ha una fine-

stra di una certa lunghezza N . Quando il mittente riceve un ACK per un certo

segmento i, l’inizio della finestra si sposta nel buffer, impostando il suo inizio

al segmento i + 1. Ovviamente, se l’inizio della finestra si trova in una certa

posizione i, il mittente può inviare, senza ricevere un ACK, i segmenti solo fino

−

a i + N 1. La finestra del ricevente, di lunghezza 1, invece, avrà un certo

indice di inizio j, dopo il quale non sono stati ricevuti segmenti. Se al ricevente

non arriva un segmento con sequence number j + 1, allora questi continuerà

ad inviare un ACK con sequence number j, scartando tutti i segmenti ricevuti,

finché il mittente non soddisferà la richiesta.

25

Il problema del protocollo Go-Back-N è che, reinviando tutto, viene sprecato

un tempo enorme, poiché tutti i segmenti successivi, che potrebbero essere im-

magazzinati, vengono scartati e devono essere reinviati più di una volta, anche

se, magari, erano stati ricevuti correttamente.

Il protocollo Selective Repeat risolve anche questo secondo problema.

L’idea è proprio quella di dare al ricevente una finestra lunga N , come quella del

mittente, e di lasciargli immagazzinare i segmenti ricevuti, indipendentemente

dall’ordine in cui sono ricevuti. Se la finestra del ricevente, infatti, inizia ad un

certo indice j prima del quale tutti i segmenti sono stati confermati, la ricezione

di un segmento con sequence number j + k (con k > 1) non implica lo scarto del

segmento, ma l’immagazzinamento nella rispettiva locazione del buffer e l’invio

del messaggio di ACK per quel segmento.

Se, invece, viene ricevuto il segmento j + 1, allora la finestra avanza fino al

primo segmento non ricevuto e l’ACK viene inviato. Da parte del mittente, la

situazione è completamente analoga.

Algoritmo 3.2.2: pipeline case L’algoritmo che gestisce la finestra per

il selective repeat. Da sostituirsi all’evento nell’algoritmo 3.2.1.

ACK

SendBase = InitBase;

...

if event == then

ACK

if acked > SendBase then

stop timer(acked);

←

for i SendBase + 1 to acked do

if alredy acked(i) then

←

SendBase i + 1;

else

break;

end

end

end

end

3.2.3 Flow Control e Congestion Control

Il controllo del flusso è un problema per cui non è possibile inviare più segmenti

di quanti il ricevente ne possa immagazzinare, in modo da evitare il problema

delle perdite dovute al riempimento della coda. Per risolvere questo problema,

è sufficiente che il ricevente, quando invia il segnale di ACK, notifichi al mit-

tente anche lo spazio ancora disponibile nel buffer. Il mittente, a questo punto,

regolerà l’invio dei dati imponendo una dimensione massima al segmento pari

proprio allo spazio disponibile nel buffer del ricevente. Se il sequence number

non si riferisce al numero del segmento, ma alla posizione del byte, nel messag-

gio, che inizia il segmento, allora la notifica al mittente del numero dell’ultimo

26

byte immagazzinato nel buffer e della dimensione dello spazio libero, può essere

fatta con un campo in meno, perché il campo che notifica l’ultimo ACK è pro-

prio il campo del sequence number.

Il problema della congestione della rete, invece, è molto più complicato. Si

tratta di regolare la velocità a cui i pacchetti vengono inviati in base al traffico

presente nella rete. Più traffico è presente, più i pacchetti grandi intaseranno la

rete, rallentando ancora di più il traffico.

Si definisce una variabile cwnd, che indica la dimensione massima della fine-

stra di trasmissione. Questa variabile è utilizzata per definire la velocità a cui

possono essere trasmessi i dati.

In parole povere, cwnd definisce il numero di segmenti che possono essere inviati

ad ogni RTT, perciò, approssimativamente

∗

cwnd sizeof(segment) byte/sec

rate = RT T

E per bloccare la trasmissione è sufficiente imporre che la seguente sia sempre

vera − ≤ ∗

LastByteSent LastByteAcked cwnd sizeof(segment)

Il modo in cui viene gestita la variazione di cwnd è molto complicato e differisce

dal momento della trasmissione e dagli eventi che occorrono.

All’inizio della connessione, la gestione della congestione entra in modalità

slow start. Si pone cwnd = 1 e, ad ogni ACK ricevuto, viene incrementato di 1.

In questo modo, cwnd aumenta esponenzialmente, perché se cwnd = n e nessun

pacchetto viene perso, allora vengono ricevuti n ACK, dopo i quali cwnd = 2n.

Durante la fase di slow start possono occorrere due eventi:

• Occorre un timout per un pacchetto. Questo evento significa che un pac-

chetto è andato perso. cwnd viene impostato ad 1 e cresce esponenzial-

mente fino ad una certa soglia, definita dalla variabile ssthresh. Da quel

punto in poi, cresce linearmente.

• Si riceve tre volte un ACK per un determinato pacchetto. Questo signi-

fica che i pacchetti successivi non sono mai stati ricevuti, quindi la rete

potrebbe essere congestionata. cwnd viene dimezzata e da questo punto

in poi crescerà linearmente.

Per calcolare la variabile ssthresh è sufficiente che essa sia impostata alla

metà del valore di cwnd esattamente prima della perdita del pacchetto. In que-

sto modo, nel caso di un timeout, cwnd crescerà esponenzialmente fino alla velo-

cità precedente a quella che ha causato quel timeout, mentre nel caso di un triplo

ACK assumerà esattamente il valore di ssthresh, quindi verrà incrementato da

subito con velocità lineare. 27

Capitolo 4

Livello Network

Nel livello network si arriva finalmente alla concezione di rete. In questo livello si

prende coscienza del fatto che due host comunicanti non si passano informazioni

direttamente, ma queste ultime devono attraversare una rete di altri host e

router, prima di arrivare a destinazione.

Il compito del livello network è quello di incapsulare i segmenti provenienti dal

livello di trasporto in datagrammi, contenenti sia il segmento, sia l’header del

protocollo di networking, per poi trovare la strada migliore attraverso la rete che

possa portare il datagramma a destinazione, dove verrà decomposto e spedito

al livello di trasporto.

Due sono le parole chiave che identificano il livello network:

• Routing:

Il processo di routing è quello che identifica, dati due nodi A, B nel grafo

della rete, la strada che permette ad un datagramma che parte da A di

arrivare a B.

• Forwarding:

Il processo di forwarding è quello che identifica, dato un datagramma che

arriva ad una delle porte di unput del router, l’appropriata porta di output

per proseguire il tragitto verso la destinazione.

Un protocollo di networking può fornire diverse garanzie, come, ad esempio,

quella di consegnare i messaggi, di consegnarli in ordine o con una larghezza

minima di banda.

Nonostante ciò, il protocollo utilizzato per la rete Internet, il protocollo IP, non

fornisce alcuna garanzia: si comporta come un protocollo best-effort.

Al livello network possono essere forniti due tipi di servizi:

• Datagram Network:

Una datagram network fornisce un servizio connectionless, vale a dire

che i datagrammi vengono spediti senza stabilire una connessione con il

destinatario. 28

• Virtual Circuit Network (VC):

Un VC fornisce un servizio di setup della connessione, analogo a quello

utilizzato per il protocollo TCP.

Il vantaggio di una connessione VC è che il tempo impiegato per l’invio

di tutti i datagrammi viene considerevolmente ridotto, in quanto un router

potrebbe riservare delle risorse ad un VC e mantenere delle informazioni sul

percorso nella rete.

L’implemetazione di una rete VC necessita di un percorso da mittente a de-

stinatario, un numero identificativo per ogni link (VC number ) e una forwarding

table dedicata.

L’idea di fondo è quella di assegnare ad ogni datagramma un VC number, che

potrebbe essere cambiato al router successivo. La forwarding table, sapendo

da quale link proviene il datagramma e in quale porta di input è arrivato, lo

immetterà su una corrispettiva porta di output cambiando, se necessario, il suo

VC number.

Una datagram network funziona in modo completamente diverso. Non c’è

alcun setup della connessione, i router non mantengono informazioni e non riser-

vano alcuna risorsa dedicata e, infine, il forwarding viene effettuato solamente

con l’ausilio dell’indirizzo di destinazione.

Poiché un indirizzo IP è formato da 32 bit, esistono oltre 4 miliardi di in-

dirizzi. Ovviamente, questo preclude la p