Patent US1958019A successfully refreshed from Google Patents.
Patent US5748901A successfully refreshed from Google Patents.
US5748901A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Flow control algorithm for high speed networks
Assignee: Ramot at Tel Aviv University Ltd
•
Filing: 1996-05-21
•
Granted: 1998-05-05
•
Expires: 2016-05-21
Abstract
Abstract A constant space algorithm for rate based flow control in large computer networks. The switches in the network dynamically measure their unused link capacity, and signal sessions with higher rates to reduce their rates to that unused link capacity. Sessions with lower rates are allowed to increase their rates. This algorithm is suitable for both ATM networks and suitably modified TCP networks.
Inventors
- 👤 Yehuda Afek
- 👤 Yishay Mansour
- 👤 Zvi Ostfeld
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-05 10:46
CPC Classifications
H; H04; H04L; H04L12/00; H04L12/54; H04L12/56; H04L12/5601; H04L12/5602; H04L2012/5629; H04L2012/5631; H04L2012/5632; H04L2012/5636
Claims Analysis
Total Claims: 38
Claim 1
Independent Claim
192 words
A method of flow control in a network having at least one switch, the at least one switch receiving at least one forward cell from at least one source via one of at least one first link and transmitting the at least one forward cell to at least one destination via one of at least one second link, the at least one switch receiving at least one backward cell from the at least one destination via one of the at least one second link and transmitting the at least one backward cell to the at least one source via one of the at least one first link, each of the first and second links having a link capacity, L, the method comprising the steps of: for at least one link, selected from the group consisting of the at least one first link and the at least one second link of at least one of the at least one switch: (a) determining an unused bandwidth, Δ; and (b) setting a maximum allowed cell rate, MACR, equal to a weighted average of said Δ and a prior value of said MACR, prior -- MACR.
Claim 2
Independent Claim
192 words
A method of flow control in a network having at least one switch, the at least one switch receiving at least one forward cell from at least one source via one of at least one first link and transmitting the at least one forward cell to at least one destination via one of at least one second link, the at least one switch receiving at least one backward cell from the at least one destination via one of the at least one second link and transmitting the at least one backward cell to the at least one source via one of the at least one first link, each of the first and second links having a link capacity, L, the method comprising the steps of: for at least one link, selected from the group consisting of the at least one first link and the at least one second link of at least one of the at least one switch: (a) determining an unused bandwidth, Δ; and (b) setting a maximum allowed cell rate, MACR, equal to a weighted average of said Δ and a prior value of said MACR, prior -- MACR.
Claim 3
Dependent Claim
76 words
The method of claim 1, wherein said Δ is determined by the steps of: (a) counting a number, N, of the at least one forward cell transmitted by said at least one link, selected from the group consisting of the at least one first link and the at least one second link of said at least one of the at least one switch, in a time interval, τ; and (b) setting said Δ equal to L-N/τ.
Claim 4
Dependent Claim
83 words
The method of claim 2, wherein said at least one link, selected from the group consisting of the at least one first link and the at least one second link of said at least one of the at least one switch, requires a fixed transmission time to transmit each of the at least one cell, wherein said τ is a power of two times said transmission time, and wherein said division of said N by said τ is performed by a shift operation.
Claim 5
Dependent Claim
83 words
The method of claim 1, wherein said at least one link, selected from the group consisting of the at least one first link and the at least one second link of said at least one of the at least one switch, has a queue, and wherein said Δ is determined by the steps of: (a) counting a number, N, of the at least one forward cell arriving at said queue in a time interval, τ; and (b) setting said Δ equal to L-N/τ.
Claim 6
Dependent Claim
83 words
The method of claim 4, wherein said at least one link, selected from the group consisting of the at least one first link and the at least one second link of said at least one of the at least one switch, requires a fixed transmission time to transmit each of the at least one cell, wherein said τ is a power of two times said transmission time, and wherein said division of said N by said τ is performed by a shift operation.
Claim 7
Dependent Claim
91 words
The method of claim 1, wherein said at least one link, selected from the group consisting of the at least one first link and the at least one second link of said at least one of the at least one switch, has a plurality of queues, and wherein said Δ is determined by the steps of: (a) counting a number, N, of the at least one forward cell arriving at at least one of said plurality of queues in a time interval, τ; and (b) setting said Δ equal to L-N/τ.
Claim 8
Dependent Claim
83 words
The method of claim 6, wherein said at least one link, selected from the group consisting of the at least one first link and the at least one second link of said at least one of the at least one switch, requires a fixed transmission time to transmit each of the at least one cell, wherein said τ is a power of two times said transmission time, and wherein said division of said N by said τ is performed by a shift operation.
Claim 9
Dependent Claim
122 words
The method of claim 1, wherein the at least one forward cell includes an allowed cell rate field containing an allowed cell rate, A, and wherein said Δ is determined by the steps of: (a) initializing a number, N, to zero; (b) for each of the at least one forward cell transmitted by said at least one link, selected from the group consisting of the at least one first link and the at least one second link of said at least one of the at least one switch, in a time interval, τ: if said A exceeds said prior -- MACR: (i) adding prior -- MACR/A to n, otherwise: (ii) adding one to N; and (c) setting said Δ equal to L-N/τ.
Claim 10
Dependent Claim
83 words
The method of claim 8, wherein said at least one link, selected from the group consisting of the at least one first link and the at least one second link of said at least one of the at least one switch, requires a fixed transmission time to transmit each of the at least one cell, wherein said τ is a power of two times said transmission time, and wherein said division of said N by said τ is performed by a shift operation.
Claim 11
Dependent Claim
83 words
The method of claim 1, wherein said MACR is determined by the steps of: (a) choosing an increasing weighting factor, α inc , and a decreasing weighting factor, α dec ; and (b) if said Δ exceeds said prior -- MACR: (i) setting said MACR equal to prior -- MACR*(1-α inc )+Δ*α inc , otherwise: (ii) setting said MACR equal to the greater of prior -- MACR*(1-α dec )+Δ*α dec and prior -- MACR*f D , where f D is a decreasing factor.
Claim 12
Dependent Claim
38 words
The method of claim 10, wherein said α inc and said α dec are inverse powers of two, and wherein said multiplications by said α inc and said multiplications by said α dec are performed by shift operations.
Claim 13
Dependent Claim
15 words
The method of claim 10, wherein said α inc and said α dec are equal.
Claim 14
Dependent Claim
16 words
The method of claim 12, wherein said α inc and said α dec are held constant.
Claim 15
Dependent Claim
68 words
The method of claim 10, wherein said at least one link, selected from the group consisting of the at least one first link and the at least one second link of said at least one of the at least one switch, has a queue having a queue length, and wherein said α inc and said α dec are chosen by comparing said queue length to a queue threshold.
Claim 16
Dependent Claim
14 words
The method of claim 14, wherein said queue threshold is a power of two.
Claim 17
Dependent Claim
47 words
The method of claim 14, wherein said α inc is obtained by multiplying a factor, α, by a first power of two, wherein said α dec is obtained by multiplying said α by a second power of two, and wherein said multiplications are performed by shift operations.
Claim 18
Dependent Claim
13 words
The method of claim 16, wherein α inc *α dec is held constant.
Claim 19
Dependent Claim
14 words
The method of claim 16, wherein said α is an inverse power of two.
Claim 20
Dependent Claim
41 words
The method of claim 10, wherein said f D is 1 minus an inverse power of two, and where said multiplication of said prior -- MACR by said f D is performed by a shift operation and by an addition operation.
Claim 21
Dependent Claim
33 words
The method of claim 10, wherein said f D is a power of two, and wherein said multiplication of said prior -- MACR by said f D is done by a shift operation.
Claim 22
Dependent Claim
113 words
The method of claim 10, further comprising the steps of: (a) setting an error, E, equal to MACR--Δ; (b) if said E is positive: (i) setting a first variation, D pos , equal to a weighted average of said E and a prior value of said D pos , prior -- D pos , otherwise: (ii) setting a second variation, D neg , equal to a weighted average of the negative of said E and a prior value of said D neg , prior -- D neg ; and (c) if the lesser of said D pos and said D neg exceeds a threshold, decreasing said α inc and said α dec .
Claim 23
Dependent Claim
32 words
The method of claim 21, wherein said D pos is determined by the steps of: (a) choosing a weighting factor, h; and (b) setting D pos equal to E*h+prior --D pos *(1-h).
Claim 24
Dependent Claim
25 words
The method of claim 22, wherein said h is an inverse power of two, and wherein said multiplications by h are performed by shift operations.
Claim 25
Dependent Claim
32 words
The method of claim 21, wherein said D neg is determined by the steps of: (a) choosing a weighting factor, h; and (b) setting D neg equal to E*h+prior --D neg *(1-h).
Claim 26
Dependent Claim
25 words
The method of claim 24, wherein said h is an inverse power of two, and wherein said multiplications by h are performed by shift operations.
Claim 27
Dependent Claim
31 words
The method of claim 21, wherein said decreasing of said α inc and of said α dec is done by multiplying said α inc and said α dec by a ratio.
Claim 28
Dependent Claim
23 words
The method of claim 26, wherein said ratio is an inverse power of two, and wherein said multiplications are done by shift operations.
Claim 29
Dependent Claim
61 words
The method of claim 1, wherein at least one of the at least one backward cell is a control cell having an explicit rate field containing an explicit rate, the method further comprising the step of: if said explicit rate exceeds said MACR*f u , where f u is a utilization factor, setting said explicit rate equal to MACR*f u .
Claim 30
Dependent Claim
31 words
The method of claim 28, wherein said utilization factor is a power of two, and wherein said multiplication of said MACR by said f u is done by a shift operation.
Claim 31
Dependent Claim
112 words
The method of claim 28, wherein said control cell has a current cell rate field containing a current cell rate, and wherein said control cell has a no increase field, the method further comprising the steps of: (a) if said explicit rate exceeds a first multiple of said current cell rate, setting said explicit rate equal to said first multiple of said current cell rate; (b) setting a fast maximum allowed cell rate, Fast -- MACR, equal to a weighted average of said Δ and a prior value of said Fast -- MACR; and (c) if said MACR exceeds a second multiple of said Fast -- MACR, setting said no increase field.
Claim 32
Dependent Claim
36 words
The method of claim 30, wherein said first multiple of said current cell rate is twice said current cell rate, and wherein said second multiple of said Fast -- MACR is twice said Fast -- MACR.
Claim 33
Dependent Claim
53 words
The method of claim 1, wherein the at least one source has a window of an adjustable size, the method further comprising the steps of: (a) receiving said MACR from said one of the at least one switch; and (b) adjusting said size of said window according to said at least one MACR.
Claim 34
Dependent Claim
31 words
The method of claim 1, wherein the at least one source has a rate, the method further comprising the step of instructing the at least one source to decrease said rate.
Claim 35
Dependent Claim
22 words
The method of claim 33, wherein said instructing is done by sending a Source Quench message to said at least one source.
Claim 36
Dependent Claim
46 words
The method of claim 33, wherein at least one cell, selected from the group consisting of the at least one forward cell and the at least one backward cell, includes a congestion indication bit, and wherein said instructing is done by setting said congestion indication bit.
Claim 37
Dependent Claim
55 words
The method of claim 1, wherein at least one cell, selected from the group consisting of the at least one forward cell and the at least one backward cell, includes a rate field containing a rate, the method further comprising the step of: if said rate exceeds said MACR, dropping said at least one cell.
Claim 38
Dependent Claim
142 words
The method of claim 1, wherein said at least one source has a rate, and wherein said at least one link, selected from the group consisting of the at least one first link and the at least one second link of said at least one of the at least one switch, has a high priority queue and at least one low priority queue, the method further comprising the step of: if said rate exceeds said MACR: (a) transmitting at least one cell, selected from the group consisting of the at least one forward cell and the at least one backward cell, via one of said at least one low priority queue, otherwise: (b) transmitting at least one cell, selected from the group consisting of the at least one forward cell and the at least one backward cell, via said high priority queue.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-05-04 | 2001-11-03 | 2002-05-05 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-05-04 | 2005-11-03 | 2006-05-05 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-05-04 | 2009-11-03 | 2010-05-05 | $7700.00 | Window Closed / Lapsed |