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, . [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, . 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]