Network Working Group J. Lee Internet Draft ETRI Intended status: Informational February 15, 2014 Expires: August 2014 Scalable Domain-based Routing Scheme draft-lee-icnrg-domainbasedrouting-00.txt Status of this Memo This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79. This document may contain material from IETF Documents or IETF Contributions published or made publicly available before November 10, 2008. The person(s) controlling the copyright in some of this material may not have granted the IETF Trust the right to allow modifications of such material outside the IETF Standards Process. Without obtaining an adequate license from the person(s) controlling the copyright in such materials, this document may not be modified outside the IETF Standards Process, and derivative works of it may not be created outside the IETF Standards Process, except to format it for publication as an RFC or to translate it into languages other than English. 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 August 15, 2014. Lee Expires August 15, 2014 [Page 1] Internet-Draft Scalable Domain-based Routing February 20144 Copyright Notice Copyright (c) 2014 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. Abstract This memo describes a scalable routing scheme for information centric networks. Moving the focus from "nodes" to "information objects" raises scalability issue because aggregation of flat name for objects is not easy task and the number of addressable information objects is so huge than the IP address space. For scalable routing, we propose hierarchically-organized domain architecture. A domain is a "logical group" of information objects and each domain has its own ID. The concatenation of domain IDs from top level domain to the current domain plays the role of "locator". Thus, we can get scalable routing table and it is more scalable by means of "topology reduction". More challenging issue is name-based forwarding. It is hard to aggregate forwarding table due to flat name space, therefore we propose "reactive path setup". Table of Contents 1. Introduction ................................................ 3 2. Conventions used in this document............................ 3 3. Terminologies ............................................... 3 4. Scalable Domain-based Routing................................ 4 4.1. Hierarchically-organized Domain Architecture............ 4 4.1.1. Locator ........................................... 5 4.2. Name-Locator Mapping System (NLMS) (name resolution step)5 4.3. Domain-based Routing.................................... 5 5. Name-based Forwarding (discovery step)....................... 6 6. Delivery step ............................................... 6 7. Security Considerations...................................... 6 8. IANA Considerations ......................................... 7 9. References .................................................. 7 9.1. Informative References.................................. 7 Lee Expires August 15, 2014 [Page 2] Internet-Draft Scalable Domain-based Routing February 20144 1. Introduction ICN routing locates a data object based on its name which is initially provided by a requestor. Currently, the Internet is addressing on the order of 10^9 nodes, whereas the number of addressable ICN objects is expected to be several orders of magnitude higher [ICNRG charter]. Therefore, it raises scalability issues in routing based on locator and forwarding based on name. ICN routing may comprise 3 steps: a name resolution step, a discovery step, and a delivery step [ICN challenges]. Name resolution step is not the main concern of this memo, but scalable routing in discovery and forwarding in delivery are mainly described. In this memo we propose hierarchically-organized domain architecture with topology reduction for scalable routing, and reactive path setup for scalable forwarding. 2. 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 [RFC2119]. In this document, these words will appear with that interpretation only when in ALL CAPS. Lower case uses of these words are not to be interpreted as carrying RFC-2119 significance. In this document, the characters ">>" preceding an indented line(s) indicates a compliance requirement statement using the key words listed above. This convention aids reviewers in quickly identifying or finding the explicit compliance requirements of this RFC. 3. Terminologies o Domain: a logical group of "information objects" which have similar characteristics (E.g. geographical region, same type of contents, similar category of contents etc.) or "other domains". o Domain Gateway: a border gateway for a domain. This domain gateway exchanges or filters LSAs (Link-State Advertisement) for domain- based routing, and forwards control messages or data object to the next-hop domain gateway. Lee Expires August 15, 2014 [Page 3] Internet-Draft Scalable Domain-based Routing February 20144 4. Scalable Domain-based Routing 4.1. Hierarchically-organized Domain Architecture Movie (Id:0x0A) +-----------------------------------------------------------------+ | <---------> | | +-----------< user A > | | | <---------> | | | ^^^^^^^^ | | | +--------------------| NLMS | | | SF (Id:0x0B) | | ^^^^^^^^ | | +-------------------[GW #1]--------------------------------+ | | | | | | | | | | | | | | | | | | +-------------------------------+ | | | | North America | | | | | | (Id:0x0C) | | | | | | +----------------[GW #2]-+ Asia Server (Id:0x0D) | | | | | | | | +=====================+=+ | | | | | | | | [Snowpiercer] | | | | | | US server (Id:0x0D)| | | [2009: lost memories]| | | | | | +=============+ | | | .... | | | | | | | [StarWars] | | | | | | | | | | | [Tron] | | | | | | | | | | | [RoboCop] | | | | | | | | | | | .... +-----+ | +=======================+ | | | | | | | | | | | | | | +=============+ | | | | | | | | | | | | | | Canada server | | | | | | | (Id:0x0E) | | | | | | | +===============+ | | | | | | | | [Cube] | | | | | | | | | .... +---+ | | | | | | | | | | | | | | +===============+ | | | | | +------------------------+ | | | +----------------------------------------------------------+ | +-----------------------------------------------------------------+ Figure 1 Sample domain architecture In this scheme we compose network as a set of domains, and each of which may be further decomposed into smaller domains recursively. A domain is a logical group of information objects which have similar characteristics or other sub-domains. Figure 1 shows an example of Lee Expires August 15, 2014 [Page 4] Internet-Draft Scalable Domain-based Routing February 20144 domain architecture. In our scheme contents server itself is also a domain (see US server, Canada server, and Asia server) 4.1.1. Locator Each domain has its own ID (domain Id) and a concatenation of domain IDs from top level domain to the current domain plays the role of "locator". (E.g. locator for domain North America is 0x0A:0x0B:0x0C). 4.2. Name-Locator Mapping System (NLMS) (name resolution step) Name resolution step is done by querying locator mapped to a name to the NLMS. For fast processing we use bloom filter technique. NLMS is composed as a form of tree. More detailed structure is out of scope of this memo (it will be written as another I-D). 4.3. Domain-based Routing Each domain gateway (including contents server, of course) runs "modified link-state routing protocol". Each LSA transfers "locator" instead of IP prefix. Thus, locator appears in destination field and IP address of a domain gateway takes next-hop field of routing table entries. Unlike existing link-state routing protocol, each domain gateway forwards LSA to the other domain according to the following filtering rule: o LSAs in tier N domain are forwarded to all domain gateways which belong to tier N o LSAs in tier N-1 are injected to tier N o LSAs in tier N+1 are filtered, LSA which only includes aggregated locator is injected to tier N instead. (E.g. GW #2 delivers LSA which includes 0x0A:0x0B:0x0C) This results in topology reduction effect. Therefore, each domain gateway would have topology graph which is as reduced as possible in its current position. Lee Expires August 15, 2014 [Page 5] Internet-Draft Scalable Domain-based Routing February 20144 +----------------+--------------+--------+ | Destination | nexthop | out if | +----------------+--------------+--------+ | 0x0A:0x0C | GW #2's IP | if0 | +----------------+--------------+--------+ | 0x0A:0x0B:0x0D | - | lo | +----------------+--------------+--------+ Figure 2 Routing table portion of Asia server 5. Name-based Forwarding (discovery step) As we described earlier it is very difficult to aggregate flat names. Thus we chose "reactive path setup" for scalability of forwarding table. Detailed procedure of reactive path setup is as follows: 1. A user issues request for certain named content. This request is forwarded to the default domain gateway ("GW #1" in Figure 1). 2. If the default gateway receives the request from user, it checks there is any forwarding cache entry matching with the name. If there is any, it forwards the request to the next-hop domain gateway according to the found forwarding cache. 3. If there is none, it queries current locator for the name to the NLMS. After getting the locator for the name, the domain gateway looks up its routing table entry matching the locator. Finally a forwarding cache for the name is made by using next-hop information of found routing table entry. If this is the first domain gateway which doesn't have forwarding cache for the name, the domain gateway keeps user request for a while and sends "path discovery message" including "locator". This will reduce unnecessary NLMS lookup. The forwarding cache is managed in "reactive" manner. Unused cache entries for certain time will be removed immediately. 6. Delivery step Once user request arrives at the contents server, it can send data object to the source address of request. 7. Security Considerations TBD. Lee Expires August 15, 2014 [Page 6] Internet-Draft Scalable Domain-based Routing February 20144 8. IANA Considerations TBD. 9. References 9.1. Informative References [ICNRG charter] http://irtf.org/icnrg [ICN Challenges] D.Kutscher, "ICN Research Channelges", internet- draft, July 2013 [aRoute] Ahmed, Reaz, Md Faizul Bari, Shihabur Rahman Chowdhury, Md Golam Rabbani, Raouf Boutaba, and Bertrand Mathieu. "Route: A Name Based Routing Scheme for Information Centric Networks." In IEEE International Conference on Computer Communications (INFOCOM) Mini-Conference, 2013. Authors' Addresses Joo-Chul Lee ETRI 161 Gajeong-dong, Yuseong-gu, Daejon Phone: Email: rune@etri.re.kr Lee Expires August 15, 2014 [Page 7]