Rate allocation system and method for ATM switched networks

• US 6,359,863 B1
• Filed: 12/24/1998
• Issued: 03/19/2002
• Est. Priority Date: 08/12/1998
• Status: Expired due to Term

• Current Assignee: Regents of the University of California (University of California)
• Original Assignee: Regents of the University of California (University of California)
• Inventors: Kalampoukas, Lampros, Varma, Anujan
• Primary Examiner(s): Yao, Kwang B.
• Assistant Examiner(s): Pham, Brenda H.
• Application Number:
  US09/220,539
• Time in Patent Office: 1,181 Days
• Field of Search: 370/229, 370/230, 370/231, 370/232, 370/233, 370/234, 370/235, 370/253, 370/377, 370/395, 370/397, 370/399, 370/409, 370/468, 370/465, 370/252
• US Class Current: 370/232
• CPC Class Codes: H04L 12/5601 Transfer mode dependent, e.g. ATM
• CPC Class Codes: H04L 2012/5632 Bandwidth allocation
• CPC Class Codes: H04L 43/00 Arrangements for monitoring or testing data switching networks
• CPC Class Codes: H04L 43/0864 Round trip delays
• CPC Class Codes: H04L 43/0894 Packet rate
• CPC Class Codes: H04L 49/557 Error correction, e.g. fault recovery or fault tolerance

Abstract

A method for rate allocation within the individual switches of a communication network implementing a rate-based congestion control approach for best-effort traffic. The method enables a guaranteed minimum bandwidth to be allocated to each communication session or connection, in addition to fairly dividing the available bandwidth among the competing connections. The method also estimates the transmission rate of each connection, instead of relying on explicit indications provided by the connection, and uses this information in the computation of its fair share of bandwidth. The method also calculates the available bandwidth on the link where the bandwidth is allocated, by measuring the utilization of the link periodically. Finally, the method incorporates a mechanism to detect connections that remain idle and withdraw allocations from them so as to avoid under-utilization of the link bandwidth.

Claims

1. A congestion control method for communications networks having a plurality of connections to switches, wherein each connection has a current transmission rate, wherein the source of each connection requests a specific amount of bandwidth to be allocated to the connection by the switches on its path to the destination, and wherein requests for bandwidth allocation are carried by resource management (RM) cells transmitted periodically by the source, comprising the steps of:

(a) estimating the current transmission rate of each connection by measuring the time interval between the reception of a plurality of resource management (RM) cells from the given connection;

(b) allocating bandwidth using said estimated transmission rate as the requested rate;

(c) designating a connection for which a max-min fairness rate for that connection is less than the minimum cell rate (MCR) for that connection as a MCR-limited connection; and

(d) allocating bandwidth to said MCR-limited connection equal to said connection'"'"'s MCR to satisfy a minimum rate requirement for that connection.

2. A method as recited in claim 1, further comprising the steps of setting the current transmission rate of a connection equal to n_j/t_j if n_j cells from a connection j are received during an interval t_j in which said plurality RM cells were received.

3. A method as recited in claim 1, further comprising the steps of updating the actual bandwidth allocation maintained for a connections wherein the new allocation A_j(t₁) for connection j is determined according to the steps comprising,

(i) if the maximum allocation A_max(t₁) is less than the MCR of the connection, setting A_j(t₁) to A_max(t₁),

(ii) if the maximum allocation A_max(t₁) is less than both the request ρ _j(t₁) and the value of CCR in the RM cell received, setting A_j(t₁) to A_max(t₁), and

(iii) if the computed A_max(t₁) is equal to or more than the minimum of ρ

_j(t₁) and the value of CCR in the RM cell received, setting A_j(t₁) to the minimum of ρ

_j(t₁) and the value of CCR in the RM cell received.

4. A method as recited in claim 1, further comprising the steps of estimating the bandwidth of each connection from its actual bandwidth usage.

5. A method as recited in claim 1, further comprising the steps of estimating the available bandwidth on an output link carrying said connections.

6. A method as recited in claim 1, further comprising the steps of recovering bandwidth from connections that remain idle for specified periods.

7. A congestion control method for communications networks having a plurality of connections to switches, wherein each connection has a current transmission rate, wherein the source of each connection requests a specific amount of bandwidth to be allocated to the connection by the switches on its path to the destination, and wherein requests for bandwidth allocation are carried by resource management (RM) cells transmitted periodically by the source, comprising the steps of:

(a) estimating the current transmission rate of each connection by measuring the time interval between the reception of a plurality of resource management (RM) cells from the given connection;

(b) allocating bandwidth using said estimated transmission rate as the requested rate;

(c) setting the current transmission rate of a connection equal to n_j/t_j if n_j cells from a connection j are received during an interval t_j in which said plurality RM cells were received; and

(d) designating a connection for which a max-min fairness rate for that connection is less than the minimum cell rate (MCR) for that connection as a MCR-limited connection; and

(e) allocating bandwidth to said MCR-limited connection equal to said connection'"'"'s MCR to satisfy a minimum rate requirement for that connection.

8. A method as recited in claim 7, further comprising the steps of updating the actual bandwidth allocation maintained for a connection j wherein the new allocation A_j(t₁) for connection j is determined according to the steps comprising,

(i) if the maximum allocation A_max(t₁) is less than the MCR of the connection, setting A_j(t₁) to A_max(t₁),

(ii) if the maximum allocation A_max(t₁) is less than both the request ρ _j(t₁) and the value of CCR in the RM cell received, setting A_j(t₁) to A_max(t₁), and

(iii) if the computed A_max(t₁) is equal to or more than the minimum of ρ

_j(t₁) and the value of CCR in the RM cell received, setting A_j(t₁) to the minimum of ρ

_j(t₁) and the value of CCR in the RM cell received.

9. A method as recited in claim 8, further comprising the steps of estimating the bandwidth of each connection from its actual bandwidth usage.

10. A method as recited in claim 9, further comprising the steps of estimating the available bandwidth on an output link carrying said connections.

11. A method as recited in claim 10, further comprising the steps of recovering bandwidth from connections that remain idle for specified periods.

12. A congestion control method for communications networks having a plurality of connections to switches, wherein each connection has a current transmission rate, wherein the source of each connection requests a specific amount of bandwidth to be allocated to the connection by the switches on its path to the destination and wherein requests for bandwidth allocation are carried by resource management (RM) cells transmitted periodically by the source, said RM cells having a minimum cell rate (MCR) comprising the steps of:

(a) estimating the current transmission rate of each connection by measuring the time interval between the reception of a plurality of resource management (RM) cells from the given connection;

(b) allocating bandwidth using said estimated transmission rate as the requested rate;

(c) setting the current transmission rate of a connection equal to n_j/t_j if n_j cells from a connections j are received during an interval t_j in which said plurality RM cells were received;

(d) designating a connection for which a max-min fairness rate for that connection is less than the MCR for that connection as a MCR-limited connection;

(e) allocating bandwidth to said MCR-limited connection equal to said connection'"'"'s MCR to satisfy a minimum rate requirement for that connection;

(f) updating the actual bandwidth allocation maintained for a connection j wherein the new allocation A_j(t₁) for connection j is determined according to the steps comprising,

(i) if the maximum allocation A_max(t₁) is less than the MCR of the connection, setting A_j(t₁) to A_max(t₁),

(ii) if the maximum allocation A_max(t₁) is less than both the request ρ

_j(t₁) and the value of CCR in the RM cell received, setting A_j(t₁) to A_max(t₁), and

(iii) if the computed A_max(t₁) is equal to or more than the minimum of ρ

_j(t₁) and the value of CCR in the RM cell received, setting A_j(t₁) to the minimum of ρ

_j(t₁) and the value of CCR in the RM cell received,

(g) estimating the bandwidth of each connection from its actual bandwidth usage;

(h) estimating the available bandwidth on an output link carrying said connections; and

(i) recovering bandwidth from connections that remain idle for specified periods.

13. A congestion control method for communications networks having a plurality of connections to switches, wherein each connection has a current transmission rate, wherein the source of each connection requests a specific amount of bandwidth to be allocated to the connection by the switches on its path to the destination, and wherein requests for bandwidth allocation are carried by resource management (RM) cells transmitted periodically by the source, comprising the steps of:

(a) estimating the current transmission rate of each connection by measuring the time interval between the reception of a plurality of resource management (RM) cells from the given connection;

(b) allocating bandwidth using said estimated transmission rate as the requested rate; and

(c) updating the actual bandwidth allocation maintained for a connection j wherein the new allocation A_j(t₁) for connection j is determined according to the steps comprising,

(i) if the maximum allocation A_max(t₁) is less than the minimum cell rate (MCR) of the connection, setting A_j(t₁) to A_max(t₁),

(ii) if the maximum allocation A_max(t₁) is less than both the request ρ

_j(t₁) and the value of current cell rate (CCR) in the RM cell received, setting A_j(t₁) to A_max(t₁), and

(iii) if the computed A_max(t₁) is equal to or more than the minimum of ρ

_j(t₁) and the value of CCR in the RM cell received, setting A_j(t₁) to the minimum of ρ

_j(t₁) and the value of CCR in the RM cell received.

14. A method as recited in claim 13, further comprising the steps of setting the current transmission rate of a connection equal to n_j/t_j if n_j cells from a connection j are received during an interval t_j in which said plurality RM cells were received.

15. A method as recited in claim 13, wherein said RM cells include a minimum cell rate (MCR), and further comprising the steps of:

(d) designating a connection for which a max-min fairness rate for that connection is less than the MCR for that connection as a MCR-limited connection; and

(e) allocating bandwidth to said MCR-limited connection equal to said connection'"'"'s MCR to satisfy a minimum rate requirement for that connection.

16. A method as recited in claim 13, further comprising the steps of estimating the bandwidth of each connection from its actual bandwidth usage.

17. A method as recited in claim 13, further comprising the steps of estimating the available bandwidth on an output link carrying said connections.

18. A method as recited in claim 13, further comprising the steps of recovering bandwidth from connections that remain idle for specified periods.