1 15-744: Computer Networking L-12 Wireless Broadcast Taking Advantage of Broadcast • Opportunistic forwarding • Network coding • Assigned reading • XORs In The Air: Practical Wireless Network Coding • ExOR: Opportunistic Multi-Hop Routing for Wireless Networks 2 Outline • Opportunistic forwarding (ExOR) • Network coding (COPE) • Combining the two (MORE) 3 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 42 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 5 packet packet packet packet packet packet 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 6 Why ExOR Might Increase Throughput • 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% 7 Why ExOR Might Increase Throughput • 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% 83 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 rx: 23 rx: 57 rx: 88 rx: 0 rx: 0 tx: 0 tx: ≅ 9 rx: 53 rx: 85 rx: 99 rx: 40 rx: 22 N1 N2 9 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} batch map: {1,2,6, ... 97, 98, 99} batch map: {1, 6, 7 ... 91, 96, 99} 10 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 src N1 N2 N3 dst N4 11 Using ExOR with TCP Node Proxy ExOR Gateway Web Proxy Client PC Web Server TCP TCP ExOR Batches (not TCP) • Batching requires more packets than typical TCP window 124 Discussion • Exploits radio properties, instead of hiding them • Scalability? • Parameters – 10%? • Overheads? 13 Outline • Opportunistic forwarding (ExOR) • Network coding (COPE) • Combining the two (MORE) 14 Background • Famous butterfly example: • All links can send one message per unit of time • Coding increases overall throughput 15 Background • Bob and Alice Relay Require 4 transmissions 165 Background • Bob and Alice Relay Require 3 transmissions XOR XOR XOR 17 Coding Gain • Coding gain = 4/3 1 1+3 3 18 Throughput Improvement • UDP throughput improvement ~ a factor 2 > 4/3 coding gain 1 1+3 3 19 Coding Gain: more examples Without opportunistic listening, coding [+MAC] gain=2N/(1+N) 2. With opportunistic listening, coding gain + MAC gain ∞ 3 51+2+3+4+5 2 4 1 206 COPE (Coding Opportunistically) • Overhear neighbors’ transmissions • Store these packets in a Packet Pool for a short time • Report the packet pool info. to neighbors • Determine what packets to code based on the info. • Send encoded packets 21 Opportunistic Coding B’s queue Next hop P1 A P2 C P3 C P4 D Coding Is it good? P1+P2 Bad (only C can decode) P1+P3 Better coding (Both A and C can decode) P1+P3+P4 Best coding (A, C, D can decode) B A C D P4 P3 P3 P1 P4 P3 P2 P1 P4 P1 Packet Coding Algorithm • When to send? • Option 1: delay packets till enough packets to code with • 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 hop • Limit packet re-ordering • XORing a packet as long as all its nexthops can decode it with a high enough probability 23 Packet Decoding • Where to decode? • Decode at each intermediate hop • How to decode? • Upon receiving a packet encoded with n native packets • find n-1 native packets from its queue • XOR these n-1 native packets with the received packet to extract the new packet 247 Prevent 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 filled or timer expires 25 Summary 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 coding 26 Reasons for Lower Improvement in TCP • COPE introduces packet re-ordering • Router queue is small smaller coding opportunity • TCP congestion window does not sufficiently open up due to wireless losses • TCP doesn’t provide fair allocation across different flows 27 Discussion • Wired vs. wireless coding • Traffic patterns • Scale 288 Outline • Opportunistic forwarding (ExOR) • Network coding (COPE) • Combining the two (MORE) 29 • 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% Use Opportunistic Routing Opportunistic routing promises large increase in throughput src R1 dst R4 R2 R3 50% 0% 50% 0% 0% 0% 50% 50% 30 src R1 dst But • Overlap in received packets Routers forward duplicates R2 P1 P2 P10 P1 P2 P1 P2 31 ExOR • State-of-the-art opp. routing, ExOR imposes a global scheduler: • Requires full
View Full Document
Unlocking...