Subject: guaranteed service (version 3)

From: Craig Partridge <[email-masked]>
Date: Wed, 15 Nov 95 06:46:16 -0800

Hi folks:

The new guaranteed service ID is attached (and is being sent to
the IETF Secretariat this instant).

Changes are largely small, but may be significant.  They are:

    * changing the policing rules to deal with a denial of service
    attack John Wroclawski discovered.  [Note: the best solution involves
    marking headers -- which currently we can't do, so we chose the second
    best solution, namely just forward stuff as best effort, while noting the
    need for marking]

    * adding a peak rate, per the suggestion of Guerin et al.  The major
    advantage is that it allows for somewhat reduced buffering in routers.

    * addressing the issues of link overhead, fragmentation, and packet
    rate raised in Stockholm.

A large set of notes by Scott Shenker, describing the motivation for various
changes in more detail, should be coming out in the next day or two.

[NOTE: This is the first of 6 to 8 documents I expect to see us send out
over the next few days].

Craig

************************************************************************

Internet Engineering Task Force                   Integrated Services WG
INTERNET-DRAFT                                   S. Shenker/C. Partridge
draft-ietf-intserv-guaranteed-svc-03.txt                       Xerox/BBN
                                                        14 November 1995
                                                         Expires: ?/?/96

             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).

   This document is a product of the Integrated Services working group
   of 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).

   This draft reflects changes from the IETF meeting in Stockholm.

Abstract

   This memo describes the network element behavior required to deliver
   guaranteed service in the Internet.  Guaranteed service provides firm
   (mathematically provable) bounds on end-to-end packet delays.  This
   specification follows the service specification template described in
   [1].

Shenker/Partridge            Expires ?/?/96                     [Page 1]

INTERNET-DRAFT  draft-ietf-intserv-guaranteed-svc-03.txt          ? 1995

Introduction

   This document defines the requirements for network elements that
   support guaranteed service.  This memo is one of a series of
   documents that specify the network element behavior required to
   support various qualities of service in IP internetworks.  Services
   described in these documents are useful both in the global Internet
   and private IP networks.

   This document is based on the service specification template given in
   [1]. Please refer to that document for definitions and additional
   information about the specification of qualities of service within
   the IP protocol family.

End-to-End Behavior

   The end-to-end behavior provided by a series of service elements that
   conform to this document is an assured level of bandwidth that, when
   used by a policed flow, produces a delay bounded service with no
   queueing loss (assuming no failure of network components or changes
   in routing during the life of the flow).

   The end-to-end behavior conforms to the fluid model (described below)
   in that the delivered delays do not exceed the fluid delays by more
   than the specified error bounds.  More precisely, the end-to-end
   delay bound is b/R+Ctot/R+Dtot (where b, R, Ctot, and Dtot are
   defined later in this document).  Guaranteed service does not control
   the minimal delay of packets, merely the maximal delays.

      NOTE: While the per-hop error terms needed to compute the end-to-
      end delays are exported by the service module (see Exported
      Information below), the mechanisms needed to collect per-hop
      bounds and make the end-to-end quantities Ctot and Dtot known to
      the applications are not described in this specification.  These
      functions, which can be provided by reservation setup protocols,
      routing protocols or by other network management functions, are
      outside the scope of this document.

   The end-to-end behavior (as characterized by Ctot and Dtot) provided
   along a path should be stable.  That is, it should not change as long
   as the end-to-end path does not change.

   This service is subject to admission control.

Shenker/Partridge            Expires ?/?/96                     [Page 2]

INTERNET-DRAFT  draft-ietf-intserv-guaranteed-svc-03.txt          ? 1995

Motivation

   Guaranteed service guarantees that packets will arrive within the
   guaranteed delivery time and will not be discarded due to queue
   overflows, provided the flow traffic stays within its specified
   traffic parameters.  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.  For example,
   some audio and video "play-back" applications are intolerant of any
   packet arriving after their play-back time.  Applications that have
   hard real-time requirements will also require guaranteed service.

   This service does not attempt to minimize the jitter (the difference
   between the minimal and maximal packet delays); it merely controls
   the maximal delay.  Because the guaranteed bound 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 can be far lower than the guaranteed delay.
   Therefore, authors of playback applications should note that packets
   will often arrive far earlier than the delivery deadline and will
   have to be buffered at the receiving system until it is time for the
   application to process them.

   This service represents one extreme end of delay control for
   networks.  Most other services providing delay control provide much
   weaker assurances about the resulting delays.  In order to provide
   this high level of assurance, guaranteed service is typically only
   useful if provided by every network element along the path.
   Moreover, as described in the Exported Information section, effective
   provision and use of the service requires that the set-up protocol
   used to request service provides service characterizations to
   intermediate routers and to the endpoints.

Network Element Data Handling Requirements

   The network element must ensure that the service approximates the
   "fluid model" of service.  The fluid model at service rate R is
   essentially the service that would be provided by a dedicated wire of
   bandwidth R between the source and receiver.  Thus, in the fluid
   model of service at a fixed rate R, the flow's service is completely
   independent of that of any other flow.

   The flow's level of service is characterized at each network element
   by a bandwidth (or service rate) 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.

Shenker/Partridge            Expires ?/?/96                     [Page 3]

INTERNET-DRAFT  draft-ietf-intserv-guaranteed-svc-03.txt          ? 1995

   The network element must ensure that its service matches the fluid
   model at that same rate to within a sharp error bound.

   The definition of guaranteed service relies on the result that the
   fluid delay of a flow obeying a token bucket (r,b) and being served
   by a line with bandwidth R is bounded by b/R as long as R is no less
   than r.  Guaranteed service with a service rate R, where now R is a
   share of bandwidth rather than the bandwidth of a dedicated line,
   approximates this behavior.

   More specifically, 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.  It is important to emphasize
   that C and D are maximums.  So, for instance, if an implementation
   has occasional gaps in service (perhaps due to processing routing
   updates), D needs to be large enough to account for the time a packet
   may lose during the gap in service.

   Links are not permitted to fragment packets as part of guaranteed
   service.  Packets larger than the MTU of the link must be policed as
   nonconformant which means that they will be policed according to the
   rules described in the Policing section below.

Invocation Information

   Guaranteed service is invoked by specifying the traffic (TSpec) and
   the desired service (RSpec) to the network element.  A service
   request for an existing flow that has a new TSpec and/or RSpec should
   be treated as a new invocation, in the sense that admission control
   must be reapplied to the flow.  Flows that reduce their TSpec and/or
   their RSpec (i.e., their new TSpec/RSpec is strictly smaller than the
   old TSpec/RSpec according to the ordering rules described in the
   section on Ordering below) should never be denied service.

   The TSpec takes the form of a token bucket plus a peak rate (p), a
   minimum policed unit (m), and a maximum packet size (M).

   The token bucket has a bucket depth, b, and a bucket rate, r.  Both b
   and r must be positive.  The rate, r, is measured in bytes of IP
   datagrams per second, and can range from 1 byte per second to as
   large as 40 terabytes per second (or about what is believed to be the
   maximum theoretical bandwidth of a single strand of fiber).  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 also measured in bytes and can range from 1
   byte to 250 gigabytes.  Again, floating point representations

Shenker/Partridge            Expires ?/?/96                     [Page 4]

INTERNET-DRAFT  draft-ietf-intserv-guaranteed-svc-03.txt          ? 1995

   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 peak rate, p, is measured in bytes of IP datagrams per second and
   has the same range and suggested representation as the bucket rate.
   The peak rate is the maximum rate at which the source and any
   reshaping points (reshaping points are defined below) may inject
   bursts of traffic into the network.  More precisely, it is the
   requirement that for all time periods the amount of data sent cannot
   exceed M+pT where M is the maximum packet size and T is the length of
   the time period.

   The minimum policed unit, m,  is an integer measured in bytes.  All
   IP datagrams less than size m will be counted, when policed and
   tested for conformace to the TSpec, as being of size m. The maximum
   packet size, M, is the biggest packet that will conform to the
   traffic specification; it is also measured in bytes.  The flow must
   be rejected if the requested maximum packet size is larger than the
   MTU of the link.   Both m and M must be positive, and m must be less
   then or equal to M.

   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 floating point numbers in
   single-precision IEEE floating point format followed by two 32-bit
   integers in network byte order.  The first value is the rate (r), the
   second value is the bucket size (b), the third is the minimum policed
   unit (m), and the fourth is the maximum packet size (M).

   The RSpec rate, R, can also be represented using single-precision
   IEEE floating point.

   For all IEEE floating point values, the sign bit must be zero. (All
   values must be positive).  Exponents less than 127 (i.e., 0) are
   prohibited.  Exponents greater than 162 (i.e., positive 35) are
   discouraged.

Shenker/Partridge            Expires ?/?/96                     [Page 5]

INTERNET-DRAFT  draft-ietf-intserv-guaranteed-svc-03.txt          ? 1995

Exported Information

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

   A network elements implementation of guaranteed 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.

   If the composition function is applied along the entire path to
   compute the end-to-end sums of C and D (Ctot and Dtot) and the
   resulting values are then provided to the end nodes (by presumably
   the setup protocol), the end nodes can compute the maximal packet
   delays.  Moreover, if the partial sums (Csum and Dsum) from the most
   recent reshaping point (reshaping points are defined below)
   downstream towards receivers are handed to each network element then
   these network elements can compute the buffer allocations necessary
   to achieve no packet loss.  The proper use and provision of this
   service requires that the quantities Ctot and Dtot, and the
   quantities Csum and Dsum be computed.  Therefore, we assume that
   usage of guaranteed service will be primarily in contexts where these
   quantities are made available to end nodes and network elements.

   The error term C is measured in units of bytes.  An individual
   element can advertise a C value between 1 and 2**28 (a bit over 250
   megabytes) and the total added over 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 (Ctot) for C is numbered 3 and the
   end-to-end composed value for D (Dtot) is numbered 4.

   The since-last-reshaping point composed value (Csum) for C is
   numbered 5 and the since-last-reshaping point composed value for D

Shenker/Partridge            Expires ?/?/96                     [Page 6]

INTERNET-DRAFT  draft-ietf-intserv-guaranteed-svc-03.txt          ? 1995

   (Dsum) is numbered 6.

   No other exported data is required by this specification.

Policing

   Policing is done at the edge of the network, at all heterogeneous
   source branch points and at all source merge points.  A heterogeneous
   source branch point is a spot where the multicast distribution tree
   from a source branches to multiple distinct paths, and the TSpec's of
   the reservations on the various outgoing links are not all the same.
   Policing need only be done if the TSpec on the outgoing link is "less
   than" (in the sense described in the Ordering section) the TSpec
   reserved on the immediately upstream link.  A source merge point is
   where the multicast distribution trees from two different sources
   (sharing the same reservation) merge.  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.  Policing may be done at other points as well as those
   described above.

   The token bucket and peak rate parameters require that traffic must
   obey the rule that over all time periods, the amount of data sent
   cannot exceed M+min[pT, rT+b-M], where r and b are the token bucket
   parameters, M is the maximum packet size, and T is the length of the
   time period (note that when p is infinite this reduces to the
   standard token bucket requirement).  For the purposes of this
   accounting, links must count packets which are smaller than the
   minimal policing unit to be of size m.  Packets which arrive at an
   element and cause a violation of the the M+min[pT, rT+b-M] bound are
   considered nonconformant.  Policing to conformance with this token
   bucket is done in two different ways.

   At the edge of the network, non-conforming packets are treated as
   best-effort datagrams.  [If and when a marking ability becomes
   available, these nonconformant packets should be ''marked'' as being
   noncompliant and then treated as best effort packets at all
   subsequent routers.]

      NOTE: There may be situations outside the scope of this document,
      such as when a a service module's implementation of guaranteed
      service is being used to implement traffic sharing rather than a
      quality of service, where the desired action is to discard non-
      conforming packets.  To allow for such uses, implementors should
      ensure that the action to be taken for non-conforming packets is

Shenker/Partridge            Expires ?/?/96                     [Page 7]

INTERNET-DRAFT  draft-ietf-intserv-guaranteed-svc-03.txt          ? 1995

      configurable.

   Inside the network, this approach does not produce the desired
   results, because queueing effects will occasionally cause a flow's
   traffic that entered the network as conformant to be no longer
   conformant at some downstream network element.  Therefore, inside the
   network, service elements must reshape traffic before applying the
   token bucket test.  Reshaping entails delaying packets until they are
   within conformance of the TSpec.

   Reshaping is done by combining a buffer with a token bucket and peak
   rate regulator and buffering data until it can be sent in conformance
   with the token bucket and peak rate parameters.  (The token bucket
   regulator should start with its token bucket full of tokens).  Under
   guaranteed service, the amount of buffering required to reshape any
   conforming traffic back to its original token bucket shape is
   b+Csum+(Dsum*r), where Csum and Dsum are the sums of the parameters C
   and D between the last reshaping point and the current reshaping
   point.  A network element must provide at least this much buffering.

   If a datagram arrives to discover the reshaping buffer is full, then
   the datagram is non-conforming.  Observe this means that a reshaper
   is effectively policing too.  As with a policer, the reshaper should
   relegate non-conforming datagrams to best effort.  [If marking is
   available, the non-conforming datagrams should be marked]

      NOTE: As with policers, it should be possible to configure how
      reshapers handle non-conforming packets.

   Note that while the large buffer makes it appear that reshapers add
   considerable delay, this is not the case.  Given a valid TSpec that
   accurately describes the traffic, reshaping will cause little extra
   delay at the reshaping point.  However, if the TSpec is smaller than
   the actual traffic, reshaping will cause a large queue to develop at
   the reshaping point, which both causes substantial additional delays
   and forces some datagrams to be treated as non-conforming.  This
   scenario makes an unpleasant denial of service attack possible, in
   which a receiver who is successfully receiving a flow's traffic via
   best effort service is pre-empted by a new receiver who requests a
   reservation for the flow, but with an inadequate TSpec and RSpec.
   The flow's traffic will now be policed and possibly reshaped.  If the
   policing function was chosen to discard datagrams, the best-effort
   receiver would stop receiving traffic.  For this reason, in the
   normal case, policers are simply to mark packets as best effort.
   While this protects against denial of service, it is still true that
   the bad TSpec may cause queueing delays to increase.

Shenker/Partridge            Expires ?/?/96                     [Page 8]

INTERNET-DRAFT  draft-ietf-intserv-guaranteed-svc-03.txt          ? 1995

      NOTE: To minimize problems of reordering datagrams, reshaping
      points may wish to forward a best-effort datagram from the front
      of the reshaping queue when a new datagram arrives and the
      reshaping buffer is full.

      Readers should also observe that reclassifying datagrams as best
      effort also makes support for elastic flows easier.  They can
      reserve a modest token bucket and when their traffic exceeds the
      token bucket, the excess traffic will be sent best effort.

   A related issue is that at all network elements, packets bigger than
   the MTU of the network element must be considered nonconformant and
   should be classified as best effort (and will then either be
   fragmented or dropped according to the element's handling of best
   effort traffic).  [Again, if marking is available, these reclassified
   packets should be marked.]

Ordering and Merging

   TSpec's are ordered according to the following rule: TSpec A is a
   substitute ("as good or better than") for TSpec B if (1) both the
   token bucket depth and rate for TSpec A are greater than or equal to
   those of TSpec B, (2) the minimum policed unit m is at least as small
   for TSpec A as it is for TSpec B, (3) the maximum packet size M is at
   least as large for TSpec A as it is for TSpec B, and (4) the peak
   rate p is at least as large in TSpec A as it is in TSpec B.

   A merged TSpec may be calculated over a set of TSpecs by taking the
   largest token bucket rate, largest bucket size, smallest minimal
   policed unit, and largest maximum packet size across all members of
   the set.  This use of the word "merging" is similar to that in the
   RSVP protocol; a merged TSpec is one which is adequate to describe
   the traffic from any one of a number of flows.

   The RSpec's are ordered by their numerical values, with larger being
   better.  More precisely, RSpec A is a substitute for RSpec B if the
   value of reserved service rate R in RSpec A is greater than or equal
   to the value in RSpec B.

 Guidelines for Implementors

   This section discusses a number of important implementation issues in
   no particular order.

   It is important to note that individual subnetworks are service
   elements and both routers and subnetworks must support the guaranteed
   service model to achieve guaranteed service.  Since subnetworks

Shenker/Partridge            Expires ?/?/96                     [Page 9]

INTERNET-DRAFT  draft-ietf-intserv-guaranteed-svc-03.txt          ? 1995

   typically are not capable of negotiating service using IP-based
   protocols, as part of providing guaranteed service, routers will have
   to act as proxies for the subnetworks they are attached to.

   In some cases, this proxy service will be easy.  For instance, on
   leased line, the proxy need simply ensure that the sum of all the
   flows' Rspec rates does not exceed the bandwidth of the line, and
   needs to advertise the serialization and transmission delays of the
   link as the values of C and D.

   In other cases, this proxy service will be complex.  In an ATM
   network, for example, it may require establishing an ATM VC for the
   flow  and computing the C and D terms for that VC.  Readers may
   observe that the token bucket and peak rate used by guaranteed
   service map directly to the Sustained Cell Rate, Burst Size, and Peak
   Cell Rate of ATM's Q.2931 QoS parameters for Variable Bit Rate
   traffic.

   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 (described below).

   Another issue related to subnetworks is that the TSpec's token bucket
   rates measure IP traffic and do not (and cannot) account for link
   level headers.  So the subnetwork service elements must adjust the
   rate and possibly the bucket size to account for adding link level
   headers.  Tunnels must also account for the additional IP headers
   that they add.

   For packet networks, a maximum header rate can usually be computed by
   dividing the rate and bucket sizes by the minimum policed unit.  For
   networks that do internal fragmentation, such as ATM, the computation
   may be more complex, since one must account for both per-fragment
   overhead and any wastage (empty bytes transmitted) due to mismatches
   between packet sizes and fragment sizes.  For instance, a
   conservative estimate of the additional data rate imposed by ATM AAL5
   plus ATM segmentation and reassembly is

                         ((r/48)*5)+((r/m)*(8+52))

   which represents the rate divided into 48-byte cells multiplied by
   the 5-byte ATM header, plus the maximum packet rate (r/m) multiplied
   by the cost of the 8-byte AAL5 header plus the maximum space that can
   be wasted by ATM segmentation of a packet (which is the 52 bytes
   wasted in a cell that contains one byte).  But this estimate is
   likely to be wildly high, especially if m is small, since ATM wastage
   is usually much less than 52 bytes.  (ATM implementors should be

Shenker/Partridge            Expires ?/?/96                    [Page 10]

INTERNET-DRAFT  draft-ietf-intserv-guaranteed-svc-03.txt          ? 1995

   warned that the token bucket may also have to be scaled when setting
   the VC parameters for call setup and that this example does not
   account for overhead incurred by encapsulations such as those
   specified in RFC 1483).

   To ensure no loss, service elements will have to allocate some
   buffering for bursts.  If every hop implemented the fluid model
   perfectly, this buffering would simply be b (the token bucket size).
   However, as noted in the discussion of reshaping earlier,
   implementations are approximations and we expect that traffic will
   become more bursty as it goes through the network.  However, as with
   shaping the amount of buffering required to handle the burstiness is
   bounded by b+Csum+(Dsum*R).  This buffering requirement can be
   reduced somewhat by computing the amount by which the peak rate slows
   the introduction of bursts into the network.

Evaluation Criteria

   The scheduling algorithm and admission control algorithm of the
   element must ensure that the delay bounds are never violated.
   Furthermore, the element must ensure that misbehaving flows do not
   affect the service given to other flows.  Vendors are encouraged to
   formally prove that their implementation is an approximation of the
   fluid model.

 Examples of Implementation

   Several algorithms and implementations exist that approximate the
   fluid model.  They include Weighted Fair Queueing (WFQ) [2], Jitter-
   EDD [3], Virtual Clock [4] and a scheme proposed by IBM [5].  A nice
   theoretical presentation that shows these schemes are part of a large
   class of algorithms can be found in [6].

 Examples of Use

   Consider an application that is intolerant of any lost or late
   packets.  It uses the advertised values Ctot and Dtot 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

   This memo discusses how this service could be abused to permit denial
   of service attacks.  The service, as defined, does not allow denial
   of service (although service may degrade under certain
   circumstances).

Shenker/Partridge            Expires ?/?/96                    [Page 11]

INTERNET-DRAFT  draft-ietf-intserv-guaranteed-svc-03.txt          ? 1995

References

   [1] S. Shenker and J. Wroclawski. "Network Element Service
   Specification Template", Internet Draft, June 1995, <draft-ietf-
   intserv-svc-template-01.txt>

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

   [3] L. Zhang, "Virtual Clock: A New Traffic Control Algorithm for
   Packet Switching Networks," in Proc. ACM SIGCOMM '90, pp. 19-29.

   [4] D. Verma, H. Zhang, and D. Ferrari, "Guaranteeing Delay Jitter
   Bounds in Packet Switching Networks," in Proc. Tricomm '91.

   [5] L. Georgiadis, R. Guerin, V. Peris, and K. N. Sivaraja,
   "Efficient Network QoS Provisioning Based on per Node Traffic
   Shaping," IBM Research Report No. RC-20064.

   [6] P. Goyal, S.S. Lam and H.M. Vin, "Determining End-to-End Delay
   Bounds in Heterogeneous Networks," in Proc. 5th Intl. Workshop on
   Network and Operating System Support for Digital Audio and Video,
   April 1995.

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 ?/?/96                    [Page 12]


Internet Engineering Task Force                   Integrated Services WG
INTERNET-DRAFT                                   S. Shenker/C. Partridge
draft-ietf-intserv-guaranteed-svc-03.txt                       Xerox/BBN
                                                        14 November 1995
                                                         Expires: ?/?/96

             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).

   This document is a product of the Integrated Services working group
   of 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).

   This draft reflects changes from the IETF meeting in Stockholm.

Abstract

   This memo describes the network element behavior required to deliver
   guaranteed service in the Internet.  Guaranteed service provides firm
   (mathematically provable) bounds on end-to-end packet delays.  This
   specification follows the service specification template described in
   [1].

Shenker/Partridge            Expires ?/?/96                     [Page 1]

INTERNET-DRAFT  draft-ietf-intserv-guaranteed-svc-03.txt          ? 1995

Introduction

   This document defines the requirements for network elements that
   support guaranteed service.  This memo is one of a series of
   documents that specify the network element behavior required to
   support various qualities of service in IP internetworks.  Services
   described in these documents are useful both in the global Internet
   and private IP networks.

   This document is based on the service specification template given in
   [1]. Please refer to that document for definitions and additional
   information about the specification of qualities of service within
   the IP protocol family.

End-to-End Behavior

   The end-to-end behavior provided by a series of service elements that
   conform to this document is an assured level of bandwidth that, when
   used by a policed flow, produces a delay bounded service with no
   queueing loss (assuming no failure of network components or changes
   in routing during the life of the flow).

   The end-to-end behavior conforms to the fluid model (described below)
   in that the delivered delays do not exceed the fluid delays by more
   than the specified error bounds.  More precisely, the end-to-end
   delay bound is b/R+Ctot/R+Dtot (where b, R, Ctot, and Dtot are
   defined later in this document).  Guaranteed service does not control
   the minimal delay of packets, merely the maximal delays.

      NOTE: While the per-hop error terms needed to compute the end-to-
      end delays are exported by the service module (see Exported
      Information below), the mechanisms needed to collect per-hop
      bounds and make the end-to-end quantities Ctot and Dtot known to
      the applications are not described in this specification.  These
      functions, which can be provided by reservation setup protocols,
      routing protocols or by other network management functions, are
      outside the scope of this document.

   The end-to-end behavior (as characterized by Ctot and Dtot) provided
   along a path should be stable.  That is, it should not change as long
   as the end-to-end path does not change.

   This service is subject to admission control.

Shenker/Partridge            Expires ?/?/96                     [Page 2]

INTERNET-DRAFT  draft-ietf-intserv-guaranteed-svc-03.txt          ? 1995

Motivation

   Guaranteed service guarantees that packets will arrive within the
   guaranteed delivery time and will not be discarded due to queue
   overflows, provided the flow traffic stays within its specified
   traffic parameters.  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.  For example,
   some audio and video "play-back" applications are intolerant of any
   packet arriving after their play-back time.  Applications that have
   hard real-time requirements will also require guaranteed service.

   This service does not attempt to minimize the jitter (the difference
   between the minimal and maximal packet delays); it merely controls
   the maximal delay.  Because the guaranteed bound 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 can be far lower than the guaranteed delay.
   Therefore, authors of playback applications should note that packets
   will often arrive far earlier than the delivery deadline and will
   have to be buffered at the receiving system until it is time for the
   application to process them.

   This service represents one extreme end of delay control for
   networks.  Most other services providing delay control provide much
   weaker assurances about the resulting delays.  In order to provide
   this high level of assurance, guaranteed service is typically only
   useful if provided by every network element along the path.
   Moreover, as described in the Exported Information section, effective
   provision and use of the service requires that the set-up protocol
   used to request service provides service characterizations to
   intermediate routers and to the endpoints.

Network Element Data Handling Requirements

   The network element must ensure that the service approximates the
   "fluid model" of service.  The fluid model at service rate R is
   essentially the service that would be provided by a dedicated wire of
   bandwidth R between the source and receiver.  Thus, in the fluid
   model of service at a fixed rate R, the flow's service is completely
   independent of that of any other flow.

   The flow's level of service is characterized at each network element
   by a bandwidth (or service rate) 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.

Shenker/Partridge            Expires ?/?/96                     [Page 3]

INTERNET-DRAFT  draft-ietf-intserv-guaranteed-svc-03.txt          ? 1995

   The network element must ensure that its service matches the fluid
   model at that same rate to within a sharp error bound.

   The definition of guaranteed service relies on the result that the
   fluid delay of a flow obeying a token bucket (r,b) and being served
   by a line with bandwidth R is bounded by b/R as long as R is no less
   than r.  Guaranteed service with a service rate R, where now R is a
   share of bandwidth rather than the bandwidth of a dedicated line,
   approximates this behavior.

   More specifically, 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.  It is important to emphasize
   that C and D are maximums.  So, for instance, if an implementation
   has occasional gaps in service (perhaps due to processing routing
   updates), D needs to be large enough to account for the time a packet
   may lose during the gap in service.

   Links are not permitted to fragment packets as part of guaranteed
   service.  Packets larger than the MTU of the link must be policed as
   nonconformant which means that they will be policed according to the
   rules described in the Policing section below.

Invocation Information

   Guaranteed service is invoked by specifying the traffic (TSpec) and
   the desired service (RSpec) to the network element.  A service
   request for an existing flow that has a new TSpec and/or RSpec should
   be treated as a new invocation, in the sense that admission control
   must be reapplied to the flow.  Flows that reduce their TSpec and/or
   their RSpec (i.e., their new TSpec/RSpec is strictly smaller than the
   old TSpec/RSpec according to the ordering rules described in the
   section on Ordering below) should never be denied service.

   The TSpec takes the form of a token bucket plus a peak rate (p), a
   minimum policed unit (m), and a maximum packet size (M).

   The token bucket has a bucket depth, b, and a bucket rate, r.  Both b
   and r must be positive.  The rate, r, is measured in bytes of IP
   datagrams per second, and can range from 1 byte per second to as
   large as 40 terabytes per second (or about what is believed to be the
   maximum theoretical bandwidth of a single strand of fiber).  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 also measured in bytes and can range from 1
   byte to 250 gigabytes.  Again, floating point representations

Shenker/Partridge            Expires ?/?/96                     [Page 4]

INTERNET-DRAFT  draft-ietf-intserv-guaranteed-svc-03.txt          ? 1995

   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 peak rate, p, is measured in bytes of IP datagrams per second and
   has the same range and suggested representation as the bucket rate.
   The peak rate is the maximum rate at which the source and any
   reshaping points (reshaping points are defined below) may inject
   bursts of traffic into the network.  More precisely, it is the
   requirement that for all time periods the amount of data sent cannot
   exceed M+pT where M is the maximum packet size and T is the length of
   the time period.

   The minimum policed unit, m,  is an integer measured in bytes.  All
   IP datagrams less than size m will be counted, when policed and
   tested for conformace to the TSpec, as being of size m. The maximum
   packet size, M, is the biggest packet that will conform to the
   traffic specification; it is also measured in bytes.  The flow must
   be rejected if the requested maximum packet size is larger than the
   MTU of the link.   Both m and M must be positive, and m must be less
   then or equal to M.

   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 floating point numbers in
   single-precision IEEE floating point format followed by two 32-bit
   integers in network byte order.  The first value is the rate (r), the
   second value is the bucket size (b), the third is the minimum policed
   unit (m), and the fourth is the maximum packet size (M).

   The RSpec rate, R, can also be represented using single-precision
   IEEE floating point.

   For all IEEE floating point values, the sign bit must be zero. (All
   values must be positive).  Exponents less than 127 (i.e., 0) are
   prohibited.  Exponents greater than 162 (i.e., positive 35) are
   discouraged.

Shenker/Partridge            Expires ?/?/96                     [Page 5]

INTERNET-DRAFT  draft-ietf-intserv-guaranteed-svc-03.txt          ? 1995

Exported Information

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

   A network elements implementation of guaranteed 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.

   If the composition function is applied along the entire path to
   compute the end-to-end sums of C and D (Ctot and Dtot) and the
   resulting values are then provided to the end nodes (by presumably
   the setup protocol), the end nodes can compute the maximal packet
   delays.  Moreover, if the partial sums (Csum and Dsum) from the most
   recent reshaping point (reshaping points are defined below)
   downstream towards receivers are handed to each network element then
   these network elements can compute the buffer allocations necessary
   to achieve no packet loss.  The proper use and provision of this
   service requires that the quantities Ctot and Dtot, and the
   quantities Csum and Dsum be computed.  Therefore, we assume that
   usage of guaranteed service will be primarily in contexts where these
   quantities are made available to end nodes and network elements.

   The error term C is measured in units of bytes.  An individual
   element can advertise a C value between 1 and 2**28 (a bit over 250
   megabytes) and the total added over 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 (Ctot) for C is numbered 3 and the
   end-to-end composed value for D (Dtot) is numbered 4.

   The since-last-reshaping point composed value (Csum) for C is
   numbered 5 and the since-last-reshaping point composed value for D

Shenker/Partridge            Expires ?/?/96                     [Page 6]

INTERNET-DRAFT  draft-ietf-intserv-guaranteed-svc-03.txt          ? 1995

   (Dsum) is numbered 6.

   No other exported data is required by this specification.

Policing

   Policing is done at the edge of the network, at all heterogeneous
   source branch points and at all source merge points.  A heterogeneous
   source branch point is a spot where the multicast distribution tree
   from a source branches to multiple distinct paths, and the TSpec's of
   the reservations on the various outgoing links are not all the same.
   Policing need only be done if the TSpec on the outgoing link is "less
   than" (in the sense described in the Ordering section) the TSpec
   reserved on the immediately upstream link.  A source merge point is
   where the multicast distribution trees from two different sources
   (sharing the same reservation) merge.  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.  Policing may be done at other points as well as those
   described above.

   The token bucket and peak rate parameters require that traffic must
   obey the rule that over all time periods, the amount of data sent
   cannot exceed M+min[pT, rT+b-M], where r and b are the token bucket
   parameters, M is the maximum packet size, and T is the length of the
   time period (note that when p is infinite this reduces to the
   standard token bucket requirement).  For the purposes of this
   accounting, links must count packets which are smaller than the
   minimal policing unit to be of size m.  Packets which arrive at an
   element and cause a violation of the the M+min[pT, rT+b-M] bound are
   considered nonconformant.  Policing to conformance with this token
   bucket is done in two different ways.

   At the edge of the network, non-conforming packets are treated as
   best-effort datagrams.  [If and when a marking ability becomes
   available, these nonconformant packets should be ''marked'' as being
   noncompliant and then treated as best effort packets at all
   subsequent routers.]

      NOTE: There may be situations outside the scope of this document,
      such as when a a service module's implementation of guaranteed
      service is being used to implement traffic sharing rather than a
      quality of service, where the desired action is to discard non-
      conforming packets.  To allow for such uses, implementors should
      ensure that the action to be taken for non-conforming packets is

Shenker/Partridge            Expires ?/?/96                     [Page 7]

INTERNET-DRAFT  draft-ietf-intserv-guaranteed-svc-03.txt          ? 1995

      configurable.

   Inside the network, this approach does not produce the desired
   results, because queueing effects will occasionally cause a flow's
   traffic that entered the network as conformant to be no longer
   conformant at some downstream network element.  Therefore, inside the
   network, service elements must reshape traffic before applying the
   token bucket test.  Reshaping entails delaying packets until they are
   within conformance of the TSpec.

   Reshaping is done by combining a buffer with a token bucket and peak
   rate regulator and buffering data until it can be sent in conformance
   with the token bucket and peak rate parameters.  (The token bucket
   regulator should start with its token bucket full of tokens).  Under
   guaranteed service, the amount of buffering required to reshape any
   conforming traffic back to its original token bucket shape is
   b+Csum+(Dsum*r), where Csum and Dsum are the sums of the parameters C
   and D between the last reshaping point and the current reshaping
   point.  A network element must provide at least this much buffering.

   If a datagram arrives to discover the reshaping buffer is full, then
   the datagram is non-conforming.  Observe this means that a reshaper
   is effectively policing too.  As with a policer, the reshaper should
   relegate non-conforming datagrams to best effort.  [If marking is
   available, the non-conforming datagrams should be marked]

      NOTE: As with policers, it should be possible to configure how
      reshapers handle non-conforming packets.

   Note that while the large buffer makes it appear that reshapers add
   considerable delay, this is not the case.  Given a valid TSpec that
   accurately describes the traffic, reshaping will cause little extra
   delay at the reshaping point.  However, if the TSpec is smaller than
   the actual traffic, reshaping will cause a large queue to develop at
   the reshaping point, which both causes substantial additional delays
   and forces some datagrams to be treated as non-conforming.  This
   scenario makes an unpleasant denial of service attack possible, in
   which a receiver who is successfully receiving a flow's traffic via
   best effort service is pre-empted by a new receiver who requests a
   reservation for the flow, but with an inadequate TSpec and RSpec.
   The flow's traffic will now be policed and possibly reshaped.  If the
   policing function was chosen to discard datagrams, the best-effort
   receiver would stop receiving traffic.  For this reason, in the
   normal case, policers are simply to mark packets as best effort.
   While this protects against denial of service, it is still true that
   the bad TSpec may cause queueing delays to increase.

Shenker/Partridge            Expires ?/?/96                     [Page 8]

INTERNET-DRAFT  draft-ietf-intserv-guaranteed-svc-03.txt          ? 1995

      NOTE: To minimize problems of reordering datagrams, reshaping
      points may wish to forward a best-effort datagram from the front
      of the reshaping queue when a new datagram arrives and the
      reshaping buffer is full.

      Readers should also observe that reclassifying datagrams as best
      effort also makes support for elastic flows easier.  They can
      reserve a modest token bucket and when their traffic exceeds the
      token bucket, the excess traffic will be sent best effort.

   A related issue is that at all network elements, packets bigger than
   the MTU of the network element must be considered nonconformant and
   should be classified as best effort (and will then either be
   fragmented or dropped according to the element's handling of best
   effort traffic).  [Again, if marking is available, these reclassified
   packets should be marked.]

Ordering and Merging

   TSpec's are ordered according to the following rule: TSpec A is a
   substitute ("as good or better than") for TSpec B if (1) both the
   token bucket depth and rate for TSpec A are greater than or equal to
   those of TSpec B, (2) the minimum policed unit m is at least as small
   for TSpec A as it is for TSpec B, (3) the maximum packet size M is at
   least as large for TSpec A as it is for TSpec B, and (4) the peak
   rate p is at least as large in TSpec A as it is in TSpec B.

   A merged TSpec may be calculated over a set of TSpecs by taking the
   largest token bucket rate, largest bucket size, smallest minimal
   policed unit, and largest maximum packet size across all members of
   the set.  This use of the word "merging" is similar to that in the
   RSVP protocol; a merged TSpec is one which is adequate to describe
   the traffic from any one of a number of flows.

   The RSpec's are ordered by their numerical values, with larger being
   better.  More precisely, RSpec A is a substitute for RSpec B if the
   value of reserved service rate R in RSpec A is greater than or equal
   to the value in RSpec B.

 Guidelines for Implementors

   This section discusses a number of important implementation issues in
   no particular order.

   It is important to note that individual subnetworks are service
   elements and both routers and subnetworks must support the guaranteed
   service model to achieve guaranteed service.  Since subnetworks

Shenker/Partridge            Expires ?/?/96                     [Page 9]

INTERNET-DRAFT  draft-ietf-intserv-guaranteed-svc-03.txt          ? 1995

   typically are not capable of negotiating service using IP-based
   protocols, as part of providing guaranteed service, routers will have
   to act as proxies for the subnetworks they are attached to.

   In some cases, this proxy service will be easy.  For instance, on
   leased line, the proxy need simply ensure that the sum of all the
   flows' Rspec rates does not exceed the bandwidth of the line, and
   needs to advertise the serialization and transmission delays of the
   link as the values of C and D.

   In other cases, this proxy service will be complex.  In an ATM
   network, for example, it may require establishing an ATM VC for the
   flow  and computing the C and D terms for that VC.  Readers may
   observe that the token bucket and peak rate used by guaranteed
   service map directly to the Sustained Cell Rate, Burst Size, and Peak
   Cell Rate of ATM's Q.2931 QoS parameters for Variable Bit Rate
   traffic.

   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 (described below).

   Another issue related to subnetworks is that the TSpec's token bucket
   rates measure IP traffic and do not (and cannot) account for link
   level headers.  So the subnetwork service elements must adjust the
   rate and possibly the bucket size to account for adding link level
   headers.  Tunnels must also account for the additional IP headers
   that they add.

   For packet networks, a maximum header rate can usually be computed by
   dividing the rate and bucket sizes by the minimum policed unit.  For
   networks that do internal fragmentation, such as ATM, the computation
   may be more complex, since one must account for both per-fragment
   overhead and any wastage (empty bytes transmitted) due to mismatches
   between packet sizes and fragment sizes.  For instance, a
   conservative estimate of the additional data rate imposed by ATM AAL5
   plus ATM segmentation and reassembly is

                         ((r/48)*5)+((r/m)*(8+52))

   which represents the rate divided into 48-byte cells multiplied by
   the 5-byte ATM header, plus the maximum packet rate (r/m) multiplied
   by the cost of the 8-byte AAL5 header plus the maximum space that can
   be wasted by ATM segmentation of a packet (which is the 52 bytes
   wasted in a cell that contains one byte).  But this estimate is
   likely to be wildly high, especially if m is small, since ATM wastage
   is usually much less than 52 bytes.  (ATM implementors should be

Shenker/Partridge            Expires ?/?/96                    [Page 10]

INTERNET-DRAFT  draft-ietf-intserv-guaranteed-svc-03.txt          ? 1995

   warned that the token bucket may also have to be scaled when setting
   the VC parameters for call setup and that this example does not
   account for overhead incurred by encapsulations such as those
   specified in RFC 1483).

   To ensure no loss, service elements will have to allocate some
   buffering for bursts.  If every hop implemented the fluid model
   perfectly, this buffering would simply be b (the token bucket size).
   However, as noted in the discussion of reshaping earlier,
   implementations are approximations and we expect that traffic will
   become more bursty as it goes through the network.  However, as with
   shaping the amount of buffering required to handle the burstiness is
   bounded by b+Csum+(Dsum*R).  This buffering requirement can be
   reduced somewhat by computing the amount by which the peak rate slows
   the introduction of bursts into the network.

Evaluation Criteria

   The scheduling algorithm and admission control algorithm of the
   element must ensure that the delay bounds are never violated.
   Furthermore, the element must ensure that misbehaving flows do not
   affect the service given to other flows.  Vendors are encouraged to
   formally prove that their implementation is an approximation of the
   fluid model.

 Examples of Implementation

   Several algorithms and implementations exist that approximate the
   fluid model.  They include Weighted Fair Queueing (WFQ) [2], Jitter-
   EDD [3], Virtual Clock [4] and a scheme proposed by IBM [5].  A nice
   theoretical presentation that shows these schemes are part of a large
   class of algorithms can be found in [6].

 Examples of Use

   Consider an application that is intolerant of any lost or late
   packets.  It uses the advertised values Ctot and Dtot 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

   This memo discusses how this service could be abused to permit denial
   of service attacks.  The service, as defined, does not allow denial
   of service (although service may degrade under certain
   circumstances).

Shenker/Partridge            Expires ?/?/96                    [Page 11]

INTERNET-DRAFT  draft-ietf-intserv-guaranteed-svc-03.txt          ? 1995

References

   [1] S. Shenker and J. Wroclawski. "Network Element Service
   Specification Template", Internet Draft, June 1995, <draft-ietf-
   intserv-svc-template-01.txt>

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

   [3] L. Zhang, "Virtual Clock: A New Traffic Control Algorithm for
   Packet Switching Networks," in Proc. ACM SIGCOMM '90, pp. 19-29.

   [4] D. Verma, H. Zhang, and D. Ferrari, "Guaranteeing Delay Jitter
   Bounds in Packet Switching Networks," in Proc. Tricomm '91.

   [5] L. Georgiadis, R. Guerin, V. Peris, and K. N. Sivaraja,
   "Efficient Network QoS Provisioning Based on per Node Traffic
   Shaping," IBM Research Report No. RC-20064.

   [6] P. Goyal, S.S. Lam and H.M. Vin, "Determining End-to-End Delay
   Bounds in Heterogeneous Networks," in Proc. 5th Intl. Workshop on
   Network and Operating System Support for Digital Audio and Video,
   April 1995.

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 ?/?/96                    [Page 12]

---

From: Pawan Goyal <[email-masked]>
Date: Thu, 16 Nov 1995 10:57:56 -0600 (CST)

A few months ago, I had pointed out what I believed to be an error in
the "Network Element Data Handling Requirements" specifications.
However, the specifications have not changed. I would appreciate it if
someone could clear up my confusion (I am enclosing the original post
below the dashed line).

On a separate note, the new specification allows the rate reservation
to be increased but does not specify the delay behaviour in presence
of such changes.  If rate reservation is increased from R_1 to R_2,
one might intuitively expect the e2e delay to be:

b/R_2 + Ctot/R_2 + Dtot (1)

However, contrary to the intuition, the e2e delay that can be guaranteed
is:

b/R_2 + Ctot/R_1 + Dtot (2)
	^^^^^^^^
Clearly, (2) is larger than (1) (refer to Theorem 9 of [1] for a proof).
Hence, delay behaviour needs to be specified in greater detail for such
rate changes.

Pawan

[1] P. Goyal and H. M. Vin, "Generalized Guaranteed Rate Scheduling Algorithms:
A Framework", Technical Report 95-30, Department of Computer Sciences, The
University of Texas at Austin, Available via http://www.cs.utexas.edu/users/pawang .

-----------------------------------------------------------------------

I believe the error term C as specified in the "Network Element Data 
Handling Requirements" does not correctly capture the semantics it is
supposed to. To illustrate, the Network Element Data Handling Requirements
says
 
 " The fluid delay of a flow obeying a token bucket (r,b) and being
   served by a line with bandwidth R is bounded 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. "

It can be easily shown that for many scheduling algorithms (WFQ,
Virtual Clock...) C as defined above is 0. However, for the purpose of
computing Ctot, even in a network of only WFQ servers, C can not be
chosen to be 0.

The main problem, I believe, is that the term Ctot in a network
environment comes into play because of the packetized nature of
transmission and not the behaviour of individual network
elements. Hence, even if a network element ensures that delay of any
packet is less than b/R+D, the term C would exist in the end-to-end
delay computations.  Hence, C is "independent" of the network element
behaviour.

The correct semantics would be captured if a network element is
required to ensure maximum delay of b/R +D and Ctot is interpreted as
the number of servers on the path of a flow.  In such a case, the e2e
delay would be computed as:

	b/R + (Ctot -1)*L_max/R + Dtot

where L_max is the maximum packet length of a flow. Observe that since
L_max is a property of a flow, the network element has to characterize
its behaviour by only one parameter D.  Though it is possible that
removing C from the characterization of a network element may not
allow capturing the behaviour of all network elements (although I do
not believe so), its current definition can lead to incorrect
behaviour.

Pawan