A Model of Path Stretch in Proactive Routing in MANETs

It is well known that topology information from nodes that are many hops away has little impact on the selection of the next hop. Hazy-sighted routing and fish-eye routing attempt to take advantage of this behavior in order to reduce overhead without impacting path stretch, which is the increase in the number of hops a packet travels as a result of stale topology information. However, these previous efforts failed to quantify the impact of their approach on path stretch. This paper develops a model of the path stretch as a function of stale topology information. To this end, we find a Markov model that describes the quality of packet forwarding, where jumps occur with some probability whenever the topology changes. From this Markov model, a precise model of path stretch can be derived, and a new and less optimistic view of hazy-sighted flooding emerges.