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

Yih Chun Hu, David B. Johnson

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publicationProceedings of the ACM International Workshop on Principles of Mobile Commerce
Pages25-30
Number of pages6
StatePublished - Dec 1 2002
Externally publishedYes
EventProceedings of the Second International Workshop on Principles of Mobile Commerce POMC '2002 - Toulouse, France
Duration: Oct 30 2002Oct 31 2002

Publication series

NameProceedings of the ACM International Workshop on Principles of Mobile Commerce

Other

OtherProceedings of the Second International Workshop on Principles of Mobile Commerce POMC '2002
Country/TerritoryFrance
CityToulouse
Period10/30/0210/31/02

Keywords

  • Ad hoc networks
  • Bounded latency
  • DSR
  • Dynamic Source Routing
  • Epoch numbers
  • Route cache
  • Theory

ASJC Scopus subject areas

  • Engineering(all)

Fingerprint

Dive into the research topics of 'Ensuring Cache Freshness in On-Demand Ad Hoc Network Routing Protocols'. Together they form a unique fingerprint.

Cite this