US5557607A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Methods and apparatus for enqueueing and dequeueing data cells in an ATM switch fabric architecture
Assignee: PMC-SEIRRA Inc
•
Filing: 1995-05-11
•
Granted: 1996-09-17
•
Expires: 2015-05-11
Abstract
Abstract An ATM switching system architecture of a switch fabric-type is built of, a plurality of ATM switch element circuits and routing table circuits for each physical connection to/from the switch fabric. A shared pool of memory is employed to eliminate the need to provide memory at every crosspoint. Each routing table maintains a marked interrupt linked list for storing information about which ones of its virtual channels are experiencing congestion. This linked list is available to a processor in the external workstation to alert the processor when a congestion condition exists in one of the virtual channels. The switch element circuit typically has up to eight 4-bit-wide nibble inputs and eight 4-bit-wide nibble outputs and is capable of connecting cells received at any of its inputs to any of its outputs, based on the information in a routing tag uniquely associated with each cell.
Inventors
- 👤 Brian D. Holden
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-31 20:14
CPC Classifications
H; H04; H04L; H04L12/00; H04L12/54; H04L12/56; H04L12/5601; C; C07; C07K; C07K14/00; C07K14/195; C07K14/32; C07K14/325; H04L49/00; H04L49/10; H04L49/104; H04L49/105; H04L49/108; H04L49/20; H04L49/201; H04L49/203; H04L49/25; H04L49/253; H04L49/255; H04L49/30; H04L49/3081; H04L49/309; H04J; H04J2203/00; H04J2203/0001; H04J2203/0064; H04J2203/0067; H04J2203/0071; H04L2012/5629; H04L2012/5631; H04L2012/5632; H04L2012/5635; H04L2012/5638; H04L2012/5646; H04L2012/5651; H04L2012/5678; H04L2012/5681; H04L2012/5682
Claims Analysis
Total Claims: 14
Claim 1
Independent Claim
200 words
In a switch element having a plurality of queues for storing cells of data being routed from an input interface to an output interface and having a controller, each of the queues having a proportion of available bandwidth associated therewith, a method for determining which of the queues will be connected to the output interface during a given cell cycle in accordance with a proportional bandwidth scheme comprising the steps of: designating a specified number of cell cycles as a service order interval; constructing a service order table that, for each of the cell cycles within the service order interval, lists the queues in accordance with the service order priority they will have during that cell cycle, the service order priority for each queue being related to the proportion of available bandwidth associated therewith; using the controller to determine which of the plurality of queues contain a cell ready to be transmitted to the output interface during a given cell cycle; and using the controller to decide, by reference to the service order table, which of the queues containing a cell ready to be transmitted to the output interface during that cell cycle will be connected to the output interface.
Claim 2
Dependent Claim
200 words
In a switch element having a plurality of queues for storing cells of data being routed from an input interface to an output interface and having a controller, each of the queues having a proportion of available bandwidth associated therewith, a method for determining which of the queues will be connected to the output interface during a given cell cycle in accordance with a proportional bandwidth scheme comprising the steps of: designating a specified number of cell cycles as a service order interval; constructing a service order table that, for each of the cell cycles within the service order interval, lists the queues in accordance with the service order priority they will have during that cell cycle, the service order priority for each queue being related to the proportion of available bandwidth associated therewith; using the controller to determine which of the plurality of queues contain a cell ready to be transmitted to the output interface during a given cell cycle; and using the controller to decide, by reference to the service order table, which of the queues containing a cell ready to be transmitted to the output interface during that cell cycle will be connected to the output interface.
Claim 3
Dependent Claim
43 words
The method according to claim 1 wherein the proportion of available bandwidth that is a fraction consisting of a numerator and a denominator common to each queue and wherein the service order interval has a number of cell cycles equal to said denominator.
Claim 4
Dependent Claim
29 words
The method according to claim 1 wherein there are three queues assigned proportional bandwidths 1/8, 2/8 and 5/8 and there are eight cell cycles in each service order interval.
Claim 5
Dependent Claim
162 words
A switching device for transmitting a data cell in a network, the network having a plurality of network destinations coupled thereto, the data cell comprising a first data field, the first data field corresponding to a first group of network destinations to which the data cell is to be transmitted, the switching device comprising: a plurality of outputs; a queue for temporarily storing the data cell; and a memory for storing a plurality of data words, each data word comprising a plurality of first bits, each of said first bits corresponding to a different one of said outputs; wherein the data cell is placed on selected ones of the outputs for transmission to the first group of network destinations, the selected ones of the outputs corresponding to first bits which have been set in a first data word selected from the plurality of data words, the first data word being selected in response to the first data field in the data cell.
Claim 6
Dependent Claim
162 words
A switching device for transmitting a data cell in a network, the network having a plurality of network destinations coupled thereto, the data cell comprising a first data field, the first data field corresponding to a first group of network destinations to which the data cell is to be transmitted, the switching device comprising: a plurality of outputs; a queue for temporarily storing the data cell; and a memory for storing a plurality of data words, each data word comprising a plurality of first bits, each of said first bits corresponding to a different one of said outputs; wherein the data cell is placed on selected ones of the outputs for transmission to the first group of network destinations, the selected ones of the outputs corresponding to first bits which have been set in a first data word selected from the plurality of data words, the first data word being selected in response to the first data field in the data cell.
Claim 7
Dependent Claim
21 words
The switching device of claim 4 wherein there are up to eight outputs and eight first bits in each data word.
Claim 8
Dependent Claim
14 words
The switching device of claim 4 wherein the memory comprises random access memory (RAM).
Claim 9
Dependent Claim
17 words
The switching device of claim 4 wherein the data cell comprises up to 118 nibble wide segments.
Claim 10
Dependent Claim
79 words
The switching device of claim 4, further comprising a queue completion register, the queue completion register comprising a plurality of second bits, each of the second bits corresponding to one of the outputs, the second bits being set when the data cell is placed on the outputs corresponding to the second bits, the data cell remaining in the queue until the second bits set in the queue completion register match the first bits set in the first data word.
Claim 11
Dependent Claim
17 words
The switching device of claim 8 wherein there are up to eight outputs and eight second bits.
Claim 12
Independent Claim
142 words
A method for transmitting a data cell to a plurality of network destinations using a switch element having a plurality of outputs, the data cell having a first data field, the first data field corresponding to a first group of network destinations to which the data cell is to be transmitted, the method comprising the steps of: storing the data cell in a queue; using the first data field to select a first data word from a memory, the first data word comprising first bits, each of the first bits corresponding to a different one of the switch element outputs; and placing the data cell on selected ones of the switch element outputs for transmission to the first group of network destinations, the selected ones of the switch outputs corresponding to first bits in the first data word which have been set.
Claim 13
Independent Claim
142 words
A method for transmitting a data cell to a plurality of network destinations using a switch element having a plurality of outputs, the data cell having a first data field, the first data field corresponding to a first group of network destinations to which the data cell is to be transmitted, the method comprising the steps of: storing the data cell in a queue; using the first data field to select a first data word from a memory, the first data word comprising first bits, each of the first bits corresponding to a different one of the switch element outputs; and placing the data cell on selected ones of the switch element outputs for transmission to the first group of network destinations, the selected ones of the switch outputs corresponding to first bits in the first data word which have been set.
Claim 14
Dependent Claim
84 words
The method of claim 10, further comprising the steps of: setting second bits in a queue completion register, each of the second bits set in the queue completion register corresponding to the outputs upon which the data cell has been placed; comparing the second bits in the queue completion register to the first bits in the first data word; and dequeuing the data cell when the second bits set in the queue completion register match the first bits set in the first data word.
References Cited (Backward Citations)
US5126999A
Cited
US5050161A
Cited
US5303078A
Cited
US5241536A
Cited
US5278828A
Cited
US5299190A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1999-09-17 | 2000-03-18 | 2000-09-17 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-09-17 | 2004-03-18 | 2004-09-17 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-09-17 | 2008-03-18 | 2008-09-17 | $7700.00 | Window Closed / Lapsed |