Importance

Loading Importance Indicators...

Abstract

The routing address lookup problem is one of the major bottlenecks in high performance routers and deals with forwarding of packets. In the Internet domain it is known as 'IP address lookup problem.' This invention provides a new and easy way to preprocess routing tables which gives efficient packet/message forwarding and is feasible in the time and the space it consumes. More precisely, the method for m-bit IP addresses gives a balanced trade-off between performing a binary search on T with O(log.vertline.T.vertline.) accesses, where .vertline.T.vertline. is the number of entries in T, and executing a single access on a table of 2.sup.m entries obtained by fully expanding T. While the prior art starts out from space-efficient data structures and aim at lowering the O(log.vertline.T.vertline.) access cost, the invention starts out from the expanded table with 2.sup.m entries and aim at compressing it without an excessive increase in the number of accesses. The embodiment results in a lookup which takes exactly three memory accesses in tables which occupy O(2.sup.m/2 +.vertline.T.vertline..sup.2) space in the worst case. Since the Internet is more structured real routing tables for IP with m=32 bits, should take even much smaller space. For most routers the cache is sufficient to include our tables whereas dedicated routers need only a few megabytes cache for large tables. The impact of fast lookup is increased network bandwidth.

Loading the Abstract Image...

First Claim