Re: [icnrg] New Version Notification for draft-hong-icnrg-bloomfilterbased-name-resolution-01.txt

Petri Jokela <petri.jokela@ericsson.com> Sat, 27 September 2014 07:17 UTC

Return-Path: <petri.jokela@ericsson.com>
X-Original-To: icnrg@ietfa.amsl.com
Delivered-To: icnrg@ietfa.amsl.com
Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 71CF51A1A77 for <icnrg@ietfa.amsl.com>; Sat, 27 Sep 2014 00:17:56 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.3
X-Spam-Level:
X-Spam-Status: No, score=-2.3 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, HTML_MESSAGE=0.001, MIME_8BIT_HEADER=0.3, RCVD_IN_DNSWL_LOW=-0.7, SPF_PASS=-0.001] autolearn=ham
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id J2OCektg8hs8 for <icnrg@ietfa.amsl.com>; Sat, 27 Sep 2014 00:17:53 -0700 (PDT)
Received: from sessmg22.ericsson.net (sessmg22.ericsson.net [193.180.251.58]) (using TLSv1 with cipher DHE-RSA-AES256-SHA (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id B1F451A1A4C for <icnrg@irtf.org>; Sat, 27 Sep 2014 00:17:52 -0700 (PDT)
X-AuditID: c1b4fb3a-f79da6d0000008c7-46-5426649e02d0
Received: from ESESSHC014.ericsson.se (Unknown_Domain [153.88.253.124]) by sessmg22.ericsson.net (Symantec Mail Security) with SMTP id 6C.C7.02247.E9466245; Sat, 27 Sep 2014 09:17:50 +0200 (CEST)
Received: from mail.lmf.ericsson.se (153.88.183.153) by smtp.internal.ericsson.com (153.88.183.62) with Microsoft SMTP Server id 14.3.174.1; Sat, 27 Sep 2014 09:17:49 +0200
Received: from [127.0.0.1] (nomadiclab.lmf.ericsson.se [131.160.33.3]) by mail.lmf.ericsson.se (Postfix) with ESMTP id 7557D1102A3; Sat, 27 Sep 2014 10:17:49 +0300 (EEST)
Content-Type: multipart/signed; boundary="Apple-Mail=_7AA14684-2519-4DCD-95B9-4F1253442735"; protocol="application/pkcs7-signature"; micalg="sha1"
MIME-Version: 1.0 (Mac OS X Mail 7.3 \(1878.6\))
From: Petri Jokela <petri.jokela@ericsson.com>
In-Reply-To: <F8EFC212DF9A004DA18AA8FB011E42331D611152@SMTP1.etri.info>
Date: Sat, 27 Sep 2014 10:17:48 +0300
Message-ID: <3F24F5B9-BEDB-4C25-AFAB-F4DA368789A0@ericsson.com>
References: <20140917002758.31365.13695.idtracker@ietfa.amsl.com> <F8EFC212DF9A004DA18AA8FB011E42331D610CB8@SMTP1.etri.info>, <8A63F6C6-4361-4105-B1AD-04B3DCE99F6E@ericsson.com> <F8EFC212DF9A004DA18AA8FB011E42331D611152@SMTP1.etri.info>
To: 홍정하 <jhong@etri.re.kr>
X-Mailer: Apple Mail (2.1878.6)
X-Brightmail-Tracker: H4sIAAAAAAAAA+NgFvrLLMWRmVeSWpSXmKPExsUyM+Jvje68FLUQg9snpCx2zt7JZHFs50Mm ByaPrZ8fMnpM3niYLYApissmJTUnsyy1SN8ugStj3fE7jAWLnzBWbNq5nr2BcdUJxi5GTg4J AROJbz93skHYYhIX7q0Hsrk4hASOMkr87DvDCuFsYJTY8OIOlLOOUeLc+wfsIA6zwBRGiatH joP18woYSBz//pMFxBYWyJKYfeIxUBEHB5uAnsSJdYkgJqeAu8TRGdogFSwCqhI7t29jAgkz A9mNs2MghthL7Ni+kgVi1WtGiYunroNNFBHQl2jbN5MZ4lJ5iQ8fjrOD2EICahJTPjxgn8Ao OAvZRbOQXARiMwskSRz+9IcRwtaWWLbwNTOErSmxv3s5C6a4hkTnt4msELapxOujH6F6rSVm /DrIBmErSkzpfsi+gJFrFaNocWpxcW66kZFealFmcnFxfp5eXmrJJkZgfB3c8ttqB+PB546H GAU4GJV4eBWk1EKEWBPLiitzDzFKc7AoifMuPDcvWEggPbEkNTs1tSC1KL6oNCe1+BAjEwen VAOjNK/k69tXdd88bju5+vIeTtHixr3rZvcHvdWbGWLpcPSz0AQPnlkeu6+Y7/gySX5W85Xk 6PKzF29/31wVWWbYmyZYbpe7eGKA5DOJLEf9E+ev6kxfu+Nu+53c5etetmkvCK7VFJ9m9uNw caSLgf35nYmXwm0bLJWMpljwrb9Q1bb8Zu++Q/valViKMxINtZiLihMBIYyVx5ACAAA=
Archived-At: http://mailarchive.ietf.org/arch/msg/icnrg/93gZ7-oldh86ku4MylDkEXWaSY0
Cc: "icnrg@irtf.org" <icnrg@irtf.org>
Subject: Re: [icnrg] New Version Notification for draft-hong-icnrg-bloomfilterbased-name-resolution-01.txt
X-BeenThere: icnrg@irtf.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Information-Centric Networking research group discussion list <icnrg.irtf.org>
List-Unsubscribe: <https://www.irtf.org/mailman/options/icnrg>, <mailto:icnrg-request@irtf.org?subject=unsubscribe>
List-Archive: <http://www.irtf.org/mail-archive/web/icnrg/>
List-Post: <mailto:icnrg@irtf.org>
List-Help: <mailto:icnrg-request@irtf.org?subject=help>
List-Subscribe: <https://www.irtf.org/mailman/listinfo/icnrg>, <mailto:icnrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Sat, 27 Sep 2014 07:17:56 -0000

Hi, thanks for the clarifications. Unfortunately, I am not attending the Saturday meeting. I hope you have fruitful discussions there. See my reply in-line: 

On 27 Sep 2014, at 00:15, 홍정하 <jhong@etri.re.kr> wrote:

> Hi,
>  
> We can take advantage of that bloom filter size can be adjusted by the maximum number of names registered to a single NRS server to keep the FPP less than a desirable value.

> For example, the bloom filter with the size of 2MB for 10^6 entries can keep the FPP less than 0.00046. If we assume that the number of such a NRS server on the top level is 10^6 and they are fully peered, then the maximum memory required at each server is 2TB. To deal with such a size, we are considering of being supported by hardware using GPU or TCAM and we are working on it.

If you want to merge BFs at higher level (by ORing them together), you must use same size filters on each level. Filters with different sizes cannot be merged. Just to clarify, are you assuming that you are using different sizes of filters on different places in the network, or are you using one-size filters which must be optimised for the worst case? If you have different sizes of filters, you have to collect the lower layer filters to the higher layer servers and when this higher level B-NRS receives a request, it must match the item to each of the 10^6 BFs separately. If you are 

On the other hand, different sizes of filters on different B-NRS nodes would need a different set of hash functions for them. This is not a major thing, but not efficient because you have to do more hash calculations over the same item name to get correct values for different filters where we want to test the existence of the data item on a single server with multiple BFs from other B-NRSs.

If you are using same size filters on every layer to make it possible to OR them together, this requires huge filters because they must take into account also the worst case (i.e. the maximum number of information items that may be included in a single filter). 
 
> 
> As the draft [3] mentions, there are 10^9 nodes in the current Internet. The number of addressable ICN objects will be several orders of magnitude higher. This means that there will be, on average, tens of thousands of ICN objects per node. How many of the objects will be in the NRS, is not known. It is possible that some of the objects are only inside a single node and some globally available. Also, depending on the role of a node, the number of objects may be lower or higher. 
>  
> In B-NRS[3], it is not assumed that all names are globally visible. We are considering that the maximum number of names which are globally visible is 10^9 and the maximum number of B-NRS servers which are fully peered on the top level with 10^6 names for each is 10^3 ~ 10^6, which is the upper bound.

Now I must as that are you really talking about information items, not the node names. Considering the network today and what is available there, AND taking into account the new developments, such as IoT with lots of information, I guess that the amount of information items will be larger. If we have now 10^9 nodes in the network, your assumption would mean one information item published per one node (on average) globally, which is pretty low. Of course, not everything is globally visible, but still the amount looks low. 

There is also a scalability issue. What happens if the number of items still grows in the future and the filter sizes must be adjusted accordingly? If increasing the size is enough, it is probably not a big problem. But we should prepare us also for something that we cannot envision now.  

> 

> On the third level, the BFs from the ten 2nd level NRS are merged. The merged BF contains information of 2 000 000 000 objects. In theory, the 3rd level NRS can use this merged BF to check if a certain ICN object can be found in any of the 1st level NRSes in this tree. 
>  
> It has to be corrected like that the 3rd level NRS checks for the 2nd level and the 2nd level does for the 1st level

Yes, true. What is assumed to be the highest level of NRSs, is three levels enough?

> 
> - What is the acceptable rate for false positives?
> We are considering that FPP is less than 0.001 (i.e., 0.1%, 1000 out of 1 M entries).

Reasonable. However, this changes my original calculations, where I assumed slightly worse performance. 

> 
> - How big BFs are feasible to send and receive in the network? 
> When bloom filters at each server are initially built, it will take a long time. However, once they are established, the insertion is done by each new name not the whole bloom filter.

> On bloom filter updates for deletions, we are considering of refresh by shadow memory and the frequency can be from several hours to several days

Inserting items into a BF is not a problem, the problem comes when items should be removed and the whole BF must be recalculated as you say and the update frequency obviously depends on many things. 


> - The verification process should be fast, how can we efficiently match publications to filters with gigabit size?
> With H/W assisted implementation using GPU, chunks including the corresponding bit set to 1 for hash value can be loaded to GPU memory and a child can be selected by bit-wise AND.

Ok, thanks! Although this probably requires some processing to find these chunks before matching can be done. But, as said, I don’t know much about the optimisations that you can do on lower layers. 

BR, Petri


> 
> [1] Bellovin S., “Using Bloom Filters for Authenticated Yes/No Answers in the DNS”, draft-bellovin-dnsext-bloomfilt-00.txt, December 2001, Expired
> [2] http://pages.cs.wisc.edu/~cao/papers/summary-cache/node8.html
> [3] Hong, J., Chun, W., Jung, H., “Bloom Filter-based Flat Name Resolution System for ICN”, draft-hong-icnrg-bloomfilterbased-name-resolution-01.txt

-- 
Petri Jokela
Senior researcher
NomadicLab, Ericsson Research
Oy L M Ericsson Ab                  

E-mail: petri.jokela@ericsson.com
Mobile: +358 44 299 2413