Re: [manet] DYMO/AODVv2 and LOADng -- Problems and Proposed Solutions

["Charles E. Perkins" <[e-mail]>]

Hello Marius,

Interesting results.  I have some follow-up questions.

On 12/3/2012 9:21 PM, Marius Portmann wrote:
>
> (1) Non-Optimal Routes
>
> --------------------------------
>
> On-demand/reactive routing protocols (such as AODV, DYMO and 
> LOADng) often fail to discover the best (shortest) routes [1,2].
>

This is certainly true.  There have been measurements about how far from 
optimal
the routes can be, and if I remember correctly it's typically somewhere 
in the
neighborhood of 10%, depending on congestion and node mobility.

> The problem is that during route discovery the destination (target) 
> node does not forward route requests; so, nodes that lie downstream of 
> the destination node frequently create non-optimal routes to the 
> source. Knightly and Miskovic [1] have shown that "poorly selected 
> paths can have significantly higher routing-metric costs, and their 
> duration can extend to minute time scales".
>
> We have verified that this problem exists in DYMO and LOADng.
>

Moreover, the result makes intuitive sense.  However, the nodes which 
establish
non-optimalroutes to the source are also unlikely to use those routes.

> As a possible solution, we propose that route requests are always 
> forwarded, even by nodes generating a route reply [2,3]. The forwarded 
> request should include a flag stating that a reply has already been 
> initiated. In [3] it is shown that this increases the quality of 
> routes. Of course this could increase the overhead of control 
> messages, but in most of the cases the additional overhead is minimal, 
> since a request floods the entire network anyway.
>

This can be made into an optional behavior, controllable either by a
system-wide configuration parameter, or a new RREQ option.  I would
not expect that it should be the default behavior.


> (2) Route Reply Loss
>
> -----------------------------
>
> AODV can lose route replies 
> (http://www.ietf.org/mail-archive/web/manet/current/msg05702.html).
>
> The reason is that route replies are only forwarded by an intermediate 
> node when the node updates its routing table.
>
> This problem has partly been solved in DYMO and LOADng by increasing 
> sequence numbers when initiating a route reply.
>
> However, a careful analysis shows that replies can still be lost; 
> yielding again non-optimal routes or route discovery failures. Namely, 
> if one route reply overtakes another, i.e., a newer reply reaches a 
> node earlier than an older one, then the older route reply is dropped [4].
>

I guess you mean that the two RREPs under discussion were going towards
two distinct Originating Nodes. Otherwise, it would be good for the 
older RREP
to be dropped.

For the case of two distinct Originating Nodes, the behavior is a protocol
error that needs to be fixed."Always forwarding" RREPs is one alternative,
and certainly preferable to a new Route Discovery cyclein the network.
I am confident that there is a better solution, and I will work on finding
and specifying it.

> (3) Route Request Loss
>
> ---------------------------------------------
>
> Similar to (2), route requests might be lost in DYMO and LOADng.
>
> Namely, if one route request overtakes another, i.e., a newer request 
> reaches a node earlier than an older one, then the older route request 
> is dropped.
>
> This problem does not occur in AODV, thanks to the use of a list of 
> previously seen RREQ IDs.
>

I think that a "better" solution for (2) will also resolve this problem.
Here, the solution of "always forwarding" seems much less palatable.

Thanks much for reporting these error cases, and for providing the
references.

-- 
Regards,
Charlie P.