US6141323A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Closed loop congestion control using a queue measurement system
Assignee: Whittaker Corp
•
Filing: 1996-06-03
•
Granted: 2000-10-31
•
Expires: 2016-06-03
Abstract
Abstract A queue length measurement device that is comprised of a number of queues that are capable of holding data cells. A differential counter is coupled to each queue. The counter is incremented when a cell is written into the queue and decremented when a cell is read from the queue. An interval measurement device, coupled to the differential counter, generates a pulse to reset the counter at fixed intervals equivalent to n cells time (where n is the maximum number of cells the queue counter can measure). A multiplexer is coupled to the multiple differential counters. A transfer control circuit coupled to the interval measurement device selects the appropriate queue measurement to be output from the multiplexer to the other switch elements. A system and methodology provide for queue flow statistics and closed loop control of cell flow into the queue. A congestion control system is provided comprising a queue (having an input and an output, and capable of storing and outputting a plurality of data cells), an input processor (for coupling a plurality of data cells to the queue input), an output processor, an interval measurement device (generating a pulse at predetermined intervals), and differential queue length generation logic. The output processor, couples to the queue output, for receiving a plurality of data cells from the queue, which generates a queue change in size signal in response to determining for each of the predefined intervals of the difference between a present and a previous queue length.
Inventors
- 👤 Marinica Rusu
- 👤 Ihab A. Jaser
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-07 23:00
CPC Classifications
H; H04; H04L; H04L47/00; H04L47/50; H04L47/62; H04L47/625; H04L47/6255; H04L47/10; H04L47/16; H04L47/30; H04L49/00; H04L49/90; H04L49/9036
Claims Analysis
Total Claims: 31
Claim 1
Independent Claim
118 words
A congestion control system comprising: a queue having an input and an output, and capable of storing and outputting a plurality of data cells; an input processor for coupling a plurality of data cells to the queue input; an output processor, coupled to the queue output, for receiving a plurality of data cells from the queue; an interval measurement device for generating a pulse at predetermined intervals; and differential queue length generation logic, coupled to the queue and the interval measurement device, for generating a signal representative of change in size of the queue in response to determining for each of the predetermined intervals a change in size between a present queue length and a previous queue length.
Claim 2
Dependent Claim
118 words
A congestion control system comprising: a queue having an input and an output, and capable of storing and outputting a plurality of data cells; an input processor for coupling a plurality of data cells to the queue input; an output processor, coupled to the queue output, for receiving a plurality of data cells from the queue; an interval measurement device for generating a pulse at predetermined intervals; and differential queue length generation logic, coupled to the queue and the interval measurement device, for generating a signal representative of change in size of the queue in response to determining for each of the predetermined intervals a change in size between a present queue length and a previous queue length.
Claim 3
Dependent Claim
23 words
The system as in claim 1, wherein said differential queue length generation logic has a predetermined maximum count and a predetermined minimum count.
Claim 4
Dependent Claim
19 words
The system as in claim 1, wherein said queue change in size signal is generated in two's complement form.
Claim 5
Dependent Claim
28 words
The system as in claim 1, wherein the differential queue length generation logic provides the change in size signal in a format providing increased and decreased size information.
Claim 6
Dependent Claim
18 words
The system as in claim 1, wherein the interval measurement device is dynamically programmable to time different intervals.
Claim 7
Dependent Claim
30 words
The system as in claim 1, wherein the interval measurement device is a timer that outputs the pulse after timing an interval equal to a predetermined number of data cells.
Claim 8
Dependent Claim
49 words
The system as in claim 1, wherein the differential queue length generation logic is further comprised of a differential counter, incremented for each queue output of a data cell and decremented for each queue input of a data cell, for providing a current change in queue size signal output.
Claim 9
Dependent Claim
60 words
The system as in claim 7, further comprising: a register for storing and outputting the change in queue size signal output of the differential counter, responsive to the pulse; and wherein the differential counter output is coupled to the register, and wherein the differential counter output is reset after its contents are stored in the register, responsive to the pulse.
Claim 10
Dependent Claim
76 words
The system as in claim 8, further comprising: means for comparing the register output to the differential counter output to generate a comparator output; a register for storing and outputting the change in queue size signal output of the differential counter, responsive to the pulse; and wherein the differential counter output is coupled to the register, and wherein the differential counter output is reset after its contents are stored in the register, responsive to the pulse.
Claim 11
Dependent Claim
39 words
The system as in claim 8, further comprising: a processor coupled to the register for converting the current change in queue size signal output into a two's complement formatted output to provide the change in queue size signal output.
Claim 12
Dependent Claim
33 words
The system as in claim 1, further comprising: means for processing a plurality of queue change in size signals over a plurality of successive time intervals to provide a queue congestion signal output.
Claim 13
Dependent Claim
84 words
The system as in claim 1, further comprising: a host computer providing a source for outputting of the data cells, coupled to the input processor, and a destination associated with the source for receiving the data cells coupled from the output processor, and control means for selectively modifying the output of the data cells from the queue destined for coupling to the destination, responsive to the respective queue congestion signal wherein the source output of data cells is throttled responsive to the control means.
Claim 14
Dependent Claim
74 words
The system as in claim 12, wherein communication of data cells is in packets comprised of a control cell and a plurality of data cells, said control means further comprising: means for selectively modifying the control cell for an output packet of data cells from the queue destined for coupling to the destination, responsive to the queue congestion signal to selectively throttle the source output of data cells responsive to the modified control cell.
Claim 15
Dependent Claim
202 words
The system as in claim 12, further characterized in that said host computer is comprised of a plurality of host computers each having its own respective associated source and destination, wherein the queue is comprised of a plurality of independent storage queues, each providing for input to and output of data cells from the input processor and to the output processor; wherein the differential queue length generation logic is comprised of a plurality of queue length generation circuits, each associated with a respective one of the storage queues, each providing its own respective change in queue size output; wherein the control means provides a separate one of the congestion outputs for each of the respective storage queue; and wherein the control means provides for detection of queue congestion for a specific one of the independent storage queues and provides for the interception of the output of a respective one of the control cells from one of the storage queues to be coupled to the same destination as the specific storage queue, wherein the control cell is modified by the control means to throttle the output from an associated source responsive to the congestion output for the specific one of the storage queues.
Claim 16
Dependent Claim
53 words
The system as in claim 12, further comprising: means for purging a respective one of the storage queues of all data cells associated with a partial packet responsive to detecting the respective input has been throttled so as to compromise to the integrity of the respective packet, responsive to the queue congestion output.
Claim 17
Dependent Claim
31 words
The system as in claim 15, wherein said detecting is comprised of determining a timing throughput for full completion of the packet output exceeds a computed current throughput of said packet.
Claim 18
Dependent Claim
21 words
The system as in claim 16, wherein the computed current throughput is determined by the control cell for the respective packet.
Claim 19
Dependent Claim
24 words
The system as in claim 16, wherein the computed current throughput is determined by the identity of the source associated with the respective packet.
Claim 20
Dependent Claim
23 words
The system as in claim 16, wherein the computed current throughput is determined by the identity of the destination for the respective packet.
Claim 21
Dependent Claim
18 words
The system of claim 2 and further comprising: means for dynamically changing the predetermined maximum and minimum counts.
Claim 22
Dependent Claim
36 words
The system of claim 11, wherein the time interval for the interval measurement device is programmable to a plurality of time intervals; and wherein the programmable time interval is determined responsive to the queue congestion output.
Claim 23
Dependent Claim
104 words
The system as in claim 1, wherein the cells are communicated from a first source having an associated first destination, in packets, comprised of a control cell and payload cells, wherein the control cell controls its receiving input processor, the system further coprising: means for modifying the control cell output for a respective storage queue which is determined to be providing an output to the first destination, responsive to the congestion signal for the storage queue associated with the output to the first source; and wherein said modified control cell throttles the output from the first source prior to coupling to the input processor.
Claim 24
Independent Claim
86 words
A method for controlling data flow in a computer network using a queue measurement device, the method comprising the steps of: determining a measurement of available space of a queue using differential queue length logic based on a change in size of the queue for each of a present queue length and a previous queue length; informing other computers in the computer network of the measurement of available space; and the other computers adjusting their data transfer rate in response to the measurement of available space.
Claim 25
Independent Claim
86 words
A method for controlling data flow in a computer network using a queue measurement device, the method comprising the steps of: determining a measurement of available space of a queue using differential queue length logic based on a change in size of the queue for each of a present queue length and a previous queue length; informing other computers in the computer network of the measurement of available space; and the other computers adjusting their data transfer rate in response to the measurement of available space.
Claim 26
Dependent Claim
109 words
A queue management system for measuring a data queue size, the system comprising: memory for storing data; a cell buffer controller, coupled to the memory, for partitioning the memory into a plurality of queues; a first processor, coupled to the cell buffer controller, for controlling the data flow into the cell buffer controller; a second processor, coupled to the cell buffer controller and to the first processor, for controlling the data flow out of the cell buffer controller; and differential queue measurement apparatus for measuring a change in length for each of the plurality of queues, responsive to the data flow into and out of the cell buffer controller.
Claim 27
Dependent Claim
109 words
A queue management system for measuring a data queue size, the system comprising: memory for storing data; a cell buffer controller, coupled to the memory, for partitioning the memory into a plurality of queues; a first processor, coupled to the cell buffer controller, for controlling the data flow into the cell buffer controller; a second processor, coupled to the cell buffer controller and to the first processor, for controlling the data flow out of the cell buffer controller; and differential queue measurement apparatus for measuring a change in length for each of the plurality of queues, responsive to the data flow into and out of the cell buffer controller.
Claim 28
Dependent Claim
37 words
The system of claim 24, wherein the cell buffer controller comprises: control logic for controlling operation of the cell buffer control; and a plurality of registers for storing information regarding each queue's measurement of change in length.
Claim 29
Dependent Claim
29 words
The system of claim 25 and further including a multiplexer, coupled to the plurality of registers, for outputting one at a time each of a plurality of the registers.
Claim 30
Independent Claim
80 words
A method for providing a queue size output, having a maximum size, the method comprising the steps of: determining a current change in queue length in response to determining for each of a plurality of successive predefined time intervals a change in size of the queue between a present queue length and a previous queue length; determining the current queue size responsive to accumulating the plurality of successive determinations of change in queue length; and outputting the current queue size.
Claim 31
Independent Claim
80 words
A method for providing a queue size output, having a maximum size, the method comprising the steps of: determining a current change in queue length in response to determining for each of a plurality of successive predefined time intervals a change in size of the queue between a present queue length and a previous queue length; determining the current queue size responsive to accumulating the plurality of successive determinations of change in queue length; and outputting the current queue size.
References Cited (Backward Citations)
US4769811A
Cited
US4970720A
Cited
US5140584A
Cited
US5167033A
Cited
US5572522A
Cited
US5777985A
Cited
US5519701A
Cited
US5737313A
Cited
US5898669A
Cited
US5748901A
Cited
US5938749A
Cited
US5864538A
Cited
US5909443A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-10-31 | 2004-05-01 | 2004-10-31 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-10-31 | 2008-05-01 | 2008-10-31 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-10-31 | 2012-05-01 | 2012-10-31 | $7700.00 | Window Closed / Lapsed |