A longest prefix first search tree for IP lookup

One of the key design issues for IP routers is the IP lookup mechanism. IP lookup is an important action in router that is to find the next hop of each incoming packet with a longest-prefix-match address in the routing table. In this paper, we put the routing table on a longest prefix first search tree. The tree is constructed as a heap by the prefix length. That makes a router executing IP lookup have the minimal number of memory accesses as compared with Trie [Sklower, K 1991], Patricia [Nilsson, S 1999] and Prefix tree [Berger, M 2003]. Some nodes of our tree can contain two entries of the routing table to reduce the number of tree nodes. For example, a 138286 of a routing table can be stored in 132050 nodes of our tree. Furthermore, the proposed scheme makes the tree can be updated without being reconstructed from scratch when the routing table is changed, and it can be applied in both the IPv4 and IPv6 routers.