A new routing mechanism for networks with irregular topology

ABSTRACT

Selecting a Pseudo-Hamiltonian cycle in any irregular network and applying a restricted packet injection mechanism to avoid the exhaustion of the storage resources, a new fully adaptive routing algorithm has been developed and tested. Our new routing mechanism outperforms the most relevant routing proposals for networks with irregular topology. In all the tested cases a significant improvement has been obtained. The most spectacular gains were obtained for big networks. For a 512-node network, uniform traffic, and virtual cut-through flow control, our mechanism can outperform, in some cases, the classic up*/down* algorithm by almost a factor of 2.

REFERENCES

• 1: Nanette J. Boden , Danny Cohen , Robert E. Felderman , Alan E. Kulawik , Charles L. Seitz , Jakov N. Seizovic , Wen-King Su, Myrinet: A Gigabit-per-Second Local Area Network, IEEE Micro, v.15 n.1, p.29-36, February 1995 [doi>10.1109/40.342015 ]
• 2: Ludmila Cherkasova , Vadim Kotov , Tomas Rokicki, Fibre Channel Fabrics: Evaluation and Design, Proceedings of the 29th Hawaii International Conference on System Sciences (HICSS'96) Volume 1: Software Technology and Architecture, p.53, January 03-06, 1996
• 3: José Duato, A Necessary and Sufficient Condition for Deadlock-Free Routing in Cut-Through and Store-and-Forward Networks, IEEE Transactions on Parallel and Distributed Systems, v.7 n.8, p.841-854, August 1996 [doi>10.1109/71.532115 ]
• 4: P. Kermani and L. Kleinrock, "Virtual Cut-Through: a new computer communication switching technique", Computer Networks 3, pp. 267-286, 1979.
• 5: Smaragda Konstantinidou , Lawrence Snyder, The Chaos Router, IEEE Transactions on Computers, v.43 n.12, p.1386-1397, December 1994 [doi>10.1109/12.338098 ]
• 6: V. Puente , R. Beivide , J. A. Gregorio , J. M. Prellezo , J. Duato , C. Izu, Adaptive Bubble Router: A Design to Improve Performance in Torus Networks, Proceedings of the 1999 International Conference on Parallel Processing, p.58, September 21-24, 1999
• 7: Wenjian Qiao , Lionel M. Ni , Tomas Rokicki, Adaptive-Trail Routing and Performance Evaluation in Irregular Networks Using Cut-Through Switches, IEEE Transactions on Parallel and Distributed Systems, v.10 n.11, p.1138-1158, November 1999 [doi>10.1109/71.809573 ]
• 8: M. D. Schroeder et al., "Autonet: A high-speed, self-configuring local area network using point-to-point links," 'Technical Report SRC research report 59, DEC, April 1990.
• 9: Federico Silla , Manuel P. Malumbres , Antonio Robles , Pedro López , José Duato, Efficient Adaptive Routing in Networks of Workstations with Irregular Topology, Proceedings of the First International Workshop on Communication and Architectural Support for Network-Based Parallel Computing, p.46-60, February 01-02, 1997

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network topology

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Packet-switching networks

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Routing and layout

General Terms:
Algorithms, Design, Performance

Keywords:
Bubble method, irregular networks, routers, routing algorithm, virtual channels