It's a curious paradox that digital networks, bred of high binary certainty, can be so capricious. But they are, at best, barely domesticated animals.
All the same, we've built our civilization on their restive backs--a civilization dependent on perfect information. Take a thousand bits, change one of them: your password doesn't work, a train switches to the wrong track, your bank account has $65,536 extra in it, the space station's orbit-keeping software malfunctions. Nature abhors perfection almost as much as a vacuum; there's nothing it loves to do more than flip bits. But somehow, despite nature's puckish tendencies, your password works, the train keeps rolling, you're still broke, and the ISS is still up there. How?
Long ago, scientists and engineers learned that the best way to make sure something works is to assume that it will fail. A lot. In fact, the most wildly successful communication protocols, such as Ethernet and Internet Protocol, not only accept failure as inevitable, but seem almost to revel in it. If you read their specs you'll notice that most of their considerable cleverness is given over to how to survive when everything blow ups. In communication circles this is called error correction.
TFTP: Acknowledging the Possibility of Data Misadventure
Which brings us to my favorite protocol: the Trivial File Transfer Protocol. TFTP's design is revealing the same way that a car's airbags are. As an airbag testifies to the probability and violent nature of a crash, so TFTP's design speaks to frequent and catastrophic data misadventure. It's trivialness of purpose (to move one file from one computer to another--nothing more, nothing less) makes it something like a 1950's truck engine: crack open the hood and it's still simple enough to understand in an afternoon. And once you understand it, most other protocols are just TFTP with dual overhead cams and a swish fuel injection system.
It's revealing then to find out that TFTP is almost entirely composed of error correction. And instructive to note that it uses only three basic techniques in the process: redundancy, acknowledgement, and timeouts. These are the pistons and carburetors of error correction, basics worth understanding because they crop up everywhere, from P2P to 802.11g.
We'll look at each one in turn, but first a glance at what TFTP has to work with.
Usually Drops Packets
To understand the nature of TFTP, we must first look at its dependency on another protocol, the User Datagram Protocol (UDP).
UDP's purpose in life is to carry a datagram packet from one computer to another over a network. A datagram is a chunk of data with an address attached to it; imagine it as postcard. And like postcards, datagrams are typically not big enough to contain anything serious--so many must be sent, each with a small part of the whole (usually less than a kilobyte). In other words, to transfer a whole file, TFTP must first break it up into datagrams, which it then gives to UDP to deliver.
The trouble with UDP is that it's only as reliable as the network that it runs on, which is to say not at all. Datagrams get lost or misrouted, they usually arrive out of order, they might even arrive twice. Think of Charlie Chaplin delivering postcards.
For example, I send a message with one letter per datagram: HELLO. The receiver gets LHHEO. Not only is this possible, it's likely.
So the relationship between TFTP and UDP is this: TFTP needs UDP to send its packets across the network, UDP needs TFTP to unravel the mess that it creates.
Now let's look at the first tool that TFTP uses to accomplish that: redundancy.
Superfluity, Redundancy, and Repetitiousness
Imagine for a moment a fictitious colonial scene: the ambassador from Lemuria enters the court of King Ed of Florin and says hello. This takes ten minutes. A courtly greeting is a dissertation on genealogy, titles, and treaties between the two nations. During which, Ed is referred to as (at the very least) "the sovereign king", or "his royal highness".
Have a look at those two phrases, you'll notice that they repeat themselves. Sovereign means king; the two words can be used interchangeably. Likewise for "royal" and "highness".
Let's say that His Royal Highness King Ed (Sovereign of Florin) is kind of miffed at Lemuria, and wants to catch the Ambassador on any breach of etiquette so he can feign grave insult and send a couple of Florin warships out that way. The lives of many Lemurians rest on the Ambassador's flawless smarminess.
And let's suppose that someone coughs right in the middle of the Ambassador's address, obscuring the word "sovereign"... Lemuria is still safe, because the "king" part still got through.
Better yet than plain redundancy is what you could call synonymous redundancy. The purest form of repetition would be to say, "his royal royalness". But imagine that the Ambassador has a lisp, and can't say his R's. His Woyal Highness still can't take offence, because though he may not have been formally recognized as Royal, he's still a Highness.
Redundancy is probably the single most vital aspect of reliable communication. So how does TFTP use it?
The first way is actually a function of UDP. A number, called a Cyclic Redundancy Check (CRC), is attached to every datagram packet. This is a numeric summary of the data contained in the packet.
As an analogy, let's take our greeting, and for every letter we also tag on its position in the alphabet (A is 1, B is 2, and so forth):
H8 E5 L12 L12 O15
The one thing that UDP does do reliably is to make sure that a datagram hasn't been altered during the transfer. If UDP sees a packet with a mismatch, like "H4", it would know that either the letter got changed or the number did. In either case it knows that something's up and throws the packet out.
The second way that TFTP uses redundancy is via explicit ordering.
It's something that we usually don't think about, but in any word there are actually two kinds of information. The first is the character of the alphabet, the second is the order in which they appear. LHLOE doesn't mean the same thing as HELLO because the information implicit in the sequence of the characters has been altered.
We could explicitly note the order of the letters, but writing "1H2E3L4L5O" on paper isn't useful (besides being hard to read). You already know that E is the second letter because it's right after the H.
But you'll recall that UDP isn't as reliable as paper for keeping things straight. So, we add in ordering information. Our once simple hail (with redundant character and ordering information) is now:
1H8 2E5 3L12 4L12 5O15.
Which looks like a lot of superfluous writing. However, when a computer receives this:
3L12 1H8 4R5 1H8 2E5 5O15
it can make some sense of it. Let's sort it out:
Throwing out obviously bad packets (R is not the fourth letter of the alphabet), duplicates (too many H's), and rearranging things: we get HEL_O. Not quite what we were expecting, but it's a whole lot better than LHRHEO.
So, what do we do about that missing L? That's where acknowledgement comes in.
Roger That, Houston
Another familiar protocol is the preflight check that pilots do before take-off--vital functions are read out, checked, and acknowledged: "Ailerons? Check. Rudder? Check."
This is known as lockstep acknowledgement, which is slow but has a number of advantages.
To begin with, the two parties never get out of sync. If the co-pilot didn't wait for the "check" before asking the next question, he might end up going too fast--question would pile on question until the pilot became overwhelmed. In computer parlance, keeping things at the right speed is called flow control. There are many schemes for doing this, but lockstep is one of the simplest.
Another significant benefit to lockstep is that there's only one thing happening at any given moment. In the case of a preflight check, this is so the pilot can focus entirely on checking for malfunction.
If the co-pilot mashed a couple of checks together: "Aerlons, rudder, elevators?", the pilot would have to remember three things at once. Furthermore, if he responded "Check, fail, check" the co-pilot would have to accurately recall what the second check was.
TFTP uses lockstep acknowledgement as both flow control and a means of error correction. A typical exchange would look like this:
"Here's the first letter."
"OK, got the first letter."
"Here's the second letter."
"OK, got the second letter."
The sender awaits an acknowledgement, and if it doesn't receive one it simply resends the packet until it does. But how does the sender decide if the packet is really lost? This brings us to timeouts.
Hello... Hello?
The essence of a timeout is: when all else fails, wait a bit, and then try again. It's a crude method, but it allows recovery from a wide range of failures. Imagine a conversation at the top of a lighthouse in a gale--a man opens the door and steps outside...
Man1: "Windy day!"
Man2: "What?"
Man1: "Huh? I didn't hear you!"
Man2: "What?"
Both parties give up. The man waits for a second and tries again:
Man1: "Windy day!"
Man2: "Ohh! Yeah."
The Internet is a very windy place--electronic counterparts of that conversation happen all the time. Timeouts are a last bulwark against total confusion.
However, timeouts have drawbacks, which is why they are often used only as safety nets. There can be a lot of time wasted between the message being lost and the clock running out, or the receiver might give up too soon.
Humans have an intuitive sense of time: the term "give me a sec" can mean anything from five seconds to five minutes depending on the context. Computers, on the contrary, have lousy intuition--they need to be told exactly how long to wait, down to the microsecond. So a human has to decide in advance how long "enough" should be.
As you can imagine this isn't an ideal solution. It's telling that the TFTP specification talks a great deal about timeouts, but never tells you how long they should be. Ultimately, the coder simply has to guess.
Of course, that's still better than the alternative, which is to wait forever.
Send in the Pocket Protectors!
In 1948, Claude Shannon published a paper called "A Mathematical Theory of Communication". It sparked off an entire field of science devoted to studying what happens to a signal in the midst of noise.
The three basic building blocks which we've looked at--redundancy, acknowledgement, and timeouts--seemingly simple, are actually real head-scratchers for these scientists. For instance: there are countless ways to put redundancy into a signal, but which is the best, and how much is needed over a static-sounding phone line? How about a fibre optic strand? Or a cell phone in a subway? Acknowledgement and flow control mechanisms range from the Neanderthal (like TFTP's) to the subtly nuanced. But like Zeno's paradox, we can't ever get all the way to either 100 percent guaranteed correct communication or complete transfer efficiency. Both can only be approached asymptotically.
And the stakes are high--depending on the circumstances, error correction as a percentage of transfer cost can reach up into the double digits. On your LAN it's not much of a big deal, but imagine sending program code to Mars probes, or bits to and from a 15,000 RPM hard drive, or data between thousands of p2p nodes. Shaving off a fraction of a percent of overhead is a big deal.
Billions of dollars are spent each year on cramming as much accurate information down a wire or through the air as possible and still resisting nature's idle meddling. Some of the best minds of our time have devoted their lives to it.
And to think, all this, just to say HELLO.
