Hardware-Based IP Routing Using Partitioned Lookup Table

摘要

We present a search algorithm implementable by a parallel architecture based on partitioned forwarding table. This scheme effectively reduces the complexity of finding “the longest prefix match” problem to “a prefix match” problem. The main feature of this algorithm is twofold. First, it advocates intelligent partitioning of the forwarding table to enhance and parallelize the lookup operation. Second, it takes advantage of ternary CAM to achieve low lookup time. The resulting architecture has better throughput and much better update time than the traditional TCAM. Our experimental results show that such features can significantly elevate the flexibility and scalability of the next generation packet processing devices.