Method and apparatus for performing an address lookup using a multi-bit trie with backtracking
US7339930B2 · kind B2 · utility
Assignee
Inventor
Key dates
| Filing date | Nov 22, 2002 |
| Grant date | Mar 4, 2008 |
| Priority date | — |
| Expiry date | Dec 1, 2025 |
Classification
- Technology area (CPC H)Electricity
- CPC primaryH04L45/74591
- WIPO fieldDigital communication
- WIPO sectorElectrical engineering
Abstract
One embodiment of the present invention provides a system that facilitates performing a fast address lookup within a packet forwarder to determine where to forward a packet. Upon receiving the packet at an input link of the packet forwarder, the system reads a destination address from the packet. The system uses this destination address to lookup a corresponding entry in a forwarding table that is organized as a multi-bit trie. If the corresponding entry does not identify the output link for the packet, the system backtracks through the multi-bit trie to locate an entry with a prefix that matches the destination address and that identifies the output link for the packet. Finally, the system forwards the packet to the identified output link.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.