This document describes some of the mechanisms used by Asynchronous
Transfer Mode (ATM) to manage traffic. It is based on the ATM Forum
User-Network Interface (UNI) 3.1 and the Traffic Management (TM) 4.0
specifications. UNI 3.1 contains both signaling and traffic management
specifications. TM 4.0 was written to accompany the ATM Forum UNI 4.0
specification, splitting the two topics into two different documents.
Hence, there is some redundancy between UNI 3.1 and TM 4.0, and TM 4.0
contains some UNI 4.0-specific features. However, I find the TM 4.0
specification to be a much more useful description of traffic
management mechanisms, even in the UNI 3.1 context. All of my ATM
experience has been with UNI 3.0 and UNI 3.1. I find UNI 3.1 to be
widely implemented, UNI 4.0 not so much. I will briefly mention a
couple of places that UNI 4.0 differs from UNI 3.1 in regards to
traffic management and traffic contracts.
It
would be easy to dismiss ATM traffic management now that ATM is being
eclipsed by other technologies, such as Internet Protocol (IP) over
gigabit-Ethernet. However, ATM is still widely used as a wide area
network transport layer, and for technologies like Digital Subscriber
Line (DSL). Also, I have usefully applied ATM traffic management
algorithms to non-ATM applications. For example, the Desperado software
library for embedded applications contains rate control components
based on ATM traffic contracts. By mentally replacing the ATM rate
metric of cells-per-second with anything-else-per-second, you can use
these components to implement complex rate controls to shape traffic of
just about any sort at the application layer. Understanding ATM traffic
management has led me to a better understanding and appreciation of
traffic management issues in other networking technologies.
Connection Admission Control
Unlike network technologies like IP, each discrete data stream, known
as a virtual circuit (VC), over ATM has associated with it a traffic
contract. A traffic contract is an explicit description of the expected
behavior of the virtual circuit in terms of flow rate, burstiness, and
its tolerance to jitter or rate variation. Both permanent virtual
circuits (PVCs), established statically via administration, and
switched virtual circuits (SVCs), established dynamically via a
signaling protocol like UNI 3.1, have traffic contracts.
When an ATM end point requests that the network set up a VC, the
Connection Admission Control (CAC) algorithm in every ATM switch that
the VC may traverse examines the traffic contract and decides whether
it can support it in light of all the other VCs it is currently
handling. Each ATM switch that the VC traverses must accept the traffic
contract for the VC to be successfully set up end to end. Even the
terminating ATM end point may reject the VC set up based on its own CAC
algorithm.
CAC
algorithms are serious business. An ATM switch that accepts more
traffic than it can reliabily handle will end up dropping ATM cells due
to congestion, or jittering cells beyond the tolerance of their traffic
contract. Either alternative leads to unreliable cell transport. An ATM
switch that rejects traffic that it could have handled has a lower
capacity than a competing switch, leading to higher costs, and for an
ATM service provider, lower revenue. When ATM was in its hey day, a lot
of research and development, and many dissertations, went into CAC
algorithms.
UNI
3.1 and TM 4.0 describe two simple CAC algorithms. But my experience is
that most ATM switches at the high end implement much more complex
proprietary algorithms, or at the low end no CAC algorithm at all. At
high traffic levels, wackiness ensues on the low end switches. I
personally implemented the two simple algorithms and a third complex
proprietary algorithm, the so-called "Bell Labs" algorithm, in firmware
on a middle end ATM switch, whose manufacture, in the way typical of
high tech, was discontinued just as the device reached maturity and
stability.
Traffic Contracts
UNI 3.1 supports several classes of service for virtual circuits (VCs). Each class of service has a different format of traffic contract describing a different real-time need of the VC.
The
most widely used class of service in my experience is Unspecified Bit
Rate (UBR). A UBR VC has
no
explicit traffic contract. A typical application is the transport of
data
traffic, for example, IP packets. Cells on a UBR VC are transmitted on
a best
effort basis. They will not necessarily be the first cells to be
dropped when
network congestion occurs. This honor falls to cells that have been
tagged by
ATM traffic policing hardware because the VCs of which they are a part
have
violated their explicit traffic contracts. But all other things being
equal,
cells that are part of a UBR VC will dropped before cells of other
classes.
The
next most widely used class of service is Constant Bit Rate (CBR). A
CBR VC is expected to transmit cells at a constant rate. Whether it
actually does or not is immaterial. The CAC algorithms in the network
assume that it does and accept or reject the set up request based on
that assumption. CBR VCs are expensive from a bandwidth point of view,
since the full requested bandwidth is assumed to be required whether it
is actually used or not. CBR VCs are used for applications like
uncompressed voice, using coders-decoders (CODECs) based on the G.711
standard. A CBR VC has a traffic contract that specifies just Peak Cell
Rate (PCR) and which has an implicit Cell Delay Variation Tolerance
(CDVT). The PCR is the the rate in cells per second (CPS) at which the
VC is expected to transmit. A G.711 encoded voice stream has a constant
bit rate of sixty-four kilobits per second, for a PCR or about (with
some overhead accounted for) 173 CPS. The CDVT, in microseconds, is the
amount of variation in the PCR that the traffic source may exhibit
before the cells are policed by an ATM switch, or at least marked for
possible policing by a down stream ATM switch. It is the amount of
slack afforded by the network. Since the CDVT is not a parameter in the
traffic contract, it is typically manually administered on each ATM
switch. A typical CDVT is 250 microseconds. How the CDVT comes into
play is part of the ATM Generic Cell Rate Algorithm (GCRA) and will
described below.
Next
comes Variable Bit Rate non-real-time (VBR-nrt). VBR-nrt VCs are
expected to be bursty, and it is here that the proprietary CAC
algorithms really come into play. Such a CAC algorithm makes a guess,
typically using complicated statistical methods, at how likely it is
that all of its VBR-nrt VCs will burst at the same time, and by how
much. If the CAC algorithm guesses right, its switch can handle more,
perhaps many more, VCs than a competitor's ATM switch. If it guesses
wrong, many cells will be lost or jittered. VBR-nrt traffic contracts
include the PCR (and the implied CDVT), plus a Sustainable Cell Rate
(SCR) and Maximum Burst Size (MBS). PCR is the maximum rate that the
VBR-nrt VC can transmit. The SCR is the long term average in cells per
second at which the
VC is expected to transmit. MBS is the number of cells the VC is
allowed to burst at PCR before they are found to be out of compliance
with the traffic contract and subject to policing.
The graph of time
versus cell rate below shows a well-behaved VBR-nrt VC transmitting at
exactly its SCR. A sequence of cells of length MBS is demarked to show
the time it takes to send the maximum burst size at the sustainable
cell rate. MBS cells sent at the SCR take MBS/SCR to send
(cells/(cells/second) equals seconds). Such a VC is a uniform
continuous traffic source.
^
|
PCR +
|
|
|
|
|
|
|
SCR +...............................................................
| : :
| : MBS cells :
| : sent at SCR :
| : :
| : :
| : :
| : :
| : :
0 +--------------------------------------------------------------->Time
0 | |
|<-------------- MBS/SCR ----------------->|
If the application instead transmits in nothing but bursts, in order to conform to its traffic contract its traffic pattern must appear as shown on the graph below. Such a VC is a periodic on-off traffic source. It must transmit on average the same number of cells over the period of MBS/SCR as if it were transmitting at its SCR at all times. It can send no more than MBS cells at PCR in order to conform to the MBS in its traffic contract. Such a burst takes MBS/PCR seconds to transmit. The burst must be followed by a quiet period of at least ((MBS/SCR)-(MBS/PCR)) seconds in which no cells are transmitted in order to conform to the SCR in its traffic contract. This works out to (MBS*((1/SCR)-(1/PCR)). Note that (1/SCR) and (1/PCR) are cell interarrival (or from the point of view of the traffic source, interdeparture) intervals (cells/second becomes seconds/cell).
Cell
Rate
^
|
PCR
+----------------
----------------
||
|
|
|
|| Burst #1
|
| Burst #2 |
|| of MBS cells
|
| of MBS cells |
|| sent at PCR
|
| sent at PCR |
||
|
|
|
||
|
|
|
||
|
|
|
SCR
+|
|
|
|
||
|
|
|
||
|
|
|
||
|
|
|
||
|
|
|
||
|
|
|
||
|
|
|
||
|
|
|
||
|
|
|
0
+--------------------------------------------------------------->Time
0
|
|
|<- MBS/PCR -->|<-
MBS*((1/SCR)-(1/PCR)) ->|
|
|
|<--------------- MBS/SCR
---------------->|
These two graphs represent the extremes of acceptable traffic behavior
that that may be exhibited by a VBR-nrt VC. Generally, VBR-nrt VCs fall
somewhere in between. How more complex traffic behavior is managed is
again the subject of the GCRA described below. The graph below shows
the prior two graphs superimposed on one another for comparison. A
perfect ATM traffic shaper would consume cells from the periodic on-off
traffic source and emit cells as a uniform continuous traffic source. A
perfect ATM traffic policer would find either cell stream in compliance
with its traffic contract.
^
|
PCR +---------------- ----------------
|| | | |
|| Burst #1 | | Burst #2 |
|| of MBS cells | | of MBS cells |
|| sent at PCR | | sent at PCR |
|| | | |
|| | | |
|| | | |
SCR +|..............................................................
|| : | | : |
|| : | MBS cells | : |
|| : | sent at SCR | : |
|| : | | : |
|| : | | : |
|| : | | : |
|| : | | : |
|| : | | : |
0 +--------------------------------------------------------------->Time
0| | | |
| |<-------------- MBS/SCR --------------|-->|
|<- MBS/PCR -->|<- MBS*((1/SCR)-(1/PCR)) ->|
| |
|<--------------- MBS/SCR ---------------->|
The UNI 4.0 specification supports two additional classes of service: Variable Bit Rate real-time (VBR-rt) and Available Bit Rate (ABR).
The VBR-rt traffic contract adds another parameter, Cell Delay Variation (CDV). CDV is different from CDVT. CDVT is the amount of slack the network allows for the PCR before cells are subject to policing. CDV is the amount of jitter or variation in interarrival (or interdeparture) interval a cell may incur before it is no longer useful to the application and may as well be policed by the network. Real-time applications like voice and video can only tolerate just so much jitter before the cell arrives too late at the end point to be useful because a voice or video sample associated time-wise with the cell payload has already been played. (This is the cause of the "freeze-frame" and "jump-ahead" effects you sometimes see on live television feeds.) Rather than have the network transport a cell that the end point will ultimately throw away anyway, CDV allows the application to specify when the network may police the cell rather than transport it.
ATM switches that support ABR traffic contracts implement a flow control mechanism that allows a traffic source to increase and decrease its cell rate based on real-time feedback from the network on the amount of bandwidth that is instantaneously available. I have never used ABR, nor have I ever seen an ATM switch that supported it.
ATM traffic contracts sound complicated, but in fact ATM traffic policing based on these traffic contracts is typically implemented in hardware. There are chipsets that enforce traffic contracts for as many as 64,000 VCs simultaneously. As we shall see below, the GCRA is a simple algorithm that lends itself to being implemented efficiently in hardware. For relatively low performance applications on ATM end points, it can also be easily implemented in firmware for purposes of traffic shaping cells before injecting them into the network. I have implemented traffic shaping for multiple VBR-nrt VCs on one such product.
Cell Emission Prioritization
ATM switch hardware may (and in my experience, generally do) prioritize the order of cell emission based on their classes of service and traffic contracts. The prioritization is based on the amount of jitter that a VC can suffer before the application is affected. Although such hardware is usually programmable, a typical approach is to give CBR cells first priority, followed by VBR-rt cells, then VBR-nrt cells, then ABR cells, then finally UBR cells. (You quickly learn in ATM that UBR VCs get no respect.)
It is for this reason that it may make perfect sense to set up a VBR-nrt VC but have PCR equal to SCR in the traffic contract. This causes the CAC algorithms in the network to reserve the full requested bandwidth, but the ATM network hardware to prioritize the cells lower than CBR traffic (because they are part of the same application) but higher than UBR traffic (because they are not part of the same application). ATM applications I have worked on have done this very thing, although it was not unusual at the time to find that ATM switches (and ATM switch vendor representatives) were confused by this.
Non-application Cell Streams
There are also non-application cell streams transported between end points and the ATM network. These are the various control, routing, and signaling protocols used by end points and ATM switches. Common examples are UNI signaling, Interim Layer Management Interface (ILMI), and Private Network-Network Interface (PNNI). Because these cell streams compete with application streams for both bandwidth and cell emission priority, it is appropriate that these control streams also each have a traffic contract. However, these cell streams are essentially PVCs. They are not set up dynamically but instead associated with pre-defined and fixed Virtual Circuit Identifiers (VCI). So any traffic contract that they may have must be implicit.
UNI 3.1 assigns the UBR class of service to the cell streams for the UNI and ILMI protocols. This could allow application cell streams to starve these control VCs of bandwidth, and could jitter even these protocols beyond their tolerance in conditions of heavy network congestion. This could result long delays for VC set up, deny an end point its ability to register with its edge ATM switch, or even in extreme cases take portions of the ATM network down as various protocols time out and go into recovery states.
UNI 4.0 gives UNI and ILMI the CBR class of service with an implicit PCR. This reserves bandwidth for these control VCs and also gives them priority above VBR and UBR cell streams. Presumable this was done precisely because of the potential starvation problem. The issue arises of starving application cell streams with high rates of UNI and ILMI protocol messages, but this is limited by the implicit PCR of the UNI and ILMI traffic contracts.
The Generic Cell Rate Algorithm
The Generic Cell Rate Algorithm (GCRA) as described in UNI 3.1 and TM 4.0 (and probably elsewhere) is a method of measuring the long term behavior of a traffic source in terms of ideal cell interarrival interval and the degree to which the actual interarrival interval can differ from it. It can be (and is) used for both traffic policing in ATM switches and traffic shaping in ATM end devices.
The GCRA can also be used in other, non-ATM, applications. For example, I have seen it used as a way to measure the state of health of non-ATM WAN telecommunications circuits; instead of being triggered by a cell arrival event, it is triggered by an error on the circuit. By substituting any event for a cell arrival event, the GCRA can be adapted to be a very flexible form of rate control.
The GCRA is very simple and requires only two parameters I (Increment) and L (Limit), a single state variable X, also known as TAT (Theoretical Arrival Time), and temporary variables X1 and Elapsed. (These variable names aren't the most descriptive, but they are the ones used in the UNI 3.1 and TM 4.0 specifications from the ATM Forum, so they are used both here and in the Desperado CellRateThrottle class so that they could be easily correlated back to the original specification.) Both I and L are in units of time, typically microseconds.
I is the ideal interarrival interval (or in the case of traffic shaping rather than traffic policing, interdeparture interval) of cells, which is the reciprocal of the expected cell rate. If an ATM traffic source has a cell rate of one thousand cells per second, then I is 1/1000 seconds, or 1000000/1000 or 1000 microseconds.
L is the maximum time a cell can arrive ahead of its theoretical arrival time, referred to in the literature as TAT (I think "expected arrival time" is a little clearer term, and it is what I use in the following explanation). When you see a generic cell rate algorithm referred to in the literature, it is usually written as GCRA(I,L) (possibly with numeric values for I and L), frequently with no explanation for the meaning of this notation. Time units are typically in microseconds.
In
ATM, one
GCRA is necessary to police each CBR VC, and a second GCRA is necessary
to
police each VBR VCs. In typical notation, the first GCRA is described
as GCRA(1/PCR,CDVT), and the second GCRA
is described as GCRA(1/SCR,BT+CDVT). For the first GCRA, the Increment
is 1/PCR, the cell interarrival interval at the Peak Cell Rate, and the
Limit is the Cell Delay Variation Tolerance. For the second GCRA, the
Increment is 1/SCR, the cell interarrival interval at the Sustainable
Cell Rate, and the Limit is the Burst Tolerance plus the Cell Delay
Variation Tolerance.
Burst
Tolerance (BT) is computed by the ATM network as
BT=(MBS-1)*((1/SCR)-(1/PCR)),
which can be thought of as
the maximum allowable aggregate difference in interarrival times for a
VC
bursting above SCR. The (MBS-1) is the number of intervals between
cells of a burst of size MBS cells. The ((1/SCR)-(1/PCR)) is the
difference in interarrival intervals between cells arriving at SCR and
cells arriving at PCR. Note that for a fixed BT calculated using the
signaled PCR,
SCR and MBS, a burst size can be computed for any cell rate above SCR
by
substituting that cell rate for PCR and solving for MBS. This answers
the
question "If I can send at most MBS cells at PCR, how many cells can I
send at PCR/2, if PCR/2 is still more than SCR?".
Cell Delay Variation
Tolerance (CDVT) is the amount of variance in
interarrival time
allowed when a VC transmits at PCR. CDVT is present to allow for the
slotted
nature of the serial ATM cell stream and for some variation or jitter
introduced into the cell stream by the ATM network itself. It is not
intended
to allow for cell jitter induced by an end station as it emits cells
into the
ATM network. CDVT is not a signalable parameter, although it can be
manually
administered on some ATM switches. A typical value for CDVT on an OC-3
connection is 250 microseconds; faster connections (e.g., OC-12) get
smaller
values for
CDVT.
You may notice in some ATM documents that the CDVT is omitted from the Limit of the second GCRA. This is a bug. GCRAs policing SCR without taking CDVT into account can and will police conformant cells. This becomes obvious when you work out the math, or as I have done, actually implement some of this stuff.
The GCRA can be described in two equivalent forms: as a virtual scheduling algorithm, or as a continuous state leaky bucket algorithm. I find the virtual scheduler a little easier to understand conceptually. Here is an explanation of how the GCRA works based on the virtual scheduling algorithm.
The GCRA sees a time line in which each E represents when a cell is expected to arrive. The arrival times are exactly I time units apart, where I is the GCRA parameter that is the recipricol of the signaled cell rate (I=1/SCR for the SCR traffic policer, I=1/PCR for the PCR traffic policer).
E0 E1 E2 E3 E4 E5 E6 E7 E8 E9
-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----> Time
|<-I->|<-I->|<-I->|<-I->|<-I->|<-I->|<-I->|<-I->|<-I->|
In
a perfectly
behaved cell stream, cells arrive exactly when they are expected. In
the graph
below, each C is an actual cell arrival. The cell arrivals in the
graph below coincide with the expected arrival times, so the GCRA sees
that
cells C0 through C9 arrive exactly on time.
E0 E1 E2 E3 E4 E5 E6 E7 E8 E9
-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----> Time
C0 C1 C2 C3 C4 C5 C6 C7 C8 C9
|<-I->|<-I->|<-I->|<-I->|<-I->|<-I->|<-I->|<-I->|<-I->|
If
a cell
arrives late, no credit is given by the GCRA. Instead, the remainder of
the
time line is shifted forward in time by the GCRA so that the new
expected
arrival times coincide with the arrival time of the late cell. In the
graph below,
cell C2 arrives n time units late, so its interarrival interval is
(I+n)
instead of I. The time line is shifted such that each successive cell
is still
expected some multiple of I time units after cell C2.
E0 E1 E2 E3 E4 E5 E6 E7 E8 E9
-----+-----+---------+-----+-----+-----+-----+-----+-----+-----+-----> Time
C0 C1 C2 C3 C4 C5 C6 C7 C8 C9
|<-I->|<-(I+n)->|<-I->|<-I->|<-I->|<-I->|<-I->|<-I->|<-I->|
If
a cell
arrives early, the GCRA compares the difference between the actual
arrival time
and the expected arrival time for that cell with L, the other GCRA
parameter
(L=BT for the SCR traffic policer, L=CDVT for the PCR traffic policer).
If that
difference is greater than L, the cell does not conform to the traffic
contract
and may be policed, that is, dropped or tagged at the option of the ATM
network. Whether a cell is policed or not, the effect of sending
subsequent
cells early is cumulative. To get back into the good graces of the
GCRA, the
cell stream must return to sending cells at their original expected
arrival
time. This might require a long period of idle traffic in order for the
time
line to "catch up" (or, for the leaky bucket to drain). In the graph
below, cells C1 through C6 are early but fall within L time units of
their
expected arrival time. Cell C7 does not, and so would be policed. At
the end of
the burst of seven cells, the cell stream is quiet until cell 8 arrives
at its
originally expected arrival time. At this point, the cell stream may
burst
again providing all cells are within L of their expected arrival time.
E0 E1 E2 E3 E4 E5 E6 E7 E8 E9
-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----> Time
C0 C1 C2 C3 C4 C5 C6 C7 C8 C9
|<---- L ---->|
|<---- L ---->|
|<---- L ---->|
|<---- L ---->|
|<---- L ---->|
|<---- L ---->|
|<---- L ---->|
Here
is
another example that shows a short burst of three cells (cells C1
through C3)
followed by subsequent cells arriving at SCR. Although cells C4 through
C9 are
sent at SCR, they are each still arriving before their scheduled
interarrival
times. Although no cells are policed, the time debt accumulated by the
burst is
carried along, affecting whether cells in a future burst are policed or
not.
The short burst of three cells has used up part of L. This time debt is
not
recovered until a cell arrives at the traffic policer at its original
expected
arrival time.
E0 E1 E2 E3 E4 E5 E6 E7 E8 E9
-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----> Time
C0 C1 C2 C3 C4 C5 C6 C7 C8 C9
|<---- L ---->|
|<---- L ---->|
|<---- L ---->|
|<---- L ---->|
|<---- L ---->|
|<---- L ---->|
|<---- L ---->|
|<---- L ---->|
|<---- L ---->|
A Pseudo-code Implementation
Below is an object-oriented pseudo-code description of the GCRA as implemented in the Desperado class CellRateThrottle. It is based on the continuous state virtual scheduling algorithm described in TM 4.0. elapsed is the actual arrival time for a cell. x is the expected arrival time for a cell. x1 is the difference between the expected arrival time (x) and the actual arrival time (elapsed). Hence, it is x1 that is compared to l. For the cell to conform to the traffic contract, x1 must be less than l.
//
// GENERIC CELL RATE ALGORITHM
//
// Implements a GCRA using a continuous state virtual scheduling algorithm.
//
class Gcra {
public:
Gcra(ulong i, ulong l); // Each GCRA is initialized with an
// I (Increment) and L (Limit).
bool conformant(void); // Would the cell conform to the
// traffic contract if emitted now?
void commit(void); // The cell was emitted, so update
// the GCRA state.
ulong elapsed; // Elapsed time since the last
// time we emitted a cell. Updated
// "off screen" as time passes.
private:
ulong i; // I for Increment in GCRA(I,L)
ulong l; // L for Limit in GCRA(I,L)
ulong x; // This is the state variable of the
// GCRA. It retains state between
// successive calls to conformant.
ulong x1; // This is an auxiliary variable
// that retains state between calls
// to conformant and commit.
}
//
// Gcra: constructor.
//
Gcra(ulong i, ulong l) {
this->i = i;
this->l = l;
this->x = 0;
this->x1 = 0;
this->elapsed = i; // So that first cell conforms
}
//
// Gcra::conformant: returns true if the current cell conforms
// to the traffic contract, false otherwise. Called prior to
// deciding if each cell should be emitted to the ATM network.
// Any number of Gcra::conformant()s can be called with no
// intervening calls to Gcra::commit().
//
bool conformant(void) {
if (this->x < this->elapsed) {
this->x1 = 0;
//
// Cell is on time or even late.
//
return(true);
} else {
this->x1 = this->x - this->elapsed;
if (this->x1 > this->l) {
//
// Cell is too early.
//
return(false);
} else {
//
// Cell is early but within L.
//
return(true);
}
}
}
//
// Gcra::commit: updates the state of the Gcra based on the
// calculations performed by the prior Gcra::conformant().
// Called as a cell is emitted to the ATM network, whether
// it conforms to the traffic contract or not. Gcra::conformant()
// must be called prior to each call to Gcra::commit().
//
void commit(void) {
this->x = this->x1 + this->i; // Update expected arrival time by I.
this->elapsed = 0; // Clear time since last emission.
}
References
Traffic Management Specification Version 4.0, ATM Forum, af-tm-0056.000, April 1996
ATM User-Network Interface Specification Version 3.1, ATM Forum, af-uni-0010.002, September 1994
Author
J.
L. Sloan
jsloan@diag.com 2005-08-29
© 2005
by the Digital Aggregates Corporation. All rights reserved.