Longest prefix match search technique
US7764687B1 · kind B1 · utility
Assignee
Inventors
Key dates
| Filing date | Mar 28, 2003 |
| Grant date | Jul 27, 2010 |
| Priority date | — |
| Expiry date | Dec 28, 2026 |
Classification
- Technology area (CPC H)Electricity
- CPC primaryH04L45/74591
- WIPO fieldDigital communication
- WIPO sectorElectrical engineering
Abstract
A router identifies in a data packet an address of a network device. An algorithm determines that the address and a first prefix in a tree data structure match up to a first mask length of the first prefix. The algorithm maintains the first prefix in a temporary storage location if there is a match, and determines whether the address and a second prefix in the tree data structure match up to a second mask length of the second prefix, wherein an external node of the second prefix is linked below an external node of the first prefix, and wherein the second mask length is longer than the first mask length. The algorithm maintains the second prefix as a better match of the address, if the address and the second prefix match up to the mask length of the second prefix.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.