PlanetLab における 効率的な近隣サーバ選択法

Presentation on theme: "PlanetLab における 効率的な近隣サーバ選択法"— Presentation transcript:

1 PlanetLab における 効率的な近隣サーバ選択法
後藤研究室　修士2年 米山 諒 修士論文審査会 2011/2/4

2 Agenda 研究テーマ 背景 Contents Delivery Network (CDN) 提案手法 実験内容 実験結果 結論
修士論文審査会 2011/2/4

3 研究テーマ 地理情報 (位置) が把握できない クライアントからのリクエストに対する 最適なサーバ選択アルゴリズムの実現
目標規定文 効率的な近隣サーバ選択法の提案 クライアントからサーバへの地理距離に対する最適化 世界規模ネットワーク (インターネット) における利用検討 地理情報 (位置) が把握できない クライアントからのリクエストに対する 最適なサーバ選択アルゴリズムの実現 修士論文審査会 2011/2/4

4 研究背景 Web コンテンツのリッチ化によりアクセスの集中やネットワーク遅延の影響が大きくなっている
コンテンツを地理的に分散配置し最適化された Contents Delivery Network (CDN)が注目される 地理的な距離の近いサーバ利用が効率的だが， クライアントの地理情報が必ず取れるわけではない 修士論文審査会 2011/2/4

5 Contents Delivery Network (CDN)
Web コンテンツ配信用に最適化されたネットワーク Contents Server の選択手法 DNS ラウンドロビン P2P (Distributed Hash Table) 地理情報を加味した複雑な手法 例: Akamai DNS System CNAME レコードで Root Server を指定 $ any IN CNAME toggle. toggle IN CNAME g. g IN CNAME lb1. lb IN A 修士論文審査会 2011/2/4

6 地理情報と IP アドレスマッピング MaxMind 社が提供する GeoIP クライアントとサーバの緯度経度により算出
スコア 計算結果から地理的に近いサーバを探す ドメイン名から GeoIP レコードを参照して地理情報を得る $ geoiplookup planetlab1.iii.u-tokyo.ac.jp GeoIP City Edition, Rev 1: JP, 40, Tokyo, N/A, , , 0, 0 緯度・経度の情報 ユークリッド距離による相対的な地理距離の比較 修士論文審査会 2011/2/4

7 提案手法① IP アドレス同士の XOR 値による近傍性推測 IP アドレスの近いノード同士は地理的にも近いと考えられる
1 修士論文審査会 2011/2/4

8 Contents Server のAS と隣接 AS を
提案手法② AS2107 Contents Server のAS と隣接 AS を 優先した XOR 値によるサーバ選択 AS786 /17 /14 XOR 値 >> 4 Root Server /16 /16 AS137 /13 AS17956 Client XOR 値 >> 8 AS81 Contents Server XOR 値 本実験では PlanetLab ノード群 修士論文審査会 2011/2/4

9 PlanetLab Internet 上に展開する大規模テストベッド 世界519拠点1138ノード稼働 (2010年11月時点)
実験でコンテンツサーバとして利用 修士論文審査会 2011/2/4

10 実験1 近隣5ノード選択比較 近隣5ノード選択の比較実験 Contents Server は PlanetLab のノードを使用
GeoIP による地理情報をもとにした近隣ノード選択 XOR 値による近隣ノード選択 AS 情報と XOR 値による近隣ノード選択 Contents Server は PlanetLab のノードを使用 クライアントは便宜的に公開サーバを使用 今回の実験では以下の制約がある GeoIP によって地理情報が“正確に”調べられるサーバ XOR スコアの特性上，PlanetLab のノードと同じネットワークに 属するノードをクライアントから除外 Cf. など 近隣5ノード選択の比較実験 修士論文審査会 2011/2/4

11 実験1 サーバ選択結果① www.facebook.com をクライアントとした場合 Client GeoIP XOR ASXOR
修士論文審査会 2011/2/4

12 実験1 サーバ選択結果② www.kyushu-u.ac.jp をクライアントとした場合 Client GeoIP XOR ASXOR
地理距離は若干遠いが 同じ国内のノードが 選択できている 修士論文審査会 2011/2/4

13 実験2 選択手法の精度比較 各選択手法の比較実験 各手法で近隣20ノードの精度比較を行う 世界中のクライアントからアクセスされることを想定
ランダムにノード選択 XOR 値による近隣ノード選択 AS 情報と XOR 値による近隣ノード選択 各手法で近隣20ノードの精度比較を行う 世界中のクライアントからアクセスされることを想定 Contents Server は PlanetLab のノードを使用 クライアントは便宜的に公開サーバを使用 今回の実験では以下の制約がある GeoIP によって地理情報が“正確に”調べられるサーバ 各選択手法の比較実験 修士論文審査会 2011/2/4

14 実験2における利用データ コンテンツサーバ 仮想クライアント Planet Lab に属する47ヶ国の782ノード
地理情報が取得可能なノードを抽出 仮想クライアント 世界の公開ウェブサーバ 21130ノード トップレベルドメイン (TLDs) から各100ノード程度使用 参考: Akamai CDN サービスプロバイダ世界シェア1位 世界70ヶ国に73,000台のコンテンツサーバ配置 修士論文審査会 2011/2/4

15 実験2 選択手法の比較結果 最適解 クライアント数 割合 Random 7545 35.71% XOR 13029 61.66%
AS-XOR 556 2.63% 合計 21130 100% 提案手法 65% 修士論文審査会 2011/2/4

16 実験2 選択手法の精度比較結果 選択手法 平均 中央値 Random 3.24362 3.26084 XOR 2.67670 2.34410
AS-XOR 数値が低いほど 近隣サーバ推測の精度が高い 修士論文審査会 2011/2/4

17 結論 IP アドレスによる近隣サーバの選択法を提案 PlanetLab により近隣サーバの推測が可能
クライアントとサーバの IP アドレス同士の XOR による推測 低計算コストで近隣サーバの選択ができる IP アドレスと位置情報のマッピングデータを参照しない PlanetLab により近隣サーバの推測が可能 サーバ782台で，世界の約65%に対し最適な選択ができた コンテンツサーバの IP アドレスが分散していることが理想的 BGP 経路情報 (AS) を考慮することで精度を上げられる 修士論文審査会 2011/2/4

18 ご清聴ありがとうございました 修士論文審査会 2011/2/4