Methods and apparatus for fair queuing over a network

A queue selection method for data transfer of packets of any length over a network having a system bandwidth, comprising:

• providing a plurality of queues to hold data to be transferred over the network, each of the plurality of queues being associated with a bandwidth integer, each of the plurality of queues having a bandwidth less than the system bandwidth, and the sum of the bandwidths for each of the plurality of queues is less than or equal to a maximum system bandwidth integer;
• determining the plurality of queues that are enabled;
• determining an allocated bandwidth integer from the bandwidth integers of the plurality of queues that are enabled;
• precomputing a set of varying time increment amounts;
• incrementing a virtual time by one of said pre-computed amounts while at least one of the plurality of queues is enabled;
• selecting one of the plurality of queues based on the virtual time;
• and
• outputting a packet of any length from the selected one of the plurality of queues, whereby said selected queue is selected in a computationally efficient manner.

A queue selection apparatus for transferring data packets of any length, said apparatus comprising:

• a plurality of queues for holding data packets to be transferred over a network, each of the plurality of queues being associated with a bandwidth amount, each of the plurality of queues having a bandwidth that is less than a system bandwidth, and the sum of the bandwidth amounts for each of the plurality of queues is less than about a maximum system bandwidth integer;
• an allocated bandwidth computer for calculating an allocated bandwidth from the bandwidth amounts associated with each of the plurality of queues that are enabled, and for precomputing a set of varying time increment amounts;
• a virtual time computer for incrementing a virtual time by one of said pre-computed amounts while at least one of the plurality of queues is enabled;
• a queue selection computer for selecting one of the plurality of queues based on the virtual time;
• and
• an output port for outputting data packets of any length from the selected one of the plurality of queues, whereby said selected queue is selected in a computationally efficient manner.

A method for selecting a queue for data transfer over a network, said method comprising:

• providing a plurality of queues available for data transfer, each queue being associated with a queue virtual time and arranged to accept packets of any length;
• pre-computing a set of varing time increments;
• incrementing a first queue virtual time of a first queue by reference to a first one of said pre-computed time increments;
• selecting one of said queues for data transfer based upon a comparison of the queue virtual times of said queues;
• and
• outputting a packet of data of any length from said selected queue over a network, whereby said selected queue is selected for data transfer in a computationally efficient manner.

A queue selection apparatus comprising:

• a plurality of queues available for data transfer, each queue being associated with a queue virtual time and arranged to accept packets of any length;
• a computer for precomputing a set of varying time increments;
• a queue virtual time computer that increments a first queue virtual time of a first queue by reference to one of a plurality of pre-computed time increments;
• a queue selection computer that selects one of said queues for data transfer based upon a comparison of the queue virtual times of said queues;
• and
• an output port that outputs a packet of data of any length from said selected queue over a network, whereby said selected queue is selected for data transfer in a computationally efficient manner.

A queue selection apparatus comprising:

• a plurality of queues for holding data to be transferred over a network, each of said queues being associated with a bandwidth amount and each having a bandwidth that is less than a system bandwidth, and wherein the sum of the bandwidth amounts for each of said queues is less than about a maximum system bandwidth integer;
• a virtual time increment array that stores a plurality of pre-computed amounts;
• an allocated bandwidth computer for calculating an allocated bandwidth from the bandwidth amounts associated with each of said queues that are enabled, said allocated bandwidth being mapped to a specific pre-computed amount in said virtual time increment array;
• a system virtual time computer that increments a system virtual time for each cycle of a system clock;
• a queue virtual time computer that increments a queue virtual time by a pre-computed amount for each cycle of a system clock for one of said queues while at least one of said queues is enabled, said pre-computed amount being retrieved from said virtual time increment array by said queue virtual time computer, said incrementing being performed for each cycle of said system clock while outputting data is in progress;
• a queue selection computer for selecting one of said queues based on said queue virtual time;
• an output port for outputting data from said selected queue;
• and
• wherein said plurality of pre-computed amounts stored in said virtual time increment array are determined in accordance with the following equation:
• C*(100/(u*i)), where i.epsilon.[1 . . . 100/u]
• wherein C is a constant, i and u are integers, and where i is an integer representing an index to said virtual time increment array and u is a unit of bandwidth allocation that is a percentage of said system bandwidth.