Performance Evaluation of a New Routing Strategy for Irregular Networks with Source Routing

Networks of workstations (NOWs) are becoming increas-ingly popular as a cost-effective alternative to parallel com-puters. Typically, these networks connect processors using irregular topologies, providing the wiring flexibility, scala-bility, and incremental expansion capability required in this environment. In some of these networks, messages are deliv-ered using the up*/down * routing algorithm [9]. However, the up*/down * routing scheme is often non-minimal. Also, some of these networks use source routing [1]. With this technique, the entire path to destination is generated at the source host before the message is sent. In this paper we develop a new mechanism in order to im-prove the performance of irregular networks with source routing, increasing overall throughput. With this mecha-nism, messages always use minimal paths. To avoid possible deadlocks, when necessary, routes between a pair of hosts are divided into sub-routes, and a special kind of virtual cut-through is performed at some intermediate hosts. We evaluate the new mechanism by simulation using parame-ters taken from the Myrinet network. We show that the current routing schemes used in Myrinet can be improved by modifying only the routing software without increasing its overhead siguificantly and, most importantly, without modifying the network hardware. The benefits of using the new routing scheme are noticeable for networks with 16 or more switches, and increase with network size. For 32 and 64-switch networks, throughput is increased on average by a factor ranging from 1.3 to 3.3