Skip to Main content Skip to Navigation

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.
Complete list of metadata

Cited literature [6 references]  Display  Hide  Download
Contributor : Juan Antonio Cordero Connect in order to contact the contributor
Submitted on : Wednesday, June 30, 2010 - 10:57:01 PM
Last modification on : Sunday, June 26, 2022 - 11:51:56 AM
Long-term archiving on: : Tuesday, October 23, 2012 - 9:41:04 AM


Files produced by the author(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⟩



Record views


Files downloads