A TCP-friendly policer

This article describes a non-standard policing solution. Also note: the TCP-friendly policer discussed here is NOT about solving fairness issues between TCP and non-TCP flows.

TCP is known to exhibit bumpy behavior when it is rate limited via policing. The phenomenon is more evident when testing under short Round Trip Time (RTT) lab conditions. Under such conditions the TCP throughput of a policed flow is far below CIR, and far behind the throughput and goodput of a shaped flow with the same rate.

The root cause of the issue lies in the congestion avoidance method of TCP. In congestion avoidance mode (the most widely deployed TCP agents) use the additive increase multiplicative decrease algorithm. TCP increases the congestion window once per RTT, and this lies at the foundation of the problem. If the TCP flow is rate limited via a shaper, then, as the shaper builds up backlog, the RTT increases and the rate at which transmission speed accelerates reduces. Therefore, when the shaped queue gets full and the first packet is discarded, there is sufficient time for the sender to react as the next increase would only occur when the acknowledges ot the lost segment would arrive, and which will help the source to detect packet loss via duplicate ACKs. Senders in such cases perform the Fast Retransmit algorithm. To be noted that when the queue is full, the sender is already sending faster than the shaping rate, but the increase in this rate per time interval is low. In a tail-drop buffer multiple packets could get lost before the sender is notified.

Policing however does not introduce delay. As such the TCP flows increases its sending rate in congestion avoidance mode more aggressively than a shaped flow. This way it ‘hits the ceiling more vertiginously’ than a shaped flow. In other words, by the time token depletion occurs it sends at far higher rate than CIR, much faster than a shaped flow does above the shaper rate. The result is multiple packet losses, of which one will eventually trigger TCP timeout. The TCP timeout is a condition that is detected by the expiry of a retransmission timer in the sender. TCP congestion avoidance then mandates the sender to stop, wait couple of hundred milliseconds, and start from slow start again.

The figures above illustrate a measurement-based arrival curve of a long-lived TCP flow that was policed with a single token bucket policer at CIR=5Mbps, CBS=64KB. The second figure shows the reverse-engineered token count, based on a trace taken before the node that performed the policing.

From time zero till approximately 0.2 seconds the first sprint of the TCP connection can be observed. During slow start there is a round shape of the token count (showing the accelerating behavior of TCP) after which congestion avoidance mode ramps up the rate (resulting in a steadily declining token count in the policer).

In this example the sender may have attempted a fast retransmission algorithm around 0.2 seconds, however some retransmission timers may have expired around 3 seconds (see arrival curve) as multiple losses occurred, and the sender stopped completely for 200 milliseconds. During this time the token count fully recovered at a rate of 5 Mbps.

The TCP-friendly policer

The basic idea of the TCP-friendly policer is to knock out a frame from the TCP stream before complete token depletion; just in time to let the sender detect the congestion and perform fast retransmit. During fast-retransmit the sending rate is reduced and congestion avoidance mode is maintained.

Of course, in practice multiple flows share a link, and consequently it is not sufficient to knock out just one frame when the token count crosses a threshold. A simple solution is then to emulate the well-known Random Early Detection (RED) algorithm, but instead of linking it to the queue depth, link RED to the inverse of the token count.

An equivalent method to the TCP-friendly policer above is proposed in RFC2859

Although the text introduces is rather differently, the two methods are quite equivalent, and solve the same issue based on the same principle. RFC 2859 calculates an estimated rate of the traffic and then sets colors based on a stochastic process, where the probability of marking increases with the estimated rate of the traffic stream.

A TCP-friendly policer should mark ECN-bits if the packet belongs to a stream that supports ECN, rather than discarding it. The sender would react the same way as if the packet would have been lost, except it could save the bandwidth for retransmitting the packet that was marked. The method is also faster than the loss-based 3-duplicate ack method of TCP, because the standard requires TCP clients to send an immediate ACK to the sender with the TCP option for congestion experienced set.

How to police TCP flows with a single token bucket?

Ok, so you do not have a TCP-friendly policer in your gear. What now?

First, the issue in reality is not that acute, as the phenomenon is much worse in the lab than in reality. The reason is that in reality round trip times are much larger, hence TCP ramp-ups are slower, and the goodput of a policed TCP flow is not much lower than that of a shaped one.

Furthermore, subscribers that only browse and do not use long-lived transfers will in fact see a better performance than those limited by shapers, because the RTT is not artificially inflated. Gamers will usually also benefit, as network games are built such that they can tolerate quite some loss, but an extra 50ms delay can ruin the experience of a real-time gamer.

A fairly good TCP goodput can be achieved with policer burst tolerances in the area of 96 - 128Kbytes. Such burst tolerances are suitable for today’s most common broadband access speeds of 3 to 10Mbps. In lab-tests performed, a 3-minute download from a fast public file-server took only 3 seconds longer with policing than with shaping, so for most practical purposes policing should be OK.

Shaping should be used when there are serious concerns about the negative effect of bursting micro-flows for other traffic. This however is seldom the case in data traffic classes in modern gigabit networks, and should occur at places when traffic enters the netowork, rather than where it exits towards the subscriber.

To summarize: long-lived TCP flows (e.g.: P2P file sharing) benefit from a shaped solution, to the expense of transactional services (browsing) and gaming, applications that would benefit more from a policer with a well-defined burst tolerance.