Transcript Refinement on MPLS: An Application of Graceful Numbering to IP

Graceful Label Numbering
in
Optical MPLS Networks
Ibrahim C. Arkut
[email protected]
Refik C. Arkut
[email protected]
Nasir Ghani
[email protected]
What is MPLS?
Multi Protocol Label Switching
is a routing technique
that imitate connection
oriented forwarding
method in a connectionless
(IP) environment
OptiComm 2000, October 24, 2000, Dallas, Texas
Chart 2
What is MPLS? (cont.)
• Hop-by-hop or source routing
to establish labels - non-shortest paths
• Uses label native to the media
• Multi level label substitution transport
OptiComm 2000, October 24, 2000, Dallas, Texas
Chart 3
Why MPLS ?
• Performance and scalability
• Explicit routing and traffic engineering
– Constraint-based Routing / QoS
• Separation of control (routing) and
forwarding
• Virtual Private Networks
– Controllable tunneling mechanism
• Unified approach to routing functionality
OptiComm 2000, October 24, 2000, Dallas, Texas
Chart 4
Best of both Worlds
Packet
Forwarding
IP
HYBRID
MPLS
+IP
Circuit
Switching
ATM
• Flexibility and predictability
• Performance - complexity trade-off
OptiComm 2000, October 24, 2000, Dallas, Texas
Chart 5
Forwarding Equivalence Classes (FEC)
LER
(ingress)
IP1
LSR
LSR
LER
(egress)
IP1
IP1
#L1
IP1
#L2
IP1
#L3
IP2
#L1
IP2
#L2
IP2
#L3
IP2
IP2
LSP
Flow of IP packets
• over the same path
• treated in the same manner
• mapped to the same label
OptiComm 2000, October 24, 2000, Dallas, Texas
Chart 6
FEC / label binding mechanism
• Binding is done once at the ingress LER / OXC
• Currently based on destination IP address prefix
• Future mappings based on SP-defined policy
• In electronic MPLS domain
Label <---> FEC (packet associated)
• In photonic MPLS domain
Label <---> Wavelength ( channel associated)
OptiComm 2000, October 24, 2000, Dallas, Texas
Chart 7
MPLS Signaling Protocols
•
•
•
•
Hop-by-hop & Explicit
Label Distribution Protocol (LDP)
Constraint-based Routing LDP (CR-LDP)
Extensions to RSVP
OptiComm 2000, October 24, 2000, Dallas, Texas
Chart 8
Packet Forwarding over LSP(Label swapping)
Edge
Core
Edge
Core
Egress Label Switch
Ingress label switch
IP addr Out label
192.4/16
192.4.2.1
Layer 2
transport
5
Assign
Initial
Label
IP label Next hop
Core
5
Label Switch
Label Switch
In label Out label
In label Out label
5
9
Label
Swapping
9
9
2
2
2
21.9.1.1
Layer 2
Transport
Remove
label
192.4.2.1
Label
Swapping
Label-Switched Path
Label swapping is ‘simple’, but is it simple enough?
OptiComm 2000, October 24, 2000, Dallas, Texas
Chart 9
Matching the Speeds?
IP/MPLS-over-WDM
IP/MPLS
Electronic
Speed
Frame
Monitoring
Optical
Speed
Optical (Physical) Layer
For increased speed, the mechanism must be simpler!
OptiComm 2000, October 24, 2000, Dallas, Texas
Chart 10
Graceful Numbering of Trees
• It is a well-known labeling
problem in graphs and trees.
• Number the nodes of a graph G
with 1, 2,…, e so that induce
edge labels computed by
absolute node number
differences are all distinct.
• Notorious conjecture of RingelKotzig [1963] asserts that “all
trees are graceful”
9
7
6
10
4
7
3
14
8
6
2
13
1
12
1
13
5
2
14
8
9
15
11
4
3
12
11
10
5
Graceful numbering of a tree
OptiComm 2000, October 24, 2000, Dallas, Texas
Chart 11
MPLS unicast with graceful numbering
DESTINATION
4
2
7
5
6
1
5
2
4
3
3
6
1
SOURCE
OptiComm 2000, October 24, 2000, Dallas, Texas
Chart 12
MPLS+Graceful Numbering
Edge
Core
Ingress label switch
Egress Label Switch
IP addr Out label
192.4/16
192.4.2.1
Layer 2
transport
1
IP label Next hop
Core
3
Assign
Initial
Label
Edge
Core
3
Label Switch
Label Switch
In label Out label
In label Out label
3
2
2
2
1
Label
Swaping
Label
Swaping
4
2
L a b e l -S w i t c h e d P a t h
OptiComm 2000, October 24, 2000, Dallas, Texas
1
1
21.9.1.1
Layer 2
Transport
Remove
label
192.4.2.1
3
Chart 13
MPLS multicast caterpillar using
graceful numbering
3
9
8
12
4
10
11
1
SOURCE
2
SOURCE
N={1,2,3,4,5,6,7,8,9,10,11,12}
11
3
N={1,2,3,4,5,6,7,8,9,10,11,12}
10
7
9
11
3
8
11
4
10
6
4
11
9
1
SOURCE
2
N={1,2,3,4,5,6,7,8,9,10,11,12}
OptiComm 2000, October 24, 2000, Dallas, Texas
8
12
8
5
1
SOURCE
6
7
9
6
12
10
2
4
4
10
5
3
8
5
9
2
1
7
N={1,2,3,4,5,6,7,8,9,10,11,12}
Chart 14
Graceful numbering of paths and caterpillars (*)
are not complex and resembles label assignment in
PATH
MPLS
N
1
2
N-1
3
N-3
N-2
N-1
N-2
N-5
N-4
etc.
CATERPILLAR
backbone path
N-3
1
N-5
N-2
N-6
3
N-14
N-13
N-10
N-3
N-6
7
etc.
N-1
N-2
N-4
N-7
N-9
N-11
N-12
N-8
N
N-1
2
4
5
6
N-4
N-5
(*)I. Cahit and R. Cahit, “On Graceful Numbering of Spanning Trees”,
Info. Proc. Lett., 3(4), March 1975,
OptiComm 2000, October 24, 2000, Dallas, Texas
Chart 15
MPLS Roles
MPLS
SONET
Optical
Present
MPLS
Adaptation
Optical
Future
IP/MPLS:Service and addressing,
Quality of service, TE, Protection
Efficient logical
Sonet: Multiplexing, Protection
overlay over
Optical: Bandwidth
Sonet
IP/MPLS: Service and addressing
Quality of service, TE, Protection,
Multiplexing,
Efficient Peer
Optical: Protection, Multiplexing
model and
Bandwidth
transport
topology aware
OptiComm 2000, October 24, 2000, Dallas, Texas
Chart 16
One Control (MPLS) - End to End
VPI/VCI
/DLCI/
Label
MPLS Control Plane
Label
Lambda
OptiComm 2000, October 24, 2000, Dallas, Texas
Lambda
Label
VPI/VCI
/DLCI/
Label
Chart 17
Lambda-Labeling with Graceful Numbering
(IP-Over-WDM)
• Graceful Lambda
(Gl) Labeling in
Optical Core
Network
IP/MPLS network
(electronic)
”Gl - labeling"
Optical MPLS Core
I1
I6
M12
M8
Large bandwidth lambda
LSP's explicit routing
I2
M11
I5
M9
M10
I3
I4
Lambda-labeling approach: multiple MPLS network node types
OptiComm 2000, October 24, 2000, Dallas, Texas
Chart 18
Graceful Numbering of Two Light-paths
(without lambda conversion)
• IF the light-paths from
C to B and from A to
D arrive to node X
with the same label
but different
wavelengths
• THEN no need to
convert any
wavelength at node X
OptiComm 2000, October 24, 2000, Dallas, Texas
C
B
5
4
1
merging is
not possible
X
2
3
3
4
2
1
A
D
Chart 19
Graceful Numbering of Two Light-paths with
wavelength conversion
• IF the light-path from
C to B and from A to
D arrive to node X
with the same labels
and wavelengths
• THEN one of the
wavelength is to be
converted at node X
C
B
5
4
1
merging is
not possible
X
2
3
3
4
2
1
A
D
OptiComm 2000, October 24, 2000, Dallas, Texas
Chart 20
Summary
• Topology associated labeling
• Distinct labels per LSP or MC Caterpillar
• Label conflict resolution by central control
• Source controlled Graceful Number assignments
• Labels generation automatic and simple
• Efficient O(n) algorithms
• Minimum label-process time
• Distributed algorithm to assign Gl-labels
OptiComm 2000, October 24, 2000, Dallas, Texas
Chart 21