Loading...
Please wait, while we are loading the content...
Similar Documents
Analysis of Link Reversal Routing Algorithms for Mobile Ad Hoc Networks (2003)
| Content Provider | CiteSeerX |
|---|---|
| Author | Tirthapura, Srikanta Busch, Costas |
| Description | In 15th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA |
| Abstract | Link reversal algorithms provide a simple mechanism for routing in communication networks whose topology is frequently changing, such as in mobile ad hoc networks. A link reversal algorithm routes by imposing a direction on each network link such that the resulting graph is a destination oriented DAG. Whenever a node loses routes to the destination, it reacts by reversing some (or all) of its incident links. Link reversal algorithms have been studied experimentally and have been used in practical routing algorithms, including TORA [11]. This paper presents the first formal performance analysis of link reversal algorithms. We study these algorithms in terms of work (number of node reversals) and the time needed until the network stabilizes to a state in which all the routes are reestablished. We focus on the full reversal algorithm and the partial reversal algorithm, both due to Gafni and Berstekas [6]; the first algorithm is simpler, while the latter has been found to be more efficient for typical cases. Our results are as follows: • The full reversal algorithm requires O(n 2) work and time, where n is the number of nodes which have lost the routes to the destination. This bound is tight in the worst case. • The partial reversal algorithm requires O(n · a ∗ + n 2) work and time, where a ∗ is a non-negative integer which depends on the state of the network. This bound is tight in the worst case, for any a ∗. • There exist networks such that for every deterministic link reversal algorithm, there are initial states which require requires Ω(n 2) work and time to stabilize. Therefore, surprisingly, the full reversal algorithm is asymptotically optimal in the worst case, while the partial reversal algorithm is not, since a ∗ can grow arbitrarily large. 1 |
| File Format | |
| Publisher Date | 2003-01-01 |
| Access Restriction | Open |
| Subject Keyword | First Formal Performance Analysis Communication Network Link Reversal Algorithm Exist Network Non-negative Integer Link Reversal Routing Algorithm Deterministic Link Reversal Algorithm Node Reversal Link Reversal Practical Routing Algorithm First Algorithm Incident Link Typical Case Simple Mechanism Partial Reversal Algorithm Initial State Full Reversal Algorithm Mobile Ad Hoc Network |
| Content Type | Text |
| Resource Type | Conference Proceedings Article |
