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-
serv@isi.edu 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
shenker@parc.xerox.com
415-812-4840
415-812-4471 (FAX)
Craig Partridge
BBN
2370 Amherst St
Palo Alto CA 94306
craig@bbn.com
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]