Hsing-Lung Chen and Han-Shing Yihng
Department of Electronic Engineering
National Taiwan Institute of Technology
43, keelung Road, Section 4
Taipei, Taiwan, R.O.C.
This paper presents a set of general routing rules for developing wormhole routing strategies that are deadlock-free and adaptive in hypercubes. Based on the set of routing rules, we can derive many different deadlock-free and adaptive routing strategies, which include prior adaptive routing strategies as special cases. The e-cube routing algorithm identifies only one shortest path between an arbitrary pair of nodes and fails to take advantage of the flexibility provided by hypercubes. Prior adaptive routing strategies have unbalanced characteristics in that either the numbers of shortest paths allowed between certain communication pairs are limited, or some links carry heavy traffic load. These unbalanced characteristics possibly make some links/nodes become congested earlier, leading to considerable performance degradation. Our routing strategies, if chosen properly, possess balanced load while offering good adaptivity. They are evaluated experimentally and compared with prior routing strategies under various traffic patterns. We show that our routing strategies often give rise to better performance than do prior routing strategies.
Keywords: adaptive routing, balance, deadlock, traffic patterns, wormhole routing
Received December 27, 1993; revised April 2, 1994.
Communicated by Shing-Tsaan Huang.