Please have symmetric option negotiations in your protocols

June 30, 2011

Suppose that you are designing a protocol where the two ends (let us call them the initiator and the target) must agree on a joint set of options, actions, or whatever that they both support, will use, or whatever. If you are doing this, I have a small request: please make the option negotiation process symmetric, where the initiator and the target do the same operations (with slightly different data).

In a symmetric option negotiation process, the initiator says something like 'I support the following things' and the target replies with 'I support the following subset of the things you support'. One sign of a symmetric exchange is that if the initiator and target are equally capable, the set of options in the messages back and forth is exactly the same; the initiator says 'I support everything', and the target says 'then lets do everything'. In an asymmetric option negotiation process, well, things don't work that neatly.

Since this all sounds very abstract, let's use a concrete example; the milter protocol. In the milter protocol the MTA and the milter exchange two sets of options. The MTA opens with a bitfield of the message modification actions it supports and a bitfield of the protocol steps it is willing to skip. The milter replies with a bitfield of the message modification actions it may use and a bitfield of the protocol steps it wants the milter to skip. The negotiation of actions is a symmetric negotiation, but the negotiation of protocol steps is an asymmetric one. We can see the asymmetry in what the MTA and the milter say; the MTA will normally say 'I could skip all of the steps I support', and the milter will normally say 'I don't want you to skip anything (except maybe the steps that I don't understand)'.

The fundamental operation in a symmetric option negotiation is binary and-ing supported options together, you can do it repeatedly, and each end can use the same code. For example, you might and together what your program wants to support, what your protocol codec library can support, and what the other side is willing to support (if there is an other end). Asymmetric option negotiation has no neatly commutable operation on the target; in the milter protocol, for example, a milter support library wants to form the 'protocol steps I want you to skip' reply with:

mta_proto & (~known_proto_steps | client_skip_list)

(We want to tell the MTA to skip anything outside the library's known protocol steps plus anything that the client code wants the MTA to skip.)

A symmetric version of this would negotiate what protocol steps the MTA should perform, and would be:

mta_proto & known_proto_steps & client_do_list

If you default mta_proto to known_proto_steps, this code is also how a library would form the MTA's initial supported protocol bitfield; if you also default client_do_list to known_proto_steps, you have covered the common case for both MTA and milter (where you wind up doing all steps in the protocol).

As you can see, symmetric option negotiation is simpler, more straightforward, easier to get right, and easier to understand and convince yourself that the code is correct. I believe that these differences matter.

Comments on this page:

From at 2011-06-30 10:54:34:

A corollary is "don't have the safe response for options you don't know about be 'turn the option on'". If you do this, then the target's response grows as the initiator's initial message grows, and you end up not having symmetric option negotiation.

In fact, that's pretty much what's going on here: the initiator says effectively that they support the options SKIP_STAGEFOO, SKIP_STAGEBAR, etc. and the target responds with which skip options they want to enable, and must echo back any options they (the target) don't understand.

Viewed in that light - that really what we have here is options with the safe default backwards - then we can make the steps look slightly more symmetric; what we need is to define an "and not" operator that behaves like (asymmetric) set difference. I'll write it as &~, since I intend:

a &~ b == a & (~b)

with the caveat that b is first widened to be as wide as a by adding zeros if necessary. Then, we can write the library's option handling as this pseudocode:

mta_stages = read_stages_from_upstream()
write_stages_to_downstream(mta_stages & known_stages)
client_skips = read_stages_from_downstream()
known_client_stages = known_stages &~ client_skips
write_stages_to_upstream(mta_stages &~ known_client_stages)

In other words, in one direction use & and in the other use &~. Note that this pseudocode works even if there are multiple libraries between the two ends of the communication.

I think this is slightly clearer than dealing with both & and | in the same expression, though I'll agree that the whole thing'd be easier given a "safe default is off" option protocol. (Note that to convert the pseudocode for such a protocol, you just replace every occurrence of &~ with &)

-- DanielMartin

Written on 30 June 2011.
« Our ZFS spares handling system (part 1)
Some ways to test if a program securely runs other programs »

Page tools: View Source, View Normal, Add Comment.
Login: Password:
Atom Syndication: Recent Comments.

Last modified: Thu Jun 30 01:03:28 2011
This dinky wiki is brought to you by the Insane Hackers Guild, Python sub-branch.