Method and apparatus for longest matching prefix determination in a communication network
US6697363B1 · kind B1 · utility
Assignee
Inventor
Key dates
| Filing date | Jun 28, 2000 |
| Grant date | Feb 24, 2004 |
| Priority date | — |
| Expiry date | Jun 9, 2022 |
Classification
- Technology area (CPC H)Electricity
- CPC primaryH04L69/22
- WIPO fieldDigital communication
- WIPO sectorElectrical engineering
Abstract
A method and apparatus for compressing the data associated with trie cuts (strides), and a method and apparatus for utilizing such compressed data to determine forwarding decisions for data packets in a communication network are presented. The compression technique presented generates a pair of bitmaps and a pair of base pointers for each set of compressed data. The bitmaps are compared with a portion of the address to ascertain whether the forwarding decision is determined within this portion of the trie. Forwarding decisions are stored in a leaf table that is accessed via a leaf table index. The leaf table index is generated by combining a leaf table offset generated from at least one of the bitmaps with a leaf table base pointer included in the stride block. Thus, if the forwarding decision is determined within the stride, the leaf table will be accessed via the leaf table index to retrieve the forwarding decision. If the forwarding decision is not completely determined within the stride, a branch table is used to determine the location of the subsequent stride to be processed. The branch table is accessed via a branch table index generated by combining the branch table base poi…
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.