US5517495A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Fair prioritized scheduling in an input-buffered switch
Assignee: Alcatel Lucent SAS
•
Filing: 1994-12-06
•
Granted: 1996-05-14
•
Expires: 2014-12-06
Abstract
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.
Inventors
- 👤 Carsten Lund
- 👤 Steven Phillips
- 👤 Nicholas F. Reingold
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-26 21:18
CPC Classifications
H; H04; H04L; H04L12/00; H04L12/54; H04L12/56; H04L12/5601; H04L49/00; H04L49/15; H04L49/1553; H04L49/1576; H04L49/30; H04L49/3081; H04L2012/5629; H04L2012/5631; H04L2012/5632; H04L2012/5638; H04L2012/5646; H04L2012/5649; H04L2012/5651; H04L2012/5678; H04L2012/5679; H04L2012/5681
Claims Analysis
Total Claims: 26
Claim 1
Independent Claim
109 words
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.
Claim 2
Independent Claim
109 words
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.
Claim 3
Independent Claim
141 words
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.
Claim 4
Independent Claim
141 words
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.
Claim 5
Independent Claim
100 words
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.
Claim 6
Independent Claim
100 words
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.
Claim 7
Dependent Claim
26 words
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.
Claim 8
Dependent Claim
50 words
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.
Claim 9
Dependent Claim
28 words
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.
Claim 10
Dependent Claim
25 words
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.
Claim 11
Dependent Claim
24 words
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.
Claim 12
Dependent Claim
25 words
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.
Claim 13
Dependent Claim
23 words
The apparatus of claim 1 wherein the scheduling control circuit pre-selects at each input buffer a respective virtual circuit for each output port.
Claim 14
Dependent Claim
44 words
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.
Claim 15
Dependent Claim
19 words
The apparatus of claim 1 further comprising: an arbiter unit operating a FARR program to process the received cells.
Claim 16
Dependent Claim
121 words
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.
Claim 17
Dependent Claim
23 words
The apparatus of claim 1 further comprising: a central arbiter using the timestamps to fairly arbitrate between input buffers in an input-buffered switch.
Claim 18
Dependent Claim
22 words
The apparatus of claim 1 further comprising: a central arbiter using the timestamps to fairly arbitrate between ports in an input-buffered switch.
Claim 19
Dependent Claim
24 words
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.
Claim 20
Dependent Claim
22 words
The apparatus of claim 2 wherein the scheduling control circuit pre-selects at each input buffer the virtual circuit for each output port.
Claim 21
Dependent Claim
43 words
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.
Claim 22
Dependent Claim
19 words
The apparatus of claim 2 further comprising: an arbiter unit operating the FARR program to process the received cells.
Claim 23
Dependent Claim
70 words
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.
Claim 24
Dependent Claim
23 words
The apparatus of claim 2 further comprising: a central arbiter using the timestamps to fairly arbitrate between input buffers in an input-buffered switch.
Claim 25
Dependent Claim
22 words
The apparatus of claim 2 further comprising: a central arbiter using the timestamps to fairly arbitrate between ports in an input-buffered switch.
Claim 26
Dependent Claim
24 words
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.
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-05-14 | 1999-11-13 | 2000-05-14 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-05-14 | 2003-11-13 | 2004-05-14 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-05-14 | 2007-11-13 | 2008-05-14 | $7700.00 | Window Closed / Lapsed |