CS计算机代考程序代写 algorithm Week 12 Network Optimization

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