BRN-070312-1 - Revision history

Uhermann: /* Task 4: Performance Evaluation and Optimization */

2008-02-26T14:13:46Z

Task 4: Performance Evaluation and Optimization

← Older revision		Revision as of 14:13, 26 February 2008
Line 146:		Line 146:
	* Performance Evaluation (report)		* Performance Evaluation (report)

	'''Deadline: 31.01.2008'''		'''Deadline: 31.03.2008'''

	'''Progress: 0% finished'''		'''Progress: 0% finished'''

Uhermann: /* Task 3: Fragment Coding */

2008-02-26T14:12:51Z

Task 3: Fragment Coding

← Older revision		Revision as of 14:12, 26 February 2008
Line 122:		Line 122:
	'''Deadline: 21.12.2007'''		'''Deadline: 21.12.2007'''

	'''Progress: 0% finished'''		'''Progress: 90% finished'''

	----		----

Uhermann: /* Task 2: Extend NC to opportunistic routing */

2008-02-26T14:12:33Z

Task 2: Extend NC to opportunistic routing

← Older revision		Revision as of 14:12, 26 February 2008
Line 107:		Line 107:
	'''Deadline: 21.11.2007'''		'''Deadline: 21.11.2007'''

	'''Progress: 50% finished'''		'''Progress: 90% finished'''

	----		----

Uhermann at 11:33, 24 October 2007

2007-10-24T11:33:42Z

← Older revision		Revision as of 11:33, 24 October 2007
Line 45:		Line 45:
	===Contribution===		===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.		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 ==		== Analysis and Design ==
Line 61:		Line 62:

	[[Image:NCarch2.png\|right\|400px\|part 2]]		[[Image:NCarch2.png\|right\|400px\|part 2]]
	The first part is mainly concerned with encoding and decoding linear combinations of ~~ethernet~~ ~~frames~~. 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 ~~frames~~ are sent in broadcast mode. This means that another element, the decider, is needed to discard ~~frames~~ for which the current node is not among the intended recipients. The recipients can be determined using the source route information included in each ~~frame~~. ~~After~~ ~~successfully~~ ~~decoding~~ a batch of ~~frames~~ the ~~decoder~~ ~~emits~~ a STOP ~~message~~ ~~which~~ 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.		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]]		[[Image:NCarch3.png\|right\|400px\|part 3]]
	The second part adds the capability for opportunistic routing. The decider is extended so that ~~it frames~~ 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 the low level driver 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 ~~frames~~ directly from its predecessor will send less packets than a node constituting a bottleneck. Most likely modifications or additions to the lower layer will be needed to obtain these details. 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, ~~before~~ it was sent by a given node.		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 ~~ethernet frames~~. An extractor module retrieves the fragments from ~~ethernet~~ ~~frames~~ before having them decoded by the decoder. An assembler reassembles the original ~~frames~~ from a set of decoded fragments or combines a set of encoded fragments into a new ~~frame~~. The fragmenter splits up the original ~~frames~~ into fragments that need to be encoded. The decoder and encoder have to be slightly modified so that they can handle fragments instead of ~~frames~~ but their principal functionality remains the same. Also the MadWifi driver needs to be configured to hand out corrupt frames to the upper layers.		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 ==

Uhermann at 11:15, 24 October 2007

2007-10-24T11:15:13Z

← Older revision		Revision as of 11:15, 24 October 2007
Line 87:		Line 87:
	* Realization for Simulation and on Netgear Hardware		* Realization for Simulation and on Netgear Hardware

	'''Deadline: xx.xx.~~xxxx~~'''		'''Deadline: 07.11.2007'''

	'''Progress: 0% finished'''		'''Progress: 90% finished'''

	----		----
Line 104:		Line 104:
	* Performance Evaluation (report)		* Performance Evaluation (report)

	'''Deadline: xx.xx.~~xxxx~~'''		'''Deadline: 21.11.2007'''

	'''Progress: 0% finished'''		'''Progress: 50% finished'''

	----		----
Line 119:		Line 119:
	* Realization for Simulation and on Netgear Hardware		* Realization for Simulation and on Netgear Hardware

	'''Deadline: xx.xx.~~xxxx~~'''		'''Deadline: 21.12.2007'''

	'''Progress: 0% finished'''		'''Progress: 0% finished'''
Line 145:		Line 145:
	* Performance Evaluation (report)		* Performance Evaluation (report)

	'''Deadline: xx.xx.~~xxxx~~'''		'''Deadline: 31.01.2008'''

	'''Progress: 0% finished'''		'''Progress: 0% finished'''

Kurth: /* Architecture */

2007-04-21T15:14:41Z

Architecture

← Older revision		Revision as of 15:14, 21 April 2007
Line 57:		Line 57:

	=== Architecture ===		=== Architecture ===
	[[Image:NCarch1.png\|right\|~~150px~~\|part 1]]		[[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.		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\|~~150px~~\|part 2]]		[[Image:NCarch2.png\|right\|400px\|part 2]]
	The first part is mainly concerned with encoding and decoding linear combinations of ethernet frames. 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 frames are sent in broadcast mode. This means that another element, the decider, is needed to discard frames for which the current node is not among the intended recipients. The recipients can be determined using the source route information included in each frame. After successfully decoding a batch of frames the decoder emits a STOP message which 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.		The first part is mainly concerned with encoding and decoding linear combinations of ethernet frames. 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 frames are sent in broadcast mode. This means that another element, the decider, is needed to discard frames for which the current node is not among the intended recipients. The recipients can be determined using the source route information included in each frame. After successfully decoding a batch of frames the decoder emits a STOP message which 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.

	[[Image:NCarch3.png\|right\|~~150px~~\|part 3]]		[[Image:NCarch3.png\|right\|400px\|part 3]]
	The second part adds the capability for opportunistic routing. The decider is extended so that it frames 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 the low level driver 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 frames directly from its predecessor will send less packets than a node constituting a bottleneck. Most likely modifications or additions to the lower layer will be needed to obtain these details. 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, before it was sent by a given node.		The second part adds the capability for opportunistic routing. The decider is extended so that it frames 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 the low level driver 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 frames directly from its predecessor will send less packets than a node constituting a bottleneck. Most likely modifications or additions to the lower layer will be needed to obtain these details. 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, before it was sent by a given node.

Uhermann: /* Architecture */

2007-04-19T21:01:22Z

Architecture

← Older revision		Revision as of 21:01, 19 April 2007
Line 57:		Line 57:

	=== Architecture ===		=== Architecture ===
		⚫	[[Image:NCarch1.png\|right\|150px\|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.		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:~~NCarch1~~.png\|right\|~~250px~~\|part 1]]		[[Image:NCarch2.png\|right\|150px\|part 2]]
	The first part is mainly concerned with encoding and decoding linear combinations of ethernet frames. 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 frames are sent in broadcast mode. This means that another element, the decider, is needed to discard frames for which the current node is not among the intended recipients. The recipients can be determined using the source route information included in each frame. After successfully decoding a batch of frames the decoder emits a STOP message which 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.		The first part is mainly concerned with encoding and decoding linear combinations of ethernet frames. 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 frames are sent in broadcast mode. This means that another element, the decider, is needed to discard frames for which the current node is not among the intended recipients. The recipients can be determined using the source route information included in each frame. After successfully decoding a batch of frames the decoder emits a STOP message which 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.

	[[Image:~~NCarch2~~.png\|right\|~~250px~~\|part 2]]		[[Image:NCarch3.png\|right\|150px\|part 3]]
	The second part adds the capability for opportunistic routing. The decider is extended so that it frames originally intended for nodes upstream in the source route are utilized. This means that multiple nodes can be able to decode a given batch ~~simultaniously~~ 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 the low level driver 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 frames directly from its predecessor will send less packets than a node constituting a bottleneck. Most likely modifications or additions to the lower layer will be needed to obtain these details. 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, before it was sent by a given node.		The second part adds the capability for opportunistic routing. The decider is extended so that it frames 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 the low level driver 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 frames directly from its predecessor will send less packets than a node constituting a bottleneck. Most likely modifications or additions to the lower layer will be needed to obtain these details. 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, before it was sent by a given node.

⚫	[[Image:~~NCarch3~~.png\|right\|~~250px~~\|part 3]]
	The third part, finally, adds the capability to deal with fragments instead of whole ethernet frames. An extractor module retrieves the fragments from ethernet frames before having them decoded by the decoder. An assembler reassembles the original frames from a set of decoded fragments or combines a set of encoded fragments into a new frame. The fragmenter splits up the original frames into fragments that need to be encoded. The decoder and encoder have to be slightly modified so that they can handle fragments instead of frames but their principal functionality remains the same. Also the MadWifi driver needs to be configured to hand out corrupt frames to the upper layers.		The third part, finally, adds the capability to deal with fragments instead of whole ethernet frames. An extractor module retrieves the fragments from ethernet frames before having them decoded by the decoder. An assembler reassembles the original frames from a set of decoded fragments or combines a set of encoded fragments into a new frame. The fragmenter splits up the original frames into fragments that need to be encoded. The decoder and encoder have to be slightly modified so that they can handle fragments instead of frames but their principal functionality remains the same. Also the MadWifi driver needs to be configured to hand out corrupt frames to the upper layers.

Uhermann: /* Architecture */

2007-04-19T20:55:40Z

Architecture

← Older revision		Revision as of 20:55, 19 April 2007
Line 57:		Line 57:

	=== Architecture ===		=== Architecture ===

			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:NCarch1.png\|right\|250px\|part 1]]
			The first part is mainly concerned with encoding and decoding linear combinations of ethernet frames. 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 frames are sent in broadcast mode. This means that another element, the decider, is needed to discard frames for which the current node is not among the intended recipients. The recipients can be determined using the source route information included in each frame. After successfully decoding a batch of frames the decoder emits a STOP message which 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.

			[[Image:NCarch2.png\|right\|250px\|part 2]]
			The second part adds the capability for opportunistic routing. The decider is extended so that it frames originally intended for nodes upstream in the source route are utilized. This means that multiple nodes can be able to decode a given batch simultaniously 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 the low level driver 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 frames directly from its predecessor will send less packets than a node constituting a bottleneck. Most likely modifications or additions to the lower layer will be needed to obtain these details. 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, before it was sent by a given node.

			[[Image:NCarch3.png\|right\|250px\|part 3]]
			The third part, finally, adds the capability to deal with fragments instead of whole ethernet frames. An extractor module retrieves the fragments from ethernet frames before having them decoded by the decoder. An assembler reassembles the original frames from a set of decoded fragments or combines a set of encoded fragments into a new frame. The fragmenter splits up the original frames into fragments that need to be encoded. The decoder and encoder have to be slightly modified so that they can handle fragments instead of frames 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 ==

Kurth: /* Abstract */

2007-03-21T19:34:43Z

Abstract

← Older revision		Revision as of 19:34, 21 March 2007
Line 11:		Line 11:
	* Random Linear Network Coding auf Basis von Fragmenten innerhalb eines Batchs zur Minimierung der übertragenen Redundanz.		* 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.		* Integration einer Variante des opportunistischen Routings entlang der DSR Source Route.
	* Verfahren zur Bestimmung der Senderate für netzwerk-kodierte Pakete.		* 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.

	<!--		<!--

Kurth: /* Abstract */

2007-03-21T19:22:44Z

Abstract

← Older revision		Revision as of 19:22, 21 March 2007
Line 8:		Line 8:
	Im Rahmen der Arbeit werden folgende Punkte näher betrachtet:		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.		* 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		* 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		* 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		* Integration einer Variante des opportunistischen Routings entlang der DSR Source Route.
	* Verfahren zur Bestimmung der Senderate für netzwerk-kodierte Pakete		* Verfahren zur Bestimmung der Senderate für netzwerk-kodierte Pakete.

	<!--		<!--