Progress Report Kenji Kaneda

Parallel SMP emulator Naïve implementation has been finished

Demo Boot Execution of simple programs Linux SMP on a dual-processor machine Execution of simple programs Type “yes > /dev/null” three times Processes are distributed over two CPUs correctly

Ad-Hoc Mobile Network Routing Kenji Kaneda

Ad-Hoc Mobile Networkとは? E.g.) rescue operation, meeting, battle 個々のノードが自律して動作 近接ノード間のみ通信可能 E C A F B D

Ad-Hoc Mobile Network Routing (1/2) 他ノードを中継することにより、　　　　　　　　　　　　遠くのノードにメッセージを送ることが可能になる E C A F source B D destination

Ad-Hoc Mobile Network Routing (2/2) Internet routingと異なり ネットワークトポロジーが頻繁に動的に変化し、 ノード名が階層的に割り当てられていない 　ことを考慮しなければいけない 133.11.12.101 E B A C D 133.11.12.1 133.11.12.2 133.11.12.3 Ad-hoc mobile network routing Internet routing

Routing Algorithms Many algorithms have been proposed ABR SSR LMR TORA DSR AODV WRP DSDV CGSR …

Classification of Algorithms Proactive vs. Reactive Proactive: ルーティング表を常に最新の状態に保持 Reactive: メッセージ送信時にルーティング表を構築 Flat vs. Hierarchical

Rest of This Talk Proactive Routing Reactive Routing DSDV Reactive Routing AODV Hierarchical (Proactive) Routing Dominating-set based DSDV Landmark

Proactive Routing

Proactive Routing Destination Sequenced Distance Vector (DSDV) Clustered Gateway Switch Routing (CGSR) The Wireless Routing Protocol (WRP) …

DSDV (1/2) 各ノードがBroadcastを行うことにより、 ルーティング表が構築される B E t w s u A D y v x tを経由してAに到達 wを経由してAに到達 B E t sを経由してAに到達 w s u A D y v x C F vを経由してAに到達 xを経由してAに到達

DSDV (2/2) 各ノードが ブロードキャストを行うことにより、ルーティング表を構築する リンクの追加・削除が発生した時に ルーティング表が更新された時に 定期的に ブロードキャストを行うことにより、ルーティング表を構築する

Routing Table Updateの例1 新しくリンクが追加された場合 Dest. Next Metric A 1 B C ? ∞ Dest. Next Metric A B 1 C ? ∞ Dest. Next Metric A ? ∞ B C B A C

Routing Table Updateの例1 AとCは自分のルーティング表をお互いに送信 送られてきた情報をもとに、ルーティング表を更新 Dest. Next Metric A 1 B C ? ∞ Dest. Next Metric A B 1 C Dest. Next Metric A B 1 C ? ∞ Dest. Next Metric A ? ∞ B C Dest. Next Metric A 1 B 2 C B A C

Routing Table Updateの例1 Aは自分のルーティング表が更新されたので、再度broadcast Dest. Next Metric A 1 B C 2 Dest. Next Metric A 1 B C ? ∞ Dest. Next Metric A B 1 C Dest. Next Metric A 1 B 2 C B A C

Routing Table Updateの例2 リンクが削除された場合 Dest. Next Metric A 1 B C 2 Dest. Next Metric A B 1 C Dest. Next Metric A 1 B 2 C B A C

Routing Table Updateの例2 A, Cは自分のルーティング表を更新する A, Cはbroadcastを行う ※ Bも、Cに到達不可能となる（Aを経由していたので） Dest. Next Metric A 1 B C ? ∞ Dest. Next Metric A 1 B C 2 Dest. Next Metric A B 1 C Dest. Next Metric A B 1 C ? ∞ Dest. Next Metric A ? ∞ B C Dest. Next Metric A 1 B 2 C B A C

Routing Table Updateの例3 リンクが削除された場合 Dest. Next Metric A 1 B C Dest. Next Metric A B 1 C Dest. Next Metric A 1 B C B A C

Routing Table Updateの例3 A、Cは自分のルーティング表を更新する A,Cはbroadcastを行う ※ Bは、AとCに直接到達できるので、ルーティング表は更新されない Dest. Next Metric A 1 B C Dest. Next Metric A B 1 C ? ∞ Dest. Next Metric A B 1 C Dest. Next Metric A 1 B C Dest. Next Metric A ? ∞ B 1 C B A C

Routing Table Updateの例3 Bは定期的に自分のルーティング表をbroadcastする ※ A,Cのルーティング表が更新され、B経由でお互いに到達可能になる Dest. Next Metric A 1 B C Dest. Next Metric A B 1 C 2 Dest. Next Metric A B 1 C ? ∞ Dest. Next Metric A ? ∞ B 1 C Dest. Next Metric A B 2 1 C B A C

Counting-to-Infinity Problem Network topologyの変化のタイミングによって、loopが発生してしまう AはBを経由してCに到達可能 BはAを経由してCに到達可能 Dest. Next Metric A 1 B C 2 Dest. Next Metric A 1 B C 2 Dest. Next Metric A B 1 C Dest. Next Metric A B 1 C 3 Dest. Next Metric A 1 B 2 C B A C

Counting-to-Infinityの例 AC間のリンクが切れる A, Cは自分のルーティング表を更新する Bが定期的にbroadcastを行う A, Bはルーティング表の更新を繰り返す Dest. Next Metric A 1 B C 4 Dest. Next Metric A 1 B C 4 Dest. Next Metric A 1 B C 6 Dest. Next Metric A 1 B C 2 Dest. Next Metric A B 1 C 3 Dest. Next Metric A B 1 C 5 Dest. Next Metric A B 1 C Dest. Next Metric A B 1 C ? ∞ Dest. Next Metric A ? ∞ B 1 C Dest. Next Metric A 1 B C B A C

Counting-to-Infinity Problem もっと複雑なloopが発生しうる  sequence numberを導入することにより、loopを回避する

Sequence numberとは ルーティング表の各エントリに付加される 単調に増加する Dest. Next Metric Seq. A 4 B 1 2 C 3 A

Sequence numberの増加 (1/2) Dest. Next Metric Seq. A 4 B 1 C 2 Dest. Next Metric Seq. A 2 B 1 4 C B A C

Sequence numberの増加 (2/2) Dest. Next Metric Seq. A 2 B 1 4 C ? ∞ 3 Dest. Next Metric Seq. A 2 B 1 4 C B A C

Route Selectionの基準 Seq. の高い経路を優先的に選択 Seq.が等しい時には、Metricの小さいもの A B A 2 Dest. Next Metric Seq. A 2 B 1 4 C ? ∞ 3 D G 6 Dest. Next Metric Seq. A 2 B 1 4 C ? ∞ 3 D 5 Dest. Next Metric Seq. A 2 B 1 4 C D G 6 Dest. Next Metric Seq. A 1 2 B 4 C ? ∞ 3 D F A B

Loop回避例 AC間のリンクが切れる A, Cは自分のルーティング表を更新する Bが定期的にbroadcastを行う ※ Seq.の小さいエントリなので無視される Dest. Next Metric Seq. A 1 2 B C Dest. Next Metric Seq. A 1 2 B C ? ∞ 3 Dest. Next Metric Seq. A 2 B 1 C ? ∞ 3 Dest. Next Metric Seq. A 2 B 1 C B A C

Complexity Time complexity Communication Complexity where O(d) O(N) N = # of nodes d = network diameter

Reactive Routing

Reactive Routing Ad hoc On-Demand Distance Vector Routing (AODV) Dynamic Source Routing (SOR) Temporally Ordered Routing Algorithm (TORA) … The landmark hierarchy: a new hierarchy for routing in very large networks P. F. Tsuchiya  The MITRE Corporation SponsorsSIGCOMM: ACM

AODV On-demandにルーティング表を構築する 定期的なbroadcastを必要としない ※メッセージ送信の際のlatencyは増大する

ルーティング表の構築 (1/3) ~ Reverse Path Setup ~ AB B ACD ACDF A D F source destination C AC E ACE

ルーティング表の構築 (2/3) ~ Forward Path Setup ~ AB B FD ACD ACDF A D F source destination C FDCA AC E FDC ACE

ルーティング表の構築 (3/3) ~ Cacheの利用 ~ AからFの経路を計算したときに蓄えられた情報を利用 AB B FD ACD ACDF A D F source destination C FDCA AC E FDC ACE

Path Maintenance Sequence numberを利用することにより、loopを回避 一定時間以上経過した経路情報は削除 DSDVとほぼ同様 一定時間以上経過した経路情報は削除 BroadcastごとにuniqueなIDを割り振る すでに受け取ったメッセージを再度broadcastするのを避けるため

Complexity Time complexity Communication Complexity where O(2d) O(2N) N = # of nodes d = network diameter

Hierarchical Routing

Hierarchical Routing 階層構造を利用して などを実現する ルーティング表の縮小・集約 メッセージ数の削減 133.11.12.101 133.11.9.11 133.11.12.1 133.11.12.2 133.11.12.3 133.11.9.31 133.11.9.11 133.11.12.3

Hierarchical Routing Dominating-set based DSDV Landmark Routing Clustered Gateway Switch Routing (CGSR) …

Hierarchical Routing 各ノードは自律的に動作しながら階層構造を構築 各ノードは、ネットワークトポロジーの変化に応じて、動的に階層構造を再構築する ※ Internet routingならば、階層構造の構築は、ほぼ手動（ネットワーク管理者の作業）

Dominating-set based DSDV 2-level hierarchy Gatewayとnon-gatewayが存在 Gateway間では、shortest pathを計算 Non-gatewayは、隣接gatewayのうちのどれかを中継してメッセージを配送 gat gateway non-gateway

Gatewayはどうなるべきか？ Minimum Connected Dominating set (MCDS)が望ましい Given a graph G=(V,E), U (⊆V) is a connected dominating set if ∀v ∈ V–U, ∃u ∈ U, uv ∈ E and the subgraph of G induced by U is connected

approximate MCDSを求める 分散アルゴリズム 各ノードは、自分から2hop先のノードまでを把握する 以下の条件を満たすノードuをgatewayとする ∃v,w ∈ N, (uv ∈ E) ∧ (uw ∈ E) ∧ (vw ∈ E) where N = { v | uv ∈ E } u v w

Landmark Routing Landmarkと呼ばれるノードによって階層構造を構築

Landmark Landmark of radius r　 = a node for which all nodes within r hops contain a routing entry vへの経路を知っているノード v Landmark of radius 2

Hierarchy of Landmarks (1/3) Hierarchy Level 各Landmarkに与えられる0からHまでの値 levelの高いLandmarkほどradiusも大きい ※ Li をlevel iのLandmarkの集合とする ※ ri(v)をlevel iのLandmark vのradiusとする Level 2 Level 1 Level 0

Hierarchy of Landmarks (2/3) [条件1] 全てのノードは、level 0 のLandmark

Hierarchy of Landmarks (3/3) [条件2] 全てのlevel i のLandmark　vにおいて、　　　　 ri(v)ホップ中にlevel i+1 のLandmarkが　　　　少なくとも一つの存在 Level 1 のLandmark Level 0 のLandmark v u r1(u) r0(v) Level 2 のLandmark w

Routing Table ノードvは、以下のノードへの経路をもつ r0(v)内に位置する全てのlevel 0のLandmark … Level 1 のLandmark Level 0 のLandmark v u r1(u) r0(v) Level 2 のLandmark w

Landmark Address 各ノードにnHnH-1…n0というアドレスを割り当てる ただし ni (0 ≦ i ≦ H)はlevel iのLandmarkの名前 n0は自分の名前 niは、ni-1からri-1(ni-1)ホップ中に存在 E.g.) vのLandmark addressは、wuv The Landmark represented by each address component must be within the radius of the Landmark represented by the next lower address component

Routing in a Landmark Hierarchy 宛先をLandmark addressで指定 Landmark addressの下位からみて、経路の分かるノードに転送 Level 1 のLandmark Level 0 のLandmark u,vへの経路が不明なのでwに転送 v u vへの経路が不明なのでuに転送 Level 2 のLandmark source w

Dynamic Algorithms in Landmark Routing (1/4) 動作の概要 Electionにより階層構造を動的に構築 Distance vector routingで経路を計算 ノード名をLandmark addressにmapping

Dynamic Algorithms in Landmark Routing (2/4) Electionにより階層構造を動的に構築

Dynamic Algorithms in Landmark Routing (3/4) Distance vector routingで経路を計算 Level iのLandmarkであるノードvに関する情報は、ri(v)だけ伝播される vへの経路を知っているノード v Level i のLandmark ri(v)=2

Dynamic Algorithms in Landmark Routing (4/4) ノード名をLandmark addressにmapping ノード名からLandmark　addressへのハッシュ関数Hを利用して、分散管理 vのLandmark addressは、Landmark addressがH(v)であるノードが管理 wのLandmark address = H(v) vにメッセージを送信したい. そのためにvのlandmark addressを知っている必要がある w 自分のLandmarkを登録 u vのLandmark Addressを問い合わせる v vのLandmark address =xyv

Summary Ad-hoc mobile network routing DSDV AODV Dominating-set based DSDV Landmark

References (1/3) “A Review of Current Routing Protocols for Ad-Hoc Mobile Wireless Networks” E. Royer and C-K. Toh IEEE Personal Communications Magazine 1999

References (2/3) “Highly Dynamic Destination-Sequenced Distance-Vector Routing (DSDV) for Mobile Computers” Charles Perkins and Pravin Bhagwat SIGCOMM 1994 Ad hoc On-Demand Distance Vector Routing Charles Perkins and Elizabeth M Mobile Computing Systems and Applications 1999

References (3/3) “The Landmark Hierarchy: a new hierarchy for routing in very large networks” P.F. Tsuchiya Communication Review, vol. 18, No. 4 1998 “A Dominating-Set-Based Routing Scheme in Ad Hoc Wireless Networks” Jie Wu and Hailan Li Telecomm. Systems, A special issue on Wireless Networks 2001

Appendix

Peer-to-Peer Routing Algorithms E.g.) Pastry, CAN, Chord Ad-hoc mobile networkと異なり 各ノードはお互いに直接通信可能 厳密にルーティングを行う必要は必ずしもない 例）ある特定のファイルをもつノードのうちの　　　　　　　　　　　　　　　　　　どれかに届けば十分