Fast routing lookup system using complete prefix tree, bit vector, and pointers in a routing table for determining where to route IP datagrams
US6266706A · kind A · utility
Assignee
Inventors
Key dates
| Filing date | Apr 17, 1998 |
| Grant date | Jul 24, 2001 |
| Priority date | — |
| Expiry date | Apr 17, 2018 |
Classification
- Technology area (CPC H)Electricity
- CPC primaryH04L45/74591
- WIPO fieldDigital communication
- WIPO sectorElectrical engineering
Abstract
In a method of IP routing lookup in a routing table, comprising entries of arbitrary length prefixes with associated next-hop information in a next-hop table, to determine where IP datagrams are to be forwarded, a representation of the routing table is stored, in the form of a complete prefix tree (7), defined by the prefixes of all routing table entries. Further, a representation of a bit vector (8), comprising data of a cut through the prefix tree (7) at a current depth (D), and an array of pointers, comprising indices to the next-hop table and to a next-level chunk, are stored. The bit-vector (8) is divided into bit-masks and a representation of the bit-masks is stored in a maptable. Then, an array of code words, each encoding a row index into the maptable and a pointer offset, and an array of base addresses are stored. Finally, the lookup is performed.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.