wormhole routing;virtual channels;time-dependent selection functions;deadlock-free adaptive routing algorithms;store-and-forward routing;binary n-cube;message destination;channel multiplexing;

In previous papers by the author (1991, 1992), a new theory for the design of deadlock-free adaptive routing algorithms for wormhole and store-and-forward routing as well as two design methodologies have been proposed. Also, a new adaptive routing algorithm, obtained from the application of the former theory to the binary n-cube, has been evaluated using both, a uniform and an exponential distribution for message destination. The results are good, especially for large networks and a uniform distribution for message destination. When locality is exploited, the results are comparatively worse, mainly due to the reduction in channel bandwidth produced by channel multiplexing. In this paper, the author analyses the advantages and disadvantages produced by the use of virtual channels, proposing a new approach to maximize their efficiency. This approach uses time-dependent selection functions, associating a threshold to some virtual channels. Those channels cannot be selected by a message unless it is waiting for longer than the corresponding threshold. The evaluation of the new selection function for the binary n-cube shows an important improvement, especially when locality is exploited