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 + α, 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.
Download file
Counter downloads: 4
- Title Discovery of infinite families of optimal double-loop networks with a given template of generators
- Headline Discovery of infinite families of optimal double-loop networks with a given template of generators
- Publesher
Tomsk State University - Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 66
- Date:
- DOI 10.17223/20710410/66/9
Keywords
dataset of optimal networks, undirected double-loop networks, circulant networks, minimum diameterAuthors
References
Bermond J.-C., Cornelias F., and Hsu D. F. Distributed loop computer networks: a survey //j. Parallel Distrib.Comput. 1995. No. 24 (1). P.2-10.
Hwang F.K. A survey on multi-loop networks // Theoret.Comput. Sci. 2003. V. 299. P. 107-121.
Монахова Э. А. Структурные и коммуникативные свойства циркулянтных сетей // Прикладная дискретная математика. 2011. УЗ. С.92-115.
Huang X., Ramos A. F., and Deng Y. Optimal circulant graphs as low-latency network topologies //j. Supercomput. 2022. V. 78. P. 13491-13510.
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. 2023. V. 10. No. 1. P.413-425.
Perez-Roses H., Bras-Amoros M., and Seradilla-Merinero J. M. Greedy routing in circulant networks // Graphs Combinatorics. 2022. V. 38. Iss.3.
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. 2022. V.9. No. 2. P.932-946.
Chen B.-X., Meng J.-X., and Xiao W.-J. A constant time optimal routing algorithm for undirected double-loop networks // Proc. 1th Int. Conf. Mobile Ad-hoc and Sensor Networks MSN 2005, Wuhan, China, December 2005. P.309-316.
Hoffmann R., Deserable D., and Seredynski F. Cellular automata rules solving the wireless sensor network coverage problem // Natural Computing. 2022. V. 21. P.417-447.
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. P. 180-183.
Erickson A., Stewart I. A., Navaridas J., and Kiasari A. E. The stellar transformation: Prom interconnection networks to datacenter networks // Computer Networks. 2017. V. 113. P. 29-45.
Fei J. and Lu С. Adaptive sliding mode control of dynamic systems using double loop recurrent neural network structure // IEEE Trans. Neural Netw. Learn. Svst. 2018. V. 29. P. 1275-1286.
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. 2021. V. 9. P. 160836-160846.
Монахова Э.А. Об аналитическом описании оптимальных двумерных диофантовых структур однородных вычислительных систем // Вычислительные системы. 1981. №90. С.81-91.
Boesch F. and Wang J.-F. Reliable circulant networks with minimum transmission delay // IEEE Trans. Circuits Svst. 1985. V. 32. No. 12. P. 1286-1291.
Tzvieli D. Minimal diameter double-loop networks. 1. Large infinite optimal families // Networks. 1991. V.21. P.387-415.
Liu H., Li X., and Wang S. Construction of dual optimal bidirectional double-loop networks for optimal routing // Mathematics. 2022. V. 10. P. 147.
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. 2020. V.8. P.215010-215019.
Монахова Э. А., Монахов О. Г. Анализ базы данных оптимальных двухконтурных кольцевых сетей // Прикладная дискретная математика. 2024. №64. С. 56-71.
Монахова Э. А. Синтез оптимальных диофантовых структур // Вычислительные системы. 1979. №80. С. 18-35.
Bermond J. С., Illiades G., and Peyrat С. An optimization problem in distributed loop computer networks // Ann. New York Acad. Sci. 1989. V. 555. C. 45-55.
Yebra J.L.A., Fiol M.A., Morillo P., and Alegre L The diameter of undirected graphs associated to plane tessellations // Ars Combinatoria. 1985. No.20B. P. 159-172.
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. 2023. V. 44. P. 5453-5459.
Du D.-Z., Hsu D. F., Li Q., and Xu J. A combinatorial problem related to distributed loop networks // Networks. 1990. V.20. P.173-180.
Li Y., Chen Y., Tai W., and Wang R. The minimum distance diagram and diameter of undirected double-loop networks // Proc. 3rd Inter. Conf. ICMEMTC. Taiyuan, China, 2016. P. 1682-1687.
Loudiki L., Kchikech M., and Essaky E. H. A New Approach for Computing the Distance and the Diameter in Circulant Graphs, https://arxiv.org/abs/2210.11116. 2022.
Jha P. K. Dense bipartite circulants and their routing via rectangular twisted torus // Discr. Appl. Math. 2014. V. 166. P. 141-158.
Jha P.K. and Smith J. D. H. Cycle Kronecker products that are representable as optimal circulants // Discr. Appl. Math. 2015. V. 181. P. 130-138.
Liu H., Yang Y., and Hu M. Tight optimal infinite families of undirected double-loop networks // Systems Engineering Theory and Practice. 2002. V. 1. P. 75-79.
Монахова Э. А., Монахов О. Г. Эволюционный синтез семейств оптимальных двумерных циркулянтных сетей j j Вестник СибГУТИ. 2014. №2. С. 72-81.
Jha K.P. Tight-optimal circulants vis-a-vis twisted tori // Discr. Appl. Math. 2014. V. 175. P. 24-34.
Chen B.-X., Meng J.-X., and Xiao W.-J. Some new optimal and suboptimal infinite families of undirected double-loop networks // DMTCS. 2006. V.8. P.299-312.
Discovery of infinite families of optimal double-loop networks with a given template of generators | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2024. № 66. DOI: 10.17223/20710410/66/9
Download full-text version
Counter downloads: 129