Sensor Net Routing CS525 Distributed Systems 03/03/2009 Presenters- Saurabh Nangia Paria MoinzadehA Review of Current Routing Protocols for Ad Hoc Wireless Networks Elizabeth M. Royer, Chai-KeongToh Presented by: Saurabh NangiaAd Hoc Routing Protocols Table Driven DSDV CGSR WRP Source Initiated On-Demand AODV DSR LMR TORA ABR SSROutline • Ad hoc Networks • Existing Routing Protocols ▫ Table Driven DSDV (CGSR) (WRP) ▫ Source Driven AODV DSR TORA (ABR) (SSR) • DiscussionIntroduction • Mobile wireless networks ▫ Infrastructured Networks Fixed & Wired Gateways Bridges – Base Station ▫ Infrastructureless Mobile Networks Alias: Ad Hoc Network No Fixed Router Movable nodes connecting dynamically in arbitrary mannerExisting Ad Hoc Routing Protocols • Classified in two main categories ▫ Table Driven Proactive Continuously evaluate routes Maintain up-to-date routing information ▫ Source Initiated (demand driven) Reactive Create route when desire Longer DelayAd Hoc Routing Protocols Table Driven DSDV CGSR WRP Source Initiated On-Demand AODV DSR LMR TORA ABR SSRDSDV : Destination Sequenced Distance Vector Routing • Based on Bellman-Ford Routing ▫ Addition: Freedom from loops using sequence number • Routes labeled with Sequence Number ▫ Assigned by destination ▫ Distinguishes old routes ▫ Avoids routing loops • Route with most recent sequence number used ▫ If same, use one with smaller metricDSDV : Destination Sequenced Distance Vector Routing • Two tables ▫ Routing table ▫ Incremental update table • Periodic Updates ▫ Full dump packets All available routing info ▫ Incremental packets Changed info since last full dumpDetour • Contribution of DSDV as compared to Distance VectorDistance Vector (Tables) C Dest. Next Metric …A A 1B B 0C C 2Dest. Next Metric …A A 0B B 1C B 31 2Dest. Next Metric …A B 3B B 2C C 0B A(A, 1) (B, 0) (C, 1) (A, 1) (B, 0) (C, 1) Distance Vector (Update) C Dest. Next Metric …A A 1B B 0C C 1Dest. Next Metric …A A 0B B 1C B 3 211Dest. Next Metric …A B 3 2B B 1C C 0B A B broadcasts the new routing information to his neighbors Routing table is updated(D, 0) (A, 2) (B, 1) (C, 0) (D, 1) (A, 1) (B, 0) (C, 1) (D, 2) Distance Vector (New Node) C 1 1B A D 1broadcasts to update tables of C, B, A with new entry for D Dest. Next Metric …A B 2B B 1C C 0D D 1Dest. Next Metric …A A 1B B 0C C 1D C 2Dest. Next Metric …A A 0B B 1C B 2D B 3Distance Vector (Broken Link) C 1 1B A D 1Dest.c Next Metric …… … …D C 2Dest. Next Metric …… … …D B 3Dest. Next Metric …… … …D B 1Dest. Next Metric …… … …D D ∞(D, 2) (D, 2) Distance Vector (Loops) C 1 1B A D 1Dest. Next Metric …… … …D B 3Dest. Next Metric …… … …D C 2Dest. Next Metric …… … …D B 3(D,2) (D,4) (D,3) (D,5) (D,2) (D,4) Distance Vector (Count to Infinity) C 1 1B A D 1Dest. Next Metric …… … …D B 3, 5, …Dest. Next Metric …… … …D B 3, 5, …Dest.c Next Metric …… … …D C 2, 4, 6…Coming back to DSDV(D, 0, D-000) DSDV (New Node) C B A D Dest. Next Metric Seq. A A 0 A-550 B B 1 B-104 C B 2 C-590 Dest. Next Metric Seq. A A 1 A-550 B B 0 B-104 C C 1 C-590 Dest. Next Metric Seq. A B 2 A-550 B B 1 B-104 C C 0 C-590 D D 1 D-000 1. D broadcast for first time Send Sequence number D-000 2. Insert entry for D with sequence number D-000 Then immediately broadcast own table(A, 2, A-550) (B, 1, B-102) (C, 0, C-592) (D, 1, D-000) (A, 2, A-550) (B, 1, B-102) (C, 0, C-592) (D, 1, D-000) DSDV (New Node cont.) C B A D Dest. Next Metric Seq. A A 1 A-550 B B 0 B-102 C C 1 C-592 D C 2 D-000 Dest. Next Metric Seq. A A 0 A-550 B B 1 B-104 C B 2 C-590 Dest. Next Metric Seq. A B 2 A-550 B B 1 B-102 C C 0 C-592 D D 1 D-000 ……… ………3. C increases its sequence number to C-592 then broadcasts its new table. 4. B gets this new information and updates its table…….(D, 2, D-100) (D, 2, D-100) DSDV (no loops, no count to infinity) C B A D Dest.c Next Metric Seq. … … …D C 2 D-100 Dest. Next Metric Seq. … … …D B 3 D-100 Dest. Next Metric Seq. … … …D D ∞D-101 1. Node C detects broken Link: -> Increase Seq. Nr. by 1 (only case where not the destination sets the sequence number -> odd number) 2. B does its broadcast -> no affect on C (C knows that B has stale information because C has higher seq. number for destination D) -> no loop -> no count to infinity(D, ∞, D-101) (D, ∞, D-101) DSDV (Immediate Advertisement) C B A D Dest.c Next Metric Seq. … … …D C 3 D-100 Dest. Next Metric Seq. … … …D B 4 D-100 Dest. Next Metric Seq. … … …D B 1 D-100 Dest. Next Metric Seq. … … …D D 1 D-100 D D ∞D-101 1. Node C detects broken Link: -> Increase Seq. Nr. by 1 (only case where not the destination sets the sequence number -> odd number) 3. Immediate propagation B to A: (update information has higher Seq. Nr. -> replace table entry) 2. Immediate propagation C to B: (update information has higher Seq. Nr. -> replace table entry) Dest.c Next Metric Seq. … … … ... D C 2 D-100 D C ∞D-101 Dest. Next Metric Seq. … … … ... D B 3 D-100 D B ∞D-101DSDV Discussion: • Disadvantage: ▫ Periodic updates independent of network change Solution: Dynamic periods (?) ▫ Fluctuating paths Solution: Settling time delays ▫ No sleeping nodes • Applications Memory & Power vs LatencyAd Hoc Routing Protocols Table Driven DSDV CGSR WRP Source Initiated On-Demand AODV DSR LMR TORA
View Full Document
Unlocking...