Scalable Name Lookup for NDN Using Hierarchical Hashing and Patricia Trie
Source abstract
Abstract
Named data networking (NDN) is a content-centric network for the future of the internet. An NDN a packet is delivered based on a content name instead of a destination IP address. The name lookup for packet forwarding is challenging because the content name is variable, and its space is unbounded. This paper proposes a novel name lookup scheme that employs a hashing technique combined with Patricia tries. In this scheme, hash tables are dynamically maintained according to the hierarchical structure of the name, so the name can effectively accommodate variable and unbounded content names. Unlike chaining, a Patricia trie compares a key string only once at a leaf node, so it provides a fast name lookup. The proposed lookup scheme is implemented and evaluated by using an Intel Core i7-2600 CPU and 4GB of memory. Experimental results show that our scheme gives good scalability and a high throughput of name lookup with a controlled memory consumption.
Source: crossref · Quality: baseline
Research context
OpenAlex topics: Caching and Content Delivery · Network Packet Processing and Optimization · Cooperative Communication and Network Coding
SciVX discovery tags are terminology-based. OpenAlex topics are source-provided classifications.
Affiliations
Department of Software Technology, Konkuk University, Chungcheongbuk-do 27478, Korea
References (27)
Show source-provided references
1. A survey of information-centric networking10.1109/MCOM.2012.6231276 ↗
2. A survey of the research on future internet architectures10.1109/MCOM.2011.5936152 ↗
3. Named data networking10.1145/2656877.2656887 ↗
4. Survey and taxonomy of IP address lookup algorithms10.1109/65.912716 ↗
5. Li, F., Chen, F., Wu, J., and Xie, H. (2014, January 6–8). Longest prefix lookup in named data networking: How fast can it be?. Proceedings of the 9th IEEE International Conference on Networking, Architecture, and Storage (NAS), Tianjin, China.10.1109/NAS.2014.36 ↗
6. Yuan, H., Song, T., and Crowley, P. (August, January 30). Scalable NDN forwarding: Concepts, issues and principles. Proceedings of the 21st International Conference on Computer Communications and Networks (ICCCN), Munich, Germany.
7. An Efficient Prefix Caching Scheme for Fast Forwarding in Named Data Networking10.24846/v27i2y201805 ↗
8. A survey of naming and routing in information-centric networks10.1109/MCOM.2012.6384450 ↗
9. IP-address lookup using LC-tries10.1109/49.772439 ↗
10. Scalable pipelined IP lookup with prefix tries10.1016/j.comnet.2017.03.017 ↗
11. Sun, Y., Egi, N., Shi, G., and Wu, J. (2012, January 3–7). Content-based route lookup using CAMs. Proceedings of the 2012 IEEE Global Communications Conference (GLOBECOM), Anaheim, CA, USA.10.1109/GLOCOM.2012.6503521 ↗
12. Lee, J., and Lim, H. (2016, January 26–28). A new name prefix trie with path compression. Proceedings of the 2016 IEEE International Conference on Consumer Electronics-Asia (ICCE-Asia), Seoul, Korea.10.1109/ICCE-Asia.2016.7804781 ↗
13. Li, D., Li, J., and Du, Z. (2016, January 27–30). An improved trie-based name lookup scheme for named data networking. Proceedings of the 2016 IEEE Symposium on Computers and Communication (ISCC), Messina, Italy.
14. Wang, Y., Dai, H., Jiang, J., He, K., Meng, W., and Liu, B. (2011, January 5–9). Parallel name lookup for named data networking. Proceedings of the 2011 IEEE Global Telecommunications Conference (GLOBECOM 2011), Houston, TX, USA.
15. Wang, Y., He, K., Dai, H., Meng, W., Jiang, J., Liu, B., and Chen, Y. (2012, January 18–21). Scalable name lookup in NDN using effective name component encoding. Proceedings of the 32nd International Conference on Distributed Computing Systems (ICDCS), Macau, China.10.1109/ICDCS.2012.35 ↗
16. Wang, Y., Pan, T., Mi, Z., Dai, H., Guo, X., Zhang, T., Liu, B., and Dong, Q. (2013, January 14–19). Namefilter: Achieving fast name lookup with low memory cost via applying two-stage bloom filters. Proceedings of the 2013 INFOCOM, Turin, Italy.10.1109/INFCOM.2013.6566742 ↗
17. Wang, Y., Qi, Z., Dai, H., Wu, H., Lei, K., and Liu, B. (2017, January 18–19). Statistical Optimal Hash-based Longest Prefix Match. Proceedings of the 2017 ACM/IEEE Symposium on Architectures for Networking and Communications Systems, Beijing, China.10.1109/ANCS.2017.29 ↗
18. Yuan, H., and Crowley, P. (2015, January 7–8). Reliably scalable name prefix lookup. Proceedings of the 2015 ACM/IEEE Symposium on Architectures for Networking and Communications Systems, Oakland, CA, USA.10.1109/ANCS.2015.7110125 ↗
19. Name prefix matching using bloom filter pre-searching for content centric network10.1016/j.jnca.2016.02.008 ↗
20. BFAST: High-Speed and Memory-Efficient Approach for NDN Forwarding Engine10.1109/TNET.2016.2623379 ↗
21. So, W., Narayanan, A., Oran, D., and Wang, Y. (2012, January 29–30). Toward fast NDN software forwarding lookup engine based on hash tables. Proceedings of the 2012 ACM/IEEE Symposium on Architectures for Networking and Communications Systems, Austin, TX, USA.10.1145/2396556.2396575 ↗
22. TCAM architecture for IP lookup using prefix properties10.1109/MM.2004.1289292 ↗
23. A TCAM-based distributed parallel IP lookup scheme and performance analysis10.1109/TNET.2006.880171 ↗
24. Scalable name lookup with adaptive prefix bloom filter for named data networking10.1109/LCOMM.2013.112413.132231 ↗
25. Yuan, H., Crowley, P., and Song, T. (2017, January 18–19). Enhancing Scalable Name-Based Forwarding. Proceedings of the 2017 ACM/IEEE Symposium on Architectures for Networking and Communications Systems, Beijing, China.10.1109/ANCS.2017.16 ↗
26. Cormen, T.H., Leiserson, C.E., Rivest, R.L., and Stein, C. (2009). Hash tables. Introduction to Algorithms, MIT Press. [3rd ed.].
27. (2016, November 05). Directory of World Wide Web. Available online: http://www.dmoz.org/.