as TCP.
- because a meter exceeds a configured profile (i.e., policing).
The queuing elements in this model represent a logical abstraction of
a queuing system which is used to configure PHB-related parameters.
The model can be used to represent a broad variety of possible
implementations. However, it need not necessarily map one-to-one
with physical queuing systems in a specific router implementation.
Implementors should map the configurable parameters of the
implementation's queuing systems to these queuing element parameters
as appropriate to achieve equivalent behaviors.
7.1. Queuing Model
Queuing is a function which lends itself to innovation. It must be
modeled to allow a broad range of possible implementations to be
represented using common structures and parameters. This model uses
functional decomposition as a tool to permit the needed latitude.
Queuing systems perform three distinct, but related, functions: they
store packets, they modulate the departure of packets belonging to
various traffic streams and they selectively discard packets. This
model decomposes queuing into the component elements that perform
each of these functions: Queues, Schedulers, and Algorithmic
Droppers, respectively. These elements may be connected together as
part of a TCB, as described in section 8.
The remainder of this section discusses FIFO Queues: typically, the
Queue element of this model will be implemented as a FIFO data
structure. However, this does not preclude implementations which are
not strictly FIFO, in that they also support operations that remove
or examine packets (e.g., for use by discarders) other than at the
head or tail. However, such operations must not have the effect of
reordering packets belonging to the same microflow.
Note that the term FIFO has multiple different common usages: it is
sometimes taken to mean, among other things, a data structure that
permits items to be removed only in the order in which they were
inserted or a service discipline which is non-reordering.
7.1.1. FIFO Queue
In this model, a FIFO Queue element is a data structure which at any
time may contain zero or more packets. It may have one or more
thresholds associated with it. A FIFO has one or more inputs and
exactly one output. It must support an enqueue operation to add a
packet to the tail of the queue and a dequeue operation to remove a
packet from the head of the queue. Packets must be dequeued in the
order in which they were enqueued. A FIFO has a current depth, which
indicates the number of packets and/or bytes that it contains at a
particular time. FIFOs in this model are modeled without inherent
limits on their depth - obviously this does not reflect the reality
of implementations: FIFO size limits are modeled here by an
algorithmic dropper associated with the FIFO, typically at its input.
It is quite likely that every FIFO will be preceded by an algorithmic
dropper. One exception might be the case where the packet stream has
already been policed to a profile that can never exceed the scheduler
bandwidth available at the FIFO's output - this would not need an
algorithmic dropper at the input to the FIFO.
This representation of a FIFO allows for one common type of depth
limit, one that results from a FIFO supplied from a limited pool of
buffers, shared between multiple FIFOs.
In an implementation, packets are presumably stored in one or more
buffers. Buffers are allocated from one or more free buffer pools.
If there are multiple instances of a FIFO, their packet buffers may
or may not be allocated out of the same free buffer pool. Free
buffer pools may also have one or more thresholds associated with
them, which may affect discarding and/or scheduling. Other than
this, buffering mechanisms are implementation specific and not part
of this model.
A FIFO might be represented using the following parameters:
Queue1:
Type: FIFO
Output: Scheduler1
Note that a FIFO must provide triggers and/or current state
information to other elements upstream and downstream from it: in
particular, it is likely that the current depth will need to be used
by Algorithmic Dropper elements placed before or after the FIFO. It
will also likely need to provide an implicit "I have packets for you"
signal to downstream Scheduler elements.
7.1.2. Scheduler
A scheduler is an element which gates the departure of each packet
that arrives at one of its inputs, based on a service discipline. It
has one or more inputs and exactly one output. Each input has an
upstream element to which it is connected, and a set of parameters
that affects the scheduling of packets received at that input.
The service discipline (also known as a scheduling algorithm) is an
algorithm which might take any of the following as its input(s):
a) static parameters such as relative priority associated with each
of the scheduler's inputs.
b) absolute token bucket parameters for maximum or minimum rates
associated with each of the scheduler's inputs.
c) parameters, such as packet length or DSCP, associated with the
packet currently present at its input.
d) absolute time and/or local state.
Possible service disciplines fall into a number of categories,
including (but not limited to) first come, first served (FCFS),
strict priority, weighted fair bandwidth sharing (e.g., WFQ), rate-
limited strict priority, and rate-based. Service disciplines can be
further distinguished by whether they are work-conserving or non-
work-conserving (see Glossary). Non-work-conserving schedulers can
be used to shape traffic streams to match some profile by delaying
packets that might be deemed non-conforming by some downstream node:
a packet is delayed until such time as it would conform to a
downstream meter using the same profile.
[DSARCH] defines PHBs without specifying required scheduling
algorithms. However, PHBs such as the class selectors [DSFIELD], EF
[EF-PHB] and AF [AF-PHB] have descriptions or configuration
parameters which strongly suggest the sort of scheduling discipline
needed to implement them. This document discusses a minimal set of
queue parameters to enable realization of these PHBs. It does not
attempt to specify an all-embracing set of parameters to cover all
possible implementation models. A minimal set includes:
a) a minimum service rate profile which allows rate guarantees for
each traffic stream as required by EF and AF without specifying
the details of how excess bandwidth between these traffic streams
is shared. Additional parameters to control this behavior should
be made available, but are dependent on the particular scheduling
algorithm implemented.
b) a service priority, used only after the minimum rate profiles of
all inputs have been satisfied, to decide how to allocate any
remaining bandwidth.
c) a maximum service rate profile, for use only with a non-work-
conserving service discipline.
Any one of these profiles is composed, for the purposes of this
model, of both a rate (in suitable units of bits, bytes or larger
chunks in some unit of time) and a burst size, as discussed further
in Appendix A.
By way of example, for an implementation of the EF PHB using a strict
priority scheduling algorithm that assumes that the aggregate EF rate
has been appropriately bounded by upstream policing to avoid
starvation of other BAs, the service rate profiles are not used: the
minimum service rate profile would be defaulted to zero and the
maximum service rate profile would effectively be the "line rate".
Such an implementation, with multiple priority classes, could also be
used for the Diffserv class selectors [DSFIELD].
Alternatively, setting the service priority values for each input to
the scheduler to the same value enables the scheduler to satisfy the
minimum service rates for each input, so long as the sum of all
minimum service rates is less than or equal to the line rate.
For example, a non-work-conserving scheduler, allocating spare
bandwidth equally between all its inputs, might be represented using
the following parameters:
Scheduler1:
Type: Scheduler2Input
Input1:
MaxRateProfile: Profile1
MinRateProfile: Profile2
Priority: none
Input2:
MaxRateProfile: Profile3
MinRateProfile: Profile4
Priority: none
A work-conserving scheduler might be represented using the following
parameters:
Scheduler2:
Type: Scheduler3Input
Input1:
MaxRateProfile: WorkConserving
MinRateProfile: Profile5
Priority: 1
Input2:
MaxRateProfile: WorkConserving
MinRateProfile: Profile6
Priority: 2
Input3:
MaxRateProfile: WorkConserving
MinRateProfile: none
Priority: 3
7.1.3. Algorithmic Dropper
An Algorithmic Dropper is an element which selectively discards
packets that arrive at its input, based on a discarding algorithm.
It has one data input and one output. In this model (but not
necessarily in a real implementation), a packet enters the dropper at
its input and either its buffer is returned to a free buffer pool or
the packet exits the dropper at the output.
Alternatively, an Algorithmic Dropper can be thought of as invoking
operations on a FIFO Queue which selectively remove a packet and
return its buffer to the free buffer pool based on a discarding
algorithm. In this case, the operation could be modeled as being a
side-effect on the FIFO upon which it operated, rather than as having
a discrete input and output. This treatment is equivalent and we
choose the one described in the previous paragraph for this model.
One of the primary characteristics of an Algorithmic Dropper is the
choice of which packet (if any) is to be dropped: for the purposes of
this model, we restrict the packet selection choices to one of the
following and we indicate the choice by the relative positions of
Algorithmic Dropper and FIFO Queue elements in the model:
a) selection of a packet that is about to be added to the tail of a
queue (a "Tail Dropper"): the output of the Algorithmic Dropper
element is connected to the input of the relevant FIFO Queue
element.
b) a packet that is currently at the head of a queue (a "Head
Dropper"): the output of the FIFO Queue element is connected to
the input of the Algorithmic Dropper element.
Other packet selection methods could be added to this model in the
form of a different type of datapath element.
The Algorithmic Dropper is modeled as having a single input. It is
possible that packets which were classified differently by a
Classifier in this TCB will end up passing through the same dropper.
The dropper's algorithm may need to apply different calculations
based on characteristics of the incoming packet (e.g., its DSCP). So
there is a need, in implementations of this model, to be able to
relate information about which classifier element was matched by a
packet from a Classifier to an Algorithmic Dropper. In the rare
cases where this is required, the chosen model is to insert another
Classifier element at this point in the flow and for it to feed into
multiple Algorithmic Dropper elements, each one implementing a drop
calculation that is independent of any classification keys of the
packet: this will likely require the creation of a new TCB to contain
the Classifier and the Algorithmic Dropper elements.
NOTE: There are many other formulations of a model that could
represent this linkage that are different from the one described
above: one formulation would have been to have a pointer from one
of the drop probability calculation algorithms inside the dropper
to the original Classifier element that selects this algorithm.
Another way would have been to have multiple "inputs" to the
Algorithmic Dropper element fed from the preceding elements,
leading eventually back to the Classifier elements that matched
the packet. Yet another formulation might have been for the
Classifier to (logically) include some sort of "classification
identifier" along with the packet along its path, for use by any
subsequent element. And yet another could have been to include a
classifier inside the dropper, in order for it to pick out the
drop algorithm to be applied. These other approaches could be
used by implementations but were deemed to be less clear than the
approach taken here.
An Algorithmic Dropper, an example of which is illustrated in Figure
5, has one or more triggers that cause it to make a decision whether
or not to drop one (or possibly more than one) packet. A trigger may
be internal (the arrival of a packet at the input to the dropper) or
it may be external (resulting from one or more state changes at
another element, such as a FIFO Queue depth crossing a threshold or a
scheduling event). It is likely that an instantaneous FIFO depth
will need to be smoothed over some averaging interval before being
used as a useful trigger. Some dropping algorithms may require
several trigger inputs feeding back from events elsewhere in the
system (e.g., depth-smoothing functions that calculate averages over
more than one time interval).
+------------------+ +-----------+
| +-------+ | n |smoothing |
| |trigger|<----------/---|function(s)|
| |calc. | | |(optional) |
| +-------+ | +-----------+
| | | ^
| v | |Depth
Input | +-------+ no | ------------+ to Scheduler
---------->|discard|--------------> |x|x|x|x|------->
| | ? | | ------------+
| +-------+ | FIFO
| |yes |
| | | | |
| | v | count + |
| +---+ bit-bucket|
+------------------+
Algorithmic
Dropper
Figure 5. Example of Algorithmic Dropper from Tail of a Queue
A trigger may be a boolean combination of events (e.g., a FIFO depth
exceeding a threshold OR a buffer pool depth falling below a
threshold). It takes as its input some set of dynamic parameters
(e.g., smoothed or instantaneous FIFO depth), and some set of static
parameters (e.g., thresholds), and possibly other parameters
associated with the packet. It may also have internal state (e.g.,
history of its past actions). Note that, although an Algorithmic
Dropper may require knowledge of data fields in a packet, as
discovered by a Classifier in the same TCB, it may not modify the
packet (i.e., it is not a marker).
The result of the trigger calculation is that the dropping algorithm
makes a decision on whether to forward or to discard a packet. The
discarding function is likely to keep counters regarding the
discarded packets (there is no appropriate place here to include a
Counter Action element).
The example in Figure 5 also shows a FIFO Queue element from whose
tail the dropping is to take place and whose depth characteristics
are used by this Algorithmic Dropper. It also shows where a depth-
smoothing function might be included: smoothing functions are outside
the scope of this document and are not modeled explicitly here, we
merely indicate where they might be added.
RED, RED-on-In-and-Out (RIO) and Drop-on-threshold are examples of
dropping algorithms. Tail-dropping and head-dropping are effected by
the location of the Algorithmic Dropper element relative to the FIFO
Queue element. As an example, a dropper using a RIO algorithm might
be represented using 2 Algorithmic Droppers with the following
parameters:
AlgorithmicDropper1: (for in-profile traffic)
Type: AlgorithmicDropper
Discipline: RED
Trigger: Internal
Output: Fifo1
MinThresh: Fifo1.Depth > 20 kbyte
MaxThresh: Fifo1.Depth > 30 kbyte
SampleWeight .002
MaxDropProb 1%
AlgorithmicDropper2: (for out-of-profile traffic)
Type: AlgorithmicDropper
Discipline: RED
Trigger: Internal
Output: Fifo1
MinThresh: Fifo1.Depth > 10 kbyte
MaxThresh: Fifo1.Depth > 20 kbyte
SampleWeight .002
MaxDropProb 2%
Another form of Algorithmic Dropper, a threshold-dropper, might be
represented using the following parameters:
AlgorithmicDropper3:
Type: AlgorithmicDropper
Discipline: Drop-on-threshold
Trigger: Fifo2.Depth > 20 kbyte
Output: Fifo1
7.2. Sharing load among traffic streams using queuing
Queues are used, in Differentiated Services, for a number of
purposes. In essence, they are simply places to store traffic until
it is transmitted. However, when several queues are used together in
a queuing system, they can also achieve effects beyond that for given
traffic streams. They can be used to limit variation in delay or
impose a maximum rate (shaping), to permit several streams to share a
link in a semi-predictable fashion (load sharing), or to move
variation in delay from some streams to other streams.
Traffic shaping is often used to condition traffic, such that packets
arriving in a burst will be "smoothed" and deemed conforming by
subsequent downstream meters in this or other nodes. In [DSARCH] a
shaper is described as a queuing element controlled by a meter which
defines its temporal profile. However, this representation of a
shaper differs substantially from typical shaper implementations.
In the model described here, a shaper is realized by using a non-
work-conserving Scheduler. Some implementations may elect to have
queues whose sole purpose is shaping, while others may integrate the
shaping function with other buffering, discarding, and scheduling
associated with access to a resource. Shapers operate by delaying
the departure of packets that would be deemed non-conforming by a
meter configured to the shaper's maximum service rate profile. The
packet is scheduled to depart no sooner than such time that it would
become conforming.
7.2.1. Load Sharing
Load sharing is the traditional use of queues and was theoretically
explored by Floyd & Jacobson [FJ95], although it has been in use in
communications systems since the 1970's.
[DSARCH] discusses load sharing as dividing an interface among
traffic classes predictably, or applying a minimum rate to each of a
set of traffic classes, which might be measured as an absolute lower
bound on the rate a traffic stream achieves or a fraction of the rate
an interface offers. It is generally implemented as some form of
weighted queuing algorithm among a set of FIFO queues i.e., a WFQ
scheme. This has interesting side-effects.
A key effect sought is to ensure that the mean rate the traffic in a
stream experiences is never lower than some threshold when there is
at least that much traffic to send. When there is less traffic than
this, the queue tends to be starved of traffic, meaning that the
queuing system will not delay its traffic by very much. When there
is significantly more traffic and the queue starts filling, packets
in this class will be delayed significantly more than traffic in
other classes that are under-using their available capacity. This
form of queuing system therefore tends to move delay and variation in
delay from under-used classes of traffic to heavier users, as well as
managing the rates of the traffic streams.
A side-effect of a WRR or WFQ implementation is that between any two
packets in a given traffic class, the scheduler may emit one or more
packets from each of the other classes in the queuing system. In
cases where average behavior is in view, this is perfectly
acceptable. In cases where traffic is very intolerant of jitter and
there are a number of competing classes, this may have undesirable
consequences.
7.2.2. Traffic Priority
Traffic Prioritization is a special case of load sharing, wherein a
certain traffic class is deemed so jitter-intolerant that if it has
traffic present, that traffic must be sent at the earliest possible
time. By extension, several priorities might be defined, such that
traffic in each of several classes is given preferential service over
any traffic of a lower class. It is the obvious implementation of IP
Precedence as described in [RFC791], of 802.1p traffic classes
[802.1D], and other similar technologies.
Priority is often abused in real networks; people tend to think that
traffic which has a high business priority deserves this treatment
and talk more about the business imperatives than the actual
application requirements. This can have severe consequences;
networks have been configured which placed business-critical traffic
at a higher priority than routing-protocol traffic, resulting in
collapse of the network's management or control systems. However, it
may have a legitimate use for services based on an Expedited
Forwarding (EF) PHB, where it is absolutely sure, thanks to policing
at all possible traffic entry points, that a traffic stream does not
abuse its rate and that the application is indeed jitter-intolerant
enough to merit this type of handling. Note that, even in cases with
well-policed ingress points, there is still the possibility of
unexpected traffic loops within an un-policed core part of the
network causing such collapse.
8. Traffic Conditioning Blocks (TCBs)
The Classifier, Meter, Action, Algorithmic Dropper, Queue and
Scheduler functional datapath elements described above can be
combined into Traffic Conditioning Blocks (TCBs). A TCB is an
abstraction of a set of functional datapath elements that may be used
to facilitate the definition of specific traffic conditioning
functionality (e.g., it might be likened to a template which can be
replicated multiple times for different traffic streams or different
customers). It has no likely physical representation in the
implementation of the data path: it is invented purely as an
abstraction for use by management tools.
This model describes the configuration and management of a Diffserv
interface in terms of a TCB that contains, by definition, zero or
more Classifier, Meter, Action, Algorithmic Dropper, Queue and
Scheduler elements. These elements are arranged arbitrarily
according to the policy being expressed, but always in the order
here. Traffic may be classified; classified traffic may be metered;
each stream of traffic identified by a combination of classifiers and
meters may have some set of actions performed on it, followed by drop
algorithms; packets of the traffic stream may ultimately be stored
into a queue and then be scheduled out to the next TCB or physical
interface. It is permissible to omit elements or include null
elements of any type, or to concatenate multiple functional datapath
elements of the same type.
When the Diffserv treatment for a given packet needs to have such
building blocks repeated, this is performed by cascading multiple
TCBs: an output of one TCB may drive the input of a succeeding one.
For example, consider the case where traffic of a set of classes is
shaped to a set of rates, but the total output rate of the group of
classes must also be limited to a rate. One might imagine a set of
network news feeds, each with a certain maximum rate, and a policy
that their aggregate may not exceed some figure. This may be simply
accomplished by cascading two TCBs. The first classifies the traffic
into its separate feeds and queues each feed separately. The feeds
(or a subset of them) are now fed into a second TCB, which places all
input (these news feeds) into a single queue with a certain maximum
rate. In implementation, one could imagine this as the several
literal queues, a CBQ or WFQ system with an appropriate (and complex)
weighting scheme, or a number of other approaches. But they would
have the same externally measurable effect on the traffic as if they
had been literally implemented with separate TCBs.
8.1. TCB
A generalized TCB might consist of the following stages:
- Classification stage
- Metering stage
- Action stage (involving Markers, Absolute Droppers, Counters,
and Multiplexors)
- Queuing stage (involving Algorithmic Droppers, Queues, and
Schedulers)
where each stage may consist of a set of parallel datapaths
consisting of pipelined elements.
A Classifier or a Meter is typically a 1:N element, an Action,
Algorithmic Dropper, or Queue is typically a 1:1 element and a
Scheduler is a N:1 element. A complete TCB should, however, result
in a 1:1 or 1:N abstract element. Note that the fan-in or fan-out of
an element is not an important defining characteristic of this
taxonomy.
8.1.1. Building blocks for Queuing
Some particular rules are applied to the ordering of elements within
a Queuing stage within a TCB: elements of the same type may appear
more than once, either in parallel or in series. Typically, a
queuing stage will have relatively many elements in parallel and few
in series. Iteration and recursion are not supported constructs (the
elements are arranged in an acyclic graph). The following inter-
connections of elements are allowed:
- The input of a Queue may be the input of the queuing block, or
it may be connected to the output of an Algorithmic Dropper, or
to an output of a Scheduler.
- Each input of a Scheduler may be connected to the output of a
Queue, to the output of an Algorithmic Dropper, or to the
output of another Scheduler.
- The input of an Algorithmic Dropper may be the first element of
the queuing stage, the output of another Algorithmic Dropper,
or it may be connected to the output of a Queue (to indicate
head-dropping).
- The output of the queuing block may be the output of a Queue,
an Algorithmic Dropper, or a Scheduler.
Note, in particular, that Schedulers may operate in series such so
that a packet at the head of a Queue feeding the concatenated
Schedulers is serviced only after all of the scheduling criteria are
met. For example, a Queue which carries EF traffic streams may be
served first by a non-work-conserving Scheduler to shape the stream
to a maximum rate, then by a work-conserving Scheduler to mix EF
traffic streams with other traffic streams. Alternatively, there
might be a Queue and/or a dropper between the two Schedulers.
Note also that some non-sensical scenarios (e.g., a Queue preceding
an Algorithmic Dropper, directly feeding into another Queue), are
prohibited.
8.2. An Example TCB
A SLS is presumed to have been negotiated between the customer and
the provider which specifies the handling of the customer's traffic,
as defined by a TCS) by the provider's network. The agreement might
be of the following form:
DSCP PHB Profile Treatment
---- --- ------- ----------------------
001001 EF Profile4 Discard non-conforming.
001100 AF11 Profile5 Shape to profile, tail-drop when full.
001101 AF21 Profile3 Re-mark non-conforming to DSCP 001000,
tail-drop when full.
other BE none Apply RED-like dropping.
This SLS specifies that the customer may submit packets marked for
DSCP 001001 which will get EF treatment so long as they remain
conforming to Profile4, which will be discarded if they exceed this
profile. The discarded packets are counted in this example, perhaps
for use by the provider's sales department in convincing the customer
to buy a larger SLS. Packets marked for DSCP 001100 will be shaped
to Profile5 before forwarding. Packets marked for DSCP 001101 will
be metered to Profile3 with non-conforming packets "downgraded" by
being re-marked with a DSCP of 001000. It is implicit in this
agreement that conforming packets are given the PHB originally
indicated by the packets' DSCP field.
Figures 6 and 7 illustrates a TCB that might be used to handle this
SLS at an ingress interface at the customer/provider boundary.
The Classification stage of this example consists of a single BA
classifier. The BA classifier is used to separate traffic based on
the Diffserv service level requested by the customer (as indicated by
the DSCP in each submitted packet's IP header). We illustrate three
DSCP filter values: A, B, and C. The 'X' in the BA classifier is a
wildcard filter that matches every packet not otherwise matched.
The path for DSCP 001100 proceeds directly to Dropper1 whilst the
paths for DSCP 001001 and 001101 include a metering stage. All other
traffic is passed directly on to Dropper3. There is a separate meter
for each set of packets corresponding to classifier outputs A and C.
Each meter uses a specific profile, as specified in the TCS, for the
corresponding Diffserv service level. The meters in this example
each indicate one of two conformance levels: conforming or non-
conforming.
Following the Metering stage is an Action stage in some of the
branches. Packets submitted for DSCP 001001 (Classifier output A)
that are deemed non-conforming by Meter1 are counted and discarded
while packets that are conforming are passed on to Queue1. Packets
submitted for DSCP 001101 (Classifier output C) that are deemed non-
conforming by Meter2 are re-marked and then both conforming and non-
conforming packets are multiplexed together before being passed on to
Dropper2/Queue3.
The Algorithmic Dropping, Queuing and Scheduling stages are realized
as follows, illustrated in figure 7. Note that the figure does not
show any of the implicit control linkages between elements that allow
e.g., an Algorithmic Dropper to sense the current state of a
succeeding Queue.
+-----+
| A|---------------------------> to Queue1
+->| |
| | B|--+ +-----+ +-----+
| +-----+ | | | | |
| Meter1 +->| |--->| |
| | | | |
| +-----+ +-----+
| Counter1 Absolute
submitted +-----+ | Dropper1
traffic | A|-----+
--------->| B|--------------------------------------> to AlgDropper1
| C|-----+
| X|--+ |
+-----+ | | +-----+ +-----+
Classifier1| | | A|--------------->|A |
(BA) | +->| | | |--> to AlgDrop2
| | B|--+ +-----+ +->|B |
| +-----+ | | | | +-----+
| Meter2 +->| |-+ Mux1
| | |
| +-----+
| Marker1
+-----------------------------------> to AlgDropper3
Figure 6: An Example Traffic Conditioning Block (Part 1)
Conforming DSCP 001001 packets from Meter1 are passed directly to
Queue1: there is no way, with configuration of the following
Scheduler to match the metering, for these packets to overflow the
depth of Queue1, so there is no requirement for dropping at this
point. Packets marked for DSCP 001100 must be passed through a
tail-dropper, AlgDropper1, which serves to limit the depth of the
following queue, Queue2: packets that arrive to a full queue will be
discarded. This is likely to be an error case: the customer is
obviously not sticking to its agreed profile. Similarly, all packets
from the original DSCP 001101 stream (some may have been re-marked by
this stage) are passed to AlgDropper2 and Queue3. Packets marked for
all other DSCPs are passed to AlgDropper3 which is a RED-like
Algorithmic Dropper: based on feedback of the current depth of
Queue4, this dropper is supposed to discard enough packets from its
input stream to keep the queue depth under control.
These four Queue elements are then serviced by a Scheduler element
Scheduler1: this must be configured to give each of its inputs an
appropriate priority and/or bandwidth share. Inputs A and C are
given guarantees of bandwidth, as appropriate for the contracted
profiles. Input B is given a limit on the bandwidth it can use
(i.e., a non-work-conserving discipline) in order to achieve the
desired shaping of this stream. Input D is given no limits or
guarantees but a lower priority than the other queues, appropriate
for its best-effort status. Traffic then exits the Scheduler in a
single orderly stream.
The interconnections of the TCB elements illustrated in Figures 6 and
7 can be represented textually as follows:
TCB1:
Classifier1:
FilterA: Meter1
FilterB: Dropper1
FilterC: Meter2
Default: Dropper3
from Meter1 +-----+
------------------------------->| |----+
| | |
+-----+ |
Queue1 |
| +-----+
from Classifier1 +-----+ +-----+ +->|A |
---------------->| |------->| |------>|B |------->
| | | | +--->|C | exiting
+-----+ +-----+ | +->|D | traffic
AlgDropper1 Queue2 | | +-----+
| | Scheduler1
from Mux1 +-----+ +-----+ | |
---------------->| |------->| |--+ |
| | | | |
+-----+ +-----+ |
AlgDropper2 Queue3 |
|
from Classifier1 +-----+ +-----+ |
---------------->| |------->| |----+
| | | |
+-----+ +-----+
AlgDropper3 Queue4
Figure 7: An Example Traffic Conditioning Block (Part 2)
Meter1:
Type: AverageRate
Profile: Profile4
ConformingOutput: Queue1
NonConformingOutput: Counter1
Counter1:
Output: AbsoluteDropper1
Meter2:
Type: AverageRate
Profile: Profile3
ConformingOutput: Mux1.InputA
NonConformingOutput: Marker1
Marker1:
Type: DSCPMarker
Mark: 001000
Output: Mux1.InputB
Mux1:
Output: Dropper2
AlgDropper1:
Type: AlgorithmicDropper
Discipline: Drop-on-threshold
Trigger: Queue2.Depth > 10kbyte
Output: Queue2
AlgDropper2:
Type: AlgorithmicDropper
Discipline: Drop-on-threshold
Trigger: Queue3.Depth > 20kbyte
Output: Queue3
AlgDropper3:
Type: AlgorithmicDropper
Discipline: RED93
Trigger: Internal
Output: Queue3
MinThresh: Queue3.Depth > 20 kbyte
MaxThresh: Queue3.Depth > 40 kbyte
<other RED parms too>
Queue1:
Type: FIFO
Output: Scheduler1.InputA
Queue2:
Type: FIFO
Output: Scheduler1.InputB
Queue3:
Type: FIFO
Output: Scheduler1.InputC
Queue4:
Type: FIFO
Output: Scheduler1.InputD
Scheduler1:
Type: Scheduler4Input
InputA:
MaxRateProfile: none
MinRateProfile: Profile4
Priority: 20
InputB:
MaxRateProfile: Profile5
MinRateProfile: none
Priority: 40
InputC:
MaxRateProfile: none
MinRateProfile: Profile3
Priority: 20
InputD:
MaxRateProfile: none
MinRateProfile: none
Priority: 10
8.3. An Example TCB to Support Multiple Customers
The TCB described above can be installed on an ingress interface to
implement a provider/customer TCS if the interface is dedicated to
the customer. However, if a single interface is shared between
multiple customers, then the TCB above will not suffice, since it
does not differentiate among traffic from different customers. Its
classification stage uses only BA classifiers.
The configuration is readily modified to support the case of multiple
customers per interface, as follows. First, a TCB is defined for
each customer to reflect the TCS with that customer: TCB1, defined
above is the TCB for customer 1. Similar elements are created for
TCB2 and for TCB3 which reflect the agreements with customers 2 and 3
respectively. These 3 TCBs may or may not contain similar elements
and parameters.
Finally, a classifier is added to the front end to separate the
traffic from the three different customers. This forms a new TCB,
TCB4, which is illustrated in Figure 8.
A representation of this multi-customer TCB might be:
TCB4:
Classifier4:
Filter1: to TCB1
Filter2: to TCB2
Filter3: to TCB3
No Match: AbsoluteDropper4
AbsoluteDropper4:
Type: AbsoluteDropper
TCB1:
(as defined above)
TCB2:
(similar to TCB1, perhaps with different
elements or numeric parameters)
TCB3:
(similar to TCB1, perhaps with different
elements or numeric parameters)
and the filters, based on each customer's source MAC address, could
be defined as follows:
Filter1:
submitted +-----+
traffic | A|--------> TCB1
--------->| B|--------> TCB2
| C|--------> TCB3
| X|------+ +-----+
+-----+ +-->| |
Classifier4 +-----+
AbsoluteDrop4
Figure 8: An Example of a Multi-Customer TCB
Type: MacAddress
SrcValue: 01-02-03-04-05-06 (source MAC address of customer 1)
SrcMask: FF-FF-FF-FF-FF-FF
DestValue: 00-00-00-00-00-00
DestMask: 00-00-00-00-00-00
Filter2:
(similar to Filter1 but with customer 2's source MAC address as
SrcValue)
Filter3:
(similar to Filter1 but with customer 3's source MAC address as
SrcValue)
In this example, Classifier4 separates traffic submitted from
different customers based on the source MAC address in submitted
packets. Those packets with recognized source MAC addresses are
passed to the TCB implementing the TCS with the corresponding
customer. Those packets with unrecognized source MAC addresses are
passed to a dropper.
TCB4 has a Classifier stage and an Action element stage performing
dropping of all unmatched traffic.
8.4. TCBs Supporting Microflow-based Services
The TCB illustrated above describes a configuration that might be
suitable for enforcing a SLS at a router's ingress. It assumes that
the customer marks its own traffic for the appropriate service level.
It then limits the rate of aggregate traffic submitted at each
service level, thereby protecting the resources of the Diffserv
network. It does not provide any isolation between the customer's
individual microflows.
A more complex example might be a TCB configuration that offers
additional functionality to the customer. It recognizes individual
customer microflows and marks each one independently. It also
isolates the customer's individual microflows from each other in
order to prevent a single microflow from seizing an unfair share of
the resources available to the customer at a certain service level.
This is illustrated in Figure 9.
Suppose that the customer has an SLS which specifies 2 service
levels, to be identified to the provider by DSCP A and DSCP B.
Traffic is first directed to a MF classifier which classifies traffic
based on miscellaneous classification criteria, to a granularity
sufficient to identify individual customer microflows. Each
microflow can then be marked for a specific DSCP The metering
elements limit the contribution of each of the customer's microflows
to the service level for which it was marked. Packets exceeding the
allowable limit for the microflow are dropped.
+-----+ +-----+
Classifier1 | | | |---------------+
(MF) +->| |-->| | +-----+ |
+-----+ | | | | |---->| | |
| A|------ +-----+ +-----+ +-----+ |
-->| B|-----+ Marker1 Meter1 Absolute |
| C|---+ | Dropper1 | +-----+
| X|-+ | | +-----+ +-----+ +-->|A |
+-----+ | | | | | | |------------------>|B |--->
| | +->| |-->| | +-----+ +-->|C | to TCB2
| | | | | |---->| | | +-----+
| | +-----+ +-----+ +-----+ | Mux1
| | Marker2 Meter2 Absolute |
| | Dropper2 |
| | +-----+ +-----+ |
| | | | | |---------------+
| |--->| |-->| | +-----+
| | | | |---->| |
| +-----+ +-----+ +-----+
| Marker3 Meter3 Absolute
| Dropper3
V etc.
Figure 9: An Example of a Marking and Traffic Isolation TCB
This TCB could be formally specified as follows:
TCB1:
Classifier1: (MF)
FilterA: Marker1
FilterB: Marker2
FilterC: Marker3
etc.
Marker1:
Output: Meter1
Marker2:
Output: Meter2
Marker3:
Output: Meter3
Meter1:
ConformingOutput: Mux1.InputA
NonConformingOutput: AbsoluteDropper1
Meter2:
ConformingOutput: Mux1.InputB
NonConformingOutput: AbsoluteDropper2
Meter3:
ConformingOutput: Mux1.InputC
NonConformingOutput: AbsoluteDropper3
etc.
Mux1:
Output: to TCB2
Note that the detailed traffic element declarations are not shown
here. Traffic is either dropped by TCB1 or emerges marked for one of
two DSCPs. This traffic is then passed to TCB2 which is illustrated
in Figure 10.
TCB2 could then be specified as follows:
Classifier2: (BA)
FilterA: Meter5
FilterB: Meter6
+-----+
| |---------------> to Queue1
+->| | +-----+
+-----+ | | |---->| |
| A|---+ +-----+ +-----+
->| | Meter5 AbsoluteDropper4
| B|---+ +-----+
+-----+ | | |---------------> to Queue2
Classifier2 +->| | +-----+
(BA) | |---->| |
+-----+ +-----+
Meter6 AbsoluteDropper5
Figure 10: Additional Example: TCB2
Meter5:
ConformingOutput: Queue1
NonConformingOutput: AbsoluteDropper4
Meter6:
ConformingOutput: Queue2
NonConformingOutput: AbsoluteDropper5
8.5. Cascaded TCBs
Nothing in this model prevents more complex scenarios in which one
microflow TCB precedes another (e.g., for TCBs implementing separate
TCSs for the source and for a set of destinations).
9. Security Considerations
Security vulnerabilities of Diffserv network operation are discussed
in [DSARCH]. This document describes an abstract functional model of
Diffserv router elements. Certain denial-of-service attacks such as
those resulting from resource starvation may be mitigated by
appropriate configuration of these router elements; for example, by
rate limiting certain traffic streams or by authenticating traffic
marked for higher quality-of-service.
There may be theft-of-service scenarios where a malicious host can
exploit a loose token bucket policer to obtain slightly better QoS
than that committed in the TCS.
10. Acknowledgments
Concepts, terminology, and text have been borrowed liberally from
[POLTERM], as well as from other IETF work on MIBs and policy-
management. We wish to thank the authors of some of those documents:
Fred Baker, Michael Fine, Keith McCloghrie, John Seligson, Kwok Chan,
Scott Hahn, and Andrea Westerinen for their contributions.
This document has benefited from the comments and suggestions of
several participants of the Diffserv working group, particularly
Shahram Davari, John Strassner, and Walter Weiss. This document
could never have reached this level of rough consensus without the
relentless pressure of the co-chairs Brian Carpenter and Kathie
Nichols, for which the authors are grateful.
11. References
[AF-PHB] Heinanen, J., Baker, F., Weiss, W. and J. Wroclawski,
"Assured Forwarding PHB Group", RFC2597, June 1999.
[DSARCH] Carlson, M., Weiss, W., Blake, S., Wang, Z., Black, D.
and E. Davies, "An Architecture for Differentiated
Services", RFC2475, December 1998.
[DSFIELD] Nichols, K., Blake, S., Baker, F. and D. Black,
"Definition of the Differentiated Services Field (DS
Field) in the IPv4 and IPv6 Headers", RFC2474, December
1998.
[DSMIB] Baker, F., Smith, A., and K. Chan, "Management
Information Base for the Differentiated Services
Architecture", RFC3289, May 2002.
[E2E] Bernet, Y., Yavatkar, R., Ford, P., Baker, F., Zhang, L.,
Speer, M., Nichols, K., Braden, R., Davie, B.,
Wroclawski, J. and E. Felstaine, "A Framework for
Integrated Services Operation over Diffserv Networks",
RFC2998, November 2000.
[EF-PHB] Davie, B., Charny, A., Bennett, J.C.R., Benson, K., Le
Boudec, J.Y., Courtney, W., Davari, S., Firoiu, V. and D.
Stiliadis, "An Expedited Forwarding PHB (Per-Hop
Behavior)", RFC3246, March 2002.
[FJ95] Floyd, S. and V. Jacobson, "Link Sharing and Resource
Management Models for Packet Networks", IEEE/ACM
Transactions on Networking, Vol. 3 No. 4, August 1995l.
[INTSERV] Braden, R., Clark, D. and S. Shenker, "Integrated
Services in the Internet Architecture: an Overview", RFC
1633, June 1994.
[NEWTERMS] Grossman, D., "New Terminology and Clarifications for
Diffserv", RFC3260, April, 2002
[PDBDEF] K. Nichols and B. Carpenter, "Definition of
Differentiated Services Per Domain Behaviors and Rules
for Their Specification", RFC3086, April 2001.
[POLTERM] Westerinen, A., Schnizlein, J., Strassner, J., Scherling,
M., Quinn, B., Herzog, S., Huynh, A., Carlson, M., Perry,
J. and S. Waldbusser, "Policy Terminology", RFC3198,
November 2001.
[QOSDEVMOD] Strassner, J., Westerinen, A. and B. Moore, "Information
Model for Describing Network Device QoS Mechanisms", Work
in Progress.
[QUEUEMGMT] Braden, R., Clark, D., Crowcroft, J., Davie, B., Deering,
S., Estrin, D., Floyd, S., Jacobson, V., Minshall, C.,
Partridge, C., Peterson, L., Ramakrishnan, K., Shenker,
S., Wroclawski, J. and L. Zhang, "Recommendations on
Queue Management and Congestion Avoidance in the
Internet", RFC2309, April 1998.
[SRTCM] Heinanen, J. and R. Guerin, "A Single Rate Three Color
Marker", RFC2697, September 1999.
[TRTCM] Heinanen, J. and R. Guerin, "A Two Rate Three Color
Marker", RFC2698, September 1999.
[VIC] McCanne, S. and Jacobson, V., "vic: A Flexible Framework
for Packet Video", ACM Multimedia '95, November 1995, San
Francisco, CA, pp. 511-522.
<ftp://ftp.ee.lbl.gov/papers/vic-mm95.ps.Z>
[802.1D] "Information technology - Telecommunications and
information exchange between systems - Local and
metropolitan area networks - Common specifications - Part
3: Media Access Control (MAC) Bridges: Revision. This
is a revision of ISO/IEC 10038: 1993, 802.1j-1992 and
802.6k-1992. It incorporates P802.11c, P802.1p and
P802.12e.", ISO/IEC 15802-3: 1998.
Appendix A. Discussion of Token Buckets and Leaky Buckets
"Leaky bucket" and/or "Token Bucket" models are used to describe rate
control in several architectures, including Frame Relay, ATM,
Integrated Services and Differentiated Services. Both of these
models are, by definition, theoretical relationships between some
defined burst size, B, a rate, R, and a time interval, t:
R = B/t
Thus, a token bucket or leaky bucket might specify an information
rate of 1.2 Mbps with a burst size of 1500 bytes. In this case, the
token rate is 1,200,000 bits per second, the token burst is 12,000
bits and the token interval is 10 milliseconds. The specification
says that conforming traffic will, in the worst case, come in 100
bursts per second of 1500 bytes each and at an average rate not
exceeding 1.2 Mbps.
A.1 Leaky Buckets
A leaky bucket algorithm is primarily used for shaping traffic as it
leaves an interface onto the network (handled under Queues and
Schedulers in this model). Traffic theoretically departs from an
interface at a rate of one bit every so many time units (in the
example, one bit every 0.83 microseconds) but, in fact, departs in
multi-bit units (packets) at a rate approximating the theoretical, as
measured over a longer interval. In the example, it might send one
1500 byte packet every 10 ms or perhaps one 500 byte packet every 3.3
ms. It is also possible to build multi-rate leaky buckets in which
traffic departs from the interface at varying rates depending on
recent activity or inactivity.
Implementations generally seek as constant a transmission rate as
achievable. In theory, a 10 Mbps shaped transmission stream from an
algorithmic implementation and a stream which is running at 10 Mbps
because its bottleneck link has been a 10 Mbps Ethernet link should
be indistinguishable. Depending on configuration, the approximation
to theoretical smoothness may vary by moving as much as an MTU from
one token interval to another. Traffic may also be jostled by other
traffic competing for the same transmission resources.
A.2 Token Buckets
A token bucket, on the other hand, measures the arrival rate of
traffic from another device. This traffic may originally have been