Flow and congestion control in packet switched networks

• US 6,061,330 A
• Filed: 09/15/1998
• Issued: 05/09/2000
• Est. Priority Date: 03/15/1996
• Status: Expired due to Term

• Current Assignee: Telefonaktiebolaget LM Ericsson
• Original Assignee: Telefonaktiebolaget LM Ericsson
• Inventors: Johansson, Per Gunnar
• Primary Examiner(s): Horabik, Michael
• Assistant Examiner(s): JONES, PRENELL P
• Application Number:
  US09/153,738
• Time in Patent Office: 602 Days
• Field of Search: 370/235, 370/236, 370/231, 370/230, 370/232, 370/233, 370/234, 370/252, 370/253, 395/200.63, 395/203.65
• US Class Current: 370/229
• CPC Class Codes: H04L 12/5602 Bandwidth control in ATM Networks, e.g. leaky bucket
• CPC Class Codes: H04L 2012/5636 Monitoring or policing, e.g. compliance with allocated rate, corrective actions
• CPC Class Codes: H04L 2012/5672 Multiplexing, e.g. coding, scrambling
• CPC Class Codes: H04L 2012/5679 Arbitration or scheduling
• CPC Class Codes: H04L 49/3081 ATM peripheral units, e.g. policing, insertion or extraction

Abstract

A control system in an ATM system controls flows of data cells and flow control management cells from a number of sources to a destination over connections passing a network element. The flow control management cells are returned from the destination via the network element to their respective sources. The network element is exposed to congestion due to contention between the connections, that necessitates queuing of the connections. The flow control management cells have an explicit rate field for an explicit rate value used to limit a source maximum allowed cell rate to a specific value. An operating function uses deviations from an available rate value for lower priority cells and from a queue length reference forming a desirable queue length, to calculate a modified explicit rate value as a function of these deviations. This modified explicit rate value is introduced into the explicit rate field of the backward flow control management cells.

Claims

1. A method in an ATM system for controlling flows of data cells and flow control management cells from a number of sources to a destination over connections passing a network element, while returning the flow control management cells from the destination via the network element to their respective sources,

said network element being exposed to congestion due to contention between the connections, said contention necessitating queuing of the connections,

said data cells including lower priority cells and higher priority cells, and said flow control management cells having an explicit rate field for an explicit rate value used to limit a source maximum allowed cell rate to a specific value, and a current cell rate field for receiving said specific value,

comprising performing in the network element the steps of

counting a predetermined number of higher priority cells due to be sent on an output link from the network element to the destination while keeping track of the time interval taken for performing the counting to produce a higher priority cell rate in the form of a ratio between the counted higher priority cells and the time interval,

calculating an available rate value for lower priority cells as a difference between a total available link rate value and the higher priority cell rate,

establishing a queue length reference forming a desirable queue length,

calculating deviations from the available rate value and the queue length reference due to receiving varying amounts of cells on contending connections,

calculating a modified explicit rate value as a function of these deviations, and

introducing the modified explicit rate value into the explicit rate field of the backward flow control management cells.

2. The method according to claim 1, comprising performing in the network element further steps of

counting cells arriving from the respective sources to produce source specific cell counts,

counting the source specific cell counts to produce a determined total count of received cells while keeping track of the time interval taken for performing the counting to produce an offered rate value as a ratio between the determined total count value and a time interval,

calculating a total queue length for all arriving cells,

calculating the deviation from the available rate value as a difference between the available rate value and the offered rate value,

calculating the deviation from the queue length reference as a difference between the total queue length and the queue length reference.

3. The method according to claim 2, comprising performing in the network element the further steps of

keeping track of a first condition implying that received current cell rate field values are equal to or higher than a threshold value and a second condition implying that a limit number of received current cell rate field values lower than the threshold value has been exceeded,

calculating, provided that any of these conditions is fulfilled, a contention rate as an exponential averaging of the current cell rate field values,

performing the calculation of the explicit rate value while using the contention rate as a multiplication factor.

4. The method according to claim 2 or 3, comprising performing in the network element a further step of multiplying the deviations from the available rate value and the queue length value each by a proportional constant.

5. The method according to claim 4, comprising performing in the network element the further step of determining the values of respective constants of each pair of proportional constants a and b for each connection j as depending upon the propagation delay in a loop extending over the source and the network element.

6. The method according to claim 2, comprising performing in the network element the further step of decreasing the available rate value by means of a multiplication factor.

7. The method according to claim 2, comprising performing in the network element further steps of counting queuing cells arriving from the respective sources to produce source specific queuing cell counts, and calculating the total queue length by summing all source specific queuing cell counts.

8. The method according to claim 2, comprising performing in the network element further steps of counting cells arriving from the respective sources to produce source specific cell counts, calculating the total queue length by summing these counts and subtracting therefrom the amount of 1 for each cell that is sent on the output link.

9. The control system in an ATM system for controlling flows of data cells and flow control management cells from a number of sources to a destination over connections passing a network element, while returning the flow control management cells from the destination via the network element to their respective sources,

said network element being exposed to congestion due to contention between the connections, said contention necessitating queuing of the connections,

said data cells including lower priority cells and higher priority cells, and said flow control management cells having an explicit rate field for an explicit rate value used to limit a source maximum allowed cell rate to a specific value, and a current cell rate field for receiving said specific value,

comprising

means for counting a predetermined number of higher priority cells due to be sent on an output link from the network element to the destination while keeping track of the time interval taken for performing the counting to produce a higher priority cell rate in the form of a ratio between the counted higher priority cells and the time interval, and

means for calculating an available rate value for lower priority cells as a difference between a total available link rate value and the higher priority cell rate,

establishing a queue length reference forming a desirable queue length,

calculating deviations from the available rate value and the queue length reference due to receiving varying amounts of cells on contending connections,

calculating a modified explicit rate value as a function of these deviations, and

introducing the modified explicit rate value into the explicit rate field of the backward flow control management cells.

10. The system according to claim 9, comprising

means for counting cells arriving from the respective sources to produce source specific cell counts,

means for counting the source specific cell counts to produce a determined total count of received cells while keeping track of the time interval taken for performing the counting to produce an offered rate value as a ratio between the determined total count value and a time interval, and

means for

calculating a total queue length for all arriving cells,

calculating the deviation from the available rate value as a difference between the available rate value and the offered rate value,

calculating the deviation from the queue length reference as a difference between the total queue length and the queue length reference.

11. The system according to claim 10, comprising means for

keeping track of a first condition implying that received current cell rate field values are equal to or higher than a threshold value and a second condition implying that a limit number of received current cell rate field values lower than the threshold value has been exceeded,

calculating, provided that any of these conditions is fulfilled, a contention rate as an exponential averaging of the current cell rate field values,

performing the calculation of the explicit rate value while using the contention rate as a multiplication factor.

12. The system according to claim 9 or 10, comprising means for multiplying the deviations from the available rate value and the queue length value each by a proportional constant.

13. The system according to claim 12, comprising means for determining the values of respective constants of each pair of proportional constants a and b for each connection as depending upon the propagation delay in a loop extending over the source and the network element.

14. The system according to claim 10, comprising means for performing in the network element the further step of decreasing the available rate value by means of a multiplication factor.

15. The system according to claim 10, comprising means for counting queuing cells arriving from the respective sources to produce source specific queuing cell counts, and calculating the total queue length by summing all source specific queuing cell counts.

16. The system according to claim 10, comprising means for counting cells arriving from the respective sources to produce source specific cell counts, calculating the total queue length by summing these counts and subtracting therefrom the amount of 1 for each cell that is sent on the output link.

17. A method in an ATM system for controlling slows of data cells and flow control management cells from a number of sources to a destination over connections passing an output buffer of a switch, while returning the flow control management cells from the destination via the switch to their respective sources,

said output buffer being exposed to congestion due to contention between the connections, said contention necessitating queuing of the connections,

said data cells including lower priority cells and higher priority cells, and said flow control management cells having an explicit rate field for an explicit rate value used to limit a source maximum allowed cell rate to a specific value, and a current cell rate field for receiving said specific value,

comprising performing the steps of

obtaining values of a set of parameters and variables including

y(t):

a contention rate at the output buffer at time t,

y_tot (t);

a measured offered rate to the output buffer at time t,

C(t);

available rate at the buffer for lower priority cells at time t,

Q(t);

total queue length at the buffer at time t,

p;

fraction of an available rate at the buffer strived for,

M;

a buffer queue length reference,

a_i and b_i ;

proportional constants for a connection i passing the output buffer,

determining the explicit rate value x_i (t) at time t for the connection i as x_i t=y(t)[1-a_i {1-pC(t)/y_tot (t)}-b_i {Q(t)-M/y_tot (t)}], where i is an integer, and

assigning the explicit rate value x_i t to the explicit rate field of a backward flow control management cell.

18. The method according to claim 17, comprising

counting cells arriving from the respective sources to produce source specific cell counts,

counting the source specific cell counts to produce a determined total count value of received cells while keeping track of the time interval taken for performing the counting to produce the offered rate value y_tot (t) as a ratio between the determined total count value and the time interval.

19. The method according to claim 18, comprising

keeping track of a first condition implying that received current cell rate field values are equal to or higher than a threshold value and a second condition implying that a limit number of received current cell rate field values lower than the threshold value has been exceeded,

calculating, provided that any of these conditions is fulfilled, the contention rate (y(t)) as an exponential averaging of the current cell rate field values.

20. The method according to claim 19, comprising determining the values of the respective constants a_i and b_i as depending upon the propagation delay in a loop extending over the switch and the source from which the connection i starts.

21. The method according to claim 18, comprising counting queuing cells arriving from the respective sources to produce source specific queuing cell counts, and calculating the total queue length by summing all source specific queuing cell counts.

22. The method according to claim 18, comprising counting cells arriving from the respective sources to produce source specific cell counts, and calculating the total queue length by summing these counts and subtracting therefrom the amount of 1 for each cell that is sent on the output link.

23. A method in an ATM system for controlling flows of data cells and resource management cells from a number of sources to a destination over connections passing a respective input buffer and a common output buffer of a fair queuing switch, while returning the resource management cells as backward resource management cells from the destination via the switch to the respective sources,

said switch being exposed to congestion due to contention between the connections, said contention necessitating queuing of the connections in the input buffers and the output buffer,

said resource management cells having an explicit rate field for an explicit rate value used to limit a source maximum allowed cell rate to a specific value, comprising

obtaining values of a set of parameters and variables including

r_j (t):

output rate at time (t) at the input buffer for connection j,

p(t);

total load at time (t) on output from the input buffer calculated as the quotient number of ABR cells received at the input buffer per time unit/number of occasions to send an ABR cell per time unit,

pref;

desired load on output from the input buffer,

Q_j (t);

queue length at time (t) at the input buffer for connection j,

M_j ;

queue length reference at the input buffer for connection j,

a and b;

proportional constants for connection j,

determining the explicit rate value x_j (t) at time t for the connection j as

space="preserve" listing-type="equation">x.sub.j (t)-max(r.sub.j (t))[1-a{1-pref/p(t)}-b{Q.sub.j (t)-M/max(r.sub.j (t))}]

wherein max(r_j (t)) is an operation performed on the individual connection output rates r_j (t) of the switch in order to find a common output rate for the connections passing the common output buffer and thus avoid a divergence in the individual connection rates, and j is an integer, and

assigning the explicit rate value x_jt to the explicit rate field of a backward resource management cell passing the input buffer j.

24. The method according to claim 23, comprising determining the values of the constants a and b as depending upon the propagation delay in a loop extending over the source and the switch.