{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:14:55Z","timestamp":1750306495292,"version":"3.41.0"},"reference-count":28,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2016,1,29]],"date-time":"2016-01-29T00:00:00Z","timestamp":1454025600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Parallel Comput."],"published-print":{"date-parts":[[2016,3,15]]},"abstract":"<jats:p>Folded-Clos networks, also known as fat-trees, have been widely used as interconnects in large-scale high-performance computing clusters. Although users often treat such interconnects as replacements of nonblocking crossbar switches that can carry out any permutation communication without contention, the networking capability of such interconnects without a centralized controller in computer communication environments is not well understood. In this article, we investigate nonblocking two-level folded-Clos networks with deterministic single-path routing, but no centralized controller, and establish the nonblocking condition. The results indicate that nonblocking two-level folded-Clos networks without a centralized controller are much more expensive to construct than the traditional nonblocking networks in the telecommunication environment. Practical two-level folded-Clos based interconnects are blocking. For such interconnects, we establish the lower bound for worst-case contention for permutations with any deterministic single-path routing scheme, show that existing routing schemes perform poorly in terms of worst-case contention for permutations, present a routing scheme that achieves the theoretical optimal, and empirically compare the performance of existing schemes with the optimal routing scheme. The techniques developed for two-level folded-Clos networks are further extended for the general fat-trees of any heights.<\/jats:p>","DOI":"10.1145\/2858654","type":"journal-article","created":{"date-parts":[[2016,2,1]],"date-time":"2016-02-01T20:37:54Z","timestamp":1454359074000},"page":"1-22","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["On Folded-Clos Networks with Deterministic Single-Path Routing"],"prefix":"10.1145","volume":"2","author":[{"given":"Xin","family":"Yuan","sequence":"first","affiliation":[{"name":"Florida State University, Tallahassee, FL"}]},{"given":"Wickus","family":"Nienaber","sequence":"additional","affiliation":[{"name":"Florida State University, Tallahassee, FL"}]},{"given":"Santosh","family":"Mahapatra","sequence":"additional","affiliation":[{"name":"Florida State University, Tallahassee, FL"}]}],"member":"320","published-online":{"date-parts":[[2016,1,29]]},"reference":[{"volume-title":"Proceedings of the 10th International Parallel Processing Symposium. 258--267","year":"1996","author":"Aydogan Y.","key":"e_1_2_1_1_1"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1962.tb03990.x"},{"key":"e_1_2_1_3_1","unstructured":"V. E. Benes. 1965. Mathematical Theory of Connecting Networks and Telephone Traffic. Vol. 17. Academic Press.  V. E. Benes. 1965. Mathematical Theory of Connecting Networks and Telephone Traffic. Vol. 17. Academic Press."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/71.642949"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1953.tb01433.x"},{"volume-title":"Proceedings of the 14th International Parallel and Distributed Processing Symposium (IPDPS'00)","year":"2000","author":"Flich J.","key":"e_1_2_1_6_1"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/HOTI.2008.21"},{"volume-title":"Proceedings of the 21st IEEE International Parallel and Distributed Processing Symposium. 1--8. DOI:http:\/\/dx.doi.org\/10","year":"2007","author":"Gomez C.","key":"e_1_2_1_8_1"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1985.46"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/CLUSTR.2008.4663762"},{"key":"e_1_2_1_11_1","unstructured":"InfiniBandTM Trade Association. 2004. InfiniBandTM Architecture Specification. Release 1.2.  InfiniBand TM Trade Association. 2004. InfiniBand TM Architecture Specification. Release 1.2."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2008.4536345"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1999.1058"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1188455.1188552"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/4492.4495"},{"volume-title":"Proceedings of the 18th International Parallel and Distributed Processing Symposium. 11","year":"2004","author":"Lin Xuan-Yi","key":"e_1_2_1_16_1"},{"volume-title":"Proceedings of the 2001 International Conference on Parallel Processing. 427--434","year":"2001","author":"Lopez P.","key":"e_1_2_1_17_1"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2008.144"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/645605.663087"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/645607.661664"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/CLUSTR.2009.5289145"},{"volume-title":"ORCS: An Oblivious Routing Congestion Simulator. TR-675","year":"2009","author":"Schneider T.","key":"e_1_2_1_22_1"},{"key":"e_1_2_1_23_1","unstructured":"A. Singh. 2005. Load-Balanced Routing in Interconnection Networks. Ph.D. Dissertation. Stanford University Stanford CA.  A. Singh. 2005. Load-Balanced Routing in Interconnection Networks. Ph.D. Dissertation. Stanford University Stanford CA."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/12.754994"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2011.27"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2009.2012853"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1002\/cpe.v22:2"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2012.01.018"}],"container-title":["ACM Transactions on Parallel Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2858654","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2858654","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T05:48:43Z","timestamp":1750225723000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2858654"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,1,29]]},"references-count":28,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2016,3,15]]}},"alternative-id":["10.1145\/2858654"],"URL":"https:\/\/doi.org\/10.1145\/2858654","relation":{},"ISSN":["2329-4949","2329-4957"],"issn-type":[{"type":"print","value":"2329-4949"},{"type":"electronic","value":"2329-4957"}],"subject":[],"published":{"date-parts":[[2016,1,29]]},"assertion":[{"value":"2013-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-01-29","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}