BRN-070312-1: Difference between revisions

From
Jump to navigation Jump to search
No edit summary
 
(28 intermediate revisions by 2 users not shown)
Line 2: Line 2:


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

<!--
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.
Also an intelligent combination of end-to-end network coding and hop-by-hop ACKs may be more efficient than either of the two principles implemented exclusively.

== Analysis and Design ==

=== Requirements ===

==== Constrains ====
* IEEE 802.11 MAC and PHY
* Preserve ISO/OSI layer separation

==== Out of Scope ====

=== Architecture ===
[[Image:NCarch1.png|right|400px|part 1]]
The architecture is built around existing components of the BRN infrastructure. Especially the MadWifi driver and the DSR routing algorithm are used. All algorithms are implemented using the Click modular routing toolkit. As DSR is also implemented using Click network coding can easily be inserted between the lower part of the link layer, provided by MadWifi and the upper part of the link layer, provided by DSR. Yet not all input and output of DSR is intercepted, only the frames coming from and going into the BRN network are used. The structure of the network coding algorithm can be described in three functionally independent units.

[[Image:NCarch2.png|right|400px|part 2]]
The first part is mainly concerned with encoding and decoding linear combinations of packets. These packets are organized in batches of a specific maximum size. This requires two caches for frames that couldn't be decoded yet or are still needed for encoding. In order to avoid link layer ACK messages all encoded packages are sent in broadcast mode. This means that another element, the decider, is needed to discard packets for which the current node is not among the intended recipients. The recipients can be determined using the source route information included in each packet. If a node receives an (unneeded) encoded packet for a fully decodable batch from an upstream node it will send a STOP packet to that node. Also a STOP packet is sent to the direct predecessor in the source route as soon as a batch can be decoded. The STOP packet is sent reliably with link layer ACK. On the receiving side this STOP message is recognized by the decider and used to signal the encoder to stop sending packets of that batch. Even before sending a STOP packet or being able to decode the packets a node may already forward linear combinations of the packets it has received.

[[Image:NCarch3.png|right|400px|part 3]]
The second part adds the capability for opportunistic routing. The decider is extended so that packets originally intended for nodes upstream in the source route are utilized. This means that multiple nodes can be able to decode a given batch simultaneously and start resending it. This is to be prevented by STOP messages. In order to further prevent excessive congestion and guarantee the delivery of STOP messages a transmission control module is inserted. Based on link statistics obtained from either the low level driver or the annotations in the DSR header and routing information the sending frequency is determined and controlled. For example a node knowing that its successor on the source route can overhear most packets directly from its predecessor will send less packets than a node constituting a bottleneck. Most likely modifications or additions to the lower layer or the DSR elements will be needed to obtain these details and create enough opportunities for shortcuts in the route. Also it might be useful to employ the STOP messages here in order to find out which nodes overheard how much of a given batch, when it was sent by a given node.

The third part, finally, adds the capability to deal with fragments instead of whole packets. An extractor module retrieves the fragments from the original packets before having them decoded by the decoder. An assembler reassembles the original packets from a set of decoded fragments or combines a set of encoded fragments into a new packet. The fragmenter splits up the original packets into fragments that need to be encoded. The decoder and encoder have to be slightly modified so that they can handle fragments instead of packets but their principal functionality remains the same. Also the MadWifi driver needs to be configured to hand out corrupt frames to the upper layers.


== Project Plan: Tasks ==
== Project Plan: Tasks ==
Line 7: Line 73:
=== Milestones ===
=== Milestones ===


----
alle Tasks mit Deadline und Zeiger auf aktuellen Stand


=== Tasks 1 ===
=== 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'''
* Description

* Extensions
* Realization for Simulation and on Netgear Hardware
* Deliverable

* Deadline
'''Deadline: 07.11.2007'''
* Progress: 0% finished

'''Progress: 90% 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: 21.11.2007'''

'''Progress: 90% 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: 21.12.2007'''

'''Progress: 90% 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: 31.03.2008'''

'''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 ==
== References ==

see [http://www.citeulike.org/user/fonso/tag/brn-070312-1 my CiteULike site]

Latest revision as of 14:13, 26 February 2008

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. Also an intelligent combination of end-to-end network coding and hop-by-hop ACKs may be more efficient than either of the two principles implemented exclusively.

Analysis and Design

Requirements

Constrains

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

Out of Scope

Architecture

part 1

The architecture is built around existing components of the BRN infrastructure. Especially the MadWifi driver and the DSR routing algorithm are used. All algorithms are implemented using the Click modular routing toolkit. As DSR is also implemented using Click network coding can easily be inserted between the lower part of the link layer, provided by MadWifi and the upper part of the link layer, provided by DSR. Yet not all input and output of DSR is intercepted, only the frames coming from and going into the BRN network are used. The structure of the network coding algorithm can be described in three functionally independent units.

part 2

The first part is mainly concerned with encoding and decoding linear combinations of packets. These packets are organized in batches of a specific maximum size. This requires two caches for frames that couldn't be decoded yet or are still needed for encoding. In order to avoid link layer ACK messages all encoded packages are sent in broadcast mode. This means that another element, the decider, is needed to discard packets for which the current node is not among the intended recipients. The recipients can be determined using the source route information included in each packet. If a node receives an (unneeded) encoded packet for a fully decodable batch from an upstream node it will send a STOP packet to that node. Also a STOP packet is sent to the direct predecessor in the source route as soon as a batch can be decoded. The STOP packet is sent reliably with link layer ACK. On the receiving side this STOP message is recognized by the decider and used to signal the encoder to stop sending packets of that batch. Even before sending a STOP packet or being able to decode the packets a node may already forward linear combinations of the packets it has received.

part 3

The second part adds the capability for opportunistic routing. The decider is extended so that packets originally intended for nodes upstream in the source route are utilized. This means that multiple nodes can be able to decode a given batch simultaneously and start resending it. This is to be prevented by STOP messages. In order to further prevent excessive congestion and guarantee the delivery of STOP messages a transmission control module is inserted. Based on link statistics obtained from either the low level driver or the annotations in the DSR header and routing information the sending frequency is determined and controlled. For example a node knowing that its successor on the source route can overhear most packets directly from its predecessor will send less packets than a node constituting a bottleneck. Most likely modifications or additions to the lower layer or the DSR elements will be needed to obtain these details and create enough opportunities for shortcuts in the route. Also it might be useful to employ the STOP messages here in order to find out which nodes overheard how much of a given batch, when it was sent by a given node.

The third part, finally, adds the capability to deal with fragments instead of whole packets. An extractor module retrieves the fragments from the original packets before having them decoded by the decoder. An assembler reassembles the original packets from a set of decoded fragments or combines a set of encoded fragments into a new packet. The fragmenter splits up the original packets into fragments that need to be encoded. The decoder and encoder have to be slightly modified so that they can handle fragments instead of packets but their principal functionality remains the same. Also the MadWifi driver needs to be configured to hand out corrupt frames to the upper layers.

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: 07.11.2007

Progress: 90% 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: 21.11.2007

Progress: 90% 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: 21.12.2007

Progress: 90% 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: 31.03.2008

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

Retrieved from "https://sarwiki.informatik.hu-berlin.de/index.php?title=BRN-070312-1&oldid=8383"