Internet Draft
Internet Draft J. Wroclawski
Expires September, 2000 MIT LCS
draft-ietf-issll-ds-map-00.txt A. Charny
Cisco Systems
March, 2000
Integrated Service Mappings for Differentiated Services Networks
Status of this Memo
This document is an Internet Draft and is in full conformance with all
provisions of Section 10 of RFC2026. 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.
Internet Drafts may be updated, replaced, or obsoleted by other
documents at any time. It is not appropriate to use Internet Drafts as
reference material or to cite them other than as a "working draft" or
"work in progress."
The list of current Internet-Drafts can be accessed at
http://www.ietf.org/ietf/1id-abstracts.txt
The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html.
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.ietf.org (US East Coast), nic.nordu.net (Europe),
ftp.isi.edu (US West Coast), or munnari.oz.au (Pacific Rim).
This document is a product of the ISSLL working group of the Internet
Engineering Task Force. Please address comments to the group's mailing
list at issll@mercury.lcs.mit.edu, with a copy to the authors.
Copyright (C) The Internet Society (1999). All Rights Reserved.
Abstract
This document describes mappings of IETF Integrated Services onto IETF
differentiated services networks. These mappings allow appropriately
engineered and configured differentiated service network clouds to play
the role of "network elements" in the Integrated Services framework, and
thus to be used as components of an overall end-to-end Integrated
Services QoS solution.
1. Introduction
The IETF Integrated Services framework [INTSERV] defines mechanisms and
interfaces for providing network Quality of Service control useful for
applications that require more predictable network service than is
available with the traditional best-effort IP delivery model. Provision
of end-to-end QoS control in the Intserv model is based on the
concatenation of "network elements" along the data transmission path.
When all of the concatenated network elements implement one of the
defined Intserv "services" [G,CL], the resulting data transmission path
will deliver a known, controlled QoS defined by the particular Intserv
service in use.
The IETF Differentiated Services framework [DIFFSERV] defines a number
of mechanisms for differentiating different traffic streams within a
network and providing different levels of delivery service to those
different streams. These mechanisms include differentiated per-hop
queuing and forewarding behaviors, as well as behaviors such as traffic
classification, metering, policing and shaping that are intended to be
used at the edge or boundary of a diffserv cloud. Crucially, the
Differentiated Services framework manages traffic forwarding behavior
within a diffserv cloud at the aggregate level, rather than the
per-application-flow level.
The availability of Differentiated Services per-hop and cloud-edge
behaviors, together with additional mechanisms to statically or
dynamically limit the absolute level of traffic within a traffic class,
allows an IETF Differentiated Services network cloud to act as a network
element within the Integrated Services framework. In other words, an
appropriately designed, configured and managed Diffserv network cloud
can act as one component of an overall end-to-end QoS controlled data
path using the Integrated Services framework, and therefore support the
delivery of Intserv QoS services.
This document is one of a set that together describe the usage of
Differentiated Services networks in this manner. This document
describes methods for implementing Intserv using Diffserv network
behaviors and mechanisms. Companion documents [RSVPAGGR, DCLASS] define
extensions to the RSVP signaling protocol [RSVP] that are useful in this
environment.It is recommended that readers be familiar with the overall
framework in which these mappings and protocols are expected to be used;
this framework is described fully in [ISDSFRAME].
Within this document, Section 2 describes the overall approach and
discusses issues that are independent of the class of Intserv service
being implemented. Section 3 discusses implementation of the Controlled
Load service. Section 4 discusses implementation of a mathematically
correct Guaranteed service, and presents information about the
performance and limitations of this implementation. Section 5 discusses
implementation of close approximations to the Guaranteed service that
may be acceptable in some circumstances and may allow more efficient use
of network resources. Section 6 briefly describes the relationship of
the mechanisms described here to the Intserv Null Service [NULL].
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
document are to be interpreted as described in RFC 2119.
2. Basics
2.1. Components
Figure 1 shows the basic use of a Diffserv network cloud as an Intserv
network element.
Figure 1
The figure shows that required Intserv network element functions are
mapped to the Diffserv cloud as follows:
- Traffic scheduling. The Intserv traffic scheduling function is
supported by appropriately selected, configured, and provisioned PHB's
within the Diffserv network. These PHB's, when concatenated along the
path of traffic flow, must provide a scheduling result that adequately
approximates the result defined by the Intserv service.
In general, the PHB concatenation will only be able to approximate the
defined Intserv service over a limited range of operating conditions
(level of traffic, allocated resources, and the like). In that case,
other elements of the network, such as shapers and policers, must
ensure that the traffic conditions seen by the PHB's stay within this
range.
- Traffic classification. The Intserv framework requires that each
network element (re)classify arriving traffic into flows for further
processing. This requirement is based on the architectural assumption
that network elements should be independent, and not depend on other
network elements for correct operation.
NOTE: the Intserv framework does not specify the granularity of a
flow. Intserv is often associated with per-application or
per-session end-to-end flows, but in fact any collection of packets
that can be described by an appropriate classifier can be treated as
an Intserv traffic flow.
When Intserv is mapped to Diffserv, packets must be classified into
flows, policed, shaped, and marked with the appropriate DSCP before
they enter the interior of the diffserv cloud. Strictly speaking, the
independence requirement stated above implies that the ingress
boundary router of each diffserv cloud must implement a MF classifier
to perform the classification function. However, in keeping with the
diffserv model, it is permissible to push the flow classification
function further towards the edge of the network if appropriate
agreements are in place. For example, flows may be classified and
marked by the upstream edge router if the Diffserv network is prepared
to trust this router.
- Policing and shaping. In terms of location in the network, these
functions are similar to traffic classification. A strict
interpretation of the Intserv framework would require that the ingress
boundary router of the diffserv cloud perform these functions. In
practice, they may be pushed to an upstream edge router if appropriate
agreements are in place.
Note that moving the shaping function upstream of the diffserv ingress
boundary router may result in poorer overall QoS performance. This is
because if shaping is performed at the boundary router, a single
shaper can be applied to all of the traffic in the service class,
whereas if the shaping is performed upstream separate shapers will be
applied to the traffic from each upstream node. As discussed further
in Section 4, the single shaper may be preferable in some
circumstances.
- Admission control. The quantitative Intserv services (Guaranteed and
Controlled Load) require that some form of admission control limit the
amount of arriving traffic relative to the available resources. Two
issues are of interest; the method used by the diffserv cloud to
determine whether sufficient resources are available, and the method
used by the overall network to query the diffserv cloud about this
availability.
Within the cloud, the admission control *mechanism* is closely related
to resource allocation. If some form of static resource allocation
(provisioning) is used, the admission control function can be
performed by any network component that is aware of this allocation,
such as a properly configured boundary router. If resource allocation
within the network cloud is dynamic (a dynamic "bandwidth broker" or
signaling protocol) then this protocol can also perform the admission
control function, by refusing to admit new traffic when it determines
that it cannot allocate new resources to match.
The admission control *mechanism* used is independent of the admission
control *algorithm* used to determine whether sufficient resources are
available to admit a new traffic flow. The algorithm used may range
from simple peak-rate allocation to a complex statistical
measurement-based approach. The choice of algorithm is dependent on
the Intserv service to be supported. Admission control algorithms
appropriate for each service are discussed in the service
specific sections below.
The admission control mechanism used within the diffserv cloud is also
independent of the mechanism used by the outside world to request
service from the cloud. As an example, end-to-end RSVP might be used
together with any form of interior admission control mechanism -
static provisioning, a central bandwidth broker, or aggregate RSVP
internal signalling.
2.2. Per-Cloud versus Per-Path Control
The key to providing absolute, quantitative QoS services within a
diffserv network is to ensure that at each hop in the network the
resources allocated to the PHB's used for these services are sufficient
to handle the arriving traffic. As described above, this can be done
through a spectrum of mechanisms ranging from static provisioning to
dynamic per-hop signaling within the cloud. Two situations are
possible:
- With per-cloud provisioning, sufficient resources are made available
in the network so that traffic arriving at an ingress point can flow
to *any* egress point without violating the PHB resource allocation
requirements. In this case, admission control and traffic management
decisions need not be based on destination information.
- With per-path provisioning, resources are made available in the
network to ensure that the PHB resource allocation requirements will
not be violated if traffic arriving at an ingress point flows to one
(in the unicast case) specific egress point. This requires that
admission control and resource allocation mechanisms take into account
the egress point of traffic entering the network, but results in more
efficient resource utilization.
Two points are important to note:
- Both approaches are valuable, but all functions must adopt the same
approach. Particularly, if resource allocation is per-path, traffic
shaping and policing, and hence classification must be destination
aware as well.
- The per-cloud vs per-path decision is independent of decisions about
static vs. dynamic provisioning. It is often assumed that dynamic
provisioning is necessarily per-path, while static provisioning is
more likely to be per-cloud. In reality, all four options may be
useful in differing circumstances.
3. Implementation of the Controlled Load Service
3.1. Summary of CL Requirements
The essence of the Controlled Load service is that traffic using it
experiences the performance expected of an unloaded network. The CL
specification [CL] refines this definition.
- Controlled Load traffic is described by a token bucket Tspec. When
traffic is conformant to the Tspec, network elements will forward it
with queuing delay not greater than that caused by the traffic's own
burstiness - that is, the result of the source emitting a burst of
size B into a logical network with capacity R. Further, in doing this
no packets will be discarded due to queue overflow. Statistically
rare deviations from this ideal behavior are permitted. A measure of
the "quality" of a CL service is how rare these deviations are.
NOTE: the actual behavior requirements stated in the CL spec are
slightly more detailed than what is presented here.
- Network elements must not assume that that arrival of nonconformant
traffic for a specific controlled-load flow will be unusual, or
indicative of error. In certain circumstances large numbers of
packets will fail the conformance test *as a matter of normal
operation*. Some aspects of the behavior of a CL network element in
the presence of nonconformant traffic are specified.
(These circumstances include elements carrying traffic from adaptive
applications that use the CL service to provide a floor on performance
but constantly try to do better, elements acting as the "split points"
of a multicast distribution tree or carrying multi-source aggregate
flows, such as those generated by RSVP's wildcard or shared-explicit
reservation styles supporting a shared reservation).
In the presence of nonconformant packets arriving for one or more
controlled-load flows, each network element must ensure locally that
the following requirements are met:
1) The network element MUST continue to provide the contracted
quality of service to those controlled-load flows not experiencing
excess traffic.
2) The network element SHOULD prevent excess controlled-load
traffic from unfairly impacting the handling of arriving best-
effort traffic.
3) Consistent with points 1 and 2, the network element MUST attempt
to forward the excess traffic on a best-effort basis if sufficient
resources are available.
These points lead to two observations about a well implemented CL service.
- CL traffic can be sorted into "delay classes" based on burstiness.
Highly bursty flows, having a large ratio of Tspec parameters B/R,
should expect to experience more queuing delay than their
low-burstiness counterparts. Thus, a good CL implementation will sort
the offered CL traffic into sub-classes that are expecting roughly
equivalent delay, and queue these subclasses independently to achieve
this result.
- The CL specification leaves open the precise treatment of
nonconformant traffic, giving only the minimum requirements listed
above.
NOTE: The phrase "best effort basis" in the portion of the CL spec
quoted above has sometimes been taken to mean "the traffic must be
placed in the best effort traffic class and treated identically to
BE traffic". This interpretation is incorrect. It is easy to see
this at one level, because if nonconformant CL traffic from
non-adaptive applications is simply lumped in with adaptive
best-effort traffic it will tend to unfairly impact that traffic, in
contravention of point 2). However, the intent of the specification
is more general. An appropriate reading is "nonconformant CL
traffic should be transmitted, when possible, in the way that is
most advantageous to users and applications, subject to the
requirements on non-interference with other traffic". This allows
the CL service to be used both to provide a specific QoS for
non-adaptive applications and as to provide a "floor" or minimum QoS
for adaptive applications.
3.2. Implementation of CL using the AF Per-Hop Behavior
The CL service can be supported most effectively using an appropriately
designed and configured Assured Forwarding PHB implementation [AF] as
the data forwarding element. This approach SHOULD be used whenever
possible.
The basics of the AF-based approach are as follows:
- Sort the offered CL traffic into delay classes based on the B/R
ratio of the Tspec. The packets of each delay class will be forwarded
using a separate instance of the AF PHB.
- For each delay class, construct an aggregate Tspec for the admitted
traffic according to the rule for summing Tspecs given in [CL]. This
Tspec will be used to police the traffic for conformance at the
ingress to the diffserv cloud.
- For each delay class, police arriving packets against the token
bucket Tspec derived above. Mark conforming packets with a DSCP
indicating the selected AF instance, and highest priority forwarding
within that instance. Mark nonconformant packets with a DSCP
indicating the selected AF instance, and lowest priority forwarding
within that instance.
- At each node within the diffserv network, configure each AF instance
appropriately by:
a) setting the actual queue size (or alternatively the dropping
parameters for high priority packets) to limit queuing delay to the
delay class's target. (In other words, packets that have been
delayed beyond the class target should be dropped).
b) setting the dropping parameters for low priority packets to drop
such packets as soon as any significant non-transient queuing of
these packets is detected.
c) setting the service rate of the AF instance to a bandwidth
sufficient to meet the delay and loss behavior requirements of the
CL spec when only high-priority packets are present.
- Implement an admission control algorithm that ensures that at each
hop in the network the level of conformant traffic offered to each AF
instance is equal to or less than that provisioned for in step 4c
above (or alternatively dynamically allocates more bandwidth to the
relevant AF instance when required).
In addition to these basic actions, two subtleties with the use of AF
must be observed.
First the relationship between different AF instances, and between AF
and other PHBs, must be more tightly constrained than is required by the
the base AF specification.
- Bandwidth should be allocated between AF and BE (and any other
relevant PHB's) in such a way that AF cannot simply steal all
best-effort bandwidth on demand. A simple WFQ or CBQ scheduler can
meet this requirement.
- The bandwidth allocation relationship between different AF instances
must be known. Two likely relationships are
o Bandwidth is allocated to each AF instance independently, as with
a WFQ scheduler.
o Bandwidth is allocated across the AF instances used for CL service
on a priority basis, with the AF instance supporting the lowest
delay class of CL having the highest priority.
Either of these approaches may be used. However the choice of approach
affects the admission control decision, and must be taken into account.
In the first case, admission control decisions may be made for each CL
delay class independently. In the second case, admission control
decisions for high priority classes will affect lower priority classes,
which must be taken into account.
The second subtlety is that the implementation of AF must service the AF
classes in a timely manner, by ensuring that the bandwidth allocated to
an AF instance is made available at a time-scale substantially shorter
than the delay target of the class. This requirement is slightly
stronger than that stated in the AF specification. In practice, any
implementation using a common queuing algorithm is likely to be able to
meet this requirement unless other PHB's, such as EF, are served at
higher priority. When that is true, the traffic seen by the higher
priority PHB will also require limiting and shaping in order to ensure
that the CL AF instances receive bandwidth on a timely basis.
The overall result of this procedure is an implementation of the CL
service with the following characteristics:
- Conformant CL traffic is carried according to the CL requirements.
- Resources are used efficiently by aggregating traffic with similar
requirements, but supporting multiple delay classes for traffic with
widely differing requirements.
- Non-CL traffic is carried whenever resources permit, and is not
reordered with respect to the CL flow's conformant traffic.
- Nonconformant CL traffic is not able to disrupt traffic of other
classes, particular BE.
3.2.1 CL/AF Admission Control Approaches
3.3. Implementation of CL using the EF Per-Hop Behavior
It is also possible to implement an approximation of the Controlled Load
service using the Diffserv Expedited Forwarding [EF] PHB as the traffic
scheduling element. This approach is not preferred, because of two
significant limitations. Therefore, this approach SHOULD NOT be used
unless the AF-based approach is not available.
- Because there is only one EF scheduling class per node, it is
impossible to sort the Controlled Load traffic into queuing delay
classes, as described above for the AF implementation. Instead, all
CL traffic must be handled as one scheduling class, and sufficient
resources must be allocated to the class to cause *all* CL traffic to
meet the queuing delay expectations of the most demanding flows.
- Because the EF PHB requires a hard limit on the amount of traffic
passing through it, a CL service implemented using EF cannot handle
nonconformant (over-Tspec) traffic gracefully, as can be done with AF.
Instead, nonconformant traffic must either be discarded at the ingress
of the Diffserv cloud or remarked into a different behavior aggregate,
and thus potentially reordered in transit. Either of these behaviors
is less desirable than the one obtained from the AF-based
implementation above.
Notwithstanding these limitations, it may be useful to implement a CL
approximation based on the EF PHB when the Diffserv network does not
support the AF PHB, or when the implementation of the AF PHB cannot
assure the forwarding of traffic in a sufficiently timely manner. In
this case:
- All CL traffic is marked with a DSCP corresponding to the EF PHB.
- A single aggregate Tspec for all CL traffic is computed for each
network ingress.
- Arriving CL traffic is policed against this Tspec, and nonconformant
traffic is either discarded or remarked as BE, at the preference of
the network operator.
- At each hop within the network the EF PHB must receive a bandwidth
allocation sufficient to meet the requirements given in the EF
specification when the arriving CL traffic is at the Tspec level for
that point within the network.
- The topology of the network must be designed so that the
instantaneous queuing delay caused by fan-in to a node will exceed the
CL requirements rarely or never. In practice, this will be a concern
only with very high fan-in topologies.
4. Implementation of the Guaranteed Service
The Guaranteed service [G] offers a strict mathematical assurance of
both throughput and queuing delay, assuming only that the network is
functioning correctly. A key concept of the Guaranteed service is that
"error terms", referred to as C and D in the specification, are provided
by the network element to the customer, allowing the customer to
calculate the bandwidth it must request from the network in order to
achieve a particular queuing delay target. Thus, the two important
tasks in implementing a Guaranteed service network element are providing
the traffic scheduling, policing, and shaping functions needed to
support a hard bound on performance, and characterizing the network
element's error terms so that the customer of the service can accurately
characterize the network path and deduce what level of resources must be
requested.
Our strategy for implementing these capabilities within a diffserv cloud
revolves around the use of the EF PHB for Guaranteed traffic, together
with the shaping and policing functions necessary to obtain a
performance bound in this context. The basic traffic policing and
shaping requirements for Guaranteed service are discussed more fully in
the service specification.
Delay through a Diffserv cloud can be roughly classified into
propagation and serialization delay, shaping/reshaping delays at the
boundary, and queuing delay inside the cloud. In order to determine the
error terms C_dc and D_dc for the Diffserv cloud needed for end-to-end
determination of end-to-end delay, each of these delay components need
to be evaluated. The difficulty in characterizing C_dc and D_dc is that
unlike the Intserv model, where the C and D terms are a local property
of the router, in the case of Diffserv cloud these terms depend not only
on the topology of the cloud, but also on the internal traffic
characteristics of potentially _all_ EF traffic in the cloud.
Hence, the existence of upper bounds on delay through the cloud implies
centralized knowledge about the topology of the cloud and traffic
characterization. In turn, dependence of the delay bounds on traffic
characterization at any ingress point to the cloud implies the existence
of a policy that defines traffic characterization rules, as well as
implementation mechanisms at _all_ ingress points in the network that
enforce that policy.
These considerations imply that determination of the bound on the delay
through the Diffserv cloud should be performed off-line, perhaps as part
of a traffic management algorithm, based on the knowledge of the
topology, traffic patterns, shaping policies, and other relevant
parametersof the cloud. These parameters are discussed in the following
sections with respect of each delay component.
Once the delay bounds and determined, the corresponding error terms C_dc
and D_dc are configured into the appropriate intserv-capable edge
routers, as discussed below.
4.1 Propagation and Serialization Delay.
These delay components can be bounded by modeling the Diffserv cloud as
a sequence of at most h links, each of which of at most length C. The
parameters (h, C) determine the so-called "diameter" of the cloud. The
knowledge of this diameter can then be used to obtain upper bounds on
the propagation and serialization delay through the cloud.
4.2 Shaping delay.
The Diffserv EF PHB assumes that traffic entering the Diffserv region is
conditioned at the Diffserv cloud boundary. In the framework of Figure
1, shaping is expected to take place at the ingress edge router ER1, and
optionally at the boundary router BR1. Granularity of such shaping is
implementation dependent, and can range from microflow shaping to
aggregate shaping. The granularity of aggregation can be "all EF
traffic between a particular ingress-egress pair", which is frequently
referred to as "pipe model", or "all EF traffic originating at a given
ingress to all possible destinations", which is frequently referred to
as "hose model".
In addition to ingress shaping, the Diffserv model allows re-shaping
traffic at the egress point. As for the case of ingress shaping, the
egress shaping can be implemented either at BR2 or ER2.
The effect of different choices of the location and granularity of
shaping on the delay guarantees that can be provided by a Diffserv cloud
will be discussed in section ??. In this section we consider the effect
of this choices on the C and D terms advertised by the Interv-capable
routers ER1 and ER2. Note that the Intserv capable router downstream
from the Diffserv cloud (ER2 in the reference network of Figure 1) is
responsible for exporting the C and D terms of the Diffserv cloud.
4.2.1. Shaping at the Edge Routers
If shaping is performed at the ingress edge router ER1, and reshaping,
if any, is performed at ER2, but there is no shaping implemented inside
the Diffserv cloud, the shaping/reshaping delay is part of the total
delay advertised by the edge routers ER1 and ER2, and hence the
corresponding C and D terms are exported by the Intserv-capable edge
routers. These will be denoted as C_is, D_is, C_es, D_es respectively,
where the indices _is and _es denote "ingress shaper" and "egress
shaper". The values of these parameters are implementation dependent.
Since the Diffserv cloud itself does not perform any shaping in this
case, its C_dc should be set to zero. The determination of the value of
D_dc and factors affecting it are discussed in section 4.4 below.
4.2.2 Shaping at the boundary routers
In the case where shaping is performed by the boundary routers, shaping
and reshaping delay become part of the delay of the Diffserv cloud and
hence have to be accounted for in the C_dc and D_dc error terms. Note
that depending on the shaping implementation, the rate-dependent error
term may not necessarily be zero, and hence ingress shaping may add a
non-zero component to the C_dc value of the Diffserv cloud.
Since the ingress shaping delay depends on the shaping implementation
and shaping granularity at the border router, and since different border
routers may implement different shaping algorithms, it seems natural to
dedicate the responsibility to export the error terms for ingress
shaping delay to the ingress edge router(s) attached to the border
router.
It is important to note that in the case of aggregate shaping, the
shaping delay may be a function of the combined burst and combined rate
of all microflows comprising the shaped aggregate (note that the
aggregate may consist of microflows arriving from different ingress
points).
To enable an existence of a meaningful upper bound on the shaping delay
the shapers at the edge routers must be configured in such a way as to
ensure the existence of the bound on the shaping delay at the boundary
router. This may be accomplished by emposing a policy such as "token
bucket parameters of all flows requiring G support entering the diffserv
cloud from any edge router should satisfy the condition (r>=r_min,
b<=b_max). Such conditions would enable token bucket characterization
of the aggregate stream, which in combination with the properties of the
shaping implementation would enable the computation of an upper bound
for a particular microflow.
If the egress boundary router implements reshaping on an aggregate
basis, just as in the case if ingress shaping, the egress reshaping
delay of a microflow depends on the combined rate and burstiness of the
aggregate which is being reshaped. Aggregate burstiness depends, among
other things, on the parameters of ingress shapers and on the delay
bound of the diffserv cloud incurred by all microflows after the last
shaping point.
The C and D terms corresponding to the egress boundary shaping must be
configured at the egress edge router, which is responsible for exporting
the egress shaping component of the C and D terms of the Diffserv cloud.
In addition, just as in section 4.2.1, the egress edge router is
responsible for exporting the D_ds component of the delay inside the
diffserv cloud which is not due to the shaping or reshaping delays.
4.2.3. Shaping inside the Diffserv cloud
While the Diffserv model does not prevent shaping inside the cloud as
well as at the boundaries, this draft will concentrate on the most
common case when all internal interfaces of any node in the diffserv
cloud implement work-conserving aggregate class-based scheduling only.
4.3 Queuing delay
Queuing delay experienced by a given packet is caused by two reasons:
contention with other packets in the scheduler and the interruption of
service experienced by the scheduler as a whole. A typical example of
the latter is the delay in a single processor system when the processor
schedules some tasks other than packet scheduler. If a bound on this
latter portion of the delay is known for all routers inside the diffserv
cloud, then the contribution of this delay component can be bounded by
multiplying this bound by the max hop count h.
The component of the queuing delay due to contention with other packets
in the link scheduler will be discussed in detail in section 4.4. For
the sake of brevity, in the rest of this draft the term queuing delay
will be used to refer to just the portion of the queuing delay due to
contention with other packets in the scheduler.
4.4. Queueing delay bounds in the Diffserv Cloud
The main difficulty in obtaining hard delay bounds for an arbitrary
topology cloud arises from the assumption of aggregate scheduling inside
the cloud. When a packet of some flow f traverses a sequence of
aggregate queues, its worst case delay may depend on the traffic of
other flows which do not even share a single queue with the flow.
Moreover, the delay of a packet p of flow f at time t may be affected by
flows whose last packets have exited the network long before the first
packet of flow f entered the network [CHARNY].
The ability to provide hard delay bounds in a Diffserv cloud with
aggregate scheduling must rely on cooperation of all devices in the
cloud, as well as strict constraints on the traffic entering the cloud.
It has been demonstrated that the knowledge of the following parameters
global to the cloud is essential for the ability to provide strict
queuing delay guarantees across the Diffserv cloud [CHARNY],[LEBOUDEC]:
- limited number of hops of any flow across the cloud (denoted h)
- low (bounded) ratio of the load of EF traffic to the service rate of
the EF queue on any link in the cloud (denoted u)
- minimum rate of the shaped aggregate (denoted r_min)
- maximum token bucket depth of an edge-to-edge aggregate (denoted
b_max)
- minimum service rate of the EF queue (denoted S)
- maximum deviation of the amount of service of the EF queue from the
ideal fluid service at rate S (denoted E)
Currently, the only known delay bound that holds for an arbitrary
topology and arbitrary route distribution is given in [LeBouldec] by
D = (E/S + ub_max/r_min)x h/(1-u(h-1))
which holds for any utilization u<1/(h-1). This bound holds for the
case when the capacity of any single link is substantially smaller than
the total capacity of all interfaces of any router. (This bound may be
slightly improved if the capacity of a single link is not negligible
compared to the total router capacity [LeBouldec]). Unfortunately, this
bound explodes when u=1/(h-1).
Some knowledge on either the topology or the routes in the cloud may
yield to an improved bound. For example, for a class of network
topologies which includes a multistage network it can be shown [CHARNY]
that the bound is given by
D = (E/S + ub_max/r_min)x((1+u)^h-1)/u
While this bound holds for any utilization, due to the exponential term
the delay grows very fast with the increase in utilization u.
Unfortunately, at the moment no bound is known for a general topology
with utilization greater than 1/(h-1). It can be shown [CHARNY], that
for utilization values greater than 1/(h-1), for any value of delay D
one can always construct a network such that the delay in that network
is greater than D. This implies that either no bound exists at all, or
if a bound does exist, it must depend on some additional characteristics
of the network other than just h and u.
The practical implication of these results is that, barring new results
on delay bounds, the amount of traffic requiring end-to-end Guaranteed
service across the diffserv cloud should be rather small. Furthermore,
it also implies that if substantial amount of other EF traffic is
present in the network, in order to ensure strict delay bounds for GS
traffic, buffering and scheduling mechanisms must exist that ensure
separation of the GS traffic using EF PHB from other traffic using EF
PHB.
4.5. Relationship to Bandwidth Allocation Techniques and Traffic
Conditioning Models
4.5.1. Availability of sufficient bandwidth
As discussed in Section 4.4, in order to provide a strict delay bound
across the Diffserv cloud the ratio of the EF load to the service rate
of the EF queue has to be deterministically bounded on all links in the
network. This can be either ensured by signaled admission control (such
as using RSVP aggregation techniques [RSVPAGGR] or by a static
provisioning mechanism. It should be noted that if provisioning is
used, then to ensure deterministic load/service rate ratio on all link
the network should be strongly overprovisioned to account for possible
inaccuracy of traffic matrix estimates.
In either case deterministic availability of sufficient bandwidth on all
links is a necessary condition for the ability to provide deterministic
delay guarantees.
4.5.2. Effect of Shaping Granularity on Delay Bounds
A related, although different issue for the ability to provide delay
deterministic delay guarantees is the granularity of the ingress
shaping. The implications of different choices on the resulting delay
bounds are discussed in the following subsections.
4.5.2.1 Per-microflow shaping
The known worst case delay bound is linear in the ratio b_max/r_min. In
the case of microflow shaping, the minimal rate of the microflow can be
quite small, resulting in a large delay bound. There is a substantial
advantage therefore in aggregating many small microflows into an
aggregate and shaping the aggregate as a whole. While in principle
there is a range of choices for aggregation, this document will consider
only two: edge-to-edge aggregation and edge-to-everywhere aggregation.
4.5.2.2. Shaping of edge-to-edge aggregates
This type of shaping is natural for explicit bandwidth reservation
techiques. In this case r_min and b_max relate to the rate and token
bucket depth of the border-to-border aggregates. Since the delay bound
is linear in b_max/r_min, aggregating as many microflows sharing the
same border-to-border pair as possible results in the increase of r_min,
and hence in the decrease of the delay bound. The location of the
shaper at the border router is therefore beneficial for reducing the
edge-to-edge delay bound.
4.5.2.3. Shaping of edge-to-everywhere aggregates.
This type of shaping is frequently assumed in conjunction with bandwidth
provisioning. The effect of this choice on delay bounds depends on
exactly how provisioning is done. One possibility for provisioning the
network is to estimate edge-to-edge demand matrix for EF traffic and
ensure that there is sufficient capacity to accommodate this demand,
assuming that the traffic matrix is accurate enough. Another option is
to make no assumption on the edge-to-edge EF traffic distribution, but
rather admit a certain amount of EF traffic at each ingress edge,
regardless of the destination edge, and provision the network in such a
way that even if _all_ traffic from _all_ sources happens to pass
through a single bottleneck link, the capacity of that link is
sufficient to ensure the appropriate load to service rate ratio for the
EF traffic.
Depending on which of the two choices for provisioning is chosen,
shaping of the edge-to-everywhere aggregate has the opposite effect on
the delay bound.
In the case of "edge-to-edge provisioning", the bandwidth of any link
may be sufficient to accommodate the _actual_ load of EF traffic while
remaining within the target utilization bound. Hence, it is the minimal
rate and the maximum burst size of the _actual_ edge-to-edge aggregates
sharing any link that effect the delay bound. However, aggregate
edge-to-all shaping may result in individual substreams of the shaped
aggregate being shaped to a much higher rate than the expected rate of
that substream. When the edge-to-everywhere aggregate splits inside the
network into different substreams going to different destinations, each
of those substreams may have in the worst case substantially larger
burstiness than the token bucket depth of the aggregate
edge-to-everywhere stream. This results in substantial increase of the
worst case delay over the edge-to-edge shaping model. Moreover, in this
case the properties of ingress shapers do not provide sufficient
information to bound the worst case delay, since it is the burstiness of
the _substreams_ inside the shaped aggregates that is needed, but is
unknown.
In contrast, if the "worst case" provisioning is assumed, the network is
provisioned in such a way that each link can accommodate all the traffic
even if all edge-to-everywhere aggregates end up sharing this link. In
this case the r_min and b_max of the edge-to-everywhere aggregate should
be used without modification in the formula for the delay bound.
Intuitively, in this case the actual traffic distribution can only be
better than the worst case, in which all the aggregate traffic at a
given ingress is destined to the same "worst case egress".
Note that the "worst case" provisioning model targeting a particular
utilization bound results in substantially more overprovisioning than
the the "point-to-point" provisioning using an estimated traffic matrix,
or explicit point-to point bandwidth allocation using signaled admission
control.
4.6 Concatenation of Diffserv Clouds
In the case where one or more Diffserv clouds are concatenated via an
Intserv-capable node, the total delay is simply a concatenation of
delays computed for each individual intserv-diffserv-insterv segment
along the path. However, obtaining end-to-end delay bound for a
concatenation of Diffserv clouds via nodes implementing aggregate
scheduling is a more complicated problem which requires further
research.
5. Implementation of Resource Efficient Close Approximations to the
Guaranteed Service
6. Relationship to the Null Service
The Intserv "Null Service" [NULL] differs from other defined services by
not expressing any quantitative network performance requirements. Use
of the Null Service where an Intserv service class is required allows an
application or host requesting QoS control service to express policy
related information to the network without making a specific
quantitative QoS request. The assumption is that the network policy
management and control elements will use this information to select an
appropriate QoS for the requesting entity, and take whatever action is
required to provide this QoS.
One possibility is that the network policy mechanisms will determine
that a quantitative end-to-end QoS is appropriate for this entity, and
that this QoS can be provided using Intserv mechanisms. In this case,
the Null service selector can be replaced, at the first hop router or
elsewhere along the path, with a different Intserv service class and
related parameter information. Once this occurs, the situation with
respect to the use of Diffserv networks to provide the desired QoS is
identical to that described above for these other services.
A second alternative is that the network policy mechanisms determine
that the requesting entity should receive a relative, rather than
absolute (quantitative) level of service. In this case, the packets are
marked with the appropriate DSCP, but the admission control actions
described above are not necessary.
7. Security Considerations
8. References
[AF] Heinanen, J., Baker, F., Weiss, W., Wroclawski, J., "Assured
Forwarding PHB Group", RFC 2597, June 1999.
[CHARNY] Anna Charny, "Delay Bounds in a Network with Aggregate
Scehduling", work in progress,
ftpeng.cisco.com/ftp/acharny/aggregate_delay_v4.ps
[CL] Wroclawski, J., "Specification of the Controlled-Load Network
Element Service", RFC 2211, September 1997
[DCLASS] Bernet, Y., "Usage and Format of the DCLASS Object With RSVP
Signaling", Internet Draft draft-ietf-issll-dclass-00.txt
[DIFFSERV] Blake, S., Black, D., Carlson, M., Davies, E., Wang Z.,
Weiss, W., "An Architecture for Differentiated Service", RFC 2475,
December 1998.
[EF] Jacobson, V., Nichols, K., Poduri, K., "An Expedited Forwarding
PHB", RFC 2598, June 1999.
[G] Schenker, S., Partridge, C., Guerin, R., "Specification of
Guaranteed Quality of Service", RFC 2212 September 1997
[GENCHAR] Shenker, S., Wroclawski, J., "General Characterization
Parameters for Integrated Service Network Elements", RFC 2215, September
1997
[INTSERV] Clark, D. et al. "Integrated Services in the Internet
Architecture: an Overview" RFC1633, June 1994
[ISDSFRAME] Several hundred people, Internet Draft
draft-ietf-issll-diffserv-rsvp-03.txt
[LEBOUDEC] Jean-Yves LeBoudec, "A Proven Delay Bound in a Network with
Aggregate Scheduling", work in progress,
http://ica1www.epfl.ch/PS_files/ds2.ps
[NULL] Bernet, Y., Smith, A., Davie, B., "Specification of the Null
Service Type", Internet Draft draft-ietf-issll-nullservice-00.txt
[RSVP] Braden, R., L. Zhang, S. Berson, S. Herzog, S. Jamin, "Resource
Reservation Protocol (RSVP) - Version 1 Functional Specification", RFC
2205, September 1997
[RSVPAGGR] Baker, F., Iturralde, C., Le Faucheur, F., Davie, B.,
"Aggregation of RSVP for IPv4 and IPv6 Reservations", Internet Draft
draft-ietf-issll-rsvp-aggr-02.txt
[RSVPINTSERV] Wroclawski, J., "The use of RSVP with IETF Integrated
Services", RFC 2210, September 1997.
9. Authors' addresses
John Wroclawski
MIT Laboratory for Computer Science
545 Technology Sq., Cambridge, MA 02139, USA
Phone: +1 617 253 7885
EMail: jtw@lcs.mit.edu
Anna Charny
Cisco Systems
250 Apollo Drive, Chelmsford, MA 01824, USA
Phone: +1 978 244 8000
Email: acharny@cisco.com
10. Full Copyright
Copyright (C) The Internet Society 1999. All Rights Reserved.
This document and translations of it may be copied and furnished
to others, and derivative works that comment on or otherwise
explain it or assist in its implementation may be prepared, copied,
published and distributed, in whole or in part, without
restriction of any kind, provided that the above copyright notice
and this paragraph are included on all such copies and derivative
works. However, this document itself may not be modified in any
way, such as by removing the copyright notice or references to the
Internet Society or other Internet organizations, except as needed
for the purpose of developing Internet standards in which case the
procedures for copyrights defined in the Internet Standards
process must be followed, or as required to translate it into
languages other than English.
The limited permissions granted above are perpetual and will not
be revoked by the Internet Society or its successors or assigns.
This document and the information contained herein is provided on
an "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET
ENGINEERING TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF
THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED
WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
draft-ietf-issll-ds-map-00.txt Expires September, 2000