Optimizing Route-Cache Lifetime in Ad Hoc Network.

Optimizing Route-Cache Lifetime in Ad Hoc Network, Ben Liang, Zygmunt Haas, IEEE Infocom 2003.

This paper deals with building a mathematical framework to analyze the performance of ad hoc network and the effectiveness of route cache. The mathematical framework is straightforward probabilistic analysis (same tools as queueing theory, I'd say), trying to find the residual lifetime of a link (or, rather, the Laplace transform of the distribution thereof) as well, then computing the probability that the link is still up, and thus that the cost (in terms of delay) of the route discovery process is nil, the probability that the link has timed out (therefore: cost=route discovery overhead) or the probability that the cost is that of using an entry corresponding to a broken link (cost=route repair).

The analytical result involves solving some polynomial equations and inverting the Laplace transform. A closed form expression is given for the case where the arrival process and the link breakage process are memoryless (both reasonable assumption, actually).

The result shows that the optimal route time-out is independent of the packet arrival process (which is actually quite obvious when you think about it: you should keep the route as long as the network topology is valid, which is independent of the packet arrivals).

The not-technical note: Ben Liang was TPC program co-chair for IEEE MASS'06. I believe that Ben's advisor and co-author here, Zygmunt Haas was TPC chair, with Jennifer Hou, if my memory is correct. Ben is now a faculty at UToronto, and as publication chair for the conference, I ended up interacting with him quite a bit. We actually got quite a few new features implemented in EDAS to support our needs (e-copyrights, or a way to export data to fit the proceedings CD processing company requirements, thanks to Henning's willingness and responsiveness). I feel I should have known about this paper then.