Transcript CS244a: An Introduction to Computer Networks

Intra-Domain Traffic Engineering
• Traffic Engineering (TE)
– MPLS and traffic engineering (will go over very briefly)
– traffic engineering as network-wide optimization problem
– TE through link weight assignments
•
Traffic Matrix Estimation (only briefly)
– challenges and issues
Readings: do the required readings.
CSci5221: Intra-Domain Traffic Engineering
1
Traffic Engineering
• Goal: configure routes to meet traffic demands
– balanced load, low latency, service agreements
• operates at coarse timescales
– Not to adapt to short-term sudden traffic changes
– May take potential failures into consideration
• Input to traffic engineering:
– Topology: connectivity & capacity of routers & links
– Traffic matrix: offered load between points in the
network
• Traffic Engineering: network-wide optimization
– Subject to protocol mechanisms, configurable
parameters and other practical constraints, ….
CSci5221: Intra-Domain Traffic Engineering
2
Traffic Engineering Framework
• Basic Requirements
– Knowledge of Topology
• Connectivity and capacities of routers/links of a network
– Traffic Matrix
• (average) traffic demand between difference
ingress/egress points of a network
• Instrumentation
– Topology: monitoring of the routing protocols
– Traffic matrix: “fine-grained” traffic measurement
and inference, for example, via
• SNMP
• edge measurements + routing tables
• network tomography
• packet sampling
CSci5221: Intra-Domain Traffic Engineering
3
Traffic Engineering Framework (cont’d)
• Traffic Engineering as Network-Wide Optimization
• Network-wide models
– Network topology:
graph (V,E), cij: capacity of link (i,j)
– Traffic Matrix:
K set of (ingress/egress) source-destination pair demands
– k K, dk – demand, sk – source, tk – destination
• Optimization criteria, e.g.,
– minimize maximum utilization,
– minimize sum of link utilization
– keep utilizations below 60%
CSci5221: Intra-Domain Traffic Engineering
4
Traffic Engineering as a Global
Optimization Problem
• topology G = (V,E)
• cij – capacity of link (i, j) ÎE
• K – set of origin-destination flows (demands)
–
k ÎK, dk - demand, sk - source, t k - destination
• Fkij: traffic load of O-D flow k routed on link (i,j)
Fij := å Fijk : total load ( of all demands ) on link (i, j)
k
•
Optimization objective function: F({Fij ,cij }) e.g., F({Fij ,cij }) := max{(i, j )ÎE} {Fij / cij }
or
F({Fij ,cij }) := å
CSci5221: Intra-Domain Traffic Engineering
{( i , j )ÎE }
{Fij / cij }
5
More Cost Functions
• works for rich set of cost
functions
• example:
F   ( i , j )E F ij (d k X ijk )
• where Fij are piecewise linear
CSci5221: Intra-Domain Traffic Engineering
6
Traffic Engineering as a Global
Optimization Problem (cont’d)
Objective function: minimize F({F ,c }) ij ij

 Constraints:
-- flow conservation: total outflow vs. total inflow
 0, i  sk , i  tk , k  K

k
k
 j:(i, j )E Fij   j:( j ,i )E Fji   d k , i  sk , i  tk , k  K
 d , i  s , i  t , k  K
k
k
 k
-- capacity and (non-negative load) constraints
k
F
kK ij  cij ,
(i, j )  E
Fijk  0
CSci5221: Intra-Domain Traffic Engineering
7
Traffic Engineering Example:
minimize maximum link utilization
• Minimize F({Fij ,cij }) := max{(i, j )ÎE} {Fij / cij }
• Multi-commodity flow problem
– There exists polynomial time solutions to the problem
• Equivalent linear programming formulation
– a -- maximum link utilization
– Let X k := F k / d
ij
ij
k
Xijk denotes fraction of demand k on link (i, j)
Xijk Î[0,1]
CSci5221: Intra-Domain Traffic Engineering
8
Traffic Engineering:
LP Formulation
min 
 0, i  sk , tk , k  K

k
k
s.t.  j:( i , j )E X ij   j:( j ,i )E X ji  1, i  sk , k  K
 1, i  t , k  K

k
k
d
X
 kK k ij  cij ,
(i , j )  E
0  X ijk  1
CSci5221: Intra-Domain Traffic Engineering
9
Traffic Engineering w/ MPLS
• We can set up label-switched paths (LSPs) between
origin-destination pairs to realize the optimal TE
traffic load distributions
• Let {X*kij} be the optimal solutions
– If for a given k (corresponding to a given O-D pair),
X*kij = 0 or 1,
then we set up one LSP (or tunnels) for the O-D pair
– Otherwise, traffic load for flow (demand) k is carried over
multiple paths, we need to set up multiple LSPs (or
tunnels) for the given O-D pair
• In general, traffic split among multiple LSPs are not equal!
• worst-case complexity:
– O(N^2E) LSPs/tunnels needed
CSci5221: Intra-Domain Traffic Engineering
10
Traffic Engineering w/o MPLS
• Can we perform traffic engineering without MPLS?
– we need to use “shortest path” routing
– But shortest paths are defined based on link weights
• TE becomes link weight assignment problem!
• Other constraints we need to take into account
– destination-based routing: not <src, dst> pair-based!
– multiple shortest paths (“equal-cost” paths, ECPs) may
exist and can be used for load-balancing
• But typical equal splitting is used to split traffic among ECPs
for a given destination prefix
• On the other hand, multiple destination prefixes are mapped
to the same egress point of a network!
CSci5221: Intra-Domain Traffic Engineering
11
Traffic Engineering under Shortest
Path Routing: Tuning Link Weights
• Problem: congestion along the blue path
– Second or third link on the path is overloaded
• Solution: move some traffic to bottom path
– E.g., by decreasing the weight of the second link
2
3
2
1
1
31
3
5
4
3
CSci5221: Intra-Domain Traffic Engineering
12
Effect of link weights
(see [FRT02])
• unit link weights
• local change to congested link
• global optimization
– to balance link utilizations
CSci5221: Intra-Domain Traffic Engineering
13
Shortest Path Routing and Link
Weight Assignment Problem
• Key Problem: how to assign link weights to optimize
TE objectives under conventional link-state
(shortest path) routing paradigm?
• Key Insight: traffic engineering optimization is
closely related to optimal link weight assignment
using “shortest path routing” (with some caveats!)
– The relationship comes from duality properties of linear
programming
• optimal link weight assignment problem is a dual problem
to the optimal traffic engineering problem!
For materials in slides 53-62, see [WWZ01]
CSci5221: Intra-Domain Traffic Engineering
14
Duality of Linear Programming
Primal
Dual
T
maximize c x
subject to Ax = b
x ³ 0,
•
•
•
minimize
T
y b
subject to y A £ c
T
T
Y’s are Lagrange multipliers for equality constraints Ax=b; z≥0
Lagrange multipliers for inequality constraints x≥0
Lagrange function: L(x, y, z) := cT x - yT (Ax - b) + zT x ³ cT x, if x is
a feasible solution
Lagrange dual: g(y, z) := infx³0 L(x, y,z) ³ cT x* (x* optimal solution)
g(y, z) = yT b if cT - yT A + zT ³ 0 or yT A £ cT as zT ³ 0
CSci5221: Intra-Domain Traffic Engineering
15
Complementary Slackness.
Let x and y be feasible solutions. A necessary
and sufficient condition for them to be
optimal is that for all i
1. xi > 0  yT Ai = ci
2. xi = 0  yT Ai < ci
Here Ai is i-th column of A
CSci5221: Intra-Domain Traffic Engineering
16
Example: Primal (P-SP)
• topology G = (V,E), link weights
min
{wij : (i, j) ÎE }
k
w
(
X
(i, j )E ij  ij )
k
s.t.
k
k
X

X
 j:(i, j )E ij  j:( j ,i )E ji  0,


j:( sk
k
X
ij   j:( j , s
, j )E
j:( t k , j )E
X   j:( j ,t
k
ij
k
i  sk , t k
k
X
ji  1,
)E
k )E
X  1,
k
ji
X 0
k
ij
CSci5221: Intra-Domain Traffic Engineering
17
Example: Dual (D-SP)
max kK U
k
tk
kK
s.t. U  U  wij ,
(i, j )  E
k
j
k
i
U  0,
k
sk
CSci5221: Intra-Domain Traffic Engineering
kK
18
Dual Solution Interpretation
max kK U
k
tk
kK
s.t. U  U  wij ,
(i, j )  E
k
j
k
i
U  0,
 
k
sk
kK
• U i k optimal solution to dual problem
• X ijk  0  U jk  U ik  wij , U jk length of shortest path
from sk to j
• U tkk length of shortest path from sk to tk
CSci5221: Intra-Domain Traffic Engineering
19
Duality (More General Form)
Dual
Primal
minimize y b + y b
maxmize c x
T
T
T
subject to Ax = b1 subject to y1 A + y2 A' £ c
y2 ³ 0
A' x ³ b2
x ³ 0,
T
•
•
T
1 1
T
2 2
y1: Lagrange multipliers for equality constraints Ax=b1;
y2≥0 : Lagrange multipliers for inequality constraints A’x≥b2
Lagrange dual: g(y1,y2) :=infx≥0 {cTx +yT1(b1-Ax) +yT2(b2-A’x)}
CSci5221: Intra-Domain Traffic Engineering
20
Load Balancing Optimization Problem
min
 d
(i,j)E kK
k
X
k
ij
 0, i  sk , tk , k  K

k
k
s.t.  j:(i , j )E X ij   j:( j ,i )E X ji  1, i  sk , k  K
  1, i  t , k  K
k


kK
d k X  cij ,
k
ij
(i, j )  E
0  X 1
k
ij
CSci5221: Intra-Domain Traffic Engineering
21
Re-formulating the Problem
• Let {X*kij} be optimal solutions, then dkX*kij is the
load of demand (flow) k placed on link (i,j)
• Define Cij* := å dk Xij*k
k
-- total load of all demands on link (i,j); C*ij b Cij
Primal Problem: min

k
d
X
 k ij
( i , j )E kK
 0, i  sk , tk , k  K

s.t.  j:( i , j )E X ijk   j:( j ,i )E X kji  1, i  sk , k  K
 1, i  t , k  K

k

k
d
X
ij  cij ,
kK k
(i , j )  E
0  X ijk  1
CSci5221: Intra-Domain Traffic Engineering
22
Dual Formulation
• dual variables
max
U , W 
k
d
U
 kK k tk 
k
i
k
i

( i , j )E
s.t. U  U  Wij  1,
k
j
ij
cijWij
k  K ,(i, j )  E
Wij  0
U 0
k
sk
CSci5221: Intra-Domain Traffic Engineering
23
Properties of Primal-Dual Solutions
 
  
• optimal solution to primal problem
X ijk
dual problem U ik , Wij
• if X ijk  0, then U jk  U i k  Wij  1
• can think of U jk as shortest path distance
from sk to j when link weights are W  1

ij

Therfore: solution to TE problem is also
solution to shortest path problem with
wij  Wij  1
CSci5221: Intra-Domain Traffic Engineering
24
Link Weight Assignment:
Generalization
• works for rich set of cost
functions
• example:
F  ( i , j )E F ij

k
d
X
k
ij
kK

• where Fij are piecewise linear
CSci5221: Intra-Domain Traffic Engineering
25
Issues
• solutions are flow specific - need
destination specific solutions
– not a big deal, can reformulate to account for this
• solutions may not support equal split rule of
OSPF
– accounting for this yields NP-hard problem
– modify IP routing
CSci5221: Intra-Domain Traffic Engineering
26
One approach to overcome the
“splitting problem”
• current routing tables have thousands of
routing prefixes
• instead of routing each prefix on all equal
cost paths, selectively assign next hops to
(each) prefix
– i.e., remove some equal cost next hops assigned to prefixes
• goal: to approximate optimal link load
see [FT00], [FRT02] and [SDG05]
CSci5221: Intra-Domain Traffic Engineering
27
Example :
EQUAL-SUBSET-SPLIT
j
Prefixes: D C
5+4=9
9
Prefix A : 5
Prefix B :
1Prefix C : 8
3
i
Prefix D : 10
Prefix A: Hops k,l
Prefix B : Hops k,l
Prefix C: Hops j,l
Prefix D: Hops j,l
CSci5221: Intra-Domain Traffic Engineering
k
Prefixes: A B
2.5 + 0.5 = 3
12
Prefixes: D C B A
l
5 + 4 + 2.5 + 0.5 = 12
28
Advantages
• requires no change in data path
• can leverage existing routing protocols
• current routers have 10,000s of routes in
routing tables
– provides large degree of flexibility in next hop allocation
to match optimal allocation
CSci5221: Intra-Domain Traffic Engineering
29
Performance
CSci5221: Intra-Domain Routing and TE
CSci5221: Intra-Domain Traffic Engineering
30
Traffic Engineering Summary
• can use OSPF/ISIS to support traffic
engineering objectives
• performance objectives link weights
– Further considerations:
• Link weight assignment under multiple traffic matrices,
and/or under multiple topologies (under link failures)
• equal splitting rule complicates problem
– heuristics provide good performance
– small changes to IP routing provide in better
performance
• MPLS suffers none of these problems, but
protocol more complex!
CSci5221: Intra-Domain Traffic Engineering
31
Traffic Demands & Traffic Matrices
• How to measure and model the traffic demands?
– Know where the traffic is coming from and going to
• Why do we care about traffic demands?
– Traffic engineering utilizes traffic demand matrices in
balancing traffic loads and managing network congestion
– Support what-if questions about topology and routing changes
– Handle the large fraction of traffic crossing multiple domains
• Understanding traffic demand matrices are critical inputs
to network design, capacity planning and business planning!
• How to populate the demand model?
– Typical measurements show only the impact of traffic demands
• Active probing of delay, loss, and throughput between hosts
• Passive monitoring of link utilization and packet loss
– Need network-wide direct measurements of traffic demands
• How to characterize the traffic dynamics?
– User behavior, time-of-day effects, and new applications
– Topology and routing changes within or outside your network
CSci5221: Intra-Domain Traffic Engineering
32
Traffic Demands
Big Internet
Web Site
User Site
CSci5221: Intra-Domain Traffic Engineering
33
Traffic Demands
Interdomain Traffic
AS 2
AS 3, U
AS 3
Web Site
AS 3, U
U
User Site
AS 1
AS 3, U
AS 4
AS 4, AS 3, U
•What path will be taken between AS’s to get to the User site?
•Next: What path will be taken within an AS to get to the User site?
CSci5221: Intra-Domain Traffic Engineering
34
Traffic Demands
Zoom in on one AS
OUT1
25
110
110
User Site
Web Site
300
200
75
300
110
IN
OUT2
10
50
110
OUT3
Change in internal routing configuration changes flow exit point!
CSci5221: Intra-Domain Traffic Engineering
35
Defining Traffic Demand Matrices
• Granularity and time scale:
– Source/destination network prefix pairs,
source/destination AS pairs
– ingress/egress routers, or ingress/egress PoP pairs?
– Finer granularity: traffic demands
likely unstable or fluctuate too widely!
CSci5221: Intra-Domain Traffic Engineering
36
36
Traffic Matrix (TM)
• Point-to-Point Model:
T: = [Ti,j ], where Ti,j from an ingress point i to an egress point j
over a given time interval
– ingress/egress points: routers or PoPs
– an ingress-egress pair is often referred to as an O-D pair
• Point-to-Multipoint Model:
– Sometimes it may be difficult to determine egress points due to
uncertainty in routing or route changes
Definition: V(in, {out}, t)
•
•
•
•
Entry link (in)
Set of possible exit links ({out})
Time period (t)
Volume of traffic (V(in,{out},t))
CSci5221: Intra-Domain Traffic Engineering
37
(Ideal) Measurement Methodology
• Measure traffic where it enters the network
– Input link, destination address, # bytes, and time
• Determine where traffic can leave the network
– Set of egress links associated with each network address
(forwarding tables)
• Compute traffic demands
– Associate each measurement with a set of egress links
• Even at PoP-level, direct measurement can be too expensive!
– We either need to tap all ingress/egress links, or collect
netflow records at all ingress/egress routers
• May lead to reduced performance at routers
• large amount of data: limited router disk space, export Netflow
records consumes bandwidth!
• Either packet-level or flow-level data, need to map to
ingress/egress points, and a lot of processing to generate TM!
• In practice: a combination of sampled flow measurements,
link loads & estimation/inference techniques
CSci5221: Intra-Domain Traffic Engineering
38
38