Subject: RE: Refresh Reduction (out of order)

From: "Feng, Mark" <[email-masked]>
Date: Fri, 25 Jan 2002 10:49:11 -0800

One minor comment.

As long as the LSP experiences a state change within the range, so that a
new message ID is allocated, the test would work. This would also depends on
the state change frequency of other LSPs.

There were some discussions on this topic on the RSVP mailing list, if you
are interested. I am not sure the mails are archived though.

- Mark

> -----Original Message-----
> From: David Charlap [mailto:[email-masked]]
> Sent: Friday, January 25, 2002 9:49 AM
> To: Manoj Agiwal
> Cc: [email-masked]'; [email-masked]'
> Subject: Re: Refresh Reduction (out of order)
> 
> 
> Manoj Agiwal wrote:
> > 
> > As per RFC 2961
> > "Out of order messages SHOULD be ignored, i.e., silently dropped."
> > If Epoch value of the message is same and new message id is less
> > than the old one , then message is out of order and hence it should
> > be dropped .
> >   For message Id wrap cases ::
> > "
> > if ((int) old_id - (int) new_id > 0) {
> >           new value is less than old value;
> >        } "
> > How you will you differentiate between wrap case and normal out of
> > order case , since in both cases new message Id will be less than
> > old message ID and epoch is same .
> 
> Note the algorithm provided.  It is casting the IDs onto 
> _signed_ ints. 
> So any values greater than 2^31 will be negative.
> 
> If both IDs are positive (between 0 and 2^31-1), then the subtraction
> will result a positive value if the new ID is less than the old ID.
> 
> If both IDs are negative (between 2^31 and 2^32-1), then the 
> subtraction
> will still result in a positive value if the new ID is less 
> than the old
> ID.  Note that when large integers approach the wrap point, 
> their signed
> equivalent values (when cast to a signed int) approaches zero from the
> negative side.
> 
> If one ID is positive and one is negative, the test will work 
> as long as
> the delta between the two values is less than half the total 
> range (i.e.
> less than 2^31).  The proof of this is left as an exercise for the
> reader.
> 
> In other words, the above algorithm (cast to signed and subtract) will
> work even when the values wrap, as long as the delta between values is
> no larger than 2^31.  This is more than sufficient to catch the cases
> where a stale message ID might be in transit for longer than 
> expected. 
> It won't catch the pathological case where a router is sending out IDs
> that are completely wrong, but that's not the problem this is 
> trying to
> solve.
> 
> -- David
>