Multilevel length-based classified index table for IP lookups and updates

To obtain a high-speed IP address lookup algorithm for wire-speed packet forwarding in Internet routers, a new data structure, called multilevel length-based classified index table, is proposed. This data structure can be divided into multilevel structures on the basis of prefix length distribution. Each level has a corresponding data structure and dynamic router-table operations. Experiments were performed using real-world routing databases, wherein the proposed data structure was compared with other structures by using the benchmark IPv4 and IPv6 prefix databases AS1221, AS4637, AS6447, AS1221*, and AS6447*. The average lookup time and the average update time of the proposed structure were superior to those of the other data structures; the memory requirement was lower than that of simple structures, such as prefix trees and priority tries.