Routing table lookup implemented using M-trie having nodes duplicated in multiple memory banks
US6308219A · kind A · utility
Assignee
Inventor
Key dates
| Filing date | Jul 31, 1998 |
| Grant date | Oct 23, 2001 |
| Priority date | — |
| Expiry date | Jul 31, 2018 |
Classification
- Technology area (CPC H)Electricity
- CPC primaryH04L45/742
- WIPO fieldDigital communication
- WIPO sectorElectrical engineering
Abstract
The invention provides a method and system for rapid access to one or more M-tries for responding to header information. The M-tries are stored in a plurality of memory banks, which are accessed in parallel to provide relatively greater access throughput. Parts of the M-tries that are (or are expected to be) frequently referenced are stored in multiple banks of the memory, to provide concurrent simultaneous access for those parts of the M-tries for parallel lookup of multiple routes. Regions of the multiple banks of the memory can be dynamically reallocated to provide improved access through-put to those multiple banks. The invention can be applied to routing decisions in response to destination addresses, to combinations of destination and source addresses (either for unicast or multicast routing), to access control decisions, to quality of service decisions, to accounting, and to other administrative processing in response to header information.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.