Skip to Main content Skip to Navigation

An adaptive strategy for deflection routing in meshes

Abstract : In this paper, we describe a new adaptive routing algorithm for meshed-topology deflection networks. Our algorithm is based on a local learning method which evolves in order to produce a local spatial representation of the traffic. We first prove that our algorithm is a generalization of the $Z^2$ routing. Secondly, we prove that we can set the parameters of the learning algorithm such that our adaptive policy cannot create livelock situation. Then we show experimentally the efficiency of our algorithm. First, we compare the routing policies in a grid network, under an uniform load. Second, we create local congestion in order to show that the adaptive routing scheme avoid the overloaded region. Moreover, we propose a more realistic traffic model, and show that our algorithm is valid, even in such context. At last, we show that the algorithm is also efficient in a torus network. These results show the relevance of this method.
Document type :
Complete list of metadatas

Cited literature [15 references]  Display  Hide  Download
Contributor : Colette Orange <>
Submitted on : Wednesday, April 17, 2019 - 9:09:23 AM
Last modification on : Thursday, November 21, 2019 - 2:38:40 AM


Files produced by the author(s)


  • HAL Id : hal-02101903, version 1



Thierry Chich. An adaptive strategy for deflection routing in meshes. [Research Report] LIP RR-1997-25, Laboratoire de l'informatique du parallélisme. 1997, 2+18p. ⟨hal-02101903⟩



Record views


Files downloads