Architettura di un router.

Componenti interni di un router

Dopo aver esaminato i compiti e i servizi offerti dal livello Rete, si vuole esaminare la funzione di instradamento svolta dai router, cioè i pacchetti entranti su un canale devono essere ripetuti verso il corretto canale che permette loro di raggiungere la destinazione. L'operazione di smistamento è anche detta commutazione. In un router si possono trovare quattro componenti principali.

Porte di input. Una porta di input si colloca al livello fisico del modello di riferimento, essa è la terminazione di un canale. La porta di input svolge anche compiti del livello 2, necessari per cooperare con il livello 2 residente all'altro estremo del canale. Il compito principale svolto sulla porta di input è la consultazione della tabella di instradamento: dal pacchetto entrante viene letto l'indirizzo di destinazione e si individua la porta di uscita verso cui spostare il pacchetto. Lo spostamento del pacchetto avviene tramite un commutatore interno. I pacchetti di servizio (ad esempio quelli che trasportano le informazioni sullo stato dei canali) vengono smistati dalla porta di ingresso al processore di routing. Notare che il termine porta si riferisce ad un componente fisico (un registro) collegato al canale; non lo si confonda con il termine porta associato al socket di una applicazione di rete.
Commutatore interno. Il commutatore interno, simile ad un deviatore, collega fisicamente le linee della porta di input alle linee della porta di output su cui dovrà essere inviato il pacchetto.
Porte di output. Una porta di output memorizza i pacchetti ricevuti dal commutatore per trasmetterli sul canale di output ed applicare a questi pacchetti i processi di livello 2 e livello 1. Un canale è bidirezionale, quindi ogni canale del router ha sia la porta di input che la porta di output.
Processore di routing. Il processore di routing esegue i protocolli di routing, gestisce la consultazione delle tabelle di instradamento e aggiorna le tabelle di instradamento.

L'operazione di Forwarding coinvolge una porta di input, il commutatore e una porta di output ed è implementata nell'hardware del dispositivo. Il motivo per cui questa funzione non è svolta dal software può essere giustificato con il seguente esempio. Con una velocità del canale di 10 Gbps un datagramma di 64 byte, cioè 512 bit, dura 51.2 ns. La porta di input ha solo 51.2 ns per elaborare un datagramma prima che ne arrivi un altro. Se il router ha N porte, l'elaborazione dei datagrammi deve avvenire N volte più velocemente. Non è possibile realizzare un software che operi a tale velocità.

Mentre l'hardware si occupa di smistare i pacchetti da una porta di input ad una porta di output, una CPU esegue le funzioni di controllo del router, cioè esegue gli algoritmi di instradamento, in conseguenza delle variazioni di stato dei canali (attivo o non).

Si consideri l'analogia tra la rete a datagramma e una rete autostradale. Si supponga che all'uscita del casello ci sia una rotatoria che immette su più strade e che, prima che una vettura affronti l'incrocio, è richiesta una certa elaborazione, ad esempio deve pagare il pedaggio, leggere il cartello indicatore delle possibili direzioni ed immettersi sulla strada che lo porta verso la sua destinazione. Per uscire dal casello il veicolo deve immettersi nel flusso di veicoli che ha già impegnato la rotatoria da altre direzioni. L'accesso alla rotatoria è analogo alla porta di input del router (compresa l'operazione di determinare la strada di uscita dalla rotatoria), la rotatoria è analoga al commutatore e la strada che porta verso la destinazione corrisponde alla porta di output. Questa analogia permette di individuare il collo di bottiglia del flusso. Se la frequenza di arrivo delle auto al casello è elevata e l'operatore al casello è lento si forma una coda di auto. Ma anche se il servizio al casello fosse veloce, potrebbe succedere che le auto sono costrette ad impegnare la rotatoria a bassa velocità o ancora potrebbero essere dirette tutte verso la stessa destinazione. Queste problematiche si ripresentano anche nei router.

Elaborazione dell'input

La funzione della porta di input è di implementare i livelli fisico e collegamento per il canale a cui è collegata. La funzione di ricerca svolta sulla porta di input è l'operazione principale del router. Mentre il pacchetto si trova in questa area, il router legge l'indirizzo di destinazione del pacchetto e cerca nella tabella di instradamento la porta di output su cui, tramite il commutatore interno, spostare il pacchetto. La tabella di instradamento è costruita ed aggiornata dal processore di routing. Una copia della tabella è condivisa da ciascuna porta di input. La tabella di instradamento viene copiata dal processore di routing sulla porta di input. In questo modo, avendo una copia della tabella di instradamento, le decisioni di Forwarding possono essere prese senza coinvolgere il processore di routing, che altrimenti costituirebbe un collo di bottiglia del flusso. Con la tabella di Forwarding la ricerca è semplificata: si deve cercare la corrispondenza più lunga tra il prefisso di rete e i primi bit dell'indirizzo di destinazione. Ma a velocità di trasmissione dell'ordine del Gbps questa ricerca deve concludersi entro pochi ns. Quindi, non solo bisogna affidare all'hardware la ricerca, ma sono richieste anche tecniche di ricerca molto veloci, in una tabella non ordinata. Inoltre sono richieste memoria ad alta capacità (DRAM) e con bassi tempi di accesso (SRAM, cache). Il tipo di memoria che offre queste prestazioni è Ternary Content Address Memories (TCAM). Dato ad una TCAM un indirizzo IP di 32 bit, questa restituisce la riga della tabella di instradamento in un tempo che non dipende dalla posizione della riga. Dopo aver determinato, dalla tabella di instradamento, la porta di uscita di un pacchetto, il pacchetto può essere affidato al commutatore interno. Ma se altri pacchetti sono in corso di spostamento da altre porte, il commutatore interno potrebbe bloccare temporaneamente il pacchetto. Oltre alla ricerca, ci sono anche altre operazioni che possono essere svolte dalla porta di input: (1) il pacchetto deve attraversare i livelli fisico e collegamento, si deve controllare il campo checksum, si deve aggiornare il campo TTL e (3) si devono aggiornare i contatori N(R) e N(S) usati per controllare il flusso delle trame a livello 2.

Le azioni svolte da un router per smistare i pacchetti sono svolte in modo quasi simile da un switch. Altri dispositivi di rete agiscono sui pacchetti in transito: i firewall possono filtrare i pacchetti entranti e i pacchetti uscenti in base ad una combinazione di indirizzi sorgente e destinazione o numero di porta sorgente e destinazione, e altri criteri; Un dispositivo NAT (network address translator) cambia il numero di porta dei pacchetti entranti.

Commutazione

Il commutatore interno è il componente che svolge il compito fondamentale del router: spostare i pacchetti dalla porta di input alla porta di output. Esistono vari modi per svolgere la commutazione.

Commutazione tramite la memoria. Le porte sono configurate come dispositivi di I/O. Quando viene ricevuto un pacchetto si genera una interruzione. Il sistema operativo del router deve riconoscere e trattare questa segnalazione generata da una periferica, cioè trasferisce il pacchetto nella memoria del processore, da dove il processore legge l'indirizzo destinazione contenuto nell'header e lo cerca nella tabella di instradamento per determinare l'interfaccia a cui consegnare il pacchetto, quindi copia il pacchetto nel buffer della porta di uscita. In questo caso se la larghezza di banda della memoria ammette una velocità di trasferimento di B pacchetti al secondo, allora il flusso di smistamento totale (il numero di pacchetti al secondo trasferiti da una porta di input ad una porta di output) deve essere minore di B/2. Notare che non si possono trasferire pacchetti contemporaneamente, perchè il bus di sistema può essere usato per un solo input e un solo output.
Molti router moderni usano la commutazione tramite la memoria. La ricerca all'interno della tabella di instradamento avviene direttamente sulla porta di input. Questa tecnica si ispira all'architettura di sistemi a multiprocessore con memoria condivisa.
Commutazione tramite bus. Questa tecnica non coinvolge il processore. La porta di input trasferisce direttamente il pacchetto verso la porta di uscita. Per realizzare questo trasferimento, l'header del pacchetto è preceduto dal numero della porta di uscita verso cui dovrà essere copiato. Il bus è condiviso tra tutte le porte di output, ma solo quella che ha il numero indicato prima dell'header lo acquisisce. A questo punto la label recante il numero della porta di output viene tolta. Se il router riceve molti pacchetti contemporaneamente, ognuno su una porta di input diversa, uno solo di questi può accedere al bus, gli altri devono aspettare. La velocità di commutazione dipende dalla velocità del bus.
Commutazione tramite interconnessione delle porte. Per superare la limitazione del bus condiviso si può realizzare una connessione che per ogni porta di input raggiunge tutte le altre porte di uscita con un bus separato. Questa interconnessione è denominata crossbar switch. Consiste di 2·N bus che connettono le N porte di input alle N porte di output. Ogni bus verticale interseca ognuno dei bus orizzontali in un incrocio. L'incrocio può essere azionato dal controllore del commutatore in due stati: aperto (scollegato) o chiuso (collegato).

Quando viene ricevuto un pacchetto sulla porta A e deve essere instradato sulla porta Y il controllore del commutatore chiude gli interruttori al punto di incrocio dei bus A ed Y e la porta A invia i pacchetti sul suo bus che vengono prelevati solo dal bus Y. Si noti che un pacchetto sulla porta B può essere smistato sulla porta X perchè i bus da A ad Y sono separati dai bus da B a X. Questa soluzione consente di trasferire pacchetti in parallelo. Se però due pacchetti da sorgenti diverse devono essere smistati sulla stessa porta, solo uno potrà essere inviato, l'altro dovrà aspettare.

Elaborazione dell'output

L'elaborazione sulla porta di output consiste nel prelevare i pacchetti memorizzati nel buffer della porta di output e trasmetterli sul canale di output. Questa elaborazione prevede l'applicazione delle operazioni di livello collegamento e fisico.

Formazione della coda

Osservando la configurazione e le funzionalità delle porte di input e di output, si nota che le code dei pacchetti si possono formare sia alle porte di input sia alle porte di output. La lunghezza delle code dipende dall'intensità del traffico, dalla velocità del commutatore interno al router e dalla velocità della linea. Se queste code in cui i pacchetti restano in attesa di essere smistati crescono più rapidamente di quanto si svuotano, la memoria del router si potrebbe saturare e non ci sarebbe posto per acquisire nuovi pacchetti in arrivo. Si verifica quindi una perdita di pacchetti perchè il router scarta quelli che non può memorizzare. Si potrebbe anche pensare che si verifica una sovrascrittura di pacchetti, perchè, comunque, il router sta perdendo un pacchetto.

Si supponga che la velocità delle linee, di input e di output, sia R_linea pacchetti al secondo per ogni canale, e che ci siano N porte di input e N porte di output. Si ammetta che tutti i pacchetti abbiano la stessa lunghezza. Inoltre, il tempo richiesto per trasmettere un pacchetto su un canale è uguale al tempo impiegato a ricevere un pacchetto su un canale qualsiasi, e durante tale intervallo di tempo possono arrivare nessuno o al massimo un pacchetto su un canale di input. Si indichi con R_sw la velocità di spostamento di un pacchetto da una porta di input ad una porta di output. Se R_sw è N volte maggiore di R_linea allora la lunghezza della coda ad una qualsiasi porta di input è trascurabile. Perchè, nel caso peggiore, quando tutte le N linee di input stanno ricevendo pacchetti, e tutti i pacchetti sono spostati verso la stessa porta di output, ogni blocco di N pacchetti (un pacchetto per porta di input) può essere cancellato prima che arrivi un altro blocco.

Si consideri la coda che si crea su una porta di output. Si supponga che R_sw sia ancora N volte più veloce di R_linea. Nell'ipotesi che i pacchetti giunti su ognuna delle N porte di input siano destinati alla stessa porta di output, nel tempo richiesto per trasmettere un pacchetto sul canale di uscita, arrivano N pacchetti nella memoria della porta di output. Poichè la porta di output può trasmettere un solo pacchetto alla volta, gli N pacchetti che arrivano dovranno aspettare in coda prima di essere trasmessi. Poi potrebbero arrivare altri N pacchetti da trasmettere mentre solo uno degli N pacchetti in coda è in corso di trasmissione.

Il numero di pacchetti in coda può crescere fino a saturare tutta la memoria disponibile nella porta di output, e i nuovi pacchetti, non trovando posto, vengono scartati o sovrascrivono quelli presenti.

Il fenomeno della formazione della coda sulla porta di output è illustrato in figura. Al tempo t arriva un pacchetto su ognuna delle porte di input, ciascuno destinato alla stessa porta di output. Assumendo che tutte le linee abbiano la stessa velocità e il commutatore operi a velocità 3 volte maggiore a quella delle linee, una unità di tempo dopo (cioè il tempo necessario per ricevere o inviare un pacchetto) tutti i tre pacchetti originali sono stati trasferiti sulla porta di output e restano in attesa di essere trasmessi. Nella successiva unità di tempo, uno di questi tre pacchetti sarà stato trasmesso sul canale di uscita. Nell'esempio, altri due pacchetti sono giunti sul lato entrante del commutatore; uno di questi è destinato alla stessa porta di uscita dei precedenti. Ai buffer dei router è richiesto di assorbire le fluttuazioni dell'intensità del traffico, ci si chiede come dimensionare il buffer.

In base a simulazioni statistiche, la regola suggerita per calcolare la dimensione B del buffer era il prodotto tra il tempo medio RTT (ad esempio 250 ms) e la capacità C del canale. Quindi con una velocità di trasmissione di 10 Gbps e un RTT di 250 ms la dimensione del buffer è B = 2.5 Gbit.

Esperimenti più accurati sulle moderne reti suggeriscono che se ci sono N connessioni TCP che attraversano lo stesso canale, la dimensione del buffer deve essere B = RTT·C·√N. Su una dorsale viene convogliata una grande quantità di traffico, quindi il valore di N è grande e considerarne la radice, non produce un valore molto grande nella dimensione del buffer.

Una conseguenza della formazione della coda nella porta di uscita è che bisogna scegliere il pacchetto, tra quelli in attesa, da trasmettere. Il criterio di scelta potrebbe essere il semplice "primo arrivato primo servito" oppure il più sofisticato criterio che ripartisce equamente la trasmissione tra tutte le connessioni. Questa scelta si manifesta sulla qualità del servizio.

Anche in questo caso, quando si verifica la saturazione della memoria, bisogna decidere se scartare un pacchetto in arrivo o sovrascriverne uno presente in coda. Sarebbe vantaggioso poter restituire il pacchetto scartato al mittente, con una indicazione del motivo per cui il pacchetto non può essere recapitato, informare cioè che la rete è congestionata.

Sono stati proposti molti algoritmi per scartare pacchetti e segnalare la congestione: Uno di maggior interesse è l'algoritmo Random Early Detection (RED). Viene mantenuta un media ponderata della lunghezza della coda di uscita. Se, quando arriva un pacchetto, la lunghezza media della coda resta al di sotto di un valore di soglia minimo, il pacchetto viene inserito in coda. In caso contrario, quando arriva un pacchetto, se la coda è piena o se la lunghezza media della coda è superiore al valore di soglia massimo, il pacchetto viene scartato o rispedito al mittente con una marca di segnalazione. Infine se arriva un pacchetto, mentre la lunghezza della coda è compresa tra i valori di soglia minimo e massimo, si decide con una probabilità che dipende dai valori medi di lungheza della coda e dei valori di soglia se il pacchetto deve essere scartato o accettato.

Struttura di un router.

Se il circuito interno di commutazione non è sufficientemente veloce, rispetto alla velocità delle linee di input, a trasferire tutti i pacchetti entranti senza inserire ritardi, si può formare una coda di pacchetti alla porta di input, in cui i pacchetti aspettano il turno di essere trasmessi sulla porta di output. Per illustrare una importante conseguenza di questo fenomeno si consideri un canale tra le porte di input e le porte di output formato da un crossbar switch. Si supponga che tutti i canali abbiano la stessa velocità, che il tempo richiesto per trasferire un pacchetto da una porta di input ad una porta di output è uguale al tempo occorrente a ricevere un pacchetto su un canale di input e che i pacchetti vengono spostati da una coda di input ad una coda di output secondo il criterio primo arrivato primo servito. Si possono trasferire più pacchetti in parallelo, fintantochè sono diretti a porte di output diverse. Se però due pacchetti di due code di input diverse sono destinati alla stessa porta di output uno passerà e l'altro dovrà rimanere in attesa nella coda.

La figura mostra due pacchetti che da due code di input diverse devono andare alla stessa coda di uscita. Il commutatore sceglie un pacchetto da una coda per trasferirlo nella coda di output. Il secondo pacchetto deve aspettare. Ma anche il pacchetto che lo segue deve aspettare, nonostante debba andare in una diversa coda di output, per la quale il bus è libero. In conseguenza di questo fenomeno (la via è libera, ma il pacchetto è preceduto da un pacchetto bloccato), si possono verificare altre perdite di pacchetti.

Schema di controllo del router

Finora si è assunto che tutto il controllo dei componenti del router è affidato interamente ad un processore di routing. Lo schema di controllo dei router interconnessi deve essere distribuito, cioè ciascun router collabora, ad esempio, alla costruzione delle tabelle di instradamento scambiandosi messaggi di servizio che riportano informazioni sullo stato dei canali e delle code. Sono in corso di studio nuove archietture dei router, in cui parte del controllo è implementato nei router (misure dello stato dei canali, creazione ed aggioranamento delle tabelle di instradamento) e parte del controllo può essere affidato a computer esterni ai router (ad esempio un server centrale esegue i calcoli richiesti per valutare i costi dei cammini tra i router).

Attualmente i ricercatori sono impegnati ad investigare nuove architetture dei router, nelle quali parte del controllo è implementato nei router stessi (come ad esempio, misure e segnalazioni dello stato dei canali, installazione e manutenzione delle tabelle di instradamento) insieme ai dati, e parte de controllo può essere implementato esternamente ai router (ad esempio, in un server centralizzato, che esegue gli algoritmi di calcolo delle tabelle di instradamento). Una ben precisa interfaccia di programmazione (API) regola le interazioni e la comunicazione tra queste due parti. Iricercatori ritengono che la separazione controllo software dalla memorizzazione in hardware dei dati, possa semplificare notevolmente l'instradamento, sostituendo il calcolo distribuito con il calcolo centralizzato, e permette che ci siano innovazioni di rete.