Transcript ATM Traffic Control

ATM Traffic & Congestion
Control
1
Introduction
ATM congestion problem overview
 ITU-T and ATM Forum framework
for control of delay-sensitive traffic
 ATM traffic control mechanisms
 ATM congestion control
 Congestion control schemes for
bursty traffic (ABR and GFR)

Chapter 13: ATM Traffic & Congestion Control
2
ATM Service Categories

Constant Bit Rate (CBR)
– fixed data rate required at guaranteed capacity

Real-Time Variable Bit-Rate (rt-VBR)
– tightly constrained delay and delay variation
– sustained rate & guaranteed fast burst rate

Non-Real-Time Variable Bit-Rate (nrt-VBR)
– no delay variation bound, cell loss ratio only

Available Bit Rate (ABR)
– guaranteed minimum capacity, with bursts

Guaranteed Frame Rate (GFR)
– like UBR/ABR, expressed in terms of frame rate

Unspecified Bit Rate (UBR)
– best-effort service
Chapter 13: ATM Traffic & Congestion Control
3
Why Typical Traffic Control
Schemes Are Inadequate for ATM



Majority of ATM traffic sources are timesensitive, and not amenable to typical flow
control schemes (e.g. CBR, rt-VBR)
For long-haul ATM: ttrans << tprop … slow
feedback (latency/speed effects)
Due to the broad range of ATM application
types, flow control may indiscriminately
penalize some
– bandwidth requirements (kbps to Mbps)
– traffic patterns (CBR, VBR)
– service requirements (delay/loss sensitivity)

Very high-speed switching increases volatility
re: control mechanisms
Chapter 13: ATM Traffic & Congestion Control
4
ATM Performance considerations

Two key issues must be addressed
for CBR and real-time VBR traffic…
– Latency/speed effects for long-haul
networks:
Cause - ttrans << 2 x tprop (or, one RTT)
Approach – fast feedback mechanisms
– Cell delay variation:
Cause - Variation at user-network interface
and in network core
Approach: time reassembly of CBR cells at
receiver
Chapter 13: ATM Traffic & Congestion Control
5
Latency/Speed Effects

Issue: rapid insertion rate of ATM cells vs.
relatively long round-trip delays
– small size (53 bytes) of ATM cell
– high bandwidth links in ATM networks
– small switching delays

Simplified Example:
–
–
–
–
150 Mbps data rate ( SONET OC-3)
tinsert = ttrans = 53 x 8 bits
= 2.8 x 10-6 seconds
6
150 x 10 bps
U.S. coast-to-coast roundtrip dprop = 48 msec
Then the number of cells inserted (N) during RTT =
48 x 10-3 seconds
4 cells = 7.2 million bits
=
1.7
x
10
2.8 x 10-6 seconds
Chapter 13: ATM Traffic & Congestion Control
6
Cell Delay Variation

General requirement: delay should be
short
– ATM designed to minimize delay
For some applications, rate of delivery
of cells to destination must be
constant (ATM’s CBR service level)
 Contributors to cell delay variation

– network contribution: queuing and
processing variations
– variation at UNI (user network
interface) due to cell processing
Chapter 13: ATM Traffic & Congestion Control
7
Origins of Cell Delay Variation
at UNI
Interleaving
prior to delivery
to physical layer
Further delays possible
at the physical layer
Chapter 13: ATM Traffic & Congestion Control
Per I-371
8
Cell Delay Variation: CBR Cells
 = 1/R = inverse of insertion rate
V(0) = est. tolerable delay variation
cell arrives late:
discarded
Slope = R cells/sec
= 1/ 
cell insertion rate
D(i) = end-to-end
delay for the ith cell
Chapter 13: ATM Traffic & Congestion Control
V(i) = V(i-1) – [ti – (ti-1 + )]
9
ATM Attributes
How we describe an ATM traffic flow
 Traffic parameters
 QoS parameters
 Congestion (for ABR)
 Other (for UBR)
Chapter 13: ATM Traffic & Congestion Control
10
Traffic Parameters

Connection Traffic Descriptor
– Source Traffic Descriptor: PCR, SCR,
MBS, MCR, MFS (more on next slide)
– Cell Delay Variation Tolerance (): upper
bound on amount of cell delay that is
introduced by the network interface and
the UNI (due to interleaving, physical
layer overhead, multiplexing, etc.)

Note- this is the value V(0) from our earlier
discussion of CDV
– Conformance Definition: unambiguous
specification of conforming cells of a
connection at the UNI (see GCRA, later)
Chapter 13: ATM Traffic & Congestion Control
11
Traffic Parameters

Source Traffic Descriptor
– Peak Cell Rate (PCR): upper bound on traffic
submitted by source (PCR = 1/T, where T =
minimum cell spacing
– Sustainable Cell Rate (SCR): upper bound on
average rate of traffic submitted by source
(over a larger T)
– Maximum Burst Size (MBS): maximum number
of cells sent continuously at PCR
– Minimum Cell Rate (MCR): used with ABR and
GFR… minimum cell rate requested, access to
unused capacity up to PCR (elastic capacity =
PCR-MCR?)
– Maximum Frame Size (MFS): maximum size of
a frame in cells available for GFR service
Chapter 13: ATM Traffic & Congestion Control
12
QoS Parameters
(negotiated between user and network during connection set-up,
as defined by the ATM Forum)
Peak-to-peak cell delay variation (CDV):
acceptable delay variation at destination
– the difference between the best case
and worst case CTD
 Maximum Cell Transfer Delay (maxCTD):
maximum time between transmission of
first bit of a cell at the source UNI to
receipt of its last bit at the destination
UNI
 Cell Loss Ratio: ratio of lost cells to
total transmitted cells on a connection

Chapter 13: ATM Traffic & Congestion Control
13
Cell Transfer Delay Probability
Density (real-time services)
Variable component of
delay, due to buffering
and cell scheduling.
Propagation
through
physical
media.
Chapter 13: ATM Traffic & Congestion Control
Fraction of cells that exceed
Maximum and will be
discarded or delivered late.
14
Congestion Control and Other
Traffic Attributes

Congestion Control
– defined only for ABR service category
– uses network feedback controls
– ABR flow control mechanism (more later)

Other Attributes (introduced July 2000)
– Behavior class selector (BCS):



for IP differentiated services (DiffServ)
provides for different levels of service among UBR
connections
implementation dependent, no guidance in specs
– Minimum desired cell rate (MDCR):

UBR application minimum capacity objective
Chapter 13: ATM Traffic & Congestion Control
15
Service Category-Attribute
Relationship
Chapter 13: ATM Traffic & Congestion Control
16
Chapter 13 – Section 2
ATM Traffic Control
(continued)
17
Traffic & Congestion Control
Function Classification – A
Framework
affect more than one connection,
effective over long timeframe
determine if/how network can
accommodate connection at a given QoS
network responds within the round-trip
lifetime of a cell
react immediately to a cell as it is
transmitted
Chapter 13: ATM Traffic & Congestion Control
18
Resource Management Using
Virtual Paths


Multiple VCCs with various QoS requirements in
same VPC
Cases to consider:
– User-to-User application: VPCs between pairs of
UNIs, VCC QoS is user’s responsibility… user must
ensure that aggregate of VCCs does not exceed
capacity allocated to VPC
– User-to-network application: VPC between UNI and
network node, network must accommodate QoS of
individual VCCs
– Network-to-network application: network must
accommodate QoS of individual VCCs
Chapter 13: ATM Traffic & Congestion Control
19
Resource Management Using
Virtual Paths


Performance (QoS) of a VCC depends on
resources allocated to the VPC(s) through
which the VCC extends
Network allocates capacity to each VPC based
on performance objectives agreed between
network and subscriber (contract). Two
approaches:
– Aggregate peak demand – VPC capacity (e.g. data
rate) set to sum of peak data rates of all VCCs
– Statistical multiplexing – VPC capacity set to be
greater than or equal to average demand for all
VCCs, but less than aggregate peak demand
Chapter 13: ATM Traffic & Congestion Control
20
Connection Admission Control
(CAC)

Network accepts the connection only
if it can commit resources - in both
directions - that satisfy a given
connection request:
1. Service category (CBR, rt-VBR, …)
2. Connection traffic descriptor (PCR, …,
CDVT, conformance definition)
3. QoS (peak-to-peak CDV, max CTD, CLR)
4. Cell loss priority (CLP bit 0 or 0+1)

If connection is accepted, a “traffic
contract” is awarded to the user
Chapter 13: ATM Traffic & Congestion Control
22
Connection Admission Control
(Traffic Contract)
(a.k.a. jitter)
Chapter 13: ATM Traffic & Congestion Control
23
Connection Admission Control
(CAC)
Contract
Contract
Contract
ATM Network
• Traffic Parameters
Peak cell rate
Sustainable cell rate
Burst tolerance
Etc.
• Quality of Service
Delay
Jitter
Cell loss
Chapter 13: ATM Traffic & Congestion Control
24
Usage Parameter Control
Purpose: after a connection is
established, protect the network’s
resources from overload/abuse by
violating connections
 Monitors connection for conformance
to the traffic contract

– detect violation of assigned parameters
based on conformance definition agreed
to in contract
– take appropriate action
Chapter 13: ATM Traffic & Congestion Control
26
Usage Parameter Control
Policing
Contract
You are
Not in Conformance
with the Contract.
What Should the
Penalty Be??
?DECISION?
REBEL
APPLICATION
Chapter 13: ATM Traffic & Congestion Control
ATM Network
• PASS
• MARK CLP BIT
• DROP
27
Usage Parameter Control
Function Location
Case 2
Case 1
Chapter 13: ATM Traffic & Congestion Control
28
UPC Traffic Management

Peak Cell Rate Algorithm
– Regulates the peak cell rate and the
associated CDVT of a connection

Sustainable Cell Rate Algorithm
– Regulates the sustainable cell rate and
associated burst tolerance of a
connection

Traffic Shaping
– Smoothes out traffic at network entry
points to reduce “clumping”
– Reduce delays, ensure fair resource
allocation
Chapter 13: ATM Traffic & Congestion Control
29
Generic Cell Rate Algorithm
(GCRA): Virtual Scheduling
Late
arrival
OK
GCRA (I, L):
I = Increment
L = Limit
ta(k) = Time of arrival of a cell
TAT = Theoretical arrival time
At time of arrival ta(1) of the first
cell of connection, TAT = ta(1)
Early arrival
beyond limit
NOT OK
Early arrival
TEST
I.e., this cell
arrived too late.
Early arrival
within limit
OK
Reset
TAT
Chapter 13: ATM Traffic & Congestion Control
 Algorithm takes two
arguments, I and L
 With PCR of R, I = T = 1/R
 CDVT limit,  = L
 Then peak cell rate
algorithm is expressed as:
GCRA(T, )
30
Effect of CDVT on Cell Arrival at UNI
(example: T=4.5)
Ideal ( = 0.5)
Possible ( = 1.5)
Cell Clumping
Possible ( = 3.5)
Note:

= T -

N = 1 + ( / T-)
Cell Clumping
Possible ( = 7)
Note:

> T -

N = 1 + ( / T-)
Chapter 13: ATM Traffic & Congestion Control
34
Sustainable Cell Rate Algorithm

Uses GCRA (Ts, s), where:
Ts = 1/Rs is the interarrival time at the
sustainable cell rate, Rs, and
s is the burst tolerance, or the time
scale during which cell rate fluctuations
(at PCR) are allowed
is derived from the burstiness of
the traffic stream:
 s
1
1
Burst Tolerance = s = (MBS-1)
SCR PCR
Chapter 13: ATM Traffic & Congestion Control
35
Sustainable Cell Rate Algorithm

Note that, if the traffic stream is
constrained by both GCRA (T, ) and
GCRA (Ts, s) , then Maximum Burst
Size (MBS) is:
s
MBS = 1 +
Ts-T
is derived from the burstiness of
the traffic stream:
 s
1
1
Burst Tolerance = s = (MBS-1)
SCR PCR
Chapter 13: ATM Traffic & Congestion Control
36
UPC Function: Possible Actions
based on CLP bit (dual CLP)
Forward
cell or
discard
it?
(see p. 377)
P? = Compliance test for parameter P
Chapter 13: ATM Traffic & Congestion Control
37
Token Bucket for Traffic
Shaping
Tokens are generated
and fill the bucket at
the constant rate, .
To pass, a token is
removed from the
bucket. If bucket is
empty, cell is queued to
wait for next token.
Departures rate is
“smoothed” to .
Chapter 13: ATM Traffic & Congestion Control
38
ABR Traffic Management
CBR, rt-VBR, nrt-VBR: traffic contract
with open-loop control
 UBR: best effort sharing of unused
capacity
 ABR: share unused (available) capacity
using closed-loop control of source

– Allowed Cell Rate (ACR): current max. cell
transmission rate
– Minimum Cell Rate (MCR): network
guaranteed minimum cell rate
– Peak Cell Rate (PCR): max. value for ACR
– Initial Cell Rate (ICR): initial value of ACR
Chapter 13: ATM Traffic & Congestion Control
39
ABR Traffic Management
ACR is dynamically adjusted based
on feedback to the source in the
form of Resource Management (RM)
cells
 RM cells contain three fields:

– Congestion Indication (CI) bit
– No Increase (NI) bit
– Explicit Cell Rate (ER) field
Chapter 13: ATM Traffic & Congestion Control
40
Flow of Data and RM Cells –
ABR Connection
Nrm parameter
usually set to 32
FRM cell flow

 BRM Cell flow
Chapter 13: ATM Traffic & Congestion Control
41
ABR Source Reaction Rules
NI CI
ACTION
0
0
ACR  max[MCR,min[ER,PCR,ACR+RIFxPCR]]
0
1
ACR  max[MCR,min[ER, ACR(1-RDF)]]
1
0
ACR  max[MCR,min[ER, ACR]]
1
1
ACR  max[MCR,min[ER, ACR(1-RDF)]]
RIF – Fixed rate increase factor (default 1/16)
RDF – Fixed rate decrease factor (default 1/16)
Chapter 13: ATM Traffic & Congestion Control
42
Variations in Allowed Cell Rate
RIF = 1/16
RDF = 1/4
Chapter 13: ATM Traffic & Congestion Control
43
ABR RM
Cell Format
Chapter 13: ATM Traffic & Congestion Control
44
Initial Values of Cell Fields
Chapter 13: ATM Traffic & Congestion Control
45
ABR Parameters
Chapter 13: ATM Traffic & Congestion Control
46
ABR Capacity Allocation

Two Functions of ATM Switches
– Congestion Control: throttle back on
rates based on buffer dynamics
– Fairness: throttle back as required to
ensure fair allocation of available
capacity between connections

Two categories of switch algorithms
– Binary: EFCI, CI and NI bits
– Explicit rate: use of the ER field
Chapter 13: ATM Traffic & Congestion Control
47
Binary Feedback Schemes

Single FIFO queue at each output
port buffer
– switch issues EFCI, CI, NI based on
threshold(s) in each queue

Multiple queues per port - separate
queue for each VC, or group of VCs
– uses threshold levels as above

Use selective feedback to dynamically
allocate fair share of capacity
– switch will mark cells that exceed their
fair share of buffer capacity
Chapter 13: ATM Traffic & Congestion Control
48
Explicit Rate Feedback Schemes
Basic scheme at switch is:

1.
2.
3.

–
–
–
compute fair share of capacity for each VC
determine the current load or degree of
congestion
compute an explicit rate (ER) for each VC and
send to the source in an RM cell
Several example of this scheme
Enhanced proportional rate control algorithm
(EPRCA)
Explicit rate indication for congestion avoidance
(ERICA)
Congestion Avoidance using proportional control
(CAPC)
Chapter 13: ATM Traffic & Congestion Control
49
EPRCA

Switch calculates mean current load on
each connection, called the MACR:
MACR(I) = (1-) x MACR(I-1) +  x CCR(I)
Note: typical value for  is 1/16

When queue length at an output port
exceeds the established threshold, update
ER field in RMs for all VCs on that port as:
ER  min[ER, DPF x MACR]
where DPF is the down pressure factor parameter,
typically set to 7/8.

Effect: lowers ERs of VCs that are
consuming more than fair share of switch
capacity
Chapter 13: ATM Traffic & Congestion Control
50
ERICA

Makes adjustments to ER based on
switch load factor:
Load Factor (LF) = Input rate /Target rate
where input rate is averaged over a fixed interval,
and target rate is typically 85-90% of link
bandwidth

When LF > 1, congestion is threatened,
and ERs are reduced by VC on a fair
share basis:
– Fairshare = target rate/number of VCs
– Current VCshare = CCR/LF
– newER = min[oldER, max[Fairshare, VCshare]]
Chapter 13: ATM Traffic & Congestion Control
51