Reliability Evaluation of Generalized Exchanged Hypercubes Based on Imprecise Diagnosis Strategies
Abstract
Fault diagnostic analysis is extremely important for interconnection networks. The -diagnosis imprecise strategy plays an essential role in the reliability of networks. The -diagnosis strategy can detect up to faulty vertices which might include at most misdiagnosed vertices. The exchanged hypercube is obtained by systematically removing links from a binary hypercube, which has smaller maximum degree and Wiener index than the hypercube. We use to denote the generalized exchanged hypercube, and show in this paper that is -diagnosable with and under the PMC model and MM model. We also propose a -diagnosis algorithm on . As a side benefit, the -diagnosability of the dual-cube-like network can be directly obtained from our results.
References
- 1. , On the connection assignment problem of diagnosable systems, IEEE Trans. Electron. Comput. 16(6) (1967) 848–854. Crossref, ISI, Google Scholar
- 2. , Probabilistic diagnosis of multiprocessor systems, ACM Comput. Surv. 26(1) (1994) 121–139. Crossref, ISI, Google Scholar
- 3. , A comparison connection assignment for diagnosis of multiprocessor systems, Proceedings of the 7th Annual Symposium on Computer Architecture (
1981 ), pp. 31–36. Google Scholar - 4. , On self-diagnosable multiprocessor systems: Diagnosis by the comparison approach, IEEE Trans. Comput. 41(11) (1992) 1386–1396. Crossref, ISI, Google Scholar
- 5. , On the t/k-diagnosability of BC networks, Appl. Math. Comput. 225 (2013) 366–371. ISI, Google Scholar
- 6. , The t/k-diagnosability of star graph networks, IEEE Trans. Comput. 64(2) (2015) 547–555. Crossref, ISI, Google Scholar
- 7. , The t/k-diagnosability for regular networks, IEEE Trans. Comput. 65(10) (2015) 3157–3170. Crossref, ISI, Google Scholar
- 8. , The (t, k)-diagnosability of shuffle-cubes under PMC model, Int. J. Comput. Math. 4(2) (2019) 111–126. Google Scholar
- 9. , The extra connectivity, extra conditional diagnosability, and, t/m-diagnosability of arrangement graphs, IEEE Trans. Reliab. 65(3) (2016) 1248–1262. Crossref, ISI, Google Scholar
- 10. , The exchanged hypercube, IEEE Trans. Parallel Distrib. Syst. 16(9) (2005) 866–874. Crossref, ISI, Google Scholar
- 11. , Optimal edge congestion of exchanged hypercubes, IEEE Trans. Parallel Distrib. Syst. 27(1) (2015) 250–262. Crossref, ISI, Google Scholar
- 12. , ExCCC-DCN: A highly scalable, cost-effective and energy-efficient data center structure, IEEE Trans. Parallel Distrib. Syst. 28(4) (2016) 1046–1060. Crossref, ISI, Google Scholar
- 13. , Topological Structure and Analysis of Interconnection Networks,
Springer Science and Business Media , Vol. 7 (2013). Google Scholar - 14. , Dual-cubes: A new interconnection network for high-performance computer clusters, Proceedings of the 2000 International Computer Symposium, Workshop on Computer Architecture (
2000 ), pp. 51–57. Google Scholar - 15. , Linearly many faults in dual-cube-like networks, Theor. Comput. Sci. 472 (2013) 1–8. Crossref, ISI, Google Scholar
- 16. , On diagnosability of large fault sets in regular topology-based computer systems, IEEE Trans. Comput. 45(8) (1996) 892–903. Crossref, ISI, Google Scholar
- 17. , A (4n-9)/3 diagnosis algorithm on n-dimensional cube network, Inf. Sci. 177 (2007) 1771–1781. Crossref, ISI, Google Scholar
- 18. , 1-Perfect codes over dual-cubes vis-à-vis Hamming codes over hypercubse, IEEE Trans. Inform. Theory 61(8) (2015) 4259–4268. Crossref, ISI, Google Scholar
- 19. , A strong connectivity property of the generalized exchanged hypercube, Discrete Appl. Math. 216 (2017) 529–536. Crossref, ISI, Google Scholar
- 20. , Structural properties of generalized exchanged hypercubes, Emergent Comput. 24 (2017) 215–232. Crossref, Google Scholar
- 21. , On reliability of multiprocessor system based on star graph, IEEE Trans. Reliab. 64 (2019) 547–555. Google Scholar
- 22. , Reliability analysis of data center networks based on precise and imprecise diagnosis strategies, Theoret. Comput. Sci. 809 (2020) 189–203. Crossref, ISI, Google Scholar


