Topologie Internetu
Luděk Matyska
autor prezentace: Pavel Troubil
22. listopadu 2018
Luděk Matyska autor prezentace: Pavel Troubil ·Topologie Internetu ·22. listopadu 2018 1 / 31
Přehled prezentace
Motivace
Náhodné grafy
Hierarchie
Power law
HOT model
dK-řady
Luděk Matyska autor prezentace: Pavel Troubil ·Topologie Internetu ·22. listopadu 2018 2 / 31
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 ·22. listopadu 2018 3 / 31
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 ·22. listopadu 2018 4 / 31
Luděk Matyska autor prezentace: Pavel Troubil ·Topologie Internetu ·22. listopadu 2018 5 / 31
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 ·22. listopadu 2018 6 / 31
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 ·22. listopadu 2018 7 / 31
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 ·22. listopadu 2018 8 / 31
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 ·22. listopadu 2018 9 / 31
Erdős–Rényi vs. Waxman
Luděk Matyska autor prezentace: Pavel Troubil ·Topologie Internetu ·22. listopadu 2018 10 / 31
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 ·22. listopadu 2018 11 / 31
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 ·22. listopadu 2018 12 / 31
Transit-Stub algoritmus
Luděk Matyska autor prezentace: Pavel Troubil ·Topologie Internetu ·22. listopadu 2018 13 / 31
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 ·22. listopadu 2018 14 / 31
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 ·22. listopadu 2018 15 / 31
Počet uzlů připojených k Internetu
Luděk Matyska autor prezentace: Pavel Troubil ·Topologie Internetu ·22. listopadu 2018 16 / 31
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 ·22. listopadu 2018 17 / 31
Srovnání Erdős–Rényi a Barabási-Albert
Luděk Matyska autor prezentace: Pavel Troubil ·Topologie Internetu ·22. listopadu 2018 18 / 31
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 ·22. listopadu 2018 19 / 31
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 ·22. listopadu 2018 20 / 31
L(g) metrika
l(g) =
(i,j)∈E(g)
didj
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 ·22. listopadu 2018 21 / 31
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 ·22. listopadu 2018 22 / 31
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 ·22. listopadu 2018 23 / 31
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 ·22. listopadu 2018 24 / 31
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 ·22. listopadu 2018 25 / 31
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 ·22. listopadu 2018 26 / 31
dk-Distribuce
Orsini et al: Quantifying randomness in real networks
http://www.nature.com/articles/ncomms9627
Luděk Matyska autor prezentace: Pavel Troubil ·Topologie Internetu ·22. listopadu 2018 27 / 31
Vstup vs. dK - grafy
Vstup
2K
1K
3K
Luděk Matyska autor prezentace: Pavel Troubil ·Topologie Internetu ·22. listopadu 2018 28 / 31
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 ·22. listopadu 2018 29 / 31
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 ·22. listopadu 2018 30 / 31
Zajímavé články
[1] 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.
[2] Albert-László Barabási and Réka Albert.
Emergence of Scaling in Random Networks.
Science, 286(5439):509–512, 1999.
[3] 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.
[4] Michalis Faloutsos, Petros Faloutsos, and Christos Faloutsos.
On power-law relationships of the internet topology.
SIGCOMM Computer Communication Review, 29:251–262, August 1999.
[5] 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.
[6] 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.
[7] 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 ·22. listopadu 2018 31 / 31