Distributed Adaptive Cache Update Algorithm for the Dynamic Source Routing Protocol
On demand routing protocols use route caches to make routing decisions. Due to mobility, cached routes easily become stale. To address the cache staleness issue, prior work in DSR used heuristics with ad hoc parameters to predict the lifetime of a link or a route. However, heuristics cannot accurately predict timeouts because topology changes are unpredictable. In this paper, we propose to proactively disseminate the broken link information to the nodes that have that link in their caches. We deﬁne a new cache structure called a cache table and present a distributed cache update algorithm. Each node maintains in its cache table the information necessary for cache updates. When a link failure is detected, the algorithm notiﬁes all reachable nodes that have cached the link in a distributed manner. The algorithm does not use any ad hoc parameters, thus making route caches fully adaptive to topology changes. We show that the algorithm outperforms DSR with path caches and with Link-MaxLife, an adaptive timeout mechanism for link caches. We conclude that proactive cache updating is the key to the adaptation of on-demand routing protocols to mobility.
In mobile ad hoc networks, nodes move arbitrarily. Frequent topology changes present the fundamental challenge to routing protocols. Routing protocols can be classiﬁed into two major types: proactive and on-demand. Proactive protocols attempt to maintain up-to-date routing information to all nodes by periodically disseminating topology updates throughout the network. On-demand protocols attempt to discover a route only when a node originates a packet. To reduce the overhead and the latency of initiating a route discovery for each packet, on-demand routing protocols use route caches. Due to mobility, cached routes easily become stale. Using stale routes causes packet losses and increases latency and overhead. In this paper, we investigate how to make on-demand routing protocols adapt quickly to topology changes, an important and challenging problem. To address the cache staleness issue in DSR (the Dynamic Source Routing protocol) prior work used adaptive timeout mechanisms. Such mechanisms use heuristics with ad hoc parameters to predict the lifetime of a link or a route. However, a predetermined choice of ad hoc parameters for certain scenarios may not work well for others; scenarios in the real world are different from those used in simulations. Moreover, heuristics cannot accurately predict timeouts because topology changes are unpredictable. As a result, either valid routes will be removed or stale routes will be kept in caches. DSR uses a small cache size for path caches in order to evict stale routes faster. However, as trafﬁc load or network size increases, small caches will cause route re-discoveries, because more routes need to be stored but small caches cannot hold all useful routes. If the cache size is set large, more stale routes will stay in caches because FIFO becomes less effective. It was shown that path caches with unlimited size perform much worse than caches with limited size because of stale routes . In this paper, we propose to proactively disseminate the broken link information to the nodes that have that link in their caches. Proactive cache updating is the key to making route caches adapt quickly to topology changes. It is important to inform only the nodes that have cached a broken link so as to avoid unnecessary overhead. Thus, when a link failure is detected, our goal is to notify all reachable nodes that have cached the broken link. We deﬁne a new cache structure called a cache table to maintain the information necessary for cache updates. A cache table has no capacity limit. Each node maintains in its cache table two types of information for each route. The ﬁrst type of information is how well routing information is synchronized among nodes on a route: whether a link has been cached in only upstream nodes, or both upstream and downstream nodes, or neither. The second type of information is which neighbor has learned which links through a RO U T E RE P LY. Thus, we keep track of topology propagation state, the information necessary and sufﬁcient to remove stale routes, in a distributed manner. We present a novel algorithm that uses the information kept by each node to achieve distributed cache updating. When a link failure is detected, the algorithm notiﬁes selected neighborhood nodes about the broken link: the closest upstream and/or downstream nodes in each route containing the broken link, and other neighbors that have cached that link. When a node receives a notiﬁcation, the algorithm notiﬁes selected neighbors. Therefore, the broken link information will be quickly propagated to all reachable nodes that need to be notiﬁed.
Our algorithm has the following desirable properties:
• Distributed: The algorithm uses only local information and
communicates with neighborhood nodes; therefore, it is
scalable with network size.
• Adaptive: The algorithm notiﬁes only the nodes that have
cached a broken link to update their caches; therefore, cache
update overhead is minimized.
• Proactive on-demand: Proactive cache updating is triggered
on-demand, without periodic behavior.
• Without ad hoc mechanisms: The algorithm does not use any
ad hoc parameters, thus making route caches fully adaptive
to topology changes.