A method for automatic search for families of optimal chordal ring networks

E. A. Monakhova ; O. G. Monakhov

Diskretnyj analiz i issledovanie operacij, Tome 31 (2024) no. 1, pp. 85-108

Résumé

Arden and Lee proposed a class of chordal ring networks of degree three as communication networks for multicomputer systems, derived a formula for the diameter, and produced an algorithm for finding the shortest paths for them. In this paper, it is shown that the formula for the diameter and the routing algorithm presented by them are inaccurate. We have obtained a large dataset containing parameters for describing optimal diameter chord rings for all the numbers of nodes up to 60 000 and found the exact lower bound for the diameter of chordal ring networks. A new method is proposed and the algorithms for automatic search for analytical descriptions of families of optimal chordal rings are realized based on an analysis of the database. Using the latter, analytical descriptions of over 500 new families of optimal chordal ring networks for many values of the number of nodes are found (only six families have been known until now in the literature). Tab. 5, illustr. 6, bibliogr. 26.

Détail

Keywords: optimal degree-three chordal network, diameter, extremal chordal graph, optimal chordal ring dataset.

Bibliographie

[1] Arden B. W., Lee H., “Analysis of chordal ring network”, IEEE Trans. Comput., C-30:4 (1981), 291–295 | DOI | MR

[2] Morillo P., Comellas F., Fiol M. A., “The optimization of chordal ring networks”, Communication technology, World Scientific, Singapore, 1987, 295–299

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

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

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

[6] Monakhova E. A., “A survey on undirected circulant graphs”, Discrete Math. Algorithms Appl., 4:1 (2012), 1250002, 30 pp. | DOI | MR | Zbl

[7] Pedersen J. M., Riaz M. T., Madsen O. B., “Distances in generalized double rings and degree three chordal rings”, Parallel and distributed computing and networks, Proc. IASTED Int. Conf. (Innsbruck, Austria, Feb. 15–17, 2005), ACTA Press, Calgary, 2005, 153–158

[8] Parhami B., “Periodically regular chordal rings are preferable to double-ring networks”, J. Interconnect. Netw., 9:1 (2008), 99–126 | DOI

[9] Farah R. N., Chien S. L. E., Othman M., “Optimum free-table routing in the optimised degree six $3$-modified chordal ring network”, J. Commun., 12:12 (2017), 677–682 | DOI | MR

[10] Hwang F. K., Wright P. E., “Survival reliability of some double-loop networks and chordal rings”, IEEE Trans. Comput., 44:12 (1995), 1468–1471 | DOI | Zbl

[11] Chen S. K., Hwang F. K., Liu Y. C., “Some combinatorial properties of mixed chordal rings”, J. Interconnect. Netw., 4:1 (2003), 3–16 | DOI

[12] Stojmenović I., “Honeycomb networks: Topological properties and communication algorithms”, IEEE Trans. Parallel Distrib. Syst., 8 (1997), 281–305 | MR

[13] Ahmad M., Zahid Z., Zavaid M., Bonyah E., “Studies of chordal ring networks via double metric dimensions”, Math. Probl. Eng., 98 (2022), 8303242, 7 pp.

[14] Bujnowski S., Marciniak B., Oyerinde O. O., Lutowski Z., Flizikowski A., Galan S. G., “The possibility of equalising the transmission properties of networks described by chordal rings”, Proc. 15th Int. Conf. Signal Processing and Communication Systems (Sydney, Australia, Dec. 13–15, 2021), IEEE, Piscataway, 2021, 8 pp. | MR

[15] Irwan N., Othman M., Farah R. N., “Network properties for classes of chordal ring network degree three topologies”, Proc. Int. Conf. Intelligent Network and Computing (Kuala Lumpur, Malaysia, Nov. 26–28, 2010), IEEE, Piscataway, 2010, 16–20

[16] Monakhov O. G., Monakhova E. A., “A class of parametric regular networks for multicomputer architectures”, Comput. Sist. J., 4:2 (2000), 85–93

[17] Huang H.-C., The diameter-edge invariant property of chordal ring networks, Master Thes., Natl. Chiao Tung Univ., Hsinchu, 2009, 30 pp.

[18] Loudiki L., Kchkech M., Essaky E. H., A new approach for computing the distance and the diameter in circulant graphs, Cornell Univ., Ithaca, NY, 2022, 14 pp., arXiv: 2210.11116

[19] Monakhov O. G., Monakhova E. A., Kireev S. E., “Parallel generation and analysis of optimal chordal ring networks using Python tools on Kunpeng prosessors”, Parallel computing technologies, Proc. 17th Int. Conf. (Astana, Kazakhstan, Aug. 21–25, 2023), Lect. Notes Comput. Sci., 14098, Springer, Cham, 2023, 126–135 | DOI

[20] Mollin R. A., “Quadratic polynomials producing consecutive, distinct primes and class groups of complex quadratic fields”, Acta Arithmetica, 74 (1996), 17–30 | DOI | MR | Zbl

[21] Marwan N., Romano M. C., Thiel M., Kurths J., “Recurrence plots for the analysis of complex systems”, Phys. Rep., 438:5–6 (2007), 237–329 | DOI | MR

[22] Barriere L., “Symmetry properties of chordal rings of degree $3$”, Discrete Appl. Math., 129 (2003), 211–232 | DOI | MR | Zbl

[23] Lee H., Modeling of multi-microcomputer networks, PhD Thes., Princeton Univ., Princeton, NJ, 1979

[24] Gutierrez J., Riaz T., Pedersen J., Labeaga S., Madsen O., “Degree $3$ networks topological routing”, Image Process. Commun., 14:4 (2009), 35–48

[25] Gutierrez J., Riaz T., Pedersen J., Labeaga S., Madsen O., “On topological routing on degree $3$ chordal rings”, Proc. 1st Int. Conf. Image Processing Communications (Bydgoszcz, Poland, Sept. 16–18, 2009), Acad. Publ. House EXIT, Warsaw, 2009, 59020255, 8 pp.

[26] Monakhova E. A., Monakhov O. G., 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