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

Tasks 1

• Description
  • 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
  • adaptively add new packets to the batch if parts of it could be decoded at the receiver (sliding window)
• Deliverable
• Deadline
• Progress: 0% finished

References

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