Opportunistic Routing - Revision history

Frank Lange: /* Stage 1: Select Forwarding Candidates */

2012-12-14T20:33:43Z

Stage 1: Select Forwarding Candidates

← Older revision		Revision as of 20:33, 14 December 2012
Line 41:		Line 41:
	[[Image:Example_net.png]]		[[Image:Example_net.png]]

	As mentioned above, there may be other strategies for other topologies. Imagine a relatively dense network, where all nodes in the set of ''forwarding candidates'' would be relatively far away from the sending node. The result would be, that the probability that one of them successfully receives the packet is small, resulting in multiple retransmissions of the packet. The selection of ''forwarding candidates'' ~~sould~~ assure that there are always some nodes near the transmitting node in the set.		As mentioned above, there may be other strategies for other topologies. Imagine a relatively dense network, where all nodes in the set of ''forwarding candidates'' would be relatively far away from the sending node. The result would be, that the probability that one of them successfully receives the packet is small, resulting in multiple retransmissions of the packet. The selection of ''forwarding candidates'' should assure that there are always some nodes near the transmitting node in the set.

	=== Stage 2: Acknowledgements ===		=== Stage 2: Acknowledgements ===

217.93.27.39: /* References */

2005-04-25T21:12:20Z

References

← Older revision		Revision as of 21:12, 25 April 2005
Line 79:		Line 79:
	== References ==		== References ==

	Origin of this page is the [http://sar.informatik.hu-berlin.de/teaching/2004-w%20Ad-Hoc%20Networks/index.htm Ad-Hoc Networks Seminar] in WS 2004/05 organized by the [http://sar.informatik.hu-berlin.de Systems Architecture Group] at [http://www.hu-berlin.de Humboldt University Berlin], in which [http://www.informatik.hu-berlin/~mstigge Martin Stigge] talked about that topic (using [http://www.informatik.hu-berlin.de/~mstigge/ad-hoc-networks/opportunistic_routing.pdf some pdf slides]) and created [[Opportunistic_Routing\|this page]] (self reference: see 'self reference'). Most of the content is based on the paper [http://sar.informatik.hu-berlin.de/teaching/2004-w%20Ad-Hoc%20Networks/readings/1.pdf Opportunistic Routing in Multi-Hop Wireless Networks] by Sanjit Biswas and Robert Mirros (MIT, 2004).		Origin of this page is the [http://sar.informatik.hu-berlin.de/teaching/_previous-years/2004-w%20Ad-Hoc%20Networks/index.htm Ad-Hoc Networks Seminar] in WS 2004/05 organized by the [http://sar.informatik.hu-berlin.de Systems Architecture Group] at [http://www.hu-berlin.de Humboldt University Berlin], in which [http://www.informatik.hu-berlin/~mstigge Martin Stigge] talked about that topic (using [http://www.informatik.hu-berlin.de/~mstigge/ad-hoc-networks/opportunistic_routing.pdf some pdf slides]) and created [[Opportunistic_Routing\|this page]] (self reference: see 'self reference'). Most of the content is based on the paper [http://sar.informatik.hu-berlin.de/teaching/_previous-years/2004-w%20Ad-Hoc%20Networks/readings/1.pdf Opportunistic Routing in Multi-Hop Wireless Networks] by Sanjit Biswas and Robert Mirros (MIT, 2004).

	Please see also [[Ad-Hoc Networks]] for other aspects of Ad-Hoc Networks discussed in our seminar.		Please see also [[Ad-Hoc Networks]] for other aspects of Ad-Hoc Networks discussed in our seminar.

217.93.18.52: revert

2005-04-23T21:51:23Z

revert

← Older revision		Revision as of 21:51, 23 April 2005
Line 61:		Line 61:
	Let's face the example net for the last time:		Let's face the example net for the last time:

			[[Image:Example_net.png]]
	[[]]

	A packet is sent from node A to node D with a ''candidate set'' of (D, C, B). Let's assume, B and C receive the packet, but D doesn't. The ACK-slots are used as follows:		A packet is sent from node A to node D with a ''candidate set'' of (D, C, B). Let's assume, B and C receive the packet, but D doesn't. The ACK-slots are used as follows:

195.132.46.200: /* Example transmission using ''ExOR'' */

2005-04-23T20:03:29Z

Example transmission using ''ExOR''

← Older revision		Revision as of 20:03, 23 April 2005
Line 61:		Line 61:
	Let's face the example net for the last time:		Let's face the example net for the last time:

			[[]]
	[[Image:Example_net.png]]

	A packet is sent from node A to node D with a ''candidate set'' of (D, C, B). Let's assume, B and C receive the packet, but D doesn't. The ACK-slots are used as follows:		A packet is sent from node A to node D with a ''candidate set'' of (D, C, B). Let's assume, B and C receive the packet, but D doesn't. The ACK-slots are used as follows:

217.93.22.81: /* References */

2005-02-09T22:56:59Z

References

← Older revision		Revision as of 22:56, 9 February 2005
Line 79:		Line 79:
	== References ==		== References ==

	Origin of this page is the [http://sar.informatik.hu-berlin.de/teaching/2004-w%20Ad-Hoc%20Networks/index.htm Ad-Hoc Networks Seminar] in WS 2004/05 organized by the [http://sar.informatik.hu-berlin.de Systems Architecture Group] at [http://www.hu-berlin.de Humboldt University Berlin], in which [http://www.informatik.hu-berlin/~mstigge Martin Stigge] talked about that topic (using [http://www.informatik.hu-berlin.de/~mstigge/ad-hoc-networks/opportunistic_routing.pdf some pdf ~~foils~~]) and created [[Opportunistic_Routing\|this page]] (self reference: see 'self reference'). Most of the content is based on the paper [http://sar.informatik.hu-berlin.de/teaching/2004-w%20Ad-Hoc%20Networks/readings/1.pdf Opportunistic Routing in Multi-Hop Wireless Networks] by Sanjit Biswas and Robert Mirros (MIT, 2004).		Origin of this page is the [http://sar.informatik.hu-berlin.de/teaching/2004-w%20Ad-Hoc%20Networks/index.htm Ad-Hoc Networks Seminar] in WS 2004/05 organized by the [http://sar.informatik.hu-berlin.de Systems Architecture Group] at [http://www.hu-berlin.de Humboldt University Berlin], in which [http://www.informatik.hu-berlin/~mstigge Martin Stigge] talked about that topic (using [http://www.informatik.hu-berlin.de/~mstigge/ad-hoc-networks/opportunistic_routing.pdf some pdf slides]) and created [[Opportunistic_Routing\|this page]] (self reference: see 'self reference'). Most of the content is based on the paper [http://sar.informatik.hu-berlin.de/teaching/2004-w%20Ad-Hoc%20Networks/readings/1.pdf Opportunistic Routing in Multi-Hop Wireless Networks] by Sanjit Biswas and Robert Mirros (MIT, 2004).

	Please see also [[Ad-Hoc Networks]] for other aspects of Ad-Hoc Networks discussed in our seminar.		Please see also [[Ad-Hoc Networks]] for other aspects of Ad-Hoc Networks discussed in our seminar.

217.231.251.83: /* References */

2005-02-08T23:13:02Z

References

← Older revision		Revision as of 23:13, 8 February 2005
Line 79:		Line 79:
	== References ==		== References ==

	Origin of this page is the [http://sar.informatik.hu-berlin.de/teaching/2004-w%20Ad-Hoc%20Networks/index.htm Ad-Hoc Networks Seminar] in WS 2004/05 organized by the [http://sar.informatik.hu-berlin.de Systems Architecture Group] at [http://www.hu-berlin.de Humboldt University Berlin], in which [http://www.informatik.hu-berlin/~mstigge Martin Stigge] talked about that topic (using [http://www.informatik.hu-berlin.de/~mstigge/ad-hoc-networks/opportunistic_routing.pdf some pdf foils]) and created [[Opportunistic_Routing\|this page]] (self reference: see 'self reference'). Most of the content is based on the paper [http://sar.informatik.hu-berlin.de/teaching/2004-w%20Ad-Hoc%20Networks/readings/1.pdf ~~Opportinustic~~ Routing in Multi-Hop Wireless Networks] by Sanjit Biswas and Robert Mirros (MIT, 2004).		Origin of this page is the [http://sar.informatik.hu-berlin.de/teaching/2004-w%20Ad-Hoc%20Networks/index.htm Ad-Hoc Networks Seminar] in WS 2004/05 organized by the [http://sar.informatik.hu-berlin.de Systems Architecture Group] at [http://www.hu-berlin.de Humboldt University Berlin], in which [http://www.informatik.hu-berlin/~mstigge Martin Stigge] talked about that topic (using [http://www.informatik.hu-berlin.de/~mstigge/ad-hoc-networks/opportunistic_routing.pdf some pdf foils]) and created [[Opportunistic_Routing\|this page]] (self reference: see 'self reference'). Most of the content is based on the paper [http://sar.informatik.hu-berlin.de/teaching/2004-w%20Ad-Hoc%20Networks/readings/1.pdf Opportunistic Routing in Multi-Hop Wireless Networks] by Sanjit Biswas and Robert Mirros (MIT, 2004).

	Please see also [[Ad-Hoc Networks]] for other aspects of Ad-Hoc Networks discussed in our seminar.		Please see also [[Ad-Hoc Networks]] for other aspects of Ad-Hoc Networks discussed in our seminar.

217.231.251.83: /* Evaluation and Simulation Results */

2005-02-08T23:09:34Z

Evaluation and Simulation Results

← Older revision		Revision as of 23:09, 8 February 2005
Line 75:		Line 75:
	== Evaluation and Simulation Results ==		== Evaluation and Simulation Results ==

	As the authors of the paper on which this page is based on pointed out, ''ExOR'' can be implemented using standard 802.11 hardware with only minor firmware modifications. Simulations showed, that the total number of transmissions required to route a packet from source to destination in a MANET can be improved by 55-65% in comparison to the best predetermined route (from the wired model) and that the successful transmission distances are better distributed (which may make us all [http://www.informatik.hu-berlin.de/~mstigge/downloads/smile.html very happy]). Please have a look at the paper for more details about the implementation into 802.11 hardware and some more detailled simulation results.		As the authors of the paper on which this page is based pointed out, ''ExOR'' can be implemented using standard 802.11 hardware with only minor firmware modifications. Simulations showed, that the total number of transmissions required to route a packet from source to destination in a MANET can be improved by 55-65% in comparison to the best predetermined route (from the wired model) and that the successful transmission distances are better distributed (which may make us all [http://www.informatik.hu-berlin.de/~mstigge/downloads/smile.html very happy]). Please have a look at the paper for more details about the implementation into 802.11 hardware and some more detailled simulation results.

	== References ==		== References ==

217.231.251.83: /* Stage 3: Forwarding Decision */

2005-02-08T23:08:29Z

Stage 3: Forwarding Decision

← Older revision		Revision as of 23:08, 8 February 2005
Line 55:		Line 55:
	This stage of ''ExOR'' is rather simple, because after all nodes received not only the packet but also a (hopefully) large subset of acknowledgements, they can easily decide whether they act as the forwarding node: The packet is forwarded iff the highest known ACK-ID is not greater than (means: equal to) the ID of the node itself.		This stage of ''ExOR'' is rather simple, because after all nodes received not only the packet but also a (hopefully) large subset of acknowledgements, they can easily decide whether they act as the forwarding node: The packet is forwarded iff the highest known ACK-ID is not greater than (means: equal to) the ID of the node itself.

	As said above, this mechanism somehow reduces ~~dublicates~~, but doesn't eleminate them completely, in some cases. (Imagine a node which doesn't receive any ACKs from other nodes but is not the best candidate). An ID cache should be used to reduce duplicates even more.		As said above, this mechanism somehow reduces duplicates, but doesn't eleminate them completely, in some cases. (Imagine a node which doesn't receive any ACKs from other nodes but is not the best candidate). An ID cache should be used to reduce duplicates even more.

	=== Example transmission using ''ExOR'' ===		=== Example transmission using ''ExOR'' ===

217.231.251.83: /* Stage 2: Acknowledgements */

2005-02-08T23:05:20Z

Stage 2: Acknowledgements

← Older revision		Revision as of 23:05, 8 February 2005
Line 45:		Line 45:
	=== Stage 2: Acknowledgements ===		=== Stage 2: Acknowledgements ===

	After sending the packet, it's important that all candidate ~~notes~~ somehow agree who will be the forwarding node. This done by acknowledgements (ACKs), which are sent in defined time-slots directly after the successful reception of our packet. The ACKs are sent by the ''forwarding candidates'', in the order in which they appear in the packet header. Each ACK not only contains the ID of its sender, but also the ID of the highest priority successful recipient known to the ACK's sender. All candidates listen to all slots, before deciding whether to forward a packet, so this mechanism can supress duplicate forwarding to a certain degree, because the information, which node will be the forwarding node, somehow 'ripples' through the candidate-subnetwork. Let's have another look at our example network, to make this more clear:		After sending the packet, it's important that all candidate nodes somehow agree who will be the forwarding node. This done by acknowledgements (ACKs), which are sent in defined time-slots directly after the successful reception of our packet. The ACKs are sent by the ''forwarding candidates'', in the order in which they appear in the packet header. Each ACK not only contains the ID of its sender, but also the ID of the highest priority successful recipient known to the ACK's sender. All candidates listen to all slots, before deciding whether to forward a packet, so this mechanism can supress duplicate forwarding to a certain degree, because the information, which node will be the forwarding node, somehow 'ripples' through the candidate-subnetwork. Let's have another look at our example network, to make this more clear:

	[[Image:Example_net.png]]		[[Image:Example_net.png]]

217.231.251.83: /* Stage 1: Select ''Forwarding Candidates'' */

2005-02-08T23:03:08Z

Stage 1: Select ''Forwarding Candidates''

← Older revision		Revision as of 23:03, 8 February 2005
Line 37:		Line 37:
	The decision which algorithm to use for this selection is very important for the strength of ''ExOR'', as it has a major impact on its performance. The following approach seems to be very simple, but results in good performance in most average topologies:		The decision which algorithm to use for this selection is very important for the strength of ''ExOR'', as it has a major impact on its performance. The following approach seems to be very simple, but results in good performance in most average topologies:

	A node which wants to forward a packet to a final destination first identifies the shortest path to this destination. We definitely need the aforementioned loss-rate-matrix here. The first node in this path is surely a good candidate regarding the forwarding job, so we use ~~him~~ as the best candidate. It's then deleted from the loss-rate-matrix and the whole process is repeated, until the set of ''forwarding candidates'' is full. (Typical sizes are 8 or 16 nodes.) Let's have a look at our example net, where the set of ''forwarding candidates'' would be (D, C, B), while assuming that we want to send a packet from node A to node D:		A node which wants to forward a packet to a final destination first identifies the shortest path to this destination. We definitely need the aforementioned loss-rate-matrix here. The first node in this path is surely a good candidate regarding the forwarding job, so we use it as the best candidate. It's then deleted from the loss-rate-matrix and the whole process is repeated, until the set of ''forwarding candidates'' is full. (Typical sizes are 8 or 16 nodes.) Let's have a look at our example net, where the set of ''forwarding candidates'' would be (D, C, B), while assuming that we want to send a packet from node A to node D:

	[[Image:Example_net.png]]		[[Image:Example_net.png]]