Retels Ver 1.9

Appunti di Reti di Telecomunicazioni L-S (versione 1.11) Ingegnere Pazzo http://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 unicamente a me e non alle fonti, che consistono nelle slide del prof. Franco Callegati (dalle quali ho attinto le immagini) e nei miei modestissimi appunti. Chiedo già in anticipo scusa per qualsiasi errore dovesse far perdere tempo al lettore. Chiaramente questo riassunto, da solo, non sostituisce le lezioni del prof. (delle quali segue spudoratamente la traccia) e non è esaustivo e chiarificatore quanto può essere la spiegazione in aula degli argomenti ivi trattati. Nonostante questo, spero che possa essere un valido supporto per chiunque fosse interessato a leggerli o ad utilizzarli. Ing. Pazzo

Indice 1

2

3

Il protocollo TCP: generalità 1.1 Il segmento TCP . . . . . . . . . . . 1.2 Macchina a stati finiti . . . . . . . . 1.2.1 Three-way handshake . . . . . 1.2.2 Chiusura della connessione 1.3 Lo svolgimento del dialogo . . . . 1.3.1 Retransmission Time-Out . 1.4 Lo stato enstablished . . . . . . . . . 1.5 Messaggi di conferma (ACK) . . . 1.6 In sintesi . . . . . . . . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

5 5 5 7 8 8 9 12 12 13

Il protocollo TCP: controllo del flusso 2.1 Generalità . . . . . . . . . . . . . . . . . . . . . . . 2.2 Meccanismo a finestra scorrevole . . . . . . . . . . 2.2.1 Silly Window Syndrome . . . . . . . . . . . . 2.2.2 Algoritmo di Nagle . . . . . . . . . . . . . 2.3 Controllo di congestione . . . . . . . . . . . . . . . 2.4 Alcune definizioni ed evoluzione della CW . . . . 2.5 Alcune approssimazioni . . . . . . . . . . . . . . . 2.5.1 Un esempio . . . . . . . . . . . . . . . . . . 2.6 Altri aspetti del protocollo: algoritmi migliorativi 2.6.1 Fast recovery . . . . . . . . . . . . . . . . . . 2.6.2 Fast retransmit . . . . . . . . . . . . . . . . . 2.6.3 Reno e New Reno . . . . . . . . . . . . . . 2.7 In sintesi . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

15 15 15 16 16 17 19 20 21 22 22 24 25 26

Modelli analitici per le prestazioni del TCP 3.1 Ricerca di modelli matematici . . . . . . 3.2 Throughput e goodput . . . . . . . . . . . 3.3 Modello periodico . . . . . . . . . . . . 3.3.1 ACK ritardati . . . . . . . . . . . 3.4 Perdite aleatorie . . . . . . . . . . . . . . 3.4.1 Modello TD . . . . . . . . . . . . 3.4.2 Modello TD+TO . . . . . . . . . 3.4.3 Modello TD+TO+AW . . . . . . 3.5 Modelli a confronto . . . . . . . . . . . . 3.6 Latenza . . . . . . . . . . . . . . . . . . . 3.6.1 Finestra a dimensione fissa . . . 3.6.2 Finestra evolvente (dinamica) . . 3.7 In sintesi . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

29 29 29 30 31 32 32 36 36 37 40 41 43 45

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . . 3

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

INDICE

4 4

5

6

7

8

Intradamento e forwarding IP 4.1 Introduzione sulla commutazione . . . . . . . . . . 4.1.1 Nodi di commutazione: routing e forwarding 4.2 Indirizzi IP . . . . . . . . . . . . . . . . . . . . . . . . 4.2.1 Instradamento e table look-up . . . . . . . . . 4.3 In sintesi . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

47 47 48 48 50 50

Architetture dei router IP 5.1 Tipologie commerciali di router . . . . . . 5.2 Schema funzionale, routing vs. forwarding 5.3 Table look-up . . . . . . . . . . . . . . . . . 5.4 Architettura dei router . . . . . . . . . . . 5.4.1 Crossbar . . . . . . . . . . . . . . . 5.4.2 Rete di Clos . . . . . . . . . . . . . 5.5 Posizionamento delle memorie . . . . . . 5.6 In sintesi . . . . . . . . . . . . . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

53 53 53 53 54 55 55 56 57

Algoritmi di routing 6.1 La teoria dei grafi e il routing . . . . . . . . . . . . 6.2 Algoritmi per il calcolo del minimum spanning tree 6.2.1 Algoritmo di Kruskal . . . . . . . . . . . . 6.2.2 Algoritmo di Prim . . . . . . . . . . . . . . 6.3 Shortest path . . . . . . . . . . . . . . . . . . . . . . 6.4 Algoritmi per il calcolo dello SP . . . . . . . . . . 6.4.1 Bellman-Ford . . . . . . . . . . . . . . . . . 6.4.2 Dijkstra . . . . . . . . . . . . . . . . . . . . 6.5 Applicazione alle reti . . . . . . . . . . . . . . . . . 6.5.1 Flooding . . . . . . . . . . . . . . . . . . . . 6.5.2 Deflection routing . . . . . . . . . . . . . . . 6.5.3 Load sharing . . . . . . . . . . . . . . . . . . 6.6 Shortest Path Routing . . . . . . . . . . . . . . . . . 6.6.1 Protocolli distance vector . . . . . . . . . . . 6.7 Soluzioni migliorative ai protocolli distance vector 6.7.1 Split Horizon . . . . . . . . . . . . . . . . . . 6.7.2 Triggered Update . . . . . . . . . . . . . . . . 6.8 Protocolli path vector . . . . . . . . . . . . . . . . . 6.9 Protocolli link state . . . . . . . . . . . . . . . . . . 6.10 In sintesi . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . .

59 59 61 61 61 61 62 62 63 63 64 65 65 66 66 69 69 69 69 70 70

IGP: Interior Gateway Protocols 7.1 RIP . . . . . . . . . . . . . . . . . . . . . . . 7.2 OSPF: Open Shortest Path First . . . . . . . . 7.2.1 Distinzione logica fra host e router . 7.2.2 OSPF e reti multi-accesso . . . . . . 7.2.3 Messaggi dell’OSPF . . . . . . . . . 7.3 In sintesi . . . . . . . . . . . . . . . . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

73 73 74 75 76 77 78

. . . .

81 81 81 83 84

. . . . . . . .

. . . . . . . .

. . . . . .

. . . . . . . .

. . . . . .

. . . . . . . .

. . . . . .

. . . . . .

EGP: Exterior Gateway Protocols 8.1 L’EGP per antonomasia: Exterior Gateway Protocol 8.2 BPG: Border Gateway Protocol . . . . . . . . . . . . . 8.2.1 Attributi e tipi di messaggio . . . . . . . . 8.3 In sintesi . . . . . . . . . . . . . . . . . . . . . . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

INDICE 9

5

MPLS: sostituzione d’etichetta 9.1 Introduzione: il label switching . . . . . . . 9.2 Nomenclatura . . . . . . . . . . . . . . . . 9.3 Uso e trattamento delle label . . . . . . . 9.4 Allocazione delle label . . . . . . . . . . . 9.5 Altri aspetti . . . . . . . . . . . . . . . . . 9.5.1 Controllo dei Label-Switched Paths 9.5.2 Label Distribution Protocol . . . . . 9.5.3 Fish picture . . . . . . . . . . . . . . 9.6 In sintesi . . . . . . . . . . . . . . . . . . .

A Esercizi A.1 Protocolli di rete, analisi di CW A.1.1 Esercizio 1 . . . . . . . . A.1.2 Esercizio 2 . . . . . . . . A.1.3 Esercizio 3 . . . . . . . . A.1.4 Esercizio 4 . . . . . . . . A.2 Modelli per il TCP . . . . . . . A.2.1 Esercizio 1 . . . . . . . . A.2.2 Esercizio 2 . . . . . . . . A.2.3 Esercizio 3 . . . . . . . . A.3 Latenza . . . . . . . . . . . . . . A.3.1 Esercizio 1 . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

85 85 86 87 88 89 89 89 90 90

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

93 93 93 95 97 99 101 101 101 103 104 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 svincolare gli strati superiori dai problemi di rete. È un protocollo di tipo connection-oriented (al contrario dell’UDP che è connection-less) e gestisce una connessione end-to-end (punto-punto) e full-duplex (bidirezionale); prevede inoltre procedure per l’instaurazione della connessione, il controllo del suo corretto andamento e la chiusura. Tutte le informazioni necessarie al corretto svolgimento dell’algoritmo TCP sono contenute nel TCB (transmission control block). L’interfaccia con le applicazioni, invece, non è definita a 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 standard di 20 byte, un header variabile con varie opzioni, un payload di dimensione variabile contente i dati dell’applicazione. Ogni segmento può avere una dimensione massima pari a MSS (Maximum Segment Size) e tipicamente contiene - oltre ai dati - informazioni come la porta sorgente, la porta destinazione, il numero di sequenza, l’acknowledge-number, un checksum per controllare se vi sono errori, alcuni bit per settare le opzioni (URG per considerare il campo Urgent Pointer, ACK considerare il campo Acknowledge, RST per resettare 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ò assumere è pari a 216 − 20(header TCP) − 20(header IP) = 65495 byte, cioè pari alla dimensione del payload IP meno le intestazione, ma per l’Ethernet (che è il caso sul quale ci soffermeremo) è molto inferiore in quanto 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 tratteggiate indicano un’azione tipica di un server, le linee nere le azioni tipiche dei client e quelle chiare gli eventi ‘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 seguendo 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 la sua richiesta (siamo ora nello stato SYN RECIEVED). Il client riceve la conferma del server e manda a sua 7

CAPITOLO 1. IL PROTOCOLLO TCP: GENERALITÀ

8

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 entrambi i comunicanti finiscono nello stato ENSTABLISHED (in verde). Quello illustrato fin’ora è il cosiddetto three-way handshake (‘stretta di mano a tre tempi’) e, alla prova dei fatti, si è dimostrato un metodo abbastanza 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 non completamento del TWH (freccia nera da SYN RCVD a LISTEN). La parte inferiore del diagramma a stati si riferisce invece alla chiusura della connessione: la chiusura può essere passiva (da parte del server, che riceve 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 un FIN e il C, che è in stato FIN WAIT 2, risponde con un ACK. 1 Se

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 riceve anche il FIN del server e va in CLOSING, confermando il tutto con un ACK. Il server poco prima aveva 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 come nel caso 1, tranne per il fatto che S non vuole spedire dati e in una botta sola invia sia l’ACK che il FIN. Si noti che il client rimane per un po’ nello stato di time wait, utile per fare sì che i pacchetti dell’attuale connessione 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, sia quelli contenenti dati che quelli contenenti informazioni di servizio, possono effettivamente perdersi nella rete.

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, duplicazione o ritardo dei pacchetti. In tabella 1.1 si illustra il procedimento con particolare riferimento ai numeri di sequenza. Per semplicità indicheremo i due colloquianti con CLIENT e SERVER (ma, per generalità, si possono pensare tali due computer come due calcolatori qualsiasi A e B). Chi parla? CLIENT CLIENT CLIENT

SIN bit 1 1 0 0

ACK bit 0 1 1 0

Tabella 1.1:

SeqN x y x+1 x+1

AckN x+1 y+1 y+1

Chi parla? SERVER

→ inizio invio dati

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):

CAPITOLO 1. IL PROTOCOLLO TCP: GENERALITÀ

10

• 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 con SIN e ACK entrambi a 1 dà il via alla trasmissione dati (l’altro eventuale pacchetto con SIN e ACK ad 1 è del tutto superfluo); • Pacchetti d’apertura ritardatari: uno dei due tentativi di connessione viene inibito tramite l’attivazione 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à stabilirne una nuova. Questo potrebbe dar adito a diverse ’incarnazioni’ della medesima connessione logica: se le due incarnazioni non sussistono contemporaneamente questo non è un dramma, mentre la sopravvivenza in rete di due (o più) incarnazioni distinte è un problema da non sottovalutare in quanto potrebbero gironzolare pacchetti aventi gli stessi indirizzi (IP + porta), gli stessi numeri di sequenza, ma contenuto diverso! Il TCP risolve questo problema (v. paragrafo 1.4) riallineando i numeri di sequenza e ristabilendo il parallelismo: uno dei due host, infatti, crederà che la connessione precedente 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 bit RST.

1.2.2

Chiusura della connessione

Il TCP ce la mette tutta per garantire che, alla chiusura della connessione, non vengano persi dati. Anche 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’host che intende terminare la trasmissione invia un segmento con il bit FIN a 1 e, ricevuto l’ACK, considera chiuso 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 di chiudere la connessione: in tal caso, infatti, la chiusura avviene in maniera esattamente simmetrica da ambo 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 macchine completamente 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 propagazione non essere mai costante; • possono esserci, in maniera aleatoria, aumenti/diminuzioni della banda dovuti all’arrivo di nuovi utenti (o alla scomparsa di altri); • etc. . . Per risolvere questi problemi, il TCP utilizza un protocollo a finestra scorrevole e utilizza quattro contatori: • 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 i due host comunicanti rimangano l’uno in attesa dell’altro: il ricevitore attende i nuovi dati, mentre il trasmettitore aspetta di ricevere la conferma (ACK) in grado di allargargli la finestra. Per prevenire questa forma di deadlock è necessario che il trasmettitore utilizzi un persist timer che interpelli il ricevitore in maniera periodica;

1.3. LO SVOLGIMENTO DEL DIALOGO

11

• keep-alive timer: non necessariamente, se è attiva una connessione fra due host, vi è un trasferimento di 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 liberare le risorse da essa occupate. Allo scadere del keep-alive timer, uno dei due host invia all’altro un messaggio di prova; se riceve risposta allora il timer viene resettato mentre, se tutto tace, vengono mandati altri 9 messaggi di prova con un intervallo pari a 75 secondi l’uno dall’altro. Presumibilmente, 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 un tempo pari a 2MSL 2 , allo scadere del quale - se nulla è accaduto, lo stato della connessione passa a CLOSED. Questo timer vuole garantire l’estinzione di segmenti appartenenti a precedenti incarnazioni, 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 sia stato ricevuto l’ACK si assume che il segmento non sia stato ricevuto. L’RTO dev’essere dimensionato in relazione al tempo di andata e di ritorno (Round Trip Time, RTT) ma, soprattutto, deve poter essere determinato 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 comparsa l’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 effettuata semplicemente traendo l’ultima misurazione3 eRTT (0) = sRTT (0) Quelle successive vengono invece determinate dando un certo peso (1 − α) alla stima dell’istante precedente (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è alla misurazione dell’istante n − 1: sRTT (n − 1)): tanto più è piccolo e tanto più faremo riferimento alle stime del passato piuttosto che alla misurazione (sRTT) corrente. Tale procedura di calcolo dell’eRTT viene detta Exponential Weighted Moving Average: Exponential perché il peso dei valori passati diminuisce in modo esponenziale a favore dei valori recenti4 ; Weighted perché il parametro α ci permette di fissare 2 MSL

= Maximum Segment Lifetime, noto a priori (nell’RFC 793 è fissato a 2 minuti). Perché bisogna aspettare 2MSL e non semplicemente MSL? Semplicemente perché adottiamo al filosofia del caso peggiore e vogliamo che si estinguano sia i pacchetti delle vecchie connessioni (vivono al massimo per un tempo pari a MSL) che le loro conferme (aspettiamo un altro MSL)! 3 In questo caso non abbiamo alternative per mancanza di informazioni, indi per cui la cosa più logica è quella di affidarsi alla misurazione fatta in quello stesso istante. 4 Si ha infatti eRTT (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) ... n

eRTT (n) = (1 − α)n · eRTT (0) + ∑ (1 − α)n−i α · sRTT (i ) i =1

CAPITOLO 1. IL PROTOCOLLO TCP: GENERALITÀ

12

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 viene dato 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 calcolo dell’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; Jacobson ha quindi proposto di considerare anche le fluttuazioni della situazione (rappresentate dal parametro vRTT): 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 presa come parametro. La relazione soprascritta indica che, se la linea è instabile e ballerina, è opportuno sovradimensionare l’RTO; in caso contrario, una buona stabilità della linea incoraggerebbe a mantenere l’RTO il più vicino possibile a eRTT (tendiamo a ’fidarci’ della linea). Per visualizzare meglio quanto detto si 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 attiva una sola misurazione alla volta quindi, in caso di trasmissioni consecutive a breve distanza, solamente la prima valuta l’sRTT (figura 1.4). Un inconveniente comune (figura 1.5) è quello che potrebbe avvenire quando vi è ritrasmissione dei dati (in seguito alla perdita di un pacchetto o allo scadere dell’RTO): per questo motivo in caso di ritrasmissione 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. 5 Come 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. 6 1 minuto. 7 1 secondo.

1.3. LO SVOLGIMENTO DEL DIALOGO

Figura 1.3:

13

Evoluzione dell’RTO secondo i due RFC illustrati. Il risultato è migliore tanto più si è vicini alla linea rossa. Si noti che Jacobson ha dei grossi vantaggi quando la linea è stabile, mentre si tiene dalla parte del sicuro 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 tempo maggiore al ricevitore di rispondere: per questo motivo, ad ogni ritrasmissione, il TCP raddoppia l’RTO fino al raggiungimento di un valore massimo.

CAPITOLO 1. IL PROTOCOLLO TCP: GENERALITÀ

14

Figura 1.5:

1.4

Ambiguità nel calcolo dell’sRTT

Lo stato enstablished

Per avere massima flessibilità si sceglie di assegnare un numero non ai segmenti bensì ai singoli byte trasportati dai segmenti: si comincia a numerare da un numero X scelto all’atto dell’apertura della connessione8 e la conferma di avvenuta ricezione viene data mettendo nel campo Ack number il numero del byte successivo all’ultimo ricevuto (cioè del primo byte che ci si aspetta di ricevere). Definito questo meccanismo, 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, mentre l’altra arriva solo successivamente9 . In tal caso la trasmissione continua e, una volta che si è esaurito lo spazio di numerazione, vengono riciclati numeri già utilizzati10 : questo significa che prima o poi sarà generato un altro pacchetto avente numero di sequenza X (ma diverso da quello del giro precedente): se entrambi gireranno per la rete avremo due segmenti con stessa intestazione ma contenuto diverso! Il peggio che può capitare, in questo caso, è che la copia ritardata (quella del giro prima) 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 il tempo. Le rette nere spesse rappresentano l’andamento crescente del numero di sequenza col passare del tempo: 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) si riferisce all’esistenza in vita di un pacchetto avente numero di sequenza pari a quello cui si era arrivati prima del crash della connessione C1. La connessione C2 riparte e, in entrambi i casi, finiamo per cadere nella trappola dei ’numeri doppi’: l’esempio ci mostra che questo può accedere sia se l’ISN (Initial Sequence Number) viene fissato a zero di default (a sinistra), sia se viene posto pari a un contatore11 (a destra). L’unico modo veramente sicuro in grado di farci evitare questo inconveniente è quello di attendere un MSL prima di 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’ (piggybacking) 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 8 Questo 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. 9 Quello che stiamo per dire vale anche nel caso in cui un host venga riavviato a causa di un problema e rimanga attiva l’incarnazione di tale connessione. 10 Questo è 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 parametro veniva fissato a 2 minuti, ma con l’avvento di reti sempre più veloci si è reso necessario abbatterlo notevolmente. 11 In quest’ultimo caso ISN è funzione del tempo utilizzando un sistema di conteggio a 32 bit con incremento ogni 4 microsecondi. 12 Quel 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 il numero. Si potrebbe, ad esempio, inviare un ACK ogni due segmenti utilizzando il sistema della finestra scorrevole. Sia ora WT la finestra di trasmissione e WR la finestra di ricezione, con WT e WR minori dello spazio di 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 segmento con SeqN > N o < N, allora il ricevitore interpreterà quello che gli arriva rispettivamente come un segmento fuori sequenza (numero di sequenza troppo alto) o come un duplicato ritardato (numero di sequenza appartenente ’al passato’). Nel primo caso il ricevitore memorizzerà il segmento, purché esso stia all’interno della sua finestra WR , ritrasmetterà l’ultima conferma inviata (ACK N + 1) e, una volta che avrà ricevuto tutta la sequenza completa (compreso il segmento N + 1), comunicherà direttamente ’ACK X + 1’ sbloccando la sua finestra; nell’altro caso scarterà il pacchetto considerandolo un doppione. Quanto detto fin’ora funziona purché il ricevitore sia dotato di memoria: chiaramente conviene memorizzare meno cose possibili quindi, finché non accade nulla di imprevisto, ogni pacchetto confermato in ordine corretto cancella 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 adabile. 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 vericare la correttezza del contenuto, vari campi per le segnalazioni di servizio (ag-bits, etc. . . ) e inne 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 13 Ad

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

CAPITOLO 1. IL PROTOCOLLO TCP: GENERALITÀ

16

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 matematiche 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ù ranata 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). Inne, 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 vericarsi di un evento che ha interrotto il dialogo, di inibire qualsiasi ulteriore tentativo di connessione per un tempo pari a MSL (TCP quiet-time).

14 Se

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 non per questo uno dei due colloquianti ha licenza di saturare l’altro: per tal motivo si utilizza un meccanismo a finestra scorrevole. Il corretto dimensionamento della finestra deve tuttavia tenere conto - oltre che della velocità 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 congestione in rete non aiuta a prendere delle decisioni senza uno straccio d’informazione. Per potersi conoscere, i due host devono quindi potersi comunicare l’un l’altro le dimensioni della memoria di ricezione: per questo motivo, 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 di dimensione 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 stima effettuata 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 viene saturato: 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 1 La dimensione della finestra può essere data in byte o in segmenti: noi preferiremo generalmente questa seconda scelta, indicando con w la finestra in byte e W la finestra in segmenti. Si noti che si ha w = MSS · W, dove MSS è il Maximum Segment Size.

17

CAPITOLO 2. IL PROTOCOLLO TCP: CONTROLLO DEL FLUSSO

18

• 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 con AW > 0. Siamo in pieno deadlock; per questo il TCP permette che sia sempre possibile inviare un segmento di 1 byte anche se AW = 0: dal momento che l’Advertised Window diventa pari a zero, infatti, parte il persist timer allo scadere del quale si invia un segmento di un byte (SeqN = X + 1, dove X è il numero di sequenza dell’ultimo pacchetto correttamente trasmesso) avente lo scopo di sbloccare la finestra. Se poi il ricevitore risponde 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 0 = 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’applicazione è lenta ad accettare i dati e legge un byte alla volta, comunicando una dimensione di finestra sempre troppo piccola. Quest’ultima evenienza prende il nome di silly window syndrome (abbreviato in SWS): • 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 aumentare la 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 il trasmettitore 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 inviarti tutto, ti invio almeno metà di quello che potresti); • non vi sono ACK pendenti ed è possibile trasmettere tutto ciò che è in attesa nel buffer di trasmissione. 2 Wikipedia

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

Nel caso in cui il processo di scrittura dei dati nel buer TCP del mittente sia molto lento, il protocollo spedirà una serie di pacchetti contenti una quantità di dati molto bassa, con un uso ineciente del canale (è infatti molto meglio spedire un solo pacchetto con n byte di dati, per il quale bisogna pagare il peso di un solo header, che spedire n pacchetti contenenti solo un byte di dati, per ognuno dei quali bisogna pagare il peso di un header, un rapporto di 1/n contro n/n = 1). La soluzione a questo problema consiste nel trattenere i dati nel buer allo scopo di spedirli in un unico segmento. Tuttavia un'attesa troppo lunga potrebbe causare dei ritardi troppo grandi nella trasmissione. Un'ottima soluzione a questo problema è fornita dall'algoritmo di Nagle, secondo il quale i dati devono essere accumulati nel buer per poi venire spediti in un unico blocco alla ricezione dell'ACK dell'ultimo pacchetto trasmesso o quando si raggiunge la massima dimensione ssata per un segmento (MSS). Questo semplicissimo algoritmo riesce a risolvere il problema tenendo anche conto della velocità di trasmissione dei pacchetti: se questa è più lenta della scrittura dei messaggi (il mittente riesce ad accumulare una notevole quantità di dati nel buer prima dell'arrivo del riscontro) vengono creati pacchetti con il massimo rapporto dati-header, sfruttando al meglio le risorse del canale. Se invece la rete è più veloce, i pacchetti risulteranno più piccoli, assicureranno una certa continuità nella trasmissione e verrà garantito comunque un utilizzo più eciente delle risorse del canale 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 collaterale, 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 chiarire come quest’ultimo parametro venga determinato. Ebbene, il TCP cerca di adattare la dimensione della finestra in funzione delle condizioni di congestione della rete, aumentandola quando si ricevono correttamente gli ACK e restringendola quando si verificano perdite: da qui l’esistenza del parametro CW. Avendo a disposizione una banda B (misurata in byte/s), il massimo throughput si ottiene quando il protocollo a finestra non limita la velocità di scambio dei dati, cioè quando nel famoso schema con le due aste verticali rappresentanti client e server non vi sono buchi e ogni momento diventa un istante valido per trasmettere dati nuovi. Se siamo in questo caso la finestra dev’essere più grande di: wid ≥ RTT · B → In byte wid Wid = → In segmenti MSS W w (byte/sec) = (segmenti/sec) Massimo throughput → S = RTT RTT In questo caso si utilizza il massimo della capacità disponibile; gli altri due casi, quelli cioè in cui la finestra è 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 intero il flusso di dati nelle parti intermedie a velocità minore: in questo caso è infatti necessario accodare nei 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 alla capacità e alla banda della rete: se facciamo l’assunzione che vi siano parti di rete ad elevata capacità ed altre a banda più ristretta (rispettivamente rappresentate da tubi più larghi e più stretti), si nota come il tempo necessario a trasmettere pacchetti di dimensione fissata sia molto diverso da zona a zona. Il collo di bottiglia rappresentato dal primo tratto di linea avente banda (stretta) pari B ha l’effetto di rallentare la trasmissione complessiva di dati: giunti alla parte di rete (veloce) del ricevitore, infatti, i pacchetti sono fra

20

CAPITOLO 2. IL PROTOCOLLO TCP: CONTROLLO DEL FLUSSO

loro temporalmente molto più distanziati rispetto a quanto lo fossero in partenza. Il ritorno, immaginando che la situazione sia simmetrica rispetto all’andata, non ritarda ulteriormente i pacchetti essendo questi dei piccoli ACK inviati ad una frequenza ‘sfrondata’ dalla rete d’andata e quindi più che gestibili. Il protocollo a finestra, come abbiamo detto, permette al trasmettitore di inviare dati solo dal momento che riceve le necessarie conferme: se esse giungono con la frequenza indicata in figura, la successiva trasmissione farà sì che il trasmettitore già ‘ab ovo’ invii pacchetti ad una velocità accordata sulla base di quanto possa sopportare la rete. Tornando alla questione di partenza, come dimensioniamo CW considerando quanto detto e il fatto che la banda disponibile B può cambiare durante la connessione? A questo proposito, fatte le ipotesi che trasmettitore e ricevitore siano correttamente configurati, che non vi siano problemi di SWS (vedi paragrafo 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 diverse dinamiche di CW: • slow start (SS): all’inizio della trasmissione W è3 ≤ 2 e, per ogni ACK ricevuto senza scadenza di RTO 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 Slow Start Threshold (SSTHR)5 , che all’apertura della connessione è fissata ad un valore arbitrariamente alto ma che è anche in grado di cambiare dinamicamente durante la trasmissione dati. In SS si ipotizza 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 il ritmo). 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 avoidance passiamo ad una crescita lineare onde evitare di esagerare e incappare nella perdita di pacchetti. La finestra w viene incrementata di un MSS per ogni RTT (o, se si preferisce, ogni RTT W aumenta di un 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 la trasmissione (e se tutto è andato bene) vengono ricevuti 10 ACK e la nuova finestra W (n + 1) diventa7 1 W (n) + 10 · = W (n) + 1. 10

2.4. ALCUNE DEFINIZIONI ED EVOLUZIONE DELLA CW

Figura 2.4:

2.4

21

Distinzione fra SS e CA

Alcune definizioni ed evoluzione della CW

Loss Window (LW): quando scade un RTO il trasmettitore ritiene perso un segmento, che quindi dev’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 la rete). 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 della CW, fra slow start e congestion avoidance, scade il Retransmission Time Out8 ? In tal caso il protocollo reagisce ripartendo dalla SS (W = 1) e imponendo che la SSTHR diventi pari al flight-size/2 (o, se quest’ultima quantità è più piccola di due segmenti, a 2). Si noti che, grazie a questo meccanismo, la rete cerca di adattarsi allo stato della congestione pur mantenendo un atteggiamento greedy (avido): finché si può, infatti, il TCP cerca di allargare sempre più la sua finestra. Non c’è però pericolo che questo consegni l’intera rete in mano ad un unico host visto che tutti quanti condividono la stessa politica: infatti il meccanismo delle perdite ha lo scopo di inibire colui che sovraccarica il mezzo trasmissivo, ridimensionando la sua voracità; piuttosto, il risvolto 3 Quindi,

in byte, w ≤ 2MSS. è una slow start per modo di dire: in realtà la finestra cresce molto di più qui che in congestion avoidance. 5 Manterremo la convenzione di scrivere ssthr in byte e SSTHR in segmenti. 6 Non possiamo parlare di istanti perché gli ACK e le trasmissioni non avvengono tutte nello stesso momento, quindi approssimeremo il cosiddetto passo con un lasso di tempo poco più grande di RTT, quello - cioè - che permette ad un numero di segmenti pari a quello contenuto nella finestra di essere trasmessi e confermati. 7 In realtà, per essere più precisi, questa relazione dovrebbe essere scritta come approssimazione visto che l’incremento di W avviene 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, 4 Quindi

W = (4 + 1)/4 = 4, 25 Ricevuto il secondo ACK abbiamo W = (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 noti quindi che non si ha esattamente W = W + 1 dopo la ricezione di tutti gli ACK della finestra. Di conseguenza, la crescita di W non è esattamente lineare, ma noi per semplicità la considereremo tale. 8 Tipicamente questo evento viene interpretato dal TCP come indice di congestionamento della rete visto che, con buona stima del RTT, il time out scaduto è praticamente sempre dovuto alla perdita del segmento.

CAPITOLO 2. IL PROTOCOLLO TCP: CONTROLLO DEL FLUSSO

22

Figura 2.5:

Un esempio d’evoluzione della finestra

positivo di quest’indole è quello di permettere ai colloquianti di occupare l’eventuale banda rilasciata da un calcolatore che ha abbandonato la conversazione: in questo modo, la banda è teoricamente sempre sfruttata 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 visto che, in ultima analisi, la quantità di dati trasmessi è pari all’integrale della curva presente nel grafico finestra/tempo e, chiaramente, l’area che si trova sotto la curva che evolve in CA è maggiore di quella sotto la curva in zona di SS. Se l’ipotesi TSS << TCA è vera, allora possiamo trascurare la fase di SS e immaginare 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 moltiplicativo: se r è la quantità di dati inviata dal trasmettitore • additive-increase: la finestra cresce in maniera additiva. Al passo i-esimo si ha: r ( t i +1 ) = r ( t i ) + c

con c << rmax

• multiplicative-decrease: la finestra decresce in maniera moltiplicativa. Se si ha una situazione di congestione al passo i-esimo si ha: r ( t i +1 ) = a · r ( t i )

con a < 1

Perché tutte queste definizioni? Il punto cui vogliamo arrivare è dimostrare che il TCP permette un’equa distribuzione della banda disponibile: questo significa che se un certo numero di colloquianti (noi per semplicità ne considereremo due) condividono una certa banda, a regime finiranno per avere più o meno tutti 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 stessa banda. Siccome entrambi i calcolatori (r1 e r2 sul grafico: gli assi rappresentano la banda destinata a 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 contro l’impossibilità di congestionare troppo la rete: prendiamo per esempio r2 che, per ipotesi, parte con un maggior sfruttamento della banda. Dopo un appagante incremento additivo, la freccia verde si scontra contro il limite (linea scura) e si ha in decremento moltiplicativo (freccia rossa). Il giro successivo, r2 non potrà occupare così tanta banda come l’ultima volta perché, nel frattempo r1 gli avrà rosicchiato un po’ di risorse da sotto i piedi. Nonostante questo, r2 ha un incremento additivo che lo riporta (quasi) ai livelli di 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 continua fino a quando la freccia rossa e la freccia verde hanno la stessa pendenza, pari tra l’altro alla bisettrice del nostro quadrante: giunti lì, a meno di inconvenienti particolari, i due host avranno decrementi ed incrementi simili e ciò porterà ad avere, a regime, una sostanziale equipartizione della banda (il punto di

CAPITOLO 2. IL PROTOCOLLO TCP: CONTROLLO DEL FLUSSO

24

intersezione fra la bisettrice e la retta ad essa perpendicolare è quello di massimo equilibrio fra le risorse destinate ai due calcolatori). Si noti che tutto questo è reso possibile dall’atteggiamento greedy, avido e assetato 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 sempre, ma ogni K > 1 corrette ricezioni) può portare a degli squilibri. Se prendiamo in considerazione l’esempio nel paragrafo 2.5.1 e facciamo l’ipotesi che uno dei due colloquianti invii un ACK ogni quattro segmenti invece che ad ogni singolo datagramma, allora quest’ultimo calcolatore sarà indiscutibilmente danneggiato perché, al contrario dell’altro contendente, non riuscirà a raggranellare banda al suo stesso ritmo. Preme inoltre sottolineare che l’incremento di CW è funzione del round-trip time; due connessioni che sperimentano diversi RTT aumentano in modo diverso le proprie finestre e si tende a favorire connessioni con 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 ad inviare un ACK duplicato9 per ogni segmento fuori ordine. La generazione di ACK duplicati dovuti alla perdita di un segmento è un evento che può essere utilizzato come indicazione di congestione unitamente al time-out. Sono quindi stati proposti ulteriori algoritmi per sfruttare al meglio questa situazione: di questi 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 segmento avente come numero di sequenza quello indicato dall’ackN duplicato. E poi che si fa? Si potrebbe ripartire dall’inizio della slow start, ma quella di far ricrollare la finestra allo stadio embrionale non è una scelta furbissima: il fatto che il ricevitore ci stia rispondendo, infatti, è sintomo che i pacchetti stanno effettivamente giungendo a destinazione e che quindi vi è abbastanza reattività da parte della rete (e non vi è perciò una situazione esageratamente congestionata). Inoltre, potrà pure capitare che ogni tanto si perde qualche pacchetto!10 Considerando quindi il triplo ACK duplicato come evento ’meno grave’ di un RTO effettivamente scaduto, si preferisce agire ritrasmettendo il solo segmento mancante e continuando la 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 della rete; • si gonfia (provvisoriamente) la finestra W (window inflation) aumentandone istantaneamente la dimensione 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 in quando 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 avoidance ponendo W = SSTHR (la finestra viene sgonfiata). 9 Che

si riferisce all’ultimo segmento ricevuto correttamente.

10 Suvvia!

2.6. ALTRI ASPETTI DEL PROTOCOLLO: ALGORITMI MIGLIORATIVI

Figura 2.8:

Figura 2.9:

25

L’algoritmo di fast recovery

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 di ripartire. Anche solo due pacchetti persi in breve tempo avrebbero infatti creato una situazione di stallo e avrebbero fatto ripartire il tutto dalla slow start, con un conseguente crollo della finestra. Non è però tutto

CAPITOLO 2. IL PROTOCOLLO TCP: CONTROLLO DEL FLUSSO

26

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 spedire immediatamente, senza aspettare l’RTO come invece accadrebbe nel TCP classico, il pacchetto del quale si è 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é il dimezzamento della finestra blocca la trasmissione a causa delle perdite multiple. 11 O magari è il fast recovery ad essere una versione più evoluta del fast retransmit: la sostanza però è quella. Mediamente il fast recovery funziona meglio, ma in alcuni casi potrebbe non essere così, quindi ha senso vedere questi due algoritmi separatamente. 12 Da Wikipedia:

TCP Tahoe prevede che ogni qual volta si verichi 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 iniziale della nestra di congestione corrente pari a MSS (massima dimensione di un segmento TCP). Si ha quindi una 'ripartenza lenta', la crescita avverrà lentamente ma in maniera esponenziale no a raggiungere il valore di soglia prima determinato [è la SS]. Oltre questo valore la crescita avviene linearmente [CA] no a quando non si verica 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 lentamente per cercare di raggiungere il livello di congestione il più lentamente possibile.

2.6. ALTRI ASPETTI DEL PROTOCOLLO: ALGORITMI MIGLIORATIVI

2.6.3

27

Reno e New Reno

Nel caso illustrato nel paragrafo 2.6.1 il cosiddetto TCP ’Reno’13 (SS+CA+Fast Recovery) non sarebbe andato molto meglio (v. figura 2.11). Il ’New Reno’14 , invece, avrebbe avuto delle performance migliori (si faccia 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 finestra 2: il trasmettitore è nuovamente bloccato ed è costretto ad attendere l’RTO di 16, allo scadere del quale si ritrasmette 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 un po’ più di tempo, quel che basta per scavalcare i pacchetti corretti successivi a quello sbagliato e poter riprendere la numerazione in santa pace, senza aspettare lo scadere degli RTO. La fase di recupero inizia all’istante (che chiameremo T0 ) di ricezione del quarto duplicato: giunti lì memorizziamo infatti seqN(T0 ) 13 Ancora

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 trasmissione impostando la nestra corrente al valore minimo di 1 MSS. Quando invece l'evento perdita è generato dalla ricezione di 3 ACK duplicati, il TCP Reno assume che la rete sia ancora in grado di trasferire qualcosa. Il valore soglia viene impostato alla metà del valore della nestra di congestione al momento della ricezione di tre ACK duplicati e la trasmissione riparte impostando il valore di nestra corrente pari al valore di soglia e proseguendo nell'invio incrementando di MSS, ad ogni RTT, il valore della nestra di congestione. 14 La

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 nelle situazioni 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 riscontrano pacchetti intermedi, e non gli ultimi pacchetti che necessiterebbero riscontro, dopo che è stata già iniziata la fase di Fast Retransmit in seguito all'arrivo di tre ACK duplicati. Quando uno di questi ACK si presenta durante una fase di Fast Retransmit (cioè in seguito alla 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.

CAPITOLO 2. IL PROTOCOLLO TCP: CONTROLLO DEL FLUSSO

28

= 17. Questo numero indica infatti il seqN dell’ultimo pacchetto che si presume sia stato correttamente ricevuto dal ricevitore: dopo la ripetizione dei 3 pacchetti aventi seqN = 13 esso rappresenterà quindi la prima 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 si riceve ackN > seqN(T0 ). Se dopo la spedizione del segmento perduto (il 13simo) tutta la finestra è stata ricevuta correttamente allora arriverà ackN = 18 (si esce dal Fast Recovery) mentre, se sono stati perduti altri segmenti della finestra, ackN < 18 (ACK parziale, che re-inizializza RTO).

2.7

In sintesi

Per poter comunicare in maniera eciente, 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 buer 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 buer 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 buer 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, incrementandolo quando si ricevono gli ACK e ridimensionandolo quando si vericano 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 inne (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 dierenti 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 1 con l'incremento della nestra, onde evitare di saturare il collegamento; la crescita è infatti di W = W + W

ad 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). 15 L’aggettivo slow è fortemente fuorviante: esso si riferisce alla dimensione di W, inferiore a quella che si ha in CA, e non al suo ritmo di crescita, che invece è molto sostenuto. 16 In 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'eventuale 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 sucientemente ecace (è 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

) nonché la nestra17 e si spedisce immediatamente, senza attendere lo scadere dell'RTO, il pacchetto del quale si è ricevuta la richiesta duplicata; 2

• fast recovery: come il fast retransmit, solo che no a quando non arriva la conferma del pacchetto perso si gona 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 gonamento 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. cioè, il cui numero di sequenza è stato salvato nella variabile recover quando sono arrivati i tre ACK duplicati

18 Quello,

30

CAPITOLO 2. IL PROTOCOLLO TCP: CONTROLLO DEL FLUSSO

Capitolo 3

Modelli analitici per le prestazioni del TCP 3.1

Ricerca di modelli matematici

Le prestazioni del protocollo TCP vengono influenzate fondamentalmente dalla dinamica della finestra di trasmissione W (che viene regolata dal controllo di congestione e dal protocollo ARQ) nonché dai processi di ritardo e perdita di segmenti in rete (vedi capitolo ??). Un modello analitico del TCP deve descrivere 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 possibili eventualità che si potrebbero presentare; • è difficile tenere conto di tutta l’infrastruttura che si trova tra ricevitore e trasmettitore: tra i due colloquianti, infatti, si trovano vari router - non necessariamente uguali - con code di lunghezza diversa e prestazioni differenti; • se siamo in congestion avoidance l’andamento della finestra è approssimativamente lineare e le cose vanno 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 altri calcolatori; • 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à di tempo. Il goodput, invece, è la quantità di informazioni trasmesse con successo nell’unità di tempo (senza contare 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 che in RTT venga trasmessa un’intera finestra e che, al termine di tale periodo, giungano tutte le conferme di 31

CAPITOLO 3. MODELLI ANALITICI PER LE PRESTAZIONI DEL TCP

32

ricezione1 . Fatte queste ipotesi il throughput è semplicemente il numero di segmenti trasmessi per RTT: S(t) =

W (t) · MSS w(t) = RTT RTT

Di seguito supporremo che il trasmettitore abbia infiniti dati da trasmettere (e che spedisca sempre segmenti di dimensioni pari a MSS), che i buffer di trasmissione e ricezione non limitino il comportamento del TCP (lo stato delle code nei router rimane approssimativamente costante e non si modifica in modo significativo 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 inoltre che, 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 avoidance fa sì che, al termine di essa, si riceva l’ACK che fa scattare W = W + 1. Se non si riceve l’ACK, invece, la finestra 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). Se assumiamo che la perdita avvenga periodicamente allora possiamo dire che, se ad esempio la perdita è di 1 A 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=

1 p

Possiamo però dare un’espressione di N anche in funzione della finestra2 :    W W W −1 −1 2 W W2 W2 W2 3W 2 2 2 N= ∑ ≈ +i = + + = 2 4 2 4 8 8 i =0 {z } | serie del ’piccolo Gauss’

Per capire a fondo questa espressione si tenga presente che la sommatoria ha quegli estremi visto che la finestra, 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 ottiene facilmente: s 8 W= 3p Il throughput si calcola come rapporto fra: • numero di pacchetti trasmessi = 1/p; • tempo totale di trasmissione =

W RTT. 2

Ed è quindi pari a: s    r 1 p 2 p 1 2 p 3p 3 1 S ( p) = = = = W RTT W RTT 8 RTT 2p RTT 2

3.3.1

ACK ritardati

Facciamo ora l’ipotesi aggiuntiva che il ricevitore spedisca un ACK ogni b segmenti e non ogni segmento. In tal caso, se trasmettiamo una finestra W riceveremo non più W ACK, ma W/b ACK: questo farà 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=

Wb RTT 2

Si noti che questo tempo è b volte quello esaminato nel caso di ACK non ritardati. Possiamo quindi fare calcoli analoghi a quelli già visti nel paragrafo 3.3: il parametro N (segmenti spediti all’interno del dente di sega) è pari a    bW bW W −1 − 1 2 W i bW 2 bW 2 bW 2 3bW 2 2 2 N= ∑ + = + ≈ + = 2 b 4 2 4 8 8 i =0 | {z } Ancora il piccolo Gauss

Quindi, uguagliando nuovamente questa relazione con N= 2 Con

1 p

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

∑k=

i =0

k ( k + 1) 2

CAPITOLO 3. MODELLI ANALITICI PER LE PRESTAZIONI DEL TCP

34 si ha:

s W=

8 3bp

E quindi il throughput sarà: s    r 1 p 2 p 1 2 p 3pb 3 1 S ( p) = = = = W RTT bW b · RTT 8 RTT 2pb RTT b 2

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 aggiungendo quella che siano aleatorie, allora già le cose si fanno più complicate! Supponiamo che la trasmissione avvenga ancora a batch (uno per RTT e di dimensioni pari alla finestra W) e che gli ACK siano ritardati (uno ogni b pacchetti). Sia inoltre la probabilità di perdita indipendente da segmento a segmento e da batch a batch. In questo caso, com’è prevedibile, l’andamento a dente di sega non sussiste più (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 fast recovery); • 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 controllo della 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 in cui non vi sono stati errori3 : anche quest’ultimo lasso di tempo è una variabile aleatoria che indicheremo con Ai e che, chiaramente, sarà pari al numero di RTT che intercorrono tra l’inizio del ’dente’ del grafico e l’istante in cui si verifica la perdita (vedi figura 3.4). Sia poi αi il numero del pacchetto4 che provoca la perdita e p la probabilità che avvenga una perdita; infine, sia Wi il valore della finestra nel momento in cui è avvenuta la perdita e β i la metà di Wi 5 . Si noti che le variabili Yi , Ai , Wi αi e β i sono tutte aleatorie e tutte riferite all’analisi del dente di sega i. La variabile aleatoria Yi (numero dell’ultimo pacchetto spedito nella tornata6 i) sarà chiaramente pari a Yi = αi + Wi − 1 3 Cioè

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

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’è avvenuto l’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 precedenti siano 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 ci riporta alla memoria il caso periodico, v. par. 3.3): E[α] = 1/p Sostituendo otteniamo quindi: E[Yi ] = E[αi ] + E[Wi ] − 1 =

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

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

Ai =

∑

RTT

j =1

Se supponiamo che RTT sia costante (rete abbastanza stabile), il suo valor medio è legato a quello di Xi dalla formula: E[ A] = ( E[ X ] + 1) · RTT Ora ci serve un legame fra Y (numero di pacchetti correttamente spediti), X (numero di RTT effettuati in un dente di sega) e W (valore della finestra prima del suo crollo): per trovarlo attingiamo dal paragrafo 3.3.1, visto che - per ipotesi - spediamo b finestre7 prima di ricevere un ACK in grado di incrementare la nostra W (t) di 1. Intuitivamente, infatti, il massimo valore raggiunto dalla finestra nella tornata i sarà pari al numero di RTT totali diviso per b (X/b è quindi il numero intero che indica di quanto è aumentata la finestra, ovvero il numero degli ACK che sono riusciti ad incrementare la finestra8 ) sommato al valore di partenza (che coincide con il valore finale della tornata i − 1, dimezzato): Wi = 7 O, 8 O,

Wi−1 X + i 2 b

→

Xi W = Wi − i−1 b 2

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

CAPITOLO 3. MODELLI ANALITICI PER LE PRESTAZIONI DEL TCP

36

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 b finestre, abbiamo detto, incrementiamo W (t) di 1; questo significa che, ad ogni incremento, avremo spedito un numero di segmenti pari al numero di RTT necessari a far incrementare la finestra (= b) moltiplicato W per il valore che la finestra ha avuto per gli ultimi b RTT, ovvero i−1 + k, dove k è un contatore che ci 2 dice quanti incrementi di finestra sono avvenuti fin’ora. Se ora mettiamo il tutto in sommatoria e facciamo X andare k da 0 fino a i − 1 (il −1 serve a ignorare l’ultimo RTT, all’interno del quale sono stati inviati solo b β i pacchetti, che sommiamo separatamente) otteniamo:

Yi =

Xi −1  b W

∑

i −1

2

j =0



+ k + βi =

Xi Wi−1 b |b {z2 }

Xi −1 b

+b

∑

k + βi =

j =0

portiamo fuori da sommat.



Xi b Xi b = Wi−1 + b b 2 |





Xi     −1 Xi b Xi Xi Xi b + βi = Wi−1 + − 1 + βi = Wi−1 + − 1 + βi 2 b 2 b 2 b {z }

Piccolo Gauss!

Xi , otteniamo l’espressione finale di Yi : b       Xi Xi b Xi Wi−1 Yi = Wi−1 + − 1 + βi = −1 Wi + − 1 + βi 2 b b 2 2

Ricordando ora l’espressione che avevamo per

Giunti fin qui siamo ben felici dei nostri risultati: mostriamo però che, in termini medi, tutto va come nel caso di modello periodico9 (par. 3.3). Applichiamo l’operatore di valor medio all’espressione della Yi per ottenere:   E [ Xi ] E[Wi−1 ] E[Yi ] = E[Wi ] + − 1 + E[ β i ] 2 2 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 ] 2

9 Avevamo 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

e E [Y ] = E [W ] +

1− p p

otteniamo (eliminando tutti i pedici che sono inutili in questa trattazione ’media’):   E[ X ] E [W ] E [Y ] = E [W ] + − 1 + E[ β] 2 2   1− p E[ X ] E [W ] E [W ] E [W ] + = E [W ] + −1 + p 2 2 2 1− p E [ X ] E [W ] E [ X ] E [W ] E[ X ] E [W ] E [W ] + = + − + p 2 4 2 2 E [ X ] E [W ] E[ X ] 1 − p E [W ] =3 − − 2 4 2 p Ora sostituiamo tenendo conto che10 E [W ] =

2E [ X ] b

⇒

E [X] =

b E [W ] 2

Ci tocca fare qualche calcoletto: E [W ] E [ X ] E [W ] E[ X ] 1 − p =3 − − 2 4 2 p     b b E [W ] E [W ] E [W ] E [W ] 1− p 2 2 =3 − − 2 4 2 p   3b 2 b+2 1− p E [W ] + − E [W ] − =0 8 4 p   b+2 4 (1 − p ) 1 2 E [W ] + − E [W ] − =0 2 3b 3pb s s   1 4 (1 − p ) b+2 b+2 2 b+2 b + 2 2 8 (1 − p ) +4· + E [W ] = + = + 3b 3b 2 3pb 3b 3b 3pb Se supponiamo che p << 1 (cosa largamente auspicabile) allora 1 − p → 1 e s E [W ] ≈

1 p

>> 1, quindi riotteniamo:

8 3bp

Anche se consideriamo il throughput, mediamente le cose tornano ad andare come nel caso periodico: infatti E [Y ] E [Y ] S( p) = = E[ A] ( E[ X ] + 1) · RTT Ricordiamo però che: b b+2 + E [ X ] = E [W ] = 2 6

s

b+2 6

2

+

8b (1 − p) 3p

10 Cioè il valor medio della finestra W, alla fine del dente di sega, è pari al prodotto fra il numero di RTT all’interno del dente fratto 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 X + i 2 b

Che diventa quindi: E [W ] E[ X ] + 2 b E[ X ] E [W ] = 2 b

E [W ] =

CAPITOLO 3. MODELLI ANALITICI PER LE PRESTAZIONI DEL TCP

38 E che

E [Y ] =

1− p + E [W ] p

Quindi, sostituendo e approssimando: s  b + 2 2 8 (1 − p ) 1 − p b + 2 1− p s + + + + E [W ] p 3b 3b 3bp p << 1 1 3 p  −−−−→  S ( p) = = s 2 RTT ( E[ X ] + 1) RTT 2bp b+2 b+2 8b (1 − p) + + 1 RTT  + 6 6 3p

3.4.2

Modello TD+TO

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

Figura 3.6:

Modello TD+TO

In questo caso il throughput è pari a: 1

S ( p) ≈

r RTT

3.4.3

2bp + T0 min 1, 3 3

r

3bp 8

!

Modello TD+TO+AW

Figura 3.7:

Modello TD+TO+AW

p (1 + 32p2 )

3.5. MODELLI A CONFRONTO

39

Se consideriamo anche l’eventualità che AW possa limitare W (v. figura 3.7) allora il throughput diventa pari a:     Wmax S ( p) ≈ min   RTT , 

1 r RTT

2bp + T0 min 1, 3 3

r

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 Wmax dei denti di sega, creando delle aree rettangolari (approssimabili da ). RTT Quanto detto è maggiormente comprensibile visionando la figura 3.8.

Figura 3.8:

3.5

L’approssimazione introdotta dalla formula di AW

Modelli a confronto

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

40

CAPITOLO 3. MODELLI ANALITICI PER LE PRESTAZIONI DEL TCP

Figura 3.9:

Figura 3.10:

Modelli a confronto

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

CAPITOLO 3. MODELLI ANALITICI PER LE PRESTAZIONI DEL TCP

42

3.6

Latenza

Si definisce latenza L il tempo che intercorre fra l’istante ti in cui il client inizia una connessione TCP e l’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 trasmissione trascurabili. 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 per iniziare la connessione TCP (protocollo TWH Three Way Handshake): trascorso un RTT viene infatti inviata la richiesta dell’oggetto e, dopo un ulteriore RTT, il client comincia a ricevere i dati richiesti. Instaurato il trasferimento dei dati, essi vengono ricevuti per un periodo pari a P/C. I passi definiti fin’ora sono obbligatori e imprescindibili (v. figura 3.13), quindi il limite inferiore (lower bound) per la latenza risulta essere: P Lmin = 2RTT + C In generale L > Lmin a causa delle perdite e delle non idealità della rete.

3.6. LATENZA

3.6.1

43

Finestra a dimensione fissa

Facciamo ora l’ipotesi che la finestra abbia dimensione fissa pari a W. Quando il server riceve la richiesta del client parte spedendogli W segmenti. Successivamente invia un segmento per ogni riscontro ricevuto; occorre però considerare due casi: W · MSS MSS ≥ RTT + → il server riceve il primo riscontro prima di aver terminato la trasmissione C C W · MSS è infatti il tempo necessario a spedire un’intera finestra di dimensione W, della finestra: C MSS mentre RTT + è il tempo che ci mette un segmento ad partire e a tornare (sotto forma di C conferma);

•

W · MSS MSS < RTT + → il server termina la trasmissione della finestra prima di aver ricevuto il C C riscontro.

•

Caso

W · MSS MSS ≥ RTT + C C

Instaurata la connessione i segmenti continuano ad essere trasmessi a velocità C fino a che l’oggetto non è stato completamente inviato. In questo caso la latenza è uguale a quella minima: L1 = Lmin = 2RTT +

Figura 3.14:

P C

Esempio con W = 6

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

W · MSS MSS < RTT + C C

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

P W · MSS

Il server è in attesa nell’intervallo tra la trasmissione di due finestre consecutive e quindi per K − 1 volte. Facciamo il calcolo della latenza: P L2 = 2RTT + + (K − 1) TA C P 2RTT + è il tempo che avremmo speso anche nell’altro caso; TA è il tempo ’perso’ per ogni segmento e C K − 1 è il numero di segmenti per cui si perde tempo. 11 Il

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

CAPITOLO 3. MODELLI ANALITICI PER LE PRESTAZIONI DEL TCP

44

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 capire come ottenerla12 ):   W · MSS MSS + RTT + L2 = 2RTT + (K − 1) C C Di questi termini: • il 2 · RTT è dovuto al three-way handshake;   MSS MSS • il (K − 1) + RTT è il termine legato alla trasmissione di ogni finestra ( per poter C C spedire il primo segmento della serie + RTT per avere la sua conferma che farà cominciare una nuova serie di trasmissioni); •

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

Sviluppando il tutto si ha: W · MSS W · MSS W · MSS L2 = 2RTT + (K − 1) + RTT + − C C C   P (W − 1) · MSS = 2RTT + + (K − 1) RTT − C C 



+

W · MSS C

Uguagliando questa espressione con quella analoga scritta poco sopra otteniamo anche l’espressione di TA : (W − 1) · MSS TA = RTT − C Il tempo perso è quindi l’RTT meno il tempo utilizzato per spedire i dati (com’è ovvio aspettarsi). Si ricorda che siamo nel caso di finestra costante (il W ’a regime’ è fisso e noto a priori) e si nota che la latenza cresce: • se K aumenta (molte trasmissioni dovute a una grande quantità di dati o a una finestra troppo piccola); • RTT grande rispetto a MSS/C (molto tempo perso in giro per la rete). 12 L’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) · MSS → RTT (idem come sopra). C

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 riscontro si ha W = W + 1 e quindi la finestra raddoppia ad ogni RTT (v. figura 3.16. Sia quindi k la variabile che conta 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 avremmo invece 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 non c’è bisogno di considerare il tempo perso a causa del fatto che la finestra è più grande del prodotto banda-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 attendere prima di avere la conferma ed allargare la finestra: W < S/C + RTT. In questo caso, come abbiamo detto 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 la meglio. L’RTT corrente è quindi il k-simo o uno successivo. 13 Che

è valida solo se lavoriamo unicamente in SS!! 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). 14 E

CAPITOLO 3. MODELLI ANALITICI PER LE PRESTAZIONI DEL TCP

46

Siano P i bit totali da spedire, P0 i bit spediti durante la prima fase (non ottimale) e P00 = P − P0 i bit spediti nella seconda (ottimale). Se il ciclo k è quello in cui termina la prima fase allora durante quest’ultima avremo trasmesso, se W partiva da 1, k

∑ 2i−1 · MSS

k

∑ 2i − 1

[bit]

i =1

[segmenti]

i =1

oppure k

∑ 2i · MSS

k

∑ 2i

[bit]

i =1

[segmenti]

i =1

se W partiva da 2. Di lì in poi siamo nella seconda fase e quindi nel caso ottimo della prima fase e della seconda otteniamo15 :   MSS L3 = 2RTT + k + RTT + C | {z }

= 2RTT + k

MSS + RTT C

P00 C |{z}

=

seconda fase

prima fase



per la latenza. Sommando i contributi



+

P00

P0 P0 + − = |C {z C} C P/C

k

P = 2RTT + + k C



MSS + RTT C

∑ 2i−1 · MSS



−

i =1

Se W iniziava da 1

C k

L3 = . . . = 2RTT +

P +k C



MSS + RTT C

∑ 2i · MSS



−

i =1

C

Se W iniziava da 2

In ogni caso, lo schema concettuale è sempre lo stesso:   P{Dopo i cicli ottimali} MSS L3 = 2RTT + + RTT · N{Cicli ’non ottimali’} + · N{Cicli ’ottimali’} C C Tutto quello che abbiamo detto fin’ora vale fintanto che si suppone di stare sempre in SS fino al fantomatico ciclo in cui la finestra raggiunge (e supera) il valore ottimo per la latenza (pari al prodotto banda-ritardo B · RTT). E se nel frattempo andiamo in CA? In realtà non cambia un granché: bisogna solo avere l’accortezza di capire il numero di cicli (cioè di RTT) in cui la finestra è ancora troppo piccola per essere ottima. Per esempio, se il prodotto banda-ritardo ci suggerisce che la finestra ottima è 32 e la SSTHR è pari a 16 si hanno: • i soliti 2RTT per il TWH; MSS • 4 cicli in cui siamo in SS (la finestra è, nell’ordine: 1 → RTT + MSS C → 2 → RTT + C → 4 → MSS RTT + MSS C → 8 → RTT + C → 16). In questo caso, quindi, il parametro k è pari a 5;

• 32 − 16 cicli di congestion avoidance; • un tempo pari a

P0 C

eventuali altri P0 bit da trasmettere.     MSS MSS P L = 2RTT + 4 · + RTT + 16 · + RTT + C C C

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

questi calcoli può tornare utile la seguente relazione: k −1

∑ 2i = 2 k − 2

i =1

3.7. IN SINTESI

3.7

47

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 graco 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 graco di W (t) per una connessione 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.

Periodico Periodico (ACK rit.) Aleatorio TD Aleatorio TD+TO

Aleatorio TD+TO+AW

Throughput s S 1 3 RTT 2p s 1 3 RTT 2bp mediamente come il periodico (m.d.) 1  q q  2bp 3bp RTT p (1 + 32p2 ) 3 + T0 min 1, 3 8   Wmax ,S min RTT TD+TO Tabella 3.1:

dim. s max di W

T fra perdite

8 3p

W RTT 2

8 3bp m.d.

Wb RTT 2 m.d.

s

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 P trascurabile, la latenza minima (quella imprescindibile) è Lmin = 2RTT + . C Per W sia ssa che mobile, dobbiamo tenere in conto due casi: • W

MSS MSS ≥ RTT + ⇒ W ≥ prodotto banda-ritardo ⇒ il server riceve il primo riscontro prima di aver C C

trasmesso tutta la nestra (caso 'buono');

CAPITOLO 3. MODELLI ANALITICI PER LE PRESTAZIONI DEL TCP

48 • W

MSS MSS < RTT + ⇒ W < prodotto banda-ritardo ⇒ il server termina la trasmissione della nestra C C

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

Dopodiché bisogna trovare il modo di scrivere la latenza nel seguente modo:  L3 = 2RTT +

MSS + RTT C



· N{Cicli 'non ottimali'} +

P{Dopo i cicli ottimali} · N{Cicli 'ottimali'} C

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 certo destinatario: il cardine del meccanismo che rende questo possibile risiede all’interno dei cosiddetti nodi di commutazione (i router, tanto per intenderci), i quali devono possedere tante interfacce di ingresso/uscita quanti sono i collegamenti afferenti/uscenti. La commutazione consiste nello scegliere l’interfaccia giusta verso 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’interno del terminale che vuole inviare i dati: sapendo di voler raggiungere la destinazione X, colui che deve spedire 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 reti grandi) in quanto esistono dei nodi intermedi (nodi di commutazione) che si occupano di smistare i messaggi verso la giusta destinazione, reperendo le risorse necessarie a realizzare il trasferimento dell’informazione fra sorgente e destinazione. La commutazione si è quindi in questo caso spostata dal mittente ai nodi intermedi. Esistono due tipi principali di commutazione: • commutazione di circuito: la rete crea un canale di comunicazione esclusivo fra due terminali colloquianti. In questo caso la trasmissione è assolutamente trasparente dal punto di vista temporale in quanto, una volta effettuate le operazioni per l’instaurazione del collegamento, la trasmissione disporrà 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 per operazioni di controllo (servono a malapena quelle per instaurare il circuito e rilasciarlo), ma non permette di modificare la banda del collegamento, né di sfruttarlo meglio in caso di lunghi silenzi fra i due colloquianti; • commutazione di pacchetto: è una commutazione di tipo numerico (digitale) che si basa sullo smistamento di pacchetti di dimensione fissa e predefinita. I messaggi o i pacchetti vengono trasmessi da un nodo di commutazione all’altro utilizzando in tempi diversi risorse comuni (pacchetti appartenenti a diverse ’conversazioni’ possono essere trasmessi attraverso la stessa interfaccia); le due tecniche 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 a priori quale sia il percorso che i pacchetti devono prendere; – invio di datagrammi (connection-less): ogni pacchetto viene gestito e instradato in modo indipendente, senza relazione con pacchetti precedenti o successivi, anche appartenenti alla stessa connessione. I vari pacchetti, quindi, potrebbero scegliere di volta in volta un percorso diverso per 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 memoriz49

CAPITOLO 4. INTRADAMENTO E FORWARDING IP

50

zazione e di effettuare il controllo degli errori all’interno dei nodi. Per contro, non riusciamo a garantire 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 il messaggio; • inserire il pacchetto nell’opportuna coda d’uscita (forward). Questi compiti appartengono chiaramente allo strato di rete (piano utente) e le modalità con cui vengono eseguiti 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 costruire le tabelle di instradamento (routing). La funzione di routing si avvale di algoritmi di routing, usati per il calcolo delle tabelle di instradamento note le informazioni sulla topologia della rete, e di protocolli di routing, 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 e ben noti a priori. Inoltre, i router devono comportarsi come veri e propri calcolatori specializzati e contenere al loro interno delle strutture dati idonee (cioè veloci e ottimizzate) entro le quali memorizzare le tabelle.

4.2

Indirizzi IP

Gli indirizzi IP sono stringhe lunghe 32 bit convenzionalmente scritte come sequenze di 4 numeri decimali, 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 di network differenziate per dimensione2 (v. fig. 4.2 e tabella sottostante): Classe A Classe B Classe C

7 bit net-ID → 27 reti 14 bit net-ID → 214 reti 21 bit net-ID → 221 reti

Figura 4.2:

24 bit host-ID → 224 − 2 host 16 bit host-ID → 216 − 2 host 8 bit host-ID → 28 − 2 host

Le classi di reti

Grazie al CIDR (Classless InterDomain Routing) si è però abbandonata questa rigida suddivisione nelle 3 classi, permettendo il settaggio di una dimensione qualunque per il Net-ID la cui lunghezza in bit, a partire 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 255.255.000.000 (notazione alternativa /16)->Net-ID: primi 16 bit da SX dell'indirizzo IP 255.255.255.000 (notazione alternativa /24)->Net-ID: primi 24 bit da SX dell'indirizzo IP etc... Obiettivo del CIDR era quello di allocare reti IP di dimensioni variabili, accorpando preferibilmente le informazioni di routing per più reti contigue (cosa che avrebbe semplificato notevolmente le tabelle di routing) e ponendo, allo stesso tempo, rimedio alla limitatezza di classi A e B. Accorpare più reti in una sola o scindere una rete grande in tante più piccole sono due operazioni duali che passano sotto il nome di: • subnetting: scindere di una rete grande in più reti, contenenti ciascuna meno host di quella di partenza (’alzando’ la netmask, v. fig. 4.3); • supernetting: accorpare più reti continue in un’unica rete (’abbassando’ la netmask, v. fig. 4.3). 1 Internet 2 In

Assigned Numbers Authority 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

CAPITOLO 4. INTRADAMENTO E FORWARDING IP

52

Figura 4.3:

4.2.1

Subnetting e Supernetting

Instradamento e table look-up

Si dice: • consegna diretta : IP sorgente e destinatario fanno parte della stessa rete. In tal caso l’host sorgente spedisce il datagramma direttamente al destinatario; • consegna indiretta : IP sorgente e destinatario non fanno parte della stessa rete e c’è quindi bisogno di 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’ ci stiamo 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 riga della tabella: si esegue un’operazione AND bit-a-bit tra l’indirizzo di destinazione del datagramma e la netmask 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, adabile, 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 pressata: 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 indirizzamento necessarie a raggiungere la destinazione nale, è gestito e instradato in maniera indipendente.

4.3. IN SINTESI

53

PRO: ecienza nell'uso del collegamento maggiore, uso scalabile della rete (con possibilità di memorizzazione 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 topologia 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 eettuata 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 eettuare 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 predenito per arrivare a quell'indirizzo, la relativa interfaccia di rete e, inne, la metrica. In base alla tabella di routing e all'operazione di table-look-up con longest prex 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 eettuare il forwarding.

3 In

questo senso i router sono calcolatori specializzati.

54

CAPITOLO 4. INTRADAMENTO E FORWARDING IP

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 piccole imprese. Dispongono di un elevato numero di porte a bit-rate medio-bassa (50 kbps - 10 Mbps) e supportano una grande varietà di protocolli e tecnologie di accesso (PPP, ADSL, FTTH, . . . ). Costano relativamente poco; • enterprise router: utilizzati per interconnettere le infrastrutture di rete di imprese medio-grandi o di grossi enti (università). Hanno un limitato numero di porte ad alta bit-rate (10 Mbps - 1 Gbps) e un costo medio; • backbone router: utilizzati per interconnettere reti su scala regionale/globale. Dispongono di poche porte ad elevatissima bit-rate (1 Gbps - 10 Gbps); costano molto ma hanno un’alta affidabilità ed efficienza.

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 strato 2 (data link) e lo strato 4 (trasporto): fra i suoi compiti vi sono quelli di effettuare la frammentazione o il riassemblaggio 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 il calcolo 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 fatte sempre 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’esigenza di 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 bit dell’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 iterazioni da effettuare è sempre pari alla profondità dell’albero; 55

CAPITOLO 5. ARCHITETTURE DEI ROUTER IP

56

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 da scorrere 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 (caso peggiore) è pari al più alla profondità dell’albero; se invece siamo più fortunati risparmiamo del tempo rispetto al caso del tree (v. fig. 5.2).

Figura 5.2:

5.4

Patricia Trie

Architettura dei router

I router di prima generazione erano delle workstation con struttura a bus (v. fig. 5.3): questa scelta topologica, tuttavia, non rendeva tali dispositivi molto efficienti in quanto il bus si configurava come un elemento di contesa e quindi come un ’collo di bottiglia’ per le prestazioni. I passi per il processamento dei 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 nel frattempo 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 N 2 punti d’incrocio, non bloccante, in grado di effettuare più trasferimenti in parallelo. La velocità di commutazione è quindi limitata 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 N 2 .

5.4.2

Rete di Clos

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

CAPITOLO 5. ARCHITETTURE DEI ROUTER IP

58

Figura 5.5:

5.5

Rete di Clos

Posizionamento delle memorie

Nelle reti a commutazione di pacchetto in ogni nodo tipicamente si memorizzano i pacchetti prima di trasmetterli in uscita (store and forward). Essi vengono posti nelle memorie delle interfacce di ingresso durante l’elaborazione dell’intestazione e il look-up e quindi nelle memorie nelle interfacce di uscita prima della trasmissione. L’utilizzo di matrici di commutazione (anche se non bloccanti) per trasferire pacchetti necessita 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 pari alla 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 qualsiasi fila, infatti, devono attendere che sia processato il primo della fila prima di poter essere a loro volta commutati. 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 N 2 . Con questa scelta abbiamo il massimo throughput, evitiamo il blocco HOL ma necessitiamo di una quantità esorbitante di code, cosa che complica di molto lo scheduler; • 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 caso disponiamo del throughput massimo, evitiamo il blocco HOL e non necessitiamo di un numero esagerato di code (in quanto c’è un’unica memoria); inoltre, perché si verifichi la perdita di pacchetto si deve riempire tutta la memoria, eventualità relativamente difficile da realizzare. Il rovescio della 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 Enterprise Router Backbone Router

basso medio elevato

0,05 - 10 10 - 1000 1000+

elevato limitato scarso

I router si occupano di routing (protocolli + algoritmi di instradamento) e di forwarding (processamento dell'intestazione IP, table look-up, header update). Per eettuare 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 congurazione Unix-like). 1 Questo

sì che è kitsch!

CAPITOLO 5. ARCHITETTURE DEI ROUTER IP

60

Grande importanza riveste il table look-up eettuato per l'instradamento tramite longest prex match: anché esso sia ecace 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 semplicata e 'sfogliata' del tree all'interno della quale vengono riporti soltanto i pressi 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 eettuare più trasferimenti in parallelo; la matrice di commutazione può essere crossbar (matrice N × N , complessità N 2 ) 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 3 ( N 2 vs. N 2 ). Un altro elemento in grado di inuire sulle prestazioni è il posizionamento delle memorie adiacenti alla matrice di commutazione (v. tabella) Pos. memorie Uscita Ingresso Virtuale in uscita A memoria comune

Pro

Contro

Non serve lo speed-up No speed-up e blocco HOL No speed-up e blocco HOL, unica memoria

Necessario speed-up con fattore N Blocco HOL (limitato throughput) N 2 code, scheduler complesso 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), risulta comodo utilizzare la teoria dei grafi per effettuarne la rappresentazione e lo studio: indicheremo con V un insieme finito di nodi, con il termine arco il collegamento di fra i nodi (i, j) ∈ V, con E un insieme di archi. Un grafo si costruisce mettendo insieme i nodi e gli archi quindi, in definitiva, può essere caratterizzato dalla coppia (V, E): sarà orientato se anche gli archi lo sono, non orientato viceversa. Due nodi connessi da un arco verranno poi detti adiacenti. Da un grafo di V nodi e E archi possiamo trarre un sottografo fatto da V 0 ⊆ V nodi e E0 ⊆ 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 potrebbe essere differente in base all’orientazione, mentre in un grafo non orientato la distanza è univoca dati i nodi (i, j). Convenzionalmente, infine, diremo che la distanza fra due nodi non connessi da un arco è pari a +∞. 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 nodo v una sequenza di k + 1 nodi il primo dei quali è il nodo u e l’ultimo il nodo v. Se contiene tutti nodi distinti (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 contiene cicli è detto aciclico. Un grafo viene denominato connesso se esiste sempre un cammino fra due qualsiasi 61

CAPITOLO 6. ALGORITMI DI ROUTING

62

suoi nodi, completamente connesso se due nodi qualsiasi possono essere collegati da un solo arco1 (e quindi sono 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 grado di 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 eliminando opportuni archi da un grafo connesso, qualsiasi esso sia. Dato un grafo pesato connesso e non orientato G, un minimum spanning tree (albero di ricoprimento minimo) di G è uno spanning tree G 0 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:

1 In

Alcuni esempi di minimum spanning tree

questo caso il numero di archi del grafo è |V |

|V | − 1 2

6.2. ALGORITMI PER IL CALCOLO DEL MINIMUM SPANNING TREE

6.2

63

Algoritmi per il calcolo del minimum spanning tree

Dato un grafo pesato connesso non orientato G = (V, E) esistono alcuni algoritmi di tipo greedy che man mano aggiungono un arco di E ad un sottografo A (il quale, durante i passi dell’algoritmo, è sottografo sia di G che di un MST di G) fino al ricoprimento di tutti i nodi. Alla fine di tali algoritmi saranno stati esclusi i rami di G aventi peso maggiore (o al limite uguale) a quelli inclusi nell’MST (completo) A che è 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 non connesso (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 collegato tutti 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’algoritmo 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 due nodi è la somma dei pesi degli archi che lo costituiscono. Uno shortest path (cammino minimo) dal nodo u al nodo v è un cammino (u, v) il cui peso è minimo fra tutti i possibili cammini (v. fig. 6.4: si noti che possono 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 aver sicuramente 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 abbiamo uno shortest path p tra il nodo di indice 0 e quello di indice k (supponiamo di averli numerati in ordine

CAPITOLO 6. ALGORITMI DI ROUTING

64

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 algoritmi per trovare uno SP da s verso ogni altro nodo di V (single-source shortest path problem). Tali algoritmi permettono inoltre di trovare la distanza d(v) di un generico nodo v (appartenente allo SP) da s nonché il predecessore π (v) del nodo v lungo lo SP3 . Inizialmente (initialization) ogni nodo viene posto a distanza pari 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 dei predecessori di ogni nodo verranno definiti esplicitamente. Il rilassamento di un arco (u, v) ∈ E, con u e v nodi generici di V, consiste nel valutare se, utilizzando u come predecessore di v, si può migliorare il valore 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 del nodo u (tuo potenziale predecessore) sommata alla distanza tra u e te? Allora sbagli! Sappi che arrivando da u e imboccando l’arco che da u porta a te la distanza è inferiore a quella alla quale tu credi ora di essere. Quindi aggiorna la tua distanza con quella nuova, appena scoperta, e segnati che l’hai ottenuta a partire 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 sicuramente quelle di uno shortest path, ma non è escluso (anche se non è garantito) che la convergenza possa avvenire anche prima. Pseudocodice:

Per i da 1 a |V | − 1 Per ogni (u, v) appartenente a E rilassa(u, v) Principali svantaggi dell’algoritmo di Bellman-Ford (parleremo più diffusamente di questo aspetto dal paragrafo 6.6 in poi): 2 Se 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 nodo k sarebbe minimo (al suo interno esisterebbe una strada alternativa più breve tra i e j)! 3 Il predecessore è il nodo attraverso il quale siamo passati immediatamente prima di arrivare a v. 4 L’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. 5 Riportiamo, 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 archi possono essere negativi). L'algoritmo di Dijkstra risolve lo stesso problema in un tempo computazionalmente inferiore, ma richiede che i pesi degli archi siano non-negativi. Per questo, Bellman-Ford è usato di solito quando sul grafo sono presenti pesi degli archi negativi. Secondo Robert Sedgewick, 'I pesi negativi non sono solamente una curiosità matematica; [. . . ] si presentano in modo naturale quando riduciamo altri problemi a quelli di cammini minimi' [. . . ]. Se un grafo contiene un ciclo di peso totale negativo allora sono ottenibili pesi arbitrariamente piccoli e quindi non c'è soluzione; Bellman-Ford individua questo caso. L'algoritmo di Bellman-Ford è nella sua struttura base molto simile a quello di Dijkstra, ma invece di selezionare il nodo di peso minimo, tra quelli non ancora processati, con tecnica greedy, semplicemente processa tutti gli archi e lo fa |V | − 1 volte, dove |V | è il numero di vertici nel grafo. Le ripetizioni permettono alle distanze minime di propagarsi accuratamente attraverso il grafo poiché, in assenza di cicli negativi, il cammino minimo può solo visitare ciascun nodo al più una volta. Diversamente da quello con tecnica greedy, il quale dipende 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 nella composizione 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 impiegare un tempo infinito per aumentare gradatamente la stima della distanza per quel nodo a meno di non adoperare uno scalare come soglia, oltre il quale il nodo viene considerato non raggiungibile e quindi 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 S0 complementare ad S 7 avente distanza minima e rilassa tutti gli archi uscenti da tale nodo e diretti verso elementi di S0 , interrompendosi quando S = V e S0 = ∅.

Finché S0 6= ∅ trova u ∈ S0 tale che la distanza d(u) = min{d(v), v ∈ S0 } metti u in S togli u da S0 per ogni v ∈ S0 tale che (u, v) ∈ E rilassa(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 che includeremo nell’insieme S (pallini blu, v. fig. 6.6). A questo punto rilassiamo gli archi collegati a questo nodo, i quali logicamente finiranno sui nodi adiacenti: dei nodi adiacenti ora scegliamo quello a distanza minima, includiamolo in S e rilassiamo tutti gli archi ad esso collegati. Adesso parte la fase iterativa: si sceglie il nodo a distanza complessiva minore da quello di partenza, lo si include in S e poi si rilassano gli archi (e così via. . . ). Alla fine dell’algoritmo ogni nodo saprà a che distanza è da quello di partenza e, 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 orientato dove i nodi sono i commutatori (router, switch, etc. . . ), gli archi sono i collegamenti e la loro 7 Nel

primo passo S0 = V perché S = ∅.

CAPITOLO 6. ALGORITMI DI ROUTING

66

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 collegamenti 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 tutte le 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 che tutte le strade possibili sono percorse, il primo pacchetto che arriva a un nodo è anche quello che ha fatto la strada più breve possibile (shortest path). Questo algoritmo è molto adatto alle trasmissioni broadcast e richiede 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), allora potrebbero pervenire in uno stesso luogo numerosissime (e inutili) copie di uno stesso pacchetto, con la 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 ripetere tale 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 qualche aggiustamento: • si impedisce la ritrasmissione sul nodo dal quale è arrivato il messaggio (’me l’ha mandato lui, cosa glielo rispedisco a fare?!’); • ad ogni pacchetto viene associato un identificativo unico e ciascun nodo mantiene in memoria una lista 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 le interfacce;

6.5. APPLICAZIONE ALLE RETI

67

• si trasmette solo lungo lo spanning tree, cosicché i pacchetti non possono ciclare (cioè ’fare il giro’) e percorrere strade già battute da altri. Quanto detto sopra vale anche per l’interconnessione di più LAN, anche di tipo diverso, attuata al fine di estendere il dominio di broadcast: lo spanning tree può essere costruito sulla base delle differenti reti e diventa il canale preferenziale per evitare che vi sia un’eccessiva proliferazione di trame duplicate in giro per la rete (v. figura 6.7).

Figura 6.7:

6.5.2

Interconnessione di più LAN e spanning tree

Deflection routing

Questo tipo d’algoritmo (detto anche hot potato) è adatto alle reti in cui i nodi di commutazione dispongono di spazio di memorizzazione molto limitato e in cui si desidera minimizzare il tempo di permanenza dei pacchetti nei nodi. In base alla regola del deflection routing, infatti, quando un nodo riceve un pacchetto lo 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 porta alla destinazione corretta: i pacchetti potrebbero sparpagliarsi chissà dove e arrivare a destinazione in un ordine assolutamente casuale); • alcuni pacchetti potrebbero percorrere all’infinito un certo ciclo in seno alla rete, semplicemente perché 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 (mandiamo solamente nella coda più corta); si legge su di una tabella la linea d’uscita preferenziale verso la destinazione 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 di trasmissione più breve. Così facendo, in condizioni di basso carico della rete, l’instradamento non viene fatto senza criterio e bovinamente (come nel caso hot potato), ma sulla base dell’effettiva destinazione finale. 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 una coda molto lunga. 8 Una

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

CAPITOLO 6. ALGORITMI DI ROUTING

68

6.6

Shortest Path Routing

Tale filosofia di routing associa una lunghezza ad ogni collegamento della rete e l’algoritmo cerca la strada di lunghezza minima fra ogni mittente e ogni destinatario. A questo proposito vengono utilizzati gli algoritmi 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 aspetti patologici di questo tipo di algoritmi; supponiamo di avere due percorsi, uno di costo d1 e l’altro di costo d2 > d1 : l’algoritmo che scegliesse sempre e comunque il percorso di costo minimo intaserebbe la linea con parametro d1 e non invierebbe niente su quella di costo d2 . Per questo si cerca di fare un uso probabilistico della 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 rendiamo la distribuzione del traffico più uniforme sui vari link della rete ma anche questa volta, come nel deflection routing (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:

9 Proposta

da Ford-Fulkerson.

Esempio di calcolo delle tabelle di routing

6.6. SHORTEST PATH ROUTING

69

In figura 6.8 viene riportato un esempio10 di costruzione delle tabelle di routing; immaginiamo di essere il nodo 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 distance vector 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 modifiche e, 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 la riga facente riferimento al nodo E, ora raggiungibile attraverso C (distanza: 10 = 7 + 3). Le altre entry, invece, non vengono modificate perché B rimane un referente più comodo (dista 1 invece che 6!); 3. B riceve DV ( D ) = {( B, 1), (C, 3), ( D, 0), ( E, 2)}: concentriamoci per un attimo sulla tabella di routing di B (v. la solita figura). Anche B, come A non conosceva la strada per arrivare ad E: D gliela suggerisce, dicendogli che dista 2 da E, cosicché B si convince di distarvi 3 = 1 + 2 (al solito, un passo 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 la tabella di routing di B e quindi anche il suo distance vector, che ora contiene ( E, 3); quando A riceve questa nuova informazione, abbandona C come next-hop per arrivare a E e seleziona B, calcolando la 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 se non la distanza di questi ultimi da loro stessi (pari a 0, sai che roba. . . ). Da quel momento in poi lo scambio dei distance vector permette la creazione di tabelle sempre più complete e l’algoritmo converge al più dopo un numero di passi pari al numero di nodi della rete12 : se la rete è molto grande, di conseguenza, la convergenza sarà lunga, con il fastidioso effetto collaterale che - se nel frattempo cambia lo stato della rete - l’algoritmo potrebbe incepparsi e la convergenza non arrivare mai (v. convergenza lenta);

Figura 6.9:

10 Anche

Bouncing effect

questo tratto dalle slide del Prof. Callegati, ’Applicazione alle reti’, slide 11. 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 un tempo 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. 12 Come Bellman-Ford, v. par. 6.4.1. 11 A

CAPITOLO 6. ALGORITMI DI ROUTING

70

• bouncing effect: si faccia riferimento alla figura 6.9. Supponiamo che il link fra A e B assuma costo +∞ a causa della caduta del collegamento: in tal caso A e B si accorgono dell’anomalia e immediatamente 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 a C 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 raggiungere quest’ultimo solo tramite il collegamento di costo 6. Tra questi due punti, però, c’è un’incongruenza temporanea che vede C ed A mandarsi compulsivamente e senza soluzione di continuità pacchetti destinati a B. Il bouncing effect consiste quindi in momenti patologici in cui due o più nodi si scambiano datagrammi palesemente errati fino a che non 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 collegati a un terzo nodo, e uno di questi collegamenti si deteriora fortemente, potrebbe succedere che i due nodi 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 collegamento tra B e C vada fuori servizio: A dice ad B di distare 2 da C, così B si convince di poter andare a C passando 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 avanti all’infinito (appunto), ma per fortuna questo problema è facilmente risolvibile imponendo una soglia oltre 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 essere risolte: nessuno fra i metodi esposti nei paragrafi 6.7.1 e 6.7.2 è quindi davvero risolutivo.

Figura 6.12:

6.7.1

Situazione patologica e irrisolvibile

Split Horizon

Il concetto è molto semplice: se A instrada i pacchetti verso una certa destinazione X tramite B, non ha senso che quest’ultimo cerchi di raggiungere X tramite A e, di conseguenza, è inutile che A dica a B la sua 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 per lo 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 X uguale a +∞.

6.7.2

Triggered Update

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

6.8

Protocolli path vector

L’unica soluzione davvero risolutiva a tutti gli inconvenienti fin qui illustrati (v. par. 6.6.1) è quella di cambiare la filosofia di comunicazione delle distanze: in base ai protocolli path vector, ad esempio, il vettore che ogni router manda ai vicini contiene, oltre alle distanze dagli altri nodi, anche l’intero cammino che 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 una delle cause dei problemi dei protocolli distance vector). Il prezzo da pagare, com’è intuitivo, sta in nella maggiore mole di informazioni da scambiare.

CAPITOLO 6. ALGORITMI DI ROUTING

72

Protocolli link state

6.9

Grazie a tale tipo di protocolli ogni nodo si procura un’immagine della topologia della rete e, sulla base di tale immagine, calcola le tabelle di routing13 . Ogni router deve chiaramente scoprire chi sono i propri vicini e imparare i loro indirizzi: ciò viene fatto tramite l’invio di Hello Packet. La distanza dai vicini viene invece scoperta grazie ai pacchetti che questi spediscono di rimando (Echo Packet). Con le informazioni ricavate in tal modo è possibile, per ogni router, costruire una lista dei vicini corredata con le distanze da questi 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 minimi verso ogni altro router. Rispetto ai protocolli distance vector, quelli di tipo link state sono più complicati da implementare e richiedono un quantitativo superiore di memoria; per contro, tuttavia, offrono maggiori funzionalità in termini di gestione di rete, permettono una convergenza migliore (per velocità ed affidabilità) e si adattano meglio ai cambi di topologia (guasti, aggiunta di nuovi collegamenti, etc. . . ).

6.10

In sintesi

Un grafo è un'entità denita 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 • un

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

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.

13 Nel caso di reti di grandi dimensioni non è possibile gestire le tabelle di routing per l’intera rete in tutti i router: in questo caso il routing deve essere gerarchico. 14 Il 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 innita 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'insieme S0 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 S0 , poi rilassiamo gli archi a lui collegati e iteriamo il procedimento sopra descritto. Quando tutti i nodi saranno niti in S0 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'eettiva 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 eettuare 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 eect : 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 innity : A, B e C sono collegati (congurazione: 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.

74

CAPITOLO 6. ALGORITMI DI ROUTING

Alcuni possibili miglioramenti consistono nell'implementazione di triggered update (appena si modica la topologia vengono inviati i distance vector aggiornati) e di split horizon (se A va a C tramite B, A non 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 orono 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 solo su reti TCP/IP. Sfrutta la porta 520 (sia in ricezione che in trasmissione), si regge su UDP e utilizza due tipi 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 classi di 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 hanno notizie di una route (la si mette a costo +∞), e il garbage-collection timer, che elimina del tutto tale route dopo ulteriori 120 secondi. Un messaggio response con nuove informazioni di routing viene inviato periodicamente (ogni 30 secondi con uno scarto di ±5 secondi per evitare aggiornamenti a raffica), oppure come risposta ad una richiesta esplicita, o anche qualora cambiasse la topologia della rete (triggered update). Quando si riceve un response viene inizialmente controllata la correttezza dei dati presenti nel distance vector ricevuto (indirizzi IP e metriche validi) quindi si considerano solo le voci con distanze di non infinite, le quali vengono incrementate di una unità (le di sono le distanze del nostro vicino dagli altri nodi: siccome esso dista un hop 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 appena incrementata, 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 viene aggiornata 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, la entry viene aggiornata se diversa dal valore precedente. Si fa inoltre ripartire il contatore del periodo di 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 messaggi 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

CAPITOLO 7. IGP: INTERIOR GATEWAY PROTOCOLS

76

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 correttivi soffre comunque dei problemi illustrati all’inizio del paragrafo 6.7, e può presentare problemi di convergenza; inoltre non è sicuro, in quanto chiunque trasmetta datagrammi dalla porta UDP 520 viene considerato come un router autorizzato. Funziona infine maluccio con le reti grandi. Parte di queste questioni vengono risolte con il RIP versione 2, che permette l’indirizzamento CIDR e ha un sistema di autenticazione 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 in reti medio-grandi e grandi. Grazie a tale tipo di protocollo, infatti, riusciamo ad effettuare il cosiddetto routing gerarchico: esso consiste nel ripartire grandi porzioni di rete chiamate Autonomous Systems (AS) in sotto-ripartizioni, chiamate Routing Areas (RA), come mostrato in figura 7.2. I router all’interno di una RA (internal router) effettuano l’instradamento relativamente alla sola area, mentre per destinazioni al di fuori dell’area si limitano ad inviare i pacchetti a dei router ’di bordo’ (Area Border Router) che si occupano unicamente 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 protocollo EGP (v. cap. 8), e i Backbone Router, che si interfacciano con il backbone. Esaminando nuovamente la figura 7.2 si può notare la presenza di una Stub Area; essa è tipicamente un’area avente un solo punto di interconnessione con il resto della rete: l’instradamento verso l’esterno della stub area viene effettuato con la 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 reti esterne alla stub area non vengono propagate da OSPF internamente alle stesse. Questa è un’altra delle tecniche atte a ridurre le dimensioni della tabella di routing, col vantaggio che il router di bordo necessita di 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 certa destinazione, 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

Figura 7.2:

77

Schema concettuale del routing gerarchico

• autenticazione tramite uso di password e crittografia, per garantire maggiore sicurezza nello scambio delle 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 sulla base 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 da raggiungere: 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 diffuse informazioni relative alla irraggiungibilità di intere reti e non dei singoli host.

Figura 7.3:

Distinzione logica fra host e router

CAPITOLO 7. IGP: INTERIOR GATEWAY PROTOCOLS

78

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, in particolare, 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 tutti gli altri. Nella rete a maglia completa il numero di archi bidirezionali è pari a N ( N − 1) +N 2 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 archi bidirezionali 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 instradamento 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 cui ogni router è suo adiacente e lo scambio di informazioni di routing avviene solo fra lui e ogni router preso singolarmente; il DR è inoltre l’unico a comunicare la raggiungibilità di router e host della LAN al mondo esterno. Grazie a questi accorgimenti riusciamo a realizzare la situazione illustrata in figura 7.5. 2 Al

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

7.2. OSPF: OPEN SHORTEST PATH FIRST

Figura 7.6:

79

Router vicini e router adiacenti

Ogni router ha il suo ID univoco (router-ID) (di default si prende quello più alto fra quelli assegnati alle interfacce del router) nonché un valore di priorità, compreso fra 0 (default) e 255, utilizzato nell’elezione del 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, eleggendolo come 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 di Link State Database.

7.2.3

Messaggi dell’OSPF

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

diversi tipi di LSA:

• router-LSA: creati da ogni router e diffusi in una singola area, contengono le informazioni relative allo stato delle interfacce del 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 router connessi a quella rete; • summary-LSA: creati dagli Area Border Router e diffusi in una singola area, contengono informazioni di routing per destinazioni 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 di routing 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 destinazioni appartenenti ad altri AS (compresa la default route). 4 Il

campo protocol ha valore 89. dell’intestazione:

5 Campi

• Version indica la versione di OSPF (versione 2); • Type indica il tipo di pacchetto; • Packet Length numero di byte del pacchetto;

CAPITOLO 7. IGP: INTERIOR GATEWAY PROTOCOLS

80

• messaggio hello: serve a controllare l’operatività dei link, a eleggere il designated router, a scoprire e mantenere le relazioni coi vicini. Sono mandati periodicamente e contengono una lista di tutti i vicini dai quali è stato ricevuto un pacchetto hello di recente; • messaggi per l’exchange protocol: una volta stabilite le adiacenze, è necessario che i router sincronizzino i rispettivi Link State Database (dove, abbiamo detto, sono contenute le informazioni sulla topologia della rete). La procedura di sincronizzazione è asimmetrica in quanto, nella comunicazione fra due router, si stabilisce chi è il master e chi è lo slave: il primo invia messaggi al secondo, che risponde, 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 aggiornamento ’a tappeto’. Viene inoltre richiesta conferma di ricezione.

Figura 7.7:

7.3

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

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 classico di 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 sore delle patologie di tutti i protocolli distance vector, è insicuro (si appoggia su UDP senza crittograa 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 • semplicare 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 N−1 altri (servono N + N archi e bisogna trasmettere N ( N − 1) LSA). L'OSPF risolve questo problema 2

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 eettuata scegliendo quello avente priorità maggiore, mentre il 'secondo classicato' 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 crittograa;

• 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 dierenziano 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 diondere gli LSA a tutti i router della rete.

82

CAPITOLO 7. IGP: INTERIOR GATEWAY PROTOCOLS

Capitolo 8

EGP: Exterior Gateway Protocols Mentre i protocolli IGP si occupano del routing all’interno degli Autonomous Systems cercando di trovare il percorso ottimale, i protocolli di tipo EGP (Exterior Gateway Protocol) e BGP (Border Gateway Protocol) 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 distanza minima 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 pericolosamente la convergenza). Inoltre, non si adatta velocemente ai cambi di topologia, né implementa alcun meccanismo 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 sessioni BGP, 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 tutti gli AS da attraversare per raggiungere una particolare destinazione. Ciò risolve il problema dei percorsi ciclici (se un AS vede sé stesso nel path vector che riceve allora controlla che nel relativo percorso non vi siano loop) e inoltre permette una maggiore flessibilità nella definizione delle politiche di routing fra gli AS. 1 Alcuni AS non vogliono essere raggiunti da altri, oppure vogliono mantenere la loro indipendenza, oppure ci sono alcuni accordi internazionali da rispettare etc. . . 2 A dire il vero, non sono nemmeno specificate le regole per definire le distanze. . . 3 La ’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 tratta della forma per così dire embrionale dalla quale poi nel 1983 nascerà Internet. ARPAnet fu pensata per scopi militari statunitensi durante la Guerra Fredda, ma paradossalmente ne nascerà uno dei più grandi progetti civili: una rete globale che collegherà tutto il mondo.

83

CAPITOLO 8. EGP: EXTERIOR GATEWAY PROTOCOLS

84

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 le quali si vuole permettere il traffico (export policies) oppure si accettano solo le informazioni provenienti da AS ritenuti compatibili (import policies). Inoltre, l’approccio basato sul percorso invece che sulla distanza non richiede che tutti i router usino la stessa metrica: in quanto non vincolati a rispettare i criteri di minima distanza ci sono infatti permesse scelte arbitrarie. Il rovescio della medaglia sta nel fatto che in questo modo si consuma molta banda e memoria per le informazioni di routing (bisogna inviare interi percorsi).

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 151.16.0.0/16 -> 10010111.00010000 151.17.0.0/16 -> 10010111.00010001

Host-ID .00000000.00000000 .00000000.00000000

8.2. BPG: BORDER GATEWAY PROTOCOL

151.18.0.0/15 -> 10010111.0001001

85

0.00000000.00000000

le quali possono quindi essere raggruppate sotto l’unico IP+netmask

INDIRIZZO IP Net-ID 151.16.0.0/14 -> 10010111.000100

Host-ID 00.00000000.00000000

che viene inviato all’AS5 con l’indicazione di path ’AS3’ (per forza, c’è solo quello da attraversare!). Questo a sua volta invia tale informazione all’AS1, aggiungendo sé stesso nel percorso; tornati in AS5, viene rilevato il ciclo {AS5 - AS1 - AS5 - AS3} e si rimuove AS1 dall’AS-PATH. La diffusione dei path vector continua verso AS2, dove è presente un’altra rete (80.128.0.0/12) che viene annunciata a AS4, che a sua volta scambia le sue informazioni con AS2. Grazie a questo protocollo è possibile, ad esempio, che AS4 decida di non accettare/inviare pacchetti verso qualcuno degli altri AS e quindi, ad esempio, non accettare il 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 attributo può essere • well-known: riconoscibile da tutte le implementazioni BGP, deve essere inoltrato assieme al path vector (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’interno dell’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 il percorso; • next-hop: di tipo well-known, indica l’indirizzo IP del prossimo router da attraversare verso la destinazione specificata. I tipi di messaggio sono invece: • Open: è primo messaggio trasmesso quando viene attivata una connessione verso un router BGP vicino. Contiene le informazioni di identificazione/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; • 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.

CAPITOLO 8. EGP: EXTERIOR GATEWAY PROTOCOLS

86

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 vericare 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ù adabile) 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 denire 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 specicano 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 inne: • Open: contiene le informazioni di identicazione/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; • Notication: messaggio di notica 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 sua ideazione nasce dalla volontà di rendere possibile l’instradamento da parte di apparati non in grado di trattare datagrammi IP come fanno i router, che possono essere decisamente costosi al contrario dei molto più economici switch: mentre infatti i primi, oltre a instradare i datagrammi IP, supportano un gran numero di interfacce e protocolli ed effettuano anche operazioni addizionali come il packet filtering, il controllo della QoS1 , etc. . . gli switch fanno instradamento semplice in funzione di indirizzi statici e hanno un supporto per un numero limitato di interfacce e di protocolli. Ciò li rende molto più a buon mercato e questo ha fomentato l’ipotesi che si potesse migliorarli un poco per renderli dei ’quasi-router’ (con un ottimo compromesso funzionalità/costo): da qui l’idea di trovare un metodo alternativo al destination based routing per effettuare l’instradamento. Il label switching, tra l’altro, rende possibile il trasferimento di pacchetti IP su percorsi prestabiliti diversi da quelli selezionati dai normali protocolli per il routing IP, supporta bene le VPN (Virtual Private Network) e permette il mantenimento dei protocolli di routing IP standard (OSPF, BGP). Infine, uno dei grandi vantaggi dell’approccio MPLS consiste nell’aggregazione di più flussi di fati in un unico qualora entrambi 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 due componenti: • trasferimento (ereditata dagli switch) - si basa su hardware veloce e identificazione tramite etichettamento dei flussi informativi. Si adotta un modo di trasferimento con commutazione orientata alla connessione: la commutazione si basa infatti sul riconoscimento di un’etichetta (label) associata al datagramma. Tale etichetta è un’entità breve e di lunghezza predefinita che non codifica gli indirizzi di rete (scordiamoci quindi il meccanismo degli indirizzi con netmask!), bensì viene inserita tra l’intestazione dello strato di linea e quella dello strato di rete. La label viene utilizzata sia per il trasferimento (individua il destinatario) sia per la gestione delle risorse; • controllo (ereditata dai router) - si basa sui protocolli di rete convenzionali sui e meccanismi di associazione 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 destinazione e accomunati da medesimo instradamento, uniformi richieste di qualità di servizio e stesse politiche di routing. Può essere utile immaginare il flusso come un grande tubo, un’autostrada per i pacchetti che devono andare tutti quanti verso la stessa direzione; tali pacchetti vengono infatti associati2 a questo tubo (cioè ad una FEC, Forwarding Equivalence Class) in base a destinazione e classe di traffico: 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. 1 Quality 2 Il

of Service. processo di associazione si chiama binding.

87

CAPITOLO 9. MPLS: SOSTITUZIONE D’ETICHETTA

88

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 attribuire ai pacchetti entranti la giusta label e di togliere quest’ultima a quelli uscenti: per poter effettuare tale operazione, è necessario che i LER sino in grado di determinare la corretta FEC e l’opportuno next hop per ogni possibile messaggio entrante. Inoltre, onde evitare di calcolare la FEC ad ogni nodo attraversato, è opportuno che tutti i LSR del dominio MPLS instradino i pacchetti identificati dalla 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 che inserisce (push) la prima label a livello gerarchico m. Il livello gerarchico viene inserito in quanto i vari domini MPLS possono essere fra loro intersecati nonché disposti in maniera gerarchica: per ogni livello di gerarchia, quindi, è necessario inserire una label in grado di identificare il next-hop di quel particolare livello. Tutti i LSR intermedi commutano i pacchetti sulla base della label di livello3 m (con label swapping) e il Label-Swicthed Path termina con un LSR che prende una decisione d’instradamento sulla base di una label di livello gerarchico < m (oppure in modo convenzionale, in base alla particolare politica di routing scelta). Instradamento ’classico’ Algoritmo di forwarding

longest prefix match: si utilizza il binomio IPadress + netmask per individuare il path da seguire

Algoritmo di routing

nessuna differenza fra i due casi (instradamento classico e MPLS): i router LER devono tuttavia conoscere il protocollo IP per potersi interfacciare con l’esterno

3I

MPLS exact match: una label indica chiaramente un unico percorso, da prendere senza effettuare calcoli nessuna differenza fra i due casi: un dispositivo che usa MPLS (come un LSR) non deve padroneggiare il protocollo IP, ma deve saper instradare e fare label swapping

livelli gerarchici più ’alti’ (maggiore generalità e incapsulamento) sono quelli aventi m inferiore.

9.3. USO E TRATTAMENTO DELLE LABEL

9.3

89

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 datagramma emerge da una rete di trasporto MPLS il campo TTL dovrebbe avere un valore che tiene conto del numero di LSR attraversati. In questo modo, ritornati nel mondo IP, il pacchetto avrà il tempo di vita che gli spetta: se non esistesse un meccanismo per questa ’traduzione’ del TTL, un pacchetto congelerebbe la sua età dal momento esatto in cui entrasse in un’area MPLS. Per questo motivo TTL viene inserito nella label MPLS e inizialmente ha lo stesso valore del TTL di IP all’ingresso del primo LSR. Tale parametro viene decrementato ad ogni attraverso di un LSR e viene copiato nell’intestazione IP al momento di ritornare ad un normale router. In figura 9.3 vediamo invece il meccanismo del label stacking, che permette all’MPLS di poter gestire un’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. Bisogna quindi che sia possibile: • associare una label ad ogni LSP4 (operazione di label binding) in modo che, se immaginiamo l’LSP come un’autostrada per i pacchetti, questi ultimi vengano opportunamente etichettati con la giusta 4E

quindi ad ogni FEC.

CAPITOLO 9. MPLS: SOSTITUZIONE D’ETICHETTA

90

label se devono prendere tale via. Questo implica inoltre che pacchetti appartenenti alla stessa FEC abbiano 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 modo che il LSR a valle li riconosca correttamente, e viceversa (bisogna concordare una label con il LSR a valle, in modo che riconosca i pacchetti come appartenenti all’LSP). Ciò è necessario affinché sia possibile fissare un indirizzamento; si vuole però sottolineare che non è necessario che la label di ingresso e quella di uscita per un LSP siano uguali: l’importante è che gli LSR siano adeguatamente informati 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 routing tradizionali, 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, grazie all’uso di una tabella di instradamento detta Label Forwarding Information Base (LFIB), riesce a sostituire l’etichetta qualora le label di ingresso e quelle di uscita per un LSP non fossero uguali. Il label swapping non 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 router dell’LSP ha applicato la sua etichetta: lo swapping, viceversa, è una ’passiva’ sostituzione di etichetta utile a sistemare le cose quando le label dell’interfaccia d’ingresso e quelle d’uscita di un nodo, lungo lo stesso LSP, 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 relativa a quella label, sostituisce la label di ingresso con la label di uscita e infine invia il pacchetto sulla interfaccia specificata verso il next hop. Il tutto, affinché sia fatto correttamente, comporta che il LER sappia effettuare il corretto forwarding del pacchetto verso la sua giusta destinazione.

Figura 9.4:

9.4

Il label swapping

Allocazione delle label

Come abbiamo già sottolineato, le label sono una risorsa gestita dai LSR a valle di un link. Esse possono essere allocate con due diverse modalità: • downstream on demand allocation: l’allocazione viene richiesta dal LSR a monte e viene resa nota solamente al LSR richiedente; • unsolicited downstream allocation: l’allocazione avviene senza esplicita richiesta e viene notificata a tutti i LSR a monte di quello che esegue l’allocazione. A seguito di unsolicited allocation da parte di un certo LSR (che chiamiamo X) si possono tuttavia ricevere allocazioni su di un percorso non utilizzato 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 immediatamente utilizzata se ad un certo punto si vuole instradare traffico attraverso l’LSR X. Ciò permette una maggiore velocità di esecuzione ma richiede memoria; – conservative retention mode: si cancella l’associazione e, in caso di bisogno, si deve eseguire un’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. 5 Necessario è, 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

9.5

91

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 distribuisce ai LSR a monte7 . Siccome i risultati di questo modo d’operare non sono coordinati e comportano 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 LSR che lo segue lungo il LSP (cioè se riceve informazioni già validate dal LRS a valle). Seguendo questo metodo il binding avviene in maniera ordinata e la label all’ingresso è disponibile solamente quando tutto il LSP è stato creato. Rispetto all’indipendent LSP control, tutti i pacchetti di una FEC seguono lo 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 fine di 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 uso di messaggi predefiniti per la gestione e l’assegnazione delle label (v. fig. 9.5). Ha inoltre un meccanismo di riparazione degli errori. 6 Il

binding, lo ricordiamo, è il processo di associazione fra i FEC e le label. decisioni vengono sempre prese dall’LSR a valle.

7 Le

CAPITOLO 9. MPLS: SOSTITUZIONE D’ETICHETTA

92

9.5.3 Fish picture Il problema della fish picture si ha quando la decisione di instradamento è presa solo sulla base dell’indirizzo IP, senza alcun tipo di calcolo statistico atto a bilanciare il carico di due collegamenti posti come in 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 questo modo 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 il traffico su diversi percorsi e si tracciano vie alternative già pronte da utilizzare in caso di guasto (v. fig. 9.7).

Figura 9.7:

9.6

Questione della fish picture [2]

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 eettuata in base ai protocolli tradizionali, quella di trasferimento (forwarding) è dall'MPSL ottemperata tramite il sistema delle etichette e la denizione del concetto di usso (non lavoriamo più con la logica del longest prex match, bensì con quella dell'exact match). Grazie all'MPLS è possibile eettuare una commutazione orientata alla connessione, consistente nel riconoscimento 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.

8 Alcuni

considerano l’MPSL un protocollo di livello 2,5!

9.6. IN SINTESI

93

• Un LSR è un router che supporta MPLS: esso eettua 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 eettua 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 stacking 10 (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 eettuare 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 eettuare 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).

9 Non 10 Il

è un errore di battitura: m piccolo = maggiore generalità, v. slide 25! bit è ad 1 se è l’ultima etichetta o è 0 se vi sono delle etichette ’stack-ate’.

94

CAPITOLO 9. MPLS: SOSTITUZIONE D’ETICHETTA

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: 26 Segmenti 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 e 2 < 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 è ulteriormente raddoppiata (siamo a CW = W = 8 e quindi inizia la fase di congestion avoidance). Teoricamente dovremmo spedire i segmenti 7 . . . 14, solo che il 14◦ si perde. In effetti, il ciclo dopo, la finestra non passa a 9 (cioè non aumenta di 1, com’è normale che accada nel CA) perché non abbiamo ricevuto 8 ACK (quelli da 8 . . . 15), ma solo quelli di numero 8 . . . 14, che sono 7 e che quindi non completano la finestra. Tali 7 ACK, 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 giro prima (il 15) nonché quelli da 16 a 22: il ricevitore, invece, non può fare altro che chiedergli insistentemente il segmento 14, che non è riuscito ad arrivare, ed infatti vengono spediti 6 ACK (da 8 che dovevano essere 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 il Fast retransmit/Fast recovery (in effetti ne sarebbero bastati 3 duplicati, ovvero 4 in totale, per far scattare l’algoritmo): quel che accade è che la finestra si gonfia e passa a fightsize 8 + Numero di ACK duplicati = + 6 = 10 2 2 Si ricorda che il flightsize indica quanti pacchetti il ricevitore presume siano in giro per la rete (tra quelli fightsize confermati e non arriviamo a 8). La W = CW viene perciò messa a 10 e la SSTHR a , cioè a 4. Il 2 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, è tuttavia decisamente indispettito e chiede tre volte il segmento 17 [5b], non essendogli esso ancora arrivato. Siamo ora in [6]: siamo in CA perché la soglia era 4 e la finestra si è sgonfiata fino a passare a 4. Per un pelo non scatta di nuovo il FR/FR, dato che sono arrivati 2 ACK duplicati; in compenso scade l’RTO del 17◦ fightsize segmento e quindi [7] la nuova SSTRH diventa pari a , cioè a 3 (per il trasmettitore i segmenti 2 in giro sono 7, cioè quelli dal 17 al 23, per cui si ha 7/2 arrotondato per difetto), mentre sia W che CW decadono 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 fino al 23◦ ); di lì in poi [8][9], la connessione riprende a crescere in SS secondo le regole del TCP classico e, al 26◦ segmento, la trasmissione è completa. 95

APPENDICE A. ESERCIZI

96

Figura A.1:

Rappresentazione schematica dell’esercizio A.1.1

A.1. PROTOCOLLI DI RETE, ANALISI DI CW

A.1.2

97

Esercizio 2 DATI PRELIMINARI Protocollo: TCP New Reno Segmenti (dimensione MSS) spediti: 30 Segmenti perduti: 14 e 17 RTO = 3RTT

Questo esercizio ha praticamente gli stessi dati di quello precedente e serve semplicemente a mettere in 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 segmento 17 e la sestuplicale1 richiesta del segmento 14. La prima vera differenza si nota a [3]: anzitutto viene memorizzato il numero di sequenza dell’ultimo pacchetto inviato (il 21) nella variabile recover. Il calcolo della nuova CW [3] è identico a quello dell’esercizio A.1.1; questa volta però non usciamo subito dal fastretransmit/fast-recovery perché in [3] riceviamo gli ACK di 17, che è < di 18. In [4] la finestra è ancora pari a 10 in quanto essa deve crescere di 1 per ogni ulteriore ACK duplicato e decrementarsi di 1 per ogni segmento 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 stare nella finestra grande 10). Alla fine di [4] riceviamo gli ACK di 24, 25, 26 e 27: tutti questi numeri sono maggiori della variabile recover (= 17) e quindi possiamo uscire dal FR/FR. In [5] la finestra CW viene messa pari alla soglia, cioè a 4. Come si può notare, una volta che siamo usciti dalla SS non ci torniamo più.

1 Non

ci crederete, ma si scrive proprio così!

APPENDICE A. ESERCIZI

98

Figura A.2:

Rappresentazione schematica dell’esercizio A.1.2

A.1. PROTOCOLLI DI RETE, ANALISI DI CW

A.1.3

99

Esercizio 3 DATI PRELIMINARI Protocollo: TCP 'standard' (senza fronzoli) Segmenti (dimensione MSS) spediti: 64 Segmenti perduti: 53 RTO = 2RTT

Esercizio abbastanza banale, se raffrontato con quelli numero A.1.1 e A.1.2. Fino a [7], di fatto, non accade 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 e quindi il numero degli ACK ad ogni RTT è pari al numero dei segmenti inviati + 1. Da [4] in poi siamo in CA e la finestra cresce di 1 ad ogni RTT, invece di raddoppiare: anche qui tutto va normalmente e senza intoppi. 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 questi 10 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 non impedisce alla finestra di scorrere di 9 posizioni cosicché inviamo i messaggi da 54 a 62. Continuiamo tuttavia 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 finestra W a 1, il ridimensionamento di SSTHR a CW/2 = 12/2 = 6 e la ritrasmissione del 53◦ pacchetto che questa volta viene correttamente ricevuto. Ad [8] la finestra passa a 2 (siamo tornati in SS) e termina la trasmissione con l’invio di 63 e 64.

APPENDICE A. ESERCIZI

100

Figura A.3:

Rappresentazione schematica dell’esercizio A.1.3

A.1. PROTOCOLLI DI RETE, ANALISI DI CW

A.1.4

101

Esercizio 4 DATI PRELIMINARI Protocollo: TCP 'standard' (senza fronzoli) Segmenti (dimensione MSS) spediti: 64 Segmenti 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 RTT dopo [8]: in seguito, la trasmissione può continuare con 63 e 64 (non vengono riportati nello schema, tanto il meccanismo è analogo all’esercizio precedente).

APPENDICE A. ESERCIZI

102

Figura A.4:

Rappresentazione schematica dell’esercizio A.1.4

A.2. MODELLI PER IL TCP

A.2

Modelli per il TCP

A.2.1

Esercizio 1

103

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 ininuente);

• 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,048 Mbit/s discutere l'eetto delle perdite sull'ecienza nell'uso della capacità disponibile. SOLUZIONE:

1. siamo nel caso più semplice, cioè quello di perdite periodiche (v. par 3.3) quindi la dimensione massima della finestra è s 8 W= = 11, 547 → 11 segmenti ⇔ 11, 547 · MSS = 11547 byte 3p 2. anche questo punto è risolvibile semplicemente applicando una pedissequamente formula s 1 3 S= = 108, 25 → 108 segmenti/s ⇔ 108, 25 · MSS · 8 = 866025 bit/s RTT 2p 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. 866 = 42, 3%. L’efficienza nell’uso della banda è infatti del 2048

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;

APPENDICE A. ESERCIZI

104

• 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 a quello degli ACK ritardati (v. par. 3.3.1) quindi la dimensione massima della finestra è, nel primo caso s 8 W1max = = 16, 33 → 16 segmenti ⇔ 16, 33 · MSS = 8165 byte 3p mentre per la connessione 2 si ha: s 8 W2max = = 11, 547 → 11 segmenti ⇔ 11, 547 · MSS = 5774 byte 3pb 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 due parametri2 . Connessione 1: W1min =

16, 33 = 8, 17 → 8 segmenti ⇔ 8, 17 · MSS = 4085 byte 2

W2min =

11, 547 = 5, 77 → 5 segmenti ⇔ 5, 77 · MSS = 2885 byte 2

Connessione 2:

L’andamento nel tempo di entrambe le connessioni sarà caratterizzato dal tipico grafico a dente di sega: la lunghezza dei periodi sarà maggiore nel caso di ACK ritardati (la connessione va a tutti gli effetti più lenta e, inoltre, non riesce a raggiungere i valori della finestra del caso not delayed). La lunghezza di tali periodi è calcolabile tramite la formula: T1 =

W1max · RTT 16, 33 · 0, 06 = = 0, 4899 s 2 2

W2max b · RTT 2 · 11, 547 · 0, 06 = = 0, 6928 s 2 2 √ √ Si noti che T1 · 2 = T2 : tra i due parametri T vi è infatti un fattore b. T2 =

2. anche nel risolvere questo punto dobbiamo tenere presente che una delle due connessioni utilizza ACK ritardati: s 1 3 S1 = = 204, 12 → 204 segmenti/s ⇔ 204, 12 · MSS · 8 = 816497 bit/s RTT 2p s 1 3 S2 = = 144, 34 → 144 segmenti/s ⇔ 144, 34 · MSS · 8 = 577350 bit/s RTT 2bp √ Ancora una √ volta si ha una relazione del tipo S1 · 2 = S2 : anche tra i due parametri S vi è infatti un fattore b. 2 Infatti,

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:

A.2.3

Interpretazione grafica dell’esercizio A.2.2

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 s 8 = 32, 660 segmenti/s ⇒ 32, 66 · 1000 = 32.660 byte/s W= 3p La dimensione della finestra, scritta come numero intero (com’è normale che sia), è pari a 32 (non riceviamo mai l’ACK che la fa diventare 33). La dimensione minima che la finestra potrà assumere è invece pari a 32/2 = 16.

APPENDICE A. ESERCIZI

106

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: 32 · RTT = 1920 ms 2 3. Applicando le formulette: s S=

3 1 = 204, 12 segmenti/s ⇒ 1, 633 Mbit/s 2p RTT

4. Possiamo o utilizzare la formula approssimata che consiste nel confondere il trapezio col rettangolo (v. figura A.6) AW 20 · 1000 · 8 = 20 segmenti/s ⇒ = 1, 333 Mbit/s RTT 0.120 Il valore 1, 333 Mbit/s è abbastanza inferiore agli 1, 633 Mbit/s del caso senza AW: è un buon segno perché 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, la finestra cresce di 1 per ogni round trip time fino al raggiungere il valore 20 (v. figura A.7). In questa fase trasmettiamo: 16 + 17 + 18 + 19 = 70 segmenti La domanda è: quanti RTT con finestra pari a 20 mancano per trasmettere il numero di segmenti che vengono inviati tra una perdita e l’altra (= 1/p = 400 in questo caso)? Per saperlo, basta risolvere l’equazione: 400 = 70 + 20x Il numero di RTT mancanti risulta facilmente essere pari a 16, 5: approssimeremo per eccesso in quanto la 17ma finestra è necessaria per poter trasmettere quello 0,5 che c’è oltre a 16 (detto proprio in 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=

A.3

Latenza

A.3.1

Esercizio 1

400 = 1, 26 Mbit/s 21 · RTT

Supponiamo di avere una connessione TCP New Reno e si tengano buone le seguenti ipotesi: • round trip time RTT = 100 ms;

A.3. LATENZA

Figura A.7:

107

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 anché 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, in segmenti: 25600 WO = = 6, 4 → 7 500 · 8 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!

APPENDICE A. ESERCIZI

108 4. Abbiamo:

• 2RTT per il set-up della connessione (SYN - SYN/ACK - ACK/Richiesta dati);   MSS • 2· + RTT per la fase non ottimale di trasmissione; C •

P − (2 + 4) MSS per trasmettere i dati rimanenti. C

Riassumendo in una formula:   MSS P − (2 + 4) MSS L = 2RTT + 2 · + RTT + = 0, 2 + 0, 231 + 31, 16 = 31, 681 s C C

Elenco delle figure 1.1 1.2 1.3 1.4 1.5 1.6 1.7

La macchina a stati finiti che implementa il TCP . . . . . Possibili inconvenienti in cui si può incappare nel TWH Evoluzione dell’RTO secondo RFC 793 e RFC 2988. . . . Misurazione dell’sRTT . . . . . . . . . . . . . . . . . . . . Ambiguità nel calcolo dell’sRTT . . . . . . . . . . . . . . Duplicazione dei numeri di sequenza . . . . . . . . . . . Schema riassuntivo del calcolo dell’RTT . . . . . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

6 7 11 11 12 13 14

2.1 2.2 2.3 2.4 2.5 2.6 2.7 2.8 2.9 2.10 2.11

Il meccanismo a finestra fra segmenti ricevuti e segmenti non trasmessi. La questione delle capacità e l’adattività del controllo di flusso . . . . . Meccanismo di Slow Start . . . . . . . . . . . . . . . . . . . . . . . . . . . Distinzione fra SS e CA . . . . . . . . . . . . . . . . . . . . . . . . . . . . Un esempio d’evoluzione della finestra . . . . . . . . . . . . . . . . . . . Effetto dell’approssimazione TSS << TCA . . . . . . . . . . . . . . . . . . Condivisione della risorsa . . . . . . . . . . . . . . . . . . . . . . . . . . . L’algoritmo di fast recovery . . . . . . . . . . . . . . . . . . . . . . . . . . . L’algoritmo di fast recovery (2) . . . . . . . . . . . . . . . . . . . . . . . . . Il TCP classico e il Tahoe (cioè TCP + Fast Rec.) a confronto . . . . . . . I protocolli TCP Reno e TCP New Reno a confronto . . . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

15 17 18 19 20 20 21 23 23 24 25

3.1 3.2 3.3 3.4 3.5 3.6 3.7 3.8 3.9 3.10 3.11 3.12 3.13 3.14 3.15 3.16

Modello periodico . . . . . . . . . . . . . . . . . . . . . . . Modello periodico (2) . . . . . . . . . . . . . . . . . . . . . . Andamento della finestra con perdite aleatorie . . . . . . . Le variabili Yi e Ai . . . . . . . . . . . . . . . . . . . . . . . Le variabili aleatorie in gioco nel modello TD . . . . . . . Modello TD+TO . . . . . . . . . . . . . . . . . . . . . . . . . Modello TD+TO+AW . . . . . . . . . . . . . . . . . . . . . . L’approssimazione introdotta dalla formula di AW . . . . Modelli a confronto . . . . . . . . . . . . . . . . . . . . . . . Influenza dell’RTT sul modello . . . . . . . . . . . . . . . . Influenza di AW sul modello . . . . . . . . . . . . . . . . . Influenza di RTO sul modello . . . . . . . . . . . . . . . . . I passi imprescindibili per effettuare un trasferimento dati Esempio con W = 6 . . . . . . . . . . . . . . . . . . . . . . . Schema esplicativo della formula di L2 . . . . . . . . . . . Raddoppio della finestra in SS . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

30 30 32 33 34 36 36 37 38 38 39 39 40 41 42 43

4.1 4.2 4.3

Schema concettuale dello store-and-forward, nella commutazione di pacchetto . . . . . . . . . Le classi di reti . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Subnetting e Supernetting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

48 49 50

5.1 5.2 5.3 5.4

Schema logico di funzionamento di un router Patricia Trie . . . . . . . . . . . . . . . . . . . . . Schema dei router di prima generazione . . . Matrice di commutazione crossbar . . . . . . .

54 54 55 55

109

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . . . . .

. . . .

. . . . . . .

. . . . . . . . . . . . . . . .

. . . .

. . . . . . .

. . . . . . . . . . . . . . . .

. . . .

. . . . . . .

. . . . . . . . . . . . . . . .

. . . .

. . . . . . .

. . . . . . . . . . . . . . . .

. . . .

. . . . . . .

. . . . . . . . . . . . . . . .

. . . .

. . . . . . .

. . . . . . . . . . . . . . . .

. . . .

. . . . . . .

. . . . . . . . . . . . . . . .

. . . .

. . . . . . . . . . . . . . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

ELENCO DELLE FIGURE

110 5.5 5.6 5.7 5.8 5.9

Rete di Clos . . . . . . . . . . . . . Accodamento in uscita . . . . . . . Accodamento in ingresso . . . . . Accodamento virtuale in uscita . . Accodamento a memoria comune

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

56 56 56 57 57

6.1 6.2 6.3 6.4 6.5 6.6 6.7 6.8 6.9 6.10 6.11 6.12

Grafo orientato (a sinistra) e un grafo non orientato (a destra) Grafi aciclici, connessi, completamente connessi . . . . . . . . Alcuni esempi di minimum spanning tree . . . . . . . . . . . . . Cammino di peso minimo . . . . . . . . . . . . . . . . . . . . . Algoritmo di Bellman-Ford . . . . . . . . . . . . . . . . . . . . Esempio grafico d’applicazione dell’algoritmo di Dijkstra . . Interconnessione di più LAN e spanning tree . . . . . . . . . . Esempio di calcolo delle tabelle di routing . . . . . . . . . . . . Bouncing effect . . . . . . . . . . . . . . . . . . . . . . . . . . . . Convergenza lenta . . . . . . . . . . . . . . . . . . . . . . . . . Il problema del count to infinity . . . . . . . . . . . . . . . . . . Situazione patologica e irrisolvibile . . . . . . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

59 60 60 61 63 64 65 66 67 68 68 69

7.1 7.2 7.3 7.4 7.5 7.6 7.7

Formato del pacchetto RIP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Schema concettuale del routing gerarchico . . . . . . . . . . . . . . . . . . . . . . . . Distinzione logica fra host e router . . . . . . . . . . . . . . . . . . . . . . . . . . . . Alcuni tipi di reti multiaccesso . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Topologia a stella equivalente (con nodo virtuale) . . . . . . . . . . . . . . . . . . . Router vicini e router adiacenti . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Le fasi necessarie per lo scambio di informazioni e la sincronizzazione nell’OSPF

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

74 75 75 76 76 77 78

8.1 8.2

BGP: sessioni interne ed esterne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . BGP: scambio di path vector . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

82 82

9.1 9.2 9.3 9.4 9.5 9.6 9.7

Schema concettuale di una rete funzionante tramite MPLS: LER e LSR Struttura e posizionamento dell’etichetta dell’MPLS. . . . . . . . . . . Il meccanismo del label stacking . . . . . . . . . . . . . . . . . . . . . . . Il label swapping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Label Distribution Protocol . . . . . . . . . . . . . . . . . . . . . . . . . . . Questione della fish picture . . . . . . . . . . . . . . . . . . . . . . . . . . Questione della fish picture [2] . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

86 87 87 88 89 90 90

A.1 A.2 A.3 A.4 A.5 A.6 A.7

Rappresentazione schematica dell’esercizio A.1.1 . . . . . . . . . . . . . . . . . . Rappresentazione schematica dell’esercizio A.1.2 . . . . . . . . . . . . . . . . . . Rappresentazione schematica dell’esercizio A.1.3 . . . . . . . . . . . . . . . . . . Rappresentazione schematica dell’esercizio A.1.4 . . . . . . . . . . . . . . . . . . Interpretazione grafica dell’esercizio A.2.2 . . . . . . . . . . . . . . . . . . . . . . Interpretazione grafica dell’approssimazione effettuata per il calcolo di AW. . . Interpretazione grafica dell’approssimazione effettuata per il calcolo di AW (2).

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

94 96 98 100 103 104 105

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .