Fault tolerance designs of interconnection networks | Peer-to-Peer Networking and Applications Skip to main content
Springer Nature Link
Log in

Fault tolerance designs of interconnection networks

  • Published:
Peer-to-Peer Networking and Applications Aims and scope Submit manuscript

Abstract

Multiprocessor interconnection networks are mainly required to link a significant number of stable processor memory sets, every one of which is known as a processing vertex. Due to the cost-effectiveness, the design and utilization of multiprocessor interconnection networks have drawn attention lately. An interconnection network is extensively used in a parallel multiprocessor system to connect the processors and memory modules. In multiprocessor networks, vertices represent processors, and each processor of which is subject to complete failure. Fault tolerance is a process that ensures the working of a system to its total capacity, even if one or more of its components fail. In fault-tolerant design, backup components are used in interconnection networks to automatically take the place of the failed component, guaranteeing that the system’s working continues. This paper proposed the fault-tolerant design in the form of \(P_j^k\) and \(C_j^k\) graphs, where n processing components are linked, and i of these n components creating a chain of maximum size, are used to perform the task, they can tolerate the failure of components, maintaining steady operation. In particular, we present the fault-tolerant designs of pyramid, OTIS, biswapped, and mesh-derived networks.

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
¥17,985 /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 (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12
Fig. 13
Fig. 14
Fig. 15
Fig. 16
Fig. 17
Fig. 18
Fig. 19

Similar content being viewed by others

Data availibility

Data used to support the study already included in the manuscript.

References

  1. Hsu LH, Lin CK (2008) Graph theory and interconnection networks. CRC Press

    Book  MATH  Google Scholar 

  2. Park JH, Kim HC, Lim HS (2005) Fault-hamiltonicity of hypercube-like interconnection networks, In 19th IEEE International Parallel and Distributed Processing Symposium, p 10

  3. Park JH, Lim HS, Kim HC (2007) Panconnectivity and pancyclicity of hypercube-like interconnection networks with faulty elements. Theor Comput Sci 377:170–180

    Article  MathSciNet  MATH  Google Scholar 

  4. Bistouni F, Jahanshahi M (2015) Pars network: a multistage interconnection network with fault-tolerance capability. J Parallel Distrib Comput 75:168–183

    Article  Google Scholar 

  5. Fu JS (2008) Fault-free Hamiltonian cycles in twisted cubes with conditional link faults. Theor Comput Sci 407:318–329

    Article  MathSciNet  MATH  Google Scholar 

  6. Prakash A, Yadav DK (2019) Design and reliability analysis of fault-tolerant shuffle exchange gamma logical neighborhood interconnection network. J Supercomput 75:7934–7951

    Article  Google Scholar 

  7. Wang S, Yang Y (2012) Fault tolerance in bubble-sort graph networks. Theor Comput Sci 421:62–69

    Article  MathSciNet  MATH  Google Scholar 

  8. Ballesteros A, Barranco M, Proenza J, Almeida L, Pozo F, Palmer-Rodríguez P (2022) An infrastructure for enabling dynamic fault tolerance in highly-reliable adaptive distributed embedded systems based on switched ethernet. Sensors 22(18):7099

    Article  Google Scholar 

  9. Choudhary A, Kumar S, Gupta S, Gong M, Mahanti A (2021) FEHCA: A fault-tolerant energy-efficient hierarchical clustering algorithm for wireless sensor networks. Energies 14(13):3935

    Article  Google Scholar 

  10. Zhao Z, Wang T, Benbouzid M (2022) A fault-tolerant reconfiguration system based on pilot switch for grid-connected inverters. Microelectron Reliab 131:114511

    Article  Google Scholar 

  11. Park P, Ghadikolaei HS, Fischione C (2021) Proactive fault-tolerant wireless mesh networks for mission-critical control systems. J Netw Comput Appl 186:103082

    Article  Google Scholar 

  12. Sahu S, Silakari S (2022) Distributed multilevel k-coverage energy-efficient fault-tolerant scheduling for wireless sensor networks. Wireless Pers Commun 124:2893–2922

    Article  Google Scholar 

  13. Gallai T (1968) “Problem 4”, in: Theory of Graphs, Proc. Tihany (1966) (ed: P. Erdös & G. Katona), Academic Press, New York, 362

  14. Zamfirescu T (1972) A two-connected planar graph without concurrent longest paths. J Comb Theory B 13:116–121

    Article  MathSciNet  MATH  Google Scholar 

  15. Zamfirescu T (2001) Intersecting longest paths or cycles: a short survey. An Univ Craiova Ser Mat Inform 28:1–9

    MathSciNet  MATH  Google Scholar 

  16. Shabbir A (2014) Fault-tolerant designs in lattice networks on the Klein bottle. Electron J Graph Theory Appl 2:99–109

    Article  MathSciNet  MATH  Google Scholar 

  17. Shabbir A, Zamfirescu T (2016) Fault-tolerant designs in triangular lattice networks. Appl Anal 10:447–456

    MathSciNet  MATH  Google Scholar 

  18. Shabbir A, Zamfirescu CT, Zamfirescu TI (2013) Intersecting longest paths and longest cycles: A survey. Electron J Graph Theory Appl 1:56–76

    Article  MathSciNet  MATH  Google Scholar 

  19. Gao C, He X, Dong H, Liu H, Lyu G (2022) A survey on fault-tolerant consensus control of multi-agent systems: trends, methodologies and prospects. Int J Syst Sci 53(13):2800-2813

  20. Qu Z, Xu H, Zhao X, Tang H, Wang J, Li B (2022) A fault-tolerant sensor scheduling approach for target tracking in wireless sensor networks. Alexandria Eng J 61(12):13001–13010

    Article  Google Scholar 

  21. Salam R, Bhattacharya A (2022) Efficient greedy heuristic approach for fault-tolerant distributed controller placement in scalable SDN architecture. Cluster Comput 25:4543–4572

    Article  Google Scholar 

  22. Song Y, Zhao J, Sun J (2022) Design of a fault-tolerant system for a multi-motor drive with multiple inverter leg faults. J Power Electron 22:1848–1859

    Article  Google Scholar 

  23. Sun X, Fan J, Cheng B, Liu Z, Yu J (2021) Component conditional fault tolerance of hierarchical folded cubic networks. Theor Comput Sci 883:44–58

    Article  MathSciNet  MATH  Google Scholar 

  24. Nadeem F, Shabbir A, Zamfirescu T (2013) Planar lattice graphs with Gallai’s property. Graph Combinator 29:1523–1529

    Article  MathSciNet  MATH  Google Scholar 

  25. Shabbir A, Zamfirescu T (2016) Gallai’s property for graphs in lattices on the torus and the Möbius strip. Period Math Hung 72:1–11

  26. Jumani AD, Zamfirescu C, Zamfirescu T (2014) Lattice graphs with non-concurrent longest cycles. Rend Semin Mat U Pad 132:75–82

    Article  MathSciNet  MATH  Google Scholar 

  27. Leighton FT (2014) Introduction to parallel algorithms and architectures: Arrays trees hypercubes. Elsevier

    MATH  Google Scholar 

  28. Quinn MJ (1987) Designing efficient algorithms for parallel computers. McGraw-Hill

    MATH  Google Scholar 

  29. Levialdi S (1985) A Pyramid Project Using Integrated Technology, Integrated Technology for Parallel Image Processing, S. Levialdi, ed. New York: Academic Press

  30. Cao F, Du DZ, Hsu F, Teng SH (1999) Fault tolerance properties of pyramid networks. IEEE Trans Comput 48:88–93

    Article  MathSciNet  MATH  Google Scholar 

  31. Hoseinyfarahabady MR, Sarbazi-Azad H (2006) The grid-pyramid: A generalized pyramid network. J Supercomput 37:23–45

    Article  Google Scholar 

  32. Marsden GC, Marchand PJ, Harvey P, Esener SC (1993) Optical transpose interconnection system architectures. Opt Lett 18:1083-1085

  33. Sahni S, Wang CF (1997) BPC Permutations on the OTIS-mesh Optoelectronic Computer, In proceedings of the fourth international conference on massively parallel processing using optical interconnections, pp 130–135

  34. Osterloh A (2000) Sorting on the OTIS-Mesh. In: Proceedings 14th International Parallel and Distributed Processing Symposium, IPDPS, IEEE, pp 269–274

  35. Rajasekaran S, Sahni S (1998) Randomized routing, selection, and sorting on the OTIS-mesh. IEEE T Parall Distr 9:833–840

    Article  Google Scholar 

  36. Wang CF (1998) Algorithms for the OTIS optoelectronic computer, University of Florida

  37. Wang CF, Sahni S (2000) Image processing on the OTIS-mesh optoelectronic computer. IEEE T Parall Distr 11:97–109

    Article  Google Scholar 

  38. Xiao W, Chen W, He M, Wei W, Parhami B (2007) Biswapped networks and their topological properties. In: Eighth ACIS International Conference on Software Engineering, Artificial Intelligence, Networking, and Parallel/Distributed Computing, pp 193–198

  39. Imran M, Hayat S, Mailk MYH (2014) On topological indices of certain interconnection networks. Appl Math Comput 244:936–951

    MathSciNet  MATH  Google Scholar 

Download references

Funding

This research received no specific grant from any funding agency in the public, commercial, or not-for-profit sectors.

Author information

Authors and Affiliations

  1. Department of Mathematics, COMSATS University Islamabad, Lahore Campus, Lahore, Pakistan

    Muhammad Faisal Nadeem & Hafiz Muhammad Afzal Siddiqui

  2. Department of Mathematical Sciences, United Arab Emirates University, Al Ain, United Arab Emirates

    Muhammad Imran

  3. Department of Mathematics, Riphah Institute of Computing and Applied Sciences, Riphah International University, Lahore, Pakistan

    Muhammad Azeem

Authors
  1. Muhammad Faisal Nadeem
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Muhammad Imran
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Hafiz Muhammad Afzal Siddiqui
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Muhammad Azeem
    View author publications

    You can also search for this author in PubMed Google Scholar

Contributions

All authors have contributed equally to the finding the results and writing of this article. All authors read and approved the final version of the paper.

Corresponding author

Correspondence to Muhammad Faisal Nadeem.

Ethics declarations

Ethical approval

This article does not contain any studies with human participants or animals performed by any of the authors.

Informed consent

Informed consent was obtained from all individual participants included in the study.

Conflict of interest

The authors declare that they have no conflict of interest.

Additional information

Publisher’s Note

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

This article belongs to the Topical Collection: Special Issue on 2 - Track on Security and Privacy

Guest Editors: Rongxing Lu

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Nadeem, M.F., Imran, M., Afzal Siddiqui, H.M. et al. Fault tolerance designs of interconnection networks. Peer-to-Peer Netw. Appl. 16, 1125–1134 (2023). https://doi.org/10.1007/s12083-023-01462-4

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s12083-023-01462-4

Keywords

Search

Navigation