Convex Optimization - THUxukeGroupnonlinear convex optimization (Nesterov&Nemirovski 1994) applications before 1990: mostly in operations research; few in engineering since 1990: many

Convex Optimization TCP Duality Rethinking Internet Traffi c Management SPEF: Optimal TE with OSPF P2P Traffic Optimizat ion

Convex Optimization

Instructor: M�Dep. of CS & T

Tsinghua University

May 10, 2012

Instructor: MMM�� OOO��ÅÅÅ��äää ÷÷÷ïïïÄÄÄConvex Optimization

Convex Optimization TCP Duality Rethinking Internet Traffi c Management SPEF: Optimal TE with OSPF P2P Traffic Optimizat ion

Outline

1 Convex Optimization

2 TCP Duality

3 Rethinking Internet Traffic Management

4 SPEF: Optimal TE with OSPF

5 P2P Traffic Optimization


Convex Optimization TCP Duality Rethinking Internet Traffic Management SPEF: Op timal TE with OSPF P2P Traffic Optimization

Outline


2 TCP Duality






Mathematical optimization

(mathematical) optimization problem

minimize f0(x)subject to fi(x) ≤ bi , i = 1, ...,m

(1)

x = (x1, ..., xn) : optimization variables

f0 : Rn → R : objective function

fi : Rn → R, i = 1, ...,m : constraint functions

optimal solution x⋆ has smallest value of f0 among all vectorsthat satisfy the constraints



Solving optimization problems

general optimization problem

very difficult to solve

methods involve some compromise, e.g., very longcomputation time, or not always finding the solution

exceptions:certain problem classes can be solved efficiently andreliably

least-squares problems

linear programming problems

convex optimization problems



Least-squares

minimize ‖Ax − b‖22 =k∑

i=1(aT

i x − bi)2 (2)

solving least-squares problems

analytical solution: x⋆ = (AT A)−1AT b

reliable and efficient algorithms and software

computation time proportional to n2k(A ∈ Rk×n);less ifstructured

a mature technology

using least-squares

least-squares problems are easy to recognize

a few standard techniques increase flexibility (e.g., includingweights,adding regularization terms)



Linear programming

minimize cT xsubject to aT

i x ≤ bi , i = 1, ...,m(3)

solving linear programsno analytical formula for solutionreliable and efficient algorithms and softwarecomputation time proportional to n2m if m ≥ n; less withstructurea mature technology

using linear programmingnot as easy to recognize as least-squares problemsa few standard tricks used to convert problems into linearprograms (e.g., problems involving ℓ1− or ℓ∞− norms,piecewise-linear functions)



Convex optimization problem

minimize f0(x)subject to fi(x) ≤ bi , i = 1, ...,m

(4)

objective and constraint functions are convex:

fi(αx + βy) ≤ αfi(x) + βfi(y)

if α+ β = 1, α ≥ 0, β ≥ 0

includes least-squares problems and linear programs asspecial cases



solving convex optimization problems

no analytical solution

reliable and efficient algorithms

computation time (roughly) proportional tomax{n3, n2m,F},where F is cost of evaluating fi ’s and theirfirst and second derivatives

almost a technology

using convex optimization

often difficult to recognize

many tricks for transforming problems into convex form

surprisingly many problems can be solved via convexoptimization



Example

m lamps illuminating n (small, flat) patches

intensity Ik at patch k depends linearly on lamp powers pj:

Ik =m∑

j=1akjpj , akj = r−2

kj max{cos θkj , 0}

problem : achieve desired illumination Ides with bounded lamp powers

minimize maxk=1,...,n| lg Ik − lg Ides |subject to 0 ≤ pj ≤ pmax , j = 1, ...,m



how to solve?

use uniform power: pj = p, vary p

use least-squares:

Minn∑

k=1(Ik − Ides)

2

round pj if pj > pmax or pj < 0

use weighted least-squares:

Minn∑

k=1(Ik − Ides)

2 +m∑

j=1wj(pj − pmax/2)2

iteratively adjust weights wj until 0 ≤ pj ≤ pmax

use linear programming:

minimize maxk=1,...,n|Ik − Ides |subject to 0 ≤ pj ≤ pmax , j = 1, ...,m

which can be solved via linear programming



how to solve?(Cont.)

5. use convex optimization: problem is equivalent to

minimize f0(p) = maxk=1,...,n h(Ik/Ides)subject to 0 ≤ pj ≤ pmax , j = 1, . . . ,m

with h(u) = max{u, 1/u}

f0 is convex because maximum of convex functions is convexexact solution obtained with effort ≈ modest factor × least-squareseffort



additional constraints:does adding 1 or 2 below complicate the problem?

1. no more than half of total power is in any 10 lamps2. no more than half of the lamps are on (pj > 0)

answer: with (1), still easy to solve; with (2), extremely difficult

moral: (untrained) intuition doesn’t always work; without theproper background very easy problems can appear quitesimilar to very difficult problems



Nonlinear optimization

traditional techniques for general nonconvex problems involvecompromiseslocal optimization methods (nonlinear programming)

find a point that minimizes f0 among feasible points near it

fast, can handle large problems

require initial guess

provide no information about distance to (global) optimum

global optimization methods

find the (global) solution

worst-case complexity grows exponentially with problem size

these algorithms are often based on solving convex subproblems



Brief history of convex optimization

theory (convex analysis): ca1900õ1970algorithms

1939: the mathematical technique now known as linearprogramming(Leonid Kantorovich)

1947: simplex algorithm for liner programming(Dantzig)Leonid Vitaliyevich Kantorovich(1912-1986) was a Soviet/Russianmathematician and economist.He came up (1939) with the mathematicaltechnique now known as linearprogramming, some years before it wasreinvented and much advanced by GeorgeDantzig.He was the winner of the NobelPrize in Economics in 1975.



Brief history of convex optimization (Cont.)

theory (convex analysis): ca1900õ1970algorithms

1939: the mathematical technique now known as linearprogramming(Leonid Kantorovich)1947: simplex algorithm for liner programming(Dantzig)1960s: early interior-point methods(Fiacco&McCormick)1970s: ellipsoid method and other subgradient methods

In 1947 George Dantzig formulatedthe linear programming problem asa mathematical model for theplanning problem and devised thesimplex method for its solution,whichled to his titles as the/father oflinear programming0and the/inventor of the simplex method.0



Brief history of convex optimization (Cont.)

algorithms

1980s: polynomial-time interior-point methods for linearprogramming (Karmarkar 1984)

late 1980sõnow: polynomial-time interior-point methods fornonlinear convex optimization (Nesterov&Nemirovski 1994)

applications

before 1990: mostly in operations research; few inengineering

since 1990: many new applications in engineering (control,signal processing, communications, circuit design,...)



Affine set

line through x1, x2: all points

x = θx1 + (1 − θ)x2

affine set: contains the line through any two distinct points in thesetexample: solution set of linear equations {x |Ax = b}(conversely, every affine set can be expressed as solution set ofsystem of linear equations)



Convex set

line segment between x1, x2: all points

x = θx1 + (1 − θ)x2

with 0 ≤ θ ≤ 1

convex set: contains line segment between any two points

x1, x2 ∈ C, 0 ≤ θ ≤ 1⇒ θx1 + (1 − θ)x2 ∈ C

examples(one convex, two nonconvex sets)



Convex combination and convex hull

convex combination of x1, ..., xk : any point x of the form

x = θ1x1 + θ2x2 + · · ·+ θk xk

with θ1 + θ2 + · · ·+ θk = 1, θi ≥ 0

convex hull conv S: set of all convex combinations of points in S



Convex cone

conic (nonnegative) combination of x1 and x2: any point of the form

x = θ1x1 + θ2x2

with θ1 ≥ 0, θ2 ≥ 0

convex cone: set that contains all conic combinations of points inthe set



Hyperplanes and halfspaces

hyperplane: set of the form {x |aT x = b}(a , 0)

halfspace: set of the form {x |aT x ≤ b}(a , 0)

a is the normal vector

hyperplanes are affine and convex; halfspaces are convex



Norm balls and norm cones

norm : a function ‖ · ‖ that satisfies

‖x‖ ≥ 0; ‖x‖ = 0 if and only if x = 0

‖tx‖ = |t |‖x‖ for t ∈ R

‖x + y‖ ≤ ‖x‖+ ‖y‖

notation: ‖ · ‖ is general (unspecified) norm; ‖ · ‖symb is particular normnorm ball with center xc and radius r : {x |‖x − xc‖ ≤ r}

norm cone :{(x , t)|‖x‖ ≤ t}Euclidean norm cone is calledsecondorder conenorm balls and cones are convex



Polyhedra

solution set of finitely many linear inequalities and equalities

ax � b ,Cx = d

(A ∈ Rm×n,C ∈ Rp×n ,� is componentwise inequality)

polyhedron is intersection of finite number of halfspaces andhyperplanes



Separating hyperplane theorem

if C and D are disjoint convex sets, then there exists a , 0, bsuch that

aT x ≤ b for x ∈ C, aT x ≥ b for x ∈ D

the hyperplane {x |aTx = b} separates C and Dstrict separation requires additional assumptions (e.g., C is closed,D is a singleton)



Supporting hyperplane theorem

supporting hyperplane to set C at boundary point x0:

{x |aT x = aT x0}

where a , 0 and aT x ≤ aT x0 for all x ∈ C

supporting hyperplane theorem:

if C is convex, then there exists a supporting hyperplane at everyboundary point of C



Definition

f : Rn → R is convex if dom f is a convex set and

f(θx + (1 − θ)y) ≤ θf(x) + (1 − θ)f(y)

for all x , y ∈ dom f , 0 ≤ θ ≤ 1

f is concave if −f is convexf is strictly convex if dom f is convex and

f(θx + (1 − θ)y) < θf(x) + (1 − θ)f(y)for x , y ∈ dom f , x , y , 0 < θ < 1



Examples on R

convex:

affine: ax + b on R, for any a, b ∈ R

exponential: eax , for any a ∈ R

powers: xa on R++, for a ≥ 1 or a ≤ 0

powers of absolute value: |x |p on R, for p ≥ 1

negative entropy: x log x on R++

concave:

affine: ax + b on R, for any a, b ∈ R

powers: xa on R++, for 0 ≤ a ≤ 1

logarithm: log x on R++



First-order condition

f is differentiable if dom f is open and the gradient:

∇f(x) = (∂f(x)∂x1

,∂f(x)∂x2

, · · · , ∂f(x)∂xn

)

exists at each x ∈ dom f

1st-order condition:

differentiable f with convexdomain is convex iff

f(y) ≥ f(x) + ∇f(x)T (y − x) forall x , y ∈ dom f



Second-order conditions

f is twice differentiable if dom f is open and the Hessian∇2f(x) ∈ Sn:

∇2f(x)ij =∂2f(x)∂xi ∂xj

, i, j = 1, . . . , n

exists at each x ∈ dom f

2nd-order condition:for twice differentiable f with convex domain

f is convex if and only if

∇2f(x) � 0 for all x ∈ dom f

if ∇2f(x) ≻ 0 for all x ∈ dom f , then f is strictly convex



Examples

1. quadratic function: f(x) = (1/2)xT Px + qT x + r (with P ∈S)

∇f(x) = Px + q, ∇2f(x) = P

convex if P � 02. least-squares objective: f(x) = ‖Ax − b‖22

∇f(x) = 2AT(Ax − b), ∇2f(x) = 2AT A

convex (for any A)3. quadratic-over-linear : f(x , y) = x2/y

∇2f(x , y) = 2y3

[

y−x

] [

y−x

]T

� 0

convex for y > 0



Optimization problem in standard form

minimize f0(x)subject to fi(x) ≤ 0, i = 1, . . . ,m; hi(x) = 0, i = 1, . . . , p

x ∈ Rn is the optimization variablef0 : Rn → R is the objective or cost functionfi : Rn → R, i = 1, . . . ,m, are the inequality constraintfunctionshi : Rn → R are the equality constraint functions

optimal value:

p∗ = inf {f0(x)|fi(x) ≤ 0, i = 1, . . . ,m, hi(x) = 0, i = 1, . . . , p}p∗ = ∞ if problem is infeasible (no x satisfies the constraints)

p∗ = −∞ if problem is unbounded below



Optimal and locally optimal points

x is feasible if x ∈ dom f0 and it satisfies the constraintsa feasible x is optimal if f0(x) = p∗;Xopt is the set of optimal points

x is locally optimal if there is an R > 0 such that x is optimal for

minimize(overz) f0(z)subject to fi(z) ≤ 0, i = 1, . . . ,m, hi(z) = 0, i = 1, . . . , p

‖z − x‖2 = [(z1 − x1)2 + · · ·+ (zn − xn)

2]1/2 ≤ R

examples (with n = 1,m = p = 0)

f0(x) = 1/x, dom f0 = R++ : p∗ = 0, no optimal point

f0(x) = − log x, dom f0 = R++ : p∗ = −∞f0(x) = x log x, dom f0 = R++ : p∗ = −1/e, x = 1/e, is optimal

f0(x) = x3 − 3x, p∗ = −∞, local optimum at x = 1



Implicit constraints

the standard form optimization problem has an implicit constraint

x ∈ D =⋂m

i=0dom fi ∩⋂p

i=1dom hi

we call D the domain of the problem

the constraints fi(x) ≤ 0, hi(x) = 0 are the explicit constraints

a problem is unconstrained if it has no explicit constraints(m = p = 0)

example

minimize f0(x) = −k∑

i=1log(bi − aT

i x)

is an unconstrained problem with implicit constraints aTi x < bi



Feasibility problem

find xsubject to fi(x) ≤ 0, i = 1, . . . ,m

hi(x) = 0, i = 1, . . . , p

can be considered a special case of the general problem withf0(x) = 0:

minimize 0subject to fi(x) ≤ 0, i = 1, . . . ,m

hi(x) = 0, i = 1, . . . , p

p∗ = 0 if constraints are feasible; any feasible x is optimal

p∗ = ∞ if constraints are infeasible



Convex optimization problem

example

minimize f0(x) = x21 + x2

2subject to f1(x) = x1/(1 + x2

2 ) ≤ 0h1(x) = (x1 + x2)

2 = 0

f0 is convex; feasible set {(x1, x2)|x1 = −x2 ≤ 0} is convex

not a convex problem (according to our definition): f1 is not convex,h1 is not affine

equivalent (but not identical) to the convex problem

minimize x21 + x2

2subject to x1 ≤ 0

x1 + x2 = 0



Local and global optimal

any locally optimal point of a convex problem is (globally) optimal

proof:suppose x is locally optimal and y is optimal with f0(y) < f0(x)x locally optimal means there is an R > 0 such that

z feasible, ‖z − x‖2 ≤ R ⇒ f0(z) ≥ f0(x)

consider z = θy + (1 − θ)x with θ = R/(2‖y − x‖2)

‖y − x‖2 > R, so 0 < θ < 1/2z is a convex combination of two feasible points, hence also feasible

‖z − x‖2 < R when θ is small enough and

f0(z) ≤ θf0(x) + (1 − θ)f0(y) < f0(x)

which contradicts our assumption that x is locally optimal



Optimality criterion for differentiable f0

x is optimal if and only if it is feasible and

∇f0(x)T (y − x) ≥ 0 for all feasible y

if nonzero, ∇f0(x) defines a supporting hyperplane to feasible set Xat x



unconstrained problem : x is optimal if and only if

x ∈ dom f0, ∇f0(x) = 0

equality constrained problem

minimize f0(x) subject to Ax = b

x is optimal if and only if there exists a ν such that

x ∈ dom f0, Ax = b , ∇f0(x) + ATν = 0

minimization over nonnegative orthant

minimize f0(x) subject to x � 0

x is optimal if and only if

x ∈ dom f0, x � 0, { ∇f0(x)i ≥ 0 xi = 0∇f0(x)i = 0 xi > 0



Lagrangian

standard form problem (not necessarily convex)

minimize f0(x)subject to fi(x) ≤ 0, i = 1, . . . ,m

hi(x) = 0, i = 1, . . . , p

variable x ∈ Rn, domain D, optimal value P∗

Lagrangian:L : Rn × Rm × Rp → R, with dom L = D × Rm × Rp ,

L(x , λ, ν) = f0(x) +m∑

i=1λi fi(x) +

p∑

i=1νihi(x)

weighted sum of objective and constraint functions

λi is Lagrange multiplier associated with fi(x) ≤ 0

νi is Lagrange multiplier associated with hi(x) = 0Instructor: MMM�� OOO��ÅÅÅ��äää ÷÷÷ïïïÄÄÄConvex Optimization


Lagrange dual function

Lagrange dual function: g = Rm × Rp → R

g(λ, ν) = infx∈DL(x , λ, ν)

= infx∈D(f0(x) +m∑

i=1λi fi(x) +

p∑

i=1νihi(x))

g is concave, can be −∞ for some λ, ν

lower bound property: if λ � 0, then g(λ, ν) ≤ p∗

Proof

if x̃ is feasible and λ � 0, then

f0(x̃) ≥ L(x̃ , λ, ν) ≥ infx∈DL(x , λ, ν) = g(λ, ν)

minimizing over all feasible x̃ gives p∗ ≥ g(λ, ν)



Primal & Dual problem

Primal problem


hi(x) = 0, i = 1, . . . , p

variable x ∈ Rn, domain D, optimal value P∗

Dual problem

maximize g(λ, ν)subject to λ � 0

g(λ, ν) = infx∈D(f0(x) +m∑

i=1λi fi(x) +

p∑

i=1νihi(x))


Convex Optimization TCP Duality Rethinking Internet Traffic Management SPEF: Op timal TE with OSPF P2P Traffic Optimizationéó¯K�¢~¯K£ã,7ì�m\ó�÷7�Â\Ǒ56�/÷!\ó7IÂ\Ǒ30�/÷.\ó�÷7�I7ó4��§hÖó2��¶\ó�÷7II7ó3��§hÖó1��.T�mzF�^�7óÚhÖóoó�©OǑ120Ú50��.TXÛSSSüüü)))��âU�zFÂ\��ºÂÂÂ\\\��zzz�.maximize z = 56x1 + 30x2;subject to 4x1 + 3x2 ≤ 120,

2x1 + x2 ≤ 50,x1, x2 ≥ 0.

x∗ = (x1, x2)T = (15, 20)T , z∗ = 1440.


Convex Optimization TCP Duality Rethinking Internet Traffic Management SPEF: Op timal TE with OSPF P2P Traffic Optimizationéó¯K�¢~l,��ÆÝ�ÄT¯Keyk��N²Eö§�¥k�17ì�¬£7�Ú7I¤)�¾ü.��|^T7ì�m�7óÚhÖó5�¤�¥�¾ü. �o§�I�ïÄXÛ�7óÚhÖó�óóó��½½½ddd§âUQ�T�mú�k|�ãl �¿O�\ó§q�gC¤G�ó�¤^o��.¤¤¤^̂̂��zzz�.minimize f = 120ω1 + 50ω2;subject to 4ω1 + 2ω2 ≥ 56,

3ω1 + ω2 ≥ 30,ω1, ω2 ≥ 0.

ω∗1 = 2, ω∗2 = 24, f∗ = 1440.



Duality theorem

Weak duality theorem

Let x′ be a feasible solution to the primal problem, and λ′ be afeasible solution to its dual problem, then f(x′) ≥ g(λ′)..

Strong duality theorem (for convex programming)

Assume that X is an open convex set, f0(x) and fi(x)(i = 1, . . . ,m)are convex functions, and hi(x)(i = 1, . . . , p) are linear functions.Moreover, assume that there exists x′ ∈ X suchfi(x′) < 0, (i = 1, . . . ,m) and hi(x′) = 0, (i = 1, . . . , p), then

i) The optimal value of the primal problem is equal to that of thedual problem.

ii) Let x∗ be a solution of the primal problem and λ∗ be a solutionof the dual problem, then it holds that λ∗i fi(x∗) = 0, (i = 1, . . . ,m).



Karush-Kuhn-Tucker (KKT) conditions

The following four conditions are called KKT conditions(for a problem with differentiable fi , hi)1. primal constraints: fi(x) ≤ 0, i = 1, . . . ,m, hi(x) = 0, i = 1, . . . , p2. dual constraints: λ � 03. complementary slackness: λi fi(x) = 0, i = 1, . . . ,m4. gradient of Lagrangian with respect to x vanishes:

∇f0(x) +m∑

i=1λi∇fi(x) +

p∑

i=1νi∇hi(x) = 0

if strong duality holds and x , λ, ν are optimal, then they must satisfythe KKT conditions



Slater’s condition

Convex Optimization Problem


hi(x) = 0, i = 1, . . . , p

variable x ∈ Rn, domain D.

We say that the problem satisfies Slater’s condition if it is strictlyfeasible, that is

∃x0 ∈ D : fi(x0) < 0, i = 1, . . . ,m, hi(x0) = 0, i = 1, . . . , p.

Slater’s condition (or Slater condition) is a sufficient condition forstrong duality to hold for a convex optimization problem.



KKT conditions for convex problem

if x̃ , λ̃, ν̃ satisfy KKT for a convex problem, then they are optimal:

from complementary slackness: f0(x̃) = L(x̃ , λ̃, ν̃)

from 4th condition (and convexity): g(λ̃, ν̃) = L(x̃ , λ̃, ν̃)hence, f0(x̃) = g(λ̃, ν̃)

If Slater’s condition is satisfied:x is optimal if and only if there exist λ, ν that satisfy KKT conditions

recall that Slater implies strong duality, and dual optimum isattained

generalizes optimality condition ∇f0(x) = 0 for unconstrainedproblem


Convex Optimization TCP Duality Rethinking Internet Traffic Management SPEF: Op timal TE with OSPF P2P Traffic Optimization�{�^�ê��`z�{��eü{Úî{�ÝFÝ{¨v¼ê{:v¼ê{S:v¼ê{�f{Instructor: MMM�� OOO��ÅÅÅ��äää ÷÷÷ïïïÄÄÄConvex Optimization

Convex Optimization TCP Duality Rethinking Internet Traffic Management SPEF: Op timal TE with OSPF P2P Traffic Optimization�^�ê��`z�{��eü{minimize f(x)subject to x ∈ En

f(x)äk��ëY �ê,�|¢��µd(k ) = −∇f(x(k ))Úî{Ä�g�:^��g¼ê�Cq8I¼êf(x),,�°(/�Ñù��g¼ê�4�:.


Convex Optimization TCP Duality Rethinking Internet Traffic Management SPEF: Op timal TE with OSPF P2P Traffic Optimization¨v¼ê{:v¼ê{: Ú\v�p(x) =

m∑

i=1ϕ[gi(x)] +

l∑

j=1ψ[hj(x)]

where ϕ[gi(x)] = [max{0,−gi(x)}]α ψ[hj(x)] = |hj(x)|βS:v¼ê{: æN¼êG(x , r) = f(x) + rB(x)

where : B(x) =m∑

i=1

1gi(x)

B(x) = −m∑

i=1lngi(x)


Convex Optimization TCP Duality Rethinking Internet Traffic Management SPEF: Optimal TE wit h OSPF P2P Traffic Optimization

Outline


2 TCP Duality






TCP & AQM

Duality→ equilibrium

Source rates xi(t) are primal variables

Congestion measures pl(t) are dual variables

Congestion control is optimization process



Congestion control

Interaction of source rates xs(t) and congestion measures pl(t)Duality theory

They are primal and dual variables

Flow control is optimization process

Example congestion measure

Loss (Reno)

Queueing delay (Vegas)

Queue length (RED)

Price (REM)



Model

Sources s

L(s) - links used by source s

Us(xs) - utility if source rate = xs

Network

Links l of capacities cl



Primal problem

maximizexs≥0∑

sUs(xs)

subject to x l ≤ cl , ∀l ∈ L

Assumptions: Strictly concave increasing Us

Unique optimal rates xs exist

Direct solution impractical



Duality Approach

Primal

maximizexs≥0∑

sUs(xs)


Dual

minimizep≥0 D(p) = (maximizexs≥0∑

sUs(xs) +

∑

lpl(cl − x l))

Primal-dual algorithm:

x(t + 1) = F(p(t), x(t))

p(t + 1) = G(p(t), x(t))



Duality Model of TCP

Source algorithm iterates on rates

Link algorithm iterates on prices

With different utility functions


x(t + 1) = F(p(t), x(t)) ⇐ Reno,Vegasp(t + 1) = G(p(t), x(t)) ⇐ DropTail,RED,REM



Summary

Flow control problem

maximizexs≥0∑

sUs(xs)



x(t + 1) = F(p(t), x(t))p(t + 1) = G(p(t), x(t))

Major TCP schemes

Maximize aggregate source utility

With different utility functions



Summary

What are the (F ,G,U)?Derivation

Derive (F ,G) from protocol description

Fix point (x, p) = (F ,G) gives equilibrium

Derive U: regard fixed point as Kuhn-Tucker condition



Active queue management

Idea: provide congestion information by probabilistically markingpacketsIssues

How to measure congestion (pandG)?

How to embed congestion measure?

How to feed back congestion info?

x(t + 1) = F(p(t), x(t)) ⇐ Reno,Vegasp(t + 1) = G(p(t), x(t)) ⇐ DropTail,RED,REM



RED (Floyd & Jacobson 1993)

Congestion measure: average queue length

bl(t + 1) = [bl(t) + y l(t) − cl ]+

rl(t + 1) = (l − a)rl(t) + a ∗ bl(t)

Embedding: p-linear probability function

Feedback: dropping or ECN markingInstructor: MMM�� OOO��ÅÅÅ��äää ÷÷÷ïïïÄÄÄConvex Optimization


REM (Athuraliya & Low 2000)

Congestion measure: price

rl(t + 1) = [rl(t) + γ(αlbl(t) + y l(t) − cl)]+

Embedding: exponential probability function

Feedback: dropping or ECN markingInstructor: MMM�� OOO��ÅÅÅ��äää ÷÷÷ïïïÄÄÄConvex Optimization


Key features

Clear buffer and match rate

rl(t + 1) = [rl(t)+ γ(αlbl(t)+ y l(t) − cl)]+

Clearbuffer matchrate

Sum prices

pl(t) = 1 − φ−rl(t)



TCP and AQM



Reno:F

for every ack (ca){ w+ = 1

w }

for every loss{ w := w

2 }

∆ws(t) =xs(t)(1−q(t))

ws− xs(t)q(t) ∗ 1

2 ∗4ws

3

xs(t) = ws(t)/Ds ,Ds is the equilibrium round trip time

Fs(q(t), x(t)) = xs(t) +1−q(t)

D2s− 2x2

s (t)3 q(t)



Reno: Utility Function

Fs(q(t), x(t)) = xs(t) +1−q(t)

D2s− 2x2

s (t)3 q(t)

xs = Fs(q, x)

⇒ 1−q(t)D2

s=

2x2s

3 q

⇒ 33+2x2

s D2s= q ⇒ Ureno

s (xs) =√

3/2Ds

tan−1(√

23xsDs)


Convex Optimization TCP Duality Rethinking Internet Traffic Management SPEF: Optimal TE with OSPF P2P Traffic Optimization

Outline


2 TCP Duality






Traffic Management Today



Shortcomings of today.s traffic management

Congestion control assumes routing is fixed, trafficengineering assumes traffic is inelastic

Link weight tuning problem is NP-hard

Link weights are tuned at the timescale of hours, slower thantraffic shifts

What if we redesign traffic management from scratch usingoptimization tools?



Congestion Control Implicitly Maximizes AggregateUser Utility



Traffic Engineering Explicitly Minimizes NetworkCongestion



A Balanced Objective



Model of He et al and TRUMP Algorithm

maximize∑

s Us(xs) − w∑

l f(zl/cl)subject to x = Hy, z = Ay

y ≥ 0, z ≤ c,

f is a convex, non-decreasing,and twice-differentiablefunction , e.g., ezl/cl .


Convex Optimization TCP Duality Rethinking Internet Traffi c Management SPEF: Optimal TE with OSPF P2P Traffic Optimization

Outline


2 TCP Duality






Motivation

Traffic Engineering (TE) is important for ISPs

OSPF is a commonly used intra-domain routing protocol

The quality of OSPF-based traffic engineering dependslargely on the choice of link weights

Optimizing the link weights for OSPF to the offered traffic is anknown NP-hard problem

Some related issues of multi-path protocol are addressed in ourprevious work LBMP

Introduce a novel logarithm barrier-based approach to makesoptimal solution achievable

Demonstrate a distributed implementation and design apractical Logarithm-Barrier-based Multi-path Protocol (LBMP)



Challenges

Can we guarantee the universal existence of optimal link weights?

Wang et al. (INFOCOM’01) proved that any arbitrary set ofroutes can be converted to shortest paths with respect tosome set of positive link weightsWe prefer to ensure the universal existence of optimal linkweights which are explicitly determined by the objectivefunction

Difficulties in OSPF protocol to realize/optimal routing0It uses shortest path routing with destination based forwardingThe forwarding mechanism equally splits the correspondingtraffic across the multiple equal cost paths or next hops for agiven destination routing prefix.

Open problem: can a link-state protocol with hop-by-hopforwarding achieve optimal TE?



Related Work

Traffic Engineering

Fortz et al. showed that optimizing the link weights for OSPF withevenly split over ECMP to the offered traffic is an NP-hard problem

Xu et al. (INFOCOM’08) proposed PEFT, a link-state routingprotocol splitting traffic over multiple paths with an exponentialpenalty on longer paths. Limitations:- All available paths rather than the shortest paths are involved- No illustration on how to find the candidate paths for traffic splitting

Rate Control and Congestion avoidance

Kelly et al. considered fairness and stability from theperspective of economic and engineering

maximize∑

s Us(xs)subject to Ax ≤ c

x ≥ 0Us(xs) =

{

ps log(xs), α = 1ps(1 − α)−1x1−α

s , otherwise.



Main Contributions

Ensuring the existence of optimal link weights, which can beexplicitly formulated using the optimal distribution of traffic andobjective function

Developing a new link-state routing protocol, SPEF, andtheoretically proving that it can achieve the optimal TE forintra-domain IP networks

Illustrating the effectiveness of SPEF in terms of link utilizationand network traffic distribution via simulations



Network Model

Directed network G = (N ,E) with vertex set N , edge set E,the capacity for link (i, j) ∈ E is cij .Source-destination pairs set R = {(s1, t1), · · · , (sR , tR)}, thedemand for (sr , tr) is dr .Destination node set with D = {t ∈ N : ∃ r ∈ R s.t. tr = t}.The flow of commodity t along edge (i, j) is f t

ij .Two kinds of constraints:Capacity constraints:

fij =∑

t∈Df tij ≤ cij ,∀(i, j) ∈ E

Flow conservation constraints:∑

i:(s,i)∈Ef tsi −

∑

j:(j,s)∈Ef tjs = dt

s , ∀t ∈ D, s ∈ N



Universal Existence of Optimal Link Weights

TE(V ,G, c,D)

maximizeft≥0∑

(i,j)∈E Vij(sij)

subject to c −∑t∈D ft = s ≥ 0Bf t = dt , ∀t ∈ D,

Let (s, ft , t ∈ D) be a solution and w = (wij : (i, j) ∈ E) be thecorresponding Lagrangian multiplier vector.

Result 1 We have that ft determines the shortest path for eachsource-destination pair (s, t) under the link weight vector w, whichis determined explicitly by the utility function Vij and the residualcapacity sij as wij = V ′ij(sij) if link (i, j) ∈ E is no saturated, i.e.sij > 0.



Properties of Optimal Link Weights

Linkij(Vij ;wij):maximize Vij(sij) − wijsij

subject to sij ≥ 0.

Network(G, c,D;w)

maximize∑

(i,j)∈E wijsij

subject to c −∑

t∈D ft = s ≥ 0

Bf t = dt , ∀t ∈ Dft ≥ 0.

minimize∑

(i,j)∈E wij∑

t∈D f tij

subject to∑

t∈D f tij ≤ cij ,∀(i, j) ∈ E

Bf t = dt , ∀t ∈ Dft ≥ 0.

Result 2 There exists a weight vector w = (wij , (i, j) ∈ E) such thatthe vector s = (sij , (i, j) ∈ E), formed from the unique solution sij toLinkij(Vij ;wij), solves Network(G, c,D;w). The vector s also solvesTE(V ,G, c,D).



(q, β) Utility Function

Consider the objective function

Vij(sij) =

qij log (sij), if β = 1qij(1 − β)−1cβ−1

ij s1−βij , if β , 1.

Example 1 For β = 2, let qij = cij .

Vij(sij) = −1 − fij/(cij − fij), wij = cij/(cij − fij)2.

Example 2 For β = 1, let qij = 1.

Vij(sij) = log (sij), wij = 1/(cij − fij).

Example 3 For β = 0, let dij be the processing and propagation delay onlink (i, j).

Vij(sij) = dijcij − dij fij , wij = dij .

Remark : wij = dij for unsaturated link (i, j) and wij ≥ dij for saturated link(i, j). If dij = 1, we have the minimum hop routing.



SPEF: Toward the Optimal Traffic Engineering with OSPF

In SPEF (Shortest paths Penalizing ExponentialFlow-splitting), we only need one more weight for each link .

The packet forwarding scheme is the same as that in OSPF:hop-by-hop along the shortest paths constructed based ondestination according to the first link weights.

When there are multiple equal cost shortest paths for someOD pairs in view of the first link weights, the flow split ratioover the multiple shortest paths can be independentlycomputed by the routers from the second link weights.



Shortest-Path-Based NEM

We can determine the set of shortest paths ON = {ONt : t ∈ D}based on the first link weights, where ONt is the shortest path setfor any node s ∈ N to destination t ∈ D. Specifically, SPr denotesthe shortest path set for (sr , tr). Let SP = {SPr : r ∈ R}.We use NEM (Network Entropy Maximization) to deal with thescenario of multiple equal cost paths.NEM(SP, f∗,D):

maximize −∑

r∈R dr∑nr

k=1 prk log pr

ksubject to

∑

r∈R∑

k :(i,j)∈SPrk

drprk ≤ f∗ij ,∀(i, j) ∈ J

∑nrk=1 pr

k = 1, ∀r ∈ R,

where SPrk denotes the k -th shortest path from sr to tr and pr

k isthe traffic split ratio for path SPr

k .



Forwarding Table for SPEF Routing

Table 2 Forwarding table for SPEF routing.

Lengths of multiple equal cost shortest paths through

Next hop link (s, next hop) to t in view of the second link weights

v1 (v(s,t)11 , · · · , v(s,t)

1n1)

......

vms (v(s,t)ms1 , · · · , v

(s,t)msnms

)

The traffic to destination t can be split according to the followingformula

Γt(s, vk ) =

∑nkj=1 e−v(s,t)

kj

∑msi=1

∑nij=1 e−v(s,t)

ij

, k = 1, · · · ,ms. (5)



An Example

96

10 123

1 2

78

1

2 3

4

5 6

7

5

11

13

4There are 4 source-destination pairs and each needs a bandwidthof 4 units. Each link has a capacity of 5 units.



An Example (Continues)

1 2 3 4 5 6 7 8 9 10 11 12 130

0.5

1

1.5

2

2.5

3

Links

The

Firs

t Link

Weig

hts

SPEF0

SPEF1

SPEF5

1 2 3 4 5 6 7 8 9 10 11 12 130

0.5

1

1.5

2

2.5

Links

The

Seco

nd L

ink W

eight

s

SPEF0

SPEF1

SPEF5

1 2 3 4 5 6 7 8 9 10 11 12 130

0.5

1

1.5

2

Links

Link U

tiliza

tions

OSPFSPEF

0

SPEF1

SPEF5



Outline


2 TCP Duality






P2P6þ`z�.`zg´ÏLÿþ&EÚÝ�.��P2P6þÝÏLP2P6þÝ�)ó´þP2P6þ©ÛP2P`zEâÜÝ�Yéó´P2P6þ�KǑÏL�`zï�©Û�)�`�ÜÝ�YInstructor: MMM�� OOO��ÅÅÅ��äää ÷÷÷ïïïÄÄÄConvex Optimization


P2P6þ`zÏLP2P6þÝ��ó´þ�P2P6þÏLP2P6þÝÚ´d&E§�±��äó´þ�P2P6þò�ä�ó´8Ü½ÂǑJ§Kà�à�´dr �±½ÂǑJ��f8§ǑÒ´�|ó´�8Ü½Â0-1ÝA : �ó´jáu´di�,Aij = 1;ÄKAij = 0�^ó´þ�6þÒ´:L = Ay



P2P`zEâéP2P6þÝ�KǑP2P6þ�/z

uij = f(dij),

{

f(dij) ≥ 1, dij ≤ Sf(dij) < 1, dij > S

P2P6þ��üÑuij =

(1 − λij)uij , i , juij +

∑

i,jλuij , i = j , Pj ⊆ CacheSet

uij , Pj & CacheSet

P2P6þ½�Instructor: MMM�� OOO��ÅÅÅ��äää ÷÷÷ïïïÄÄÄConvex Optimization


The basic modelüó´Â�ï�KǑÏ�-`z~��6þ;ó´�§Ý;ó´|^Çó´Â�¼ê

Bi =∫ νi

0ψi(ηi)dν =

∫ νi

0ψi(

ui−νCi

)dν�äÂ�ï��ä�ó´Â�\�Bt =

m∑

i=1Bi =

m∑

i=1

∫ νi

0ψi(

ui−νCi

)dν



P2P6þ`z�`zï�maximize B(xi)subject to

∑

xi∈Xi

ci ≤ c�þXi(< x1, x2, ..., xn >)L«P2P`zEâ��ÜÝ�YciL«ÜÝ�YXi�ÜÝm�§ cK´��m�þ�B(Xi)L«3ÜÝ�YXie�äÜÝoÂ�3ÜÝm��åe§�)�äÜÝoÂ��ÜÝ�Y.



P2P6þ`zP2P6þ��-yk��ó�Ì�8¥3üó´��{�O-"yéu��ÜÝ�©Û�Û��ÜÝ�Y-��KǑ�ó´U§�JØU{üU\-ÀJ�Pl��ó´ÜÝ¿Ø´�`üÑ


Convex Optimization TCP Duality Rethinking Internet Traffi c Management SPEF: Optimal TE with OSPF P2P Traffic Optimizationõó´��ÜÝ��`z¯K`z�.maximize Btotal =

m∑

i=1xiBi(X ∗i )

subject tom∑

i=1xici ≤ c

xi = 0or1õó´��ÜÝ�E,Ý-�5�Ǒ0/1��¯K-õ�ª�mØ�)õó´��ÜÝ�{-©|½.�{£�`�{¤-éuª�{



P2P6þ`zµd'�n��{��J-{ü�À��Pló´��{5U��-éuª�{�Cu�`�{5Uéuª�{�J��O�m��



P2P6þ`zµd�Pl�20^ó´��Uõ�¹ÜÝ�.Ú�{�±k��Uõó´�Pl



Future Research Directions

Nonconvexity

- dealing with nonconvex optimization formulations

Research Issues Involving Time

- dealing with formulations of real-time applications

Quantifying Network X-ities

- e.g., scalability, availability, diagnosability, manageability, etc.



Nonconvexity

Four different forms of nonconvex optimization formulations

Nonconcave utilitye.g., the sigmoidal utility that are more realistic models inapplications

Nonconvex constraint sete.g., lower bounds on SIR as a function of transmit powervector

Integer constrainte.g., formulations in single-path routing protocols

Convex constraints growing exponentially with the number ofvariablese.g., schedulability constraints in multi-hop interferencemodels



Three approaches to deal with nonconvexity

Go around nonconvexity (Left figure)-Change variables to turn the seemingly nonconvex probleminto a convex one, e.g., geometric programming

Go through nonconvexity (Middle figure)-Use successive convex relaxations, utilize special structures,or leverage smarter branch and bound methods

Go above nonconvexity (Right figure)-Design for optimizability, changing assumptions may result ina different, much easier-to-solve formulation



Geometric Programming

Original Form

minimize f0(x)subject to fi(x) ≤ 1, i = 1, ...,m

hi(x) = 1, i = 1, ..., p(6)

where fi() are posynomials and hi() are monomials.f(x) = cxa1

1 xa22 · · · x

ann , c > 0 and ai ∈ R

Define: yi = log(xi), then f(x) = eaT y+b , where b = log(c)

Convex Form

minimize f0(ey)

subject to fi(ey) ≤ 1, i = 1, ...,mhi(ey) = 1, i = 1, ..., p

(7)



Research Issues Involving Time

Utility functions-For real-time applications, utility should be a function of rateallocation through the transients instead of equilibrium rates.-How to formulate and maximize such functions?

Variants in time scales-Time scales differ by several orders-of-magnitude acrosslayers. e.g., App., Trans. and Phys. are determined by userbehaviors, RTT and physics of the transmission medium.-How to bound them tightly?

From theoretical to practical-Theoretically, iterative algorithms allow variables drop belowa threshold during the transient, such as TCP window size-Practically, under threshold may result in disconnection.



Quantifying Network X-ities

Network X-ities: robustness metrics-Performance Metrics: throughput, latency, and distortion.-Robustness Metrics: evolvability, scalability, availability,diagnosability, and manageability.Existing techniques for ”design by decomposition”-Enhance scalability and evolvability.-Present risks to manageability such as diagnosability andoptimizability.long-term goal of Optimization Decomposition-Move away from the restriction of one decomposition fits all,away from the focus on deterministic fluid models andasymptotic convergence, and even away from the emphasison optimality-Instead, towards optimizability.



References 1

S. Boyd, L. Vandenberghe. Convex Optimization, CambridgeUniversity Press: Cambridge,2004.

S. H. Low. A Duality Model of TCP and Queue ManagementAlgorithms S. H. Low, ”A Duality Model of TCP and QueueManagement Algorithms,” IEEE/ACM Trans. Netw. vol. 11, pp.525õ536, Aug. 2003.

J. He, M. Suchara, M. Bresler, J. Rexford, and M. Chiang. Frommultiple decompositions to TRUMP: traffic management usingmultipath protocol. Summitted to IEEE/ACM Trans. Networking,March 2008.�²�,Çï²,M�. Peer-to-Peer6þ��ÜÝï�"�u�ÆÆ�£g,�Æ�¤, 2009 1Ï.



References 2

S. Boyd, S. J. Kim, L. Vandenberghe, and A. Hassibi. A tutorial ongeometric programming. Optimization and Engineering, vol. 8, no.1, pp. 67-127, 2007

K. Xu, H. Liu, J. Liu and M. Shen. One More Weight is Enough:Toward the Optimal Traffic Engineering with OSPF. In Proc. of IEEEICDCS, 2011



Thanks for Your Attentions


Documents

Convex Optimization - THUxukeGroupnonlinear convex optimization (Nesterov&Nemirovski 1994) applications before 1990: mostly in operations research; few in engineering since 1990: many