An extended link reversal protocol in dynamic networks

We consider the problem of maintaining routing paths between nodes in a dynamic network. Gafni and Bertsekas proposed a link reversal approach called the BG method that maintains a directed acyclic graph (DAG) with a given destination as the sink node. By virtue of built-in redundancy, an updating algorithm to establish a new DAG is activated infrequently and it happens only when the last outgoing link of a host in the DAG is destroyed due to the movement of nodes. In this paper, we propose another updating approach that tries to minimize the total number of reversed links and to maintain routing information without using much extra overhead. The approach maintains a reversed breadth-first tree. Nodes in the network are either marked (inside the tree) or unmarked (outside the tree). When it is too costly to maintain a minimum path for a marked node, the branch rooted at the node is trimmed and the approach then gracefully switches to the BG method. Several extensions are also discussed. A simulation study is conducted to compare the performance of the proposed approach with the existing one.