{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,1]],"date-time":"2025-10-01T15:32:50Z","timestamp":1759332770749,"version":"3.41.0"},"reference-count":38,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2020,10,1]],"date-time":"2020-10-01T00:00:00Z","timestamp":1601510400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Internet Technol."],"published-print":{"date-parts":[[2020,11,30]]},"abstract":"<jats:p>The increasing volume of network-connected devices comprising Internet of Things and the variety of heterogeneous network architectures across these devices pose significant challenges to effective deployment and routing. In this article, we consider the adoption of probabilistic data structures to develop a novel Bloom Filter-based dual-layer inter-domain routing scheme. Our designed scheme implements internal and external routing layers in network gateways constructed upon the counting bloom filter and the original bloom filter. We first compare several representative structures in both theory and experimentation. We then propose our novel Bloom Filter-based dual-layer inter-domain routing scheme. In the design of the routing scheme, we consider issues related to the overall space cost and routing loop prevention, as well as present corresponding solutions. We also detail the principal structures and algorithms. Further, we conduct a theoretical analysis of the space efficiency of our proposed scheme compared to traditional routing with respect to the size of data packets and the size of routing tables, as well as in routing loop avoidance. Finally, via extensive performance evaluation, our experimental results demonstrate the effectiveness and efficiency of our proposed scheme.<\/jats:p>","DOI":"10.1145\/3407192","type":"journal-article","created":{"date-parts":[[2020,10,2]],"date-time":"2020-10-02T04:12:30Z","timestamp":1601611950000},"page":"1-24","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Routing in Large-scale Dynamic Networks"],"prefix":"10.1145","volume":"20","author":[{"given":"Weichao","family":"Gao","sequence":"first","affiliation":[{"name":"Dept. of Computer and Information Sciences, Towson University, Towson, MD, USA"}]},{"given":"James","family":"Nguyen","sequence":"additional","affiliation":[{"name":"U.S. Army Command, Control, Computers, Communications, Cyber, Intelligence, Surveillance and Reconnaissance Center, Aberdeen, MD, USA"}]},{"given":"Yalong","family":"Wu","sequence":"additional","affiliation":[{"name":"Dept. of Computer and Information Sciences, Towson University, Towson, MD, USA"}]},{"given":"William G.","family":"Hatcher","sequence":"additional","affiliation":[{"name":"Dept. of Computer and Information Sciences, Towson University, Towson, MD, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4522-7340","authenticated-orcid":false,"given":"Wei","family":"Yu","sequence":"additional","affiliation":[{"name":"Dept. of Computer and Information Sciences, Towson University, Towson, MD, USA"}]}],"member":"320","published-online":{"date-parts":[[2020,10]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2013.2281614"},{"key":"e_1_2_1_2_1","unstructured":"Apache Hadoop 2.7.3. [n.d.]. Retrieved from http:\/\/hadoop.apache.org\/docs\/current\/api\/org\/apache\/hadoop\/util\/bloom\/package-summary.html.  Apache Hadoop 2.7.3. [n.d.]. Retrieved from http:\/\/hadoop.apache.org\/docs\/current\/api\/org\/apache\/hadoop\/util\/bloom\/package-summary.html."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/362686.362692"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/WF-IoT.2014.6803204"},{"volume-title":"Proceedings of the 10th ACM International on Conference on Emerging Networking Experiments and Technologies.","author":"Fan Bin","key":"e_1_2_1_5_1","unstructured":"Bin Fan , Dave G. Andersen , Michael Kaminsky , and Michael D. Mitzenmacher . 2014. Cuckoo filter: Practically better than bloom . In Proceedings of the 10th ACM International on Conference on Emerging Networking Experiments and Technologies. Bin Fan, Dave G. Andersen, Michael Kaminsky, and Michael D. Mitzenmacher. 2014. Cuckoo filter: Practically better than bloom. In Proceedings of the 10th ACM International on Conference on Emerging Networking Experiments and Technologies."},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1109\/90.851975","article-title":"Summary cache: A scalable wide-area Web cache sharing protocol","volume":"8","author":"Fan Li","year":"2000","unstructured":"Li Fan , Pei Cao , J. Almeida , and A. Z. Broder . 2000 . Summary cache: A scalable wide-area Web cache sharing protocol . IEEE\/ACM Trans. Netw. 8 , 3 (June 2000), 281--293. Li Fan, Pei Cao, J. Almeida, and A. Z. Broder. 2000. Summary cache: A scalable wide-area Web cache sharing protocol. IEEE\/ACM Trans. Netw. 8, 3 (June 2000), 281--293.","journal-title":"IEEE\/ACM Trans. Netw."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2007.892876"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2017.2778426"},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the 26th International Conference on Computer Communication and Networks (ICCCN\u201917)","author":"Gao W.","year":"2017","unstructured":"W. Gao , J. Nguyen , Y. Wu , W. G. Hatcher , and W. Yu . 2017. A bloom filter-based dual-layer routing scheme in large-scale mobile networks . In Proceedings of the 26th International Conference on Computer Communication and Networks (ICCCN\u201917) . 1--9. DOI:https:\/\/doi.org\/10.1109\/ICCCN. 2017 .8038405 10.1109\/ICCCN.2017.8038405 W. Gao, J. Nguyen, Y. Wu, W. G. Hatcher, and W. Yu. 2017. A bloom filter-based dual-layer routing scheme in large-scale mobile networks. In Proceedings of the 26th International Conference on Computer Communication and Networks (ICCCN\u201917). 1--9. DOI:https:\/\/doi.org\/10.1109\/ICCCN.2017.8038405"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/90.993304"},{"key":"e_1_2_1_11_1","first-page":"2","article-title":"Design of a multiple bloom filter for distributed navigation routing","volume":"44","author":"Jiang P.","year":"2014","unstructured":"P. Jiang , Y. Ji , X. Wang , J. Zhu , and Y. Cheng . 2014 . Design of a multiple bloom filter for distributed navigation routing . IEEE Trans. Syst. Man Cybernet.: Syst. 44 , 2 (Feb. 2014), 254--260. DOI:https:\/\/doi.org\/10.1109\/TSMC.2013.2242884 10.1109\/TSMC.2013.2242884 P. Jiang, Y. Ji, X. Wang, J. Zhu, and Y. Cheng. 2014. Design of a multiple bloom filter for distributed navigation routing. IEEE Trans. Syst. Man Cybernet.: Syst. 44, 2 (Feb. 2014), 254--260. DOI:https:\/\/doi.org\/10.1109\/TSMC.2013.2242884","journal-title":"IEEE Trans. Syst. Man Cybernet.: Syst."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2018.2813425"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2018.2852220"},{"key":"e_1_2_1_14_1","first-page":"2","article-title":"On adding bloom filters to longest prefix matching algorithms","volume":"63","author":"Lim H.","year":"2014","unstructured":"H. Lim , K. Lim , N. Lee , and K. Park . 2014 . On adding bloom filters to longest prefix matching algorithms . IEEE Trans. Comput. 63 , 2 (Feb. 2014), 411--423. DOI:https:\/\/doi.org\/10.1109\/TC.2012.193 10.1109\/TC.2012.193 H. Lim, K. Lim, N. Lee, and K. Park. 2014. On adding bloom filters to longest prefix matching algorithms. IEEE Trans. Comput. 63, 2 (Feb. 2014), 411--423. DOI:https:\/\/doi.org\/10.1109\/TC.2012.193","journal-title":"IEEE Trans. Comput."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/JIOT.2017.2683200"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIFS.2015.2493983"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2002.803864"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2015.2444850"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1587\/transcom.E98.B.1768"},{"key":"e_1_2_1_20_1","unstructured":"Probabilistic data structures for Guava.[n.d.]. Retrieved from https:\/\/github.com\/bdupras\/guava-probably.  Probabilistic data structures for Guava.[n.d.]. Retrieved from https:\/\/github.com\/bdupras\/guava-probably."},{"key":"e_1_2_1_21_1","article-title":"SCIDR: A scalable cluster based inter-domain routing protocol for heterogeneous MANET","volume":"122","author":"Rekha B.","year":"2015","unstructured":"B. Rekha and D. V. Ashoka . 2015 . SCIDR: A scalable cluster based inter-domain routing protocol for heterogeneous MANET . Int. J. Comput. Appl. 122 , 4 (2015). B. Rekha and D. V. Ashoka. 2015. SCIDR: A scalable cluster based inter-domain routing protocol for heterogeneous MANET. Int. J. Comput. Appl. 122, 4 (2015).","journal-title":"Int. J. Comput. Appl."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2014.2306060"},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of the 2nd International Conference on Devices, Circuits and Systems (ICDCS\u201914)","author":"Saravanan K.","year":"2014","unstructured":"K. Saravanan , A. Senthilkumar , and P. Chacko . 2014. Modified whirlpool hash based bloom filter for networking and security applications . In Proceedings of the 2nd International Conference on Devices, Circuits and Systems (ICDCS\u201914) . 1--6. DOI:https:\/\/doi.org\/10.1109\/ICDCSyst. 2014 .6926138 10.1109\/ICDCSyst.2014.6926138 K. Saravanan, A. Senthilkumar, and P. Chacko. 2014. Modified whirlpool hash based bloom filter for networking and security applications. In Proceedings of the 2nd International Conference on Devices, Circuits and Systems (ICDCS\u201914). 1--6. DOI:https:\/\/doi.org\/10.1109\/ICDCSyst.2014.6926138"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/LCOMM.2013.020513.122557"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/JIOT.2014.2312291"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2014.2342155"},{"volume-title":"Proceedings of the 7th IFIP Wireless and Mobile Networking Conference (VMNC\u201914)","author":"Trindade J.","key":"e_1_2_1_27_1","unstructured":"J. Trindade , R. Pereira , and T. Vazao . 2014. Scalability of bloom filter based routing for large-scale mobile networks . In Proceedings of the 7th IFIP Wireless and Mobile Networking Conference (VMNC\u201914) . J. Trindade, R. Pereira, and T. Vazao. 2014. Scalability of bloom filter based routing for large-scale mobile networks. In Proceedings of the 7th IFIP Wireless and Mobile Networking Conference (VMNC\u201914)."},{"key":"e_1_2_1_28_1","volume-title":"Proceedings of the IEEE International Conference on Intelligence and Security Informatics (ISI\u201917)","author":"Tseung C. Y.","year":"2017","unstructured":"C. Y. Tseung , K. P. Chow , and X. Zhang . 2017. Extended abstract: Anti-DDoS technique using self-learning bloom filter . In Proceedings of the IEEE International Conference on Intelligence and Security Informatics (ISI\u201917) . 204--204. DOI:https:\/\/doi.org\/10.1109\/ISI. 2017 .8004917 10.1109\/ISI.2017.8004917 C. Y. Tseung, K. P. Chow, and X. Zhang. 2017. Extended abstract: Anti-DDoS technique using self-learning bloom filter. In Proceedings of the IEEE International Conference on Intelligence and Security Informatics (ISI\u201917). 204--204. DOI:https:\/\/doi.org\/10.1109\/ISI.2017.8004917"},{"key":"#cr-split#-e_1_2_1_29_1.1","doi-asserted-by":"crossref","unstructured":"Jean-Philippe Vasseur and Adam Dunkels (Eds.). 2010. Interconnecting Smart Objects with IP. Morgan Kaufmann Boston. 387--397. DOI:https:\/\/doi.org\/10.1016\/B978-0-12-375165-2.00031-4 10.1016\/B978-0-12-375165-2.00031-4","DOI":"10.1016\/B978-0-12-375165-2.00031-4"},{"key":"#cr-split#-e_1_2_1_29_1.2","doi-asserted-by":"crossref","unstructured":"Jean-Philippe Vasseur and Adam Dunkels (Eds.). 2010. Interconnecting Smart Objects with IP. Morgan Kaufmann Boston. 387--397. DOI:https:\/\/doi.org\/10.1016\/B978-0-12-375165-2.00031-4","DOI":"10.1016\/B978-0-12-375165-2.00031-4"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/MILCOM.2015.7357477"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2872332"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNSE.2018.2869093"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/ACCESS.2018.2884906"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2018.2853575"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/ACCESS.2017.2778504"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/ACCESS.2018.2879760"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3122984"}],"container-title":["ACM Transactions on Internet Technology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3407192","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3407192","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:41:23Z","timestamp":1750200083000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3407192"}},"subtitle":["A Bloom Filter-based Dual-layer Scheme"],"short-title":[],"issued":{"date-parts":[[2020,10]]},"references-count":38,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2020,11,30]]}},"alternative-id":["10.1145\/3407192"],"URL":"https:\/\/doi.org\/10.1145\/3407192","relation":{},"ISSN":["1533-5399","1557-6051"],"issn-type":[{"type":"print","value":"1533-5399"},{"type":"electronic","value":"1557-6051"}],"subject":[],"published":{"date-parts":[[2020,10]]},"assertion":[{"value":"2019-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-10-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}