Routing in wormhole networks

As software overheads decrease and processor speeds increase relative to network speeds, the performance of multiprocessor interconnection networks will become increasingly important. This motivates design of efficient switching and routing schemes. Wormhole switching is an efficient switching technique wherein messages are pipelined through the network. Networks employing wormhole switching (termed "wormhole networks") are currently very popular as they yield low network latency and have minimal buffer requirements. This thesis is primarily concerned with performance and reliability aspects of wormhole networks. The main goal of this thesis is to identify how routing can be done effectively in these networks. Two concepts that have been proposed for performance improvements in wormhole networks are "Virtual Channel Flow Control" (VCFC) and "adaptive routing". In the VCFC concept multiple virtual channels (logical channels) share the same physical channel and can be employed as "lanes" with complete freedomin routing choice among them. Many new adaptive routing schemes have also been proposed in recent times which allow the next hop taken by a message to be determined "on the fly" based on local conditions at each router. These adaptive routing schemes have been shown to improve performance for certain traffic patterns and at the same time perform badly for other patterns. This thesis begins by investigating the question of whether adaptive routing can be made to perform uniformly well for all traffic patterns by proper combination with VCFC. It is shown that although both these techniques are not entirely satisfactory in isolation, a combination of both can provide substantial benefit. Even if adaptive routing techniques can be made to provide good improvements in performance, they are limited by the fact that routing is based only on local conditions at each router. This thesis next investigates the extent to which the local nature of decisions affect routing performance and explores the scope for further improvement. A practical source-directed routing method which uses application-specific knowledge is shown to be a potential approach to achieve these improvements. Finally, this thesis develops a general and cost-efficient fault tolerance approach based on reconfiguration of virtual channels around fault regions. The proposed approach is shown to be capable of tolerating a large set of faults and at the same time providing good performance