4. Il livello rete

4.1 Visione d'insieme

L'obiettivo è spostare i pacchetti dal mittente al destinatario. Il livello di rete nel mittente incapsula i segmenti in datagrammi, cioè pacchetti a livello di rete, e poi in frame al livello 2. Infine li trasmette al proprio router vicino. Nel ricevente, il livello di rete riceve i datagrammi dal proprio router vicino, estrae i segmenti e li consegna al livello trasporto, poi a un processo.
Il ruolo primario del piano dei dati di ciascun router intermedio è quello di inoltrare il datagramma da link d’ingresso a link d’uscita, mentre quello del piano di controllo è coordinare queste azioni di inoltro locali in modo che alla fine i datagrammi vengano trasferiti end-to-end su percorsi di router tra mittente e destinatario.
Ci sono protocolli di livello rete in tutti gli host e router, ma i router non hanno ulteriori livelli sopra quello di rete. Il compito dei router è di ispezionare tutti gli header dei datagrammi che li attraversano per prendere decisioni di inoltro.

4.1.1 Inoltro e instradamento: piano dei dati (data plane) e piano di controllo (control plane)

Il ruolo principale del livello di rete è quindi piuttosto semplice: trasferire pacchetti da un host a un altro. Per fare questo è possibile identificare due importanti funzioni.

Inoltro (forwarding) - data plane

È un operazione locale che esegue un router quando riceve un pacchetto e che consiste nel trasferimento del pacchetto sull’appropriato collegamento di uscita. Ad esempio un pacchetto che arriva dal mittente deve essere inoltrato al successivo router sul percorso verso il destinatario. In pratica il pacchetto viene spostato da un interfaccia d'ingresso del router a una di uscita. Per inoltrare tali pacchetti, i router estraggono da uno o più campi dell’intestazione i loro valori che utilizzano come indice nella tabella di inoltro (tabella di forwarding o forwarding table). Questo gli permette di identificare a quale interfaccia di uscita il pacchetto debba essere diretto. Dato che l'inoltro ci impiega poco tempo, perché avviene su scala locale, è solitamente implementato in hardware.

Un analogia al forwarding può essere un viaggio, quando bisogna spostarsi all'interno di uno snodo e quindi cambiare treno o prendere uno svincolo autostradale per esempio.

Instradamento (routing) - control plane

Il livello di rete deve determinare il percorso che i pacchetti devono seguire tramite algoritmi di instradamento (algoritmi di routing). Un algoritmo di instradamento determina il percorso seguito dai pacchetti dal mittente al destinatario. La funzione di instradamento è implementata nel piano di controllo del livello di rete e, dato che ci impiega più tempo dell'inoltro perché avviene su scala globale, è solitamente implementato in software.

Un analogia al routing è quando si pianificano tutte le tappe del viaggio, dall'inizio alla fine.

Tradizionalmente le aziende produttrici di router implementavano in ognuno di essi una componente di instradamento che comunicava con la corrispettiva negli altri router.

L'approccio in cui un controller remoto, separato fisicamente dai router, calcola e distribuisce le tabelle di inoltro a tutti i router presenta le stesse componenti del metodo tradizionale, tranne che la funzionalità di instradamento del piano di controllo è separata fisicamente dal router. In questo caso il dispositivo di instradamento effettua solo l'inoltro, mentre il controller remoto calcola e distribuisce le tabelle di inoltro. Dato che il controller remoto potrebbe essere implementato in un data center per comunicare con i router devono scambiarsi messaggi contenenti le tabelle di inoltro e altre informazioni di instradamento. Questo piano di controllo è il cuore del software-defined networking (SDN), nel quale la rete è “software-defined” perché il controller che calcola le tabelle di inoltro e interagisce coi router è implementato in software. Spesso tali implementazioni sono open e quindi più persone possono contribuire per migliorare il software che controlla le funzionalità di rete.

4.2 Com'è fatto un router

In un router si possono identificare quattro componenti.

4.2.1 Componenti del router

Porte di ingresso

Svolgono le funzioni a livello fisico di terminazione di un collegamento in ingresso al router (riquadri verdi).
Svolgono anche funzioni a livello collegamento (riquadri arancioni) necessarie per inter-operare con le analoghe funzioni all’altro capo del collegamento di ingresso.
Svolgono inoltre la funzione di ricerca (riquadri rossi) in modo che il pacchetto inoltrato nella struttura di commutazione del router esca sulla porta di uscita corretta.
I pacchetti di controllo, per esempio quelli che trasportano informazioni sul protocollo di instradamento, sono inoltrati dalla porta di ingresso al processore di instradamento. Con il termine porta ci si riferisce alle interfacce fisiche di input e output del router, che sono diverse dalle porte software associate alle applicazioni di rete e alle socket.

La funzione di terminazione (elettrica) della linea e l’elaborazione a livello di collegamento implementano rispettivamente il livello fisico e di collegamento associati a un singolo collegamento di ingresso al router. L’elaborazione effettuata alla porta di ingresso è centrale per la funzionalità del router: è qui che, utilizzando le informazioni della tabella di inoltro, viene determinata la porta di uscita a cui dirigere un pacchetto attraverso la struttura di commutazione.

Struttura di commutazione

La struttura di commutazione connette fisicamente le porte di ingresso a quelle di uscita, trasferendo i pacchetti, ed è interamente contenuta all’interno del router. Il tasso di commutazione è la frequenza alla quale i pacchetti vengono trasferiti dagli ingressi alle uscite e viene spesso misurato come multiplo della velocità di comunicazione. Con $N$ ingressi vorremmo una commutazione $N$ volte più veloce della comunicazione.

Commutazione a memoria

Le prime generazioni di router erano computer tradizionali dove la commutazione era controllata dalla CPU. Quando arrivava un pacchetto, la porta di ingresso ne segnalava l'arrivo tramite interrupt e quindi lo copiava nella memoria del processore di instradamento che procedeva a estrarre dall’intestazione l’indirizzo di destinazione. Poi, tramite la tabella di inoltro, individuava la porta di uscita e copiava nel suo buffer il pacchetto.
Due pacchetti non possono essere inoltrati contemporaneamente, anche se hanno differenti porte di destinazione, perché può essere effettuata solo un’operazione alla volta di scrittura/lettura in memoria tramite il bus di sistema. Per cui la velocità di commutazione, ossia la velocità massima alla quale i pacchetti vengono trasferiti dalle porte di ingresso a quelle di uscita, era inferiore a $B/2$. Questo nel caso in cui l'ampiezza di banda della memoria permetteva di leggere o scrivere $B$ pacchetti al secondo.

Commutazione a bus

In questo approccio si usa un bus dati condiviso interno al router per trasmettere i datagrammi dagli ingressi alle uscite, senza intervento da parte del processore di instradamento. Dato che il pacchetto viene ricevuto da tutte le porte di output, viene aggiunta un'etichetta interna di commutazione (intestazione) al pacchetto che indica la porta locale di output alla quale il pacchetto deve essere trasferito quando viene trasmesso sul bus, così solo la porta corrispondente all’etichetta lo raccoglierà. L’etichetta viene quindi rimossa dalla porta di output in quanto usata solo all’interno della struttura di commutazione per attraversare il bus. Se più pacchetti arrivano contemporaneamente al router, ognuno su una porta di input diversa, tutti tranne uno dovranno aspettare, dato che sul bus si può trasferire soltanto un pacchetto alla volta. La velocità di commutazione è limitata dalla banda del bus (cioè dalla velocità di trasferimento dati sul bus). Gli switch Cisco 6500 commutano pacchetti su un bus a 32 Gbit/s che è sufficiente per router di accesso e router interni alle reti aziendali.

Commutazione a matrice

Per superare la limitazione di banda di un singolo bus condiviso viene utilizzata una matrice di punti di interconnessioni tra linee di ingresso e linee di uscita. Tale matrice consiste di $2n$ bus che collegano $n$ porte di ingresso a $n$ porte di uscita. Ogni bus verticale interseca tutti i bus orizzontali a un punto di incrocio che può essere in qualsiasi momento aperto o chiuso dal controller della struttura di commutazione. Quando un pacchetto giunge a una porta di ingresso A e deve essere inoltrato alla porta Y, il controller chiude l’incrocio di A e Y e la porta A invia il pacchetto sul suo bus e solo il bus Y lo riceverà. Un pacchetto dalla porta B può però essere inoltrato a X nello stesso tempo, perché i pacchetti A-Y e B-X usano bus di input e output diversi. Quindi, a differenza degli altri due approcci, la commutazione a matrice è in grado di inoltrare più pacchetti in parallelo.
Una matrice di commutazione è non-blocking, quindi un pacchetto in via di inoltro verso una porta di uscita non viene bloccato a meno che esista un altro pacchetto in via di inoltro sulla stessa porta di uscita. Tuttavia, se due pacchetti provenienti da due diverse porte di input sono destinati alla stessa porta di output, uno dovrà accodarsi alla porta di input, perché solo un pacchetto alla volta può essere inoltrato su uno specifico bus.
Gli switch Cisco 1200 commutano 60 Gbit/s attraverso la matrice di interconnesione.

Porte di uscita

Memorizzano i pacchetti che provengono dalla struttura di commutazione e li trasmettono sul collegamento in uscita, operando le funzionalità necessarie del livello di collegamento e fisico. Nei collegamenti bidirezionali, che trasportano traffico in entrambe le direzioni, la porta di uscita verso un collegamento è solitamente accoppiata alla porta di ingresso di quel collegamento sulla stessa scheda di collegamento.
In questo caso, se i datagrammi arrivano dal commutatore più in fretta di quanto le porte di uscita possano smaltirli potrebbero essere scartati se le memorie si riempiono.
Per cui si adotta una politica di scheduling, ovvero si decide quale datagramma deve essere servito (FIFO, Priority scheduling, Network neutrality).

Processore di instradamento

Esegue le funzioni del piano di controllo. Nei router tradizionali, esegue i protocolli di instradamento, gestisce le tabelle di inoltro e le informazioni sui collegamenti attivi, ed elabora la tabella di inoltro per il router. Nei router SDN il processore di instradamento è responsabile della comunicazione con il controller remoto, in modo da ricevere le occorrenze della tabella di inoltro e installarle alle porte di ingresso. Inoltre effettua delle operazioni di gestione della rete.

In un router le porte di ingresso, le porte di uscita e la struttura di commutazione sono implementate quasi sempre in hardware, mentre le e funzioni del piano di controllo sono solitamente implementate via software ed eseguite sul processore di instradamento.

4.2.4 Accodamento

È evidente che si possono formare code di pacchetti sia presso le porte di ingresso sia presso quelle di uscita. Il luogo e la lunghezza della coda (sia alle porte di input che di output) dipendono dalla quantità di traffico di rete, dalle velocità relative della struttura di commutazione e dalla linea. Quando queste code crescono, la memoria del router può esaurirsi e quindi può avvenire una perdita di pacchetti nel caso non vi sia memoria per immagazzinare quelli in arrivo.

Accodamento alle porte di ingresso

Nel caso in cui la struttura di commutazione non fosse sufficientemente rapida, rispetto alle linee in ingresso, nel trasferire tutti i pacchetti in arrivo senza ritardo, si può verificare un accodamento anche alle porte di ingresso.

Consideriamo una struttura di commutazione facente uso di una rete di interconnessione. È possibile trasferire più pacchetti in parallelo quando le relative porte di uscita sono differenti, ma se due pacchetti in testa a due code di ingresso sono destinati alla stessa coda di uscita, allora uno dei pacchetti sarà bloccato e dovrà attendere: istante per istante, la struttura di commutazione può trasferire solo un pacchetto a una certa porta di uscita.

Supponiamo che la struttura di commutazione scelga di trasferire il primo pacchetto della coda in alto a sinistra (quello rosso). In questo caso, il pacchetto nella coda in basso a sinistra (rosso) deve attendere, così come quello verde che si trova dietro di lui, anche se non si verifica contesa per la porta di uscita centrale (che rappresenta la destinazione del pacchetto di colore verde). Questo fenomeno è noto come blocco in testa alla coda (HOL, head-of-the-line blocking), ovvero che un pacchetto nella coda di ingresso deve attendere il trasferimento attraverso la struttura (anche se la propria porta di destinazione è libera) in quanto risulta bloccato da un altro pacchetto che lo precede. In pratica, anche se il pacchetto verde può essere trasferito nella porta di destinazione centrale, rimane bloccato perché il pacchetto rosso non è stato ancora consegnato.

Accodamento alle porte di uscita (pagina 333 - slide 19)

Se i pacchetti arrivano troppo velocemente sul collegamento in uscita, si accodano. Il numero di pacchetti in coda può continuare a crescere fino a esaurire lo spazio di memoria sulla porta di uscita. In assenza di sufficiente memoria per inserire nel buffer il nuovo pacchetto in ingresso, occorrerà stabilire se scartarlo (politica nota come drop-tail, eliminazione in coda) o se rimuoverne uno o più, fra quelli già in coda, per far posto al nuovo arrivato. In alcuni casi può risultare vantaggioso eliminare un pacchetto (o marcarne l’intestazione) prima che il buffer sia pieno, al fine di fornire al mittente un segnale di congestione. Tali tecniche che prevedono l'eliminazione e marcatura dei pacchetti presentano il nome collettivo di algoritmi di AQM (active queue management, gestione attiva della coda). Tra questi il più studiato e implementato è detto algoritmo RED (random early detection).

All'istante $t$ i datagrammi di ogni porta di ingresso transitano verso la stessa porta di uscita e sono accodati in attesa di trasmissione. Nell'unità di tempo successiva verrà trasmesso uno di questi tre pacchetti. Nel mentre però sono giunti due nuovi pacchetti al commutatore ed uno di questi pacchetti è destinato alla porta di uscita superiore. Quando vi sono più pacchetti accodati sulle porte di uscita, uno schedulatore di pacchetti (packet scheduler) deve stabilire in quale ordine trasmetterli e quindi bisogna capire quanta memoria serve nei buffer.

La regola empirica nella RFC3439 era che la quantità di memoria riservata al buffer (B) dovesse essere uguale a un RTT medio (per esempio 250 ms) moltiplicato per la capacità del collegamento (C). Quindi un collegamento a 10 Gbps con un RTT di 250 ms avrebbe bisogno di un buffer pari a $B=RTT\times C=2,5$ Gbit. Le raccomandazioni più recenti suggeriscono che quando c'è un gran numero di flussi TCP, quindi $N$ flussi, che passano attraverso un collegamento, la quantità di buffer necessaria sia $B=\frac{RTT\times C}{\sqrt{N}}$.

4.2.5 Schedulazione dei pacchetti

I meccanismi di scheduling scelgono quale pacchetto deve essere trasmesso su un collegamento. Esiste la procedura FCFS (first-come-first-served, primo-arrivato-primo-servito), anche nota come FIFO (first-in-first-out). Vi sono poi delle politiche di scarto nel caso la coda sia piena:

• Tail drop: scarto i pacchetti in arrivo
• Priority drop: scarto o cancello basandomi su un livello di priorità
• Random drop: scarto o cancello casualmente

4.3 Il protocollo IP

4.3.1 Formato dei datagrammi IPv4

Il pacchetto a livello di rete è noto come datagramma. I principali campi dei datagrammi IPv4 sono i seguenti:

Numero di versione

Quattro bit che specificano la versione del protocollo IP del datagramma per consentire al router la corretta interpretazione del datagramma, dato che versioni diverse di IP (4 o 6) hanno differenti formati per i datagrammi.

Lunghezza header

Dato che un datagramma IPv4 può contenere un numero variabile di opzioni (incluse nell’intestazione), sono presenti quattro bit che indicano il numero di parole di 32 bit nell'header, ovvero dove iniziano i dati del datagramma. I datagrammi IP che non contengono opzioni hanno un intestazione di 20 byte (5 $\cdot$ 32).

Tipo di servizio

Gli 8 bit del type of service (TOS) servono per indicare il tipo di servizio del datagramma (per esempio quelli che richiedono basso ritardo, alto throughput o affidabilità). Viene potenzialmente usato per funzioni chiamate "DiffServ" e "Explicit Congestion Notification" (ECN), ma è raramente usato in pratica.

Lunghezza del datagramma

Campo a 16 bit che rappresenta la lunghezza totale del datagramma IP, includendo sia l'intestazione sia i dati, misurata in byte. La massima dimensione dei datagrammi IP è 65.535 byte, anche se raramente questi superano i 1500 in modo da non superare la lunghezza massima del campo dati dei frame Ethernet.

Identificatore (ID) del datagramma

Campo a 16 bit che indicano il numero (di solito sequenziale) assegnato al datagramma. È usato per raccogliere eventuali frammenti multipli e riassemblare il datagramma complessivo. Questo campo serve per la frammentazione.

Flag

Campo a 3 bit che specificano se il datagramma è un frammento di un datagramma più lungo. Se è così, dicono anche se questo è l'ultimo frammento o no. Questo campo serve per la frammentazione.

Offset del frammento

Campo a 13 bit che indica in quale punto del datagramma originale va inserito questo frammento e viene espresso in multipli di 8 byte. Questo campo serve per la frammentazione.

Time to live (TTL)

Campo a 8 bit utilizzato per assicurare che i datagrammi non restino in circolazione per sempre nella rete (per esempio, a causa di un instradamento ciclico). Viene inizializzato dal mittente e viene decrementato di un'unita ogni volta che il datagramma è elaborato da un router. Quando raggiunge il valore 0, il router scarta il datagramma e invia un messaggio di notifica al mittente.

Protocollo superiore

Campo a 8 bit che viene utilizzato quando il datagramma raggiunge la destinazione finale. Il valore del campo indica lo specifico protocollo a livello di trasporto al quale vanno passati i dati del datagramma (es: 6 = TCP, 17 = UDP). Questo valore ha un ruolo analogo a quello del campo numero di porta nel segmento a livello di trasporto. Il numero di protocollo collega livello rete e di trasporto, mentre il numero di porta collega livello di trasporto e di applicazione.

Checksum dell'header

Campo a 16 bit che, come in UDP, consente ai router di rilevare gli errori sui bit nei datagrammi ricevuti. È calcolato facendo la somma con riporto di tutte le parole di 16 bit dell'header, sui cui viene fatto il complemento a 1.
Un router calcola il checksum per ciascun datagramma IP ricevuto e rileva una condizione di errore se il checksum trasportato nell’intestazione del datagramma non corrisponde a quello calcolato, in tal caso viene scartato il datagramma. Tale checksum però viene effettuato solo sull'intestazione, mentre in TCP/UDP è calcolato sull'intero segmento.

Indirizzo IP sorgente

Campo a 32 bit nel quale il mittente inserisce il proprio indirizzo IP.

Indirizzo IP destinazione

Campo a 32 bit nel quale il mittente inserisce l'indirizzo IP del destinatario, che spesso viene determinato attraverso una ricerca DNS.

Opzioni IP

In alcuni casi è utilizzato per controllare l'elaborazione e l'instradamento dei datagrammi, ma nella maggioranza dei casi il campo è vuoto.

Padding

Bit a zero aggiunto se le opzioni non terminano ad un multiplo di 32 bit, in modo che l'header sia un multiplo di 32 bit.

Dati

Nella maggior parte dei casi, il campo dati contiene il segmento a livello di trasporto (TCP o UDP) da consegnare alla destinazione, ma può trasportare anche altri tipi di dati, quali i messaggi ICMP.

4.3.2 Frammentazione dei datagrammi IPv4

Ciascun tipo di hardware specifica un limite di dati che una trasmissione può trasportare, per cui la massima quantità di dati che un frame a livello di collegamento può trasportare è detta unità massima di trasmissione (Maximum Transmission Unit, MTU). Ciascun datagramma deve contenere al più un numero di Byte pari alla MTU, se no l'hardware non può incapsularlo in un frame (livello 2). Questo limite non sarebbe un problema di per sé, ma le tratte del percorso tra mittente e destinatario possono utilizzare differenti protocolli a livello di collegamento e possono avere differenti MTU, proprio perchè Internet è eterogenea. Un datagramma su una di queste reti potrebbe essere troppo grande per inviarlo su una delle altre reti.

Per esempio supponiamo di avere un router che interconnette due reti che presentano diversi protocolli a livello di collegamento e MTU di 1500 e 1000 Byte rispettivamente. Se l'host $H_1$ invia un datagramma di 1500 Byte all'host $H_2$ il router $R$ non potrà trasmetterlo direttamente sulla rete 2.

Quindi il router $R$ frammenta il datagramma IP in due o più datagrammi IP più piccoli, detti frammenti, e invia ogni frammento indipendentemente dagli altri sul collegamento di uscita. Ogni frammento ha lo stesso formato di un datagramma normale. Il flag nell'header indicano se un datagramma è un frammento o no ed il campo "Offset del frammento" specifica come concatenarli.

Conoscendo l'MTU e la dimensione dell'header, il router calcola quanti frammenti servono e quanti Byte di dati contiene ciascuno. Quando crea i frammenti, il router copia i campi necessari dall'header del frammento originale e trasmette tutti i frammenti in sequenza, con identificatori diversi.
I flag utilizzati sono: 0 - D - M

• D: do not fragment (se servisse frammentare, scarta il pacchetto). Il ricevitore che non può gestire la frammentazione o rilevamento MTU.
• M: more fragments (= 1 per ogni frammento), eccetto l'ultimo che ha M = 0, ma fragment offset > 0.

I frammenti dovranno però essere riassemblati prima di raggiungere il livello di trasporto alla destinazione, questo perché riassemblare i datagrammi nei router avrebbe introdotto una complessità che ne avrebbe limitato le prestazioni. Per tale motivo il compito di riassemblare i datagrammi e dei sistemi periferici. Per consentire all'host di destinazione di riassemblare i frammenti, nell'intestazione del datagramma IPv4 ci sono i campi identificazione, flag e offset di frammentazione.
Quando crea un datagramma, l’host lo contrassegna con un numero identificativo e con gli indirizzi di sorgente e di destinazione. Generalmente, l’host di invio incrementa l’identificativo di ciascun datagramma che invia. Quando il router frammenta il datagramma, contrassegna i frammenti con gli indirizzi di sorgente e di destinazione e con l’identificatore numerico del datagramma originario. Quando la destinazione riceve una serie di datagrammi dallo stesso host mittente, può esaminare gli identificatori per individuare i frammenti di uno stesso datagramma. Siccome IP fornisce un servizio non affidabile, alcuni frammenti potrebbero non giungere mai a destinazione. Per questo motivo, affinché l’host di destinazione sia assolutamente certo di aver ricevuto tutti i frammenti e sia in grado di riassemblarli in modo corretto, l’ultimo ha il campo posto a 0, mentre in tutti gli altri è posto a 1. Si utilizza infine il campo di offset per specificare l’esatto ordine che i frammenti avevano originariamente all’interno del datagramma IP e per determinare se un frammento è stato perduto.

Se per esempio deve essere inviato un datagramma di 1500 Byte da $H_1$ a $H_2$, $R_1$ divide il datagramma in due frammenti e li invia a $R_2$. $R_2$ però non riassembla i frammenti perchè non è la destinazione finale, ma li inoltra come pacchetti qualsiasi (stateless). La destinazione finale $H_2$ raccoglie e riassembla i frammenti.
Questo meccanismo porta al vantaggio che i frammenti possono seguire percorsi diversi ed $R_2$ non deve ricevere tutti i frammenti prima di inoltrarli.

Il problema si presenta quando ci sono perdite di frammenti, perché un datagramma non può essere ricomposto finché non arrivano tutti i frammenti. Il ricevitore memorizza i frammenti finché non li riceve tutti, ma non può memorizzarli per un tempo arbitrariamente lungo. Per questo motivo il protocollo IP specifica il tempo massimo da attendere dopo la ricezione del primo frammento, poiché i ritardi di consegna potrebbero far eccedere questo tempo.

4.3.3 Indirizzamento IPv4

Generalmente un host ha 1-2 collegamenti (Ethernet e WiFi) su cui invia i datagrammi. Un indirizzo IP è una stringa di 32 bit (4 byte) associata ad un'interfaccia di rete, che è il confine tra host e collegamento fisico. Invece, dato che il compito di un router è ricevere datagrammi da un collegamento e inoltrarli su un altro, deve necessariamente essere connesso ad almeno due collegamenti. Anche il confine tra un router e i suoi collegamenti è chiamato interfaccia e ne possiede una su ciascuno dei suoi collegamenti, che possono essere più di due.

Gli host ed i router devono usare le stesse convenzioni di indirizzo e, dato che ogni indirizzo IP pubblicamente raggiungibile deve essere unico, ogni interfaccia ha (almeno) un indirizzo IP. L'indirizzo IP è associato a un'interfaccia e non all'host o al router che la contiene.
Quando si invia un pacchetto su Internet, il software che implementa i protocolli di rete lato mittente deve specificare il proprio indirizzo IP (32 bit), cioè il source address, e l'indirizzo IP del ricevitore (32 bit), cioè il destination address. I router prendono decisioni di inoltro e instradamento basandosi unicamente sul destination address.
Gli indirizzi IP sono lunghi 32 bit (4 byte) e quindi ci sono in totale $2^{3}2$ indirizzi IP che vanno da 0.0.0.0 a 255.255.255.255. Tali indirizzi sono scritti nella notazione decimale puntata, in cui ogni sezione da 8 bit (1 byte) è espressa come un intero decimale (che può essere solamente positivo) che è separato dagli altri byte dell'indirizzo con un punto. Per esempio l'indirizzo IP 193.32.216.9 in notazione binaria diventa 11000001.00100000.11011000.00001001.

Gli indirizzi IP sono generalmente divisi in due parti:

• un prefisso che identifica la rete alla quale l'host è allacciato (network ID o NetID). Ogni rete in Internet è identificata da un numero unico al mondo ma che non può essere scelto in modo casuale, perché parte dell'indirizzo è determinato dalla sottorete cui è collegato. Un NetID specifica una Local Area Network (LAN).
• un suffisso che identifica un'interfaccia di rete allacciata a quella rete (ID dell'host, o HostID). Ogni interfaccia di rete ha un indirizzo IP unico su quella rete.

Il modo di assegnare gli indirizzi IP garantisce che ogni host riceva un indirizzo univoco, che gli ID di rete (i prefissi) siano coordinati a livello globale e che i suffissi possano essere assegnati localmente, senza bisogno di coordinazione globale.

In passato vi era l'indirizzamento statico noto come classful addressing, in cui le parti di rete di un indirizzo IP dovevano essere lunghe 8, 16 o 24 bit ed erano note rispettivamente come reti di classe A, B, C.

• Classe A (primo bit = 0): 7 bit per il NetID, 24 bit per l'HostID
• Classe B (primi bit = 10): 14 bit per il NetID, 16 bit per l'HostID
• Classe C (primi bit = 110): 21 bit per il NetID, 8 bit per l'HostID

Le reti che ne risultavano non erano ben dimensionate

• Classe A: 128 reti, ciascuna con 16777216 host
• Classe B: 16384 reti, ciascuna con 65536 host
• Classe C: 2097152 reti, ciascuna con 256 host
• Classe D (primi bit = 1110): riservata per 268,435,456 indirizzi multicast
• Classe C (primi bit = 1111): riservata per 268,435,456 indirizzi non assegnati

Dato che le reti di classe C potevano ospitare solo fino a $2^8-2=254$ host, che erano troppo pochi per molte organizzazioni, venivano richieste da tutti le classi A e B. Questo però comportò ad un rapido esaurimento degli indirizzi.

Esiste un’autorità globale che ha la responsabilità di gestire lo spazio di indirizzamento IP e di allocare i blocchi di indirizzi, ovvero ICANN (Internet Corporation for Assigned Names and Numbers). È stata creata per gestire l'assegnazione di indirizzi ed arbitrare eventuali dispute tra molteplici pretendenti, ma non assegna i prefissi direttamente perché autorizza diverse entità, dette registrar, a farlo. I registrar consentono agli ISP (Internet Service Provider) di accaparrarsi blocchi di indirizzi. Quindi per ottenere un indirizzo un'azienda solitamente contatta un ISP e se ne fa assegnare uno.

Supponiamo che un ISP avesse un prefisso di classe C. Con l'assegnazione "classful" dovrebbe dare tutti gli indirizzi allo stesso cliente, invece con l'indirizzamento classless può suddividere ulteriormente lo spazio di indirizzi a disposizione. Per fare ciò dovrà allungare il prefisso.
Se per esempio l'ISP ha il blocco di indirizzi 193.185.15.0 - 193.185.15.255:

• Da **11000001.10111001.00001111.**00000000
• A **11000001.10111001.00001111.**11111111

Per poterli ripartire tra più clienti, l'ISP genera 4 prefissi più lunghi:

• Prefisso 1: 11000001.10111001.00001111.00 xxxxxx
• Prefisso 2: 11000001.10111001.00001111.01 xxxxxx
• Prefisso 3: 11000001.10111001.00001111.10 xxxxxx
• Prefisso 4: 11000001.10111001.00001111.11 xxxxxx

Ogni rete può contenere 62 host (i suffissi con tutti 0 sono per l'indirizzo di rete, mentre con tutti 1 è per l'indirizzo di broadcast). Abbiamo quindi 4 clienti invece di 1.

Per conoscere il limite tra prefisso e suffisso si memorizzano 32 bit, dove gli unici bit a 1 sono quelli del prefisso. Per memorizzare tale informazione si utilizza una maschera di sottorete(subnet mask), della quale i bit a 1 più a sinistra definiscono l’indirizzo della sottorete. Tale maschera serve perché ai router serve solo il prefisso per prendere decisioni di inoltro ed una maschera permette di estrarre tale prefisso da un indirizzo con un AND logico bit-a-bit.

Per mandare pacchetti all'indirizzo di destinazione $D$, si utilizza l'interfaccia per cui ($D$ AND $M_i)=N_i$. In pratica, per ricavarsi l'interfaccia di uscita (eth1, eth2...) si esegue prima l'AND tra indirizzo di destinazione e la subnet mask per ricavarsi l'indirizzo di rete. La coppia indirizzo di rete e subnet mask ($N_1/M_1$ per esempio) identifica l'interfaccia di uscita.

La strategia di assegnazione degli indirizzi Internet è detta Classless Inter-Domain Routing CIDR. Se consideriamo per esempio prefissi di 26 bit e 6 bit per l'HostID, nella maschera avremo 26 bit a 1 seguiti da 6 zeri.
In notazione binaria avremo: 11111111.11111111.11111111.11000000
In notazione decimale invece: 255.255.255.192
Con la notazione CIDR si può sintetizzare il tutto scrivendo ddd.ddd.ddd.ddd/m, ovvero la notazione decimale + /m, dove $m$ indica il numero di bit uguali a 1 nella maschera.
Un esempio di indirizzo è 193.185.15.199/26

Se per esempio un ISP possiede il blocco di indirizzi 128.211.0.0/16 ed avesse tre clienti:

• il cliente 1 necessita di 12 indirizzi IP
• il cliente 2 necessita di 9 indirizzi IP
• il cliente 3 necessita di 6 indirizzi IP

In questo caso l'ISP può assegnare i seguenti prefissi:

• Cliente 1: 128.211.0.16/28
• Cliente 2: 128.211.0.32/28
• Cliente 3: 128.211.0.48/29

I clienti 1 e 2 hanno prefissi diversi ma della stessa lunghezza, mentre per il cliente 3, a cui servono meno indirizzi IP, il prefisso è più lungo. I bit non utilizzati per il prefisso di rete andranno ad identificare gli host della rete di ogni cliente, oppure possono essere utilizzati per la suddivisioni in ulteriori sottoreti all'interno dell'organizzazione di ogni cliente.
Per esempio il cliente 1, che ha il prefisso 128.211.0.16/28, può usare 4 bit per assegnare indirizzi agli host.

È utile tenersi a mente alcune delle maschere più utilizzate:

Quando riceve un datagramma, un router deve decidere su quale interfaccia inoltrarlo. L'interfaccia usata dipende dall'indirizzo IP di destinazione e la corrispondenza viene identificata usando la netmask. Consideriamo la tabella di inoltro qui sotto e l'IP destinazione 200.23.19.7. Calcoliamo l'AND bit-a-bit con una maschera avente 23 bit a 1 (/23):

• 200.23.19.7 & 255.255.254.0 (/23) = 200.23.18.0 $\to$ eth1

Se consideriamo ancora la destinazione 200.23.19.7 e la nuova tabella sotto che contiene elementi con netmask diverse:

• 200.23.19.7 & 255.255.240.0 (/20) = 200.23.16.0 $\to$ OK!
• 200.23.19.7 & 255.255.254.0 (/23) = 200.23.18.0 $\to$ OK!

Il 19 si scrive come 00010011 e, dato che la maschera /23 considera la rete fino a 000100|11, quello che risulterà fuori sarà 00010000 che corrisponde a 18. Stessa cosa accade con la maschera /20, solamente che prendendo meno bit risulterà 16.

Dato che ci potrebbero essere corrispondenze multiple si utilizza la regola del prefisso più lungo e, in questo caso, il datagramma viene inoltrato usando eth1.

Se ad esempio il provider (Fly-By-Night-ISP) comunica che gli debbano essere inviati tutti i datagrammi i cui primi 20 bit di indirizzo corrispondono a 200.23.16.0/20, il resto del mondo non ha bisogno di sapere che all'interno di quel blocco di indirizzi esistono altre organizzazioni, ciascuna con la propria sottorete. L'utilizzo di un singolo prefisso per sottendere più reti viene spesso detto aggregazione di indirizzi.
Se utilizziamo /23 a sinistra della linea blu avremo tutte reti diverse, ma se invece contiamo il prefisso /20, che è più corto, prima della linea blu tutti i prefissi risulteranno uguali. Questo permette di mandare un unico messaggio ad una rete di prefisso /20, ovvero 200.23.16.0 (16 = 0001). In tal modo il router avrà un'unica regola di indirizzamento.

Mettiamo caso che un router da Internet debba inoltrare un datagramma per l'IP 200.23.19.7 o a "Fly-by-Night-ISP" oppure a "ISPs-R-Us". Per effettuare ciò, dato che ciascun ISP possiede un diverso blocco degli indirizzi, effettueranno due AND con le rispettive subnet mask contenute nei router:

• 200.23.19.7 & 255.255.240.0 (/20) = 200.23.16.0 $\to$ OK!
• 200.23.19.7 & 255.255.0.0 (/16) = 200.23.0.0 $\to$ NO MATCH

Di conseguenza il router inoltra il pacchetto a Fly-by-Night-ISP. Sarà poi compito del router di Fly-by-Night-ISP di inoltrare il pacchetto alla sottorete corretta (nelle sue tabelle ci saranno maschere /23).

Supponiamo adesso che Fly-By-Night-ISP acquisisse un altro provider chiamato ISPs-R-Us e l'Organizzazione 1 passasse sotto la sua competenza per connettersi a Internet. ISPs-R-Us però possiede il blocco di indirizzi 199.31.0.0/16, ma gli indirizzi IP dell’Organizzazione 1 non appartengono a tale blocco. Dato che rinumerere tutti i router dell'Organizzazione 1 risulterebbe un'operazione costosa ed anche inutile, perché in futuro potrebbe essere riassegnata a un'altra sottorete, di conseguenza la soluzione migliore è un'altra. Proprio per questo Fly-By-Night-ISP continua a mostrare il blocco di indirizzi 200.23.16.0/20 e ISPs-R-Us continua a mostrare 199.31.0.0/16, ma ora ISPs-R-Us mostra anche il blocco di indirizzi dell’Organizzazione 1, ovvero 200.23.18.0/23.

Dato che ora, se volessimo inviare un datagramma all'indirizzo 200.23.19.7, ci sarebbero due corrispondenze:

• 200.23.19.7 & 255.255.240.0 (/20) = 200.23.16.0 $\to$ OK
• 200.23.19.7 & 255.255.0.0 (/16) = 200.23.0.0 $\to$ NO MATCH
• 200.23.19.7 & 255.255.254.0 (/23) = 200.23.18.0 $\to$ OK

I router che dovranno inoltrare tale datagramma sceglieranno la corrispondenza con il prefisso più lungo e quindi verrà inoltrato a ISPs-R-Us all'indirizzo 200.23.18.0.

Se non ci sono corrispondenze si usa un valore di default: il default gateway. Negli host si tratta solo dell'indirizzo IP del router, mentre per i router è l'indirizzo IP di un altro router che si suppone sappia come inoltrare ulteriormente il datagramma. Nelle tabelle questa entry ha destinazione 0.0.0.0/0.
Supponiamo di voler inviare un datagramma a 193.117.8.1. Come si può notare nella tabella non ci sono corrispondenze per le prime 3 righe, mentre l'ultima riga è:

• 193.117.8.1 & 0.0.0.0 (/0) = 0.0.0.0 $\to$ OK

Per cui il datagramma verrà inoltrato sull'interfaccia eth2.

Se sono presenti più router nella stessa rete, dato che ognuno ha un indirizzo sulla propria rete ed uno sulla rete che lo interconnette agli altri, risulta difficile stabilire quello che deve gestire il datagramma in arrivo.

Per assicurarsi che venga mandato il datagramma al router giusto viene inserita un'informazioni in più nella tabella di routing, ovvero l'IP del router che si dovrà occupare di inoltrare il datagramma. Tale router viene chiamato next hope.
Gli indirizzi IP sorgente e destinazione non cambiano quando il pacchetto viene inoltrato, fatta eccezione per il NAT. Tale indirizzo non può essere messo nell'header IP perché è un processo svolto a livello di collegamento, ma una volta effettuato l'AND con la maschera so a quale indirizzo bisogna mandare il datagramma.

Il data plane (inoltro locale) si occupa di leggere la tabella e trova interfaccia e destinatario usando longest prefix matching, mentre il control plane (routing globale) popola la tabella.

In una tipica rete casalinga potremmo avere una tabella di routing del tipo:

In questo caso il router ha 3 interfacce, una sulla rete LAN di casa, una sulla rete Wireless ed una con il proprio ISP, ma tutte le interfacce sono gestite da regole di inoltro. Gli host della rete, per trasmettere qualsiasi pacchetto in Internet, lo mandano all'indirizzo 192.168.0.1 e poi sarà compito del router instradarlo correttamente.

NAT (network address translation)

La maggioranza dei $2^{3}2=4.294.967.296$ indirizzi IP è pubblica e può essere assegnata a host e raggiunta su Internet. Alcuni blocchi di indirizzi IP però sono riservati e non possono essere usati come indirizzi di destinazione in Internet, di conseguenza i router li bloccano.
Sono definiti indirizzi IP privati e si usano per costruire reti private:

• Da 10.0.0.0 a 10.255.255.255 (10.0.0.0/8)
• Da 172.16.0.0 a 172.31.255.255 (172.16.0.0/12)
• Da 192.168.0.0 a 192.168.255.255 (192.168.0.0/16)

Questi indirizzi sono riutilizzabili in tutte le reti private perché non escono dalla rete, sono sempre univoci all'interno di una rete privata e, di solito, sono assegnati dinamicamente. Ma se gli indirizzi privati hanno significato solo all’interno di una data rete, come fanno gli host con un indirizzo IP privato a mandare pacchetti verso Internet? Esistono due modi:

• Utilizzare un Proxy nel mezzo, ovvero un computer che possiede sia un indirizzo pubblico che uno privato e che media la connessione. Questo però avviene solamente per applicazioni specifiche.
• L'utilizzo del NAT invece permette a qualunque applicazione, in maniera quasi trasparente, di accedere ad Internet. Questo perché è un apparato allacciato sia alla rete privata sia ad Internet che effettua la seguente mappatura.
  

Quando gli arriva un pacchetto dalla rete interna (colonna di sinistra) copia alcune informazioni, ma ne cambia. Ad esempio come indirizzo sorgente utilizza l'IP pubblico del NAT invece che l'IP sorgente privato e come porta sorgente ne imposta un'altra. Al ritorno un pacchetto con i dati della rete esterna (colonna di destra) viene trasferito in un pacchetto con i dati della rete interna (colonna di sinistra).

Supponiamo di avere un router, con l'indirizzo 10.0.0.4 per la rete privata, che deve mediare la connessione con la rete pubblica alla quale si rivolgerà con l'unico indirizzo che vede, ovvero 138.76.29.7. Per fare ciò il router deve effettuare un network address translation.
Supponiamo che l'host 10.0.0.1 richieda una pagina web a un server, che ha porta 80, con indirizzo IP 128.119.40.186. L’host 10.0.0.1 assegna il numero di porta di origine (casuale) 3345 e invia il datagramma nella rete locale. Il router NAT riceve il datagramma, genera per esso un nuovo numero di porta di origine 5001, sostituisce l’indirizzo IP sorgente del datagramma con il proprio indirizzo IP pubblico sul lato WAN 138.76.29.7 e sostituisce il numero di porta di origine del datagramma iniziale 3345 con il nuovo numero 5001. Quando genera un nuovo numero di porta di origine, il router NAT può selezionare qualsiasi numero di porta che attualmente non si trova nella tabella di traduzione NAT e, dato che il campo numero di porta è lungo 16 bit, il protocollo NAT può supportare più di 60.000 connessioni simultanee con un solo indirizzo IP sul lato WAN relativo al router. Il NAT del router aggiunge inoltre una riga alla propria tabella di traduzione NAT.
Dato che il web server è ignaro della manipolazione subita dal datagramma in arrivo con la richiesta HTTP, risponde con un datagramma con l’indirizzo IP del router NAT come destinazione e il cui numero di porta di destinazione è 5001. Quando questo datagramma arriva al router NAT, quest’ultimo consulta la tabella di traduzione NAT usando l’indirizzo IP di destinazione e il numero di porta di destinazione per ottenere l’appropriato l’indirizzo IP (10.0.0.1) e il corretto numero di porta di destinazione (3345) del browser nella rete domestica. Il router NAT quindi cambia l’indirizzo di destinazione del datagramma (da 138.76.29.7 a 10.0.0.1) e il suo numero di porta di destinazione (da 5001 a 3345) e inoltra il datagramma nella rete domestica.

Il NAT è stato a lungo la soluzione alla mancanza di IP pubblici che a partire da IPv6 dovrebbe essere stata risolta, ma nonostante sia una soluzione controversa si continua comunque ad utilizzare perché sono presenti comunque indirizzi IPv4 ed anche per garantire un minimo di sicurezza in più (non si conosce l'IP univoco di un host). Innanzitutto viola l'architettura a livelli perché il NAT è un router e non dovrebbe né cambiare le porte né cambiare l'indirizzo di destinazione. Questo si deve tenere in considerazione anche quando si crea un'applicazione di rete perché alcune di essere, come P2P, sono vulnerabili a questo cambio dato che si attendono richieste in ingresso su numeri di porta prestabiliti. Per far si che un client possa connettersi a un server che sta dietro ad un NAT sono state proposte delle soluzioni per l'attraversamento del NAT. Alcuni esempi sono Hole punching, UPnP Internet Gateway Device Protocol, STUN ed il Port forwarding che ad esempio dice al router che tutto ciò che viene inviato sulla porta 5001 (per esempio) deve essere sempre inviato all'indirizzo privato 10.0.0.2 con porta 5001 (ma che può essere anche diversa).

Se consideriamo l'esempio precedente in cui un host vuole richiedere una pagina ad un web server, il NAT risulta l'unico modo di connettere due reti se non si controllano tutti i router (qui si suppone di non controllare A). In questo caso il pacchetto, che parte dall'host, raggiungerà senza problemi il server perché in ogni tabella c'è il next hop corretto. Il problema si presenta quando il server deve inviare un pacchetto di risposta, perché l'indirizzo di destinazione sarà 10.0.0.5 ma nel router A non si ha modo di capire dove inoltrarlo. Quindi, dato che non si ha modo di controllare A, si utilizza il NAT sul router R in modo che il traffico diretto all'IP 10.0.1.0/30 venga poi indirizzato dal router verso l'indirizzo 10.0.0.0/24, dove risiede l'host con l'indirizzo 10.0.0.5.

Indirizzi IP speciali

Ci sono alcuni indirizzi IP speciali che non vengono mai assegnati agli host, per esempio:

• Gli indirizzi che denotano "tutta la rete"
• L'indirizzo broadcast di una rete ("Directed Broadcast Address")
• L'indirizzo broadcast di rete locale ("Limited Broadcast Address")
• Questo computer
• Indirizzi di loopback
• Gli indirizzi multicast
• Gli indirizzi link-local

Indirizzi di "tutta la rete"

Gli indirizzi di tutta la rete sono usati per riferirsi al prefisso usato per una certa rete e si formano impostando l'HostID a tutti 0. Per esempio, l'indirizzo 128.211.0.16/28 indica una rete e quindi tutti i bit oltre il 28-esimo sono a 0

• ==10000000.11010011.00000000.0001==0000, quindi non si possono usare come indirizzo di destinazione.

Bisogna fare attenzione perché 128.211.0.17/28 non è un indirizzo valido per denotare una rete

• ==10000000.11010011.00000000.0001==0001, però può essere un host della rete 128.211.0.16/28

Indirizzo broadcast di una rete

Per semplificare l'invio di un pacchetto a tutti gli host di una rete, IP definisce un indirizzo broadcast (Directed Broadcast Address) specifico per quella rete. Questo tipo di pacchetti viene inoltrato dai router ed una sola coppia del datagramma viaggia in Internet finché non raggiunge la rete di destinazione e viene consegnato a tutti gli host in quella rete. Si genera usando un HostID di tutti 1, ad esempio

• ==10000000.11010011.00000000.0001==1111

Indirizzo broadcast di una rete locale

Il Limited Broadcast Address si riferisce al fatto che i datagrammi con questo indirizzo destinazione non escono mai dalla rete locale perché nessun router li inoltra. IP riserva l'indirizzo con 32 bit tutti a 1 per questo scopo

• 255.255.255.255 = 11111111.11111111.11111111.11111111

Tale indirizzo si usa quando un host si accende e deve ancora capire su che rete si trova. Finché non ha un indirizzo IP valido, IP manda datagrammi all'indirizzo broadcast di rete locale.

Questo computer

Prima di inviare datagrammi verso Internet, un host deve conoscere il proprio indirizzo IP. La pila di protocolli TCP/IP include un protocollo per l'assegnazione automatica degli indirizzi, ma anche quella richiede un IP per comunicare. Quindi, quando un host parte ("boots up") e non ha un indirizzo IP valido, imposta come IP sorgente un indirizzo di tutti 0

• 00000000.00000000.00000000.00000000

Indirizzi loopback

Si usano per testare le applicazioni di rete. Se si possiedono dei componenti che comunicano attraverso una rete, invece di farli girare su computer diversi li si fa girare sullo stesso computer attraverso indirizzi di loopback. Quando un componente invia un datagramma a un altro componente dell'applicazione il datagramma scende la pila protocollare fino al livello 3 (IP) e poi risale verso il secondo programma, senza che nessun pacchetto lasci il computer.
IP riserva il prefisso 127.0.0.0/8 per il loopback. L'HostID è irrilevante perché i datagrammi sono comunque gestiti come sopra, ma spesso si usa l'HostID 1 $\to$ 127.0.0.1

Indirizzi multicast

Servono per inviare i pacchetti a un gruppo di host ed i router si occupano di creare le copie necessarie. In IPv4 gli indirizzi riservati al multicast iniziano con 1110 e vanno da 224.0.0.0 a 239.255.255.255. Il multicast in Internet però è poco supportato e spesso non è nemmeno implementato dai router che ne bloccano il traffico.

Se per esempio un host vuole inviare un pacchetto ad un gruppo di host in altre reti locali e non ci fosse il multicast, dovrebbe inviare 3 pacchetti in tre collegamenti diversi e potrebbe capitare che lo stesso link, perché magari in comune, possa essere usato più volte per gli stessi dati.

Con multicast il mittente dovrà inviare un solo pacchetto e sarà poi compito dei router decidere quando effettuare una copia.

Indirizzi IP link-local

Sottorete riservata per consentire le comunicazioni quando un host non riesce a "trovare" un indirizzo IP, perché magari è impostato per cercarlo automaticamente e nessuno gli risponde. Ogni host sceglie a caso un IP dalla sottorete 169.254.0.0/16 e questo gli permette di comunicare tra loro nella sottorete anche se li mantiene isolati dall'esterno.

Indirizzi IP per i router

Ad ogni router si assegnano due o più indirizzi IP, ovvero almeno un indirizzo IP per interfaccia. Infatti un router, per definizione, connette multiple reti e dato che ogni rete ha un prefisso unico, per parlare su quella rete serve un indirizzo IP con quel prefisso (e solo quello).
Gli indirizzi IP però non contrassegnano un host ma un'interfaccia di rete, quindi una connessione logica tra un host e una rete. Di conseguenza un sistema con molte interfacce (un router) avrà necessariamente diversi indirizzi IP.

Per esempio il router 1 ha una porta che con un indirizzo di rete compatibile (131.108.99.5) si immette sulla rete ethernet 131.108.0.0/16. Stessa cosa per l'interfaccia 223.240.129.2 che è compatibile con le rete 223.240.129.0/24. Il router 2 è collegato, come per il router 1, alla rete Wi-Fi Net e quindi ha lo stesso prefisso di rete, solo che cambia l'HostID. Il router poi si interfaccia con la WAN (78.0.0.0/8) e quindi l'interfaccia manterrà gli 8 bit per l'indirizzo di rete, mentre gli altri tre li riserverà per gli host.

Un router può collegare diversi indirizzi IP ad un'interfaccia di rete. Il router sotto possiede un'indirizzo IP per ciascuna delle 4 sottoreti, ma ne possiede anche un quinto perché così può inoltrare i pacchetti anche al router sopra, il quale si interfaccia verso l'esterno (153.18.125.1). Il router sotto quindi riceverà i datagrammi dalle 4 sottoreti ed utilizzerà una sola interfaccia di rete (192.168.5.1) per direzionarli all'interfaccia del router sopra (192.168.5.2).

Disposizione logica

Tutte le reti private, collegate allo switch, avranno come default gateway uno tra i 4 indirizzi e poi il router passerà il pacchetto all'interfaccia 192.168.5.1 mediante lo stesso cavo (non ha importanza se il cavo è lo stesso). I pacchetti quindi verranno inviati al router mediante l'interfaccia 192.168.5.2 che li manderà verso Internet.

Disposizione fisica

Per essere spedito anche il datagramma IP deve essere incapsulato in un frame di livello 2, il quale avrà il suo header e nel campo dati il datagramma IP. Un datagramma con IP sorgente 111.111.111.111 ed IP destinazione 222.222.222.222 viene inserito in un frame che contiene l'indirizzo sorgente e destinazione del livello 2. Tale indirizzo è il MAC address, ovvero una stringa di 48 bit rappresentata come 12 cifre esadecimali. Ogni interfaccia di rete ne ha uno che è diverso dagli altri. Per formare il pacchetto in maniera completa non basta conoscere l'indirizzo IP del destinatario ma anche l'indirizzo MAC, che viene recuperato dall'ARP (address resolution protocol).

ARP

Se l'host destinatario di un datagramma IP si trova sulla mia rete voglio inviargli il pacchetto direttamente e questo accade se il prefisso di rete (NetID) del destinatario è uguale al mio. Se l'indirizzo IP del destinatario è C, il mittente invia in broadcast una richiesta per ottenere il MAC address che corrisponde all'indirizzo IP C. La richiesta raggiunge tutti gli host sulla rete, ma solo l'host con indirizzo IP C risponde e fornisce l'indirizzo MAC.

Questo avviene solo per comunicazioni punto-punto sulla stessa rete. Anche se gli indirizzi IP sorgente e destinazione non cambiano lungo il percorso, gli indirizzi MAC cambiano ad ogni salto, ma in ogni caso non si cerca mai l'indirizzo MAC di un host su un'altra rete perché nessun messaggio di richiesta MAC passerà il limite della propria rete. In questo caso si passa sempre il pacchetto a un router, il cui indirizzo MAC deve però essere trovato mediante ARP.

Se l'host $A$ deve inviare un pacchetto a $B$ lo dovrà prima inviare al router $R$ e, per essere sicuro di inviarlo proprio al router $R$, utilizzerà il protocollo ARP per chiedere la corrispondenza tra l'indirizzo IP dell'interfaccia di destinazione (111.111.111.110) e l'indirizzo MAC di quell'interfaccia (E6-E9-00-17-BB-4B). Dopo il router si occuperà di inoltrarlo a $B$.
Dato che i messaggi ARP sono broadcast non vengono inviati molto spesso per evitare di inondare la rete di messaggi. Proprio per questo viene utilizzato in una singola rete.

Formato del messaggio ARP

I messaggi ARP sono interpretati come dati di livello 3 e quindi vengono incapsulati nel payload del frame di livello 2. Nell'header del frame c'è un campo "Type" (protocol address type) che identifica il tipo di dati trasportati. Se tale campo contiene il valore 2054 (0x806) significa che i dati sono un messaggio ARP.

ARP caching

Per evitare di inviare un messaggio ARP per ogni datagramma, si mantengono in memoria cache le risposte ARP ricevute. Se si riceve una nuova risposta per una certa corrispondenza tra indirizzo IP e indirizzo MAC, questa sovrascrive la precedente e le corrispondenza più vecchie vengono cancellate periodicamente (ogni 30 secondi circa). La cache viene consultata sempre prima di inviare una richiesta.

Proxy ARP

Un proxy ARP è una macchina che restituisce un indirizzo MAC facendo le veci di un host che si trova su una rete diversa.
Per esempio un router gestisce accesso alla rete locale sulla sinistra, ma fornisce indirizzi, della stessa sottorete di sinistra, anche alla rete di destra.
Se un host sulla rete di sinistra vuole comunicare con uno degli host della rete di accesso a destra (e viceversa) il router di accesso risponde con il proprio MAC ai messaggi ARP. Il messaggio è di tipo ARP perché entrambi gli host si trovano sulla stessa sottorete e quindi è lecito per l'hosy 192.167.0.2 chiedere il MAC associato all'indirizzo 192.168.0.252 per esempio, ma in questa configurazione le due reti non sono connesse perché hanno un router nel mezzo e quindi il router spaccia il proprio MAC address come quello del reale destinatario. Il router poi capisce che i pacchetti non sono in realtà per lui ed instaura una regola al suo interno per inoltrarli al destinatario corretto. Di conseguenza gli host non appartengono a due sottoreti diverse e quindi non è necessario instaurare una regola di routing.

ICMP

ICMP (Internet control message protocol) è un protocollo utilizzato da host e router per scambiarsi informazioni a livello di rete ed è utilizzato principalmente per notificare errori alla sorgente di un datagramma, ma è anche un ottimo strumento per gestione e manutenzione delle reti.
ICMP è spesso considerato parte di IP, ma dal punto di vista dell’architettura si trova esattamente sopra IP dato che i i suoi messaggi vengono trasportati nel payload dei datagrammi IP. Di conseguenza, come i segmenti TCP o UDP, se un host riceve un datagramma IP, che specifica ICMP come protocollo di livello superiore, allora effettua il demultiplexing dei contenuti del datagramma. In pratica IP ha bisogno di ICMP per segnalare errori e ICMP ha bisogno di IP per trasportare i messaggi.
L'header è semplice:

Il campo type identifica il tipo di messaggio.

Source quench è usato per fare un po' di controllo della congestione, anche se alla fine se ne occupa comunque TCP, però a livello 3 è praticamente inutilizzato tale controllo.

Ci sono due classi di messaggi:

• quelli usati per segnalare errori, come ad esempio Time Exceeded e Destination Unreachable
• quelli usati per recuperare informazioni, come ad esempio Echo Request e Echo Reply

Echo Request/Reply sono utilizzati dal comando ping. Quando un host riceve un echo request, restituisce un messaggio ICMP con gli stessi dati presenti nella richiesta (definizione di echo).

I messaggi ICMP funzionano come qualunque pacchetto IP e sono inviati senza particolari priorità, in pratica sono il payload del pacchetto IP. Se un messaggio ICMP genera un errore non viene inviato nessun messaggio di errore, questo per evitare di congestionare Internet con troppi messaggi di errore.

Dato che ICMP nasce nel livello 3 il payload non contiene altre informazioni e viene incapsulato nel pacchetto IP che contiene anche altre informazioni.

ICMP è lo strumento che viene utilizzato per ping e traceroute.
Ping è un meccanismo che sfutta echo request + echo reply e verifica l'esistenza di un percorso verso la destinazione, misurandone l'RTT. Quando parte il messaggio di echo request fa partire un cronometro e quando riceve il messaggio di echo reply lo ferma, restituendoci il valore di RTT.
Traceroute è un programma diagnostico che fornisce una misura del ritardo dalla sorgente al router lungo i percorsi internet punto-punto verso la destinazione. Quando si scopre l'indirizzo IP del primo router si calcola anche un RTT. Si inviano datagrammi IP con TTL sempre maggiore (1, 2, 3m ...). Si parte con TTL = 1 e, dato che il primo router decrementa TTL a 0, scarta il pacchetto ed invia un messaggio "Time Exceeded" con il proprio indirizzo IP. Quindi ora siamo a conoscenza dell'indirizzo IP di dove si è fermato il pacchetto e del RTT, quindi li salviamo. Viene inviato nuovamente il pacchetto verso la destinazione con TTL = 2, il primo router decrementa il TTL a 1 ed il secondo a 0. Sarà quindi il secondo router a rispondere con il proprio indirizzo IP e con il RTT. Si ripetono questi passaggi finché non si è raggiunta la destinazione. Questo procedimento è utilizzato per rilevare il percorso seguito dal pacchetto ma, essendo un protocollo troppo distribuito non si ha un pieno controllo, per cui il pacchetto potrebbe seguire percorsi diversi. Se tutti i router collaborassero e trasmettessero il proprio indirizzo IP si saprebbe con esattezza il percorso, ma non tutti sempre lo fanno.

4.4 Il protocollo IP (segue)

4.4.1 DHCP

Consente di assegnare un indirizzo IP a un host quando questo si accende, in maniera del tutto automatica, permettendo di liberare indirizzi quando non vengono utilizzati, affinché possano essere assegnati ad altri host. Questo permette di supportare più utenti, però non superiori al massimo numero di hostID che si possono avere in una sottorete. DHCP viene spesso detto protocollo plug-and-play o zero-conf proprio perché permette di automatizzare la connessione degli host alla rete. Infatti è molto usato nelle reti wireless, dove gli host arrivano e se ne vanno con estrema frequenza dalla rete e quindi sarebbe impossibile gestire manualmente tutti gli indirizzi.

DHCP clien-server scenario

Quando un nuovo host si connette a una rete e richiede un indirizzo avvengono 4 fasi.

Individuazione del server DHCP

Il primo compito di un host appena collegato è l’identificazione del server DHCP con il quale interagire e tale operazione è svolta utilizzando un messaggio DHCP discover, che è opzionale, che il client invia in un pacchetto UDP attraverso la porta 67 (in questo caso). L'host però non conosce ancora l’indirizzo IP della rete alla quale è collegato, ne tantomeno l'indirizzo di un server DHCP per quella rete. Di conseguenza il client DHCP crea un datagramma IP contenente il messaggio DHCP con l'indirizzo IP di destinazione broadcast 255.255.255.255 e l’indirizzo IP sorgente 0.0.0.0, cioè “questo host”, e lo inoltra al suo livello di collegamento che si occuperà di inviare il frame in broadcast a tutti i nodi collegati alla sottorete.

Offerta del server DHCP

Un server DHCP (di solito un software che gira in un altro host o in un router) risponde con un messaggio DHCP offer, che è opzionale e che viene inviato in broadcast a tutti i nodi della sottorete, usando di nuovo l’indirizzo IP broadcast 255.255.255.255. Tale messaggio è di broadcast perché in una sottorete possono essere presenti diversi server DHCP e quindi il client dovrebbe avere la possibilità di scegliere tra le diverse "offerte" disponibili. In ogni messaggio di offerta server è presente l'ID di transazione del messaggio di identificazione ricevuto, l’indirizzo IP proposto al client, la maschera di sottorete e la durata della concessione (lease time) dell’indirizzo IP (il lasso di tempo durante il quale l’indirizzo IP sarà valido).

Richiesta DHCP

Il client appena collegato sceglierà tra le offerte dei server e risponderà con un messaggio DHCP request, che riporta i parametri di configurazione.

Conferma DHCP

Il server risponde al messaggio di richiesta DHCP con un messaggio DHCP ACK, che conferma i parametri richiesti.

I messaggi DHCP discover e DHCP offer sono opzionali perché servono nel caso in cui il client non conosca l'indirizzo del server DHCP.

L'indirizzo IP fornito da DHCP rimane valido per un tempo limitato e, quando il prestito finisce, il server rimette l'indirizzo IP in un insieme di indirizzi utilizzabili. A quel punto il client può decidere di cambiare indirizzo IP o negoziare un'estensione del prestito. Normalmente DHCP approva tutte le estensioni per permettere ad un host di continuare a funzionare senza interruzioni, ma per varie ragioni un server potrebbe negare l'estensione di un lease ed in tal caso il client deve smettere di usare l'IP. Anche se il client impostasse un indirizzamento statico con quell'IP, il server DHCP conserva comunque l'associazione con il MAC e non lo farebbe funzionare.
Dato che DHCP usa UDP non è un protocollo di trasporto affidabile, ma è comunque progettato per essere robusto a perdite e duplicati. Di conseguenza, se non riceve nessuna risposta dal server, l'host ritrasmette la richiesta. Se invece arriva una risposta duplicata, l'host ignora la copia extra. Quando il client trova un server DHCP ne memorizza l'indirizzo in una cache. Per evitare richieste simultanee, se una richiesta non va a buon fine, si aspetta un ritardo scelto casualmente prima di inviare di nuovo una richiesta.

Formato dei messaggi DHCP

• OP: specifica se si tratta di una risposta o una richiesta
• HTYPE e HLEN specificano il tipo di hardware e la lunghezza dell'indirizzo di livello 2
• FLAGS specifica se il mittente può ricevere broadcast o risposte dirette
• HOPS specifica quanti server hanno inoltrato la richiesta
• TRANSACTION IDENTIFIER si usa per far corrispondere le richieste alle risposte
• SECOND ELAPSED dice quanto tempo è passato da quando l'host si è attivato (utilizzato per l'estensione del prestito dell'IP).
• Dimensioni fissate (eccetto per il campo OPTION che può trasmettere più informazioni)

I campi rimanenti trasportano le informazioni richieste

• YOUR IP ADDRESS si usa per trasportare l'indirizzo IP offerto al client DHCP
• Il server mette il proprio indirizzo IP e nome nei campo SERVER IP ADDRESS e SERVER HOST NAME
• ROUTER IP ADDRESS contiene l'indirizzo IP di un router di default, il DHCP lo usa per comunicare a un host il default gateway.

Il DHCP può restituire anche:

• il nome e l'indirizzo IP di un server DNS
• la maschera di rete per suddividere il prefisso dal suffisso
• altre informazioni (es il percorso di un file con le istruzioni per configurare un host all'avvio)

In una rete locale, l'indirizzo IP dei messaggi DHCP è quello di broadcast 255.255.255.255 e quindi non escono dalla rete locale perché di default i router non li inoltrano. Ma dato che il pacchetto DHCP è dentro al livello 3, i router possono essere configurati per inoltrare i messaggi DHCP, identificati dal campo tipo, a un server noto. Se il router non lo facesse bisognerebbe implementare un server DHCP in ogni sottorete.

Se non c'è nessun DHCP o si disabilita il client DHCP di un host e si configura l'indirizzo IP manualmente, oppure il client DHCP imposta un indirizzo tipo link-local 169.254.0.0/16. Per impostare un indirizzo si seguono i seguenti passi:

1. si sceglie casualmente un indirizzo tra 169.254.0.1 e 169.254.255.254
2. si cerca, se esiste, un'interfaccia di rete con questo indirizzo tramite una risoluzione ARP
3. se la si trova, si torna al punto 1
4. altrimenti, l'host si tiene l'indirizzo scelto al punto 1

Questo consente agli host di parlarsi almeno sulla rete locale.

4.4.2 Il viaggio di un pacchetto

DHCP, UDP, IP e Ethernet

Uno studente (Bob) collega il proprio laptop a un cavo Ethernet connesso allo switch Ethernet della scuola, che a sua volta è connesso al router della scuola, per poter scaricare una pagina web, come ad esempio la home page di www.google.com.
Il router della scuola è connesso a un ISP, in questo esempio Comcast.net, che fornisce il servizio DNS alla scuola e quindi il server DNS risiede nella rete Comcast piuttosto che nella rete della scuola. Assumiamo che il server DHCP sia eseguito nel router, come avviene spesso.

Dal momento che senza indirizzo IP Bob non può fare niente, la prima azione che intraprende il suo laptop è quella di eseguire il protocollo DHCP per ottenere un indirizzo IP, insieme ad altre informazioni, dal server DHCP locale.

1. Il sistema operativo del laptop di Bob crea un messaggio DHCP request e inserisce questo messaggio in un segmento UDP, con porta a di destinazione 67 (server DHCP) e porta sorgente 68 (client DHCP). Il segmento UDP viene quindi inserito all’interno di un datagramma IP con Il segmento UDP viene quindi inserito all’interno di un datagramma IP.

2. Il datagramma IP contenente il messaggio di richiesta DHCP è quindi posto in un frame Ethernet che ha indirizzo MAC di destinazione FF:FF:FF:FF:FF:FF in modo che il frame venga inviato in broadcast a tutti i dispositivi connessi allo switch, tra i quali si spera ci sia un server DHCP. L'indirizzo MAC della sorgente del frame è quello del laptop di Bob, ovvero 00:16:D3:23:68:8A.

3. Il frame Ethernet broadcast contenente la richiesta DHCP è il primo frame inviato dal laptop di Bob allo switch Ethernet. Lo switch invia in broadcast il frame in entrata a tutte le porte in uscita, compresa la porta che lo connette al router.

4. Il router riceve il frame broadcast Ethernet che contiene la richiesta DHCP sulla sua interfaccia con indirizzo MAC 00:22:6B:45:1F:1B e il datagramma IP è estratto dal frame Ethernet. L’indirizzo IP di destinazione del datagramma broadcast indica che tale datagramma IP dovrebbe essere elaborato dai protocolli di livello superiore su questo nodo e quindi sul payload del datagramma (un segmento UDP) viene effettuato un demultiplexing verso UDP e il messaggio di richiesta DHCP viene estratto dal segmento UDP. Ora il server DHCP ha il messaggio di richiesta DHCP.

5. Supponiamo ora che il server DHCP in esecuzione sul router possa allocare indirizzi IP nel blocco CIDR 68.85.2.0/24 e in questo esempio tutti gli indirizzi IP usati all’interno della scuola sono contenuti nel blocco di indirizzi di Comcast. Supponiamo che il server DHCP allochi l’indirizzo 68.85.2.101 al laptop di Bob. Il server DHCP crea un messaggio DHCP ACK contenente tale indirizzo IP, insieme all’indirizzo IP del server DNS, l’indirizzo IP del gateway di default (68.85.2.1) e il blocco della sottorete (68.85.2.0/24 o equivalentemente la maschera di rete). Il messaggio DHCP è posto all’interno di un segmento UDP, inserito in un datagramma IP, a sua volta posto in un frame Ethernet che ha come indirizzo MAC sorgente quello dell’interfaccia del router sulla rete domestica (00:22:6B:45:1F:1B) e come indirizzo MAC di destinazione quello del laptop di Bob (00:16:D3:23:68:8A).

6. Il frame Ethernet contenente il messaggio DHCP ACK è inviato, in unicast, dal router allo switch. Dato che lo switch è in grado di auto-apprendere e ha precedentemente ricevuto dal laptop di Bob un frame Ethernet contenente la richiesta DHCP, sa di dover inoltrare un frame indirizzato a 00:16:D3:23:68:8A solo alla porta di uscita verso il laptop di Bob.

7. Il laptop di Bob riceve il frame Ethernet contenente il messaggio DHCP ACK, estrae dal frame Ethernet il datagramma IP, estrae dal datagramma IP il segmento UDP ed estrae dal segmento UDP il messaggio DHCP ACK. Il client DHCP di Bob memorizza il suo indirizzo IP e quello del server DNS ed installa l'indirizzo del gateway di default nella sua tabella di inoltro. Di conseguenza il laptop di Bob invierà tutti i datagrammi il cui indirizzo di destinazione è all’esterno della sua sottorete 68.85.2.0/24 al gateway di default. A questo punto il laptop di Bob ha inizializzato le sue componenti di rete ed è pronto a iniziare a elaborare la lettura della pagina web. Bisogna ricordare che solo gli ultimi due passi DHCP sono realmente necessari.

DNS e ARP

Quando Bob scrive l'URL di www.google.com nel suo browser web esso inizia il processo creando una socket TCP che verrà usata per inviare una richiesta HTTP a www.google.com. Per creare tale socket, il laptop di Bob deve conoscere l'indirizzo IP e per questo viene utilizzato il protocollo DNS che fornisce il servizio di traduzione da nome a indirizzo IP.

8. Il sistema operativo del laptop di Bob crea un messaggio di DNS query inserendo la stringa “www.google.com” nella sezione riguardante la richiesta del messaggio DNS. Tale messaggio DNS è quindi posto all’interno di un segmento UDP con porta di destinazione 53 (server DNS). Il segmento UDP è quindi posto all’interno di un datagramma IP con indirizzo IP di destinazione 68.87.71.226 (l’indirizzo del server DNS restituito nel messaggio DHCP ACK al passo 5) e indirizzo IP sorgente 68.85.2.101.

9. Il laptop di Bob quindi inserisce il datagramma contenente il messaggio di richiesta DNS in un frame Ethernet che verrà inviato, con indirizzo a livello di collegamento, al gateway della rete della scuola di Bob. Tuttavia il laptop di Bob, pur conoscendo l’indirizzo IP del gateway della scuola (68.85.2.1) tramite il messaggio DHCP ACK del passo 5, non ne conosce l’indirizzo MAC, per ottenere il quale deve usare il protocollo ARP.

10. Il laptop di Bob crea un messaggio di ARP query con indirizzo IP di destinazione 68.85.2.1 (il gateway di default), pone il messaggio ARP all’interno di un frame Ethernet con indirizzo di destinazione broadcast FF:FF:FF:FF:FF:FF e invia il frame Ethernet allo switch, che lo consegna a tutti i dispositivi connessi compreso il gateway.

11. Il router gateway riceve il frame contenente il messaggio di interrogazione ARP sull’interfaccia della rete della scuola e scopre che l’indirizzo IP 68.85.2.1 nel messaggio ARP corrisponde all’indirizzo IP della sua interfaccia. Il gateway prepara quindi un messaggio ARP reply che indica che il suo indirizzo MAC 00:22:6B:45:1F:1B corrisponde all’indirizzo IP 68.85.2.1. Pone il messaggio di risposta ARP in un frame Ethernet con l’indirizzo di destinazione 00:16:D3:23:68:8A (il laptop di Bob) e invia il frame allo switch che lo consegna al laptop di Bob.

12. Il laptop di Bob riceve il frame contenente il messaggio di risposta ARP ed estrae l’indirizzo MAC del gateway (00:22:6B:45:1F:1B) dal messaggio di risposta ARP.

13. Il laptop di Bob può ora indirizzare il frame Ethernet contenente l’interrogazione DNS all’indirizzo MAC del gateway. Si noti che il datagramma IP in questo frame ha indirizzo IP di destinazione 68.87.71.226 (il server DNS), mentre il frame ha indirizzo di destinazione 00:22:6B:45:1F:1B (il router gateway). Il laptop di Bob invia questo frame allo switch che lo consegna al gateway.

Instradamento intra-dominio al server DNS

14. Il gateway riceve il frame ed estrae il datagramma IP contenente l’interrogazione DNS. Il router ricerca l’indirizzo di destinazione di tale datagramma (68.87.71.226) e determina sulla base della sua tabella di inoltro che il datagramma dovrebbe essere inviato al router più a sinistra nella rete Comcast. Il datagramma IP è posto all’interno di un frame appropriato per il collegamento che connette il router della scuola al router Comcast più a sinistra e poi il frame viene trasmesso.

15. Il router più a sinistra nella rete Comcast riceve il frame, estrae il datagramma IP, esamina l’indirizzo di destinazione del datagramma (68.87.71.226) e determina l’interfaccia di uscita sulla quale inoltrare il datagramma al server DNS sulla base della sua tabella di inoltro, che è stata riempita dal protocollo intra-dominio di Comcast e dal protocollo inter-dominio di Internet, BGP.

16. Infine, il datagramma IP contenente l’interrogazione DNS arriva al server DNS, che estrae il messaggio di interrogazione DNS, ricerca il nome www.google.com nel suo database DNS e trova il record di risorsa DNS che contiene l’indirizzo IP (64.233.169.105) di www.google.com (assumendo che sia nella cache del server DNS). Si ricordi che i dati nella cache sono originati dal DNS server autoritativo di google.com. Il server DNS scrive un messaggio DNS reply contenente la corrispondenza tra il nome dell’host e l’indirizzo IP e lo pone in un segmento UDP, poi pone tale segmento all’interno di un datagramma IP indirizzato al laptop di Bob (68.85.2.101). Questo datagramma verrà restituito al router della scuola attraverso la rete Comcast e da qua al laptop di Bob tramite lo switch Ethernet.

17. Questo datagramma verrà restituito al router della scuola attraverso la rete Comcast e da qua al laptop di Bob tramite lo switch Ethernet. Ora il laptop di Bob è finalmente pronto a contattare il server www.google.com.

Interazione client-server: TCP e HTTP

18. Il laptop di Bob, che ora ha l'indirizzo IP di www.google.com, può creare la socket TCP che verrà usata per inviare un messaggio di HTTP GET a www.google.com. Quando Bob crea la socket TCP, per prima cosa il laptop di Bob effettua l’handshake a tre vie con TCP su www.google.com e poi crea un segmento TCP SYN con porta di destinazione 80 (per HTTP). Poi pone il segmento TCP all’interno di un datagramma IP con indirizzo IP di destinazione 64.233.169.105 (www.google.com), pone il datagramma all’interno di un frame con indirizzo MAC di destinazione 00:22:6B:45:1F:1B (il gateway) e invia il frame allo switch.

19. I router nelle reti della scuola, di Comcast e di Google inoltrano il datagramma contenente TCP SYN a www.google.com, usando ognuno la propria tabella di inoltro, come spiegato nei passi da 14 a 16. Si ricordi che le righe delle tabelle di inoltro dei router che governano la procedura di inoltro dei pacchetti sul collegamento inter-dominio tra Comcast e Google sono determinate dal protocollo BGP.

20. Infine il datagramma contente il TCP SYN arriva a www.google.com. Il messaggio TCP SYN viene estratto dal datagramma e viene effettuato un demultiplexing verso la socket di benvenuto associata alla porta 80 e viene creata una socket di connessione per la connessione TCP tra il server HTTP di Google e il laptop di Bob. Un segmento TCP SYNACK viene generato, posto all’interno di un datagramma indirizzato al laptop di Bob e infine inserito in un frame appropriato al collegamento tra www.google.com e il primo router.

21. Il datagramma contenente il segmento TCP SYNACK viene inoltrato attraverso le reti di Google, Comcast e della scuola per arrivare infine alla scheda Ethernet del laptop di Bob. Viene effettuato un demultiplexing del datagramma all’interno del sistema operativo alla socket TCP creata al passo 18, che entra nello stato di connessione.

22. Con la socket sul laptop di Bob finalmente pronta per trasmettere byte a www.google.com, il browser di Bob crea il messaggio HTTP GET contenente l’URL da leggere. Quindi il messaggio HTTP GET viene scritto nella socket e diventa il payload di un segmento TCP, il quale viene posto in un datagramma, inviato e consegnato a www.google.com come descritto dei passi da 18 a 20.

23. Il server HTTP di www.google.com legge dalla socket TCP il messaggio HTTP GET, crea un messaggio di risposta HTTP, pone il contenuto della pagina web richiesta nel corpo del messaggio di risposta HTTP che invia alla socket TCP.

24. Il datagramma contenente il messaggio di risposta HTTP viene inoltrato attraverso le reti di Google, Comcast e della scuola al laptop di Bob. Il browser di Bob legge dalla socket la risposta HTTP, estrae il codice HTML della pagina web dal corpo della risposta HTTP e finalmente visualizza la pagina web.

IPv6

La ragione iniziale per la quale è stato progettato IPv6 era che lo spazio di indirizzamento IP a 32 bit stava cominciando a esaurirsi, ma i progettisti ne approfittarono anche per apportare delle migliorie a questo nuovo protocollo.

Formato dei datagrammi IPv6

• Indirizzamento esteso: IPv6 aumenta la dimensione dell'indirizzo IP da 32 a 128 bit, in modo che gli indirizzi IP diventino praticamente inesauribili. IPv6 supporta, oltre agli indirizzi unicast e multicast, anche indirizzi anycast che consentono di consegnare un datagramma a un qualsiasi host all’interno di un gruppo.
• Intestazione ottimizzata di 40 byte: Alcuni campi IPv4 sono stati eliminati o resti opzionali. L'intestazione a 40 byte e a lunghezza fissa consente una più rapida elaborazione dei datagrammi IP, mentre una nuova codifica delle opzioni ne consente l’elaborazione in maniera più flessibile.
• Etichetta dei flussi (flow label): Il concetto di flusso non è ben definito, ma consente l’etichettatura di pacchetti che appartengono a flussi particolari per i quali il mittente richiede una gestione speciale.
• Versione: Campo a 4 bit che identifica il numero di versione IP
• Classe di traffico (priority): Campo a 8 bit che identifica la priorità dei datagrammi che fanno parte dello stesso flusso o provenienti da specifiche applicazioni.
• Etichetta di flusso: Campo a 20 bit utilizzato per identificare un flusso di datagrammi.
• Lunghezza del payload: Campo a 16 bit, trattato come un intero senza segno, che indica il numero di byte nel datagramma IPv6 che seguono l’intestazione a lunghezza fissa di 40 byte.
• Intestazione successiva (next header): Campo che identifica il protocollo di livello 4 a cui verranno consegnati i contenuti (campo dati) del datagramma, per esempio TCP o UDP. Utilizza gli stessi valori del campo protocollo nell’intestazione IPv4.
• Limite di hop: Il contenuto di questo campo è decrementato di 1 da ciascun router che inoltra il datagramma, in modo che il datagramma venga eliminato quando il suo valore raggiunge 0.
• Indirizzi sorgente e destinazione: Campi a 128 bit.
• Dati: Payload che viene passato al protocollo specificato nel campo di intestazione successiva quando il datagramma IPv6 raggiunge la sua destinazione.

Altri cambiamenti rispetto a IPv4:

• Checksum dell’intestazione: Dato che i protocolli Internet a livello di trasporto (per esempio TCP e UDP) e di collegamento (per esempio Ethernet) calcolano un loro checksum, si è ritenuto che fosse una funzionalità ridondante.
• Opzioni: Rimosso dall'header ma consentito al di fuori indicando un valore apposito nel campo "Next header".
• Frammentazione/riassemblaggio: Non consente né frammentazione né riassemblaggio sui router intermedi, ma soltanto da sorgente o destinazione. Se un router riceve un datagramma IPv6 che risulta troppo grande per essere inoltrato sul collegamento di uscita, non fa altro che eliminarlo e inviare al mittente un messaggio d’errore ICMP “Pacchetto troppo grande” (Packet Too Big). Il mittente può quindi inviare nuovamente i dati, con una dimensione di datagramma IP inferiore. Dato che frammentazione e riassemblaggio sono operazioni che consumano tempo, farle svolgere ai sistemi periferici rende più rapido l’instradamento IP all’interno della rete.

Transizione da IPv4 a IPv6

Nonostante i nuovi sistemi IPv6 siano retrocompatibili, ossia sono in grado d’inviare, instradare e ricevere datagrammi IPv4, i sistemi IPv4 esistenti non sono in grado di gestire datagrammi IPv6. Dato che non tutti i router possono essere aggiornati simultaneamente è necessario che IPv4 e IPv6 coesistano finché la transizione non sarà completa. L'approccio alla transizione da IPv4 a IPv6 è noto come tunneling, la cui idea di base è che i datagrammi IPv6 possano viaggiare come dati incapsulati dentro datagrammi IPv4.

Supponiamo che due nodi IPv6, $B$ ed $E$, vogliano utilizzare datagrammi IPv6, ma siano connessi da un insieme di router intermedi IPv4, che chiameremo tunnel. Il Nodo B, al lato di invio del tunnel, prende l’intero datagramma IPv6 arrivato da A, lo pone nel campo dati di un datagramma IPv4 e lo indirizza al nodo $E$. Il primo nodo del tunnel a cui viene inviato il datagramma, ovvero $C$, lo instraderà come farebbe per qualsiasi altro datagramma, ignaro che questo contenga un datagramma IPv6 completo. Lo stesso faranno gli altri router IPv4 del tunnel. Il nodo IPv6 sul lato di ricezione del tunnel riceverà il datagramma IPv4, determinerà che questo ne contiene uno IPv6 osservando che il valore del campo numero di protocollo nel pacchetto IPv4 è 41 (che indica la presenza di un datagramma IPv6), lo estrarrà e lo instraderà esattamente come se l’avesse ricevuto da un nodo IPv6 adiacente.

Indirizzi IPv6

La lunghezza degli indirizzi IPv6 è di 128 bit, per cui si possono ottenere $3.4\cdot {10}^{38}$ indirizzi. Dato che la notazione decimale puntata, usata per IPv4, sarebbe troppo lunga, gli indirizzi IPv6 si scrivino in notazione esadecimale. Ogni gruppo di 4 bit è scritto come una cifra (da 0 a 9, da $a$ ad $f$) e sono presenti 32 cifre esadecimali per ogni indirizzo, quindi 8 gruppi di 4 cifre.

Esempio: 2a03 : 2880 : f108 : ...

• 2a03:
  • 0010 (2)
  • 1010 (a)
  • 0000 (0)
  • 0011 (3)

Un indirizzo completo può essere qualcosa del genere

• 2a03 : 2880 : f108 : 0083 : face : b00c : 0000 : 25de

Per accorciarlo si omettono gli zeri all’inizio di ogni campo e si scrivono gli zeri consecutivi con un solo “0”

• 2a03 : 2880 : f108 : 0083 : face : b00c : 0000 : 25de diventa
• 2a03 : 2880 : f108 : 83 : face : b00c : 0 : 25de

I gruppi consecutivi di zeri si rappresentano con un $::$

• 2a03 : 2880 : f108 : 0000 : 0000 : 0000 : 0000 : 25de diventa
• 2a03 : 2880 : f108 : : 25de

Ma il $::$ si può usare una sola volta e, se ci sono più gruppi di zeri, lo si usa sul gruppo più lungo.

I prefissi e le sottoreti funzionano esattamente come nel CIDR di IPv4, inclusa la / per indicare i bit a 1 nella maschera:

• IPv4: 192.168.0.0/24
  • Da 192.168.0.0
  • A 192.168.0.255
• IPv6: 2a03 : 2880 : f108 : 83 : : /64
  • Da 2a03 : 2880 : f108 : 83 : 0 : 0 : 0 : 0
  • A 2a03 : 2880 : f108 : 83 : ffff : ffff : ffff : ffff

Tipica composizione di un indirizzo

Indirizzi speciali

• Non specificato o “questo computer” $\to$ $::$ /128 (tutti 0)
• Loopback (localhost) $\to$ $::$ 1/128 (tutti 0 con un 1 alla fine)
• Indirizzo riservato per quelli che incapsulano IPv4 in IPv6 $\to$ $::$ ffff : 0 : 0/96
  • Quindi $::$ ffff : xxyy : zzww, dove xx.yy.zz.ww sono i bit dell'indirizzo IPv4 espresso in esadecimale.
  • IPv4 = 193.175.55.16 = c1.af.37.10
  • IPv6 = $::$ ffff : c1af : 3710
• Multicast: ff00 $::$ /8
• Link-local unicast: fe80 $::$ /10
  • 169.254.0.0/16 in IPv4
  • Utilizzato per consentire il networking di rete locale senza router o DHCP.

4.5 Protocolli di instradamento

Fino ad ora abbiamo visto reti, indirizzi IP, router, regole di inoltro e tabelle di inoltro che ci erano fornita da "qualcuno". Esistono due possibili approcci:

• Controllo locale: l’algoritmo di instradamento viene eseguito su ogni singolo router, all’interno del quale vengono effettuate sia le funzioni di inoltro (piano dei dati) che quelle di instradamento (piano di controllo). Ogni router ha una componente di instradamento che comunica con le componenti di instradamento degli altri router per calcolare la propria tabella di inoltro.
  

• Controllo logicamente centralizzato: il controller logicamente centralizzato calcola e distribuisce le tabelle di inoltro che devono essere utilizzate da ogni router.
  

Nel controllo centralizzato il controller interagisce con l’agente di controllo (CA, control agent) in ogni router tramite un protocollo che configura e gestisce la tabella dei flussi del router, mentre nel controllo locale gli agenti di controllo non interagiscono direttamente tra di loro e non partecipano attivamente all’elaborazione della tabella di inoltro.

I protocolli di instradamento (routing algorithm) hanno l'obiettivo di determinare "buoni" percorsi da un mittente a un destinatario, attraverso una rete di router. Il percorso è una sequenza di router attraversati da un datagramma per giungere all’host di destinazione. Un "buon percorso" è definito secondo qualche metrica, come ad esempio il costo più basso, il più veloce o il meno congestionato. Tipicamente, il percorso migliore è quello che ha costo minimo (che in verità possono essere più di uno a ugual costo).

Grafo

Per formulare i problemi di instradamento si utilizza un grafo, che è un modello che astrae la rete. Un grafo $G=(N,E)$ è un insieme $N$ di nodi (router), $N=$ {$u,v,w,x,y,z$}, e un insieme $E$ di archi (collegamenti fisici), $E=$ {$(u,v),(u,x),(v,x),(v,w),(x,w),(x,y),(w,y),(w,z),(y,z)$}, dove ciascun arco collega una coppia di nodi $N$. Ad ogni arco è anche associato un valore che ne indica il costo, che in genere può essere qualsiasi cosa come:

• numero di salti
• banda del link (proporzionale al costo del collegamento)
• Inverso della banda del link (banda elevata ha un costo minore perché trasmette più velocemente)
• congestione
• dipende dall'algoritmo utilizzato

Per ogni arco $(x,x^{\prime })$ tra i nodi $x$ e $x^{\prime }$ denotiamo con $c(x,x^{\prime })$ il suo costo, per esempio$c(w,z)=5$. Se la coppia $(x,x^{\prime })$ non appartiene a $E$, poniamo $c(x,x^{\prime })=+\mathrm{\infty }$.
Il costo del percorso è uguale alla somma del costo di tutti i link: $cost(x_1,x_2,...,x_p)=c(x_1,x_2)+c(x_2,x_3)+...+c(x_{p-1},x_p)$ ed il compito dell'algoritmo di routing è di trovare il percorso di costo minimo.

Tipi di algoritmi di routing

Gli algoritmi di instradamento sono classificati come centralizzati o decentralizzati.

Algoritmo di instradamento centralizzato (globale)

Un algoritmo di instradamento centralizzato calcola il percorso a costo minimo tra una sorgente e una destinazione avendo una conoscenza globale e completa della rete. Tale algoritmo riceve in ingresso tutti i collegamenti tra i nodi e i loro costi prima di effettuare il calcolo, il quale viene svolto in un controller logicamente centralizzato o replicato in ognuno dei router della rete. Gli algoritmi con informazioni di stato globali sono detti algoritmi link-state (LS o con stato del collegamento).

Algoritmo di instradamento decentralizzato

In un algoritmo di instradamento decentralizzato nessun nodo possiede informazioni complete sul costo di tutti i collegamenti di rete. I router conoscono soltanto gli altri router a cui sono collegati ed il costo dei collegamenti verso di essi. Poi, attraverso un processo iterativo e lo scambio di informazioni (pacchetti) con i router adiacenti, un nodo gradualmente calcola il percorso a costo minimo verso una destinazione o un insieme di destinazioni (ognuno lo scambia con il vicino, il quale lo scambia con il vicino e così via). Tali algoritmi decentralizzati vengono definiti algoritmi distance vector (DV o con vettore delle distanze). Tali algoritmi decentralizzati, che prevedono scambi interattivi tra router vicini, possono essere implementati nei piani di controllo nei quali i router interagiscono direttamente, mentre hanno poco senso nel caso di controllo centralizzato.

Algoritmo di instradamento statico

Negli algoritmi di instradamento statici i percorsi cambiano molto raramente, spesso come risultato di un intervento umano (es una modifica manuale di una tabella di inoltro di un router).

Algoritmo di instradamento dinamico

Negli algoritmi di instradamento dinamici le rotte cambiano più frequentemente in seguito ad aggiornamenti periodici o a causa di cambiamenti nel costo o nella topologia dei link.

4.5.1 Link state: Dijkstra

L'algoritmo di Dijkstra è bastato sul link state e quindi la topologia di rete e tutti i costi dei collegamenti sono noti. Questo si ottiene facendo inviare in broadcast a ciascun nodo pacchetti sullo stato (quali link sono attivi, quali nodi ci sono ed il costo dei link) dei suoi collegamenti e quindi tutti i nodi hanno le stesse informazioni. Come output di questo algoritmo si ha il percorso a costo minimo da un nodo a tutti gli altri nodi, ovvero la tabella di inoltro. L'algoritmo è iterativo perché dopo $k$ iterazioni si conosce il percorso a costo minimo verso almeno $k$ destinazioni.

Notazione:

• $c(x,y)$: costo del link da $x$ a $y$, se è uguale a $\mathrm{\infty }$ allora i nodi non sono collegati
• $D(v)$: costo minimo del percorso dal nodo origine verso la destinazione $v$
• $p(v)$: predecessore di $v$ lungo il cammino dall'origine a $v$
• $N^{\prime }$: insieme di nodi per cui il cammino a costo minimo è stato già determinato

Esempio 1

Tabella di inoltro per il nodo $u$

Esempio 2

Tabella di inoltro per il nodo $u$

La complessità dell'algoritmo con una rete di $n$ nodi (senza contare l'origine) è il numero di calcoli che occorre fare, nel caso peggiore, per determinare i percorsi a costo minimo dall'origine a tutte le destinazioni. Nella prima iterazione bisogna cercare su tutti gli $n$ nodi per determinare quello $w\notin N^{\prime }$ avente il costo minimo. Nella seconda iterazione dobbiamo controllare $n$ – 1 nodi per determinare il costo minimo, nella terza iterazione i nodi sono $n$ – 2 e così via. Il numero totale di nodi da cercare in tutte le iterazioni è n(n + 1)/2, quindi la complessità dell'algoritmo di Dijkstra è di $O(n^2)$. Alcune implementazioni più efficienti hanno complessità di $O(n\ast log(n))$.

L'algoritmo può oscillare se vengono definiti male i costi, come ad esempio mettere il costo uguale alla quantità di traffico trasportata dal link. Partiamo da una quantità di traffico di 1 in $D$, e in $C$ ed 1 in $B$.
Nella successiva iterazione dell’algoritmo, il nodo $C$ determina, sulla base dei costi dei collegamenti indicati nel primo passaggio, che il percorso in senso orario verso $A$ ha costo 1, mentre il percorso in senso antiorario ha costo pari a 1 + e. Pertanto, il percorso a costo minimo di $C$ verso $A$ ora è quello in senso orario. Analogamente, $B$ determina che il proprio nuovo percorso a costo minimo verso $A$ è quello in senso orario, il che porta ai risultati sui costi mostrati nella seconda immagine. Quando l’algoritmo viene nuovamente eseguito, $B$, $C$ e $D$ instradano tutti il proprio traffico su percorsi in senso antiorario. La volta successiva che l’algoritmo viene eseguito, tutti i nodi x, y e z instradano il loro traffico in senso orario.

4.5.2 Internet, AS, OSPF

Internet è formata da moltissime sottoreti, ognuna di proprietà di qualche entità (ISP, operatori di rete, aziende, ecc...). Idealmente ogni rete dovrebbe essere amministrativamente autonoma, quindi gli amministratori di rete sono liberi di configurarla come vogliono e sono liberi di scegliere l'algoritmo di routing che preferiscono, ma dovrebbe essere comunque capace di collegarsi a tutte le altre reti. Oltretutto bisogna trovare un modo per ridurre la complessità del calcolo dei percorsi nelle reti di grandi dimensioni perché archiviare le informazioni di instradamento in ogni router diventerebbe insostenibile sia dal punto di vista della memoria dei router, sia perché verrebbe generato un enorme traffico.
Questi problemi possono essere risolti organizzando i router in sistemi autonomi (AS, autonomous system), ovvero gruppi di router sotto lo stesso controllo ammnistrativo. Ogni AS è identificato da un numero (RFC 1930), ed i numeri di AS sono assegnati centralmente dai registri regionali ICANN.
Vengono distinti tra protocolli di instradamento dentro ad ogni AS (Intra-AS) routing e tra AS diversi (Inter-AS) routing. L'insieme di questi protocolli consente di raggiungere qualunque host su internet.

OSPF (Open Shortest Path First)

OSPF è un protocollo di routing basato su link state che raccoglie le informazioni sullo stato dei link e dissemina pacchetti con questo stato, assumendo che la topologia della rete sia nota a tutti i router. Applica poi l'algoritmo di Dijkstra per calcolare i percorsi migliori e formare le tabelle di inoltro. Per trasmettere queste informazioni utilizza datagrammi IP, quindi non si serve di nessun livello di trasporto e, come ICMP, mette le informazioni dentro al payload del datagramma IP. I pacchetti di aggiornamento dei link vengono inviati all'indirizzo multicast 224.0.0.5.
Implementa tre procedure:

• Protocollo di "Hello": messaggi di mantenimento che controllano i link funzionanti e quindi verificano quali altri nodi sono vicini.
• Protocollo di “Exchange”: utilizzato per informare i vicini che si sono appena “conosciuti” sulla topologia della rete nota al momento.
• Protocollo di “Flooding”: informa tutti i router di un cambio nello stato dei link

Flooding

Il flooding viene effettuato in maniera controllata, quindi tutti i messaggi ricevuti da un router su un'interfaccia vengono inviati a tutte le altre interfacce. Questo avviene in due modi diversi:

• Se esistono connessioni dirette (reti /30) ad altri router viene inviato un messaggio per ogni link (sinistra).
• Se invece sono presenti sottoreti appartenenti ad un dominio di broadcast, viene mandato un solo messaggio per ogni dominio di broadcast (destra).

L'OSPF gerachico viene utilizzato in reti con molti router e presenta due livelli: dorsale ("backbone") e reti di area. Questa suddivisione consente di far girare all'interno di ogni area (dorsale compresa) i messaggi di aggiornamento dei link e quindi non c'è bisogno di informare tutta la rete perché sarà il router di bordo che avrà il compito di gestire i messaggi provenienti dalle aree. Se ad un router di bordo sono collegate più sottoreti esso può indicare in un unica tabella tutti i pesi e gli stati per arrivare a tutte le reti di quell'area.
Il router di bordo di un AS lo collega agli altri ma, dato che non si può usare OSPF in reti eccessivamente grandi, si utilizza il protocollo BGP.

OSPF è un protocollo a link state e quindi l'unica cosa che influenza la scelta dei percorsi è il costo dei link che sono dati in input. Ma se io volessi decidere il percorso che deve seguire il traffico, come faccio a indurre OSPF a farlo? Per esempio se so che il traffico che entra nella mia rete da un certo router è quasi tutto destinato ad un’altra rete specifica, vorrei che OSPF scegliesse il percorso che desidero io tra i due punti.
Per fare ciò si utilizza la "traffic engineering", che consiste nel manipolare il costo dei link per fare in modo che il percorso ottimo che risulta sia quello che voglio io.

4.5.3 Distance vector: Bellman-Ford

L'instradamento con distance vector è un algoritmo distribuito perché ogni nodo di rete conosce i propri vicini ed il costo dei link verso questi vicini, ma non tutta la topologia di rete. La presenza di altri nodi posizionati oltre i propri vicini viene notificata con dei messaggi e quindi un nodo apprenderà la presenza di questi vicini da tali messaggi. L'algoritmo di base utilizzato per questo tipo di routing è Bellman-Ford.
Sono i router a far girare l'algoritmo ed ognuno di loro conosce la rete connessa alle proprie interfacce e ai loro NetID. Nonostante noi utilizziamo gli ID dei router per indicare le destinazioni, in realtà le tabelle riportano indirizzi IP.

Notazione:

• $N$: insieme di vicini $\to N_x$ è l'insieme di vicini del router $x$.
• $R$: tabella di inoltro $\to R_x$ è la tabella di inoltro del router $x$.
  • $R[d]$: riga della tabella di inoltro per la destinazione $d$ che comprende tre cose
    • $R[d]$.cost: costo per raggiungere $d$
    • $R[d]$.nexthop: nodo verso cui inoltrare il pacchetto per procedere verso $d$
    • $R[d]$.time: tempo al quale il percorso è stato impostato ed è usato per invalidare percorsi troppo vecchi
• $D$: vettore con tutte le distanze $\to D_x$ è il distance vector del router $x$
  • $D_x=$[(d, $R_x[d]$.cost) tale che d $\in R_x$]
• I costi dei link si chiamano anche distanze o metriche

distance vector slide

distance vector libro

Bellman-Ford: esempio

Inizialmente ciascun router scrive nella propria tabella di routing i costi che conosce. $Y$ manda un aggiornamento agli altri nodi e questo consente ad $X$ di trovare una rotta migliore verso $Z$, stessa cosa per il router $Z$ che trova una rotta migliore verso $X$, entrambi confrontando con i valori già in loro possesso.

Il router $X$ manda il proprio distance vector sia ad $Y$ che a $Z$, che però non aggiornano la propria tabella perché non otterrebbero alcun vantaggio.

Anche $Z$ manda il proprio distance vector verso $X$ ed $Y$, ma anche in questo caso non cambia nulla.

Un altro esempio di DV

Ogni nodo inserisce nella propria tabella di routing la lista dei nodi che conosce.

Il router $D$ invia il distance vector ai suoi vicini.

Questo permetterà sia al router $E$ che al router $C$ di conoscere il percorso per raggiungersi a vicenda.

A questo punto è il router $E$ ad inviare il distance vector ai suoi vicini $A$, $B$ e $D$.

Questo permetterà ai router $A$, $B$ e $D$ di aggiornare i costi di alcuni percorsi.

Anche $C$ manda il suo messaggio di distance vector ai vicini $B$ e $D$.

Questo permette sia a $B$ che a $D$ di aggiornare la propria tabella.

Dopo aver scambiato tutti i messaggi si arriverà ad un punto in cui tutti i router possiedono i costi minimi verso gli altri nodi.

Count-to-infinity

Consideriamo questo esempio in cui il router $D$ è direttamente connesso a NTW_1.

Poniamo il caso in cui si rompa il collegamento tra $A$ e $D$. Il router $A$ dice al router $B$ che attraverso di sé la rete non è raggiungibile, ma il router $B$ afferma che in realtà lui può raggiungere la rete NTW_1 con costo 3. Il router $A$ quindi aggiorna la sua tabella e la prossima volta raggiungerà la rete NTW_1 passando per il router $B$, con costo 4.

Le tabelle così si aggiornano finché non ci si rende conto che il percorso con costo minore di $B$ verso la rete NTW_1 è di 11, mentre per $A$ è di 12. Questo è un problema perché finché i costi non sono definiti la rete non risulta attiva.

Soluzioni per il count-to-infinity

Un modo per abbassare il tempo di convergenza è di impostare un massimo numero di hop per la propagazione dei DV, ad esempio 15.

Split Horizon

Protocollo che quando un nodo manda aggiornamenti a un vicino, omette le rotte apprese da quel vicino. Nell’esempio precedente, $B$ non avrebbe incluso (NTW_1, 3) nel DV inviato ad $A$, perché lo aveva appreso proprio da $A$. Di conseguenza avrebbe messo un costo non raggiungibile verso la rete NTW_1 passando per $A$ e si sarebbe cercato un percorso alternativo verso $D$.

Poison reverse

Finché un nodo $x$ raggiunge un nodo $z$ attraverso $y$, $x$ comunica ad $y$ che $Dx(z)=\mathrm{\infty }$. Nell'esempio precedente $B$ includerebbe la riga (NTW_1, $\mathrm{\infty }$) nel DV inviato ad $A$, perché $A$ è il nodo attraverso cui B raggiunge NTW_1. In pratica $B$ sta dicendo ad $A$ che non può andare a $D$ passando per $B$.

Se i costi dei link cambiano, le buone notizie (costi minori del link) viaggiano in fretta, mentre le cattive notizie (costi più alti del link) viaggiano lentamente. Per esempio, se si fa girare l'algoritmo DV nella topologia sotto, nel caso in cui il costo del link $x-y$ diminuisca da 4 a 1 l'aggiornamento verrà propagato velocemente, mentre se il costo del link $x-y$ dovesse aumentare da 4 a 60 l'aggiornamento verrebbe propagato più lentamente.

Split horizon e poisoned reverse: funzionano sempre?

Questi due metodi non funzionano sempre perché la loro efficacia dipende dall'ordine con il quale i messaggi vengono inviati.

Supponiamo che si rompa il link con costo 1 tra $W$ e $Z$ e, dato che i nodi operano in modo distribuito, $X$ potrebbe inviare il proprio messaggio in qualunque momento. Il messaggio viene inviato con split horizon e dato che si suppone che $X$ abbia imparato da $Y$ che esiste una rotta di costo 3 verso $W$, $X$ non dirà nulla su $W$ ad $Y$ per il concetto dello split horizon (non mando al nodo che mi ha insegnato una rotta un aggiornamento sul mio costo verso quella rotta). Mentre $Z$, che non ha imparato nulla da $Y$ perché era direttamente collegato a $W$, riceve l'aggiornamento dei costi di tutti i percorsi da $X$.
Questo fa creare un ciclo perché $X$ andrà a $W$ attraverso $Y$, $Y$ andrà a $W$ attraverso $Z$ e $Z$ andrà a $W$ attraverso $X$.

Dato che $Z$ ha costo 6 per raggiungere $W$, siccome $Y$ per raggiungere $W$ deve passare per $Z$ ed il costo verso di lui è 1, aggiorna la propria tabella a 7. Dato che $Z$ ha imparato da $X$ come si raggiunge $W$, per una proprietà dello split horizon non gli invia aggiornamenti.

Anche $X$ aggiorna la tabella sulla base dei DV che gli invia $Y$.

E questo si ripete per un pel po' di volte.

Questo ciclo di aggiornamenti terminerà quando si capirà che $X$ va a $W$ direttamente con costo 100, $Y$ va a $W$ attraverso $X$ e $Z$ va a $W$ attraverso $Y$.

Se ci sono link con il costo molto diverso questo potrebbe metterci molto a propagarsi, soprattutto se il costo diventa molto diverso in seguito ad una variazione del costo dei link.

4.5.4 RIP (Routing Information Protocol)

RIP è un protocollo per routing Intra-AS che implementa il distance vector, molto semplice da implementare e gestire ma ha una convergenza lenta perché ha diversi router collegati. Inoltre permette la propagazione fino ad un certo numero massimo di hop. Per limitare il tempo di convergenza si limita la dimensione della rete. È incluso in UNIX BSD dal 1982.
Il costo dei link è il numero di hop ed al massimo questo costo è 15, mentre se il costo è di 16 indica un costo infinito (irraggiungibilità). Un singolo hop potrebbe avere comunque un costo > 1, quindi si può favorire un link piuttosto che un altro. Ogni 30 secondi, o se cambiano le tabelle di routing, RIP invia un distance vector (DV) che viene chiamato RIP advertisement. Ogni messaggio contiene un elenco comprendente fino a 25 sottoreti di destinazione all’interno dell’AS e la distanza del mittente rispetto a ciascuna di queste sottoreti.
Si usa UDP con porta 520 e indirizzo multicast 224.0.0.9.

RIP: esempio

Quando $A$ manda una propria notifica, per esempio indicando che si può raggiungere $Z$ attraverso di lui e passando per $C$ con costo 4, $D$ aggiorna la propria tabella di routing. Di conseguenza ora $D$ può raggiungere $Z$ con un costo di 5 e passando per $A$ invece che per $B$.

Se un router non riceve notizie dal suo vicino per 180 s la rotta scade ed il collegamento verso il nodo adiacente viene considerato guasto. RIP quindi modifica la tabella di instradamento locale e propaga l’informazione mandando annunci ai router vicini tramite i DV. I vicini inviano nuovi messaggi se la loro tabella d’instradamento è cambiata e poi l’informazione che il collegamento è fallito si propaga su tutta la rete, Per evitare i loop, RIP utilizza Poisoned reverse (impostando il costo verso quella rotta alla distanza infinita = 16 hop),

La tabella di instradamento viene aggiornata da un processo di sistema operativo Linux chiamato routed (demoni sono quei programmi eseguiti in background), dove route è il programma che trova le rotte e routed è il programma che continua ad eseguirsi in memoria per aggiornare continuamente le rotte. Questo processo esegue RIP, ossia mantiene le informazioni d’instradamento e scambia messaggi con i processi routed nei router vicini. Poiché RIP viene implementato come un processo a livello di applicazione, può inviare e ricevere messaggi su una socket standard e utilizzare un protocollo di trasporto standard, ovvero UDP. Quando i messaggi arrivano al router destinatario, questi faranno girare l'algoritmo di bellman-ford e aggiorneranno le tabelle di inoltro su ciascuno dei propri sistemi.

Confronto tra algoritmi link state e distance vector

Complessita dello scambio messaggi

LS: con $n$ nodi ed $E$ link vengono inviati una quantità di messaggi proporzionale ad $n\cdot E$, ovvero $O(nE)$.

DV: i messaggi sono inviati solo ai vicini e quindi ci sono meno messaggi, però il tempo di convergenza dipende

Velocità di convergenza

LS: l'algoritmo di complessità O(n2) richiede O(nE) messaggi, ma ci possono essere oscillazioni (che però dipendono dal costo che è stato scelto male).

DV: dipende perché si potrebbero generare cicli oppure c'è il problema del count-to-infinity.

Robustezza: che succede se un router si rompe?

LS: i nodi potrebbero comunicare costi sbagliati per i link, ma ogni nodo gestisce la propria tabella indipendentemente e quindi tutto dipende se il costo del link è stato scelto correttamente.

DV: i nodi potrebbero comunicare costi sbagliati per i percorsi generando cicli e finché tale ciclo non viene corretto, di solito con molti cicli di propagazione dei DV fra i router, gli errori si propagano attraverso la rete perché i pacchetti possono essere rimpallati tra due router che se li mandano l'un l'altro mentre cercano di capire che la rotta da seguire è in realtà un'altra.

4.6 BGP

Fino ad ora sappiamo come stabilire regole di inoltro usando protocolli di routing internamente ad un AS (es. OSPF, RIP), come gestire gli indirizzi IP ed eseguire gli inoltri (es. CIDR, longest prefix matching, …) e che in un AS esistono router di bordo, che connettono l’AS con il resto di Internet. Quello che manca è far parlare i router di bordo tra loro per realizzare questa connessione tra diversi AS.

Ricordiamo che un AS è un insieme di router ed altri sistemi di rete che si trovano sotto la stessa amministrazione, per esempio un network operator che controlla una porzione di indirizzi/traffico/flussi di Internet. Vi sono molteplici livelli di AS (tier one, ..., customers) e sono presenti interconnessioni tra gli AS per lo scambio di informazioni.

Inter-AS networking

Gli AS comunicano tra loro per condividere info di raggiungibilità ed ogni AS decide autonomamente i propri punti di ingresso e di uscita e può decidere di condividere informazioni con alcuni vicini, ma non con altri. Al mondo vi sono più di 60.000 AS interconnessi.

I Transit AS sono AS che non condividono conoscenza sulla propria rete, ma fanno solo da tramite.

Le occorrenze della tabella di inoltro corrispondenti a destinazioni interne all’AS vengono determinate dal protocollo di instradamento intra-AS, mentre quelle esterne all'AS sono determinate da BGP, che di fatto è l'unico protocollo standard per comunicare informazioni di raggiungibilità per le reti. In BGP i pacchetti non vengono instradati verso uno specifico indirizzo, ma piuttosto verso prefissi CIDR che rappresentano una sottorete o una collezione di sottoreti. Con BGP una destinazione potrebbe avere la forma 138.16.68/22, che include 1024 indirizzi IP, quindi le occorrenze delle tabelle di inoltro hanno forma ($x,I$) dove $x$ è un prefisso di rete e $I$ è un numero di interfaccia del router.
BGP è un Path Vector Protocol, ovvero un algoritmo intermedio tra il DV e il LS che aggiunge le informazioni strettamente necessarie sui percorsi annunciati senza avere la complessità associata al Link State dove è necessario conoscere l'intera topologia della rete.
Il principio chiave di BGP è la libertà amministrativa per ogni AS che

• Può decidere se publicizzare info di raggiungibilità per le proprie reti interne oppure no
• Può decidere di ritrarre la raggiungibilità di qualunque propria rete
• Può decidere offrire o meno transito verso altri AS in ogni momento

Ogni AS ha un certo numero di router detti «BGP speaker» che possono parlare tra loro attraverso una connessione TCP. Una volta interconnessi, due BGP speaker possono scambiarsi informazioni di raggiungibilità. Le informazioni condivise includono non solo la raggiungibilità di un certo prefisso, ma anche il percorso per raggiungerlo.

Interconnessioni tra AS

• Client - Provider: Il client paga il provider per ottenere raggiungibilità
• Provider - Client: Il provider viene pagato dal client per fornirgli raggiungibilità
• Peer: Due nodi hanno una relazione di peering nel momento in cui condividono tutte le proprie conoscenze di raggiungibilità

Policies

Le interconnessioni tra AS sono controllate da contratti e le policies controllano ciò che sono abilitato a condividere con un certo vicino e cosa no. Le Ingress Policies sono politiche applicate alle rotte che voglio importare nel mio sistema, mentre le Egress Policies sono politiche applicate alle rotte prima che vengano esportate.

BGP ha raggiunto la sua quarta versione nel 2006. La struttura base di BGP è data da una macchina a stati finiti ed il funzionamento del protocollo è dettato dallo stato in cui ci si trova. Già nel 1994 BGP prevedeva l’utilizzo di policies e filtri, mentre l'RFC 4271 dà solamente delle indicazioni generali su come il protocollo deve funzionare. Ogni sviluppatore ha poi creato la propria versione, in grado di interoperare con le altre.

Best Path BGP

Il best path in BGP è diverso dal Best Path di OSPF o RIP, in cui si preferiva il percorso più breve o comunque con costo minore. Il concetto di “preferito” in BGP è vago e dipende principalmente dalle policy degli AS. Un Best Path può variare in base anche ad un solo cambiamento nelle policy di un singolo AS che si trova sul percorso verso la destinazione.

Ogni speaker BGP condivide solamente il proprio best path per raggiungere una destinazione e se decide di ignorare certi percorsi (come AS3 poco fa), questi non potranno mai diventare best path per quella destinazione, e non verranno mai condivisi. I best path vengono solitamente installati nella routing table del router che fa da speaker BGP, ma non è detto che il best path BGP sia il percorso più veloce.

Messaggi

BGP utilizza 4 messaggi:

• Open: usato per aprire una nuova connessione con un altro nodo BGP
• Notification: usato per condividere errori
• KeepAlive: usato per mantenere attiva la connessione
• Update: usato per inoltrare conoscenza

Open

Usato per aprire una connessione BGP.
Se l’OPEN message viene accettato, viene inviato un messaggio KEEPALIVE di conferma e dopo la ricezione del KEEPALIVE, la connessione viene considerata aperta. L’hold time è una proposta che si scambiano i due BGP speaker riguardo al tempo di validità della rotta e viene utilizzato il minore. Una connessione BGP può essere rifiutata a causa dell’hold timer. Il BGP identifier è l'indirizzo IP identificativo dello speaker, uguale per tutte le interfacce BGP dello speaker.

Notification

In base al tipo di errore sono presenti 6 Error codes, mentre ci sono 20 Error subcodes in base a dove avviene l'errore.

Keepalive

I messaggi keepalive devono essere inviati in modo tale da non lasciar scadere l’hold timer che è stato scelto per la connessione. Possono essere disattivati impostando un Hold Timer di 0s e se l'header BGP risulta senza contenuti (19 Byte), tale messaggio è di keepalive.

Update

Contengono informazioni di raggiungibilità ed attributi correlati. I messaggi di update sono i responsabili per la disseminazione delle informazioni, le quali possono essere di due tipi:

• Additive: portano informazioni di raggiungibilità riguardanti nuovi percorsi
• Sottrattive: rimuovono percorsi per raggiungere una destinazione

Withdraw

Un withdraw è l’azione di rimozione di una rotta. All’interno di un pacchetto di update vi è una sezione apposita per le rotte che vengono cancellate e si effettua un withdraw quando non vi è più nessun percorso disponibile verso un certo AS.

Update + Withdraw

Nel caso in cui un nodo BGP conoscesse un percorso alternativo per raggiungere una rotta, potrebbe decidere di rimuovere la rotta precedente, utilizzare il nuovo percorso e condividerlo.

Implicit Withdraw

Permette di non inviare un pacchetto di withdraw seguito da uno di update, ma solamente uno di “aggiornamento” del percorso migliore.

Facebook disaster

Il 4 Ottobre 2021 Facebook non è stato raggiungibile. Alle 15:40 c'è stato un picco di aggiornamenti nelle rotte di Facebook. Un comando di routine per controllare lo stato della dorsale di trasporto dati di Facebook innesca dei WITHDRAW ed il sistema, per un bug, non ha fermato il WITHDRAW delle rotte. I server DNS disabilitano i messaggi BGP se non sono in grado di comunicare e questo ha portato alla completa disconnessione. Oltre a ciò, i tool di diagnostica erano parzialmente compromessi ed un collegamento remoto non era disponibile. Per risolvere il problema bisognava quindi resettare tutto manualmente sui server, operazione né semplice né immediata.

Aggregazione delle rotte

Per poter risparmiare informazioni, all’interno dei pacchetti generalmente le rotte vengono aggregate, si perde però precisione nel percorso.

Filtri

I filtri controllano ciò che entra e ciò che esce e possono esserci filtri specifici per ogni connessione BGP: Ingress filters ed Egress filters.
Possono essere generici, per esempio "Non lasciar passare nulla che contenga AS129" oppure possono essere molto precisi (si può arrivare a filtrare su qualsiasi campo dei singoli pacchetti). Un pacchetto che non supera i filtri viene scartato.

Routing information Base (RIB)

BGP sostanzialmente utilizza 3 tabelle per le rotte:

• ADJ_RIB_IN: contiene le rotte che state accettate in ingresso ed è usato per valutare percorsi alternativi.
• Routing Table: contiene i best path attuali.
• ADJ_RIB_OUT: contiene le rotte che hanno superato i filtri in uscita e che devono essere condivise.

Quando riceve un pacchetto di UPDATE costruttivo viene valutato dai filtri in ingresso. Superati i filtri in ingresso, le rotte ivi contenute vengono aggiunte alla ADJ_RIB_IN ed il best path per la destinazione viene rivalutato in base alla ADJ_RIB_IN aggiornata. Nel caso in cui il best path fosse variato allora aggiorna la routing table, aggiorna ADJ_RIB_OUT ed inoltra i cambiamenti ai vicini.
Quando invece riceve un pacchetto di UPDATE con WITHDRAW viene sempre valutato dai filtri in ingresso. Ma questa volta superati i filtri in ingresso, le rotte ivi contenute vengono rimosse dalla ADJ_RIB_IN ed il best path per la destinazione viene rivalutato in base alla ADJ_RIB_IN aggiornata. Anche qui, nel caso in cui il best path fosse variato, viene aggiorna la routing table, ADJ_RIB_OUT e vengono inoltrati i cambiamenti ai vicini.

Negli anni BGP si è evoluto molto attraverso nuovi IETF RFC e se qualcuno volesse produrre la propria versione di un router BGP-compliant da zero, dovrebbe almeno includere circa 30 parametri tecnicamente “opzionali” ma di fatto richiesti (es AS communities, RFD, MRAI settings, Extended Communities).

Riassumento

Gli AS di Internet si interconnettono condividendo informazioni di raggiungibilità, formano un grafo gerarchico e possono essere di solo transito. Ogni AS è autonomo e può avere molteplici punti di ingresso e uscita. Il Best Path di BGP è policy-driven, ed è ottimo secondo le politiche commerciali e di traffic engineering degli operatori, non secondo le metriche di performance. BGP è un protocollo path vector (condivide anche il percorso per raggiungere una destinazione), può inserire molteplici filtri a livelli differenti della catena decisionale del protocollo ed è un protocollo vasto e con moltissime sfaccettature.
Gli ISP inoltre possono discriminare informazioni che non portano guadagni sufficienti.