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]