Transcript Powerpoint Slides

Protection Routing in an MPLS Network
using
Bandwidth Sharing with Primary Paths
Zartash Afzal Uzmi
Computer Science and Engineering
Lahore University of Management Sciences (LUMS)
Visiting Professor – Chonbuk National University
Jan 13, 2006
Lahore University of Management Sciences
1
Outline

Background
 Network Services and QoS Requirements
 Protection Routing in MPLS
 Backup Bandwidth Sharing


Sharing with Primary Paths
NPP++ Protection Routing Framework

Routing Overhead
Path Computation
 Path Signaling
Simulation Results
 Evaluation and Experimentation
 Simulation Parameters
 Comparative Results


Jan 13, 2006
Lahore University of Management Sciences
2
Outline

Background
 Network Services and QoS Requirements
 Protection Routing in MPLS
 Backup Bandwidth Sharing


Sharing with Primary Paths
NPP++ Protection Routing Framework

Routing Overhead
Path Computation
 Path Signaling
Simulation Results
 Evaluation and Experimentation
 Simulation Parameters
 Comparative Results


Jan 13, 2006
Lahore University of Management Sciences
3
IP versus MPLS


In IP Routing, each router makes its own routing
and forwarding decisions
In MPLS:




Only one router (source) makes the routing decision
Intermediate routers make forwarding decisions
A path is computed and a “virtual circuit” is established
from ingress router to egress router
An MPLS path or virtual circuit from source to
destination is called an LSP (label switched path)
Jan 13, 2006
Lahore University of Management Sciences
4
QoS Requirements

Bandwidth Guaranteed Primary Paths


Bandwidth Guaranteed Backup Paths


MPLS allows establishing bandwidth-guaranteed paths
BW remains provisioned in case of network failure
Minimal “Recovery Latency”

Recovery latency is the time that elapses between:
 “the occurrence of a failure”, and
 “the diversion of network traffic on a new path”
Preset backup paths needed for minimal latency
Jan 13, 2006
Lahore University of Management Sciences
5
Types of Backup Paths
LOCAL PROTECTION (showing one LSP only)
All links and all nodes are protected!
nnhop
A
B
D
C
E
nhop
PLR: Point of Local Repair
Primary Path
Backup Path
Jan 13, 2006
Lahore University of Management Sciences
6
Opportunity cost of backup paths

Protection requires that backup paths are setup in
advance

Upon failure, traffic is promptly switched onto preset
backup paths

Bandwidth must be reserved for all backup paths


This results in a reduction in the number of Primary LSPs
that can otherwise be placed on the network
Can we reduce the amount of “backup bandwidth” but
still provide guaranteed backups?

Jan 13, 2006
YES: Try to share the bandwidth along backup paths
Lahore University of Management Sciences
7
BW Sharing in backup Paths

Example:
LSP1
A
BW: X
Sharing is possible
B
IF
X
X
E
LSP2
G
F
X+Y
Y
C
X
max(X, Y)
BW: Y
Y
Links (A,B) and (C,D)
do not simultaneously
fail!
D
Primary Path
Backup Path
Jan 13, 2006
Lahore University of Management Sciences
8
Sharing with Primary Paths

Can we do any sharing with primary paths?




Normally, the answer is NO because…
Traffic is always flowing on the primary paths
BUT…
Backup paths protecting a node N may share
bandwidth with primary paths that originate or
terminate at node N because…

Such backup will be active when:
 node N fails, and in that condition…
 No primary originates or terminates at node N
Sharing with (some) primary paths is possible
Jan 13, 2006
Lahore University of Management Sciences
9
Outline

Background
 Network Services and QoS Requirements
 Protection Routing in MPLS
 Backup Bandwidth Sharing


Sharing with Primary Paths
NPP++ Protection Routing Framework

Routing Overhead
Path Computation
 Path Signaling
Simulation Results
 Evaluation and Experimentation
 Simulation Parameters
 Comparative Results


Jan 13, 2006
Lahore University of Management Sciences
10
Protection Routing Framework

Tasks related to backup paths in a protection
routing framework:



Objectives of protection routing framework




Backup path computation
Backup path signaling
Incur scalable routing overhead
Find optimal backup paths
Maximize bandwidth sharing
NPP++ framework achieves all of above
Jan 13, 2006
Lahore University of Management Sciences
11
1.Scalable routing overhead
More Information propagated  More potential for BW sharing

Aggregate Information Scenario (AIS)




Fij: Bandwidth reserved on link (i, j) for all
primary LSPs
Gij: Bandwidth reserved on link (i, j) for all
backup LSPs
Rij: Bandwidth remaining on link (i, j)
Extended NPP (NPP++) relies on AIS

Low routing overhead
Jan 13, 2006
Lahore University of Management Sciences
12
2.Optimal backup paths


Backup path computation is moved to a node that has maximal
information about the activation set of protected element
Node that computes backup paths maintains two local maps:
 BFTLIM


PFTLIM


How much backup bandwidth will fall on a given link (u,v) if this
element fails
How much primary bandwidth will be available on a given link (u,v)
if this element fails
FTLIMs keep historical information about bandwidth
reserved for protecting an element
 Leads to the computation of backup paths that are optimal
Jan 13, 2006
Lahore University of Management Sciences
13
Path Computation in NPP++
The backup paths protecting
against the failure of R2 cannot
share bandwidth on any link.
R
1
R2 Contains:
a) BFTLIM
b) PFTLIM
But such backup paths
may share bandwidth with
primary paths originating
or terminating at R2.
R
5
R
2
R
3
R
4
Path computation is shifted to R2 because…
Only R2 has full knowledge of its own Activation set
Jan 13, 2006
Lahore University of Management Sciences
14
3.Maximum Bandwidth Sharing


Optimal path is signaled with requirements for
FULL bandwidth
All nodes (along the backup path) maintain two
local data structures:



BLTFIM
 How much backup bandwidth will fall on this link if a
given element fails
PLTFIM
 How much primary bandwidth will be released on this
link if a given element fails
LTFIMs help nodes reserve only what is needed

Leading to maximum sharing along backup paths
Jan 13, 2006
Lahore University of Management Sciences
15
NPP++ Summary
Protecting R2
(1) Advertise aggregate link usage information only
R
4
R
1
FTLIMs
LTFIMs
LTFIMs
R
2
FTLIMs
R
3
FTLIMs
LTFIMs
(2) Path computation is shifted to special nodes
Results:
Primary Path
Backup Path
Jan 13, 2006
•Path
computation
optimal
(3) Nodes
in primaryispath
maintain “local data
structures”
•Bandwidth called
sharingBFTLIM/PFTLIM
on backup paths is maximum.
(4)
Nodes in backup
paths maintain
“local data
•Advertisement
overhead
is minimum
structures” called BLTFIM/PLTFIM
Lahore University of Management Sciences
16
Outline

Background
 Network Services and QoS Requirements
 Protection Routing in MPLS
 Backup Bandwidth Sharing


Sharing with Primary Paths
NPP++ Protection Routing Framework

Routing Overhead
Path Computation
 Path Signaling
Simulation Results
 Evaluation and Experimentation
 Simulation Parameters
 Comparative Results


Jan 13, 2006
Lahore University of Management Sciences
17
Evaluation & Experimentation

Traffic generation


Rejected requests experiments




Used existing traffic models
Generate a set of LSP requests
Measure the number of rejected requests
Simulate on various topologies
Scalability of local state information

How do the average number of entries in locally
stored maps grow with the number of requests
Jan 13, 2006
Lahore University of Management Sciences
18
Simulation Parameters


Simulations performed on two networks
Network 1:



Network 2:

20-node homogenous topology (metros in the U.S.)
Each link with capacity 120 units

Ingress/Egress pairs chosen randomly




15-node heterogeneous topology
Core links with capacity 480 units, other links 120 units
LSP requests arrive one-by-one
Bandwidth demand for each request is uniformly
distributed between 1 and 6
100 experiments with different traffic matrices
Jan 13, 2006
Lahore University of Management Sciences
19
Comparative Results: Network 1
Jan 13, 2006
Lahore University of Management Sciences
20
Comparative Results: Network 2
Jan 13, 2006
Lahore University of Management Sciences
21
Local Storage: Network 1
Jan 13, 2006
Lahore University of Management Sciences
22
Local Storage: Network 2
Jan 13, 2006
Lahore University of Management Sciences
23
Conclusions: NPP++

Optimal path computation

Maximum sharing along computed path

Scalable routing overhead


Practically feasible
15% – 40% improvement over existing
protection schemes
Jan 13, 2006
Lahore University of Management Sciences
24
Last slide…
Thank you!
Questions?
Jan 13, 2006
Lahore University of Management Sciences
25