Apparatus for controlling packet output

• US 7,190,674 B2
• Filed: 10/25/2002
• Issued: 03/13/2007
• Est. Priority Date: 04/30/2002
• Status: Expired due to Fees

• Current Assignee: Fujitsu Limited
• Original Assignee: Fujitsu Limited
• Inventors: Yamashita, Hiroaki, Kobayakawa, Takahiro
• Primary Examiner(s): Pham; Chi
• Assistant Examiner(s): Jagannathan; Melanie
• Application Number:
  US10/281,366
• Publication Number:
  US 20030202517A1
• Time in Patent Office: 1,600 Days
• Field of Search: None
• US Class Current: 370/235
• 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/50 Queue scheduling
• CPC Class Codes: H04L 47/56 implementing delay-aware scheduling
• CPC Class Codes: H04L 49/30 Peripheral units, e.g. input or output ports
• CPC Class Codes: H04L 49/506 Backpressure
• CPC Class Codes: H04L 49/508 Head of Line Blocking Avoidance

Abstract

In a packet scheduler, an arithmetic-operation controlling means designates output ports in a time-sharing manner and a parallel arithmetic operation means performs an arithmetic operation common with the queues of each designated output port to obtain packet output completion due times (evaluation factors) of the top packets of queues of each output port. Intra-port selecting means selects the evaluation factor of a packet that is to be preferentially output for each output port based on the result of the arithmetic operations. Then inter-port selecting means determines one to be most-preferentially output from the top packets selected based on the selected evaluation factors and the bandwidths for the output ports. Therefore, an apparatus for controlling packet output having such a packet scheduler can realize accurately control bandwidths of a plurality of queues, high-speed processing and the reduced size thereby being incorporated in hardware.

Claims

1. An apparatus for controlling packet output comprising:

a plurality of sets of queues, each set associated with the respective one of a plurality of output ports;

enqueuing means for enqueuing each of packets input to said apparatus on corresponding one of said queues in accordance with a flow of each said packet;

a packet scheduler for scheduling issuing an instruction to dequeue each said packet enqueued by said enqueuing means; and

dequeuing means for dequeuing a packet, one from said enqueued packets, for which such an instruction to dequeue is issued by said packet scheduler,

said packet scheduler including;

parallel arithmetic operating means for performing parallel arithmetic operations using a predefined arithmetic formula on said enqueued packets on the top positions (hereinafter called “

top packets”

) of said queues for each of said plural output ports based on parameters including at least information of the arrival time and the size of each of said top packets in order to obtain an evaluation factor indicating the outputting-completion due time for each said top packets;

arithmetic-operation controlling means for selecting one output port for which the parallel arithmetic operations are to be performed on said top packets by said parallel arithmetic operating means from said plural output ports and for inputting the parameters of said top packets of said queues for said selected output port to said parallel arithmetic operating means;

intra-port selecting means for selecting the evaluation factor of a packet that is to be preferentially output, which factor has been obtained by said parallel arithmetic operating means, from the evaluation factors of said top packets of said queues for each said output port based on the evaluation factors of said top packets on said queues for each said output port;

inter-port selecting means for retaining the evaluation factor of said top packet that is to be preferentially output from each said output port, which factor has been selected by said intra-port selecting means, and for selecting one output port from which an enqueued packet is to be most-preferentially output from said apparatus based on the evaluation factors retained therein and on a bandwidth for each said output ports; and

dequeue controlling means for providing said dequeuing means with the instruction to dequeue said top packet, which has been selected from said top packets by said intra-port selecting means, of said output port selected by said inter-port selecting means.

2. An apparatus for controlling packet output according to claim 1, said arithmetic-operation controlling means comprising a time-sharing port designation section for designating the one output port, for which the parallel arithmetic operations are to be performed on said top packets by said parallel arithmetic operating means, from said plural output ports in a time-sharing manner in accordance with the ratio of the bandwidths of said plural output ports.

3. An apparatus for controlling packet output according to claim 2, said packet scheduler further including a pre-processing section for performing an arithmetic operation on terms common with said queues for each said output port in the predefined formula based on the parameters of said enqueued packets to obtain an interim variable and for inputting the interim variable to said parallel arithmetic operating means for the first-named parallel arithmetic operations in order to obtain the evaluation factor for each said top packets of each said output port.

4. An apparatus for controlling packet output according to claim 2, wherein:

said packet scheduler further comprises a bandwidth distribution rate computing section for computing, if one or more queues of each said output port are void of packets, a rate of distribution of the bandwidths for active queues having at least one packet of each said output port so as to distribute bandwidths allocated to said void queues to said active queues; and

said parallel arithmetic operating means performs the first-named parallel arithmetic operations based on the distribution rate of the bandwidths, which have been computed for said active queues by said bandwidth computing section in order to obtain evaluation factors of said top packets on said active queues.

5. An apparatus for controlling packet output according to claim 2, wherein:

said packet scheduler further comprises fixed bandwidth control means for outputting a fixed rate of the distribution of bandwidths predetermined for said queues of each said output port to said parallel arithmetic operating means; and

said parallel arithmetic operating means performs the first-named parallel arithmetic operations based on the fixed distribution rate of the bandwidths output from said fixed bandwidth control means in order to obtain the evaluation factor for each said top packet of each said output port.

6. An apparatus for controlling packet output according to claim 2, wherein:

said packet scheduler further comprises

a bandwidth distribution rate computing section for computing, if one or more queues of each said output port are void of packets, a rate of distribution of the bandwidths for active queues having at least one packet of each said output port so as to distribute bandwidths allocated to said void queues to said active queues, and

fixed bandwidth control means for outputting a fixed rate of distribution of the bandwidths predetermined for said queues of each said output port to said parallel arithmetic operating means;

said parallel arithmetic operating means further comprises bandwidth selecting means for selecting one from the computed distribution rate of the bandwidths from said bandwidth distribution rate computing and the fixed distribution rate of the bandwidths from said fixed bandwidth control means for each of said queues of each said output ports; and

said parallel arithmetic operating means performs the first-named parallel arithmetic operations based on the distribution rate of the bandwidths selected by said bandwidth selecting means in order to obtain the evaluation factor for each said top packet on each said queue of each said output port.

7. An apparatus for controlling packet output according to claim 2, said packet scheduler further comprising priority control means for determining priorities of said queues of said each output port and for masking, if one of said queues has a packet, the evaluation factors of queues of lower priorities than said one queue, which factors has been obtained by said parallel arithmetic operating means.

8. An apparatus for controlling packet output according to claim 2, said time-sharing port designation section determines a ratio of the designating of said plural output ports in the time-sharing manner for a predetermined time period in accordance with the ratio of the bandwidths of said plural output ports.

9. An apparatus for controlling packet output according to claim 3, wherein:

said packet scheduler further comprises a bandwidth distribution rate computing section for computing, if one or more queues of each said output port are void of packets, a rate of distribution of the bandwidths for active queues having at least one packet of each said output port so as to distribute bandwidths allocated to said void queues to said active queues; and

said parallel arithmetic operating means performs the first-named parallel arithmetic operations based on the distribution rate of the bandwidths, which have been computed for said active queues by said bandwidth computing section in order to obtain evaluation factors of said top packets on said active queues.

10. An apparatus for controlling packet output according to claim 3, wherein:

said packet scheduler further comprises fixed bandwidth control means for outputting a fixed rate of the distribution of bandwidths predetermined for said queues of each said output port to said parallel arithmetic operating means; and

said parallel arithmetic operating means performs the first-named parallel arithmetic operations based on the fixed distribution rate of the bandwidths output from said fixed bandwidth control means in order to obtain the evaluation factor for each said top packet of each said output port.

11. An apparatus for controlling packet output according to claim 3, wherein:

said packet scheduler further comprises

a bandwidth distribution rate computing section for computing, if one or more queues of each said output port are void of packets, a rate of distribution of the bandwidths for active queues having at least one packet of each said output port so as to distribute bandwidths allocated to said void queues to said active queues, and

fixed bandwidth control means for outputting a fixed rate of distribution of the bandwidths predetermined for said queues of each said output port to said parallel arithmetic operating means;

said parallel arithmetic operating means further comprises bandwidth selecting means for selecting one from the computed distribution rate of the bandwidths from said bandwidth distribution rate computing and the fixed distribution rate of the bandwidths from said fixed bandwidth control means for each of said queues of each said output ports; and

said parallel arithmetic operating means performs the first-named parallel arithmetic operations based on the distribution rate of the bandwidths selected by said bandwidth selecting means in order to obtain the evaluation factor for each said top packet on each said queue of each said output port.

12. An apparatus for controlling packet output according to claim 3, said packet scheduler further comprising priority control means for determining priorities of said queues of said each output port and for masking, if one of said queues has a packet, the evaluation factors of queues of lower priorities than said one queue, which factors has been obtained by said parallel arithmetic operating means.

13. An apparatus for controlling packet output according to claim 1, said packet scheduler further including a pre-processing section for performing an arithmetic operation on terms common with said queues for each said output port in the predefined formula based on the parameters of said enqueued packets to obtain an interim variable and for inputting the interim variable to said parallel arithmetic operating means for the first-named parallel arithmetic operations in order to obtain the evaluation factor for each said top packets of each said output port.

14. An apparatus for controlling packet output according to claim 13, wherein:

said packet scheduler further comprises a bandwidth distribution rate computing section for computing, if one or more queues of each said output port are void of packets, a rate of distribution of the bandwidths for active queues having at least one packet of each said output port so as to distribute bandwidths allocated to said void queues to said active queues; and

said parallel arithmetic operating means performs the first-named parallel arithmetic operations based on the distribution rate of the bandwidths, which have been computed for said active queues by said bandwidth computing section in order to obtain evaluation factors of said top packets on said active queues.

15. An apparatus for controlling packet output according to claim 13, wherein:

said packet scheduler further comprises fixed bandwidth control means for outputting a fixed rate of the distribution of bandwidths predetermined for said queues of each said output port to said parallel arithmetic operating means; and

said parallel arithmetic operating means performs the first-named parallel arithmetic operations based on the fixed distribution rate of the bandwidths output from said fixed bandwidth control means in order to obtain the evaluation factor for each said top packet of each said output port.

16. An apparatus for controlling packet output according to claim 13, wherein:

said packet scheduler further comprises

a bandwidth distribution rate computing section for computing, if one or more queues of each said output port are void of packets, a rate of distribution of the bandwidths for active queues having at least one packet of each said output port so as to distribute bandwidths allocated to said void queues to said active queues, and

fixed bandwidth control means for outputting a fixed rate of distribution of the bandwidths predetermined for said queues of each said output port to said parallel arithmetic operating means;

said parallel arithmetic operating means further comprises bandwidth selecting means for selecting one from the computed distribution rate of the bandwidths from said bandwidth distribution rate computing and the fixed distribution rate of the bandwidths from said fixed bandwidth control means for each of said queues of each said output ports; and

said parallel arithmetic operating means performs the first-named parallel arithmetic operations based on the distribution rate of the bandwidths selected by said bandwidth selecting means in order to obtain the evaluation factor for each said top packet on each said queue of each said output port.

17. An apparatus for controlling packet output according to claim 13, said packet scheduler further comprising priority control means for determining priorities of said queues of said each output port and for masking, if one of said queues has a packet, the evaluation factors of queues of lower priorities than said one queue, which factors has been obtained by said parallel arithmetic operating means.

18. An apparatus for controlling packet output according to claim 1, wherein:

said packet scheduler further comprises a bandwidth distribution rate computing section for computing, if one or more queues of each said output port are void of packets, a rate of distribution of the bandwidths for active queues having at least one packet of each said output port so as to distribute bandwidths allocated to said void queues to said active queues; and

said parallel arithmetic operating means performs the first-named parallel arithmetic operations based on the distribution rate of the bandwidths, which have been computed for said active queues by said bandwidth computing section in order to obtain evaluation factors of said top packets on said active queues.

19. An apparatus for controlling packet output according to claim 18, said packet scheduler further comprising priority control means for determining priorities of said queues of said each output port and for masking, if one of said queues has a packet, the evaluation factors of queues of lower priorities than said one queue, which factors has been obtained by said parallel arithmetic operating means.

20. An apparatus for controlling packet output according to claim 19, wherein:

said packet scheduler further comprises a previous evaluation factor memory for retaining evaluation and factors obtained as the results of previous parallel arithmetic operations using the predefined arithmetic formula in said parallel arithmetic operating means with respect to said plural queues (hereinafter called “

preferentially-controlled queues”

) of which priorities have been determined; and

said parallel arithmetic operating means performs the first-named arithmetic operations based on the last-named evaluation factors retained in said previous evaluation factor memory in order to obtain evaluation factors of said top packets of said preferentially-controlled queues thereby controlling the bandwidths of said preferentially-controlled queues regarding said preferentially-controlled queues as a single queue.

21. An apparatus for controlling packet output according to claim 1, wherein:

said packet scheduler further comprises fixed bandwidth control means for outputting a fixed rate of the distribution of bandwidths predetermined for said queues of each said output port to said parallel arithmetic operating means; and

said parallel arithmetic operating means performs the first-named parallel arithmetic operations based on the fixed distribution rate of the bandwidths output from said fixed bandwidth control means in order to obtain the evaluation factor for each said top packet of each said output port.

22. An apparatus for controlling packet output according to claim 21, said packet scheduler further comprising priority control means for determining priorities of said queues of said each output port and for masking, if one of said queues has a packet, the evaluation factors of queues of lower priorities than said one queue, which factors has been obtained by said parallel arithmetic operating means.

23. An apparatus for controlling packet output according to claim 22, wherein:

said packet scheduler further comprises a previous evaluation factor memory for retaining evaluation and factors obtained as the results of previous parallel arithmetic operations using the predefined arithmetic formula in said parallel arithmetic operating means with respect to said plural queues (hereinafter called “

preferentially-controlled queues”

) of which priorities have been determined; and

said parallel arithmetic operating means performs the first-named arithmetic operations based on the last-named evaluation factors retained in said previous evaluation factor memory in order to obtain evaluation factors of said top packets of said preferentially-controlled queues thereby controlling the bandwidths of said preferentially-controlled queues regarding said preferentially-controlled queues as a single queue.

24. An apparatus for controlling packet output according to claim 1, wherein:

said packet scheduler further comprises

a bandwidth distribution rate computing section for computing, if one or more queues of each said output port are void of packets, a rate of distribution of the bandwidths for active queues having at least one packet of each said output port so as to distribute bandwidths allocated to said void queues to said active queues, and

fixed bandwidth control means for outputting a fixed rate of distribution of the bandwidths predetermined for said queues of each said output port to said parallel arithmetic operating means;

said parallel arithmetic operating means further comprises bandwidth selecting means for selecting one from the computed distribution rate of the bandwidths from said bandwidth distribution rate computing and the fixed distribution rate of the bandwidths from said fixed bandwidth control means for each of said queues of each said output ports; and

said parallel arithmetic operating means performs the first-named parallel arithmetic operations based on the distribution rate of the bandwidths selected by said bandwidth selecting means in order to obtain the evaluation factor for each said top packet on each said queue of each said output port.

25. An apparatus for controlling packet output according to claim 24, said packet scheduler further comprising priority control means for determining priorities of said queues of said each output port and for masking, if one of said queues has a packet, the evaluation factors of queues of lower priorities than said one queue, which factors has been obtained by said parallel arithmetic operating means.

26. An apparatus for controlling packet output according to claim 25, wherein:

said packet scheduler further comprises a previous evaluation factor memory for retaining evaluation factors obtained as the results of previous parallel arithmetic operations using the predefined arithmetic formula in said parallel arithmetic operating means with respect to said plural queues (hereinafter called “

preferentially-controlled queues”

) of which priorities have been determined; and

said parallel arithmetic operating means performs the first-named arithmetic operations based on the last-named evaluation factors retained in said previous evaluation factor memory in order to obtain evaluation factors of said top packets of said preferentially-controlled queues thereby controlling the bandwidths of said preferentially-controlled queues regarding said preferentially-controlled queues as a single queue.

27. An apparatus for controlling packet output according to claim 1, said packet scheduler further comprising priority control means for determining priorities of said queues of said each output port and for masking, if one of said queues has a packet, the evaluation factors of queues of lower priorities than said one queue, which factors has been obtained by said parallel arithmetic operating means.

28. An apparatus for controlling packet output according to claim 27, wherein:

said packet scheduler further comprises a previous evaluation factor memory for retaining evaluation and factors obtained as the results of previous parallel arithmetic operations using the predefined arithmetic formula in said parallel arithmetic operating means with respect to said plural queues (hereinafter called “

preferentially-controlled queues”

) of which priorities have been determined; and

said parallel arithmetic operating means performs the first-named arithmetic operations based on the last-named evaluation factors retained in said previous evaluation factor memory in order to obtain evaluation factors of said top packets of said preferentially-controlled queues thereby controlling the bandwidths of said preferentially-controlled queues regarding said preferentially-controlled queues as a single queue.

29. An apparatus for controlling packet output according to claim 1, said packet scheduler further comprising:

destination-information retaining means for retaining destination information for designating two or more of said plural output ports through which one of said enqueued packets is to be multicasted; and

distribution controlling means for controlling, each time when one of said two or more output ports is selected by said arithmetic-operation controlling means, the evaluating factor of said last-named enqueued packet that is to be multicasted to said two or more output ports designated by said destination information, which factor has been obtained by said parallel arithmetic operating means, by discriminating that the evaluating factor of said last-named enqueued packet is valid.

30. An apparatus for controlling packet output according to claim 1, said inter-port selecting means including:

a first register for retaining the evaluation factor of said top packet that is to be preferentially output from each said output port, which factor has been selected by said intra-port selecting means; and

an output-port-shaping controlling section for controlling the bandwidth of each said output port by controlling output of the evaluate factor retained in said first register regarding the bandwidth of each said output port based on information of the last-named evaluation factor of each said output port and the bandwidth predetermined for each said output port.

31. An apparatus for controlling packet output according to claim 30, said output-port-shaping controlling section including an output-port-burst controlling section for controlling a burst of output of said top packets, each selected by said intra-port selecting means, except said top packet that has been selected to be most-preferentially output by controlling outputting of the evaluation factors of said except top packets.

32. An apparatus for controlling packet output according to claim 30, said dequeue controlling means including:

a second register for retaining the evaluation factor of said top packet that is to be preferentially output from each said output port, which factor has been selected by said intra-port selecting means; and

a dequeue-bus-shaping controlling section for controlling the bandwidth of each said output port by controlling output of the evaluate factor retained in said second register regarding bandwidths of dequeue bus, through which said enqueued packets are to be output from said apparatus, based on information of the evaluation factors for each said output port and the bandwidth predetermined for the dequeue bus.

33. An apparatus for controlling packet output according to claim 32, said dequeue-bus-shaping controlling section including a dequeue-bus-burst controlling section for controlling a burst of output of said top packets, each selected by said intra-port selecting means, except said top packet that has been selected to be most-preferentially output by controlling outputting of the evaluation factors of the except packets on the top positions.

34. An apparatus for controlling packet output according to claim 1, wherein:

said packet scheduler comprising a leading-packets memory for retaining the parameters of a number of packets which are successively enqueued on said queues of each said output ports and which packets includes said top packets of said last-named queues; and

upon issuing the instruction to dequeue said top packet, which has been selected from said plural queue by said inter-port selecting means

said arithmetic-operation controlling means reads the parameter of the subsequent packet of said last-named top packet that is to be dequeued from said leading-packet memory and inputs the read parameter to said parallel arithmetic operating means.

35. An apparatus for controlling packet output according to claim 1, said dequeue controlling means including:

a second register for retaining the evaluation factor of said top packet that is to be preferentially output from each said output port, which factor has been selected by said intra-port selecting means; and

a dequeue-bus-shaping controlling section for controlling the bandwidth of each said output port by controlling output of the evaluation factor retained in said second register regarding bandwidths of dequeue bus, through which said enqueued packets are to be output from said apparatus, based on information of the evaluation factors for each said output port and the bandwidth predetermined for the dequeue bus.

36. An apparatus for controlling packet output according to claim 1, said dequeue controlling means further including a mask-signal outputting section for outputting, upon issuing the instruction to dequeue said top packet of said queue, which has been selected by said inter-port selecting means, a mask-control signal to said arithmetic-operation controlling means, said parallel arithmetic operating means and said inter-port selecting means in order to mask the evaluation factors of said last-named top packet that is selected to be dequeued by said dequeue controlling means.