Transcript N-hub routing - The Department of Computer Science

Maximizing Restorable Throughput in MPLS
Networks
Reuven Cohen
Dept. of Computer Science, Technion
Gabi Nakibly
National EW Research Center
Published in Infocom 2008 – mini-conference
1
Motivation





2
IP networks are required to service real-time applications such as phone
conversation
These services demand high availability and reliability, and in particular
– Fast restoration
– Guaranteed QoS even in the case of failures
IP routing protocols are not able to provide these features
MPLS protection mechanisms are able to provide these features
– by pre-establishment of backup LSPs
We study the effectiveness of the various MPLS protections schemes
Outline





3
Define the various MPLS protection schemes
Define our optimization metric
Define four different problem models
Present algorithms for the various protections mechanisms and models
Present simulations results for the various algorithms
The protection schemes we study
1.
A Global Recovery scheme (GR)
–
–
2.
S
A
B
D
A Local Recovery scheme (LR)
–
–
–
4
For each LSP we find a path between
the same (S,D) pair that does not use
any link of the LSP
The backup path can protect against
any failure along the LSP
For each link A-B we find a path that
starts at A and ends between B and D
Recovery is faster than GR (because
it is initiated by the detecting node)
However, more backup LSPs are
needed for the protection of each LSP
S
A
B
a standard MPLS scheme
D
The protection schemes we study (cont.)
3.
A Restricted Local Recovery scheme
(RLR)
–
4.
A Facility Local Recovery scheme
(FLR)
–
5
The backup path for link A-B is
established between A and B
Same as RLR, except that the new
path serves all the LSPs that use the
failed link
S
A
A
B
D
B
a standard MPLS scheme
The protection schemes we study (cont.)
5.
An extended k-facility Local
Recovery scheme (EkFLR)
–
–
6.
A
B
A
B
An Unrestricted Recovery scheme
(UR)
–
6
Same as FLR, except that the
number of LSPs protected by each
backup path is limited to k
Hence, we can use more backup
paths for the failed LSPs
The backup path for every link can
use any route and can protect any
number of LSPs
S
D
Our optimization criterion

Most past research aims at minimizing the total bandwidth reserved for
the backup LSPs (Spare Capacity Allocation).
–

We believe that network operators struggle with a different problem:
–

7
Such models consider a network with unbounded capacities, and a cost
function associated with bandwidth usage.
They have a network with finite link capacities and seek to maximize the
traffic that can be admitted with protection.
Our optimization criterion: constructing primary and backup LSPs
while maximizing throughput.
Our four problem models
A capacitated directed network
We make the common “single-failure” assumption.
A set of source-destination pairs with associated BW demands and
profits.



Splittable
Unsplittable

Each flow can be split over several  One primary LSP and one
primary or backup paths
backup LSP
 Each flow can be partially satisfied  All or nothing
Primary-restricted
8
the primary LSPs are given in
advance
Primary + Backup
We also need to establish the
primary LSPs (joint optimization)
Our results
1.
2.
3.
4.
5.
We show that the splittable version of the problem is in P and we offer a
polynomial time algorithm for it.
We show that the unsplittable version of the problem is NP-complete and
has no approximation algorithm with a ratio better than |E|½.
We propose an approximation algorithm with that ratio.
We present efficient heuristics for the various recovery schemes.
We compare the various recovery schemes with respect to our
throughput maximization criterion.


9
We show that UR, GR and, LR differ only marginally in their performance.
 Since LR has the fastest restoration time of the three schemes, it should
be the scheme of choice.
We show that EkFLR with k=2 has almost the same performance as RLR and
should be preferred over it.

Due to its lower administrative overhead (fewer backup LSPs).
Complexity results - summary
1.
2.
3.
10
4.
S-PRFP (Splitable, Primary restricted)
U-PRFP (Unsplitable, Primary restricted)
S-RFP (Splitable, joint primary/backup optimization)
U-RFP (Unplitable, joint primary/backup optimization)
primary route is already given
S-PRFP
The Splittable Primary-restricted Restorable Flow
Problem (S-PRFP)


11
It is in P for all recovery schemes.
We showed it using the following linear program:
–
- the fraction of flow f routed over edge e when edge e fails
–
- the routed fraction of f
Maximize the profit
S-PRFP
LP common constraints

The following constraints are common to all recovery schemes:

(C1) = flow conservation
(C2) = capacity constraints
(C3) = a flow is routed on its primary LSP as long as there is no failure
(C4) = a flow is not routed over a failed link


12

S-PRFP
The recovery-specific LP constraints for LR
S


13
A
B
D
This rule ensures that the backup LSP will follow the primary LSP all the
way from the source to A.
From node A to the destination node, the backup LSP is not constrained.
S-PRFP
The recovery-specific LP constraints for RLR
S

14
A
B
D
RLR-1 is similar to LR-1, except that it also ensures that the backup LSP
will follow the primary LSP from B to the destination.
S-PRFP
The recovery-specific LP constraints for GR
S


16
A
B
D
GR-1 ensures that the backup LSPs must be edge disjoint with the primary LSP.
GR-2 and GR-3 ensures that the backup LSPs are identical for every failure.
S-RFP
The Splittable Restorable Flow Problem (S-RFP)



17
Joint primary and backup LSP optimization
The same linear program but without the primary LSP constraint (C-3).
Can only be applied to RLR scheme.
The “penalty of reliability” in the Splittable Primaryrestricted model
optimal algorithm
w/ restoration





26
optimal algorithm
w/o restoration
For each backup scheme we find the ratio OPT_S-PRFP/OPT_S-PFP
For all schemes: it is easier to protect when load is lower
As expected, UR is the best
As expected, LR is better than RLR
The advantage of GR over LR is
interesting
S
A
B
D
GR
S
A
B
D
LR
S
A
B
D
RLR
The penalty of unsplittable backup LSPs (for primaryrestricted)

We see here the penalty ratio
for using unsplittable backup
–


29
As a function of the load in
the network
Surprisingly, the penalty
decreases as the load
increases.
Can be explained by the fact
that the primary LSPs
traverse the shortest-paths.
The benefit of joint optimization (primary + backup)


30
As expected, as the load in
the network increases so does
the penalty of using primary
LSP set in advance.
The penalty increases for
network with higher average
degree.
Conclusions





The first comprehensive study of maximizing restorable throughput in
MPLS networks
We considered 4 models of the problem and 6 restoration schemes
The splittable versions are in P
The unsplittable versions are all NP-complete, and they cannot be
approximated within |E| ½-
LR should be the recovery scheme of choice
S
31
A
B
D