Stability of a local greedy distributed routing algorithm

Florian Huc 1 Christelle Molle 2, * Nicolas Nisse 2 Stéphane Pérennes 2 Hervé Rivano 2
* Auteur correspondant
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
Abstract : In this work, we study the problem of routing packets between undifferentiated sources and sinks in a network modeled by a multigraph. We provide a distributed and local algorithm that transmits packets hop by hop in the network and study its behaviour. At each step, a node transmits its queued packets to its neighbours in order to optimize a local gradient. This protocol is thus greedy since it does not require to record the history about the past actions, and lazy since it only needs informations of the neighborhood. We prove that this protocol is stable in the sense that the number of packets stored in the network stays bounded as soon as the sources injects a flow that another method could have exhausted. In particular, our protocol stays stable even if the feasibility condition is not strict on topologies with several sources and destinations, under a conjecture when the value of the flow is constrained at the destination nodes. We therefore reinforce a result from the literature that worked for differentiated suboptimal flows.
Type de document :
Rapport
[Research Report] RR-6871, INRIA. 2009
Liste complète des métadonnées


https://hal.inria.fr/inria-00366441
Contributeur : Christelle Caillouet <>
Soumis le : mardi 6 octobre 2009 - 15:56:35
Dernière modification le : samedi 17 septembre 2016 - 01:33:28
Document(s) archivé(s) le : mercredi 22 septembre 2010 - 13:27:19

Fichier

RR-6871.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00366441, version 2

Collections

Citation

Florian Huc, Christelle Molle, Nicolas Nisse, Stéphane Pérennes, Hervé Rivano. Stability of a local greedy distributed routing algorithm. [Research Report] RR-6871, INRIA. 2009. <inria-00366441v2>

Partager

Métriques

Consultations de
la notice

250

Téléchargements du document

114