End-to-End Arguments in System Design

On Sunday, July 20, 2008, error rates in every Amazon S3 data center started to climb. By the AWS team's own account, the cause was "a handful of messages" between S3's servers that "had a single bit corrupted such that the message was still intelligible, but the system state information was incorrect." S3's servers spread state to each other by gossiping, so the wrong state spread too, until very few requests completed. Engineers shut down all communication between the servers, cleared the system's state and restarted; the US region was back to normal more than eight hours after the errors began.

One way to catch a flipped bit is a checksum: a short number computed from the data and sent along with it, so the receiver can compute it again and spot a change. S3 already used MD5 checksums to protect the files its customers stored. Still, that one bit got through, because nothing checked those internal messages. The postmortem does not say where the bit flipped or what carried the messages; what it does say is that this internal state had no such protection. The fix was to add checksums to them, "so we can log any such messages and then reject them." So when data crosses a whole chain of machines and programs, which part of the chain should check that it arrived intact? A 1984 paper from MIT answers that question.

Where Does a Function Go?

In the early 1980s, networks were becoming a normal part of computer systems. Designers drew a firm boundary around the network, the communication subsystem, with the programs that use it on either side. For each useful job there was a placement choice: encryption, catching duplicate messages, keeping messages in order, guaranteeing delivery, noticing when a computer crashed, and sending delivery receipts could each live in the network, in the program that uses it, in both, or split between the two.

Jerome Saltzer, David Reed and David Clark (MIT Laboratory for Computer Science) published their answer in ACM Transactions on Computer Systems in November 1984, a revised version of their paper from a 1981 conference in Paris. They work the whole answer out on one concrete job.

Careful File Transfer

A file sits on the disk of computer A. You want an exact copy on the disk of computer B, with a network in between. The file transfer program has two halves, one on each computer, and the paper lists five steps:

1. On A, the program asks the file system to read the file, which hands it over in fixed-size blocks.
2. The program passes the blocks to the communication system, which splits the data into packets, the small pieces a network carries one at a time, of a different size than the blocks.
3. The network carries the packets from A to B, perhaps through gateways, computers that pass packets from one network to the next.
4. On B, the communication program unpacks the data and hands it to the other half of the file transfer program.
5. That program asks B's file system to write the data to B's disk.

Five Threats

A careful designer would worry about all of these (p. 279):

The obvious plan is to harden every step with duplicate copies, timeouts and retries, error checks and crash recovery. The paper rejects it on two counts. Threat 2 alone means writing correct programs, "which is quite difficult," and "not all the programs that must be correct are written by the file transfer-application programmer." And if the threats are rare, "brute force countermeasures, such as doing everything three times, appear uneconomical."

End-to-End Check and Retry

The alternative needs one new step. Store a checksum with the file, a short number computed from its contents, with enough extra bits that an undetected error is acceptably unlikely. Move the file through the five steps with no extra care. Then the program on B reads its copy back from its own disk, recomputes the checksum and sends it to A, which compares it with the checksum of the original. Only if they match is the transfer committed; otherwise it is retried from the beginning.

Every threat ends the same way: a bad disk, a buggy copy, a memory error or a damaged packet shows up as a mismatch, and a crash halfway means nothing is committed. If failures are rare, the first try usually works, and the paper suggests that two or more failures on one file mean some part of the system needs repair.

A Perfect Network?

Now take the common proposal: let the network guarantee reliable delivery itself, with packet checksums, sequence numbers and internal retries, until undetected bit errors are as rare as you like. Could you then delete the end-to-end check?

No. A perfect network removes threat 4 and only threat 4. Threats 1, 2, 3 and 5 live outside the network, so the file transfer program "should still provide its own retries based on an end-to-end checksum of the file." Once it does, the network's extra effort "is only reducing the frequency of retries by the file transfer application; it has no effect on inevitability or correctness of the outcome."

What the Paper Says

The argument, in three sentences:

The function in question can completely and correctly be implemented only with the knowledge and help of the application standing at the endpoints of the communication system. Therefore, providing that questioned function as a feature of the communication system itself is not possible. (Sometimes an incomplete version of the function provided by the communication system may be useful as a performance enhancement.)

We call this line of reasoning against low-level function implementation the end-to-end argument. …

(p. 278)

In the file transfer, the function is reliable transfer, and only the transfer program at each end knows what correct means: the right bytes, on B's disk. The checks on each packet are the "incomplete version": useful, but for speed.

A Too-Real Example

The authors had a real case from MIT. A network joined several local networks through gateways, with a packet checksum on every hop from one gateway to the next, on the assumption that the main danger was bits damaged on the wire.

… Application programmers, aware of this checksum, assumed that the network was providing reliable transmission, without realizing that the transmitted data were unprotected while stored in each gateway.

One gateway computer developed a transient error: while copying data from an input to an output buffer a byte pair was interchanged, with a frequency of about one such interchange in every million bytes passed. …

… Some of these source files were corrupted by byte exchanges, and their owners were forced to the ultimate end-to-end error check: manual comparison with and correction from old listings.

(p. 280)

Every hop's checksum still passed, because each hop only checked its own wire and the swap happened in between, inside the gateway. In our illustrative example, a line retries = 10; arrives as retries = 01; and nothing complains.

The Performance Exception

So should the network do nothing? The paper says that would be too simple. Take a network that drops one packet in every hundred, and assume, as a simplification, that losses are independent. With only the end-to-end check, one lost packet means resending the whole file:

If the network instead resends each lost packet by itself, those 1,000 packets cost about 1,010 sends. (These numbers are worked out from the paper's 1-in-100 example; the paper itself says only that the chance "decreases exponentially with the file length.")

… But the key idea here is that the lower levels need not provide "perfect" reliability.

Thus the amount of effort to put into reliability measures within the data communication system is seen to be an engineering trade-off based on performance, rather than a requirement for correctness. …

(p. 281)

Who Pays for the Low Level

A function placed low in the stack has costs of its own: bandwidth spent on redundant data, and delay while the network waits for its own checks. The paper adds two reasons a low-level version can cost more overall:

• the network is shared by many applications, so "those applications that do not need the function will pay for it anyway";
• the network "may not have as much information as the higher levels, so it cannot do the job as efficiently."

Its example is live speech, which "has tighter constraints on message delay than on bit-error rate," while "most retry schemes significantly increase the variability of delay."

Where should the early, performance-only checks go? The end-to-end argument does not say; either layer can do it. Hop by hop in the network, a failure is fixed sooner, but an application that does not want the check "has no choice in the matter." In the application, the network stays simple, but every application builds its own. The paper's advice: start with the reliability that comes cheaply, then check that the errors left over cause an acceptable number of retries.

The Same Argument, Other Functions

Delivery receipts. The ARPANET sent back a packet called Request For Next Message (RFNM) every time it delivered a message. That was useful inside the network for congestion control, but in the paper's words it "was never found to be very helpful for applications." Delivery is not completion: the program on the other end can still crash or refuse. What the sender wants is an answer only the target application can give: "I did it," or "I didn't." TCP, the protocol built for reliable delivery between two computers, says the same of its own acknowledgments in its 1981 specification: "An acknowledgment by TCP does not guarantee that the data has been delivered to the end user, but only that the receiving TCP has taken the responsibility to do so." When an action must happen only if actions on other computers also succeed, you need a two-phase commit, which the paper calls "a sophisticated end-to-end acknowledgment."

Encryption. If the network encrypts, it must be trusted with the keys; the data is in the clear again inside the target computer; and the program still has to check the message is authentic. Encrypting end to end, in the program, gives it its own authentication check and its own keys, and the data is never exposed outside it. The paper keeps network-level encryption for a different need: "one more firewall" so a misbehaving user or program cannot deliberately leak data, simple enough that one key can serve every host. "Neither mechanism can satisfy both requirements completely."

Duplicates. A network can deliver the same message twice when its own retry fires, and it could suppress those copies. But the program makes duplicates of its own: a user who sees no response logs in again, or a program mistakes a lost or late reply for a crash and sends the request again. To the network that retry is a new message, so only the program can recognize it, and once the program has that mechanism, it catches the network's duplicates too. Payment APIs work this way today. Stripe's documentation: "A client generates an idempotency key, which is a unique key that the server uses to recognize subsequent retries of the same request." Retry with the same key after a connection error, and Stripe will not create a second object or do the update twice.

Order. A network can keep messages on one connection first in, first out. But when one computer starts actions at several sites over separate connections, nothing orders them across connections, so something above the network must.

Transactions. The authors applied all of this in their own storage system, SWALLOW. Its message layer does not suppress duplicates (an object's identifier and version reveal a repeated write; a repeated read only produces an extra reply the sender discards) and does not send delivery acknowledgments (a write needs to know the data "were stored safely," which only the storage can say, and a read's reply is its own acknowledgment). Dropping the acknowledgments halved the number of messages.

Identifying the Ends

The ends are not always obvious. For a live phone call carried as packets, a network that insists on perfect bits resends damaged packets and holds back later ones, and the delay wrecks the conversation. Better to play a damaged packet, or silence, and let the people repair it: "excuse me, someone dropped a glass. Would you please say that again?" Store the same packets as a voice message, though, and the answer flips: short delays don't matter, accuracy does, because the listener cannot ask the sender to repeat a sentence.

… Thus the end-to-end argument is not an absolute rule, but rather a guideline that helps in application and protocol design analysis; one must use some care to identify the endpoints to which the argument should be applied.

(p. 285)

The paper also says none of its examples is new. A bank's audits catch both a withdrawal from the wrong account and coordination errors in the database underneath. An airline agent keeps trying until a booking is confirmed or refused. Telephone exchanges don't recover a single lost call, because "the caller will probably replace the call if it matters." In the 1950s, attempts to build a reliable magnetic tape subsystem kept failing until every application provided its own checks. Even the debate between datagrams (packets routed on their own) and virtual circuits (connections the network keeps) is, the authors say, "a debate about end-to-end arguments." Their conclusion calls the argument a kind of "Occam's razor": because the network is designed before its applications are known, its designers are tempted to "help" by taking on more function than necessary.

Where It Lives Today

Amazon S3 uploads. The S3 user guide describes a client-to-service upload integrity check: "For uploads, all AWS-owned clients calculate a checksum of the object and send it with the upload request. S3 then independently calculates a checksum value of the object on the server-side, and validates it with the provided value before storing the object and checksum value." If the values don't match, the request is rejected with a BadDigest error, and the checksum is kept with the object so it can be validated later. This check compares the upload before storage; the guide does not describe the paper's further step of reading the stored copy back from disk before commit.

TCP's checksum still earns its place. It is a 16-bit ones' complement sum on every segment, each chunk of data TCP sends. In traces of real Internet traffic, Stone and Partridge (SIGCOMM 2000) found "between 1 packet in 1,100 and 1 packet in 32,000 fails the TCP checksum," with errors coming from host hardware, host software and router memory, not only the wire. They estimated that the checksum misses errors in "roughly 1 in 16 million to 10 billion packets," and concluded that "some applications should employ application-level checksums or equivalents." That is the same kind of fix S3 made in 2008.

Identify your end. S3's check covers the bytes from the SDK to S3. Whether those were the bytes you meant, on your own disk, is still your end's job.

What Aged

The ends stopped trusting each other. In 2001, David Clark, one of the three authors, wrote with Marjory Blumenthal that "the examples in the original end-to-end paper assume that the end-points are in willing cooperation to achieve their goals. Today, there is less and less reason to believe that we can trust other end-points to behave as desired." Making the network trustworthy when the ends are not "seems to imply more mechanism in the center of the network." They point to firewalls that "inspect passing network traffic and reject communications," and to address translators that modify the addresses in packets.

Middleboxes froze the transport, so the transport moved to the ends. Google's QUIC paper (SIGCOMM 2017) describes middleboxes as "key control points in the Internet's architecture" that block unfamiliar traffic and rewrite transport headers. QUIC runs as "a user-space transport with UDP as a substrate" and "encrypts transport headers," "limiting ossification of the protocol by middleboxes." In October 2016, a 1-bit change to one header field "resulted in pathological packet loss for users behind one brand of firewall," and the change was reverted. It is the end-to-end argument pushed further: the transport itself moved into the application.

Costs Lampson named in 1983. Butler Lampson's Hints for Computer System Design credits the observation to Saltzer and lists two problems with the end-to-end strategy: "it requires a cheap test for success," and it "can lead to working systems with severe performance defects that may not appear until the system becomes operational and is placed under heavy load."

The Takeaway

Data crosses disks, programs, memory and networks, and any of them can damage it. Checks in the middle make failures rarer and are worth paying for when failures are common. But only the ends know what correct means, so only a check at the ends can promise it.

Put the guarantee where correct is defined, at the ends, and treat every check below them as a way to go faster.

Lampson filed this rule in a whole notebook of design advice, and he says many of his hints apply the same idea: a hint is saved information that "may be wrong," so "there must be a way to check its correctness before taking any unrecoverable action." Which raises the question that Lampson's Hints for Computer System Design takes up: what other rules belong in that notebook, and why would a good system depend on information that might be wrong?

References

• J. H. Saltzer, D. P. Reed, D. D. Clark, "End-To-End Arguments in System Design," ACM Transactions on Computer Systems 2(4), November 1984, pp. 277 to 288. ACM Digital Library; the authors' copy at web.mit.edu.
• Amazon Web Services, "Amazon S3 Availability Event: July 20, 2008." Archived copy.
• Amazon S3 User Guide, "Checking object integrity in Amazon S3" and "Checking object integrity for data uploads in Amazon S3." docs.aws.amazon.com.
• Jonathan Stone, Craig Partridge, "When The CRC and TCP Checksum Disagree," SIGCOMM 2000. PDF.
• RFC 793, "Transmission Control Protocol," September 1981, and RFC 9293, 2022. rfc-editor.org.
• Stripe API reference, "Idempotent requests." docs.stripe.com.
• Marjory S. Blumenthal, David D. Clark, "Rethinking the Design of the Internet: The End-to-End Arguments vs. the Brave New World," ACM Transactions on Internet Technology 1(1), August 2001, pp. 70 to 109. PDF.
• Adam Langley et al., "The QUIC Transport Protocol: Design and Internet-Scale Deployment," SIGCOMM 2017. PDF.
• Butler W. Lampson, "Hints for Computer System Design," 1983. PDF.
• RFC 1983, "Internet Users' Glossary," 1996 (definitions of datagram, virtual circuit, congestion). rfc-editor.org.