Method and apparatus for scheduling cells in an input-queued switch

• US 5,500,858 A
• Filed: 12/20/1994
• Issued: 03/19/1996
• Est. Priority Date: 12/20/1994
• Status: Expired due to Term

• Current Assignee: Regents of the University of California (University of California)
• Original Assignee: Regents of the University of California (University of California)
• Inventors: McKeown, Nicholas W.
• Primary Examiner(s): Olms, Douglas W.
• Assistant Examiner(s): TON, DANG T
• Application Number:
  US08/359,890
• Time in Patent Office: 455 Days
• Field of Search: 370/60, 370/60.1, 370/94.1, 370/185.6, 370/85.13, 370/91.1, 370/95.3, 370/61, 370/63, 370/64, 370/65.5, 370/68, 370/112, 370/68.1, 370/61, 340/825.5, 340/825.51, 340/825.52
• US Class Current: 370/412
• 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/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 2012/5682 Threshold; Watermark
• CPC Class Codes: H04L 49/106 using space switching, e.g. crossbar or matrix
• 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 high-bandwidth input-queued switch includes a set of input queues, a rotating priority iterative matching desynchronizing scheduler, and a crossbar switch. Each input queue includes at least one stored cell with an output device designation signal and a data signal. Each output device designation signal is processed by the rotating priority iterative matching desynchronizing scheduler so that the data signal associated with the output device designation signal is routed through the crossbar switch to an output device specified by the output device designation signal. The rotating priority iterative matching desynchronizing scheduler includes a set of grant scheduler units, each of which receives a set of device designation signals and generates an input device grant signal on the basis of a grant scheduler priority designation signal. The scheduler also includes a set of accept scheduling units, each of which receives a set of input device grant signals from the grant scheduling units, and generates a input/output match signal on the basis of an accept scheduler priority designation signal. Each grant scheduling unit includes a grant scheduler register that stores the grant scheduler priority designation signal. The grant scheduler priority designation signal is incremented when an input device grant signal results in an input/output match signal at one of the accept scheduler units. Each accept scheduler unit includes an accept scheduler register that stores the accept scheduler priority designation signal. The accept scheduler priority designation signal is incremented when the input/output match signal is selected.

Claims

1. A switch of the type that includes a set of input queues, each of said input queues including at least one stored cell with an output device designation signal and a data signal, said output device designation signals of said stored cells being routed to a request delivery circuit that conveys said output device designation signals to a set of grant scheduler units, each grant scheduler unit corresponding to an output device specified by one or more of said output device designation signals, each of said grant scheduler units arbitrating between a set of received output device designation signals and generating an input device grant signal, said input device grant signals from said grant scheduler units being conveyed to a grant delivery circuit that conveys said input device grant signals to a set of accept scheduler units, each accept scheduler unit arbitrating between a set of received input device grant signals and selecting an input/output match signal, said input/output match signal being processed by a switching device that connects a selected stored cell in said set of input queues with an output device specified by said output device designation signal of said selected stored cell, the improvement comprising:

a set of rotating priority grant scheduler units, each of said rotating priority grant scheduler units producing a selected input device grant signal from said set of output device designation signals according to a grant scheduler priority designation signal; and

a set of rotating priority accept scheduler units, each of said rotating priority accept scheduler units producing an input/output match signal from said set of received input device grant signals according to an accept scheduler priority designation signal;

wherein said rotating priority grant scheduler units each include a grant scheduler register that stores said grant scheduler priority designation signal, said grant scheduler priority designation signal being revised when said selected input device grant signal results in an input/output match signal at one of said rotating priority accept scheduler units; and

wherein said rotating priority accept scheduler units each include an accept scheduler priority designation register that stores said accept scheduler priority designation signal, said accept scheduler priority designation signal being updated when said input/output match signal is selected.

2. The apparatus of claim 1 wherein each of said rotating priority grant scheduler units includes a request vector register for storing said output device designation signals.

3. The apparatus of claim 2 wherein each of said rotating priority grant scheduler units includes a priority encoder connected to said request vector register and said grant scheduler register, said priority encoder processing said output device designation signals from said request vector register and said grant scheduler priority designation signal from said grant scheduler register to produce said selected input device grant signal.

4. The apparatus of claim 3 wherein each of said rotating priority grant scheduler units includes a decoder connected to said priority encoder to process said selected input device grant signal.

5. The apparatus of claim 4 wherein each of said rotating priority grant scheduler units includes an incrementer connected to said priority encoder to increment said selected input device grant signal to produce an incremented grant signal.

6. The apparatus of claim 5 wherein each of said rotating priority grant scheduler units includes an incremented value register connected to said incrementer to store said incremented grant signal.

7. The apparatus of claim 6 wherein said incremented value register is connected to said grant scheduler register, said incremented value register writing said incremented grant signal into said grant scheduler register in response to an acceptance feedback signal, thereby revising said grant scheduler priority designation signal.

8. A method of operating a switch of the type that includes a set of input queues, each of said input queues including at least one stored cell with an output device designation signal and a data signal, said output device designation signals of said stored cells being routed to a request delivery circuit that conveys said output device designation signals to a set of grant scheduler units, each grant scheduler unit corresponding to an output device specified by one or more of said output device designation signals, each of said grant scheduler units arbitrating between a set of received output device designation signals and generating an input device grant signal, said input device grant signals from said grant scheduler units being conveyed to a grant delivery circuit that conveys said input device grant signals to a set of accept scheduler units, each accept scheduler unit arbitrating between a set of received input device grant signals and selecting an input/output match signal, said input/output match signal being processed by a switching device that connects a selected stored cell in said set of input queues with an output device specified by said output device designation signal of said selected stored cell, the method comprising the steps of:

(a) selecting an input device grant from said set of output device designation signals according to a grant scheduler priority designation signal;

(b) choosing an input/output match from said set of received input device grant signals according to an accept scheduler priority designation signal;

(c) revising said grant scheduler priority designation signal when said input device grant signal results in an input/output match signal at one of said rotating priority accept schedulers; and

(d) updating said accept scheduler priority designation signal when said input/output match signal is selected.

9. The method of claim 8 further comprising the step of repeating steps (a) through (d) until a time slot period associated with said input queued switch is expired.

10. The method of claim 9 further including the step of (e) removing committed scheduling units before repeating steps (a) through (d).

11. A switch, comprising:

a set of input queues, with each input queue including a stored cell with an output device designation signal and a data signal;

a scheduler unit, including

a grant scheduler priority designation register to store a grant scheduler priority designation signal,

an accept scheduler priority designation register to store an accept scheduler priority designation signal, and

a processing circuit to

compare said grant scheduler priority designation signal with a set of output device designation signals derived from said stored cells of said input queues to produce a selected input device grant signal, and

compare said accept scheduler priority designation signal with a set of input device grant signals, including said selected input device grant signal, to produce an input/output match signal;

a priority revision circuit to

revise said grant scheduler priority designation signal when said processing circuit selects said input/output match signal from said selected input device grant signal,

update said accept scheduler priority designation signal when said input/output match signal is produced; and

a switch to process said input/output match signal such that a stored cell in said set of input queues is connected with an output device specified by said output device designation of said stored cell.

12. The apparatus of claim 11 wherein said scheduler unit includes a request vector register for alternately storing said set of output device designation signals and said set of input device grant signals.

13. The apparatus of claim 12 wherein said scheduler includes a selection circuit for selecting said grant scheduler priority designation signal from said grant scheduler designation register or said accept scheduler priority designation signal from said accept scheduler priority designation register.

14. The apparatus of claim 13 wherein said scheduler unit includes a priority encoder connected to said request vector register and said grant scheduler designation register to process said output device designation signals from said request vector register and said grant scheduler priority designation signal from said grant scheduler register to produce said selected input device grant signal.

15. The apparatus of claim 14 wherein said scheduler unit includes a decoder connected to said priority encoder to process said selected input device grant signal.

16. The apparatus of claim 15 wherein said scheduler unit includes an incrementer connected to said priority encoder to increment said selected input device grant signal to produce an incremented grant signal.

17. The apparatus of claim 16 wherein said scheduler unit includes a first incremented value register connected to said incrementer to store said incremented grant signal.

18. The apparatus of claim 17 wherein said incremented value register is connected to said grant scheduler register, said incremented value register writing said incremented grant signal into said grant scheduler register in response to an acceptance feedback signal, thereby revising said grant scheduler priority designation signal.

19. The apparatus of claim 13 wherein said scheduler unit includes a priority encoder connected to said request vector register and said accept scheduler designation register to process said set of input device grant signals stored within said request vector register and said grant scheduler priority designation signal from said grant scheduler register to produce said input/output match signal.

20. The apparatus of claim 19 wherein said scheduler unit includes a decoder connected to said priority encoder to process said input/output match signal.

21. The apparatus of claim 20 wherein said scheduler unit includes an incrementer connected to said priority encoder to increment said input/output match signal to produce an incremented input/output match signal.

22. The apparatus of claim 16 wherein said scheduler unit includes a second incremented value register connected to said second incrementer to store said incremented input/output match signal.

23. The apparatus of claim 22 wherein said second incremented value register is connected to said accept scheduler register, said second incremented value register writing said incremented input/output match signal into said accept scheduler register in response to said input/output match signal, thereby revising said accept scheduler priority designation signal.