An adaptive strategy for deflection routing in meshes

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.Nous proposons un algorithme adaptatif pour les réseaux maillés à déflexion. Cet algorithme est fondé sur une méthode d'apprentissage locale qui permet d'obtenir une représentation spatiale du trafic et de gérer ainsi la répartition de la charge. Nous montrons que notre algorithme peut être vu comme une généralisation du routage $Z^2$ qui est optimal dans les réseaux maillés réguliers. Ensuite, nous montrons que notre algorithme ne peut pas créer d'inter-bloquage dynamique. Puis nous montrons expérimentalement l'efficacité de notre algorithme. D'abord, nous comparons notre politique de routage avec une politique de routage $Z^2$ dans une grille, sous une charge uniforme. Puis nous créons artificiellement des congestions locales pour montrer que notre algorithme permet d'éviter les zones surchargées. Enfin, nous proposons un modèle de trafic plus réaliste et nous montrons que, et dans la grille et dans le tore, l'algorithme permet l'amélioration des performances par un meilleur partage des ressources