2006.10.31

Research

Vivaldi: A Decentralized Network Coordinate System

分散ネットワーク(P2Pのネットワークなど?)を効率よく構成するアルゴリズムについての論文。Grid班の後輩君から教えてもらった。

MOCKの初期グラフ生成のヒントがあるかも知れないと思い、アブストだけ訳してみた。参考文献を見る限り、コアなグラフ理論の文献はほとんど無さそう(文献11の"Surface reconstruction from unorganized points"くらいか)なので、外れな予感が漂う。ま、とりあえず4ページ目くらいまで読んでみようかな。

Vivaldi: A Decentralized Network Coordinate System

Abstract

大規模インターネットアプリケーションでは、あるノードからその他のノードに接続すること無しに通信速度を予測できることがメリットとなる。明確な測定値は計測にかかるコストが得られる利得を上回ることが多く、魅力的ではない。Vivaldeはシンプルかつ少ない珪酸コストで全体の調整を各ホストに委譲するアルゴリズムであり、得られた2つのホスト間の距離はそのホスト間の接続レイテンシを正確に予測する。
Vivaldiは完全に分散し、特定のネットワークインフラや特別なホストは必要としない。このアルゴリズムでは、新しいノードを追加する際にも少数の他のノードからの遅延情報を収集するだけで適切な配置が行える為、効率的でもある。必要な接続コストもほとんど無いため、Vivaldeはアプリケーションの接続パターンに便乗することも可能であり、スケーラビリティにも優れる。
本論では仮想ネットワークを用いてVivaldiを評価した。評価に用いた仮想ネットワークには1740のインターネット上のホスト間で計測されたデータに基づいたレイテンシを持たせた。実験の結果、高度ベクトルを有する2次元ユークリッドモデルが最もエラー率が低いことが分かった。(round-tripタイム予測における相対誤差の中央値は11%であった)