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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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