Longest Prefix Match and Incremental Updates for Range Tries

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