Paper Info
Title
Flexible and fast IP lookup algorithm
Abstract
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
Year
DOI
Venue
2001
10.1109/ICC.2001.937020
ICC
Keywords
Field
DocType
patricia trie,giga-bit routing performance,fast ip table lookup algorithm,ip address searching time,backbone routers,memory requirement,search problems,transport protocols,network size,routing table,internet,scalability problem,internet traffic,flexible ip lookup algorithm,telecommunication network routing,table updating time,table lookup,scalability,linux,spine,routing
Default-free zone,Computer science,Static routing,Enhanced Interior Gateway Routing Protocol,Computer network,Algorithm,route,Loose Source Routing,Routing table,IP forwarding,Virtual routing and forwarding
Conference
Volume
ISBN
Citations 
7
0-7803-7097-1
2
PageRank 
References 
Authors
0.93
4
2
Name
Order
Citations
PageRank
Wooguil Pak1379.83
Saewoong Bahk21024112.58