Transcript how to link

Lecture 15. IGP and MPLS
D. Moltchanov, TUT, Spring 2015
Outline
IP intra-domain traffic engineering
MPLS tunneling optimization
IP intra-domain traffic engineering
IP Intra-domain TE
Routing in the Internet
Intra-domain (interior gateway protocols, IGP)
Inter-domain (exterior gateway protocols, EGP)
Intra-domain routing
Performed by ISP controlling its own network
Efficiently for cross-traffic and own traffic
IGP Routing protocols
Open shortest path first (OSPF, IETF)
Intermediate system to intermediate system (IS-IS, ITU-T)
Link-state protocols with similar functionality
Link-state: use link-weight metrics to determine shortest path
Provides common view for all the routers in the networks
IP Intra-domain TE
An example of general problem
How to minimize the delay for packets traversing the network
What would be the appropriate way of doing so?
Delays happens due to link congestion
Suppose happens on the shortest path for a demand
Link weight is too low on a link?
Shortest path should not use this link
How? Increase the link weight!
OSPF/IS-IS will use other link instead of this one
General problem
Determine the links weights such that
SPs are determined in a way minimizing the delay!
Which delay?
Average packet delay, not individual one
On all links individually? Average over all links?
IP Intra-domain TE
Input data
Network itself: graph having V nodes, E links
Demands between routers: hd , d  1, 2, , D
Link capacities: ce , e  1, 2, , E
Design objective
Metric related to delay but which one?
Minimize the maximum link utilization!
What are we doing with this?
Minimizing delay
On all SPs simultaneously!
The problem now
Minimize the maximum link utilization, given that we have
demands hd , d  1, 2, , D and link capacities ce , e  1, 2, , E
and the routing happens according to OSPF/IS-IS
IP Intra-domain TE
Formulating the problem mathematically
Let the link weights system be w  ( w1 , w2 , , wE )
It induces all the flows in the network
OSPF/IS-IS: SP routing with “equal-cost multi-path” rule (ECMP)
Let p  1,2, , Pd be the set of all path for demand d
Not necessarily SP as we do not know w yet
Can be done using K-shortest path algorithm
Let xdp ( w) flow of path p for demand d induced by w
We have demand constraints
Pd
x
p 1
dp
( w)  hd , d  1, 2,
,D
Isn’t is similar to what we got solving NDP problem?
Yes, but flows depend on the link metric system w !
IP Intra-domain TE
Getting capacity constraints is next
Let  edp {0,1} be the link path indicator
 edp  1 if route p for demand d uses link e, 0 otherwise
Link load of link e is given by
D
Pd
ye ( w)    edp xdp ( w), e  1, 2,
,E
d 1 p 1
And it should be less than given capacity of link e
D
Pd
ye ( w)    edp xdp ( w)  ce , e  1, 2,
,E
d 1 p 1
What we got so far?
Demand constraints
Pd
x
p 1
D
Capacity constraints
dp
Pd
( w)  hd , d  1, 2,

d 1 p 1
,D
x ( w)  ce , e  1, 2,
edp dp
,E
IP Intra-domain TE
What is our objective?
Minimize maximum utilization of the link
Utilization of a link e is
ye ( w) ce , e  1, 2,
,E
The maximum utilization is then
 max  max ye ( w) ce
e 1,2, , E
The whole problem: minimize F  max ye ( w) ce over w
e 1,2, , E
subject to:
Pd
x
p 1
D
dp
Pd
( w)  hd , d  1, 2,

d 1 p 1
,D
x ( w)  ce , e  1, 2,
edp dp
for integers we , e  1, 2,
E
,E
IP Intra-domain TE
Can also be stated as
Minimize F   over w and 
Subject to
Pd
x
dp
p 1
D Pd
( w)  hd , d  1, 2,

d 1 p 1
,D
x ( w)  ce  , e  1, 2,
edp dp
for integers we , e  1, 2,
and continuous 
,E
E
If optimal   1 then no links are congested
Practice: task is solved in off-line and then w are disseminated
Why? No need to implement on-line
Complex to solve! There might be no solutions!
IP Intra-domain TE
What is about relaxed model?
What if no constraints are imposed by w ?
This means when allocations xdp are free of dependence on w
Does it has any significance for SP problems like this?
Why we care? That would be LP problem
Results for relaxed model
In general far from optimal 
Link metric system induces strict constraints on xdp ( w)
MPLS tunneling optimization
MPLS tunneling optimization
Why MPLS?
MPLS: multi-protocol label switching
No hop-by-hop routing anymore
Virtual paths (AKA tunnels) instead are used
An individual virtual path for a traffic class
No more IP routing in domains
A virtual class is uniquely identified by labels
Why MPLS is so good?
We can route as we want
Not only along shortest paths
Can work with DiffServ
Can provide QoS (together with DiffServ) and network control…
Huge popularity in US (see Verizon, Comcast, etc.)
MPLS tunneling optimization
MPLS tunnels
Also called label switched path (LSR)
Established using label distribution protocol (LDP)
Without MPLS TE: just mapping from OSPF
With MPLS TE: whatever we want
MPLS TE features: RVSP-TE or LDP-TE
We need to know how and where to set-up tunnels
Problems?
Number of tunnels: should be kept at minimum
How and where to establish tunnels such that load is balanced
Task statement
How to carry different traffic classes in MPLS network though
the creation of tunnels in such a way that the number of tunnels
on each MPLS switch is minimized while the load is balanced
MPLS tunneling optimization
Formalization of the problem
d denotes a demand (depends on traffic class and pair of nodes)
hd is the demand volume
a demand can be carried over different tunnels (splitting allowed!)
Do the following
let Pd be the number of different paths allowed for d
let xdp be the fraction of demand d routed over p
We get demand constraints
Pd
x
p 1
dp
 1, d  1, 2,
,D
Notice
different use of flow variable
We may get plenty of flows with small allocation…
Recall we want to keep the number of tunnels at minimum!
MPLS tunneling optimization
What to do with “small” allocations?
Introduce a minimum constraint (lower bound)  ?
letting udp {0,1}: 1 if higher than  and 0 otherwise
How to use udp and  to enforce no “small” flows?
If tunnel is chosen: greater than 
 udp  hd xdp , d  1, 2, , D, p  1, 2, , Pd
If not (less than  ): force to 0
xdp  udp , d  1, 2,
, D, p  1, 2,
Capacity constraint:
Pd
D
 h 
d 1
d
p 1
x  ce , e  1, 2,
edp dp
Number of tunnels on a link
D
Pd

d 1 p 1
u
edp dp
,E
, Pd
MPLS tunneling optimization
Objective function
Minimize number of tunnels to carry traffic
Let r be the max number of tunnels over all links
The problem
Minimize F  r
Subject to
Pd
x
p 1
dp
 1, d  1, 2,
Pd
D
,D
 h 
d 1
d
p 1
 udp  hd xdp , d  1, 2, , D, p  1, 2, , Pd
xdp  udp , d  1, 2,
, D, p  1, 2,
, Pd
x  ce , e  1, 2,
edp dp
D
Pd

d 1 p 1
,E
u r
edp dp
xdp continuous non-negative, udp binary, r integer
Continuous and discrete variables? Mixed integer problem! Complex…
Can be extended to limit number of tunnels on a single link!