Modely topologie Internetu Pavel Troubil 13. prosince 2011 Pavel Troubil Modely topologie Internetu Přehled prezentace Motivace Náhodné grafy Hierarchie Power law HOT model dK-řady Pavel Troubil Modely topologie Internetu Proč se zabývat topologií Internetu? Ověřování výkonu a funkčnosti protokolů Šíření červů, botnetů Návrhy obranných mechanismů Pavel Troubil Modely topologie Internetu Metody výzkumu topologie Internetu Měření skutečné topologie Analýza traceroute, BGP Projekty Rocketfuel, Skitter Teoretická práce Hledání charakteristických vlastností Návrh algoritmů pro generování náhodných sítí Pavel Troubil Modely topologie Internetu Erdős–Rényi model Obecný model náhodných grafů G(n, p) n – počet vrcholů p – pravděpodobnost vzniku hrany Všechny hrany stejně pravděpodobné Průměrně n 2 p hran Pavel Troubil Modely topologie Internetu Waxmanův model Algoritmus Obdélníkový prostor Náhodně rozmístěné vrcholy Euklidovská vzdálenost p(u, v) = βe −d(u,v) αL , α, β ∈ [0, 1) β - počet hran α - poměr počtů krátkých/dlouhých hran Pavel Troubil Modely topologie Internetu Transit-Stub model Kritika Waxmana Grafy vizuálně nepodobné reálným sítím Hierarchie Páteř Dlouhé linky skrz síť Nespojitost Tři stupně hierarchie Tranzitní AS Koncové AS Lokální sítě Pavel Troubil Modely topologie Internetu Transit-Stub algoritmus Postup od nejvyšší úrovně dolů, pro každý prvek obdélníkový podregion Vždy generuje souvislé (pod)grafy 1. Výběr umístění tranzitních AS, vytvoření hran mezi nimi 2. Vytvoření uzlů v tranzitních AS a hran mezi nimi 3. Výběr hraničních uzlů v tranzitních AS 4. Výběr umístění koncových AS, vytvoření vnitřních uzlů a hran v AS 5. Spojení koncových a tranzitních AS 6. Výběr umístění lokálních sítí, topologie hvězda 7. Připojení lokálních sítí ke koncovým AS Pavel Troubil Modely topologie Internetu Power law v topologiích Power law Mocninný vztah dvou veličin f (x) = axk + o(xk ) Obvykle 2 ≤ k ≤ 4 Reálné příklady Síla zemětřesení Velikost kráterů na Měsíci Frekvence slov Velikost válek Pavel Troubil Modely topologie Internetu Power law v Internetu Stupeň vrcholu vs. frekvence mocnina ≈ 2,2 Počet hopů vs. počet dvojic uzlů v nejvýše této vzdálenosti mocnina ≈ 4,7 Bezškálové (scale-free) sítě Pavel Troubil Modely topologie Internetu Model Barabási-Albert Aspekty reálných sítí Růst sítě Preferované uzly Algoritmus Začni s m0 uzly Přidávej uzly s m ≤ m0 hranami Vytváří bezškálové sítě Oba předpoklady nutné Pavel Troubil Modely topologie Internetu Srovnání Barabási-Albert a Erdős–Rényi Pavel Troubil Modely topologie Internetu Kritika bezškálových sítí Omezení na posloupnost stupňů Mnoho grafů různých vlastností se stejnou posloupností Pavel Troubil Modely topologie Internetu Kritika bezškálových sítí Vznik hubů Kritické uzly sítě, kterými prochází většina provozu Spojují síť dohromady Pavel Troubil Modely topologie Internetu L(g) metrika l(g) = (i,j)∈Edges(g) di dj Uvažujme jednu posloupnost vrcholů Množina takových grafů G lmax = max{l(g) : g ∈ G} Normalizovaná metrika: L(g) = (l(g) − lmin)/(lmax − lmin) L(g) ∈ [0, 1] Vyšší L(g) ⇔ uzly vysokých stupňů spojeny Pavel Troubil Modely topologie Internetu L(g) konkrétně Pavel Troubil Modely 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 Pavel Troubil Modely topologie Internetu Přístup First-Principle Technologická omezení Ekonomický imperativ HOT - Heuristicky Optimální Topologie Přepojení grafu z Barabási-Albert modelu Výběr uzlů nižšího stupně do jádra Jejich sousedi vyšších stupňů jakožto brány Redistribuce hran mezi branami a jádrem Přepojení okrajových uzlů Pavel Troubil Modely 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 Pavel Troubil Modely topologie Internetu Vstup vs. 0K Pavel Troubil Modely topologie Internetu Vstup vs. 1K Pavel Troubil Modely topologie Internetu Vstup vs. 2K Pavel Troubil Modely topologie Internetu Vstup vs. 3K Pavel Troubil Modely topologie Internetu Generování dK-grafů Přepojování Obecná metoda pro libovolné d k2 k3 k4 k2 k3 k4 Pavel Troubil Modely topologie Internetu Generování dK-grafů Přepojování Obecná metoda pro libovolné d k2 k3 k4 k2 k3 k4 k2 k3 k4 k2 k3 k4 Pavel Troubil Modely topologie Internetu Generování dK-grafů Přepojování Obecná metoda pro libovolné d k2 k3 k4 k2 k3 k4 k2 k3 k4 k2 k3 k4 k2 k3 k4 k2 k3 k2 Pavel Troubil Modely topologie Internetu Generování dK-grafů Přepojování Obecná metoda pro libovolné d k2 k3 k4 k2 k3 k4 k2 k3 k4 k2 k3 k4 k2 k3 k4 k2 k3 k2 Hledání takových přepojení, které nezachovávají isomorfismus Pavel Troubil Modely topologie Internetu Shrnutí Obecné grafy ⇓ Zavedení hierarchie ⇓ Power law ⇓ Principy růstu ⇓ dK-rozdělení Pavel Troubil Modely topologie Internetu Děkuji za pozornost Obrázky: autoři článků, wikipedia Pavel Troubil Modely topologie Internetu Reference 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. Pavel Troubil Modely topologie Internetu