exor sigcomm

Information about exor sigcomm

Published on December 23, 2007

Author: Columbia

Source: authorstream.com

Content

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/

Related presentations


Other presentations created by Columbia

Electrical motors
14. 11. 2007
0 views

Electrical motors

Plant Adaptations
23. 11. 2007
0 views

Plant Adaptations

Davis powerpoint
03. 10. 2007
0 views

Davis powerpoint

8 1 intro unix
29. 11. 2007
0 views

8 1 intro unix

model
07. 12. 2007
0 views

model

Coparmex Laboral Yanis Raptis
11. 12. 2007
0 views

Coparmex Laboral Yanis Raptis

moodys 1
26. 10. 2007
0 views

moodys 1

Careers English
05. 11. 2007
0 views

Careers English

Ford Carter 1975 1980
07. 11. 2007
0 views

Ford Carter 1975 1980

Nitrogen Asphyxiation Bulletin
12. 11. 2007
0 views

Nitrogen Asphyxiation Bulletin

Class10
16. 11. 2007
0 views

Class10

Susantha Bangkok Bioethics
21. 11. 2007
0 views

Susantha Bangkok Bioethics

rciabc en
21. 11. 2007
0 views

rciabc en

SMMGEuler
30. 12. 2007
0 views

SMMGEuler

mod18 1
01. 01. 2008
0 views

mod18 1

RICGPSlideshow
03. 01. 2008
0 views

RICGPSlideshow

Space Wortzel
03. 01. 2008
0 views

Space Wortzel

CTSAs Today Part 3 Wall
04. 01. 2008
0 views

CTSAs Today Part 3 Wall

Nano Paris Oct2006 a5
07. 01. 2008
0 views

Nano Paris Oct2006 a5

vote Verification Sherman GWU
07. 01. 2008
0 views

vote Verification Sherman GWU

pocketcheffmkt
12. 12. 2007
0 views

pocketcheffmkt

ABSLec5
27. 09. 2007
0 views

ABSLec5

Rain Drops
03. 10. 2007
0 views

Rain Drops

04 Livestock Contributions
26. 11. 2007
0 views

04 Livestock Contributions

Ici
20. 02. 2008
0 views

Ici

Family and Social Change
24. 02. 2008
0 views

Family and Social Change

InventorsWorkshop042 006
27. 02. 2008
0 views

InventorsWorkshop042 006

Lewis ISDS 2007stp
27. 03. 2008
0 views

Lewis ISDS 2007stp

Neu259 2006 2 photon
20. 11. 2007
0 views

Neu259 2006 2 photon

ASI Presentation
28. 11. 2007
0 views

ASI Presentation

MonetaryPolicyInChina
13. 04. 2008
0 views

MonetaryPolicyInChina

Team Tracer Presentation
14. 11. 2007
0 views

Team Tracer Presentation

NISL History current2
30. 10. 2007
0 views

NISL History current2

Hewitt
02. 10. 2007
0 views

Hewitt

Schmidt
08. 11. 2007
0 views

Schmidt

marineFallOffDuty
06. 11. 2007
0 views

marineFallOffDuty

muzi
29. 10. 2007
0 views

muzi

patty abramson russian
01. 10. 2007
0 views

patty abramson russian

tufts web
19. 11. 2007
0 views

tufts web

WkshpPres
26. 11. 2007
0 views

WkshpPres

thetis
31. 10. 2007
0 views

thetis

2 06 dela croce
05. 11. 2007
0 views

2 06 dela croce

RenaissanceArt
31. 10. 2007
0 views

RenaissanceArt

Gautam Handout
28. 12. 2007
0 views

Gautam Handout

WillgerodtAllRoads
01. 11. 2007
0 views

WillgerodtAllRoads

Planning Change 5C2
01. 12. 2007
0 views

Planning Change 5C2

Moving with EUROUSA
06. 11. 2007
0 views

Moving with EUROUSA