A Scalable Location Service for Geographic Ad Hoc Routing 2000 Jinyang Li John Jannotti Douglas S J De Couto David R Karger Robert Morris MIT Laboratory for Computer Science Presented by Nathan Farrington Overview aMotivation for Grid scalable routing for large ad hoc networks metropolitan area 1000s of nodes aProtocol Scalability The number of packets each node has to forward and the amount of state kept at each node grow slowly with the size of the network Current Routing Strategies aTraditional scalable Internet routing address aggregation hampers mobility aPro active topology distribution e g DSDV reacts slowly to mobility in large networks aOn demand flooded queries e g DSR too much protocol overhead in large networks Avg packets transmitted per node per second Flooding causes too much packet overhead in big networks Number of nodes Flooding based on demand routing works best in small nets Can we route without global topology knowledge Geographic Forwarding Scales Well a Assume each node knows its geographic location C s radio range A C B D F G E a A addresses a packet to G s latitude longitude a C only needs to know its immediate neighbors to forward packets towards G a Geographic forwarding needs a location service Possible Designs for a Location Service aFlood to get a node s location LAR DREAM excessive flooding messages aCentral static location server not fault tolerant too much load on central server and nearby nodes the server might be far away for nearby nodes or inaccessible due to network partition aEvery node acts as server for a few others good for spreading load and tolerating failures Desirable Properties of a Distributed Location Service aSpread load evenly over all nodes aDegrade gracefully as nodes fail aQueries for nearby nodes stay local aPer node storage and communication costs grow slowly as the network size grows GLS s spatial hierarchy level 0 level 1 level 2 level 3 All nodes agree on the global origin of the grid hierarchy 3 Servers Per Node Per Level sibling level 0 squares sibling level 1 squares sibling level 2 squares s n s s s s s s s s s is n s successor in that square Successor is the node with least ID greater than n Queries Search for Destination s Successors s n s s s Each query step visit n s successor at each level s s s s1 s2 s s3 location query path x GLS Update level 0 9 11 2 1 9 11 3 6 23 23 16 29 7 6 17 5 26 21 25 4 Invariant for all levels For node n in a square n s successor in each sibling square knows about n Base case Each node in a level 0 square knows about all other nodes in the same square 8 19 location table content GLS Update level 1 9 11 2 1 9 11 2 3 6 23 23 2 2 16 Invariant for all levels For node n in a square n s successor in each sibling square knows about n 29 7 6 17 5 26 21 25 4 location table content 8 19 location update GLS Update level 1 11 2 9 1 9 11 2 6 23 23 2 Invariant for all levels For node n in a square n s successor in each sibling square knows about n 3 2 16 29 7 6 17 26 21 5 25 4 8 19 location table content GLS Update level 2 1 11 2 9 1 9 11 2 6 23 23 2 Invariant for all levels For node n in a square n s successor in each sibling square knows about n 3 2 16 29 7 6 17 26 21 5 25 4 location table content 8 19 location update GLS Query 1 11 2 9 1 9 11 2 6 23 23 2 3 2 16 29 7 6 17 26 21 5 25 4 location table content 8 19 query from 23 for 1 Challenges for GLS in a Mobile Network aOut of date location information in servers aTradeoff between maintaining accurate location data and minimizing periodic location update messages Adapt location update rate to node speed Update distant servers less frequently than nearby servers Leave forwarding pointers until updates catch up Performance Analysis aHow aHow aHow aHow well does GLS cope with mobility scalable is GLS well does GLS handle node failures local are the queries for nearby nodes Simulation Environment aSimulations using ns with CMU s wireless extension IEEE 802 11 aMobility Model random way point with speed 0 10 m s 22 mph aArea of square universe grows with the number of nodes in the network Achieve spatial reuse of the spectrum aGLS level 0 square is 250m x 250m a300 seconds per simulation query success rate GLS Finds Nodes in Big Mobile Networks Biggest network simulated 600 nodes 2900x2900m 4 level grid hierarchy Number of nodes Failed queries are not retransmitted in this simulation Queries fail because of out of date information for destination nodes or intermediate servers Avg packets transmitted per node per second GLS Protocol Overhead Grows Slowly Number of nodes Protocol packets include GLS update GLS query reply Avg location table size Average Location Table Size is Small Number of nodes Average location table size grows extremely slowly with the size of the network Non uniform Location Table Size 2 Simulated universe 7 21 26 Node 3 is to be the location server for all other nodes 1 23 6 3 8 11 1 2 6 7 8 11 16 18 21 23 25 27 18 16 25 The complete Grid hierarchy of level 3 Possible solution dynamically adjust square boundaries GLS is Fault Tolerant Query success rate Measured query performance immediately after a number of nodes crash simultaneously 200 node networks Fraction of failed nodes Ratio of query path to src dst distance Query Path Length is proportional to the distance between source and destination Hop count between source and destination Performance Comparison between Grid and DSR aDSR Dynamic Source Routing Source floods route request to find the destination Query reply includes source route to destination Source uses source route to send data packets aSimulation scenario 2Mbps radio bandwidth CBR sources 4 128 byte packets second for 20 seconds 50 of nodes initiate over 300 second life of simulation Successfully delivered data Fraction of Data Packets Delivered Grid DSR Number of nodes Geographic forwarding is less fragile than source routing Why does DSR have trouble with 300 nodes Avg packets transmitted per node per second Protocol Packet Overhead DSR Grid Number of nodes DSR prone to congestion in big networks Sources must re flood queries to fix broken source routes These queries cause congestion Grid s queries cause less network load Queries are unicast not flooded Un routable packets are discarded at source when query fails Conclusion aGLS enables routing using geographic forwarding aGLS preserves the scalability of geographic forwarding aCurrent work Implementation of Grid in Linux http pdos lcs mit edu grid
View Full Document
Unlocking...