Patent ID: 8625604

Claim:
A computer-implemented method for Internet Protocol (IP) network lookup in a forwarding device, the forwarding device including an internal processor memory storing a first next hop information table and membership query information, and an external processor memory storing a plurality of prefix-compressed trees and a second next hop information table, the method comprising: a) receiving, by the forwarding device, an IP network address of a destination device, as input, to determine next hop information indicating a network address of a next hop device to which a data packet is to be sent on the way to the data packet's final destination; b) determining, by the forwarding device, a first set of next hop information using the received IP network address by performing a direct memory lookup of a first next hop information table stored in the internal processing memory of the forwarding device; c) determining, by the forwarding device, a location of a prefix-compressed trie, stored in external processor memory, using the received network address by performing a query of membership query information stored in internal processor memory; d) searching, by the forwarding device, the prefix-compressed trie at the determined location using the received IP network address, to determine a location and an offset within a second next hop information table, stored in external processor memory, which stores the desired next hop information; e) determining, by the forwarding device, a second set of next hop information using (1) the determined location and (2) the offset within the second next hop information table; f) determining, by the forwarding device, which of the first set of next hop information and the second set of next hop information has a longest match of the received IP network address; and g) selecting, by the forwarding device, the set of next hop information that has the longest match of the received IP network address.