BRN-070312-1

Network Coding for Bit-Error Recovery

Abstract

Die drahtlose Übertragung ist auf der physikalischem Ebene erheblich fehleranfälliger im Vergleich zu kabelgebundener Kommunikation. Im Standard IEEE 802.11 sind daher Vorwärtsfehlerkorrektur (FEC) und Automatische Wiederholungsanfragen (ARQ) vorgesehen, um Übertragungsfehler auf ein für höhere Protokollschichten zumutbares Maß zu begrenzen. Beide Techniken sind effektiv, wenn auch nicht optimal, bei der Unicast-Übertragung. Allerdings genügen sie nicht den Anforderungen von neuen Routing-Ansätzen wie Opportunistischem Routing, da das Anycast Link Layer Primitiv nicht abgebildet wird.

Ziel der Diplomarbeit soll es sein, für das Anycast Primitiv ein ARQ Schema mit inkrementeller Redundanz zu entwerfen. Mit einem funktionsfähigen Prototyp für Simulator und BerlinRoofNet Testumgebung soll die Leistungsfähigkeit des Ansatzes beurteilt werden. Da durch die Beschränkung auf COTS IEEE 802.11 Hardware die Datenübertragungs- und Sicherungsschicht unveränderlich ist, muss in der Realisierung entsprechend auf höhere Schichten ausgewichen werden.

Im Rahmen der Arbeit werden folgende Punkte näher betrachtet:

• Fehlererkennung innerhalb von Paketen auf Basis von Fragmenten; Weiterverarbeitung von korrekten Fragmenten innerhalb fehlerhafter Pakete.
• Verarbeitung von Batches als logische Zusammenfassung von Paketen; darin eingeschlossen die zuverlässige Signalisierung des vollständigen Batch-Empfangs am Empfänger.
• Random Linear Network Coding auf Basis von Fragmenten innerhalb eines Batchs zur Minimierung der übertragenen Redundanz.
• Integration einer Variante des opportunistischen Routings entlang der DSR Source Route.
• Verfahren zur Bestimmung der Senderate für netzwerk-kodierte Anycast-Pakete.
• Modellierung von Übertragungsfehlern auf Datenübertragungs- und Sicherungsschicht im Simulator (JiST/SWANS).
• Auswertung der erzielten Systemleistung im Simulator und in der BerlinRoofNet Testumgebung.

Contribution and Related Work

Related Work

• Link Level & Bit Error Measurements
  • MIT Link Level Measurements
  • Henri Dubois-Ferrière, Deborah Estrin, Martin Vetterli (EPFL) “Packet Combining in Sensor Networks”
  • TU Berlin measurements
• Source and Network Coding
  • Reina Riemann, Keith Winstein (MIT) “Improving 802.11 Range with Forward Error Correction”
  • Digital Fountains and Linear Random Network Codes
  • Szymon Chachulski, Michael Jennings, Sachin Katti, Dina Katabi (MIT) “MORE: A Network Coding Approach to Opportunistic Routing”
  • Szymon Chachulski, Michael Jennings, Sachin Katti, Dina Katabi (MIT) "Trading Structure for Randomness in Wireless Opportunistic Routing"
  • Sachin Katti, Hariharan Rahul, Wenjun Hu, Dina Katabi, Muriel Médard, Jon Crowcroft "XORs in The Air: Practical Wireless Network Coding"
• Hybrid ARQ, Packet Combining
  • Allen Miu, Hari Balakrishnan, Can Emre Koksal (EPFL) “Packet Combining in Sensor Networks”
  • Kyle Jamieson, Hari Balakrishnan (MIT) "PPR: Partial Packet Recovery for Wireless Networks"
  • Henri Dubois-Ferrière, Deborah Estrin, Martin Vetterli (MIT) “Improving Loss Resilience with Multi-Radio Diversity in Wireless Networks”
• Opportunistic Routing
  • MIT Biswas
  • Candidate selection and routing metrics: Zhong

Contribution

The combination of partial packet recovery and network coding is expected to unite the benefits from both approaches. Partial packet recovery still creates overhead by sending ACKs for single packets and a system like MORE still drops a lot of packets which could be partially retrieved by splitting them into fragments. Also an intelligent combination of end-to-end network coding and hop-by-hop ACKs may be more efficient than either of the two principles implemented exclusively.

Analysis and Design

Requirements

Constrains

• IEEE 802.11 MAC and PHY
• Preserve ISO/OSI layer separation

Architecture

The architecture is built around existing components of the BRN infrastructure. Especially the MadWifi driver and the DSR routing algorithm are used. All algorithms are implemented using the Click modular routing toolkit. As DSR is also implemented using Click network coding can easily be inserted between the lower part of the link layer, provided by MadWifi and the upper part of the link layer, provided by DSR. Yet not all input and output of DSR is intercepted, only the frames coming from and going into the BRN network are used. The structure of the network coding algorithm can be described in three functionally independent units.

The first part is mainly concerned with encoding and decoding linear combinations of packets. These packets are organized in batches of a specific maximum size. This requires two caches for frames that couldn't be decoded yet or are still needed for encoding. In order to avoid link layer ACK messages all encoded packages are sent in broadcast mode. This means that another element, the decider, is needed to discard packets for which the current node is not among the intended recipients. The recipients can be determined using the source route information included in each packet. If a node receives an (unneeded) encoded packet for a fully decodable batch from an upstream node it will send a STOP packet to that node. Also a STOP packet is sent to the direct predecessor in the source route as soon as a batch can be decoded. The STOP packet is sent reliably with link layer ACK. On the receiving side this STOP message is recognized by the decider and used to signal the encoder to stop sending packets of that batch. Even before sending a STOP packet or being able to decode the packets a node may already forward linear combinations of the packets it has received.

The second part adds the capability for opportunistic routing. The decider is extended so that packets originally intended for nodes upstream in the source route are utilized. This means that multiple nodes can be able to decode a given batch simultaneously and start resending it. This is to be prevented by STOP messages. In order to further prevent excessive congestion and guarantee the delivery of STOP messages a transmission control module is inserted. Based on link statistics obtained from either the low level driver or the annotations in the DSR header and routing information the sending frequency is determined and controlled. For example a node knowing that its successor on the source route can overhear most packets directly from its predecessor will send less packets than a node constituting a bottleneck. Most likely modifications or additions to the lower layer or the DSR elements will be needed to obtain these details and create enough opportunities for shortcuts in the route. Also it might be useful to employ the STOP messages here in order to find out which nodes overheard how much of a given batch, when it was sent by a given node.

The third part, finally, adds the capability to deal with fragments instead of whole packets. An extractor module retrieves the fragments from the original packets before having them decoded by the decoder. An assembler reassembles the original packets from a set of decoded fragments or combines a set of encoded fragments into a new packet. The fragmenter splits up the original packets into fragments that need to be encoded. The decoder and encoder have to be slightly modified so that they can handle fragments instead of packets but their principal functionality remains the same. Also the MadWifi driver needs to be configured to hand out corrupt frames to the upper layers.

Project Plan: Tasks

---

Task 1: Hop-by-Hop NC scheme

• Similar to MORE
• Continuously send randomly (linear) coded packets from a defined batch to the next hop
• Don't send link layer ACKs for any packets
• Stop when next hop has enough correctly transmitted encoded packets to decode all originals.
• A node receiving encoded packets sends a special „STOP“ packet when all packets of a batch could be decoded.
• STOP should be sent reliably – in contrast to data packets. Find a way to accomplish that
• Try to reduce overhead and interference between multiple transmissions (Consider the Tx control from „XORs in the Air“)

Deliverable

• Realization for Simulation and on Netgear Hardware

Deadline: 07.11.2007

Progress: 90% finished

---

Task 2: Extend NC to opportunistic routing

• Make use of „overheard“ packets
• Any downstream node can receive packets from a batch and send STOP if enough information is present
• Any STOP for a given batch prevents upstream recipients of that batch from resending its packets
• Find a route selection algorithm (consider for example MORE's Tx triggers)

Deliverable

• Realization for Simulation and on Netgear Hardware
• Performance Evaluation (report)

Deadline: 21.11.2007

Progress: 90% finished

---

Task 3: Fragment Coding

• Instead of complete packets parts (fragments) are encoded
• Each fragment gets a seperate CRC
• Next node makes use of corrupted packets and extracts the fragments that have been correctly received

Deliverable

• Realization for Simulation and on Netgear Hardware

Deadline: 21.12.2007

Progress: 90% finished

---

Task 4: Performance Evaluation and Optimization

• Sending packets in batches creates a considerable delay and burstiness at the receiver
• Compare that delay with standard WiFi communication
• Which applications can deal with that and which can't?
• Which parameters have an influence on the delay?
• How does the delay change with
  • multi-hop coding
  • resending of partially decoded batches
  • different forms of Tx control
  • sliding window coding
• Larger fragments mean less error recovery because larger parts of the packets have to be discarded
• Smaller fragments mean more overhead for the calculation of CRC and the meta-information in packets
• Evaluate different fragment sizes and find good values for various environments
• What other parameters have an influence on coding efficiency, overhead, delay or throughput?
• Based on these findings estimate the parameters for the coding algorithm at runtime

Deliverable

• Performance Evaluation (report)

Deadline: 31.03.2008

Progress: 0% finished

---

Task 5: Extensions

• multi-hop coding, where packets are resent without decoding them (for simple and opportunistic routing)
• allow the next node to encode parts of the batch and resend them before all packets have been decoded
• regular status reports (for example after x data packets) announcing if a batch could be partially decoded
• generate realistical patterns of packet corruption in a simulation

Deliverable

• Implementation in the context of Tasks 1-3
• Performance Evaluation and Comparison

Deadline: none, optional task to be done if time is left

Progress: 0% finished

References

see my CiteULike site