MPR-based Pruning Techniques for Shortest Path Tree Computation

Juan Antonio Cordero 1, 2
1 HIPERCOM - High performance communication
Inria Paris-Rocquencourt, UP11 - Université Paris-Sud - Paris 11, Inria Saclay - Ile de France, X - École polytechnique, CNRS - Centre National de la Recherche Scientifique : UMR
Abstract : Multi-Point Relaying (MPR) is a well-known relay pruning algorithm that has proved to be useful for efficient dissemination in Mobile Ad hoc Networks (MANETs). But this technique may be useful for other tasks in MANET link-state routing as well. In particular, the approach is attractive for the selection of topology information to be flooded across the network. Requirements for such topology selection are however different from those applying for efficient dissemination, so approaches in such direction need to address these requirements and adapt or complement the MPR mechanism accordingly. This paper analyzes the main asymptotic properties of MPR and MPR-based topology selection algorithms, and provides sufficient conditions for the correctness of MPR-based topology selection. It examines as well in detail the MPR-based topology selection algorithm of MPR-OSPF, Path MPR, and shows that this algorithm may be unable, in certain conditions, to preserve optimal routes in its topology selection. The paper concludes by proposing and validating a modification of the Path MPR algorithm to overcome this sub-optimal performance.
Type de document :
[Research Report] RR-7329, INRIA. 2010
Liste complète des métadonnées

Littérature citée [6 références]  Voir  Masquer  Télécharger
Contributeur : Juan Antonio Cordero <>
Soumis le : mercredi 30 juin 2010 - 22:57:01
Dernière modification le : vendredi 25 mai 2018 - 12:02:06
Document(s) archivé(s) le : mardi 23 octobre 2012 - 09:41:04


Fichiers produits par l'(les) auteur(s)


  • HAL Id : inria-00496617, version 1



Juan Antonio Cordero. MPR-based Pruning Techniques for Shortest Path Tree Computation. [Research Report] RR-7329, INRIA. 2010. 〈inria-00496617〉



Consultations de la notice


Téléchargements de fichiers