Patent ID: 7339930

Claim:
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.