Computer networks are something most of us take for granted--speed, reliability, availability are expectations. In fact, network problems tend to make us very angry, whether it's dropped packets (yielding jittery Skype calls), congestion (that huge game download eating all the bandwidth), or simply a network outage. There's an awful lot going on underneath the hood of all devices on a network to load that webpage or download that song for you.
Much of the reliability in networking relies on maintaining good Quality of Service (QoS) policies, which involve buffering and queue management. Networks aren't unlike the roads we travel on; traffic isn't steady, and congestion at interfaces (or intersections on the road) happen. How do we handle that? We'll explore some basic networking principles in order to uncover some interesting mathematics governing buffering and queue management at congested network interfaces.
Update: Mr. Fred Baker reached out to me with a few corrections regarding my interchangeable use of queue and buffer. I've inserted his comments into the "Buffer" section. Incidentally, Mr. Baker wasthe inventor of the WRED (Weighted Random Early Detection) algorithm mentioned as an extension below.
TCP is the protocol that controls the flow of information across a network connection between two hosts. It runs on top of IP (Internet Protocol), which is responsible for the actual transport of data and multiplexing (the ability for multiple entities to communicate over the shared network). The excellent analogy for multiplexing given in CNPS is air. When multiple people in a room are having simultaneous conversations, they share a medium (air) to do it. Communication gets garbled if everyone shouts across the room, and there's no way to organize the flow of conversations so thoughts get where they're supposed to go.
TCP and IP work together to get packets of data from one place to another. For example, TCP/IP worked together to bring you this page, from the server where it is hosted to your computer, phone, or tablet you're reading on.
How fast should packets be transmitted? If packets are transmitted too fast, the receiver may not be able to keep up, and packets may get dropped and transmission data lost. Packet loss manifests in a voice call by jittery video, or perhaps a temporary loss of audio. If packets are transmitted too slowly, there is a lag, or the transmission just isn't as efficient as it could be. The goal is to strive for the fastest transmission we can have without packet loss.
TCP uses a windowing algorithm with a changing window size to constantly react to changing network conditions. When packets are all being transmitted successfully in sequence, the window widens and the transmitter is allowed to send a larger amount of data before the receiver is required to acknowledge receipt. The window increases until a packet is lost, at which point the window size will sharply decrease. Then we start the cycle again, slowly ramping up the window size (and hence amount of data transmitted before acknowledgement) until we experience another packet loss.
How many times have you had to wait for something to buffer when watching Netflix? A buffer is created at network interfaces to handle congestion. Think ../about an on-ramp to a freeway with the traffic lights on at rush hour, controlling the rate at which cars enter a crowded interstate. If we let all the cars on at the rate they want to go during rush hour, the interstate traffic would be even worse. So we buffer them at on-ramps, controlling the flow at the congested interface.
What happens when a buffer gets full? In basic queuing theory, we typically get around this by assuming a queue (buffer in this case) has infinite capacity. For the most part, we know that's not true.[note]There are mathematical ways to study finite capacity queues. We'll get to these.[/note] If the buffer is full, the most recent packets into the buffer will get turned away, or dropped. There's just no room for them. (Network engineers call thistail drop.)
(Editor's note: Here I'll insert the comments Mr. Fred Baker sent to me regarding my mistaken conflation of buffer and queue. I chose not to change the article itself, but rather insert his comments of correction, for the sake of full transparency.)From Mr. Baker:
A buffer is a container, much like a prescription bottle is a container. If a buffer "forms" when data arrives, the corollary would be a prescription bottle coming into being when a pharmacist attempted to put pills into it. It doesn't work that way. A buffer as a section in memory in which messages are stored, and has a maximum size. When the number of messages or number of bytes exceeds the maximum, one can't put more messages into it. The organization of the buffer is usually some form of queuing system, as simple as a single FIFO queue (common) and as complex as a hierarchy of queues with different methodologies. Each queue has some service discipline, which may be that it is "work conserving", meaning that it rattles data through as quickly as it can, or may not be "work conserving", meaning that it passes data through at some slower rate. A well known example of a non work conserving system is called Virtual Clock, published by Lixia Zhang in SIGCOMM 1990 (IIRC). A queue has a minimum depth (zero), while the buffer containing it has a maximum depth, and individual queues in the buffer may have maximum depths smaller than the buffer's depth or service disciplines (such as RED) that moderate queue depth in some other way (RED and WRED interact with TCP, moderating the TCP window and as a result the amount of data the session keeps in flight at any given time). The Differentiated Services Architecture (RFCs 2474 and 2475) looks at quite a few other aspects of service and queue management as well.
Not all packets are created equal. Some packets, when delayed in a buffer, lose their purpose for existence. VoIP calls are the perfect example here. VoIP requires packets to be delivered, and delivered on time. A delayed packet is useless to the end user--the conversation has moved on. This means that a packet at the front of the queue can be useless, and tail-dropped packets (the most recent bits of your Skype conversation) are more needed.
Simply letting a buffer get full and drop the tail packets is passive queue management. The problem with this goes back to how we explained TCP's functionality above. If a packet gets dropped, TCP shrinks the window size and decreases the amount of data allowed per transmission before the receiver has to acknowledge receipt of packets, effectively throttling traffic. Throttle traffic enough, and we can empty the buffer and packets flow normally without congestion. But then as TCP ramps the window size up again, our buffer gets full, resulting in tail drop, and we start that whole cycle again. The end result is a bandwidth oscillation wherein the poor network goes from highly congested to empty to congested again, because all the TCP-traffic is synchronized.
How can we avoid this TCP synchronization phenomenon? We can take what might seem to be a counterintuitive approach and never let the buffer get full. How? We drop packets on purpose, with some probability, which will depend on the queue length inside the buffer. The Random Early Detection (RED) algorithm provides a way to randomly select packets to drop in order to prevent a full buffer and resulting tail-drop. Dropping random packets also desynchronizes different TCP streams, since some packet sequences will have their windows decreased upon packet drop, while those streams whose packets are not selected for drop maintain or increase their window size.
RED [5] calculates a probability for marking a packet for drop based on the current average queue length, calculated by a moving average.
We only invoke Step (3)- calculating the probability of marking a packet if our average queue length $\bar{Q}_{n}$ is inside our boundaries $T_{\min}$ and $T_{\max}$. If $\bar{Q}_{n} < T_{\min}$, then there's no congestion, so we don't need to drop anything at all. The traffic lights at the interstate on-ramp aren't turned on in the middle of the night when traffic is light.
If $\bar{Q}_{n} > T_{\max}$, then we're really congested, then we mark the incoming packet. Period. This means we have to clear out the buffer ASAP.
Notice above that the function to calculate $p_{a}$ was linear in terms of the average queue length $\bar{Q}_{n}$. Why linear? Well, for one, when RED was first created in 1993, it was easier. Absent further information, simple is best, and linear is simple. There are other functions to calculate the packet drop probability $p_{d}$ that are nonlinear. We'll explore one of those papers next [2], which takes us into the notion of orthogonal polynomials.
We can also discuss the fact that the average queue length was computed by a weighted moving average. Other works out there have looked at the impact of a weighted moving average [1], and other drop functions on the performance of the RED algorithm[2].
Analysis of queues is a huge field. Since everything ../about network traffic (and general queues as well) is based on random variables, the mathematical study of queuing theory is a rich environment. We can view traffic as discrete random processes, like a birth-death process. We can assume the process is stationary, or we can look into studying traffic the way we study fluid flow, typically using differential equations.
As networks get more and more complicated, we need this more sophisticated (and hopefully elegant) mathematics to help us understand traffic flow. We never really discussed in this article how to set the thresholds $T_{\min}$ and $T_{\max}$. Those require a good model and understanding of the particular type of traffic flow in a specific network. Good understanding of queuing behavior yields good threshold design, which yields good queue management schemes, which ultimately yields a better user experience.