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

[홍정하 <[e-mail]>]

Hi,

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

Thanks,
Jungha Hong

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

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, 홍정하 <[e-mail]<mailto:[e-mail]>> 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

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.

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.

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.

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.

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.


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?
JH: We thinks that 4 to 5 levels would be enough which we are working on to prove it.


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

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

- 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: [e-mail]<mailto:[e-mail]>
Mobile: [phone]