LISP Working Group                                              L. Cheng
Internet-Draft                                                    M. Sun
Intended status: Standards Track                         ZTE Corporation
Expires: August 25, 2013                               February 21, 2013


                       draft-cheng-lisp-shdht-03
                  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 corresponds 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
   destination 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 planes.

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 August 25, 2013.

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



Cheng & Sun              Expires August 25, 2013                [Page 1]


Internet-Draft     LISP Single-Hop DHT Mapping Overlay     February 2013


   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
   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  . . . . . . . . . . . . . . . . . . . . . . 10
     4.3.  SHDHT Map Resolver Operation . . . . . . . . . . . . . . . 11
     4.4.  SHDHT Map Server Operation . . . . . . . . . . . . . . . . 11
     4.5.  Encapsulated Message Format  . . . . . . . . . . . . . . . 12
       4.5.1.  Encapsulated Map Request . . . . . . . . . . . . . . . 13
   5.  Domain LISP SHDHT Deployment . . . . . . . . . . . . . . . . . 14
     5.1.  SHDHT Border  Node . . . . . . . . . . . . . . . . . . . . 14
     5.2.  Mapping Register . . . . . . . . . . . . . . . . . . . . . 15
       5.2.1.  Intra Domain Mapping Register  . . . . . . . . . . . . 15
       5.2.2.  Inter Domain Mapping Register  . . . . . . . . . . . . 15
     5.3.  Mapping Request  . . . . . . . . . . . . . . . . . . . . . 16
       5.3.1.  Intra Domain Mapping Request . . . . . . . . . . . . . 16
       5.3.2.  Inter Domain Mapping Request . . . . . . . . . . . . . 17
   6.  Mobility Considerations  . . . . . . . . . . . . . . . . . . . 18
   7.  Security Considerations  . . . . . . . . . . . . . . . . . . . 19
   8.  IANA Considerations  . . . . . . . . . . . . . . . . . . . . . 20
   9.  References . . . . . . . . . . . . . . . . . . . . . . . . . . 21
     9.1.  Normative References . . . . . . . . . . . . . . . . . . . 21
     9.2.  Informational References . . . . . . . . . . . . . . . . . 21
   Appendix A.  Acknowledgments . . . . . . . . . . . . . . . . . . . 21
   Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 21












Cheng & Sun              Expires August 25, 2013                [Page 2]


Internet-Draft     LISP Single-Hop DHT Mapping Overlay     February 2013


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].

   According to hybrid model 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 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
       is designed.



Cheng & Sun              Expires August 25, 2013                [Page 3]


Internet-Draft     LISP Single-Hop DHT Mapping Overlay     February 2013


   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 mapping 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.  Security strategies on/between Domain LISP SHDHTs is for
   future study.












































Cheng & Sun              Expires August 25, 2013                [Page 4]


Internet-Draft     LISP Single-Hop DHT Mapping Overlay     February 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 Server:  A SHDHT Node that also implements Map Server
      functionality (forwarding Map-Requests and/or return Map Replies
      if offering proxy Map-Reply service) for mapping entries it
      maintains.

   SHDHT Map Resolver:  A SHDHT Node that also implements Map Resolver
      functionality (accepting Map-Requests, hash the requested EID to
      be Resource ID, and then forward Map-Requests to corresponding
      SHDHT Map Server based on Resource ID).  Furthermore, in this
      document SHDHT Map Resolver could perform as proxy for Map-



Cheng & Sun              Expires August 25, 2013                [Page 5]


Internet-Draft     LISP Single-Hop DHT Mapping Overlay     February 2013


      Register.  SHDHT Map Resolver could accept register messages and
      forward them to SHDHT Map Servers.

   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 Ttable:  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 August 25, 2013                [Page 6]


Internet-Draft     LISP Single-Hop DHT Mapping Overlay     February 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 general



Cheng & Sun              Expires August 25, 2013                [Page 7]


Internet-Draft     LISP Single-Hop DHT Mapping Overlay     February 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 general 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 August 25, 2013                [Page 8]


Internet-Draft     LISP Single-Hop DHT Mapping Overlay     February 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       |
                +--------------+---------+---------------+
                | 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 August 25, 2013                [Page 9]


Internet-Draft     LISP Single-Hop DHT Mapping Overlay     February 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).

   In LISP SHDHT, mapping overlay consists of SHDHT Nodes which play
   roles of SHDHT Map Server and/or SHDHT Map Resolver.  In this draft
   SHDHT-MS and SHDHT-MR just represent function entities, and these
   entities could be collocated on the same SHDHT Node.

   All EID-to-RLOC mapping entries are stored in SHDHT Nodes as data
   objects.  Each SHDHT Node has 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
   format:

          Object (lisp) = [EID prefix, (RLOC1, priority, weight),
                        ...,RLOCn, priority, weight), TTL ]

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
   the ITR.

4.2.  ETR Operation

   According to LISP-MS [RFC6833], LISP ETRs register mapping
   information onto the Map Server by sending Map-Register messages.

   In scenario of LISP SHDHT, ETR could send Map-Register messages
   directly to the SHDHT Node which is selected to play roles of SHDHT
   Map Server for the registered EIDs.

   Alternatively, ETRs could send Map-Register messages to a nearest
   SHDHT Node who will hash registered mapping entries to be Resource
   IDs.  Then, the SHDHT Node forwards Map-Register messages to the
   corresponding SHDHT Map Servers based on Resource IDs.  This
   alternative strategy will be more efficient for roaming scenario.
   Furthermore, ETRs are no longer anchoring to fixed SHDHT Map Server



Cheng & Sun              Expires August 25, 2013               [Page 10]


Internet-Draft     LISP Single-Hop DHT Mapping Overlay     February 2013


   Nodes, and ISPs who operate mapping overlays could arrange hash space
   onto SHDHT Nodes more autonomously and could perform better load
   balance among SHDHT Nodes.

4.3.  SHDHT Map Resolver Operation

   In LISP SHDHT, when a SHDHT Map Resolver receives a Map-Request
   message from an ITR, it will perform the following operations,

   1.  SHDHT Map Resolver extracts destination EID address from the Map-
       Request message.

   2.  SHDHT Map Resolver hashes the EID address to be Resource ID based
       on the shared hash algorithm.

   3.  SHDHT Map Resolver looks up Node Routing Table and finds out the
       Partition ID which matches the Resource ID.

   4.  SHDHT Map Resolver forwards Map-Request message to the
       corresponding SHDHT Node.  This SHDHT Node maintains the hash
       space labeled by matched Partition ID and plays the role of SHDHT
       Map Server for the requested mapping entry.

   In LISP SHDHT, when a SHDHT Map Resolver receives a Map-Register
   message from an ETR, it will perform the following operations,

   1.  SHDHT Map Resolver extracts registered EID information of the
       Map-Register message.

   2.  SHDHT Map Resolver hashes the registered EID address to be
       Resource ID based on shared hash algorithm.

   3.  SHDHT Map Resolver looks up Node Routing Table and finds out the
       Partition ID which matches the Resource ID.

   4.  SHDHT Map Resolver forwards Map-Register message to the
       corresponding SHDHT Map Server.

4.4.  SHDHT Map Server Operation

   In LISP SHDHT, when a SHDHT Map Server receives a Map-Request
   message, it will perform the following operations,

   1.  SHDHT Map Server first check if it is responsible for the
       requested mapping entry, i.e. if it has a hash space whose
       Partition ID matches Resource ID of the requested EID.





Cheng & Sun              Expires August 25, 2013               [Page 11]


Internet-Draft     LISP Single-Hop DHT Mapping Overlay     February 2013


   2.  SHDHT Map Server then looks for data objects in its hash space
       according to the matched Partition ID.

   3.  If there's no data object corresponds to the requested EID, SHDHT
       Map Server responses a negative Map-Reply message.

   4.  If there's a data object corresponds to the requested EID, SHDHT
       Map Server will forward the Map-Request to registered ETR or
       return Map-Reply message if it offers proxy Map-Reply service.

   In LISP SHDHT, when a SHDHT Map Server receives a Map-Register
   message, it will perform the following operations,

   1.  SHDHT Map Server first checks if it is responsible for the
       registered mapping entry, i.e. if it has a hash space whose
       Partition ID matches Resource ID of the requested EID.

   2.  SHDHT Map Server then stores and maintains the registered mapping
       information in its hash space according to the matched Partition
       ID.

4.5.  Encapsulated Message Format

   An Encapsulated Control Message (ECM) defined in[RFC6830] is used to
   encapsulate control packets sent between xTRs and mapping database
   system.  At this time, only Map-Request messages are allowed to be
   encapsulated in ECM format.  When ITRs choose a SHDHT Node as proxy
   to send control messages, they could use encapsulated message format
   defined in [RFC6830], as shown in Fig.2.






















Cheng & Sun              Expires August 25, 2013               [Page 12]


Internet-Draft     LISP Single-Hop DHT Mapping Overlay     February 2013


        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.5.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.











Cheng & Sun              Expires August 25, 2013               [Page 13]


Internet-Draft     LISP Single-Hop DHT Mapping Overlay     February 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 application, 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 practice 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.3, 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.3, 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.


    +----+     +-----+      +-----+   +-----+      +-----+      +----+
    |ITR1+-----+Node1+------+Node2|   |Node4+------+Node5+------+ITR2|
    +----+     +--+--+      +--+--+   +--+--+      +--+--+      +----+
                  |   Domain   |         |   Domain   |
                  |  Overlay 1 |         |  Overlay 2 |
                  | 12.0.0.0\8 |         | 16.0.0.0\8 |
    +----+     +--+--+      +--+--+   +--+--+      +--+--+      +----+
    |ETR1+-----+Node3+------+ BN1 |<->| BN2 +------+Node6+------+ETR2|
    +----+     +-----+      +-----+   +-----+      +-----+      +----+

   * BN: SHDHT Border Node

                   Fig.3 Domain SHDHT Deployment Example

5.1.  SHDHT Border  Node

   Each Domain SHDHT Overlay has one or more Border Nodes which are not
   only to store EID-to-RLOC mapping just like normal SHDHT Nodes, but
   also be used to flood cross domain routing and forward the cross
   domain packets.

   Each SHDHT Border Node maintains an Inter-Domain Routing Table, which
   contains information of all other domain overlays, such like EID



Cheng & Sun              Expires August 25, 2013               [Page 14]


Internet-Draft     LISP Single-Hop DHT Mapping Overlay     February 2013


   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.  Mapping Register

5.2.1.  Intra Domain Mapping Register

   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 Map-Register message, it checks
   if the registered EIDs are covered by local domain overlay's EID
   prefixes.  If local domain overlay is responsible for registered
   EIDs, SHDHT Node who receives Map-Register message will process the
   message as procedures listed in Section 4.3.

   Suppose in Fig.3, ETR1 registers mapping entry of EID 12.0.0.1 to
   Node3 of Domain1.  Node 3 will perform the following operations,

   1.  Node3 extracts the mapping information and finds that the
       registered EID is 12.0.0.1.

   2.  Node3 determines that EID 12.0.0.1 is covered by Domain 1's
       prefix 12.0.0.0/8.

   3.  Node3 hashes registered EID 12.0.0.1 to be Resource ID.

   4.  Node3 forwards Map-Register message to the Node whose Partition
       ID matches the Resource ID.

5.2.2.  Inter Domain Mapping Register

   All SHDHT Nodes of a Domain SHDHT Overlay must be configured with
   routing information pointing to local domain overlay's Border Nodes.
   When a SHDHT Node of a domain overlay receives a Map-Register
   message, it checks if the registered EIDs are covered by local domain
   overlay's EID prefixes.  If local domain overlay is not responsible
   for registered EIDs, SHDHT Node who receives Map-Register 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.3, ETR2 registers mapping entry of EID 12.2.0.1 to
   Node 6 of Domain 2.  It will perform the following operations,



Cheng & Sun              Expires August 25, 2013               [Page 15]


Internet-Draft     LISP Single-Hop DHT Mapping Overlay     February 2013


   1.  Node6 extracts the mapping information and finds that the
       registered EID is 12.2.0.1.

   2.  Node6 determines that EID 12.2.0.1 is not covered by Domain 2's
       prefix 16.0.0.0/8.

   3.  Node6 forwards the Map-Register message to BN2.

   4.  BN2 extracts mapping information 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-Register message to Domain 1's Border Node ( BN1).

   6.  BN1 processes the Map-Register message based on procedures
       introduced in Section 5.2.1.

5.3.  Mapping Request

5.3.1.  Intra Domain Mapping Request

   When SHDHT Node of a Domain SHDHT Overlay 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 Node hashes the requested EID to be Resource ID
   and forward message to the SHDHT Node who maintains the hash space
   labeled by matched Partition ID.  The Target SHDHT Node plays roles
   of SHDHT Map Server for the required mapping entry, and will process
   the message based on procedures introduced in Section 4.4.

   Suppose in Fig.3, ITR1 send a Map-Request message to Node1 of Domain
   1 to get mapping information of EID 12.2.0.1.

   1.  Node1 extract requested EID from the Map-Request message.

   2.  Node1 determines that EID 12.2.0.1 is covered by Domain 1's EID
       prefix 12.0.0.0/8.  The mapping entry is now stored on a SHDHT
       Node of Domain 1.

   3.  Node1 hashes requested EID 12.0.0.1 to be Resource ID.

   4.  Node1 forwards Map-Register message to the Node whose Partition
       ID matches the Resource ID.






Cheng & Sun              Expires August 25, 2013               [Page 16]


Internet-Draft     LISP Single-Hop DHT Mapping Overlay     February 2013


5.3.2.  Inter Domain Mapping Request

   When SHDHT Node of a Domain SHDHT Overlay receives a Map-Request
   message, it checks if the requested EID is covered by local domain
   overlay's EID prefixes.  If the requested EID entry is not stored on
   local domain overlay, SHDHT Node 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.3, ITR2 send a Map-Request message to Node 5 of Domain
   2 to get mapping information of EID 12.0.0.1.

   1.  Node5 extracts requested EID from the Map-Request message.

   2.  Node5 determines that EID 12.0.0.1 is not covered by Domain 2's
       prefix 16.0.0.0/8.

   3.  Node5 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.0.0.1.

   5.  BN2 finds out Domain 1 is responsible for EID 12.0.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 5.3.1.
























Cheng & Sun              Expires August 25, 2013               [Page 17]


Internet-Draft     LISP Single-Hop DHT Mapping Overlay     February 2013


6.  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.











































Cheng & Sun              Expires August 25, 2013               [Page 18]


Internet-Draft     LISP Single-Hop DHT Mapping Overlay     February 2013


7.  Security Considerations

   TBD
















































Cheng & Sun              Expires August 25, 2013               [Page 19]


Internet-Draft     LISP Single-Hop DHT Mapping Overlay     February 2013


8.  IANA Considerations

   This document makes no requests to IANA.
















































Cheng & Sun              Expires August 25, 2013               [Page 20]


Internet-Draft     LISP Single-Hop DHT Mapping Overlay     February 2013


9.  References

9.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.

   [RFC6836]  Fuller, V., Farinacci, D., Meyer, D., and D. Lewis, "LISP
              Alternative Topology (LISP+ALT)", January 2013.

9.2.  Informational References

   [I-D.lear-lisp-nerd]
              Lear, E., "NERD: A Not-so-novel EID to RLOC Database",
              April 2012.

   [RFC6833]  Fuller, V. and D. Farinacci, "LISP Map Server Interface",
              January 2013.


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.












Cheng & Sun              Expires August 25, 2013               [Page 21]


Internet-Draft     LISP Single-Hop DHT Mapping Overlay     February 2013


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 August 25, 2013               [Page 22]