Distributed Packet Processing With Ordered Locks To Maintain Requisite Packet Orderings

• US 20080181229A1
• Filed: 04/03/2008
• Published: 07/31/2008
• Est. Priority Date: 11/12/2003
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Listman, Shimon, Shoham, Doron, Williams, John J., Fingerhut, John Andrew
• Granted Patent: US 7,630,376 B2
• Time in Patent Office: Days
• US Class Current: 370/394
• CPC Class Codes: H04L 45/10 Routing in connection-oriented networks, e.g. X.25 or ATM
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/34 ensuring sequence integrity, e.g. using sequence numbers
• CPC Class Codes: H04L 47/50 Queue scheduling
• CPC Class Codes: H04L 47/624 Altering the ordering of packets in an individual queue
• CPC Class Codes: H04L 49/9094 Arrangements for simultaneous transmit and receive, e.g. simultaneous reading/writing from/to the storage element
• CPC Class Codes: Y10S 707/99938 Concurrency, e.g. lock management in shared database

Abstract

Sequences of items may be maintained using ordered locks. These items may correspond to anything, but using ordered locks to maintain sequences of packets, especially for maintaining requisite packet orderings when distributing packets to be processed to different packet processing engines, may be particularly useful. For example, in response to a particular packet processing engine completing processing of a particular packet, a gather instruction is attached to the particular identifier of a particular ordered lock associated with the particular packet. If no longer needed for further processing, the packet processing engine is immediately released to be able to process another packet or perform another function. The gather instruction is typically performed in response to the particular ordered lock being acquired by the particular identifier, with the gather instruction causing the processed particular packet to be sent.

Claims

1. An apparatus, comprising:

one or more ordered lock managers configured to receive lock requests, to receive instruction requests corresponding to said lock requests, and to perform said received instructions corresponding to said lock requests in the order said lock requests are requested and after an immediately prior lock request in the order said lock requests are received is released;

a plurality of packet processing engines, each of the plurality of packet processing engines configured to process packets distributed to it and to communicate one or more instructions to one or more of said one or more ordered lock managers for each said packet distributed to it; and

a distributor configured to receive packets, make locking requests corresponding to said received packets to said one or more ordered lock managers, and to distribute said received packets to the plurality of packet processing engines.

2. The apparatus of claim 1, wherein said instruction requests include a gather instruction for a processed packet processed by one of the plurality of packet processing engines.

3. The apparatus of claim 2, comprising a gather mechanism configured to prepare and send the processed packet in response to receiving a gather request for the processed packet;

and

wherein a particular ordered lock manager of said one or more ordered lock managers is configured to communicate the gather request for the processed packet to the gather mechanism in response to acquiring a lock identifier associated with the processed packet and processing one or more instructions including the gather instruction.

4. The apparatus of claim 3, wherein a particular packet processing engine of the plurality of packet processing engines is configured to process the processed packet;

and

wherein the particular packet processing engine is configured to cause the gather instruction for the processed packet to be added to a lock of the particular ordered lock manager and be associated with the lock identifier.

5. The apparatus of claim 4, wherein particular packet processing engine is configured to further process the processed packet and to cause the gather mechanism to forward one or more additional packets based on the processed packet.

6. The apparatus of claim 4, wherein the gather mechanism is configured to communicate an acknowledgement to the particular packet processing engine subsequent to the gather mechanism receiving the gather request for the processed packet;

and

wherein the particular packet processing engine is configured to perform additional processing based on the particular packet in response to the acknowledgement.

7. The apparatus of claim 3, wherein said instruction requests include a convert instruction;

and wherein said one or more lock managers are configured to, in response to acquiring a lock identifier associated with a particular packet for a first particular lock and processing one or more instructions including the convert instruction, to convert from the first particular lock to a second particular lock.

8. The apparatus of claim 7, wherein the first particular lock is associated with a stream of packets;

and the second particular lock is associated with an identifiable sub-stream of packets within the stream of packets.

9. The apparatus of claim 8, wherein the particular packet is processed by a particular packet processing engine of the plurality of packet processing engines;

and wherein the particular packet processing engine is configured to cause the convert instruction to be added to the first particular lock and to be associated the lock identifier associated with the particular packet.

10. The apparatus of claim 1, wherein said instruction requests include a convert instruction;

and wherein said one or more lock managers are configured to, in response to acquiring a lock identifier associated with a particular packet for a first particular lock and processing one or more instructions including the convert instruction, to convert from the first particular lock to a second particular lock.

11. The apparatus of claim 10, wherein the first particular lock is associated with a stream of packets;

and the second particular lock is associated with an identifiable sub-stream of packets within the stream of packets.

12. The apparatus of claim 11, wherein the particular packet is processed by a particular packet processing engine of the plurality of packet processing engines;

and wherein the particular packet processing engine is configured to cause the convert instruction to be added to the first particular lock and to be associated the lock identifier associated with the particular packet.

13. A method, comprising:

distributing a plurality of packets of one or more streams of packets to a plurality of packet processing engines while maintaining the original order of the individual streams of one or more streams of packets using one or more ordered locks of one or more ordered locking mechanisms, wherein each of said ordered locks is configured for queuing a plurality of identifiers corresponding to its locking requests in the order of receipt of its said locking requests, and to associate instructions with said identifiers;

for each particular packet of the plurality of packets;

in response to completing processing of the particular packet, attaching a gather instruction to an identifier of said identifiers, wherein the identifier corresponds to said particular packet; and

for each particular gather instruction of said gather instructions;

performing the particular gather instruction in response to a particular ordered lock of said ordered locks being acquired by the particular identifier, wherein said performance of the gather instruction causes a processed packet of the plurality of packets to be sent with the same original order of the individual streams of one or more streams of packets being maintained.

14. The method of claim 13, wherein said performing the gather instruction includes communicating a gather request to a gather mechanism;

wherein the gather mechanism prepares and sends the processed particular packet.

15. The method of claim 13, comprising performing a root lock on each of the plurality of packets to maintain the order of the stream of the plurality of packets.

16. The method of claim 15, comprising:

for each specific packet of the plurality of packets;

performing a classification operation on said specific packet to determine a secondary lock corresponding to an individual stream of a plurality of individual streams within the stream of the plurality of packets, and performing a convert operation from the root lock to said determined secondary lock.

17. An apparatus, comprising:

means for distributing a plurality of packets of one or more streams of packets to a plurality of packet processing engines while maintaining the original order of the individual streams of one or more streams of packets using one or more ordered locks of one or more ordered locking mechanisms, wherein each of said ordered locks is configured for queuing a plurality of identifiers corresponding to its locking requests in the order of receipt of its said locking requests, and to associate instructions with said identifiers;

means for, for each particular packet of the plurality of packets;

in response to completing processing of the particular packet, attaching a gather instruction to an identifier of said identifiers, wherein the identifier corresponds to said particular packet; and

means for, for each particular gather instruction of said gather instructions;

performing the particular gather instruction in response to a particular ordered lock of said ordered locks being acquired by the particular identifier, wherein said performance of the gather instruction causes a processed packet of the plurality of packets to be sent with the same original order of the individual streams of one or more streams of packets being maintained.

18. The apparatus of claim 17, wherein said performing the gather instruction includes communicating a gather request to means for preparing and sending the processed particular packet.

19. The apparatus of claim 17, comprising means for performing a root lock on each of the plurality of packets to maintain the order of the stream of the plurality of packets.

20. The apparatus of claim 19, comprising:

means for, for each specific packet of the plurality of packets;

performing a classification operation on said specific packet to determine a secondary lock corresponding to an individual stream of a plurality of individual streams within the stream of the plurality of packets; and

means for performing a convert operation from the root lock to said determined secondary lock.