- ACL a filtrovací pravidla - rozdělení provozu na ten, co projde a neprojde
- směrovače
- směrování - CAM tabulka
- QoS - kvalita služeb - rozděluje do které fronty paket dát
- na základě
- IP adresa,
- port,
- Type of Service,
- MAC adresy,
- aplikační hlavičky,
- IP protocol - TCP, UDP, …
- vyhledávání adres - pomocí cílové adresy
- firewall = ACL listy
- filtrování na 2 místech - na vstupním rozhraní a na výstupním rozhraní
- pokud zařízení generuje pakety -> pak nechodí na vstup
- může být více rozhraní -> vstupní nemusí filtrovat požadovaní filtry -> potřebujeme i na výstupu
- chybně zadané - špatné pořadí 40 a 50, bere se 1. vyhovující podle pořadí, 40 pohltí a překoná pravidlo 50
- u intrusion detect systémů
- pro každý specifický protokol musí být parser!
- potřeba bufferu na uchovávání paketů -> nebude implementováno v HW ale na control planu
- čím víc pravidel, tím víc zpožďuje
- prvních 20-30 bytů
- vyhledávání podle nejdelšího společného prefixu (LPM longest prefix match)
- nezáleží na pořadí ve směrovací tabulce
- výběr cesty podle
- administrativní vzdálenosti - číslo vzhledem k důvěryhodnosti protokolu
- metriky - podle směrovacího protokolu
- délka prefixu
- Která cesta se vybere pro paket s cílovou adresou 192.168.32.1?
- pošle se na 1. síť, protože má nejlepší prioritu podle směrovacího protokolu
- Jaké pravidlo se použije k poslání IP datagramu s Cílovou adresou 10.10.13.214?
- poslední OSPF - nejdelší prefix pro .208 a .214
>>> bin(208)
'0b11010000'
>>> bin(214)
'0b11010110'
- kontext paketu = Vybereme všechny hlavičky, které můžeme potřebovat pro filtrování (dáno pravidly)
- klasifikátor - porovnává data z hlavičky vůči pravidlům (porovnávání n-tic)
- způsoby porovnávání
- exact match
- prefix match
- interval match
- Jaká je časová složitost?
- Lineární složitost vůči počtu pravidel a počtu sloupců. $\mathcal{O}(N \times R)$
- → nepoužitelné pro stovky pravidel a několika sloupců (5+)
- pro prefixové vyhledávání - stromová struktura trie
- uzly co nemají pravidlo jsou pomocné uzly
- při stejné délce vezme se dané pravidlo
- při nenalezení přesné délky se vrací zpět, dokud nenajde pravidlo které matchuje
- složitost - nezáleží na počtu pravidel!
- $o(w)$ - w nejdelší prefix, které mám
- optimalizace - vícebitová (multibit trie)
- n-ární strom, krok může být více bitů $k$ (stride)
- prefixy dané velikosti -> potřeba transformace
- menší prefixy rozšiřujeme podle dané délky bitů
- pokud rozšířený prefix obsahuje již dané pravidlo před rozšířením -> pravidlo z rozšíření vypustíme
- implementace pomocí pole
- LC-tries - Lulea Compressed Trie = komprese na 2 pole - maska a pointer/pravidlo
- Pro každou dimenzi strom trie -> duplicity -> exponeciální prostorová složitost
- odstranění duplicit -> menší prostorová složitost, ale větší časová!!
- optimalizace - použití ukazatele (switch pointers) - chceme se vyhnout zpětnému vyhledávání
- ukazatele si mohu předpočítat dopředu!
- snížení časové složitosti
- pro jednoduchou implementaci některých firewallů
- divide and conquer
- pro každou dimenzi se udělá bitový vektor a porovná se s daty z paketu a nakonec se to sloučí pomocí bitového ANDu
- bitové vektory jsou dlouhé podle toho kolik je pravidel
- bitový vektor - bitová maska podle výskytu daného čísla v daném pravidle
- bereme první vyhovující pravidlo
- pokud adresy - daná dimenze jako trie
010001 - bereme první jedničku zleva -> tedy druhé pravidlo
- množina n-tic
- rozdělíme na jednotlivé dimenze
- najdeme nejbližší match
- dáme dohromady
- uděláme hash z n-tice a dostaneme pravidlo
- rozdělení pravidel do podprostorů/regiony
- paket je bod v prostoru - ukazuje kam patří do regionu
- rozdělení pomocí řezů - cuts
- regiony jako uzly rozhodovacího stromu
- Paměť CAM (Context addressable memory)
- opak RAM paměti - znám content a chci adresu
- využití u CAM tabulky (znám MAC adresu, chci vědět port)
- paměť TCAM (Ternary Con) - rozšířená CAM (3 hodnoty)
- hodnoty 0, 1, X (dont care)
- hodnota X je pomocí bitové masky
- prefixy sestupně podle délky
- vyhledání v 1 cyklu
- nevyhody