Topologie Internetu Pavel Troubil
19. listopadu 2013
Pavel Troubil
Topologie Internetu
P°ehled prezentace
I
Motivace
I
Náhodné grafy
I
Hierarchie
I
Power law
I
HOT model
I
dK-°ady
Pavel Troubil
Topologie Internetu
Co víme o podob¥ Internetu Kdy se spojují uzly v Internetu? I Uvnit° autonomních jednotek: dle pot°eb správc· I Mezi autonomními jednotkami: dle vzájemné domluvy bez centrální autority I I
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 I ádná centrální autorita neschvaluje a neeviduje budování sítí I Provozovatelé £asto necht¥jí podobu své sít¥ zve°ejnit I I I
I
Bezpe£nostní d·vody Ochrana know-how Flexibilita kon gurace
Existují výjimky (nap°. NRENs sít¥ výzkumných institucí) Pavel Troubil
Topologie Internetu
Děčín
Jablonec n. N.
Ústí n. L.
Most
Turnov
Řež
Cheb Praha
Poděbrady
Dvůr Králové
Plzeň
Humpolec Písek AMS-IX
NIX
Vodňany
Jindřichův Hradec
Krnov Opava
Česká Třebová
Ostrava Olomouc
Jihlava
Tábor
PIONIER
Hradec Králové
Pardubice Kostelec n. Č. L. Ondřejov Kutná Hora Litomyšl
Beroun
Mariánské Lázně
DWDM 100 Gb/s 10 Gb/s 1–2,5 Gb/s <1 Gb/s
Liberec
Prostějov Vyškov
Brno
Telč
Třeboň České Budějovice GÉANT
5 Gb/s
Nové Hrady
Internet
Kyjov Znojmo ACONET
Pavel Troubil
Zlín Uherské Hradiště
Lednice
Topologie Internetu
SANET
Karviná
Pavel Troubil
Topologie Internetu
Modely topologie Internetu Popis Internetu jako grafu I
Uzly I
I
Jednotlivá za°ízení, routery, autonomní systémy
Propojení na L1L3 ISO OSI I
Ohodnocení kapacitou, latencí, jitterem, velikostí buer·, . . .
Motivace I
Ov¥°ování výkonu a funk£nosti protokol·
I
í°ení £erv·, botnet·
I
Návrhy obranných mechanism·
I
Metody plánování zdroj· Pavel Troubil
Topologie Internetu
Metody výzkumu topologie Internetu M¥°ení skute£né topologie I I I
Analýza traceroute, BGP Projekty Rocketfuel, Skitter, Archipelago M¥°ící uzly, aktivní vzájemná komunikace
Teoretická práce I
I
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
Pavel Troubil
Topologie Internetu
Erd®sRényi model I
Obecný model náhodných graf·, bez p°izp·sobení sítím
I
Model I
G (n, p)
n pevný po£et
vrchol· Vrcholy jsou náhodn¥ spojovány, kaºdá dvojice nezávisle na sob¥ I p pravd¥podobnost vzniku kaºdé hrany I Pr·m¥rn¥ n p hran 2 I
I
V²echny hrany stejn¥ pravd¥podobné nerealistické I
ast¥ji se spojují blízké uzly nebo uzly podobné kapacity a významu Pavel Troubil
Topologie Internetu
Waxman·v model I I
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 I
Vygeneruj obdélníkový prostor
I
Náhodn¥ rozmísti vrcholy do tohoto prostoru (rovnom¥rné, normální £i Poissonovo rozloºení)
I
Pro kaºdou dvojici nezávisle rozhodni o hran¥
I
Pravd¥podobnost vzniku hrany je závislá na euklidovské vzdálenosti mezi vrcholy
I
−d (u ,v ) α
p(u , v ) = β e L , α, β ∈ [0, 1) I p (u , v ) pravd¥podobnost vzniku hrany mezi vrcholy u , v I d (u , v ) vzdálenost mezi vrcholy u , v I I I
α pom¥r po£t· krátkých/dlouhých hran β po£et hran L maximální moºná vzdálenost mezi uzly Pavel Troubil
Topologie Internetu
Erd®sRényi vs. Waxman
Pavel Troubil
Topologie Internetu
Model Transit-Stub Kritika Waxmanova modelu I
Grafy se vizuáln¥ nepodobají reálným sítím I I I
I
Uzly nemají ºádnou hierarchii Chybí obvyklá páte°ní sí´ Objevují se nelogické linky na dlouhé vzdálenosti
Grafy nejsou spojité I
Pouºívá se nejv¥t²í komponenta
Zavádí t°i stupn¥ hierarchie I I I
Tranzitní (Transit) AS Koncové (Stub) AS Lokální sít¥
Pavel Troubil
Topologie Internetu
Transit-Stub algoritmus I Hierarchicky spou²tí d°ív¥j²í algoritmy, obvykle Waxman·v I Také generuje vrcholy do obdélníkového prostoru I Postupuje od nejvy²²í úrovn¥ dol·, pro kaºdý prvek
obdélníkový podregion I 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 Pavel Troubil
Topologie Internetu
Power law I
Statistické ozna£ení pro vztah dvou veli£in, kdy závislá prom¥nná roste £i klesá s mocninou nezávislé prom¥nné
Power law I I
f (x ) ≈ ax k
Obvykle 1, 5 ≤ k ≤ 4
Reálné p°íklady v p°irod¥ i vytvo°ené £lov¥kem I I I I
Síla zem¥t°esení Velikost kráter· na M¥síci Frekvence slov Ob¥ti válek Pavel Troubil
Topologie Internetu
Power law v Internetu bez²kálové sít¥ I
Stupe¬ vrcholu vs. frekvence I I I
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 I
≈ (−dv )2,2
Po£et hop· vs. po£et dvojic vrchol· v nejvý²e této vzdálenosti I
I I
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
I
V²echny pozd¥j²í generátory dodrºují exponenciální vztah stupn¥ a frekvence vrcholu Pavel Troubil
Topologie Internetu
Model BarabásiAlbert Zohled¬uje dva aspekty reálných sítí I I
Sí´ od svého vzniku stále roste Preference p°ipojení k vrchol·m vy²²ího stupn¥
Algoritmus I I
Vytvo° m0 vrchol·, ºádné hrany Dokud nemá sí´ poºadovanou velikost I I
I
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 ) = P I
dv
w ∈ V dw
P°irozen¥ vytvá°í souvislé bez²kálové grafy, fv ≈ (−dv )2,9 Pavel Troubil
Topologie Internetu
Srovnání Erd®sRényi a Barabási-Albert
Pavel Troubil
Topologie Internetu
Kritika bez²kálových sítí Zachování distribude (posloupnost) stup¬· není dosta£ující I
Mnoho graf· r·zných vlastností se stejnou posloupností
Pavel Troubil
Topologie Internetu
Kritika bez²kálových sítí
Vznik hub· I
I
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.
Pavel Troubil
Topologie Internetu
L(g) metrika
l (g ) = I I
X (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 } I
Normalizovaná metrika: L(g ) = (l (g ) − lmin )/(lmax − lmin )
L(g ) ∈ [0, 1] I
Vy²²í L(g ) ⇔ vrcholy vysokých stup¬· spojeny Pavel Troubil
Topologie Internetu
L(g) konkrétn¥
BarabásiAlbert: vysoká
Náhodný graf: vysoká
HOT: nízká
Skute£ná sí´: nízká
Pavel Troubil
Topologie Internetu
Schéma páte°ní sít¥ Abilene Intermountain GigaPoP Front Range GigaPoP
Northern Lights
U. Memphis
U. Louisville
Great Plains
U. Arizona
Iowa St.
U. Hawaii
Pacific Northwest GigaPoP
Denver
Pacific Wave
Kansa s City
USGS
TransPAC/APAN
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
MANLAN
New York
GEANT
DREN
Wash D.C.
MAGPI
Los Angeles
CENIC
SINet
SURFNet
ESnet
UniNet
WPI
Indianapolis Chicago
Sunnyvale
NREN
Northern Crossroads
StarLight
Seattle
NISN
NYSERNet
WiscREN
CHECS-NET
Oregon GigaPoP
OARNET
OneNet
Qwest Labs
Arizona St.
Indiana GigaPoP
Merit
NCNI/MCNC Atlanta
Houston
North Texas GigaPoP
SOX
Texas Tech
UT Austin UT-SW Med Ctr.
UMD NGIX
SFGP/ AMPATH
Texas GigaPoP
Pavel Troubil
U. Florida U. So. Florida
Florida A&M
Tulane U.
Mid-Atlantic Crossroads
Jackson St.
Miss State GigaPoP LaNet
Drexel U.
PSC
U. So. Miss.
Topologie Internetu
DARPA BossNet
P°ístup First-Principle Jak správci staví sít¥? I
Technologická omezení I I I
I
Ekonomická omezení I I
I
I
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á 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 I
Obvyklá p°edstava provozovatel· o dobré topologii sít¥
Pavel Troubil
Topologie Internetu
Vznik HOT grafu
P°epojení grafu z Barabási-Albert modelu I I I
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?
Pavel Troubil
Topologie Internetu
dK-rozd¥lení
dK -rozd¥lení pravd¥podobnostní rozd¥lení na podgrafech velikosti d I 0K pr·m¥rný stupe¬ vrcholu I 1K rozd¥lení stup¬· vrcholu I 2K pravd¥podobnost spojení vrchol· o daných stupních I 3K rozd¥lení podgraf· o 3 vrcholech
dK -grafy I I I
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
Topologie Internetu
Vstup vs. 0K
Pavel Troubil
Topologie Internetu
Vstup vs. 1K
Pavel Troubil
Topologie Internetu
Vstup vs. 2K
Pavel Troubil
Topologie Internetu
Vstup vs. 3K
Pavel Troubil
Topologie Internetu
Generování
dK -graf·
P°epojování hran v existujícím grafu poºadovaných vlastností I
0K : zachování po£t· hran, p°esun hrany mezi libovolnými dv¥ma vrcholy k2
k2
k3
I
k4
k3
1K : zachování stup¬·, vým¥na koncových vrchol· mezi dv¥ma hranami k2
k2
k3
I
I I
k4
k4
k3
k4
2K : vým¥na jednoho 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í, která nezachovávají isomor smus 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í 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:12051218, December 2005. Albert-László Barabási and Réka Albert. Emergence of Scaling in Random Networks. Science, 286(5439):509512, 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):1449714502, October 2005. Michalis Faloutsos, Petros Faloutsos, and Christos Faloutsos. On power-law relationships of the internet topology. SIGCOMM Computer Communication Review, 29:251262, August 1999. Lun Li, David Alderson, Walter Willinger, and John Doyle. A rst-principles approach to understanding the internet's router-level topology. SIGCOMM Computer Communication Review, 34:314, August 2004. Priya Mahadevan, Dmitri Krioukov, Kevin Fall, and Amin Vahdat. Systematic topology analysis and generation using degree correlations. SIGCOMM Computer Communication Review, 36:135146, August 2006. Bernard M. Waxman. Routing of multipoint connections. IEEE Journal on Selected Areas in Communications, 6(9):16171622, August 1988. Pavel Troubil
Topologie Internetu
