Washington University

George Varghese

Srinivasan Venkatachary

Marcel Waldvogel

Jonathan S Turner

Subhash Suri

Hari Adiseshu

A new process called &ldquo;crossproducting&rdquo; allows level 4 switching to be performed at gigabit speeds. In crossproducting, a database of routing filters or rules is &ldquo;sliced&rdquo; into columns corresponding to fields. Each column represents a set of prefixes or ranges. Given a data packet P, a best matching prefix or narrowest enclosing range lookup is performed separately for each packet field. The results of the lookups on individual fields are concatenated to quickly determine the earliest matching rule. The search can be optimized further through such techniques as removing default entries, creating multiple crossproduct tables, caching crossproducts, and early stopping, the latter optimization being made possible by recognizing that it is not necessary in all cases to search all columns for a match. The inventive devices and methods are applicable to various types of networks, including, but not limited to, the Internet and related types of networks, and telephone switching networks.

Fast level four switching using crossproducting

Fast, scalable methods and devices are provided for layer four switching in a router as might be found in the Internet. In a first method, a grid of tries, which are binary branching trees, is constructed from the set of routing filters. The grid includes a dest-trie and a number of source tries. To avoid memory blowup, each filter is stored in exactly one trie. The tries are traversed to find the lowest cost routing. Switch pointers are used to improve the search cost. In an extension of this method, hash tables may be constructed that point to grid-of-tries structures. The hash tables may be used to handle combinations of port fields and protocol fields. Another method is based on hashing, in which searches for lowest cost matching filters take place in bit length tuple space. Rectangle searching with precomputation and markers are used to eliminate a whole column of tuple space when a match occurs, and to eliminate the rest of a row when no match is found. Various optimizations of these methods are also provided. A router incorporating memory and processors implementing these methods is capable of rapid, selective switching of data packets on various types of networks, and is particularly suited to switching on Internet Protocol networks.

Fast scaleable methods and devices for layer four switching

A method and apparatus for an exponentially faster technique than is presently utilized in routers for looking-up destination addresses and matching them to a prefix in order to determine an output data link for routing of the data message to a destination. The basic algorithm includes arranging the prefix and corresponding output data link information in sub-databases arranged by prefix length and then using a multi-step prefix length binary search algorithm to sort through the sub-databases to determine a best matching prefix for routing of the data packet. Various refinements of the basic algorithm are disclosed to further enhance the search time including adding markers representative of sub-database entries having a longer prefix length and also various searching methodologies to minimize the number of searching steps including rope searching in various formats. Thus, methodologies are disclosed for building the sub-databases, as appropriate to implement the corresponding novel search routines and perform the novel search routines themselves, and the router which implements all of the foregoing. Many of the inventive features disclosed herein are applicable to other routing DPJ protocols such as OSI Routing, call routing and telephone DPJ networks, and string matching problems.

Scalable high speed IP routing lookups

Many network protocols, including the Internet, have addresses that are structured hierarchically. The hierarchy is expressed by an address prefix P that represents all addresses in the given hierarchical level that starts with prefix P. The hierarchy is not strict and can be overridden by more inclusive hierarchies. This is achieved by having network routers find the longest prefix that matches a destination address in a message. The disclosed invention describes a method and apparatus for implementing controlled expansion: for expanding a set of prefixes into an equivalent (possibly larger) set of prefixes that have a smaller set of prefix lengths. The new set of prefixes can then be looked up significantly faster using any technique whose speed improves by reducing the number of prefix lengths. Our invention also incorporates fast techniques to insert and delete new prefixes, and a technique of pointer hoisting to halve the memory READs needed for trie search. Our solution to longest matching prefix also applies to other routing protocols such as OSI Routing, call routing in telephone networks, and to string matching problems.

Growing community of inventors

St. Louis, MO, United States of America

George Varghese