Slow-start packet scheduling particularly applicable to systems including a non-blocking switching fabric and homogeneous or heterogeneous line card interfaces

• US 7,289,443 B1
• Filed: 10/10/2003
• Issued: 10/30/2007
• Est. Priority Date: 03/30/2002
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Costello, Patrick A.
• Primary Examiner(s): Pezzlo; John
• Application Number:
  US10/684,282
• Time in Patent Office: 1,481 Days
• Field of Search: 370229-231, 370/399, 370/461, 370/462, 370/395.42, 370/389, 370/412, 370/390, 370/252, 370/413, 370/428, 370/429, 455/428
• US Class Current: 370/231
• CPC Class Codes: H04L 47/15 in relation to multipoint traffic arrangements for broadcast or multicast in data networks H04L12/18
• CPC Class Codes: H04L 47/2441 relying on flow classification, e.g. using integrated services [IntServ]
• CPC Class Codes: H04L 47/26 using explicit feedback to the source, e.g. choke packets
• CPC Class Codes: H04L 47/50 Queue scheduling
• CPC Class Codes: H04L 49/201 Multicast operation; Broadcast operation
• CPC Class Codes: H04L 49/254 Centralised controller, i.e. arbitration or scheduling
• CPC Class Codes: H04L 49/506 Backpressure
• CPC Class Codes: H04L 49/508 Head of Line Blocking Avoidance
• CPC Class Codes: H04Q 2213/13003 Constructional details of switching devices
• CPC Class Codes: H04Q 2213/1302 Relay switches
• CPC Class Codes: H04Q 2213/1304 Coordinate switches, crossbar, 4/2 with relays, coupling field
• CPC Class Codes: H04Q 2213/13103 Memory
• CPC Class Codes: H04Q 2213/13106 Microprocessor, CPU
• CPC Class Codes: H04Q 2213/13109 Initializing, personal profile
• CPC Class Codes: H04Q 2213/13141 Hunting for free outlet, circuit or channel
• CPC Class Codes: H04Q 2213/13166 Fault prevention
• CPC Class Codes: H04Q 2213/13174 Data transmission, file transfer
• CPC Class Codes: H04Q 2213/13204 Protocols
• CPC Class Codes: H04Q 2213/13216 Code signals, frame structure
• CPC Class Codes: H04Q 2213/13242 Broadcast, diffusion, multicast, point-to-multipoint (1 : N)
• CPC Class Codes: H04Q 2213/13299 : Bus
• CPC Class Codes: H04Q 2213/13389 : LAN, internet
• CPC Class Codes: H04Q 3/66 : Traffic distributors

Abstract

Methods and apparatus are disclosed for slow-start scheduling packets, such as in systems having a non-blocking switching fabric and homogeneous or heterogeneous line card interfaces. In one implementation, multiple request generators, grant arbiters, and acceptance arbiters work in conjunction to determine the scheduling of packets. A set of requests for sending packets from a particular input is identified. The number of requests is possibly reduced to a value less than the number of packets that can be sent from the particular source if the particular input is not saturated. Otherwise, when the particular input is saturated, the number of requests remains the same or is reduced to the maximum number of packets that can be sent during a packet time.

Claims

1. A method, comprising:

identifying a set of requests corresponding to packets desired to be sent from a plurality of inputs across a packet switch to a particular output, the set of requests including j requests from a particular source with the ability to send k packets during a particular packet time and having a saturation level of s packets;

slow-start adjusting the value of said j to a slow-start value, wherein the slow-start value is less than said k when a number of packets corresponding to the particular source is less than said s;

maintaining a grant starting position;

determining a grant advancement position;

identifying a first n requests in a predetermined sequence starting from the grant starting position, where n is less than or equal to the maximum number of packets that can be sent in a single packet time to the particular output; and

wherein the first n requests include the slow-start value number of requests from the particular source; and

updating the grant starting position in response to the first n grants including a particular grant corresponding to the grant advancement position.

2. The method of claim 1, wherein said slow-start adjusting the value of said j to the slow-start value includes setting the slow-start value to said k when the number of packets corresponding to the particular source is greater than said s.

3. The method of claim 1, wherein said slow-start adjusting the value of said j to the slow-start value includes a division or shift operation by a predetermined value on said j when the number of packets corresponding to the particular source is less than said s.

4. The method of claim 1, wherein said slow-start adjusting the value of said j to the slow-start value includes identifying the slow-start value in a data structure based on the value of said j.

5. An apparatus, comprising:

a plurality of request generators;

a plurality of grant arbiters coupled to the plurality of request generators;

a plurality of acceptance arbiters coupled to the plurality of grant arbiters;

wherein each of the plurality of request generators is configured for generating requests for its associated input of a plurality of inputs of a switch, wherein said requests include j requests from a particular source with the ability to send k packets during a particular packet time and having a saturation level of s packets, and a request generator corresponding to the particular source of the plurality of request generators is configured to slow-start adjust the value of said j to a slow-start value, wherein the slow-start value is less than said k when a number of packets corresponding to the particular source is less than said s;

wherein each of the plurality of grant arbiters is configured for generating grants based on one or more received requests, said grants corresponding to authorization to send to its associated output of a plurality of outputs of the switch, where said generating grants includes maintaining a grant starting position, determining a grant advancement position, identifying a first n requests in a predetermined sequence starting from the grant starting position, where n is less than or equal to the maximum number of packets that can be sent in a single packet time to said associated output; and

updating the grant starting position in response to the first n grants including a particular grant corresponding to the grant advancement position; and

wherein each of the plurality of acceptance arbiters is configured for generating acceptances based on one or more received grants, said acceptances corresponding to its associated input of the plurality of inputs.

6. The apparatus of claim 5, wherein the request generator corresponding to the particular source is configured to set the slow-start value to said k when the number of packets corresponding to the particular source is greater than said s.

7. A computer-readable medium tangibly storing thereon computer-executable instructions for performing steps when executed by a computer, said steps comprising:

identifying a set of requests corresponding to packets desired to be sent from a plurality of inputs across a packet switch to a particular output, the set of requests including i requests from a particular source with the ability to send k packets during a particular packet time and having a saturation level of s packets;

slow-start adjusting the value of said j to a slow-start value, wherein the slow-start value is less than said k when a number of packets corresponding to the particular source is less than said s;

maintaining a grant starting position;

determining a grant advancement position;

identifying a first n requests in a predetermined sequence starting from the grant starting position, where n is less than or equal to the maximum number of packets that can be sent in a single packet time to the particular output; and

wherein the first n requests include the slow-start value number of requests from the particular source; and

updating the grant starting position in response to the first n grants including a particular grant corresponding to the grant advancement position.

8. The computer-readable medium of claim 7, wherein said slow-start adjusting the value of said j to the slow-start value includes setting the slow-start value to said k when the number of packets corresponding to the particular source is greater than said s.

9. The computer-readable medium of claim 7, wherein said slow-start adjusting the value of said j to the slow-start value includes a division or shift operation by a predetermined value on said j when the number of packets corresponding to the particular source is less than said s.

10. The computer-readable medium of claim 7, wherein said slow-start adjusting the value of said j to the slow-start value includes identifying the slow-start value in a data structure based on the value of said j.

11. An apparatus, comprising:

means for identifying a set of requests corresponding to packets desired to be sent from a plurality of inputs across a packet switch to a particular output, the set of requests including j requests from a particular source with the ability to send k packets during a particular packet time and having a saturation level of s packets;

means for slow-start adjusting the value of said j to a slow-start value, wherein the slow-start value is less than said k when a number of packets corresponding to the particular source is less than said s;

means for maintaining a grant starting position;

means for determining a grant advancement position;

means for identifying a first n requests in a predetermined sequence starting from the grant starting position, where n is less than or equal to the maximum number of packets that can be sent in a single packet time to the particular output; and

wherein the first n requests include the slow-start value number of requests from the particular source; and

means for updating the grant starting position in response to the first n grants including a particular grant corresponding to the grant advancement position.

12. The apparatus of claim 11, wherein said means for slow-start adjusting the value of said j to the slow-start value includes means for setting the slow-start value to said k when the number of packets corresponding to the particular source is greater than said s.

13. The apparatus of claim 11, wherein said means for slow-start adjusting the value of said j to the slow-start value includes means for performing a division or shift operation by a predetermined value on said j when the number of packets corresponding to the particular source is less than said s.

14. The apparatus of claim 11, wherein said means for slow-start adjusting the value of said j to the slow-start value includes means for identifying the slow-start value in a data structure based on the value of said j.