Internet Draft
Network Working Group                                      Loa Andersson
Internet Draft                                      Nortel Networks Inc.
Expiration Date: November 1999
                                                             Paul Doolan
                                                       Ennovate Networks

                                                           Nancy Feldman
                                                                IBM Corp

                                                          Andre Fredette
                                                    Nortel Networks Inc.

                                                              Bob Thomas
                                                     Cisco Systems, Inc.

                                                                May 1999

                           LDP Specification

                       draft-ietf-mpls-ldp-04.txt

Status of this Memo

   This document is an Internet-Draft and is in full conformance with
   all provisions of Section 10 of RFC2026.

   Internet-Drafts are working documents of the Internet Engineering
   Task Force (IETF), its areas, and its working groups.  Note that
   other groups may also distribute working documents as Internet-
   Drafts.

   Internet-Drafts are draft documents valid for a maximum of six months
   and may be updated, replaced, or obsoleted by other documents at any
   time.  It is inappropriate to use Internet-Drafts as reference
   material or to cite them other than as "work in progress."

   The list of current Internet-Drafts can be accessed at
   http://www.ietf.org/ietf/1id-abstracts.txt

   The list of Internet-Draft Shadow Directories can be accessed at
   http://www.ietf.org/shadow.html.

   To view the list Internet-Draft Shadow Directories, see
   http://www.ietf.org/shadow.html.

Abstract

   An overview of Multi Protocol Label Switching (MPLS) is provided in
   [FRAMEWORK] and a proposed architecture in [ARCH].  A fundamental
   concept in MPLS is that two Label Switching Routers (LSRs) must agree
   on the meaning of the labels used to forward traffic between and

Andersson, et al.                                               [Page 1]

Internet Draft         draft-ietf-mpls-ldp-04.txt               May 1999

   through them.  This common understanding is achieved by using a set
   of procedures, called a label distribution protocol, by which one LSR
   informs another of label bindins it has made.  This document defines
   a set of such procedures called LDP (for Label Distribution
   Protocol).

Changes from Previous Draft

     - This draft addresses issues raised during the LDP last call held
       February 8, 1999 through February 24, 1999.

Open Issues

   The following LDP issues are left unresolved with this version of the
   spec:

     - LDP support for CoS is not specified in this version.  CoS
       support may be addressed in a future version.

     - LDP support for multicast is not specified in this version.
       Multicast support will be addressed in a future version.

     - LDP support for multipath label switching is not specified in
       this version.  Multipath support will be addressed in a future
       version.

Andersson, et al.                                               [Page 2]

Internet Draft         draft-ietf-mpls-ldp-04.txt               May 1999

Table of Contents

    1          LDP Overview  .......................................   6
    1.1        LDP Peers  ..........................................   6
    1.2        LDP Message Exchange  ...............................   7
    1.3        LDP Message Structure  ..............................   7
    1.4        LDP Error Handling  .................................   8
    1.5        LDP Extensibility and Future Compatibility  .........   8
    2          LDP Operation  ......................................   8
    2.1        FECs  ...............................................   8
    2.2        Label Spaces, Identifiers, Sessions and Transport  ..  10
    2.2.1      Label Spaces  .......................................  10
    2.2.2      LDP Identifiers  ....................................  11
    2.2.3      LDP Sessions  .......................................  11
    2.2.4      LDP Transport  ......................................  11
    2.3        LDP Sessions between non-Directly Connected LSRs  ...  12
    2.4        LDP Discovery   .....................................  12
    2.4.1      Basic Discovery Mechanism  ..........................  12
    2.4.2      Extended Discovery Mechanism  .......................  13
    2.5        Establishing and Maintaining LDP Sessions  ..........  14
    2.5.1      LDP Session Establishment  ..........................  14
    2.5.2      Transport Connection Establishment  .................  14
    2.5.3      Session Initialization  .............................  15
    2.5.4      Initialization State Machine  .......................  17
    2.5.5      Maintaining Hello Adjacencies  ......................  20
    2.5.6      Maintaining LDP Sessions  ...........................  20
    2.6        Label Distribution and Management  ..................  21
    2.6.1      Label Distribution Control Mode  ....................  21
    2.6.1.1    Independent Label Distribution Control  .............  21
    2.6.1.2    Ordered Label Distribution Control  .................  21
    2.6.2      Label Retention Mode  ...............................  22
    2.6.2.1    Conservative Label Retention Mode  ..................  22
    2.6.2.2    Liberal Label Retention Mode  .......................  22
    2.6.3      Label Advertisement Mode  ...........................  23
    2.7        LDP Identifiers and Next Hop Addresses  .............  23
    2.8        Loop Detection  .....................................  24
    2.8.1      Label Request Message  ..............................  25
    2.8.2      Label Mapping Message  ..............................  26
    2.8.3      Discussion  .........................................  28
    2.9        Label Distribution for Explicitly Routed LSPs  ......  28
    3          Protocol Specification  .............................  29
    3.1        LDP PDUs  ...........................................  29
    3.2        LDP Procedures  .....................................  30
    3.3        Type-Length-Value Encoding  .........................  30
    3.4        TLV Encodings for Commonly Used Parameters  .........  32
    3.4.1      FEC TLV  ............................................  32

Andersson, et al.                                               [Page 3]

Internet Draft         draft-ietf-mpls-ldp-04.txt               May 1999

    3.4.1.1    FEC Procedures  .....................................  35
    3.4.2      Label TLVs  .........................................  35
    3.4.2.1    Generic Label TLV  ..................................  35
    3.4.2.2    ATM Label TLV  ......................................  35
    3.4.2.3    Frame Relay Label TLV  ..............................  36
    3.4.3      Address List TLV  ...................................  37
    3.4.4      Hop Count TLV  ......................................  38
    3.4.4.1    Hop Count Procedures  ...............................  38
    3.4.5      Path Vector TLV  ....................................  39
    3.4.5.1    Path Vector Procedures  .............................  40
    3.4.5.1.1  Label Request Path Vector  ..........................  40
    3.4.5.1.2  Label Mapping Path Vector  ..........................  41
    3.4.6      Status TLV  .........................................  42
    3.5        LDP Messages  .......................................  43
    3.5.1      Notification Message  ...............................  45
    3.5.1.1    Notification Message Procedures  ....................  47
    3.5.1.2    Events Signaled by Notification Messages  ...........  47
    3.5.1.2.1  Malformed PDU or Message  ...........................  47
    3.5.1.2.2  Unknown or Malformed TLV  ...........................  48
    3.5.1.2.3  Session KeepAlive Timer Expiration  .................  49
    3.5.1.2.4  Unilateral Session Shutdown  ........................  49
    3.5.1.2.5  Initialization Message Events  ......................  49
    3.5.1.2.6  Events Resulting From Other Messages  ...............  49
    3.5.1.2.7  Miscellaneous Events  ...............................  49
    3.5.2      Hello Message  ......................................  50
    3.5.2.1    Hello Message Procedures  ...........................  52
    3.5.3      Initialization Message  .............................  53
    3.5.3.1    Initialization Message Procedures  ..................  61
    3.5.4      KeepAlive Message  ..................................  61
    3.5.4.1    KeepAlive Message Procedures  .......................  62
    3.5.5      Address Message  ....................................  62
    3.5.5.1    Address Message Procedures  .........................  63
    3.5.6      Address Withdraw Message  ...........................  63
    3.5.6.1    Address Withdraw Message Procedures  ................  64
    3.5.7      Label Mapping Message  ..............................  64
    3.5.7.1    Label Mapping Message Procedures  ...................  65
    3.5.7.1.1  Independent Control Mapping  ........................  65
    3.5.7.1.2  Ordered Control Mapping  ............................  66
    3.5.7.1.3  Downstream on Demand Label Advertisement  ...........  66
    3.5.7.1.4  Downstream Unsolicited Label Advertisement  .........  67
    3.5.8      Label Request Message  ..............................  68
    3.5.8.1    Label Request Message Procedures  ...................  69
    3.5.9      Label Abort Request Message  ........................  70
    3.5.9.1    Label Abort Request Message Procedures  .............  71
    3.5.10     Label Withdraw Message  .............................  72
    3.5.10.1   Label Withdraw Message Procedures  ..................  73
    3.5.11     Label Release Message  ..............................  74
    3.5.11.1   Label Release Message Procedures  ...................  74

Andersson, et al.                                               [Page 4]

Internet Draft         draft-ietf-mpls-ldp-04.txt               May 1999

    3.6        Messages and TLVs for Extensibility  ................  75
    3.6.1      LDP Vendor-private Extensions  ......................  76
    3.6.1.1    LDP Vendor-private TLVs  ............................  76
    3.6.1.2    LDP Vendor-private Messages  ........................  77
    3.6.2      LDP Experimental Extensions  ........................  78
    3.7        Message Summary  ....................................  79
    3.8        TLV Summary  ........................................  79
    3.9        Status Code Summary  ................................  80
    3.10       Well-known Numbers  .................................  81
    3.10.1     UDP and TCP Ports  ..................................  81
    3.10.2     Implicit NULL Label  ................................  81
    4          Security Considerations  ............................  81
    4.1        The TCP MD5 Signature Option  .......................  81
    4.2        LDP Use of the TCP MD5 Signature Option  ............  83
    5          Intellectual Property Considerations  ...............  84
    6          Acknowledgments  ....................................  84
    7          References  .........................................  84
    8          Author Information  .................................  85

    Appendix.A LDP Label Distribution Procedures  ..................  87
    A.1        Handling Label Distribution Events  .................  89
    A.1.1      Receive Label Request  ..............................  90
    A.1.2      Receive Label Mapping  ..............................  93
    A.1.3      Receive Label Abort Request  ........................  97
    A.1.4      Receive Label Release  ..............................  99
    A.1.5      Receive Label Withdraw  ............................. 101
    A.1.6      Recognize New FEC  .................................. 102
    A.1.7      Detect Change in FEC Next Hop  ...................... 105
    A.1.8      Receive Notification / Label Request Aborted  ....... 108
    A.1.9      Receive Notification / No Label Resources  .......... 109
    A.1.10     Receive Notification / No Route  .................... 109
    A.1.11     Receive Notification / Loop Detected  ............... 110
    A.1.12     Receive Notification / Label Resources Available  ... 111
    A.1.13     Detect local label resources have become available  . 111
    A.1.14     LSR decides to no longer label switch a FEC  ........ 112
    A.1.15     Timeout of deferred label request  .................. 113
    A.2        Common Label Distribution Procedures  ............... 114
    A.2.1      Send_Label  ......................................... 114
    A.2.2      Send_Label_Request  ................................. 115
    A.2.3      Send_Label_Withdraw  ................................ 117
    A.2.4      Send_Notification  .................................. 117
    A.2.5      Send_Message  ....................................... 118
    A.2.6      Check_Received_Attributes  .......................... 118
    A.2.7      Prepare_Label_Request_Attributes  ................... 119
    A.2.8      Prepare_Label_Mapping_Attributes  ................... 121

Andersson, et al.                                               [Page 5]

Internet Draft         draft-ietf-mpls-ldp-04.txt               May 1999

1. LDP Overview

   Section 2.6 of the MPLS architecture [ARCH] defines a label
   distribution protocol as a set of procedures by which one Label
   Switched Router (LSR) informs another of the meaning of labels used
   to forward traffic between and through them.

   The MPLS architecture does not assume a single label distribution
   protocol.  In fact, a number of different label distribution
   protocols are being standardized.  Existing protocols have been
   extended so that label distribution can be piggybacked on them.  New
   protocols have also been defined for the explicit purpose of
   distributing labels.  Section 2.29 of the architecture [ARCH]
   discusses some of the considerations when chosing a label
   distribution protocol for use in particular MPLS applications such as
   Traffic Engineering [TE].

   The Label Distribution Protocol (LDP) defined in this document is a
   new protocol defined for distributing labels.  It is the set of
   procedures and messages by which Label Switched Routers (LSRs)
   establish Label Switched Paths (LSPs) through a network by mapping
   network-layer routing information directly to data-link layer
   switched paths.  These LSPs may have an endpoint at a directly
   attached neighbor (comparable to IP hop-by-hop forwarding), or may
   have an endpoint at a network egress node, enabling switching via all
   intermediary nodes.

   LDP associates a Forwarding Equivalence Class (FEC) [ARCH] with each
   LSP it creates. The FEC associated with an LSP specifies which
   packets are "mapped" to that LSP.  LSPs are extended through a
   network as each LSR "splices" incoming labels for a FEC to the
   outgoing label assigned to the next hop for the given FEC.

   This document assumes familiarity with the MPLS architecture [ARCH].
   Note that [ARCH] includes a glossary of MPLS terminology, such as
   ingress, label switched path, etc.

1.1. LDP Peers

   Two LSRs which use LDP to exchange label/stream mapping information
   are known as "LDP Peers" with respect to that information and we
   speak of there being an "LDP Session" between them.  A single LDP
   session allows each peer to learn the other's label mappings; i.e.,
   the protocol is bi-directional.

Andersson, et al.                                               [Page 6]

Internet Draft         draft-ietf-mpls-ldp-04.txt               May 1999

1.2. LDP Message Exchange

   There are four categories of LDP messages:

      1. Discovery messages, used to announce and maintain the presence
         of an LSR in a network.

      2. Session messages, used to establish, maintain, and terminate
         sessions between LDP peers.

      3. Advertisement messages, used to create, change, and delete
         label mappings for FECs.

      4. Notification messages, used to provide advisory information and
         to signal error information.

   Discovery messages provide a mechanism whereby LSRs indicate their
   presence in a network by sending the Hello message periodically.
   This is transmitted as a UDP packet to the LDP port at the `all
   routers on this subnet' group multicast address.  When an LSR chooses
   to establish a session with another LSR learned via the Hello
   message, it uses the LDP initialization procedure over TCP transport.
   Upon successful completion of the initialization procedure, the two
   LSRs are LDP peers, and may exchange advertisement messages.

   When to request a label or advertise a label mapping to a peer is
   largely a local decision made by an LSR.  In general, the LSR
   requests a label mapping from a neighboring LSR when it needs one,
   and advertises a label mapping to a neighboring LSR when it wishes
   the neighbor to use a label.

   Correct operation of LDP requires reliable and in order delivery of
   messages.  To satisfy these requirements LDP uses the TCP transport
   for session, advertisement and notification messages; i.e., for
   everything but the UDP-based discovery mechanism.

1.3. LDP Message Structure

   All LDP messages have a common structure that uses a Type-Length-
   Value (TLV) encoding scheme; see Section "Type-Length-Value"
   encoding.  The Value part of a TLV-encoded object, or TLV for short,
   may itself contain one or more TLVs.

Andersson, et al.                                               [Page 7]

Internet Draft         draft-ietf-mpls-ldp-04.txt               May 1999

1.4. LDP Error Handling

   LDP errors and other events of interest are signaled to an LDP peer
   by notification messages.

   There are two kinds of LDP notification messages:

      1. Error notifications, used to signal fatal errors.  If an LSR
         receives an error notification from a peer for an LDP session,
         it terminates the LDP session by closing the TCP transport
         connection for the session and discarding all label mappings
         learned via the session.

      2. Advisory notifications, used to pass an LSR information about
         the LDP session or the status of some previous message received
         from the peer.

1.5. LDP Extensibility and Future Compatibility

   Functionality may be added to LDP in the future.  It is likely that
   future functionality will utilize new messages and object types
   (TLVs).  It may be desirable to employ such new messages and TLVs
   within a network using older implementations that do not recognize
   them.  While it is not possible to make every future enhancement
   backwards compatible, some prior planning can ease the introduction
   of new capabilities.  This specification defines rules for handling
   unknown message types and unknown TLVs for this purpose.

2. LDP Operation

2.1. FECs

   It is necessary to precisely specify which packets may be mapped to
   each LSP.  This is done by providing a FEC specification for each
   LSP.  The FEC identifies the set of IP packets which may be mapped to
   that LSP.

   Each FEC is specified as a set of one or more FEC elements.  Each FEC
   element identifies a set of packets which may be mapped to the
   corresponding LSP.  When an LSP is shared by multiple FEC elements,
   that LSP is terminated at (or before) the node where the FEC elements
   can no longer share the same path.

   Following are the currently defined types of FEC elements.  New
   element types may be added as needed:

Andersson, et al.                                               [Page 8]

Internet Draft         draft-ietf-mpls-ldp-04.txt               May 1999

      1. Address Prefix.  This element is an address prefix of any
         length from 0 to a full address, inclusive.

      2. Host Address.  This element is a full host address.

   (We will see below that an Address Prefix FEC element which is a full
   address has a different effect than a Host Address FEC element which
   has the same address.)

   We say that a particular address "matches" a particular address
   prefix if and only if that address begins with that prefix.  We also
   say that a particular packet matches a particular LSP if and only if
   that LSP has an Address Prefix FEC element which matches the packet's
   destination address.  With respect to a particular packet and a
   particular LSP, we refer to any Address Prefix FEC element which
   matches the packet as the "matching prefix".

   The procedure for mapping a particular packet to a particular LSP
   uses the following rules.  Each rule is applied in turn until the
   packet can be mapped to an LSP.

     - If there is exactly one LSP which has a Host Address FEC element
       that is identical to the packet's destination address, then the
       packet is mapped to that LSP.

     - If there multiple LSPs, each containing a Host Address FEC
       element that is identical to the packet's destination address,
       then the packet is mapped to one of those LSPs.  The procedure
       for selecting one of those LSPs is beyond the scope of this
       document.

     - If a packet matches exactly one LSP, the packet is mapped to that
       LSP.

     - If a packet matches multiple LSPs, it is mapped to the LSP whose
       matching prefix is the longest.  If there is no one LSP whose
       matching prefix is longest, the packet is mapped to one from the
       set of LSPs whose matching prefix is longer than the others.  The
       procedure for selecting one of those LSPs is beyond the scope of
       this document.

     - If it is known that a packet must traverse a particular egress
       router, and there is an LSP which has an Address Prefix FEC
       element which is an address of that router, then the packet is
       mapped to that LSP.  The procedure for obtaining this knowledge
       is beyond the scope of this document.

   The procedure for determining that a packet must traverse a

Andersson, et al.                                               [Page 9]

Internet Draft         draft-ietf-mpls-ldp-04.txt               May 1999

   particular egress router is beyond the scope of this document.  (As
   an example, if one is running a link state routing algorithm, it may
   be possible to obtain this information from the link state data base.
   As another example, if one is running BGP, it may be possible to
   obtain this information from the BGP next hop attribute of the
   packet's route.)

   It is worth pointing out a few consequences of these rules:

     - A packet may be sent on the LSP whose Address Prefix FEC element
       is the address of the packet's egress router ONLY if there is no
       LSP matching the packet's destination address.

     - A packet may match two LSPs, one with a Host Address FEC element
       and one with an Address Prefix FEC element.  In this case, the
       packet is always assigned to the former.

     - A packet which does not match a particular Host Address FEC
       element may not be sent on the corresponding LSP, even if the
       Host Address FEC element identifies the packet's egress router.

2.2. Label Spaces, Identifiers, Sessions and Transport

2.2.1. Label Spaces

   The notion of "label space" is useful for discussing the assignment
   and distribution of labels.  There are two types of label spaces:

     - Per interface label space.  Interface-specific incoming labels
       are used for interfaces that use interface resources for labels.
       An example of such an interface is a label-controlled ATM
       interface that uses VCIs as labels, or a Frame Relay interface
       that uses DLCIs as labels.

       Note that the use of a per interface label space only makes sense
       when the LDP peers are "directly connected" over an interface,
       and the label is only going to be used for traffic sent over that
       interface.

     - Per platform label space. Platform-wide incoming labels are used
       for interfaces that can share the same labels.

Andersson, et al.                                              [Page 10]

Internet Draft         draft-ietf-mpls-ldp-04.txt               May 1999

2.2.2. LDP Identifiers

   An LDP identifier is a six octet quantity used to identify an LSR
   label space.  The first four octets encode an IP address assigned to
   the LSR, and the last two octets identify a specific label space
   within the LSR.  The last two octets of LDP Identifiers for
   platform-wide label spaces are always both zero.  This document uses
   the following print representation for LDP Identifiers:

               :