Semiring Pruning for Information Dissemination in Mobile Ad Hoc Networks

Link state routing mechanisms have shown good convergence behaviour with mobile hosts. Pruning methods such as those used in Optimized Link State Routing (OLSR) have showed good throughput behaviour when compared to traditional link-state approaches which suffered from broadcast storm problems. In this paper, we show that the pruning function is a fundamental component of link-state routing protocols for mobile networks. We also show that this component architecture aids in interpreting both distance vector and link-state approaches under a common framework. We develop a class of pruning methods for many of the most commonly used routing objectives and show that these pruning methods are a special case of the semiring distribution property.