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