15-744: Computer NetworkingTaking Advantage of BroadcastOutlineInitial Approach: Traditional RoutingRadios Aren’t WiresExploiting Probabilistic BroadcastWhy ExOR Might Increase ThroughputSlide 8ExOR BatchingReliable SummariesPriority OrderingUsing ExOR with TCPDiscussionSlide 14BackgroundSlide 16Slide 17Coding GainThroughput ImprovementCoding Gain: more examplesCOPE (Coding Opportunistically)Opportunistic CodingPacket Coding AlgorithmPacket DecodingPrevent Packet ReorderingSummary of ResultsReasons for Lower Improvement in TCPSlide 28Slide 29Use Opportunistic RoutingButExORGlobal SchedulingMORE (Sigcomm07)Go RandomRandom Coding Benefits MulticastSlide 37MORESlide 39Slide 40Summary/Midterm15-744: Computer NetworkingL-12 Wireless BroadcastTaking Advantage of Broadcast•Opportunistic forwarding•Network coding•Assigned reading•XORs In The Air: Practical Wireless Network Coding•ExOR: Opportunistic Multi-Hop Routing for Wireless Networks2Outline•Opportunistic forwarding (ExOR)•Network coding (COPE)•Combining the two (MORE)3packetpacketpacketInitial Approach: Traditional Routing•Identify a route, forward over links•Abstract radio to look like a wired linksrcA BdstC4Radios Aren’t Wires•Every packet is broadcast•Reception is probabilistic123456123 63 5142345612 456srcA BdstC5packetpacketpacketpacketpacketpacketExploiting Probabilistic BroadcastsrcA BdstCpacketpacketpacket•Decide who forwards after reception•Goal: only closest receiver should forward•Challenge: agree efficiently and avoid duplicate transmissions6Why 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 distancesrc dstN1 N2 N3 N475%50%N525%7Why 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 lossesN1src dstN2N3N425%25%25%25%100%100%100%100%8ExOR 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 batchsrcN3dstN4tx: 23tx: 57 -23 24tx: 8tx: 100rx: 23rx: 57rx: 88rx: 0rx: 0tx: 0tx: 9rx: 53rx: 85rx: 99rx: 40rx: 22N1N29Reliable Summaries•Repeat summaries in every data packet•Cumulative: what all previous nodes rx’d•This is a gossip mechanism for summariessrcN1N2N3dstN4tx: {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}10Priority 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 headersrcN1N2N3dstN411Using ExOR with TCPNodeProxyExORGatewayWeb ProxyClient PCWeb ServerTCPTCPExOR Batches (not TCP)•Batching requires more packets than typical TCP window12Discussion•Exploits radio properties, instead of hiding them•Scalability?•Parameters – 10%?•Overheads?13Outline•Opportunistic forwarding (ExOR)•Network coding (COPE)•Combining the two (MORE)14Background•Famous butterfly example:•All links can send one message per unit of time•Coding increases overall throughput15Background•Bob and AliceRelayRequire 4 transmissions16Background•Bob and AliceRelayRequire 3 transmissionsXORXORXOR17Coding Gain•Coding gain = 4/311+3318Throughput Improvement•UDP throughput improvement ~ a factor 2 > 4/3 coding gain11+3319Coding Gain: more examplesWithout opportunistic listening, coding [+MAC] gain=2N/(1+N) 2.With opportunistic listening, coding gain + MAC gain ∞351+2+3+4+524120COPE (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 21Opportunistic CodingB’s queueNext hopP1 AP2 CP3 CP4 DCoding Is it good?P1+P2 Bad (only C can decode)P1+P3 Better coding (Both A and C can decode)P1+P3+P4Best coding (A, C, D can decode)BACDP4 P3P3 P1P4 P3 P2 P1P4 P1Packet 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 probability23Packet 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 24Prevent 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 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 opportunity•TCP congestion window does not sufficiently open up due to wireless losses•TCP doesn’t provide fair allocation across different flows27Discussion•Wired vs. wireless coding•Traffic patterns•Scale28Outline•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 RoutingOpportunistic routing promises large increase in throughputOpportunistic routing promises large increase in throughputsrcR1dstR4R2R350%0%50%0%0%0%50%50%30srcR1dstBut•Overlap in received packets Routers forward duplicatesR2P1P2P10P1P2P1P231ExOR•State-of-the-art opp. routing, ExOR imposes a global
View Full Document
Unlocking...