US5724358A
Expired / Lapsed
US
⏱️ 0.0 years remaining
High speed packet-switched digital switch and method
Assignee: Riverstone Networks Inc
•
Filing: 1996-02-23
•
Granted: 1998-03-03
•
Expires: 2016-02-23
Abstract
Abstract A system and method for communicating multiple priority level data packets between input ports and output ports of a switch is disclosed where the data packet has a header portion identifying at least one output port destination and a level of priority, selected from a predetermined set of priority levels, of the data within the data packet. A buffer, shared by the output ports, stores the data packet in a selected buffer location based on the output port destination and priority level of the data packet. Pointers to buffer locations containing data packets having a particular priority level are stored in one or more priority sub-queues for one or more of the plurality of output ports based on the output port destinations and the priority level of the data packet. The data packets are output to the output ports in priority order.
Inventors
- 👤 Kent H. Headrick
- 👤 Kannan Devarajan
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-03 22:58
CPC Classifications
H; H04; H04L; H04L12/00; H04L12/54; H04L12/56; H04L12/5601; H04L49/00; H04L49/10; H04L49/104; H04L49/105; H04L49/108; H04L49/20; H04L49/201; H04L49/203; H04L49/30; H04L49/3081; H04L2012/5638; H04L2012/5646; H04L2012/5651; H04L2012/5678; H04L2012/5681; Y; Y10; Y10S; Y10S370/00; Y10S370/901; Y10S370/902; Y10S370/903; Y10S370/905
Claims Analysis
Total Claims: 36
Claim 1
Independent Claim
154 words
A system for communicating multiple priority level data packets between an input port and one or more output ports of a switch, comprising: means for receiving a data packet from the input port, the data packet having a header portion indicating an output port destination and a level of priority, selected from a predetermined set of priority levels, of the data within the data packet; a buffer for storing the data packet in a selected buffer location, the buffer being shared by the output ports; a plurality of queues corresponding to each of the output ports, each queue having a plurality of sub-queues for storing pointers to buffer locations containing data packets having different priority levels, selected from the predetermined set of priority levels; and means for storing a pointer to the selected buffer location in the priority sub-queues based on the output port destination and the selected priority level of the data packet.
Claim 2
Independent Claim
154 words
A system for communicating multiple priority level data packets between an input port and one or more output ports of a switch, comprising: means for receiving a data packet from the input port, the data packet having a header portion indicating an output port destination and a level of priority, selected from a predetermined set of priority levels, of the data within the data packet; a buffer for storing the data packet in a selected buffer location, the buffer being shared by the output ports; a plurality of queues corresponding to each of the output ports, each queue having a plurality of sub-queues for storing pointers to buffer locations containing data packets having different priority levels, selected from the predetermined set of priority levels; and means for storing a pointer to the selected buffer location in the priority sub-queues based on the output port destination and the selected priority level of the data packet.
Claim 3
Dependent Claim
28 words
The switch of claim 1, further comprising means for outputing the data packet to the output port, in an order based on the predetermined set of priority levels.
Claim 4
Dependent Claim
32 words
The switch of claim 1, further comprising means for outputing the data packets output ports, the data packets for each output port being output based on the predetermined set of priority levels.
Claim 5
Dependent Claim
45 words
The switch of claim 1, further comprising means for updating the pointers in the output queues when a data packet is received from an input port, and means for storing the plurality of priority sub-queues separately so that the plurality of sub-queues are updated simultaneously.
Claim 6
Dependent Claim
28 words
The switch of claim 4, wherein the updating means updates the pointers in each output queue when a data packet, indicating more than one output ports, is received.
Claim 7
Dependent Claim
42 words
The switch of claim 3, further comprising means for updating the output queues when a data packet is received and output by the switch, and means for storing the plurality of priority sub-queues so that the plurality of sub-queues are updated simultaneously.
Claim 8
Dependent Claim
48 words
The switch of claim 1, wherein each output queue for an output port stores the pointers to the buffer locations so that a first pointer within the output queue for a selected priority level is the first pointer output to the output port for that selected priority level.
Claim 9
Dependent Claim
21 words
The switch of claim 7, wherein each output port queue comprises a plurality of pointers linked together in a linked list.
Claim 10
Dependent Claim
14 words
The switch of claim 1, wherein the predetermined set of priority levels is four.
Claim 11
Dependent Claim
24 words
The switch of claim 1, further comprising means for determining whether to accept a data packet into the buffer based on predetermined congestion criteria.
Claim 12
Independent Claim
142 words
A method for communicating multiple priority level data packets between an input port and one or more output ports of a switch, comprising: receiving a data packet from the input port, the data packet having a header portion indicating an output port destination and a level of priority, selected from a predetermined set of priority levels, of the data within the data packet; storing the data packet in a selected buffer location in a buffer, the buffer being shared by the output ports; and storing a pointer to the selected buffer location, in a plurality of queues corresponding to each of the plurality of output ports, each queue having a plurality of sub-queues for storing pointers to buffer locations containing data packets having a particular priority level, based on the output port destination and the selected priority level of the data packet.
Claim 13
Independent Claim
142 words
A method for communicating multiple priority level data packets between an input port and one or more output ports of a switch, comprising: receiving a data packet from the input port, the data packet having a header portion indicating an output port destination and a level of priority, selected from a predetermined set of priority levels, of the data within the data packet; storing the data packet in a selected buffer location in a buffer, the buffer being shared by the output ports; and storing a pointer to the selected buffer location, in a plurality of queues corresponding to each of the plurality of output ports, each queue having a plurality of sub-queues for storing pointers to buffer locations containing data packets having a particular priority level, based on the output port destination and the selected priority level of the data packet.
Claim 14
Dependent Claim
26 words
The method of claim 11, further comprising outputing the data packet to the output port, in an order based on the predetermined set of priority levels.
Claim 15
Dependent Claim
31 words
The method of claim 11, further comprising outputing the data packets to output ports, the data packets for each output port being output based on the predetermined set of priority levels.
Claim 16
Dependent Claim
41 words
The method of claim 11, further comprising updating the pointers in the output queues when a data packet is received from an input port, and storing the plurality of priority sub-queues separately so that the plurality of sub-queues are updated simultaneously.
Claim 17
Dependent Claim
27 words
The method of claim 14, wherein updating comprises updating the pointers in each output queue when a data packet, indicating more than one output ports, is received.
Claim 18
Dependent Claim
38 words
The method of claim 13, further comprising updating the output queues when a data packet is received and output by the switch, and storing the plurality of priority sub-queues so that the plurality of sub-queues are updated simultaneously.
Claim 19
Dependent Claim
48 words
The method of claim 11, wherein each output queue for an output port stores the pointers to the buffer locations so that a first pointer within the output queue for a selected priority level is the first pointer output to the output port for that selected priority level.
Claim 20
Dependent Claim
21 words
The method of claim 17, wherein each output port queue comprises a plurality of pointers linked together in a linked list.
Claim 21
Dependent Claim
14 words
The method of claim 11, wherein the predetermined set of priority levels is four.
Claim 22
Dependent Claim
21 words
The method of claim 11, further comprising determining whether to accept a data packet into the buffer based on congestion criteria.
Claim 23
Independent Claim
182 words
A method for communicating multiple priority level data packets between an input port and one or more output ports of a switch, comprising: receiving a data packet from the input port, the data packet having a header portion indicating a plurality of output port destinations and a level of priority, selected from a predetermined set of priority levels, of the data within the data packet; storing the data packet in a selected buffer location within a buffer; storing a pointer pointing to the selected buffer location in a plurality of queues corresponding to each of the plurality of output ports, each output port queue having a plurality of sub-queues for storing pointers to buffer locations containing data packets having a plurality of priority levels, wherein a pointer to the selected buffer location is stored in each particular priority sub-queue, corresponding to the priority level of the particular data packet, for each of the plurality of output port destinations; and reading the data packet out of the buffer memory in priority order, for each of the plurality of pointers, for each output port.
Claim 24
Independent Claim
182 words
A method for communicating multiple priority level data packets between an input port and one or more output ports of a switch, comprising: receiving a data packet from the input port, the data packet having a header portion indicating a plurality of output port destinations and a level of priority, selected from a predetermined set of priority levels, of the data within the data packet; storing the data packet in a selected buffer location within a buffer; storing a pointer pointing to the selected buffer location in a plurality of queues corresponding to each of the plurality of output ports, each output port queue having a plurality of sub-queues for storing pointers to buffer locations containing data packets having a plurality of priority levels, wherein a pointer to the selected buffer location is stored in each particular priority sub-queue, corresponding to the priority level of the particular data packet, for each of the plurality of output port destinations; and reading the data packet out of the buffer memory in priority order, for each of the plurality of pointers, for each output port.
Claim 25
Dependent Claim
41 words
The method of claim 21, further comprising updating the pointers in the output queues when a data packet is received from an input port, and storing the plurality of priority sub-queues separately so that the plurality of sub-queues are updated simultaneously.
Claim 26
Dependent Claim
27 words
The method of claim 22, wherein updating comprises updating the pointers in each output queue when a data packet, indicating more than one output ports, is received.
Claim 27
Dependent Claim
38 words
The method of claim 21, further comprising updating the output queues when a data packet is received and output by the switch, and storing the plurality of priority sub-queues so that the plurality of sub-queues are updated simultaneously.
Claim 28
Dependent Claim
48 words
The method of claim 21, wherein each output queue for an output port stores the pointers to the buffer locations so that a first pointer within the output queue for a selected priority level is the first pointer output to the output port for that selected priority level.
Claim 29
Dependent Claim
21 words
The method of claim 25, wherein each output port queue comprises a plurality of pointers linked together in a linked list.
Claim 30
Dependent Claim
14 words
The method of claim 21, wherein the predetermined set of priority levels is four.
Claim 31
Dependent Claim
21 words
The method of claim 21, further comprising determining whether to accept a data packet into the buffer based on congestion criteria.
Claim 32
Independent Claim
184 words
A method for communicating multiple priority level data packets between an input port and one or more output ports of a switch, comprising: receiving a data packet from the input port, the data packet having a header portion indicating an output port destinations and a level of priority, selected from a predetermined set of priority levels, of the data within the data packet; managing a buffer, the buffer having buffer locations for storing a data packet, with a plurality of queues corresponding to each of the plurality of output ports, each queue having a plurality of sub-queues for storing pointers to buffer locations containing data packets having a particular priority level; determining if the number of data packets within each of the plurality of priority sub-queues is greater than a minimum value; comparing a maximum buffer space value of the buffer to a total number of data packets within the buffer; and storing the data packet in a particular priority sub-queue for a particular output port, comprising accepting the data packet into the buffer, and temporarily decreasing the free space available in the buffer.
Claim 33
Independent Claim
184 words
A method for communicating multiple priority level data packets between an input port and one or more output ports of a switch, comprising: receiving a data packet from the input port, the data packet having a header portion indicating an output port destinations and a level of priority, selected from a predetermined set of priority levels, of the data within the data packet; managing a buffer, the buffer having buffer locations for storing a data packet, with a plurality of queues corresponding to each of the plurality of output ports, each queue having a plurality of sub-queues for storing pointers to buffer locations containing data packets having a particular priority level; determining if the number of data packets within each of the plurality of priority sub-queues is greater than a minimum value; comparing a maximum buffer space value of the buffer to a total number of data packets within the buffer; and storing the data packet in a particular priority sub-queue for a particular output port, comprising accepting the data packet into the buffer, and temporarily decreasing the free space available in the buffer.
Claim 34
Dependent Claim
106 words
The method of claim 29, wherein determining if the number of data packets, comprises determining a total number of data packets within each priority sub-queue, adding the total number of data packets for each priority sub-queue together to produce a total value, determining a reserved buffer space value corresponding to a number of buffer locations needed to satisfy the minimums for all of said priority sub-queues, comparing said total value to said reserved buffer space value to produce a buffer quota value for satisfying the minimum value of all of the priority sub-queues, and reducing the free space available in said buffer by said buffer quota.
Claim 35
Dependent Claim
34 words
The method of claim 30, further comprising comparing a number of data packets within each priority sub-queue to a minimum and maximum value to determine whether to accept a data packet into the buffer.
Claim 36
Dependent Claim
51 words
The method of claim 21, wherein comparing the number of data packets comprises accepting the data packet if the number of data packets within priority sub-queue is below the minimum value, and dropping the data packet if the number of data packets with the priority sub-queue is above the maximum value.
References Cited (Backward Citations)
US4849968A
Cited
US5072443A
Cited
US5014265A
Cited
US5163046A
Cited
US5191578A
Cited
US5051979A
Cited
US5331641A
Cited
US5280475A
Cited
US5115430A
Cited
US5229991A
Cited
US5317562A
Cited
US5365519A
Cited
US5287530A
Cited
US5459724A
Cited
US5179556A
Cited
US5233606A
Cited
US5191582A
Cited
US5535197A
Cited
US5287346A
Cited
US5440546A
Cited
US5369635A
Cited
US5394397A
Cited
US5313454A
Cited
US5278828A
Cited
US5438566A
Cited
US5291477A
Cited
US5323389A
Cited
US5410540A
Cited
US5406566A
Cited
US5436893A
Cited
US5422880A
Cited
US5440549A
Cited
US5402415A
Cited
US5359592A
Cited
US5440523A
Cited
US5430715A
Cited
US5457679A
Cited
US5521916A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-03-02 | 2001-09-01 | 2002-03-03 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-03-02 | 2005-09-01 | 2006-03-03 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-03-02 | 2009-09-01 | 2010-03-03 | $7700.00 | Window Closed / Lapsed |