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]