The MPLS WG Archive

[David Charlap <David.Charlap@marconi.com>]

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