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.
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