髦ｿ驛ｨ菫贋ｺ 縲後う繝ｳ繧ｿ繝ｼ繝阪ャ繝医ヨ繝ｩ繝輔ぅ繝け縺ｮ髟ｷ譛滉ｾ晏ｭ俶ｧ縺ｨ諤ｧ閭ｽ縺ｫ荳弱∴繧句ｽｱ髻ｿ縲

Research and Development Center for Academic Networks

インターネットトラフィックの長期依存性と

性能に与える影響

2007年11月6日

国立情報学研究所

阿部

俊二（[email protected])

2

Research and Development Center for Academic Networks

© 2007 National Institute of Informatics

発表内容

１．インターネットトラフィックの自己相似性/長期依存性

¾要因

¾学術情報ネットワーク（SINET)のトラフィックの性質

２．自己相似性/長期依存性がネットワーク性能に与える

影響

３．FBM（Fractional Brownian Motion)モデルと

MMPP（Markov Modulated Poisson Process)による性

能評価手法

Research and Development Center for Academic Networks

インターネットトラフィックの自己相似性/長期依存性

‹ＬＡＮやＷＡＮに流れるトラフィックに自己相似性/長期依存性が

あることが指摘されている（W.E. Leland, et al, “On the self-similar

Nature of Ethernet traffic,” SIGCOM’93, pp.183-193,1993)

‹近年のインターネット通信が画像や動画などのマルチメディアの

コンテンツからなるWebへのアクセスが中心的になっている。

¾Webアクセストラフィックのファイル長分布がHeavy-tailである

¾Heavy-tailなトラフィックを多重すると長期依存性を有する

¾ＭＰＥＧなど動画像に自己相似性/長期依存性があることが

分かっている

→これらマルチメディア情報がネットワークを流れることで

自己相似性や長期依存性が生じている

4

Research and Development Center for Academic Networks

© 2007 National Institute of Informatics

自己相似性/長期依存性の例

Webサーバー/ftpサーバー

ストリーミングサーバー

(MPEG動画像）

ルータ

インターネット

http/ftp

http/rtsp

スパコン

‹自己相似性：例えば、異なるサンプル時間で計測し

た時系列過程で、異なるサンプル時間でも不変な

性質

‹長期依存性：長い期間にわたり相関が持続する性質

サンプル時間＝１０ｓ

サンプル時間＝１ｓ

サンプル時間＝0.1ｓ

Research and Development Center for Academic Networks

学術情報ネットワーク（ＳＩＮＥＴ３）の構成

40Gbps回線

10Gbps以上の回線

600Ｍｂｐｓ以上の回線

コアノード

エッジノード

6

Research and Development Center for Academic Networks

© 2007 National Institute of Informatics

ＳＩＮＥＴ３のコアノードとエッジノードの拠点と、計測点

‹１２のコアノード拠点

‹６２のエッジノード拠点

‹７００を越える加入機関（エッジ拠点から接続されている）

トラフィック計測点（ＳＩＥＮＴとＪＰＩＸ東京の接続点）

（※ＪＰＩＸ東京：商用ＩＳＰとの接続点）

Research and Development Center for Academic Networks

ＪＰＩＸ→ＳＩＥＮＴの１日のトラフィック流量変化の様子

8

Research and Development Center for Academic Networks

© 2007 National Institute of Informatics

JPIX→SINETの約１時間のビットレート変化の様子

計測期間：２００４/３/０１

１４：３３

→

１５：４５

サンプル時間：１秒

Research and Development Center for Academic Networks

ＳＩＮＥＴトラフィックの長期依存性

¾ 自己相関関数：r(k)=Cov(X

_n

,X

_n+k

)/Var[X

_n

]

¾ 分散：Var[X

_n

(m)

_]=Var[S

n,m

]/m

¾ X

_n

が長期依存性を持つとき、

– r(k) ～αk

-β1

, k → ∞

– Var[X

_n

(m)

] ～

cm

-β2

, m →

∞

• α, cは定数

• HをHurstパラメタとしたとき、β

_１

=β

₂

=2(1-H)で、１より小さ

い正の定数

X

1

X

2

….

X

m

X

m+1

….

….

X

2m

τ

τ

τ

τ

τ

τ

τ

τ

S

1,m

S

2,m

‹トラヒックのサンプル過程Xn(一定時間τよるサンプル）

10

Research and Development Center for Academic Networks

© 2007 National Institute of Informatics

JPIX→SINETの自己相関特性

サンプル時間(τ): 0.1ms

Research and Development Center for Academic Networks

JPIX→SINETの時間分散特性

H=0.88

12

Research and Development Center for Academic Networks

© 2007 National Institute of Informatics

R/S解析によるハーストパラメタ(H)の推定

(

)

∑

∑

−

=

−

=

−

=

=

X

X

m

m

l

S

iX

X

i

m

l

Z

i

m

l

Z

i

m

l

Z

m

l

R

m

l

S

m

l

R

S

R

1

)

,

(

)

,

,

(

);

,

,

(

min

)

,

,

(

max

)

,

(

)

,

(

/

)

,

(

/

ただし、

‹

Ｅ

［

Ｒ

／

Ｓ

］ ～

am

H

_{となることから}

_Ｈ

_{を推定する（aは定数）}

Research and Development Center for Academic Networks

ストリーミング動画像の長期依存性

‹ストリーミング動画像（ＷＭＶの符号化、レイト：1Mbps）を0.1秒毎にサンプル

‹時間分散特性およびR/S解析からH=0.9に近いので、長期依存性のあることが

14

Research and Development Center for Academic Networks

© 2007 National Institute of Informatics

長期依存性トラフィックのネットワーク性能に与える影響

入力：Poisson

入力：SINETトラヒック（長期依存性）

：

ルータ（パケットスイッチ）

・

・

・

Ａ宛

Ａ宛

Ａ宛

Ａ宛

Ａ宛

Ｂ宛

Ａ宛の経路

Ｂ宛の経路

衝突

衝突

バッファ

バッファ

パケット

バッファで衝突回避

‹長期依存性トラフィックとポアソン入力によるバッファオーバーフロー確率P(Q>X)の比較

¾同じ入力負荷と同一のP(Q>X)の値の下で、長期依存性トラフィックは非常に大きな

バッファが必要である

Q

X=0

Ｘ

P(Q>Ｘ)

入力

Research and Development Center for Academic Networks

FBMトラヒックモデル近似を用いた応用

‹FBM(Factional Brownian Motion)Z

_H

(ｔ）

（HurstパラメタHを持つ)を用いて時刻tまで

に到着するトラヒックを近似

–

–

– 両対数グラフ上で減衰率２（１－H)の直線

）でモデル化

つのパラメタ（

　・　　

は分散係数

は到着率、

　・　

H

a

a

t

Z

a

t

t

A

_H

,

,

3

)

(

)

(

λ

λ

λ

λ

+

=

H

H

m

n

m

a

X

Var

m

2

2

)

1

(

2

2

)

(

_ただし、

]

[

σ

σ

λ

τ

τ

=

=

−

−

時間分散

離散

　間隔サンプル過程の

16

Research and Development Center for Academic Networks

© 2007 National Institute of Informatics

FBM時間分散式によるJPIX→SINETの時間分散特性近似

Research and Development Center for Academic Networks

FBMトラヒックの無限バッファキュー長のテール確率への応用

伝送路速度

：加わる負荷率、

～

が得られる。

を計算すると次の近似

として

とすると、

これを満たす時間を　

:

/

)

1

)(

1

(

)

1

(

2

1

)

(

)

(

*

)

)(

1

(

*

*

)

(

max

)

)

(

(

max

)

(

2

2

0

0

C

C

H

H

C

H

a

x

as

e

x

Q

P

x

Q

P

t

t

C

H

Hx

t

t

a

t

x

t

C

x

Ct

t

A

P

x

Q

P

H

x

H

c

t

t

λ

ρ

ρ

λ

γ

λ

λ

λ

γ

=

⎟

⎠

⎞

⎜

⎝

⎛

−

−

−

=

∞

→

>

>

=

−

−

=

⎟

⎠

⎞

⎜

⎝

⎛

−

+

Φ

=

>

−

≥

>

−

≥

≥

‹バッファキュー長のテール確率（バッファオーバーフロー確率）: P(Q>x)

18

Research and Development Center for Academic Networks

© 2007 National Institute of Informatics

マルチFBMパラメタによるテール確率近似

)

,

,

(

),....,

,

,

(

λ

a

₁

H

₁

λ

a

_n

H

_n

3

≤

n

n

P

P ,...,

₁

•FBMパラメタセット：

・・・実用的には

•テール確率の近似手法

-バッファの稼動時間を用いて入力負荷に対応した

FBMパラメタを決める方法

-時間スケールt*を用いる方法

-最大確率近似法

•最大確率近似法

- 各FBMパラメタによるテール確率：

)

,...,

,

max(

)

(

Q

x

P

₁

P

₂

P

_n

P

>

≈

Research and Development Center for Academic Networks

バッファキュー長のテール確率近似（最大確率近似）

‹個々のＦＢＭパラメタを用いた

バッファキュー長テール確率と

シミュレーションの比較

‹最大確率を用いた近似と

シミュレーション比較

20

Research and Development Center for Academic Networks

© 2007 National Institute of Informatics

MMPP（Markov Modulated

Poisson Process）による近似

‹FBMトラヒック近似はガウス分布を基本にしている

¾(0,t]に到着するトラヒックを、時間tが小さいとガウ

ス分布として旨く近似できない可能性が高い。すな

わち、時間が小さいとパケットの到着数が少ない。ま

た、入力負荷が小さい場合も同様に到着パケット数

が少ないのでFBMトラヒックモデルが適用できない

可能性がある。

‹MMPPトラヒック近似を時間の小さな領域に適用する

Research and Development Center for Academic Networks

MMPP モデル(2位相)

t

位相1

位相2

位相１

位相２

λ

₁

λ

₂

λ

₁

λ

₂

r

₁

-1

_r

2

-1

r

1

-1

r

2

-1

¾位相１のパケット発生レイト: λ

₁

（ポアソン分布）

¾位相１の平均長: r

₁

-1

_{（指数分布）}

¾位相２のパケット発生レイト: λ

₂

（ポアソン分布）

¾位相２の平均長:r

₂

-1

_{（指数分布）}

‹２位相のMMPP は４つのパラメタが必要

22

Research and Development Center for Academic Networks

© 2007 National Institute of Informatics

MMPPによるモデル化

・MMPPで近似するためには最小４つのパラメタが必要：

_1,

_2,

r

_1,

r

₂

r

₁

D

D

1

_p

E

,

r

2

D

D

1

_p

E

₁

_p

F

1

_p

E ,

₂

_p

F

F

1

_p

E

　　ただし、

D

I '

0

I

1

,

E

I '

0

F

2

,

F

I '

0

S

3

I

2

3

I

1

2

すなわち、

_p

, I '

0

, I

, S

を決めればよい

_p

:パケット到着率

I '

0

lim

_t

₀

I t , I

lim

_t

I t

;

I t

:分散指数

S

lim

_t

S t

;

S t

:歪度指数

Research and Development Center for Academic Networks

パラメタの決定方法

_p

:実測定からパケット到着率を算出する

他は、サンプル時間 毎の到着パケット数の

時間分散

Var X

_n

m

と３次中心積率

T X

_n

m

から算出する。

Var X

_n

m

p

I m

m

,

T X

n

m

p

S m

m

2

I t

I

I

1

2

2

I '

0

t

1

e

2

I '

0

t

i

1

S t

S

S

3

I

2

e

2

I '

0

t

I

1

I

2

S

3

I

1

2

I '

0

t

1

e

2

I '

0

t

I

1

24

Research and Development Center for Academic Networks

© 2007 National Institute of Informatics

小時間領域のMMPPよる時間分散近似

３ ７

Research and Development Center for Academic Networks

３次中心積率：T[X_n^(m)]

７

26

Research and Development Center for Academic Networks

© 2007 National Institute of Informatics

MMPP/G/1による平均待ち時間（W)

W

1

W

1

2

W

2

W

₁

A

1,2

2 1

r

₁

r

₂

2

,

W

2

A

2,1

2 1

r

₁

r

₂

2

A j , k

h

2

r

_k

r

₁

₂

r

₂

₁

1

2

r

_j

P

₀

_j

r

_k

P

₀

_k

2

h h

_k

r

_j

P

₀

_j

_k

r

_k

P

₀

_k

_j

r

_k

P

₀

_k

₁

₂

2

r

_j

P

₀

_j

_k

P

₀₁

w z

R

1

z

r

2

1

2

1

1

z

,

P

₀₂

w z

R

2

z

r

1

1

1

2

1

z

ただし、

R

_j

z

_j

1

z

r

_j

として、

w z

R

1

z

R

2

z

R

1

z

R

2

z

2

4

R

₁

z R

₂

z

r

₁

r

₂

0.5

2

　さらに、サービス時間分布のLST（ラプラス・スチュルチェス変換）を

s

とすると、

z

0

z

1 は次の関数のゼロ点から求まる。

F z

w z

z

Research and Development Center for Academic Networks

MMPP/M/1による平均待ち時間近似

‹ＭＭＰＰによる近似は、入力負荷が小さい領域に関して、実際より大きめになるが、

ポアソン入力よりも良い近似であることが分かる

28

Research and Development Center for Academic Networks

© 2007 National Institute of Informatics

まとめ

‹インターネットの長期依存性をSINETの実計測トラフィック

から示した

‹長期依存性トラフィックのネットワーク性能の影響をバッファオー

バーフロー確率から示した

‹バッファオーバーフロー確率の評価に関して、時間スケールの大き

な領域（負荷の大きな領域）において、マルチFBMパラメタを用いた

バッファキュー長のテール確率近似の一手法を示した（ビット数ベー

ス）

‹小時間スケール領域（負荷の小さな領域）において、MMPPモデルよ

る平均待ち時間近似の方法も示した（パケット数ベース）