IEICE TRANS. COMMUN., VOL.E85–B, NO.8 AUGUST 2002

1434

PAPER

Special Issue on Outstanding Papers from APCC 2001

A Buﬀer Management Mechanism for Achieving
Approximately Fair Bandwidth Allocation in
High-Speed Networks
Takashi MIYAMURA† , Takashi KURIMOTO† , Kenji NAKAGAWA†† , Regular Members,
Prasad DHANANJAYA†† , Nonmember, Michihiro AOKI† ,and Naoaki YAMANAKA††† , Regular Members

SUMMARY We propose a buﬀer management mechanism,
called V-WFQ (Virtual Weighted Fair Queueing), for achieving an approximately fair allocation of bandwidth with a small
amount of hardware in a high-speed network. The basic process for the allocation of bandwidth uses selective packet dropping that compares the measured input rate of the ﬂow withan estimated fair share of bandwidth. Although V-WFQ is a
hardware-eﬃcient FIFO-based algorithm, it achieves almost ideal
fairness in bandwidth allocation. V-WFQ can be implemented
in the high-speed core routers of today’s IP backbone networks
to provide various high-quality services. We have investigated
V-WFQ’s performance in terms of fairness and link utilization
through extensive simulation. The results of simulation showthat V-WFQ achieves a good balance between fairness and link
utilization under various simulation conditions.
key words: fairness, QoS, Di -serv, high-speed network, band-

width management

1.

Introduction

In today’s Internet, the sharing of network resourcesamong the many ﬂows is on a best-eﬀort basis. A malicious user of a network may thus be able to get more
bandwidth than a well-behaved user. Protecting bandwidth for well-behaved ﬂows from ill-behaved ﬂows isthus important in the Internet environment. One way
to stop ill-behaved ﬂows from adversely aﬀecting otherﬂows is to allocate a fair bandwidth to each ﬂow.
Two types of algorithms can be used to achieve
fair bandwidth allocation: scheduling-based algorithms
and preferential-dropping-based algorithms.
Scheduling-based algorithms (e.g., Weighted Fair
Queueing (WFQ) [4] and its variants [5]–[7]) are known
to be ideal as mechanisms allocating bandwidth ina fair way and providing guaranteed QoS. In theseapproaches, however, must be maintained a separate
queue for each ﬂow and state is maintained on a perManuscript received February 1, 2002.
Manuscript revised April 10, 2002.
†
The authors are with NTT Network Service System
Laboratories, NTT Corporation, Musashino-shi, 180-8585
Japan.
††
The authors are with Electrical Department, Nagaoka
University of Technology, Nagaoka-shi, 940-2188 Japan.
†††
The author is with NTT Network Innovation Laboratories, NTT Corporation, Musashino-shi, 180-8585 Japan.

ﬂow basis, so that hardware eﬃciency is out of the question. More precisely, WFQ has a computational complexity of O(log(n)), where n is the number of ﬂows
currently queued at a router. WFQ is hard to implement in high-speed backbone routers with trunks thatcarry large numbers of ﬂows.
Core-Stateless Fair Queueing (CSFQ), proposed by
Stoica et al. [9], is a well-known preferential-droppingbased algorithm. The CSFQ mechanism achieves almost ideal fairness without using the per-ﬂow statesof the core routers. To avoid maintaining the per-ﬂow
state for each router, they use a distributed algorithm inwhich per-ﬂow state is only maintained for edge routers
and is not maintained for core (non-edge) routers. Anedge router estimates the arrival rate for each ﬂow andthis information is carried by a label in each packet’s
header to the core router, which utilizes this information in deciding whether to discard or queue each arriving packet. Thus, in terms of the core routers, CSFQ issimpler and easier to implement than WFQ. However,
the architecture of the edge routers is still complicated.
Although it is easy to extend CSFQ to support ﬂows
that have diﬀerent weights, the algorithm is incapableof accommodating situations where the relative weightsof ﬂows diﬀer from router to router.
Recently, Cao et al. [10] have proposed Rainbow
Fair Queueing (RFQ), which, like CSFQ, may be used
to achieve approximately fair sharing. The approachhere is to divide each ﬂow into a set of layers, basedon rate. At the edge routers, the packets in a ﬂow
are marked with layer labels rather than with explicit
rates of ﬂows. While the calculation of fair share in
CSFQ requires exponential averaging, the core routersin RFQ only need to perform threshold-based dropping;
the routers are thus simple and amenable to hardware
implementation. However, the approach applied in theedge routers in their remains complicated. It is important to note that the application of either CSFQ or
RFQ requires to the Internet of today extension of theIP packet’s header.
We have proposed the basic architecture of anactive queue-control scheme, called V-WFQ (Virtual
Weighted Fair Queueing), which achieves almost fair

MIYAMURA et al.: A BUFFER MANAGEMENT MECHANISM

1435

allocation of bandwidth and minimum bandwidth guarantees in high-speed networks [1], [2]. The word “Virtual” here indicates that V-WFQ emulates the function
and performance of WFQ without using sophisticatedper-ﬂow queueing. In this paper, we present the details of the V-WFQ algorithm and an investigation of
its performance through extensive experiments by simulation.
This algorithm’s basic process for the fair allocation of bandwidth uses preferential packet dropping tocompare the measured input rate of the ﬂow with anestimated fair share of bandwidth. Although V-WFQ isa hardware-eﬃcient FIFO-based algorithm, it is capable of achieving almost ideal fair bandwidth allocation.
Unlike CSFQ and RFQ, V-WFQ does not require any
extensions to the headers of IP packets and does notneed to distinguish between the core and edge routersof the network, so it is easy to apply to today’s Internet
backbone networks.
2.

Proposed Algorithm

buﬀer of the output link.
2.2 The Algorithm of V-WFQ
2.2.1

Estimating Flow RateTo estimate the packet-arrival rate for a ﬂow, we use
the simple ‘jumping window’ method. This requires
only two states for each ﬂow and involves no complex
computation to estimate the arrival rate. Let Ri be
the estimated rate of ﬂow i and Tw be the window sizefor using with the method. Let Cti be the cumulative
packet length of the ﬂow i. At the beginning of thewindow, Cti is set to 0. When a packet of ﬂow i arrives,
Cti is renewed in the following way:
Cti = Cti + li ,where li is the packet length. At the end of the window,
the estimated rate Ri is calculated as
Ri =

Cti
.
Tw

2.1 An Overview of V-WFQ

Cti is then reset to 0.

The buﬀer architecture of a V-WFQ router is shown in
Fig. 1. The proposed mechanism: (1) estimates the input rates of the ﬂows at each router in the network, (2)calculates the bandwidth allocated to each ﬂow at eachrouter, and (3) uses FIFO buﬀering with preferential
dropping.
We avoid the need for per-ﬂow buﬀer management
and scheduling by using FIFO buﬀers with preferential
packet discarding on arrival. Thus, as well as providing
improved fairness, our proposed mechanism is suited toeﬃcient implementation in high-speed core routers.
A V-WFQ router measures the input rates of theﬂows it is processing. When each packet arrives, the
V-WFQ router calculates a fair bandwidth for the corresponding ﬂow on the basis of the degree of output-linkcongestion. The router decides whether or not to discard a given packet by comparing the estimated input
rate with the calculated result for allocated bandwidth.
If the packet is not discarded, it is enqueued in the

2.2.2

Deciding to Drop or Enqueue a Packet

The V-WFQ router estimates the degree of output-linkcongestion from the variation in queue length. The
following terms are used in calculating the allocatedrate:• N : number of sources,• weighti : weight of ﬂow i,• Ri : estimated arrival rate of packets in ﬂow i,• AR: the fair share for a ﬂow,
• ARi : the bandwidth allocated to ﬂow i,• ARmax : maximum allocatable bandwidth,• M GR: per-ﬂow bandwidth achieved in an ideal situation,• tupdate : time interval for the updating of AR,• C: capacity of the output link.
The ﬂowchart and pseudocode of the V-WFQ routeralgorithm are given in Figs. 2 and 3, respectively. The
router updates the fair share AR according to the current congestion status of the output link at the end of
every time interval tupdate . When the average queue
length qaverage reaches the threshold qmax , the output
link is assumed to be congested and AR should be decreased. If qaverage is below the threshold qmin , the output link is assumed to be underutilized and AR should
be increased to raise the degree of link utilization.
When a packet arrives, the router calculates the
bandwidth ARi which is allocated to the ﬂow.
ARi = weighti · AR

Fig. 1

Buﬀer architecture of a V-WFQ router.

Then, the V-WFQ router decides whether or not to discard the arriving packet. We use the random-dropping

IEICE TRANS. COMMUN., VOL.E85–B, NO.8 AUGUST 2002

1436

Fig. 2The V-WFQ algorithm.

Fig. 4 Comparison of V-WFQ with WFQ in terms of required
memory.

this approach avoids the congestion collapse and provides low levels of latency.
2.2.3

Fig. 3

Algorithm of packet dropping decision.

approach. The probability of the arriving packet being
dropped pdrop is given by Ri −ARi
if Ri ≥ ARi
Ri
pdrop =
0
if Ri < ARi
If one ill-behaved ﬂow keeps sending packets at a higher
rate than its fair share, the V-WFQ router discards
packets of this ﬂow on a probabilistic basis and provides
only that bandwidth which corresponds to the calculated fair share for the ill-behaved ﬂow. This mechanism can ensure a fair allocation of bandwidth for all
ﬂows that share a given link’s resources. Furthermore,by dropping packets long before the buﬀer becomes full,Hardware Implementation

Here we compare V-WFQ with WFQ in terms of thecost of hardware implementation. In VLSI, this is directly dependent on the chip area that is required,
which in turn is dominated by the requirement for memory [12].
Figure 4 is a comparison of the amount of memory
required by V-WFQ and WFQ across a range of numbers of ﬂows. Much less memory is required by V-WFQ
than is required by WFQ. For example, V-WFQ only
requires about 11 kbytes for 4000 ﬂows, while WFQ
requires about 1560 kbytes. V-WFQ is thus a more
hardware-eﬃcient algorithm than is WFQ.
However, V-WFQ needs to measure the input rateof each ﬂow and compute a fair bandwidth. The calculation of the fair share consists of simple operations
and its computational complexity does not depend on
the number of ﬂows. Per-ﬂow traﬃc measurement is
now becoming common in high-speed routers that support line speeds of OC-48 and higher [17]. With today’s
technology, it is feasible to implement V-WFQ to support several thousands of ﬂows at line speeds of OC-48
and higher.
2.2.4

A New Network Service Based on V-WFQ

We have proposed several new network services that are
based on the use of V-WFQ routers [3]. Here we introduce one proposed service. A network which consists of
V-WFQ routers is capable of providing a new VPN service as well as a high-quality IP service. Figure 5 shows
an isolated-VPN service where the bandwidth is determined on the basis of the tariﬀ concept. The word “isolated” here means that the bandwidth for each VPN is
not aﬀected by the number of VPN connections. In

MIYAMURA et al.: A BUFFER MANAGEMENT MECHANISM

1437

Fig. 5 Example of a new VPN service (BW indicatesbandwidth).

Fig. 6One-link network model.

other words, the bandwidth for each VPN is provided
independently of the other VPNs with which it shareslink resources and is determined by the VPN’s connection weight alone. Conventional Diﬀ-serv routers canguarantee only a minimum bandwidth. Excess bandwidth is then equally apportioned among the VPNs. In
the proposed service, on the other hand, bandwidth inexcess of the minimum guaranteed bandwidth is allocated to each of the VPNs according to its weight.
The example shows two ISPs connected to a network and taking advantage of the isolated-VPN service. VPN Service providers can charge each VPN (orISP) according to the bandwidth with which it is actually provided. For example, the tariﬀ for VPN-1 is$100/month while that for VPN-2 is $1000/month; accordingly, VPN-2 has better quality and gets always
more bandwidth than VPN-1. Each user can be assuredof the required bandwidth even when all go through thesame bottleneck link. This service will become the basis of next-generation ISP services and of premium IP
services.
3.

Performance Evaluationn UDP ﬂows. Each end host is connected to the router
via a 10-Mbps link and one end host persistently transmits packets to the other end host. We compared theperformance of V-WFQ with Random Early Discard(RED) [13], Flow Random Early Discard (FRED) [7],Deﬁcit Round Robin (DRR) [14], CSFQ, and DropTail.
RED monitors the average queue length and starts
to drop arriving packets on a probabilistic basis when
the average queue length exceeds a certain threshold.
To make a router start to drop packets before its buﬀer
becomes full, RED gives an early congestion indication
to each ﬂow and avoids congestion collapse. However,RED does not provide fairness among competing ﬂows.
FRED brings fairness of a bandwidth allocation to RED
by maintaining a per-ﬂow state. FRED drops packets
from ﬂows that have had many packets dropped in thepast and from ﬂows that have longer queues than the
average queue length.
DRR is a well-known implementation of WFQ thathas a computational complexity O(1). The buﬀer management scheme of DRR requires a sophisticated perﬂow queueing mechanism, while the other algorithms
applied in our simulation only require simple FIFObuﬀer mechanisms. DRR achieves a higher degree of
fairness than the other algorithms, so we used DRR as
the benchmark for the fair allocation of bandwidth.
All simulations were performed in ns-2 [15]. The
simulation code for the DRR, RED, FRED, and CSFQ
algorithms is supplied with the ns-2 package. In all simulations, unless otherwise stated, we used the following
assumptions and parameters.
• All TCP sources were persistent TCPs and started
at the same time. For a TCP ﬂow, the maximum
segment size (MSS) was 1000 bytes and the version
of TCP was Reno. The TCP hosts transmitted
ﬁles of inﬁnite size by FTP to the corresponding
end hosts.
• The UDP hosts sent packets at a constant bit rate(CBR) of k kbps, where k is a variable, and all
started sending at the same time. The packet sizeof the UDP ﬂows was set to 500 bytes.
• The output buﬀer size was 128 KB.
• All ﬂows had the same weight values.
• The following parameters were used with V-WFQ.
The jumping window size was 50 ms. qmax andqmin were 128 KB and 8 KB, respectively. Fairsharing M GR was 625 kbps and ARmax was
10 Mbps. α was 0.05.

3.1 Conﬁguration of the Simulation

3.2 Indices of Performance

To investigate the performance of V-WFQ when there
is a single congested link in the network, we considered
the network conﬁguration shown in Fig. 6. The congested link is between two routers. The link, which has
a capacity of 10 Mbps, is shared by m TCP ﬂows andWe evaluated the performance of our algorithms interms of fairness and eﬃciency. Let N be the numberof TCP sources, C be the capacity of the bottleneck
link, xi be the measured throughput of the i-th TCP
source, and zi be the ideal throughput of the i-th TCPIEICE TRANS. COMMUN., VOL.E85–B, NO.8 AUGUST 2002

1438

source. We deﬁne eﬃciency asNxieﬃciency = i=1 .
C

had the same performance as DRR and much better
performance than FRED.
3.3.2

We measured the fairness of algorithms in terms of thefairness index (FI) [16], which is deﬁned as
2

N zi
i=1 xifairness index =
N×




i=1

zi
xi

2 .

3.3 Results of Simulation
3.3.1 Fair Allocation for UDP Flows
In the ﬁrst experiment, we evaluated the performanceof V-WFQ when all hosts were transmitting an inﬁnite amount of data according to the UDP. Each of
the 16 UDP sources sent packets at i × 10
16 kbps, wherei (1, . . . , 16) is the ﬂow ID. Each UDP source constantly
had data to transmit so the backbone link was always severely congested. Under max-min fairness [16],each ﬂow should have achieved an average throughput
of 626 kbps. Figure 7 shows the average throughput
achieved by the 16 UDP sources sharing the bottleneck link which was conﬁgured with V-WFQ, DRR,
CSFQ, FRED, RED or DropTail. Table 1 shows theindex of fairness and the level of eﬃciency for each algorithm used in this simulation. The throughput achievedby RED or DropTail was almost exactly in proportion
to the input rate of each ﬂow, while the throughput
achieved by V-WFQ, DRR, or CSFQ was nearly constant at around 626 kbps. These results show that RED
and DropTail completely failed to allocate fair amountsof bandwidth to the ﬂows during periods of congestion
while DRR and CSFQ achieved almost ideal fairness
in sharing bandwidth among competing ﬂows. V-WFQ

A Single Misbehaving Flow

In the second experiment, we examined the levels ofprotection provided by the various algorithms for wellbehaved ﬂows in the presence of a single misbehaving
ﬂow. In this simulation, we assumed that 15 TCP ﬂows
and 1 UDP ﬂow shared a 10-Mbps bottleneck link. The
UDP source sent packets at the constant bit rate of
10 Mbps during the 30 seconds of simulation. Figure 8
shows the normalized throughput, which is deﬁned as
the throughput/fair-share ratio. Note that the normalized throughput for each ﬂow should equal 1.0 in the
optimal situation. Table 2 shows the fairness index andlevel of eﬃciency achieved by each algorithm used inthis simulation.
Table 1Comparison of fairness indices and eﬃciency.
V-WFQ
DRR
CSFQ
FRED
RED
DropTailEﬃciency
0.999
0.999
0.999
0.999
0.999
0.999

Fairness
0.999
0.999
0.999
0.859
0.766
0.768

Fig. 8 Throughput for 1 UDP ﬂow and 15 TCP ﬂows sharing
a 10-Mbps bottleneck link. The UDP ﬂow i sends packets at
10 Mbps.

Table 2 Indices of eﬃciency and fairness for a conﬁguration
with a single misbehaving UDP ﬂow and 15 TCP ﬂows.

Fig. 7 Throughput for 16 UDP ﬂows sharing a 10-Mbps bottleneck link. Each UDP ﬂow i sends packets at i times its fair
allocation (626 kbps).

V-WFQ
DRR
CSFQ
FRED
RED
DropTailEﬃciency

Fairness

0.995
1.00
0.996
1.00
1.00
1.00

0.926
0.973
0.952
0.735
0.07780.0778MIYAMURA et al.: A BUFFER MANAGEMENT MECHANISM

1439

Under FIFO and RED, the misbehaving UDP ﬂow
got more than 8 Mbps, while each of the other TCP
ﬂows received less than 30 percent of fair share. Under V-WFQ, the UDP ﬂow got about twice the fairbandwidth, but most of the TCP ﬂows got more than85 percent of the fair bandwidth. CSFQ shows similartendencies. Under DRR, most of the ﬂows got almost
the ideal bandwidth. These results show that RED
and DropTail failed to provide fair share to the wellbehaved TCP ﬂows while DRR, CSFQ, and V-WFQ
protected the TCP ﬂows against the over-transmitting
UDP ﬂow and achieved almost ideal fairness. On fairness index, CSFQ slightly outperformed V-WFQ. BothCSFQ and V-WFQ are FIFO-based algorithms and require per-ﬂow traﬃc measurement. In V-WFQ, thesimple jumping-window method is used to measure perﬂow traﬃc, while CSFQ requires complex exponential
averaging at a high-speed core router. The diﬀerencein performance is traded-oﬀ against the cost of implementation.

and FIFO, the allocation of shared bandwidth to eachﬂow was independent of its weight. The throughput
achieved by V-WFQ or DRR was proportional to its
weight. RED and FIFO failed to ensure fairness interms of throughput, while V-WFQ and DRR achieved
almost ideal fairness.
Figure 10 compares the queue dynamics for VWFQ and DRR. The queue length of DRR is the sum of
the length of the separate per-ﬂow queues. The queue
length for V-WFQ ﬂuctuated greatly between 0 kbytes
and 60 kbytes, while the length for DRR tended to stabilize at a higher level of buﬀer occupancy, i.e., around90 kbytes. V-WFQ estimated its fair allocations foreach ﬂow from the queue length, hence the rate control
of a V-WFQ router ceases to operate the queue lengthis not becoming longer. The average queue length wasmuch shorter for V-WFQ than for DRR. V-WFQ, like
RED, starts to drop packets before the buﬀer becomes
full, so it gives an early congestion indication to each
ﬂow and hence can provide much lower latency thanDRR.

3.3.3 Flows with Diﬀerent Weights
4.
Next, we investigated the performance of V-WFQ forﬂows with diﬀerent weights. We compared the performance of V-WFQ with DRR in terms of throughput
achieved for each ﬂow and of queue dynamics. Here, thenumber of source-destination pairs was 5. The weightweighti is given byweight1 : weight2 : · · · : weight5 = 1 : 2 : · · · : 5.
In this simulation, the sources were all TCP sources.
During the 30-s simulation, each TCP source had an
inﬁnite amount of data to transmit so the backbone
link was always severely congested. The ideal result isthe allocation of bandwidth to each ﬂow in proportion
to its weight.
Figure 9 shows the average throughput achieved
for the 5 TCP sources over a 30-s interval. Under RED

Fig. 9 Average throughput achieved by each of the 5 TCP
ﬂows with diﬀerent weights.

Concluding Remarks

We have proposed a FIFO-based mechanism called VWFQ that achieves fairness in throughput and haveinvestigated its performance in terms of both fairness
and link utilization through extensive simulations. In
this investigation, we compared the performance of VWFQ with DRR and other algorithms. DRR requires
a sophisticated per-ﬂow queueing mechanism, while VWFQ only requires simple FIFO-buﬀer mechanisms.
DRR achieved a higher degree of fairness than the otheralgorithms, so we used DRR as the benchmark for thefair allocation of bandwidth. The results of simulation
show that V-WFQ achieves almost ideal fairness undervarious simulated conditions. In particular, we shouldnote that it showed almost the same levels of performance as DRR and achieved a much higher degree of
fairness than FRED, which, like V-WFQ, is a preferential dropping algorithm.
It is also possible to use the V-WFQ architecture toprovide minimum bandwidth guarantees for ﬂows. One
example of a new application which V-WFQ allows is

Fig. 10

Queue dynamics for V-WFQ and DRR.

IEICE TRANS. COMMUN., VOL.E85–B, NO.8 AUGUST 2002

1440

an IP VPN backbone network that provides minimum
bandwidth guarantees to each of multiple VPNs.
References[1] T. Miyamura, T. Kurimoto, K. Nakagawa, P. Dhananjaya,
M. Aoki, and N. Yamanaka, “A new queueing mechanism
for achieving fair bandwidth allocation in high-speed networks,” Proc. APCC 2001, vol.E84-B, pp.473–476, 2001.
[2] T. Miyamura, T. Kurimoto, K. Nakagawa, P. Dhananjaya, M. Aoki, and N. Yamanaka, “Active queue control
scheme for achieving approximately fair bandwidth allocation,” Proc. IEEE ICC, vol.2, pp.1269–1273, 2002.
[3] N. Yamanaka, T. Kurimoto, T. Miyamura, and M.
Aoki, “MSN Type-X: Next generation Internet backbone switch/router architecture,” Proc. IEEE ICC, vol.4,
pp.2085–2099, 2002.
[4] A. Parekh and G. Gallager, “A generalized processor sharing approach to ﬂow control in integrated services networks: The single-node case,” IEEE/ACM Trans. Networking, vol.1, no.3, pp.344–357, 1993.
[5] S.J. Golestani, “A self-clocked fair queueing scheme forbroadband applications,” Proc. IEEE INFOCOM, vol.2,
pp.636–645, 1994.
[6] S. Suri and G. Varghese, “Leap forward virtual clock:A new fair queueing scheme with guaranteed delays
and throughput fairness,” Proc. IEEE INFOCOM, vol.3,
pp.557–565, 1997.
[7] M. Schreedhar and G. Varghese, “Eﬃcient fair queueing
using deﬁcit round robin,” Proc. SIGCOMM’95, Sept. 1995.
[8] M. Katevenis, S. Sidiropoulos, and C. Courcoubetis,“Weighted round-robin cell multiplexing in a generalpurpose ATM switch chip,” IEEE J. Sel. Areas Commun.,vol.9, no.8, pp.1265–1279, 1991.
[9] I. Stoica, S. Shenker, and H. Zhang, “Core-stateless fairqueueing: Achieving approximately fair bandwidth allocations in high-speed networks,” Proc. ACM SIGCOMM’98,
pp.118–130, Sept. 1998.
[10] Z. Cao, Z. Wang, and E. Zegura, “Rainbow fair queueing: Fair bandwidth sharing without per-ﬂow state,” Proc.
IEEE INFOCOM 2000, vol.2, pp.922–931, March 2000.
[11] B. Braden, D. Clark, J. Crowcroft, B. Davie, S. Deering, D.
Estrin, S. Floyd, V. Jacobson, G. Minshall, C. Partridge,
L. Peterson, K. Ramakrishnan, S. Shenker, J. Wroclawski,
and L. Zhang, “Recommendations on queue and congestion
avoidance in the Internet,” IETF, RFC2309, April 1998.
[12] M. Grossglauser and S. Keshav, “On CBR service,” Proc.
IEEE INFOCOM, pp.129–137, 1996.
[13] S. Floyd and V. Jacobson, “Random early detection gateways for congestion avoidance,” IEEE/ACM Trans. Networking, vol.1, no.4, pp.397–413, 1993.
[14] D. Lin and R. Morris, “Dynamics of random early detection,” Proc. SIGCOMM’97, pp.127–137, Oct. 1997.
[15] UCB/LBNL/VINT, “Network Simulator - NS (Version 2),”
http://www-mash.cs.berkley.edu/ns/[16] R. Jain, A. Durresi, and G. Babic, “Throughput fairness
index: An explanation,” ATM Forum, 99-0045, 1999.
[17] Cisco Systems Inc., “Cisco Documentation,” http://www.
cisco.com /univercd/home/home.htm

Takashi Miyamura
received the B.S.
and M.S. degrees from Osaka University,
Osaka, Japan, in 1997 and 1999, respectively. In 1999, he joined NTT (Nippon
Telegraph and Telephone Corp.) Network
Service Systems Laboratories, where he
was engaged in research and developmentof a high-speed IP switching router. He is
now researching future photonic IP networks and an optical switching system.
He received Paper Awards from the 7th
Asia-Paciﬁc Conference on Communications in 2001. He is amember of the Operations Research Society of Japan.

Takashi Kurimoto
graduated fromthe Tokyo Institute of Technology, Japan,
where he received B.E. and M.E. degrees
in applied physics 1992 and 1994, respectively. In 1994, he joined Nippon
Telegraph and Telephone Corporation’s(NTT’s) Network Service Systems Laboratories, Tokyo Japan. He has been engaged in researching the switching technology for high-speed computer networks
and multimedia communication networks.

Kenji Nakagawa
received the B.S.,
M.S. and D.S. degrees from Tokyo Institute of Technology, Tokyo, Japan, in
1980, 1982 and 1986, respectively. In
1985, he joined NTT (Nippon Telegraphand Telephone Corp.). Since 1992, he has
been an associate professor of Dept. ofElectrical Engineering, Nagaoka University of Technology. He is an associate editor of the IEICE Transactions on Communications. His research interests include
queueing theory, performance evaluation of networks, and geometric theory of statics. Dr. Nakagawa is a member of the IEEE,
SITA, and Mathematical Society of Japan.

Prasad Dhananjaya
received the
B.E., M.E. degrees in Electrical Engineering from Nagaoka University of Technology, Niigata, Japan, in 2000 and 2002, respectively. He joined Fujitsu Primesoftware Technologies Ltd in 2002. His research interests include the performance
evaluation of TCP/IP networks.

MIYAMURA et al.: A BUFFER MANAGEMENT MECHANISM

1441

Michihiro Aoki
received the B.E.
and M.E. degrees in electronics engineering from Chiba University, Chiba, Japan,
in 1981 and 1983, respectively. In 1983,
he joined the Electrical Communication
Laboratory, Nippon Telegraph and Telephone Public Corporation, where he has
been engaged in the research and development of high reliable and high performance switching systems and high performance IP router. He is currently a seniorresearch engineer of the NTT Network Service Systems Laboratories. He received the Asia Paciﬁc Conference on Communications Paper award in 2001. He is a member of the Information
Processing Society of Japan.

Naoaki Yamanaka
graduated from
Keio University, Japan where he received
B.E., M.E. and Ph.D. degrees in engineering in 1981, 1983 and 1991, respectively.
In 1983 he joined Nippon Telegraph andTelephone Corporation’s (NTT’s) Communication Switching Laboratories, Tokyo Japan, where he was engaged in research and development of a high-speed
switching system and high-speed switching technologies for Broadband ISDN services. Since 1994, he has been active in the development of
ATM base backbone network and system including Tb/s electrical/optical backbone switching as NTT’s Distinguished Technical Member. He is now researching future optical IP network,and optical MPLS router system. He is currently a senior research engineer, supervisor, and research group leader in Network Innovation Laboratories at NTT. He has published over
112 peer-reviewed journal and transaction articles, written 82
international conference papers, and been awarded 174 patents
including 17 international patents. Dr. Yamanaka received Bestof Conference Awards from the 40th, 44th, and 48th IEEE Electronic Components and Technology Conference in 1990, 1994 and1998, TELECOM System Technology Prize from the Telecommunications Advancement Foundation in 1994, IEEE CPMTTransactions Part B: Best Transactions Paper Award in 1996
and IEICE Transaction Paper award in 1999. Dr. Yamanaka isTechnical Editor of IEEE Communication Magazine, Broadband
Network Area Editor of IEEE Communication Surveys, Former
Editor of IEICE Transaction, TAC Chair of Asia Paciﬁc Board
at IEEE Communications Society as well as Board member ofIEEE CPMT Society. Dr. Yamanaka is an IEEE Fellow.