Research Article | OPEN ACCESS
Fault Tolerance in Interconnection Network-a Survey
1Laxminath Tripathy, 2Devashree Tripathy and 3C.R. Tripathy
1Department of CSE, Orissa Engineering College Bhubaneswar, Odisha, India
2Central Electronics Engineering Research Institute (CEERI) Pilani, India
3Sambalpur University, Sambalpur, Odisha, India
Research Journal of Applied Sciences, Engineering and Technology 2015 2:198-214
Received: April 28, 2015 | Accepted: May 22, 2015 | Published: September 15, 2015
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
- 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 -
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
- 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.
- Bay, P., 1995. Deterministic online routing on area-universal networks. J. Assoc. Comput. Mach., 42(3): 614-640.
CrossRef
- 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
- 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.
- 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
-
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
-
Feng, T.Y., 1981. A survey of interconnection networks. Computer, 14: 12-17.
CrossRef
-
Fu, J.S., 2003. Fault-tolerant cycle embedding in the hypercube. Parallel Comput., 29: 821-832.
CrossRef
-
Harary, F. and J.P. Hayes, 1993. Edge fault tolerance in graphs. Networks, 23: 135-142.
CrossRef
- Huang, C.F. and W.T. Chen, 1987. Fault-tolerant single-stage interconnectiohl networks. IEEE T. Comput., C-36(5): 637-640.
CrossRef
-
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
- 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
- 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
-
Kruskal, C.P. and M. Snir, 1983. Performance of multi stage interconnection networks for multi processors. IEEE T. Comput., c-32(12): 1091-1098.
- 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
- Leighton, F.T., 1992. Introduction to Parallel Algorithms and Architecture: Arrays. Trees, Hyper Cubes, Morgan Kaufman, CA.
-
Leiserson, C.E., 1985. Fat-trees: Universal networks hardware efficient supercomputing. IEEE T. Comput., 34(10): 892-901.
CrossRef
- Leung, Y.W., 1993. Online fault identification in multistage interconnection networks. Parallel Comput., 19: 693-702.
CrossRef
-
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.
- 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
- Padmanabhan, K. and D.H. Lawrie, 1983. A class of redundant path multistage interconnection networks. IEEE T. Comput., 32(12): 1099-1108.
CrossRef
-
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
-
Pradhan, D.K., 1982. On a class fault-tolerant multiprocessor network architectures. Proceeding of 3rd International Conference on Distributed Computing System, pp: 302-311.
- Rowley, R.A. and B. Bose, 1993. Fault-tolerant ring embedding in de Bruijn networks. IEEE T. Comput., 42(12): 1480-1486.
CrossRef
-
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
- 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
- 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
- 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
- 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
-
Shen, J.P. and J.P. Hayes, 1984. Fault-tolerance of dynamic-full-access interconnection networks. IEEE T. Comput., C-33: 241-248.
CrossRef
-
Skillicorn, D.B., 1988. A new class of fault-tolerant static interconnection networks. IEEE T. Comput., 31(11): 1468-1470.
CrossRef
- Street, A.P. and W.D. Wallis, 1977. Combinatorial Theory: An Introduction. Charles Babbage Research Centre, Winnipeg, Canada.
-
Theiss, I. and O. Lysne, 2006. FRoots: A fault tolerant and topology-flexible routing technique. IEEE T. Parall. Distr., 17(10).
- Tripathy, C.R. and N. Adhikari, 2011. A new multicomputer interconnection topology for massively parallel systems. Int. J. Distrib. Parallel Syst. (IJDPS), 2(4).
- 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
-
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
- Wang, D.J., 2001. Embedding Hamiltonian cycles into folded hyper cubes with link faults. J. Parall. Distr. Com., 61(4): 545-564.
CrossRef
-
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.
|
|
![](http://www.maxwellsci.com/images/RJASET-maxw.jpg) |
ISSN (Online): 2040-7467
ISSN (Print): 2040-7459 |
![Submit Manuscript](../images/sub.jpg) |
Information |
|
|
|
Sales & Services |
|
|
|