Method and apparatus for performing an address lookup using a multi-bit trie with backtracking

1. A method for performing a fast address lookup within a packet forwarder to determine where to forward a packet, comprising:

receiving the packet at an input link of the packet forwarder;

reading a destination address from the packet;

using the destination address to lookup a corresponding entry in a forwarding table, wherein the forwarding table is organized as a multi-bit trie;

examining the corresponding entry in the forwarding table to identify an output link for the packet;

if the corresponding entry does not identify the output link for the packet, backtracking 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, wherein backtracking through the multi-bit trie involves scanning backwards through multiple consecutive entries within a current node in the multi-bit trie looking for an entry with a prefix that matches the destination address and that identifies the output link for the packet, and wherein the multiple consecutive entries have the prefix that matches the destination address; and

forwarding the packet to the identified output link.

2. The method of claim 1 , further comprising:

receiving a request to delete an entry for a prefix from the forwarding table;

using the prefix to lookup the entry for the prefix in the forwarding table, wherein the entry identifies an output link associated with the prefix; and

deleting the entry from the forwarding table, wherein deleting the entry involves deleting one or more nodes in the multi-bit trie, if necessary.

3. The method of claim 1 , further comprising:

receiving a request to insert an entry for a prefix into the forwarding table; and

inserting the entry into the forwarding table;

wherein inserting the entry involves creating one or more nodes in the multi-bit trie, if necessary, to accommodate the entry; and

wherein inserting the entry involves inserting information into the entry that identifies an output link associated with the prefix.

4. The method of claim 1 , wherein if a matching entry is not found in the current node, backtracking through the multi-bit trie involves recursively repeating the scanning process for preceding nodes in the multi-bit trie until a matching entry is found.

5. The method of claim 1 , wherein the destination address is an Internet Protocol (IP) address.

6. The method of claim 1 , wherein the output link for the packet is identified by an entry in the forwarding table.

7. The method of claim 1 , wherein each node in the multi-bit trie includes 2 n entries for each of the 2 n possible combinations of a p corresponding n-bit portion of the destination address.

8. An apparatus performs a fast address lookup within a packet forwarder to determine where to forward a packet, comprising:

the packet forwarder;

an input link of the packet forwarder configured to receive the packet;

an address lookup mechanism configured to,

read a destination address from the packet,

use the destination address to lookup a corresponding entry in a forwarding table, wherein the forwarding table is organized as a multi-bit trie,

examine the corresponding entry in the forwarding table to identify an output link for the packet, and

if the corresponding entry does not identify the output link for the packet, to backtrack through the multi-bit the to locate an entry with a prefix that matches the destination address and that identifies the output link for the packet, wherein while backtracking through the multi-bit trie, the address lookup mechanism is configured to scan backwards through multiple consecutive entries within a current node in the multi-bit trie looking for an entry with a prefix that matches the destination address and that identifies the output link for the packet, and wherein the multiple consecutive entries have the prefix that matches the destination address; and

a forwarding mechanism configured to forward the packet to the identified output link.

9. The apparatus of claim 8 , further comprising a deletion mechanism, wherein upon receiving a request to delete an entry for a prefix from the forwarding table, the deletion mechanism is configured to:

use the prefix to lookup the entry for the prefix in the forwarding table, wherein the entry identifies an output link associated with the prefix; and to

delete the entry from the forwarding table, wherein deleting the entry involves deleting one or more nodes in the multi-bit trie, if necessary.

10. The apparatus of claim 8 , further comprising an insertion mechanism, wherein upon receiving a request to insert an entry for a prefix into the forwarding table, the insertion mechanism is configured to:

insert the entry into the forwarding table;

wherein inserting the entry involves creating one or more nodes in the multi-bit trie, if necessary, to accommodate the entry; and

wherein inserting the entry involves inserting information into the entry that identifies an output link associated with the prefix.

11. The apparatus of claim 8 , wherein while backtracking through the multi-bit the, if a matching entry is not found in the current node, the address lookup mechanism is configured to recursively repeat the scanning process for preceding nodes in the multi-bit trie until a matching entry is found.

12. The apparatus of claim 8 , wherein the destination address is an Internet Protocol (IP) address.

13. The apparatus of claim 8 , wherein the output link for the packet is identified by an entry in the forwarding table.

14. The apparatus of claim 8 , wherein each node in the multi-bit trie includes 2 n entries for each of the 2 n possible combinations of a corresponding n-bit portion of the destination address.