Cooperative flow locks distributed among multiple components

• US 8,139,488 B2
• Filed: 05/30/2008
• Issued: 03/20/2012
• 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: Williams, John J. Jr., Chesters, Eric John
• Primary Examiner(s): Pham, Chi
• Assistant Examiner(s): Mohebbi, Kouroush
• Application Number:
  US12/130,936
• Publication Number:
  US 20090296580A1
• Time in Patent Office: 1,390 Days
• Field of Search: None
• 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 and process a plurality of flow locks in a distributed manner, wherein each of the plurality of components includes one or more packet processing contexts and one or more flow lock interfaces;

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, which includes said one component communicating directly or indirectly with the different component in processing flow locks, including said one particular flow lock and the second particular flow lock, in a distributed manner;

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;

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;

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; and

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.

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

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

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

5. The apparatus claim 1, 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 1, wherein each of said plurality of components is an application-specific integrated circuit (ASIC).

8. 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, which includes the first component communicating directly or indirectly with the second component in processing flow locks, including the flow lock and the second flow lock, in a distributed manner; and

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

wherein each of the plurality of components includes one or more packet processing contexts and one or more flow lock interfaces.

9. The method of claim 8, 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.

10. The method of claim 9, 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.

11. The method of claim 9, 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.

12. The method of claim 9, 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.

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

14. An apparatus, comprising:

a plurality of components, each of the plurality of components being configured to maintain and process a plurality of flow locks in a distributed manner, wherein each of the plurality of components includes one or more packet processing contexts and one or more flow lock interfaces;

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, which includes said one component communicating directly or indirectly with the different component in processing flow locks, including said one particular flow lock and the second particular flow lock, in a distributed manner;

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.

15. The apparatus of claim 14, 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.

16. The apparatus of claim 15, 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.