Patent CA858212A successfully refreshed from Google Patents.
Patent US6044061A successfully refreshed from Google Patents.
US6044061A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for fair and efficient scheduling of variable-size data packets in an input-buffered multipoint switch
Assignee: Riverstone Networks Inc
•
Filing: 1998-03-10
•
Granted: 2000-03-28
•
Expires: 2018-03-10
Abstract
Abstract An input-buffered multipoint switch having input channels and output channels includes multi-level request buffers, a data path multiplexer, and a scheduler. The switch has a distinct multi-level request buffer associated with each input channel and each request buffer has multiple request registers for storing data cell transfer requests of different priorities. The multi-level request registers are linked in parallel to the scheduler to allow arbitration among requests of different input channels and different priority levels. The preferred arbitration process involves generating masks that reflect the output channels required by the same priority level requests. Utilizing masks to arbitrate between multiple requests in an input-buffered switch reduces arbitration cycle time and minimizes HOL blocking.
Inventors
- 👤 Gunes Aybay
- 👤 Philip Arnold Ferolito
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 01:43
CPC Classifications
H; H04; H04L; H04L49/00; H04L49/50; H04L49/505; H04L49/508; H04L49/15; H04L49/1553; H04L49/1576; H04L49/20; H04L49/201; H04L49/203; H04L49/25; H04L49/253; H04L49/254; H04L49/35; H04L49/351; H04L49/352; H04L49/60; H04L49/608; H04L12/00; H04L12/54; H04L12/56; H04L12/5601; H04L2012/5638; H04L2012/5646; H04L2012/5651; H04L2012/5678; H04L2012/5679; H04L49/30; H04L49/40
Claims Analysis
Total Claims: 23
Claim 1
Independent Claim
142 words
An apparatus for scheduling packets in an input-buffered multipoint switch comprising: a plurality of input channels; a plurality of output channels; multi-level request buffers, each multi-level request buffer being specific to one of said plurality of input channels, said multi-level request buffers having discrete levels for storing requests having different packet priorities; and a scheduler circuit, connected to said multi-level request buffers, to indicate a transmission status for each of said input and output channels, said transmission status being indicative of channel availability, arbitrate among a totality of said requests stored in all of said levels of said plurality of multi-level request buffers at least partially based upon a combination of said packet priorities and said transmission statuses of said input and output channels, and issue grants to said requests in a sequence based upon said arbitrating among said totality of requests.
Claim 2
Independent Claim
142 words
An apparatus for scheduling packets in an input-buffered multipoint switch comprising: a plurality of input channels; a plurality of output channels; multi-level request buffers, each multi-level request buffer being specific to one of said plurality of input channels, said multi-level request buffers having discrete levels for storing requests having different packet priorities; and a scheduler circuit, connected to said multi-level request buffers, to indicate a transmission status for each of said input and output channels, said transmission status being indicative of channel availability, arbitrate among a totality of said requests stored in all of said levels of said plurality of multi-level request buffers at least partially based upon a combination of said packet priorities and said transmission statuses of said input and output channels, and issue grants to said requests in a sequence based upon said arbitrating among said totality of requests.
Claim 3
Dependent Claim
38 words
The apparatus of claim 1 further comprising parallel links between each level of said multi-level request buffers and said scheduler circuit, said scheduler circuit being enabled to simultaneously access all of said levels of each said request buffer.
Claim 4
Dependent Claim
55 words
The apparatus of claim 1 wherein said scheduler circuit further includes a mask generator circuit operationally connected to said multi-level request buffers to generate output vectors that are indicative of each output channel that is requested at each of said different packet priorities, each said output vector being associated with one of said packet priorities.
Claim 5
Dependent Claim
86 words
The apparatus of claim 3 wherein said scheduler circuit further includes a mask comparator circuit operationally connected to said mask generator circuit and said multi-level request buffers to compare each particular output vector to associated requests having a packet priority associated with said each particular output vector, said mask comparator circuit having a plurality of outputs, each output being responsive to said comparing of said each particular output vector to said associated requests and being indicative of availability of output channels represented by said associated requests.
Claim 6
Dependent Claim
49 words
The apparatus of claim 4 wherein said scheduler circuit further includes a plurality of sub-scheduler circuits, each sub-scheduler circuit being operationally connected to an associated output of said mask comparator circuit to geneate a level-specific grant for a request having an available input channel and available requested output channels.
Claim 7
Dependent Claim
59 words
The apparatus of claim 5 wherein said scheduler circuit further includes a priority encoder circuit operationally connected to said sub-scheduler circuits to select a highest priority grant from all grants generated from said subscheduler circuits for a specific channel and to transmit said selected highest priority grant to an input channel that corresponds to said selected highest priority request.
Claim 8
Dependent Claim
56 words
The apparatus of claim 1 further including a data path multiplexer operationally connected between said plurality of input channels and said plurality of output channels, said data path multiplexer having data paths for transmitting cells to requested output channels when a request specific to an awaiting cell has been issued a grant by said scheduler circuit.
Claim 9
Independent Claim
225 words
A method for scheduling transmissions of switching cells across an input-buffered network switch that connects a plurality of input channels to a plurality of output channels, each switching cell being associated with one of said plurality of input channels, said method including the steps of: storing a first plurality of requests in a first request buffer that buffers requests related to a first input channel, each said request corresponding to one of said switching cells and having a priority; storing a second plurality of requests in a second request buffer that buffers requests related to a second input channel, each said request corresponding to one of said switching cells and having a priority; accessing said first and second pluralities of requests; arbitrating among said requests of said accessed first and second pluralities of requests based upon availability of said first and second input channels and availability of requested output channels; issuing a grant in response to that request of said first and second pluralities of requests that has a highest priority and for which respective input channels and output channels are available; and issuing grants in response to those requests of said first and second pluralities of requests that have lower priorities than said highest priority and that utilize input channels and output channels that are not utilized by said request having said highest priority.
Claim 10
Independent Claim
225 words
A method for scheduling transmissions of switching cells across an input-buffered network switch that connects a plurality of input channels to a plurality of output channels, each switching cell being associated with one of said plurality of input channels, said method including the steps of: storing a first plurality of requests in a first request buffer that buffers requests related to a first input channel, each said request corresponding to one of said switching cells and having a priority; storing a second plurality of requests in a second request buffer that buffers requests related to a second input channel, each said request corresponding to one of said switching cells and having a priority; accessing said first and second pluralities of requests; arbitrating among said requests of said accessed first and second pluralities of requests based upon availability of said first and second input channels and availability of requested output channels; issuing a grant in response to that request of said first and second pluralities of requests that has a highest priority and for which respective input channels and output channels are available; and issuing grants in response to those requests of said first and second pluralities of requests that have lower priorities than said highest priority and that utilize input channels and output channels that are not utilized by said request having said highest priority.
Claim 11
Dependent Claim
27 words
The method of claim 8 further including a step of receiving done signals that indicate when input channels and output channels are available for new cell transmissions.
Claim 12
Dependent Claim
34 words
The method of claim 8 wherein said step of accessing includes a step of accessing each request of said first and second pluralities of requests in parallel such that all requests are accessed simultaneously.
Claim 13
Dependent Claim
29 words
The method of claim 8 wherein said step of arbitrating includes a step of arbitrating requests one at a time in descending priority from highest priority to lowest priority.
Claim 14
Dependent Claim
33 words
The method of claim 8 wherein said step of arbitrating includes a sub-step of arbitrating requests of all priority levels stored in a request buffer associated with a particular input channel in parallel.
Claim 15
Dependent Claim
34 words
The method of claim 12 wherein said step of arbitrating requests of all priority levels in parallel includes a step of executing said arbitrations in a fixed sequence with respect to said input channels.
Claim 16
Dependent Claim
55 words
The method of claim 12 wherein said step of arbitrating requests of all priority levels includes sub-steps of: generating masks that represent all requests of similar priority levels; and comparing a mask for a particular priority level to a request having a same priority level to determine availability of output channels required by said request.
Claim 17
Dependent Claim
59 words
The method of claim 12 further including the steps of: identifying an input channel having a highest round-robin priority among said plurality of input channels for arbitration purposes; and reserving requested output channels for a multicast request when said multicast request is associated with an input channel that has said highest round-robin priority among said plurality of input channels.
Claim 18
Independent Claim
117 words
An apparatus for scheduling cells in an input-buffered multipoint switch having input channels and output channels comprising: request buffers, each request buffer being specific to one of said input channels, each said request buffer having a number of register levels for storing requests of corresponding priority levels; a means connected to said request buffers for reviewing each request stored in each request buffer and for issuing request grants to highest priority requests having available input channels and available output channels; and parallel data links between each register level of said request buffers and said means for reviewing to enable said means for reviewing simultaneous access to all of said requests stored in all of said request buffers.
Claim 19
Independent Claim
117 words
An apparatus for scheduling cells in an input-buffered multipoint switch having input channels and output channels comprising: request buffers, each request buffer being specific to one of said input channels, each said request buffer having a number of register levels for storing requests of corresponding priority levels; a means connected to said request buffers for reviewing each request stored in each request buffer and for issuing request grants to highest priority requests having available input channels and available output channels; and parallel data links between each register level of said request buffers and said means for reviewing to enable said means for reviewing simultaneous access to all of said requests stored in all of said request buffers.
Claim 20
Dependent Claim
52 words
The apparatus of claim 16 comprising a means for generating a mask vector that represents an aggregate of requested output channels for a particular priority level, said means for generating a mask vector being operatively connected to said request buffers in order to generate a distinct mask vector for each priority level.
Claim 21
Dependent Claim
59 words
The apparatus of claim 17 comprising a means for performing parallel mask comparisons between mask vectors and requests from respective priority levels for a particular input channel to indicate output channel conflicts between requests, said means for performing parallel mask comparisons being operatively connected to said means for generating a mask vector in order to receive said mask vectors.
Claim 22
Dependent Claim
59 words
The apparatus of claim 18 comprising a means for performing level-specific scheduling between said requests from respective priority levels, available input and output channels, said mask comparisons and a round-robin channel priority, said means for performing level-specific scheduling having three outputs per priority level, a level-specific request grant, an updated input channel vector, and an updated output channel vector.
Claim 23
Dependent Claim
46 words
The apparatus of claim 19 wherein said means for reviewing further comprises a means for selecting which level-specific request grant has a highest priority among all level-specific request grants for a single input channel and for transmitting said selected request grant from said means for reviewing.
References Cited (Backward Citations)
US5140582A
Cited
US5301333A
Cited
US5241536A
Cited
US5255265A
Cited
US5471590A
Cited
US5561669A
Cited
US5517495A
Cited
US5500858A
Cited
US5631908A
Cited
US5689508A
Cited
US5742597A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-03-28 | 2003-09-27 | 2004-03-28 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-03-28 | 2007-09-27 | 2008-03-28 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-03-28 | 2011-09-27 | 2012-03-28 | $7700.00 | Window Closed / Lapsed |