Fast and efficient internet lookups
Srinivasan Venkatachary, George Varghese · 1999
The Internet has been growing exponentially, reaching an estimated 45 million hosts in Jan 1999. Internet traffic is doubling every 3 months because of increasing number of web users, and because of new bandwidth intensive multimedia applications. The Internet is a global computer network that primarily consists of computers connected by communication links with intermediate switch points called routers. So for improved Internet performance, we need faster computers, faster communication links and faster routers. Processing power has been on the increase, with even cheap personal computers gaining the ability to support complex multimedia application. Communication links have kept pace with increasing traffic requirements, and gigabit fiber links are commonplace. This leaves Internet routers as bottlenecks in Internet performance. Specifically, the packet header processing component of a router is the major bottleneck in today's router forwarding performance. Towards removing this bottleneck, we present fast and scalable algorithms for header processing. We present efficient algorithms (which can be implemented even in software to support gigabit speeds) for destination address lookups and fast filter matching, which are important components of packet processing in a router. Routers have what is called a ‘forwarding table’ that they consult in order to forward the packet to the next router in the packets path. When this decision depends only on the destination address of the packet, we call it Layer 3 forwarding. When this decision depends on the header fields like protocol, destination address, source address, destination and source ports etc., we refer to it as Layer 4 forwarding. The destination address lookup problem is to find the longest matching prefix for a given address from among a set of prefixes in the router's forwarding table. In Layer 4 forwarding, the problem is to find the best matching ‘filter’ for a given packet header. Each filter (e.g. firewall filters) is a rule specified on multiple header fields. Our algorithms for address lookups are designed to work with bounded worst case lookup times, update times and memory requirements. Our algorithms are licensed to several major networking companies and are used in their products. We propose a better filter caching strategy called cross-product caching which will have better hit rates than caching full headers. We also provide incremental cache update algorithms using timestamp based lazy update techniques. We have developed algorithms for fast filter matching that rely on hashing which we generically call ‘Tuple Space Search Schemes’. (Abstract shortened by UMI.)