[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

A unified approach to reliability and edge fault tolerance of cube-based interconnection networks under three hypotheses

  • Published:
The Journal of Supercomputing Aims and scope Submit manuscript

Abstract

The topological structures of the interconnection networks of some parallel and distributed systems are designed as n-dimensional hypercube \(Q_n\) or n-dimensional folded hypercube \(FQ_n\) with \(N=2^n\) processors. For integers \(0\le k\le {n-1}\), let \(\mathcal {P}_1^k\), \(\mathcal {P}_2^k\) and \(\mathcal {P}_3^k\) be the property of having at least k neighbors for each processor, containing at least \(2^k\) processors and admitting average neighbors at least k, respectively. \(\mathcal {P}\)-conditional edge-connectivity of G, \(\lambda (\mathcal {P},G)\), is the minimum cardinality of faulty edge-cut, whose malfunction divides this network into several components, with each component satisfying the property of \(\mathcal {P}\). For each integer \(0\le k\le {n-1}\), and \(1\le i\le 3\), this paper offers a unified method to investigate the \(\mathcal {P}_i^k\)-conditional edge-connectivity of \(Q_n\) and \(FQ_n\). Exact value of \(\mathcal {P}_i^k\)-conditional edge-connectivity of \(Q_n\), \(\lambda (\mathcal {P}_i^k,Q_n)\), is \((n-k)2^k\), and that of \(\mathcal {P}_i^k\)-conditional edge-connectivity of \(FQ_n\), \(\lambda (\mathcal {P}_i^k,FQ_n)\), is \((n-k+1)2^k\). Our method generalizes the result of Guo and Guo in [The Journal of Supercomputing, 2014, 68:1235-1240] and the previous other results.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4

Similar content being viewed by others

References

  1. Archit JS (2002) Folded-crossed hypercube: a complete interconnection network. J Syst Archit 47:917–922

    Article  Google Scholar 

  2. Cai XP, Vumar E (2019) The super connectivity of folded crossed cubes. Inf Process Lett 142:52–56

    Article  MathSciNet  Google Scholar 

  3. Chang NW, Tsai CY, Hsieh SY (2014) On 3-extra connectivity and 3-extra edge connectivity of folded hypercubes. IEEE Trans Comput 63:1594–1600

    Article  MathSciNet  Google Scholar 

  4. Cheng E, Qiu K, Shen ZZ (2017) On the restricted connectivity of the arrangement graph. J Supercomput 73(8):3669–3682

    Article  Google Scholar 

  5. Chung FRK, Füredi Z, Graham RL, Seymour P (1998) On induced subgraphs of the cube. J Comb Theory 49(1):180–187

    Article  MathSciNet  Google Scholar 

  6. El-Amawy A, Latifi S (1991) Properties and performance of folded hypercubes. IEEE Trans Parallel Distrib Syst 2(1):31–42

    Article  Google Scholar 

  7. Esfahanian AH (1989) Generalized measure of fault tolerance with application to \(n\)-cube networks. IEEE Trans Comput 38(11):1586–1591

    Article  Google Scholar 

  8. Esmaeili T, Lak G, Rad AN (2012) 3D-FolH-NOC: a new structure for parallel processing and distributed systems. J Comput 4(6):163–168

    Google Scholar 

  9. Fàbrega J, Fiol MA (1996) On the extraconnectivity of graphs. Discret Math 155:49–57

    Article  MathSciNet  Google Scholar 

  10. Guo LT (2018) Reliability analysis of crossed cube networks on degree. J Comput Commun 6:129–134

    Article  Google Scholar 

  11. Guo LT, Guo XF (2014) Fault tolerance of hypercubes and folded hypercubes. J Supercomput 68:1235–1240

    Article  Google Scholar 

  12. Harary F (1983) Conditional connectivity. Networks 13(3):346–357

    Article  MathSciNet  Google Scholar 

  13. Harper LH (1964) Optimal assignments of numbers to vertices. J Soc Ind Appl Math 12(1):131–135

    Article  MathSciNet  Google Scholar 

  14. Hsieh SY, Huang HW, Lee CW (2016) \(\{2,3\}\)-Restricted connectivity of locally twisted cubes. Theor Comput Sci 615:78–90

    Article  MathSciNet  Google Scholar 

  15. Latifi S (1991) Simulation of PM21 network by folded hypercube. IEEE Proc E Comput Digit Tech 138(6):397–400

    Article  Google Scholar 

  16. Lee CW, Hsieh SY, Yang SS (2020) \(R_3\)-connectivity of folded hypercubes. Discret Appl Math 285:261–273

    Article  Google Scholar 

  17. Li XJ, Xu JM (2013) Edge-fault tolerance of hypercube-like networks. Inf Process Lett 113(19–21):760–763

    Article  MathSciNet  Google Scholar 

  18. Li H, Yang WH (2013) Bounding the size of the subgraph induced by \(m\) vertices and extra edge-connectivity of hypercubes. Discret Appl Math 161(16–17):2753–2757

    Article  MathSciNet  Google Scholar 

  19. Park JS, Davis NJ (2001) Modeling the folded hypercube ATM Switches. In: The proceedings of OPNETWORK, Washington DC

  20. Park PS, Davis NJ (2001) The folded hypercube ATM switches. In: International Conference on Networking 2094:370–379

  21. Rajasingh I, Arockiaraj M (2020) Linear wirelength of folded hypercubes. Math Comput Sci 5:101–111

    Article  MathSciNet  Google Scholar 

  22. Wei CC, Hsieh SY (2017) \(H\)-restricted connectivity of locally twisted cubes. Discret Appl Math 217(2):330–339

    Article  MathSciNet  Google Scholar 

  23. Yang WH, Lin HQ (2014) Reliability evaluation of BC networks in terms of extra vertex- and edge-connectivity. IEEE Trans Comput 63(10):2540–2548

    Article  MathSciNet  Google Scholar 

  24. Zhang MZ, Zhang LZ, Feng X (2016) Reliability measures in relation to the \(h\)-extra edge-connectivity of folded hypercubes. Theor Comput Sci 615:71–77

    Article  MathSciNet  Google Scholar 

  25. Zhu Q, Xu JM (2006) On restricted edge connectivity and extra edge connectivity of hypercubes and folded hypercubes. J Univ Sci Technol China 36:246–253

    MATH  Google Scholar 

Download references

Acknowledgements

This work was supported by Science and Technology Project of Xinjiang Uygur Autonomous Region (Grant No. 2020D01C069), National Natural Science Foundation of China (Grant No.1210011532 and No. 11771362), Doctoral Startup Foundation of Xinjiang University (Grant No.62031224736) and Tianchi Ph.D Program (No. tcbs201905). We would like to thank the referees for kind help and valuable suggestions.

Author information

Authors and Affiliations

  1. School of Mathematics and System Sciences, Xinjiang University, Urumqi, 830046, Xinjiang, China

    Mingzu Zhang & Hongxi Liu

  2. School of Informatics, Xiamen University, Xiamen, 361005, Fujian, China

    Wenshui Lin

Authors
  1. Mingzu Zhang
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Hongxi Liu
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Wenshui Lin
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Wenshui Lin.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Zhang, M., Liu, H. & Lin, W. A unified approach to reliability and edge fault tolerance of cube-based interconnection networks under three hypotheses. J Supercomput 78, 7936–7947 (2022). https://doi.org/10.1007/s11227-021-04185-6

Download citation

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11227-021-04185-6

Keywords

Search

Navigation