A little while ago, I wrote about some of the design principles of IMAP dating back 30 years. Since I recently came across a blog post explaining how slow SMTP is, it occurred to me there was plenty to learn from that too.

Internet Mail is a really ancient facility. It dates back to 1971 at least – that’s older than me, and older than most people think the Internet is. Email became the original killer application of the Internet, and the format of Internet Mail messages – now RFC 5322 – was one of the first community-developed open standards and really helped shape how standards would be developed on the Internet, so we owe Internet Mail a huge debt. SMTP itself was documented in 1981 by RFC 788, and it’s a pretty simple architecture back then for exchanging messages. The current specification is RFC 5321, published in 2008, and is largely unchanged.

Because SMTP is all about exchanging messages; as the message is transferred in one direction, the responsibility for the message moves along with it (and therefore, acknowledgements flow in the other direction).

The conversation goes roughly like this:

• Server: Welcome, puny client, for I am the great and mighty server!
• Client: HELO! Oh mighty server, I beseech thee to recognise my humble self.
• Server: I condescend to recognise you.
• Client: I humbly request that I might ask you to send an email from <human@example.org>
• Server: This I shall do.
• Client: I would like to send it to <somebody@example.net>
• Server: All this, and more, is within my power.
• Client: And also send it to <other@example.net>
• Server: Yes! Yes! And thrice yes.
• Client: May I give you the message?
• Server: Very well.
• Client: Here it is.
• Server: Ha! It is nothing to me to send this.

The amount of actual data here is very close to the amount of data that absolutely has to be transferred – and especially these days, it’s not usually anything more than a trivial amount given today’s bandwidth. Unless you’re one of those people who likes sending huge powerpoint presentations – and if you are, please stop. But there’s a much bigger problem than bandwidth: Latency.

Now remember, every time the server speaks, the client is waiting for its reply. If the ping time is, say, 100ms – a slow fixed connection, but a very fast mobile one – this entire exchange takes 700ms – that’s about 3/4 of a second. Ouch! But that’s not all – in many cases, we want the client to authenticate (another round-trip), and the connection itself is another one as well. This is properly painful, we’re up to almost a full second, which is mostly spent sitting around.

There’s good news, though – although the message is quite big, we only need to send it once even if we’re sending to two people. Yay! Also, once setup, we can use the connection to send multiple messages, so three of those Round-Trip Times (RTTs for short) can be amortised over all the messages we’re sending. Double Yay!

Filling the Pipe

So how do we improve this? The first step is pipelining. This is a fairly common technique wherein the client sends commands one after another without waiting for a response. We can’t do this every time though, and we need to establish whether the server can handle that (many ancient servers couldn’t). So it turns out there’s a step we need to do before the first – we need a feature negotiation phase.

In SMTP, this was done in 1994 by replacing the first “HELO” command with an “EHLO” – an extended Hello, from RFC 1651. The mechanism is largely the same as IMAP’s CAPABILITY response published the same year – a list of supported features are sent back. Then, if one of those was PIPELINING (from RFC 1854), the client could do this:

• Server: Welcome, puny client, for I am the great and mighty server!
• Client: EHLO! Oh mighty server, I beseech thee to recognise my humble self, and tell me what manner of miracle you can perform?
• Server: I condescend to recognise you, and can do PIPELINING.
• Client: I humbly request that I might ask you to send an email from <human@example.org>
• Client: I would like to send it to <somebody@example.net>
• Client: And also send it to <other@example.net>
• Client: May I give you the message?
• Server: This I shall do.
• Server: All this, and more, is within my power.
• Server: Yes! Yes! And thrice yes.
• Server: Very well, give me the message.
• Client: Here it is.
• Server: Ha! It is nothing to me to send this.

Whee! Three round-trips (that’s over a quarter of a second) has just vanished. But maybe there’s also a more efficient way of sending that message that’d help remove a round-trip there? And it turns out there is. But in order to explain this, I’m going to need to have a small diversion about framing.

Putting Data into the Frame

If a protocol needs to send data – from an email address to a message to an image – it needs a way to indicate which stuff is part of the protocol – commands and so on – and which stuff is the payload – the address, or image, or whatever. There’s a number of ways to do this. In many cases, we can rely on a well-known syntax meaning the data can be easily recognised – we could, for example, rely on a hostname not having a space in it. But where the data is fairly arbitrary, that won’t help.

We could use a known delimiter, and then have a special way of hiding the delimiter if it actually appears in the data. This is what SMTP does with its DATA command – the message follows, a line at a time, until it ends by having a line with only a dot in it. That’s fine, but if the user sends a line with only a dot on it, that’d break things – so we put a dot before it, like this:

..

And in fact, we have to put a dot before any line beginning with a dot, to stop a double-dot turning into a single dot and so on. This also means we need to scan every line of the message as we send it – that’s surprisingly slow.

The alternative would be to send the message as-is, but terminate it by closing the connection. That works – FTP does this – but it has the effect of needing tricky error handling, and it’d mean that the connection setup cost was repeated each time.

There’s also a very rarely-encountered possibility where the data is effectively self-framing, since it’s a complex syntax itself. So if your data is JSON, you know when it ends by parsing it. It’s the same with XML. Don’t do this in your protocol, by the way – it’s cute, but you’ll soon find yourself needing some pretty odd handling.

The final mechanism is octet-counting – just figure out how big the payload is, tell the other end, and then send the data as-is. The other end just counts that many octets off the wire. Octets are, by the way, bytes to you and me, but protocol designers say “octet” because many of us are stuck in the past and remember 9-bit bytes and other odd things.

This final mechanism is generally most efficient, but doesn’t work for streaming data – a small modification is to send data in chunks as it’s obtained, and indicate the last chunk when you send it. (Don’t know the last chunk in advance? Just send a zero-length last chunk).

Re-framing the Problem

It’s this that was added to SMTP. The result is CHUNKING (there’s a closely related extension for handling BINARYMIME, too), and uses a new single-stage BDAT command defined in RFC 1830 instead of the older two-stage DATA. Then what we can do is this:

• Server: Welcome, puny client, for I am the great and mighty server!
• Client: EHLO! Oh mighty server, I beseech thee to recognise my humble self, and tell me what manner of miracle you can perform?
• Server: I condescend to recognise you, and can do PIPELINING and CHUNKING
• Client: I humbly request that I might ask you to send an email from <human@example.org>
• Client: I would like to send it to <somebody@example.net>
• Client: And also send it to <other@example.net>
• Client: Here is my is my 49327 octet message.
• Server: This I shall do.
• Server: All this, and more, is within my power.
• Server: Yes! Yes! And thrice yes.
• Server: Ha! It is nothing to me to send this.

Now look – we have a single RTT message send. Moreover, this style allows whole transactions to be pipelined together – but there’s a catch, and this catch actually has a name – it’s the Two Generals problem.

The Two Generals Problem

The Two generals problem named for a thought experiment in which you are one of two generals laying siege to a city. In order to take the city, both generals must attack simultaneously; otherwise they will be defeated in detail. The only way of sending a message to the other general involves sending a messenger on a dangerous journey through the city; similarly, the messenger is at risk when he comes back with a return message, too. There turns out to be no pattern of messages which allows both generals to know for certain that they are both going to attack at a certain time – you’re never sure the general has received the message, and the other general is never sure you received his acknowledgement should he send one.

And so it is with email – if we never get the server saying “Ha! It is nothing to me to send this.”, but we also don’t get an error back, we’ll never know if the other server actually got the full message.

This problem exists in the very first version of SMTP, incidentally, but because we’re only sending one message before waiting for an acknowledgement, it’s a rare case – and we can just resend the message, risking a duplicate. But if we’re pipelining transactions, we’ll risk generating a vast backlog of messages that need resending. Amazingly, SMTP developed a partial solution for this insoluble problem years ago – RFC 1854, in 1995 – but it’s rarely been implemented; so the best solution is simply to be very careful when pipelining transactions, and not to allow a vast backlog to build up.

The Future

Still, by using existing extensions (the newest is RFC 1854 from 1995), we’ve reduced the RTT-per-messsage from 4 to potentially less than one – and all these techniques are applicable to any new protocol, too, whether it’s over HTTP, Websockets, or XMPP, too. As native web applications become more prevalent, these techniques are going to become more important – and core techniques like clean framing, pipelining, RTT-reduction, and mitigation for the Two Generals problem are going to be required reading. In the next article I’ll look at some modern protocol design tricks and see how they can be reapplied to solve some truly mind-bending problems.