home *** CD-ROM | disk | FTP | other *** search
/ Internet Info 1997 December / Internet_Info_CD-ROM_Walnut_Creek_December_1997.iso / drafts / draft_ietf_i / draft-ietf-intserv-control-flow-00.txt < prev    next >
Text File  |  1997-04-17  |  14KB  |  426 lines
  1.  
  2.  
  3.  
  4.  
  5. Internet Engineering Task Force                   Integrated Services WG
  6. INTERNET-DRAFT                                       S. Jamin/L. Breslau
  7. draft-ietf-intserv-control-flow-00.txt                       UMich/Xerox
  8.                                                           April 18, 1997
  9.                                                        Expires: 10/18/97
  10.  
  11.  
  12.  
  13.           A Measurement Based Admission Control Algorithm for
  14.                         Controlled-Load Service
  15.  
  16.  
  17. Status of this Memo
  18.  
  19.  
  20.    This document is an Internet-Draft.  Internet-Drafts are working
  21.    documents of the Internet Engineering Task Force (IETF), its areas,
  22.    and its working groups.  Note that other groups may also distribute
  23.    working documents as Internet-Drafts.
  24.  
  25.    Internet-Drafts are draft documents valid for a maximum of six months
  26.    and may be updated, replaced, or obsoleted by other documents at any
  27.    time.  It is inappropriate to use Internet-Drafts as reference
  28.    material or to cite them other than as "work in progress."
  29.  
  30.    To learn the current status of any Internet-Draft, please check the
  31.    "1id-abstracts.txt" listing contained in the Internet-Drafts Shadow
  32.    Directories on ftp.is.co.za (Africa), nic.nordu.net (Europe),
  33.    munnari.oz.au (Pacific Rim), ds.internic.net (US East Coast), or
  34.    ftp.isi.edu (US West Coast).
  35.  
  36.  
  37. Abstract
  38.  
  39.  
  40.    Controlled-Load Service provides data flows with an enhanced quality
  41.    of service, in the form of low packet delay and a low probability of
  42.    packet loss even under congestion.  A network element providing
  43.    Controlled-Load Service must use an admission control algorithm to
  44.    limit the number of data flows receiving the service.  In this
  45.    document we describe an admission control algorithm for Controlled-
  46.    Load Service.  This algorithm is not intended for IETF
  47.    standardization.  Rather, it is presented for informational purposes
  48.    only.
  49.  
  50.  
  51.  
  52.  
  53.  
  54.  
  55.  
  56. Jamin/Breslau               Expires 10/18/97                    [Page 1]
  57.  
  58.  
  59.  
  60.  
  61.  
  62.  
  63. INTERNET-DRAFT   draft-ietf-intserv-control-flow-00.txt   April 18, 1997
  64.  
  65.  
  66. Introduction
  67.  
  68.  
  69.    Controlled-Load Service (CL), as defined in [Wro95], is an enhanced
  70.    quality of service intended to support applications requiring
  71.    performance better than that which would be provided by traditional
  72.    best-effort service.  Even under congestion, network elements
  73.    offering CL are expected to provide flows with low delay and low
  74.    packet loss.
  75.  
  76.    In order to provide this enhanced level of service, network elements
  77.    must limit the number of flows receiving the service.  This is
  78.    accomplished by requiring applications to make explicit requests for
  79.    service.  Explicit requests for service can be made using a
  80.    reservation setup protocol, such as RSVP [B+96], or some other means.
  81.    Each network element that receives a request for service can either
  82.    accept or reject the request.  We refer to this decision as
  83.    "admission control".
  84.  
  85.    An application requesting CL presents the network element with a
  86.    traffic descriptor to describe its data flow.  This descriptor
  87.    includes a token bucket filter and a peak rate.  The token bucket
  88.    parameters, a rate and bucket depth, represent a loose upper bound on
  89.    the new data flow.  A measurement based admission control (MBAC)
  90.    admits or rejects a new flow based on measurements of existing
  91.    traffic and the parameterized description of the new flow.  The
  92.    dependence of MBACs on traffic measurements makes the quality of the
  93.    service they provide subject to statistical fluctuation of traffic.
  94.    We expect MBACs to work well only when there is a high degree of
  95.    statistical multiplexing of uncorrelated flows and traffic
  96.    fluctuation is not dominated by a small number of flows.  In this
  97.    document, we describe one such MBAC designed for CL.
  98.  
  99.    Admission control is not an area appropriate for IETF
  100.    standardization.  Rather, vendors and service providers are free to
  101.    implement and deploy any admission control algorithm that enables a
  102.    network element to meet the service requirements of the Controlled-
  103.    Load specification.  Indeed, admission control can be seen as an area
  104.    for product differentiation.  Hence, the algorithm described here is
  105.    presented for informational purposes only, providing a single example
  106.    of an MBAC that may be used as a reference algorithm.
  107.  
  108.    Various MBACs suitable for use with CL have been proposed in the
  109.    academic literature.  See, for example, algorithms described in
  110.    [Flo96, JSD97, GK97].  The algorithm described here was first
  111.    proposed in [JS97] and was shown to perform as well as several other
  112.    MBACs.  This algorithm is designed to be very simple to implement.
  113.    We believe that it meets the requirements given in the CL
  114.  
  115.  
  116.  
  117. Jamin/Breslau               Expires 10/18/97                    [Page 2]
  118.  
  119.  
  120.  
  121.  
  122.  
  123.  
  124. INTERNET-DRAFT   draft-ietf-intserv-control-flow-00.txt   April 18, 1997
  125.  
  126.  
  127.    specification, performs as well as other known algorithms, and
  128.    provides sufficient configuration parameters to allow it to be
  129.    deployed in a variety of settings.  We refer the interested readers
  130.    to the above references both for further details on the other MBACs
  131.    and for more background on the proposed MBAC.
  132.  
  133.    The remainder of this document is organized as follows.  In the next
  134.    section we describe the admission control algorithm.  Next, we
  135.    describe one measurement process that may be used to provide load
  136.    estimates that are used as inputs to the admission control algorithm.
  137.    Finally, we discuss the different tuning parameters that allow the
  138.    algorithm to be used in various settings.
  139.  
  140.  
  141. The Admission Control Algorithm
  142.  
  143.  
  144.    Our admission control algorithm takes as input L, a load estimate
  145.    produced by the measurement process (described in the next section),
  146.    C, the link bandwidth, upsilon, a user defined aggregate loading
  147.    factor, kappa, a user defined new flow effect factor, and r, the
  148.    token bucket rate of the new flow requesting admission.  Whenever a
  149.    new flow requests admittance under CL, the flow is admitted if the
  150.    following inequality is satisfied:
  151.  
  152.                         L < upsilon * C - kappa * r
  153.  
  154.    Otherwise the flow is rejected.
  155.  
  156.  
  157. The Measurement Process
  158.  
  159.  
  160.    The purpose of the measurement process is to compute an estimate of
  161.    the network load attributed to data packets receiving Controlled-Load
  162.    Service.  This estimate, which we refer to as L is used as input to
  163.    the admission control algorithm.  We describe a time window
  164.    measurement process here.  An alternative measurement process using
  165.    exponential averaging may be used instead [Flo96].
  166.  
  167.    The time window measurement process uses 2 parameters, T and S.  T is
  168.    the measurement window and S is the sampling period, with S <= T.
  169.  
  170.    During every sampling period, S, an average load is computed.  This
  171.    average load is simply the sum of bytes in packets receiving CL
  172.    divided by the length of the sampling period.  We note that computing
  173.    average load for a given sampling period is basic to most measurement
  174.    processes advocated for use with MBAC.
  175.  
  176.  
  177.  
  178. Jamin/Breslau               Expires 10/18/97                    [Page 3]
  179.  
  180.  
  181.  
  182.  
  183.  
  184.  
  185. INTERNET-DRAFT   draft-ietf-intserv-control-flow-00.txt   April 18, 1997
  186.  
  187.  
  188.    The only per-packet action required by the measurement process is to
  189.    accummulate the byte-count of packets receiving CL service.  All
  190.    other processing occurs with low frequency.  For performance
  191.    enhancement, a router vendor may wish to implement the per-packet
  192.    byte counting in hardware.  At each operator-defined sampling period
  193.    S, a software process reads and clears the hardware accummulator.
  194.    The software process also performs the other low frequency processing
  195.    to compute the load estimate.
  196.  
  197.    The load estimate, L, is updated as follows:
  198.  
  199.    1.  At the end of every measurement window, T, L is set to the
  200.    highest average load computed for any S during the previous window.
  201.  
  202.    2.  If a newly computed average load for a given sampling period S is
  203.    larger than the current value of L, L is set to the newly computed
  204.    average.
  205.  
  206.    3.  Whenever a new flow is admitted, the measurement estimate is
  207.    immediately increased by r, the token bucket rate of the newly
  208.    admitted flow.
  209.  
  210.  
  211. The Parameters
  212.  
  213.    In this section we discuss how each of the parameters can be adjusted
  214.    to control the behavior of the algorithm.  The specific settings that
  215.    are appropriate in any deployment environment depend on the
  216.    characteristics of that environment (i.e., the traffic
  217.    characteristics and link bandwidth), on how much Controlled-Load
  218.    traffic a network operator wants to admit on a link, and on the level
  219.    of risk the network operator is willing to take that the service
  220.    requirements are occasionally violated.
  221.  
  222.    T -- Measurement Window
  223.  
  224.    Increasing T increases the amount of history remembered by the
  225.    measurement process.  The values of T will be some integral multiple
  226.    of the value of S.
  227.  
  228.    S -- Sampling Period
  229.  
  230.    For a fixed T, decreasing S makes this measurement process more
  231.    sensitive to bursts of data.  Appropriate values of S are likely to
  232.    be on the order of thousands of packet transmission times.
  233.  
  234.    upsilon -- Aggregate Loading Factor
  235.  
  236.  
  237.  
  238.  
  239. Jamin/Breslau               Expires 10/18/97                    [Page 4]
  240.  
  241.  
  242.  
  243.  
  244.  
  245.  
  246. INTERNET-DRAFT   draft-ietf-intserv-control-flow-00.txt   April 18, 1997
  247.  
  248.  
  249.    Upsilon controls the amount of the link resources that can be used by
  250.    CL traffic.  Decreasing upsilon makes the admission control algorithm
  251.    more conservative and reduces the number of CL flows admitted on a
  252.    link.  Network operator willing to commit all their link capacity to
  253.    CL traffic might want to start off setting upsilon to 0.7.  Depending
  254.    on the burstiness of extant traffic, upsilon may be tuned to values
  255.    higher than 1.  Larger values of upsilon decreases the "safety
  256.    margin" of slack bandwidth that may be used to accommodate sudden
  257.    bursts in traffic.  Hence network operators that operate their
  258.    network with high upsilon run a higher risk of violating CL service
  259.    description.
  260.  
  261.    kappa -- New Flow Effect Factor
  262.  
  263.    Kappa reflects the network operator's assessment of the effect new
  264.    flows may have on traffic load.  Kappa of 1 provides for the worst
  265.    case where a new flow may send data at a constant bit rate consummate
  266.    with its token rate.
  267.  
  268.    Network service providers should have the ability to control the
  269.    settings of each of these parameters, conditioned upon the network
  270.    link speed, extant traffic characteristics, and the providers' goals
  271.    (i.e., the percentage of bandwidth set aside for other services such
  272.    as best-effort, the degree of risk aversion, etc.).  Network
  273.    operators will need to monitor the performance of the algorithm over
  274.    time and adjust these parameters to meet changing traffic
  275.    characteristics and service requirements.  Automatic tuning of these
  276.    parameters is also possible [CKT96].
  277.  
  278.    We mentioned in the Introduction that MBAC works well only on links
  279.    with high degree of statistical multiplexing where current traffic
  280.    measurements are reasonable predictors of future load.  For links
  281.    with low degree of statistical multiplexing, the algorithm presented
  282.    here may be used without the measurement part, for example by
  283.    maintaining L as the sum of the token rates of all admitted flows,
  284.    with the parameters upsilon and kappa both set to 1.
  285.  
  286.  
  287. Security Considerations
  288.  
  289.  
  290.    Security considerations are not discussed in this memo.
  291.  
  292.  
  293. References
  294.  
  295.  
  296.    [B+96] R. Braden (ed.) et al. "Resource ReSerVation Protocol (RSVP)
  297.  
  298.  
  299.  
  300. Jamin/Breslau               Expires 10/18/97                    [Page 5]
  301.  
  302.  
  303.  
  304.  
  305.  
  306.  
  307. INTERNET-DRAFT   draft-ietf-intserv-control-flow-00.txt   April 18, 1997
  308.  
  309.  
  310.    -- Version 1 Functional Specification", Internet Draft, November
  311.    1996, <draft-ietf-rsvp-spec-14.txt>.
  312.  
  313.    [CKT96] C. Casetti, J. Kurose, and D. Towsley. "An Adaptive Algorithm
  314.    for Measurement-based Admission Control in Integrated Services Packet
  315.    Networks", Proc. of the Protocols for High Speed Networks Workshop,
  316.    Oct. 1996.
  317.  
  318.    [Flo96] S. Floyd. "Comments on Measurement-based Admissions Control
  319.    for Controlled-Load Service", submitted for publication, 1996.  Also
  320.    available as ftp://ftp.ee.lbl.gov/papers/admit.ps.Z.
  321.  
  322.    [GK97] R.J. Gibbens and F.P. Kelly, "Measurement-Based Connection
  323.    Admission Control", Proc. of the International Teletraffic Congress
  324.    15, Jun. 1997.
  325.  
  326.    [JSD97] S. Jamin, S.J. Shenker, and P.B. Danzig, "Comparison of
  327.    Measurement-based Admission Control Algorithms for Controlled-Load
  328.    Service", Proc. of IEEE Infocom 97, Apr. 1997.  Also available as
  329.    http://netweb.usc.edu/jamin/admctl/info97.ps.gz.
  330.  
  331.    [JS97] S. Jamin, S.J. Shenker, "Measurement-based Admission Control
  332.    Algorithms for Controlled-Load Service: A Structural Examination",
  333.    Univ. of Michigan, TR, 1997.  Available as
  334.    http://irl.eecs.umich.edu/jamin/papers/mbac/clmbac.ps.gz
  335.  
  336.    [Wro95] J. Wroclawski.  "Specification of Controlled-Load Network
  337.    Element Service", Internet Draft, November 1996, <draft-ietf-
  338.    intserv-ctrl-load-svc-04.txt>.
  339.  
  340.  
  341. Authors' Addresses:
  342.  
  343.  
  344.    Sugih Jamin
  345.    University of Michigan
  346.    CSE/EECS
  347.    1301 Beal Ave.
  348.    Ann Arbor, MI 48109-2122
  349.  
  350.    EMail: jamin@eecs.umich.edu
  351.    Phone: (313) 763-1583
  352.  
  353.    Lee Breslau
  354.    Xerox PARC
  355.    3333 Coyote Hill Road
  356.    Palo Alto, CA  94304-1314
  357.  
  358.  
  359.  
  360.  
  361. Jamin/Breslau               Expires 10/18/97                    [Page 6]
  362.  
  363.  
  364.  
  365.  
  366.  
  367.  
  368. INTERNET-DRAFT   draft-ietf-intserv-control-flow-00.txt   April 18, 1997
  369.  
  370.  
  371.    EMail: breslau@parc.xerox.com
  372.    Phone: 415-812-4402
  373.    Fax:   415-812-4471
  374.  
  375.  
  376.  
  377.  
  378.  
  379.  
  380.  
  381.  
  382.  
  383.  
  384.  
  385.  
  386.  
  387.  
  388.  
  389.  
  390.  
  391.  
  392.  
  393.  
  394.  
  395.  
  396.  
  397.  
  398.  
  399.  
  400.  
  401.  
  402.  
  403.  
  404.  
  405.  
  406.  
  407.  
  408.  
  409.  
  410.  
  411.  
  412.  
  413.  
  414.  
  415.  
  416.  
  417.  
  418.  
  419.  
  420.  
  421.  
  422. Jamin/Breslau               Expires 10/18/97                    [Page 7]
  423.  
  424.  
  425.  
  426.