Transcript Document

MPLS Protection/Restoration
Instructor : Dr.Qiao
Ph.d Student:
Ming Zhao
HanSheng Lei
[email protected]
[email protected]
1
Multiprotocol Label Switching
Architecture & LDP
Introduction
MPLS Basics
LDP Procedures
LDP Specification

2
MPLS&LDP->Introduction

Conventional network forwarding
Each router analyzes the coming packet’s header and
independently chooses a next hop. Routing algorithm and
adequate speed are prerequisite.

MPLS forwarding
All forwarding is driven by the labels, no header analysis
needed. Once a packet enters a network, it’s assigned a
label. Each router forwards packets according their labels.
3
MPLS&LDP->Introduction

Advantages over conventional routing
1.
Router can use any information in determining label assignment, not
limited to packet header;
How to distribute labels may become more and more complicated,
without any impact on the routers that merely forward labeled
packets.
A label can be used to represent a pre-chosen route so that the
identity of explicit route need not be carried with the packet.
Mutiprotocol: its techniques are applicable to ANY network layer
protocol.
Etc.
2.
3.
4.
5.
4
MPLS&LDP->Introduction

Terminology. Some important terms.
FEC(forwarding equivalence class)
a group of IP packets which are
forwarded in the same manner (e.g., over the same path, with the
same forwarding treatment)
LSR(label switching router)
an MPLS node which is capable
of forwarding native Layer 3 packets
label swap
the basic forwarding operation
consisting of looking up an incoming label to determine the outgoing
label, encapsulation, port, and other data handling information.
MPLS domain
a contiguous set of nodes which
operate MPLS routing and forwarding and which are also in one
Routing or Administrative Domain
5
MPLS&LDP->MPLS Basics





Labels
Packet forward
Route selection
Tunnels and Hierarchy
Multiprotocol
6
MPLS&LDP->MPLS Basics->Labels
A label is a short, fixed length, locally significant
identifier which is used to identify a FEC. The label which
is put on a particular packet represents the FEC to which
that packet is assigned.
Most commonly, a packet is assigned to a FEC based
(completely or partially) on its network layer destination
address. However, the label is never an encoding of that
address.
7
MPLS&LDP->MPLS Basics->Labels
Ru
Upstream LSR
Rd
Downstream LSR
Agreement: "binding" label L to FEC F for packets moving
from Ru to Rd.
So, L becomes Ru's "outgoing label" representing FEC F, and
L becomes Rd's "incoming label" representing FEC F. Note
that L is an arbitrary value whose binding to F is local to Ru
and Rd.
8
MPLS&LDP->MPLS Basics->Labels

Label Assignment and Distribution
The decision to bind a particular label L to a particular
FEC F is made by the LSR which is DOWNSTREAM
with respect to that binding. The downstream LSR then
informs the upstream LSR of the binding.

Attributes of a Label Binding
A particular binding of label L to FEC F, distributed by
Rd to Ru, may have associated "attributes". If Ru, acting
as a downstream LSR, distributes a binding of a label to
FEC F, then under certain conditions, it may be required
to also distribute the corresponding attribute that it
received from Rd.
9
MPLS&LDP->MPLS Basics->Labels

A label distribution protocol is a set of procedures by which one LSR
informs another of the label/FEC bindings it has made.

The label distribution protocol also encompasses any negotiations in
which two label distribution peers need to engage in order to learn of
each other's MPLS capabilities.
THE ARCHITECTURE DOES NOT ASSUME THAT THERE IS
ONLY A SINGLE LABEL DISTRIBUTION PROTOCOL. E.g.,
[MPLS-BGP], [MPLS-RSVP], [MPLS-RSVP-TUNNELS], [MPLSLDP], [MPLS-CR-LDP].

10
MPLS&LDP->MPLS Basics->Packet forward
Unlabeled
Determine
FEC
Examine the
labeled
label of packet
Invalid label
ILM
Discard No
FTN
outgoing
label
NHLFE
Next Hop
Fig 1. Procedures to forward a packet
11
MPLS&LDP->MPLS Basics-> Packet forward


ILM(Incoming Label Map)
Maps each incoming label to a set of NHLFEs.
NHLFE(Next Hop Label Forwarding Entry)
It contains the following information:
1. the packet's next hop
2. the operation to perform on the packet's label stack; this is
one of the following operations:
a) replace the label at the top of the label stack with a
specified new label
b) pop the label stack
c) replace the label at the top of the label stack with a
specified new label, and then push one or more specified
new labels onto the label stack.
It may also contain some other information
12
MPLS&LDP->MPLS Basics-> Packet forward

FTN(FEC-to-NHLFE)
The FTN maps each FEC to a set of NHLFEs. It is used
when forwarding packets that arrive unlabeled, but which
are to be labeled before being forwarded.

Determine unlabeled packet’s FEC
LSR analyzes the layer network header to make decision.
How to analyze is beyond the scope of architecture.
13
MPLS&LDP->MPLS Basics-> Packet forward

Invalid Incoming Labels
when a labeled packet is received with an invalid incoming label, it
MUST be discarded, UNLESS it is determined by some means (not
within the scope of the MPLS architecture) that forwarding it
unlabeled cannot cause any harm.

Lack of Outgoing Label
Unless it can be determined that neither of these situations obtains, the
only safe procedure is to discard the packet.
- If the packet has been following an explicitly routed LSP, this
could result in a loop.
-The packet's network header may not contain enough information to
enable this particular LSR to forward it correctly.
14
MPLS&LDP->MPLS Basics-> Packet forward
15
MPLS&LDP->MPLS Basics-> Packet forward
16
MPLS&LDP->MPLS Basics-> Route selection

Hop by hop routing
Allows each node to independently choose the next hop for each FEC.
This is the usual mode today in existing IP networks. A "hop by hop
routed LSP" is an LSP whose route is selected using hop by hop
routing.

Explicit routing
A single LSR, generally the LSP ingress or the LSP egress, specifies
several (or all) of the LSRs in the LSP. Explicit routing may be useful
for a number of purposes, such as policy routing or traffic engineering.
17
MPLS&LDP->MPLS Basics-> Route selection
18
MPLS&LDP->MPLS Basics-> Tunnels&Hierarchy
R1
R3
R2
R21
R22
R23
R4
Level m-1
Level m
Fig. 2. Tunnels and Hierarchy
19
MPLS&LDP->MPLS Basics-> Tunnels&Hierarchy

Hop-by-Hop Routed Tunnel
If a Tunneled Packet follows the Hop-by-hop path from Ru to Rd, we
say that it is in an "Hop-by-Hop Routed Tunnel" whose "transmit
endpoint" is Ru and whose "receive endpoint" is Rd.

Explicitly Routed Tunnel
If a Tunneled Packet travels from Ru to Rd over a path other than the
Hop-by-hop path, we say that it is in an "Explicitly Routed Tunnel"
whose "transmit endpoint" is Ru and whose "receive endpoint" is Rd.
For example, we might send a packet through an Explicitly Routed
Tunnel by encapsulating it in a packet which is source routed.
20
MPLS&LDP->MPLS Basics->Multiprotocol

Labels for RSVP
When RSVP is used to set up resource reservations for particular
flows, it can be desirable to label the packets in those flows, so
that the RSVP does not need to be applied at each hop. It can be argued
that having RSVP distribute the labels as part of its path/reservation
setup process is the most efficient method of
distributing labels for this purpose.
21
MPLS&LDP->MPLS Basics->Multiprotocol

Labels for Explicitly Routed LSPs
In some applications of MPLS, particularly those related to traffic
engineering, it is desirable to set up an explicitly routed path,
from ingress to egress. It is also desirable to apply resource
reservations along that path.
One can imagine two approaches to this:
- Start with an existing protocol that is used for setting up
resource reservations, and extend it to support explicit routing
and label distribution.
- Start with an existing protocol that is used for label
distribution, and extend it to support explicit routing and
resource reservations.
22
MPLS&LDP-> LDP Procedures

The Procedures for Advertising and Using labels
There are a number of different procedures that may be used to
distribute label bindings.
The downstream LSR must perform:
- The Distribution Procedure, and
- the Withdrawal Procedure.
The upstream LSR must perform:
- The Request Procedure, and
- the NotAvailable Procedure, and
- the Release Procedure, and
- the labelUse Procedure.
23
MPLS&LDP-> LDP Procedures
1.
Downstream LSR: Distribution Procedure
The Distribution Procedure is used by a downstream LSR to
determine when it should distribute a label binding for a particular
address prefix to its label distribution peers.
2.
Upstream LSR: Request Procedure
The Request Procedure is used by the upstream LSR for an address
prefix to determine when to explicitly request that the downstream
LSR bind a label to that prefix and distribute the binding.
24
MPLS&LDP-> LDP Procedures
3.
Upstream LSR: Release Procedure
Suppose that Rd is an LSR which has bound a label to address prefix
X, and has distributed that binding to LSR Ru. If Rd does not happen to
be Ru's L3 next hop for address prefix X, or has ceased to be Ru's L3 next
hop for address prefix X, then Ru will not be using the label. The Release
Procedure determines how Ru acts in this case.
4.
Upstream LSR: labelUse Procedure
Suppose Ru is an LSR which has received label binding L for address
prefix X from LSR Rd, and Ru is upstream of Rd with respect to X.
Ru will make use of the binding if Rd is Ru's L3 next hop for X. The
labelUse Procedure determines just how Ru makes use of Rd's binding.
25
MPLS&LDP-> LDP Procedures

Security Considerations
Some routers may implement security procedures which depend on
the network layer header being in a fixed place relative to the data link
layer header. The MPLS generic encapsulation inserts a shim between
the data link layer header and the network layer header. This may
cause any such security procedures to fail.
An MPLS label has its meaning by virtue of an agreement between the
LSR that puts the label in the label stack, and the LSR that interprets
that label (the "label reader"). If labeled packets are accepted from
untrusted sources, or if a particular incoming label is accepted from
an LSR to which that label has not been distributed, then packets may
be routed in an illegitimate manner.
26
MPLS&LDP-> LDP specification




LDP Message Exchange
LDP Operation
LDP Discovery
LDP Session
27
MPLS&LDP-> LDP specification-> Message
Exchange

Discovery messages
used to announce and maintain the presence of an LSR in a network.

Session messages
used to establish, maintain, and terminate sessions between LDP peers.

Advertisement messages
used to create, change, and delete label mappings for FECs.

Notification messages
used to provide advisory information and to signal error information.
28
MPLS&LDP-> 5. LDP specification-> LDP Operation

FECs
Each FEC is specified as a set of one or more FEC
elements. Each FEC element identifies a set of packets
which may be mapped to the corresponding LSP.
1. Address Prefix. This element is an address prefix of
any length from 0 to a full address, inclusive.
2. Host Address. This element is a full host address.
29
MPLS&LDP-> 5. LDP specification-> LDP Operation

Label Spaces
The notion of "label space" is useful for discussing
the assignment and distribution of labels.
- Per interface label space.
Interface-specific incoming labels are used for interfaces that
use interface resources for labels. An example of such an
interface is a label-controlled ATM interface that uses VCIs as
labels.
- Per platform label space.
Platform-wide incoming labels are used for interfaces that can
share the same labels.
30
MPLS&LDP-> 5. LDP specification-> LDP Operation

LDP Identifiers
An LDP identifier is a six octet quantity used to identify an LSR
label space. The first four octets identify the LSR and must be a
globally unique value, such as a 32-bit router Id assigned to the
LSR. The last two octets identify a specific label space within the
LSR. The last two octets of LDP Identifiers for platform-wide label
spaces are always both zero.
<LSR Id> : <label space id>
e.g., lsr171:0, lsr19:2.
31
MPLS&LDP-> 5. LDP specification-> LDP Operation

LDP Sessions
LDP sessions exist between LSRs to support label exchange between
them. When an LSR uses LDP to advertise more than one label space
to another LSR it uses a separate LDP session for each label space.

LDP Transport
LDP uses TCP as a reliable transport for sessions.
When multiple LDP sessions are required between two LSRs there is
one TCP session for each LDP session.
32
MPLS&LDP-> 5. LDP specification-> LDP Operation
33
MPLS&LDP-> 5. LDP specification-> LDP Discovery
LDP discovery is a mechanism that enables an LSR to
discover potential LDP peers. Discovery makes it
unnecessary to explicitly configure an LSR's label
switching peers.
- A basic discovery mechanism used to discover LSR
neighbors that are directly connected at the link level.
- An extended discovery mechanism used to locate LSRs
that are not directly connected at the link level.
34
MPLS&LDP-> 5. LDP specification-> LDP Discovery

Extended Discovery Mechanism
LDP sessions between non-directly connected LSRs are supported by
LDP Extended Discovery.
Extended Discovery differs from Basic Discovery in the following
ways:
- A Targeted Hello is sent to a specific address
- Unlike Basic Discovery, which is symmetric, Extended Discovery
is asymmetric. Targeted LSR decides whether to respond to or
ignore the Targeted Hello.
35
MPLS&LDP-> 5. LDP specification-> LDP Session

Session Establishment
The exchange of LDP Discovery Hellos between
two LSRs triggers LDP session establishment.
Session establishment is a two step process:
- Transport connection establishment.
- Session initialization
36
MPLS&LDP-> 5. LDP specification-> LDP Session
NON
EXISTENT
Time out/Error
Time out/Error
ACTIVE ROLE
INITIALIZED
PASSIVE
Time out/Error
Keep Alive
OPENREC
OPENSENT
Keep Alive
OPERATIONAL
Shut Down/Time
out
Fig.3 Session Initialization State Machine
37
Outline



Introduction
MPLS Recovery Framework
MPLS Mechanism for Protection/Restoration




Shared Backup LSP Restoration
Fast reroute
RSVP-TE Recovery
A Heuristic Restoration Approach



Analysis
Simulations
Comparison
38
Outline



Introduction
MPLS Recovery Framework
MPLS Mechanism for Protection/Restoration




Shared Backup LSP Restoration
Fast reroute
RSVP-TE Recovery
A Heuristic Restoration Approach



Analysis
Simulations
Comparison
39
Current Backbone
Networks Protection

Link layer protection (SONET/SDH)



Be capable of service restoration within few tens
of milliseconds
The scope of the protection is limited, has no visibility
into higher layer operations
Layer 3 protection


Routing protocol provide much greater flexibility
The cost of the restoration time in the order of seconds
to minutes
40
Motivation: MPLS-Based Recovery




MPLS is the lowest layer with the knowledge of the entire
network topology
MPLS provide necessary traffic engineering capabilities
MPLS has desirable attributes when applied to the
purpose of recovery for connectionless networks
MPLS provide restoration times significantly shorter then
the convergence times of IP routing protocols
41
Definitions and Terminology

Rerouting
the recovery path or path segments are created
dynamically after the detection of a fault on the working
path. (the recovery path is not pre-established)

Protection Switching
In contrast the Rerouting, the recovery path is preestablished
42
Definitions and Terminology
Path Switch LSR (PSL)



The PSL is responsible for switching or replicating the
traffic between the working path and the recovery path
Normally chose as the Ingress LSR or the nearest
upstream LSR upon the failure node
Path Merge LSR (PML)



The PML is responsible for receiving the recovery path
traffic, and either merges the traffic back onto the
working path, or, if it is itself the destination, passes the
traffic on to the higher layer protocols
Normally chose as the Egress LSR
43
Definitions and Terminology

Fault Indication Signal (FIS)
A signal that indicates that a fault along a path has occurred.
It is relayed by each intermediate LSR to its upstream or
downstream neighbor, until it reaches the PSL

Fault Recovery Signal (FIS)
A signal that indicates a fault along a working path has been
repaired.Like the FIS,it is relayed by each intermediate LSR
to its upstream or downstream neighbor, until is reaches the
PSL
44
Fault Detection

Path Failure
detected by a link probing mechanism (hello liveness message )
between neighbor LSRs

Path Degraded
path has connectivity, but that the quality of the connection is
unacceptable (eg.high error bit rate, label mismatch or due to
TTL errors). it is detected by a path performance monitoring


mechanism
Link Failure
Link Degraded
the link over which the working path is carried is performing
below an acceptable level
45
Path Mapping


Path Mapping : the methods of mapping traffic from a faulty
working path on to the recovery path
1-to-1 Protection
recovery path that is only to be used to recover that specific
working path

n-to-1 Protection
n working paths are protected using only one recovery path

n-to-m Protection
n working paths are protected using m recovery paths, the n
working paths and the m recovery paths should be diversely
routed between the same PSL and PML
46
Scope of Recovery

Local Repair



protect against a link or neighbor node fault and to
minimize the amount of time required for failure
propagation
Fast but not optimized
Global Repair



the PSL is usually distant from the failure and needs to
be notified by a FIS
the recovery path can be made completely link and
node disjoint with its working path
slower than local repair
47
Post Recovery Operation




When traffic is flowing on the recovery path
decisions can be made to whether let the traffic
remain on the recovery path and consider it as:
a new working path (Non-Revertive Mode )
switch to the old (Revertive Mode )
switch to a new preferred working path
(
make before break ----- RSVP TE Recovery)
48
Outline



Introduction
MPLS Recovery Framework
MPLS Mechanism for Protection/Restoration




Shared Backup LSP Restoration
Fast reroute
RSVP-TE Recovery
A Heuristic Restoration Approach



Analysis
Simulations
Comparison
49
MPLS-based Recovery Principles

Configuration of Recovery



Initiation of Path Setup




Default-recovery (No MPLS-based recovery enabled)
Recoverable (MPLS-based recovery enabled)
Pre-established
Pre Qualified
Established-on-Demand
Initiation of Resource Allocation


Pre-reserved
Reserved-on-Demand
50
MPLS Recovery Cycle Model
Network Impairment
Fault Detected
Start of Notification
Start of Recovery Operation
Recovery Operation Complete
Path Traffic Restored
T1
T2
T3 T4
T5
T
T1 Fault Detection Time
T2 Hold-off Time
T3 Notification Time
T4 Recovery Operation Time
T5 Traffic Restoration Time
51
Main Comparison Criteria

Recovery Time
the time required for a recovery path to be activated (and traffic flowing) after a fault

Loss
Recovery schemes may introduce a certain amount of packet loss during switchover
to a recovery path.

Backup Capacity : corresponding to ( Quality of Protection )
The capacity will be dependent on the traffic characteristics of the network, the particular
protection plan selection algorithms as well as the signaling and re-routing methods.

Re-ordering
the action of putting traffic back on preferred paths might cause packet re-ordering

State Overhead
As the number of recovery paths in a protection plan grows, the state required to maintain
them also grows
52
Outline



Introduction
MPLS Recovery Framework
MPLS Mechanism for Protection/Restoration




Shared Backup LSP Restoration
Fast reroute
RSVP-TE Recovery
A Heuristic Restoration Approach



Analysis
Simulations
Comparison
53
Shared Backup LSP Restoration



links on the backup path can be shared between different
active paths
Single link failure restoration is guaranteed
using only aggregate network usage information without
requiring per-LSP routing information for all current active
LSPs

Aggregate information is obtainable by adding a few new
information elements to the link state advertisement of a link state
routing protocol like OSPF or ISIS
54
Model
A
B
LSP 2
LSP 2 B
C
LSP 2 B
LSP 1 B
D
LSP 2 B
LSP 1 B
LSP 1 B
LSP 1
E
F
G
LSP1 : E- F-G
LSP1 Backup : E-C-D-G
LSP2 : A- B
LSP2 Backup : A-C-D-B
55
Algorithm
For link (i,j)



the cumulative bandwidth allocated for active
paths is F(i,j)
the cumulative bandwidth allocated for backup
paths is G(i,j)
the residual bandwidth free for allocation is R(i,j)
56
Algorithm



For a request of bandwidth b the active path is calculated as
the shortest path on the topology of links that have R(i,j) > b
Let M be the max of the F values along the active path
The backup path is calculated as follows. The cost of a link
(u,v) is now taken as:





0
if { M+b < G(u,v) } else
b
if { G(u,v) <= M and b <= R(u,v) } else
M+b - G(u,v)
if { M <= G(u,v) and M+b <= G(u,v)+R(u,v) } else
infinity in all other cases
The backup path is calculated as the shortest path on the
topology with the cost of links calculated as above
57
Fast Reroute

Main Idea:
reverse traffic at the point of failure of the protected LSP back
to the source switch of the protected LSP such that the traffic
flow can be redirected via a parallel LSP between source and
destination switches of the protected LSP tunnel

Objective:



provide a single failure protection with quick restoration
comparable to the order of milliseconds
Minimize the alternative path computation complexity and
signaling requirements
1:1 protection and 1:N protection can be achieved
58
Fast Reroute Model
1:1 protection
24
46
LSR 2
LSR 4
LSR 6
67
12
31
53
35
13
LSR 1
75
LSR 3
From LSR 1 to LSR 7
57
LSR 5
LSR1: PSL ,
LSR 7
LSR7 : PML
Working LSP: 13-35-57 alternative LSP: 53 –31-12-24-46-67
59
Fast Reroute Model
( Using Label Stack )
1:N protection
24
20
12
57
12
20
24
57
24
46
20
46
46
57
20
LSR 2
LSR 4
LSR 6
67
12
57
31
31 57
13
LSR 1
10
40
20
53
75
35
LSR 3
40
57
LSR 5
30
LSR 7
20
15
LSR 8
LSR 9
60
Restoration Shortcuts
 LSR B setup the a shortcut alternative LSP
 Applied for Voice over IP service
LSR D
Source
LSR A
LSR B
LSR C
Destination
61
Prof. and Cons.

Path computation complexity is greatly reduced





both primary and alternative path computations can be
localized at a single switch
The amount of LSP setup signaling is minimized
presence of traffic on the alternative segment path
can be used as an FIS of the downstream primary
path
Data packet need reordering during the path
rerouting process
Less efficient use the resources (total length protection)
62
RSVP Detour





To achieve timely detour path setup, using precomputed and pre- established detour path is essential
for data traffic where packet loss is undesirable
Detour decision must be made as close to the failure
point as possible
Ideal detour mechanism is to protect the entire LSP
by establishing detour paths throughout the LSP
To minimize the path computation overhead, it is
desirable for the detour paths to merge back to the
main LSP as soon as possible
Now, only protect unidirectional LSP
63
RSVP Detour Model
Activate RSVP Tunnel (LSP)
RSVP Detour (LSP)
detour ( Ingress,LSR2 )
Ingress
LSR 1
LSR 2
LSR 3
Egress
For detour ( Ingress,LSR2 ) , LSR1 and LSR 3 are not aware of the detour
64
RSVP Extension
Two new objects are defined to support LSP fast-reroute
 FAST_REROUTE object




Setup (Holding) Priority: The priority of the detour with respect to
taking(holding) resources
Hop – limit: The maximum number of extra hops the detour is
allowed to take
Bandwidth
DETOUR object


Source ID : IPv4 address identifying the beginning point of detour
Downstream Node ID :IP address identifying the downstream node
that source is trying to avoid
65
Make before break



In general, it is highly desirable not to disrupt traffic, or
adversely impact network operations while TE tunnel
rerouting is in progress.
This adaptive and smooth rerouting requirement
necessitates establishing a new LSP tunnel and
transferring traffic from the old LSP tunnel onto it before
tearing down the old LSP tunnel
The principle (implemented by RSVP Tunnel) applies
not only in the case of failure but also when better routes
are available than the existing ones.
66
Outline



Introduction
MPLS Recovery Framework
MPLS Mechanism for Protection/Restoration




Shared Backup LSP Restoration
Fast reroute
RSVP-TE Recovery
A Heuristic Restoration Approach



Analysis
Simulations
Comparison
67
Analysis
Basic Idea




Providing fault tolerance in MPLS networks based on the
concept of “ domain protection”
In that domain, protection paths for all working paths that
terminate in an egress router are calculated simultaneously
The algorithm attempts to locate two trees in the domain
such that no single link failure would disconnect a node
form the root of the tree (the egress node)
Permit the decoupling the protection path placement from
the working path (much greater flexibility)
68
Analysis
Conditions


Assume MPLS domain represented by graph
G(N,L)
 N is the set of n nodes
 L is the set of l links between the nodes
Assume that graph G is two-edge redundant and
therefore can be protected against any single link
failure
69
Analysis



Input : The MPLS domain D and the egress router e
Output : two collections of protection path
connecting ingress routers to egress router e
Initialization:



Find a spanning tree of graph G rooted in the egress
router e.
Let P be the set of nodes for which the protection paths
have been established
Initially it contains the egress router: p ={e}
70
Heuristic Algorithm
Repeat until all nodes are protected (P=N):
1.
2.
3.
Select one of the branches of the spanning tree
attached to the egress node and mark all its nodes
except for the egress node
Scan all marked nodes to find node i that has a link to
an unmarked node j
Find a ring path consisting of the links of the spanning
tree leading from e to i, the link between I and j, and
the links of the spanning tree between j and e ( note
that if j = e, this segment of the ring is empty )
71
Heuristic Algorithm (Cont.)
Place two ring paths along the ring:
4.
1)
2)
3)
one in clockwise, the other in counterclockwise direction
Merge the created protection paths with protection paths
established in the previous iterations of the algorithm for the
protected nodes that are now a part of the egress node
All nodes on the ring are added to p
5.
Consider a new graph constructed by treating all nodes
in P as a single node that will act as the egress node
6.
Begin the subsequent iteration
72
Heuristic Model
1. Find a branch
F
2. Find node C has a link
with an unmarked node D
D
3. construct the ring
C
C
E
BB
A
4. All nodes on the ring
are now a part of the
egress node
5. Next iteration : Node
F assume both node C
and D as egress node,
and setup the protection
path respectively
73
Quality of a protection Scheme

Finding optimal protection path
The length of the protection path



Indicate the delay of the traffic after a link failure
Reflect the amount of the resources required to protect
the domain
The number of protection paths pre link


Indicate the amount of resources (eg. Label table size,
signalling overhead need to maintain the protection)
Indicate that how well the protection paths are
distributed throughout the network
74
Heuristic Decisions

Spanning tree selection




The protection paths are routed mostly along the
branched of the spanning tree
Try to find up a spanning tree with many short
branches
Using the Dijkstra’s algorithm to calculate the
shortest path spanning tree
Finding the smallest possible ring

Reduce the maximum and the average protection
path lengths
75
Heuristic Decisions Example


Find the short branch
A-B-C (step 1)
Comparison the length
of the ring (step 2 &3)

A-B-C-F selected
Heuristic edge Decisions
76
Simulations
Maximum length of protection paths for meshes
Average length of protection paths for meshes
77
Simulations
Number of protection paths per link for meshes
Avg. number of protection paths per link for meshes
78
Comparison of MPLS
Protection Schemes
79
Conclusion





The scheme considers protection of all paths leading from
ingress routers to a common egress router
Protection using two paths allow for greater flexibility in
protection path placement
It provides the protection is better than Fast Reroute
scheme
The algorithmic complexity is less than that of RSVP
Backup Tunnel while providing comparably good
protection
Unlike the FR and BT schemes, it guarantees
independence of the working and protection path
placement
80
MPLS Recovery Goals




Using traffic engineering to optimal use of resources
Aim to facilitate restoration times that are sufficiently
fast for the end user application
Aim to maximize network reliability and availability
Aim to be applicable for protection of traffic at various
granularities




for a portion of the traffic on an individual path
for all traffic on an individual path
for all traffic on a group of paths
Be applicable for segments or an entire end-to-end path
81
References







Framework for MPLS-based recovery Vishal Sharma, Ben-Mack Crane,
<Draft-ietf-mpls-recovery-framework-03> , July 2001
Extensions to RSVP-TE for MPLS Path Protection Ken Owens, Vishal Sharma
<Draft-chang-mpls-path-protection-02>, July 2001
Shared Backup Label Switched Path Restoration Sriganesh Kini Murali
Kodialam <Draft-kini-restoration-shared-backup-01>, May 2001
A Method for Setting an Alternative Label Switched Paths to Handle Fast
Reroute Dimitry Haskin , Ram Krishnan <Draft-haskin-mpls-fast-reroute-05>,
November 2000
A Method for MPLS LSP Fast-Reroute Using RSVP Detours Der-Hwa Gan,
<Draft-gan-fast-reroute-00 > April 10, 2001
MPLS RSVP-TE Interoperability for Local Protection/Fast Reroute Alia
Atlas ,Curtis Villamizar <Draft-atlas-rsvp-local-protect-interop-01>, July 2001
“ A heuristic approach to service restoration in MPLS networks,” in proc. Of the
2001 IEEE International Conference on Communications (ICC), Helsinki, Finland,
June 2001
82