US5500858A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for scheduling cells in an input-queued switch
Assignee: University of California
•
Filing: 1994-12-20
•
Granted: 1996-03-19
•
Expires: 2014-12-20
Abstract
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.
Inventors
- 👤 Nicholas W. McKeown
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-29 21:53
CPC Classifications
H; H04; H04L; H04L12/00; H04L12/54; H04L12/56; H04L12/5601; H04L49/00; H04L49/10; H04L49/104; H04L49/105; H04L49/106; H04L49/15; H04L49/1553; H04L49/1576; H04L49/30; H04L49/3081; H04L2012/5629; H04L2012/5631; H04L2012/5632; H04L2012/5638; H04L2012/5646; H04L2012/5651; H04L2012/5678; H04L2012/5679; H04L2012/5681; H04L2012/5682
Claims Analysis
Total Claims: 26
Claim 1
Independent Claim
366 words
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.
Claim 2
Dependent Claim
366 words
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.
Claim 3
Dependent Claim
26 words
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.
Claim 4
Dependent Claim
63 words
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.
Claim 5
Dependent Claim
30 words
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.
Claim 6
Dependent Claim
36 words
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.
Claim 7
Dependent Claim
29 words
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.
Claim 8
Dependent Claim
46 words
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.
Claim 9
Independent Claim
293 words
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.
Claim 10
Independent Claim
293 words
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.
Claim 11
Dependent Claim
28 words
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.
Claim 12
Dependent Claim
21 words
The method of claim 9 further including the step of (e) removing committed scheduling units before repeating steps (a) through (d).
Claim 13
Dependent Claim
202 words
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.
Claim 14
Dependent Claim
202 words
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.
Claim 15
Dependent Claim
32 words
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.
Claim 16
Dependent Claim
40 words
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.
Claim 17
Dependent Claim
57 words
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.
Claim 18
Dependent Claim
25 words
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.
Claim 19
Dependent Claim
31 words
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.
Claim 20
Dependent Claim
25 words
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.
Claim 21
Dependent Claim
46 words
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.
Claim 22
Dependent Claim
58 words
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.
Claim 23
Dependent Claim
23 words
The apparatus of claim 19 wherein said scheduler unit includes a decoder connected to said priority encoder to process said input/output match signal.
Claim 24
Dependent Claim
30 words
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.
Claim 25
Dependent Claim
27 words
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.
Claim 26
Dependent Claim
49 words
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.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1999-03-19 | 1999-09-18 | 2000-03-19 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-03-19 | 2003-09-18 | 2004-03-19 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-03-19 | 2007-09-18 | 2008-03-19 | $7700.00 | Window Closed / Lapsed |