Transcript ppt - Worcester Polytechnic Institute

XORs in The Air: Practical Wireless
Network Coding
Sachin Katti, Hariharan Rahul, Wenjun Hu, Dina Katabi, Muriel
Medard, Jon Crowcroft
MIT CSAIL & University of Cambridge
Daniel Courcy- [email protected]
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
2
Worcester Polytechnic Institute
Review
• Mesh Networks
– Way to Route Data
– Allows For Continuous Connections &
Reconfigurations
• Multicast
– Transmission to Multiple Selected Recipients
• Unicast
– Transmission to Single Selected Recipient
3
Worcester Polytechnic Institute
COPE
• Substantially Improves Throughput
• ‘Coding Shim’ Between IP and MAC
Layers
– Finds Coding Opportunities
– Benefits by Sending Multiple Packets in
Single Transmission
4
Worcester Polytechnic Institute
COPE: Simple Example
• Bob & Alice
• Current
Approach = 4
Transmissions
• COPE = 3
Transmissions
• Thus Allowing
For Increased
Throughput
• Coding+MAC
5
Worcester Polytechnic Institute
COPE: Even Bigger Savings
• Previous Example: Obvious Throughput
Gains
• COPE Exploits Shared Nature of
Wireless Medium
• Some Nodes Overhear Transmission
– Store These Packets for Short Time
– Sends Data Out Telling What It Has Heard
• This Data is Used For Opportunistic
Coding
Worcester Polytechnic Institute
6
Opportunistic Coding
• Each Node Uses Knowledge of What It’s
Neighbors Have (Which Packets)
• This Data Allows For Source to Send
XOR’ed Packets Intelligently
– In Other Words: It Knows who Will Be Able
to Decode The Encoded Packet
• Allows For More Than Two Flows
• Allows For Multiple Packets to be Coded
7
Worcester Polytechnic Institute
COPE = 2 Key Principles (1)
• COPE Embraces Broadcast Nature of
Wireless Channel
– Typically Network Designers Use Point-toPoint
– Adaptations are Made To Use Forwarding
and Routing Techniques Native to Wired
Networking
– COPE Exploits Radio Broadcast (Does Not
Attempt to Hide It)
Worcester Polytechnic Institute
8
COPE = 2 Key Principles (2)
• COPE Employs Network Coding
– Packets Are Mixed Before Transmission
– Prior Work Is Mainly Theoretical
– COPE Addresses:
• Unicast Traffic
• Dynamic & Bursty Flows
• Other Practical Issues Regarding Implementation
9
Worcester Polytechnic Institute
Why is COPE Different?
• 1st System Architecture For Wireless
Network Coding
• Implementation: 1st Deployment of
Wireless Network Coding
• Performance Study with Results of
Wireless Network Coding
10
Worcester Polytechnic Institute
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%
Worcester Polytechnic Institute
11
Background
Famous Butterfly Example:
•All Links Can Send
One Message Per
Unit of Time
•Sources Want to Hit
Both Receivers
•Coding (Again)
Increases Overall
Throughput
12
Worcester Polytechnic Institute
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
13
Worcester Polytechnic Institute
Background (cont.)
• All Previous Work Theoretical &
Multicast
• Some Unicast Scenarios Show Better
Throughput for Those Scenarios
• This Paper Seeks to ‘Bridge the Gap’
Between Network Coding, Practical
Design
• Seeks to Provide Operational Protocol
14
Worcester Polytechnic Institute
COPE Overview
• Before Getting Into The Details Know
These Terms:
15
Worcester Polytechnic Institute
COPE Overview
• 3 Main Techniques
– Opportunistic Listening
– Opportunistic Coding
– Learning Neighbor State
16
Worcester Polytechnic Institute
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
Worcester Polytechnic Institute
17
COPE Overview:
Opportunistic Coding
• Which Packets do we Combine to
Achieve Maximum Throughput?
• Simple Answer: Send as Many (Native
Packets) as Possible While Ensuring
Nexthop Has Enough Info to Decode
18
Worcester Polytechnic Institute
COPE Overview:
Opportunistic Coding
• Always Seeking Largest N That Satisfies
Above Rule
Worcester Polytechnic Institute
19
COPE Overview:
Learning Neighbor State
• Each Node Announces Its Stored
Packets In Reception Reports
• Sometimes Reports Don’t Get Through
– Congestion or In Times of Light Traffic
• To Solve This Problem: Intelligent Guess
– Estimation of Probability That Neighbor Has
Packet Based On Delivery Probability
20
Worcester Polytechnic Institute
COPE’s Gains
• How Beneficial is COPE?
– Throughput Improvement Depends On:
• Coding Opportunities
• Traffic Patterns
21
Worcester Polytechnic Institute
COPE’s Gains:
Coding Gain
• Coding Gain:
– # Transmissions w/o Coding to the Minimum
# Transmissions w/ Coding
• Remember Alice & Bob?
– Coding Gain = 4/3 = 1.33
22
Worcester Polytechnic Institute
COPE’s Gains:
Coding Gain
• Maximum Achievable Coding Gain?
– For Arbitrary Topologies - Open Question
• Authors Prove:
• With Listening Certain Topologies Benefit
23
Worcester Polytechnic Institute
COPE’s 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 (as Opposed to Opportunistic Routing)
24
Worcester Polytechnic Institute
COPE’s 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
25
Worcester Polytechnic Institute
COPE’s Gain:
Coding+MAC Gain
• Authors Prove:
26
Worcester Polytechnic Institute
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 Nexthop
27
Worcester Polytechnic Institute
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 Reordeing Bad (TCP Thinks
Congestion)
– Doesn’t Happen Much But If so They Are
Put in Order Before Transport Layer
Worcester Polytechnic Institute
28
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
29
Worcester Polytechnic Institute
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)
30
Worcester Polytechnic Institute
Making It Work Pseudo-Broadcast
• 802.11 Has Two MAC Modes:
– Unicast
– Broadcast
• Unicast
– Packets Are Ack-ed
– Exponential Backoff
• Multicast
– Un-Reliable
– No Backoff
31
Worcester Polytechnic Institute
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
Worcester Polytechnic Institute
32
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
33
Worcester Polytechnic Institute
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)
34
Worcester Polytechnic Institute
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
Worcester Polytechnic Institute
35
Implementation Details: Packet
Format
• COPE Inserts Variable Length Coding
Header
• Only Shaded Fields Below Required
36
Worcester Polytechnic Institute
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 Packets
– Last_PKT: Last Packet Heard From Source
– Bit Map of Recently Heard Packets
Worcester Polytechnic Institute
37
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
38
Worcester Polytechnic Institute
Implementation Details:
Control Flow
39
Worcester Polytechnic Institute
Experimental Results
• 20 Node Wireless Testbed
• Following Slides Will Show:
– 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 TCP’s Gain Agrees With
Expected Coding Gain
40
Worcester Polytechnic Institute
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
41
Worcester Polytechnic Institute
Experimental Results: Testbed
• Nodes Ran Linux / Used Click Toolkit
• Runs as User Space Daemon
• Applications Interact With Daemon as Normally Would
With Any Network Device
• Testbed Used Srcr Routing Protocol
– Djikstra’s 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
42
Worcester Polytechnic Institute
Metrics
• Network Throughput
– End-to-End Throughput
• Throughput Gain
– Ratio of Measured Network Throughputs
With and Without COPE
• What Else Might Have Been Interesting?
43
Worcester Polytechnic Institute
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)
44
Worcester Polytechnic Institute
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
45
Worcester Polytechnic Institute
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
46
Worcester Polytechnic Institute
COPE in an Ad Hoc Network
• Here it is: 20 Node Wireless Testbed
• 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?
Worcester Polytechnic Institute
47
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
48
Worcester Polytechnic Institute
COPE in an Ad Hoc Network
•
•
•
•
UDP (Back to Large Scale Testbed)
(Again) Random Sender / Receiver
File Size Follows Internet Studies
500 Experiments…
49
Worcester Polytechnic Institute
COPE in an Ad Hoc Network
• Scare Coding Opp. At Low Demands
• Demand Up / Congestion Up / Gain Up
Worcester Polytechnic Institute
50
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
Worcester Polytechnic Institute
51
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
Worcester Polytechnic Institute
52
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 (Of Course)
• Fluctuate Upload / Download Traffic
• Gain Goes Up as Upload Traffic Up
53
Worcester Polytechnic Institute
COPE in Mesh Access Network
54
Worcester Polytechnic Institute
Fairness
• Channel From Source to Bottleneck
Matters
• Capture Effect (If Alice’s 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
Worcester Polytechnic Institute
55
Fairness
56
Worcester Polytechnic Institute
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
57
Worcester Polytechnic Institute
Conclusions
• Coding is an Old Theme
• COPE Has Potential to Largely Increase
Network Throughput
• 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?
Worcester Polytechnic Institute
58
Questions?
59
Worcester Polytechnic Institute