LISP Single-Hop DHT Mapping Overlay
draft-cheng-lisp-shdht-00

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]