Subject: Re: [manet] Request table and ID FIFO cache of DSR

From: Dave Maltz <[email-masked]>
Date: Fri, 15 Aug 2003 15:23:27 -0400

In message <[email-masked]>, Young-J
un Lee writes:
>I'm trying to implement DSR protocol in a simulation tool.
>While reading the DSR draft (draft-ietf-manet-dsr-08.txt),
>I found the request table structure a little bit confusing.
>
>In Page 28 of the draft, it says route request table records information
>about route request, i.e. <id, dst> using ID fifo cache.
>Does this mean that this ID fifo cache is a field of request table entry?
>Or, is the ID fifo cache a separate data structure?

My intention was that the ID cache is a field of the request table
entry, although you do not have to design it that way.  The DSR spec
only defines the conceptual data structure for a Route Request table.

The requirments are that given a src and an ID, a node must be able to
determine whether it has already forwarded route request #ID from that
src.  The node should not remember more than RequestTableIds IDs.

>I checked the DSR model in ns-2 and the DSR linux implementation by univ.
>Colorado, but both do not have any data structure like ID fifo cache.
>I'd appreciate it if anybody gives me some hints on this.

The reason for limiting the cache to contain only RequestTableIds IDs
is that when a node reboots it may lose track of what IDs were on its
recent Route Requests.  If the node is extremely unlucky, it might
reuse IDs it had already sent, causing neighbors to drop the new Route
Requests as duplicates.  Limiting the amount of history the neighbors
can store limits the total length of time the node can be unlucky (the
counter balancing factor that keeps us from setting RequestTableIds to
1 is that for Route Discovery to be most efficient, a single node
should not have more than RequestTableIds Route Requests outstanding
at one time).

Since we did not intend our ns-2 simulations to model individual nodes
crashing and rebooting, we did not implement the ID cache in the ns-2
model.

We did implement it in our FreeBSD kernel implementation.  (available
from www.monarch.rice.edu, see freebsd/sys/dsr/requesttable.h)

Cheers,
 -dam

_______________________________________________
manet mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/manet