115-744: Computer NetworkingL-12 Wireless BroadcastTaking Advantage of Broadcast• Opportunistic forwarding• Network codingg• Assigned reading• XORs In The Air: Practical Wireless Network Coding• ExOR: Opportunistic Multi-Hop Routing for Wireless NetworksWireless Networks2Outline• Opportunistic forwarding (ExOR)pp g ( )• Network coding (COPE)•Combining the two (MORE)Combining the two (MORE)3packet packetInitial Approach: Traditional RoutingA Bpacketsrc dstC• Identify a route, forward over links• Abstract radio to look like a wired linkC42Radios Aren’t WiresA B123456123 63 5142345612 456src dstC• Every packet is broadcast• Reception is probabilisticC5packetExploiting Probabilistic BroadcastA Bpacketpacketpacketpacketpacketpacketpacketpacketsrc dstCC• Decide who forwards after reception• Goal: only closest receiver should forward• Challenge: agree efficiently and avoid duplicate transmissions6Why ExOR Might Increase Throughputsrc dstN1 N2 N3 N475%50%N525%• 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 distance7Why ExOR Might Increase ThroughputN1src dstN2N3N4• Traditional routing: 1/0.25+ 1 = 5 tx• ExOR: 1/(1 – (1 – 0.25)4) + 1 = 2.5 transmissions• Assumes independent losses83ExOR BatchingN4tx: 57 -23tx: 100rx: 57rx: 0rx: 0tx: 0tx: ≅ 9rx: 85rx: 40rx: 22N2• Challenge: finding the closest node to have rx’d •Send batches of packets for efficiencysrcN3dsttx: 23≅ 24tx:≅ 8rx: 23rx: 88rx: 53rx: 99N1Send 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 batch9Reliable SummariesN2N4tx: {2, 4, 10 ... 97, 98}summary: {1,2,6, ... 97, 98, 99}RiidksrcN1N2N3dstN4tx: {1, 6, 7 ... 91, 96, 99}summary: {1, 6, 7 ... 91, 96, 99}•Repeat summaries in every data packet• Cumulative: what all previous nodes rx’d• This is a gossip mechanism for summaries10Priority OrderingN2N4• Goal: nodes “closest” to the destination send first•Sort by ETX metric to dstsrcN1N2N3dstN4y• Nodes periodically flood ETX “link state” measurements• Path ETX is weighted shortest path (Dijkstra’s algorithm)• Source sorts, includes list in ExOR header11Using ExOR with TCPClient PCWeb ServerTCPTCPNodeProxyExORGatewayWeb ProxyExOR Batches (not TCP)• Batching requires more packets than typical TCP window124Summary• ExOR achieves 2x throughput improvement• ExOR implemented on Roofnet• Exploits radio properties, instead of hiding them13Outline•Opportunistic forwarding (ExOR)pp g ( )• Network coding (COPE)•Combining the two (MORE)Combining the two (MORE)14Background• Famous butterfly example:All li k d it f•All links can send one message per unit of time• Coding increases overall throughput15Background• Bob and AliceRelayRequire 4 transmissions165Background• Bob and AliceRelayXORXORXORRequire 3 transmissions17Coding Gain• Coding gain = 4/311+3318Throughput Improvement• UDP throughput improvement ~ a factor 2 > 4/3 coding gain11+3319Coding Gain: more examples52131+2+3+4+541With opportunistic listening, coding gain=2N/(1+N) Æ 2.With opportunistic listening, coding gain + MAC gain Æ ∞206COPE (Coding Opportunistically)• Overhear neighbors’ transmissions• Store these packets in a Packet Pool for a pshort time• Report the packet pool info. to neighbors• Determine what packets to code based on the info.• Send encoded packets 21Opportunistic CodingB’s queue Next hopP1 AP2CP4 P1P2CP3 CP4 DCoding Is it good?P1 P2Bd ( l C BCDP4 P3 P2 P1P1+P2Bad (only C can decode)P1+P3 Better coding (Both A and C can decode)P1+P3+P4 Best coding (A, C, D can decode)ADP4 P3P3 P1Packet Coding Algorithm• When to send?• Option 1: delay packets till enough packets to code withOti 2 dl i kthth’•Option 2: never delaying packets -- when there’s a transmission opportunity, send packet right away• Which packets to use for XOR?• Prefer XOR-ing packets of similar lengths• Never code together packets headed to the same next hophop• Limit packet re-ordering• XORing a packet as long as all its nexthops can decode it with a high enough probability23Packet Decoding• Where to decode?• Decode at each intermediate hop• How to decode?• Upon receiving a packet encoded with n native packetsfi d1ti ktf it•find n-1 native packets from its queue• XOR these n-1 native packets with the received packet to extract the new packet 247Prevent Packet Reordering• Packet reordering due to async acks degrade TCP performance• Ordering agent• Deliver in-sequence packets immediately• Order the packets until the gap in seq. no is fill d ti ifilled or timer expires25Summary of Results• Improve UDP throughput by a factor of 3-4 •Improve TCP by• wo/ hidden terminal: up to 38% improvement• w/ hidden terminal and high loss: little improvement• Improvement is largest when uplink to downlink has similar traffic• Interesting follow-on work using analog coding26Reasons for Lower Improvement in TCP• COPE introduces packet re-ordering • Router queue is small Î smaller coding qgopportunity• TCP congestion window does not sufficiently open up due to wireless losses• TCP doesn’t provide fair allocation across different flowsdifferent flows27Outline•Opportunistic forwarding (ExOR)pp g ( )• Network coding (COPE)•Combining the two (MORE)Combining the two (MORE)288Use Opportunistic RoutingR1srcdstR4R2R350%• Best single path Æ loss prob. 50% • In opp. routing [ExOR’05], any router that hears the packet can forward it Æ loss prob. 0.54= 6%Opportunistic routing promises large increase in throughputOpportunistic routing promises large increase in throughputR429But• Overlap in received packets Æ Routers forward duplicatessrcR1dstP1P2P1P2R2P10P1P230ExOR• State-of-the-art opp. routing, ExOR imposesa global scheduler:• Requires full coordination; every node must know who received what• Only one node transmits at a time, others listen31Global Scheduling?srcdst• Global coordination is too hard • One transmitter329Global Scheduling?srcdst• Global coordination is too hard • One transmitter Æ You lost spatial reuse!Does opportunistic routing have to be so complicated? Does opportunistic routing have to be so complicated? 33MORE (Sigcomm07)• Opportunistic
View Full Document
Unlocking...