Title: Probing multiple node-disjoint paths using multi-labelled tree traversing

Authors: Wenchao Jiang, Hai Jin, Yanhong Zhou

Addresses: Bioinformatics and Molecular Imaging Lab, School of Computer Science and Technology, Huazhong University of Science and Technology, Wuhan, 430074, PR China. ' Services Computing Technology and System Lab, Cluster and Grid Computing Lab, School of Computer Science and Technology, Huazhong University of Science and Technology, Wuhan, 430074, PR China. ' Bioinformatics and Molecular Imaging Lab, School of Computer Science and Technology, Huazhong University of Science and Technology, Wuhan, 430074, PR China

Abstract: A node-disjoint multi-path routing (NMPR) method based on multi-labelled tree (MLT) is proposed. Given an assured node as the drain, any network can be transformed into a MLT rooted at the drain through sending multiple (equal to the number of its neighbours) probing messages from the drain to the other nodes according to the node-disjoint constraints. For each node except for the drain in the MLT, a path will be located by inverse-traversing from this node to the root. Multiple paths distributed in different branches of the MLT are necessarily node-disjoint. MLT is one kind of decentralised approach because each node in the network need only contain the relevant information about its neighbours. From the viewpoint of data forwarding, our NMPR based on MLT is of multiple points to one point. Examples and simulation experiments indicate that NMPR based on MLT can probe more node-disjoint paths than coloured tree (CT) approach with a little increment in routing table size at each node while retaining similar searching time. In addition, the average path length using MLT approach is smaller than that of CT approach.

Keywords: inverse traversing; MLT; multi-labelled tree; multiple points to one point; NMPR; node-disjoint multi-path routing.

DOI: 10.1504/IJAACS.2009.024420

International Journal of Autonomous and Adaptive Communications Systems, 2009 Vol.2 No.2, pp.175 - 200

Published online: 03 Apr 2009 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article