Caching queue status updates

• US 20030235188A1
• Filed: 03/20/2003
• Published: 12/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,000,061 B2
• Time in Patent Office: Days
• US Class Current: 370/379
• 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 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.

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.

2. The apparatus of claim 1, wherein said queue occupancy cache writes the update back to said queue occupancy device upon completion of the search.

3. 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 queue based on said queue occupancy device, said service eligibility device and the most recently serviced queue.

4. The apparatus of claim 3, further comprising a service eligibility cache to record an update in the eligibility status of a particular queue if the particular queue is involved in the search.

5. The apparatus of claim 4, wherein said service eligibility cache writes the update back to said service eligibility device upon completion of a search.

6. 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 queue based on said queue occupancy device, said queue enable device and the most recently serviced queue.

7. The apparatus of claim 1, wherein said 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.

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

9. The apparatus of claim 7, 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 unit is used to search an individual block within an associated occupancy register.

10. The apparatus of claim 9, wherein said next queue selector further includes a processor to instruct the plurality of selector logic units 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 lowest valid level of the hierarchal structure that has an occupancy register having a slot representing a valid queue;

for each occupancy register below the lowest valid level,

identify a block to search based on valid slot from an occupancy register directly above in the hierarchal structure; and

search the identified block to identify a slot representing a valid queue; and

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

11. The apparatus of claim 1, wherein the processor further instructs the plurality of selector logic units to search said queue occupancy cache instead of said queue occupancy device for a specific queue if the update has not been recorded back to said queue occupancy device when the specific queue becomes involved in the search.

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.

13. The method of claim 12, further comprising recording the updates to the queue status device at conclusion of said searching.

14. The method of claim 12, wherein said searching includes

searching in parallel an appropriate block at each level of the queue status hierarchy for a slot representing a valid queue, wherein the appropriate block is identified in the 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 for each level in the queue identification register.

15. The method of claim 14, wherein said searching in parallel includes starting the search of the appropriate block at each level of the queue occupancy hierarchy at a next slot after a slot identified in the queue identification register.

16. The method of claim 14, 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.

17. The method of claim 16, 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.

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.

19. The device of claim 18, wherein said queue occupancy cache writes the update back to said queue occupancy device upon completion of the search.

20. 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 available for service based on said queue occupancy device, said service eligibility device and the most recently serviced queue.

21. The device of claim 20, further comprising a service eligibility cache to record an update in the eligibility status of an associated queue if the associated queue is involved in the search.

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

23. The device of claim 18, wherein said queue occupancy device is a plurality of occupancy registers organized and connected together in a hierarchal structure, wherein each occupancy register has a plurality of slots organized into at least one block, a block of slots in a first occupancy register at a first level of the hierarchal structure are summarized as a single slot in a second occupancy register at a next higher level of the hierarchal structure.

24. The device of claim 23, wherein said next queue selector

searches 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;

determines lowest valid occupancy register to have a slot representing a valid queue;

for each successive occupancy register below the lowest valid occupancy register;

identifies a block to search based on a slot from an occupancy register directly above; and

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

records the valid slot for each occupancy register in the queue identification register.

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

26. The device of claim 18, further comprising an optical backplane.

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.

28. The method of claim 27, further comprising searching the queue status hierarchy in a fashion to find next slot representing a valid queue.

29. The method of claim 27, 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.

30. The method of claim 27, further comprising 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.

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.

32. The program of claim 31, further comprising instructions for causing the processor to record the updates to the queue status device at conclusion of said searching.