社団法人 電子情報通信学会
THE INSTITUTE OF ELECTRONICS,INFORMATION AND COMMUNICATION ENGINEERS

信学技報
TECHNICAL REPORT OF IEICE.

遅延および帯域情報を用いたオーバレイルーティングの有効性評価
平岡佑一朗†

長谷川剛††

村田正幸†† 大阪大学大学院情報科学研究科〒 565–0871 吹田市山田丘 1–5†† 大阪大学サイバーメディアセンター 〒 560–0043 豊中市待兼山町 1–32
E-mail: †{y-hiraok, murata}@ist.osaka-u.ac.jp, ††hasegawa@cmc.osaka-u.ac.jp
あらまし オーバレイルーティングは，オーバレイネットワーク技術を用いてオーバレイノード間の遅延時間やパケット廃棄率などを指標として行うアプリケーションレベルのルーティングであり，エンドホストが享受する性能が向上することが知られている．その性能について，遅延時間を指標とした場合の評価は数多く行われているが，帯域情報の計測結果を指標とした評価はこれまで行われていない．本稿では，PlanetLab に参加するノード間のパスの遅延時間および利用可能帯域の計測データを用いて，オーバレイルーティングによりデータ転送する際に使用するパスの性能が，遅延時間および利用可能帯域の面でどの程度性能が向上するのかを評価する．また評価結果を基に，オーバレイルーティングがユーザ性能にとって逆効果になる問題，およびネットワークただ乗り問題について言及する．
キーワード

オーバレイネットワーク，オーバレイルーティング，IP ルーティング，PlanetLab

Eﬀectiveness of overlay routing based ondelay and bandwidth information
Yuichiro HIRAOKA† , Go HASEGAWA†† , and Masayuki MURATA†† Graduate School of Information Science and Technology, Osaka University Yamadaoka 1–5, Suita-shi, Osaka 565–0871 Japan†† Cybermedia Center, Osaka University Machikaneyama 1–32, Toyonaka-shi, Osaka 560–0043 Japan
E-mail: †{y-hiraok, murata}@ist.osaka-u.ac.jp, ††hasegawa@cmc.osaka-u.ac.jp
Abstract Recent researches on overlay networks have revealed that user-perceived network performance such as
end-to-end delay could be improved by overlay routing mechanism, since the traditional IP routing is not always
conﬁgured according to the user-perceived performance metrics. However, those studies only focus on end-to-end
delay, and the bandwidth-related information such as available bandwidth and physical capacity is not considered.
In this report, we use the measurement results of delay and available bandwidth of network paths between PlanetLab
nodes and investigate the eﬀect of overlay routing. We further reveal the relationships between delay and available
bandwidth of the network paths. Finally we discuss two kinds of problems caused by the increase of the amount ofoverlay-routed traﬃc.
Key words Overlay networks, Overlay routing, IP routing, PlanetLab

1. は じ め に
近年のインターネットの発展，ユーザ数の増加にともない，さまざまなサービスやアプリケーションが登場している．それらの中には，下位層ネットワークである IP ネットワーク上に独自の論理ネットワークを構築する，サービスオーバレイネットワークと呼ばれるものがある．例えば P2P ネットワー
ク，Grid ネットワーク，IP-VPN サービスなどが挙げられる．
これらのアプリケーションは，ある特定のサービスを前提として論理ネットワークを構築し，それぞれのアプリケーションのポリシーにしたがってトラヒックの制御を行う．例えば，P2Pのファイル交換ネットワークは，コンテンツの所在場所に応じてダウンロードホストや中継ホストを選択する．またその際に，エンドホスト間の TCP スループットや遅延時間，IP ネットワークレベルあるいはオーバレイネットワークレベルのホップ数などのネットワーク性能を指標として，トラヒック制御を行うものも存在する．例えば Akamai [1] などのコンテンツ配信サービスは，データセンタを世界各地に設置し，コンテンツの移動やコピーなどを行う際に，どのデータセンタ間でデータ転送を行えば効率が良いかを判断している．
さらに，特定のアプリケーションを前提とせず，トラヒックのルーティングそのものを目的とするオーバレイネットワークも登場しつつある．例えば Resilient Overlay Network (RON) [2]では，参加ノード間の伝送遅延時間やパケット廃棄率などを計測し，あるノード間のデータ転送を直接行うのか，他のオーバレイノードを経由して行うのかを判断している．これにより，IP ネットワークでのルーティングと比較して効率の良いデータ転送を実現し，また IP ネットワークの障害をすばやく検知し，迂回パスを選択することが可能である．本稿では，このようなオーバレイネットワーク上で行われるトラヒックのルーティン
グをオーバレイルーティング，また従来の IP レイヤにおけるパケットルーティングを IP ルーティングと呼ぶ．
オーバレイルーティングを行うことによって，通常の IP ルー
ティングに比べて，利用するユーザにとってのネットワーク性能 (スループットや転送遅延時間など) が改善することが明らかとなっている．これは，従来行われている ISP による IP ルー
ティングが，ネットワーク性能やユーザ (アプリケーション) の感じる性能を考慮して行われていないことに起因している．IP
ルーティングにおいて考慮されているネットワーク性能はホップ数が主であり，ルータ間リンク，あるいはエンドホスト間パスの利用可能帯域などを指標としたルーティングは通常行われていない．
また，ISP が行う IP ルーティングは，そのほとんどが上位
ISP とのトランジットリンクの課金体系や，パブリックピアリングやプライベートピアリングを行っている他 ISP との契約関係などの経済的および政治的理由によって決定される．そのため結果として行われる IP ルーティングが，ネットワーク性能やユーザの感じる性能の最適化には必ずしも繋がらない．すなわち，オーバレイルーティングと IP ルーティングではルーティングに用いるポリシーが大きく異なることが，オーバレイルーティングがユーザにとっての有効性を示す要因である．
オーバレイルーティングの有効性に関する評価は [3–9] などで行われており，例えば [6] では国内の地理的に離れた ISP 間でデータ転送を行う場合に，ノード間で直接転送するのではな
く，他のノードを 1 つ経由させる迂回経路を用いることで，遅延時間について全体の 28 ％のパスで中継ノードの存在しない直接パスに比べて遅延時間が改善することが示されている．これらの検討はオーバレイノード間の遅延時間に関する情報のみを用いてオーバレイルーティングを行った場合を想定している．しかし，ファイル交換ネットワークなどのオーバレイネッ
トワークにおいては，転送されるデータサイズが大きいため，ノード間の遅延時間だけでなく帯域に関する情報 (利用可能帯域や物理帯域など) が重要となる．しかし，帯域情報の計測結果を用いてオーバレイルーティングを行った場合の検討はこれまでほとんど行われていない．
そこで本稿では，Scalable Sensing Service [10] (以下 S-cubeと表記する) で公開されている，PlanetLab [11] に参加するノード間パスの遅延時間および利用可能帯域に関する計測結果を用いて，オーバレイルーティングの有効性に関する検討を行う．
あわせて，オーバレイルーティングを行う際に用いるオーバレイパスに関して，利用可能帯域と遅延時間との間の相関関係についても考察する．さらに，オーバレイルーティングを用いて運ばれるトラヒックが増加した場合に，各ノードが得たパス性能の情報にもとづいて最適と判断したパスを使用するよりも，直接パスを選択したほうがデータ転送性能が向上する場合が存在すること，また，オーバレイルーティングを行うことで IPルーティングを司る Internet Service Provider (以下 ISP と表記する) のコスト構造を無視したトラヒックが発生する，ネッ
トワークただ乗り問題 [4] についても言及する．
以下，2 章では S-cube のデータを用いたオーバレイルーティングの有効性に関する評価結果を示す．3 章では，オーバレイルーティングの問題点について言及する．最後に 4 章で本稿のまとめと今後の課題について述べる．

めに，S-cube において公開されている，PlanetLab のノード間のネットワーク性能の計測結果を利用する．S-cube においては，PlanetLab ノード間の物理帯域，利用可能帯域，遅延時間，およびパケット廃棄率がおよそ 4 時間おきに計測され，その結果が公開されている．本稿では，2006 年 10 月 25 日に計測・公開されていたデータを利用し，オーバレイルーティングの有効性の評価を行う．すなわち，PlanetLab に参加するノードがオーバレイルーティングを行うためのオーバレイネットワークを構築すると仮定し，ノード間の遅延時間および利用可能帯域の計測結果を用いてオーバレイルーティングを行った時の性能を推測する．性能評価に関しては，あるノード間にデータ転送要求が発生した際のデータ転送経路として，(1) ノード間で直接転送する (直接パス)，(2) 1 つのノードを中継させて転送する (2 ホップ迂回パス)，および (3) 2 つのノードを中継させて転送する (3 ホップ迂回パス) の 3 つの場合を比較する．
本稿において用いたデータに含まれる PlanetLab のノード数は 588 だが，PlanetLab の参加機関には，2 つ以上のノードを同一ネットワークに接続しているものが存在する．同一ネットワーク内のノード間の遅延時間や利用可能帯域の計測結果は，他に比べて非常に小さな遅延時間および非常に大きな利用可能帯域を持つことが多く，その計測誤差も大きいと考えられる．さらに，オーバレイルーティングを行う場合に，同一ネットワーク内で中継を行うことは，ユーザが感じるネットワーク性能の向上のためには無意味である．
そこで本稿では，PlanetLab のノードを所属している AS ごとにグルーピングし，各 AS に 1 つずつオーバレイノードが存在する場合を想定した評価を行う．PlanetLab のノードが所属する AS 番号は，traceroute.org [12] の所有するルートサーバにログインし，ノードへ traceroute を実行することによって取得した．その結果，ノード数 (AS 数に相当) は 179 に減少した．グルーピングの結果，AS 内に複数の PlanetLab ノードが存在し，ノード間の計測データが複数存在する場合には，それらの平均値をノード間の計測結果として用いる．このデータに対して，直接パス，2 ホップ迂回パス，3 ホップ迂回パスの性能比較を行う．その際，迂回パスの遅延時間は迂回パスを構成するノード間パスの遅延時間の和を用いる．また利用可能帯域に関しては，迂回パスを構成するノード間パスの利用可能帯域の最小値を用いる．すなわち，オーバレイノード数を M ，ノード Ni とノード Nj (1 <= i, j <= M ) の間の遅延時間と利用可能帯域の計測値を δij および βij とすると，ノード Ni ，Nj 間の直接パス，2 ホップ迂回パス，3 ホップ迂回パスの遅延時間および利用可能帯域はそれぞれ式 (1)-(6) のようになる．
1Dij= δij

(1)

2
Dikj
= δik + δkj(2)

3Diklj
1Bij
2Bikj3Biklj= δik + δkl + δlj

(3)

= βij

(4)

= min(βik ，βkj )(5)= min(βik ，βkl ，βlj )(6)

ただし，2 ホップ迂回パスの迂回ノードを Nk ，3 ホップ迂回| l，パスの迂回ノードを Nk ，Nl とする (1 <= M ，k == k, l <k, l =| i, j)．
また，遅延時間および利用可能帯域に関して最適となる 2ホップ迂回パスおよび 3 ホップ迂回パスをそれぞれ最適 2 ホップ迂回パスおよび最適 3 ホップ迂回パスと呼ぶ．それらの遅延時間および利用可能帯域はそれぞれ式 (7)-(10) のようになる．

2. オーバレイルーティングの有効性評価
2. 1 計測データおよび計測指標
本章では，オーバレイルーティングの有効性の評価を行うた

22Dij= min (Dikj)

(7)

3Dij
=(8)

k=i,j|mink=l| ，k,l=i,j|3(Diklj)

best 2hop Available BW (Kbps)

Available BW (Kbps)

1e+06
10000010000
1000

2hop Avail-BW
3hop Avail-BW
direct Avail-BW

100

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1

ratio of node pair(a) 利用可能帯域

1e+06
10000
1000
100
101100000
10000
1000
1000 10000 100000 1e+06

direct Available BW (Kbps)

best 3hop Available BW (Kbps)

1000

100

2hop latency
3hop latency
direct latency

10 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1

ratio of node pair(b) 遅延時間

図 1 直接パスおよび迂回パスの品質分布
2Bij

2= max (Bikj)
k=i,j|

3Bij=max

k=l| ，k,l=i,j|3(Biklj)

10000
1000
100
10
1100000
10000
1000
1000 10000 100000 1e+06

direct Available BW (Kbps)(b) 最適 3 ホップパス(9)

図 2 直接パスと最適迂回パスの比較 (空き帯域)(10)

さらに，最適迂回パスの直接パスに対する遅延時間および利用可能帯域の改善度をそれぞれ式 (11)-(14) のように定義する．

2I(Dij) =

1Dij
2Dij

(11)

3I(Dij) =

1Dij
3Dij

(12)

2I(Bij) =2Bij
1Bij(13)3I(Bij) =

3Bij
1Bij

best 2hop latency (msec)101e+0610000
10000
1000
1001011000
100101110100 1000 10000

direct latency (msec)(a) 最適 2 ホップパス(14)

改善度の値が 1 より大きいときに最適迂回パスが直接パスよりも性能のよいパスと言うことができる．
2. 2 遅延時間および利用可能帯域の分布
図 1 は，直接パスおよび迂回パスの遅延時間および利用可能帯域の分布を示したものである．図から，直接パスの利用可能帯域は全体の約 80 ％が 10 Mbps から 100 Mbps の間に存在するが，迂回パスを利用することでその割合が約 90 ％に増加することがわかる．遅延時間については，直接パスの約半数が 10 ms から 100 ms の間に存在するが，迂回パスを利用することでその割合が約 80 ％に増加する．また，迂回パスによる性能向上は，直接パスの性能が悪い場合に顕著であり，利用可能帯域が 100 Mbps 以上，あるいは遅延時間が 20 ms 以下といった，性能の良い直接パスに関しては，迂回パスを利用しても性能はほとんど向上しないことがわかる．これらのことから，オーバレイルーティングによって迂回パスを用いることで，特に品質の悪い直接パスに対して，遅延時間や利用可能帯域の面で性能がよい迂回パスを発見することができる可能性があることがわかる．

best 3hop latency (msec)

latency (msec)(a) 最適 2 ホップパス

10000
10000
1000
1001011000
100101110100 1000 10000

direct latency (msec)(b) 最適 3 ホップパス

図 3 直接パスと最適迂回パスの比較 (遅延)2. 3 迂回パスの性能
図 2 は各ノードペアの利用可能帯域について，直接パスに対する最適 2 ホップ迂回パスの改善度，および直接パスに対する最適 3 ホップ迂回パスの改善度の関係の頻度分布を示したものである．図 3 は遅延時間について，同様の関係を示したもので

1010.1
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1

ratio of node pair(a) 利用可能帯域

latency ratio

100

2hop/direct
3hop/direct
3hop/2hop

1010.1
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1

ratio of node pair(b) 遅延時間

図4

latency ratio (2hop/direct)

2hop/direct
3hop/direct
3hop/2hop

1000
100
101

10.1
0.1

110(a) 2 ホップ迂回パス

10
1000
100
101

10.1
0.1

110

best Available BW ratio (3hop/direct)(b) 3 ホップ迂回パス

改善度の分布図5ある．直接パスと最適 2 ホップ迂回パスを比較した場合，利用可能帯域で 96.6 ％，遅延時間で 87.5 ％ の割合のノードペアに関して最適 2 ホップ迂回パスが有効となる．直接パスと最適 3ホップ迂回パスを比較した場合，利用可能帯域で 97.7 ％，遅延時間で 85.4 ％ の割合のノードペアに関して最適 3 ホップ迂回パスが有効となる．
さらに，利用可能帯域について，2 ホップ迂回パスで改善が見られなかったパスのうち 46.9 ％ のパスにおいて，直接パスより有効となる 3 ホップ迂回パスが存在する．また，2 ホップ迂回パスで改善の見られたパスについても，51.6 ％ のパスにおいてさらに有効な 3 ホップ迂回パスが存在する．遅延時間については，2 ホップ迂回パスで改善が見られなかったパスのうち 17.8 ％ のパスにおいて，直接パスより有効となる 3 ホップ迂回パスが存在し，2 ホップ迂回パスで改善の見られたパスについても，47.3 ％ のパスにおいてさらに有効な 3 ホップ迂回パスが存在する．
図 4 は，各ノードペアの利用可能帯域および遅延時間について，直接パスに対する最適 2 ホップ迂回パスの改善度，直接パスに対する最適 3 ホップ迂回パスの改善度，および最適 2 ホップ迂回パスに対する最適 3 ホップ迂回パスの改善度の関係を示したグラフである．図 4 (a) から，直接パスに対する最適 2ホップ迂回パス，および最適 3 ホップ迂回パスの利用可能帯域の改善度はそのほとんどが 1 以上であることがわかる．一方，最適 2 ホップ迂回パスに対する最適 3 ホップ迂回パスの改善度は大半が 1 に近い．また図 4 (b) から，遅延時間に関しても，改善度が全体的にやや小さいが，同様の傾向を確認することができる．
これらの結果から，3 ホップ迂回パスを考慮することによって，より良いデータ転送パスが発見できる場合があるものの，その改善度は小さいことがわかる．これは，データ転送パスとして 1 本のパスを用いる場合には，2 ホップ迂回パスを対象とすれば十分であるということを意味している．しかし，データ転送を複数のパスを用いて行うマルチパス転送を行う場合には，3 ホップ迂回パスを対象とすることで性能が向上することが期待される．これにはパスの独立性が大きく影響すると考えられ10

best Available BW ratio (2hop/direct)
latency ratio (3hop/direct)

Available BW ratio100

利用可能帯域と遅延時間の改善度の関係 (1)るが，詳しい検討は今度の課題としたい．また，迂回パスを用いたオーバレイルーティングの効果は，利用可能帯域の改善度に比べて，遅延時間の改善度がやや小さいことがわかる．これは，IP ルーティングが IP レベルあるいは AS レベルのホップ数を基準としたルーティングを行い，よりホップ数の少ないパスを選択する傾向を持つため，ホップ数と相関関係を持つと考えられる遅延時間は，ある程度最適化されているからであると考えられる．
2. 4 利用可能帯域と遅延時間の関係
次に，迂回パスの利用可能帯域と遅延時間の直接パスに対する改善度の相関関係を調べることにより，利用可能帯域の大きい迂回パスが，遅延時間に関しても性能が良いか否かを明らかにする．図 5 は，各ノードペアについて，直接パスに対する最適迂回パスの利用可能帯域の改善度と，利用可能帯域に関する最適迂回パスが持つ遅延時間の，直接パスに対する改善度の関係の分布を示したものである．これらの図からは，利用可能帯域の改善度に対する遅延時間の改善度にはばらつきがあり，明確な相関関係は確認できない．
図 6 は，図 5 のデータを利用可能帯域の改善度の区間ごとに分割し，各区間ごとに遅延時間の改善度の平均値および 95 ％の信頼区間を示したものである．利用可能帯域の改善度が 0.1 以下の範囲では，遅延時間の平均値は悪化しており，改善度の信頼区間もそのほとんどが 1.0 以下に収まっている．このことから，迂回パスの利用可能帯域が直接パスに対して著しく小さい場合には，遅延時間も同様に悪化することがわかる．利用可能帯域の改善度が 0.1 以上 1 以下の範囲では，遅延時間の改善度の平均は向上しているが，信頼区間の幅が広いことから，迂回パスの遅延時間の改善度にばらつきが大きいことが分かる．一方，利用可能帯域の改善度が 1 以上の範囲では，遅延時間の改善度がほぼ直線的に低下していることから，迂回パスの利用可能帯域の改善度が良くなるにつれて，その迂回パス遅延時間は悪化する傾向をもつことがわかる．すなわち，利用可能帯域のより大きい迂回パスを利用すると，その遅延時間は一般に大きくなると言える．

average of latency ratio (2hop/direct)

表 1 例 1，2 のルーティング結果
例1
最適パス
直接パス
A→C
A-B-C50, 100 A-C 30, 30
B→C
B-C50, 50
B-C 100, 100
B→D
B-A-D
100, 200 B-D 40, 40
平均スループット
66.7
56.7
使用ネットワーク資源350
170
例2最適パス
直接パス
A→C
A-B-C
50, 100 A-C 60, 60
B→C
B-C
50, 50B-C 100, 100
B→D
B-A-C-D 60, 180 B-D 40, 40
平均スループット
53.3
66.7
使用ネットワーク資源
330
200

10

10.1
latency avg
confidence interval

0.01
0.01

0.1

1

10100

best available BW ratio (2hop/direct)

average of latency ratio (3hop/direct)(a) 2 ホップ迂回パス

101

0.1
latency avg
confidence interval

0.01
0.01

0.1

110100best available BW ratio (3hop/direct)(b) 3 ホップ迂回パス

図6

利用可能帯域と遅延時間の改善度の関係 (2)
100

A

B

100

AB

30 10010060 100
10010040
D60(a) 例 140C60DC(b) 例 2

図 7 ネットワークモデル

3. オーバレイルーティングの問題点
本章では，オーバレイルーティングを行った際に発生すると考えられる問題について言及する．3. 1 節ではオーバレイルーティングを行うユーザやアプリケーションが増えた場合の問題について，3. 2 節ではオーバレイルーティングを行うことで IPルーティングを司る Internet Service Provider (ISP) のコスト構造を無視したトラヒックが発生するネットワークただ乗り問題について述べる．
3. 1 オーバレイネットワークパスの選択に関する問題
2 章における評価結果，および [3–9] における検討などから，オーバレイルーティングによってユーザの感じる性能は大きく向上することがわかる．したがって，オーバレイルーティングが普及することにより，オーバレイルーティングによって運ばれるトラヒック量が今後増大することが考えられる．オーバレ
イルーティングにおいては，各ユーザはオーバレイルーティン
グによって取得した各ノード間パスの遅延時間や利用可能帯域などに関する情報を用いて，最適なパスを独自に選択して通信を行う．しかし，各ノードにとって遅延時間や利用可能帯域が最適となるパスが迂回パスである場合においても，各ノードがその迂回パスを選ぶよりも，単純に直接パスを選んだ方が，オーバレイネットワーク全体の性能，および各ノードにとっての性能の両面で有効となる場合がある．
その典型的な例を図 7 を用いて説明する．図 7 において，リンク上の数値はその方向の利用可能帯域を表し，数値のない部分は利用可能帯域が十分小さいものとする．A → C，B → C，
B → D に転送が発生し，各転送は用いる各リンクの利用可能帯域を通過するフローで公平に分配して利用すると仮定する．
また，各転送の送信ノードはネットワークの利用可能帯域の情報を完全に把握しており，利用可能帯域が最も大きくなるパスを最適パスと考えて利用するものとする．表 1 は，これらの場合において，最適パスを利用する場合，および全ての転送において直接パスを利用する場合における，各転送が得ることのできるスループットと，利用するネットワーク資源量をまとめたものである．ここでネットワーク資源量とは，全てのノード間リンクの遅延時間を 1 としたときの，各転送のスループットと遅延時間の積を意味する．各項目のノード列は，それぞれ選択した転送経路を表し，2 つの数値は，各転送のスループットと使用しているネットワーク資源量を表す．
例 1 のネットワーク状況においては，最適パスを用いることによって，平均スループットが直接パスを用いる場合に比べて向上している．しかし，使用しているネットワーク資源量は直接パスを用いる場合の 2 倍以上になっている．これは，利用可能帯域が大きく，かつホップ数の多い経路を用いたためである．
一方，例 2 のネットワーク状況の場合，各ノードが最適と判断したパスを用いることで，平均スループットが直接パスを用いる場合に比べて小さくなっていることがわかる．また，使用しているネットワーク資源も直接パスを用いる場合に比べて大きくなっている．これは，ホップ数の多い経路を選択することによって，より多くの帯域資源を利用し，他の転送のスループット低下を引き起こしているためである．
2 章における検討では，オーバレイネットワークによって運ばれるトラヒック量を考慮していないため，オーバレイネットワークを用いたあるデータ転送が，他の転送に与える影響 (利用可能帯域の減少や遅延時間の増大など) を無視した評価になっている．そのため，オーバレイルーティングの有効性を過大に評価していると言うことができる．より正当な評価を行うためには，本節で示したようなトラヒック量を考慮した評価が必要であると考えられる．
3. 2 ネットワークただ乗り問題
Internet Service Provider (ISP) は対外接続のためのリンクとして，上位 ISP との接続であるトランジットリンク，および他 ISP とピアリング関係を結ぶためのピアリングリンクを持つ．トランジットリンクは通常，通過するトラヒック量の最大値によって金銭的コストが決定される．一方ピアリングリンク
は，共有する ISP で回線維持コストを折半する点以外にはほとんどコストが発生しないが，接続した両 ISP 内に所属するホストを通信の起点および終点とするトラヒックのみ通過させるのが一般的である．ISP の行う IP ルーティングは，これら対外問題となると考えられる．

Overlay
NetworkNj

Direct-path

4. ま と め

Ni
Relay-path(2hop-path)

Nk

Transit Link: Cij

ISP I
Peering Link: Cik

ISP J

ISP K

Transit Link: Ckj

IP Network

図 8 ネットワークただ乗り問題

リンクのコスト構造や制約を考慮して決定される．
しかし，オーバレイルーティングが行われると，ISP の考えるコスト構造を無視したトラヒックが流れる．図 8 を用いてその典型的な例を示す．図 8 においては， ISP J を上位 ISP とし，ISP I，K はそれぞれ ISP J との間にトランジットリンクを持つ．また，ISP I，K の間にはピアリングリンクが張られている．また，ノード Ni ，Nj ，Nk は，それぞれ ISP I，J，Kに所属するノードであり，リンク Cij ，Ckj は，それぞれ ISP
I と J の間， ISP K と J の間のトランジットリンク，リンク
Cik は， ISP I と K の間のピアリングリンクである．
このとき，ノード Ni ，Nj 間でデータ転送要求があったとする．IP ルーティングで経路を決定した場合，トラヒックはノード Ni から Cij を通って，ノード Nj へ届けられる．オーバレ
イルーティングを用いた場合においても，直接パスの方が有効である場合には他のオーバレイノードを経由しないため， IPルーティングの場合と同様の経路を通る．この場合，送信ノード Ni が所属する ISP I が上位 ISP である ISP J と契約しているトランジットリンク Cij を使い，その利用料金を ISP J に対して払う．これは一般的な課金構造であり，ISP I はノード
Ni のユーザから利用料金を徴収することでトランジットコストを回収することができる．
一方，ノード Nk を経由する 2 ホップ迂回パスを利用する場合には問題が発生する．この場合，トラヒックはまず ISP I とISP K 間のピアリングリンク Cik を通ってノード Nk へ一度届けられ，その後， ISP K と ISP J 間のトランジットリンク
Ckj を通って，ノード Nj へ届けられる．したがって，このトラヒックに対するトランジットコストは，Ckj を契約しているISP K が負担することになる．この場合，ISP K は，実際のトラヒックの送受信者である Ni ，Nj のユーザからコストを回収することはできない．この問題を我々はオーバレイルーティン
グによるネットワークただ乗り問題と呼んでいる [4]．
ISP 間のリンクを通過するトラヒックが，ただ乗りトラヒックであるか否かの判断が出来る場合には，ただ乗りトラヒックに対して制限をかける，あるいは別途課金する，などの方法によってこの問題は解決することができる．しかし，ただ乗りトラヒックはアプリケーションレベルのオーバレイネットワークによって運ばれるため，通過するパケットの送信先および送信元アドレスを監視することでは，ただ乗りトラヒックと通常のISP 間トラヒックとを区別することができない．
ISP が自身の課金構造を基に行っている IP ルーティングを無視したトラヒックが発生するこの問題は，オーバレイルーティングが普及しそのトラヒックが増加すると ISP にとって深刻な

本稿では，PlanetLab のノード間の計測データを用いて，遅延時間および利用可能帯域を指標としてオーバレイルーティングを行うことの効果に関する検討を行った．その結果，利用可能帯域を指標としてルーティングを行うことの効果が大きいこと，利用可能帯域が大きくなる迂回パスの遅延時間は悪化する傾向にあること，また 3 ホップ迂回パスは 2 ホップ迂回パスに比べてその改善度は大きくないことなどが明らかとなった．
今後の課題としては，2.3 節で示した，マルチパス転送を考慮した場合のオーバレイルーティングの効果を検証することがあげられる．また，3 章で示したオーバレイルーティングの 2つの問題に対する解決策として，ユーザ性能が向上し，かつただ乗りトラヒック量が小さくなるような，新たな指標に基づくオーバレイルーティング手法を提案したい．

謝辞

本研究の一部は，総務省戦略的情報通信研究開発推進制度委
託研究「ネットワークサービスの早期展開を実現するオーバレイネットワーク基盤の研究開発」，および平成 19 年度文部科
学省科学研究費基盤研究 (C) 「インラインネットワーク計測技術に基づく新たなトランスポートサービスの創出」によっている．ここに記して謝意を表す．
文献[1] Akamai Home Page. available at http://www.akamai.com/.
[2] D. G. Andersen, H. Balakrishnan, M. F. Kaashoek, andR. Morris, “Resilient overlay networks,” in Proceedings of18th ACM Symposium on Operating Systems Principles,Oct. 2001.
[3] C. L. T. Man, G. Hasegawa, and M. Murata, “Inferring
bandwidth of overlay network paths using inline networkmeasurement,” 電子情報通信学会技術研究報告 (IN2006-217),
Mar. 2007.
[4] 長谷川剛, 小林正好, 村田正幸, 村瀬勉, “オーバレイルーティン
グに起因するネットワークただ乗り問題に関する一検討,” 電子
情報通信学会技術研究報告 (IN2006-136), Dec. 2006.
[5] M. Uchida, S. Kamei, and R. Kawahara, “Performance evaluation of QoS-aware routing in overlay network,” in Proceedings of ICOIN 2006, Jan. 2006.
[6] S. Kamei, “Applicability of overlay routing in Japan using
inter-domain measurement data,” Overlay Network Workshop, Dec. 2006.
[7] Y.Zhu, C. Dovrolis, and M. Ammar, “Dynamic overlay routing based on available bandwidth estimation: A simulation
study,” Computer Networks Journal, vol. 50, pp. 739–876,
Apr. 2006.
[8] D. G. Andersen, A. C. Snoeren, and H. Balakrishnan,“Best-path vs. multi-path overlay routing,” in Proceedingsof ACM SIGCOMM conference on Internet measurement,Oct. 2003.
[9] S. Banerjee, C. Kommareddy, K. Kar, B. Bhattacharjee,
and S. Khuller, “Construction of an eﬃcient overlay multicast infrastructure for real-time applications,” in Proceedings of IEEE INFOCOM 2003, Apr. 2003.
[10] Scalable Sensing Service. available at http://networking.
hpl.hp.com/s-cube/.
[11] PlanetLab Web Page. available at http://www.planet-lab.
org/.
[12] traceroute.org. available at http://www.traceroute.org/.