polimd/Piattaforme Software per la Rete/MOD1/lesson_05.md

Piattaforme Software per la Rete - lesson 5

Giacomo Verticale

18 March 2016

Prefix Match

Per ogni pacchetto viene fatto il matching nella tabella di inoltro In caso di ambiguità di applica la regola del Longest prefix matching Cioè data una chiave, dobbiamo trovare la riga contenente il prefisso più lungo.

Osservazioni

Potremmo usare una cache per le voci più usate Il costo finale della ricerca sarà una media pesata del costo per la ricerca in cache e del costo per la ricerca fuori, quindi è utile solo in caso di alta probabilità di usare la cache (~90-95%) Nei router con tabelle molto grandi, gli indirizzi utilizzati sono molto vari

• 1 molti flussi contemporaneamente
  • molti indirizzi diversi in un intervallo breve
• 2 ~50% dei pacchetti sono TCP SYN e/o ACK ~40byte
  • Quindi il tempo di interarrivo è all'incirca quello dei pacchetti di lunghezza minima, quindi ho poco tempo per risolvere gli indirizzi.
• 3 Il costo della ricerca è dominato dal tempo di accesso in memoria Perchè ci sono solo operazioni aritmetiche semplici da effettuare.
• 4 Capita di trovare prefissi di tutte le lunghezze (non solo 24)
• 5 ~100'000 di righe Con IPv6 la situazione peggiora perchè ci sono altri indirizzi e le netmask vanno da 8 a 64bit
• 6 Aggiornamenti frequenti (ms-s) devo usare algoritmi con letture e scritture bilanciate.
  • Ci sono algoritmi che hanno ottime prestazioni in lettura ma quelle in scrittura sono disastrose ce ne sono altri che hanno delle buone velocità in scrittura ma meno in lettura

Soluzione

Una soluzione ottima che richiede budget molto elevato è tutta in hardware Le CAM hanno una tabella chiave-valore chiave = {0,1}^n è utile una variante: TCAM (ternary) chiave = {0,1,}^n (:wildcard) Gli * possono essere in qualsiasi posizione, noi li metteremo alla fine. La CAM può restituire al più 1 risultato, nella TCAM potrebbe succedere Il problema si risolve mettendo una preferenza tra le voci Cioè vince il prefisso più in alto, per questo è necessario ordinare le voci mettendo il prefisso più lungo in alto (inserimento più costoso rispetto ad una CAM normale usata nel Exact Matching)

Vantaggio Tempo di ricerca costante in lettura Svantaggi

• Rispetto ad una memoria normale, utilizza più transistor (10 rispetto a 1-2) Questo posta ad un costo più elevato per circuito (chip per area) Quindi consumano anche molto di più In italia il primo consumatore di energia sono le ferrovie, il secondo è telecom Ultimamente si utilizzano meno le TCAM e si usano invece memorie veloci con algoritmi molto ottimizzati e Cisco ha ottenuto anche un algoritmo con due accessi alla memoria (dinamica) per entry (e un numero fisso di accessi in cache). vedi successivamente multibit trie. Quindi le TCAM vengono usate in dispositivi di fascia media perchè per router troppo grossi non sono abbastanza capienti, e per router piccoli sono costose.

Algoritmo

Supponiamo di avere una TCAM già popolata con prefissi di lunghezza decrescente Se dobbiamo inserire un indirizzo in mezzo ad altri ma non c'è spazio Inserendo un indirizzo di lunghezza 31 lo mettiamo a posto del primo di lunghezza 30 che dobbiamo riposizionare, in questo modo avremo max 32 riposizionamenti. Un implementazione furba ha gli indirizzi lunghi sopra, quelli corti sotto e un buco in mezzo.

Soluzioni algoritmiche

Algoritmi basati su:

• Tries ha prestazioni migliori ma i più efficienti sono brevettati
• Ricerca binaria

Unibit trie

Tabella di routing
P1=101*
P2=111*
P3=11001*
P4=1*
P5=0*
P6=10000*
P7=100000*
P8=100*
P9=110*

Nodo dell'albero |Prefisso/valore| |---|---| |0|1| Il primo blocco è il puntatore al prossimo livello sul ramo 0 Il secondo è il puntatore al prossimo livello sul ramo 1 Radice dell'albero |Root| |---|---| |0-P5|1-P4|

|P5| |---|---| |-|-|

|P4| |---|---| |sottoalbero|s.a.|

|-| |---|---| |0-P8|1-P1| ecc... Ogni livello indica la lunghezza del prefisso.

Visita dell'albero Se dobbiamo cercare un indirizzo nell'albero iniziamo a scorrerlo dalla radice annotando l'ultimo nodo per cui passiamo Quando non possiamo più procedere l'ultimo nodo per cui siamo passati è la route cercata.

Tempi di accesso Costo nel caso pessimo: 32 accessi in memoria In generale è possibile scambiare occupazione di memoria con tempo di calcolo Utilizzando un multibit trie che ha per ogni nodo molti figli (es.4) Il problema dei multibit trie è che posso memorizzare solo prefissi che hanno lunghezza multipla intera del passo dell'albero, se ho prefissi più corti devo esploderli in più nodi di lunghezza intera. (1*3bit -> 2*4bit)

Se ho una tabella data, esiste un passo che ottimizza i tempi di accesso Però gli inserimenti sono critici perchè si sposta il punto di ottimo.