BRN-070312-1

Network Coding for Bit-Error Recovery

Abstract

Forschungsergebnisse im Bereich der Drahtlosnetzwerke zeigen, dass Network Coding eine verheißungsvolle Technologie zur Steigerung der Durchsatzraten ist.

Diese Erkenntnisse werden genutzt und weiterentwickelt, indem Network Coding zur Verringerung des Effekts von Bitfehlern und verkürzten Paketen in 802.11-Paketen benutzt wird. Betrachtet wird der Fall von Unicast-Übertragungen auf einer, durch das Routing vorgegebenen, Linkstrecke. Aufbauend auf bestehenden BRN-Technologien wird ein System implementiert, das Mengen von Quellpaketen zu Bündeln zusammenfasst, Fragmente von Paketen einem Bündel miteinander linear kodiert, zu neuen Paketen zusammenstellt und so redundant überträgt. Aus fehlerhaft empfangenen Paketen werden diejenigen Teile extrahiert, die nicht von Bitfehlern oder Verkürzungen betroffen sind. Diese korrekt übertragenen Teile dienen als Grundlage für die Dekodierung der ursprünglichen Fragmente. Dieses Verfahren wird mit einem Mechanismus zur Steuerung von Retransmissionen kombiniert, der auf der Basis von Bündeln als kleinste Einheiten arbeitet. Dabei sendet der Empfänger eine Empfangsbestätigung sobald alle Quellpakete eines Bündels vollständig dekodiert werden können. Bis zum Eintreffen der Empfangsbestätigung sendet der Sender weitere Linearkombinationen von Fragmenten des selben Bündels.

Dieses System, sowie sinnvolle Modifikationen und Erweiterungen werden bezüglich ihrer Leistungsfähigkeit analysiert und mit bestehenden, ähnlichen Ansätzen verglichen.

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.

Analysis and Design

Requirements

Constrains

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

Project Plan: Tasks

Milestones

alle Tasks mit Deadline und Zeiger auf aktuellen Stand

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.

Extensions

• multi-hop coding, where packets are resent without decoding them
• allow the next node to encode parts of the batch and resend them before all packets have been decoded

Deliverable

Deadline: xx.xx.xxxx

Progress: 0% finished

Task 2: Transmission control scheme („STOP“)

• 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“)

Extensions

• regular status reports (for example after x data packets) announcing if a batch could be partially decoded
• relay STOP packets over multiple links in case of multi-hop coding

Deliverable

Deadline: xx.xx.xxxx

Progress: 0% finished

Task 3: 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)

Extensions

• multi-hop coding in opportunistic environment like MORE
• forward newly combined packets before the batch is completely received (how to prevent spurious Tx with OR?)

Deliverable

Deadline: xx.xx.xxxx

Progress: 0% finished

Task 4: 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

Extensions

• Is there a way to generate realistical patterns of bit errors and truncations in a simulation?

Deliverable

Deadline: xx.xx.xxxx

Progress: 0% finished

Task 5: 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

Extensions

Deliverable

Deadline: xx.xx.xxxx

Progress: 0% finished

References

link to your citeulike site, using the tag BRN-070312-1