Importance

Loading Importance Indicators...

Abstract

The present invention provides a technique for efficiently looking up address-routing information in an intermediate network node, such as a router. To that end, the node locates routing information stored in its memory using one or more 'lookup' tables (LUT) which can be searched using a small, bounded number of dependent lookups, thereby reducing the number of dependent lookups conventionally performed. The LUTs are arranged so each table provides routing information for network addresses whose subnet mask lengths are within a different range ('stride') of mask lengths. According to the technique, the node locates a network address's routing information by searching the LUTs, in order of decreasing prefix lengths, until the routing information is found. Preferably, several tables are searched in parallel. A match in a LUT may further point to a small MTRIE that enables the final bits of a prefix to be matched. That final MTRIE is searched using a relatively small, bounded number of dependent lookups.

Loading the Abstract Image...

First Claim