Transcript slides

Mathematical models
of the Internet
Frank Kelly
www.statslab.cam.ac.uk/~frank
Hood Fellowship Public Lecture
University of Auckland
3 April 2012
Source: CAIDA,
Young Hyun
Source: CAIDA Young Hyun,
Bradley Huffaker
(displayed at MOMA)
Functional view
Applications
TCP/IP
Physical
technology
Outline
• End-to-end congestion control
– square-root formula
• Utilities and fairness
– optimization formulation
• Multipath routing
– reliability, robustness
End-to-end congestion control
senders
receivers
Senders learn (through feedback from receivers)
of congestion at queue, and slow down or speed
up accordingly. With current TCP, throughput of
a flow is proportional to
1 /(T p )
T = round-trip time, p = packet drop probability.
(Jacobson 1988, Mathis, Semke, Mahdavi, Ott 1997, Padhye,
Firoiu, Towsley, Kurose 1998, Floyd and Fall 1999)
Feedback mechanism
• Now: dropped packets (acknowledgements
carry information from receivers to senders)
• Standards track: Explicit Congestion
Notification (Ramakrishnan, Floyd and
Black RFC3168) - routers mark packets at
queues as overload approached
Control of elastic network flows
• How should available
resources be shared
between competing
streams of elastic
traffic?
• Conceptual problem:
fairness
• Pragmatic problem:
stability of rate control
algorithm
flow
resource
user
Elastic flows
utility,
U(x)
utility,
U(x)
rate, x
elastic traffic prefers to share
(Shenker)
rate, x
inelastic traffic prefers to randomize
Network structure (J, R, A)
J
R
A jr  1
A jr  0
-
set of resources
set of routes
if resource j is on route r
otherwise
route
resource
Notation
J
R
jr
xr
U r (xr )
Cj
Ax  C

- set of resources
- set of users, or routes
- resource j is on route r
- flow rate on route r
- utility to user r
- capacity of resource j
- capacity constraints
The system problem
SYSTEM(U,A,C):
Maxim ize U r ( xr )
rR
subject to
Ax  C
over
x0
Maximize aggregate utility,
subject to capacity constraints
The user problem
USERr(Ur;r):
 wr 
Maxim izeU r    wr
 r 
over
wr  0
User r chooses
an amount to pay per unit time, wr ,
and receives in return a flow xr =wr /r
The network problem
NETWORK(A,C;w):
Maxim ize  wr log xr
rR
subject to
Ax  C
over
x0
As if the network maximizes a
logarithmic utility function, but
with constants {wr} chosen by the users
Problem decomposition
Theorem: the system problem
may be solved
by solving simultaneously
the network problem and
the user problems
Max-min fairness
Rates {xr} are max-min fair if they
are feasible:
x  0,
Ax  C
and if, for any other feasible rates {yr},
 r : yr  xr   s : ys  xs  xr
Proportional fairness
Rates {xr} are proportionally fair if
they are feasible:
x  0, Ax  C
and if, for any other feasible rates {yr}, the
aggregate of proportional changes is negative:


rR
yr  x r
xr
 0
Weighted proportional fairness
A feasible set of rates {xr} are such that
are weighted proportionally fair
if, for any other feasible rates {yr},
yr  x r
wr

x
rR
r

 0
Fairness and the network problem
Theorem: a set of rates {xr}
solves the network problem,
NETWORK(A,C;w),
if and only if the rates are
weighted proportionally fair
Bargaining problem (Nash, 1950)
Solution to NETWORK(A,C;w) with
w = 1 is unique point satisfying
• Pareto efficiency
• Symmetry
• Independence of Irrelevant Alternatives
(General w corresponds to a model
with unequal bargaining power)
Market clearing equilibrium
(Gale, 1960)
Find prices p and an allocation x such
that
p  0,
Ax  C
p (C  Ax)  0
T
wr  xr  p j , r  R
(feasibility)
(complementary
slackness)
(endowments spent)
jr
Solution solves NETWORK(A,C;w)
Fairness criteria
We’ve seen three fairness criteria:
• proportional fairness
• max-min fairness
• TCP-fairness (as described by the
square-root formula)
Can we unify these fairness criteria
within a single framework?
Optimization formulation
Suppose the allocation x is chosen to
1
maximize
xr
r wr 1  
subject to
A
jr
xr  C j
jJ
r
xr  0 r  R
(weighted  -fair allocations, Mo and Walrand 2000)
Solution
1/


 wr 
xr  

  pj 
 jr

pj
rR
- shadow price for the resource j
capacity constraint
Observe alignment with square-root formula when
  2,
wr  1 / Tr ,
2
pr   p j
jr
Examples of  -fair allocations
1
maximize
subject to
xr
r wr 1  
A
jr
1/
xr  C j


 wr 
xr  

  pj 
 jr

jJ
r
xr  0 r  R
 0
 1
(w  1 )
(w  1 )
 2
 
( wr  1 / Tr )
2
(w  1 )
-
maximum flow
proportionally fair
TCP fair
max-min fair
rR
nr  1, wr  1 r  R,
Example
Cj 1 j  J
1/2
1/2
max-min fairness:
 
1/2
2/3
proportional fairness:
 1
2/3
1/3
1
maximum flow:
 0
0
1
Rate control algorithms
• Can rate control algorithms be
interpreted within the optimization
framework?
• Several types of algorithm possible,
based on
– congestion indication using linear increase
and multiplicative decrease rules
– explicit rates inversely proportional to
network shadow prices
Notation
J
- set of resources
R
jr
wr
x r (t)
- set of routes
- resource j is on route r
- weight of route r
- flow rate on route r at time t
- shadow price, or rate of congestion
indication, at resource j at time t
j (t)
A primal algorithm
d
xr (t )   r wr  xr (t )  j (t ) 
dt
jr
 j (t )  p j   xs (t ) 
s: js
xr(t) - rate changes by linear increase,
multiplicative decrease
pj(.) - proportion of packets marked a
function of flow through resource
Global stability
Theorem: the above dynamical system
has a stable point to which all
trajectories converge. The stable point
is proportionally fair with respect to
the weights {wr}, and solves the
network problem, when
p j ( x)  0
x  Cj

x  Cj
TCP
• We’ve seen that TCP’s square root
formula is interpretable in terms of
an optimization problem
• Next we show that its dynamic
behaviour is interpretable as a
form of primal algorithm
TCP (Jacobson’s congestion
avoidance algorithm)
Source maintains a window of sent, but not yet
acknowledged, packets - size cwnd
cwnd  xT
• cwnd incremented by 1/cwnd on positive ack
• cwnd decremented by cwnd/2 on congestion
• change in rate x per unit time is about
cwnd 
 1
(1  p ) 
p /T

2
1 p x p
2
 cwnd

 2 
T / cwnd
T
2
Differential equations for TCP
d
1  r (t ) xr (t ) r (t )
xr ( t ) 

2
dt
2
Tr
2
r (t )  1   1   j (t ) 
jr


 j (t )  p j   xs (t ) 
 s: js

Equilibrium point
1
xr 
Tr
 1  r
 2
 r
1/ 2



rR
• check: the equilibrium of the
dynamical system recovers the inverse
square root formula for TCP
• note again the round-trip time bias
Consequences of RTT bias
Question: where to place cache?
user
cache?
short congested links, T
long uncongested link, T’
cache?
1 
1
2T 2 p
1
2 
T  T ' p
If T '  2 2 1T then short RTT preferred
under TCP, even though twice the resource usage
Multipath routing
Suppose a source-destination pair has access to
several routes across the network:
source
route
resource
- set of source-destination pairs
r s - route r serves s-d pair s
S
destination
Combined multipath routing and congestion control: a robust
Internet architecture. Key, Massoulié & Towsley 2005
Routing and optimization formulation
Suppose x  x(n)
is chosen to
 n log(x )
maximize
s
s
s
H
subject to
xs
sS
nr y r  C j
jJ
sr
yr 
r
A
jr
r
yr  0 r  R
( H is an incidence matrix, showing which
routes serve a source-destination pair )
Example of multipath routing
n3
n2
C3
C1
n1
C2
Routes, as well as flow rates,
are chosen to optimize
 ns log(xs ) over source-destination pairs s
s
C3
C3  C1,C2
First cut constraint
n3
n2
C3
C1
n1
C2
C3
n1 x1  n2 x2  C1  C2
Cut defines a single pooled resource
Second cut constraint
n3
n2
C3
C1
n1
C2
C3
1
n1 x1  n3 x3  C3
2
Cut defines a second pooled resource
Conclusions
Mathematical models of end-to-end
congestion control show it to be a
distributed algorithm that: solves an
optimization problem; computes a fair
allocation; and finds a market clearing
equilibrium.
The models provide a framework for
engineering efforts to improve reliability
and robustness.
Further information and references
are available at:
www.statslab.cam.ac.uk/~frank