LISP Working Group L. Cheng Internet-Draft M. Sun Intended status: Standards Track ZTE Corporation Expires: January 16, 2014 July 15, 2013 draft-cheng-lisp-shdht-04 LISP Single-Hop DHT Mapping Overlay Abstract This draft specifies the LISP Single-Hop Distributed Hash Table Mapping Database (LISP-SHDHT), a distributed mapping database which consists of a set of SHDHT Nodes to provide mappings from LISP Endpoint Identifiers (EIDs) to Routing Locators (RLOCs). EID namespace is dynamically distributed among SHDHT Nodes based on DHT Hash algorithm. Each SHDHT Node is configured with one or more hash spaces which contain multiple EID-prefixes along with RLOCs of corresponding Map Servers. Status of This Memo This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF). Note that other groups may also distribute working documents as Internet-Drafts. The list of current Internet- Drafts is at http://datatracker.ietf.org/drafts/current/. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress." This Internet-Draft will expire on January 16, 2014. Copyright Notice Copyright (c) 2013 IETF Trust and the persons identified as the document authors. All rights reserved. This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (http://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must Cheng & Sun Expires January 16, 2014 [Page 1] Internet-Draft LISP Single-Hop DHT Mapping Overlay July 2013 include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License. Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2 2. Definition of Terms . . . . . . . . . . . . . . . . . . . . . 5 3. SHDHT Overview . . . . . . . . . . . . . . . . . . . . . . . 7 3.1. Node ID and Partition ID . . . . . . . . . . . . . . . . 7 3.2. Data Storage and Hash Assignment . . . . . . . . . . . . 8 3.3. Node Routing Table . . . . . . . . . . . . . . . . . . . 9 4. LISP SHDHT . . . . . . . . . . . . . . . . . . . . . . . . . 10 4.1. ITR Operation . . . . . . . . . . . . . . . . . . . . . . 10 4.2. ETR Operation . . . . . . . . . . . . . . . . . . . . . . 11 4.3. SHDHT Map Server Operation . . . . . . . . . . . . . . . 11 4.4. SHDHT Map Resolver Operation . . . . . . . . . . . . . . 12 4.4.1. SHDHT Map Resolver Operation under SHDHT Forward Mode 12 4.4.2. SHDHT Map Resolver Operation under Recursive Lookup Mode . . . . . . . . . . . . . . . . . . . . . . . . 12 4.5. SHDHT Nodes Operation . . . . . . . . . . . . . . . . . . 13 4.6. EID prefixes Report onto LISP-SHDHT . . . . . . . . . . . 13 5. Domain LISP SHDHT Deployment . . . . . . . . . . . . . . . . 16 5.1. SHDHT Border Node . . . . . . . . . . . . . . . . . . . 16 5.2. EIDs/EID Prefixes Report onto Domain SHDHT Overlay . . . 17 5.3. Mapping Request Lookup onto Domain SHDHT Overlay . . . . 17 6. Security Considerations . . . . . . . . . . . . . . . . . . . 20 7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 21 8. References . . . . . . . . . . . . . . . . . . . . . . . . . 22 8.1. Normative References . . . . . . . . . . . . . . . . . . 22 8.2. Informational References . . . . . . . . . . . . . . . . 22 Appendix A. Acknowledgments . . . . . . . . . . . . . . . . . . 22 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 22 1. Introduction Locator/ID Separation Protocol (LISP) [RFC6830] specifies an architecture and mechanism for replacing the address currently used by IP with two separate name spaces: Endpoint IDs (EIDs), used within LISP sites, and Routing Locators (RLOCs), used on transit networks that make up the Internet infrastructure. To achieve this separation, LISP defines protocol mechanisms for mapping from EIDs to RLOCs. As a result, an efficient database is needed to store and propagate those mappings globally. Several such mapping databases have been proposed, among them: LISP-NERD [I-D.lear-lisp-nerd], LISP- ALT[RFC6836], LISP-DDT[I-ietf-lisp-ddt], and LISP-DHT [LISP-DHT]. Cheng & Sun Expires January 16, 2014 [Page 2] Internet-Draft LISP Single-Hop DHT Mapping Overlay July 2013 According to databases such like LISP-ALT [RFC6836] and LISP-DDT [I-ietf-lisp-ddt], architectures of these mapping databases are based on announcement/delegation of hierarchically-delegated segments of EID namespace (i.e., prefixes). Therefore, based on these architectures, when a roaming event occurs and a LISP site or a LISP MN receives new RLOCs, the site or MN has to anchor pre-configured map-server to register its new mapping information no matter where the site or MN currently locates, just in order to protect EID prefixes announced aggregately in the database [I-D.meyer-lisp-mn]. As a DHT strategy based mapping database, LISP-DHT [LISP-DHT] exhibits several interesting properties, such as self-configuration, self-maintenance, scalability and robustness that are clearly desirable for a EID-to-RLOC resolution service. However, this database is based on multi-hop Chord DHT. On one hand, inquiries of mapping information in this case need to pass through iterative multi-hop lookup steps which will cause relatively large delay time. On the other hand, load balance between Chord nodes is another essential problem need to be solved. This draft specifies a LISP Single-Hop Distributed Hash Table Mapping Overlay (LISP-SHDHT) which provides mapping information lookup service for sites running LISP. Main characters of this strategy is that, 1. Each SHDHT Node maintains routing information for all other SHDHT Nodes. Thus, messages interaction between SHDHT Nodes in the same SHDHT overlay just need one hop. 2. Traditionally, Node IDs are used to identify DHT nodes and represent hash space arrangement on DHT nodes. In SHDHT strategy, the two roles are separated. Partition IDs are adopted for hash space arrangement and a build-in load balancing solution is designed. This draft specifies the outline of SHDHT and the basic application of LISP SHDHT. In actual deployment of LISP SHDHT, mapping database could be maintained by multiple service providers and could be deployed as collaborative combination of multiple Domain LISP SHDHTs. Details about Domain LISP SHDHT Deployment are introduced in Section 5. In main context of this draft, SHDHT Mapping database is proposed according to structure requirements of LISP-MS [RFC6833]. This SHDHT strategy provides services for LISP Sites mapping lookup. In Appendix A, a special SHDHT strategy for LISP-MN [I-D.meyer-lisp-mn] scenario is proposed. This SHDHT strategy is not completely match structure requirements of LISP-MS. However, it could provide better Cheng & Sun Expires January 16, 2014 [Page 3] Internet-Draft LISP Single-Hop DHT Mapping Overlay July 2013 service for LISP-MN scenario, where LISP-MN need not to anchor pre- configured Map Server and could update its mapping information as soon as possible when it roams to a new location. Cheng & Sun Expires January 16, 2014 [Page 4] Internet-Draft LISP Single-Hop DHT Mapping Overlay July 2013 2. Definition of Terms This draft uses terms defined in [RFC6830]. This section defines some new terms used in this document. SHDHT: Single-Hop Distributed Hash Table Mapping Overlay. SHDHT Node: Physical nodes which compose SHDHT overlay's topology. Each SHDHT Node has a unique Node ID and maintains multiple hash space segments which labeled by Partition IDs. Each SHDHT Node maintains a Node Routing Table of local SHDHT Mapping Overlay. SHDHT Nodes locates in the same Mapping Overlay implement hash operation based on the same hash algorithm. SHDHT Nodes hash data object to be a unique Resource ID, and perform put/get/move operations based on the Resource IDs. Node ID: Node identifier, which is used for maintenance. Each SHDHT Node has a unique Node ID. The ring containing Node IDs indicates overlay's topology. Partition ID: Partition identifier, which is used for hash space assignment. Partition IDs and Resource IDs share the same hash space. All Partition IDs in overlay are unique. Each SHDHT Node could have multiple Partition IDs. The ring containing Partition IDs determines how the hash space is partitioned into segments and how these segments are assigned to nodes. Resource ID: Each data object stored in DHT overlay could be hashed to be a unique Resource ID. In LISP-SHDHT strategy, data objects correspond to the EIDs. Resource IDs share the same hash space with Partition IDs. As a result, SHDHT Nodes perform data objects put/get/remove operations based on these IDs. Node Routing Table: Routing table of a SHDHT Mapping Overlay which contains all SHDHT Nodes information of this overly, including Node IDs, Partition IDs and Node IP addresses, etc. Each SHDHT Node of this overly will maintain the Routing Table. SHDHT Map Resolver: A SHDHT Node that also implements Map Resolver functionality (accept Map-Requests, and forward them to corresponding SHDHT Map Servers based on information get from SHDHT mapping database or forward them to corresponding SHDHT Map Servers through SHDHT Nodes, which corresponds to different operation modes of the SHDHT Mapping Database.). Report Message: Kind of message sent by Map Server to SHDHT Nodes to publish the EIDs/EID prefix information in charge of Map Server onto the LISP-SHDHT mapping overlay. Cheng & Sun Expires January 16, 2014 [Page 5] Internet-Draft LISP Single-Hop DHT Mapping Overlay July 2013 SHDHT Border Node: SHDHT Border Node locates on the border of a Domain SHDHT Overlay. Each SHDHT Border Node maintains an Inter- Domain Routing Table. SHDHT Border Nodes are used to flood cross domain routing and forward cross domain packets. Inter-Domain Routing Table: A routing table maintained on a SHDHT Border Node. This routing table contains information of other Domain SHDHT Overlays, such like EID prefixes other domain overlays maintain, IP addresses and ports information of other overlay's Border Nodes. Cheng & Sun Expires January 16, 2014 [Page 6] Internet-Draft LISP Single-Hop DHT Mapping Overlay July 2013 3. SHDHT Overview 3.1. Node ID and Partition ID Most of existing DHTs use node IDs for both maintenance and hash space arrangement. For example, in LISP-DHT[LISP-DHT], each chord node of the DHT ring has a unique k-bits identifier (ChordID). Nodes perform operations such like put/get/remove based on ChordIDs. Furthermore, ChordIDs are also used to associate nodes with hash space segments that the nodes responsible for. In SHDHT, two roles of maintenance and hash space arrangement are separated and a new kind identifier called Partition ID is adopted. Each SHDHT node has a unique Node ID which identifies the physical node and multiple Partition IDs which represent hash space segments. All Partition IDs in the overlay are also unique. Node IDs and Partition IDs are mapped into two ring-shaped spaces respectively. The ring containing Node IDs indicates the overlay's topology. The ring containing Partition IDs determines how the hash space is partitioned into segments and how these segments are assigned to nodes. It is noteworthy that SHDHT Nodes could determine number of Partition IDs on them separately and could generate Partition IDs randomly just need to make sure that the generated Partition IDs will not conflict with existing Partition IDs on the SHDHT plane. +--------------------+ +--------------------+ |Node ID: 0x0123| |Node ID: 0x4444| |Partition ID: 0x1234| +-----+ +-----+ |Partition ID: 0x9000| | 0x7000| |Node1+----------+Node2| | 0x3234| +--------------------+ +--+--+ +--+--+ +--------------------+ | | | | | | | | +--------------------+ +--+--+ +--+--+ +--------------------+ |Node ID: 0xe000| |Node3+----------+Node4| |Node ID: 0xc000| |Partition ID: 0x5000| +-----+ +-----+ |Partition ID: 0xaaaa| | 0xeeee| | 0xcccc| +--------------------+ +--------------------+ Fig.1 SHDHT Deployment Example As shown in Fig.1 is an example of SHDHT. This SHDHT overlay is consist of four SHDHT NODEs each has a unique Node ID and maintains two Partition IDs. According to this deployment, hash space is partitioned to be eight segments each is indexed by a Partition ID. From Fig. 1, it could be observed that hash space segments are not required to be partitioned equally. As SHDHT Nodes could generate Cheng & Sun Expires January 16, 2014 [Page 7] Internet-Draft LISP Single-Hop DHT Mapping Overlay July 2013 Partition IDs separately, when a SHDHT Node gets all hash segments assignment information of other SHDHT Nodes, it will be able to implement the load balance of SHDHT overlay by generate proper Partition IDs. In SHDHT, each SHDHT Node stores and maintains data objects. Data objects are indexed by Resource IDs which share the same hash space with Partition IDs and will locate in the hash space segments whose Partition IDs are closest to their Resource IDs. For example, for a data object whose Resource ID is 0x8213, the Resource ID locates between Partition ID 0x7000 and Partition ID 0x9000. As Partition ID 0x9000 is closer to Resource ID 0x8213, the data object will be stored and maintained on Node2 who is assigned with the hash space segment indexed by Partition ID 0x9000. 3.2. Data Storage and Hash Assignment In traditional DHTs, hash space is partitioned into segments based on node IDs. As a result, data objects are always stored in their root nodes, whose node IDs are "closest" to data objects' Resource IDs. What does "closest" means? Suppose we have three consecutive Partition IDs a, b and c which are the only Partition IDs in SHDHT for our example, then the range of each hash space segment is defined as follow: Partition ID a: [id(a)-0.5*d(c,a); id(a)+0.5*d(a,b)) Partition ID b: [id(b)-0.5*d(a,b); id(b)+0.5*d(b,c)) Partition ID c: [id(c)-0.5*d(b,c); id(c)+0.5*d(c,a)) with functions id(x): value of Partition ID x in hash space d(x,y): distance between Partition ID x and y in hash space Replications of data objects in a particular node are always stored in the preceding node or successor node of the root node. The backup preceding node or successor node will automatically become the new closest node if the root node leaves the overlay. In SHDHT, the whole hash space is partitioned into segments based on partition IDs. The root node of a data object is the node, which has the closest partition ID to the data object's Resource ID. In SHDHT, each node can maintain multiple hash space segments with respective Cheng & Sun Expires January 16, 2014 [Page 8] Internet-Draft LISP Single-Hop DHT Mapping Overlay July 2013 Partition IDs. As the preceding Partition ID or successor Partition ID may be owned by the same root node. Replication of data objects could still be stored in preceding node or successor node of root node. 3.3. Node Routing Table In SHDHT, each node maintains a Node Routing Table containing routing information of all other SHDHT Nodes locate in the same SHDHT overlay. Table I shows the Node Routing Table on SHDHT Nodes of Fig.1. A Node Routing Table contains all Partition IDs and their associated Node IDs and node addresses. For simplification, Node IDs and Partition IDs shown in the draft are only 16-bit numbers. When SHDHT Node receives a message points to a particular Resource ID, it could look up Node Routing Table and find out the Partition ID which is closest to the Resource ID. Furthermore, message could be transferred to the corresponding SHDHT Node. +--------------+---------+---------------+ | Partition ID | Node ID | Address:Port | +--------------+---------+---------------+ | 0x1234 | 0x0123 | 10.0.0.2:2000 | | 0x3234 | 0x4444 | 10.0.0.3:2000 | | 0x5000 | 0xe000 | 10.0.0.4:2000 | | 0x7000 | 0x0123 | 10.0.0.2:2000 | | 0x9000 | 0x4444 | 10.0.0.3:2000 | | 0xaaaa | 0xc000 | 10.0.0.5:2000 | | 0xcccc | 0xc000 | 10.0.0.5:2000 | | 0xeeee | 0xe000 | 10.0.0.4:2000 | +--------------+---------+---------------+ TABLE I SHDHT Node Routing Table For example, if Node 1 (ID: 0x1234) in Fig.1 needs to implement put/ get/remove operations for a data object with Resource ID 0x8213. Node 1 first looks up its Node Routing Table and finds out that the closest Partition ID corresponding to this Resource ID is 0x9000. Then Node 1 will send put/get/remove request to the node owns the Partition ID, in Fig.1 is Node2, whose Node ID is 0x4444 and address is 10.0.0.3:2000. Cheng & Sun Expires January 16, 2014 [Page 9] Internet-Draft LISP Single-Hop DHT Mapping Overlay July 2013 4. LISP SHDHT LISP SHDHT is proposed to provide "EID-to-RLOC(s)" mapping information lookup service for sites running the Locator/ID Separation Protocol (LISP). As shown in Fig.2, LISP SHDHT is consists of SHDHT Nodes in which some nodes play roles of Map Resolver. And in the draft, term "SHDHT-MR" is adopted to identify these nodes. +--------------------+ |Node ID: 0x4444| +-----+ +-----+ |Partition ID: 0x9000| |Node1+---------+Node2| | 0x3234| +--+--+ +--+--+ +--------------------+ | | | SHDHT | | | +--+--+ +--+--+ +-----+ +-------+ M R +---------+Node4+-------+ M S | | +-----+ +-----+ +--+--+ | | +--+--+ +--+--+ | ITR | | ETR | +-----+ +-----+ Fig.2 LISP-SHDHT Deployment Example Map Server publishes EIDs/EID prefixes information it responsible to onto SHDHT Mapping overlay. All EIDs/EID prefixes entries are stored in SHDHT Nodes as data objects. EIDs/EID prefixes in mapping entries can be hashed as Resource IDs of data objects. All SHDHT Nodes in the same SHDHT overlay perform hash operation based on the same hash algorithm. In this draft, LISP-SHDHT can run in two distinct modes: i) SHDHT Forward Mode and ii) Recursive Lookup Mode. 4.1. ITR Operation According to LISP-MS [RFC6833], LISP ITRs use Map Resolvers as proxy to send control messages, such like encapsulated Map-Requests and Map-Replies. In Scenario of LISP SHDHT, an ITR send Map-Requests directly to the SHDHT Node which is selected to play roles of SHDHT Map Resolver for that ITR. Cheng & Sun Expires January 16, 2014 [Page 10] Internet-Draft LISP Single-Hop DHT Mapping Overlay July 2013 4.2. ETR Operation LISP ETR plays the same role as defined in LISP-MS [RFC6833]; it registers mapping information onto the Map Server by sending Map- Register messages. 4.3. SHDHT Map Server Operation When Map Server receives Map Request messages, it forwards the messages to ETRs or send Map-Reply messages directly based on M-bits of ETRs' Map Registers. That's to say, Map Server performs the same operation as defined in LISP-MS[RFC6833] . Extended in LISP SHDHT, Map Server needs to publish EIDs/EID prefixes information onto the LISP-SHDHT mapping overlay. For example, as shown in figure 2, when a Map Server needs to publish EIDs information such like EID "1.1.1.1" onto LISP-SHDHT, following operations will be performed. 1. Map Server sends a report message to the nearest SHDHT Node, i.e. Node 4. Map Server contains the information of EID "1.1.1.1" in the report message, along with Map Server's routable RLOCs. Report message may not be a kind of new defined message. For example, Map Server could advertise EID information onto SHDHT mapping database based on BGP protocol. 2. When Node 4 receives the report message, it extracts EID information from the message, i.e. EID "1.1.1.1". Node 4 then hashes the report EID to be a Resource ID. 3. Suppose Node 4 hash EID "1.1.1.1" to be Resource ID 0x8956. Then it checks the Nodes Routing Table to find out which Node maintains the hash space whose Partition ID matches the Resource ID. In this example, the match Partition ID is 0x9000, and the corresponding hash space is maintained by Node 2. 4. Node 4 forwards the report message to Node 2. Node 2 stores the (key, value) pair, where key is the Resource ID 0x8956, and value contains reported EID "1.1.1.1" along with corresponding Map Server's RLOCs. Other SHDHT Nodes now could contact Node2 to get which Map Server is responsible to the EID "1.1.1.1". Cheng & Sun Expires January 16, 2014 [Page 11] Internet-Draft LISP Single-Hop DHT Mapping Overlay July 2013 Note: In previous example, we suppose that Map-Server reports an EID address onto LISP-SHDHT. In practical deployment, Map Server reports EID prefixes at most time. Details about EID prefix report will be illustrated in Section 4.6. 4.4. SHDHT Map Resolver Operation As previous mentioned, LISP-SHDHT can run in two distinct modes: i) SHDHT Forward Mode and ii) Recursive Lookup Mode. As shown in Fig.2, suppose SHDHT Map Resolver receives a Map-Request message target at EID 1.1.1.1. SHDHT Map Resolver operations under two different modes are illustrated in following sections. 4.4.1. SHDHT Map Resolver Operation under SHDHT Forward Mode Under SHDHT Forward Mode, SHDHT Map Resolver performs the following operaion. 1. SHDHT Map Resolver extracts destination EID address "1.1.1.1" from the Map-Request message. 2. SHDHT Map Resolver hashes the EID address to be Resource ID 0x8956 based on the shared hash algorithm. 3. SHDHT Map Resolver looks up Node Routing Table and finds out the Partition ID 0x9000 which matches the Resource ID. 4. SHDHT Map Resolver forwards Map-Request message to the corresponding SHDHT Node 2 who maintains the hash space labeled by matched Partition ID 0x9000. 4.4.2. SHDHT Map Resolver Operation under Recursive Lookup Mode Under Recursive Lookup Mode, SHDHT Map Resolver performs the following operation. 1. SHDHT Map Resolver receives the Map-Request message and stores it in local catch. 2. SHDHT Map Resolver hash destination EID of Map-Request to be Resource ID 0x8956. 3. SHDHT Map Resolver looks up Node Routing Table and finds out that Node 2 maintains the corresponding hash space and stores the data object indexed by 0x8956. Cheng & Sun Expires January 16, 2014 [Page 12] Internet-Draft LISP Single-Hop DHT Mapping Overlay July 2013 4. SHDHT Map Resolver query Node 2 to get data object indexed by 0x8956, i.e. get EID information and RLOCs of the Map Server who maintains the destination EID. 5. SHDHT Map Resolver forwards Map-Request message to corresponding Map Server based on data object. Under Recursive Lookup Mode, SHDHT Map Resolve could catch information of the Map Server, including EID prefix Map Server responsible for and Map Server's RLOCs. When receives other Map Requests whose destination EIDs covered by Map Server's EID prefix, Map Resolver could forward Map Requests directly to Map Server. 4.5. SHDHT Nodes Operation As specified in Section 4.3, when SHDHT Nodes receive a report message, it will hash the report EID/EID prefix to be Resource ID, and check which Node should store the data object. If itself is the responsible Node, it will store the (key, value) pair, otherwise, it forward report message to corresponding Node. As specified in Section 4.4.1, under SHDHT Forward Mode, when a SHDHT Node receives a Map-Request message from a Map Resolver, it hashes the requested EID to be a Resource ID to get the data object stored in its hash space. Then SHDHT Node forwards the Map-Request to Map Server based on data object information. As specified in Section 4.4.2, under Recursive Lookup Mode, when a SHDHT Node receives a query message from Map Resolver, it replies with the data object Map Resolver requested. 4.6. EID prefixes Report onto LISP-SHDHT In LISP-SHDHT, Map Server always report EID prefixes onto the SHDHT Mapping overlay. However, Map-Request message always targets at a specific EID address. How to hash the requested EID and the EID prefix covered this EID to be the same Resource ID? Each LISP-SHDHT Mapping overlay could configure a "Hash Bit" to solve this problem. As shown in Fig.3, suppose the LISP-SHDHT Mapping overlay configures the "Hash Bit" to be 16 bits. Cheng & Sun Expires January 16, 2014 [Page 13] Internet-Draft LISP Single-Hop DHT Mapping Overlay July 2013 +--------------------+ +--------------------+ |Node ID: 0x0123| |Node ID: 0x4444| |Partition ID: 0x1234| +-----+ +-----+ |Partition ID: 0x9000| | 0x7000| |Node1+---------+Node2| | 0x3234| +--------------------+ +--+--+ +--+--+ +--------------------+ | | | SHDHT | | Hash Bit=16 | | | 1.1.1/24 +--+--+ +--+--+ +-----+ +------+ Map-Request +-------+ M R +---------+Node4+----+ MS1 +----+ ETR1 | 1.1.1.1 | +-----+ +--+--+ +-----+ +------+ 2.0.0.1 | | +--+--+ | +-----+ +------+ | ITR | +-------+ MS2 +----+ ETR2 | +-----+ +-----+ +------+ 2.0/15 Fig.3 EID Prefix Report Example Example 1: MS1 reports EID prefix 1.1.1/24 onto the LISP-SHDHT. 1. When Node4 receives the report message from MS1, it extracts the EID prefix 1.1.1/24. 2. Node4 hashes the EID prefix to be Resource ID based on Hash Bit. In this case, Hash Bit is 16 bits, as a result Node4 hashes the / 16 prefix of reported EID prefix. That's to say, Node4 hashes 1.1/16 to be a Resource ID, suppose to be 0x8560. 3. Node 4 checks Node Routing Table and forwards the report message to Node 2 who maintains the corresponding hash space with Partition ID 0x9000. In this example, when another Map Server advertises EID prefix such like 1.1.2/24, this prefix will also be hashed to be Resource ID 0x8560 and the report message will be forwarded to Node 2. Node 2 maintains (key, value) pair, where key is 0x8560 and value contains all EIDs/EID prefixes information covered by 1.1/16. Example 2: MS2 reports EID prefix 2.0/15 onto the LISP-SHDHT. 1. When Node4 receives the report message from MS1, it extracts the EID prefix 2.0/15. 2. Node4 hashes the EID prefix to be Resource ID based on Hash Bit. In this case, Hash Bit is 16 bits, Node4 first splits the EID Cheng & Sun Expires January 16, 2014 [Page 14] Internet-Draft LISP Single-Hop DHT Mapping Overlay July 2013 prefix 2.0/15 to be two 16 bits sub-prefixes, 2.0/16 and 2.1/16. Suppose Node 4 hashes prefix 2.0/16 to be Resource ID 0x1210 and hashes prefix 2.1/16 to be Resource ID 0x3200. 3. As Shown in Fig. 3, data objects with Resource ID 0x1210 and 0x3200 should be stored on Node 1 and Node 2 separately. Node 4 will copy the report message and forward report message both to Node 1 and Node 2. In this example, Node 1 and Node 2 maintains (key, value) pairs with different keys (0x1210 and 0x3200), but the value both contain the same EID prefix 2.0/15. In practical deployment, SHDHT service providers could configure proper Hash Bits, in order to avoid the scenario which needs to split a shorter EID prefix to be multiple longer prefixes. Example 3: ITR sends Map Requests onto LISP-SHDHT. 1. When ITR sends a Map-Request target at EID 1.1.1.1 as shown in Fig.3, SHDHT Map Resolver hashes the EID based on Hash Bit, i.e. SHDHT Map Resolver hashes EID prefix 1.1/16 to get the Resource ID. SHDHT Map Resolver judges the corresponding data object is stored on Node 2 (according to Example 1), then SHDHT Map Resolver could forward the Map-Request to Node 2 (based on SHDHT Forward Mode) or get information about the best matched EID prefix 1.1.1/24 from Node 2 (based on Recursive Lookup Mode). 2. When ITR sends a Map-Request target at EID 2.0.0.1, SHDHT Map Resolver hashes EID prefix 2.0/16 to get the Resource ID. SHDHT Map Resolver judges the corresponding data object is stored on Node 1 (according to Example 2), then SHDHT Map Resolver could forward the Map-Request to Node 1 (based on SHDHT Forward Mode) or get information about the best matched EID prefix 2.0/15 from Node 1 (based on Recursive Lookup Mode). Cheng & Sun Expires January 16, 2014 [Page 15] Internet-Draft LISP Single-Hop DHT Mapping Overlay July 2013 5. Domain LISP SHDHT Deployment LISP is a global architecture. In order to make LISP SHDHT meets requirements of LISP mapping database better, LISP SHDHT should perform better scalability and distribution attributes. Especially in practical deployment, LISP mapping database may be operated by different ISPs, when a new mapping service provider join or leave the mapping database, all other providers should not be influenced to be re-assigned. In practical deployment, LISP SHDHT mapping overlay could be consist of multiple Domain SHDHT overlays which are operated by different mapping service providers. These Domain SHDHT overlays communicate through SHDHT Border Nodes of each other. As shown in Fig.4, there are two Domain LISP SHDHT Overlays which communicate through BN1 (Border Node1) and BN2. In domain LISP SHDHT deployment, different domain overlays maintain EID-to-RLOC mapping information covered by different EID prefixes. As in example of Fig.4, Domain 1 maintains mapping information according to EID prefix 12.0.0.0/8, and Domain 2 maintains mapping information covered by EID prefix 16.0.0.0/8. Furthermore, different Domain Overlay could configure their Hash Bits separately. +------+ +-----+ +-----+ +-----+ +-----+ +------+ | ITR1 +--+ MR1 +-------+Node2| |Node4+-------+ MR2 +---+ ITR2 | +------+ +--+--+ +--+--+ +--+--+ +--+--+ +------+ | Domain | | Domain | | Overlay 1 | | Overlay 2 | | Hash Bit 16 | | Hash Bit 14 | | 12.0.0.0\8 | | 16.0.0.0\8 | +-----+ +--+--+ +--+--+ +--+--+ +--+--+ +-----+ | MS1 +--+Node3+-------+ BN1 |<--->| BN2 +-------+Node6+---+ MS2 | +-----+ +-----+ +-----+ +-----+ +-----+ +-----+ * BN: SHDHT Border Node * MR: SHDHT Map Resolver * MS: Map Server Fig.4 Domain SHDHT Deployment Example 5.1. SHDHT Border Node Each Domain SHDHT Overlay has one or more Border Nodes which are not only perform like normal SHDHT Nodes, but also be used to flood cross domain routing and forward the cross domain packets. Cheng & Sun Expires January 16, 2014 [Page 16] Internet-Draft LISP Single-Hop DHT Mapping Overlay July 2013 Each SHDHT Border Node maintains an Inter-Domain Routing Table, which contains information of all other domain overlays, such like EID prefixes other domain overlays maintain, IP addresses and ports information of other overlays' Border Nodes. At the beginning, Inter-Domain Routing Table could be configured on SHDHT Border Nodes. Then, a SHDHT Border Node will flood cross domain routing periodically to trigger other Border Nodes update their Inter-Domain Routing Tables. 5.2. EIDs/EID Prefixes Report onto Domain SHDHT Overlay All SHDHT Nodes of a Domain SHDHT Overlay must be noticed the EID prefixes that local domain overlay responsible for. When a SHDHT Node of a domain overlay receives a report message, it checks if the registered EIDs/EID prefixes are covered by local domain overlay's EID prefixes. If local domain overlay is responsible for reported EIDs/EID prefixes, SHDHT Node who receives report message will process the message as procedures listed in Section 4.3 and 4.6 Otherwise, if local domain overlay is not responsible for reported EIDs/EID prefixes, SHDHT Node who receives report message will forward it directly to local domain overlay's Border Nodes. Then, Border Nodes will forward the message to corresponding domain overlay based on the Inter-Domain Routing Table. Suppose in Fig.4, MS2 reports EID prefix 12.2.0/24 to Node 6 of Domain 2. 1. Node6 extracts the EID prefix from report message and finds that the reported EID prefix is 12.2.0/24. 2. Node6 determines that EID prefix 12.2.0/24 is not covered by Domain 2's prefix 16.0.0.0/8. 3. Node6 forwards the report message to BN2. 4. BN2 looks up Inter-Domain Routing Table to find that Domain 1 is responsible for EID prefix 12.2.0/24. BN2 forwards report message to Domain 1's Border Node (BN1). 5. BN1 processes the report message based on procedures introduced in Section 4.3 and 4.6. 5.3. Mapping Request Lookup onto Domain SHDHT Overlay Cheng & Sun Expires January 16, 2014 [Page 17] Internet-Draft LISP Single-Hop DHT Mapping Overlay July 2013 When SHDHT Map Resolver receives a Map-Request message, it checks if the requested EID is covered by local domain overlay's EID prefixes, i.e. if the requested mapping entry is stored on local domain overlay. If local domain overlay is responsible for requested EID, SHDHT Map Resolver processes the message based on procedures introduced in Section 4.4 and 4.6. Otherwise, if the requested EID entry is not stored on local domain overlay, under SHDHT Forward Mode, SHDHT Map Resolver directly forwards the Map-Request to Border Nodes. Border Nodes of local domain overlay then forwards it to corresponding domain overlay based on Inter-Domain Routing Table. Suppose in Fig.4, ITR2 sends a Map-Request message to SHDHT MR 2 of Domain 2 to get mapping information of EID 12.2.0.1. 1. SHDHT MR2 extracts requested EID from the Map-Request message. 2. SHDHT MR2 determines that requested EID 12.2.0.1 is not covered by Domain 2's prefix 16.0.0.0/8. 3. SHDHT MR2 forwards the Map-Request message to BN2. 4. BN2 extracts requested EID and looks for Inter-Domain Routing Table to find corresponding domain overlay of EID 12.2.0.1. 5. BN2 finds out Domain 1 is responsible for EID 12.2.0.1. BN2 forwards Map-Request message to Domain 1's Border Node (BN1). 6. BN1 processes the Map-Request message based on procedures introduced in Section 4.4 and 4.6. If the requested EID entry is not stored on local domain overlay, under Recursive Lookup Mode, SHDHT Map Resolver catch the Map-Request message, and send query message to Border Nodes. Border Nodes of local domain overlay query Border Nodes of the corresponding domain overlay responsible for requested EID entry to get related information. Suppose in Fig.4, ITR2 sends Map-Request message to SHDHT MR 2 to get mapping information of 12.2.0.1. 1. SHDHT MR2 determines the requested EID 12.2.0.1 is not covered by Domain 2's prefix 16.0.0.0/8. Cheng & Sun Expires January 16, 2014 [Page 18] Internet-Draft LISP Single-Hop DHT Mapping Overlay July 2013 2. SHDHT MR2 catches the Map-Request message and sends a query message for EID 12.2.0.1 to BN2. 3. BN2 finds out Domain 1 is responsible for the requested EID. BN2 sends query message to BN1. 4. BN1 hashes 12.2/16 to be Resource ID to get which SHDHT Node in Domain 1 now maintains information of EIDs covered by EID prefix 12.2/16. 5. Suppose the responsible Node in Domain 1 is Node 2. Node 2 maintains information of EID prefix 12.2.0/24 along with MS2's RLOC information. BN2 queries Node 2 to get the information and sends them to BN1. 6. BN1 sends relative information to SHDHT MR 2. 7. After the recursive lookup procedures, SHDHT MR 2 sends the Map- Request directly to MS2. Cheng & Sun Expires January 16, 2014 [Page 19] Internet-Draft LISP Single-Hop DHT Mapping Overlay July 2013 6. Security Considerations TBD Cheng & Sun Expires January 16, 2014 [Page 20] Internet-Draft LISP Single-Hop DHT Mapping Overlay July 2013 7. IANA Considerations This document makes no requests to IANA. Cheng & Sun Expires January 16, 2014 [Page 21] Internet-Draft LISP Single-Hop DHT Mapping Overlay July 2013 8. References 8.1. Normative References [I-D.meyer-lisp-mn] Farinacci, D., Lewis, D., Meyer, D., and C. White, "LISP Mobile Node", October 2012. [I-ietf-lisp-ddt] Fuller, V., Lewis, D., and V. Ermagan, "LISP Delegated Database Tree", October 2012. [LISP-DHT] Mathy, L. and L. Iannone, "LISP-DHT: Towards a DHT to map identifiers onto locators, http://dl.acm.org/citation.cfm?id=1544073", December 2008. [RFC6830] Farinacci, D., Fuller, V., Meyer, D., and D. Lewis, "Locator/ID Separation Protocol (LISP)", January 2013. [RFC6833] Fuller, V. and D. Farinacci, "LISP Map Server Interface", January 2013. [RFC6836] Fuller, V., Farinacci, D., Meyer, D., and D. Lewis, "LISP Alternative Topology (LISP+ALT)", January 2013. 8.2. Informational References [I-D.lear-lisp-nerd] Lear, E., "NERD: A Not-so-novel EID to RLOC Database", April 2012. Appendix A. Acknowledgments The authors with to express their thanks to Michael Hoefling for work on Hash space segment of SHDHT overlay. Thanks also go to Dino Farinacci and Darrel Lewis for their suggestions about database structure deployment. Authors' Addresses Li Cheng ZTE Corporation R&D Building 1, Zijinghua Road No.68 Nanjing, Yuhuatai District 210012 P.R.China Email: cheng.li2@zte.com.cn Cheng & Sun Expires January 16, 2014 [Page 22] Internet-Draft LISP Single-Hop DHT Mapping Overlay July 2013 Mo Sun ZTE Corporation R&D Building 1, Zijinghua Road No.68 Nanjing, Yuhuatai District 210012 P.R.China Email: sun.mo@zte.com.cn Cheng & Sun Expires January 16, 2014 [Page 23]