Flexible and fast IP lookup algorithm

We introduce a fast IP table lookup algorithm that improves the table updating time as well as the IP address searching time. Because routers with Patricia trie can not support giga-bit performance, many algorithms to support giga-bit routing performance by reducing the searching time have been introduced. Most of them, however, did not considerably count the importance of the updating time. As a network often falls into unstable states, a router may generate and receive hundreds of update request messages per second. So the router should be able to update its routing table at least 1000 times per second to appropriately run in real networks. We consider the updating time as much an important factor as the searching time in proposing a flexible and fast IP lookup algorithm (FFILA). Our scheme searches the table about 3 times faster than Patricia trie. It also shows improved performance in updating time by at least 30% when compared with Patricia trie. Also as many backbone routers today have over 100,000 routing table entries and its number is still increasing due to the growth in the network size, the memory requirement for the lookup algorithm becomes more important. An additional advantage of our algorithm is in its small memory requirement, which is good to overcome the scalability problem