{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,23]],"date-time":"2026-01-23T09:46:20Z","timestamp":1769161580827,"version":"3.49.0"},"reference-count":33,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2014,12,8]],"date-time":"2014-12-08T00:00:00Z","timestamp":1417996800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"European HiPEAC Network of Excellence and the JSA no. 2013-119"},{"name":"Spanish FPU","award":["AP2010-4900"],"award-info":[{"award-number":["AP2010-4900"]}]},{"name":"ERC-321253 (RoMoL)"},{"name":"Spanish Science and Technology Commission (CICYT) under contracts TIN2010-21291-C02-02 and TIN2013-46957-C2-2-P"},{"name":"IBM\/BSC Technology Center for Supercomputing agreement"},{"name":"European Union FP7 under Agreements ICT-288777 (Mont-Blanc)"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Archit. Code Optim."],"published-print":{"date-parts":[[2015,1,9]]},"abstract":"<jats:p>Current High-Performance Computing (HPC) and data center networks rely on large-radix routers. Hamming graphs (Cartesian products of complete graphs) and dragonflies (two-level direct networks with nodes organized in groups) are some direct topologies proposed for such networks. The original definition of the dragonfly topology is very loose, with several degrees of freedom, such as the inter- and intragroup topology, the specific global connectivity, and the number of parallel links between groups (or trunking level). This work provides a comprehensive analysis of the topological properties of the dragonfly network, providing balancing conditions for network dimensioning, as well as introducing and classifying several alternatives for the global connectivity and trunking level. From a topological study of the network, it is noted that a Hamming graph can be seen as a canonical dragonfly topology with a high level of trunking. Based on this observation and by carefully selecting the global connectivity, the Dimension Order Routing (DOR) mechanism safely used in Hamming graphs is adapted to dragonfly networks with trunking. The resulting routing algorithms approximate the performance of minimal, nonminimal, and adaptive routings typically used in dragonflies but without requiring virtual channels to avoid packet deadlock, thus allowing for lower cost router implementations. This is obtained by properly selecting the link to route between groups based on a graph coloring of network routers. Evaluations show that the proposed mechanisms are competitive with traditional solutions when using the same number of virtual channels and enable for simpler implementations with lower cost. Finally, multilevel dragonflies are discussed, considering how the proposed mechanisms could be adapted to them.<\/jats:p>","DOI":"10.1145\/2677038","type":"journal-article","created":{"date-parts":[[2014,12,8]],"date-time":"2014-12-08T16:17:14Z","timestamp":1418055434000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":27,"title":["Topological Characterization of Hamming and Dragonfly Networks and Its Implications on Routing"],"prefix":"10.1145","volume":"11","author":[{"given":"Crist\u00f3bal","family":"Camarero","sequence":"first","affiliation":[{"name":"University of Cantabria, Santander, Spain"}]},{"given":"Enrique","family":"Vallejo","sequence":"additional","affiliation":[{"name":"University of Cantabria, Santander, Spain"}]},{"given":"Ram\u00f3n","family":"Beivide","sequence":"additional","affiliation":[{"name":"University of Cantabria, Santander, Spain"}]}],"member":"320","published-online":{"date-parts":[[2014,12,8]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1654059.1654101"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2512433"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/12.21148"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/HOTI.2010.16"},{"key":"e_1_2_1_5_1","volume-title":"Proceedings off the 10th International Parallel Processing Symposium (IPPS\u201996)","author":"Bae M. M.","unstructured":"M. M. Bae and B. Bose . 1996. Resource placement in torus-based networks . In Proceedings off the 10th International Parallel Processing Symposium (IPPS\u201996) . 327--331. M. M. Bae and B. Bose. 1996. Resource placement in torus-based networks. In Proceedings off the 10th International Parallel Processing Symposium (IPPS\u201996). 327--331."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2063384.2063486"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1984.1676437"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/HiPC.2013.6799144"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.4153\/CMB-1966-001-6"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0195-6698(85)80043-3"},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the 2012 International Conference on High Performance Computing, Networking, Storage and Analysis (SC\u201912)","author":"Faanes G.","unstructured":"G. Faanes , A. Bataineh , D. Roweth , T. Court , E. Froese , B. Alverson , T. Johnson , J. Kopnick , M. Higgins , and J. Reinhard . 2012. Cray cascade: A scalable HPC system based on a Dragonfly network . In Proceedings of the 2012 International Conference on High Performance Computing, Networking, Storage and Analysis (SC\u201912) . 1--9. G. Faanes, A. Bataineh, D. Roweth, T. Court, E. Froese, B. Alverson, T. Johnson, J. Kopnick, M. Higgins, and J. Reinhard. 2012. Cray cascade: A scalable HPC system based on a Dragonfly network. In Proceedings of the 2012 International Conference on High Performance Computing, Networking, Storage and Analysis (SC\u201912). 1--9."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/HOTI.2013.16"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2482759.2482763"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICPP.2012.46"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICPP.2013.72"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCOM.1981.1095021"},{"key":"e_1_2_1_17_1","volume-title":"International Supercomputing Conference (ISC\u201914)","author":"Hazra Raj","year":"2014","unstructured":"Raj Hazra . 2014 . Accelerating insights... in the technical computing transformation . International Supercomputing Conference (ISC\u201914) keynote. Raj Hazra. 2014. Accelerating insights... in the technical computing transformation. International Supercomputing Conference (ISC\u201914) keynote."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(84)90020-0"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1147\/rd.45.0497"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1555754.1555783"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250662.1250679"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISCA.2008.19"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISCA.2005.35"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2003.1190592"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2011.03.038"},{"key":"e_1_2_1_26_1","volume-title":"Moore graphs and beyond: A survey of the degree\/diameter problem","author":"Miller Mirka","year":"2013","unstructured":"Mirka Miller and Jozef Sir\u00e1n . 2013. Moore graphs and beyond: A survey of the degree\/diameter problem ( 2 nd Ed). The Electronic Journal of Combinatorics ( 5 2013 ). Mirka Miller and Jozef Sir\u00e1n. 2013. Moore graphs and beyond: A survey of the degree\/diameter problem (2nd Ed). The Electronic Journal of Combinatorics (5 2013).","edition":"2"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(82)90021-8"},{"key":"e_1_2_1_28_1","volume-title":"Proceedings of the 7th International Symposium on High-Performance Computer Architecture (HPCA\u201901)","author":"Peh Li-Shiuan","unstructured":"Li-Shiuan Peh and William J. Dally . 2001. A delay model and speculative architecture for pipelined routers . In Proceedings of the 7th International Symposium on High-Performance Computer Architecture (HPCA\u201901) . IEEE Computer Society, Washington, DC, 255. Li-Shiuan Peh and William J. Dally. 2001. A delay model and speculative architecture for pipelined routers. In Proceedings of the 7th International Symposium on High-Performance Computer Architecture (HPCA\u201901). IEEE Computer Society, Washington, DC, 255."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/11549468_111"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2556857.2556860"},{"key":"e_1_2_1_32_1","volume-title":"Proceedings of the 15th Annual International Symposium on Computer Architecture (ISCA\u201988)","author":"Tamir Y.","unstructured":"Y. Tamir and G. L. Frazier . 1988. High-performance multi-queue buffers for VLSI communications switches . In Proceedings of the 15th Annual International Symposium on Computer Architecture (ISCA\u201988) . IEEE Computer Society Press, Los Alamitos, CA, USA, 343--354. Y. Tamir and G. L. Frazier. 1988. High-performance multi-queue buffers for VLSI communications switches. In Proceedings of the 15th Annual International Symposium on Computer Architecture (ISCA\u201988). IEEE Computer Society Press, Los Alamitos, CA, USA, 343--354."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1137\/0211027"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2464996.2465436"}],"container-title":["ACM Transactions on Architecture and Code Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2677038","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2677038","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T06:11:56Z","timestamp":1750227116000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2677038"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,12,8]]},"references-count":33,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2015,1,9]]}},"alternative-id":["10.1145\/2677038"],"URL":"https:\/\/doi.org\/10.1145\/2677038","relation":{},"ISSN":["1544-3566","1544-3973"],"issn-type":[{"value":"1544-3566","type":"print"},{"value":"1544-3973","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,12,8]]},"assertion":[{"value":"2014-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-12-08","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}