LISP Working Group L. Cheng Internet-Draft M. Sun Intended status: Standards Track ZTE Corporation Expires: January 9, 2013 July 8, 2012 draft-cheng-lisp-shdht-00 LISP Single-Hop DHT Mapping Overlay Abstract This draft specifies the LISP Single-Hop Distributed Hash Table Mapping Overlay (LISP-SHDHT), a distributed mapping database which embodies SHDHT Nodes to maintain (Key, value) pairs for LISP (Locator/ID Separation Protocol)-like architecture, wherein every (key value) pair is according to an EID(Endpoint ID)-to-RLOC(Routing Locator) mapping information entry. According to this strategy, EID is hashed to be a unique Resource ID which is used for locating destiny DHT Node who maintains mapping entry for the particular EID. Furthermore, adaptive hash space partition method is adopted to solve the load balance problem on SHDHT Nodes which is common on traditional DHT plan. 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 9, 2013. Copyright Notice Copyright (c) 2012 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 Cheng & Sun Expires January 9, 2013 [Page 1] Internet-Draft LISP Single-Hop DHT Mapping Overlay July 2012 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 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 . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.1. Requirements Language . . . . . . . . . . . . . . . . . . 4 2. Definition of Terms . . . . . . . . . . . . . . . . . . . . . 4 3. SHDHT Overview . . . . . . . . . . . . . . . . . . . . . . . . 4 3.1. Node ID and Partition ID . . . . . . . . . . . . . . . . . 4 3.2. Data Storage and Hash Assignment . . . . . . . . . . . . . 5 3.3. Node Routing Table . . . . . . . . . . . . . . . . . . . . 6 4. LISP SHDHT . . . . . . . . . . . . . . . . . . . . . . . . . . 6 4.1. SHDHT Node Operation . . . . . . . . . . . . . . . . . . . 7 4.2. ITR Operation . . . . . . . . . . . . . . . . . . . . . . 7 4.3. ETR Operation . . . . . . . . . . . . . . . . . . . . . . 8 4.4. Encapsulated Message Format . . . . . . . . . . . . . . . 8 4.4.1. Encapsulated Map Request . . . . . . . . . . . . . . . 9 4.4.2. Encapsulated Map Register . . . . . . . . . . . . . . 9 5. Mobility Considerations . . . . . . . . . . . . . . . . . . . 10 6. Security Considerations . . . . . . . . . . . . . . . . . . . 10 7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 10 8. References . . . . . . . . . . . . . . . . . . . . . . . . . . 10 8.1. Normative References . . . . . . . . . . . . . . . . . . . 10 8.2. Informational References . . . . . . . . . . . . . . . . . 10 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 11 Cheng & Sun Expires January 9, 2013 [Page 2] Internet-Draft LISP Single-Hop DHT Mapping Overlay July 2012 1. Introduction Locator/ID Separation Protocol (LISP) [I-D.ietf-lisp] specifies an architecture and mechanism for replacing the address currently used by IP with two separate name spaces: Endpoint IDs (EIDs), used within 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 mapping globally. Several such mapping databases have been proposed, among them: LISP-NERD [I-D.lear-lisp-nerd], LISP- ALT[I-D.ietf-lisp-alt], LISP-DDT[I-D.fuller-lisp-ddt], and LISP-DHT [I-D.fuller-lisp-ddt]. According to hybrid model databases such like LISP-ALT [I-D.ietf-lisp-alt] and LISP-DDT [I-D.fuller-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 [I-D.mathy-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 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, massages interaction between SHDHT Nodes in the same SHDHT overlay just need one or two hops. 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 Cheng & Sun Expires January 9, 2013 [Page 3] Internet-Draft LISP Single-Hop DHT Mapping Overlay July 2012 is designed. 1.1. Requirements Language The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in RFC2119 [RFC2119]. 2. Definition of Terms This draft uses terms defined in [I-D.ietf-lisp]. 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. 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 are according 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 on SHDHT Nodes. 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[I-D.mathy-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. Cheng & Sun Expires January 9, 2013 [Page 4] Internet-Draft LISP Single-Hop DHT Mapping Overlay July 2012 +--------------------+ +--------------------+ |Node ID: 0x0123| |Node ID: 0x4444| |Partition ID: 0x1234| +-----+ +-----+ |Partition ID: 0x8000| | 0x6000| |Node1+----------+Node2| | 0x6000| +--------------------+ +--+--+ +--+--+ +--------------------+ | | | | | | | | +--------------------+ +--+--+ +--+--+ +--------------------+ |Node ID: 0xe000| |Node3+----------+Node4| |Node ID: 0xc000| |Partition ID: 0x4000| +-----+ +-----+ |Partition ID: 0xaaaa| | 0xeeee| | 0xcccc| +--------------------+ +--------------------+ Fig.1 In SHDHT, two roles of maintenance and hash space arrangement are separated and a new kind identifier called Partition ID is adopted. As shown in Fig.1, 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. 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. When a SHDHT Node gets the Resource ID of a data object, it could find out Partition ID of the hash space segment where the data object now locates in. 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. 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 9, 2013 [Page 5] Internet-Draft LISP Single-Hop DHT Mapping Overlay July 2012 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 for 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 massage point 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, massage could be transferred to the corresponding SHDHT Node. +--------------+---------+---------------+ | Partition ID | Node ID | Address | +--------------+---------+---------------+ | 0x1234 | 0x0123 | 10.0.0.2:2000 | | 0x3000 | 0x4444 | 10.0.0.3:2000 | | 0x4000 | 0xe000 | 10.0.0.4:2000 | | 0x6000 | 0x0123 | 10.0.0.2:2000 | | 0x8000 | 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 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). In SHDHT, all EID-to-RLOC mapping entries are stored in SHDHT Nodes as data objects. Each SHDHT Node have a RLOC address. EIDs in mapping entries can be hashed as Resource IDs of data objects. All SHDHT Nodes in the same SHDHT overly perform hash operation based on the same hash algorithm. Data objects stored in LISP SHDHT Nodes may be in the following Cheng & Sun Expires January 9, 2013 [Page 6] Internet-Draft LISP Single-Hop DHT Mapping Overlay July 2012 format: Object (lisp) = [EID prefix, (RLOC1, priority, weight), ...,RLOCn, priority, weight), TTL ] 4.1. SHDHT Node Operation In SHDHT, each SHDHT Node plays the roles of mapping server and forwarding router. When a SHDHT Node receives a control massage from the LISP data plane, it will perform the following operations, 1. SHDHT Node extracts destination EID address from the control massage. 2. SHDHT Node map the EID address to be Resource ID based on the shared hash algorithm. 3. SHDHT Node look up the Node Routing Table and find out the Partition ID which is closest to the Resource ID. 4. If the Resource ID locates in hash space segments the SHDHT Node responsible for, SHDHT Node decapsulates the control massage and performs proper operations according to massage type: * If the message is a Map-Request, SHDHT Node first checks if there's data objection, i.e. corresponding mapping entry, matching the Resource ID. If there is no match, the SHDHT Node returns a encapsulated negative Map-Reply. If there is matched mapping entry, the SHDHT Node returns the encapsulated Map-Reply. Furthermore, if the queried EID is covered by an EID prefix mapping entry, SHDHT Node could choose to return EID prefix mapping as response. * If the message is a Map-Register, SHDHT Node extracts and stores mapping information in the message. 5. Otherwise, SHDHT Node re-encapsulates the control massage and sends it to the corresponding node based on routing information in Node Routing Table. 4.2. ITR Operation According to LISP-MS [I-D.ietf-lisp-ms], LISP ITRs use Map Resolvers as proxy to send control messages, such like encapsulated Map- Requests and Map-Replies. In scenario of LISP SHDHT, SHDHT Nodes could also be configured as a Map Resolvers for the ITRs. An ITR could send encapsulated Map- Cheng & Sun Expires January 9, 2013 [Page 7] Internet-Draft LISP Single-Hop DHT Mapping Overlay July 2012 Requests to a SHDHT Node directly. If the selected SHDHT Node is the node who maintains the matching information, it will respond Map- Replies directly. Otherwise, it will forward Map-Requests into the DHT overlay, and forward Map-Replies to ITRs when it receives responds from other SHDHT Nodes. 4.3. ETR Operation According to LISP-MS [I-D.ietf-lisp-ms], LISP ETRs register mapping information onto the Map Server by sending encapsulated Map-Register messages. In scenario of LISP SHDHT, SHDHT Nodes play the role of Map Server. Thus, encapsulated Map-Register messages should be sent to corresponding SHDHT Nodes. As a result, ETRs could send Map-Register messages to a nearest SHDHT Node who will forward messages to the corresponding SHDHT Nodes who should take on the responsibility. 4.4. Encapsulated Message Format An Encapsulated Control Message (ECM) defined in[I-D.ietf-lisp] is used to encapsulate control packets sent between ITRs/ETRs and mapping database system. When ITRs/ETRs choose a SHDHT Node as proxy to send control messages, they could use encapsulated message format defined in , as shown in Fig.2. Cheng & Sun Expires January 9, 2013 [Page 8] Internet-Draft LISP Single-Hop DHT Mapping Overlay July 2012 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ / | IPv4 or IPv6 Header | OH | (uses RLOC addresses) | \ | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ / | Source Port = xxxx | Dest Port = 4342 | UDP +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ \ | UDP Length | UDP Checksum | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ LH |Type=8 |S| Reserved | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ / | IPv4 or IPv6 Header | IH | (uses RLOC or EID addresses) | \ | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ / | Source Port = xxxx | Dest Port = yyyy | UDP +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ \ | UDP Length | UDP Checksum | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ LCM | LISP Control Message | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Fig.2 Encapsulated Control Message Format 4.4.1. Encapsulated Map Request Suppose that the selected SHDHT Node of an ITR is Node1. When the ITR sends Encapsulated Map-Requests to Node1, source address and destination address in message OH (Outside Header) should be RLOC addresses of ITR and Node1 respectively. In the IH (Inside Header), source address is still RLOC address of Node1, while destination address is the inquired EID address. Consider Node1 is a configured Map Resolver, and then the configuration of Encapsulated Map-Request message has not been changed. 4.4.2. Encapsulated Map Register Suppose an ETR chooses a SHDHT Node (Node2) to send encapsulated Map- Register. As in traditional mapping overlay design, ETR anchors the corresponding map server, and send Map-Register message to map Cheng & Sun Expires January 9, 2013 [Page 9] Internet-Draft LISP Single-Hop DHT Mapping Overlay July 2012 server. As a result, the destination address in both OH and IH of encapsulated Map-Register message should be RLOC address of map server. However, in LISP SHDHT, there are some modifications. When the ETR send Encapsulated Map-Register to Node2, the source address in both OH and IH of message is RLOC address of ETR. The destination address in OH should be RLOC address of Node2, while destination address in IH should be the EID address according to the registered mapping entry. Furthermore, if the registered mapping entry is an EID prefix mapping entry, ETR could choose the highest EID address of the prefix as destination address. 5. Mobility Considerations As specified in section 4.2 and 4.3, ITR/ETR could choose a nearest LISP SHDHT Node as proxy to send control messages. Based on LISP SHDHT, when roaming events occurs, the roamed LISP sites or LISP MNs are no longer need to anchor pre-configured map- servers. 6. Security Considerations TBD 7. IANA Considerations This document makes no requests to IANA. 8. References 8.1. Normative References [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", March 1997. 8.2. Informational References [I-D.fuller-lisp-ddt] Fuller, V., Lewis, D., and V. Ermagan, "LISP Delegated Database Tree", March 2012. Cheng & Sun Expires January 9, 2013 [Page 10] Internet-Draft LISP Single-Hop DHT Mapping Overlay July 2012 [I-D.ietf-lisp] Farinacci, D., Fuller, V., Meyer, D., and D. Lewis, "Locator/ID Separation Protocol (LISP)", May 2012. [I-D.ietf-lisp-alt] Fuller, V., Farinacci, D., Meyer, D., and D. Lewis, "LISP Alternative Topology (LISP+ALT)", December 2011. [I-D.ietf-lisp-ms] Fuller, V. and D. Farinacci, "LISP Map Server Interface", March 2012. [I-D.lear-lisp-nerd] Lear, E., "NERD: A Not-so-novel EID to RLOC Database", April 2012. [I-D.mathy-lisp-dht] Mathy, L., Iannone, L., and O. Bonaventure, "LISP-DHT: Towards a DHT to map identifiers onto locators", February 2008. [I-D.meyer-lisp-mn] Farinacci, D., Lewis, D., Meyer, D., and C. White, "LISP Mobile Node", April 2012. 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 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 9, 2013 [Page 11]