Flow control algorithm for high speed networks

• US 5,748,901 A
• Filed: 05/21/1996
• Issued: 05/05/1998
• Est. Priority Date: 05/21/1996
• Status: Expired due to Term

• Current Assignee: Ramot University Authority Limited
• Original Assignee: Ramot University Authority Limited
• Inventors: Mansour, Yishay, Afek, Yehuda, Ostfeld, Zvi
• Primary Examiner(s): Voeltz, Emanuel T.
• Assistant Examiner(s): COLE, TONY MITCHELL
• Application Number:
  US08/651,176
• Time in Patent Office: 714 Days
• Field of Search: 370/229, 370/231, 370/232, 370/235, 370/236, 370/238, 370/234, 370/237, 370/397, 370/412, 370/253, 370/395, 370/468, 395/200.13, 395/200.15, 395/200.68, 395/200.65, 340/825.51
• US Class Current: 709/238
• CPC Class Codes: H04L 12/5602 Bandwidth control in ATM Networks, e.g. leaky bucket
• CPC Class Codes: H04L 2012/5632 Bandwidth allocation
• CPC Class Codes: H04L 2012/5636 Monitoring or policing, e.g. compliance with allocated rate, corrective actions

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.

Claims

1. 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.

2. 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/τ

.

3. 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.

4. 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/τ

.

5. 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.

6. 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/τ

.

7. 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.

8. 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/τ

.

9. 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.

10. 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.

11. 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.

12. The method of claim 10, wherein said α

_inc and said α

_dec are equal.

13. The method of claim 12, wherein said α

_inc and said α

_dec are held constant.

14. 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.

15. The method of claim 14, wherein said queue threshold is a power of two.

16. 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.

17. The method of claim 16, wherein α

_inc *α

_dec is held constant.

18. The method of claim 16, wherein said α

is an inverse power of two.

19. 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.

20. 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.

21. 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.

22. 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_--Dpos *(1-h).

23. 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.

24. 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_--Dneg *(1-h).

25. 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.

26. 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.

27. The method of claim 26, wherein said ratio is an inverse power of two, and wherein said multiplications are done by shift operations.

28. 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.

29. 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.

30. 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.

31. 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.

32. 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.

33. 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.

34. The method of claim 33, wherein said instructing is done by sending a Source Quench message to said at least one source.

35. 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.

36. 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.

37. 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.