Internet DRAFT - draft-yao-icnrg-naming-routing

draft-yao-icnrg-naming-routing



 



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]