Context-switched multi-stream pipelined reorder engine

• US 8,102,858 B1
• Filed: 07/08/2009
• Issued: 01/24/2012
• Est. Priority Date: 09/19/2001
• Status: Active Grant

• Current Assignee: Juniper Networks Incorporated
• Original Assignee: Juniper Networks Incorporated
• Inventors: Rahim, Rami, Talapaneni, Venkateswarlu, Lacroute, Philippe G
• Primary Examiner(s): WILSON, ROBERT W
• Application Number:
  US12/499,543
• Time in Patent Office: 930 Days
• Field of Search: None
• US Class Current: 370/394
• CPC Class Codes: H04L 12/5601 Transfer mode dependent, e.g. ATM
• CPC Class Codes: H04L 2012/565 Sequence integrity
• CPC Class Codes: H04L 2012/5681 Buffer or queue management

Abstract

A pipelined reorder engine reorders data items received over a network on a per-source basis. Context memories correspond to each of the possible sources. The pipeline includes a plurality of pipeline stages that together simultaneously operate on the data items. The context memories are operatively coupled to the pipeline stages and store information relating to a state of reordering for each of the sources. The pipeline stages read from and update the context memories based on the source of the data item being processed.

Claims

1. A reorder engine for reordering a plurality of out-of-order data items, received from a plurality of sources, to correspond to a transmitted order from each of the plurality of sources, the reorder engine comprising:

a plurality of sets of context memories operatively coupled to a plurality of pipelined stages, where one of the plurality of sets of context memories stores state information associated with a state of reordering of data items transmitted by one of the plurality of sources; and

a pipeline that includes the plurality of pipelined stages, the pipeline to;

receive a data item,

determine a particular source, of the plurality of sources, from which the data item was transmitted, based on source identification information obtained from the data item or based on source identification information read from one or more context memories of the plurality of sets of context memories,

identify a particular set of context memories, of the plurality of context memories, based on the determination of the particular source, of the plurality of sources, and

determine a position for the data item, relative to other data items transmitted by the particular source, of the plurality of sources, based on particular state information obtained from at least one context memory of the particular set of context memories, and

order the data item, based on the determined position for the data item, with respect to the other data items transmitted by the particular source of the plurality of sources.

2. The reorder engine of claim 1, where, when determining the particular source from which the particular data item was transmitted, the pipeline is to:

determine that the data item is a new data item based on the source identification information, and

set the particular source as an active source based on the determination that the data item is the new data item.

3. The reorder engine of claim 2, where, when setting the particular source as the active source, the pipeline is to:

mark a particular active source bit, in a work vector associated with the plurality of the sets of context memories, the particular active source bit corresponding to the particular source.

4. The reorder engine of claim 1, where the pipeline is further to:

identify at least one active bit, of a plurality of bits, in a work vector associated with the plurality of sets of context memories, and

determine that another particular source, of the plurality of sources, is an active source, based on the identification of the at least one active bit.

5. The reorder engine of claim 4, where the pipeline is further to:

identify another particular set of context memories, of the plurality of context memories, from which to obtain information to reorder another particular data item based on the determination of the other particular source.

6. The reorder engine of claim 1, where, when determining the position for the particular data item, the pipeline is to:

calculate the position for the particular data item based on a modulo operation of a sequence number, associated with the data item, with a size of a reorder buffer associated with the particular set of context memories.

7. The reorder engine of claim 1, where, when determining the position for the particular cell, the pipeline is to:

determine the position for the particular cell based on information associated with the position read from a pointer associated with a reorder buffer associated with the particular set of context memories.

8. A method performed by a reorder engine, the reorder engine including a plurality of pipelined stages to reorder data items transmitted by a plurality of sources, to correspond to a transmitted order, the method comprising:

receiving, by the reorder engine, sequence information associated with the data items transmitted by the plurality of sources, the sequence information, for each data item, including a different one of a plurality of sequence numbers associated with one of the plurality of sources;

performing, by the reorder engine and using a stage of the plurality of pipelined stages, an arbitration operation on particular sequence information, associated with a particular data item, to determine a particular source, of the plurality of sources, from which the particular data item was transmitted;

computing, by the reordering engine and using another stage of the plurality of pipelined stages, an order for the particular data item relative to other data items transmitted by the particular source, based on a particular sequence number obtained from the particular sequence information; and

storing, by the reorder engine and using a further stage of the plurality of pipelined stages, the particular sequence information in a context memory associated with the particular source based on the order computed for the particular data item.

9. The method of claim 8, where the plurality of pipelined stages are operatively coupled to a plurality of sets of context memories, each of the plurality of sets of context memories corresponds to a different one of the plurality of sources, and a particular set of context memories, of the plurality of sets of context memories, stores information associated with a state of reordering of data items transmitted by the particular source.

10. The method of claim 8, where performing the arbitration operation on the particular sequence information includes:

determining, using the stage of the plurality of pipelined stages, that the particular sequence information is new sequence information based on source identification information obtained from the particular sequence information;

setting the particular source as an active source based on the determination that the particular sequence information is the new sequence information; and

identifying a set of context memories, of a plurality of sets of context memories, from which to obtain information associated with a state of reordering of data items transmitted by the particular source.

11. The method of claim 8, where performing the arbitration operation on the particular sequence information includes:

identifying at least one active bit, of a plurality of bits, in a work vector associated with a plurality of sets of context memories;

identifying another source, of the plurality of sources, as an active source, based on the identification of the at least one active bit; and

identifying a set of context memories, of the plurality of sets of context memories, from which to obtain information associated with a state of reordering of cells transmitted by the other source.

12. The method of claim 11, further comprising:

computing, using the other stage, another order for another particular data item, transmitted by the other source, relative to another one or more data items transmitted by the other source, based on another sequence number obtained from other sequence information associated with the other particular data item; and

storing, using the further stage, the other sequence information in another context memory of the set of context memories.

13. The method of claim 8, where storing the particular sequence information in the context memory includes:

determining an entry, of a plurality of entries associated with the context memory, in which to store the particular sequence information based on the particular sequence number and a size of the context memory; and

storing the particular sequence information in the context memory based on the determination of the entry.

14. The method of claim 13, where determining the entry in which to store the particular sequence information includes:

performing a modulo operation of the particular sequence number with a quantity of the plurality of entries.

15. The method of claim 8, where storing the particular sequence information in the context memory includes:

storing the particular sequence information in a last entry, of a plurality of entries, associated with the context memory.

16. A system for reordering a plurality of out-of-order data items, received from a plurality of sources, to correspond to a transmitted order, the system comprising:

a plurality of sets of context memories associated with the plurality of sources, each of the plurality of sets of context memories storing information associated with a state of reordering of data items transmitted by one of the plurality of sources; and

a reordering pipeline engine, that includes a plurality of sequential stages configured to interact with the plurality of sets of context memories, to;

receive data items from the plurality of sources, each of the received data items including source identification information,

identify a set of context memories, of the plurality of sets of context memories, for a particular data item, of the received data items, based on the source identification information obtained from the particular data item,

reorder one or more of the received data items, using information obtained from the identified set of context memories associated with the one or more of the received data items, and

update address information, in one or more of the plurality of sets of context memories, with other address information associated with the reordered one or more received data items, corresponding to a transmitted order of the one or more received data items.

17. The system of claim 16, where when reordering the one or more of the received data items, the reordering pipeline engine is further to:

calculate an order for the one or more of the received data items based on sequence information obtained from the one or more of the received data items.

18. The system of claim 17, where the reordering engine is further to:

determine the other address information associated with the reordered one or more received data items by performing a modulo operation based on the sequence information obtained from the one or more received data items and a size of the one or more context memories associated with the one or more of the plurality of sets of context memories.

19. The system of claim 16, where the plurality of sources are connected to the reordering pipeline engine via a switch fabric.

20. The system of claim 16, where the plurality of sequential stages include:

at least one arbitration stage that determines an active one of the plurality of sources for which to process one of the received data items, and

an address computation stage that calculates an address for each of the received data items, relative to other received data items, associated with the active one of the plurality of sources, based on a sequence number of the each of the received data items.

21. The system of claim 16, where each of the plurality of sets of context memories includes:

at least one reorder buffer, associated with one of the plurality of sources, to store information associated with one or more of the received data items transmitted by the one of the plurality of sources.

22. The system of claim 16, where each of the plurality of sets of context memories includes:

at least one notification assembly memory configured to store addresses of the received data items in the transmitted order of the data items.