Shortest node-to-node disjoint paths algorithm for symmetric networks
Abstract
Disjoint paths are defined as paths between the source and destination nodes where the intermediate nodes in any two paths are disjoint. They are helpful in fault-tolerance routing and securing message distribution in the network. Several research papers were proposed to solve the problem of finding disjoint paths for a variety of interconnection networks such as Hypercube, Generalized Hypercube, Mesh, Torus, Gaussian, Eisenstein–Jacobi, and many other topologies. In this research, we have developed a general algorithm that constructs maximal node-to-node disjoint paths for symmetric networks where all paths are shortest. The algorithm presented in this paper outperforms other algorithms in finding not only the disjoint paths but shortest and maximal disjoint paths with a complexity of . In addition, we have simulated the proposed algorithm on different networks. The solution of unsolved problem in Cube-Connected-Cycles is given in the simulation results.
References
[1]
Jurczyk M, Siegel HJ, and Stunkel C Interconnection Networks for Parallel Computers 2009 Atlanta American Cancer Society 1613-1623
[2]
Kotsis, G.: Interconnection topologies and routing for parallel processing systems. Citeseer (1992)
[3]
Hayes JP and Mudge T Hypercube supercomputers Proc. IEEE 1989 77 12 1829-1841
[4]
Kumar V, Grama A, Anshul G, and Karypis G Introduction to Parallel Computing: Design and Analysis of Algorithms 1994 San Francisco Benjamin/Cummings Publishing Company 82-109
[5]
Bose B, Broeg B, Kwon Y, and Ashir Y Lee distance and topological properties of k-ary n-cubes IEEE Trans. Comput. 1995 44 8 1021-1030
[6]
Preparata, F.P., Vuillemin, J.: The cube-connected-cycles: a versatile network for parallel computation. In: 20th Annual Symposium on Foundations of Computer Science (SFCS 1979), 1979, pp. 140–147. IEEE (1979)
[7]
Dally WJ and Seitz CL The torus routing chip Distrib. Comput. 1986 1 4 187-196
[8]
Martínez C, Beivide R, Stafford E, Moretó M, and Gabidulin EM Modeling toroidal networks with the Gaussian integers IEEE Trans. Comput. 2008 57 8 1046-1056
[9]
Flahive M and Bose B The topology of Gaussian and Eisenstein–Jacobi interconnection networks IEEE Trans. Parallel Distrib. Syst. 2009 21 8 1132-1142
[10]
Martínez C, Stafford E, Beivide R, and Gabidulin EM Modeling hexagonal constellations with Eisenstein–Jacobi graphs Probl. Inf. Transm. 2008 44 1 1-11
[11]
Holton DA and Sheehan J The Petersen Graph 1993 Cambridge Cambridge University Press
[12]
Noakes MD, Wallach DA, and Dally WJ The j-machine multicomputer: an architectural evaluation ACM SIGARCH Comput. Archit. News 1993 21 2 224-235
[13]
Scott SL et al. The Cray T3E Network: Adaptive Routing in a High Performance 3D Torus 1996 Stanford Stanford University
[14]
Quoc DN, Bi L, Wu Y, He S, Li L, and Guo D Energy efficiency clustering based on Gaussian network for wireless sensor network IET Commun. 2019 13 6 741-747
[15]
Ganjali, Y., Keshavarzian, A.: Load balancing in ad hoc networks: single-path routing vs. multi-path routing. In: IEEE INFOCOM 2004, 2004, vol. 2, pp. 1120–1125 (2004).
[16]
Taft-Plotkin, N., Bellur, B., Ogier, R.: Quality-of-service routing using maximally disjoint paths. In: 1999 Seventh International Workshop on Quality of Service. IWQoS’99, 1999 (Cat. No. 98EX354), pp. 119–128 (1999).
[17]
Bagchi, A., Chaudhary, A., Goodrich, M.T., Xu, S.: Constructing disjoint paths for secure communication. In: International Symposium on Distributed Computing, 2003, pp. 181–195. Springer (2003)
[18]
Suurballe JW and Tarjan RE A quick method for finding shortest pairs of disjoint paths Networks 1984 14 2 325-336
[19]
Bhandari, R.: Optimal physical diversity algorithms and survivable networks. In: Proceedings of Second IEEE Symposium on Computer and Communications, 1997 (1997).
[20]
Cormen TH, Leiserson CE, Rivest RL, and Stein C Section 26.2: The Ford-Fulkerson Method 2001 2 Cambridge MIT Press 651-664
[21]
Lai C-N Optimal construction of all shortest node-disjoint paths in hypercubes with applications IEEE Trans. Parallel Distrib. Syst. 2011 23 6 1129-1134
[22]
Sinanoglu O, Karaata MH, and AlBdaiwi B An inherently stabilizing algorithm for node-to-node routing over all shortest node-disjoint paths in hypercube networks IEEE Trans. Comput. 2010 59 7 995-999
[23]
Gu Q-P and Tamaki H Routing a permutation in the hypercube by two sets of edge disjoint paths J. Parallel Distrib. Comput. 1997 44 2 147-152
[24]
Madhavapeddy, S., Sudborough, I.H.: A topological property of hypercubes: node disjoint paths. In: Proceedings of the Second IEEE Symposium on Parallel and Distributed Processing 1990, 1990, pp. 532–539. IEEE (1990)
[25]
Gu, Q.P., Okawa, S., Peng, S.: Efficient Algorithms for Disjoint Paths in Hypercubes and Star Networks. Notes from the Institute of Mathematical Analysis (1994)
[26]
Day, K., Alzeidi, N., Arafeh, B., Touzene, A.: A parallel routing algorithm for torus NOCS. In: 2012 International Conference on Computer Networks and Communication Systems, 2012, vol. 35. Citeseer (2012)
[27]
Lai C-N Constructing all shortest node-disjoint paths in torus networks J. Parallel Distrib. Comput. 2015 75 123-132
[28]
Xiang, Y., Stewart, I., Madelaine, F.: Node-to-node disjoint paths in k-ary n-cubes with faulty edges, In: 2011 IEEE 17th International Conference on Parallel and Distributed Systems, 2011, pp. 181–187. IEEE (2011)
[29]
Day K and Al-Ayyoub AE Constructing node-disjoint routes in k-ary n-cubes Sultan Qaboos Univ. J. Sci. 1998 3 41-45
[30]
Shih Y-K and Kao S-S One-to-one disjoint path covers on k-ary n-cubes Theor. Comput. Sci. 2011 412 35 4513-4530
[31]
Zhuang H, Li X-Y, Chang J-M, Lin C-K, and Liu X Embedding Hamiltonian paths in -ary -cubes with exponentially-many faulty edges IEEE Trans. Comput. 2023 72 11 3245-3258
[32]
Wu R-Y, Chen G-H, Kuo Y-L, and Chang GJ Node-disjoint paths in hierarchical hypercube networks Inf. Sci. 2007 177 19 4200-4207
[33]
Li, Y., Peng, S.: Fault-tolerant routing and disjoint paths in dual-cube: a new interconnection network. In: Proceedings. Eighth International Conference on Parallel and Distributed Systems. ICPADS 2001, 2001, pp. 315–322. IEEE (2001)
[34]
Bakhshi, S., Sarbazi-Azad, H.: One-to-one and one-to-many node-disjoint routing algorithms for WK-recursive networks. In: International Symposium on Parallel Architectures, Algorithms, and Networks (I-span 2008), 2008, pp. 227–232. IEEE (2008)
[35]
Lai C-N, Chen G-H, and Duh D-R Constructing one-to-many disjoint paths in folded hypercubes IEEE Trans. Comput. 2002 51 1 33-45
[36]
Kaneko, K., Peng, S.: Node-to-set disjoint paths routing in dual-cube. In: International Symposium on Parallel Architectures, Algorithms, and Networks (I-span 2008), 2008, pp. 77–82. IEEE (2008)
[37]
Alsaleh O, Bose B, and Hamdaoui B One-to-many node-disjoint paths routing in dense Gaussian networks Comput. J. 2015 58 2 173-187
[38]
Kaneko, K., Peng, S.: Set-to-set disjoint paths routing in dual-cubes. In: 2008 Ninth International Conference on Parallel and Distributed Computing, Applications and Technologies, 2008, pp. 129–136. IEEE (2008)
[39]
Gu, Q.-P., Peng, S.: An efficient algorithm for set-to-set node-disjoint paths problem in hypercubes. In: Proceedings of 1996 International Conference on Parallel and Distributed Systems, 1996, pp. 98–105. IEEE (1996)
[40]
Park J-H, Kim H-C, and Lim H-S Many-to-many disjoint path covers in hypercube-like interconnection networks with faulty elements IEEE Trans. Parallel Distrib. Syst. 2006 17 3 227-240
[41]
Kaneko K and Bossard A A set-to-set disjoint paths routing algorithm in tori Int. J. Netw. Comput. 2017 7 2 173-186
[42]
Bossard A and Kaneko K Set-to-set disjoint paths routing in torus-connected cycles IEICE Trans. Inf. Syst. 2016 99 11 2821-2823
[43]
Bossard A and Kaneko K Set-to-set disjoint paths routing in hierarchical cubic networks Comput. J. 2014 57 2 332-337
[44]
Friš I, Havel I, and Liebl P The diameter of the cube-connected cycles Inf. Process. Lett. 1997 61 3 157-160
[45]
Dally WJ and Towles BP Principles and Practices of Interconnection Networks 2004 Amsterdam Elsevier
Index Terms
- Shortest node-to-node disjoint paths algorithm for symmetric networks
Index terms have been assigned to the content through auto-classification.
Recommendations
Finding min-sum disjoint shortest paths from a single source to all pairs of destinations
TAMC'06: Proceedings of the Third international conference on Theory and Applications of Models of ComputationGiven a graph G = (V, E) with |V| = n, |E| = m, and a source node s, we consider the problem of finding two disjoint paths from s to two destination nodes t1 and t2 with minimum total length, for every pair nodes t1, t2 ∈ V–{s}. One efficient solution ...
Finding non-dominated bicriteria shortest pairs of disjoint simple paths
In this paper we introduce a method to compute non-dominated bicriteria shortest pairs, each including two disjoint simple paths. The method is based on an algorithm for ranking pairs of disjoint simple paths by non-decreasing order of cost, that is an ...
On shortest disjoint paths in planar graphs
For a graph G and a collection of vertex pairs {(s"1,t"1),...,(s"k,t"k)}, the k disjoint paths problem is to find k vertex-disjoint paths P"1,...,P"k, where P"i is a path from s"i to t"i for each i=1,...,k. In the corresponding optimization problem, the ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
© The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature 2024. Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
Publisher
Kluwer Academic Publishers
United States
Publication History
Published: 15 June 2024
Accepted: 17 May 2024
Revision received: 26 April 2024
Received: 07 March 2024
Author Tags
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 25 Jan 2025