Method and apparatus for scheduling data on a medium
View Patent ↗A bandwidth guaranteeing, BW, process transmits data from a first group of queues to a medium. When none of the queues of the first group wishes to transmit data via the bandwidth guaranteeing process, a weighted fair queuing process is provided for dividing any excess bandwidth between a second group of queues. A mathematically simple WFQ process is described which may be interrupted by the BW process and resumed with the same order etc. between the queues.
1. A method of transmitting information packets from a plurality of queues into a single transmission medium, wherein the packets may have different sizes, the method comprising:
a bandwidth guaranteeing process transferring packets from one or more queues to the transmission medium in a manner so that each of those queues can obtain at least a predetermined bandwidth, and
a queuing process comprising the steps of:
1. assigning a priority to each of the queues not using the bandwidth guaranteeing process;
2. defining, for each of the queues not using the bandwidth guaranteeing process, a variable, and
3. for the queues not using the bandwidth guaranteeing process, when no queues using the bandwidth guaranteeing process transmit packets;
determining a first queue having a variable with a value fulfilling a predetermined criterion,
transmitting a packet from the first queue to the transmission medium, and
determining a new value for the variable of the first queue, the new value based on a mathematical operation using a previous value for the variable at a point in time prior to transmission of the packet and a factor scaling the priority of the first queue multiplied with a factor relating to a size of the packet transmitted from the first queue, the new value not fulfilling the predetermined criterion.
2. A method according to claim 1 , wherein the step of transmitting the data packet comprises transmitting the packet in accordance with a periodic timing signal and wherein the step of determining the new value for the first queue comprises, during transmission and for each period of the timing signal, providing a new value for the variable by performing the predetermined mathematical operation on a previous variable value and a factor scaling with the priority of the first queue.
3. A method according to claim 1 , further comprising the step of determining a bandwidth used for at least one of the queues.
4. A method according to claim 3 , further comprising the step of altering, on the basis of the bandwidth used by a queue, a parameter of the bandwidth guaranteeing process for the queue.
5. A method according to claim 3 , further comprising the step of providing information to an operator of the bandwidth used.
6. A method according to claim 1 , wherein the step of defining the variable comprises defining an integer value relating to a priority or quality of each queue.
7. An apparatus for transmitting information units or packets from a plurality of queues into a single transmission medium, wherein the units or packets may have different sizes, the apparatus comprising:
bandwidth guaranteeing means for transferring units from one or more queues to the transmission medium in a manner so that each of those queues can obtain at least a predetermined bandwidth, and
queuing means comprising:
1. means for assigning a priority to each of the queues not using the bandwidth guaranteeing process,
2. means for defining, for each of the queues not using the bandwidth guaranteeing process, a variable, and
3. means for, when no queues using the bandwidth guaranteeing process transmit packets;
determining a first queue having data and having a variable with a value fulfilling a predetermined criterion,
transmitting a packet from the first queue to the transmission medium, and
determining a new value for the variable of the first queue, the new value relating to a mathematical operation using a previous value for the variable at a point in time prior to transmission of the packet and a factor scaling the priority of the first queue multiplied with a factor relating to a size of the packet transmitted from the first queue, the new value not fulfilling the predetermined criterion.
8. An apparatus according to claim 7 , wherein the means for transmitting the data packet comprises means for transmitting the packet in accordance with a periodic timing signal and wherein the means for determining the new value for the first queue comprise means for, during transmission and for each period of the timing signal, providing a new value for the variable by performing the predetermined mathematical operation on a previous variable value and a factor scaling the priority of the first queue.
9. An apparatus according to claim 7 , further comprising means of determining a bandwidth used for at least one of the queues.
10. An apparatus according to claim 9 , further comprising means for altering, on the basis of the bandwidth used by a queue, a parameter of the bandwidth guaranteeing means for the queue.
11. An apparatus according to claim 9 , further comprising means for providing information to an operator of the bandwidth used.
12. An apparatus according to claim 7 , wherein the means for defining the variable comprises means for defining an integer value relating to a priority or quality of each queue.