On-demand link-state routing in ad hoc networks

This thesis explores the challenges, merits and demerits of using link-state information for on-demand routing in ad hoc networks, such that routers maintain path information for only those destinations for which they have data traffic.; We first present the source tree on-demand adaptive routing (SOAR) protocol, in which each router exchanges with its neighbors a "source tree" containing paths to only those destinations for which the router is the source or relay of data packets. The main advantage of SOAR is that it is more scalable and better performing than current state-of-the-art on-demand routing protocols. However, a limitation of SOAR is that it requires data packets to specify the paths they traverse to detect loops. To eliminate the need for source routing or path traversal information in data packets, we introduce the on-demand link-vector (OLIVE) protocol, which prevents temporary loops for each destination by synchronizing relevant link-state information among neighbors. In OLIVE, the advertised paths combine to form a source graph, rather than a source tree. OLIVE is shown to outperform the current routing protocols proposed for mobile ad-hoc networks in terms of control overhead, throughput and network delay.; We demonstrate that the problem of computing a source tree with the constraint imposed due to the exact nature of on-demand routing protocols is an NP-complete problem and show approximation algorithms for the path-selection problem.; The practical implementations of ad-hoc networks would be mainly wireless extensions of the wired Internet and the traffic would be mainly from the mobile nodes towards certain special nodes that act as gateways to the wired Internet. To achieve high performance in such scenarios we have developed a new genre of node-centric hybrid routing protocol where routes for frequently-accessed gateways would be kept proactive, while routes between mobile nodes would be reactive.