Abstract

Interconnection networks are used to provide communication between processors and memory modules in a parallel computing environment. In the past years, various interconnection networks have been proposed by many researchers. An interconnection network may suffer from mainly two types of faults: link faults and/or switch fault. Many fault tolerant techniques have also been proposed in the literature. This study makes an extensive survey of various methods of fault tolerance for interconnection networks those are used in large scale parallel processing.

Keywords:

DFA property, dynamic fault-tolerance, fault model, interconnection network, MIN, static fault tolerance,

References

1. Adams, G.B. III and H.J. Siegel, 1982. The extra stage cube: A fault-tolerant interconnection network for supercomputer systems. IEEE T. Comput., C-31: 443-454.
   CrossRef    
2. Adams III, G.B., D.P. Agrawal and H.J. Siegal, 1987. A survey and comparision of fault-tolerant multistage interconnection networks. Computer, 20: 14-27.
   CrossRef    
3. Bansal, P.K., R.C. Joshi and K. Singh, 1994. On a fault-tolerant multi-stage interconnection network. Int. J. Electron. Electr. Eng., 20(4): 335-345.
   
4. Bay, P., 1995. Deterministic online routing on area-universal networks. J. Assoc. Comput. Mach., 42(3): 614-640.
   CrossRef    
5. Chen, C.W. and C.P. Chung, 2005. Designing a disjoint path interconnection network with collision solving and fault tolerance. J. Supercomput., 34(1): 63-80.
   CrossRef    
6. Cheng, S.Y. and J.H. Chuang, 1994. Varietal hypercube-a new interconnection network topology for large scale multicomputer. Proceedings of International Conference on Parallel and Distributed System, pp: 703-708.
   
7. Choi, S.B. and A.K. Somani, 1996. Design and performance analysis of load-distributing fault-tolerant network. IEEE T. Comput., 45(5): 540-551.
   CrossRef    
8. Dash, R.K., N.K. Barpanda, P.K. Tripathy and C.R. Tripathy, 2012. Network reliability optimization problem of interconnection network under node-edge failure model. Appl. Soft Comput., 8: 2322-2328.
   CrossRef    
9. Feng, T.Y., 1981. A survey of interconnection networks. Computer, 14: 12-17.
   CrossRef    
10. Fu, J.S., 2003. Fault-tolerant cycle embedding in the hypercube. Parallel Comput., 29: 821-832.
    CrossRef    
11. Harary, F. and J.P. Hayes, 1993. Edge fault tolerance in graphs. Networks, 23: 135-142.
    CrossRef    
12. Huang, C.F. and W.T. Chen, 1987. Fault-tolerant single-stage interconnectiohl networks. IEEE T. Comput., C-36(5): 637-640.
    CrossRef    
13. Kamiura, N., T. Kodera and N. Matsui, 2000. Fault tolerant multistage interconnection networks with widely dispersed paths. Proceedings of the Ninth Asian Test Symposium, pp: 423-428.
    CrossRef    
14. Kamiura, N., T. Kodera and N. Matsui, 2002. A fault tolerant multistage interconnection network with partly duplicated switches. J. Syst. Architect., 47: 901-916.
    CrossRef    
15. Kim, J.H., L. Ziqiang and A. Chien, 1997. Compressionless routing: A framework for adaptive and fault-tolerant routing. IEEE T. Parall. Distr., 8(30): 229-243.
    CrossRef    
16. Kruskal, C.P. and M. Snir, 1983. Performance of multi stage interconnection networks for multi processors. IEEE T. Comput., c-32(12): 1091-1098.
    
17. Latifi, S., S.Q. Zheng and N. Bagherzadeh, 1992. Optimal ring embedding in hypercube with faulty links. Proceeding of the IEEE Symposium on Fault-tolerant Computing, pp: 178-184.
    CrossRef    
18. Leighton, F.T., 1992. Introduction to Parallel Algorithms and Architecture: Arrays. Trees, Hyper Cubes, Morgan Kaufman, CA.
    
19. Leiserson, C.E., 1985. Fat-trees: Universal networks hardware efficient supercomputing. IEEE T. Comput., 34(10): 892-901.
    CrossRef    
20. Leung, Y.W., 1993. Online fault identification in multistage interconnection networks. Parallel Comput., 19: 693-702.
    CrossRef    
21. Lysne, O. and T. Skeie, 2001. Load balancing of irregular system area networks through multiple roots. Proceeding of 2nd International Conference on Communications in Computing, 26: 62-76.
    
22. Nitin Garhwal, S. and N. Srivastava, 2011. Designing a fault-tolerant fully-chained combining switches multi-stage interconnection network with disjoint paths. J. Supercomput., 55: 400-431.
    CrossRef    
23. Padmanabhan, K. and D.H. Lawrie, 1983. A class of redundant path multistage interconnection networks. IEEE T. Comput., 32(12): 1099-1108.
    CrossRef    
24. Petrini, F. and M. Vanneschi, 1997. K-ary N-trees: High performance networks for massively parallel architectures. Proceeding of 11th International Symposium Parallel Processing (IPPS ’97), pp: 87.
    CrossRef    
25. Pradhan, D.K., 1982. On a class fault-tolerant multiprocessor network architectures. Proceeding of 3rd International Conference on Distributed Computing System, pp: 302-311.
    
26. Rowley, R.A. and B. Bose, 1993. Fault-tolerant ring embedding in de Bruijn networks. IEEE T. Comput., 42(12): 1480-1486.
    CrossRef    
27. Sancho, J.C. and A. Robles, 2000. Improving the up*/down* routing scheme for networks of workstations. Proceeding of the 6th International Euro-Par Conference, pp: 882-889.
    CrossRef    
28. Sem-Jacobsen, F.O., T. Skeie, O. Lysne,O. Tørudbakken, E. Rongved and B. Johnsen, 2005. Siamese-twin: A dynamically fault tolerant fat tree. Proceeding of the 19th IEEE International Parallel and Distributed Processing Symposium.
    CrossRef    
29. Sem-Jacobsen, F.O., O. Lysne and T. Skeie, 2006. Combining source routing and dynamic fault tolerance. Proceedings of 18th International Symposium on Computer Architecture and High Performance Computing (SBACPAD), pp: 151-158.
    CrossRef    
30. Sem-Jacobsen, F.O., T. Skeie, O. Lysne and J. Duato, 2011. Dynamic fault tolerance in fat trees. IEEE T. Comput., 60(40): 508-524.
    CrossRef    
31. Sengupta, J. and P.K. Bansal, 1998. Fault-tolerant routing in irregular MINs. Proceeding of the IEEE Region 10 International Conference on Global Connectivity in Energy, Computer, Communication and Control, 2: 638-641.
    CrossRef    
32. Shen, J.P. and J.P. Hayes, 1984. Fault-tolerance of dynamic-full-access interconnection networks. IEEE T. Comput., C-33: 241-248.
    CrossRef    
33. Skillicorn, D.B., 1988. A new class of fault-tolerant static interconnection networks. IEEE T. Comput., 31(11): 1468-1470.
    CrossRef    
34. Street, A.P. and W.D. Wallis, 1977. Combinatorial Theory: An Introduction. Charles Babbage Research Centre, Winnipeg, Canada.
    
35. Theiss, I. and O. Lysne, 2006. FRoots: A fault tolerant and topology-flexible routing technique. IEEE T. Parall. Distr., 17(10).
    
36. Tripathy, C.R. and N. Adhikari, 2011. A new multicomputer interconnection topology for massively parallel systems. Int. J. Distrib. Parallel Syst. (IJDPS), 2(4).
    
37. Tseng, Y.C., S.H. Chang and J.P. Sheu, 1997. Fault-tolerant ring embedding in a star graph with both link and node failures. IEEE T. Parall. Distr., 8(12): 1185-1195.
    CrossRef    
38. Tzeng, N.F., P.C. Yew and C.Q. Zhu, 1985. A fault tolerant scheme for multistage interconnection network. Proceeding of International Conference on Parallel Processing, pp: 368-375.
    CrossRef    
39. Wang, D.J., 2001. Embedding Hamiltonian cycles into folded hyper cubes with link faults. J. Parall. Distr. Com., 61(4): 545-564.
    CrossRef    
40. Wu, J. and D. Wang, 2002. Fault-tolerant and deadlock-free routing in 2-D meshes using rectilinear-monotone polygonal fault blocks. Proceeding of International Conference on Parallel Processing, pp: 247-254.
    

Competing interests

The authors have no competing interests.

Open Access Policy

This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.

Copyright

The authors have no competing interests.