Method and apparatus for distribution of bandwidth in a switch

A method for bandwidth scheduling in a switch comprising a switching fabric, and a bandwidth scheduler located before any queue of said switch, the method comprising the steps of:

• receiving a stream of data from the switching fabric;
• extracting flow identity information from the stream;
• updating counters corresponding to the stream;
• and
• subjecting the stream to a decision making algorithm in the bandwidth scheduler based on the extracted flow identity information and the updated counters for that particular stream resulting in that the stream is accepted or rejected before said stream enters any queue of said switch,
• wherein the flow identity information includes port, identified by port number, and traffic class, and
• wherein a limit (BWTCmax) is set on the maximum accepted bandwidth per traffic class, and
• wherein a virtual queue is associated with each traffic class by means of a counter VQLTC (virtual queue length per traffic class) and the counter VQLTC is increased with the packet length for each accepted packet and updated each time unit by subtracting the configuration parameter BWTCmax.

A method for bandwidth scheduling in a switch comprising a switching fabric, and a bandwidth scheduler located before any queue of said switch, the method comprising the steps of:

• receiving a stream of data from the switching fabric;
• extracting flow identity information from the stream;
• updating counters corresponding to the stream;
• and
• subjecting the stream to a decision making algorithm in the bandwidth scheduler based on the extracted flow identity information and the updated counters for that particular stream resulting in that the stream is accented or rejected before said stream enters any queue of said switch,
• wherein the flow identity information includes port, identified by port number, and traffic class, and
• wherein a counter TC (traffic class) is increased with the packet length when the traffic class accepts a packet, and a variable TCPmax (traffic class port maximum) is set to a value equal to the maximum of the TC counters for the port in question, wherein, for a traffic class having the ratio TC/TCPmax<a constant, a flag is set to a value used by the algorithm in deciding to accept or reject a packet, whereby the bandwidth is distributed in accordance with the Max-Min algorithm.

A method for bandwidth scheduling in a switch comprising a switching fabric, and a bandwidth scheduler located before any queue of said switch, the method comprising the steps of:

• receiving a stream of data from the switching fabric;
• extracting flow identity information from the stream;
• updating counters corresponding to the stream;
• and
• subjecting the stream to a decision making algorithm in the bandwidth scheduler based on the extracted flow identity information and the undated counters for that particular stream resulting in that the stream is accepted or rejected before said stream enters any queue of said switch,
• wherein the flow identity information includes port, identified by port number, and traffic class, and
• wherein each traffic class is guaranteed a bandwidth up to a limit (BWTCmin), and
• wherein a counter TC (traffic class) is increased with the packet length when the traffic class accepts a packet and is updated each time unit by subtracting the configuration parameter BWTCmin (bandwidth per traffic class minimum).

A method for bandwidth scheduling in a switch comprising a switching fabric, and a bandwidth scheduler located before any queue of said switch, the method comprising the steps of:

• receiving a stream of data from the switching fabric;
• extracting flow identity information from the stream;
• updating counters corresponding to the stream;
• and
• subjecting the stream to a decision making algorithm in the bandwidth scheduler based on the extracted flow identity information and the updated counters for that particular stream resulting in that the stream is accepted or rejected before said stream enters any queue of said switch,
• wherein the flow identity information includes port, identified by port number, and traffic class, and
• wherein, for each traffic class, a counter BL (backlogging) keeps track of how many packets are accepted in relation to the other traffic classes, so that if a previously idle traffic class becomes active, the traffic class is compensated by distributing more bandwidth to this traffic class.

A method for bandwidth scheduling in a switch comprising a switching fabric, and a bandwidth scheduler located before any queue of said switch, the method comprising the steps of:

• receiving a stream of data from the switching fabric;
• extracting flow identity information from the stream;
• updating counters corresponding to the stream;
• and
• subjecting the stream to a decision making algorithm in the bandwidth scheduler based on the extracted flow identity information and the updated counters for that particular stream resulting in that the stream is accepted or rejected before said stream enters any queue of said switch,
• wherein the flow identity information includes port, identified by port number, and traffic class, and
• wherein, if one traffic class is particularly aggressive or active, it is forced to give up a part of its accented bandwidth and
• wherein, when a packet is accepted in a traffic class having the maximum accepted bandwidth (TC=TCPmax), a charity function forces the packet to be discarded and a counter charity (CH) is increased with a configurable fraction of the accepted packet length (+packet length×give factor), and when a packet is rejected in one of the other traffic classes, the charity function forces the packet to be accepted and the clarity counter (CH) is decreased with the packet length multiplied with the weight of the respective traffic class (−packet length×WTC), and the counter (CH) is updated each time unit by multiplication with a decay factor.

A method for bandwidth scheduling in a switch comprising a switching fabric, and a bandwidth scheduler located before any queue of said switch, the method comprising the steps of:

• receiving a stream of data from the switching fabric;
• extracting flow identity information from the stream;
• updating counters corresponding to the stream;
• and
• subjecting the stream to a decision making algorithm in the bandwidth scheduler based on the extracted flow identity information and the updated counters for that particular stream resulting in that the stream is accepted or rejected before said stream enters any queue of said switch,
• wherein the flow identity information includes port, identified by port number, and traffic class, and, wherein:
• a limit (BWPmax) is set on the maximum accepted bandwidth per port, a virtual queue is associated with each port, and a flag is set in dependence of the port queue length;
• a limit (BWTCmax) is set on the maximum accepted bandwidth per traffic class, a virtual queue is associated with each traffic class, and a flag is set in dependence of the traffic class queue length;
• the bandwidth is distributed in accordance with the Max-Min algorithm;
• each traffic class is guaranteed a bandwidth up to a limit (BWTCmin);
• a weight (WTC) is associated with each traffic class, so shat the algorithm automatically prioritizes certain traffic classes;
• for each traffic class, a backlogging counter (BL) keeps track of how many packets are accepted in relation to the other traffic classes, so that if a previously idle traffic class becomes active, the traffic class is compensated by distributing more bandwidth to this traffic class;
• if one traffic class is particularly aggressive or active, it gives up a part of its accepted bandwidth.

A method for bandwidth scheduling in a switch comprising a switching fabric, and a bandwidth scheduler located before any queue of said switch, the method comprising the steps of:

• receiving a stream of data from the switching fabric;
• extracting flow identity information from the stream;
• updating counters corresponding to the stream;
• and
• subjecting the stream to a decision making algorithm in the bandwidth scheduler based on the extracted flow identity information and the updated counters for that particular stream resulting in that the stream is accepted or rejected before said stream enters any queue of said switch,
• wherein the flow identity information includes port, identified by port number, and traffic class, and,
• wherein flows are grouped together by means of a hash function into a set of flow groups, and
• wherein a counter FG (flow group) is increased with the packet length when the flow group accepts a packet, and a variable FGmax, (flow group maximum) is set to a value equal to the maximum of the FG counters for the traffic class in question, and wherein, for a flow group having the ratio FG/FGmax<a constant, a flag is set to a value used by the algorithm in deciding to accept or reject a packet, whereby the bandwidth is distributed in accordance with the Max-Min algorithm.

An arrangement for bandwidth scheduling in a switch comprising a switching fabric, and a bandwidth scheduler located before any queue of said switch, the arrangement comprising:

• means for receiving a stream of data from the switching fabric;
• means for extracting flow identity information from the stream;
• means for updating counters corresponding to the stream;
• and
• means for subjecting the stream to a decision making algorithm in the bandwidth scheduler based on the extracted flow identity information and the updated counters for that particular stream resulting in that the stream is accepted or rejected before said stream enters any queue of said switch,
• wherein the flow identity information includes port, identified by port number, and traffic class, and,
• wherein a limit (BWPmax) is set on the maximum accepted bandwidth per port, and
• wherein a virtual queue is associated with each port by means of a counter VQLP (virtual queue length of port) and the counter VQLP is increased with the packet length for each accepted packet and updated by subtracting the configuration parameter BWPmax (maximum accepted bandwidth per port) each time unit.

An arrangement for bandwidth scheduling in a switch comprising a switching fabric, and a bandwidth scheduler located before any queue of said switch, the arrangement comprising:

• means for receiving a stream of data from the switching fabric;
• means for extracting flow identity information from the stream;
• means for updating counters corresponding to the stream;
• and
• means for subjecting the stream to a decision making algorithm in the bandwidth scheduler based on the extracted flow identity information and the updated counters for that particular stream resulting in that the stream is accepted or rejected before said stream enters any queue of said switch,
• wherein the flow identity information includes port, identified by port number, and traffic class, and,
• wherein a limit (BWTCmax) is set on the minimum accepted bandwidth per traffic class, and
• wherein a virtual queue is associated with each traffic class by means of a counter VQLTC (virtual queue length per traffic class) and the counter VQLTC is increased with the packet length for each accepted packet and updated each time unit by subtracting the configuration parameter BWTCmax.

An arrangement for bandwidth scheduling in a switch comprising a switching fabric, and a bandwidth scheduler located before any queue of said switch, the arrangement comprising:

• means for receiving a stream of data from the switching fabric;
• means for extracting flow identity information from the stream;
• means for updating counters corresponding to the stream;
• and
• means for subjecting the stream to a decision making algorithm in the bandwidth scheduler based on the extracted flow identity information and the updated counters for that particular stream resulting in that the stream is accepted or rejected before said stream enters any queue of said switch,
• wherein the flow identity information includes port, identified by port number, and traffic class, and
• wherein a counter TC (traffic class) is increased with the packet length when the traffic class accepts a packet, and a variable TCPmax (traffic class port maximum) is set to a value equal to the maximum of the TC counters for the port in question, and wherein, for a traffic class having the ratio TC/TCPmax<a constant, a flag is set to a value used by the algorithm in deciding to accept or reject a packet, whereby the bandwidth is distributed in accordance with the Max-Min algorithm.

An arrangement for bandwidth scheduling in a switch comprising a switching fabric, and a bandwidth scheduler located before any queue of said switch, the arrangement comprising:

• means for receiving a stream of data from the switching fabric;
• means for extracting flow identity information from the stream;
• means for updating counters corresponding to the stream;
• and
• means for subjecting the stream to a decision making algorithm in the bandwidth scheduler based on the extracted flow identity information and the updated counters for that particular stream resulting in that the stream is accented or rejected before said stream enters any queue of said switch,
• wherein the flow identity information includes port, identified by port number, and traffic class, and
• wherein each traffic class is guaranteed a bandwidth up to a limit (BWTCmin), and
• wherein a counter TC (traffic class) is increased with the packet length when the traffic class accepts a packet and is updated each time unit by subtracting the configuration parameter BWTCmin (bandwidth per traffic class minimum).

An arrangement for bandwidth scheduling in a switch comprising a switching fabric, and a bandwidth scheduler located before any queue of said switch, the arrangement comprising:

• means for receiving a stream of data from the switching fabric;
• means for extracting flow identity information from the stream;
• means for updating counters corresponding to the stream;
• and
• means for subjecting the stream to a decision making algorithm in the bandwidth scheduler based on the extracted flow identity information and the updated counters for that particular stream resulting in that the stream is accepted or rejected before said stream enters any queue of said switch,
• wherein the flow identity information includes port, identified by port number, and traffic class, and
• wherein, for each traffic class, a counter BL (backlogging) keeps track of how many packets are accepted in relation to the other traffic classes, so that if a previously idle traffic class becomes active, the traffic class is compensated by distributing more bandwidth to this traffic class.

An arrangement for bandwidth scheduling in a switch comprising a switching fabric, and a bandwidth scheduler located before any queue of said switch, the arrangement comprising:

• means for receiving a stream of data from the switching fabric;
• means for extracting flow identity information from the stream:
• means for updating counters corresponding to the stream;
• and
• means for subjecting the stream to a decision making algorithm in the bandwidth scheduler based on the extracted flow identity information and the updated counters for that particular stream resulting in that the stream is accepted or rejected before said stream enters any queue of said switch,
• wherein the flow identity information includes port, identified by port number, and traffic class, and
• wherein, if one traffic class is particularly aggressive or active, it is forced to give up a part of its accented bandwidth, and
• wherein when a packet is accepted in a traffic class having the maximum accepted bandwidth (TC=TCPmax), a charity function forces the packet to be discarded and a counter charity (CH) is increased with a configurable fraction of the accepted packet length (+packet length×give factor), and when a packet is rejected in one of the other traffic classes, the charity function forces the packet to be accepted and the charity counter (CH) is decreased with the packet length multiplied with the weight of the respective traffic class (−packet length×WTC), and the counter (CH) is updated each time unit by multiplication with a decay factor.

An arrangement for bandwidth scheduling in a switch comprising a switching fabric, and a bandwidth scheduler located before any queue of said switch, the arrangement comprising:

• means for receiving a stream of data from the switching fabric;
• means for extracting flow identity information from the stream;
• means for updating counters corresponding to the stream;
• and
• means for subjecting the stream to a decision making algorithm in the bandwidth scheduler based on the extracted flow identity information and the updated counters for that particular stream resulting in that the stream is accepted or rejected before said stream enters any queue of said switch,
• wherein the flow identity information includes port, identified by port number, and traffic class, and wherein:
• a limit (BWPmax) is set on the maximum accepted bandwidth per port, a virtual queue is associated with each port, and a flag is set in dependence of the port queue length;
• a limit (BWTCmax) is set on the maximum accepted bandwidth per traffic class, a virtual queue is associated with each traffic class, and a flag is set in dependence of the traffic class queue length;
• the bandwidth is distributed in accordance with the Max-Min algorithm;
• each traffic class is guaranteed a bandwidth up to a limit (BWTCmin);
• a weight (WTC) is associated with each traffic class, so that the algorithm automatically prioritizes certain traffic classes;
• for each traffic class, a backlogging counter (BL) keeps track of how many packets are accepted in relation to the other traffic classes, so that if a previously idle traffic class becomes active, the traffic class is compensated by distributing more bandwidth to this traffic class;
• if one traffic class is particularly aggressive or active, it gives up a part of its accepted bandwidth.

An arrangement for bandwidth scheduling in a switch comprising a switching fabric, and a bandwidth scheduler located before any queue of said switch, the arrangement comprising:

• means for receiving a stream of data from the switching fabric:
• means for extracting flow identity information from the stream;
• means for updating counters corresponding to the stream;
• and
• means for subjecting the stream to a decision making algorithm in the bandwidth scheduler based on the extracted flow identity information and the updated counters for that particular stream resulting in that the stream is accepted or rejected before said stream enters any queue of said switch,
• wherein the flow identity information includes port, identified by port number, and traffic class, and
• wherein flows are grouped together by means of a hash function into a set of flow groups, and
• wherein a counter FG (flow group) is increased with the packet length when the flow group accepts a packet, and a variable FGmax (flow group maximum is set to a value equal to the maximum of the FG counters for the traffic class in question, and wherein, for a flow group having the ratio FG/FCmax<a constant, a flag is set to a value used by the algorithm in deciding to accept or reject a packet, whereby the bandwidth is distributed in accordance with the Max-Min algorithm.