Subject: [icnrg] On false negative errors of BFs?

From: 홍정하 <[email-masked]>
Date: Tue, 11 Nov 2014 03:16:15 +0000

Hi,

I am attanding at ICNRG in Honolulu now and just finished my presentation on Bloom filter-based NRS for ICN.
I was asked if I have considered the false negative errors of BFs.
My answer was there is no false negative of BF.
But the questionor (sorry for not knowing your name) said that there is the false negative of BF.

So, I have checked that there exists the false negative problem of counting bloom filter.
Although I mentioned the counting BF on my presentation as an alternative for BF deletion issue,
I said that we do not adopt the counting BF in our B-NRS.
Thus, we do not have that kind of issue.

Please let me know if I am missing anything else on this issue.

Thanks,
Jungha Hong

---

From: Ibrahim ABDULLAHI <[email-masked]>
Date: Tue, 11 Nov 2014 19:42:43 +0800

Hi Hong J,

Sure there is false positive in Bloom Filters as part of its distinct
Characteristics.
We here are also working on the incorporation of BF to our ICN-Caching
proposed scenarios for NR.
The good advantages in using BFs include fast-look ups due to its fast
searching characteristics,  but when certain conditions didnt get checked,
a false negative could be delivered since we will be dealing with a highly
populated network.
Well look at the case of a network that has good scalability and mobility
rates; the false negative could as well occur.

On Tue, Nov 11, 2014 at 11:16 AM, 홍정하 <[email-masked]> wrote:

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

-- 

*Regards.*

******************************************************************

*Ibrahim ABDULLAHI*

*B.Sc (UDU), M.Sc (ABU)*
*PhD Research Student, *

*InterNetworks Research Laboratory,*

*School of Computing; College of Arts and Sciences,*

*Universiti Utara Malaysia, UUM 06010 Sintok, Kedah, Darul Aman.*

*M A L A Y S I A (+60169290804)*

*http://uum.edu.my/index.php/en/ <http://uum.edu.my/index.php/en/> *

* NIGERIA: (+2348035991532) *

*Department of Mathematics/Computer Science.*

*Faculty of Natural Science, P.M.B 11*

*Ibrahim Badamasi Babangida University, Lapai.*

*Niger State. N I G E R I A*

*http://ibbu.edu.ng/ <http://ibbu.edu.ng/>*

******************************************************************

******************************************************************

---

From: Gwendal SIMON <[email-masked]>
Date: Tue, 11 Nov 2014 15:53:43 +0100

Indeed, dealing with false negative of Bloom filters can be difficult. We
had to build a quite complicated system to get a consistent PIT based on
Bloom Filters in our previous works. The articles are available here:

Wei You, Bertrand Mathieu, Patrick Truong, Jean-François Peltier and
Gwendal Simon. "DiPIT: a Distributed Bloom-Filter based PIT Table for CCN
Nodes", in IEEE Int. Conf. on Computers, Communications and Networks
(ICCCN), 2012.
http://perso.telecom-bretagne.eu/gwendalsimon/data/iccc2012.pdf

Wei You, Bertrand Mathieu, Patrick Truong, Jean-François Peltier and
Gwendal Simon. « Realistic Storage of Pending Requests in Content-Centric
Network Routers », in IEEE Int. Conf. on Communications in China (ICCC),
2012.
http://perso.telecom-bretagne.eu/gwendalsimon/data/iccc2012.pdf

Hope it can help for those who want to build Bloom Filter-based CCN systems
:-)

Sincerely,
--
Gwendal SIMON
Associate-Professor
Telecom Bretagne (Institut Mines Telecom)
IRISA ReOP team
Phone: (+33) 6 52 72 62 65
Twitter: @gwendal
Skype: gwendal.simon
http://perso.telecom-bretagne.eu/gwendalsimon/

On Tue, Nov 11, 2014 at 12:42 PM, Ibrahim ABDULLAHI <[email-masked]>
wrote:

> *M A L A Y S I A (+60169290804 <%28%2B60169290804>)*
>
> * NIGERIA: (+2348035991532 <%28%2B2348035991532>) *
>

---

From: 홍정하 <[email-masked]>
Date: Tue, 11 Nov 2014 18:15:02 +0000

I think there is no false negative as long as any bits are not deleted from BF.
So, in our B-NRS, false negative cannot occur since we use the pure BF concept.
However, the loop-free network was basically assumed, which is also related to the false positive not false negative.

I agree that dealing the false negative is not easy if it occurs in a certain scenario.
Thanks for your comments and references.

Jungha Hong

________________________________
보낸 사람 : "Gwendal SIMON" <[email-masked]>
보낸 날짜 : 2014-11-11 23:54:05 ( +09:00 )
받는 사람 : Ibrahim ABDULLAHI <[email-masked]>
참조 : 홍정하 <[email-masked]>, [email-masked] <[email-masked]>, [email-masked] <[email-masked]>
제목 : Re: [icnrg] On false negative errors of BFs?

Indeed, dealing with false negative of Bloom filters can be difficult. We had to build a quite complicated system to get a consistent PIT based on Bloom Filters in our previous works. The articles are available here:

Wei You, Bertrand Mathieu, Patrick Truong, Jean-François Peltier and Gwendal Simon. "DiPIT: a Distributed Bloom-Filter based PIT Table for CCN Nodes", in IEEE Int. Conf. on Computers, Communications and Networks (ICCCN), 2012.
http://perso.telecom-bretagne.eu/gwendalsimon/data/iccc2012.pdf

Wei You, Bertrand Mathieu, Patrick Truong, Jean-François Peltier and Gwendal Simon. « Realistic Storage of Pending Requests in Content-Centric Network Routers », in IEEE Int. Conf. on Communications in China (ICCC), 2012.
http://perso.telecom-bretagne.eu/gwendalsimon/data/iccc2012.pdf

Hope it can help for those who want to build Bloom Filter-based CCN systems :-)

Sincerely,

On Tue, Nov 11, 2014 at 12:42 PM, Ibrahim ABDULLAHI <[email-masked]<mailto:[email-masked]>> wrote:
Hi Hong J,

Sure there is false positive in Bloom Filters as part of its distinct Characteristics.
We here are also working on the incorporation of BF to our ICN-Caching proposed scenarios for NR.
The good advantages in using BFs include fast-look ups due to its fast searching characteristics,  but when certain conditions didnt get checked, a false negative could be delivered since we will be dealing with a highly populated network.
Well look at the case of a network that has good scalability and mobility rates; the false negative could as well occur.

On Tue, Nov 11, 2014 at 11:16 AM, 홍정하 <[email-masked]<mailto:[email-masked]>> wrote:
Hi,

Thanks,
Jungha Hong

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

--

Regards.

****************************************************************

Ibrahim ABDULLAHI

B.Sc (UDU), M.Sc (ABU)
PhD Research Student,

InterNetworks Research Laboratory,

School of Computing; College of Arts and Sciences,

Universiti Utara Malaysia, UUM 06010 Sintok, Kedah, Darul Aman.

M A L A Y S I A (+60169290804<tel:%28%2B60169290804>)

http://uum.edu.my/index.php/en/

 NIGERIA: (+2348035991532<tel:%28%2B2348035991532>)

Department of Mathematics/Computer Science.

Faculty of Natural Science, P.M.B 11

Ibrahim Badamasi Babangida University, Lapai.

Niger State. N I G E R I A

http://ibbu.edu.ng/

****************************************************************

****************************************************************

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