Maintaining packet order using hash-based linked-list queues

US7764606B1 · kind B1 · utility

Assignee

• Juniper Networks, Inc. · US

Inventors

• Dennis C. Ferguson · Palo Alto, US
• Philippe Lacroute · Sunnyvale, US
• Chi-Chung Chen · Hengshan, TW
• Gerald Cheung · Sunnyvale, US
• Tatao Chuang · San Jose, US
• Pankaj Patel · Cupertino, US
• Viswesh Ananthakrishnan · Sunnyvale, US

Key dates

• Filing date: May 30, 2007
• Grant date: Jul 27, 2010
• Expiry date: Aug 5, 2028

Classification

• Technology area (CPC H): Electricity
• CPC primary: H04L49/351
• WIPO field: Digital communication
• WIPO sector: Electrical engineering

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.