Transcript IP Multicast Tutorial

ECE544: Communication Networks-II
Spring 2009
H. Liu
Lecture 9 (MPLS)
Includes teaching materials from D. Saha
MPLS: Multi-protocol Label Switching

Introduction



MPLS protocols


History and motivation
MPLS mechanisms
RSVP-TE/CR-LDP
MPLS applications

VPNSs, traffic engineering, protection &
restoration
2
Multiprotocol Lable Switching (MPLS)

MPLS: Combine some properties of virtual
circuits with flexibility & robustness of
datagrams





Relies on IP addresses and IP routing protocols
to set up the path
MPLS-enabled routers forwards packets by
examining a short, fixed-length lables
Labels have local scope, similar to VC
Layer 2.5 protocol
Support different link layer technologies (ATM,
Ethernet, PPP)
3
WHY MPLS ?

Ultra fast forwarding


IP Traffic Engineering


Constraint-based routing
Virtual Private Networks


Use switching instead of routing
Controllable tunneling mechanism
Protection and restoration
4
IP Forwarding Table
Dest
47.1
47.2
47.3
Dest
47.1
47.2
47.3
Out
1
2
3
Out
1
2
3
1
47.1.*.*
3
1
Dest
47.1
47.2
47.3
Out
1
2
3
2
3
2
1
47.2.*.*
47.3.*.* 3
2
5
Hop-by-Hop IP Forwarding
Dest
47.1
47.2
47.3
Dest
47.1
47.2
47.3
Out
1
2
3
1 47.1
1
Dest
47.1
47.2
47.3
Out
1
2
3
IP 47.1.1.1
2
IP 47.1.1.1
3
Out
1
2
3
2
IP 47.1.1.1
1
47.2
47.3 3
2
IP 47.1.1.1
6
Routing Lookup
Control CPU
Switch
fabric
I/F
I/F
10 Gbps
10 Gbps
Prefix
9.*.*.*
9.1.*.*
9.2.*.*
9.1.1.*
9.2.1.*
9.1.1.1
9.1.1.2
9.2.1.1
Next Hop
14.1.2.1
67.1.2.2
71.1.2.3
113.1.2.1
113.1.2.1
71.1.2.3
14.1.2.1
71.1.2.3
Interface
2
4
6
8
8
6
2
6
20M packets/sec


Longest prefix match is (was) expensive.
Label matching is much less expensive.
7
MPLS Label

ATM-encapsulated packets: VPI and VCI => label
GFC
VPI
VCI
PTI
CLP
HEC
DATA
Label
Frame-based packets (Ethernet, PPP): “Shim” header

Ethernet Header
Shim Header
Label (20 bits)



Stack (1 bit)
IP Payload
Ether Trailer
TTL(8 bits)
Label: local scope as VCI
Exp: to identify the class of service (ToS)
Stack bit: indicate whether to encapsulate another shim label header


Exp (3 bits)
IP Header
MPLS encapsulation is specified over various media types. For example, top labels
may use existing ATM format, lower label(s) use a new “shim” label header
TTL: time-to-live counter. Special processing rules are used to mimic IP TTL
semantics.
8
MPLS Labels
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.3 3
47.1
Mapping: 0.40
2
47.2
2
9
Label Switched Path
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
IP 47.1.1.1
1 47.1
Intf Dest Intf Label
In
Out Out
3
47.1 1
0.50
3
1
1
3
2
2
47.3 3
47.2
2
IP 47.1.1.1
If no label mapping, pass up to L3 and IP routing is used to forward packets
10
Forwarding Equivalence Classes (FEC)
LER
LSR
LSR
LER
LSP
IP1
IP1
IP2
IP1
#L1
IP1
#L2
IP1
#L3
IP2
#L1
IP2
#L2
IP2
#L3
IP2
Packets are destined for different address prefixes, but can be mapped to
the same FEC and follows a common path from the ingress to the egress

FEC = “A subset of packets that are all treated the same way by a router”




a MPLS label is associated with a FEC, FEC <-> label binding
The concept of FECs provides for a great deal of flexibility and scalability
In conventional routing, a packet is assigned to a FEC at each hop (i.e. L3
look-up)
in MPLS it is only done once at the network ingress


At the ingressof a MPLS network, a packet is classified and assigned a FEC/label
Packet forwarding is done according to the label in the MPLS network
11
MPLS Terminology





LDP: Label Distribution Protocol
LSP: Label Switched Path
FEC: Forwarding Equivalence Class
LSR: Label Switching Router
LER: Label Edge Router
12
Label Distribution Methods
Downstream Label Distribution
LSR1
LSR2
Label-FEC Binding
• LSR2 discovers a ‘next hop’ for a particular FEC
• LSR2 generates a label for the FEC and
communicates the binding to LSR1
Downstream-on-Demand Label Distribution
LSR1
LSR2
Request for Binding
Label-FEC Binding
• LSR1 recognizes LSR2 as its next-hop for an FEC
• LSR1 inserts the binding into its forwarding tables
• A request is made to LSR2 for a binding between
the FEC and a label
• If LSR2 is the next hop for the FEC, LSR1 can use
that label knowing that its meaning is understood
• If LSR2 recognizes the FEC and has a next hop for
it, it creates a binding and replies to LSR1
• Both LSRs then have a common understanding
Both methods are supported, even in the same network at the same time
13
Distribution Control
Next Hop
(for FEC)
Incoming
Label
Independent LSP Control
Definition
Comparison
• Each LSR makes independent decision on when to
generate labels and communicate them to upstream
peers
• Communicate label-FEC binding to peers once
next-hop has been recognized
• LSP is formed as incoming and outgoing labels are
spliced together
• Labels can be exchanged with less delay
• Does not depend on availability of egress node
• Granularity may not be consistent across the nodes
at the start
• May require separate loop detection/mitigation
method
Outgoing
Label
Ordered LSP Control
• Label-FEC binding is communicated to peers if:
- LSR is the ‘egress’ LSR to particular FEC
- label binding has been received from
upstream LSR
• LSP formation ‘flows’ from egress to ingress
• Requires more delay before packets can be
forwarded along the LSP
• Depends on availability of egress node
• Mechanism for consistent granularity and freedom
from loops
• Used for explicit routing and multicast
Both methods are supported in the standard and can be fully interoperable
14
Label Retention Methods
Conservative Label Retention
Liberal Label Retention
LSR2
Label Bindings
for LSR4
Label Bindings
for LSR4
LSR1
LSR3
LSR4’s Label
LSR3’s Label
LSR2’s Label
Valid
Next Hop
LSR4
• LSR maintains bindings received from LSRs
other than the valid next hop
• If the next-hop changes, it may begin using
these bindings immediately
• May allow more rapid adaptation to routing
changes
• Requires an LSR to maintain many more
labels
LSR2
LSR1
LSR3
LSR4’s Label
LSR3’s Label
LSR2’s Label
Valid
Next Hop
LSR4
• LSR only maintains bindings received from
valid next hop
• If the next-hop changes, binding must be
requested from new next hop
• Restricts adaptation to changes in routing
• Fewer labels must be maintained by LSR
Label Retention method trades off between label
capacity and speed of adaptation to routing changes
15
Label Distribution Protocols




Label Distribution Protocol (LDP)
Constraint-based Routing LDP (CR-LDP)
Extensions to RSVP
Extensions to BGP
16
LDP:Label Distribution Protocol
Label distribution ensures that adjacent routers have
a common view of FEC <-> label bindings
Routing Table:
Routing Table:
Addr-prefix
47.0.0.0/8
Addr-prefix
47.0.0.0/8
Next Hop
LSR2
Next Hop
LSR3
LSR1
IP Packet
LSR3
LSR2
47.80.55.3
Label Information Base:
Label-In FEC Label-Out
XX
47.0.0.0/8
17
Step 3: LSR inserts label
value into forwarding base
For 47.0.0.0/8
use label ‘17’
Label Information Base:
Label-In FEC Label-Out
17
47.0.0.0/8
XX
Step 2: LSR communicates
binding to adjacent LSR
Step 1: LSR creates binding
between FEC and label value
Common understanding of which FEC the label is referring to!
17
LDP: Basic Characteristics


Provides LSR discovery mechanisms to enable LSR peers to
find each other and establish communication
Defines four classes of messages






DISCOVERY: deals with finding neighboring LSRs
ADJACENCY: deals with initialization, keep alive, and shutdown of sessions
LABEL ADVERTISEMENT: deals with label binding advertisements, request,
withdrawal, and release
NOTIFICATION: deals with advisory information and signal error
information
Runs over TCP for reliable delivery of messages, except for
discovery, which uses UDP and IP multicast
Designed to be extensible, using messages specified as TLVs
(type, value, length) encoded objects.
18
LDP Messages






INITIALIZATION
KEEPALIVE
LABEL MAPPING
LABEL WITHDRAWAL
LABEL RELEASE
LABEL REQUEST
19
Explicitly Routed (ER) LSP

Intf
In
3
3
Forward packets along “explicit routes”- pre-calculated routes that don’t
necessarily match those that normal IP routing protocols would select.
Dest
47.1.1
47.1
Intf
Out
2
1
Intf
In
3
Label
Out
1.33
0.50
Label
In
0.50
Dest Intf
Out
47.1 1
Label
Out
0.40
Intf
In
3
Label
In
0.40
Dest Intf
Out
47.1 1
IP 47.1.1.1
1 47.1
3
2
1
47.3 3
3
2
1
47.2
2
IP 47.1.1.1
20
ER LSP - Advantages

Operator has routing flexibility



policy-based, QoS-based
Can use routes other than shortest path
Can compute routes based on
constraints in exactly the same manner
as ATM based on distributed topology
database.(traffic engineering)
21
ER LSP - discord!



Two signaling options proposed in the
standards: CR-LDP, RSVP extensions:
CR-LDP = LDP + Explicit Route
RSVP ext = Traditional RSVP + Explicit
Route +Scalability Extensions



RSVP-TE: RSVP traffic engineering
Market will probably have to resolve it
Survival of the fittest not such a bad thing.
22
MPLS and QoS in IP Network


Integrated Services

Assign a FEC/label to a flow

RSVP was extended to RSVP-TE to support traffic engineering
 RSVP was further extend to add MPLS support for label
distribution
Differentiated Services

LSRs don’t sort based on IP headers, hence DSCPs need to be
mapped to EXP field in MPLS shim header
 Exp field is only 3-bit wide – can support only 8 DSCPs/PHBs

Labels can be used if more than 8 PHBs need to be supported
 Assign different labels to different classes
 Some signaling is needed to specify the PHB

Same approach can be used for link layers which do not use Shim
headers, e.g. ATM
23
Traffic Engineering with RSVP
PATH
{Tspec}
PATH
{Tspec}
PATH
{Tspec}
Sender
RESV
{Rspec}
RESV
{Rspec}
RESV
{Rspec}
PATH
{Tspec}
RESV
{Rspec}
Receiver
24
Label Distribution with RSVP-TE
PATH
{Tspec}
PATH
{Tspec}
PATH
{Tspec}
Sender
RESV
{Rspec}
PATH
{Tspec}
RESV
{Rspec}
{Label = 10}
RESV
{Rspec}
{Label = 5}
PATH
{Tspec}
RESV
{Rspec}
25
MPLS Protection


End-to-end protection
Fast node and link reroute
26
MPLS Protection
End-to-end Path Protection
F
Primary LSP
E
A
D
B
C
Backup LSP
Backup and primary LSPs should be route diverse
27
MPLS Protection: Fast Reroute
Detour to avoid CD
Detour to avoid AB
LSR B
LSR A
LSR D
LSR C
Detour to avoid BC

LSR E
Detour to avoid DE
Detour around node or link failures


Detour to avoid link
DE
LSR F
Example LSP shown traverses (A, B, C, D, E, F)
Each detour avoids


Immediate downstream node & link towards it
Except for last detour: only avoids link DE
28
Detour Merging
Detour to avoid AB
Merged detour to
avoid AB and BC
Detour to avoid BC
LSR A


LSR B
LSR C
LSR F
LSR D
LSR E
Reduces state maintained
Improves resource utilization
29
MPLS Protection Types

1+1: Backup LSP established in advance, resources
dedicated, data simultaneously sent on both primary
and backup



Switchover performed only by egress LSR
Fastest, but most resource intensive
1:1 : Same as 1+1 with the difference that data is
not sent on the backup



Requires failure notification to the ingress LSR to start
transmitting on backup
Notification may be send to egress also
Resources in the backup may be used by other traffic

Low priority traffic (e.g., plain IP traffic), shared by other
backup paths
30
MPLS VPN: The Problem
Customer 1
Site 1
Provider Network
10.2/16
Customer 1
Site 2
10.1/16
10.2/16
Customer 2
Site 2
10.1/16
Customer 2
Site 1
10.3/16
Customer 2
Site 3
Customer 1
Site 3
10.3/16
31
MPLS VPN: The Model
Customer 1
Site 1
10.1/16
10.2/16
Customer 1
Site 2
Customer 1
Virtual Network
10.2/16
10.1/16
Customer 2
Site 2
Customer 2
Virtual Network
Customer 2
Site 1
10.3/16
Customer 2
Site 3
Customer 1
Site 3
10.3/16
MPLS is used to tunnel data across a network of MPLS-enabled routers
32
MPLS VPN: The Solution
MPLS LSP
Customer 1
Site 1
10.2/16
Customer 1
Site 2
VRF 1
10.1/16
VRF 1
10.2/16
VRF 2
Customer 2
Site 2
VRF 2
10.1/16
VRF 1
Customer 2
Site 1
VRF 2
MPLS LSP
10.3/16
Customer 2
Site 3
Customer 1
Site 3
10.3/16
33