Kvantitativní analýza
internetového provozu (6)
Ladislav Lhotka
lhotka@cesnet.cz
Osnova přednášky
* Struktura IP adres ve vzorcích
* Fraktální dimenze
* Multifraktály
2
Struktura adres ve vzorcích
Kohler et al. Observed structure of addresses in IP traffic. IEEE
Transaction on Networking 14(6), 2006, p. 1207­1218.
Adresový agregát pro prefix délky p: množina adres shodujících se v
prvních p bitech. Zápis: 147.251.0.0/16, nebo jen 147.251/16.
Každý p-agregát obsahuje 232-p
adres. Kratší prefix znamená větší množinu
adres!
Rozložení adres ukazuje zajímavé struktury na všech úrovních rozlišení
(= délka prefixu).
3
Vzorek provozu (4 h.) z přípoje
velké univerzity, 62 mil. paketů.
4
Praha­Brno 10 Gbps
16
15
14
13
12
11
10
9
8
7
6
5
4
3
2
1
0-10 10-20 20-30 30-40 40-50 50-60 60-70 70-80 80-90 90-100 %
5
147.0.0.0/8
16
15
14
13
12
11
10
9
8
7
6
5
4
3
2
1
0-10 10-20 20-30 30-40 40-50 50-60 60-70 70-80 80-90 90-100 %
6
147.224.0.0/12
12
11
10
9
8
7
6
5
4
3
2
1
0-10 10-20 20-30 30-40 40-50 50-60 60-70 70-80 80-90 90-100 %
7
147.231.204.0/21
11
10
9
8
7
6
5
4
3
2
1
0-10 10-20 20-30 30-40 40-50 50-60 60-70 70-80 80-90 90-100 %
8
Cantorova množina
.
.0 .1
.0 .1
.0 .1
.0 .1
Z uzavřeného intervalu [0, 1] vyjmeme
prostřední třetinu, z obou
částí [0, 1/3] a [2/3, 0] znovu prostřední
třetinu atd.
Výsledkem limitního procesu této konstrukce je Cantorova množina,
která je nekonečná a má dokonce stejnou mohutnost jako celý interval
[0, 1] ( = nespočetná). Přitom neobsahuje žádný otevřený interval, takže
její celková délka (míra) je 0.
9
Fraktální dimenze
Eukleidovské objekty mají celočíselnou dimenzi ­ 0 (bod), 1 (úsečka, kružnice,
. . .), 2 (obdélník, kruh, . . .). U některých "podivných" objektů ale
intuitivně cítíme, že jejich dimenze je někde mezi.
Například Cantorova množina je více než soubor izolovaných bodů, ale
méně než úsečka.
Sierpińského síto:
Reálné objekty: pobřežní čára, tepny a žíly v těle, atd.
10
Výpočet fraktální dimenze
Kolmogorovova kapacita, box-counting dimension
Omezenou množinu A v prostoru dimenze n uzavřeme do n-rozměrné
krychle a její stranu prohlásím ze jednotkovou délku.
Tuto krychli rozdělíme na síť krychliček o straně  (jejich celkový počet je
tedy 1/n
).
N(A) je počet krychliček obsahujících aspoň jeden bod množiny A.
Zmenšujeme-li , N(A) roste úměrně s nějakou mocninou :
N(A)  -D(A)
.
Číslo D(A) nazveme fraktální dimenze množiny A.
D(A) = - lim
0
log N(A)
log 
(1)
U eukleidovských objektů odpovídá jejich geometrické dimenzi, pro Cantorovu
množinu je log 2/ log 3  0, 63.
11
Odhad fraktální dimenze z dat
Pro naměřená data nemá limita žádný smysl, můžeme ale sledovat, jak
se na nějaké konečné škále chová log N(A) proti log . Směrnice tečny
rozumně blízko 0 udává odhad fraktální dimenze.
Postup pro IP adresy (A je množina všech zjištěných adres): 32-bitový
adresový prostor dělíme postupně na 2, 4, 8, . . . části. V p-tém kroku
tedy máme (232
je pro nás jednotka délky)
p = 232-p
/232
= 2-p
Každá "krychlička" v p-tém kroku představuje p-agregát, Np
(A) = Np je
tedy počet prefixů délky p obsahujících aspoň jednu adresu ze vzorku.
D(A) = lim
p
log Np
p log 2
= lim
p
log2 Np
p.
12
Odhad fraktální dimenze vzorků Kohler et al.
Fraktální dimenze vzorku R1 (regionální ISP) je 0,79.
13
Výpočet v R
flows <- read.csv("../4-081103/gn2-flows-10ge.data",
col.names=c("source", "dest","proto","sip","dip",
"sport","dport","packets","bytes"))
dip <- flows$dip
lcnt <- c()
for (p in 1:32) {
lcnt <- c(log(length(unique(dip)), base=2), lcnt)
dip <- dip %/% 2
}
plot(lcnt)
p <- 5:15
np <- lcnt[p]
fit <- lm(np ~ p)
abline(coef(fit))
14
Multifraktály
Fraktální dimenze je založena na počítání krychliček, které obsahují nějaký
bod. Co když ale různé body nemají stejnou váhu?
Míra  na množině A je zobrazení, které podmnožinám přiřazuje nějaké
číslo (váhu). V našich aplikacích to může být např. množinou A adresový
prostor a mírou počet paketů příslušejících cílovým adresám dané
podmnožiny (např. p-agregátu).
Například ve vzorku GN2
(192.8.0.0/16) = 55954.
Obvykle nás zajímá, jak se mění míra v okolí nějakého bodu x v závislosti
na velikosti tohoto okolí (hustota míry). V případě tzv. multifraktálních
měr se toto chování často rychle mění podle toho, v jakém bodě x se
nacházíme:
(Bx())  (x)
,
kde Bx() je okolí bodu x (např. krychlička) o objemu .
15
Hölderův exponent
(x) = lim
0
(Bx())

V praktických případech, jako je struktura IP adres, ale nemá limita
význam, proto pracujeme s hrubým Hölderovým exponentem (coarsegrained
H. e.)
(x) =
(Bx())

.
Chceme nyní posčítat krychličky vždy jen s jednou hodnotou H. e. Ukazuje
se, že pro počet výskytů dané hodnoty  platí u multifraktálních měr
vztah
N()  -f()
Funkce f() nezávisí na  a je zobecněním fraktální dimenze.
16
Multiplikativní kaskáda
Původně rovnoměrně rozdělená pravděpodobnostní
míra na intervalu [0, 1] je
rozdělena v poměru m0 : m1 mezi levou
a pravou polovinu, přičemž m0 + m1 = 1.
V každé z těchto polovin je míra rozdělena
v poměru m0 : m1 mezi levou a
pravou čtvrtinu atd.
Značení subintervalů v k-tém kroku:
I0.00...k
je interval velikosti 2-k
, jehož všechny
body mají ve dvojkové soustavě stejný
začátek uvedený v indexu. Index tedy
představuje jeho levý krajní bod.
17
Míry subintervalů
Značíme
0.00...k
= (I0.00...k
) = mn0
0 mn1
1 ,
kde n0 je počet nul a n1 počet jedniček ve dvojkovém rozvoji čísla
0.00 . . . k.
Zajímá nás, jak se s rostoucím k mění závislost míry intervalu vpravo od
nějakého bodu x = 0.00 . . . k v závislosti na jeho délce (2-k
):
0.00...k
= (2-k
)(
n0
k v0+
(k-n0)
k v1)
,
kde v0 = - log2 m0 a v1 = - log2 m1. Hodnoty v0 a v0 nezávisejí na k.
Hölderův exponent:
(x) =
n0
k
v0 +
(k - n0)
k
v1)
Předpokládejme, že m0  m1. Pak platí
v0  (x)  v1.
18
Rozložení hodnot Hölderova exponentu
Při daném k, kolik bodů x má H. e. rovný dané hodnotě ?
Nk() =
(
k
n0
)
Výpočtem se dá ukázat, že tato hodnota aproximovat takto:
Nk()  (2-k
)-f()
,
kde
f() = -(
v1 - 
v1 - v0
) log2(
v1 - 
v1 - v0
) - (
 - v0
v1 - v0
) log2(
 - v0
v1 - v0
)
19
2 4 6 8 10
0.2
0.4
0.6
0.8
1.0
20