etx a highthroughput path metric for multihop wireless networks

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,A High-Throughput Path Metric for Multi-Hop Wireless Routing,Douglas S. J. De Couto,MIT CSAIL (LCS),Daniel Aguayo, John Bicket, and Robert Morris,1,5,th,floor,6,th,floor,29 PCs with 802.11b radios (fixed transmit power) in ad hoc mode,Indoor wireless network,4,th,floor,3,rd,floor,2,nd,floor,2,Testbed UDP throughput,better,Better,3,What throughput is possible?,Best for each pair is highest measured throughput of 10 promising static routes.,Routing protocol,Best,4,Talk outline,Testbed throughput problems,Wireless routing challenges,A new high-throughput metric (ETX),Evaluation,5,Links in route share radio spectrum,Extra hops reduce throughput,Challenge: more hops, less throughput,Throughput = 1/2,Throughput = 1,Throughput = 1/3,6,Challenge: many links are lossy,Smooth link distribution complicates link classification.,One-hop broadcast delivery ratios,Good,Bad,7,Challenge: many links are asymmetric,Many links are good in one direction, but lossy in the other.,Broadcast delivery ratios in both link directions.,Very asymmetric link.,8,Bottleneck throughput:,A straw-man route metric,Maximize bottleneck throughput,50%,Delivery ratio = 100%,51%,51%,D,A,B,C,Actual throughput:,A-B-C : ABBABBABB =,33%,A-D-C : AADDAADD = 25%,A-B-C = 50%,A-D-C =,51%,9,A-B-C =,51%,A-C = 50%,Another straw-man metric,Maximize end-to-end delivery ratio,51%,100%,50%,A,B,C,Actual throughput:,A-B-C : ABBABBABB = 33%,A-C : AAAAAAAA =,50%,End-to-end delivery ratio:,10,Minimize total transmissions per packet,(ETX, Expected Transmission Count),New metric: ETX,Link throughput,1/ Link ETX,Delivery Ratio,100%,50%,33%,Throughput,100%,50%,33%,Link ETX,1,2,3,11,Calculating link ETX,Assuming 802.11 link-layer acknowledgments (ACKs) and retransmissions:,P(TX success) = P(Data success),P(ACK success),Link ETX = 1 / P(TX success),= 1 / ,P(Data success),P(ACK success) ,Estimating link ETX:,P(Data success),measured fwd delivery ratio,r,fwd,P(ACK success),measured rev delivery ratio,r,rev,Link ETX,1 / (,r,fwd,r,rev,),12,Measuring delivery ratios,Each node broadcasts small link probes (134 bytes), once per second,Nodes remember probes received over past 10 seconds,Reverse delivery ratios estimated as,r,rev,pkts received / pkts sent,Forward delivery ratios obtained from neighbors (piggybacked on probes),13,Route ETX,Route ETX,1,2,2,3,Route ETX = Sum of link ETXs,5,Throughput,100%,50%,50%,33%,20%,14,ETX Properties,ETX predicts throughput for short routes,(1, 2, and 3 hops),ETX quantifies loss,ETX quantifies asymmetry,ETX quantifies throughput reduction of longer routes,15,ETX caveats,ETX link probes are susceptible to MAC unfairness and hidden terminals,Route ETX measurements change under load,ETX estimates are based on measurements of a single link probe size (134 bytes),Under-estimates data loss ratios, over-estimates ACK loss ratios,ETX assumes all links run at one bit-rate,16,Evaluation Setup,Indoor network, 802.11b, ad hoc mode,1 Mbps, 1 mW, small packets (134 bytes), RTS/CTS disabled,DSDV + modifications to respect metrics,Packets are routed using route table snapshot to avoid route instability under load.,DSR + modifications to respect metrics,17,ETX improves DSDV throughput,better,DSDV overhead,Best,DSDV+ETX,DSDV+hop-count,18,DSR with ETX,DSR+ETX,Best,DSR+hop-count,19,DSR with ETX (no TX feedback),DSR+ETX,Best,DSR+hop-count,20,Some related work,Threshold-based techniques,DARPA PRNet, 1970s80s Jubin87: Minimum hop-count, ignore bad links (delivery ratio,5/8 in either direction),Link handshaking Lundgren02, Chin02: Nodes exchange neighbor sets to filter out asymmetric links.,SNR-based approaches Hu02: Mark low-SNR links as bad, and avoid them,Mote sensors Yarvis02,Product of link delivery ratios,21,Whats next: MIT Roofnet,22,Summary,ETX is a new route metric for multi-hop wireless networks,ETX accounts for,Throughput reduction of extra hops,Lossy and asymmetric links,Link-layer acknowledgements,ETX finds better routes!,23,DSDV & DSR implementations:,Roofnet info at poster session,24,Extra slides follow,25,Big packets,26,Per-pair DSDV throughputs,27,ETX vs. link handshaking,28,Hop-count penalty,29,Throughput differs between paths,Paths from 23 to 36,30,Evaluation details,All experiments:,134-byte (including 802.11 overhead) UDP packets sent for 30 seconds,DSDV:,90 second warm-up (including ETX),Route table snapshot taken at end of 90s used to route UDP data for next 30s,DSR:,Initiate route request by sending 1 pkt/s for five seconds; followed by UDP data for 30s,ETX warms up for 15s before route request,31,Effect of asymmetry on DSDV,100%,100%,100%,8%,But, throughput of,B-A,B-C-A,B successfully receives all of As route ads, and installs a one-hop route to A.,A,C,B,100%,100%,32,