Scale free Internet Traffic

Multivariate SelfSimilarity

Multivariate Traffic

Anomaly detection

Conclusions

Scale-free dynamics in Internet traffic The benefits of multivariate analysis ?

ution du système Vélo’v

Modèle statistiquePrédiction à l’heure

Conclusion

Patrice Abry(1,2) , Romain Fontugne(3) , Gustavo Didier(4) ,Première approche :Herwig Wendt(5) , Kensuke Fukuda(2) , Kenjiro Cho(3)Introduction

Classical Analysis

Robust Analysis w/ Sketches

Analyse du nombre de locations de Vélo’v
Introduction

Classical Analysis

Robust Analysis w/ SketchesLongitudinal Study

Longitudinal Study

Conclusion

Conclusion

Seven Years and One Day:
(1)
Sketching
the Evolutionof Internet
Traffic
CNRS, Ecole
NormaleSupérieurede Lyon, France
Seven Years and One Day:
PierreSevenB ORGNAT
Years
and One Day:
(2) National
Institute of Informatics, Tokyo,Sketching
Japan the Evolution of Internet Traffic
Sketchingthe
EvolutionofInternet
Traffic
1(3)
CNRS – ENS Lyon, Laboratoire de Physique (UMR5672), Université de1Lyon
Introduction

Classical Analysis

Robust Analysis w/ SketchesLongitudinal StudyCon

Pierre B ORGNAT , Guillaume D EWAELEIXXI (Institut des Systèmes Complexes de Lyon)
Kensuke(4) F UKUDA 2 , Patrice A BRY 1 Kenjiro C HO 3

Internet Initiative Japan, Tokyo, Japan
Tulane University, New Orleans, USA Pierre BORGNAT 1, Guillaume DEWAELE 1
1 , Guillaume D EWAELE 1
Kensuke F UKUDA 2 , Patrice A BRY 1 Kenjiro C HO 3
PierreB ORGNAT(5) CNRS,
23 octobre
2009
CNRS – ENS Lyon
Physics Lab., IRIToulouse,
Université de Lyon, FranceFrance–
2
Kensuke F UKUDA , Patrice A BRY 1 Kenjiro C HO 3
1

2 NII, Tokyo, Japan – 3 IIJ Internet Initiative Japan.

1 CNRS – ENS Lyon Physics Lab., Université de Lyon, France –2 NII, Tokyo, Japan – 3 IIJ Internet Initiative Japan.

1 CNRS – ENS Lyon Physics Lab., Université de Lyon, France –INFOCOM 2009

2 NII, Tokyo, Japan – 3 IIJ Internet Initiative Japan.

ECOLE NORMALE SUPERIEURE DE LYONINFOCOM 2009

INFOCOM 2009

CENTRE NATIONALDE LA RECHERCHESCIENTIFIQUECENTRE NATIONALDE LA RECHERCHESCIENTIFIQUE

ECOLE NORMALE SUPERIEURE DE LYONECOLE NORMALE SUPERIEURE DE LYON

CENTRE NATIONALDE LA RECHERCHESCIENTIFIQUE

ECOLE NORMALE SUPERIEURE DE LYON

Introduction

Introduction

Classical Analysis

Robust Analysis w/ SketchesLongitudinal Study

Conclusion

Classical Analysis

Robust Analysis w/ SketchesLongitudinal Study

Internet Traffic: A Longitudinal Analysis
Multivariate SelfSimilarity for Internet
Internet Traffic
IIJ,
Tokyo, Japan- Feb. 2018 [Context:
1 / 59Traffic:- A
Longitudinal
Analysis
Passive Monitoring of TCP/IP traffic on a link]ConScale free Internet Traffic

Multivariate SelfSimilarity

Multivariate Traffic

Anomaly detection

Conclusions

OutlineScale free Internet Traffic
Multivariate SelfSimilarity
Multivariate Traffic
Anomaly detection
Conclusions

Multivariate SelfSimilarity for Internet Traffic - IIJ, Tokyo, Japan - Feb. 2018 -2 / 59

Scale free Internet Traffic

Multivariate SelfSimilarity

Multivariate Traffic

Anomaly detection

Conclusions

Aggregated Time Series• Aggregation procedure- aggregation scale ∆,- Pkt or Byte counts.

∆
t

3

2

2

4

2

1

2

4

Multivariate SelfSimilarity for Internet Traffic - IIJ, Tokyo, Japan - Feb. 2018 -

3

2

3

t

3 / 59

Scale free Internet Traffic

Multivariate SelfSimilarity

Multivariate Traffic

Anomaly detection

Conclusions

Aggregated Time Series• Aggregation procedure- aggregation scale ∆,- Pkt or Byte counts.

∆
t

3
70

2

2

4

2

1

2

4

3

Trafic Internet: Transpacific Japon−USA, 2007

2

3

t

∆ = 3.2 ms

35
0

0

300

temps (s)600

Multivariate SelfSimilarity for Internet Traffic - IIJ, Tokyo, Japan - Feb. 2018 -900
3 / 59

Scale free Internet Traffic

30

0
398

Multivariate SelfSimilarity

Multivariate Traffic

Anomaly detection

Conclusions

Scaling ? Covariance under aggregation∆ = 0.1 mstime (s)Multivariate SelfSimilarity for Internet Traffic - IIJ, Tokyo, Japan - Feb. 2018 -402

4 / 59

Scale free Internet Traffic

30

Multivariate SelfSimilarity

Multivariate Traffic

Anomaly detection

Conclusions

Scaling ? Covariance under aggregation∆ = 0.1 ms

0
398
40

time (s)0396time (s)402∆ = 0.2 ms

Multivariate SelfSimilarity for Internet Traffic - IIJ, Tokyo, Japan - Feb. 2018 -404

4 / 59

Scale free Internet Traffic

30

Multivariate SelfSimilarity

Multivariate Traffic

Anomaly detection

Conclusions

Scaling ? Covariance under aggregation∆ = 0.1 ms

0
398
40

time (s)0396
60

time (s)0392time (s)402∆ = 0.2 ms

404∆ = 0.4 ms

Multivariate SelfSimilarity for Internet Traffic - IIJ, Tokyo, Japan - Feb. 2018 -408

4 / 59

Scale free Internet Traffic

30

Multivariate SelfSimilarity

Multivariate Traffic

Anomaly detection

Conclusions

Scaling ? Covariance under aggregation∆ = 0.1 ms

0
398
40

time (s)0396
60

time (s)0392
80time (s)0384time (s)402∆ = 0.2 ms

404∆ = 0.4 ms

408∆ = 0.8 ms

Multivariate SelfSimilarity for Internet Traffic - IIJ, Tokyo, Japan - Feb. 2018 -416
4 / 59

Scale free Internet Traffic

Multivariate SelfSimilarity

Multivariate Traffic

Anomaly detection

Conclusions

Statistical modeling of Internet traffic time series• Aggregated time series: (aggregation levels ∆)- Packet counts, Byte counts, Flow counts,- Arrivals, durations, . . .

2
MiB/s
5
1
5
0
0s
150

300

450

600

750

900s

103 Pkt/s
4
3
2
1
0
0s
150 300• Statistics: ⇒ Irregularity, Burstiness !
- Long Range Dependence (covariance functions)- Heavy Tails (Marginal Distributions) Definition

Multivariate SelfSimilarity for Internet Traffic - IIJ, Tokyo, Japan - Feb. 2018 -

450

600

750

Definition

5 / 5990

Scale free Internet Traffic

Multivariate SelfSimilarity

Multivariate Traffic

Anomaly detection

Conclusions

Statistical modeling of Internet traffic time series• Aggregated time series: (aggregation levels ∆)- Packet counts, Byte counts, Flow counts,- Arrivals, durations, . . .

2
MiB/s
5
1
5
0
0s
150

300

450

600

750

900s

103 Pkt/s
4
3
2
1
0
0s
150 300• Statistics: ⇒ Irregularity, Burstiness !
- Long Range Dependence (covariance functions)- Heavy Tails (Marginal Distributions) Definition

Multivariate SelfSimilarity for Internet Traffic - IIJ, Tokyo, Japan - Feb. 2018 -

450

600

750

Definition

5 / 5990

Scale free Internet Traffic

Multivariate SelfSimilarity

Multivariate Traffic

Anomaly detection

Conclusions

MAWI data: B-US2Jp, 2005/07/11
2
MiB/s
1.5
1
0.5
0
0s 150 300 450 600 750 900s

LD for Byte count

2ms

16ms 128ms

H=0.94

1s

8s

64s

3

10 Pkt/s
LD for Pkt countH=0.92432
1
00s 150 300 450 600 750 900s 2ms 16ms 128ms 1s 8s 64s• Compares well with current knowledge and theory/models
Multivariate SelfSimilarity for Internet Traffic - IIJ, Tokyo, Japan - Feb. 2018 -6 / 59

Scale free Internet Traffic

Multivariate SelfSimilarity

Multivariate Traffic

Anomaly detection

Conclusions

MAWI data: B-US2Jp, 2003/06/03
2
MiB/s
1.5
1
0.5
0
0s 150 300 450 600 750 900s

LD for Byte count

2ms

16ms 128ms

H=0.41

1s

8s

64s

3

10 Pkt/s
LD for Pkt countH=0.89432
100s 150 300 450 600 750 900s 2ms 16ms 128ms 1s 8s 64s• Congestion.
Multivariate SelfSimilarity for Internet Traffic - IIJ, Tokyo, Japan - Feb. 2018 -7 / 59

Scale free Internet Traffic

Multivariate SelfSimilarity

Multivariate Traffic

Anomaly detection

Conclusions

MAWI data: B-Jp2US, 2004/09/21
2
MiB/s
1.5
1
0.5
0
0s 150 300 450 600 750 900s

LD for Byte count

2ms

16ms 128ms

H=0.73

1s

8s

64s

3

10 Pkt/s
LD for Pkt countH=1.00432
1
00s 150 300 450 600 750 900s 2ms 16ms 128ms 1s 8s 64s• Anomalies:
network scan, spoofed flooding, attack on a Realserver
Multivariate SelfSimilarity for Internet Traffic - IIJ, Tokyo, Japan - Feb. 2018 -8 / 59

Scale free Internet Traffic

Multivariate SelfSimilarity

Multivariate Traffic

Anomaly detection

Conclusions

Random Projections or sketches
Sketches = ensemble of outputs of random hash table[Muthukrishnan’03, Krishnamurty’03,...] [Abry+ SAINT’07, Dewaele+ Sigcomm
LSAD’07]• Random Hash Functions : hn
- y = h(x),- M− outputs: y ∈ [1, . . . , M],- k− universal Hash functions.
• Hash the Traffic :- Packet: i−th packet, n−tuple: ti , PTscri , PTdsti , IPsrci , IPdsti- Choose one specific key: e.g., Destination Address- Hash according to this key: mi = h(IPdsti ) ∈ [1, . . . , M],- All packets with same mi = one sub-trace, sampled by random
projection.
- Aggregate traffic {ti , mi }i∈I into M series X∆m (t), bins of ∆s.
Multivariate SelfSimilarity for Internet Traffic - IIJ, Tokyo, Japan - Feb. 2018 -9 / 59

Scale free Internet Traffic

Multivariate SelfSimilarity

Multivariate Traffic

Anomaly detection

Conclusions

Sketched Traffic• Sketches = M sub-traces representing the total traffic• Total of outputs = total trace (constrained sampling)• Each sketched output = random flow-sampling
Multivariate SelfSimilarity for Internet Traffic - IIJ, Tokyo, Japan - Feb. 2018 -10 / 59

Scale free Internet Traffic

Multivariate SelfSimilarity

Multivariate Traffic

Anomaly detection

Conclusions

MAWI data: B-US2Jp, 2005/07/11
103 Pkt/s

2 MiB/s
4
1.5
3
1

2

0.5
0
0s

1

150

300

450

LD for Byte count

600

750

0
900s 0s

Hg=0.94

150

300

450

LD for Pkt countHm=0.88
2ms 16ms 128ms 1s

8s

600

750

900s

Hg=0.92

Hm=0.9064s

2ms 16ms 128ms 1s

8s

64s

• All Hm s are consistent ! Hm s and Hg are consistent !
• LRDs on Bytes pr Pkts are consistent !
• Normal Traffic: no congestion (no anomaly ?)Multivariate SelfSimilarity for Internet Traffic - IIJ, Tokyo, Japan - Feb. 2018 -11 / 59

Scale free Internet Traffic

Multivariate SelfSimilarity

Multivariate Traffic

Anomaly detection

Conclusions

MAWI data: B-US2Jp, 2003/06/03, Congestion
103 Pkt/s

2 MiB/s
4
1.5
3
1

2

0.5

1

0
0s

150

300

450

600

750

0
900s 0s

Hg=0.41

LD for Byte count

150

300

450

Hm=0.802ms

16ms 128ms

1s

8s

600

750

900s

Hg=0.89

LD for Pkt count

H =0.83
m

64s

2ms

16ms 128ms

1s

8s

64s

• HgByte ' 0.4: no variability, no LRD, HgByte 6= HgPkt
Byte
Byte
Pkt
• Hm
' Hm
' 0.9, Flow variability, significant LRD, Hm
Multivariate SelfSimilarity for Internet Traffic - IIJ, Tokyo, Japan - Feb. 2018 -12 / 59

Scale free Internet Traffic

Multivariate SelfSimilarity

Multivariate Traffic

Anomaly detection

Conclusions

MAWI data: B-Jp2US, 2004/09/21, Anomalies
Sketched Traffic: Bytes Counts / 1 s

5

18

x 10

Sketched Traffic: Packet Counts / 1 s
6000

16
5000
14

12

4000

10
3000
8

6

2000

4
1000
2

0

0

100

200

300

400

500

600

700

800

900

0

0

100

200

300

400

500

600

700

800

900

seconds

seconds

Sketched Traffic: Bytes Counts − LD − H=0.777

Sketched Traffic: Packet Counts − LD − H=0.905

24

10

23
8
22
6
21

20

4

19
2
18
0
17

16

0

2

4

6

8

10

12

14

16

18

−2

0

2

4

scales

6

8

10

12

14

16

18

scales• HgByte ' 0.7: LD ???, HgPkt ' 1, ???
Byte
Byte
Pkt
• Hm
' 0.8, LDs ok, significant LRD, Hm' Hm
Multivariate SelfSimilarity for Internet Traffic - IIJ, Tokyo, Japan - Feb. 2018 -13 / 59

Scale free Internet Traffic

Multivariate SelfSimilarity

Multivariate Traffic

Anomaly detection

Conclusions

Univariate Self-Similarity
Fontugne et al. 2017

- Long-Memory (Self-Similarity) at Coarse Scales, H ' 0.9.
- Multifractality like at Fine Scales- Frontier scale around 1s, connected to RTT- Random projections + Multiscale Analysis ⇒ robust statistics,
anomaly detection

log2 Sd(j,2)

30
20
10
0
2013
2010
2007
2004
2001

0

5

10

15

j = log2 scaleMultivariate SelfSimilarity for Internet Traffic - IIJ, Tokyo, Japan - Feb. 2018 -14 / 59

Scale free Internet Traffic

Multivariate SelfSimilarity

Multivariate Traffic

Anomaly detection

Conclusions

Another point of view?

Multivariate SelfSimilarity for Internet Traffic - IIJ, Tokyo, Japan - Feb. 2018 -15 / 59

Scale free Internet Traffic

Multivariate SelfSimilarity

Multivariate Traffic

Anomaly detection

Conclusions

Limitations• Not versatile enough for data :- One-parameter model: 0 < H < 1 - Jointly Gaussian⇒ Multifractal models (univariate) Mandelbrot
1974, Fontugne et al., 2017
Funconal
connecvity⇒ Non Gaussian asymptotically self-similar processes (univariate)
Helgason et al., 2005

⇒ Anisotropic SelfSimilar textures (univariate fields) Roux et al. 2013stascal dependence between remote temporal signals• Data are naturally multivariate:reects large-scale neuronal interacons
failure of univariate analysis- Multivariate wavelet analysis:x3(t)

Frontal

x2(t
)
x5(t
)

Centralx1(t)

CentralFrontal

x4(t
)

x6(t
)

Didier, Pipiras, 2011
Multivariate SelfSimilarity for Internet Traffic - IIJ, Tokyo, Japan - Feb. 2018 -Parieto/Occipital- Need to model selfsimilarity in a multivariate setting

16 / 59

Scale free Internet Traffic

Multivariate SelfSimilarity

Multivariate Traffic

Anomaly detection

Conclusions

Limitations• Not versatile enough for data :- One-parameter model: 0 < H < 1 - Jointly Gaussian⇒ Multifractal models (univariate) Mandelbrot
1974, Fontugne et al., 2017
Funconal
connecvity⇒ Non Gaussian asymptotically self-similar processes (univariate)
Helgason et al., 2005

⇒ Anisotropic SelfSimilar textures (univariate fields) Roux et al. 2013stascal dependence between remote temporal signals• Data are naturally multivariate:reects large-scale neuronal interacons
failure of univariate analysis- Multivariate wavelet analysis:x3(t)

Frontal

x2(t
)
x5(t
)

Centralx1(t)

CentralFrontal

x4(t
)

x6(t
)

Didier, Pipiras, 2011
Multivariate SelfSimilarity for Internet Traffic - IIJ, Tokyo, Japan - Feb. 2018 -Parieto/Occipital- Need to model selfsimilarity in a multivariate setting

16 / 59

Scale free Internet Traffic

Multivariate SelfSimilarity

Multivariate Traffic

Anomaly detection

Conclusions

Internet Traffic is naturally bivariate
Fontugne et al. 2017, Abry, Didier 2017c

Japan to USA

30

4 ×10

Japan to USA

4

3.5

25
3

20

Byte

P kt

2.5

15

2

1.5

10
1

5
0.5

0

0

0

5

10

15

0

T ime(min)Multivariate SelfSimilarity for Internet Traffic - IIJ, Tokyo, Japan - Feb. 2018 -

5

10

15

T ime(min)17 / 59

Scale free Internet Traffic

Multivariate SelfSimilarity

Multivariate Traffic

Anomaly detection

Conclusions

Internet Traffic is naturally 4-variate
Fontugne et al. 2017, Abry, Didier 2017c
Japan to USA

USA to Japan

60

25

50

20

40

P kt

P kt

30

15

30

10

20

5

10

0

0
0

5

10

15

0

5

T ime(min)4 ×10Japan to USA

4

10

15

10

15

T ime(min)USA to Japan

4
6 ×10

3.5

5

3

4

Byte

Byte

2.5

2

3

1.5

2
1

1
0.5

0

0
0

5

10

T ime(min)

15

0

5

T ime(min)Multivariate SelfSimilarity for Internet Traffic - IIJ, Tokyo, Japan - Feb. 2018 -18 / 59

Scale free Internet Traffic

Multivariate SelfSimilarity

Multivariate Traffic

Anomaly detection

Conclusions

OutlineScale free Internet Traffic
Multivariate SelfSimilarity
Multivariate Traffic
Anomaly detection
Conclusions

Multivariate SelfSimilarity for Internet Traffic - IIJ, Tokyo, Japan - Feb. 2018 -19 / 59

Scale free Internet Traffic

Multivariate SelfSimilarity

Multivariate Traffic

Anomaly detection

Conclusions

Operator Fractional Brownian Motion (OFBM): Definition
Didier, Pipiras, 2011

• M-components: {BH,Σ (t)}t∈R{BH,Σ (t)}t∈R = {Bh1 (t), . . . , Bhm (t), . . . BhM (t)}t∈R- M-correlated fBm each with Hurst parameter 0 < hm < 1
H = {h1 , . . . , hm , . . . , hM }- Σ: M × M point covariance (positive definite) matrix• Linear mixing:- W : M × M invertible matrix (in RM )• OFBM: t ∈ R → BH,Σ,W ∈ RM
- BH,Σ,W (t) = W · BH,Σ (t)- Free parameters:
H, Σ, W
M + M(M − 1)/2 + M(M − 1) = 3/2M 2 + M/2

Multivariate SelfSimilarity for Internet Traffic - IIJ, Tokyo, Japan - Feb. 2018 -20 / 59

Scale free Internet Traffic

Multivariate SelfSimilarity

Multivariate Traffic

Anomaly detection

Conclusions

Properties• Covariance:- ΣBH,Σ,W (t, t 0 ) ≡ W ΣBH,Σ (t, t 0 )W ∗(ΣBH,Σ (t, t 0 ))m,m0 = (Σ)m,m0 · (|t|hm +hm0 + |t 0 |hm +hm0 − |t − t 0 |hm +hm0 )⇒ Σ ≡ ΣBH,Σ (1, 1)• Existence:- Matrix G ◦ Σ has full rank (Hadamard matrix product)
Gm,m0 = Γ(hm + hm0 + 1) sin((hm + hm0 )π/2)⇒ constraints on Free parameters:⇒ H and Σ cannot be chosen independently⇒ e.g., M = 2: ρ12 = Σ1,2 /sqrt(Σ1,1 Σ2,2 )Γ(2h1 + 1)Γ(2h2 + 1) sin(πh1 ) sin(πh2 ) − ρ212 Γ(h1 + h2 + 1)2 sin2 (π(h1 + h2 )/2) > 0• Time Reversibility:
By definition: ΣBH,Σ,W (t, t 0 ) = (ΣBH,Σ,W (−t, −t 0 ))T
There exist more general definitions
Multivariate SelfSimilarity for Internet Traffic - IIJ, Tokyo, Japan - Feb. 2018 -21 / 59

Scale free Internet Traffic

Multivariate SelfSimilarity

Multivariate Traffic

Anomaly detection

Conclusions

Multivariate SelfSimilarity• Selfsimilarity:
fdd- {BH,Σ,W (t)}t∈R = {aH BH,Σ,W (t/a)}t∈R , ∀a > 0
fdd

where = : equality of all finite dimensional distributions,with H = W · Diag H · W −1 , M × M matrix
P(log aH)kwhere aH := exp(log(aH)) = k>0 k ! .

• Mixture of Power-laws:- when W ≡ IM
fdd
{BH,Σ,W (t)}t∈R = {ah1 Bh1 (t/a), . . . , ahm Bhm (t/a), . . . ahM BhM (t/a)}t∈R , ∀a > 0- when W 6= IM
Multivariate SelfSimilarity ⇒ Mixtures of power-laws

Multivariate SelfSimilarity for Internet Traffic - IIJ, Tokyo, Japan - Feb. 2018 -22 / 59

Scale free Internet Traffic

Multivariate SelfSimilarity

Multivariate Traffic

Anomaly detection

Conclusions

Multivariate (discrete) Wavelet Transform• Wavelet Coefficients:R
Dym (j, k) = R 2−j/2 ψ(2−j t − k)Ym (t)dt• Vector of CoefficientsDy (j, k) ≡ (Dy1 (j, k), . . . , Dym (j, k), . . . , DyM (j, k))T
• Wavelet Spectrum
PKj
S(2j ) = K1j k=1
D(2j , k)D(2j , k)∗ ,Kj = 2Nj

S(2j ) is M × M matrix for each scale 2j
N: data sample size
S11 (2j ) S21 (2j )


j
...
S(2 ) = 

...


...
SM1 (2j )

S12 (2j )S22 (2j )
...
...
...
...

...
...
S33 (2j )
...
...
...

...
...
...
...
...
...

...
...
...
...
...
...

Multivariate SelfSimilarity for Internet Traffic - IIJ, Tokyo, Japan - Feb. 2018 -S1M (2j )
...
...
...
...
SMM (2j )





,




23 / 59

Scale free Internet Traffic

Multivariate SelfSimilarity

Multivariate Traffic

Anomaly detection

Conclusions

Multivariate (discrete) Wavelet Transform and OFBM
Frecon et al. 2015, A., Didier 2017a, A., Didier 2017b, A., Didier 2017c,• Short cuts:- Pre-Mixing: X = BH,Σ (t)}t∈R- Post-Mixing: Y = BH,Σ,W (t)}t∈R• Wavelet CoefficientsDy (j, k) = W 2j(H+IM /2) Dx (0, k)• Theoretical Wavelet Spectrum∗
EDy (j, k)Dy (j, k)∗ = W 2j(H+IM /2) EDx (0, k)Dx (0, k)∗ 2j(H+IM /2) W ∗(1) EDym (j, k)Dym0 (j, k)∗ =(m,m0 )
j(hp +hp 0 +1)
p 0 =1 Ap,p 0 (Σ, W )2

PM PM
p=1

⇒ Mixtures of Power Laws
⇒ Identification: Non linear regression
Frecon et al. 2016, M = 2, Branch and Bound Strategy
Multivariate SelfSimilarity for Internet Traffic - IIJ, Tokyo, Japan - Feb. 2018 -24 / 59

Scale free Internet Traffic

Multivariate SelfSimilarity

Multivariate Traffic

Anomaly detection

Conclusions

Multivariate analysis: Eigen Value Decomposition
Abry, Didier 2017a M = 2, Abry, Didier, Hui 2017b Σ ≡ IM , Abry, Didier 2017c, M ≥ 2• For each scale j, :- Eigen Value Decomposition of S(2j ):S(2j ) = U(2j ) Λ(2j ) U ∗ (2j )




j
j 
S(2 ) = U(2 ) 

λ1 (S(2j ))
0
0
0
0
0

0
λ2 (S(2j ))
0
0
0
0

0
0
λ3 (S(2j ))
0
0
0

0
0
0
...
0
0

Multivariate SelfSimilarity for Internet Traffic - IIJ, Tokyo, Japan - Feb. 2018 -

0
0
0
0
...
0

0
0
0
0
0
λM (S(2j )) U(2j )T

25 / 59

Scale free Internet Traffic

Multivariate SelfSimilarity

Multivariate Traffic

Anomaly detection

Conclusions

Multivariate analysis of SelfSimilarity
Abry, Didier 2017a M = 2, Abry, Didier 2017c, M ≥ 2• Assume:- ∀(m, m0 ), m0 6= m, hm 6= hm0- 0 < h1 < . . . < hm < . . . hM < 1• Consistency:- λm (S(2j(n) )) →n→+∞ ξm 22hm j(n) , ∀m = 1, . . . , M- um ∈ span{W·,m , W·,m+1 , . . . , W·,M }, 1 ≤ m ≤ M• Asymptotic Normality:

p n
2j(n)

{log2 λm (S(2j(n) )) − log2 λm (ES(2j(n) ))}(m=1,...,M,j1 (n)≤j≤j2 (n)) →n→+∞ N (0, Σλ )Multivariate SelfSimilarity for Internet Traffic - IIJ, Tokyo, Japan - Feb. 2018 -26 / 59

Scale free Internet Traffic

Multivariate SelfSimilarity

Multivariate Traffic

Anomaly detection

Conclusions

Multivariate EVD estimation of Hurst exponents• Multivariate estimators:
bm = 1 Pj2 wj log λm (S(2j ))
h
2
j=j1
2

• Asymptotic Normality:qnbm − hm }m=1,...,M →n→+∞ N (0, Mj ,j Σλ M ∗ ){h
1 2
j1 ,j22j (n)• Scaling range (j1 (n), j2 (n)(j1 (n), j2 (n) = (j10 + f (n), (j20 + f (n)) (see later)• Univariate estimators:
bU = 1 (Pj2 wj log Smm (2j ) − 1)
h
2
m
j=j1
2

Multivariate SelfSimilarity for Internet Traffic - IIJ, Tokyo, Japan - Feb. 2018 -27 / 59

Scale free Internet Traffic

Multivariate SelfSimilarity

Multivariate Traffic

Anomaly detection

Conclusions

Univariate (discrete) Wavelet Transform and OFBM
• Diagonal entries of Sm,m (2j ):15

log2 Sqq (2j )

10
5
0
-5
-10

5

10

15

j = log2 2j- Mixture of Power-Laws- Dominant h only
⇒ Misleading conclusion: All h are equal
Multivariate SelfSimilarity for Internet Traffic - IIJ, Tokyo, Japan - Feb. 2018 -28 / 59

Scale free Internet Traffic

Multivariate SelfSimilarity

Multivariate Traffic

Anomaly detection

Conclusions

Multivariate (EVD) Wavelet Transform and OFBM
• Eigen Values of S(2j ): λm
1510log2 λp (j)

5
0
-5
-10
-15
-20

5

10

15

j = log2 2j- Demixed Power-Laws- All hs
- ⇒ correct conclusion: All h can be different
Multivariate SelfSimilarity for Internet Traffic - IIJ, Tokyo, Japan - Feb. 2018 -29 / 59

Scale free Internet Traffic

Multivariate SelfSimilarity

Multivariate Traffic

Anomaly detection

Conclusions

Multivariate (EVD) Wavelet Transform and OFBM
• Eigen Values of S(2j ): λm
642

log2 λp (j)

0
-2
-4
-6
-8
-10
-12
-14

2

4

6

8

j = log2 2j- Demixed Power-Laws- All hs
- Even for very small sample size !
Multivariate SelfSimilarity for Internet Traffic - IIJ, Tokyo, Japan - Feb. 2018 -30 / 59

Scale free Internet Traffic

Multivariate SelfSimilarity

Multivariate Traffic

Anomaly detection

Conclusions

Multivariate (EVD) Wavelet Transform and OFBM
Diagonal entries of Sm,m (2j )Eigen Values of S(2j ): λm
15

15

10

10

log2 λq (S(2j ))log2 Sqq (2j )

5
5
0
-5
-10

0
-5
-10
-15

5

10

15

-20

5

j = log2 2j

Multivariate SelfSimilarity for Internet Traffic - IIJ, Tokyo, Japan - Feb. 2018 -1015

j = log2 2j

31 / 59

Scale free Internet Traffic

Multivariate SelfSimilarity

Multivariate Traffic

Anomaly detection

Conclusions

1

1

0.8

0.8

0.8

0.6

0.4

0.2

0

ĥ3 (o), ĥU3 (∗), h3 (−−)

1ĥ2 (o), ĥU2 (∗), h2 (−−)

ĥ1 (o), ĥU1 (∗), h1 (−−)

Estimation Performance: Bias → 0

0.6

0.4

0.2

0
12

14

16

18

20

0.4

0.2

0
12

log2 SampleSize

14

16

18

20

12

log2 SampleSize
1

0.8

0.8

0.8

0.4

0.2

0

ĥ6 (o), ĥU6 (∗), h6 (−−)

1

0.6

0.6

0.4

0.2

0
12

14

16

log2 SampleSize

18

20

14

16

18

20

18

20

log2 SampleSize

1ĥ5 (o), ĥU5 (∗), h5 (−−)

ĥ4 (o), ĥU4 (∗), h4 (−−)

0.6

0.6

0.4

0.2

0
12

14

16

18

20

log2 SampleSize

12

14

16

log2 SampleSize

Proof

Multivariate SelfSimilarity for Internet Traffic - IIJ, Tokyo, Japan - Feb. 2018 -32 / 59

Scale free Internet Traffic

Multivariate SelfSimilarity

Multivariate Traffic

Anomaly detection

Conclusions

OutlineScale free Internet Traffic
Multivariate SelfSimilarity
Multivariate Traffic
Anomaly detection
Conclusions

Multivariate SelfSimilarity for Internet Traffic - IIJ, Tokyo, Japan - Feb. 2018 -33 / 59

Scale free Internet Traffic

Multivariate SelfSimilarity

Multivariate Traffic

Anomaly detection

Conclusions

Internet Traffic - M = 4
Fontugne et al. 2017, Abry, Didier 2017c
Japan to USA

USA to Japan

60

25

50

20

40

P kt

P kt

30

15

30

10

20

5

10

0

0
0

5

10

15

0

5

T ime(min)4 ×10Japan to USA

4

10

15

10

15

T ime(min)USA to Japan

4
6 ×10

3.5

5

3

4

Byte

Byte

2.5

2

3

1.5

2
1

1
0.5

0

0
0

5

10

T ime(min)

15

0

5

T ime(min)Multivariate SelfSimilarity for Internet Traffic - IIJ, Tokyo, Japan - Feb. 2018 -34 / 59

Scale free Internet Traffic

Multivariate SelfSimilarity

Multivariate Traffic

Anomaly detection

Conclusions

Wavelet Cross Coherence

Multivariate SelfSimilarity for Internet Traffic - IIJ, Tokyo, Japan - Feb. 2018 -35 / 59

Scale free Internet Traffic

Multivariate SelfSimilarity

Multivariate Traffic

Anomaly detection

Conclusions

Wavelet Eigen Structure and Random Projections

Multivariate SelfSimilarity for Internet Traffic - IIJ, Tokyo, Japan - Feb. 2018 -36 / 59

Scale free Internet Traffic

Multivariate SelfSimilarity

Multivariate Traffic

Anomaly detection

Conclusions

Multivariate (WavEigen) vs. Univariate Structures

Multivariate SelfSimilarity for Internet Traffic - IIJ, Tokyo, Japan - Feb. 2018 -37 / 59

Scale free Internet Traffic

Multivariate SelfSimilarity

Multivariate Traffic

Anomaly detection

Conclusions

Multivariate (WavEigen) vs. Univariate Structures

Multivariate SelfSimilarity for Internet Traffic - IIJ, Tokyo, Japan - Feb. 2018 -38 / 59

Scale free Internet Traffic

Multivariate SelfSimilarity

Multivariate Traffic

Anomaly detection

Conclusions

Long Memory at Coarse Scales
8

7

λ1
W22
λ

6
log2 Wqq (2j ), log2 λq (W (2j ))log2 Wqq (2j ), log2 λq (W (2j ))

10

W11

2

6
4

W33
λ3
W44
λ4

2
0

W11
λ1
W
22

5

λ2
W33
λ3
W44
λ

4
3

4

2
1

-2
0
2

4
6
j = log2 (scale)univariate
multivariate

8

Hb1
0.85
0.51

0

2

Hb2
0.86
0.69

Hb3
0.86
0.82

Multivariate SelfSimilarity for Internet Traffic - IIJ, Tokyo, Japan - Feb. 2018 -46
j = log2 (scale)

8

10

Hb4
0.90
0.86

39 / 59

Scale free Internet Traffic

Multivariate SelfSimilarity

Multivariate Traffic

Anomaly detection

Conclusions

Demixing

Multivariate SelfSimilarity for Internet Traffic - IIJ, Tokyo, Japan - Feb. 2018 -40 / 59

Scale free Internet Traffic

Multivariate SelfSimilarity

Multivariate Traffic

Anomaly detection

Conclusions

Wavelet Cross Coherence: 2007 vs 2016
2007

Multivariate SelfSimilarity for Internet Traffic - IIJ, Tokyo, Japan - Feb. 2018 -2016

41 / 59

Scale free Internet Traffic

Multivariate SelfSimilarity

Multivariate Traffic

Anomaly detection

Conclusions

Demixing: 2007 vs 2016
2007

Multivariate SelfSimilarity for Internet Traffic - IIJ, Tokyo, Japan - Feb. 2018 -2016

42 / 59

Scale free Internet Traffic

Multivariate SelfSimilarity

Multivariate Traffic

Anomaly detection

Conclusions

Wavelet Cross Coherence: from 2007 to 2017

Multivariate SelfSimilarity for Internet Traffic - IIJ, Tokyo, Japan - Feb. 2018 -43 / 59

Scale free Internet Traffic

Multivariate SelfSimilarity

Multivariate Traffic

Anomaly detection

Conclusions

Multi vs. Uni Variate Structures: 2007 vs 2016
2007

Multivariate SelfSimilarity for Internet Traffic - IIJ, Tokyo, Japan - Feb. 2018 -2016

44 / 59

Scale free Internet Traffic

Multivariate SelfSimilarity

Multivariate Traffic

Anomaly detection

Conclusions

Multi vs. Uni Variate Structures: from 2007 to 2017

Multivariate SelfSimilarity for Internet Traffic - IIJ, Tokyo, Japan - Feb. 2018 -45 / 59

Scale free Internet Traffic

Multivariate SelfSimilarity

Multivariate Traffic

Anomaly detection

Conclusions

OutlineScale free Internet Traffic
Multivariate SelfSimilarity
Multivariate Traffic
Anomaly detection
Conclusions

Multivariate SelfSimilarity for Internet Traffic - IIJ, Tokyo, Japan - Feb. 2018 -46 / 59

Scale free Internet Traffic

Multivariate SelfSimilarity

Multivariate Traffic

Anomaly detection

Conclusions

Principle

Multivariate SelfSimilarity for Internet Traffic - IIJ, Tokyo, Japan - Feb. 2018 -47 / 59

Scale free Internet Traffic

Multivariate SelfSimilarity

Multivariate Traffic

Anomaly detection

Conclusions

Case Study 1: Scan found by L1 only - Low Pkt

Multivariate SelfSimilarity for Internet Traffic - IIJ, Tokyo, Japan - Feb. 2018 -48 / 59

Scale free Internet Traffic

Multivariate SelfSimilarity

Multivariate Traffic

Anomaly detection

Conclusions

Case Study 2: Scan found by L2 only - Short Duration

Multivariate SelfSimilarity for Internet Traffic - IIJ, Tokyo, Japan - Feb. 2018 -49 / 59

Scale free Internet Traffic

Multivariate SelfSimilarity

Multivariate Traffic

Anomaly detection

Conclusions

Longitudinal Study- Method:
One day per month, from 2007 to 2017
Trinocular: filtered out- Detection:
Top-5 most anomalous sketch,
8 successive hash tables,
Anomalous if suspicious in each hast table,
Similarity index: (|A ∩ B|)/ min (|A|, |B|)

Multivariate SelfSimilarity for Internet Traffic - IIJ, Tokyo, Japan - Feb. 2018 -50 / 59

Scale free Internet Traffic

Multivariate SelfSimilarity

Multivariate Traffic

Anomaly detection

Conclusions

Longitudinal Study - from 2007 to 2017

- MawiLab: ∼ 142 detections per day on average- Multiscale:
S
L

1
∼9
∼7

2
∼8
∼7

3
∼9
∼7

4
∼8
∼9

- Multiscale S ∩ L: 30% only !

Multivariate SelfSimilarity for Internet Traffic - IIJ, Tokyo, Japan - Feb. 2018 -51 / 59

Scale free Internet Traffic

Multivariate SelfSimilarity

Multivariate Traffic

Anomaly detection

Conclusions

Longitudinal Study- Univariate: Same anomalies for Pkt & Byt in same direction- Multivariate: L4 ∼ univariate, L1, L2, L3: different anomalies- MawiLab: Univ. Pkt, then Univ. Bytmuch less in common with L1, L2, L3
S1 S2 S3 S4 L1 L2 L3 L4 ML

1.0

S1
S2

0.8

S3
S4

0.6

L1
L2
L3

0.4

L4
ML
Multivariate SelfSimilarity for Internet Traffic - IIJ, Tokyo, Japan - Feb. 2018 -

0.2
52 / 59

Scale free Internet Traffic

Multivariate SelfSimilarity

Multivariate Traffic

Anomaly detection

Conclusions

Longitudinal Study - Low Pkt Anomalies
1.0

CDF

0.8
0.6

L1
L2
L3
L4

0.4
0.2
0.0 2
10

3

10

4

10

5

6

10
10
# packets

Multivariate SelfSimilarity for Internet Traffic - IIJ, Tokyo, Japan - Feb. 2018 -

7

10

8

10

53 / 59

Scale free Internet Traffic

Multivariate SelfSimilarity

Multivariate Traffic

Anomaly detection

Conclusions

Longitudinal Study - Short Duration Anomalies
1.0

L1
L2
L3
L4

CDF

0.8
0.6
0.4
0.2
0.0

0

200
400
600
Duration (seconds)

Multivariate SelfSimilarity for Internet Traffic - IIJ, Tokyo, Japan - Feb. 2018 -800

54 / 59

Scale free Internet Traffic

Multivariate SelfSimilarity

Multivariate Traffic

Anomaly detection

Conclusions

OutlineScale free Internet Traffic
Multivariate SelfSimilarity
Multivariate Traffic
Anomaly detection
Conclusions

Multivariate SelfSimilarity for Internet Traffic - IIJ, Tokyo, Japan - Feb. 2018 -55 / 59

Scale free Internet Traffic

Multivariate SelfSimilarity

Multivariate Traffic

Anomaly detection

Conclusions

Conclusions and perspectives• Scale-free dynamics:- Ubiquitous in applications- Well-modeled by SelfSimilarity- Efficiently analyzed with wavelets• Multivariate SelfSimilarity:- But Data are multivariate- Multivariate SelfSimilarity model (OFBM)
Change of Perspectives- Multivariate wavelet analysis:
Univariate: Scales then Components
Multivariate: Components then Scales⇒ Efficient and robust estimation procedures• Internet data:- Longitudinal study ? Demixing ? Interpretation ?
- Multivariate statistical modeling ? Anomaly detection ?

• References:- patrice.abry@ens-lyon.fr ;- http://perso.ens-lyon.fr/patrice.abry/Multivariate SelfSimilarity for Internet Traffic - IIJ, Tokyo, Japan - Feb. 2018 -56 / 59

Scale free Internet Traffic

Multivariate SelfSimilarity

Multivariate Traffic

Anomaly detection

Conclusions

Conclusions and perspectives• Scale-free dynamics:- Ubiquitous in applications- Well-modeled by SelfSimilarity- Efficiently analyzed with wavelets• Multivariate SelfSimilarity:- But Data are multivariate- Multivariate SelfSimilarity model (OFBM)
Change of Perspectives- Multivariate wavelet analysis:
Univariate: Scales then Components
Multivariate: Components then Scales⇒ Efficient and robust estimation procedures• Internet data:- Longitudinal study ? Demixing ? Interpretation ?
- Multivariate statistical modeling ? Anomaly detection ?

• References:- patrice.abry@ens-lyon.fr ;- http://perso.ens-lyon.fr/patrice.abry/Multivariate SelfSimilarity for Internet Traffic - IIJ, Tokyo, Japan - Feb. 2018 -56 / 59

Scale free Internet Traffic

Multivariate SelfSimilarity

Multivariate Traffic

Anomaly detection

Conclusions

Conclusions and perspectives• Scale-free dynamics:- Ubiquitous in applications- Well-modeled by SelfSimilarity- Efficiently analyzed with wavelets• Multivariate SelfSimilarity:- But Data are multivariate- Multivariate SelfSimilarity model (OFBM)
Change of Perspectives- Multivariate wavelet analysis:
Univariate: Scales then Components
Multivariate: Components then Scales⇒ Efficient and robust estimation procedures• Internet data:- Longitudinal study ? Demixing ? Interpretation ?
- Multivariate statistical modeling ? Anomaly detection ?

• References:- patrice.abry@ens-lyon.fr ;- http://perso.ens-lyon.fr/patrice.abry/Multivariate SelfSimilarity for Internet Traffic - IIJ, Tokyo, Japan - Feb. 2018 -56 / 59

Scale free Internet Traffic

Multivariate SelfSimilarity

Multivariate Traffic

Anomaly detection

Conclusions

Conclusions and perspectives• Scale-free dynamics:- Ubiquitous in applications- Well-modeled by SelfSimilarity- Efficiently analyzed with wavelets• Multivariate SelfSimilarity:- But Data are multivariate- Multivariate SelfSimilarity model (OFBM)
Change of Perspectives- Multivariate wavelet analysis:
Univariate: Scales then Components
Multivariate: Components then Scales⇒ Efficient and robust estimation procedures• Internet data:- Longitudinal study ? Demixing ? Interpretation ?
- Multivariate statistical modeling ? Anomaly detection ?

• References:- patrice.abry@ens-lyon.fr ;- http://perso.ens-lyon.fr/patrice.abry/Multivariate SelfSimilarity for Internet Traffic - IIJ, Tokyo, Japan - Feb. 2018 -56 / 59

Scale free Internet Traffic

Multivariate SelfSimilarity

Multivariate Traffic

Anomaly detection

Conclusions

References - Theory• Multivariate SelfSimilarity Analysis:- Frecon 2016: J. Frecon, G. Didier, N. Pustelnik, P. Abry, Non-Linear Wavelet Regression and
Branch and Bound Optimization for the Full Identification of Bivariate Operator Fractional
Brownian Motion, IEEE Transactions on Signal Processing, 64(15):4040-4049, 2016.

.pdf- Abry, Didier, 2017a: Abry, P. and Didier, G., Wavelet estimation for operator fractional Brownian
motion, Bernoulli, to appear, 2017.

.pdf- Abry, Didier, Hui, 2017b: Abry, P., Didier, G., Hui L., Two-step wavelet-based estimation formixed Gaussian fractional processes, Preprint, 2017.

.pdf- Abry, Didier, 2017c: Abry, P. and Didier, G., Wavelet eigenvalue regression for n-variate operator
fractional Brownian motion, preprint 2017.

.pdf- H. Wendt, G. Didier, S. Combrexelle, P. Abry, Multivariate Hadamard self-similarity: testing
fractal connectivity, Signal Processing, 2017.

.pdf- G. Didier, H. Helgason, P. Abry, Demixing Multivariate-Operator Self-Similar Processes, IEEE Int.
Conf. on Acoust., Speech and Signal Proc., ICASSP 2015, Brisbane (AU), 20-24 april 2015 .pdf
Multivariate SelfSimilarity for Internet Traffic - IIJ, Tokyo, Japan - Feb. 2018 -57 / 59

Scale free Internet Traffic

Multivariate SelfSimilarity

Multivariate Traffic

Anomaly detection

Conclusions

References - Applications• Internet Traffic:- Fontugne et al. 2017: R. Fontugne, P. Abry, K. Fukuda, D. Veitch, K. Cho, P. Borgnat, H.
Wendt, Scaling in Internet Traffic: a 14 year and 3 day longitudinal study, with multiscale
analyses and random projections, IEEE Trans. on Networking, 2017

.pdf

- P. Abry, R. Baraniuk, P. Flandrin, R. Riedi, D. Veitch, Multiscale Network Traffic Analysis,
Modeling, and Inference Using Wavelets, Multifractals, and Cascades, IEEE Signal Processing
Magazine 19(3):28–46, May 2002.

.pdf• Neurosciences:- Ph. Ciuciu, P. Abry, B. He., Interplay between functional connectivity and scale-free dynamics inintrinsic fMRI networks, NeuroImage, 95:248-263, 2014.

.www .pdf• Art Investigations:- P. Abry, S. G. Roux, H. Wendt, P. Messier, A. G. Klein, N. Tremblay, P. Borgnat, S. Jaffard, B.
Vedel, J. Coddington, L. Daffner, Multiscale Anisotropic Texture Analysis and Classification of
Photographic Prints: Art scholarship meets image processing algorithms, IEEE Signal
Processing Mag., vol. 32, no. 4, pp. 18-27, July 2015.
Multivariate SelfSimilarity for Internet Traffic - IIJ, Tokyo, Japan - Feb. 2018 -.pdf
58 / 59

Scale free Internet Traffic

Multivariate SelfSimilarity

Multivariate Traffic

Anomaly detection

Conclusions

Thank you !

Multivariate SelfSimilarity for Internet Traffic - IIJ, Tokyo, Japan - Feb. 2018 -59 / 59

Univariate analysis is dangerous !

Multivariate SelfSimilarity for Internet Traffic - IIJ, Tokyo, Japan - Feb. 2018 -60 / 59

Univariate versus Multivariate Analyses
1210log2 Sm,m (j)

8
6
4
2
0
-2

5

10

15

j = log2 2j• Diagonal entries of Sm,m (2j ):- Mixture of Power-Laws⇒ Misleading conclusion: All h are equalbackMultivariate SelfSimilarity for Internet Traffic - IIJ, Tokyo, Japan - Feb. 2018 -61 / 59

Univariate versus Multivariate Analyses

Multivariate SelfSimilarity for Internet Traffic - IIJ, Tokyo, Japan - Feb. 2018 -62 / 59

Univariate versus Multivariate Analyses

backMultivariate SelfSimilarity for Internet Traffic - IIJ, Tokyo, Japan - Feb. 2018 -63 / 59Long Range Dependence (or covariance)• Theory: Y 2nd order stationary process- Definition:
Spectrum: ΓY (ν) ∼ CΓ |ν|−γ , |ν| → 0, 0 < γ < 1,
Covariance: γY (τ ) ∼ Cγ |τ |−(1−γ) , |τ | → ∞- Self-similarity:
fdd

X is H-ss, {X (t), t ∈ R} = {aH X (t/a), t ∈ R}, a > 0,
if stationary increments, Y (k) = X (k + 1) − X (k)and 1/2 < H < 1,then Y is LRD with γ = 2H − 1.

- Fractional Brownian motion BH (t):Gaussian H-ss, with stationary increments

Multivariate SelfSimilarity for Internet Traffic - IIJ, Tokyo, Japan - Feb. 2018 -64 / 59Long Range Dependence (or covariance)• Theory: Y 2nd order stationary process- Definition:
Spectrum: ΓY (ν) ∼ CΓ |ν|−γ , |ν| → 0, 0 < γ < 1,
Covariance: γY (τ ) ∼ Cγ |τ |−(1−γ) , |τ | → ∞- Self-similarity:
fdd

X is H-ss, {X (t), t ∈ R} = {aH X (t/a), t ∈ R}, a > 0,
if stationary increments, Y (k) = X (k + 1) − X (k)and 1/2 < H < 1,then Y is LRD with γ = 2H − 1.

- Fractional Brownian motion BH (t):Gaussian H-ss, with stationary increments

Multivariate SelfSimilarity for Internet Traffic - IIJ, Tokyo, Japan - Feb. 2018 -64 / 59Long Range Dependence (or covariance)• Theory: Y 2nd order stationary process- Definition:
Spectrum: ΓY (ν) ∼ CΓ |ν|−γ , |ν| → 0, 0 < γ < 1,
Covariance: γY (τ ) ∼ Cγ |τ |−(1−γ) , |τ | → ∞- Self-similarity:
fdd

X is H-ss, {X (t), t ∈ R} = {aH X (t/a), t ∈ R}, a > 0,
if stationary increments, Y (k) = X (k + 1) − X (k)and 1/2 < H < 1,then Y is LRD with γ = 2H − 1.

- Fractional Brownian motion BH (t):Gaussian H-ss, with stationary increments

Multivariate SelfSimilarity for Internet Traffic - IIJ, Tokyo, Japan - Feb. 2018 -64 / 59

Scale-free dynamics: Intuition- Covariance under Dilation (Change of Scale),- The Whole and the SubPart (Statistically) Undistinguishable,- No Characteristic Scale of TimeMultivariate SelfSimilarity for Internet Traffic - IIJ, Tokyo, Japan - Feb. 2018 -65 / 59

LRD and Wavelets

10• Wavelets: WaveletTransform−1
time (s)- Mother-Wavelet ψ: Oscillating pattern,−10- Numberofvanishing
moments
N
:
∀k
=
0,
...,
N
−
1,
ψ
R k
R
t ψ0 (t)dt ≡ 0 and R t N ψ0 (t)dt 6= 0.
R- Basis: {ψj,k (t) = 2−j/2 ψ0 (2−j t − k)},- Coefficients of Y : dY (j, k) = hψj,k , Y i

1• Wavelets and 2nd order stationary process:R- IE|dY (j, k)|2 = R ΓY (ν)2j |Ψ̃0 (2j ν)|2 dν,• Wavelets and LRD:2
- IE|dY (j, k)|P
∼ C 2j(2H−1) for 2j → +∞,- S(j) = n1j k |dY (j, k)|2 ,j- Logscalelog2 S(j) vs.
 Diagram: log2 2 = j,Pj2
wj log2 S(j) .
- Ĥ = 12 1 + j=j
1
Multivariate SelfSimilarity for Internet Traffic - IIJ, Tokyo, Japan - Feb. 2018 -66 / 59

LRD and Wavelets

10• Wavelets: WaveletTransform−1
time (s)- Mother-Wavelet ψ: Oscillating pattern,−10- Numberofvanishing
moments
N
:
∀k
=
0,
...,
N
−
1,
ψ
R k
R
t ψ0 (t)dt ≡ 0 and R t N ψ0 (t)dt 6= 0.
R- Basis: {ψj,k (t) = 2−j/2 ψ0 (2−j t − k)},- Coefficients of Y : dY (j, k) = hψj,k , Y i

1• Wavelets and 2nd order stationary process:R- IE|dY (j, k)|2 = R ΓY (ν)2j |Ψ̃0 (2j ν)|2 dν,• Wavelets and LRD:2
- IE|dY (j, k)|P
∼ C 2j(2H−1) for 2j → +∞,- S(j) = n1j k |dY (j, k)|2 ,j- Logscalelog2 S(j) vs.
 Diagram: log2 2 = j,Pj2
wj log2 S(j) .
- Ĥ = 12 1 + j=j
1
Multivariate SelfSimilarity for Internet Traffic - IIJ, Tokyo, Japan - Feb. 2018 -66 / 59

LRD and Wavelets

10• Wavelets: WaveletTransform−1
time (s)- Mother-Wavelet ψ: Oscillating pattern,−10- Numberofvanishing
moments
N
:
∀k
=
0,
...,
N
−
1,
ψ
R
R k
t ψ0 (t)dt ≡ 0 and R t N ψ0 (t)dt 6= 0.
R- Basis: {ψj,k (t) = 2−j/2 ψ0 (2−j t − k)},- Coefficients of Y : dY (j, k) = hψj,k , Y i

1• Wavelets and 2nd order stationary process:R- IE|dY (j, k)|2 = R ΓY (ν)2j |Ψ̃0 (2j ν)|2 dν,• Wavelets and LRD:2
- IE|dY (j, k)|P
∼ C 2j(2H−1) for 2j → +∞,1- S(j) = nj k |dY (j, k)|2 ,j- Logscalelog2 S(j) vs.
 Diagram: log2 2 = j,Pj2
1
- Ĥ = 2 1 + j=j1 wj log2 S(j) .
Multivariate SelfSimilarity for Internet Traffic - IIJ, Tokyo, Japan - Feb. 2018 -LD for Byte countH=0.942ms 16ms 128ms 1s

8s

64s

66 / 59

Wavelet Transform• Let ψ0 denote an elementary mother wavelet,• Shifted and dilated templates of ψ0 :

ψj,k (t) = 2−j/2 ψ0 (2−j t − k),• Wavelet Coefficients: dX∆ (j, k) = hψj,k , X∆ i.

Back
Multivariate SelfSimilarity for Internet Traffic - IIJ, Tokyo, Japan - Feb. 2018 -

67 / 59

Sketch of Proof - 1• log2 λm (S(2j (n))) → 2jhm ?
• Courant-Fischer principle:- Let Um such that dim Um = m
λm (S(2j )) = inf Um supx∈Um ∩S M−1 x ∗ S(2j )xC• Hence:- Study x ∗ S(2j )x

Multivariate SelfSimilarity for Internet Traffic - IIJ, Tokyo, Japan - Feb. 2018 -68 / 59

Sketch of Proof - 2• Wavelet Spectrum:∗

EDy (j, k)Dy (j, k)∗ = W 2j(H+IM /2) EDx (0, k)Dx (0, k)∗ 2j(H+IM /2) W ∗∗EDy (j, k)Dy (j, k)∗ = W 2j(H+IM /2) W −1 EDY (0, k)Dy (0, k)∗ (W ∗ )−1 2j(H+IM /2) W ∗{z}|
BW ,Σ (0)jj(H+IM /2)

S(2 ) = W 2

W
|

−1

∗

DY (0, k)Dy (0, k)∗ (W ∗ )−1 2j(H+IM /2) W ∗{z}
B̂W ,Σ (0)• OFBM is well-defined:⇒ BW ,Σ (0) has bounded eigen values⇒ B̂W ,Σ (0) has bounded eigen values⇒ 0 < A ≤ λm (B̂W ,Σ (0)) ≤ B < ∞• Hence:0 < A · x ∗ WDD ∗ W ∗ x ≤ x ∗ S(2j )x ≤ B · x ∗ WDD ∗ W ∗ x < ∞with D = Diag{2jh1 , . . . , 2jhm , . . . , 2jhM }Multivariate SelfSimilarity for Internet Traffic - IIJ, Tokyo, Japan - Feb. 2018 -69 / 59

Sketch of Proof - 4• D = Diag{2jh1 , . . . , 2jhm , . . . , 2jhM }• When W = IM :0 < A · x ∗ WDD ∗ W ∗ x ≤ x ∗ S(2j )x ≤ B · x ∗ WDD ∗ W ∗ x < ∞0 < A · x ∗ DD ∗ x ≤ x ∗ S(2j )x ≤ B · x ∗ DD ∗ x < ∞∀m = 1, . . . , M, 0 < A · λm (DD ∗ ) ≤ λ(S(2j )) ≤ B · λm (DD ∗ ) < ∞∀m = 1, . . . , M, 0 < A · 22jhm ≤ λm (S(2j )) ≤ B · 22jhm < ∞⇒ ∀m = 1, . . . , M, log2 λm (S(2j ))) → 2hm · j

Multivariate SelfSimilarity for Internet Traffic - IIJ, Tokyo, Japan - Feb. 2018 -70 / 59

Sketch of Proof - 5• When W 6= IM :0 < A · x ∗ WDD ∗ W ∗ x ≤ x ∗ S(2j )x ≤ B · x ∗ WDD ∗ W ∗ x < ∞
∗

∗

x W
∗ W x
∗
2
x ∗ WDD ∗ W ∗ x = ||W∗ x|| DD ||W ∗ x|| × ||W x||

0 < A0 · ≤ ||W ∗ x||2 ≤ B 0 < +∞ since W invertible
∗

∗

∗

∗

x W
x W
∗ W x
∗
∗
∗
0
∗ W x
0 < A0 · ||W∗ x|| DD ||W ∗ x|| ≤ x WDD W x < B · ||W ∗ x|| DD ||W ∗ x|| < +∞∀m = 1, . . . , M, 0 < A · A0 · λm (DD ∗ ) ≤ λ(S(2j )) ≤ B · B 0 · λm (DD ∗ ) < ∞∀m = 1, . . . , M, 0 < A · A0 · 22jhm ≤ λm (S(2j )) ≤ B · B 0 · 22jhm < ∞⇒ ∀m = 1, . . . , M, log2 λm (S(2j ))) → 2hm · j⇒ W 6= IM does not create difficulties compared to W ≡ IM
⇒ key step in proof: BW ,Σ (0) has bounded eigen values
Multivariate SelfSimilarity for Internet Traffic - IIJ, Tokyo, Japan - Feb. 2018 -

71 / 59

Sketch of Proof - 6

• M=2


IES22 (1)22j(h1 −h2 )λ1 (2j ) = 2 det(IES) 22jh1 +IES22 (1)F (IES11 (1),IES22 (1))• Scaling range (j1 (n), j2 (n)(j1 (n), j2 (n) = (j10 + f (n), (j20 + f (n))β log2 n ≤ f (n) ≤ (1 − ) log2 n,  > 0
β = 1+2max(h ,min 1
1

1≤m<m0 ≤M (hm0 −hm ))Bias-Variance trade-offbackMultivariate SelfSimilarity for Internet Traffic - IIJ, Tokyo, Japan - Feb. 2018 -72 / 59