# 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.