Transcript ppt1
CS 15-849E: Wireless Networks (Spring 2006) Ad Hoc Routing Discussion Leads: Abhijit Deshmukh Sai Vinayak Srinivasan Seshan Dave Andersen Papers “Outdoor Experimental Comparison of Four Ad Hoc Routing Algorithms” Gray, Dubrovsky, Masone, Kotz, Fiske, McGrath, Newport, Liu, Yuan “A Performance Comparison of Multi-Hop Wireless Ad Hoc Network Routing Protocols” Broch, Maltz, Johnson, Hu, Jetcheva “Link-level Measurements from an 802.11b Mesh Network” Aguayo, Bicket, Biswas, Judd, Morris Outline • Motivation • Outdoor Experimental Comparison • • • • APRL ODMRP AODV STARA • Performance Comparison • • • • DSDV TORA DSR AODV • Link-level Measurements, Mesh Networks • RoofNet • Temporal and Spatial Variation • Take Aways • Q&A Motivation • Infrastructureless Networks • Ad Hoc Routing Algorithms? • Issues coupled with Wireless Ad Hoc? • • • • • Dynamic Nature Limited Transmission Range Node as a router No Maintenance Tradeoff: Link state maintenance & Messaging complexity Ad Hoc Network Routing Protocols AdHoc Routing Algorithms (1) • • • • APRL STARA AODV ODMRP Proactive APRL Reactive STARA AODV ODMRP APRL • • • • Proactive Routing Periodic Beaconing Ping Destination Via Neighbor (PDVN) Features • Loopless routing • Any path (not necessarily the shortest) STARA • Proactive Scheme • Periodic broadcast of neighborhood probe packets NP and NP_ACKs • Probabilistically chooses neighbor thru which to route packet • First uniform, then based on end to end latency • Sends dummy data packets (DDPS) to update latency information of alternate routes AODV • Reactive Scheme • Route request (RREQ) packet to explore route to destination • Route response (RREP) along reverse route • Link failure detection? • Periodic Hello messages • Link layer detection ODMRP • • • • • Reactive routing protocol Route establishment Similar to AODV Sender broadcasts JoinQuery Interested parties respond with JoinReplies Sender piggybacks data packet along with JoinQuery Outdoor Evaluation-Experimental Setup • All 4 algos implemented at the user level • Apps use virtual interface, Routing algos use physical interface • UDP Traffic + Multicast IP • Traffic Generator • Packet Number + sizes 2 Gaussian Distributions • Delay b/w packet streams 2 Exponential Distributions • Destination Laptops 1 Uniform Distribution Analysis • Message Delivery Ratio • Communication Efficiency • Hop Count Analysis (Contd.) • Zero Hop Failures • Stara-S 88% • APRL 63% • AODV 25% Final Verdict • AODV • Good in limited bandwidth or energy resources • OMDRP • If bandwidth and energy resources are plentiful & data packets are small and reliability is crucial • Reactive is better than proactive • Tradeoff in AD-HOC algorithms • Efficiency vs. Reliability DSDV (Destination-Sequenced Distance Vector) • Distance Vector Routing Protocol • Tag Route with Sequence Number • Updates • Periodically • Infinite-metric route • DSDV vs. DSDV-SQ • Change == new metric • Triggered update == New sequence number • Overhead vs. packet delivery ratio DSDV (Destination-Sequenced Distance Vector) • Advantages • loop-free fewest-hop path • Disadvantages • Periodic updates • Maintaining routes in the presence of mobility • Route info. may be expensive and unnecessary TORA (Temporally Ordered Routing Algorithm) • Highly adaptive, loop-free distributed algorithm • Link-reversal • Maintain a mesh • Local Adaptation • Key Design Concept • localization of control messages to a very small set of nodes near the occurrence of a topological change. • Three basic steps • Route creation • Route maintenance • Route erasure Link Reversal A B F C E G Represents a link that was reversed recently D Any node, other than the destination, that has no outgoing links reverses all its incoming links. Node G has no outgoing links Link Reversal A B F C E G D Now all nodes (other than destination D) have an outgoing link TORA • QUERY packet propagation • UPDATE packet • subsequent height increase of neighbors • CLEAR packet • Incase of a network partition TORA • Advantages • Loop free paths • Establish routes quickly, before topology changes • Able to detect network partitions very quickly • Disadvantages • Temporary oscillations (count to infinity type) • Needs synchronization DSR (Dynamic Source Routing) • Source Routing • On-demand • Two mechanisms • Route Discovery • ROUTE REQUEST (propagating , non-propagating) • Route Maintenance DSR (Dynamic Source Routing) Route RouteRequest Reply DSR (Dynamic Source Routing) • Advantages • Reactive: only active routes • Route caching : reduce route discovery overhead • Disadvantages • Packet header size • Collisions between route requests and route reply? Evaluation • DSR vs. AODV-LL • Similar shape, yet AODV has greater overhead? • Propagation of route discovery packets to all nodes • 2200 route discoveries • DSR: 950 non-propagating + 300 propagating • DSDV-LL : 110,000 ROUTE REQUEST Evaluation • TORA • Congestive Collapse • Positive feedback loop • MAC-layer collisions Evaluation • DSDV-SQ • Constant Overhead • Periodic update with new sequence number Link Level Measurements in Mesh Networks • Analyze cause of packet loss • Neighbor Abstraction • Ability to hear control packets or No Interference • Strong correlation between BER and S/N • RoofNet pairs communicate • At intermediate loss rates • Temporal Variation • Spatial Variation Roofnet Node Map 1 kilometer Typical Rooftop View A Roofnet Self-Installation Kit Antenna ($65) 50 ft. Cable ($40) 8dBi, 20 degree vertical Low loss (3dB/100ft) Computer ($340) Miscellaneous ($75) 533 MHz PC, hard disk, CDROM Chimney Mount, Lightning Arrestor, etc. 802.11b card ($155) Software (“free”) Engenius Prism 2.5, 200mW Our networking software based on Click Total: $685 Takes a user about 45 minutes to install on a flat roof RoofNet Implies failure of Neighbor Abstraction RoofNet (Spatial Distribution of Loss Rates) Reasons for Differences ? • Different Antenna Heights • Multi-path fading RoofNet (Effect of Signal-to-Noise Ratio) • High S/N == high delivery probabilities • Range of S/N values > 3 db RoofNet (Effect of Power Level) • 10 40 milliwatts doubles delivery RoofNet (Effect of Multi-Path) • Significant losses inter-node distance • Reflected signal delayed by a microsecond • Approx 300 meters Q&A