Discovery of infinite families of optimal double-loop networks with a given template of generators

E. A. Monakhova ; O. G. Monakhov

Prikladnaâ diskretnaâ matematika, no. 4 (2024), pp. 97-115.

Résumé

Optimal ring circulant networks of degree four are considered as models of reliable communication networks with minimal delays for networks on a chip and multiprocessor cluster systems. Based on the analysis of a data set of optimal descriptions of double-loop networks, a search has been carried out for analytically determined infinite families of optimal graphs. By integrating data visualization and analytical descriptions of optimal graphs, new infinite families of optimal networks with a linear generator of the form $s=4d+\alpha$, where $d$ is the diameter of the graph, have been constructed and theoretically justified. The proposed approach to obtaining families of optimal networks is new and is of interest for further studies of the properties of optimal double-loop networks.

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) | Zbl

[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] 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

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

[7] 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

[8] Chen B.-X., Meng J.-X., and Xiao W.-J., “A constant time optimal routing algorithm for undirected double-loop networks”, Proc. 1$^\text{th}$ Int. Conf. Mobile Ad-hoc and Sensor Networks, MSN 2005 (Wuhan, China, December, 2005), 309–316 | MR

[9] Hoffmann R., Deserable D., and Seredynski F., “Cellular automata rules solving the wireless sensor network coverage problem”, Natural Computing, 21 (2022), 417–447 | DOI | MR | Zbl

[10] Chen Y. B., Li Y., and Zheng X., “Research on undirected double-loop data center networks”, Proc. Int. Conf. Advanced Cloud and Big Data (Huangshan, China, 2014), 180–183

[11] Erickson A., Stewart I. A., Navaridas J., and Kiasari A. E., “The stellar transformation: From interconnection networks to datacenter networks”, Computer Networks, 113 (2017), 29–45 | DOI

[12] Fei J. and Lu C., “Adaptive sliding mode control of dynamic systems using double loop recurrent neural network structure”, IEEE Trans. Neural Netw. Learn. Syst., 29 (2018), 1275–1286 | DOI | MR

[13] 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

[14] 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

[15] 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

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

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

[18] 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

[19] Monakhova E. A. and Monakhov O. G., “Database analysis of optimal double-loop networks”, Prikladnaya Diskretnaya Matematika, 2024, no. 64, 56–71 (in Russian) | Zbl

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

[21] Bermond J. C., Illiades G., and Peyrat C., “An optimization problem in distributed loop computer networks”, Ann. New York Acad. Sci., 555 (1989), 45–55 | DOI | MR | Zbl

[22] Yebra J. L. A., Fiol M. A., Morillo P., and Alegre I., “The diameter of undirected graphs associated to plane tessellations”, Ars Combinatoria, 20B (1985), 159–172 | MR

[23] Sukhov A. M., Romanov A. Y., and Amerikanov A. A., “The problem of a symmetric graph with a maximum number of vertices and minimum diameter”, Lobachevskii J. Math., 44 (2023), 5453–5459 | DOI | MR | Zbl

[24] 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

[25] Li Y., Chen Y., Tai W., and Wang R., “The minimum distance diagram and diameter of undirected double-loop networks”, Proc. 3$^\text{rd}$ Inter. Conf. ICMEMTC (Taiyuan, China, 2016), 1682–1687

[26] 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

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

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

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

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

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

[32] Chen B.-X., Meng J.-X., and Xiao W.-J., “Some new optimal and suboptimal infinite families of undirected double-loop networks”, DMTCS, 8 (2006), 299–312 | MR

[33] Jha P. K., “Dimension-order routing algorithms for a family of minimal-diameter circulants”, J. Inter. Networks, 14:1 (2013), 1350002

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

[35] Monakhova E. A. and Monakhov O. G., “Generation and analysis of a dataset of optimal double-loop circulant networks”, Programmnaya Inzheneriya, 15:8 (2024), 402–410 (in Russian)

[36] Monakhova E. A. and Monakhov O. G., “A method for automatic search for families of optimal chordal ring networks”, J. Appl. Industr. Math., 18:1 (2024), 122–136 | DOI | MR | MR | Zbl

[37] Monakhov O. G., Monakhova E. A., Program for calculating characteristics of regular graphs with parametric description, Certificate of official registration of computer programs No 2013619128, Federal Service for Intellectual Property, Patents and Trademarks, M., 2013 (in Russian)

[38] Romanov A. Y., “Development of routing algorithms in networks-on-chip based on ring circulant topologies”, Heliyon, 5:4 (2019) https://www.sciencedirect.com/science/article/pii/S2405844018355208 | DOI

[39] Liu H. and Yang Y., “On the fault-tolerant routing in distributed loop networks”, J. Electronics (China), 17 (2000), 84–89 | DOI