Abstract
The challenge of achieving the Longest Prefix Match (LPM) in IP address lookup remains a bottleneck in high-speed routers. Classless Inter-Domain Routing (CIDR) utilizes member query algorithms within Packet Forwarding Engines (PFE) to determine whether a packet's next hop should be forwarded through a specific output port. Among these, Bloom Filters (BF), Scalar Vector Routing and Forwarding (SVRF), and their improved variants have all proven efficient for rapid packet forwarding. In this paper, we propose a Unicast Packet Forwarding Accelerator design that utilizes the Chinese Remainder Theorem (CRT), Residue Number System (RNS), and SVRF. This framework associates prefix lengths with processing blocks by partitioning n-elements into 22 columns (sub-blocks) based on prefix lengths. Within each sub-block, IP addresses are parallelly computed for output port indexing, optimizing the partitioning of scalar vectors to facilitate the determination of address membership in a prefix set sorted by prefix length. This scheme optimization simultaneously addresses the Longest Prefix Match problem while reducing memory space usage and forwarding latency. Furthermore, we perform an analysis of snapshots from real-world IPV4 BGP tables to instantiate and simulate the performance of our algorithm. Simulation evaluations demonstrate that our proposed algorithm offers significant advantages in terms of both time and space efficiency under optimized partitioning.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Dharmapurikar, S., Krishnamurthy, P., Sproull, T., Lockwood, J.: Deep packet inspection using parallel Bloom filters. In: 11th Symposium on High Performance Interconnects, 2003. Proceedings, pp. 44–51 (2003)
BGP Reports. https://bgp.potaroo.net/
CIDR Report. https://www.cidr-report.org/as2.0/
Hinden, B.: Applicability statement for the implementation of classless inter-domain routing (CIDR). In: Internet Engineering Task Force (1993)
Waldvogel, M., Varghese, G., Turner, J., Plattner, B.: Scalable high-speed prefix matching. ACM Trans. Comput. Syst. 19, 440–482 (2001)
Cerović, D., Del Piccolo, V., Amamou, A., Haddadou, K., Pujolle, G.: Fast packet processing: a survey. IEEE Commun. Surv. Tutor. 20, 3645–3676 (2018)
Aweya, J.: Introduction to switch/router architectures. In: Switch/Router Architectures: Shared-Bus and Shared-Memory Based Systems, pp. 1–16. IEEE (2018)
Wei, J., Jiang, H., Zhou, K., Feng, D.: Efficiently representing membershipfor variable large data sets. IEEE Trans. Parallel Distrib. Syst. 25, 960–970
Aweya, J.: Switch/Router Architectures: Shared-Bus and Shared-Memory Based Systems. Wiley, Hoboken (2018)
Radoslavov, P.I., Estrin, D., Govindan, R.: Exploiting the Bandwidth-Memory Tradeoff in Multicast State Aggregation
Li, Q., Xu, M., Wang, D., Li, J., Jiang, Y., Yang, J.: Nexthop-selectable FIB aggregation: an instant approach for internet routing scalability. Comput. Commun. 67, 11–22 (2015)
Ghosh, S., Baliyan, M.: A hash based architecture of longest prefix matching for fast IP processing. In: 2016 IEEE Region 10 Conference (TENCON), pp. 228–231 (2016)
Zarandi, A.A.E.: RNS applications in computer networks. In: Molahosseini, A.S., de Sousa, L.S., Chang, C.-H. (eds.) Embedded Systems Design with Special Arithmetic and Number Systems, pp. 369–380. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-49742-6_14
Eatherton, W., Varghese, G., Dittia, Z.: Tree bitmap: hardware/software IP lookups with incremental updates. SIGCOMM Comput. Commun. Rev. 34, 97–122 (2004)
Degermark, M., Brodnik, A., Carlsson, S., Pink, S.: Small forwarding tables for fast routing lookups. SIGCOMM Comput. Commun. Rev. 27, 3–14 (1997)
Hasan, J., Cadambi, S., Jakkula, V., Chakradhar, S.: Chisel: A Storage-efficient, collision-free hash-based network processing architecture. In: 33rd International Symposium on Computer Architecture (ISCA 2006). pp. 203–215 (2006)
Pong, F., Tzeng, N.-F.: Concise lookup tables for IPv4 and IPv6 longest prefix matching in scalable routers. IEEE/ACM Trans. Netw. 20, 729–741 (2012)
Tobola, J., Kořenek, J.: Effective hash-based IPv6 longest prefix match. In: 14th IEEE International Symposium on Design and Diagnostics of Electronic Circuits and Systems, pp. 325–328 (2011)
Tzeng, H.H.-Y., Przygienda, T.: On fast address-lookup algorithms. IEEE J. Sel. Areas Commun. 17, 1067–1082 (1999)
Chazelle, B., Kilian, J., Rubinfeld, R., Tal, A.: The bloomier filter: an efficient data structure for static support lookup tables (2004)
Park, G., Kwon, M.: An enhanced bloom filter for longest prefix matching. In: 2013 IEEE/ACM 21st International Symposium on Quality of Service (IWQoS), pp. 1–6 (2013)
Lim, H., Lim, K., Lee, N., Park, K.-H.: On adding bloom filters to longest prefix matching algorithms. IEEE Trans. Comput. 63, 411–423 (2014)
Song, H., Hao, F., Kodialam, M., Lakshman, T.V.: IPv6 lookups using distributed and load balanced bloom filters for 100 Gbps core router line cards. In: IEEE INFOCOM 2009, pp. 2518–2526 (2009)
Pei, D., Salomaa, A., Ding, C.: Chinese Remainder Theorem: Applications In Computing, Coding, Cryptography. World Scientific, Singapore (1996)
Jia, W.-K., Wang, L.-C.: A unified unicast and multicast routing and forwarding algorithm for software-defined datacenter networks. IEEE J. Select. Areas Commun. 31, 2646–2657 (2013)
Jia, W.-K., Jin, Z.: Fractional- N SVRF forwarding algorithm for low port-density packet forwarding engines. IEEE Netw. Lett. 3, 42–46 (2021)
Route Views Archive Project Page. http://archive.routeviews.org/
Lim, H., Seo, J.-H., Jung, Y.-J.: High speed IP address lookup architecture using hashing. IEEE Commun. Lett.Commun. Lett. 7, 502–504 (2003)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2024 ICST Institute for Computer Sciences, Social Informatics and Telecommunications Engineering
About this paper
Cite this paper
Zhu, L., Jia, WK. (2024). A Unicast Packet Forwarding Accelerator Design Based on the RNS Algorithm. In: Gao, F., Wu, J., Li, Y., Gao, H., Wang, S. (eds) Communications and Networking. Chinacom 2023. Lecture Notes of the Institute for Computer Sciences, Social Informatics and Telecommunications Engineering, vol 590. Springer, Cham. https://doi.org/10.1007/978-3-031-67162-3_25
Download citation
DOI: https://doi.org/10.1007/978-3-031-67162-3_25
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-67161-6
Online ISBN: 978-3-031-67162-3
eBook Packages: Computer ScienceComputer Science (R0)