RFC 817

Modularity and efficiency in protocol implementation

📅 published July 1982, from ietf

RFC 817 🎀 Modularity and Efficiency in Protocol Implementation

okay bestie, this one is from July 1982 and it's written by David D. Clark from the MIT Laboratory for Computer Science, specifically the Computer Systems and Communications Group 🧑‍💻✨. The title block doesn't list a category or status, and it doesn't say what it obsoletes or updates, so we're just going off the facts we've got 🫶.

1. Introduction ✨

okay so MANY protocol implementers have had the sad realization that their packages don't run as fast as they hoped 😭. People blame all kinds of stuff for this, from details in the protocol design to the underlying structure of the host operating system 🧩. This RFC is going to go through some of the commonly encountered reasons why protocol implementations seem to run slowly 🐢.

experience says one of the most important factors for how an implementation performs is how it's modularized and plugged into the host operating system 🔌. so it makes sense to talk about how an implementation is structured at the same time as how it will perform 💅. honestly, this RFC is going to argue that modularity is one of the chief villains when you're trying to get good performance 😤. so the designer ends up facing a delicate and inevitable tradeoff between good structure and good performance ⚖️. and the single factor that most strongly decides how well that conflict gets resolved? not the protocol. it's the operating system 👑.

2. Efficiency Considerations 🧮

efficiency has lots of sides, bestie 💖. one is sending data at minimum transmission cost, which is critical for common carrier communications, if not local area network communications 📡. another is sending data at a high rate, which may not be possible at all if the net is very slow, but which may be the one central design constraint when you're using a local net with high raw bandwidth 🚀. the final consideration is doing all of the above with minimum expenditure of computer resources 🖥️. that last one may be necessary to achieve high speed, but on a slow net it may only matter because the resources being used up, like CPU cycles, are costly or otherwise needed 💸.

it's worth pointing out that these goals often conflict 🙈. for example, it's often possible to trade efficient use of the computer against efficient use of the network. so there may be no such thing as a successful general purpose protocol implementation 💀.

the simplest measure of performance is throughput, measured in bits per second 📊. it's worth doing a few simple computations to get a feeling for the magnitude of the problems involved 🧠. say data is being sent from one machine to another in packets of 576 bytes, which is the maximum generally acceptable internet packet size 📦. allowing for header overhead, that packet size leaves room for 4288 bits in each packet 🧾.

if a useful throughput of 10,000 bits per second is the goal, then a data bearing packet has to leave the sending host about every 430 milliseconds, which is a little over two per second. this is clearly not difficult to achieve 😌. but if you want 100 kilobits per second, the packet has to leave the host every 43 milliseconds 🏃‍♀️. and to hit one megabit per second, which is not at all unreasonable on a high-speed local net, the packets must be spaced no more than 4.3 milliseconds apart 🔥.

these latter numbers are a lowkey alarming goal to set your sights on 😱. many operating systems take a substantial fraction of a millisecond just to service an interrupt 🫠. if the protocol has been structured as a process, you have to go through process scheduling before the protocol code can even begin to run 🗓️. if any piece of a protocol package or its data has to be fetched from disk, real time delays of 30 to 100 milliseconds can be expected 💿. and if the protocol has to compete for CPU resources with other processes on the system, it may need to wait a scheduling quantum before it can run ⏳. many systems have a scheduling quantum of 100 milliseconds or more 😵. considering these sorts of numbers, it becomes immediately clear that the protocol has to be fitted into the operating system in a thorough and effective manner if any reasonable throughput is going to be achieved 🫶✨.

there's one obvious conclusion that even this simple analysis suggests 💡. except in very special circumstances, when many packets are being processed at once, the cost of processing a packet is dominated by factors, like CPU scheduling, that are independent of the packet size 📉. this suggests two general rules that any implementation ought to obey 📜. first, send data in large packets. obviously, if processing time per packet is a constant, then throughput will be directly proportional to the packet size 📈. second, never send an unneeded packet 🚫. unneeded packets use up just as many resources as a packet full of data, but they perform no useful function 🗑️. RFC 813, "Window and Acknowledgement Strategy in TCP", discusses one aspect of reducing the number of packets sent per useful data byte 🪟. this document will mention other attacks on the same problem 🗡️.

the analysis above suggests there are two main parts to the problem of achieving good protocol performance 🧩. the first has to do with how the protocol implementation is integrated into the host operating system 🖇️. the second has to do with how the protocol package itself is organized internally 🗂️. this document will consider each of these topics in turn 🫡.

3. The Protocol vs. the Operating System 🖥️

there are normally three reasonable ways to add a protocol to an operating system 🛠️. the protocol can be in a process that's provided by the operating system, or it can be part of the kernel of the operating system itself, or it can be put in a separate communications processor or front end machine 🖧. this decision is strongly influenced by details of hardware architecture and operating system design, and each of these three approaches has its own advantages and disadvantages ⚖️.

the "process" is the abstraction most operating systems use to provide the execution environment for user programs 🏃. a very simple path for implementing a protocol is to obtain a process from the operating system and implement the protocol to run in it 🛤️. superficially, this approach has a number of advantages 🌸. since modifications to the kernel aren't required, the job can be done by someone who isn't an expert in kernel structure 🙌. and since it's often impossible to find somebody who's experienced both in the structure of the operating system and in the structure of the protocol, this path is, from a management point of view, often extremely appealing 💼. unfortunately, putting a protocol in a process has a number of disadvantages, related to both structure and performance 😬. first, as was discussed above, process scheduling can be a significant source of real-time delay ⏰. there's not only the actual cost of going through the scheduler, but also the problem that the operating system may not have the right sort of priority tools to bring the process into execution quickly whenever there's work to be done 🚨.

structurally, the difficulty with putting a protocol in a process is that the protocol may be providing services, like support of data streams, that are normally obtained by going to special kernel entry points 🚪. depending on the generality of the operating system, it may be impossible to take a program that's used to reading through a kernel entry point and redirect it so it reads the data from a process 🙅‍♀️. the most extreme example of this problem happens when implementing server telnet 📟. in almost all systems, the device handler for locally attached teletypes is located inside the kernel, and programs read and write from their teletype by making kernel calls 🧾. if server telnet is implemented in a process, you then have to take the data streams server telnet provides and somehow get them back down inside the kernel so they mimic the interface provided by local teletypes 🌀. usually this needs special kernel modification, which kind of defeats the benefit of having removed the protocol from the kernel in the first place 🤦‍♀️.

so clearly, there are advantages to putting the protocol package in the kernel 💜. structurally, it's reasonable to view the network as a device, and device drivers are traditionally contained in the kernel 🔌. presumably, the problems associated with process scheduling can be sidestepped, at least to a certain extent, by placing the code inside the kernel 🥷. and it's obviously easier to make server telnet channels mimic local teletype channels if they're both realized at the same level in the kernel 🎯.

however, implementing protocols in the kernel has its own set of pitfalls 🕳️. first, network protocols have a characteristic that's shared by almost no other device: they require rather complex actions to be performed as a result of a timeout ⏱️. the problem with this requirement is that the kernel often has no facility by which a program can be brought into execution as a result of a timer event 😩. what's really needed is a special sort of process inside the kernel 🧚. most systems lack this mechanism 🙃. failing that, the only execution mechanism available is to run at interrupt time ⚡.

⚠️ there are substantial drawbacks to implementing a protocol to run at interrupt time, bestie. first, the actions performed may be somewhat complex and time consuming, compared to the maximum amount of time the operating system is prepared to spend servicing an interrupt 🥵. problems can arise if interrupts are masked for too long. this is particularly bad when running as a result of a clock interrupt, which can imply that the clock interrupt is masked 🕰️. second, the environment provided by an interrupt handler is usually extremely primitive compared to the environment of a process 🪨. there are usually a variety of system facilities that are unavailable while running in an interrupt handler 🚫. the most important of these is the ability to suspend execution pending the arrival of some event or message 🛑. it is a cardinal rule of almost every known operating system that one must not invoke the scheduler while running in an interrupt handler 🙅. so the programmer who's forced to implement all or part of their protocol package as an interrupt handler must be the best sort of expert in the operating system involved, and must be prepared for development sessions filled with obscure bugs that crash not just the protocol package but the entire operating system 💥😭.

a final problem with processing at interrupt time is that the system scheduler has no control over the percentage of system time used by the protocol handler 🎛️. if a large number of packets arrive from a foreign host that is either malfunctioning or fast, all of the time may be spent in the interrupt handler, effectively killing the system ☠️.

there are other problems associated with putting protocols into an operating system kernel 🧷. the simplest problem often encountered is that 👀

the kernel address space is simply too small to hold the piece of code in question 🥲 this is a rather artificial sort of problem, but it is a severe problem none the less in many machines. it is an appallingly unpleasant experience to do an implementation knowing that for every byte of new feature you put in, you must find some other byte of old feature to throw out 😭 it is hopeless to expect an effective and general implementation under this kind of constraint 💀 another problem is that the protocol package, once it is thoroughly entwined in the operating system, may need to be redone every time the operating system changes. if the protocol and the operating system are not maintained by the same group, this makes maintenance of the protocol package a perpetual headache 🙈

the third option for protocol implementation is to take the protocol package and move it outside the machine entirely, onto a separate processor dedicated to this kind of task ✨ such a machine is often described as a communications processor or a front-end processor. there are several advantages to this approach 🦋 first, the operating system on the communications processor can be tailored for precisely this kind of task, which makes the job of implementation much easier. second, one does not need to redo the task for every machine to which the protocol is to be added. it may be possible to reuse the same front-end machine on different host computers 🌸 since the task need not be done as many times, one might hope that more attention could be paid to doing it right. given a careful implementation in an environment which is optimized for this kind of task, the resulting package should turn out to be very efficient. unfortunately, there are also problems with this approach 😤 there is, of course, a financial problem associated with buying an additional computer. in many cases, this is not a problem at all, since the cost is negligible compared to what the programmer would cost to do the job in the mainframe itself. more fundamentally, the communications processor approach does not completely sidestep any of the problems raised above. the reason is that the communications processor, since it is a separate machine, must be attached to the mainframe by some mechanism. whatever that mechanism is, code is required in the mainframe to deal with it 🔥 it can be argued that the program to deal with the communications processor is simpler than the program to implement the entire protocol package. even if that is so, the communications processor interface package is still a protocol in nature, with all of the same structural problems. thus, all of the issues raised above must still be faced. in addition to those problems, there are some other, more subtle problems associated with an outboard implementation of a protocol. we will return to these problems later 👀

there is a way of attaching a communications processor to a mainframe host which sidesteps all of the mainframe implementation problems, and that is to use some preexisting interface on the host machine as the port by which the communications processor is attached 🎀 this strategy is often used as a last stage of desperation, when the software on the host computer is so intractable that it cannot be changed in any way. unfortunately, it is almost inevitably the case that all of the available interfaces are totally unsuitable for this purpose, so the result is unsatisfactory at best 😩 the most common way in which this form of attachment occurs is when a network connection is being used to mimic local teletypes. in this case, the front-end processor can be attached to the mainframe by simply providing a number of wires out of the front-end processor, each corresponding to a connection, which are plugged into teletype ports on the mainframe computer. (because of the appearance of the physical configuration which results from this arrangement, Michael Padlipsky has described this as the "milking machine" approach to computer networking. 🐄 iconic naming, no notes.) this strategy solves the immediate problem of providing remote access to a host, but it is extremely inflexible. the channels being provided to the host are restricted by the host software to one purpose only, remote login. it is impossible to use them for any other purpose, such as file transfer or sending mail, so the host is integrated into the network environment in an extremely limited and inflexible manner. if this is the best that can be done, then it should be tolerated. otherwise, implementors should be strongly encouraged to take a more flexible approach. 🧚

4. Protocol Layering ✨

the previous discussion suggested that there was a decision to be made as to where a protocol ought to be implemented 🤔 in fact, the decision is much more complicated than that, because the goal is not to implement a single protocol, but to implement a whole family of protocol layers. we start with a device driver or local network driver at the bottom, then IP and TCP, and eventually reach the application specific protocol on top, such as Telnet, FTP and SMTP. clearly, the bottommost of these layers is somewhere within the kernel, since the physical device driver for the net is almost inevitably located there. equally clearly, the top layers of this package, which provide the user his ability to perform the remote login function or to send mail, are not entirely contained within the kernel. thus, the question is not whether the protocol family shall be inside or outside the kernel, but how it shall be sliced in two between that part inside and that part outside 💅

since protocols come nicely layered, an obvious proposal is that one of the layer interfaces should be the point at which the inside and outside components are sliced apart 🍓 most systems have been implemented this way, and many have been made to work quite effectively. one obvious place to slice is at the upper interface of TCP. since TCP provides a bidirectional byte stream, which is somewhat similar to the I/O facility provided by most operating systems, it is possible to make the interface to TCP almost mimic the interface to other existing devices. except in the matter of opening a connection, and dealing with peculiar failures, the software using TCP need not know that it is a network connection, rather than a local I/O stream that is providing the communications function. this approach does put TCP inside the kernel, which raises all the problems addressed above. it also raises the problem that the interface to the IP layer can, if the programmer is not careful, become excessively buried inside the kernel 😬 it must be remembered that things other than TCP are expected to run on top of IP. the IP interface must be made accessible, even if TCP sits on top of it inside the kernel. 🌈

another obvious place to slice is above Telnet. the advantage of slicing above Telnet is that it solves the problem of having remote login channels emulate local teletype channels 🦋 the disadvantage of putting Telnet into the kernel is that the amount of code which has now been included there is getting remarkably large. in some early implementations, the size of the network package, when one includes protocols at the level of Telnet, rivals the size of the rest of the supervisor. this leads to vague feelings that all is not right 🫠

any attempt to slice through a lower layer boundary, for example between internet and TCP, reveals one fundamental problem 🚨 the TCP layer, as well as the IP layer, performs a demultiplexing function on incoming datagrams. until the TCP header has been examined, it is not possible to know for which user the packet is ultimately destined. therefore, if TCP, as a whole, is moved outside the kernel, it is necessary to create one separate process called the TCP process, which performs the TCP multiplexing function, and probably all of the rest of TCP processing as well. this means that incoming data destined for a user process involves not just a scheduling of the user process, but scheduling the TCP process first. ⏳

this suggests an alternative structuring strategy which slices through the protocols, not along an established layer boundary, but along a functional boundary having to do with demultiplexing 👑 in this approach, certain parts of IP and certain parts of TCP are placed in the kernel. the amount of code placed there is sufficient so that when an incoming datagram arrives, it is possible to know for which process that datagram is ultimately destined. the datagram is then routed directly to the final process, where additional IP and TCP processing is performed on it. this removes from the kernel any requirement for timer based actions, since they can be done by the process provided by the user. this structure has the additional advantage of reducing the amount of code required in the kernel, so that it is suitable for systems where kernel space is at a premium 🧠 the RFC 814, titled "Names, Addresses, Ports, and Routes," discusses this rather orthogonal slicing strategy in more detail. 📚

a related discussion of protocol layering and multiplexing can be found in Cohen and Postel [1]. 🫶

5. Breaking Down the Barriers 🌸

in fact, the implementor should be sensitive to the possibility of even more peculiar slicing strategies when dividing up the various protocol layers between the kernel and the one or more user processes 🤯 the result of the strategy proposed above was that part of TCP should execute in the process of the user. in other words, instead of having one TCP process for the system, there is one TCP process per connection. given this architecture, it is no longer necessary to imagine that all of the TCPs are identical. one TCP could be optimized for high throughput applications, such as file transfer. another TCP could be optimized for small, low delay applications, such as Telnet. in fact, it would be possible to produce a TCP which was somewhat integrated with the Telnet or FTP on top of it. such an integration is extremely important, because it can lead to a kind of efficiency which more traditional structures are incapable of producing ✨ earlier, this paper pointed out that one of the important rules to achieving efficiency was to send the minimum number of packets for a given amount of data. the idea of protocol layering interacts very strongly (and poorly) with this goal, because independent layers have independent ideas about when packets should be sent, and unless these layers can somehow be brought into cooperation, additional packets will flow 😵‍💫 the best example of this is the operation of server telnet in a character at a time remote echo mode on top of TCP. when a packet containing a character arrives at a server host, each layer has a different response to that packet. TCP has an obligation to acknowledge the packet. either server telnet or the application layer above has an obligation to echo the character received in the packet. if the character is a Telnet control sequence, then Telnet has additional actions which it must perform in response to the packet. the result of this, in most implementations, is that several packets are sent back in response to the one arriving packet 📦

Combining all of these return messages into one packet is SO important, bestie 💖 It matters for a few reasons. First, it cuts down the number of packets zooming around the net 🦋, which directly lowers the charges under lots of common carrier tariff structures 💸. Second, it reduces the number of scheduling actions that happen inside both hosts, and like we talked about above, that is extremely important for improving throughput 🔥.

Here's how we get this packet sharing goal: we break down the barrier between the protocol layers, but in a very restrained and careful way 🎀. That way a limited amount of info can leak across the barrier, and one layer can optimize its behavior based on what the layers above and below it want ✨. For example, it would be an improvement if TCP, when it got a packet, could ask the layer above whether it'd be worth pausing for a few milliseconds before sending an acknowledgement, just to see if the upper layer has any outgoing data to send 👀. Dallying before the ack is precisely the right optimization if the client of TCP is server Telnet 💅. But dallying before an acknowledgement is absolutely unacceptable if TCP is being used for file transfer 😭. In file transfer there is almost never data flowing in the reverse direction, and the delay in sending the ack probably turns directly into a delay in getting the next packets. So TCP has to know a little about the layers above it to adjust its performance as needed 🫶.

It would be possible to imagine a general purpose TCP equipped with all sorts of special mechanisms to query the layer above and change its behavior accordingly 🧚. In the structures suggested above, where there's not one but several TCPs, the TCP can simply be modified so it produces the correct behavior as a matter of course 🌈. This structure has the disadvantage that there will be several implementations of TCP existing on a single machine, which can mean more maintenance headaches if a problem is found where TCP needs to be changed 💀. However, it's probably the case that each of the TCPs will be substantially simpler than the general purpose TCP that would otherwise have been built 🍓. There are some experimental projects currently under way which suggest that this approach may make designing a TCP, or almost any other layer, substantially easier. That means the total effort to bring up a complete package is actually less if this approach is followed ⭐. This approach is by no means generally accepted, but it deserves some consideration 🙈.

The general conclusion here is that a layer boundary has both a benefit and a penalty 🌸. A visible layer boundary, with a well specified interface, provides a form of isolation between two layers. That lets one be changed with the confidence that the other one won't stop working as a result. However, a firm layer boundary almost inevitably leads to inefficient operation 😤. You can see this easily by analogy with other aspects of operating systems. Take file systems, for example. A typical operating system provides a file system, which is a highly abstracted representation of a disk. The interface is highly formalized and presumed to be highly stable, which makes it super easy for naive users to access disks without writing a great deal of software 🙌. So the existence of a file system is clearly beneficial. On the other hand, the restricted interface to a file system almost inevitably leads to inefficiency 💔. If the interface is organized as a sequential read and write of bytes, then people who want high throughput transfers won't be able to reach their goal. If the interface is a virtual memory interface, then other users will regret having to build a byte stream interface on top of the memory mapped file. The most objectionable inefficiency happens when a highly sophisticated package, such as a data base management package, has to be built on top of an existing operating system. Almost inevitably, the implementors of the database system try to reject the file system and get direct access to the disks. They've sacrificed modularity for efficiency 😩.

The same conflict shows up in networking, in a rather extreme form 🚨. The concept of a protocol is still unknown and frightening to most naive programmers. The idea that they might have to implement a protocol, or even part of one, as part of some application package is a dreadful thought 😱. So there's great pressure to hide the function of the net behind a very hard barrier. On the other hand, the inefficiency that results is a particularly undesirable kind, because it shows up, among other things, in increasing the cost of the communications resource used to achieve the application goal. When you have to pay for your communications costs, those costs usually turn out to be the dominant cost within the system 💸. So doing an excessively good job of packaging up the protocols in an inflexible manner has a direct impact on raising the cost of the critical resource within the system. This is a dilemma that will probably only get solved when programmers become somewhat less alarmed about protocols 🧠. Then they'll be willing to weave a certain amount of protocol structure into their application program, much like application programs today weave parts of database management systems into their structure ✨.

An extreme example of putting the protocol package behind a firm layer boundary is when the protocol package is relegated to a front-end processor 🖥️. In this case the interface to the protocol is some other protocol. It's difficult to imagine how to build close cooperation between layers when they're that far apart 🥲. Realistically, one of the prices you pay for an implementation that's physically modularized this way is that the performance will suffer as a result. Of course, a separate processor for protocols could be very closely integrated into the mainframe architecture, with interprocessor co-ordination signals, shared memory, and similar features 🤝. Such a physical modularity might work very well, but there is little documented experience with this closely coupled architecture for protocol support 📚.

6. Efficiency of Protocol Processing ✨

Okay so up to this point, this document has looked at how a protocol package should be broken into modules, and how those modules should be spread across free standing machines, the operating system kernel, and one or more user processes 🧩. Now it's time to look at the other half of the efficiency question: what can be done to speed up the programs that actually implement the protocols 🏎️. We'll make some specific observations about TCP and IP, and then wrap up with a few generalities 💜.

IP is a simple protocol, especially when it comes to processing normal packets, so it should be easy to get it to perform efficiently 😌. The only area of real complexity related to actual packet processing is fragmentation and reassembly. For specific consideration of this point, the reader is referred to RFC 815, titled "IP Datagram Reassembly Algorithms" 📖.

Most costs in the IP layer come from table look up functions, not from packet processing functions 🔍. An outgoing packet needs two translation functions to be performed. The internet address has to be translated to a target gateway, and a gateway address has to be translated to a local network number (if the host is attached to more than one network) 🗺️. It's easy to build a simple implementation of these table look up functions that performs very poorly, so be careful, bestie 🚫. Keep in mind that there may be as many as a thousand network numbers in a typical configuration. Linear searching of a thousand entry table on every packet is extremely unsuitable 💀. In fact, it may be worth asking TCP to cache a hint for each connection. That hint can be handed down to IP each time a packet is sent, to try to avoid the overhead of a table look up 🧠✨.

TCP is a more complex protocol, and it presents way more opportunities for getting things wrong 😵‍💫. There's one area that's generally accepted as causing noticeable and substantial overhead in TCP processing: computing the checksum 🧮. It would be nice if this cost could somehow be avoided, but the idea of an end-to-end checksum is absolutely central to how TCP works 🫡. No host implementor should think of omitting the validation of a checksum on incoming data 🙅‍♀️.

People have tried all kinds of clever tricks to minimize the cost of computing the checksum 🪄. If it's possible to add extra microcoded instructions to the machine, a checksum instruction is the most obvious candidate 🤖. Since computing the checksum means picking up every byte of the segment and examining it, you can combine that with copying the segment from one location to another 🔁. A number of data copies are probably already required as part of the processing structure, so this kind of sharing might pay off, if it didn't cause too much trouble for the modularity of the program 🤔. Finally, computing the checksum seems to be one place where careful attention to the details of the algorithm can make a drastic difference in the throughput of the program 🔥. The Multics system is one of the best case studies of this, since Multics is about as poorly organized for this function as any machine implementing TCP 🙃. Multics is a 36-bit word machine, with four 9-bit bytes per word. The eight-bit bytes of a TCP segment are laid down packed in memory, ignoring word boundaries. So when you need to pick up the data as a set of 16-bit units to add them up for checksums, horrible masking and shifting is required for each 16-bit value 😫. An early version of a program using this strategy needed 6 milliseconds to checksum a 576-byte segment. Obviously, at that point checksum computation was becoming the central bottleneck to throughput 🚧. A more careful recoding of the algorithm cut the checksum processing time to less than one millisecond 🎉. The strategy used was extremely dirty 🫣. It involved adding up carefully selected words of the area where the data lay, knowing that for those particular words, the 16-bit values were properly aligned inside the words. Only after the addition was done were the various sums shifted, and finally added to produce the eventual checksum. This kind of highly specialized programming probably isn't acceptable if it's used everywhere within an operating system 🙅. It's clearly appropriate for one highly localized function that can be clearly identified as an extreme performance bottleneck 🎯.

Another area of TCP processing that may cause performance problems is the overhead of examining all of the possible flags and options that occur in each incoming packet 🚩. One paper, by Bunch and Day [2], asserts

that the overhead of packet header processing is actually an important limiting factor in throughput computation 👀 Not all measurement experiments have tended to support this result 🤔 but to whatever extent it's true, there's one obvious strategy the implementor ought to use: build the program to optimize the expected case 💅 It's so easy, especially when you're first designing something, to give equal attention to every possible outcome of every test. In practice, though, few of those outcomes will ever happen 🙃 A TCP should be built on the assumption that the next packet to arrive has absolutely nothing special about it, and that it'll be the next one expected in the sequence space ✨ One or two tests are enough to confirm that the expected set of control flags is on. (The ACK flag should be on, the Push flag may or may not be on, and no other flags should be on.) One test is enough to confirm that the sequence number of the incoming packet is one greater than the last sequence number received. In almost every case, that's exactly what you'll get 🥹

Again, using the Multics system as an example, failing to optimize the case of receiving the expected sequence number had a detectable effect on performance 😭 The problem showed up when a bunch of packets arrived at once. TCP tried to process all of them before waking the user, so by the time the last packet arrived, there was a threaded list of packets with several items on it. Every time a new packet came in, the list got searched to find where it should go. Obviously, the list should be searched from highest sequence number to lowest, because you're expecting a packet that comes after the ones you've already got 🧠 But by mistake, the list was searched front to back, starting with the lowest sequence numbers. Searching it backwards like that took enough time to be easily spotted in the metering measurements 💀

Other data structures can be organized to optimize the action that's normally taken on them 🦋 For example, the retransmission queue is very rarely actually used for retransmission, so it shouldn't be organized to optimize that action. It should be organized to optimize discarding things from it when the acknowledgement arrives 🧹 In lots of cases, the easiest way to do this is to not save the packet at all, and just reconstruct it if it needs to be retransmitted, starting from the data as it was originally buffered by the user. Galaxy brain move 🌌

There's another generality that's at least as important as optimizing the common case 🎀 and that's avoiding copying data any more times than necessary. One more result from the Multics TCP is super enlightening here 🔍 Multics takes between two and three milliseconds within the TCP layer to process an incoming packet, depending on its size. For a 576-byte packet, that three milliseconds breaks down roughly like this:

One millisecond goes to computing the checksum 🧮
Six hundred microseconds goes to copying the data. (The data is copied twice, at .3 milliseconds a copy.) One of those copy operations could correctly be counted as part of the checksum cost, since it's done to get the data onto a known word boundary to optimize the checksum algorithm. BUT the copy also performs another necessary transfer at the same time 👯
Header processing and packet resequencing takes .7 milliseconds 📦
The rest of the time goes to miscellaneous processing, like removing packets from the retransmission queue that are acknowledged by this packet 🗑️

Data copying is the second most expensive single operation, right after data checksumming 😤 Some implementations end up copying data around a lot, often because of excessively layered modularity 🥴 Other implementations copy data because there's no shared memory between processes, so the data has to be moved from process to process via a kernel operation. Unless the amount of this activity is kept strictly under control, it'll quickly become the major performance bottleneck 🚨

7. Conclusions ✨

This document has covered two aspects of getting performance out of a protocol implementation: the way the protocol is layered and integrated into the operating system, and the way the detailed handling of each packet is optimized 🧁 It would be nice if one of these costs completely dominated, so you could focus all your attention in one spot. Sadly, that's not how it goes 😩 Depending on the kind of traffic you're getting, say Telnet one-byte packets or file transfer maximum-size packets at maximum speed, you can expect to see either cost being the major bottleneck to throughput 🔄 Most implementors who've studied their programs to find out where the time was going have reached the unsatisfying conclusion that it's going equally to all parts of the program 💔 With the possible exception of checksum processing, very few people have ever found that their performance problems came from a single, horrible bottleneck they could fix with one stroke of inventive programming. Instead, performance got better through painstaking tuning of the entire program 🛠️

Most discussions of protocols begin by introducing the concept of layering, which kind of suggests that layering is a fundamentally wonderful idea that should be part of every consideration of protocols 🍰 In fact, layering is a mixed blessing 🫠 Clearly, a layer interface is necessary whenever more than one client of a particular layer is going to use that same layer. But an interface, precisely because it's fixed, inevitably leads to a lack of complete understanding of what one layer wants from another, and that leads to inefficiency 📉 Layering is also a potential snare, because you're tempted to think that a layer boundary (which was really an artifact of the specification procedure) is the proper boundary for modularizing the implementation. Again, in certain cases an architected layer must correspond to an implemented layer, so that several clients can access that layer in a reasonably straightforward manner. In other cases, cunning rearrangement of the implemented module boundaries to match functions like the demultiplexing of incoming packets, or the sending of asynchronous outgoing packets, can lead to unexpected performance improvements compared to more traditional strategies 🚀

Finally, good performance is really hard to retrofit onto an existing program 😵‍💫 Since performance is influenced not just by the fine detail but by the gross structure, it's sometimes the case that to get a substantial improvement, you have to completely redo the program from the bottom up. Programmers, especially those doing a protocol implementation for the first time, find this super disappointing 😭 Programmers who are somewhat inexperienced with protocols are rightly concerned with getting their program logically correct, so they don't have the capacity to also think about the performance of the structure they're building. Only after they've got a logically correct program do they discover they've done it in a way that has ruled out real performance 🙈 Clearly, it's harder to design a program thinking from the start about both logical correctness and performance. With time, as implementors as a group learn more about which structures are best for building protocols, it'll be possible to start an implementation project with more confidence that the structure is rational, that the program will work, and that it'll work well 💖 Those of us implementing protocols right now have the privilege of being on the forefront of this learning process 🌈 It's no surprise our programs sometimes suffer from the uncertainty we bring to them 🫶

Citations 🎀

[1] Cohen and Postel, "On Protocol Multiplexing", Sixth Data Communications Symposium, ACM/IEEE, November 1979.

[2] Bunch and Day, "Control Structure Overhead in TCP", Trends and Applications: Computer Networking, NBS Symposium, May 1980. 🦋✨

📦 where this page comes from

ietf: rfc817 1982-07
💖 girlified by claude-haiku-5-5 on 2026-10-18: a language model's rewrite of the original, under its terms