Applied Network Coding in Wireless Networks

Table of Contents

1. Introduction
1.1. Network Coding
1.1.1. Principle
1.1.2. Linear Coding
1.1.3. Deterministic Coding
1.1.4. Decentralized network coding
1.1.5. Random Coding
1.2. Peer-to-Peer Swarming
1.2.1. Microsoft Avalanche
1.2.2. Codetorrent
1.3. Haggle
1.4. COPE
1.4.1. Opportunistic Listening
1.4.2. Opportunistic Coding
1.4.3. Opportunistic Routing
1.4.4. Pseudo Broadcast
1.4.5. Realization of the Cope principle
1.4.6. Performance Bottlenecks for TCP

2. Implementations
2.1. MIT Reference Implementation
2.1.1. CLICK
2.1.2. Roofnet
2.1.3. Madwifi-stripped
2.1.4. COPE elements
2.2. OpenWRT
2.2.1. Stable Branch / White Russian
2.2.2. "Bleeding Edge” / Kamikaze
2.2.3. Buildroot Environment
2.2.4. Packages
2.2.5. Image Deploying / Flashing

3. Measurements
3.1. Layout of the experiments
3.1.1. Retransmissions
3.1.2. Bandwidth
3.1.3. Memory leak
3.2. Measurement results
3.2.1. Throughput without coding
3.2.2. Throughput with coding
3.2.3. Analysis
3.3. Conclusion of the experiments

4. Resilience through redundancy
4.1. Zaib Quality of Service
4.1.1. Problems Addressed
4.1.2. Improvements
4.1.3. Complete solution
4.1.4. Example
4.1.5. Simulation / Analysis
4.2. Adaptive Preventive Redundancy
4.2.1. Problems addressed
4.2.2. Improvements
4.2.3. Complete solution
4.2.4. Example
4.2.5. Advantages against Reed-Solomon Coding
4.3. Outlook

Appendix A Current QoS implementation

Appendix B Porting Cope
B.1 Native Implementation
B.2 Roofnet/Click on OpenWRT
B.2.1 Berlinroofnet
B.2.2 MIT Roofnet Package
B.2.3 Patching COPE Reference Implementation
B.2.4 Modifications on Cope
B.2.5 OpenWRT development
B.3 Modifications on Cope to run on broadcom

Appendix C Cope packet handling
C.1 Alice sending
C.2 Router
C.3 Alice receiving
C.4 Bob

Appendix D Click configuration File

Appendix E Measurement results

Index of Figures

Index of Tables

Bibliography

Affidavit

1. Introduction

1.1. Network Coding

Network coding describes the technique to perform coding operations on contents throughout the network, increasing the information density of a single transmission and therefore increasing network throughput.

The idea of network coding was first introduced by Ahlswede et al. [AHL00]. Later it was shown by Li et al. [LI03] that simple, linear codes where sufficient for network coding in multicast networks, and then Koetter and Medard [KOE03] showed the same for arbitrary networks.

1.1.1. Principle

Instead of transmitting one packet after the other, like traffic on roads, network cod­ing exploits the fact that instead of simply forwarding the transmitted data can be used for calculations that improve the information density per packet.

Therefore data for multiple packets for different destinations can be combined (en­coded) and sent in one broadcast to all destinations. The premise is that each desti­nation receives enough data to reconstruct the original information. Thus each relay­ing node (routers or mesh nodes) can combine several input packets in one or more output packets that will be sent "downstream".

A receiver only has to receive enough linear combinations of the packets it is looking for in order to reconstruct the data.

A simple example to show the principle of network coding is the so-called "butterfly network” shown by [FRA05].

illustration not visible in this excerpt

Figure 1.1: The butterfly network

The butterfly network is a simple multicast network using slotted time transfers. As shown in figure 1.1, hosts A and B are senders in a multicast setup and hosts E and F are receivers while host C and D will forward packets. With traditional routing, only one of the receivers can receive both packets in one transmission, e.g. if C forwards the packet x1, F will receive both packets but E will receive only x1. The throughput rate is at 1,5 packets/time-slot.

illustration not visible in this excerpt

Figure 1.2: The butterfly network using network coding

Using network coding, host C can encode the packets together by using XOR and send them out as one packet. Host E can now XOR the encoded packet with the packet x1 to receive packet x2. Host F does the same with packet x2 to receive packet x1. This way both receivers get both packets in one transmission, and the throughput rate is increased to 2 packets/time-slot.

Assume, for example, the packet size is 1 bit, then the packet and operations could be as follows:

illustration not visible in this excerpt

Figure 1.3: Coding operations in the butterfly network

illustration not visible in this excerpt

Thus, why do you do network coding? It allows to increase the information density of a transmission on a given link. This can be used to increase the throughput and thus bandwidth of a link or to enhance the resilience of this link by spending the gained transmitted information on redundancy.

The premise that enables network coding to enhance performance is that in current hardware calculations are much faster than transmissions.

1.1.2. Linear Coding

In linear coding every host not only repeats the packets it forwards, but also com­bines them as linear combinations. To do this smaller packets get padded with 0, so that all input packets are of the same size. The output packet is a linear combination of the input packets. Since it is binary information, the underlying field used for cal­culations is always [Abbildung in dieser Leseprobe nicht enthalten] , usually the coding is done byte wise, so the underlying field is [Abbildung in dieser Leseprobe nicht enthalten] . Linear combinations are taken because linear algebra is simple to use.

1.1.2.1. Encoding

If a host has n input packets of n input lines which are padded to packets of the same length (called M), each symbol of each packet M will gets multiplied by the corresponding coefficient for the packet in the encoding vector g and summed up with the symbols at that location in the other input packets. This sum of the linear combination of the symbols is the symbol at that location of the resulting packet.

illustration not visible in this excerpt

An encoded packet contains the vector g called encoding vector as well as the vec­tor X called information vector.

Already encoded packets can be encoded again at later nodes, this is called recur­sive encoding. In recursive encoding, the elements of the information vector get mul­tiplied again by new coefficients The new encoding vector is then multiplied by the old one.

1.1.2.2. Decoding

The decoding can, but need not, be done on all nodes in the network. It is sufficient to decode only at the receivers, because intermediate nodes do not need to know the packet's data to forward it. A node will store each received packet (g,X) as a row in a matrix representing linear equations with the unknowns [Abbildung in dieser Leseprobe nicht enthalten].

The node will try to solve the matrix as far as possible using e.g. Gaussian elimina­tion. This will transform the matrix into a triangular matrix. If the received packet is innovative (is linearly independent from the stored packets), it will increase the rank of the matrix, if not, it will get eliminated by the Gaussian Algorithm. It will only be possible to solve the whole system with at least [Abbildung in dieser Leseprobe nicht enthalten] rows or more if rows are linearly dependent from each other.

Obviously, it is essential for the efficiency of network coding that the encoding vec­tors are linearly independent. Thus the question is: How to choose the encoding co­efficients for packets, so that they are linearly independent?

1.1.3. Deterministic Coding

Ideally, each node that encodes packets would do this in a way that all encoding vectors in the network are linearly independent, so that each packet is innovative for the receiver. This will only be possible in a centralized deterministic manner if each node has complete knowledge of the network and the coefficients all other nodes use to encode. This is most likely not achievable in real-life setups.

1.1.4. Decentralized network coding

One approach to deterministic network coding without knowing the state of the en­tire network is called decentralized network coding. (see [FRA1])

This type of decentralized network coding is intended for multicast applications.

The basic principle is to span a multicast tree between the senders and the re­ceivers and then perform an operation called subtree decomposition:

Some nodes on this tree get classified into source nodes (nodes that send informa­tion), so called coding points (nodes with at least two inputs) and receiver nodes. Then the multicast tree gets divided into subtrees, so that each subtree contains ex­actly one source node or coding point, every other node should belong to the sub­tree containing its ancestral source node or coding point. In this way, only the con­nections among subtrees are of importance for the network coding design problem, as the structure of the network inside a subtree is unimportant.

To assign a vector of coefficients to each subtree, different algorithms can be used.

For example, one forwards tokens from the sources to the destinations, taking one token for each encoding node. The tokens are created using a different point in the projective line through the underlying finite field, called PG(1,q). In this way, the cod­ing scheme stays the same, even if new nodes are added, as long as the subtree decomposition remains the same.

1.1.5. Random Coding

One practical approach is to choose the encoding coefficients randomly out of the underlying finite field, relying on the even distribution of random numbers. There is a probability, that is dependent on the size of the finite field, that the chosen coeffi­cients result in linearly dependent encoded packets, which will impact performance but this probability vanishes with a sufficient size of the finite field, as shown by [HO03].

This makes random linear network coding the most practical approach because no knowledge of the whole network and the coefficients used by other nodes is neces­sary.

1.2. Peer-to-Peer Swarming

Even in Application layer protocols, network coding can be used to improve through­put and robustness. One typical application for network coding on layer 7 is peer-to- peer file distribution, often called file swarming.

1.2.1. Microsoft Avalanche

The Avalanche project by Microsoft uses a Bittorrent-like approach of swarming a file across peers, meaning that a central server manages a peer-to-peer net that swarms the files. Among the peers are so-called seeds that have the complete file and share it. But instead of exchanging parts of the file like in Bittorrent, each peer sends and receives linear combinations of multiple parts of the file together with a tag describing the linear combination. Each peer will also create new linear combi­nations of pieces it already has decoded.

This way, a peer does not need to have any global knowledge of who has which parts and does not need any specific part. It just needs enough linear combinations to solve the matrix of all linear combinations and reconstruct the original data.

Experiments show that this makes file sharing far more robust and efficient even if the originating seeds leave the network after only one upload.

1.2.2. Codetorrent

Codetorrent is a file-swarming protocol that uses network coding, which is targeted on vehicular ad-hoc networks (VANETs). In future, cars and other vehicles will be equipped with wireless networking connectivity devices which can be used to estab­lish a network between cars, trucks, roadside objects and other vehicles. These net­works are called VANET.

Codetorrent uses random network coding and recoding. Each node that has a file to share (seed) broadcasts a description of that file. If a node is interested in the file, it broadcasts a request. Each node that has a piece or an encoded packet of the file encodes (or re-encodes) the pieces it has and sends them to the node that request­ed them. Each time a node sends out such a packet, it uses a completely new ran­dom encoding vector to (re-) encode the file pieces. With sufficient encoding vec­tors, the receiving node can reconstruct single pieces of the file and finally the com­plete file.

1.3. Haggle

The Haggle Project of the European Union is an approach to explore new paradigms in networking to enable spontaneous, opportunistic communication in wireless networks with only intermittent connectivity and no infrastructure. In net­works like this, classic networking approaches will not work and new communication schemes are needed.

Haggle proposes a radical departure from the existing TCP/IP protocol suite by omit­ting all layers above the data link and use application-level message forwarding in­stead of doing this on the network layer. The target is to provide a lightweight ser­vice layer with only the core necessary functionality that is sufficient to support a large range of current and future applications. The Haggle project's orientation is fo­cused more on the way that humans (or generally communities) communicate rather than based on the technical aspects of communication.

According to [HAG06], Haggle has 3 core components:

1. A revolutionary paradigm for autonomic communication, based on advanced local forwarding and sensitive to realistic human mobility.
2. A simple and powerful architecture oriented to opportunistic message relay­ing, and based on privacy, authentication, trust and advanced data handling.
3. An open environment for the easy proliferation of applications and services, thanks to a top-down approach that aims to reproduce communities' behav­ior, which makes Haggle an ideal paradigm for supporting applications with high social and economic impact.

The research in Haggle is split into seven different areas, so-called work packets:

- WP0 Project Management
- WP1 Node Architecture
- WP2 Communication Architecture
- WP3 Integration and Trials
- WP4 Trusted Communities and Secure Communications
- WP5 Mobility Aware Models and Measurement Testbeds
- WP6 Human Factors
- WP7 Dissemination, Standardization and Exploitation

The work packet 2, Communication Architecture, currently houses three major re­search projects:

Context-based forwarding

This research branch explores the possibility of using contextual information for for­warding decisions.

Self-limiting Epidemic forwarding (SLEF)

This branch tries to define a self-limiting service that broadcasts messages within a scope which adapts to a wide range of conditions, e.g. the count and density of net­work nodes. So the system manages the spreading of broadcast messages accord­ing to the density of nodes and the fraction of actively sending nodes by modifying the packet's TTL (Time-To-Live) through adaptive aging, controlling the forwarding factor by self-inhibition and inter-inhibition as well as controlling the rate of injection by sources.

Innovative Information Dissemination in Ad Hoc Networks with Network Coding

This part of the haggle project aims to create a forwarding scheme for challenged networks, where nodes often disconnect and reconnect, as for example in personal area networks (PANs) or vehicular networks. These networks are often subsumed as "delay-tolerant networks” (DTNs). These networks face additional challenges like heterogeneous types of connected appliances, different types of user behavior (e.g. highly mobile users and stationary users) and user collaboration.

They approach this goal by using network coding for resilience. The proposed net­work coding system in [MOSY06] uses random network coding for the next hop. A node is creating and forwarding linear combinations of received packets and pack­ets in the local buffer with random coefficients before sending them out. The coeffi­cients and unique ids are transmitted in the header of a special packet type whose payloads are the linear combinations. A number specified in the configuration limits the number of packets encoded per transmission.

The receiving node then stores the coefficients in a matrix and attempts a Gaussian pivot elimination step to reduce the order of the equation system. If this step results in the decoding of one or more packets, the node will check if they are intended for this node and process them.

One the one hand, the proposal is implemented in Java as a standalone application, on the other hand it can also be used in the FRANC framework.

FRANC stands for "Framework for Ad hoc Network Communication". It is a lightweight framework tailored to implement and deploy real ad-hoc network appli­cations. It is implemented in Java to be portable and can run on every system that has a Java VM installed. It can also be easily integrated into a simulator. For this so­lution, it was integrated into Jist/Swans, a simulator for mobile ad-hoc networks de­veloped at Cornell University.

FRANC is composed out of three components:

illustration not visible in this excerpt

Figure 1.4: The FRANC framework

(1) The layered protocol stack, its composition is chosen by the user configura­tion.
(2) The services, which are shared portions of code executed aside the protocol stack for common tasks such as for example neighbor detection.
(3) The Recycled message pool which is a mechanism to reuse references to messages to increase performance.
The network coding is implemented as a layer in FRANC's network stack. Its advan­tage is that it is easily exchangeable and the developers can focus on network cod­ing without having to deal with other layers.

The network coding system is demonstrated with an application that offers a dis­tributed bullet-board system (D-BBS).

1.4. COPE

Cope is an approach to practical network coding in wireless environments made by Sachin Katti et al. [KAT05]. It uses the given broadcast nature of each wireless me­dia recognize coding opportunities and introduces a shim layer between the 802.11 MAC layer and the IP layer. Coding is only done for one hop by XORing multiple packets together and broadcasting them to the surrounding nodes.

An example for the coding in Cope is the so-called "Alice and Bob” example. Sup­pose Alice and Bob are two hosts with a router between them. Alice and Bob cannot receive each other's signals, but both can reach the router. Now Alice wants to send a Packet to Bob and vice versa.

illustration not visible in this excerpt

The classical approach would be that Alice sends her packet to the router which sends the packet to Bob, then Bob will send his packet to the router which will send it to Alice.

Using the network coding approach Alice and Bob will both send their packets to the router who will xor both packets together and broadcast the result. Because Alice knows packet a, she can recover packet b from the encoded packet. Bob can do the same with his packet.

Theoretically this approach uses three instead of four transmissions, thus having a throughput gain of 33% called the coding gain. However, experimental results of MIT [KAT05] showed much larger throughput gains, which is caused by the band­width allocation policy of the 802.11 MAC. The MAC tries to distribute the bandwidth evenly between the three hosts, but on the classical approach the sender has to send twice as many packets as the other hosts. This is called the MAC fairness gain.

1.4.1. Opportunistic Listening

In a wireless environment, all nodes share one medium (the radio channel). There­fore all nodes within the radio range of a node overhear all transmissions by all other hosts in their radio range. Normally all transmissions which are not targeted for the node get discarded. However, for some applications , it is useful to snoop every packet. This is exploited, for example, by “wardrivers” who try to break into a wire­less network. In network coding, however, all overheard messages are stored for a certain amount of time (T) in a buffer, so that they can be used to de- or encode a packet.

T is chosen so that it is larger than the maximum latency of a packet, which is in the range of hundred milliseconds. Thus the memory requirement for this buffer will usually not exceed 1 MB which should be available on virtually any device.

Another requirement for Opportunistic listening is that every node must be informed which packets adjacent nodes have overheard. For this purpose, each node informs its neighbors by sending reception reports either with their next transmission or in a special control packet. To identify each single packet COPE uses the sender's IP address concatenated with the IP sequence number.

In heavy congested traffic these reception reports might get lost or arrive too late in very light traffic, therefore it is not reliable that every node knows the overheard packets of other nodes just by the measure of reception reports.

To improve this convergence, COPE implements educated guessing, meaning that a node that receives a packet from a node A guesses that all nodes nearer to A must have heard the packet as well. It can judge the probabilities whether the node received the packet by using the ETX metric.

ETX stands for estimated transmission count and is a specialized metric for lossy links. It tries to find the path with the fewest transmissions while also taking retrans­missions for lost packets into account. It does this by periodically probing links in both directions.

Alternative ways of collecting data for guessing a reception are measuring the signal strength, or using GPS and deciding upon the position if the geographic network structure is known.

The result of opportunistic listening is that each node holds a buffer of packets and knows which packets its neighboring nodes hold.

1.4.2. Opportunistic Coding

The major question in network coding is: "When and how should a node encode packets?” COPE's approach is the opportunistic coding. This means that every time a node wants to transmit a packet from the head of its FIFO queue, it checks if it can XOR other packets out of the queue together with this one, so that it transmits the maximum possible number of packets with one transmission, where each receiv­er has all other packets to decode the transmission and regenerate the packet.

For each transmission a node may have several coding options, so finding the maxi­mum number of packets is an optimization task.

Thus the general rule is:

Each node must find max (n),

illustration not visible in this excerpt

Example for Opportunistic coding (refer to [KAT05])

For example if a node called B has four packets in its delivery queue whose next hops are given in Figure 1.5, it has to decide which packets to encode and broad­cast will deliver the maximum number of packets to their receivers.

illustration not visible in this excerpt

Figure 1.5: Example Packets and next hops of node B

illustration not visible in this excerpt

Figure 1.6: Coding decision 1: A bad coding decision The node will always send packet 1 and now needs to look for possible coding op­tions. It could take the decision shown in Figure 1.6, broadcasting packet 1+2. How­ever this is a bad decision, as C can decode packet P2 because it has packet P1 in its buffer, but A cannot decode packet P1.

The decision shown in Figure 1.7 would be better: P1 is encoded together with P3, so both node A and node C could decode their packet .

illustration not visible in this excerpt

Figure 1.7: Coding decision 2: A better decision

The optimal decision, however, is shown in Figure 1.8. Because both A and C have packet P4 in their buffer, it can be encoded into the transmission as well and as D has packets P1 and P3 in its buffer, it can decode the packet. This way three trans­mission take place in one single transmission.

illustration not visible in this excerpt

Figure 1.8: Coding decision 3: optimal coding decision

This coding scheme avoids packet delay because the first packet in a the transfer queue always gets sent, as it would be without coding. The only difference is that each transmission can hold up more information because multiple packets get XORed together and sent in one transmission.

1.4.3. Opportunistic Routing

In addition to network coding, the effect that nodes overhear packets can be used for opportunistic routing. Opportunistic routing enables packets to skip hops on the route if they get overheard by nodes further downstream. The node has then to find out that it is on the route, either because the route is sent in the header of the packet or because the routing algorithm is simple enough that the node can calculate the route. Then it is important that the packets do not get sent duplicated to avoid pack­et reordering.

Opportunistic routing is best illustrated using this example:

illustration not visible in this excerpt

Figure 1.9: Example for Opportunistic Routing

In this setup, Source S will send a Packet p to receiver R. The routing protocol de­termines the route S,A,B,R. If B overhears the packet sent from S to A, it can see from the route that it is a node further downstream and immediately send the packet to R, saving one transmission.

A receives the reception report of B, so it will not send the packet on to B. Even if A does not get the report on time, B can still discard the packet, if it has kept the pack­et's state in memory, instead of resending it.

1.4.4. Pseudo Broadcast

Instead of using 802.11 broadcasts, COPE defines a special header after the link- layer header which is used for a facility called pseudo broadcast. In this case broad­casts are transferred using unicast packets. The destination MAC is set to one of the target MAC addresses, while all other targets are defined in the additional header.

All nodes listen in promiscuous mode and analyze each packet they capture. If their MAC is in the additional header, they will process the packet. If not, they will buffer it as an opportunistically overheard packet.

This has the major advantage that the 802.11 MAC sends acknowledgments for uni­cast packages and automatically does a backoff if the Ack is missing, which it does not for Broadcast. This leads to bad performance for Broadcasts in congested net­works because every node keeps on resending at the maximum rate, causing colli­sions. So instead of implementing a backoff scheme for broadcasts and having to change the MAC, the pseudo broadcasts exploits the existing 802.11 backoff by hid­ing broadcasts in unicast packages.

1.4.5. Realization of the Cope principle

Cope attaches each packet a special header to transmit additional information.

This header includes the number of encoded packets inside this packet together with the id and next hop of original each packet which are contained in this packet. Furthermore, there is a field for the number of reception reports (of overheard pack­ets) with a list of reports, for each one source ip and the id of the last packet heard from this host is sent and additionally a bit map of the last overheard packets from this host.

The last header field transmits acknowledgments for packets that were received and intended for the host. It consists of a field for the number of acknowledgments, fol­lowed by the packet's local sequence number and a list of ACKs. Each ACK con­tains a field for the neighbor it is directed to, a number of the last packet to acknowl­edge and a bit map containing the cumulated acknowledgments (meaning a bit field representing the last packets with a 1 for an ACK and a 0 for a NACK).

illustration not visible in this excerpt

Figure 1.10: Cope shim header

If the acknowledgment for the coding layer is missing after a timeout, the sender will resend the packet. These are retransmissions that are additional to the retransmis­sions provided by the MAC layer. The number of retransmissions in the Cope layer is configurable.

[...]