Internet DRAFT - draft-zhang-lisp-hms
draft-zhang-lisp-hms
Network Working Group Hongke Zhang
Internet Draft Xiaoqian Li
Expires: June 2013 Hongbin Luo
Huachun Zhou
Zhengxin Zhang
December 17, 2012
A Hierarchical Mapping System for LISP
draft-zhang-lisp-hms-01.txt
Status of this Memo
This Internet-Draft is submitted to IETF in full conformance with the
provisions of BCP 78 and BCP 79.
Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF), its areas, and its working groups. Note that
other groups may also distribute working documents as Internet-Drafts.
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."
The list of current Internet-Drafts can be accessed at
http://www.ietf.org/ietf/1id-abstracts.txt
The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html
This Internet-Draft will expire on June 17, 2013.
Copyright Notice
Copyright (c) 2011 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
Zhang et al. Expires June 17, 2013 [Page 1]
Internet-Draft A Hierarchical Mapping System for LISP December 2012
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.
Abstract
This draft proposes a Hierarchical Mapping System (HMS) for
Locator/ID Separation Protocol (LISP). HMS uses a hierarchical
architecture as well as one-hop DHT (Distributed Hash Tables). HMS
composes two levels with the bottom level maintaining EID-to-RLOC
mappings in an Autonomous System (AS) and the upper level storing the
global EID-prefix-to-AS mappings. The bottom level is organized in
one-hop DHT and the upper level propagates EID-prefix-to-AS mappings
using a protocol like BGP. HMS builds an efficient and scalable
mapping system to provide RLOCs for a given EID.
Conventions used in this document
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
document are to be interpreted as described in RFC-2119 0.
Table of Contents
1. Introduction ................................................ 3
2. Definition of items ......................................... 3
3. HMS Overview ................................................ 5
3.1. The architecture of HMS
................................. 5
3.2. Mapping registration
.................................... 7
3.3. Mapping resolution
...................................... 8
4. Mobility .................................................... 9
5. Scalability ................................................ 10
6. Multihoming and traffic engineering ......................... 10
7. Security Considerations
..................................... 10
8. IANA Considerations ........................................ 10
9. Acknowledgments ............................................ 10
10. References ................................................ 11
Author's Addresses ............................................ 11
Intellectual Property Statement
....................
Disclaimer of Validity ............................
Copyright Statement ...............................
Acknowledgment ................................................ 12
Zhang et al. Expires June 17, 2013 [Page 2]
Internet-Draft A Hierarchical Mapping System for LISP December 2012
1. Introduction
The current Internet is facing routing scalability problems and the
overloading of IP addresses with the semantics of both "who" and
"where" is considered to have deep implications for the routing
scalability [RFC 4984]. Separating the address space into identifiers
and locators has been proposed to address this problem, such as ILNP
(Identifier-Locator Network Protocol) [ILNP], LISP (Locator/ID
Separation Protocol) [LISP]. The mapping system is built to supply
EID-to-RLOC mappings for Ingress Tunnel Routers (ITRs) and it is a
very important component of the locator/identifier separation network.
There have been several proposals to address this issue [LISP+ALT]
[LISP-DHT] [LISP-TREE] [DHT-MAP].
This document proposes a hierarchical mapping system (HMS) which
comprises two levels. The bottom level stores the EID-to-RLOC
mappings in an AS and the upper level stores the global mappings
between EID-prefixes and ASs. Each AS can organize its own mapping
system in the bottom level and this draft suggests the use of one hop
DHT to implement this. It can guarantee one hop lookup in an AS while
the hierarchical architecture or other DHTs cannot. HMS treats each
EID as an individual, flat identifier in the bottom level. In the
upper level, HMS propagates the EID-prefix-to-AS mapping information
using a protocol like BGP. It can aggregate the prefixes in an AS to
reduce the number of mapping entries in the upper level. This draft
designs the mobility management in HMS and the mobility does not
cause mapping updates in the upper level, which makes HMS support
host mobility efficiently.
2. Definition of items
Autonomous System (AS): Within the Internet, an autonomous system is
a collection of connected Internet Protocol (IP) routing prefixes
under the control of one or more network operators that presents a
common, clearly defined routing policy to the Internet. See [RFC
1930] for details.
Endpoint ID (EID): An EID is a 32-bit (for IPv4) or 128-bit (for IPv6)
value used in the source and destination address fields of the
first (most inner) LISP header of a packet. An EID is allocated to
a host from an EID-prefix block associated with the site where the
host is located. See [LISP] for details.
Routing Locator (RLOC): A RLOC is an IPv4 or IPv6 address of an
egress tunnel router (ETR). A RLOC is the output of an EID-to-RLOC
Zhang et al. Expires June 17, 2013 [Page 3]
Internet-Draft A Hierarchical Mapping System for LISP December 2012
mapping lookup. An EID maps to one or more RLOCs. Typically, RLOCs
are numbered based on the connectivity of provider networks. See
[LISP] for details.
EID-prefix: An EID-prefix is a power-of-two block of EIDs which are
allocated to a site by an address allocation authority. EID-prefix
allocations can be broken up into smaller blocks when an RLOC set
is to be associated with the smaller EID-prefix.
EID-to-RLOC mapping: a binding between an EID or EID-prefix and a
RLOC set which can be used to reach the EID. The ITRs can
encapsulate packets with the RLOC in the EID-to-RLOC mapping to
reach the destination EID. A RLOC set may contain multiple RLOCs to
perform multi-homing or traffic engineering.
Ingress Tunnel Router (ITR): An ITR accepts an IP packet and prepends
an "outer" header with RLOCs. It sends a Map-request to the mapping
system when it does not have the EID-to-RLOC mapping for the
destination EID.
Egress Tunnel Router (ETR): An ETR accepts packets with the RLOCs as
the destination addresses. It strips the outer header and forwards
packets based on EIDs.
xTR: A xTR is a reference to an ITR or ETR when direction of data
flow is not part of the context description. xTR refers to the
router that is the tunnel endpoint.
Mapping Server (MS): A Mapping Server is a component introduced in
HMS to store the EID-to-RLOC mappings in an AS. It is used in the
bottom level of HMS. An AS may need multiple Mapping Servers. This
draft organizes Mapping Servers in an AS based on one-hop DHT.
Destination Mapping Server (DMS): The destination Mapping Server is
the successor of the EID that is requested in the one hop DHT.
Mapping Domain (MD): This document defines the area that a Mapping
Server covers as a Mapping Domain, that is, a Mapping Server can
supply the EID-to-RLOC mappings in a Mapping Domain. A Mapping
Server reports the EID-prefix in its mapping domain to the
Forwarder it connects to.
Zhang et al. Expires June 17, 2013 [Page 4]
Internet-Draft A Hierarchical Mapping System for LISP December 2012
Forwarder (FW): A Forwarder is an agent in an AS. It aggregates the
EID-prefixes in an AS, issues mappings between EID-prefixes and
Forwarder and reports to the upper level in HMS. When there is one
Forwarder in an AS, it actually issues the mapping between EID-
prefix and AS.
Resolver (RS): A Resolver is a component in the upper level to store
the global mappings between EID-prefixes and Forwarders. There may
be multiple Resolvers in an AS. Resolvers run a protocol like BGP
to propagate EID-prefix-to-Forwarder mappings. Each Resolver stores
the global mappings.
EID-prefix-to-Forwarder mapping: A binding between EID-prefix and the
Forwarder which is in the same AS as the EID-prefix. EID-prefix-to-
Forwarder mapping is issued by the Forwarder.
EID-prefix-to-AS mapping: When there is one Forwarder in an AS, the
EID-prefix-to-Forwarder mapping actually is EID-prefix-to-AS
mapping. It is the binding between the EID-prefix and the AS which
announces the EID-prefix.
3. HMS Overview
3.1. The architecture of HMS
This draft proposes a Hierarchical Mapping System (HMS). Figure 1
shows the architecture of HMS. HMS consists of two levels. The bottom
level stores the EID-to-RLOC mappings in an AS and the upper level
propagates the EID-prefix-to-Forwarder mappings. HMS introduces three
types of components: Mapping Server, Forwarder and Resolver. Mapping
Servers locate in the bottom level and maintain EID-to-RLOC mappings
in a Mapping Domain. There may be several Mapping Servers in an AS. A
Mapping Server reports the prefixes in its Mapping Domain to the
Forwarder it connects to. A Forwarder in an AS aggregates the
prefixes it receives, issues the EID-prefix-to-Forwarder mappings and
reports the mappings to the Resolver it connects to. Resolvers
exchange EID-prefix-to-Forwarder mappings using a protocol like BGP.
Each Resolver stores the global mappings.
In the bottom level, every AS can organize the Mapping Servers in its
own manner and this draft suggests the use of one-hop DHT to
implement this. One-hop DHT can guarantee one hop lookup. The
Zhang et al. Expires June 17, 2013 [Page 5]
Internet-Draft A Hierarchical Mapping System for LISP December 2012
designer of the network can organizes Mapping Servers in an
appropriate way as long as they can exchange the mapping information
with the upper level. Mapping Servers and Forwarders deal with the
local mapping information.
In the upper level, Resolvers propagate EID-prefix-to-Forwarder
mappings running a protocol like BGP so that each Resolver stores the
mappings in the overall network. When there is only one Forwarder in
an AS, the Resolvers aggregate EID-prefixes and the EID-prefix-to-
Forwarder mappings are actually the EID-prefix-to-AS mappings.
+------------------------------------------------+
| +----+ +----+ |
| | RS |------------ | RS | |
| +----+ +----+ |
| | | |
| | | |
| +----+ +----+ |
| | RS |------------ | RS | |
| +----+ +----+ |
| / Upper level \ |
| ----------/----------------------\------------- |
| / Bottom level \ |
| +--+ +--+ |
| |FW| |FW| |
| +--+ +--+ |
| / \ |
| / \ |
| +--+ +--+ +--+ +--+ |
| |MS|----- |MS| |MS|----- |MS| |
| +--+ +--+ +--+ +--+ |
| | | | | |
| +--+ +--+ +--+ +--+ |
| |MS|----- |MS| |MS|----- |MS| |
| +--+ +--+ +--+ +--+ |
| | | |
| | | |
| +---+ +---+ |
| |ITR| |ITR| |
| +---+ +---+ |
| |
+------------------------------------------------+
Figure 1 :Architecture of HMS
Zhang et al. Expires June 17, 2013 [Page 6]
Internet-Draft A Hierarchical Mapping System for LISP December 2012
3.2. Mapping registration
When an end host attaches to an ITR, the ITR delegates a RLOC to the
EID and reports the mapping to the mapping system. Figure 2 shows the
registration flow.
Step 1: After an ITR delegates a RLOC to an EID, it registers the
EID-to-RLOC mapping to its default Mapping Server.
Step 2: Besides storing the EID-to-RLOC mapping to its local memory,
the Mapping Server hashes the EID and sends the mapping to the
destination Mapping Server.
Step 3: The Mapping Server aggregates the EIDs in its local memory
and reports the EID-prefixes to the Forwarder it connects to.
Step 4: The Forwarder aggregates the EID-prefixes it receives, issues
the EID-prefix-to-Forwarder mappings and reports the mappings to the
Resolver it connects to.
Step 5: After receiving the EID-prefix-to-Forwarder mappings, the
Resolver advertises the mappings to other Resolvers using a protocol
like BGP so that all the Resolvers keep the global EID-prefix-to-
Forwarder mappings.
+---------------------------------------------------+
| +---+ +---+ +---+ +---+ +---+ +---+ |
| |ITR| | MS| |DMS| |FW | |RS | |RS | |
| +---+ +---+ +---+ +---+ +---+ +---+ |
| | | | | | | |
| |---1---> | | | | | |
| | | | | | | |
| | |---2--> | | | | |
| | | | | | | |
| | |-------3-------> | | | |
| | | | | | | |
| | | | |---4--> | | |
| | | | | | | |
| | | | | |---5--> | |
| | | | | | | |
| | | | | | | |
| |
+---------------------------------------------------+
Figure 2 :Registration flow
Zhang et al. Expires June 17, 2013 [Page 7]
Internet-Draft A Hierarchical Mapping System for LISP December 2012
3.3. Mapping resolution
When an ITR receive an IP packet, it encapsulates the packet with the
RLOCs of the source and destination EID. If an ITR cannot supply a
RLOC for the destination EID, it resolves the mapping in the mapping
system. Figure 3 depicts the resolution flow.
Step 1: When an ITR does not have an EID-to-RLOC mapping for the
destination EID, it sends a map-request to the Mapping Server.
Step 2: If the source and destination EIDs are in the same Mapping
Domain, the Mapping Server can supply a RLOC for the destination EID.
If not, the Mapping Server hashes the EID and forwards the map-
request to the destination Mapping Sever.
Step 3: If the source and destination EIDs are in the same AS, the
destination Mapping Server can supply a RLOC for the destination EID.
If not, the destination Mapping Server forwards the map-request to
the Resolver it connects to.
Step 4: The Resolver finds the EID-prefix-to-Forwarder mapping and
forwards the map-request to the Forwarder.
Step 5: The Forwarder sends the map-request to one of the Mapping
Servers in the destination AS.
Step 6: The Mapping Server hashes the EID and forwards the map-
request to the destination Mapping Server.
Step 7: The destination Mapping Server finds the EID-to-RLOC mapping
in its mapping database and sends a map-reply to the ITR.
Zhang et al. Expires June 17, 2013 [Page 8]
Internet-Draft A Hierarchical Mapping System for LISP December 2012
+--------------------------------------------------+
| +---+ +---+ +---+ +---+ +---+ +---+ +---+ |
| |ITR| | MS| |DMS| |RS | |FW | |MS | |DMS| |
| +---+ +---+ +---+ +---+ +---+ +---+ +---+ |
| | | | | | | | |
| |--1--> | | | | | | |
| | | | | | | | |
| | |--2--> | | | | | |
| | | | | | | | |
| | | |--3-> | | | | |
| | | | | | | | |
| | | | |--4-> | | | |
| | | | | | | | |
| | | | | |--5-> | | |
| | | | | | | | |
| | | | | | |-6-> | |
| | | | | | | | |
| |<--------------7 Map-Reply--------------------- |
| | | | | | | | |
+--------------------------------------------------+
Figure 3 :Resolution flow
4. Mobility
The upper level in HMS stores the global mapping information of EID-
prefix-to-Forwarder, so it is very important to keep the mappings
stable in the upper level. The mobility in HMS must not cause lots of
mapping updates.
When a Mobile Node (MN) moves in one AS, it just updates the EID-to-
RLOC mapping in the bottom level and does not cause EID-prefix-to-
Forwarder mapping dynamics in the upper level.
When a MN moves across several ASs, the Forwarder in the current AS
sends an update message to the Forwarder in the home AS and there is
no need to update the upper level. When a map-request arrives at the
Forwarder in the home AS, it forwards the map-request to the
Forwarder in the current AS and resolves the mapping in the current
AS.
Zhang et al. Expires June 17, 2013 [Page 9]
Internet-Draft A Hierarchical Mapping System for LISP December 2012
5. Scalability
When there is one Forwarder in an AS, the upper level can aggregate
the EID-prefixes in an AS. The number of mapping entries can be
reduced and the number of aggregated EID-prefixes grows slower than
the routing table.
The hierarchical architecture prevents the mapping dynamics within an
AS from impacting the upper level. It makes the mappings in the upper
level rather stable, reducing the error caused by the mapping
information asynchronization. The less dynamics of HMS reduces the
processing cost and make a less possibility to have scalability
problems.
6. Multihoming and traffic engineering
When an end host or a sub network is multihoming, there is only one
mapping entry for the EID or EID-prefix in the mapping system. The
mapping system can set different preferences or weights for the
mappings to perform traffic engineering.
7. Autonomous
Although we suggest the use of One-hop DHT in the bottom level, the
network designer can design its own mapping system in an AS as long
as the bottom level can exchange EID-prefix-to-AS mappings with the
upper level. The network can design the mapping system according to
its own constraints.
8. Security Considerations
The EID-to-RLOC mappings are organized in an AS and they do not
appear in the transit network. The transit network just knows where
to get the EID-to-RLOC mapping does not know the exact information,
which makes the mapping information security.
The upper level in HMS uses a protocol like BGP to propagate mapping
information, so HMS can share the security characteristics of BGP.
9. IANA Considerations
This document makes no request of the IANA.
10. Acknowledgments
Zhang et al. Expires June 17, 2013 [Page 10]
Internet-Draft A Hierarchical Mapping System for LISP December 2012
11. References
[RFC 2119] Bradner, S., Key words for use in RFCs to Indicate
Requirement Levels. BCP 14, RFC 2119, March 1997.
[RFC 4984] David, M., Lixia, Z. and Kevin, F., Report from the IAB
Workshop on Routing and Addressing. RFC 4984, September 2007.
[ILNP] Randall, A., Saleem, B. and Stephen, H., Evolving the
Internet Architecture Through Naming. IEEE Journal on Selected Areas
in Communications, VOL.28, NO.8, October 2010.
[LISP] Dino, F., Vince, F., Dave, M. and Darrel, L., Locator/ID
Separation Protocol (LISP). Internet draft, draft-ietf-lisp-24,
November 2012.
[LISP+ALT] Vince,F., Dino, F., Dave, M. and Darrel, L., LISP
alternative topology (LISP-ALT). Internet draft,draft-fuller-lisp-
alt-10, December 2011.
[LISP-DHT] Laurent, M. and Luigi, I., LISP-DHT: Towards a DHT to
map identifiers onto locators. in Proc of ReArch'08, December 2008.
[LISP-TREE] Lorand, J., Albert, C-A., Florin, C., Damien, S. and
Oliver, B., LISP-TREE: A DNS Hierarchy to Support the LISP Mapping
System. IEEE Journal on Selected Areas in Communication, VOL. 28,
NO.8, October 2010.
[DHT-MAP] Hongbin, L., Yajuan, Q and Hongke, Z., A DHT-based
Identifier-to-locator mapping approach for a scalable Internet. IEEE
Transaction on Parallel and Distributed Systems, Vol. 20,Issue 12, pp.
1790-1802, December,2009.
[RFC 1930] John,H. and Tony,B., Guidelines for creation, selection,
and registration of an Autonomous System (AS), BCP 6, RFC 1930, March
1996.
Author's Addresses
Hongke Zhang, Xiaoqian Li, Hongbin Luo, Huachun Zhou
National Engineering Laboratory for Next Generation Internet
Interconnection Devices
School of Electronics and Information Engineering
Zhang et al. Expires June 17, 2013 [Page 11]
Internet-Draft A Hierarchical Mapping System for LISP December 2012
Beijing Jiaotong University of China
Phone: +86 01051685677
hkzhang@bjtu.edu.cn
xiaoqianli@bjtu.edu.cn
hbluo@bjtu.edu.cn
hczhou@bjtu.edu.cn
Zhengxin Zhang
BEIJING C&W ELECTRONICS(GROUP) CO.,LTD.
paulzhang@163.com
Acknowledgment
Funding for the RFC Editor function is currently provided by the
Internet Society.
Zhang et al. Expires June 17, 2013 [Page 12]
