40 - Směrování a filtrování dat v Internetu

• Určit vhodnou cestu (sekvence směrovačů) sítí od zdroje k cíli
• Doba konvergence - doba potřebná k rozšíření informace o změně do všech směrovačů a jejich reakce na tuto změnu
• Směrovací tabulka - lokální tabulka směrovače obsahující informace pro každý známý cíl v síti
• Destination network - cílová síť - identifikace sítě, nejčastěji jako její ip adresa a maska
• Brána (gateway) - defaultní směrovač, first-hop router - směrovač připojený v lokální síti, zabezpečuje konektivitu lokální sítě
• Defaultní cesta - cesta, použita v případech kdy není k dispozici přesnější směrovací informace
• Směrovací protokol - protokol pro výměnu informací mezi směrovači pro účely zajištění směrování, např. RIP, OSPF, BGP, IS-IS, IGRP, EIGRP
• Směrovaný protokol - protokol pro přenos dat, využívá směrování, například IP, IPX, AppleTalk
• Směrovací algoritmus - algoritmus pro výpočet optimální cesty pro jednotlivé cílové sítě
• Statické směrování - pomalá konvergence, lokální aktualizace
• Dynamické směrování - rychlejší reakce na změnu, periodické aktualizace informací, okamžitá reakce na změnu ceny linky
• Globální - Každý směrovač má k dispozici kompletní informaci o topologii sítě, Vyžaduje šíření informací celou oblastí
• Decentralizované - Směrovače znají pouze sousedy a cenu linek k nim, Pouze výměna informací se sousedy

• Výpočet nejkratší cesty v grafu na základě informací o kompletní topologii a ohodnocení hran grafu cenami linek - Globální
• Po k iteracích jsou známy cesty do k cílů

Každý směrovač vypočítá cestu s nejmenší cenou pro každou cílovou síť Začátek cesty je vždy aktuální směrovač Iterativní výpočet Notace:

• C(i,j) - cena linky z uzlu i do uzlu j
• D(v) - aktuální hodnota ceny cesty ze zdroje do cíle v
• P(v) - předchůdce uzlu v podél cesty
• N - množina uzlů

• Bellman-Fulkerson-Ford algoritmus
• Iterativní, distribuovaný
• Informace se přímo šíří pouze mezi sousedy
• Asynchronní algoritmus - Není potřeba synchronizace mezi uzly pro zajištění správnosti výpočtu
• Datová struktura je tabulka:
  • Řádky jsou cíle
  • Sloupce jsou sousedé
  • V buňkách je uvedena cena do daného cíle přes uvedeného souseda
  • D(A, C) = 4, znamená, že ke směrovači A je přes souseda C cena 4.
• Poison Reverse: Jestliže C směruje přes B do A, pak C bude oznamovat B, že jeho nejlepší vzdálenost do A je nekonečno. (aby nedošlo k počítání do nekonečna)

→Wait (změna lokální ceny linky, zpráva od souseda) → Recompute (na základě nových dat aktualizace distance table) → Notify (zaslání informace sousedům, jestliže cena nejlepší cesty byla změněna)→

• Intra-autonomous system routing protocols (IGP) →RIP,OSPF, IGRP - EIGRP (cisco)
• Inter-autonomous system routing protocols (EGP) →BGP (iBGP, eBGP)

• link-state protokol
• siri informaci o změně v celé oblasti (LSA flooding)
• Dijkstrův algoritmus pro výpočet nejlepší cesty
• Ceny linek definuje administrátor (hop-count, bandwidth)
• Informace jsou posílány okamžitě v případě změny, či alespoň jednou za 30 minut.
• OSPF protokol je nesen IP protokolem (má číslo 89)
• V režii OSPF protokolu je zajištění spolehlivého přenosu a broadcastu
• OSPF testuje stav linky pomocí HELO paketů
• Aktualizace mohou být autetizovány
• Load-balancing - více cest se stejnou cenou může být současně použito pro přenos dat
• Podpora pro multicastové směrování – Multicast OSPF
• Podpora pro intra-autonomous system hierarchické směrovaní
  • Rozdělení AS do oblastí (areas)
  • Šíření informací pouze směrovačům v rámci oblasti
  • Hraniční směrovače pro každou oblasti propojují oblasti mezi sebou
  • Area 0 je propojovací oblastí –backbone area

• nejstarší směrovací protokol
• distance-vector (metrikou je počet skoku, hop-count)
• hop count > 15oznacuje nedosažitelnou cestu - kvuli zacyklení směrovačů
• periodicke aktualizace kazdych 30s
• jestliže neprijde po dobu 180s aktualizace od souseda, je oznacen za neplatny a jsou informovani sousede
• sousede aktualizuji sva data a pokud doslo ke zmene v RT posilaji oznameni
• selhani linky/směrovače je takto sireno celou siti
• poison reverse – zabráněni vytvareni směrovacích smyček
• rip zprávy jsou neseny UDP/520
• RIPv1 – classfull (nezna masku), nema autentizaci, unicast
• RIPv2 – classless (podporuje CIDR), sifrovany, multicast
• RIPng – podpora IPv6

• Path-vector protokol –podobny princip jako DV
• Cesta jako seznam AS je k dispozici pro každou cílovou síť
• ASN je 16-bitové číslo, přiřazované ICANN
• Například: Path(4,6) = 4, 1, 3, 6
• Přijmutí a filtrování informace od souseda
  • Soused je označován jako BGP Peer
  • Router advertisement je nabídka možnosti směrování
• Výběr cesty
  • BGP směrovače mohou mít k dispozici více různých cest ke stejné síti
  • Na základě atributů cesty a rating policy se vybírá jedna z nich
  • Routing policy je lokálně definována administrátorem AS
  • Atributy: AS posloupnost, lokální preference, původ, komunitní číslo, MED, váha
• Poslání oznámení o cestě sousedovi
  • Mechanismus umožňuje vybrat, jaké informace budou posílány
  • Prevence používání netranzitních (koncových) AS pro tranzitní přenosy
• BGP zprávy se vyměňují pomocí TCP port 179
• Typy zpráv:
  • OPEN: otevře spojení a autentizuje peery
  • UPDATE:oznámení nové cesty (new feasible route), respektive oznámení o jejím zániku (withdrawn route)
  • KEEPALIVE: udržování spojení
  • NOTIFICATION: uzavření spojení, oznamování chyb
• Sumarizace:nebude - zamitnut obrazek

• filtrování vstupního a výstupního provozu
• kontrolují provoz - data propustí nebo zablokují
• cislo protokolu, zdrojová/cílová IP adresa, zdrojový/cílový port, a další
• 10 permit TCP from 147.229.0.0 to any dst-port 80
• Pruchod pravidly od zacatku, dokud není nejake splneno

• Filtrování paketů (packet filtering) - kontrola jednotlivých paketů
• Stavové filtrování (stateful filtering) - kontrola TCP toku (SYN,ACK)
• Aplikační brána (application gateway) - na úrovni aplikační vrstvy

• Inkluzivní přístup – zakazuje vše, co není povoleno, bezpečnější než
• Exkluzivní přístup - propouští vše, co není zakázáno

• provoz považován za dvousměrnou výměnu paketů v rámci relace
• aktivace keep-state dynamicky generuje interní pravidla pro každý očekávaný paket v relaci
• Činnost stavového filtrování
  • Odcházející paket se zkontroluje v dynamické stavové tabulce
    • Pokud paket odpovídá očekávanému paketu relace (TCP), prochází. Stav relace je v tabulce aktualizován.
    • Ostatní pakety se kontrolují podle výstupních pravidel
  • Podobně pro přicházející pakety
  • Po ukončení relace se zruší informace z dynamické stavové tabulky

• kontrola (inspekce) toků známých protokolů
• SMTP, HTTP, FTP, IMAP, POP3
• filtrování URL
• Peer-to-peer (P2P) síťe: Bittorent, KaZaA, Gnutella, eDonkey
• Pokročilá filtrovací pravidla
  • kontextově závislé filtrování
  • časově podmíňená pravidla

—-

• Firewally
  • filtrování provozu
  • zahazování, propuštění definovaného provozu
• Detekční systémy IDS (Intrusion Detection Systems)
  • kontrola provozu, monitorování dat
  • detekce útoků, neočekávaného chování
  • detekce na základě signatur či chování
• Prevenční systémy IPS (Intrusion Prevention Systems)
  • reakce na útok → odkloňení či odfiltrování provozu

• Algoritmický problém
  • roztřídit zprávy podle zadaných pravidel
  • najít co nejrychleji pravidlo, které se shodu s informacemi v hlavičce
  • paket H obsahuje K hlaviček (dimenzí): H = (H1,H2, . . . ,HK)
  • klasifikátor se skládá z N pravidel R = {R1,R2, . . . ,RN}
  • pravidlo je n-tice obsahující K položek (počet dimenzí)
  • např. R1 = (147.229.* .*, *, 25, *, *)
• Typy porovnání
  • Přesné porovnání (exact match)
  • Porovnání prefixu (prefix match)
  • Intervalové porovnání (interval match)
• Výsledkem porovnání v klasifikátoru je číslo pravidla s akcí.
• Typy vyhledávání
  • Podle dimenzí (počtu kontrolovaných polí v hlavičce)
    • vyhledávání v jedné dimenzi (1D)
    • vyhledávání ve dvou dimenzích (2D)
    • vyhledávání ve více dimenzích (nD)
  • Podle techniky vyhledávání
    • lineární vyhledávání (linear search) - často používané, časová složitost je velká, používají se různé modifikace a rozšíření, algoritmus PathFinder kombinuje lineární a stromové vyhledávání, používá se i pro více dimenzí (bitový vektor)
    • vyhledávání technikou rozděl a panuj (divide and conquer) - rozdělí úlohu na více podúloh, které vyřeší a pak složí výsledky, metoda bitového vektoru, vektorový součin, či RFC
    • stromové vyhledávání – tries, grid of tries a jejich modifikace - prohledává postupně všechny dimenze - vhodné pro 1D či 2D, pro více dimenzí se používají rozhodovací stromy, např. HiCuts
  • použití bitových vektorů (bit vector)
  • vyhledávání pomocí vektorového součinu (cross producting)
  • rozhodovací stromy (decision trees)