パスペースなアクティブ計測によるネットワーク負荷伝搬特性の実験的分析

fマルチメディア通信と分散処理ワークショップJ 平成15年 12月

パスペースなアクティブ計測による

ネットワーク負荷伝搬特性の実験的分析

中嶋卓雄，築地原護

九州東海大学応用情報学部 E-mail: {tak時 ktmail

，

OOiis232@stmail}.ktokai-u .ac.jp 本研究では.IPパフォーマンスを計測するパスペースなアクティプ計測を用いて，ネットワーク を伝搬する遅延およびロスの特性を実験的に分析した.この計測手法は.ICMP TIMESTAMP メッセージを送信し，そのリプライメッセージを受信することにより，パスに沿った各ノード までの双方向の特性を抽出することができる.パケットを収集し，遅延の分散とロスの発生を 分析することにより，次のような結果を得ることができた.まず第一に，中継ルータで発生し ているパースト的な遅延はパスに沿って各ノードに伝搬する.第二に，周期的な遅延はノード 固有のものであり，およそ30秒または 60秒の周期を持つ.第三に，ある一定時間間隔内に分 散するロスの発生は特定のプロパイダー内において伝搬する場合がある.

Experimen t

a

l

A

n

a

l

y

s

i

s

o

f

P

r

o

p

a

g

a

t

i

o

n

P

r

o

p

e

r

t

i

e

s

h

n

p

l

e

m

e

n

t

i

n

g

t

h

e

P

a

t

h

-

B

a

s

e

d

Measurement

Takuo

N

akashima

，

Mamoru Tsuichihara School ofInformation Science， Kyushu TokaiUniversity

In this paper

，

we will show theexperimental analysis ofnetwork load propagation properties of Internet pathsusingourIP performance activemeasurement method. This method sends ICMP TIMESTAMP messages and receives reply messages to and from each node along the path. Aftercollecting and analyzing the delay fluctuationsand loss occurrences

，

we extracted following results. First

，

burst-type delays were propagatedtoeach node throughout thepath. Second， cyclic delays were peculiar toeach node and had timeinもervalsof30or 60seconds. Finally， scattered losses occurred along paths through one of the providers.

1

はじめに

インターネットのトラフィックを理論的に解析す る時，以前ではパケット到着時間などはポアソン過 程のモデルにより説明されてきた[1].しかし，実際 のパケットの到着間隔はこのモデルとは異なってい ることが実験結果により示されてきた

[

2

]

.

近年にな り.Self-similarな特性が LANトラフィックにおいて 発見されたり [3].Self-similarで長期間依存 (Long -rangedependence)である特性が.End-tcトEndにお けるパケット到着間隔およびパケット損失について 見られることが報告されている [4]. End-to-Endの 特性を詳細に調べたい時，パス上の中継ノードのパ フォーマンスや，パスのトポロジーの構造がその特 性に大きく影響するため，パケットがパス上を流れ ている挙動の正確な観察が必要となる. このようなIPネットワークの挙動を計測・評価する 手法として.2つの計測手法，パッシブF計測(P出slve Measuremen t)とアクティブ計測 (AvtiveMeasure -ment). がある.パッシフ計測は中継ノードを通過す るIPパケットフローを観察する手法であり. IETF のIPFIX(IPFlow Information Export)WGにおい て議論されている.一方のアクティブ計測は，パケッ トをインターネットに送出し，その挙動を計測する ことによってパフォーマンスを評価する手法である. IPPM (IP Performance Metrics) W Gにおいて，ア クティブ計測に基づきIPパフォーマンスの評価手 法や指標が議論されている

[

5

]

.

パッシブ計測では， ノード上のトラフイツクを正確に観測することがで きるが，計測できる領域については特定のノードに 限定される.一方アクティブ計測では，パケットを 送出することにより.End-to-Endのパケットの流れ を観測することができ.End-to-Endのパスに基づ く情報を抽出することができる. ACM SIGCOMMによって公開されているデータ

[

6

]

は， 一般的なトラフイツクの解析およびネットワー クの特徴抽出には有益なデータである.しかし，こ のデータは詳細なパスを含むデータではないため解 析には限界が存在する. 本研究では，パケットの遅延の分散およびロスの -4

9-発生をアクティプ計測により実験的に収集すること により，ノード間の関係性，およびノードにおける 独立性などの特徴を抽出することを試みる.この実 験データはトラフィックの理論的な検証にとって基 礎的なデータとなると考えている.本研究で採用し たアクティブ計測は，パスペースの双方向性を持つ 計測手法である.IPPMではパケットの行きおよび 帰りの経路変動による誤差を取り除くため，一方向 性のパフォーマンスが議論されているが， 一方向性 を前提とするとデータの収集範囲が限定されるので 双方向性の手法を開発した.本研究で提案する双方 向性のアクティブ計測は，一方向性のデータとして も解析が可能であり，広範囲なデータを収集するこ とができ，公開されているデータと比較して詳細な データを収集することができる.またパスペースな 手法であることにより.End-to-Endの中継ノードに おける挙動を各ノードにおける遅延およびロスの現 象から詳細に検証することが可能となる.

2

パスペース計測手法

我々は.IPパケットが経路に沿って流れるパスペー スな計測手法を提案しており

[

7

]

.

本研究においても 同じ計測手法を用いる.パスペースであることによ り，パケットが流れるノード聞の隣接関係および連 続的なパケットの送信による時間的なノードでの遅 延の変化などを抽出することができる. 以下，新たな記号を導入しているので，計測パケッ トとその送信パターンについて説明する.

2

.

1

計測パケット

Source Destination Originate Timestamp (tl) ICMP Timestamp Receive TimestamI (t2) E 仕 組 mt ss ne

、 ，

a E 3 r ・1 t T T { Receive

Time . _(t4.._l11 _{工CMPTimestamp Repl}

図1ICMP TIMESTAMPパケットシーケンス 図1にICMPTIMESTAMPのパケットシーケン スを示す.まず，送信ノードにおいて ICMPTIMES-TAMPメッセージの送信元タイムスタンプ (Origi -na民Timestamp)フィールド

(

t

1

)

に現時刻を打刻し， 計測するリモートノードへメッセージを送信する.リ モートノードでは，メッセージを受信した段階でそ の時刻を受信タイムスタンプ(ReceiveTimestamp) フィールド

(

t

2

)

に打刻し.ICMP TIMESTAMP RE -PLYメッセージとして再構成する.送信する直前に 伝送タイムスタンプ (TransmitTimestamp)(t3)を 刻印し，送信ノードへメッセージを返信する.送信 ノードにおいてICMPTIMESTAMP REPLYメッ セージを受信した段階でローカル時刻

(

t

4)を求めれ ば4箇所の時刻情報を得ることができる.

2

.

2

送信パターン

図2に計測パケットの送信パターンを示す.縦軸 方向に経緯する時間を，横軸方向にパスとパス上に あるノードを示す.ほぽ同時に特定のパス上にある すべてのノードに対してパケットを送信する.一定 間隔を空けた後，同様にパケット群(以下ではグルー プと呼ぶ)を送信し，それを繰り返す.本研究では， この一連のパケット群をほぼ同時に送信しているこ とから，パケット群が一つのパケットの挙動を表し ていると考える. Path ω E H ' F NodeONode1 Node i Noden 「一一一『 Group1 ' ~ ~ l Group2 r一一一『 ' ~ Groupg 「1一一『町1 図2計測パケット送信パターン

3 評価指標

前述した送信パターンによる計測パケットを送信 することによって得られる，遅延およびロスに関す る評価指標を提案する.

3

.

1

差分

RTT

ノードtまでの RTTをRTT(i)で表した時，ノー ドiとノードト1問の差分RTT(Differential恥 und TripTime)DRTT(i

，

i -

1

)

を DRTT(i

，

i -

1

)

=

RTT(i) -RTT(i -

1

)

と表す.

3

.

2

一方向遅延

図

1

において示したように，仕様上は

4

つの異な る時刻が求まるはずであるが，実際の実装では，受 信タイムスタンプ

(

t

2

)

と伝送タイムスタンプ (

t

3

)

は 同ーとなる.以下では •

t

2

=

t

3

とし，それが内部処 理のどのタイミングで押されたのかについて，実験 結果において検討する. ここで.)11員方向の遅延をFTT(ForwardTrip Time) および逆方向の遅延をBTT(BackwardTrip Time) n U R U

と呼び，FTT

=

t2- t1および BTT

=

t4ーらと定 義する.

3

.

3

遅延分散極座標

遅延の周期性を評価するために，遅延分散極座標 を導入する.これは図3に示すように，極座標

(

r

，

B

)

5

において， rとして RTTを，

B

として計測開始からの 経過時間を取る.一周期のOの値を変えることによっ て，周期性が存在するか否かを判断する. 図3遅延分散極座標表現

4

計測実験環境

4

.

1

計測実験

プラットフオームとしてFreeBSD-4.X上に， ICMP TIMESTAMPを送信するアプリケーションを実装し た.また，送信元ノードについてはNTPを stratum lから非常に近いstratum2として動作させ(offsetを 1 [msec]以内)，絶対時刻との誤差を極力取り除いた. 計測実験は次のような手順により行った.まず，送 信元は九州東海大学内のノードに限定し， Endノー ドに関しては圏内および国際回線，および異なるプ ロバイダを利用する 61個のノードを抽出した.次 に， Endノードに対して数度に渡って tracerouetに よって経路を調べ，ほとんど変化しないと思われる 43個の経路を計測パスとして抽出した.その後，そ の計測パスを構成する各ノードに対して，前述した 計測パケットと送信パターンによりパケットを送信 しデータを収集した.また， ICMP TIMESTAMPに 応答しないノードは計測パスから削除した.具体的 には，計測パケットのサイズを40[byte]とし，送信 パターンは，まずパス上のすべてのノードへ1[msec] 以内にパケットを送信し，グループ聞の先頭パケッ トの間隔を約300[msec]とし， 2000回のグループ送 信を行った.

4

.

2

経路変動に関する仮定

経路の動的な変動により，実験段階において当初 選択した計測パスと異なる経路を通ったり，あるEnd ノードへの経路としては，計測パス上の中間ノード を通らない可能性や，計測パスの隣接関係が実際に は成立していない可能性もある.しかし，実験におい ては， ICMP TIMESTAMPが戻ったノードのみを データとしており，事前に決定したEndノードまで のノードのリストは，ほぽネットワーク的な距離を 保っているという意味で妥当な経路である仮定する.

評価

まず，表記を簡略化するため，パスに沿って順に ノードに番号をつけ，その番号をノード順番号(Node Sequence N umber) (以下ではNSNと略記)と呼ぶこ とにする.以下では，特徴が現れている特定のパス および計測時刻における結果について検討する.パ スまたはノード固有の現象か一般的な現象かについ ては，実験結果のところで検討する.

5.1

遅延の評価に利用したパスデータ

表1に示すパスのデータについて，遅延に関する 特性を検討する. 表

1

遅延の評価に利用したパスデータ NSN P address 1 202250615(02. 0225061) 2 tip (202.250.1.1) 3 4 5 6 7 8 9 10 11 12 13 2.216) 14 5.112) 15 表1のパスは，まず九州東海大学の学内のパスを 通り， SINETに入り，その熊本ノード，九州ノード を経由して東京のExcahangeポイントまで行き，そ の後， verIo.netを通る経路である.

5

.

2

遅延のパス依存性

表1に示すパスデータに基づ、き実験を行った時，パ ス上の NSN= 1から NSN= 15までの各ノード において遅延が時間的に変化する状況を示したのが 図4である. 最小遅延については ，NSN=l1のnii-gate3-P1 -O.sInet.ad刊 か ら 約 230[msec]に上昇している.特 に，NSN

=

4のノード(九州東海大学のゲートウェ イである202.250.0.253)において負荷が発生し，パー スト的に遅延が45秒ほど増加している.さらにこ の遅延の増加が後続する他のノードの遅延に影響し， 同様に増加していることがわかる. 同様に他のパスデータにおいても遅延の増加がパ スに沿って伝搬する傾向が見られた. p h u

RTI[msec] 600 200

。

111，:， ， ，:¥1 図

7

に示すように ，NSN二

1

0

と

9

聞において差 分

RTT

がある間隔毎に負の値を取っている.これ は，NSN

=

9において発生している短い間隔の遅 Gl~刊延の増加は NSN=9 のノードにおいて独立である A b JOG ，ことを示している.同様に NSN=10-9におけ

-a13654ew

伊 @ る 差 分 町Tの正の値が， NSN=11-10において 12(f-l

。

針

。

負の値となっているのも ，NSN=10においてノー ゃ.cT0 ら 河 ドに独立な遅延の増加が発生していることを示して いる. 図

4

において ，NSNニ 4以降の各ノードにおけ る遅延の増加が NSN=4のノードにおける負荷の 発生による影響か否かを判断するため，図5に，隣 接ノード聞の差分

RTT

が変化する状況を示す.こ の図から NSN=4のノードに加わった負荷はそれ 以降のパスの隣接ノード聞の

RTT

にはほとんど影 響をしていないと考えられる.したがって，特定の ノードで発生した負荷が，それ以降のノードの遅延 に影響していると考えられる.また，このような状 況は，他のパスにおいても同様に発見できた. 図5において見られる，値が負となる現象につい ては後述する. Differential RTI[msec]

∞

∞

。

∞

∞

4 2 a 4 Time[sec] 図5隣接ノード聞の差分

RTT

の変化

5

.

3

ノードに独立した遅延

図4に示した NSN

=

9，

1

0

，11の遅延を，その前 後の時間も含めて拡大すると，図6となり，パース ト的な遅延の増加以外に，短い時間間隔の遅延の増 加が多数発生している. 11 600 _"，({'"Q0¥ 10 刊，c，0'"岬 .-ら.0o..V'O' や。M 図6ノードにおける遅延 図5において考察したのと同様に，差分

RTT

に より、ノードにおける遅延の依存性の有無を考察す る.図7に，NSN=9，10，11，12聞の差分

RTT

を 示す. Differential RTT[m時c) 400 200

。

-200 -400 12-11 図7遅延の独立性

5

.

4

トリップの方向による遅延の分割

前述したパースト的な遅延の増加および短期的な 遅延の増加がメッセージの転送方向，すなわちメッ セージがトリップする方向，と関連性があるか否か について検討する. 図8に，N SN

=

9，

1

0

，11に対する

FTT

の時間 的な変化を，図9に， BTTの時間的な変化を示す. ワ ム u p h d

FTI[msec] 2000 1600 1200 800 400 。

ι

ム ← ] ム ム ム ム ム 」 600 9 図8Forward Trip Timeの変化

NSN

=

10，11において，漸近的に FTTが増加 しているのは，それらのノードにおけるローカルク ロックがドリフトしていることが原因と考えられる. また ，

NSN

=

9において，急にFTTの値が減少し ているのは，時刻同期が発生したと考えられ，時刻 同期の機構，例えばNTPクライアントなど，によ り同期が発生したと思われる. このFTTにはパースト的な遅延の増加がまったく 含まれず，短期的な遅延の増加のみが含まれている. ネットワークのノード聞に一定間隔の短期的な遅延 の増加が発生しているとは考えにくいため， ICMP がノードに到着してら=らが押される前にノード に独立な優先的な処理が動作し，その結果として， FTTの値が増加するものと考えられる. BTI[msec] 500

。

-500 -1000 -1500 -2000 Time[s配] 図9Backward Trip Timeの変化 BTTについても，同様にノードのローカルクロッ クのドリフトが影響している_BTTはFTTと異な り，パースト的な遅延の増加が影響している.この 遅延の増加がパス依存性を持つことを併せて考察す ると，スタンプが押された以降，送信元へ返送する 処理や，次のノードへ転送する処理の過程で遅延が 伝搬していると考えられる.

5

.

5

遅延の周期性

E

∞

Node Sequential Number= 10 100 11 -1

∞

-2

∞

」

:2

∞

-100

。

100 2

∞

図10 121秒周期の遅延分散極座標表現 図 6，図 7に示したように ，

NSN

ニ 10における ノードに強立な遅延を差分 RTTから取り出し，遅 延分散極座標により表現したものを図8に示す.こ こでは周期を121秒としている.ほぽ2つの方向に 分離しており，このことから約60秒の周期がこの ノードにおいて発生していることがわかる. 4

∞

走 。 。

。

-200 .400_:-: --400 -2

∞

200 400 図11 114秒周期の遅延分散極座標表現 同様に ，

NSN

= 9におけるノードに独立な遅延 を差分 RTTから取り出し，遅延分散極座標により 表現したものを図9に示す.ここでは，周期を 114 11 秒としている.ほぽ4つの方向に分離しており，こ のことから，約28秒の周期がこのノードにおいて発 生していることがわかる. 他のノードにおいても周期的な遅延が見られ，そ の周期は同様に約60秒か 30秒となった.

5

.

6

ロスの評価に利用したパスデータ

今回の実験では大部分のパスにおいてロスの発生 はまれであったが，あるパス中の連続するノードまた は特定のノードにおいてロスが発生していた.ここ では表2に示すパス中の一定の範囲で発生したロス の発生に注目する.このパスは ，

NSN

=

9までは， 表1と同様のSINETのパスを通り，さらにSINET の中間ノードを介してIIJに接続し.f伽irs

“

ts問er刊ve訂r_n肘e吋_-J の経路を通過するパスである. q u p h u

の 限定された日時，図 13では2003年6月12日， データである. 6 島唱。ぐかd'¥ _t¥.u0(

、

r 60 5 "，<ifoJ ノードに独立なロス 7 リ FF 旬 、 、 - a . ・ . -p ' ' ' " j d ・ . ‘ J J ・ -y r 1 J w -FJ'e a 丸 山 WLM l 1 2 2 H -i d ， ・ 0 . ， r ， a -u wd ・ -o i J ， e v . ‘ ， ! J o -・ . 可 ' a μ 川 崎 川 川 図13 RTT(ms配] ε1UAUE3nuza 内 U 司 ζ 内 4

・

E 4 ， ロスの評価に利用したパスデータ INSN P address I ~02.250.6.1 (202.250.6.1) 2 ~tip (202.250.1.1) 3 okai-router (202.250.0.1) 4 5 lkumamoto-1-FE1-0-0.sinet.ad.jp (150.99.45.1) 6 lkyushu-S1-GE6-1.sinet.ad叩(150.99.130.129) 7 JT-osaka-S1-P6-0.sinet.ad .jp(150.99.197.105) 8 JT-tokyo-S1-P1-0.sinet.ad .jp (150.99.197.5) 9 ιS1-P4-0.sinet.ad.jp(150.99.197.22) 10 ui-IX-PO-O.sinet.ad.jp (150.99.197.142) 11_{IstekMO03bbi-Ob1 b8IIJ Net (210mm7)} 12 IIJ.Net (202.232.0.81) 13 psk003ip05.IIJ.Net (210.138.33.25) 14

ロ

10.138.33.86(210.138.33.86) 15_区knwa+lla 128.抗rstserver.ne.jp(164.46.253.18) 16 med.jp (164.46.141.223) 表

2

おわりに

本研究では， 1msec以下という短い間隔のパケッ トをパス上に送信するアクティプ計測によって，遅 延に関しては，パス上のパースト的な遅延の伝搬の 傾向，および周期的な遅延の独立性およびその周期 などを抽出することができ，ロスに関しては，プロ パイダの特定のエリアにおいて，部分的に連続する ロスが伝搬する傾向があることなどを抽出すること ができた. 今後は，これらの現象の統計的特質，およびパス の変動と遅延およびロスとの関連性について考察し ていきたい.

6

ロスのパス依存性

図 12に

NSN

=

10以降のノードに関する， RTTおよびロスの発生を示す.この図では，ロス を

RTT=O

の値として表現しているので， RTTの 値 がOに向かっているのがロスが発生したタイミン グである.図

1

2

から ，

NSN=

l1か ら は ま で の 各ノードにおいて，ロスがほぼ同じ時間帯にに分散 しながら発生しているのがわかる .

NSN

=

15にお いては，そのロスも回復していることから，特定の 部分パスにおいてのみロスの発生が依存していると 見なすことができる.ロスの発生前後の RTTはそ のノードにとって比較的安定していると見なせるこ とから，この場合はロスと遅延との相関はほぼない ものと見なすことができる.

5

.

7

[1]Frost， V. and Melamed， B.: Tra侃cModeling for

Telecommunications Networks， IEEE

Communi-cat附 ISMagazine， 32(3)， pp.70-80， March (1994)ー

[2]Paxson， V. and Floyd， S.:Wide-Area tra侃c:the

failure of Poissonmodeling， IEEE/ACM Trans Net凹orking，Vo1.3， No.3， pp.226-244(1995). [3]Leland， W.， Taqqu， M.， Willinger， W. and Wil -son

，

D:. On the Self-SimilarNature ofEth -ernetT日 侃c (Extended Version)， IEEE/ A C M Trans.Networking， Vo1.2， No.1， pp.1-15， February (1994). [4]串田高幸，柴田義孝 End-to-Endパスにおけるパ ケット到着間隔および損失の特性解析，情報処理学 会論文誌，Vo1.44， No.3， pp.570-579(2003).

[5]Paxson， V.， Almes， G.， Mahdavi， J. and

Mathis， M.: Framework for IP Performance

Met-rics，RFC2330， May (1998) [6]The Internet Traffic Archive: http://www.acm.org/sigs/sigcomm/ITA (2002). [7]井原修一，中嶋卓雄 パスペース IPパフォーマン ス計測システムの実装と評価，情報処理学会論文誌， Vo1.44， No.2， pp.364-373(2003).

参考文献

15 性 存 依 制 収 ， ノ の

ス

ロ

肉廿1ms血l 制 制 制 抑 制 抑 制 湖 町 出 。 図12 ロスは図12に示したように，部分パス上である 程度の依存性を持ちながら発生する以外に，負荷が 集中していると思われるノードにおいて発生する場 合もある.図13の

NSN=6

のノードにおいては， その前後のノード

NSN=5

，

7

においてロスがまっ たく発生していないにもかかわらず，かなり頻繁に ロスが発生している.このことは，パケットのフォ ワーディングにおいてはロスが発生するほどの負荷 はなく，内部処理において負荷がかかりその結果が ロスの発生につながっていると思われる.ただし，こ の多発するロスは日常的に発生している訳ではなく， AUZ F h d