Subject: new draft of guaranteed service document

From: Craig Partridge <[email-masked]>
Date: Fri, 23 Jun 95 15:27:06 -0700

[new template and controlled-delay are also enroute]

Internet Engineering Task Force                   Integrated Services WG
INTERNET-DRAFT                                   S. Shenker/C. Partridge
draft-ietf-intserv-guaranteed-svc-01.txt                 Xerox/BBN
                                                             July 1995
                                                        Expires: 12/1/95

             Specification of Guaranteed Quality of 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

   This memo describes the network element behavior required to deliver
   guaranteed service in the Internet. The memo follows the service
   template model of specifying per-network-element behavior,
   guidelines, and evaluation requirements.

   This document is a product of the Integrated Services working group
   within the Internet Engineering Task Force.  Comments are solicited
   and should be addressed to the working group's mailing list at int-
   [email-masked] and/or the author(s).

Introduction

   This memo is one of a series of documents which specify network
   element behavior in IP internetworks which provide multiple qualities
   of service.

   This memo defines a guaranteed service.  In particular, it defines

Shenker/Partridge           Expires 12/1/95                     [Page 1]

INTERNET-DRAFT  draft-ietf-intserv-guaranteed-svc-01.txt      July, 1995

   requirements for network elements that support this service.  It
   follows the service template specified in [XXX].  Readers should
   refer to that document for additional details about the specification
   of qualities of service for IP internetworks.

Motivation

   A guaranteed service provides firm (mathematically provable)
   guarantees that the end-to-end delay experienced by packets in a flow
   will not exceed a set limit, assuming that all service elements in
   the flow's path support guaranteed service.  We also assume that
   there are no hard failures in the intermediate nodes or packet
   routing changes within the lifetime of the flow. Failure cases must
   be handled by higher protocols.

   This service is designed for applications which are intolerant of any
   loss and any applications with hard real-time requirements.  This
   service guarantees that packets will arrive within the guaranteed
   delivery time and will not be discarded due to queue overflows.
   Authors of playback applications should note that packets will often
   arrive far earlier than the delivery deadline and will have to
   buffered at the receiving system until it is time for the application
   to process them.

Network Element Data Handling Requirements

   The network element must ensure that the service matches the "fluid
   model" of service (as discussed in [XXX]).

   The flow's level of service is characterized at each network element
   by a bandwidth R and a buffer size B.  R represents the share of the
   link's bandwidth the flow is entitled to and B represents the buffer
   space in the router that the flow may consume.  The network element
   must ensure that its service matches the fluid model at that same
   rate to within a sharp error bound.

   The fluid delay of a flow obeying a token bucket (r,b) and being
   served by a line with bandwith R is given by b/R as long as R is no
   less than r.

   The network element must ensure that the delay of any packet be less
   than b/R+C/R+D where C and D describe the maximal deviation away from
   the fluid model.  For instance, for Weighted Fair Queueing, C is
   given by MTU of the outbound link and D is zero.

   The assurance that packets will not be lost is obtained by setting
   the router buffer space B to be equal to the token bucket b plus some
   error term.

Shenker/Partridge           Expires 12/1/95                     [Page 2]

INTERNET-DRAFT  draft-ietf-intserv-guaranteed-svc-01.txt      July, 1995

    NOTE: the mathematics of buffer space are not fully worked out and
    this last sentence may be wrong.

Invocation Information

   Service is invoked by specifying the traffic (TSpec) and the desired
   service (RSpec) to the network element.

   The TSpec takes the form of a token bucket, with a bucket depth, b,
   and a bucket rate, r.  Both b and r must be positive.

   The rate, r, is measured in bytes per 1/100th of a second, and can
   range from 1 to 10^12.  This range allows data rates as small as 800
   bits per second (a reasonable minimum) as well as data rates as large
   as 800 terabits per second (or 10 times what is believed to be the
   maximum theoretical bandwidth of a single strand of fiber) to be
   requested.  Clearly, particularly for large bandwidths, only the
   first few digits are significant and so the use of floating point
   representations, accurate to at least 0.1% is encouraged.

   The bucket depth, b, is measured in bytes and can range from 1 byte
   to 250 gigabytes.  Again, floating point representations accurate to
   at least 0.1% are encouraged.

   The range of values is intentionally large to allow for the future
   bandwidths.  The range is not intended to imply that a network
   element must support the entire range.

   The RSpec is a rate R, where R must be greater than or equal to r.
   The RSpec rate can be bigger than the TSpec rate because higher rates
   will reduce queueing delay.   No buffer specification is included in
   the RSpec because the service element is expected to derive the
   required buffer space to ensure no queueing loss from the bucket size
   in the TSpec, the rate in the RSpec, combined with internal
   information about how the element manages its traffic.

   The TSpec can be represented by two 16-bit values each using the
   following form:
                    15        10 9                 0
                    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
                    | Exponent  |     Value         |
                    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

   In this format, the 6 most significant bits of the word encode an
   exponent (E), and the 10 LSB's encode a value (V).  This format
   encodes a number, of the form V * (2**E).  This format is chosen to
   allow easy representation of a wide range of values, while avoiding
   over-precise representations. The 16-bit word is placed into packets

Shenker/Partridge           Expires 12/1/95                     [Page 3]

INTERNET-DRAFT  draft-ietf-intserv-guaranteed-svc-01.txt      July, 1995

   in network byte order.

   The first value is the rate (r) and the second value is the bucket
   size (b).

   The RSpec rate, R, can use the same representation.

Exported Information

   Each guaranteed service module must export at least the following
   information.  All of the parameters described below are
   characterization parameters.

   A flow's service is characterized by two error terms, C and D, which
   represent how the element's implementation of the guaranteed service
   deviates from the fluid model.  These two parameters have an additive
   composition rule.  For both parameters, the composition function
   computes the sum of the parameter values (Ctot and Dtot) across all
   network elements in the path and delivers this value to the end
   nodes.  Furthermore, (see the section on Policing below),
   intermediate values of Ctot and Dtot need to be delivered to policing
   points to ensure no queueing loss.

   The error term C is measured in units of bytes.  An individual
   element can advertise a delay value between 1 and 2**28 (a bit over
   250 megabytes) and the total added all elements can range as high as
   2**32-1.  Should the sum of the different elements delay exceed
   2**32-1, the end-to-end error term should be 2**32-1.

   The error term D is measured in units of one microsecond.  An
   individual element can advertise a delay value between 1 and 2**28
   (somewhat over two minutes) and the total delay added all elements
   can range as high as 2**32-1.  Should the sum of the different
   elements delay exceed 2**32-1, the end-to-end delay should be 2**32-
   1.

   The guaranteed service is service_name 2.

   Error characterization parameter C is numbered 1 and parameter D is
   numbered 2.

   The end-to-end composed value for C is numbered 3 and the end-to-end
   composed value for D is numbered 4.

Shenker/Partridge           Expires 12/1/95                     [Page 4]

INTERNET-DRAFT  draft-ietf-intserv-guaranteed-svc-01.txt      July, 1995

Policing

   Policing is done at the edge of the network and at all source merge
   points. A source merge point is where data from different sources is
   merged into a single flow.  It is the responsibility of the invoker
   of the service (a setup protocol, local configuration tool, or
   similar mechanism) to identify points where policing is required.

   Nonconforming packets are dropped.

   Implementors should note that traffic entering the network with a
   particular token bucket (r,b) will often become more bursty as it
   travels through the network.  However, under guaranteed service, the
   burstiness of the flow at any given point is bounded by a token
   bucket equal Ctot+b+(Dtot*R), where Ctot and Dtot are the sums of the
   parameters C and D between the flow's source and the policing point.

    WARNING: The derivation of the enhanced token bucket size may not be
    quite right.  We are still working through the theory.

Ordering and Merging

   TSpec's are ordered according to the following rule: TSpec A is a
   substitute for TSpec B if both the the token bucket depth and rate
   for TSpec A are greater than or equal than those of TSpec B.  The
   RSpec's are ordered by their numerical values, with larger being
   better.

Resulting Service

   The resulting end-to-end service is an assured bandwidth service
   which, when used by a policed flow, produces a delay bounded service
   with no queueing loss.

   The service conforms to the fluid model to within the specified error
   bounds.  The end-to-end delay bound is b/R+Ctot/R+Dtot.

   This service is intended for applications which need a firm guarantee
   that a packet will arrive no later than a certain time after it was
   transmitted by its source.  However, implementors should keep in mind
   that because the guaranteed is a firm one, it must be large enough to
   cover extremely rare cases of long queueing delays.  Several studies
   have shown that the actual delay for the vast majority of packets
   will be far lower than the guaranteed delay, and receiving systems or
   applications should be prepared to receive packets that arrive well
   before the delay bound.

Shenker/Partridge           Expires 12/1/95                     [Page 5]

INTERNET-DRAFT  draft-ietf-intserv-guaranteed-svc-01.txt      July, 1995

 Guidelines for Implementors

   [none]

Evaluation Criteria

   The scheduling algorithm and admission control algorithm of the
   element must ensure that the delay bounds are never violated.
   Vendors are encouraged to formally prove that their implementation is
   an approximation of the fluid model.

 Examples of Implementation

   One implementation of guaranteed service would be to implement the
   Weighted Fair Queueing (WFQ) scheduling algorithm [1].

 Examples of Use

   Consider an application that is intolerant of any lost or late
   packets.  It uses the advertised values Ctot and Dtot (the values of
   C and D added across all nodes) and the TSpec of the flow, to
   determine compute the resulting delay bound from a service request R.
   It then sets its playback point to b/R+Ctot/R+Dtot.
Security Considerations

   Security considerations are not discussed in this memo.

References

   1. A. Demers, S. Keshav and S. Shenker, "Analysis and Simulation of a
   Fair Queueing Algorithm," in Internetworking: Research and
   Experience, Vol 1, No. 1., pp. 3-26.

Authors' Address:

   Scott Shenker
   Xerox PARC
   3333 Coyote Hill Road
   Palo Alto, CA  94304-1314
   [email-masked]
   415-812-4840
   415-812-4471 (FAX)

   Craig Partridge
   BBN
   2370 Amherst St
   Palo Alto CA 94306
   [email-masked]

Shenker/Partridge           Expires 12/1/95                     [Page 6]

INTERNET-DRAFT  draft-ietf-intserv-guaranteed-svc-01.txt      July, 1995

Shenker/Partridge           Expires 12/1/95                     [Page 7]