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 , Laboratoire I3S - 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).
Document type :
Conference papers
Complete list of metadatas

https://hal.inria.fr/inria-00466484
Contributor : Hervé Rivano <>
Submitted on : Wednesday, March 24, 2010 - 12:26:48 AM
Last modification on : Monday, November 5, 2018 - 3:36:03 PM

Identifiers

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. ⟨10.1109/IPDPSW.2010.5470832⟩. ⟨inria-00466484⟩

Share

Metrics

Record views

400