Bloom Filter-based Flat Name Resolution System for ICN
draft-hong-icnrg-bloomfilterbased-name-resolution-00

ICNRG                                                                 J. Hong
Internet Draft                                                             ETRI
Intended status: Informational                                  W. Chun
Expires: January 2015                                               HUFS
                                                                          H. Jung
                                                                              ETRI
                                                                    July 20, 2014

           Bloom Filter-based Flat Name Resolution System for ICN
          draft-hong-icnrg-bloomfilterbased-name-resolution-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 January 21, 2015.

Hong                  Expires January 21, 2015                [Page 1]
Internet-Draft         Bloom filter-based NRS                July 2014

Copyright Notice

   Copyright (c) 0000 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.

Abstract

   In information-centric networking (ICN), uniquely identifiable and
   location independent names are assigned directly to the named data
   which raises scalability issues and they get even worse with flat
   names. Accordingly, name resolution system required for lookup-by-
   name routing in ICN has to be designed to scale, also considering
   mobility support. In this draft, a bloom filter-based flat name
   resolution system (B-NRS) is proposed where the bloom filter as an
   aggregated form of names and hierarchical structure of the B-NRS are
   exploited to address the scalability issues.

Table of Contents

   1. Introduction ................................................ 3
   2. Bloom filter-based name resolution system (B-NRS)    ........ 4
      2.1. System structure........................................ 4
      2.2. Key operations ......................................... 5
         2.2.1. Name registration.................................. 5
         2.2.2. Locator Update..................................... 5
         2.2.3. Lookup ............................................ 6
   3. Performance analysis......................................... 6
   4. Security Considerations...................................... 6
   5. IANA Considerations ......................................... 7
   6. Conclusions ................................................. 7
   7. References .................................................. 7
      7.1. Normative References.................................... 7
      7.2. Informative References.................................. 7
      A.1. Authors' Addresses...................................... 9

Hong                  Expires January 21, 2015                [Page 2]
Internet-Draft         Bloom filter-based NRS                July 2014

1. Introduction

   In contrast to the host-centric networking in the current Internet,
   the primary communication object in information-centric networking
   (ICN) is named data, where uniquely identifiable and location
   independent name is assigned directly to the named data. This shift
   raises scalability issues to a new level. The current 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]. Accordingly, name resolution
   system required both for lookup-by-name routing in ICN [ICN
   Challenges] and for ICN-IoT architecture [ICN-IoT] has to be
   designed to scale, also considering mobility support.

   In this draft, we propose a bloom filter-based flat name resolution
   system (B-NRS) which maintains and resolves the binding between
   names and locators, i.e. B-NRS takes a name as its input and
   produces the locator sets that the name is currently associated with.
   We assume that the locator independent names are flat since the flat
   names provide some advantages compared to hierarchical ones, such as
   higher flexibility, simpler name allocation and benefits in terms of
   persistency and privacy [Ghodsi, ITU]. On the other hand,
   scalability becomes the most important challenge on designing the
   NRS supporting flat names. It is because of the ever increasing
   number of names in the network and no possible way to compactly
   represent the flat names such as the aggregation in IP addresses.

   In order to address the scalability issue in designing the NRS for
   flat name, we need to aggregate names in any shape of type. One
   popular technique for flat name is Distributed Hashing Table (DHT)
   based approach [Hanka, Luo, Ahlgren, Mathy], where multiple servers
   form circular linked list and the bindings are stored in the
   appropriate server. However, the DHT technique has some drawbacks;
   the binding must be stored in a server other than the owner's, which
   causes a serious trust problem related to the authority issue  and
   lookup message may be propagated through the long paths.

   In this draft, to overcome the drawbacks of DHT, we exploit the
   bloom filter as an aggregated form of names and hierarchically
   construct the B-NRS. One of the major benefits of the bloom filter
   is a fixed constant time of insertion and search which is completely
   independent of the number of names already in the set. Another
   important and powerful property of bloom filter is the efficient
   support for union of bloom filters with the same size and set of
   hash functions which can be implemented with bitwise OR. However,
   bloom filter also has some drawbacks; false positive and no member
   deletion. Although there is no way to get rid of the false positive,

Hong                  Expires January 21, 2015                [Page 3]
Internet-Draft         Bloom filter-based NRS                July 2014

   it can be minimized by choosing the right parameters. The deletion
   problem is also taken care by periodic reconstruct of the bloom
   filters or by using variants of the bloom filter such as the
   counting bloom filter.

   We note that the B-NRS in this draft does not require any specific
   mechanism for registering names, since names have no structure and
   can be registered to any B-NRS server with no constraint. Thus, the
   B-NRS needs only lookup mechanism. Whereas in the DHT-based system,
   the lookup message for a name is forwarded by the same way how to
   register the name.

2. Bloom filter-based flat name resolution system (B-NRS)

   We propose a bloom filter-based name resolution system (B-NRS) for
   supporting flat name which maintains and resolves the binding
   between names and locators.

2.1. System structure

   We construct the B-NRS hierarchically by defining a network of B-NRS
   servers, which consists of a forest by several disjoint trees. The
   network of B-NRS servers is defined by both parent-child and peering
   relationships.

   A B-NRS server consists of a name lookup table which stores the
   binding between names and locators for all names which are directly
   registered to the BRS server. The lookup table takes an name as the
   input and produces its associated locator sets as the output.

   We utilize bloom filters as an aggregated form of names at each B-
   NRS server. B-NRS servers announce their name set to the other B-NRS
   servers. Instead of announcing the whole list of names, bloom filter
   as an aggregated form of names is announced. When announcing its
   name set to its peers or parents, the B-NRS server announces the
   union of name sets of all child B-NRS servers. Union of child name
   sets can be built by using the characteristic of bloom filer that
   bloom filter for union of sets can be built merely by bitwise 'OR'
   operation on all the sets. Thus, each B-NRS server stores bloom
   filters for itself, from children, and from peers.

   We note that the forest of B-NRS servers retains the loop-free
   property for the use of bloom filter.

   At the top of the trees, the B-NRS servers are fully peered, which
   means that each server shares its knowledge of all names that it
   manages with its the peers. A leaf B-NRS server knows every single

Hong                  Expires January 21, 2015                [Page 4]
Internet-Draft         Bloom filter-based NRS                July 2014

   name/locator pair that it manages but nothing else. The intermediate
   B-NRS servers know the name/locator pair for all names that are
   directly registered to them and also possess only information about
   the names that their descendant and peer B-NRS servers manage.

2.2. Key operations

2.2.1. Name registration

   When a communication entity attempts to join the network, it must
   register itself in at least one B-NRS server. In this draft, it is
   allowed that the communication entity can be registered in any
   arbitrary B-NRS server since names have no structure.

   Upon receiving the registration request from the communication
   entity, the B-NRS server registers the name to its lookup table. The
   locators for the name are stored in the table when the communication
   entity for the name is actually present into the network. We
   separate this as the operation of locator update from the name
   registration.

   The name registration is along with bloom filter update. When a
   communication entity is registered in a B-NRS server, the
   registration information is extracted from its name using the hash
   functions for its bloom filter and inserted into its own bloom
   filter first and then the B-NRS server updates bloom filters for its
   parents and peers, where this recursion holds until bloom filters at
   the top of trees are completely updated.

   When names are deleted from the lookup table, we need to adopt a
   certain mechanism to update the bloom filters for the deletion since
   bloom filter cannot handle the deletion by itself. Thus, we use the
   periodic refresh technique that bloom filters with registered names
   are rebuilt periodically and followed by bloom filter updates.

2.2.2. Locator Update

   When a communication entity actually presents in the network, the
   locator update is occurred, where the gateway sends the locator
   update message to the correspondent B-NRS server and the locator
   associated with the name is stored in the lookup table. If the name
   has multiple locators, then they are stored as a set of locators for the
   name. Through the bloom filter test of the name, the locator update
   messages are forwarded into the lookup table where the name is
   stored.

Hong                  Expires January 21, 2015                [Page 5]
Internet-Draft         Bloom filter-based NRS                July 2014

   When the communication entity depresents from the network, the
   locators for the name is deleted from the lookup table by the
   locator update message as well. Thus, changing locators has no
   effect on the structure of the B-NRS and mobility is easily
   supported.

2.2.3. Lookup

   The lookup operation is to find the locator information for a given
   name. The simplest case is when the source object tries to
   communicate with the destination object registered in the same B-NRS
   server. B-NRS server always searches for the destination name in its 
   own lookup table first so the locator information is acquired at the
   first lookup in such a case.

   A harder, but more interesting, case is when the destination object
   is registered in the other B-NRS server with the source object. In
   this case, the B-NRS server would quickly learn that the destination
   object is not registered in the same B-NRS server by a simple search
   of its lookup table. Then, it searches bloom filters for its child
   and peer B-NRS servers. If none of the bloom filters return a
   positive answer, the lookup request message is forwarded to its
   parent B-NRS server. On the other hand, if any of bloom filters
   return a positive answer, the lookup request message is forwarded to
   every B-NRS server that corresponds to the bloom filters with
   positive answers. We note that because of the false positives of the
   bloom filter, multiple bloom filters may return positive answers.

   This search is done recursively, and the locator information for the
   destination name can eventually be found. Once the locator
   information is found, it is delivered to the source object by the
   lookup reply message which takes the reverse path of the lookup
   request message.

3. Performance analysis

   TBD

4. Security Considerations

   TBD

Hong                  Expires January 21, 2015                [Page 6]
Internet-Draft         Bloom filter-based NRS                July 2014

5. IANA Considerations

   TBD

6. Conclusions

   In this draft, we proposed a bloom filter-based name resolution
   system (B-NRS) supporting flat name. The proposed system is a
   network of B-NRS server in a forest by multiple trees with peering
   relationship. Scalability issue was addressed by information
   compression using bloom filters to represent collection of names of
   the child B-NRS server, where the bloom filter was exploited to
   overcome some drawbacks of DHT-based system. The peering
   relationship was adopted to alleviate the traffic load to the B-NRS
   servers at the upper part of the B-NRS.

7. References

7.1. Normative References

7.2. Informative References

   [ICNRG charter]  http://irtf.org/icnrg

   [ICN Challenges] D.Kutscher, S. Eum, K. Pentikousis, I. Psaras, D.
             Corujo, D. Saucez, T. Schmidt, and M. Waehlisch, "ICN
             Research Challenges ", draft-kutscher-icnrg-challenges-02,
             February 2014.

   [ICN-IoT] Y. Zhang, D. Raychadhuri, R. Ravindran, and G. Wang, "ICN
             based Architecture for IoT", draft-zhang-iot-icn-
             architecture-01, June 2014.

   [Ghodsi] A. Ghodsi, T. Koponen, J. Rajahalme, P. Sarolahti, and
             Shenker, "Naming in Content-Oriented Architectures," In
             Proceedings of the SIGCOMM ICN'11, August 19, 2011,
             Toronto, Ontario, Canada.

   [ITU]     International Telecommunication Union (ITU), "ITU-T
             Recommendation Y.3031 - Identification framework in future
             networks," available at: http://www.itu.int/rec/T-REC-
             Y.3031-201205-P/en, 2012.

Hong                  Expires January 21, 2015                [Page 7]
Internet-Draft         Bloom filter-based NRS                July 2014

   [Hanka]  O. Hanka, C. Spleiss, G. Kunzmann, and J. Ebersp¨acher, "A
             novel DHTbased network architecture for the next
             generation internet," Eighth International Conference on
             Networks, Cancun, Mexico, March 2009.

   [Luo]    H. Luo, Y. Qin, and H. Zhang, "A DHT-Based Identifier-to-
             Locator Mapping Scheme for a Scalable Internet," IEEE
             Transactions on Parallel and Distributed Systems, October
             2009.

   [Ahlgren] B. Ahlgren, J. Arkko, L. Eggert, and J. Rajahalme, "A node
             identity internetworking architecture," in INFOCOM 2006.
             25th IEEE International Conference on Computer
             Communications Proceedings. Washington, DC, USA: IEEE
             Computer Society, April 2006, pp. 1-6.

   [Mathy]  L. Mathy and L. Iannone, "LISP-DHT: Towards a DHT to map
             identifiers onto locators," in ReArch'08. Madrid, Spain:
             ACM, December 2008.

   [Fab1999] Faber, T., Touch, J. and W. Yue, "The TIME-WAIT state in
             TCP and Its Effect on Busy Servers", Proc. Infocom 1999 pp.
             1573-1583.

Hong                  Expires January 21, 2015                [Page 8]
Internet-Draft         Bloom filter-based NRS                July 2014

A.1. Authors' Addresses

   Jungha Hong
   ETRI
   218 Gajeong-ro, Yuseong-gu, Daejeon, Korea

   Email: jhong@etri.re.kr

   Woojik Chun
   Hankuk University of Foreign Strudies
   81, Oedae-ro, Mohyeon-myeon, Cheoin-gu, Yongin-si, Gyeonggi-do, Korea

   Email: woojikchun@gmail.com

   Heeyoung Jung
   ETRI
   218 Gajeong-ro, Yuseong-gu, Daejeon, Korea

   Email: hyjung@etri.re.kr

Hong                  Expires January 21, 2015                [Page 9]