draft-ietf-lisp-ddt-09.txt   rfc8111.txt 
Network Working Group V. Fuller Internet Engineering Task Force (IETF) V. Fuller
Internet-Draft Request for Comments: 8111 VAF.NET Internet Consulting
Intended status: Experimental D. Lewis Category: Experimental D. Lewis
Expires: July 22, 2017 V. Ermagan ISSN: 2070-1721 V. Ermagan
Cisco Systems Cisco Systems
A. Jain A. Jain
Juniper Networks Juniper Networks
A. Smirnov A. Smirnov
Cisco Systems Cisco Systems
January 18, 2017 May 2017
LISP Delegated Database Tree Locator/ID Separation Protocol Delegated Database Tree (LISP-DDT)
draft-ietf-lisp-ddt-09
Abstract Abstract
This document describes the LISP Delegated Database Tree (LISP-DDT), This document describes the Locator/ID Separation Protocol Delegated
a hierarchical, distributed database which embodies the delegation of Database Tree (LISP-DDT), a hierarchical distributed database that
authority to provide mappings from LISP Endpoint Identifiers (EIDs) embodies the delegation of authority to provide mappings from LISP
to Routing Locators (RLOCs). It is a statically-defined distribution Endpoint Identifiers (EIDs) to Routing Locators (RLOCs). It is a
of the EID namespace among a set of LISP-speaking servers, called DDT statically defined distribution of the EID namespace among a set of
nodes. Each DDT node is configured as "authoritative" for one or LISP-speaking servers called "DDT nodes". Each DDT node is
more EID-prefixes, along with the set of RLOCs for Map Servers or configured as "authoritative" for one or more EID-prefixes, along
"child" DDT nodes to which more-specific EID-prefixes are delegated. with the set of RLOCs for Map-Servers or "child" DDT nodes to which
more-specific EID-prefixes are delegated.
Status of This Memo Status of This Memo
This Internet-Draft is submitted in full conformance with the This document is not an Internet Standards Track specification; it is
provisions of BCP 78 and BCP 79. published for examination, experimental implementation, and
evaluation.
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 http://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six months This document defines an Experimental Protocol for the Internet
and may be updated, replaced, or obsoleted by other documents at any community. This document is a product of the Internet Engineering
time. It is inappropriate to use Internet-Drafts as reference Task Force (IETF). It represents the consensus of the IETF
material or to cite them other than as "work in progress." 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.
This Internet-Draft will expire on July 22, 2017. Information about the current status of this document, any errata,
and how to provide feedback on it may be obtained at
http://www.rfc-editor.org/info/rfc8111.
Copyright Notice Copyright Notice
Copyright (c) 2017 IETF Trust and the persons identified as the Copyright (c) 2017 IETF Trust and the persons identified as the
document authors. All rights reserved. document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents Provisions Relating to IETF Documents
(http://trustee.ietf.org/license-info) in effect on the date of (http://trustee.ietf.org/license-info) in effect on the date of
publication of this document. Please review these documents publication of this document. Please review these documents
carefully, as they describe your rights and restrictions with respect carefully, as they describe your rights and restrictions with respect
to this document. Code Components extracted from this document must to this document. Code Components extracted from this document must
include Simplified BSD License text as described in Section 4.e of include Simplified BSD License text as described in Section 4.e of
the Trust Legal Provisions and are provided without warranty as the Trust Legal Provisions and are provided without warranty as
described in the Simplified BSD License. described in the Simplified BSD License.
Table of Contents Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 1. Introduction ....................................................4
2. Requirements Language . . . . . . . . . . . . . . . . . . . . 4 2. Requirements Language ...........................................5
3. Definition of Terms . . . . . . . . . . . . . . . . . . . . . 5 3. Definitions of Terms ............................................6
4. Database organization . . . . . . . . . . . . . . . . . . . . 7 4. Database Organization ...........................................8
4.1. XEID prefixes . . . . . . . . . . . . . . . . . . . . . . 7 4.1. XEID-Prefixes ..............................................8
4.2. DDT database tree structure . . . . . . . . . . . . . . . 7 4.2. Structure of the DDT Database ..............................8
4.3. Configuring prefix delegation . . . . . . . . . . . . . . 8 4.3. Configuring Prefix Delegation ..............................9
4.3.1. The root DDT node . . . . . . . . . . . . . . . . . . 9 4.3.1. The Root DDT Node ..................................10
5. DDT Map-Request . . . . . . . . . . . . . . . . . . . . . . . 9 5. DDT Map-Request ................................................10
6. The Map-Referral message . . . . . . . . . . . . . . . . . . 10 6. The Map-Referral Message .......................................11
6.1. Action codes . . . . . . . . . . . . . . . . . . . . . . 10 6.1. Action Codes ..............................................11
6.2. Referral set . . . . . . . . . . . . . . . . . . . . . . 11 6.2. Referral Set ..............................................12
6.3. Incomplete flag . . . . . . . . . . . . . . . . . . . . . 11 6.3. "Incomplete" Flag .........................................12
6.4. Map-Referral Message Format . . . . . . . . . . . . . . . 11 6.4. Map-Referral Message Format ...............................13
6.4.1. SIG section . . . . . . . . . . . . . . . . . . . . . 14 6.4.1. Signature Section ..................................15
7. DDT network elements and their operation . . . . . . . . . . 15 7. DDT Network Elements and Their Operation .......................17
7.1. DDT node . . . . . . . . . . . . . . . . . . . . . . . . 15 7.1. DDT Node ..................................................17
7.1.1. Match of a delegated prefix (or sub-prefix) . . . . . 15 7.1.1. Matching of a Delegated Prefix (or Sub-prefix) .....17
7.1.2. Missing delegation from an authoritative prefix . . . 16 7.1.2. Missing Delegation from an Authoritative Prefix ....18
7.2. DDT Map Server . . . . . . . . . . . . . . . . . . . . . 16 7.2. DDT Map-Server ............................................18
7.3. DDT client . . . . . . . . . . . . . . . . . . . . . . . 17 7.3. DDT Client ................................................18
7.3.1. Queuing and sending DDT Map-Requests . . . . . . . . 17 7.3.1. Queuing and Sending DDT Map-Requests ...............19
7.3.2. Receiving and following referrals . . . . . . . . . . 18 7.3.2. Receiving and Following Referrals ..................20
7.3.3. Handling referral errors . . . . . . . . . . . . . . 20 7.3.3. Handling Referral Errors ...........................22
7.3.4. Referral loop detection . . . . . . . . . . . . . . . 20 7.3.4. Referral Loop Detection ............................22
8. Pseudo Code and Decision Tree diagrams . . . . . . . . . . . 21
8.1. Map Resolver processing of ITR Map-Request . . . . . . . 21 8. Pseudocode and Decision Tree Diagrams ..........................23
8.1.1. Pseudo-code summary . . . . . . . . . . . . . . . . . 21 8.1. Map-Resolver Processing of ITR Map-Request ................23
8.1.2. Decision tree diagram . . . . . . . . . . . . . . . . 21 8.1.1. Pseudocode Summary .................................23
8.2. Map Resolver processing of Map-Referral message . . . . . 22 8.1.2. Decision Tree Diagram ..............................24
8.2.1. Pseudo-code summary . . . . . . . . . . . . . . . . . 22 8.2. Map-Resolver Processing of Map-Referral Message ...........25
8.2.2. Decision tree diagram . . . . . . . . . . . . . . . . 24 8.2.1. Pseudocode Summary .................................25
8.3. DDT Node processing of DDT Map-Request message . . . . . 25 8.2.2. Decision Tree Diagram ..............................27
8.3.1. Pseudo-code summary . . . . . . . . . . . . . . . . . 25 8.3. DDT Node Processing of DDT Map-Request Message ............28
8.3.2. Decision tree diagram . . . . . . . . . . . . . . . . 27 8.3.1. Pseudocode Summary .................................28
9. Example topology and request/referral following . . . . . . . 27 8.3.2. Decision Tree Diagram ..............................30
9.1. Lookup of 2001:db8:0103:1::1/128 . . . . . . . . . . . . 30 9. Example Topology and Request/Referral Following ................31
9.2. Lookup of 2001:db8:0501:8:4::1/128 . . . . . . . . . . . 31 9.1. Lookup of 2001:db8:0103:1::1/128 ..........................33
9.3. Lookup of 2001:db8:0104:2::2/128 . . . . . . . . . . . . 32 9.2. Lookup of 2001:db8:0501:8:4::1/128 ........................34
9.4. Lookup of 2001:db8:0500:2:4::1/128 . . . . . . . . . . . 32 9.3. Lookup of 2001:db8:0104:2::2/128 ..........................35
9.5. Lookup of 2001:db8:0500::1/128 (non-existent EID) . . . . 33 9.4. Lookup of 2001:db8:0500:2:4::1/128 ........................36
10. Securing the database and message exchanges . . . . . . . . . 34 9.5. Lookup of 2001:db8:0500::1/128 (Nonexistent EID) ..........37
10.1. XEID-prefix Delegation . . . . . . . . . . . . . . . . . 34 10. Securing the Database and Message Exchanges ...................37
10.2. DDT node operation . . . . . . . . . . . . . . . . . . . 35 10.1. XEID-Prefix Delegation ...................................38
10.2.1. DDT public key revocation . . . . . . . . . . . . . 35 10.2. DDT Node Operation .......................................38
10.3. Map Server operation . . . . . . . . . . . . . . . . . . 36 10.2.1. DDT Public Key Revocation .........................38
10.4. Map Resolver operation . . . . . . . . . . . . . . . . . 36 10.3. Map-Server Operation .....................................39
11. Open Issues and Considerations . . . . . . . . . . . . . . . 37 10.4. Map-Resolver Operation ...................................39
12. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 37 11. Open Issues and Considerations ................................40
13. Security Considerations . . . . . . . . . . . . . . . . . . . 37 12. IANA Considerations ...........................................41
14. References . . . . . . . . . . . . . . . . . . . . . . . . . 38 13. Security Considerations .......................................41
14.1. Normative References . . . . . . . . . . . . . . . . . . 38 14. References ....................................................42
14.2. Informative References . . . . . . . . . . . . . . . . . 38 14.1. Normative References .....................................42
Appendix A. Acknowledgments . . . . . . . . . . . . . . . . . . 39 14.2. Informative References ...................................43
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 40 Acknowledgments ...................................................44
Authors' Addresses ................................................44
1. Introduction 1. Introduction
LISP [RFC6830] specifies an architecture and mechanism for replacing The Locator/ID Separation Protocol (LISP) [RFC6830] specifies an
the addresses currently used by IP with two separate name spaces: architecture and mechanism for replacing the addresses currently used
Endpoint Identifiers (EIDs), used end-to-end for terminating by IP with two separate namespaces:
transport-layer associations, and Routing Locators (RLOCs), which are
bound to topological location, and are used for routing and
forwarding through the Internet infrastructure.
[RFC6833] specifies an interface between database storing EID-to-RLOC o Endpoint Identifiers (EIDs), used end to end for terminating
mappings and LISP devices which need this information for packet transport-layer associations, and
forwarding. Internal organization of such database is out 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 architecture for database of LISP EID-to-RLOC o Routing Locators (RLOCs), which are bound to topological locations
mappings with emphasis on high scalability. LISP-DDT is a and are used for routing and forwarding through the Internet
hierarchical distributed database, which embodies the delegation of infrastructure.
authority to provide mappings, i.e. its internal structure mirrors
the hierarchical delegation of address space. It also provides [RFC6833] specifies an interface between a database storing
delegation information to Map Resolvers, which use the information to EID-to-RLOC mappings and LISP devices that need this information for
locate EID-to-RLOC mappings. A Map Resolver, which needs to locate a packet forwarding. The internal organization of such a database is
given mapping, will follow a path through the tree-structured beyond the scope of [RFC6833]. Multiple architectures of the
database, contacting, one after another, the DDT nodes along that database have been proposed, each having its advantages and
path until it reaches the leaf DDT node(s) authoritative for the disadvantages (see, for example, [RFC6836] and [RFC6837]).
mapping it is seeking.
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 LISP offers a general-purpose mechanism for mapping between EIDs and
RLOCs. In organizing a database of EID to RLOC mappings, this RLOCs. In organizing a database of EID-to-RLOC mappings, this
specification extends the definition of the EID numbering space by specification extends the definition of the EID numbering space by
logically prepending and appending several fields for purposes of logically prepending and appending several fields for purposes of
defining the database index key: Database-ID (DBID, 16 bits), defining the database index key:
Instance identifier (IID, 32-bits), Address Family Identifier (16
bits), and EID-prefix (variable, according to AFI value). The o Database-ID (DBID) (16 bits),
resulting concatenation of these fields is termed an "Extended EID
prefix" or XEID-prefix. 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.
LISP-DDT defines a new device type, the DDT node, that is configured LISP-DDT defines a new device type, the DDT node, that is configured
as authoritative for one or more XEID-prefixes. It also is as authoritative for one or more XEID-prefixes. It is also
configured with the set of more-specific sub-prefixes that are configured with the set of more-specific sub-prefixes that are
further delegated to other DDT nodes. To delegate a sub-prefix, the 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 "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 that is authoritative for the sub-prefix. Each RLOC either points to
a DDT Map Server to which an Egress Tunnel Router (ETR) has 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 registered that sub-prefix or points to another DDT node in the
database tree that further delegates the sub-prefix. See [RFC6833] database tree that further delegates the sub-prefix. See [RFC6833]
for a description of the functionality of the Map Server and Map for a description of the functionality of the Map-Server and
Resolver. Note that the target of a delegation must always be an Map-Resolver. Note that the target of a delegation must always be an
RLOC (not an EID) to avoid any circular dependency. RLOC (not an EID) to avoid any circular dependency.
To provide a mechanism for traversing the database tree, LISP-DDT To provide a mechanism for traversing the database tree, LISP-DDT
defines a new LISP message type, the Map-Referral, which is returned 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 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. the sender to another DDT node that has more detailed information.
See Section 6 for the definition of the Map-Referral message. 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 To find an EID-to-RLOC mapping, a LISP-DDT client, usually a DDT
Resolver, starts by sending an Encapsulated Map-Request to a Map-Resolver, starts by sending an Encapsulated Map-Request to a
preconfigured DDT node RLOC. The DDT node responds with a Map- preconfigured DDT node RLOC. The DDT node responds with a
Referral message that either indicates that it will find the Map-Referral message indicating that either (1) it will find the
requested mapping to complete processing of the request or that the requested mapping to complete processing of the request or (2) the
DDT client should contact another DDT node that has more-specific DDT client should contact another DDT node that has more-specific
information; in the latter case, the DDT node then sends a new information; in the latter case, the DDT node then sends a new
Encapsulated Map-Request to the next DDT node and the process repeats Encapsulated Map-Request to the next DDT node and the process repeats
in an iterative manner. in an iterative manner.
Conceptually, this is similar to the way that a client of the Domain Conceptually, this is similar to the way that a client of the Domain
Name System (DNS) follows referrals (DNS responses that contain only Name System (DNS) follows referrals (DNS responses that contain only
NS records) from a series of DNS servers until it finds an answer. NS records) from a series of DNS servers until it finds an answer.
2. Requirements Language 2. Requirements Language
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and
document are to be interpreted as described in [RFC2119]. "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. Definition of Terms 3. Definitions of Terms
Extended EID (XEID): a LISP EID extended with data uniquely Extended EID (XEID): a LISP EID extended with data uniquely
identifying address space to which it belongs, such as LISP identifying the address space to which it belongs (LISP IID,
instance ID, Address Family etc. See Section 4.1 for detailed address family, etc.). See Section 4.1 for a detailed description
description of XEID data. of XEID data.
XEID-prefix: Extended EID-prefix (XEID-prefix) is a LISP EID-prefix Extended EID-prefix (XEID-prefix): a LISP EID-prefix prepended with
prepended with XEID data. An XEID-prefix is used as a key index XEID data. An XEID-prefix is used as a key index into the DDT
into the DDT database. XEID prefixes are used to describe database. XEID-prefixes are used to describe database
database organization and are not seen as a single entity in organization and are not seen as a single entity in protocol
protocol messages, though messages contain individual fields messages, though messages contain individual fields constituting
constituting XEID prefix. XEID-prefixes.
DDT node: a network infrastructure component responsible for DDT node: a network infrastructure component responsible for
specific XEID-prefix(es) and for delegation of more-specific sub- specific XEID-prefix(es) and for the delegation of more-specific
prefixes to other DDT nodes. sub-prefixes to other DDT nodes.
DDT client: a network infrastructure component that sends DDT Map- DDT client: a network infrastructure component that sends DDT
Request messages and implements the iterative following of Map- Map-Request messages and implements the iterative following of
Referral results. Typically, a DDT client will be a Map Resolver Map-Referral results. Typically, a DDT client will be a
(as defined by [RFC6833]), but it is also possible for an ITR to Map-Resolver (as defined by [RFC6833]), but it is also possible
implement DDT client functionality. for an Ingress Tunnel Router (ITR) to implement DDT client
functionality.
DDT Map Server: a DDT node that also implements Map Server DDT Map-Server: a DDT node that also implements Map-Server
functionality (forwarding Map-Requests and/or returning Map- functionality (forwarding Map-Requests and/or returning
Replies if offering proxy Map-Reply service) for a subset of its Map-Replies if offering a proxy Map-Reply service) for a subset of
delegated prefixes. Map Server functions including proxying Map- its delegated prefixes. Map-Server functions, including proxying
Replies are described in [RFC6833]. Map-Replies, are described in [RFC6833].
DDT Map Server peers: list of all DDT Map Servers performing Map DDT Map-Server peers: a list of all DDT Map-Servers performing
Server functionality for the same prefix. If peers are configured Map-Server functionality for the same prefix. If peers are
on a DDT Map Server then the latter will provide complete configured on a DDT Map-Server, then the latter will provide
information about the prefix in its Map-Replies; otherwise the Map complete information about the prefix in its Map-Replies;
Server will mark returned reply as potentially incomplete. otherwise, the Map-Server will mark the returned reply as
potentially incomplete.
DDT Map Resolver: a network infrastructure element which implements DDT Map-Resolver: a network infrastructure element that implements
both the DDT client functionality and Map Resolver functionality both DDT client functionality and Map-Resolver functionality as
as defined by [RFC6833]. DDT Map Resolver accepts Map-Requests defined by [RFC6833]. A DDT Map-Resolver accepts Map-Requests
from ITRs, sends DDT Map-Requests to DDT nodes and implements from ITRs, sends DDT Map-Requests to DDT nodes, and implements the
iterative following of Map-Referrals. Note that Map Resolvers do iterative following of Map-Referrals. Note that Map-Resolvers
not respond to clients which sent Map-Requests, they only ensure 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 that the Map-Request has been forwarded to a LISP device (ETR or
proxy Map-Server) which will provide authoritative response to the proxy Map-Server) that will provide an authoritative response to
original requestor. A DDT Map Resolver will typically maintain a the original requester. A DDT Map-Resolver will typically
cache of previously received Map-Referral message results maintain a cache (termed the "referral cache") of previously
containing RLOCs for DDT nodes responsible for XEID- prefixes of received Map-Referral message results containing RLOCs for DDT
interest (termed the "referral cache"). nodes responsible for XEID-prefixes of interest.
Encapsulated Map-Request: a LISP Map-Request carried within an Encapsulated Map-Request: a LISP Map-Request that is carried within
Encapsulated Control Message, which has an additional LISP header an Encapsulated Control Message and that has an additional LISP
prepended. Sent to UDP destination port 4342. The "outer" header prepended to it. Sent to UDP destination port 4342. The
addresses are globally-routable IP addresses, also known as RLOCs. "outer" addresses are globally routable IP addresses, also known
Used by an ITR when sending to a Map Resolver and by a Map Server as RLOCs. Used by an ITR when sending a Map-Request to a
when forwarding a Map-Request to an ETR as documented in LISP-MS Map-Resolver and by a Map-Server when forwarding a Map-Request to
[RFC6833]. an ETR as documented in [RFC6833].
DDT Map-Request: an Encapsulated Map-Request sent by a DDT client to 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 a DDT node. The "DDT-originated" flag is set in the encapsulation
header indicating that the DDT node should return Map-Referral header, indicating that the DDT node should return Map-Referral
messages if the Map-Request EID matches a delegated XEID-prefix messages if the Map-Request EID matches a delegated XEID-prefix
known to the DDT node. Section 7.3.1 describes how DDT Map- known to the DDT node. Section 7.3.1 describes how DDT
Requests are sent. Section 5 defines position of the "DDT- Map-Requests are sent. Section 5 defines the position of the
originated" flag in the Encapsulated Control Message header. "DDT-originated" flag in the Encapsulated Control Message header.
Authoritative XEID-prefix: an XEID-prefix delegated to a DDT node Authoritative XEID-prefix: an XEID-prefix delegated to a DDT node
and for which the DDT node may provide further delegations of and for which the DDT node may provide further delegations of
more-specific sub-prefixes. more-specific sub-prefixes.
Map-Referral: a LISP message sent by a DDT node in response to a 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 Map-Request for an XEID that matches a configured XEID-prefix
delegation. A non-negative Map-Referral includes a "referral", a delegation. A non-Negative Map-Referral includes a "referral" --
set of RLOCs for DDT nodes that have information about the more a set of RLOCs for DDT nodes that have information about the
specific XEID prefix covering requested XEID; a DDT client more-specific XEID-prefix covering the requested XEID; a DDT
"follows the referral" by sending another DDT Map-Request to one client "follows the referral" by sending another DDT Map-Request
of those RLOCs to obtain either an answer or another referral to to one of those RLOCs to obtain either an answer or another
DDT nodes responsible for even more specific XEID-prefix. See referral to DDT nodes responsible for an XEID-prefix that is even
Section 7.1 and Section 7.3.2 for details on the sending and more specific. See Sections 7.1 and 7.3.2 for details on the
processing of Map-Referral messages. sending and processing of Map-Referral messages.
Negative Map-Referral: an answer from an authoritative DDT node that Negative Map-Referral: an answer from an authoritative DDT node that
there is no mapping for the requested XEID. Negative Map-Referral there is no mapping for the requested XEID. A Negative
is a Map-Referral sent in response to a DDT Map-Request that Map-Referral is a Map-Referral sent in response to a DDT
matches an authoritative XEID-prefix but for which there is no Map-Request that matches an authoritative XEID-prefix but for
delegation configured (or no ETR registration if sent by a DDT which there is no delegation configured (or no ETR registration,
Map-Server). if sent by a DDT Map-Server).
Pending Request List: the set of outstanding requests for which a Pending Request List: the set of outstanding requests for which a
DDT Map Resolver has received encapsulated Map-Requests from its DDT Map-Resolver has received Encapsulated Map-Requests from its
clients seeking EID-to-RLOC mapping for a XEID. Each entry in the clients seeking EID-to-RLOC mapping for an XEID. Each entry in
list contains additional state needed by the referral following the list contains additional state needed by the
process, including the XEID, requestor(s) of the XEID (typically, referral-following process, including the XEID, requester(s) of
one or more ITRs), saved information about the last referral the XEID (typically one or more ITRs), saved information about the
received and followed (matching XEID-prefix, action code, RLOC last referral received and followed (matching XEID-prefix, action
set, index of last RLOC queried in the RLOC set), and any LISP-SEC code, RLOC set, index of the last RLOC queried in the RLOC set),
information ([I-D.ietf-lisp-sec]) that was included in the DDT and any LISP-Security (LISP-SEC) information [LISP-SEC] that was
client Map-Request. An entry in the list may be interchangeably included in the DDT client Map-Request. An entry in the list may
termed a "pending request list entry" or simply a "pending be interchangeably termed a "pending request list entry" or simply
request". a "pending request".
For definitions of other terms, notably Map-Request, Map-Reply, For definitions of other terms -- notably Map-Request, Map-Reply,
Ingress Tunnel Router (ITR), Egress Tunnel Router (ETR), Map Server, ITR, ETR, Map-Server, and Map-Resolver -- please consult the LISP
and Map Resolver, please consult the LISP specification [RFC6830] and specification [RFC6830] and the LISP Mapping Service specification
the LISP Mapping Service specification [RFC6833]. [RFC6833].
4. Database organization 4. Database Organization
4.1. XEID prefixes 4.1. XEID-Prefixes
DDT database is indexed by Extended EID-prefixes (XEID-prefixes). A DDT database is indexed by Extended EID-prefixes (XEID-prefixes).
XEID-prefix is LISP EID-prefix together with data extending it to An XEID-prefix is a LISP EID-prefix, together with data extending it
uniquely identify address space of the prefix. XEID-prefix is to uniquely identify the address space of the prefix. An XEID-prefix
composed as binary encoding of five fields, in order of significance: is composed of four binary-encoded fields, ordered by significance:
DBID (16 bits), Instance Identifier (IID, 32 bits), Address Family DBID (16 bits), IID (32 bits), AFI (16 bits), and EID-prefix
Identifier (AFI, 16 bits), and EID-prefix (variable, according to AFI (variable, according to the AFI value). The fields are concatenated,
value). The fields are concatenated, with the most significant with the most significant fields as listed above.
fields as listed above.
DBID is LISP-DDT database ID, a 16-bit field provided to allow the The DBID is the LISP-DDT Database-ID, a 16-bit field provided to
definition of multiple databases. In this version of DDT DBID MUST allow the definition of multiple databases. Implementations that are
always be set to zero. Other values of DBID are reserved for future compliant with this document must always set this field to 0. Other
use. values of the DBID are reserved for future use.
Instance ID (IID) is 32-bit value describing context of EID prefix if The Instance ID (IID) is a 32-bit value describing the context of the
the latter is intended for use in an environment where addresses may EID-prefix, if the latter is intended for use in an environment where
not be unique, such as on a Virtual Private Network where [RFC1918] addresses may not be unique, such as in a Virtual Private Network
address space is used. See "Using Virtualization and Segmentation where the [RFC1918] address space is used. See Section 5.5 of
with LISP" in [RFC6830] for more discussion of Instance IDs. [RFC6830] for more discussion of IIDs. Encoding of the IID is
Encoding of the instance ID (IID) is specified by specified by [RFC8060].
[I-D.ietf-lisp-lcaf].
Address Family Identifier (AFI) is a 16-bit value defining syntax of The AFI is a 16-bit value defining the syntax of the EID-prefix. AFI
EID-prefix. AFI values are assigned by IANA ([AFI]. values are assigned by IANA [AFI].
4.2. DDT database tree structure 4.2. Structure of the DDT Database
LISP-DDT database of each DDT node is organised as a tree structure The LISP-DDT database for each DDT node is organized as a tree
that is indexed by XEID prefixes. Leaves of the database tree structure that is indexed by XEID-prefixes. Leaves of the database
describe delegation of authority between DDT nodes (see more on tree describe the delegation of authority between DDT nodes (see
delegation and information kept in the database entries in Section 4.3 for details regarding delegation and information kept in
Section 4.3). the database entries).
DDT Map-Requests sent by the DDT client to DDT nodes always contain DDT Map-Requests sent by the DDT client to DDT nodes always contain
specific values for DBID, IID and AFI; never a range or unspecified specific values for the DBID, IID, and AFI; unspecified values or
value for any of these fields. Thus XEID prefix used as key for ranges of values are never used for any of these fields. Thus, an
search in the database tree will have length of at least 64 bits. XEID-prefix used as a key for searches in the database tree will have
a length of at least 64 bits.
DDT node may, for example, be authoritative for a consecutive range 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 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/ for a specific EID-prefix of a single 3-tuple. Thus,
keys of the database tree leaves may have length less, equal or more XEID-prefixes/keys of the database tree leaves may have lengths less
than 64 bits. than, equal to, or more than 64 bits.
It is important to note that LISP-DDT does not store actual EID-to- It is important to note that LISP-DDT does not store actual
RLOC mappings; it is, rather, a distributed index that can be used to EID-to-RLOC mappings; it is, rather, a distributed index that can be
find the devices (ETRs which registered their EIDs with DDT Map used to find the devices (ETRs that registered their EIDs with DDT
Servers) that can be queried with LISP to obtain those mappings. Map-Servers) that can be queried with LISP to obtain those mappings.
Changes to EID-to-RLOC mappings are made on the ETRs which define Changes to EID-to-RLOC mappings are made on the ETRs that define
them, not to any DDT node configuration. DDT node configuration them, not to any DDT node configuration. DDT node configuration
changes are only required when branches of the database hierarchy are changes are only required when branches of the database hierarchy are
added, removed, or modified. added, removed, or modified.
4.3. Configuring prefix delegation 4.3. Configuring Prefix Delegation
Every DDT node is configured with one or more XEID-prefixes for which 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 it is authoritative, along with a list of delegations of
to other DDT nodes. A DDT node is required to maintain a list of XEID-prefixes to other DDT nodes. A DDT node is required to maintain
delegations for all sub-prefixes of its authoritative XEID-prefixes; a list of delegations for all sub-prefixes of its authoritative
it also may list "hints", which are prefixes that it knows about that XEID-prefixes; it also may list "hints", which are prefixes that it
belong to its parents, to the root, or to any other point in the knows about that belong to its parents, to the root, or to any other
XEID-prefix hierarchy. A delegation (or hint) consists of an XEID- point in the XEID-prefix hierarchy. A delegation (or hint) consists
prefix, a set of RLOCs for DDT nodes that have more detailed of an XEID-prefix, a set of RLOCs for DDT nodes that have more
knowledge of the XEID-prefix, and accompanying security information detailed knowledge of the XEID-prefix, and accompanying security
(for details of security infomation exchange and its use see information (for details regarding security information exchange and
Section 10). Those RLOCs are returned in Map-Referral messages when its use, see Section 10). Those RLOCs are returned in Map-Referral
the DDT node receives a DDT Map-Request with an XEID that matches a messages when the DDT node receives a DDT Map-Request with an XEID
delegation. A DDT Map Server will also have a set of sub-prefixes that matches a delegation. A DDT Map-Server will also have a set of
for which it accepts ETR mapping registrations and for which it will sub-prefixes for which it accepts ETR mapping registrations and for
forward (or answer, if it provides proxy Map-Reply service) Map- which it will forward (or answer, if it provides a proxy Map-Reply
Requests. service) Map-Requests.
XEID prefix (or prefixes) for which DDT node is authoritative and One or more XEID-prefixes for which a DDT node is authoritative, and
delegation of authority for sub-prefixes is provided as configuration the delegation of authority for sub-prefixes, are provided as part of
of the DDT node. Implementations will likely develop a language to the configuration of the DDT node. Implementations will likely
express this prefix authority and delegation. Since DDT develop a language to express this prefix authority and delegation.
configuration is static (i.e. not exchanged between DDT nodes as part Since DDT configuration is static (i.e., not exchanged between DDT
of the protocol itself) such language is implementation-dependant and nodes as part of the protocol itself), such language is
is outside the scope of this specification. implementation dependent and is outside the scope of this
specification.
4.3.1. The root DDT node 4.3.1. The Root DDT Node
The root DDT node is the logical "top" of the distributed database The root DDT node is the logical "top" of the distributed database
hierarchy. It is authoritative for all XEID prefixes, that is for hierarchy. It is authoritative for all XEID-prefixes -- that is, for
all valid 3-tuples (DBID, IID, AFI) and their EID prefixes. A DDT all valid 3-tuples (DBID, IID, AFI) and their EID-prefixes. A DDT
Map-Request that matches no configured XEID-prefix will be referred Map-Request that matches no configured XEID-prefix will be referred
to the root node (see Section 8 for formal description of conditions to the root node (see Section 8 for a formal description of
when DDT Request is forwarded to the root node). The root node in a conditions where a DDT Map-Request is forwarded to the root node).
particular instantiation of LISP-DDT therefore MUST be configured The root node in a particular instantiation of LISP-DDT therefore
with delegations for at least all defined IIDs and AFIs. MUST be configured, at a minimum, with delegations for all defined
IIDs and AFIs.
5. DDT Map-Request 5. DDT Map-Request
A DDT client (usualy a Map Resolver) uses LISP Encapsulated Control A DDT client (usually a Map-Resolver) uses LISP Encapsulated Control
Message (ECM) to send Map-Request to a DDT node. Format of the ECM Messages (ECMs) to send Map-Request messages to a DDT node. The
is defined by [RFC6830]. This specification adds to ECM flag "DDT- format of the ECM is defined by [RFC6830]. This specification adds
originated". 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
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 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 | / | IPv4 or IPv6 Header |
OH | (uses RLOC addresses) | OH | (uses RLOC addresses) |
\ | | \ | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
/ | Source Port = xxxx | Dest Port = 4342 | / | Source Port = xxxx | Dest Port = 4342 |
UDP +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ UDP +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
skipping to change at page 9, line 47 skipping to change at page 11, line 5
IH | (uses RLOC or EID addresses) | IH | (uses RLOC or EID addresses) |
\ | | \ | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
/ | Source Port = xxxx | Dest Port = yyyy | / | Source Port = xxxx | Dest Port = yyyy |
UDP +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ UDP +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
\ | UDP Length | UDP Checksum | \ | UDP Length | UDP Checksum |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
LCM | LISP Control Message | LCM | LISP Control Message |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
D: The "DDT-originated" flag. It is set by a DDT client to indicate D: The "DDT-originated" flag. This flag is set by a DDT client to
that the receiver SHOULD return Map-Referral messages as indicate that the receiver SHOULD return Map-Referral messages as
appropriate. Use of the flag is further described in appropriate. The use of this flag is further described in
Section 7.3.1. This bit is allocated from LISP message header Section 7.3.1. This bit is allocated from LISP message header
bits marked as Reserved in [RFC6830]. bits marked as "Reserved" in [RFC6830].
6. The Map-Referral message 6. The Map-Referral Message
This specification defines a new LISP message, the Map-Referral. It This specification defines a new LISP message called the Map-Referral
is sent by a DDT node to a DDT client in response to a DDT Map- message. A Map-Referral message is sent by a DDT node to a
Request message. See Section 6.4 for a detailed layout of the Map- DDT client in response to a DDT Map-Request message. See Section 6.4
Referral message fields. for a detailed layout of the Map-Referral message fields.
The message consists of an action code along with delegation The message consists of an action code along with delegation
information about the XEID-prefix that matches the requested XEID. information about the XEID-prefix that matches the requested XEID.
6.1. Action codes 6.1. Action Codes
The action codes are as follows: The action codes are as follows:
NODE-REFERRAL (0): indicates that the replying DDT node has NODE-REFERRAL (0): indicates that the replying DDT node has
delegated an XEID-prefix that matches the requested XEID to one or delegated an XEID-prefix that matches the requested XEID to one or
more other DDT nodes. The Map-Referral message contains a "map- more other DDT nodes. The Map-Referral message contains a
record" with additional information, most significantly the set of "map-record" with additional information -- most significantly,
RLOCs to which the prefix has been delegated, that is used by a the set of RLOCs to which the prefix has been delegated -- that is
DDT client to "follow" the referral. used by a DDT client to "follow" the referral.
MS-REFERRAL (1): indicates that the replying DDT node has delegated MS-REFERRAL (1): indicates that the replying DDT node has delegated
an XEID-prefix that matches the requested XEID to one or more DDT an XEID-prefix that matches the requested XEID to one or more DDT
Map Servers. It contains the same additional information as a Map-Servers. It contains the same additional information as a
NODE-REFERRAL, but is handled slightly differently by the NODE-REFERRAL but is handled slightly differently by the receiving
receiving DDT client (see Section 7.3.2). DDT client (see Section 7.3.2).
MS-ACK (2): indicates that the replying DDT Map Server received a MS-ACK (2): indicates that the replying DDT Map-Server received a
DDT Map-Request that matches an authoritative XEID-prefix for DDT Map-Request that matches an authoritative XEID-prefix for
which it has one or more registered ETRs. This means that the which it has one or more registered ETRs. This means that the
request has been forwarded to one of those ETRs to provide an request has been forwarded to one of those ETRs to provide an
answer to the querying ITR. answer to the querying ITR.
MS-NOT-REGISTERED (3): indicates that the replying DDT Map Server MS-NOT-REGISTERED (3): indicates that the replying DDT Map-Server
received a Map-Request for one of its configured XEID-prefixes received a Map-Request for one of its configured XEID-prefixes
which has no ETRs registered. that has no ETRs registered.
DELEGATION-HOLE (4): indicates that the requested XEID matches a DELEGATION-HOLE (4): indicates that the requested XEID matches a
non-delegated sub-prefix of the XEID space. This is a non-LISP 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. "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 See Section 7.1.2 for details. Also sent by a DDT Map-Server with
authoritative configuration covering the requested EID, but for authoritative configuration covering the requested EID but for
which no specific site ETR is configured. which no specific site ETR is configured.
NOT-AUTHORITATIVE (5): indicates that the replying DDT node received NOT-AUTHORITATIVE (5): indicates that the replying DDT node received
a Map-Request for an XEID for which it is not authoritative and a Map-Request for an XEID for which it is not authoritative and
has no configured matching hint referrals. This can occur if a has no configured matching hint referrals. This can occur if a
cached referral has become invalid due to a change in the database cached referral has become invalid due to a change in the database
hierarchy. However, if such a DDT node has a "hint" delegation hierarchy. However, if such a DDT node has a "hint" delegation
covering the requested EID, it MAY choose to return NODE-REFERRAL covering the requested EID, it MAY choose to return NODE-REFERRAL
or MS-REFERRAL as appropriate. When returning action code NOT- or MS-REFERRAL as appropriate. When returning action code
AUTHORITATIVE DDT node MUST provide EID-prefix received in the NOT-AUTHORITATIVE, the DDT node MUST provide the EID-prefix
request and the TTL MUST be set to 0. received in the request and the TTL MUST be set to 0.
6.2. Referral set 6.2. Referral Set
For "positive" action codes (NODE-REFERRAL, MS-REFERRAL, MS-ACK), a 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 node MUST include in the Map-Referral message a list of RLOCs for
DDT nodes that are authoritative for the XEID-prefix being returned; DDT nodes that are authoritative for the XEID-prefix being returned;
a DDT client uses this information to contact one of those DDT nodes a DDT client uses this information to contact one of those DDT nodes
as it "follows" a referral. as it "follows" a referral.
6.3. Incomplete flag 6.3. "Incomplete" Flag
A DDT node sets the "Incomplete" flag in a Map-Referral message if 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 the Referral Set is incomplete; this is intended to prevent a DDT
client from caching a referral with incomplete information. A DDT client from caching a referral with incomplete information. A DDT
node MUST set the "incomplete" flag in the following cases: 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 o If it is setting action code MS-ACK or MS-NOT-REGISTERED but the
matching XEID-prefix is not flagged in configuration as matching XEID-prefix is not flagged as "complete" in the
"complete". XEID-prefix configuration on DDT Mapping Server configuration. The XEID-prefix configuration on the DDT
SHOULD be marked as "complete" when configuration of the XEID- Map-Server SHOULD be marked as "complete" when the configuration
prefix lists all "peer" DDT nodes that are also authoritative for of the XEID-prefix lists all "peer" DDT nodes that are also
the same XEID-prefix or when it is known that local DDT node is authoritative for the same XEID-prefix or when it is known that a
the only one authoritative for the XEID-prefix. local DDT node is the only authoritative node for the XEID-prefix.
o If it is setting action code NOT-AUTHORITATIVE. o If it is setting action code NOT-AUTHORITATIVE.
6.4. Map-Referral Message Format 6.4. Map-Referral Message Format
0 1 2 3 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 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 | |Type=6 | Reserved | Record Count |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Nonce . . . | | Nonce . . . |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| . . . Nonce | | . . . Nonce |
+-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | Record TTL | | | Record TTL |
| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
R | Referral Count| EID mask-len | ACT |A|I| Reserved | R | Referral Count| EID mask-len | ACT |A|I| Reserved |
e +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ e +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
c |SigCnt | Map Version Number | EID-AFI | c |SigCnt | Map Version Number | EID-AFI |
o +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ o +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
r | EID-prefix ... | r | EID-prefix ... |
d +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ d +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| /| Priority | Weight | M Priority | M Weight | | /| Priority | Weight | M Priority | M Weight |
| R +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | R +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| e | Unused Flags |L|p|R| Loc-AFI | | e | Unused Flags |L|p|R| Loc-AFI |
| f +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | f +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| \| Locator ... | | \| Locator ... |
| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ~ Sig section ~ | ~ Sig section ~
+-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Type: Type value 6 was reserved for future use in RFC6830, this Type: Type value 6 was reserved for future use in [RFC6830]. This
document allocates this value to identify Map-Referral messages. document allocates this value to identify Map-Referral messages.
ACT: The "action" field of the mapping record in a Map-Referral ACT: The ACT (Action) field of the mapping Record in a Map-Referral
message encodes one of the 6 action types: NODE-REFERRAL, MS- message encodes one of the following six action types:
REFERRAL, MS-ACK, MS-NOT-REGISTERED, DELEGATION-HOLE, NOT- NODE-REFERRAL, MS-REFERRAL, MS-ACK, MS-NOT-REGISTERED,
AUTHORITATIVE. See Section 6.1 for description of their meaning. DELEGATION-HOLE, or NOT-AUTHORITATIVE. See Section 6.1 for
descriptions of these action types.
Incomplete: The "I" bit indicates that a DDT node's referral-set of Incomplete: The "I" bit indicates that a DDT node's Referral Set of
locators is incomplete and the receiver of this message SHOULD NOT locators is incomplete and the receiver of this message SHOULD NOT
cache the referral. A DDT sets the "incomplete" flag, the TTL, and cache the referral. A DDT sets the "Incomplete" flag, the TTL,
the Action Type field as follows: and the Action field as follows:
------------------------------------------------------------------- -------------------------------------------------------------------
Type (Action field) Incomplete Referral-set TTL values Type (Action field) Incomplete Referral Set TTL values
------------------------------------------------------------------- -------------------------------------------------------------------
0 NODE-REFERRAL NO YES 1440 0 NODE-REFERRAL No Yes 1440
1 MS-REFERRAL NO YES 1440 1 MS-REFERRAL No Yes 1440
2 MS-ACK * * 1440 2 MS-ACK * * 1440
3 MS-NOT-REGISTERED * * 1 3 MS-NOT-REGISTERED * * 1
4 DELEGATION-HOLE NO NO 15 4 DELEGATION-HOLE No No 15
5 NOT-AUTHORITATIVE YES NO 0 5 NOT-AUTHORITATIVE Yes No 0
------------------------------------------------------------------- -------------------------------------------------------------------
*: The "Incomplete" flag setting on Map Server originated referral of *: The "Incomplete" flag setting for the Map-Server-originated
MS-ACK and MS-NOT-REGISTERED types depend on whether the Map referral of MS-ACK and MS-NOT-REGISTERED types depends on whether
Server has the full peer Map Server configuration for the same the Map-Server has the full peer Map-Server configuration for the
prefix and has encoded the information in the mapping record. same prefix and has encoded the information in the mapping Record.
Incomplete bit is not set when the Map Server has encoded the The "Incomplete" bit is not set when the Map-Server has encoded
information, which means the referral-set includes all the RLOCs the information; this means that the Referral Set includes all the
of all Map Servers that serve the prefix. It MUST be set when RLOCs of all Map-Servers that serve the prefix. It MUST be set
configuration of the Map Server does not flag matching prefix as when the configuration of the Map-Server does not flag the
configured with the complete information about "peer" Map Servers matching prefix as configured with the complete information about
or when the Map Server does not return all configured locators. "peer" Map-Servers or when the Map-Server does not return all
configured locators.
Referral Count: number of RLOCs in the current Referral set, it is Referral Count: Number of RLOCs in the current Referral Set. This
equal to the number of Ref sections in the message. number is equal to the number of "Ref" sections in the message (as
shown in the diagram above).
SigCnt: Indicates the number of signatures (sig section) present in SigCnt: Indicates the number of signatures (Signature section)
the Record. If SigCnt is larger than 0, the signature information present in the Record. If SigCnt is larger than 0, the signature
captured in a sig section as described in Section 6.4.1 will be information captured in a Signature section as described in
appended to the end of the record. The number of sig sections at the Section 6.4.1 will be appended to the end of the Record. The
end of the Record MUST match the SigCnt. Note that bits occupied by number of Signature sections at the end of the Record MUST match
SigCnt were Reserved in Records embedded into messages defined by the SigCnt. Note that bits occupied by SigCnt were marked as
[RFC6830] and were required to be set to zero. "Reserved" in Records embedded into messages defined by [RFC6830]
and were required to be set to zero.
Loc-AFI: AFI of the Locator field. If AFI value is different from Loc-AFI: AFI of the Locator field. If the AFI value is different
LCAF AFI, security keys are not included in the record. If AFI is from the LISP Canonical Address Format (LCAF) AFI, security keys
equal to the LCAF AFI, the contents of the LCAF depend on the Type are not included in the Record. If the AFI value is equal to the
field of the LCAF. LCAF Type 11 is used to store security material LCAF AFI, the contents of the LCAF depend on the Type field of the
along with the AFI of the locator. DDT nodes and DDT Map Servers can LCAF. LCAF Type 11 is used to store security material along with
use this LCAF Type to include public keys associated with their Child the AFI of the locator. DDT nodes and DDT Map-Servers can use
DDT nodes for a XEID-prefix referral record. LCAF types and formats this LCAF Type to include public keys associated with their child
are defined in [I-D.ietf-lisp-lcaf]. DDT nodes for an XEID-prefix Map-Referral Record. LCAF Types and
formats are defined in [RFC8060].
Locator: RLOC of a DDT node the DDT client is being referred to. Locator: RLOC of a DDT node to which the DDT client is being
Lenght of this variable-length field is determined by the Loc-AFI. 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 All other fields and their descriptions are equivalent to those in
the Map-Reply message, as defined in LISP [RFC6830]. Note, though, 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 that the set of RLOCs correspond to the DDT node to be queried as a
result of the referral not the RLOCs for an actual EID-to-RLOC result of the referral and not to the RLOCs for an actual EID-to-RLOC
mapping. mapping.
6.4.1. SIG section 6.4.1. Signature Section
SigCnt counts the number of signature sections that appear at the end SigCnt counts the number of signature sections that appear at the end
of the Record. Format of the signature section is described below. of the Record. The format of the signature section is described
below.
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
/| Original Record TTL | /| Original Record TTL |
/ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ / +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
/ | Signature Expiration | / | Signature Expiration |
| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
s | Signature Inception | s | Signature Inception |
i +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ i +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
g | Key Tag | Sig Length | g | Key Tag | Sig Length |
| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
\ | Sig-Algorithm | Reserved | Reserved | \ | Sig-Algorithm | Reserved | Reserved |
\ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ \ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
\ ~ Signature ~ \ ~ Signature ~
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Original Record TTL: The original Record TTL for this record that is Original Record TTL: The original Record TTL for this Record that
covered by the signature. Record TTL is in minutes. is covered by the signature. The Record TTL value is specified
in minutes.
Signature Expiration and Inception: Specify the validity period for Signature Expiration and Signature Inception: Specify the validity
the signature. The signature MUST NOT be used for authentication period for the signature. The signature MUST NOT be used for
prior to the inception date and MUST NOT be used for authentication authentication prior to the inception date and MUST NOT be used
after the expiration date. Each field specifies a date and time in for authentication after the expiration date. Each field
the form of a 32-bit unsigned number of seconds elapsed since 1 specifies a date and time in the form of a 32-bit unsigned number
January 1970 00:00:00 UTC, ignoring leap seconds, in network byte of seconds elapsed since 1 January 1970 00:00:00 UTC, ignoring
order. leap seconds, in network byte order.
Key Tag: An identifier to specify which key is used for this 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. signature if more than one valid key exists for the signing
DDT node.
Sig Length: The length of the Signature field in bytes. Sig Length: The length of the Signature field in bytes.
Sig-Algorithm: The identifier of the cryptographic algorithm used for Sig-Algorithm: The identifier of the cryptographic algorithm used
the signature. Sig-Algorithm values defined in this specification for the signature. Sig-Algorithm values defined in this
are listed in Table 1. Implementation conforming to this specification are listed in Table 1. Implementations conforming
specification MUST implement at least RSA-SHA256 for DDT signing. to this specification MUST implement at least RSA-SHA256 for DDT
Sig-Algorithm type 1 RSA-SHA1 is deprecated and SHOULD NOT be used. signing. Sig-Algorithm type 1 (RSA-SHA1) is deprecated and
SHOULD NOT be used.
+---------------+------------+-----------+------------+ +---------------+------------+-----------+------------+
| Sig-Algorithm | Name | Reference | Notes | | Sig-Algorithm | Name | Reference | Notes |
+---------------+------------+-----------+------------+ +---------------+------------+-----------+------------+
| 1 | RSA-SHA1 | [RFC3447] | DEPRECATED | | 1 | RSA-SHA1 | [RFC8017] | DEPRECATED |
| | | | | | | | | |
| 2 | RSA-SHA256 | [RFC3447] | MANDATORY | | 2 | RSA-SHA256 | [RFC8017] | MANDATORY |
+---------------+------------+-----------+------------+ +---------------+------------+-----------+------------+
Table 1: Sig-Algorithm Values Table 1: Sig-Algorithm Values
Reserved: This field MUST be set to 0 on transmit and MUST be ignored Reserved: MUST be set to 0 on transmit and MUST be ignored on
on receipt. receipt.
Signature: Contains the cryptographic signature that covers the Signature: Contains the cryptographic signature that covers the
entire referral record that this signature belongs to. The Record entire Map-Referral Record to which this signature belongs. For
TTL is set to Original Record TTL and the sig fields are Signature the purpose of computing the signature, the Record TTL
field is set to zero for the purpose of computing the Signature. (Section 6.4) value is set to the value of Original Record TTL and
the Signature field is filled with zeros.
7. DDT network elements and their operation 7. DDT Network Elements and Their Operation
As described above, DDT introduces a new network element, the "DDT As described above, LISP-DDT introduces a new network element -- the
node", extends the functionality of Map Servers and Map Resolvers to DDT node -- and extends the functionality of Map-Servers and
send and receive Map-Referral messages. The operation of each of Map-Resolvers to send and receive Map-Referral messages. The
these devices is described as follows. operation of each of these devices is described below.
7.1. DDT node 7.1. DDT Node
When a DDT node receives a DDT Map-Request, it compares the requested 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 XEID against its list of XEID-prefix delegations and its list of
authoritative XEID-prefixes and acts as follows: authoritative XEID-prefixes, and proceeds as follows:
7.1.1. Match of a delegated prefix (or sub-prefix) 7.1.1. Matching of a Delegated Prefix (or Sub-prefix)
If the requested XEID matches one of the DDT node's delegated If the requested XEID matches one of the DDT node's delegated
prefixes, then a Map-Referral message is returned with the matching prefixes, then a Map-Referral message is returned with the matching
more-specific XEID-prefix and the set of RLOCs for the referral more-specific XEID-prefix and the set of RLOCs for the referral
target DDT nodes including associated security information (see target DDT nodes, including associated security information (see
Section 10 for details on security). If at least one DDT node of the 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 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 message SHOULD be sent with action code MS-REFERRAL to indicate to
the receiver that LISP-SEC information (if saved in the pending the receiver that LISP-SEC information (if saved in the pending
request) SHOULD be included in the next DDT Map-Request; otherwise, request) SHOULD be included in the next DDT Map-Request; otherwise,
the action code NODE-REFERRAL SHOULD be used. the action code NODE-REFERRAL SHOULD be used.
Note that a matched delegation does not have to be for a sub-prefix Note that a matched delegation does not have to be for a sub-prefix
of an authoritative prefix; in addition to being configured to of an authoritative prefix; in addition to being configured to
delegate sub-prefixes of an authoritative prefix, a DDT node may also delegate sub-prefixes of an authoritative prefix, a DDT node may also
be configured with other XEID-prefixes for which it can provide be configured with other XEID-prefixes for which it can provide
referrals to DDT nodes anywhere in the database hierarchy. This referrals to DDT nodes anywhere in the database hierarchy. This
capability to define "shortcut hints" is never required to be capability to define "shortcut hints" is never required to be
configured, but may be a useful heuristic for reducing the number of configured, but it may be a useful heuristic for reducing the number
iterations needed to find an EID, particular for private network of iterations needed to find an EID, particularly for private network
deployments. deployments.
Referral hints, if used properly, may reduce number of referrals a Referral hints, if used properly, may reduce the number of referrals
DDT client needs to follow to locate DDT Map Server authoritative for a DDT client needs to follow to locate a DDT Map-Server authoritative
XEID prefix being resolved. On the other hand, incorrect use of for the XEID-prefix being resolved. On the other hand, the incorrect
hints may create circular dependencies between DDT nodes (or use of hints may create circular dependencies (or "referral loops")
"referral loops"). DDT client MUST be prepared to handle such between DDT nodes. A DDT client MUST be prepared to handle such
circular referrals. See Section 7.3.4 for discussion of referral circular referrals. See Section 7.3.4 for a discussion of referral
loops and measures DDT client must implement in order to detect loops and measures that the DDT client must implement in order to
circular referrals and prevent infinite looping. detect circular referrals and prevent infinite looping.
Another danger with use of hints is when DDT deployment spans Another danger related to the use of hints is when a DDT deployment
multiple administrative domains (i.e. different authorities manage spans multiple administrative domains (i.e., different authorities
DDT nodes in the same DDT database). In this case operator managing manage DDT nodes in the same DDT database). In this case, an
a DDT node may not be aware of the fact that the node is being operator managing a DDT node may not be aware of the fact that the
referred to by hints. Locator addresses in hints may become stale node is being referred to by hints. Locator addresses in hints may
when referred DDT nodes are taken out of service or change their become stale when referred DDT nodes are taken out of service or
locator addresses. change their locator addresses.
7.1.2. Missing delegation from an authoritative prefix 7.1.2. Missing Delegation from an Authoritative Prefix
If the requested XEID did not match a configured delegation but does If the requested XEID did not match a configured delegation but does
match an authoritative XEID-prefix, then the DDT node MUST return a match an authoritative XEID-prefix, then the DDT node MUST return a
negative Map-Referral that uses the least-specific XEID-prefix that Negative Map-Referral that uses the least-specific XEID-prefix that
does not match any XEID-prefix delegated by the DDT node. The action 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 code is set to DELEGATION-HOLE; this indicates that the XEID is not a
LISP destination. LISP destination.
If the requested XEID did not match either a configured delegation, If the requested XEID did not match either a configured delegation,
an authoritative XEID-prefix or a "hint", then negative Map-Referral an authoritative XEID-prefix, or a hint, then a Negative Map-Referral
with action code NOT-AUTHORITATIVE MUST be returned. with action code NOT-AUTHORITATIVE MUST be returned.
7.2. DDT Map Server 7.2. DDT Map-Server
When a DDT Map Server receives a DDT Map-Request, its operation is 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: similar to that of a DDT node, with additional processing as follows:
o If the requested XEID matches a registered XEID-prefix, then the o If the requested XEID matches a registered XEID-prefix, then the
Map-Request is forwarded to one of the destination ETR RLOCs (or Map-Request is forwarded to one of the destination ETR RLOCs (or
the Map Server sends a Map-Reply, if it is providing proxy Map- the Map-Server sends a Map-Reply, if it is providing a proxy
Reply service) and a Map-Referral with the MS-ACK action MUST be Map-Reply service), and a Map-Referral with action code MS-ACK
returned to the sender of the DDT Map-Request. MUST be returned to the sender of the DDT Map-Request.
o If the requested XEID matches a configured XEID-prefix for which o If the requested XEID matches a configured XEID-prefix for which
no ETR registration has been received then a negative Map-Referral no ETR registration has been received, then a Negative
with action code MS-NOT-REGISTERED MUST be returned to the sender Map-Referral with action code MS-NOT-REGISTERED MUST be returned
of the DDT Map-Request. to the sender of the DDT Map-Request.
7.3. DDT client 7.3. DDT Client
A DDT client queries one or more DDT nodes and uses an iterative A DDT client queries one or more DDT nodes and uses an iterative
process of following returned referrals until it receives one with process of following returned referrals until it receives one with
action code MS-ACK (or an error indication). MS-ACK indicates that 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 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 an ETR that, in turn, will provide a Map-Reply to the locator address
in the Map-Request. in the Map-Request.
DDT client functionality will typically be implemented by DDT Map DDT client functionality will typically be implemented by DDT
Resolvers. Just as any other Map Resolver, a DDT Map Resolver Map-Resolvers. Just as would any other Map-Resolver, a DDT
accepts Map-Requests from its clients (typically, ITRs) and ensures Map-Resolver accepts Map-Requests from its clients (typically ITRs)
that those Map-Requests are forwarded to the correct ETR, which and ensures that those Map-Requests are forwarded to the correct ETR,
generates Map-Replies. Unlike a Map Resolver that uses the ALT which generates Map-Replies. However, unlike a Map-Resolver that
mapping system (see [RFC6836]), however, a DDT Map Resolver uses the LISP Alternative Logical Topology (LISP+ALT) mapping system
implements a DDT client functionality to find the correct ETR to [RFC6836], a DDT Map-Resolver implements DDT client functionality to
answer a Map-Request; this requires a DDT Map Resolver to maintain find the correct ETR to answer a Map-Request; this requires a DDT
additional state: a Map-Referral cache and pending request list of Map-Resolver to maintain additional state: a Map-Referral cache and a
XEIDs that are going through the iterative referral process. pending request list of XEIDs that are going through the iterative
referral process.
DDT client functionality may be implemented on ITRs. In this case DDT client functionality may be implemented on ITRs. In this case,
the DDT client will not receive Map-Request from another network the DDT client will not receive a Map-Request from another network
element; instead, equivalent information will be provided to the DDT element; instead, equivalent information will be provided to the DDT
client by the means of programming interface. client via a programming interface.
7.3.1. Queuing and sending DDT Map-Requests 7.3.1. Queuing and Sending DDT Map-Requests
When a DDT client receives a request to resolve XEID (in case of DDT When a DDT client receives a request to resolve an XEID (in the case
Map Resolver this will be in the form of received encapsulated Map- of a DDT Map-Resolver, this will be in the form of a received
Request), it first performs a longest-match search for the XEID in Encapsulated Map-Request), it first performs a longest-match search
its referral cache. If no match is found or if a negative cache for the XEID in its referral cache. If no match is found or if a
entry is found, then the destination is not in the database; a negative cache entry is found, then the destination is not in the
negative Map-Reply MUST be returned and no further processing is database; a Negative Map-Reply MUST be returned, and no further
performed by the DDT client. processing is performed by the DDT client.
If a match is found, the DDT client creates a pending request list If a match is found, the DDT client creates a pending request list
entry for the XEID and saves the original request (in case of DDT entry for the XEID and saves the original request (in the case of a
Map-Resolved, original Map-Request minus the encapsulation header) DDT Map-Resolver, this will be the original Map-Request minus the
along with other information needed to track progress through the encapsulation header) along with other information needed to track
iterative referral process; the "referral XEID-prefix" is also progress through the iterative referral process; the "referral
initialized to indicate that no referral has yet been received. The XEID-prefix" is also initialized to indicate that no referral has yet
DDT client then creates a DDT Map-Request (which is an encapsulated been received. The DDT client then creates a DDT Map-Request (which
Map-Request with the "DDT-originated" flag set in the message header) is an Encapsulated Map-Request with the "DDT-originated" flag set in
for the XEID but without any authentication data that may have been the message header) for the XEID but without any authentication data
included in the original request. It sends the DDT Map-Request to that may have been included in the original request. It sends the
one of the RLOCs in the chosen referral cache entry. The referral DDT Map-Request to one of the RLOCs in the chosen referral cache
cache is initially populated with one or more statically-configured entry. The referral cache is initially populated with one or more
entries; additional entries are added when referrals are followed, as statically configured entries; additional entries are added when
described below. A DDT client is not absolutely required to cache referrals are followed, as described below. A DDT client is not
referrals, but it doing so decreases latency and reduces lookup absolutely required to cache referrals, but doing so will decrease
delays. latency and reduce lookup delays.
Note that in normal use on the public Internet, the statically- Note that in normal use on the public Internet, the statically
configured initial referral cache for a DDT client should include a configured initial referral cache for a DDT client should include a
"default" entry with RLOCs for either the DDT root node or one or "default" entry with RLOCs for either the root DDT node or one or
more DDT nodes that contain hints for the DDT root node. If a DDT more DDT nodes that contain hints for the root DDT node. If a DDT
client does not have such configuration, it will return a Negative 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 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 mapping database known to it. While this may be desirable on private
network deployments or during early transition to LISP when few sites network deployments or during early transition to LISP when few sites
are using it, this behavior is not appropriate when LISP is in are using it, this behavior is not appropriate when LISP is in
general use on the Internet. If DDT message exchange is general use on the Internet. If DDT message exchanges are
authenticated as described in Section 10 then DDT client MUST also be authenticated as described in Section 10, then the DDT client MUST
configured with public keys of DDT nodes pointed to by the "default" also be configured with public keys of DDT nodes pointed to by the
cache entry. In this case the "default" entry will typically be for "default" cache entry. In this case, the "default" entry will
the DDT root node. typically be for the root DDT node.
7.3.2. Receiving and following referrals 7.3.2. Receiving and Following Referrals
After sending a DDT Map-Request, a DDT client expects to receive a After sending a DDT Map-Request, a DDT client expects to receive a
Map-Referral response. If none occurs within the timeout period, the Map-Referral response. If none occurs within the timeout period, the
DDT client retransmits the request, sending to the next RLOC in the DDT client retransmits the request, sending it to the next RLOC in
referral cache entry if one is available. If all RLOCs have been the referral cache entry if one is available. If all RLOCs have been
tried and the maximum number of retransmissions has occurred for tried and the maximum number of retransmissions has occurred for
each, then the pending request list entry is dequeued and discarded. each, then the pending request list entry is dequeued and discarded.
In this case DDT client returns no response to sender of the original In this case, the DDT client returns no response to the sender of the
request. original request.
A DDT client processes a received Map-Referral message according to A DDT client processes a received Map-Referral message according to
each action code: each action code:
NODE-REFERRAL: The DDT client checks for a possible referral loop as NODE-REFERRAL: The DDT client checks for a possible referral loop as
as described in Section 7.3.4. If no loop is found, the DDT described in Section 7.3.4. If no loop is found, the DDT client
client saves the prefix returned in the Map-Referral message in saves the prefix returned in the Map-Referral message in the
the referral cache, updates the saved prefix and saved RLOCs in referral cache, updates the saved prefix and saved RLOCs in the
the pending request list entry, and follows the referral by pending request list entry, and follows the referral by sending a
sending a new DDT Map-Request to one of the DDT node RLOCs listed new DDT Map-Request to one of the DDT node RLOCs listed in the
in the Referral Set; security information saved with the original Referral Set; security information saved with the original
Map-Request SHOULD NOT be included. Map-Request SHOULD NOT be included.
MS-REFERRAL: The DDT client processes an MS-REFERRAL in the same MS-REFERRAL: The DDT client processes an MS-REFERRAL in the same
manner as a NODE-REFERRAL except that security information saved manner as a NODE-REFERRAL, except that security information saved
with the original Map-Request MUST be included in the new Map- with the original Map-Request MUST be included in the new
Request sent to a Map Server (see Section 10 for details on Map-Request sent to a Map-Server (see Section 10 for details on
security). security).
MS-ACK: This is returned by a DDT Map Server to indicate that it has MS-ACK: An MS-ACK is returned by a DDT Map-Server to indicate that
one or more registered ETRs that can answer a Map-Request for the it has one or more registered ETRs that can answer a Map-Request
XEID and the request has been forwarded to one of them (or if the for the XEID and the request has been forwarded to one of them
Map Server is doing proxy service for the prefix then reply has (or, if the Map-Server is providing a proxy service for the
been sent to the querying ITR). If the pending request did not prefix, then a reply has been sent to the querying ITR). If the
include saved LISP-SEC information or if that information was pending request did not include saved LISP-SEC information or if
already included in the previous DDT Map-Request (sent by the DDT that information was already included in the previous DDT
client in response to either an MS-REFERRAL or a previous MS-ACK Map-Request (sent by the DDT client in response to either an
referral), then the pending request for the XEID is complete; MS-REFERRAL or a previous MS-ACK referral), then the pending
processing of the request stops and all request state can be request for the XEID is complete; processing of the request stops,
discarded. Otherwise, LISP-SEC information is required and has and all request state can be discarded. Otherwise, LISP-SEC
not yet been sent to the authoritative DDT Map-Server; the DDT information is required and has not yet been sent to the
client MUST re-send the DDT Map-Request with LISP-SEC information authoritative DDT Map-Server; the DDT client MUST resend the DDT
included and the pending request queue entry remains until another Map-Request with LISP-SEC information included, and the pending
Map-Referral with MS-ACK action code is received. If the request queue entry remains until another Map-Referral with action
"incomplete" flag is not set, the prefix is saved in the referral code MS-ACK is received. If the "Incomplete" flag is not set, the
cache. prefix is saved in the referral cache.
MS-NOT-REGISTERED: The DDT Map Server queried could not process the MS-NOT-REGISTERED: The DDT Map-Server queried could not process the
request because it did not have any ETRs registered for a request because it did not have any ETRs registered for a
matching, authoritative XEID-prefix. If the DDT client has not matching, authoritative XEID-prefix. If the DDT client has not
yet tried all of the RLOCs saved with the pending request, then it 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 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 have been tried, then the destination XEID is not registered and
is unreachable. The DDT client MUST return a negative Map-Reply is unreachable. The DDT client MUST return a Negative Map-Reply
to the requester (in case of DDT Map Resolver to the sender of to the requester (or, in the case of a DDT Map-Resolver, to the
original Map-Request); this Map-Reply contains the least-specific sender of the original Map-Request). This Map-Reply contains the
XEID-prefix in the range for which this DDT Map Server is least-specific XEID-prefix in the range for which this DDT
autoritative and no registrations exist and whose TTL value SHOULD Map-Server is authoritative and in which no registrations exist.
be set to one minute. A negative referral cache entry is created The TTL value of the Negative Map-Reply SHOULD be set to 1 minute.
for the prefix (whose TTL also SHOULD be set to one minute) and A negative referral cache entry is created for the prefix (whose
processing of the request stops. TTL also SHOULD be set to 1 minute), and processing of the request
stops.
DELEGATION-HOLE: The DDT Map Server queried did not have an XEID- DELEGATION-HOLE: The DDT Map-Server queried did not have an
prefix defined that matched the requested XEID so it does not XEID-prefix defined that matched the requested XEID, so the XEID
exist in the mapping database. The DDT client MUST return a does not exist in the mapping database. The DDT client MUST
negative Map-Reply to the requester (in case of DDT Map Resolver return a Negative Map-Reply to the requester (or, in the case of a
to the sender of original Map-Request); this Map-Reply SHOULD DDT Map-Resolver, to the sender of the original Map-Request); this
indicate the least-specific XEID-prefix matching the requested Map-Reply SHOULD indicate the least-specific XEID-prefix matching
XEID for which no delegations exist and SHOULD have a TTL value of the requested XEID for which no delegations exist and SHOULD have
15 minutes. A negative referral cache entry is created for the a TTL value of 15 minutes. A negative referral cache entry is
prefix (which also SHOULD have TTL of 15 minutes) and processing created for the prefix (which also SHOULD have a TTL of
of the pending request stops. 15 minutes), and processing of the pending request stops.
NOT-AUTHORITATIVE: The DDT Map Server queried is not authoritative NOT-AUTHORITATIVE: The DDT Map-Server queried is not authoritative
for the requested XEID. This can occur if a cached referral has for the requested XEID. This can occur if a cached referral has
become invalid due to a change in the database hierarchy. If the become invalid due to a change in the database hierarchy. If the
DDT client receiving this message can determine that it is using DDT client receiving this message can determine that it is using
old cached information, it MAY choose to delete that cached old cached information, it MAY choose to delete that cached
information and re-try the original Map-Request, starting from its information and retry the original Map-Request, starting from its
"root" cache entry. If this action code is received in response "root" cache entry. If this action code is received in response
to a query that did not use a cached referral information, then it to a query that did not use cached referral information, then it
indicates a database synchronization problem or configuration indicates a database synchronization problem or configuration
error. The pending request is silently discarded, i.e. all state error. The pending request is silently discarded; i.e., all state
for the request that caused this answer is removed and no answer for the request that caused this answer is removed, and no answer
is returned to the original requestor. is returned to the original requester.
7.3.3. Handling referral errors 7.3.3. Handling Referral Errors
Other states are possible, such as a misconfigured DDT node (acting 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 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 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; 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 one possibility is to remove the pending request list entry and send
a negative Map-Reply to the requester (in case of DDT Map Resolver to a Negative Map-Reply to the requester (or, in the case of a DDT
the sender of original Map-Request). Alternatively, if a DDT client Map-Resolver, to the sender of the original Map-Request).
detects unexpected behavior by a DDT node, it could mark that node as Alternatively, if a DDT client detects unexpected behavior by a DDT
unusable in its referral cache and update the pending request to try node, it could mark that node as unusable in its referral cache and
a different DDT node if more than one is listed in the referral update the pending request to try a different DDT node if more than
cache. In any case, any prefix contained in a Map-Referral message one is listed in the referral cache. In any case, any prefix
that causes a referral error (including a referral loop) is not saved contained in a Map-Referral message that causes a referral error
in the DDT client referral cache. (including a referral loop) is not saved in the DDT client referral
cache.
7.3.4. Referral loop detection 7.3.4. Referral Loop Detection
In response to a Map-Referral message with action code NODE-REFERRAL 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 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 node RLOCs that are expected to have more-specific XEID-prefix
information for the requested XEID. To prevent a possible "iteration information for the requested XEID. To prevent a possible "iteration
loop" (following referrals back-and-forth among a set of DDT nodes loop" (following referrals back and forth among a set of DDT nodes
without ever finding an answer), a DDT client saves the last received without ever finding an answer), a DDT client saves the last received
referral XEID-prefix for each pending request and checks that a newly referral XEID-prefix for each pending request and checks to see if a
received NODE-REFERRAL or MS-REFERRAL message contains a more- newly received NODE-REFERRAL or MS-REFERRAL message contains a
specific referral XEID-prefix; an exact or less-specific match of the more-specific referral XEID-prefix; an exact or less-specific match
saved XEID-prefix indicates a referral loop. If a loop is detected, of the saved XEID-prefix indicates a referral loop. If a loop is
the DDT Map Resolver handles the request as described in detected, the DDT Map-Resolver handles the request as described in
Section 7.3.3. Otherwise, the DDT client saves the most recently Section 7.3.3. Otherwise, the DDT client saves the most recently
received referral XEID-prefix with the pending request when it received referral XEID-prefix with the pending request when it
follows the referral. follows the referral.
As an extra measure to prevent referral loops, it is probably also 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 wise to limit the total number of referrals for any request to some
reasonable number; the exact value of that number will be determined reasonable number; the exact value of that number will be determined
during experimental deployment of LISP-DDT, but is bounded by the during experimental deployment of LISP-DDT but is bounded by the
maximum length of the XEID. maximum length of the XEID.
Note that when a DDT client adds an entry to its lookup queue and 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 sends an initial Map-Request for an XEID, the queue entry has no
previous referral XEID-prefix; this means that the first DDT node previous referral XEID-prefix; this means that the first DDT node
contacted by a DDT Map Resolver may provide a referral to anywhere in 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 the DDT hierarchy. This, in turn, allows a DDT client to use
essentially any DDT node RLOCs for its initial cache entries and essentially any DDT node RLOCs for its initial cache entries and
depend on the initial referral to provide a good starting point for 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 Map-Requests; there is no need to configure the same set of root DDT
nodes on all DDT clients. nodes on all DDT clients.
8. Pseudo Code and Decision Tree diagrams 8. Pseudocode and Decision Tree Diagrams
To illustrate DDT algorithms described above and to aid in To illustrate the DDT algorithms described above and to aid in
implementation, each of the major DDT Map Server and DDT Map Resolver implementation, each of the major DDT Map-Server and DDT Map-Resolver
functions are described below, first using simple "psuedo-code" and functions are described below, first using simple "pseudocode" and
then in the form of a decision tree. then in the form of a decision tree.
8.1. Map Resolver processing of ITR Map-Request 8.1. Map-Resolver Processing of ITR Map-Request
8.1.1. Pseudo-code summary 8.1.1. Pseudocode Summary
if ( request pending i.e., (ITR,EID) of request same ) { if ( request pending, i.e., (ITR,EID) of request same ) {
replace old request with new & use new request nonce replace old request with new, & use new request nonce
for future requests for future requests
} else if ( no match in refcache ) { } else if ( no match in refcache ) {
return negative map-reply to ITR return Negative Map-Reply to ITR
} else if ( match type delegation hole ) { } else if ( match type DELEGATION-HOLE ) {
return negative map-reply to ITR return Negative Map-Reply to ITR
} else if ( match type ms-ack ) { } else if ( match type MS-ACK ) {
fwd DDT request to map-server fwd DDT Map-Request to Map-Server
} else { } else {
store & fwd DDT request w/o security material to node delegation store & fwd DDT Map-Request w/o security material
to node delegation
} }
8.1.2. Decision tree diagram 8.1.2. Decision Tree Diagram
+------------+ +------------+
| Is Request | Yes | Is request | Yes
| |----> Replace old request with | pending? |----> Replace old request with
| Pending? | new nonce for future requests | | new nonce for future requests
+------------+ +------------+
| |
|No |No
| |
V V
+------------+ +------------+
| Match In | No | Match in | No
| Referral |----> Send Negative Map-Reply | referral |----> Send Negative Map-Reply
| cache? | (not a likely event as root or | cache? | (not a likely event, as root or
+------------+ hint configured on every MR) +------------+ hint configured on every Map-Resolver)
| |
|Yes |Yes
| |
V V
+------------+ +-------------+
| Match Type | Yes | Match type | Yes
| Delegation |----> Send Negative Map-Reply | DELEGATION- |----> Send Negative Map-Reply
| Hole? | | HOLE? |
+------------+ +-------------+
| |
|No |No
| |
V V
+------------+ +------------+
| Match Type | Yes | Match type | Yes
| MS-ACK? |----> Forward DDT Map-request to Map-Server | MS-ACK? |----> Forward DDT Map-Request to Map-Server
| | | |
+------------+ +------------+
| |
|No |No
| |
V V
Store request & Fwd DDT Request w/o security material Store original request & send DDT Map-Request w/o security material
to DDT node delegation to DDT node delegation
8.2. Map Resolver processing of Map-Referral message 8.2. Map-Resolver Processing of Map-Referral Message
8.2.1. Pseudo-code summary 8.2.1. Pseudocode Summary
if ( authentication signature validation failed ) { if ( authentication signature validation failed ) {
silently drop silently drop
} }
if ( no request pending matched by referral nonce ) { if ( no request pending matched by referral nonce ) {
silently drop silently drop
} }
if ( pfx in referral less specific than last referral used ) { if ( pfx in referral less specific than last referral used ) {
if ( gone through root ) { if ( gone through root ) {
silently drop silently drop
} else { } else {
send request to root send request to root
} }
} }
switch (map_referral_type) { switch (map_referral_type) {
case NOT_AUTHORITATIVE : case NOT_AUTHORITATIVE:
if ( gone through root ) { if ( gone through root ) {
return negative map-reply to ITR return Negative Map-Reply to ITR
} else { } else {
send request to root send request to root
} }
case DELEGATION_HOLE: case DELEGATION_HOLE:
cache & send negative map-reply to ITR cache & send Negative Map-Reply to ITR
case MS_REFERRAL: case MS_REFERRAL:
if ( referral equal to last used ) { if ( referral equal to last used ) {
if ( gone through root ) { if ( gone through root ) {
return negative map-reply to ITR return Negative Map-Reply to ITR
} else { } else {
send request to root send request to root
} }
} else { } else {
cache cache
follow the referral, include security material follow the referral; include security material
} }
case NODE_REFERRAL: case NODE_REFERRAL:
if ( referral equal to last used ) { if ( referral equal to last used ) {
if ( gone through root ) { if ( gone through root ) {
return negative map-reply to ITR return Negative Map-Reply to ITR
} else { } else {
send request to root send request to root
} }
} else { } else {
cache cache
follow the referral, strip security material follow the referral; strip security material
} }
case MS_ACK: case MS_ACK:
if ( security material stripped ) { if ( security material stripped ) {
resend request with security material resend request with security material
if { !incomplete } { if { !incomplete } {
cache cache
} }
} }
case MS_NOT_REGISTERED: case MS_NOT_REGISTERED:
if { all map-server delegations not tried } { if { all Map-Server delegations not tried } {
follow delegations not tried follow delegations not tried
if ( !incomplete ) { if ( !incomplete ) {
cache cache
} }
} else { } else {
send negative map-reply to ITR send Negative Map-Reply to ITR
if { !incomplete } { if { !incomplete } {
cache cache
} }
} }
case DEFAULT: case DEFAULT:
drop drop
} }
} }
8.2.2. Decision tree diagram 8.2.2. Decision Tree Diagram
+----------------+ +----------------+
| Auth Signature | No | Auth signature | No
| Valid? |----> Silently drop | valid? |----> Silently drop
+----------------+ +----------------+
| Yes | Yes
V V
+------------+ +------------+
| Is Request | No | Is request | No
| Pending? |----> Silently drop | pending? |----> Silently drop
+------------+ +------------+
| Yes | Yes
V V
+------------------------------+ Yes +------------------------------+ Yes
| Pfx less specific than last? |----> Silently drop | Pfx less specific than last? |----> Silently drop
+------------------------------+ +------------------------------+
|No |No
V V
+---------------------------------------------------+ +---------------------------------------------------+
| What is Map-Referral Type? |--UNKNOWN-+ | What is Map-Referral type? |--Unknown-+
+---------------------------------------------------+ | +---------------------------------------------------+ |
| | | | | | V | | | | | | V
| | | | | DEL_HOLE DROP | | | | | DEL_HOLE Drop
| | | | MS_ACK | | | | | MS_ACK |
| | | | | V | | | | | V
| | MS_REF NODE_REF | Cache & return | | MS_REF NODE_REF | Cache & return
| | | | V negative map-reply | | | | V Negative Map-Reply
| | | | +---------+ | | | | +---------+
| NOT_AUTH | | | Was sec | Yes | NOT_AUTH | | | Was sec | Yes
| | | | | material| | | | | | material|
| | | | |Stripped?|----> Done | | | | |stripped?|----> Done
| | V V +---------+ | | V V +---------+
| | +------------+ | No | | +------------+ | No
| | Yes | Pfx equal | V | | Yes | Pfx equal | V
MS_NOT_REGISTERED | +---| to last | +------------+ MS_NOT_REGISTERED | +---| to last | +------------+
| | | | used? | | Incomplete | Yes | | | | used? | |"Incomplete"| Yes
| | | +------------+ | bit set? |---> Resend DDT | | | +------------+ | bit set? |---> Resend DDT
| V V |No +------------+ request w | V V |No +------------+ request w/
| +------------+ | |No security | +------------+ | |No security
| | Gone | V | material | | Gone | V | material
| | Through | Cache & follow V | | through | Cache & follow V
| | Root? | the referral Cache & resend DDT | | root? | the referral Cache & resend DDT
| +------------+ request with | +------------+ request with
| |No |Yes security material | |No |Yes security material
| | | | | |
| V V | V V
| Send req Send negative map-reply | Send req Send Negative Map-Reply
| to root | to root
V V
+-----------+ Yes +-----------+ Yes +-----------+ Yes +------------+ Yes
| Other MS |----Follow other MS-------->|Incomplete |----> Don't cache | Other MS |---Follow other MS-------->|"Incomplete"|----> Don't cache
| not tried?| |bit set? | | not tried?| | bit set? |
| |---Send negative map-reply->| |----> Cache | |--Send Negative Map-Reply->| |----> Cache
+-----------+ No +-----------+ No +-----------+ No +------------+ No
8.3. DDT Node processing of DDT Map-Request message 8.3. DDT Node Processing of DDT Map-Request Message
8.3.1. Pseudo-code summary 8.3.1. Pseudocode Summary
if ( I am not authoritative ) {
send map-referral NOT_AUTHORITATIVE with if ( I am not authoritative ) {
incomplete bit set and ttl 0 send Map-Referral NOT_AUTHORITATIVE with
} else if ( delegation exists ) { "Incomplete" bit set and TTL 0
if ( delegated map-servers ) { } else if ( delegation exists ) {
send map-referral MS_REFERRAL with if ( delegated Map-Servers ) {
ttl 'Default_DdtNode_Ttl' send Map-Referral MS_REFERRAL with
} else { TTL 'Default_DdtNode_Ttl'
send map-referral NODE_REFERRAL with } else {
ttl 'Default_DdtNode_Ttl' send Map-Referral NODE_REFERRAL with
} TTL 'Default_DdtNode_Ttl'
} else { }
if ( eid in site) { } else {
if ( site registered ) { if ( EID in site) {
forward map-request to etr if ( site registered ) {
if ( map-server peers configured ) { forward Map-Request to ETR
send map-referral MS_ACK with if ( Map-Server peers configured ) {
ttl 'Default_Registered_Ttl' send Map-Referral MS_ACK with
} else { TTL 'Default_Registered_Ttl'
send map-referral MS_ACK with } else {
ttl 'Default_Registered_Ttl' and incomplete bit set send Map-Referral MS_ACK with
} TTL 'Default_Registered_Ttl' and "Incomplete" bit set
} else { }
if ( map-server peers configured ) { } else {
send map-referral MS_NOT_REGISTERED with if ( Map-Server peers configured ) {
ttl 'Default_Configured_Not_Registered_Ttl' send Map-Referral MS_NOT_REGISTERED with
} else { TTL 'Default_Configured_Not_Registered_Ttl'
send map-referral MS_NOT_REGISTERED with } else {
ttl 'Default_Configured_Not_Registered_Ttl' send Map-Referral MS_NOT_REGISTERED with
and incomplete bit set TTL 'Default_Configured_Not_Registered_Ttl'
} and "Incomplete" bit set
} }
} else { }
send map-referral DELEGATION_HOLE with
ttl 'Default_Negative_Referral_Ttl' } else {
} send Map-Referral DELEGATION_HOLE with
} TTL 'Default_Negative_Referral_Ttl'
}
}
where architectural constants for TTL are set as follows: where architectural constants for TTL are set as follows:
Default_DdtNode_Ttl 1440 minutes Default_DdtNode_Ttl 1440 minutes
Default_Registered_Ttl 1440 minutes Default_Registered_Ttl 1440 minutes
Default_Negative_Referral_Ttl 15 minutes Default_Negative_Referral_Ttl 15 minutes
Default_Configured_Not_Registered_Ttl 1 minute Default_Configured_Not_Registered_Ttl 1 minute
8.3.2. Decision tree diagram 8.3.2. Decision Tree Diagram
+------------+ +------------+
| Am I | No | Am I | No
| Authori- |----> Return NOT_AUTHORITATIVE | authori- |----> Return NOT_AUTHORITATIVE
| tative? | Incomplete = 1 | tative? | Incomplete = 1
+------------+ ttl = Default_DdtNode_Ttl +------------+ TTL = Default_DdtNode_Ttl
| |
|Yes |Yes
| |
V V
+------------+ +------------+ +------------+ +-------------+
| Delegation | Yes | Delegations| Yes | Delegation | Yes | Delegations | Yes
| Exists? |---->| are map |----> Return MS_REFERRAL | exists? |---->| are |----> Return MS_REFERRAL
| | | servers? | ttl = Default_DdtNode_Ttl | | | Map-Servers?| TTL = Default_DdtNode_Ttl
+------------+ +------------+ +------------+ +-------------+
| \ No | \ No
|No +--> Return NODE_REFERRAL |No +--> Return NODE_REFERRAL
| ttl = Default_DdtNode_Ttl | TTL = Default_DdtNode_Ttl
V V
+------------+ +------------+ +------------+ +------------+ +------------+ +------------+
| EID in | Yes | Site | Yes | Map-server | | EID in | Yes | Site | Yes | Map-Server |
| Site |---->| Registered?|----> Forward---->| peers | | site |---->| registered?|----> Forward---->| peers |
| Config? | | | Map-request | configured?| | config? | | | Map-Request | configured?|
+------------+ +------------+ to ETR +------------+ +------------+ +------------+ to ETR +------------+
| | | | | | | |
| |No No| |Yes | |No No| |Yes
| | | | | | | |
| | V V | | V V
| | Return MS_ACK Return MS_ACK | | Return MS_ACK Return MS_ACK
| V with INC=1 | V with INC=1
| +------------+ ttl=Default_Registered_Ttl | +------------+ TTL = Default_Registered_Ttl
| | Map-server | Yes | | Map-Server | Yes
| | peers |----> Return MS_NOT_REGISTERED | | peers |----> Return MS_NOT_REGISTERED
| | configured?| ttl = Default_Negative_Referral_Ttl | | configured?| TTL = Default_Negative_Referral_Ttl
| +------------+ | +------------+
| \ No | \ No
|No +--> Return MS_NOT_REGISTERED |No +--> Return MS_NOT_REGISTERED
| Incomplete = 1 | Incomplete = 1
V ttl = Default_Negative_Referral_Ttl V TTL = Default_Negative_Referral_Ttl
Return DELEGATION_HOLE Return DELEGATION_HOLE
ttl = Default_Negative_Referral_Ttl TTL = Default_Negative_Referral_Ttl
9. Example topology and request/referral following 9. Example Topology and Request/Referral Following
This chapter shows example DDT tree and several possible scenarios of This section shows an example DDT tree and several possible scenarios
Map-Requests coming to a Map Resolver and subsequent iterative DDT of Map-Requests coming to a Map-Resolver and subsequent iterative DDT
referrals. For the sake of example RLOCs of DDT nodes are shown in referrals. In this example, RLOCs of DDT nodes are shown in the IPv4
IPv4 address space while the EIDs are in IPv6 AF. The same principle address space while the EIDs are in the IPv6 AF. The same principle
of hierarchical delegation and pinpointing referrals is equally of hierarchical delegation and pinpointing referrals is equally
applicable to any AF whose address hierarchy can be expressed as a applicable to any AF whose address hierarchy can be expressed as a
bitstring with associated length. DDT tree of IPv4 prefixes is bit string with associated length. The DDT "tree" of IPv4 prefixes
another AF with immediate practical value. is another AF with immediate practical value. This section could
benefit from additional examples, perhaps including one using IPv4
EIDs and another using IPv6 RLOCs. If this document is moved to the
Standards Track, consideration should be given to adding such
examples.
To show how referrals are followed to find the RLOCs for a number of To show how referrals are followed to find the RLOCs for a number of
EIDs, consider the following example EID topology for DBID=0, IID=0, EIDs, consider the following example EID topology for DBID=0, IID=0,
AFI=2, and EID=0/0 AFI=2, and EID=0/0:
+---------------------+ +---------------------+ +---------------------+ +---------------------+
| root1: 192.0.2.1 | | root2: 192.0.2.2 | | root1: 192.0.2.1 | | root2: 192.0.2.2 |
| authoritative: ::/0 | | authoritative: ::/0 | | authoritative: ::/0 | | authoritative: ::/0 |
+---------------------+ +---------------------+ +---------------------+ +---------------------+
| \ / | | \ / |
| \ / | | \ / |
| X | | X |
| / \ | | / \ |
| / \ | | / \ |
| | | | | | | |
V V V V V V V V
+-------------------------+ +--------------------------+ +-------------------------+ +--------------------------+
| DDT node1: 192.0.2.11 | | DDT node2: 192.0.2.12 | | DDT node1: 192.0.2.11 | | DDT node2: 192.0.2.12 |
| authoritative: | | authoritative: | | authoritative: | | authoritative: |
| 2001:db8::/32 | | 2001:db8::/32 | | 2001:db8::/32 | | 2001:db8::/32 |
+-------------------------+ +--------------------------+ +-------------------------+ +--------------------------+
| \ / | | \ / |
| \ / | | \ / |
| X | | X |
| / \ | | / \ |
| / \ | | / \ |
| | | | | | | |
V V V V V V V V
+--------------------------+ +---------------------------+ +--------------------------+ +---------------------------+
| Map-Server1: 192.0.2.101 | | DDT node3: 192.0.2.201 | | Map-Server1: 192.0.2.101 | | DDT node3: 192.0.2.201 |
skipping to change at page 29, line 46 skipping to change at page 32, line 51
V V V V
+---------------------------+ +---------------------------+ +---------------------------+ +---------------------------+
| Map-Server2: 192.0.2.211 | | Map-Server3: 192.0.2.221 | | Map-Server2: 192.0.2.211 | | Map-Server3: 192.0.2.221 |
| authoritative: | | authoritative: | | authoritative: | | authoritative: |
| 2001:db8:0500::/48 | | 2001:db8:0501::/48 | | 2001:db8:0500::/48 | | 2001:db8:0501::/48 |
|site3: 2001:db8:0500:1::/64| |site5: 2001:db8:0501:8::/64| |site3: 2001:db8:0500:1::/64| |site5: 2001:db8:0501:8::/64|
|site4: 2001:db8:0500:2::/64| |site6: 2001:db8:0501:9::/64| |site4: 2001:db8:0500:2::/64| |site6: 2001:db8:0501:9::/64|
+---------------------------+ +---------------------------+ +---------------------------+ +---------------------------+
DDT nodes are configured for this "root" at IP addresses 192.0.2.1 DDT nodes are configured for this "root" at IP addresses 192.0.2.1
and 192.0.2.2. DDT Map Resolvers are configured with default and 192.0.2.2. DDT Map-Resolvers are configured with default
referral cache entries to these addresses. referral cache entries for these addresses.
The root DDT nodes delegate 2001:db8::/32 to two DDT nodes with IP The root DDT nodes delegate 2001:db8::/32 to two DDT nodes with IP
addresses 192.0.2.11 and 192.0.2.12. addresses 192.0.2.11 and 192.0.2.12.
The DDT nodes for 2001:db8::/32 delegate 2001:db8:0100::/40 to a DDT The DDT nodes for 2001:db8::/32 delegate 2001:db8:0100::/40 to a DDT
Map Server with RLOC 192.0.2.101 Map-Server with RLOC 192.0.2.101.
The DDT Map Server for 2001:db8:0100::/40 is configured to allow ETRs The DDT Map-Server for 2001:db8:0100::/40 is configured to allow ETRs
to register the sub-prefixes 2001:db8:0103::/48 and to register the sub-prefixes 2001:db8:0103::/48 and
2001:db8:0104::/48 2001:db8:0104::/48.
The DDT nodes for 2001:db8::/32 also delegate 2001:db8:0500::/40 to a The DDT nodes for 2001:db8::/32 also delegate 2001:db8:0500::/40 to a
DDT node with RLOC 192.0.2.201 DDT node with RLOC 192.0.2.201.
The DDT node for 2001:db8:0500::/40 is further configured to delegate The DDT node for 2001:db8:0500::/40 is further configured to delegate
2001:db8:0500::/48 to a DDT Map Server with RLOC 192.0.2.211 and 2001:db8:0500::/48 to a DDT Map-Server with RLOC 192.0.2.211 and
2001:db8:0501::/48 to a DDT Map Server with RLOC 192.0.2.221 2001:db8:0501::/48 to a DDT Map-Server with RLOC 192.0.2.221.
The DDT Map Server for 2001:db8:0500::/48 is configured to allow ETRs The DDT Map-Server for 2001:db8:0500::/48 is configured to allow ETRs
to register the sub-prefixes 2001:db8:0500:1::/64 and to register the sub-prefixes 2001:db8:0500:1::/64 and
2001:db8:0500:2::/64 2001:db8:0500:2::/64.
The DDT Map Server for 2001:db8:0501::/48 is configured to allow ETRs The DDT Map-Server for 2001:db8:0501::/48 is configured to allow ETRs
to register the sub-prefixes 2001:db8:0501:8::/64 and to register the sub-prefixes 2001:db8:0501:8::/64 and
2001:db8:0501:9::/64 2001:db8:0501:9::/64.
9.1. Lookup of 2001:db8:0103:1::1/128 9.1. Lookup of 2001:db8:0103:1::1/128
The first example shows a DDT Map Resolver following a delegation 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 from the root to a DDT node followed by another delegation to a DDT
Map Server. Map-Server.
ITR1 sends an Encapsulated Map-Request for 2001:db8:0103:1::1 to one ITR1 sends an Encapsulated Map-Request for 2001:db8:0103:1::1 to one
of its configured (DDT) Map Resolvers. The DDT Map Resolver proceeds of its configured (DDT) Map-Resolvers. The DDT Map-Resolver proceeds
as follows: as follows:
1. Send DDT Map-Request (for 2001:db8:0103:1::1) to one of the root 1. Send a DDT Map-Request (for 2001:db8:0103:1::1) to one of the
DDT nodes, 192.0.2.1 or 192.0.2.2 root DDT nodes (192.0.2.1 or 192.0.2.2).
2. Receive (and save in referral cache) Map-Referral for EID-prefix 2. Receive (and save in the referral cache) the Map-Referral for
2001:db8::/32, action code NODE-REFERRAL, RLOC set (192.0.2.11, EID-prefix 2001:db8::/32, action code NODE-REFERRAL, RLOC set
192.0.2.12) (192.0.2.11, 192.0.2.12).
3. Send DDT Map-Request to 192.0.2.11 or 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 referral cache) Map-Referral for EID-prefix 4. Receive (and save in the referral cache) the Map-Referral for
2001:db8:0100::/40, action code MS-REFERRAL, RLOC set EID-prefix 2001:db8:0100::/40, action code MS-REFERRAL, RLOC set
(192.0.2.101) (192.0.2.101).
5. Send DDT Map-Request to 192.0.2.101; if the ITR-originated 5. Send a DDT Map-Request to 192.0.2.101; if the ITR-originated
Encapsulated Map-Request had a LISP-SEC signature, it is included Encapsulated Map-Request had a LISP-SEC signature, it is
included.
6. DDT Map Server at 192.0.2.101 decapsulates the DDT Map-Request 6. The DDT Map-Server at 192.0.2.101 decapsulates the DDT
and forwards to a registered site1 ETR for 2001:db8:0103::/48 Map-Request and forwards the Map-Request to a registered site1
ETR for 2001:db8:0103::/48.
7. DDT Map Server at 192.0.2.101 sends a Map-Referral message for 7. The DDT Map-Server at 192.0.2.101 sends a Map-Referral message
EID-prefix 2001:db8:0103::/48, action code MS-ACK to the DDT Map for EID-prefix 2001:db8:0103::/48, action code MS-ACK, to the DDT
Resolver Map-Resolver.
8. DDT Map Resolver receives Map-Referral message and dequeues the 8. The DDT Map-Resolver receives the Map-Referral message and
pending request for 2001:db8:0103:1::1 dequeues the pending request for 2001:db8:0103:1::1.
9. site1 ETR for 2001:db8:0103::/48 receives Map-Request forwarded 9. The site1 ETR for 2001:db8:0103::/48 receives the Map-Request
by DDT Map Server and sends Map-Reply to ITR1 forwarded by the DDT Map-Server and sends a Map-Reply to ITR1.
9.2. Lookup of 2001:db8:0501:8:4::1/128 9.2. Lookup of 2001:db8:0501:8:4::1/128
The next example shows a three-level delegation: root to first DDT The next example shows a three-level delegation: root to first DDT
node, first DDT node to second DDT node, second DDT node to DDT Map node, first DDT node to second DDT node, and second DDT node to DDT
Server. Map-Server.
ITR2 sends an Encapsulated Map-Request for 2001:db8:0501:8:4::1 to ITR2 sends an Encapsulated Map-Request for 2001:db8:0501:8:4::1 to
one of its configured (DDT) Map Resolvers, which are different from one of its configured (DDT) Map-Resolvers, which are different from
those for ITR1. The DDT Map Resolver proceeds as follows: those for ITR1. The DDT Map-Resolver proceeds as follows:
1. Send DDT Map-Request (for 2001:db8:0501:8:4::1) to one of the 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 root DDT nodes (192.0.2.1 or 192.0.2.2).
2. Receive (and save in referral cache) Map-Referral for EID-prefix 2. Receive (and save in the referral cache) the Map-Referral for
2001:db8::/32, action code NODE-REFERRAL, RLOC set (192.0.2.11, EID-prefix 2001:db8::/32, action code NODE-REFERRAL, RLOC set
192.0.2.12) (192.0.2.11, 192.0.2.12).
3. Send DDT Map-Request to 192.0.2.11 or 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 referral cache) Map-Referral for EID-prefix 4. Receive (and save in the referral cache) the Map-Referral for
2001:db8:0500::/40, action code NODE-REFERRAL, RLOC set EID-prefix 2001:db8:0500::/40, action code NODE-REFERRAL, RLOC
(192.0.2.201) set (192.0.2.201).
5. Send DDT Map-Request to 192.0.2.201 5. Send a DDT Map-Request to 192.0.2.201.
6. Receive (and save in referral cache) Map-Referral for EID-prefix 6. Receive (and save in the referral cache) the Map-Referral for
2001:db8:0501::/48, action code MS-REFERRAL, RLOC set EID-prefix 2001:db8:0501::/48, action code MS-REFERRAL, RLOC set
(192.0.2.221) (192.0.2.221).
7. Send DDT Map-Request to 192.0.2.221; if the ITR-originated 7. Send a DDT Map-Request to 192.0.2.221; if the ITR-originated
Encapsulated Map-Request had a LISP-SEC signature, it is Encapsulated Map-Request had a LISP-SEC signature, it is
included included.
8. DDT Map Server at 192.0.2.221 decapsulates the DDT Map-Request 8. The DDT Map-Server at 192.0.2.221 decapsulates the DDT
and forwards to a registered site5 ETR for 2001:db8:0501:8::/64 Map-Request and forwards the Map-Request to a registered site5
ETR for 2001:db8:0501:8::/64.
9. DDT Map Server at 192.0.2.221 sends a Map-Referral message for 9. The DDT Map-Server at 192.0.2.221 sends a Map-Referral message
EID-prefix 2001:db8:0501:8::/64, action code MS-ACK, to the DDT for EID-prefix 2001:db8:0501:8::/64, action code MS-ACK, to the
Map Resolver DDT Map-Resolver.
10. DDT Map Resolver receives Map-Referral(MS-ACK) message and 10. The DDT Map-Resolver receives a Map-Referral(MS-ACK) message and
dequeues the pending request for 2001:db8:0501:8:4::1 dequeues the pending request for 2001:db8:0501:8:4::1.
11. site5 ETR for 2001:db8:0501:8::/64 receives Map-Request 11. The site5 ETR for 2001:db8:0501:8::/64 receives a Map-Request
forwarded by DDT Map Server and sends Map-Reply to ITR2 forwarded by the DDT Map-Server and sends a Map-Reply to ITR2.
9.3. Lookup of 2001:db8:0104:2::2/128 9.3. Lookup of 2001:db8:0104:2::2/128
This example shows how a DDT Map Resolver uses a saved referral cache This example shows how a DDT Map-Resolver uses a saved referral cache
entry to skip the referral process and go directly to a DDT Map entry to skip the referral process and go directly to a DDT
Server for a prefix that is similar to one previously requested. Map-Server for a prefix that is similar to one previously requested.
In this case, ITR1 uses the same Map Resolver used in example In this case, ITR1 uses the same Map-Resolver used in the example in
Section 9.1. It sends an Encapsulated Map-Request for Section 9.1. It sends an Encapsulated Map-Request for
2001:db8:0104:2::2 to that (DDT) Map Resolver. The DDT Map-Resolver 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 finds an MS-REFERRAL cache entry for 2001:db8:0100::/40 with RLOC set
(192.0.2.101) and proceeds as follows: (192.0.2.101) and proceeds as follows:
1. Send DDT Map-Request (for 2001:db8:0104:2::2) to 192.0.2.101; if 1. Send a DDT Map-Request (for 2001:db8:0104:2::2) to 192.0.2.101;
the ITR-originated Encapsulated Map-Request had a LISP-SEC if the ITR-originated Encapsulated Map-Request had a LISP-SEC
signature, it is included signature, it is included.
2. DDT Map Server at 192.0.2.101 decapsulates the DDT Map-Request 2. The DDT Map-Server at 192.0.2.101 decapsulates the DDT
and forwards to a registered site2 ETR for 2001:db8:0104::/48 Map-Request and forwards the Map-Request to a registered site2
ETR for 2001:db8:0104::/48.
3. DDT Map Server at 192.0.2.101 sends a Map-Referral message for 3. The DDT Map-Server at 192.0.2.101 sends a Map-Referral message
EID-prefix 2001:db8:0104::/48, action code MS-ACK to the DDT Map for EID-prefix 2001:db8:0104::/48, action code MS-ACK, to the DDT
Resolver Map-Resolver.
4. DDT Map Resolver receives Map-Referral(MS-ACK) and dequeues the 4. The DDT Map-Resolver receives the Map-Referral (MS-ACK) and
pending request for 2001:db8:0104:2::2 dequeues the pending request for 2001:db8:0104:2::2.
5. site2 ETR for 2001:db8:0104::/48 receives Map-Request and sends 5. The site2 ETR for 2001:db8:0104::/48 receives a Map-Request and
Map-Reply to ITR1 sends a Map-Reply to ITR1.
9.4. Lookup of 2001:db8:0500:2:4::1/128 9.4. Lookup of 2001:db8:0500:2:4::1/128
This example shows how a DDT Map Resolver uses a saved referral cache This example shows how a DDT Map-Resolver uses a saved referral cache
entry to start the referral process at a non-root, intermediate DDT entry to start the referral process at a non-root, intermediate DDT
node for a prefix that is similar to one previously requested. node for a prefix that is similar to one previously requested.
In this case, ITR2 asks the same Map Resolver used in example In this case, ITR2 uses the same Map-Resolver used in the example in
Section 9.2. It sends an Encapsulated Map-Request for Section 9.2. It sends an Encapsulated Map-Request for
2001:db8:0500:2:4::1 to that (DDT) Map Resolver, which finds a NODE- 2001:db8:0500:2:4::1 to that (DDT) Map-Resolver, which finds a
REFERRAL cache entry for 2001:db8:0500::/40 with RLOC set NODE-REFERRAL cache entry for 2001:db8:0500::/40 with RLOC set
(192.0.2.201). It proceeds as follows: (192.0.2.201). It proceeds as follows:
1. Send DDT Map-Request (for 2001:db8:0500:2:4::1) to 192.0.2.201 1. Send a DDT Map-Request (for 2001:db8:0500:2:4::1) to 192.0.2.201.
2. Receive (and save in referral cache) Map-Referral for EID-prefix 2. Receive (and save in the referral cache) the Map-Referral for
2001:db8:0500::/48, action code MS-REFERRAL, RLOC set EID-prefix 2001:db8:0500::/48, action code MS-REFERRAL, RLOC set
(192.0.2.211) (192.0.2.211).
3. Send DDT Map-Request to 192.0.2.211; if the ITR-originated 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 Encapsulated Map-Request had a LISP-SEC signature, it is
included.
4. DDT Map Server at 192.0.2.211 decapsulates the DDT Map-Request 4. The DDT Map-Server at 192.0.2.211 decapsulates the DDT
and forwards to a registered site4 ETR for 2001:db8:0500:2::/64 Map-Request and forwards the Map-Request to a registered site4
ETR for 2001:db8:0500:2::/64.
5. DDT Map Server at 192.0.2.211 sends a Map-Referral message for 5. The DDT Map-Server at 192.0.2.211 sends a Map-Referral message
EID-prefix 2001:db8:0500:2::/64, action code MS-ACK to the DDT for EID-prefix 2001:db8:0500:2::/64, action code MS-ACK, to the
Map Resolver DDT Map-Resolver.
6. DDT Map Resolver receives Map-Referral(MS-ACK) and dequeues the 6. The DDT Map-Resolver receives the Map-Referral (MS-ACK) and
pending request for 2001:db8:0500:2:4::1 dequeues the pending request for 2001:db8:0500:2:4::1.
7. site4 ETR for 2001:db8:0500:2::/64 receives Map-Request and sends 7. The site4 ETR for 2001:db8:0500:2::/64 receives a Map-Request and
Map-Reply to ITR2 sends a Map-Reply to ITR2.
9.5. Lookup of 2001:db8:0500::1/128 (non-existent EID) 9.5. Lookup of 2001:db8:0500::1/128 (Nonexistent EID)
This example uses the cached MS-REFERRAL for 2001:db8:0500::/48 This example uses the cached MS-REFERRAL for 2001:db8:0500::/48
learned above to start the lookup process at the DDT Map-Server at learned above to start the lookup process at the DDT Map-Server at
192.0.2.211. The DDT Map Resolver proceeds as follows: 192.0.2.211. The DDT Map-Resolver proceeds as follows:
1. Send DDT Map-Request (for 2001:db8:0500::1) to 192.0.2.211; if 1. Send a DDT Map-Request (for 2001:db8:0500::1) to 192.0.2.211; if
the ITR-originated Encapsulated Map-Request had a LISP-SEC the ITR-originated Encapsulated Map-Request had a LISP-SEC
signature, it is included signature, it is included.
2. DDT Map Server at 192.0.2.211, which is authoritative for 2. The DDT Map-Server at 192.0.2.211, which is authoritative for
2001:db8:0500::/48, does not have a matching delegation for 2001:db8:0500::/48, does not have a matching delegation for
2001:db8:0500::1. It responds with a Map-Referral message for 2001:db8:0500::1. It responds with a Map-Referral message for
2001:db8:0500::/64, action code DELEGATION-HOLE to the DDT Map 2001:db8:0500::/64, action code DELEGATION-HOLE, to the DDT
Resolver. The prefix 2001:db8:0500::/64 is used because it is Map-Resolver. The prefix 2001:db8:0500::/64 is used because it
the least-specific prefix that does match the requested EID, but is the least-specific prefix that does match the requested EID
does not match one of configured delegations but does not match one of the configured delegations
(2001:db8:0500:1::/64 and 2001:db8:0500:2::/64). (2001:db8:0500:1::/64 and 2001:db8:0500:2::/64).
3. DDT Map Resolver receives the delegation, adds a negative 3. The DDT Map-Resolver receives the delegation, adds a negative
referral cache entry for 2001:db8:0500::/64, dequeues the pending referral cache entry for 2001:db8:0500::/64, dequeues the pending
request for 2001:db8:0500::1, and returns a negative Map-Reply to request for 2001:db8:0500::1, and returns a Negative Map-Reply
ITR2. to ITR2.
10. Securing the database and message exchanges 10. Securing the Database and Message Exchanges
This section specifies the DDT security architecture that provides This section specifies the DDT security architecture that provides
data origin authentication, data integrity protection, and XEID- data origin authentication, data integrity protection, and
prefix delegation. Global XEID-prefix authorization is out of the XEID-prefix delegation. Global XEID-prefix authorization is out of
scope of this document. scope for this document.
Each DDT node is configured with one or more public/private key Each DDT node is configured with one or more public/private key pairs
pair(s) that are used to digitally sign referral records for XEID- that are used to digitally sign Map-Referral Records for
prefix(es) that the DDT node is authoritative for. In other words, XEID-prefix(es) for which the DDT node is authoritative. In other
each public/private key pair is associated with the combination of a words, each public/private key pair is associated with the
DDT node and a XEID-prefix that it is authoritative for. Every DDT combination of a DDT node and an XEID-prefix for which it is
node is also configured with the public keys of its children DDT authoritative. Every DDT node is also configured with the public
nodes. By including public keys of target child DDT nodes in the keys of its child DDT nodes. By including the public keys of target
Map-Referral records, and signing each record with the DDT node's child DDT nodes in the Map-Referral Records and signing each Record
private key, a DDT node can securely delegate sub-prefixes of its with the DDT node's private key, a DDT node can securely delegate
authoritative XEID-prefixes to its children DDT nodes. A DDT node sub-prefixes of its authoritative XEID-prefixes to its child DDT
configured to provide hints must also have the public keys of the DDT nodes. A DDT node configured to provide hints must also have the
nodes that its hints point to. DDT node keys can be encoded using public keys of the DDT nodes to which its hints point. DDT node keys
LCAF type 11 to associate the key to the RLOC of the referred DDT can be encoded using LCAF Type 11 to associate the key to the RLOC of
node. If a node has more than one public key, it should sign its the referred DDT node. If a node has more than one public key, it
records with at least one of these keys. When a node has N keys, it should sign its Records with at least one of these keys. When a node
can sustain up to N-1 key compromises. Revocation mechanism is has N keys, it can sustain up to N-1 key compromises. The revocation
described in Section 10.2.1. mechanism is described in Section 10.2.1.
Map Resolvers are configured with one or more trusted public keys Map-Resolvers are configured with one or more trusted public keys,
referred to as trust anchors. Trust anchors are used to authenticate referred to as "trust anchors". Trust anchors are used to
the DDT security infrastructure. Map Resolvers can discover a DDT authenticate the DDT security infrastructure. Map-Resolvers can
node's public key either by having it configured as a trust anchor, discover a DDT node's public key by either (1) having it configured
or by obtaining it from the node's parent as part of a signed Map- as a trust anchor or (2) obtaining it from the node's parent as part
Referral. When a public key is obtained from a node's parent, it is of a signed Map-Referral. When a public key is obtained from a
considered trusted if it is signed by a trust anchor, or if it is node's parent, it is considered trusted if it is signed by a trust
signed by a key that was previously trusted. Typically, in a Map anchor or if it is signed by a key that was previously trusted.
Resolver, the root DDT node public keys should be configured as trust Typically, in a Map-Resolver, the root DDT node's public keys should
anchors. Once a Map Resolver authenticates a public key it locally be configured as trust anchors. Once a Map-Resolver authenticates a
caches the key along with the associated DDT node RLOC and XEID- public key, it locally caches the key along with the associated DDT
prefix for future use. node RLOC and XEID-prefix for future use.
10.1. XEID-prefix Delegation 10.1. XEID-Prefix Delegation
In order to delegate XEID sub-prefixes to its children, a parent DDT In order to delegate XEID sub-prefixes to its child DDT nodes, a
node signs its Map-Referrals. Every signed Map-Referral MUST also parent DDT node signs its Map-Referrals. Every signed Map-Referral
include the public keys associated with each child DDT node. Such a MUST also include the public keys associated with each child DDT
signature indicates that the parent node is delegating the specified node. Such a signature indicates that the parent DDT node is
XEID-prefix to a given child DDT node. The signature is also delegating the specified XEID-prefix to a given child DDT node. The
authenticating the public keys associated with the children nodes, signature is also authenticating the public keys associated with the
and authorizing them to be used by the children DDT nodes to provide child DDT nodes, and authorizing them to be used by the child DDT
origin authentication and integrity protection for further nodes, to provide origin authentication and integrity protection for
delegations and mapping information of the XEID-prefix allocated to further delegations and mapping information of the XEID-prefix
the DDT node. allocated to the DDT node.
As a result, for a given XEID-prefix, a Map Resolver can form an As a result, for a given XEID-prefix, a Map-Resolver can form an
authentication chain from a configured trust anchor (typically the authentication chain from a configured trust anchor (typically the
root DDT node) to the leaf nodes (Map Servers). Map Resolvers root DDT node) to the leaf nodes (Map-Servers). Map-Resolvers
leverage this authentication chain to verify the Map-Referral leverage this authentication chain to verify the Map-Referral
signatures while walking the DDT tree until they reach a Map Server signatures while walking the DDT tree until they reach a Map-Server
authoritative for the given XEID-prefix. authoritative for the given XEID-prefix.
10.2. DDT node operation 10.2. DDT Node Operation
Upon receiving a Map-Request, the DDT node responds with a Map- Upon receiving a Map-Request, the DDT node responds with a
Referral as specified in Section 7. For every record present in the Map-Referral as specified in Section 7. For every Record present in
Map-Referral, the DDT node also includes the public keys associated the Map-Referral, the DDT node also includes the public keys
with the record's XEID-prefix and the RLOCs of the children DDT associated with the Record's XEID-prefix and the RLOCs of the child
nodes. Each record contained in the Map-Referral is signed using the DDT nodes. Each Record contained in the Map-Referral is signed using
DDT node's private key. the DDT node's private key.
10.2.1. DDT public key revocation 10.2.1. DDT Public Key Revocation
The node that owns a public key can also revoke that public key. For The node that owns a public key can also revoke that public key. For
instance if a parent node advertises a public key for one of its instance, if a parent DDT node advertises a public key for one of its
child DDT nodes, the child DDT node can at a later time revoke that child DDT nodes, the child DDT node can at a later time revoke that
key. Since DDT nodes do not keep track of the Map Resolvers that key. Since DDT nodes do not keep track of the Map-Resolvers that
query them, revocation is done in a pull model, where the Map query them, revocation is done in a pull model, where the
Resolver is informed of the revocation of a key only when it queries Map-Resolver is informed of the revocation of a key only when it
the node that owns that key. If the parent DDT is configured to queries the node that owns that key. If the parent DDT node is
advertise this key, the parent node must also be signaled to remove configured to advertise that key, the parent DDT node must also be
the key from the records it advertises for the child DDT node; this signaled to remove the key from the Records it advertises for the
is necessary to avoid further distribution of the revoked key. child DDT node; this is necessary to avoid further distribution of
the revoked key.
To securely revoke a key, the DDT node creates a new Record for the To securely revoke a key, the DDT node creates a new Record for the
associated XEID-prefix and locator, including the revoked key with associated XEID-prefix and locator, including the revoked key with
the R bit set. The DDT node must also include a signature in the the R bit set. (See Section 4.7 of [RFC8060] for details regarding
Record that covers this record; this is computed using the private the R bit.) The DDT node must also include a signature in the Record
key corresponding to the key being revoked. Such a record is termed that covers this Record; this is computed using the private key
a "revocation record". By including this record in its Map- corresponding to the key being revoked. Such a Record is termed a
Referrals, the DDT node informs querying Map Resolvers about the "revocation record". By including this Record in its Map-Referrals,
revoked key. A digital signature computed with a revoked key can the DDT node informs querying Map-Resolvers about the revoked key. A
only be used to authenticate the revocation, and SHOULD NOT be used digital signature computed with a revoked key can only be used to
to validate any data. To prevent a compromised key from revoking authenticate the revocation and SHOULD NOT be used to validate any
other valid keys, a given key can only be used to sign a revocation data. To prevent a compromised key from revoking other valid keys, a
for that specific key; it cannot be used to revoke other keys. This given key can only be used to sign a revocation for that specific
prevents the use of a compromised key to revoke other valid keys as key; it cannot be used to revoke other keys. This prevents the use
described in [RFC5011]. A revocation record MUST be advertised for a of a compromised key to revoke other valid keys as described in
period of time equal to or greater than the TTL value of the Record [RFC5011]. A revocation record MUST be advertised for a period of
that initially advertised the key, starting from the time that the time equal to or greater than the TTL value of the Record that
advertisement of the key was stopped by removal from the parent DDT initially advertised the key, starting from the time that the
node. advertisement of the key was stopped by removal from the parent
DDT node.
10.3. Map Server operation 10.3. Map-Server Operation
Similar to a DDT node, a Map Server is configured with one (or more) Similar to a DDT node, a Map-Server is configured with one or more
public/private key pairs that it must use to sign Map-Referrals. public/private key pairs that it must use to sign Map-Referrals.
However unlike DDT nodes, Map Servers do not delegate prefixes and as However, unlike DDT nodes, Map-Servers do not delegate prefixes and
a result they do not need to include keys in the Map-Referrals they as a result do not need to include keys in the Map-Referrals they
generate. generate.
10.4. Map Resolver operation 10.4. Map-Resolver Operation
Upon receiving a Map-Referral, the Map Resolver MUST first verify the Upon receiving a Map-Referral, the Map-Resolver MUST first verify the
signature(s) by using a trust anchor, or a previously authenticated signature(s) by using either a trust anchor or a previously
public key, associated with the DDT node sending the Map-Referral. authenticated public key associated with the DDT node sending the
If multiple authenticated keys are associated with the DDT node Map-Referral. If multiple authenticated keys are associated with the
sending this Map-Referral, the Key Tag field of the signature can be DDT node sending this Map-Referral, the Key Tag field (Section 6.4.1)
used to select the right public key for verifying the signature. If of the signature can be used to select the correct public key for
the key tag matches more than one key associated with that DDT node, verifying the signature. If the key tag matches more than one key
the Map Resolver MUST try verifying the signature with all matching associated with that DDT node, the Map-Resolver MUST try to verify
keys. For every matching key that is found the Map Resolver MUST the signature with all matching keys. For every matching key that is
also verify that the key is authoritative for the XEID-prefix in the found, the Map-Resolver MUST also verify that the key is
Map-Referral record. If such a key is found, the Map Resolver MUST authoritative for the XEID-prefix in the Map-Referral Record. If
use it to verify the associated signature in the record. If no such a key is found, the Map-Resolver MUST use it to verify the
matching key is found, or if none of the matching keys is associated signature in the Record. If (1) no matching key is found,
authoritative for the XEID-prefix in the Map-Referral record, or if (2) none of the matching keys is authoritative for the XEID-prefix in
such a key is found but the signature is not valid the Map-Referral the Map-Referral Record, or (3) such a key is found but the signature
record is considered corrupted and MUST be discarded. This may be is not valid, the Map-Referral Record is considered corrupted and
due to expired keys. The Map Resolver MAY try other siblings of this MUST be discarded. This may be due to expired keys. The
node if there is an alternative node authoritative for the same Map-Resolver MAY try other siblings of this node if there is an
prefix. If not, the Map Resolver CAN query the DDT node's parent to alternate node that is authoritative for the same prefix. If not,
retrieve a valid key. It is good practice to use a counter or timer the Map-Resolver CAN query the DDT node's parent to retrieve a valid
to avoid repeating this process if the resolver cannot verify the key. It is good practice to use a counter or timer to avoid
signature after several trials. repeating this process if the Map-Resolver cannot verify the
signature after several attempts.
Once the signature is verified, the Map Resolver has verified the Once the signature is verified, the Map-Resolver has verified the
XEID-prefix delegation in the Map-Referral, and authenticated the XEID-prefix delegation in the Map-Referral. This also means that
public keys of the children DDT nodes. The Map Resolver must add public keys of the child DDT nodes were authenticated; the
these keys to the authenticated keys associated with each child DDT Map-Resolver must add these keys to the authenticated keys associated
node and XEID-prefix. These keys are considered valid for the with each child DDT node and XEID-prefix. These keys are considered
duration specified in the record's TTL field. valid for the duration specified in the Record's TTL field.
11. Open Issues and Considerations 11. Open Issues and Considerations
There are a number of issues with the organization of the mapping There are a number of issues with the organization of the mapping
database that need further investigation. Among these are: database that need further investigation. Among these are:
o Defining an interface to implement interconnection and/or o Defining an interface to implement interconnection and/or
interoperability with other mapping databases, such as LISP+ALT. interoperability with other mapping databases, such as LISP+ALT.
o Additional key structures for use with LISP-DDT, such as to o Additional key structures for use with LISP-DDT, such as key
support additional EID formats as defined in [I-D.ietf-lisp-lcaf] structures to support additional EID formats as defined in
[RFC8060].
o Management of the DDT Map Resolver referral cache, in particular, o Management of the DDT Map-Resolver referral cache -- in
detecting and removing outdated entries. particular, detecting and removing outdated entries.
o Best practices for configuring hint referrals (or vice verse o Best practices for either configuring hint referrals or avoiding
avoiding using them). their use.
Operational experience will help answer open questions surrounding Operational experience will help answer open questions surrounding
these and other issues. these and other issues.
12. IANA Considerations 12. IANA Considerations
This document makes no request of the IANA. IANA has made the following early assignment per this document:
o Message type 6, "LISP DDT Map-Referral", was added to the
"LISP Packet Types" registry. See Section 6.4 ("Map-Referral
Message Format").
As this document is an Experimental RFC, this is an early allocation
as per [RFC7120].
13. Security Considerations 13. Security Considerations
Section 10 describes a DDT security architecture that provides data Section 10 describes a DDT security architecture that provides data
origin authentication, data integrity protection, and XEID-prefix origin authentication, data integrity protection, and XEID-prefix
delegation within the DDT Infrastructure. delegation within the DDT infrastructure.
Global XEID-prefix authorization is beyond the scope of this Global XEID-prefix authorization is beyond the scope of this
document, but the SIDR working group [RFC6480] is developing an document, but the Secure Inter-Domain Routing (SIDR) working group
infrastructure to support improved security of Internet routing. [RFC6480] is developing an infrastructure to support improved
Further work is required to determine if SIDR's public key security of Internet routing. Further work is required to determine
infrastructure (PKI) and the distributed repository system it uses if SIDR's Public Key Infrastructure (PKI) and the distributed
for storing and disseminating PKI data objects may also be used by repository system it uses for storing and disseminating PKI data
DDT devices to verifiably assert that they are the legitimate holders objects may also be used by DDT devices to verifiably assert that
of a set of XEID prefixes. they are the legitimate holders of a set of XEID-prefixes.
This document specifies how DDT security and LISP-SEC This document specifies how DDT security and LISP-SEC [LISP-SEC]
([I-D.ietf-lisp-sec]) complement one another to secure the DDT complement one another to secure the DDT infrastructure, Map-Referral
infrastructure, Map-Referral messages, and the Map-Request/Map-Reply messages, and the Map-Request/Map-Reply protocols. In the future,
protocols. In the future other LISP security mechanisms may be other LISP security mechanisms may be developed to replace LISP-SEC.
developed to replace LISP-SEC. Such future security mechanisms Such future security mechanisms should describe how they can be used
should describe how they can be used together with DDT to provide together with LISP-DDT to provide similar levels of protection.
similar levels of protection.
LISP-SEC can use the DDT public key infrastructure to secure the LISP-SEC can use the DDT public-key infrastructure to secure the
transport of LISP-SEC key material (the One-Time Key) from a Map- transport of LISP-SEC key material (the One-Time Key) from a
Resolver to the corresponding Map-Server. For this reason, when Map-Resolver to the corresponding Map-Server. For this reason, when
LISP-SEC is deployed in conjunction with a LISP-DDT mapping database LISP-SEC is deployed in conjunction with a LISP-DDT mapping database
and the path between Map-Resolver and Map-Server needs to be and the path between the Map-Resolver and Map-Server needs to be
protected, DDT security as described in Section 10 should be enabled protected, DDT security as described in Section 10 should be enabled
as well. as well.
14. References 14. References
14.1. Normative References 14.1. Normative References
[I-D.ietf-lisp-lcaf]
Farinacci, D., Meyer, D., and J. Snijders, "LISP Canonical
Address Format (LCAF)", draft-ietf-lisp-lcaf-22 (work in
progress), November 2016.
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119, Requirement Levels", BCP 14, RFC 2119,
DOI 10.17487/RFC2119, March 1997, DOI 10.17487/RFC2119, March 1997,
<http://www.rfc-editor.org/info/rfc2119>. <http://www.rfc-editor.org/info/rfc2119>.
[RFC3447] Jonsson, J. and B. Kaliski, "Public-Key Cryptography
Standards (PKCS) #1: RSA Cryptography Specifications
Version 2.1", RFC 3447, DOI 10.17487/RFC3447, February
2003, <http://www.rfc-editor.org/info/rfc3447>.
[RFC6830] Farinacci, D., Fuller, V., Meyer, D., and D. Lewis, "The [RFC6830] Farinacci, D., Fuller, V., Meyer, D., and D. Lewis, "The
Locator/ID Separation Protocol (LISP)", RFC 6830, Locator/ID Separation Protocol (LISP)", RFC 6830,
DOI 10.17487/RFC6830, January 2013, DOI 10.17487/RFC6830, January 2013,
<http://www.rfc-editor.org/info/rfc6830>. <http://www.rfc-editor.org/info/rfc6830>.
[RFC6833] Fuller, V. and D. Farinacci, "Locator/ID Separation [RFC6833] Fuller, V. and D. Farinacci, "Locator/ID Separation
Protocol (LISP) Map-Server Interface", RFC 6833, Protocol (LISP) Map-Server Interface", RFC 6833,
DOI 10.17487/RFC6833, January 2013, DOI 10.17487/RFC6833, January 2013,
<http://www.rfc-editor.org/info/rfc6833>. <http://www.rfc-editor.org/info/rfc6833>.
[RFC7120] Cotton, M., "Early IANA Allocation of Standards Track Code
Points", BCP 100, RFC 7120, DOI 10.17487/RFC7120,
January 2014, <http://www.rfc-editor.org/info/rfc7120>.
[RFC8017] Moriarty, K., Ed., Kaliski, B., Jonsson, J., and A. Rusch,
"PKCS #1: RSA Cryptography Specifications Version 2.2",
RFC 8017, DOI 10.17487/RFC8017, November 2016,
<http://www.rfc-editor.org/info/rfc8017>.
[RFC8060] Farinacci, D., Meyer, D., and J. Snijders, "LISP Canonical
Address Format (LCAF)", RFC 8060, DOI 10.17487/RFC8060,
February 2017, <http://www.rfc-editor.org/info/rfc8060>.
[RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in
RFC 2119 Key Words", BCP 14, RFC 8174,
DOI 10.17487/RFC8174, May 2017,
<http://www.rfc-editor.org/info/rfc8174>.
14.2. Informative References 14.2. Informative References
[AFI] "Address Family Identifier (AFIs)", IANA , Febuary 2007, [AFI] IANA, "Address Family Numbers",
<http://www.iana.org/assignments/address-family-numbers/ <http://www.iana.org/assignments/address-family-numbers/>.
address-family-numbers.xhtml>.
[I-D.ietf-lisp-sec] [LISP-SEC] Maino, F., Ermagan, V., Cabellos, A., and D. Saucez,
Maino, F., Ermagan, V., Cabellos-Aparicio, A., and D. "LISP-Security (LISP-SEC)", Work in Progress,
Saucez, "LISP-Security (LISP-SEC)", draft-ietf-lisp-sec-12 draft-ietf-lisp-sec-12, November 2016.
(work in progress), November 2016.
[LISP-TREE] [LISP-TREE]
Jakab, L., Cabellos-Aparicio, A., Coras, F., Saucez, D., Jakab, L., Cabellos-Aparicio, A., Coras, F., Saucez, D.,
and O. Bonaventure, "LISP-TREE: a DNS hierarchy to support and O. Bonaventure, "LISP-TREE: a DNS Hierarchy to Support
the lisp mapping system", Selected Areas in the LISP Mapping System", IEEE Journal on Selected Areas
Communications, IEEE Journal , 2010, in Communications, Volume 28, Issue 8,
DOI 10.1109/JSAC.2010.101011, September 2010,
<http://ieeexplore.ieee.org/xpls/ <http://ieeexplore.ieee.org/xpls/
abs_all.jsp?arnumber=5586446>. abs_all.jsp?arnumber=5586446>.
[RFC1918] Rekhter, Y., Moskowitz, B., Karrenberg, D., de Groot, G., [RFC1918] Rekhter, Y., Moskowitz, B., Karrenberg, D., de Groot, G.,
and E. Lear, "Address Allocation for Private Internets", and E. Lear, "Address Allocation for Private Internets",
BCP 5, RFC 1918, DOI 10.17487/RFC1918, February 1996, BCP 5, RFC 1918, DOI 10.17487/RFC1918, February 1996,
<http://www.rfc-editor.org/info/rfc1918>. <http://www.rfc-editor.org/info/rfc1918>.
[RFC5011] StJohns, M., "Automated Updates of DNS Security (DNSSEC) [RFC5011] StJohns, M., "Automated Updates of DNS Security (DNSSEC)
Trust Anchors", STD 74, RFC 5011, DOI 10.17487/RFC5011, Trust Anchors", STD 74, RFC 5011, DOI 10.17487/RFC5011,
skipping to change at page 39, line 36 skipping to change at page 44, line 5
[RFC6836] Fuller, V., Farinacci, D., Meyer, D., and D. Lewis, [RFC6836] Fuller, V., Farinacci, D., Meyer, D., and D. Lewis,
"Locator/ID Separation Protocol Alternative Logical "Locator/ID Separation Protocol Alternative Logical
Topology (LISP+ALT)", RFC 6836, DOI 10.17487/RFC6836, Topology (LISP+ALT)", RFC 6836, DOI 10.17487/RFC6836,
January 2013, <http://www.rfc-editor.org/info/rfc6836>. January 2013, <http://www.rfc-editor.org/info/rfc6836>.
[RFC6837] Lear, E., "NERD: A Not-so-novel Endpoint ID (EID) to [RFC6837] Lear, E., "NERD: A Not-so-novel Endpoint ID (EID) to
Routing Locator (RLOC) Database", RFC 6837, Routing Locator (RLOC) Database", RFC 6837,
DOI 10.17487/RFC6837, January 2013, DOI 10.17487/RFC6837, January 2013,
<http://www.rfc-editor.org/info/rfc6837>. <http://www.rfc-editor.org/info/rfc6837>.
Appendix A. Acknowledgments Acknowledgments
The authors would like to express their thanks to Lorand Jakab, The authors would like to express their thanks to Lorand Jakab,
Albert Cabellos-Asparicio, Florin Coras, Damien Saucez, and Olivier Albert Cabellos, Florin Coras, Damien Saucez, and Olivier Bonaventure
Bonaventure for their work on LISP-TREE [LISP-TREE] and LISP iterable for their work on LISP-TREE [LISP-TREE] and LISP iterable mappings
mappings that inspired the hierarchical database structure and lookup that inspired the hierarchical database structure and lookup
iteration approach described in this document. Thanks also go to iteration approach described in this document. Thanks also go to
Dino Farinacci and Isidor Kouvelas for their implementation work; to Dino Farinacci and Isidor Kouvelas for their implementation work; to
Selina Heimlich and Srin Subramanian for testing; to Fabio Maino for Selina Heimlich and Srin Subramanian for testing; to Fabio Maino for
work on security processing; and to Job Snijders, Glen Wiley, Neel work on security processing; and to Job Snijders, Glen Wiley, Neel
Goyal, and Mike Gibbs for work on operational considerations and Goyal, and Mike Gibbs for work on operational considerations and
initial deployment of a prototype database infrastructure. Special initial deployment of a prototype database infrastructure. Special
thanks go to Jesper Skriver, Andrew Partan, and Noel Chiappa; all of thanks go to Jesper Skriver, Andrew Partan, and Noel Chiappa, all of
whom have participated in (and put up with) seemingly endless hours whom have participated in (and put up with) seemingly endless hours
of discussion of mapping database ideas, concepts, and issues. of discussion of mapping database ideas, concepts, and issues.
Authors' Addresses Authors' Addresses
Vince Fuller Vince Fuller
VAF.NET Internet Consulting
Email: vaf@vaf.net Email: vince.fuller@gmail.com
Darrel Lewis Darrel Lewis
Cisco Systems Cisco Systems
Email: darlewis@cisco.com Email: darlewis@cisco.com
Vina Ermagan Vina Ermagan
Cisco Systems Cisco Systems
Email: vermagan@cisco.com Email: vermagan@cisco.com
 End of changes. 303 change blocks. 
954 lines changed or deleted 1020 lines changed or added

This html diff was produced by rfcdiff 1.45. The latest version is available from http://tools.ietf.org/tools/rfcdiff/