Name
Title | ||
|---|---|---|
Fault tolerance analysis of mesh networks with uniform versus nonuniform node failure probability |
Abstract | ||
|---|---|---|
Mesh networks have been applied to build large scale multicomputer systems and Network-on-Chips (NoCs). Mesh networks perform poorly in tolerating faults in the view of worst-case analysis, so it is practically important for multicomputer systems and NoCs manufactures to determine the lower bound for the mesh network connectivity probability when the node failure probability and the network size are given. In this paper, we study the topic based on k-submesh model under two fault models: Each node has uniform or nonuniform failure probability. We develop a novel technique to formally derive lower bound on the connectivity probability for mesh networks. Our study shows that mesh networks of practical size can tolerate a large number of faulty nodes and maintain higher connectivity probability, thus are reliable and trustworthy enough for multicomputer systems and NoCs. For example, suppose we are building a mesh network of 40@?000 nodes (e.g., M"2"0"0"x"2"0"0) and require a network connectivity probability 99%, we only need to bound the uniform node failure probability by 0.25%. On the other hand, for the same size network M"2"0"0"x"2"0"0, the mesh network connectivity probability can maintain 95.88% even the network runs one million seconds uninterruptedly under exponential distribution node failure probability with failure rate 10^-^9 level. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1016/j.ipl.2011.12.013 | Inf. Process. Lett. |
Keywords | Field | DocType |
network size,connectivity probability,multicomputer system,network connectivity probability,higher connectivity probability,node failure probability,mesh network connectivity probability,fault tolerance analysis,mesh network,uniform node failure probability,nonuniform failure probability,fault tolerance | Mesh networking,Switched mesh,Computer science,Failure rate,Computer network,Order One Network Protocol,Fault tolerance,Exponential distribution,Wireless mesh network,Shared mesh | Journal |
Volume | Issue | ISSN |
112 | 10 | 0020-0190 |
Citations | PageRank | References |
1 | 0.36 | 16 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| GaoCai Wang | 1 | 19 | 7.92 |
| Guojun Wang | 2 | 1740 | 144.41 |
| Zhiguang Shan | 3 | 97 | 19.01 |