`18 Reliable Networks`

In chapter 16, we saw how the transmission of data could be protected by error-correcting codes, so that information could be received accurately in spite of occasional noise. Such codes are an important ingredient in getting reliable communication, but not the whole story. Although such codes can correct or detect a small number of bits lost or garbled, often there’s a bigger failure to be overcome. In a typical packet network, a whole packet (of many bits) can be lost all at once. What can we do to ensure that communication still succeeds despite that kind of loss?

`Guaranteed Delivery?`

We could try to build the network so that it guarantees delivery of every message, but that approach doesn’t work out as well as we might hope. Let’s consider what would be required for guaranteed delivery. The network is handling various messages that are sent at unpredictable times by different sending parties, traversing the network to reach various other parties. Because we don’t know in advance who will send a message or to whom they’ll send it, we could have a situation where an unusually popular destination or path exhausts its resources—for example, it could run out of space for holding messages.

If we’re building a network that guarantees delivery, we can’t allow any situations in which the network runs out of resources. So guaranteed delivery also requires guaranteed space at every step along the delivery path. To have guaranteed space at every step we have to both determine a path and reserve resources all the way from sender to receiver.

What’s strange about those requirements is that we already considered and rejected this path-reserving approach when we first looked at data networking (chapter 14). So did we make the wrong choice when we argued in favor of packet networks instead of end-to-end connections? No. Packet networks are a better overall choice, especially if the communications are bursty rather than constant—and as we noted previously, bursty communication is very common. The end-to-end reservation is expensive: effectively, each transmission from sender to receiver may require crossing the network twice. The first network crossing finds a suitable path and reserves the needed space, and the second network crossing actually transmits the data.

Worse is that building a network with guaranteed delivery is not only expensive but also ultimately futile. Even with all of those reservations, we still can’t really guarantee delivery. After all, it’s still possible that a component along the reserved path might fail. In any of those occasional failure situations, all of the carefully arranged reservations won’t make any difference.

`Redundant Messages`

What can we do instead of guaranteed service? Can we build an error-correcting code so that it could replace a whole lost message? Yes, but it’s often not an attractive approach. If we want to be able to recover hundreds or thousands of lost bits, the error-correcting code will involve sending hundreds or thousands more bits. That error correction will take a substantial fraction of the communication capacity available, in a super-cautious effort to recover in case some message is lost. Although there are systems that work this way, most of the time this approach is wasteful. The loss of a packet occurs only occasionally, while the overhead cost of the extra bits is a burden all of the time.

What we really want instead is to send a second or third copy of a message only when it’s needed. It’s still a redundancy strategy, but now, instead of sending redundant information all of the time, we’re just keeping one extra copy on hand to resend as needed.

`The End-to-End Principle`

We assume that the network will at least try to deliver each message—this is what is sometimes referred to as a “best effort” service—but there’s no guarantee of success. How should we think about organizing communication to achieve reliability? Computer scientists have a term for this approach: the end-to-end principle. We can put this principle into some everyday terms: if someone is asking you whether you received a phone call, they ask you—not the phone company. Or if someone is asking you if you received a letter, they ask you—not the post office. If you didn’t receive a call, it doesn’t matter what the phone company says about the call. Likewise, if you didn’t receive a letter, it doesn’t matter what the post office says about getting it to somewhere near you.

The phone company or post office might have relevant information if there is a disagreement about whether you have received a call or letter, but their view of success can’t be substituted for yours as the ultimate recipient of a call or letter.

For example, in a postal service there are “return reply” postcards that may be signed by the recipient—not by the post office!—and returned to the original sender. Such a postcard conveys that the sent item was actually received, not just delivered.

The lesson from these examples is the principle that applies to data networking in general: even if the network were completely reliable in its task, that still wouldn’t guarantee reliable delivery to the recipient. There could still be a failure between the network service itself and whatever or whoever is using the network.

If we require an end-to-end mechanism to achieve real reliability, is there any point to having any kind of guaranteed delivery? Yes, but the value is a little different from what we might have thought. It’s possible—but by no means certain—that a guaranteed-delivery network offers improved performance. Resending a message all the way from sender to recipient may take a while, and it may be smart to avoid that cost. But that possible performance benefit is quite different from a reliability guarantee.

`Acknowledgment and Retransmission`

So far, we’ve concluded that a guaranteed-delivery network is not the same as reliable end-to-end communication; indeed, a guaranteed-delivery network is arguably an expensive way of solving the wrong problem if what we really want is reliable end-to-end communication. Instead of a guaranteed-delivery network, we need to add two elements:

1. Acknowledgment of received messages, and
2. Retransmission of lost messages

Actually getting these two elements to work typically requires some additional machinery. In particular, the sender needs some way to figure out when a message has been lost. The lost message doesn’t announce itself. Instead, just like when a letter is lost in a postal system, the sender has to judge when a message is lost.

As in a postal system, the key input for the judgment is elapsed time since sending. The sender needs a timer to estimate a reasonable span of time for the message to be sent and the corresponding acknowledgment to be received. If a message is acknowledged within the expected time, that is success (for that particular message). But if a message has not been acknowledged within the expected time, it has to be declared as lost. Then the message is retransmitted.

Getting the timer right can be hard. If the timer is too long, then the sender wastes time waiting whenever a message is genuinely lost. If the timer is too short, the sender will resend messages unnecessarily. Each unnecessary resent message causes no confusion for the receiver, who can easily discard it. But sending the extra message wastes time and network capacity that could have been used for sending useful messages.

`Multiple Acknowledgments and Negative Acknowledgments`

Once we’ve seen how a single-message system works, it’s not hard to see how we could send more than one message at a time. There has to be some kind of labeling of the different messages and their corresponding acknowledgments, so we can tell which acknowledgment is for which message. A really simple system that allows up to three messages in flight might call them “red,” “green,” and “blue.” Each time we send a message, we’d say which color slot we were using, and we’d have different-color timers and matching-color acknowledgments.

Or instead of using colors, we could use numbers like 1, 2, 3. If we use numbers, that makes it easier to see how we could keep expanding the number of slots in use—we could just add the next-higher number if we wanted to use an additional slot.

Using numbers, it also becomes easier to have a single acknowledgment indicating that multiple messages have been received. Usually, messages don’t get lost. (In environments where we expect to lose lots of messages we might well return to the error-correcting code approach we previously considered too wasteful.) So rather than sending an acknowledgment for 1, followed by an acknowledgment for 2, followed by an acknowledgment for 3, we could send an acknowledgment for 3 that implicitly acknowledges the receipt of 1 and 2.

In a system where a particular acknowledgment implicitly acknowledges all of the previous numbers, we need a different way of handling a situation in which we have received most of the messages but are missing some. The solution is to use negative acknowledgments. Whereas ordinary acknowledgments signal that the receiver has successfully received the corresponding message(s), negative acknowledgments signal that the receiver has found a “hole” in the received message sequence and is requesting a resending of what’s missing.

Even as we increase the sophistication of our acknowledgments, the underlying strategy remains the same:

1. The sender retains a copy of each message until it’s acknowledged.
2. If any message remains unacknowledged within a reasonable time, the sender assumes that the message is lost.
3. The sender retransmits a message if it seems to have been lost.

In practice, this work of reliable transmission is almost always handled on the internet by the protocol called TCP. We encountered TCP already in chapter 15. When you use the internet, TCP is just another piece of the invisible plumbing, rather than something that you’re likely to interact with directly. But it’s worth being aware that TCP is the underlying mechanism used for web traffic, email, and many other less common uses of the internet. In the vast majority of cases where it’s important to be sure that all of the packets get across the network, TCP is involved.

`Congestion Collapse`

When we looked at reliable storage, we overcame individual component failures by using groups of components. Then, when we looked at reliable networking, we overcame individual message loss by using multiple messages as needed. This pattern might leave an impression that groups are always better for reliability, but that would be an incomplete picture. To better round out our understanding, it’s also worth looking at a problem that arises only from groups.

We have already seen one kind of group-only problem. We previously mentioned gridlock as one kind of failure that arises in non-computer settings (chapter 8). Gridlock simply can’t occur when there’s only a single entity taking actions—there’s no one else to “gridlock with.”

Another kind of failure that requires multiple players is called congestion collapse. To understand it, let’s start with a simple model: a single sender/receiver pair and some external, otherwise-unspecified source of interference. The sender and receiver communicate easily in the absence of interference but have increasing difficulty as the level of interference increases. As interference increases, more messages are lost and need to be retransmitted. As the loss rate increases, there is a corresponding decrease in the efficiency of the transmission between sender and receiver. We can still get reliable communication by retransmitting lost messages. But that communication is both slower (because of the delay caused by retransmission) and less efficient in the use of capacity (because some messages are transmitted more than once). The more likely a loss is, the longer it takes for any single message to be successfully transmitted. So far, this is just a simple statement of the problems for a single communicating pair, as interference increases.

We start to get an inkling of the problem of congestion collapse when we realize that in a shared network, each transmitting process is not only trying to communicate—it is also, from the perspective of every other transmitting process, a potential source of interference. If the sender/receiver pairs were completely isolated from each other, they wouldn’t affect each other. But since they are using some of the same resources in the shared network, they are competing and potentially interfering. As we increase the density of attempted communication, we are not only increasing the number of sources of traffic—we are also, intrinsically, increasing the number of sources of interference.

Congestion collapse is an unintended consequence of our otherwise sensible system for achieving reliable delivery. The hold-message-until-acknowledged approach works fine as long as losses are relatively rare. If losses don’t happen very often, then the retransmissions typically succeed. However, we can run into trouble as losses happen more often. More losses cause more retransmissions, which in turn cause more losses. What is an individually sensible strategy becomes madness when applied by all parties.

In congestion collapse, everyone may be very “busy” but they are not accomplishing anything. Like a cocktail party in which everyone is talking but no one is listening, it is loud but not useful. It is the networking equivalent of thrashing, which we previously encountered briefly in our discussion of coordination (chapter 8). Everyone’s transmitted traffic is dropped and has to be retransmitted. But since every other sender’s traffic is likewise being dropped and then has to be retransmitted, nothing much happens. Congestion collapse is not a merely theoretical concern—it was a real-world problem that affected the internet in October 1986. That incident led to the urgent study of the problem and a search for solutions.

`Congestion Control`

How can we avoid congestion collapse? As with the cocktail party where everyone is talking at once, we have to create some space for real conversation by reducing interference. Congestion collapse occurs because everyone is eager to talk, creating a situation in which no one actually succeeds at being heard. Avoiding congestion collapse requires that everyone be prepared to stop talking, creating a situation in which some communication succeeds. To avoid congestion collapse, a reliable-communication protocol like TCP needs to include some kind of congestion control mechanism that causes it to do three things:

1. send at a slow rate initially;
2. build up communication speed gradually; and
3. sharply reduce its communication speed at the first sign of congestion.

Most TCP implementations use an implicit form of congestion control. With implicit congestion control, the sender assumes that the loss of a message means that the network is congested; the sender then reduces its sending rate.

However, not all message failures or losses are caused by congestion. Depending on the kind of network being used, there may be other reasons why a message could be lost. For example, a mobile telephone may be in an area with no wireless service. Attempts to send messages fail, but that kind of loss just happens because of circumstances of geography—it’s completely unrelated to any kind of congestion in the network.

In environments where noncongestion losses are frequent, TCP implementations with implicit congestion control don’t perform very well. A TCP implementation that interprets every message loss as congestion will tend to slow down when it doesn’t really need to. Alternative protocols have been designed for those environments: some are variants of TCP, while others are completely unrelated protocols. A common feature is that they don’t consider a single packet loss to be a signal of congestion. Some protocols rely on explicit signals of congestion from the network, while others perform a more sophisticated analysis on the patterns of loss to better infer the presence or absence of congestion.

`Cheating on Congestion Control`

In an ideal world, everyone sharing a network would implement congestion control consistently. Consistent use of congestion control means that everyone’s results are better than without congestion control. Unfortunately, communication over a network typically happens between distant, autonomous parties. Accordingly, congestion control requires cooperation among those independent entities. Getting the right result is not like changing the laws of a single country. It’s more like negotiating an international treaty.

Consider what happens if only two senders cheat on the convention by not implementing any congestion control. That deviation from the norm can be sufficient to induce congestion collapse, even if everyone else implements congestion control. The two cheating senders can potentially grab all the available resources and more, interfering with each other and all the other senders.

That might be the end of the story, with the moral that everyone needs to implement congestion control. But it’s a little more complex than that. Curiously, a single cheater won’t induce congestion collapse, and the cheater will get unusually good service as a result of grabbing more than their fair share. After all, if there’s only one blabbermouth at a party, they are clearly heard by everyone else.

Accordingly, a chronic problem in real networks is convincing senders not to cheat on congestion control. Many people who are reasonably familiar with networks in their everyday life don’t know about the risk of congestion collapse. A possible comparison would be to people who operate a ferry and don’t understand the risk of sinking; they might be tempted to discard all that “useless bulk” of life vests and rafts.

Sometimes the discarding of congestion control shows up as a networking vendor who has “invented” a great new way to improve performance. Other times, it shows up as a user who has “discovered” that they can adjust their local settings to get dramatically improved performance. The problem is hard to prevent entirely, because each initial attempt at cheating yields excellent results for the first single cheater. However, the apparent success produces a widespread failure if others do likewise. What initially seems to be a promising business model or brilliant insight turns out to be a catastrophe when used more widely.