logging in or signing up exor sigcomm Columbia Download Post to : URL : Related Presentations : Share Add to Flag Embed Email Send to Blogs and Networks Add to Channel Uploaded from authorPOINTLite Insert YouTube videos in PowerPont slides with aS Desktop Copy embed code: (To copy code, click on the text box) Embed: URL: Thumbnail: WordPress Embed Customize Embed The presentation is successfully added In Your Favorites. Views: 277 Category: Entertainment License: All Rights Reserved Like it (0) Dislike it (0) Added: December 23, 2007 This Presentation is Public Favorites: 0 Presentation Description No description available. Comments Posting comment... Premium member Presentation Transcript 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 kilometerInitial 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 CRadios 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 CExOR: 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 WorkWhy 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 WorkExOR 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 N2Reliable 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 N4Using ExOR with TCP: Using ExOR with TCP Node Proxy ExOR Gateway Web Proxy Client PC Web Server Batching requires more packets than typical TCP windowOutline: Outline Introduction Why ExOR might increase throughput ExOR protocol Measurements Related WorkExOR 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.3x25 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 linksExOR 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/ You do not have the permission to view this presentation. In order to view it, please contact the author of the presentation.
exor sigcomm Columbia Download Post to : URL : Related Presentations : Share Add to Flag Embed Email Send to Blogs and Networks Add to Channel Uploaded from authorPOINTLite Insert YouTube videos in PowerPont slides with aS Desktop Copy embed code: (To copy code, click on the text box) Embed: URL: Thumbnail: WordPress Embed Customize Embed The presentation is successfully added In Your Favorites. Views: 277 Category: Entertainment License: All Rights Reserved Like it (0) Dislike it (0) Added: December 23, 2007 This Presentation is Public Favorites: 0 Presentation Description No description available. Comments Posting comment... Premium member Presentation Transcript 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 kilometerInitial 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 CRadios 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 CExOR: 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 WorkWhy 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 WorkExOR 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 N2Reliable 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 N4Using ExOR with TCP: Using ExOR with TCP Node Proxy ExOR Gateway Web Proxy Client PC Web Server Batching requires more packets than typical TCP windowOutline: Outline Introduction Why ExOR might increase throughput ExOR protocol Measurements Related WorkExOR 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.3x25 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 linksExOR 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/