RFC 970

On Packet Switches With Infinite Storage 🎀

okay so bestie, before we dive in, here's the lowdown on this RFC 💅 It's RFC 970, written by John Nagle from FACC Palo Alto and dated December 1985, and it's titled On Packet Switches With Infinite Storage. It doesn't say anything about obsoleting or updating other RFCs, so it's totally standalone 🌸

Status of This Memo ✨

so the whole point of this doc is to get people talking about specific problems in the ARPA-Internet and possible ways to fix them 🗣️ none of the solutions in here are meant to be standards yet, no cap. the hope is that everyone eventually agrees on the right fix, and then we make it official 🫶 distribution of this memo is unlimited, so share away 🦋

Abstract 🍓

most of the earlier congestion work in datagram systems is all about buffer management 🧺 but the vibe here is different. we look at a packet switch with infinite storage. 🤯 a switch like that can literally never run out of buffers, but it can still get congested, which is the wild part ✨ we explore what congestion even means in that kind of system, and the big reveal is that a datagram network with infinite storage, first-in-first-out queuing, at least two packet switches, and a finite packet lifetime will drop all packets under overload 💀 by solving congestion for the infinite-storage case, we end up with new solutions that also work for switches with finite storage 🔥

Introduction 🧚

packet switching showed up back when computer storage cost several orders of magnitude more than it does now 📼 so the early builders went super hard on making switches with the absolute minimum storage they could get away with. the usual framing was that congestion control meant avoiding buffer exhaustion in the switches. we're doing it differently 💖 we start by assuming infinite memory, which forces us to look at congestion with fresh eyes. we stop asking when to block or which packets to toss, and instead ask how we want the system to perform 👑

pure datagram systems are especially prone to congestion problems 😭 they don't have the blocking mechanisms that virtual circuit systems get, and no fully effective fixes for congestion in pure datagram systems are known yet. most existing datagram systems behave badly under overload, honestly iconic behavior for the wrong reasons 🙈 but we'll show that real progress is possible even for pure datagram systems, as long as we define the problem as deciding the order of packet transmission, instead of how buffer space gets allocated 🎯

A Packet Switch with Infinite Storage 🌈

let's start with a simple packet switch with infinite storage ✨ it has incoming and outgoing links, and each link has a fixed data transfer rate. the links don't all have to run at the same rate. packets arrive on incoming links and get assigned an outgoing link right away by some routing mechanism, which we're not going to get into here 🧭 each outgoing link has a queue. packets come off that queue and go out on the link at that link's data rate. for now, we'll assume the queues are first in, first out 🫶

we also assume packets have a finite lifetime 🕰️ in the DoD IP protocol, packets have a time-to-live field, which is the number of seconds left before the packet gets discarded as uninteresting. every time the packet moves through the network, this field gets decremented, and if it hits zero, the packet must be discarded 💅 the starting value is fixed, and in the DoD IP protocol it's 15 by default ⏳

the time-to-live mechanism stops queues from growing forever. once the queues get long enough, packets time out before they ever get sent 🙌 that puts an upper bound on the total size of all the queues, and the bound depends on the total data rate of all incoming links and the upper limit on the time-to-live ✨

but this does not get rid of congestion, and here's why 👀

take a simple node with one incoming link and one outgoing link 🔗 say the packet arrival rate at the node is higher than the departure rate. the outgoing link's queue will keep growing until the time spent sitting in the queue is longer than the time-to-live of the incoming packets 😳 at that point, whenever the process serving the outgoing link pulls a packet off the queue, it'll sometimes find one whose time-to-live has already been decremented to zero. when that happens, it discards that packet and moves on to the next one in the queue 🗑️ packets with nonzero time-to-live fields still get sent out on the outgoing link 📤

the packets that do get sent still have nonzero time-to-live values. but once the steady state under overload is reached, those values will be small, because each packet has been sitting in the queue for just under the maximum time-to-live 🫠 in fact, if the departure rate is greater than one per time-to-live unit, the time-to-live of any forwarded packet will be exactly one. the reason is that if more than one packet goes out per time-to-live unit, consecutive packets in the queue will have time-to-live values that differ by no more than 1 🧠 so the part of the switch that pulls packets off the queue and either sends or discards them as expired will run into either packets with negative or zero time-to-live values (which it discards) or packets with a value of 1 (which it sends) 🎭

so, clearly enough, at the next node in the packet switching system, the arriving packets will all have time-to-live values of 1 😬 since we always decrement the time-to-live value by at least 1 at each node, so that it goes down as the packet travels through the network, the next node will decrement each incoming packet to zero and then discard it 💀

so we've shown that a datagram network with infinite storage, first-in-first-out queuing, and a finite packet lifetime will drop all packets under overload 😱 this is a pretty unexpected result, but it's totally real 💯 it's not some artifact of the infinite-buffer assumption. the problem still happens in networks with finite storage, it's just harder to see there 🔍 datagram networks are known to behave badly under overload, but nobody has really analyzed why, and the infinite-buffer case is super simple to analyze, so we get a lot of insight into the problem from it 🧁

you'd think someone would've spotted this before, right? 🤔 but earlier work on congestion control in packet switching almost always focuses on buffer management. as far as anyone can tell, analyzing the infinite buffer case is unique to this writer 🦄

this result also applies directly to networks with finite resources 🎀 the storage needed for a switch that can never run out of buffers turns out to be pretty reasonable, honestly. take a pure datagram switch for an ARPANET-like network 🛰️ for a packet switch with four 56Kb links and an upper bound on the time-to-live of 15 seconds, the maximum buffer space that could ever be required is 420K bytes <1> 📦 a switch with this pretty modest amount of memory need never drop a packet due to buffer exhaustion 💖

and this isn't just theory, bestie 😤 we demonstrated it experimentally on our own network, using a supermini with several megabytes of memory as the switch 🖥️ we now have experimental evidence that the phenomenon described above happens in practice. in our first experiment, an Ethernet on one side of the switch and a 9600 baud line on the other, there were 916 IP datagrams queued in the switch at peak 📈 but we were applying the load over a TCP transport connection, and that connection timed out because of excessive round trip time before the queue reached the time-to-live limit. so we never actually got to the stable state with the queue at its maximum length, the way our analysis predicted 😭 it's kinda wild that we can force this condition from a user application sitting on top of the transport layer (TCP), and that definitely deserves more analysis 🔬

Interaction with Transport Protocols 🦋

so far we've assumed packet sources that send packets at a fixed rate 🎶 that's a valid model for certain sources, like packet voice systems. systems that use transport protocols from the ISO TP4 or DoD TCP class, though, ought to be better behaved 🫶 the key point is that transport protocols used in datagram systems should behave in a way that doesn't overload the network, even when the network has no means of stopping them from doing so 🙌 and that's totally possible, no cap ✨

in a previous paper by this writer [1], we looked at how the TCP transport protocol behaves over a congested network 📖 we showed that a badly behaved transport protocol implementation can cause serious harm to a datagram network, and we talked about how such an implementation ought to behave. that paper also gave some specific guidance on implementing a well-behaved TCP, and showed that proper behavior could, in some cases, cut network load by an order of magnitude 📉 the big takeaways were that a well-behaved transport protocol should not have a retransmit time shorter than the current round trip time between the hosts involved, and that when the network tells it about congestion, the transport protocol should take steps to reduce the number of packets outstanding on the connection 🛑

we bring up our earlier work here to show that the network load a transport protocol creates isn't necessarily fixed by the protocol spec 🧩 some existing implementations are well-behaved, and others are not. we've seen a wide range of behavior across existing TCP implementations 😬 we suspect ISO TP4 implementations will be more uniform, since the spec is more rigid, but there's still enough room in the TP4 standard for a lot of variability 🫠 we expect there'll be marginal TP4 implementations, from a network point of view, just like there are marginal TCP implementations today 🙈 those will usually work fine until they're asked to run over a heavily loaded network with big delays. then we find out which ones are well-behaved 😳

even if every host is moderately well-behaved, there's still room for trouble 🌪️ each host can usually get more bandwidth by sending more packets per unit time, because first in, first out gives the most resources to whoever sends the most packets 🏃‍♀️ but when all the hosts together overload the network, total throughput drops. as shown above, throughput can drop all the way to zero 💀 so the optimal strategy for each individual host is strongly suboptimal for the network as a whole 😭🫶

---

to be continued in part 2, bestie 🧚💜

Game Theoretic Aspects of Network Congestion ✨

okay so this section is where things get juicy 🍓 it's a digression into game theory, and bestie, it's giving chaos in the best way. systems where each player's best move is a bad move for everyone tend to slide toward the bad state. the classic example is the prisoner's dilemma, but the closer match is the tragedy of the commons 🐑

here's the vibe: each person can make their own life better by using more of a free shared resource. but the more people pile on, the more the total resource gets wrecked. so everybody's self-interest leads to overload and collapse. this was first worked out for common grazing land, but it applies to all kinds of stuff, like air quality and time-sharing systems. honestly, the general lesson is that many-player systems with this kind of instability tend to get into serious trouble 😭

there are three ways people usually try to fix the tragedy of the commons: cooperative, authoritarian, and market solutions. cooperative ones, where everyone just agrees to behave, are fine for a small group but tend to fall apart as the group grows 🫶 authoritarian ones work well when behavior is easy to monitor, but they fail if "good behavior" is subtle. and a market solution only works if the rules of the game can change so that each player's best move is also best for everybody. when that's possible, market solutions can be super effective 💅

this analysis mostly applies to human players. in networking, though, the player is a computer running a preprogrammed strategy. that alone doesn't guarantee good behavior, because the software might be tuned to make that one computer faster with zero regard for the network 🙈 telephony has the same problem with automatic redialing devices. a user's equipment tries to get through an overloaded network by redialing failed calls really fast. call setup is a scarce resource in phone systems, so this can seriously hurt the network. some countries have had to ban these devices outright (Brazil, for one). banning them by administrative decree sometimes works and sometimes doesn't, depending on how much power the authority has compared to the users 🇧🇷

as transport protocols get more commercialized and there are competing systems out there, we should expect people to tune their protocols in ways that look great from a single host's point of view but are bad for the whole network. we already see signs of this in the transport protocol of one popular workstation manufacturer 👀

so, back to our pure datagram internetwork. an authoritarian fix would order every host to be "well-behaved" by decree. that's hard, because defining a well-behaved host by what you can observe from the outside is subtle. a cooperative fix has that same problem, plus the extra headache of applying social pressure across a distributed system 😩 which leaves the market solution: we have to make it pay to be well-behaved. to do that, we'll have to change the rules of the game 🎀

Fairness in Packet Switching Systems ⚖️

we want to protect the network from hosts that aren't well-behaved. more specifically, when well-behaved and badly-behaved hosts are both present, we want to make sure well-behaved hosts get better service than badly-behaved ones. and we've actually figured out a way to do that 🦋

let's picture a network made of high-bandwidth pure-datagram local area networks with no flow control (Ethernet and most IEEE 802.x datagram systems are this kind, whether they use carrier sensing or token passing), hosts plugged into those LANs, and a wide area network made of packet switches and long-haul links. the wide area network might have internal flow control, but it has no way to force flow control on the source hosts. the DoD Internet, Xerox Network Systems internetworks, and the networks derived from them all fit this model 🌈

if any host on a local area network sends packets toward the wide area network faster than the wide area network can absorb them, congestion happens at the packet switch that connects the two. if those switches queue strictly first in, first out, the badly-behaved host will mess up the transmission for all the better-behaved hosts 😤

so we introduce fairness. we want our packet switches to be fair, meaning each source host should be able to get an equal fraction of each packet switch's resources ✨ here's how: instead of one first in, first out queue for each outgoing link, we use multiple queues, one for each source host in the entire network. we service those queues round-robin, taking one packet from each non-empty queue in turn. packets with a positive time to live value get sent out on the outgoing link, and expired packets get dropped. empty queues get skipped and lose their turn 💜

this is fair! outgoing link bandwidth gets split equally among source hosts. every source host with packets queued in the switch for that outgoing link gets exactly one packet sent each time the round-robin cycles. so, honestly, we've built a form of load-balancing 🫧

we've also made the game better from a game-theory point of view. the best move for a host is no longer to send as many packets as possible 🙅‍♀️ the best move is to send at a rate that keeps about one packet waiting in each packet switch. why? because that way the host gets serviced every time the round-robin cycles, and its packets see the least transit delay. this is also totally fine from the network's side, since each queue's length will usually be between 1 and 2 🍰

hosts need advisory information from the network to optimize their strategies, and the existing Source Quench mechanism in DoD IP is enough for that. it's minimal, but it works 🧚 packet switches should send a Source Quench message to a source host whenever the number of packets queued for that host goes over some small value, probably 2. if hosts keep their traffic just under the point where they start getting Source Quench messages, the network should run with mean queue lengths under 2 for each host 💖

badly-behaved hosts can send all the datagrams they want, but it won't increase their share of the network. the only thing that happens is their packets experience long transit times through the network 💀 a really badly-behaved host can send so many datagrams that its own transit times climb up to the time to live limit, and then none of its datagrams get through at all. this happens sooner with fair queuing than with first in, first out queuing, because the badly-behaved host only gets a share of the bandwidth that's inversely proportional to the number of hosts using the packet switch at that moment. that's way less than it would've gotten under the old system, where the more verbose hosts grabbed more bandwidth. so this gives badly-behaved hosts a strong reason to clean up their act 🌸

it's also worth noting that malicious hosts, as opposed to merely badly-behaved ones, can overload the network by using lots of different source addresses in their datagrams. that way they impersonate a bunch of different hosts and grab a bigger share of the bandwidth. this is an attack on the network, not something that's likely to happen by accident. so it's a network security problem, and we won't go further into it here 🔐

okay, real talk: making the packet switches fair doesn't make the whole network fair 😬 this is a weakness of our approach. the strategy is most useful for a packet switch at a choke point, like an entry node of a wide area network or an internetwork gateway. as a strategy for an intermediate node in a large packet switching network, where packets from many hosts at different locations pass through the same switch, it's a lot less useful. the writer doesn't claim this approach is a complete solution to congestion in datagram networks. but it does solve a serious problem, and it points toward a direction for future work on the general case 🧭

Implementation 🛠️

at first, keeping a separate queue for each source host, for each outgoing link, in each packet switch sounds like it adds a lot of complexity to the queuing mechanism. there is some complexity, sure, but the manipulations are simpler than what you'd need with something like balanced binary trees 🌳 one simple way to do it is to put space for pointers in the header of each datagram buffer. each source host's queue only needs to be singly linked. the queue heads (the first buffer of each queue) need to be doubly linked, so we can delete a whole queue once it's empty. that means we need three pointers in each buffer. there are fancier strategies that can speed things up when queues get long, but the extra complexity probably isn't worth it in practice 🙃

with a finite buffer supply, we might someday run out of buffers. when that happens, we should drop the packet at the end of the longest queue, since that's the one that would be transmitted last 😌 this is unfavorable to the host with the most datagrams in the network, and honestly that's exactly what fairness is supposed to look like 👑

Conclusion 🎀

by breaking away from packet switching's long-time obsession with buffer management, we got some new insights into congestion control in datagram systems, and we came up with solutions for some known problems in real systems. we hope others will build on this new insight and make some real progress on the general datagram congestion problem 🦋💜

References 📚

[1] Nagle, J. "Congestion Control in IP/TCP Internetworks", ACM Computer Communications Review, October 1984.

Editor's Notes 📝

<1> The buffer space required for just one 10Mb Ethernet with an upper bound on the time-to-live of 255 is 318 million bytes. 🧮