22 / ( ) OD (Origin-Destination)

Size: px

Start display at page:

Download "22 / ( ) OD (Origin-Destination)"

ひでかいちぬの
6 years ago
Views:

2 22 / ( ) OD (Origin-Destination)

3 i

4 47 ii

5 1 Traffic Engineering ( ) ( ) AS ( ) ( )IP IP ( ) OD (Origin-Destination) (e.g., [1] [2] [3]) [4] OD 1

6 [5] ( ) ( )

7 ping traceroute tcpdump 3

8 2.1: 2.2: 4

9 2.3 IP TCP DoS(Denial of Service) ISP Traffic Engineering NetFlow sflow [6] ( ) 1 5

10 2.3: Virtual Private Network (VPN) VPN [7] 2.4 N VPN (IP/VPN) NS 6

11 VPN LAN ルータ拠点間トラヒック IP-VPN ( インターネット ) 拠点インターネット間トラヒック 2.4:. 7

12 ネットワーク A ネットワーク B ネットワーク C フロー 1 フローフロー 2 ルータ 1 ルータ : T 2 3 X i i i =, 1, 2 Y j j j = 1, 2 (3.1) Y j = X + X j ( j = 1, 2). (3.1) 3.1 M X i i i =, 1, 2; X = (X, X 1, X 2 ) Y j j j = 1, 2; Y = (Y 1, Y 2 ) x i (m) = Pr[X i = m] i m m [, 1, 2,..., M] x i (m) i m 8

13 y j (m) j m y 12 (m) 1,2 m (3.2) X i x (), x 1 (), x 2 () > {y 1 (m), y 2 (m), y 12 (m) m = 1,..., M} x (m), x 1 (m), x 2 (m) m y j (m) = y 12 (m) = m x (m k)x j (k) ( j = 1, 2), k= m x (m k)x 1 (k)x 2 (k). (3.2) k= (3.2) x (m), x 1 (m), x 2 (m) m= m=1 x () = y 1()y 2 (), x 1 () = y 12() y 12 () y 2 (), x 2() = y 12() y 1 (). (3.3) x (1) = b 1 b 2 1 4a 1c 1, 2a 1 a 1 = x 1()x 2 (), x () b 1 = y 12() x 1 ()y 2 (1) x 2 ()y 1 (1), x () c 1 = y 1(1)y 2 (1) x () y 12 (1), x 1 (1) = x 1()x (1) + y 1 (1) y 1 (), x () x 2 (1) = x 2()x (1) + y 2 (1) y 2 (). (3.4) x () x (m) = b b 2 4ac, 2a a = x 1()x 2 (), x () b = y 12() x 1 ()B 2 x 2 ()B 1, x () c = B 1B 2 x () C, 9

14 m 1 B r = y r (m) x (m k)x r (k) (r = 1, 2), k=1 m 1 C = y 12 (m) x (m k)x 1 (k)x 2 (k), k=1 x 1 (m) = x 1()x (m) + B 1 x () x 2 (m) = x 2()x (m) + B 2 x () x 1 (m 1), x 2 (m 1). (3.5) y 1 (m), y 2 (m), y 12 (m) 1 2 ŷ 1, ŷ 2, ŷ 12 ŷ 1, ŷ 2, ŷ N Y 1 = [Y 1 (1), Y 1 (2),..., Y 1 (N)] Y 2 = [Y 2 (1), Y 2 (2),..., Y 2 (N)] (N = 1, 2,..., N) 1 s 2 t C(s, t) (3.6) ŷ 1, ŷ 2, ŷ 12 (3.2) ˆx, ˆx 1, ˆx 2 ŷ 1 (m) = 1 N ŷ 2 (m) = 1 N ŷ 12 (m) = 1 N M m C(s, t) ( j = 1, 2) t= M s= s= t= m s= t= m C(s, t) m C(s, t) (3.6) (3.3) y 1 (), y 2 (), y 12 () (3.3) 2 2 bin 1

15 3.1.1 i [, r i 1] r i r i i i r i (i =, 1, 2) 1 2 j R j 1 2 R j ( j = 1, 2) r i (i =, 1, 2) (3.7) R j = r + r j ( j = 1, 2) (3.7) r i X i = X i r i (i =, 1, 2) Y j = Y j R j ( j = 1, 2) Y j y 1() y 2 () y 12 () r r 1 r 2 R 1 R 2 R 1 R 2 r r 1 r 2 R 1 R 2 R j 1/2 j r r j R 1 < R 2 R 1 r = r 1 = R 1 /2 (3.7) r r 1 r 2 R 1 R 2 r r 1 r 2 > r r 1 r 2 R 1 R R 1 R 2 y 1 () y 2 () y 12 () + α (3.8).1 Pr[Y j R j + h].25 ( j = 1, 2).5 Pr[(Y 1 R 1 + h Y 2 R 2 + h] (3.8) h [, R j 1]( j = 1, 2) M [M, M] 11

16 3.1.2 ( ) y 1 () y 2 () y 12 () [, 1,..., M] (bin ) q [, 1,..., h] ( h = q/2 1 ) [h+1, h+2,..., q+h] 1 [(m 1)q+h+1,..., mq+h] m (y 1 y 2 y 12 ) m = 1, 2,, ((M R j h)/q) y j () = Pr[Y j R j + h] ( j = 1, 2), y j (m) = Pr[Y j R j + qm + h], y 12 () = Pr[Y 1 R 1 + h Y 2 R 2 + h], y 12 (m) = Pr[Y 1 R 1 + qm + h Y 2 R 2 + qm + h]. (3.9) y 1 y 2 y 12 (3.3) (3.4) (3.5) (x, x 1, x 2 ) m = 1, 2,, ((M r i h)/q) x i () = Pr[X i r i + h] (i =, 1, 2), x i (m) = Pr[r i + qm (h + 1) X i r i + qm + h]. (3.1) bin bin y 1 (), y 2 (), y 12 () 12

17 (ˆµ, ˆµ 1, ˆµ 2 ) M i ˆµ i = r i + q (1 x i (k)) (i =, 1, 2) (3.11) M i = ((M r i h)/q) x i m) = Pr[X j r i + qm + h] k= Y 1 = [Y 1 (1), Y 1 (2),, Y 1 (t)], Y 2 = [Y 2 (1), Y 2 (2),, Y 2 (t)] (t ) 1 2 X i = [X i (1), X i (2),, X i (t)] (i =, 1, 2) Y 1, Y 2 (Cov[Y 1, Y 2 ]) (Var[Y 1 ], Var[Y 2 ]) (3.12) Y 1, Y Cov[Y 1, Y 2 ] = 1 t Var[Y 1 ] = 1 t Var[Y 2 ] = 1 t t (Y 1 (i) Y 1 )(Y 2 (i) Y 2 ), i=1 t (Y 1 (i) Y 1 ) 2, i=1 t (Y 2 (i) Y 2 ) 2. (3.12) i=1 Y 1,2 (3.13) Cov[Y 1, Y 2 ] = Cov[X + X 1, X + X 2 ] = Var[X ], Var[Y 1 ] = Var[X ] + Var[X 1 ], Var[Y 2 ] = Var[X ] + Var[X 2 ]. (3.13) (3.12) (3.13) 1 2 (Y 1, Y 2 ) (Var[X ] Var[X 1 ] Var[X 2 ]) 13

18 フロー : NET -> SINET 九州工業大学飯塚九州工業大学若松フロー 1 : NET -> NET フロー 2 : NET -> SINET フロー 1 計測地点 1 フロー 2 計測地点 2 AX36 AX78 AX36 SINET フロー九州工業大学飯塚 ISC 九州工業大学戸畑 ISC 九州工業大学戸畑その他のネットワーク NET NET 4.1: 4 [5] , 1, 2 ) ( 1 T 1 ) 1 1[s] [1, 1], [51, 15], [11, 2],... n 14

19 [5] 3 1, 2 ˆµ i (i =, 1, 2) i ν j ( j = 1, 2) j j f g f g (4.1) f = ˆµ + ˆµ 1 ν 1, g = ˆµ + ˆµ 2 ν 2 (4.1) n i ˆµ (n) i ˆµ i (i =, 1, 2) 3 n n n (4.2) ˆµ i = αˆµ (n) i + βˆµ (n ) i + γˆµ (n ) i (i =, 1, 2) (4.2) α + β + γ = 1 α, β, γ 1 f 2 + g 2 α β γ (4.1) (RMS) µ i (t) ˆµ i (t) t i ν j (t) j N w (4.3) i (e (t) e 1 (t) e 2 (t)) (4.4) RMS P 3 RMS (4.5) RMS 3 RMS 9%tile 15

20 e (t) = µ (t) ˆµ (t) min(ν 1 (t), ν 2 (t)), e j(t) = µ j (t) ˆµ j (t) ν j (t) (4.3) e = 1 N w N w t=1 e (t) 2, e j = 1 N w N w t=1 e j (t) 2 (4.4) e = 1 P P {e (t) 2 + e 1 (t) 2 + e 2 (t) 2 } (4.5) t=1 16

21 5 dataset dataset 1 ( ) dataset 2 ( ) dataset 3 ( ) : dataset parameters value (T) [s].2 5 samples (W) [s] 1 (n) 2, 4, 8 3 dataset UDP/TCP dataset1 TCP 5.1 dataset2 UDP 5.2 dataset 3 TCP dataset UDP real-i inferred-i i (3.7) RMS RMS [5] (i.e., (4.1) α β γ = 1 3 ) RMS

22 5.2 3 RMS RMS dataset (4.3) 3 RMS RMS RMS 18

23 3 UDP / UDP / RMS 9%tile dataset 1 1[s] dataset 2 37[s] dataset 3 43[s] UDP/TCP / RMS 9%tile UDP/TCP RMS 9%tile UDP/TCP 19

24 3 Avg number of pkts [pps] real- inferred- real-1 inferred-1 real-2 inferred-2 5.1: dataset1 TCP 6 Avg number of pkts [Bps] real- inferred- real-1 inferred-1 real-2 inferred-2 5.2: dataset2 UDP 5 Avg number of pkts [Bps] real- inferred- real-1 inferred-1 real-2 inferred-2 5.3: dataset3 TCP 2

25 5.2: dataset 1 TCP ( RMS ) : dataset 2 UDP ( RMS )

26 5.4: dataset 3 TCP ( RMS ) : UDP ( ) RMS %tile RMS %tile : TCP ( ) RMS %tile RMS %tile

27 , 1, 2 6 ( ) a, b, c, a, b, c 6 ab, ac, ba, bc, ca, cb ab a b a, b, c, a, b, c Y a, Y b, Y c, Y a, Y b, Y c X ab, X ac, X ba, X bc, X ca, X cb ( ) (6.1) Y a = X ab + X ac, Y b = X ba + X bc, Y c = X ca + X cb, Y a = X ba + X ca, Y b = X ab + X cb, Y c = X ac + X bc (6.1) ( {, 3, 1} {, 3, 2}, {1, 3, 2} ) {, 3, 1} 2 {, 3, 2} 3 {1, 3, } 1 4 {1, 3, 2} 5 {2, 3, } 2 6 {2, 3, 1} ab, ac, cb 2 ac, ab, bc 3 ba, bc, ca 4 bc, ba, ac 5 ca, cb, ba 6 cb, ca, ab 3 (e.g., ab 1, 2, 6 ) ( ) 3 23

6.1: 3 6.1 r ab, r ac, r ba, r bc, r ca, r cb R a, R b, R c, R a, R b, R c (6.2) R a = r ab + r ac, R b = r ba + r bc, R c = r ca + r cb, R a = r ba + r ca, R b = r ab + r cb, R c = r ac + r bc (6.

28 6.1: r ab, r ac, r ba, r bc, r ca, r cb R a, R b, R c, R a, R b, R c (6.2) R a = r ab + r ac, R b = r ba + r bc, R c = r ca + r cb, R a = r ba + r ca, R b = r ab + r cb, R c = r ac + r bc (6.2) ( ) min(r a, R b, R c, R a, R b, R c ) = R a r ab r ac min(r b, R c ) = R b r ab min(r b, R c ) = R c r ac (6.2) r ab, r ac, r ba, r bc, r ca, r cb min(r a, R b, R c, R a, R b, R c ) = R a R b < R c 24

29 6.3: 2 6.2: 1 (6.2) r ab (6.3) r ac = R a r ab, r ba = R b R c + R a r ab, r bc = R c R a + r ab, r ca = R c R b + r ab, r cb = R b r ab (6.3) (6.3) r ab, r ac, r ba, r bc, r ca, r cb r ab (6.4) r ab, r ab R a, 25

30 6.4: 3 6.5: 4 r ab R c R a, r ab R b, r ab R c R b, r ab R b R c + R a (6.4) (6.4) r ab r ab (6.5) r ab R a, r ab R b R c R a, R c R a r ab R a, R c R a r ab R b R c + R a, R c R b r ab R a, R c R b r ab R b R c + R a (6.5) r ab ( + )/2 26

31 6.6: 5 6.7: 6 (6.6) r ab = R a 2, r ab = R b R c R a, 2 r ab = R c 2, r ab = R b 2, r ab = R c R b + R a, 2 r ab = R c R b + R b R c + R a 2 (6.6) r ab (6.3) 3 27

32 6.2 4 a, b,..., c ( ) ˆµ ν f a, f b,..., f c (6.7) f a = 1 ˆµ ab +ˆµ ac ν a, f b = 1 ˆµ ba +ˆµ bc ν b, f c = 1 ˆµ ca +ˆµ cb ν c, f a = 1 ˆµ ba +ˆµ ca ν a, f b = 1 ˆµ ab +ˆµ cb ν b, f c = 1 ˆµ ac +ˆµ bc ν c (6.7) j( j = 1, 2,.., 6) n w ˆµ (n) w j 3 3 ( n, n, n ) 9 ˆµ w (6.8) ˆµ ab = α 1 ˆµ (n) + α ab 2 ˆµ (n ) + α 1 ab 3 ˆµ (n ) + β 1 ab 1 ˆµ (n) + β 1 ab 2 ˆµ (n ) + β 2 ab 3 ˆµ (n ) + ζ 2 ab 1 ˆµ (n) + ζ 2 ab 2 ˆµ (n ) + ζ ab 6 3 ˆµ (n ) ab 6 6 ˆµ ac = α 1 ˆµ (n) + α ac 2 ˆµ (n ) + α 1 ac 3 ˆµ (n ) + β 1 ac 1 ˆµ (n) + β 1 ac 2 ˆµ (n ) + β 2 ac 3 ˆµ (n ) + δ 2 ac 1 ˆµ (n) + δ 2 ac 2 ˆµ (n ) + δ 4 ac 3 ˆµ (n ) 4 ac 4 ˆµ ba = γ 1 ˆµ (n) + γ ba 2 ˆµ (n ) + γ 3 ba 3 ˆµ (n ) + δ 3 ba 1 ˆµ (n) + δ 3 ba 2 ˆµ (n ) + δ 4 ba 3 ˆµ (n ) + ɛ 4 ba 1 ˆµ (n) + ɛ 4 ba 2 ˆµ (n ) + ɛ ba 5 3 ˆµ (n ) ba 5 5 ˆµ bc = β 1 ˆµ (n) + β bc 2 ˆµ (n ) + β 2 bc 3 ˆµ (n ) + γ 2 bc 1 ˆµ (n) + γ 2 bc 2 ˆµ (n ) + γ 3 bc 3 ˆµ (n ) + δ 3 bc 1 ˆµ (n) + δ 3 bc 2 ˆµ (n ) + δ 4 bc 3 ˆµ (n ) 4 bc 4 ˆµ ca = γ 1 ˆµ (n) + γ ca 2 ˆµ (n ) + γ 3 ca 3 ˆµ (n ) + ɛ 3 ca 1 ˆµ (n) + ɛ 3 ca 2 ˆµ (n ) + ɛ ca 5 3 ˆµ (n ) + ζ ca 5 1 ˆµ (n) + ζ ca 5 2 ˆµ (n ) + ζ ca 6 3 ˆµ (n ) ca 6 6 ˆµ cb = α 1 ˆµ (n) + α cb 2 ˆµ (n ) + α 1 cb 3 ˆµ (n ) + ɛ 1 cb 1 ˆµ (n) + ɛ 1 cb 2 ˆµ (n ) + ɛ cb 5 3 ˆµ (n ) + ζ cb 5 1 ˆµ (n) + ζ cb 5 2 ˆµ (n ) + ζ cb 6 3 ˆµ (n ) cb 6 6 (6.8) (6.9) α 1,..., ζ 3 1 f a 2 + f b f c 2 α 1,..., ζ 3 18 α 1 + α 2 + α 3 + β 1 + β 2 + β 3 + ζ 1 + ζ 2 + ζ 3 = 1 α 1 + α 2 + α 3 + β 1 + β 2 + β 3 + δ 1 + δ 2 + δ 3 = 1 γ 1 + γ 2 + γ 3 + δ 1 + δ 2 + δ 3 + ɛ 1 + ɛ 2 + ɛ 3 = 1 β 1 + β 2 + β 3 + γ 1 + γ 2 + γ 3 + δ 1 + δ 2 + δ 3 = 1 28

33 γ 1 + γ 2 + γ 3 + ɛ 1 + ɛ 2 + ɛ 3 + ζ 1 + ζ 2 + ζ 3 = 1 α 1 + α 2 + α 3 + ɛ 1 + ɛ 2 + ɛ 3 + ζ 1 + ζ 2 + ζ 3 = 1 (6.9) (RMS) µ i j (t) ˆµ i j (t) t ν i (t), ν j (t) N w (6.1) ( e i j (t) ) (6.11) RMS P 6 RMS (6.12) RMS 6 RMS 9%tile e ab (t) = µ ab (t) ˆµ ab (t) min(ν a (t), ν b (t)), e ac (t) = µ ac (t) ˆµ ac (t) min(ν a (t), ν c (t)), e ba (t) = µ ba (t) ˆµ ba (t) min(ν b (t), ν a (t)), e bc (t) = µ bc (t) ˆµ bc (t) min(ν b (t), ν c (t)), e ca (t) = µ ca (t) ˆµ ca (t) min(ν c (t), ν a (t)), e cb (t) = µ cb (t) ˆµ cb (t) min(ν c (t), ν b (t)) (6.1) N 1 w N 1 w 1 N w e ab = e ab (t) N 2, e ac = e ac (t) w N 2, e ba = e ba (t) t=1 w N 2, t=1 w t=1 N 1 w N 1 w 1 N w e bc = e bc (t) 2, e ca = e ca (t) 2, e cb = e cb (t) 2 (6.11) N w t=1 N w t=1 N w t=1 e = 1 P P {e ab (t) 2 + e ac (t) e cb (t) 2 } (6.12) t=1 29

34 real inferred ( a ) 2 1 ( a ) 3 UDP TCP RMS (6.1) 1 ab, ac 7.1 ab RMS 1.12, 1.48 ac RMS.93, RMS ab.38,.54 ac.33,.48 ( a ) 1 ba, bc 7.7 RMS ba , bc , RMS ba.12,.15 bc.11,

35 3 31

36 15 2 Avg number of pkts [pps] Avg number of pkts [Bps] Ya Yb Yc YA YB YC Ya Yb Yc YA YB YC (a) 1 (a) Avg number of pkts [pps] Avg number of pkts [Bps] Ya Yb Yc YA YB YC Ya Yb Yc YA YB YC (b) 2 (b) Avg number of pkts [pps] Avg number of pkts [Bps] Ya Yb Yc YA YB YC Ya Yb Yc YA YB YC (c) 3 (c) 3 7.1: (TCP ) 7.2: (TCP ) 32

37 3 9 Avg number of pkts [pps] Avg number of pkts [Bps] Ya Yb Yc YA YB YC Ya Yb Yc YA YB YC (a) 1 (a) Avg number of pkts [pps] Avg number of pkts [Bps] Ya Yb Yc YA YB YC Ya Yb Yc YA YB YC (b) 2 (b) Avg number of pkts [pps] Avg number of pkts [Bps] Ya Yb Yc YA YB YC Ya Yb Yc YA YB YC (c) 3 (c) 3 7.3: (TCP ) 7.4: (TCP ) 33

38 1 15 Avg number of packets [pps] Avg number of Bytes [Bps] real-ab real-ac real-ba real-bc real-ca real-cb real-ab real-ac real-ba real-bc real-ca real-cb Avg number of packets [pps] Avg number of Bytes [Bps] inferred-ab inferred-ac inferred-ba inferred-bc inferred-ca inferred-cb inferred-ab inferred-ac inferred-ba inferred-bc inferred-ca inferred-cb 7.5: UDP ( 1 ) 7.6: UDP ( 3) 34

39 2 5 Avg number of pkts [pps] Avg number of Bytes [Bps] real-ab real-ac real-ba real-bc real-ca real-cb real-ab real-ac real-ba real-bc real-ca real-cb Avg number of pkts [pps] Avg number of Bytes [Bps] inferred-ab inferred-ac inferred-ba inferred-bc inferred-ca inferred-cb inferred-ab inferred-ac inferred-ba inferred-bc inferred-ca inferred-cb 7.7: TCP ( 2) 7.8: TCP ( 1 ) 35

40 Variance 6 4 Variance real-ab real-ac real-ba real-bc real-ca real-cb real-ab real-ac real-ba real-bc real-ca real-cb Variance 6 4 Variance inferred-ab inferred-ac inferred-ba inferred-bc inferred-ca inferred-cb inferred-ab inferred-ac inferred-ba inferred-bc inferred-ca inferred-cb 7.9: UDP 7.1: UDP ( 1 ) ( 3) 36

41 Variance 6 4 Variance real-ab real-ac real-ba real-bc real-ca real-cb real-ab real-ac real-ba real-bc real-ca real-cb Variance 6 4 Variance inferred-ab inferred-ac inferred-ba inferred-bc inferred-ca inferred-cb inferred-ab inferred-ac inferred-ba inferred-bc inferred-ca inferred-cb 7.11: TCP 7.12: TCP ( 2) ( 1 ) 37

42 7.1: UDP ( 1) flowab flowac flowba flowbc flowca flowcb RMS : UDP ( 1) flowab flowac flowba flowbc flowca flowcb RMS : UDP ( 3) flowab flowac flowba flowbc flowca flowcb RMS : UDP ( 3) flowab flowac flowba flowbc flowca flowcb RMS

43 7.5: TCP ( 2) flowab flowac flowba flowbc flowca flowcb RMS : TCP ( 2) flowab flowac flowba flowbc flowca flowcb RMS : TCP ( 1) flowab flowac flowba flowbc flowca flowcb RMS : TCP ( 1) flowab flowac flowba flowbc flowca flowcb RMS

44 , 4, ab, ac a 2 ba, ca a 3 2 1, 2 1 (e.g., 1 ab, ac ) ca 2, 4, 8 RMS.35,.44, RMS 7.9 ac 2, 4, 8.86,.48, ca 2, 4, 8.7,.7, ab 2, 4, 8.9,.12,

45 7.11 ba.76, 2.82, UDP / TCP / RMS 9%tile RMS 9%tile RMS 9%tile UDP / TCP / RMS 9%tile 41

46 7.9: UDP ( RMS 1 ) ab ac ba bc ca cb ab ac ba bc ca cb : UDP ( RMS 3 ) ab ac ba bc ca cb ab ac ba bc ca cb

47 7.11: TCP ( RMS 2 ) ab ac ba bc ca cb ab ac ba bc ca cb : TCP ( RMS 1 ) ab ac ba bc ca cb ab ac ba bc ca cb

48 7.13: ( UDP UDP ) RMS %tile RMS %tile : ( TCP TCP ) RMS %tile RMS %tile

49 8 RMS 3 RMS 9%tile RMS RMS 9%tile 45

50 46

51 [1] J. Cao, D. Davis, S.V. Wiel, and B. Yu. Time-Varying Network Tomography: Router Link Data. Journal of the American Statistical Association, Vol. 95, No. 452, pp , 2. [2] G. Liang and B. Yu. Maximum pseudo likelihood estimation in network tomography. Signal Processing, IEEE Transactions on [see also Acoustics, Speech, and Signal Processing, IEEE Transactions on], Vol. 51, No. 8, pp , 23. [3] Y. Vardi. Network Tomography: Estimating Source-Destination Traffic Intensities from Link Data. Journal of the American Statistical Association, Vol. 91, No. 433, pp , [4] M. Tsuru, T. Takine, and Y. Oie. Inferring arrival rate statistics of individual flows from aggregatedflow rate measurements. In Applications and the Internet, 23. Proceedings. 23 Symposium on, pp , 23. [5],,,,... CS28-66, pp. 55 6, 28. [6],,,,... NS,, Vol. 11, No. 714, pp , 22. [7].., 15,

Ł\”ƒ-2005

$Ł\”ƒ-2005$