Cooperative Flow Locks Distributed Among Multiple Components

• US 20090296580A1
• Filed: 05/30/2008
• Published: 12/03/2009
• Est. Priority Date: 05/30/2008
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Chesters, Eric John, Williams, John J. Jr.
• Granted Patent: US 8,139,488 B2
• Time in Patent Office: Days
• US Class Current: 370/235
• CPC Class Codes: H04L 47/34 ensuring sequence integrity, e.g. using sequence numbers
• CPC Class Codes: H04L 49/90 Buffering arrangements

Abstract

Disclosed are, inter alia, methods, apparatus, computer-storage media, mechanisms, and means associated with cooperative flow locks distributed among multiple components, such as on different application-specific integrated circuits in a packet switching device. Flow locks are typically used for maintaining the order of packets and operations performed thereon by the coordination of a context (e.g., the processing of a packet by a packet processor) with a corresponding flow lock interface, and by the manner of communication performed among the flow lock interface and the distributed flow locks.

Claims

1. An apparatus, comprising:

a plurality of components, each of the plurality of components being configured to maintain a plurality of flow locks;

wherein each particular flow lock of the plurality of flow locks is associated with a queue for maintaining an ordering of packet identifiers associated with the particular flow lock; and

wherein each particular flow lock of the plurality of flow locks is configured to perform one or more operations from a plurality of operations corresponding to a particular packet identifier corresponding to a particular packet when the particular packet identifier acquires the flow lock;

wherein the plurality of operations includes selectively converting from one particular flow lock of said flow locks on one component of the plurality of components to a second particular flow lock of said flow locks on a different component of the plurality of components;

wherein said converting from said one particular flow lock to the second particular flow lock includes adding a packet identifier corresponding to the particular packet to the second particular flow lock and releasing said one particular flow lock.

2. The apparatus of claim 1, wherein each of said flow locks has associated with it a command queue configured to store one or more commands;

wherein each of the plurality of components includes a flow lock interface configured for communicating commands to be stored in said command queues in each of the plurality of components.

3. The apparatus of claim 2, wherein each of the plurality of components includes one or more packet processors;

wherein each packet processor of said packet processors is configured to communicate with the flow lock interface on said component on which the said packet processor resides for communicating said commands associated with packets being processed by said packet processor to said command queues in each of the plurality of components.

4. The apparatus of claim 3, wherein each flow lock interface of the plurality of flow lock interfaces includes one or more data structures stored in one or more computer-readable media for maintaining information related to flow locks of packets being processed on the component on which said flow lock interface resides;

wherein said information includes an indication of a location of the current flow lock for each packet being processed on the component.

5. The apparatus of claim 4, wherein each flow lock interface of the plurality of flow lock interfaces is configured to store a plurality of commands related to flow locks of packets being processed on the component on which said flow lock interface resides.

6. The apparatus of claim 5, wherein said command queue of each of said flow locks is configured to store at most a single command.

7. The apparatus of claim 3, wherein each of said plurality of components is an application-specific integrated circuit (ASIC).

8. The apparatus of claim 2, wherein each flow lock interface of the plurality of flow lock interfaces is configured to store a plurality of commands related to flow locks of packets being processed on the component on which said flow lock interface resides.

9. The apparatus of claim 8, wherein said command queue of each of said flow locks is configured to store at most a single command.

10. The apparatus of claim 1, wherein each of said plurality of components is an application-specific integrated circuit (ASIC).

11. A method, comprising:

a particular flow lock interface, on a component of a plurality of components of a packet switching device, adding a packet identifier corresponding to a particular packet to the end of queue of a flow lock on a first component of the plurality of components;

in response to the packet identifier associated with a convert operation request acquiring the flow lock, performing the convert operation to a second flow lock on a second component, which is not the first component, of the plurality of components; and

in response to said performance of the convert operation, the second component communicating an acknowledgement message indentifying to the particular flow lock interface that the current location of a flow lock associated with the particular packet is the second flow lock.

12. The method of claim 11, comprising:

in response to receiving the acknowledgement message, the particular flow lock interface communicating an instruction to the second component which associates the instruction with a packet identifier corresponding to the particular packet; and

wherein in response to packet identifier acquiring the second flow lock, performing the instruction.

13. The method of claim 12, wherein the instruction corresponds to a convert operation to a flow lock on a component of the plurality of components different than the second component.

14. The method of claim 12, wherein the instruction corresponds to a packet gather operation to cause a packet generated from processing of the particular packet to be sent from the packet switching device.

15. The method of claim 12, wherein each particular flow lock of the flow lock and the second flow lock is configured to associate at most a single command with each packet identifier associated with the particular flow lock.

16. The method of claim 11, wherein the acknowledgement message includes an identification of a new packet identifier associated with the particular packet.

17. An apparatus, comprising:

a first component of a plurality of components in a packet switching device including means for adding a packet identifier corresponding to a particular packet to the end of queue of a flow lock;

means for performing the convert operation to a second flow lock on a second component, which is not the first component, of the plurality of components in response to the packet identifier associated with a convert operation request acquiring the flow lock; and

the second component including means for communicating an acknowledgement message indentifying to the particular flow lock interface that the current location of a flow lock associated with the particular packet is the second flow lock in response to said performance of the convert operation.

18. The apparatus of claim 17, wherein the first component includes means for communicating an instruction to the second component in response to receiving the acknowledgement message;

and

wherein the second component includes;

means for associating the instruction with a particular packet identifier, corresponding to the particular packet, in the second flow lock; and

means for performing the instruction in response to the particular packet identifier acquiring the second flow lock.

19. The apparatus of claim 18, wherein the instruction corresponds to a convert operation to a flow lock on a component of the plurality of components different than the second component.

20. The apparatus of claim 18, wherein the instruction corresponds to a packet gather operation;

and wherein the apparatus includes means for gathering a packet resulting from the processing of the particular packet and for sending said gathered packet from the packet switching device.