Message-Id: <200701030856.19416@strip-the-willow>
Date:	Wed, 3 Jan 2007 08:56:19 +0000
From:	Gerrit Renker <gerrit@....abdn.ac.uk>
To:	Herbert Xu <herbert@...dor.apana.org.au>
Cc:	David Miller <davem@...emloft.net>, netdev@...r.kernel.org
Subject: Re: [PATCH][RFC] tcp: fix ambiguity in the `before' relation

Hi Herbert,


|  >> While looking at DCCP sequence numbers, I stumbled over a problem with
|  >> the following definition of before in tcp.h:
|  >> 
|  >> static inline int before(__u32 seq1, __u32 seq2)
|  >> {
|  >>         return (__s32)(seq1-seq2) < 0;
|  >> }
|  >> 
|  >> Problem: This definition suffers from an an ambiguity, i.e. always
|  >>                    
|  >>            before(a, (a + 2^31) % 2^32)) = 1
|  >>            before((a + 2^31) % 2^32), a) = 1
|  >>  
|  >>          In text: when the difference between a and b amounts to 2^31,
|  >>          a is always considered `before' b, the function can not decide. 
|  >>          The reason is that implicitly 0 is `before' 1 ... 2^31-1 ... 2^31
|  >>       
|  >> Solution: There is a simple fix, by defining before in such a way that 
|  >>           0 is no longer `before' 2^31, i.e. 0 `before' 1 ... 2^31-1
|  >>           By not using the middle between 0 and 2^32, before can be made 
|  >>           unambiguous. 
|  >>           This is achieved by testing whether seq2-seq1 > 0 (using signed
|  >>           32-bit arithmetic).
| 
|  Sorry, I still don't get the point of this change.
|  
|  Prior to the patch, we have values x and y such that both
|  before(x, y) and before(y, x) are true.  Now for those same
|  values both before(x, y) and before(y, x) are false.
|
|  It's still as ambiguous as ever.  Surely to resolve the
|  ambiguity we want to make before(x, y) = !before(y, x), no?
Please let me restate:
 Ambiguity here means that for those numbers x,y such that  (x + 2^31) % 2^32) = y
 before(x, y) = 1 and before(y, x) = 1. With the previous implementation, one could 
 not tell the difference here: and there are 2^32 such cases where this occurs.

 With the implementation now, the output of before(x,y) is reliable: it returns true
 if (and only if) x is indeed `before' y.

 If before(x,y) is false then there are now two possibilities:
  (a) before(y, x) is true   and y != (x + 2^31) % 2^32
  (b) before(y, x) is false  and y == (x + 2^31) % 2^32
 This means that the cases can be clearly separated out, which was not possible before.

		To summarize the differences:
		-----------------------------

1) Possible cases in the old implementation (exclusive-or list):
    * x == y                            -  identity
    * before(x, y) && !before(y, x)     -  x is `before' y
    * before(y, x) && !before(x, y) 	-  y is `before' x
    * before(x, y) && before(y, x)      -  y == (x + 2^31) % 2^32
    
2) Possible cases in the new implementation (exclusive-or list):
    * x == y 				-  identity
    * before(x, y)			-  x is `before' x
    * before(y, x)			-  y is `before x
    * !before(x, y) && !before(y, x)    -  y == (x + 2^31) % 2^32

As can be seen (2) requires fewer test cases while (1) would need extra checks to disambiguate
before(x, y) from the case "before(x,y) && before(y,x)".

I do believe that this is useful, since now speeds of 10 Gigabits are in use, which means that
sequence numbers wrap around faster; and also with regard to the issue of selecting an initial
sequence number; and protection against sequence number attacks.

A related discussion is in RFC 1982, but with regard to the case y == (x + 2^31) % 2^32 it 
recommends to leave this `undefined' -- the new solution is in agreement with this, and is
even less complicated to implement.

Gerrit
-
To unsubscribe from this list: send the line "unsubscribe netdev" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Powered by blists - more mailing lists