Performance and fluid simulations of a novel shared buffer management system.
We consider a switching system that has multiple ports that share a common buffer, in which there is a FIFO logical queue for each port. Each port may support a large number of flows or connections, which are approximately homogeneous in their statistical characteristics, with common QoS requirements in cell loss and maximum delay. Heterogeneity may exist across ports. Our first contribution is a buffer management scheme based on Buffer Admission Control, which is integrated with Connection Admission Control at the switch. At the same time, this scheme is fair, efficient, and robust in sharing the buffer resources across ports. Our scheme is based on the resource-sharing technique of Virtual Partitioning. Our second major contribution is to advance the practice of discrete-event fluid  simulations. Such simulations are approximations to cell-level simulations and offer orders of magnitude speed-up. A third contribution of the paper is the formulation and solution of a problem of optimal allocation of bandwidth and buffers to each port having specific delay bounds, in a lossless multiplexing framework. Finally, we report on extensive simulation results. The scheme is found to be effective, efficient, and robust.
Introduction
This paper considers a model of a switching node shown
in

Figure

1, which has multiple(N ) ports with bandwidths
that share a common buffer of size B. In the
shared buffer there is a FIFO logical queue implemented as
a linked-list for each port. Each port may support a large
number of flows or connections, which we envision to be
more or less homogeneous in their statistical characteris-
tics, with heterogeneity existing across ports. This view
is compatible with the QoS requirements, which is that
there is a common delay bound on all connections through
a port and that the bound on the probability of either violating
the delay bound or losing cells is specific to each port.
While shared buffer management has been of interest for
some time, see for instance [IRL78], [FGO83], [HBO93],
[CHA93], [GCG95], [WMA95], [CHA96], the approach
taken here is rather different. Our work shares objectives
with recent work on Virtual Queueing (see [SWR97] and
references therein), in which per-VC behavior is emulated
on a shared FIFO buffer. However, the algorithms are different
and further work is necessary to make the linkages
explicit.
This work has three main contributions. First, we propose
a shared buffer management scheme based on Buffer
Admission Control (BAC), which is integrated with Connection
Admission Control (CAC) at the switch and is
at the same time fair, efficient and robust in sharing the
buffer resource across multiple ports. Recent work on
CAC for single port systems [EMW95], [EMI97], [LZT97],
[LZI97], [RRR97] has used crucially the idea of trading
bandwidth and buffer to arrive at designs which allocate
specific amounts of bandwidth and buffer per connection.
If this approach is to be followed for multiport, shared
buffer systems, it is imperative that CAC and BAC work
in tandem. The dual objectives of satisfying QoS, which
requires protecting and isolating connections, and extracting
multiplexing gains from sharing the buffer resources,
need to be balanced in shared memory architectures. With
this in mind we base our scheme on Virtual Partitioning
[MZI96], [BMI97], [MZI97], which is a technique for
fair, efficient and robust resource
at each point in time, ports
that are using less than their nominal allocations, which
may be called "underloaded", are accorded higher priority;
conversely, ports that are exceeding their nominal alloca-
tions, which may be called "overloaded", are given lower
priority; finally, the priority mechanism is implemented by
a dynamic adaptation of the classical technique of trunk
reservation [AKI84], [KEY90], [REI91], wherein cells for a
port are admitted to the buffer only if the free capacity in
the buffer exceeds a reservation parameter, which is specific
to the port's loading status. The role of the reserved
capacity is to protect underloaded ports and the dynamic
reservation mechanism forces traffic to overloaded ports to
back-off in the event that underloaded ports need to claim
their allocated share. Note that the push-out mechanism is
not explicitly used in this scheme for ease of implementa-
tion, but it may easily be added. Also note that the state
information required to implement BAC for port i consists
of just the current queue for port i and the current total
buffer occupancy.
Traffic classes/ports are differentiated by QoS and also
by the degree of isolation or protection required [CSZ93].
This is realized by the nominal allocations and the reservation
parameters. For instance, a greedy "best effort"
class/port will have relatively large reservation parameters
working against it. Classical trunk reservation displays extraordinary
robustness properties and, also, optimal reservation
parameters scale slowly (eg. logarithmically or sub-
linearly) with the size of the problem [REI91], [MGH91].
We observe similar properties here. It suffices for the reserved
capacities to be small and there are broad ranges
of the reservation parameters that offer desirable perfor-
mance. The former is key to the efficiency and the latter
to the robustness of the scheme.
In a fluid simulation of our BAC the sample path of the
total buffer occupancy Q(t) exhibits persistence or "stick-
iness" at thresholds, which are determined by the nominal
allocations and reservation parameters. These thresholds
are points where the BAC is active and admits only fractional
amounts of fluid generated by affected ports. The
determination of these fractions is based here on a particular
notion of fairness, wherein all affected ports are treated
equally. Alternative notions of fairness may readily be sub-
stituted. These fractions, called "fairshare", are computed
at the onset of a sticky period during simulations by solving
an equation. We should point out that similar issues
arise in Fair Queueing, Generalized Processor Sharing and
Max-Min Fair ABR services, and the techniques for fluid
simulation developed here are expected to extend to these
applications.
The traffic source models considered in this work are adversarial
to the extent permitted by Dual Leaky Bucket
regulators, which are assumed to be typically present to
police the sources. In the case of lossless multiplexing, the
sources are permitted to collude so that in the worst case
the sources synchronize to burst at their peak rates at the
same time. In the contrasting, less conservative, statistical
multiplexing approach, the sources are assumed to be
non-collusive, so that their burst activity is asynchronous,
i.e., their phases are independent, uniformly distributed
random variables. In addition, we allow very small probabilities
to bound the possibility that QoS requirements in
delay and/or loss are not satisfied. Note that the design for
statistical multiplexing relies on the design for lossless mul-
tiplexing, so that the complete treatment is the composite
of phase 1 (lossless) and phase 2 (statistical).
This is the approach taken in [EMW95]. LoPresti et.
al. [LZT97], in an important recent paper, formulated a
general bandwidth-buffer trade-off problem in the lossless
multiplexing framework, in addition to treating the buffers
and bandwidth as two resources in the analysis of statistical
multiplexing, in contrast to a conservative device
in [EMW95] which allowed a reduction to a single-resource
problem. Our extension of the resource allocation problem
in lossless multiplexing to a shared buffer, multiport system
integrates the notion of the traffic class profile, an input
generated exogenously, possibly by market conditions,
and also delay bounds for each traffic class. The solution
to this general problem classifies bandwidth-buffer systems
in a new way and sheds light on the desired mix of these
resources to match traffic mixes. Le Boudec [LEB96] has
also considered a problem of optimal resource allocation to
inhomogeneous flows in the lossless framework in which the
optimization criterion is quite different from ours.
It has been shown in [MMO95] that in a single-resource
problem, the Chernoff estimate of the loss probability for
asynchronous, independent sources is maximized by source
rate waveforms which are on-off, periodic and extremal.
This result was used in [EMI97] to formalize the choice
of on-off waveforms as extremal in the bounding approach
followed in [EMW95]. More recently, Rajagopal, Reisslein
and Ross [RRR97], in an important work, have shown that
the extremal source rate processes for a two-resource formulation
of the statistical multiplexing problem are not on-
off. Since the numerical results in [LZT97] and [RRR97]
on system capacity with statistical multiplexing do not
show a marked increase over that obtained by the approach
in [EMW95] and [EMI97], which is based on a reduction to
a single resource and on-off waveforms, we adopt here the
latter, since it is substantially easier to implement.
Section 2 below gives the details of the system model and
Buffer Admission Control. Section 3 formulates and solves
a problem of optimally allocating buffers and bandwidth
to ports in a lossless multiplexing framework. Section 4
describes the issues in fluid simulation of the BAC. Section
5 describes the numerical results, which are all based on
statistical multiplexing. Concluding remarks are in Sec.6.
II. Description of System Model and Buffer
Management
A. System Model
The N-port system is shown in Figure 1. The term "con-
nection" is used interchangeably with "source". The shared
buffer capacity is B and we let
denote the aggregate
output bandwidth. Note that, while each port is
work-conserving, work-conservation does not apply to the
Source
Rate
Time
on
Fig. 2. Rate
aggregate output bandwidth. That is, unlike Generalized
Processor Sharing (GPS), it is possible for some ports to
be not fully utilized, while other ports are backlogged.
Each port has a logical or virtual FIFO queue, which is
implemented as a linked-list, with cell addresses in a data
RAM [EPA97]. Note that situations may arise where the
buffer is full, but there is no queue for one or more ports.
In this case, the incoming data for a port without a queue
may access the port directly and not be blocked. We let
denote the logical queue for port i at time t, and
denotes the total buffer occupancy at t.
We assume that there are K i connections for port i. A
tacit assumption made here is that the connections for any
port share common QoS requirements and are policed by
Dual Leaky Bucket regulators with similar, if not iden-
tical, specifications. In the analysis of the next section
it is assumed that the connections for port i are homogeneous
with Dual Leaky Bucket regulators specified by
In the succeeding section on fluid simulations
we allow the additional generality of heterogeneous
traffic classes for each port. The QoS requirement on the
probability of loss for connections going through port i is
and the delay bound is D i .
In the Dual Leaky Bucket regulator with specifications
is the mean sustainable rate or the token rate,
B T is the burst tolerance or the token buffer size, and P
is the peak rate. The connection traffic rate which is regulated
by such a device is assumed to be on-off, periodic and
extremal in the sense that when the source is on its rate is
the maximum permitted rate, P . The amount of data \Theta
generated in an on period is also maximum, and is given
by
with the mean rate in each period being r. This extremal
rate process, denoted by \Omega\Gamma t), is shown in Figure 2, where
B. Description of the Buffer Admission Control
We let B i denote the "nominal allocation" of buffer
capacity to port i. Assume that B i is calculated by
some technique appropriate for single port systems, such
as [EMW95], [LZT97] or [RRR97], which takes into account
. Thus, the process of nominal buffer
allocation and CAC are intimately coupled. Typically,
the extent of buffer over-allocation
is a subject of design influenced by issues such as multiplexing
gain across ports, the degree of isolation desired000000000000000000000000000000000000000000000000000000000000000000000000111111111111111111111111111111111111111111111111111111111111111111111111000000000000000000000000000000000000000000000000000000000000000000000000111111111111111111111111111111111111111111111111111111111111111111111111
traffic
admission
block
admission
traffic
block
admit admit
R
R u N
BN
to port N
to port 1
port 1 traffic port N traffic
Fig. 3. Illustration of the Buffer Admission Control for an N-port
system where ports 1 and N are carrying "guaranteed service"
and "best effort" traffic, respectively.
for ports from other ports which are misbehaving due to,
say, the breakdown of policing regulators, and the presence
of "best effort" traffic through some ports. Some of these
issues are probed in Section 5 on numerical investigations.
We define the "status" of a port i as overloaded if
underloaded if Q . For each port
i we define the pair of "reservation parameters" (R u
with the superscripts u and denoting "underloaded" and
"overloaded", respectively. These parameters are chosen so
that R u
i for all i. Typically, R u
as we shall see,
and the main reason for having R u
is to give traffic
for such a port lower priority in accessing the buffer. Our
Buffer Admission Control (BAC) algorithm is as follows:
Admit traffic for port i into the buffer if and only if one of
the following conditions is satisfied
fflPort i is underloaded, i.e.
fflPort i is overloaded, i.e. Q
From the fluid flow point of view, the BAC is not complete
until the policy at the global thresholds
for each s and i, is specified. This is an important aspect
of the BAC. The principle we adopt, which is based
on a particular notion of fairness, admits fluid to affected
ports at rates which correspond to equal fractions of the
rate of total fluid generated by the sources for each port.
This principle may readily be substituted by another such
as admitting fractions proportional to prespecified weights,
or, as in the cell-level control scheme of [RWM95], treating
the admitted fractions as control variables to meet QoS
requirements.
We illustrate the application of the BAC in a scenario
where port 1 is carrying "guaranteed service" traffic, while
port N is carrying "best effort" traffic. The tacit assumption
is that the traffic through port 1 is tightly regulated
and admission-controlled, while the traffic through port N
is loosely regulated, perhaps only its peak rate is policed,
and the QoS constraints for CAC are slack. Hence the flow
for port 1 is given priority in accessing the buffer over port
N . One level of control in buffer management is reflected
in the selection of the nominal allocations B 1 and BN . Yet
another level of control is exercised through reservation pa-
rameters. We set
N . Figure
3 illustrates the BAC for the two ports. Consider an instant
in time when port N is overloaded, while port 1 is underloaded
4and its sources have just become active.Besides
the reserved buffer capacity being made available to port
1, the other mechanism working in its favor is that every
departing cell of port N is systematically replaced by an
arriving cell for port 1.
III. Bandwidth and Buffer Allocations: The
Design Problem
In the first phase, the design problem is considered in the
lossless multiplexing framework, and in the second phase
with statistical multiplexing. The antecedents of this work
are [EMW95], [LZT97] and [EMI97]. The lossless multiplexing
problem is as follows. We are given (see Figure 1)
and C, the shared buffer capacity and aggregate output
bandwidth, respectively. The connections for port i are
subject to Dual Leaky Bucket regulation with parameters
furthermore, the sources are on-off periodic
and extremal (see Figure 2). We are also given the
traffic class profile j
represents the relative mix of connections of the various
traffic classes at the desired operating point. That is, the
desired operating point is Kj. The
scalar K is hence a proxy for the capacity of the system for
the specified traffic mix. The QoS requirements are zero
loss and delay bound D i for class/port i. The problem
is to obtain the buffer-bandwidth allocations (B
port such that the capacity K is maximized
subject to the resource constraints
It will be shown shortly that the above problem is equivalent
to the following.
Lossless Multiplexing Design Problem (B; C; j; D)
subject to
where
The burst size and time, \Theta i and T on;i , are given in (1)
and (2). The solution to this problem is given in the following
subsection.
A. Lossless Multiplexing
We begin by briefly reviewing the notion of a "virtual
buffer/trunk system" for a single source [EMW95]. Consider
a single source of class i with periodic, on-off rate pro-
cess\Omega\Gamma which supplies an initially empty, infinite buffer
with an output port of bandwidth c i , where c i ? r i for
stability. Let b i denote the maximum buffer content over
time. Then it is easy to see that
F
Fig. 4. Two cases for class i in the min-max design problem.
When K i sources of class i are connected to port i, the
constraint implied by lossless multiplexing is
where
The constraint implied by the bound on the maximum delay
is
Thus we obtain the design problem stated in (4)-(7).
Next we systematically normalize with respect to B, C
and K. Let
The resource constraints in (5) translate to
Also,
where
Note that fq i g, ft i g and fd i g are dimensionless parameters.
Hence the design problem is equivalent to the following
where
subject to
To analyze the problem it will help to first consider two
cases for each class: d i - 1 and d i ? 1. For reasons
which will become clear shortly, the former may be called
"bandwidth constrained" and the latter "balanced" (see

Figure

4). In case (i) the delay requirement necessitates
a disproportionate amount of bandwidth to be expended.
Clearly, the point E i is locally the most attractive allocation
point. For case (ii), the delay requirement is not so
stringent, which makes the balanced allocation point A i locally
the most attractive. However, as we shall see, global
considerations will lead to allocations different from the
local optima.
For the min-max problem (16)-(18), a little thought
shows that, for each class/port i, the globally optimum
allocation lie on the segment shown in

Figure

4. Hence, the constraint (18) may be replaced by
the following: for
using (19), we may eliminate from the problem
to obtain the following version:
where
ae P
subject to
The two cases in (22) correspond to whether the limiting
resource is bandwidth or buffer, respectively. Note too that
a feasible solution always exists.
There are now two cases to consider depending upon the
location of the corner point fq i with respect to
the separating hyperplane in fl-space, which is in (22). In
the first, simpler, case
This may be referred to as the "globally bandwidth-
constrained" case in analogy to the previously discussed
classification for the single class. Certainly this case holds
if each class is bandwidth constrained, i.e., d i - 1 for all i.
If (24) holds then it is easy to see that the solution to the
min-max problem is
Now consider the alternative to (24), namely E ? 0,
which may be termed the "globally balanced" case. In this
case, it may be deduced that the solution to the min-max
problem as stated in (21)-(23) must lie on the separating
hyperplane where the buffer and bandwidth are simultaneously
exhausted., i.e.,
It then follows that the min-max problem reduces to
min
subject to (26), and the inequality constraints (23); also
This problem is an LP with a simple solution, which is
also exploited in [LZT97]. The solution is incorporated in
the summary given below to the design problem (4)-(7),
which is stated in terms of the original variables.
Proposition 1: Let
(i) In the "globally bandwidth-constrained" case, E - 0.
In this case the maximum capacity is
which is obtained for the following buffer and bandwidth
allocations.
and
where
(ii) In the "globally balanced" case, E ? 0. Let the classes
be indexed in decreasing order of their on periods, i.e.,
and let k be the smallest integer such that
The capacity K is then maximized by the following allocations

K[ EB
Ton;j +B=C
Ton;k+B=C
Ton;j
jk \Theta k
Ton;k+Dk
The maximum capacity K is obtained from the relation
C. The buffer allocations are obtained from the
relation
which satisfies
The differences between the two cases in the above result
are noteworthy. In the globally bandwidth-constrained
case the sum of the allocated bandwidths equals the given
aggregate bandwidth, but that is not the case with the
buffers. In contrast, in the globally balanced case, both
buffers and bandwidth are totally consumed by the allocations

This dichotomy has broad implications, which we briefly
touch upon now. Suppose that in the former case,
class/port N is "best effort" with generous delay require-
ments, say DN - B=C. Clearly, by giving greater weight
to the best effort class in the traffic-class profile j, i.e., by
increasing jN , perhaps induced by tariffs, the quantity E
in (28) can be made to change from negative to positive,
which would make the system globally balanced, resulting
in full utilization of both resources with proper allocations.
B. Statistical Multiplexing
The objective here is to take the buffer-bandwidth allocation
and maximize the number
of connections K i by exploiting statistical multiplexing,
such that the loss probability In particular, as
mentioned in Section 1, here we do not consider the sharing
of buffer resources across ports as governed by the BAC.
The technique given below for computing the loss probability
for any given K i is based on the Chernoff asymptotic
approximation technique and is due to [EMW95].
A key observation is that the allocation (B based
on the behavior of the "virtual buffer/trunk system" for
a single source, where the peak buffer utilization is b i and
the peak bandwidth utilization is c i , with (see 10),
This relation is key to the reduction to a single-resource,
which we may now take to the bandwidth. The bandwidth
utilization by a single connection k is denoted by u ik . On
account of the assumption that the sources have phases
which are independent and uniformly distributed over the
period
. The loss probability for port i is
where the bandwidth load on port i is U
k=1 u ik .
Since the distribution of the random variables is bino-
mial, it is straightforward to obtain the following Chernoff
asymptotic approximation to P loss;i .
Proposition 2:
where
a
log
- a i
a i log a i
and
The capacity K max;i is the value of K i for which
IV. Fluid Simulations
In this section, we investigate the technical issues in a
fluid simulation of the proposed Buffer Admission Control
scheme. For the simulation, we also allow the additional
generality of possibly several classes of connections through
each port, with each class having a corresponding Dual
regulator. Note that the fluid flow representation
is an approximation to cell-level behavior in which
cell-level details in the behavior of sources, trunks and
buffers are smoothed into a steady rate of fluid flow from
the sources causing piecewise linear changes in buffer oc-
cupancy. Events such as admission/removal of connections
and starts/ends of bursts in connections are key events in
fluid simulations, which coincide with jumps in the fluid
rates. In addition to these source related events, there are
buffer and control related events. For example, when the
buffer becomes empty or full, the rate of flow out of the
buffer undergoes a discontinuous change. In a high speed
system such as ATM, the advantage of fluid simulation accrues
from the fact that these "events" occur on a much
slower time-scale as compared to cell arrivals and depar-
tures, thereby requiring much less simulation time to cover
a given amount of actual system time. Obviously, fluid
simulations must be event-driven in order to realize this
advantage.
In event-driven simulations, the event set in the system
determines the logical complexity; the larger the event set,
the more complex the simulation, since it is necessary to
determine the earliest next event from among a larger number
of possibilities.
In the simulations described here, the source model for
traffic of an individual connection of class j going into port
i consists of on-off, periodic rate waveforms, which are extremal
with respect to the Dual Leaky Bucket regulator
for the class (see Figure 2) and have phases that are independent
random variables uniformly distributed over the
period of the waveform. The rate process of the aggregate
traffic offered to port i is the superposition of the rate
processes of all connections through the port.
An important feature of the fluid simulations described
here, which is a reflection of the BAC, is that the logical
queues fQ i g for the ports are computed and monitored, of
course, but not the queues for the individual connections.
The set of events relevant to our fluid simulation is of
two types - (i) Source events and (ii) Buffer events. Buffer
events, which are threshold crossings, can further be subdivided
into (i) port-specific and (ii) global. We now proceed
to enumerate and describe these events.
Type 1: Source state changes The state changes are
discrete events corresponding to the discontinuities of the
piece-wise constant, aggregate rate process for each port.
ffl Type 2: Port threshold crossings When the logical
queue for any port empties or the port uses up its nominal
allocation, i.e., Q some of the incoming fluid
is treated differently by the control scheme. Hence the rate
of change of the port buffer occupancy, dQ i =dt, encounters
a discontinuity, as a result of which
discontinuous as well. We postpone the detailed discussion
of this event, except to note that the change in port status
caused by this event causes changes in the admitted fluid
rates for all classes feeding into the port.
ffl Type 3: Global threshold crossings These events
are characterized by
ij for some class j and status indicator s. When
one of these thresholds is encountered, there is a jump in
dQ=dt, since when R
ij , traffic of class j is not admitted
into the buffer, and immediately after
0 or B. We later discuss in detail the behavior of the system
following this event.
Event types 2 and 3 correspond to instants when the
BAC is active. There is a "stickiness" associated with these
thresholds, i.e., the thresholds behave like attractors, holding
the queue fixed until the next source state change. A
similar feature is shown to exist and analyzed in the loss
priority control scheme of [EMI94]. The stickiness is a result
of our control policy at the thresholds, which requires
admitting only a fraction of the fluid belonging to the affected
classes. The exact composition of admitted fluid of
the various classes can be controlled in different ways depending
on QoS considerations. Here, motivated by fair-
ness, equal fractions of each of these flows are admitted.
A. Characterization and Analysis of Events
We now proceed to describe how the aforementioned
events are processed in the simulation. Each of the above
events triggers computations that determine acceptance,
buffer usage and loss rates for each port and source class
till the next event occurs. The scheduling of future events
is also dependent on these computations. The set of ports
are grouped into subsets based on status.
ports with zero occupancy.
denotes underloaded
ports with nonzero occupancy.
denotes "border" ports, i.e. these
ports are at their overload thresholds.
denotes strictly overloaded ports.
A.1 Single Threshold System
For the benefit of the reader, we first consider the simple
case where the reservation parameters are common to all
ports, i.e., R u
Thus, there is
only one global threshold B \Gamma R in the buffer occupancy.
However, even in this case, inhomogeneity exists on account
of the diverse character and number of connections through
the ports and in the QoS specifications. This diversity is
reflected in the possibly different nominal allocations B i
for different ports.
be the piece-wise constant rate of fluid generated
for port i. We then have the following cases:
1. active in this case and all
fluid going into the system is accepted, i.e.,
dt
dt
2. In this case, the BAC blocks flows to
overloaded ports. However, ports at the border between
overload and underload, i.e., those with Q must
be treated carefully in the fluid system. To start with, we
avoid this complication and assume that there are no such
border ports with Q at instant t. We then define
the following rate function f(fi) in terms of the fraction
admitted fluid from overloaded ports.
i2O
Note that f(fi) monotonically increases with fi. We then
have the following cases:
(a) 0: In this case, the underloaded ports by themselves
cause a net increase in buffer occupancy and hence
no fluid from overloaded ports is admitted, i.e.,
(b) f(1) - 0: All fluid coming into the system is admitted
and no control is exercised, i.e.,
(c) In this case, the operating value of
and we have
the net occupancy exhibits stickiness at
Now consider the case in which the queue for one of the
ports is at nominal occupancy, say Q
going into this port is admitted if the port subsequently becomes
underloaded, which is the case if - i
ternatively, if the "fairshare" (fi- i causes the port
to stay overloaded, only the fairshare is admitted. If neither
of these conditions is true, the occupancy of this port
stays unchanged at Q i This port-level stickiness
is induced by the notion of port status, which undergoes
a discontinuous change when the condition Q
crossed. Thus, the contribution of this port to the net drift
is given by
dt
0). For this case, the modified rate
function is
i2O
This rate function is used instead of (40) to determine fi
and the net rate of change of the buffer occupancy, dQ=dt.
In this case, no fluid from ports with
is admitted. However, a fraction of fluid from
ports with Q admitted so as to keep dQ i =dt - 0.
Thus, we have
dt
4. When the entire buffer is occupied, the uniform
fraction fi of fluid going into underloaded and border
ports that is admitted is such that the net drift is non-
positive. We define the rate function
which clearly satisfies We have the cases
(a) f(1) - 0: All fluid from underloaded ports and border
ports is admitted, i.e.
0: The admitted fraction fi satisfies
and the net occupancy sticks at till the next event.
A.2 General Case
We now extend the above analysis of events to the general
case where the reservation parameters are arbitrary
and there are a number of classes of connections indexed
by through each port. Let - ij (t) denote the
piece-wise constant rate of fluid of class j offered to port i
at time t. Then, the total rate of fluid generated for port i
at time t is given by
The strictly admissible, or "legal", component of this rate
is given by
l
where the superscript s in R s
ij denotes "status" of port i
at time t.
Type 1 Events are most simply processed since they
merely involve changing the values of the legal fluid rates.
Assume that, at time t, the total occupancy is not at a
global threshold, i.e., Q(t) R where R is any one of
the reservation parameters R s
ij , and the port occupancies
are not at their nominal values, i.e. Q
the rates of change for these quantities at this instant are
expressed simply as
dt
dt
(S l
(S l
i2O
(S l
where I(:) is an indicator function, which is 1 if the argument
is true and 0 otherwise. Note that since we
have assumed that no port queue is at its nominal value.
We will later modify equations (46) to include terms for
these ports, but with this assumption, (46) determines the
evolution of port occupancies till an event of type 2 or type
3 occurs, i.e. one of the thresholds is encountered.
Type 2 Events occur when one or more port queues
are at nominal allocations fB i g. In this case, the set B is
non-empty and we need to include these ports in the rate
calculations. We assume initially that the total occupancy
Q(t) is not at a global threshold. For ports in B, we define
the following aggregate rate from "border" 1 flows,
The "legal" flow rates for these ports is computed using
(45) and the o superscript on the reservation parameters.
We then have the following cases
1. S l
. In this case, dQ i
positive
and none of the border fluid is admitted, since the port
becomes strictly overloaded after this instant.
2. S l
. In this case, dQ i
strictly negative and all the border fluid is
admitted, since the port becomes underloaded after this
instant.
3. S l
(t). This case demonstrates
"stickiness" at the port level. The fluid system has
while the cell behavior experiences fluctuations
about with a long-term adherence to this condi-
tion. In this case, the contention is between the various
classes of fluid going into port i. Following our notion of
fairness, we propose that a fraction ff i of the border fluid of
each border class be admitted. This fraction is determined
by the equation
dt
which gives
These cases can be combined into the following pair of
equations that determine dQ i =dt and ff i for ports in B
We would like to distinguish this "port-level border" by superscript
bp, from other "globally border" flows to be defined later on.
dt
l
With this information, the system evolution is determined,
until the next event, by the equation
dt
dt
(S l
(S l
[(S l
i2O
(S l
Type 3 Events are the most computationally involved
and also have the most impact in the control scheme. For
simplicity, we begin with the case
that, at instant t,
j is one of
the reservation parameters. Then, for each port, we define
the "globally border" flow rate S bg
i as
where, as before, superscript s represents port status(u or
o). The possibilities for system evolution are then as follows
1. dQ=dt This is possible if and only if the legal flows
by themselves cause the total occupancy to increase, since
i would be strictly disallowed after t. Thus we require
dt
(1)
(S l
(S l
i2O
(S l
2. This condition occurs when admitting the
legal and the border flows still causes the total occupancy
to decrease. This implies
dt
(2)
(S l
(S l
i2O
(S l
3. case occurs when dQ=dt (1) - 0 and
dQ=dt (2) - 0. Then, as before, we admit a fraction fi
of the border fluid that would keep the total occupancy
unchanged. This fraction is determined by the equation
dt
where
(S l
(S l
i2O
(S l
The form of equation (53) is generic to the computation
of "fairshare" in various contexts, such as Fair Queueing,
Generalized Processor Sharing and Max-Min Fairness. A
solution procedure is described in the Appendix.
When B 6= ;, we must make further distinctions between
the flows into ports with events. We
divide these flows into the following four classes,
l
The rate equations must now include these ports. Admitting
a fraction fi of border fluid results in the following rate
changes.
dt
(S l
(S l
(S l
(S l
dt
dt
The possibilities are as follows.
1. only legal flows
are admitted.
2.
unrestricted access.
3. The fraction fi
of border flows admitted is determined
equation is solved using the procedure outlined in the Appendix

V. Numerical Investigation
In this section we present simulation results of case studies
on the efficacy of the BAC and the influence of the
scheme's parameters on system performance. All cases
studied involve statistical multiplexing. In fact, as we shall
see, in some cases the number of connections considered are
significantly more than can be supported if there was no
buffer sharing among ports. Also, the cell loss ratios (CLR)
given in the results are the ratios of lost cells to cells offered
to the buffer. We have also computed the fraction of time
during which the losses occur but these are not reported.
Finally, we consider two classes of connections with rather
different characteristics. All results reported are in dupli-
cate, one set for each class. The results are grouped in
five subsections, with Sec. 5.1 giving background data and
benchmarks for the whole section.
A. Background Data and Benchmarks
In this study the standard sources or connections
are either of class 1 or 2 with the specifications given
in

Table

I. These classes have been studied earlier
in [EMW95], [LZT97] and [RRR97]. Note that non-
regulated sources, "rogue" and "best-effort" are also considered
in the study. Table II contains basic data on
Class r(Mbps) P(Mbps) \Theta(cells) Ton(ms) T(ms)


I
Dual Leaky Bucket parameters.
statistical multiplexing gain in capacity that may be expected
from sharing the buffer. Single port and 4-port systems
are considered. In all cases the CLR is in the range
which was a choice made to keep the
burden on the simulations acceptable.
The buffer management for the multiport system of Table
II is Complete Sharing, which is the case of Virtual
Partitioning is all reservation parameters are null. Thus,
in the multiport system, no consideration is given to selective
isolation and protection for purposes of QoS, and hence
the multiplexing gain reported is optimistic. In Table II,
Class Single port system 4-port system Sharing gain


II
Buffer requirements in single and multi-port systems with
Complete Sharing. speed=15Mbps.
Kmax is the maximum admissible number of connections
in the single port system for given L,
15Mbps. Thus, Kmax takes into account statistical
multiplexing across connections through each port.
In the following experiments, we take the multiplexing
advantage between ports into account only when all connections
in the system belong to the guaranteed service
category. We do not assume any multiplexing advantage
between ports when the buffer is shared with "best effort"
or greedy "rogue" connections.
B. BAC Performance under Homogeneous Loading
Here we provide basic performance data for our BAC.
The case considered has four ports
numbers of connections through each port (see Figure 5.
The reservation parameters are common to all ports:
R u
and the parameter R is varied. In Figures 5(a) and 6(a),
there are K connections and in Figures 5(b)
and 6(b), there are K connections through
each port.
The figure plots unconditional and conditional CLR. Of
great importance is the "CLR conditional on port under-
load" for each port, which is the ratio of cells lost to cells
offered during periods when the port is underloaded. This
quantity, above all, should be small if the BAC is working
effectively in conjunction with CAC.

Figures

5 and 6 show the effect of the reservation parameters
on the conditional and unconditional CLR values for
two different nominal buffer allocations B i . In Figure 5,
are set aggressively at 333 cells per port, while in Figure
6, the B i are set conservatively so that
For class 1 connections, which have a high value of P=r of
40, the reservation mechanism helps to substantially reduce
the CLR conditional on underload only for the conservative
setting of fB i g, while for class 2 connections with a
more benign P=r of 10, reservation is uniformly effective in
restricting underloaded CLR. In both cases, the CLR conditional
on underload is uniformly lower than the unconditional
CLR. The reservation effectively trades off over-loaded
CLR for underloaded CLR, while the unconditional
CLR increases very slowly with R. Thus, at the cost of
a small amount of throughput, the reservation mechanism
in the BAC enforces compliance to resource allocations in
CAC, even while allowing effective sharing of buffers across
ports.
C. Inhomogeneity among
The objective here is to investigate the capabilities of
the reservation mechanism to support diverse QoS to the
individual ports (see Figure 7), where the single variable
R controls the reservation parameters of each of the four
ports:
R u
The nominal allocations to the ports are set conservatively
at
For

Figure

7 the number of connections through ports,
in each case, have been selected such that, if the ports
were isolated with buffer allocations matching the nominal
allocations, the QoS experienced by the ports would be
substantially different
that, in Figure 7(a) at the intended difference in
CLR is completely diluted and the CLR experienced by the
ports is roughly similar, while Figure 7(b) shows a similar
dilution to a lesser extent. The main observation on this
experiment is that a small value of R (eg.
introduces a wide separation in QoS, again at the cost of
a small amount of throughput. To minimize this slowly
varying difference in throughput, the design should select
the smallest value of R that satisfies the CLR of all the
ports. This selection is usually determined by the most
stringent CLR requirement.
D. Effect of "Best-Effort" Traffic
Here we consider the case where one of the ports, port 4,
in a 4-port system is dedicated to carrying traffic not regulated
by Dual Leaky Buckets. The traffic through port-4,
called "best-effort", has been designed to be detrimental to
the other ports carrying regulated traffic, from the multiplexing
point of view. We assume that the aggregate source
traffic for port 4 is offered to the buffer at a constant rate,
which is slightly in excess of the bandwidth of the port,
if the queue
is initially empty. Indeed, a good implementation of the
"best-effort" service would restrict the peak rate not to exceed
the port speed. Here, however, our objective is to test
the BAC under the presence of such a greedy source that
takes up all of the buffer space permitted to it. We chose
Fig. 8(a) (59)
Fig. 8(b) (60)
The reservation here is applied only against the best effort
port, i.e., R u
while for the other ports R u
The results in Figure 8 show that the scheme hence provides
substantial protection and isolation for the regulated
sources, while carrying substantial "best effort" traffic.
E. Effect of Misbehaving Connection
In

Figure

9, we show the effect of a "rogue" connection
through port 4 in a 4-port system. Under ideal conditions,
the system is as described in Section 5.2 with the same
reservation parameters and nominal allocations. However,
we do not expect any multiplexing advantage across ports
in such a scenario, and we set cells.
The BAC here is only intended to protect the well-behaved
ports 1-3.
Our model of the misbehaving guaranteed service connection
is that of a connection with a defective Dual
Bucket regulator that fails to regulate the mean
rate. Hence, the connection pumps in fluid into the system
steadily at it's peak rate. This case differs from the best-effort
case of Section 5.4 in that the reservation is applied
uniformly to all ports, and also the port with the misbehaving
connection has other well-behaved connections through
it. Thus, while the reservation restricts well-behaved ports
as well, the rogue port is not always backlogged on account
of the multiplexing in bandwidth between connections
port 4.
The results in Figure 9 once again reveal the benefits of
the reservation mechanism. The ports carrying regulated
traffic are effectively protected from the effects of the rogue
connection. The difference between cases (a) and (b) is due
in part to the fact that in the former the peak rate of one
source is a significant fraction (6/15) of the port speed.
VI. Conclusions
This paper has proposed and evaluated a shared buffer
management scheme in which the Buffer Admission Control
is coupled to the Connection Admission Control. Also,
(a).1e-050.0010.1
CLR
CLR Conditional on Port Underload
CLR Conditional on Port Overload
CLR
(b).
CLR
CLR Conditional on Port Underload
CLR Conditional on Port Overload
CLR
Fig. 5. Effect of reservation parameter on unconditional and conditional
cell loss ratios in 4-port system. See Sec. 5.2. (a) K
class 1 connections in each port,
connections in each port,
a problem of optimal allocation of buffers and bandwidth
to ports in a shared memory, multiport system has been
formulated and solved in a lossless multiplexing framework.
The scheme is found to be efficient and robust.
Extensions to the work include, first, an analytical technique
to evaluate the benefits of statistically multiplexing
the buffer resource across ports and second, the development
of fluid simulation techniques for the Generalized Processor
Sharing discipline in a multiport system.



--R

The Overload Performance of Engineered networks with Non-Hierarchical and Hierarchical Rout- ing
Virtual Partitioning for Resource Sharing by State-Dependent Priorities: Analysis
Space Priority Management in a Shared Memory ATM Switch.
Dynamic Queue Length Thresholds in a Shared Memory ATM Switch.


Traffic Shaping at a Network Node: Theory
A New Approach for Allocating Buffers and Bandwidth to Heterogenous
Advances in Shared-Memory Designs for Gigabit ATM Switching
Sharing Memory Opti- mally
Optimal Buffer Sharing.
Simulation of a Simple Loss/Delay Priority Scheme for Shared Memory ATM Fabrics.
Buffer Management in a Packet Switch.
Optimal Control and Trunk Reservation in Loss Networks.
Network Calculus Made Easy.
A CAC Algorithm for VBR Connections over a VBR Trunk.
Source Time Scale Optimal Buffer/BandwidthTrade-off for Regulated Traffic in an ATM Node
Analysis and Optimal Design of Aggregated-Least-Busy-Alternative Routing in Symmetrical Lossless Networks with Trunk Reservations
Multiple Time Scale Regulation and Worst Case Processes for ATM Network Con- trol
Virtual Partitioning by Dynamic Priorities: Fair and Efficient Resource Sharing by Several Services.
Hierarchical Virtual Partitioning: Algorithms for Virtual Private Networking.
Optimal Trunk Reservation for a Critically Loaded Link.
Packet Multiplexers with Adversarial Regulated Traffic.
Dynamic Call Admission Control of an ATM Multiplexer with On/Off Sources.
Virtual Queueing Techniques for UBR
A Buffer Allocation Scheme for ATM Networks: Complete Sharing Based on Virtual Partition.
--TR
Supporting real-time applications in an Integrated Services Packet Network
A buffer allocation scheme for ATM networks
Virtual Partitioning by Dynamic Priorities
Traffic Shaping at a Network Node
Source Time Scale and Optimal Buffer/Bandwidth Trade-off for Regulated Traffic in an ATM Node

--CTR
David M. Nicol , Guanhua Yan, Discrete event fluid modeling of background TCP traffic, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.14 n.3, p.211-250, July 2004
buffer management;fluid simulations;virtual partitioning