Method and apparatus for request/grant priority scheduling

• US 7,602,797 B2
• Filed: 10/02/2003
• Issued: 10/13/2009
• Est. Priority Date: 10/02/2003
• Status: Expired due to Fees

• Current Assignee: WSOU Investments, LLC (WSOU Holdings, LLC)
• Original Assignee: Alcatel-Lucent SA (Nokia Corporation)
• Inventors: Robotham, Robert Elliott
• Primary Examiner(s): Pham, Chi H
• Assistant Examiner(s): Faroul, Farah
• Application Number:
  US10/677,842
• Publication Number:
  US 20050073951A1
• Time in Patent Office: 2,203 Days
• Field of Search: 370/412, 370/414, 370/416, 370/418, 370/468, 370/395.4, 370/230, 370/230.1, 370/236, 370/229, 370/386, 370/389, 370/392, 370/419, 370/231
• US Class Current: 370/412
• CPC Class Codes: H04L 49/205 Quality of Service based
• CPC Class Codes: H04L 49/254 Centralised controller, i.e. arbitration or scheduling
• CPC Class Codes: H04L 49/30 Peripheral units, e.g. input or output ports
• CPC Class Codes: H04L 49/3045 Virtual queuing

Abstract

In accordance with at least one embodiment of the present invention, a method and apparatus for scheduling traffic in a communications node is provided. Line cards request communication opportunities from a switch fabric. The switch fabric issues grants for such communication opportunities in response to specific requests. By dynamically adjusting usage of such communication opportunities corresponding to such grants among requests of differing priorities and/or latency criteria, embodiments of the present invention are able to provide increased capacity utilization of switching fabric bandwidth while maximizing adherence to priority requirements and/or latency criteria.

Claims

1. A method for scheduling traffic in a communications node having a plurality of line cards coupled to a switch fabric, the method comprising the steps of:

a) sending, to the switch fabric by a first line card of the line cards, a first request for transmitting a first unit of the traffic of a first priority to the switch fabric, the first request indicating a first output port for which the first unit of the traffic is destined; and

b) using, by the first line card, a first grant received from the switch fabric permitting transmission of the first unit of the traffic to the switch fabric and issued in response to a second request made for a second unit of the traffic having a second priority lower than the first priority and being destined to the first output port, for scheduling transmission of the first unit of the traffic to the switch fabric.

2. The method of claim 1 further comprising the step of:

using a second grant issued in response to the first request for scheduling transmission of the second unit of the traffic to the switch fabric.

3. The method of claim 1 wherein the first priority and the second priority are selected from a plurality of priorities corresponding to a respective plurality of service classes.

4. The method of claim 1 wherein the first line card sends the first request after the second request.

5. The method of claim 1 wherein the first line card sends a first set of requests of a highest priority of a plurality of priorities, with the first set of requests corresponding to a first quantity of the traffic in an amount of guaranteed traffic flow serviced by the first line card, and sends a second set of requests of a lower priority of the priorities for a second quantity of the traffic.

6. The method of claim 1 wherein the using, by the first line card, the first grant comprises:

performing grant substitution.

7. Apparatus for scheduling traffic in a communications node having a plurality of line cards coupled to a switch fabric comprising:

a first line card of the plurality of line cards, the first line card configured to send requests for transmitting units of the traffic of specified priorities to the switch fabric and to receive grants permitting transmission of the units of the traffic to switch fabric, the first line card further configured to utilize a first grant of the grants corresponding to a first request of the requests, wherein the first request is of a lower priority than a second request of the requests, for transmitting a first unit of the traffic corresponding to the second request to the switch fabric.

8. The apparatus of claim 7 wherein the first line card is further configured to utilize the first grant for transmitting the first unit of the traffic to conform to a latency criterion pertaining to a first data stream comprising the first unit of the traffic.

9. The apparatus of claim 7 wherein the first line card is further configured to utilize a second grant of the grants corresponding to the second request for transmitting a second unit of traffic corresponding to the first request to the switch fabric.

10. The apparatus of claim 9 wherein the first line card is further configured to issue the first request prior to the second request.

11. Apparatus for scheduling traffic in a communications node having a plurality of line cards coupled to a switch fabric comprising:

a first line card of the plurality of line cards, the first line card further comprising;

a first means configured to send requests for transmitting units of the traffic of specified priorities to the switch fabric and to receive grants permitting transmission of the units of the traffic to switch fabric; and

a second means configured to utilize a first grant of the grants corresponding to a first request of the requests, wherein the first request is of a lower priority than a second request of the requests, for transmitting a first unit of the traffic corresponding to the second request to the switch fabric.

12. The apparatus of claim 11 wherein the second means is further configured to utilize the first grant for transmitting the first unit of the traffic to conform to a latency criterion pertaining to a first data stream comprising the first unit of the traffic.

13. The apparatus of claim 11 wherein the second means is further configured to utilize a second grant of the grants corresponding to the second request for transmitting a second unit of traffic corresponding to the first request to the switch fabric.

14. The apparatus of claim 13 wherein the first means is further configured to issue the first request prior to the second request.