ExOR - Extremely Opportunistic Routing: Difference between revisions
| (42 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
= Description = |
= Description = |
||
Extremely Opportunistic Routing |
Extremely Opportunistic Routing mechanism which takes plainly advantage of the characteristics of wireless networks. |
||
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. |
|||
| ⚫ | |||
The Implementation of this routing protocol needs some requirements. |
|||
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. |
|||
== Modified MAC Protocol == |
|||
The standard MAC Protocol is used to define the format for data transmission. Therefor its frame has several partitions. |
|||
{| style="float:center; background:transparent; padding:0px; margin:0px;" |
|||
|[[Image:mac-protocol.jpg|thumb|center|300px]] |
|||
|- |
|||
|} |
|||
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 == |
|||
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. |
|||
== The 3 important Stages == |
|||
=== Selecting a Forwarding Set === |
|||
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 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. |
|||
{| style="float:center; background:transparent; padding:0px; margin:0px;" |
|||
|[[Image:forwarding-set.jpg|thumb|center|300px| the forwarding list can be found in the marked area within the modified MAC frame]] |
|||
|- |
|||
|} |
|||
=== Sending Acknowledgements === |
|||
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 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. |
|||
{| style="float:center; background:transparent; padding:0px; margin:0px;" |
|||
|[[Image:main_network.jpg|thumb|center|200px]] |
|||
|- |
|||
|} |
|||
Example: |
|||
Suppose that node A hears a transmission, that A is the highest-priority candidate, and that A sends an ACK. Node B, the secondhighestpriority candidate, does not hear the ACK, but node C does hear the ACK. Suppose further that node B hears node |
|||
C’s ACK. If ACKs did not contain IDs, node B would forward the packet, since to its knowledge it is the highest-priority recipient. |
|||
The fact that node C’s ACK contains node A’s ID indirectly notifies B that node A did receive the packet. |
|||
=== Decision === |
|||
After all transmission were sent each candidate has to decide whether it should forward or discard the packet. Only nodes which have not received a higher ID forward a packet. |
|||
In the worst case it can happen occasionally that multiple nodes will forward a packet due to acknowledgment reception failure. For this reason, each packet also contains a random value which forwarding nodes will store in a cache. |
|||
This prevents from forwarding the same packet multiple times. Consequently a packet is transmitted |
|||
only if the random value was not found in the cache. |
|||
| ⚫ | |||
= Performance = |
= Performance = |
||
In comparison to many well-known |
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 |
In generell the greatest benefit out of ExOR is its ability to skip intermediate hops. |
||
{| style="float: |
{| style="float:center; background:transparent; padding:0px; margin:0px;" |
||
|- valign="top" |
|||
|[[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| |
|[[Image:distribution.jpg|thumb|right|300px|Number of used nodes in correlation with distance]] |
||
|- |
|||
|} |
|} |
||
| ⚫ | |||
ExOR's main ability is to skip intermediate Hops which consequently reduces the use of hops in general. |
|||
| ⚫ | |||
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 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 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. |
|||
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] |
||
Latest revision as of 20:46, 31 July 2007
Description
Extremely Opportunistic Routing mechanism which takes plainly advantage of the characteristics of wireless networks. 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
The Implementation of this routing protocol needs some requirements. 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.
Modified MAC Protocol
The standard MAC Protocol is used to define the format for data transmission. Therefor its frame has several partitions.
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
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.
The 3 important Stages
Selecting a Forwarding Set
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 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.
Sending Acknowledgements
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 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.
Example: Suppose that node A hears a transmission, that A is the highest-priority candidate, and that A sends an ACK. Node B, the secondhighestpriority candidate, does not hear the ACK, but node C does hear the ACK. Suppose further that node B hears node C’s ACK. If ACKs did not contain IDs, node B would forward the packet, since to its knowledge it is the highest-priority recipient. The fact that node C’s ACK contains node A’s ID indirectly notifies B that node A did receive the packet.
Decision
After all transmission were sent each candidate has to decide whether it should forward or discard the packet. Only nodes which have not received a higher ID forward a packet. In the worst case it can happen occasionally that multiple nodes will forward a packet due to acknowledgment reception failure. For this reason, each packet also contains a random value which forwarding nodes will store in a cache. This prevents from forwarding the same packet multiple times. Consequently a packet is transmitted only if the random value was not found in the cache.
Performance
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 possible of up to 65%. In generell the greatest benefit out of ExOR is its ability to skip intermediate hops.
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
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 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 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.
Consequently it is possible to communicate within different levels(Multi-Level Opportunistic Routing).