tech-invite   World Map     

3GPP     Specs     Glossaries     Architecture     IMS     UICC       IETF     RFCs     Groups     SIP     ABNFs       Search

RFC 8111

Pages: 44
Top     in Index     Prev     Next
in Group Index     Prev in Group     Next in Group     Group: LISP

Locator/ID Separation Protocol Delegated Database Tree (LISP-DDT)

Part 1 of 2, p. 1 to 23
None       Next Section


Top       ToC       Page 1 
Internet Engineering Task Force (IETF)                         V. Fuller
Request for Comments: 8111                   VAF.NET Internet Consulting
Category: Experimental                                          D. Lewis
ISSN: 2070-1721                                               V. Ermagan
                                                           Cisco Systems
                                                                 A. Jain
                                                        Juniper Networks
                                                              A. Smirnov
                                                           Cisco Systems
                                                                May 2017

   Locator/ID Separation Protocol Delegated Database Tree (LISP-DDT)


   This document describes the Locator/ID Separation Protocol Delegated
   Database Tree (LISP-DDT), a hierarchical distributed database that
   embodies the delegation of authority to provide mappings from LISP
   Endpoint Identifiers (EIDs) to Routing Locators (RLOCs).  It is a
   statically defined distribution of the EID namespace among a set of
   LISP-speaking servers called "DDT nodes".  Each DDT node is
   configured as "authoritative" for one or more EID-prefixes, along
   with the set of RLOCs for Map-Servers or "child" DDT nodes to which
   more-specific EID-prefixes are delegated.

Status of This Memo

   This document is not an Internet Standards Track specification; it is
   published for examination, experimental implementation, and

   This document defines an Experimental Protocol for the Internet
   community.  This document is a product of the Internet Engineering
   Task Force (IETF).  It represents the consensus of the IETF
   community.  It has received public review and has been approved for
   publication by the Internet Engineering Steering Group (IESG).  Not
   all documents approved by the IESG are a candidate for any level of
   Internet Standard; see Section 2 of RFC 7841.

   Information about the current status of this document, any errata,
   and how to provide feedback on it may be obtained at

[Page 2] 
Copyright Notice

   Copyright (c) 2017 IETF Trust and the persons identified as the
   document authors.  All rights reserved.

   This document is subject to BCP 78 and the IETF Trust's Legal
   Provisions Relating to IETF Documents
   ( in effect on the date of
   publication of this document.  Please review these documents
   carefully, as they describe your rights and restrictions with respect
   to this document.  Code Components extracted from this document must
   include Simplified BSD License text as described in Section 4.e of
   the Trust Legal Provisions and are provided without warranty as
   described in the Simplified BSD License.

Table of Contents

   1. Introduction ....................................................4
   2. Requirements Language ...........................................5
   3. Definitions of Terms ............................................6
   4. Database Organization ...........................................8
      4.1. XEID-Prefixes ..............................................8
      4.2. Structure of the DDT Database ..............................8
      4.3. Configuring Prefix Delegation ..............................9
           4.3.1. The Root DDT Node ..................................10
   5. DDT Map-Request ................................................10
   6. The Map-Referral Message .......................................11
      6.1. Action Codes ..............................................11
      6.2. Referral Set ..............................................12
      6.3. "Incomplete" Flag .........................................12
      6.4. Map-Referral Message Format ...............................13
           6.4.1. Signature Section ..................................15
   7. DDT Network Elements and Their Operation .......................17
      7.1. DDT Node ..................................................17
           7.1.1. Matching of a Delegated Prefix (or Sub-prefix) .....17
           7.1.2. Missing Delegation from an Authoritative Prefix ....18
      7.2. DDT Map-Server ............................................18
      7.3. DDT Client ................................................18
           7.3.1. Queuing and Sending DDT Map-Requests ...............19
           7.3.2. Receiving and Following Referrals ..................20
           7.3.3. Handling Referral Errors ...........................22
           7.3.4. Referral Loop Detection ............................22

Top      ToC       Page 3 
   8. Pseudocode and Decision Tree Diagrams ..........................23
      8.1. Map-Resolver Processing of ITR Map-Request ................23
           8.1.1. Pseudocode Summary .................................23
           8.1.2. Decision Tree Diagram ..............................24
      8.2. Map-Resolver Processing of Map-Referral Message ...........25
           8.2.1. Pseudocode Summary .................................25
           8.2.2. Decision Tree Diagram ..............................27
      8.3. DDT Node Processing of DDT Map-Request Message ............28
           8.3.1. Pseudocode Summary .................................28
           8.3.2. Decision Tree Diagram ..............................30
   9. Example Topology and Request/Referral Following ................31
      9.1. Lookup of 2001:db8:0103:1::1/128 ..........................33
      9.2. Lookup of 2001:db8:0501:8:4::1/128 ........................34
      9.3. Lookup of 2001:db8:0104:2::2/128 ..........................35
      9.4. Lookup of 2001:db8:0500:2:4::1/128 ........................36
      9.5. Lookup of 2001:db8:0500::1/128 (Nonexistent EID) ..........37
   10. Securing the Database and Message Exchanges ...................37
      10.1. XEID-Prefix Delegation ...................................38
      10.2. DDT Node Operation .......................................38
           10.2.1. DDT Public Key Revocation .........................38
      10.3. Map-Server Operation .....................................39
      10.4. Map-Resolver Operation ...................................39
   11. Open Issues and Considerations ................................40
   12. IANA Considerations ...........................................41
   13. Security Considerations .......................................41
   14. References ....................................................42
      14.1. Normative References .....................................42
      14.2. Informative References ...................................43
   Acknowledgments ...................................................44
   Authors' Addresses ................................................44

Top      ToC       Page 4 
1.  Introduction

   The Locator/ID Separation Protocol (LISP) [RFC6830] specifies an
   architecture and mechanism for replacing the addresses currently used
   by IP with two separate namespaces:

   o  Endpoint Identifiers (EIDs), used end to end for terminating
      transport-layer associations, and

   o  Routing Locators (RLOCs), which are bound to topological locations
      and are used for routing and forwarding through the Internet

   [RFC6833] specifies an interface between a database storing
   EID-to-RLOC mappings and LISP devices that need this information for
   packet forwarding.  The internal organization of such a database is
   beyond the scope of [RFC6833].  Multiple architectures of the
   database have been proposed, each having its advantages and
   disadvantages (see, for example, [RFC6836] and [RFC6837]).

   This document specifies an architecture for a database of LISP
   EID-to-RLOC mappings, with an emphasis on high scalability.  The
   LISP Delegated Database Tree (LISP-DDT) is a hierarchical distributed
   database that embodies the delegation of authority to provide
   mappings, i.e., its internal structure mirrors the hierarchical
   delegation of address space.  It also provides delegation information
   to Map-Resolvers, which use the information to locate EID-to-RLOC
   mappings.  A Map-Resolver that needs to locate a given mapping will
   follow a path through the tree-structured database and will contact,
   one after another, the DDT nodes along that path until it reaches the
   leaf DDT node(s) authoritative for the mapping it is seeking.

   LISP offers a general-purpose mechanism for mapping between EIDs and
   RLOCs.  In organizing a database of EID-to-RLOC mappings, this
   specification extends the definition of the EID numbering space by
   logically prepending and appending several fields for purposes of
   defining the database index key:

   o  Database-ID (DBID) (16 bits),

   o  Instance Identifier (IID) (32 bits),

   o  Address Family Identifier (AFI) (16 bits), and

   o  EID-prefix (variable, according to the AFI value).

   The resulting concatenation of these fields is termed an "Extended
   EID-prefix", or XEID-prefix.

Top      ToC       Page 5 
   LISP-DDT defines a new device type, the DDT node, that is configured
   as authoritative for one or more XEID-prefixes.  It is also
   configured with the set of more-specific sub-prefixes that are
   further delegated to other DDT nodes.  To delegate a sub-prefix, the
   "parent" DDT node is configured with the RLOCs of each child DDT node
   that is authoritative for the sub-prefix.  Each RLOC either points to
   a DDT Map-Server (MS) to which an Egress Tunnel Router (ETR) has
   registered that sub-prefix or points to another DDT node in the
   database tree that further delegates the sub-prefix.  See [RFC6833]
   for a description of the functionality of the Map-Server and
   Map-Resolver.  Note that the target of a delegation must always be an
   RLOC (not an EID) to avoid any circular dependency.

   To provide a mechanism for traversing the database tree, LISP-DDT
   defines a new LISP message type, the Map-Referral, which is returned
   to the sender of a Map-Request when the receiving DDT node can refer
   the sender to another DDT node that has more detailed information.
   See Section 6 for the definition of the Map-Referral message.

   To find an EID-to-RLOC mapping, a LISP-DDT client, usually a DDT
   Map-Resolver, starts by sending an Encapsulated Map-Request to a
   preconfigured DDT node RLOC.  The DDT node responds with a
   Map-Referral message indicating that either (1) it will find the
   requested mapping to complete processing of the request or (2) the
   DDT client should contact another DDT node that has more-specific
   information; in the latter case, the DDT node then sends a new
   Encapsulated Map-Request to the next DDT node and the process repeats
   in an iterative manner.

   Conceptually, this is similar to the way that a client of the Domain
   Name System (DNS) follows referrals (DNS responses that contain only
   NS records) from a series of DNS servers until it finds an answer.

2.  Requirements Language

   The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
   "OPTIONAL" in this document are to be interpreted as described in
   BCP 14 [RFC2119] [RFC8174] when, and only when, they appear in all
   capitals, as shown here.

Top      ToC       Page 6 
3.  Definitions of Terms

   Extended EID (XEID):  a LISP EID extended with data uniquely
      identifying the address space to which it belongs (LISP IID,
      address family, etc.).  See Section 4.1 for a detailed description
      of XEID data.

   Extended EID-prefix (XEID-prefix):  a LISP EID-prefix prepended with
      XEID data.  An XEID-prefix is used as a key index into the DDT
      database.  XEID-prefixes are used to describe database
      organization and are not seen as a single entity in protocol
      messages, though messages contain individual fields constituting

   DDT node:  a network infrastructure component responsible for
      specific XEID-prefix(es) and for the delegation of more-specific
      sub-prefixes to other DDT nodes.

   DDT client:  a network infrastructure component that sends DDT
      Map-Request messages and implements the iterative following of
      Map-Referral results.  Typically, a DDT client will be a
      Map-Resolver (as defined by [RFC6833]), but it is also possible
      for an Ingress Tunnel Router (ITR) to implement DDT client

   DDT Map-Server:  a DDT node that also implements Map-Server
      functionality (forwarding Map-Requests and/or returning
      Map-Replies if offering a proxy Map-Reply service) for a subset of
      its delegated prefixes.  Map-Server functions, including proxying
      Map-Replies, are described in [RFC6833].

   DDT Map-Server peers:  a list of all DDT Map-Servers performing
      Map-Server functionality for the same prefix.  If peers are
      configured on a DDT Map-Server, then the latter will provide
      complete information about the prefix in its Map-Replies;
      otherwise, the Map-Server will mark the returned reply as
      potentially incomplete.

   DDT Map-Resolver:  a network infrastructure element that implements
      both DDT client functionality and Map-Resolver functionality as
      defined by [RFC6833].  A DDT Map-Resolver accepts Map-Requests
      from ITRs, sends DDT Map-Requests to DDT nodes, and implements the
      iterative following of Map-Referrals.  Note that Map-Resolvers
      do not respond to clients that sent Map-Requests; they only ensure
      that the Map-Request has been forwarded to a LISP device (ETR or
      proxy Map-Server) that will provide an authoritative response to
      the original requester.  A DDT Map-Resolver will typically

Top      ToC       Page 7 
      maintain a cache (termed the "referral cache") of previously
      received Map-Referral message results containing RLOCs for DDT
      nodes responsible for XEID-prefixes of interest.

   Encapsulated Map-Request:  a LISP Map-Request that is carried within
      an Encapsulated Control Message and that has an additional LISP
      header prepended to it.  Sent to UDP destination port 4342.  The
      "outer" addresses are globally routable IP addresses, also known
      as RLOCs.  Used by an ITR when sending a Map-Request to a
      Map-Resolver and by a Map-Server when forwarding a Map-Request to
      an ETR as documented in [RFC6833].

   DDT Map-Request:  an Encapsulated Map-Request sent by a DDT client to
      a DDT node.  The "DDT-originated" flag is set in the encapsulation
      header, indicating that the DDT node should return Map-Referral
      messages if the Map-Request EID matches a delegated XEID-prefix
      known to the DDT node.  Section 7.3.1 describes how DDT
      Map-Requests are sent.  Section 5 defines the position of the
      "DDT-originated" flag in the Encapsulated Control Message header.

   Authoritative XEID-prefix:  an XEID-prefix delegated to a DDT node
      and for which the DDT node may provide further delegations of
      more-specific sub-prefixes.

   Map-Referral:  a LISP message sent by a DDT node in response to a DDT
      Map-Request for an XEID that matches a configured XEID-prefix
      delegation.  A non-Negative Map-Referral includes a "referral" --
      a set of RLOCs for DDT nodes that have information about the
      more-specific XEID-prefix covering the requested XEID; a DDT
      client "follows the referral" by sending another DDT Map-Request
      to one of those RLOCs to obtain either an answer or another
      referral to DDT nodes responsible for an XEID-prefix that is even
      more specific.  See Sections 7.1 and 7.3.2 for details on the
      sending and processing of Map-Referral messages.

   Negative Map-Referral:  an answer from an authoritative DDT node that
      there is no mapping for the requested XEID.  A Negative
      Map-Referral is a Map-Referral sent in response to a DDT
      Map-Request that matches an authoritative XEID-prefix but for
      which there is no delegation configured (or no ETR registration,
      if sent by a DDT Map-Server).

   Pending Request List:  the set of outstanding requests for which a
      DDT Map-Resolver has received Encapsulated Map-Requests from its
      clients seeking EID-to-RLOC mapping for an XEID.  Each entry in
      the list contains additional state needed by the
      referral-following process, including the XEID, requester(s) of
      the XEID (typically one or more ITRs), saved information about the

Top      ToC       Page 8 
      last referral received and followed (matching XEID-prefix, action
      code, RLOC set, index of the last RLOC queried in the RLOC set),
      and any LISP-Security (LISP-SEC) information [LISP-SEC] that was
      included in the DDT client Map-Request.  An entry in the list may
      be interchangeably termed a "pending request list entry" or simply
      a "pending request".

   For definitions of other terms -- notably Map-Request, Map-Reply,
   ITR, ETR, Map-Server, and Map-Resolver -- please consult the LISP
   specification [RFC6830] and the LISP Mapping Service specification

4.  Database Organization

4.1.  XEID-Prefixes

   A DDT database is indexed by Extended EID-prefixes (XEID-prefixes).
   An XEID-prefix is a LISP EID-prefix, together with data extending it
   to uniquely identify the address space of the prefix.  An XEID-prefix
   is composed of four binary-encoded fields, ordered by significance:
   DBID (16 bits), IID (32 bits), AFI (16 bits), and EID-prefix
   (variable, according to the AFI value).  The fields are concatenated,
   with the most significant fields as listed above.

   The DBID is the LISP-DDT Database-ID, a 16-bit field provided to
   allow the definition of multiple databases.  Implementations that are
   compliant with this document must always set this field to 0.  Other
   values of the DBID are reserved for future use.

   The Instance ID (IID) is a 32-bit value describing the context of the
   EID-prefix, if the latter is intended for use in an environment where
   addresses may not be unique, such as in a Virtual Private Network
   where the [RFC1918] address space is used.  See Section 5.5 of
   [RFC6830] for more discussion of IIDs.  Encoding of the IID is
   specified by [RFC8060].

   The AFI is a 16-bit value defining the syntax of the EID-prefix.  AFI
   values are assigned by IANA [AFI].

4.2.  Structure of the DDT Database

   The LISP-DDT database for each DDT node is organized as a tree
   structure that is indexed by XEID-prefixes.  Leaves of the database
   tree describe the delegation of authority between DDT nodes (see
   Section 4.3 for details regarding delegation and information kept in
   the database entries).

Top      ToC       Page 9 
   DDT Map-Requests sent by the DDT client to DDT nodes always contain
   specific values for the DBID, IID, and AFI; unspecified values or
   ranges of values are never used for any of these fields.  Thus, an
   XEID-prefix used as a key for searches in the database tree will have
   a length of at least 64 bits.

   A DDT node may, for example, be authoritative for a consecutive range
   of 3-tuples (DBID, IID, AFI) and all associated EID-prefixes, or only
   for a specific EID-prefix of a single 3-tuple.  Thus,
   XEID-prefixes/keys of the database tree leaves may have lengths less
   than, equal to, or more than 64 bits.

   It is important to note that LISP-DDT does not store actual
   EID-to-RLOC mappings; it is, rather, a distributed index that can be
   used to find the devices (ETRs that registered their EIDs with DDT
   Map-Servers) that can be queried with LISP to obtain those mappings.
   Changes to EID-to-RLOC mappings are made on the ETRs that define
   them, not to any DDT node configuration.  DDT node configuration
   changes are only required when branches of the database hierarchy are
   added, removed, or modified.

4.3.  Configuring Prefix Delegation

   Every DDT node is configured with one or more XEID-prefixes for which
   it is authoritative, along with a list of delegations of
   XEID-prefixes to other DDT nodes.  A DDT node is required to maintain
   a list of delegations for all sub-prefixes of its authoritative
   XEID-prefixes; it also may list "hints", which are prefixes that it
   knows about that belong to its parents, to the root, or to any other
   point in the XEID-prefix hierarchy.  A delegation (or hint) consists
   of an XEID-prefix, a set of RLOCs for DDT nodes that have more
   detailed knowledge of the XEID-prefix, and accompanying security
   information (for details regarding security information exchange and
   its use, see Section 10).  Those RLOCs are returned in Map-Referral
   messages when the DDT node receives a DDT Map-Request with an XEID
   that matches a delegation.  A DDT Map-Server will also have a set of
   sub-prefixes for which it accepts ETR mapping registrations and for
   which it will forward (or answer, if it provides a proxy Map-Reply
   service) Map-Requests.

   One or more XEID-prefixes for which a DDT node is authoritative, and
   the delegation of authority for sub-prefixes, are provided as part of
   the configuration of the DDT node.  Implementations will likely
   develop a language to express this prefix authority and delegation.
   Since DDT configuration is static (i.e., not exchanged between DDT
   nodes as part of the protocol itself), such language is
   implementation dependent and is outside the scope of this

Top      ToC       Page 10 
4.3.1.  The Root DDT Node

   The root DDT node is the logical "top" of the distributed database
   hierarchy.  It is authoritative for all XEID-prefixes -- that is, for
   all valid 3-tuples (DBID, IID, AFI) and their EID-prefixes.  A DDT
   Map-Request that matches no configured XEID-prefix will be referred
   to the root node (see Section 8 for a formal description of
   conditions where a DDT Map-Request is forwarded to the root node).
   The root node in a particular instantiation of LISP-DDT therefore
   MUST be configured, at a minimum, with delegations for all defined
   IIDs and AFIs.

5.  DDT Map-Request

   A DDT client (usually a Map-Resolver) uses LISP Encapsulated Control
   Messages (ECMs) to send Map-Request messages to a DDT node.  The
   format of the ECM is defined by [RFC6830].  This specification adds
   to the Encapsulated Control Message (ECM) header a new flag,
   "DDT-originated", as shown in the diagram and described below.

        0                   1                   2                   3
        0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
     / |                       IPv4 or IPv6 Header                     |
   OH  |                      (uses RLOC addresses)                    |
     \ |                                                               |
     / |       Source Port = xxxx      |       Dest Port = 4342        |
   UDP +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     \ |           UDP Length          |        UDP Checksum           |
   LH  |Type=8 |S|D|                Reserved                           |
     / |                       IPv4 or IPv6 Header                     |
   IH  |                  (uses RLOC or EID addresses)                 |
     \ |                                                               |
     / |       Source Port = xxxx      |       Dest Port = yyyy        |
   UDP +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     \ |           UDP Length          |        UDP Checksum           |
   LCM |                      LISP Control Message                     |

Top      ToC       Page 11 
   D: The "DDT-originated" flag.  This flag is set by a DDT client to
      indicate that the receiver SHOULD return Map-Referral messages as
      appropriate.  The use of this flag is further described in
      Section 7.3.1.  This bit is allocated from LISP message header
      bits marked as "Reserved" in [RFC6830].

6.  The Map-Referral Message

   This specification defines a new LISP message called the Map-Referral
   message.  A Map-Referral message is sent by a DDT node to a
   DDT client in response to a DDT Map-Request message.  See Section 6.4
   for a detailed layout of the Map-Referral message fields.

   The message consists of an action code along with delegation
   information about the XEID-prefix that matches the requested XEID.

6.1.  Action Codes

   The action codes are as follows:

   NODE-REFERRAL (0):  indicates that the replying DDT node has
      delegated an XEID-prefix that matches the requested XEID to one or
      more other DDT nodes.  The Map-Referral message contains a
      "map-record" with additional information -- most significantly,
      the set of RLOCs to which the prefix has been delegated -- that is
      used by a DDT client to "follow" the referral.

   MS-REFERRAL (1):  indicates that the replying DDT node has delegated
      an XEID-prefix that matches the requested XEID to one or more DDT
      Map-Servers.  It contains the same additional information as a
      NODE-REFERRAL but is handled slightly differently by the receiving
      DDT client (see Section 7.3.2).

   MS-ACK (2):  indicates that the replying DDT Map-Server received a
      DDT Map-Request that matches an authoritative XEID-prefix for
      which it has one or more registered ETRs.  This means that the
      request has been forwarded to one of those ETRs to provide an
      answer to the querying ITR.

   MS-NOT-REGISTERED (3):  indicates that the replying DDT Map-Server
      received a Map-Request for one of its configured XEID-prefixes
      that has no ETRs registered.

Top      ToC       Page 12 
   DELEGATION-HOLE (4):  indicates that the requested XEID matches a
      non-delegated sub-prefix of the XEID space.  This is a non-LISP
      "hole", which has not been delegated to any DDT Map-Server or ETR.
      See Section 7.1.2 for details.  Also sent by a DDT Map-Server with
      authoritative configuration covering the requested EID but for
      which no specific site ETR is configured.

   NOT-AUTHORITATIVE (5):  indicates that the replying DDT node received
      a Map-Request for an XEID for which it is not authoritative and
      has no configured matching hint referrals.  This can occur if a
      cached referral has become invalid due to a change in the database
      hierarchy.  However, if such a DDT node has a "hint" delegation
      covering the requested EID, it MAY choose to return NODE-REFERRAL
      or MS-REFERRAL as appropriate.  When returning action code
      NOT-AUTHORITATIVE, the DDT node MUST provide the EID-prefix
      received in the request and the TTL MUST be set to 0.

6.2.  Referral Set

   For "positive" action codes (NODE-REFERRAL, MS-REFERRAL, MS-ACK), a
   DDT node MUST include in the Map-Referral message a list of RLOCs for
   DDT nodes that are authoritative for the XEID-prefix being returned;
   a DDT client uses this information to contact one of those DDT nodes
   as it "follows" a referral.

6.3.  "Incomplete" Flag

   A DDT node sets the "Incomplete" flag in a Map-Referral message if
   the Referral Set is incomplete; this is intended to prevent a DDT
   client from caching a referral with incomplete information.  A DDT
   node MUST set the "Incomplete" flag in the following cases:

   o  If it is setting action code MS-ACK or MS-NOT-REGISTERED but the
      matching XEID-prefix is not flagged as "complete" in the
      configuration.  The XEID-prefix configuration on the DDT
      Map-Server SHOULD be marked as "complete" when the configuration
      of the XEID-prefix lists all "peer" DDT nodes that are also
      authoritative for the same XEID-prefix or when it is known that a
      local DDT node is the only authoritative node for the XEID-prefix.

   o  If it is setting action code NOT-AUTHORITATIVE.

Top      ToC       Page 13 
6.4.  Map-Referral Message Format

        0                   1                   2                   3
        0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
       |Type=6 |                Reserved               | Record Count  |
       |                         Nonce . . .                           |
       |                         . . . Nonce                           |
   +-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |   |                         Record TTL                            |
   |   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   R   | Referral Count| EID mask-len  | ACT |A|I|     Reserved        |
   e   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   c   |SigCnt |   Map Version Number  |            EID-AFI            |
   o   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   r   |                          EID-prefix ...                       |
   d   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |  /|    Priority   |    Weight     |  M Priority   |   M Weight    |
   | R +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   | e |       Unused Flags      |L|p|R|            Loc-AFI            |
   | f +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |  \|                             Locator ...                       |
   |   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |   ~                          Sig section                          ~
   +-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

   Type:  Type value 6 was reserved for future use in [RFC6830].  This
      document allocates this value to identify Map-Referral messages.

   ACT:  The ACT (Action) field of the mapping Record in a Map-Referral
      message encodes one of the following six action types:
      DELEGATION-HOLE, or NOT-AUTHORITATIVE.  See Section 6.1 for
      descriptions of these action types.

Top      ToC       Page 14 
   Incomplete:  The "I" bit indicates that a DDT node's Referral Set of
      locators is incomplete and the receiver of this message SHOULD NOT
      cache the referral.  A DDT sets the "Incomplete" flag, the TTL,
      and the Action field as follows:

    Type (Action field)          Incomplete Referral Set   TTL values
     0    NODE-REFERRAL              No         Yes           1440

     1    MS-REFERRAL                No         Yes           1440

     2    MS-ACK                     *          *             1440

     3    MS-NOT-REGISTERED          *          *             1

     4    DELEGATION-HOLE            No         No            15

     5    NOT-AUTHORITATIVE          Yes        No            0

   *: The "Incomplete" flag setting for the Map-Server-originated
      referral of MS-ACK and MS-NOT-REGISTERED types depends on whether
      the Map-Server has the full peer Map-Server configuration for the
      same prefix and has encoded the information in the mapping Record.
      The "Incomplete" bit is not set when the Map-Server has encoded
      the information; this means that the Referral Set includes all the
      RLOCs of all Map-Servers that serve the prefix.  It MUST be set
      when the configuration of the Map-Server does not flag the
      matching prefix as configured with the complete information about
      "peer" Map-Servers or when the Map-Server does not return all
      configured locators.

   Referral Count:  Number of RLOCs in the current Referral Set.  This
      number is equal to the number of "Ref" sections in the message (as
      shown in the diagram above).

   SigCnt:  Indicates the number of signatures (Signature section)
      present in the Record.  If SigCnt is larger than 0, the signature
      information captured in a Signature section as described in
      Section 6.4.1 will be appended to the end of the Record.  The
      number of Signature sections at the end of the Record MUST match
      the SigCnt.  Note that bits occupied by SigCnt were marked as
      "Reserved" in Records embedded into messages defined by [RFC6830]
      and were required to be set to zero.

Top      ToC       Page 15 
   Loc-AFI:  AFI of the Locator field.  If the AFI value is different
      from the LISP Canonical Address Format (LCAF) AFI, security keys
      are not included in the Record.  If the AFI value is equal to the
      LCAF AFI, the contents of the LCAF depend on the Type field of the
      LCAF.  LCAF Type 11 is used to store security material along with
      the AFI of the locator.  DDT nodes and DDT Map-Servers can use
      this LCAF Type to include public keys associated with their child
      DDT nodes for an XEID-prefix Map-Referral Record.  LCAF Types and
      formats are defined in [RFC8060].

   Locator:  RLOC of a DDT node to which the DDT client is being
      referred.  This is a variable-length field; its length is
      determined by the Loc-AFI setting.

   All other fields and their descriptions are equivalent to those in
   the Map-Reply message, as defined in LISP [RFC6830].  Note, though,
   that the set of RLOCs correspond to the DDT node to be queried as a
   result of the referral and not to the RLOCs for an actual EID-to-RLOC

6.4.1.  Signature Section

   SigCnt counts the number of signature sections that appear at the end
   of the Record.  The format of the signature section is described

      /|                      Original Record TTL                      |
     / +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    /  |                      Signature Expiration                     |
   |   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   s   |                      Signature Inception                      |
   i   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   g   |            Key Tag            |           Sig Length          |
   |   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   \   | Sig-Algorithm |    Reserved   |            Reserved           |
    \  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     \ ~                             Signature                         ~

   Original Record TTL:  The original Record TTL for this Record that
      is covered by the signature.  The Record TTL value is specified
      in minutes.

Top      ToC       Page 16 
   Signature Expiration and Signature Inception:  Specify the validity
      period for the signature.  The signature MUST NOT be used for
      authentication prior to the inception date and MUST NOT be used
      for authentication after the expiration date.  Each field
      specifies a date and time in the form of a 32-bit unsigned number
      of seconds elapsed since 1 January 1970 00:00:00 UTC, ignoring
      leap seconds, in network byte order.

   Key Tag:  An identifier to specify which key is used for this
      signature if more than one valid key exists for the signing
      DDT node.

   Sig Length:  The length of the Signature field in bytes.

   Sig-Algorithm:  The identifier of the cryptographic algorithm used
      for the signature.  Sig-Algorithm values defined in this
      specification are listed in Table 1.  Implementations conforming
      to this specification MUST implement at least RSA-SHA256 for DDT
      signing.  Sig-Algorithm type 1 (RSA-SHA1) is deprecated and
      SHOULD NOT be used.

          | Sig-Algorithm |    Name    | Reference |   Notes    |
          |       1       |  RSA-SHA1  | [RFC8017] | DEPRECATED |
          |               |            |           |            |
          |       2       | RSA-SHA256 | [RFC8017] | MANDATORY  |

                       Table 1: Sig-Algorithm Values

   Reserved:  MUST be set to 0 on transmit and MUST be ignored on

   Signature:  Contains the cryptographic signature that covers the
      entire Map-Referral Record to which this signature belongs.  For
      the purpose of computing the signature, the Record TTL
      (Section 6.4) value is set to the value of Original Record TTL and
      the Signature field is filled with zeros.

Top      ToC       Page 17 
7.  DDT Network Elements and Their Operation

   As described above, LISP-DDT introduces a new network element -- the
   DDT node -- and extends the functionality of Map-Servers and
   Map-Resolvers to send and receive Map-Referral messages.  The
   operation of each of these devices is described below.

7.1.  DDT Node

   When a DDT node receives a DDT Map-Request, it compares the requested
   XEID against its list of XEID-prefix delegations and its list of
   authoritative XEID-prefixes, and proceeds as follows:

7.1.1.  Matching of a Delegated Prefix (or Sub-prefix)

   If the requested XEID matches one of the DDT node's delegated
   prefixes, then a Map-Referral message is returned with the matching
   more-specific XEID-prefix and the set of RLOCs for the referral
   target DDT nodes, including associated security information (see
   Section 10 for details on security).  If at least one DDT node of the
   delegation is known to be a DDT Map-Server, then the Map-Referral
   message SHOULD be sent with action code MS-REFERRAL to indicate to
   the receiver that LISP-SEC information (if saved in the pending
   request) SHOULD be included in the next DDT Map-Request; otherwise,
   the action code NODE-REFERRAL SHOULD be used.

   Note that a matched delegation does not have to be for a sub-prefix
   of an authoritative prefix; in addition to being configured to
   delegate sub-prefixes of an authoritative prefix, a DDT node may also
   be configured with other XEID-prefixes for which it can provide
   referrals to DDT nodes anywhere in the database hierarchy.  This
   capability to define "shortcut hints" is never required to be
   configured, but it may be a useful heuristic for reducing the number
   of iterations needed to find an EID, particularly for private network

   Referral hints, if used properly, may reduce the number of referrals
   a DDT client needs to follow to locate a DDT Map-Server authoritative
   for the XEID-prefix being resolved.  On the other hand, the incorrect
   use of hints may create circular dependencies (or "referral loops")
   between DDT nodes.  A DDT client MUST be prepared to handle such
   circular referrals.  See Section 7.3.4 for a discussion of referral
   loops and measures that the DDT client must implement in order to
   detect circular referrals and prevent infinite looping.

   Another danger related to the use of hints is when a DDT deployment
   spans multiple administrative domains (i.e., different authorities
   manage DDT nodes in the same DDT database).  In this case, an

Top      ToC       Page 18 
   operator managing a DDT node may not be aware of the fact that the
   node is being referred to by hints.  Locator addresses in hints may
   become stale when referred DDT nodes are taken out of service or
   change their locator addresses.

7.1.2.  Missing Delegation from an Authoritative Prefix

   If the requested XEID did not match a configured delegation but does
   match an authoritative XEID-prefix, then the DDT node MUST return a
   Negative Map-Referral that uses the least-specific XEID-prefix that
   does not match any XEID-prefix delegated by the DDT node.  The action
   code is set to DELEGATION-HOLE; this indicates that the XEID is not a
   LISP destination.

   If the requested XEID did not match either a configured delegation,
   an authoritative XEID-prefix, or a hint, then a Negative Map-Referral
   with action code NOT-AUTHORITATIVE MUST be returned.

7.2.  DDT Map-Server

   When a DDT Map-Server receives a DDT Map-Request, its operation is
   similar to that of a DDT node, with additional processing as follows:

   o  If the requested XEID matches a registered XEID-prefix, then the
      Map-Request is forwarded to one of the destination ETR RLOCs (or
      the Map-Server sends a Map-Reply, if it is providing a proxy
      Map-Reply service), and a Map-Referral with action code MS-ACK
      MUST be returned to the sender of the DDT Map-Request.

   o  If the requested XEID matches a configured XEID-prefix for which
      no ETR registration has been received, then a Negative
      Map-Referral with action code MS-NOT-REGISTERED MUST be returned
      to the sender of the DDT Map-Request.

7.3.  DDT Client

   A DDT client queries one or more DDT nodes and uses an iterative
   process of following returned referrals until it receives one with
   action code MS-ACK (or an error indication).  MS-ACK indicates that
   the Map-Request has been sent to a Map-Server that will forward it to
   an ETR that, in turn, will provide a Map-Reply to the locator address
   in the Map-Request.

   DDT client functionality will typically be implemented by DDT
   Map-Resolvers.  Just as would any other Map-Resolver, a DDT
   Map-Resolver accepts Map-Requests from its clients (typically ITRs)
   and ensures that those Map-Requests are forwarded to the correct ETR,
   which generates Map-Replies.  However, unlike a Map-Resolver that

Top      ToC       Page 19 
   uses the LISP Alternative Logical Topology (LISP+ALT) mapping system
   [RFC6836], a DDT Map-Resolver implements DDT client functionality to
   find the correct ETR to answer a Map-Request; this requires a DDT
   Map-Resolver to maintain additional state: a Map-Referral cache and a
   pending request list of XEIDs that are going through the iterative
   referral process.

   DDT client functionality may be implemented on ITRs.  In this case,
   the DDT client will not receive a Map-Request from another network
   element; instead, equivalent information will be provided to the DDT
   client via a programming interface.

7.3.1.  Queuing and Sending DDT Map-Requests

   When a DDT client receives a request to resolve an XEID (in the case
   of a DDT Map-Resolver, this will be in the form of a received
   Encapsulated Map-Request), it first performs a longest-match search
   for the XEID in its referral cache.  If no match is found or if a
   negative cache entry is found, then the destination is not in the
   database; a Negative Map-Reply MUST be returned, and no further
   processing is performed by the DDT client.

   If a match is found, the DDT client creates a pending request list
   entry for the XEID and saves the original request (in the case of a
   DDT Map-Resolver, this will be the original Map-Request minus the
   encapsulation header) along with other information needed to track
   progress through the iterative referral process; the "referral
   XEID-prefix" is also initialized to indicate that no referral has yet
   been received.  The DDT client then creates a DDT Map-Request (which
   is an Encapsulated Map-Request with the "DDT-originated" flag set in
   the message header) for the XEID but without any authentication data
   that may have been included in the original request.  It sends the
   DDT Map-Request to one of the RLOCs in the chosen referral cache
   entry.  The referral cache is initially populated with one or more
   statically configured entries; additional entries are added when
   referrals are followed, as described below.  A DDT client is not
   absolutely required to cache referrals, but doing so will decrease
   latency and reduce lookup delays.

   Note that in normal use on the public Internet, the statically
   configured initial referral cache for a DDT client should include a
   "default" entry with RLOCs for either the root DDT node or one or
   more DDT nodes that contain hints for the root DDT node.  If a DDT
   client does not have such a configuration, it will return a Negative
   Map-Reply if it receives a query for an EID outside the subset of the
   mapping database known to it.  While this may be desirable on private
   network deployments or during early transition to LISP when few sites
   are using it, this behavior is not appropriate when LISP is in

Top      ToC       Page 20 
   general use on the Internet.  If DDT message exchanges are
   authenticated as described in Section 10, then the DDT client MUST
   also be configured with public keys of DDT nodes pointed to by the
   "default" cache entry.  In this case, the "default" entry will
   typically be for the root DDT node.

7.3.2.  Receiving and Following Referrals

   After sending a DDT Map-Request, a DDT client expects to receive a
   Map-Referral response.  If none occurs within the timeout period, the
   DDT client retransmits the request, sending it to the next RLOC in
   the referral cache entry if one is available.  If all RLOCs have been
   tried and the maximum number of retransmissions has occurred for
   each, then the pending request list entry is dequeued and discarded.
   In this case, the DDT client returns no response to the sender of the
   original request.

   A DDT client processes a received Map-Referral message according to
   each action code:

   NODE-REFERRAL:  The DDT client checks for a possible referral loop as
      described in Section 7.3.4.  If no loop is found, the DDT client
      saves the prefix returned in the Map-Referral message in the
      referral cache, updates the saved prefix and saved RLOCs in the
      pending request list entry, and follows the referral by sending a
      new DDT Map-Request to one of the DDT node RLOCs listed in the
      Referral Set; security information saved with the original
      Map-Request SHOULD NOT be included.

   MS-REFERRAL:  The DDT client processes an MS-REFERRAL in the same
      manner as a NODE-REFERRAL, except that security information saved
      with the original Map-Request MUST be included in the new
      Map-Request sent to a Map-Server (see Section 10 for details on

   MS-ACK:  An MS-ACK is returned by a DDT Map-Server to indicate that
      it has one or more registered ETRs that can answer a Map-Request
      for the XEID and the request has been forwarded to one of them
      (or, if the Map-Server is providing a proxy service for the
      prefix, then a reply has been sent to the querying ITR).  If the
      pending request did not include saved LISP-SEC information or if
      that information was already included in the previous DDT
      Map-Request (sent by the DDT client in response to either an
      MS-REFERRAL or a previous MS-ACK referral), then the pending
      request for the XEID is complete; processing of the request stops,
      and all request state can be discarded.  Otherwise, LISP-SEC
      information is required and has not yet been sent to the
      authoritative DDT Map-Server; the DDT client MUST resend the DDT

Top      ToC       Page 21 
      Map-Request with LISP-SEC information included, and the pending
      request queue entry remains until another Map-Referral with action
      code MS-ACK is received.  If the "Incomplete" flag is not set, the
      prefix is saved in the referral cache.

   MS-NOT-REGISTERED:  The DDT Map-Server queried could not process the
      request because it did not have any ETRs registered for a
      matching, authoritative XEID-prefix.  If the DDT client has not
      yet tried all of the RLOCs saved with the pending request, then it
      sends a Map-Request to the next RLOC in that list.  If all RLOCs
      have been tried, then the destination XEID is not registered and
      is unreachable.  The DDT client MUST return a Negative Map-Reply
      to the requester (or, in the case of a DDT Map-Resolver, to the
      sender of the original Map-Request).  This Map-Reply contains the
      least-specific XEID-prefix in the range for which this DDT
      Map-Server is authoritative and in which no registrations exist.
      The TTL value of the Negative Map-Reply SHOULD be set to 1 minute.
      A negative referral cache entry is created for the prefix (whose
      TTL also SHOULD be set to 1 minute), and processing of the request

   DELEGATION-HOLE:  The DDT Map-Server queried did not have an
      XEID-prefix defined that matched the requested XEID, so the XEID
      does not exist in the mapping database.  The DDT client MUST
      return a Negative Map-Reply to the requester (or, in the case of a
      DDT Map-Resolver, to the sender of the original Map-Request); this
      Map-Reply SHOULD indicate the least-specific XEID-prefix matching
      the requested XEID for which no delegations exist and SHOULD have
      a TTL value of 15 minutes.  A negative referral cache entry is
      created for the prefix (which also SHOULD have a TTL of
      15 minutes), and processing of the pending request stops.

   NOT-AUTHORITATIVE:  The DDT Map-Server queried is not authoritative
      for the requested XEID.  This can occur if a cached referral has
      become invalid due to a change in the database hierarchy.  If the
      DDT client receiving this message can determine that it is using
      old cached information, it MAY choose to delete that cached
      information and retry the original Map-Request, starting from its
      "root" cache entry.  If this action code is received in response
      to a query that did not use cached referral information, then it
      indicates a database synchronization problem or configuration
      error.  The pending request is silently discarded; i.e., all state
      for the request that caused this answer is removed, and no answer
      is returned to the original requester.

Top      ToC       Page 22 
7.3.3.  Handling Referral Errors

   Other states are possible, such as a misconfigured DDT node (acting
   as a proxy Map-Server, for example) returning a Map-Reply to the DDT
   client; they should be considered errors and logged as such.  It is
   not clear exactly what else the DDT client should do in such cases;
   one possibility is to remove the pending request list entry and send
   a Negative Map-Reply to the requester (or, in the case of a DDT
   Map-Resolver, to the sender of the original Map-Request).
   Alternatively, if a DDT client detects unexpected behavior by a DDT
   node, it could mark that node as unusable in its referral cache and
   update the pending request to try a different DDT node if more than
   one is listed in the referral cache.  In any case, any prefix
   contained in a Map-Referral message that causes a referral error
   (including a referral loop) is not saved in the DDT client referral

7.3.4.  Referral Loop Detection

   In response to a Map-Referral message with action code NODE-REFERRAL
   or MS-REFERRAL, a DDT client is directed to query a new set of DDT
   node RLOCs that are expected to have more-specific XEID-prefix
   information for the requested XEID.  To prevent a possible "iteration
   loop" (following referrals back and forth among a set of DDT nodes
   without ever finding an answer), a DDT client saves the last received
   referral XEID-prefix for each pending request and checks to see if a
   newly received NODE-REFERRAL or MS-REFERRAL message contains a
   more-specific referral XEID-prefix; an exact or less-specific match
   of the saved XEID-prefix indicates a referral loop.  If a loop is
   detected, the DDT Map-Resolver handles the request as described in
   Section 7.3.3.  Otherwise, the DDT client saves the most recently
   received referral XEID-prefix with the pending request when it
   follows the referral.

   As an extra measure to prevent referral loops, it is probably also
   wise to limit the total number of referrals for any request to some
   reasonable number; the exact value of that number will be determined
   during experimental deployment of LISP-DDT but is bounded by the
   maximum length of the XEID.

   Note that when a DDT client adds an entry to its lookup queue and
   sends an initial Map-Request for an XEID, the queue entry has no
   previous referral XEID-prefix; this means that the first DDT node
   contacted by a DDT Map-Resolver may provide a referral to anywhere in
   the DDT hierarchy.  This, in turn, allows a DDT client to use
   essentially any DDT node RLOCs for its initial cache entries and

Top      ToC       Page 23 
   depend on the initial referral to provide a good starting point for
   Map-Requests; there is no need to configure the same set of root DDT
   nodes on all DDT clients.

(page 23 continued on part 2)

Next Section