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

From: Marius Portmann <[email-masked]>
Date: Tue, 4 Dec 2012 05:21:00 +0000

We have been following the recent discussion on DYMO and LOADng with interest, and would like to share some of our findings and experience in this context, in the hope of being able to make a constructive contribution. Any feedback is appreciated.

Based on a careful analysis of AODV, we have encountered problems that still persist in both DYMO (ver 23) and LOADng (ver 6).

(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].

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.

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.

(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].

A solution consists of intermediate nodes always forwarding route replies. Surely, forwarding (unicasting) replies increases the number of messages in the network. But, (a) route discovery is more likely and (b) re-sending a route request to establish a route would yield another broadcast  cycle, which is much more expensive w.r.t. network load.

(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.

---------------------------------------------

If requested we can provide  more detailed explanations and examples.

Rob van Glabbeek
Peter Höfner
Marius Portmann
Wee Lum Tan
(a team of networks and formal methods researchers at NICTA, working on formally modelling and analysing MANET routing protocols)

cheers
Marius

References
---------------
[1] S. Miskovic and E. W. Knightly, "Routing primitives for wireless mesh networks: Design, analysis and experiments", in Conference on Information Communications (INFOCOM'10). IEEE, 2010, pp. 2793-2801.
networks.rice.edu/papers/MeshRoutingPrimitives.pdf<http://networks.rice.edu/papers/MeshRoutingPrimitives.pdf>
[2] P. Höfner, R. J. van Glabbeek, W. L. Tan, M. Portmann, A. McIver, and A. Fehnker, "A rigorous analysis of AODV and its variants", in Modeling, Analysis and Simulation of Wireless and Mobile Systems (MSWIM'12). ACM Press, 2012. doi:10.1145/2387238.2387274
http://www.cse.unsw.edu.au/~rvg/pub/mswim12.pdf
[3] A. Fehnker, R. J. van Glabbeek, P. Höfner, A. McIver, M. Portmann, and W. L. Tan, "Automated analysis of AODV using UPPAAL", in Tools and Algorithms for the Construction and Analysis of Systems (TACAS'12), LNCS, C. Flanagan and B. König, Eds., vol. 7214. Springer, 2012, pp. 173-187. doi:10.1007/978-3-642-28756-5_13
http://www.cse.unsw.edu.au/~rvg/pub/tacas12.pdf
[4] P. Höfner, and S. Edenhofer, "Towards a Rigorous Analysis of AODVv2 (DYMO)", in Workshop on Rigorous Protocol Engineering, IEEE
http://www.nicta.com.au/pub?id=6169

----------------------------------------------------------------------

Dr Marius Portmann

School of ITEE

The University of Queensland

Brisbane 4072, Australia

CRICOS Provider No: 00025B

Tel: +61 7 3300 8561, Fax: +61 7 3365 4999

----------------------------------------------------------------------

---

From: Abdussalam Baryun <[email-masked]>
Date: Tue, 4 Dec 2012 15:04:31 +0000

Hi Marius

Thanks for your feedback and references, but your analysis will be more
interesting if I know when/how such disadvantages happen in your work done
so far. Could you inform on the list of the evaluation you done as
including number of nodes, mobility model, etc. However, when I get time to
read your references I can reply better.

No protocol is perfect in general :)

AB

On Tue, Dec 4, 2012 at 5:21 AM, Marius Portmann <[email-masked]>wrote:

>  We have been following the recent discussion on DYMO and LOADng with
> interest, and would like to share some of our findings and experience in
> this context, in the hope of being able to make a constructive
> contribution. Any feedback is appreciated.****
>
> ** **
>
> Based on a careful analysis of AODV, we have encountered problems that
> still persist in both DYMO (ver 23) and LOADng (ver 6).****
>
> ** **
>
> (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].****
>
> ** **
>
> 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.****
>
> ** **
>
> 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.****
>
>   ****
>
> (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].****
>
> ** **
>
> A solution consists of intermediate nodes always forwarding route
> replies. Surely, forwarding (unicasting) replies increases the number of
> messages in the network. But, (a) route discovery is more likely and (b)
> re-sending a route request to establish a route would yield another
> broadcast  cycle, which is much more expensive w.r.t. network load.****
>
> ** **
>
> (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.****
>
> ** **
>
> ---------------------------------------------****
>
>
> If requested we can provide  more detailed explanations and examples.****
>
> ** **
>
> ** **
>
> Rob van Glabbeek****
>
> Peter Höfner****
>
> Marius Portmann****
>
> Wee Lum Tan****
>
> (a team of networks and formal methods researchers at NICTA, working on
> formally modelling and analysing MANET routing protocols)****
>
> ** **
>
> ** **
>
> cheers****
>
> Marius****
>
> ** **
>
> ** **
>
> ** **
>
> References****
>
> ---------------****
>
> [1] S. Miskovic and E. W. Knightly, "Routing primitives for wireless mesh
> networks: Design, analysis and experiments", in Conference on Information
> Communications (INFOCOM’10). IEEE, 2010, pp. 2793-2801.****
>
> networks.rice.edu/papers/MeshRoutingPrimitives.pdf****
>
> [2] P. Höfner, R. J. van Glabbeek, W. L. Tan, M. Portmann, A. McIver, and
> A. Fehnker, "A rigorous analysis of AODV and its variants", in Modeling,
> Analysis and Simulation of Wireless and Mobile Systems (MSWIM’12).
> ACM Press, 2012. doi:10.1145/2387238.2387274****
>
> http://www.cse.unsw.edu.au/~rvg/pub/mswim12.pdf****
>
> [3] A. Fehnker, R. J. van Glabbeek, P. Höfner, A. McIver, M. Portmann, and
> W. L. Tan, "Automated analysis of AODV using UPPAAL", in Tools and
> Algorithms for the Construction and Analysis of Systems (TACAS’12), LNCS,
> C. Flanagan and B. König, Eds., vol. 7214. Springer, 2012, pp. 173–187.
> doi:10.1007/978-3-642-28756-5_13****
>
> http://www.cse.unsw.edu.au/~rvg/pub/tacas12.pdf****
>
> [4] P. Höfner, and S. Edenhofer, "Towards a Rigorous Analysis of AODVv2
> (DYMO)", in Workshop on Rigorous Protocol Engineering, IEEE
> http://www.nicta.com.au/pub?id=6169****
>
> ** **
>
> ** **
>
> ----------------------------------------------------------------------****
>
> Dr Marius Portmann****
>
> School of ITEE****
>
> The University of Queensland****
>
> Brisbane 4072, Australia****
>
> CRICOS Provider No: 00025B****
>
> Tel: +61 7 3300 8561, Fax: +61 7 3365 4999****
>
> ----------------------------------------------------------------------****
>
> ** **
>
> ** **
>
> _______________________________________________
> manet mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/manet
>
>

---

From: "Charles E. Perkins" <[email-masked]>
Date: Tue, 04 Dec 2012 10:25:58 -0800

Hello Marius,

Interesting results.  I have some follow-up questions.

On 12/3/2012 9:21 PM, Marius Portmann wrote:
> 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".
>

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

> 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.

> AODV can lose route replies 
> (http://www.ietf.org/mail-archive/web/manet/current/msg05702.html).
>
> node when the node updates its routing table.
>
> 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.

> reaches a node earlier than an older one, then the older route request 
> is dropped.
>
> 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.

---

From: Jiazi YI <[email-masked]>
Date: Wed, 5 Dec 2012 18:34:04 +0100

Hi Marius, 
Thanks for you valuable comments, please check inline:

> Based on a careful analysis of AODV, we have encountered problems that still persist in both DYMO (ver 23) and LOADng (ver 6).

In LOADng, only bi-diretional routes are used by default, i.e. only the routes that are verified by RREP are used. So I think the example you mentioned in figure 2 of [3,4] shouldn't be a problem for LOADng.  

Of course, another well-known non-optimal routes problem is because of the broadcast nature of on-demand protocol. The LOADng authors are still discussing how to improve it. 

> (2) Route Reply Loss

I think it would be safe to forward every unicast RREPs. 

In the meantime, I'm wondering how often the situation that you mentioned in fig 1 of [4] would happen. Because it requires 1) two RREPs are generated in very short time interval and 2) The route set up by broadcasting two RREQs between the two nodes (B and T in your example) are different. 

I'll first check this with other LOADng authors also, to see which might be the better choice to make. 

> (3) Route Request Loss

Could you please have an example of this? What you said, the case that a newer RREQ reaches a node earlier than an older one, shouldn't happen. Because in LOADng, the originator of RREQ has a rate limit, i.e. certain interval. If an old RREQ came to an intermediate router that slow, probably it shouldn't be forwarded anyway, because it has great possibility to carry bad route information. 

best

Jiazi

> [1] S. Miskovic and E. W. Knightly, "Routing primitives for wireless mesh networks: Design, analysis and experiments", in Conference on Information Communications (INFOCOM’10). IEEE, 2010, pp. 2793-2801.
> networks.rice.edu/papers/MeshRoutingPrimitives.pdf
> [2] P. Höfner, R. J. van Glabbeek, W. L. Tan, M. Portmann, A. McIver, and A. Fehnker, "A rigorous analysis of AODV and its variants", in Modeling, Analysis and Simulation of Wireless and Mobile Systems (MSWIM’12). ACM Press, 2012. doi:10.1145/2387238.2387274
> [3] A. Fehnker, R. J. van Glabbeek, P. Höfner, A. McIver, M. Portmann, and W. L. Tan, "Automated analysis of AODV using UPPAAL", in Tools and Algorithms for the Construction and Analysis of Systems (TACAS’12), LNCS, C. Flanagan and B. König, Eds., vol. 7214. Springer, 2012, pp. 173–187. doi:10.1007/978-3-642-28756-5_13

---

From: "Charles E. Perkins" <[email-masked]>
Date: Wed, 05 Dec 2012 11:33:36 -0800

Hello again Marius,

I have been looking for the protocol error, and up until now have not
found it.  I probably should have looked closer before sending my
reply to you yesterday.   Here is a summary of the relevant protocol
details that affect processing (and, retransmission) of RREQ and RREP
messages.

- Check that the RREQ or RREP is "valid"
- Test all the routing information and use when permissible
- Update certain fields of the incoming message
- Decide whether to advertise availability for forwarding
- If so, retransmit (or, consume the RREQ and transmit RREP)

The relevant point is that an AODVv2 router retransmits the
RREQ or RREP regardless of whether the AODVv2 router used
the incoming routing information to update its route table.

I thought there might be some wording to the contrary, but after
reading the relevant parts of the specification several times I haven't
found any such wording.  Please let me know what I have missed.

Otherwise, since the AODVv2 routers typically do retransmit
route discovery messages even when not using the routing
information contained by those route discovery messages, I think
the problem you identified for earlier protocols does not arise.

Regards,
Charlie P.

On 12/4/2012 10:25 AM, Charles E. Perkins wrote:
> 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
>> node does not forward route requests; so, nodes that lie downstream 
>> of the destination node frequently create non-optimal routes to the 
>> 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.
>>
>
>> The reason is that route replies are only forwarded by an 
>> intermediate node when the node updates its routing table.
>>
>> 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].
>>
>
>> reaches a node earlier than an older one, then the older route 
>> request is dropped.
>>

-- 
Regards,
Charlie P.

---

From: Marius Portmann <[email-masked]>
Date: Thu, 13 Dec 2012 01:25:34 +0000

Dear Abdussalam,

Thanks for your feedback, and apologies for the delayed reply.

> Thanks for your feedback and references, but your analysis will be

> more interesting if I know when/how such disadvantages happen in

> your work done so far. Could you inform on the list of the

> evaluation you done as including number of nodes, mobility model, etc.

So far we have not performed any experimental quantitative evaluation on any particular network scenarios.

However, we believe if there is an identified limitation in a protocol, even if the corresponding problem might occur relatively rarely, and if the limitation has a simple, robust and low cost solution, it is worth implementing it.

> No protocol is perfect in general :)

True, but protocols should be as good as possible, within all the given constraints. :)

Cheers

Rob, Peter, Marius and Wee Lum

From: Abdussalam Baryun [mailto:[email-masked]]
Sent: Wednesday, 5 December 2012 1:05 AM
To: Marius Portmann
Cc: [email-masked]
Subject: Re: [manet] DYMO/AODVv2 and LOADng -- Problems and Proposed Solutions

Hi Marius

Thanks for your feedback and references, but your analysis will be more interesting if I know when/how such disadvantages happen in your work done so far. Could you inform on the list of the evaluation you done as including number of nodes, mobility model, etc. However, when I get time to read your references I can reply better.

AB
On Tue, Dec 4, 2012 at 5:21 AM, Marius Portmann <[email-masked]<mailto:[email-masked]>> wrote:
We have been following the recent discussion on DYMO and LOADng with interest, and would like to share some of our findings and experience in this context, in the hope of being able to make a constructive contribution. Any feedback is appreciated.

(1) Non-Optimal Routes

(2) Route Reply Loss

(3) Route Request Loss

Rob van Glabbeek
Peter Höfner
Marius Portmann
Wee Lum Tan

cheers
Marius

References
---------------

Dr Marius Portmann

School of ITEE

Brisbane 4072, Australia

Tel: +61 7 3300 8561<tel:%2B61%207%203300%208561>, Fax: +61 7 3365 4999<tel:%2B61%207%203365%204999>

_______________________________________________
manet mailing list
[email-masked]<mailto:[email-masked]>
https://www.ietf.org/mailman/listinfo/manet

---

From: Marius Portmann <[email-masked]>
Date: Thu, 13 Dec 2012 01:50:37 +0000

Dear Jiazi,

>> ----------------------
>> LOADng) often fails to discover the best (shortest) routes [1,2].

> In LOADng, only bi-directional routes are used by default, i.e. only
> the routes that are verified by RREP are used. So I think the example
> you mentioned in figure 2 of [3,4] shouldn't be a problem for LOADng.

As of yet we are not convinced that this covers all cases.
Isn't it the case that in LOADng a bidirectional routing entry can be
updated with new information from a RREQ message, and keep its flag saying
that the route is bidirectional? If yes, then we can adapt our example
to apply to LOADng: see
   http://www.cse.unsw.edu.au/~rvg/LOADng-non-optimal-routes.pdf

>> --------------------

> In the meantime, I'm wondering how often the situation that you
> mentioned in fig 1 of [4] would happen. Because it requires 1) two
> RREPs are generated in very short time interval and 2) The route
> set up by broadcasting two RREQs between the two nodes (B and T in
> your example) are different.

True. But even if the situation doesn't occur that often, we think a
the proposed fix comes without significant cost in communication overhead,
and thus is preferable to accepting the occasional loss of RREPs.

>> ----------------------
>> 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.

> Could you please have an example of this?

We created one at http://www.cse.unsw.edu.au/~rvg/route-request-loss.pdf

> What you said, the case that a newer RREQ reaches a node earlier
> than an older one, shouldn't happen. Because in LOADng, the
> originator of RREQ has a rate limit, i.e. certain interval. If an
> old RREQ came to an intermediate router that slow, probably it
> shouldn't be forwarded anyway, because it has great possibility to
> carry bad route information.

In the example in the above link, the dropped RREQ1 does come along a
route that is no longer optimal, but it should be forwarded anyway to
make sure the destination d learns about the request. Forwarding will
result in a bidirectional route between s and d that doesn't use the detour.

We hope this makes sense.

Best regards,

References
---------------

---

From: Jiazi YI <[email-masked]>
Date: Thu, 13 Dec 2012 14:56:12 +0100

Dear Marius,

thanks for your detailed reply, those figures are great :)
please check inline:

>    http://www.cse.unsw.edu.au/~rvg/LOADng-non-optimal-routes.pdf

There are two issues regarding this topic. 

1) The first is the difference between route using only bi-directional links, and bi-directional route. 
Currently, LOADng only supports finding route using only bi-directional links, not the latter. In another words, only the originator of the route discovery knows that there is a route using bi-directional links to the destination. For example, in your figure 1(a), <router s> knows there is a route to <router a> with bidirectional flag set to TRUE. For <router a>, even there is an available route to <router s>, he is not aware of that (so the bidirectional flag is FALSE). 
To build bi-directional route, another end-to-end RREP from originator to destination is needed, like three-way handshake. The LOADng authors have already a lot of discussions on this, but no consensus on it yet. Maybe I can put some of that discussion, and you  can share some of your experience later. 
So, in your example Figure 1(a), router a won't have a route to router s with bi-directional flag set to TRUE in the first place. 

2) Your argument is still valid, if it's <router a> sending a RREQ to <router d> in figure 2(b). In that case, <router s> will reset the route with the sub-optimal one. 

By having the destination router also broadcast the RREQ can solve the problem, but it would also result in more overhead. In certain scenarios, the overhead would be significant. In fact, what we are trying to do is to limit the broadcast region of RREQ, and there are some results in 
http://jiaziyi.com/documents/smart_rreq_full.pdf

I'll first think about the tradeoff and if there is other solutions, and then come back to you, is that OK?

> and thus is preferable to accepting the occasional loss of RREPs.

It's noted. And we will see if there is consensus to make this change. 

> result in a bidirectional route between s and d that doesn't use the detour.

By allowing stale RREQ broadcasting can have significant overhead in the network. 
As I said, for LOADng, there is a rate control at the originator of the RREQ, i.e., the RREQ is initiated with certain interval (for example, 0.1s). 
In your example, if the time for RREQ1 (t1) needed to get to <router a> is greater than traversal time of RREQ2 (t2) plus interval, then I think the route shouldn't be considered because of bad quality and long delay. In this case, I think what <router s> should do is wait for the route discovery timeout, and then initiate a new one for <router d>. 

> We hope this makes sense.

all your comments are very helpful and will be carefully considered. thanks again. 

regards

Jiazi

---

From: Marius Portmann <[email-masked]>
Date: Fri, 14 Dec 2012 02:09:35 +0000

Hi Charlie,

> This is certainly true. ... However, the nodes which establish

> non-optimal routes to the source are also unlikely to use those

> routes.

Of course it is quite possible that these 'indirectly discovered' non-optimal routes will never or rarely be used.

However, as far as we understand, DYMO/AODVv2 supports the option of 'path accumulation' (as it used to be called),  where nodes can include 'AddedNode routing information' discovered indirectly, i.e. not via the source or destination of a route discover process. Assuming the 'path accumulation' feature is beneficial, and nodes will use this 'indirectly discovered' routing information, we think it is likely that non-optimal routes will be used as a consequence.

>> control messages, but in most of the cases the additional overhead

>> is minimal, since a request floods the entire network anyway.

> not expect that it should be the default behavior.

This is obviously a trade off between the cost and the benefit of this mechanism.

We believe that overhead is small enough for it to be considered as a default option.

Unfortunately, we don't have any quantitative results to back this up at the moment.

> 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.

Yes, indeed.

> The relevant point is that an AODVv2 router retransmits the RREQ or

> RREP regardless of whether the AODVv2 router used the incoming

> routing information to update its route table.

> reading the relevant parts of the specification several times I

> haven't found any such wording.  Please let me know what I have missed.

Our analysis was based on DYMO/AODVv2 version 23. It now appears that in version 24, the specification has changed such that it is similar to what we are proposing, i.e. to let the AODVv2 routers always forward the RREQ/RREP messages.

All the best,

From: Charles E. Perkins [mailto:[email-masked]]
Sent: Thursday, 6 December 2012 5:34 AM
To: Marius Portmann
Cc: [email-masked]'
Subject: Re: [manet] DYMO/AODVv2 and LOADng -- Problems and Proposed Solutions

Hello again Marius,

Regards,
Charlie P.

Hello Marius,

(1) Non-Optimal Routes

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.

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

(2) Route Reply Loss

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 cycle in the network.
I am confident that there is a better solution, and I will work on finding
and specifying it.

(3) Route Request Loss

--

Regards,

Charlie P.

--

Regards,

Charlie P.

---

From: "Charles E. Perkins" <[email-masked]>
Date: Sun, 30 Dec 2012 14:40:21 -0800

Hello folks,

As noted by Marius Portmann et al., there are some subtleties about
using sequence numbers to inhibit dissemination of possibly
outdated RREQ and RREP messages.  After reconsidering this
matter for the last couple of weeks, I realized that the existing
specification does not properly handle suppression of duplicate
multicast messages.  In order to accomplish that, while still
not suppressing earlier multicast messages that do need to be
transmitted, a list of previously retransmitted multicast AODVv2
routing messages needs to be maintained, as suggested by Marius.

Here is some proposed text for that purpose:

Two incoming RREQ messages should be considered the "same" if
they have the same Sequence Number and were generated by the same
AODVv2 router.  Using that notion of equivalence, when RREQ messages
are multicast in a MANET, a node may well receive the same RREQ from
more than one of its neighbors.  Such duplicated RREQs SHOULD NOT
be retransmitted; otherwise, a great deal of unnecessary signaling
traffic is likely to be generated in the network as multicast RREQs
are retransmitted over and over again with practically no additional
benefit.

To avoid unnecessary retransmission of duplicate RREQ messages,
while still enabling the proper handling of earlier RREQ messages
that may have somehow been delayed in the network, it is needed
for each AODVv2 router to keep a list of the RREQ messages which
it has recently retransmitted.

The same duplicate suppression is needed for other AODVv2 messages.
For instance, when optional multicast RREP is used to enable selection
from among multiple possible return routes, similar measures need to
be taken.

For this reason, the table is more generally called the AODVv2
Duplicate Suppression Table; it is simply a list of the AODVv2 RREQ
and RREP messages which have been recently multicast, using
the above notion of message equivalence.  More formally, two
AODVv2 RREQ messages are equivalent if:
- they were generated by the same AODVv2 router (RREQ_gen)
- RREQ_Gen assigned the same Sequence Number to its
   routing information in the RREQs
- the RREQs are for the same desired destination address
An analogous definition applies for a RREP message, in case that
the RREP message would be multicast.

Protocol handling of RERR messages eliminates the need for
tracking RERR messages, since the rules for retransmitting RERR
multicast messages prevent the phenomenon of message duplication
(that can affect RREQ and RREP retransmission).

As a historical note, AODV and early versions of DYMO contained
a similar broadcast suppression mechanism.  Prior to initiating the
conversion to RFC 5444 compliance, Ian and I had thought that the
underlying multicast optimization <via SMF> would do a better
job of duplicate suppression, and in a manner already integrated
with the underlying forwarding mechanisms.  Thanks, Marius et al.
for triggering a re-examination of this issue which has needed
attention since the RFC 5444 compliance changes.

On 12/13/2012 6:09 PM, Marius Portmann wrote:
> ....................
> ................

> Our analysis was based on DYMO/AODVv2 version 23. It now appears that 
> in version 24, the specification has changed such that it is similar 
> to what we are proposing, i.e. to let the AODVv2 routers always 
> forward the RREQ/RREP messages.
>
> All the best,
>

-- 
Regards,
Charlie P.

---

From: "Charles E. Perkins" <[email-masked]>
Date: Mon, 31 Dec 2012 16:06:14 -0800

Hello again folks,

During the process of writing down the specification for duplicate
suppression, various technical points became much more clear.
Consequently, the proposed mechanics of duplicate suppression
that I sent out yesterday requires some modification.

First, while it is true that suppressing message retransmission
has in the past been motivated mostly by broadcast RREQ, the
actual phenomenon applies equally well to unicast RREQ and
unicast RREP.  For example, if a target router receives RREQ and
would respond with RREP, then it must first check to see whether
the routing information in the RREP is more useful than from
a previous RREP sent in response to a comparable incoming RREQ.

Second, I reviewed the proposed concept of RteMsg "equivalence",
and it is far too fragile.  There are several worthy variations of
"message equivalence" that deserve consideration.  It turns out
that the algorithm can be expressed quite well with the much
weaker notion of "comparable" messages.  Two RREQ or RREP
messages are "comparable" if:
- they were generated by the same router, and
- they have the same OrigNode and TargNode addresses.
The algorithm proceeds by comparing a candidate outgoing
message "comparable" to previous messages to see whether
the candidate outgoing message should be "suppressed".

Third, the table of previously transmitted messages (renamed
to be "AODVv2 Transmitted RteMsg Table" -- or, simply "RteMsg
Table) is maintained so that no two entries are comparable.
This is easier than trying to compare a candidate outgoing
RREQ or RREP message against all comparable messages in
the RteMsg table -- if there were to be more than one such
comparable RteMsg table entry.

In the above, it's hard to know whether a message is a
"duplicate" without relying on a notion of "equivalence".
For that reason, the algorithm should no longer be called
"duplicate suppression".  I have renamed it to be "useless
message suppression".  It is, however, quite similar to the
duplicate broadcast suppression used long ago, but lost
during the transition to enable use of more general multicast
transmission infrastructures (and RFC 5444).

I am sure this is will all be clearer when I am able to exhibit
the text for the above data structure and algorithm in the
natural settings of the revised draft.

-- 
Regards,
Charlie P.