48-bit sequence number arithmetic
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
Quoted 23 lines · Gerrit Renker
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 isbefore' b or b isbefore' 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
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
Quoted 68 lines · 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) = -0x80000000The RFC is not in error and your
delta_seqnopatch 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
Quoted 31 lines · Gerrit Renker
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 isbefore' b or b isbefore' 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
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
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
Quoted 58 lines · 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_LEQmacros 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-1and 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 bbefore' 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:
intbefore48(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@vgerGerrit
| 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.