**
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 6k^{2} − 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; C_{1},
· · · , C_{d}) 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.