idnits 2.17.1 draft-ietf-lisp-ddt-09.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- No issues found here. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (January 18, 2017) is 2655 days in the past. Is this intentional? Checking references for intended status: Experimental ---------------------------------------------------------------------------- ** Obsolete normative reference: RFC 3447 (Obsoleted by RFC 8017) ** Obsolete normative reference: RFC 6830 (Obsoleted by RFC 9300, RFC 9301) ** Obsolete normative reference: RFC 6833 (Obsoleted by RFC 9301) == Outdated reference: A later version (-29) exists of draft-ietf-lisp-sec-12 Summary: 3 errors (**), 0 flaws (~~), 2 warnings (==), 1 comment (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group V. Fuller 3 Internet-Draft 4 Intended status: Experimental D. Lewis 5 Expires: July 22, 2017 V. Ermagan 6 Cisco Systems 7 A. Jain 8 Juniper Networks 9 A. Smirnov 10 Cisco Systems 11 January 18, 2017 13 LISP Delegated Database Tree 14 draft-ietf-lisp-ddt-09 16 Abstract 18 This document describes the LISP Delegated Database Tree (LISP-DDT), 19 a hierarchical, distributed database which embodies the delegation of 20 authority to provide mappings from LISP Endpoint Identifiers (EIDs) 21 to Routing Locators (RLOCs). It is a statically-defined distribution 22 of the EID namespace among a set of LISP-speaking servers, called DDT 23 nodes. Each DDT node is configured as "authoritative" for one or 24 more EID-prefixes, along with the set of RLOCs for Map Servers or 25 "child" DDT nodes to which more-specific EID-prefixes are delegated. 27 Status of This Memo 29 This Internet-Draft is submitted in full conformance with the 30 provisions of BCP 78 and BCP 79. 32 Internet-Drafts are working documents of the Internet Engineering 33 Task Force (IETF). Note that other groups may also distribute 34 working documents as Internet-Drafts. The list of current Internet- 35 Drafts is at http://datatracker.ietf.org/drafts/current/. 37 Internet-Drafts are draft documents valid for a maximum of six months 38 and may be updated, replaced, or obsoleted by other documents at any 39 time. It is inappropriate to use Internet-Drafts as reference 40 material or to cite them other than as "work in progress." 42 This Internet-Draft will expire on July 22, 2017. 44 Copyright Notice 46 Copyright (c) 2017 IETF Trust and the persons identified as the 47 document authors. All rights reserved. 49 This document is subject to BCP 78 and the IETF Trust's Legal 50 Provisions Relating to IETF Documents 51 (http://trustee.ietf.org/license-info) in effect on the date of 52 publication of this document. Please review these documents 53 carefully, as they describe your rights and restrictions with respect 54 to this document. Code Components extracted from this document must 55 include Simplified BSD License text as described in Section 4.e of 56 the Trust Legal Provisions and are provided without warranty as 57 described in the Simplified BSD License. 59 Table of Contents 61 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 62 2. Requirements Language . . . . . . . . . . . . . . . . . . . . 4 63 3. Definition of Terms . . . . . . . . . . . . . . . . . . . . . 5 64 4. Database organization . . . . . . . . . . . . . . . . . . . . 7 65 4.1. XEID prefixes . . . . . . . . . . . . . . . . . . . . . . 7 66 4.2. DDT database tree structure . . . . . . . . . . . . . . . 7 67 4.3. Configuring prefix delegation . . . . . . . . . . . . . . 8 68 4.3.1. The root DDT node . . . . . . . . . . . . . . . . . . 9 69 5. DDT Map-Request . . . . . . . . . . . . . . . . . . . . . . . 9 70 6. The Map-Referral message . . . . . . . . . . . . . . . . . . 10 71 6.1. Action codes . . . . . . . . . . . . . . . . . . . . . . 10 72 6.2. Referral set . . . . . . . . . . . . . . . . . . . . . . 11 73 6.3. Incomplete flag . . . . . . . . . . . . . . . . . . . . . 11 74 6.4. Map-Referral Message Format . . . . . . . . . . . . . . . 11 75 6.4.1. SIG section . . . . . . . . . . . . . . . . . . . . . 14 76 7. DDT network elements and their operation . . . . . . . . . . 15 77 7.1. DDT node . . . . . . . . . . . . . . . . . . . . . . . . 15 78 7.1.1. Match of a delegated prefix (or sub-prefix) . . . . . 15 79 7.1.2. Missing delegation from an authoritative prefix . . . 16 80 7.2. DDT Map Server . . . . . . . . . . . . . . . . . . . . . 16 81 7.3. DDT client . . . . . . . . . . . . . . . . . . . . . . . 17 82 7.3.1. Queuing and sending DDT Map-Requests . . . . . . . . 17 83 7.3.2. Receiving and following referrals . . . . . . . . . . 18 84 7.3.3. Handling referral errors . . . . . . . . . . . . . . 20 85 7.3.4. Referral loop detection . . . . . . . . . . . . . . . 20 86 8. Pseudo Code and Decision Tree diagrams . . . . . . . . . . . 21 87 8.1. Map Resolver processing of ITR Map-Request . . . . . . . 21 88 8.1.1. Pseudo-code summary . . . . . . . . . . . . . . . . . 21 89 8.1.2. Decision tree diagram . . . . . . . . . . . . . . . . 21 90 8.2. Map Resolver processing of Map-Referral message . . . . . 22 91 8.2.1. Pseudo-code summary . . . . . . . . . . . . . . . . . 22 92 8.2.2. Decision tree diagram . . . . . . . . . . . . . . . . 24 93 8.3. DDT Node processing of DDT Map-Request message . . . . . 25 94 8.3.1. Pseudo-code summary . . . . . . . . . . . . . . . . . 25 95 8.3.2. Decision tree diagram . . . . . . . . . . . . . . . . 27 96 9. Example topology and request/referral following . . . . . . . 27 97 9.1. Lookup of 2001:db8:0103:1::1/128 . . . . . . . . . . . . 30 98 9.2. Lookup of 2001:db8:0501:8:4::1/128 . . . . . . . . . . . 31 99 9.3. Lookup of 2001:db8:0104:2::2/128 . . . . . . . . . . . . 32 100 9.4. Lookup of 2001:db8:0500:2:4::1/128 . . . . . . . . . . . 32 101 9.5. Lookup of 2001:db8:0500::1/128 (non-existent EID) . . . . 33 102 10. Securing the database and message exchanges . . . . . . . . . 34 103 10.1. XEID-prefix Delegation . . . . . . . . . . . . . . . . . 34 104 10.2. DDT node operation . . . . . . . . . . . . . . . . . . . 35 105 10.2.1. DDT public key revocation . . . . . . . . . . . . . 35 106 10.3. Map Server operation . . . . . . . . . . . . . . . . . . 36 107 10.4. Map Resolver operation . . . . . . . . . . . . . . . . . 36 108 11. Open Issues and Considerations . . . . . . . . . . . . . . . 37 109 12. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 37 110 13. Security Considerations . . . . . . . . . . . . . . . . . . . 37 111 14. References . . . . . . . . . . . . . . . . . . . . . . . . . 38 112 14.1. Normative References . . . . . . . . . . . . . . . . . . 38 113 14.2. Informative References . . . . . . . . . . . . . . . . . 38 114 Appendix A. Acknowledgments . . . . . . . . . . . . . . . . . . 39 115 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 40 117 1. Introduction 119 LISP [RFC6830] specifies an architecture and mechanism for replacing 120 the addresses currently used by IP with two separate name spaces: 121 Endpoint Identifiers (EIDs), used end-to-end for terminating 122 transport-layer associations, and Routing Locators (RLOCs), which are 123 bound to topological location, and are used for routing and 124 forwarding through the Internet infrastructure. 126 [RFC6833] specifies an interface between database storing EID-to-RLOC 127 mappings and LISP devices which need this information for packet 128 forwarding. Internal organization of such database is out the scope 129 of [RFC6833]. Multiple architectures of the database have been 130 proposed, each having its advantages and disadvantages (see for 131 example [RFC6836] and [RFC6837]). 133 This document specifies architecture for database of LISP EID-to-RLOC 134 mappings with emphasis on high scalability. LISP-DDT is a 135 hierarchical distributed database, which embodies the delegation of 136 authority to provide mappings, i.e. its internal structure mirrors 137 the hierarchical delegation of address space. It also provides 138 delegation information to Map Resolvers, which use the information to 139 locate EID-to-RLOC mappings. A Map Resolver, which needs to locate a 140 given mapping, will follow a path through the tree-structured 141 database, contacting, one after another, the DDT nodes along that 142 path until it reaches the leaf DDT node(s) authoritative for the 143 mapping it is seeking. 145 LISP offers a general-purpose mechanism for mapping between EIDs and 146 RLOCs. In organizing a database of EID to RLOC mappings, this 147 specification extends the definition of the EID numbering space by 148 logically prepending and appending several fields for purposes of 149 defining the database index key: Database-ID (DBID, 16 bits), 150 Instance identifier (IID, 32-bits), Address Family Identifier (16 151 bits), and EID-prefix (variable, according to AFI value). The 152 resulting concatenation of these fields is termed an "Extended EID 153 prefix" or XEID-prefix. 155 LISP-DDT defines a new device type, the DDT node, that is configured 156 as authoritative for one or more XEID-prefixes. It also is 157 configured with the set of more-specific sub-prefixes that are 158 further delegated to other DDT nodes. To delegate a sub-prefix, the 159 "parent" DDT node is configured with the RLOCs of each child DDT node 160 that is authoritative for the sub-prefix. Each RLOC either points to 161 a DDT Map Server to which an Egress Tunnel Router (ETR) has 162 registered that sub-prefix or points to another DDT node in the 163 database tree that further delegates the sub-prefix. See [RFC6833] 164 for a description of the functionality of the Map Server and Map 165 Resolver. Note that the target of a delegation must always be an 166 RLOC (not an EID) to avoid any circular dependency. 168 To provide a mechanism for traversing the database tree, LISP-DDT 169 defines a new LISP message type, the Map-Referral, which is returned 170 to the sender of a Map-Request when the receiving DDT node can refer 171 the sender to another DDT node that has more detailed information. 172 See Section 6 for the definition of the Map-Referral message. 174 To find an EID-to-RLOC mapping, a LISP-DDT client, usually a DDT Map 175 Resolver, starts by sending an Encapsulated Map-Request to a 176 preconfigured DDT node RLOC. The DDT node responds with a Map- 177 Referral message that either indicates that it will find the 178 requested mapping to complete processing of the request or that the 179 DDT client should contact another DDT node that has more-specific 180 information; in the latter case, the DDT node then sends a new 181 Encapsulated Map-Request to the next DDT node and the process repeats 182 in an iterative manner. 184 Conceptually, this is similar to the way that a client of the Domain 185 Name System (DNS) follows referrals (DNS responses that contain only 186 NS records) from a series of DNS servers until it finds an answer. 188 2. Requirements Language 190 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 191 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 192 document are to be interpreted as described in [RFC2119]. 194 3. Definition of Terms 196 Extended EID (XEID): a LISP EID extended with data uniquely 197 identifying address space to which it belongs, such as LISP 198 instance ID, Address Family etc. See Section 4.1 for detailed 199 description of XEID data. 201 XEID-prefix: Extended EID-prefix (XEID-prefix) is a LISP EID-prefix 202 prepended with XEID data. An XEID-prefix is used as a key index 203 into the DDT database. XEID prefixes are used to describe 204 database organization and are not seen as a single entity in 205 protocol messages, though messages contain individual fields 206 constituting XEID prefix. 208 DDT node: a network infrastructure component responsible for 209 specific XEID-prefix(es) and for delegation of more-specific sub- 210 prefixes to other DDT nodes. 212 DDT client: a network infrastructure component that sends DDT Map- 213 Request messages and implements the iterative following of Map- 214 Referral results. Typically, a DDT client will be a Map Resolver 215 (as defined by [RFC6833]), but it is also possible for an ITR to 216 implement DDT client functionality. 218 DDT Map Server: a DDT node that also implements Map Server 219 functionality (forwarding Map-Requests and/or returning Map- 220 Replies if offering proxy Map-Reply service) for a subset of its 221 delegated prefixes. Map Server functions including proxying Map- 222 Replies are described in [RFC6833]. 224 DDT Map Server peers: list of all DDT Map Servers performing Map 225 Server functionality for the same prefix. If peers are configured 226 on a DDT Map Server then the latter will provide complete 227 information about the prefix in its Map-Replies; otherwise the Map 228 Server will mark returned reply as potentially incomplete. 230 DDT Map Resolver: a network infrastructure element which implements 231 both the DDT client functionality and Map Resolver functionality 232 as defined by [RFC6833]. DDT Map Resolver accepts Map-Requests 233 from ITRs, sends DDT Map-Requests to DDT nodes and implements 234 iterative following of Map-Referrals. Note that Map Resolvers do 235 not respond to clients which sent Map-Requests, they only ensure 236 that the Map-Request has been forwarded to a LISP device (ETR or 237 proxy Map-Server) which will provide authoritative response to the 238 original requestor. A DDT Map Resolver will typically maintain a 239 cache of previously received Map-Referral message results 240 containing RLOCs for DDT nodes responsible for XEID- prefixes of 241 interest (termed the "referral cache"). 243 Encapsulated Map-Request: a LISP Map-Request carried within an 244 Encapsulated Control Message, which has an additional LISP header 245 prepended. Sent to UDP destination port 4342. The "outer" 246 addresses are globally-routable IP addresses, also known as RLOCs. 247 Used by an ITR when sending to a Map Resolver and by a Map Server 248 when forwarding a Map-Request to an ETR as documented in LISP-MS 249 [RFC6833]. 251 DDT Map-Request: an Encapsulated Map-Request sent by a DDT client to 252 a DDT node. The "DDT-originated" flag is set in the encapsulation 253 header indicating that the DDT node should return Map-Referral 254 messages if the Map-Request EID matches a delegated XEID-prefix 255 known to the DDT node. Section 7.3.1 describes how DDT Map- 256 Requests are sent. Section 5 defines position of the "DDT- 257 originated" flag in the Encapsulated Control Message header. 259 Authoritative XEID-prefix: an XEID-prefix delegated to a DDT node 260 and for which the DDT node may provide further delegations of 261 more-specific sub-prefixes. 263 Map-Referral: a LISP message sent by a DDT node in response to a DDT 264 Map-Request for an XEID that matches a configured XEID-prefix 265 delegation. A non-negative Map-Referral includes a "referral", a 266 set of RLOCs for DDT nodes that have information about the more 267 specific XEID prefix covering requested XEID; a DDT client 268 "follows the referral" by sending another DDT Map-Request to one 269 of those RLOCs to obtain either an answer or another referral to 270 DDT nodes responsible for even more specific XEID-prefix. See 271 Section 7.1 and Section 7.3.2 for details on the sending and 272 processing of Map-Referral messages. 274 Negative Map-Referral: an answer from an authoritative DDT node that 275 there is no mapping for the requested XEID. Negative Map-Referral 276 is a Map-Referral sent in response to a DDT Map-Request that 277 matches an authoritative XEID-prefix but for which there is no 278 delegation configured (or no ETR registration if sent by a DDT 279 Map-Server). 281 Pending Request List: the set of outstanding requests for which a 282 DDT Map Resolver has received encapsulated Map-Requests from its 283 clients seeking EID-to-RLOC mapping for a XEID. Each entry in the 284 list contains additional state needed by the referral following 285 process, including the XEID, requestor(s) of the XEID (typically, 286 one or more ITRs), saved information about the last referral 287 received and followed (matching XEID-prefix, action code, RLOC 288 set, index of last RLOC queried in the RLOC set), and any LISP-SEC 289 information ([I-D.ietf-lisp-sec]) that was included in the DDT 290 client Map-Request. An entry in the list may be interchangeably 291 termed a "pending request list entry" or simply a "pending 292 request". 294 For definitions of other terms, notably Map-Request, Map-Reply, 295 Ingress Tunnel Router (ITR), Egress Tunnel Router (ETR), Map Server, 296 and Map Resolver, please consult the LISP specification [RFC6830] and 297 the LISP Mapping Service specification [RFC6833]. 299 4. Database organization 301 4.1. XEID prefixes 303 DDT database is indexed by Extended EID-prefixes (XEID-prefixes). 304 XEID-prefix is LISP EID-prefix together with data extending it to 305 uniquely identify address space of the prefix. XEID-prefix is 306 composed as binary encoding of five fields, in order of significance: 307 DBID (16 bits), Instance Identifier (IID, 32 bits), Address Family 308 Identifier (AFI, 16 bits), and EID-prefix (variable, according to AFI 309 value). The fields are concatenated, with the most significant 310 fields as listed above. 312 DBID is LISP-DDT database ID, a 16-bit field provided to allow the 313 definition of multiple databases. In this version of DDT DBID MUST 314 always be set to zero. Other values of DBID are reserved for future 315 use. 317 Instance ID (IID) is 32-bit value describing context of EID prefix if 318 the latter is intended for use in an environment where addresses may 319 not be unique, such as on a Virtual Private Network where [RFC1918] 320 address space is used. See "Using Virtualization and Segmentation 321 with LISP" in [RFC6830] for more discussion of Instance IDs. 322 Encoding of the instance ID (IID) is specified by 323 [I-D.ietf-lisp-lcaf]. 325 Address Family Identifier (AFI) is a 16-bit value defining syntax of 326 EID-prefix. AFI values are assigned by IANA ([AFI]. 328 4.2. DDT database tree structure 330 LISP-DDT database of each DDT node is organised as a tree structure 331 that is indexed by XEID prefixes. Leaves of the database tree 332 describe delegation of authority between DDT nodes (see more on 333 delegation and information kept in the database entries in 334 Section 4.3). 336 DDT Map-Requests sent by the DDT client to DDT nodes always contain 337 specific values for DBID, IID and AFI; never a range or unspecified 338 value for any of these fields. Thus XEID prefix used as key for 339 search in the database tree will have length of at least 64 bits. 341 DDT node may, for example, be authoritative for a consecutive range 342 of 3-tuples (DBID, IID, AFI) and all associated EID prefixes; or only 343 for a specific EID prefix of a single 3-tuple. Thus XEID prefixes/ 344 keys of the database tree leaves may have length less, equal or more 345 than 64 bits. 347 It is important to note that LISP-DDT does not store actual EID-to- 348 RLOC mappings; it is, rather, a distributed index that can be used to 349 find the devices (ETRs which registered their EIDs with DDT Map 350 Servers) that can be queried with LISP to obtain those mappings. 351 Changes to EID-to-RLOC mappings are made on the ETRs which define 352 them, not to any DDT node configuration. DDT node configuration 353 changes are only required when branches of the database hierarchy are 354 added, removed, or modified. 356 4.3. Configuring prefix delegation 358 Every DDT node is configured with one or more XEID-prefixes for which 359 it is authoritative along with a list of delegations of XEID-prefixes 360 to other DDT nodes. A DDT node is required to maintain a list of 361 delegations for all sub-prefixes of its authoritative XEID-prefixes; 362 it also may list "hints", which are prefixes that it knows about that 363 belong to its parents, to the root, or to any other point in the 364 XEID-prefix hierarchy. A delegation (or hint) consists of an XEID- 365 prefix, a set of RLOCs for DDT nodes that have more detailed 366 knowledge of the XEID-prefix, and accompanying security information 367 (for details of security infomation exchange and its use see 368 Section 10). Those RLOCs are returned in Map-Referral messages when 369 the DDT node receives a DDT Map-Request with an XEID that matches a 370 delegation. A DDT Map Server will also have a set of sub-prefixes 371 for which it accepts ETR mapping registrations and for which it will 372 forward (or answer, if it provides proxy Map-Reply service) Map- 373 Requests. 375 XEID prefix (or prefixes) for which DDT node is authoritative and 376 delegation of authority for sub-prefixes is provided as configuration 377 of the DDT node. Implementations will likely develop a language to 378 express this prefix authority and delegation. Since DDT 379 configuration is static (i.e. not exchanged between DDT nodes as part 380 of the protocol itself) such language is implementation-dependant and 381 is outside the scope of this specification. 383 4.3.1. The root DDT node 385 The root DDT node is the logical "top" of the distributed database 386 hierarchy. It is authoritative for all XEID prefixes, that is for 387 all valid 3-tuples (DBID, IID, AFI) and their EID prefixes. A DDT 388 Map-Request that matches no configured XEID-prefix will be referred 389 to the root node (see Section 8 for formal description of conditions 390 when DDT Request is forwarded to the root node). The root node in a 391 particular instantiation of LISP-DDT therefore MUST be configured 392 with delegations for at least all defined IIDs and AFIs. 394 5. DDT Map-Request 396 A DDT client (usualy a Map Resolver) uses LISP Encapsulated Control 397 Message (ECM) to send Map-Request to a DDT node. Format of the ECM 398 is defined by [RFC6830]. This specification adds to ECM flag "DDT- 399 originated". 401 0 1 2 3 402 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 403 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 404 / | IPv4 or IPv6 Header | 405 OH | (uses RLOC addresses) | 406 \ | | 407 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 408 / | Source Port = xxxx | Dest Port = 4342 | 409 UDP +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 410 \ | UDP Length | UDP Checksum | 411 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 412 LH |Type=8 |S|D| Reserved | 413 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 414 / | IPv4 or IPv6 Header | 415 IH | (uses RLOC or EID addresses) | 416 \ | | 417 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 418 / | Source Port = xxxx | Dest Port = yyyy | 419 UDP +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 420 \ | UDP Length | UDP Checksum | 421 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 422 LCM | LISP Control Message | 423 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 425 D: The "DDT-originated" flag. It is set by a DDT client to indicate 426 that the receiver SHOULD return Map-Referral messages as 427 appropriate. Use of the flag is further described in 428 Section 7.3.1. This bit is allocated from LISP message header 429 bits marked as Reserved in [RFC6830]. 431 6. The Map-Referral message 433 This specification defines a new LISP message, the Map-Referral. It 434 is sent by a DDT node to a DDT client in response to a DDT Map- 435 Request message. See Section 6.4 for a detailed layout of the Map- 436 Referral message fields. 438 The message consists of an action code along with delegation 439 information about the XEID-prefix that matches the requested XEID. 441 6.1. Action codes 443 The action codes are as follows: 445 NODE-REFERRAL (0): indicates that the replying DDT node has 446 delegated an XEID-prefix that matches the requested XEID to one or 447 more other DDT nodes. The Map-Referral message contains a "map- 448 record" with additional information, most significantly the set of 449 RLOCs to which the prefix has been delegated, that is used by a 450 DDT client to "follow" the referral. 452 MS-REFERRAL (1): indicates that the replying DDT node has delegated 453 an XEID-prefix that matches the requested XEID to one or more DDT 454 Map Servers. It contains the same additional information as a 455 NODE-REFERRAL, but is handled slightly differently by the 456 receiving DDT client (see Section 7.3.2). 458 MS-ACK (2): indicates that the replying DDT Map Server received a 459 DDT Map-Request that matches an authoritative XEID-prefix for 460 which it has one or more registered ETRs. This means that the 461 request has been forwarded to one of those ETRs to provide an 462 answer to the querying ITR. 464 MS-NOT-REGISTERED (3): indicates that the replying DDT Map Server 465 received a Map-Request for one of its configured XEID-prefixes 466 which has no ETRs registered. 468 DELEGATION-HOLE (4): indicates that the requested XEID matches a 469 non-delegated sub-prefix of the XEID space. This is a non-LISP 470 "hole", which has not been delegated to any DDT Map Server or ETR. 471 See Section 7.1.2 for details. Also sent by a DDT Map Server with 472 authoritative configuration covering the requested EID, but for 473 which no specific site ETR is configured. 475 NOT-AUTHORITATIVE (5): indicates that the replying DDT node received 476 a Map-Request for an XEID for which it is not authoritative and 477 has no configured matching hint referrals. This can occur if a 478 cached referral has become invalid due to a change in the database 479 hierarchy. However, if such a DDT node has a "hint" delegation 480 covering the requested EID, it MAY choose to return NODE-REFERRAL 481 or MS-REFERRAL as appropriate. When returning action code NOT- 482 AUTHORITATIVE DDT node MUST provide EID-prefix received in the 483 request and the TTL MUST be set to 0. 485 6.2. Referral set 487 For "positive" action codes (NODE-REFERRAL, MS-REFERRAL, MS-ACK), a 488 DDT node MUST include in the Map-Referral message a list of RLOCs for 489 DDT nodes that are authoritative for the XEID-prefix being returned; 490 a DDT client uses this information to contact one of those DDT nodes 491 as it "follows" a referral. 493 6.3. Incomplete flag 495 A DDT node sets the "Incomplete" flag in a Map-Referral message if 496 the Referral Set is incomplete; this is intended to prevent a DDT 497 client from caching a referral with incomplete information. A DDT 498 node MUST set the "incomplete" flag in the following cases: 500 o If it is setting action code MS-ACK or MS-NOT-REGISTERED but the 501 matching XEID-prefix is not flagged in configuration as 502 "complete". XEID-prefix configuration on DDT Mapping Server 503 SHOULD be marked as "complete" when configuration of the XEID- 504 prefix lists all "peer" DDT nodes that are also authoritative for 505 the same XEID-prefix or when it is known that local DDT node is 506 the only one authoritative for the XEID-prefix. 508 o If it is setting action code NOT-AUTHORITATIVE. 510 6.4. Map-Referral Message Format 511 0 1 2 3 512 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 513 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 514 |Type=6 | Reserved | Record Count | 515 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 516 | Nonce . . . | 517 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 518 | . . . Nonce | 519 +-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 520 | | Record TTL | 521 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 522 R | Referral Count| EID mask-len | ACT |A|I| Reserved | 523 e +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 524 c |SigCnt | Map Version Number | EID-AFI | 525 o +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 526 r | EID-prefix ... | 527 d +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 528 | /| Priority | Weight | M Priority | M Weight | 529 | R +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 530 | e | Unused Flags |L|p|R| Loc-AFI | 531 | f +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 532 | \| Locator ... | 533 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 534 | ~ Sig section ~ 535 +-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 537 Type: Type value 6 was reserved for future use in RFC6830, this 538 document allocates this value to identify Map-Referral messages. 540 ACT: The "action" field of the mapping record in a Map-Referral 541 message encodes one of the 6 action types: NODE-REFERRAL, MS- 542 REFERRAL, MS-ACK, MS-NOT-REGISTERED, DELEGATION-HOLE, NOT- 543 AUTHORITATIVE. See Section 6.1 for description of their meaning. 545 Incomplete: The "I" bit indicates that a DDT node's referral-set of 546 locators is incomplete and the receiver of this message SHOULD NOT 547 cache the referral. A DDT sets the "incomplete" flag, the TTL, and 548 the Action Type field as follows: 550 ------------------------------------------------------------------- 551 Type (Action field) Incomplete Referral-set TTL values 552 ------------------------------------------------------------------- 553 0 NODE-REFERRAL NO YES 1440 555 1 MS-REFERRAL NO YES 1440 557 2 MS-ACK * * 1440 559 3 MS-NOT-REGISTERED * * 1 561 4 DELEGATION-HOLE NO NO 15 563 5 NOT-AUTHORITATIVE YES NO 0 564 ------------------------------------------------------------------- 566 *: The "Incomplete" flag setting on Map Server originated referral of 567 MS-ACK and MS-NOT-REGISTERED types depend on whether the Map 568 Server has the full peer Map Server configuration for the same 569 prefix and has encoded the information in the mapping record. 570 Incomplete bit is not set when the Map Server has encoded the 571 information, which means the referral-set includes all the RLOCs 572 of all Map Servers that serve the prefix. It MUST be set when 573 configuration of the Map Server does not flag matching prefix as 574 configured with the complete information about "peer" Map Servers 575 or when the Map Server does not return all configured locators. 577 Referral Count: number of RLOCs in the current Referral set, it is 578 equal to the number of Ref sections in the message. 580 SigCnt: Indicates the number of signatures (sig section) present in 581 the Record. If SigCnt is larger than 0, the signature information 582 captured in a sig section as described in Section 6.4.1 will be 583 appended to the end of the record. The number of sig sections at the 584 end of the Record MUST match the SigCnt. Note that bits occupied by 585 SigCnt were Reserved in Records embedded into messages defined by 586 [RFC6830] and were required to be set to zero. 588 Loc-AFI: AFI of the Locator field. If AFI value is different from 589 LCAF AFI, security keys are not included in the record. If AFI is 590 equal to the LCAF AFI, the contents of the LCAF depend on the Type 591 field of the LCAF. LCAF Type 11 is used to store security material 592 along with the AFI of the locator. DDT nodes and DDT Map Servers can 593 use this LCAF Type to include public keys associated with their Child 594 DDT nodes for a XEID-prefix referral record. LCAF types and formats 595 are defined in [I-D.ietf-lisp-lcaf]. 597 Locator: RLOC of a DDT node the DDT client is being referred to. 598 Lenght of this variable-length field is determined by the Loc-AFI. 600 All other fields and their descriptions are equivalent to those in 601 the Map-Reply message, as defined in LISP [RFC6830]. Note, though, 602 that the set of RLOCs correspond to the DDT node to be queried as a 603 result of the referral not the RLOCs for an actual EID-to-RLOC 604 mapping. 606 6.4.1. SIG section 608 SigCnt counts the number of signature sections that appear at the end 609 of the Record. Format of the signature section is described below. 611 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 612 /| Original Record TTL | 613 / +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 614 / | Signature Expiration | 615 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 616 s | Signature Inception | 617 i +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 618 g | Key Tag | Sig Length | 619 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 620 \ | Sig-Algorithm | Reserved | Reserved | 621 \ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 622 \ ~ Signature ~ 623 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 625 Original Record TTL: The original Record TTL for this record that is 626 covered by the signature. Record TTL is in minutes. 628 Signature Expiration and Inception: Specify the validity period for 629 the signature. The signature MUST NOT be used for authentication 630 prior to the inception date and MUST NOT be used for authentication 631 after the expiration date. Each field specifies a date and time in 632 the form of a 32-bit unsigned number of seconds elapsed since 1 633 January 1970 00:00:00 UTC, ignoring leap seconds, in network byte 634 order. 636 Key Tag: An identifier to specify which key is used for this 637 signature if more than one valid key exists for the signing DDT node. 639 Sig Length: The length of the Signature field in bytes. 641 Sig-Algorithm: The identifier of the cryptographic algorithm used for 642 the signature. Sig-Algorithm values defined in this specification 643 are listed in Table 1. Implementation conforming to this 644 specification MUST implement at least RSA-SHA256 for DDT signing. 645 Sig-Algorithm type 1 RSA-SHA1 is deprecated and SHOULD NOT be used. 647 +---------------+------------+-----------+------------+ 648 | Sig-Algorithm | Name | Reference | Notes | 649 +---------------+------------+-----------+------------+ 650 | 1 | RSA-SHA1 | [RFC3447] | DEPRECATED | 651 | | | | | 652 | 2 | RSA-SHA256 | [RFC3447] | MANDATORY | 653 +---------------+------------+-----------+------------+ 655 Table 1: Sig-Algorithm Values 657 Reserved: This field MUST be set to 0 on transmit and MUST be ignored 658 on receipt. 660 Signature: Contains the cryptographic signature that covers the 661 entire referral record that this signature belongs to. The Record 662 TTL is set to Original Record TTL and the sig fields are Signature 663 field is set to zero for the purpose of computing the Signature. 665 7. DDT network elements and their operation 667 As described above, DDT introduces a new network element, the "DDT 668 node", extends the functionality of Map Servers and Map Resolvers to 669 send and receive Map-Referral messages. The operation of each of 670 these devices is described as follows. 672 7.1. DDT node 674 When a DDT node receives a DDT Map-Request, it compares the requested 675 XEID against its list of XEID-prefix delegations and its list of 676 authoritative XEID-prefixes and acts as follows: 678 7.1.1. Match of a delegated prefix (or sub-prefix) 680 If the requested XEID matches one of the DDT node's delegated 681 prefixes, then a Map-Referral message is returned with the matching 682 more-specific XEID-prefix and the set of RLOCs for the referral 683 target DDT nodes including associated security information (see 684 Section 10 for details on security). If at least one DDT node of the 685 delegation is known to be a DDT Map Server, then the Map-Referral 686 message SHOULD be sent with action code MS-REFERRAL to indicate to 687 the receiver that LISP-SEC information (if saved in the pending 688 request) SHOULD be included in the next DDT Map-Request; otherwise, 689 the action code NODE-REFERRAL SHOULD be used. 691 Note that a matched delegation does not have to be for a sub-prefix 692 of an authoritative prefix; in addition to being configured to 693 delegate sub-prefixes of an authoritative prefix, a DDT node may also 694 be configured with other XEID-prefixes for which it can provide 695 referrals to DDT nodes anywhere in the database hierarchy. This 696 capability to define "shortcut hints" is never required to be 697 configured, but may be a useful heuristic for reducing the number of 698 iterations needed to find an EID, particular for private network 699 deployments. 701 Referral hints, if used properly, may reduce number of referrals a 702 DDT client needs to follow to locate DDT Map Server authoritative for 703 XEID prefix being resolved. On the other hand, incorrect use of 704 hints may create circular dependencies between DDT nodes (or 705 "referral loops"). DDT client MUST be prepared to handle such 706 circular referrals. See Section 7.3.4 for discussion of referral 707 loops and measures DDT client must implement in order to detect 708 circular referrals and prevent infinite looping. 710 Another danger with use of hints is when DDT deployment spans 711 multiple administrative domains (i.e. different authorities manage 712 DDT nodes in the same DDT database). In this case operator managing 713 a DDT node may not be aware of the fact that the node is being 714 referred to by hints. Locator addresses in hints may become stale 715 when referred DDT nodes are taken out of service or change their 716 locator addresses. 718 7.1.2. Missing delegation from an authoritative prefix 720 If the requested XEID did not match a configured delegation but does 721 match an authoritative XEID-prefix, then the DDT node MUST return a 722 negative Map-Referral that uses the least-specific XEID-prefix that 723 does not match any XEID-prefix delegated by the DDT node. The action 724 code is set to DELEGATION-HOLE; this indicates that the XEID is not a 725 LISP destination. 727 If the requested XEID did not match either a configured delegation, 728 an authoritative XEID-prefix or a "hint", then negative Map-Referral 729 with action code NOT-AUTHORITATIVE MUST be returned. 731 7.2. DDT Map Server 733 When a DDT Map Server receives a DDT Map-Request, its operation is 734 similar to that of a DDT node with additional processing as follows: 736 o If the requested XEID matches a registered XEID-prefix, then the 737 Map-Request is forwarded to one of the destination ETR RLOCs (or 738 the Map Server sends a Map-Reply, if it is providing proxy Map- 739 Reply service) and a Map-Referral with the MS-ACK action MUST be 740 returned to the sender of the DDT Map-Request. 742 o If the requested XEID matches a configured XEID-prefix for which 743 no ETR registration has been received then a negative Map-Referral 744 with action code MS-NOT-REGISTERED MUST be returned to the sender 745 of the DDT Map-Request. 747 7.3. DDT client 749 A DDT client queries one or more DDT nodes and uses an iterative 750 process of following returned referrals until it receives one with 751 action code MS-ACK (or an error indication). MS-ACK indicates that 752 the Map-Request has been sent to a Map Server that will forward it to 753 an ETR that, in turn, will provide a Map-Reply to the locator address 754 in the Map-Request. 756 DDT client functionality will typically be implemented by DDT Map 757 Resolvers. Just as any other Map Resolver, a DDT Map Resolver 758 accepts Map-Requests from its clients (typically, ITRs) and ensures 759 that those Map-Requests are forwarded to the correct ETR, which 760 generates Map-Replies. Unlike a Map Resolver that uses the ALT 761 mapping system (see [RFC6836]), however, a DDT Map Resolver 762 implements a DDT client functionality to find the correct ETR to 763 answer a Map-Request; this requires a DDT Map Resolver to maintain 764 additional state: a Map-Referral cache and pending request list of 765 XEIDs that are going through the iterative referral process. 767 DDT client functionality may be implemented on ITRs. In this case 768 the DDT client will not receive Map-Request from another network 769 element; instead, equivalent information will be provided to the DDT 770 client by the means of programming interface. 772 7.3.1. Queuing and sending DDT Map-Requests 774 When a DDT client receives a request to resolve XEID (in case of DDT 775 Map Resolver this will be in the form of received encapsulated Map- 776 Request), it first performs a longest-match search for the XEID in 777 its referral cache. If no match is found or if a negative cache 778 entry is found, then the destination is not in the database; a 779 negative Map-Reply MUST be returned and no further processing is 780 performed by the DDT client. 782 If a match is found, the DDT client creates a pending request list 783 entry for the XEID and saves the original request (in case of DDT 784 Map-Resolved, original Map-Request minus the encapsulation header) 785 along with other information needed to track progress through the 786 iterative referral process; the "referral XEID-prefix" is also 787 initialized to indicate that no referral has yet been received. The 788 DDT client then creates a DDT Map-Request (which is an encapsulated 789 Map-Request with the "DDT-originated" flag set in the message header) 790 for the XEID but without any authentication data that may have been 791 included in the original request. It sends the DDT Map-Request to 792 one of the RLOCs in the chosen referral cache entry. The referral 793 cache is initially populated with one or more statically-configured 794 entries; additional entries are added when referrals are followed, as 795 described below. A DDT client is not absolutely required to cache 796 referrals, but it doing so decreases latency and reduces lookup 797 delays. 799 Note that in normal use on the public Internet, the statically- 800 configured initial referral cache for a DDT client should include a 801 "default" entry with RLOCs for either the DDT root node or one or 802 more DDT nodes that contain hints for the DDT root node. If a DDT 803 client does not have such configuration, it will return a Negative 804 Map-Reply if it receives a query for an EID outside the subset of the 805 mapping database known to it. While this may be desirable on private 806 network deployments or during early transition to LISP when few sites 807 are using it, this behavior is not appropriate when LISP is in 808 general use on the Internet. If DDT message exchange is 809 authenticated as described in Section 10 then DDT client MUST also be 810 configured with public keys of DDT nodes pointed to by the "default" 811 cache entry. In this case the "default" entry will typically be for 812 the DDT root node. 814 7.3.2. Receiving and following referrals 816 After sending a DDT Map-Request, a DDT client expects to receive a 817 Map-Referral response. If none occurs within the timeout period, the 818 DDT client retransmits the request, sending to the next RLOC in the 819 referral cache entry if one is available. If all RLOCs have been 820 tried and the maximum number of retransmissions has occurred for 821 each, then the pending request list entry is dequeued and discarded. 822 In this case DDT client returns no response to sender of the original 823 request. 825 A DDT client processes a received Map-Referral message according to 826 each action code: 828 NODE-REFERRAL: The DDT client checks for a possible referral loop as 829 as described in Section 7.3.4. If no loop is found, the DDT 830 client saves the prefix returned in the Map-Referral message in 831 the referral cache, updates the saved prefix and saved RLOCs in 832 the pending request list entry, and follows the referral by 833 sending a new DDT Map-Request to one of the DDT node RLOCs listed 834 in the Referral Set; security information saved with the original 835 Map-Request SHOULD NOT be included. 837 MS-REFERRAL: The DDT client processes an MS-REFERRAL in the same 838 manner as a NODE-REFERRAL except that security information saved 839 with the original Map-Request MUST be included in the new Map- 840 Request sent to a Map Server (see Section 10 for details on 841 security). 843 MS-ACK: This is returned by a DDT Map Server to indicate that it has 844 one or more registered ETRs that can answer a Map-Request for the 845 XEID and the request has been forwarded to one of them (or if the 846 Map Server is doing proxy service for the prefix then reply has 847 been sent to the querying ITR). If the pending request did not 848 include saved LISP-SEC information or if that information was 849 already included in the previous DDT Map-Request (sent by the DDT 850 client in response to either an MS-REFERRAL or a previous MS-ACK 851 referral), then the pending request for the XEID is complete; 852 processing of the request stops and all request state can be 853 discarded. Otherwise, LISP-SEC information is required and has 854 not yet been sent to the authoritative DDT Map-Server; the DDT 855 client MUST re-send the DDT Map-Request with LISP-SEC information 856 included and the pending request queue entry remains until another 857 Map-Referral with MS-ACK action code is received. If the 858 "incomplete" flag is not set, the prefix is saved in the referral 859 cache. 861 MS-NOT-REGISTERED: The DDT Map Server queried could not process the 862 request because it did not have any ETRs registered for a 863 matching, authoritative XEID-prefix. If the DDT client has not 864 yet tried all of the RLOCs saved with the pending request, then it 865 sends a Map-Request to the next RLOC in that list. If all RLOCs 866 have been tried, then the destination XEID is not registered and 867 is unreachable. The DDT client MUST return a negative Map-Reply 868 to the requester (in case of DDT Map Resolver to the sender of 869 original Map-Request); this Map-Reply contains the least-specific 870 XEID-prefix in the range for which this DDT Map Server is 871 autoritative and no registrations exist and whose TTL value SHOULD 872 be set to one minute. A negative referral cache entry is created 873 for the prefix (whose TTL also SHOULD be set to one minute) and 874 processing of the request stops. 876 DELEGATION-HOLE: The DDT Map Server queried did not have an XEID- 877 prefix defined that matched the requested XEID so it does not 878 exist in the mapping database. The DDT client MUST return a 879 negative Map-Reply to the requester (in case of DDT Map Resolver 880 to the sender of original Map-Request); this Map-Reply SHOULD 881 indicate the least-specific XEID-prefix matching the requested 882 XEID for which no delegations exist and SHOULD have a TTL value of 883 15 minutes. A negative referral cache entry is created for the 884 prefix (which also SHOULD have TTL of 15 minutes) and processing 885 of the pending request stops. 887 NOT-AUTHORITATIVE: The DDT Map Server queried is not authoritative 888 for the requested XEID. This can occur if a cached referral has 889 become invalid due to a change in the database hierarchy. If the 890 DDT client receiving this message can determine that it is using 891 old cached information, it MAY choose to delete that cached 892 information and re-try the original Map-Request, starting from its 893 "root" cache entry. If this action code is received in response 894 to a query that did not use a cached referral information, then it 895 indicates a database synchronization problem or configuration 896 error. The pending request is silently discarded, i.e. all state 897 for the request that caused this answer is removed and no answer 898 is returned to the original requestor. 900 7.3.3. Handling referral errors 902 Other states are possible, such as a misconfigured DDT node (acting 903 as a proxy Map Server, for example) returning a Map-Reply to the DDT 904 client; they should be considered errors and logged as such. It is 905 not clear exactly what else the DDT client should do in such cases; 906 one possibility is to remove the pending request list entry and send 907 a negative Map-Reply to the requester (in case of DDT Map Resolver to 908 the sender of original Map-Request). Alternatively, if a DDT client 909 detects unexpected behavior by a DDT node, it could mark that node as 910 unusable in its referral cache and update the pending request to try 911 a different DDT node if more than one is listed in the referral 912 cache. In any case, any prefix contained in a Map-Referral message 913 that causes a referral error (including a referral loop) is not saved 914 in the DDT client referral cache. 916 7.3.4. Referral loop detection 918 In response to a Map-Referral message with action code NODE-REFERRAL 919 or MS-REFERRAL, a DDT client is directed to query a new set of DDT 920 node RLOCs that are expected to have more-specific XEID-prefix 921 information for the requested XEID. To prevent a possible "iteration 922 loop" (following referrals back-and-forth among a set of DDT nodes 923 without ever finding an answer), a DDT client saves the last received 924 referral XEID-prefix for each pending request and checks that a newly 925 received NODE-REFERRAL or MS-REFERRAL message contains a more- 926 specific referral XEID-prefix; an exact or less-specific match of the 927 saved XEID-prefix indicates a referral loop. If a loop is detected, 928 the DDT Map Resolver handles the request as described in 929 Section 7.3.3. Otherwise, the DDT client saves the most recently 930 received referral XEID-prefix with the pending request when it 931 follows the referral. 933 As an extra measure to prevent referral loops, it is probably also 934 wise to limit the total number of referrals for any request to some 935 reasonable number; the exact value of that number will be determined 936 during experimental deployment of LISP-DDT, but is bounded by the 937 maximum length of the XEID. 939 Note that when a DDT client adds an entry to its lookup queue and 940 sends an initial Map-Request for an XEID, the queue entry has no 941 previous referral XEID-prefix; this means that the first DDT node 942 contacted by a DDT Map Resolver may provide a referral to anywhere in 943 the DDT hierarchy. This, in turn, allows a DDT client to use 944 essentially any DDT node RLOCs for its initial cache entries and 945 depend on the initial referral to provide a good starting point for 946 Map-Requests; there is no need to configure the same set of root DDT 947 nodes on all DDT clients. 949 8. Pseudo Code and Decision Tree diagrams 951 To illustrate DDT algorithms described above and to aid in 952 implementation, each of the major DDT Map Server and DDT Map Resolver 953 functions are described below, first using simple "psuedo-code" and 954 then in the form of a decision tree. 956 8.1. Map Resolver processing of ITR Map-Request 958 8.1.1. Pseudo-code summary 960 if ( request pending i.e., (ITR,EID) of request same ) { 961 replace old request with new & use new request nonce 962 for future requests 963 } else if ( no match in refcache ) { 964 return negative map-reply to ITR 965 } else if ( match type delegation hole ) { 966 return negative map-reply to ITR 967 } else if ( match type ms-ack ) { 968 fwd DDT request to map-server 969 } else { 970 store & fwd DDT request w/o security material to node delegation 971 } 973 8.1.2. Decision tree diagram 974 +------------+ 975 | Is Request | Yes 976 | |----> Replace old request with 977 | Pending? | new nonce for future requests 978 +------------+ 979 | 980 |No 981 | 982 V 983 +------------+ 984 | Match In | No 985 | Referral |----> Send Negative Map-Reply 986 | cache? | (not a likely event as root or 987 +------------+ hint configured on every MR) 988 | 989 |Yes 990 | 991 V 992 +------------+ 993 | Match Type | Yes 994 | Delegation |----> Send Negative Map-Reply 995 | Hole? | 996 +------------+ 997 | 998 |No 999 | 1000 V 1001 +------------+ 1002 | Match Type | Yes 1003 | MS-ACK? |----> Forward DDT Map-request to Map-Server 1004 | | 1005 +------------+ 1006 | 1007 |No 1008 | 1009 V 1010 Store request & Fwd DDT Request w/o security material 1011 to DDT node delegation 1013 8.2. Map Resolver processing of Map-Referral message 1015 8.2.1. Pseudo-code summary 1017 if ( authentication signature validation failed ) { 1018 silently drop 1019 } 1021 if ( no request pending matched by referral nonce ) { 1022 silently drop 1023 } 1025 if ( pfx in referral less specific than last referral used ) { 1026 if ( gone through root ) { 1027 silently drop 1028 } else { 1029 send request to root 1030 } 1031 } 1033 switch (map_referral_type) { 1035 case NOT_AUTHORITATIVE : 1036 if ( gone through root ) { 1037 return negative map-reply to ITR 1038 } else { 1039 send request to root 1040 } 1042 case DELEGATION_HOLE: 1043 cache & send negative map-reply to ITR 1045 case MS_REFERRAL: 1046 if ( referral equal to last used ) { 1047 if ( gone through root ) { 1048 return negative map-reply to ITR 1049 } else { 1050 send request to root 1051 } 1052 } else { 1053 cache 1054 follow the referral, include security material 1055 } 1057 case NODE_REFERRAL: 1058 if ( referral equal to last used ) { 1059 if ( gone through root ) { 1060 return negative map-reply to ITR 1061 } else { 1062 send request to root 1063 } 1064 } else { 1065 cache 1066 follow the referral, strip security material 1067 } 1069 case MS_ACK: 1071 if ( security material stripped ) { 1072 resend request with security material 1073 if { !incomplete } { 1074 cache 1075 } 1076 } 1078 case MS_NOT_REGISTERED: 1079 if { all map-server delegations not tried } { 1080 follow delegations not tried 1081 if ( !incomplete ) { 1082 cache 1083 } 1084 } else { 1085 send negative map-reply to ITR 1086 if { !incomplete } { 1087 cache 1088 } 1089 } 1091 case DEFAULT: 1092 drop 1093 } 1094 } 1096 8.2.2. Decision tree diagram 1098 +----------------+ 1099 | Auth Signature | No 1100 | Valid? |----> Silently drop 1101 +----------------+ 1102 | Yes 1103 V 1104 +------------+ 1105 | Is Request | No 1106 | Pending? |----> Silently drop 1107 +------------+ 1108 | Yes 1109 V 1110 +------------------------------+ Yes 1111 | Pfx less specific than last? |----> Silently drop 1112 +------------------------------+ 1113 |No 1114 V 1115 +---------------------------------------------------+ 1116 | What is Map-Referral Type? |--UNKNOWN-+ 1117 +---------------------------------------------------+ | 1118 | | | | | | V 1119 | | | | | DEL_HOLE DROP 1120 | | | | MS_ACK | 1121 | | | | | V 1122 | | MS_REF NODE_REF | Cache & return 1123 | | | | V negative map-reply 1124 | | | | +---------+ 1125 | NOT_AUTH | | | Was sec | Yes 1126 | | | | | material| 1127 | | | | |Stripped?|----> Done 1128 | | V V +---------+ 1129 | | +------------+ | No 1130 | | Yes | Pfx equal | V 1131 MS_NOT_REGISTERED | +---| to last | +------------+ 1132 | | | | used? | | Incomplete | Yes 1133 | | | +------------+ | bit set? |---> Resend DDT 1134 | V V |No +------------+ request w 1135 | +------------+ | |No security 1136 | | Gone | V | material 1137 | | Through | Cache & follow V 1138 | | Root? | the referral Cache & resend DDT 1139 | +------------+ request with 1140 | |No |Yes security material 1141 | | | 1142 | V V 1143 | Send req Send negative map-reply 1144 | to root 1145 V 1146 +-----------+ Yes +-----------+ Yes 1147 | Other MS |----Follow other MS-------->|Incomplete |----> Don't cache 1148 | not tried?| |bit set? | 1149 | |---Send negative map-reply->| |----> Cache 1150 +-----------+ No +-----------+ No 1152 8.3. DDT Node processing of DDT Map-Request message 1154 8.3.1. Pseudo-code summary 1155 if ( I am not authoritative ) { 1156 send map-referral NOT_AUTHORITATIVE with 1157 incomplete bit set and ttl 0 1158 } else if ( delegation exists ) { 1159 if ( delegated map-servers ) { 1160 send map-referral MS_REFERRAL with 1161 ttl 'Default_DdtNode_Ttl' 1162 } else { 1163 send map-referral NODE_REFERRAL with 1164 ttl 'Default_DdtNode_Ttl' 1165 } 1166 } else { 1167 if ( eid in site) { 1168 if ( site registered ) { 1169 forward map-request to etr 1170 if ( map-server peers configured ) { 1171 send map-referral MS_ACK with 1172 ttl 'Default_Registered_Ttl' 1173 } else { 1174 send map-referral MS_ACK with 1175 ttl 'Default_Registered_Ttl' and incomplete bit set 1176 } 1177 } else { 1178 if ( map-server peers configured ) { 1179 send map-referral MS_NOT_REGISTERED with 1180 ttl 'Default_Configured_Not_Registered_Ttl' 1181 } else { 1182 send map-referral MS_NOT_REGISTERED with 1183 ttl 'Default_Configured_Not_Registered_Ttl' 1184 and incomplete bit set 1185 } 1186 } 1187 } else { 1188 send map-referral DELEGATION_HOLE with 1189 ttl 'Default_Negative_Referral_Ttl' 1190 } 1191 } 1193 where architectural constants for TTL are set as follows: 1195 Default_DdtNode_Ttl 1440 minutes 1196 Default_Registered_Ttl 1440 minutes 1197 Default_Negative_Referral_Ttl 15 minutes 1198 Default_Configured_Not_Registered_Ttl 1 minute 1200 8.3.2. Decision tree diagram 1202 +------------+ 1203 | Am I | No 1204 | Authori- |----> Return NOT_AUTHORITATIVE 1205 | tative? | Incomplete = 1 1206 +------------+ ttl = Default_DdtNode_Ttl 1207 | 1208 |Yes 1209 | 1210 V 1211 +------------+ +------------+ 1212 | Delegation | Yes | Delegations| Yes 1213 | Exists? |---->| are map |----> Return MS_REFERRAL 1214 | | | servers? | ttl = Default_DdtNode_Ttl 1215 +------------+ +------------+ 1216 | \ No 1217 |No +--> Return NODE_REFERRAL 1218 | ttl = Default_DdtNode_Ttl 1219 V 1220 +------------+ +------------+ +------------+ 1221 | EID in | Yes | Site | Yes | Map-server | 1222 | Site |---->| Registered?|----> Forward---->| peers | 1223 | Config? | | | Map-request | configured?| 1224 +------------+ +------------+ to ETR +------------+ 1225 | | | | 1226 | |No No| |Yes 1227 | | | | 1228 | | V V 1229 | | Return MS_ACK Return MS_ACK 1230 | V with INC=1 1231 | +------------+ ttl=Default_Registered_Ttl 1232 | | Map-server | Yes 1233 | | peers |----> Return MS_NOT_REGISTERED 1234 | | configured?| ttl = Default_Negative_Referral_Ttl 1235 | +------------+ 1236 | \ No 1237 |No +--> Return MS_NOT_REGISTERED 1238 | Incomplete = 1 1239 V ttl = Default_Negative_Referral_Ttl 1240 Return DELEGATION_HOLE 1241 ttl = Default_Negative_Referral_Ttl 1243 9. Example topology and request/referral following 1245 This chapter shows example DDT tree and several possible scenarios of 1246 Map-Requests coming to a Map Resolver and subsequent iterative DDT 1247 referrals. For the sake of example RLOCs of DDT nodes are shown in 1248 IPv4 address space while the EIDs are in IPv6 AF. The same principle 1249 of hierarchical delegation and pinpointing referrals is equally 1250 applicable to any AF whose address hierarchy can be expressed as a 1251 bitstring with associated length. DDT tree of IPv4 prefixes is 1252 another AF with immediate practical value. 1254 To show how referrals are followed to find the RLOCs for a number of 1255 EIDs, consider the following example EID topology for DBID=0, IID=0, 1256 AFI=2, and EID=0/0 1257 +---------------------+ +---------------------+ 1258 | root1: 192.0.2.1 | | root2: 192.0.2.2 | 1259 | authoritative: ::/0 | | authoritative: ::/0 | 1260 +---------------------+ +---------------------+ 1261 | \ / | 1262 | \ / | 1263 | X | 1264 | / \ | 1265 | / \ | 1266 | | | | 1267 V V V V 1268 +-------------------------+ +--------------------------+ 1269 | DDT node1: 192.0.2.11 | | DDT node2: 192.0.2.12 | 1270 | authoritative: | | authoritative: | 1271 | 2001:db8::/32 | | 2001:db8::/32 | 1272 +-------------------------+ +--------------------------+ 1273 | \ / | 1274 | \ / | 1275 | X | 1276 | / \ | 1277 | / \ | 1278 | | | | 1279 V V V V 1280 +--------------------------+ +---------------------------+ 1281 | Map-Server1: 192.0.2.101 | | DDT node3: 192.0.2.201 | 1282 | authoritative: | | authoritative: | 1283 | 2001:db8:0100::/40 | | 2001:db8:0500::/40 | 1284 | site1: 2001:db8:0103::/48| +---------------------------+ 1285 | site2: 2001:db8:0104::/48| | | 1286 +--------------------------+ | | 1287 | | 1288 | | 1289 V V 1290 +---------------------------+ +---------------------------+ 1291 | Map-Server2: 192.0.2.211 | | Map-Server3: 192.0.2.221 | 1292 | authoritative: | | authoritative: | 1293 | 2001:db8:0500::/48 | | 2001:db8:0501::/48 | 1294 |site3: 2001:db8:0500:1::/64| |site5: 2001:db8:0501:8::/64| 1295 |site4: 2001:db8:0500:2::/64| |site6: 2001:db8:0501:9::/64| 1296 +---------------------------+ +---------------------------+ 1298 DDT nodes are configured for this "root" at IP addresses 192.0.2.1 1299 and 192.0.2.2. DDT Map Resolvers are configured with default 1300 referral cache entries to these addresses. 1302 The root DDT nodes delegate 2001:db8::/32 to two DDT nodes with IP 1303 addresses 192.0.2.11 and 192.0.2.12. 1305 The DDT nodes for 2001:db8::/32 delegate 2001:db8:0100::/40 to a DDT 1306 Map Server with RLOC 192.0.2.101 1308 The DDT Map Server for 2001:db8:0100::/40 is configured to allow ETRs 1309 to register the sub-prefixes 2001:db8:0103::/48 and 1310 2001:db8:0104::/48 1312 The DDT nodes for 2001:db8::/32 also delegate 2001:db8:0500::/40 to a 1313 DDT node with RLOC 192.0.2.201 1315 The DDT node for 2001:db8:0500::/40 is further configured to delegate 1316 2001:db8:0500::/48 to a DDT Map Server with RLOC 192.0.2.211 and 1317 2001:db8:0501::/48 to a DDT Map Server with RLOC 192.0.2.221 1319 The DDT Map Server for 2001:db8:0500::/48 is configured to allow ETRs 1320 to register the sub-prefixes 2001:db8:0500:1::/64 and 1321 2001:db8:0500:2::/64 1323 The DDT Map Server for 2001:db8:0501::/48 is configured to allow ETRs 1324 to register the sub-prefixes 2001:db8:0501:8::/64 and 1325 2001:db8:0501:9::/64 1327 9.1. Lookup of 2001:db8:0103:1::1/128 1329 The first example shows a DDT Map Resolver following a delegation 1330 from the root to a DDT node followed by another delegation to a DDT 1331 Map Server. 1333 ITR1 sends an Encapsulated Map-Request for 2001:db8:0103:1::1 to one 1334 of its configured (DDT) Map Resolvers. The DDT Map Resolver proceeds 1335 as follows: 1337 1. Send DDT Map-Request (for 2001:db8:0103:1::1) to one of the root 1338 DDT nodes, 192.0.2.1 or 192.0.2.2 1340 2. Receive (and save in referral cache) Map-Referral for EID-prefix 1341 2001:db8::/32, action code NODE-REFERRAL, RLOC set (192.0.2.11, 1342 192.0.2.12) 1344 3. Send DDT Map-Request to 192.0.2.11 or 192.0.2.12 1346 4. Receive (and save in referral cache) Map-Referral for EID-prefix 1347 2001:db8:0100::/40, action code MS-REFERRAL, RLOC set 1348 (192.0.2.101) 1350 5. Send DDT Map-Request to 192.0.2.101; if the ITR-originated 1351 Encapsulated Map-Request had a LISP-SEC signature, it is included 1353 6. DDT Map Server at 192.0.2.101 decapsulates the DDT Map-Request 1354 and forwards to a registered site1 ETR for 2001:db8:0103::/48 1356 7. DDT Map Server at 192.0.2.101 sends a Map-Referral message for 1357 EID-prefix 2001:db8:0103::/48, action code MS-ACK to the DDT Map 1358 Resolver 1360 8. DDT Map Resolver receives Map-Referral message and dequeues the 1361 pending request for 2001:db8:0103:1::1 1363 9. site1 ETR for 2001:db8:0103::/48 receives Map-Request forwarded 1364 by DDT Map Server and sends Map-Reply to ITR1 1366 9.2. Lookup of 2001:db8:0501:8:4::1/128 1368 The next example shows a three-level delegation: root to first DDT 1369 node, first DDT node to second DDT node, second DDT node to DDT Map 1370 Server. 1372 ITR2 sends an Encapsulated Map-Request for 2001:db8:0501:8:4::1 to 1373 one of its configured (DDT) Map Resolvers, which are different from 1374 those for ITR1. The DDT Map Resolver proceeds as follows: 1376 1. Send DDT Map-Request (for 2001:db8:0501:8:4::1) to one of the 1377 root DDT nodes, 192.0.2.1 or 192.0.2.2 1379 2. Receive (and save in referral cache) Map-Referral for EID-prefix 1380 2001:db8::/32, action code NODE-REFERRAL, RLOC set (192.0.2.11, 1381 192.0.2.12) 1383 3. Send DDT Map-Request to 192.0.2.11 or 192.0.2.12 1385 4. Receive (and save in referral cache) Map-Referral for EID-prefix 1386 2001:db8:0500::/40, action code NODE-REFERRAL, RLOC set 1387 (192.0.2.201) 1389 5. Send DDT Map-Request to 192.0.2.201 1391 6. Receive (and save in referral cache) Map-Referral for EID-prefix 1392 2001:db8:0501::/48, action code MS-REFERRAL, RLOC set 1393 (192.0.2.221) 1395 7. Send DDT Map-Request to 192.0.2.221; if the ITR-originated 1396 Encapsulated Map-Request had a LISP-SEC signature, it is 1397 included 1399 8. DDT Map Server at 192.0.2.221 decapsulates the DDT Map-Request 1400 and forwards to a registered site5 ETR for 2001:db8:0501:8::/64 1402 9. DDT Map Server at 192.0.2.221 sends a Map-Referral message for 1403 EID-prefix 2001:db8:0501:8::/64, action code MS-ACK, to the DDT 1404 Map Resolver 1406 10. DDT Map Resolver receives Map-Referral(MS-ACK) message and 1407 dequeues the pending request for 2001:db8:0501:8:4::1 1409 11. site5 ETR for 2001:db8:0501:8::/64 receives Map-Request 1410 forwarded by DDT Map Server and sends Map-Reply to ITR2 1412 9.3. Lookup of 2001:db8:0104:2::2/128 1414 This example shows how a DDT Map Resolver uses a saved referral cache 1415 entry to skip the referral process and go directly to a DDT Map 1416 Server for a prefix that is similar to one previously requested. 1418 In this case, ITR1 uses the same Map Resolver used in example 1419 Section 9.1. It sends an Encapsulated Map-Request for 1420 2001:db8:0104:2::2 to that (DDT) Map Resolver. The DDT Map-Resolver 1421 finds an MS-REFERRAL cache entry for 2001:db8:0100::/40 with RLOC set 1422 (192.0.2.101) and proceeds as follows: 1424 1. Send DDT Map-Request (for 2001:db8:0104:2::2) to 192.0.2.101; if 1425 the ITR-originated Encapsulated Map-Request had a LISP-SEC 1426 signature, it is included 1428 2. DDT Map Server at 192.0.2.101 decapsulates the DDT Map-Request 1429 and forwards to a registered site2 ETR for 2001:db8:0104::/48 1431 3. DDT Map Server at 192.0.2.101 sends a Map-Referral message for 1432 EID-prefix 2001:db8:0104::/48, action code MS-ACK to the DDT Map 1433 Resolver 1435 4. DDT Map Resolver receives Map-Referral(MS-ACK) and dequeues the 1436 pending request for 2001:db8:0104:2::2 1438 5. site2 ETR for 2001:db8:0104::/48 receives Map-Request and sends 1439 Map-Reply to ITR1 1441 9.4. Lookup of 2001:db8:0500:2:4::1/128 1443 This example shows how a DDT Map Resolver uses a saved referral cache 1444 entry to start the referral process at a non-root, intermediate DDT 1445 node for a prefix that is similar to one previously requested. 1447 In this case, ITR2 asks the same Map Resolver used in example 1448 Section 9.2. It sends an Encapsulated Map-Request for 1449 2001:db8:0500:2:4::1 to that (DDT) Map Resolver, which finds a NODE- 1450 REFERRAL cache entry for 2001:db8:0500::/40 with RLOC set 1451 (192.0.2.201). It proceeds as follows: 1453 1. Send DDT Map-Request (for 2001:db8:0500:2:4::1) to 192.0.2.201 1455 2. Receive (and save in referral cache) Map-Referral for EID-prefix 1456 2001:db8:0500::/48, action code MS-REFERRAL, RLOC set 1457 (192.0.2.211) 1459 3. Send DDT Map-Request to 192.0.2.211; if the ITR-originated 1460 Encapsulated Map-Request had a LISP-SEC signature, it is included 1462 4. DDT Map Server at 192.0.2.211 decapsulates the DDT Map-Request 1463 and forwards to a registered site4 ETR for 2001:db8:0500:2::/64 1465 5. DDT Map Server at 192.0.2.211 sends a Map-Referral message for 1466 EID-prefix 2001:db8:0500:2::/64, action code MS-ACK to the DDT 1467 Map Resolver 1469 6. DDT Map Resolver receives Map-Referral(MS-ACK) and dequeues the 1470 pending request for 2001:db8:0500:2:4::1 1472 7. site4 ETR for 2001:db8:0500:2::/64 receives Map-Request and sends 1473 Map-Reply to ITR2 1475 9.5. Lookup of 2001:db8:0500::1/128 (non-existent EID) 1477 This example uses the cached MS-REFERRAL for 2001:db8:0500::/48 1478 learned above to start the lookup process at the DDT Map-Server at 1479 192.0.2.211. The DDT Map Resolver proceeds as follows: 1481 1. Send DDT Map-Request (for 2001:db8:0500::1) to 192.0.2.211; if 1482 the ITR-originated Encapsulated Map-Request had a LISP-SEC 1483 signature, it is included 1485 2. DDT Map Server at 192.0.2.211, which is authoritative for 1486 2001:db8:0500::/48, does not have a matching delegation for 1487 2001:db8:0500::1. It responds with a Map-Referral message for 1488 2001:db8:0500::/64, action code DELEGATION-HOLE to the DDT Map 1489 Resolver. The prefix 2001:db8:0500::/64 is used because it is 1490 the least-specific prefix that does match the requested EID, but 1491 does not match one of configured delegations 1492 (2001:db8:0500:1::/64 and 2001:db8:0500:2::/64). 1494 3. DDT Map Resolver receives the delegation, adds a negative 1495 referral cache entry for 2001:db8:0500::/64, dequeues the pending 1496 request for 2001:db8:0500::1, and returns a negative Map-Reply to 1497 ITR2. 1499 10. Securing the database and message exchanges 1501 This section specifies the DDT security architecture that provides 1502 data origin authentication, data integrity protection, and XEID- 1503 prefix delegation. Global XEID-prefix authorization is out of the 1504 scope of this document. 1506 Each DDT node is configured with one or more public/private key 1507 pair(s) that are used to digitally sign referral records for XEID- 1508 prefix(es) that the DDT node is authoritative for. In other words, 1509 each public/private key pair is associated with the combination of a 1510 DDT node and a XEID-prefix that it is authoritative for. Every DDT 1511 node is also configured with the public keys of its children DDT 1512 nodes. By including public keys of target child DDT nodes in the 1513 Map-Referral records, and signing each record with the DDT node's 1514 private key, a DDT node can securely delegate sub-prefixes of its 1515 authoritative XEID-prefixes to its children DDT nodes. A DDT node 1516 configured to provide hints must also have the public keys of the DDT 1517 nodes that its hints point to. DDT node keys can be encoded using 1518 LCAF type 11 to associate the key to the RLOC of the referred DDT 1519 node. If a node has more than one public key, it should sign its 1520 records with at least one of these keys. When a node has N keys, it 1521 can sustain up to N-1 key compromises. Revocation mechanism is 1522 described in Section 10.2.1. 1524 Map Resolvers are configured with one or more trusted public keys 1525 referred to as trust anchors. Trust anchors are used to authenticate 1526 the DDT security infrastructure. Map Resolvers can discover a DDT 1527 node's public key either by having it configured as a trust anchor, 1528 or by obtaining it from the node's parent as part of a signed Map- 1529 Referral. When a public key is obtained from a node's parent, it is 1530 considered trusted if it is signed by a trust anchor, or if it is 1531 signed by a key that was previously trusted. Typically, in a Map 1532 Resolver, the root DDT node public keys should be configured as trust 1533 anchors. Once a Map Resolver authenticates a public key it locally 1534 caches the key along with the associated DDT node RLOC and XEID- 1535 prefix for future use. 1537 10.1. XEID-prefix Delegation 1539 In order to delegate XEID sub-prefixes to its children, a parent DDT 1540 node signs its Map-Referrals. Every signed Map-Referral MUST also 1541 include the public keys associated with each child DDT node. Such a 1542 signature indicates that the parent node is delegating the specified 1543 XEID-prefix to a given child DDT node. The signature is also 1544 authenticating the public keys associated with the children nodes, 1545 and authorizing them to be used by the children DDT nodes to provide 1546 origin authentication and integrity protection for further 1547 delegations and mapping information of the XEID-prefix allocated to 1548 the DDT node. 1550 As a result, for a given XEID-prefix, a Map Resolver can form an 1551 authentication chain from a configured trust anchor (typically the 1552 root DDT node) to the leaf nodes (Map Servers). Map Resolvers 1553 leverage this authentication chain to verify the Map-Referral 1554 signatures while walking the DDT tree until they reach a Map Server 1555 authoritative for the given XEID-prefix. 1557 10.2. DDT node operation 1559 Upon receiving a Map-Request, the DDT node responds with a Map- 1560 Referral as specified in Section 7. For every record present in the 1561 Map-Referral, the DDT node also includes the public keys associated 1562 with the record's XEID-prefix and the RLOCs of the children DDT 1563 nodes. Each record contained in the Map-Referral is signed using the 1564 DDT node's private key. 1566 10.2.1. DDT public key revocation 1568 The node that owns a public key can also revoke that public key. For 1569 instance if a parent node advertises a public key for one of its 1570 child DDT nodes, the child DDT node can at a later time revoke that 1571 key. Since DDT nodes do not keep track of the Map Resolvers that 1572 query them, revocation is done in a pull model, where the Map 1573 Resolver is informed of the revocation of a key only when it queries 1574 the node that owns that key. If the parent DDT is configured to 1575 advertise this key, the parent node must also be signaled to remove 1576 the key from the records it advertises for the child DDT node; this 1577 is necessary to avoid further distribution of the revoked key. 1579 To securely revoke a key, the DDT node creates a new Record for the 1580 associated XEID-prefix and locator, including the revoked key with 1581 the R bit set. The DDT node must also include a signature in the 1582 Record that covers this record; this is computed using the private 1583 key corresponding to the key being revoked. Such a record is termed 1584 a "revocation record". By including this record in its Map- 1585 Referrals, the DDT node informs querying Map Resolvers about the 1586 revoked key. A digital signature computed with a revoked key can 1587 only be used to authenticate the revocation, and SHOULD NOT be used 1588 to validate any data. To prevent a compromised key from revoking 1589 other valid keys, a given key can only be used to sign a revocation 1590 for that specific key; it cannot be used to revoke other keys. This 1591 prevents the use of a compromised key to revoke other valid keys as 1592 described in [RFC5011]. A revocation record MUST be advertised for a 1593 period of time equal to or greater than the TTL value of the Record 1594 that initially advertised the key, starting from the time that the 1595 advertisement of the key was stopped by removal from the parent DDT 1596 node. 1598 10.3. Map Server operation 1600 Similar to a DDT node, a Map Server is configured with one (or more) 1601 public/private key pairs that it must use to sign Map-Referrals. 1603 However unlike DDT nodes, Map Servers do not delegate prefixes and as 1604 a result they do not need to include keys in the Map-Referrals they 1605 generate. 1607 10.4. Map Resolver operation 1609 Upon receiving a Map-Referral, the Map Resolver MUST first verify the 1610 signature(s) by using a trust anchor, or a previously authenticated 1611 public key, associated with the DDT node sending the Map-Referral. 1612 If multiple authenticated keys are associated with the DDT node 1613 sending this Map-Referral, the Key Tag field of the signature can be 1614 used to select the right public key for verifying the signature. If 1615 the key tag matches more than one key associated with that DDT node, 1616 the Map Resolver MUST try verifying the signature with all matching 1617 keys. For every matching key that is found the Map Resolver MUST 1618 also verify that the key is authoritative for the XEID-prefix in the 1619 Map-Referral record. If such a key is found, the Map Resolver MUST 1620 use it to verify the associated signature in the record. If no 1621 matching key is found, or if none of the matching keys is 1622 authoritative for the XEID-prefix in the Map-Referral record, or if 1623 such a key is found but the signature is not valid the Map-Referral 1624 record is considered corrupted and MUST be discarded. This may be 1625 due to expired keys. The Map Resolver MAY try other siblings of this 1626 node if there is an alternative node authoritative for the same 1627 prefix. If not, the Map Resolver CAN query the DDT node's parent to 1628 retrieve a valid key. It is good practice to use a counter or timer 1629 to avoid repeating this process if the resolver cannot verify the 1630 signature after several trials. 1632 Once the signature is verified, the Map Resolver has verified the 1633 XEID-prefix delegation in the Map-Referral, and authenticated the 1634 public keys of the children DDT nodes. The Map Resolver must add 1635 these keys to the authenticated keys associated with each child DDT 1636 node and XEID-prefix. These keys are considered valid for the 1637 duration specified in the record's TTL field. 1639 11. Open Issues and Considerations 1641 There are a number of issues with the organization of the mapping 1642 database that need further investigation. Among these are: 1644 o Defining an interface to implement interconnection and/or 1645 interoperability with other mapping databases, such as LISP+ALT. 1647 o Additional key structures for use with LISP-DDT, such as to 1648 support additional EID formats as defined in [I-D.ietf-lisp-lcaf] 1650 o Management of the DDT Map Resolver referral cache, in particular, 1651 detecting and removing outdated entries. 1653 o Best practices for configuring hint referrals (or vice verse 1654 avoiding using them). 1656 Operational experience will help answer open questions surrounding 1657 these and other issues. 1659 12. IANA Considerations 1661 This document makes no request of the IANA. 1663 13. Security Considerations 1665 Section 10 describes a DDT security architecture that provides data 1666 origin authentication, data integrity protection, and XEID-prefix 1667 delegation within the DDT Infrastructure. 1669 Global XEID-prefix authorization is beyond the scope of this 1670 document, but the SIDR working group [RFC6480] is developing an 1671 infrastructure to support improved security of Internet routing. 1672 Further work is required to determine if SIDR's public key 1673 infrastructure (PKI) and the distributed repository system it uses 1674 for storing and disseminating PKI data objects may also be used by 1675 DDT devices to verifiably assert that they are the legitimate holders 1676 of a set of XEID prefixes. 1678 This document specifies how DDT security and LISP-SEC 1679 ([I-D.ietf-lisp-sec]) complement one another to secure the DDT 1680 infrastructure, Map-Referral messages, and the Map-Request/Map-Reply 1681 protocols. In the future other LISP security mechanisms may be 1682 developed to replace LISP-SEC. Such future security mechanisms 1683 should describe how they can be used together with DDT to provide 1684 similar levels of protection. 1686 LISP-SEC can use the DDT public key infrastructure to secure the 1687 transport of LISP-SEC key material (the One-Time Key) from a Map- 1688 Resolver to the corresponding Map-Server. For this reason, when 1689 LISP-SEC is deployed in conjunction with a LISP-DDT mapping database 1690 and the path between Map-Resolver and Map-Server needs to be 1691 protected, DDT security as described in Section 10 should be enabled 1692 as well. 1694 14. References 1696 14.1. Normative References 1698 [I-D.ietf-lisp-lcaf] 1699 Farinacci, D., Meyer, D., and J. Snijders, "LISP Canonical 1700 Address Format (LCAF)", draft-ietf-lisp-lcaf-22 (work in 1701 progress), November 2016. 1703 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 1704 Requirement Levels", BCP 14, RFC 2119, 1705 DOI 10.17487/RFC2119, March 1997, 1706 . 1708 [RFC3447] Jonsson, J. and B. Kaliski, "Public-Key Cryptography 1709 Standards (PKCS) #1: RSA Cryptography Specifications 1710 Version 2.1", RFC 3447, DOI 10.17487/RFC3447, February 1711 2003, . 1713 [RFC6830] Farinacci, D., Fuller, V., Meyer, D., and D. Lewis, "The 1714 Locator/ID Separation Protocol (LISP)", RFC 6830, 1715 DOI 10.17487/RFC6830, January 2013, 1716 . 1718 [RFC6833] Fuller, V. and D. Farinacci, "Locator/ID Separation 1719 Protocol (LISP) Map-Server Interface", RFC 6833, 1720 DOI 10.17487/RFC6833, January 2013, 1721 . 1723 14.2. Informative References 1725 [AFI] "Address Family Identifier (AFIs)", IANA , Febuary 2007, 1726 . 1729 [I-D.ietf-lisp-sec] 1730 Maino, F., Ermagan, V., Cabellos-Aparicio, A., and D. 1731 Saucez, "LISP-Security (LISP-SEC)", draft-ietf-lisp-sec-12 1732 (work in progress), November 2016. 1734 [LISP-TREE] 1735 Jakab, L., Cabellos-Aparicio, A., Coras, F., Saucez, D., 1736 and O. Bonaventure, "LISP-TREE: a DNS hierarchy to support 1737 the lisp mapping system", Selected Areas in 1738 Communications, IEEE Journal , 2010, 1739 . 1742 [RFC1918] Rekhter, Y., Moskowitz, B., Karrenberg, D., de Groot, G., 1743 and E. Lear, "Address Allocation for Private Internets", 1744 BCP 5, RFC 1918, DOI 10.17487/RFC1918, February 1996, 1745 . 1747 [RFC5011] StJohns, M., "Automated Updates of DNS Security (DNSSEC) 1748 Trust Anchors", STD 74, RFC 5011, DOI 10.17487/RFC5011, 1749 September 2007, . 1751 [RFC6480] Lepinski, M. and S. Kent, "An Infrastructure to Support 1752 Secure Internet Routing", RFC 6480, DOI 10.17487/RFC6480, 1753 February 2012, . 1755 [RFC6836] Fuller, V., Farinacci, D., Meyer, D., and D. Lewis, 1756 "Locator/ID Separation Protocol Alternative Logical 1757 Topology (LISP+ALT)", RFC 6836, DOI 10.17487/RFC6836, 1758 January 2013, . 1760 [RFC6837] Lear, E., "NERD: A Not-so-novel Endpoint ID (EID) to 1761 Routing Locator (RLOC) Database", RFC 6837, 1762 DOI 10.17487/RFC6837, January 2013, 1763 . 1765 Appendix A. Acknowledgments 1767 The authors would like to express their thanks to Lorand Jakab, 1768 Albert Cabellos-Asparicio, Florin Coras, Damien Saucez, and Olivier 1769 Bonaventure for their work on LISP-TREE [LISP-TREE] and LISP iterable 1770 mappings that inspired the hierarchical database structure and lookup 1771 iteration approach described in this document. Thanks also go to 1772 Dino Farinacci and Isidor Kouvelas for their implementation work; to 1773 Selina Heimlich and Srin Subramanian for testing; to Fabio Maino for 1774 work on security processing; and to Job Snijders, Glen Wiley, Neel 1775 Goyal, and Mike Gibbs for work on operational considerations and 1776 initial deployment of a prototype database infrastructure. Special 1777 thanks go to Jesper Skriver, Andrew Partan, and Noel Chiappa; all of 1778 whom have participated in (and put up with) seemingly endless hours 1779 of discussion of mapping database ideas, concepts, and issues. 1781 Authors' Addresses 1783 Vince Fuller 1785 Email: vaf@vaf.net 1787 Darrel Lewis 1788 Cisco Systems 1790 Email: darlewis@cisco.com 1792 Vina Ermagan 1793 Cisco Systems 1795 Email: vermagan@cisco.com 1797 Amit Jain 1798 Juniper Networks 1800 Email: atjain@juniper.net 1802 Anton Smirnov 1803 Cisco Systems 1805 Email: as@cisco.com