Sartomiki.net

Switching e Forwarding
Lo switching, come già detto, è un meccanismo che serve a decidere su quale uscita deve essere portato un pacchetto in ingresso in un router o in uno switch. Negli switch Ethernet questa funzionalità è implementata mediante gli algoritmi di lookup a match esatto, mentre nei router IP viene implementata mediante il forwarding.
Il forwarding è il processo che dato l'indirizzo di destinazione di un pacchetto si decide il next hop, dopo aver consultato la routing table.

Lookup
Data in ingresso una chiave, mediante la funzione di lookup, si ottiene un valore in uscita. Normalmente si ottengono più valori in uscita. I parametri utilizzati per la valutazione delle tecnologie di lookup sono diversi:
-velocità.
-memoria utilizzata.
-tempo di aggiornamento della tabella di lookup.
-scalabilità della tabella, nel senso quanto costa in termini di tempo l'aggiunta di un certo numero di righe nella tabella.
-flessibilità.

Lookup esatto
Per lookup esatto si intende trovare l'uscita esatta data una chiave univoca.
Nell'MPLS (label swapping) le chiavi (label) sono da 20bit, il router data la label deve decidere la nuova label e portarla in uscita.
La soluzione implementativa più semplice è quella di avere una tabella di 2^20 chiavi, con associate le chiavi di ingresso, la qualità del servizio e la porta di uscita. La label in questo caso è un indirizzo (indice del vettore) e ogni riga è di 32bit. In totale si hanno 32MB di memoria occupata.
Un metodo alternativo è quello dell'ethernet switching. Anche in questo caso abbiamo lookup esatto (dato il destination MAC, dobbiamo decidere l'interfaccia di uscita). La cardinalità massima dell'insieme, usando il metodo precedente, in questo caso sarebbe 2^48, in quanto gli indirizzi MAC sono da 48bit. Non è quindi possibile utilizzare il metodo precedente. L'insieme dei MAC conosciuti dallo switch è molto più piccolo dell'insieme di tutti gli indirizzi MAC del mondo. Si tratta quindi di una tabella sparsa. Una possibile soluzione è quella delle memorie CAM, che sono memorie associative che, dato un valore in ingresso, restituiscono in uscita l'indirizzo della cella che contiene le informazioni riguardanti quella chiave. Queste memorie si ottengono mettendo un circuito di comparazione per ogni bit in ingresso. Il risultato di tutte le comparazioni (che viene prodotto in un colpo di clock) viene mandato in un encoder, che fornisce l'indirizzo della cella corrispondente all'indirizzo di ingresso. Ovviamente l'encoder è fatto in modo da dare risultati diversi per ogni dato in ingresso. I vantaggi della CAM sono il tempo di ricerca molto veloce e una latenza comparabile a quella delle SRAM. Lo svantaggio è avere una densità pari a circa la metà delle SRAM, un alto costo e un'elevata dissipazione di potenza.
L'operazione di lookup di ethernet switching può essere effettuato mediante una tabella di hash. L'operazione di hashing necessita di un tempo costante, mentre la ricerca necessita di un tempo variabile. A causa delle collisioni si può avere un caso peggiore di tempo di ricerca lineare, mentre un caso migliore di un hit in un passo. Il vantaggio principale è la semplicità di implementazione. Gli svantaggi sono un utilizzo inefficiente della memoria e un tempo di lookup non lineare.
Un ultimo metodo di implementazione di lookup di ethernet switching è quello dell'albero binario. In questo modo, avendo un albero bilanciato e ordinato, si può avere nel caso peggiore il valore corrispondente all'ingresso in un numero log2(N) di passi. Questo metodo è molto veloce in lettura, anche se ha un tempo di update che può essere lungo, in quanto l'albero deve essere ribilanciato.

Longest prefix match
Dato un indirizzo di ingresso si vuole avere una chiave di uscita.
Se si pensa a IPv4 classfull (ormai non più in uso) ad ogni classe è associata una NETMask implicita. In base alla classe, si associava l'indirizzo di rete, e la ricerca era fatta mediante una forwarding table.
Con l'introduzione di IPv4 classless le NETMask non si basano più sulla classe, ma sono indipendenti. Si effettua quindi una associazione ingresso-uscita mediante la tecnica del longest prefix match.
Secondo questa tecnica la tabella è composta da valori e don't care. L'indirizzo da individuare è quello che risulta essere più "simile". Grazie a questa tecnica è possibile aggregare più indirizzi di ingresso verso una stessa uscita.
Mantenendo la lista ordinata si ha un tempo di ricerca abbastanza basso, anche se non sempre è facile tenerla ordinata. L'alternativa hardware è data dalla TCAM, memoria simile alla CAM, ma con anche i valori di don't care. In questo modo si possono ottenere i risultati in un colpo di clock. La TCAM fornisce l'indirizzo del prefisso più lungo. I vantaggi/svantaggi sono gli stessi delle CAM.
Un'altra possibile implementazione software oltre alla ricerca lineare è l'Uni-bit Trie. E' un "automa" che riesce a riconoscere sequenze di bit. E' organizzato ad albero (viene costruito solo l'albero delle sequenze di bit che ci interessano) e da in uscita la label del percorso più lungo che matcha l'ingresso. Questo metodo è molto semplice da implementare ed è utilizzabile anche per match esatti. Il lookup e l'update sono veloci. Gli svantaggi sono un caso peggiore molto lento (24/32 accessi in memoria) e uno spreco di memoria causato dai puntatori.
La stessa soluzione precedente può essere messa in atto mediante un Multi-bit Trie, che consente un matching multiplo per ogni passo. In questo caso si aumenta il numero di puntatori (k per ogni nodo), anche se diminuisce la profondità dell'albero, quindi il numero di accessi in memoria. Un ulteriore problema è che non si riescono a matchare i prefissi con lunghezze che non sono multipli di 2^k, a meno di non espanderli. Con k=8 abbiamo al massimo 4 accessi in memoria.

Classificazione
Serve per stabilire il tipo di traffico che deve passare per un determinato router. Possono interessare packet filtering (firewalling..) per gestire in maniera diversa il traffico proveniente da host diversi. Si passa da un concetto a pacchetti a un concetto di flusso. Le decisioni di forwarding o di switching si basano solo sull'indirizzo di arrivo. Un flusso è definito come un insieme di pacchetti che condivide le stesse caratteristiche, che si possono basare su:
-stessa coppia ip sorgente-ip destinazione
-stesso ip destinazione-stesso protocollo di livello 4
-stessa connessione TCP
-stessa generica sessione TCP/UDP
Indipendentemente dal flusso è necessario definire un insieme di campi (detti regole) e di comportamenti da assumere in determinate situazioni. La coppia in gioco è quindi data da regola-azione. Esistono diversi tipi di matching delle regole:
-exact, si basa su un parametro univoco (una singola porta tcp)
-range, si basano su un insieme di fattori (un insieme di porte tcp)
Il longest prefix match, ad esempio è un classificatore basato su un solo campo (l'ip destinazione). In questo caso il database delle regole è la forwarding table, le regole definiscono il prefisso, il next-hop e il link. Il costo della regola è 1/(lunghezza del prefisso). I fattori che definiscono il "peso" di una classificazione sono:
-velocità necessaria per i pacchetti di dimensione minima.
-occupazione in memoria del database.
-capacità di gestire ampi database di regole.
-scalabilità del numero di campi.
-velocità di aggiornamento delle regole.
-flessibilità delle regole.

Tecniche di classificazione
E' la soluzione più semplice risulta uguale al forwarding. Per i dispositivi di fascia bassa è la soluzione più usata, in quanto le regole non sono molte.
La soluzione hardware prevede l'utilizzo delle TCAM, mettendo su ogni riga tutti i campi da confrontare. Da essa esce un dato che porta all'indirizzo in RAM dove è contenuta l'azione da intraprendere. I problemi sono gli stessi del caso del forwarding (costo, dissipazione, scalabilità e bassa densità). In più in caso di range bisogna creare dei prefissi, incrementando il numero delle entry. Questo è un problema nel caso in cui i limiti non siano multipli di 2, in cui una semplice regola può essere messa su un numero di entry anche elevato. Nella realtà le regole basate su range non sono moltissime.
Esistono numerose soluzioni algoritmiche che si comportano in modo migliore rispetto alle TCAM.
L'interpretazione geometrica consente di rappresentare le regole mediante figure in un piano o in un solido, a seconda del numero di parametri che si devono prendere in considerazione. Si mette su ciascun asse il parametro, in questo modo si può definire ogni ingresso come un punto all'interno dello spazio. Lo spazio sarà diviso in regioni (dettate dalle regole), e in base alla regione di appartenenza verranno intraprese delle azioni. Il tempo di soluzione dipende dalla memoria occupata. Nel caso di memoria O(N) si ha un tempo di soluzione O((logN)^(k-1)), nel caso di memoria O(N^k) il tempo di soluzione O(logN). Questi risultati derivano dalla geometria computazionale.
Nel caso in cui ci siano solo due campi da confrontare abbiamo diverse soluzioni possibili:
-Hierarchical tries. Si valutano gli insiemi di prefissi dei due campi da confrontare e si costruisce l'uni-bit tree relativo al primo campo. Ai nodi si associano le regole corrispondenti. Dopo questa prima costruzione si costruiscono gli uni-bit tree di secondo livello per il secondo campo. La ricerca avviene ricercando prima nel primo albero e poi in tutti i sottoalberi. Ha dei problemi di backtracking. Nel caso peggiore di ricerca abbiamo O(W^2), con w pari alla lunghezza delle regole
-Set pruning tries. E' come il precedente ma si duplicano le informazioni del secondo campo su ogni ramo. In questo caso si ha un grande dispendio di memoria
-Grid of tries. E' come il primo ma inserisce puntatori che consentono l'accesso diretto ai nodi che ci interessano. Il lookup è pari a 2*W e memoria N*W. E' un buon compromesso anche se è difficile da aggiornare e non è estendibile a più di due dimensioni
Nel caso in cui ci siano più di due dimensioni:
-prodotto cartesiano, per ogni elemento del primo campo si uniscono tutti gli elementi del secondo campo. In questa tabella viene inserita la relativa regola per ogni campo. Il problema è che si ha un numero di righe necessario pari a N^k a fronte di una velocità di k+1. Il prodotto cartesiano garantisce alte prestazioni e supporta regole a più di due dimensioni, anche se comporta un eccessivo uso della memoria e una fase di preproccessing che può essere molto onerosa.
-soluzioni euristiche.