Topologie Internetu Luděk Matyska autor prezentace: Pavel Troubil 23. listopadu 2017 Luděk Matyska autor prezentace: Pavel Troubil Topologie Internetu Přehled prezentace Motivace Náhodné grafy Hierarchie Power law HOT model dK-řady Luděk Matyska autor prezentace: Pavel Troubil Topologie Internetu 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í) Luděk Matyska autor prezentace: Pavel Troubil Topologie Internetu Praha Liberec PardubicePardubice Č. TřebováČ. Třebová Hradec KrálovéHradec Králové Brno Olomouc Ostrava Opava NIX.CZ Internet Cheb Poděbrady Lázně Bohdaneč Lázně Bohdaneč Kuks Turnov GÉANT AMS-IX Písek Příbram Budkov SANET ACONET PIONIER Kyjov Jihlava Humpolec ŘežŘež TerezínTerezín Kralupy Děčín Ústí n. L. Plzeň Beroun Blatná Klatovy Temelín Dolní Břežany Poněšice M. Třebová Litomyšl Letohrad Karviná Český Těšín Nový Hrádek Zlín Vyškov Lednice Břeclav České Budějovice Vodňany Nové Hrady Jindřichův Hradec Tábor Třeboň Telč Most Litvínov Kostelec n.Č.L. Ondřejov Komorní Hrádek JenštejnMariánské Lázně Kašperské Hory Jablonec n. N. Uherské Hradiště 100 Gb/s 10 Gb/s 1–2,5 Gb/s <1 Gb/s n×100 Gb/s n×10 Gb/s uzel (PoP) uživatel (user) Luděk Matyska autor prezentace: Pavel Troubil Topologie Internetu Luděk Matyska autor prezentace: Pavel Troubil Topologie Internetu 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ů Luděk Matyska autor prezentace: Pavel Troubil Topologie Internetu 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 Luděk Matyska autor prezentace: Pavel Troubil Topologie Internetu 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ě n 2 p hran Všechny hrany stejně pravděpodobné – nerealistické Častěji se spojují blízké uzly nebo uzly podobné kapacity a významu Luděk Matyska autor prezentace: Pavel Troubil Topologie Internetu 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) = βe −d(u,v) αL , α, β ∈ [0, 1) p(u, v) – pravděpodobnost vzniku hrany mezi vrcholy u, v d(u, v) – vzdálenost mezi vrcholy u, v α – poměr počtů krátkých/dlouhých hran β – počet hran L – maximální možná vzdálenost mezi uzly Luděk Matyska autor prezentace: Pavel Troubil Topologie Internetu Erdős–Rényi vs. Waxman Luděk Matyska autor prezentace: Pavel Troubil Topologie Internetu 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ě Luděk Matyska autor prezentace: Pavel Troubil Topologie Internetu 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ý podregion 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 Luděk Matyska autor prezentace: Pavel Troubil Topologie Internetu Transit-Stub algoritmus Luděk Matyska autor prezentace: Pavel Troubil Topologie Internetu 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 Luděk Matyska autor prezentace: Pavel Troubil Topologie Internetu 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(1) – počet hran v grafu Počet dvojic vrcholů, které jsou vzájemně dosažitelné v h hopech, roste s h P(h) ≈ h4,7 Všechny pozdější generátory dodržují exponenciální vztah stupně a frekvence vrcholu Luděk Matyska autor prezentace: Pavel Troubil Topologie Internetu Počet uzlů připojených k Internetu Luděk Matyska autor prezentace: Pavel Troubil Topologie Internetu 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ř m0 vrcholů, žádné hrany Dokud nemá síť požadovanou velikost Přidej 1 vrchol Připoj ho hranou k m ≤ m0 vrcholům Pravděpodobnost připojení je přímo úměrná stupni vrcholu p(u, v) = dv w∈V dw Přirozeně vytváří souvislé bezškálové grafy, fv ≈ (−dv )2,9 Luděk Matyska autor prezentace: Pavel Troubil Topologie Internetu Srovnání Erdős–Rényi a Barabási-Albert Luděk Matyska autor prezentace: Pavel Troubil Topologie Internetu Kritika bezškálových sítí Zachování distribuce (posloupnost) stupňů není dostačující Barabási–Albert HOT GRG graf Skutečná síť Luděk Matyska autor prezentace: Pavel Troubil Topologie Internetu 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. Luděk Matyska autor prezentace: Pavel Troubil Topologie Internetu L(g) metrika l(g) = (i,j)∈E(g) di dj Uvažujme jednu posloupnost stupňů (d1, d2, . . . , dn) Množina grafů G, všechny s touto posloupností stupňů lmax = max{l(g) : g ∈ G} lmin = min{l(g) : g ∈ G} Normalizovaná metrika: L(g) = (l(g) − lmin)/(lmax − lmin) L(g) ∈ [0, 1] Vyšší L(g) ⇔ vrcholy vysokých stupňů spojeny Luděk Matyska autor prezentace: Pavel Troubil Topologie Internetu L(g) konkrétně Barabási–Albert: vysoká HOT: nízká GRG graf: nižší Skutečná síť: nízká Luděk Matyska autor prezentace: Pavel Troubil Topologie Internetu Schéma páteřní sítě Abilene SOX U. Florida U. So. Florida Miss State GigaPoP WiscREN SURFNet MANLAN Northern Crossroads Mid-Atlantic Crossroads Drexel U. NCNI/MCNC MAGPI UMD NGIX Seattle Sunnyvale Los Angeles Houston Denver Kansas City Indian- apolis Atlanta Wash D.C. Chicago New York OARNET Northern Lights Indiana GigaPoP MeritU. Louisville NYSERNet U. Memphis Great Plains OneNet U. Arizona Qwest Labs CHECS-NET Oregon GigaPoP Front Range GigaPoP Texas Tech Tulane U. Texas GigaPoP LaNetUT Austin CENIC UniNet NISN Pacific Northwest GigaPoP U. Hawaii Pacific Wave TransPAC/APAN Iowa St. Florida A&M UT-SW Med Ctr. SINetWPI Star- Light Intermountain GigaPoP Abilene Backbone Physical Connectivity (as of August 2004) 0.1-0.5 Gbps 0.5-1.0 Gbps 1.0-5.0 Gbps 5.0-10.0 Gbps DREN Jackson St. NREN USGS U. So. Miss. PSC DARPA BossNet SFGP/ AMPATH Arizona St. ESnet GEANT North Texas GigaPoP Luděk Matyska autor prezentace: Pavel Troubil Topologie Internetu Přístup First-Principle Jak správci staví sítě? Technologická omezení Routery dostupné na trhu Kompromis mezi celkovou propustností a stupněm vrcholu Se stupněm neklesá jen propustnost pro každé připojení, ale propustnost celková Ekonomická omezení Provoz fyzických linek je drahý Snaha o maximální agregaci do linek vyšších kapacit co nejblíže koncovým uzlům Páteř tvoří relativně málo dlouhých linek vysokých kapacit HOT - Heuristicky Optimální Topologie Obvyklá představa provozovatelů o dobré topologii sítě Luděk Matyska autor prezentace: Pavel Troubil Topologie Internetu Vznik HOT grafu Přepojení grafu z Barabási-Albert modelu Výběr 50 centrálních uzlů nižšího stupně do jádra Jejich sousedi vyšších stupňů jakožto brány Redistribuce hran mezi branami a jádrem (rovnoměrná distribuce kapacity mezi brány) Jak tyto vlastnosti popsat matematicky? Luděk Matyska autor prezentace: Pavel Troubil Topologie Internetu dK-rozdělení dK-rozdělení – pravděpodobnostní rozdělení na podgrafech velikosti d 0K – průměrný stupeň vrcholu 1K – rozdělení stupňů vrcholu 2K – pravděpodobnost spojení vrcholů o daných stupních 3K – rozdělení podgrafů o 3 vrcholech dK-grafy množina grafů se stejným dK-rozdělením jako vstupní graf 3K(g) ⊆ 2K(g) ⊆ 1K(g) ⊆ 0K(g) nK – identický graf Luděk Matyska autor prezentace: Pavel Troubil Topologie Internetu dk-Distribuce Orsini et al: Quantifying randomness in real networks http://www.nature.com/articles/ncomms9627Luděk Matyska autor prezentace: Pavel Troubil Topologie Internetu Vstup vs. dK - grafy Vstup 2K 1K 3K Luděk Matyska autor prezentace: Pavel Troubil Topologie Internetu Generování dK-grafů Přepojování hran v existujícím grafu požadovaných vlastností 0K: zachování počtů hran, přesun hrany mezi libovolnými dvěma vrcholy k2 k3 k4 k2 k3 k4 1K: zachování stupňů, výměna koncových vrcholů mezi dvěma hranami k2 k3 k4 k2 k3 k4 2K: výměna jednoho z koncových vrcholů stejného stupně mezi dvěma hranami ki značí stupeň příslušného vrcholu Opakovaný náhodný výběr přepojení, bez isomorfismu Luděk Matyska autor prezentace: Pavel Troubil Topologie Internetu Shrnutí vývoje Obecné náhodné grafy ⇓ Pravděpodobnost hrany závislá na vzdálenosti vrcholů ⇓ Zavedení hierarchie ⇓ Power law ⇓ Principy růstu ⇓ dK-rozdělení Luděk Matyska autor prezentace: Pavel Troubil Topologie Internetu Zajímavé články David Alderson, Lun Li, Walter Willinger, and John C. Doyle. Understanding internet topology: principles, models, and validation. IEEE/ACM Transactions on Networking, 13:1205–1218, December 2005. Albert-László Barabási and Réka Albert. Emergence of Scaling in Random Networks. Science, 286(5439):509–512, 1999. John C. Doyle, David L. Alderson, Lun Li, Steven Low, Matthew Roughan, Stanislav Shalunov, Reiko Tanaka, and Walter Willinger. The "robust yet fragile"nature of the Internet. Proceedings of the National Academy of Sciences of the United States of America, 102(41):14497–14502, October 2005. Michalis Faloutsos, Petros Faloutsos, and Christos Faloutsos. On power-law relationships of the internet topology. SIGCOMM Computer Communication Review, 29:251–262, August 1999. Lun Li, David Alderson, Walter Willinger, and John Doyle. A first-principles approach to understanding the internet’s router-level topology. SIGCOMM Computer Communication Review, 34:3–14, August 2004. Priya Mahadevan, Dmitri Krioukov, Kevin Fall, and Amin Vahdat. Systematic topology analysis and generation using degree correlations. SIGCOMM Computer Communication Review, 36:135–146, August 2006. Bernard M. Waxman. Routing of multipoint connections. IEEE Journal on Selected Areas in Communications, 6(9):1617–1622, August 1988. Luděk Matyska autor prezentace: Pavel Troubil Topologie Internetu