Subject: Re: [manet] Duplicate suppression for RREQ and RREP -- Problem and Proposed Solutions

From: Abdussalam Baryun <[email-masked]>
Date: Tue, 1 Jan 2013 09:29:21 +0100

Thanks for the update. Does the proposal also mean that AODVv2 will
not need to use SMF for MANET multicast?

AB

On 12/30/12, Charles E. Perkins <[email-masked]> wrote:
> 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:
>>
>> Hi Charlie,
>>
>> ....................
>>
>> >> (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.
>>
>> ................
>
>> > 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.
>>
>> 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,
>>
>> Rob, Peter, Marius and Wee Lum
>>
>>
>
> --
> Regards,
> Charlie P.
>
>

---

From: "Charles E. Perkins" <[email-masked]>
Date: Thu, 03 Jan 2013 16:44:16 -0800

Hello Abdussalam,

AODVv2 should still use SMF techniques to build a reduced
forwarding tree for the multicast messages.  But it will work
just fine with brute force forwarding.

Regards,
Charlie P.

-- 
Regards,
Charlie P.

---

From: Henning Rogge <[email-masked]>
Date: Mon, 7 Jan 2013 10:28:46 +0100

Back from vacation...

On 12/30/2012 11:40 PM, Charles E. Perkins wrote:
> outdated RREQ and RREP messages.

 > .....

Its good that we are looking into this issue.

> attention since the RFC 5444 compliance changes.

Not sure SMF would apply to all of AODV anyways. SMF is for flooding a 
message over the whole MANET, but some AODV messages are modified for 
each hop.

Henning Rogge

-- 
Diplom-Informatiker Henning Rogge , Fraunhofer-Institut für
Kommunikation, Informationsverarbeitung und Ergonomie FKIE
Kommunikationssysteme (KOM)
Fraunhofer Straße 20, 53343 Wachtberg, Germany
Telefon +49 228 9435-961,   Fax +49 228 9435 685
mailto:[email-masked] http://www.fkie.fraunhofer.de

---

From: "Charles E. Perkins" <[email-masked]>
Date: Mon, 07 Jan 2013 09:10:47 -0800

Hello Henning,

> message over the whole MANET, but some AODV messages are modified for 

My conclusion is that SMF-based duplicate detection basically does not
apply, and to make it apply would require some really extensive changes
to AODVv2.

However, the techniques for building a multicast backbone do apply.
If needed, I could write another document detailing the integration
of dominating-set maintenance with AODVv2.  It could be done without
any changes, or (alternatively) there could be integration with RERR
functions.

-- 
Regards,
Charlie P.

---

From: Henning Rogge <[email-masked]>
Date: Tue, 8 Jan 2013 07:25:05 +0100

> any changes, or (alternatively) there could be integration with RERR

Yes, the MPR-based flooding could work for AODV too, as long as you do 
not expect the intermediate nodes to change the messages (except for 
hopcount/hoplimit).

But wouldn't this mean you need to run a proactive neighbor discovery 
like NHDP ?

Henning Rogge

---

From: Marius Portmann <[email-masked]>
Date: Thu, 10 Jan 2013 07:26:16 +0000

Hi Charlie,

Thanks for your reply.  The latest draft of the AODVv2 appears to solve the problem of loss of RREQ and RREP messages we raised.

With this solution in place, there appears to be no further need to increment a node's sequence number when it issues a route reply (unless needed to match the sequences number requested in the received RREQ message). In fact, we think that the policy of ALWAYS incrementing a node's sequence number when it initiates a route reply can lead to non-optimal routes. We will post the details in a separate email.

cheers

Marius, Rob, Peter, Wee Lum

From: Charles E. Perkins [mailto:[email-masked]]
Sent: Monday, 31 December 2012 8:40 AM
To: Marius Portmann
Cc: [email-masked]'
Subject: Duplicate suppression for RREQ and RREP -- Problem and Proposed Solutions

Hello folks,

....................

>> AODV can lose route replies (http://www.ietf.org/mail-archive/web/manet/current/msg05702.html).

................

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

--

Regards,

Charlie P.