Stability of a Localized and Greedy Routing Algorithm

Christelle Caillouet 1 Nicolas Nisse 2 Florian Huc 3 Stéphane Pérennes 2 Hervé Rivano 4
1 Drakkar
LIG - Laboratoire d'Informatique de Grenoble
2 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
4 SWING - Smart Wireless Networking
Inria Grenoble - Rhône-Alpes, CITI - CITI Centre of Innovation in Telecommunications and Integration of services
Abstract : In this work, we study the problem of routing packets between undifferentiated sources and sinks in a network modeled by a multigraph. We consider a distributed and local algorithm that transmits packets hop by hop in the network and study its behavior. At each step, a node transmits its queued packets to its neighbors in order to optimize a local gradient. This protocol is greedy since it does not require to record the history about the past actions, and localized since nodes only need information about their neighborhood. A transmission protocol is \emph{stable} if the number of packets in the network does not diverge. To prove the stability, it is sufficient to prove that the number of packets stored in the network remains bounded as soon as the sources inject a flow that another method could have exhausted. The localized and greedy protocol considered has been shown to be stable in some specific cases related to the arrival rate of the packets. We investigate its stability in a more general context and therefore reinforce results from the literature that worked for differentiated suboptimal flows. We show that, to prove the stability of this protocol, it is sufficient to prove the intuitive following conjecture: roughly, if the protocol is stable when all sources inject the maximum number of packets at each turn and no packets are lost, then the protocol is stable whatever be the behavior of the network (i.e., when less packets are injected and some of them may be lost).
Type de document :
Communication dans un congrès
12th IEEE Workshop in Parallel and Distributed Computational Models (IEEE APDCM 2010), in conjunction with IPDPS 2010, Apr 2010, Atlanta, United States. IEEE, 2010, Parallel & Distributed Processing, Workshops and Phd Forum (IPDPSW), 2010 IEEE International Symposium on. <10.1109/IPDPSW.2010.5470832>
Liste complète des métadonnées

https://hal.inria.fr/inria-00466484
Contributeur : Hervé Rivano <>
Soumis le : mercredi 24 mars 2010 - 00:26:48
Dernière modification le : jeudi 18 août 2016 - 01:07:43

Identifiants

Collections

Citation

Christelle Caillouet, Nicolas Nisse, Florian Huc, Stéphane Pérennes, Hervé Rivano. Stability of a Localized and Greedy Routing Algorithm. 12th IEEE Workshop in Parallel and Distributed Computational Models (IEEE APDCM 2010), in conjunction with IPDPS 2010, Apr 2010, Atlanta, United States. IEEE, 2010, Parallel & Distributed Processing, Workshops and Phd Forum (IPDPSW), 2010 IEEE International Symposium on. <10.1109/IPDPSW.2010.5470832>. <inria-00466484>

Partager

Métriques

Consultations de la notice

279