Transcript 2001DecSem1_finalpre..

A General approach
to MPLS Path Protection
using Segments
Ashish Gupta
Ashish Gupta
Overview
• Intro to MPLS
— Difference from IP
• Why Path Protection ?
— Existing Schemes
• Segment Based Approach
— Its Mechanisms
— Algorithm for segment setup
— Simulation Results
— Detection , Notification and Path Switching
1
MPLS Label Distribution
Intf Label Dest Intf Label
In In
Out Out
3
0.50 47.1 1
0.40
Intf
In
3
Label Dest Intf
In
Out
0.40 47.1 1
1
Request: 47.1
3
Intf Dest Intf Label
In
Out Out
3
47.1 1
0.50
3
2
1
1
47.1
Mapping: 0.40
2
47.3 3
47.2
2
2
Label Switched Path (LSP)
Intf Label Dest Intf Label
In In
Out Out
3
0.50 47.1 1
0.40
Intf Dest Intf Label
In
Out Out
3
47.1 1
0.50
Intf
In
3
Label Dest Intf
In
Out
0.40 47.1 1
IP 47.1.1.1
1 47.1
3
3
2
1
1
2
47.3 3
47.2
2
IP 47.1.1.1
3
The Need for Path Protection
What happens if fault occurs in a network element ?
For traffic with critical QOS requirements , fast rerouting is required
IP rerouting can take order of seconds
Solution : Protect the path with another backup path
4
Existing Schemes
•
Global Path Protection
Original LSP
Backup LSP
•
Local Path Protection
r
•
Link Failure
•
Node Failure
Drawback :
No flexibility in providing path protection for a MPLS network
Segment Based Approach : A General Scheme for Path
5 Protection
Segment Based Approach
•Protect each segment separately : Each segment seen as a single unit of
failure
•SSR – Segment Switching router
•Flexibility in creating segments -> flexibility in Path Protection ( delay and
backup paths )
•SBPP – Segment Based Path Protection
6
Steps in SBPP
•
Creation of LSP
•
Creation of segments - Greedy Algorithm
•
Reservation of Backup Paths
— Backup paths as tunnels
•
A new combined Algorithm
— Advantages
•
Label Management in SBPP
•
Changes required in LSR
•
Label Distribution Mechanisms
•
Signaling mechanisms
•
Buffering to avoid packet loss and reordering
•
Steps in recovery :
—
—
—
—
•
Fault Detection and Localization
Fault Notification– How does it work in MPLS ?
Switching the path
Backup Path recovery
Experimental Results
7
Fault Detection , Localization and Notification
• Fault can be detected by periodically sending
liveness messages – Absence of response
indicates link/node failure
• For faster detection , each node sends periodic
messages to its neighbors
• Timing Analysis for Detection and Notification
8
Fault Detection , Localization and Notification
9
Creation of Segments
• Created according to QOS criteria
— Delay , Reliability , Bandwidth
• Just ensure each segment individually meets the criteria
• Example - Bounded Delay on switching
— Greedy Algorithm
Some Problems - Experiments
10
Issues in Reservation of Backup Paths
• Avoiding Loops
• Sharing of backup paths important
— Cases :
– 1. Multiple LSPs , Multiple Segments
– 2. Multiple LSPs, Same Segment
— Assumptions : Only one failure at a time
• Problem with the previous approach – see figure
11
Loops in Backup Paths
12
Problem with Greedy Algorithm
13
A New Combined Algorithm
• Possible approaches
— Exhaustive search for a suitable path – computationally exhaustive –
need a heuristic
• The Combined Path Setup Algorithm
— 1. Setup a primary path ( based on a constraint e.g. min delay)
— 2. Start from egress node and find the largest possible segment which
satisfies bounded delay switching time constraint ( call the SSR of this
segment S1 )
— 3. Find a backup path for this segment starting from S1
— 4. If no backup path can be found , shrink the segment and try to find the
backup path from the new SSR. If no further shrinking is possible then
Reject request( or try another primary path - see below)
— 5. Repeat Step 4 until a segment with a backup path is found.
— 6. Repeat from step 2 for creating the next segment
— 7. Do this until the complete LSP is segmented.
14
Advantages of this algorithm
• Ensures that if segmentation is possible on the
primary path, then it will be performed.
• Here we have multiple starting nodes possible
for finding the backup paths , so possibility of
finding backup paths is more
• Can add more flexibility for the choice of SSR in
forming segments e.g. case of overloaded LSR –
won’t be made a SSR
15
Description of Simulation Setup
• An MPLS network of was created
— 100 Nodes
— 200 Edges
• RTT of each link = 10 ms
• Periodicity of Liveness message = 2 ms
• BW – 50 to 100
• Generated large number of random LSPs requests
and observed various parameters
• Results indicate advantages of SBPP
16
Segment Size vs BW reserved
17
Segment Size vs BW reserved
18
Segment Size vs Rejection Rate ( for 250 LSPs )
19
No. of Requested LSPs vs Rejection Rate
20
Effect of Backup Path Sharing
Bandwidth reserved vs No. of LSPs setup
22
Crossover - Effects of backup path sharing
23
Further Analysis – More possibilities
• End-to-end delay of Backup Path also affects switching time !
• Long backup paths : Higher end-to-end delay : Higher Switching
time so have to constrain backup path construction also
• New expression for switching time
— Tp + RTT + (t2-t1) < max. switching delay
• Can help in providing bound in other performance metrics like
jitter
24
Steps in Rerouting
A Mechanism for Notification
• After a fault is detected, notification needs to be sent
to the SSR for switching the traffic
• Some nodes will participate in notification and the SSR
will switch the route
• What information will be passed after a fault occurs ?
• What changes do we need in the LSR tables for
switching?
• Case of Multiple LSPs : All LSPs using that segment
may not pass through the faulty node/link – Only
concerned LSPs should be switched
26
A Mechanism for Notification
27
Other work
• Creating Backup paths using tunnels
• Analysis of Liveness message periodicity
28
Future Work
• Label Management and Distribution Issues
• Formal Definition of Protocol and Signaling
Mechanisms required for detection, notification and
other parts of our scheme
• Use of buffering to reduce packet loss during
switchover
• Recovery Issues
• Implementation of our scheme in MPLS emulator.
29
Targets specified in Mid-sem
• December 1st 2001
— Error detection and notification issues in Segment based
protection (SBP)
— Work out example scenarios using SBP
— An algorithm for SBP
— Label management issues in SBP
• May 1st 2002
— Simulations to test performance and resource usage vs.
other schemes
— Explore other issues like Buffering
— Documenting our work
30
Thank You