{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,29]],"date-time":"2026-03-29T15:57:46Z","timestamp":1774799866214,"version":"3.50.1"},"reference-count":33,"publisher":"MDPI AG","issue":"11","license":[{"start":{"date-parts":[[2020,6,9]],"date-time":"2020-06-09T00:00:00Z","timestamp":1591660800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["19K11887"],"award-info":[{"award-number":["19K11887"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Sensors"],"abstract":"<jats:p>The number of Internet-connected devices grows very rapidly, with even fears of running out of available IP addresses. It is clear that the number of sensors follows this trend, thus inducing large sensor networks. It is insightful to make the comparison with the huge number of processors of modern supercomputers. In such large networks, the problem of node faults necessarily arises, with faults often happening in clusters. The tolerance to faults, and especially cluster faults, is thus critical. Furthermore, thanks to its advantageous topological properties, the torus interconnection network has been adopted by the major supercomputer manufacturers of the recent years, thus proving its applicability. Acknowledging and embracing these two technological and industrial aspects, we propose in this paper a node-to-node routing algorithm in an    n   -dimensional    k   -ary torus that is tolerant to faults. Not only is this algorithm tolerant to faulty nodes, it also tolerates faulty node clusters. The described algorithm selects a fault-free path of length at most     n ( 2 k + \u230a k \/ 2 \u230b \u2212 2 )     with an     O (  n 2   k 2  | F | )     worst-case time complexity with    F    the set of faulty nodes induced by the faulty clusters.<\/jats:p>","DOI":"10.3390\/s20113286","type":"journal-article","created":{"date-parts":[[2020,6,9]],"date-time":"2020-06-09T08:49:11Z","timestamp":1591692551000},"page":"3286","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":18,"title":["Cluster-Fault Tolerant Routing in a Torus"],"prefix":"10.3390","volume":"20","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9381-9346","authenticated-orcid":false,"given":"Antoine","family":"Bossard","sequence":"first","affiliation":[{"name":"Graduate School of Science, Kanagawa University, Kanagawa 259-1293, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1790-4615","authenticated-orcid":false,"given":"Keiichi","family":"Kaneko","sequence":"additional","affiliation":[{"name":"Institute of Engineering, Tokyo University of Agriculture and Technology, Tokyo 184-8588, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2020,6,9]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"516","DOI":"10.1016\/j.chb.2016.04.023","article-title":"An empirical examination of consumer adoption of Internet of things services: Network externalities and concern for information privacy perspectives","volume":"62","author":"Hsu","year":"2016","journal-title":"Comput. Hum. Behav."},{"key":"ref_2","unstructured":"Nordrum, A. (2016). Popular Internet of things forecast of 50 billion devices by 2020 is outdated. IEEE Spectrum, Available online: https:\/\/spectrum.ieee.org\/tech-talk\/telecom\/internet\/popular-internet-of-things-forecast-of-50-billion-devices-by-2020-is-outdated."},{"key":"ref_3","unstructured":"Duato, J., Yalamanchili, S., and Ni, L. (2003). Interconnection Networks: An Engineering Approach, Morgan Kaufmann."},{"key":"ref_4","unstructured":"Cray Inc (2020, June 08). Cray XE6 Brochure. Available online: https:\/\/www.cray.com\/sites\/default\/files\/resources\/CrayXE6Brochure.pdf."},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Ajima, Y., Inoue, T., Hiramoto, S., Uno, S., Sumimoto, S., Miura, K., Shida, N., Kawashima, T., Okamoto, T., and Moriyama, O. (2014, January 22\u201326). Tofu interconnect 2: System-on-chip integration of high-performance interconnect. Proceedings of the 29th International Supercomputing Conference, Leipzig, Germany.","DOI":"10.1007\/978-3-319-07518-1_35"},{"key":"ref_6","unstructured":"TOP500 (2020, June 08). TOP500 List Refreshed, US Edged out of Third Place. Available online: https:\/\/www.top500.org\/news\/top500-list-refreshed-us-edged-out-of-third-place\/."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"867","DOI":"10.1109\/12.2234","article-title":"Topological properties of hypercubes","volume":"37","author":"Saad","year":"1988","journal-title":"IEEE Trans. Comput."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1145\/2465.2467","article-title":"The cosmic cube","volume":"28","author":"Seitz","year":"1985","journal-title":"Commun. ACM"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"723","DOI":"10.1515\/amcs-2015-0052","article-title":"Torus-Connected Cycles: A simple and scalable topology for interconnection networks","volume":"25","author":"Bossard","year":"2015","journal-title":"Int. J. Appl. Math. Comput. Sci."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"96","DOI":"10.4064\/fm-10-1-96-115","article-title":"Zur allgemeinen Kurventheorie","volume":"10","author":"Menger","year":"1927","journal-title":"Fundam. Math."},{"key":"ref_11","unstructured":"Sedgewick, R. (2002). Algorithms in C\u2014Part 5, Graph Algorithms, Addison-Wesley. [3rd ed.]."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1016\/j.jnca.2015.07.014","article-title":"Fault resilience in sensor networks: Distributed node-disjoint multi-path multi-sink forwarding","volume":"57","author":"Chakraborty","year":"2015","journal-title":"J. Netw. Comput. Appl."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"555","DOI":"10.1109\/12.21148","article-title":"A group-theoretic model for symmetric interconnection networks","volume":"38","author":"Akers","year":"1989","journal-title":"IEEE Trans. Comput."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"1739","DOI":"10.1007\/s11276-016-1432-7","article-title":"Hybrid data dissemination protocol (HDDP) for wireless sensor networks","volume":"24","author":"Guerroumi","year":"2018","journal-title":"Wirel. Netw."},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Shi, X., An, X., Zhao, Q., Liu, H., Xia, L., Sun, X., and Guo, Y. (2019). State-of-the-art Internet of things in protected agriculture. Sensors, 19.","DOI":"10.3390\/s19081833"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"329","DOI":"10.2503\/hortj.OKD-136","article-title":"Shortening of the juvenile phase of the southern highbush blueberry (Vaccinium corymbosum L. interspecific hybrid) grown controlled rooms under artificial light","volume":"87","author":"Watanabe","year":"2018","journal-title":"Hortic. J."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"701","DOI":"10.1109\/71.940745","article-title":"Recursive diagonal torus: An interconnection network for massively parallel computers","volume":"12","author":"Yang","year":"2001","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"ref_18","first-page":"1153","article-title":"Fault tolerant routing in toroidal networks","volume":"79","author":"Gu","year":"1996","journal-title":"IEICE Trans. Inf. Syst."},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Li, Y., Peng, S., and Chu, W. (2005, January 2\u20135). Online adaptive fault-tolerant routing in 2D torus. Proceedings of the Third International Symposium on Parallel and Distributed Processing and Applications, Nanjing, China.","DOI":"10.1007\/11576235_20"},{"key":"ref_20","first-page":"173","article-title":"A set-to-set disjoint paths routing algorithm in tori","volume":"7","author":"Kaneko","year":"2017","journal-title":"Int. J. Netw. Comput."},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Bossard, A., and Kaneko, K. (2018). Torus pairwise disjoint-path routing. Sensors, 8.","DOI":"10.1109\/Cybermatics_2018.2018.00290"},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"964","DOI":"10.1109\/71.808128","article-title":"Unicast in hypercubes with large number of faulty nodes","volume":"10","author":"Gu","year":"1999","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"ref_23","first-page":"483","article-title":"Set-to-set fault tolerant routing in hypercubes","volume":"79","author":"Gu","year":"1996","journal-title":"IEICE Trans. Fundam. Electron. Commun. Comput. Sci."},{"key":"ref_24","first-page":"282","article-title":"Set-to-set fault tolerant routing in star graphs","volume":"79","author":"Gu","year":"1996","journal-title":"IEICE Trans. Inf. Syst."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"535","DOI":"10.1016\/j.ipl.2010.04.023","article-title":"Fault-tolerant routing in burnt pancake graphs","volume":"110","author":"Iwasaki","year":"2010","journal-title":"Inf. Process. Lett."},{"key":"ref_26","first-page":"272","article-title":"Hypercube fault tolerant routing with bit constraint","volume":"5","author":"Bossard","year":"2015","journal-title":"Int. J. Netw. Comput."},{"key":"ref_27","doi-asserted-by":"crossref","unstructured":"Iwasawa, N., Watanabe, T., Iwasaki, T., and Kaneko, K. (2010, January 21\u201323). Cluster-fault-tolerant routing in burnt pancake graphs. Proceedings of the 10th International Conference on Algorithms and Architectures for Parallel Processing, Busan, Korea.","DOI":"10.1007\/978-3-642-13136-3_27"},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"14","DOI":"10.1093\/comjnl\/39.1.14","article-title":"An efficient algorithm for node-to-node routing in hypercubes with faulty clusters","volume":"39","author":"Gu","year":"1996","journal-title":"Comput. J."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"1245","DOI":"10.1016\/S0167-8191(98)00050-7","article-title":"Node-to-set and set-to-set cluster fault tolerant routing in hypercubes","volume":"24","author":"Gu","year":"1998","journal-title":"Parallel Comput."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"1042","DOI":"10.1109\/12.620486","article-title":"k-pairwise cluster fault tolerant routing in hypercubes","volume":"46","author":"Gu","year":"1997","journal-title":"IEEE Trans. Comput."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1016\/0020-0190(95)00135-Y","article-title":"Node-to-node cluster fault tolerant routing in star graphs","volume":"56","author":"Gu","year":"1995","journal-title":"Inf. Process. Lett."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1002\/(SICI)1097-0037(200001)35:1<83::AID-NET7>3.0.CO;2-D","article-title":"Cluster fault-tolerant routing in star graphs","volume":"35","author":"Gu","year":"2000","journal-title":"Networks"},{"key":"ref_33","doi-asserted-by":"crossref","unstructured":"Diestel, R. (2010). Graph Theory, Springer. [4th ed.].","DOI":"10.1007\/978-3-642-14279-6"}],"container-title":["Sensors"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1424-8220\/20\/11\/3286\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T09:37:04Z","timestamp":1760175424000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1424-8220\/20\/11\/3286"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,9]]},"references-count":33,"journal-issue":{"issue":"11","published-online":{"date-parts":[[2020,6]]}},"alternative-id":["s20113286"],"URL":"https:\/\/doi.org\/10.3390\/s20113286","relation":{},"ISSN":["1424-8220"],"issn-type":[{"value":"1424-8220","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,6,9]]}}}