Transcript Overcomming Link/Router Failure In MPLS Networks

Overcomming Link/Router
Failure In MPLS Networks
Yuval Hava
Pini Halperin
Introduction
•
•
•
•
MPLS networks overview
MPLS in the use of path recovery
Methods of recovery
Results
MPLS – Terminology
• FEC – Forwarding Equivalence
Classes
• LER – Label Edge Router
• LSR – Label Switching Router
• LSP – Label Switching Path
• LDP – Label Distribution Protocol
IP
MPLS
Ethernet, Frame Relay,
ATM, PPP…
Physical Layer
MPLS – Terminology
MPLS
Network
MPLS
• Header Format
MPLS ‘Shim’ Headers (1-n)
n
•••
1
Network Layer Header
and Packet (eg. IP)
Layer 2 Header
(eg. PPP, 802.3)
4 Bytes
Label Stack
Entry Format
Label
|------------------------------ 20 -----------------------------|
Label:
Exp.:
S:
TTL:
Exp.
|---- 3 ----|
S
TTL
|- 1 -| |----------- 8 -----------|
Label Value, 20 bits (0-16 reserved)
Experimental / Class of Service, 3 bits
Bottom of Stack, 1 bit (1 = last entry in label stack)
Time to Live, 8 bits
MPLS header is inserted between layer 3 and layer 2 headers
MPLS – FEC
FEC - forward equivalence class
•
LER classifies incoming IP traffic, relating it to the appropriate label by the
FEC priority.
•
We establish routing paths (A…Z), and we call them forward equivalence
classes, or FECs.
•
The FEC “A” paths are the highest-quality paths, and the FEC “Z” paths are
the lowest-quality paths.
MPLS – FEC
LER
LSR
LSR
LER
LSP
IP1
IP1
IP2
IP1
#L1
IP1
#L2
IP1
#L3
IP2
#L1
IP2
#L2
IP2
#L3
Packets are destined for different address prefixes, but can be
mapped to common path
FEC - A subset of packets that are all treated the same way by a router
IP2
MPLS – LSR
• LSR – Label Switching Router
• When packets leave the LER, they are
destined for the LSR, then there examined
for the presence of labels.
• The LSR looks to its forwarding table.
• LIB (label information base), the LSR will
swap labels according to instructions in
LIB table.
MPLS – LSR Example
R1
X
A
B
R4
D
R3
None
20
Label Stack
R2
R5
Z
MPLS – LSR Example
R1
X
A
B
R4
D
R3
600
20
Label Stack
R2
R5
Z
MPLS – LSR Example
R1
X
A
B
R4
D
R3
600
Label Stack
R2
R5
Z
MPLS – LSP
•
•
•
LSP – Label Switching Path
MPLS domain a path is setup for a given packet to travel based on an FEC
Two options for route selection for a particular FEC :
– Hop by hop routing
– Explicit routing
•
Hop-by-Hop routing
– This method allows each LSR to independently choose the next hop for
each FEC. It is similar to that currently used in IP networks. The LSR
uses any available routing protocols like Open Shortest Path First
(OSPF).
MPLS – LSP
•
Explicit Routing (Source Routing) is a very powerful technique
– With pure datagram routing, overhead of carrying complete explicit route is
prohibitive
– MPLS allows explicit route to be carried only at the time the LSP is setup, and
not with each packet
– MPLS makes explicit routing practical
•
In an explicitly routed LSP
– LSP next hop is not chosen by the local node
– Selected by a single node, usually the ingress
•
The sequence of LSRs may be chosen by
– Configuration (e.g., by an operator or by a centralized server)
– Selected dynamically by Ingress or Egress LSR
•
MPLS explicit routing much more efficient than the alternative of IP source
routing
MPLS – LSP Example
LSR 5
LSR 1
LSR 6
Ingress
LSR 3
LSR 7
LSR 2
LSR 4
Consider the next parameters :
•LSR1 -> LSR7
•LSR5, LSR6 are underused
•LSR4 is overused
Egress
physical connection
hop by hop LSP
explicit routing LSP
MPLS
• Example of hop by hop path:
R1
R2
Packet P
• R1 analyzes P’s dest. And sets L1 to P
• L1 is being pushed into MPLS label stack in P’s header
• L1 represents LSP <R1,R2,R3,R4>
R3
R4
MPLS
• Example of hop by hop path:
R1
R3
R2
R21
R22
• R2 determines that P must pass through green tunnel
• R2 pushes a new label: L2
• During tunneling through R2, R21, R22, R23, R3, stack has depth 2
• L2 represents LSP <R2, R21, R22, R23, R3>
R23
R4
MPLS
• Example of hop by hop path:
R1
R3
R2
R21
R22
R23
• R3 finds out it is the final hop of L2 LSP and pops L2 from the stack
• R3 discovers L1 on top of the stack and forwards P to the next hop for L1 LSP: R4
R4
MPLS
• Why use MPLS ?
– IP-based forwarding is too slow for large traffic loads.
In MPLS, the lookup requires only one access to the
forwarding table
– Scalability: Label switching allowing large number of
IP addresses with one or few labels
– Route control
(exist in IP-based forwarding but is too messy)
MPLS
• With the needs of real-time, high priority,
and mission critical application services,
network reliability and survivability have
become important issues in the Internet
– Network failure is critical to these applications
– IP based recovery mechanism may take a long time
(10s of seconds) - may result in a large amount of
packet loss
– MPLS based protection: a protected LSP makes
traffic travel through it at the same service quality
regardless of any failures
MPLS – LSP Failure Recovery
• All methods pre-establish a backup path
– Quick recovery
• 2 common types of recovery:
– Global repair
• The ingress LSR establishes the backup path to
the whole LSP
– Local repair
• Each LSR along the path establishes the backup
path to the next hop
RSVP-TE
• RSVP defines a 'session' to be a data flow
with a particular destination and transportlayer protocol
• RSVP-TE – an extension to RSVP, defines
resource reservation for IP systems
• RFC 4090 efficiently uses RSVP-TE to
establish backup label-switched path
(LSP) tunnels for the local repair of LSP
tunnels
RSVP-TE – backup LSPs
• Meets the needs of real-time applications
• Traffic should be redirected onto backup LSP
tunnels in 10s of milliseconds
• Can be satisfied by computing and signaling
backup LSP tunnels in advance of failure and by
re-directing traffic as close to the failure point as
possible
• The time for redirection includes no path
computation and no signaling delays, including
delays to propagate failure notification between
label-switched routers (LSRs).
RSVP-TE – backup LSPs
• One-to-one backup
Protected LSP: [R1-R2-R3-R4-R5]
R1's Backup: [R1-R6-R7-R8-R3]
R2's Backup: [R2-R7-R8-R4]
R3's Backup: [R3-R8-R9-R5]
R4's Backup: [R4-R9-R5]
•
•
•
•
R2
R1
R6
R4
R3
R7
R8
R5
R9
Detour – partial one-to-one backup LSP
For instance, if the link [R2-R3] fails , R2 will switch traffic received from R1
onto the protected LSP along link [R2-R7], using the label received when R2
created the detour. When R4 receives traffic with the label provided for R2's
detour, R4 will switch that traffic onto link [R4-R5], using the label received
from R5 for the protected LSP.
At no point does the depth of the label stack increase as a result of the detour.
While R2 is using its detour, traffic will take the path [R1-R2-R7-R8-R4-R5]
For N nodes, there could be as many as (N - 1) detours
RSVP-TE – backup LSPs
R8
• Facility backup
Protected LSP 1: [R1-R2-R3-R4-R5]
Protected LSP 2: [R8-R2-R3-R4]
Protected LSP 3: [R2-R3-R4-R9]
Bypass LSP Tunnel: [R2-R6-R7-R4]
•
•
•
•
R1
R2
R4
R3
R6
R7
R5
R9
For instance, if link [R2-R3] fails , R2 will switch onto link [R2-R6]. The label
will be switched for one which will be understood by R4 to indicate the
protected LSP, and the bypass tunnel's label will then be pushed onto the
label-stack of the redirected packets.
R4 will pop the bypass tunnel's label and examine the label underneath to
determine the protected LSP that the packet is to follow.
When R2 is using the bypass tunnel for protected LSP 1, the traffic takes
the path [R1-R2-R6-R7-R4-R5]; the bypass tunnel is the connection
between R2 and R4.
There could be as many as (N-1) bypass tunnels to fully protect an LSP that
traverses N nodes
Pre-Qualify
• IETF’s recovery mechanisms have not considered
optimal backup path for the recovery of an LSP in the
occurrence of a network failure
• Pre-qualified recovery path – establishing an optimal
backup LSP during the working LSP setup time
– Has a drawback: as time goes by, the network status changes
– The pre-qualified recovery path may not be optimal at the time of
failure
Efficient Pre-Qualify
• During setup, each LSR calculates the pre-qualified
recovery path to the next hop
• Whenever each LSR receives routing update message
(and information of current network parameters), the
qualified recovery path is also updated immediately
• When a fault occurs, the LSR establishes the recovery
path using constraint-based LDP or sends FIS to LER
• If LER cannot establish a recovery path, it notifies to
network manager
Efficient Pre-Qualify
Simulation results:
Hundessa Fast rerouting MPLS
• Upgraded D.Haskin method for backwards LSP.
• Backwards LSP :
– When a failure is detected the traffic is sent backwards to the
ingress LSR using the pre-established LSP.
– From the ingress LSR the data will now sent through the
recovery path .
• Drawback in this method is the delay involved in detecting the first
packet plush the delay of the subsequent packets .
recovery path
Ingress
Egress
backwards path
Hundessa Fast rerouting MPLS
• Hundessa proposed a better way to overcome D.Haskin method
with respect to RTT delay and packet disorder .
• When a fault is detected by LSR :
– Each LSR on backward start storing incoming packets in local buffer
– Last packet before initiating storing is tagged to indentify way back
– Each LSR on the backward send back its stored packets when he
received its tagged packet
– We use one of the Exp field bits in MPLS header to avoid overheads
– Ingress LSR sent its stored packet with all the new packets from the
backwards LSR’s through the alternative LSP
Ingress
Egress
Hundessa Fast rerouting MPLS
• A simulation was made in a network simulator for MPLS called MNS
FRR with PBT
Fast ReRoute with Pre-establised Bypass Tunnels
• Establishes bypass tunnels rather than backup paths
– A tunnel back up all protected LSPs, not a particular one
• Max-Flow-Min-Cut is adopted to find the necessary links
through which all paths between LSRi and LSRj must pass
• To protect both link failure and node failure, bypass tunnels
are established around the next hop to the next-next hop
FRR with PBT
Fast ReRoute with Pre-establised Bypass Tunnels
•
Shortest augmenting path algorithm:
1.
2.
3.
4.
Set the residual bandwidth of every link as the link bandwidth
Identify the shortest path from one LSR to the other.
If the path does not exit, then end the algorithm.
Discover the minimum residual bandwidth R in the path, and
decrease the residual bandwidth by R for each link in the path.
If the residual bandwidth of a link is zero, then set this link to
be disconnected.
Store the path and go to step 2.
FRR with PBT
Fast ReRoute with Pre-establised Bypass Tunnels
• Each LSR establishes the bypass tunnels in the network
initial state.
• The bypass tunnels to the next-next hop are set up with
the shortest augmenting path algorithm
• By that, we establish the least amount of tunnels
between 2 LSRs
• PBT-D
– Disjoint bypass tunnel for every link
– Disjoint algorithm can reduce the searching time for
the shortest path
Reroute Methods comparison
The simulation topology
Reroute Methods comparison
Packet loss vs Transmission rates (bps)
Pre-qualify has more packet loss since it reroutes the packets after failure
Reroute Methods comparison
CRR – the number of packets received without link failure divided by
the number of packets received with link failure