Fair prioritized scheduling in an input-buffered switch

• US 5,517,495 A
• Filed: 12/06/1994
• Issued: 05/14/1996
• Est. Priority Date: 12/06/1994
• Status: Expired due to Term

• Current Assignee: Nokia of America Corporation (Nokia Corporation)
• Original Assignee: AT&T Corporation (AT&T, Inc.)
• Inventors: Lund, Carsten, Reingold, Nicholas F., Phillips, Steven
• Primary Examiner(s): MARCELO, MELVIN C
• Application Number:
  US08/350,347
• Time in Patent Office: 525 Days
• Field of Search: 370/60, 370/60.1, 370/85.6, 370/94.1, 370/94.2, 370/61
• US Class Current: 370/399
• CPC Class Codes: H04L 12/5601 Transfer mode dependent, e.g. ATM
• CPC Class Codes: H04L 2012/5632 Bandwidth allocation
• CPC Class Codes: H04L 2012/5649 Cell delay or jitter
• CPC Class Codes: H04L 2012/5651 Priority, marking, classes
• CPC Class Codes: H04L 2012/5679 Arbitration or scheduling
• CPC Class Codes: H04L 2012/5681 Buffer or queue management
• CPC Class Codes: H04L 49/1576 Crossbar or matrix
• CPC Class Codes: H04L 49/3081 ATM peripheral units, e.g. policing, insertion or extraction

Abstract

A Fair Arbitrated Round Robin (FARR) method is disclosed for scheduling the crossbar of an input-buffered asynchronous transfer mode (ATM) switch using an arbiter. Per-virtual-circuit queuing of ATM cells is performed.

Claims

1. An apparatus for scheduling input buffers of fixed size packet switches, including asynchronous transfer mode (ATM) switches, having input and output ports, the apparatus comprising:

a plurality of input buffers having associate virtual circuits for receiving the arriving cells, each input buffer associated with a respective input port;

a cell switching fabric for processing the received cells from the input buffers to the output ports; and

a scheduling control circuit which uses timestamps associated with the virtual circuits for controlling the processing of the received cells through the cell switching fabric using fair arbitration round robin (FARR) to allow each virtual circuit to receive a fair share of bandwidth.

10. The apparatus of claim 1 wherein the scheduling control circuit pre-selects at each input buffer a respective virtual circuit for each output port.

11. The apparatus of claim 1 further comprising:

means for pre-selecting at each input buffer a respective virtual circuit for each output port; and

means for performing request processing to send a respective timestamp associated with each pre-selected virtual circuit to the scheduling control circuit.

12. The apparatus of claim 1 further comprising:

an arbiter unit operating a FARR program to process the received cells.

13. The apparatus of claim 1 further comprising:

the scheduling control circuit which uses the timestamps to generate a matching of input buffers to output ports, wherein each unmatched output buffer is associated with a respective input buffer as an unmatched input buffer;

means for pre-selecting at each input buffer a virtual circuit for each output port;

means for performing request processing on at least one request to send a timestamp associated with each pre-selected virtual circuit to the scheduling control circuit;

means for granting, for each unmatched output port, the request having a minimum timestamp;

means for accepting, for each unmatched input buffer, the granted request with a minimum timestamp; and

means for incorporating the accepted granted request in the matching.

14. The apparatus of claim 1 further comprising:

a central arbiter using the timestamps to fairly arbitrate between input buffers in an input-buffered switch.

15. The apparatus of claim 1 further comprising:

a central arbiter using the timestamps to fairly arbitrate between ports in an input-buffered switch.

16. The apparatus of claim 1 further comprising:

a central arbiter using the timestamps to fairly arbitrate between the virtual circuits in an input-buffered switch.

2. An apparatus for scheduling input buffers of fixed size packet switches, including asynchronous transfer mode (ATM) switches, having input ad output ports, the apparatus comprising:

a plurality of input buffers for receiving arriving cells, each input buffer is associated with a respective input port and includes a service list associated with each priority level for each output port;

a cell switching fabric for processing the received cells from the input buffers to the output ports;

a plurality of queues, each queue associated with a virtual circuit connecting the input buffer with at least one output port and having an associated timestamp; and

a scheduling control circuit which uses the timestamps to generate a matching of input buffers to output ports to control the processing of the received cells through the cell switching fabric using a fair arbitration round robin (FARR) program.

17. The apparatus of claim 2 wherein the scheduling control circuit pre-selects at each input buffer the virtual circuit for each output port.

18. The apparatus of claim 2 further comprising:

means for pre-selecting at each input buffer the virtual circuit for each output port; and

means for performing request processing to send a respective timestamp associated with each pre-selected virtual circuit to the scheduling control circuit.

19. The apparatus of claim 2 further comprising:

an arbiter unit operating the FARR program to process the received cells.

20. The apparatus of claim 2 further comprising:

means for performing request processing on at least one request to send a timestamp associated with each circuit to the scheduling control circuit;

means for granting, for each unmatched output port, the request having a minimum timestamp;

means for accepting, for each unmatched input buffer, the granted request with a minimum timestamp; and

means for incorporating the accepted granted request in the matching.

21. The apparatus of claim 2 further comprising:

a central arbiter using the timestamps to fairly arbitrate between input buffers in an input-buffered switch.

22. The apparatus of claim 2 further comprising:

a central arbiter using the timestamps to fairly arbitrate between ports in an input-buffered switch.

23. The apparatus of claim 2 further comprising:

a central arbiter using the timestamps to fairly arbitrate between the virtual circuits in an input-buffered switch.

3. A method for scheduling input buffers of fixed size packet switches, including asynchronous transfer mode (ATM) switches, having input and output ports, the method comprising the steps of:

receiving cells in the input buffers;

pre-selecting at each input buffer a virtual circuit for each output port;

performing request processing to send a timestamp associated with each pre-selected virtual circuit to a scheduling control circuit;

generating a matching of the input buffers to the output ports from the scheduling control circuit using the timestamps; and

processing the received cells through a cell switching fabric to the output ports using the matching.

4. The method of claim 3 wherein the step of matching includes the step of using an arbiter unit operating a fair arbitration round robin (FARR) program.

5. The method of claim 3 wherein the step of generating a matching includes the steps of:

granting, for each unmatched output port, the request having a minimum timestamp;

accepting, for each unmatched input buffer, the granted request with a minimum timestamp; and

incorporating the accepted granted request in the matching.

6. The method of claim 5 wherein the steps of granting requests, accepting granted requests, and incorporating the accepted granted requests are performed for a predetermined number of rounds.

7. The method of claim 3 including the step of using timestamps and a central arbiter to fairly arbitrate between input buffers in an input-buffered switch.

8. The method of claim 3 including the step of using timestamps and a central arbiter to fairly arbitrate between ports in an input-buffered switch.

9. The method of claim 3 including the step of using timestamps and a central arbiter to fairly arbitrate between virtual circuits in an input-buffered switch.