Subject: [manet] Rollover in AODV, Draft 11.

From: "Mullen, John P. (Contractor)" <[email-masked]>
Date: Fri, 12 Jul 2002 10:07:04 -0600

Hi,

I understand that this topic has been discussed before, but I believe there
is a potential glitch in the manner in which sequence number rollovers are
detected in Draft 11 of AODV.  I also have a very simple solution.

The problem is that if the current counter value is very large and the
stored copy is very small, the result of a 2's complement subtraction will
falsely indicate that rollover has occurred.  For example, if the current
counter value is 4294967200 and the stored copy is 200, the result of a 2's
complement subtraction will cause the unsigned difference of 4294967000 to
be misinterpreted as -296, which according to the middle paragraph on page
10 of draft 11, would falsely indicate rollover has occurred.  A similar
problem exists in that if the current value is very small (say 200) and the
stored value very large (say 4294967200), the difference will be
misinterpreted as a positive number (296 in this case) and the code will
assume no rollover has taken place.

Now, it is unlikely that such a difference would come up, but as Murphy
would say, it is always best to assume that a potential problem will someday
be realized.  Also, in this case, there is an easy fix.

Instead of using 2's complement subtraction, I would recommend that one
simply do a logical comparison.  If the current and stored counters are
properly typed as long unsigned integers, the logical test will reliably
indicate whether the stored value is larger than the current value,
indicating rollover.  Moreover, since this is a hardware operation, the
logic test will execute much more rapidly and require less object code than
the subtraction and subsequent sign test.

To check this out, I've written a simple C++ program to show what happens
for different values of the sequence number and stored values.  If anyone is
interested, I can send it to them.

John P. Mullen,  Ph.D.
Contractor at TRAC/WSMR while on sabbatical from New Mexico State University

Mail to:
    Director
    USATRAC-WSMR
    Attn: ATRC-WBC (John Mullen)
    White Sands Missile Range, NM  88002-5502

Phone:  
    (505) 678-5275
    DSN 258-5275

After 12/31/02
   Tel: (505) 646-2958
   Email: [email-masked]

_______________________________________________
manet mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/manet

---

From: Chip Elliott <[email-masked]>
Date: Fri, 12 Jul 2002 14:28:19 -0400

Just a quick note that there's "the usual way" of handling
sequence numbers and rollover, which is used in OSPF,
IS-IS, and so forth. I think this way should also be used
in the MANET protocols, because other ways have
various odd failure modes.

Radia Perlman's "Interconnections" book, pp 216-219,
describes the time the ARPANET failed spectacularly
due to a flipped bit in the memory of one of the routers.
It accidently made it so that 3 different sequence numbers
were all "less than" each other, ie, A < B < C < A. As she
points out, once a network gets into such a state, there is
no way for it to recover.

(The next section in her book describe's today's scheme
as used in OSPF etc, with rationale. She's talking link
state but the same basic issues arise in reactive protocols.)

If we're going to use a "not so good" sequence number
scheme, this should be a conscious decision and should be
discussed as such in the document. I have no particular
axe to grind here, just to point out there's been a lot
of rather subtle thought in this area already.

cheers,

-- Chip

---

From: Chip Elliott <[email-masked]>
Date: Fri, 12 Jul 2002 14:28:19 -0400

cheers,

-- Chip