Maintaining aggregate data counts for flow controllable queues

• US 20050015388A1
• Filed: 07/18/2003
• Published: 01/20/2005
• Est. Priority Date: 07/18/2003
• Status: Active Grant

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Varma, Anujan, Bannur, Jaisimha, Dasgupta, Subhajit
• Granted Patent: US 7,080,168 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: H04L 47/50 Queue scheduling
• CPC Class Codes: H04L 47/522 Dynamic queue service slot or variable bandwidth allocation
• CPC Class Codes: H04L 47/621 Individual queue per connection or flow, e.g. per VC
• CPC Class Codes: H04L 47/6255 queue load conditions, e.g. longest queue first
• CPC Class Codes: H04L 49/254 Centralised controller, i.e. arbitration or scheduling

Abstract

In general, in one aspect, the disclosure describes an apparatus that includes a plurality of flow controllable queues containing data to be transmitted. The queues are organized by flow. The apparatus also includes a plurality of destinations to receive data from the plurality of queues. The apparatus further includes a controller to continually maintain an aggregate count of data ready for transmission to the destinations and determine next queue to transmit data from based at least partially on the aggregate counts.

Claims

1. An apparatus, comprising:

a plurality of flow controllable queues containing data to be transmitted, wherein the flow controllable queues are organized by flow;

a plurality of destinations to receive data from the plurality of flow controllable queues;

a controller to continually maintain an aggregate count of data ready for transmission to the destinations and determine next queue to transmit data from based at least partially on the aggregate counts.

2. The apparatus of claim 1, wherein the flow includes at least some subset of source, destination, protocol, and class of service.

3. The apparatus of claim 1, wherein data is ready for transmission if the associated flow controllable queue is flow controlled.

4. The apparatus of claim 1, wherein the count for a particular destination includes flow controllable queues associated with the particular destination.

5. The apparatus of claim 1, wherein the next queue is one of the flow controllable queues associated with the destination having biggest aggregate count.

6. The apparatus of claim 1, wherein the aggregate count is number of bytes.

7. The apparatus of claim 1, wherein the aggregate count for a specific destination is updated to add data queued when data is added to an associated flow controllable queue.

8. The apparatus of claim 1, wherein the aggregate count for a specific destination is updated to remove data dequeued when data is removed from an associated flow controllable queue.

9. The apparatus of claim 3, wherein the aggregate count for a specific destination is updated to remove data associated with a flow controllable queue if the flow control for the associated flow controllable queue is deactivated.

10. The apparatus of claim 3, wherein the aggregate count for a specific destination is updated to add data associated with a flow controllable queue if the flow control for the associated flow controllable queue is activated.

11. The apparatus of claim 1, wherein the aggregate count for a specific destination is updated to reflect any changes in associated flow controllable queues.

12. The apparatus of claim 11, wherein the changes include any combination of data being added, data being removed, or a flow control change.

13. The apparatus of claim 1, wherein said controller updates the aggregate counts each clock cycle to account for changes made to associated flow controllable queues during that clock cycle.

14. The apparatus of claim 1, wherein said controller updates the aggregate count for a specific destination by adding data queued in a first associated flow controllable queue and subtracting data dequeued from a second associated flow controllable queue if the queuing and the dequeuing occurred during the same clock cycle.

15. The apparatus of claim 1, wherein said controller updates the aggregate count for a specific destination by adding data queued in a first associated flow controllable queue, and adding data contained within a second associated flow controllable queue that became flow controlled, if the queuing and the flow control activation occurred during the same clock cycle.

16. The apparatus of claim 1, wherein said controller updates the aggregate count for a specific destination by subtracting data dequeued from a first associated flow controllable queue, and adding data contained within a second associated flow controllable queue that became flow controlled, if the dequeuing and the flow control activation occurred during the same clock cycle.

17. The apparatus of claim 1, wherein said controller updates the aggregate count for a specific destination by adding data queued in a first associated flow controllable queue, subtracting data dequeued from a second associated flow controllable queue, and adding data contained within a third associated flow controllable queue that became flow controlled, if the queuing, the dequeuing, and the flow control activation occurred during the same clock cycle.

18. The apparatus of claim 1, wherein said controller updates the aggregate count for a specific destination by subtracting data contained within an associated flow controllable queue that had flow control deactivated, if the flow control de-activation was the only event that occurred during a clock cycle or occurred during the same clock cycle as a queuing to the associated flow controllable queue, a dequeuing from the associated queue, or both.

19. A method, comprising:

creating a plurality of queues based on at least some subset of source, destination, protocol, and class of service;

storing data received in a first one of the plurality of queues based on the flow of the data;

removing data transmitted from a second one of the plurality of queues;

maintaining a continuous aggregate count of data eligible for transmission to the destinations;

selecting a next queue to transmit data from based at least in part on the aggregate counts.

20. The method of claim 19, wherein the aggregate count for a particular destination includes queues associated with the particular destination.

21. The method of claim 19, wherein said selecting includes selecting one of the queues associated with the destination having biggest aggregate count as the next queue.

22. The method of claim 19, wherein said maintaining includes totaling number of bytes eligible for transmission to the destinations.

23. The method of claim 19, wherein said maintaining includes adding data queued to an associated queue.

24. The method of claim 19, wherein said maintaining includes removing data dequeued from an associated queue.

25. The method of claim 19, wherein said maintaining includes removing an associated queue that is deactivated.

26. The method of claim 19, wherein said maintaining includes adding an associated queue that is activated.

27. The method of claim 19, wherein said maintaining includes updating the count each clock cycle to reflect any combination of data being added, data being removed, and flow control change made to associated queues during that clock cycle.

28. A store and forward device comprising:

a plurality of Ethernet cards to receive, store, and transmit data, wherein the plurality of Ethernet cards include a plurality of ingress ports, a plurality of egress ports, and a plurality of queues;

a processor to maintain a continuous aggregate count of amount of data queued for the egress ports;

a backplane to connect the plurality of Ethernet cards together; and

a scheduler to determine a next queue to service based at least in part on the aggregate counts.

29. The device of claim 28, wherein said scheduler selects the next queue based on the egress port having highest aggregate count.

30. The device of claim 28, wherein said scheduler selects the next queue per ingress port based on the associated egress port having highest aggregate count.

31. The device of claim 28, wherein said processor maintains the aggregate count by updating the count each clock cycle to reflect any combination of data being added, data being removed, and flow control change made to associated queues during that clock cycle.