Evaluating on Topology Survivability Based on Largest Number of Node-Disjoint Paths

Qiurong Chen


On the point of view of Largest Number of Node-Disjoint Path (LNNDP for short) between a node pair in a network, this article states the importance of LNNDP to global survivability of topology at first, then proposes an algorithm to compute maximal number of node-disjoint paths between node pairs. A new topology survivability metric based on LNNDP is put forward to evaluate the global survivability of network topology. It can be used to evaluate the survivability of topology provided. This metric can express accurately global topology survivability.


Topology; Survivability; Metric; Node-Disjoint Path; Working Path; Alternate Path

Full Text:



Whalen JS, Kenney J. Finding maximal link disjoint paths in a multigraph. IEEE Global Telecommunications Conference IEEE; 1990.

Loh RC, Soh S, Lazarescu M. An approach to find maximal disjoint paths with reliability and delay constraints. The IEEE 23rd International Conference on Advanced Information Networking and Applications; 2009 May 26-29. Bradford, United Kingdom; 2009.

Lin G, Lazarescu M, Soh S, et al. Energy-aware two link-disjoint paths routing. IEEE International Conference on High Performance Switching & Routing IEEE; 2013.

Li X, Cuthbert L. On-demand node-disjoint multipath routing in wireless ad hoc networks. IEEE International Conference on Local Computer Networks IEEE; 2004.

Ash A. A hybrid protocol for identification of a maximal set of node disjoint paths in mobile ad hoc networks. IEEE International Conference on Networks IEEE; 2008.

Nagaratna M, Srinivas PVS, Prasad VK, et al. Computation of multiple paths in MANETs using node disjoint method. International Journal of Computer Science Issues 2011.

Sun Z, Xie Z, Chen Z. Algorithm design for disjoint path problem. Computer Engineering 2013.

Chen W, Xiao W, Parhami B. An efficient construction of node disjoint paths in OTIS networks. Advanced Parallel Processing Technologies, 7th International Symposium, APPT 2007; 2007 Nov 22–23; Guangzhou, China; Proceedings DBLP; 2007.

Newport KT, Varshney PK. Design of survivable communications networks under performance constraints. IEEE Transactions on Reliability 1991; 40(4): 433–440.

Lipson HF, Mead NR, Linger RC. Requirements definition for survivable network systems 1998.

Rohrer JP, Sterbenz JPG. Predicting topology survivability using path diversity. International Congress on Ultra Modern Telecommunications & Control Systems & Workshops IEEE; 2011.

Liang Q, Modiano E. Survivability in time-varying networks. IEEE Transactions on Mobile Computing 2015; PP(99): 2668–2681.

Liu W, Pawlikowski K, Sirisena H. Algebraic connectivity metric for spare capacity allocation problem in survivable networks. Computer Communications 2011; 34(12): 1425–1435.

DOI: http://dx.doi.org/10.18282/jnt.v2i3.1107


  • There are currently no refbacks.