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 doubleloop 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.
Download file
Counter downloads: 5
- Title Database analysis of optimal double-loop networks
- Headline Database analysis of optimal double-loop networks
- Publesher
Tomsk State University - Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 64
- Date:
- DOI 10.17223/20710410/64/5
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.
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. 2006. V. 8. P.299-311.
Romanov A. Y. Development of routing algorithms in networks-on-chip based on ring circulant topologies // Helivon. 2019. V. 5. Iss.4. Article e01516.
Chen B.-X., Xiao W.-J., and Parhami B. Diameter formulas for a class of undirected doubleloop networks // Networks. 2005. V. 6(1). P. 1-15.
Jha К. P. Tight-optimal circulants vis-a-vis twisted tori // Discrete Appl. Math. 2014. V. 175. P. 24-34.
Huanping L. and Yixian Y.-J. On the fault-tolerant routing in distributed loop networks //j. Electronics. 2000. V. 17. P. 84-89.
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. Naniang, Jiangsu China, 2010. P.461-466.
Martinez C., Beivide R., Stafford E., et al. Modeling toroidal networks with the Gaussian integers // IEEE Trans.Comput. 2008. V.57. No. 8. P.1046-1056.
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 Н., Bras-Amoros М., and Seradilla-Merinero J. М. Greedy routing in circulant networks // Graphs Combinatorics. 2022. V. 38. Article 86.
Lewis R. R. Analysis and Construction of Extremal Circulant and Other Abelian Cayley Graphs. Ph.D. Thesis. The Open University, London, UK, 2022.
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. ScL Eng. 2022. V.9. No. 2. P.932-946.
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. Article 4016.
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.
Монахова Э. А. Синтез оптимальных диофантовых структур // Вычислительные системы. 1979. №80. С. 18-35.
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. 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 // Discrete 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 // Discrete 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 Eng. Theory Practice. 2002. V. 1. P. 75-79.
Jha P. K. Dimension-order routing algorithms for a family of minimal-diameter circulants //j.Interconn.Networks. 2013. V. 14. No. 1. Article 1350002. 24p.
Bermond J.-C. and Tzvieli D. Minimal diameter double-loop networks: Dense optimal families // Networks. 1991. V.21. P. 1-9.
Chen B.-X., Meng J.-X., and Xiao W.-J. A constant time optimal routing algorithm for undirected double-loop networks // LNCS. 2005. V.3794. P.308-316.
Monakhova E. A. Optimal circulant computer networks // Proc. PaCT'91. Novosibirsk, USSR, 1991. P.450-458.
Монахова Э. А., Монахов О. Г. Эволюционный синтез семейств оптимальных двумерных циркулянтных сетей j j Вестник СибГУТII. 2014. №2. С. 72-81.
Zerovnik J. and Pisanski T.Computing the diameter in multiple-loop networks //j. Algorithms. 1993. V. 14. P.226-243.
Romanov A. The dataset for optimal circulant topologies // Big Data Cogn.Comput. 2023. V. 7. P. 80.
Monakhova E. A. and Monakhov O. G. Generation and analysis of optimal double-loop circulant networks dataset // Proc. CEUR Workshop SibDATA. 2023. (to be published).
Storn R. and Price K. Differential evolution - A simple and efficient heuristic for global optimization over continuous spaces //j. Global Optimization. 1997. V. 11. P.341-359.
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. P.731-737.
Database analysis of optimal double-loop networks | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2024. № 64. DOI: 10.17223/20710410/64/5
Download full-text version
Counter downloads: 143