Internet Engineering Task Force Integrated Services WG
INTERNET-DRAFT S. Jamin/L. Breslau
draft-ietf-intserv-control-flow-00.txt UMich/Xerox
April 18, 1997
Expires: 10/18/97
A Measurement Based Admission Control Algorithm for
Controlled-Load Service
Status of this Memo
This document is an Internet-Draft. Internet-Drafts are working
documents of the Internet Engineering Task Force (IETF), its areas,
and its working groups. Note that other groups may also distribute
working documents as Internet-Drafts.
Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress."
To learn the current status of any Internet-Draft, please check the
"1id-abstracts.txt" listing contained in the Internet-Drafts Shadow
Directories on ftp.is.co.za (Africa), nic.nordu.net (Europe),
munnari.oz.au (Pacific Rim), ds.internic.net (US East Coast), or
ftp.isi.edu (US West Coast).
Abstract
Controlled-Load Service provides data flows with an enhanced quality
of service, in the form of low packet delay and a low probability of
packet loss even under congestion. A network element providing
Controlled-Load Service must use an admission control algorithm to
limit the number of data flows receiving the service. In this
document we describe an admission control algorithm for Controlled-
Load Service. This algorithm is not intended for IETF
standardization. Rather, it is presented for informational purposes
only.
Jamin/Breslau Expires 10/18/97 [Page 1]
INTERNET-DRAFT draft-ietf-intserv-control-flow-00.txt April 18, 1997
Introduction
Controlled-Load Service (CL), as defined in [Wro95], is an enhanced
quality of service intended to support applications requiring
performance better than that which would be provided by traditional
best-effort service. Even under congestion, network elements
offering CL are expected to provide flows with low delay and low
packet loss.
In order to provide this enhanced level of service, network elements
must limit the number of flows receiving the service. This is
accomplished by requiring applications to make explicit requests for
service. Explicit requests for service can be made using a
reservation setup protocol, such as RSVP [B+96], or some other means.
Each network element that receives a request for service can either
accept or reject the request. We refer to this decision as
"admission control".
An application requesting CL presents the network element with a
traffic descriptor to describe its data flow. This descriptor
includes a token bucket filter and a peak rate. The token bucket
parameters, a rate and bucket depth, represent a loose upper bound on
the new data flow. A measurement based admission control (MBAC)
admits or rejects a new flow based on measurements of existing
traffic and the parameterized description of the new flow. The
dependence of MBACs on traffic measurements makes the quality of the
service they provide subject to statistical fluctuation of traffic.
We expect MBACs to work well only when there is a high degree of
statistical multiplexing of uncorrelated flows and traffic
fluctuation is not dominated by a small number of flows. In this
document, we describe one such MBAC designed for CL.
Admission control is not an area appropriate for IETF
standardization. Rather, vendors and service providers are free to
implement and deploy any admission control algorithm that enables a
network element to meet the service requirements of the Controlled-
Load specification. Indeed, admission control can be seen as an area
for product differentiation. Hence, the algorithm described here is
presented for informational purposes only, providing a single example
of an MBAC that may be used as a reference algorithm.
Various MBACs suitable for use with CL have been proposed in the
academic literature. See, for example, algorithms described in
[Flo96, JSD97, GK97]. The algorithm described here was first
proposed in [JS97] and was shown to perform as well as several other
MBACs. This algorithm is designed to be very simple to implement.
We believe that it meets the requirements given in the CL
Jamin/Breslau Expires 10/18/97 [Page 2]
INTERNET-DRAFT draft-ietf-intserv-control-flow-00.txt April 18, 1997
specification, performs as well as other known algorithms, and
provides sufficient configuration parameters to allow it to be
deployed in a variety of settings. We refer the interested readers
to the above references both for further details on the other MBACs
and for more background on the proposed MBAC.
The remainder of this document is organized as follows. In the next
section we describe the admission control algorithm. Next, we
describe one measurement process that may be used to provide load
estimates that are used as inputs to the admission control algorithm.
Finally, we discuss the different tuning parameters that allow the
algorithm to be used in various settings.
The Admission Control Algorithm
Our admission control algorithm takes as input L, a load estimate
produced by the measurement process (described in the next section),
C, the link bandwidth, upsilon, a user defined aggregate loading
factor, kappa, a user defined new flow effect factor, and r, the
token bucket rate of the new flow requesting admission. Whenever a
new flow requests admittance under CL, the flow is admitted if the
following inequality is satisfied:
L < upsilon * C - kappa * r
Otherwise the flow is rejected.
The Measurement Process
The purpose of the measurement process is to compute an estimate of
the network load attributed to data packets receiving Controlled-Load
Service. This estimate, which we refer to as L is used as input to
the admission control algorithm. We describe a time window
measurement process here. An alternative measurement process using
exponential averaging may be used instead [Flo96].
The time window measurement process uses 2 parameters, T and S. T is
the measurement window and S is the sampling period, with S <= T.
During every sampling period, S, an average load is computed. This
average load is simply the sum of bytes in packets receiving CL
divided by the length of the sampling period. We note that computing
average load for a given sampling period is basic to most measurement
processes advocated for use with MBAC.
Jamin/Breslau Expires 10/18/97 [Page 3]
INTERNET-DRAFT draft-ietf-intserv-control-flow-00.txt April 18, 1997
The only per-packet action required by the measurement process is to
accummulate the byte-count of packets receiving CL service. All
other processing occurs with low frequency. For performance
enhancement, a router vendor may wish to implement the per-packet
byte counting in hardware. At each operator-defined sampling period
S, a software process reads and clears the hardware accummulator.
The software process also performs the other low frequency processing
to compute the load estimate.
The load estimate, L, is updated as follows:
1. At the end of every measurement window, T, L is set to the
highest average load computed for any S during the previous window.
2. If a newly computed average load for a given sampling period S is
larger than the current value of L, L is set to the newly computed
average.
3. Whenever a new flow is admitted, the measurement estimate is
immediately increased by r, the token bucket rate of the newly
admitted flow.
The Parameters
In this section we discuss how each of the parameters can be adjusted
to control the behavior of the algorithm. The specific settings that
are appropriate in any deployment environment depend on the
characteristics of that environment (i.e., the traffic
characteristics and link bandwidth), on how much Controlled-Load
traffic a network operator wants to admit on a link, and on the level
of risk the network operator is willing to take that the service
requirements are occasionally violated.
T -- Measurement Window
Increasing T increases the amount of history remembered by the
measurement process. The values of T will be some integral multiple
of the value of S.
S -- Sampling Period
For a fixed T, decreasing S makes this measurement process more
sensitive to bursts of data. Appropriate values of S are likely to
be on the order of thousands of packet transmission times.
upsilon -- Aggregate Loading Factor
Jamin/Breslau Expires 10/18/97 [Page 4]
INTERNET-DRAFT draft-ietf-intserv-control-flow-00.txt April 18, 1997
Upsilon controls the amount of the link resources that can be used by
CL traffic. Decreasing upsilon makes the admission control algorithm
more conservative and reduces the number of CL flows admitted on a
link. Network operator willing to commit all their link capacity to
CL traffic might want to start off setting upsilon to 0.7. Depending
on the burstiness of extant traffic, upsilon may be tuned to values
higher than 1. Larger values of upsilon decreases the "safety
margin" of slack bandwidth that may be used to accommodate sudden
bursts in traffic. Hence network operators that operate their
network with high upsilon run a higher risk of violating CL service
description.
kappa -- New Flow Effect Factor
Kappa reflects the network operator's assessment of the effect new
flows may have on traffic load. Kappa of 1 provides for the worst
case where a new flow may send data at a constant bit rate consummate
with its token rate.
Network service providers should have the ability to control the
settings of each of these parameters, conditioned upon the network
link speed, extant traffic characteristics, and the providers' goals
(i.e., the percentage of bandwidth set aside for other services such
as best-effort, the degree of risk aversion, etc.). Network
operators will need to monitor the performance of the algorithm over
time and adjust these parameters to meet changing traffic
characteristics and service requirements. Automatic tuning of these
parameters is also possible [CKT96].
We mentioned in the Introduction that MBAC works well only on links
with high degree of statistical multiplexing where current traffic
measurements are reasonable predictors of future load. For links
with low degree of statistical multiplexing, the algorithm presented
here may be used without the measurement part, for example by
maintaining L as the sum of the token rates of all admitted flows,
with the parameters upsilon and kappa both set to 1.
Security Considerations
Security considerations are not discussed in this memo.
References
[B+96] R. Braden (ed.) et al. "Resource ReSerVation Protocol (RSVP)
Jamin/Breslau Expires 10/18/97 [Page 5]
INTERNET-DRAFT draft-ietf-intserv-control-flow-00.txt April 18, 1997
-- Version 1 Functional Specification", Internet Draft, November
1996, <draft-ietf-rsvp-spec-14.txt>.
[CKT96] C. Casetti, J. Kurose, and D. Towsley. "An Adaptive Algorithm
for Measurement-based Admission Control in Integrated Services Packet
Networks", Proc. of the Protocols for High Speed Networks Workshop,
Oct. 1996.
[Flo96] S. Floyd. "Comments on Measurement-based Admissions Control
for Controlled-Load Service", submitted for publication, 1996. Also
available as ftp://ftp.ee.lbl.gov/papers/admit.ps.Z.
[GK97] R.J. Gibbens and F.P. Kelly, "Measurement-Based Connection
Admission Control", Proc. of the International Teletraffic Congress
15, Jun. 1997.
[JSD97] S. Jamin, S.J. Shenker, and P.B. Danzig, "Comparison of
Measurement-based Admission Control Algorithms for Controlled-Load
Service", Proc. of IEEE Infocom 97, Apr. 1997. Also available as
http://netweb.usc.edu/jamin/admctl/info97.ps.gz.
[JS97] S. Jamin, S.J. Shenker, "Measurement-based Admission Control
Algorithms for Controlled-Load Service: A Structural Examination",
Univ. of Michigan, TR, 1997. Available as
http://irl.eecs.umich.edu/jamin/papers/mbac/clmbac.ps.gz
[Wro95] J. Wroclawski. "Specification of Controlled-Load Network
Element Service", Internet Draft, November 1996, <draft-ietf-
intserv-ctrl-load-svc-04.txt>.
Authors' Addresses:
Sugih Jamin
University of Michigan
CSE/EECS
1301 Beal Ave.
Ann Arbor, MI 48109-2122
EMail: jamin@eecs.umich.edu
Phone: (313) 763-1583
Lee Breslau
Xerox PARC
3333 Coyote Hill Road
Palo Alto, CA 94304-1314
Jamin/Breslau Expires 10/18/97 [Page 6]
INTERNET-DRAFT draft-ietf-intserv-control-flow-00.txt April 18, 1997
EMail: breslau@parc.xerox.com
Phone: 415-812-4402
Fax: 415-812-4471
Jamin/Breslau Expires 10/18/97 [Page 7]