Fast Forwarding and Packet Classification

Background

Throughput bottlenecks plague the Internet because the speeds of affordable routers limp behind the speeds users desire and fiber-optics can deliver. Emerging services such as Virtual Private Networks, firewalls, QoS routing, multimedia broadcasts, or real-time conferencing require fast matching of each packet's header against a potentially large database of multi-dimensional filter rules. This combined lack of power and flexibility to provide for the deployment of new services poses a major limitation on future Internet services. We thus worked on improving the router speeds by providing new algorithms and enabling high-speed, easy-to-use, flexible, and modular support for programmable hardware.

Solutions

Fast Longest Prefix Matching

One major reason for the limited speed of Internet connections is the complex packet forwarding decision required for Internet Protocol (IP) packets. To keep the size of the routing database small, packets today have to be matched against a continuously growing routing tables of currently up to 100,000 entries, containing possibly overlapping prefixes of variable length. Among these matches, the search must return the longest matching prefix. With current Internet links being able to handle many million packets per second, and speeds fast increasing, this becomes a serious task. With the hundreds of millions of systems out there relying on the Internet Protocol, changing the protocol was not an option.

The traditional trie approach to packet forwarding requires work proportional to the number W of address bits (32 for the current version of the Internet Protocol, dubbed IPv4; 128 for the upcoming IP version 6). To achieve improvements in computational complexity and thus scalability to higher speeds and larger routing tables, we radically departed from slow linear search among the prefixes and introduced binary search on prefix lengths. Even though this had previously been considered inefficient by researchers, we started placing the individual prefixes in hash tables according to their prefix length. The challenge was to leave behind linear search and adopt binary search among the tables, even though binary search depends on ordered comparisons which hash tables do not provide. O(log W) search time for the best match is achieved through placement of a small number of guiding entries ("Markers") into the hash tables at predetermined decision points, enabling us to achieve with this new algorithm what was previously considered to be impossible.

To improve beyond the O(log W) time, we provide for Asymmetric Binary Search and Rope Search, which exploit the inherent non-uniformity of the routing tables. Rope Search piggybacks an extremely compact representation of a refined search tree onto the entries and Markers, narrowing the search faster than conventional binary search, namely in both the prefix length and address range dimensions at the same time. Ropes thus introduce a powerful new data structure, enabling a compact and highly efficient search algorithm.

Our original paper in SIGCOMM '97 (together with another presentation on the same day) started an active new research area with a lot of research activities. Our work has been heavily cited and made it into many textbooks. Our schemes have been used by other researchers and were licensed to several key players in the networking market.

High-Speed Packet Classification

Extending on our work in prefix matching to algorithms, we provided for multi-dimensional prefix-style addresses and wildcardable fields to match protocol and port numbers. Again, this paper was followed by a flurry of activity in that newly-created area.

Line Search and its sibling Rectangle Search are algorithms we have developed for two-dimensional Longest Prefix Matching. They naturally extend our Binary Search on Prefix Lengths scheme to prefix pairs, with Markers guiding the search among them. In addition to a logarithmic line optimization algorithm designed for two-dimensional optimization, the one-dimensional techniques Rope Search and Asymmetric Search become even more powerful in two dimensions.

I have also helped initiate new Space Division techniques that combine results from computational geometry with our own enhancements to provide a second solution to two-dimensional packet classification. This results in tight bounds for space, search, and insertion/deletion times.

An additional decision layer easily extends the two-dimensional schemes to efficiently support wildcardable protocol and port fields.

High-Speed Configurable Router Hardware

To speed up things further and show the feasibility of hardware implementations, we implemented the algorithm in hardware, requiring substantial changes to efficiently exploit the available inherent parallelism, including changing binary search to k-ary search. We expanded this into a full-featured, flexible framework of hardware-supported packet processing, which has since been used as a teaching tool and as a basis for many applications. To support high-speed operations, we provided a high-speed way to update CRCs of packets being modified, improving speed by an order of magnitude compared to conventional approaches.

Overlays for High-Speed Forwarding

Overlay networks have the power to augment and maybe at some time partially replace the Internet. We are looking at overlay networks that provide for mechanisms that would allow them to be used as a general-purpose protocol. The main goal of Mithos (Mapping Internet Topology for Hybrid Overlay Services) is to provide for use of locality, minimum routing information (neighborhood information only), and efficient forwarding, while also providing for location triangulation and supporting distributed hash tables (DHTs) on top.

Publications

Participants

• Florian Braun
• Milind Buddhikot
• Thomas Meyer, whose report (in German) discusses and evaluates optimization strategies
• Samphel Norden
• V. "Cheenu" Srinivasan
• Jon Turner
• George Varghese
• Marcel Waldvogel

Licensing Terms

This work is covered by U.S. patent 6,018,524. Please contact Marcel Waldvogel for further information regarding licensing. Some further information (including a description intended for a general audience) can be found in The Fastest Lookups in the West. For non-commercial use, a free license is planned. Please inquire for more details.

Selected Press Coverage

• James Glave:
  Lookups Looking Up,
  Wired Magazine, April 1998.
• Neil Gross:
  Will Zip Codes for E-Mail be Next?,
  Business Week February 9, 1998
  (also covered in the February 5, 1998 issue of Edupage).
• Gene Koprowski:
  Router Breakthrough Takes Net Traffic to Task,
  Wired News, January 20, 1998
• William Allen:
  WU Inventions Make Data Zip Along the Net,
  St. Louis Post-Dispatch, January 4, 1998 (Front Page)