ExOR - Extremely Opportunistic Routing - Revision history

Itachi: /* Performance */

2007-07-31T20:46:11Z

Performance

← Older revision		Revision as of 20:46, 31 July 2007
Line 66:		Line 66:
	In generell the greatest benefit out of ExOR is its ability to skip intermediate hops.		In generell the greatest benefit out of ExOR is its ability to skip intermediate hops.

	{\| style="float:~~enter~~; background:transparent; padding:0px; margin:0px;"		{\| style="float:center; background:transparent; padding:0px; margin:0px;"
	\|width="50%"
	\|[[Image:transmissions.jpg\|thumb\|left\|300px\|Number of Transmissions per node pair]]		\|[[Image:transmissions.jpg\|thumb\|left\|300px\|Number of Transmissions per node pair]]
	\|\|[[Image:distribution.jpg\|thumb\|right\|300px\|Number of used nodes in correlation with distance]]		\|[[Image:distribution.jpg\|thumb\|right\|300px\|Number of used nodes in correlation with distance]]
	\|-		\|-
	\|}		\|}

Itachi: /* Performance */

2007-07-31T20:45:58Z

Performance

← Older revision		Revision as of 20:45, 31 July 2007
Line 66:		Line 66:
	In generell the greatest benefit out of ExOR is its ability to skip intermediate hops.		In generell the greatest benefit out of ExOR is its ability to skip intermediate hops.

	{\| style="float:~~center~~; background:transparent; padding:0px; margin:0px;"		{\| style="float:enter; background:transparent; padding:0px; margin:0px;"
			\|width="50%"
	\|[[Image:transmissions.jpg\|thumb\|left\|300px\|Number of Transmissions per node pair]]		\|[[Image:transmissions.jpg\|thumb\|left\|300px\|Number of Transmissions per node pair]]
		⚫	\|\|[[Image:distribution.jpg\|thumb\|right\|300px\|Number of used nodes in correlation with distance]]
	\|-
⚫	\|[[Image:distribution.jpg\|thumb\|right\|300px\|Number of used nodes in correlation with distance]]
	\|-		\|-
	\|}		\|}

Itachi: /* Performance */

2007-07-31T20:45:20Z

Performance

← Older revision		Revision as of 20:45, 31 July 2007
Line 67:		Line 67:

	{\| style="float:center; background:transparent; padding:0px; margin:0px;"		{\| style="float:center; background:transparent; padding:0px; margin:0px;"
	\|[[Image:transmissions.jpg\|thumb\|~~center~~\|300px\|Number of Transmissions per node pair]]		\|[[Image:transmissions.jpg\|thumb\|left\|300px\|Number of Transmissions per node pair]]
	\|-		\|-
	\|[[Image:distribution.jpg\|thumb\|right\|300px\|Number of used nodes in correlation with distance]]		\|[[Image:distribution.jpg\|thumb\|right\|300px\|Number of used nodes in correlation with distance]]

Itachi: /* Sending Acknowledgements */

2007-07-31T20:43:55Z

Sending Acknowledgements

← Older revision		Revision as of 20:43, 31 July 2007
Line 45:		Line 45:

	{\| style="float:center; background:transparent; padding:0px; margin:0px;"		{\| style="float:center; background:transparent; padding:0px; margin:0px;"
	\|[[Image:main_network.jpg\|thumb\|center\|~~300px~~]]		\|[[Image:main_network.jpg\|thumb\|center\|200px]]
	\|-		\|-
	\|}		\|}

Itachi: /* Problems */

2007-07-31T19:55:40Z

Problems

← Older revision		Revision as of 19:55, 31 July 2007
Line 79:		Line 79:

	The main problem of ExOR introduces to the major problems of wireless networks in general: Sharing the same medium all the time.		The main problem of ExOR introduces to the major problems of wireless networks in general: Sharing the same medium all the time.
	Even with the modified MAC ~~with~~ a time slotted mechanism for acknowledgements it is not possible to solve the following problem case:		Even with the modified MAC using a time slotted mechanism for acknowledgements it is not possible to solve the following problem case:

	A node is waiting for an acknowledgement from a potential forwarder but receives much more acknowledgements from nodes more close to itself.		A node is waiting for an acknowledgement from a potential forwarder far away but receives much more acknowledgements from nodes more close to itself.

	One solution is using different transmission channels. Therefore the Systems Architecture Group of the Humboldt-Universität zu Berlin made a multi-channel protocol for opportunistic routing.		One solution is using different transmission channels. Therefore the Systems Architecture Group of the Humboldt-Universität zu Berlin made a multi-channel protocol for opportunistic routing.

	Consequently it is possible to communicate within different levels(Multi-Level Opportunistic Routing).		Consequently it is possible to communicate within different levels(Multi-Level Opportunistic Routing).



	= External Links =		= External Links =

Itachi: /* Performance */

2007-07-30T09:33:42Z

Performance

← Older revision		Revision as of 09:33, 30 July 2007
Line 62:		Line 62:

	= Performance =		= Performance =
	In comparison to many well-known ~~Routing -~~ algorithms like OSPF,DSR,AODV Opportunistic ~~routing~~ generally performs better than ~~the~~		In comparison to many well-known routing algorithms like OSPF,DSR or AODV Opportunistic Routing generally performs better than
	a margin of 55%. Depending on how large the network is there are improvements of up to 65%.		a margin of 55%. Depending on how large the network is there are improvements possible of up to 65%.
	In generell the greatest benefit out of ExOR is its ability to skip intermediate hops.		In generell the greatest benefit out of ExOR is its ability to skip intermediate hops.

Itachi: /* Performance */

2007-07-28T12:56:41Z

Performance

← Older revision		Revision as of 12:56, 28 July 2007
Line 73:		Line 73:
	\|}		\|}

	The first graphic shows how ExOR reduces the number of Transmissions in a network.		The first graphic shows how ExOR reduces the number of Transmissions in a network. The second graphic emphasizes why ExOR reduces the number of transmissions overall.
			ExOR's main ability is to skip intermediate Hops which consequently reduces the use of hops in general.

	= Problems =		= Problems =

Itachi: /* Implementation */

2007-07-28T12:51:44Z

Implementation

← Older revision		Revision as of 12:51, 28 July 2007
Line 5:		Line 5:
	= Implementation =		= Implementation =

			The Implementation of this routing protocol needs some requirements.
	What is neccesary to implement such a routing protocol?

	First the standard MAC Protocol has to be modified. And in second every node needs a Delivery-Ratio-Matrix to decide which node would be the best receiver.		First the standard MAC Protocol has to be modified. And in second every node needs a Delivery-Ratio-Matrix to decide which node would be the best receiver.

Line 18:		Line 17:
	\|}		\|}

	The ExOR algorithm needs to improve the current MAC - Protocol as it changes the single destination and acknowledgement partition into a n-slot partition. E.G. the network where ExOR will be implemented needs a 3 candidate list, there will be 3 destination slots and 3 acknowledgement slots like it is shown in the picture.		The ExOR algorithm needs to improve the current MAC - Protocol as it changes the single destination and acknowledgement partition into a n-slot partition. E.G. the network where ExOR will be implemented needs a 3 candidate Forwarder-list, there will be 3 destination slots and 3 acknowledgement slots like it is shown in the picture.

	== Delivery - Ratio MAtrix ==		== Delivery - Ratio MAtrix ==

	The Delivery - Ratio Matrix consists of transmission rates between each node in the network. Consequently every node owns such a matrix.		The Delivery - Ratio Matrix consists of measured transmission rates between each node in the network. Consequently every node owns such a matrix.
	All Values are updated in a specific period of time through a link-state-flooding scheme. Though it is possible to keep up with changes within the network.		All Values are updated in a specific period of time through a link-state-flooding scheme. Though it is possible to keep up with changes within the network.

	== The 3 important Stages ==		== The 3 important Stages ==
Line 31:		Line 30:

	A Forwarding Set is a list of all potential forwarding nodes. Each node of the network creates such a list by its own view of the network.		A Forwarding Set is a list of all potential forwarding nodes. Each node of the network creates such a list by its own view of the network.
	Therefor it first identifies the shortest path to the destination. Then it breaks ties between equally short paths using information from ~~the~~ ~~delivery ratio~~ matrix. The priority in this list is given as the first node in this path is the highest priority candidate.		Therefor it first identifies the shortest path to the destination. Then it breaks ties between equally short paths using information from its Delivery-Ratio matrix. The priority in this list is given as the first node in this path is the highest priority candidate.
	This set of nodes is cached until there is any update from the Delivery-Ratio matrix. In this way the process guarantees, that it will adept to all changes within the network.		This set of nodes is cached until there is any update from the Delivery-Ratio matrix. In this way the process guarantees, that it will adept to all changes within the network.

Line 42:		Line 41:

	The major problem in optimizing W-LAN networks is based on deciding which node will send the packet.		The major problem in optimizing W-LAN networks is based on deciding which node will send the packet.
	So this protocol uses a modified version of the 802.11 MAC which reserves multiple slots of time for ~~the~~ receiving nodes to return acknowledgments. Through out this improvement it is possible to reduce the collision probability down to 2%. Furthermore it integrates the ID of the highest priority successful recipient known to the ACK’s sender. This is very useful in case a low-priority candidate’s ACK reports a high-priority candidate’s ID.		So this protocol uses a modified version of the 802.11 MAC which reserves multiple slots of time for receiving nodes to return acknowledgments. Through out this improvement it is possible to reduce the collision probability down to 2%. Furthermore it integrates the ID of the highest priority successful recipient known to the ACK’s sender. This is very useful in case a low-priority candidate’s ACK reports a high-priority candidate’s ID.
	This major improvement suppresses duplicate forwarding.		This major improvement suppresses duplicate forwarding.

Itachi: /* Description */

2007-07-28T12:45:03Z

Description

← Older revision		Revision as of 12:45, 28 July 2007
Line 1:		Line 1:
	= Description =		= Description =
	Extremely Opportunistic Routing is a ~~Routing~~ ~~algorithm that takes~~ advantage of the characteristics of wireless networks.		Extremely Opportunistic Routing mechanism which takes plainly advantage of the characteristics of wireless networks.
	~~Therefor~~ ExOR ~~determines~~ the path as the packet moves through the network instead of choosing a ~~single~~ route ahead of time. Through this improvement the performance in wireless networks will increase significantly.		Therefore ExOR seeks the path from source to destination as the packet moves through the network instead of choosing a pre-determined route ahead of time. Through this improvement the performance in wireless networks will increase significantly.

	= Implementation =		= Implementation =

Itachi: /* See also */

2007-07-28T12:41:47Z

← Older revision		Revision as of 12:41, 28 July 2007
Line 87:		Line 87:
	Consequently it is possible to communicate within different levels(Multi-Level Opportunistic Routing).		Consequently it is possible to communicate within different levels(Multi-Level Opportunistic Routing).


	= See also =

	= External Links =		= External Links =
	[https://pdos.csail.mit.edu/~rtm/papers/hotnets-exor.pdf hotnets-exor]		[https://pdos.csail.mit.edu/~rtm/papers/hotnets-exor.pdf hotnets-exor]