An Optimal Routing Algorithm for Horizontal Moving Signals in OCN for Massively Parallel Systems with Faulty Node/Link
American Journal of Networks and Communications
Volume 6, Issue 2, April 2017, Pages: 35-46
Received: Mar. 9, 2017;
Accepted: Mar. 21, 2017;
Published: Apr. 7, 2017
Views 2406 Downloads 87
Sanjukta Mohanty, Department of Computer Application, North Orissa University, Sriram Chandra Vihar, Baripada, Odisha, India
Prafulla Kumar Behera, Department of Computer Science and Applications, Utkal University, Vani Vihar, Bhubaneswar, Odisha, India
An Octagon-Cell Interconnected Network (OCN) has many attractive features. To represent OCN an undirected graph G = (V, E) is used, in which V is the set of nodes in the graph and E is the set of edges in the graph. Already the optimal routing algorithm had been presented with its features in our past research work. This research paper presents the optimal routing algorithm for horizontal moving signals in OCN with a faulty node/link along the optimal path. OCN is expandable. Also the algorithm tells that, even the OCN is expanded; there is no effect to find the optimal path in presence of faulty nodes. OCN can be utilized in massively parallel computing. In a massively parallel system a large number of processors are used to perform a set of coordinated computation simultaneously. So OCN is assumed a type of integrated circuit with an array of hundreds or thousands of central processing units (CPUs) and random-access memory banks.
Prafulla Kumar Behera,
An Optimal Routing Algorithm for Horizontal Moving Signals in OCN for Massively Parallel Systems with Faulty Node/Link, American Journal of Networks and Communications.
Vol. 6, No. 2,
2017, pp. 35-46.
S. Mohanty and P. K. Behera. “Fault Tolerant Routing Algorithm in Octagon-Cell Interconnected Network for Horizontal Moving Messages”. International Journal of Computer Networks & Communications. Vol. 9, No. 1, January 2017, pp. 23-38.
S. Mohanty and P. K. Behera. “Optimal Routing Algorithm in a Octagon-Cell Network”. International Journal of Advanced Research in Computer Science. Vol. 2, No. 5, September-October 2011, pp. 625-637.
A. Sharieh, M. Qatawneh, W. Almobaideen and A. Sleit. “Hex-Cell: Modeling, Topological Properties and Routing Algorithm”. European Journal of Scientific Research, Vol. 22, No. 2, April 2008, pp. 457-468.
N. G. Kini, M. S. Kumar and Mruthyunjaya H.S. “An Optimal Data Routing Scheme for Mesh Embedded Hypercube Interconnection network with Multiple Faulty Nodes”. International Journal of Computer Science and Engineering. 3:1, January 2009, pp. 26-30.
A. Louri and H. Sung, “An Optical Multi-Mesh Hypercube: A Scalable Optical interconnection Network for Massively Parallel Computing”. Journal of Lightwave Technology. Vol. 12, No. 4, April 1994, pp. 704-716.
T. C. Lee and J. P.Hayes. “A Fault-Tolerant Communication Scheme for Hypercube Computers”. IEEE Transactions on Computers. Vol. 41, No. 10, October 1992, pp. 1242-1256.
S. Sharma and P. K. Bansal. “A New Fault Tolerant Multistage Interconnection Networks”. IEEE TENCON’ 02, Vol. 1, October 2002, pp. 347-350.
S.-C. Wang and S.-Y. Kuo. “Fault Tolerance in Hyperbus and Hypercube Multiprocessors Using Partitioning Scheme”. IEEE International Conference on Parallel and Distributed Systems. December 1994, pp. 340-347.
D. Nassimi and S. Sahni. “An Optimal Routing Algorithm for Mesh Connected Parallel Computers”. Journal of the ACM, Vol.27, January 1980, pp. 6-29.
J. P. Shen. “Fault Tolerance Analysis of Several Interconnection Networks”. In Proceedings of International Conference on Parallel Processing. 1982, pp. 102-112.
J. Bruck, R. Cypher and D. Soroker. “Tolerating Faults in Hypercubes Using Subcube Partitioning”. IEEE Trasactions on Computers. Vol. 41, No. 5, May 1992, pp. 599-605.
K. V. Arya and R. K. Ghosh. “Designing a New Class of Fault Tolerant Multistage Interconneconnection Networks”. Journal of Interconneconnection Network. Vol. 6, No. 4, December 2005, pp. 361-382.
K.-H. Chen and G.-M. Chiu. “Fault-Tolerant Routing Algorithm for Meshes without Using Virtual Channels”. Journal of Information Science and Engineering. 1998, Vol. 14, pp. 765-783.
J. Chen, I. A. Kanj and G. Wang. “Hypercube Network Fault Tolerance: A Probabilistic Approach”. In Proceedings of the IEEE International Conference on Parallel Processing. August 2002.
M. J. Serrano and B. Parhami. “Optimal Architectures and Algorithms for Mesh-Connected Parallel Computers with Separable Row/Column Buses”. IEEE Trasactions on Parallel and Distributed Systems. Vol. 4, No. 10, October 1993, pp. 1073-1080.
M. Qatawneh, B. Hamed, W. AlMobaideen, A. Sleit, A. Qudat, W. Qutechat and R. Al-Soub. “FTRH: Fault Tolerance Routing Algorithm for Hex-Cell Networks”. International Journal of Computer Science and Network Security. Vol. 9, No. 12, December 2009, pp. 268-274.
K. Day, S. Harous and A. Al-Ayyoub. “A Fault Tolerant Routing Scheme for Hypercubes”. Telecommunication Systems. Vol. 13, No. 1, May 2000, pp. 29-44.
C. Decayeux and D. Seme. “3D Hexagonal Network: Modeling, Topological Properties, Addressing Scheme and Optimal Routing Algorithm”. IEEE Trasactions on parallel and Distributed Systems. Vol. 16, No. 9, August 2005, pp. 875-884.
Q. Mohammad. “Adaptive Fault Tolerant Routing Algorithm for Tree-Hypercube Multicomputer”. Journal of Computer Science. Vol. 2, No. 2, February 2006, pp. 124-126.
S. Chalasani and R. V. Boppana. “Fault-Tolerant Wormhole Routing in Tori”. International Conference on Supercomputing. July 1994, pp. 146-155.
M. A. Omari and M. Mahafzah. “Fault-Tolerant Routing in hypercubes using masked interval Routing Scheme”. In Proceedings of the (1999) ACM symposium on Applied Computing. February-March 1999, pp. 481-485.
J. Zhou and F. C. M. Lau. “Multi-Phase Minimal Fault-Tolerant Wormwhole Routing in Meshes”. Parallel Computing. Vol. 30, No. 3, March 2004, pp. 423-442.
J.-H. Youn, B. Bose and S. Park. “Fault-Tolerant Routing Algorithm in Meshes with solid faults”. Journal of Supercomputing. 37, 2006, pp. 161-177.
F. Cristian, B. Dancey and J. Dehn. “Fault-Tolerance in Air Traffic Control Systems”. Trasaction on Computer Systems (TOCS), Vol. 14, No. 3, August 1996, pp. 256-286.
D. Wang. “A Low Cost Fault-Tolerant Structure for Hypercube”. Journal of Supercomputing. Vol. 20, No. 3, November 2001, pp. 203-216.
D. Gordon, I. Koren and G. M. Silberman. “Reconstructing Hexagonal Arrays of Processors in the Presence of Faults”. Journal of VLSI and Computer Systems. Vol. 2, 1987, pp. 23-35.
M. Rezazad and H. S. Azad. “A Routing Algorithm for Star Interconnection Network in the Presence of Faults”. The CSI Journal on Computer Science and Engineering. Vol. 1, No. 4(b), Winter 2003, pp. 11-18.
S. Mohanty and P. K. Behera. “Comparison of Octagon-Cell Network with other Interconnected Network Topologies and its Applications”. International Journal of Computer Engineering and Applications. Vol. 7, No. 2, August 2014, pp. 201-211.