Database analysis of optimal double-loop networks

E. A. Monakhova ; O. G. Monakhov

Prikladnaâ diskretnaâ matematika, no. 2 (2024), pp. 56-71.

Résumé

Optimal circulant networks are of practical interest as models of reliable low-latency communication networks for multiprocessor cluster systems and on-chip networks. The authors are the first to construct a large dataset of optimal diameter double-loop circulant networks with up to 50 thousand nodes, containing a complete set of optimal graph generators. The analysis of the dataset has been carried out in order to study the problem of finding analytically defined families of optimal graphs. Two new algorithms for automatically finding analytical descriptions of optimal graphs families described by polynomials in diameter have been developed. Using the implemented algorithms, a large number of new analytically described families of optimal networks have been found and tested using validation over the entire range of changes in the diameters of the dataset graphs. The found families of optimal networks can be used when scaling information transmission algorithms in double-loop circulant structures.

Détail

Keywords: dataset of optimal networks, undirected double-loop networks, circulant networks, minimum diameter.

Bibliographie

[1] Bermond J.-C., Comellas F., and Hsu D. F., “Distributed loop computer networks: a survey”, J. Parallel Distrib. Comput., 24:1 (1995), 2–10 | DOI

[2] Hwang F. K., “A survey on multi-loop networks”, Theoret. Comput. Sci., 299 (2003), 107–121 | DOI | MR | Zbl

[3] Monakhova E. A., “Structural and communicative properties of circulant networks”, Prikladnaya Diskretnaya Matematika, 2011, no. 3, 92–115 (in Russian)

[4] Huang X., Ramos A. F., and Deng Y., “Optimal circulant graphs as low-latency network topologies”, J. Supercomput., 78 (2022), 13491–13510 | DOI

[5] Chen B.-X., Meng J.-X., and Xiao W.-J., “Some new optimal and suboptimal infinite families of undirected double-loop networks”, Discrete Math. Theor. Comput. Sci., 8 (2006), 299–311 | DOI | MR | Zbl

[6] Romanov A. Y., “Development of routing algorithms in networks-on-chip based on ring circulant topologies”, Heliyon, 5:4 (2019), e01516 | DOI

[7] Chen B.-X., Xiao W.-J., and Parhami B., “Diameter formulas for a class of undirected double-loop networks”, Networks., 6:1 (2005), 1–15 | MR

[8] Jha K. P., “Tight-optimal circulants vis-a-vis twisted tori”, Discrete Appl. Math., 175 (2014), 24–34 | DOI | MR | Zbl

[9] Huanping L. and Yixian Y.-J., “On the fault-tolerant routing in distributed loop networks”, J. Electronics, 17 (2000), 84–89

[10] Bian Q.-F., Hang T., Liu H., and Fang M., “Research on the diameter and average diameter of undirected double-loop networks”, Int. Conf. Grid Cloud Computing (Nanjang, Jiangsu China), 2010, 461–466 | MR

[11] Martinez C., Beivide R., Stafford E., et al., “Modeling toroidal networks with the Gaussian integers”, IEEE Trans. Comput., 57:8 (2008), 1046–1056 | DOI | MR | Zbl

[12] Monakhova E. A., Monakhov O. G., and Romanov A. Yu., “Routing algorithms in optimal degree four circulant networks based on relative addressing: Comparative analysis for networks-on-chip”, IEEE Trans. Netw. Sci. Eng., 10:1 (2023), 413–425 | DOI | MR

[13] Perez-Roses H., Bras-Amoros M., and Seradilla-Merinero J. M., “Greedy routing in circulant networks”, Graphs Combinatorics, 38 (2022), 86 | DOI | MR | Zbl

[14] Lewis R. R., Analysis and Construction of Extremal Circulant and Other Abelian Cayley Graphs, Ph.D. Thesis, The Open University, London, UK, 2022

[15] Pai K.-J., Yang J.-S., Chen G.-Y., and Chang J.-M., “Configuring protection routing via completely independent spanning trees in dense Gaussian on-chip networks”, IEEE Trans. Netw. Sci. Eng., 9:2 (2022), 932–946 | DOI | MR

[16] Monakhov O. G., Monakhova E. A., Romanov A. Y., et al., “Adaptive dynamic shortest path search algorithm in networks-on-chip based on circulant topologies”, IEEE Access, 9 (2021), 160836–160846 | DOI

[17] Monakhova E. A., “On analytical representation of optimal two-dimensional Diophantine structures of homogeneous computer systems”, Vychislitel'nye Sistemy, 1981, no. 90, 81–91 (in Russian) | MR | Zbl

[18] Boesch F. and Wang J.-F., “Reliable circulant networks with minimum transmission delay”, IEEE Trans. Circuits Syst., 32:12 (1985), 1286–1291 | DOI | MR | Zbl

[19] Tzvieli D., “Minimal diameter double-loop networks. 1. Large infinite optimal families”, Networks, 21 (1991), 387–415 | DOI | MR | Zbl

[20] Liu H., Li X., and Wang S., “Construction of dual optimal bidirectional double-loop networks for optimal routing”, Mathematics, 10 (2022), 4016 | DOI

[21] Monakhova E. A., Romanov A. Y., and Lezhnev E. V., “Shortest path search algorithm in optimal two-dimensional circulant networks: Implementation for networks-on-chip”, IEEE Access, 8 (2020), 215010–215019 | DOI | MR

[22] Monakhova E. A., “Synthesis of optimal Diophantine structures”, Vychislitel'nye Sistemy, 1979, no. 80, 18–35 (in Russian) | Zbl

[23] Du D.-Z., Hsu D. F., Li Q., and Xu J., “A combinatorial problem related to distributed loop networks”, Networks, 20 (1990), 173–180 | DOI | MR | Zbl

[24] Li Y., Chen Y., Tai W., and Wang R., “The minimum distance diagram and diameter of undirected double-loop networks”, Proc. ICMEMTC (Taiyuan, China), 2016, 1682–1687

[25] Loudiki L., Kchikech M., and Essaky E. H., A New Approach for Computing the Distance and the Diameter in Circulant Graphs, 2022, arXiv: 2210.11116

[26] Jha P. K., “Dense bipartite circulants and their routing via rectangular twisted torus”, Discrete Appl. Math., 166 (2014), 141–158 | DOI | MR | Zbl

[27] Jha P. K. and Smith J. D. H., “Cycle Kronecker products that are representable as optimal circulants”, Discrete Appl. Math., 181 (2015), 130–138 | DOI | MR | Zbl

[28] Liu H., Yang Y., and Hu M., “Tight optimal infinite families of undirected double-loop networks”, Systems Eng. Theory Practice, 1 (2002), 75–79 | MR

[29] Jha P. K., “Dimension-order routing algorithms for a family of minimal-diameter circulants”, J. Interconn. Networks, 14:1 (2013), 1350002, 24 pp. | DOI

[30] Bermond J.-C. and Tzvieli D., “Minimal diameter double-loop networks: Dense optimal families”, Networks, 21 (1991), 1–9 | DOI | MR | Zbl

[31] Chen B.-X., Meng J.-X., and Xiao W.-J., “A constant time optimal routing algorithm for undirected double-loop networks”, LNCS, 3794, 2005, 308–316 | MR

[32] Monakhova E. A., “Optimal circulant computer networks”, Proc. PaCT'91 (Novosibirsk, USSR), 1991, 450–458

[33] Monakhova E. A. and Monakhov O. G., “Evolutionary synthesis of families of optimal two-dimensional circulant networks”, Vestnik SibSUTIS, 2014, no. 2, 72–81 (in Russian)

[34] Zerovnik J. and Pisanski T., “Computing the diameter in multiple-loop networks”, J. Algorithms, 14 (1993), 226–243 | DOI | MR | Zbl

[35] Romanov A., “The dataset for optimal circulant topologies”, Big Data Cogn. Comput., 7 (2023), 80 pp. | Zbl

[36] Monakhova E. A. and Monakhov O. G., “Generation and analysis of optimal double-loop circulant networks dataset”, SibDATA, Proc. CEUR Workshop, 2023 (to appear) | Zbl

[37] Storn R. and Price K., “Differential evolution — A simple and efficient heuristic for global optimization over continuous spaces”, J. Global Optimization, 11 (1997), 341–359 | DOI | MR | Zbl

[38] Zaheer H., Pant M., Monakhov O., and Monakhova E., “Simple and efficient co-operative approach for solving multi modal problems”, Proc. ICEEOT (Chennai, Tamilnadu, India), 2016, 731–737