Pipeline scheduler with fairness and minimum bandwidth guarantee

• US 8,189,597 B2
• Filed: 08/05/2010
• Issued: 05/29/2012
• Est. Priority Date: 01/03/2001
• Status: Expired due to Fees

• Current Assignee: Juniper Networks Incorporated
• Original Assignee: Juniper Networks Incorporated
• Inventors: Fan, Ruixue, Lu, Chi-Yu
• Primary Examiner(s): PHUNKULH, BOB A
• Application Number:
  US12/851,317
• Publication Number:
  US 20100296513A1
• Time in Patent Office: 663 Days
• Field of Search: None
• US Class Current: 370/395.4
• CPC Class Codes: H04L 12/5602 Bandwidth control in ATM Networks, e.g. leaky bucket
• CPC Class Codes: H04L 2012/5651 Priority, marking, classes
• CPC Class Codes: H04L 2012/5679 Arbitration or scheduling

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.

Claims

1. A device comprising:

an input component to;

generate a request for constructing a data segment, the data segment including;

a predetermined number of aggregated first type of data units corresponding to a particular output port, or

a predetermined number of aggregated second type of data units corresponding to the particular output port; and

a scheduler component to;

receive the request for constructing the data segment, and

generate, based on receiving the request, a grant to construct the data segment including the predetermined number of aggregated first type of data units or the predetermined number of second type of data units.

2. The device of claim 1, where the input component is further to:

receive data via a network, and

partition the data into a plurality of data units.

3. The device of claim 2, where the input component is further to:

determine whether each of the plurality of data units comprise the first type of data units or the second type of data units.

4. The device of claim 1, further comprising:

a plurality of output ports, the plurality of output ports including the particular output port;

a plurality of buffers, where each of the plurality of buffers is associated with one of the plurality of output ports, and

where the input component is further to;

partition data, received via a network, into a plurality of data units,

determine an output port, of the plurality of output ports, associated with each one of the plurality of data units, and

store each data unit, of the plurality of data units, in one of the plurality of buffers associated with the determined output port.

5. The device of claim 4, where each of the plurality of buffers is further associated with one of a plurality of traffic classes, and where the input component is further to:

determine a traffic class, of the plurality of traffic classes, associated with each data unit, of the plurality of data units, and

store each data unit, of the plurality of data units, in one of the plurality of buffers associated with the determined one of the plurality of output ports and the determined traffic class associated with the data unit.

6. The device of claim 1, where the input component is further to:

receive the grant from the scheduler component, and

construct the data segment based on receiving the grant;

and where the device further comprises;

an output component that includes the particular output port, where the output component is to;

receive the data segment,

de-construct the data segment to form data units corresponding to the predetermined number of aggregated first type of data units or the predetermined number of aggregated second type of data units, and

output, via the particular output port, the data units to a network.

7. The device of claim 1, where the request for constructing the data segment identifies a status, of the data segment to be constructed, as conforming or non-conforming, and

where the predetermined number of aggregated first type of data units comprise conforming data units and the predetermined number of aggregated second type of data units comprise non-conforming data units.

8. The device of claim 7, where the scheduler component is further to:

generate the grant based on the status of the data segment.

9. A method comprising:

generating, by a network device, a request for constructing a data segment of a number of aggregated first type of data units or a number of aggregated second type of data units, the number of aggregated first type of data units or the number of aggregated second type of data units corresponding to one of a plurality of classes of traffic; and

generating, by the network device and based on generating the request, a grant to construct the data segment that includes the number of aggregated first type of data units or the number of aggregated second type of data units.

10. The method of claim 9, further comprising:

receiving data via a network; and

partitioning the data into a plurality of data units.

11. The method of claim 10, further comprising:

determining a class of traffic, of the plurality of classes of traffic, of each data unit, of the plurality of data units; and

storing, based on the determined class of traffic, each data unit, of the plurality of data units, in one of a plurality of buffers associated with the determined class of traffic of the data unit.

12. The method of claim 11, further comprising:

determining whether each data unit, of the plurality of data units, comprise a data unit of the first type or a data unit of the second type; and

where storing each data unit, of the plurality of data units, further comprises;

aggregating data units of the first type and data units of the second type within the one of a plurality of buffers associated with the determined class of traffic of the data unit.

13. The method of claim 9, further comprising:

partitioning data, received via a network, into a plurality of data units;

determining one of a plurality of output ports associated with each of the plurality of data units;

determining a class of traffic, of the plurality of classes of traffic, associated with each of the plurality of data units; and

storing, based on the determined output port and the determined class of traffic, each of the plurality of data units in one of a plurality of buffers.

14. The method of claim 13, where the data is received by one of a plurality of input ports, and where the storing is further based on the one of the plurality of input ports receiving the data.

15. A method comprising:

aggregating, by an input component of a network device, a first type of data units generated from data received at the network device, where the first type of data units are aggregated based on an input port—

output port pair associated with the first type of data units;

receiving, by the input component, a grant from a scheduler of the network device, where the grant is received in response to a request transmitted by the input component to the scheduler in response to the input component determining that a predetermined number of the aggregated first type of data units had been stored in one of a plurality of buffers of the network device;

constructing, by the input component and based on the grant, a data segment, where the constructed data segment includes a quantity of the aggregated first type of data units;

routing, by the input component, the constructed data segment to an output port corresponding to the input port—

output port pair associated with the aggregated first type of data units; and

de-constructing, by the output port, the constructed data segment into standardized data units for output to a network.

16. The method of claim 15, where the first type of data units conform to a minimum rate, and aggregating the first type of data units further comprises:

storing the first type of data units in the one of the plurality of buffers corresponding to the input port—

output port pair associated with each of the first type of data units,

incrementing a counter associated with the one of the plurality of buffers, and

determining that the predetermined number of the aggregated first type of data units are stored in the one of the plurality of buffers based on a value of the counter.

17. The method of claim 15, where the first type of data units conform to a minimum rate, the method further comprising:

transmitting another request for a grant to construct another data segment when a predetermined number of aggregated second type of data units are stored in another one of the plurality of buffers, where the second type of data units do not conform to the minimum rate.

18. The method of claim 17, where the data segment, constructed from the aggregated first type of data units, is constructed prior to constructing the other data segment.

19. The method of claim 15, where de-constructing the data segment further comprises:

generating Internet Protocol (IP) datagrams corresponding to one of a plurality of service classes for each of the standardized data units.

20. The method of claim 15, further comprising:

aggregating, by the input component, a second type of data units generated from data received at the network device, where the second type of data units are aggregated based on an input port—

output port pair associated with the second type of data units; and

constructing, by the input component and based on another grant received from the scheduler, another data segment, where the other data segment is constructed to include a number of the aggregated second type of data units and the grant was received in response to another request transmitted by the input component to the scheduler upon the input component determining that a predetermined number of the aggregated second type of data units had been stored in one of a plurality of buffers of the network device; and

routing, by the input component, the other data segment to an output port corresponding to the input port—

output port pair associated with the aggregated second type of data units.