Re: [tcpinc] Simultaneous open tie breaking

[David Mazieres <[e-mail]>]

Tero Kivinen <[e-mail]> writes:

> I do not think the b bit is really going to work, and I agree with
> others that we need proper tie-breaker to solve this issue.
>
> On the other hand I do not think we need to add large tie breaker to
> the frame, we can most likely use something like very small tie
> breaker and sequence numbers for tie-breaker. I.e. whoever has smaller
> 8-bit (or 6-bit) tie breaker is winner,

This is doable, though adds complexity to implementations.  Should this
tie-breaker be sent by every active opener (and therefore consume option
space), or do you imagine that applications intending to use
simultaneous open set an option to include the tie breaker?

> if the tie breakers are same, then we compare initial sequence
> numbers, and whoever has smaller initial sequence number is the
> initiator and other end responder.

I'm very uncomfortable using sequence numbers.  In our initial tests for
tcpcrypt we found sequence numbers got modulated.  If I recall OpenBSD
does this by default when operating as a NAT, and I'm not even sure
there's a way to disable it.  Same for timestamp.

> After that we just need to have rules specifying how we pick up the
> protocol from two ordered list. The most simple solution would be to
> just say we take initiators list, remove all of the protocols not in
> the responders list, and then take first item from initiators list
> that is also supported by responder.

ENO currently does the mirror of this, letting the responder's list
determine priority.  The logic was that passive openers tend to need to
support higher numbers of connections per second, and so may need to
steer choices towards options with better hardware acceleration, etc.

Is your choice of the initiator's list just arbitrary, because you think
we should just settle on one of the two lists and happened to say
initiator?  Or is there an argument to favor the initiator's list over
the responder's?

> I.e. the negotiation would be (with same tie breaker selected randomly
> in both ends):
>
> A->B(0x9453f454) SYN: Tie breaker=33; I can speak Z, Y
> B->A(0x434945e5) SYN: Tie breaker=33; I can speak X, Y, Z
>
> As tie breaker is same, we will check sequence numbers, and as B has
> smaller he is the winner, and both ends know this. Following the rules
> above, the protocol to be used is Y.
>
> There are of course some middleboxes who do mess up with sequence
> numrbers. To detect this we want to tell the result of the exchange to
> both ends:
>
> A->B(0x9453f455) ACK: We are using protocol Y
> B->A(0x434945e6) ACK: We are using protocol Y, I am initiator

This is going to add significant complexity to the protocol, including
some cold code paths that are likely to be weakly tested in some OS
distributions.

If we are going to add another round of exchanges anyway, though, why
not do the tie-breaking there?  We could keep the single b bit as is
(for applications that want to work it out), and then add a
variable-length tie-breaking phase.  E.g.,

    A->B:  SYN ENO<Z, Y>
    B->A:  SYN ENO<X, Y, Z>
    A->B:  ACK ENO<Breaker 0x29892a863ce5>
    B->A:  ACK ENO<Breaker 0xdb636b5918a2>

Here B is chosen as virtual responder because it has a higher
tie-breaker, and at this point the protocol proceeds as usual.

Yet another possibility is hashing the options list and comparing.

Before settling on something, I'd like to get a sense of whether people
think it's okay to ask applications to signal their intent to use
simultaneous open, or whether it's important for TCP-ENO to enable
encryption for existing, unmodified applications that use simultaneous
open.  Those two options put us down different paths.

> Also if application will know it will NEVER do simulatenous opens
> (like web server, or web client), it can do setsockopt that will
> disable the Tie breaker option from the option list, saving byte or
> two.

Obviously a passive opener never needs to include the tie-breaker.  But
this sounds like you want active openers to include a tie-breaker by
default, but want to enable them to opt out of it to save option space.

My personal feeling is that it's unfortunate to waste option space and
add all this complexity to deal with such a fringe case.  But it's not a
strong feeling and I'm happy to modify ENO to suit the option of the
working group.

But... I might have an idea for how to make this work that isn't so bad.
Let me try something based on sorting the option lists and adding a
variable-length tie-breaker option.  I think that might allow
simultaneous open to work out of the box without adding too much
complexity, and would allow people trade-offs in terms of option space
consumed vs. failure probability.

David