Re: 48-bit sequence number arithmetic

Re: 48-bit sequence number arithmetic

[Eddie Kohler]

Gerrit,

Subtracting two 32-bit numbers which are 2^31 apart will have the same results.

(int32_t) ((uint32_t) 0 - (uint32_t) 0x80000000) = -0x80000000
(int32_t) ((uint32_t) 0x80000000 - (uint32_t) 0) = -0x80000000

The RFC is not in error and your delta_seqno patch should not be accepted.

As RFC 1982 says:

    Note that there are some pairs of values s1 and s2 for which s1 is
    not equal to s2, but for which s1 is neither greater than, nor less
    than, s2.  An attempt to use these ordering operators on such pairs
    of values produces an undefined result.

    The reason for this is that those pairs of values are such that any
    simple definition that were to define s1 to be less than s2 where
    (s1, s2) is such a pair, would also usually cause s2 to be less than
    s1, when the pair is (s2, s1).  This would mean that the particular
    order selected for a test could cause the result to differ, leading
    to unpredictable implementations.

...

    Thus the problem case is left undefined, implementations are free to
    return either result, or to flag an error, and users must take care
    not to depend on any particular outcome.  Usually this will mean
    avoiding allowing those particular pairs of numbers to co-exist.

Eddie



Gerrit Renker wrote:
> I would like to notify you of an error in RFC 4340.
> 
> In [RFC 4340, sec. 3.1] it is suggested that
>  "It may make sense to store DCCP sequence numbers in the most significant 48 bits
>   of 64-bit integers and set the least significant 16 bits to zero, since this 
>   supports a common technique that implements circular comparison A < B by testing
>   whether (A - B) < 0 using conventional two's-complement arithmetic."
> 
> Unfortunately this does not work.
> 
> Signed 64-bit numbers represent the range -2^63 ... 0 ... 2^63-1. 
> When the difference between two left-shifted 48-bit numbers a and b is +/- 2^63, we can not tell
> whether a is `before' b or b is `before' a: the difference will yield the same negative result -2^63,
> due to the constraints of the data type.
> 
> This case occurs for all 48-bit numbers whose difference amounts to 2^47. Since there are 2^47
> such numbers, this test fails to produce correct results in 2^47 = 140.7375e12 cases.
> 
> The sequence number test based on subtraction works for TCP since signed 32 bit numbers are a native type. 
> For 48 bit, arithmetic operations need to be redeveloped from scratch. It is not sufficient to shift and subtract.
> 
> Regards
> Gerrit Renker

Re: 48-bit sequence number arithmetic

[Eddie Kohler]

Let me restate.

- Patches to clean up sequence number arithmetic are fine.
- Your analysis of the 2^47 problem is not correct, however.  As RFC 1982 
says, two 48-bit numbers which are 2^47 apart are *unordered*.  Think about 
it: You see 0 and 2^47.  The distance between 0 and 2^47 is, IN EITHER 
DIRECTION, exactly 2^47.  Neither can be declared before the other.
- This is exactly the same case as in 32-bit TCP sequence number comparisons. 
  There is nothing magical about the 32-bit "native type".
- Therefore I'd recommend staying with the simplest check you can find, which 
may be the 64-bit trick recommended by RFC4340.

Eddie


Eddie Kohler wrote:
> Gerrit,
> 
> Subtracting two 32-bit numbers which are 2^31 apart will have the same 
> results.
> 
> (int32_t) ((uint32_t) 0 - (uint32_t) 0x80000000) = -0x80000000
> (int32_t) ((uint32_t) 0x80000000 - (uint32_t) 0) = -0x80000000
> 
> The RFC is not in error and your delta_seqno patch should not be accepted.
> 
> As RFC 1982 says:
> 
>    Note that there are some pairs of values s1 and s2 for which s1 is
>    not equal to s2, but for which s1 is neither greater than, nor less
>    than, s2.  An attempt to use these ordering operators on such pairs
>    of values produces an undefined result.
> 
>    The reason for this is that those pairs of values are such that any
>    simple definition that were to define s1 to be less than s2 where
>    (s1, s2) is such a pair, would also usually cause s2 to be less than
>    s1, when the pair is (s2, s1).  This would mean that the particular
>    order selected for a test could cause the result to differ, leading
>    to unpredictable implementations.
> 
> ...
> 
>    Thus the problem case is left undefined, implementations are free to
>    return either result, or to flag an error, and users must take care
>    not to depend on any particular outcome.  Usually this will mean
>    avoiding allowing those particular pairs of numbers to co-exist.
> 
> Eddie
> 
> 
> 
> Gerrit Renker wrote:
>> I would like to notify you of an error in RFC 4340.
>>
>> In [RFC 4340, sec. 3.1] it is suggested that
>>  "It may make sense to store DCCP sequence numbers in the most 
>> significant 48 bits
>>   of 64-bit integers and set the least significant 16 bits to zero, 
>> since this   supports a common technique that implements circular 
>> comparison A < B by testing
>>   whether (A - B) < 0 using conventional two's-complement arithmetic."
>>
>> Unfortunately this does not work.
>>
>> Signed 64-bit numbers represent the range -2^63 ... 0 ... 2^63-1. When 
>> the difference between two left-shifted 48-bit numbers a and b is +/- 
>> 2^63, we can not tell
>> whether a is `before' b or b is `before' a: the difference will yield 
>> the same negative result -2^63,
>> due to the constraints of the data type.
>>
>> This case occurs for all 48-bit numbers whose difference amounts to 
>> 2^47. Since there are 2^47
>> such numbers, this test fails to produce correct results in 2^47 = 
>> 140.7375e12 cases.
>>
>> The sequence number test based on subtraction works for TCP since 
>> signed 32 bit numbers are a native type. For 48 bit, arithmetic 
>> operations need to be redeveloped from scratch. It is not sufficient 
>> to shift and subtract.
>>
>> Regards
>> Gerrit Renker
> 

Re: 48-bit sequence number arithmetic

[Gerrit Renker]

Hi Eddie,

sorry there is a bit of confusion here. For the record, please let's move the
issue whether RFC 4340 is right or not out of the focus. If you say it is right,
I will not argue with it; but there are useful and valid points that can be
used to make existing algorithms better. 

And I think it is time well spent to think these issues through, in particular since
the performance of CCID 3 for instance depends on the accuracy with which loss is 
detected - therefore I don't think that it harms to strive for maximum precision in
these matters.


|  - Patches to clean up sequence number arithmetic are fine.
|  - Your analysis of the 2^47 problem is not correct, however.  As RFC 1982 
|  says, two 48-bit numbers which are 2^47 apart are *unordered*.  Think about 
|  it: You see 0 and 2^47.  The distance between 0 and 2^47 is, IN EITHER 
|  DIRECTION, exactly 2^47.  Neither can be declared before the other.
Although RFC 1982 is about serial numbers as they are used in the Domain Name
System, it is a very useful reference here. Your point is valid, and it is solved
by the solution below. My point here is that for 2^(n-1) the result should really be
'undefined': with the current solution of subtraction, the result is not undefined,
but ambiguous.

|  - This is exactly the same case as in 32-bit TCP sequence number comparisons. 
You are right and therefore RFC 4340 is not `wrong'. It is strange that this way
of comparing sequence numbers has survived for so long: as early as 4.4BSDLite
(the SEQ_LEQ macros in Stevens vol II), until today's Linux IP stack.


|  - Therefore I'd recommend staying with the simplest check you can find, which 
|  may be the 64-bit trick recommended by RFC4340.
I found a solution which is as easy to implement as that _and_ removes the ambiguity.
It is, for two n-bit sequence numbers a and b, as follows:
	
 	a `before' b <=>         1 <= b-a <= 2^(n-1) - 1

To contrast: the previous definition was:

	a `before' b <=>   2^(n-1) <= a-b <= 2^n-1

and it suffers from the ambiguity problem when a-b = 2^(n-1). With the former solution,
the ambiguity is removed: whenever the difference between a and b is 2^(n-1), the result
is 2^(n-1) and thus neither a `before' b nor b `before' a: this is exactly what RFC 1982
suggests.

And my suggestion is not even new: we say "it is 29 minutes /before/ xxx o'clock", but we
don't say "it is /half/ before xxx o'clock". 

To summarise, the revised algorithm is:
	* store 48-bit numbers in leftmost fields of 64-bit numbers as per RFC 4340
	* a sequence number comparison based on the following pseudo-code:
  		int before48(u64 a, u64 b) { return ((b << 16) - (a << 16)) > 0; }
	* this removes the ambiguity
	* same suggestion was made for 32-bit TCP sequence numbers to netdev@vger


Gerrit

Re: 48-bit sequence number arithmetic

[Eddie Kohler]

Hi Gerrit,

Thanks for the useful work.  This is just for the record.

Your solution differs than the usual 32-bit subtraction solution used 
for TCP, but it has interesting properties of its own.  We now have 
pairs of numbers where "a != b && !before48(a, b) && !before48(b, a)"!

Not clear this is significantly better than having numbers where "a != b 
&& before48(a, b) && before48(b, a)".  As RFC 1982 says (and FYI this is 
explicitly referenced in RFC4340), "the problem case is left undefined, 
[and] implementations are free to return either result, or to flag an 
error".  This explicitly blesses the existing TCP implementation of SEQ_LEQ.

So you have made a perfectly reasonable choice, but it really isn't 
"more correct" than the other.  As a result, I wouldn't necessarily push 
too hard on the TCP folks; if I were them, I'd stay with the existing, 
de facto standard SEQ_LEQ.

Eddie


Gerrit Renker wrote:
> Hi Eddie,
> 
> sorry there is a bit of confusion here. For the record, please let's move the
> issue whether RFC 4340 is right or not out of the focus. If you say it is right,
> I will not argue with it; but there are useful and valid points that can be
> used to make existing algorithms better. 
> 
> And I think it is time well spent to think these issues through, in particular since
> the performance of CCID 3 for instance depends on the accuracy with which loss is 
> detected - therefore I don't think that it harms to strive for maximum precision in
> these matters.
> 
> 
> |  - Patches to clean up sequence number arithmetic are fine.
> |  - Your analysis of the 2^47 problem is not correct, however.  As RFC 1982 
> |  says, two 48-bit numbers which are 2^47 apart are *unordered*.  Think about 
> |  it: You see 0 and 2^47.  The distance between 0 and 2^47 is, IN EITHER 
> |  DIRECTION, exactly 2^47.  Neither can be declared before the other.
> Although RFC 1982 is about serial numbers as they are used in the Domain Name
> System, it is a very useful reference here. Your point is valid, and it is solved
> by the solution below. My point here is that for 2^(n-1) the result should really be
> 'undefined': with the current solution of subtraction, the result is not undefined,
> but ambiguous.
> 
> |  - This is exactly the same case as in 32-bit TCP sequence number comparisons. 
> You are right and therefore RFC 4340 is not `wrong'. It is strange that this way
> of comparing sequence numbers has survived for so long: as early as 4.4BSDLite
> (the SEQ_LEQ macros in Stevens vol II), until today's Linux IP stack.
> 
> 
> |  - Therefore I'd recommend staying with the simplest check you can find, which 
> |  may be the 64-bit trick recommended by RFC4340.
> I found a solution which is as easy to implement as that _and_ removes the ambiguity.
> It is, for two n-bit sequence numbers a and b, as follows:
> 	
>  	a `before' b <=>         1 <= b-a <= 2^(n-1) - 1
> 
> To contrast: the previous definition was:
> 
> 	a `before' b <=>   2^(n-1) <= a-b <= 2^n-1
> 
> and it suffers from the ambiguity problem when a-b = 2^(n-1). With the former solution,
> the ambiguity is removed: whenever the difference between a and b is 2^(n-1), the result
> is 2^(n-1) and thus neither a `before' b nor b `before' a: this is exactly what RFC 1982
> suggests.
> 
> And my suggestion is not even new: we say "it is 29 minutes /before/ xxx o'clock", but we
> don't say "it is /half/ before xxx o'clock". 
> 
> To summarise, the revised algorithm is:
> 	* store 48-bit numbers in leftmost fields of 64-bit numbers as per RFC 4340
> 	* a sequence number comparison based on the following pseudo-code:
>   		int before48(u64 a, u64 b) { return ((b << 16) - (a << 16)) > 0; }
> 	* this removes the ambiguity
> 	* same suggestion was made for 32-bit TCP sequence numbers to netdev@vger
> 
> 
> Gerrit

Re: 48-bit sequence number arithmetic

[Gerrit Renker]

|  Your solution differs than the usual 32-bit subtraction solution used 
|  for TCP, but it has interesting properties of its own.  We now have 
|  pairs of numbers where "a != b && !before48(a, b) && !before48(b, a)"!
For each number a there is one such number b = a + 2^(n-1)  = a - 2^(n-1)
(modulo 2^n). This means the above test can be used to identify this number,
as in all other cases either before48(a, b), or before48(b, a), or a = b.

With the previous solution one would have to eliminate the ambiguity by testing

 * whether before48(b, a) when before48(a, b)
 * whether before48(a, b) when before48(b, a)

This kind of test is more expensive. Likely, the advantages of the solution are more
theoretical in nature. But it may be interesting in light of testing against earlier
segments (quiet time, 2 MSL), or for DoS attacks, or choosing initial numbers.