draft-ietf-mpls-arch-00.txt   draft-ietf-mpls-arch-01.txt 
Network Working Group Eric C. Rosen Network Working Group Eric C. Rosen
Internet Draft Cisco Systems, Inc. Internet Draft Cisco Systems, Inc.
Expiration Date: February 1998 Expiration Date: September 1998
Arun Viswanathan Arun Viswanathan
IBM Corp. Lucent Technologies
Ross Callon Ross Callon
Ascend Communications, Inc. IronBridge Networks, Inc.
August 1997 March 1998
A Proposed Architecture for MPLS Multiprotocol Label Switching Architecture
draft-ietf-mpls-arch-00.txt draft-ietf-mpls-arch-01.txt
Status of this Memo Status of this Memo
This document is an Internet-Draft. Internet-Drafts are working This document is an Internet-Draft. Internet-Drafts are working
documents of the Internet Engineering Task Force (IETF), its areas, documents of the Internet Engineering Task Force (IETF), its areas,
and its working groups. Note that other groups may also distribute and its working groups. Note that other groups may also distribute
working documents as Internet-Drafts. working documents as Internet-Drafts.
Internet-Drafts are draft documents valid for a maximum of six months Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress." material or to cite them other than as "work in progress."
To learn the current status of any Internet-Draft, please check the To view the entire list of current Internet-Drafts, please check
"1id-abstracts.txt" listing contained in the Internet-Drafts Shadow the "1id-abstracts.txt" listing contained in the Internet-Drafts
Directories on ftp.is.co.za (Africa), nic.nordu.net (Europe), Shadow Directories on ftp.is.co.za (Africa), ftp.nordu.net
munnari.oz.au (Pacific Rim), ds.internic.net (US East Coast), or (Northern Europe), ftp.nis.garr.it (Southern Europe), munnari.oz.au
ftp.isi.edu (US West Coast). (Pacific Rim), ftp.ietf.org (US East Coast), or ftp.isi.edu
(US West Coast).
Abstract Abstract
This internet draft contains a draft protocol architecture for This internet draft specifies the architecture for multiprotocol
multiprotocol label switching (MPLS). The proposed architecture is label switching (MPLS). The architecture is based on other label
based on other label switching approaches [2-11] as well as on the switching approaches [2-11] as well as on the MPLS Framework document
MPLS Framework document [1]. [1].
Table of Contents Table of Contents
1 Introduction to MPLS ............................... 3 1 Introduction to MPLS ............................... 4
1.1 Overview ........................................... 3 1.1 Overview ........................................... 4
1.2 Terminology ........................................ 5 1.2 Terminology ........................................ 6
1.3 Acronyms and Abbreviations ......................... 9 1.3 Acronyms and Abbreviations ......................... 9
1.4 Acknowledgments .................................... 10 1.4 Acknowledgments .................................... 10
2 Outline of Approach ................................ 10 2 Outline of Approach ................................ 11
2.1 Labels ............................................. 10 2.1 Labels ............................................. 11
2.2 Upstream and Downstream LSRs ....................... 11 2.2 Upstream and Downstream LSRs ....................... 12
2.3 Labeled Packet ..................................... 11 2.3 Labeled Packet ..................................... 12
2.4 Label Assignment and Distribution; Attributes ...... 11 2.4 Label Assignment and Distribution; Attributes ...... 12
2.5 Label Distribution Protocol (LDP) .................. 12 2.5 Label Distribution Protocol (LDP) .................. 13
2.6 The Label Stack .................................... 12 2.6 The Label Stack .................................... 13
2.7 The Next Hop Label Forwarding Entry (NHLFE) ........ 13 2.7 The Next Hop Label Forwarding Entry (NHLFE) ........ 14
2.8 Incoming Label Map (ILM) ........................... 13 2.8 Incoming Label Map (ILM) ........................... 14
2.9 Stream-to-NHLFE Map (STN) .......................... 13 2.9 Stream-to-NHLFE Map (STN) .......................... 15
2.10 Label Swapping ..................................... 14 2.10 Label Swapping ..................................... 15
2.11 Label Switched Path (LSP), LSP Ingress, LSP Egress . 14 2.11 Scope and Uniqueness of Labels ..................... 15
2.12 LSP Next Hop ....................................... 16 2.12 Label Switched Path (LSP), LSP Ingress, LSP Egress . 16
2.13 Route Selection .................................... 17 2.13 Penultimate Hop Popping ............................ 18
2.14 Time-to-Live (TTL) ................................. 18 2.14 LSP Next Hop ....................................... 19
2.15 Loop Control ....................................... 19 2.15 Route Selection .................................... 20
2.15.1 Loop Prevention .................................... 20 2.16 Time-to-Live (TTL) ................................. 21
2.15.2 Interworking of Loop Control Options ............... 22 2.17 Loop Control ....................................... 22
2.16 Merging and Non-Merging LSRs ....................... 23 2.17.1 Loop Prevention .................................... 23
2.16.1 Stream Merge ....................................... 24 2.17.2 Interworking of Loop Control Options ............... 25
2.16.2 Non-merging LSRs ................................... 24 2.18 Merging and Non-Merging LSRs ....................... 26
2.16.3 Labels for Merging and Non-Merging LSRs ............ 25 2.18.1 Stream Merge ....................................... 27
2.16.4 Merge over ATM ..................................... 26 2.18.2 Non-merging LSRs ................................... 27
2.16.4.1 Methods of Eliminating Cell Interleave ............. 26 2.18.3 Labels for Merging and Non-Merging LSRs ............ 28
2.16.4.2 Interoperation: VC Merge, VP Merge, and Non-Merge .. 26 2.18.4 Merge over ATM ..................................... 29
2.17 LSP Control: Egress versus Local ................... 27 2.18.4.1 Methods of Eliminating Cell Interleave ............. 29
2.18 Granularity ........................................ 29 2.18.4.2 Interoperation: VC Merge, VP Merge, and Non-Merge .. 29
2.19 Tunnels and Hierarchy .............................. 30 2.19 LSP Control: Egress versus Local ................... 30
2.19.1 Hop-by-Hop Routed Tunnel ........................... 30 2.20 Granularity ........................................ 32
2.19.2 Explicitly Routed Tunnel ........................... 30 2.21 Tunnels and Hierarchy .............................. 33
2.19.3 LSP Tunnels ........................................ 30 2.21.1 Hop-by-Hop Routed Tunnel ........................... 33
2.19.4 Hierarchy: LSP Tunnels within LSPs ................. 31 2.21.2 Explicitly Routed Tunnel ........................... 33
2.19.5 LDP Peering and Hierarchy .......................... 31 2.21.3 LSP Tunnels ........................................ 33
2.20 LDP Transport ...................................... 33 2.21.4 Hierarchy: LSP Tunnels within LSPs ................. 34
2.21 Label Encodings .................................... 33 2.21.5 LDP Peering and Hierarchy .......................... 34
2.21.1 MPLS-specific Hardware and/or Software ............. 33 2.22 LDP Transport ...................................... 36
2.21.2 ATM Switches as LSRs ............................... 34 2.23 Label Encodings .................................... 36
2.21.3 Interoperability among Encoding Techniques ......... 35 2.23.1 MPLS-specific Hardware and/or Software ............. 36
2.22 Multicast .......................................... 36 2.23.2 ATM Switches as LSRs ............................... 37
3 Some Applications of MPLS .......................... 36 2.23.3 Interoperability among Encoding Techniques ......... 38
3.1 MPLS and Hop by Hop Routed Traffic ................. 36 2.24 Multicast .......................................... 39
3.1.1 Labels for Address Prefixes ........................ 36 3 Some Applications of MPLS .......................... 39
3.1.2 Distributing Labels for Address Prefixes ........... 36 3.1 MPLS and Hop by Hop Routed Traffic ................. 39
3.1.2.1 LDP Peers for a Particular Address Prefix .......... 36 3.1.1 Labels for Address Prefixes ........................ 39
3.1.2.2 Distributing Labels ................................ 37 3.1.2 Distributing Labels for Address Prefixes ........... 39
3.1.3 Using the Hop by Hop path as the LSP ............... 38 3.1.2.1 LDP Peers for a Particular Address Prefix .......... 39
3.1.4 LSP Egress and LSP Proxy Egress .................... 38 3.1.2.2 Distributing Labels ................................ 40
3.1.5 The POP Label ...................................... 39 3.1.3 Using the Hop by Hop path as the LSP ............... 41
3.1.6 Option: Egress-Targeted Label Assignment ........... 40 3.1.4 LSP Egress and LSP Proxy Egress .................... 41
3.2 MPLS and Explicitly Routed LSPs .................... 41 3.1.5 The POP Label ...................................... 42
3.2.1 Explicitly Routed LSP Tunnels: Traffic Engineering . 42 3.1.6 Option: Egress-Targeted Label Assignment ........... 43
3.3 Label Stacks and Implicit Peering .................. 42 3.2 MPLS and Explicitly Routed LSPs .................... 44
3.4 MPLS and Multi-Path Routing ........................ 43 3.2.1 Explicitly Routed LSP Tunnels: Traffic Engineering . 44
3.5 LSPs may be Multipoint-to-Point Entities ........... 44 3.3 Label Stacks and Implicit Peering .................. 45
3.6 LSP Tunneling between BGP Border Routers ........... 44 3.4 MPLS and Multi-Path Routing ........................ 46
3.7 Other Uses of Hop-by-Hop Routed LSP Tunnels ........ 46 3.5 LSP Trees as Multipoint-to-Point Entities .......... 46
3.8 MPLS and Multicast ................................. 46 3.6 LSP Tunneling between BGP Border Routers ........... 47
4 LDP Procedures ..................................... 47 3.7 Other Uses of Hop-by-Hop Routed LSP Tunnels ........ 49
5 Security Considerations ............................ 47 3.8 MPLS and Multicast ................................. 49
6 Authors' Addresses ................................. 47 4 LDP Procedures for Hop-by-Hop Routed Traffic ....... 50
7 References ......................................... 47 4.1 The Procedures for Advertising and Using labels .... 50
Appendix A Why Egress Control is Better ....................... 48 4.1.1 Downstream LSR: Distribution Procedure ............. 50
Appendix B Why Local Control is Better ........................ 56 4.1.1.1 PushUnconditional .................................. 51
4.1.1.2 PushConditional .................................... 51
4.1.1.3 PulledUnconditional ................................ 52
4.1.1.4 PulledConditional .................................. 52
4.1.2 Upstream LSR: Request Procedure .................... 53
4.1.2.1 RequestNever ....................................... 53
4.1.2.2 RequestWhenNeeded .................................. 53
4.1.2.3 RequestOnRequest ................................... 53
4.1.3 Upstream LSR: NotAvailable Procedure ............... 54
4.1.3.1 RequestRetry ....................................... 54
4.1.3.2 RequestNoRetry ..................................... 54
4.1.4 Upstream LSR: Release Procedure .................... 54
4.1.4.1 ReleaseOnChange .................................... 54
4.1.4.2 NoReleaseOnChange .................................. 54
4.1.5 Upstream LSR: labelUse Procedure ................... 55
4.1.5.1 UseImmediate ....................................... 55
4.1.5.2 UseIfLoopFree ...................................... 55
4.1.5.3 UseIfLoopNotDetected ............................... 55
4.1.6 Downstream LSR: Withdraw Procedure ................. 56
4.2 MPLS Schemes: Supported Combinations of Procedures . 56
4.2.1 TTL-capable LSP Segments ........................... 57
4.2.2 Using ATM Switches as LSRs ......................... 57
4.2.2.1 Without Multipoint-to-point Capability ............. 58
4.2.2.2 With Multipoint-To-Point Capability ................ 58
4.2.3 Interoperability Considerations .................... 59
4.2.4 How to do Loop Prevention .......................... 60
4.2.5 How to do Loop Detection ........................... 60
4.2.6 Security Considerations ............................ 60
5 Authors' Addresses ................................. 60
6 References ......................................... 61
1. Introduction to MPLS 1. Introduction to MPLS
1.1. Overview 1.1. Overview
In connectionless network layer protocols, as a packet travels from In connectionless network layer protocols, as a packet travels from
one router hop to the next, an independent forwarding decision is one router hop to the next, an independent forwarding decision is
made at each hop. Each router analyzes the packet header, and runs a made at each hop. Each router runs a network layer routing
network layer routing algorithm. The next hop for a packet is chosen algorithm. As a packet travels through the network, each router
analyzes the packet header. The choice of next hop for a packet is
based on the header analysis and the result of running the routing based on the header analysis and the result of running the routing
algorithm. algorithm.
Packet headers contain considerably more information than is needed Packet headers contain considerably more information than is needed
simply to choose the next hop. Choosing the next hop can therefore be simply to choose the next hop. Choosing the next hop can therefore be
thought of as the composition of two functions. The first function thought of as the composition of two functions. The first function
partitions the entire packet forwarding space into "forwarding partitions the entire set of possible packets into a set of
equivalence classes (FECs)". The second maps these FECs to a next "Forwarding Equivalence Classes (FECs)". The second maps each FEC to
hop. Multiple network layer headers which get mapped into the same a next hop. Insofar as the forwarding decision is concerned,
FEC are indistinguishable, as far as the forwarding decision is different packets which get mapped into the same FEC are
concerned. The set of packets belonging to the same FEC, traveling indistinguishable. All packets which belong to a particular FEC and
from a common node, will follow the same path and be forwarded in the which travel from a particular node will follow the same path. Such
same manner (for example, by being placed in a common queue) towards a set of packets may be called a "stream".
the destination. This set of packets following the same path,
belonging to the same FEC (and therefore being forwarded in a common
manner) may be referred to as a "stream".
In IP forwarding, multiple packets are typically assigned to the same In conventional IP forwarding, a particular router will typically
Stream by a particular router if there is some address prefix X in consider two packets to be in the same stream if there is some
that router's routing tables such that X is the "longest match" for address prefix X in that router's routing tables such that X is the
each packet's destination address. "longest match" for each packet's destination address. As the packet
traverses the network, each hop in turn reexamines the packet and
assigns it to a stream.
In MPLS, the mapping from packet headers to stream is performed just In MPLS, the assignment of a particular packet to a particular stream
once, as the packet enters the network. The stream to which the is done just once, as the packet enters the network. The stream to
packet is assigned is encoded with a short fixed length value known which the packet is assigned is encoded with a short fixed length
as a "label". When a packet is forwarded to its next hop, the label value known as a "label". When a packet is forwarded to its next
is sent along with it; that is, the packets are "labeled". hop, the label is sent along with it; that is, the packets are
"labeled".
At subsequent hops, there is no further analysis of the network layer At subsequent hops, there is no further analysis of the packet's
header. Rather, the label is used as an index into a table which network layer header. Rather, the label is used as an index into a
specifies the next hop, and a new label. The old label is replaced table which specifies the next hop, and a new label. The old label
with the new label, and the packet is forwarded to its next hop. This is replaced with the new label, and the packet is forwarded to its
eliminates the need to perform a longest match computation for each next hop. If assignment to a stream is based on a "longest match",
packet at each hop; the computation can be performed just once. this eliminates the need to perform a longest match computation for
each packet at each hop; the computation can be performed just once.
Some routers analyze a packet's network layer header not merely to Some routers analyze a packet's network layer header not merely to
choose the packet's next hop, but also to determine a packet's choose the packet's next hop, but also to determine a packet's
"precedence" or "class of service", in order to apply different "precedence" or "class of service", in order to apply different
discard thresholds or scheduling disciplines to different packets. In discard thresholds or scheduling disciplines to different packets.
MPLS, this can also be inferred from the label, so that no further MPLS allows the precedence or class of service to be inferred from
header analysis is needed. the label, so that no further header analysis is needed; in some
cases MPLS provides a way to explicitly encode a class of service in
the "label header".
The fact that a packet is assigned to a Stream just once, rather than The fact that a packet is assigned to a stream just once, rather than
at every hop, allows the use of sophisticated forwarding paradigms. at every hop, allows the use of sophisticated forwarding paradigms.
A packet that enters the network at a particular router can be A packet that enters the network at a particular router can be
labeled differently than the same packet entering the network at a labeled differently than the same packet entering the network at a
different router, and as a result forwarding decisions that depend on different router, and as a result forwarding decisions that depend on
the ingress point ("policy routing") can be easily made. In fact, the ingress point ("policy routing") can be easily made. In fact,
the policy used to assign a packet to a Stream need not have only the the policy used to assign a packet to a stream need not have only the
network layer header as input; it may use arbitrary information about network layer header as input; it may use arbitrary information about
the packet, and/or arbitrary policy information as input. Since this the packet, and/or arbitrary policy information as input. Since this
decouples forwarding from routing, it allows one to use MPLS to decouples forwarding from routing, it allows one to use MPLS to
support a large variety of routing policies that are difficult or support a large variety of routing policies that are difficult or
impossible to support with just conventional network layer impossible to support with just conventional network layer
forwarding. forwarding.
Similarly, MPLS facilitates the use of explicit routing, without Similarly, MPLS facilitates the use of explicit routing, without
requiring that each IP packet carry the explicit route. Explicit requiring that each IP packet carry the explicit route. Explicit
routes may be useful to support policy routing and traffic routes may be useful to support policy routing and traffic
skipping to change at page 9, line 15 skipping to change at page 9, line 50
1.3. Acronyms and Abbreviations 1.3. Acronyms and Abbreviations
ATM Asynchronous Transfer Mode ATM Asynchronous Transfer Mode
BGP Border Gateway Protocol BGP Border Gateway Protocol
DLCI Data Link Circuit Identifier DLCI Data Link Circuit Identifier
FEC Forwarding Equivalence Class FEC Forwarding Equivalence Class
STN Stream to NHLFE Map STN stream to NHLFE Map
IGP Interior Gateway Protocol IGP Interior Gateway Protocol
ILM Incoming Label Map ILM Incoming Label Map
IP Internet Protocol IP Internet Protocol
LIB Label Information Base LIB Label Information Base
LDP Label Distribution Protocol LDP Label Distribution Protocol
skipping to change at page 10, line 20 skipping to change at page 11, line 12
Paul Doolan, Nancy Feldman, Yakov Rekhter, Vijay Srinivasan, and Paul Doolan, Nancy Feldman, Yakov Rekhter, Vijay Srinivasan, and
George Swallow for their inputs and ideas. George Swallow for their inputs and ideas.
2. Outline of Approach 2. Outline of Approach
In this section, we introduce some of the basic concepts of MPLS and In this section, we introduce some of the basic concepts of MPLS and
describe the general approach to be used. describe the general approach to be used.
2.1. Labels 2.1. Labels
A label is a short fixed length locally significant identifier which A label is a short, fixed length, locally significant identifier
is used to identify a stream. The label is based on the stream or which is used to identify a stream. The label is based on the stream
forwarding equivalence class that a packet is assigned to. The label or Forwarding Equivalence Class that a packet is assigned to. The
does not directly encode the network layer address, and is based on label does not directly encode the network layer address. The choice
the network layer address only to the extent that the forwarding of label depends on the network layer address only to the extent that
equivalence class is based on the address. the Forwarding Equivalence Class depends on that address.
If Ru and Rd are neighboring LSRs, they may agree to use label L to If Ru and Rd are LSRs, and Ru transmits a packet to Rd, they may
represent Stream S for packets which are sent from Ru to Rd. That agree to use label L to represent stream S for packets which are sent
is, they can agree to a "mapping" between label L and Stream S for from Ru to Rd. That is, they can agree to a "mapping" between label
packets moving from Ru to Rd. As a result of such an agreement, L L and stream S for packets moving from Ru to Rd. As a result of such
becomes Ru's "outgoing label" corresponding to Stream S for such an agreement, L becomes Ru's "outgoing label" corresponding to stream
packets; L becomes Rd's "incoming label" corresponding to Stream S S for such packets; L becomes Rd's "incoming label" corresponding to
for such packets. stream S for such packets.
Note that L does not necessarily correspond to Stream S for any Note that L does not necessarily correspond to stream S for any
packets other than those which are being sent from Ru to Rd. Also, L packets other than those which are being sent from Ru to Rd. Also, L
is not an inherently meaningful value and does not have any network- is not an inherently meaningful value and does not have any network-
wide value; the particular value assigned to L gets its meaning wide value; the particular value assigned to L gets its meaning
solely from the agreement between Ru and Rd. solely from the agreement between Ru and Rd.
Sometimes it may be difficult or even impossible for Rd to tell that Sometimes it may be difficult or even impossible for Rd to tell, of
an arriving packet carrying label L comes from Ru, rather than from an arriving packet carrying label L, that the label L was placed in
some other LSR. In such cases, Rd must make sure that the mapping the packet by Ru, rather than by some other LSR. (This will
from label to FEC is one-to-one. That is, in such cases, Rd must not typically be the case when Ru and Rd are not direct neighbors.) In
agree with Ru1 to use L for one purpose, while also agreeing with such cases, Rd must make sure that the mapping from label to FEC is
some other LSR Ru2 to use L for a different purpose. one-to-one. That is, in such cases, Rd must not agree with Ru1 to
use L for one purpose, while also agreeing with some other LSR Ru2 to
The scope of labels could be unique per interface, or unique per MPLS use L for a different purpose.
node, or unique in a network. If labels are unique within a network,
no label swapping needs to be performed in the MPLS nodes in that
domain. The packets are just label forwarded and not label swapped.
The possible use of labels with network-wide scope is FFS.
2.2. Upstream and Downstream LSRs 2.2. Upstream and Downstream LSRs
Suppose Ru and Rd have agreed to map label L to Stream S, for packets Suppose Ru and Rd have agreed to map label L to stream S, for packets
sent from Ru to Rd. Then with respect to this mapping, Ru is the sent from Ru to Rd. Then with respect to this mapping, Ru is the
"upstream LSR", and Rd is the "downstream LSR". "upstream LSR", and Rd is the "downstream LSR".
The notion of upstream and downstream relate to agreements between The notion of upstream and downstream relate to agreements between
nodes of the label values to be assigned for packets belonging to a nodes of the label values to be assigned for packets belonging to a
particular Stream that might be traveling from an upstream node to a particular stream that might be traveling from an upstream node to a
downstream node. This is independent of whether the routing protocol downstream node. This is independent of whether the routing protocol
actually will cause any packets to be transmitted in that particular actually will cause any packets to be transmitted in that particular
direction. Thus, Rd is the downstream LSR for a particular mapping direction. Thus, Rd is the downstream LSR for a particular mapping
for label L if it recognizes L-labeled packets from Ru as being in for label L if it recognizes L-labeled packets from Ru as being in
Stream S. This may be true even if routing does not actually forward stream S. This may be true even if routing does not actually forward
packets for Stream S between nodes Rd and Ru, or if routing has made packets for stream S between nodes Rd and Ru, or if routing has made
Ru downstream of Rd along the path which is actually used for packets Ru downstream of Rd along the path which is actually used for packets
in Stream S. in stream S.
2.3. Labeled Packet 2.3. Labeled Packet
A "labeled packet" is a packet into which a label has been encoded. A "labeled packet" is a packet into which a label has been encoded.
The encoding can be done by means of an encapsulation which exists The encoding can be done by means of an encapsulation which exists
specifically for this purpose, or by placing the label in an specifically for this purpose, or by placing the label in an
available location in either of the data link or network layer available location in either of the data link or network layer
headers. Of course, the encoding technique must be agreed to by the headers. Of course, the encoding technique must be agreed to by the
entity which encodes the label and the entity which decodes the entity which encodes the label and the entity which decodes the
label. label.
2.4. Label Assignment and Distribution; Attributes 2.4. Label Assignment and Distribution; Attributes
For unicast traffic in the MPLS architecture, the decision to bind a For unicast traffic in the MPLS architecture, the decision to bind a
particular label L to a particular Stream S is made by the LSR which particular label L to a particular stream S is made by the LSR which
is downstream with respect to that mapping. The downstream LSR then is downstream with respect to that mapping. The downstream LSR then
informs the upstream LSR of the mapping. Thus labels are informs the upstream LSR of the mapping. Thus labels are
"downstream-assigned", and are "distributed upstream". "downstream-assigned", and are "distributed upstream".
A particular mapping of label L to Stream S, distributed by Rd to Ru, A particular mapping of label L to stream S, distributed by Rd to Ru,
may have associated "attributes". If Ru, acting as a downstream LSR, may have associated "attributes". If Ru, acting as a downstream LSR,
also distributes a mapping of a label to Stream S, then under certain also distributes a mapping of a label to stream S, then under certain
conditions, it may be required to also distribute the corresponding conditions, it may be required to also distribute the corresponding
attribute that it received from Rd. attribute that it received from Rd.
2.5. Label Distribution Protocol (LDP) 2.5. Label Distribution Protocol (LDP)
A Label Distribution Protocol (LDP) is a set of procedures by which A Label Distribution Protocol (LDP) is a set of procedures by which
one LSR informs another of the label/Stream mappings it has made. one LSR informs another of the label/Stream mappings it has made.
Two LSRs which use an LDP to exchange label/Stream mapping Two LSRs which use an LDP to exchange label/Stream mapping
information are known as "LDP Peers" with respect to the mapping information are known as "LDP Peers" with respect to the mapping
information they exchange; we will speak of there being an "LDP information they exchange; we will speak of there being an "LDP
skipping to change at page 12, line 29 skipping to change at page 13, line 27
The LDP also encompasses any negotiations in which two LDP Peers need The LDP also encompasses any negotiations in which two LDP Peers need
to engage in order to learn of each other's MPLS capabilities. to engage in order to learn of each other's MPLS capabilities.
2.6. The Label Stack 2.6. The Label Stack
So far, we have spoken as if a labeled packet carries only a single So far, we have spoken as if a labeled packet carries only a single
label. As we shall see, it is useful to have a more general model in label. As we shall see, it is useful to have a more general model in
which a labeled packet carries a number of labels, organized as a which a labeled packet carries a number of labels, organized as a
last-in, first-out stack. We refer to this as a "label stack". last-in, first-out stack. We refer to this as a "label stack".
At a particular LSR, the decision as to how to forward a labeled IN MPLS, EVERY FORWARDING DECISION IS BASED EXCLUSIVELY ON THE LABEL
packet is always based exclusively on the label at the top of the AT THE TOP OF THE STACK.
stack.
Although, as we shall see, MPLS supports a hierarchy, the processing
of a labeled packet is completely independent of the level of
hierarchy. The processing is always based on the top label, without
regard for the possibility that some number of other labels may have
been "above it" in the past, or that some number of other labels may
be below it at present.
An unlabeled packet can be thought of as a packet whose label stack An unlabeled packet can be thought of as a packet whose label stack
is empty (i.e., whose label stack has depth 0). is empty (i.e., whose label stack has depth 0).
If a packet's label stack is of depth m, we refer to the label at the If a packet's label stack is of depth m, we refer to the label at the
bottom of the stack as the level 1 label, to the label above it (if bottom of the stack as the level 1 label, to the label above it (if
such exists) as the level 2 label, and to the label at the top of the such exists) as the level 2 label, and to the label at the top of the
stack as the level m label. stack as the level m label.
The utility of the label stack will become clear when we introduce The utility of the label stack will become clear when we introduce
the notion of LSP Tunnel and the MPLS Hierarchy (sections 2.19.3 and the notion of LSP Tunnel and the MPLS Hierarchy (sections 2.21.3 and
2.19.4). 2.21.4).
2.7. The Next Hop Label Forwarding Entry (NHLFE) 2.7. The Next Hop Label Forwarding Entry (NHLFE)
The "Next Hop Label Forwarding Entry" (NHLFE) is used when forwarding The "Next Hop Label Forwarding Entry" (NHLFE) is used when forwarding
a labeled packet. It contains the following information: a labeled packet. It contains the following information:
1. the packet's next hop 1. the packet's next hop
2. the data link encapsulation to use when transmitting the packet 2. the data link encapsulation to use when transmitting the packet
skipping to change at page 13, line 29 skipping to change at page 14, line 29
a) replace the label at the top of the label stack with a a) replace the label at the top of the label stack with a
specified new label specified new label
b) pop the label stack b) pop the label stack
c) replace the label at the top of the label stack with a c) replace the label at the top of the label stack with a
specified new label, and then push one or more specified specified new label, and then push one or more specified
new labels onto the label stack. new labels onto the label stack.
Note that at a given LSR, the packet's "next hop" might be that LSR Note that at a given LSR, the packet's "next hop" might be that LSR
itself. In this case, the LSR would need to pop the top level label itself. In this case, the LSR would need to pop the top level label,
and examine and operate on the encapsulated packet. This may be a and then "forward" the resulting packet to itself. It would then
lower level label, or may be the native IP packet. This implies that make another forwarding decision, based on what remains after the
in some cases the LSR may need to operate on the IP header in order label stacked is popped. This may still be a labeled packet, or it
to forward the packet. If the packet's "next hop" is the current LSR, may be the native IP packet.
then the label stack operation MUST be to "pop the stack".
This implies that in some cases the LSR may need to operate on the IP
header in order to forward the packet.
If the packet's "next hop" is the current LSR, then the label stack
operation MUST be to "pop the stack".
2.8. Incoming Label Map (ILM) 2.8. Incoming Label Map (ILM)
The "Incoming Label Map" (ILM) is a mapping from incoming labels to The "Incoming Label Map" (ILM) is a mapping from incoming labels to
NHLFEs. It is used when forwarding packets that arrive as labeled NHLFEs. It is used when forwarding packets that arrive as labeled
packets. packets.
2.9. Stream-to-NHLFE Map (STN) 2.9. Stream-to-NHLFE Map (STN)
The "Stream-to-NHLFE" (STN) is a mapping from stream to NHLFEs. It is The "Stream-to-NHLFE" (STN) is a mapping from stream to NHLFEs. It is
skipping to change at page 14, line 18 skipping to change at page 15, line 24
packet. packet.
In order to forward a labeled packet, a LSR examines the label at the In order to forward a labeled packet, a LSR examines the label at the
top of the label stack. It uses the ILM to map this label to an top of the label stack. It uses the ILM to map this label to an
NHLFE. Using the information in the NHLFE, it determines where to NHLFE. Using the information in the NHLFE, it determines where to
forward the packet, and performs an operation on the packet's label forward the packet, and performs an operation on the packet's label
stack. It then encodes the new label stack into the packet, and stack. It then encodes the new label stack into the packet, and
forwards the result. forwards the result.
In order to forward an unlabeled packet, a LSR analyzes the network In order to forward an unlabeled packet, a LSR analyzes the network
layer header, to determine the packet's Stream. It then uses the FTN layer header, to determine the packet's stream. It then uses the STN
to map this to an NHLFE. Using the information in the NHLFE, it to map this to an NHLFE. Using the information in the NHLFE, it
determines where to forward the packet, and performs an operation on determines where to forward the packet, and performs an operation on
the packet's label stack. (Popping the label stack would, of course, the packet's label stack. (Popping the label stack would, of course,
be illegal in this case.) It then encodes the new label stack into be illegal in this case.) It then encodes the new label stack into
the packet, and forwards the result. the packet, and forwards the result.
It is important to note that when label swapping is in use, the next IT IS IMPORTANT TO NOTE THAT WHEN LABEL SWAPPING IS IN USE, THE NEXT
hop is always taken from the NHLFE; this may in some cases be HOP IS ALWAYS TAKEN FROM THE NHLFE; THIS MAY IN SOME CASES BE
different from what the next hop would be if MPLS were not in use. DIFFERENT FROM WHAT THE NEXT HOP WOULD BE IF MPLS WERE NOT IN USE.
2.11. Label Switched Path (LSP), LSP Ingress, LSP Egress 2.11. Scope and Uniqueness of Labels
A given LSR Rd may map label L1 to stream S, and distribute that
mapping to LDP peer Ru1. Rd may also map label L2 to stream S, and
distribute that mapping to LDP peer Ru2. Whether or not L1 == L2 is
not determined by the architecture; this is a local matter.
A given LSR Rd may map label L to stream S1, and distribute that
mapping to LDP peer Ru1. Rd may also map label L to stream S2, and
distribute that mapping to LDP peer Ru2. IF (AND ONLY IF) RD CAN
TELL, WHEN IT RECEIVES A PACKET WHOSE TOP LABEL IS L, WHETHER THE
LABEL WAS PUT THERE BY RU1 OR BY RU2, THEN THE ARCHITECTURE DOES NOT
REQUIRE THAT S1 == S2. In general, Rd can only tell whether it was
Ru1 or Ru2 that put the particular label value L at the top of the
label stack if the following conditions hold:
- Ru1 and Ru2 are the only LDP peers to which Rd distributed a
mapping of label value L, and
- Ru1 and Ru2 are each directly connected to Rd via a point-to-
point interface.
When these conditions hold, an LSR may use labels that have "per
interface" scope, i.e., which are only unique per interface. When
these conditions do not hold, the labels must be unique over the LSR
which has assigned them.
If a particular LSR Rd is attached to a particular LSR Ru over two
point-to-point interfaces, then Rd may distribute to Rd a mapping of
label L to stream S1, as well as a mapping of label L to stream S2,
S1 != S2, if and only if each mapping is valid only for packets which
Ru sends to Rd over a particular one of the interfaces. In all other
cases, Rd MUST NOT distribute to Ru mappings of the same label value
to two different streams.
This prohibition holds even if the mappings are regarded as being at
different "levels of hierarchy". In MPLS, there is no notion of
having a different label space for different levels of the hierarchy.
2.12. Label Switched Path (LSP), LSP Ingress, LSP Egress
A "Label Switched Path (LSP) of level m" for a particular packet P is A "Label Switched Path (LSP) of level m" for a particular packet P is
a sequence of LSRs, a sequence of routers,
<R1, ..., Rn> <R1, ..., Rn>
with the following properties: with the following properties:
1. R1, the "LSP Ingress", pushes a label onto P's label stack, 1. R1, the "LSP Ingress", is an LSR which pushes a label onto P's
resulting in a label stack of depth m; label stack, resulting in a label stack of depth m;
2. For all i, 1<i<n, P has a label stack of depth m when received 2. For all i, 1<i<n, P has a label stack of depth m when received
by Ri; by LSR Ri;
3. At no time during P's transit from R1 to R[n-1] does its label 3. At no time during P's transit from R1 to R[n-1] does its label
stack ever have a depth of less than m; stack ever have a depth of less than m;
4. For all i, 1<i<n: Ri transmits P to R[i+1] by means of MPLS, 4. For all i, 1<i<n: Ri transmits P to R[i+1] by means of MPLS,
i.e., by using the label at the top of the label stack (the i.e., by using the label at the top of the label stack (the
level m label) as an index into an ILM; level m label) as an index into an ILM;
5. For all i, 1<i<n: if a system S receives and forwards P after P 5. For all i, 1<i<n: if a system S receives and forwards P after P
is transmitted by Ri but before P is received by R[i+1] (e.g., is transmitted by Ri but before P is received by R[i+1] (e.g.,
Ri and R[i+1] might be connected via a switched data link Ri and R[i+1] might be connected via a switched data link
skipping to change at page 15, line 19 skipping to change at page 17, line 19
on the network layer header. This may be because: on the network layer header. This may be because:
a) the decision is not based on the label stack or the a) the decision is not based on the label stack or the
network layer header at all; network layer header at all;
b) the decision is based on a label stack on which b) the decision is based on a label stack on which
additional labels have been pushed (i.e., on a level m+k additional labels have been pushed (i.e., on a level m+k
label, where k>0). label, where k>0).
In other words, we can speak of the level m LSP for Packet P as the In other words, we can speak of the level m LSP for Packet P as the
sequence of LSRs: sequence of routers:
1. which begins with an LSR (an "LSP Ingress") that pushes on a 1. which begins with an LSR (an "LSP Ingress") that pushes on a
level m label, level m label,
2. all of whose intermediate LSRs make their forwarding decision 2. all of whose intermediate LSRs make their forwarding decision
by label Switching on a level m label, by label Switching on a level m label,
3. which ends (at an "LSP Egress") when a forwarding decision is 3. which ends (at an "LSP Egress") when a forwarding decision is
made by label Switching on a level m-k label, where k>0, or made by label Switching on a level m-k label, where k>0, or
when a forwarding decision is made by "ordinary", non-MPLS when a forwarding decision is made by "ordinary", non-MPLS
forwarding procedures. forwarding procedures.
A consequence (or perhaps a presupposition) of this is that whenever A consequence (or perhaps a presupposition) of this is that whenever
an LSR pushes a label onto an already labeled packet, it needs to an LSR pushes a label onto an already labeled packet, it needs to
make sure that the new label corresponds to a FEC whose LSP Egress is make sure that the new label corresponds to a FEC whose LSP Egress is
the LSR that assigned the label which is now second in the stack. the LSR that assigned the label which is now second in the stack.
Note that according to these definitions, if <R1, ..., Rn> is a level We will call a sequence of LSRs the "LSP for a particular stream S"
m LSP for packet P, P may be transmitted from R[n-1] to Rn with a if it is an LSP of level m for a particular packet P when P's level m
label stack of depth m-1. That is, the label stack may be popped at label is a label corresponding to stream S.
the penultimate LSR of the LSP, rather than at the LSP Egress. This
is appropriate, since the level m label has served its function of
getting the packet to Rn, and Rn's forwarding decision cannot be made
until the level m label is popped. If the label stack is not popped
by R[n-1], then Rn must do two label lookups; this is an overhead
which is best avoided. However, some hardware switching engines may
not be able to pop the label stack.
The penultimate node pops the label stack only if this is Consider the set of nodes which may be LSP ingress nodes for stream
specifically requested by the egress node. Having the penultimate S. Then there is an LSP for stream S which begins with each of those
node pop the label stack has an implication on the assignment of nodes. If a number of those LSPs have the same LSP egress, then one
labels: For any one node Rn, operating at level m in the MPLS can consider the set of such LSPs to be a tree, whose root is the LSP
hierarchy, there may be some LSPs which terminate at that node (i.e., egress. (Since data travels along this tree towards the root, this
for which Rn is the egress node) and some other LSPs which continue may be called a multipoint-to-point tree.) We can thus speak of the
beyond that node (i.e., for which Rn is an intermediate node). If the "LSP tree" for a particular stream S.
penultimate node R[n-1] pops the stack for those LSPs which terminate
at Rn, then node R[n] will receive some packets for which the top of
the stack is a level m label (i.e., packets destined for other egress
nodes), and some packets for which the top of the stack is a level
m-1 label (i.e., packets for which Rn is the egress). This implies
that in order for node R[n-1] to pop the stack, node Rn must assign
labels such that level m and level m-1 labels are distinguishable
(i.e., use unique values across multiple levels of the MPLS
hierarchy).
Note that if m = 1, the LSP Egress may receive an unlabeled packet, 2.13. Penultimate Hop Popping
and in fact need not even be capable of supporting MPLS. In this
case, assuming that we are using globally meaningful IP addresses,
the confusion of labels at multiple levels is not possible. However,
it is possible that the label may still be of value for the egress
node. One example is that the label may be used to assign the packet
to a particular Forwarding Equivalence Class (for example, to
identify the packet as a high priority packet). Another example is
that the label may assign the packet to a particular virtual private
network (for example, the virtual private network may make use of
local IP addresses, and the label may be necessary to disambiguate
the addresses). Therefore even when there is only a single label
value the stack is nonetheless popped only when requested by the
egress node.
We will call a sequence of LSRs the "LSP for a particular Stream S" Note that according to the definitions of section 2.11, if <R1, ...,
if it is an LSP of level m for a particular packet P when P's level m Rn> is a level m LSP for packet P, P may be transmitted from R[n-1]
label is a label corresponding to Stream S. to Rn with a label stack of depth m-1. That is, the label stack may
be popped at the penultimate LSR of the LSP, rather than at the LSP
Egress.
2.12. LSP Next Hop From an architectural perspective, this is perfectly appropriate.
The purpose of the level m label is to get the packet to Rn. Once
R[n-1] has decided to send the packet to Rn, the label no longer has
any function, and need no longer be carried.
There is also a practical advantage to doing penultimate hop popping.
If one does not do this, then when the LSP egress receives a packet,
it first looks up the top label, and determines as a result of that
lookup that it is indeed the LSP egress. Then it must pop the stack,
and examine what remains of the packet. If there is another label on
the stack, the egress will look this up and forward the packet based
on this lookup. (In this case, the egress for the packet's level m
LSP is also an intermediate node for its level m-1 LSP.) If there is
no other label on the stack, then the packet is forwarded according
to its network layer destination address. Note that this would
require the egress to do TWO lookups, either two label lookups or a
label lookup followed by an address lookup.
If, on the other hand, penultimate hop popping is used, then when the
penultimate hop looks up the label, it determines:
- that it is the penultimate hop, and
- who the next hop is.
The penultimate node then pops the stack, and forward the packet
based on the information gained by looking up the label that was at
the top of the stack. When the LSP egress receives the packet, the
label at the top of the stack will be the label which it needs to
look up in order to make its own forwarding decision. Or, if the
packet was only carrying a single label, the LSP egress will simply
see the network layer packet, which is just what it needs to see in
order to make its forwarding decision.
This technique allows the egress to do a single lookup, and also
requires only a single lookup by the penultimate node.
The creation of the forwarding fastpath in a label switching product
may be greatly aided if it is known that only a single lookup is
every required:
- the code may be simplified if it can assume that only a single
lookup is ever needed
- the code can be based on a "time budget" that assumes that only a
single lookup is ever needed.
In fact, when penultimate hop popping is done, the LSP Egress need
not even be an LSR.
However, some hardware switching engines may not be able to pop the
label stack, so this cannot be universally required. There may also
be some situations in which penultimate hop popping is not desirable.
Therefore the penultimate node pops the label stack only if this is
specifically requested by the egress node, or if the next node in the
LSP does not support MPLS. (If the next node in the LSP does support
MPLS, but does not make such a request, the penultimate node has no
way of knowing that it in fact is the penultimate node.)
An LSR which is capable of popping the label stack at all MUST do
penultimate hop popping when so requested by its downstream LDP peer.
Initial LDP negotiations must allow each LSR to determine whether its
neighboring LSRS are capable of popping the label stack. A LSR will
not request an LDP peer to pop the label stack unless it is capable
of doing so.
It may be asked whether the egress node can always interpret the top
label of a received packet properly if penultimate hop popping is
used. As long as the uniqueness and scoping rules of section 2.11
are obeyed, it is always possible to interpret the top label of a
received packet unambiguously.
2.14. LSP Next Hop
The LSP Next Hop for a particular labeled packet in a particular LSR The LSP Next Hop for a particular labeled packet in a particular LSR
is the LSR which is the next hop, as selected by the NHLFE entry used is the LSR which is the next hop, as selected by the NHLFE entry used
for forwarding that packet. for forwarding that packet.
The LSP Next Hop for a particular Stream is the next hop as selected The LSP Next Hop for a particular stream is the next hop as selected
by the NHLFE entry indexed by a label which corresponds to that by the NHLFE entry indexed by a label which corresponds to that
Stream. stream.
2.13. Route Selection Note that the LSP Next Hop may differ from the next hop which would
be chosen by the network layer routing algorithm. We will use the
term "L3 next hop" when we refer to the latter.
2.15. Route Selection
Route selection refers to the method used for selecting the LSP for a Route selection refers to the method used for selecting the LSP for a
particular stream. The proposed MPLS protocol architecture supports particular stream. The proposed MPLS protocol architecture supports
two options for Route Selection: (1) Hop by hop routing, and (2) two options for Route Selection: (1) Hop by hop routing, and (2)
Explicit routing. Explicit routing.
Hop by hop routing allows each node to independently choose the next Hop by hop routing allows each node to independently choose the next
hop for the path for a stream. This is the normal mode today with hop for the path for a stream. This is the normal mode today with
existing datagram IP networks. A hop by hop routed LSP refers to an existing datagram IP networks. A hop by hop routed LSP refers to an
LSP whose route is selected using hop by hop routing. LSP whose route is selected using hop by hop routing.
An explicitly routed LSP is an LSP where, at a given LSR, the LSP An explicitly routed LSP is an LSP where, at a given LSR, the LSP
next hop is not chosen by each local node, but rather is chosen by a next hop is not chosen by each local node, but rather is chosen by a
single node (usually the ingress or egress node of the LSP). The single node (usually the ingress or egress node of the LSP). The
sequence of LSRs followed by an explicit routing LSP may be chosen by sequence of LSRs followed by an explicitly routed LSP may be chosen
configuration, or by a protocol selected by a single node (for by configuration, or may be selected dynamically by a single node
example, the egress node may make use of the topological information (for example, the egress node may make use of the topological
learned from a link state database in order to compute the entire information learned from a link state database in order to compute
path for the tree ending at that egress node). Explicit routing may the entire path for the tree ending at that egress node). Explicit
be useful for a number of purposes such as allowing policy routing routing may be useful for a number of purposes such as allowing
and/or facilitating traffic engineering. With MPLS the explicit policy routing and/or facilitating traffic engineering. With MPLS
route needs to be specified at the time that Labels are assigned, but the explicit route needs to be specified at the time that labels are
the explicit route does not have to be specified with each IP packet. assigned, but the explicit route does not have to be specified with
This implies that explicit routing with MPLS is relatively efficient each IP packet. This implies that explicit routing with MPLS is
(when compared with the efficiency of explicit routing for pure relatively efficient (when compared with the efficiency of explicit
datagrams). routing for pure datagrams).
For any one LSP (at any one level of hierarchy), there are two For any one LSP (at any one level of hierarchy), there are two
possible options: (i) The entire LSP may be hop by hop routed from possible options: (i) The entire LSP may be hop by hop routed from
ingress to egress; (ii) The entire LSP may be explicit routed from ingress to egress; (ii) The entire LSP may be explicit routed from
ingress to egress. Intermediate cases do not make sense: In general, ingress to egress. Intermediate cases do not make sense: In general,
an LSP will be explicit routed specifically because there is a good an LSP will be explicit routed specifically because there is a good
reason to use an alternative to the hop by hop routed path. This reason to use an alternative to the hop by hop routed path. This
implies that if some of the nodes along the path follow an explicit implies that if some of the nodes along the path follow an explicit
route but some of the nodes make use of hop by hop routing, then route but some of the nodes make use of hop by hop routing, then
inconsistent routing will result and loops (or severely inefficient inconsistent routing will result and loops (or severely inefficient
skipping to change at page 18, line 10 skipping to change at page 21, line 10
explicit route if this is specified. explicit route if this is specified.
It is not necessary for a node to be able to create an explicit It is not necessary for a node to be able to create an explicit
route. However, in order to ensure interoperability it is necessary route. However, in order to ensure interoperability it is necessary
to ensure that either (i) Every node knows how to use hop by hop to ensure that either (i) Every node knows how to use hop by hop
routing; or (ii) Every node knows how to create and follow an routing; or (ii) Every node knows how to create and follow an
explicit route. We propose that due to the common use of hop by hop explicit route. We propose that due to the common use of hop by hop
routing in networks today, it is reasonable to make hop by hop routing in networks today, it is reasonable to make hop by hop
routing the default that all nodes need to be able to use. routing the default that all nodes need to be able to use.
2.14. Time-to-Live (TTL) 2.16. Time-to-Live (TTL)
In conventional IP forwarding, each packet carries a "Time To Live" In conventional IP forwarding, each packet carries a "Time To Live"
(TTL) value in its header. Whenever a packet passes through a (TTL) value in its header. Whenever a packet passes through a
router, its TTL gets decremented by 1; if the TTL reaches 0 before router, its TTL gets decremented by 1; if the TTL reaches 0 before
the packet has reached its destination, the packet gets discarded. the packet has reached its destination, the packet gets discarded.
This provides some level of protection against forwarding loops that This provides some level of protection against forwarding loops that
may exist due to misconfigurations, or due to failure or slow may exist due to misconfigurations, or due to failure or slow
convergence of the routing algorithm. TTL is sometimes used for other convergence of the routing algorithm. TTL is sometimes used for other
functions as well, such as multicast scoping, and supporting the functions as well, such as multicast scoping, and supporting the
skipping to change at page 19, line 19 skipping to change at page 22, line 19
TTL value before forwarding packets into a non-TTL LSP segment. TTL value before forwarding packets into a non-TTL LSP segment.
Sometimes it can be determined, upon ingress to a non-TTL LSP Sometimes it can be determined, upon ingress to a non-TTL LSP
segment, that a particular packet's TTL will expire before the packet segment, that a particular packet's TTL will expire before the packet
reaches the egress of that non-TTL LSP segment. In this case, the LSR reaches the egress of that non-TTL LSP segment. In this case, the LSR
at the ingress to the non-TTL LSP segment must not label switch the at the ingress to the non-TTL LSP segment must not label switch the
packet. This means that special procedures must be developed to packet. This means that special procedures must be developed to
support traceroute functionality, for example, traceroute packets may support traceroute functionality, for example, traceroute packets may
be forwarded using conventional hop by hop forwarding. be forwarded using conventional hop by hop forwarding.
2.15. Loop Control 2.17. Loop Control
On a non-TTL LSP segment, by definition, TTL cannot be used to On a non-TTL LSP segment, by definition, TTL cannot be used to
protect against forwarding loops. The importance of loop control may protect against forwarding loops. The importance of loop control may
depend on the particular hardware being used to provide the LSR depend on the particular hardware being used to provide the LSR
functions along the non-TTL LSP segment. functions along the non-TTL LSP segment.
Suppose, for instance, that ATM switching hardware is being used to Suppose, for instance, that ATM switching hardware is being used to
provide MPLS switching functions, with the label being carried in the provide MPLS switching functions, with the label being carried in the
VPI/VCI field. Since ATM switching hardware cannot decrement TTL, VPI/VCI field. Since ATM switching hardware cannot decrement TTL,
there is no protection against loops. If the ATM hardware is capable there is no protection against loops. If the ATM hardware is capable
skipping to change at page 20, line 5 skipping to change at page 22, line 46
Even if fair buffer access can be provided, it is still worthwhile to Even if fair buffer access can be provided, it is still worthwhile to
have some means of detecting loops that last "longer than possible". have some means of detecting loops that last "longer than possible".
In addition, even where TTL and/or per-VC fair queuing provides a In addition, even where TTL and/or per-VC fair queuing provides a
means for surviving loops, it still may be desirable where practical means for surviving loops, it still may be desirable where practical
to avoid setting up LSPs which loop. to avoid setting up LSPs which loop.
The MPLS architecture will therefore provide a technique for ensuring The MPLS architecture will therefore provide a technique for ensuring
that looping LSP segments can be detected, and a technique for that looping LSP segments can be detected, and a technique for
ensuring that looping LSP segments are never created. ensuring that looping LSP segments are never created.
2.15.1. Loop Prevention All LSRs will be required to support a common technique for loop
detection. Support for the loop prevention technique is optional,
though it is recommended in ATM-LSRs that have no other way to
protect themselves against the effects of looping data packets. Use
of the loop prevention technique, when supported, is optional.
2.17.1. Loop Prevention
NOTE: The loop prevention technique described here is being
reconsidered, and may be changed.
LSR's maintain for each of their LSP's an LSR id list. This list is a LSR's maintain for each of their LSP's an LSR id list. This list is a
list of all the LSR's downstream from this LSR on a given LSP. The list of all the LSR's downstream from this LSR on a given LSP. The
LSR id list is used to prevent the formation of switched path loops. LSR id list is used to prevent the formation of switched path loops.
The LSR ID list is propagated upstream from a node to its neighbor The LSR ID list is propagated upstream from a node to its neighbor
nodes. The LSR ID list is used to prevent loops as follows: nodes. The LSR ID list is used to prevent loops as follows:
When a node, R, detects a change in the next hop for a given stream, When a node, R, detects a change in the next hop for a given stream,
it asks its new next hop for a label and the associated LSR ID list it asks its new next hop for a label and the associated LSR ID list
for that stream. for that stream.
skipping to change at page 22, line 38 skipping to change at page 25, line 42
The LSR Id list can also be used to provide a "loop detection" The LSR Id list can also be used to provide a "loop detection"
capability. To use it in this manner, an LSR which sees that it is capability. To use it in this manner, an LSR which sees that it is
already in the LSR Id list for a particular stream will immediately already in the LSR Id list for a particular stream will immediately
unsplice itself from the switched path for that stream, and will NOT unsplice itself from the switched path for that stream, and will NOT
pass the LSR Id list further upstream. The LSR can rejoin a switched pass the LSR Id list further upstream. The LSR can rejoin a switched
path for the stream when it changes its next hop for that stream, or path for the stream when it changes its next hop for that stream, or
when it receives a new LSR Id list from its current next hop, in when it receives a new LSR Id list from its current next hop, in
which it is not contained. The diffusion computation would be which it is not contained. The diffusion computation would be
omitted. omitted.
2.15.2. Interworking of Loop Control Options 2.17.2. Interworking of Loop Control Options
The MPLS protocol architecture allows some nodes to be using loop The MPLS protocol architecture allows some nodes to be using loop
prevention, while some other nodes are not (i.e., the choice of prevention, while some other nodes are not (i.e., the choice of
whether or not to use loop prevention may be a local decision). When whether or not to use loop prevention may be a local decision). When
this mix is used, it is not possible for a loop to form which this mix is used, it is not possible for a loop to form which
includes only nodes which do loop prevention. However, it is possible includes only nodes which do loop prevention. However, it is possible
for loops to form which contain a combination of some nodes which do for loops to form which contain a combination of some nodes which do
loop prevention, and some nodes which do not. loop prevention, and some nodes which do not.
There are at least four identified cases in which it makes sense to There are at least four identified cases in which it makes sense to
skipping to change at page 23, line 36 skipping to change at page 26, line 41
doing or not doing loop prevention as options, and is permitted to doing or not doing loop prevention as options, and is permitted to
choose which to use for any one particular LSP based on the choose which to use for any one particular LSP based on the
information obtained from downstream nodes. When the label mapping information obtained from downstream nodes. When the label mapping
arrives from downstream, then the node may choose whether to use loop arrives from downstream, then the node may choose whether to use loop
prevention so as to continue to use the same approach as was used in prevention so as to continue to use the same approach as was used in
the information passed to it. Note that regardless of whether loop the information passed to it. Note that regardless of whether loop
prevention is used the egress nodes (for any particular LSP) always prevention is used the egress nodes (for any particular LSP) always
initiates exchange of label mapping information without waiting for initiates exchange of label mapping information without waiting for
other nodes to act. other nodes to act.
2.16. Merging and Non-Merging LSRs 2.18. Merging and Non-Merging LSRs
Merge allows multiple upstream LSPs to be merged into a single Merge allows multiple upstream LSPs to be merged into a single
downstream LSP. When implemented by multiple nodes, this results in downstream LSP. When implemented by multiple nodes, this results in
the traffic going to a particular egress nodes, based on one the traffic going to a particular egress nodes, based on one
particular Stream, to follow a multipoint to point tree (MPT), with particular stream, to follow a multipoint to point tree (MPT), with
the MPT rooted at the egress node and associated with the Stream. the MPT rooted at the egress node and associated with the stream.
This can have a significant effect on reducing the number of labels This can have a significant effect on reducing the number of labels
that need to be maintained by any one particular node. that need to be maintained by any one particular node.
If merge was not used at all it would be necessary for each node to If merge was not used at all it would be necessary for each node to
provide the upstream neighbors with a label for each Stream for each provide the upstream neighbors with a label for each stream for each
upstream node which may be forwarding traffic over the link. This upstream node which may be forwarding traffic over the link. This
implies that the number of labels needed might not in general be implies that the number of labels needed might not in general be
known a priori. However, the use of merge allows a single label to be known a priori. However, the use of merge allows a single label to be
used per Stream, therefore allowing label assignment to be done in a used per stream, therefore allowing label assignment to be done in a
common way without regard for the number of upstream nodes which will common way without regard for the number of upstream nodes which will
be using the downstream LSP. be using the downstream LSP.
The proposed MPLS protocol architecture supports LSP merge, while The proposed MPLS protocol architecture supports LSP merge, while
allowing nodes which do not support LSP merge. This leads to the allowing nodes which do not support LSP merge. This leads to the
issue of ensuring correct interoperation between nodes which issue of ensuring correct interoperation between nodes which
implement merge and those which do not. The issue is somewhat implement merge and those which do not. The issue is somewhat
different in the case of datagram media versus the case of ATM. The different in the case of datagram media versus the case of ATM. The
different media types will therefore be discussed separately. different media types will therefore be discussed separately.
2.16.1. Stream Merge 2.18.1. Stream Merge
Let us say that an LSR is capable of Stream Merge if it can receive Let us say that an LSR is capable of Stream Merge if it can receive
two packets from different incoming interfaces, and/or with different two packets from different incoming interfaces, and/or with different
labels, and send both packets out the same outgoing interface with labels, and send both packets out the same outgoing interface with
the same label. This in effect takes two incoming streams and merges the same label. This in effect takes two incoming streams and merges
them into one. Once the packets are transmitted, the information that them into one. Once the packets are transmitted, the information that
they arrived from different interfaces and/or with different incoming they arrived from different interfaces and/or with different incoming
labels is lost. labels is lost.
Let us say that an LSR is not capable of Stream Merge if, for any two Let us say that an LSR is not capable of Stream Merge if, for any two
skipping to change at page 24, line 39 skipping to change at page 27, line 43
An LSR which is capable of Stream Merge (a "Merging LSR") needs to An LSR which is capable of Stream Merge (a "Merging LSR") needs to
maintain only one outgoing label for each FEC. AN LSR which is not maintain only one outgoing label for each FEC. AN LSR which is not
capable of Stream Merge (a "Non-merging LSR") may need to maintain as capable of Stream Merge (a "Non-merging LSR") may need to maintain as
many as N outgoing labels per FEC, where N is the number of LSRs in many as N outgoing labels per FEC, where N is the number of LSRs in
the network. Hence by supporting Stream Merge, an LSR can reduce its the network. Hence by supporting Stream Merge, an LSR can reduce its
number of outgoing labels by a factor of O(N). Since each label in number of outgoing labels by a factor of O(N). Since each label in
use requires the dedication of some amount of resources, this can be use requires the dedication of some amount of resources, this can be
a significant savings. a significant savings.
2.16.2. Non-merging LSRs 2.18.2. Non-merging LSRs
The MPLS forwarding procedures is very similar to the forwarding The MPLS forwarding procedures is very similar to the forwarding
procedures used by such technologies as ATM and Frame Relay. That is, procedures used by such technologies as ATM and Frame Relay. That is,
a unit of data arrives, a label (VPI/VCI or DLCI) is looked up in a a unit of data arrives, a label (VPI/VCI or DLCI) is looked up in a
"cross-connect table", on the basis of that lookup an output port is "cross-connect table", on the basis of that lookup an output port is
chosen, and the label value is rewritten. In fact, it is possible to chosen, and the label value is rewritten. In fact, it is possible to
use such technologies for MPLS forwarding; LDP can be used as the use such technologies for MPLS forwarding; LDP can be used as the
"signalling protocol" for setting up the cross-connect tables. "signalling protocol" for setting up the cross-connect tables.
Unfortunately, these technologies do not necessarily support the Unfortunately, these technologies do not necessarily support the
skipping to change at page 25, line 21 skipping to change at page 28, line 25
reassemble the packets. reassemble the packets.
We propose to support two solutions to this problem. First, MPLS will We propose to support two solutions to this problem. First, MPLS will
contain procedures which allow the use of non-merging LSRs. Second, contain procedures which allow the use of non-merging LSRs. Second,
MPLS will support procedures which allow certain ATM switches to MPLS will support procedures which allow certain ATM switches to
function as merging LSRs. function as merging LSRs.
Since MPLS supports both merging and non-merging LSRs, MPLS also Since MPLS supports both merging and non-merging LSRs, MPLS also
contains procedures to ensure correct interoperation between them. contains procedures to ensure correct interoperation between them.
2.16.3. Labels for Merging and Non-Merging LSRs 2.18.3. Labels for Merging and Non-Merging LSRs
An upstream LSR which supports Stream Merge needs to be sent only one An upstream LSR which supports Stream Merge needs to be sent only one
label per FEC. An upstream neighbor which does not support Stream label per FEC. An upstream neighbor which does not support Stream
Merge needs to be sent multiple labels per FEC. However, there is no Merge needs to be sent multiple labels per FEC. However, there is no
way of knowing a priori how many labels it needs. This will depend on way of knowing a priori how many labels it needs. This will depend on
how many LSRs are upstream of it with respect to the FEC in question. how many LSRs are upstream of it with respect to the FEC in question.
In the MPLS architecture, if a particular upstream neighbor does not In the MPLS architecture, if a particular upstream neighbor does not
support Stream Merge, it is not sent any labels for a particular FEC support Stream Merge, it is not sent any labels for a particular FEC
unless it explicitly asks for a label for that FEC. The upstream unless it explicitly asks for a label for that FEC. The upstream
skipping to change at page 25, line 43 skipping to change at page 28, line 47
each time. When a downstream neighbor receives such a request from each time. When a downstream neighbor receives such a request from
upstream, and the downstream neighbor does not itself support Stream upstream, and the downstream neighbor does not itself support Stream
Merge, then it must in turn ask its downstream neighbor for another Merge, then it must in turn ask its downstream neighbor for another
label for the FEC in question. label for the FEC in question.
It is possible that there may be some nodes which support merge, but It is possible that there may be some nodes which support merge, but
have a limited number of upstream streams which may be merged into a have a limited number of upstream streams which may be merged into a
single downstream streams. Suppose for example that due to some single downstream streams. Suppose for example that due to some
hardware limitation a node is capable of merging four upstream LSPs hardware limitation a node is capable of merging four upstream LSPs
into a single downstream LSP. Suppose however, that this particular into a single downstream LSP. Suppose however, that this particular
node has six upstream LSPs arriving at it for a particular Stream. In node has six upstream LSPs arriving at it for a particular stream. In
this case, this node may merge these into two downstream LSPs this case, this node may merge these into two downstream LSPs
(corresponding to two labels that need to be obtained from the (corresponding to two labels that need to be obtained from the
downstream neighbor). In this case, the normal operation of the LDP downstream neighbor). In this case, the normal operation of the LDP
implies that the downstream neighbor will supply this node with a implies that the downstream neighbor will supply this node with a
single label for the Stream. This node can then ask its downstream single label for the stream. This node can then ask its downstream
neighbor for one additional label for the Stream, implying that the neighbor for one additional label for the stream, implying that the
node will thereby obtain the required two labels. node will thereby obtain the required two labels.
The interaction between explicit routing and merge is FFS. The interaction between explicit routing and merge is FFS.
2.16.4. Merge over ATM 2.18.4. Merge over ATM
2.16.4.1. Methods of Eliminating Cell Interleave 2.18.4.1. Methods of Eliminating Cell Interleave
There are several methods that can be used to eliminate the cell There are several methods that can be used to eliminate the cell
interleaving problem in ATM, thereby allowing ATM switches to support interleaving problem in ATM, thereby allowing ATM switches to support
stream merge: : stream merge: :
1. VP merge 1. VP merge
When VP merge is used, multiple virtual paths are merged into a When VP merge is used, multiple virtual paths are merged into a
virtual path, but packets from different sources are virtual path, but packets from different sources are
distinguished by using different VCs within the VP. distinguished by using different VCs within the VP.
skipping to change at page 26, line 42 skipping to change at page 29, line 46
disadvantage that it requires coordination of the VCI space within disadvantage that it requires coordination of the VCI space within
each VP. There are a number of ways that this can be accomplished. each VP. There are a number of ways that this can be accomplished.
Selection of one or more methods is FFS. Selection of one or more methods is FFS.
This tradeoff between compatibility with existing equipment versus This tradeoff between compatibility with existing equipment versus
protocol complexity and scalability implies that it is desirable for protocol complexity and scalability implies that it is desirable for
the MPLS protocol to support both VP merge and VC merge. In order to the MPLS protocol to support both VP merge and VC merge. In order to
do so each ATM switch participating in MPLS needs to know whether its do so each ATM switch participating in MPLS needs to know whether its
immediate ATM neighbors perform VP merge, VC merge, or no merge. immediate ATM neighbors perform VP merge, VC merge, or no merge.
2.16.4.2. Interoperation: VC Merge, VP Merge, and Non-Merge 2.18.4.2. Interoperation: VC Merge, VP Merge, and Non-Merge
The interoperation of the various forms of merging over ATM is most The interoperation of the various forms of merging over ATM is most
easily described by first describing the interoperation of VC merge easily described by first describing the interoperation of VC merge
with non-merge. with non-merge.
In the case where VC merge and non-merge nodes are interconnected the In the case where VC merge and non-merge nodes are interconnected the
forwarding of cells is based in all cases on a VC (i.e., the forwarding of cells is based in all cases on a VC (i.e., the
concatenation of the VPI and VCI). For each node, if an upstream concatenation of the VPI and VCI). For each node, if an upstream
neighbor is doing VC merge then that upstream neighbor requires only neighbor is doing VC merge then that upstream neighbor requires only
a single VPI/VCI for a particular Stream (this is analogous to the a single VPI/VCI for a particular stream (this is analogous to the
requirement for a single label in the case of operation over frame requirement for a single label in the case of operation over frame
media). If the upstream neighbor is not doing merge, then the media). If the upstream neighbor is not doing merge, then the
neighbor will require a single VPI/VCI per Stream for itself, plus neighbor will require a single VPI/VCI per stream for itself, plus
enough VPI/VCIs to pass to its upstream neighbors. The number enough VPI/VCIs to pass to its upstream neighbors. The number
required will be determined by allowing the upstream nodes to request required will be determined by allowing the upstream nodes to request
additional VPI/VCIs from their downstream neighbors (this is again additional VPI/VCIs from their downstream neighbors (this is again
analogous to the method used with frame merge). analogous to the method used with frame merge).
A similar method is possible to support nodes which perform VP merge. A similar method is possible to support nodes which perform VP merge.
In this case the VP merge node, rather than requesting a single In this case the VP merge node, rather than requesting a single
VPI/VCI or a number of VPI/VCIs from its downstream neighbor, instead VPI/VCI or a number of VPI/VCIs from its downstream neighbor, instead
may request a single VP (identified by a VPI) but several VCIs within may request a single VP (identified by a VPI) but several VCIs within
the VP. Furthermore, suppose that a non-merge node is downstream the VP. Furthermore, suppose that a non-merge node is downstream
skipping to change at page 27, line 38 skipping to change at page 30, line 43
of VCs (identified by a set of VCIs which are significant within a of VCs (identified by a set of VCIs which are significant within a
VP). VP merge nodes would therefore request one VP, with a contained VP). VP merge nodes would therefore request one VP, with a contained
VCI for traffic that it originates (if appropriate) plus a VCI for VCI for traffic that it originates (if appropriate) plus a VCI for
each VC requested from above (regardless of whether or not the VC is each VC requested from above (regardless of whether or not the VC is
part of a containing VP). VC merge node would request only a single part of a containing VP). VC merge node would request only a single
VPI/VCI (since they can merge all upstream traffic into a single VC). VPI/VCI (since they can merge all upstream traffic into a single VC).
Non-merge nodes would pass on any requests that they get from above, Non-merge nodes would pass on any requests that they get from above,
plus request a VPI/VCI for traffic that they originate (if plus request a VPI/VCI for traffic that they originate (if
appropriate). appropriate).
2.17. LSP Control: Egress versus Local 2.19. LSP Control: Egress versus Local
There is a choice to be made regarding whether the initial setup of There is a choice to be made regarding whether the initial setup of
LSPs will be initiated by the egress node, or locally by each LSPs will be initiated by the egress node, or locally by each
individual node. individual node.
When LSP control is done locally, then each node may at any time pass When LSP control is done locally, then each node may at any time pass
label bindings to its neighbors for each FEC recognized by that node. label bindings to its neighbors for each FEC recognized by that node.
In the normal case that the neighboring nodes recognize the same In the normal case that the neighboring nodes recognize the same
FECs, then nodes may map incoming labels to outgoing labels as part FECs, then nodes may map incoming labels to outgoing labels as part
of the normal label swapping forwarding method. of the normal label swapping forwarding method.
When LSP control is done by the egress, then initially only the When LSP control is done by the egress, then initially only the
egress node passes label bindings to its neighbors corresponding to egress node passes label bindings to its neighbors corresponding to
any FECs which leave the MPLS network at that egress node. Other any FECs which leave the MPLS network at that egress node. Other
nodes wait until they get a label from downstream for a particular nodes wait until they get a label from downstream for a particular
FEC before passing a corresponding label for the same FEC to upstream FEC before passing a corresponding label for the same FEC to upstream
nodes. nodes.
skipping to change at page 28, line 33 skipping to change at page 31, line 39
configuration) change its mind in terms of the granularity which is configuration) change its mind in terms of the granularity which is
to be used. This implies the same mechanism will be necessary to to be used. This implies the same mechanism will be necessary to
allow changes in granularity to bubble up to upstream nodes. The allow changes in granularity to bubble up to upstream nodes. The
choice of egress or local control may therefore effect the frequency choice of egress or local control may therefore effect the frequency
with which this mechanism is used, but will not effect the need for a with which this mechanism is used, but will not effect the need for a
mechanism to achieve consistency of label granularity. Generally mechanism to achieve consistency of label granularity. Generally
speaking, the choice of local versus egress control does not appear speaking, the choice of local versus egress control does not appear
to have any effect on the LDP mechanisms which need to be defined. to have any effect on the LDP mechanisms which need to be defined.
Egress control and local control can interwork in a very Egress control and local control can interwork in a very
straightforward manner (although some of the advantages ascribed to straightforward manner (although when both methods exist in the
egress control may be lost, see appendices A and B). With either network, the overall behavior of the network is largely that of local
approach, (assuming downstream label assignment) the egress node will control). With either approach, (assuming downstream label
initially assign labels for particular FECs and will pass these assignment) the egress node will initially assign labels for
labels to its neighbors. With either approach these label assignments particular FECs and will pass these labels to its neighbors. With
will bubble upstream, with the upstream nodes choosing labels that either approach these label assignments will bubble upstream, with
are consistent with the labels that they receive from downstream. The the upstream nodes choosing labels that are consistent with the
difference between the two approaches is therefore primarily an issue labels that they receive from downstream. The difference between the
of what each node does prior to obtaining a label assignment for a two approaches is therefore primarily an issue of what each node does
particular FEC from downstream nodes: Does it wait, or does it assign prior to obtaining a label assignment for a particular FEC from
a preliminary label under the expectation that it will (probably) be downstream nodes: Does it wait, or does it assign a preliminary label
correct? under the expectation that it will (probably) be correct?
Regardless of which method is used (local control or egress control) Regardless of which method is used (local control or egress control)
each node needs to know (possibly by configuration) what granularity each node needs to know (possibly by configuration) what granularity
to use for labels that it assigns. Where egress control is used, this to use for labels that it assigns. Where egress control is used, this
requires each node to know the granularity only for streams which requires each node to know the granularity only for streams which
leave the MPLS network at that node. For local control, in order to leave the MPLS network at that node. For local control, in order to
avoid the need to withdraw inconsistent labels, each node in the avoid the need to withdraw inconsistent labels, each node in the
network would need to be configured consistently to know the network would need to be configured consistently to know the
granularity for each stream. However, in many cases this may be done granularity for each stream. However, in many cases this may be done
by using a single level of granularity which applies to all streams by using a single level of granularity which applies to all streams
(such as "one label per IP prefix in the forwarding table"). The (such as "one label per IP prefix in the forwarding table").
choice between local control versus egress control could similarly be
left as a configuration option.
Future versions of the MPLS architecture will need to choose between This architecture allows the choice between local control and egress
three options: (i) Requiring local control; (ii) Requiring egress control to be a local matter. Since the two methods interwork, a
control; or (iii) Allowing a choice of local control or egress given LSR need support only one or the other.
control. Arguments for local versus egress control are contained in
appendices A and B.
2.18. Granularity 2.20. Granularity
When forwarding by label swapping, a stream of packets following a When forwarding by label swapping, a stream of packets following a
stream arriving from upstream may be mapped into an equal or coarser stream arriving from upstream may be mapped into an equal or coarser
grain stream. However, a coarse grain stream (for example, containing grain stream. However, a coarse grain stream (for example, containing
packets destined for a short IP address prefix covering many subnets) packets destined for a short IP address prefix covering many subnets)
cannot be mapped directly into a finer grain stream (for example, cannot be mapped directly into a finer grain stream (for example,
containing packets destined for a longer IP address prefix covering a containing packets destined for a longer IP address prefix covering a
single subnet). This implies that there needs to be some mechanism single subnet). This implies that there needs to be some mechanism
for ensuring consistency between the granularity of LSPs in an MPLS for ensuring consistency between the granularity of LSPs in an MPLS
network. network.
skipping to change at page 30, line 5 skipping to change at page 33, line 5
case the node has two options: (i) It may forward the corresponding case the node has two options: (i) It may forward the corresponding
packets using normal IP datagram forwarding (i.e., by examination of packets using normal IP datagram forwarding (i.e., by examination of
the IP header); (ii) It may withdraw the label mappings that it has the IP header); (ii) It may withdraw the label mappings that it has
passed to its upstream neighbors, and replace these with finer grain passed to its upstream neighbors, and replace these with finer grain
label mappings. label mappings.
When LSP control is egress based, the label setup originates from the When LSP control is egress based, the label setup originates from the
egress node and passes upstream. It is therefore straightforward with egress node and passes upstream. It is therefore straightforward with
this approach to maintain equally-grained mappings along the route. this approach to maintain equally-grained mappings along the route.
2.19. Tunnels and Hierarchy 2.21. Tunnels and Hierarchy
Sometimes a router Ru takes explicit action to cause a particular Sometimes a router Ru takes explicit action to cause a particular
packet to be delivered to another router Rd, even though Ru and Rd packet to be delivered to another router Rd, even though Ru and Rd
are not consecutive routers on the Hop-by-hop path for that packet, are not consecutive routers on the Hop-by-hop path for that packet,
and Rd is not the packet's ultimate destination. For example, this and Rd is not the packet's ultimate destination. For example, this
may be done by encapsulating the packet inside a network layer packet may be done by encapsulating the packet inside a network layer packet
whose destination address is the address of Rd itself. This creates a whose destination address is the address of Rd itself. This creates a
"tunnel" from Ru to Rd. We refer to any packet so handled as a "tunnel" from Ru to Rd. We refer to any packet so handled as a
"Tunneled Packet". "Tunneled Packet".
2.19.1. Hop-by-Hop Routed Tunnel 2.21.1. Hop-by-Hop Routed Tunnel
If a Tunneled Packet follows the Hop-by-hop path from Ru to Rd, we If a Tunneled Packet follows the Hop-by-hop path from Ru to Rd, we
say that it is in an "Hop-by-Hop Routed Tunnel" whose "transmit say that it is in an "Hop-by-Hop Routed Tunnel" whose "transmit
endpoint" is Ru and whose "receive endpoint" is Rd. endpoint" is Ru and whose "receive endpoint" is Rd.
2.19.2. Explicitly Routed Tunnel 2.21.2. Explicitly Routed Tunnel
If a Tunneled Packet travels from Ru to Rd over a path other than the If a Tunneled Packet travels from Ru to Rd over a path other than the
Hop-by-hop path, we say that it is in an "Explicitly Routed Tunnel" Hop-by-hop path, we say that it is in an "Explicitly Routed Tunnel"
whose "transmit endpoint" is Ru and whose "receive endpoint" is Rd. whose "transmit endpoint" is Ru and whose "receive endpoint" is Rd.
For example, we might send a packet through an Explicitly Routed For example, we might send a packet through an Explicitly Routed
Tunnel by encapsulating it in a packet which is source routed. Tunnel by encapsulating it in a packet which is source routed.
2.19.3. LSP Tunnels 2.21.3. LSP Tunnels
It is possible to implement a tunnel as a LSP, and use label It is possible to implement a tunnel as a LSP, and use label
switching rather than network layer encapsulation to cause the packet switching rather than network layer encapsulation to cause the packet
to travel through the tunnel. The tunnel would be a LSP <R1, ..., to travel through the tunnel. The tunnel would be a LSP <R1, ...,
Rn>, where R1 is the transmit endpoint of the tunnel, and Rn is the Rn>, where R1 is the transmit endpoint of the tunnel, and Rn is the
receive endpoint of the tunnel. This is called a "LSP Tunnel". receive endpoint of the tunnel. This is called a "LSP Tunnel".
The set of packets which are to be sent though the LSP tunnel becomes The set of packets which are to be sent though the LSP tunnel becomes
a Stream, and each LSR in the tunnel must assign a label to that a stream, and each LSR in the tunnel must assign a label to that
Stream (i.e., must assign a label to the tunnel). The criteria for stream (i.e., must assign a label to the tunnel). The criteria for
assigning a particular packet to an LSP tunnel is a local matter at assigning a particular packet to an LSP tunnel is a local matter at
the tunnel's transmit endpoint. To put a packet into an LSP tunnel, the tunnel's transmit endpoint. To put a packet into an LSP tunnel,
the transmit endpoint pushes a label for the tunnel onto the label the transmit endpoint pushes a label for the tunnel onto the label
stack and sends the labeled packet to the next hop in the tunnel. stack and sends the labeled packet to the next hop in the tunnel.
If it is not necessary for the tunnel's receive endpoint to be able If it is not necessary for the tunnel's receive endpoint to be able
to determine which packets it receives through the tunnel, as to determine which packets it receives through the tunnel, as
discussed earlier, the label stack may be popped at the penultimate discussed earlier, the label stack may be popped at the penultimate
LSR in the tunnel. LSR in the tunnel.
A "Hop-by-Hop Routed LSP Tunnel" is a Tunnel that is implemented as A "Hop-by-Hop Routed LSP Tunnel" is a Tunnel that is implemented as
an hop-by-hop routed LSP between the transmit endpoint and the an hop-by-hop routed LSP between the transmit endpoint and the
receive endpoint. receive endpoint.
An "Explicitly Routed LSP Tunnel" is a LSP Tunnel that is also an An "Explicitly Routed LSP Tunnel" is a LSP Tunnel that is also an
Explicitly Routed LSP. Explicitly Routed LSP.
2.19.4. Hierarchy: LSP Tunnels within LSPs 2.21.4. Hierarchy: LSP Tunnels within LSPs
Consider a LSP <R1, R2, R3, R4>. Let us suppose that R1 receives Consider a LSP <R1, R2, R3, R4>. Let us suppose that R1 receives
unlabeled packet P, and pushes on its label stack the label to cause unlabeled packet P, and pushes on its label stack the label to cause
it to follow this path, and that this is in fact the Hop-by-hop path. it to follow this path, and that this is in fact the Hop-by-hop path.
However, let us further suppose that R2 and R3 are not directly However, let us further suppose that R2 and R3 are not directly
connected, but are "neighbors" by virtue of being the endpoints of an connected, but are "neighbors" by virtue of being the endpoints of an
LSP tunnel. So the actual sequence of LSRs traversed by P is <R1, R2, LSP tunnel. So the actual sequence of LSRs traversed by P is <R1, R2,
R21, R22, R23, R3, R4>. R21, R22, R23, R3, R4>.
When P travels from R1 to R2, it will have a label stack of depth 1. When P travels from R1 to R2, it will have a label stack of depth 1.
skipping to change at page 31, line 35 skipping to change at page 34, line 35
to R3. Then it pushes on a new label. This level 2 label has a value to R3. Then it pushes on a new label. This level 2 label has a value
which is meaningful to R21. Switching is done on the level 2 label by which is meaningful to R21. Switching is done on the level 2 label by
R21, R22, R23. R23, which is the penultimate hop in the R2-R3 tunnel, R21, R22, R23. R23, which is the penultimate hop in the R2-R3 tunnel,
pops the label stack before forwarding the packet to R3. When R3 sees pops the label stack before forwarding the packet to R3. When R3 sees
packet P, P has only a level 1 label, having now exited the tunnel. packet P, P has only a level 1 label, having now exited the tunnel.
Since R3 is the penultimate hop in P's level 1 LSP, it pops the label Since R3 is the penultimate hop in P's level 1 LSP, it pops the label
stack, and R4 receives P unlabeled. stack, and R4 receives P unlabeled.
The label stack mechanism allows LSP tunneling to nest to any depth. The label stack mechanism allows LSP tunneling to nest to any depth.
2.19.5. LDP Peering and Hierarchy 2.21.5. LDP Peering and Hierarchy
Suppose that packet P travels along a Level 1 LSP <R1, R2, R3, R4>, Suppose that packet P travels along a Level 1 LSP <R1, R2, R3, R4>,
and when going from R2 to R3 travels along a Level 2 LSP <R2, R21, and when going from R2 to R3 travels along a Level 2 LSP <R2, R21,
R22, R3>. From the perspective of the Level 2 LSP, R2's LDP peer is R22, R3>. From the perspective of the Level 2 LSP, R2's LDP peer is
R21. From the perspective of the Level 1 LSP, R2's LDP peers are R1 R21. From the perspective of the Level 1 LSP, R2's LDP peers are R1
and R3. One can have LDP peers at each layer of hierarchy. We will and R3. One can have LDP peers at each layer of hierarchy. We will
see in sections 3.6 and 3.7 some ways to make use of this hierarchy. see in sections 3.6 and 3.7 some ways to make use of this hierarchy.
Note that in this example, R2 and R21 must be IGP neighbors, but R2 Note that in this example, R2 and R21 must be IGP neighbors, but R2
and R3 need not be. and R3 need not be.
skipping to change at page 33, line 5 skipping to change at page 36, line 5
Peers is large. Implicit peering does not require a n-square Peers is large. Implicit peering does not require a n-square
peering mesh to distribute labels to the remote LDP peers peering mesh to distribute labels to the remote LDP peers
because the information is piggybacked through the local LDP because the information is piggybacked through the local LDP
peering. However, implicit peering requires the intermediate peering. However, implicit peering requires the intermediate
nodes to store information that they might not be directly nodes to store information that they might not be directly
interested in. interested in.
An example of the use of implicit peering is found in section An example of the use of implicit peering is found in section
3.3. 3.3.
2.20. LDP Transport 2.22. LDP Transport
LDP is used between nodes in an MPLS network to establish and LDP is used between nodes in an MPLS network to establish and
maintain the label mappings. In order for LDP to operate correctly, maintain the label mappings. In order for LDP to operate correctly,
LDP information needs to be transmitted reliably, and the LDP LDP information needs to be transmitted reliably, and the LDP
messages pertaining to a particular FEC need to be transmitted in messages pertaining to a particular FEC need to be transmitted in
sequence. This may potentially be accomplished either by using an sequence. Flow control is also required, as is the capability to
existing reliable transport protocol such as TCP, or by specifying carry multiple LDP messages in a single datagram.
reliability mechanisms as part of LDP (for example, the reliability
mechanisms which are defined in IDRP could potentially be "borrowed"
for use with LSP). The precise means for accomplishing transport
reliability with LSP are for further study, but will be specified by
the MPLS Protocol Architecture before the architecture may be
considered complete.
2.21. Label Encodings These goals will be met by using TCP as the underlying transport for
LDP.
(The use of multicast techniques to distribute label mappings is
FFS.)
2.23. Label Encodings
In order to transmit a label stack along with the packet whose label In order to transmit a label stack along with the packet whose label
stack it is, it is necessary to define a concrete encoding of the stack it is, it is necessary to define a concrete encoding of the
label stack. The architecture supports several different encoding label stack. The architecture supports several different encoding
techniques; the choice of encoding technique depends on the techniques; the choice of encoding technique depends on the
particular kind of device being used to forward labeled packets. particular kind of device being used to forward labeled packets.
2.21.1. MPLS-specific Hardware and/or Software 2.23.1. MPLS-specific Hardware and/or Software
If one is using MPLS-specific hardware and/or software to forward If one is using MPLS-specific hardware and/or software to forward
labeled packets, the most obvious way to encode the label stack is to labeled packets, the most obvious way to encode the label stack is to
define a new protocol to be used as a "shim" between the data link define a new protocol to be used as a "shim" between the data link
layer and network layer headers. This shim would really be just an layer and network layer headers. This shim would really be just an
encapsulation of the network layer packet; it would be "protocol- encapsulation of the network layer packet; it would be "protocol-
independent" such that it could be used to encapsulate any network independent" such that it could be used to encapsulate any network
layer. Hence we will refer to it as the "generic MPLS layer. Hence we will refer to it as the "generic MPLS
encapsulation". encapsulation".
skipping to change at page 34, line 13 skipping to change at page 37, line 13
2. a Time-to-Live (TTL) field 2. a Time-to-Live (TTL) field
3. a Class of Service (CoS) field 3. a Class of Service (CoS) field
The TTL field permits MPLS to provide a TTL function similar to what The TTL field permits MPLS to provide a TTL function similar to what
is provided by IP. is provided by IP.
The CoS field permits LSRs to apply various scheduling packet The CoS field permits LSRs to apply various scheduling packet
disciplines to labeled packets, without requiring separate labels for disciplines to labeled packets, without requiring separate labels for
separate disciplines. separate disciplines.
This section is not intended to rule out the use of alternative 2.23.2. ATM Switches as LSRs
mechanisms in network environments where such alternatives may be
appropriate.
2.21.2. ATM Switches as LSRs
It will be noted that MPLS forwarding procedures are similar to those It will be noted that MPLS forwarding procedures are similar to those
of legacy "label swapping" switches such as ATM switches. ATM of legacy "label swapping" switches such as ATM switches. ATM
switches use the input port and the incoming VPI/VCI value as the switches use the input port and the incoming VPI/VCI value as the
index into a "cross-connect" table, from which they obtain an output index into a "cross-connect" table, from which they obtain an output
port and an outgoing VPI/VCI value. Therefore if one or more labels port and an outgoing VPI/VCI value. Therefore if one or more labels
can be encoded directly into the fields which are accessed by these can be encoded directly into the fields which are accessed by these
legacy switches, then the legacy switches can, with suitable software legacy switches, then the legacy switches can, with suitable software
upgrades, be used as LSRs. We will refer to such devices as "ATM- upgrades, be used as LSRs. We will refer to such devices as "ATM-
LSRs". LSRs".
skipping to change at page 35, line 32 skipping to change at page 38, line 29
This technique depends on the existence of a capability for This technique depends on the existence of a capability for
assigning small unique values to each ATM switch. assigning small unique values to each ATM switch.
If there are more labels on the stack than can be encoded in the ATM If there are more labels on the stack than can be encoded in the ATM
header, the ATM encodings must be combined with the generic header, the ATM encodings must be combined with the generic
encapsulation. This does presuppose that it be possible to tell, encapsulation. This does presuppose that it be possible to tell,
when reassembling the ATM cells into packets, whether the generic when reassembling the ATM cells into packets, whether the generic
encapsulation is also present. encapsulation is also present.
2.21.3. Interoperability among Encoding Techniques 2.23.3. Interoperability among Encoding Techniques
If <R1, R2, R3> is a segment of a LSP, it is possible that R1 will If <R1, R2, R3> is a segment of a LSP, it is possible that R1 will
use one encoding of the label stack when transmitting packet P to R2, use one encoding of the label stack when transmitting packet P to R2,
but R2 will use a different encoding when transmitting a packet P to but R2 will use a different encoding when transmitting a packet P to
R3. In general, the MPLS architecture supports LSPs with different R3. In general, the MPLS architecture supports LSPs with different
label stack encodings used on different hops. Therefore, when we label stack encodings used on different hops. Therefore, when we
discuss the procedures for processing a labeled packet, we speak in discuss the procedures for processing a labeled packet, we speak in
abstract terms of operating on the packet's label stack. When a abstract terms of operating on the packet's label stack. When a
labeled packet is received, the LSR must decode it to determine the labeled packet is received, the LSR must decode it to determine the
current value of the label stack, then must operate on the label current value of the label stack, then must operate on the label
skipping to change at page 36, line 15 skipping to change at page 39, line 11
Naturally there will be MPLS networks which contain a combination of Naturally there will be MPLS networks which contain a combination of
ATM switches operating as LSRs, and other LSRs which operate using an ATM switches operating as LSRs, and other LSRs which operate using an
MPLS shim header. In such networks there may be some LSRs which have MPLS shim header. In such networks there may be some LSRs which have
ATM interfaces as well as "MPLS Shim" interfaces. This is one example ATM interfaces as well as "MPLS Shim" interfaces. This is one example
of an LSR with different label stack encodings on different hops. of an LSR with different label stack encodings on different hops.
Such an LSR may swap off an ATM encoded label stack on an incoming Such an LSR may swap off an ATM encoded label stack on an incoming
interface and replace it with an MPLS shim header encoded label stack interface and replace it with an MPLS shim header encoded label stack
on the outgoing interface. on the outgoing interface.
2.22. Multicast 2.24. Multicast
This section is for further study This section is for further study
3. Some Applications of MPLS 3. Some Applications of MPLS
3.1. MPLS and Hop by Hop Routed Traffic 3.1. MPLS and Hop by Hop Routed Traffic
One use of MPLS is to simplify the process of forwarding packets One use of MPLS is to simplify the process of forwarding packets
using hop by hop routing. using hop by hop routing.
3.1.1. Labels for Address Prefixes 3.1.1. Labels for Address Prefixes
In general, router R determines the next hop for packet P by finding In general, router R determines the next hop for packet P by finding
the address prefix X in its routing table which is the longest match the address prefix X in its routing table which is the longest match
for P's destination address. That is, the packets in a given Stream for P's destination address. That is, the packets in a given stream
are just those packets which match a given address prefix in R's are just those packets which match a given address prefix in R's
routing table. In this case, a Stream can be identified with an routing table. In this case, a stream can be identified with an
address prefix. address prefix.
If packet P must traverse a sequence of routers, and at each router If packet P must traverse a sequence of routers, and at each router
in the sequence P matches the same address prefix, MPLS simplifies in the sequence P matches the same address prefix, MPLS simplifies
the forwarding process by enabling all routers but the first to avoid the forwarding process by enabling all routers but the first to avoid
executing the best match algorithm; they need only look up the label. executing the best match algorithm; they need only look up the label.
3.1.2. Distributing Labels for Address Prefixes 3.1.2. Distributing Labels for Address Prefixes
3.1.2.1. LDP Peers for a Particular Address Prefix 3.1.2.1. LDP Peers for a Particular Address Prefix
skipping to change at page 38, line 14 skipping to change at page 41, line 9
These rules ensure that labels corresponding to address prefixes These rules ensure that labels corresponding to address prefixes
which correspond to BGP routes are distributed to IGP neighbors if which correspond to BGP routes are distributed to IGP neighbors if
and only if the BGP routes are distributed into the IGP. Otherwise, and only if the BGP routes are distributed into the IGP. Otherwise,
the labels bound to BGP routes are distributed only to the other BGP the labels bound to BGP routes are distributed only to the other BGP
speakers. speakers.
These rules are intended to indicate which label mappings must be These rules are intended to indicate which label mappings must be
distributed by a given LSR to which other LSRs, NOT to indicate the distributed by a given LSR to which other LSRs, NOT to indicate the
conditions under which the distribution is to be made. That is conditions under which the distribution is to be made. That is
discussed in section 2.17. discussed in section 2.19.
3.1.3. Using the Hop by Hop path as the LSP 3.1.3. Using the Hop by Hop path as the LSP
If the hop-by-hop path that packet P needs to follow is <R1, ..., If the hop-by-hop path that packet P needs to follow is <R1, ...,
Rn>, then <R1, ..., Rn> can be an LSP as long as: Rn>, then <R1, ..., Rn> can be an LSP as long as:
1. there is a single address prefix X, such that, for all i, 1. there is a single address prefix X, such that, for all i,
1<=i<n, X is the longest match in Ri's routing table for P's 1<=i<n, X is the longest match in Ri's routing table for P's
destination address; destination address;
2. for all i, 1<i<n, Ri has assigned a label to X and distributed 2. for all i, 1<i<n, Ri has assigned a label to X and distributed
that label to R[i-1]. that label to R[i-1].
Note that a packet's LSP can extend only until it encounters a router Note that a packet's LSP can extend only until it encounters a router
whose forwarding tables have a longer best match address prefix for whose forwarding tables have a longer best match address prefix for
the packet's destination address. At that point, the LSP must end and the packet's destination address. At that point, the LSP must end and
the best match algorithm must be performed again. the best match algorithm must be performed again.
Suppose, for example, that packet P, with destination address Suppose, for example, that packet P, with destination address
10.2.153.178 needs to go from R1 to R2 to R3. Suppose also that R2 10.2.153.178 needs to go from R1 to R2 to R3. Suppose also that R2
advertises address prefix 10.2/16 to R1, but advertises 10.2.153/22, advertises address prefix 10.2/16 to R1, but R3 advertises
10.2.154/22, and 10.2/16 to R3. That is, R2 is advertising an 10.2.153/22, 10.2.154/22, and 10.2/16 to R2. That is, R2 is
"aggregated route" to R1. In this situation, packet P can be label advertising an "aggregated route" to R1. In this situation, packet P
Switched until it reaches R2, but since R2 has performed route can be label Switched until it reaches R2, but since R2 has performed
aggregation, it must execute the best match algorithm to find P's route aggregation, it must execute the best match algorithm to find
Stream. P's stream.
3.1.4. LSP Egress and LSP Proxy Egress 3.1.4. LSP Egress and LSP Proxy Egress
An LSR R is considered to be an "LSP Egress" LSR for address prefix X An LSR R is considered to be an "LSP Egress" LSR for address prefix X
if and only if one of the following conditions holds: if and only if one of the following conditions holds:
1. R1 has an address Y, such that X is the address prefix in R1's 1. R1 has an address Y, such that X is the address prefix in R1's
routing table which is the longest match for Y, or routing table which is the longest match for Y, or
2. R contains in its routing tables one or more address prefixes Y 2. R contains in its routing tables one or more address prefixes Y
such that X is a proper initial substring of Y, but R's "LSP such that X is a proper initial substring of Y, but R's "LSP
previous hops" for X do not contain any such address prefixes previous hops" for X do not contain any such address prefixes
Y; that is, R2 is a "deaggregation point" for address prefix X. Y; that is, R2 is a "deaggregation point" for address prefix X.
An LSR R1 is considered to be an "LSP Proxy Egress" LSR for address An LSR R1 is considered to be an "LSP Proxy Egress" LSR for address
prefix X if and only if: prefix X if and only if:
1. R1's next hop for X is R2 R1 and R2 are not LDP Peers with 1. R1's next hop for X is R2 R1 and R2 are not LDP Peers with
respect to X (perhaps because R2 does not support MPLS), or respect to X (perhaps because R2 does not support MPLS), or
skipping to change at page 40, line 16 skipping to change at page 43, line 10
capability to pop the label stack. Hence a POP label mapping may be capability to pop the label stack. Hence a POP label mapping may be
distributed only to LSRs which can support that function. distributed only to LSRs which can support that function.
If the penultimate LSR in an LSP for address prefix X is an LSP Proxy If the penultimate LSR in an LSP for address prefix X is an LSP Proxy
Egress, it acts just as if the LSP Egress had distributed the POP Egress, it acts just as if the LSP Egress had distributed the POP
label for X. label for X.
3.1.6. Option: Egress-Targeted Label Assignment 3.1.6. Option: Egress-Targeted Label Assignment
There are situations in which an LSP Ingress, Ri, knows that packets There are situations in which an LSP Ingress, Ri, knows that packets
of several different Streams must all follow the same LSP, of several different streams must all follow the same LSP,
terminating at, say, LSP Egress Re. In this case, proper routing can terminating at, say, LSP Egress Re. In this case, proper routing can
be achieved by using a single label can be used for all such Streams; be achieved by using a single label can be used for all such streams;
it is not necessary to have a distinct label for each Stream. If it is not necessary to have a distinct label for each stream. If
(and only if) the following conditions hold: (and only if) the following conditions hold:
1. the address of LSR Re is itself in the routing table as a "host 1. the address of LSR Re is itself in the routing table as a "host
route", and route", and
2. there is some way for Ri to determine that Re is the LSP egress 2. there is some way for Ri to determine that Re is the LSP egress
for all packets in a particular set of Streams for all packets in a particular set of streams
Then Ri may bind a single label to all FECS in the set. This is Then Ri may bind a single label to all FECS in the set. This is
known as "Egress-Targeted Label Assignment." known as "Egress-Targeted Label Assignment."
How can LSR Ri determine that an LSR Re is the LSP Egress for all How can LSR Ri determine that an LSR Re is the LSP Egress for all
packets in a particular Stream? There are a couple of possible ways: packets in a particular stream? There are a couple of possible ways:
- If the network is running a link state routing algorithm, and all - If the network is running a link state routing algorithm, and all
nodes in the area support MPLS, then the routing algorithm nodes in the area support MPLS, then the routing algorithm
provides Ri with enough information to determine the routers provides Ri with enough information to determine the routers
through which packets in that Stream must leave the routing through which packets in that stream must leave the routing
domain or area. domain or area.
- It is possible to use LDP to pass information about which address - It is possible to use LDP to pass information about which address
prefixes are "attached" to which egress LSRs. This method has prefixes are "attached" to which egress LSRs. This method has
the advantage of not depending on the presence of link state the advantage of not depending on the presence of link state
routing. routing.
If egress-targeted label assignment is used, the number of labels If egress-targeted label assignment is used, the number of labels
that need to be supported throughout the network may be greatly that need to be supported throughout the network may be greatly
reduced. This may be significant if one is using legacy switching reduced. This may be significant if one is using legacy switching
skipping to change at page 43, line 35 skipping to change at page 46, line 31
each hop along the LSP, the stack attribute value is passed each hop along the LSP, the stack attribute value is passed
unchanged, and is set by the LSP proxy egress. unchanged, and is set by the LSP proxy egress.
Thus the LSP proxy egress for X becomes an "implicit peer" with each Thus the LSP proxy egress for X becomes an "implicit peer" with each
other LSR in the routing area or domain. In this case, explicit other LSR in the routing area or domain. In this case, explicit
peering would be too unwieldy, because the number of peers would peering would be too unwieldy, because the number of peers would
become too large. become too large.
3.4. MPLS and Multi-Path Routing 3.4. MPLS and Multi-Path Routing
If an LSR supports multiple routes for a particular Stream, then it If an LSR supports multiple routes for a particular stream, then it
may assign multiple labels to the Stream, one for each route. Thus may assign multiple labels to the stream, one for each route. Thus
the reception of a second label mapping from a particular neighbor the reception of a second label mapping from a particular neighbor
for a particular address prefix should be taken as meaning that for a particular address prefix should be taken as meaning that
either label can be used to represent that address prefix. either label can be used to represent that address prefix.
If multiple label mappings for a particular address prefix are If multiple label mappings for a particular address prefix are
specified, they may have distinct attributes. specified, they may have distinct attributes.
3.5. LSPs may be Multipoint-to-Point Entities 3.5. LSP Trees as Multipoint-to-Point Entities
Consider the case of packets P1 and P2, each of which has a Consider the case of packets P1 and P2, each of which has a
destination address whose longest match, throughout a particular destination address whose longest match, throughout a particular
routing domain, is address prefix X. Suppose that the Hop-by-hop routing domain, is address prefix X. Suppose that the Hop-by-hop
path for P1 is <R1, R2, R3>, and the Hop-by-hop path for P2 is <R4, path for P1 is <R1, R2, R3>, and the Hop-by-hop path for P2 is <R4,
R2, R3>. Let's suppose that R3 binds label L3 to X, and distributes R2, R3>. Let's suppose that R3 binds label L3 to X, and distributes
this mapping to R2. R2 binds label L2 to X, and distributes this this mapping to R2. R2 binds label L2 to X, and distributes this
mapping to both R1 and R4. When R2 receives packet P1, its incoming mapping to both R1 and R4. When R2 receives packet P1, its incoming
label will be L2. R2 will overwrite L2 with L3, and send P1 to R3. label will be L2. R2 will overwrite L2 with L3, and send P1 to R3.
When R2 receives packet P2, its incoming label will also be L2. R2 When R2 receives packet P2, its incoming label will also be L2. R2
again overwrites L2 with L3, and send P2 on to R3. again overwrites L2 with L3, and send P2 on to R3.
Note then that when P1 and P2 are traveling from R2 to R3, they carry Note then that when P1 and P2 are traveling from R2 to R3, they carry
the same label, and as far as MPLS is concerned, they cannot be the same label, and as far as MPLS is concerned, they cannot be
distinguished. Thus instead of talking about two distinct LSPs, <R1, distinguished. Thus instead of talking about two distinct LSPs, <R1,
R2, R3> and <R4, R2, R3>, we might talk of a single "Multipoint-to- R2, R3> and <R4, R2, R3>, we might talk of a single "Multipoint-to-
Point LSP", which we might denote as <{R1, R4}, R2, R3>. Point LSP Tree", which we might denote as <{R1, R4}, R2, R3>.
This creates a difficulty when we attempt to use conventional ATM This creates a difficulty when we attempt to use conventional ATM
switches as LSRs. Since conventional ATM switches do not support switches as LSRs. Since conventional ATM switches do not support
multipoint-to-point connections, there must be procedures to ensure multipoint-to-point connections, there must be procedures to ensure
that each LSP is realized as a point-to-point VC. However, if ATM that each LSP is realized as a point-to-point VC. However, if ATM
switches which do support multipoint-to-point VCs are in use, then switches which do support multipoint-to-point VCs are in use, then
the LSPs can be most efficiently realized as multipoint-to-point VCs. the LSPs can be most efficiently realized as multipoint-to-point VCs.
Alternatively, if the SVP Multipoint Encoding (section 2.21) can be Alternatively, if the SVP Multipoint Encoding (section 2.23) can be
used, the LSPs can be realized as multipoint-to-point SVPs. used, the LSPs can be realized as multipoint-to-point SVPs.
3.6. LSP Tunneling between BGP Border Routers 3.6. LSP Tunneling between BGP Border Routers
Consider the case of an Autonomous System, A, which carries transit Consider the case of an Autonomous System, A, which carries transit
traffic between other Autonomous Systems. Autonomous System A will traffic between other Autonomous Systems. Autonomous System A will
have a number of BGP Border Routers, and a mesh of BGP connections have a number of BGP Border Routers, and a mesh of BGP connections
among them, over which BGP routes are distributed. In many such among them, over which BGP routes are distributed. In many such
cases, it is desirable to avoid distributing the BGP routes to cases, it is desirable to avoid distributing the BGP routes to
routers which are not BGP Border Routers. If this can be avoided, routers which are not BGP Border Routers. If this can be avoided,
skipping to change at page 47, line 5 skipping to change at page 50, line 5
distribute the mapping to its siblings. This allows the parent to distribute the mapping to its siblings. This allows the parent to
use a single label value when multicasting to all children on the use a single label value when multicasting to all children on the
LAN.) LAN.)
When a multicast labeled packet arrives, the NHLFE corresponding to When a multicast labeled packet arrives, the NHLFE corresponding to
the label indicates the set of output interfaces for that packet, as the label indicates the set of output interfaces for that packet, as
well as the outgoing label. If the same label encoding technique is well as the outgoing label. If the same label encoding technique is
used on all the outgoing interfaces, the very same packet can be sent used on all the outgoing interfaces, the very same packet can be sent
to all the children. to all the children.
4. LDP Procedures 4. LDP Procedures for Hop-by-Hop Routed Traffic
This section is FFS. 4.1. The Procedures for Advertising and Using labels
5. Security Considerations In this section, we consider only label mappings that are used for
traffic to be label switched along its hop-by-hop routed path. In
these cases, the label in question will correspond to an address
prefix in the routing table.
Security considerations are not discussed in this version of this There are a number of different procedures that may be used to
draft. distribute label mappings. One such procedure is executed by the
downstream LSR, and the others by the upstream LSR.
6. Authors' Addresses The downstream LSR must perform:
Eric C. Rosen - The Distribution Procedure, and
Cisco Systems, Inc.
250 Apollo Drive
Chelmsford, MA, 01824
E-mail: erosen@cisco.com
Arun Viswanathan - the Withdrawal Procedure.
IBM Corp.
17 Skyline Drive
Hawthorne NY 10532
914-784-3273
E-mail: arunv@vnet.ibm.com
Ross Callon The upstream LSR must perform:
Ascend Communications, Inc.
1 Robbins Road
Westford, MA 01886
508-952-7412
E-mail: rcallon@casc.com
7. References - The Request Procedure, and
[1] "A Framework for Multiprotocol Label Switching", R.Callon, - the NotAvailable Procedure, and
P.Doolan, N.Feldman, A.Fredette, G.Swallow, and A.Viswanathan, work
in progress, Internet Draft <draft-ietf-mpls-framework-01.txt>, July
1997.
[2] "ARIS: Aggregate Route-Based IP Switching", A. Viswanathan, N. - the Release Procedure, and
Feldman, R. Boivie, R. Woundy, work in progress, Internet Draft
<draft-viswanathan-aris-overview-00.txt>, March 1997.
[3] "ARIS Specification", N. Feldman, A. Viswanathan, work in - the labelUse Procedure.
progress, Internet Draft <draft-feldman-aris-spec-00.txt>, March
1997.
[4] "ARIS Support for LAN Media Switching", S. Blake, A. Ghanwani, W. The MPLS architecture supports several variants of each procedure.
Pace, V. Srinivasan, work in progress, Internet Draft <draft-blake-
aris-lan-00.txt>, March 1997.
[5] "Tag Switching Architecture - Overview", Rekhter, Davie, Katz, However, the MPLS architecture does not support all possible
Rosen, Swallow, Farinacci, work in progress, Internet Draft <draft- combinations of all possible variants. The set of supported
rekhter-tagswitch-arch-00.txt>, January, 1997. combinations will be described in section 4.2, where the
interoperability between different combinations will also be
discussed.
[6] "Tag distribution Protocol", Doolan, Davie, Katz, Rekhter, Rosen, 4.1.1. Downstream LSR: Distribution Procedure
work in progress, Internet Draft <draft-doolan-tdp-spec-01.txt>, May,
1997.
[7] "Use of Tag Switching with ATM", Davie, Doolan, Lawrence, The Distribution Procedure is used by a downstream LSR to determine
McGloghrie, Rekhter, Rosen, Swallow, work in progress, Internet Draft when it should distribute a label mapping for a particular address
<draft-davie-tag-switching-atm-01.txt>, January, 1997. prefix to its LDP peers. The architecture supports four different
distribution procedures.
[8] "Label Switching: Label Stack Encodings", Rosen, Rekhter, Tappan, Irrespective of the particular procedure that is used, if a label
Farinacci, Fedorkow, Li, work in progress, Internet Draft <draft- mapping for a particular address prefix has been distributed by a
rosen-tag-stack-02.txt>, June, 1997. downstream LSR Rd to an upstream LSR Ru, and if at any time the
attributes (as defined above) of that mapping change, then Rd must
inform Ru of the new attributes.
[9] "Partitioning Tag Space among Multicast Routers on a Common If an LSR is maintaining multiple routes to a particular address
Subnet", Farinacci, work in progress, internet draft <draft- prefix, it is a local matter as to whether that LSR maps multiple
farinacci-multicast-tag-part-00.txt>, December, 1996. labels to the address prefix (one per route), and hence distributes
multiple mappings.
[10] "Multicast Tag Binding and Distribution using PIM", Farinacci, 4.1.1.1. PushUnconditional
Rekhter, work in progress, internet draft <draft-farinacci-
multicast-tagsw-00.txt>, December, 1996.
[11] "Toshiba's Router Architecture Extensions for ATM: Overview", Let Rd be an LSR. Suppose that:
Katsube, Nagami, Esaki, RFC 2098, February, 1997.
[12] "Loop-Free Routing Using Diffusing Computations", J.J. Garcia- 1. X is an address prefix in Rd's routing table
Luna-Aceves, IEEE/ACM Transactions on Networking, Vol. 1, No. 1,
February 1993.
Appendix A Why Egress Control is Better 2. Ru is an LDP Peer of Rd with respect to X
This section is written by Arun Viswanathan. Whenever these conditions hold, Rd must map a label to X and
distribute that mapping to Ru. It is the responsibility of Rd to
keep track of the mappings which it has distributed to Ru, and to
make sure that Ru always has these mappings.
It is demonstrated here why egress control is a necessary and 4.1.1.2. PushConditional
sufficient mechanism for the LDP, and therefore is the optimal method
for setting up LSPs.
The necessary condition is established by citing counter examples Let Rd be an LSR. Suppose that:
that can be achieved *only* by egress control. It's also established
why these typical scenarios are vital requirements for a
multiprotocol LDP. The sufficiency part is established by proving
that egress control subsumes the local control.
Then finally, some discussions are made to mitigate concerns 1. X is an address prefix in Rd's routing table
expressed against not having local control. It is shown that local
control has clearly undesirable properties which may lead to severe
scalability and robustness problems. It is also shown that in having
both egress control and local control simultaneously in a network
leads to interoperability problems and how local control abrogates
the essential benefits of egress control.
A complete and self-contained case is presented here that clearly 2. Ru is an LDP Peer of Rd with respect to X
establishes that egress control is the preponderant mechanism for
LDP, and it suffices to support egress control alone as the
distribution paradigm.
A.1 Definition of an Egress 3. Rd is either an LSP Egress or an LSP Proxy Egress for X, or
Rd's L3 next hop for X is Rn, where Rn is distinct from Ru, and
Rn has bound a label to X and distributed that mapping to Rd.
A node is identified as an "egress" for a Stream, if: Then as soon as these conditions all hold, Rd should map a label to X
and distribute that mapping to Ru.
1) it's at a routing boundary for that Stream, Whereas PushUnconditional causes the distribution of label mappings
2) the next hop for that Stream is non-MPLS, for all address prefixes in the routing table, PushConditional causes
3) the Stream is directly attached or the node itself. the distribution of label mappings only for those address prefixes
for which one has received label mappings from one's LSP next hop, or
for which one does not have an MPLS-capable L3 next hop.
Nodes that satisfy conditions 1 or 2 for Streams, will by default 4.1.1.3. PulledUnconditional
start behaving as egress for those streams. Note that conditions 1
and 2 can be learned dynamically. For condition 3, nodes will not by
default act as an egress for themselves or directly attached
networks. If this condition is made the default, the LSPs setup by
egress control will create LSPs that are identical to the LSPs
created by local control.
A.2 Overview of Egress Control Let Rd be an LSR. Suppose that:
When a node is an egress for a Stream, it originates a LSP setup 1. X is an address prefix in Rd's routing table
message for that particular Stream. The setup message is sent to all
MPLS neighbors, except the next hop neighbor. Each of these messages
to the neighbors carry an appropriate label for that Stream. When a
node in a MPLS domain receives a setup message from a neighbor for a
particular Stream, it checks if that neighbor is the next hop for the
given Stream. If so, it propagates the message to all its MPLS
neighbors, except the next hop from which the message arrived. If
not, the node may keep the label provided in the setup message for
future use or negatively acknowledge the node that sent the message
to release the label assignment. But it must not forward the setup
message from the incorrect next hop to any of its neighbors. This
flooding scheme is similar in mechanism to Reverse Path Multicast.
When a next hop for a Stream changes due to change in network 2. Ru is a label distribution peer of Rd with respect to X
topology, or a new node joins the topology, the node is locally
appended to the existing LSP, without requiring egress intervention.
The node may either request the label mapping from the new next hop,
or use the previously stored (but unused) label from that next hop.
In the former case, the new next hop immediately responds with a
label mapping for that Stream if it has its own downstream mapping
for that Stream.
A.3 Why Egress Control is Necessary 3. Ru has explicitly requested that Rd map a label to X and
distribute the mapping to Ru
There are some important situations in which egress control is Then Rd should map a label to X and distribute that mapping to Ru.
necessary: Note that if X is not in Rd's routing table, or if Rd is not an LDP
peer of Ru with respect to X, then Rd must inform Ru that it cannot
provide a mapping at this time.
- Shutting off an LSP If Rd has already distributed a mapping for address prefix X to Ru,
and it receives a new request from Ru for a mapping for address
prefix X, it will map a second label, and distribute the new mapping
to Ru. The first label mapping remains in effect.
If for some reason a network administrator requires to "shut off" 4.1.1.4. PulledConditional
a LSP setup for a particular Stream, s/he can configure the
egress node for that Stream for the desired result. Note that
the requirement to shut off an LSP is a very fundamental one. If
a destination has network layer reachability but no MPLS layer
reachability (because of a problem in MPLS layer), shutting off
an LSP provides the only means to reach that destination. This
mode of operation can be used by LSRs in a network that aren't a
sink for large amounts of data. These LSRs usually require an
occasional telnet or network management traffic. It's important
to provide the capability that such nodes in a network can be
accessed through hop-by-hop connectivity avoiding the MPLS layer
optimization. The reachability is more important than
optimization in instances like this. The MPLS architecture MUST
provide this capability.
Note that this is only possible in local control when each node Let Rd be an LSR. Suppose that:
in an entire network is configured to shut off a LSP setup for a
particular Stream. Such is neither desirable nor scalable.
- Egress Aggregation 1. X is an address prefix in Rd's routing table
In some networks, due to the absence of routing summarization, 2. Ru is a label distribution peer of Rd with respect to X
aggregation may not be possible through routing information.
However, with Egress control, it is possible to aggregate *all*
Streams that exit the network through a common egress node with a
single LSP. This is achieved easily because the egress simply
can use the same label for all Streams.
Such is simply not possible with the Local control; with local 3. Ru has explicitly requested that Rd map a label to X and
knowledge LSRs cannot map several Streams to a single label distribute the mapping to Ru
because it is unknown if Streams will diverge at some subsequent
downstream node.
The egress aggregation works for both distance vector protocols 4. Rd is either an LSP Egress or an LSP Proxy Egress for X, or
and link state protocols; it is protocol independent. Note that Rd's L3 next hop for X is Rn, where Rn is distinct from Ru, and
when using VP switching in conjunction with some distance vector Rn has bound a label to X and distributed that mapping to Rd,
protocols it becomes very essential that such aggregation be or
possible, as there are many vendor switches that don't have VC
merging capability, and have limited VP switching capability.
The egress control provides such vendors with a level-playing
field to compete with MPLS products. Moreover, this capability
can be very useful in enterprise networks; where several legacy
LANs at a site can be aggregated to the egress LSR at that site.
Furthermore, this approach can drastically reduce signalling and
LSP state maintenance overheads in the entire network.
- Loop Prevention Then as soon as these conditions all hold, Rd should map a label to X
and distribute that mapping to Ru. Note that if X is not in Rd's
routing table, or if Rd is not a label distribution peer of Ru with
respect to X, then Rd must inform Ru that it cannot provide a mapping
at this time.
The loop-prevention mechanism only works from the egress node for However, if the only condition that fails to hold is that Rn has not
multipoint-to-point LSPs, since the loop prevention mechanism yet provided a label to Rd, then Rd must defer any response to Ru
requires the list of LSR nodes through which the setup message until such time as it has receiving a mapping from Rn.
has already traversed in order to identify and prevent LSP loops.
A loop prevention scheme is not possible through local control. If Rd has distributed a label mapping for address prefix X to Ru, and
at some later time, any attribute of the label mapping changes, then
Rd must redistribute the label mapping to Ru, with the new attribute.
It must do this even though Ru does not issue a new Request.
- De-aggregation In section 4.2, we will discuss how to choose the particular
procedure to be used at any given time, and how to ensure
interoperability among LSRs that choose different procedures.
Egress control provides the capability to de-aggregate one or 4.1.2. Upstream LSR: Request Procedure
more Streams from an aggregated Stream. For example, if a
network is aggregating all CIDRs of an EBGP node into a single
LSP, with egress control, a specific CIDR from this bundle can be
given its own dedicated LSP. This enables one to apply special
policies to specific CIDRs when required.
In the local control this can be achieved only by configuring The Request Procedure is used by the upstream LSR for an address
every node in the network with specific de-aggregation prefix to determine when to explicitly request that the downstream
information and the associated policy. This approach can lead LSR map a label to that prefix and distribute the mapping. There are
severe scalability problems. three possible procedures that can be used.
- Unique Labels 4.1.2.1. RequestNever
As is known, when using VP merging, all ingresses must have Never make a request. This is useful if the downstream LSR uses the
unique VCI values to prevent cell interleaving. With egress PushConditional procedure or the PushUnconditional procedure, but is
control, it is possible to distribute unique VCI values to the not useful if the downstream LSR uses the PulledUnconditional
ingress nodes, avoiding the need to configure each ingress node. procedure or the the Pulledconditional procedures.
The egress node can pick a unique VCI for each ingress node.
Another benefit of egress control is that each egress can be
configured with a unique label value in the case of egress
aggregation (as described above). Since the label value is
unique, the same label value can be used on all the segments of a
LSP. This enables one to identify anywhere in a network each LSP
that is associated with a certain egress node, thus easing
network debugging.
This again, is not possible in the local control because of the 4.1.2.2. RequestWhenNeeded
lack of a single coordinating node.
A.4 Examples that work better through egress control Make a request whenever the L3 next hop to the address prefix
changes, and one doesn't already have a label mapping from that next
hop for the given address prefix.
Local control needs to propagate attributes that come from the 4.1.2.3. RequestOnRequest
downstream node to all upstream nodes. This behavior itself can be
LIKENED to the egress control. Nevertheless, the local control can
achieve these only in a severely inefficient manner. Since each node
only knows of local information, it creates and distributes an LSP
with incorrect attributes. As each node learns of new downstream
attributes, a correction is made as the attributes are propagated
upstream again. This can lead to a worst case of O(n-squared) setup
messages to create a single LSP, where n is the number of nodes in a
LSP.
In the egress control, the attribute distribution is achieved during Issue a request whenever a request is received, in addition to
initial LSP setup, with a single message from the egress to issuing a request when needed (as described in section 4.1.2.2). If
ingresses. Rd receives such a request from Ru, for an address prefix for which
Rd has already distributed Ru a label, Rd shall assign a new
(distinct) label, map it to X, and distribute that mapping. (Whether
Rd can distribute this mapping to Ru immediately or not depends on
the Distribution Procedure being used.)
- TTL/Traceroute This procedure is useful when the LSRs are implemented on
conventional ATM switching hardware.
The ingress requires a proper LSP hop-count value to decrement 4.1.3. Upstream LSR: NotAvailable Procedure
TTL in packets that use a particular LSP, in environments such as
ATM which do not have a TTL equivalent. This simulates the TTL
decrement which exists in an IP network, and also enables scoping
utilities, such as traceroute, to work as they do today in IP
networks. In egress control, the LSP hop-count is known at the
ingress as a by-product of the LSP setup message, since an LSP
setup message traverses from egress to ingress, and increments
the hop-count at each node along the path.
- MTU If Ru and Rd are respectively upstream and downstream label
distribution peers for address prefix X, and Rd is Ru's L3 next hop
for X, and Ru requests a mapping for X from Rd, but Rd replies that
it cannot provide a mapping at this time, then the NotAvailable
procedure determines how Ru responds. There are two possible
procedures governing Ru's behavior:
When the MTU at the egress node is smaller than the MTU at some 4.1.3.1. RequestRetry
of the ingress nodes, packets originated at those ingress nodes
will be dropped when they reach the egress node. Hosts not using
MTU discovery have no means to recover from this. However,
similar to the hop-count, the minimum LSP MTU can be propagated
to the ingresses via egress control LSP setup messages, enabling
the ingress to do fragmentation when required.
- Implicit Peering Ru should issue the request again at a later time. That is, the
requester is responsible for trying again later to obtain the needed
mapping.
Implicit peering is the mechanism through which higher level 4.1.3.2. RequestNoRetry
stack labels are communicated to the ingress nodes. These label
values are piggybacked in the LSP setup messages. This works
best with egress control; when the egress creates the setup
message, it can piggyback the stack labels at the same time.
- ToS/COS Based LSPs Ru should never reissue the request, instead assuming that Rd will
provide the mapping automatically when it is available. This is
useful if Rd uses the PushUnconditional procedure or the
PushConditional procedure.
When certain LSPs require higher or lower precedence or priority 4.1.4. Upstream LSR: Release Procedure
through a network, the single egress node for that LSP can be
configured with the required priority and this can be
communicated in the egress control LSP setup message. In the
local control, each and every node in the network must be
configured per LSP to achieve the same result.
The local control initially distributes labels to its neighbors Suppose that Rd is an LSR which has bound a label to address prefix
willy-nilly, and then waits for attributes to come through egress X, and has distributed that mapping to LSR Ru. If Rd does not happen
control. Thus, local control is completely dependent on egress to be Ru's L3 next hop for address prefix X, or has ceased to be Ru's
control to provide complete functional operation to LSPs. Otherwise, L3 next hop for address prefix X, then Rd will not be using the
local control requires that attributes be configured through the label. The Release Procedure determines how Ru acts in this case.
entire network for each Stream. This is the most compelling argument There are two possible procedures governing Ru's behavior:
that local control is *not sufficient*; or conversely, egress control
is necessary. This demonstrates egress control subsumes the local
control. Moreover, distribution of labels without associated
attributes may not be appropriate and may lead to undesired results.
A.5 Egress Control is Sufficient 4.1.4.1. ReleaseOnChange
The argument for sufficiency is proved by demonstrating that required Ru should release the mapping, and inform Rd that it has done so.
LSPs can be created with egress control, and this is not the case
with local control.
The egress control can create an LSP for every route entry made by 4.1.4.2. NoReleaseOnChange
the routing protocols:
1. A route can be learned from another routing domain, in which Ru should maintain the mapping, so that it can use it again
case the LSR at the routing domain will act as an egress for immediately if Rd later becomes Ru's L3 next hop for X.
the route and originate an LSP setup for that route.
2. A route can be a locally attached network or the LSR itself may 4.1.5. Upstream LSR: labelUse Procedure
be a host route. In this case, the LSR to which such a route
is attached originates an LSP setup message.
3. An LSR with a non-MPLS next-hop behaves as an egress for all Suppose Ru is an LSR which has received label mapping L for address
those route whose next-hop is the non-MPLS neighbor. prefix X from LSR Rd, and Ru is upstream of Rd with respect to X, and
in fact Rd is Ru's L3 next hop for X.
These three above methods can create an LSP for each route entry in a Ru will make use of the mapping if Rd is Ru's L3 next hop for X. If,
network. Moreover, policy specific LSPs, as described previously, at the time the mapping is received by Ru, Rd is NOT Ru's L3 next hop
can *only* be achieved with egress control. Thus, egress control is for X, Ru does not make any use of the mapping at that time. Ru may
necessary and sufficient for creating LSPs. QED. however start using the mapping at some later time, if Rd becomes
Ru's L3 next hop for X.
A.6 Discussions The labelUse Procedure determines just how Ru makes use of Rd's
mapping.
A.6.1 Is Local control faster than Egress control? There are three procedures which Ru may use:
During topology changes, such as links going down, coming up, change 4.1.5.1. UseImmediate
in link cost, etc, there is no difference in setup latency between
Egress Control and Local control. This is due to the fact that the
node (Ru) which undergoes a change in next-hop for a Stream
immediately requests a label assignment from the new next hop node
(Rd). The new next hop node then immediately supplies the label
mapping for the requested Stream. As explained in the Egress Control
Method section, the node Ru may already have stored label assignments
from the node Rd, in which case node Ru can immediately splice itself
to the multipoint-to-point tree. Hence, new nodes are spliced into
existing LSPs locally. In the scenario where a network initially
learns of a new route, although the Local control may setup LSPs
faster than the Egress control, this difference in latency has no
perceived advantage. Since routing itself may take several seconds
to propagate and converge on the new route information, the potential
latency of egress control is small as compared to the routing
protocol propagation time, and the initial setup time at route
propagation time is unimportant since these are long lived LSPs.
Moreover, the hurried distribution of labels in local control may not Ru may put the mapping into use immediately. At any time when Ru has
carry much meaning because: a mapping for X from Rd, and Rd is Ru's L3 next hop for X, Rd will
also be Ru's LSP next hop for X.
4. The associated attributes are not applied or propagated to the 4.1.5.2. UseIfLoopFree
ingress.
5. While the ingress may believe it has an LSP, in reality the Ru will use the mapping only if it determines that by doing so, it
packets may be blackholed in the middle of the network if the will not cause a forwarding loop.
full LSP is not established.
6. Policy based LSPs, which can only be achieved via egress If Ru has a mapping for X from Rd, and Rd is (or becomes) Ru's L3
control as described above, may undo an un-used label next hop for X, but Rd is NOT Ru's current LSP next hop for X, Ru
assignment established by local control. does NOT immediately make Rd its LSP next hop. Rather, it initiates
a loop prevention algorithm. If, upon the completion of this
algorithm, Rd is still the L3 next hop for X, Ru will make Rd the LSP
next hop for X, and use L as the outgoing label.
A.6.2 Scalability and Robustness The loop prevention algorithm to be used is still under
consideration.
It has been alleged that the egress control does not have the 4.1.5.3. UseIfLoopNotDetected
scalability and robustness properties required by distributed
processing. However, the egress uses a root distribution paradigm
commonly used by many other standard routing protocols. For example,
in the case of OSPF, LSAs are flooded through a domain originating at
the "egress", where the difference being that the flooding in the
case of OSPF is contained through a sequence number and in the Egress
control it is contained by the next hop validation. In the case of
PIM (and some other multicast protocols), the distribution mechanism
is in fact exactly similar. Even in BGP with route reflection,
updates originate at the root and traverse a tree structure to reach
the peers, as opposed to a n-square mesh. The commonality is the
distribution paradigm, in which the distribution originates at the
root of a tree and traverses the branches till it reaches all the
leaves. None of the above mentioned protocols have scalability or
robustness problems because of the distribution paradigm.
The ONLY concern expressed against to counter Egress control is that This procedure is the same as UseImmediate, unless Ru has detected a
if the setup message does not propagate upstream from a certain node, loop in the LSP. If a loop has been detected, Ru will discard
then the sub-tree upstream of that node will not be added into the packets that would otherwise have been labeled with L and sent to Rd.
LSP. It's a reasonable concern, but further analysis shows that it's
not a realistic problem. The impact of this problem compared to the
impact of a similar problem in local control are exactly the same
when LSRs employed in a MPLS domain have little or no forwarding
capabilities (for example, ATM LSRs), since in both cases, packets
are blackholed. In fact, in the egress control the packets for
afflicted LSPs will be dropped right at the ingress, while with local
control the packets will be dropped at the point of breakage, causing
packets to unnecessarily traverse part way through the network. When
reasonable forwarding capability exists in the MPLS domain, with the
egress control the packets may be forwarded hop-by-hop till the point
where the LSP setup ended. Whereas in case of local control, the
packets will label switched till the point of breakage and hop-by-hop
forwarded till the LSP segment resumes. Since egress control has
advantages when there is no forwarding capability, and local control
is has advantages when there is forwarding capability, there is an
equal tradeoff between them, and thus, neither is superior or
inferior in this regard. This latter case is simply a loss in
optimization, since the network has reasonable forwarding
capabilities. Hence the robustness issue is not a problem in either
types of networks. As mentioned before, the local control is
dependent on egress control for distributing attributes. The
attribute distribution could then also face the same problem of
stalled propagation, which would lead to erroneous LSP setup. So,
the local control can also be seen as afflicted with this problem, if
it exists.
Moreover, if stalled propagation were truly a problem, there are This will continue until the next hop for X changes, or until the
other schemes in MPLS that would face the same issue. For example, loop is no longer detected.
the label distribution through PIM, Explicit Route setup, and RSVP
would also not work, and therefore should be withdrawn :-).
Note that exhaustion of label space cannot stall the propagation of 4.1.6. Downstream LSR: Withdraw Procedure
messages to the upstream nodes. Appropriate indications can be given
to the upstream nodes in the setup message that no label allocation
was made because of exhaustion of label space, so that correct action
can be taken at the upstream nodes, and yet the LSP setup would
continue.
A.6.3 Conclusion In this case, there is only a single procedure.
The attempt here is not to deride the local control, but since one When LSR Rd decides to break the mapping between label L and address
method subsumes the features and properties of the other, then why prefix X, then this unmapping must be distributed to all LSRs to
support both and complicate implementation, interoperability and which the mapping was distributed.
maintenance? In fact RFC1925 says, "In protocol design, perfection
has been reached not when there is nothing left to add, but when
there is nothing left to take away". A usual diplomatic resolution
for such controversy is to make accommodations for both. We feel
that it's a poor choice of architecture to support both. That is why
we feel strongly that this must be evaluated by the MPLS WG.
In a way, controlling the network behavior as to which LSP are It is desirable, though not required, that the unmapping of L from X
formed, which Streams map to which LSPs, and the associated be distributed by Rd to a LSR Ru before Rd distributes to Ru any new
attributes, can be compared to applying policies at the edges of an mapping of L to any other address prefix Y, where X != Y. If Ru
AS. This is precisely what the egress control provides, a rich and learns of the new mapping of L to Y before it learns of the unmapping
varied policy control at the egress node of LSPs. of L from X, and if packets matching both X and Y are forwarded by Ru
to Rd, then for a period of time, Ru will label both packets matching
X and packets matching Y with label L.
Appendix B Why Local Control is Better The distribution and withdrawal of label mappings is done via a label
distribution protocol, or LDP. LDP is a two-party protocol. If LSR R1
has received label mappings from LSR R2 via an instance of an LDP,
and that instance of that protocol is closed by either end (whether
as a result of failure or as a matter of normal operation), then all
mappings learned over that instance of the protocol must be
considered to have been withdrawn.
This section is written by Eric Rosen. As long as the relevant LDP connection remains open, label mappings
that are withdrawn must always be withdrawn explicitly. If a second
label is bound to an address prefix, the result is not to implicitly
withdraw the first label, but to map both labels; this is needed to
support multi-path routing. If a second address prefix is bound to a
label, the result is not to implicitly withdraw the mapping of that
label to the first address prefix, but to use that label for both
address prefixes.
The remaining area of dispute between advocates of "local control" 4.2. MPLS Schemes: Supported Combinations of Procedures
and advocates of "egress control" is relatively small. In
particular, there is agreement on the following points:
1. If LSR R1's next hop for address prefix X is LSR R2, and R2 is Consider two LSRs, Ru and Rd, which are label distribution peers with
in a different area or in a different routing domain than R1, respect to some set of address prefixes, where Ru is the upstream
then R1 may assign and distribute a label for X, even if R2 has peer and Rd is the downstream peer.
not done so.
This means that even under egress control, the border routers The MPLS scheme which governs the interaction of Ru and Rd can be
in one autonomous system do not have to wait, before described as a quintuple of procedures: <Distribution Procedure,
distributing labels, for any downstream routers which are in Request Procedure, NotAvailable Procedure, Release Procedure,
other autonomous systems. labelUse Procedure>. (Since there is only one Withdraw Procedure, it
need not be mentioned.) A "*" appearing in one of the positions is a
wild-card, meaning that any procedure in that category may be
present; an "N/A" appearing in a particular position indicates that
no procedure in that category is needed.
2. If LSR R1's next hop for address prefix X is LSR R2, but R1 Only the MPLS schemes which are specified below are supported by the
receives a label mapping for X from LSR R3, then R1 may MPLS Architecture. Other schemes may be added in the future, if a
remember R3's mapping. If, at some later time, R3 becomes R1's need for them is shown.
next hop for S, then (if R1 is not using loop prevention) R1
may immediately begin using R3 as the LSP next hop for S, using
the remembered mapping from R3.
3. Attributes which are passed upstream from the egress may change 4.2.1. TTL-capable LSP Segments
over time, as a result of reconfiguration of the egress, or of
other events. This means that even if egress control is used,
LSRs must be able to accept attribute changes on existing LSPs;
attributes are not fixed when the LSP is first constructed, nor
does a change in attributes require a new LSP to be
constructed.
The dispute is centered on the situation in which the following If Ru and Rd are MPLS peers, and both are capable of decrementing a
conditions hold: TTL field in the MPLS header, then the MPLS scheme in use between Ru
and Rd must be one of the following:
- LSR R1's next hop for address prefix X is within the same <PushUnconditional, RequestNever, N/A, NoReleaseOnChange,
administrative domain as R1, and UseImmediate>
- R1's next hop for X has not distributed to R1 a label for X, and <PushConditional, RequestWhenNeeded, RequestNoRetry, *, *>
- R1 has not yet distributed to its neighbors any labels for X. The former, roughly speaking, is "local control with downstream label
assignment". The latter is an egress control scheme.
With local control, R1 is permitted to distribute a label for X to 4.2.2. Using ATM Switches as LSRs
its neighbors; with egress control it is not.
From an implementation perspective, the difference then between The procedures for using ATM switches as LSRs depends on whether the
egress control and local control is relatively small. Egress control ATM switches can realize LSP trees as multipoint-to-point VCs or VPs.
simply creates an additional state in the label distribution process,
and prohibits label distribution in that state.
From the perspective of network behavior, however, this difference is Most ATM switches existing today do NOT have a multipoint-to-point
a bit more significant: VC-switching capability. Their cross-connect tables could easily be
programmed to move cells from multiple incoming VCs to a single
outgoing VC, but the result would be that cells from different
packets get interleaved.
- Egress control adds latency to the initial construction of an Some ATM switches do support a multipoint-to-point VC-switching
LSP, because the path must be set up serially, node by node from capability. These switches will queue up all the incoming cells from
the egress. With local control, all LSRs along the path may an incoming VC until a packet boundary is reached. Then they will
perform their setup activities in parallel. transmit the entire sequence of cells on the outgoing VC, without
allowing cells from any other packet to be interleaved.
- Egress control adds additional interdependencies among nodes, as Many ATM switches do support a multipoint-to-point VP-switching
there is something that one node cannot do until some other node capability, which can be used if the Multipoint SVP label encoding is
does something else first, which it cannot do until some other used.
node does something first, etc. This is problematical for a
number of reasons.
* In robust system design, one tries to avoid such 4.2.2.1. Without Multipoint-to-point Capability
interdependencies, since they always bring along robustness
and scalability problems.
* In some situations, it is advantageous for a node to use Suppose that R1, R2, R3, and R4 are ATM switches which do not support
MPLS, even if some node downstream is not functioning multipoint-to-point capability, but are being used as LSRs. Suppose
properly and hence not assigning labels as it should. further that the L3 hop-by-hop path for address prefix X is <R1, R2,
R3, R4>, and that packets destined for X can enter the network at any
of these LSRs. Since there is no multipoint-to-point capability, the
LSPs must be realized as point-to-point VCs, which means that there
needs to be three such VCs for address prefix X: <R1, R2, R3, R4>,
<R2, R3, R4>, and <R3, R4>.
These disadvantages might be tolerable if there is some significant Therefore, if R1 and R2 are MPLS peers, and either is an LSR which is
problem which can be solved by egress control, but not by local implemented using conventional ATM switching hardware (i.e., no cell
control. So it is worth looking to see if there is such a problem. interleave suppression), the MPLS scheme in use between R1 and R2
must be one of the following:
There are a number of situations in which it may be desirable for an <PulledUnconditional, RequestOnRequest, RequestRetry,
LSP Ingress node to know certain attributes of the LSP, e.g., the ReleaseOnChange, UseImmediate>
number of hops in the LSP. It is sometimes claimed that obtaining
such information requires the use of egress control. However, this
is not true. Any attribute of an LSP is liable to change after the
LSP exists. Procedures to detect and communicate the change must
exist. These procedures CANNOT be tied to the initial construction
of the LSP, since they must execute after the LSP has already been
constructed. The ability to pass control information upstream along
a path towards an ingress node does not presuppose anything about the
procedures used to construct the path.
The fundamental issue separating the advocates of egress control from <PulledConditional, RequestOnRequest, RequestNoRetry,
the advocates of local control is really a network management issue. ReleaseOnChange, *>
To advocates of egress control, setting up an LSP for a particular
address prefix is analogous to setting up a PVC in an ATM network.
When setting up a PVC, one goes to one of the PVC endpoints and
enters certain configuration information. Similarly, one might think
that to set up an LSP for a particular address prefix, one goes to
the LSR which is the egress for that address prefix, and enters
configuration information. This allows the network administrator
complete control of which address prefixes are assigned LSPs and
which are not. And if this is one's management model, egress control
does simplify the configuration issues.
On the other hand, if one's model is that the LSPs get set up The use of the RequestOnRequest procedure will cause R4 to distribute
automatically by the network, as a result of the operation of the three labels for X to R3; R3 will distribute 2 labels for X to R2,
routing algorithm, then egress control is of no utility at all. When and R2 will distribute one label for X to R1.
one hears the claim that "egress control allow you to control your
network from a few nodes", what is really being claimed is "egress
control simplifies the job of manually configuring all the LSPs in
your network". Of course, if you don't intend to manually configure
all the LSPs in your network, this is irrelevant.
So before an egress control scheme is adopted, one should ask whether The first of these procedures is the "optimistic downstream-on-
complete manual configuration of the set of address prefixes which demand" variant of local control. The second is the "conservative
get assigned LSPs is necessary. That is, is this capability needed downstream-on-demand" variant of local control.
to solve a real problem?
It is sometimes claimed that egress control is needed if one wants to An egress control scheme which works in the absence of multipoint-
conserve labels by assigning a single label to all address prefixes to-point capability is for further study.
which have the same egress. This is not true. If the network is
running a link state routing algorithm, each LSR already knows which
address prefixes have a common egress, and hence can assign a common
label. If the network is running a distance vector routing protocol,
information about which address prefixes have a common egress can be
made to "bubble up" from the egress, using LDP, even if local control
is used.
It is only in the case where the number of available labels is so 4.2.2.2. With Multipoint-To-Point Capability
small that their use must be manually administered that egress
control has an advantage. It may be arguable that egress control If R1 and R2 are MPLS peers, and either of them is an LSR which is
should be an option that can be used for the special cases in which implemented using ATM switching hardware with cell interleave
it provides value. In most cases, there is no reason to have it at suppression, and neither is an LSR which is implemented using ATM
all. switching hardware that does not have cell interleave suppression,
then the MPLS scheme in use between R1 and R2 must be one of the
following;
<PushConditional, RequestWhenNeeded, RequestNoRetry, *, *>
<PushUnconditional, RequestNever, N/A, NoReleaseOnChange,
UseImmediate>
<PulledConditional, RequestOnRequest, RequestNoRetry,
ReleaseOnChange, *>
The first of these is an egress control scheme. The second is is the
"downstream" variant of local control. The third is the
"conservative downstream-on-demand" variant of local control.
4.2.3. Interoperability Considerations
It is easy to see that certain quintuples do NOT yield viable MPLS
schemes. For example:
- <PulledUnconditional, RequestNever, *, *, *>
<PulledConditional, RequestNever, *, *, *>
In these MPLS schemes, the downstream LSR Rd distributes label
mappings to upstream LSR Ru only upon request from Ru, but Ru
never makes any such requests. Obviously, these schemes are not
viable, since they will not result in the proper distribution of
label mappings.
- <*, RequestNever, *, *, ReleaseOnChange>
In these MPLS schemes, Rd releases mappings when it isn't using
them, but it never asks for them again, even if it later has a
need for them. These schemes thus do not ensure that label
mappings get properly distributed.
In this section, we specify rules to prevent a pair of LDP peers from
adopting procedures which lead to infeasible MPLS Schemes. These
rules require the exchange of information between LDP peers during
the initialization of the LDP connection between them.
1. Each must state whether it is an ATM switch, and if so, whether
it has cell interleave suppression.
2. If Rd is an ATM switch without cell interleave suppression, it
must state whether it intends to use the PulledUnconditional
procedure or the Pulledconditional procedure. If the former,
Ru MUST use the RequestRetry procedure; if the latter, Ru MUST
use the RequestNoRetry procedure.
3. If Ru is an ATM switch without cell interleave suppression, it
must state whether it intends to use the RequestRetry or the
RequestNoRetry procedure. If Rd is an ATM switch without cell
interleave suppression, Rd is not bound by this, and in fact Ru
MUST adopt Rd's preferences. However, if Rd is NOT an ATM
switch without cell interleave suppression, then if Ru chooses
RequestRetry, Rd must use PulledUnconditional, and if Ru
chooses RequestNoRetry, Rd MUST use PulledConditional.
4. If Rd is an ATM switch with cell interleave suppression, it
must specify whether it prefers to use PushConditional,
PushUnconditional, or PulledConditional. If Ru is not an ATM
switch without cell interleave suppression, it must then use
RequestWhenNeeded and RequestNoRetry, or else RequestNever and
NoReleaseOnChange, respectively.
5. If Ru is an ATM switch with cell interleave suppression, it
must specify whether it prefers to use RequestWhenNeeded and
RequestNoRetry, or else RequestNever and NoReleaseOnChange. If
Rd is NOT an ATM switch with cell interleave suppression, it
must then use either PushConditional or PushUnconditional,
respectively.
4.2.4. How to do Loop Prevention
TBD
4.2.5. How to do Loop Detection
TBD.
4.2.6. Security Considerations
Security considerations are not discussed in this version of this
draft.
5. Authors' Addresses
Eric C. Rosen
Cisco Systems, Inc.
250 Apollo Drive
Chelmsford, MA, 01824
E-mail: erosen@cisco.com
Arun Viswanathan
Lucent Technologies
101 Crawford Corner Rd., #4D-537
Holmdel, NJ 07733
732-332-5163
E-mail: arunv@dnrc.bell-labs.com
Ross Callon
IronBridge Networks
55 Hayden Avenue,
Lexington, MA 02173
+1-781-402-8017
E-mail: rcallon@ironbridgenetworks.com
6. References
[1] "A Framework for Multiprotocol Label Switching", R.Callon,
P.Doolan, N.Feldman, A.Fredette, G.Swallow, and A.Viswanathan, work
in progress, Internet Draft <draft-ietf-mpls-framework-02.txt>,
November 1997.
[2] "ARIS: Aggregate Route-Based IP Switching", A. Viswanathan, N.
Feldman, R. Boivie, R. Woundy, work in progress, Internet Draft
<draft-viswanathan-aris-overview-00.txt>, March 1997.
[3] "ARIS Specification", N. Feldman, A. Viswanathan, work in
progress, Internet Draft <draft-feldman-aris-spec-00.txt>, March
1997.
[4] "Tag Switching Architecture - Overview", Rekhter, Davie, Katz,
Rosen, Swallow, Farinacci, work in progress, Internet Draft <draft-
rekhter-tagswitch-arch-00.txt>, January, 1997.
[5] "Tag distribution Protocol", Doolan, Davie, Katz, Rekhter, Rosen,
work in progress, Internet Draft <draft-doolan-tdp-spec-01.txt>, May,
1997.
[6] "Use of Tag Switching with ATM", Davie, Doolan, Lawrence,
McGloghrie, Rekhter, Rosen, Swallow, work in progress, Internet Draft
<draft-davie-tag-switching-atm-01.txt>, January, 1997.
[7] "Label Switching: Label Stack Encodings", Rosen, Rekhter, Tappan,
Farinacci, Fedorkow, Li, Conta, work in progress, Internet Draft
<draft-ietf-mpls-label-encaps-01.txt>, February, 1998.
[8] "Partitioning Tag Space among Multicast Routers on a Common
Subnet", Farinacci, work in progress, internet draft <draft-
farinacci-multicast-tag-part-00.txt>, December, 1996.
[9] "Multicast Tag Binding and Distribution using PIM", Farinacci,
Rekhter, work in progress, internet draft <draft-farinacci-
multicast-tagsw-00.txt>, December, 1996.
[10] "Toshiba's Router Architecture Extensions for ATM: Overview",
Katsube, Nagami, Esaki, RFC 2098, February, 1997.
[11] "Loop-Free Routing Using Diffusing Computations", J.J. Garcia-
Luna-Aceves, IEEE/ACM Transactions on Networking, Vol. 1, No. 1,
February 1993.
 End of changes. 

This html diff was produced by rfcdiff 1.23, available from http://www.levkowetz.com/ietf/tools/rfcdiff/