INTERNET-DRAFT Chunfeng Yao Intended Status: Informational Rong Wang Expires: August 21, 2013 Yuanzhe Xuan Zhefeng Yan Huawei February 17, 2013 Container Assisted Naming and Routing for ICN draft-yao-icnrg-naming-routing-00 Abstract In ICN (Information-centric network), everything is an identifiable object with a name, therefore the number of name prefixes is a few orders of magnitude higher than that in current BGP routing table. Towards scalable routing in ICN, we propose a name scheme, called container assisted naming. With this scheme, an object name consists of two components: a content name which uniquely specifies the object within certain scope, and one or more containers which define access relationships to the object. This document illustrates the concept of container and how it assists scalable routing in ICN. 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/1id-abstracts.html The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html Copyright and License Notice Yao, et al. Expires August 21, 2013 [Page 1] INTERNET DRAFT ICN-Naming-Routing February 17, 2013 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 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 Design Principles . . . . . . . . . . . . . . . . . . . . . . . 3 1.1 Naming in ICN . . . . . . . . . . . . . . . . . . . . . . . 3 2 Container-assisted Naming . . . . . . . . . . . . . . . . . . . 3 2.1 Container . . . . . . . . . . . . . . . . . . . . . . . . . 3 2.2 Container Assisted Naming Formats . . . . . . . . . . . . . 4 2.3 Resolving Container . . . . . . . . . . . . . . . . . . . . 5 3 Container Assisted Forwarding . . . . . . . . . . . . . . . . . 6 3.1 Container Assisted Forwarding Procedure . . . . . . . . . . 6 3.1.1 Forwarding with full container resolution . . . . . . . 6 3.1.2 Forwarding with iterative container resolution . . . . . 6 3.2 Scalable Container Assisted Routing . . . . . . . . . . . . 7 3.2.1 Topology oriented containers . . . . . . . . . . . . . . 8 3.2.2 Non-topology oriented containers . . . . . . . . . . . . 8 4 Container Assisted Mobility . . . . . . . . . . . . . . . . . . 9 4.1 Container Assisted Terminal Mobility . . . . . . . . . . . . 9 4.2 Container assisted network mobility . . . . . . . . . . . . 10 5 IANA Considerations . . . . . . . . . . . . . . . . . . . . . . 11 6 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . 11 7 References . . . . . . . . . . . . . . . . . . . . . . . . . . 11 7.1 Normative References . . . . . . . . . . . . . . . . . . . 11 7.2 Informative References . . . . . . . . . . . . . . . . . . 11 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 13 Yao, et al. Expires August 21, 2013 [Page 2] INTERNET DRAFT ICN-Naming-Routing February 17, 2013 1 Design Principles 1.1 Naming in ICN Name plays a critical role in serving many fundamental functions in ICN: a unique name identifies a mutable or immutable content or information object; it is used to look up and access data in network cache; and it is used for routing and forwarding. Therefore, naming is the foundation for ICN architecture. We follow several principles for defining a naming scheme in ICN: -Unique: A name uniquely identifies an object or entity within some scope (e.g., within a domain or the entire Internet). -Locatable: A name enables interested entities to locate the identified object in a network. For this purpose, the name is either routable to reach the object, or includes information to derive the routable location(s) of the object. -Location-independent: identified object may be served by any node that has the object, which is independent of location or original source of the object. -Scalable Routing: The number of potential prefixes in global content or information object namespaces is several orders of magnitude larger than that in IP address namespace [Cisco-Name]. Therefore, ICN name should support routing scalability. 2 Container-assisted Naming 2.1 Container The container component in our naming scheme is appended to the original content name to assist routing. This naming scheme is not restricted to the hierarchical [NDN] or flat name [DONA]. A container is a space where content or information objects reside. A container in an ICN name can be one of the following: -A content or object identifier prefix, e.g., Huawei.com/blog; -An enterprise or organization name, e.g., Huawei.com, tsinghua.edu; -A host or a device such as a mobile phone or a content storage device, e.g., chinamobile/johndoe/iphone; -A mobile network, such as airplane, train, e.g., Airchina/ca1314; -A network domain, e.g., cn, cn/gd, cn/gd/sz. Access Container: If container A is contained in container B, and Yao, et al. Expires August 21, 2013 [Page 3] INTERNET DRAFT ICN-Naming-Routing February 17, 2013 container B has the routing entry to container A, container B is defined as the access container for container A. One container can have multiple access containers, and it can provide access service to multiple other containers as while. Base Container: The smallest container that can be used to assist routing for other container(s) is defined as the base container of the content. One content can have multiple base containers, such as multi-homing scenario. 2.2 Container Assisted Naming Formats A container assisted name can be expressed in a Directed Acyclic Graph or a tree as Figure 1 shows. +----+ +----+ |Name| |Name| / +----+ \ / +----+ \ / | \ / | \ +---------++---------++---------+ +---------++---------++---------+ |container||container||container| |container||container||container| | A || B || C | | A || B || C | +---------++---------++---------+ +---------++---------++---------+ \ / \ / | \ +---------+ +---------+ +---------++---------++---------+ |container| |container| |container||container||container| | D | | E | | D || D || E | +---------+ +---------+ +---------++---------++---------+ DAG TREE Figure 1.Container assisted naming As illustrated in Figure 1, the content name can be hierarchical or flat, container A, container B, and container C are the base containers, container D is the access container for A, and container D and container E are the access containers for B. As can be seen from figure 1, base containers A, B, C provide access to the content or information objects directly. These base containers may locate in or logically access to other containers, namely access containers. The base containers may be referred to as "first layer/depth containers" in the DAG or TREE, and their access containers may be referred to as "second layer/depth containers". Similarly, the access containers for the "second layer containers" may be called "third layer containers". In an ICN request packet, we propose a new content name format by using depth-first traversal of the container access relationship tree (hereinafter referred to as CART). The name shown in Figure 1 can be represented as the following: Yao, et al. Expires August 21, 2013 [Page 4] INTERNET DRAFT ICN-Naming-Routing February 17, 2013 Name = {content name | container A || container D | container B || container D || container E | container C}, Where "|" is container separator. Each node of the tree is listed in the sequence of depth-first traversal, and separated by a separator "|". As the depth increases, the number of separators also increases. A container at higher layer provides access service for the ones at lower layer. The depth of a CART has no theoretical limitation. 2.3 Resolving Container The location of a container can change from time to time, the same as its access containers. In order to avoid frequent changes in containers and guarantee the name persistency, we propose container resolution, which allows a container to dynamically register and query its access containers from a resolution system. Container Resolution System is a distributed system composed of several container resolution servers deployed in the network to store the mapping relationship between a container and its access containers. The system supports dynamic register and query operations. A container resolution request can be initiated by a content consumer or intermediate network node, when the request carries a resolvable container. A container in a name or in a resolution result can carry an attribute "resolvable", if "resolvable = yes", this container can be further resolved in the resolution system to get its access container(s); if "resolvable = no", it is not resolvable; that is, it may be the deepest level container in the resolution tree. The default value is set as "resolvable = no". A resolved container from resolution system can carry the following two attributes: -- Cacheable: defines whether the resolution result can be cached in the network thus can be shared with other nodes or consumers. The default value is set as "cacheable = no". -- Time To Live (TTL): defines the fresh time a resolved container result can live in the network. The default value is set as "TTL = 0", namely uncacheable. If a resolved container from the resolution system is also resolvable, the container resolution process is iterated. Yao, et al. Expires August 21, 2013 [Page 5] INTERNET DRAFT ICN-Naming-Routing February 17, 2013 3 Container Assisted Forwarding 3.1 Container Assisted Forwarding Procedure When a request is received, an ICN router first checks the content store for a matched content with the content name in the request packet. If a matched content is acquired, it is returned to the consumer or the preceding router. If there is no matched content in content store, the router looks up its FIB for outbound faces. The forwarding decision is made based on content name first. If there is no match in the FIB, the decision is then made based on carried container(s) in the name. There can be two ways to assist forwarding with containers by the router. 3.1.1 Forwarding with full container resolution The procedure of forwarding with full container resolution can be described as follows: Firstly, the router checks whether there is a container carried in the request. If not, it forwards the request to the default routing entry or drops it. When there is a container carried, the router checks whether the request includes resolvable container or not. If "yes", the router initiates a container resolution request to the resolution system. The result can be responded either by a server in the resolution system or an intermediary's cache where a previous resolution result resides. If the resolved container is also resolvable, the resolution process is iterated by the router with the result container(s). When all resolvable containers are resolved, the complete set of container(s) including the carried ones in the name and the resolved ones from the resolution system are used to forward the request. The traversal order can be depth-first or can be breadth-first. In case one of these containers matches a FIB entry, the request is forwarded to the corresponding outbound interfaces. Otherwise, the request is forwarded to default outbound faces or dropped. 3.1.2 Forwarding with iterative container resolution The procedure of forwarding with iterative container resolution can be described as follows: Firstly, the router checks whether there is at least one container carried in the request. If there is not, the request is forwarded to default outbound interfaces or dropped. Yao, et al. Expires August 21, 2013 [Page 6] INTERNET DRAFT ICN-Naming-Routing February 17, 2013 For all carried containers, the router matches them with its FIB entries, if one container matches, the request is forwarded according to the matched outbound faces. When the carried container(s) have no match in FIB, the router checks whether one of the carried containers is resolvable. If yes, it sends container resolution request to the resolution system to get the access container for the resolvable container(s). After that, the router matches the resolved container(s) with FIB. When one container matches an FIB entry, it forwards accordingly. If there is no match, the container resolution can be iterated with other resolvable containers in the request. When there is no more resolvable container in the request, the request can be forwarded to default outbound faces, or dropped. 3.2 Scalable Container Assisted Routing ____............____ _,.,--''' `'`--..__ _,--' cn `-.._ ,-' ____...........___ `.. ,-' _,.--'' `'--.._ `. / ,-' _________ `-. `. .' ,'_..------.._ ,,-'' `'-.. `. \ |,.--'''''''--.. | [ cn/gd/sz \ `._ cn/gd/gz _,' \ | [ cn/bj ]\ '-.._ _ __ _ / `'---------'' / | `-.__ . __.-' `._ , ,' / `. `''|''' `.._ ,' cn/gd _.-' / `. | ,'--...i__ ____..--'' ,' `..| ,' `''''''''' ,-' |-.. ,' _,--' | `--.,i __..--' | ,' `'`--+-..........;-.--''' | ,' | ,' _,..--------...__ | ,' ,-'' _,.-----.._ `-._ '__.....__ ,' .' us/ca `. \ ,-' `':'-'-'-''-''''-'-'-'-'-'''. ,- | / hostsrv.com \ i. `'-----'' ,' ` ' `-.,i _,.-' `-.__ __.-' ,' `''------,'''' `'''' ........... ,' | sina.com|' `---------' Figure 2. Solution to Routing Scalability The scalability of name-based routing in ICN can be well addressed by Yao, et al. Expires August 21, 2013 [Page 7] INTERNET DRAFT ICN-Naming-Routing February 17, 2013 containers. We divide containers into two categories: topology oriented and non-topology oriented. 3.2.1 Topology oriented containers Topology oriented containers aggregate naturally. For example, as illustrated in Figure 2, the whole network of China can be viewed as a national level container "cn", and province level containers such as "cn/gd" for Guangdong province and "cn/sd" for Shandong province are contained in "cn". Similarly, a city level container such as "cn/gd/sz" is contained in "cn/gd". Giant ISPs can also be treated as topology oriented containers. For example, China Telecom, as a top level container "ct", contains "ct/gd", which further contains "ct/gd/sz". As LPM is used in FIB matching, a routing entry for a container may only propagate within the network domain of its access containers. For example, a routing entry for "cn/gd" does not need to propagate out of "cn". In this case, a core router in the network domain of "us" with only a routing entry "cn" can forward all the packets with "cn" as a container prefix. Obviously the size of FIB can be greatly reduced due to the recursive aggregation of topology oriented containers. Therefore, the routing entries created by topology oriented containers are the basis for FIB compression. 3.2.2 Non-topology oriented containers According to the scale-free property of the Internet, we further divide non-topology oriented containers into popular ones and non- popular ones. The majority of the non-topology oriented containers have non-popular content and low visiting volume, such as small companies and organizations, home networks, and personal digital devices. The large number of this type of containers is the major cause of the routing scalability problem. Since these containers do not have to propagate outside of their access containers, we can greatly reduce the size of FIBs in core routers with access containers. For example, the corporate network of a company "hostsrv.com" locates in three different places, "cn/gd", "cn/beijing", "us/ca", which can be seen as three topology oriented containers that provide access service to "hostsrv.com". The route to "hostsrv.com" exists only inside these three containers, and any outside router can use these three containers to assist packet routing in order to reach "hostsrv.com". A small portion of non-topology oriented containers has several orders of magnitude higher visiting volume than others, such as large corporations (e.g., huawei.com) and large portal websites (e.g., Yao, et al. Expires August 21, 2013 [Page 8] INTERNET DRAFT ICN-Naming-Routing February 17, 2013 sina.com). The small number of these frequently visited containers does not cause scalability problems for core routers. To conclude, with the container assisted naming scheme and routing, the size of FIBs in core routers is determined by the number of "aggregated topology oriented containers" and "frequently visited non-topology oriented containers", which could be smaller than the size of routing table in current Internet's core routers. 4 Container Assisted Mobility 4.1 Container Assisted Terminal Mobility By terminal we mean either consumer side terminal devices or data source side terminal devices or hosts. In the scenario where a data source terminal is static and a consumer terminal is moving, the consumer can resend requests to fetch the latest data packets after the movement. In the scenario where the data source is moving, a carried container in data request packets can assist the forwarding during the data source movement. .---. _.----------. |E1 | _.----------. ,-'' .---. `--. `---' ,-'' `--. ,' |E2 | `. ,' `. / `---' \ / \ ( A O---O ) ( B ) | C |<--------`--------- / `. O---O,' `. ,' '--. _.-' '--. _.-' `----------'' `----------'' Figure 3. Data source terminal movement As Figure 3 shows, if the data source in container C moves within its access container B, its routing update is contained within the access container, and there is no routing update out of container B. If the data source moves out of its access container B to a new container A, it needs to register a new route in the new access container A, and updates the access container information in the resolution system. After this, its data consumers or on-path routers can acquire the latest base container (i.e., container A) with container resolution. The register process can refer to [Huawei- Resolution]. As shown in Figure 3, during the movement, if a data consumer E2, Yao, et al. Expires August 21, 2013 [Page 9] INTERNET DRAFT ICN-Naming-Routing February 17, 2013 which resides within the same access container (i.e., container A) as the data source in container C, sends a request to retrieve the data, the request packet can be forwarded straightly to the mobile source. However, if a router E1 outside the access container A receives such request, it cannot find the route directly by the carried container in the name (i.e., container C). Therefore, the router sends resolution request to obtain the data source's access container. After gets the access container A, the router forwards the requests to A firstly, and then to destination C by content object name or carried base container(s). 4.2 Container assisted network mobility A mobile container can provide access to a set of containers that moves together with it, for example, a train, airplane, or ship can provide access service to its passengers. This can be seen as network mobility. .---. _.-.---.----. |E1 | ,---------. ,--'' |E2 | `---. `---' ,' __ `. ,' `---'____ `. __..-'' ) / ,-'' ``-. __.--'' `. D ,' / A ,' .---. __.--:' \ `-+-------' ( | B | E3| | ) / \ \ `---' O--O ' / / ,---------. \ `. |C | ,' / / ,' `. `. `-..____O--O' ,' / ( ) '---. i.--' / `.' F ,' `----------'' `. / .' `---------' `. / .' `. ,-+---.' ;: `. ( G ) `. ,' `-----' Figure 4. Network mobility As Figure 4 shows, when container B moves, the processing is similar as the data source movement in previous case. If container B moves insides of its access container, i.e., container D, routing update only propagates within this container. If B moves out of its access container, it needs to register a new routing to its new access container, e.g., container A, and updates its new access container relationship in container resolution system. When container B moves across several containers, it only needs to update its access Yao, et al. Expires August 21, 2013 [Page 10] INTERNET DRAFT ICN-Naming-Routing February 17, 2013 containers (e.g., from D to A) in the resolution system, while all contained containers (e.g., container E3 and C) within itself do not need to do any update since their routing in the network (inside of container B) and their access container relationships do not changed. With this container assisted routing, the updating and querying frequency to the resolution system can be significantly reduced. Consider the mobile network B as a high-speed train. Along with its inside containers (E3 and C), it moves from original access container D to a new access container A. During this movement, if a consumer within the same mobile network E3 requests for data in contained container C, the request is forwarded directly. If a consumer in container E2, which is outside B, requests data in container C, the router in the access container A cannot forward the request directly by the content name. It then sends resolving request to the resolution system. With the resolved container B, the router can forward the request to the mobile network B, which in turn forwards to data source C with content name or carried container. If a consumer in container E1, which is outside the access container of the mobile network B, requests data in contained container C, it needs two-level resolution: it obtains the mobile network B with the first level resolution, and the network's new access container A with the second. Routers can route the request with the second resolution result (i.e., container A), and then with the network container B, and finally to the destination container C with content object name in request or carried base container(s). Note that the number of resolution level is not restricted in our scheme, which is decided by access relationships among containers. 5 IANA Considerations No IANA consideration for this draft. 6 Conclusions 7 References 7.1 Normative References 7.2 Informative References [Cisco-Name] NDN and IP Routing, Can it Scale? http://trac.tools.ietf.org/group/irtf/trac/raw- attachment/wiki/icnrg/IRTF%20- Yao, et al. Expires August 21, 2013 [Page 11] INTERNET DRAFT ICN-Naming-Routing February 17, 2013 %20CCN%20And%20IP%20Routing%20-%202.pdf [CCN] V. Jacobson et al. Networking named content. Proceedings of the 5th ACM International Conference on Emerging Networking Experiments and Technologies (CoNEXT 2009). NY: ACM; 2009; 1-12. [DONA] T. Koponen, M. Chawla, B.-G. Chun, A. Ermolinskiy, K. H. Kim, S. Shenker, and I. Stoica. A Data-Oriented (and Beyond) Network Architecture. In Proc. of SIGCOMM, 2007. [Huawei-Resolution] Draft-ietf-icnrg-icn-container-resolution-system-00.txt. Yao, et al. Expires August 21, 2013 [Page 12] INTERNET DRAFT ICN-Naming-Routing February 17, 2013 Authors' Addresses Chunfeng Yao Huawei Technologies Huawei Building, No.156, BeiQing Rd., Haidian District Beijing, 100095 P.R. CHINA EMail: chunfengyao@huawei.com Rong Wang Huawei Technologies Huawei Building, BanTian, LongGang District Shenzhen, GuangDong 518129 P.R.CHINA EMail: WANG.RONG@huawei.com Yuanzhe Xuan Huawei Technologies Huawei Building, BanTian, LongGang District Shenzhen, GuangDong 518129 P.R.CHINA EMail: xuanyuanzhe@huawei.com Zhefeng Yan Huawei Technologies Huawei Building, BanTian, LongGang District Shenzhen, GuangDong 518129 P.R.CHINA EMail: yanzhefeng@huawei.com Yao, et al. Expires August 21, 2013 [Page 13]