ExOR - Extremely Opportunistic Routing: Difference between revisions
| Line 35: | Line 35: | ||
{| style="float:center; background:transparent; padding:0px; margin:0px;" |
{| style="float:center; background:transparent; padding:0px; margin:0px;" |
||
|[[Image:forwarding-set.jpg|thumb|center|300px]] |
|[[Image:forwarding-set.jpg|thumb|center|300px| the forwarding list can be found in the marked area within the modified MAC frame]] |
||
|- |
|- |
||
|} |
|} |
||
Revision as of 14:43, 26 July 2007
Description
Extremely Opportunistic Routing is a Routing algorithm that takes 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.
Implementation
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.
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 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 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 the 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 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. 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,AODV Opportunistic routing generally performs better than the a margin of 55%. Depending on how large the network is there are improvements 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.