US 2010/0246584 A1 · MAINTAINING PACKET ORDER USING HASH-BASED LINKED-LIST QUEUES

Abstract

Ordering logic ensures that data items being processed by a number of parallel processing units are unloaded from the processing units in the original per-flow order that the data items were loaded into the parallel processing units. The ordering logic includes a pointer memory, a tail vector, and a head vector. Through these three elements, the ordering logic keeps track of a number of “virtual queues” corresponding to the data flows. A round robin arbiter unloads data items from the processing units only when a data item is at the head of its virtual queue.

Claims2

Dependent claims

A method of tracking an order of data units in a plurality of data flows, the method comprising:

generating hash values based on the data units, each hash value identifying the data flow to which the particular data unit belongs;
comparing one of the generated hash values to previously generated hash values to generate a comparison indicator;
updating a tail vector that identifies a last one of the data units currently being processed for a data flow based on the comparison indicator indicating a first condition;
and
updating the tail vector and a head vector that identifies a beginning of the data flow based on the comparison indicator indicating a second condition.

2 more elements

Dependencies are inferred from the claim text.

Facts

Application

12/815,906Filed 15 Jun 2010

Priority

14 Jun 2002

Published

30 Sep 2010

Term ends

Not estimatedThe source records don’t support an estimate.

Classification8 codes

H04L 49/90
Packet switching elements: buffering arrangements
H04L 47/50
Traffic control in data switching networks: queue scheduling
H04L 47/6225
Queue service order: fixed service order, e.g. Round Robin
H04L 49/901
Buffering arrangements: using storage descriptor, e.g. read or write pointers

Family

Application60/388,361Us provisional application · filed 14 Jun 2002

Application10/193,212Division · filed 12 Jul 2002

Application11/755,292Continuation · filed 30 May 2007

Application12/815,906Continuation

Application11/755,292Division

US 7,243,184 B1Related patent

US 7,764,606 B1Related patent

US 8,059,543 B2Related patent

US 2010/0246584 A1This patent

From the US filing history. Foreign family members aren’t listed.

Maintaining packet order using hash-based linked-list queues

Life of this patent

Maintaining packet order using hash-based linked-list queues

Life of this patent

Abstract

Claims2