Kvantitativní analýza internetového provozu (7)
Ladislav Lhotka {IhotkaQjcesnet. cz)
Osnova přednášky
•  Fraktály a multifraktály
•  Histogramová metoda
•  Model
•  Přehled otázek ke zkoušce
•  Q&A
2
Fraktální struktura adres
0-10       10-20      20-30      30-40      40-50      50-60      60-70      70-80      80-90    90-100   %
Dělíme adresový rozsah na 2P prefixů délky p, pro p prefixů obsahujících aspoň jednu adresu ze vzorku
1,2,..., 32. Počet
IN p ~
2dp
Fraktální dimenze (box-counting dimension)
log2Np
D =
P
Určení ze vzorku
Vzorek z okruhu GN2, D « 0,65 jako směrnice tečny.
(M
C Ü
00    —
CD    —
Index
4
■ÍJUi
D <
O
Oe+00
o
CD      _
+
O
CC-
1e+09 ___I___
Destination IP
2e+09
_
3e+09
___I___
4e+09
___L
OJ
«BBCOOO       003300g
O N
3
3
CDs
Q_
CD r+ QJ
c e   é o
Ln
Odhad dimenze pro obě adresy
flows <- read.csv("../4-081103/gn2-flows-lOge.data",
col.names=c("source","dest","proto","sip","dip",
"sport","dport","packets","bytes")) adresy <- flows[c("sip","dip")] lent <- c() for (p in 1:32) {
lent <- c(log2(length(unique(adresy)$dip)),lent)
adresy <- adresy %/% 2
}
plot(lcnt, xlab="Prefix length p", ylab="log2(Np)")
p <- 3:13
np <- lcnt[p]
fit <- lm(np ~ p)
abline(coef(fit))
6
CD
CM
CM O
CO
CD
CM
ooooooooooo
0             5             10            15           20           25           30
Prefix length p
D ^0,76
7
Váha prefixů
Výpočet fraktální dimenze bere v úvahu pouze, zda je daný prefix /p ve vzorku vůbec zastoupen, tj. zda obsahuje aspoň jednu cílovou adresu patřící do prefixu /p.
Různé prefixy ale zdaleka nemají stejnou váhu, pro detailnější analýzu je tedy potřeba brát v úvahu např. kolik (i) adres, (ii) paketů nebo (iii) bajtů patří do daného prefixu.
Pro tento účel se definuje míra \i, která může, ale nemusí být normována na 1.
8
Adresy v prefixech /8
c
o Ü
to to
CD
i_
T3
<
o o CN					o o	o
O O LO					o o	
O O O					%	
O o   -LO o   -	o o	o o	<a>	o        o o	o° o     ° °°rvP s©         o^oeP	o o o o o ^    o % °
			1	1	1	1
50
100
150
200
Prefixes /8
(D 10
o
j_
"D
-í CD
X'
CD V)
en
o o o o
K3
o o o o
CO
o o o o
o o o o
en o o o o
en o o o o
50
l
o
Address count
100
150
200
250
o
o
00   o o©   oo
o
o
0 OO    oo Qj
O       O        o
o
o
<
TD
fD 3l X fD
n
cn
o
Adresy v prefixech /24
c
o Ü
to to
CD
i_
T3
<
o
LO
CN
O O CN
O LO
O O
O LO
O    -
0.0e+00
5.0e+06
1.0e+07
1.5e+07
Prefixes /24
11
Rel. počty paketů v prefixech /8
c
o Ü
-I—» CD
.*:
o co
Q.
CD >
03 CD
50
100
150
200
Prefixes /8
12
Rel. počty paketů v prefixech /16
	O
	t-    —
	O
	co
	O    -
-1—'	o
c	
D	
o	
o	
-1—'	CD
CD V	O    -
o	o
co	
SS-	
CD	
>	
	'vT
co	O    -
CD	O
QĹ	
	CN
	O    -
	O
	O
	O    -
10000  20000  30000  40000  50000  60000
Prefixes /16
13
Rel. počty paketů v prefixech /24
c
o Ü
-I—» CD
.*:
o co
Q.
CD >
03 CD
				o	
o					
Ö					
00 O    -					
Ö				o	
CD o   _					
Ö					
O    -					
Ö				o	O
0.00          0.02 l                 l	o é	ODO	O o dfenQBHDDO 1	o 1	o 9o o Mm* i
0.0e+00
5.0e+06
1.0e+07
1.5e+07
Prefixes /24
14
Multifraktální míra
Podobně jako u fraktální dimenze dělíme adresový rozsah na prefixy délky /p a sledujeme, jaká je míra každého prefixu a jak rychle klesá s rostoucím p. Tato charakteristika je zřejmě závislá na pozici v adresovém rozsahu:
\i{a/v) ^2-voc[a]
Holderův exponent:
log2(i4a/p)) (x(a) =-------------------
P Zajímá nás relativní zastoupení jednotlivých hodnot a:
■p
Charakteristika míry:
f(a)
Np(cx) ~
«3 2vi^
log2Np(g) P
15
Histogramová metoda
1.  Při rozdělení adresového prostoru na prefixy délky p spočítej Hölde-rův exponent pro každý prefix Pt (i = 1, 2,... ,2P):
OCi =--------------------------------
p
2.  Vytvoř histogram hodnot otif tj. rozděl celý rozsah hodnot a na intervaly a zjisti počet hodnot Np(a) v každém intervalu.
3.  Nakresli graf (aproximace) funkce f (a) = log2Np(a)/p.
4.  Postup opakuj pro různá p.
16
Algoritmus v R
flows <- read.csv("../4-081103/gn2-flows-lOge.data", col.names=c("source","dest","proto","sip","dip", "sport","dport","packets","bytes"))
udip <- unique(flows$dip)
totad <- length(udip)
p <- 16
pref <- rle(sort(udip %/% 2**p))
mu <- pref$length / totad
alfa <- -log2(mu) / p
hist <- hist(alfa, breaks=1000)
plot(hist$mids, log2(hist$counts)/p)
17
Výsledky Kohler et al.
V konstrukci Cantorovy množiny lze délkou h vyjmutého prostředního intervalu regulovat fraktální dimenzi:
log^l -H)
Fraktální model: "zředit" adresový prostor na Cantorovu množinu s fraktální dimenzí shodnou s dimenzí cílových adres ve vzorku.
Spekulativní konstrukce, není žádný důvod k tomu, aby adresy ve vzorku měly kvalitativně strukturu Cantorovy množiny.
18
Multifraktální spektrum (Kohler)
0.8

Rl
Cantor-like set, D = 0.79 Rl Model
0.6         0.7         0.8
Scaling exponent
1.1
19
Multifraktální model
Stejná konstrukce "Cantorova ředění" adresového prostoru, v každém kroku se ale oběma zbývajícím částem přiřadí míry (= pravděpodobnost výskytu adresy) mo a 1 - mo. Parametr mo je odhadnut tak, aby jeho multifraktální spektrum co nejlépe souhlasilo s modelovaným vzorkem.
20