Title: A Distributed Adaptive Cache Update Algorithm for the Dynamic Source Routing Protocol 

(NYU-CS-TR842)

Authors: Xin Yu and Zvi M. Kedem


Abstract:
On-demand routing protocols use route caches to make routing decisions.  Due
to frequent topology changes, cached routes easily become stale. To address
the cache staleness issue in DSR (the Dynamic Source Routing protocol),
prior work mainly 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
present a novel distributed cache update algorithm to make route caches
adapt quickly to topology changes without using ad hoc parameters. We define
a new cache structure called a cache table to maintain the information
necessary for cache updates. When a node detects a link failure, our
algorithm proactively notifies all reachable nodes that have cached the
broken link in a distributed manner. We compare our algorithm with DSR with
path caches and with Link-MaxLife through detailed simulations. We show that
our algorithm significantly outperforms DSR with path caches and with
Link-MaxLife.