Method and apparatus for a data structure comprising a hierarchy of queues or linked list data structures

A method performed by a single appliance, the method comprising:

• (a) receiving a particular piece of information of a stream of pieces of information to be added to a queue, the queue including a plurality of sub-queues with each of capable of storing a plurality of pieces of information in the stream of pieces of information;
• (b) adding the particular piece of information to a currently selected one of the plurality of sub-queues to which to add information;
• (c) advancing the currently selected one of the plurality of sub-queues to which to add information to a next one of the plurality of the sub-queues to which to add information in a predetermined order among the plurality of sub-queues independent of the stream of information;
• (d) removing information from a currently selected one of the plurality of sub-queues to which to remove information;
• (e) advancing the currently selected one of the plurality of sub-queues to which to remove information to a next one of the plurality of sub-queues to which to remove information in the predetermined order;
• and
• repeatedly performing steps (a)-(c) to add information to the queue and steps (d)-(e) to remove information from the queue such that pieces of information of the stream of pieces of information are added to queue and removed from the queue in the same order.

A queue for storing items of a stream of information with said items received in a particular order, the queue being implemented by a single apparatus, the queue comprising:

• a plurality of sub-queues, each of the plurality of sub-queues capable of storing a plurality of items;
• an enqueue distributor configured to receive said items of the stream of information in said particular order, and configured to distribute said items to the plurality of sub-queues in a predetermined sequence order among the plurality of sub-queues such that each of said items are only stored in a single one of the plurality of sub-queues;
• and
• a dequeue receiver configured to only receive said items of the stream of information from the plurality of queues in the predetermined sequence order and to forward said items in said particular order;
• wherein the predetermined sequence order is a round robin order among the plurality of sub-queues;
• wherein the enqueue distributor includes a counter for use in identifying the predetermined sequence order;
• wherein said items correspond to packets.

A queue for storing items of a stream of information with said items received in a particular order, the queue being implemented by a single apparatus, the queue comprising:

• a plurality of sub-queues, each of the plurality of sub-queues capable of storing a plurality of items;
• means for receiving said items of the stream of information in said particular order, and for distributing said items to the plurality of sub-queues in a predetermined sequence order among the plurality of sub-queues such that each of said items are only stored in a single one of the plurality of sub-queues, wherein items distributed to a sub-queue are stored in the sub-queue wherein the means for receiving includes a counter for identifying the predetermined sequence order;
• and
• means for retrieving said items of the stream of information from the plurality of queues in the predetermined sequence order and for forwarding said items in said particular order,
• wherein the sequence order among the plurality of sub-queues is predetermined and independent of the content of said items of the stream of information;
• wherein the predetermined order is a round robin among the plurality of sub-queues;
• and
• wherein said items correspond to packets.

A queue, comprising:

• means for adding information to the queue, including means for repeatedly performing:
• (a) receiving a particular piece of information of a stream of pieces of information to be added to the queue, the queue including a plurality of sub-queues with each of capable of storing a plurality of pieces of information in the stream of pieces of information;
• (b) adding the particular piece of information to a currently selected one of the plurality of sub-queues to which to add information;
• (c) advancing the currently selected one of the plurality of sub-queues to which to add information to a next one of the plurality of the sub-queues to which to add information in a predetermined order among the plurality of sub-queues independent of the stream of information;
• and
• means for removing information from the queue such that pieces of information of the stream of pieces of information are added to queue and removed from the queue in the same order, wherein said means for removing information from the queue includes means for repeatedly performing:
• (d) removing information from a currently selected one of the plurality of sub-queues to which to remove information;
• and (e) advancing the currently selected one of the plurality of sub-queues to which to remove information to a next one of the plurality of sub-queues to which to remove information in the predetermined order.

An apparatus comprising one or more processors and memory, wherein the memory stores one or more instructions that, when executed by said one or more processors, perform operations comprising:

• (a) receiving a particular piece of information of a stream of pieces of information to be added to a queue, the queue including a plurality of sub-queues with each of capable of storing a plurality of pieces of information in the stream of pieces of information;
• (b) adding the particular piece of information to a currently selected one of the plurality of sub-queues to which to add information;
• (c) advancing the currently selected one of the plurality of sub-queues to which to add information to a next one of the plurality of the sub-queues to which to add information in a predetermined order among the plurality of sub-queues independent of the stream of information;
• (d) removing information from a currently selected one of the plurality of sub-queues to which to remove information;
• (e) advancing the currently selected one of the plurality of sub-queues to which to remove information to a next one of the plurality of sub-queues to which to remove information in the predetermined order;
• and
• repeatedly performing steps (a)-(c) to add information to the queue and steps (d)-(e) to remove information from the queue such that pieces of information of the stream of pieces of information are added to queue and removed from the queue in the same order.