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 equal bandwidths
• 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 to 1/sqrt(p)
  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.

Test Scenarios

• 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 (flash crowds.
  
• Need to also consider relative bandwidth fairness of SlowCC mechanisms with
• 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 per rtt.

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 rtt.
  
• 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 previous rtt.
  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 rate.

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 to change.
  
• 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.

Potential Beneifits

• 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 considerably worse.

Thu, 7 August, 2003 3:25