Back to index
Credit-Based Flow Control for ATM Networks: Credit Update Protocol,
Adaptive Credit Allocation, and Statistical Multiplexing
H.T. Kung, Trevor Blackwell, Alan Chapman, Harvard Univ. and Bell
Per-VC credit-based flow control in which credit and bandwidth
allocations adapt dynamically to offered load. The use of
adaptive flow control for statistical multiplexing of traffic through a
switch keeps switch buffer requirements modest (RTT x O(1), as
opposed to RTT x peak BW) and cell loss low.
- Why to use credit based flow control per VC (virtual ckt):
- "fill in" traffic to use surplus capacity after guaranteed
traffic has been scheduled
- Data to be used for "fill in" must be "drawn" to switches
with excess capacity early enough to fill in the excess,
but don't want to draw excess traffic (resulting in
- congestion control via backpressure per VC doesn't affect
throughput of noncongested VC's
- The "N23" credit-based flow control scheme:
- Roughly, N2 is amount of "steady state" buffering
available per VC at receiving switch; N3 is
"overflow" buffering for excess traffic. N2
generally stays fixed, N3 may be varied over life of VC.
The larger N2 is, the more resilient the VC is to
short-term load fluctuations.
- N3 chosen as Bvc x RTT, where
Bvc is targeted average bandwidth of this VC.
- When sender receives "credit update" C from
receiver, new credit is computed as C-E, where E is number
of cells sent in last RTT (i.e. number of cells in flight
when update received)
- Properties of N23 scheme:
- No data overflow, as long as corrupted credit updates can
- Self-repairing as long as corrupted credit updates are
- Average BW achievable over one RTT is at most
- Credit update protocol (CUP): a simple hardware implementation of
- Receiver sends credit update; sender computes new credit
as N2+N3-(Vs-Vr), where Vs is number of
cells sender has forwarded or dropped, and Vr is number of
cells receiver has forwarded (enclosed in update).
- Note Vs+Vr=B+E, where B is the number of cells in the
receiver's buffer when update leaves receiver, and E is as
- Each receiver also keeps running total U of all data cells it
has received. "Periodically" (an engineering
choice) each sender transmits its current Vs, and the
receiver computes the number of lost cells as Vs-U, then
increments U and Vr by this value.
- Adaptive credit allocation:
- Size of shared buffer pool is r x RTT, where
- Each VC wants to get C=B x RTT, where C is its
credit and B its operating bandwidth over some measurement
interval M (paper assumes M=RTT for simplicity).
- Each VC's credit allocation is always strictly larger than
its operating credit by a factor of r'>=r>1 (to
allow "headroom" for fast credit growth).
- Suppose the shared buffers are not completely full when
credit reallocation occurs. VC's experiencing ramp-up in
bandwidth can grow their share of allocation by a factor
of up to r per reallocation, i.e. exponential ramp up
(like TCP slow start).
- Suppose shared buffers are completely full when
reallocation occurs: so we should consider only the
shared buffer size minus the in-flight cells.
- Parameter r can be reduced dynamically as each VC's
operating credit approaches its target bandwidth. There
is also a parameter a that defines the cutoff of a
low-pass filter, which insulates N3 from rapid
fluctuations in bandwidth. The choice of both of these is
"an engineering choice" -- no details are given.
- Adaptation can be sender- or receiver-based. Receiver
based allows quick adjustment of N3: since N3 is a
receiver-only parameter it can just be changed locally as
desired. But receiver-oriented implies that ramp-up will
be delayed by about 1 RTT.
- Per-VC flow control enables statistical multiplexing of the
shared buffer, helping to minimize its size. Under low to
moderate congestion, very few cells lost; under heavy congestion,
cells get lost.
- Assumption: all N VC's have identical loads, involving
bursts of B cells with exponentially distributed
- Assumption: shared buffer pool size is
M=b x N x B cells, where b<1 is the
"memory reduction factor" due to statistical multiplexing.
- Simulation 1: link utilization, number of cell delays, and
number of dropped cells as function of N3, with B=172,
N=100, M=4096, offered load=0.95, RTT=3200 cell times.
utilization quickly reaches 1.0 and stays there; at about
N3=100, number of dropped cells starts to climb, since
statistical multiplexing starts to break down.
- Simulation 2: same, but with unlimited memory size, also
plotting max memory usage as function of N3. Result:
same, but memory usage grows slowly up to about N3=80,
then slope takes off, again as statistical multiplexing
begins to fail.
- Simulation 3: goal is to show that the same throughput
and rate of cell loss can be achieved with less memory
(i.e. lower b) if per-VC flow control is used than if it
is not. Duh. Result is that adaptive FC can pin b to
- Simulation 4: shows fast adaptation. N3 value at
receiving switch tracks N3 at sending switch with a delay
of about 4000-5000 cell times, i.e. about 1.5 RTT, as
How to use fast adaptive credit based FC to get proportional share
credit allocation (and therefore capacity/BW utilization) for multiple
VC's. Implementation requires 3 state counters per VC and is robust to
corrupted credit cells.
- The parameters r and a, and the manner and frequency with which
they can be varied over time, seem critical to the stability and
responsiveness of the algorithm, yet all the authors say is that
they are "engineering choices". Bah.
- "Burstiness at all timescales" calls simulated load
- Are the counters required by their implementation soft or hard
state? If soft state, how is the credit computed at time
t=0, and what effect on the VC (and other VC's) is seen if the
state is lost
during the connection?
Back to index