lesson_06.md 6.2 KB
Piattaforme e Software per la rete - lezione 6
Giacomo Verticale
22 March 2016
IP Prefix Match
Più sofisticato rispetto all'exact match degli switch ethernet Serve che tutti gli indirizzi abbiano un tempo di risoluzione uniforme La famiglia di algoritmi basati su trie sono molto diffusi per IPv4 Gli algoritmi di ricerca binaria danno risultati dignitosi in IPv4 e stanno tornando di interesse per IPv6 in quanto le ottimizzazioni di IPv4 non sono più efficaci.
Possiamo costruire facilmente la ricerca esatta, quindi posso ricondurre la ricerca generica alla ricerca esatta, come nel L'algoritmo binary search on prefix lenghts
- Ho un array con lunghezze diverse per ogni elemento Ad ogni elemento corrisponde una hashtable con i prefissi di quella lunghezza.
L'algoritmo applicato all esempio precedente
0* - 101* 1000* 11001* 100000*
1* 111*
100*
110*
Il costo computazionale per una ricerca lineare nell'array nel caso pessimo (prefix length=0) porta a 32 accessi, Posso migliorare questa resa fino a log2(32) usando ricerca binaria.
Esempio: Iniziando la ricerca binaria da l=16
- Se trovo un match posso escludere la parte sinistra perchè il longest match sarà sicuramente a destra
- Se non lo trovo non so dire se è a destra o sinistra.
Aggiungo un marcatore per segnare un punto all'interno dell'array uguale al prefisso da cercare, in modo che se la ricerca a destra non porta risultati, devo cercare a sinistra.
Packet Classification
Stiamo trattando il livello 4, che in teoria dovrebbe essere implementato solo a livello di host, ma i nodi interni alla rete possono sbirciare nei pacchetti per implementare funzioni aggiuntive ad esempio NPAT(NAT con modifica dei numeri di porta), oppure i firewall Questi oggetti non implementano la macchina a stati TCP ma gestiscono i pacchetti intermedi.
Middlebox è un nodo interno della rete che non è un host ma nemmeno un router Hanno funzioni molto diverse, in Internet circa 50% dei nodi sono middlebox. Storicamente i middlebox erano dei pizzabox da inserire nei rack del datacenter, ma ultimamente si tende alla dematerializzazione di questi dispositivi.
Esempi di middlebox sono:
- NPAT Fanno Network Port Address translation
- Firewall Impediscono o meno il passaggio di determinati pacchetti
- WAN Accellerator Gestiscono la differenza di velocità tra reti, per evitare la formazione di code lunghe ad esempio tra dorsare e rete mobile o adsl. Nota: ad esempio nel caso di streaming video su rete mobile la rete fa il prefetching dei contenuti del video richiesto e quando i contenuti sono finiti, ne vengono chiesti altri
- L4 Switch violano la separazione dei layer e fanno routing ottimizzando in base ad informazioni prese dal livello 4
- L7 Switch fanno routing in base al livello applicativo
All'interno di un middlebox possono esserci ~10'000-100'000 regole per gestire i pacchetti. I pacchetti sono classificati in base ad un set di regole: Ruleset o Database. Ogni regola ha una priorità per disambiguare nel caso di match multipli. Problema della Packet classification consiste nel trovare la regola corrispondente a massima priorità o a costo minimo. (in ogni caso numero d'ordine più basso)
Le regole sono multifield Ogni regola da delle condizioni su uno o più campi del pacchetto, quindi guarda fino a K campi distinti del pacchetto. Ogni campo è una stringa di bit di lunghezza fissata. Nota: la posizione del campo nel pacchetto dipende da altri campi. Sono consentiti 3 tipi di corrispondenza per ogni campo:
- Exact match es: TCP con porta 80
- Prefix match es: indirizzi IP
- Range match es: un certo intervallo di porte
Classificatore = {R1,R2,...Rn} Ri=regola i-esima Regola = (regola campo 1, regola campo 2,.. regola campo K) Ad ogni regola è associato un costo o priorità, e una direttiva (insieme di azioni da compiere)
Abbiamo una rete 'Net' con due host 'M' e 'TI', alla rete Net è collegato un middlebox. Al middlebox è attaccata un altra rete con due host 'TO' e 'S'
TI e TO sono due server del tempo che usano il protocollo NTP
Esempio di possibile ruleset per un firewall (non unica applicazione possibile):
| DEST IP | SORG IP | DST P | SRC P | PROTO | FLAG |
|---|---|---|---|---|---|
| M | - | 25 | - | TCP | - |
| M | - | 53 | - | UDP | - |
| TI | TO | 123 | 123 | UDP | - |
| - | Net | - | - | - | - |
| Net | - | - | - | TCP | ACK |
| - | - | - | - | - | - |
La penultima regola fa passare tutti i pacchetti a parte il SYN iniziale L'ultima regola matcha tutti gli altri casi, generalmente per un firewall il comportamento di default è bloccare (whitelisting), ma potrebbe essere diverso per un altro middlebox.
Requisiti prestazionali
- Classificazione wirespeed Posso sempre scambiare utilizzo di memoria con prestazioni, usando ad esempio strutture dati replicate per il ruleset.
- Occupazione di memoria piccola
- Inserimento / cancellazione infrequenti
- Sono generalmente stateless ma possono essere stateful Esempio: firewall stateful che quando rileva un pacchetto SYN uscente aggiunge una rule per far passare gli ACK entranti per consentire quella connessione. Esempio2: Middlebox che bloccano tentativi di accesso anomali (es: fail2ban)
Ricerca lineare
Va bene quando ho pochi elementi Posso abbinarla ad un caching per le ultime regole usate. Ricordando che la località dei pacchetti è relativamente bassa, rispetto ad esempio ad un accesso su disco. Attenzione a basso hit ratio (~80-90%) Il problema è che se un pacchetto fa match nella cache, posso avere fuori dalla cache una regola a priorità più alta Quindi conviene copiare in cache gli header dei pacchetti della stessa connessione, in modo da riconoscere pacchetti della stessa connessione.
Passare etichette
E un approccio di 'thinking out of the box', e consiste nel delegare la classificazione ad altri, ad esempio ai router di frontiera che hanno un flusso minore e hanno più tempo per classificare i pacchetti, quindi:
- Nodi di frontiera fanno classificazione multi-field e applicano tag
- Nodi interni fanno exact match sui tag (es: MPLS, DIFFSERV)
BPF
PacketFilter usato negli host in modo efficace, ma molto lento se usato nei router.