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

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.

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.

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.

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.

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.

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.

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.

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.