Modeling, analysis and evaluation of adaptive routing strategies
A. Lagman · 1995
The use of adaptive routing in interconnection networks is one approach to improving the performance of large scale multicomputer systems. In adaptive routing, network state information can be used in selecting the path taken by a message from its source to its destination. This type of routing is flexible, and can take advantage of network features in order to reduce communication costs. However, adaptive routing is complex, and at present not enough is known about the relationship between its design parameters and system performance. The research described in this dissertation is a study of adaptive routing in k-ary n-cube networks. It has two objectives: (1) to assess the potential improvement in network performance that can be achieved by using adaptive routing instead of the currently popular dimension ordered routing schemes, and (2) to identify the design issues that affect performance, and to measure and characterize their effect. The performance study was conducted analytically through the derivation of queueing models for idealized adaptive routing, in conjunction with extensive simulation experiments. The network parameters investigated include buffer organization, message selection policy, path selection policy, and deadlock avoidance technique. Networks with various choices of these parameters were proposed, and their performances were compared to each other as well as to that of a network with dimension ordered routing.