Submit Manuscript

Journal of Applied Sciences

Year: 2004 | Volume: 4 | Issue: 4 | Page No.: 568-574
Facebook Twitter Digg Reddit Linkedin StumbleUpon E-mail
Research Article

Adaptive Wormhole Routing in Mesh-Hypercube Network

Bassam Al-Mahadeen and Mahmoud Omari

ABSTRACT

The aim of this research was the development of wormhole routing algorithms for the Mesh Hypercube (MH) network. MH has been introduced as a new interconnection network for parallel systems. The basic structure for this network is a combination of both mesh and hypercube networks. It combines the attractive features of both the hypercube and the mesh, while at the same time overcoming their disadvantages. Attractive features of the MH are high connectivity, simple message routing, fault-tolerance, scalability, constant node degree and small diameter and average distance. This research introduced two wormhole routing algorithms for unicast and multicast communication. These algorithms are based on labeling the nodes in the network to prevent deadlock and livelock problems. Messages are allowed to travel in ascending order or descending order of labels only to prevent any cyclic dependencies between nodes. The algorithms are shown to be deadlock-free and livelock-free.
PDF References Citation

Search

REFERENCES

  1. Omari, M., 2003. Mesh-hypercube: A network topology for parallel systems. Nat. Applied Sci. Ser., 18: 37-60.
  2. Omari, M. and H. Abu-Salem, 2001. Routing strategies for binary tree-hypercube network. Al-Manarah Res., 7: 27-48.
  3. Raghavendra, C.S., A. Avizienis and M.D. Ercegovac, 1984. Fault tolerance in binary tree architectures. IEEE Trans. Comput., 33: 568-572.
  4. Saad, Y. and M.H. Schultz, 1987. Data communication in hyperubes. J. Parallel Distributed Comput., 9: 115-153.
  5. Tsai, Y.J. and P. McKinley, 1996. A broadcast algorithm for all-port wormhole-routed torus networks. IEEE Trans. Parallel Distributed Syst., 7: 876-885.
    Direct Link
  6. Stout, Q.F. and B. Wagar, 1990. Intensive hypercube communication. J. Parallel Distributed Comput., 10: 167-181.
  7. Schwiebert, L. and D.N. Jayasimha, 1995. Optimal fully adaptive minimal wormhole routing for meshes. J. Parallel Distributed Comput., 27: 56-70.
  8. Bhuyan, L.N. and D.P. Agrawal, 1984. Generalized hypercube and hyperbus structures for a computer network. IEEE Trans. Comput., 32: 323-333.
  9. Lan, Y., 1995. An adaptive fault-tolerant routing algorithm for hypercube multicomputers. IEEE Trans. Parallel Distribution Syst., 6: 1147-1152.
    Direct Link
  10. Padmanbhan, K. and D. Lawrie, 1983. A class of redundant path multistage interconnection networks. IEEE Trans. Comput., 32: 1099-1108.
    Direct Link
  11. Yeung, K.H. and T.S. Yu, 1997. Selective broadcast data distribution systems. IEEE Trans. Comput., 46: 100-104.
    Direct Link
  12. Gaughan, P., B. Dao, S. Yalamanchili and D. Schimmel, 1996. Distributed, deadlock-free routing in faulty, pipelined, directed interconnection networks. IEEE Trans. Parallel Distribution Syst., 45: 651-665.
  13. Fleury, E. and P. Fraigniaud, 1998. Strategies for path-based multicasting in wormhole-routed meshes. J. Parallel Distribution Comput., 60: 26-62.
    Direct Link
  14. Bokhari, S., 1990. Communication overhead on the intel ipsc-860 hypercube. Icase Interim Report 10, ICASE. http://openlibrary.org/b/OL16138269M/Communication_overhead_on_the_Intel_iPSC-860_hypercube.
  15. Lin, X., A.H. Esfahanian, P.K. Mckinely and A. Burago, 1993. Adaptive wormhole routing in hypercube multicomputers. Proceedings of the 5th IEEE Symposium on Parallel and Distributed Computing, Dec. 1-4, Dallas, Texas, pp: 72-79.
    CrossRef
  16. Mohapatra, P., 1998. Wormhole routing techniques for directly connected multicomputer systems. ACM Comput. Surveys, 30: 374-410.
    Direct Link
  17. Ababneh, I. and A.A. Obeid, 2001. Wormhole-Routed Multicast in 3D Mesh Architecture. Al-Manara J. Al al-Bayt University, UK.
  18. Mahadeen, B.A. and M. Omari, 2003. Fault-free point-to-point routing in mesh-hypercube networks. Proceedings of International Conference on Information Technology and Natural Sciences, (ICITNS'03), Al-Zaytoonah University, Amman, Jordan, pp: 19-21.
  19. Omari, M., 2000. Routing in quad tree-hypercubes. Proceedings of the 15th ACM Symposium on Applied Computing, (SAC'00), Como, Italy, pp: 677-681.

Search

Related Articles

Leave a Comment

Your email address will not be published. Required fields are marked *