Wireless Mesh Networks - sar.informatik.hu-berlin.de

Wireless Mesh Networks - sar.informatik.hu-berlin.de

Wireless Mesh Networks XORs in the Air A. Zubow XORs in The Air: Practical Wireless Network Coding, Sachin Katti, Hariharan Rahul, Wenjun Hu, Dina Katabi, Muriel Medard, Jon Crowcroft, http://piper.csail.mit.edu/papers/copesc.pdf Introduction - COPE

New Architecture For Wireless Mesh Networks Routers Forward & Code (Mix) Packets Intelligent Mixing Improves Throughput Prior Work = Theoretical & Multicast This Study = Practical & Unicast COPE = Inter-flow Network Coding MORE = Intra-flow Network Coding

2 COPE Substantially improves throughput Coding Shim between IP and MAC Layers Finds coding opportunities Benefits by sending multiple packets in single transmission (wireless broadcast) 3 COPE: Simple Example

Bob & Alice Current approach = 4 transmissions COPE = 3 transmissions Thus allowing for increased through put Coding+MAC 4

COPE: Even Bigger Savings Previous example: obvious throughput gains COPE exploits shared nature of wireless medium (broadcast) Nodes overhear transmissions Store these packets for short time Sends data out telling what it has heard This data is used for opportunistic coding 5

Opportunistic Coding Each node uses knowledge of what its neighbors have (which packets) This information allows for source to send XORed packets intelligently It knows who will be able to decode the encoded packet Allows for more than two flows Allows for multiple packets to be coded 6

COPE = 2 Key Principles COPE exploits broadcast nature of wireless channel COPE employs network coding Packets are mixed before transmission COPE addresses: Unicast traffic Dynamic & bursty flows Other practical issues regarding implementation 7

Summarized Findings Network coding can improve wireless throughput When congested with mainly UDP flows throughput gains 3 - 4x For mesh networks connected to Internet via AP gains depend on total download / upload traffic @ AP w/o hidden terminals TCP throughput increases about 38% 8

Background (Theory) Famous Butterfly Example: All Links Can Send One Message Per Unit of Time Sources Want to Hit Both Receivers Coding (Again) Increases Overall Throughput 9 Background (cont.)

Ahlswede et al. pioneered network coding Routers that mix information allow communication to achieve multicast capacity Li et al. found for multicast linear codes sufficient to achieve max capacity bounds 10 COPE Overview COPE terms:

11 COPE Overview 3 Main Techniques Opportunistic Listening Opportunistic Coding Learning Neighbor State 12 COPE Overview: Opportunistic Listening

Wireless is a broadcast medium Many chances for nodes to overhear COPE sets all nodes as promiscuous They store overheard packets for time (T) Default T = .5 seconds Also: reception reports are sent out These are tacked onto normal output Includes seq. number of stored packets 13 COPE Overview:

Opportunistic Coding Q.: Which packets do we combine to achieve maximum throughput? A.: Send as many (native packets) as possible while ensuring nexthop has enough info to decode. 14 COPE Overview: Opportunistic Coding

Always seeking largest N that satisfies above rule 15 COPE Overview: Learning Neighbor State Each node announces its stored packets in reception reports Sometimes reports dont get through Congestion or in times of light traffic To solve this problem: educated guess

Estimation of probability that neighbor has packet based on delivery probability 16 COPEs Gains How Beneficial is COPE? Throughput improvement depends on: Coding opportunities Traffic patterns 17

COPEs Gains: Coding Gain Coding Gain: # transmissions w/o coding to the minimum # transmissions w/ Coding Remember Alice & Bob? Coding gain = 4/3 = 1.33 18

COPEs Gains: Coding Gain Maximum Achievable Coding Gain? For arbitrary topologies - open question Authors prove: With listening certain topologies benefit 19

COPEs Gain: Coding Gain Interesting to note: Previous slide talks about theoretical gain In practice gains are lower due to: Coding opportunities Packet header overhead Medium losses COPE coding gains are not lost when medium is fully utilized. 20

COPEs Gain: Coding+MAC Gain Interaction between coding & MAC Beneficial results Example Bob & Alice MAC divides bandwidth between 3 w/o coding router sends 2 x more Makes router a bottleneck COPE allows routers queue to drain fast Coding + MAC gain of Alice & Bob = 2 21

COPEs Gain: Coding+MAC Gain Authors Prove: 22 Making It Work - Packet Coding Algorithm Packets are never delayed If there is nothing to code with, send anyway

Preference to XOR with similar lengths Small packet XOR with large = less bandwidth If one must XOR different lengths - pad Never code packets to same next hop 23 Making It Work - Packet Coding Algorithm Searching for appropriate packets to code is efficient

FIFO output queue: De-queue, small or large?, Look at appropriate queues (only heads to avoid reordering) Worst case - looks @ 2M packets (M=# neighbors) Packet reordering bad (TCP thinks congestion) Doesnt happen much but if so they are put in order before transport layer 24 Making It Work - Packet Coding

Algorithm Finally relay nodes all estimate probability that neighbor has packet prior to sending PD must stay higher than threshold G (G = 0.8 default) If equation is above G each nexthop has probability G of being able to decode next packet 25 Making It Work - Packet Decoding Fairly Simple

Each node maintains a packet pool Searches hash table keyed on packet ID XORs native packets with coded packets Gets packet meant for it (node) 26 Making It Work Pseudo-Broadcast 802.11 Has Two MAC Modes: Unicast Broadcast

Unicast Packets Are Ack-ed Exponential Backoff Broadcast Un-Reliable No Backoff 27 Making It Work Pseudo-Broadcast Pseudo-Broadcast

Piggy backs unicast Link-layer destination set to one intended node

XOR header added Other nodes can overhear transmission If receiving node is nexthop - continue Else store packet in buffer More reliable than pure broadcast Packets have several tries to get to destination Snooping nodes get more chances to update their buffers 28 Making It Work - Hop-by-Hop ACKs and Retransmissions

(Again) Encoded packets require all nexthops to acknowledge receipt of native packet Packets headed many places & only link layer designated hop returns synchronous ACK COPE may guess node has enough info to decode when it really does not 29 Making It Work - Hop-by-Hop ACKs and Retransmissions When a node sends an encoded packet it schedules a

retransmission event for each encoded native packet If any packet is not Ack-ed within some threshold (time) that native packet is encoded and re-sent later Nexthops receive packets and ACK immediately upon decoding via header (or control packets which are also used for reception reports) 30 Making It Work - TCP Packet Reordering Asynchronous ACKs can cause packet

reordering TCP may see this as congestion COPE has ordering agent For each TCP flow ending @ host Maintains packet buffer Records last TCP sequence number Will not pass on packets to transport layer until no hole exists or timer times out 31 Implementation Details: Packet

Format COPE inserts variable length coding header Only shaded fields below required 32 Implementation Details: Packet Format First Block: Metadata for decoding ENCODED_NUM: # Encoded For each packet PKT_ID (Dest. IP & Seq. #) MAC of nexthop (for each native packet)

Reception Reports REPORT_NUM: # of Reports SRC_IP: Source of reported rackets Last_PKT: last packet heard from source Bit map of recently heard packets 33 Implementation Details: Packet Format Asynchronous ACKs Cumulative ACKs on per neighbor basis

Local sequence numbers established ACK headers start with # of ACKs Each ACK starts with MAC of neighbor Next each ACK has pointer to end of cumulative ACKs Finally, bit map shows missing packets 34 Implementation Details: Control Flow 35

Experimental Results 20 Node wireless testbed Results: When many random UDP flows: Throughput 3 - 4x increase Traffic does not use congestion control: Throughput improves - exceeding coding gain Mesh network -> internet via gateway Throughput improvement between 5 - 70%

w/o hidden terminals TCPs gain agrees with expected coding gain 36 Experimental Results: Testbed 20 Node wireless network Two floors connected by open lounge Offices, passages, etc. Paths btw 1 & 6 hops Loss rate btw 0 - 30% 802.11a @ 6 Mb/s

37 Experimental Results: Testbed Nodes ran Linux / used Click toolkit Testbed used Srcr routing protocol Djikstras shortest path algorithm Each node had 802.11 card w/ omni-directional antenna 802.11 ad hoc mode w/ RTS / CTS disabled udpgen & ttcp used to generate traffic Long-live flows & attempt to match internet traffic

38 Metrics Network throughput E2E throughput Throughput gain Ratio of measured network throughputs with and without COPE What else might have been interesting?

39 COPE in Gadget Topologies Toy topologies Very small loss rate & no hidden terminals (40 different runs) Long-lived TCP flows Close to expected (minus overhead) 40

COPE in Gadget Topologies Above results show that w/ congestion control results lean towards coding gain rather than Coding+MAC When many long-lived flows (TCP) bottleneck senders backoff (to avoid drop) This leaves only coding gains 41 COPE in Gadget Topologies Repeat of Above w/ UDP

Coding+MAC Gains (Better Than TCP) Coding Allows Downstream Routers to Avoid Dropping Packets Already Having Consumed Bandwidth Worcester Polytechnic Institute 42 COPE in an Ad Hoc Network TCP

TCP flows arrive w/ poisson process Pick sender & receiver randomly Traffic models Internet No significant improvement (2-3%) Hidden terminals are culprit Many retransmissions Queues @ bottlenecks never build up

Therefore no coding gains (or opportunities) Would TCP do better w/o collisions? 43 COPE in an Ad Hoc Network Compressed topology Within carrier sense range Artificially impose original loss rates

Hidden terminals = no more At peak 38% gain over no coding 44 COPE in an Ad Hoc Network

UDP (back to large scale testbed) Random sender / receiver File size follows Internet studies 500 experiments 45 COPE in an Ad Hoc Network Scare coding opp. at low demands

demand up / congestion up / gain up 46 COPE in an Ad Hoc Network Low demand - reports arrive to late Demand goes up - bottlenecks form - longer wait times - nodes get more reports Demands get higher - high loss rates of reception reports - guessing relied upon

47 COPE in an Ad Hoc Network @ peak gain point (5.6 Mb/s) On average 3 packets coded together

Packets drained from bottlenecks faster Throughput gains 3 - 4 x 48 COPE in a Mesh Access Network Growing interest in accessing Internet via multi-hop network with one (or more) gateways Nodes divided into 4 sets (1 is gateway) UDP flows Fluctuate upload / download traffic Gain goes up as upload traffic up

49 COPE in Mesh Access Network 50 Fairness Channel from source to bottleneck matters Capture effect (If Alices channel is bad then Bob might push more traffic) If Alice moves slowly away? Coding opp. down, throughput down, fairness

down w/o coding throughput goes Up Coding aligns fairness & efficiency 51 Fairness 52 Discussion Target: stationary wireless mesh networks

Memory needed to store packets Need more than delay bandwidth product Need omni-directional antenna Current design does not consider power 53 Conclusions

Coding is an old theme COPE assists many random UDP flows best No congestion control is a good thing No hidden terminals is good as well (even for TCP) Mesh networks connected to Internet via AP - COPE shows gains from 5 - 70 % Many extensions - sensor networks? cellular? 54

Resources Sachin Katti, Hariharan Rahul, Wenjun Hu, Dina Katabi, Muriel Medard, Jon Crowcroft, MIT CSAIL & University of Cambridge Daniel Courcy- [email protected], Worcester Polytechnic Institute 55

Recently Viewed Presentations

  • Frequency Spectrum , Antennas, and Amateur Radio

    Frequency Spectrum , Antennas, and Amateur Radio

    Frequency Spectrum , Antennas, and Amateur Radio ... Applications 3-300GHZ Wireless Data Links Broadband Internet links Large bandwidth Radar Wireless USB Amateur Microwave Contesting What is Amateur Radio Hobby Provide Emergency Communication Much more resilient than convention telephone lines ...
  • FODAVA-Lead Education, Community Building, and Research: Dimension Reduction

    FODAVA-Lead Education, Community Building, and Research: Dimension Reduction

    Haesun Park and Guy Lebanon School of Computational Science and Engineering Georgia Institute of Technology ... (Eric E Monson, Rachael Brady, Guangliang Chen & Mauro Maggioni) VAC Consortium Meeting Poster/Demo Session " (Eric E Monson, Rachael Brady, Guangliang Chen &...
  • Mendel and the Gene Idea and The Chromosomal Basis of Inheritance

    Mendel and the Gene Idea and The Chromosomal Basis of Inheritance

    Lethal Recessive Alleles. Usually cause the death of the individual before they mature and reproduce. Huntington's Disease. Does not cause symptoms until 35-45 years of age. By this point the affected individual may have already had children. The child will...
  • Cut head parts on ALL solid lines. Pattern

    Cut head parts on ALL solid lines. Pattern

    Lines can be thick, thin, zigzag, curved, etc. Eyes: Using pre-cut eyes and a pencil, design horse's eyes. Use a U-shape for the eyeball. Refer to examples. Redraw pencil lines of eye and fill in pupil . with Sharpie. They...
  • Australias Vocational Education & Training System and its

    Australias Vocational Education & Training System and its

    Queanbeyan Lismore/Ballina Darwin Perth Adelaide Gosford Hunter Illawarra Dubbo Western Sydney Port Macquarie Northern Tasmania North Brisbane Gladstone Townsville Gold Coast Pilbara Whyalla/Port Augusta Geelong Warrnambool Bairnsdale/Sale Eastern Melbourne Bendigo Sunshine New technical ...
  • Rotary International-District 5180 WELCOME

    Rotary International-District 5180 WELCOME

    Includes Northern California, Oregon, Washington, Idaho, Montana and Alaska. It is the largest geographical multi-district in the world. Arranges exchange partners with other districts. Helps to arrange - flights, insurance, visas, orientations, training and background checks. Lee Oelke, Chairman of...
  • Слайд 1 - Msu

    Слайд 1 - Msu

    Horizontal axis ~Q/kT T=T(M) Vertical - d2N/dQdt * EGRET and constraints on PBH Background radiation at energies: 30 MeV - 120 GeV. The upper limit on the density of PBHs astro-ph/0504034 * Constraints on cosmological parameters from data on PBH...
  • Counseling Through The Super Heroes

    Counseling Through The Super Heroes

    Ruth Vincent, LPC, NCC & Gloria Varela - Super Clerk. Ready to fight crime? Our Powers as Counselors. The Heroes. The Identities . The Treatment / Becoming Nick Fury. ... Clark Kent. superman. Normalise feelings of anxiety and assure safety...