Topologie Internetu Pavel Troubil 19. listopadu 2013 hled prezentace ► Motivace ► Náhodné gra ► Hierarchie ► Power law ► HOT model ► dK-řady Co víme o podobě Internetu Kdy se spojují uzly v Internetu? ► Uvnitř autonomních jednotek: dle potřeb správců Mezi autonomními jednotkami: dle vzájemné domluvy bez centrální autority ► za úplatu (připojení k ISP, mezi menším a větším ISP) ► vzájemně výhodné (výměna dat, sdílení kapacit, atd.) Dostupné informace Žádná centrální autorita neschvaluje a neeviduje budování sítí ► Provozovatelé často nechtějí podobu své sítě zveřejnit ► Bezpečnostní důvody ► Ochrana know-how ► Flexibilita konfigurace ► Existují výjimky (např. NRENs - sítě výzkumných institucí) Modely topologie Internetu Popis Internetu jako grafu ► Uzly ► Jednotlivá zařízení, routery, autonomní systémy ► Propojení na L1-L3 ISO OSI ► Ohodnocení kapacitou, latencí, jitterem, velikostí bufferů, ... Motivace ► Ověřování výkonu a funkčnosti protokolů ► Šíření červů, botnetů Návrhy obranných mechanismů ► Metody plánování zdrojů Metody výzkumu topologie Internetu Měření skutečné topologie ► Analýza traceroute, BGP ► Projekty Rocketfuel, Skitter, Archipelago ► Měřící uzly, aktivní vzájemná komunikace Teoretická práce ► Hledání charakteristických vlastností a jevů v naměřených datech ► Návrh algoritmů pro generování náhodných sítí s nalezenými charakteristikami Erdós—Rényi model ► Obecný model náhodných grafů, bez přizpůsobení sítím ► Model G{n,p) *■ n - pevný počet vrcholů ► Vrcholy jsou náhodně spojovány, každá dvojice nezávisle na sobě *■ p - pravděpodobnost vzniku každé hrany ► Průměrně (!J)p hran ► Všechny hrany stejně pravděpodobné - nerealistické ► Častěji se spojují blízké uzly nebo uzly podobné kapacity a významu Waxmanův model ► První model náhodného generování grafu s přihlédnutím k síti ► Oproti obecnému modelu není vznik všech hran stejně pravděpodobný Algoritmus ► Vygeneruj obdélníkový prostor ► Náhodně rozmísti vrcholy do tohoto prostoru (rovnoměrné, normální či Poissonovo rozložení) ► Pro každou dvojici nezávisle rozhodni o hraně ► Pravděpodobnost vzniku hrany je závislá na euklidovské vzdálenosti mezi vrcholy ► P{u,v) = pe=*äčí, a, p e [0,1) ► p(u, v) - pravděpodobnost vzniku hrany mezi vrcholy u, v *■ d(u, v) - vzdálenost mezi vrcholy u, v *■ a — poměr počtů krátkých/dlouhých hran *■ 13 - počet hran *■ L - maximální možná vzdálenost mezi uzly Erdós—Rényi vs. Waxma Model Transit-Stub Kritika Waxmanova modelu ► Grafy se vizuálně nepodobají reálným sítím ► Uzly nemají žádnou hierarchii ► Chybí obvyklá páteřní síť ► Objevují se nelogické linky na dlouhé vzdálenosti ► Grafy nejsou spojité ► Používá se největší komponenta Zavádí tři stupně hierarchie ► Tranzitní (Transit) AS ► Koncové (Stub) AS ► Lokální sítě Transit-Stub algoritmus Hierarchicky spouští dřívější algoritmy, obvykle Waxmanův ► Také generuje vrcholy do obdélníkového prostoru ► Postupuje od nejvyšší úrovně dolů, pro každý prvek obdélníkový pod region ► Vždy generuje souvislé grafy 1. Vytvoř tranzitní AS (vrcholy) a hrany mezi nimi 2. Každý vrchol nahraď náhodným souvislým grafem (páteř tranzitního AS) 3. Pro každý vrchol (síťový prvek v tranzitním AS) vygeneruj několik koncových AS 4. Ke koncovým AS připoj lokální sítě s topologií hvězdy 5. Náhodně přidej několik hran spojujících koncové AS, nebo koncový a transitní AS Power law ► Statistické označení pro vztah dvou veličin, kdy závislá proměnná roste či klesá s mocninou nezávislé proměnné Power law ► f(x) axk ► Obvykle 1,5 < k < 4 Reálné příklady v přirodě i vytvořené člověkem ► Síla zemětřesení ► Velikost kráterů na Měsíci ► Frekvence slov ► Oběti válek Power law v Internetu - bezškálové sítě ► Stupeň vrcholu vs. frekvence *■ dv - stupeň vrcholu *■ fv - frekvence vrcholů stupně dv *■ Vrcholy vysokého stupně jsou velmi výjimečné. Frekvence vrcholů roste s klesajícím stupněm fv « (-dv)2>2 ► Počet hopů vs. počet dvojic vrcholů v nejvýše této vzdálenosti ► P(h) - počet dvojic vrcholů ve vzdálenosti nejvýše h (měřeno počtem hopů, tj. hran na cestě) ► P(l) - počet hran v grafu ► Počet dvojic vrcholů, které jsou vzájemně dosažitelné v h hopech, roste s h P(h) « /?4'7 ► Všechny pozdější generátory dodržují exponenciální vztah stupně a frekvence vrcholu Model Barabási-Albert Zohledňuje dva aspekty reálných sítí ► Síť od svého vzniku stále roste ► Preference připojení k vrcholům vyššího stupně Algoritmus ► Vytvoř mo vrcholů, žádné hrany ► Dokud nemá síť požadovanou velikost ► Přidej 1 vrchol ► Připoj ho hranou k m < mo vrcholům ► Pravděpodobnost připojení je přímo úměrná stupni vrcholu ž^wev "w ► Přirozeně vytváří souvislé bezškálové grafy, fv ~ (—dv)2'9 Srovnání Erdos-Rényi a Barabási-Albert Kritika bezškálových sítí Zachování distribude (posloupnost) stupňů není dostačující ► Mnoho grafů různých vlastností se stejnou posloupností < U k 4 & k 4 = * 4 = k 3 -0(^(> Kritika bezškálových sítí Vznik hubů ► Kritické uzly sítě, kterými prochází většina provozu. Tvoří úzké hrdlo. ► Spojují síť dohromady, jejich výpadek vede k zásadnímu omezení konektivity. L(g) metrika /(*)= Y, d