Progress Report Kenji Kaneda.

Presentation on theme: "Progress Report Kenji Kaneda."— Presentation transcript:

1 Progress Report Kenji Kaneda

2 Parallel SMP emulator Naïve implementation has been finished

3 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

4 Ad-Hoc Mobile Network Routing
Kenji Kaneda

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

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

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

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

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

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

11 Proactive Routing

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

13 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に到達

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

15 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

16 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

17 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

18 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

19 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

20 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

21 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

22 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

23 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

24 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

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

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

27 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

28 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

29 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

30 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

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

32 Reactive Routing

33 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

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

35 ルーティング表の構築 (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

36 ルーティング表の構築 (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

37 ルーティング表の構築 (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

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

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

40 Hierarchical Routing

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

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

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

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

45 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

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

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

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

49 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

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

51 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

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

53 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

54 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

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

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

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

58 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

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

60 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

61 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

62 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

63 Appendix

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