Retels ver 1.9

Appunti di Reti di Telecomunicazioni L-S(versione 1.11)

Ingegnere Pazzohttp://ingegnerepazzo.wordpress.com/

18 marzo 2009

2

Piccola premessa

Questo piccolo riassunto non ha la pretesa di essere un libro, né tantomeno un manuale o un saggio:trattasi piuttosto di semplici appunti riordinati dalla mia obnubilata mente.

In essi potrebbero esserci imperfezioni o incongruenze piccole o grandi, ed esse sono imputabili uni-camente a me e non alle fonti, che consistono nelle slide del prof. Franco Callegati (dalle quali ho attintole immagini) e nei miei modestissimi appunti. Chiedo già in anticipo scusa per qualsiasi errore dovessefar perdere tempo al lettore.

Chiaramente questo riassunto, da solo, non sostituisce le lezioni del prof. (delle quali segue spudo-ratamente la traccia) e non è esaustivo e chiarificatore quanto può essere la spiegazione in aula degliargomenti ivi trattati. Nonostante questo, spero che possa essere un valido supporto per chiunque fosseinteressato a leggerli o ad utilizzarli.

Ing. Pazzo

Indice

1 Il protocollo TCP: generalità 51.1 Il segmento TCP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51.2 Macchina a stati finiti . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

1.2.1 Three-way handshake . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71.2.2 Chiusura della connessione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

1.3 Lo svolgimento del dialogo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81.3.1 Retransmission Time-Out . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

1.4 Lo stato enstablished . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121.5 Messaggi di conferma (ACK) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121.6 In sintesi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

2 Il protocollo TCP: controllo del flusso 152.1 Generalità . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152.2 Meccanismo a finestra scorrevole . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

2.2.1 Silly Window Syndrome . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162.2.2 Algoritmo di Nagle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

2.3 Controllo di congestione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172.4 Alcune definizioni ed evoluzione della CW . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192.5 Alcune approssimazioni . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

2.5.1 Un esempio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212.6 Altri aspetti del protocollo: algoritmi migliorativi . . . . . . . . . . . . . . . . . . . . . . . . . 22

2.6.1 Fast recovery . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222.6.2 Fast retransmit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242.6.3 Reno e New Reno . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

2.7 In sintesi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

3 Modelli analitici per le prestazioni del TCP 293.1 Ricerca di modelli matematici . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 293.2 Throughput e goodput . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 293.3 Modello periodico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

3.3.1 ACK ritardati . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 313.4 Perdite aleatorie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

3.4.1 Modello TD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 323.4.2 Modello TD+TO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 363.4.3 Modello TD+TO+AW . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

3.5 Modelli a confronto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 373.6 Latenza . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

3.6.1 Finestra a dimensione fissa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 413.6.2 Finestra evolvente (dinamica) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

3.7 In sintesi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

3

4 INDICE

4 Intradamento e forwarding IP 474.1 Introduzione sulla commutazione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

4.1.1 Nodi di commutazione: routing e forwarding . . . . . . . . . . . . . . . . . . . . . . . . 484.2 Indirizzi IP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

4.2.1 Instradamento e table look-up . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 504.3 In sintesi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

5 Architetture dei router IP 535.1 Tipologie commerciali di router . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 535.2 Schema funzionale, routing vs. forwarding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 535.3 Table look-up . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 535.4 Architettura dei router . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

5.4.1 Crossbar . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 555.4.2 Rete di Clos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

5.5 Posizionamento delle memorie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 565.6 In sintesi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

6 Algoritmi di routing 596.1 La teoria dei grafi e il routing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 596.2 Algoritmi per il calcolo del minimum spanning tree . . . . . . . . . . . . . . . . . . . . . . . . . 61

6.2.1 Algoritmo di Kruskal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 616.2.2 Algoritmo di Prim . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

6.3 Shortest path . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 616.4 Algoritmi per il calcolo dello SP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

6.4.1 Bellman-Ford . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 626.4.2 Dijkstra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63

6.5 Applicazione alle reti . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 636.5.1 Flooding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 646.5.2 Deflection routing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 656.5.3 Load sharing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65

6.6 Shortest Path Routing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 666.6.1 Protocolli distance vector . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66

6.7 Soluzioni migliorative ai protocolli distance vector . . . . . . . . . . . . . . . . . . . . . . . . . 696.7.1 Split Horizon . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 696.7.2 Triggered Update . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69

6.8 Protocolli path vector . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 696.9 Protocolli link state . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 706.10 In sintesi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70

7 IGP: Interior Gateway Protocols 737.1 RIP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 737.2 OSPF: Open Shortest Path First . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74

7.2.1 Distinzione logica fra host e router . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 757.2.2 OSPF e reti multi-accesso . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 767.2.3 Messaggi dell’OSPF . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77

7.3 In sintesi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78

8 EGP: Exterior Gateway Protocols 818.1 L’EGP per antonomasia: Exterior Gateway Protocol . . . . . . . . . . . . . . . . . . . . . . . . . 818.2 BPG: Border Gateway Protocol . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81

8.2.1 Attributi e tipi di messaggio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 838.3 In sintesi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84

INDICE 5

9 MPLS: sostituzione d’etichetta 859.1 Introduzione: il label switching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 859.2 Nomenclatura . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 869.3 Uso e trattamento delle label . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 879.4 Allocazione delle label . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 889.5 Altri aspetti . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89

9.5.1 Controllo dei Label-Switched Paths . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 899.5.2 Label Distribution Protocol . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 899.5.3 Fish picture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90

9.6 In sintesi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90

A Esercizi 93A.1 Protocolli di rete, analisi di CW . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93

A.1.1 Esercizio 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93A.1.2 Esercizio 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95A.1.3 Esercizio 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97A.1.4 Esercizio 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99

A.2 Modelli per il TCP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101A.2.1 Esercizio 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101A.2.2 Esercizio 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101A.2.3 Esercizio 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103

A.3 Latenza . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104A.3.1 Esercizio 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104

6 INDICE

Capitolo 1

Il protocollo TCP: generalità

Il protocollo TCP è parte integrante dello strato 4 (trasporto) della pila OSI e ha il compito di svin-colare gli strati superiori dai problemi di rete. È un protocollo di tipo connection-oriented (al contrariodell’UDP che è connection-less) e gestisce una connessione end-to-end (punto-punto) e full-duplex (bidi-rezionale); prevede inoltre procedure per l’instaurazione della connessione, il controllo del suo correttoandamento e la chiusura. Tutte le informazioni necessarie al corretto svolgimento dell’algoritmo TCPsono contenute nel TCB (transmission control block). L’interfaccia con le applicazioni, invece, non è definitaa priori e fondamentalmente dipende dal sistema operativo utilizzato dall’utente.

Il TCP garantisce la correttezza nella consegna dei dati utilizzando un protocollo a finestra scorrevole(Sliding-Window) basato su:

• numerazione sequenziale dei dati;

• conferma esplicita da parte del ricevitore;

• ritrasmissione dei dati non confermati.

1.1 Il segmento TCP

Il TCP incapsula i dati in pacchetti chiamati segmenti. Il segmento TCP prevede un header standarddi 20 byte, un header variabile con varie opzioni, un payload di dimensione variabile contente i dati del-l’applicazione. Ogni segmento può avere una dimensione massima pari a MSS (Maximum Segment Size) etipicamente contiene - oltre ai dati - informazioni come la porta sorgente, la porta destinazione, il numerodi sequenza, l’acknowledge-number, un checksum per controllare se vi sono errori, alcuni bit per settare leopzioni (URG per considerare il campo Urgent Pointer, ACK considerare il campo Acknowledge, RST perresettare la connessione, SYN per sincronizzare i numeri di sequenza, FIN, per indicare la fine dei dati,PSH per la funzione di push, etc. . . ).

L’MSS dipende dall’implementazione e normalmente è configurabile: il valore massimo che può as-sumere è pari a 216 − 20(header TCP)− 20(header IP) = 65495 byte, cioè pari alla dimensione del payloadIP meno le intestazione, ma per l’Ethernet (che è il caso sul quale ci soffermeremo) è molto inferiore inquanto deve rispettare i 1500 byte imposti da tale tecnologia.

1.2 Macchina a stati finiti

In figura 1.1 vediamo il diagramma che illustra il funzionamento del protocollo TCP. Le linee trat-teggiate indicano un’azione tipica di un server, le linee nere le azioni tipiche dei client e quelle chiare glieventi ‘inusuali’. Sopra ogni freccia è indicata inoltre la {causa}/{effetto}. Esaminiamo insieme la figura:cosa succede fra un client e un server che vogliono iniziare a comunicare? Partendo da CLOSED e seguen-do la linea nera, il client invierà un SYN al server per poter sincronizzare con esso il numero di sequenza.Il server (che parte da LISTEN) è - appunto - in ascolto e aspetta che qualcuno chieda i suoi servigi così,quando gli arriva il SYN da parte del client, invia un SYN+ACK per far sapere al client che ha ricevuto lasua richiesta (siamo ora nello stato SYN RECIEVED). Il client riceve la conferma del server e manda a sua

7

8 CAPITOLO 1. IL PROTOCOLLO TCP: GENERALITÀ

Figura 1.1: La macchina a stati finiti che implementa il TCP

volta una conferma (un SYN+ACK): a questo punto il server non richiede altre conferme1 ed entrambii comunicanti finiscono nello stato ENSTABLISHED (in verde). Quello illustrato fin’ora è il cosiddettothree-way handshake (‘stretta di mano a tre tempi’) e, alla prova dei fatti, si è dimostrato un metodo ab-bastanza robusto per instaurare una connessione (v. paragrafo 1.2.1). Chiaramente, durante queste fasi,possono accadere eventi come l’apertura simultanea (freccia nera da SYN SENT a SYN RCVD) o il noncompletamento del TWH (freccia nera da SYN RCVD a LISTEN). La parte inferiore del diagramma a statisi riferisce invece alla chiusura della connessione: la chiusura può essere passiva (da parte del server, chericeve il FIN e risponde con ACK) oppure attiva (da parte del client).

• CASO 1: il client (C) vuole chiudere così invia un FIN; S risponde con un ACK ed, eventualmente,continua ad inviare dati perché la sua direzione è ancora aperta; quando si stufa pure lui invia unFIN e il C, che è in stato FIN WAIT 2, risponde con un ACK.

1Se si continua a confermare all’infinito non si trasmette nulla!

1.2. MACCHINA A STATI FINITI 9

• CASO 2: entrambi vogliono chiudere. Il client C invia il FIN e finisce in FIN WAIT 1, poi riceveanche il FIN del server e va in CLOSING, confermando il tutto con un ACK. Il server poco primaaveva ricevuto il FIN di C e così invia pure lui un ACK; al termine di tale scambio di conferme,entrambe le direzioni si chiudono e la trasmissione ha termine;

• CASO 3: il client vuole chiudere e il server si accorge di voler fare lo stesso. Tutto funziona comenel caso 1, tranne per il fatto che S non vuole spedire dati e in una botta sola invia sia l’ACK che ilFIN.

Si noti che il client rimane per un po’ nello stato di time wait, utile per fare sì che i pacchetti dell’attualeconnessione si estinguano onde evitare la sovrapposizione di più incarnazioni (v. par 1.2.1).

Perché tutta questa serie di conferme e riconferme? Il fatto è che, se il mezzo di comunicazione èinaffidabile, è impossibile avere uno scambio di informazioni con conferma certa in quanto i messaggi, siaquelli contenenti dati che quelli contenenti informazioni di servizio, possono effettivamente perdersi nellarete.

1.2.1 Three-way handshake

Per quanto riguarda l’apertura di una connessione, si è scelto di fermarsi alla conferma della conferma:il three-way handshake, grazie a questa convenzione, è in grado di gestire situazioni di perdita, duplicazioneo ritardo dei pacchetti. In tabella 1.1 si illustra il procedimento con particolare riferimento ai numeri disequenza. Per semplicità indicheremo i due colloquianti con CLIENT e SERVER (ma, per generalità, sipossono pensare tali due computer come due calcolatori qualsiasi A e B).

Chi parla? SIN bit ACK bit SeqN AckN Chi parla?CLIENT 1 0 x -

1 1 y x+1 SERVERCLIENT 0 1 x+1 y+1CLIENT 0 0 x+1 y+1 → inizio invio dati

Tabella 1.1: Numeri di sequenza nel TWH

Si noti che il primo pacchetto dati ha numero di sequenza uguale all’ACK precedente!

Figura 1.2: Possibili inconvenienti in cui si può incappare nel TWH

Eventi imprevisti o inusuali (v. figura 1.2):


• Instaurazione multipla: A e B vogliono connettersi ed inviano entrambi una richiesta d’apertura.Grazie al TWH questa situazione si risolve in modo molto naturale e spontaneo: visto che vi èvolontà di connettersi da parte di entrambi gli host, il primo che riesce a mandare un pacchetto conSIN e ACK entrambi a 1 dà il via alla trasmissione dati (l’altro eventuale pacchetto con SIN e ACKad 1 è del tutto superfluo);

• Pacchetti d’apertura ritardatari: uno dei due tentativi di connessione viene inibito tramite l’atti-vazione del bit RST;

• Problema delle ’incarnazioni’: A e B stanno parlando, ma A viene riavviato per qualche motivo;B rimane attivo su quella connessione, ma se A vuole riprendere la conversazione dovrà stabilirneuna nuova. Questo potrebbe dar adito a diverse ’incarnazioni’ della medesima connessione logica:se le due incarnazioni non sussistono contemporaneamente questo non è un dramma, mentre lasopravvivenza in rete di due (o più) incarnazioni distinte è un problema da non sottovalutare inquanto potrebbero gironzolare pacchetti aventi gli stessi indirizzi (IP + porta), gli stessi numeri disequenza, ma contenuto diverso! Il TCP risolve questo problema (v. paragrafo 1.4) riallineando i nu-meri di sequenza e ristabilendo il parallelismo: uno dei due host, infatti, crederà che la connessioneprecedente sia ancora attiva e invierà all’altro dei numeri di sequenza palesemente sbagliati (cioèappartenenti al passato), cosicché la vecchia connessione verrà annullata con l’attivazione del bitRST.

1.2.2 Chiusura della connessione

Il TCP ce la mette tutta per garantire che, alla chiusura della connessione, non vengano persi dati. An-che questo aspetto, in realtà, non è così immediato da affrontare visto che la rete può risultare inaffidabile:il TCP però ci prova scegliendo una chiusura unidirezionale e indipendente delle due direzioni. L’hostche intende terminare la trasmissione invia un segmento con il bit FIN a 1 e, ricevuto l’ACK, considerachiuso il dialogo. Se l’ACK non arriva, il mittente del FIN lascia comunque la connessione.

Questa procedura ha il pregio di funzionare anche se i due host tentano contemporaneamente dichiudere la connessione: in tal caso, infatti, la chiusura avviene in maniera esattamente simmetrica daambo le parti (vedi la macchina a stati finiti nel paragrafo 1.2).

1.3 Lo svolgimento del dialogo

Il protocollo TCP deve saper gestire problematiche non banali del tipo:

• i ricevitori potrebbero avere caratteristiche fra loro diverse o essere addirittura delle macchinecompletamente diverse;

• la rete non garantisce l’arrivo dei dati in sequenza;

• i pacchetti potrebbero perdersi e non arrivare mai;

• la congestione della rete potrebbe qualcosa di estremamente variabile e il ritardo di propagazionenon essere mai costante;

• possono esserci, in maniera aleatoria, aumenti/diminuzioni della banda dovuti all’arrivo di nuoviutenti (o alla scomparsa di altri);

• etc. . .

Per risolvere questi problemi, il TCP utilizza un protocollo a finestra scorrevole e utilizza quattrocontatori:

• RTO (retransmission time-out): vedi paragrafo 1.3.1;

• persist timer: se un ACK (o, comunque, un messaggio di servizio) viene perso, può capitare che idue host comunicanti rimangano l’uno in attesa dell’altro: il ricevitore attende i nuovi dati, mentre iltrasmettitore aspetta di ricevere la conferma (ACK) in grado di allargargli la finestra. Per prevenirequesta forma di deadlock è necessario che il trasmettitore utilizzi un persist timer che interpelli ilricevitore in maniera periodica;

1.3. LO SVOLGIMENTO DEL DIALOGO 11

• keep-alive timer: non necessariamente, se è attiva una connessione fra due host, vi è un trasferimentodi dati fra sorgente e destinazione; se tuttavia la connessione rimane dormiente per molto tempo, èprobabile che uno dei due colloquianti si sia disattivato ed è opportuno eliminarla del tutto per lib-erare le risorse da essa occupate. Allo scadere del keep-alive timer, uno dei due host invia all’altro unmessaggio di prova; se riceve risposta allora il timer viene resettato mentre, se tutto tace, vengonomandati altri 9 messaggi di prova con un intervallo pari a 75 secondi l’uno dall’altro. Presumi-bilmente, se anche questi 9 messaggi non ricevono risposta, l’altro calcolatore dev’essere ’caduto’quindi la connessione viene interrotta;

• time wait: al termine della chiusura della connessione, il client si ferma nello stato time wait per untempo pari a 2MSL 2, allo scadere del quale - se nulla è accaduto, lo stato della connessione passaa CLOSED. Questo timer vuole garantire l’estinzione di segmenti appartenenti a precedenti incar-nazioni, onde evitare ambiguità con future riconnessioni fra le stesse porte degli stessi calcolatori(vedi paragrafo 1.2.1).

1.3.1 Retransmission Time-Out

Ogni volta che si trasmette un segmento viene fatto partire l’RTO: se il timer scade prima che siastato ricevuto l’ACK si assume che il segmento non sia stato ricevuto. L’RTO dev’essere dimensionatoin relazione al tempo di andata e di ritorno (Round Trip Time, RTT) ma, soprattutto, deve poter esseredeterminato in modo dinamico per meglio adattarsi alle condizioni sempre mutevoli della rete. L’RTT èinfatti aleatorio e dipende dalla maggiore o minore congestione della rete; l’RTO invece è deterministico,nel senso che viene ricavato tramite formule matematiche all’interno delle quali, tuttavia, fa comparsal’RTT medio in qualità di parametro. Per il calcolo si utilizzano tre variabili:

• eRTT: stima del valore medio del RTT basato sulle misurazioni passate;

• sRTT: misurazione del RTT relativo all’ultimo segmento confermato;

• vRTT: stima della variabilità di RTT.

Vediamoli ora più in dettaglio.

Estimated Round Trip Time (eRTT)

La prima misurazione della stima del RTT (parametro eRTT), all’istante n = 0, viene effettuatasemplicemente traendo l’ultima misurazione3

eRTT(0) = sRTT(0)

Quelle successive vengono invece determinate dando un certo peso (1− α) alla stima dell’istante prece-dente (n− 1) e un altro peso (α) al valore ricavato dall’ultimo segmento confermato (istante n):

eRTT(n) = (1− α) · eRTT(n− 1) + α · sRTT(n)

Il parametro α (valore suggerito: 1/8 = 0, 125) indica quanto peso viene dato al ’passato’ (cioè allamisurazione dell’istante n − 1: sRTT(n − 1)): tanto più è piccolo e tanto più faremo riferimento allestime del passato piuttosto che alla misurazione (sRTT) corrente. Tale procedura di calcolo dell’eRTTviene detta Exponential Weighted Moving Average: Exponential perché il peso dei valori passati diminuiscein modo esponenziale a favore dei valori recenti4; Weighted perché il parametro α ci permette di fissare

2MSL = Maximum Segment Lifetime, noto a priori (nell’RFC 793 è fissato a 2 minuti). Perché bisogna aspettare 2MSL e nonsemplicemente MSL? Semplicemente perché adottiamo al filosofia del caso peggiore e vogliamo che si estinguano sia i pacchetti dellevecchie connessioni (vivono al massimo per un tempo pari a MSL) che le loro conferme (aspettiamo un altro MSL)!

3In questo caso non abbiamo alternative per mancanza di informazioni, indi per cui la cosa più logica è quella di affidarsi allamisurazione fatta in quello stesso istante.

4Si ha infattieRTT (1) = (1− α) · eRTT (0) + α · sRTT (1)

eRTT (2) = (1− α)2 · eRTT (0) + (1− α) α · sRTT (1) + α · sRTT (2)

eRTT (3) = (1− α)3 · eRTT (0) + (1− α)2 α · sRTT (1) + (1− α) α · sRTT (2) + α · sRTT (3)

. . .

eRTT (n) = (1− α)n · eRTT (0) +n

∑i=1

(1− α)n−iα · sRTT (i)


il peso dei campioni più recenti; Moving per la sua natura dinamica; Average per l’uso che fa di ’medie’ponderate matematiche.

Parametro vRTT

Passiamo infine al parametro vRTT che, come abbiamo già detto, è una stima della variabilità del RTT.Il valore di vRTT all’istante 0 è canonicamente5 pari a

vRTT(0) =sRTT(0)

2

Per le successive misurazioni, invece, si segue la seguente regola:

vRTT(n) = (1− β) · vRTT(n− 1) + β |eRTT (n− 1)− sRTT (n)|

Il parametro β è compreso tra 0 e 1 e ha valore consigliato pari a 1/4 = 0, 25: questo significa che vienedato più peso al passato rispetto che al presente.

RFC 793 (1981)

L’RTO viene calcolato come segue:

RTO = min[UB, max[LB, (γ · eRTT)]] = γ · eRTTSe non consideriamo i limiti.

UB è il valore massimo ammissibile per RTO6, mentre LB è il corrispondente valore minimo7; γ, invece,è un parametro compreso fra 1 e 2. Come è facile dedurre, l’RTO sarà compreso fra LB e UB; il calcolodell’eRTT, infine, può eventualmente essere sovrastimato mediante il parametro β.

RFC 2988 (2000): algoritmo di Jacobson

Col passare del tempo si è scoperto che la convenzione imposta dall’RFC 793 era migliorabile; Jacobsonha quindi proposto di considerare anche le fluttuazioni della situazione (rappresentate dal parametrovRTT):

RTO = max[LB, eRTT + max[G, 4 · vRTT]] = eRTT + 4 · vRTTSe non consideriamo i limiti.

LB è ancora il valore minimo ammissibile per l’RTO, mentre G è un’unità di misura del tempo presacome parametro. La relazione soprascritta indica che, se la linea è instabile e ballerina, è opportunosovradimensionare l’RTO; in caso contrario, una buona stabilità della linea incoraggerebbe a mantenerel’RTO il più vicino possibile a eRTT (tendiamo a ’fidarci’ della linea). Per visualizzare meglio quanto dettosi faccia riferimento alla figura 1.3.

Linea stabile→ RTO ≈ eRTT

Linea instabile→ RTO >> eRTT

Misurazione di sRTT

Generalmente tale parametro si ricava come multiplo di intervalli di 500 ms; il TCP mantiene attivauna sola misurazione alla volta quindi, in caso di trasmissioni consecutive a breve distanza, solamente laprima valuta l’sRTT (figura 1.4).

Un inconveniente comune (figura 1.5) è quello che potrebbe avvenire quando vi è ritrasmissione deidati (in seguito alla perdita di un pacchetto o allo scadere dell’RTO): per questo motivo in caso di ri-trasmissione l’sRTT non viene misurato e viene invece rilevato al successivo segmento senza ritrasmissione(algoritmo di Karn/Partridge).

Come si nota, iterando la formula compaiono dei termini in cui il parametro α viene elevato ad una certa potenza.5Come per quanto riguarda l’eRTT, non possiamo fare alcuna stima della variabilità visto che siamo all’inizio della trasmissione

e non abbiamo dati sufficienti; anche questa volta la scelta migliore è quella di affidarsi ad un valore standard.61 minuto.71 secondo.

1.3. LO SVOLGIMENTO DEL DIALOGO 13

Figura 1.3: Evoluzione dell’RTO secondo i due RFC illustrati. Il risultato è migliore tanto più si è vicini alla linearossa. Si noti che Jacobson ha dei grossi vantaggi quando la linea è stabile, mentre si tiene dalla parte delsicuro quando non lo è

Figura 1.4: Misurazione dell’sRTT

Exponential back-off

Una volta che avviene una ritrasmissione per mancanza di risposta, può aver senso dare un tempomaggiore al ricevitore di rispondere: per questo motivo, ad ogni ritrasmissione, il TCP raddoppia l’RTOfino al raggiungimento di un valore massimo.


Figura 1.5: Ambiguità nel calcolo dell’sRTT

1.4 Lo stato enstablished

Per avere massima flessibilità si sceglie di assegnare un numero non ai segmenti bensì ai singoli bytetrasportati dai segmenti: si comincia a numerare da un numero X scelto all’atto dell’apertura della con-nessione8 e la conferma di avvenuta ricezione viene data mettendo nel campo Ack number il numero delbyte successivo all’ultimo ricevuto (cioè del primo byte che ci si aspetta di ricevere). Definito questomeccanismo, possono sopraggiungere diversi inconvenienti:

• segmenti duplicati: un segmento con numero di sequenza X viene duplicato dalla rete;

• segmenti ritardati: un segmento con numero di sequenza Y > X arriva prima del segmento X;

• ambedue le cose: un segmento X viene duplicato e una delle due copie viene confermata, mentrel’altra arriva solo successivamente9. In tal caso la trasmissione continua e, una volta che si è esauritolo spazio di numerazione, vengono riciclati numeri già utilizzati10: questo significa che prima opoi sarà generato un altro pacchetto avente numero di sequenza X (ma diverso da quello del giroprecedente): se entrambi gireranno per la rete avremo due segmenti con stessa intestazione macontenuto diverso! Il peggio che può capitare, in questo caso, è che la copia ritardata (quella del giroprima) arrivi prima dell’altra e venga interpretata come segmento valido.

Osserviamo ora la figura 1.6: sulle ordinate compare il numero di sequenza, mentre sulle ascisse iltempo. Le rette nere spesse rappresentano l’andamento crescente del numero di sequenza col passare deltempo: la loro diversa pendenza dipende dalla velocità della connessione (più lo scambio di messaggiè rapido, più velocemente aumenta il SeqN e più pendente è la retta); il segmento orizzontale (MSL) siriferisce all’esistenza in vita di un pacchetto avente numero di sequenza pari a quello cui si era arrivatiprima del crash della connessione C1. La connessione C2 riparte e, in entrambi i casi, finiamo per caderenella trappola dei ’numeri doppi’: l’esempio ci mostra che questo può accedere sia se l’ISN (Initial SequenceNumber) viene fissato a zero di default (a sinistra), sia se viene posto pari a un contatore11 (a destra). L’unicomodo veramente sicuro in grado di farci evitare questo inconveniente è quello di attendere un MSL primadi aprire una nuova connessione TCP (TCP quiet time).

1.5 Messaggi di conferma (ACK)

Gli ACK, ovvero i messaggi di conferma, sono cumulativi e vengono portati ’a cavalluccio’ (piggyback-ing) di un normale messaggio TCP12, che può normalmente contenere dati. La conferma, di default, èesplicita e quindi il ricevitore trasmette un ACK per ogni segmento ricevuto: può però essere conveniente

8Questo numero è detto ISN (Initial Sequence Number) e dev’essere casuale, uguale per tutti nonché appositamente scelto affinchénon vi sia duplicazione nell’uso dei numeri di sequenza.

9Quello che stiamo per dire vale anche nel caso in cui un host venga riavviato a causa di un problema e rimanga attival’incarnazione di tale connessione.

10Questo è inevitabile, ma dovremmo prima essere sicuri che in rete non esistano più vecchi segmenti numerati con tali numeri.Per questo si fissa un massimo tempo di vita dei segmenti (MSL, Maximum Segment Life), noto a priori: nel 1973 tale parametroveniva fissato a 2 minuti, ma con l’avvento di reti sempre più veloci si è reso necessario abbatterlo notevolmente.

11In quest’ultimo caso ISN è funzione del tempo utilizzando un sistema di conteggio a 32 bit con incremento ogni 4 microsecondi.12Quel che fa testo è il bit ACK, che se è pari ad 1 ha significato di conferma.

1.6. IN SINTESI 15

Figura 1.6: Duplicazione dei numeri di sequenza

ripensare questo meccanismo e scegliere di inviare ACK ritardati o cumulativi al fine di diminuirne ilnumero. Si potrebbe, ad esempio, inviare un ACK ogni due segmenti utilizzando il sistema della finestrascorrevole.

Sia ora WT la finestra di trasmissione e WR la finestra di ricezione, con WT e WR minori dello spaziodi numerazione del TPC (M = 232); se il ricevitore ha ricevuto fino a SeqN = N, allora si attenderàun segmento con SeqN = (N + 1) mod M: se non riceve quello che si aspetta13, bensì un segmentocon SeqN > N o < N, allora il ricevitore interpreterà quello che gli arriva rispettivamente come unsegmento fuori sequenza (numero di sequenza troppo alto) o come un duplicato ritardato (numero disequenza appartenente ’al passato’). Nel primo caso il ricevitore memorizzerà il segmento, purché essostia all’interno della sua finestra WR, ritrasmetterà l’ultima conferma inviata (ACK N + 1) e, una volta cheavrà ricevuto tutta la sequenza completa (compreso il segmento N + 1), comunicherà direttamente ’ACKX + 1’ sbloccando la sua finestra; nell’altro caso scarterà il pacchetto considerandolo un doppione. Quantodetto fin’ora funziona purché il ricevitore sia dotato di memoria: chiaramente conviene memorizzare menocose possibili quindi, finché non accade nulla di imprevisto, ogni pacchetto confermato in ordine correttocancella il corrispondente segmento in memoria e fa scorrere la finestra.

1.6 In sintesi

Il TCP è un protocollo di strato 4, pensato per connessioni bidirezionali e point-to-point, in grado di svincolare

gli strati superiori da tutti i problemi di rete e di garantire, grazie alla sua natura connection oriented, una

conversazione a�dabile. In particolare, il TCP fa uso di un meccanismo a �nestra scorrevole in grado di adattarsi

alle condizioni di congestione della rete (v. capitolo 2), di rimediare alla perdita di pacchetti e di assicurare il

corretto ordine della loro ricezione.

L'unità di riferimento è il segmento (il 'pacchetto' cui ci riferiamo sempre), il quale contiene l'indirizzo sorgente

e destinazione, un checksum per veri�care la correttezza del contenuto, vari campi per le segnalazioni di servizio

(�ag-bits, etc. . . ) e in�ne i dati.

Il funzionamento del protocollo TCP è illustrabile tramite lo schema di una macchina stati �niti (v. �gura 1.1)

caratterizzato da due eventi principali: il TWH (three way handshake, v. par 1.2.1), che consiste in un triplice

scambio di messaggi (Client: SYN, Server: SYN+ACK, Client: ACK) facente da preambolo per l'inizio della

connessione, e la chiusura unidirezionale e indipendente delle due direzioni (Client: FIN, Server: ACK + eventuale

trasmissione + FIN, Client: ACK). Il TWH, in particolare, è in grado di resistere all'apertura contemporanea di

più connessioni nonché all'arrivo ravvicinato di due richieste di connessione (una delle quali è ritardata).

Inoltre, il TCP ha un meccanismo - regolato da diversi timer - in grado di far fronte a inconvenienti come un

deadlock dovuto alla perdita di un ACK (scade il persist timer), una connessione senza scambio di dati da troppo

13Ad esempio perché la rete ha perso o ritardato i pacchetti che doveva consegnare.


tempo (keep-alive timer), la presenza in rete di più incarnazioni di una stessa connessione logica (time wait), la

perdita di un segmento (RTO, Retransmission Time Out).

Un aspetto importante del TCP è il dimensionamento dell'RTO: esso viene calcolato mediante formule matem-

atiche all'interno delle quali fa bella mostra la stima del RTT (Round Trip Time), cioè del tempo che intercorre

tra l'invio di un pacchetto e la ricezione della sua conferma. Il parametro RTT è aleatorio, quindi dobbiamo

appoggiarci al calcolo di una media ponderata mobile (Exponential Weighted Moving Average) per ottenerne un

valore plausibile.

Col passare del tempo sono state emanate diverse raccomandazioni (RFC), descriventi ognuna una particolare

metodologia di calcolo dell'RTT; in �gura 1.7 vengono illustrate la RFC 793 e la più nuova e performante RFC

2988: la prima è più rudimentale, in quanto fa uso dei soli parametri eRTT (stima dell'RTT ad un certo istante)

e sRTT (misurazione del RTT), mentre la seconda è più ra�nata dato che tiene anche conto della variabilità

delle condizioni della rete (parametro vRTT).

Figura 1.7: Schema riassuntivo del calcolo dell’RTT

Per il calcolo di sRTT serve una particolare cautela in quanto potrebbero esservi ambiguità dovute alla perdita

di pacchetti (v. �g. 1.5); inoltre, il TCP mantiene una misurazione dell'sRTT alla volta (v. �g. 1.4). In�ne, se

per una certa trasmissione non si riceve risposta, l'RTO viene raddoppiato (Exponential back-o� ).

Il TCP impone che ogni segmento abbia un proprio numero di sequenza ed è in grado di gestire le situazioni in

cui arriva un pacchetto fuori sequenza, duplicato oppure ritardato (o addirittura ritardato duplicato!). Il ricevitore

che si aspetta il pacchetto X, ma che riceve Y 6= X, può reagire in diversi modi in base all'entità di Y e X:

• Y > X: memorizza il pacchetto futuro14 (Y) e continua a richiedere quello corrente (X), in modo da poter

saltare il pacchetto Y una volta ricevuti tutti quelli precedenti;

• Y < X: il calcolatore scarta il doppione.

Un problema più sottile è quello riguardante segmenti con stesso numero di sequenza, stessa intestazione ma

contenuto diverso: essi possono essere il frutto di un'anomalia dovuta al crash di uno dei due colloquianti e alla

ripresa del dialogo con numeri di sequenza tali da indurre in rete la contemporanea sopravvivenza di pacchetti della

vecchia e della nuova connessione con stesso SeqN. Questa eventualità può accadere sia che ad ogni connessione

si scelga un ISN (Initial Sequence Number) �sso a un valore di default, sia che tale parametro venga calibrato

mediante un contatore (convenzione scelta del TCP). Per stare dalla parte del sicuro e non avere più dubbi il

TCP sceglie, conseguentemente al veri�carsi di un evento che ha interrotto il dialogo, di inibire qualsiasi ulteriore

tentativo di connessione per un tempo pari a MSL (TCP quiet-time).

14Se esso sta nella sua finestra.

Capitolo 2

Il protocollo TCP: controllo del flusso

2.1 Generalità

La velocità del trasmettitore potrebbe, in generale, essere molto diversa da quella del ricevitore, ma nonper questo uno dei due colloquianti ha licenza di saturare l’altro: per tal motivo si utilizza un meccanismoa finestra scorrevole. Il corretto dimensionamento della finestra deve tuttavia tenere conto - oltre che dellavelocità della rete - anche delle velocità d’elaborazione di trasmettitore e ricevitore, nonché della quantitàdi memoria posseduta da ciascuno di essi. Questo problema potrà sembrare anche banale, ma non lo èaffatto: il trasmettitore, a priori, non sa proprio un bel niente sul ricevitore e l’aleatorietà della congestionein rete non aiuta a prendere delle decisioni senza uno straccio d’informazione. Per potersi conoscere, i duehost devono quindi potersi comunicare l’un l’altro le dimensioni della memoria di ricezione: per questomotivo, nell’intestazione del pacchetto TCP, è contenuto il campo Advertised Window (AW).

2.2 Meccanismo a finestra scorrevole

La dimensione della finestra viene messa appunto dinamicamente: non ha infatti senso una finestra didimensione fissa, dovendo noi obbligatoriamente adeguarci di volta in volta alle situazioni del momento.Per poter dimensionare la finestra, abbiamo bisogno di:

• dati provenienti dal ricevitore (parametro AW);

• dati sulla congestione della rete (parametro CW, Congestion Window, ricavati tramite una stimaeffettuata dal TCP.

Figura 2.1: Il meccanismo a finestra fra segmenti ricevuti e segmenti non trasmessi.

La dimensione della finestra1 è pari al massimo tra AW e CW:

W = max(AW, CW)

Mettiamo ora che un ipotetico trasmettitore sia molto più lento di un ricevitore, che quindi vienesaturato: una volta che il buffer di ricezione si riempie, AW va a 0 e il trasmettitore blocca l’invio di dati.La ripresa della trasmissione avviene quando il processo ricevente legge dal buffer e spedisce un AW > 0.Questo meccanismo nasconde però un’insidia: se

1La dimensione della finestra può essere data in byte o in segmenti: noi preferiremo generalmente questa seconda scelta, in-dicando con w la finestra in byte e W la finestra in segmenti. Si noti che si ha w = MSS ·W, dove MSS è il Maximum SegmentSize.

17

18 CAPITOLO 2. IL PROTOCOLLO TCP: CONTROLLO DEL FLUSSO

• il trasmittente invia messaggi fino alla ricezione di AW = 0 e, a quel punto, sospende l’invio,

• il ricevitore non ha nulla da dire e quindi non trasmette nulla,

allora la finestra non verrà mai sbloccata perché il ricevitore non riesce a spedire alcun messaggio conAW > 0. Siamo in pieno deadlock; per questo il TCP permette che sia sempre possibile inviare un segmentodi 1 byte anche se AW = 0: dal momento che l’Advertised Window diventa pari a zero, infatti, parte il persisttimer allo scadere del quale si invia un segmento di un byte (SeqN = X + 1, dove X è il numero di sequenzadell’ultimo pacchetto correttamente trasmesso) avente lo scopo di sbloccare la finestra. Se poi il ricevitorerisponde con ACK = X + 2 e AW > 0, la trasmissione potrà continuare; in caso contrario, se cioè il bufferè invece ancora irrimediabilmente pieno, verrà spedito ACK = X + 1 e AW = 0, così che il persist timer,che questa volta avrà durata doppia (PT′ = 2PT), ricomincerà a contare.

2.2.1 Silly Window Syndrome

Il meccanismo descritto nel paragrafo 2.2 va bene fino a un certo punto: se non arrivano altri ACK,la finestra avrà sempre dimensione 1 e la trasmissione sarà lentissima. Stesso risultato abbiamo se l’ap-plicazione è lenta ad accettare i dati e legge un byte alla volta, comunicando una dimensione di finestrasempre troppo piccola. Quest’ultima evenienza prende il nome di silly window syndrome (abbreviato inSWS):

• il buffer di ricezione è pieno (AW = 0);

• l’applicazione (del ricevitore) legge un byte, libera altrettanto spazio dal buffer e trasmette AW = 1;

• il trasmettitore riceve tale indicazione e, non potendo far altro, manda un solo byte;

• il buffer di ricezione si riempie di nuovo e siamo daccapo.

In questa spiacevole situazione inviamo un carattere alla volta e AW continua ad oscillare tra 0 e 1;fortunatamente anche quest’inconveniente è risolvibile, grazie all’algoritmo di Nagle (v. paragrafo 2.2.2).

2.2.2 Algoritmo di Nagle

Quando siamo in deadlock per colpa della SWS (paragrafo 2.2.1) bisogna trovare il modo di aumentarela dimensione del messaggio (dev’essere più grande di 1 byte, cioè di un ’tinygram’, come si dice in gergo):è infatti stupido inviare un datagrammetto con 90% header e 10% dati; ciò si può realizzare forzando iltrasmettitore a inviare un nuovo segmento se e solo se è vera una delle seguenti condizioni2:

• il segmento ha dimensioni pari a MSS;

• il segmento è di dimensioni pari almeno alla metà del valore di AW (se proprio non riesco ad inviartitutto, ti invio almeno metà di quello che potresti);

• non vi sono ACK pendenti ed è possibile trasmettere tutto ciò che è in attesa nel buffer di trasmis-sione.

2Wikipedia spiega lo stesso problema con altre parole e aiuta a fare chiarezza.

Nel caso in cui il processo di scrittura dei dati nel bu�er TCP del mittente sia molto lento, il protocollo spedirà una serie di pacchetticontenti una quantità di dati molto bassa, con un uso ine�ciente del canale (è infatti molto meglio spedire un solo pacchetto con nbyte di dati, per il quale bisogna pagare il peso di un solo header, che spedire n pacchetti contenenti solo un byte di dati, per ognunodei quali bisogna pagare il peso di un header, un rapporto di 1/n contro n/n = 1). La soluzione a questo problema consiste neltrattenere i dati nel bu�er allo scopo di spedirli in un unico segmento. Tuttavia un'attesa troppo lunga potrebbe causare dei ritarditroppo grandi nella trasmissione. Un'ottima soluzione a questo problema è fornita dall'algoritmo di Nagle, secondo il quale i datidevono essere accumulati nel bu�er per poi venire spediti in un unico blocco alla ricezione dell'ACK dell'ultimo pacchetto trasmessoo quando si raggiunge la massima dimensione �ssata per un segmento (MSS). Questo semplicissimo algoritmo riesce a risolvereil problema tenendo anche conto della velocità di trasmissione dei pacchetti: se questa è più lenta della scrittura dei messaggi (ilmittente riesce ad accumulare una notevole quantità di dati nel bu�er prima dell'arrivo del riscontro) vengono creati pacchetti conil massimo rapporto dati-header, sfruttando al meglio le risorse del canale. Se invece la rete è più veloce, i pacchetti risulterannopiù piccoli, assicureranno una certa continuità nella trasmissione e verrà garantito comunque un utilizzo più e�ciente delle risorse delcanale che nel caso in cui l'algoritmo non venga utilizzato.

2.3. CONTROLLO DI CONGESTIONE 19

L’effetto dell’algoritmo di Nagle è che si può avere un solo segmento pendente per il quale non si èricevuto l’ACK; di conseguenza, più veloci arrivano gli ACK e più velocemente si trasmette. L’effetto col-laterale, invece, è quello che si tende a ritardare i dati nel buffer di trasmissione e, per alcune applicazioni,questo potrebbe essere non accettabile: di conseguenza l’algoritmo di Nagle è disabilitabile.

2.3 Controllo di congestione

Come abbiamo avuto modo di vedere, W è limitato superiormente da AW e CW; rimane da chiarirecome quest’ultimo parametro venga determinato. Ebbene, il TCP cerca di adattare la dimensione del-la finestra in funzione delle condizioni di congestione della rete, aumentandola quando si ricevonocorrettamente gli ACK e restringendola quando si verificano perdite: da qui l’esistenza del parametroCW.

Avendo a disposizione una banda B (misurata in byte/s), il massimo throughput si ottiene quando ilprotocollo a finestra non limita la velocità di scambio dei dati, cioè quando nel famoso schema con le dueaste verticali rappresentanti client e server non vi sono buchi e ogni momento diventa un istante validoper trasmettere dati nuovi. Se siamo in questo caso la finestra dev’essere più grande di:

wid ≥ RTT · B→ In byte

Wid =wid

MSS→ In segmenti

Massimo throughput→ S =w

RTT(byte/sec) =

WRTT

(segmenti/sec)

In questo caso si utilizza il massimo della capacità disponibile; gli altri due casi, quelli cioè in cui lafinestra è più piccola o più grande di wid, vanno peggio perché

• se la finestra è più piccola parte della banda viene sprecata per l’attesa di arrivo delle conferme;

• se la finestra è più grande il vero handicap viene dalla rete, che non è in grado di accettare per interoil flusso di dati nelle parti intermedie a velocità minore: in questo caso è infatti necessario accodarenei router intermedi, cosa che può generare perdite e ritardi.

Figura 2.2: La questione delle capacità e l’adattività del controllo di flusso

Esaminiamo per esempio la figura 2.2; in essa si illustra come il flusso sia in grado di adattarsi allacapacità e alla banda della rete: se facciamo l’assunzione che vi siano parti di rete ad elevata capacità edaltre a banda più ristretta (rispettivamente rappresentate da tubi più larghi e più stretti), si nota come iltempo necessario a trasmettere pacchetti di dimensione fissata sia molto diverso da zona a zona. Il collodi bottiglia rappresentato dal primo tratto di linea avente banda (stretta) pari B ha l’effetto di rallentare latrasmissione complessiva di dati: giunti alla parte di rete (veloce) del ricevitore, infatti, i pacchetti sono fra


loro temporalmente molto più distanziati rispetto a quanto lo fossero in partenza. Il ritorno, immaginandoche la situazione sia simmetrica rispetto all’andata, non ritarda ulteriormente i pacchetti essendo questidei piccoli ACK inviati ad una frequenza ‘sfrondata’ dalla rete d’andata e quindi più che gestibili. Ilprotocollo a finestra, come abbiamo detto, permette al trasmettitore di inviare dati solo dal momentoche riceve le necessarie conferme: se esse giungono con la frequenza indicata in figura, la successivatrasmissione farà sì che il trasmettitore già ‘ab ovo’ invii pacchetti ad una velocità accordata sulla base diquanto possa sopportare la rete.

Tornando alla questione di partenza, come dimensioniamo CW considerando quanto detto e il fattoche la banda disponibile B può cambiare durante la connessione? A questo proposito, fatte le ipotesi chetrasmettitore e ricevitore siano correttamente configurati, che non vi siano problemi di SWS (vedi para-grafo 2.2.1), che i buffer di trasmissione e ricezione siano abbastanza grandi e che AW >> CW (cosicché èCW a ‘comandare’ nel dimensionamento della finestra), sono definite due fasi che corrispondono a diversedinamiche di CW:

• slow start (SS): all’inizio della trasmissione W è3 ≤ 2 e, per ogni ACK ricevuto senza scadenza diRTO si effettua

W = W + 1

L’effetto netto è che, ad ogni tornata, la finestra raddoppia4 (v. figura 2.3). Lo SS termina quando

Figura 2.3: Meccanismo di Slow Start

si verifica congestione (non ritorna un ACK in tempo) oppure quando superiamo la cosiddetta SlowStart Threshold (SSTHR)5, che all’apertura della connessione è fissata ad un valore arbitrariamentealto ma che è anche in grado di cambiare dinamicamente durante la trasmissione dati. In SS siipotizza che la situazione di rete, a finestra ancora relativamente piccola, sia abbastanza stazionaria;l’evoluzione di W, com’è facile intuire, avviene per tempi multipli di RTT (sono gli ACK a dettare ilritmo). La durata di tale fase dipende chiaramente dalla SSTHR ed è pari a:

TSS = RTT · log2 SSTHR

• congestion avoidance (CA): dopo la crescita esponenziale della fase di SS, con la congestion avoidancepassiamo ad una crescita lineare onde evitare di esagerare e incappare nella perdita di pacchetti. Lafinestra w viene incrementata di un MSS per ogni RTT (o, se si preferisce, ogni RTT W aumenta diun segmento): ad ogni ACK, quindi, si ha

W = W +1

W

Quindi, ad esempio, se la finestra al ’passo’6 n è pari a 10 segmenti (W(n) = 10), avvenuta latrasmissione (e se tutto è andato bene) vengono ricevuti 10 ACK e la nuova finestra W(n + 1) diventa7

W(n) + 10 · 110

= W(n) + 1.

2.4. ALCUNE DEFINIZIONI ED EVOLUZIONE DELLA CW 21

Figura 2.4: Distinzione fra SS e CA

2.4 Alcune definizioni ed evoluzione della CW

Loss Window (LW): quando scade un RTO il trasmettitore ritiene perso un segmento, che quindi de-v’essere ritrasmesso. Si pone quindi CW ≤ LW (tipicamente LW = 1).

Flightsize: quantità di byte trasmessi ma non confermati (in parole povere è ciò che è in giro per larete). Non è necessariamente uguale a W e dipende da dove si e arrivati nella trasmissione di una finestra.

Dopo aver definito queste quantità, chiediamoci: cosa accade se durante la normale evoluzione dellaCW, fra slow start e congestion avoidance, scade il Retransmission Time Out8? In tal caso il protocollo reagisceripartendo dalla SS (W = 1) e imponendo che la SSTHR diventi pari al flight-size/2 (o, se quest’ultimaquantità è più piccola di due segmenti, a 2).

Si noti che, grazie a questo meccanismo, la rete cerca di adattarsi allo stato della congestione purmantenendo un atteggiamento greedy (avido): finché si può, infatti, il TCP cerca di allargare semprepiù la sua finestra. Non c’è però pericolo che questo consegni l’intera rete in mano ad un unico hostvisto che tutti quanti condividono la stessa politica: infatti il meccanismo delle perdite ha lo scopo diinibire colui che sovraccarica il mezzo trasmissivo, ridimensionando la sua voracità; piuttosto, il risvolto

3Quindi, in byte, w ≤ 2MSS.4Quindi è una slow start per modo di dire: in realtà la finestra cresce molto di più qui che in congestion avoidance.5Manterremo la convenzione di scrivere ssthr in byte e SSTHR in segmenti.6Non possiamo parlare di istanti perché gli ACK e le trasmissioni non avvengono tutte nello stesso momento, quindi approssimer-

emo il cosiddetto passo con un lasso di tempo poco più grande di RTT, quello - cioè - che permette ad un numero di segmenti pari aquello contenuto nella finestra di essere trasmessi e confermati.

7In realtà, per essere più precisi, questa relazione dovrebbe essere scritta come approssimazione visto che l’incremento di Wavviene ad ogni ACK e non solo alla fine della tornata (cioè ad ogni ’passo’ e l’altro, v. nota precedente).ESEMPIO: si ipotizzi W = CW = 4: vengono trasmessi 4 segmenti e, ricevuto il primo ACK risulta,

W = (4 + 1)/4 = 4, 25

Ricevuto il secondo ACK abbiamoW = (4, 25 + 1)/4, 25 = 4, 49

Ricevuto il quarto ACK, ossia terminato il RTT dell’intera finestra (ovvero il passo di cui parlavamo prima) W = 4, 92 6= 5! Si notiquindi che non si ha esattamente W = W + 1 dopo la ricezione di tutti gli ACK della finestra. Di conseguenza, la crescita di Wnon è esattamente lineare, ma noi per semplicità la considereremo tale.

8Tipicamente questo evento viene interpretato dal TCP come indice di congestionamento della rete visto che, con buona stimadel RTT, il time out scaduto è praticamente sempre dovuto alla perdita del segmento.


Figura 2.5: Un esempio d’evoluzione della finestra

positivo di quest’indole è quello di permettere ai colloquianti di occupare l’eventuale banda rilasciata daun calcolatore che ha abbandonato la conversazione: in questo modo, la banda è teoricamente sempresfruttata al meglio.

2.5 Alcune approssimazioni

Sia TSS la durata della fase di slow-start e TCA quella della fase di congestion avoidance. Se la rete èabbastanza stabile si ha che:

TSS << TCA

Questo significa che passiamo molto più tempo in CA piuttosto che in SS e questo è un bene vistoche, in ultima analisi, la quantità di dati trasmessi è pari all’integrale della curva presente nel graficofinestra/tempo e, chiaramente, l’area che si trova sotto la curva che evolve in CA è maggiore di quellasotto la curva in zona di SS. Se l’ipotesi TSS << TCA è vera, allora possiamo trascurare la fase di SS eimmaginare un andamento perennemente in CA, come in figura 2.6.

Figura 2.6: Effetto dell’approssimazione TSS << TCA

2.5. ALCUNE APPROSSIMAZIONI 23

L’andamento della finestra in Congestion Avoidance oscilla fra incremento additivo e decremento moltiplica-tivo: se r è la quantità di dati inviata dal trasmettitore

• additive-increase: la finestra cresce in maniera additiva. Al passo i-esimo si ha:

r(ti+1) = r(ti) + c con c << rmax

• multiplicative-decrease: la finestra decresce in maniera moltiplicativa. Se si ha una situazione dicongestione al passo i-esimo si ha:

r(ti+1) = a · r(ti) con a < 1

Perché tutte queste definizioni? Il punto cui vogliamo arrivare è dimostrare che il TCP permette un’e-qua distribuzione della banda disponibile: questo significa che se un certo numero di colloquianti (noi persemplicità ne considereremo due) condividono una certa banda, a regime finiranno per avere più o menotutti la stessa porzione di essa.

2.5.1 Un esempio

Figura 2.7: Condivisione della risorsa

Si faccia riferimento alla figura 2.7: abbiamo due connessioni che si ritrovano a condividere la stessabanda. Siccome entrambi i calcolatori (r1 e r2 sul grafico: gli assi rappresentano la banda destinataa ciascuno di essi) adottano il tanto decantato approccio greedy, tenteranno di accaparrarsi quante piùrisorse possibili. Così facendo arriverà inevitabilmente il momento in cui si dovrà sbattere il muso control’impossibilità di congestionare troppo la rete: prendiamo per esempio r2 che, per ipotesi, parte con unmaggior sfruttamento della banda. Dopo un appagante incremento additivo, la freccia verde si scontracontro il limite (linea scura) e si ha in decremento moltiplicativo (freccia rossa). Il giro successivo, r2 nonpotrà occupare così tanta banda come l’ultima volta perché, nel frattempo r1 gli avrà rosicchiato un po’ dirisorse da sotto i piedi. Nonostante questo, r2 ha un incremento additivo che lo riporta (quasi) ai livellidi un tempo; anche stavolta, tuttavia, scatta un RTO a causa della troppa avidità del nostro host e cosìsi ha un’ulteriore freccia rossa corrispondente a un decremento moltiplicativo. Questa tendenza continuafino a quando la freccia rossa e la freccia verde hanno la stessa pendenza, pari tra l’altro alla bisettricedel nostro quadrante: giunti lì, a meno di inconvenienti particolari, i due host avranno decrementi edincrementi simili e ciò porterà ad avere, a regime, una sostanziale equipartizione della banda (il punto di


intersezione fra la bisettrice e la retta ad essa perpendicolare è quello di massimo equilibrio fra le risorsedestinate ai due calcolatori). Si noti che tutto questo è reso possibile dall’atteggiamento greedy, avido eassetato di banda, imposto dal TCP: se così non fosse non riusciremmo ad avere uno sfruttamento cosìintenso e sistematico della capacità del nostro canale. Inoltre, se uno dei due host dovesse andarsene,quello rimanente non approfitterebbe subito della banda liberatasi e l’efficienza sarebbe piuttosto scarsa.

2.6 Altri aspetti del protocollo: algoritmi migliorativi

Una cosa che è importante sottolineare è che la politica dei delayed ACK (non inviare gli ACK sem-pre, ma ogni K > 1 corrette ricezioni) può portare a degli squilibri. Se prendiamo in considerazionel’esempio nel paragrafo 2.5.1 e facciamo l’ipotesi che uno dei due colloquianti invii un ACK ogni quattrosegmenti invece che ad ogni singolo datagramma, allora quest’ultimo calcolatore sarà indiscutibilmentedanneggiato perché, al contrario dell’altro contendente, non riuscirà a raggranellare banda al suo stessoritmo.

Preme inoltre sottolineare che l’incremento di CW è funzione del round-trip time; due connessioni chesperimentano diversi RTT aumentano in modo diverso le proprie finestre e si tende a favorire connessionicon RTT brevi su connessioni con RTT lunghi.

Quando poi un segmento viene perso, il ricevitore riceve uno o più segmenti fuori sequenza: se ciòavviene, il protocollo TCP (quello nudo e crudo, senza gli algoritmi che vedremo fra poco) è costretto adinviare un ACK duplicato9 per ogni segmento fuori ordine. La generazione di ACK duplicati dovuti allaperdita di un segmento è un evento che può essere utilizzato come indicazione di congestione unitamenteal time-out. Sono quindi stati proposti ulteriori algoritmi per sfruttare al meglio questa situazione: diquesti noi tratteremo il fast recovery (paragrafo 2.6.1) e il fast retransmit (paragrafo 2.6.2).

2.6.1 Fast recovery

Questo algoritmo entra in funzione quando avviene il caso di triple duplicate ACK (tre ACK duplicati):se il trasmettitore riceve infatti 4 ACK con uguale acknowledge number allora si ritrasmette il segmentoavente come numero di sequenza quello indicato dall’ackN duplicato. E poi che si fa? Si potrebberipartire dall’inizio della slow start, ma quella di far ricrollare la finestra allo stadio embrionale non è unascelta furbissima: il fatto che il ricevitore ci stia rispondendo, infatti, è sintomo che i pacchetti stannoeffettivamente giungendo a destinazione e che quindi vi è abbastanza reattività da parte della rete (e nonvi è perciò una situazione esageratamente congestionata). Inoltre, potrà pure capitare che ogni tanto siperde qualche pacchetto!10 Considerando quindi il triplo ACK duplicato come evento ’meno grave’ di unRTO effettivamente scaduto, si preferisce agire ritrasmettendo il solo segmento mancante e continuandola fase di congestion avoidance.

Ecco i passi dell’algoritmo (per visionare alcuni esempi si faccia riferimento alle figure 2.8 e 2.9:

• si riduce la soglia di CW a SSTHR = max(Flightsize/2, 2) o, se si preferisce questa quantità in byte,a ssthr = max(Flightsize/2, 2MSS): questo passo serve per riadattarci alle condizioni di carico dellarete;

• si gonfia (provvisoriamente) la finestra W (window inflation) aumentandone istantaneamente la di-mensione di tre pacchetti: W = SSTHR + 3 (o, come al solito, w = ssthr + 3MSS in byte). Cosìfacendo si tiene conto del fatto che almeno 3 segmenti successivi al mancante sono stati ricevuti inquando sono partiti gli ACK duplicati;

• si continua la trasmissione e, se la dimensione di W lo permette, si trasmettono ulteriori segmenti;

• ad ogni ulteriore ACK duplicato ricevuto si pone W = W + 1;

• quando arriva l’ACK per il pacchetto perduto finisce la fase di FR e si riparte con congestion avoidanceponendo W = SSTHR (la finestra viene sgonfiata).

9Che si riferisce all’ultimo segmento ricevuto correttamente.10Suvvia!

2.6. ALTRI ASPETTI DEL PROTOCOLLO: ALGORITMI MIGLIORATIVI 25

Figura 2.8: L’algoritmo di fast recovery

Figura 2.9: L’algoritmo di fast recovery (2)

Il TCP standard, messo di fronte a un’eventualità come quella illustrata nell’esempio in figura 2.8,sarebbe impazzito, in quanto avremmo dovuto per forza attendere lo scadere dei time out prima diripartire. Anche solo due pacchetti persi in breve tempo avrebbero infatti creato una situazione di stallo eavrebbero fatto ripartire il tutto dalla slow start, con un conseguente crollo della finestra. Non è però tutto


oro quel che luccica: a volte, infatti, il fast recovery può addirittura essere dannoso e peggiorativo!

2.6.2 Fast retransmit

Il fast retransmit (una specie di fast recovery semplificato11), consiste nel dimezzare la finestra e spedireimmediatamente, senza aspettare l’RTO come invece accadrebbe nel TCP classico, il pacchetto del qualesi è ricevuta la richiesta duplicata (tripla, come da programma).

Consideriamo infatti la seguente casistica:

• 12 segmenti ricevuti, riconosciuti e confermati;

• segmenti 13 e 16 perduti.

In figura 2.10 si mostra come il TCP standard (SS+CA) e il TCP ’Tahoe’12 (SS+CA+Fast Retransmit)avrebbero agito e si nota chiaramente come quest’ultimo sia più efficiente.

Figura 2.10: Il TCP classico e il Tahoe (cioè TCP + Fast Rec.) a confronto

Qual è il problema del Tahoe? Ebbene, il vantaggio ottenuto è molto piccolo (se non nullo) perché ildimezzamento della finestra blocca la trasmissione a causa delle perdite multiple.

11O magari è il fast recovery ad essere una versione più evoluta del fast retransmit: la sostanza però è quella. Mediamente il fastrecovery funziona meglio, ma in alcuni casi potrebbe non essere così, quindi ha senso vedere questi due algoritmi separatamente.

12Da Wikipedia:TCP Tahoe prevede che ogni qual volta si veri�chi un evento perdita di qualsiasi tipo, la �nestra di congestione venga dimezzata

e il nuovo valore memorizzato in una variabile soglia. Fatto questo la trasmissione dei dati ricomincia impostando il valore inizialedella �nestra di congestione corrente pari a MSS (massima dimensione di un segmento TCP). Si ha quindi una 'ripartenza lenta', lacrescita avverrà lentamente ma in maniera esponenziale �no a raggiungere il valore di soglia prima determinato [è la SS]. Oltre questovalore la crescita avviene linearmente [CA] �no a quando non si veri�ca nuovamente un evento perdita e l'algoritmo viene rieseguito.La crescita esponenziale �no al livello di soglia avviene poiché si ritiene che all'inizio di ogni trasferimento il canale trasmissivo sia piùlibero, e quindi si cerca di inviare all'inizio i pacchetti più grossi. Una volta raggiunto il livello di soglia, la crescita avviene lentamenteper cercare di raggiungere il livello di congestione il più lentamente possibile.

2.6. ALTRI ASPETTI DEL PROTOCOLLO: ALGORITMI MIGLIORATIVI 27

2.6.3 Reno e New Reno

Nel caso illustrato nel paragrafo 2.6.1 il cosiddetto TCP ’Reno’13 (SS+CA+Fast Recovery) non sarebbeandato molto meglio (v. figura 2.11). Il ’New Reno’14, invece, avrebbe avuto delle performance migliori (sifaccia nuovamente riferimento alla figura 2.11).

Figura 2.11: I protocolli TCP Reno e TCP New Reno a confronto

Come si osserva facilmente, il TCP Reno si infogna subito (segmenti pendenti 5, W = 5 → non si puòtrasmettere altro finché non riceviamo ACK 13: dopodiché si esce dal fast recovery e si riparte con finestra2: il trasmettitore è nuovamente bloccato ed è costretto ad attendere l’RTO di 16, allo scadere del quale siritrasmette con finestra a 1. . . Oltre al danno pure la beffa!): terminare il fast recovery troppo presto (cioèad ackN=15) è infatti prematuro.

Il New Reno fa tesoro di questa esperienza e reagisce meglio, mantenendo la finestra gonfiata per unpo’ più di tempo, quel che basta per scavalcare i pacchetti corretti successivi a quello sbagliato e poterriprendere la numerazione in santa pace, senza aspettare lo scadere degli RTO. La fase di recupero iniziaall’istante (che chiameremo T0) di ricezione del quarto duplicato: giunti lì memorizziamo infatti seqN(T0)

13Ancora una volta Wikipedia ci aiuta con una sua spiegazione:TCP Reno [...] in caso di perdita dovuta al timeout del timer, applica l'algoritmo di Tahoe, poiché si assume che la rete sia

talmente congestionata da non essere in grado di far passare nessun altro pacchetto e che quindi sia meglio far ripartire la trasmissioneimpostando la �nestra corrente al valore minimo di 1 MSS. Quando invece l'evento perdita è generato dalla ricezione di 3 ACKduplicati, il TCP Reno assume che la rete sia ancora in grado di trasferire qualcosa. Il valore soglia viene impostato alla metà delvalore della �nestra di congestione al momento della ricezione di tre ACK duplicati e la trasmissione riparte impostando il valoredi �nestra corrente pari al valore di soglia e proseguendo nell'invio incrementando di MSS, ad ogni RTT, il valore della �nestra dicongestione.

14La solita Wikipedia:Il TCP Reno risolve in parte il problema di perdite non dovute a congestione solo quando le perdite non sono fortemente correlate

tra loro, cioè quando si perde al massimo un pacchetto all'interno di ogni �nestra. Questo comportamento è problematico nellesituazioni in cui si perdono interi burst di pacchetti (situazione frequente ad esempio nei collegamenti wireless). TCP New Reno

cerca di aggirare il problema basandosi sul sistema degli ACK parziali. Vengono considerati ACK parziali gli ACK che riscontranopacchetti intermedi, e non gli ultimi pacchetti che necessiterebbero riscontro, dopo che è stata già iniziata la fase di Fast Retransmitin seguito all'arrivo di tre ACK duplicati. Quando uno di questi ACK si presenta durante una fase di Fast Retransmit (cioè in seguitoalla ricezione di 3 ACK duplicati), TCP New Reno si mantiene in Fast Retransmit continuando a inviare i pacchetti via via richiesti�nché non viene riscontrato l'ultimo pacchetto inviato.


= 17. Questo numero indica infatti il seqN dell’ultimo pacchetto che si presume sia stato correttamentericevuto dal ricevitore: dopo la ripetizione dei 3 pacchetti aventi seqN = 13 esso rappresenterà quindi laprima informazione ’buona’ disponibile dopo i 3 duplicati. Il numero memorizzato è quindi utile perché,proprio per i motivi poco fa indicati, l’algoritmo prevede che si esca dalla fase di Fast Recovery quando siriceve ackN > seqN(T0). Se dopo la spedizione del segmento perduto (il 13simo) tutta la finestra è stataricevuta correttamente allora arriverà ackN = 18 (si esce dal Fast Recovery) mentre, se sono stati perdutialtri segmenti della finestra, ackN < 18 (ACK parziale, che re-inizializza RTO).

2.7 In sintesi

Per poter comunicare in maniera e�ciente, due host devono avere almeno una vaga idea della rispettiva

velocità di elaborazione, della rapidità con la quale le proprie applicazioni riescono ad 'assorbire i dati' e un indice

di congestione della rete; esistono, a questo proposito, due importanti parametri che vengono continuamente

scambiati durante la conversazione: CW, dimensionato in base alla congestione della rete, e AW, che riguarda

la velocità del ricevitore. La dimensione della �nestra W di conversazione è sempre pari al massimo fra AW e

CW. Combinando le informazioni sul congestionamento della rete e sulla capacità dei comunicanti, il TCP riesce

ad uniformare la velocità di trasmissione dei dati, accordando il ritmo d'invio dei messaggi fra spezzoni di rete a

velocità disomogenea, quand'anche la banda e la capacità del collegamento variassero in maniera molto dinamica

e disomogenea nel tempo.

Esistono tuttavia alcune situazioni pericolose assolutamente da evitare:

• il trasmettitore invia messaggi, ma riceve AW = 0 e nulla più → il trasmettitore è bloccato (deadlock).

SOLUZIONE: il TCP permette sempre l'invio, allo scadere del persist timer, di un segmento piccino picciò

(1 byte) anche se AW = 0. Se, fatto questo, il bu�er risultasse essere ancora pieno, il persist timer viene

raddoppiato;

• se l'applicazione del ricevitore (o del trasmettitore) è lenta a processare i pacchetti e legge (o scrive) una

misera manciata di byte alla volta (caso peggiore: un solo byte alla volta), il bu�er si svuoterà molto

lentamente e verranno inviati pacchetti con AW = 1 (sempre nel caso peggiore). Colui che sta all'altro

capo della trasmissione non potrà fare altro che inviare un solo byte, con la conseguenza che il bu�er di

ricezione si riempirà di nuovo e saremo daccapo. Questo è il caso della SWS (Silly Window Syndrome)

e porta alla trasmissione di pacchetti costituiti per la stragrande maggioranza di informazioni di servizio

(header) e da pochissimi dati. SOLUZIONE: algoritmo di Nagle → si permette l'invio di dati solo se (1)

il segmento ha dimensioni pari a MSS, (2) il segmento è di dimensioni pari almeno alla metà del valore di

AW, (3) non vi sono ACK pendenti. Il risvolto negativo sta nel fatto che la trasmissione perde reattività:

per questo l'Algoritmo di Nagle è disabilitabile.

Il TCP cerca di adattare il parametro CW in base alla percezione che ha sulla congestione della rete, incre-

mentandolo quando si ricevono gli ACK e ridimensionandolo quando si veri�cano perdite. Trascurando per un

attimo il problema della SWS, immaginando che AW � CW e che i calcolatori comunicanti abbiano sempre

qualcosa da trasmettere e supponendo in�ne (per semplicità) che l'aggiornamento di CW avvenga al termine di

ogni �nestra (cioè al termine di ogni RTT), il tipico andamento del parametro CW si destreggia fra due di�erenti

fasi:

• SS (Slow Start → crescita della �nestra: esponenziale): in questa fase la �nestra raddoppia ad ogni RTT15,

dato che per ogni ACK ricevuto si ha W = CW = W + 1. La SS dura �nché CW non raggiunge la SSTHR(Slow Start THReshold) e quindi possiamo supporre che permanga per log2 SSTHR round trip times;

• CC (Congestion Avoidance → crescita della �nestra: (sub)lineare): in questa fase si cerca di non esagerare

con l'incremento della �nestra, onde evitare di saturare il collegamento; la crescita è infatti di W = W +1

Wad ogni ACK ricevuto (e di circa un segmento per ogni RTT16)

Se a questo punto scade l'RTO, il TCP reagisce ripartendo dalla SS (W = 1) e imponendo che la SSTHR diventi

pari al �ight-size/2 (o, se quest'ultima quantità è più piccola di due segmenti, a 2).

15L’aggettivo slow è fortemente fuorviante: esso si riferisce alla dimensione di W, inferiore a quella che si ha in CA, e non al suoritmo di crescita, che invece è molto sostenuto.

16In realtà la crescita è sublineare, v. par. 2.3.

2.7. IN SINTESI 29

A questo punto appare chiaro come la caratteristica fondante del protocollo sia la sua avidità (protocollo

greedy : l'unico evento che fa calare CW è la perdita di un pacchetto, mentre di norma questo parametro viene

solo incrementato): grazie alla richiesta sempre maggiore di banda da parte di tutti coloro che sono in rete, l'even-

tuale capacità liberatasi in seguito all'abbandono della conversazione da parte di qualcuno viene immediatamente

sfruttata. Altra conseguenza di questo protocollo è quella di permettere un'equa condivisione della banda (v. par.

2.5) a regime.

La pura alternanza di SS e CW non risulta essere un algoritmo su�cientemente e�cace (è anzi troppo severo:

far crollare la �nestra a 1 è una punizione eccessiva se la linea non è inverosimilmente congestionata). Per questo

esistono diverse versioni in grado di migliorare questa dinamica: tutte quante scattano al triplo ACK duplicato

(triple duplicated ACK e sono

• fast retransmit: si ridimensiona immediatamente la SSTHR (la si pone a�ightsize

2) nonché la �nestra17

e si spedisce immediatamente, senza attendere lo scadere dell'RTO, il pacchetto del quale si è ricevuta la

richiesta duplicata;

• fast recovery : come il fast retransmit, solo che �no a quando non arriva la conferma del pacchetto perso si

gon�a la �nestra e la si fa diventare pari a W = SSTHR + 3, +1 per ogni eventuale altro ACK duplicato.

Dopodiché la �nestra viene posta pari a SSTHR e si ricomincia in CA;

• Reno: comprende fast retransmit + fast recovery ;

• New Reno: è come il Reno solo che la fase di FR/FR dura �no a quando non si riceve un ACK avente

numero di sequenza superiore a quello dell'ultimo pacchetto inviato correttamente prima dello scattare

dell'algoritmo18. Il gon�amento della �nestra avviene secondo la regola: W = SSTHR + 3 +1 per ogni

eventuale altro ACK duplicato, −1 per ogni ACK ricevuto correttamente. L'uscita dall'algoritmo va come

nel Reno.

17È sempre valida l’ipotesi che AW � CW quindi W = CW.18Quello, cioè, il cui numero di sequenza è stato salvato nella variabile recover quando sono arrivati i tre ACK duplicati

Capitolo 3

Modelli analitici per le prestazioni delTCP

3.1 Ricerca di modelli matematici

Le prestazioni del protocollo TCP vengono influenzate fondamentalmente dalla dinamica della fines-tra di trasmissione W (che viene regolata dal controllo di congestione e dal protocollo ARQ) nonché daiprocessi di ritardo e perdita di segmenti in rete (vedi capitolo ??). Un modello analitico del TCP deve de-scrivere questi processi fondamentali e, nello stesso tempo, riuscire a valutare le prestazioni del protocollo.Sembra una cosa banale, ma in realtà esistono diverse questioni delicate da affrontare, in quanto:

• gli eventi consistenti nella perdita di pacchetti sono aleatori (e non deterministici);

• la rete ha una natura dinamica ed è impossibile racchiudere in un solo modello tutte le possibilieventualità che si potrebbero presentare;

• è difficile tenere conto di tutta l’infrastruttura che si trova tra ricevitore e trasmettitore: tra i duecolloquianti, infatti, si trovano vari router - non necessariamente uguali - con code di lunghezzadiversa e prestazioni differenti;

• se siamo in congestion avoidance l’andamento della finestra è approssimativamente lineare e le cosevanno bene; se vogliamo considerare anche la slow start nonché le dinamiche dei protocolli piùevoluti (Tahoe, Reno, New Reno, etc. . . ), allora il problema si complica notevolmente;

• il RTT non è in generale un parametro costante;

• non valutiamo la possibilità che la banda venga occupata, durante il periodo che ci interessa, da altricalcolatori;

• etc. . .

Per questi ed altri motivi, di seguito studieremo alcune situazioni notevoli adeguatamente semplificate.

3.2 Throughput e goodput

Il throughput di una connessione TCP è la quantità totale di informazioni trasmesse nell’unità ditempo.

Il goodput, invece, è la quantità di informazioni trasmesse con successo nell’unità di tempo (senzacontare quindi i segmenti trasmessi con errore o duplicati).

Intuitivamente, si ha che:throughput ≥ goodput

Nei modelli TCP più comuni il tempo è logicamente diviso in unità di dimensione RTT: supporremo chein RTT venga trasmessa un’intera finestra e che, al termine di tale periodo, giungano tutte le conferme di

31

32 CAPITOLO 3. MODELLI ANALITICI PER LE PRESTAZIONI DEL TCP

ricezione1. Fatte queste ipotesi il throughput è semplicemente il numero di segmenti trasmessi per RTT:

S(t) =w(t)RTT

=W(t) ·MSS

RTT

Di seguito supporremo che il trasmettitore abbia infiniti dati da trasmettere (e che spedisca sempre seg-menti di dimensioni pari a MSS), che i buffer di trasmissione e ricezione non limitino il comportamentodel TCP (lo stato delle code nei router rimane approssimativamente costante e non si modifica in modosignificativo durante il periodo d’analisi) e - infine - che si lavori perennemente in congestion avoidance.

3.3 Modello periodico

Si tratta del modello più semplice: esso assume che

• si lavori in una situazione di equilibrio, con il TCP in congestion avoidance: questo comporta inoltreche, ad ogni perdita, la finestra si dimezzi (invece che ripartire da 1);

• si riceva un ACK per ogni segmento correttamente trasmesso;

• gli eventi di perdita siano periodici, in percentuale di p.

Fatte queste ipotesi, la finestra ha in funzione del tempo un andamento periodico a dente di sega (v.figura 3.1).

Figura 3.1: Modello periodico

Supponendo che ad ogni finestra (batch) vengano trasmessi W segmenti, lo stato di congestion avoidancefa sì che, al termine di essa, si riceva l’ACK che fa scattare W = W + 1. Se non si riceve l’ACK, invece, lafinestra viene dimezzata per effetto della congestione (vedi figura 3.2).

Figura 3.2: Modello periodico (2)

Sia ora N il numero di segmenti trasmessi in T (periodo che intercorre tra una perdita e l’altra). Seassumiamo che la perdita avvenga periodicamente allora possiamo dire che, se ad esempio la perdita è di

1A noi fa comodo pensare che le cose vadano così: in realtà i pacchetti non arrivano tutti contemporaneamente e, di conseguenza,la finestra si aggiorna non soltanto ad ogni RTT. Anche questa, pertanto, è un’approssimazione.

3.3. MODELLO PERIODICO 33

1 segmento su 100, all’interno di T avremo spedito 100 segmenti:

N =1p

Possiamo però dare un’espressione di N anche in funzione della finestra2:

N =W2 −1

∑i=0

W2

+ i =W2

4+

(W2− 1)(

W2

)2︸︷︷︸

serie del ’piccolo Gauss’

≈ W2

4+

W2

8=

3W2

8

Per capire a fondo questa espressione si tenga presente che la sommatoria ha quegli estremi visto che lafinestra, per ogni dente di sega, varia da W/2 a W (per un delta complessivo che va da 0 a W/2) e che il+i indica la crescita pari ad 1 della finestra per ogni RTT. Uguagliando le due espressioni di N si ottienefacilmente:

W =

√8

3p

Il throughput si calcola come rapporto fra:

• numero di pacchetti trasmessi = 1/p;

• tempo totale di trasmissione =W2

RTT.

Ed è quindi pari a:

S (p) =1/

p

RTTW2

=2/

pRTT

1W

=2/

pRTT

√3p8

=1

RTT

√3

2p

3.3.1 ACK ritardati

Facciamo ora l’ipotesi aggiuntiva che il ricevitore spedisca un ACK ogni b segmenti e non ogni seg-mento. In tal caso, se trasmettiamo una finestra W riceveremo non più W ACK, ma W/b ACK: questofarà sì che

• W = W + 1/b;

• W = W + 1 solo dopo b finestre trasmesse.

Il periodo T che intercorre tra una perdita e l’altra sarà quindi pari a:

T =Wb2

RTT

Si noti che questo tempo è b volte quello esaminato nel caso di ACK non ritardati. Possiamo quindi farecalcoli analoghi a quelli già visti nel paragrafo 3.3: il parametro N (segmenti spediti all’interno del dentedi sega) è pari a

N =W2 −1

∑i=0

W2

+ib

=bW2

4+

(bW2− 1)(

bW2

)2︸︷︷︸

Ancora il piccolo Gauss

≈ bW2

4+

bW2

8=

3bW2

8

Quindi, uguagliando nuovamente questa relazione con

N =1p

2Con la ’serie del piccolo Gauss’ (cit. Seccia) intendiamo:

k

∑i=0

k =k(k + 1)

2


si ha:

W =

√8

3bp

E quindi il throughput sarà:

S (p) =1/

p

RTTW2

b=

2/

pRTT

1bW

=2/

pb · RTT

√3pb

8=

1RTT

√3

2pb

3.4 Perdite aleatorie

Figura 3.3: Andamento della finestra con perdite aleatorie

Se complichiamo leggermente il modello, rimuovendo l’ipotesi che le perdite siano periodiche e ag-giungendo quella che siano aleatorie, allora già le cose si fanno più complicate! Supponiamo che latrasmissione avvenga ancora a batch (uno per RTT e di dimensioni pari alla finestra W) e che gli ACKsiano ritardati (uno ogni b pacchetti). Sia inoltre la probabilità di perdita indipendente da segmento asegmento e da batch a batch. In questo caso, com’è prevedibile, l’andamento a dente di sega non sussistepiù (v. figura 3.3).

Facciamo inoltre l’ipotesi che siano due gli eventi a determinare la contrazione di CW(t):

• il triple duplicate ACK (TD): in tal caso il protocollo reagisce con un fast retransmit (trascureremo il fastrecovery);

• la scadenza di un timeout (TO): in questo caso dimezziamo la finestra (senza ripartire dalla slow start).

Per ora immagineremo che AW sia abbastanza elevata da essere CW a spuntarla sempre sul controllodella finestra (poi rimuoveremo questa ipotesi).

3.4.1 Modello TD

Sia Yi la variabile aleatoria che indica quanti pacchetti sono stati inviati all’interno di un periodo incui non vi sono stati errori3: anche quest’ultimo lasso di tempo è una variabile aleatoria che indicheremocon Ai e che, chiaramente, sarà pari al numero di RTT che intercorrono tra l’inizio del ’dente’ del graficoe l’istante in cui si verifica la perdita (vedi figura 3.4). Sia poi αi il numero del pacchetto4 che provoca laperdita e p la probabilità che avvenga una perdita; infine, sia Wi il valore della finestra nel momento incui è avvenuta la perdita e βi la metà di Wi

5. Si noti che le variabili Yi, Ai, Wi αi e βi sono tutte aleatorie etutte riferite all’analisi del dente di sega i.

La variabile aleatoria Yi (numero dell’ultimo pacchetto spedito nella tornata6 i) sarà chiaramente paria

Yi = αi + Wi − 13Cioè all’interno del dente di sega.4Un numero relativo al dente di sega i, non il suo numero assoluto!5Abbiamo fatto l’ipotesi di mantenerci sempre in congestion avoidance e di ignorare lo SS.6La tornata comprende anche i β pacchetti spediti nel mentre la finestra si dimezzava.

3.4. PERDITE ALEATORIE 35

Figura 3.4: Le variabili Yi e Ai

cioè al numero relativo del primo pacchetto errato più il valore che la finestra aveva quand’è avvenutol’errore, meno 1 (che ci fa beccare l’ultimo bit giusto). Applicando l’operatore di valor medio, che è lineare,si ha:

E[Yi] = E[αi] + E[Wi]− 1

La probabilità che αi sia pari a un certo numero k è modellabile ipotizzando che i k− 1 pacchetti precedentisiano stati correttamente ricevuti (probabilità 1− p) mentre il k-simo sia stato ’scagliato’:

Pr{a = k} = (1− p)k−1 p

Il valore medio di α è chiaramente legato alla probabilità d’errore p dalla seguente relazione (che ciriporta alla memoria il caso periodico, v. par. 3.3):

E[α] = 1/p

Sostituendo otteniamo quindi:

E[Yi] = E[αi] + E[Wi]− 1 =1p

+ E[Wi]− 1 = E[Wi] +1− p

p

Infine, il periodo di trasmissione senza errori, che come abbiamo detto è pari al numero di RTT cheintercorrono tra l’inizio del ’dente’ del grafico e l’istante in cui si verifica la perdita, sarà esprimibile nelseguente modo:

Ai =Xi+1

∑j=1

RTT

Se supponiamo che RTT sia costante (rete abbastanza stabile), il suo valor medio è legato a quello di Xidalla formula:

E[A] = (E[X] + 1) · RTT

Ora ci serve un legame fra Y (numero di pacchetti correttamente spediti), X (numero di RTT effettuatiin un dente di sega) e W (valore della finestra prima del suo crollo): per trovarlo attingiamo dal paragrafo3.3.1, visto che - per ipotesi - spediamo b finestre7 prima di ricevere un ACK in grado di incrementare lanostra W(t) di 1. Intuitivamente, infatti, il massimo valore raggiunto dalla finestra nella tornata i sarà parial numero di RTT totali diviso per b (X/b è quindi il numero intero che indica di quanto è aumentata lafinestra, ovvero il numero degli ACK che sono riusciti ad incrementare la finestra8) sommato al valore dipartenza (che coincide con il valore finale della tornata i− 1, dimezzato):

Wi =Wi−1

2+

Xib

→ Xib

= Wi −Wi−1

27O, se si preferisce, aspettiamo b RTT prima di osservare un incremento della finestra.8O, se si preferisce, il numero di volte in cui la finestra è aumentata di 1.


Figura 3.5: Le variabili aleatorie in gioco nel modello TD

Il numero di segmenti Yi trasmessi nella tornata i è invece calcolabile nel seguente modo: ogni bfinestre, abbiamo detto, incrementiamo W(t) di 1; questo significa che, ad ogni incremento, avremo speditoun numero di segmenti pari al numero di RTT necessari a far incrementare la finestra (= b) moltiplicato

per il valore che la finestra ha avuto per gli ultimi b RTT, ovveroWi−1

2+ k, dove k è un contatore che ci

dice quanti incrementi di finestra sono avvenuti fin’ora. Se ora mettiamo il tutto in sommatoria e facciamo

andare k da 0 fino aXib− 1 (il −1 serve a ignorare l’ultimo RTT, all’interno del quale sono stati inviati solo

βi pacchetti, che sommiamo separatamente) otteniamo:

Yi =

Xib−1

∑j=0

(Wi−1

2+ k)

+ βi =Xib

Wi−1

2b︸︷︷︸

portiamo fuori da sommat.

+b

Xib−1

∑j=0

k + βi =

=Xib

Wi−1b2

+ b

(Xib

)(Xib− 1)

2︸︷︷︸Piccolo Gauss!

+βi =Xib

b2

[Wi−1 +

Xib− 1]

+ βi =Xi2

[Wi−1 +

Xib− 1]

+ βi

Ricordando ora l’espressione che avevamo perXib

, otteniamo l’espressione finale di Yi:

Yi =Xi2

[Wi−1 +

Xib− 1]

+ βi =(

Xib− 1)

b2

[Wi +

Wi−1

2− 1]

+ βi

Giunti fin qui siamo ben felici dei nostri risultati: mostriamo però che, in termini medi, tutto va comenel caso di modello periodico9 (par. 3.3). Applichiamo l’operatore di valor medio all’espressione della Yiper ottenere:

E[Yi] =E[Xi]

2

[E[Wi] +

E[Wi−1]2

− 1]

+ E[βi]

Si noti che quanto abbiamo fatto è stato reso possibile dall’indipendenza delle variabili aleatorie Xi e Wi.Infine tenendo conto che, come abbiamo già sottolineato nel corso di questa trattazione

E[β] =E[W]

29Avevamo già avuto un assaggio di quanto ora detto quando dicemmo che il valore medio di α è legato alla probabilità d’errore

p dalla seguente relazione (assolutamente coincidente a quella citata nel modello periodico):

E[α] = 1/p

3.4. PERDITE ALEATORIE 37

eE[Y] = E[W] +

1− pp

otteniamo (eliminando tutti i pedici che sono inutili in questa trattazione ’media’):

E[Y] =E[X]

2

[E[W] +

E[W]2− 1]

+ E[β]

E[W] +1− p

p=

E[X]2

[E[W] +

E[W]2− 1]

+E[W]

2

E[W] +1− p

p=

E[X]E[W]2

+E[X]E[W]

4− E[X]

2+

E[W]2

E[W]2

= 3E[X]E[W]

4− E[X]

2− 1− p

p

Ora sostituiamo tenendo conto che10

E [W] =2E [X]

b⇒ E [X] =

b2

E [W]

Ci tocca fare qualche calcoletto:

E[W]2

= 3E[X]E[W]

4− E[X]

2− 1− p

p

E[W]2

= 3

(b2

E [W])

E[W]

4−

(b2

E [W])

2− 1− p

p3b8

E2 [W] +(− b + 2

4

)E [W]− 1− p

p= 0

12

E2 [W] +(− b + 2

3b

)E [W]− 4 (1− p)

3pb= 0

E [W] =b + 2

3b+

√(b + 2

3b

)2+ 4 · 1

24 (1− p)

3pb=

b + 23b

+

√(b + 2

3b

)2+

8 (1− p)3pb

Se supponiamo che p << 1 (cosa largamente auspicabile) allora 1− p→ 1 e 1p >> 1, quindi riotteniamo:

E[W] ≈√

83bp

Anche se consideriamo il throughput, mediamente le cose tornano ad andare come nel caso periodico:infatti

S(p) =E[Y]E[A]

=E[Y]

(E[X] + 1) · RTT

Ricordiamo però che:

E[X] =b2

E[W] =b + 2

6+

√(b + 2

6

)2+

8b (1− p)3p

10Cioè il valor medio della finestra W, alla fine del dente di sega, è pari al prodotto fra il numero di RTT all’interno del dentefratto gli RTT necessari ad incrementare di 1 la finestra (= b) il tutto moltiplicato per due. Questo deriva dalla rimozione di pedici(dovuta all’introduzione dell’operatore E[· · · ]) nella relazione:

Wi =Wi−1

2+

Xi

b

Che diventa quindi:

E[W] =E[W]

2+

E[X]b

E[W] = 2E[X]

b


E che

E[Y] =1− p

p+ E[W]

Quindi, sostituendo e approssimando:

S (p) =

1− pp

+ E[W]

RTT (E[X] + 1)=

1− pp

+b + 2

3b+

√(b + 2

3b

)2+

8 (1− p)3bp

RTT

b + 26

+

√(b + 2

6

)2+

8b (1− p)3p

+ 1

p << 1−−−−→ 1

RTT

√3

2bp

3.4.2 Modello TD+TO

Se ora consideriamo anche la possibile scadenza dei time-out, l’andamento della finestra W(t) si faancora più diversificato nel tempo (v. figura 3.6).

Figura 3.6: Modello TD+TO

In questo caso il throughput è pari a:

S (p) ≈ 1

RTT√

2bp3

+ T0 min

(1, 3

√3bp

8

)p (1 + 32p2)

3.4.3 Modello TD+TO+AW

Figura 3.7: Modello TD+TO+AW

3.5. MODELLI A CONFRONTO 39

Se consideriamo anche l’eventualità che AW possa limitare W (v. figura 3.7) allora il throughput diventapari a:

S (p) ≈ min

Wmax

RTT,

1

RTT√

2bp3

+ T0 min

(1, 3

√3bp

8

)p (1 + 32p2)

Qual è il senso di questa formula approssimata? Essa in pratica sceglie fra due alternative:

• se AW è abbastanza grande allora possiamo tenere buona la stima del modello TD+TO;

• se AW è molto restrittiva, allora saranno molte le parti del grafico in cui tale limite ’taglia’ le punte

dei denti di sega, creando delle aree rettangolari (approssimabili daWmax

RTT).

Quanto detto è maggiormente comprensibile visionando la figura 3.8.

Figura 3.8: L’approssimazione introdotta dalla formula di AW

3.5 Modelli a confronto

Nelle figure 3.9 - 3.12 vengono messi a confronto i vari modelli (figura 3.9) e vengono esaminati glieffetti della variazione dei parametri p, RTO, RTT, AW sul modello completo (TD+TO+AW) (figure 3.10,3.11, 3.12).


Figura 3.9: Modelli a confronto

Figura 3.10: Influenza dell’RTT sul modello

3.5. MODELLI A CONFRONTO 41

Figura 3.11: Influenza di AW sul modello

Figura 3.12: Influenza di RTO sul modello


3.6 Latenza

Si definisce latenza L il tempo che intercorre fra l’istante ti in cui il client inizia una connessione TCP el’istante t f in cui i dati richiesti sono completamente ricevuti.

L = t f − ti

Per il calcolo di tale parametro faremo qualche ipotesi semplificativa:

• W limitata solamente da CW del trasmettitore (AW sufficientemente grande);

• assenza di ritrasmissioni;

• overhead dovuto alle intestazioni trascurabile;

• file costituito da un numero intero di MSS;

• i segmenti che non trasportano dati, ma solo informazioni di servizio, hanno tempi di trasmissionetrascurabili.

Indicheremo con:

• P (bit): dimensione del file di dati (ad es. pagina web) da trasferire;

• MSS (bit): il maximum segment size;

• C (bit/s): velocita del canale dal server al client.

Figura 3.13: I passi imprescindibili per effettuare un trasferimento dati

Nel caso in cui non ci sia limitazione al flusso dati dovuta al protocollo a finestra occorrono 2 RTT periniziare la connessione TCP (protocollo TWH Three Way Handshake): trascorso un RTT viene infatti inviatala richiesta dell’oggetto e, dopo un ulteriore RTT, il client comincia a ricevere i dati richiesti. Instauratoil trasferimento dei dati, essi vengono ricevuti per un periodo pari a P/C. I passi definiti fin’ora sonoobbligatori e imprescindibili (v. figura 3.13), quindi il limite inferiore (lower bound) per la latenza risultaessere:

Lmin = 2RTT +PC

In generale L > Lmin a causa delle perdite e delle non idealità della rete.

3.6. LATENZA 43

3.6.1 Finestra a dimensione fissa

Facciamo ora l’ipotesi che la finestra abbia dimensione fissa pari a W. Quando il server riceve larichiesta del client parte spedendogli W segmenti. Successivamente invia un segmento per ogni riscontroricevuto; occorre però considerare due casi:

• W ·MSSC

≥ RTT +MSS

C→ il server riceve il primo riscontro prima di aver terminato la trasmissione

della finestra:W ·MSS

Cè infatti il tempo necessario a spedire un’intera finestra di dimensione W,

mentre RTT +MSS

Cè il tempo che ci mette un segmento ad partire e a tornare (sotto forma di

conferma);

• W ·MSSC

< RTT +MSS

C→ il server termina la trasmissione della finestra prima di aver ricevuto il

riscontro.

CasoW ·MSS

C≥ RTT +

MSSC

Instaurata la connessione i segmenti continuano ad essere trasmessi a velocità C fino a che l’oggettonon è stato completamente inviato. In questo caso la latenza è uguale a quella minima:

L1 = Lmin = 2RTT +PC

Figura 3.14: Esempio con W = 6

In figura 3.14 si può visionare un esempio di quanto detto.

CasoW ·MSS

C< RTT +

MSSC

Inviata una finestra il server deve arrestarsi per aspettare il riscontro. Una volta arrivati i riscontriviene trasmessa una nuova finestra11. Il numero di finestre per trasmettere l’oggetto è pari a:

K =P

W ·MSSIl server è in attesa nell’intervallo tra la trasmissione di due finestre consecutive e quindi per K− 1 volte.Facciamo il calcolo della latenza:

L2 = 2RTT +PC

+ (K− 1)TA

2RTT +PC

è il tempo che avremmo speso anche nell’altro caso; TA è il tempo ’perso’ per ogni segmento eK− 1 è il numero di segmenti per cui si perde tempo.

11Il server si può quindi trovare o nello stato di trasmissione o nello stato di attesa di riscontro.


Figura 3.15: Schema esplicativo della formula di L2

La seguente espressione è equivalente a quella scritta poco sopra (si osservi la figura 3.15 per capirecome ottenerla12):

L2 = 2RTT + (K− 1)(

MSSC

+ RTT)

+W ·MSS

C

Di questi termini:

• il 2 · RTT è dovuto al three-way handshake;

• il (K − 1)(

MSSC

+ RTT)

è il termine legato alla trasmissione di ogni finestra (MSS

Cper poter

spedire il primo segmento della serie + RTT per avere la sua conferma che farà cominciare unanuova serie di trasmissioni);

• W ·MSSC

per l’ultima finestra, che non necessita dell’RTT del punto precedente in quanto tutti i datisono stati inviati (correttamente per ipotesi, quindi non devono tornare gli ACK).

Sviluppando il tutto si ha:

L2 = 2RTT + (K− 1)(

W ·MSSC

+ RTT +W ·MSS

C− W ·MSS

C

)+

W ·MSSC

= 2RTT +PC

+ (K− 1)[

RTT − (W − 1) ·MSSC

]Uguagliando questa espressione con quella analoga scritta poco sopra otteniamo anche l’espressione

di TA:

TA = RTT − (W − 1) ·MSSC

Il tempo perso è quindi l’RTT meno il tempo utilizzato per spedire i dati (com’è ovvio aspettarsi). Siricorda che siamo nel caso di finestra costante (il W ’a regime’ è fisso e noto a priori) e si nota che la latenzacresce:

• se K aumenta (molte trasmissioni dovute a una grande quantità di dati o a una finestra troppopiccola);

• RTT grande rispetto a MSS/C (molto tempo perso in giro per la rete).

12L’S in figura è l’MSS.

3.6. LATENZA 45

La latenza tende invece al valore ottimo (cioè cala) se:

• K = 1 (una sola finestra contiene tutto il blocco dati e il termine TA non esiste);

• (W − 1) ·MSSC

→ RTT (idem come sopra).

3.6.2 Finestra evolvente (dinamica)

Figura 3.16: Raddoppio della finestra in SS

Facciamo l’ipotesi che il server utilizzi inizialmente lo Slow Start. Come sappiamo, ad ogni riscontrosi ha W = W + 1 e quindi la finestra raddoppia ad ogni RTT (v. figura 3.16. Sia quindi k la variabile checonta gli RTT a partire da 1 seguendo la seguente relazione13

RTT numero k→W = 2k−1

Si noti che si è fatta l’ipotesi che la finestra parta da 1 all’istante iniziale: se essa fosse partita da 2 avremmoinvece avuto

RTT numero k→W = 2k

D’ora in poi, comunque, ci riferiremo all’istante k come a quello del primo RTT durante il quale nonc’è bisogno di considerare il tempo perso a causa del fatto che la finestra è più grande del prodottobanda-ritardo14 (B · RTT) La trasmissione dei dati può essere quindi suddivisa in due fasi:

• in una prima fase la finestra è ancora piuttosto piccola e abbiamo purtroppo dei tempi morti, perchéil tempo d’invio dei dati (che sono pochi) è molto piccolo rispetto al tempo che dobbiamo attendereprima di avere la conferma ed allargare la finestra: W < S/C + RTT. In questo caso, come abbiamodetto poco fa, siamo ad un RTT precedente al k-simo;

• nella fase successiva la finestra è abbastanza grande e da far sì che, all’arrivo della prima conferma,ancora si stanno spedendo dei segmenti: W ≥ S/C + RTT. In questo regime la banda è sfruttata lameglio. L’RTT corrente è quindi il k-simo o uno successivo.

13Che è valida solo se lavoriamo unicamente in SS!!14E quindi siamo nel caso buono in cui trasmettiamo durante tutto il periodo in cui aspettiamo il primo ACK di ogni finestra

trasmessa (e possiamo quindi continuare a trasmettere qualcos’altro, non fermandoci mai).


Siano P i bit totali da spedire, P′ i bit spediti durante la prima fase (non ottimale) e P′′ = P − P′

i bit spediti nella seconda (ottimale). Se il ciclo k è quello in cui termina la prima fase allora durantequest’ultima avremo trasmesso, se W partiva da 1,

k

∑i=1

2i−1 ·MSS [bit]k

∑i=1

2i−1 [segmenti]

oppurek

∑i=1

2i ·MSS [bit]k

∑i=1

2i [segmenti]

se W partiva da 2.Di lì in poi siamo nella seconda fase e quindi nel caso ottimo per la latenza. Sommando i contributi

della prima fase e della seconda otteniamo15:

L3 = 2RTT + k(

MSSC

+ RTT)

︸︷︷︸prima fase

+P′′

C︸︷︷︸seconda fase

=

= 2RTT + k(

MSSC

+ RTT)

+P′′

C+

P′

C︸︷︷︸P/C

−P′

C=

= 2RTT +PC

+ k(

MSSC

+ RTT)−

k∑

i=12i−1 ·MSS

CSe W iniziava da 1

L3 = . . . = 2RTT +PC

+ k(

MSSC

+ RTT)−

k∑

i=12i ·MSS

CSe W iniziava da 2

In ogni caso, lo schema concettuale è sempre lo stesso:

L3 = 2RTT +(

MSSC

+ RTT)· N{Cicli ’non ottimali’} +

P{Dopo i cicli ottimali}

C· N{Cicli ’ottimali’}

Tutto quello che abbiamo detto fin’ora vale fintanto che si suppone di stare sempre in SS fino alfantomatico ciclo in cui la finestra raggiunge (e supera) il valore ottimo per la latenza (pari al prodottobanda-ritardo B · RTT). E se nel frattempo andiamo in CA? In realtà non cambia un granché: bisognasolo avere l’accortezza di capire il numero di cicli (cioè di RTT) in cui la finestra è ancora troppo piccolaper essere ottima. Per esempio, se il prodotto banda-ritardo ci suggerisce che la finestra ottima è 32 e laSSTHR è pari a 16 si hanno:

• i soliti 2RTT per il TWH;

• 4 cicli in cui siamo in SS (la finestra è, nell’ordine: 1 → RTT + MSSC → 2 → RTT + MSS

C → 4 →RTT + MSS

C → 8→ RTT + MSSC → 16). In questo caso, quindi, il parametro k è pari a 5;

• 32− 16 cicli di congestion avoidance;

• un tempo pari a P′C eventuali altri P′ bit da trasmettere.

L = 2RTT + 4 ·(

MSSC

+ RTT)

+ 16 ·(

MSSC

+ RTT)

+PC

C’è infine da dire che AW, se assume valori relativamente bassi, potrebbe limitare la finestra W ad unvalore non ottimale: in tal caso bisogna naturalmente tenerne conto.

15In questi calcoli può tornare utile la seguente relazione:

k−1

∑i=1

2i = 2k − 2

3.7. IN SINTESI 47

3.7 In sintesi

Il throughput di una connessione TCP è la quantità totale di informazioni trasmesse nell'unità di tempo,

S(t) =W(t)RTT

mentre il goodput misura i dati trasmessi con successo (sempre nell'unità di tempo). Com'è ovvio, il goodput

è uguale al throughput nel caso migliore, altrimenti è sempre inferiore. I parametri S e W sono interessanti da

analizzare ed infatti sono stati creati dei modelli in grado di stimarli:

• modello periodico: questo modello assume che vi sia una certa percentuale di perdita p e che quindi si

riescano a trasmettere N = p−1 segmenti all'interno di un periodo di trasmissione T stante fra due perdite.

Il gra�co di W(t) per una connessione a perdite periodiche ha la forma di un treno periodico di denti di

sega (periodo di ripetizione = T);

• modello periodico con ACK ritardati: è tutto come nel caso precedente ma la crescita della �nestra è

rallentata dall'uso di ACK ritardati. Ne risentono sia il troughput che la dimensione massima assunta da

W;

• modello aleatorio TD: i calcoli iniziano a complicarsi perché dobbiamo abbandonare la periodicità delle

perdite. In questo caso particolare, le perdite sono dovute all'eventualità di triple duplicate ACK, mentre

trascureremo la scadenza di eventuali timeout (in particolare l'RTO) o il contributo della �nestra AW nel

dimensionamento di W. Per generalità, terremo invece in considerazione la possibilità che si faccia uso di

delayed ACK, tanto basta porre b = 1 per tornare nel caso di ACK non ritardati. Il gra�co di W(t) per unaconnessione a perdite aleatorie è fatto da denti di sega di forme completamente diverse l'uno dall'altro e

non presenta periodicità. Volendo trovare formule assimilabili a quelle dei modelli precedenti non possiamo

fare altro che ragionare in termini medi;

• modello aleatorio TD+TO: come il caso precedente, ma questa volta mettiamo in conto il possibile

scadere dell'RTO;

• modello aleatorio TD+TO+AW: come il caso precedente, ma consideriamo anche l'eventualità che

AW < CW e quindi limiti la �nestra.

Throughput S dim. max di W T fra perdite

Periodico1

RTT

√3

2p

√8

3pW2

RTT

Periodico (ACK rit.)1

RTT

√3

2bp

√8

3bpWb2

RTT

Aleatorio TD mediamente come il periodico (m.d.) m.d. m.d.

Aleatorio TD+TO1

RTT√

2bp3 + T0 min

(1, 3

√3bp

8

)p (1 + 32p2)

Aleatorio TD+TO+AW min(

Wmax

RTT, STD+TO

)Tabella 3.1: Schema riassuntivo per i vari modelli

La latenza è il tempo che intercorre fra l'istante in cui il client inizia una connessione TCP (ti) e l'istante in

cui i dati richiesti sono stati completamente ricevuti (t f ): L = t f − ti. Sia P la dimensione dei dati da trasferire

e C la velocità del canale di trasmissione; se facciamo l'ipotesi che W dipenda solo da CW e che l'overhead sia

trascurabile, la latenza minima (quella imprescindibile) è Lmin = 2RTT +PC.

Per W sia �ssa che mobile, dobbiamo tenere in conto due casi:

• WMSS

C≥ RTT +

MSSC⇒ W ≥ prodotto banda-ritardo⇒ il server riceve il primo riscontro prima di aver

trasmesso tutta la �nestra (caso 'buono');


• WMSS

C< RTT +

MSSC⇒ W < prodotto banda-ritardo ⇒ il server termina la trasmissione della �nestra

prima di aver ricevuto il primo riscontro (caso non ottimale).

Dopodiché bisogna trovare il modo di scrivere la latenza nel seguente modo:

L3 = 2RTT +(

MSSC

+ RTT)· N{Cicli 'non ottimali'} +

P{Dopo i cicli ottimali}

C· N{Cicli 'ottimali'}

Nel far questo si tenga presente l'azione che gli eventuali SSTHR o AW, se troppo bassi, potrebbero avere

sulla �nestra.

Capitolo 4

Intradamento e forwarding IP

4.1 Introduzione sulla commutazione

Il compito dello strato di rete è quello di trasportare informazioni da un certo mittente a un certodestinatario: il cardine del meccanismo che rende questo possibile risiede all’interno dei cosiddetti nodi dicommutazione (i router, tanto per intenderci), i quali devono possedere tante interfacce di ingresso/uscitaquanti sono i collegamenti afferenti/uscenti. La commutazione consiste nello scegliere l’interfaccia giustaverso la quale instradare i dati, reperendo le risorse necessarie al trasferimento.

In una rete a maglia completa, in cui tutti sono collegati con tutti, la commutazione avviene all’internodel terminale che vuole inviare i dati: sapendo di voler raggiungere la destinazione X, colui che devespedire il messaggio sceglierà autonomamente (e internamente) verso quale interfaccia di rete inviarlo.

In una rete commutata, invece, non c’è necessità di collegare tutti con tutti (scelta improponibile in retigrandi) in quanto esistono dei nodi intermedi (nodi di commutazione) che si occupano di smistare i messaggiverso la giusta destinazione, reperendo le risorse necessarie a realizzare il trasferimento dell’informazionefra sorgente e destinazione. La commutazione si è quindi in questo caso spostata dal mittente ai nodiintermedi.

Esistono due tipi principali di commutazione:

• commutazione di circuito: la rete crea un canale di comunicazione esclusivo fra due terminali collo-quianti. In questo caso la trasmissione è assolutamente trasparente dal punto di vista temporale inquanto, una volta effettuate le operazioni per l’instaurazione del collegamento, la trasmissione dis-porrà di una quantità di banda costante e immutabile (nessuno si infilerà mai nel nostro circuito!) e,se il mezzo di comunicazione è full-duplex, l’unico ritardo percepito sarà quello fisico di trasmissione.La commutazione di circuito garantisce massima affidabilità e sicurezza nonché minimo overhead peroperazioni di controllo (servono a malapena quelle per instaurare il circuito e rilasciarlo), ma nonpermette di modificare la banda del collegamento, né di sfruttarlo meglio in caso di lunghi silenzifra i due colloquianti;

• commutazione di pacchetto: è una commutazione di tipo numerico (digitale) che si basa sullo smis-tamento di pacchetti di dimensione fissa e predefinita. I messaggi o i pacchetti vengono trasmessida un nodo di commutazione all’altro utilizzando in tempi diversi risorse comuni (pacchetti ap-partenenti a diverse ’conversazioni’ possono essere trasmessi attraverso la stessa interfaccia); le duetecniche principali di commutazione di pacchetto sono:

– circuito virtuale (connection-oriented): si simula l’instaurazione di un circuito (circuito virtuale),cercando di garantire la corretta sequenza di ricezione (con un protocollo ARQ) e stabilendo apriori quale sia il percorso che i pacchetti devono prendere;

– invio di datagrammi (connection-less): ogni pacchetto viene gestito e instradato in modo indipen-dente, senza relazione con pacchetti precedenti o successivi, anche appartenenti alla stessaconnessione. I vari pacchetti, quindi, potrebbero scegliere di volta in volta un percorso diversoper arrivare a destinazione.

I vantaggi della commutazione di pacchetto stanno in un’utilizzazione più efficiente della banda,nella possibilità di scegliere dinamicamente la velocità del collegamento, di utilizzare la memoriz-

49

50 CAPITOLO 4. INTRADAMENTO E FORWARDING IP

zazione e di effettuare il controllo degli errori all’interno dei nodi. Per contro, non riusciamo agarantire il corretto funzionamento in caso di vincoli real-time.

4.1.1 Nodi di commutazione: routing e forwarding

Nel caso della commutazione di pacchetto, i nodi di commutazione hanno svariati compiti.

Anzitutto devono essere in grado di effettuare la commutazione vera e propria (forwarding) e cioè:

• verificare e memorizzare (store) i pacchetti entranti;

• leggere la loro intestazione;

• consultare un’opportuna struttura dati (tabella di routing) per capire verso quale interfaccia spedire ilmessaggio;

• inserire il pacchetto nell’opportuna coda d’uscita (forward).

Questi compiti appartengono chiaramente allo strato di rete (piano utente) e le modalità con cui vengonoeseguiti dipendono da chi ha costruito il router.

Figura 4.1: Schema concettuale dello store-and-forward, nella commutazione di pacchetto

Parallelamente a questo, i router devono poter scambiare informazioni fra di loro al fine di costruirele tabelle di instradamento (routing). La funzione di routing si avvale di algoritmi di routing, usati per ilcalcolo delle tabelle di instradamento note le informazioni sulla topologia della rete, e di protocolli di rout-ing, usati per lo scambio delle informazioni sulla topologia della rete necessarie per applicare l’algoritmo.Perché questo meccanismo funzioni, i protocolli per lo scambio di informazioni devono essere standard eben noti a priori. Inoltre, i router devono comportarsi come veri e propri calcolatori specializzati e con-tenere al loro interno delle strutture dati idonee (cioè veloci e ottimizzate) entro le quali memorizzare letabelle.

4.2 Indirizzi IP

Gli indirizzi IP sono stringhe lunghe 32 bit convenzionalmente scritte come sequenze di 4 numeridecimali, aventi valori da 0 a 255, separati da un punto:

4.2. INDIRIZZI IP 51

10001001.11001100.11010100.00000001 = 137.204.212.1

Vengono assegnati dalla IANA1 e sono logicamente suddivisi in due parti:

• network-ID: identifica la rete cui appartene l’indirizzo e occupa la parte sinistra dell’indirizzo;

• host-ID: identifica l’host vero e proprio di una certa rete; occupa la parte destra dell’indirizzo.

Originariamente la dimensione dei net-ID era specificata di default, in quanto esistevano classi dinetwork differenziate per dimensione2 (v. fig. 4.2 e tabella sottostante):

Classe A 7 bit net-ID→ 27 reti 24 bit host-ID→ 224 − 2 hostClasse B 14 bit net-ID→ 214 reti 16 bit host-ID→ 216 − 2 hostClasse C 21 bit net-ID→ 221 reti 8 bit host-ID→ 28 − 2 host

Figura 4.2: Le classi di reti

Grazie al CIDR (Classless InterDomain Routing) si è però abbandonata questa rigida suddivisione nelle3 classi, permettendo il settaggio di una dimensione qualunque per il Net-ID la cui lunghezza in bit, apartire da sinistra, è indicata dal parametro Netmask (sempre associato all’indirizzo IP).

NETMASK:

255.252.000.000 (notazione alternativa /14)->Net-ID: primi 14 bit da SX dell'indirizzo IP



etc...

Obiettivo del CIDR era quello di allocare reti IP di dimensioni variabili, accorpando preferibilmente leinformazioni di routing per più reti contigue (cosa che avrebbe semplificato notevolmente le tabelle dirouting) e ponendo, allo stesso tempo, rimedio alla limitatezza di classi A e B. Accorpare più reti in unasola o scindere una rete grande in tante più piccole sono due operazioni duali che passano sotto il nomedi:

• subnetting: scindere di una rete grande in più reti, contenenti ciascuna meno host di quella dipartenza (’alzando’ la netmask, v. fig. 4.3);

• supernetting: accorpare più reti continue in un’unica rete (’abbassando’ la netmask, v. fig. 4.3).

1Internet Assigned Numbers Authority2In più alcuni gruppi di indirizzi riservati per le reti private:

da 10.0.0.0 a 10.255.255.255

da 172.16.0.0 a 172.31.255.255

da 192.168.0.0 a 192.168.255.255


Figura 4.3: Subnetting e Supernetting

4.2.1 Instradamento e table look-up

Si dice:

• consegna diretta : IP sorgente e destinatario fanno parte della stessa rete. In tal caso l’host sorgentespedisce il datagramma direttamente al destinatario;

• consegna indiretta : IP sorgente e destinatario non fanno parte della stessa rete e c’è quindi bisognodi uno o più router intermedi per effettuare la consegna.

Nelle tabelle di routing sono infine presenti:

• indirizzo di destinazione: un host o una network;

• netmask: per verificare la corrispondenza con la destinazione e per indicare a quale rete ’logica’ cistiamo riferendo;

• gateway: indica il tipo di consegna da effettuare (a chi bisogna dare il pacchetto);

• interfaccia di rete: specifica quale interfaccia utilizzare;

• metrica: specifica il ’costo’ di una particolare route.

Il table-lookup avviene incrociando l’indirizzo IP di destinazione del datagramma e quello di ciascuna rigadella tabella: si esegue un’operazione AND bit-a-bit tra l’indirizzo di destinazione del datagramma e lanetmask di ciascuna riga, poi il risultato viene confrontato con la destinazione specificata nella riga stessa.Se coincidono, la riga è quella giusta: altrimenti, se nessuna riga corrisponde, si usa un gateway di default.

4.3 In sintesi

Compito dello strato di rete è quello di trasportare informazioni da mittente a destinatario. In soldoni, una

rete è costituita da collegamenti e da nodi: i nodi sono apparati dotati di interfacce verso uno più collegamenti,

il cui incarico è quello di collegare una certa linea d'ingresso con una linea (o più linee) d'uscita. In base alla

topologia della rete si distingue fra:

• rete a maglia completa: collega a 1 a 1 tutti gli utenti;

• rete commutata: abbiamo terminali e nodi di transito, i quali devono concorrere a reperire risorse al �ne di

realizzare il trasferimento dell'informazione fra sorgente e destinazione.

Esistono due tipi di commutazione:

• di circuito: la rete crea un canale di comunicazione dedicato fra due terminali che vogliono colloquiare.

PRO: sicuro, a�dabile, trasparente, pochissime procedure di controllo. CONTRO: circuito sottoutilizzato

se le sorgenti hanno basso tasso d'attività, capacità �ssata a priori ed invariante.

• di pacchetto (v. �g. 4.1): trasporta informazioni in forma numerica (digitale). Le informazioni sono divise

in messaggi (pacchetti) di lunghezza pre�ssata: per la loro trasmissione esistono due principali tecniche,

che sono

– la creazione di un circuito virtuale (connection-oriented): lo scambio di informazioni è preceduto da

una procedura di segnalazione che stabilisce il percorso dei pacchetti da origine a destinazione. Tutti

i pacchetti, di conseguenza, prenderanno lo stesso percorso;

– l'uso di datagrammi (connection-less): ogni pacchetto, portando con sé le informazioni di indirizza-

mento necessarie a raggiungere la destinazione �nale, è gestito e instradato in maniera indipendente.

4.3. IN SINTESI 53

PRO: e�cienza nell'uso del collegamento maggiore, uso scalabile della rete (con possibilità di memoriz-

zazione e controllo dell'errore). CONTRO: poco adatta per i servizi real-time.

Nella commutazione di pacchetto le tabelle di routing, usate per il corretto instradamento, sono costruite

tramite scambio di informazioni tra i router (protocolli di routing : servono ad ottenere informazioni sulla topolo-

gia della rete e si basano su uno scambio di informazioni tra applicazioni3) ed elaborazione locale (algoritmi di

routing : calcolano le tabelle di instradamento una volta note le informazioni portate dai protocolli di routing).

Nelle reti IP la commutazione viene e�ettuata sulla base dell'indirizzo IP, parametro di 32 bit (scritto in

notazione dotted decimal) che può essere scisso in:

• net-ID: individua la rete (ad es. quella di un'università o di un'azienda);

• host-ID: individua l'host di una particolare rete (ad es. un server di una certa università o azienda).

Un tempo host-ID e net-ID dovevano avere dimensioni �sse determinate dalle cosiddette 'classi' ma poi, per

maggiore �essibilità, si è scelta la convenzione indicata dal CIDR grazie alla quale net-ID e host-ID potevano

avere dimensioni variabili (indicate dal parametro Netmask, anch'esso scrivibile in dotted decimal oppure con un

semplice numero decimale). Grazie a questo rivoluzionario cambiamento è stato possibile e�ettuare subnetting

(scissione di una certa classe di reti in più reti più piccole) e il supernetting (raggruppamento di più reti in

un'unica, più grande) in maniera naturale.

Gli indirizzi IP sono l'indicazione più importante che compare nelle tabelle di routing. Esse sono memorizzate

all'interno dei nodi di commutazione e contengono indirizzo di destinazione, netmask, gateway prede�nito per

arrivare a quell'indirizzo, la relativa interfaccia di rete e, in�ne, la metrica. In base alla tabella di routing e all'op-

erazione di table-look-up con longest pre�x match (propendiamo per l'indirizzo valido con la netmask maggiore)

un nodo capisce infatti se deve fare consegna diretta (nella stessa rete) o indiretta (in un'altra rete) e individua

qual è l'interfaccia di rete verso la quale e�ettuare il forwarding.

3In questo senso i router sono calcolatori specializzati.

Capitolo 5

Architetture dei router IP

5.1 Tipologie commerciali di router

I router commerciali possono essere divisi in categorie:

• access router: sono utilizzati dai provider (ISP) per fornire accesso ad utenti domestici e a piccoleimprese. Dispongono di un elevato numero di porte a bit-rate medio-bassa (50 kbps - 10 Mbps) esupportano una grande varietà di protocolli e tecnologie di accesso (PPP, ADSL, FTTH, . . . ). Costanorelativamente poco;

• enterprise router: utilizzati per interconnettere le infrastrutture di rete di imprese medio-grandi o digrossi enti (università). Hanno un limitato numero di porte ad alta bit-rate (10 Mbps - 1 Gbps) e uncosto medio;

• backbone router: utilizzati per interconnettere reti su scala regionale/globale. Dispongono di pocheporte ad elevatissima bit-rate (1 Gbps - 10 Gbps); costano molto ma hanno un’alta affidabilità edefficienza.

5.2 Schema funzionale, routing vs. forwarding

Lo schema funzionale di un router mostrato in figura 5.1; come si vede, il router lavora tra lo strato2 (data link) e lo strato 4 (trasporto): fra i suoi compiti vi sono quelli di effettuare la frammentazione o ilriassemblaggio dei pacchetti, il loro inoltro, l’aggiunta e il processamento dell’intestazione.

In particolare, le incombenze dei router si snodano tra:

• routing: consistente nei protocolli (per la comunicazione dei dati fra nodi) e negli algoritmi (per ilcalcolo delle tabelle) atti a fornire le risorse utili all’instradamento;

• forwarding: consistente nel processamento IP, nel table look-up e nell’header update.

5.3 Table look-up

Con l’espansione esponenziale di internet le tabelle di instradamento dei router di bordo si sono fattesempre più complesse: a titolo d’esempio, dalle poche centinaia di entry che si avevano nei primi anni’90 si è passati alle centinaia di migliaia degli ultimi tempi. Per tal motivo si è presto sentita l’esigenzadi creare delle strutture dati specializzate, efficaci nel mantenere in memoria (veloce, ad es. una cache)questa mole incredibile di informazioni e contemporaneamente in grado di garantire un rapido look-up.Fra queste troviamo:

• struttura ad albero (tree): le route sono mantenute in una struttura ad albero binario. Ogni bitdell’indirizzo di destinazione (a partire dal più significativo) prende il ramo di sinistra o di destra(rispettivamente associati ad un ’1’ o ad uno ’0’, nell’ordine che si preferisce). Il numero di iterazionida effettuare è sempre pari alla profondità dell’albero;

55

56 CAPITOLO 5. ARCHITETTURE DEI ROUTER IP

Figura 5.1: Schema logico di funzionamento di un router

• trie (Patricia Trie): come l’albero, ma conserviamo soltanto le foglie che portano ad un indirizzo (cioèa un prefisso) ’valido’. Per questo motivo il trie tiene relativamente poca memoria ed è più veloce dascorrere in quanto l’attraversamento dei rami si interrompe non appena raggiungiamo una stringa’valida’. Con questa scelta il numero massimo di iterazioni utili a reperire il giusto indirizzo (casopeggiore) è pari al più alla profondità dell’albero; se invece siamo più fortunati risparmiamo deltempo rispetto al caso del tree (v. fig. 5.2).

Figura 5.2: Patricia Trie

5.4 Architettura dei router

I router di prima generazione erano delle workstation con struttura a bus (v. fig. 5.3): questa sceltatopologica, tuttavia, non rendeva tali dispositivi molto efficienti in quanto il bus si configurava come unelemento di contesa e quindi come un ’collo di bottiglia’ per le prestazioni. I passi per il processamentodei pacchetti erano infatti, in tal caso:

1. trasferimento in memoria (DMA) dei pacchetti ricevuti nelle interfacce tramite il bus;

2. elaborazione delle intestazioni e consultazione la tabella di routing da parte della CPU, che nelfrattempo esegue anche i protocolli di routing;

5.4. ARCHITETTURA DEI ROUTER 57

3. trasferimento dei pacchetti elaborati sulle interfacce (ancora tramite il bus!).

Figura 5.3: Schema dei router di prima generazione

Le architetture attuali, quindi, sono decisamente più ottimizzate in quanto constano di:

• una CPU che calcola la tabella di routing, esegue i protocolli e gestisce il sistema nel suo complesso;

• interfacce d’ingresso che memorizzano i pacchetti ed eseguono il look-up su copie locali della tabella(più o meno complete);

• una matrice di commutazione permette il trasferimento diretto e contemporaneo di più pacchetti(da diversi ingressi a diverse uscite).

Il tutto è realizzato in hardware veloce e specializzato (ASIC).

5.4.1 Crossbar

La matrice di commutazione crossbar (v. fig. 5.4) è una matrice monostadio fatta da N2 punti d’incrocio,non bloccante, in grado di effettuare più trasferimenti in parallelo. La velocità di commutazione è quindilimitata alla velocità dello scheduler deputato ad associare gli ingressi con le corrette interfacce d’uscita.

Figura 5.4: Matrice di commutazione crossbar

La complessità di una rete del genere è piuttosto elevata in quanto va con N2.

5.4.2 Rete di Clos

Trattasi di una soluzione alternativa alla crossbar consistente in una matrice multistadio simmetrica ingrado di ridurre la complessità e i punti d’incrocio. In figura 5.5 viene mostrata una rete di Clos a trestadi, simmetrica: si dimostra che essa è non bloccante se m ≥ 2n− 1. La sua complessità va con N

32 ed è

quindi piuttosto inferiore rispetto a quella della crossbar.


Figura 5.5: Rete di Clos

5.5 Posizionamento delle memorie

Nelle reti a commutazione di pacchetto in ogni nodo tipicamente si memorizzano i pacchetti primadi trasmetterli in uscita (store and forward). Essi vengono posti nelle memorie delle interfacce di ingressodurante l’elaborazione dell’intestazione e il look-up e quindi nelle memorie nelle interfacce di uscita primadella trasmissione. L’utilizzo di matrici di commutazione (anche se non bloccanti) per trasferire pacchettinecessita infatti di code (buffer) per risolvere le contese tra pacchetti diretti verso la stessa porta di uscita.A tal proposito possono essere fatte alcune scelte aventi grandi ripercussioni sulle prestazioni:

• accodamento in uscita, come mostrato in figura. Purtroppo con questa configurazione è necessario

Figura 5.6: Accodamento in uscita

uno speed-up con fattore N: la velocità di commutazione della matrice dev’essere infatti almeno parialla somma delle velocità di trasmissione dei pacchetti nelle N linee d’ingresso;

• accodamento in ingresso, come mostrato in figura. Con questa scelta non necessitiamo dello speed-

Figura 5.7: Accodamento in ingresso

5.6. IN SINTESI 59

up, tuttavia soffriamo del cosiddetto blocco HOL (Head Of Line): tutti i pacchetti di una qualsiasifila, infatti, devono attendere che sia processato il primo della fila prima di poter essere a loro voltacommutati. In queste condizioni, il throughput massimo equivale al 58

• accodamento virtuale in uscita, come mostrato in figura. In questo caso ogni ingresso dispone di N

Figura 5.8: Accodamento virtuale in uscita

code (una per uscita) per un totale di N2. Con questa scelta abbiamo il massimo throughput, evitiamoil blocco HOL ma necessitiamo di una quantità esorbitante di code, cosa che complica di molto loscheduler;

• accodamento a memoria comune, come mostrato in figura In tal caso si ha un’unica memoria co-

Figura 5.9: Accodamento a memoria comune

mune, con un’organizzazione a code logiche combinate in un unica fisica. Anche in questo casodisponiamo del throughput massimo, evitiamo il blocco HOL e non necessitiamo di un numeroesagerato di code (in quanto c’è un’unica memoria); inoltre, perché si verifichi la perdita di pac-chetto si deve riempire tutta la memoria, eventualità relativamente difficile da realizzare. Il rovesciodella medaglia, ineluttabile come il destino1, sta però in una più complicata gestione della memoria.

5.6 In sintesi

Tipologia router Costo Velocità (Mbps) Numero di interfacce

Access Router basso 0,05 - 10 elevatoEnterprise Router medio 10 - 1000 limitatoBackbone Router elevato 1000+ scarso

I router si occupano di routing (protocolli + algoritmi di instradamento) e di forwarding (processamento

dell'intestazione IP, table look-up, header update). Per e�ettuare queste operazioni, tali dispositivi fanno uso di

una routing table (contenente la route, il next-hop e la metrica) e di una forwarding table (costruita a partire

dalla routing table e avente la classica con�gurazione Unix-like).

1Questo sì che è kitsch!


Grande importanza riveste il table look-up e�ettuato per l'instradamento tramite longest pre�x match: a�nché

esso sia e�cace si richiedono infatti strutture per l'accesso rapido e ottimizzato. Due fra le scelte maggiormente

notevoli sono quelle che passano sotto il nome di tree (albero binario che viene interamente percorso lungo i suoi

rami per scoprire l'indirizzo IP complessivo) e il trie, che è una versione sempli�cata e 'sfogliata' del tree all'interno

della quale vengono riporti soltanto i pre�ssi degli indirizzi (e non l'intero albero, profondo 232) cosicché non è

necessario scorrere tutti i rami per arrivare alla giusta entry.

Mentre le architetture dei primi router si basavano su una workstation a bus, cosa che limitava di molto le

prestazioni, i router moderni dispongono di una matrice di commutazione in grado di e�ettuare più trasferimenti

in parallelo; la matrice di commutazione può essere crossbar (matrice N × N, complessità N2) oppure di Clos,

matrice multistadio simmetrica costituita da elementi non bloccanti, complessivamente non bloccante se m, cioè il

numero di elementi nello stadio centrale, è maggiore o uguale a 2n− 1 (dove n è il numero di ingressi di ciascuno

dei k elementi del primo e dell'ultimo stadio). La complessità della rete di Clos è inferiore a quella della crossbar

(N32 vs. N2).Un altro elemento in grado di in�uire sulle prestazioni è il posizionamento delle memorie adiacenti alla matrice

di commutazione (v. tabella)

Pos. memorie Pro Contro

Uscita Necessario speed-up con fattore NIngresso Non serve lo speed-up Blocco HOL (limitato throughput)Virtuale in uscita No speed-up e blocco HOL N2 code, scheduler complessoA memoria comune No speed-up e blocco HOL, unica memoria Gestione complessa

Capitolo 6

Algoritmi di routing

In questo capitolo ci occuperemo di algoritmi di routing in senso generale (teoria dei grafi) nonchédella loro applicazione nelle reti di telecomunicazione.

6.1 La teoria dei grafi e il routing

Essendo una rete sostanzialmente un insieme di nodi interconnessi da collegamenti (rami, archi), risul-ta comodo utilizzare la teoria dei grafi per effettuarne la rappresentazione e lo studio: indicheremo conV un insieme finito di nodi, con il termine arco il collegamento di fra i nodi (i, j) ∈ V, con E un insiemedi archi. Un grafo si costruisce mettendo insieme i nodi e gli archi quindi, in definitiva, può essere carat-terizzato dalla coppia (V, E): sarà orientato se anche gli archi lo sono, non orientato viceversa. Due nodiconnessi da un arco verranno poi detti adiacenti.

Da un grafo di V nodi e E archi possiamo trarre un sottografo fatto da V′ ⊆ V nodi e E′ ⊆ E archi.Denomineremo poi pesato un grafo tale che ad ogni arco è associato un numero reale e positivo w

chiamato peso (o costo, o distanza). In un grafo orientato il peso del collegamento fra due nodi potrebbeessere differente in base all’orientazione, mentre in un grafo non orientato la distanza è univoca dati inodi (i, j). Convenzionalmente, infine, diremo che la distanza fra due nodi non connessi da un arco è paria +∞. Quanto detto fin’ora può essere visto in figura 6.1.

Figura 6.1: Grafo orientato (a sinistra) e un grafo non orientato (a destra)

Continuiamo con la terminologia: chiameremo cammino (path) di lunghezza k fra il nodo u e il nodov una sequenza di k + 1 nodi il primo dei quali è il nodo u e l’ultimo il nodo v. Se contiene tutti nodidistinti (e quindi non passiamo due volte da uno stesso nodo), un cammino è detto semplice. Un ciclo èun cammino di lunghezza ≥ 3 in cui il nodo di arrivo e di partenza coincidono; se un grafo non contienecicli è detto aciclico. Un grafo viene denominato connesso se esiste sempre un cammino fra due qualsiasi

61

62 CAPITOLO 6. ALGORITMI DI ROUTING

suoi nodi, completamente connesso se due nodi qualsiasi possono essere collegati da un solo arco1 (e quindisono automaticamente adiacenti).

Figura 6.2: Grafi aciclici, connessi, completamente connessi

Un albero è un grafo connesso e aciclico: in esso

• ogni coppia di nodi è connessa da un unico cammino;

• il numero di nodi è pari al numero di archi meno 1;

• se si rimuove un qualsiasi arco il grafo diventa non connesso;

• se si aggiunge un qualsiasi arco il grafo diventa ciclico.

Chiameremo spanning tree (albero di ricoprimento) di un qualsiasi grafo connesso G un albero in gradodi connettere tutti i nodi di G. Intuitivamente, il numero di archi dello spanning tree di G sarà inferiore(o al limite uguale) al numero di archi di G e sarà sempre possibile ottenere uno spanning tree eliminandoopportuni archi da un grafo connesso, qualsiasi esso sia.

Dato un grafo pesato connesso e non orientato G, un minimum spanning tree (albero di ricoprimentominimo) di G è uno spanning tree G′ di peso minimo, ovvero la cui somma dei pesi dei vari archi è minima(v. figura 6.3: com’è indicato, possono esservi più MST per uno stesso grafo).

Figura 6.3: Alcuni esempi di minimum spanning tree

1In questo caso il numero di archi del grafo è |V| |V| − 12

6.2. ALGORITMI PER IL CALCOLO DEL MINIMUM SPANNING TREE 63

6.2 Algoritmi per il calcolo del minimum spanning tree

Dato un grafo pesato connesso non orientato G = (V, E) esistono alcuni algoritmi di tipo greedy cheman mano aggiungono un arco di E ad un sottografo A (il quale, durante i passi dell’algoritmo, è sot-tografo sia di G che di un MST di G) fino al ricoprimento di tutti i nodi. Alla fine di tali algoritmi sarannostati esclusi i rami di G aventi peso maggiore (o al limite uguale) a quelli inclusi nell’MST (completo) Ache è stato ’estratto’ da G.

6.2.1 Algoritmo di Kruskal

La complessità di quest’algoritmo va con E log V; esso ordina gli archi di E secondo il peso crescente,creando, nei passi intermedi, un sottografo che durante lo svolgimento dell’algoritmo può essere nonconnesso (molto spesso ciò accade se i rami di piccolo peso sono ’distanti’ fra loro).

1. Si parte da un sottografo A vuoto.

2. Si aggiunge ad A l’arco (di G) di peso minore possibile, senza creare cicli.

3. Si continua in questa maniera fino al termine dell’algoritmo, cioè fino a quando non avremo collegatotutti i nodi del grafo G di partenza.

6.2.2 Algoritmo di Prim

La complessità di quest’algoritmo va con E + V log V; differentemente da quanto avviene nell’algorit-mo di Kruskal, A è sempre un albero connesso durante i passi intermedi dell’algoritmo.

1. Si parte da un nodo radice (cioè di partenza, scelto fra quelli di G) come unico elemento di A.

2. Si aggiunge l’arco connesso ad A di peso minore, senza creare cicli.

3. Si prosegue fino ad esaurire l’algoritmo.

6.3 Shortest path

Come abbiamo già detto, dato un grafo pesato orientato G = (V, E), il peso del cammino p fra duenodi è la somma dei pesi degli archi che lo costituiscono. Uno shortest path (cammino minimo) dal nodou al nodo v è un cammino (u, v) il cui peso è minimo fra tutti i possibili cammini (v. fig. 6.4: si noti chepossono esistere contemporaneamente più cammini di peso minimo).

Figura 6.4: Cammino di peso minimo

Uno shortest path è sicuramente un cammino semplice (cioè che contiene tutti nodi distinti, v. par. 6.1):questa affermazione è abbastanza ovvia in quanto passare due volte per uno stesso nodo significa aversicuramente allungato il percorso fra il nodo di partenza e quello di arrivo.

Altra proprietà piuttosto intuitiva è quella che passa sotto il nome di principio di ottimalità: se abbiamouno shortest path p tra il nodo di indice 0 e quello di indice k (supponiamo di averli numerati in ordine


crescente in base al percorso), allora qualsiasi sottocammino di p effettuato tra due nodi intermedi i e j(con 0 < i < j < k) è anch’esso uno shortest path2.

6.4 Algoritmi per il calcolo dello SP

Dato un grafo pesato connesso e orientato G = (V, E) e un nodo sorgente s ∈ V esistono algoritmiper trovare uno SP da s verso ogni altro nodo di V (single-source shortest path problem). Tali algoritmipermettono inoltre di trovare la distanza d(v) di un generico nodo v (appartenente allo SP) da s nonché ilpredecessore π(v) del nodo v lungo lo SP3. Inizialmente (initialization) ogni nodo viene posto a distanzapari ad infinito dal nodo sorgente s, mentre quest’ultimo viene posto a distanza pari a 0 con sé stesso;durante l’esecuzione, tramite la tecnica del rilassamento degli archi, tali distanze da s nonché l’insieme deipredecessori di ogni nodo verranno definiti esplicitamente. Il rilassamento di un arco (u, v) ∈ E, con u ev nodi generici di V, consiste nel valutare se, utilizzando u come predecessore di v, si può migliorare ilvalore corrente della distanza: se ciò avviene allora si possono aggiornare sia le distanze che i predecessori(sostituendo eventualmente quelli ’passati’ con quelli migliorativi scoperti)4.

Pseudocodice:

Se d(v) > d(u) + distanza(u,v)

allora d(v) = d(u) + distanza(u,v)

e π(v) = u

A parole, molto in soldoni, si dice: ’Caro nodo v, ti risulta di essere ad una distanza maggiore di quella delnodo u (tuo potenziale predecessore) sommata alla distanza tra u e te? Allora sbagli! Sappi che arrivandoda u e imboccando l’arco che da u porta a te la distanza è inferiore a quella alla quale tu credi ora diessere. Quindi aggiorna la tua distanza con quella nuova, appena scoperta, e segnati che l’hai ottenuta apartire da u, che ora è il tuo predecessore’.

6.4.1 Bellman-Ford

La complessità di quest’algoritmo5 va con il prodotto E ·V.Dopo l’inizializzazione, l’algoritmo ripete per |V| − 1 volte6 il rilassamento di tutti gli archi del grafo

(l’ordine con cui si rilassano è arbitrario). Alla fine di questo procedimento, d(v) e π(v) saranno sicura-mente quelle di uno shortest path, ma non è escluso (anche se non è garantito) che la convergenza possaavvenire anche prima.

Pseudocodice:

Per i da 1 a |V| − 1Per ogni (u, v) appartenente a E

rilassa(u, v)

Principali svantaggi dell’algoritmo di Bellman-Ford (parleremo più diffusamente di questo aspetto dalparagrafo 6.6 in poi):

2Se il sottocammino tra i e j non fosse minimo cadremmo in un assurdo, in quanto nemmeno il cammino p tra il nodo 0 e il nodok sarebbe minimo (al suo interno esisterebbe una strada alternativa più breve tra i e j)!

3Il predecessore è il nodo attraverso il quale siamo passati immediatamente prima di arrivare a v.4L’operazione di rilassamento di un certo arco X può anche essere vista come una funzione che prende in pasto i due nodi

generici u e v collegati da X e il nodo sorgente s che fa da riferimento.5Riportiamo, per curiosità e completezza, anche cosa dice Wikipedia a proposito:

L'algoritmo di Bellman-Ford calcola i cammini minimi di un'unica sorgente su un grafo diretto pesato (dove alcuni pesi degli archipossono essere negativi). L'algoritmo di Dijkstra risolve lo stesso problema in un tempo computazionalmente inferiore, ma richiedeche i pesi degli archi siano non-negativi. Per questo, Bellman-Ford è usato di solito quando sul grafo sono presenti pesi degli archinegativi. Secondo Robert Sedgewick, 'I pesi negativi non sono solamente una curiosità matematica; [. . . ] si presentano in modonaturale quando riduciamo altri problemi a quelli di cammini minimi' [. . . ]. Se un grafo contiene un ciclo di peso totale negativoallora sono ottenibili pesi arbitrariamente piccoli e quindi non c'è soluzione; Bellman-Ford individua questo caso. L'algoritmo diBellman-Ford è nella sua struttura base molto simile a quello di Dijkstra, ma invece di selezionare il nodo di peso minimo, tra quellinon ancora processati, con tecnica greedy, semplicemente processa tutti gli archi e lo fa |V| − 1 volte, dove |V| è il numero di verticinel grafo. Le ripetizioni permettono alle distanze minime di propagarsi accuratamente attraverso il grafo poiché, in assenza di ciclinegativi, il cammino minimo può solo visitare ciascun nodo al più una volta. Diversamente da quello con tecnica greedy, il qualedipende da certe assunzioni strutturali derivate dai pesi positivi, questo semplice approccio si applica al caso più generale.

6|V|= cardinalità di V.

6.5. APPLICAZIONE ALLE RETI 65

Figura 6.5: Algoritmo di Bellman-Ford

• modesta scalabilità della rete;

• convergenza lenta: i cambiamenti nella topologia della rete non si riflettono velocemente nellacomposizione delle tabelle, poiché gli aggiornamenti sono fatti nodo dopo nodo;

• conto all’infinito: se si interrompe il collegamento con un nodo, gli altri nodi possono impiegareun tempo infinito per aumentare gradatamente la stima della distanza per quel nodo a meno dinon adoperare uno scalare come soglia, oltre il quale il nodo viene considerato non raggiungibile equindi fuori dalla rete.

6.4.2 Dijkstra

La complessità di quest’algoritmo va E + V log V.Dopo l’inizializzazione l’algoritmo crea un insieme S vuoto e, ad ogni passo, vi inserisce un nodo

dell’insieme S′ complementare ad S 7 avente distanza minima e rilassa tutti gli archi uscenti da tale nodoe diretti verso elementi di S′, interrompendosi quando S = V e S′ = ∅.

Finché S′ 6= ∅trova u ∈ S′ tale che la distanza d(u) = min{d(v), v ∈ S′}metti u in Stogli u da S′

per ogni v ∈ S′ tale che (u, v) ∈ Erilassa(u, v)

Si può dimostrare che, alla fine del ciclo, le d(v) e π(v) sono quelli di uno SP.Facciamo anche qui il tentativo di illustrare l’algoritmo in parole povere (anzi, poverissime): ’Partiamo

con i nodi tutti a distanza infinita tranne uno (quello di partenza), che è a distanza 0 da sé stesso e cheincluderemo nell’insieme S (pallini blu, v. fig. 6.6). A questo punto rilassiamo gli archi collegati a questonodo, i quali logicamente finiranno sui nodi adiacenti: dei nodi adiacenti ora scegliamo quello a distanzaminima, includiamolo in S e rilassiamo tutti gli archi ad esso collegati. Adesso parte la fase iterativa: sisceglie il nodo a distanza complessiva minore da quello di partenza, lo si include in S e poi si rilassanogli archi (e così via. . . ). Alla fine dell’algoritmo ogni nodo saprà a che distanza è da quello di partenzae, seguendo gli archi che hanno portato man mano all’inclusione dei diversi nodi nell’insieme S, si saràcostruito lo shortest path’.

In figura 6.6 si mostra un esempio grafico d’applicazione di tale algoritmo.

6.5 Applicazione alle reti

Una generica rete di telecomunicazioni si presta benissimo ad essere rappresentata con un grafo ori-entato dove i nodi sono i commutatori (router, switch, etc. . . ), gli archi sono i collegamenti e la loro

7Nel primo passo S′ = V perché S = ∅.


Figura 6.6: Esempio grafico d’applicazione dell’algoritmo di Dijkstra

orientazione indica la direzione di trasmissione. Il peso degli archi rappresenta il costo dei collegamen-ti che è intuitivamente funzione della distanza geografica, della congestione e della capacità della rete,etc. . . . Nei prossimi paragrafi vedremo proprio alcuni esempi di algoritmi di routing applicati alle reti.

6.5.1 Flooding

Trattasi di uno dei più elementari algoritmi di routing: ogni nodo semplicemente ritrasmette su tuttele porte d’uscita ogni pacchetto ricevuto. Un generico pacchetto verrà sicuramente ricevuto da tutti i nodi(anche in copie multiple) e quindi anche da quello a cui è effettivamente destinato. Dal momento chetutte le strade possibili sono percorse, il primo pacchetto che arriva a un nodo è anche quello che ha fattola strada più breve possibile (shortest path). Questo algoritmo è molto adatto alle trasmissioni broadcast erichiede pochissima elaborazione, ma nasconde molte insidie:

• un nodo potrebbe ritrasmettere il pacchetto da duplicare anche nella direzione dalla quale è giunto,ma questa operazione è - com’è intuibile - assolutamente inutile;

• se, come è normale che sia, alcuni punti della rete possono essere raggiunti da più parti (nodi), allorapotrebbero pervenire in uno stesso luogo numerosissime (e inutili) copie di uno stesso pacchetto, conla spiacevole conseguenza che la rete si potrebbe congestionare molto facilmente;

• infine, quando un nodo ha già tramesso il pacchetto a tutti i suoi collegamenti, è superfluo ripeteretale operazione se dovessero giungere altri identici pacchetti da altre destinazioni.

Per tali motivi un algoritmo del genere non può essere preso nudo e crudo, ma necessita di qualcheaggiustamento:

• si impedisce la ritrasmissione sul nodo dal quale è arrivato il messaggio (’me l’ha mandato lui, cosaglielo rispedisco a fare?!’);

• ad ogni pacchetto viene associato un identificativo unico e ciascun nodo mantiene in memoria unalista con gli identificativi dei pacchetti già trasmessi (ignorando i duplicati). Ogni nodo, quindi, faràflooding di un certo pacchetto solo una volta e non ripeterà mai più la sua trasmissione su tutte leinterfacce;

6.5. APPLICAZIONE ALLE RETI 67

• si trasmette solo lungo lo spanning tree, cosicché i pacchetti non possono ciclare (cioè ’fare il giro’) epercorrere strade già battute da altri.

Quanto detto sopra vale anche per l’interconnessione di più LAN, anche di tipo diverso, attuata al finedi estendere il dominio di broadcast: lo spanning tree può essere costruito sulla base delle differenti reti ediventa il canale preferenziale per evitare che vi sia un’eccessiva proliferazione di trame duplicate in giroper la rete (v. figura 6.7).

Figura 6.7: Interconnessione di più LAN e spanning tree

6.5.2 Deflection routing

Questo tipo d’algoritmo (detto anche hot potato) è adatto alle reti in cui i nodi di commutazione dispon-gono di spazio di memorizzazione molto limitato e in cui si desidera minimizzare il tempo di permanenzadei pacchetti nei nodi. In base alla regola del deflection routing, infatti, quando un nodo riceve un pacchettolo deve ritrasmettere sulla linea d’uscita avente il minor numero di pacchetti in attesa di essere trasmessi.Tale politica può generare qualche inconveniente:

• i pacchetti possono essere ricevuti fuori sequenza (non sempre la coda più breve è quella che portaalla destinazione corretta: i pacchetti potrebbero sparpagliarsi chissà dove e arrivare a destinazionein un ordine assolutamente casuale);

• alcuni pacchetti potrebbero percorrere all’infinito un certo ciclo in seno alla rete, semplicementeperché le sue linee sono poco utilizzate e, di conseguenza, vengono scelte sempre loro8;

• si tiene poco conto della destinazione finale del pacchetto.

6.5.3 Load sharing

Trattasi di una scelta ibrida fra il flooding (spariamo tutto dappertutto) e il deflection routing (mandi-amo solamente nella coda più corta); si legge su di una tabella la linea d’uscita preferenziale verso ladestinazione finale del pacchetto e si accoda su di essa solo se:

• la coda non supera una soglia;

• non vi sono altri pacchetti richiedenti contemporaneamente tale linea d’uscita.

Se le condizioni non permettono questa scelta, il pacchetto viene inviato sulla linea d’uscita avente coda ditrasmissione più breve. Così facendo, in condizioni di basso carico della rete, l’instradamento non vienefatto senza criterio e bovinamente (come nel caso hot potato), ma sulla base dell’effettiva destinazionefinale. Se invece siamo fortemente congestionati può essere conveniente prendere una deviazione (cioèimboccare una coda d’uscita che non coincide con la direzione preferenziale) piuttosto che mettersi in unacoda molto lunga.

8Una possibile soluzione a questo problema è quella di fissare un tempo di vita per i pacchetti.


6.6 Shortest Path Routing

Tale filosofia di routing associa una lunghezza ad ogni collegamento della rete e l’algoritmo cerca lastrada di lunghezza minima fra ogni mittente e ogni destinatario. A questo proposito vengono utilizzati glialgoritmi di Bellman-Ford (v. par. 6.4.1) e di Dijkstra (v. par. 6.4.2) in modalità centralizzata o distribuita.

Sia che decidessimo di utilizzare l’uno oppure l’altro, dobbiamo però stare attenti ad uno degli aspettipatologici di questo tipo di algoritmi; supponiamo di avere due percorsi, uno di costo d1 e l’altro di costod2 > d1: l’algoritmo che scegliesse sempre e comunque il percorso di costo minimo intaserebbe la linea conparametro d1 e non invierebbe niente su quella di costo d2. Per questo si cerca di fare un uso probabilisticodella tabella di routing, ad esempio istradando i pacchetti su tutte le uscite disponibili con probabilitàinversamente proporzionale al peso del cammino corrispondente: grazie a questo stratagemma rendiamola distribuzione del traffico più uniforme sui vari link della rete ma anche questa volta, come nel deflectionrouting (v. par. 6.5.2), rischiamo di ricevere pacchetti fuori sequenza.

6.6.1 Protocolli distance vector

Si basano sull’algoritmo di Bellman-Ford, ma ne costituiscono una versione distribuita9. Ogni nodo:

1. Scopre i suoi vicini e calcola la distanza da se stesso.

2. Invia ai propri vicini un vettore contente la sua distanza da tutti gli altri nodi della rete (quelli di cuiè a conoscenza).

3. Esegue un’operazione di ’rilassamento’ (v. par. 6.4) verso ogni altro nodo.

4. Eventualmente, aggiorna la stima della distanza e il next-hop.

Figura 6.8: Esempio di calcolo delle tabelle di routing

9Proposta da Ford-Fulkerson.

6.6. SHORTEST PATH ROUTING 69

In figura 6.8 viene riportato un esempio10 di costruzione delle tabelle di routing; immaginiamo di essere ilnodo A: inizialmente la sua tabella di routing è, come indicato,

DV(A) = {(A, 0), (B, 1), (C, 6)}

1. A riceve DV(B) = {(A, 1), (B, 0), (C, 2), (D, 1)}: A scopre che, attraverso B (distante 2 da C), puòarrivare in C in 3 passi (1 per raggiungere B e 2 per raggiungere C da B) così aggiorna il suo distancevector sostituendo il vetusto (C, 6) col nuovo (C, 4); inoltre, inserisce la entry (D, 2) dove 2 significa{1 per arrivare a B}+{1 per passare da B a D}. Anche la tabella di routing risente di queste modifichee, infatti (v. fig. 6.8), si indica che si può raggiungere sia C che D in due passi attraverso B (next-hop);

2. A riceve DV(C) = {(A, 6), (B, 2), (C, 0), (D, 3), (E, 7)}: la tabella di routing viene aggiornata con lariga facente riferimento al nodo E, ora raggiungibile attraverso C (distanza: 10 = 7 + 3). Le altreentry, invece, non vengono modificate perché B rimane un referente più comodo (dista 1 invece che6!);

3. B riceve DV(D) = {(B, 1), (C, 3), (D, 0), (E, 2)}: concentriamoci per un attimo sulla tabella di routingdi B (v. la solita figura). Anche B, come A non conosceva la strada per arrivare ad E: D glielasuggerisce, dicendogli che dista 2 da E, cosicché B si convince di distarvi 3 = 1 + 2 (al solito, unpasso per arrivare a D e due per andare da D ad E);

4. A riceve DV(B)aggiornata = {(A, 1), (B, 0), (C, 2), (D, 1), (E, 3)}: il passo precedente ha aggiornato latabella di routing di B e quindi anche il suo distance vector, che ora contiene (E, 3); quando A ricevequesta nuova informazione, abbandona C come next-hop per arrivare a E e seleziona B, calcolandola distanza come 1 (per arrivare a B) + 3 (distanza di B da E) = 4.

Diamo un rapido sguardo sui vantaggi e svantaggi di questo approccio:VANTAGGI:

• semplicità implementativa;

• richiede poche risorse.

SVANTAGGI11:

• partenza lenta (cold start): allo start-up le tabelle dei singoli nodi non contengono informazioni senon la distanza di questi ultimi da loro stessi (pari a 0, sai che roba. . . ). Da quel momento in poilo scambio dei distance vector permette la creazione di tabelle sempre più complete e l’algoritmoconverge al più dopo un numero di passi pari al numero di nodi della rete12: se la rete è moltogrande, di conseguenza, la convergenza sarà lunga, con il fastidioso effetto collaterale che - se nelfrattempo cambia lo stato della rete - l’algoritmo potrebbe incepparsi e la convergenza non arrivaremai (v. convergenza lenta);

Figura 6.9: Bouncing effect

10Anche questo tratto dalle slide del Prof. Callegati, ’Applicazione alle reti’, slide 11.11A parte la cold start, che è fisiologica, tutti gli inconvenienti illustrati in elenco sono dovuti al fatto che i distance vector vengono

inviati, fra i nodi, senza un particolare coordinamento o arbitraggio. Inoltre, alcuni pacchetti potrebbero sopravvivere per untempo sufficiente da permettere la contemporanea sussistenza di informazioni errate o obsolete, le quali sono in grado di generare’incomprensioni’ fra nodi non recepenti la corretta distanza da una certa destinazione.

12Come Bellman-Ford, v. par. 6.4.1.


• bouncing effect: si faccia riferimento alla figura 6.9. Supponiamo che il link fra A e B assumacosto +∞ a causa della caduta del collegamento: in tal caso A e B si accorgono dell’anomalia eimmediatamente pongono ad infinito la lunghezza di tale collegamento. In giro per la rete, però,potrebbero esistere dei distance vector obsoleti in cui quel collegamento c’è ancora ed è funzionante(con costo 1). In figura, C potrebbe aver inviato ad A il DV(C) = {(A, 2), (B, 3)} ed A aver inviato aC l’informazione (B, +∞) cosicché:

– A crede di poter andare a B tramite C con costo 5 = 2 + 3, dove il ’3’ è specificato nel DV(C);

– C crede che attraverso A non si possa più andare a B quindi si convince di poter raggiungerequest’ultimo solo tramite il collegamento di costo 6.

Tra questi due punti, però, c’è un’incongruenza temporanea che vede C ed A mandarsi compulsi-vamente e senza soluzione di continuità pacchetti destinati a B. Il bouncing effect consiste quindi inmomenti patologici in cui due o più nodi si scambiano datagrammi palesemente errati fino a chenon si esaurisce il TTL o non si converge nuovamente.

Figura 6.10: Convergenza lenta

• convergenza lenta: se, ad esempio, due nodi sono collegati fra loro e contemporaneamente collegatia un terzo nodo, e uno di questi collegamenti si deteriora fortemente, potrebbe succedere che i duenodi impieghino molto tempo per recepire il nuovo itinerario (v. fig. 6.10);

Figura 6.11: Il problema del count to infinity

• conteggio all’infinito (count to infinity): esaminiamo la figura 6.11. Immaginiamo che il collegamentotra B e C vada fuori servizio: A dice ad B di distare 2 da C, così B si convince di poter andare a Cpassando da A con distanza 3 (cosa in realtà impossibile visto che A, a sua volta, si appoggia ad B).

6.7. SOLUZIONI MIGLIORATIVE AI PROTOCOLLI DISTANCE VECTOR 71

B comunica quindi la sua nuova distanza da C ad A che, a sua volta, decide di trovarsi a distanza 4(deve sfruttare B, che si appoggia A, il quale passerebbe tramite B!). La cosa potrebbe andare avantiall’infinito (appunto), ma per fortuna questo problema è facilmente risolvibile imponendo una sogliaoltre la quale una certa destinazione viene marcata come irraggiungibile.

6.7 Soluzioni migliorative ai protocolli distance vector

Di seguito verranno riportate alcune possibili scelte migliorative per i nostri protocolli. Si vuole peròsottolineare che alcune situazioni fortemente patologiche (v. fig. 6.12) non possono in nessun modo essererisolte: nessuno fra i metodi esposti nei paragrafi 6.7.1 e 6.7.2 è quindi davvero risolutivo.

Figura 6.12: Situazione patologica e irrisolvibile

6.7.1 Split Horizon

Il concetto è molto semplice: se A instrada i pacchetti verso una certa destinazione X tramite B, nonha senso che quest’ultimo cerchi di raggiungere X tramite A e, di conseguenza, è inutile che A dica a B lasua distanza da X! Quest’algoritmo è elementare così come la sua implementazione: l’unica cosa in piùche si chiede di fare ai router è di inviare informazioni diverse ai diversi vicini. Esistono due versioni perlo split horizon:

• in forma semplice: A omette la sua distanza da X nel DV che invia a B;

• poisonous reverse: A inserisce tutte le destinazioni nel DV diretto a B, ma pone la distanza da Xuguale a +∞.

6.7.2 Triggered Update

Se le informazioni sulla distanza vengono inviate periodicamente può capitare che distance vector legatiad un cambiamento della topologia della rete (ad esempio un guasto, oppure l’introduzione di un nuovonodo) partano in ritardo e vengano sopravanzati da informazioni datate e quindi scorrette. Il triggeredupdate risolve questa situazione imponendo l’invio immediato delle informazioni a tutti i vicini qualorasi verifichi una modifica della tabella di instradamento (sempre per il solito guasto o per il cambio ditopologia).

6.8 Protocolli path vector

L’unica soluzione davvero risolutiva a tutti gli inconvenienti fin qui illustrati (v. par. 6.6.1) è quelladi cambiare la filosofia di comunicazione delle distanze: in base ai protocolli path vector, ad esempio, ilvettore che ogni router manda ai vicini contiene, oltre alle distanze dagli altri nodi, anche l’intero camminoche il pacchetto deve seguire; l’algoritmo implementato nel router che riceverà tali informazioni ignoreràtutti i cammini dove compare lui stesso e questo impedirà la possibilità che si formino cicli (che sono unadelle cause dei problemi dei protocolli distance vector). Il prezzo da pagare, com’è intuitivo, sta in nellamaggiore mole di informazioni da scambiare.


6.9 Protocolli link state

Grazie a tale tipo di protocolli ogni nodo si procura un’immagine della topologia della rete e, sulla basedi tale immagine, calcola le tabelle di routing13. Ogni router deve chiaramente scoprire chi sono i proprivicini e imparare i loro indirizzi: ciò viene fatto tramite l’invio di Hello Packet. La distanza dai vicini vieneinvece scoperta grazie ai pacchetti che questi spediscono di rimando (Echo Packet). Con le informazioniricavate in tal modo è possibile, per ogni router, costruire una lista dei vicini corredata con le distanze daquesti ultimi e racchiuderla in un Link State Packet (LSP) da propagare in giro tramite il flooding14 (v. par.6.5.1). A tal fine nel pacchetto LSP occorre aggiungere l’indirizzo del mittente, un numero di sequenza(per rimuovere i doppioni) e una indicazione dell’età del pacchetto (per eliminare quelli obsoleti). Infine,costruita l’immagine della rete, tipicamente si usa l’algoritmo di Dijkstra per calcolare i cammini minimiverso ogni altro router.

Rispetto ai protocolli distance vector, quelli di tipo link state sono più complicati da implementare erichiedono un quantitativo superiore di memoria; per contro, tuttavia, offrono maggiori funzionalità intermini di gestione di rete, permettono una convergenza migliore (per velocità ed affidabilità) e si adattanomeglio ai cambi di topologia (guasti, aggiunta di nuovi collegamenti, etc. . . ).

6.10 In sintesi

Un grafo è un'entità de�nita da un insieme di archi E i quali connettono un insieme nodi V. Un grafo può

essere:

• orientato se gli archi hanno un orientamento (non orientato viceversa);

• pesato se ad ogni arco è associato un costo;

• connesso se a partire da qualunque nodo è possibile raggiungere tutti gli altri (in uno o più passi);

• completamente connesso se ogni nodo è connesso a tutti gli altri da un solo arco;

• aciclico se non contiene nessun ciclo;

• un sottografo di un altro grafo se contiene un sottoinsieme di nodi e/o di archi di quest'ultimo;

• un albero (tree) se è aciclico e connesso;

• uno spanning tree se è stato ricavato da un certo grafo G che invece non era aciclico (ma era connesso);

• un minimum spanning tree se la somma dei pesi dei suoi archi è minima.

Un cammino tra un nodo ed un altro è invece:

• ciclico se ha stesso nodo di partenza e d'arrivo;

• semplice se non passiamo due volte per lo stesso nodo;

• minimo se è quello a costo minore fra tutti quelli possibili (un cammino minimo è sicuramente semplice;

principio di ottimalità: un sottocammino di un cammino minimo è minimo).

Esistono due algoritmi per il calcolo dell'MST:

• Kruskal (complessità: E log V): scegliamo dal grafo G di partenza man mano gli archi di peso minore e

li includiamo nel sottografo A, �no a collegare tutti i nodi. Durante l'algoritmo il sottografo A può essere

non connesso, ma al termine sarà il MST;

• Prim (complessità: E + V log V): partiamo da un nodo sorgente di G, scegliamo l'arco di peso minimo ad

esso e lo includiamo in A assieme all'altro nodo cui è collegato. Poi iteriamo aggiungendo il nuovo nodo

di A a peso minimo e così via, �no a collegare tutti i nodi. Durante l'algoritmo il sottografo A è sempre

connesso e al termine sarà il MST.

13Nel caso di reti di grandi dimensioni non è possibile gestire le tabelle di routing per l’intera rete in tutti i router: in questo casoil routing deve essere gerarchico.

14Il flooding di pacchetti LSP può provocare un aumento significativo di traffico, quindi bisogna prestarvi attenzione.

6.10. IN SINTESI 73

Esistono due algoritmi principali per il calcolo del cammino minimo avente il generico nodo s come nodo di

partenza (fasi comuni: inizializzazione→ mettiamo tutti i nodi a distanza in�nita da s tranne s stesso; rilassamento→ il rilassamento dell'arco di peso d(u, v) che connette due generici nodi u e v prevede che si scelga u come

predecessore per v nel caso la distanza d(u) di u da s sommata a d(u, v) sia maggiore di quella precedentemente

misurata per v con qualche altro predecessore). Essi sono:

• Bellman-Ford (complessità: EV): rilassiamo gli archi tante volte quanti sono i nodi meno 1. Possiamo

convergere anche prima di aver fatto tutte queste iterazioni, ma cioè non è assicurato (mentre lo è dopo

|V| − 1 'giri' di rilassamento);

• Dijkstra (complessità: E + V log V): partiamo dal nodo sorgente s (l'unico che inizialmente popola l'in-

sieme S′ complementare ad S, il quale inizialmente contiene tutti i nodi) e rilassiamo gli archi a lui connessi.

Scegliamo il nodo a distanza minima e lo includiamo in S′, poi rilassiamo gli archi a lui collegati e iteriamo

il procedimento sopra descritto. Quando tutti i nodi saranno �niti in S′ l'algoritmo avrà termine.

Al termine avremo ben noti, per ogni nodo dello shortest path, il predecessore e la distanza dal nodo sorgente s.

La teoria dei gra� si presta benissimo allo studio delle reti di telecomunicazioni se facciamo l'ovvio parallelismo

fra {nodi, rami} e {router, collegamenti}. In una rete reale è di fondamentale importanza capire quale sia la

migliore strategia di routing; le alternative che si paventano alla nostra attenzione sono:

• �ooding: ogni router spedisce tutto dappertutto (il destinatario sicuramente riceverà qualcosa!). Questa

scelta implica pochissima elaborazione ed è prefetta per la trasmissione broadcast, ma congestiona la rete

con estrema facilità: i miglioramenti possibili consistono nel numerare i pacchetti (per scartare quelli già

inviati), non ritrasmettere dalla via che ci ha propinato il pacchetto oppure trasmettere sullo spanning tree;

• hot potato: i router inoltrano i pacchetti nelle code più brevi fra quelle dell'interfaccia d'uscita. Ciò fa sì

che non si tenga conto dell'e�ettiva destinazione �nale e si rende inoltre frequentissima l'eventualità che i

pacchetti arrivino fuori sequenza, ma è una scelta buona se i router hanno poca memoria per trattenere i

messaggi;

• load sharing: i router hanno una tabella dove sono scritte le uscite preferenziali per ogni determinato

pacchetto. Tale uscite vengono imboccate solo se non sono troppo congestionate o se non vi sono altri

pacchetti che le richiedono. Si tratta di una soluzione sicuramente più smart del semplice hot potato;

• shortest path routing : si calcola la strada avente costo (peso) minimo. A tal proposito tornano utilissimi

Dijsktra e Bellman-Ford; si tenga però presente che è necessario un uso probabilistico della tabella di routing,

in quanto prendere sempre e sistematicamente il percorso di peso minimo rende altamente probabile un suo

congestionamento. All'interno di questa categoria troviamo:

– protocolli distance vector : si basano su Bellman-Ford. Ogni nodo calcola la distanza di sé stesso

dagli altri e invia queste informazioni (sotto forma di distance vector) ai nodi vicini, i quali possono

utilizzarle per e�ettuare il rilassamento degli archi, scoprire nuovi percorsi e aggiornare quelli già in

lista. Si tratta di un protocollo semplice, che però nasconde molte insidie (alcune delle quali, ahimè,

sono irrisolvibili):

∗ cold start: potrebbe volerci molto tempo per avere una tabella di routing degna di questo nome.

C'è caso, infatti, che l'algoritmo sia parecchio lento a convergere (o che non riesca proprio ad

arrivare a convergenza, se qualcosa si rompe);

∗ bouncing e�ect: se si guasta un collegamento, due nodi (aventi informazioni poco aggiornate

sulla rete) potrebbero rimpallarsi i pacchetti, ciascuno fermo nella convinzione che attraverso

l'altro si possa raggiungere un nodo che ora è a distanza ∞ a causa del guasto. Finché non

vengono spediti dei distance vector aggiornati, questo problema sussiste;

∗ count to in�nity : A, B e C sono collegati (con�gurazione: A− B− C). Si rompe il link B− C:B ed A si illudono di poter raggiungere C l'uno attraverso l'altro, con l'assurdo di B che sfrutta

A (che a sua volta usava B!) per arrivare al tanto agognato C;∗ convergenza lenta: se un collegamento non cade, ma si degrada fortemente, è possibile che ci

voglia molto tempo a propendere per una strada alternativa che magari, prima del guasto, era

considerata poco conveniente.


Alcuni possibili miglioramenti consistono nell'implementazione di triggered update (appena si modi�ca

la topologia vengono inviati i distance vector aggiornati) e di split horizon (se A va a C tramite B, Anon deve dire a B come arrivare a C).

– protocolli path vector : non si spedisce la distanza dai vicini, ma l'intero percorso. Serve molta più

memoria rispetto al caso distance vector, ma si evitano tutte le condizioni patologiche sopra indicate

in quanto i router diventano in grado di evitare i cicli;

– protocolli link state: i nodi si costruiscono un'immagine della rete grazie alle informazioni raccolte

mediante un determinato protocollo in grado di regolare la conversazione fra i nodi stessi. Ogni router

scopre i vicini (hello packet) e calcola la distanza dagli stessi (echo packet), poi racimola tutte le

informazioni e le spedisce, tramite �ooding, sotto forma di LSP (link state packet). Anche se il

�ooding può rivelarsi problematico, questi protocolli o�rono molte più funzionalità di quelli distance

vector e convergono più velocemente.

Capitolo 7

IGP: Interior Gateway Protocols

7.1 RIP

Si tratta di un protocollo di tipo distance vector molto diffuso in passato e utilizzato praticamente solosu reti TCP/IP. Sfrutta la porta 520 (sia in ricezione che in trasmissione), si regge su UDP e utilizza duetipi di messaggi:

• request: si chiedono esplicitamente informazioni ai nodi vicini;

• response: si inviano ai vicini le informazioni di routing (i distance vector).

Ogni riga della tabella di routing costruita dal RIP contiene:

• l’indirizzo di destinazione (IP 32 bit), corredato dalla netmask (si utilizza la suddivisione per classidi reti e non le specifiche del CIDR);

• la distanza (metrica) dalla destinazione in termini di hop-count, con un massimo di 16 (che vale come+∞);

• il next-hop.

Inoltre il meccanismo prevede due contatori: il timeout, che scade se entro 180 secondi non si hannonotizie di una route (la si mette a costo +∞), e il garbage-collection timer, che elimina del tutto tale routedopo ulteriori 120 secondi.

Un messaggio response con nuove informazioni di routing viene inviato periodicamente (ogni 30 sec-ondi con uno scarto di ±5 secondi per evitare aggiornamenti a raffica), oppure come risposta ad unarichiesta esplicita, o anche qualora cambiasse la topologia della rete (triggered update). Quando si riceveun response viene inizialmente controllata la correttezza dei dati presenti nel distance vector ricevuto (indi-rizzi IP e metriche validi) quindi si considerano solo le voci con distanze di non infinite, le quali vengonoincrementate di una unità (le di sono le distanze del nostro vicino dagli altri nodi: siccome esso dista unhop da noi, gli ’altri’ a loro volta disteranno di + 1) e poi, per ogni destinazione:

• se non esiste una entry corrispondente nella tabella, viene creata: la distanza è quella appenaincrementata, il next-hop è il mittente del response e si fa partire il timeout;

• se nella tabella esisteva già una entry ed ha distanza maggiore di quella indicata, la entry vieneaggiornata con la nuova (e minore) distanza, poi si fa ripartire il timeout;

• se esiste già una entry verso tale destinazione ed il next-hop è lo stesso che ha inviato il response, laentry viene aggiornata se diversa dal valore precedente. Si fa inoltre ripartire il contatore del periododi vita.

Si noti che questa sequenza di operazioni ricorda moltissimo il principio di rilassamento degli archi (v.cap. 6).

Il formato dei pacchetti1 è quello indicato in figura 7.1. Il RIP fa uso dello split horizon, per cui i mes-saggi di risposta potrebbero essere diversi in base a quale interfaccia d’uscita facciano riferimento; inoltre,

1I messaggi del RIP sono formati da parole di 32 bit, fino a un massimo di 512 byte. All’interno del pacchetto troviamo i campi:

75

76 CAPITOLO 7. IGP: INTERIOR GATEWAY PROTOCOLS

Figura 7.1: Formato del pacchetto RIP

in caso di triggered update, vengono indicate nella response solo le entry modificate.

Fra i risvolti negativi del RIP: è un protocollo distance vector quindi, nonostante i meccanismi cor-rettivi soffre comunque dei problemi illustrati all’inizio del paragrafo 6.7, e può presentare problemi diconvergenza; inoltre non è sicuro, in quanto chiunque trasmetta datagrammi dalla porta UDP 520 vieneconsiderato come un router autorizzato. Funziona infine maluccio con le reti grandi. Parte di questequestioni vengono risolte con il RIP versione 2, che permette l’indirizzamento CIDR e ha un sistema diautenticazione per chi invia i messaggi, oltre a implementare altre migliorie.

7.2 OSPF: Open Shortest Path First

Si tratta di un protocollo di tipo link state, oggi il più diffuso: prevede l’invio di Link State Advertisement(LSA) a tutti i router, è incapsulato direttamente in IP ed è stato progettato per semplificare il routing inreti medio-grandi e grandi. Grazie a tale tipo di protocollo, infatti, riusciamo ad effettuare il cosiddettorouting gerarchico: esso consiste nel ripartire grandi porzioni di rete chiamate Autonomous Systems (AS) insotto-ripartizioni, chiamate Routing Areas (RA), come mostrato in figura 7.2. I router all’interno di unaRA (internal router) effettuano l’instradamento relativamente alla sola area, mentre per destinazioni al difuori dell’area si limitano ad inviare i pacchetti a dei router ’di bordo’ (Area Border Router) che si occupanounicamente dell’instradamento dei pacchetti fra aree e sono a conoscenza della topologia esterna all’area.Abbiamo infine gli AS Boundary Router, che scambiano informazioni con altri AS usando un protocolloEGP (v. cap. 8), e i Backbone Router, che si interfacciano con il backbone. Esaminando nuovamente lafigura 7.2 si può notare la presenza di una Stub Area; essa è tipicamente un’area avente un solo punto diinterconnessione con il resto della rete: l’instradamento verso l’esterno della stub area viene effettuato conla tecnica del default route (esiste un solo punto d’uscita verso tutte le destinazioni possibili, oppure piùpunti ma non è necessario trovare un percorso ottimo per uscire dall’area), mentre i percorsi verso retiesterne alla stub area non vengono propagate da OSPF internamente alle stesse. Questa è un’altra delletecniche atte a ridurre le dimensioni della tabella di routing, col vantaggio che il router di bordo necessitadi poca memoria per funzionare al meglio.

L’OSPF è molto smart e contempla:

• il bilanciamento del carico: se un router ha più percorsi di uguale lunghezza verso una certadestinazione, i pacchetti vengono ripartiti equamente fra essi;

• command: distingue tra REQUEST (1) e RESPONSE (2);

• version: versione del RIP;

• address family identifier: indica il tipo di indirizzo di rete utilizzato, vale 2 per IP;

• address: identifica la destinazione per la quale viene data la distanza;

• metrica: è la distanza dalla destinazione indicata.

7.2. OSPF: OPEN SHORTEST PATH FIRST 77

Figura 7.2: Schema concettuale del routing gerarchico

• autenticazione tramite uso di password e crittografia, per garantire maggiore sicurezza nello scambiodelle informazioni di routing (il RIP era molto vulnerabile sotto questo punto di vista);

• la gestione intrinseca di reti punto-punto e punto-multipunto;

• routing dipendente dal grado e dalla priorità del servizio (la scelta del percorso è presa anche sullabase delle informazioni contenute nel campo Type of service).

7.2.1 Distinzione logica fra host e router

I router sono gli unici responsabili del routing, mentre gli host sono unicamente punti terminali daraggiungere: se, in particolare, essi fanno parte di una certa LAN, verranno identificati con la LAN stessa(v. fig. 7.3) così da snellire molto le tabelle di routing. Come ulteriore conseguenza, verranno diffuseinformazioni relative alla irraggiungibilità di intere reti e non dei singoli host.

Figura 7.3: Distinzione logica fra host e router


7.2.2 OSPF e reti multi-accesso

L’OSPF lavora bene con reti punto-punto e multi-accesso (es. LAN). Per quest’ultima tipologia, inparticolare, l’OSPF adotta una rappresentazione a stella equivalente per evitare di inviare miriadi di LSA.Prendiamo ad esempio le reti in figura 7.4: tutti gli N router al loro interno sono di fatto connessi con tuttigli altri. Nella rete a maglia completa il numero di archi bidirezionali è pari a

N(N − 1)2

+ N

e il numero totale di LSA da trasmettere è N(N − 1).

Figura 7.4: Alcuni tipi di reti multiaccesso

Se però facciamo finta di introdurre un nodo virtuale che rappresenta la rete (v. figura 7.5), gli archibidirezionali che bastano a collegare tutti con tutti sono soltanto N. Il risparmio, come s’intuisce, ènotevole.

Figura 7.5: Topologia a stella equivalente (con nodo virtuale)

L’OSPF chiama (v. figura 7.6):

• vicini: due router che sono connessi alla medesima rete e possono quindi colloquiare tramite in-stradamento diretto;

• adiacenti: due router che si scambiano informazioni di routing;

• designated router DR (router designato2): nelle reti ad accesso multiplo (come le LAN) è tale per cuiogni router è suo adiacente e lo scambio di informazioni di routing avviene solo fra lui e ogni routerpreso singolarmente; il DR è inoltre l’unico a comunicare la raggiungibilità di router e host dellaLAN al mondo esterno. Grazie a questi accorgimenti riusciamo a realizzare la situazione illustratain figura 7.5.

2Al quale viene affiancato anche un BDR, Backup Designated Router, per ragioni di affidabilità.

7.2. OSPF: OPEN SHORTEST PATH FIRST 79

Figura 7.6: Router vicini e router adiacenti

Ogni router ha il suo ID univoco (router-ID) (di default si prende quello più alto fra quelli assegnati alleinterfacce del router) nonché un valore di priorità, compreso fra 0 (default) e 255, utilizzato nell’elezionedel DR. Per eleggere il Designated Router ciascun nodo nella rete ad accesso multiplo, in base all’OSPF:

1. esamina la lista dei suoi vicini;

2. elimina i router non eleggibili (ad esempio quelli con priorità 0);

3. fra quelli rimasti elegge quello a priorità maggiore;

4. rimuove dalla lista dei vicini il DR e sceglie nuovamente il router a priorità maggiore, eleggendolocome nodo designato di backup.

Detto questo, l’OSPF ha bisogno di un grafo orientato per poter calcolare lo shortest path tree (v. cap.6): esso viene calcolato a partire dai Link State Advertisement3 ed è presente in ogni router sotto il nome diLink State Database.

7.2.3 Messaggi dell’OSPF

OSPF invia i suoi messaggi utilizzando direttamente il protocollo IP4: tutti i messaggi hanno un’intes-tazione comune5, dopodiché il resto si differenzia in base alla tipologia del messaggio (v. figura 7.7 pervedere come tali tipologie concorrono allo scambio di informazioni e alla sincronizzazione nell’OSPF):

3Esistono diversi tipi di LSA:

• router-LSA: creati da ogni router e diffusi in una singola area, contengono le informazioni relative allo stato delle interfaccedel router all’interno di quell’area;

• network-LSA: creati dal DR di ogni rete ad accesso multiplo e diffusi in una singola area, contengono l’elenco dei routerconnessi a quella rete;

• summary-LSA: creati dagli Area Border Router e diffusi in una singola area, contengono informazioni di routing perdestinazioni appartenenti ad altre aree dello stesso AS;

• AS-boundary-router-summary-LSA: creati dagli Area Border Router e diffusi a tutte le sue aree, contengono informazioni dirouting per raggiungere gli AS-boundary router;

• AS-external-LSA: creati dagli AS-boundary router e diffusi a tutto l’AS, contengono informazioni di routing per destinazioniappartenenti ad altri AS (compresa la default route).

4Il campo protocol ha valore 89.5Campi dell’intestazione:

• Version indica la versione di OSPF (versione 2);

• Type indica il tipo di pacchetto;

• Packet Length numero di byte del pacchetto;


• messaggio hello: serve a controllare l’operatività dei link, a eleggere il designated router, a scopriree mantenere le relazioni coi vicini. Sono mandati periodicamente e contengono una lista di tutti ivicini dai quali è stato ricevuto un pacchetto hello di recente;

• messaggi per l’exchange protocol: una volta stabilite le adiacenze, è necessario che i router sincronizzi-no i rispettivi Link State Database (dove, abbiamo detto, sono contenute le informazioni sulla topolo-gia della rete). La procedura di sincronizzazione è asimmetrica in quanto, nella comunicazionefra due router, si stabilisce chi è il master e chi è lo slave: il primo invia messaggi al secondo, cherisponde, ed entrambi confrontano le informazioni ottenute con quelle in proprio possesso;

• messaggi per il flooding: serve a diffondere gli LSA a tutti i router della rete e scatenare un aggior-namento ’a tappeto’. Viene inoltre richiesta conferma di ricezione.

Figura 7.7: Le fasi necessarie per lo scambio di informazioni e la sincronizzazione nell’OSPF

7.3 In sintesi

Gli IGP (Interior Gateway Protocol) sono i protocolli che si occupano del routing all'interno degli Autonomous

Systems (AS). Uno dei protocolli storici e ora in disuso, di tipo distance vector, è il RIP (Routing Information

Protocol); il RIP si appoggia alla porta UDP 520 e presenta una dinamica che si regge su due messaggi (fatti di

parole di 32 bit):

• request: si richiedono esplicitamente informazioni ai nodi vicini;

• Router ID indirizzo IP che identifica il router mittente;

• Area ID identifica l’area di appartenenza;

• Checksum calcolata su tutto il pacchetto OSPF; escludendo gli 8 byte del campo authentication (come per l’algoritmo classicodi IP);

• AuType indica il tipo di autenticazione (nessuna, semplice o crittografica).

7.3. IN SINTESI 81

• response: i nodi vicini rispondono inviando le loro informazioni di routing. Un messaggio di questo tipo

può essere inviato solo a causa di request esplicita, di un cambiamento di topologia della rete (triggered

update) o anche periodicamente ogni 30± 5 secondi (con un piccolo scarto per non intasare la rete).

Ogni riga della tabella di routing costruita dal RIP contiene l'indirizzo IP/Netmask di destinazione (32 bit, con

logica 'classista' pre-CIDR), la distanza in termini di hop-count (con un massimo di 16 = +∞) e il next-hop. Vi

sono poi due contatori: il timer mette la distanza di una certa route a +∞ se da essa non si hanno notizie entro

3 minuti, mentre il garbage-collector timer elimina del tutto tale route se si fa attendere per altri 2 minuti. La

tabella di routing si popola in questo modo: una volta che un certo nodo A ha ricevuto le distanze di inviategli

da B, le incrementa di uno (per considerare il link A− B) e poi

• se non aveva l'entry: l'aggiunge e poi resetta il timer;

• se l'aveva: eventualmente l'aggiorna (mettendo B come next-hop se è a distanza inferiore rispetto a quella

suggerita dalle informazioni precedenti presenti in tabella), poi resetta il timer.

Nonostante faccia uso di split-horizon e triggered-update il RIP so�re delle patologie di tutti i protocolli distance

vector, è insicuro (si appoggia su UDP senza crittogra�a e autenticazione) e ignora le logiche del CIDR: per tal

motivo è uscita una seconda versione che mette una pezza su buona parte di queste questioni.

L'OSPF, invece, è un protocollo decisamente più evoluto e di tipo link state: è incapsulato a livello di IP, ha

cardine nello scambio di LSA (Link State Advertisement) ed è stato progettato per

• sempli�care il routing in reti grandi tramite la suddivisione in aree: un Autonomous System (AS) può infatti

essere scisso in Routing Areas (RA), all'interno delle quali vi sono gli Internal Router, suddivisibili a loro

volta in Area Backbone Router (router che si interfacciano con il backbone) e Area Border Router (router

che scambiano informazioni con altre aree). All'interno dell'AS esiste poi un AS Boundary Router che

comunica con gli altri AS;

• gestire intrinsecamente reti punto-punto e punto-multipunto, senza rendere enormi le tabelle di routing :

in una rete ad accesso multiplo tutti gli N router connessi alla rete sono di fatto connessi con tutti gli

altri (servono NN − 1

2+ N archi e bisogna trasmettere N(N − 1) LSA). L'OSPF risolve questo problema

adottando una topologia (logica) a stella equivalente, ottenuta tramite l'elezione di un DS (Designated

Router) tale per cui le informazioni di routing vengono scambiate unicamente fra lui e ognuno degli altri

router presenti in rete (crolla il numero di LSA da trasmettere). L'elezione del DS viene e�ettuata scegliendo

quello avente priorità maggiore, mentre il 'secondo classi�cato' diventa il BDS (Backup Designated Router).

Un altro escamotage è quello di creare delle stub areas (SA) all'interno dell'AS: esse sono aree aventi un

unico punto di interconnessione con il resto della rete, cosicché ci si può appoggiare ad esso in qualità

gateway di default e evitare di propagare, all'interno della SA, i percorsi verso network esterne;

• separare logicamente gli host dai router: i singoli host, infatti, vengono logicamente raggruppati all'interno

delle LAN in cui sono contenuti;

• garantire il bilanciamento del carico: se un router ha più percorsi di uguale lunghezza verso una certa

destinazione, il carico viene ripartito equamente su di essi;

• fornire un meccanismo di autenticazione: per garantire maggiore sicurezza nello scambio delle informazioni

di routing è prevista autenticazione con password ed uso di crittogra�a;

• rendere il routing dipendente dal grado di servizio: i router scelgono il percorso sul quale instradare un

pacchetto sulla base dell'indirizzo e del campo Type of Service dell'intestazione IP.

Per la costruzione del Link State Database, ovvero dell'immagine della rete contenuta in ogni router che fa

uso di OSPF, si usano tre sottoprotocolli (i quali di�erenziano la parte non in comune dei messaggi scambiati

tramite OSPF):

• hello: serve per controllare l'operatività dei link, scoprire e mantenere relazioni fra vicini, eleggere DR e

BDR. Sono mandati periodicamente;

• exchange: si sincronizzano i Link State Database tramite una comunicazione fra master e slave (il primo

invia messaggi al secondo, che risponde, ed entrambi confrontano le informazioni ottenute con quelle in

proprio possesso);

• �ooding : serve a di�ondere gli LSA a tutti i router della rete.

Capitolo 8

EGP: Exterior Gateway Protocols

Mentre i protocolli IGP si occupano del routing all’interno degli Autonomous Systems cercando ditrovare il percorso ottimale, i protocolli di tipo EGP (Exterior Gateway Protocol) e BGP (Border GatewayProtocol) si occupano del routing fra i diversi AS tenendo conto anche delle politiche di instradamento1.

8.1 L’EGP per antonomasia: Exterior Gateway Protocol

Si tratta del primo protocollo tra AS (è nato negli anni ’80); è simile ad un protocollo distance vector edè caratterizzato da tre funzionalità principali:

• neighbour acquisition: serve per verificare se esiste un accordo per diventare vicini;

• neighbour reachability: serve a monitorare le connessione coi vicini;

• network reachability: serve a scambiarsi le informazioni sulle reti raggiungibili da ciascun vicino.

Nella sostanza ha molti tratti in comune con i protocolli distance vector, anche se il criterio della distanzaminima non è detto che in questo caso sia quello effettivamente adottato2.

Fu ideato per funzionare su ARPAnet3, quindi è particolarmente adatto ad una topologia ad albero(ma non funziona bene con le reti a maglia complessa, causa la presenza di cicli che rallentano pericolosa-mente la convergenza). Inoltre, non si adatta velocemente ai cambi di topologia, né implementa alcunmeccanismo di sicurezza.

8.2 BPG: Border Gateway Protocol

Nacque per sostituire l’EGP e oggi è alla versione 4; è più sicuro e affidabile di EGP visto che èconnection-oriented (si appoggia al TCP, porta 179): i router si scambiano informazioni attraverso sessioniBGP, che possono essere suddivise in (v. fig. 8.1)

• sessioni BGP esterne (eBGP): fra router di AS diversi;

• sessioni BGP interne (iBGP): fra router dello stesso AS.

Il BGP è un protocollo di tipo path vector: questo significa che, nel vettore dei percorsi, si elencano tuttigli AS da attraversare per raggiungere una particolare destinazione. Ciò risolve il problema dei percorsiciclici (se un AS vede sé stesso nel path vector che riceve allora controlla che nel relativo percorso non visiano loop) e inoltre permette una maggiore flessibilità nella definizione delle politiche di routing fra gli AS.

1Alcuni AS non vogliono essere raggiunti da altri, oppure vogliono mantenere la loro indipendenza, oppure ci sono alcuni accordiinternazionali da rispettare etc. . .

2A dire il vero, non sono nemmeno specificate le regole per definire le distanze. . .3La ’rete dell’agenzia dei progetti di ricerca avanzata’ (Advanced Research Projects Agency Network, ARPANET) venne studiata e

realizzata nel 1969 dal DARPA (Defence Advanced Research Project Agency) del Dipartimento della Difesa degli Stati Uniti. Si trattadella forma per così dire embrionale dalla quale poi nel 1983 nascerà Internet. ARPAnet fu pensata per scopi militari statunitensidurante la Guerra Fredda, ma paradossalmente ne nascerà uno dei più grandi progetti civili: una rete globale che collegherà tutto ilmondo.

83

84 CAPITOLO 8. EGP: EXTERIOR GATEWAY PROTOCOLS

Figura 8.1: BGP: sessioni interne ed esterne

Per attuare queste ultime, infatti, si comunicano ai vicini solo i path vector relativi alle destinazioni verso lequali si vuole permettere il traffico (export policies) oppure si accettano solo le informazioni provenienti daAS ritenuti compatibili (import policies). Inoltre, l’approccio basato sul percorso invece che sulla distanzanon richiede che tutti i router usino la stessa metrica: in quanto non vincolati a rispettare i criteri diminima distanza ci sono infatti permesse scelte arbitrarie. Il rovescio della medaglia sta nel fatto che inquesto modo si consuma molta banda e memoria per le informazioni di routing (bisogna inviare interipercorsi).

Figura 8.2: BGP: scambio di path vector

Esaminiamo l’esempio in figura 8.2 (si noti che BGP rispetta la logica CIDR!): l’AS3 contiene le reti

INDIRIZZO IP Net-ID Host-ID

151.16.0.0/16 -> 10010111.00010000 .00000000.00000000

151.17.0.0/16 -> 10010111.00010001 .00000000.00000000

8.2. BPG: BORDER GATEWAY PROTOCOL 85

151.18.0.0/15 -> 10010111.0001001 0.00000000.00000000

le quali possono quindi essere raggruppate sotto l’unico IP+netmask

INDIRIZZO IP Net-ID Host-ID

151.16.0.0/14 -> 10010111.000100 00.00000000.00000000

che viene inviato all’AS5 con l’indicazione di path ’AS3’ (per forza, c’è solo quello da attraversare!). Questoa sua volta invia tale informazione all’AS1, aggiungendo sé stesso nel percorso; tornati in AS5, vienerilevato il ciclo {AS5 - AS1 - AS5 - AS3} e si rimuove AS1 dall’AS-PATH. La diffusione dei path vectorcontinua verso AS2, dove è presente un’altra rete (80.128.0.0/12) che viene annunciata a AS4, che a suavolta scambia le sue informazioni con AS2. Grazie a questo protocollo è possibile, ad esempio, che AS4decida di non accettare/inviare pacchetti verso qualcuno degli altri AS e quindi, ad esempio, non accettareil path {AS2 - AS5 - AS3}.

8.2.1 Attributi e tipi di messaggio

A ciascun path-vector sono associati degli attributi che ne specificano la natura: un determinato attributopuò essere

• well-known: riconoscibile da tutte le implementazioni BGP, deve essere inoltrato assieme al pathvector (dopo un eventuale aggiornamento);

– mandatory: deve essere presente nel path vector;

– discretionary: può anche non essere indicato;

• optional: può non essere riconosciuto da alcuni router;

– transitive: deve essere inoltrato anche se non riconosciuto;

– non-transitive: deve essere ignorato se non riconosciuto;

• partial: indica se un determinato path vector è stato riconosciuto o meno da tutti i router attraversati.

Gli attributi sono:

• origin: è di tipo well-known e può valere

– 0 se l’informazione è stata ottenuta direttamente dal protocollo di routing operante all’internodell’AS;

– 1 se l’informazione è stata appresa tramite EGP (con informazioni da altri AS);

– 2 altrimenti.

• AS path: è anch’esso di tipo well-known e consiste nell’elenco degli AS da attraversare durante ilpercorso;

• next-hop: di tipo well-known, indica l’indirizzo IP del prossimo router da attraversare verso la desti-nazione specificata.

I tipi di messaggio sono invece:

• Open: è primo messaggio trasmesso quando viene attivata una connessione verso un router BGP vi-cino. Contiene le informazioni di identificazione/autenticazione dell’AS di chi trasmette e la duratadel timeout per considerare un vicino non più attivo;

• Update: contiene il path vector e i relativi attributi;

• Notification: messaggio di notifica di errori e/o di chiusura della connessione;

• Keepalive: non contiene informazioni aggiuntive, ma è usato per comunicare ad un router BGP vicino,in assenza di nuove informazioni di routing, che il trasmettitore è comunque attivo, anche se silente.

86 CAPITOLO 8. EGP: EXTERIOR GATEWAY PROTOCOLS

8.3 In sintesi

Mentre i protocolli IGP cercano il percorso ottimale, i protocolli EGP (che operano fra vari AS) devono tenere

anche conto di accordi internazionali e della speciali politiche di instradamento dovute a necessità d'autonomia

et similia.

EGP è l'Exterior Gateway Protocol propriamente detto e risale alle ricerche su ARPAnet degli anni '80: è simile

a un protocollo distance vector e si occupa di veri�care se esiste un accordo per diventare 'vicino' di qualche nodo

(neighbor acquisition), di monitorare le connessioni con i vicini (neighbor reachability) e di scambiare informazioni

sulle reti raggiungibili da ciascun vicino (network reachability). EGP funziona bene per una topologia ad albero,

ma non per reti a maglia complessa (presenza di cicli), inoltre è poco sicuro e potenzialmente lento a convergere.

Il successore dell'EGP è il BGP, oggi alla versione 4: esso, oltre a rispettare lo schema classless (CIDR), fa

uso di comunicazioni connection-oriented (si appoggia su TCP, più a�dabile) dette sessioni BGP, a loro volta

suddivisibili in internal, fra router dello stesso AS, e external, fra router di diversi AS. Si tratta inoltre di un

protocollo di tipo path vector (nel vettore dei percorsi si elencano tutti gli AS da attraversare per raggiungere

una destinazione) cosa che, oltre a risolvere il problema dei percorsi ciclici e a sopperire alle mancanze dei

protocolli distance vector, rende facile de�nire le import policies (da chi si vuole accettare transito) e le export

policies (verso chi si vuole permettere il transito) dei vari AS. L'approccio basato sul percorso invece che sulla

distanza non richiede infatti che tutti i router usino la stessa metrica e questo rende possibile fare scelte arbitrarie.

Purtroppo, il BGP consuma molta banda per le informazioni di routing e richiede molta memoria nei router per

mantenere le tabelle d'instradamento.

Al �ne di poter introdurre con successo le politiche di instradamento, a ciascun path vector sono associati

degli attributi che ne speci�cano la natura. Essi sono suddivisibili in:

• well-known: riconoscibile da tutte le implementazioni BGP, deve essere inoltrato assieme al path vector

(dopo un eventuale aggiornamento). Fra questi attributi abbiamo ad esempio:

– origin: indica se il path è stato ottenuto staticamente, con IGP o EGP;

– AS path: consiste nell'elenco degli AS da attraversare lungo il percorso verso la destinazione;

– next hop: l'indirizzo dell'AS che deve fare da next hop.

• optional : può non essere riconosciuto da alcuni router;

• partial : indica se un determinato path vector è stato riconosciuto o meno da tutti i router attraversati.

Le tipologie di messaggio sono in�ne:

• Open: contiene le informazioni di identi�cazione/autenticazione dell'AS di chi trasmette e la durata del

timeout per considerare un vicino non più attivo;

• Update: contiene il path vector e i relativi attributi;

• Noti�cation: messaggio di noti�ca di errori e/o di chiusura della connessione;

• Keepalive: è usato per comunicare ad un router BGP vicino che il trasmettitore è comunque attivo, anche

se silente.

Capitolo 9

MPLS: sostituzione d’etichetta

9.1 Introduzione: il label switching

Il label switching è una modalità di trasferimento dei pacchetti IP basata su hardware veloce. La suaideazione nasce dalla volontà di rendere possibile l’instradamento da parte di apparati non in gradodi trattare datagrammi IP come fanno i router, che possono essere decisamente costosi al contrario deimolto più economici switch: mentre infatti i primi, oltre a instradare i datagrammi IP, supportano ungran numero di interfacce e protocolli ed effettuano anche operazioni addizionali come il packet filtering, ilcontrollo della QoS1, etc. . . gli switch fanno instradamento semplice in funzione di indirizzi statici e hannoun supporto per un numero limitato di interfacce e di protocolli. Ciò li rende molto più a buon mercatoe questo ha fomentato l’ipotesi che si potesse migliorarli un poco per renderli dei ’quasi-router’ (con unottimo compromesso funzionalità/costo): da qui l’idea di trovare un metodo alternativo al destination basedrouting per effettuare l’instradamento.

Il label switching, tra l’altro, rende possibile il trasferimento di pacchetti IP su percorsi prestabilitidiversi da quelli selezionati dai normali protocolli per il routing IP, supporta bene le VPN (Virtual PrivateNetwork) e permette il mantenimento dei protocolli di routing IP standard (OSPF, BGP). Infine, uno deigrandi vantaggi dell’approccio MPLS consiste nell’aggregazione di più flussi di fati in un unico qualoraentrambi condividessero la stessa destinazione. Ciò alleggerisce e semplifica di molto l’instradamento.

Come si può ottenere tutto questo ben di Dio? Scomponendo la funzione di instradamento in duecomponenti:

• trasferimento (ereditata dagli switch) - si basa su hardware veloce e identificazione tramite etichet-tamento dei flussi informativi. Si adotta un modo di trasferimento con commutazione orientata allaconnessione: la commutazione si basa infatti sul riconoscimento di un’etichetta (label) associata aldatagramma. Tale etichetta è un’entità breve e di lunghezza predefinita che non codifica gli ind-irizzi di rete (scordiamoci quindi il meccanismo degli indirizzi con netmask!), bensì viene inseritatra l’intestazione dello strato di linea e quella dello strato di rete. La label viene utilizzata sia per iltrasferimento (individua il destinatario) sia per la gestione delle risorse;

• controllo (ereditata dai router) - si basa sui protocolli di rete convenzionali sui e meccanismi di asso-ciazione delle etichette. Per capire come funziona il controllo si introduce il concetto di flusso (flow)che è una sequenza di datagrammi inviati da una particolare sorgente a una particolare destinazionee accomunati da medesimo instradamento, uniformi richieste di qualità di servizio e stesse politichedi routing. Può essere utile immaginare il flusso come un grande tubo, un’autostrada per i pacchettiche devono andare tutti quanti verso la stessa direzione; tali pacchetti vengono infatti associati2 aquesto tubo (cioè ad una FEC, Forwarding Equivalence Class) in base a destinazione e classe di traf-fico: da quel momento avranno tutti lo stesso next-hop (nodo a valle del nodo corrente) e non avràimportanza distinguerli se non quando saranno in prossimità della loro destinazione.

1Quality of Service.2Il processo di associazione si chiama binding.

87

88 CAPITOLO 9. MPLS: SOSTITUZIONE D’ETICHETTA

9.2 Nomenclatura

Di seguito chiameremo:

• Label-Switching Router (LSR): un router che supporta MPLS (MultiProtocol Label Switching);

• Label Edge Router (LER): il router di interlavoro tra la rete esterna (quella che funziona ’normalmente’con l’IP) e il dominio MPLS (v. fig. 9.1). Il compito di componenti del genere è quello di attribuireai pacchetti entranti la giusta label e di togliere quest’ultima a quelli uscenti: per poter effettuaretale operazione, è necessario che i LER sino in grado di determinare la corretta FEC e l’opportunonext hop per ogni possibile messaggio entrante. Inoltre, onde evitare di calcolare la FEC ad ogninodo attraversato, è opportuno che tutti i LSR del dominio MPLS instradino i pacchetti identificatidalla stessa label verso la medesima direzione: in questo modo l’etichetta diventa univoca e non ènecessario calcolarla di continuo;

Figura 9.1: Schema concettuale di una rete funzionante tramite MPLS: LER e LSR

• dominio MPLS: un gruppo di LSR interconnessi;

• Label-Swicthed Path (LSP): il percorso attraversato da pacchetti con stessa label: inizia con un LSR cheinserisce (push) la prima label a livello gerarchico m. Il livello gerarchico viene inserito in quantoi vari domini MPLS possono essere fra loro intersecati nonché disposti in maniera gerarchica: perogni livello di gerarchia, quindi, è necessario inserire una label in grado di identificare il next-hopdi quel particolare livello. Tutti i LSR intermedi commutano i pacchetti sulla base della label dilivello3 m (con label swapping) e il Label-Swicthed Path termina con un LSR che prende una decisioned’instradamento sulla base di una label di livello gerarchico < m (oppure in modo convenzionale, inbase alla particolare politica di routing scelta).

Instradamento ’classico’ MPLS

Algoritmo di forwardinglongest prefix match: si utilizzail binomio IPadress + netmask

per individuare il path da seguire

exact match: una label indicachiaramente un unico percor-so, da prendere senza effettuarecalcoli

Algoritmo di routing

nessuna differenza fra i due casi(instradamento classico e MPLS):i router LER devono tuttaviaconoscere il protocollo IP perpotersi interfacciare con l’esterno

nessuna differenza fra i duecasi: un dispositivo che usaMPLS (come un LSR) non devepadroneggiare il protocollo IP, madeve saper instradare e fare labelswapping

3I livelli gerarchici più ’alti’ (maggiore generalità e incapsulamento) sono quelli aventi m inferiore.

9.3. USO E TRATTAMENTO DELLE LABEL 89

9.3 Uso e trattamento delle label

In figura 9.2 è possibile vedere la struttura e il posizionamento dell’etichetta dell’MPLS. Tra i vari campi

Figura 9.2: Struttura e posizionamento dell’etichetta dell’MPLS.

compare il Time To Live (TTL): esso farebbe già parte dell’intestazione IP perciò, quando un datagrammaemerge da una rete di trasporto MPLS il campo TTL dovrebbe avere un valore che tiene conto del numerodi LSR attraversati. In questo modo, ritornati nel mondo IP, il pacchetto avrà il tempo di vita che glispetta: se non esistesse un meccanismo per questa ’traduzione’ del TTL, un pacchetto congelerebbe la suaetà dal momento esatto in cui entrasse in un’area MPLS. Per questo motivo TTL viene inserito nella labelMPLS e inizialmente ha lo stesso valore del TTL di IP all’ingresso del primo LSR. Tale parametro vienedecrementato ad ogni attraverso di un LSR e viene copiato nell’intestazione IP al momento di ritornare adun normale router.

In figura 9.3 vediamo invece il meccanismo del label stacking, che permette all’MPLS di poter gestireun’architettura a reti gerarchiche.

Figura 9.3: Il meccanismo del label stacking

Affinché tale meccanismo funzioni è necessario che la gestione delle label sia ben progettata. Bisognaquindi che sia possibile:

• associare una label ad ogni LSP4 (operazione di label binding) in modo che, se immaginiamo l’LSPcome un’autostrada per i pacchetti, questi ultimi vengano opportunamente etichettati con la giusta

4E quindi ad ogni FEC.


label se devono prendere tale via. Questo implica inoltre che pacchetti appartenenti alla stessa FECabbiano la stessa label (appartenente a quel FEC). L’associazione di questo tipo (fra label e FEC/LSP)viene sempre fatta dall’LSR a valle del collegamento;

• concordare le label con il LSR a monte, che deve etichettare i pacchetti appartenenti all’LSP in modoche il LSR a valle li riconosca correttamente, e viceversa (bisogna concordare una label con il LSRa valle, in modo che riconosca i pacchetti come appartenenti all’LSP). Ciò è necessario affinché siapossibile fissare un indirizzamento; si vuole però sottolineare che non è necessario che la label diingresso e quella di uscita per un LSP siano uguali: l’importante è che gli LSR siano adeguatamenteinformati di quali siano le etichette da applicare e quali siano i LSP da far prendere ai pacchetti5 (v.label swapping);

• calcolare il prossimo LSR di un LSP, cosa che si può fare con gli algoritmi e protocolli di routingtradizionali, riconducendosi questo problema alla ricerca del next-hop.

Il label swapping (v. fig. 9.4) è invece, come abbiamo detto, quell’operazione per cui un LER, grazieall’uso di una tabella di instradamento detta Label Forwarding Information Base (LFIB), riesce a sostituirel’etichetta qualora le label di ingresso e quelle di uscita per un LSP non fossero uguali. Il label swappingnon altera il percorso di un insieme di pacchetti aventi la stessa FEC e non è un’operazione di routing;la strada che tali pacchetti devono prendere è infatti già stata decisa dal momento in cui il primo routerdell’LSP ha applicato la sua etichetta: lo swapping, viceversa, è una ’passiva’ sostituzione di etichetta utilea sistemare le cose quando le label dell’interfaccia d’ingresso e quelle d’uscita di un nodo, lungo lo stessoLSP, cambiano nome (cosa che può accadere senza problemi, basta che i router si mettano d’accordo!).

Quando un LER riceve un datagramma estrae la sua label di ingresso, cerca nella LFIB la entry relativaa quella label, sostituisce la label di ingresso con la label di uscita e infine invia il pacchetto sulla interfacciaspecificata verso il next hop. Il tutto, affinché sia fatto correttamente, comporta che il LER sappia effettuareil corretto forwarding del pacchetto verso la sua giusta destinazione.

Figura 9.4: Il label swapping

9.4 Allocazione delle label

Come abbiamo già sottolineato, le label sono una risorsa gestita dai LSR a valle di un link. Esse possonoessere allocate con due diverse modalità:

• downstream on demand allocation: l’allocazione viene richiesta dal LSR a monte e viene resa notasolamente al LSR richiedente;

• unsolicited downstream allocation: l’allocazione avviene senza esplicita richiesta e viene notificata atutti i LSR a monte di quello che esegue l’allocazione. A seguito di unsolicited allocation da partedi un certo LSR (che chiamiamo X) si possono tuttavia ricevere allocazioni su di un percorso nonutilizzato dal LSR a monte. In tal caso ci sono due modi per reagire:

– liberal retention mode: si tiene memoria dell’associazione e questa può essere immediatamenteutilizzata se ad un certo punto si vuole instradare traffico attraverso l’LSR X. Ciò permette unamaggiore velocità di esecuzione ma richiede memoria;

– conservative retention mode: si cancella l’associazione e, in caso di bisogno, si deve eseguireun’allocazione on demand. Si ha quindi maggiore economia nella gestione delle label ma si saràpiù lenti a reagire semmai fosse necessario instradare qualcosa attraverso X.

5Necessario è, invece, che la label d’uscita dell’LSR a monte sia uguale alla corrispondente d’ingresso dell’LSR a valle, ma questoè abbastanza ovvio!

9.5. ALTRI ASPETTI 91

9.5 Altri aspetti

9.5.1 Controllo dei Label-Switched Paths

Esistono due modi per gestire il controllo dei Label-Switched Paths:

• independent LSP control: ogni LSR prende le decisioni di binding6 in modo indipendente e le dis-tribuisce ai LSR a monte7. Siccome i risultati di questo modo d’operare non sono coordinati ecomportano l’esistenza di un certo ’transitorio’ prima che venga delineato completamente il LSP,può accadere che pacchetti di una stessa FEC seguano strade diverse prima di arrivare ’a regime’nel calcolo del path;

• ordered LSP control: un LSR crea un bind per una certa FEC solamente se è l’ultimo nodo di un LSP(questo comporta che sarà lui a prendere la prima decisione sul binding, ovvero quella che verràpropagata, man mano, agli LSR a monte) oppure se ha già ricevuto il bind per quella FEC dal LSRche lo segue lungo il LSP (cioè se riceve informazioni già validate dal LRS a valle). Seguendo questometodo il binding avviene in maniera ordinata e la label all’ingresso è disponibile solamente quandotutto il LSP è stato creato. Rispetto all’indipendent LSP control, tutti i pacchetti di una FEC seguonolo stesso percorso e incontrano le medesime caratteristiche di rete.

9.5.2 Label Distribution Protocol

Per un corretto funzionamento dell’MPLS è d’obbligo uno scambio di informazioni fra gli LSR al finedi accordarsi sulla label da utilizzare per una certa FEC (cioè, in ultima analisi, verso lo stesso next-hop).Per svolgere questo compito, è possibile modificare protocolli esistenti (RSVP, BGP, RSVP-TUNNEL. . . )oppure definire nuovi protocolli ad hoc (Label Distribution Protocol LDP, CR-LDP. . . ).

Figura 9.5: Label Distribution Protocol

Il Label Distribution Protocol gestisce l’apertura, la gestione e la chiusura di una sessione fra LSR e fa usodi messaggi predefiniti per la gestione e l’assegnazione delle label (v. fig. 9.5). Ha inoltre un meccanismodi riparazione degli errori.

6Il binding, lo ricordiamo, è il processo di associazione fra i FEC e le label.7Le decisioni vengono sempre prese dall’LSR a valle.


9.5.3 Fish picture

Il problema della fish picture si ha quando la decisione di instradamento è presa solo sulla base del-l’indirizzo IP, senza alcun tipo di calcolo statistico atto a bilanciare il carico di due collegamenti posti comein figura 9.6. In tal caso, infatti, tutti i pacchetti verso una certa destinazione seguono lo stesso percorso(quello riconosciuto di lunghezza minima dall’algoritmo di routing).

Figura 9.6: Questione della fish picture

Facendo routing esplicito, invece, è possibile ripartire i flussi di traffico su diversi percorsi: in questomodo si creano diversi LSP per una stessa destinazione e, a seconda della label inserita dal nodo sorgente,il pacchetto percorrerà uno dei (più) path disponibili. Così facendo si ripartisce più armoniosamente iltraffico su diversi percorsi e si tracciano vie alternative già pronte da utilizzare in caso di guasto (v. fig.9.7).

Figura 9.7: Questione della fish picture [2]

9.6 In sintesi

MPLS sta per Multiprotocol Label Switching e consiste in una modalità di trasferimento IP compatibile con

dispositivi intermedi fra i router (complessi, con tante interfacce, costosi) e gli switch (semplici, economici).

Mentre infatti la funzione di controllo (routing) viene e�ettuata in base ai protocolli tradizionali, quella di trasfer-

imento (forwarding) è dall'MPSL ottemperata tramite il sistema delle etichette e la de�nizione del concetto di

�usso (non lavoriamo più con la logica del longest pre�x match, bensì con quella dell'exact match).

Grazie all'MPLS è possibile e�ettuare una commutazione orientata alla connessione, consistente nel riconosci-

mento di una label, breve e di lunghezza �ssa, inserita8 tra il livello 2 e il livello 3. Inoltre, l'MPLS ha un'unica

modalità di trasferimento per servizi diversi (unicast, multicast. . . ), supporta le VPN e rappresenta una soluzione

trasversale e multiprotocollo.

• Un �usso è una sequenza di datagrammi da una comune sorgente a una comune destinazione: nell'MPLS

tali datagrammi condividono il medesimo instradamento, la stessa QoS e le stesse politiche di gestione.

• Una FEC (forwarding equivalence class) consta di �ussi di pacchetti aventi medesima destinazione (la

distinzione fra �usso e FEC è molto labile): di conseguenza elementi della stessa FEC hanno lo stesso

next-hop.

8Alcuni considerano l’MPSL un protocollo di livello 2,5!

9.6. IN SINTESI 93

• Un LSR è un router che supporta MPLS: esso e�ettua il label switching sulla base di una tabella di

instradamento (LFIB: Label Forwarding Information Base) che contiene, per ogni entry, le label attive,

l'interfaccia d'uscita e la label d'uscita.

• Un LER è un router che e�ettua l'interfacciamento fra mondo IP e mondo MPLS. Attribuisce le label e

calcola il next-hop senza ricalcolare la route (se ve ne fosse stato bisogno, la fatica per fare l'MPLS sarebbe

stata inutile). Stessa label = stessa destinazione = stessa FEC.

• Un dominio MPLS consta in vari LSR interconnessi.

• Un LSP è un percorso, cioè una sequenza di router, che inizia con l'LSR che mette l'etichetta di livello

gerarchico m e �nisce con l'LSR che instrada sulla base del livello < m (cioè immediatamente superiore9).

Le label trattate dall'MPLS sono a 32 bit: 20 per la label vera e propria, 3 per la QoS, 1 per il label stacking10

(innesto di domini MPLS ordinati gerarchicamente: il router d'ingresso di un certo dominio MPLS inserisce una

label relativa a tale dominio ed essa viene rimossa dal momento che fuoriesce da quest'ultimo), 8 per il Time-to-live

(tradotto, se necessario, da e verso il mondo IP).

La gestione delle label da parte di ogni LSR prevede che:

1. si riconoscano i pacchetti aventi la stessa FEC (si associa loro la label relativa all'LSP);

2. si concordino le label con l'LSR a monte/a valle (si tenga presente che le label d'uscita ed ingresso non

devono essere necessariamente uguali, basta mettersi d'accordo sul fatto che portino alla stessa destinazione!

Se le label cambiano, l'LSR deve e�ettuare un'operazione di label swapping);

3. si calcoli il next-hop.

L'associazione delle label fra FEC e LSP avviene sempre da parte dell'LSR a valle; inoltre, essa dev'essere

fatta con la sicurezza che si garantisca unicità fra label e coppia {sorgente, destinazione}. Tale allocazione può

avvenire:

• downstream-on-demand : l'allocazione viene richiesta dall'LSR a monte verso l'LSR a valle;

• unsolicited downstream: l'allocazione avviene senza esplicita richiesta.

Se l'LSR cui viene comunicata l'allocazione scopre un percorso non utilizzato, allora

• può conservarlo in memoria (liberal retention mode), così da averlo già pronto in futuro;

• può ignorarlo (conservative retention mode), così da non occupare memoria e chiederlo all'occorrenza.

Per quanto riguarda l'ordine con cui avvengono questi processi, possiamo avere una modalità

• indipendent: ogni LSR decide indipendentemente e passa le informazioni a monte. Ciò comporta la presenza

di un certo transitorio durante il quale pacchetti aventi la stessa FEC possono e�ettuare strade diverse;

• ordered : un LSR fa il binding se è l'ultimo nodo di un LSP o se ha ricevuto indicazioni dall'LSR a valle;

questa metodologia non presenta transitori di nessun tipo e converge velocemente.

Il protocollo di scambio di tali informazioni è l'LDP e si basa su sottoprotocolli di hello (UDP) e open (TCP, con

request e response).

9Non è un errore di battitura: m piccolo = maggiore generalità, v. slide 25!10Il bit è ad 1 se è l’ultima etichetta o è 0 se vi sono delle etichette ’stack-ate’.

Appendice A

Esercizi

A.1 Protocolli di rete, analisi di CW

A.1.1 Esercizio 1

DATI PRELIMINARI

Protocollo: TCP Reno

Segmenti (dimensione MSS) spediti: 26Segmenti perduti: 14 e 17

RTO = 3RTT

[1] Il protocollo inizia con la finestra W = CW = 2: siamo in SS visto che la SSTHR è pari a 8 e2 < 8. Tutto va chiaramente a buon fine e riusciamo a spedire i segmenti 1 e 2; nella fase [2] la finestraè raddoppiata, quindi spediamo i segmenti 3 . . . 6. Passiamo quindi alla fase [3], dove la finestra è ulteri-ormente raddoppiata (siamo a CW = W = 8 e quindi inizia la fase di congestion avoidance). Teoricamentedovremmo spedire i segmenti 7 . . . 14, solo che il 14◦ si perde. In effetti, il ciclo dopo, la finestra non passaa 9 (cioè non aumenta di 1, com’è normale che accada nel CA) perché non abbiamo ricevuto 8 ACK (quellida 8 . . . 15), ma solo quelli di numero 8 . . . 14, che sono 7 e che quindi non completano la finestra. Tali 7ACK, tuttavia, hanno l’effetto di far scorrere la finestra di altrettante posizioni e di permettere l’invio [4]dei segmenti 15 . . . 21. Il trasmettitore si aspetterebbe, a questo punto, di ricevere l’ACK mancante del giroprima (il 15) nonché quelli da 16 a 22: il ricevitore, invece, non può fare altro che chiedergli insistente-mente il segmento 14, che non è riuscito ad arrivare, ed infatti vengono spediti 6 ACK (da 8 che dovevanoessere passiamo a 7 perché il segmento 14 non è arrivato e quindi a 6 perché persino il 17◦ segmento siè perso chissà dove), tutti con numero di sequenza 14 [4b]. Gli ACK duplicati sono 6 e quindi parte ilFast retransmit/Fast recovery (in effetti ne sarebbero bastati 3 duplicati, ovvero 4 in totale, per far scattarel’algoritmo): quel che accade è che la finestra si gonfia e passa a

fightsize2

+ Numero di ACK duplicati =82

+ 6 = 10

Si ricorda che il flightsize indica quanti pacchetti il ricevitore presume siano in giro per la rete (tra quelli

confermati e non arriviamo a 8). La W = CW viene perciò messa a 10 e la SSTHR afightsize

2, cioè a 4. Il

trasmettitore può [5] ora trasmettere il segmento 14, che tanto insistentemente gli è stato chiesto, nonchéi segmenti 22 e 23, che stanno all’interno della finestra da 10 (14 . . . 23). Il ricevitore, di risposta, è tuttaviadecisamente indispettito e chiede tre volte il segmento 17 [5b], non essendogli esso ancora arrivato. Siamoora in [6]: siamo in CA perché la soglia era 4 e la finestra si è sgonfiata fino a passare a 4. Per un pelonon scatta di nuovo il FR/FR, dato che sono arrivati 2 ACK duplicati; in compenso scade l’RTO del 17◦

segmento e quindi [7] la nuova SSTRH diventa pari afightsize

2, cioè a 3 (per il trasmettitore i segmenti

in giro sono 7, cioè quelli dal 17 al 23, per cui si ha 7/2 arrotondato per difetto), mentre sia W che CWdecadono a 1. L’unica buona notizia è che, finalmente, viene trasmetto ’sto maledettissimo segmento 17:il ricevitore apprezza lo sforzo e invia ACK 24 (visto che ha questo punto ha in cassa tutti i segmenti finoal 23◦); di lì in poi [8][9], la connessione riprende a crescere in SS secondo le regole del TCP classico e, al26◦ segmento, la trasmissione è completa.

95

96 APPENDICE A. ESERCIZI

Figura A.1: Rappresentazione schematica dell’esercizio A.1.1

A.1. PROTOCOLLI DI RETE, ANALISI DI CW 97

A.1.2 Esercizio 2

DATI PRELIMINARI

Protocollo: TCP New Reno

Segmenti (dimensione MSS) spediti: 30Segmenti perduti: 14 e 17

RTO = 3RTT

Questo esercizio ha praticamente gli stessi dati di quello precedente e serve semplicemente a metterein mostra quanto, in certe situazioni, il New Reno sia più figo rispetto al Reno nudo e crudo. Fino a [3]tutto va come nell’esercizio A.1.1: in [1] si ha la perdita del segmento 14 e in [2] quella del segmento17 e la sestuplicale1 richiesta del segmento 14. La prima vera differenza si nota a [3]: anzitutto vienememorizzato il numero di sequenza dell’ultimo pacchetto inviato (il 21) nella variabile recover. Il calcolodella nuova CW [3] è identico a quello dell’esercizio A.1.1; questa volta però non usciamo subito dal fast-retransmit/fast-recovery perché in [3] riceviamo gli ACK di 17, che è < di 18. In [4] la finestra è ancora paria 10 in quanto essa deve crescere di 1 per ogni ulteriore ACK duplicato e decrementarsi di 1 per ognisegmento confermato (per un totale di −3 in quanto siamo passati ad ACK 17 da ACK 14 e 17− 14 = 3).Tra [3] e [4] scade l’RTO di 17, che quindi viene inviato in [4] assieme a 24, 25 e 26 (che riescono a starenella finestra grande 10). Alla fine di [4] riceviamo gli ACK di 24, 25, 26 e 27: tutti questi numeri sonomaggiori della variabile recover (= 17) e quindi possiamo uscire dal FR/FR. In [5] la finestra CW vienemessa pari alla soglia, cioè a 4. Come si può notare, una volta che siamo usciti dalla SS non ci torniamopiù.

1Non ci crederete, ma si scrive proprio così!


A.1.3 Esercizio 3

DATI PRELIMINARI

Protocollo: TCP 'standard' (senza fronzoli)

Segmenti (dimensione MSS) spediti: 64Segmenti perduti: 53

RTO = 2RTT

Esercizio abbastanza banale, se raffrontato con quelli numero A.1.1 e A.1.2. Fino a [7], di fatto, nonaccade nulla di particolare: finché la CW è sotto a 8 (la SSTHR) siamo in SS ([1]-[3]) e quindi, ad ogni RTT,raddoppiamo la finestra (2 in [1], 4 in [2] e 8 in [3]). Tutti i segmenti vengono ricevuti correttamente equindi il numero degli ACK ad ogni RTT è pari al numero dei segmenti inviati + 1. Da [4] in poi siamo inCA e la finestra cresce di 1 ad ogni RTT, invece di raddoppiare: anche qui tutto va normalmente e senzaintoppi. La vera ’novità’, se così si può chiamare, l’abbiamo a [7]: la finestra è 10 (non può essere di piùin tutto l’esercizio perché AW è costante e pari a 10: essa fissa perciò un limite superiore) ma di questi10 segmenti solo 9 vengono correttamente recepiti. Il 53◦, infatti, si perde in rete e non viene ricevuto,cosicché vengono inviati solo 9 ACK (e non 10). Il RTT successivo ([8]) la CW non aumenta, perché nonè arrivato il pacchetto in grado di incrementarla di 1 (sempre il 53◦, mannaggia a lui!), ma questo nonimpedisce alla finestra di scorrere di 9 posizioni cosicché inviamo i messaggi da 54 a 62. Continuiamotuttavia a ricevere 9 ACK a 53 in quanto il ricevitore brama il suo pacchetto con insistenza: non dovrà peròaspettare molto perché alla fine di [7] scade il relativo RTO, evento che provoca la caduta della finestraW a 1, il ridimensionamento di SSTHR a CW/2 = 12/2 = 6 e la ritrasmissione del 53◦ pacchetto chequesta volta viene correttamente ricevuto. Ad [8] la finestra passa a 2 (siamo tornati in SS) e termina latrasmissione con l’invio di 63 e 64.


A.1.4 Esercizio 4

DATI PRELIMINARI

Protocollo: TCP 'standard' (senza fronzoli)

Segmenti (dimensione MSS) spediti: 64Segmenti perduti: 53

RTO = 3RTT

Questo esercizio è una versione minimamente modificata di quello precedente: l’unica cosa che cambiaè l’RTO, che è più lungo (3RTT invece che 2RTT). Il segmento mancante viene quindi trasmesso due RTTdopo [8]: in seguito, la trasmissione può continuare con 63 e 64 (non vengono riportati nello schema, tantoil meccanismo è analogo all’esercizio precedente).

A.2. MODELLI PER IL TCP 103

A.2 Modelli per il TCP

A.2.1 Esercizio 1

Una connessione TCP-Reno che lavora nelle seguenti condizioni:

• tempo di andata e ritorno approssimativamente costante e pari a RTT = 80 ms;

• �nestra di trasmissione (W) limitata dal valore della �nestra di congestione (CW) (AW abbastanza grande

per essere inin�uente);

• perdite di segmenti dovute a fenomeni di congestione in rete approssimativamente periodiche e pari a

p = 2% dei segmenti;

• si considerino tutti i segmenti di dimensione pari a MSS = 1000.

Trascurando i periodi di tempo relativi alle fasi di fast retransmit a valle delle perdite dei segmenti si considerino

i soli periodi in cui il controllo di congestione utilizza l'algoritmo di Congestion Avoidance. Inoltre si ipotizzi una

crescita della �nestra di congestione puramente lineare in tali fasi. Si valuti:

1. la dimensione massima di W (in segmenti) e di w (in byte)

2. il throughput S della connessione in numero di segmenti per RTT e numero di bit per secondo;

3. qualora la banda del collegamento a minore capacità del percorso end-to-end della connessione sia C=2,048Mbit/s discutere l'e�etto delle perdite sull'e�cienza nell'uso della capacità disponibile.

SOLUZIONE:

1. siamo nel caso più semplice, cioè quello di perdite periodiche (v. par 3.3) quindi la dimensionemassima della finestra è

W =

√8

3p= 11, 547→ 11 segmenti ⇔ 11, 547 ·MSS = 11547 byte

2. anche questo punto è risolvibile semplicemente applicando una pedissequamente formula

S =1

RTT

√3

2p= 108, 25→ 108 segmenti/s ⇔ 108, 25 ·MSS · 8 = 866025 bit/s

Si noti che questa volta vengono richiesti i bit, non i byte (tipico errore di distrazione)!

3. la banda della connessione è ben più consistente degli 866 Kb/sec circa che effettivamente sfruttiamo.

L’efficienza nell’uso della banda è infatti del866

2048= 42, 3%.

A.2.2 Esercizio 2

Due connessioni TCP-Reno lavorano rispettivamente nelle seguenti condizioni:

• RTT approssimativamente costante e pari a RTT = 60 ms;

• perdite di segmenti dovute a fenomeni di congestione in rete approssimativamente periodiche e di probabilità

p = 1%;

• tutti i segmenti di dimensione sono di dimensione pari a MSS = 500 byte.

Si ipotizzi che:

• la connessione 1 utilizzi un'implementazione TCP che non fa uso di ACK ritardati, mentre la connessione 2

invii un ACK ogni 2 segmenti ricevuti;


• siano trascurabili i periodi di tempo relativi alle fasi di fast retransmit e fast recovery a valle delle perdite

dei segmenti e quindi si possano considerare i soli periodi in cui il controllo di congestione utilizzi l'algoritmo

di Congestion Avoidance;

• la crescita della �nestra di congestione sia puramente lineare in tali fasi;

• AW sia di grandi dimensioni per entrambe le connessioni e pertanto W = CW.

Determinare:

1. l'andamento di W1 e W2 nel tempo ed i relativi valori massimi e minimi, in numero di segmenti ed in byte;

2. il throughput S1 ed S2 della connessione in numero di segmenti per RTT e numero di bit per secondo.

SOLUZIONE:

1. in questo caso dobbiamo sia fare riferimento al modello di perdite periodiche (v. par. 3.3) che aquello degli ACK ritardati (v. par. 3.3.1) quindi la dimensione massima della finestra è, nel primocaso

W1max =

√8

3p= 16, 33→ 16 segmenti ⇔ 16, 33 ·MSS = 8165 byte

mentre per la connessione 2 si ha:

W2max =

√8

3pb= 11, 547→ 11 segmenti ⇔ 11, 547 ·MSS = 5774 byte

Com’è evidente, la dimensione massima della finestra è superiore nel caso di ACK non ritardati.La dimensione minima, fatta l’ipotesi di rimanere sempre in CA, è pari alla metà di questi dueparametri2. Connessione 1:

W1min =16, 33

2= 8, 17→ 8 segmenti ⇔ 8, 17 ·MSS = 4085 byte

Connessione 2:

W2min =11, 547

2= 5, 77→ 5 segmenti ⇔ 5, 77 ·MSS = 2885 byte

L’andamento nel tempo di entrambe le connessioni sarà caratterizzato dal tipico grafico a dente disega: la lunghezza dei periodi sarà maggiore nel caso di ACK ritardati (la connessione va a tutti glieffetti più lenta e, inoltre, non riesce a raggiungere i valori della finestra del caso not delayed). Lalunghezza di tali periodi è calcolabile tramite la formula:

T1 =W1max · RTT

2=

16, 33 · 0, 062

= 0, 4899 s

T2 =W2maxb · RTT

2=

2 · 11, 547 · 0, 062

= 0, 6928 s

Si noti che T1 ·√

2 = T2: tra i due parametri T vi è infatti un fattore√

b.

2. anche nel risolvere questo punto dobbiamo tenere presente che una delle due connessioni utilizzaACK ritardati:

S1 =1

RTT

√3

2p= 204, 12→ 204 segmenti/s ⇔ 204, 12 ·MSS · 8 = 816497 bit/s

S2 =1

RTT

√3

2bp= 144, 34→ 144 segmenti/s ⇔ 144, 34 ·MSS · 8 = 577350 bit/s

Ancora una volta si ha una relazione del tipo S1 ·√

2 = S2: anche tra i due parametri S vi è infattiun fattore

√b.

2Infatti, quando scade un RTO e fatta l’ipotesi di trascurare la SS, dimezziamo la finestra.

A.2. MODELLI PER IL TCP 105

Figura A.5: Interpretazione grafica dell’esercizio A.2.2

A.2.3 Esercizio 3

Supponiamo di avere una connessione TCP New Reno e si tengano buone le seguenti ipotesi:

• round trip time RTT = 120 ms;

• maximum segment size MSS = 1000 byte;

• advertise window AW = 20 segmenti;

• probabilità di perdita p = 0, 25%;

• un ACK ogni segmento;

• perenne congestion avoidance.

Si determini, supponendo di caratterizzare il problema con il modello periodico:

1. La dimensione massima teorica della �nestra (senza considerare le limitazioni di AW).

2. Quanto tempo intercorre fra due perdite (senza considerare le limitazioni di AW).

3. Il throughput (senza considerare le limitazioni di AW).

4. Il throughput nell'ipotesi che AW limiti la �nestra.

SOLUZIONE:

1. La massima dimensione teorica della finestra è pari a

W =

√8

3p= 32, 660 segmenti/s ⇒ 32, 66 · 1000 = 32.660 byte/s

La dimensione della finestra, scritta come numero intero (com’è normale che sia), è pari a 32 (nonriceviamo mai l’ACK che la fa diventare 33). La dimensione minima che la finestra potrà assumereè invece pari a 32/2 = 16.


2. Il periodo fra due perdite è pari al tempo che intercorre fra quando la finestra è 16 e quello in cui èpari a 32; si ha quindi:

322· RTT = 1920 ms

3. Applicando le formulette:

S =

√3

2p1

RTT= 204, 12 segmenti/s ⇒ 1, 633 Mbit/s

4. Possiamo o utilizzare la formula approssimata che consiste nel confondere il trapezio col rettangolo(v. figura A.6)

AWRTT

= 20 segmenti/s ⇒ 20 · 1000 · 80.120

= 1, 333 Mbit/s

Il valore 1, 333 Mbit/s è abbastanza inferiore agli 1, 633 Mbit/s del caso senza AW: è un buon segnoperché significa che presumibilmente non abbiamo fatto una sovrastima eccessiva ma accettabile.

Figura A.6: Interpretazione grafica dell’approssimazione effettuata per il calcolo di AW.

oppure fare i certosini ed effettuare un calcolo preciso: in una prima fase, di durata pari a 4RTT, lafinestra cresce di 1 per ogni round trip time fino al raggiungere il valore 20 (v. figura A.7). In questafase trasmettiamo:

16 + 17 + 18 + 19 = 70 segmenti

La domanda è: quanti RTT con finestra pari a 20 mancano per trasmettere il numero di segmenti chevengono inviati tra una perdita e l’altra (= 1/p = 400 in questo caso)? Per saperlo, basta risolverel’equazione:

400 = 70 + 20x

Il numero di RTT mancanti risulta facilmente essere pari a 16, 5: approssimeremo per eccesso inquanto la 17ma finestra è necessaria per poter trasmettere quello 0,5 che c’è oltre a 16 (detto proprioin soldoni, eh!?). Servono quindi 21 RTT invece che 16 per arrivare alla perdita: il troughput esatto èquindi un po’ inferiore rispetto a quello calcolato in precedenza:

S =400

21 · RTT= 1, 26 Mbit/s

A.3 Latenza

A.3.1 Esercizio 1

Supponiamo di avere una connessione TCP New Reno e si tengano buone le seguenti ipotesi:

• round trip time RTT = 100 ms;

A.3. LATENZA 107

Figura A.7: Interpretazione grafica dell’approssimazione effettuata per il calcolo di AW (2).

• maximum segment size MSS = 500 byte;

• un ACK ogni segmento;

• perdite assenti;

• 1 MByte da trasmettere;

• velocità di trasmissione C = 256 kilobit/s;

• slow start threshold SSTHR = 32 segmenti.

Si determini:

1. Il prodotto banda-ritardo.

2. Il valore minimo della �nestra in grado si sfruttare al meglio il canale.

3. Il tempo necessario a�nché la �nestra di trasmissione raggiunga il valore ottimo.

4. Quanto tempo impiega il completo trasferimento dei dati.

SOLUZIONE:

1. Domandona! Chi si spaventa a questa è perduto:

C · RTT = 25600 bit

2. Dobbiamo soddisfare la relazione:W > B · RTT

Se essa è verificata allora saremo nel caso ottimo per la latenza. La W incriminata sarà quindi, insegmenti:

WO =25600500 · 8 = 6, 4→ 7

Dobbiamo sovrastimare per eccesso, perché la settima finestra è imprescindibile.

3. servono due RTT: infatti, se iniziamo da finestra pari a 2

W(1) = 2

. . . passa un RTT (+ S/C) . . .

W(2) = 4

. . . passa un RTT (+ S/C) . . .

W(3) = 8 OK!


4. Abbiamo:

• 2RTT per il set-up della connessione (SYN - SYN/ACK - ACK/Richiesta dati);

• 2 ·(

MSSC

+ RTT)

per la fase non ottimale di trasmissione;

• P− (2 + 4)MSSC

per trasmettere i dati rimanenti.

Riassumendo in una formula:

L = 2RTT + 2 ·(

MSSC

+ RTT)

+P− (2 + 4)MSS

C= 0, 2 + 0, 231 + 31, 16 = 31, 681 s

Elenco delle figure

1.1 La macchina a stati finiti che implementa il TCP . . . . . . . . . . . . . . . . . . . . . . . . . . 61.2 Possibili inconvenienti in cui si può incappare nel TWH . . . . . . . . . . . . . . . . . . . . . 71.3 Evoluzione dell’RTO secondo RFC 793 e RFC 2988. . . . . . . . . . . . . . . . . . . . . . . . . 111.4 Misurazione dell’sRTT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111.5 Ambiguità nel calcolo dell’sRTT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121.6 Duplicazione dei numeri di sequenza . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131.7 Schema riassuntivo del calcolo dell’RTT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

2.1 Il meccanismo a finestra fra segmenti ricevuti e segmenti non trasmessi. . . . . . . . . . . . . 152.2 La questione delle capacità e l’adattività del controllo di flusso . . . . . . . . . . . . . . . . . 172.3 Meccanismo di Slow Start . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182.4 Distinzione fra SS e CA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192.5 Un esempio d’evoluzione della finestra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202.6 Effetto dell’approssimazione TSS << TCA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202.7 Condivisione della risorsa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212.8 L’algoritmo di fast recovery . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232.9 L’algoritmo di fast recovery (2) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232.10 Il TCP classico e il Tahoe (cioè TCP + Fast Rec.) a confronto . . . . . . . . . . . . . . . . . . . 242.11 I protocolli TCP Reno e TCP New Reno a confronto . . . . . . . . . . . . . . . . . . . . . . . . 25

3.1 Modello periodico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 303.2 Modello periodico (2) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 303.3 Andamento della finestra con perdite aleatorie . . . . . . . . . . . . . . . . . . . . . . . . . . . 323.4 Le variabili Yi e Ai . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 333.5 Le variabili aleatorie in gioco nel modello TD . . . . . . . . . . . . . . . . . . . . . . . . . . . 343.6 Modello TD+TO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 363.7 Modello TD+TO+AW . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 363.8 L’approssimazione introdotta dalla formula di AW . . . . . . . . . . . . . . . . . . . . . . . . 373.9 Modelli a confronto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 383.10 Influenza dell’RTT sul modello . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 383.11 Influenza di AW sul modello . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 393.12 Influenza di RTO sul modello . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 393.13 I passi imprescindibili per effettuare un trasferimento dati . . . . . . . . . . . . . . . . . . . . 403.14 Esempio con W = 6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 413.15 Schema esplicativo della formula di L2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 423.16 Raddoppio della finestra in SS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

4.1 Schema concettuale dello store-and-forward, nella commutazione di pacchetto . . . . . . . . . 484.2 Le classi di reti . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 494.3 Subnetting e Supernetting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

5.1 Schema logico di funzionamento di un router . . . . . . . . . . . . . . . . . . . . . . . . . . . 545.2 Patricia Trie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 545.3 Schema dei router di prima generazione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 555.4 Matrice di commutazione crossbar . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

109

110 ELENCO DELLE FIGURE

5.5 Rete di Clos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 565.6 Accodamento in uscita . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 565.7 Accodamento in ingresso . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 565.8 Accodamento virtuale in uscita . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 575.9 Accodamento a memoria comune . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

6.1 Grafo orientato (a sinistra) e un grafo non orientato (a destra) . . . . . . . . . . . . . . . . . . 596.2 Grafi aciclici, connessi, completamente connessi . . . . . . . . . . . . . . . . . . . . . . . . . . 606.3 Alcuni esempi di minimum spanning tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 606.4 Cammino di peso minimo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 616.5 Algoritmo di Bellman-Ford . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 636.6 Esempio grafico d’applicazione dell’algoritmo di Dijkstra . . . . . . . . . . . . . . . . . . . . 646.7 Interconnessione di più LAN e spanning tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . 656.8 Esempio di calcolo delle tabelle di routing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 666.9 Bouncing effect . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 676.10 Convergenza lenta . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 686.11 Il problema del count to infinity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 686.12 Situazione patologica e irrisolvibile . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69

7.1 Formato del pacchetto RIP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 747.2 Schema concettuale del routing gerarchico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 757.3 Distinzione logica fra host e router . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 757.4 Alcuni tipi di reti multiaccesso . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 767.5 Topologia a stella equivalente (con nodo virtuale) . . . . . . . . . . . . . . . . . . . . . . . . . 767.6 Router vicini e router adiacenti . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 777.7 Le fasi necessarie per lo scambio di informazioni e la sincronizzazione nell’OSPF . . . . . . 78

8.1 BGP: sessioni interne ed esterne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 828.2 BGP: scambio di path vector . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82

9.1 Schema concettuale di una rete funzionante tramite MPLS: LER e LSR . . . . . . . . . . . . . 869.2 Struttura e posizionamento dell’etichetta dell’MPLS. . . . . . . . . . . . . . . . . . . . . . . . 879.3 Il meccanismo del label stacking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 879.4 Il label swapping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 889.5 Label Distribution Protocol . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 899.6 Questione della fish picture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 909.7 Questione della fish picture [2] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90

A.1 Rappresentazione schematica dell’esercizio A.1.1 . . . . . . . . . . . . . . . . . . . . . . . . . 94A.2 Rappresentazione schematica dell’esercizio A.1.2 . . . . . . . . . . . . . . . . . . . . . . . . . 96A.3 Rappresentazione schematica dell’esercizio A.1.3 . . . . . . . . . . . . . . . . . . . . . . . . . 98A.4 Rappresentazione schematica dell’esercizio A.1.4 . . . . . . . . . . . . . . . . . . . . . . . . . 100A.5 Interpretazione grafica dell’esercizio A.2.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103A.6 Interpretazione grafica dell’approssimazione effettuata per il calcolo di AW. . . . . . . . . . 104A.7 Interpretazione grafica dell’approssimazione effettuata per il calcolo di AW (2). . . . . . . . 105

Retels ver 1.9

Documents

Transcript of Retels ver 1.9