Understanding TCP Vegas: A Duality Model

Steven Low, Larry Peterson and Limin Wang

ACM/SIGMETRICS 2001, Boston, MA

• Background Knowledge
• Modeling Vegas
• Simulation Results
• Discussion

Background

• TCP Vegas: A window based congestion avoidance algorithm
• Try to maintain a target buffer occupancy at the bottleneck
• At steady state, do threshold-based AIAD control over the congestion window
• Go back to normal AIMD TCP control over when losses are detected
• How to estimate the bottleneck buffer occupancy? -- Through difference between RTT and the propagation delay (estimated from the smallest RTT)
• Constrained Optimization Problem:
• Form of the problem:
• Objective: maxmize/minimize certain objective function
• Constraints: variables can only take limited values
• Example:     max   x_1 + 4x_2 + 3(x_2 - x_3)^2        (f(x))
s.t.    x_1 +               x_3  <= 5            (c1(x) <= d1)
                      x_2  + x_3   <= 4           (c2(x) <= d2)
                                   x_i    >= 0           (c3(x) <= d3)
• One way to solve it: Lagrangian relaxation:
• Define Lagrangain:  L(x, y) = f(x) + \sum y_i * (d_i - c_i(x))
• Basic idea - define a new function that takes care of both the objective and the constraints
• y_i's are called Lagrangain multipliers whose values decide how critical the conresponding resources are
• y_i = 0 if c_i(x) < d_i  (non-bottleneck resources)
• The Primal-Dual approach
• It turns out that x_i's and y_i's are dual variables. It's easy to transform the original (primal) problem into a new (dual) problem in which y_i's become variables and x_i's become the multipliers
• Solving either problem will achieve same result
• Modeling Internet as a dynamic system:
• Approach 1 (by Frank Kelly) -- Game theoretic approach
• Users control their behavior (willingness to pay) to maximize their individual object functions
• Network determine usage-based price scheme to maximize the social welfare function (sum of user utilities)
• Approach 2 (by Steven Low) -- formalized as Constrained Optimization problem
• Primal problem -- centralized approach -- maximize global objective function (sum of utility functions)
• Dual problem -- distributed approach -- users perform individual control over the sending rate given that price scheme is known in advance
• Solving Dual problem is equivalent to solving the primal problem
• Common: Pricing is implemented by Active Queue Management + ECN
• Difference: the way price (congestion) information is encoded (RED vs. REM)
• Applications: TCP Reno/DropTail, Reno/RED, Reno/REM, Vegas/RED, Vegas/REM
• What is REM (Random Exponential Marking)?
• REM is nothing new but just an approach to convey non-additive path price information to the user
• E.g., assume user cares about packet losses, and loss rate is not additive metric unless it is extremely small
• REM is designed for such information:
• say link loss rates are p1, p2, p3, ..., pn
• want to know \sum p_i, but we can only observe total loss/mark rate TR
• trick: mark (through ECN) packets at a rate R_i = 1 - e^p_i
• So the total marking rate TR = \sum R_i = 1 - e^\sum p_i
• Basic idea: transform original price information
• Additional benefit for Vegas control (will see it later): decouples price from delay estimation

Special Case: Vegas algorithm

• Does Vegas algorithm provide optimal solution to the defined problem?
• It does if the utility function is of the form U(x) = a d log x, where d is the propagation delay, 'a*d' is the objective buffer occupancy
• Also, under ideal conditions (accurate and immediate price information), it converges to the proportional fair equilibrium
• The problem of Vegas
• Coupling of price and delay estimation if the bottleneck queue does not do anything
• Without AQM, the price is delivered in the form of end-to-end queueing delay
• Queueing delay estimation is subject to errors that can come from many forms (persistent congestion, route change, etc.)
• Errors (noises) could affect the point at which the system equilibrium is achieved
• How does AQM help?
• REM queue + ECN + PI controller
• ECN is exclusively used for price information notification (so it should really been called Instantenous Bill Notification instead of Early Congestion Notification)
• PI (Proportional, Integral) controller (recall Hollot, Misra, Gong and Towsley's work) is used to maintain the bottleneck queue occupancy at 0
• REM queue mechanism guarantees correct estimation at the end-system

Results (Analytical/Numerical/Simulation/Experimental)

• Basically they validate their analysis

Discussion

• What if there's delayed feedback and non-synchornized sources?
• ...