拡張したトポロジにおける加重混合法の適用

拡張したトポロジにおいて，4章にて説明を行った加重混合法を拡張適用する．

具体的には，ルータa,b, . . . ,c⁰における集約フローの平均流量の真の値(計測可能)と各フローの 平均流量の推定値の和の関係に着目し，以下のような方法をとる．まず，ˆµを，各フローの平均流量 の推定値，νを各ルータにて計測可能な集約フローの平均流量とし，各ルータでの集約フローの平均 流量の真の値と推定値の差を相対化したものをそれぞれ f_a,f_b, . . . ,f_c0とおくと，以下の式(6.7)で表 される．

f_a=|1−^µˆab0_ν⁺_a^µˆac0|,f_b=|1−^µˆba0_ν⁺_b^µˆbc0|, fc=|1−^µˆca0_ν⁺_c^µˆcb0|,fa⁰=|1−^µˆba0_ν⁺_a0^µˆca0|,

fb⁰=|1−^µˆab0_ν⁺_b0^µˆcb0|,fc⁰=|1−^µˆac0_ν⁺_c0^µˆbc0| (6.7) この時，向きを含めた基本トポロジ j(j=1,2, ..,6)上で分割数nを用いて推定したフローwの平均 流量をµˆ⁽ⁿ⁾wj と書くと，各フロー毎に3つの単純トポロジにおける3通りの分割数(n,n⁰,n⁰⁰)での9 個の推定値の加重平均を最終推定値µˆwとすると，式(6.8)の形になる．

µˆab⁰ = α1µˆ⁽ⁿ⁾_ab0

1+α2µˆ⁽ⁿ_ab⁰0⁾

1+α3µˆ^(n”)_ab0

1 +β1µˆ⁽ⁿ⁾_ab0

2+β2µˆ⁽ⁿ_ab⁰0⁾

2+β3µˆ^(n”)_ab0 2 +ζ1µˆ⁽ⁿ⁾_ab0

6+ζ2µˆ⁽ⁿ_ab⁰0⁾

6 +ζ3µˆ^(n”)_ab0 6

µˆac⁰ = α1µˆ⁽ⁿ⁾_ac0

1+α2µˆ⁽ⁿ_ac⁰0⁾

1 +α3µˆ^(n”)_ac0

1 +β1µˆ⁽ⁿ⁾_ac0

2+β2µˆ⁽ⁿ_ac⁰0⁾

2+β3µˆ^(n”)_ac0

2 +δ1µˆ⁽ⁿ⁾_ac0

4+δ2µˆ⁽ⁿ_ac⁰0⁾

4 +δ3µˆ^(n”)_ac0 4

µˆba⁰ = γ1µˆ⁽ⁿ⁾_ba0

3+γ2µˆ⁽ⁿ_ba⁰0⁾

3+γ3µˆ^(n”)_ba0

3 +δ1µˆ⁽ⁿ⁾_ba0

4+δ2µˆ⁽ⁿ_ba⁰0⁾

4+δ3µˆ^(n”)_ba0

4 +1µˆ⁽ⁿ⁾_ba0

5+2µˆ⁽ⁿ_ba⁰0⁾

5+3µˆ^(n”)_ba0 5

µˆbc⁰ = β1µˆ⁽ⁿ⁾_bc0

2+β2µˆ⁽ⁿ_bc⁰0⁾

2+β3µˆ^(n”)_bc0

2 +γ1µˆ⁽ⁿ⁾_bc0

3+γ2µˆ⁽ⁿ_bc⁰0⁾

3 +γ3µˆ^(n”)_bc0

3 +δ1µˆ⁽ⁿ⁾_bc0

4+δ2µˆ⁽ⁿ_bc⁰0⁾

4 +δ3µˆ^(n”)_bc0 4

µˆca⁰ = γ1µˆ⁽ⁿ⁾_ca0

3+γ2µˆ⁽ⁿ_ca⁰0⁾

3 +γ3µˆ^(n”)_ca0 3 +1µˆ⁽ⁿ⁾_ca0

5+2µˆ⁽ⁿ_ca⁰0⁾

5+3µˆ^(n”)_ca0 5 +ζ1µˆ⁽ⁿ⁾_ca0

6+ζ2µˆ⁽ⁿ_ca⁰0⁾

6 +ζ3µˆ^(n”)_ca0 6

µˆcb⁰ = α1µˆ⁽ⁿ⁾_cb0

1+α2µˆ⁽ⁿ_cb⁰0⁾

1 +α3µˆ^(n”)_cb0 1 +1µˆ⁽ⁿ⁾_cb0

5+2µˆ⁽ⁿ_cb⁰0⁾

5 +3µˆ^(n”)_cb0 5 +ζ1µˆ⁽ⁿ⁾_cb0

6+ζ2µˆ⁽ⁿ_cb⁰0⁾

6+ζ3µˆ^(n”)_cb0 6

(6.8)

この時，以下の式(6.9)，および，0≤α1, . . . , ζ3≤1の制約のもとで，fa2+fb2+. . .+fc⁰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

γ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)を各 ルータにて計測可能な集約流量の平均値とし，推定ウィンドウの数をNwとすると，式(6.10)で各フ ローの相対誤差(e_{i j}(t) )を定義し，式(6.11)相対誤差のRMSを算出する．また，推定実験を行った 全てのトラヒックデータサンプル数をPとし，全サンプルにおいて6フロー全てを通して見た相対

誤差のRMSは式(6.12)のようになる．以下では，各フローにおける相対誤差のRMS，最悪値，お

よび推定実験を行った全トラヒックデータサンプルにおける6つのフロー全てを通して見た際にお ける相対誤差のRMS，90%tile等を調査する．

eab⁰(t)= µab⁰(t)−µˆab⁰(t) min(νa(t), νb⁰(t))

, eac⁰(t)= µac⁰(t)−µˆac⁰(t) min(νa(t), νc⁰(t))

, eba⁰(t)= µba⁰(t)−µˆba⁰(t) min(νb(t), νa⁰(t))

, ebc⁰(t)= µbc⁰(t)−µˆbc⁰(t)

min(νb(t), νc⁰(t))

, eca⁰(t)= µca⁰(t)−µˆca⁰(t) min(νc(t), νa⁰(t))

, ecb⁰(t)= µcb⁰(t)−µˆcb⁰(t) min(νc(t), νb⁰(t))

(6.10)

eab0= vu t 1

N_w

Nw

∑

t=1

eab0(t)², eac0 = vu t 1

N_w

Nw

∑

t=1

eac0(t)², eba0= vu t 1

N_w

Nw

∑

t=1

eba0(t)²,

ebc⁰= vu t 1

Nw N_w

∑

t=1

ebc⁰(t)², eca⁰= vu t 1

Nw N_w

∑

t=1

eca⁰(t)², ecb⁰= vu t 1

Nw N_w

∑

t=1

ecb⁰(t)² (6.11)

e= vu t1

P

∑P t=1

{eab⁰(t)²+eac⁰(t)²+. . .+ecb⁰(t)²} (6.12)

7 拡張したトポロジにおける推定結果

拡張したトポロジにおいて推定を行った際の平均流量の推定結果を図7.5から図7.8，分散の推定 結果を図7.9から図7.12に示す．なお，量子化に使用する分割数は40で行った．ここで，図中の realは各フローの平均流量の真値，inferredは各フローの推定値である．なお，推定を行うに当たっ て仮想的にフローを作成し，推定を行った．その際の集約フローを図7.1から図7.4に示す．作成し た集約流量に関してであるが，パターン1はある1つのルータにおける上り方向の集約フロー流量 が極端に小さいフロー(ルータaにおける集約フロー流量が極端に小さいパターン)，パターン2は ある1つのルータにおける下り方向の集約フロー流量が極端に小さいパターン(ルータa⁰における 集約フロー流量が極端に小さいパターン)，パターン3は各集約フロー流量に他のパターンほど差が なく，極端に小さい集約フローがないパターンである．

各パターンにおいてUDPパケット数・バイト数，TCPパケット数・バイト数に対して推定を行った 結果，各フローの平均流量に関しては，いずれの場合においても推定値と真値におけるある程度の誤 差はあるが，それぞれのフローの大小関係やその増減などの追従が出来ていることがわかる．また，

図7.9から図7.12にある各フロー流量の分散だが，いずれの場合においても，精度よく推定できてい ることが確認できた．以上の結果より，基本トポロジにおける推定手法は拡張したトポロジにおいて も有効性があるということがわかった．また，各フローの絶対誤差と相対誤差のRMS，最悪時誤差を 表7.1から表7.8に示す．ここで，最悪時誤差とは，式(6.10)で定義した相対誤差のうち，最悪値を 示す．パターン1のフローab⁰,ac⁰をみると，表7.1でのフローab⁰は絶対誤差のRMSおよび最悪時 誤差が1.12,1.48，フローac⁰は絶対誤差のRMSおよび最悪時誤差が0.93,1.29と他のフローに比べ て小さいが，表7.2におけるそれぞれの相対誤差のRMSおよび最悪時誤差はフローab⁰が0.38,0.54，

フローac⁰が0.33,0.48と，他のフローに比べて，集約フロー流量が極端に小さいフローを形成する

フロー(この場合はルータaの集約フロー流量が極端に小さい)は絶対誤差は小さいが，相対的に推

定誤差が大きくなることがわかった．しかし，パターン1のフローba⁰,bc⁰を見ると，表7.7にある 絶対誤差のRMSと最悪時誤差がフローba⁰で53380.63,64848.28，フローbc⁰で32918.66,41684.90 と，他のフローに比べて大きいが，表7.8におけるそれぞれの相対誤差のRMSおよび最悪時誤差は フローba⁰で0.12,0.15，フローbc⁰で0.11,0.19と，他のフローと比較して流量が大きいフローに関 しては絶対誤差は大きいが，相対誤差は小さくなるということがわかった．また，表7.3，表7.4に

あるパターン3の場合を見ると，各フロー共に絶対誤差は大きいが，相対誤差は小さいことがわか る．よって，集約フロー流量で極端に小さいフローがないときは，相対的に推定誤差が小さく推定で きることがわかった．

0 30 60 90 120 150

0 1000 2000 3000 4000 5000

Avg number of pkts [pps]

Time [s]

Ya

Yb Yc

YA YB

YC

(a)パターン1

0 30 60 90 120 150

0 1000 2000 3000 4000 5000

Avg number of pkts [pps]

Time [s]

Ya

Yb Yc

YA YB

YC

(b)パターン2

0 30 60 90 120 150

0 1000 2000 3000 4000 5000

Avg number of pkts [pps]

Time [s]

Ya Yb

Yc YA

YB YC

(c)パターン3

図7.1:作成した集約流量(TCPパケット数)

0 40000 80000 120000 160000 200000

0 1000 2000 3000 4000 5000

Avg number of pkts [Bps]

Time [s]

Ya

Yb Yc

YA YB

YC

(a)パターン1

0 40000 80000 120000 160000 200000

0 1000 2000 3000 4000 5000

Avg number of pkts [Bps]

Time [s]

Ya

Yb Yc

YA YB

YC

(b)パターン2

0 40000 80000 120000 160000 200000

0 1000 2000 3000 4000 5000

Avg number of pkts [Bps]

Time [s]

Ya Yb

Yc YA

YB YC

(c)パターン3

図7.2:作成した集約流量(TCPバイト数)

0 600 1200 1800 2400 3000

0 1000 2000 3000 4000 5000

Avg number of pkts [pps]

Time [s]

Ya

Yb Yc

YA YB

YC

(a)パターン1

0 600 1200 1800 2400 3000

0 1000 2000 3000 4000 5000

Avg number of pkts [pps]

Time [s]

Ya

Yb Yc

YA YB

YC

(b)パターン2

0 600 1200 1800 2400 3000

0 1000 2000 3000 4000 5000

Avg number of pkts [pps]

Time [s]

Ya Yb

Yc YA

YB YC

(c)パターン3

図7.3:作成した集約流量(TCPパケット数)

0 180000 360000 540000 720000 900000

0 1000 2000 3000 4000 5000

Avg number of pkts [Bps]

Time [s]

Ya

Yb Yc

YA YB

YC

(a)パターン1

0 140000 280000 420000 560000 700000

0 1000 2000 3000 4000 5000

Avg number of pkts [Bps]

Time [s]

Ya

Yb Yc

YA YB

YC

(b)パターン2

0 120000 240000 360000 480000 600000

0 1000 2000 3000 4000 5000

Avg number of pkts [Bps]

Time [s]

Ya Yb

Yc YA

YB YC

(c)パターン3

図7.4:作成した集約流量(TCPバイト数)

0 20 40 60 80 100

0 1000 2000 3000 4000 5000

Avg number of packets [pps]

Time [s]

real-aB real-aC

real-bA real-bC

real-cA real-cB

0 20 40 60 80 100

0 1000 2000 3000 4000 5000

Avg number of packets [pps]

Time [s]

inferred-aB inferred-aC inferred-bA

inferred-bC inferred-cA inferred-cB

図7.5: UDPパケット数の平均流量

(上部：真値，下部：推定値，パターン1 )

0 30000 60000 90000 120000 150000

0 1000 2000 3000 4000 5000

Avg number of Bytes [Bps]

Time [s]

real-aB real-aC

real-bA real-bC

real-cA real-cB

0 30000 60000 90000 120000 150000

0 1000 2000 3000 4000 5000

Avg number of Bytes [Bps]

Time [s]

inferred-aB inferred-aC inferred-bA

inferred-bC inferred-cA inferred-cB

図7.6: UDPバイト数の平均流量

(上部：真値，下部：推定値，パターン3)

0 400 800 1200 1600 2000

0 1000 2000 3000 4000 5000

Avg number of pkts [pps]

Time [s]

real-aB real-aC

real-bA real-bC

real-cA real-cB

0 400 800 1200 1600 2000

0 1000 2000 3000 4000 5000

Avg number of pkts [pps]

Time [s]

inferred-aB inferred-aC inferred-bA

inferred-bC inferred-cA inferred-cB

図7.7: TCPパケット数の平均流量

(上部：真値，下部：推定値，パターン2)

0 100000 200000 300000 400000 500000

0 1000 2000 3000 4000 5000

Avg number of Bytes [Bps]

Time [s]

real-aB real-aC

real-bA real-bC

real-cA real-cB

0 100000 200000 300000 400000 500000

0 1000 2000 3000 4000 5000

Avg number of Bytes [Bps]

Time [s]

inferred-aB inferred-aC inferred-bA

inferred-bC inferred-cA inferred-cB

図7.8: TCPバイト数の平均流量

(上部：真値，下部：推定値，パターン1 )

0 20 40 60 80 100

0 1000 2000 3000 4000 5000

Variance

Time [s]

real-aB real-aC

real-bA real-bC

real-cA real-cB

0 20 40 60 80 100

0 1000 2000 3000 4000 5000

Variance

Time [s]

inferred-aB inferred-aC inferred-bA

inferred-bC inferred-cA inferred-cB

図7.9: UDPパケット数の分散

(上部：真値，下部：推定値，パターン1 )

0 4000 8000 12000 16000 20000

0 1000 2000 3000 4000 5000

Variance

Time [s]

real-aB real-aC

real-bA real-bC

real-cA real-cB

0 4000 8000 12000 16000 20000

0 1000 2000 3000 4000 5000

Variance

Time [s]

inferred-aB inferred-aC inferred-bA

inferred-bC inferred-cA inferred-cB

図7.10: UDPバイト数の分散

(上部：真値，下部：推定値，パターン3)

0 2000 4000 6000 8000 10000

0 1000 2000 3000 4000 5000

Variance

Time [s]

real-aB real-aC

real-bA real-bC

real-cA real-cB

0 2000 4000 6000 8000 10000

0 1000 2000 3000 4000 5000

Variance

Time [s]

inferred-aB inferred-aC inferred-bA

inferred-bC inferred-cA inferred-cB

図7.11: TCPパケット数の分散

(上部：真値，下部：推定値，パターン2)

0 100000 200000 300000 400000 500000

0 1000 2000 3000 4000 5000

Variance

Time [s]

real-aB real-aC

real-bA real-bC

real-cA real-cB

0 100000 200000 300000 400000 500000

0 1000 2000 3000 4000 5000

Variance

Time [s]

inferred-aB inferred-aC inferred-bA

inferred-bC inferred-cA inferred-cB

図7.12: TCPバイト数の分散

(上部：真値，下部：推定値，パターン1 )

表7.1: UDPパケット数の平均流量推定における絶対誤差(パターン1) flowab’ flowac’ flowba’ flowbc’ flowca’ flowcb’

RMS誤差 1.12 0.93 8.48 4.99 5.33 1.83

最悪時誤差 1.48 1.29 10.33 6.65 9.09 3.34

表7.2: UDPパケット数の平均流量推定における相対誤差(パターン1)

flowab’ flowac’ flowba’ flowbc’ flowca’ flowcb’

RMS誤差 0.38 0.33 0.11 0.17 0.09 0.06

最悪時誤差 0.54 0.48 0.15 0.22 0.17 0.11

表7.3: UDPバイト数の平均流量推定における絶対誤差(パターン3)

flowab’ flowac’ flowba’ flowbc’ flowca’ flowcb’

RMS誤差 2438.38 4714.51 6167.57 8918.44 1965.41 2284.73 最悪時誤差 4041.03 6563.25 13326.96 15848.28 3006.61 3265.51

表7.4: UDPバイト数の平均流量推定における相対誤差(パターン3)

flowab’ flowac’ flowba’ flowbc’ flowca’ flowcb’

RMS誤差 0.08 0.11 0.10 0.08 0.07 0.07

最悪時誤差 0.12 0.20 0.17 0.10 0.09 0.11

表7.5: TCPパケット数の平均流量推定における絶対誤差(パターン2) flowab’ flowac’ flowba’ flowbc’ flowca’ flowcb’

RMS誤差 72.80 110.46 18.87 69.13 2.18 45.37

最悪時誤差 86.47 143.29 50.86 100.14 4.69 63.37

表7.6: TCPパケット数の平均流量推定における相対誤差(パターン2)

flowab’ flowac’ flowba’ flowbc’ flowca’ flowcb’

RMS誤差 0.04 0.07 2.82 0.08 0.45 0.10

最悪時誤差 0.05 0.10 7.41 0.11 0.73 0.16

表7.7: TCPバイト数の平均流量推定における絶対誤差(パターン1)

flowab’ flowac’ flowba’ flowbc’ flowca’ flowcb’

RMS誤差 288.31 237.64 53380.63 32918.66 20028.98 5987.98 最悪時誤差 583.34 567.71 64848.28 41864.90 37480.70 11976.69

表7.8: TCPバイト数の平均流量推定における相対誤差(パターン1)

flowab’ flowac’ flowba’ flowbc’ flowca’ flowcb’

RMS誤差 0.37 0.32 0.12 0.11 0.11 0.05

最悪時誤差 0.64 0.62 0.15 0.19 0.20 0.09

7.1 加重混合法を適用した推定結果

表7.9から表7.12に推定結果の相対誤差を示す．表中の20分割，40分割，80分割とは，それぞ れ量子化時の分割数を20,40,80として推定し，各フロー3つの推定結果の中央値を推定値とした際 の結果である．また，表中のパターン1とはフローab⁰,ac⁰が他のフローと比べて流量が極端に小さ いフロー，つまりルータaのみ流量が極端に小さいパターン，パターン2とはフローba⁰,ca⁰が他の フローと比べて流量が極端に小さいフロー，つまりルータa⁰のみ流量が極端に小さいパターン，パ ターン3はルータにおける集約フロー流量が他の2パターンと比較してそれほど差がないパターン である．表を見ると，絶対誤差に関しては流量が小さいフローよりも流量が大きいフローの方が推定 誤差が大きくなっているが，相対誤差は流量が小さいフローの方が流量が大きいフローよりも推定誤 差が大きいことがわかる．また，パターン1,2のようにある1つの集約フロー流量のみが極端に小さ いときは，その集約フローを形成する各フロー(e.g.,パターン1の場合はフローab⁰,ac⁰)において相 対誤差が大きくなることがわかった．

表7.9から表7.12の推定結果の相対誤差を見ると，表7.11のフローca⁰のように，20,40,80分割で の相対誤差のRMS誤差が0.35,0.44,0.51に対して，提案する加重混合法を適用し推定を行うと，相対 誤差が0.27とRMS誤差が大幅に低減しているフローがあることがわかる．また，相対誤差の最悪時 誤差を見ると，例えば表7.9のフローac⁰のように，分割数20,40,80の際の推定誤差0.86,0.48,0.48 に対して，加重混合法を適用した推定結果は0.31と，最良時の分割数の選択時と比較して大幅に推 定誤差が低減していることがわかる．これは，今回使用した集約フローの平均流量の真値と推定値に 原因がある．一般に，各フロー流量において誤差が小さければ，そのフロー流量の和である集約フ ロー流量でも誤差が小さくなる．よって，今回集約フローの平均流量の真値と推定値の差が最小にな るような加重平均をとることにより，誤差が大きい分割数における推定結果の影響が低減され，推 定誤差が低減したと考える．しかし，表7.10のフローca⁰のように，分割数が20,40,80の推定誤差 が0.07,0.07,0.11に対して，加重混合法を適用すると0.14と推定誤差が増加しているフローも存在 することがわかる．また，相対誤差の最悪時誤差を見ると，例えば例えば表7.10のフローab⁰のよ うに，分割数20,40,80の際の推定誤差0.09,0.12,0.17に対して，加重混合法を適用した推定結果は 0.18と，最良時の分割数の選択時と比較して大幅に推定誤差が低減しているフローも存在すること がわかる．これは，今回着目した集約フローの平均流量の真の値と推定値の差を最小にするような加 重平均を計算をしたことに原因があると考える．例えば，各フローにおいて誤差が大きい場合でも，

ドキュメント内 22 / ( ) OD (Origin-Destination) (ページ 32-51)