An analytical model of Duato´s fully-adaptive routing algorithm in k-ary n-cubes

Analytical models of deterministic routing in wormhole-routed k-ary n-cubes have widely been reported in the literature. Although many fully-adaptive routing algorithms have been proposed to overcome the performance limitations of deterministic routing, there has been hardly any study that describes analytical models for these algorithms. The paper proposes a queueing model for obtaining latency measures in wormhole-routed k-ary n-cubes with fully-adaptive routing, based on Duato´s (1993) algorithm. The validity of the model is demonstrated by comparing analytical results with those obtained through simulation experiments