Split-queue architecture with a first queue area and a second queue area and queue overflow area having a trickle mode and an overflow mode based on prescribed threshold values

Claim 1

A queue structure for queuing entries, comprising: a first queue area for receiving entries, said first queue area including an input portion and an output portion; a second queue area for outputting entries input to said first queue area, said second queue area including an input portion and an output portion; a queue overflow engine logically coupled to both said first queue area and said second queue area, said queue overflow engine including logic circuitry for transferring entries from said first queue area to said second queue area using one of a trickle mode and an overflow mode, based on a prescribed threshold value that identifies one of a maximum number of entries allowed in said first queue area and a minimum number of entries allowed in said second queue area; an overflow storage area operatively coupled to said queue overflow engine for selectively receiving entries from said first queue area and forwarding said entries to said second queue area, said overflow storage area having a relatively larger storage capacity than said first and second queue areas; wherein said prescribed threshold value identifies a predetermined number of entries allowed in said first queue area, and said logic circuitry is further configured to: compare the number of entries stored in said second queue area to a second prescribed threshold value that identifies a minimum number of entries allowed in said second queue area; and if the number of entries stored in said second queue area is less than said second threshold value, then transferring entries into said second queue area using said trickle mode.

Claim 10

A method of queuing entries into a queue structure, the method comprising the steps: receiving entries in a first queue area of the queue structure; comparing the number of entries stored in the first queue area to a prescribed threshold value that identifies one of a maximum number of entries allowed in the first queue area and a minimum number of entries allowed in the second queue area; and transferring entries from the first queue area into a second queue area using one of a trickle mode and an overflow mode, based on the step of comparing; determining, prior to performing the step of transferring, if there is available capacity in the second queue area; performing the step of transferring based on both the step of comparing and the step of determining; wherein the prescribed threshold value corresponds to a maximum number of entries allowed in the first queue area, and further comprising a step of setting a second threshold value corresponding to a minimum number of entries allowed in the second queue area; wherein the step of transferring entries from the first queue area comprises the steps: determining if the number of entries in the first queue area is greater than the first threshold value; receiving additional entries into the first queue area if the number of entries stored therein is less than the first threshold value; and transferring entries to an overflow storage area if the number of entries in the first queue area exceeds the first threshold value and the number of entries in the second queue area exceeds the second threshold value.

Claim 11

A method of queuing entries into a queue structure, the method comprising the steps: receiving entries in a first queue area of the queue structure; comparing the number of entries stored in the first queue area to a prescribed threshold value that identifies one of a maximum number of entries allowed in the first queue area and a minimum number of entries allowed in the second queue area; and transferring entries from the first queue area into a second queue area using one of a trickle mode and an overflow mode, based on the step of comparing; determining, prior to performing the step of transferring, if there is available capacity in the second queue area; performing the step of transferring based on both the step of comparing and the step of determining; wherein the prescribed threshold value corresponds to a maximum number of entries allowed in the first queue area, and further comprising a step of setting a second threshold value corresponding to a minimum number of entries allowed in the second queue area; wherein the step of transferring entries from the first queue area comprises the steps: determining if the number of entries in the first queue area is greater than the first threshold value; receiving additional entries into the first queue area if the number of entries stored therein is less than the first threshold value; and transferring entries to an overflow storage area if the number of entries in the first queue area exceeds the first threshold value and the number of entries in the second queue area exceeds the second threshold value.