Longest Prefix Match and Incremental Updates for Range Tries

Abstract

Address lookup has become a major bottleneck in the performance of today's network routers with rapid increase in the urge for faster and high bandwidth communication. The most crucial metrics for a lookup algorithm being lookup speed, scalability and memory usage, the Range Trie algorithm provided the much needed solution to the diminishing benefits of the current address lookup algorithms. The proposed design provides Longest Prefix Match and Incremental Update support to the existing Range Trie method. The design offers faster update rates maintaining the inherent properties of the Range Trie with increasing address width and routing table size. The design only requires D memory accesses for address lookup and 4*D memory accesses(2*D read and 2*D write) for an update operation where D=depth of the tree. Each update operation requires a bubble of 4 cycles in the pipeline. The pipelined hardware design is prototyped on a Xilinx ML410 Embedded development platform(Virtex4 XC4VFX60). The Range Trie 90-nm ASIC implementation can perform 630 million lookups with no updates and more than 625 million lookups with up to 1 Million updates per second. The Range Trie design outperforms the existing designs showing better scalability and performance with minimum resource requirements.