idnits 2.17.1 draft-cheng-lisp-shdht-00.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 8 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 doesn't use any RFC 2119 keywords, yet seems to have RFC 2119 boilerplate text. -- The document date (July 8, 2012) is 4308 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) -- No information found for draft-mathy-lisp-dht - is the name correct? Summary: 0 errors (**), 0 flaws (~~), 3 warnings (==), 2 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 9, 2013 July 8, 2012 7 draft-cheng-lisp-shdht-00 8 LISP Single-Hop DHT Mapping Overlay 10 Abstract 12 This draft specifies the LISP Single-Hop Distributed Hash Table 13 Mapping Overlay (LISP-SHDHT), a distributed mapping database which 14 embodies SHDHT Nodes to maintain (Key, value) pairs for LISP 15 (Locator/ID Separation Protocol)-like architecture, wherein every 16 (key value) pair is according to an EID(Endpoint ID)-to-RLOC(Routing 17 Locator) mapping information entry. According to this strategy, EID 18 is hashed to be a unique Resource ID which is used for locating 19 destiny DHT Node who maintains mapping entry for the particular EID. 20 Furthermore, adaptive hash space partition method is adopted to solve 21 the load balance problem on SHDHT Nodes which is common on 22 traditional DHT plan. 24 Status of this Memo 26 This Internet-Draft is submitted in full conformance with the 27 provisions of BCP 78 and BCP 79. 29 Internet-Drafts are working documents of the Internet Engineering 30 Task Force (IETF). Note that other groups may also distribute 31 working documents as Internet-Drafts. The list of current Internet- 32 Drafts is at http://datatracker.ietf.org/drafts/current/. 34 Internet-Drafts are draft documents valid for a maximum of six months 35 and may be updated, replaced, or obsoleted by other documents at any 36 time. It is inappropriate to use Internet-Drafts as reference 37 material or to cite them other than as "work in progress." 39 This Internet-Draft will expire on January 9, 2013. 41 Copyright Notice 43 Copyright (c) 2012 IETF Trust and the persons identified as the 44 document authors. All rights reserved. 46 This document is subject to BCP 78 and the IETF Trust's Legal 47 Provisions Relating to IETF Documents 48 (http://trustee.ietf.org/license-info) in effect on the date of 49 publication of this document. Please review these documents 50 carefully, as they describe your rights and restrictions with respect 51 to this document. Code Components extracted from this document must 52 include Simplified BSD License text as described in Section 4.e of 53 the Trust Legal Provisions and are provided without warranty as 54 described in the Simplified BSD License. 56 Table of Contents 58 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 59 1.1. Requirements Language . . . . . . . . . . . . . . . . . . 4 60 2. Definition of Terms . . . . . . . . . . . . . . . . . . . . . 4 61 3. SHDHT Overview . . . . . . . . . . . . . . . . . . . . . . . . 4 62 3.1. Node ID and Partition ID . . . . . . . . . . . . . . . . . 4 63 3.2. Data Storage and Hash Assignment . . . . . . . . . . . . . 5 64 3.3. Node Routing Table . . . . . . . . . . . . . . . . . . . . 6 65 4. LISP SHDHT . . . . . . . . . . . . . . . . . . . . . . . . . . 6 66 4.1. SHDHT Node Operation . . . . . . . . . . . . . . . . . . . 7 67 4.2. ITR Operation . . . . . . . . . . . . . . . . . . . . . . 7 68 4.3. ETR Operation . . . . . . . . . . . . . . . . . . . . . . 8 69 4.4. Encapsulated Message Format . . . . . . . . . . . . . . . 8 70 4.4.1. Encapsulated Map Request . . . . . . . . . . . . . . . 9 71 4.4.2. Encapsulated Map Register . . . . . . . . . . . . . . 9 72 5. Mobility Considerations . . . . . . . . . . . . . . . . . . . 10 73 6. Security Considerations . . . . . . . . . . . . . . . . . . . 10 74 7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 10 75 8. References . . . . . . . . . . . . . . . . . . . . . . . . . . 10 76 8.1. Normative References . . . . . . . . . . . . . . . . . . . 10 77 8.2. Informational References . . . . . . . . . . . . . . . . . 10 78 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 11 80 1. Introduction 82 Locator/ID Separation Protocol (LISP) [I-D.ietf-lisp] specifies an 83 architecture and mechanism for replacing the address currently used 84 by IP with two separate name spaces: Endpoint IDs (EIDs), used within 85 sites, and Routing Locators (RLOCs), used on transit networks that 86 make up the Internet infrastructure. To achieve this separation, 87 LISP defines protocol mechanisms for mapping from EIDs to RLOCs. As 88 a result, an efficient database is needed to store and propagate 89 those mapping globally. Several such mapping databases have been 90 proposed, among them: LISP-NERD [I-D.lear-lisp-nerd], LISP- 91 ALT[I-D.ietf-lisp-alt], LISP-DDT[I-D.fuller-lisp-ddt], and LISP-DHT 92 [I-D.fuller-lisp-ddt]. 94 According to hybrid model databases such like LISP-ALT 95 [I-D.ietf-lisp-alt] and LISP-DDT [I-D.fuller-lisp-ddt], architectures 96 of these mapping databases are based on announcement/delegation of 97 hierarchically-delegated segments of EID namespace (i.e., prefixes). 98 Therefore, based on these architectures, when a roaming event occurs 99 and a LISP site or a LISP MN receives new RLOCs, the site or MN has 100 to anchor pre-configured map-server to register its new mapping 101 information no matter where the site or MN currently locates, just in 102 order to protect EID prefixes announced aggregately in the database 103 [I-D.meyer-lisp-mn]. 105 As a DHT strategy based mapping database, LISP-DHT 106 [I-D.mathy-lisp-dht] exhibits several interesting properties, such as 107 self-configuration, self-maintenance, scalability and robustness that 108 are clearly desirable for a EID-to-RLOC resolution service. However, 109 this database is based on multi-hop Chord DHT. On one hand, 110 inquiries of mapping information in this case need to pass through 111 iterative multi-hop lookup steps which will cause relatively large 112 delay time. On the other hand, load balance between Chord nodes is 113 another essential problem need to be solved. 115 This draft specifies a Single-Hop Distributed Hash Table Mapping 116 Overlay (LISP-SHDHT) which provides mapping information lookup 117 service for sites running LISP. Main characters of this strategy is 118 that, 120 1. Each SHDHT Node maintains routing information for all other SHDHT 121 Nodes. Thus, massages interaction between SHDHT Nodes in the 122 same SHDHT overlay just need one or two hops. 124 2. Traditionally, Node IDs are used to identify DHT nodes and 125 represent hash space arrangement on DHT nodes. In SHDHT 126 strategy, the two roles are separated. Partition IDs are adopted 127 for hash space arrangement and a build-in load balancing solution 128 is designed. 130 1.1. Requirements Language 132 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 133 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 134 document are to be interpreted as described in RFC2119 [RFC2119]. 136 2. Definition of Terms 138 This draft uses terms defined in [I-D.ietf-lisp]. This section 139 defines some new terms used in this document. 141 SHDHT: Single-Hop Distributed Hash Table Mapping Overlay. 143 SHDHT Node: Physical nodes which compose SHDHT overlay's topology. 145 Node ID: Node identifier, which is used for maintenance. Each SHDHT 146 Node has a unique Node ID. The ring containing Node IDs indicates 147 overlay's topology. 149 Partition ID: Partition identifier, which is used for hash space 150 assignment. Partition IDs and Resource IDs share the same hash 151 space. All Partition IDs in overlay are unique. Each SHDHT Node 152 could have multiple Partition IDs. The ring containing Partition 153 IDs determines how the hash space is partitioned into segments and 154 how these segments are assigned to nodes. 156 Resource ID: Each data object stored in DHT overlay could be hashed 157 to be a unique Resource ID. In LISP-SHDHT strategy, data objects 158 are according to the EIDs. Resource IDs share the same hash space 159 with Partition IDs. As a result, SHDHT Nodes perform data objects 160 put/get/remove operations based on these IDs. 162 Node Routing Table: Routing table on SHDHT Nodes. 164 3. SHDHT Overview 166 3.1. Node ID and Partition ID 168 Most of existing DHTs use node IDs for both maintenance and hash 169 space arrangement. For example, in LISP-DHT[I-D.mathy-lisp-dht], 170 each chord node of the DHT ring has a unique k-bits identifier 171 (ChordID). Nodes perform operations such like put/get/remove based 172 on ChordIDs. Furthermore, ChordIDs are also used to associate nodes 173 with hash space segments that the nodes responsible for. 175 +--------------------+ +--------------------+ 176 |Node ID: 0x0123| |Node ID: 0x4444| 177 |Partition ID: 0x1234| +-----+ +-----+ |Partition ID: 0x8000| 178 | 0x6000| |Node1+----------+Node2| | 0x6000| 179 +--------------------+ +--+--+ +--+--+ +--------------------+ 180 | | 181 | | 182 | | 183 | | 184 +--------------------+ +--+--+ +--+--+ +--------------------+ 185 |Node ID: 0xe000| |Node3+----------+Node4| |Node ID: 0xc000| 186 |Partition ID: 0x4000| +-----+ +-----+ |Partition ID: 0xaaaa| 187 | 0xeeee| | 0xcccc| 188 +--------------------+ +--------------------+ 190 Fig.1 192 In SHDHT, two roles of maintenance and hash space arrangement are 193 separated and a new kind identifier called Partition ID is adopted. 194 As shown in Fig.1, each SHDHT node has a unique Node ID which 195 identifies the physical node and multiple Partition IDs which 196 represent hash space segments. All Partition IDs in the overlay are 197 also unique. Node IDs and Partition IDs are mapped into two ring- 198 shaped spaces respectively. The ring containing Node IDs indicates 199 the overlay's topology. The ring containing Partition IDs determines 200 how the hash space is partitioned into segments and how these 201 segments are assigned to nodes. 203 In SHDHT, each SHDHT Node stores and maintains data objects. Data 204 objects are indexed by Resource IDs which share the same hash space 205 with Partition IDs. When a SHDHT Node gets the Resource ID of a data 206 object, it could find out Partition ID of the hash space segment 207 where the data object now locates in. 209 3.2. Data Storage and Hash Assignment 211 In traditional DHTs, hash space is partitioned into segments based on 212 node IDs. As a result, data objects are always stored in their root 213 nodes, whose node IDs are "closest" to data objects' Resource IDs. 214 Replications of data objects in a particular node are always stored 215 in the preceding node or successor node of the root node. The backup 216 preceding node or successor node will automatically become the new 217 closest node if the root node leaves the overlay. 219 In SHDHT, the whole hash space is partitioned into segments based on 220 partition IDs. The root node of a data object is the node, which has 221 the closest partition ID to the data object's Resource ID. In SHDHT, 222 each node can maintain multiple hash space segments with respective 223 Partition IDs. As the preceding Partition ID or successor Partition 224 ID may be owned by the same root node. Replication of data objects 225 could still be stored in preceding node or successor node of root 226 node. 228 3.3. Node Routing Table 230 In SHDHT, each node maintains a Node Routing Table containing routing 231 information for all other SHDHT Nodes locate in the same SHDHT 232 overlay. Table I shows the Node Routing Table on SHDHT Nodes of 233 Fig.1. A Node Routing Table contains all Partition IDs and their 234 associated Node IDs and node addresses. For simplification, Node IDs 235 and Partition IDs shown in the draft are only 16-bit numbers. 237 When SHDHT Node receives a massage point to a particular Resource ID, 238 it could look up Node Routing Table and find out the Partition ID 239 which is closest to the Resource ID. Furthermore, massage could be 240 transferred to the corresponding SHDHT Node. 242 +--------------+---------+---------------+ 243 | Partition ID | Node ID | Address | 244 +--------------+---------+---------------+ 245 | 0x1234 | 0x0123 | 10.0.0.2:2000 | 246 | 0x3000 | 0x4444 | 10.0.0.3:2000 | 247 | 0x4000 | 0xe000 | 10.0.0.4:2000 | 248 | 0x6000 | 0x0123 | 10.0.0.2:2000 | 249 | 0x8000 | 0x4444 | 10.0.0.3:2000 | 250 | 0xaaaa | 0xc000 | 10.0.0.5:2000 | 251 | 0xcccc | 0xc000 | 10.0.0.5:2000 | 252 | 0xeeee | 0xe000 | 10.0.0.4:2000 | 253 +--------------+---------+---------------+ 255 TABLE I 257 4. LISP SHDHT 259 LISP SHDHT is proposed to provide "EID-to-RLOC(s)" mapping 260 information lookup service for sites running the Locator/ID 261 Separation Protocol (LISP). 263 In SHDHT, all EID-to-RLOC mapping entries are stored in SHDHT Nodes 264 as data objects. Each SHDHT Node have a RLOC address. EIDs in 265 mapping entries can be hashed as Resource IDs of data objects. All 266 SHDHT Nodes in the same SHDHT overly perform hash operation based on 267 the same hash algorithm. 269 Data objects stored in LISP SHDHT Nodes may be in the following 270 format: 272 Object (lisp) = [EID prefix, (RLOC1, priority, weight), 273 ...,RLOCn, priority, weight), TTL ] 275 4.1. SHDHT Node Operation 277 In SHDHT, each SHDHT Node plays the roles of mapping server and 278 forwarding router. When a SHDHT Node receives a control massage from 279 the LISP data plane, it will perform the following operations, 281 1. SHDHT Node extracts destination EID address from the control 282 massage. 284 2. SHDHT Node map the EID address to be Resource ID based on the 285 shared hash algorithm. 287 3. SHDHT Node look up the Node Routing Table and find out the 288 Partition ID which is closest to the Resource ID. 290 4. If the Resource ID locates in hash space segments the SHDHT Node 291 responsible for, SHDHT Node decapsulates the control massage and 292 performs proper operations according to massage type: 294 * If the message is a Map-Request, SHDHT Node first checks if 295 there's data objection, i.e. corresponding mapping entry, 296 matching the Resource ID. If there is no match, the SHDHT 297 Node returns a encapsulated negative Map-Reply. If there is 298 matched mapping entry, the SHDHT Node returns the encapsulated 299 Map-Reply. Furthermore, if the queried EID is covered by an 300 EID prefix mapping entry, SHDHT Node could choose to return 301 EID prefix mapping as response. 303 * If the message is a Map-Register, SHDHT Node extracts and 304 stores mapping information in the message. 306 5. Otherwise, SHDHT Node re-encapsulates the control massage and 307 sends it to the corresponding node based on routing information 308 in Node Routing Table. 310 4.2. ITR Operation 312 According to LISP-MS [I-D.ietf-lisp-ms], LISP ITRs use Map Resolvers 313 as proxy to send control messages, such like encapsulated Map- 314 Requests and Map-Replies. 316 In scenario of LISP SHDHT, SHDHT Nodes could also be configured as a 317 Map Resolvers for the ITRs. An ITR could send encapsulated Map- 318 Requests to a SHDHT Node directly. If the selected SHDHT Node is the 319 node who maintains the matching information, it will respond Map- 320 Replies directly. Otherwise, it will forward Map-Requests into the 321 DHT overlay, and forward Map-Replies to ITRs when it receives 322 responds from other SHDHT Nodes. 324 4.3. ETR Operation 326 According to LISP-MS [I-D.ietf-lisp-ms], LISP ETRs register mapping 327 information onto the Map Server by sending encapsulated Map-Register 328 messages. 330 In scenario of LISP SHDHT, SHDHT Nodes play the role of Map Server. 331 Thus, encapsulated Map-Register messages should be sent to 332 corresponding SHDHT Nodes. As a result, ETRs could send Map-Register 333 messages to a nearest SHDHT Node who will forward messages to the 334 corresponding SHDHT Nodes who should take on the responsibility. 336 4.4. Encapsulated Message Format 338 An Encapsulated Control Message (ECM) defined in[I-D.ietf-lisp] is 339 used to encapsulate control packets sent between ITRs/ETRs and 340 mapping database system. When ITRs/ETRs choose a SHDHT Node as proxy 341 to send control messages, they could use encapsulated message format 342 defined in , as shown in Fig.2. 344 0 1 2 3 345 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 346 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 347 / | IPv4 or IPv6 Header | 348 OH | (uses RLOC addresses) | 349 \ | | 350 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 351 / | Source Port = xxxx | Dest Port = 4342 | 352 UDP +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 353 \ | UDP Length | UDP Checksum | 354 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 355 LH |Type=8 |S| Reserved | 356 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 357 / | IPv4 or IPv6 Header | 358 IH | (uses RLOC or EID addresses) | 359 \ | | 360 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 361 / | Source Port = xxxx | Dest Port = yyyy | 362 UDP +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 363 \ | UDP Length | UDP Checksum | 364 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 365 LCM | LISP Control Message | 366 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 368 Fig.2 Encapsulated Control Message Format 370 4.4.1. Encapsulated Map Request 372 Suppose that the selected SHDHT Node of an ITR is Node1. 374 When the ITR sends Encapsulated Map-Requests to Node1, source address 375 and destination address in message OH (Outside Header) should be RLOC 376 addresses of ITR and Node1 respectively. 378 In the IH (Inside Header), source address is still RLOC address of 379 Node1, while destination address is the inquired EID address. 381 Consider Node1 is a configured Map Resolver, and then the 382 configuration of Encapsulated Map-Request message has not been 383 changed. 385 4.4.2. Encapsulated Map Register 387 Suppose an ETR chooses a SHDHT Node (Node2) to send encapsulated Map- 388 Register. 390 As in traditional mapping overlay design, ETR anchors the 391 corresponding map server, and send Map-Register message to map 392 server. As a result, the destination address in both OH and IH of 393 encapsulated Map-Register message should be RLOC address of map 394 server. 396 However, in LISP SHDHT, there are some modifications. 398 When the ETR send Encapsulated Map-Register to Node2, the source 399 address in both OH and IH of message is RLOC address of ETR. The 400 destination address in OH should be RLOC address of Node2, while 401 destination address in IH should be the EID address according to the 402 registered mapping entry. Furthermore, if the registered mapping 403 entry is an EID prefix mapping entry, ETR could choose the highest 404 EID address of the prefix as destination address. 406 5. Mobility Considerations 408 As specified in section 4.2 and 4.3, ITR/ETR could choose a nearest 409 LISP SHDHT Node as proxy to send control messages. 411 Based on LISP SHDHT, when roaming events occurs, the roamed LISP 412 sites or LISP MNs are no longer need to anchor pre-configured map- 413 servers. 415 6. Security Considerations 417 TBD 419 7. IANA Considerations 421 This document makes no requests to IANA. 423 8. References 425 8.1. Normative References 427 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 428 Requirement Levels", March 1997. 430 8.2. Informational References 432 [I-D.fuller-lisp-ddt] 433 Fuller, V., Lewis, D., and V. Ermagan, "LISP Delegated 434 Database Tree", March 2012. 436 [I-D.ietf-lisp] 437 Farinacci, D., Fuller, V., Meyer, D., and D. Lewis, 438 "Locator/ID Separation Protocol (LISP)", May 2012. 440 [I-D.ietf-lisp-alt] 441 Fuller, V., Farinacci, D., Meyer, D., and D. Lewis, "LISP 442 Alternative Topology (LISP+ALT)", December 2011. 444 [I-D.ietf-lisp-ms] 445 Fuller, V. and D. Farinacci, "LISP Map Server Interface", 446 March 2012. 448 [I-D.lear-lisp-nerd] 449 Lear, E., "NERD: A Not-so-novel EID to RLOC Database", 450 April 2012. 452 [I-D.mathy-lisp-dht] 453 Mathy, L., Iannone, L., and O. Bonaventure, "LISP-DHT: 454 Towards a DHT to map identifiers onto locators", 455 February 2008. 457 [I-D.meyer-lisp-mn] 458 Farinacci, D., Lewis, D., Meyer, D., and C. White, "LISP 459 Mobile Node", April 2012. 461 Authors' Addresses 463 Li Cheng 464 ZTE Corporation 465 R&D Building 1, Zijinghua Road No.68 466 Nanjing, Yuhuatai District 210012 467 P.R.China 469 Email: cheng.li2@zte.com.cn 471 Mo Sun 472 ZTE Corporation 473 R&D Building 1, Zijinghua Road No.68 474 Nanjing, Yuhuatai District 210012 475 P.R.China 477 Email: sun.mo@zte.com.cn