A routing algorithm for triple-loop Network

 

AUTHOR

Dr Atheer Matroud

Senior Lecturer – De Montfort University Dubai, Dubai, UAE

ABSTRACT

In this paper, we study a family of triple-loop network of diameter k and number of nodes equal to 6k2 − 2k + 1 and each node i has six edges {i±1, i±3k−1, i±3k+2}. A proof that this family of triple-loop network has a diameter k is presented and a routing algorithm that has time complexity O(log n) is introduced. The routing problem in triple-loop network is modelled as a solution to a special type of Diophantine equation. Index Terms—Routing Algorithm, Diophantine Equations, Shortest Path, Time and Space Complexity

I. INTRODUCTION Inter-networking systems performances rely on several factors such as the routing algorithm implemented and the underlying topology. In order to design an effective algorithm, it is important to study the network topology. The network topology is the physical interconnection structure of the network. It is crucial for the connectivity and scalability of the network. Some examples of these topologies are d-loop graph, mesh, hypercube, butterfly, shuffle-exchange, etc. There is a common consensus that networks with simpler topologies will offer practical solutions to the problem of interconnecting a very large number of computing nodes.  Multi-loop network topology has been used for Local Area Networks [1] and Large Area Communication Networks like SONET [2], [3]. It was first introduced by Wong and Coppersmith in [4]. Informally, a d-loop network contains d interleaved rings. Among the properties of d-loop networks are scalability, fixed vertex degree, vertex symmetry, that is, vertex transitivity, regularity, reasonable diameter, and reliability. Therefore, d-loop networks have been studied extensively in the literature [5], [6], [7], [8], [9], [10], [11], [12]. A Multi-loop network, denoted by G(n; C1, · · · , Cd) is a graph with n nodes, labeled 0, . . . , n − 1, each node has 2 · d links. Node i is connected to i + cj for all 1 ≤ j ≤ d. When d is known, we can call it a d-loop network. In this paper, we study a special d-loop network topology where d = 3 (see Figure I). We model the path from one node to another in a 3-loop network as the solution of a Diophantine Equation. The routing algorithm is shown in Section III. Several algorithms have been introduced to address the routing and broadcasting algorithms on d-loop networks [13], [8],[14]. In this paper, we benefit from the properties of chordal ring graph to design an efficient routing algorithm.

 

REFERENCES

   Matroud, Atheer, Christopher Tuffley, and Michael D. Hendy. "An asymmetric alignment algorithm for estimating ancestor-descendant edit distance for tandem repeats." IEEE/ACM Transactions on Computational Biology and Bioinformatics (2021).

17.     Matroud, A. A., M. D. Hendy, and C. P. Tuffley. "NTRFinder: an algorithm to find nested tandem repeats." arXiv preprint arXiv:1006.1730 (2011).

18.     MATROUD, AA, MD HENDY, and CP TUFFLEY. "NTRFINDER: AN ALGORITHM TO FIND NESTED TANDEM REPEATS."

19.     Matroud, Atheer. Nested tandem repeat computation and analysis. Diss. Ph. D. Thesis, Massey University, 2013.

20.     Matroud, A. A., M. D. Hendy, and C. P. Tuffley. "NTRFinder: an algorithm to find nested tandem repeats." arXiv preprint arXiv:1006.1730 (2011).

21.     Matroud, Atheer A., Christopher P. Tuffley, and Michael D. Hendy. "An algorithm to solve the motif alignment problem for approximate nested tandem repeats in biological sequences." Journal of Computational Biology 18.9 (2011): 1211-1218.

22.     Matroud, Atheer A., Michael D. Hendy, and Christopher P. Tuffley. "An algorithm to solve the motif alignment Problem for approximate nested tandem repeats." RECOMB International Workshop on Comparative Genomics. Springer, Berlin, Heidelberg, 2010.

23.     Matroud, Atheer A., Michael D. Hendy, and Christopher P. Tuffley. "An algorithm to solve the motif alignment Problem for approximate nested tandem repeats." RECOMB International Workshop on Comparative Genomics. Springer, Berlin, Heidelberg, 2010.

24.     Matroud, Atheer A., Christopher P. Tuffley, and Michael D. Hendy. "An algorithm to solve the motif alignment problem for approximate nested tandem repeats in biological sequences." Journal of Computational Biology 18.9 (2011): 1211-1218.

25.       Matroud, Atheer A., et al. "A comparison of three heuristic methods for solving the parsing problem for tandem repeats." Brazilian Symposium on Bioinformatics. Springer, Berlin, Heidelberg, 2012.

1.      M. T. Liu, “Distributed loop computer networks,” in Advances in computers. Elsevier, 1978, vol. 17, pp. 163–221.

2.      H. M. Dao and C. Silio, “Ring-network with a constrained number of consecutively-bypassed stations,” IEEE Transactions on reliability, vol. 47, no. 1, pp. 35–43, 1998.

3.      A. Schrijver, P. Seymour, and P. Winkler, “The ring loading problem,” SIAM review, vol. 41, no. 4, pp. 777–791, 1999.

4.      C. Wong and D. Coppersmith, “A combinatorial problem related to multimodule memory organizations,” Journal of the ACM (JACM), vol. 21, no. 3, pp. 392–402, 1974.

5.      A. Abbas, M. Othman, M. H. Selamat, and R. Johari, “Large chordal rings for given diameter and uniqueness property of minima,” Ars Combinatoria, vol. 82, pp. 243–252, 2007.

6.      A. Abbas, “Broadcasting algorithm on large chordal ring of degree six networks,” in 2006 2nd International Conference on Information & Communication Technologies, vol. 2. IEEE, 2006, pp. 3134–3138.

7.      D. Krizanc and F. L. Luccio, “Boolean routing on chordal rings,” in In Proc. of the 2nd Colloqium on Structural Information and Communication Complexity. Citeseer, 1996.

8.      L. Narayanan and J. Opatrny, “Compact routing on chordal rings of degree 4,” Algorithmica, vol. 23, no. 1, pp. 72–96, 1999.

9.      B. Arden and H. Lee, “Analysis of chordal ring network,” IEEE Transactions on Computers, vol. 4, no. C-30, pp. 291–295, 1981.

10.     P. Morillo, F. Comellas, and M. Fiol, “The optimization of chordal ring networks,” Communication Technology, pp. 295–299, 1987.

11.     Y. Li, Y. Chen, W. Tai, and R. Wang, “The minimum distance diagram and diameter of undirected double-loop networks,” in 2016 3rd International Conference on Materials ngineering, Manufacturing Technology and Control. Atlantis Press, 2016.

12.     J.-C. Bermond, F. Comellas, and D. F. Hsu, “Distributed loop computer networks: A survey,” J. Parallel Distrib. Comput., vol. 24, no. 1, p. 2–10, Jan. 1995. [Online]. available: https://doi.org/10.1006/jpdc.1995.

13.     A. A. M. Bashi, “Boolean routing on high degree chordal ring networks,” Master Thesis, 2001.

14.     E. A. MONAKHOVA, “A survey on undirected circulant graphs,” Discrete Mathematics, Algorithms and Applications, vol. 04, no. 01, p. 1250002, 2012. [Online]. Available:
 https://doi.org/10.1142/S1793830912500024

15.     L. Narayanan and J. Opatrny, “Compact routing on chordal rings of degree four,” in Sirocco, vol. 97, 1997, pp. 125–137.

16.