Archive

Archive for October, 2011

Design Your Own Protocol In Five Minutes

October 3, 2011 7 comments

Among the most scary and official sounding terms in computing we find the word ‘protocol’. Its meaning really isn’t that scary, however. Just like when used in other contexts, all it means is a collection of agreements about how to go about something. In this case we’re talking about communication protocols, protocols which allow two or more devices and/or applications to communicate with each other.

Much like how humans have developed their own communication protocols, basically. We also do a handshake part during which we initialize the connection, whether it’s by smiling at each other, remarking on the beautiful/terrible weather or asking after something specific, depending on whether there was previous contact or not. Possible failure modes include getting ignored (Server Time-out), getting slapped in the face after a failed pick-up line (Connection Closed By Host) or interrupted by the girl’s muscular boyfriend (Connection Reset By Peer), as well as addressing the wrong person (Connection Denied).

After successfully establishing the connection, information is exchanged. For humans both during handshake and communication the form used for information exchange is a so-called language, a rather organic and informal set of syllables which when put into the right order (‘spelling’ and ‘grammar’) can be used to evoke understanding in the receiving party. To even get to this level, humans needed tens of thousands of years to evolve a series of grunts and other random noises into something coherent. Suffice it to say that human communication protocols are elaborate, imprecise, filled with misunderstandings and are a clear example of how not to design a communication protocol 🙂

Finally, ending the connection. Again, for humans this can take many forms, generally fails to result in a clean termination and can add many more minutes to a connection. Aren’t we glad now that we are designing a communication protocol for computers?

All joking aside, designing a communication protocol is fairly easy. The first choice we have to make is whether we want the protocol to be binary or text-based. Text-based protocols include the HTTP protocol, which is what we use to browse webpages with. Main benefit of it is that it’s easy for humans to write it out and debug it. Main disadvantage is that it’s less precise and exact in that generally you can’t parse it in one go, can’t instantly verify that it is valid as a whole and using the wrong text encoding can mess things up quite badly. You’ll quickly find that it’s a cumbersome and error-prone way to go about a communication protocol. It’s no wonder that they’re fairly rarely used, mostly with network applications for some reason.

Text-based protocols have the benefit of not being affected by endianness [1], which is the byte order used by a particular system. Little endian is what Intel and AMD processors use and mean that the least important (little) bits are placed at the front of a byte, while big endian is the opposite. This means that if we take the number 14 (hexidecimal 0x0E), in little endian a resulting four-byte integer looks like this: 0E 00 00 00, whereas with big endian it looks like: 00 00 00 0E. Confusing little endian with big or the other way around will lead to interpreting the number wrongly and making our small number of 14 into a much larger number of 917,504. Oops.

To solve this problem with binary protocols which might be used in mixed endian environments, we add a magic number to the front of the header, usually two bytes with known values. By reading those we know which endianness the data is in. One example is using ‘MM’ like in TIFF file headers to indicate big endian (MSB) and ‘ll’ to indicate little endian (LSB) byte order. We can then enter a different parsing routine, or swap the byte order while parsing.

Writing out the protocol itself is a fairly easy and in my experience fun task, but I may just be a tad crazy. It is made easiest when you know what the requirements for the protocol are, but in general we start with the endianness indicator if needed, then one or more indicators identifying the header as being what is expected. I generally use the name of my company followed by the protocol name. After that the data follows. Sections within the data have their own text headers to detect corruption. Where offsets aren’t fixed such as with text strings, an unsigned integer precedes the data to indicate the length of the segment.

The basic protocol thus looks like follows:

ll/MM        uint8(2)
size        uint32
NYANKO        uint8(6)
UDS            uint8(3)
command        uint8(4)

To send a UDS protocol ‘LIST’ command to the server, we would use the following code, this one using a QByteArray:

QByteArray data;
data = "ll";
quint32 size = 19;
for (int i = sizeof(size); i > 0 ; --i) {
data.append((size >> (i * 8)) & 0xFF);
}

data += "NYANKOUDS";
data += "LIST";

Did I mention yet that bitwise operators are important? 🙂 When dealing with low-level interactions such as communication protocols, they are invaluable and one’d do well to study them. Finally, I’d like to comment on the ‘size’ variable used. With network protocols it’s hard for the receiving socket to know when the end of the data has been reached. Putting the size of the whole data at the front of the header like this allows it to know exactly how much data still has to be received, when the data end has been reached and when a download is incomplete.

Parsing the protocol is essentially the opposite of putting it together. It’s done in a linear fashion, with checks for every value read. If done right it’s very robust and quite fool-proof.

Anyway, these are the basics of putting a communication protocol together. It’s very easy, absolutely not scary and even pretty fun 🙂 Go give it a try some time.

Maya

[1] http://en.wikipedia.org/wiki/Endianness

Categories: programming, Protocols