Making Link-State Routing Scale for Ad Hoc Networks

ABSTRACT In this paper, we introduce a class of approaches that attempt to scale link-state routing by limiting the scope of link state update dissemination in space and over time. We present the first fundamental analysis of this generic class, which we call "Fuzzy Sighted Link State routing". Using a novel perspective on the "overhead " of a protocol that includes not only the overhead due to control messages but also due to route suboptimality, we formulate an analytical model whose solution automatically leads to the best algorithm in this class. This algorithm is shown to have nearly the best possible asymptotic overhead for any routing algorithm- proactive or reactive. Simulation results are presented that compare the performance of several algorithms in this class. 1. INTRODUCTION Since its inception as part of the ARPANET, link-state routing has become the most widely used approach in the Internet. Its popularity has resulted from its unique advantages, including simplicity, robustness, predictable dynamics, and unmatched support for flexible QoS-based route generation. Unfortunately, as is widely recognized, link-state routing as used in the wired Internet scales poorly when used in mobile ad hoc networks. Given its advantages, a sufficiently scalable version of linkstate routing would be invaluable for ad hoc networks. Not surprisingly therefore, there are a number of approaches in the literature with this goal. These approaches may be classified into efficient dissemination approaches and limited dissemination approaches. Both attempt to reduce the routing update overhead, but do so in different ways. In efficient dissemination, updates are sent throughout the network, but more efficiently compared to traditional flooding. Examples include TBRPF[2], OLSR [3], STAR [4], etc. In contrast, limited dissemination consists of restricting the scope of routing updates in space and time. Examples include hiearchical link state [5], FSR and GSR (see [6]), etc