Networking Mathematics: Random Early Detection and TCP synchronization

Networking Mathematics: Random Early Detection and TCP synchronization

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 was the inventor of the WRED (Weighted Random Early Detection) algorithm mentioned as an extension below. 

Networking Terms

First, we need to get a few definitions out of the way. One of the main references I’m using is a book called Computer Networking Problems and Solutions: An Innovative Approach to Building Modern, Resilient Networks, by Russ White and Ethan Banks1.

TCP (Transport Control Protocol)

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)2 .

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. 

Buffers

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.3 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 this tail 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.

Tail Drop and TCP Synchronization

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.

Passive Queuing Messes up TCP

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. 

Random Early Detection 

“Get to the math please!” 

So 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. 

(1) Calculate the new average queue size

Let \bar{Q}_{n} be the average queue size at discrete time n, and let Q be the current queue length. Then

\bar{Q}_{n} = (1-w)\bar{Q}_{n-1} + wQ

Here, w is a weight we get to choose to decide how much weight we want to give to the current queue length, typically w\ll 1. If w is chosen too small, then RED will react too slowly to current congestion. If w is too large, then RED is sensitive to noise. Recommendations for choices of w vary from 0.001 to 0.07 [3,4]. 

(2) Set minimum and maximum thresholds

Next, we set minimum and maximum thresholds for the tolerance of \bar{Q}_{n}. We’ll call these T_{\min} and T_{\max}. These thresholds will depend on network capabilities. 

(3) Calculate the probability of marking an incoming packet for drop

When each packet comes in, we have to have a way to calculate a probability of dropping it or letting it join the buffer. The original RED first sets a maximum possible drop probability we’ll call p_{\max}, and then calculates the drop probability p_{d} in two stages

  1. Computing an intermediate value p_{a} that grows linearly with the average queue length \bar{Q}_{n} p_{a} = p_{\max}\frac{\bar{Q}_{n}-T_{\min}}{T_{\max}-T_{\min}}
  2. Computing the final probability based on the number of packets since the last one that was actually marked (we’ll call this c) and p_{a} above:
    p_{d} = \frac{p_{a}}{1-c\cdot p_{a}}

So why do that second step? Since we’re ultimately choosing randomly whether to mark a packet for drop or not, it’s possible we don’t mark several packets in a row even if p_{a} is high. The idea of Step (2) is to increase the probability of actually marking a packet as the number not marked increases. The purpose of this is to ensure that our interface doesn’t wait too long before marking a packet.4

Putting it all together

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. 

Now, 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. 

Conclusion and Future Stuff

Other Variants

RED has another variation, WRED (Weighted Random Early Detection), which takes into account the class of the packet arriving. Some packets really are more important than others. When you’re in the middle of a VoIP call, those packets are way more important than perhaps some email coming in, because a slight delay of a few milliseconds in email delivery isn’t noticed, whereas a few millisecond packet delay causes jitter in your video. WRED deals with classed traffic but is basically the same as RED explored here. 

Things we can change about RED

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]. 

Where else can we look?

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. Not just for networks, but any kind of traffic.  

Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

References

  1. Domanska, J., Domanski, A., Augustyn, D.R.: the Impact of the Modified Weighted Moving Average on the Performance of the RED Mechanism. CN 2011. CCIS, vol. 160, pp. 27-44
  2. Augustyn, D.R., Domanski, A., Domanska, J.: Active Queue Management with non linear packet dropping function. 6th International Conference on Performance Modeling and Evaluation of Heterogenous Networks (2010)
  3. S. Floyd. Discussions of Setting Parameters, http://www.icir.org/floyd/RED-parameters.txt (1997)
  4. Zheng, B. and Atiquzzaman, M.: A Framework to Determine the Optimal Weight Parameter of RED in Next-Generation Internet Routers. The University of Dayton, Department of Electrical and Computer Engineering, Tech. Rep., 2000
  5. Floyd, S., Jacobson, V.: Random Early Detection Gateways for Congestion Avoidance. IEEE/ACM Transactions on Networking 1(4) (1993)

 

Footnotes

  1. I give a good recommendation for this book. Currently I’m about 300 pages in. The book is aimed for the newbie to networking. I wouldn’t call it particularly deep or rigorous, but honestly, that’s not its point. There are so many resources on computer networking it’s impossible to know where to start learning just the basics. This book does an excellent job of familiarizing the reader with networking terms, protocols, general issues, solutions, and integrates it all together to give a great overview of the field.
  2. 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.
  3. There are mathematical ways to study finite capacity queues. We’ll get to these.
  4. Remember, all of these things we’re calculating are probabilities. Even a high probability doesn’t guarantee that an event will occur.

2 thoughts on “Networking Mathematics: Random Early Detection and TCP synchronization

Leave a Reply

Your email address will not be published. Required fields are marked *