Selecting a queue for service in a queuing system

• US 20030182480A1
• Filed: 03/19/2003
• Published: 09/25/2003
• Est. Priority Date: 03/25/2002
• Status: Active Grant

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Varma, Anujan, Bannur, Jaisimha, Restrick, Robert C.
• Granted Patent: US 7,062,592 B2
• Time in Patent Office: Days
• US Class Current: 710/52
• CPC Class Codes: H04L 47/24 Traffic characterised by specific attributes, e.g. priority or QoS
• CPC Class Codes: H04L 47/50 Queue scheduling

Abstract

In general, in one aspect, the disclosure describes an apparatus for selecting a queue from a plurality of queues. The apparatus includes a hierarchal queue occupancy device to indicate an occupancy status of the plurality of queues, a next queue selector to select a queue based on said hierarchal queue occupancy device and a most recently serviced queue, and a queue identification register to identify a most recently serviced queue.

Claims

1. An apparatus for selecting a queue from a plurality of queues, the apparatus comprising:

a hierarchal queue occupancy device to indicate an occupancy status of the plurality of queues;

a next queue selector to select a queue based on said hierarchal queue occupancy device and a most recently serviced queue; and

a queue identification register to identify the most recently serviced queue.

2. The apparatus of claim 1, wherein said hierarchal queue occupancy device is a plurality of occupancy registers organized and connected together in a hierarchal structure, wherein an occupancy register has a plurality of slots organized into at least one block, a block of slots at one level summarized as a single slot at a next higher level

3. The apparatus of claim 2, wherein said queue identification register identifies the most recently serviced queue by identifying an associated slot within a block in different occupancy registers, the associated slot within one occupancy register identifying the block at a next lower occupancy register.

4. The apparatus of claim 2, wherein said next queue selector includes a plurality of selector logic units equal in number to the plurality of occupancy registers, wherein each selector logic is used to search an individual block within an associated occupancy register.

5. The apparatus of claim 4, wherein said next queue selector further includes a processor to instruct the plurality of selector logic units.

6. The apparatus of claim 5, wherein the processor instructs the plurality of selector logics to:

search in parallel an appropriate block within each of the plurality of occupancy registers for a slot representing a valid queue, wherein the appropriate block is identified in the queue identification register;

determine a lowest valid level of the hierarchal structure that has an occupancy register having a slot representing a valid queue;

record the valid slot for the occupancy register at lowest valid level in the queue identification register;

for each occupancy memory below the lowest valid level, use a slot from an occupancy register directly above in the hierarchal structure to identify a block within a current occupancy register to search for a slot representing a valid queue; and

record the valid slot for each occupancy register below the initial occupancy register within the hierarchal structure in the queue identification register.

7. The apparatus of claim 1, further comprising a service eligibility device to identify queues that are eligible for service, wherein said next queue selector selects the next queue for service based on the queue occupancy device, the service eligibility device and the most recently serviced queue.

8. The apparatus of claim 1, further comprising a queue enable device to limit queues that are enabled for service, wherein said next queue selector selects the next queue based on the queue occupancy device, the queue enable device and the most recently serviced queue.

9. The apparatus of claim 1, further comprising a queue occupancy cache to record an update in occupancy status of a particular queue.

10. The apparatus of claim 7, further comprising a service eligibility cache to record an update in the eligibility status of a particular queue.

11. In a store and forward device, a method of selecting a queue from a plurality of queues, the method comprising:

searching in parallel blocks at different levels of a queue status hierarchy for a slot representing a valid queue, wherein the blocks are identified by a queue identification register;

determining a lowest level to have a slot representing a valid queue;

for each successive level below the lowest level;

identifying a block to search based on a slot from a level directly above; and

searching the identified block for a slot representing a valid queue; and

recording the valid slot in the queue identification register.

12. The method of claim 11, wherein said searching in parallel includes starting the search of the appropriate block at different levels of the queue occupancy hierarchy at a next slot after a slot identified in the queue identification register.

13. The method of claim 12, wherein said searching in parallel includes ending the search of the appropriate block at a last slot in the appropriate block.

14. The method of claim 13, wherein the search for a highest level wraps around to a first slot and ends on the identified slot.

15. The method of claim 11, wherein the queue status hierarchy identifies an occupancy status for each of the plurality of queues and a valid slot indicates an associated queue is non-empty.

16. The method of claim 15, wherein the queue status hierarchy further identifies at least some subset of eligibility status, enablement status, and priority status for each of the plurality of queues and a valid slot indicates an associated queue is non-empty and at least some subset of eligible, enabled and prioritized respectively.

17. The method of claim 11, further comprising:

detecting an update to a slot during a search of the slot;

writing the update to an associated cache; and

updating the slot at completion of the search.

18. A store and forward device that selects a queue from a plurality of queues, the device comprising:

a plurality of receivers to receive packets of data;

a storage medium to associate the packets of data with a plurality of queues;

a plurality of transmitters to transmit the packets of data;

a hierarchal queue occupancy device to indicate an occupancy status of the plurality of queues;

a next queue selector to select a queue based on said hierarchal queue occupancy device and a most recently serviced queue; and

a queue identification register to identify the most recently serviced queue.

19. The device of claim 18, further comprising a service eligibility device to identify queues that are eligible for service, wherein said next queue selector selects the next queue based on the queue occupancy device, the service eligibility device and the most recently serviced queue.

20. The device of claim 18, further comprising a queue enable device to limit queues that are enabled for service, wherein said next queue selector selects the next queue based on the queue occupancy device, the queue enable device and the most recently serviced queue.

21. The device of claim 18, further comprising at least one queue occupancy cache associated with at least one of the plurality of occupancy registers, wherein the at least one queue occupancy cache records an update in occupancy status of an associated queue.

22. The device of claim 20, further comprising a service eligibility cache to record an update in the eligibility status of an associated queue.

23. The device of claim 18, wherein said receivers are Ethernet cards.

24. The device of claim 18, further comprising an optical backplane coupling the receivers and transmitters.

25. In a store and forward device, a method for generating a service status hierarchal structure, 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; and

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.

26. The method of claim 25, further comprising:

searching in parallel an appropriate block at each level for a slot representing a valid queue, wherein the appropriate block is identified in the queue identification register;

determining a lowest valid level to have a slot representing a valid queue;

for each successive level below the lowest valid level,

identifying a block to search based on a slot from a level directly above; and

searching the identified block for a slot representing a valid queue; and

recording the valid slot for each level in the queue identification register.

27. The method of claim 25, further comprising

associating service eligibility slots with individual queues or blocks of queues, wherein each service eligibility slot identifies whether the individual queue or block of queues is eligible for service, and associating queue enable slots with individual queues or blocks of queues, wherein each queue enable slot identifies whether the individual queue or block of queues is enabled for service.

28. The method of claim 25, further comprising associating at least one queue occupancy cache with at least one level of the service status hierarchal structure.