Patent ID: 8886827

Claim:
A method comprising: receiving, with a network device, a packet of a packet flow, wherein the packet flow is one of a plurality of packet flows processed by the network device; processing, with a filter block of the network device, a lookup key associated with the packet to determine whether a prefix associated with the lookup key is stored in a hash table of the filter block, wherein processing the lookup key comprises: processing, with a Bloom filter of the network device, at least one prefix associated with the lookup key to identify one or more prefixes to use in searching the hash table, wherein the Bloom filter stores indications of whether various prefixes associated with the plurality of packet flows processed by the network device are stored in the hash table; and searching the hash table using at least one of the identified one or more prefixes, wherein the hash table stores a plurality of key value and prefix pairs for at least a first portion of the plurality of packet flows processed by the network device; and responsive to determining, with the network device, that a duration required to process the lookup key is greater than a threshold duration, storing information about the packet flow in a flow cache of the filter block, wherein the flow cache stores information about a second portion of the plurality of packet flows processed by the network device.