Patent US6563837B2 successfully refreshed from Google Patents.
US6563837B2
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for providing work-conserving properties in a non-blocking switch with limited speedup independent of switch size
Assignee: Digital Equipment Corp
•
Filing: 1998-02-10
•
Granted: 2003-05-13
•
Expires: 2018-02-10
Abstract
Abstract A switching method and apparatus operates as a work conserving network device. An arbiter using an arbitration algorithm controls a switch fabric interconnecting input ports and output ports. To switch cells, a virtual output queue of an input port is selected that corresponds to an output port with a lowest occupancy rating and a request is sent to this output port. In a greedy version of the algorithm, input ports may send requests to the lowest occupied output port for which they have a cell. In a non-greedy version, requests may only be sent if that input port has a cell for the lowest occupied output port in the entire network device. An output port that receives one or more requests from input ports uses an input port selection algorithm to select an input port from which to receive a packet. After as many input and output ports are matched as is possible in a phase, the packets for those matched ports are transferred across the switch. The switch fabric operates with a speedup of only twice that of the input port data rates and is still work conserving.
Inventors
- 👤 Pattabhiraman Krishna
- 👤 Naimish S. Patel
- 👤 Anna Charny
- 👤 Robert J. Simcoe
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-24 18:48
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; H04Q; H04Q11/00; H04Q11/04; H04Q11/0428; H04Q11/0478; H04L2012/5638; H04L2012/5646; H04L2012/5652; H04L2012/5678; H04L2012/5679; H04L2012/5681
Claims Analysis
Total Claims: 47
Claim 1
Independent Claim
275 words
A data processing apparatus for transferring data packets between input ports and output ports, the input ports for receiving the data packets into the apparatus and the output ports for transmitting the data packets from the apparatus, the apparatus comprising: a switch fabric connecting input buffers in the input ports to output buffers in the output ports to allow the data packets to be transferred between the input ports and the output ports; and an arbiter that controls the switch fabric to prioritize an order in which the data packets are transferred from the input buffers to the output buffers according to occupancy characteristics of the output buffers; wherein the switch fabric has a speedup of two, wherein the input buffers in the input ports are arranged into virtual output queues, each virtual output queue corresponding to a distinct output port; and the arbiter includes: output buffer occupancy rating detectors indicating the occupancy characteristics of the output buffers for the output ports; an output selector that selects a virtual output queue of an unmatched input port corresponding to an unmatched output port having a lowest occupancy characteristic, and that generates a request for that unmatched output port identifying that input port; an input selector that selects an unmatched input port to be matched with an unmatched output port based upon requests received from the output selector, and that generates a grant for the output selector giving permission for a selected unmatched input port to transfer a packet from its virtual output queue corresponding to the output port sending the grant, to that unmatched output port, thus matching the unmatched input port and unmatched output port.
Claim 2
Dependent Claim
275 words
A data processing apparatus for transferring data packets between input ports and output ports, the input ports for receiving the data packets into the apparatus and the output ports for transmitting the data packets from the apparatus, the apparatus comprising: a switch fabric connecting input buffers in the input ports to output buffers in the output ports to allow the data packets to be transferred between the input ports and the output ports; and an arbiter that controls the switch fabric to prioritize an order in which the data packets are transferred from the input buffers to the output buffers according to occupancy characteristics of the output buffers; wherein the switch fabric has a speedup of two, wherein the input buffers in the input ports are arranged into virtual output queues, each virtual output queue corresponding to a distinct output port; and the arbiter includes: output buffer occupancy rating detectors indicating the occupancy characteristics of the output buffers for the output ports; an output selector that selects a virtual output queue of an unmatched input port corresponding to an unmatched output port having a lowest occupancy characteristic, and that generates a request for that unmatched output port identifying that input port; an input selector that selects an unmatched input port to be matched with an unmatched output port based upon requests received from the output selector, and that generates a grant for the output selector giving permission for a selected unmatched input port to transfer a packet from its virtual output queue corresponding to the output port sending the grant, to that unmatched output port, thus matching the unmatched input port and unmatched output port.
Claim 3
Dependent Claim
48 words
The data processing apparatus of claim 1 , wherein the output selector selects the virtual output queue of the unmatched input port only if the virtual output queue corresponds to a single unmatched output port having a lowest occupancy characteristic of a set of all unmatched output ports.
Claim 4
Dependent Claim
81 words
The data processing apparatus of claim 2 , wherein the input selector selects the unmatched input port according to an input port selection algorithm that maximizes fairness properties of the apparatus in transferring data packets and/or minimizes delay properties of the apparatus in transferring data packets by having output buffers in the output ports arranged into virtual input queues, one virtual input queue for each input port, and wherein each virtual output queue buffers cells sent from its corresponding input port.
Claim 5
Dependent Claim
25 words
The data processing apparatus of claim 2 , wherein the input selector selects the unmatched input port according to a round-robin input port selection algorithm.
Claim 6
Dependent Claim
48 words
The data processing apparatus of claim 4 , wherein the input selector maintains an indication of a previously selected input port and selects the unmatched input port according to a next input port indicated within the input port requests received in relation to the previously selected input port.
Claim 7
Dependent Claim
27 words
The data processing apparatus of claim 2 , wherein the input selector selects the unmatched input port according to a Last Service Time input port selection algorithm.
Claim 8
Dependent Claim
75 words
The data processing apparatus of claim 6 , wherein: the input ports maintain, for each virtual output queue, a time-stamp of a last time each virtual output queue transferred a data packet from its associated input port to an output port, and time-stamp information for virtual output queues is communicated to the input selector; and wherein the input selector selects the unmatched input port from the input port requests received according to an oldest time-stamp.
Claim 9
Dependent Claim
27 words
The data processing apparatus of claim 2 , wherein the input selector selects the unmatched input port according to an Oldest Cell First input port selection algorithm.
Claim 10
Dependent Claim
58 words
The data processing apparatus of claim 6 , wherein: the input ports maintain a cell time stamp for cells of packets, and cell time stamp information for virtual output queues is communicated to the input selector; and wherein the input selector selects the unmatched input port from the input port requests received according to an oldest cell time-stamp.
Claim 11
Dependent Claim
148 words
A data processing apparatus for transferring data packets between input ports and output ports, the input ports for receiving the data packets into the apparatus and the output ports for transmitting the data packets from the apparatus, the apparatus comprising: a switch fabric connecting input buffers in the input ports to output buffers in the output ports to allow the data packets to be transferred between the input ports and the output ports; and an arbiter that controls the switch fabric to prioritize an order in which the data packets are transferred from the input buffers to the output buffers according to occupancy characteristics of the output buffers; wherein the switch fabric has a speedup of two and wherein the input selector selects the unmatched input port according to a shortest queue first input selection algorithm that uses virtual input queue occupancy ratings to determine input port selection.
Claim 12
Dependent Claim
148 words
A data processing apparatus for transferring data packets between input ports and output ports, the input ports for receiving the data packets into the apparatus and the output ports for transmitting the data packets from the apparatus, the apparatus comprising: a switch fabric connecting input buffers in the input ports to output buffers in the output ports to allow the data packets to be transferred between the input ports and the output ports; and an arbiter that controls the switch fabric to prioritize an order in which the data packets are transferred from the input buffers to the output buffers according to occupancy characteristics of the output buffers; wherein the switch fabric has a speedup of two and wherein the input selector selects the unmatched input port according to a shortest queue first input selection algorithm that uses virtual input queue occupancy ratings to determine input port selection.
Claim 13
Dependent Claim
58 words
The data processing apparatus of claim 1 , wherein the output selector selects the virtual output queue of the unmatched input port, wherein the virtual output queue selected corresponds to any unmatched output port having a lowest occupancy characteristic within a set of all unmatched output ports corresponding to active virtual output queues within that unmatched input port.
Claim 14
Dependent Claim
83 words
The data processing apparatus of claim 11 , wherein the input selector selects the unmatched input port according to an input port selection algorithm that maximizes fairness properties of the apparatus in transferring data packets and/or minimizes delay properties of the apparatus in transferring data packets by having output buffers in the output ports arranged into virtual input queues, one virtual input queue for each input port, and wherein each virtual input queue maintains pointers to cells sent from its corresponding input port.
Claim 15
Dependent Claim
25 words
The data processing apparatus of claim 11 , wherein the input selector selects the unmatched input port according to a round-robin input port selection algorithm.
Claim 16
Dependent Claim
48 words
The data processing apparatus of claim 13 , wherein the input selector maintains an indication of a previously selected input port and selects the unmatched input port according to a next input port indicated within the input port requests received in relation to the previously selected input port.
Claim 17
Dependent Claim
27 words
The data processing apparatus of claim 11 , wherein the input selector selects the unmatched input port according to a Last Service Time input port selection algorithm.
Claim 18
Dependent Claim
75 words
The data processing apparatus of claim 15 , wherein: the input ports maintain, for each virtual output queue, a time-stamp of a last time each virtual output queue transferred a data packet from its associated input port to an output port, and time-stamp information for virtual output queues is communicated to the input selector; and wherein the input selector selects the unmatched input port from the input port requests received according to an oldest time-stamp.
Claim 19
Dependent Claim
27 words
The data processing apparatus of claim 11 , wherein the input selector selects the unmatched input port according to an Oldest Cell First input port selection algorithm.
Claim 20
Dependent Claim
58 words
The data processing apparatus of claim 17 , wherein: the input ports maintain a cell time stamp for cells of packets, and cell time stamp information for virtual output queues is communicated to the input selector; and wherein the input selector selects the unmatched input port from the input port requests received according to an oldest cell time-stamp.
Claim 21
Dependent Claim
213 words
A data switching apparatus, comprising: input ports for receiving into the apparatus data packets; output ports for transmitting the data packets from the apparatus; a switch fabric connecting the input ports to the output ports to allow the data packets to be transferred between the input ports and the output ports, wherein the switch fabric has bandwidth that is at least twice that of the input and output ports; an arbiter that controls the switch fabric to prioritize an order in which the data packets are transferred from the input ports to the output ports according to an occupancy characteristic of the output ports; wherein the arbiter, for unmatched input ports, includes a means for requesting an unmatched output port to be matched with an input port based on which unmatched output port corresponding to an active virtual output queue of that input port has a lowest occupancy rating of its buffered data packets of all output ports corresponding to active virtual output queues for that input port; and wherein the arbiter, for unmatched output ports, includes a means for selecting an input port that will transfer a packet to an output port based on an input port selection algorithm, and for matching the selected unmatched input port with that unmatched output port.
Claim 22
Dependent Claim
213 words
A data switching apparatus, comprising: input ports for receiving into the apparatus data packets; output ports for transmitting the data packets from the apparatus; a switch fabric connecting the input ports to the output ports to allow the data packets to be transferred between the input ports and the output ports, wherein the switch fabric has bandwidth that is at least twice that of the input and output ports; an arbiter that controls the switch fabric to prioritize an order in which the data packets are transferred from the input ports to the output ports according to an occupancy characteristic of the output ports; wherein the arbiter, for unmatched input ports, includes a means for requesting an unmatched output port to be matched with an input port based on which unmatched output port corresponding to an active virtual output queue of that input port has a lowest occupancy rating of its buffered data packets of all output ports corresponding to active virtual output queues for that input port; and wherein the arbiter, for unmatched output ports, includes a means for selecting an input port that will transfer a packet to an output port based on an input port selection algorithm, and for matching the selected unmatched input port with that unmatched output port.
Claim 23
Dependent Claim
210 words
A data switching apparatus, comprising: input ports for receiving into the apparatus data packets; output ports for transmitting the data packets from the apparatus; a switch fabric connecting the input ports to the output ports to allow the data packets to be transferred between the input ports and the output ports, wherein the switch fabric has bandwidth that is at least twice that of the input and output ports; an arbiter that controls the switch fabric to prioritize an order in which the data packets are transferred from the input ports to the output ports according to an occupancy characteristic of the output ports; wherein the arbiter, for unmatched input ports, includes a means for requesting an unmatched output port to be matched with an input port, only if an unmatched output port corresponding to an active virtual output queue of that input port has a lowest occupancy rating of its buffered data packets of all unmatched output ports in the data switching apparatus; and wherein the arbiter, for unmatched output ports, includes a means for selecting an unmatched input port that will transfer a packet to an output port based on an input port selection algorithm, and for matching the selected unmatched input port with that unmatched output port.
Claim 24
Dependent Claim
210 words
A data switching apparatus, comprising: input ports for receiving into the apparatus data packets; output ports for transmitting the data packets from the apparatus; a switch fabric connecting the input ports to the output ports to allow the data packets to be transferred between the input ports and the output ports, wherein the switch fabric has bandwidth that is at least twice that of the input and output ports; an arbiter that controls the switch fabric to prioritize an order in which the data packets are transferred from the input ports to the output ports according to an occupancy characteristic of the output ports; wherein the arbiter, for unmatched input ports, includes a means for requesting an unmatched output port to be matched with an input port, only if an unmatched output port corresponding to an active virtual output queue of that input port has a lowest occupancy rating of its buffered data packets of all unmatched output ports in the data switching apparatus; and wherein the arbiter, for unmatched output ports, includes a means for selecting an unmatched input port that will transfer a packet to an output port based on an input port selection algorithm, and for matching the selected unmatched input port with that unmatched output port.
Claim 25
Independent Claim
243 words
A method for switching data packets between input ports and output ports of a network device, the method comprising the steps of: receiving the data packets into the network device on input ports; controlling a switch fabric to prioritize an order in which the data packets are transferred from the input ports to output ports according to an occupancy characteristic of the output ports; transmitting the data packets from the network device on output ports; wherein the input ports contain input buffers arranged into virtual output queues, each virtual output queue corresponding to a distinct output port, the method further comprising the steps of: detecting the occupancy characteristic of the output ports of the network device; selecting, for a specific unmatched input port, a virtual output queue corresponding to an unmatched output port having a lowest occupancy characteristic; generating, for the unmatched output port having the lowest occupancy characteristic, a request identifying the specific unmatched input port; selecting, for the unmatched output port having the lowest occupancy characteristic, an unmatched input port to be matched with that unmatched output port based upon an input port selection algorithm; sending a grant to the unmatched input port giving permission for the unmatched input port to transfer a packet from its virtual output queue corresponding to the unmatched output port having the lowest occupancy characteristic to the unmatched output port having the lowest occupancy characteristic, thus matching the unmatched input port to the unmatched output port.
Claim 26
Independent Claim
243 words
A method for switching data packets between input ports and output ports of a network device, the method comprising the steps of: receiving the data packets into the network device on input ports; controlling a switch fabric to prioritize an order in which the data packets are transferred from the input ports to output ports according to an occupancy characteristic of the output ports; transmitting the data packets from the network device on output ports; wherein the input ports contain input buffers arranged into virtual output queues, each virtual output queue corresponding to a distinct output port, the method further comprising the steps of: detecting the occupancy characteristic of the output ports of the network device; selecting, for a specific unmatched input port, a virtual output queue corresponding to an unmatched output port having a lowest occupancy characteristic; generating, for the unmatched output port having the lowest occupancy characteristic, a request identifying the specific unmatched input port; selecting, for the unmatched output port having the lowest occupancy characteristic, an unmatched input port to be matched with that unmatched output port based upon an input port selection algorithm; sending a grant to the unmatched input port giving permission for the unmatched input port to transfer a packet from its virtual output queue corresponding to the unmatched output port having the lowest occupancy characteristic to the unmatched output port having the lowest occupancy characteristic, thus matching the unmatched input port to the unmatched output port.
Claim 27
Dependent Claim
27 words
The method of claim 21 , wherein the controlling a switch fabric step controls the switch fabric such that the switch fabric has a speedup of two.
Claim 28
Dependent Claim
56 words
The method of claim 21 , wherein the step of selecting a virtual output queue for a specific unmatched input port selects a virtual output queue only if the virtual output queue corresponds to a single unmatched output port having a lowest occupancy characteristic of a set of all unmatched output ports in the network device.
Claim 29
Dependent Claim
20 words
The method of claim 23 , wherein the input port selection algorithm used is a round-robin input port selection algorithm.
Claim 30
Dependent Claim
47 words
The method of claim 24 , further comprising the steps of: maintaining an indication of a previously selected input port; and selecting an unmatched input port according to a next input port indicated within the input port requests received in relation to a previously selected input port.
Claim 31
Dependent Claim
21 words
The method of claim 23 , wherein the input port selection algorithm used is a last service input port selection algorithm.
Claim 32
Dependent Claim
61 words
The method of claim 26 , further comprising the steps of: maintaining, for each virtual output queue, a time-stamp of a last time that virtual output queue transferred a data packet from its associated input port to an output port; and selecting an unmatched input port according to an oldest time-stamp of all input ports corresponding to input port requests received.
Claim 33
Dependent Claim
22 words
The method of claim 23 , wherein the input port selection algorithm used is an Oldest Cell First input port selection algorithm.
Claim 34
Dependent Claim
45 words
The method of claim 28 , further comprising the steps of: maintaining a time stamp for each cell of a packet; and selecting an unmatched input port according to a request received, where said request is associated with a cell having an oldest time stamp.
Claim 35
Dependent Claim
48 words
The method of claim 23 , wherein the input port selection algorithm used is a Shortest Queue First input port selection algorithm that bases input port selection based upon the occupancy rating of virtual input queues associated with input ports requesting to send data to an output port.
Claim 36
Dependent Claim
56 words
The method of claim 21 , wherein the step of selecting a virtual output queue for a specific unmatched input port selects the virtual output queue corresponding to any unmatched output port having a lowest occupancy characteristic within a set of all unmatched output ports corresponding to active virtual output queues within that unmatched input port.
Claim 37
Dependent Claim
20 words
The method of claim 31 , wherein the input port selection algorithm used is a round-robin input port selection algorithm.
Claim 38
Dependent Claim
47 words
The method of claim 32 , further comprising the steps of: maintaining an indication of a previously selected input port; and selecting an unmatched input port according to a next input port indicated within the input port requests received in relation to a previously selected input port.
Claim 39
Dependent Claim
21 words
The method of claim 31 , wherein the input port selection algorithm used is a last service input port selection algorithm.
Claim 40
Dependent Claim
61 words
The method of claim 34 , further comprising the steps of: maintaining, for each virtual output queue, a time-stamp of a last time that virtual output queue transferred a data packet from its associated input port to an output port; and selecting an unmatched input port according to an oldest time-stamp of all input ports corresponding to input port requests received.
Claim 41
Dependent Claim
21 words
The method of claim 31 , wherein the input port selection algorithm used an Oldest Cell First input port selection algorithm.
Claim 42
Dependent Claim
45 words
The method of claim 36 , further comprising the steps of: maintaining a time stamp for each cell of a packet; and selecting an unmatched input port according to a request received, where said request is associated with a cell having an oldest time stamp.
Claim 43
Dependent Claim
60 words
The method of claim 21 , further including the step of maintaining, for each output port, a flow control status which is turned on when the number of queued cells in a portion of the output buffer for that output port exceeds a threshold, such that one or more input ports do not to send cells to that output port.
Claim 44
Dependent Claim
205 words
An arbiter for a network device that operates the network device in a work conserving manner, comprising: an output selector that selects a virtual output queue of an input port of the network device that has data for an output port of the network device, wherein the selection of the virtual output queue is based upon which virtual output queue corresponds to an output port having a lowest occupancy rating, and wherein the output selector includes a means for sending a request to the selected output port; an input selector that selects an input port that is to send data to the selected output port, wherein the selection of the input port is based upon an input port selection algorithm that chooses between one or more input ports represented by requests sent from the output selector; a means for signaling to the input and output ports of the network device to transmit cells across a switch fabric of the network device; and wherein the output selector and the input selector and the means for signaling operate at a processing rate that allows the switch fabric to maintain a speedup of twice that of an incoming data rate for the input ports of the network device.
Claim 45
Dependent Claim
205 words
An arbiter for a network device that operates the network device in a work conserving manner, comprising: an output selector that selects a virtual output queue of an input port of the network device that has data for an output port of the network device, wherein the selection of the virtual output queue is based upon which virtual output queue corresponds to an output port having a lowest occupancy rating, and wherein the output selector includes a means for sending a request to the selected output port; an input selector that selects an input port that is to send data to the selected output port, wherein the selection of the input port is based upon an input port selection algorithm that chooses between one or more input ports represented by requests sent from the output selector; a means for signaling to the input and output ports of the network device to transmit cells across a switch fabric of the network device; and wherein the output selector and the input selector and the means for signaling operate at a processing rate that allows the switch fabric to maintain a speedup of twice that of an incoming data rate for the input ports of the network device.
Claim 46
Dependent Claim
45 words
The arbiter of claim 39 , wherein the selection of the virtual output queue is made only if an output port having a lowest occupancy rating of all output ports in the network device corresponds to an active virtual output queue within the input port.
Claim 47
Dependent Claim
45 words
The arbiter of claim 39 , wherein the selection of the virtual output queue is made based on an output port having a lowest occupancy rating, as selected from a set of output ports corresponding only to active virtual output queues within the input port.
References Cited (Backward Citations)
US5621734A
Cited
US4933937A
Cited
US4845710A
Cited
US4823338B1
Cited
US4823338A
Cited
US5018133A
Cited
US5237661A
Cited
EP0404337A2
Cited
US5138615A
Cited
US5321693A
Cited
US5805816A
Cited
US5367520A
Cited
US5493566A
Cited
US5394402A
Cited
US5737528A
Cited
US5473599A
Cited
US5550823A
Cited
US5617421A
Cited
US5619495A
Cited
WO1996008899A1
Cited
GB2293720A
Cited
US5517495A
Cited
US5500858A
Cited
US5636215A
Cited
US5594732A
Cited
US5774453A
Cited
US5838677A
Cited
US5734865A
Cited
US5978359A
Cited
US5996019A
Cited
US5982771A
Cited
US5982776A
Cited
US5959991A
Cited
US5808056A
Cited
US5892766A
Cited
US5689644A
Cited
US6134217A
Cited
US5859835A
Cited
US6122252A
Cited
EP0817436A2
Cited
US6377583B1
Cited
US5768257A
Cited
US6144635A
Cited
US6122251A
Cited
US6188690B1
Cited
US6345050B1
Cited
US6052376A
Cited
US5892922A
Cited
US6324165B1
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2006-05-12 | 2006-11-11 | 2007-05-13 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2010-05-12 | 2010-11-11 | 2011-05-13 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2014-05-12 | 2014-11-11 | 2015-05-13 | $7700.00 | Window Closed / Lapsed |