Using ordered locking mechanisms to maintain sequences of items such as packets

• US 7,626,987 B2
• Filed: 11/12/2003
• Issued: 12/01/2009
• 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: Potter, Kenneth Harvey Jr., Williams, John J. Jr., Fingerhut, John Andrew
• Primary Examiner(s): Jung; Min
• Application Number:
  US10/706,704
• Publication Number:
  US 20050100017A1
• Time in Patent Office: 2,211 Days
• Field of Search: 370/394, 707/8, 718/107
• US Class Current: 370/394
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms
• CPC Class Codes: H04L 45/10 Routing in connection-oriented networks, e.g. X.25 or ATM
• CPC Class Codes: H04L 47/2416 Real-time traffic
• 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 may be particularly useful. One implementation uses a locking request, acceptance, and release protocol. One implementation associates instructions with locking requests such that when a lock is acquired, the locking mechanism executes or causes to be executed the associated instructions as an acceptance request of the lock is implied by the association of instructions (or may be explicitly requested). In some applications, the ordering of the entire sequence of packets is not required to be preserved, but rather only among certain sub-sequences of the entire sequence of items, which can be accomplished by converting an initial root ordered lock (maintaining the sequence of the entire stream of items) to various other locks (each maintaining a sequence of different sub-streams of items).

Claims

1. A method for maintaining ordering, the method comprising:

employing a particular machine to perform the following steps;

identifying a particular item of a plurality of items and in response, generating a locking request to an ordered lock corresponding to the particular item, wherein the ordered lock is configured to maintain a locking queue of identifiers corresponding to locking requests in the order requested and to place a particular identifier corresponding to the locking request at the end of the locking queue;

associating one or more instructions with the particular identifier corresponding to the locking request; and

identifying the particular identifier at the head of the locking queue, and in response, performing said one or more instructions.

2. The method of claim 1, wherein said associating one or more instructions with the particular identifier is performed after another identifier corresponding to a second locking request is added to the locking queue.

3. The method of claim 1, wherein the locking queue contains a plurality of other identifiers corresponding to other items when said generating the locking request to the ordered lock is performed.

4. The method of claim 1, wherein said one or more instructions includes a lock conversion instruction to associate the particular item with a second ordered lock.

5. The method of claim 1, wherein each item of the plurality of items includes a packet.

6. The method of claim 5, wherein said one or more instructions includes a packet gather instruction.

7. The method of claim 5, comprising processing one or more fields of the particular packet to identify a secondary ordered lock;

and

wherein said one or more instructions includes a lock conversion instruction to associate the particular item with a second ordered lock.

8. The method of claim 1, including sending a release lock acknowledgement message;

wherein said one or more instructions includes initiating an operation; and

wherein said sending the release lock acknowledgement message is performed after performance of the operation is complete.

9. The method of claim 1, including sending a release lock acknowledgement message;

wherein said one or more instructions includes initiating an operation; and

wherein said sending the release lock acknowledgement message is performed before performance of the operation is complete.

10. A method for maintaining packet ordering, the method comprising:

employing a particular machine to perform the following steps;

repeatedly identifying a particular packet of a plurality of packets and in response, generating a locking request to an ordered lock corresponding to the particular packet, wherein the ordered lock maintains a locking queue of identifiers corresponding to the locking requests in the order requested;

communicating acceptance requests corresponding to packets of the plurality of packets to the ordered lock; and

repeatedly removing a particular identifier from the head of the locking queue, and granting a locking acceptance request corresponding to the particular identifier if a corresponding said acceptance request was previously generated, or waiting until the locking acceptance request corresponding to the particular identifier is generated and then granting the locking acceptance request corresponding to the particular identifier.

11. The method of claim 10, wherein said locking requests are non-blocking and said acceptance requests are blocking.

12. The method of claim 10, comprising:

in response to said granting the locking acceptance request corresponding to a packet, forwarding the packet.

13. The method of claim 10, comprising:

in response to said granting the locking acceptance request corresponding to a packet, making a second locking request corresponding to the packet to a particular secondary lock of a plurality of secondary ordered locks, the particular secondary lock being identified based on contents of the packet.

14. The method of claim 10, wherein the locking request corresponding to a first packet of the plurality of packets is generated before the locking request corresponding to the second packet of the plurality of packets, and the acceptance request corresponding to the second packet is made before the acceptance request corresponding to the first packet, and the acceptance request corresponding to the first packet is granted before the acceptance request corresponding to the second packet.

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

a plurality of packet processors;

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;

wherein said instructions of each particular lock request are said processed after a lock request of said lock requests, immediately prior to said particular lock request in the order said lock requests are said received, is released; and

a distributor, coupled to the plurality of packet processors 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 one or more processors of the plurality of packet processors;

wherein at least one of said one or more processors is configured to communicate a set of instructions corresponding to the packet to the ordered lock manager.

16. The apparatus of claim 15, wherein the set of instructions includes a packet gather instruction.

17. The apparatus of claim 16, wherein the set of instructions includes an instruction for performing a lock release.

18. The apparatus of claim 15, wherein the set of instructions includes a convert instruction for performing a secondary locking request.

19. The apparatus of claim 15, wherein the set of instructions includes an instruction for performing a lock release request.

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

one or more locking mechanisms for operating a plurality of ordered locks, each ordered lock of the plurality of ordered locks including a queue for storing locking items, each locking mechanism of said one or more locking mechanisms configured to receive locking requests and to place indications of the locking requests in corresponding queues of said plurality of ordered locks, and to receive and react to locking accepts and locking releases, the plurality of ordered locks including a root ordered lock and a secondary ordered lock;

a plurality of packet processors;

a packet distributor configured to receive packets, to make root ordered locking requests for each of said packets, and to distribute each of said packets to the plurality of packet processors;

each packet processor of the plurality of packet processors configured to receive a particular packet, to accept a root ordered lock corresponding to the root ordered locking request for the particular packet, to process the packet to identify a secondary lock, to make a locking request corresponding to the secondary ordered lock, and to release the root ordered lock.

21. The apparatus of claim 20, wherein said each packet processor is configured to perform said make the lock request corresponding to the secondary lock after said accepting the root ordered lock corresponding to the root ordered locking request for the particular packet and before said releasing the root ordered lock.

22. An apparatus for maintaining ordering, the apparatus comprising:

means for identifying a particular item of a plurality of items and in response generating a locking request to an ordered lock corresponding to the particular item, wherein the ordered lock is configured to maintain a locking queue of identifiers corresponding to locking requests in the order requested and to place a particular identifier corresponding to the locking request at the end of the locking queue;

means for associating one or more instructions with the particular identifier corresponding to the locking request; and

means for identifying the particular identifier at the head of the locking queue and in response performing said one or more instructions.

23. The apparatus of claim 22, wherein said means for associating one or more instructions with the particular identifier corresponding to the locking request is configured to associate one or more instructions with the particular identifier after another identifier corresponding to a second locking request is added to the locking queue.

24. The apparatus of claim 22, wherein said one or more instructions includes a lock conversion instruction to associate the particular item with a second ordered lock.

25. The apparatus of claim 22, wherein each item of the plurality of items includes a packet.

26. The apparatus of claim 25, wherein said one or more instructions includes a packet gather instruction.

27. The apparatus of claim 25, comprising means for processing one or more fields of the particular packet to identify a secondary ordered lock;

and

wherein said one or more instructions includes a lock conversion instruction to associate the particular item with a second ordered lock.

28. An apparatus for maintaining packet ordering, the apparatus comprising:

means for repeatedly identifying a particular packet of a plurality of packets and in response, generating a locking request to an ordered lock corresponding to the particular packet, wherein the ordered lock maintains a locking queue of identifiers corresponding to the locking requests in the order requested;

means for communicating acceptance requests corresponding to packets of the plurality of packets to the ordered lock; and

means for repeatedly removing a particular identifier from the head of the locking queue, and granting a locking acceptance request corresponding to the particular identifier if a corresponding said acceptance request was previously generated, or waiting until the locking acceptance request corresponding to the particular identifier is generated and then granting the locking acceptance request corresponding to the particular identifier.

29. The apparatus of claim 28, wherein said locking requests are non-blocking and said acceptance requests are blocking.

30. The apparatus of claim 28, comprising:

means for forwarding the packet in response to said granting the locking acceptance request corresponding to a packet.

31. The apparatus of claim 28, comprising:

means for making a second locking request corresponding to the packet to a particular secondary lock of a plurality of secondary ordered locks in response to said granting the locking acceptance request corresponding to a packet; and

means for identifying the particular secondary lock based on contents of the packet.

32. The apparatus of claim 28, wherein the locking request corresponding to a first packet of the plurality of packets is generated before the locking request corresponding to the second packet of the plurality of packets;

and the acceptance request corresponding to the second packet is made before the acceptance request corresponding to the first packet; and

the acceptance request corresponding to the first packet is granted before the acceptance request corresponding to the second packet.

33. A tangible computer-readable medium containing computer-executable instructions for performing steps for maintaining ordering, said steps comprising:

identifying a particular item of a plurality of items and in response, generating a locking request to an ordered lock corresponding to the particular item, wherein the ordered lock is configured to maintain a locking queue of identifiers corresponding to locking requests in the order requested and to place a particular identifier corresponding to the locking request at the end of the locking queue;

associating one or more instructions with the particular identifier corresponding to the locking request; and

identifying the particular identifier at the head of the locking queue, and in response, performing said one or more instructions.

34. The computer-readable medium of claim 33, wherein said associating one or more instructions with the particular identifier is performed after another identifier corresponding to a second locking request is added to the locking queue.

35. The computer-readable medium of claim 33, wherein the locking queue contains a plurality of other identifiers corresponding to other items when said generating the locking request to the ordered lock is performed.

36. The computer-readable medium of claim 33, wherein said one or more instructions includes a lock conversion instruction to associate the particular item with a second ordered lock.

37. The computer-readable medium of claim 33, wherein each item of the plurality of items includes a packet.

38. The computer-readable medium of claim 37, wherein said one or more instructions includes a packet gather instruction.

39. The computer-readable medium of claim 37, wherein said steps include processing one or more fields of the particular packet to identify a secondary ordered lock;

and wherein said one or more instructions includes a lock conversion instruction to associate the particular item with a second ordered lock.

40. A tangible computer-readable medium containing computer-executable instructions for performing steps for maintaining packet ordering, said steps comprising:

repeatedly identifying a particular packet of a plurality of packets and in response, generating a locking request to an ordered lock corresponding to the particular packet, wherein the ordered lock maintains a locking queue of identifiers corresponding the locking requests in the order requested;

communicating acceptance requests corresponding to packets of the plurality of packets to the ordered lock; and

repeatedly removing a particular identifier from the head of the locking queue, and granting a locking acceptance request corresponding to the particular identifier if a corresponding said acceptance request was previously generated, or waiting until the locking acceptance request corresponding to the particular identifier is generated and then granting the locking acceptance request corresponding to the particular identifier.

41. The computer-readable medium of claim 40, wherein said locking requests are non-blocking and said acceptance requests are blocking.

42. The computer-readable medium of claim 40, wherein said steps include:

in response to said granting the locking acceptance request corresponding to a packet, forwarding the packet.

43. The computer-readable medium of claim 40, wherein said steps include:

in response to said granting the locking acceptance request corresponding to a packet, making a second locking request corresponding to the packet to a particular secondary lock of a plurality of secondary ordered locks, the particular secondary lock being identified based on contents of the packet.

44. The computer-readable medium of claim 40, wherein the locking request corresponding to a first packet of the plurality of packets is generated before the locking request corresponding to the second packet of the plurality of packets, and the acceptance request corresponding to the second packet is made before the acceptance request corresponding to the first packet, and the acceptance request corresponding to the first packet is granted before the acceptance request corresponding to the second packet.

45. The computer-readable medium of claim 40, wherein said one or more instructions includes initiating an operation;

and wherein said steps include sending a release lock acknowledgement message after performance of the operation is complete.

46. The computer-readable medium of claim 40, wherein said one or more instructions includes initiating an operation;

and wherein said steps include sending a release lock acknowledgement message before performance of the operation is complete.

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

a plurality of packet processors;

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

a distributor, coupled to the plurality of packet processors 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 one or more processors of the plurality of packet processors;

wherein at least one of said one or more processors is configured to communicate a set of instructions corresponding to the packet to the ordered lock manager.

48. The apparatus of claim 47, wherein the set of instructions includes a packet gather instruction.

49. The apparatus of claim 48, wherein the set of instructions includes an instruction for performing a lock release.

50. The apparatus of claim 47, wherein the set of instructions includes a convert instruction for performing a secondary locking request.

51. The apparatus of claim 47, wherein the set of instructions includes an instruction for performing a lock release request.