Ensuring Cache Freshness in On-Demand Ad Hoc Network Routing Protocols

In a wireless ad hoc network, nodes cooperate to forward packets for each other over possibly multi-hop paths, to allow nodes not within direct wireless transmission range to communicate. Many routing protocols have been proposed for the ad hoc network environment, several of which operate on-demand and utilize a route cache listing links that this node has learned. In such protocols, aggressive caching of overheard routes can significantly improve performance; in particular, overhead can be reduced by leveraging information received in packets overheard or forwarded from other nodes, including other routing packets and the source routes on other data packets. Unfortunately, such information sharing can substantially increase the risk of cache cross-pollution, since stale routing information in one node's cache, representing a link that no longer exists, can easily be added into the caches of other nodes. Even when a node has actually learned that a link no longer exists, it is still possible for that node to again hear the stale information. In this paper, we present a new mechanism which we call epoch numbers, to reduce this problem of cache staleness, by preventing the re-learning of stale knowledge of a link after having earlier heard that the link has broken. Our scheme does not rely on ad hoc mechanisms such as short-lived negative caching; rather, we allow a node having heard both of a broken link and a discovery of the same link to sequence the two events in order to determine whether the link break or the link discovery occurred before the other.