Sizing Router Buffers
for Large-Scale TCP/IP Networks
Hiroyuki Hisamatsu

Go Hasegawa

Masayuki Murata

Cybermedia Center
Graduate School of Information Science
Department of Computer Science
Osaka Electro–Communication University
Osaka University
and Technology, Osaka University
1130–70 Kiyotaki, Shijonawate
1–32 Machikaneyama, Toyonaka
1–5 Yamadaoka, Suita
Osaka, 575–0063 Japan
Osaka, 560–0043 Japan
Osaka, 565–0871 Japan
E-mail: hiroyuki.hisamatsu@olnr.org
E-mail: hasegawa@cmc.osaka-u.ac.jp
E-mail: murata@ist.osaka-u.ac.jp

is, the increase in packet loss ratio due to decreased buffer
size and its inﬂuence on TCP performance are not considered.
Although the authors focus on the TCP throughput in [5],the network topology used in this study is quite simple, with
only about 400 TCP connections passing through the bottleneck link, whereas 500–1,000 concurrent TCP connections
are required to avoid the synchronization [1]. Therefore, theeffect of the small buffer size is veriﬁed only in the smallscale networks that focus only on the core network, and therelationships between the core network and the edge network
are not considered. One of the reasons for this may be that
network simulators or analysis methods are limited. Thesestudies also explicitly or implicitly assumes that edge networks
are slower than core networks. The impact of the small buffer
size on network performances in today’s networks, where theaccess link speed has been increasing, should be investigated.
In this paper, we investigate the validity of reducing buffer
sizes in a large-scale network that includes both core networks
and edge networks. To do this, we ﬁrst devise a novel
method of analyzing the average behavior of TCP connections in the large-scale networks with over 100/1,000/10,000
routers/endhosts/links and 100,000 concurrent TCP connections. In our analysis, we model each network component(endhost’s TCP and network link with Tail-Drop buffer) as anindependent system, and then combine them into one system inorder to analyze the average behavior of the TCP connections
for the entire network. We apply the proposed analysis method
to the Abilene-inspired network [6], which is developed basedon the characteristics of the actual router-level topology. By
deriving the link utilization and the packet loss ratio in eachlink, the TCP throughput and the TCP round-trip time in
the network, we dispute the inﬂuence of the small buffer
size on the whole network and on TCP connections. Oneof the important results of our analysis is that the fairness
among TCP connections that pass through the core networkand those that do not becomes worse than the well-known
TCP unfairness caused by different round-trip times.
This paper is organized as follows. In Section II, we
introduce the network and trafﬁc models used in this paper.
In Section III, we describe the analysis methods used in

Abstract— We investigate the validity of reducing router buffer
size in a large-scale network that includes both core networks
and edge networks. We ﬁrst devise a novel mathematical analysis
method of estimating the average behavior of TCP connections
in a network with 100/1,000/10,000 routers/endhosts/links and100,000 concurrent TCP connections. By applying our analysis
method to the Abilene-inspired network, we demonstrate theinﬂuence of small buffer on link utilization, packet loss ratio
and the performance of TCP connections passing through therouter. One important result is that, especially when the edge
network becomes faster, decreasing buffer size at core routerscauses unfairness between TCP connections that traverse thecore network and those do not traverse the core network.

keywords: Buffer Size, TCP (Transmission Control Protocol), Fluid Flow Approximation, Large-Scale Network
I. I NTRODUCTION
The router performance is an important factor in Internet
performance. The bandwidth of an output link and the buffer
size of a router have a lot of inﬂuence on the TCP throughput
passing through the router. Traditionally, the size of routerbuffers is determined by the product of the link bandwidth andthe average round-trip time (RTT) of TCP connections passing
through the router. However, recent studies [1, 2] have claimed
that when the number of TCP connections is sufﬁciently large
and the TCP connections are desynchronized, the buffer size
can be decreased to the bandwidth-delay product divided by
the square-root of the number of ﬂows without the underutilization of the link bandwidth. In [3], authors consider the
buffer size and the stability of a network by using control
theory, and recommend that buffer size should be 50 packets
or less. In [4], authors show that the link utilization can be
kept sufﬁciently high with the buffer size of a core router at
20 packets when pacing TCP [4] is deployed or the accesslink is much slower than the backbone link. Using the ns-2
simulator, in [5], authors have shown that when router buffer
size is determined by [1], the packet loss ratio increases by
about 5% to 15% and there is a large variations in the TCP
throughput in the network.
However, these studies [1-4] focus almost exclusively on
the link utilization, and the throughput of TCP connections
passing through the router is not taken into consideration. That1

B. Trafﬁc Model(v, w): link from v to wµ(v, w) : link capacity of link (v, w)" (v, w) : propagation delay of link (v, w)b(v, w) : output buffer size to link (v, w)!
!
!

The amount of network trafﬁc is determined using thegravity model [9]. By applying the basic gravity model, we
assume that the amount of trafﬁc from router v to router w
is proportional to the product of the amount of trafﬁc thatenters the network at router v and the amount of trafﬁc thatleaves the network at router w. In this analysis, we assume
that the network trafﬁc is generated from the edge router in
Fig. 1 to that the endhost is connected. We also assume thatthe amount of trafﬁc injected into/leaving from the edge routeris proportional to the number of endhosts connected to theedge router. Then, the number of TCP connections betweenedge routers is determined to be proportional to the amountof trafﬁc between the edge routers. In summary, the numberof TCP connections that traverse from v to w is deﬁned as:µ(v, w)," (v, w)
W(v, w)

Vb(v, w)!
!
!
Vw: core router: edge router: endhost: TCP connection

Fig. 1: Network Model in the Analysis

modeling a TCP and a network link as independent systems.
By combining these models, we obtain the model for theentire network. In Section IV, by presenting several numericalexamples, we dispute the impact of the small buffer size on thecore network. Finally, in Section V, we conclude the present
paper and discuss future work.

N(v,w)=

bα × Ev · Ew c,(1)where Ev and Ew are the numbers of endhosts connected tothe edge routers v and w, respectively, and α is a weightparameter for determining the overall amount of network
trafﬁc.
In this paper, for the sake of simplicity, we employ the TCP
Reno version for TCP trafﬁc. Note that we can easily treat
other versions of TCP by using appropriate models for TCP
throughput of those version. Moreover, we can also analyze a
network that has different TCP versions in the same network.
Hereafter, TCP Reno is simply denoted as TCP unless noted
otherwise.

II. N ETWORK AND T RAFFIC M ODELS
A. Network Model
Fig. 1 shows the network model used in the analysis. The
model consists of nodes and links. Each node corresponds toa endhost or a router. Let v and w (v, w ∈ R) be nodes, where
R is a set of nodes in a network. The ordered pair (v, w) refers
to the unidirectional link from node v to node w. Note that, in
this analysis, the link (v, w) differs from the link (w, v). Let L
be a set of links in a network and L(χ) be a set of links that
the TCP connection χ traverses. The link capacity and the
propagation delay of link (v, w) are denoted by µ(v,w) andτ(v,w) , respectively. Each router is assumed to have separate
output buffers for each outgoing link. The buffer size of theoutput link buffer to link (v, w) at node v is denoted by b(v,w) .
TCP connections are established between endhosts according to the amount of offered trafﬁc deﬁned in Section IIB. C is a set of all TCP connections in the network. After
determining the route that each TCP connection traverses, we
can determine C(v, w), which is a set of TCP connections thattraverse link (v, w). In the numerical example in Section IV weuse Dijkstra’s shortest path algorithm for determining the routethat each TCP connection traverses. Note that we could apply
any kind of routing algorithm in this analysis. For example,
we could evaluate the effect of the overlay routing algorithm
by applying the routing algorithm for the TCP connections
that join the overlay network.
In this paper, we use a Drop-Tail discipline at an output
buffer of each network, and focus on the average behaviorof queue occupancy at the buffer. Note that we can apply
other kinds of queuing disciplines, such as Random Early
Detection (RED) and a mixture of multiple disciplines, byapplying appropriate models to router buffers. For example,
for RED discipline, we can use the existing model in [8].

III. A NALYSIS
In the analysis, we ﬁrst model a TCP and a network link
as independent discrete-time systems with a ∆ time slot. We
then combine them into an entire network system and create
simultaneous equations. By solving the equations, we canderive various network characteristics, such as the window
size and throughput of TCP connections, the buffer occupancy
and the packet loss ratio of network links. We also propose
a method of decreasing the complexity of the simultaneous
equations by removing links that do not cause congestion. We
omit the explanation of the complexity reducing method dueto the space limitation.
A. Models of TCP Behavior
We focus on the average behavior of a TCP connection,
which is affected by the average window size depending on
the packet loss ratio and round-trip time (RTT). That is, we
model a TCP connection as a system with two inputs (packet
loss ratio and number of packets in the output buffer of each
network link) and one output (congestion window size of the
TCP connection). The packet loss ratio of the TCP connection
is denoted by d, and the TCP congestion window size isdenoted by w. Change in the TCP congestion window size2

connection λχ (k) is given by the following equation from thecongestion window size and the RTT of TCP connection, given
by Eqs. (2) and (4).

is given by [10]
w

←

1
1 4w
− d (1 − dT O (w, d))w(
2
3)
4 w(k)−1 ,−d dT O (w, d)3
w + (1 − d)λχ (k) =where dT O (w, d) is the probability that TCP detects packet
loss by the timeout mechanism when the window size is w
and the packet loss probability is d [11]:Given a packet loss ratio dχ (k) and a RTT rχ (k) at slotk, the congestion window size of the TCP connection χ at
slot k + 1, wχ (k + 1), can be calculated using the following
equations [10];(() 1wχ (k)wχ (k + 1) = wχ (k) +∆ 1 − dχ (k)rχ (k)wχ (k)(()) 1 4 wχ (k)−dχ (k) 1 − dT O wχ (k), dχ (k)
2
3 )
)
(
)( 4 wχ (k)−dχ (k) dT O wχ (k), dχ (k)− 1 . (2)3d(v,w) (k)(v,w)∈L(χ)

Note that L(χ) is a set of links that TCP connection χ
traverses. We can also derive the RTT rχ (k) of the TCP
connection χ as follows;)∑ (q(v,w) (k)τ(v,w) +rχ (k) =,(4)µ(v,w)We therefore derive the standard deviation of the sum of thecongestion window size of the TCP connections for deriving
σ(q(v,w) (k)).
By assuming that the TCP connection is always in thecongestion avoidance phase (this assumption is reasonable
when the packet loss ratio is small), we can regard the variationof the congestion window size as a uniform distribution with alower limit of 2w/3 and an upper limit of 4w/3, where w is theaverage size of the congestion window of the TCP connection.
Consequently, we can obtain the standard deviation of thewindow size of the TCP connection as follows;

where τ(v,w) is the propagation delay of link (v, w).
B. Models of Network Link
We focus on the behavior of a network link when TCP
connections, each of which has a certain value of congestion
window size, traverse the link. Therefore, the network link ismodeled as a system with one input (window sizes of TCP
connections) and two outputs (packet loss ratio and numberof packets in the output buffer of each network link).
The number of packets in the output buffer of link (v, w)
at slot k + 1, q(v,w) (k + 1), is given by()λχ (k) − µ(v,w) ,(7)

χ∈C(v,w)(v,w)∈L(χ)∑= P rob[q(v,w) (k) > b(v,w) ]()
b(v,w) − q(v,w) (k)1= 1 − Erf,2
σ(q(v,w) (k))

where σ(q(v,w) (k)) is the standard deviation of the numberof packets in the output buffer of link (v, w) at slot k, and
Erf () is the error function. Ignoring the number of dropped
packets, the standard deviation of the number of packets inthe output buffer of link (v, w) can be identical to that of thesum of the congestion window size of the TCP connections
traversing link (v, w) [1];∑σ(q(v,w) (k)) = σ wχ (k) .
(8)

Let q(v,w) (k) and d(v,w) (k) be the number of packets in the
output buffer and the packet loss ratio at link (v, w) at slotk, respectively. We can derive the packet loss ratio for TCP
connection χ at slot k, denoted by dχ (k), as follows;∏dχ (k) = 1 −(1 − d(v,w) (k)).
(3)

q(v,w) (k) + ∆(6)

Authors [1] have revealed the following characteristic of
TCP connections traversing a link: when the number of TCP
connections is sufﬁciently large and the TCP connections
do not behave in a synchronized fashion, the sum of thecongestion window size of the TCP connections follows anormal distribution. Since we are interested in large-scale
networks with a large number of TCP connections, we canutilize this characteristic. Then, we can calculate d(v,w) (k),the packet loss ratio at the buffer of link (v, w) at slot k, as
follows [1];dT O (w, d) =(1 − (1 − d)3 ) (1 + (1 − d)3 (1 − (1 − d)w−3 )).
(1 − (1 − d)w )q(v,w) (k + 1) =wχ (k)rχ (k)

σ(w)

=

w
√ .
3 3

By assuming that the window size of all TCP connections
follow an identical independent distribution, we can determine
the standard deviation of the sum of the window size of the
TCP connections traversing link (v, w) by using the following
equation;




√ ∑
∑
σ
σ(wχ (k))2  (.9)
wχ (k) = σ (5)χ∈C(v,w)∑
whereχ∈C(v,w) λχ (k) is the sum of the throughput of
TCP connections traversing link (v, w) at slot k, and µ(v,w)
is capacity of the link (v, w). The throughput of the TCPχ∈C(lv,w )3

χ∈C(v,w)

TABLE I
L INK P ROPERTY
Link
lcc
lcm
lme
lee

Bandwidth
10 [Gbit/s] (OC192)
10 [Gbit/s] (OC192)
10 [Gbit/s] (OC192)
1 [Gbit/s] (GE)Prop. Delay
0.01 [ms]0.1 [ms]
0.1 [ms]
1 [ms]

C. Connecting Systems and Analysis:core router:middle router

The congestion window size, RTT, packet loss ratio,
throughput of TCP connection χ, packet loss ratio at output
buffer of link (v, w) and number of packets in output buffer oflink (v, w) in steady sate (k → ∞) are denoted by wχ∗ , rχ∗ , d∗χ ,∗λ∗χ , d∗(v,w) , and q(v,w)
respectively. We can regard Eqs. ((2)– (9)) as simultaneous equations by equating wχ (k + 1) ≡∗wχ (k) ≡ wχ∗ and q(v,w) (k + 1) ≡ q(v,w) (k) ≡ q(v,w). By∗equating wχ (k + 1) ≡ wχ (k) ≡ wχ and q(v,w) (k + 1) ≡∗q(v,w) (k) ≡ q(v,w), ∆ is eliminated in the simultaneous
equations. That is, the solutions of simultaneous equationsand ∆ are independent of each other. By solving thesesimultaneous equations, we can derive the window size ofeach TCP connection, the number of packets in each output
buffer and the packet loss ratio at each network link. The
straightforward design of the analysis is one of the advantagesof our analysis method.

:edge router:endhost

: lcc
: lcm

:lme
: lee

Fig. 2: Abilene-inspired Network [6]√TCP connections C × RT T / N , where N is the numberof TCP connections. Note that the buffer size of the output
buffer of lcm , lme , and lee is determined by the bandwidthdelay product.
We consider the following two situations for analysis: theﬁrst case is that the bandwidth of the edge network link iscomparatively small, and the other case is that the bandwidthof the edge network links is large. On account of space, we
just give the brief explanation for the result of the former
situation. When the link bandwidth of edge network is small,
we can not observe signiﬁcant differences in performance
between traditional and small buffer sizings. This is because
the bottleneck in the network is located at lme in this case. Thatis, the trafﬁc injected into to lcc is limited by the bandwidthof lme . Thus, the utilization of lcc is not so large to makemuch differences in the packet loss ratio of lcc . In terms of the
TCP throughput, we can conclude that decreasing the buffer
size in the network where the edge network is slow makes noadvantage.
We then investigate the effects of decreasing buffer size
when the bandwidth of the edge network links increases. Tab. I
shows the parameter settings for links. We set α in Eq. (1) to
0.12, which means the total number of TCP connections in the
network becomes 52, 394. The average two-way propagation
delay of TCP connections in the network is about 4.83 [ms]and the average number of TCP connections on the link lcc is
3, 000, and we use these values to determine the buffer size.
We expect that, with these settings, the link utilization of thecore network (lcc ) would increase and the conditions in [1]for decreasing buffer sizes would be satisﬁed.
Tab. II shows the average throughput and the average roundtrip time of TCP connections, the average link utilization, andthe average packet loss ratio for traditional and small buffers.
We also found that the link utilization and the packet loss ratioof lcc with small buffers are smaller than those of lcc withtraditional size buffers. When the buffer size of the output
buffer of lcc decreases, the packet loss ratio of lcc increases,
which degrades the throughput of TCP connections passing
through the core network (lcc ). Then the TCP connections
that do not traverse the core network dispossess the TCP

IV. E FFECT OF DECREASING ROUTER BUFFER SIZEIn this section, we investigate the effect of decreasing buffer
size on the performance of the whole network and of TCP
connections by applying the proposed analysis method to the
Abilene-inspired network [6]. Due to limitation of space, we
do not show the validation of our analysis method, we veriﬁed
the validity of our analysis method by comparing the ns2 simulation results with analysis ones. Fig. 2 shows theAbilene-inspired network used in this section. This network
topology is designed based on the characteristics of the actualrouter-level topology where the core routers have a smaller
number of links with higher bandwidth, whereas the edge
routers have a larger number of links with lower bandwidth.
The topology consists of 11 core routers, 54 middle routers,
106 edge routers and 812 endhosts. There are 901 bidirectional
links between routers and endhosts. For simplicity, we denotelinks between core routers as lcc , those between core routers
and middle routers as lcm , those between middle routers andedge routers as lme , and those between edge routers andendhosts as lee .
We compare the performance of the network and TCP
connections when the small buffer is deployed in the core
network with performance when the traditional size buffer isdeployed in the core network. We determine the traditional
buffer size of the output buffer of lcc by the bandwidth-delay
product C ×RT T , where C is the link bandwidth, and RT T is
the average round-trip time of TCP connections. Small buffer
size is determined by [1], which corresponds to the bandwidthdelay product divided by the square-root of the number of4

TABLE IIP ERFORMANCE OF N ETWORK AND TCP C ONNECTIONS WHEN E DGE N ETWORK IS FAST
buffersmall

traditional

link
lcc
lcm
lme
lee
lcc
lcm
lme
lee

Link Utilization
0.638
0.737
0.459
0.690
0.968
0.748
0.456
0.685

Packet Loss Ratio
0.001973
0.000077
0.000989
0.000003
0.004195
0.000274
0.000665
0.000006

TCP Throughput [Mbit/s]

Round-Trip Time [ms]

9.29

16.72

9.23

23.93

TABLE IIITCP T HROUGHPUT [M BIT / S ] BY NUMBER OF H OPS
buffersmall
traditional

4 hops160.32141.94

6 hops
67.33
47.04

7 hops3.29
7.10

connections that traverse the core network in the edge network(lcm and lme ). As a result, the link utilization of lcc and thepacket loss ratio of lcc with the small buffers are lower thanthose with traditional size buffers. In addition, there is almost
no difference in the average TCP throughput in the network
between small buffers and traditional size buffers. On theother hand, the average round-trip time of the traditional size
buffers is larger than that of the small buffers. This is because
traditional size buffers are much larger than small buffers andbecause the link utilization of lcc is high.
Next, we investigate the TCP throughput in more detail.
Tab. III shows the TCP throughput for the different numbersof link hops that TCP connections traverse. Note that the TCP
connections with four and six hops do not traverse the core
network and the TCP connections with seven or more hops do.
The table shows that the throughput of the TCP connections
which do not traverse the core network with small buffers isgreater than that with traditional size buffers. On the other
hand, the throughput of the TCP connections which traverse
the core network with small buffers is less than that withtraditional size buffers. This supports the explanation of low
packet loss ratio and the small link utilization of lcc when small
buffers are deployed in the core network. That is, the TCP
connections that do not traverse the core network dispossess
the TCP connections that traverse the core network in the edge
network (lcm and lme ). This means that by decreasing thebuffer size of the core routers, the relationship between TCP
connections that pass through the core network and those do
not is less fair than the well-known TCP unfairness caused bydifferent round-trip time. From these results, we can conclude
that the buffer size of the core routers should not be decreased
when the utilization of the core network links is sufﬁciently
high.

8 hops2.41
3.33

9 hops
2.15
2.32

10 hops
1.96
1.79

behavior of TCP connections in large-scale networks with
100/1,000/10,000 routers/endhosts/links and 100,000 concurrent TCP connections. We investigated the effectiveness ofdecreasing the buffer size of the core routers at both high andlow utilization of core network links by applying our analysis
method to the Abilene-inspired network. We concluded that
decreasing core router’s buffer size has almost no meritwhen the performance of the whole network, including thecore and the edge networks, is taken into account. Future
work will further investigate decreasing buffer size, especiallywith regard to the mixture of network services that includes
streaming services.
R EFERENCES[1] G. Appenzeller, I. Keslassy, and N. McKeown, “Sizing router buffers,”
in Proceedings of ACM SIGCOMM, Sept. 2004, pp. 281–292.
[2] D. Wischik and N. McKeown, “Part I: Buffer sizes for core routers,”
ACM SIGCOMM Computer Communication Review, vol. 35, no. 3, pp.
75–78, July 2005.
[3] G. Raina, D. Towsley, and D. Wischik, “Part II: Control theory for buffer
sizing,” ACM SIGCOMM Computer Communication Review, vol. 35,
no. 3, pp. 79–82, July 2005.
[4] M. Enachescu, Y. Ganjali, A. Goel, N. McKeown, and T. Roughgarden,“Routers with very small buffers,” in Proceedings of IEEE INFOCOM
2006, Apr. 2006.
[5] A. Dhamdhere and C. Dovrolis, “Open issues in router buffer sizing,”
ACM SIGCOMM Computer Communication Review, vol. 36, pp. 87–92,
Jan. 2006.
[6] D. Alderson, L. Li, W. Willinger, and J. C. Doyle, “Understanding
Internet topology: principles, models, and validation,” IEEE/ACM Transactions on Networking, vol. 13, no. 6, pp. 1205–1218, Dec. 2005.
[7] A. V. Aho and J. E. Hopcroft, The Design and Analysis of Computer
Algorithms. Addison-Wesley Longman Publishing Co., Inc., 1974.
[8] H. Hisamatu, H. Ohsaki, and M. Murata, “Steady state and transient statebehaviors analyses of TCP connections considering interactions between
TCP connections and network,” International Journal of Communication
Systems, vol. 18, pp. 619 – 637, Sept. 2005.
[9] A. Kowalski and B. Warﬁeld, “Modelling trafﬁc demand between nodes
in a telecommunications network,” in Australian Telecommunications
and Networks Conference (ATNC), Dec. 1995.
[10] H. Hisamatu, H. Ohsaki, and M. Murata, “Fluid-based analysis of a
network with DCCP connections and RED routers,” in Proceedings ofInternational Symposium on Applications and the Internet (SAINT 2006),
Jan. 2006, pp. 22–29.
[11] J. Padhye, V. Firoiu, D. Towsley, and J. Kurose, “Modeling TCP
throughput: a simple model and its empirical validation,” in Proceedingsof ACM SIGCOMM, Sept. 1998, pp. 303–314.

V. C ONCLUSION AND F UTURE W ORK
In this paper, we reported the effect on the network and
TCP connections of decreasing buffer size in the core network.
We ﬁrst proposed a novel method of analyzing the average
5