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 :
Reports
Complete list of metadatas

Cited literature [15 references]  Display  Hide  Download

https://hal-lara.archives-ouvertes.fr/hal-02101903
Contributor : Colette Orange <>
Submitted on : Wednesday, April 17, 2019 - 9:09:23 AM
Last modification on : Wednesday, November 20, 2019 - 7:24:06 AM

File

RR1997-25.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02101903, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

4

Files downloads

7