Abstract:This paper proposed a parallel multi-level pipeline IP lookup architecture based on distributed storage of routing table that consists of multi-stage lower speed nodes called FSN performing IP-lookups and switching independently. An IPv6 binary lookup algorithm was proposed based on prefix scope called PSB-BS (prefix scope based binary search) for putting IPv6 longest prefix match in practice. The IPv6 route table was partitioned into multiple levels, each representing a specified range of prefixes. By doing binary search over these subtrie levels and especially by constructing asymmetric binary tree, our solution implemented distributed storage of forwarding table, thus reducing the storage overhead as well as the complexity of IP lookup. The experiment results demonstrate the PSB-BS algorithm reduces the storage and memory access overhead considerably, compared with the tree bitmap algorithm widely used in Cisco commercial routers.