A scalable pipeline architecture for IPv4/IPv6 route lookup

摘要

When the Internet is evolving from IPv4 to IPv6, there is a need in practice for route lookup algorithms that can simultaneously support IPv4 and IPv6 packets. A scalable pipeline routing architecture for route lookups of IPv4/IPv6 packets using a prefix trie is studied in this work. In this routing architecture, a routing table is mapped into an index table and a number of prefix tries. Each prefix trie is further divided into multiple subtries, where two copies are maintained for each subtrie. Specifically, each subtrie has two copies rooted in two different memory blocks. For each copy of a subtrie, the root node is stored in a randomly selected memory block and the other descendant nodes are cyclically stored in the subsequent memory blocks in a manner of one level per block. The scheduling problem in such an architecture is modeled as bipartite matching between packets and memory blocks. For performance evaluation, extensive simulation experiments have been conducted for typical IPv4 and IPv6 corpora. The simulation results indicate that this routing architecture can achieve high system's throughputs under both IPv4 and IPv6 traffic loads.