Topologically-Aware Overlay Construction and Server Selectionのまとめ

読んだ所だけまとめる。

オーバーレイネットワークは物理トポロジを考慮しないネットワーク構造で構築されるので、通信の効率が悪い。
ネットワーク構築時に物理トポロジが分かれば、パフォーマンスを改善する事が可能であると考えられる。
或いは、ファイルを多数のWebサーバでミラーリングする時、物理トポロジ情報によりクライアントに最も近いサーバが分かれば、これもパフォーマンスを改善する事が出来る。

この論文で提案するdistributed binning schemeという方法は、
・最低限のインフラで実現する
・各ノードは少数のwell knownなランドマークノードのみ知っていれば良い
・完全に分散されており中央サーバなどを必要とはしない
という特徴を持つ。

ノード間計測方法としてtraceroute, BGP, レイテンシ計測の３つを検討したが、
× tracerouteは重すぎるしフィルタリングされている
× BGPはエンドホストが使えない
○ レイテンシは簡単に測れる、軽い
という理由でレイテンシを使う事にした。

レイテンシでどの程度トポロジ情報が正確に測れるかという疑問があるが、我々のターゲットアプリケーションであるオーバレイ構築とサーバ選択でのトポロジ情報の利用用途はパフォーマンス改善であり、処理を正しく行うのに正確なトポロジ情報が必要な訳ではない。
我々の実験結果では精度の低いトポロジ情報を与えても二つのアプリケーションのパフォーマンスは大幅に向上する事が分かっている。
つまり、トポロジ情報の精度なんて低くて良い。
それよりもシンプルに実現出来る方が重要。ping最強。

アプリケーションを実行しているノードは、予めランドマークノードを知っておき、全てのランドマークノードとの間の距離を計測する。
例えば、round-trip-timeを測定値として使う。
ランドマークノードをレイテンシ値の小さい順に並びかえ、測定結果のレイテンシ値をより大まかなレベル値に変換する。
例えば、３レベルに分ける場合：
レベル０ 0〜100ms
レベル１ 100〜200ms
レベル２ 200〜ms
図１のノードAの場合では、ランドマークl1, l2, l3との間のレイテンシはそれぞれ232ms, 51ms, 117msだった。
よって、ノードAのbinは"l2 l3 l1 : 0 1 2"となる。

疑問点

"l2 l3 l1 : 0 1 2"って値が出るのは分かったが、これをどうやってオーバレイネットワークに提供すんの？
→CANの場合の例では、二次元空間を適切な数に分割してそれぞれにランドマークの順序（組み合わせ）を割り当て、そこへjoinしにいけって書いてある。なるほど。