DHT in MANET その2
先に，DHTのアルゴリズム - WebLab.otaあたりを読んで，DHTのアルゴリズムを把握しておくと分かりが良いかも．
DHTを使ったアプリケーションではなく，オーバレイネットワークの構築手法っぽいもののまとめ
VRR（Virtual Ring Routing）
- 2006
Chord 環を利用しており，各ノードがノードID の近いノードを隣人表として所持し，ID 空間上で近いノードID を順番に辿ることでID のみによる経路選択法を実現している．
また，ID 空間上の隣人がノードの通信範囲外にある場合には，マルチホップ通信による隣人までの経路を所持することで対応している．
しかしながら，ノード数の増加に伴いID 空間も大きくなるため，ノード数が大きい場合には隣人までのホップ数が増加する．
（迂回経路を用いたドロネーネットワークの提案と検討）
- Chordのfingerテーブルだとこんな感じだけど，VRRの経路表は下図みたいな感じになるらしい．
- 保持する経路表は一つでいい（リンク層に実装してるから）
- link layerに直接実装してる
- ルーティングテーブルを見ても分かるけれど，通常のDHTが保証する探索効率（O(logN)）を保証しない．
MADPastry
- 2005
- PastryをそのままMANETに利用すると左図みたいに効率がわりぃ
- 物理ネットワークを考慮せずにオーバレイネットワークのトポロジを構築するから
- →なので物理ネットワークを考慮してノードIDを割り振ろう
- Random Landmarking(RLM)なるアルゴリズムを利用して右図みたいに効率よくする
SSR（Scalable Source Routing）
- 2005
- 維持する経路表とかが少なくて済む様子→そーゆーハード的な制約があるセンサノードなんかに使うらしい
- Chord likeな環状ハッシュ空間を使う
- それぞれのノードはChordでいうところのSuccessor Listを保持するらしい
- Successor List は,自身のハッシュ値よりも大きく，最も近いノード (次ノード) への経路
- 例えば，ノード1からノード42にパケットを送りたい時は
- ノード1は物理ネットワークで隣接しているノードから（この場合，17か13か88），一番目的ノードに近いノード（この場合17）を選んで受け渡す．
- 一番目的ノードに近いノードの計算方法：42-17=25 < 42-13=29 < 88-42=46
- 同じようにノード17は隣接ノードから（19か32），目的ノードに近いノード（32）を選んで受け渡す．
- ノード32の隣接ノードには，目的ノードへ接近できるノードが無い
- ので，自身のハッシュ値より大きく，最も近いノード（つまり，39）に受け渡す．
- ノード39は，次ノード（つまり42）への経路情報を保持しているはずなので，目的ノードにパケットが受け渡せる．（完了）
- ノード1は物理ネットワークで隣接しているノードから（この場合，17か13か88），一番目的ノードに近いノード（この場合17）を選んで受け渡す．
