The odd-even turn model for adaptive routing

TLDR

This paper proposes a model for designing adaptive wormhole routing algorithms for mesh networks without virtual channels. The model restricts turn locations to avoid deadlock. The odd‑even turn model yields more uniformly adaptive routing across source‑destination pairs, enhancing communication efficiency, reducing sensitivity to hot‑spot traffic, and stabilizing performance across traffic patterns.

Abstract

This paper presents a model for designing adaptive wormhole routing algorithms for meshes without virtual channels. The model restricts the locations where some turns can be taken so that deadlock is avoided. In comparison with previous methods, the degree of routing adaptiveness provided by the model is more even for different source-destination pairs. The mesh network may benefit from this feature in terms of communication efficiency. Simulation results show that the even adaptiveness provided by the odd-even turn model makes message routing less vulnerable to nonuniform factors such as hot spot traffic. In addition, this property results in a smaller fluctuation of the network performance with respect to different traffic patterns.