Exploring Probabilistic Data Structures for Multi-Path Routing Optimization in Named Data Networks

• Fabio Santos dos Santos UFBA http://orcid.org/0009-0007-0221-7317
• Italo Valcy S. Brito UFBA https://orcid.org/0000-0002-2669-2792
• André L. R. Madureira UFBA https://orcid.org/0000-0002-0780-5480
• Leobino N. Sampaio UFBA https://orcid.org/0000-0003-4855-0936

DOI: https://doi.org/10.5753/wpeif.2025.9053

Abstract

Routing protocols are essential for accurately discovering reachability information in Named Data Networking (NDN). In networks with multiple paths, Link State-based protocols, such as NLSR, may not be the most appropriate option due to their high synchronization complexity and computational effort. On the other hand, Distance Vector-based protocols offer a simpler synchronization process. However, their discovery mechanism faces challenges in delivering high-quality routes in multipath scenarios. We propose an approach to mitigate these limitations by using probabilistic data structures. The results obtained in an emulation environment demonstrate that the proposed solution provides a higher NDN packet delivery rate and a significant reduction in the number of unsatisfied interests, proving to be more effective.

Keywords: Named Data Networks (NDN), Multipath Routing, Distance Vector Protocols, Probabilistic Data Structures, Bloom Filter, Invertible Bloom Filter (IBF), Route Optimization, Load Balancing, Routing Loop Minimization, MiniNDN, NDVR, Unsatisfied Interests, Packet Delivery Rate, High Availability, Protocol Scalability

References

Bindu, G. (2023). Efficient bloom filter-based routing protocol for scalable mobile networks. Engineering Proceedings, 59(1), 75.

Bloom, B. H. (1970). Space/time trade-offs in hash coding with allowable errors. Communications of the ACM, 13(7), 422–426.

Brito, I. V. S. (2021). NDVR: NDN Distance Vector Routing. Technical report, Federal University of Bahia.

Brito, I. V. S., & Sampaio, L. N. (2021). Roteamento em redes de dados nomeados com ndvr: um protocolo leve e eficiente para disseminação de informações de alcançabilidade. In Anais do XXXIX SBRC 2021 (pp. 574–587). SBC.

Goodrich, M. T., & Mitzenmacher, M. (2011). Invertible bloom lookup tables. In 2011 49th Annual Allerton Conference on Communication, Control, and Computing (Allerton) (pp. 792–799). IEEE.

Karim, F. A., Aman, A. H. M., Hassan, R., Nisar, K., & Uddin, M. (2022). Named data networking: A survey on routing strategies. IEEE Access, 10, 90254–90270.

Marandi, A., Braun, T., Salamatian, K., & Thomos, N. (2017). BFR: A bloom filter-based routing approach for information-centric networks. In 2017 IFIP Networking Conference (IFIP Networking) and Workshops (pp. 1–9). IEEE.

Marandi, A., Braun, T., Salamatian, K., & Thomos, N. (2019). Pull-based bloom filter-based routing for information-centric networks. In 2019 16th IEEE Annual Consumer Communications & Networking Conference (CCNC) (pp. 1–6). IEEE.

Patil, V., Theeranantachai, S., Zhang, B., & Zhang, L. (2024). Poster: Distance vector routing for named data networking. In Proceedings of the 20th International Conference on emerging Networking EXperiments and Technologies (pp. 23–24).

Pratama, C. S., Arrachman, M. I., Nurrasyid, M. S., Hamidi, E. A. Z., Negara, R. M., Ahdan, S., Mayasari, R., & Syambas, N. R. (2023). Random load balancing in mini-NDN using modified inherent topology. In 2023 9th International Conference on Wireless and Telematics (ICWT) (pp. 1–6). IEEE.

Sampaio, L. N., Freitas, A. E., Brito, I. V., Araújo, F. R. C., & Ribeiro, A. V. (2021). Revisitando as ICNs: Mobilidade, segurança e aplicações distribuídas através das redes de dados nomeados. Sociedade Brasileira de Computação.

Wang, L., Lane, A., Serban, C., Elwell, J., Afanasyev, A., & Zhang, L. (2023). Investigating the synergy between routing and forwarding strategy in NDN networks. In Proceedings of the 10th ACM Conference on ICN (pp. 67–77).