ANALYSIS OF FULL LINK REVERSAL ALGORITHM FOR WIRELESS MOBILE AD HOC NETWORKS FOR LOOP FREE ROUTES

Author (s) : R.Sathiya Priya and A.Manjurekha

---

Abstract :
The Link Reversal algorithms offer loop-free routes with bidirectional links to a single destination from neighboring nodes in a network, using locally valid distributed information.  These algorithms do not undergo routing table loops, since a directed acyclic graph (DAG) is consistently generated from the undirected graph with the implication of link reversal mechanism. By construction, the paths are inevitably loop-free. However, the algorithm is exposed to routing loops when a link reverses directions, packets that traveled across the link just earlier to the reversal now have a choice of moving backwards, up the same link that they just traversed.  The routing loops formed in this fashion are purely transient and once the algorithm converges; all the routes are loop-free. The number of reversals and the final resulting graph depend only on the initial conditions of the network, though multiple paths can be used to reach the final state. A significant disadvantage is that GB algorithms do count to infinity under network partition, since there is always a local minimum that is not the destination, and the links in the network undergo direction reversal indefinitely. In this paper, we discuss properties of the simplest link reversal algorithm called full reversal, which may simplify verification of concurrent systems that use full reversal for resource allocation.

Keywords : link reversal routing, Wireless networks, Complexity of algorithms

Conference Date : 30/08/2019

Pages : 29

Paper ID : 19027