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

信学技報
TECHNICAL REPORT OF IEICE.

ISP コストを削減するための重回帰分析に基づくオーバレイルーティング手法
松田

一仁†

長谷川

剛††

村田

正幸†

† 大阪大学大学院情報科学研究科〒 565–0871 吹田市山田丘 1–5†† 大阪大学サイバーメディアセンター 〒 560–0043 豊中市待兼山町 1–32
E-mail: †{k-matuda, murata}@ist.osaka-u.ac.jp, ††hasegawa@cmc.osaka-u.ac.jp
あらましオーバレイルーティングは，オーバレイネットワーク上で行われるアプリケーションレベルの経路制御技術であり，遅延時間，利用可能帯域，TCP スループットなどを指標として経路選択を行うことで，エンドホストが享受する性能が向上することが知られている．一方で，IP 層で行われるルーティングとのポリシの違いにより，ISP の金銭的コスト構造に悪影響を与える，ただ乗り問題が発生することが考えられる．本稿では，オーバレイルーティン
グによるユーザ性能を向上しつつ，ISP への悪影響を削減するオーバレイルーティング手法を提案する．提案手法は，

ISP のコストに直結する経路上のトランジットリンク数を他のメトリックによって推定するための重回帰分析を行い，得られた推定式を用いてオーバレイルーティングを行う．PlanetLab ノード間の計測結果を用いた数値評価により，提案手法が ISP のコスト悪化を低減しつつ，ユーザ性能を向上することが可能であることを示す．
キーワード

オーバレイネットワーク，オーバレイルーティング，ただ乗り問題，重回帰分析，PlanetLab

Decreasing ISP transit cost in overlay routing
based on multiple regression analysis
Kazuhito MATSUDA† , 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: †{k-matuda, 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 could be
improved by overlay routing, which is routing mechanism worked on overlay network. However, some problem will
occur because of the policy mismatching between IP routing and overlay routing, which harm the monetary cost
structure of ISPs. In this report, we propose an overlay routing mechanism which can decrease ISP’s transit cost as
well as improve user-perceived performance. The proposed method will select the overlay-level route by using theestimated value of the increase degree of transit links on the route. We conﬁrm the eﬀectiveness of the proposed
method with PlanetLab environment and present that our method can keep the user-perceived performance while
decreasing the number of traversing transit links by overlay routing.
Key words Overlay networks, Overlay routing, free-riding problem, Multi regression analysis, PlanetLab

1. は じ め に
近年，IP ネットワーク上に独自の論理ネットワークを構築
してサービスを提供する，サービスオーバレイネットワークが登場している．その中の一つに，特定のアプリケーションのみを対象とせず，トラヒックのルーティングのみを行うオーバ
レイネットワークがある．例えば Resilient Overlay Network(RON) [1] では，参加ノード間の伝搬遅延時間やパケット廃棄率を計測し，直接宛先ノードへデータを転送するか，他のオーバレイノードを経由する迂回経路を用いるのかを判断する．本
稿では，オーバレイネットワーク上で行われるアプリケーショ
ンレベルのトラヒックのルーティングをオーバレイルーティン
グ，IP 層で行われるルーティングを IP ルーティングと呼ぶ．
オーバレイルーティングを用いることで，IP ルーティング
よりもユーザが感じる性能を向上させることが可能であることが明らかにされてきている [2-8]．これらの研究では伝搬遅延時
間のみを指標として評価が行われているが，我々の研究グルー
プでは [9] において伝搬遅延時間に加え帯域情報 (利用可能帯

—1—

図1

オーバレイルーティング

域及び TCP スループット) を含めた評価を行い，これらの性能がオーバレイルーティングによって大きく向上することを明らかにした．これらの性能向上は一般的に， ISP が自身の金銭的コストを考慮して制御する IP ルーティングと，ユーザが自身の感じる性能を最大化するために制御するオーバレイルー
ティングのポリシが異なることに起因する．これは逆に言うと，ユーザがオーバレイルーティングを行うことによって，ISP の金銭的コスト構造に悪影響を与える可能性があるといえる．この問題を本研究グループではただ乗り問題と呼び，ISP にとって無視できない問題であることを指摘している [3]．
この問題を解決する一つの方法として，ただ乗り問題を緩和するオーバレイルーティングを用いることが挙げられるが，ただ乗り問題の指標となる，経路上に存在する ISP 間のトラン
ジットリンクの情報は一般には公開されていない．一方，我々の研究グループでは [9] において，ただ乗り問題に関する基礎的な検討を行い，TCP スループットを指標としてオーバレイ
ルーティングを行った場合にただ乗り問題が減少することから，経路上に存在するトランジットリンクの数 (以下，トランジット
数と略称する) が観測可能な指標と相関を持つ可能性があることを知見として得た．しかし，具体的にただ乗り問題を緩和させるオーバレイルーティング手法はこれまで提案されていない．
そこで本稿では，ただ乗り問題を緩和するオーバレイルー
ティングの手法を提案する．具体的には，重回帰分析を用いることにより，トランジット数をオーバレイノードが容易に取得できるネットワーク性能指標から推定し，間接的にトランジット数を制限することでただ乗り問題を緩和する．本稿における数値評価のためには，Scalable Sensing Service [10] (以下，S 3 と表記する) が公開している，PlanetLab [11] に参加しているノード間のデータ，PlanetLab ノード間でフルメッシュ
traceroute を行うことによって計測した IP レベルの経路情報，
CAIDA [12] が公開している AS 間関係情報・AS 間リンク情報，及び Route Views Project [13] が公開している IP アドレ
スプレフィックスと AS 番号の対応情報を用いる．
以下，2 章では本稿で扱うオーバレイルーティングとその問題点について説明する．3 章では，オーバレイルーティングにおいて経路選択に用いる指標について説明する．4 章では，重回帰分析によるトランジット数の推定手法を示した後，その精度を評価する．5 章ではオーバレイルーティングの性能を，ト
ランジット数を制限しない場合 (5.1 節)，及びトランジット数に制限を設けた場合 (5.2 節) について評価する．最後に 6 章で本稿のまとめ及び今後の課題について述べる．

2. オーバレイルーティングとその問題点
2. 1 オーバレイルーティング
オーバレイルーティングは，ユーザやサービスプロバイダが

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

独自の論理トポロジを構成してアプリケーションレベルのルー
ティングを行うことにより，ユーザが感じる性能である遅延時間，利用可能帯域，TCP スループットなどを指標としてルーティングを行うことを可能とする技術である (図 1)．対して，現在のインターネットにおいて IP 層で行われているルーティ
ングは，主としてルータホップ数あるいは AS ホップ数を指標としており，必ずしもユーザが感じる性能が最適化されるような経路選択が行われていない．
ま た ，IP の ネット ワ ー ク 提 供 者 で あ る Internet Service
Provider (ISP) は他の ISP との商業的関係に基づいたコス
ト構造に従ってルーティングを行う．ISP は他の ISP とのリンクとして上位あるいは下位の ISP と接続するトランジットリ
ンク，及びピアリング関係を結ぶためのピアリングリンクを持つ（注 1）．一般的にトランジットリンクは通過するトラヒック量の最大値によってその金銭的コストが決定される．一方，ピア
リングリンクで発生する金銭的コストは回線の維持費のみであるが，ピアリングを結ぶ ISP を起点及び終点とするトラヒック
のみを通過させるのが一般的である．ISP はこのような各リンクの違いを考慮して経路を設定する．
上述のようなルーティングポリシの違いが原因となり，オーバレイルーティングを用いて遅延時間，利用可能帯域等を指標としたルーティングを行うことでユーザが感じる性能を向上させる余地が生まれる．例えば図 1 において，線分の長さが伝搬遅延時間を表すものとすると，ルータホップ数の観点では IPパスの方が性能が良いが，遅延時間の観点では IP パスよりもオーバレイパスの方が性能が良い．
2. 2 ISP への影響
上述のように，オーバレイルーティングによってユーザ性能が向上するが，一方で，オーバレイルーティングにより ISP の意図したコスト構造を無視したトラヒックが発生し，ISP が不当な金銭的コストを支払わなければならない状況が発生する．
図 2 に典型的な例を示す．図 2 において，実線で囲まれた範囲をそれぞれの ISP に属するルータ及びエンドノードとする．
また，ISP C を上位 ISP とし，ISP A，ISP B はそれぞれ ISP
C との間にトランジットリンクを持つ．ISP A と ISP B の間にはピアリングリンクが張られている．
このとき，ISP A に属するエンドノードから ISP C に属する
エンドノードへデータ転送要求が発生したとする．IP ルーティ
ングによって経路を決定した場合，又はオーバレイルーティン
グにおいて他ノードを迂回する経路よりも直接経路の方が性能がよい場合には，使用されるリンクは ISP A ，ISP C 間のト
ランジットリンクとなる．この場合には一般的な課金構造に従（注 1）：シブリングリンクは同一組織内 (同一 ISP 内) でのリンクであるため，
本稿では対象外としている.

—2—

い， ISP A から ISP C にトランジットリンクの利用料金が支払われ，ISP A は自身のエンドユーザから利用料金を回収することでトランジットコストを回収できる．
一方，オーバレイルーティングにおいて ISP B を経由するような迂回パスを選択する場合には，ISP A で発生したトラヒッ
クは ISP A，ISP B 間のピアリングリンクを経由した後，ISP
B，ISP C 間のトランジットリンクを使用して ISP C に転送される．このため，発生したトラヒックに対する金銭的コストは
ISP B から ISP C に支払われることになる．このとき，ISP
B は本来のトラヒック送受信者である ISP A のエンドユーザ
から利用料金を回収することはできない．このように，オーバ
レイルーティングによって迂回経路が選択された結果，直接経路を用いる場合には用いられなかったトランジットリンクが用いられるために，その経路を用いたデータ送受信を行うことによって利益を得るユーザが属する ISP と，金銭的コストを負担する ISP が異なるという状況が発生する．この問題を我々はただ乗り問題と呼んでいる [3]．
ISP 間のリンクを通過するトラヒックがただ乗りトラヒックであるか判断が可能であれば，これらのトラヒックに対して利用制限を課す，あるいは別途課金構造を構築するなどの対策が可能である．しかし，オーバレイルーティングはアプリケー
ションレベルで行われるため，パケットの送受信 IP アドレスを監視することでは他のトラヒックとの区別はできない．今後
オーバレイルーティングが普及しこのようなトラヒックが増加
すると，ISP の金銭的コスト構造に影響を与え，ISP にとって深刻な問題になると考えられる．

3. 使用データと評価方法
本章では，オーバレイルーティングの性能評価，及び重回帰分析を用いたオーバレイルーティング手法のために使用するデータの説明と，オーバレイルーティングが経路を選択する際の指標を説明する．
3. 1 使用データ
本稿では，PlanetLab に参加しているノードがオーバレイ
ネットワークを構築することを想定する．オーバレイルーティ
ングを行うために必要となるノード間の遅延時間及び利用可能
帯域は S 3 において公開されている PlanetLab ノード間のネッ
トワーク性能計測結果を利用する．S 3 では PlanetLab ノード間の物理帯域，遅延時間，利用可能帯域及びパケット棄却率がおよそ 4 時間毎に計測され，その結果が公開されている．本稿
では 2008 年 11 月 12 日に計測・公開されたデータを主として利用する．加えて，5.1 節で詳述する経年の変化を見るために2006 年 10 月 25 日，2007 年 9 月 2 日，及び 2009 年 4 月 8日に計測・公開されたデータを併せて利用する．
経路上のトランジットリンク数は，CAIDA において公開されている AS 間の関係情報 (ピアリングあるいはトランジット)を用いる．しかし，全ての AS 間関係が提供されていないため，
これによって得られない AS 間情報は，CAIDA の AS 間リン
ク情報から得られる各 AS の次数 (他 AS との接続関係の本数)を用いた推定 [9, 14] を行う．具体的には，CAIDA の AS 間情報において，AS 間関係がわかっている AS ペアの次数の分布を求め，AS 間関係が不明な AS ペアの関係をその分布に従って確率的に推定する．本稿では，CAIDA の AS 間情報は 2008
年 8 月 18 日に，AS 間リンク情報は 2009 年 1 月 23 日に公開されたものを利用する．
上記 CAIDA の AS 間情報は AS 番号で記述されているため，オーバレイルーティングで用いる経路がどの AS を通過しているかを知る必要がある．このため我々は PlanetLab ノード間でフルメッシュに traceroute コマンドを実行し，ルータ( IP アドレス) レベルの経路を取得し，Route Views Projectより取得できる IP アドレスプレフィックス と AS 番号の対応に当てはめて AS レベルでの経路を取得した．なお，AS 番号が不明なルータが存在するが，これは直前の AS とのリンクがBGP において広告される必要がないためと考えられる．このため，ある AS から AS 番号が不明なルータへのリンクは一般的に BGP で広告されないピアリングリンクであると推定する．
本稿では，2008 年 11 月 12 日に実行した traceroute データを用いる．
3. 2 オーバレイルーティングの経路選択指標
本節では，オーバレイルーティングにおいて経路を選択する
際の指標について説明を行う．なお本稿では，オーバレイルー
ティングにおいて候補となるパスは以下の 2 種とする．
直接経路 他ノードを迂回せず，直接送信元から宛先ノードへ至る経路．オーバレイネットワークとしては 1 ホップの経路となり，IP のルーティング制御に従ってパスが決定される．
迂回経路 送信元ノードから一度他のノードを経由し，宛先ノードへ至る経路．本稿では迂回するノードは 1 つのみ，つまり 2ホップの経路のみに限定する．これは，3 ホップ以上の迂回経路はユーザ性能向上の観点ではほとんど効果がないことが知られているためである [15]．
3. 2. 1 遅 延 時 間
遅延時間を指標としたオーバレイルーティングは，帯域よりも応答性を重視するようなアプリケーションに適している．迂回経路の遅延時間は，迂回経路を構成するノード間経路の遅延時間の和を用いる．ノード Ni とノード Nj の間の遅延時間を
δij とすると，直接経路及び迂回経路の遅延時間はそれぞれ式(1)，(2) で表される．
1
Dij
= δij

(1)

2
Dikj

(2)

= δik + δkj

最適な性能を持つ迂回経路の遅延時間は次式で表される．

(

2
2
D̂ij
= min Dikj

)

k=i,j
|

(3)

ここで，直接経路の性能に対する最適な迂回経路の性能比を性能向上率と定義すると，迂回経路の遅延時間の性能向上率は，
2
I(Dikj
) =

1
Dij

(4)

2
D̂ikj

となる．
3. 2. 2 利用可能帯域
利用可能帯域を指標としたオーバレイルーティングは，大容量のデータを連続して流すストリーミングやファイル転送に適している．迂回経路の利用可能帯域は，迂回経路を構成する
ノード間経路のうち，最小の利用可能帯域を用いる．ノード Niとノード Nj の間の利用可能帯域を βij とすると，直接経路及び迂回経路の遅延時間はそれぞれ式 (5)，(6) で表される．
1
Bij
= βij

(5)

2
Bikj

(6)

= min (βik ，
βkj )

最適な性能を持つ迂回経路の利用可能帯域は次式で表される．

(

2
2
B̂ij
= max Bikj

)

k=i,j
|

(7)

利用可能帯域の性能向上率は，—3—

ルータホップ数 0.420
遅延時間
0.300
利用可能帯域-0.0271.0

表 1 トランジット数と各指標の相関係数

0.7

0.9

2
B̂ikj
1
Bij

2
I(Bikj) =(8)

Tij1 = τij(9)= τik + τkj(10)

迂回経路を用いることによるトランジット数の増加を制限する
場合は，遅延時間では式 (3) ，利用可能帯域では式 (7) に条件
として式 (11) を加える．

Tikj <= Tij + α

α = 0, 1, . . . , n(11)

ここで，α は迂回経路のトランジット数が直接経路のトランジッ
ト数をどれだけ超過して良いかを表しており，例えば α = 0 であれば迂回経路のトランジット数が直接経路のトランジット数を越えない，という制限となる．

4. 重回帰分析によるトランジット数の推定
ただ乗り問題の指標となる経路上のトランジット数は一般には公開されていないため，エンドユーザはオーバレイルーティ
ングにおける経路選択の指標としてトランジット数を直接用いることはできない．本稿ではこの問題を解決するため，エンド
ユーザが観測可能なネットワーク性能指標から重回帰分析を用いてトランジット数を推定する手法を提案する．
本章では，まず重回帰分析を行う上でどの指標を用いるべきかを判断するために各指標とトランジット数の相関関係を示す．
その後，相関関係によって選択した指標のデータを用いて重回帰式を導出し，その精度を評価する．
4. 1 各指標の相関関係
最初に，使用する指標を決定するために，各指標とトラン
ジット数の相関関係を確認する．相関関係の確認には式 (12)に示すピアソンの積率相関係数 C を用いる．ここで，全てのノードペアの組み合わせ Ni ，Nj ，に対して xij ，yij を相関を求めたい性能指標，x̄，ȳ をそれぞれの指標の平均値とする．

∑

C = √∑(xij − x̄)(yij − ȳ)(xij − x̄)2

0.6
0.5
0.4
0.3

となる．
3. 2. 3 トランジット数
本稿では経路上のトランジット数をただ乗り問題の指標として用い，これを制限することでただ乗り問題を緩和した経路選択を行う．ノード Ni とノード Nj の間のトランジット数を τijとすると，直接経路及び迂回経路のトランジット数はそれぞれ
式 (9)，(10) のようになる．

2
Tikj

CDF of paths

0.8

√∑

(yij − ȳ)2(12)

表 1 にトランジット数と各指標の間の相関係数を示す．表 1 から，利用可能帯域を用いた場合の相関係数の絶対値が他の指標に比べて著しく低いことがわかる．このため，重回帰分析の計算の複雑性，及び重回帰分析の精度の観点から，利用可能帯域
は重回帰分析に使用する指標から除外する．
4. 2 重回帰式の導出
重回帰分析は，4.1 節の結果から，ルータホップ数及び遅延時間を用いて，最小二乗法を用いて行う．具体的には，各指標間の偏差平方和・積和行列を S ，トランジット数と各メトリッ

0.2

Multi
Single(router hops)
Single(latency)

0.1
0

-6
-4
-2
0
2
4
6
Difference between exact-transit and estimate-transit (links)

図 3 トランジット数の推定誤差の確率密度

クの偏差積和ベクトルを c とすると，重回帰式の偏回帰係数ベ
クトル b は次式で表される．

b = S −1 c(13)重回帰式の切片は，トランジット数，ルータホップ数，遅延時間の平均をそれぞれ t̄，r̄，d¯ ，式 (13) で求めた偏回帰係数を
bt ，br ，bd とすると，式 (14) のようになる．

¯dby = t̄bt − r̄br − db

(14)

以上からノード Ni ，Nj 間のトランジット数の推定値 Tij は，
hij を Ni ，Nj 間のルータホップ数，δij を遅延時間 (ms) として次式で表される．

Tijc = 0.1419hij + 0.002482δij + 1.136(15)

4. 3 重回帰式の精度
本節では 4.2 節で導出した重回帰式 (15) の精度を，3.1 節で示したトランジット数と式 (15) によって推定したトランジッ
ト数を比較することで検証する．具体的にはノード Ni ，Nj 間
eのパスに関して，真のトランジット数を Tij，式 (15) で推定しc
たトランジット数を Tij として，式 (16) を求めた．
dij = Tije − Tijc

(16)

図 3 は，全てのノードペアに対する dij の累積密度分布を示したものである．なお比較対象として，ルータホップ数，遅延時間のそれぞれで最小二乗法による単回帰分析を行った場合のdij の累積密度分布も併せて示した．結果から，真のトランジッ
ト数よりも過大推定してしまう場合において，その誤差は 4 以
内に抑えられており，80 % のノードペアにおいて過大推定の誤差は 1 以内に抑えられている．また，ルータホップ数，遅延時間による単回帰分析に比べて，重回帰分析による推定式では過大推定，過小推定の両方でより良い性能を得られており，またデータに対して滑らかに推定が行えている．

5. オーバレイルーティングの性能評価
本章では，3 章で示した選択指標でオーバレイルーティングを行った場合の性能評価を示す．まず，トランジット数を制限しない場合の評価結果を示し，その後，トランジット数を制限した場合の評価を示す．
5. 1 トランジット数を制限しない場合の評価結果
トランジット数を制限しない場合の評価は，2006 年 10 月
25 日，2007 年 9 月 2 日，2008 年 11 月 12 日，及び 2009 年
4 月 8 日の 4 日間の S 3 のデータを用い，各指標の性能評価を行うと共に，経年変化に関する評価を行う．
図 4 は，2008 年 11 月 12 日の データについて，各ノードペ

—4—

0.9

10000

0.8
1000

100

100
10

0.7
CDF of paths

latency (best of 2-hops paths) (msec)

1.0

0.6
0.5
0.4
0.3

10

06/10/25
07/09/02
08/11/12
09/04/08

0.2
1
10

0.1

100

0

latency (direct path) (msec)

0.1(a) 遅延時間を指標とした場合

1
Improve ratio

10(a) 遅延時間を指標とした場合

0.8
0.7

1e+05
100

10000
10

1000

0.6
0.5
0.4
0.3
06/10/25
07/09/02
08/11/12
09/04/08

0.2

100
1
10

100

1000

10000

1e+05

1e+06

bandwidth (direct path) (Kbps)(b) 利用可能帯域を指標とした場合

図4

0.9

1000

1e+06

CDF of paths

bandwidth (best of 2-hops paths) (Kbps)

1.0

直接経路と最適な性能を持つ迂回経路の比較 (08/11/12)

アの直接経路の性能と，最良の性能を持つ 2 ホップ迂回経路の性能の関係の分布をプロットしたものである．この図から， 遅
延時間を用いた場合 (図 4(a)) には直接経路と迂回経路の性能差が小さく，オーバレイルーティングによる性能向上の余地が小さいことがわかる．それに対して，利用可能帯域を用いた場
合 (図 4(b)) は，直接経路に比べて，最適な性能をもつ迂回経路の性能が大幅に向上する場合が多く存在することから，オーバレイルーティングによって性能が向上する余地があることがわかる．
図 5 は，上記した 4 日間のデータについて，遅延時間および利用可能帯域を用いた場合の性能向上率の累積密度分布を示したものである．遅延時間を用いた場合 (図 5(a)) には， 2006
年 10 月 25 日の性能がもっとも良く，2007 年 9 月 2 日，2008
年 11 月 12 日と年を追う毎に性能が悪化しており，2009 年 4
月 8 日では 2008 年 11 月 12 日より僅かに改善している．直接経路よりも性能のよい迂回経路が存在するノードペアの割合はそれぞれ，74 %，76 %，35 %，及び 40 % となっている．この原因は現在調査中であるが，IP 層におけるルーティングが，ユーザ性能を考慮した方向に変化したことが一因ではないかと推測される．一方，利用可能帯域を用いた場合は，全体的には2008 年 11 月 12 日の性能がもっとも良いが，性能向上率が 40を越えるノードペアに関しては 2006 年 10 月 25 日がもっとも多いものの，その差は僅かであり，経年を通して大幅な性能向上が可能であることがわかる (図 5(b))．直接経路よりも性能のよい迂回経路が存在するノードペアの割合は全ての日付で 99%以上である．
5. 2 トランジット数を制限した場合の評価結果
トランジット数を制限した場合の評価は，2008 年 11 月 12日の S 3 のデータを用いて行う．また，3 章で導出方法を示した真のトランジット数と，式 (15) を用いたトランジット数の推

0.1
0
0.1

1

10
100
Improve ratio

1000

10000

(b) 利用可能帯域を指標とした場合

図 5 トランジット数を制限しない場合の性能向上率

定値をそれぞれ用いた場合の評価を行うことで，4 章で提案した重回帰分析を用いたトランジット数の推定手法の性能を検証する．
図 6 は，真のトランジット数を用いた場合における，迂回経路を用いることによるトランジット数の増加の制限幅 α を変化させた時の性能上昇率の分布を示している．なお，式 (11)の条件を満たす迂回経路が存在しない場合は，性能向上率を 0としている．遅延時間及び利用可能帯域のいずれを用いる場合
においても，α の値が大きくなると，制限がない場合における性能に近づき，α = 3 でほぼ同等の性能になることがわかる．
このことから，オーバレイルーティングによって迂回経路が選択される場合に，増加するトランジット数を 3 以内に制限しつつ，制限がない場合とほぼ同等のユーザ性能を得ることができるといえる．
図 7 は，トランジット数の推定値を用いた場合における，図6 と同様の結果を示している．遅延時間，利用可能帯域共に，
α が 0 から 2 の時には，式 (11) 条件を満たす迂回経路が見つからない場合が多いことがわかる．一方，α が 3 以上の場合には，真のトランジット数を用いる場合とほぼ同等の性能向上率が得られていることがわかる．図 6 および図 7 の結果より，本稿で提案した重回帰分析によるトランジット推定手法は，オーバレイルーティングにおいて迂回経路が選択される場合のトランジット数の増加数の制限が 3 以上である場合には，真のトラ
ンジット数を用いる場合と同様に，トランジット数の増加が無い場合とほぼ同等のユーザ性能が得られることがわかった．

6. ま と め
本稿では，オーバレイルーティングを行うことで発生する
ISP のコスト悪化を軽減するためのオーバレイルーティング手

—5—

1.0

0.9

0.9

0.8

0.8

0.7

0.7
CDF of paths

CDF of paths

1.0

0.6
0.5
0.4

no limited path
α=0
α=1
α=2
α=3
α=4
α=5

0.3
0.2
0.1

0.6
0.5
0.4

no limited path
α=0
α=1
α=2
α=3
α=4
α=5

0.3
0.2
0.1

0

0
0.1

1
Improve ratio

10

0.1

1.0

1.0

0.9

0.9

0.8

0.8

0.7

0.7

0.6
0.5
0.4

no limited path
α=0
α=1
α=2
α=3
α=4
α=5

0.3
0.2
0.1
0.1

1

10
100
Improve ratio

10(a) 遅延時間を指標とした場合

CDF of paths

CDF of paths(a) 遅延時間を指標とした場合

1
Improve ratio

1000

0.6
0.5
0.4

no limited path
α=0
α=1
α=2
α=3
α=4
α=5

0.3
0.2
0.1
10000

0.1

1

10
100
Improve ratio

1000

10000

(b) 利用可能帯域を指標とした場合(b) 利用可能帯域を指標とした場合

図 6 3 章で述べたトランジット数を制限した場合の性能向上率

図 7 式 (15) によって推定したトランジット数を制限した場合の性能向上率法を提案した．提案手法は重回帰分析を用いることによって，経路上のトランジット数を容易に取得可能なネットワーク性能指標を用いて推定し，オーバレイルーティングによって迂回経路が用いられる際に発生するトランジット数の増加幅を抑制す
る．PlanetLab 環境を想定した性能評価の結果，提案手法を用いることにより，トランジット数の増加数の制限が 3 以上である場合には，提案した推定式の性能が，真のトランジット数を用いた場合とほぼ同等の性能を示すこと，また，その時，トランジット数に制限がない場合とほぼ同等のユーザ性能を得ることができることを明かにした．
今後の課題として，外れ値を考慮した重回帰分析の精度の向上が挙げられる．また，本稿では単一の指標に基づいて経路選択を行ったが，複数の指標を考慮した経路選択を行った場合の評価を行う予定である．
文
献[1] D. G. Andersen, H. Balakrishnan, M. F. Kaashoek, and
R. Morris, “Resilient overlay networks,” in Proceedings of
18th ACM Symposium on Operating Systems Principles,
Oct. 2001.
[2] C. L. T. Man, G. Hasegawa, and M. Murata, “Monitoring overlay path bandwidth using an inline measurement
technique,” IARIA International Journal on Advances in
Systems and Measurements, vol. 1, no. 1, pp. 50–60, 2008.
[3] G. Hasegawa, M. Kobayashi, M. Murata, and T. Murase,“Free-riding traﬃc problem in routing overlay network,” inProceedings of ICON 2007, Nov. 2007.
[4] M. Uchida, S. Kamei, and R. Kawahara, “Performance evaluation of QoS-aware routing in overlay network,” in Proceedings of ICOIN 2006, Jan. 2006.
[5] S. Kamei, “Applicability of overlay routing in Japan using
inter-domain measurement data,” Overlay Network Workshop, Dec. 2006.

[6] 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.
[7] 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.
[8] 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.
[9] 平岡佑一朗, 長谷川剛, and 村田正幸, “オーバレイルーティング
によるネットワークただ乗り問題の評価とその緩和手法に関する一検討,” 電子情報通信学会技術研究報告, vol. 107, no. 525,
pp. 271–276, 2008.
[10] Hewlett-Packard Laboratories, “Scalable sensing service.”
available at http://networking.hpl.hp.com/s-cube/.
[11] PlanetLab Web Page. available at http://www.planet-lab.
org/.
[12] University of Callfornia, “Caida.” available at http://www.
caida.org/home/.
[13] University of Oregon, “Route views project.” available at
http://www.routeviews.org/.
[14] X. Dimitropoulos, D. Krioukov, M. Fomenkov, B. Huﬀaker,
Y. Hyun, k. claﬀy, and G. Riley, “As relationships: inference and validation,” SIGCOMM Comput. Commun. Rev.,
vol. 37, no. 1, pp. 29–40, 2007.
[15] G. Hasegawa, Y. Hiraoka, and M. Murata, “Eﬀectivenessof overlay routing based on delay and bandwidth information,” IEICE Transactions on Communications, vol. E92B, pp. 1222–1232, April 2009.

—6—