Systems and methods for preserving the order of data

• US 8,397,233 B2
• Filed: 05/23/2007
• Issued: 03/12/2013
• Est. Priority Date: 10/02/2001
• Status: Active Grant

• Current Assignee: Juniper Networks Incorporated
• Original Assignee: Juniper Networks Incorporated
• Inventors: Lim, Raymond Marcelino Manese, Dyckerhoff, Stefan, Libby, Jeffrey Glenn, Tesfaye, Teshager
• Primary Examiner(s): TO, JENNIFER N
• Application Number:
  US11/752,620
• Publication Number:
  US 20070220189A1
• Time in Patent Office: 2,120 Days
• Field of Search: 718/100
• US Class Current: 718/100
• CPC Class Codes: G06F 12/00 Accessing, addressing or allocating within memory systems or architectures digital input from, or digital output to record carriers, e.g. to disk storage units, G06F3/06
• CPC Class Codes: G06F 13/1626 by reordering requests
• CPC Class Codes: G06F 13/1663 Access to shared memory
• CPC Class Codes: G06F 13/4022 using switching circuits, e.g. switching matrix, connection or expansion network G06F13/4009 takes precedence
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues
• CPC Class Codes: H04L 45/62 Wavelength based optical switching H04Q11/0062
• CPC Class Codes: H04L 49/90 Buffering arrangements
• CPC Class Codes: H04L 49/9094 Arrangements for simultaneous transmit and receive, e.g. simultaneous reading/writing from/to the storage element

Abstract

A device includes an input processing unit and an output processing unit. The input processing unit dispatches first data to one of a group of processing engines, records an identity of the one processing engine in a location in a first memory, reserves one or more corresponding locations in a second memory, causes the first data to be processed by the one processing engine, and stores the processed first data in one of the locations in the second memory. The output processing unit receives second data, assigns an entry address corresponding to a location in an output memory to the second data, transfers the second data and the entry address to one of a group of second processing engines, causes the second data to be processed by the second processing engine, and stores the processed second data to the location in the output memory.

Claims

1. A method comprising:

outputting data to one processor of a plurality of processors;

recording an identity of the one processor in a first location in a first memory, the first memory including a list of processors, identities of the processors, in the list of processors, being ordered based on an order in which the processors receive data;

reserving, based on the first location, a second location for the data in a second memory;

processing the data by the one processor;

receiving requests from multiple processors, of the plurality of processors, to store processed data, the requests including a request, from the one processor, to store the data processed by the one processor;

granting the request from the one processor based on an order of identities of the multiple processors in the list of processors; and

storing the data processed by the one processor in the second location.

2. The method of claim 1, where the outputting includes:

outputting the data in a first-in, first-out manner.

3. A system comprising:

a first processor to output data;

a plurality of second processors to;

receive the data from the first processor,

process the data, each second processor being associated with an identity, and

send a request to a third processor, after processing the data, to store the processed data in a second memory;

a first memory;

the second memory; and

the third processor to;

record, for each received data and at a location in the first memory, an identity of a second processor, of the plurality of second processors, at which the data is received, the first memory including a list of identities of the second processors ordered based on when data is received at each second processor,

reserve, for data received at the second processor, a corresponding location in the second memory for storing the processed data, the location in the second memory corresponding to a location in the first memory where the identity of the second processor is stored,

receive, from two or more second processors of the plurality of second processors, requests to store processed data, and

grant the requests to store the processed data based on an order in which identities of the two or more second processors are stored in the list of identities.

4. The system of claim 3, where the first processor is further to:

identify an available second processor, and

output data and an identity of the available second processor to the available third processor.

5. The system of claim 4, further comprising:

a bus to interconnect the first processor and the plurality of second processors, and

where the third processor is to;

obtain, from the bus, the identity of the available second processor.

6. A method comprising:

receiving a plurality of packets;

outputting a first packet, of the plurality of packets, to a first processor;

recording an identity of the first processor in a first location in a memory;

reserving a second location for the first packet in the memory, the second location being based on the first location;

outputting a second packet, of the plurality of packets, to a second processor;

recording an identity of the second processor in a third location in the memory, the identity of the second processor being ordered after the identity of the first processor in a list of identities of processors stored in the memory;

reserving a fourth location for the second packet in the memory, the fourth location being based on the third location;

processing the first and second packets by the first and second processors;

receiving, from multiple processors, requests to store processed packets, the requests including a request from the first processor to store the processed first packet and a request from the second processor to store the processed second packet;

storing, based on the request from the first processor, the processed first packet in the second location; and

storing, based on the request from the second processor, the processed second packet in the fourth location.

7. The method of claim 6, where outputting the first packet and outputting the second packet include:

outputting the first and second packets in a first-in, first-out manner.

8. The method of claim 6, where processing the first and second packets includes processing headers of the first and second packets.

9. The method of claim 6, where processing the first and second packets includes processing the first and second packets in parallel.

10. The method of claim 6, where receiving a plurality of packets includes receiving the plurality of packets via a stream of a plurality of streams.

11. The method of claim 6, where receiving the plurality of packets includes storing the received plurality of packets in an input queue.

12. The method of claim 6, where outputting the first packet to the first processor includes:

receiving a ready signal from the first processor, and

outputting the first packet to the first processor after receiving the ready signal.