exor sigcomm

60 %
40 %
Information about exor sigcomm
Entertainment

Published on December 23, 2007

Author: Columbia

Source: authorstream.com

Opportunistic Routing in Multi-hop Wireless Networks:  Opportunistic Routing in Multi-hop Wireless Networks Sanjit Biswas and Robert Morris MIT CSAIL http://pdos.csail.mit.edu/roofnet/ ExOR: a new approach to routing in multi-hop wireless networks:  ExOR: a new approach to routing in multi-hop wireless networks Dense 802.11-based mesh Goal is high-throughput and capacity 1 kilometer Initial approach: Traditional routing:  packet packet packet Initial approach: Traditional routing Identify a route, forward over links Abstract radio to look like a wired link src A B dst C Radios aren’t wires:  Radios aren’t wires Every packet is broadcast Reception is probabilistic 1 2 3 4 5 6 1 2 3 6 3 5 1 4 2 3 4 5 6 1 2 4 5 6 src A B dst C ExOR: exploiting probabilistic broadcast:  packet packet packet packet packet packet ExOR: exploiting probabilistic broadcast src A B dst C packet packet packet Decide who forwards after reception Goal: only closest receiver should forward Challenge: agree efficiently and avoid duplicate transmissions Outline:  Outline Introduction Why ExOR might increase throughput ExOR protocol Measurements Related Work Why ExOR might increase throughput (1):  Why ExOR might increase throughput (1) Best traditional route over 50% hops: 3(1/0.5) = 6 tx Throughput  1/# transmissions ExOR exploits lucky long receptions: 4 transmissions Assumes probability falls off gradually with distance src dst N1 N2 N3 N4 75% 50% N5 25% Why ExOR might increase throughput (2):  Why ExOR might increase throughput (2) Traditional routing: 1/0.25 + 1 = 5 tx ExOR: 1/(1 – (1 – 0.25)4) + 1 = 2.5 transmissions Assumes independent losses N1 src dst N2 N3 N4 25% 25% 25% 25% 100% 100% 100% 100% Outline:  Outline Introduction Why ExOR might increase throughput ExOR protocol Measurements Related Work ExOR batching:  ExOR batching Challenge: finding the closest node to have rx’d Send batches of packets for efficiency Node closest to the dst sends first Other nodes listen, send remaining packets in turn Repeat schedule until dst has whole batch src N3 dst N4 tx: 23 tx: 57 -23  24 tx:  8 tx: 100 tx: 0 tx:  9 N1 N2 Reliable summaries:  Reliable summaries Repeat summaries in every data packet Cumulative: what all previous nodes rx’d This is a gossip mechanism for summaries src N1 N2 N3 dst N4 tx: {1, 6, 7 ... 91, 96, 99} tx: {2, 4, 10 ... 97, 98} summary: {1,2,6, ... 97, 98, 99} summary: {1, 6, 7 ... 91, 96, 99} Priority ordering:  Priority ordering Goal: nodes “closest” to the destination send first Sort by ETX metric to dst Nodes periodically flood ETX “link state” measurements Path ETX is weighted shortest path (Dijkstra’s algorithm) Source sorts, includes list in ExOR header Details in the paper src N1 N2 N3 dst N4 Using ExOR with TCP:  Using ExOR with TCP Node Proxy ExOR Gateway Web Proxy Client PC Web Server Batching requires more packets than typical TCP window Outline:  Outline Introduction Why ExOR might increase throughput ExOR protocol Measurements Related Work ExOR Evaluation:  ExOR Evaluation Does ExOR increase throughput? When/why does it work well? 65 Roofnet node pairs:  65 Roofnet node pairs 1 kilometer Evaluation Details:  Evaluation Details 65 Node pairs 1.0MByte file transfer 1 Mbit/s 802.11 bit rate 1 KByte packets ExOR: 2x overall improvement :  ExOR: 2x overall improvement Median throughputs: 240 Kbits/sec for ExOR, 121 Kbits/sec for Traditional Throughput (Kbits/sec) 1.0 0.8 0.6 0.4 0.2 0 0 200 400 600 800 Cumulative Fraction of Node Pairs ExOR Traditional 25 Highest throughput pairs:  25 Highest throughput pairs Node Pair Throughput (Kbits/sec) 0 200 400 600 800 1000 ExOR Traditional Routing 1 Traditional Hop 1.14x 2 Traditional Hops 1.7x 3 Traditional Hops 2.3x 25 Lowest throughput pairs:  25 Lowest throughput pairs Node Pair 4 Traditional Hops 3.3x Longer Routes Throughput (Kbits/sec) 0 200 400 600 800 1000 ExOR Traditional Routing ExOR uses links in parallel:  ExOR uses links in parallel Traditional Routing 3 forwarders 4 links ExOR 7 forwarders 18 links ExOR moves packets farther:  ExOR moves packets farther ExOR average: 422 meters/transmission Traditional Routing average: 205 meters/tx Fraction of Transmissions 0 0.1 0.2 0.6 ExOR Traditional Routing 0 100 200 300 400 500 600 700 800 900 1000 Distance (meters) Future Work:  Future Work Choosing the best 802.11 bit-rate Cooperation between simultaneous flows Coding/combining Related work:  Related work Relay channels [Van der Meulen][Laneman+Wornell] Flooding in meshes / sensor nets [Peng][Levis] Multi-path routing [Ganesan][Haas] Selection Diversity [Miu][Roy Chowdhury][Knightly][Zorzi] Summary:  Summary ExOR achieves 2x throughput improvement ExOR implemented on Roofnet Exploits radio properties, instead of hiding them Thanks!:  Thanks! For more information and source code: http://pdos.csail.mit.edu/roofnet/

Add a comment

Related presentations

Related pages

exor-sigcomm - Ace Recommendation Platform - 1

Related Contents; ExOR; exor-sigcomm; exor-sigcomm; Recommended Courses; Northern Virginia Community College - Manassas Campus ITEC 1756; Florida Community ...
Read more

ExOR: Opportunistic Multi-Hop Routing for Wireless Networks

ExOR: Opportunistic Multi-Hop Routing for Wireless Networks Sanjit Biswas and Robert Morris M.I.T. Computer Science and Artifical Intelligence Laboratory
Read more

ExOR - Association for Computing Machinery

ExOR increases a connection's throughput while using no more network capacity than traditional routine.ExOR's ... ACM SIGCOMM Computer Communication ...
Read more

dblp: ACM SIGCOMM Conference 2005 - dblp: computer science ...

Bibliographic content of ACM SIGCOMM Conference 2005. ... Proceedings of the ACM SIGCOMM 2005 Conference on Applications, ... ExOR: opportunistic multi ...
Read more

ExOR (wireless network protocol) - Wikipedia, the free ...

Extremely Opportunistic Routing (ExOR) is a combination of routing protocol and media access control for a wireless ad hoc network, invented by Sanjit ...
Read more

Trading Structure for Randomness in Wireless Opportunistic ...

acm sigcomm. About; Awards; Join; News; Events; Publications; Information for: Authors; Educators; Conference Attendees; ... ExOR, ties the MAC with ...
Read more

ExOR: Opportunistic Multi-hop Routing for Wireless Networks

ExOR: Opportunistic Multi-hop Routing for Wireless Networks on ResearchGate, the professional network for scientists.
Read more

Opportunistic Routing in Multi-hop Wireless Networks

ExOR: a new approach to routing in multi-hop wireless networks Ł Dense 802.11-based mesh Ł Goal is high-throughput and capacity 1 kilometer
Read more

PDOS Publications - Massachusetts Institute of Technology

PDOS Publications - Massachusetts Institute of Technology ... 2016
Read more

Opportunistic Routing in Multi-Hop Wireless Networks

Opportunistic Routing in Multi-Hop Wireless Networks Sanjit Biswas and Robert Morris MIT Laboratory for Computer Science {biswas,rtm}@lcs.mit.edu
Read more