Pipeline scheduler with fairness and minimum bandwidth guarantee
AssigneeJuniper Networks, Inc.
InventorsRuixue Fan, Chi-Yu Lu
Life of this patent
Estimating the term…
Abstract
A pipeline scheduler provides a minimum bandwidth guarantee by transporting cells from an input port to an output port in a two-phased approach. Cells that conform to a minimum cell rate (MCR) are selected from queues at the input port and arranged into supercells for transport to the output port, followed by nonconforming cells, to guarantee fairness by using scheduling modules to build the supercells first for conforming cells, and then for nonconforming cells. Reservation vectors are used to permit the same time slot of the next frame to be reserved by a first queue, and the same time slot of the following time frame to be held for reservation by a second queue, to ensure equal time slot access by the first and second queues over successive time frames.
Claims19
A non-transitory computer-readable medium comprising:
- one or more instructions which, when executed by one or more processors of a network device, cause the one or more processors to:
- receive each data unit, of a plurality of data units associated with a particular quality of service (QoS) class, at an input port of the network device,
- determine, for each data unit, of the plurality of data units, whether the data unit comprises the first type of data unit or the second type of data unit based on an amount of bandwidth available for transporting data through a network device when the data unit is received at the input port of the network device,
- buffer the plurality of data units, associated with, in a queue associated with the particular QoS class,
- determine that a predetermined number of data units comprising the first type of data unit or a predetermined number of data units comprising the second type of data unit are buffered in the queue,
- generate a request for constructing a data segment, the data segment including the predetermined number of data units comprising the first type of data unit or the predetermined number of data units comprising the second type of data unit,
- receive a grant to construct the data segment based on the request,
- construct the data segment based on the grant.
A device comprising:
- a processor to:
- receive an initial allocation of a first quantity of credits for transmitting data through the device,
- set a first variable to a first value based on the first quantity of credits,
- set a second variable to a second value based on time associated with receiving the initial allocation of the first quantity of credits,
- receive a data unit,
- determine, based on the second variable, a quantity of time slots that have occurred since receiving the initial allocation of the first quantity of credits,
- determine, based on the determined quantity of time slots, an additional quantity of credits,
- determine, based on the additional quantity of credits and the first quantity of credits, a second quantity of credits,
- set the first variable to a third value based on the second quantity of credits, and
- determine whether to transmit the received data unit through the device based on the third value.
A method comprising:
- receiving, by a network device, a first quantity of credits for transmitting data through the network device;
- determining, by the network device, a value for a first variable based on the first quantity of credits;
- determining, by the network device, a value for a second variable based on a time associated with receiving the first quantity of credits;
- receiving, by the network device, a data unit;
- determining, by the network device and based on the second variable, a quantity of time slots occurring since receiving the first quantity of credits;
- determining, by the network device and based on the determined quantity of time slots, a second quantity of credits;
- determining, by the network device and based on the second quantity of credits and the first quantity of credits, a third quantity of credits;
- setting, by the network device, the value of the first variable to a second value based on the third quantity of credits;
- and
- determining, by the network device, whether to transmit the received data unit through the network device based on the second value.
Dependencies are inferred from the claim text.