Packet scheduling scheme for improving short time fairness characteristic in weighted fair queueing

A packet scheduling apparatus, comprising:

• a plurality of packet queues to which weights for packet output purpose can be assigned independently;
• a packet input unit which inputs received packets into prescribed ones of the packet queues;
• a counter unit which holds counter values indicating an amount of packets currently transmittable by each packet queue;
• a scheduling unit which holds scheduling information to be used for outputting packets held in the packet queues, and selects an output packet queue from which a top packet is to be outputted according to the scheduling information;
• and
• a packet output unit which outputs a top packet from the output packet queue selected by the scheduling unit;
• wherein the scheduling unit has first and second scheduling queues for holding the scheduling information corresponding to top packets of non-empty packet queues;
• the first scheduling queue holds the scheduling information of those packet queues for which a value obtained by subtracting a packet length of a top packet from a corresponding counter value is greater than or equal to 0, while the second scheduling queue holds the scheduling information of those packet queues for which a value obtained by subtracting a packet length of a top packet from a corresponding counter value is less than 0;
• the scheduling unit takes out one scheduling information from the first scheduling queue, at a time of packet output;
• the scheduling unit sets a value of a corresponding weight to a corresponding counter value, if the output packet queue becomes empty as a result of said packet output;
• the scheduling unit decrements a corresponding counter value as much as a packet length of a packet outputted by said packet output, if the output packet queue does not become empty as a result of said packet output and the scheduling information for a new top packet of the output packet queue resulting from said packet output is to be entered into the first scheduling queue;
• the scheduling unit increments a corresponding counter value as much as a value of a corresponding weight, if the output packet queue does not becomes empty as a result of said packet output and the scheduling information for a new top packet of the output packet queue resulting from said packet output is to be entered into the second scheduling queue;
• and
• the scheduling unit switches the first scheduling unit and the second scheduling unit, if the first scheduling queue becomes empty as a result of said packet output.

A packet scheduling method, comprising the steps of:

• holding packets in a plurality of packet queues by inputting arrived packets into the packet queues and entering a scheduling information for each arrived packet into a scheduler while inputting each arrived packet into one of the packet queues;
• sequentially selecting an output packet queue from the packet queues at the scheduler, according to a prescribed criterion based on an amount of packets currently transmittable by each packet queue, such that the output packet queue is selected to be different from a previously selected output packet queue when there are more than one packet queues that satisfy the prescribed criterion, wherein the scheduler has two scheduling queues and selects one scheduling queue as a current round scheduling queue for holding the scheduling information for packets held in those packet queues which are currently capable of transmitting packets according to the prescribed criterion while using another scheduling queue as a next round scheduling queue for holding the scheduling information for packets held in those packet queues which are currently not capable of transmitting packets, so that the scheduler takes out one scheduling information from the current round scheduling queue and selects the output packet queue according to the scheduling information at a time of packet output;
• and
• outputting a top packet from the output packet queue sequentially selected by the scheduling step.

A computer usable medium having computer readable program codes embodied therein for causing a computer to function as a scheduler of a packet scheduling apparatus having a plurality of packet queues for holding packets, an input unit for inputting arrived packets into the packet queues, and an output unit for outputting a top packet from one packet queue, the computer readable program codes including:

• a first computer readable program code for causing said computer to judge whether each packet queue satisfies a prescribed criterion based on an amount of packets currently transmittable by each packet queue;
• and
• a second computer readable program code for causing said computer to sequentially select an output packet queue from the packet queues according to the judgement made by the first computer readable program code such that the output packet queue is selected to be different from a previously selected output packet queue when there are more than one packet queues that satisfy the prescribed criterions;
• wherein the input unit enters a scheduling information for each arrived packet into the scheduler while inputting each arrived packet into one of the packet queues, and the second computer readable program code uses two scheduling queues and selects one scheduling queue as a current round scheduling queue for holding the scheduling information for packets held in those packet queues which are currently capable of transmitting packets according to the prescribed criterion while using another scheduling queue as a next round scheduling queue for holding the scheduling information for packets held in those packet queues which are currently not capable of transmitting packets, so that the second computer readable program code takes out one scheduling information from the current round scheduling queue and selects the output packet queue according to the scheduling information at a time of packet output.