Caching queue status updates
First Claim
Patent Images
1. An apparatus to search a plurality of queues to select a one of the queues, the apparatus comprising:
- a queue occupancy device to indicate an occupancy status of the plurality of queues;
a queue occupancy cache to record an update in occupancy status of a particular queue if the particular queue is involved in the search;
a next queue selector to select a queue based on said queue occupancy device and a most recently serviced queue; and
a queue identification register to identify a most recently serviced queue.
1 Assignment
0 Petitions
Accused Products
Abstract
In general, in one aspect, the disclosure describes an apparatus capable to select a queue. The apparatus includes a queue occupancy device to indicate an occupancy status of the queues, a queue occupancy cache to record an update in occupancy status of a particular queue, a next queue selector to select a queue based on said queue occupancy device and a most recently serviced queue, and a queue identification register to identify a most recently serviced queue.
-
Citations
32 Claims
-
1. An apparatus to search a plurality of queues to select a one of the queues, the apparatus comprising:
-
a queue occupancy device to indicate an occupancy status of the plurality of queues;
a queue occupancy cache to record an update in occupancy status of a particular queue if the particular queue is involved in the search;
a next queue selector to select a queue based on said queue occupancy device and a most recently serviced queue; and
a queue identification register to identify a most recently serviced queue. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11)
-
-
12. In a store and forward device, a method for updating queues at the same time as performing a search on the queues, the method comprising:
-
searching a queue status hierarchy to find a next slot representing a valid queue;
receiving updates to the queue status hierarchy; and
recording the updates in a queue status cache if the updates occur during said searching. - View Dependent Claims (13, 14, 15, 16, 17)
-
-
18. A store and forward device for updating queues at the same time as performing a search on the queues, the device comprising:
-
a plurality of receivers to receive packets of data;
a storage medium to store the packets of data in a plurality of queues;
a plurality of transmitters to transmit the packets of data from the queues;
a queue occupancy device to indicate an occupancy status of the plurality of queues;
a queue occupancy cache to record an update in occupancy status of a particular queue if the particular queue is involved in the search;
a next queue selector to select a queue based on the queue occupancy device and a most recently serviced queue; and
a queue identification register to identify a most recently serviced queue. - View Dependent Claims (19, 20, 21, 22, 23, 24, 25, 26)
-
-
27. In a store and forward device, a method for generating a service status hierarchal structure to identify status of each of a plurality of queues at a plurality of levels, the method comprising:
-
at a lowest level, associating a queue occupancy slot with each queue, wherein the queue occupancy slot reflects an occupancy status of the associated queue;
organizing the queue occupancy slots into a plurality of blocks;
for each successively higher level, associating one block occupancy slot with a block of slots from next lower level, wherein the block occupancy slot summarizes an aggregate occupancy status of the associated block; and
organizing the block occupancy slots into a plurality of blocks, wherein a highest level is organized as a single block;
assigning a queue currently being serviced a queue identification, wherein the queue identification identifies a slot within a block at each level that is associated with the queue currently being serviced, the slot at one level identifying the block at a next lower level; and
associating at least one queue occupancy cache with at least one level of the service status hierarchal structure. - View Dependent Claims (28, 29, 30)
-
-
31. A computer program product, disposed on a computer readable medium, the program including instructions for causing a processor to:
-
search a queue status hierarchy to find a next slot representing a valid queue;
receive updates to the queue status hierarchy; and
record the updates in a queue status cache if the updates occur during said searching. - View Dependent Claims (32)
-
Specification