On the design of optimal adaptive routers for direct networks

Adaptive routing systems for direct networks can make use of the multiple paths that exist between pairs of nodes, and thus have the potential to deliver low latency communication. The performance of such systems, however, is dependent on the choice of the message buffering scheme as well as on the routing algorithm used. In this paper, we describe a general adaptive routing system for direct networks which can route the maximum number of messages out of a node at any time. We apply this design to the case of a two-dimensional k-ary n-cube, for which we derive an approximate analytic queueing model. This queueing model is validated through simulation experiments, and the performance potential of the adaptive routing system is evaluated and analysed