1、An overview and a proposal Jan 24, 2007,Balaji Prabhakar,Balaji Prabhakar Stanford University,2,Outline,A framework for congestion control research Widely used in the academic world Simulations, analysisDiscussions of BCN and ECNProposal: A simple scheme Combining BCN with (F)ECN,3,A framework for c
2、ongestion control,Goals of congestion control scheme High throughput, low latency/loss, fair, robust, and simpleThe steps in the framework Stability analysis: Need to ensure high utilization and non-oscillatory queues. The “unit step response” of the network. If the switch buffers are short, oscilla
3、ting queues can overflow (hence drop packets/pause the link) or underflow (hence lose utilization) In either case, links cannot be fully utilized, throughput is lost, flow transfers take longerDynamic (realistic) loading: Interested in flow transfer time How quickly does network transfer flows/files
4、?In addition to theory, extensive simulations of 1 and 2, usually using ns-2,4,TCP-RED: The prototypical control loop,TCP: Slow start + Congestion avoidanceCongestion avoidance: AIMD No loss: increase window by 1; Pkt loss: cut window by half,5,TCP-RED: Analytical model,6,TCP-RED: Analytical model,W
5、: window size; RTT: round trip time; C: link capacity q: queue length; qa: ave queue length p: drop probability,Users:,Network:,*By V. Misra, W. Dong and D. Towsley at SIGCOMM 2000 *Fluid model concept originated by F. Kelly, A. Maullo and D. Tan at Jour. Oper. Res. Society, 1998,7,Accuracy of analy
6、tical model,8,Delay at Link 1,9,Accuracy of analytical model,10,Accuracy of analytical model,11,TCP-RED: Stability analysis,“Linearize and analyze” Linearize equations around the (unique) operating point Analyze resultant linear, delay-differential equations using Nyquist or Bode theoryEnd result: D
7、esign stable control loops Obtain control loop parameters: gains, drop functions, ,12,Instability of TCP-RED,As the bandwidth-delay-product increases, the TCP-RED control loop becomes unstableParameters: 50 sources, link capacity = 9000 pkts/sec, TCP-RED Source: S. Low et. al. Infocom 2002,13,Flow-l
8、evel Models,14,Flow-level Models,This type of traffic is more realistic: flows, of differing sizes, arrive at random times and are transferred through the network by the congestion management algorithms and transport protocols Flow completion (transfer) time is the main quantity of interest: what is
9、 its mean? variance? how does it depend of flow sizes? on network topology, on round trip time, etc?,15,Flow-level models: Simulation,10Mbps,10Mbps,grp3,arrival rate: 60flows/sec propagation delay: 150msec # of packets/flow Pareto,DropTail / RED,16,Layer 2 Congestion Control,17,BCN and (F)ECN,BCN ha
10、s been tested extensively in the previous framework For details see: Y. Lu, R. Pan, B. Prabhakar, D. Bergamasco, V. Alaria, A. Baldini, “Congestion control in networks with no congestion drops,” invited paper, Allerton 2006, September, Urbana-ChampaignAvailable at: http:/simula.stanford.edu/luyi/ an
11、d at http:/www.ieee802.org/1/files/public/docs2006/au-Lu-et-al-BCN-study.pdf,18,Some observations about ECN,19,ECN,Stands for Explicit Congestion Notification (not to be confused with ECN from the Internet context) Proposed by Prof Raj Jain at the Nov 2006 Dallas meetingIt would be great to apply th
12、e previous framework to ECN, but We have only managed some simulations And a basic control analysisHowever, I do have a couple of observations Theyre interesting, fundamental, and puzzling: need to understand more,20,The ECN scheme,The main ideas are switches estimate and advertise the current fair
13、rate to the sourcessources transmit at this rate until the advertisement changeseach source has a switch on its path whose advertisement it obeys: the one which advertises the minimum rate the key component is the rate estimation algorithmRate estimation scheme: consider N sources passing through a
14、link of capacity C at a switch Time is slotted, each slot is T secs long During slot k, the advertised rate is rk,. ideally, rk = C/N The rate of arrivals during slot k is Ak qk is the queue size at the end of slot k Let f(qk) be an decreasing function of the queue size rk is then recursively estima
15、ted as follows (new version has some enhancements),21,The ECN scheme,22,Well,Eqn (1) is multiplicative, eqn (2) is linear in A - C, which is approximately equal to rate of change of queue g(q) is linearly increasing in q when f(q) is hyperbolic!In other words ECN feeds back the state (which is queue
16、-size and its derivative) multiplicatively while BCN feeds it back linearlyMultiplicative feedback isnt common in control theory In fact, the Internet controllers PI and REM are also linear in the state Thus, these well-studied controllers they are almost identical to BCNMultiplicative feedback need
17、s to be better understood Being non-linear, it is susceptible to measurement noise in rate estimation and packet sampling, and to instability under delay At is stage, we need to crack open a couple of differential equations -:) But, we did some ns-2 simulations of ECN to test its sensitivity,23,Simu
18、lations of ECN,Using ns-2 New rate averaging enhancement included New and increased measurement interval = 1 msec Hyperbolic drop function; values from Prof Jains Nov presentation Scenario: from Prof Jains on/off loading model in Nov presentation,24,ECN with smaller r0,25,BCN in same scenario and bi
19、gger delays,26,BCN queue depths,27,BCN individual rates,28,What happened to ECNs control loop?,The nonlinearity has some serious consequences (thanks Rong Pan and Ashvin Lakshmikantha)It makes qeq a parameter of the control loop! That is, the bigger qeq is, the more stable it is! This is not true of
20、 BCN (or other Internet controllers like PI and REM) And is entirely because ECN multiplies state, while BCN and the others add If this is true, we should be able to increase qeq in the previous setup and stabilize ECN,29,Throwing buffers to buy stability,30,About fairness,Fairness is a key metric,
21、along with high throughput and low backlogs There is always a higher price to pay for fairness in terms of algorithm complexity. Why?Consider example below: 2 links, each with capacity = 1,Max ThroughputTotally unfair,Max-min FairVery fair Reduced Tpt,Proportionally fairFair Higher Tpt,1,1,0,1/2,1/2
22、,1/2,1/3,2/3,2/3,31,Complexity and fairness,From J. Mo and Walrand (1998):,32,Other issues,Measurement interval: Cant be long or short! Gone up to 1 msec from 30 musecs in Nov 2006 Short interval: Noisy estimation hurts stability Rate estimation is noisy, long interval helps convergence Cant signal
23、too many sources (30 musecs = 30 1500B pkts) Long interval: Not responsive, need buffers to store changes Rate estimation is accurate, but cant be very responsive New sources will get old rate for 1 msec; switch needs to absorb extra pkts with bigger buffers Need 32 bits to signal rate in fine detai
24、l Cannot give flows one of, say, 16 or 32 levels Because every flow needs to send at exactly the same rate; rate differences are not allowed! Quantization will lead to less total arrival rate at one level and to higher rate at the next one upPossible security issue: Network advertising rate explicit
25、ly on bottleneck links invites attacks!,33,Summary on ECN,Nonlinear feedback of state is very uncommon In this case leads to serious control problem: stability needs big buffers This is not true of BCN (or other Internet schemes like REM and PI)Max-min fairness is complex whichever way you try to do
26、 it No distributed, low communication overhead algorithm known to date Equivalent to per-flow workMeasurement interval cannot be chosen painlesslyNeed detailed rate signaling capability, a 4 or 5 bit signal is not sufficientPossible security issue: Network advertising rate explicitly on bottleneck l
27、inks invites attacks!,34,A proposal: Combining BCN and (F)ECN,35,Proposal: A Simple Algorithm,Use BCNs control loop Proven to be stable Extensive work on REM and PI which are exactly like BCN (see below) in the Internet context, shows their stability and low backlogsBCN generates extra signaling tra
28、ffic Hence sampling probability is kept at 1%; this can go up to 10% and improve responsiveness by a lot But, if forward signaling is possible, or another means of signaling more frequently can be found, then we can send less information per signalMain ideas Compress and quantize BCN signals at swit
29、ch: a 4-bit quantization works great This multi-bit signal can be trivially looked up in a table at the source and generates sources reaction (rate decrease/increase) Let source increase rate multiplicatively and let switch only send decrease signals,36,Details of the simple algorithm,Need a name DC
30、N? For Distributed Congestion Notification D is between B and FE Deccan is part of India Im from -:) QCN? For Quantized Congestion Notification Quicken Recall: In the current BCN The CP sends: Qoff and Qdelta The RP: Computes Fb = -(Qoff + w* Qdelta) If Fb 0, then R - R + Gi Fb Ru If Fb 0, then R -
31、R (1+Gd Fb) Note: only Fb is used in the rate computations! No need to send Q and Qdelta Fb is exactly the quantity used by REM and PI to mark packets at router, instead of the RED drop functionSo, let switch compute Fb (very easy, esp because w is a power of 2, usually w = 2) Quantize Fb to one of
32、4 or 5 bit levels and send to source,37,Details of the simple algorithm,QCN: control algorithm Swtich On sampled packets switch computes Fb (very easy, esp because w is a power of 2, usually w = 2) Switch quantizes Fb to one of 4 or 5 bit levels and send to source Source Reacts appropriately by usin
33、g Fb to index a lookup table Periodically (when timer expires) increases its rate multiplicativelyNotes All parameters chosen already, as in WG discussions Quantization can be uneven (nonuniform quantization): more decrease levels, different spacing, etc Simulations show that 4-bit quantization is n
34、early similar to full signaling,38,Why not send increase signals?,Switch signals only rate decreases, source performs multiplicative rate increases. This has a few benefits: It gets rid of the sampling bias problem; i.e. no rate increases to already large flows More importantly, it gets rid of the R
35、P-CP association; if no CP is going to send an RP rate increase messages, then there is no need for the RP to store the id of last CP which signaled a decrease or to send this id out on packet headers. Finally, there is a reduction in signaling traffic. Note: we may still want to keep 1 or 2 increas
36、e signals because a switch can more quickly utilize its links,39,Performance of simple version,Theoretically, neither feature affects the stability of the system; the stability margin is lowered a little, not the stability property Because feedback is linear, quantization noise moves the poles by a
37、small amount depending on the granularity of quantization; thus, the stability margin is slightly affected, not the stability itself.Simulation evidence: The following tests have been done till now (and will be exhibited in the next few slides). Davide Bergamasco has tried out, on his simulator, a 6
38、-bit quantized version of BCN on the baseline scenario discussed in the WG. The performance is nearly indistinguishable; the quantized version is slightly wiggly. Ashvin has generated plots comparing the 5-bit quantized version to BCN for “on/off inputs.” Abdul has compared the 5-bit quantized versi
39、on to BCN using flow-level models. Grand conclusion: The simple version compares v.favorably.,40,Baseline scenario: 6-bit quantization,41,On/off sources: 5-bit quantization,42,Flow-level models: 5-bit quantization,Simulation setup Hyper-exponential with mean of 50 packets SF: Short flows - Mean size
40、: 20 pkts LF: Long flows - Mean Size: 320 pkts 10% Long flows Sampling rate: 0.03 Single link, IEEE parameters FCT measured in milliseconds,43,Ave flow completion time,Load,FCT (millisecs),44,FCT ave for long and short flows,Load,FCT (millisecs),45,With no switch signaled increases,Load,FCT (millise
41、cs),46,With no switch signaled increases,Load,FCT (millisecs),47,Thanks for listening Thanks again to Rong Pan, Ashvin Lakshmikantha, Abdul Kabbani, and Davide BergamascoOverviewed Internet research Fairly substantial, vibrant literatureL2 Congestion Control Presented some work on BCN Some observations about ECN Proposed QCN, combines BCN and (F)ECNWelcome your feedback,Conclusions,
