Scalable Route Caching Methods for Networks with Many Mobile Nodes

Abstract

A mobile, ad hoc network (MANET) is a collection of wireless mobile hosts forming a networkwithout the aid of any established infrastructure or centralized administration. Generally aMANET may consist of many portable devices that are characterized by processing and memorysize limitations and in practice it will not be possible for a host to keep routing informationfor all the nodes in a large network.<p>This thesis attempts to address the scalability issue by introducing a framework and strategiesto quantify the concept of destination caching. The observation that a source host can augmentits cache's routing table by using the caches of other closely situated hosts forms the basisof our approach. We propose algorithms that determine a host's cached information by takinginto account the host's memory capacity, the network size and the number and identity of thedestinations this host needs to cache information about.<p>Mainly two classes of algorithms are introduced. The class of "Best State/Best Cost" algorithms(BSBC) tries to minimize the flooding cost per route discovery by keeping the most "expensive"destinations in each host's cache. However it does not impose any flooding constraints for thenon-cached destinations. The second class of LEADERS algorithms adopts a different view by relaxingon the flooding cost optimality and taking into account a maximum flooding constraint for each node.In this way, the worst flooding case is controlled since any node is guaranteed to find informationabout any destination within a pre-specified maximum distance.