Subject: [manet] Incrementing Sequence numbers when not needed may yield non-optimal routes.

From: Peter Höfner <[email-masked]>
Date: Thu, 10 Jan 2013 18:26:41 +1100

While analysing AODVv2 we came across a potential problem:
we can show that (at least in combination with intermediate route reply)
always incrementing sequence numbers when issuing a route reply can
lead to non-optimal routes.

A detailed example is given at
http://www.cse.unsw.edu.au/~rvg/non-opt_incSQN.pdf

The example does not use any unusual set-up (special topology, special
time of link breaks, etc); hence we think that this type of behaviour
can happen frequently.  However, we have not done any measurements.

Moreover, a similar example can occur without intermediate route
reply (when only the destination is allowed to answer); but that
scenario needs a dynamic topology or a message-loss during transmission.

A solution could be to only increment sequence numbers when needed.
More precisely, the sequence number of the destination node (generating the reply)
would be set as the maximum of the current sequence number of that node and the
incremented (by 1) sequence number from the received RREQ message.

Is there a problem with not incrementing sequence numbers all the time?

Cheers
Peter, Rob, Marius, Wee Lum

P.S. This mail may be relevant for ticket #6 in the MANET Trac system

________________________________

The information in this e-mail may be confidential and subject to legal professional privilege and/or copyright. National ICT Australia Limited accepts no liability for any damage caused by this email or its attachments.

---

From: Henning Rogge <[email-masked]>
Date: Thu, 10 Jan 2013 08:36:51 +0100

> Is there a problem with not incrementing sequence numbers all the time?

Just as a thought, maybe AODVv2 needs something like the ANSN in OLSRv2 
to have sequence numbers for message duplicate suppression and the ANSN 
to differentiate between different sets of data?

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: Abdussalam Baryun <[email-masked]>
Date: Thu, 10 Jan 2013 08:59:27 +0100

j node informs the the d node of such route otherwise how does the d
node know the route to the source s.

we don't forget that the cost of both routes are not equal,

AB

On 1/10/13, Peter Höfner <[email-masked]> wrote:
> The information in this e-mail may be confidential and subject to legal
> professional privilege and/or copyright. National ICT Australia Limited
> accepts no liability for any damage caused by this email or its
> attachments.
> _______________________________________________
> manet mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/manet
>

---

From: "Charles E. Perkins" <[email-masked]>
Date: Thu, 10 Jan 2013 09:59:34 -0800

Hello Peter and all,

It is well known that reactive protocols can yield non-optimal routes.
I agree with your scenario that iRREP has even more such cases that
can produce non-optimal routes.  Thanks for showing the example.

To answer your question directly:

Yes, it is possible to design RREP so that incrementing sequence
numbers is not always possible.  And, in fact, that was done in earlier
versions of DYMO.  But I was not 100% certain that the design was
always an improvement, and it is really important to guarantee that
stale RREPs cannot cause loops.

Plus, the current design is easy to understand and implement.
Given earlier concerns about readability, preferring simpler designs
has been an important goal for me.

I am certainly open to improving the design of the sequence number
incrementation, and if you have a proposal please do share it with
the mailing list.  If I were to make a proposal along these lines, I
would specify that the AODVv2 router generating the RREP SHOULD
NOT increment its sequence number unless either (i) its route table
has been updated with new destinations or metrics, or (ii) its
neighborhood has changed.   Even that relatively loose constraint
could probably be relaxed further with additional record-keeping.

My understanding from previous work is that the degree of
non-optimality (sometimes called the "stretch factor") is small
on average, statistically speaking.  I think it's typically under 10%,
but this depends on numerous factors.  If you have details about
any statistics you may have gathered on this point, please share!

Regards,
Charlie P.

-- 
Regards,
Charlie P.

---

From: "Charles E. Perkins" <[email-masked]>
Date: Thu, 10 Jan 2013 10:50:06 -0800

Hello folks,

I made a confusing typo in my previous email.

I said <emphasis added>:
> numbers is not always *possible*.

I should have said:
    Yes, it is possible to design RREP so that incrementing sequence
numbers is not always *required*.

Please excuse the mistake.

Regards,
Charlie P.

On 1/10/2013 9:59 AM, Charles E. Perkins wrote:
>> The information in this e-mail may be confidential and subject to 
>> legal professional privilege and/or copyright. National ICT Australia 
>> Limited accepts no liability for any damage caused by this email or 
>> its attachments.

-- 
Regards,
Charlie P.

---

From: Abdussalam Baryun <[email-masked]>
Date: Thu, 10 Jan 2013 20:08:32 +0100

Hi Peter and Charlie,

I don't think that a design for not incrementing SN is a better
approach, and don't think the example scenarios problem was caused by
the increment. The increment of SN was needed in the example. The
problem was that the source updated its route twice. I don't think it
was needed to update route while the cost was less, just ignore such
RREP and choose better option.

AB

---

From: Abdussalam Baryun <[email-masked]>
Date: Thu, 10 Jan 2013 20:20:54 +0100

In other words, if we take the subject question, as;

When the increment SN not needed, then the source node will ignore
such increment (because not needed), then the source will not update
its route, from the example given, therefore, will still take optimum
route.

AB

---

From: "Charles E. Perkins" <[email-masked]>
Date: Thu, 10 Jan 2013 11:37:14 -0800

Hello Abdussalam,

Current design requires that the route update with the most
recent Sequence Number is required to be used.  How can
one ignore such an RREP?

Or perhaps I am misunderstanding your suggestion...?

Any such proposal has to be considered from the standpoint
of trading off route optimality versus volume of signaling
(while maintaining loop-freedom).

Regards,
Charlie P.

-- 
Regards,
Charlie P.

---

From: Abdussalam Baryun <[email-masked]>
Date: Thu, 10 Jan 2013 22:19:34 +0100

Hello Charlie,

I agree with current design. Regarding the example or proposal of
subject, I want it to be required route update while required
increment SN, and if not required increment then may not required
update.

Please advise if make sense, if not then maybe I will need to run test,

AB

---

From: <[email-masked]>
Date: Thu, 10 Jan 2013 22:01:27 +0000

Peter,

In your diagram (c), node j does not increment its sequence number for d.
Intermediate RREP (iRREP) follow draft-perkins-irrep, not
draft-ietf-manet-dymo.  It would be a bad thing for a node to have an
active route with a sequence number higher than the destination's own
seqnum.  All active paths must be well-ordered according to 5.2.1.

Also, node j, according to draft-perkins-irrep, should send a uRREP to d
in addition to the iRREP to s.  This would build a shortest-path d->j->s
reverse path that would not be overridden by the s->i->Š->d rreq.  One
would end up with an asymmetric route.  I believe that in an AODV-style
network, the destination should always increment its seqnum if they are
equal.  Otherwise, you might frequently end up violating 5.2.1(2) and have
to drop the RREP.

One typically uses an expanding ring search to try and find a near by
intermediate node with a valid route.  The size of the expanding ring
search will influence the amount of route stretch.  If the nearby search
fails, you're probably better off doing a destination-only rreq than
flooding the whole network with an anybody-can-reply rreq.  In your
example, if node s had node a TTL=3 RREQ before doing a destination-only
RREQ, it would have calculated the correct shortest path s->j->d.  If it
had done a TTL=4 RREQ, it would have found the longer path s->i->Š->d and
be happy with the slack because it asked for it.

The observation that incrementing sequence numbers prior to RREQ causes
inefficient pathfinding is an old issue.  The paper, for instance, "A new
approach to on-demand loop-free routing in ad hoc networks"
(Garcia-Luna-Aceves, Mosko, Perkins, 2003)
[http://dl.acm.org/citation.cfm?id=872043] is based on the observation
that increasing the sequence number essentially invalidates your
successors and results in the destination being the only node that can
reply.  In this paper, the sequence number is used as a last-resort reset
to paths.  As per your example, the destination only increases its
sequence number if the RREQ carried the current sequence number, so in
your case d would not increment because the RREQ along the s->i->Š->d path
carried seqnum 1 and d was was seqnum 2.  Therefore, the RREPs at s would
both be seqnum 2 and s would use the shorter path.

Marc Mosko

---

From: Abdussalam Baryun <[email-masked]>
Date: Fri, 11 Jan 2013 01:15:58 +0100

Hi

Yes I agree, I also think that the use in the example of  iRREP while
it is optional in AODVv2, so by default the draft-25 only RREP
generated by d.

if you think statement not correct please advise,

AB

---

From: Peter Höfner <[email-masked]>
Date: Fri, 11 Jan 2013 19:04:17 +1100

Dear Abdussalam,

> node know the route to the source s.

You are right; in our example we didn't take into account the uRREP
that j sends to d. Hence that example would not occur in the current
version of AODVv2. In fact, $d$ would send a RREP via $j$.

We have another example however where no RREP by an intermediate
node is involved. It is presented at
http://www.cse.unsw.edu.au/~rvg/non-opt_incSQN2.pdf

In that example, node D incrementing its own sequence number leads to
a sub-optimal route to D by A. Naturally, sub-optimal route can occur
all the time, but this is an example where we are worse off as a direct
consequence of D incrementing its own sequence number when issuing a RREP.

Does one of you know of an example where the destination incrementing
its own sequence number (other than a RREQ induced increment) has any
advantages? If so, one could try to analyse which problem is more
prevalent, and hence which incrementation strategy is best.

Here, with a "RREQ induced increment" we mean that if the RREQ lists a
destination sequence number of n, indicating that n might be the latest
one that stopped working for the source of the request, then the
destination must increment its own sequence number to at least n+1.

Cheers,
Peter, Rob, Marius and Wee Lum

---

From: Peter Höfner <[email-masked]>
Date: Fri, 11 Jan 2013 19:10:29 +1100

Hi Charlie,

> numbers is not always required.  And, in fact, that was done in earlier

Our team develops mathematical techniques to formally analyse protocols;
by this we can for example show the loop-freedom of protocols.
We have already applied these techniques to several variants of
the AODV protocol.
When the AODVv2 draft is sufficiently stable, we might
apply those techniques to the proposed protocol, so that we can in
fact guarantee that stale RREPs cannot cause loops.
This task does take some time, as it involves translating the
protocol specification into a formal (unambiguous) specification language.

> could probably be relaxed further with additional record-keeping.

Is it possible to sketch an example where restrictions (i) and (ii) are
needed? This may help us working out a proposal on this point.

Regards,

---

From: Peter Höfner <[email-masked]>
Date: Fri, 11 Jan 2013 19:20:35 +1100

Dear Marc,

> seqnum.  All active paths must be well-ordered according to 5.2.1.

That's right, in our diagram (c), node j does not increment its
sequence number for d when generating an iRREP: it was 2 and remains 2.
We believe this follows the specification.

In our diagram (c) node j updates its own sequence number from 2 to 3,
when issuing the iRREP. We do not know if it is the intention of AODVv2
that this happens or not, but it makes no difference in our example.

> reverse path that would not be overridden by the s->i->#->d rreq.  One
> would end up with an asymmetric route.

Thanks for pointing out. We therefore made a
different example (see our previous posting) that doesn't involve iRREPs.

> ... As per your example, the destination only increases its
> your case d would not increment because the RREQ along the s->i->#->d path

You are right; we agree with you that d should not increment its sequence number in
this situation. However, the current draft of AODVv2 (as we understand it) does
increment the sequence number of d.

Cheers,

---

From: Abdussalam Baryun <[email-masked]>
Date: Fri, 11 Jan 2013 11:24:00 +0100

Hi Peter,

The new example now suggests topology change which always happens in
MANET but don't know why you broadcast twice from A, if A sends a RREQ
then if a new topology comes it will not send again. Only if the
neighbors change is before the sending of intermediate nodes.

if I mis-understood please advise,

AB

---

From: Abdussalam Baryun <[email-masked]>
Date: Fri, 11 Jan 2013 11:42:42 +0100

> increment the sequence number of d.

The current draft does not increment SN twice when it receives two
similar new RREQ. However, there may rare occur possibility of
non-optimal in theory, but may be it is not non-optimal in practice,
because the network topology is dynamic so you never know what will be
the next topology. Therefore, under MANET the current draft AODVv2
gets to the optimal routes more frequent.

AB

---

From: Abdussalam Baryun <[email-masked]>
Date: Sat, 19 Jan 2013 05:54:14 +0100

Hi Peter, and All,

I don't think increment is not needed, but we should not update in
some conditions. My posts before that considered example [1] takes the
node A sending twice RREQ. Another understanding of [1], if we
consider that we have two originators S and A that originate RREQ1 and
RREQ2 respectivily. Then DYMO router A will not update its route to D
when it receives the later reply RREP1 as you described in last
paragraph in [1] or in your papers.

For DYMO-25, if we follow the specification to update we get to
check-step 3 in the section 6.1, so no route update recommended.

For LOADng router ( I may be wrong because still not read fully) may
have the non-optimal problem, and node A updates route as per section
11.2 process step 8. I RECOMMEND the amendment as step conditions in
DYMO, to check if the metric cost is larger with the sequence check.

However, for LOADng, it may not get the problem only in very few
situations, because the scenarios of example [1] assumes conditions of
three sequence events
as 1) node S request RREQ1 to D, 2) node A will request RREQ2 to D
also only between the time start after topology chang, and after
forward RREQ1 and ends before receiving RREP1 and  3) there is a long
time between sending RREQ1 and receiving RREP1 as that RREP2 gets to A
befor RREP1. These events makes the example special case and low
possibility in a network, because usually route discovery have small
time delay, and chance to have two requests at different time less
than discovery.

[1] http://www.cse.unsw.edu.au/~rvg/non-opt_incSQN2.pdf

Please provide me with your thoughts :)

Regards

Abdussalam Baryun
University of Glamorgan, UK

++++++++++++++++++++++++++++++++++++++++++++++++++++