Subject: RE: RFC 2961 - detectoin of out-of-order msg

From: "Feng, Mark" <[email-masked]>
Date: Tue, 7 Aug 2001 10:49:05 -0700

I am not sure the topic of the exchange. I assume it is to prove the
original RFC is correct. Please see comments below.

- Mark

> -----Original Message-----
> From: Martin Karsten [mailto:[email-masked]]
> Sent: Monday, August 06, 2001 8:54 AM
> To: Ping Pan
> Cc: Feng, Mark; [email-masked]
> Subject: Re: RFC 2961 - detectoin of out-of-order msg
> 
> 
> Unfortunately, I don't have the original mail from Mark 
> available (the mail
> archive doesn't seem to exist for 2001?), but as far as I 
> understand, in the
> following algorithm in RFC 2961
> 
>        if ((int) old_id - (int) new_id > 0) {
>           new value is less than old value;
>        }
> 
> 'old_id' does not refer to the previous id for this particular state
> information, but to the previous id received from the 
> particular sending hop
> (i.e. across all state information).
> 
> I've been puzzled by the wording in the paragraph a lot, but 
> with the above
> interpretation, it seems to make sense to me.
> 

I am not sure this is true. Following is the description from the RFC:

"When the Epoch values match and the
 Message_Identifier value is less than the largest value previously
 received from the sender, then the receiver SHOULD check the value
 previously received for the state associated with the message."

I would assume the algorithm applies to the two checks in the description.
If not, does it mean the second test should use a different algorithm, which
is implementation dependent?

Let's assume it is so, the problem still exists for the test. What I've
given in the text below is just one example. The same logic can expand to
show that even the test on the previously received message ID at a
particular receiver could fail. Just assume all the states on one receivers
are very stable, while other receivers have many unstable states. In this
case, the same thing will occur.

The problem is that the test does not always work in the wrap-around case. I
cannot think of any that works, without imposing some kind of rules to
specify a valid range, i.e. any numbers out of the range is considered
invalid. This kind of mechanism is going to make the implementation more
complicated. At the mean time, what Ping proposed seems to be reasonable.

> Greetings,
> Martin
> 
> > > Hi,
> > > 
> > > RFC 2961 describes a mechanism to detect out-of-order 
> messages for a
> > > particular state (Please see the quote below). I am not 
> sure the mechanism
> > > works all the time. The test should work if the new 
> number does not wrap
> > > around too far. However, since the message ID is per 
> generator's IP address,
> > > it could be sent to multiple receivers; and there could 
> be numbers of
> > > connections/states on each receiver. In this case, if a 
> particular state
> > > does not experience any change of state for a substantial 
> long period of
> > > time, the next state change could result in the receiver 
> getting a trigger
> > > message with a message ID that wraps around far enough so 
> that the test will
> > > fail (e.g. let's say old id is 0x8fffffff, the new value 
> is 0x00000002, the
> > > test fails)
> > > 
> > > Please correct me if I am wrong.
> > > 
> > 
> > Mark,
> > 
> > One solution is that when the message id becomes too big, the router
> > simply changes the epoch value, and start to send the id from a low
> > number again. In this case, if you use the Ack-extension only, the
> > receiving node will simply update the states to the new 
> id's in the next
> > refresh cycle. If you use the summary-refresh extension, 
> the receiving
> > node will nack the summary-refresh messages due to epoch change. The
> > sending node will have to reply a bunch of messages to sync 
> up the id's.
> > 
> > I know the RFC said something like epoch value should not 
> change unless
> > the router has restarted.... Well, the router does restart 
> the message
> > id now. :-)
> > 
> > - Ping
> > 
> > > Thanks in advance.
> > > 
> > > Mark
> > >
> > 
> 
>

---

From: "Enoch Lee" <[email-masked]>
Date: Tue, 7 Aug 2001 15:52:35 -0500

I think I agree with Mark's observation.  Wrap around case seems to have
some issue with the algorithm given.

Enoch Lee
Yotta Networks, Inc.
[email-masked]
(P) 972-543-4236
(F) 469-241-9267

-----Original Message-----
From: Feng, Mark [mailto:[email-masked]]
Sent: Tuesday, August 07, 2001 12:49 PM
To: 'Martin Karsten'; Ping Pan
Cc: Feng, Mark; [email-masked]
Subject: RE: RFC 2961 - detectoin of out-of-order msg

- Mark

I would assume the algorithm applies to the two checks in the
description.
If not, does it mean the second test should use a different algorithm,
which
is implementation dependent?

Let's assume it is so, the problem still exists for the test. What I've
given in the text below is just one example. The same logic can expand
to
show that even the test on the previously received message ID at a
particular receiver could fail. Just assume all the states on one
receivers
are very stable, while other receivers have many unstable states. In
this
case, the same thing will occur.

The problem is that the test does not always work in the wrap-around
case. I
cannot think of any that works, without imposing some kind of rules to
specify a valid range, i.e. any numbers out of the range is considered
invalid. This kind of mechanism is going to make the implementation more
complicated. At the mean time, what Ping proposed seems to be
reasonable.

---

From: "Feng, Mark" <[email-masked]>
Date: Fri, 31 Aug 2001 08:41:01 -0700

Hi,

Regarding the issue decribed below, can any of the authors respond as to
whether a resolution has been reached? If yes, what is the final decision?

Thanks in advance.

- Mark

> Sent: Tuesday, August 07, 2001 10:49 AM