Scheduler implementing weighted fair queuing by a weight limited first in-first out methodology
AssigneeNortel Networks Limited
InventorsJohn Pillar, Bernard Marchand, Jacob Guttman, Sitaram Patro
Life of this patent
Estimating the term…
Abstract
Scheduler methods and apparatus utilize a weight limited FIFO (WLF) method to provide weighted per-connection queuing while maximizing preservation of cell arrival order, thus minimizing additional cell delay variation (CDV) added during scheduling. The invention minimizes additional CDV of a connection until the connection exceeds its fair share of resource utilization.
Claims32
A method of scheduling a plurality of data flows within a class of service for digital traffic over a limited bandwidth outgoing datapath, comprising the steps of:
- establishing a first in-first out (FIFO) order for scheduling of data flow through a single common queue feeding said datapath;
- limiting access by each of a plurality of connections to said single common queue when a number of cells in said single common queue belonging to said connection has reached an integer weight value for said connections;
- and
- storing an overflow of data from said connections in a per connection queue.
A scheduler for a digital link system which schedules a plurality of data flows over a limited bandwidth outgoing datapath and within a class of service for digital traffic, comprising:
- a single common queue configured as a FIFO queue;
- and
- a per connection queue coupled to said single connection queue and configured to receive an overflow of data from said single connection queue, wherein said overflow includes data transmitted from said connections to said single connection queue in excess of an integer weight value for said connections.
A scheduler for a digital link system which schedules a plurality of data flows over a limited bandwidth outgoing datapath and within a class of service for digital traffic, comprising:
- queuing means for sending data transmitted from a connection on a FIFO basis;
- and
- storage means coupled to said queuing means, for receiving an overflow of data from said queuing means, said overflow including data transmitted from one of a plurality of connections to said queuing means in excess of an integer weight value for said one connection.
An intra-class, per connection weighted fair queuing apparatus, comprising
- a plurality of connections each configured to transmit cells of data;
- a single, common queue having subscribed bandwidth;
- an intra-class scheduler configured to allocate shares of the subscribed bandwidth that is available in the single, common queue to the plurality of connections so that each of the connections is allotted a respective share of the subscribed bandwidth, the single;
- and
- a per-connection queue, the connections being configured to transmit at least one cell of data to the single, common queue that, in an aggregate amount, take up at most the respective share of the subscribed bandwidth and to transmit to the per-connection queue at least one further cell of data, if any, that, when added to the aggregate, exceed the respective share of the subscribed bandwidth available, the common queue being configured to accommodate the at least one cell of data, the per-connection queue being configured to accommodate the at least one further cell of data and to transmit the at least one further cell of data to the single, common queue after waiting until the respective share of the subscribed bandwidth becomes available that corresponds to the connection from which the at least one further cell of data was transmitted.
A method of intra-class, per connection weighted fair queuing, comprising
- allocating shares of subscribed bandwidth that is available in a single, common queue to a plurality of connections so that each of the connections is allotted a respective share of the subscribed bandwidth,
- transmitting at least one cell of data from at least one of the plurality of connections to the single, common queue that, in an aggregate amount, take up at most the respective share of the subscribed bandwidth;
- accommodating the at least one cell of data by the single, common queue;
- transmitting at least one further cell of data from the at least one of the plurality of connections to a per-connection queue that, when added to the aggregate, exceed the respective share of the subscribed bandwidth;
- accommodating the at least one further cell of data in the per-connection queue;
- waiting until the respective share of the subscribed bandwidth becomes available that corresponds to the connection from which the at least one further cell of data was transmitted;
- and
- after the waiting, transmitting the at least one further cell of data to the single, common queue from the per-connection queue.
Dependencies are inferred from the claim text.