LISP Working Group D. Saucez, Ed. Internet-Draft Inria Obsoletes: 8111 (if approved) L. Iannone, Ed. Updates: 9301 (if approved) Huawei Intended status: Standards Track 3 March 2025 Expires: 4 September 2025 Locator/ID Separation Protocol Delegated Database Tree (LISP-DDT) draft-saucez-lisp-8111bis-01 Abstract 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 control plane elements generically 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. This document obsoletes RFC 8111 and updates RFC 9301. Status of This Memo This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF). Note that other groups may also distribute working documents as Internet-Drafts. The list of current Internet- Drafts is at https://datatracker.ietf.org/drafts/current/. 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." This Internet-Draft will expire on 4 September 2025. Copyright Notice Copyright (c) 2025 IETF Trust and the persons identified as the document authors. All rights reserved. Saucez & Iannone Expires 4 September 2025 [Page 1] Internet-Draft LISP-DDT March 2025 This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (https://trustee.ietf.org/ license-info) 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 Revised BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Revised BSD License. Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 2. Requirements Language . . . . . . . . . . . . . . . . . . . . 5 3. Definitions of Terms . . . . . . . . . . . . . . . . . . . . 5 4. Delegated Database Tree Organization . . . . . . . . . . . . 7 4.1. XEID-Prefixes . . . . . . . . . . . . . . . . . . . . . . 7 4.2. Structure of the DDT Database . . . . . . . . . . . . . . 7 4.3. Configuring Prefix Delegation . . . . . . . . . . . . . . 8 4.3.1. The Root DDT Node . . . . . . . . . . . . . . . . . . 8 5. The DDT Map-Referral Message . . . . . . . . . . . . . . . . 9 5.1. Map-Referral Message Format . . . . . . . . . . . . . . . 9 5.2. Action Codes . . . . . . . . . . . . . . . . . . . . . . 11 5.3. Referral Set . . . . . . . . . . . . . . . . . . . . . . 12 5.4. "Incomplete" Flag . . . . . . . . . . . . . . . . . . . . 12 5.5. Signature Section . . . . . . . . . . . . . . . . . . . . 12 6. DDT Network Elements and Their Operation . . . . . . . . . . 14 6.1. DDT Node . . . . . . . . . . . . . . . . . . . . . . . . 14 6.1.1. XEID Match . . . . . . . . . . . . . . . . . . . . . 14 6.1.2. XEID Miss . . . . . . . . . . . . . . . . . . . . . . 15 6.2. DDT Map-Server . . . . . . . . . . . . . . . . . . . . . 15 6.3. DDT Client . . . . . . . . . . . . . . . . . . . . . . . 16 6.3.1. Queuing and Sending DDT Map-Requests . . . . . . . . 16 6.3.2. Receiving and Following DDT Map-Referrals . . . . . . 17 6.3.3. Handling Referral Errors . . . . . . . . . . . . . . 19 6.3.4. Referral Loop Detection . . . . . . . . . . . . . . . 19 7. Securing the Database and Message Exchanges . . . . . . . . . 19 7.1. XEID-Prefix Delegation . . . . . . . . . . . . . . . . . 20 7.2. DDT Node Operation . . . . . . . . . . . . . . . . . . . 21 7.2.1. DDT Public Key Revocation . . . . . . . . . . . . . . 21 7.3. Map-Server Operation . . . . . . . . . . . . . . . . . . 22 7.4. Map-Resolver Operation . . . . . . . . . . . . . . . . . 22 8. Security Considerations . . . . . . . . . . . . . . . . . . . 22 9. Deployment Experience . . . . . . . . . . . . . . . . . . . . 23 10. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 23 10.1. LISP DDT Map-Referral Packet Type . . . . . . . . . . . 23 10.2. LISP DDT Action Codes . . . . . . . . . . . . . . . . . 23 11. References . . . . . . . . . . . . . . . . . . . . . . . . . 24 11.1. Normative References . . . . . . . . . . . . . . . . . . 24 Saucez & Iannone Expires 4 September 2025 [Page 2] Internet-Draft LISP-DDT March 2025 11.2. Informative References . . . . . . . . . . . . . . . . . 25 Appendix A. Pseudo-code and Decision Tree Diagrams . . . . . . . 26 A.1. Map-Resolver Processing of Map-Request . . . . . . . . . 26 A.1.1. Pseudo-code Summary . . . . . . . . . . . . . . . . . 26 A.1.2. Decision Tree Diagram . . . . . . . . . . . . . . . . 26 A.2. Map-Resolver Processing of Map-Referral Message . . . . . 27 A.2.1. Pseudo-code Summary . . . . . . . . . . . . . . . . . 27 A.2.2. Decision Tree Diagram . . . . . . . . . . . . . . . . 29 A.3. DDT Node Processing of DDT Map-Request Message . . . . . 30 A.3.1. Pseudo-code Summary . . . . . . . . . . . . . . . . . 30 A.3.2. Decision Tree Diagram . . . . . . . . . . . . . . . . 31 Appendix B. Generic DDT Example . . . . . . . . . . . . . . . . 33 B.1. Reference DDT Tree Topology . . . . . . . . . . . . . . . 33 B.2. Lookup EID registered at with Map-Server1 . . . . . . . . 34 B.3. Lookup EID registered at with Map-Server3 . . . . . . . . 35 B.4. Lookups using cached DDT Map-Referrals to Map-Servers . . 36 B.5. Lookup using cached DDT Map-Referrals to DDT Nodes . . . 37 B.6. Lookup of a non-existent EID . . . . . . . . . . . . . . 37 Contributors . . . . . . . . . . . . . . . . . . . . . . . . . . 38 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 39 1. Introduction The Locator/ID Separation Protocol (LISP), defined in [RFC9300] and [RFC9301], specifies an architecture to create overlays networks leveraging on two separate namespaces, namely the Endpoint Identifiers (EIDs) used for end-to-end communications, and the Routing Locators (RLOCs) used for routing and forwarding. [RFC9301] specifies an interface between a database storing EID-to- RLOC mappings and LISP devices that need such information to forward packets. The internal organization of such a database is beyond the scope of [RFC9301]. 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 scalable distributed database of LISP EID-to-RLOC mappings: the LISP Delegated Database Tree (LISP-DDT). 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 perform EID-to-RLOC mappings lookups. A Map-Resolver that requests a given mapping will follow a path through the tree-structured database and will contact, one after another, the nodes along that path, until it reaches the leaf node(s) authoritative for the mapping it is seeking. Saucez & Iannone Expires 4 September 2025 [Page 3] Internet-Draft LISP-DDT March 2025 In organizing a database of EID-to-RLOC mappings, this specification extends the definition of the EID numbering space by logically concatenating the following attributes in order to define the database index key: * Database-ID (DBID) (16 bits) * Instance Identifier (IID) (24 bits) * Address Family Identifier (AFI) (16 bits) * EID-Prefix (variable, according to the AFI value) The resulting concatenation of these fields is termed an "Extended EID-Prefix", or XEID-Prefix. 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 [RFC9301] 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 the Map-Referral LISP message type, 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 5 for the definition of the Map-Referral message. To find an EID-to-RLOC mapping, a LISP-DDT Client, usually a Map- Resolver, starts by sending an Encapsulated Map-Request to a pre- configured 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 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 [RFC1035]. Saucez & Iannone Expires 4 September 2025 [Page 4] Internet-Draft LISP-DDT March 2025 This document obsoletes [RFC8111] and updates [RFC9301]. 2. Requirements Language The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and "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. 3. Definitions of Terms This documents assumes that the reader is familiar with LISP and the LISP terminology. For definitions of terms like Map-Request, Encapsulated Map-Request, Map-Reply, ITR, ETR, Map-Server, and Map- Resolver, please consult the LISP Data Plane specification [RFC9300] and the LISP Control Plane specification [RFC9301]. 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. DDT Client: a network infrastructure component that sends Map- Request messages and implements the iterative following of Map- Referral results. Typically, a DDT Client will be a Map-Resolver (as defined by [RFC9301]), but it is also possible for an Ingress Tunnel Router (ITR) to implement DDT Client functionality. DDT 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 DDT Map-Referral includes a "referral" consisting in a set of RLOCs for DDT Nodes that have information about the more-specific XEID-Prefix covering the requested XEID. See Section 5 for a complete definition of the message and Section 6.1 and Section 6.3 for details on its processing. DDT Map-Referral Cache: Data structure to temporarily maintain previously received Map-Referral message results, containing RLOCs for DDT Nodes responsible for XEID-Prefixes. DDT Map-Request: an ECM Map-Request sent by a DDT Client to a DDT Node, with the "DDT-originated" flag set. Section 6.3.1 describes how DDT Map-Requests are sent. [RFC9301] defines the position of the "DDT-originated" flag in the Encapsulated Control Message header. DDT Map-Resolver: a Map-Resolver that also implements DDT Client Saucez & Iannone Expires 4 September 2025 [Page 5] Internet-Draft LISP-DDT March 2025 functionality. Map-Resolver functionality is defined by [RFC9301]. A DDT Map-Resolver accepts Map-Requests from ITRs, sends Map-Requests to DDT Nodes, and implements the iterative following of Map-Referrals. Note that Map-Resolvers, as of [RFC9301], 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. This document uses the terms "DDT Map-Resolver" and "Map-Resolver" interchangeably. DDT Map-Server: a Map-Server that also implements DDT functionality. Map-Server functionality is defined in [RFC9301]. This document uses the terms "DDT Map-Server" and "Map-Server" interchangeably. 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 Node: a network infrastructure component responsible for specific XEID-Prefix(es) and for the delegation of more-specific sub-prefixes to other DDT Nodes. 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 XEID-Prefixes. Negative DDT Map-Referral: 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 Requests List: Data structure storing the set of outstanding requests for which a DDT Map-Resolver has received ECM 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 Saucez & Iannone Expires 4 September 2025 [Page 6] Internet-Draft LISP-DDT March 2025 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 [RFC9303] that was included in the DDT Client Map-Request. An entry in the list may be interchangeably termed a "pending requests list entry" or simply a "pending request". 4. Delegated Database Tree Organization This section firstly defines the DDT database index key, namely XEID- Prefixes, and then details of the DDT database organization and how to configure prefix delegation. 4.1. XEID-Prefixes A DDT database is indexed by Extended EID-Prefixes (XEID-Prefixes). An XEID-Prefix is a LISP EID-Prefix that includes additional data to uniquely identify the address space associated with the prefix. An XEID-Prefix is composed of four binary-encoded concatenated attributes: * DBID (16 bits), * Instance ID (24 bits), * AFI (16 bits), * and EID-Prefix (variable, according to the AFI value). The DBID is the LISP-DDT Database-ID, a 16-bit attribute that allows 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 24-bit value describing the context of the EID-Prefix, see Section 8 of [RFC9300] for more discussion of Instance IDs. 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 is organized as a prefix tree structure that is indexed by XEID-Prefixes, where each node of the tree is a DDT Node which has delegated for a set of sub-prefixes (see Section 4.3 for details regarding delegation). Saucez & Iannone Expires 4 September 2025 [Page 7] Internet-Draft LISP-DDT March 2025 DDT Map-Requests sent by DDT Clients to DDT Nodes always contain specific values for the DBID, IID, and AFI; unspecified values or ranges of values MUST NOT be used for any of these attributes. 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. A delegation 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 7). Those RLOCs are returned in Map-Referral messages when the DDT Node receives a DDT Map-Request with an XEID that matches a delegation. DDT Nodes may also have a list of "hints", which are XEID-Prefixes, for which it is no authoritative. Each of such XEID-Prefixes "hints" includes the list of RLOCs of the DDT Nodes authoritative for the XEID-Prefix. The list of "hints" is statically configured similarly to delegations. 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, namely, for all valid 3-tuples (DBID, IID, AFI) and their EID-Prefixes. The root DDT Nodes is the starting point for a XEID-Prefix lookup via a DDT Map-Request. However, not all DDT Map-Request will go through a root DDT Nodes thanks to the DDT Map-Referral Cache maintained by intermediate nodes (see Section 6 for details). The root DDT Node in a particular instantiation of LISP-DDT MUST be configured, at a minimum, to cover all EID space of all tuples defined in the instantiation. Saucez & Iannone Expires 4 September 2025 [Page 8] Internet-Draft LISP-DDT March 2025 5. The DDT Map-Referral Message This specification defines a new LISP message called the DDT Map- Referral message. A DDT Map-Referral message is sent by a DDT Node to a DDT Client in response to a DDT Map-Request message. The message consists of an action code along with delegation information about the XEID-Prefix that matches the requested XEID. 5.1. Map-Referral Message Format The format of the Map-Referral message is depicted in Figure 1. 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-Prefix-AFI | o +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ r | EID-Prefix ... | d +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | /| Reserved | | R +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | e | Reserved |R| Loc-AFI | | f +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | \~ Locator ~ | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | ~ Signatures Section ~ +-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Figure 1: Map-Referral message format. Type: DDT Map-Referral type 6, as allocated in [RFC9301]. Record Count: As defined in Section 5.4 of [RFC9301]. Nonce: As defined in Section 5.4 of [RFC9301]. Record TTL: As defined in Section 5.4 of [RFC9301]. Saucez & Iannone Expires 4 September 2025 [Page 9] Internet-Draft LISP-DDT March 2025 Referral Count: This is the number of referral records in this message. A referral record is comprised of that portion of the packet labeled "Ref" and occurs the number of times equal to Referral Count. EID mask-len: As defined in Section 5.4 of [RFC9301]. ACT: The DDT Action (ACT) field of the in a Map-Referral message encodes one of the action types defined in Section 5.2. Note that, despite the same position and same name as in Map-Reply messages defined in [RFC9301], the actions in DDT Map-Referrals message are different from the ones in Map-Replies. A: The Authoritative bit CAN only be set to 1 by a DDT Node that is authoritative for the XEID-Prefix. I; Incomplete (I) bit indicating that a DDT Node's Referral Set of locators is incomplete and the receiver of this message SHOULD NOT cache the referral (see Section 5.2 for details). SigCnt: Indicates the number of signatures sections present in the Record. If SigCnt is larger than 0, the signature information captured in a Signature section as described in Section 5.5 will be appended to the Record. The number of Signature sections at the end of the Record MUST match the SigCnt. Map Version Number: As defined in [RFC9302]. EID-Prefix-AFI: As defined in Section 5.4 of [RFC9301]. XEID-Prefix: The requested XEID-Prefix. Uses the LCAF type 2 [RFC8060] to encode the IID and IP address prefix that form the XEID. It can also use natively IPv4 or IPv6 addresses, in this case the IID has the implicit default value of 0. The EID-Prefix- AFI MUST be set accordingly. R bit: As defined in Section 5.4 of [RFC9301]. Loc-AFI: AFI of the Locator field. Values for this field include the value 16387 of the LISP Canonical Address Format (LCAF) [RFC8060]. LCAF Security Key Type 11 is used to store security material associated to the locator. DDT Nodes and DDT Map-Servers uses this LCAF Type to include public keys associated with their child DDT Nodes for an XEID-Prefix Map-Referral Record. 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. Saucez & Iannone Expires 4 September 2025 [Page 10] Internet-Draft LISP-DDT March 2025 Signatures Section: When present this section contain one (or more) signature sections containing a signature covering the whole DDT Map-Referral message and the related information necessary for its verification. See Section 5.5 for the details. Fields marked as "reserved" MUST be sent as 0 (zero) and MUST be ignored on reception. 5.2. Action Codes The possible values of the action field are defined hereafter, where the number in parenthesis indicated the decimal value of the 3-bit ACT filed. 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 record with additional information, most significantly, the set of RLOCs to which the XEID-Prefix has been delegated, which 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 6.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 a Map- Reply 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. 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 6.1.2 for details. Replace old Map-Request with new \ List? / use new Map-Request Nonce +------+--------+ |No V +---------------+ / Match in DDT \ No | Map-Referral +--> Send Negative Map-Reply \ Cache? / (unlikely event, as root or hint +------+--------+ configured on every Map-Resolver) |Yes V +---------------+ / Match type \ Yes | DELEGATION-HOLE? +--> Send Negative Map-Reply \ / +------+--------+ |No V +---------------+ / Match type \ Yes | MS-ACK? +--> Forward DDT Map-Request to \ / Map-Server +------+--------+ |No o Add Map-Request to Pending Request List Forward DDT Map-Request without security material A.2. Map-Resolver Processing of Map-Referral Message A.2.1. Pseudo-code Summary if ( authentication signature validation failed ) { silently drop } if ( no Pending Request List entry matched by Map-Referral Nonce ) { silently drop } if ( XEID-Prefix in Map-Referral less specific than last used ) { if ( gone through root ) { silently drop } else { send Map-Request to root Saucez & Iannone Expires 4 September 2025 [Page 27] Internet-Draft LISP-DDT March 2025 } } switch (map_referral_type) { case NOT-AUTHORITATIVE: if ( gone through root ) { return Negative Map-Reply to requester } else { send Map-Request to root } case DELEGATION-HOLE: Store in DDT Map-Referral Cache send Negative Map-Reply to requester case MS-REFERRAL: if ( Map-Referral RLOC Set contains last used RLOC ) { if ( gone through root ) { return Negative Map-Reply to requester } else { send Map-Request to root } } else { Store in DDT Map-Referral Cache follow Map-Referral with LISP-SEC security material } case NODE-REFERRAL: if ( Map-Referral RLOCs Set contains last used RLOC ) { if ( gone through root ) { return Negative Map-Reply to requester } else { send Map-Request to root } } else { Store in DDT Map-Referral Cache follow Map-Referral without LISP-SEC security material } case MS-ACK: if ( Map-Referral has no LISP-SEC security material ) { resend Map-Request with LISP-SEC security material if { !incomplete } { Store in DDT Map-Referral Cache } } Saucez & Iannone Expires 4 September 2025 [Page 28] Internet-Draft LISP-DDT March 2025 case MS-NOT-REGISTERED: if ( all Map-Server delegations not tried ) { follow Map-Referral without LISP-SEC security material if ( !incomplete ) { Store in DDT Map-Referral Cache } } else { send Negative Map-Reply to requester if { !incomplete } { Store in DDT Map-Referral Cache } } case DEFAULT: Silently Drop } A.2.2. Decision Tree Diagram +------------+ /Authetication \ No | signature +-> Silently Drop \valid? / +------+-----+ |Yes v +------------+ / In Pending \ No | Request +-> Silently Drop \ List? / +------+-----+ |Yes v +------------+ / XEID-Pfx less\ Yes | specific than +-> Silently Drop \ last used? / +------+-----+ |No v +----------------------------------------------+ Unkonwn | What is the Map-Referral type? +---------+ +--+---------+------+-------+---------+------+-+ v / | | | | \ Silently | | | | MS-ACK DEL-HOLE Drop | | | | | \ | | NODE-REF MS-REF | v | | | | | Cache & Return Saucez & Iannone Expires 4 September 2025 [Page 29] Internet-Draft LISP-DDT March 2025 | | | | v Negative Map-Reply | | | | +---------+ | NOT-AUTH | | / LISP-SEC \ Yes | | v | | material +-> Resend Request | | +-------+ \ \ stripped? / with LISP-SEC | |Yes/Pfx equal\ \ +----+----+ | *--+ last used?| \ | No | | \ / \ + MS-NOT-REGISTERED| +---+---+ | \ | + |No | \ | / v | \ | + Cache & Follow | \ | v Map-Referral v \ | +----------+ +-------+ + | /Gone through\ Yes/Pfx equal\ | | | root? |<-------+ last used?| | | \ / \ / | | +----------+ +---+---+ | | |No |Yes |No | | v v | | | Send Req Send Negative v | | to root Map-Reply Cache & Follow | | Map-Referral with/ | LISP-SEC / +-> Do Not Cache v v | +--------+ +--------+ Yes / Other MS \ Yes +-------------+ /Incomplete\ | not tried? +-->|Follow other MS|---->| bit set? | \ / +-------------+ \ / +----+---+ +--------+ No |No +---------------------+ ^ | +---->|Send Negative Map-Reply|----+ +-> Cache +---------------------+ A.3. DDT Node Processing of DDT Map-Request Message A.3.1. Pseudo-code Summary Saucez & Iannone Expires 4 September 2025 [Page 30] Internet-Draft LISP-DDT March 2025 if ( I am not authoritative ) { send Map-Referral NOT_AUTHORITATIVE & set "Incomplete" bit } else if ( delegation exists ) { if ( delegated Map-Servers ) { send Map-Referral MS_REFERRAL } else { send Map-Referral NODE_REFERRAL } } else { if ( EID in site ) { if ( site registered ) { forward Map-Request to ETR if ( Map-Server peers configured ) { send Map-Referral MS_ACK } else { send Map-Referral MS_ACK & set"Incomplete" bit } } else { if ( Map-Server peers configured ) { send Map-Referral MS_NOT_REGISTERED } else { send Map-Referral MS_NOT_REGISTERED & set"Incomplete" bit } } } else { send Map-Referral DELEGATION_HOLE } } A.3.2. Decision Tree Diagram Saucez & Iannone Expires 4 September 2025 [Page 31] Internet-Draft LISP-DDT March 2025 +------------+ / Am I \ No | authoritative? +-> Return NOT-AUTHORITATIVE & \ / I-bit = 1 +------+-----+ |Yes v +------------+ +------------+ / Delegation \ Yes / Delegations \ Yes | exists? +--->| are +--> Return MS-REFERRAL \ / \ Map-Servers? / +------+-----+ +------+-----+ |No |No v +-> Return NODE-REFERRAL +------------+ / EID in Site \ No | configuration? +-> Return DELEGATION-HOLE \ / +------+-----+ |Yes v +------------+ +------------+ / Site \ No / Map-Server \ Yes | Registered? +--->| peers +--+ \ / \ configured? / v +------+-----+ +------+-----+ Return MS-NOT-REGISTERED |Yes |No v v +----------------+ Return MS-NOT-REGISTERED & | Forward | I-bit=1 | Map-Request | | to ETR | +--------+-------+ | v +------------+ / Map-Server \ No | peers +-> Return MS-ACK & \ configured / I-bit=1 +------+-----+ |Yes v Return MS-ACK Saucez & Iannone Expires 4 September 2025 [Page 32] Internet-Draft LISP-DDT March 2025 Appendix B. Generic DDT Example This section shows an example of DDT tree and several possible scenarios of Map-Requests coming to a Map-Resolver and subsequent iterative DDT referrals. In this example, RLOCs of DDT Nodes are shown in the IPv4 address space while the EIDs are in the IPv6 address space. B.1. Reference DDT Tree Topology To show how referrals are followed to find the RLOCs for a number of different requests, the DDT topology in Figure 3 is used. +---------------------+ +---------------------+ | DDT-Root1: 192.0.2.1| | DDT-Root2: 192.0.2.2| |authoritative: ::/0 | |authoritative: ::/0 | +-----------+---------+ +---------+-----------+ | \/ | | /\ | | / \ | V V V V +-----------------------+ +-----------------------+ | DDT-Node1: 192.0.2.11 | | DDT-Node2: 192.0.2.12 | | authoritative: | | authoritative: | | 2001:db8::/32 | | 2001:db8::/32 | +-------------+---------+ +---------+-------------+ | \/ | | /\ | | / \ | V V V V +-------------------------+ +------------------------+ |Map-Server1: 192.0.2.101 | | DDT-Node3: 192.0.2.201 | | authoritative: | | authoritative: | | 2001:db8:0100::/40 | | 2001:db8:0500::/40 | |Site1: 2001:db8:0103::/48| +---+----------------+---+ |Site2: 2001:db8:0104::/48| | | +-------------------------+ | | V V +---------------------------+ +---------------------------+ | Map-Server2: 192.0.2.211 | | Map-Server3: 192.0.2.221 | | authoritative: | | authoritative: | | 2001:db8:0500::/48 | | 2001:db8:0501::/48 | |Site3: 2001:db8:0500:1::/64| |Site5: 2001:db8:0501:8::/64| |Site4: 2001:db8:0500:2::/64| |Site6: 2001:db8:0501:9::/64| +---------------------------+ +---------------------------+ Figure 3: Reference DDT tree topology. Saucez & Iannone Expires 4 September 2025 [Page 33] Internet-Draft LISP-DDT March 2025 DDT Root nodes are configured with IP addresses 192.0.2.1 and 192.0.2.2. DDT Map-Resolvers are configured with default referral cache entries for these addresses. The DDT Root nodes delegate 2001:db8::/32 to two DDT nodes, DDT-Node1 and DDT-Node2, having IP addresses 192.0.2.11 and 192.0.2.12 respectively. DDT-Node1 and DDT-Node2 delegate 2001:db8:0100::/40 to a Map-Server1, who has RLOC 192.0.2.101. Map-Server1 is configured to allow ETRs to register the sub-prefixes 2001:db8:0103::/48 and 2001:db8:0104::/48. DDT-Node1 and DDT-Node2 also delegate 2001:db8:0500::/40 to DDT-Node3 who uses the address 192.0.2.201. DDT-Node3 further delegates 2001:db8:0500::/48 to Map-Server2, who has RLOC 192.0.2.211, and 2001:db8:0501::/48 to Map-Server3, who has RLOC 192.0.2.221. Map-Server2 is configured to allow ETRs to register the sub-prefixes 2001:db8:0500:1::/64 and 2001:db8:0500:2::/64. Map-Server3 is configured to allow ETRs to register the sub-prefixes 2001:db8:0501:8::/64 and 2001:db8:0501:9::/64. B.2. Lookup EID registered at with Map-Server1 The first example shows a DDT Map-Resolver following a delegation from the root to a DDT Node followed by another delegation to a DDT Map-Server. The example assumes that DDT Map-Referral Caches contain only the default configuration. ITR1 sends an ECM Map-Request for 2001:db8:0103:1::1 to one of its configured (DDT) Map-Resolvers. The DDT Map-Resolver proceeds as follows: 1. Send a DDT Map-Request (for 2001:db8:0103:1::1) to one of the root DDT Nodes (192.0.2.1 or 192.0.2.2). 2. Receive (and save in the DDT Map-Referral Cache) the Map-Referral for EID-Prefix 2001:db8::/32, action code NODE-REFERRAL, RLOC set (192.0.2.11, 192.0.2.12). 3. Send a DDT Map-Request to 192.0.2.11 or 192.0.2.12. 4. Receive (and save in the DDT Map-Referral Cache) the Map-Referral for EID-Prefix 2001:db8:0100::/40, action code MS-REFERRAL, RLOC set (192.0.2.101). Saucez & Iannone Expires 4 September 2025 [Page 34] Internet-Draft LISP-DDT March 2025 5. Send a DDT Map-Request to 192.0.2.101; if the ITR-originated ECM Map-Request had a LISP-SEC signature, it is included. 6. The DDT Map-Server1 (192.0.2.101) decapsulates the DDT Map- Request and forwards the Map-Request to the registered Site1 ETR for 2001:db8:0103::/48. 7. The DDT Map-Server1 (192.0.2.101) sends a DDT Map-Referral message for EID-Prefix 2001:db8:0103::/48, action code MS-ACK, to the DDT Map-Resolver. 8. The DDT Map-Resolver receives the Map-Referral message with action code MS-ACK and removes the request for 2001:db8:0103:1::1 from the Pending Request List. 9. Site1's ETR for 2001:db8:0103::/48 receives the Map-Request forwarded by Map-Server1 and sends a Map-Reply to ITR1. B.3. Lookup EID registered at with Map-Server3 This example shows a three-level delegation: root to first DDT node, first DDT Node to second DDT Node, and second DDT Node to DDT Map- Server. The example assumes that DDT Map-Referral Caches contain only the default configuration. ITR2 sends an ECM Map-Request for 2001:db8:0501:8:4::1 to one of its configured DDT Map-Resolvers, which are different from those for ITR1. The DDT Map-Resolver proceeds as follows: 1. Send a DDT Map-Request (for 2001:db8:0501:8:4::1) to one of the root DDT Nodes (192.0.2.1 or 192.0.2.2). 2. Receive (and save in the DDT Map-Referral Cache) the Map- Referral for EID-Prefix 2001:db8::/32, action code NODE- REFERRAL, RLOC set (192.0.2.11, 192.0.2.12). 3. Send a DDT Map-Request to 192.0.2.11 or 192.0.2.12. 4. Receive (and save in the DDT Map-Referral Cache) the DDT Map- Referral for EID-Prefix 2001:db8:0500::/40, action code NODE- REFERRAL, RLOC set (192.0.2.201). 5. Send a DDT Map-Request to 192.0.2.201. 6. Receive (and save in the DDT Map-Referral Cache) the DDT Map- Referral for EID-Prefix 2001:db8:0501::/48, action code MS- REFERRAL, RLOC set (192.0.2.221). Saucez & Iannone Expires 4 September 2025 [Page 35] Internet-Draft LISP-DDT March 2025 7. Send a DDT Map-Request to 192.0.2.221; if the ITR-originated ECM Map-Request had a LISP-SEC signature, it is included. 8. Map-Server3 (192.0.2.221) decapsulates the DDT Map-Request and forwards the Map-Request to a registered Site5 ETR for 2001:db8:0501:8::/64. 9. Map-Server3 (192.0.2.221) sends a DDT Map-Referral message for EID-Prefix 2001:db8:0501:8::/64, action code MS-ACK, to the DDT Map-Resolver. 10. The DDT Map-Resolver receives a Map-Referral message with action code MS-ACK and removes the request for 2001:db8:0501:8:4::1 from the Pending Request List. 11. Site5's ETR for 2001:db8:0501:8::/64 receives the Map-Request forwarded by Map-Server3 and sends a Map-Reply to ITR2. B.4. Lookups using cached DDT Map-Referrals to Map-Servers This example shows a lookup for 2001:db8:0104:2::2, where the DDT Map-Resolver uses a saved DDT Map-Referral Cache entry to skip the iterative referral process and go directly to a DDT Map-Server. In this case, ITR1 uses the same Map-Resolver used in the example in Appendix B.2. It sends an ECM Map-Request for 2001:db8:0104:2::2 to that DDT Map-Resolver. The DDT Map-Resolver finds an MS-REFERRAL cache entry for 2001:db8:0100::/40 with RLOC set 192.0.2.101 and proceeds as follows: 1. Send directly a DDT Map-Request (for 2001:db8:0104:2::2) to 192.0.2.101; if the ITR-originated ECM Map-Request had a LISP-SEC signature, it is included. 2. Map-Server1 (192.0.2.101) decapsulates the DDT Map-Request and forwards the Map-Request to the registered Site2 ETR for 2001:db8:0104::/48. 3. Map-Server1 (192.0.2.101) sends a DDT Map-Referral message for EID-Prefix 2001:db8:0104::/48, action code MS-ACK, to the DDT Map-Resolver. 4. The DDT Map-Resolver receives the DTT Map-Referral with action code MS-ACK and removes the request for 2001:db8:0104:2::2 from the Pending Request List. 5. Site2's ETR for 2001:db8:0104::/48 receives the Map-Request from Map-Server1 and sends a Map-Reply to ITR1. Saucez & Iannone Expires 4 September 2025 [Page 36] Internet-Draft LISP-DDT March 2025 B.5. Lookup using cached DDT Map-Referrals to DDT Nodes This example shows how a DDT Map-Resolver uses a DDT Map-Referral Cache entry to start the referral process at a non-root, intermediate DDT node for the prefix 2001:db8:0500:2:4::1, which is similar to one previously requested. In this case, ITR2 uses the same Map-Resolver used in the example in Appendix B.3. It sends an ECM Map-Request for 2001:db8:0500:2:4::1 to that DDT Map-Resolver, which finds a NODE-REFERRAL cache entry for 2001:db8:0500::/40 with RLOC set 192.0.2.201. It proceeds as follows: 1. Send a DDT Map-Request (for 2001:db8:0500:2:4::1) to 192.0.2.201. 2. Receive (and save in the referral cache) the Map-Referral for EID-Prefix 2001:db8:0500::/48, action code MS-REFERRAL, RLOC set (192.0.2.211). 3. Send a DDT Map-Request to 192.0.2.211; if the ITR-originated Encapsulated Map-Request had a LISP-SEC signature, it is included. 4. Map-Server2 (192.0.2.211) decapsulates the DDT Map-Request and forwards the Map-Request to the registered Site4 ETR for 2001:db8:0500:2::/64. 5. Map-Server3 (192.0.2.211) sends a Map-Referral message for EID- Prefix 2001:db8:0500:2::/64, action code MS-ACK, to the DDT Map- Resolver. 6. The DDT Map-Resolver receives the Map-Referral (MS-ACK) and removes the request for 2001:db8:0500:2:4::1 from the Pending Request List. 7. Site4's ETR for 2001:db8:0500:2::/64 receives the Map-Request and sends a Map-Reply to ITR2. B.6. Lookup of a non-existent EID This example shows the lookup of 2001:db8:0500::1/128, which uses the cached MS-REFERRAL for 2001:db8:0500::/48 learned because of previous lookups at the DDT Map-Server at 192.0.2.211. The DDT Map-Resolver proceeds as follows: 1. Send a DDT Map-Request for 2001:db8:0500::1 to 192.0.2.211; if the ITR-originated ECM Map-Request has a LISP-SEC signature, it is included. Saucez & Iannone Expires 4 September 2025 [Page 37] Internet-Draft LISP-DDT March 2025 2. Map-Server2 (192.0.2.211), which is authoritative for 2001:db8:0500::/48, does not have a matching delegation for 2001:db8:0500::1. It responds with a DDT Map-Referral message for 2001:db8:0500::/64, action code DELEGATION-HOLE, to the DDT Map-Resolver. The prefix 2001:db8:0500::/64 is used because it is the least-specific prefix that does match the requested EID but does not match one of the configured delegations (2001:db8:0500:1::/64 and 2001:db8:0500:2::/64). 3. The DDT Map-Resolver receives the delegation, adds a Negative DDT Map-Referral Cache entry for 2001:db8:0500::/64, removes the request for 2001:db8:0500::1 from the Pending Request list, and returns a Negative Map-Reply to ITR2. Contributors Vince Fuller VAF.NET Internet Consulting Email: vince.fuller@gmail.com Darrel Lewis ICANN Los Angeles, CA 90292 United States of America Email: darrel.lewis@icann.org Vina Ermagan Google United States of America Email: ermagan@gmail.com Amit Jain Juniper Networks Email: atjain@juniper.net Anton Smirnov Cisco Systems, Inc. De Kleetlaan 6a 1831 Diegem Belgium Email: as@cisco.com Saucez & Iannone Expires 4 September 2025 [Page 38] Internet-Draft LISP-DDT March 2025 Authors' Addresses Damien Saucez (editor) Inria France Email: damien.saucez@inria.fr Luigi Iannone (editor) Huawei Technologies France S.A.S.U. 18, Quai du Point du Jour 92100 Boulogne-Billancourt France Email: luigi.iannone@huawei.com Saucez & Iannone Expires 4 September 2025 [Page 39]