LISP Working Group L. Cheng
Internet-Draft M. Sun
Intended status: Standards Track ZTE Corporation
Expires: January 17, 2013 July 16, 2012
draft-cheng-lisp-shdht-01
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 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 January 17, 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 17, 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
2. Definition of Terms . . . . . . . . . . . . . . . . . . . . . 4
3. SHDHT Overview . . . . . . . . . . . . . . . . . . . . . . . . 4
3.1. Node ID and Partition ID . . . . . . . . . . . . . . . . . 4
3.2. Data Storage and Hash Assignment . . . . . . . . . . . . . 6
3.3. Node Routing Table . . . . . . . . . . . . . . . . . . . . 6
4. LISP SHDHT . . . . . . . . . . . . . . . . . . . . . . . . . . 7
4.1. SHDHT Node Operation . . . . . . . . . . . . . . . . . . . 7
4.2. ITR Operation . . . . . . . . . . . . . . . . . . . . . . 8
4.3. ETR Operation . . . . . . . . . . . . . . . . . . . . . . 8
4.4. Encapsulated Message Format . . . . . . . . . . . . . . . 9
4.4.1. Encapsulated Map Request . . . . . . . . . . . . . . . 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 . . . . . . . . . . . . . . . . . 11
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 11
Cheng & Sun Expires January 17, 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
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[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, 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
Cheng & Sun Expires January 17, 2013 [Page 3]
Internet-Draft LISP Single-Hop DHT Mapping Overlay July 2012
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 operators and could be deployed as
collaborative combination of multiple domain LISP SHDHTs. Deployment
of collaborative domain LISP SHDHTs is for future study, as well as
the security strategies on/between domain LISP SHDHTs.
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
Cheng & Sun Expires January 17, 2013 [Page 4]
Internet-Draft LISP Single-Hop DHT Mapping Overlay July 2012
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. I, it could be observed that hash space segments are not
required to be partitioned equally. As SHDHT Nodes could general
Partition IDs separately, when a SHDHT Node gets all hash segments
assignment information for 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.
Cheng & Sun Expires January 17, 2013 [Page 5]
Internet-Draft LISP Single-Hop DHT Mapping Overlay July 2012
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.
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
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 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.
Cheng & Sun Expires January 17, 2013 [Page 6]
Internet-Draft LISP Single-Hop DHT Mapping Overlay July 2012
+--------------+---------+---------------+
| 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 II 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 lookups its Node Routing Table and finds out that the
closest Partition ID to this Resource ID is 0x9000. Then Node 1 will
send put/get/remove request to the node owns the Partiton ID, in
Fig.1 is Node2, whose Node ID is 0x4444 and address is 10.0.0.3:2000.
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
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 message from
the LISP data plane, it will perform the following operations,
Cheng & Sun Expires January 17, 2013 [Page 7]
Internet-Draft LISP Single-Hop DHT Mapping Overlay July 2012
1. SHDHT Node extracts destination EID address from the control
message.
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 message and
performs proper operations according to message 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 message 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-
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 Map-Register messages.
Cheng & Sun Expires January 17, 2013 [Page 8]
Internet-Draft LISP Single-Hop DHT Mapping Overlay July 2012
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 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 , as shown in Fig.2.
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.
Cheng & Sun Expires January 17, 2013 [Page 9]
Internet-Draft LISP Single-Hop DHT Mapping Overlay July 2012
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.
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
[I-D.fuller-lisp-ddt]
Fuller, V., Lewis, D., and V. Ermagan, "LISP Delegated
Database Tree", March 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.mathy-lisp-dht]
Mathy, L., Iannone, L., and O. Bonaventure, "LISP-DHT:
Towards a DHT to map identifiers onto locators
http://biblio.info.ucl.ac.be/2008/456949.txt",
Cheng & Sun Expires January 17, 2013 [Page 10]
Internet-Draft LISP Single-Hop DHT Mapping Overlay July 2012
February 2008.
[I-D.meyer-lisp-mn]
Farinacci, D., Lewis, D., Meyer, D., and C. White, "LISP
Mobile Node", April 2012.
8.2. Informational References
[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.
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 17, 2013 [Page 11]