High speed internetworking traffic scaler and shaper

• US 6,052,375 A
• Filed: 11/26/1997
• Issued: 04/18/2000
• Est. Priority Date: 11/26/1997
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Bass, Brian M., Ervin, Jim P., Lemke, Scott J., Rash, Joseph M., Reiss, Loren Blair, Ku, Edward Hau-chun, Henderson, Douglas Ray, Lee, Joseph Kinman
• Primary Examiner(s): Kizou, Hassan
• Assistant Examiner(s): ELALLAM, AHMED
• Application Number:
  US08/980,090
• Time in Patent Office: 874 Days
• Field of Search: 370/230, 370/232, 370/262, 370/363, 370/389, 370/392, 370/395, 370/412, 370/428
• US Class Current: 370/412
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/22 Traffic shaping
• CPC Class Codes: H04L 47/24 Traffic characterised by specific attributes, e.g. priority or QoS
• CPC Class Codes: H04L 47/39 Credit based
• 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/527 Quantum based scheduling, e.g. credit or deficit based scheduling or token bank
• CPC Class Codes: H04L 47/6225 Fixed service order, e.g. Round Robin
• CPC Class Codes: H04L 49/90 Buffering arrangements

Abstract

A method and system are provided for traffic shaping and bandwidth scaling in a high speed internetworking device. A slot time wheel mechanism is provided for traffic rate control and a credit/debit mechanism is provided for traffic shaping and scaling. The high speed traffic scaler and shaper incorporates a programmable slot time wheel, a traffic scaler state machine, a traffic shaper parameter table and a traffic scaler processor. The traffic scaler processor incorporates a traffic queue allocation manager, a queue priority arbiter, a port enable selector, a port priority arbiter and a DMA channel arbiter. The traffic queue allocation manager and the queue priority, port priority and DMA channel arbiters are each controlled by a corresponding state machine. The parameters in the traffic shaper parameter table are dynamically updated for each logical queue and are used to enable the credit/debit mechanism.

Claims

1. A traffic scaling and shaping apparatus for shaping the output traffic in a high speed computer network device, said apparatus comprising:

a timing mechanism for the scheduling of a plurality of logical queues, each logical queue having associated therewith valid data queues of at least one priority type;

a parameter table for storing for each logical queue a plurality of parameter values used to control the shaping of output traffic;

a traffic scaler mechanism for manipulating the traffic shaper parameter values for each of said logical queues;

a traffic queue allocation manager for allocating each said valid data queue for each said logical queue to a different one of output ports;

a plurality of queue priority arbiters associated with each output port for performing internal arbitration of each valid data queue allocated to it, said internal arbitration resulting in a plurality of priority-based queues for said each output port;

a plurality of port priority arbiters, each port priority arbiter corresponding to a separate priority type, for selecting a valid queue for each priority type; and

a bus DMA arbiter for selecting a final queue to be processed from said selected valid queues of each priority type.

2. The traffic scaling and shaping apparatus of claim 1 wherein said timing mechanism derives its clock from a base clock, and sends a clock pulse to said traffic scaler mechanism to initiate a queue scheduling operation.

3. The traffic scaling and shaping apparatus of claim 1 wherein said valid data queues associated with each logical queue are characterized as a high priority regulated queue, a low priority regulated queue, and an unregulated queue.

4. The traffic scaling and shaping apparatus of claim 1 wherein said parameter table includes for each logical queue, a used credit count value, a debit count value, a threshold value, a transmit enable flag value, a queue priority flag value and an unregulated queue flag value.

5. The traffic scaling and shaping apparatus of claim 4 wherein said used credit count value corresponds to the amount of data that has been moved from each logical queue.

6. The traffic scaling and shaping apparatus of claim 4 wherein said debit count value is a preset value allocated to a corresponding logical queue which is used to decrement from the used credit count during the processing of said corresponding logical queue.

7. The traffic scaling and shaping apparatus of claim 4 wherein said threshold value is a preset value allocated to a corresponding logical queue and which is used to compare against said used credit count value for said corresponding logical queue.

8. The traffic scaling and shaping apparatus of claim 4 wherein said transmit enable flag is set to enable moving of data from a logical queue to an output port if said used credit count is less than the threshold value for said logical queue.

9. The traffic scaling and shaping apparatus of claim 4 wherein said queue priority flag is set to control whether the high priority queue or the low priority queue corresponding to each logical queue can participate respectively in the high priority regulated or low priority regulated queue arbitration process.

10. The traffic scaling and shaping apparatus of claim 4 wherein said unregulated queue flag is used to control whether the unregulated queue corresponding to each logical queue can participate in the unregulated queue arbitration process.

11. The traffic scaling and shaping apparatus of claim 1 wherein said plurality of queue priority arbiters for each output port include a high priority regulated arbiter, a low priority regulated arbiter and an unregulated arbiter, each such queue priority arbiter processing said corresponding valid data queues on a round robin basis.

12. The traffic scaling and shaping apparatus of claim 1 wherein said plurality of port priority arbiters include a high priority regulated arbiter, a low priority regulated arbiter, and an unregulated arbiter, each such port priority arbiter serving to process each corresponding queue from each said output port on a round robin basis.

13. The traffic scaling and shaping apparatus of claim 1 wherein said bus DMA arbiter processes the valid data queues from the plurality of port priority arbiters on a priority basis, the high priority regulated queues being granted DMA bus access first, the low priority regulated queues being granted DMA bus access next, and the unregulated queue being granted DMA bus access last.

14. For use in a high speed computer network device, a method for scaling and shaping the output traffic, said method comprising:

scheduling a plurality of logical queues sequentially, each logical queue having associated therewith valid data queues of at least one priority type;

storing for each logical queue, a plurality of parameter values that are used to control the shaping of output traffic;

manipulating the parameter values corresponding to each of said logical queues dynamically;

allocating to each said valid data queue, corresponding to each said logical queue, a different one of output ports;

performing queue priority arbitration for each valid data queue allocated to each output port to generate a plurality of priority-based queues for said each output port;

performing port priority arbitration for each valid data queue at said each output port according to said priority type to generate a selected valid queue for each priority type; and

performing bus DMA arbitration to select a final queue from said selected valid queues of each priority type.

15. The method of claim 14 wherein said scheduling step is controlled by a timing mechanism.

16. The method of claim 14 wherein said valid data queues associated with each logical queue are characterized as a high priority regulated queue, a low priority regulated queue, and an unregulated queue.

17. The method of claim 14 wherein said stored parameter values include for each logical queue, a used credit count value, a debit count value, a threshold value, a transmit enable flag value, a queue priority flag value and an unregulated queue flag value.

18. The method of claim 17 wherein said used credit count value corresponds to the amount of data that has been moved from each logical queue.

19. The method of claim 17 wherein said debit count value is a preset value allocated to a corresponding logical queue for decrementing the used credit count during the processing of said corresponding logical queue.

20. The method of claim 17 wherein said threshold value is a preset value allocated to a corresponding logical queue for comparing with said used credit count value for said corresponding logical queue.

21. The method of claim 17 including setting said transmit enable flag to enable moving of data from a logical queue to an output port if said used credit count is less than the threshold value for said logical queue.

22. The method of claim 17 including setting said queue priority flag to control whether the high priority queue or the low priority queue corresponding to each logical queue can participate respectively in the high priority regulated or low priority regulated queue arbitration process.

23. The method of claim 17 including setting said unregulated queue flag to control whether the unregulated queue corresponding to each logical queue can participate in the unregulated queue arbitration process.

24. The method of claim 14 wherein performing queue priority arbitration for each output port includes performing high priority regulated arbitration, low priority regulated arbitration and unregulated arbitration, said performing high priority regulated arbitration, low priority regulated arbitration, and unregulated arbitration being performed on corresponding high priority, low priority and unregulated queues for each output port on a round robin basis to generate valid data queues of each priority type at each port.

25. The method of claim 14 wherein performing port priority arbitration includes performing high priority regulated arbitration on the valid high priority data queue;

performing low priority regulated arbitration on the valid low priority data queue; and

performing unregulated arbitration on the valid unregulated data queue, each valid data queue being processed on a round robin basis to generate a selected valid queue for each priority type.

26. The method of claim 14 wherein performing bus DMA arbitration includes processing said selected valid queues of each priority type on a priority basis, said processing step further including granting the high priority regulated queue first DMA bus access, granting the low priority regulated queue next DMA bus access, and granting the unregulated queue last DMA bus access.