Scalable High Speed IP Routing Lookups

Date Added: Jan 2010
Format: PDF

The Internet is becoming ubiquitous?everyone wants to be a part of it. Since the advent of the World Wide Web, the number of users, hosts, domains, and networks connected to the Internet seem to be exploding. The increasing traffic demand requires three key factors to keep pace if the Internet is to continue to provide good service: link speeds, router data throughput, and packet forwarding rates. Readily available solutions exist for the first two factors: for example, fiber-optic cables can provide faster links, and switching technology can be used to move packets from the input interface of a router to the corresponding output interface at gigabit speeds. This paper deals with the third factor, packet forwarding, for which current techniques perform poorly as network speeds increase. IP routing lookup requires computing the best matching prefix, for which standard solutions like hashing are believed to be inapplicable. This paper describes a new algorithm for best matching prefix using binary search on hash tables organized by prefix lengths. It is a fast, scalable solution for IP lookups that can be implemented in either software or hardware. The scheme scales very well as address and routing table sizes increase. A Mutating Binary Search is also introduced and other optimizations that, for a typical IPv4 backbone router with over 33,000 entries, considerably reduce the average number of hashes to less than 2, of which one hash can be simplified to an indexed array access.