Distributed packet processing with ordered locks to maintain requisite packet orderings

• US 20050220112A1
• Filed: 07/16/2004
• Published: 10/06/2005
• 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: Shoham, Doron, Williams, John J. Jr., Fingerhut, John Andrew, Listman, Shimon
• Granted Patent: US 7,362,762 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 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. A method for processing packets, the method comprising:

distributing a plurality of packets to a plurality of packet processing engines while maintaining order of one or more streams of packets using one or more ordered locks, said distributing including distributing a particular packet of the plurality of packets to a particular packet processing engine of the plurality of packet processing engines with the particular packet being associated with a particular identifier of a particular ordered lock of said one or more ordered locks;

in response to the particular packet processing engine completing processing of the particular packet, attaching a gather instruction to the particular identifier and releasing the packet processing engine to be able to process another packet or perform another function; and

performing the gather instruction in response to the particular ordered lock being acquired by the particular identifier, said gather instruction causing the processed particular packet to be sent;

wherein said releasing the packet processing engine is performed prior to said performing the gather instruction.

2. The method of claim 1, 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.

3. A method for processing packets, the method comprising:

receiving a particular packet of a stream of packets;

storing the packet in a packet data storage and allocating a packet handle data structure identifying the packet in the packet data storage;

associating the particular packet with a particular identifier of a particular ordered lock of one or more ordered locks;

distributing the particular packet to a particular packet processing engine of a plurality of packet processing engines;

in response to the particular packet processing engine completing processing of the particular packet, attaching a gather instruction to the particular identifier and releasing the packet processing engine to be able to process another packet or perform another function; and

performing the gather instruction in response to the particular ordered lock being acquired by the particular identifier, said gather instruction including communicating a gather request to a gather mechanism, wherein the gather mechanism prepares and sends the processed particular packet; and

receiving by the gather mechanism a copy of the packet handle data structure, and releasing the packet handle data structure after the gather mechanism receives the copy of the packet handle data structure;

wherein said releasing the packet processing engine is performed prior to said performing the gather instruction, and said releasing the packet handle data structure is performed prior to the sending of the processed packet.

4. The method of claim 3, wherein the particular packet is associated with a sub-stream of the stream of packets, and the method includes converting the particular identifier from a lock of said one or more ordered locks associated with the stream of packets to the particular ordered lock, wherein the particular ordered lock is associated with the sub-stream.

5. A method for processing packets, the method comprising:

receiving a particular packet of a stream of packets;

storing the packet in a packet data storage and allocating a packet handle data structure identifying the packet in the packet data storage, the packet handle data structure;

associating the particular packet with a particular identifier of a particular ordered lock of one or more ordered locks;

distributing the particular packet to a particular packet processing engine of a plurality of packet processing engines;

in response to the particular packet processing engine completing processing of the particular packet, attaching a gather instruction to the particular identifier; and

performing the gather instruction in response to the particular ordered lock being acquired by the particular identifier, said gather instruction including communicating a gather request to a gather mechanism, wherein the gather mechanism prepares and sends the processed particular packet;

receiving by the gather mechanism a copy of the packet handle data structure; and

reusing the packet handle data structure after the gather mechanism receives the copy of the packet handle data structure by the particular packet processing engine to perform further processing in response to said processing of the particular packet;

wherein said reusing the packet handle data structure is commenced prior to the sending of the processed packet.

6. The method of claim 5, wherein the particular packet is associated with a sub-stream of the stream of packets, and the method includes converting the particular identifier from a lock of said one or more ordered locks associated with the stream of packets to the particular ordered lock, wherein the particular ordered lock is associated the sub-stream.

7. The method of claim 5, wherein said further processing includes generating and sending a new packet.

8. A method for processing packets, the method comprising:

receiving a particular packet of a stream of packets;

associating the particular packet with a particular identifier of a particular ordered lock of one or more ordered locks;

distributing the particular packet to a particular packet processing engine of a plurality of packet processing engines;

in response to the particular packet processing engine completing processing of the particular packet, attaching a gather instruction to the particular identifier; and

performing the gather instruction in response to the particular ordered lock being acquired by the particular identifier, said gather instruction including communicating a gather request to a gather mechanism, wherein the gather mechanism prepares and sends the processed particular packet and then notifies the particular packet processing engine; and

further processing of the particular packet by the particular packet processing engine in response to said notification.

9. The method of claim 8, wherein the particular packet is associated with a sub-stream of the stream of packets, and the method includes converting the particular identifier from a lock of said one or more ordered locks associated with the stream of packets to the particular ordered lock, wherein the particular ordered lock is associated with the sub-stream.

10. The method of claim 8, wherein said further processing includes sending information contained in the particular packet to a different destination than that specified in the particular packet.

11. An apparatus for processing packets, the apparatus comprising:

a plurality of packet processing engines;

an ordered lock manager configured to receive lock requests, to receive instruction requests corresponding to said lock requests, and to process instructions corresponding to said lock requests in the order said lock requests are received and after an immediately prior lock request in the order said lock requests are received is released; and

a distributor, coupled to the plurality of packet processing engines and the ordered lock manager, configured to receive a packet, make a locking request corresponding to the packet to the ordered lock manager, and to distribute the packet to a particular processing engine of the plurality of packet processing engines;

wherein the particular processing engine is configured to communicate one or more instructions corresponding to the packet to the ordered lock manager after completing processing of the packet, and after said communication of said one or more instructions, the particular packet processing engine is released so that it can process another packet.

12. The apparatus of claim 11, wherein the ordered lock manager is configured to notify the distributor in response to receiving the set of instructions, and the distributor is configured to release the packet processing engine in response to said notification.

13. The apparatus of claim 11, wherein said one or more instructions includes a gather instruction for the packet.

14. The apparatus of claim 13, comprising a gather mechanism, wherein the ordered lock manager is configured to communicate a gather request for the packet to the gather mechanism in response to acquiring a lock identifier associated with the packet, with said one or more instructions being associated with the lock identifier.

15. An apparatus for processing packets, the apparatus comprising:

a plurality of packet processing engines;

an ordered lock manager configured to receive lock requests, to receive instruction requests corresponding to said lock requests, and to process instructions corresponding to said lock requests in the order said lock requests are received and after an immediately prior lock request in the order said lock requests are received is released; and

a distributor, coupled to the plurality of packet processing engines and the ordered lock manager, configured to receive a packet, make a locking request corresponding to the packet to the ordered lock manager, and to distribute the packet to a particular processing engine of the plurality of packet processing engines, wherein the particular processing engine is configured to communicate one or more instructions corresponding to the packet to the ordered lock manager after completing processing of the packet, wherein said one or more instructions includes a gather instruction for the packet; and

a gather mechanism, wherein the ordered lock manager is configured to communicate a gather request for the packet to the gather mechanism in response to acquiring a lock identifier associated with the packet, with said one or more instructions being associated with the lock identifier, wherein the gather mechanism prepares and sends the processed particular packet and then notifies the particular packet processing engine;

and wherein the particular packet processing engine is configured to further process the packet in response to receiving said notification.

16. The apparatus of claim 15, wherein said further processing includes sending information contained in the packet to a different destination than that specified in the packet.

17. An apparatus for processing packets, the apparatus comprising:

means for distributing a plurality of packets to a plurality of packet processing engines while maintaining order of one or more streams of packets using one or more ordered locks, said means for distributing including means for distributing a particular packet of the plurality of packets to a particular packet processing engine of the plurality of packet processing engines with the particular packet being associated with a particular identifier of a particular ordered lock of said one or more ordered locks;

means for attaching a gather instruction to the particular identifier and releasing the packet processing engine to be able to process another packet or perform another function in response to the particular packet processing engine completing processing of the particular packet; and

means for performing the gather instruction in response to the particular ordered lock being acquired by the particular identifier, said gather instruction causing the processed particular packet to be sent;

wherein said releasing the packet processing engine is performed prior to said performing the gather instruction.

18. The apparatus of claim 17, wherein the particular packet is associated with a sub-stream of the stream of packets, and the apparatus includes means for converting the particular identifier from a lock of said one or more ordered locks associated with the stream of packets to the particular ordered lock, wherein the particular ordered lock is associated with the sub-stream.

19. An apparatus for processing packets, the apparatus comprising:

means for receiving a particular packet of a stream of packets;

means for storing the packet in a packet data storage and allocating a packet handle data structure identifying the packet in the packet data storage;

means for associating the particular packet with a particular identifier of a particular ordered lock of one or more ordered locks;

means for distributing the particular packet to a particular packet processing engine of a plurality of packet processing engines;

means for attaching a gather instruction to the particular identifier and releasing the packet processing engine to be able to process another packet or perform another function, in response to the particular packet processing engine completing processing of the particular packet; and

means for performing the gather instruction in response to the particular ordered lock being acquired by the particular identifier, said gather instruction including communicating a gather request to a gather mechanism, wherein the gather mechanism prepares and sends the processed particular packet; and

means for receiving by the gather mechanism a copy of the packet handle data structure, and releasing the packet handle data structure after the gather mechanism receives the copy of the packet handle data structure;

wherein said releasing the packet processing engine is performed prior to said performing the gather instruction, and said releasing the packet handle data structure is performed prior to the sending of the processed packet.

20. A apparatus for processing packets, the apparatus comprising:

means for receiving a particular packet of a stream of packets;

means for associating the particular packet with a particular identifier of a particular ordered lock of one or more ordered locks;

means for distributing the particular packet to a particular packet processing engine of a plurality of packet processing engines;

means for attaching a gather instruction to the particular identifier in response to the particular packet processing engine completing processing of the particular packet; and

means for performing the gather instruction in response to the particular ordered lock being acquired by the particular identifier, said gather instruction including communicating a gather request to a gather mechanism, wherein the gather mechanism prepares and sends the processed particular packet and then notifies the particular packet processing engine; and

further processing of the particular packet by the particular packet processing engine in response to said notification.

21. The apparatus of claim 20, wherein the particular packet is associated with a sub-stream of the stream of packets, and the apparatus includes means for converting the particular identifier from a lock of said one or more ordered locks associated with the stream of packets to the particular ordered lock, wherein the particular ordered lock is associated with the sub-stream.

22. The apparatus of claim 20, wherein said further processing includes sending information contained in the particular packet to a different destination than that specified in the particular packet.