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

From: 홍정하 <[email-masked]>
Date: Thu, 18 Sep 2014 00:31:12 +0000

Hi all,

The draft, draft-hong-icnrg-bloomfilterbased-name-resolution-01, has been submitted to the ID system.

In this draft, we have tried to reflect few questions that we got from last meeting.

Please take a look and let us know if you have any questions or comments.

I hope this draft could be discussed more in the interim meeting.

Thanks,

Jungha Hong

-----Original Message-----
Subject: New Version Notification for draft-hong-icnrg-bloomfilterbased-name-resolution-01.txt

A new version of I-D, draft-hong-icnrg-bloomfilterbased-name-resolution-01.txt

has been successfully submitted by Jungha Hong and posted to the IETF repository.

Name:        draft-hong-icnrg-bloomfilterbased-name-resolution

Revision:    01

Title:       Bloom Filter-based Flat Name Resolution System for ICN

Document date:      2014-09-17

Group:       Individual Submission

Pages:       14

URL:            http://www.ietf.org/internet-drafts/draft-hong-icnrg-bloomfilterbased-name-resolution-01.txt

Status:         https://datatracker.ietf.org/doc/draft-hong-icnrg-bloomfilterbased-name-resolution/

Htmlized:       http://tools.ietf.org/html/draft-hong-icnrg-bloomfilterbased-name-resolution-01

Diff:           http://www.ietf.org/rfcdiff?url2=draft-hong-icnrg-bloomfilterbased-name-resolution-01

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.

Please note that it may take a couple of minutes from the time of submission until the htmlized version and diff are available at tools.ietf.org.

The IETF Secretariat

The

---

From: Petri Jokela <[email-masked]>
Date: Wed, 24 Sep 2014 18:22:54 +0300

> I hope this draft could be discussed more in the interim meeting.

Hi, 

I have read the draft and I have some comments. I’m sorry, this e-mail is pretty long. If you think that I have miscalculated or made some erroneous assumptions, please correct me. So, here we go...

In this mail I try to figure out the feasibility of using Bloom filters as they are used in the original draft [3]. I would be happy to see that 1) my assumptions are too negative and / or 2) the filters do not have to be as large as I calculate here. It seems that the sizes of the filters will be huge in some environments, for example in a large corporate network.

Bloom filter matching provides an efficient way of verifying if an item belongs to a set or not, but false positive matches decrease the performance. Thus, I will concentrate on calculating the required size of the Bloom filter in the system with some assumptions of the number of nodes, number of ICN objects, and acceptable false positive rate. 

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. 

The draft [3] envisions that the BF NRS is hierarchical and has multiple levels in a tree. It is not defined, how many nodes one NRS tree will serve. We can take an estimate, e.g. from a large corporate network where we would have, say, 200 000 nodes. Assuming that a single NRS serves e.g. 2 000 nodes, we need 100 NRS nodes. If we put them in a tree, we need more NRS nodes for higher levels. If each higher level NRS would serve e.g. 10 lower level NRS nodes, we would have 10 second level NRSs and one third level NRS. NOTE: I do not consider the peering possibility in this text, only the single NRS tree for this particular use case. 

If each of the nodes in the network has 10 000 ICN objects that they publish, a single 1st level NRS would maintain location information for 20 000 000 objects. It creates a BF out of these and sends this BF to the upper level NRS. The 2nd level NRS receives BFs from ten of the 1st level NRSes and combines them using logical OR operation. This means that the resulting BF contains information of 200 000 000 objects. 2nd level NRS can use this combined BF to verify if any of the NRSes below it has that particular ICN object information, but it can also match the object to all ten received 1st level BFs which gives more accurate information. In the first case, if there is a match in the combined BF, the NRS must also try matching to all the 1st level BFs to find the actual NRS that maintains the object location information. 

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. 

Now, the problem with BFs is the amount of false positives when the number of 1s in the filter increases. We can reduce the amount of false positives by selecting carefully the length of the filter m and the number of hash functions that are used for calculating the index values, namely k.

For each of the BFs in different levels, the amount of objects we have:

n1 = 2 * 10^7
n2 = 2 * 10^8
n3 = 2 * 10^9

If we aim at (roughly) 1% false positive rate, we get some possible values for m and k (from [2]):

m/n = 10, k=4: 

level 1: m = n1 * 10 = 20 * 10^7 (~ 200 000 000 bits ~ 200 Mbits)
level 2: m = n2 * 10 = 20 * 10^8 (~ 2 000 000 000 ~ 2 Gbits)
level 3: m = n3 * 10 = … ~ 20 000 000 000 ~ 20 Gbits

Increasing k to 8, targeting to 1% false positive ratio, we get m/n = 9 (actually, it does not change much the false positive ratio if we select any value for k from 4 to 8, see the table in [2]):

level 1: m = n1 * 11 = 18 * 10^7 (~ 180 Mbits)
level 2: m ~ 1.8 Gbits
level 3: m ~ 18 Gbits

1% false positives would mean that e.g. 1 000 000 queries would generate 10 000 false queries to the lower level NRSs. 

If we accept (roughly) 5% false positives, we can use m/n = 6 and k = 4. This would result in filter sizes:

level 1: m = n1 * 6 = 12 * 10^7 (~ 120 000 000 bits ~ 120 Mbits)
..
level 3: m = n3 * 6 = 12 * 10^9 (~ 12 000 000 000 bits ~ 12 Gbits)

In [1], BFs were suggested to be used in DNSSEC authentication. Not going into details of authentication, the author was suggesting to use 

k = 16, m = 40
k = 16, m = 32
k = 8, m = 40
k = 8, m = 32

to get low enough false positive probability. They were aiming at false positive ratios max 0.005%. In the NRS and flat name case, this low false positive ratio is not necessarily required, but I took this draft as an example because they were using 800 Mbit filters with k = 8 or 16. And, hopefully, they had kept in mind the performance for the verification process. I must admit that I don’t know how the verification can be implemented efficiently with such large filters.

We have to note that with Bloom filters, the size of the filter is always the same at all the levels. I.e. we have to take big enough filter so that it works also on higher levels in hierarchy. So, just quickly looking at this, it seems that we are dealing with huge Bloom filters, that are gigabits in size. 

Another issue is the transmission of the Bloom filters between NRSes. To keep the information as accurate as possible on different levels, we have to send updated Bloom filters pretty often to the upper level NRSes. How often this is done, depends naturally on the activity level of the nodes in the network, i.e. how often they publish new information items to the NRS or remove them.

So, we have some questions, e.g. 

- What is the acceptable rate for false positives?
- How big BFs are feasible to send and receive in the network? 
- The verification process should be fast, how can we efficiently match publications to filters with gigabit size?

[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

BR, Petri

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

E-mail: [email-masked]
Mobile: +358 44 299 2413

---

From: 정희영 <[email-masked]>
Date: Thu, 25 Sep 2014 05:24:37 +0000

Hello Petri,

Thank you for your valuable questions.
To my understanding, your questions are closely related to some design decisions and/or implementation issues.
So I’m afraid it may not easy to discuss on-line. (you had to write very long mail for the question :-))
Fortunately, Dr. Hong’s presentation is planned in this interim meeting.
I think we can have chance to discuss about your questions in the presentation.

Brs,
heeyoung

From: icnrg [mailto:[email-masked]] On Behalf Of Petri Jokela
Sent: Thursday, September 25, 2014 12:23 AM
To: 홍정하; [email-masked]
Subject: Re: [icnrg] New Version Notification for draft-hong-icnrg-bloomfilterbased-name-resolution-01.txt

On 18 Sep 2014, at 03:31, 홍정하 <[email-masked]<mailto:[email-masked]>> wrote:

Hi all,

Thanks,
Jungha Hong

Hi,

n1 = 2 * 10^7
n2 = 2 * 10^8
n3 = 2 * 10^9

m/n = 10, k=4:

k = 16, m = 40
k = 16, m = 32
k = 8, m = 40
k = 8, m = 32

BR, Petri

E-mail: [email-masked]<mailto:[email-masked]>
Mobile: +358 44 299 2413

---

From: 홍정하 <[email-masked]>
Date: Fri, 26 Sep 2014 21:15:56 +0000

Hi,

Here are my response.

We chose to utilize bloom filters for efficient lookup of flat names, where bloom filter size and false positive probability (FPP) are big challenges that have to be addressed.

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.

I put my response in the middle of your comments.
Please find them below.

Again, we are thankful for your comments.
We hope that it could be discussed more at the tomorrow meeting.

Jungha Hong

________________________________
보낸 사람 : "Petri Jokela" <[email-masked]>
보낸 날짜 : 2014-09-25 00:23:00 ( +09:00 )
받는 사람 : 홍정하 <[email-masked]>, [email-masked] <[email-masked]>
참조 :
제목 : Re: [icnrg] New Version Notification for draft-hong-icnrg-bloomfilterbased-name-resolution-01.txt

Hi all,

Thanks,
Jungha Hong

Hi,

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.

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.

n1 = 2 * 10^7
n2 = 2 * 10^8
n3 = 2 * 10^9

m/n = 10, k=4:

k = 16, m = 40
k = 16, m = 32
k = 8, m = 40
k = 8, m = 32

- 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).

- 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.

- 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.

BR, Petri

---

From: Petri Jokela <[email-masked]>
Date: Sat, 27 Sep 2014 10:17:48 +0300

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: 

> 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…

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). 
 
> 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 wh…

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.  

> 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?

> 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. 

> 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. 

> 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

---

From: "Konstantinos V. Katsaros" <[email-masked]>
Date: Sat, 27 Sep 2014 13:21:18 +0100

Hi,

If I may add 2c in this interesting discussion, though I do share the
concerns expressed on the size of the Bloom Filters (BFs), I think the
following basic assumption(s) does not necessarily hold:

"We have to note that with Bloom filters, the size of the filter is always
the same at all the levels. I.e. we have to take big enough filter so that
it works also on higher levels in hierarchy."

"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). "

I think the requirement here is rather to have a globally fixed BF size for
merging to be possible. Then we could have additional BFs created when the
capacity is exceeded: each node "fills" BFs until the FPR is reached; when
merging, an object counter per BF can assist in finding the appropriate BFs
to merge i.e., the ones that will not exceed the FPR. This calls for a bin
packing algorithm with its own processing overheads. In this context, we
could illustrate a tradeoff by considering the two following extremes:

(i) BFs of size enough to hold every object in the network. That would
surely work for the topmost nodes. However, lower level nodes would
propagate mostly very sparse BFs upwards, meaning that
we unnecessarily spend too much space/bandwidth. Though admittedly a lookup
operation on such large BFs could be an issue, note that in principle one
BF should be checked per interface/neighbour node.

(ii) BFs of a very small size that would easily get "full" necessitating
the use of an additional BF. In this case we would have "dense" BFs that
would not waste too much space/bandwidth, but would require multiple lookup
operations per interface/neighbour. I do not know however, whether multiple
lookups of smaller BFs are (computationally) preferable compared to a
single lookup of a huge BF, or if it makes no substantial difference.

Regards,
Konstantinos (Dinos) V. Katsaros

PS: Unfortunately I also do not participate the interim meeting. But,
waiting for the minutes.

On 27 September 2014 08:17, Petri Jokela <[email-masked]> wrote:

> 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:
>
>    *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*
>
>
> *We are considering that FPP is less than 0.001 (i.e., 0.1%, 1000 out of 1
> M entries).*
>
>
>  *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
> [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
> _______________________________________________
> icnrg mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/icnrg
>
>

---

From: Konstantinos Katsaros <[email-masked]>
Date: Sat, 27 Sep 2014 14:12:22 +0100

Hi,

Regards,

---

From: Petri Jokela <[email-masked]>
Date: Mon, 29 Sep 2014 08:42:04 +0300

Hi,

Good comments, thanks. See few small comments inline: 
 
On 27 Sep 2014, at 16:12, Konstantinos Katsaros <[email-masked]> wrote:

> I think the requirement here is rather to have a globally fixed BF size for merging to be possible. Then we could have additional BFs created when the capacity is exceeded: each node "fills" BFs until the FPR is reached; when merging, an object counter per BF can assist in finding the appropriate BFs to merge i.e., the ones that will not exceed the FPR.

This is true, I was probably initially thinking a very simple solution with only one BF. Multi-BF solution brings, of course, more possibilities to design the NRS mechanism. 

> This calls for a bin packing algorithm with its own processing overheads. In this context, we could illustrate a tradeoff by considering the two following extremes:
> 
> (i) BFs of size enough to hold every object in the network. That would surely work for the topmost nodes. However, lower level nodes would propagate mostly very sparse BFs upwards, meaning that we unnecessarily spend too much space/bandwidth. Though admittedly a lookup operation on such large BFs could be an issue, note that in principle one BF should be checked per interface/neighbour node.  

In case of a bit string, we probably can compress sparse BFs efficiently for transmission and the final size can be quite small.

> (ii) BFs of a very small size that would easily get "full" necessitating the use of an additional BF. In this case we would have "dense" BFs that would not waste too much space/bandwidth, but would require multiple lookup operations per interface/neighbour. I do not know however, whether multiple lookups of smaller BFs are (computationally) preferable compared to a single lookup of a huge BF, or if it makes no substantial difference.

Neither do I know which one is more efficient. From a large BF, you need to verify max k chunks each of being x-bits in size (what is the most efficient x?). This reduces the amount of logical operations. However, how much processing is needed for getting those chunks from a large filter, I have no idea. I feel that I’m on a very thin ice when discussing the implementation efficiency of big filters :-) 

Nevertheless, this is pretty interesting topic and I am interested to see how the B-NRS solution develops.

BR, Petri

> PS: Unfortunately I also do not participate the interim meeting. But, waiting for the minutes. 
>

---

From: 홍정하 <[email-masked]>
Date: Tue, 30 Sep 2014 09:17:46 +0000

Hi,

I put my notes below with my initial JH.
Please find them.

Thanks,
Jungha Hong

From: Petri Jokela [mailto:[email-masked]]
Sent: Saturday, September 27, 2014 4:18 PM
To: 홍정하
Cc: [email-masked]
Subject: Re: [icnrg] New Version Notification for draft-hong-icnrg-bloomfilterbased-name-resolution-01.txt

On 27 Sep 2014, at 00:15, 홍정하 <[email-masked]<mailto:[email-masked]>> wrote:

Hi,

JH: Yes, you are right. To combine BFs, same size filters and same hash functions are required. However, we are considering that the lower level filter would not need such a big filter as top level. So, we are working on if the BF size can be reduced.

JH: Yes, right. So, for better efficiency with different BF size, we may reuse the same hash functions and add additional ones for higher level, which is just an example that we are considering. There are few other ways that we are considering but it is not a status yet that we can discuss them now.

JH: This is why we assume that the number of names in ICN would grow up to 10^15. If you ask me what happen if it gets more than 10^15, then the scalability issue never gets solved. So, I think 10^15 would be enough for now. Once we solve it, then we can extend it for more.

Yes, true. What is assumed to be the highest level of NRSs, is three levels enough?
JH: We thinks that 4 to 5 levels would be enough which we are working on to prove it.

JH: BF refresh is also ongoing work. Once we finalize how to refresh, we hope to discuss it here, ICNRG.

BR, Petri

---

From: 홍정하 <[email-masked]>
Date: Tue, 30 Sep 2014 16:52:16 +0000

Hi,

Thanks a lot for your interesting and good comments on B-NRS.
I totally agree with both of you.

No matter what we choose between a large BF size and multiple smaller size BFs, we believe that we can get helped to prove any our ideas by H/W assisted implementation  and so we are working on it now.

I would like to share any progress that I make further than now and get comments on it.
So, please keep paying attention to discussions by e-mail.
Any comments are more than welcome any time.

Thanks,
Jungha Hong

________________________________
보낸 사람 : "Petri Jokela" <[email-masked]>
보낸 날짜 : 2014-09-29 14:42:20 ( +09:00 )
받는 사람 : Konstantinos Katsaros <[email-masked]>
참조 : [email-masked] <[email-masked]>
제목 : Re: [icnrg] New Version Notification for draft-hong-icnrg-bloomfilterbased-name-resolution-01.txt

Hi,

On 27 Sep 2014, at 16:12, Konstantinos Katsaros <[email-masked]<mailto:[email-masked]>> wrote:

BR, Petri

Regards,

On 27 September 2014 08:17, Petri Jokela <[email-masked]<mailto:[email-masked]>> wrote:
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:

Hi,

BR, Petri

E-mail: [email-masked]<mailto:[email-masked]>
Mobile: +358 44 299 2413<tel:%2B358%2044%20299%202413>

_______________________________________________
icnrg mailing list
[email-masked]<mailto:[email-masked]>
https://www.irtf.org/mailman/listinfo/icnrg

_______________________________________________
icnrg mailing list
[email-masked]<mailto:[email-masked]>
https://www.irtf.org/mailman/listinfo/icnrg

---

From: Christian Esteve Rothenberg <[email-masked]>
Date: Tue, 30 Sep 2014 17:02:45 -0300

Nice discussion!

Petri, good to hear from you :) and your love–hate relationship with
Bloom filters ;)

Just trying to a few cents to the conversation:
Traditional bloom filters as an array of bits is a convenient
representation (out of many possible along multiple variations [1])
for the data structure but probably not the best one for many
implementations (e.g., m >>> 1) and certainly not optimized for
different SW/HW implementations. For instance, fingerprint compressed
filter (FCF) as we played with some time ago in the early discussions
on ICN forwarding alternatives [2], yield a BF-like data structure
with very interesting properties on a per entry basis (e.g. deletion?)
and amenable to optimized HW/SW implementations (including a
hierarchical cache-like multi-memory design)

[1] S. Tarkoma, C. Esteve Rothenberg and E. Lagerspetz. "Theory and
Practice of Bloom Filters for Distributed Systems." In IEEE
Communications Surveys and Tutorials. Vol. 14, Number 1, 2012
http://dl.dropboxusercontent.com/u/15183439/pubs/bloom-filter-ieee-survey-preprint.pdf

[2]  C. Esteve Rothenberg, F. Verdi and M. Magalhães. "Towards a new
generation of information-oriented internetworking architectures" ACM
CoNext, First Workshop on Re-Architecting the Internet (Re-Arch08).
Dec. 2008, Madrid, Spain.
https://dl.dropboxusercontent.com/u/15183439/pubs/ccngi-rearch08-spswitch-esteve-camera-ready.pdf
Christian

On Tue, Sep 30, 2014 at 1:52 PM, 홍정하 <[email-masked]> wrote:
> No matter what we choose between a large BF size and multiple smaller size
> BFs, we believe that we can get helped to prove any our ideas by H/W
> assisted implementation  and so we are working on it now.
>
> 제목 : Re: [icnrg] New Version Notification for
> draft-hong-icnrg-bloomfilterbased-name-resolution-01.txt
>
> Hi,
>
> to merge i.e., the ones that will not exceed the FPR.
>
>
> This is true, I was probably initially thinking a very simple solution with
> only one BF. Multi-BF solution brings, of course, more possibilities to
> design the NRS mechanism.
>
> This calls for a bin packing algorithm with its own processing overheads. In
> this context, we could illustrate a tradeoff by considering the two
> following extremes:
>
> propagate mostly very sparse BFs upwards, meaning that we unnecessarily
> spend too much space/bandwidth. Though admittedly a lookup operation on such
> large BFs could be an issue, note that in principle one BF should be checked
> per interface/neighbour node.
>
>
> In case of a bit string, we probably can compress sparse BFs efficiently for
> transmission and the final size can be quite small.
>
> (ii) BFs of a very small size that would easily get "full" necessitating the
> use of an additional BF. In this case we would have "dense" BFs that would
> not waste too much space/bandwidth, but would require multiple lookup
> lookups of smaller BFs are (computationally) preferable compared to a single
> lookup of a huge BF, or if it makes no substantial difference.
>
>
> Neither do I know which one is more efficient. From a large BF, you need to
> verify max k chunks each of being x-bits in size (what is the most efficient
> x?). This reduces the amount of logical operations. However, how much
> processing is needed for getting those chunks from a large filter, I have no
> idea. I feel that I’m on a very thin ice when discussing the implementation
> efficiency of big filters :-)
>
>> We can take advantage of that bloom filter size can be adjusted by the
>> less than a desirable value.
>>
>>
>> For example, the bloom filter with the size of 2MB for 10^6 entries can
>> working on it.
>> 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
>>
>> 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.
>>
>> 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.
>>
>>
>> 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
>> 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.
>>
>>
>>
>> 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
>>
>>
>> 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
>>
>>
>> With H/W assisted implementation using GPU, chunks including the
>> child can be selected by bit-wise AND.
>>
>>