System and method of fast adaptive TCAM sorting for IP longest prefix matching
US7706375B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Feb 6, 2007 |
| Grant date | Apr 27, 2010 |
| Priority date | — |
| Expiry date | Aug 4, 2028 |
Classification
- Technology area (CPC H)Electricity
- CPC primaryH04L45/74591
- WIPO fieldDigital communication
- WIPO sectorElectrical engineering
Abstract
A system and method are provided for sorting IP routing table entries in a TCAM for longest IP prefix matching LPM of destination IP addresses. The IP routing table is divided into logical blocks, for each block an associated routing entry IP prefix length. Each block is of a respective size whose proportion of the total size of the routing table is determined by the associated IP prefix length. The blocks are ordered so that the TCAM returns an LPM when queried. Starting block sizes can be initialized to proportions which reflect actual expected numbers by proportion of routing entries by IP prefix length. The blocks also grow and shrink as entries are added and deleted so as to more closely mirror real-world populations of expected entries having the IP prefix length in question.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.