Patent ID: 7369557

Claim:
A method for forwarding packets in a flow to an assigned processor in a multi-processor system, where each packet includes tuples indicating the source, destination, and other attributes of the packet and with a particular flow identified by a set of tuples having a specific value, said method comprising the steps of: associating a flow control probabilistic data structure with each processor in the multi-processor system, with each flow control probabilistic data structure having a bit-vector of m bits with each bit identified by an index value, where m is an integer greater than zero; applying k hash functions, where k is an integer greater than zero, to selected tuples of a received packet, to generate k values; indicating a hit of a bit vector in a particular flow control probabilistic data structure if the bit values of the bit vector at k indices equal to the k values are asserted; and directing the packet to a first processor associated with a flow control probabilistic data structure indicating a hit if only a single hit occurs or looking up the tuples of the received packet in a collision flow table if multiple hits occur, with the collision flow table storing tuples of flows that hit multiple flow control probabilistic data structures and indicating a processor assigned to flows stored in the collision flow table.