Subject: new guaranteed draft

From: Craig Partridge <[email-masked]>
Date: Mon, 07 Aug 95 17:20:47 -0700

Internet Engineering Task Force                   Integrated Services WG
INTERNET-DRAFT                                   S. Shenker/C. Partridge
draft-ietf-intserv-guaranteed-svc-01b.txt                 Xerox/BBN
                                                             August 1995
                                                        Expires: 1/1/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 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. 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.

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

   This memo defines a guaranteed service.  In particular, it defines
   requirements for network elements that support this service.  It
   follows the service template specified in RFC XXX.  Readers should
   refer to that document for additional details about the specification
   of qualities of service for IP internetworks.

Motivation

   This service is designed for applications which are intolerant of any
   queueing 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, provided the flow traffic stays within its bounds.

   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 does not minimize the jitter (the difference between the
   minimal and maximal) packet delays; it merely controls the maximal
   delay.  Therefore, 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.
Provided Service

   The end-to-end service provided by service elements that conform to
   this document is an assured bandwidth service which, 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 service conforms to the fluid model (described below) to within
   the specified error bounds.  The end-to-end delay bound is
   b/R+Ctot/R+Dtot (where b, R, Ctot, and Dtot are defined later in this
   document).

   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

Shenker/Partridge            Expires 1/1/96                     [Page 2]

INTERNET-DRAFT  draft-ietf-intserv-guaranteed-svc-01b.txt     August 1995

   applications should be prepared to receive packets that arrive well
   before the delay bound.

Network Element Data Handling Requirements

   The network element must ensure that the service approximates the
   "fluid model" of service.  The fluid model simply assumes that a
   flow's service is completely independent of that of any other flow.
   Another way of expressing this idea is that the service provided to a
   flow of bandwidth R by a perfect implementation of the fluid model
   would be indistinguishable from the service provided if the flow were
   given a dedicated wire of bandwidth R between the source and
   receiver.

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

Invocation Information

   Service is invoked by specifying the traffic (TSpec) and the desired
   service (RSpec) to the network element.  A service request for an
   existing flow which has a new TSpec and 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 (their new TSpec is
   strictly smaller than the old TSpec 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 minimum packet
   size.  The token bucket has a bucket depth, b, and a bucket rate, r.
   Both b and r must be positive.  The minimum packet size, p,  is an

Shenker/Partridge            Expires 1/1/96                     [Page 3]

INTERNET-DRAFT  draft-ietf-intserv-guaranteed-svc-01b.txt     August 1995

   integer measuring in bytes the size of the minimum-sized IP datagram
   the flow may send.

   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
   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 floating point numbers in
   single-precision IEEE floating point format followed by a 16-bit
   integer in network byte order.  The first value is the rate (r), the
   second value is the bucket size (b), and the third is the minimum
   packet size.  Minimum packet sizes of less than 20 (the minimum IP
   datagram size) are also errors.

   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.

Exported Information

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

Shenker/Partridge            Expires 1/1/96                     [Page 4]

INTERNET-DRAFT  draft-ietf-intserv-guaranteed-svc-01b.txt     August 1995

   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.

   If the 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 (downstream towards receivers) are handed to
   each network element then these network elements can compute the
   buffer allocations necessary to achieve no packet loss.  We assume
   that usage of guaranteed service will be primarily in contexts where
   these quantities are made available to end nodes and network
   elements.  Therefore, this service requires that the quantities Ctot
   and Dtot, and the quantities Csum and Dsum be computed.

   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 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
   (Dsum) is numbered 6.

Policing

   Policing is done at the edge of the network, at all source split
   points and at all source merge points.  A source split point is a
   spot where the multicast distribution tree from a source branches to

Shenker/Partridge            Expires 1/1/96                     [Page 5]

INTERNET-DRAFT  draft-ietf-intserv-guaranteed-svc-01b.txt     August 1995

   multiple distinct paths.  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 is done in two different ways.  At the edge of the network,
   non conforming packets are dropped.  Inside the network, traffic is
   reshaped, causing delay, and packets are only dropped if they cannot
   be reshaped.

   At the edge, packets not conforming to the token bucket are dropped.
   The traffic must obey the rule that for any time unit T, the amount
   of data sent cannot exceed rT+b, where r and b are the token bucket
   parameters.

   Inside the network, this approach does not produce the desired
   results, because queueing effects will typically cause a flow's
   traffic to become more bursty.  So inside the network, service
   elements must shape traffic before applying the token bucket test.

   In theory, shaping is done by combining a buffer with a token bucket
   regulator and buffering data until it can be sent in conformance with
   the token bucket parameters.  (Note that the token bucket regulator
   should start with its token bucket full).  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, and may drop all traffic
   which exceeds this buffer.

   Policing points may also choose to police packet sizes.  Since the
   primary purpose of the minimum packet size is to bound overhead and
   packet per second rates, the policing function is to count the number
   of packets received per time T, and ensure it does not exceed
   (rT+b)/p.  Note that this rule will permit packets of size smaller
   than p (which may occur due to fragmentation inside the network), but
   ensures that the packet rate and header overhead will not exceed the
   maximum that any service element may expect.

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.

Shenker/Partridge            Expires 1/1/96                     [Page 6]

INTERNET-DRAFT  draft-ietf-intserv-guaranteed-svc-01b.txt     August 1995

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

   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.

   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 packet size.
   (Beware of situations where the minimum packet size is close to or
   larger than the link MTU.  Fragmented packets result in increased
   header rates).  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/p)*(8+52))

   which represents the rate divided into 48-byte cells multiplied by

Shenker/Partridge            Expires 1/1/96                     [Page 7]

INTERNET-DRAFT  draft-ietf-intserv-guaranteed-svc-01b.txt     August 1995

   the 5-byte ATM header, plus the maximum packet rate (r/p) 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 p is small, since ATM wastage
   is usually much less than 52 bytes.  (ATM implementors should be
   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).

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) [1], Jitter-
   EDD [2], Virtual Clock [3] and a scheme proposed by IBM [4].  A nice
   theoretical presentation that shows these schemes are part of a large
   class of algorithms can be found in [5].

 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.

Shenker/Partridge            Expires 1/1/96                     [Page 8]

INTERNET-DRAFT  draft-ietf-intserv-guaranteed-svc-01b.txt     August 1995

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.

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

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

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

   5. 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 1/1/96                     [Page 9]

---

From: [email-masked] (Bruce Davie)
Date: Tue, 8 Aug 1995 16:21:25 -0400

A few comments...

>   prohibited.  Exponents greater than 162 (i.e., positive 35) are

This seems unnecessarily confusing. Why not just say:

   For all IEEE floating point values, the sign bit must be zero. (All
   values must be positive). Values outside the ranges recommended
   above are discouraged.

>   elements must shape traffic before applying the token bucket test.

I don't think this is quite right. First of all, I'd prefer not to
shape if I don't need to (why add the delay), second, I don't
understand how to shape without applying the token bucket test first
anyway. However, the next paragraph looks correct. So, I think you
should change the last sentence to:
 
   So inside the network, service elements must attempt to reshape
   non-conforming traffic until it conforms to the specified token
   bucket. 

That then flows nicely into the next paragraph.

>   RSpec's are ordered by their numerical values, with larger being

This is actually a general comment: should we be giving rules that
tell you how to add up Tspecs? For example, how does the application
writer know that if he wants to reserve for three audio streams
sharing one reservation that he needs to use a Tspec that sums the r
and b values of the three component streams? Does it go in the service
spec,  and if not, where?

Bruce

---

From: John Wroclawski <[email-masked]>
Date: Tue, 8 Aug 1995 17:56:02 -0400

From: [email-masked] (Bruce Davie)

   A few comments...

Even this seems weird to me. The range, etc should be specified
independently of the specific number format, since the specific number
format is only a recommendation. So why is this here at all? You've
already (I hope) told me the minimum and maximum legal values of the
parameter.

In this example you mean Rspecs, don't you?

If I remember correctly the spec template document calls for a
discussion of adding Xspecs in this section, as well as of ordering
and merging them.

			-john

---

From: Craig Partridge <[email-masked]>
Date: Tue, 08 Aug 95 15:08:23 -0700

Well, two things.  JJ suggested we put some guidance in -- sorry I did
a poor job of it.  But I think, in general, he's right.  We should be
certainly clear about exceptional cases.  So we should state explicitly
that negative numbers are forbidden.  Zero is forbidden (currently).
Both represent protocol errors when using IEEE floating point.

Craig

---

From: John Wroclawski <[email-masked]>
Date: Tue, 8 Aug 1995 18:45:16 -0400

From: Craig Partridge <[email-masked]>

Craig,

Sorry, I guess I was being unclear.

If a parameter (rate, say) is not allowed to have zero or negative
values, then those values represent protocol errors whether or not
you're using IEEE floating point. So the guidance should be in the
basic parameter description, not as a limit placed on one particular
representation.

You weren't meaning to imply that zero or negative IEEE FP values were
always going to be an error, were you?  It certainly isn't the case
that no parameter will ever take a zero or negative value, though it
happens to be true in this particular service spec.

		-john