Cluster-Fault Tolerant Routing in a Torus
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...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2020-06-01
|
| Series: | Sensors |
| Subjects: | |
| Online Access: | https://www.mdpi.com/1424-8220/20/11/3286 |
| _version_ | 1827715369844867072 |
|---|---|
| author | Antoine Bossard Keiichi Kaneko |
| author_facet | Antoine Bossard Keiichi Kaneko |
| author_sort | Antoine Bossard |
| collection | DOAJ |
| description | 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 <inline-formula> <math display="inline"> <semantics> <mi>n</mi> </semantics> </math> </inline-formula>-dimensional <inline-formula> <math display="inline"> <semantics> <mi>k</mi> </semantics> </math> </inline-formula>-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 <inline-formula> <math display="inline"> <semantics> <mrow> <mi>n</mi> <mo>(</mo> <mn>2</mn> <mi>k</mi> <mo>+</mo> <mo>⌊</mo> <mi>k</mi> <mo>/</mo> <mn>2</mn> <mo>⌋</mo> <mo>−</mo> <mn>2</mn> <mo>)</mo> </mrow> </semantics> </math> </inline-formula> with an <inline-formula> <math display="inline"> <semantics> <mrow> <mi>O</mi> <mo>(</mo> <msup> <mi>n</mi> <mn>2</mn> </msup> <msup> <mi>k</mi> <mn>2</mn> </msup> <mo>|</mo> <mi>F</mi> <mo>|</mo> <mo>)</mo> </mrow> </semantics> </math> </inline-formula> worst-case time complexity with <inline-formula> <math display="inline"> <semantics> <mi>F</mi> </semantics> </math> </inline-formula> the set of faulty nodes induced by the faulty clusters. |
| first_indexed | 2024-03-10T19:17:10Z |
| format | Article |
| id | doaj.art-a4ff96874fda490fae19020d9fba26ba |
| institution | Directory Open Access Journal |
| issn | 1424-8220 |
| language | English |
| last_indexed | 2024-03-10T19:17:10Z |
| publishDate | 2020-06-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Sensors |
| spelling | doaj.art-a4ff96874fda490fae19020d9fba26ba2023-11-20T03:18:57ZengMDPI AGSensors1424-82202020-06-012011328610.3390/s20113286Cluster-Fault Tolerant Routing in a TorusAntoine Bossard0Keiichi Kaneko1Graduate School of Science, Kanagawa University, Kanagawa 259-1293, JapanInstitute of Engineering, Tokyo University of Agriculture and Technology, Tokyo 184-8588, JapanThe 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 <inline-formula> <math display="inline"> <semantics> <mi>n</mi> </semantics> </math> </inline-formula>-dimensional <inline-formula> <math display="inline"> <semantics> <mi>k</mi> </semantics> </math> </inline-formula>-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 <inline-formula> <math display="inline"> <semantics> <mrow> <mi>n</mi> <mo>(</mo> <mn>2</mn> <mi>k</mi> <mo>+</mo> <mo>⌊</mo> <mi>k</mi> <mo>/</mo> <mn>2</mn> <mo>⌋</mo> <mo>−</mo> <mn>2</mn> <mo>)</mo> </mrow> </semantics> </math> </inline-formula> with an <inline-formula> <math display="inline"> <semantics> <mrow> <mi>O</mi> <mo>(</mo> <msup> <mi>n</mi> <mn>2</mn> </msup> <msup> <mi>k</mi> <mn>2</mn> </msup> <mo>|</mo> <mi>F</mi> <mo>|</mo> <mo>)</mo> </mrow> </semantics> </math> </inline-formula> worst-case time complexity with <inline-formula> <math display="inline"> <semantics> <mi>F</mi> </semantics> </math> </inline-formula> the set of faulty nodes induced by the faulty clusters.https://www.mdpi.com/1424-8220/20/11/3286fault tolerancesensorIoTalgorithminformation disseminationinterconnection network |
| spellingShingle | Antoine Bossard Keiichi Kaneko Cluster-Fault Tolerant Routing in a Torus Sensors fault tolerance sensor IoT algorithm information dissemination interconnection network |
| title | Cluster-Fault Tolerant Routing in a Torus |
| title_full | Cluster-Fault Tolerant Routing in a Torus |
| title_fullStr | Cluster-Fault Tolerant Routing in a Torus |
| title_full_unstemmed | Cluster-Fault Tolerant Routing in a Torus |
| title_short | Cluster-Fault Tolerant Routing in a Torus |
| title_sort | cluster fault tolerant routing in a torus |
| topic | fault tolerance sensor IoT algorithm information dissemination interconnection network |
| url | https://www.mdpi.com/1424-8220/20/11/3286 |
| work_keys_str_mv | AT antoinebossard clusterfaulttolerantroutinginatorus AT keiichikaneko clusterfaulttolerantroutinginatorus |