US5617409A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Flow control with smooth limit setting for multiple virtual circuits
Assignee: Enterasys Networks Inc
•
Filing: 1994-01-28
•
Granted: 1997-04-01
•
Expires: 2014-01-28
Abstract
Abstract A flow control system is disclosed, for a transmitting node and a receiving node. The transmitting node and the receiving node are linked together through multiple connections or virtual circuits. A flow control circuit in the transmitting node limits the number of data transmission units transmitted from the transmitting station, and not yet copied out of the receive buffers in the receiving node, to the total number of receive buffers in the receiving node. The flow control circuit in the transmitting node further controls the transmission of data transmission units on the multiple connections fairly, such that all connections are provided a proportional amount of the total available receive buffers in the receiving node. In an example embodiment, a global counter is used to maintain the total number of receive buffers containing data in the receiving node, and a global limit register contains the maximum number of receive buffers containing data in the receiving node allowed for a single connection. The flow control circuit further includes logic providing fair and efficient allocation of receive buffers across all virtual circuits between a transmitting node and a destination node. The flow control circuit ensures that during steady state operation, receive buffers in the receiving node, which are used to store data transmission units received from the transmitting node, are fairly divided among all active virtual circuits in the transmitting node.
Inventors
- 👤 Cuneyt M. Ozveren
- 👤 Hallam G. Murray, Jr.
- 👤 Gregory M. Waters
- 👤 Robert J. Simcoe
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-30 04:00
CPC Classifications
H; H04; H04L; H04L12/00; H04L12/54; H04L12/56; H04L12/5601; H04L12/5602; H04L49/00; H04L49/25; H04L49/253; H04L49/255; H04L2012/5678; H04L2012/568; H04L2012/5681
Claims Analysis
Total Claims: 38
Claim 1
Independent Claim
248 words
A flow control apparatus for a transmitting node having a plurality of virtual circuits with a receiving node, comprising: first determining means to determine the number of buffers in said receiving node, said number referred to hereinafter as b max ; selecting means to select a cutoff value, said cutoff value hereinafter referred to as b cutoff , said cutoff value b cutoff selected to be less than b max ; second determining means to determine the number of data transmission units which may be transmitted by said transmitting node during one round trip propagation delay time between said transmitting node and said receiving node, said number of data transmission units hereinafter referred to as r; a global counter incremented in response to each data transmission unit transmitted by said transmitting node to said receiving node, and decremented in response to buffer released messages received from said receiving node, the value of said global counter hereinafter referred to as b; and means for limiting the number of data transmission units transmitted by said transmitting node to said receiving node on any one of said plurality of virtual circuits to a value of lim, responsive to said global counter having a value b greater than said b cutoff value, said value of lim being interpolated between said value r and a value min, where said value min is equal to a number of receive buffers reserved in said receiving node for each one of said plurality of virtual circuits.
Claim 2
Dependent Claim
248 words
A flow control apparatus for a transmitting node having a plurality of virtual circuits with a receiving node, comprising: first determining means to determine the number of buffers in said receiving node, said number referred to hereinafter as b max ; selecting means to select a cutoff value, said cutoff value hereinafter referred to as b cutoff , said cutoff value b cutoff selected to be less than b max ; second determining means to determine the number of data transmission units which may be transmitted by said transmitting node during one round trip propagation delay time between said transmitting node and said receiving node, said number of data transmission units hereinafter referred to as r; a global counter incremented in response to each data transmission unit transmitted by said transmitting node to said receiving node, and decremented in response to buffer released messages received from said receiving node, the value of said global counter hereinafter referred to as b; and means for limiting the number of data transmission units transmitted by said transmitting node to said receiving node on any one of said plurality of virtual circuits to a value of lim, responsive to said global counter having a value b greater than said b cutoff value, said value of lim being interpolated between said value r and a value min, where said value min is equal to a number of receive buffers reserved in said receiving node for each one of said plurality of virtual circuits.
Claim 3
Dependent Claim
89 words
The apparatus as in claim 1, wherein said means for limiting, responsive to said value b of the global counter being less than said b max and greater than said b cutoff , sets said value lim to a value equal to a function of said global counter value b, such that said value lim is set to values gradually decreasing from said value r to said value min, as said value b of said global counter increases from said value b cutoff to said value b max .
Claim 4
Dependent Claim
20 words
The apparatus as in claim 2, where said means for limiting stores said value lim in a global limit register.
Claim 5
Independent Claim
213 words
An apparatus in a first network node for setting a global limit, said global limit equal to the maximum number of receive buffers in a second node available to store data transmission units transmitted from said first network node to said second network node over a given virtual circuit between said first network node and said second network node, comprising: a global counter, containing the total number of outstanding data transmission units transmitted by said first network node to said second network node over all virtual circuits between said first network node and said second network node; global limit setting means, for setting the value of said global limit register based on the following equation: ##EQU4## where b max is a predetermined maximum value equal to a total number of receive buffers in said second network node that may be used to store data transmission units transmitted from said first network node over all virtual circuits between said first network node and said second network node; b cutoff is a predetermined value less than b max , b is the value of the global counter, and r is the number of data transmission units that can be transmitted during one round trip delay between the first network node and the second network node.
Claim 6
Independent Claim
213 words
An apparatus in a first network node for setting a global limit, said global limit equal to the maximum number of receive buffers in a second node available to store data transmission units transmitted from said first network node to said second network node over a given virtual circuit between said first network node and said second network node, comprising: a global counter, containing the total number of outstanding data transmission units transmitted by said first network node to said second network node over all virtual circuits between said first network node and said second network node; global limit setting means, for setting the value of said global limit register based on the following equation: ##EQU4## where b max is a predetermined maximum value equal to a total number of receive buffers in said second network node that may be used to store data transmission units transmitted from said first network node over all virtual circuits between said first network node and said second network node; b cutoff is a predetermined value less than b max , b is the value of the global counter, and r is the number of data transmission units that can be transmitted during one round trip delay between the first network node and the second network node.
Claim 7
Dependent Claim
17 words
The apparatus as in claim 4, wherein said global limit is stored in a global limit register.
Claim 8
Dependent Claim
294 words
A flow control apparatus for a network node, comprising: an outstanding data transmission unit counter, containing the number of outstanding data transmission units transmitted by said network node over one of a set of one or more virtual circuits with a second network node; a global counter, containing the total number of outstanding data transmission units transmitted by said network node to said second network node over said set of one or more virtual circuits; a global limit register, containing a global limit; and flow control means, coupled with said outstanding data transmission unit counter, said global counter, and said global limit register, having first comparison means for comparing the value of said outstanding data transmission unit counter with the value of said global limit register, means, responsive to said first comparison means, for stopping transmission on said one of said set of one or more virtual circuits when the value of said outstanding data transmission unit counter has a value greater than or equal to the value of said global limit register, global limit recalculating means, having second comparison means for comparing the contents of said global counter with a first value b cutoff , third comparison means, responsive to said second comparison means, for comparing said global counter with a second value b max if the contents of said global limit register are greater than or equal to said first value, and global limit setting means, responsive to said third comparison means, for setting the value of said global limit register based on the following equation: ##EQU5## where b is the value of the global counter, and r is the number of cells that can be transmitted during one round trip delay between the first network node and the second network node.
Claim 9
Dependent Claim
294 words
A flow control apparatus for a network node, comprising: an outstanding data transmission unit counter, containing the number of outstanding data transmission units transmitted by said network node over one of a set of one or more virtual circuits with a second network node; a global counter, containing the total number of outstanding data transmission units transmitted by said network node to said second network node over said set of one or more virtual circuits; a global limit register, containing a global limit; and flow control means, coupled with said outstanding data transmission unit counter, said global counter, and said global limit register, having first comparison means for comparing the value of said outstanding data transmission unit counter with the value of said global limit register, means, responsive to said first comparison means, for stopping transmission on said one of said set of one or more virtual circuits when the value of said outstanding data transmission unit counter has a value greater than or equal to the value of said global limit register, global limit recalculating means, having second comparison means for comparing the contents of said global counter with a first value b cutoff , third comparison means, responsive to said second comparison means, for comparing said global counter with a second value b max if the contents of said global limit register are greater than or equal to said first value, and global limit setting means, responsive to said third comparison means, for setting the value of said global limit register based on the following equation: ##EQU5## where b is the value of the global counter, and r is the number of cells that can be transmitted during one round trip delay between the first network node and the second network node.
Claim 10
Dependent Claim
32 words
The apparatus as in claim 6, said global limit recalculating means responsive to transmission of a data message over one of said one or more virtual circuits with said second network node.
Claim 11
Dependent Claim
26 words
The apparatus as in claim 6, said global limit recalculating means responsive to said network node receiving a buffer released message from said second network node.
Claim 12
Dependent Claim
78 words
The apparatus as in claim 6, wherein said second value b max is equal to r * x, where x is the number of virtual circuits that can be established between the first network node and the second network node before throughput is limited by a lack of receive buffers, and r is the number of data transmission units that can be transmitted during one round trip delay between the first network node and the second network node.
Claim 13
Dependent Claim
77 words
The apparatus as in claim 6, said global limit recalculating means further comprising: second global limit setting means, responsive to said first comparison means, for setting said global limit register to r when said global counter is not greater than or equal to said first value b cutoff , and r is the number of data transmission units that can be transmitted during one round trip delay between the first network node and the second network node.
Claim 14
Dependent Claim
49 words
The apparatus as in claim 6, said global limit recalculating means further comprising: third global limit setting means, responsive to said second comparison means, for setting said global limit register to 1 when said global counter is not less than or equal to said second value b max .
Claim 15
Dependent Claim
47 words
The apparatus as in claim 6, said flow control means further comprising means for starting transmission on said one of said set of one or more virtual circuits when said outstanding data transmission unit counter has a value less than the value of said global limit register.
Claim 16
Dependent Claim
44 words
The apparatus as in claim 6, said flow control means further comprising means, responsive to transmission of a data message from said network node over said one of said set of one or more virtual circuits, for incrementing said outstanding data transmission unit counter.
Claim 17
Dependent Claim
34 words
The apparatus as in claim 6, said flow control means further comprising means, responsive to receipt of a buffer released message from said second network node, for decrementing said outstanding data transmission unit counter.
Claim 18
Dependent Claim
37 words
The apparatus as in claim 6, said flow control means further comprising means, responsive to said transmission of a data message over one of said set of one or more virtual circuits, for incrementing said global counter.
Claim 19
Dependent Claim
31 words
The apparatus as in claim 6, said flow control means further comprising means, responsive to receipt of a buffer released message from said second network node, for decrementing said global counter.
Claim 20
Dependent Claim
240 words
A flow control method for a transmitting node having a plurality of virtual circuits with a receiving node, comprising the steps of: determining the number of buffers in said receiving node, said number referred to hereinafter as b max ; selecting a cutoff value, said cutoff value hereinafter referred to as b cutoff , said cutoff value b cutoff selected to be less than b max ; determining the number of data transmission units which may be transmitted by said transmitting node during one round trip propagation delay time between said transmitting node and said receiving node, said number of data transmission units hereinafter referred to as r; incrementing a global counter in response to each data transmission unit transmitted by said transmitting node to said receiving node; decrementing said global counter in response to buffer released messages received from said receiving node, the value of said global counter hereinafter referred to as b; and limiting the number of data transmission units transmitted by said transmitting node to said receiving node on any one of said plurality of virtual circuits to a value of lim, responsive to said global counter having a value b greater than said b cutoff value, said value of lim being interpolated between said value r and a value min, where said value min is equal to a number of receive buffers reserved in said receiving node for each one of said plurality of virtual circuits.
Claim 21
Dependent Claim
240 words
A flow control method for a transmitting node having a plurality of virtual circuits with a receiving node, comprising the steps of: determining the number of buffers in said receiving node, said number referred to hereinafter as b max ; selecting a cutoff value, said cutoff value hereinafter referred to as b cutoff , said cutoff value b cutoff selected to be less than b max ; determining the number of data transmission units which may be transmitted by said transmitting node during one round trip propagation delay time between said transmitting node and said receiving node, said number of data transmission units hereinafter referred to as r; incrementing a global counter in response to each data transmission unit transmitted by said transmitting node to said receiving node; decrementing said global counter in response to buffer released messages received from said receiving node, the value of said global counter hereinafter referred to as b; and limiting the number of data transmission units transmitted by said transmitting node to said receiving node on any one of said plurality of virtual circuits to a value of lim, responsive to said global counter having a value b greater than said b cutoff value, said value of lim being interpolated between said value r and a value min, where said value min is equal to a number of receive buffers reserved in said receiving node for each one of said plurality of virtual circuits.
Claim 22
Dependent Claim
89 words
The method as in claim 17, wherein said step of limiting, responsive to said value b of the global counter being less than said b max and greater than said b cutoff , sets said value lim to a value equal to a function of said global counter value b, such that said value lim is set to values gradually decreasing from said value r to said value min, as said value b of said global counter increases from said value b cutoff to said value b max .
Claim 23
Dependent Claim
20 words
The method as in claim 17, wherein said step of limiting stores said value lim in a global limit register.
Claim 24
Independent Claim
207 words
A method for setting a global limit, said global limit equal to the maximum number of receive buffers in a second node available to store data transmission units transmitted from a first network node to said second network node over a given virtual circuit between said first network node and said second network node, comprising the steps of: counting, in a global counter, the total number of outstanding data transmission units transmitted by said first network node to said second network node over all virtual circuits between said first network node and said second network node; setting a global limit register to a value equal to the following equation: ##EQU6## where b max is a predetermined maximum value equal to a total number of receive buffers in said second network node that may be used to store data transmission units transmitted from said first network node over all virtual circuits between said first network node and said second network node, b cutoff is a predetermined value less than b max , b is the value of the global counter, and r is the number of data transmission units that can be transmitted during one round trip delay between the first network node and the second network node.
Claim 25
Independent Claim
207 words
A method for setting a global limit, said global limit equal to the maximum number of receive buffers in a second node available to store data transmission units transmitted from a first network node to said second network node over a given virtual circuit between said first network node and said second network node, comprising the steps of: counting, in a global counter, the total number of outstanding data transmission units transmitted by said first network node to said second network node over all virtual circuits between said first network node and said second network node; setting a global limit register to a value equal to the following equation: ##EQU6## where b max is a predetermined maximum value equal to a total number of receive buffers in said second network node that may be used to store data transmission units transmitted from said first network node over all virtual circuits between said first network node and said second network node, b cutoff is a predetermined value less than b max , b is the value of the global counter, and r is the number of data transmission units that can be transmitted during one round trip delay between the first network node and the second network node.
Claim 26
Dependent Claim
16 words
The method of claim 20, wherein said global limit is stored in a global limit register.
Claim 27
Dependent Claim
310 words
A flow control method for a network node, comprising the steps of: counting, in an outstanding data transmission unit counter, the number of outstanding data transmission units transmitted by said network node over one of a set of one or more virtual circuits with a second network node; counting, in a global counter, the total number of outstanding data transmission units transmitted by said network node to said second network node over said set of one or more virtual circuits; comparing the value of said outstanding data transmission unit counter with the value of a global limit register, stopping transmission on said one of said set of one or more virtual circuits, responsive to said step of comparing the value of said outstanding data transmission unit counter, when said outstanding data transmission unit counter has a value greater than or equal to the value of said global limit register, comparing the contents said global counter with a first value b cutoff , comparing the contents of said global counter with a second value b max , responsive to said second comparison means, if the contents of said global limit register are greater than or equal to said first value, and setting the value of said global limit register to the following equation: ##EQU7## where b max is a predetermined maximum value equal to a total number of receive buffers in said second network node that may be used to store data transmission units transmitted from said first network node over all virtual circuits between said first network node and said second network node, b cutoff is a predetermined value less than b max , b is the value of the global counter, and r is the number of data transmission units that can be transmitted during one round trip delay between the first network node and the second network node.
Claim 28
Dependent Claim
310 words
A flow control method for a network node, comprising the steps of: counting, in an outstanding data transmission unit counter, the number of outstanding data transmission units transmitted by said network node over one of a set of one or more virtual circuits with a second network node; counting, in a global counter, the total number of outstanding data transmission units transmitted by said network node to said second network node over said set of one or more virtual circuits; comparing the value of said outstanding data transmission unit counter with the value of a global limit register, stopping transmission on said one of said set of one or more virtual circuits, responsive to said step of comparing the value of said outstanding data transmission unit counter, when said outstanding data transmission unit counter has a value greater than or equal to the value of said global limit register, comparing the contents said global counter with a first value b cutoff , comparing the contents of said global counter with a second value b max , responsive to said second comparison means, if the contents of said global limit register are greater than or equal to said first value, and setting the value of said global limit register to the following equation: ##EQU7## where b max is a predetermined maximum value equal to a total number of receive buffers in said second network node that may be used to store data transmission units transmitted from said first network node over all virtual circuits between said first network node and said second network node, b cutoff is a predetermined value less than b max , b is the value of the global counter, and r is the number of data transmission units that can be transmitted during one round trip delay between the first network node and the second network node.
Claim 29
Dependent Claim
38 words
The method as in claim 22, said step of setting the value of said global limit register responsive to transmission of a data message over one of said one or more virtual circuits with said second network node.
Claim 30
Dependent Claim
32 words
The method as in claim 22, said step of setting the value of said global limit register responsive to said network node receiving a buffer released message from said second network node.
Claim 31
Dependent Claim
78 words
The method as in claim 22, wherein said second value b max is equal to r * x, where x is the number of virtual circuits that can be established between the first network node and the second network node before throughput is limited by a lack of receive buffers, and r is the number of data transmission units that can be transmitted during one round trip delay between the first network node and the second network node.
Claim 32
Dependent Claim
73 words
The method as in claim 22, said step of setting the value of said global limit further comprising the step of: setting said global limit register to r when said global counter is not greater than or equal to said first value b cutoff , and r is the number of data transmission units that can be transmitted during one round trip delay between the first network node and the second network node.
Claim 33
Dependent Claim
45 words
The method as in claim 22, said step of setting the value of said global limit further comprising the step of: setting said global limit register to 1 when said global counter is not less than or equal to said second value b max .
Claim 34
Dependent Claim
48 words
The method as in claim 22, said flow control means further comprising the step of starting transmission on said one of said set of one or more virtual circuits when said outstanding data transmission unit counter has a value less than the value of said global limit register.
Claim 35
Dependent Claim
41 words
The method as in claim 22, further comprising the step of incrementing said outstanding data transmission unit counter responsive to transmission of a data message from said network node over said one of said set of one or more virtual circuits.
Claim 36
Dependent Claim
31 words
The method as in claim 22, further comprising the step of decrementing said outstanding data transmission unit counter responsive to receipt of a buffer released message from said second network node.
Claim 37
Dependent Claim
34 words
The method as in claim 22, further comprising the step of incrementing said global counter responsive to said transmission of a data message over one of said set of one or more virtual circuits.
Claim 38
Dependent Claim
28 words
The apparatus as in claim 22, further comprising the step of decrementing said global counter, responsive to receipt of a buffer released message from said second network node.
References Cited (Backward Citations)
US4475192A
Cited
US4849968A
Cited
US4769811A
Cited
US4839891A
Cited
US5199027A
Cited
US5276676A
Cited
US5285446A
Cited
US5278825A
Cited
US5313454A
Cited
US5335224A
Cited
US5289462A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2000-03-31 | 2000-09-30 | 2001-04-01 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2004-03-31 | 2004-09-30 | 2005-04-01 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2008-03-31 | 2008-09-30 | 2009-04-01 | $7700.00 | Window Closed / Lapsed |