Subject: [manet] Hares technical question 1: Design of sequence numbers (warning long post)

From: "Susan Hares" <[email-masked]>
Date: Mon, 14 Jan 2013 00:03:28 -0500

Technical issue 1: Sequence numbers 

DYMO-25 Text: 

An AODVv2 Sequence Number is an unsigned integer maintained by each AODVv2
router.  This sequence number guarantees the temporal order of routing
information to maintain loop-free routes.  The value zero (0) is reserved to
indicate that the SeqNum for a destination address is unknown.

Question text:  

In a monotonically increasing sequence number you have three issues:

1 - unique sequence linkage to node/port/update(e.g. LSA) 

2 - sequence number wrap

3 - when to sequence number increment. 

The delightful thread started a concrete discussion on sequence number
incrementing at the RREPLY node. However, I have not notice on the recent
thread the discussion of the other issues so I will start with questions
about these issues. 

#1 - unique node - sequence number linkage 

>From the DYMO text, the sequence number is monotonically increases per node
address. If you lose the node address-sequence number link, it appears that
this linkage is broken. This true of any sending of sequence (RREQ, RREP). 

If you do not lose the unique linkage, then you must consider that an
immediately previous sequence number in a RREQ or RREP is out of date.  In
the example in file non-opt_incSQN2.ppt, my question to Peter is if you know
the packet comes for A and has an old sequence number in (f), you have the
appropriate information (path 1: S-A-D, xmt node A, seq 1) and (path 2:
s-A-I-D xmt A, seq 1).  

Q1: How is the unique node address selected?  Did the WG group have a
security/theoretical discussion on using the loopback IP address versus
other addresses? (e.g. DOS on loopback addresses) If you can point to an
archive discussion, I'm glad to go read it. I would expect that the sharp
minds in this WG would have debated these points. 

[Please note I have tried to state this question to get at the theory behind
any selection of unique node - sequence number linkage - rather than DYMO
versus LOADng question.  I'm glad to learn from DYMO or LOADng text, but I'm
trying to see the theory]. 

#2 Sequence numbers always wrap and sequence number reuse depends on the
time and/or wrap detection. 

Formats usually do not impose a particular wrap value.  Common values are
zero or all ones (-1) to aid quick identification of the wrap.  It is not
surprising therefore that: 

a) Loadng - uses a simple number format with -1 was wrap value 

INMU (in my understanding)  wrap goes -2, 0       

b) Dymo - uses a TLV format with 0 as both initial number and wrap. 

      INMU - the wrap goes -1, 1

Sequence number time is usually 2* the wrap time so junk can clear from the
network. Therefore the equation is: 

MAX_SEQ_LIFETIME = 2 * normal_wrap_time

Distance vector routes may encounter route cycling (count to infinity in
RIP, BGP MED harmful/BGP flapping) in certain topologies. Rapidly changing
mobile topologies may cycle through topologies that do and do not cause this
route fluctuation.  The validity timer and max-sequence timer seems to be
addressing this issue. 

Q2: Am I correct? 

The timers in DYMO-24 are: 

              +------------------------------+-------------+
              |             Name             |    Value    |
              +------------------------------+-------------+
              |        ACTIVE_INTERVAL       |   5 second  |
              |         MAX_IDLETIME         | 200 seconds |
              |      MAX_SEQNUM_LIFETIME     | 300 seconds |
              |     ROUTE_RREQ_WAIT_TIME     |  2 seconds  |
              | UNICAST_MESSAGE_SENT_TIMEOUT |   1 second  |
              |      RREQ_HOLDDOWN_TIME      |  10 seconds |

---------------------------------------------

Here's my set of equations: 

Validity timer ::=max time before route declared invalid 

               = ACTIVE_INTERNAL + MAX_IDLETIME -
(Current_time-Routelast.used)

Expired route ::=  route expired, but sequence number cannot be used

              :: = valid_time < expired route < MAX_SEQNUM_TIME

Q3: Can you correct these equations or add to them? 

Architecture questions: 

1. How does MAX_SEQNUM_TIME interact with the real wrapping functions during
fast node motion to slow node motion so that links come and go (per 2c of
Gabblek, Hofner, Portman and Tan's diagram (non-opt_incSQN2.pdf) 

      As a note to Gabblek et al. (2013), you may want to examine IEEE
Sensor conference papers on this topic. 

2.  What conditions cause all nodes to engage in a sequence number wrap?
For example, would fast mobility of nodes with fast link breakage cause
these problems?

3.  One important issue is the restart of things after power loss or reboot
(likely from software errors).  Does the node going down require that a
sequence number to be maintained in NVRAM?  

4. Is there a reason for the Address Block TLV route passed through to time
out different that the originating node? If so, does (or does it not) impact
the sequence number wrap. 

Thank you for aid in helping me come up to speed on your past discussion,
and current thought. 

Sue Hares

---

From: Henning Rogge <[email-masked]>
Date: Mon, 14 Jan 2013 08:15:10 +0100

On 01/14/2013 06:03 AM, Susan Hares wrote:
> a)Loadng – uses a simple number format with -1 was wrap value
>

I think you are wrong in this... Loadng goes -1, 0, 1 without any gap. 
Similar to OLSRv1 and OLSRv2.

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: Mon, 14 Jan 2013 12:44:18 +0100

Hi Sue,

Thanks for discussion, I am not claver but will try my best to answer,
comments in line;

> indicate that the SeqNum for a destination address is unknown.

correct, similar in both AODVv2 and LOADng,

> this linkage is broken. This true of any sending of sequence (RREQ, RREP).

the above paragraph uses the words *you-lose* as dymo-router or not sure !!!

IMO, not exactly broken, but the destination Sequence Number (SN) is
invalid, because the route is active. The link considered broken only
if route is invalid. If a node loses it's own SN then all links are
broken.

> minds in this WG would have debated these points.

I don't think there are discussion in this issue, not sure :(
> INMU (in my understanding)  wrap goes -2, 0

LOADng SHOULD go -1, 0, 1, but still not followed through the
document, I'll leave/wait the authors to answer,
>       INMU - the wrap goes -1, 1

me too,

> MAX_SEQ_LIFETIME = 2 * normal_wrap_time

IMHO, I think;

 MAX_SEQ_LIFETIME < normal_wrap_time

> route fluctuation.  The validity timer and max-sequence timer seems to be

its also max-seq addresses the problem of losing SN as mentioned in
draft-dymo-25, and validitytime addresses the RFC5497 issues.

> The timers in DYMO-24 are:

this timer is flexible depends on the originator of such TLV, see RFC5497
>               :: = valid_time < expired route < MAX_SEQNUM_TIME

I don't want to mix the information, but I think draft-dymo-25 has
specified the conditions,

> Q3: Can you correct these equations or add to them?
IMHO, I don't think we SHOULD follow equations, but the use-case,
where it always will depend on the netwok parameters.
> For example, would fast mobility of nodes with fast link breakage cause

not sure what is the problem here, but yes while breaks are frequent
the wrap will become,
> sequence number to be maintained in NVRAM?

this is mentioned in draft-dymo-25, yes it requires storage,
> the sequence number wrap.

It should not time out before the origin, and specified by origin. It
is not related to wrap of SN.
> Thank you for aid in helping me come up to speed on your past discussion,

Thanks to you too,

AB

---

From: Henning Rogge <[email-masked]>
Date: Mon, 14 Jan 2013 13:42:39 +0100

> correct, similar in both AODVv2 and LOADng,

I don't think LOADng use a "magic number" within the sequence numbers. 0 
has no special meaning as a sequence number for LOADng.

Henning Rogge

---

From: "Susan Hares" <[email-masked]>
Date: Mon, 14 Jan 2013 09:19:20 -0500

Henning:

Thank you for the quick response.  Below I have the text sections from 

http://www.ietf.org/id/draft-clausen-lln-loadng-08.txt

How should I interpret this text?  Your comment is 

-1 (0xFFFF), 0, 1  

How does it work?  

Let us assume S1 rotates through MAX_VALUE
(0xFFFF, 0, 1) , and S2 stays at 0xCFFF. 

The sequence numbers are broken in half so MAX_VALUE/2 = 0x7FFF 
Step 1;  If S1= 0xFFFF and S2 = 0xCFFF
S1-S2 = 0x3000, and less than 0x7FFF - therefore S1 is > S2

Step 2: If S1=0x0000 and S2 = 0xCFFF, S1-S2 = 0x3001, therefore s1 is > S2
Step 3:  If S1 = 0x7FFF and S2 = 0xCFFF, S2-S1 = 0x5000 > 0x3FFF 
Step 4:  If S1 = 0xCFFF and S2 = 0xCFFF  S1-S2 = 0 , and no case follows

How do you know it wrapped and hit the previous value?  

Am I missing something in the LOADng text?  Or is the text missing
something? 

Sue 

------------------

In section 8 it says: 

  Each LOADng Router maintains a single sequence number, which must be
   included in each RREQ or RREP message it generates.  Each LOADng
   Router MUST make sure that no two messages (both RREQ and RREP) are
   generated with the same sequence number, and MUST generate sequence
   numbers such that these are monotonically increasing.  This sequence
   number is used as freshness information for when comparing routes to
   the LOADng Router having generated the message.

   However, with a limited number of bits for representing sequence
   numbers, wrap-around (that the sequence number is incremented from
   the maximum possible value to zero) can occur.  To prevent this from
   interfering with the operation of the protocol, the following MUST be
   observed.  The term MAXVALUE designates in the following the largest
   possible value for a sequence number.  The sequence number S1 is said
   to be "greater than" (denoted '>') the sequence number S2 if:

      S2 < S1 AND S1 - S2 <= MAXVALUE/2 OR
      S1 < S2 AND S2 - S1 > MAXVALUE/2

And on page 46

   |    RREQ.seq-num   |   <msg-seq-num>   | 16 bits, hence MAXVALUE   |
   |                                   |
| (Section 8) is 65535.  

The Hex value for 66535 is 0xFFFF. 

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of
Henning Rogge
Sent: Monday, January 14, 2013 2:15 AM
To: [email-masked]
Subject: Re: [manet] Hares technical question 1: Design of sequence numbers
(warning long post)

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: Henning Rogge <[email-masked]>
Date: Mon, 14 Jan 2013 15:22:40 +0100

On 01/14/2013 03:19 PM, Susan Hares wrote:
>> a)Loadng - uses a simple number format with -1 was wrap value
>>

I think section 8 of the LOADng draft answers your question.

Henning Rogge

---

From: "Susan Hares" <[email-masked]>
Date: Mon, 14 Jan 2013 09:36:13 -0500

Henning:

Thank you for clarifying this.  I did understand that from your first
message.  Please see that response. 

Sue 

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of
Henning Rogge
Sent: Monday, January 14, 2013 7:43 AM
To: [email-masked]
Subject: Re: [manet] Hares technical question 1: Design of sequence numbers
(warning long post)

On 01/14/2013 12:44 PM, Abdussalam Baryun wrote:
>> An AODVv2 Sequence Number is an unsigned integer maintained by each 
>> AODVv2 router.  This sequence number guarantees the temporal order of 
>> routing information to maintain loop-free routes.  The value zero (0) 
>> is reserved to indicate that the SeqNum for a destination address is 
>> unknown.
>

I don't think LOADng use a "magic number" within the sequence numbers. 0 has
no special meaning as a sequence number for LOADng.

Henning Rogge

---

From: "Susan Hares" <[email-masked]>
Date: Mon, 14 Jan 2013 09:41:12 -0500

Henning: 

Is section 8 only dealing with origination of sequence numbers?  How does
LOADng handle reception of the sequence I listed below? 

Assume some pesky broken MANET router keeps sending/forwarding a packet with
same origin and sequence number 0xCFFFF. 

Sue 
[Snip] 
> Am I missing something in the LOADng text?  Or is the text missing

[snip] 

Henning Rogge

---

From: Henning Rogge <[email-masked]>
Date: Mon, 14 Jan 2013 15:47:32 +0100

Sorry for not the bad answer to your first mail. See explanation below...

 >> The sequence number S1 is said to be "greater than" (denoted '>')
 >> the sequence number S2 if:

 >> S2 < S1 AND S1 - S2 <= MAXVALUE/2 OR S1 < S2 AND S2 - S1 > MAXVALUE/2

If this formula is "true", S1 is considered larger than S2.
If this formula is "false", S1 is considered to be smaller than S2.

Its a single boolean formula, no "two cases".

@Ulrich Herberg:

maybe the formula could be presented like this to make it more clear?

(S2 < S1 AND S1 - S2 <= MAXVALUE/2

     OR S1 < S2 AND S2 - S1 > MAXVALUE/2)

Henning Rogge

---

From: "Susan Hares" <[email-masked]>
Date: Mon, 14 Jan 2013 09:58:02 -0500

Henning:

The text might be clearer... but before we hack the text let's go through
"the rest of the story".

> Step 4:  If S1 = 0xCFFF and S2 = 0xCFFF  S1-S2 = 0 ==> The case is false. 

How does the LOADng go on to deal with the detection of the wrap that caused
a back packet to be rotting around in the network? 

What does the receiver do to decide things which packet is bad? The
originator thinks he's sending a perfectly valid packet.  The junk packet
has an aligning sequence number. 

Thanks, 

Sue 

-----Original Message-----
From: Henning Rogge [mailto:[email-masked]] 
Sent: Monday, January 14, 2013 9:48 AM
To: Susan Hares
Cc: [email-masked]; Ulrich Herberg
Subject: Re: [manet] Hares technical question 1: Design of sequence numbers
(warning long post)

@Ulrich Herberg:

Henning Rogge

---

From: Jiazi Yi <[email-masked]>
Date: Mon, 14 Jan 2013 16:07:14 +0100

Hi, 

I might miss something. 

in your step 4 (case 4?), it's just S1=S2, i.e. the same sequence number. Then the receiver will take it as the same message. 

You mean the sequence number runs so fast, and reaches the same value again? With 16 bits of sequence number of rfc5444, this is not likely to happen. Am I wrong?

@Henning: 

yes, we can consider changing the formula as you suggested to make it clearer. 

best

Jiazi

On Jan 14, 2013, at 3:58 PM, "Susan Hares" <[email-masked]> wrote:

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

---

From: Henning Rogge <[email-masked]>
Date: Mon, 14 Jan 2013 16:09:42 +0100

>> Step 4:  If S1 = 0xCFFF and S2 = 0xCFFF  S1-S2 = 0 ==> The case is false.

If you use the "greater than" relation for the question

"new" > "old"

you will get the answer false... so you drop the message because you 
want the new packet greater (and not just equal) to the one you already 
know.

But maybe I am misunderstanding your argument?

Henning Rogge

---

From: "Susan Hares" <[email-masked]>
Date: Mon, 14 Jan 2013 10:16:51 -0500

Jiazi:

That's the issue, in step 4 the receiver will take it as the same message. 

For details see my case below - broken implementation sending original
received packet or a newly received packet with fix 0xCFFF as sequence
number. 

Sue 

-----Original Message-----
From: Jiazi YI [mailto:[email-masked]] On Behalf Of Jiazi Yi
Sent: Monday, January 14, 2013 10:07 AM
To: Susan Hares
Cc: 'Henning Rogge'; [email-masked]
Subject: Re: [manet] Hares technical question 1: Design of sequence numbers
(warning long post)

Hi, 

I might miss something. 

in your step 4 (case 4?), it's just S1=S2, i.e. the same sequence number.
Then the receiver will take it as the same message. 

You mean the sequence number runs so fast, and reaches the same value again?
With 16 bits of sequence number of rfc5444, this is not likely to happen. Am
I wrong?

@Henning: 

yes, we can consider changing the formula as you suggested to make it
clearer. 

best

Jiazi

On Jan 14, 2013, at 3:58 PM, "Susan Hares" <[email-masked]> wrote:

> Henning:
> 
> The text might be clearer... but before we hack the text let's go 
> through "the rest of the story".
> 

> 
> How does the LOADng go on to deal with the detection of the wrap that 
> caused a back packet to be rotting around in the network?
> 
> originator thinks he's sending a perfectly valid packet.  The junk 
> packet has an aligning sequence number.
> 
> Thanks,
> 
> Sue
> 
> Subject: Re: [manet] Hares technical question 1: Design of sequence 
> numbers (warning long post)
> 
>> Let us assume S1 rotates through MAX_VALUE (0xFFFF, 0, 1) , and S2 
>> stays at 0xCFFF.
>> 
>> The sequence numbers are broken in half so MAX_VALUE/2 = 0x7FFF Step 
>> 1;  If S1= 0xFFFF and S2 = 0xCFFF
>> Step 2: If S1=0x0000 and S2 = 0xCFFF, S1-S2 = 0x3001, therefore s1 is 
>> > S2 Step 3:  If S1 = 0x7FFF and S2 = 0xCFFF, S2-S1 = 0x5000 > 0x3FFF 
> Kommunikationssysteme (KOM) Fraunhofer Straße 20, 53343 Wachtberg, 
> Germany

---

From: "Susan Hares" <[email-masked]>
Date: Mon, 14 Jan 2013 10:21:12 -0500

Henning:

You are saying the receiver test is:

Is the new > old 
[via test we've been discussion] 
    if true, update packet 
    if false, toss packet. 

Since, the S1=S2 - creates a false, then you toss the packet. 

Then the behavior depends on whether the bad packet reaches the node or the
new good packet from the real originator.  The bad packet is the one that
was old and now you hit the reused sequence number. 

Thank you for your quick response, 

Sue 

-----Original Message-----
From: Henning Rogge [mailto:[email-masked]] 
Sent: Monday, January 14, 2013 10:10 AM
To: Susan Hares
Cc: [email-masked]; 'Ulrich Herberg'
Subject: Re: [manet] Hares technical question 1: Design of sequence numbers
(warning long post)

"new" > "old"

Henning Rogge

---

From: Jiazi Yi <[email-masked]>
Date: Mon, 14 Jan 2013 16:51:52 +0100

Hi, 

For LOADng, the sequence number MUST NOT be changed by intermediate routers. In the vulnerability analysis of LOADng, changing sequence number can result in a pre-play attack. 

As a basic mechanism of LOADng, if a implementation doesn't do sequence number properly, and does something that the specification explicitly prohibit from doing, it should be regarded as a malicious behavior (in security consideration, indicate as "A LOADng Router forwards altered control messages"). 

LOADng currently couldn't distinguish between two different message with the same sequence number and originator address. I'm wondering that other MANET protocols like OLSR, AODV, SMF (identification-based duplicate detection) won't be able to detect that either. 

This also brings me the question how further we should go in a protocol specification, to prevent "broken implementation"?

best

Jiazi

---

From: "Susan Hares" <[email-masked]>
Date: Mon, 14 Jan 2013 13:05:41 -0500

Jiazi:

Please note that I am not suggesting changes to LOADng at this point.  I am
simply attempting to understand.   

Some people make the wrap number (0, 0xFFFF) as a clear indication that
something has wrapped.   It is just one method, and this is another.  I'm
trying to understand the pros/cons of each method. 

How many different implementations (that is uniquely coded from scratch)
coded this sequence number rotation?  How did the debugging go? 

This methodology is new to me ... so I'm just digging deeper to understand
it.  

Sue 

-----Original Message-----
From: Jiazi YI [mailto:[email-masked]] On Behalf Of Jiazi Yi
Sent: Monday, January 14, 2013 10:52 AM
To: Susan Hares
Cc: 'Henning Rogge'; [email-masked]
Subject: Re: [manet] Hares technical question 1: Design of sequence numbers
(warning long post)

Hi, 

For LOADng, the sequence number MUST NOT be changed by intermediate routers.
In the vulnerability analysis of LOADng, changing sequence number can result
in a pre-play attack. 

As a basic mechanism of LOADng, if a implementation doesn't do sequence
number properly, and does something that the specification explicitly
prohibit from doing, it should be regarded as a malicious behavior (in
security consideration, indicate as "A LOADng Router forwards altered
control messages"). 

LOADng currently couldn't distinguish between two different message with the
same sequence number and originator address. I'm wondering that other MANET
protocols like OLSR, AODV, SMF (identification-based duplicate detection)
won't be able to detect that either. 

This also brings me the question how further we should go in a protocol
specification, to prevent "broken implementation"?

best

Jiazi

> With 16 bits of sequence number of rfc5444, this is not likely to 
> happen. Am I wrong?
> 
> @Henning: 
>

---

From: Henning Rogge <[email-masked]>
Date: Mon, 14 Jan 2013 19:15:38 +0100

> trying to understand the pros/cons of each method.

What if the message with the "magic number change" gets lost? That is
a common thing in wireless networks.

> coded this sequence number rotation?

I think the olsr.org (OLSRv1) code went through multiple variations of
this code, with several people "testing optimizations" when the
original RFC didn't worked well.

> How did the debugging go?

By having hundreds of users with real wifi networks willing to test
the new version first? ;)

At the moment we have (I think, but I have to check) a standard
compliant "greater than" check in the code and some unique duplicate
check system based on a 32bit shifting register (for each originator).

Henning Rogge
-- 
Steven Hawkings about cosmic inflation: "An increase of billions of
billions of percent in a tiny fraction of a second. Of course, that
was before the present government."

---

From: Jiazi Yi <[email-masked]>
Date: Mon, 14 Jan 2013 19:19:30 +0100

Dear Sue:

> trying to understand the pros/cons of each method. 

In MANET, this clear "indication" can easily be missed, because some of the messages can be lost, and some of them are unicast messages only. 

> coded this sequence number rotation?  How did the debugging go? 

For LOADng, which make use of this sequence number rotation, has at least 4 independent implementations. As far as I can see, I didn't notice any issue. 

In the meantime, this rotation is used in since OLSR version 1 (rfc 3626), so there are must be tens of them. Henning is an expert of this. 

best

Jiazi

---

From: Abdussalam Baryun <[email-masked]>
Date: Mon, 14 Jan 2013 19:41:39 +0100

> trying to understand the pros/cons of each method.
it is a simple method without indication and don't think there maybe a
disadvantage, do you see one?

> coded this sequence number rotation?  How did the debugging go?

I did not check it but don't see any problem yet,

AB

---

From: Abdussalam Baryun <[email-masked]>
Date: Mon, 14 Jan 2013 19:44:45 +0100

On 1/14/13, Jiazi Yi <[email-masked]> wrote:
> For LOADng, which make use of this sequence number rotation, has at least 4
> independent implementations. As far as I can see, I didn't notice any issue.
>

Do you mean four different implementation or independent
implementation. I understand the independent cannot work together (not
interoperable), or am I wrong,

AB

---

From: "Charles E. Perkins" <[email-masked]>
Date: Mon, 14 Jan 2013 15:32:19 -0800

Hello folks,

AODVv2 does not enable any router to change the sequence number
of another router.  That would be quite a mistake.

Regarding your question:

> LOADng currently couldn't distinguish between two different message with the same sequence number and originator address. I'm wondering that other MANET protocols like OLSR, AODV, SMF (identificati…

Until last year, it was legal in DYMO for two different messages to have the
same sequence number.  It is not easy to state the "minimal" required set of
criteria for changing a sequence number.  But anyway it is not automatically
wrong for a routing protocol to allow a router to re-use its same sequence
number more than once.

> This also brings me the question how further we should go in a protocol specification, to prevent "broken implementation"?

A broken implementation should not be able to crash other nodes.

-- 
Regards,
Charlie P.

---

From: "Susan Hares" <[email-masked]>
Date: Mon, 14 Jan 2013 20:26:54 -0500

Henning:

Thank you for continuing this conversation.  I am enjoying learning from
you. 

<snip>

> What if the message with the "magic number change" gets lost? That is a
common thing in wireless networks.

The magic number (0/-1) is a protocol constant.   It can't get lost.  
<snip>
> How many different implementations (that is uniquely coded from 
> scratch) coded this sequence number rotation?

I think the olsr.org (OLSRv1) code went through multiple variations of this
code, with several people "testing optimizations" when the original RFC
didn't worked well.

This is great news.  We've got experience with the algorithm. 
Did they find this algorithm difficult to debug? Not the code, but finding
bugs in the deployment? 

<snip> 
>>At the moment we have (I think, but I have to check) a standard compliant
"greater than" check in the code and some unique duplicate check system
based on a 32bit >>shifting register (for each originator).

Could you post the code if you get a chance? 

Thanks, 

Sue 

-----Original Message-----
From: Henning Rogge [mailto:[email-masked]] 
Sent: Monday, January 14, 2013 1:16 PM
To: Susan Hares
Cc: Jiazi Yi; [email-masked]
Subject: Re: [manet] Hares technical question 1: Design of sequence numbers
(warning long post)

> trying to understand the pros/cons of each method.

What if the message with the "magic number change" gets lost? That is a
common thing in wireless networks.

> How many different implementations (that is uniquely coded from 
> scratch) coded this sequence number rotation?

I think the olsr.org (OLSRv1) code went through multiple variations of this
code, with several people "testing optimizations" when the original RFC
didn't worked well.

> How did the debugging go?

By having hundreds of users with real wifi networks willing to test the new
version first? ;)

At the moment we have (I think, but I have to check) a standard compliant
"greater than" check in the code and some unique duplicate check system
based on a 32bit shifting register (for each originator).

Henning Rogge
--
Steven Hawkings about cosmic inflation: "An increase of billions of billions
of percent in a tiny fraction of a second. Of course, that was before the
present government."

---

From: "Susan Hares" <[email-masked]>
Date: Mon, 14 Jan 2013 20:30:47 -0500

Jiazi:

Thanks for the question...  

The wrap (0/-1) is a protocol constant.   It can't get lost..
[snip]

[sue]
>> scratch) coded this sequence number rotation?  How did the debugging go?

Great news. 4 implementations means you got some mileage on making this
algorithm work. 

I'd love to see the OLSR code -- either privately or to the list. 

Thanks 

Sue

---

From: "Susan Hares" <[email-masked]>
Date: Mon, 14 Jan 2013 20:32:36 -0500

AB:

What I mean by independent implementations is that 4 different people took
the specification, and wrote the code from the specification.  The four
people did not share their code with each other. 

This is different than 4 people taking one code base and modifying it. 

Sue 

-----Original Message-----
From: Abdussalam Baryun [mailto:[email-masked]] 
Sent: Monday, January 14, 2013 1:45 PM
To: Jiazi Yi
Cc: Susan Hares; [email-masked]
Subject: Re: [manet] Hares technical question 1: Design of sequence numbers
(warning long post)

On 1/14/13, Jiazi Yi <[email-masked]> wrote:
> For LOADng, which make use of this sequence number rotation, has at 
> least 4 independent implementations. As far as I can see, I didn't notice
any issue.

Do you mean four different implementation or independent implementation. I
understand the independent cannot work together (not interoperable), or am I
wrong,

AB

---

From: "Susan Hares" <[email-masked]>
Date: Mon, 14 Jan 2013 20:38:24 -0500

Charlie and Jaizi:

Charlie is pointing the theoretical basis behind some of my questions. 

If a node kills itself by being broken - it is getting its reward for broken
code.
If a node can kill other nodes in the network with broken code, then it is a
concern. 

If protocol designers can avoid any possibility of this happening - it is
good.
Sometimes, protocol designers cannot prevent it.  

And .. that my fellow nerds is why I'm asking questions. 

Thank you for taking time to respond to me,

Sue 

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of
Charles E. Perkins
Sent: Monday, January 14, 2013 6:32 PM
To: Jiazi Yi
Cc: [email-masked]
Subject: Re: [manet] Hares technical question 1: Design of sequence numbers
(warning long post)

Hello folks,

AODVv2 does not enable any router to change the sequence number of another
router.  That would be quite a mistake.

Regarding your question:

On 1/14/2013 7:51 AM, Jiazi Yi wrote:
> LOADng currently couldn't distinguish between two different message with
the same sequence number and originator address. I'm wondering that other
MANET protocols like OLSR, AODV, SMF (identification-based duplicate
detection) won't be able to detect that either.

--
Regards,
Charlie P.

---

From: Henning Rogge <[email-masked]>
Date: Tue, 15 Jan 2013 07:32:24 +0100

> The magic number (0/-1) is a protocol constant.   It can't get lost.

I mean it can get lost in transmission. Wireless networks are unreliable 
and have packet loss. So the packet with "here is the magic number, I 
restarted my sequence numbers" could never arrive on the receiving nodes.

> Did they find this algorithm difficult to debug? Not the code, but finding

Finding bugs in a community owned mesh network can be hard and painful. 
Some people will have quite a technical knowledge and will be very 
helpful. Others may not.

Still, if the internet doesn't work, people will start complain quickly.

> Could you post the code if you get a chance?

All code developed at olsr.org is on the website. The duplicate code is 
here:

http://olsr.org/git/?p=olsrd.git;a=blob;f=src/duplicate_set.h;h=e5a761cb980e0ea6fa527aeaeac118e60ef4386c;hb=master

http://olsr.org/git/?p=olsrd.git;a=blob;f=src/duplicate_set.c;h=304d02c20b86f4dbe9619c934cadd1f4d03bfdc7;hb=master
v
I am also working on a complete rewrite of our codebase to implement 
OLSRv2 in the long run, you will find the code in two repositories on 
olsr.org too:

The new API for our program. Think about it as "routing agent without 
the routing protocol". I hope we will use it for other programs too.

http://olsr.org/git/?p=oonf_api.git;a=summary

The NHDP/OLSRv2 application, which is using the API mentioned (at the 
moment only NHDP):

http://olsr.org/git/?p=olsrd2.git;a=summary

Henning Rogge

---

From: Henning Rogge <[email-masked]>
Date: Tue, 15 Jan 2013 07:35:09 +0100

> And .. that my fellow nerds is why I'm asking questions.

As long as you do not run some kind of authentication that prevents 
external attacks or spoofing identity by other routers, its very 
difficult (impossible?) to build a network that cannot be wrecked by an 
attacker.

I would expect OLSR/AODV/LOADng nodes would not crash, but the routing 
itself would not work until the attack stops.

Henning Rogge

---

From: "Charles E. Perkins" <[email-masked]>
Date: Mon, 14 Jan 2013 22:50:00 -0800

Hello Sue and all,

In earlier email, I pointed out that AODVv2 could eliminate the requirement
for a distinguished value of the SeqNum.  I can go either way on this 
issue --
either to keep the distinguished value, or get rid of it.

On 1/13/2013 9:03 PM, Susan Hares wrote:
> security/theoretical discussion on using the loopback IP address 
> versus other addresses? (e.g. DOS on loopback addresses) If you can 
> point to an archive discussion, I'm glad to go read it. I would expect 
> that the sharp minds in this WG would have debated these points.
>

There have been discussions about using loopback addresses for some
functions, but I'm not clear about why that would be a good idea for
Sequence Numbers.

Anyway, I think all the [manet] protocols that have been discussed
lately assume that each node has a unique IP address, and the way
that the IP address is assigned is out of scope for the routing
protocol specification.  Given that, I think that the unique IP address
should naturally be associated with the router's SeqNum.  Or it could
be that I am missing the point here.

>
> #2 Sequence numbers always wrap and sequence number reuse depends on 
> the time and/or wrap detection.
>
> Sequence number time is usually 2* the wrap time so junk can clear 
> from the network. Therefore the equation is:
>

I think you meant half the wrap time, not twice the wrap time.

> Distance vector routes may encounter route cycling (count to infinity 
> in RIP, BGP MED harmful/BGP flapping) in certain topologies. Rapidly 
> changing mobile topologies may cycle through topologies that do and do 
> not cause this route fluctuation.  The validity timer and max-sequence 
> timer seems to be addressing this issue.
>
> Q2: Am I correct?
>

The validity timer is defined in RFC 5444 and so I think it must be
handled in general.  It's useful for intermediate RREP and for path
accumulation also.

>                = ACTIVE_INTERNAL + MAX_IDLETIME -- 

The sequence number for an Expired Route could be used in a RREQ
attempting to re-establish that route.  In fact this is the only reason
to keep Expired Routes.

> 1.How does MAX_SEQNUM_TIME interact with the real wrapping functions 
> during fast node motion to slow node motion so that links come and go 
> (per 2c of Gabblek, Hofner, Portman and Tan's diagram 
> (non-opt_incSQN2.pdf)
>

MAX_SEQNUM_TIME, as you mention, is related to how long a SeqNum is
valid before wrap-around might occur.  It also is defined to be the amount
of time a node must remain quiescent after reboot in case the router's
own sequence number is not stored in non-volatile memory.  That means
that MAX_SEQNUM_TIME might typically be far less than half the wraparound
time.

> 2. What conditions cause all nodes to engage in a sequence number 
> wrap?  For example, would fast mobility of nodes with fast link 
> breakage cause these problems?
>

It would have to be pretty darned fast.

> 3. One important issue is the restart of things after power loss or 
> reboot (likely from software errors).  Does the node going down 
> require that a sequence number to be maintained in NVRAM?
>

It's better to be maintained in NVRAM.  Then the node could start operation
immediately after reboot, using it's old SeqNum as its first value after 
reboot.
This also required maintaining last_used_time.

> 4.Is there a reason for the Address Block TLV route passed through to 
> time out different that the originating node? If so, does (or does it 
> not) impact the sequence number wrap.
>

No, the originating router timeout should be approximately the same
as the timeout for every other router seeing the AddrBlkTLV.

-- 
Regards,
Charlie P.

---

From: Abdussalam Baryun <[email-masked]>
Date: Tue, 15 Jan 2013 09:51:07 +0100

Hi Sue,

Yes in your understanding it is ok, which I think any one on the list
will think, but does thoes 4 routers with independent implementation
can work together in same network. In my opinion if understanding
independent the way you defined then they should work together as long
they are following the same IETF draft specification.

In other understandning of independent, which I think that poster ment
by *independent*, that they cannot work together, because they yes
follow the specification but they are implemented in different
architecture layers. So to say they follow the specification but not
all 4 implementation use the RFC5444's assigned port.

However, I may be wrong, but just making sure I understand the meaning :)

AB

---

From: "Timothy J. Salo" <[email-masked]>
Date: Tue, 15 Jan 2013 03:49:01 -0600

> they are following the same IETF draft specification.

It is generally expected that "independent implementations" will
interoperate.  In particular, see RFC 2026, "Internet Standards
Process", which includes the following:

   Thus, a candidate specification must be implemented and tested for
   correct operation and interoperability by multiple independent
   parties and utilized in increasingly demanding environments, before
   it can be adopted as an Internet Standard.

(Having said that, there appears to be a range of views as to what
"interoperable" means.  For some, it means: if your implementation
conforms to the specification, it is assured of interoperating with
any other conforming implementation.  For others, it seems to mean:
if you implement the same options that I do, then our implementations
will interoperate; if you implement different options, then well...)

-tjs

---

From: Jiazi Yi <[email-masked]>
Date: Tue, 15 Jan 2013 11:45:19 +0100

RFC 2026:

 In general, an Internet Standard is a specification that is stable
   and well-understood, is technically competent, has multiple,
   independent, and interoperable implementations with substantial
   operational experience, enjoys significant public support, and is
   recognizably useful in some or all parts of the Internet.

Jiazi

---

From: "Dearlove, Christopher (UK)" <[email-masked]>
Date: Tue, 15 Jan 2013 13:42:30 +0000

The case S1 and S2 differ by MAXVALUE / 2 is indeterminate. There's actually a technical problem is you define it, as then A can supersede B can supersede A. You're probably better off keeping the older/newer item as determined by order of reception, not serial number. OLSRv2 says this case is up to you. What it doesn't say is that if you ever see it smething somewhere is broken and is likely to make a mess of things.

-- 
Christopher Dearlove
Senior Principal Engineer, Communications Group
Communications, Networks and Image Analysis Capability
BAE Systems Advanced Technology Centre
West Hanningfield Road, Great Baddow, Chelmsford, CM2 8HN, UK
Tel: +44 1245 242194 |  Fax: +44 1245 242124
[email-masked] | http://www.baesystems.com

BAE Systems (Operations) Limited
Registered Office: Warwick House, PO Box 87, Farnborough Aerospace Centre, Farnborough, Hants, GU14 6YU, UK
Registered in England & Wales No: 1996687

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of Henning Rogge
Sent: 14 January 2013 14:48
To: Susan Hares
Cc: [email-masked]
Subject: Re: [manet] Hares technical question 1: Design of sequence numbers (warning long post)

@Ulrich Herberg:

Henning Rogge

********************************************************************
This email and any attachments are confidential to the intended
recipient and may also be privileged. If you are not the intended
recipient please delete it from your system and notify the sender.
You should not copy it or use it for any purpose nor disclose or
distribute its contents to any other person.
********************************************************************

---

From: "Susan Hares" <[email-masked]>
Date: Tue, 15 Jan 2013 13:12:23 -0500

Henning:

Thank you for the example code.  I will download the code, the api, and the
NHDP code. 

I really appreciate all the input. I will be a bit later today as the Wifi
in the hotel was overload this am. 

Sue 

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of
Henning Rogge
Sent: Tuesday, January 15, 2013 1:32 AM
To: [email-masked]
Subject: Re: [manet] Hares technical question 1: Design of sequence numbers
(warning long post)

On 01/15/2013 02:26 AM, Susan Hares wrote:
> Henning:
>
> Thank you for continuing this conversation.  I am enjoying learning 
> from you.
>
> <snip>
>

I mean it can get lost in transmission. Wireless networks are unreliable and
have packet loss. So the packet with "here is the magic number, I restarted
my sequence numbers" could never arrive on the receiving nodes.

> Did they find this algorithm difficult to debug? Not the code, but 
> finding bugs in the deployment?

Finding bugs in a community owned mesh network can be hard and painful. 
Some people will have quite a technical knowledge and will be very helpful.
Others may not.

>>> compliant
> "greater than" check in the code and some unique duplicate check 
> system based on a 32bit >>shifting register (for each originator).
>

http://olsr.org/git/?p=olsrd.git;a=blob;f=src/duplicate_set.h;h=e5a761cb980e
0ea6fa527aeaeac118e60ef4386c;hb=master

http://olsr.org/git/?p=olsrd.git;a=blob;f=src/duplicate_set.c;h=304d02c20b86
f4dbe9619c934cadd1f4d03bfdc7;hb=master
v
I am also working on a complete rewrite of our codebase to implement
OLSRv2 in the long run, you will find the code in two repositories on
olsr.org too:

The new API for our program. Think about it as "routing agent without the
routing protocol". I hope we will use it for other programs too.

The NHDP/OLSRv2 application, which is using the API mentioned (at the moment
only NHDP):

Henning Rogge

---

From: Henning Rogge <[email-masked]>
Date: Tue, 15 Jan 2013 19:43:29 +0100

> Thank you for the example code.  I will download the code, the api, and the

I would really love to get some feedback about the APIs design. Until
the first "stable" version of the olsr.org OLSRv2 is out, I can still
change things to make it easier to use and understand.

Henning Rogge

---

From: "Susan Hares" <[email-masked]>
Date: Wed, 16 Jan 2013 20:34:05 -0500

AB:

You got my meaning.  IETF spec + 4 implementations + same net = working code
Your correction : IETF spec + IETF 5444 protocol + IETF port x + 4
implementation + same net = working code.

Thanks for helping me understand. 

Sue 

-----Original Message-----
From: Abdussalam Baryun [mailto:[email-masked]] 
Sent: Tuesday, January 15, 2013 3:51 AM
To: Susan Hares
Cc: Jiazi Yi; [email-masked]
Subject: Re: [manet] Hares technical question 1: Design of sequence numbers
(warning long post)

Hi Sue,

Yes in your understanding it is ok, which I think any one on the list will
think, but does thoes 4 routers with independent implementation can work
together in same network. In my opinion if understanding independent the way
you defined then they should work together as long they are following the
same IETF draft specification.

In other understandning of independent, which I think that poster ment by
*independent*, that they cannot work together, because they yes follow the
specification but they are implemented in different architecture layers. So
to say they follow the specification but not all 4 implementation use the
RFC5444's assigned port.

AB

On 1/15/13, Susan Hares <[email-masked]> wrote:
> AB:
>
> What I mean by independent implementations is that 4 different people 
> took the specification, and wrote the code from the specification.  
> The four people did not share their code with each other.
>

---

From: "Susan Hares" <[email-masked]>
Date: Wed, 16 Jan 2013 20:54:09 -0500

Chris:

Thanks for letting me know the technical problem is real.   Code tends to
favor the last received, but that choice is not 100% deterministic (as I
think Charlie said). 

I still have not had time to read Hennings code.  I'm hoping I learn a bit
from the code.

Sue 

-----Original Message-----
From: Dearlove, Christopher (UK) [mailto:[email-masked]] 
Sent: Tuesday, January 15, 2013 8:43 AM
To: Henning Rogge; Susan Hares
Cc: [email-masked]
Subject: RE: [manet] Hares technical question 1: Design of sequence numbers
(warning long post)

The case S1 and S2 differ by MAXVALUE / 2 is indeterminate. There's actually
a technical problem is you define it, as then A can supersede B can
supersede A. You're probably better off keeping the older/newer item as
determined by order of reception, not serial number. OLSRv2 says this case
is up to you. What it doesn't say is that if you ever see it smething
somewhere is broken and is likely to make a mess of things.

--
Christopher Dearlove
Senior Principal Engineer, Communications Group Communications, Networks and
Image Analysis Capability BAE Systems Advanced Technology Centre West
Hanningfield Road, Great Baddow, Chelmsford, CM2 8HN, UK
Tel: +44 1245 242194 |  Fax: +44 1245 242124 [email-masked] |
http://www.baesystems.com

BAE Systems (Operations) Limited
Registered Office: Warwick House, PO Box 87, Farnborough Aerospace Centre,
Farnborough, Hants, GU14 6YU, UK Registered in England & Wales No: 1996687

-----Original Message-----

 >> The sequence number S1 is said to be "greater than" (denoted '>')  >>

@Ulrich Herberg:

Henning Rogge