BRN-070312-1

From
Revision as of 19:22, 21 March 2007 by Kurth (talk | contribs) (→‎Abstract)
Jump to navigation Jump to search

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 Pakete


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

Out of Scope

Architecture

Project Plan: Tasks

Milestones


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: xx.xx.xxxx

Progress: 0% 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: xx.xx.xxxx

Progress: 0% 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: xx.xx.xxxx

Progress: 0% 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: xx.xx.xxxx

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