17th June 2002
Notes for Dynamic Behavior of Slowly-Responsive Congestion Control Algorithms
Intro and Congestion Control Algorithms
- TCP congestion control - similarly situated end systems receive roughtly
- TCP does not assure equality of bandwidths for systems with different
rtts, or with mulitiple congest hosts, or packet size
- Equitable (ie fair)
- Bandwidth allockations function of congestion control mechanism used
- Unicast streaming apps best served by congestion contsols that are
slowly responding to congestion, ie smoother bandwidth usage profile
- Use constant pckate loss rate p - first order, bandwidth proportional
These are slowly responsive to packet loss
- Congestion control: TCP-equivalent, TCP-compatible or not TCP-compatible
based on steady state behavior.
- End-to-end: slowly-responsive, responding faster than TCP
- Cc algorithm TCP equivalent if it uses AIMD (eg RAP)
- Cc algorithm TCP-compatible if it displays cc on timescales of several
rtt with same throughput as TCP in steady state
- Slowly responsive if window of rate reduction on a single packet loss
or congestion notification is smaller than TCP
- Slowly-responsive Congestion Control (SlowCC) benefits from smoother
sending rate (eg TFRC)
- Not considered in CC mechanism: slow start procedure and exponential
backoff of the retransmit timer
- AIMD uses two parameters - a and b.
- Standard: loss: W->(1-b)W and no loss: W->W+a per rtt
- For TCP compatible, a=4(2b-b^2)/3
- Slowly-responsive AIMD algorithm: b<0.5
- Binominal CC algorithms: loss: W->W-b(W^l) , no congestion: W->W+a/(w^k)
- Binominal CC is TCP compatible if an only if k+l=1 and l<=1. Slow
responsive if for a and b, l<1;
- For binominal algorithms, smaller values of l: more slowly responsive
- TFRC responds to loss over some period of time. Uses response function
characterizing TCP sending rate as func of loss rate and rtt.
- TEAR receiver based variant of TCP. Keeps TCP Congesion window unchanged
and then averagest the current window.
- Need systematic way of characterisng aggressiveness and responsiveness.
- Stabilization time: time for packet loss rate to stabilize after the
start of a sustained period of high congestion - where packet loss rate
has stabilized if it is within 1.5 times its steady state value at congesteion.
- Need consider extremes: CBR periodic on/off and saw tooth background
- Need to also consider relative bandwidth fairness of SlowCC mechanisms
- TCP under these conditions as function of magnitude and freq of oscillations
in avail bw.
- Delta-fair convergence time: time take by two competing flows using
same CC mechanism but starting with unequal stares of the link bandwidth
to go from (B-b,b) to ((1+delta)B/2, (1+delta)B/2)
- Concern of SlowCC in temporary under utilized links, resulting form
slowness of SlowCC mech in taking advantage of sudden increase in avail-bw
- f(k): fraction of bandwidth achieved by a cc mech in first k rtts
after available bw has doubled.
- Smoothness metric: (TRFC) longest ratio between the sending rates
in two consecutive rtts.
- Responsiveness: number of rtt of persistent congestion until the sender
halves its sending rate - persistent congestion: loss of one packet
Slowly Responsive Results
- SlowCC could cause high packet loss rates for extended periods of
time. High drop rates results in unnecessary increase in response times
for other flows
Stabilization time: number of rtts, after period of high congestion,
until network loss rate goes down to 1.5 times its steady-state value.
- Stabilization cost: product of the stabilization time and the average
loss rate (in perc) during the stabilization interval. Quanitfies true
effects of persistent overload. CC mech with stabilization cost of 1
corresponds to entire rtt worth of packets dropped at the congested
link during stabilization period.
- RAP and TRFC are rate based: only transmit data based on rate determined
by AIMD algorithm irrespective of number of ACKS. ACKs start arriving
only at the rate currently available to the flow at bottleneck and sending
rate is therefore limited to the bottleneck (ACK) rate from previous
- TRCC without self-clocking: limits the senders sending rate to at
most twice the rate at which data is received by the receiver in the
TRFC with self-clocking: for rtt following a packet loss, conservative_
option limits the senders rate to at most the rate at which data is
received by thee receiver in the previous rtt (ie rtt containing loss).
- TRFC with self clocking: also need to limit the amount by which the
sending rate can exceed the receive rate even in the absence of loss.
When not in slow-start, conservative_ pegs TRFC's max sending rate to
at most a constant C times earlier recv_rate. So under period of heavy
loss, option causes sending rate to immediate reduce to the reported
Drawbacks of Slowly-Resposive Algorithsm
- Consider unfaireness with respect to TCP and each other and potential
bottlenecks in utilisaiton
- Consider changing frequency of ON/OFF CBR flow, measure the effect
on bandwidth on the different types
- Varying network conditions favour standard TCP due to quickly it quickly
getting the avail-bw.
- Over short period of time (slike after a reducting in the available
bandwidth) TRFC flows may get higher throughput than TCP, but TCP in
long run is more competitive - response of SlowCC not take advantage
- f(k): average link utilisaiton (expresses as fraction) over the first
k rtts after the bw has doubled.
- See how much utilization as a result of stopping half of the flows
for various number of packets.
- Consider flow subjected to loss pattern of three losses each after
50 packets arrivals, followed by three more losses, each after 400 packet
arrivals: TRFC smoother and slightly higher in bandwidth.
- More bursty: six second low congestion phase where every 200th packet
is dropped, followed by a one second heavy congestion pahse where every
4th packet dropped. Heavy congestion phase includes 6 loss intervals,
TRFC looses all memory of earlier low congestion periods. TRFC performs
Thu, 7 August, 2003 3:25
|© 2001-2003, Yee-Ting Li, email: email@example.com,
Tel: +44 (0) 20 7679 1376, Fax: +44 (0) 20 7679 7145
Room D14, High Energy Particle Physics, Dept. of Physics & Astronomy,
UCL, Gower St, London, WC1E 6BT