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.
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.
But since this amount of separation would indicate something bigger went wrong, this is fine...? Does that need explaining?
On Wed, Sep 23, 2015 at 7:09 PM, Charlie Perkins <charles.perkins@xxxxxxxxxxxxx <mailto: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.
