A Fault-Tolerant Routing Scheme in Dynamic Networks

In dynamic networks, links and nodes will be deletedor added regularly. It is very essential for the routing scheme to havethe ability of fault-tolerance. The method to achieve such a goal is togenerate more than one path for a given set of source and destination.In this paper, the idea of interval routing is used to construct a newscheme (Multi-Node Label Interval Routing scheme, or MNLIR scheme) torealize fault-tolerance. Interval routing is a space-efficient routingmethod for networks, but the method is static and determinative, and itcannot realize fault-tolerance. In MNLIR scheme some nodes will havemore than one label, thus some pairs of destination and source willhave more than one path; the pairs of nodes, which have inheritancerelation, will have the shortest path. Using this character, MNLIRscheme has better overall routing performance than the former intervalrouting scheme, which can be proven by simulations. The common problemconcerning the insertion and deletion of nodes and links is consideredin this paper. So if the networks have some changes in topology, MNLIRscheme may find alternative path for certain pairs of nodes. In thisway, fault-tolerance can be realized with only a little space addedto store the multi-node labels.