Figure 1: Single flow network topology.
Arthur Dick
November 14, 2005
Core routers in use today contain buffers which may be much larger than necessary. This paper will analyse what effect changing the buffer sizes in routers would have on the performance of network protocols. Specifically, we will be focusing on TCP performance, as it is the transfer protocol in use for popular applications such as the web, FTP, email, and peer to peer networks.
The widely used rule-of-thumb used to determine Internet router buffer size is that we need at least one round trip time worth of buffering[2]. This rule-of-thumb assures that the buffer in a bottleneck link will not go empty when there is a single TCP flow, it does not consider multiple flows.
The fast memory required in core routers is expensive, so reducing the required memory would reduce the cost of these routers. Additionally, if the memory requirements for the buffer in core routers is reduced, an all-optical router becomes feasible[4].
There have been a number of papers [2,3,4,5] written recently discussing the possibility of significantly reducing the amount of buffer space in core routers. However, these studies have only considered TCP Reno flows, we will be considering TCP NewReno.
The TCP congestion control algorithm is designed to allow multiple connections to share a congested links bandwidth. If a TCP sender perceives there is more bandwidth available, it will increase the sending rate. On the other hand, if the sender perceives there is congestion somewhere along it's path, it will reduce the sending rate.
The rule-of-thumb used to determine the size of buffers in a routers is calculated according to the formula B = RTT * C, where RTT is the average round trip time, and C is the data rate of the link[5]. A buffer of this size is thought to allow the router to run at a high utilization. However, it has been argued that utilization may not necessarily the right metric[2], as most core routers today run well below 100% utilization.
This calculation only takes into account a single TCP Reno flow, whereas backbone routers today carry many more flows. Therefore this single flow is not a realistic model.
In Sizing Router Buffers[5], Appenzeller et al determine that when many long-lived TCP flows share the same backbone link they tend to become desynchronized. Therefore there is no significant waiting period for the buffer to drain after a packet is lost, as there would be if there were a single flow or if all the flows were synchronized. Using a probabilistic model, simulations, and measurements with a physical router, they show that buffer sizes can be reduced to C*RTT/sqrt(n) while maintaining a link utilization of 98% or higher. Raina et al argue in Control Theory for Buffer Sizing[3] that buffers can be very small if the flows are desynchronized.
In Buffer Sizes for Core Routers[2], Wischik and McKeown argue that utilization may not even be the right metric to use, as backbone routers today tend to run significantly below 100%. They show that buffers can nearly be eliminated by sacrificing 5% utilization, and that throughput may actually increase due to the reduced latency and jitter observed with small buffers.
Figure 1: Single flow network topology.
Figure 2: Cycle of TCP NewReno.
We are assuming the topology in figure 1, with a single sender through a bottleneck link; we also assume the sender is in congestion avoidance mode. The sender will increase the window size each round trip until k packets are lost off the tail end of the buffer. We want to ensure there is enough buffer space such that the buffer will not go empty during the fast retransmit and fast recovery stages.
Upon entering fast recovery, the sender will reduce the transmission rate to Wmax/4*RTT, we will assume this rate is constant. The buffer will continue to drain at the constant rate C, so the net draining rate from the buffer is C - Wmax/4*RTT. Therefore, the buffer will drain in a time period of B/(C - Wmax/4*RTT).
Since k packets were lost, the sender will spend a time period of k*RTT in fast recovery. To ensure the congested link remains fully utilized, we want the buffer to just go empty at this point, so B/(C - Wmax/4*RTT) >= k*RTT. Now we can find the necessary relationship between B, C, and RTT to be: B >= k*C*RTT - k*Wmax/4.
At this point, fast recovery is complete, so the sender will resume sending at Wmax/2*RTT. To ensure the congested link remains fully utilized, this sending rate should be equal to C. Therefore Wmax = 2*C*RTT.
Substituting the value for Wmax into the relationship between B, C, and RTT, we find the minimum buffer size which allows the congested link to remain fully utilized is B = k*C*RTT/2.
The rule-of-thumb calculated for TCP Reno gives a buffer size of B = C*RTT for one packet drop, and those calculations can be extended to k packet drops by B = k*C*RTT. Therefore the buffer requirements for NewReno are half those for Reno.
Using a simulation tool called ns-2[1], we expect the experimentally determined optimum buffer size to be similar to the rule derived in the previous section.
TCP's congestion control algorithm is designed such that it will fill any buffer[2]. A router will drop packets once the buffer is full causing the sender to reduce their sending rate.
If the buffer size in a router is large, each TCP flow through the router tends to lose packets at the same time, and therefore they all reduce their sending rate at the same time. In this case, the TCP flows are said to be synchronized, and the sum of these flows appear to act as a single amplified flow.
On the other hand, if the buffer size in a router is small, TCP flows tend to lose packets according to a random process. The sum of these flows will not act as a single flow, so there is no need for large buffers to keep the link busy, as there is no point when all the senders enter fast recovery.
Therefore, a router with a small buffer promotes desynchronized TCP flows, and if the TCP flows are desynchronized, a small buffer size is sufficient[3]. This creates a virtuous cycle, as the small buffer tends to induce the conditions favorable for a small buffer.
To be completed.
Final results.
| [1] | The Network Simulator - ns-2. http://www.isi.edu/nsnam/ns/, accessed October 1, 2005. |
| [2] | Damon Wischik, Nick McKeown. Buffer Sizes for Core Routers. ACM SIGCOMM Computer Communication Review, 35(3):75-78, July 2005. |
| [3] | Gaurav Raina, Don Towsley, Damon Wischik. Control Theory for Buffer Sizing. ACM SIGCOMM Computer Communication Review, 35(3):79-82, July 2005. |
| [4] | Mihaela Enachescu, Yashar Ganjali, Ashish Goel, Nick McKeown, Tim Roughgarden. Routers with Very Small Buffers. ACM SIGCOMM Computer Communication Review, 35(3):83-90, July 2005. |
| [5] | Guido Appenzeller, Isaac Keslassy, Nick McKeown. Sizing Router Buffers. ACM SIGCOMM 2004, 1-12, August 2004. |