World Scientific
  • Search
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
×
Our website is made possible by displaying certain online content using javascript.
In order to view the full content, please disable your ad blocker or whitelist our website www.worldscientific.com.

System Upgrade on Tue, Oct 25th, 2022 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.

Reliability Evaluation of Generalized Exchanged Hypercubes Based on Imprecise Diagnosis Strategies

    Fault diagnostic analysis is extremely important for interconnection networks. The t/g-diagnosis imprecise strategy plays an essential role in the reliability of networks. The t/g-diagnosis strategy can detect up to t faulty vertices which might include at most g 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 GEH(s,t) to denote the generalized exchanged hypercube, and show in this paper that GEH(s,t) is [(g+1)sg(g+1)2+1]/g-diagnosable with 1st and 0gs1 under the PMC model and MM model. We also propose a t/g-diagnosis algorithm on GEH(s,t). As a side benefit, the t/g-diagnosability of the dual-cube-like network DCn can be directly obtained from our results.

    References

    • 1. F. P. Preparata, G. Metze and R. T. Chien, On the connection assignment problem of diagnosable systems, IEEE Trans. Electron. Comput. 16(6) (1967) 848–854. Crossref, ISIGoogle Scholar
    • 2. S. Lee and K. G. Shin, Probabilistic diagnosis of multiprocessor systems, ACM Comput. Surv. 26(1) (1994) 121–139. Crossref, ISIGoogle Scholar
    • 3. M. Malek, 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. A. Sengupta and A. T. Dahbura, On self-diagnosable multiprocessor systems: Diagnosis by the comparison approach, IEEE Trans. Comput. 41(11) (1992) 1386–1396. Crossref, ISIGoogle Scholar
    • 5. W. Yang, H. Lin and C. Qin, On the t/k-diagnosability of BC networks, Appl. Math. Comput. 225 (2013) 366–371. ISIGoogle Scholar
    • 6. S. Zhou, L. Lin, L. Xu and D. Wang, The t/k-diagnosability of star graph networks, IEEE Trans. Comput. 64(2) (2015) 547–555. Crossref, ISIGoogle Scholar
    • 7. L. Lin, L. Xu, S. Zhou and S.-Y. Hsieh, The t/k-diagnosability for regular networks, IEEE Trans. Comput. 65(10) (2015) 3157–3170. Crossref, ISIGoogle Scholar
    • 8. J. Li, L. Lin, Y. Huang and H. Yu, The (t, k)-diagnosability of shuffle-cubes under PMC model, Int. J. Comput. Math. 4(2) (2019) 111–126. Google Scholar
    • 9. L. Xu, L. Lin, S. Zhou and S.-Y. Hsieh, The extra connectivity, extra conditional diagnosability, and, t/m-diagnosability of arrangement graphs, IEEE Trans. Reliab. 65(3) (2016) 1248–1262. Crossref, ISIGoogle Scholar
    • 10. P. K. K. Loh, W. J. Hsu and Y. Pan, The exchanged hypercube, IEEE Trans. Parallel Distrib. Syst. 16(9) (2005) 866–874. Crossref, ISIGoogle Scholar
    • 11. T.-H. Tsai, Y.-C. Chen and J. J. Tan, Optimal edge congestion of exchanged hypercubes, IEEE Trans. Parallel Distrib. Syst. 27(1) (2015) 250–262. Crossref, ISIGoogle Scholar
    • 12. Z. Zhang, Y. Deng, G. Min, J. Xie and S. Huang, ExCCC-DCN: A highly scalable, cost-effective and energy-efficient data center structure, IEEE Trans. Parallel Distrib. Syst. 28(4) (2016) 1046–1060. Crossref, ISIGoogle Scholar
    • 13. J.-M. Xu, Topological Structure and Analysis of Interconnection Networks, Springer Science and Business Media, Vol. 7 (2013). Google Scholar
    • 14. Y. Li and S. Peng, 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. A. Angjeli, E. Cheng and L. Lipták, Linearly many faults in dual-cube-like networks, Theor. Comput. Sci. 472 (2013) 1–8. Crossref, ISIGoogle Scholar
    • 16. A. K. Somani and O. Peleg, On diagnosability of large fault sets in regular topology-based computer systems, IEEE Trans. Comput. 45(8) (1996) 892–903. Crossref, ISIGoogle Scholar
    • 17. X. Yang and Y. Tang, A (4n-9)/3 diagnosis algorithm on n-dimensional cube network, Inf. Sci. 177 (2007) 1771–1781. Crossref, ISIGoogle Scholar
    • 18. P. K. Jha, 1-Perfect codes over dual-cubes vis-à-vis Hamming codes over hypercubse, IEEE Trans. Inform. Theory 61(8) (2015) 4259–4268. Crossref, ISIGoogle Scholar
    • 19. E. Cheng, K. Qiu and Z. Shen, A strong connectivity property of the generalized exchanged hypercube, Discrete Appl. Math. 216 (2017) 529–536. Crossref, ISIGoogle Scholar
    • 20. E. Cheng, K. Qiu and Z. Shen, Structural properties of generalized exchanged hypercubes, Emergent Comput. 24 (2017) 215–232. CrossrefGoogle Scholar
    • 21. M. Lv, S. Zhou, G. Chen, L. Chen, J. Liu and C. C. Chang, On reliability of multiprocessor system based on star graph, IEEE Trans. Reliab. 64 (2019) 547–555. Google Scholar
    • 22. X. Li, X. Jia, J. Fan and C.-K. Lin, Reliability analysis of data center networks based on precise and imprecise diagnosis strategies, Theoret. Comput. Sci. 809 (2020) 189–203. Crossref, ISIGoogle Scholar