Transcript XORs in The Air: Practical Wireless Network Coding

Testbed in Network Coding
学生：李腾飞
导师：舒炎泰
Background
• Bob and Alice
Alice
Relay
Require 4 transmissions
Bob
Background
• Bob and Alice
Alice
Relay
Bob
XOR
XOR
XOR
Require 3 transmissions
Outline
•
•
•
•
•
MIT Testbed (COPE,MORE,MIXIT)
Toronto
Aalborg-Denmark
Harvard(Rainbow)
What can we learn from?
MIT-Testbed
Outline
• Objective & Function
• Configuration
• Work & Paper on Network Coding
Objective & Function
• Build a two-floors Indoor Testbed
• First putting network coding into practice
• Mainly for test Network Coding
Routing/Mac/Phyical Layer Algorithm(wireless
802.11a/b/g,zigbee, etc ) on Laptop
• Large number of Nodes support(about 30)
Configuration
Software:
• System is Linux,and using Click Routing
Module[1] toolkit send 802.11a/b/g tcp and
udp datagram
• Implement with Srcr,EXOR and other classic
Routing or Mac Layer Algorithm
Configuration(2)
Hardware:
• 802.11a/b/g wireless card with an omni-directional
antenna (MIXIT use zigbee(802.15))
• Cards based on the NETGEAR 2.4&5GHz 802.11a/g
chipset(or NETGEAR WAG311 802.11chipset)
• RTS/CTS disabled
• Power level : Adjustable
• Mode: Adjustable
Testbed Work & Paper on Network Coding
• COPE[2](Sigcomm 06)
• MORE[3](Sigcomm 07)
• MIXIT[4](Sigcomm 08)
COPE
(Coding Opportunistically)
• Consider multiple unicast flows
– Generalize Alice-Bob scenario
• Exploits Shared Nature of Wireless Medium
– Store Overheard Packets for Short Time
– These packets are used for decoding perspective
packets
• First implement Wireless Network Coding in
the real world
MIT-MORE
• Spatial reuse and thus underutilize the wireless
medium.
• MAC-independent opportunistic routing protocol
• The first intra flow (single flow) in Network Coding
• It combines random network coding with
opportunistic routing to address its current
limitations.
MIT-MIXIT
•
•
•
•
Not apply an error detection code
Use Physical Layer Hint to guess bit error/right
Cross-layer
Most Based on More
Outline
•
•
•
•
•
MIT Testbed (COPE,MORE,MIXIT)
Toronto
Aalborg-Denmark
Harvard(Rainbow)
What can we learn from?
Toronto Testbed
Hardware
• NVIDIA GTX 280 Graphics Process Unit, 240 computing
cores.
• NVIDIA GeForce 8800 GT GPU with 112 cores, which is
supported by the CUDA platform.
• 8-core Intel Xeon server
Software
• NVIDIA’s Tesla GPU architecture
• C language using the Compute Unified Device
Architecture (CUDA) programming model and
development tools
Work & Paper on Network Coding
• Parallelized Progressive Network Coding With
Hardware Acceleration[5](IWQOS07)
• Nuclei: Graphics accelerated Many-core
Network Coding[6](Infocom 09)
• Pushing the Envelope:Extreme Network
Coding on the GPU[7]( ICDCS 09)
• UUSEE[8](Infocom 2010)
Parallelized Progressive Network Coding
• hardware acceleration
• Take advantage of symmetric multiprocessor
(SMP) systems
• packaged as a C++ class library
Platform comparison of coding performance at
(n = 128, k = 4 KB).
Nuclei: GPU-accelerated Many-core Network Coding
• Hundreds of computing cores in GPU
• Not affected by competing threads and
background tasks
• combined CPU-GPU encoding & decoding
Pushing the Envelope:
Extreme Network Coding on the GPU
• Super GPU set CPU free
• Table-based encoding technique
• parallel decoding ofmultiple segments
UUSEE
Objectives
• Minimized server bandwidth costs.
• Minimized buffering delay after a random
seek
• Consistently satisfactory playback quality
Outline
•
•
•
•
•
MIT Testbed (COPE,MORE,MIXIT)
Toronto
Aalborg-Denmark
Harvard(Rainbow)
What can we learn from?
Aalborg University
Outline
• Objective & Function
• Configuration
• Work & Paper on Network Coding
Objective & Function
•
•
•
•
Mainly Build a Mobile PhoneTestbed
Easy for movement Scene
Mainly for wireless Network Research Work.
Nearly 150 Papers in recent 10 years(most on this
Testbed)
• Recently years most of Testbed work is about
Network Coding
Configuration-Ex
Hardware:
• Nokia N810 Internet Tablet Large Screen ,for
Visualization
• WLAN Interface
• Processor - TI OMAP 2420, 400 MHz ARM11.
Configuration(2)
Software:
• Operating System - Maemo1 OS2008 (Linux kernel 2.6.21omap1)
• Cross-compilation toolkit Scratchbox
• SDK:Maemo SDK
Not just N810
• Nokia N95-8GB, ARM 11 332 MHz CPU, 128
MB ram,Symbian OS 9.2.
support IEEE802.11b/g
Lots of work on it!
• Laptop:Lenovo T61p, 2.53 GHz Intel Core2Duo,
2 GB ram,Kubuntu 8.10 64bit.
Work & Paper on Network Coding
• Cautious View on Network Coding - From Theory to Practice“ JCN 2008
• Evolutionary Theory for Cluster Head Election in Cooperative Clusters
implementing Network Coding", Europe Wireless 2009
• Implementation and Performance Evaluation of Network Coding for
Cooperative Mobile Devices“ ICC2008
• Implementation of Random Linear Network Coding on OpenGL-enabled
Graphics Cards Europe Wireless 2009
• Network Coding Opportunities for Wireless Grids Formed by Mobile
Devices ICST 2008
• Network Coding for Mobile Devices - Systematic Binary Random Rateless
Codes ICC09
• …
Outline
•
•
•
•
•
MIT Testbed (COPE,MORE,MIXIT)
Toronto
Aalborg-Denmark
Harvard(Rainbow)
What can we learn from?
Harvard-Rainbow
• MAC priority scheme
• Priority computed by the information collect
from neighbor,decide the rate of TX
• Priority based on the rank of coefficient matrix
of the Buffer of node
• Network Coding scheme for the outgoing data
at each node.
Rainbow-Testbed
• 29 OLPC Beta-2[9] nodes wireless testbed
• Outdoor Experiment(wireless interference (802.11)is
small compare with indoor)
• Broadcast Ethernet packets at the 2Mbit/s rate for all
protocol implementations
• The size of the file we distributed was 6.1 MBytes,
which at the 1.7 Mbit/s link rate of our testbed takes
about 30 seconds to transfer.We limited the
experiment run time to 300 seconds.
Hardware
• i386 compatible systems based on the AMD
Geode GX processor running at 366MHz, and
equipped with 128MB RAM.
• Each node has one Marvell Libertas 88W8388
802.11b/g radio, with tunable transmit power.
Harvard Implementation,We can learn ?
Developed implementation:
• Test Application:GUI has been implemented to show the
distribution of packets
• Framework:A Virtual Layer between MAC and IP Layer,just call
basic Berkely Function,easy for implement
• Logistics Platform:It contains all the data structures and
functions for the logistics of network coding.
• Schemes:This level is the algorithms for encoding and
decoding. One scheme for reliable broadcast, and one for
network coding.
Outline
•
•
•
•
•
MIT Testbed (COPE,MORE,MIXIT)
Toronto
Aalborg-Denmark
Harvard(Rainbow)
What can we learn from?
Testbed Objective
Architectural objectives
•
•
•
•
•
•
Research Requirements
Fast control connectivity and easy management
Flexible wireless components
Extendability
Financial cost
……
Research Requirements
• Be able to observe findings that have been
published in the past.(reproductive)
• Indoor and Outdoor Experiments
• New Idea
Fast control connectivity and easy management
• Node with more number and kinds of interfaces
• NFS Mounting Strategy
– All Update link to the server
– Remote turn off the node?
– Central Control
Flexible wireless components
• hardware and software should support
modifications
• Wifi Cards Driver should be opensource(or
Partly Open)
• Click Modular Router software framework is a
good idea.
• Linux-based wireless applications are used
The Driver-chipset Architecture
Example
• Three open-source Linux drivers available
today.
Click
• Refer:http://read.cs.ucla.edu/click/
• MIT and many University using Click
• modular software based router approach. The
components of Click are packet processing
modules called elements.
Extendability
• Multiply Interface for future Application
• Big waterproof box,for future more Device
• Through NFS ,Software could be easy for
Update
Financial cost
• Complicate Problem
References
• [1] http://read.cs.ucla.edu/click/
• [2] Sachin Katti, Hariharan Rahul, Wenjun Hu, Dina Katabi, Muriel Medard,
and Jon Crowcroft "XORs In The Air: Practical Wireless Network Coding,"
ACM SIGCOMM, 2006.
• [3] Szymon Chachulski, Michael Jennings, Sachin Katti, and Dina Katabi,
"Trading Structure for Randomness in Wireless Opportunistic Routing,"
ACM SIGCOMM, 2007.
• [4] Sachin Katti, Dina Katabi, Hari Balakrishnan, and Muriel Medard,
"Symbol-Level Network Coding for Wireless Mesh Networks," ACM
SIGCOMM, 2008.
• [5] H. Shojania and B. Li, “Parallelized Network Coding With Hardware
Acceleration,” in Proc. of the 15th IEEE International Workshop on Quality
of Service (IWQoS), 2007.
• [6] H. Shojania, B. Li, and X. Wang, “Nuclei: Graphicsaccelerated Manycore Network Coding,” in Proc. of IEEE INFOCOM 2009, August 2009.
References
[7] Hassan Shojania, Baochun Li. "Pushing the Envelope: Extreme Network
Coding on the GPU," to appear in the Proceedings of the 29th
International Conference on Distributed Computing Systems (ICDCS 2009),
Montreal Canada, June 22-26, 2009.
[8] Zimu Liu, Chuan Wu, Baochun Li, Shuqiao Zhao. "UUSee: Large-Scale
Operational On-Demand Streaming with Random Network Coding," to
appear in the Proceedings of IEEE INFOCOM 2010, San Diego, California,
March 15-19, 2010.
[9] http://zh.wikipedia.org/wiki/OLPC