Week 12 Network Optimization
Advanced Network Technologies
Network Optimization
School of Computer Science
Dr. Wei Bao| Lecturer
Network Optimization
› You can skip this class if you think it is too difficult.
› Will not appear in exams
This class is not mandatory
Outline of today
› Problem Formulation
› Convex Sets and Convex Functions
› Convex Optimization and Lagrange Duality
› Optimization-based Congestion Control
Motivation: Problem Formulation
› Consider a network that consists of a set L = {1, . . ., L} of unidirectional
links of capacity cl, for each l ∈ L.
› The network is shared by a set S = {1, . . . , S} of flows.
› The path L(s) ⊆ L is a set of links that flow s uses along its routing path.
› We also define S(l) as the set of flows that use link l.
› Note that link l ∈ L(s) if and only if source s ∈ S(l).
Motivation: Problem Formulation
1
2
3
4
c2 c3
c4
c1
1
2
3
Link: {1,2,3,4}
Capacity: c1 c2 c3 c4
Flow: {1,2,3}
L(1)={1,2}
L(2)={2,4}
L(3)={1,3}
S(1)={1,3}
S(2)={1,2}
S(3)={3}
S(4)={2}
Motivation: Problem Formulation
› xs : Flow rate of s, ms ≤ xs ≤ Ms.
› Link constraint:
› The sum rate of flows at one link is limited by link capacity
Motivation: Problem Formulation
1
2
3
4
c2 c3
c4
c1
1
2
3
x1 + x3 ≤ c1
Flow’s utility
› Flow s attains a utility Us (xs), ms ≤ xs ≤ Ms.
› What does it mean?
– Us (xs) happiness of flow s if it’s rate is xs
xs
Us (xs)
Linear
xs
Us (xs)
Convex
xs
Us (xs)
Concave
Realistic:
The law of diminishing marginal utility
Optimization Problem
› Optimization problem
Decision variables
Objective function
Constraints
Optimization Problem
› Q1: How can we solve the problem?
› Q2: How can we transfer the solution into practical implementation?
The watershed between tractable and intractable
problems is not linearity, but convexity.
Convex Set and Convex Function
Convex Set
Line through points x1 and x2
Line segment between x1 and x2
Convex Set
Convex Function
dom f Domain of function f
The set of input of the function of f
f is a convex function
1. dom f is a convex set and
2. For all x, y in dom f , 0≤ θ ≤1
Convex Function
f is concave if −f is convex
Convex/Concave function examples
First-order condition
Second-order condition
Hessian matrix
Second-order condition
H is positive semidefinite
zTHz is non-negative for any vector z
f(x), x is a single-dimension variable
f’’(x) is non-negative
Convex Optimization and Lagrange Duality
Standard Convex Optimization Problem
Objective function
Inequality constraints
Equality constraints
Local and Global Optimal
Local minimum and global minimum
Local minimum
Any locally optimal point of a convex problem is (globally) optimal!
Lagrangian
Lagrange Dual Function
Lagrange Dual Problem
Duality Gap
› Optimal f of primary problem: p*
› Optimal g of dual problem: d*
Duality Gap
Karush–Kuhn–Tucker (KKT) condition
If strong duality holds and x, λ, v are optimal, then they must satisfy the KKT
conditions.
Gradient Method
Unconstraint Problem
General Guidelines
How to choose direction?
?
Contour Lines
How to choose step size?
?
How to choose step size?
Gradient Descent Method
Gradient Descent Method
Constraint Problem
Constraint Problem
Constraint Problem
Optimization-based Congestion Control
Problem Formulation
› Consider a network that consists of a set L = {1, . . ., L} of unidirectional
links of capacity cl, for each l ∈ L.
› The network is shared by a set S = {1, . . . , S} of flows.
› The path L(s) ⊆ L is a set of links that source s uses along its routing path.
› We also define S(l) as the set of flows that use link l.
› Note that link l ∈ L(s) if and only if source s ∈ S(l).
Problem Formulation
› xs : Flow rate of s, ms ≤ xs ≤ Ms.
› Link constraint:
› The sum rate of flows at one link is limited by link capacity
Optimization Problem
› Optimization problem
Decision variables
Objective function
Constraints
Us() is a concave increasing function, why?
Problem Solution via Lagrangian
Inner sum: every flow passing the link
Outer sum: every link
Inner sum: every link passed by the flow
Outer sum: every flow
Lagrange multiplier
Dual Problem
Dual Problem
It is separable in xs! Bs(ps)
ps
Dual Problem
Given xs
Dual Problem Solution
– Given p=(p1, p2…), each flow xsmaximizes
Dual Problem Solution
› Then
Dual Problem Solution
› Then, our aim is to
› This is done by gradient (projection) method
where
Dual Problem Solution
Gradient (projection) method
i.e.,
Step size
Summary
In order to
In order to
Summary
Flow 1
Flow 2
Flow S
…
p1
p2
pS
…
x1
x2
xS
…
Network
Link 1
Link 2
Link L
…
The sum rate
at one link is
equal to the
sum rate of
flows using
that link
x1
x2
xL
Network
p1
p2
pL
… …
The sum
cost of at
one flow is
equal to
the sum of
costs on
the links
used by
that flow
Dual Problem Solution
› This is a distributed algorithm
– Each source can perform calculation and determine its sending rate based on local
information.
– Each link can also update the price based on local information.
Real-world Interpretation
› Real-world interpretation
– xs: Data rate of TCP flow s, this can be adjusted by changing the congestion window
– cwnd/RTT
– xl: Sum data rate at link l
– pl: Link “cost” at l, e.g., queueing delay in the buffer.
– ps: Sum link costs of flow s.
Link capacity
Outgoing data volume
Incoming data volumeData amount in the queue
In one unit time
Real-world Interpretation
Queueing delay
pl: Queueing delay at l.
ps: Queueing delay of flow s.
RTT=Queueing delay + MinRTT
Send a very small packet to get MinRTT,
Use CurrentRTT and MinRTT to know the Queueing delay
Network-assisted congestion control is not required. Measure RTT is enough!
TCP Vegas
Flow 1
Flow 2
Flow S
…
Measure the queueing delays via SampleRTT
… …
Network
Link 1
Link 2
Link L
…
Network
Measure the queueing delays via SampleRTT
Measure the queueing delays via SampleRTT
Adjust cwnd
Adjust cwnd
Adjust cwnd