[aodvv2-discuss] Re: [manet] AODVv2 comments

  • From: Victoria Mercieca <vmercieca0@xxxxxxxxx>
  • To: aodvv2-discuss@xxxxxxxxxxxxx
  • Date: Tue, 6 Oct 2015 19:27:11 +0100

Hi Charlie,
Comment in line...

On 6 Oct 2015 5:31 pm, "Charlie Perkins" <charles.perkins@xxxxxxxxxxxxx>
wrote:


Hello Vicky,


On 10/6/2015 5:25 AM, Victoria Mercieca wrote:

Hi all,

Bit slow on catching up with this one...

The text now says:

An AODVv2 router can only attach its own sequence number to information
about a
route to one of its configured router clients. All route messages
regenerated by
other routers retain the originator's sequence number. Therefore, when
two pieces
of information about a route are received, they both contain a sequence
number
from the originating router. Comparing the sequence number will identify
which
information is stale. The currently stored sequence number is subtracted
from the
incoming sequence number. The result of the subtraction is to be
interpreted as a
signed 16-bit integer, and if less than zero, then the information in
the AODVv2
message is stale and MUST be discarded.


I think this text can be interpreted correctly. Somewhere there has to
be text that
embodies the short "Newer()" algorithm below.



Does that address Chris Dearlove's comments?

As far as I understand the discussion, if seqnums differ by half the
range or more then the message is considered stale, even if the incoming
one is greater than the current one.


In any modular arithmetic, "greater than" is ambiguous. The matter has
to be settled
somehow, and interpreting the result of subtraction as a signed number
does a nice job.


But since this amount of separation would indicate something bigger went
wrong, this is fine...? Does that need explaining?


I don't understand this question.


My point here was that if the seqnums differ by 128 in the 8bit examples,
ie half the range of the seqnum, then the subtraction and interpretation of
the result says we should discard the info. But if seqnums differ by this
much anyway it probably means something wrong has happened...? So it's OK
that the info gets discarded...?

Regards,
Vicky.

Regards,
Charlie P.




On Wed, Sep 23, 2015 at 7:09 PM, Charlie Perkins <
charles.perkins@xxxxxxxxxxxxx> wrote:

Hello folks,

The basic idea is to subtract the sequence numbers, say X = (S1 - S2).
If X is negative, S1 is older than S2; for this sentence to make sense, X
has to be a signed integer. It doesn't matter whether you consider S1 and
S2 as signed, but in our case they are unsigned.

As discussed below, zero is a special case for S1 or S2. That could be
noted in the algorithm. So:
Newer(S1,S2) returns TRUE if S1 > S2, where '>' means "newer".

Newer (S1, S2)
unsigned int S1, S2;
{
int X;

if (0 == S1) return (FALSE);
else if (0 == S2) return (TRUE);
else if (0 < (X = (S1 - S2))) return (FALSE);
else return (TRUE);
}

I think that this implementation is pretty natural given the current
specification. If both S1 and S2 are zero, then this code pretends that S1
is newer, but that case does not happen with the current protocol signaling.

Follow-up below...

On 9/21/2015 2:52 AM, Dearlove, Christopher (UK) wrote:


Let’s take a simple case, current stored 128, incoming 129. We can’t
use signed 8 bit arithmetic unless those are signed 8 bit values, so I
assume (this should be clearer) that means we assume that the current
stored is -128, the incoming is -127, we subtract current from incoming
i.e. -127 - -128 = 1. Which is not less than zero, we don’t discard, as
expected. OK.


Here Chris seems to be confused by the word "use". To be more precise,
we should say that the result of the subtraction of the unsigned numbers is
to be interpreted as a signed integer.



Now let’s try current 127, incoming 128 (-128). Now we have -128 – 127
which is 1, but only if we assume signed arithmetic wraps. Signed
arithmetic does wrap on most processors, but if for example you were coding
that in C, that’s actually explicitly not defined by the standard. This
isn’t C, but at the least the text needs to mention wrapping. (Unsigned
arithmetic is guaranteed to wrap in C, and mathematically it’s more easily
defined, which is why that’s generally preferable.)


Ask for a citation. I'm skeptical of the claim anyway, but it won't
hurt to be more precise.




OK, now let’s try current 64, incoming 192 (-64). Now we have -64 -64
= -128. That’s negative, so we discard. As we should, the separation is
128, more than half of the 255 range.



But try current 192 (-64), incoming 64. Now we have 64 - -64 = -128
(with wrapping). Which is negative, so we discard. But given that 0 is
ignored, the wraparound from 192 to 64 is actually only 127, less than half
of 255, so we shouldn’t discard.



OK, that’s a bit of a corner case, frankly by the time you are that
separated it’s pretty clear something has gone wrong, so in practice it
doesn’t matter. But then actually something pretty similar applies to
smaller separations 127, 126, …



(In OLSRv2 we have no 0 omitted, so we have an actual ambiguity over
the half range separation, which we just decided to say do what you like. I
think we did discuss introducing a parameterisable separation that if
exceeded meant something was wrong and you should … what? As we didn’t have
an answer for that, that idea went nowhere.)



So in summary (a) this really needs a clearer explanation, (b) it
needs to say overflow means wrap, (c) it would be technically better to
write using unsigned arithmetic, (d) this gets a corner case wrong, though
that probably doesn’t matter in practice (because of which I’m going to
make no attempt to write a corner case correct version).


The business about the corner claim could be considered, but the
situation is even less relevant than what Chris notes.

Basically, if we have packets from the same AODVv2 router floating
around the system that have sequence numbers separated by 10,000, I think
it will be the case that we have entered the twilight zone, or else
someone's faulty AODVv2 implementation is simply issuing random sequence
numbers. Never mind being separated by 32767.

Regards,
Charlie P.




Other related posts:

  1. Home
  2. aodvv2-discuss
  3. Archive
  4. 10-2015