Subject: Re: Path length Distribution in MANET

From: Nitin H Vaidya <[email-masked]>
Date: Mon, 5 Jun 2000 15:23:49 -0500 (CDT)

>> From: Ravi Prakash <[email-masked]>
  >> 
  >> We did some preliminary simulation experiments to determine the upper
  >> bounds on path lengths and path stability in mobile ad hoc networks. The
  >> idea was to have nodes move on a grid of streets, as in a fleet of
  >> taxi-cabs. 
  >> 
  >> The goal of these experiments was to determine the feasibility of route
  >> caching in protocols like AODV and DSR. Our experiments seem to indicate
  >> that caching may have very limited utility as paths do not stay unchanged
  >> for long. 

I don't mean to distract folks from the interesting discussion
on path lengths, but we reported a similar conclusion about the
perils of caching in "dynamic" ad hoc networks, in our MobiCom 99
paper on TCP-on-MANET (the paper discusses the interaction between
TCP and stale caches).

Of course, caches are not a bad idea in general. As intuition would
suggest, caches can be helpful in networks with slowly mobile nodes.

- nitin

  >> The paper containing these results is available as University of Texas at
  >> Dallas Technical Report # UTDCS-05-00 and can be downloaded from the
  >> following URL:
  >> 
  >>   www.utdallas.edu/~ravip/papers/persist.ps
  >> 
  >> Here is a brief description of the work and a synopsis of results. I would
  >> really appreciate your comments. 
  >> 
  >> With best regards,
  >> 
  >> ----Ravi.
  >> 
  >> ========================= DESCRIPTION ================================
  >> 
  >> Two cabs (also referred to as nodes) in line of sight have a range R, and
  >> two cabs on mutually perpendicular streets have range R' (where R' <
  >> R). Then, two nodes that are within range are supposed to have a link. So,
  >> it is a minor modification of the unit-disk graph model. We ran the
  >> Bellman-Ford algorithm to determine the reachability of nodes.
  >> Also, we decided to simulate movement in a region where the bounds along
  >> the x-axis and y-axis were both significantly more than R. This ensures
  >> that the network does not appear to be a linear alignment of nodes.
  >> 
  >> We noticed that when  the number of nodes was small the graph was highly
  >> partitioned and there were very few paths, with a majority being one-hop.
  >> As the number of nodes increased, as expected the number of partitions
  >> decreased and the average path length increased. The paper presents the
  >> mean and the 90% confidence intervals of path length and path persistence. 
  >> 
  >> Path persistence was measured as the duration for which the shortest path
  >> between a pair of nodes remains unchanged, i.e., all the intermediate
  >> nodes stay in the same alignment. As expected, with increasing path
  >> length, path persistence declined rather steeply. This, in our opinion, is
  >> because in a longer path there is a higher probability that at least
  >> one node will move such that it is now out of range of at least one of its
  >> neighbors (predecessor/successor) in the path. 
  >> 
  >> What was most disturbing was that path persistence was very low even when
  >> nodes alternated between moving at an average speed of 35 kph for a while,
  >> and staying put for a while on reaching the destination of their
  >> trip. Please note that we considered an ideal (i.e., highly
  >> unrealistic) communication model where two nodes within range always had a
  >> link. So, in reality both path persistence and path length may be far
  >> lower than what our experiments indicate. This seems to imply that the
  >> reduction in route discovery traffic that protocols like AODV and DSR
  >> strive to achieve by caching routes may be limited. 
  >> 
  >> Also, we found that deploying traffic lights at street-intersections
  >> increased path persistence while significantly reducing path lengths. This
  >> is because traffic lights tend to aggregate nodes at the intersections and
  >> they tend to move almost in unison until the next light. 
  >> 
  >> The presence of one-way streets has very little additional impact on path
  >> persistence and path lengths. 
  >> 
  >> ========================================================================
  >> Ravi Prakash ([email-masked])		www.utdallas.edu/~ravip
  >> Department of Computer Science
  >> The University of Texas at Dallas
  >> Richardson, TX 75083-0688.  Phone: (972) 883-2289,   Fax: (972) 883-2349
  >> 
  >> 
  >>

---

From: Ravi Prakash <[email-masked]>
Date: Mon, 5 Jun 2000 18:06:42 -0500 (CDT)

> suggest, caches can be helpful in networks with slowly mobile nodes.

Hi Nitin,

I would like to further qualify the statement by stating that caches can
be helpful in networks where the *communication to mobility ratio* is
high. Afterall, route caching will have little utility in a network where
the interarrival time of packets exceeds the caching duration. 

Proactive protocols like DSDV will suffer "high overheads" and will be
beaten by reactive ones like DSR and AODV when the packet interarrival
time exceeds the update interval (assuming the update interval has been
chosen with the mobility rate in mind). However, when a large number of
packets arrive at a node for routing the cost of periodic updates is
amortized over all these packets, thus reducing the overhead per packet. 

Thanks,

----Ravi.