BRN-070312-1

Network Coding for Bit-Error Recovery

Abstract

In drahtlosen Netzwerken treten erheblich mehr Bitfehler und verkürzte Pakete auf als in kabelgebundenen. Dies beruht auf der inhärenten Multicast-Eigenschaft des Mediums und den damit verbundenen Interferenzen, sowie dem Hintergrundrauschen des Mediums selbst. Korrupte Pakete treten jedoch, je nach Rahmenbedingungen, in stark schwankenden Häufigkeiten auf. Forschungsergebnisse im Bereich der Drahtlosnetzwerke zeigen, dass Network Coding eine Möglichkeit bietet, korrupte Pakete mit adaptiver Redundanz zu erkennen und korrekt übertragene Anteile zu extrahieren. In diesem Zusammenhang ist opportunistisches Routing eine sinnvolle Ergänzung. Oft werden Pakete von verschiedenen Knoten empfangen. Opportunistisches Routing baut darauf, dass es eine bestimmte Wahrscheinlichkeit gibt, dass mehrere Knoten ein Paket empfangen und es daher günstig ist, den Knoten der das Paket auf einer Route weiterreicht erst nach dem Empfangen zu bestimmen. Dieses Prinzip läst sich direkt mit Network Coding erweitern, indem die Knoten auch opportunistisch empfangene korrupte Pakete zur späteren Dekodierung aufheben. Da, wie Messungen zeigen, die Übertragungsfehler bei den Empfängern weitgehend unabhängig voneinander sind, bietet dies einen Informationsgewinn.

Diese Erkenntnisse werden genutzt und weiterentwickelt, indem Network Coding zur Verringerung des Effekts von korrupten Paketen in 802.11-Paketen benutzt wird. Betrachtet wird zunächst 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 Batches zusammenfasst, Fragmente von Paketen einem Batch 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 Batches als kleinste Einheiten arbeitet. Dabei sendet der Empfänger eine Empfangsbestätigung sobald alle Quellpakete eines Batches vollständig dekodiert werden können. Bis zum Eintreffen der Empfangsbestätigung sendet der Sender weitere Linearkombinationen von Fragmenten des selben Batches.

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

see my CiteULike site