Fast address lookup in routing tables
US6581106B1 · kind B1 · utility
Inventors
Key dates
| Filing date | Jan 13, 2000 |
| Grant date | Jun 17, 2003 |
| Priority date | — |
| Expiry date | Jan 13, 2020 |
Classification
- Technology area (CPC H)Electricity
- CPC primaryH04L2101/604
- WIPO fieldDigital communication
- WIPO sectorElectrical engineering
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|T|) accesses, where |T| is the number of entries in T, and executing a single access on a table of 2m entries obtained by fully expanding T. While the prior art starts out from space-efficient data structures and aim at lowering the O(log|T|) access cost, the invention starts out from the expanded table with 2m 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(2m/2+|T|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 cach…
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.