More Web Proxy on the site http://driver.im/

research-article

Bloom Filter Based Inter-Domain Name Resolution: A Feasibility Study

Authors:

Konstantinos V. Katsaros,

Wei Koong Chai,

George PavlouAuthors Info & Claims

ACM-ICN '15: Proceedings of the 2nd ACM Conference on Information-Centric Networking

Pages 39 - 48

https://doi.org/10.1145/2810156.2810175

Published: 30 September 2015 Publication History

Abstract

The enormous size of the information space raises significant concerns regarding the scalability of name resolution in Information-Centric Networks, especially at a global scale. Recently, the use of Bloom filters has been proposed as a means to achieve a more compact representation of name resolution state. However, little attention has been paid to the expected performance or even the feasibility of such an approach. In this paper, we aim to fill this gap, presenting a feasibility study and performance analysis of Bloom filter based route-by-name inter-domain name resolution schemes. We propose a methodology for assessing the memory and processing resource requirements of the considered schemes and apply it on top of the inter-domain topology. Our investigation reveals that the skewed distribution of state across the inter-network results in a hard to balance trade-off between memory and processing resource requirements. We show that hardly any Bloom filter configuration i.e., size and bits-per-element, is able to reduce both types of resource requirements for all Autonomous Systems (ASes) in the network, while lowering resource requirements at one area of the inter-domain topology inflates resource requirements at another. Detailed simulations further show that the direct connection of multiple stub networks to tier-1 ASes, results in a dramatic increase of false positives, questioning the reliability of a BF-based inter-domain name resolution scheme.

References

[1]

Caida dataset. http://www.caida.org/research/topology/#Datasets, 2008. {Online; accessed 19-July-2008}.

[2]

P. S. Almeida et al. Scalable bloom filters. Information Processing Letters, 101(6):255 -- 261, 2007.

Digital Library

[3]

B. H. Bloom. Space/Time Trade-offs in Hash Coding with Allowable Errors. Commun. ACM, 13(7):422--426, July 1970.

Digital Library

[4]

F. Bonomi et al. An improved construction for counting bloom filters. In Y. Azar and T. Erlebach, editors, Algorithms -- ESA 2006, volume 4168 of Lecture Notes in Computer Science, pages 684--695. Springer Berlin Heidelberg, 2006.

Digital Library

[5]

W. K. Chai et al. Curling: Content-ubiquitous resolution and delivery infrastructure for next-generation services. IEEE Communications Magazine, 49(3):112 --120, 2011.

Digital Library

[6]

C. Dannewitz et al. Hierarchical DHT-based name resolution for information-centric networks. Computer Communications, 36(7):736--749, Apr. 2013.

Digital Library

[7]

X. Dimitropoulos et al. Graph annotations in modeling complex network topologies. ACM Transactions on Modeling and Computer Simulation, 19:17:1--17:29, November 2009.

Digital Library

[8]

D. Evans. The Internet of Everything: How More Relevant and Valuable Connections Will Change the World. White Paper, February 2012.

[9]

B. Fan et al. Cuckoo filter: Practically better than bloom. In Proceedings of the 10th ACM International on Conference on Emerging Networking Experiments and Technologies, CoNEXT '14, pages 75--88, New York, NY, USA, 2014. ACM.

Digital Library

[10]

L. Fan et al. Summary Cache: a scalable wide-area web cache sharing protocol. IEEE/ACM Transactions on Networking, 8(3):281--293, 2000.

Digital Library

[11]

N. Fotiou et al. H-Pastry: An inter-domain topology aware overlay for the support of name-resolution services in the future Internet. Computer Communications, 62:13 -- 22, 2015.

Digital Library

[12]

Google. We knew the web was big, July 2008.

[13]

D. Guo et al. The dynamic bloom filters. Knowledge and Data Engineering, IEEE Transactions on, 22(1):120--133, Jan 2010.

Digital Library

[14]

J. Hong et al. Bloom Filter-based Flat Name Resolution System for ICN. Internet-Draft draft-hong-icnrg-bloomfilterbased-name-resolution-03.txt, IETF Secretariat, Mar. 2015.

[15]

R. Jarno et al. On name-based inter-domain routing. Computer Networks, Elsevier, 55:975--986, March 2011.

Digital Library

[16]

K. Katsaros et al. GlobeTraff: A Traffic Workload Generator for the Performance Evaluation of Future Internet Architectures. In New Technologies, Mobility and Security (NTMS), 2012 5th International Conference on, pages 1--5, May 2012.

[17]

K. V. Katsaros et al. On inter-domain name resolution for information-centric networks. In Proc. of the IFIP TC 6 Conference on Networking, pages 13--26, 2012.

Digital Library

[18]

K. V. Katsaros et al. On the Inter-domain Scalability of Route-by-Name Information-Centric Network Architectures. In Proc. of the IFIP TC 6 Conference on Networking, pages --, 2015.

[19]

T. Koponen et al. A data-oriented (and beyond) network architecture. In Proc. of the ACM SIGCOMM, pages 181--192, 2007.

Digital Library

[20]

C. Labovitz et al. Internet inter-domain traffic. In Proc. of the 2010 ACM SIGCOMM, pages 75--86, New York, NY, USA, 2010. ACM.

Digital Library

[21]

H. Liu et al. A multi-level DHT routing framework with aggregation. In Proc. of the 2012 ACM SIGCOMM Workshop on Information-centric networking (ICN'12), pages 43--48. ACM, 2012.

Digital Library

[22]

M. Mitzenmacher. Compressed Bloom Filters. IEEE/ACM Trans. Netw., 10(5):604--612, Oct. 2002.

Digital Library

[23]

R. Oliveira et al. The (in)completeness of the observed internet AS-level structure. IEEE/ACM Transactions on Networking, 18:109--122, February 2010.

Digital Library

[24]

S. Tarkoma et al. Theory and practice of bloom filters for distributed systems. Communications Surveys Tutorials, IEEE, 14(1):131--155, First 2012.

[25]

G. Xylomenos et al. A Survey of Information-Centric Networking Research. IEEE Communications Surveys and Tutorials, 16(2):1024--1049, 2014.

Cited By

Lian WLi YWang JYou J(2022)A Cuckoo Filter-Based Name Resolution and Routing Method in Information-Centric NetworkingElectronics10.3390/electronics1119324311:19(3243)Online publication date: 9-Oct-2022
https://doi.org/10.3390/electronics11193243
Kohama KKamiyama N(2022)Scalable Naming in ICN2022 IEEE 8th World Forum on Internet of Things (WF-IoT)10.1109/WF-IoT54382.2022.10152095(1-6)Online publication date: 26-Oct-2022
https://doi.org/10.1109/WF-IoT54382.2022.10152095
Zhang CWang Y(2019)Towards Efficient Content Discovery in NDN with Enhanced Component-Based Bloom Filters2019 IEEE 21st International Conference on High Performance Computing and Communications; IEEE 17th International Conference on Smart City; IEEE 5th International Conference on Data Science and Systems (HPCC/SmartCity/DSS)10.1109/HPCC/SmartCity/DSS.2019.00326(2345-2350)Online publication date: Aug-2019
https://doi.org/10.1109/HPCC/SmartCity/DSS.2019.00326
Show More Cited By

Index Terms

Bloom Filter Based Inter-Domain Name Resolution: A Feasibility Study
1. Computer systems organization
  1. Architectures
    1. Distributed architectures
2. Networks
  1. Network architectures

Recommendations

Analysis and improvement of name-based packet forwarding over flat ID network architectures
ICN '18: Proceedings of the 5th ACM Conference on Information-Centric Networking

One of ICN's main challenges is attaining forwarding table scalability when confronted with a huge content space. This is specially true in flat ID architectures, which do not naturally support route aggregation for hierarchical names. Previous work has ...
Scalable name-based inter-domain routing for information-centric networks
IPCCC '15: Proceedings of the 2015 IEEE 34th International Performance Computing and Communications Conference (IPCCC)

Given the large volume of content on the Internet, scalability is one of the critical challenges in the design and development of information-centric network (ICN) architectures. In this paper we develop a scalable name-based inter-domain routing (NIDR) ...
On name-based inter-domain routing

Locating objects with topology-independent identifiers has emerged as a key functionality in recent content networking approaches. Numerous designs have been proposed to address the obvious scalability and efficiency challenges such systems face in ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ACM-ICN '15: Proceedings of the 2nd ACM Conference on Information-Centric Networking

September 2015

236 pages

ISBN:9781450338554

DOI:10.1145/2810156

General Chair:
Ignacio Solis
PARC, USA
,
Program Chairs:
Antonio Carzaniga
USI, Switzerland
,
K. K. Ramakrishnan
UC Riverside, USA

Copyright © 2015 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGCOMM: ACM Special Interest Group on Data Communication

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 30 September 2015

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

CHIST-ERA / EPSRC UK
Seventh Framework Programme

Conference

ICN'15

Sponsor:

SIGCOMM

ICN'15: 2nd International Conference on Information-Centric Networking

September 30 - October 2, 2015

California, San Francisco, USA

Acceptance Rates

ACM-ICN '15 Paper Acceptance Rate 18 of 55 submissions, 33%;

Overall Acceptance Rate 133 of 482 submissions, 28%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
118
Total Downloads

Downloads (Last 12 months)5
Downloads (Last 6 weeks)0

Reflects downloads up to 27 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Lian WLi YWang JYou J(2022)A Cuckoo Filter-Based Name Resolution and Routing Method in Information-Centric NetworkingElectronics10.3390/electronics1119324311:19(3243)Online publication date: 9-Oct-2022
https://doi.org/10.3390/electronics11193243
Kohama KKamiyama N(2022)Scalable Naming in ICN2022 IEEE 8th World Forum on Internet of Things (WF-IoT)10.1109/WF-IoT54382.2022.10152095(1-6)Online publication date: 26-Oct-2022
https://doi.org/10.1109/WF-IoT54382.2022.10152095
Zhang CWang Y(2019)Towards Efficient Content Discovery in NDN with Enhanced Component-Based Bloom Filters2019 IEEE 21st International Conference on High Performance Computing and Communications; IEEE 17th International Conference on Smart City; IEEE 5th International Conference on Data Science and Systems (HPCC/SmartCity/DSS)10.1109/HPCC/SmartCity/DSS.2019.00326(2345-2350)Online publication date: Aug-2019
https://doi.org/10.1109/HPCC/SmartCity/DSS.2019.00326
Rodrigues ASteenkiste PAguiar AYeh EOran D(2018)Analysis and improvement of name-based packet forwarding over flat ID network architecturesProceedings of the 5th ACM Conference on Information-Centric Networking10.1145/3267955.3267960(148-158)Online publication date: 21-Sep-2018
https://dl.acm.org/doi/10.1145/3267955.3267960
Karrakchou OSamaan NKarmouch A(2018)FCTree: A Space Efficient FIB Data Structure for NDN Routers2018 IEEE 43rd Conference on Local Computer Networks (LCN)10.1109/LCN.2018.8638116(589-596)Online publication date: Oct-2018
https://doi.org/10.1109/LCN.2018.8638116
Chai WPavlou GKamel GKatsaros KWang N(2018)A Distributed Interdomain Control System for Information-Centric Content DeliveryIEEE Systems Journal10.1109/JSYST.2018.2856918(1-12)Online publication date: 2018
https://doi.org/10.1109/JSYST.2018.2856918
Karrakchou OSamaan NKarmouch A(2018)A Survey of Routing Mechanisms in ICNs2018 6th International Conference on Multimedia Computing and Systems (ICMCS)10.1109/ICMCS.2018.8525877(1-6)Online publication date: May-2018
https://doi.org/10.1109/ICMCS.2018.8525877
KAWAHARA RSAITO H(2017)Name Resolution Based on Set of Attribute-Value Pairs of Real-World InformationIEICE Transactions on Communications10.1587/transcom.2016EBP3005E100.B:1(110-121)Online publication date: 2017
https://doi.org/10.1587/transcom.2016EBP3005
Feng ZXu MYang Y(2016)Revolutionizing the inter-domain business model by information-centric thinking2016 IEEE International Conference on Communications (ICC)10.1109/ICC.2016.7510923(1-6)Online publication date: May-2016
https://doi.org/10.1109/ICC.2016.7510923

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten