発表の流れ
 研究背景A study on free-riding traffic
freefree-riding
problem in overlay routing

 研究目的 評価指標オーバレイルーティングに起因する

 対象パス，メトリック
 使用データ

ただ乗り問題に関する研究 オーバレイルーティングの有効性評価
 ネットワークただ乗り問題
 ただ乗り問題の定量的指標

大阪大学 大学院情報科学研究科
情報ネットワーク学専攻 中野研究室
平岡 佑一朗 ただ乗り問題の評価
 まとめと今後の課題

2008/2/15

研究背景

2研究目的

 オーバレイルーティング オーバレイルーティングの有効性評価

 トラヒックのルーティングをサービスとする 遅延時間に加え，利用可能帯域，TCPスループットをメトオーバレイネットワーク
 エンドホストが享受する性能の向上

リックとした場合の有効性
 メトリック間の相関関係

 オーバレイルーティングの性能評価
 遅延時間やパケット廃棄率を用いた評価が行われている⇒ 帯域情報を用いた場合の性能評価が必要

 ネットワークただ乗り問題の定量的評価
 定量的指標の導入

 オーバレイルーティングにより生じる問題

 メトリック別のただ乗り量の評価⇒ IP ルーティングとのポリシーの相違が原因⇒ ネットワークただ乗り問題

 ただ乗りを緩和できる迂回パスの存在割合
 ただ乗りの制限量と性能改善度の関係

 ISP のコスト構造を無視したトラヒックの発生

2008/2/15

平成19年度 修士論文報告会
平成19年度

平成19年度 修士論文報告会
平成19年度3

2008/2/15

平成19年度 修士論文報告会
平成19年度

4

評価指標

使用データ

 PlanetLab [12] 上でオーバレイルーティングを行う

 PlanetLab 参加ノード間の遅延時間，利用可能帯域

 転送パスの候補の計測結果

 直接パス (ノード間で直接転送) 3-hop
relay path
 2ホップ迂回パス

 Scalable Sensing Service [13] が計測・公開
Direct path

(中継ノードを 1つ用いて転送) Sourcenode 3ホップ迂回パス(中継ノードを 2つ用いて転送) 2-hop
relay path
 ルーティングメトリック 遅延時間

Destinationnode AS単位でノードをグルーピングし，同ASペアのデータが複数ある場合は，その平均値を使用
PlanetLab
nodeGroupingby AS
numberRouting overlay
network
IPnetwork 利用可能帯域

AS1

 TCPスループット
AS1

 性能改善度：

Take the averagefor measurement
results between
ASes

AS3

AS2

 直接パスの性能を １としたときの迂回パスの性能の改善度
AS3

2008/2/15

平成19年度 修士論文報告会
平成19年度5

2008/2/15

AS2

平成19年度 修士論文報告会
平成19年度61

CDF of node pair

最適迂回パスによる性能改善度

1
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0

利用可能帯域

TCP スループット

遅延時間0.1

110

average of improvement ratioof the path in available bandwidth

オーバレイルーティングの有効性評価

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

遅延時間と利用可能帯域の相関

Routing overlay

Relay pathから，送受信の利益を受けな Direct path
い ISP にコストがかかる問題

10

ノード Ni,Nj 間で通信発生
 直接パスの選択時⇒ Cij にかかるコストはISP I が支払う
⇒ コストは Ni から回収可能 迂回パスの選択時⇒ Ckj にかかるコストはISP K が支払う
⇒ コストは Ni から回収不可

Nk



10.1
averageconfidence interval

0.01

0.01

0.1

1

10100

improvement ratio of
the latency-optimized 2-hop relay path

improvement ratio 利用可能帯域，遅延時間をメトリックとする場合は90％以上のノードペアで性能が改善する
 TCPスループットをメトリックとする場合は，50%以上のノードペアで性能が改善しない
 遅延時間が改善する迂回パスは利用可能帯域も改善する場合が多い
2008/2/15

Nj ルーティングポリシーの相違 network100

平成19年度 修士論文報告会
平成19年度7

ただ乗り問題の定量的指標

Ni
IP network

Nj

ISP J
Transit link: Cij

Transit link: Ckj

ISP I

Ni

Nk

ISP K

Peering link: Cik トラヒックはアプリケーションレベルで転送⇒ パケットの送信先，送信元アドレスの監視により，ただ乗りトラヒックを区別することはできない
2008/2/15

平成19年度 修士論文報告会
平成19年度

8

ただ乗り量の評価
Percentage of the whole nodepairs ただ乗り量 迂回パスを使うことにより新たに通過するトランジットリンクの本数
 使用データ ノードの所属する AS 番号
 traceroute.org [16] の所有するルートサーバから取得

0.5

Available Bandwidth
End-to-End Latency
TCP Throughput

0.4
0.3
0.2最適迂回パスで発生するただ乗り量0.100

 AS間リンクの種類の推測データ

123456

Number of free-riding transit links

 CAIDA [23] が推測・公開しているものを利用

 TCP スループットをメトリックとする場合は，他の場合に比べて最適迂回パスでのただ乗り発生が少ない⇒ TCPスループットが最適な迂回パスはASホップ数が少ない 利用可能帯域，遅延時間をメトリックとする場合は，多くのノードペアでただ乗りが発生する
2008/2/15

平成19年度 修士論文報告会
平成19年度

9

最適迂回パスと比較したときの選択
パスの性能改善度

Performance improvement ratio
against best 2-hop relay path

ただ乗りの制限量と性能改善度

2008/2/15

10

まとめと今後の課題
 まとめ

10.9

 遅延時間，および利用可能帯域の情報に基づいたオー0.8

バレイルーティングの有効性評価

0.7

 遅延時間，利用可能帯域を用いた場合の有効性が高い

0.6

 遅延時間が大きく改善するパスの多くは利用可能帯域も改善

0.50.4

 ネットワークただ乗り問題の定量的評価

Available Bandwidth
End-to-End Latency
TCP Throughput (L=0.01)
TCP Throughput (L=0.001)
TCP Throughput (L=0.0001)
TCP Throughput (L=0.00001)

0.3
0.2
0.1
00

1

2

3

4

5

ただ乗り量の上限

678

 性能改善を目的としたルーティング⇒ 性能が改善する迂回パスの多くでただ乗りが発生
 TCP スループットをメトリックとした場合の性能の低さ⇒ 中継ノードでTCPを終端・中継転送することで改善可能
 利用可能帯域をメトリックとしたときに，ただ乗り量が少なく，性能が改善するパスを選択可能

9

Number of free-riding transit links
 ただ乗り量を 4本に制限しても十分な性能が得られる

 今後の課題 利用可能帯域を用いる場合，2本の制限で最適値の80%の性能が得られる⇒ ただ乗り緩和のためにはもっとも適したメトリック
2008/2/15

平成19年度 修士論文報告会
平成19年度

平成19年度 修士論文報告会
平成19年度 ただ乗りトラヒックの検出手法の検討
 ただ乗り量に応じた新たな ISP のコスト構造の提案
11

2008/2/15

平成19年度 修士論文報告会
平成19年度122