idnits 2.17.1 draft-cheng-lisp-shdht-04.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 : ---------------------------------------------------------------------------- ** There are 10 instances of too long lines in the document, the longest one being 1 character in excess of 72. == There are 18 instances of lines with non-RFC6890-compliant IPv4 addresses in the document. If these are example addresses, they should be changed. == There are 9 instances of lines with private range IPv4 addresses in the document. If these are generic example addresses, they should be changed to use any of the ranges defined in RFC 6890 (or successor): 192.0.2.x, 198.51.100.x or 203.0.113.x. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (July 15, 2013) is 3931 days in the past. Is this intentional? Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) ** Downref: Normative reference to an Experimental draft: draft-meyer-lisp-mn (ref. 'I-D.meyer-lisp-mn') -- Possible downref: Non-RFC (?) normative reference: ref. 'I-ietf-lisp-ddt' -- Possible downref: Non-RFC (?) normative reference: ref. 'LISP-DHT' ** Obsolete normative reference: RFC 6830 (Obsoleted by RFC 9300, RFC 9301) ** Obsolete normative reference: RFC 6833 (Obsoleted by RFC 9301) ** Downref: Normative reference to an Experimental RFC: RFC 6836 Summary: 5 errors (**), 0 flaws (~~), 3 warnings (==), 3 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 LISP Working Group L. Cheng 3 Internet-Draft M. Sun 4 Intended status: Standards Track ZTE Corporation 5 Expires: January 16, 2014 July 15, 2013 7 draft-cheng-lisp-shdht-04 8 LISP Single-Hop DHT Mapping Overlay 10 Abstract 12 This draft specifies the LISP Single-Hop Distributed Hash Table 13 Mapping Database (LISP-SHDHT), a distributed mapping database which 14 consists of a set of SHDHT Nodes to provide mappings from LISP 15 Endpoint Identifiers (EIDs) to Routing Locators (RLOCs). EID 16 namespace is dynamically distributed among SHDHT Nodes based on DHT 17 Hash algorithm. Each SHDHT Node is configured with one or more hash 18 spaces which contain multiple EID-prefixes along with RLOCs of 19 corresponding Map Servers. 21 Status of This Memo 23 This Internet-Draft is submitted in full conformance with the 24 provisions of BCP 78 and BCP 79. 26 Internet-Drafts are working documents of the Internet Engineering 27 Task Force (IETF). Note that other groups may also distribute 28 working documents as Internet-Drafts. The list of current Internet- 29 Drafts is at http://datatracker.ietf.org/drafts/current/. 31 Internet-Drafts are draft documents valid for a maximum of six months 32 and may be updated, replaced, or obsoleted by other documents at any 33 time. It is inappropriate to use Internet-Drafts as reference 34 material or to cite them other than as "work in progress." 36 This Internet-Draft will expire on January 16, 2014. 38 Copyright Notice 40 Copyright (c) 2013 IETF Trust and the persons identified as the 41 document authors. All rights reserved. 43 This document is subject to BCP 78 and the IETF Trust's Legal 44 Provisions Relating to IETF Documents 45 (http://trustee.ietf.org/license-info) in effect on the date of 46 publication of this document. Please review these documents 47 carefully, as they describe your rights and restrictions with respect 48 to this document. Code Components extracted from this document must 49 include Simplified BSD License text as described in Section 4.e of 50 the Trust Legal Provisions and are provided without warranty as 51 described in the Simplified BSD License. 53 Table of Contents 55 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2 56 2. Definition of Terms . . . . . . . . . . . . . . . . . . . . . 5 57 3. SHDHT Overview . . . . . . . . . . . . . . . . . . . . . . . 7 58 3.1. Node ID and Partition ID . . . . . . . . . . . . . . . . 7 59 3.2. Data Storage and Hash Assignment . . . . . . . . . . . . 8 60 3.3. Node Routing Table . . . . . . . . . . . . . . . . . . . 9 61 4. LISP SHDHT . . . . . . . . . . . . . . . . . . . . . . . . . 10 62 4.1. ITR Operation . . . . . . . . . . . . . . . . . . . . . . 10 63 4.2. ETR Operation . . . . . . . . . . . . . . . . . . . . . . 11 64 4.3. SHDHT Map Server Operation . . . . . . . . . . . . . . . 11 65 4.4. SHDHT Map Resolver Operation . . . . . . . . . . . . . . 12 66 4.4.1. SHDHT Map Resolver Operation under SHDHT Forward Mode 12 67 4.4.2. SHDHT Map Resolver Operation under Recursive Lookup 68 Mode . . . . . . . . . . . . . . . . . . . . . . . . 12 69 4.5. SHDHT Nodes Operation . . . . . . . . . . . . . . . . . . 13 70 4.6. EID prefixes Report onto LISP-SHDHT . . . . . . . . . . . 13 71 5. Domain LISP SHDHT Deployment . . . . . . . . . . . . . . . . 16 72 5.1. SHDHT Border Node . . . . . . . . . . . . . . . . . . . 16 73 5.2. EIDs/EID Prefixes Report onto Domain SHDHT Overlay . . . 17 74 5.3. Mapping Request Lookup onto Domain SHDHT Overlay . . . . 17 75 6. Security Considerations . . . . . . . . . . . . . . . . . . . 20 76 7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 21 77 8. References . . . . . . . . . . . . . . . . . . . . . . . . . 22 78 8.1. Normative References . . . . . . . . . . . . . . . . . . 22 79 8.2. Informational References . . . . . . . . . . . . . . . . 22 80 Appendix A. Acknowledgments . . . . . . . . . . . . . . . . . . 22 81 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 22 83 1. Introduction 85 Locator/ID Separation Protocol (LISP) [RFC6830] specifies an 86 architecture and mechanism for replacing the address currently used 87 by IP with two separate name spaces: Endpoint IDs (EIDs), used within 88 LISP sites, and Routing Locators (RLOCs), used on transit networks 89 that make up the Internet infrastructure. To achieve this 90 separation, LISP defines protocol mechanisms for mapping from EIDs to 91 RLOCs. As a result, an efficient database is needed to store and 92 propagate those mappings globally. Several such mapping databases 93 have been proposed, among them: LISP-NERD [I-D.lear-lisp-nerd], LISP- 94 ALT[RFC6836], LISP-DDT[I-ietf-lisp-ddt], and LISP-DHT [LISP-DHT]. 96 According to databases such like LISP-ALT [RFC6836] and LISP-DDT 97 [I-ietf-lisp-ddt], architectures of these mapping databases are based 98 on announcement/delegation of hierarchically-delegated segments of 99 EID namespace (i.e., prefixes). Therefore, based on these 100 architectures, when a roaming event occurs and a LISP site or a LISP 101 MN receives new RLOCs, the site or MN has to anchor pre-configured 102 map-server to register its new mapping information no matter where 103 the site or MN currently locates, just in order to protect EID 104 prefixes announced aggregately in the database [I-D.meyer-lisp-mn]. 106 As a DHT strategy based mapping database, LISP-DHT [LISP-DHT] 107 exhibits several interesting properties, such as self-configuration, 108 self-maintenance, scalability and robustness that are clearly 109 desirable for a EID-to-RLOC resolution service. However, this 110 database is based on multi-hop Chord DHT. On one hand, inquiries of 111 mapping information in this case need to pass through iterative 112 multi-hop lookup steps which will cause relatively large delay time. 113 On the other hand, load balance between Chord nodes is another 114 essential problem need to be solved. 116 This draft specifies a LISP Single-Hop Distributed Hash Table Mapping 117 Overlay (LISP-SHDHT) which provides mapping information lookup 118 service for sites running LISP. Main characters of this strategy is 119 that, 121 1. Each SHDHT Node maintains routing information for all other SHDHT 122 Nodes. Thus, messages interaction between SHDHT Nodes in the 123 same SHDHT overlay just need one hop. 125 2. Traditionally, Node IDs are used to identify DHT nodes and 126 represent hash space arrangement on DHT nodes. In SHDHT 127 strategy, the two roles are separated. Partition IDs are adopted 128 for hash space arrangement and a build-in load balancing solution 129 is designed. 131 This draft specifies the outline of SHDHT and the basic application 132 of LISP SHDHT. In actual deployment of LISP SHDHT, mapping database 133 could be maintained by multiple service providers and could be 134 deployed as collaborative combination of multiple Domain LISP SHDHTs. 135 Details about Domain LISP SHDHT Deployment are introduced in 136 Section 5. 138 In main context of this draft, SHDHT Mapping database is proposed 139 according to structure requirements of LISP-MS [RFC6833]. This SHDHT 140 strategy provides services for LISP Sites mapping lookup. In 141 Appendix A, a special SHDHT strategy for LISP-MN [I-D.meyer-lisp-mn] 142 scenario is proposed. This SHDHT strategy is not completely match 143 structure requirements of LISP-MS. However, it could provide better 144 service for LISP-MN scenario, where LISP-MN need not to anchor pre- 145 configured Map Server and could update its mapping information as 146 soon as possible when it roams to a new location. 148 2. Definition of Terms 150 This draft uses terms defined in [RFC6830]. This section defines 151 some new terms used in this document. 153 SHDHT: Single-Hop Distributed Hash Table Mapping Overlay. 155 SHDHT Node: Physical nodes which compose SHDHT overlay's topology. 156 Each SHDHT Node has a unique Node ID and maintains multiple hash 157 space segments which labeled by Partition IDs. Each SHDHT Node 158 maintains a Node Routing Table of local SHDHT Mapping Overlay. 159 SHDHT Nodes locates in the same Mapping Overlay implement hash 160 operation based on the same hash algorithm. SHDHT Nodes hash data 161 object to be a unique Resource ID, and perform put/get/move 162 operations based on the Resource IDs. 164 Node ID: Node identifier, which is used for maintenance. Each SHDHT 165 Node has a unique Node ID. The ring containing Node IDs indicates 166 overlay's topology. 168 Partition ID: Partition identifier, which is used for hash space 169 assignment. Partition IDs and Resource IDs share the same hash 170 space. All Partition IDs in overlay are unique. Each SHDHT Node 171 could have multiple Partition IDs. The ring containing Partition 172 IDs determines how the hash space is partitioned into segments and 173 how these segments are assigned to nodes. 175 Resource ID: Each data object stored in DHT overlay could be hashed 176 to be a unique Resource ID. In LISP-SHDHT strategy, data objects 177 correspond to the EIDs. Resource IDs share the same hash space 178 with Partition IDs. As a result, SHDHT Nodes perform data objects 179 put/get/remove operations based on these IDs. 181 Node Routing Table: Routing table of a SHDHT Mapping Overlay which 182 contains all SHDHT Nodes information of this overly, including 183 Node IDs, Partition IDs and Node IP addresses, etc. Each SHDHT 184 Node of this overly will maintain the Routing Table. 186 SHDHT Map Resolver: A SHDHT Node that also implements Map Resolver 187 functionality (accept Map-Requests, and forward them to 188 corresponding SHDHT Map Servers based on information get from 189 SHDHT mapping database or forward them to corresponding SHDHT Map 190 Servers through SHDHT Nodes, which corresponds to different 191 operation modes of the SHDHT Mapping Database.). 193 Report Message: Kind of message sent by Map Server to SHDHT Nodes to 194 publish the EIDs/EID prefix information in charge of Map Server 195 onto the LISP-SHDHT mapping overlay. 197 SHDHT Border Node: SHDHT Border Node locates on the border of a 198 Domain SHDHT Overlay. Each SHDHT Border Node maintains an Inter- 199 Domain Routing Table. SHDHT Border Nodes are used to flood cross 200 domain routing and forward cross domain packets. 202 Inter-Domain Routing Table: A routing table maintained on a SHDHT 203 Border Node. This routing table contains information of other 204 Domain SHDHT Overlays, such like EID prefixes other domain 205 overlays maintain, IP addresses and ports information of other 206 overlay's Border Nodes. 208 3. SHDHT Overview 210 3.1. Node ID and Partition ID 212 Most of existing DHTs use node IDs for both maintenance and hash 213 space arrangement. For example, in LISP-DHT[LISP-DHT], each chord 214 node of the DHT ring has a unique k-bits identifier (ChordID). Nodes 215 perform operations such like put/get/remove based on ChordIDs. 216 Furthermore, ChordIDs are also used to associate nodes with hash 217 space segments that the nodes responsible for. 219 In SHDHT, two roles of maintenance and hash space arrangement are 220 separated and a new kind identifier called Partition ID is adopted. 221 Each SHDHT node has a unique Node ID which identifies the physical 222 node and multiple Partition IDs which represent hash space segments. 223 All Partition IDs in the overlay are also unique. Node IDs and 224 Partition IDs are mapped into two ring-shaped spaces respectively. 225 The ring containing Node IDs indicates the overlay's topology. The 226 ring containing Partition IDs determines how the hash space is 227 partitioned into segments and how these segments are assigned to 228 nodes. It is noteworthy that SHDHT Nodes could determine number of 229 Partition IDs on them separately and could generate Partition IDs 230 randomly just need to make sure that the generated Partition IDs will 231 not conflict with existing Partition IDs on the SHDHT plane. 233 +--------------------+ +--------------------+ 234 |Node ID: 0x0123| |Node ID: 0x4444| 235 |Partition ID: 0x1234| +-----+ +-----+ |Partition ID: 0x9000| 236 | 0x7000| |Node1+----------+Node2| | 0x3234| 237 +--------------------+ +--+--+ +--+--+ +--------------------+ 238 | | 239 | | 240 | | 241 | | 242 +--------------------+ +--+--+ +--+--+ +--------------------+ 243 |Node ID: 0xe000| |Node3+----------+Node4| |Node ID: 0xc000| 244 |Partition ID: 0x5000| +-----+ +-----+ |Partition ID: 0xaaaa| 245 | 0xeeee| | 0xcccc| 246 +--------------------+ +--------------------+ 248 Fig.1 SHDHT Deployment Example 250 As shown in Fig.1 is an example of SHDHT. This SHDHT overlay is 251 consist of four SHDHT NODEs each has a unique Node ID and maintains 252 two Partition IDs. According to this deployment, hash space is 253 partitioned to be eight segments each is indexed by a Partition ID. 254 From Fig. 1, it could be observed that hash space segments are not 255 required to be partitioned equally. As SHDHT Nodes could generate 256 Partition IDs separately, when a SHDHT Node gets all hash segments 257 assignment information of other SHDHT Nodes, it will be able to 258 implement the load balance of SHDHT overlay by generate proper 259 Partition IDs. 261 In SHDHT, each SHDHT Node stores and maintains data objects. Data 262 objects are indexed by Resource IDs which share the same hash space 263 with Partition IDs and will locate in the hash space segments whose 264 Partition IDs are closest to their Resource IDs. 266 For example, for a data object whose Resource ID is 0x8213, the 267 Resource ID locates between Partition ID 0x7000 and Partition ID 268 0x9000. As Partition ID 0x9000 is closer to Resource ID 0x8213, the 269 data object will be stored and maintained on Node2 who is assigned 270 with the hash space segment indexed by Partition ID 0x9000. 272 3.2. Data Storage and Hash Assignment 274 In traditional DHTs, hash space is partitioned into segments based on 275 node IDs. As a result, data objects are always stored in their root 276 nodes, whose node IDs are "closest" to data objects' Resource IDs. 278 What does "closest" means? Suppose we have three consecutive 279 Partition IDs a, b and c which are the only Partition IDs in SHDHT 280 for our example, then the range of each hash space segment is defined 281 as follow: 283 Partition ID a: [id(a)-0.5*d(c,a); id(a)+0.5*d(a,b)) 285 Partition ID b: [id(b)-0.5*d(a,b); id(b)+0.5*d(b,c)) 287 Partition ID c: [id(c)-0.5*d(b,c); id(c)+0.5*d(c,a)) 289 with functions 291 id(x): value of Partition ID x in hash space 293 d(x,y): distance between Partition ID x and y in hash space 295 Replications of data objects in a particular node are always stored 296 in the preceding node or successor node of the root node. The backup 297 preceding node or successor node will automatically become the new 298 closest node if the root node leaves the overlay. 300 In SHDHT, the whole hash space is partitioned into segments based on 301 partition IDs. The root node of a data object is the node, which has 302 the closest partition ID to the data object's Resource ID. In SHDHT, 303 each node can maintain multiple hash space segments with respective 304 Partition IDs. As the preceding Partition ID or successor Partition 305 ID may be owned by the same root node. Replication of data objects 306 could still be stored in preceding node or successor node of root 307 node. 309 3.3. Node Routing Table 311 In SHDHT, each node maintains a Node Routing Table containing routing 312 information of all other SHDHT Nodes locate in the same SHDHT 313 overlay. Table I shows the Node Routing Table on SHDHT Nodes of 314 Fig.1. A Node Routing Table contains all Partition IDs and their 315 associated Node IDs and node addresses. For simplification, Node IDs 316 and Partition IDs shown in the draft are only 16-bit numbers. 318 When SHDHT Node receives a message points to a particular Resource 319 ID, it could look up Node Routing Table and find out the Partition ID 320 which is closest to the Resource ID. Furthermore, message could be 321 transferred to the corresponding SHDHT Node. 323 +--------------+---------+---------------+ 324 | Partition ID | Node ID | Address:Port | 325 +--------------+---------+---------------+ 326 | 0x1234 | 0x0123 | 10.0.0.2:2000 | 327 | 0x3234 | 0x4444 | 10.0.0.3:2000 | 328 | 0x5000 | 0xe000 | 10.0.0.4:2000 | 329 | 0x7000 | 0x0123 | 10.0.0.2:2000 | 330 | 0x9000 | 0x4444 | 10.0.0.3:2000 | 331 | 0xaaaa | 0xc000 | 10.0.0.5:2000 | 332 | 0xcccc | 0xc000 | 10.0.0.5:2000 | 333 | 0xeeee | 0xe000 | 10.0.0.4:2000 | 334 +--------------+---------+---------------+ 336 TABLE I SHDHT Node Routing Table 338 For example, if Node 1 (ID: 0x1234) in Fig.1 needs to implement put/ 339 get/remove operations for a data object with Resource ID 0x8213. 340 Node 1 first looks up its Node Routing Table and finds out that the 341 closest Partition ID corresponding to this Resource ID is 0x9000. 342 Then Node 1 will send put/get/remove request to the node owns the 343 Partition ID, in Fig.1 is Node2, whose Node ID is 0x4444 and address 344 is 10.0.0.3:2000. 346 4. LISP SHDHT 348 LISP SHDHT is proposed to provide "EID-to-RLOC(s)" mapping 349 information lookup service for sites running the Locator/ID 350 Separation Protocol (LISP). 352 As shown in Fig.2, LISP SHDHT is consists of SHDHT Nodes in which 353 some nodes play roles of Map Resolver. And in the draft, term 354 "SHDHT-MR" is adopted to identify these nodes. 356 +--------------------+ 357 |Node ID: 0x4444| 358 +-----+ +-----+ |Partition ID: 0x9000| 359 |Node1+---------+Node2| | 0x3234| 360 +--+--+ +--+--+ +--------------------+ 361 | | 362 | SHDHT | 363 | | 364 +--+--+ +--+--+ +-----+ 365 +-------+ M R +---------+Node4+-------+ M S | 366 | +-----+ +-----+ +--+--+ 367 | | 368 +--+--+ +--+--+ 369 | ITR | | ETR | 370 +-----+ +-----+ 372 Fig.2 LISP-SHDHT Deployment Example 374 Map Server publishes EIDs/EID prefixes information it responsible to 375 onto SHDHT Mapping overlay. All EIDs/EID prefixes entries are stored 376 in SHDHT Nodes as data objects. EIDs/EID prefixes in mapping entries 377 can be hashed as Resource IDs of data objects. All SHDHT Nodes in 378 the same SHDHT overlay perform hash operation based on the same hash 379 algorithm. 381 In this draft, LISP-SHDHT can run in two distinct modes: i) SHDHT 382 Forward Mode and ii) Recursive Lookup Mode. 384 4.1. ITR Operation 386 According to LISP-MS [RFC6833], LISP ITRs use Map Resolvers as proxy 387 to send control messages, such like encapsulated Map-Requests and 388 Map-Replies. 390 In Scenario of LISP SHDHT, an ITR send Map-Requests directly to the 391 SHDHT Node which is selected to play roles of SHDHT Map Resolver for 392 that ITR. 394 4.2. ETR Operation 396 LISP ETR plays the same role as defined in LISP-MS [RFC6833]; it 397 registers mapping information onto the Map Server by sending Map- 398 Register messages. 400 4.3. SHDHT Map Server Operation 402 When Map Server receives Map Request messages, it forwards the 403 messages to ETRs or send Map-Reply messages directly based on M-bits 404 of ETRs' Map Registers. That's to say, Map Server performs the same 405 operation as defined in LISP-MS[RFC6833] . 407 Extended in LISP SHDHT, Map Server needs to publish EIDs/EID prefixes 408 information onto the LISP-SHDHT mapping overlay. 410 For example, as shown in figure 2, when a Map Server needs to publish 411 EIDs information such like EID "1.1.1.1" onto LISP-SHDHT, following 412 operations will be performed. 414 1. Map Server sends a report message to the nearest SHDHT Node, i.e. 415 Node 4. Map Server contains the information of EID "1.1.1.1" in 416 the report message, along with Map Server's routable RLOCs. 417 Report message may not be a kind of new defined message. For 418 example, Map Server could advertise EID information onto SHDHT 419 mapping database based on BGP protocol. 421 2. When Node 4 receives the report message, it extracts EID 422 information from the message, i.e. EID "1.1.1.1". Node 4 then 423 hashes the report EID to be a Resource ID. 425 3. Suppose Node 4 hash EID "1.1.1.1" to be Resource ID 0x8956. Then 426 it checks the Nodes Routing Table to find out which Node 427 maintains the hash space whose Partition ID matches the Resource 428 ID. In this example, the match Partition ID is 0x9000, and the 429 corresponding hash space is maintained by Node 2. 431 4. Node 4 forwards the report message to Node 2. Node 2 stores the 432 (key, value) pair, where key is the Resource ID 0x8956, and value 433 contains reported EID "1.1.1.1" along with corresponding Map 434 Server's RLOCs. 436 Other SHDHT Nodes now could contact Node2 to get which Map Server is 437 responsible to the EID "1.1.1.1". 439 Note: In previous example, we suppose that Map-Server reports an EID 440 address onto LISP-SHDHT. In practical deployment, Map Server reports 441 EID prefixes at most time. Details about EID prefix report will be 442 illustrated in Section 4.6. 444 4.4. SHDHT Map Resolver Operation 446 As previous mentioned, LISP-SHDHT can run in two distinct modes: i) 447 SHDHT Forward Mode and ii) Recursive Lookup Mode. 449 As shown in Fig.2, suppose SHDHT Map Resolver receives a Map-Request 450 message target at EID 1.1.1.1. SHDHT Map Resolver operations under 451 two different modes are illustrated in following sections. 453 4.4.1. SHDHT Map Resolver Operation under SHDHT Forward Mode 455 Under SHDHT Forward Mode, SHDHT Map Resolver performs the following 456 operaion. 458 1. SHDHT Map Resolver extracts destination EID address "1.1.1.1" 459 from the Map-Request message. 461 2. SHDHT Map Resolver hashes the EID address to be Resource ID 462 0x8956 based on the shared hash algorithm. 464 3. SHDHT Map Resolver looks up Node Routing Table and finds out the 465 Partition ID 0x9000 which matches the Resource ID. 467 4. SHDHT Map Resolver forwards Map-Request message to the 468 corresponding SHDHT Node 2 who maintains the hash space labeled 469 by matched Partition ID 0x9000. 471 4.4.2. SHDHT Map Resolver Operation under Recursive Lookup Mode 473 Under Recursive Lookup Mode, SHDHT Map Resolver performs the 474 following operation. 476 1. SHDHT Map Resolver receives the Map-Request message and stores it 477 in local catch. 479 2. SHDHT Map Resolver hash destination EID of Map-Request to be 480 Resource ID 0x8956. 482 3. SHDHT Map Resolver looks up Node Routing Table and finds out that 483 Node 2 maintains the corresponding hash space and stores the data 484 object indexed by 0x8956. 486 4. SHDHT Map Resolver query Node 2 to get data object indexed by 487 0x8956, i.e. get EID information and RLOCs of the Map Server who 488 maintains the destination EID. 490 5. SHDHT Map Resolver forwards Map-Request message to corresponding 491 Map Server based on data object. 493 Under Recursive Lookup Mode, SHDHT Map Resolve could catch 494 information of the Map Server, including EID prefix Map Server 495 responsible for and Map Server's RLOCs. When receives other Map 496 Requests whose destination EIDs covered by Map Server's EID prefix, 497 Map Resolver could forward Map Requests directly to Map Server. 499 4.5. SHDHT Nodes Operation 501 As specified in Section 4.3, when SHDHT Nodes receive a report 502 message, it will hash the report EID/EID prefix to be Resource ID, 503 and check which Node should store the data object. If itself is the 504 responsible Node, it will store the (key, value) pair, otherwise, it 505 forward report message to corresponding Node. 507 As specified in Section 4.4.1, under SHDHT Forward Mode, when a SHDHT 508 Node receives a Map-Request message from a Map Resolver, it hashes 509 the requested EID to be a Resource ID to get the data object stored 510 in its hash space. Then SHDHT Node forwards the Map-Request to Map 511 Server based on data object information. 513 As specified in Section 4.4.2, under Recursive Lookup Mode, when a 514 SHDHT Node receives a query message from Map Resolver, it replies 515 with the data object Map Resolver requested. 517 4.6. EID prefixes Report onto LISP-SHDHT 519 In LISP-SHDHT, Map Server always report EID prefixes onto the SHDHT 520 Mapping overlay. However, Map-Request message always targets at a 521 specific EID address. How to hash the requested EID and the EID 522 prefix covered this EID to be the same Resource ID? Each LISP-SHDHT 523 Mapping overlay could configure a "Hash Bit" to solve this problem. 525 As shown in Fig.3, suppose the LISP-SHDHT Mapping overlay configures 526 the "Hash Bit" to be 16 bits. 528 +--------------------+ +--------------------+ 529 |Node ID: 0x0123| |Node ID: 0x4444| 530 |Partition ID: 0x1234| +-----+ +-----+ |Partition ID: 0x9000| 531 | 0x7000| |Node1+---------+Node2| | 0x3234| 532 +--------------------+ +--+--+ +--+--+ +--------------------+ 533 | | 534 | SHDHT | 535 | Hash Bit=16 | 536 | | 1.1.1/24 537 +--+--+ +--+--+ +-----+ +------+ 538 Map-Request +-------+ M R +---------+Node4+----+ MS1 +----+ ETR1 | 539 1.1.1.1 | +-----+ +--+--+ +-----+ +------+ 540 2.0.0.1 | | 541 +--+--+ | +-----+ +------+ 542 | ITR | +-------+ MS2 +----+ ETR2 | 543 +-----+ +-----+ +------+ 544 2.0/15 546 Fig.3 EID Prefix Report Example 548 Example 1: MS1 reports EID prefix 1.1.1/24 onto the LISP-SHDHT. 550 1. When Node4 receives the report message from MS1, it extracts the 551 EID prefix 1.1.1/24. 553 2. Node4 hashes the EID prefix to be Resource ID based on Hash Bit. 554 In this case, Hash Bit is 16 bits, as a result Node4 hashes the / 555 16 prefix of reported EID prefix. That's to say, Node4 hashes 556 1.1/16 to be a Resource ID, suppose to be 0x8560. 558 3. Node 4 checks Node Routing Table and forwards the report message 559 to Node 2 who maintains the corresponding hash space with 560 Partition ID 0x9000. 562 In this example, when another Map Server advertises EID prefix such 563 like 1.1.2/24, this prefix will also be hashed to be Resource ID 564 0x8560 and the report message will be forwarded to Node 2. 566 Node 2 maintains (key, value) pair, where key is 0x8560 and value 567 contains all EIDs/EID prefixes information covered by 1.1/16. 569 Example 2: MS2 reports EID prefix 2.0/15 onto the LISP-SHDHT. 571 1. When Node4 receives the report message from MS1, it extracts the 572 EID prefix 2.0/15. 574 2. Node4 hashes the EID prefix to be Resource ID based on Hash Bit. 575 In this case, Hash Bit is 16 bits, Node4 first splits the EID 576 prefix 2.0/15 to be two 16 bits sub-prefixes, 2.0/16 and 2.1/16. 577 Suppose Node 4 hashes prefix 2.0/16 to be Resource ID 0x1210 and 578 hashes prefix 2.1/16 to be Resource ID 0x3200. 580 3. As Shown in Fig. 3, data objects with Resource ID 0x1210 and 581 0x3200 should be stored on Node 1 and Node 2 separately. Node 4 582 will copy the report message and forward report message both to 583 Node 1 and Node 2. 585 In this example, Node 1 and Node 2 maintains (key, value) pairs with 586 different keys (0x1210 and 0x3200), but the value both contain the 587 same EID prefix 2.0/15. 589 In practical deployment, SHDHT service providers could configure 590 proper Hash Bits, in order to avoid the scenario which needs to split 591 a shorter EID prefix to be multiple longer prefixes. 593 Example 3: ITR sends Map Requests onto LISP-SHDHT. 595 1. When ITR sends a Map-Request target at EID 1.1.1.1 as shown in 596 Fig.3, SHDHT Map Resolver hashes the EID based on Hash Bit, i.e. 597 SHDHT Map Resolver hashes EID prefix 1.1/16 to get the Resource 598 ID. SHDHT Map Resolver judges the corresponding data object is 599 stored on Node 2 (according to Example 1), then SHDHT Map 600 Resolver could forward the Map-Request to Node 2 (based on SHDHT 601 Forward Mode) or get information about the best matched EID 602 prefix 1.1.1/24 from Node 2 (based on Recursive Lookup Mode). 604 2. When ITR sends a Map-Request target at EID 2.0.0.1, SHDHT Map 605 Resolver hashes EID prefix 2.0/16 to get the Resource ID. SHDHT 606 Map Resolver judges the corresponding data object is stored on 607 Node 1 (according to Example 2), then SHDHT Map Resolver could 608 forward the Map-Request to Node 1 (based on SHDHT Forward Mode) 609 or get information about the best matched EID prefix 2.0/15 from 610 Node 1 (based on Recursive Lookup Mode). 612 5. Domain LISP SHDHT Deployment 614 LISP is a global architecture. In order to make LISP SHDHT meets 615 requirements of LISP mapping database better, LISP SHDHT should 616 perform better scalability and distribution attributes. Especially 617 in practical deployment, LISP mapping database may be operated by 618 different ISPs, when a new mapping service provider join or leave the 619 mapping database, all other providers should not be influenced to be 620 re-assigned. 622 In practical deployment, LISP SHDHT mapping overlay could be consist 623 of multiple Domain SHDHT overlays which are operated by different 624 mapping service providers. These Domain SHDHT overlays communicate 625 through SHDHT Border Nodes of each other. 627 As shown in Fig.4, there are two Domain LISP SHDHT Overlays which 628 communicate through BN1 (Border Node1) and BN2. 630 In domain LISP SHDHT deployment, different domain overlays maintain 631 EID-to-RLOC mapping information covered by different EID prefixes. 632 As in example of Fig.4, Domain 1 maintains mapping information 633 according to EID prefix 12.0.0.0/8, and Domain 2 maintains mapping 634 information covered by EID prefix 16.0.0.0/8. Furthermore, different 635 Domain Overlay could configure their Hash Bits separately. 637 +------+ +-----+ +-----+ +-----+ +-----+ +------+ 638 | ITR1 +--+ MR1 +-------+Node2| |Node4+-------+ MR2 +---+ ITR2 | 639 +------+ +--+--+ +--+--+ +--+--+ +--+--+ +------+ 640 | Domain | | Domain | 641 | Overlay 1 | | Overlay 2 | 642 | Hash Bit 16 | | Hash Bit 14 | 643 | 12.0.0.0\8 | | 16.0.0.0\8 | 644 +-----+ +--+--+ +--+--+ +--+--+ +--+--+ +-----+ 645 | MS1 +--+Node3+-------+ BN1 |<--->| BN2 +-------+Node6+---+ MS2 | 646 +-----+ +-----+ +-----+ +-----+ +-----+ +-----+ 648 * BN: SHDHT Border Node 649 * MR: SHDHT Map Resolver 650 * MS: Map Server 652 Fig.4 Domain SHDHT Deployment Example 654 5.1. SHDHT Border Node 656 Each Domain SHDHT Overlay has one or more Border Nodes which are not 657 only perform like normal SHDHT Nodes, but also be used to flood cross 658 domain routing and forward the cross domain packets. 660 Each SHDHT Border Node maintains an Inter-Domain Routing Table, which 661 contains information of all other domain overlays, such like EID 662 prefixes other domain overlays maintain, IP addresses and ports 663 information of other overlays' Border Nodes. 665 At the beginning, Inter-Domain Routing Table could be configured on 666 SHDHT Border Nodes. Then, a SHDHT Border Node will flood cross 667 domain routing periodically to trigger other Border Nodes update 668 their Inter-Domain Routing Tables. 670 5.2. EIDs/EID Prefixes Report onto Domain SHDHT Overlay 672 All SHDHT Nodes of a Domain SHDHT Overlay must be noticed the EID 673 prefixes that local domain overlay responsible for. When a SHDHT 674 Node of a domain overlay receives a report message, it checks if the 675 registered EIDs/EID prefixes are covered by local domain overlay's 676 EID prefixes. 678 If local domain overlay is responsible for reported EIDs/EID 679 prefixes, SHDHT Node who receives report message will process the 680 message as procedures listed in Section 4.3 and 4.6 682 Otherwise, if local domain overlay is not responsible for reported 683 EIDs/EID prefixes, SHDHT Node who receives report message will 684 forward it directly to local domain overlay's Border Nodes. Then, 685 Border Nodes will forward the message to corresponding domain overlay 686 based on the Inter-Domain Routing Table. 688 Suppose in Fig.4, MS2 reports EID prefix 12.2.0/24 to Node 6 of 689 Domain 2. 691 1. Node6 extracts the EID prefix from report message and finds that 692 the reported EID prefix is 12.2.0/24. 694 2. Node6 determines that EID prefix 12.2.0/24 is not covered by 695 Domain 2's prefix 16.0.0.0/8. 697 3. Node6 forwards the report message to BN2. 699 4. BN2 looks up Inter-Domain Routing Table to find that Domain 1 is 700 responsible for EID prefix 12.2.0/24. BN2 forwards report 701 message to Domain 1's Border Node (BN1). 703 5. BN1 processes the report message based on procedures introduced 704 in Section 4.3 and 4.6. 706 5.3. Mapping Request Lookup onto Domain SHDHT Overlay 707 When SHDHT Map Resolver receives a Map-Request message, it checks if 708 the requested EID is covered by local domain overlay's EID prefixes, 709 i.e. if the requested mapping entry is stored on local domain 710 overlay. 712 If local domain overlay is responsible for requested EID, SHDHT Map 713 Resolver processes the message based on procedures introduced in 714 Section 4.4 and 4.6. 716 Otherwise, if the requested EID entry is not stored on local domain 717 overlay, under SHDHT Forward Mode, SHDHT Map Resolver directly 718 forwards the Map-Request to Border Nodes. Border Nodes of local 719 domain overlay then forwards it to corresponding domain overlay based 720 on Inter-Domain Routing Table. 722 Suppose in Fig.4, ITR2 sends a Map-Request message to SHDHT MR 2 of 723 Domain 2 to get mapping information of EID 12.2.0.1. 725 1. SHDHT MR2 extracts requested EID from the Map-Request message. 727 2. SHDHT MR2 determines that requested EID 12.2.0.1 is not covered 728 by Domain 2's prefix 16.0.0.0/8. 730 3. SHDHT MR2 forwards the Map-Request message to BN2. 732 4. BN2 extracts requested EID and looks for Inter-Domain Routing 733 Table to find corresponding domain overlay of EID 12.2.0.1. 735 5. BN2 finds out Domain 1 is responsible for EID 12.2.0.1. BN2 736 forwards Map-Request message to Domain 1's Border Node (BN1). 738 6. BN1 processes the Map-Request message based on procedures 739 introduced in Section 4.4 and 4.6. 741 If the requested EID entry is not stored on local domain overlay, 742 under Recursive Lookup Mode, SHDHT Map Resolver catch the Map-Request 743 message, and send query message to Border Nodes. Border Nodes of 744 local domain overlay query Border Nodes of the corresponding domain 745 overlay responsible for requested EID entry to get related 746 information. 748 Suppose in Fig.4, ITR2 sends Map-Request message to SHDHT MR 2 to get 749 mapping information of 12.2.0.1. 751 1. SHDHT MR2 determines the requested EID 12.2.0.1 is not covered by 752 Domain 2's prefix 16.0.0.0/8. 754 2. SHDHT MR2 catches the Map-Request message and sends a query 755 message for EID 12.2.0.1 to BN2. 757 3. BN2 finds out Domain 1 is responsible for the requested EID. BN2 758 sends query message to BN1. 760 4. BN1 hashes 12.2/16 to be Resource ID to get which SHDHT Node in 761 Domain 1 now maintains information of EIDs covered by EID prefix 762 12.2/16. 764 5. Suppose the responsible Node in Domain 1 is Node 2. Node 2 765 maintains information of EID prefix 12.2.0/24 along with MS2's 766 RLOC information. BN2 queries Node 2 to get the information and 767 sends them to BN1. 769 6. BN1 sends relative information to SHDHT MR 2. 771 7. After the recursive lookup procedures, SHDHT MR 2 sends the Map- 772 Request directly to MS2. 774 6. Security Considerations 776 TBD 778 7. IANA Considerations 780 This document makes no requests to IANA. 782 8. References 784 8.1. Normative References 786 [I-D.meyer-lisp-mn] 787 Farinacci, D., Lewis, D., Meyer, D., and C. White, "LISP 788 Mobile Node", October 2012. 790 [I-ietf-lisp-ddt] 791 Fuller, V., Lewis, D., and V. Ermagan, "LISP Delegated 792 Database Tree", October 2012. 794 [LISP-DHT] 795 Mathy, L. and L. Iannone, "LISP-DHT: Towards a DHT to map 796 identifiers onto locators, 797 http://dl.acm.org/citation.cfm?id=1544073", December 2008. 799 [RFC6830] Farinacci, D., Fuller, V., Meyer, D., and D. Lewis, 800 "Locator/ID Separation Protocol (LISP)", January 2013. 802 [RFC6833] Fuller, V. and D. Farinacci, "LISP Map Server Interface", 803 January 2013. 805 [RFC6836] Fuller, V., Farinacci, D., Meyer, D., and D. Lewis, "LISP 806 Alternative Topology (LISP+ALT)", January 2013. 808 8.2. Informational References 810 [I-D.lear-lisp-nerd] 811 Lear, E., "NERD: A Not-so-novel EID to RLOC Database", 812 April 2012. 814 Appendix A. Acknowledgments 816 The authors with to express their thanks to Michael Hoefling for work 817 on Hash space segment of SHDHT overlay. Thanks also go to Dino 818 Farinacci and Darrel Lewis for their suggestions about database 819 structure deployment. 821 Authors' Addresses 823 Li Cheng 824 ZTE Corporation 825 R&D Building 1, Zijinghua Road No.68 826 Nanjing, Yuhuatai District 210012 827 P.R.China 829 Email: cheng.li2@zte.com.cn 830 Mo Sun 831 ZTE Corporation 832 R&D Building 1, Zijinghua Road No.68 833 Nanjing, Yuhuatai District 210012 834 P.R.China 836 Email: sun.mo@zte.com.cn