Method and apparatus for controlling data transfer rate using virtual queues in asynchronous transfer mode networks

• US 6,021,116 A
• Filed: 11/15/1996
• Issued: 02/01/2000
• Est. Priority Date: 03/28/1996
• Status: Expired due to Term

• Current Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Xia, Ye, Kumar, Vijay Pochampalli, Chiussi, Fabio Massimo
• Primary Examiner(s): Patel, Ajit
• Application Number:
  US08/751,064
• Time in Patent Office: 1,173 Days
• Field of Search: 370/229, 370/230, 370/331, 370/232, 370/233, 370/234, 370/235, 370/236, 370/237, 370/252, 370/253, 370/259
• US Class Current: 370/236
• CPC Class Codes: H04L 12/5602 Bandwidth control in ATM Networks, e.g. leaky bucket
• CPC Class Codes: H04L 2012/5635 Backpressure, e.g. for ABR
• CPC Class Codes: H04L 2012/5636 Monitoring or policing, e.g. compliance with allocated rate, corrective actions
• CPC Class Codes: H04Q 11/0478 Provisions for broadband connections

Abstract

A method and apparatus for computing a congestion indicator in a communications switch including monitoring at least one first congestion indicator in the communication switch, computing an arrival rate and a first and a second service rate, incrementing a second congestion indicator using the arrival rate, and decrementing the second congestion indicator using the first and second service rates. The method and apparatus are used for deciding to store the data and electronic code that arrives at a communications switch when the second congestion indicator is below a first threshold, and for deciding not to store the data and electronic code that arrives at a communications switch when the second congestion indicator equals or exceeds the first threshold. The method and apparatus are also used for controlling the data transfer rates of data sources in an ATM-based network when both available bit rate and other traffic is present in a communications switch. The method and the apparatus utilize intelligent marking to identify data sources with data transfer rates exceeding a marking threshold and direct those data sources to reduce their data transfer rates when the second congestion indicator exceeds a second threshold. When the second congestion indicator exceeds a third threshold or the first congestion indicator exceeds a fourth threshold, the method and apparatus direct all the data sources to reduce their data transfer rates. The marking threshold equals a function of the maximum data transfer rate multiplied by a function of the second congestion indicator.

Claims

1. A method for determining a congestion indicator in a communications switch, the communications switch receiving data and electronic code from at least one other communication switch and a data source and a transmitting data and electronic code to at least one other communications switch containing at least one buffer memory for storing data and electronic code awaiting transmission to at least one other communications switch and a destination, the method comprising:

monitoring at least one first congestion indicator in the communications switch;

updating the at least one first congestion indicator as the communications switch receives data and electronic code from the at least one other communications switch and the data source and transmits data and electronic code to the at least one other communications switch, the data source, and the destination; and

updating at least one second congestion indicator, wherein the at least one second congestion indicator is incremented by an arrival rate and is decremented by one of a first service rate and a second service rate.

2. The method of claim 1, wherein the arrival rate of the at least one second congestion indicator is equal to 1 when the communications switch receives a specified amount of data from at least one data source, the arrival rate of the at least one second congestion indicator is equal to 0 when the communications switch does not receive a specified amount of data from at least one data source, the first service rate of the at least one second congestion indicator is equal to 1 when the communications switch transmits a specified amount of data to the at least one other communications switch and the destination, and the first service rate of the at least one second congestion indicator is equal to 0 when the communications switch does not transmit a specified amount of data to the at least one other communications switch and the destination.

3. The method of claim 1, wherein the arrival rate of the at least one second congestion indicator is a first function of at least one of data and electronic code received by the communications switch and the first service rate of the at least one second congestion indicator is a function of the at least one of data and electronic code received by the communications switch.

4. The method of claim 1, wherein the first service rate of the at least one second-congestion indicator is a function of at least the data rate of at least one of the data sources.

5. The method of claim 1, wherein the switch receives electronic code from the data sources, the electronic code comprising data transfer rate information, and the arrival rate of the at least one second congestion indicator is a function of the data transfer rate information in the electronic code.

6. The method of claim 1, wherein the first service rate and the second service rate of the at least one second congestion indicator are equal.

7. The method of claim 1, wherein the second service rate of the at least one second congestion indicator is a function of the at least one first congestion indicator.

8. The method of claim 7, wherein the function of the at least one first congestion indicator is a linear function.

9. The method of claim 7, wherein the function of the first congestion indicator is a non-linear function.

10. The method of claim 1, wherein the second service rate of the at least one second congestion indicator is a function of a total buffer memory available in the communications switch.

11. The method of claim 10, wherein the function of the total buffer memory available in the communications switch is a linear function.

12. The method of claim 10, wherein the function of the total buffer memory available in the communications switch is a non-linear function.

13. The method of claim 1, wherein a plurality of first congestion indicators are monitored and updated and at least one second congestion indicator is updated every time at least one first congestion indicator in the plurality of the first congestion indicators is updated.

14. The method of claim 13, wherein the arrival rate of the at least one second congestion indicator is a function of a plurality of first congestion indicators and of the data transfer rate of at least one data source, and the first service rate of the at least one second congestion indicator is an function of the plurality of first congestion indicators and of the data transfer rate of at least one data source.

15. The method of claim 1, wherein the communications switch receives the data and electronic code and stores the data and electronic code in the buffer memory when the at least one second congestion indicator is below at least one first threshold, and the communications switch receives the data and electronic code and does not store the data and electronic code in the buffer memory when the at least one second congestion indicator is greater than or equal to the at least one first threshold.

16. The method of claim 1, wherein the method is used in an asynchronous transfer mode-based network for controlling data transfer rates of data sources, the method further comprising:

transmitting electronic code comprising data transfer rate information from at least the communications switch to a first group of data sources, each one of the data sources in the first group of data sources having a data transfer rate greater than or equal to a communications switch marking threshold, the communications switch marking threshold being equal to a first function of at least one communications switch maximum data transfer rate multiplied by a second function of at least the second congestion indicator, when the at least one second congestion indicator equals or exceeds a first threshold;

transmitting electronic code comprising data transfer rate information from at least the communications switch to a second group of data sources, each one of the data sources in the second group of data sources having a data transfer rate lower than the communications switch marking threshold when the at least one second congestion indicator equals or exceeds a first threshold, wherein the data transfer rate information transmitted to the first group of data sources is used by each one of the data sources in the first group of data sources to reduce its data transfer rate, the data transfer rate information transmitted to the second group of data sources is used by each one of the data sources in the second group of data sources to increase its data transfer rate;

transmitting electronic code from the communications switch to all the data sources when the at least one second congestion indicator equals or exceeds a second threshold, wherein the data transfer rate information transmitted to all of the data sources when the at least one second congestion indicator equals or exceeds a second threshold is used by each data source to reduce its data transfer rate; and

transmitting electronic code from the communications switch to all the data sources when the at least one second congestion indicator is lower than the first threshold, wherein the data transfer rate information transmitted to all of the data sources when the at least one second congestion indicator is lower than the first threshold is used by each data source to increase its data transfer rate.

17. The method of claim 16, further comprising transmitting electronic code from the communications switch to all the data sources when the at least one first congestion indicator is greater than or equal to a third threshold, wherein the data transfer rate information transmitted to all of the data sources when the at least one second congestion indicator is greater or equal than the third threshold is used by each data source to decrease its data transfer rate.

18. The method of claim 17, wherein the at least one communications switch maximum data transfer rate and at least one data source identifier are updated after the communications switch receives electronic code comprising data transfer rate information from at least one data source, the at least one data source identifier identifying at least one data source having a data transfer rate equal to the at least one communications switch maximum data transfer rate.

19. The method of claim 17, wherein the at least one communications switch maximum data transfer rate and at least one data source identifier are updated after the communications switch fails to receive the electronic code from at least one data source, the at least one data source identifier identifying at least one data source having a data transfer rate equal to the communications switch maximum data transfer rate.

20. The method of claim 17, wherein updating the at least one communications switch maximum data transfer rate and the at least one data source identifier is not dependent upon the electronic code received from the at least one data source.

21. The method of claim 17, wherein the first function used to determine the communications switch marking threshold is a linear function of the at least one communications switch maximum data transfer rate.

22. The method of claim 17, where the first function used to determine the communications switch marking threshold is a running exponential weighted average of the at least one communications switch maximum data transfer rate and the data transfer rate information received in the electronic code.

23. The method of claim 17, wherein the first function used to determine the communications switch marking threshold is determined when the data transfer rate in the electronic code of at least one of the data sources equals the communications switch maximum transfer rate multiplied by a first variable.

24. The method of claim 23, wherein the first variable is a fraction of the number one.

25. The method of claim 23, wherein the first variable equals one.

26. The method of claim 17, wherein the second function used to determine the communications switch marking threshold is a linear function of at least the second congestion indicator.

27. The method of claim 17, wherein the second function used to determine the communications switch marking threshold is a non-linear function of at least the second congestion indicator.

28. The method of claim 17, wherein the second function used to determine the communications switch marking threshold is a function of the total buffer memory available in the communications switch.

29. The method of claim 17, wherein the second function used to determine the communications switch marking threshold is a function of at least one third congestion indicator.

30. The method of claim 29 wherein the third congestion indicator is a function of an amount of data traffic and an amount of electronic code received in a specified interval.

31. The method of claim 30, wherein the specified interval is continuously updated.

32. The method of claim 17, wherein the at least one first congestion indicator is a function of at least one queue length in the communications switch.

33. The method of claim 17, wherein the at least one first congestion indicator is a function of the total available buffer memory in the communications switch.

34. The method of claim 17, wherein the data sources include one of available bit rate data sources and non-available bit rate data sources.

35. The method of claim 34, further comprising assigning a first priority to the electronic code received at the communications switch from the available bit rate data sources, the first priority greater than a second priority of the non-available bit rate data sources.

36. An apparatus for determining a congestion indicator in a communications switch, the communications switch receiving data and electronic code from at least one other communications switch and a data source and transmitting data and electronic code to at least one of the other communications switch and a destination, the communications switch containing at least one buffer memory for storing data and electronic code awaiting transmission to the at least one other communications switch and the destination, the apparatus comprising:

a first congestion indicator register that stores at least one first congestion indicator;

a second congestion indicator register that stores a second congestion indicator;

a first controller for monitoring and for updating the at least one first congestion indicator, for determining an arrival rate, for determining a first service rate, for determining a second service rate, for incrementing the at least one second congestion indicator using the arrival rate, for decrementing the at least one second congestion indicator using the first ad the second service rate, and for monitoring the at least one second service rate, and for monitoring the at least one second congestion indicator as the communications switch receives data and electronic code from the at least one other communications switch and the data source and transmits data and electronic code to the at least one other communications switch, the data source, and the destination.

37. The apparatus of claim 36, further comprising means for monitoring a total buffer memory available in the communications switch.

38. The apparatus of claim 36, further comprising means for monitoring an amount of data and an amount of electronic code received in a specified interval.

39. The apparatus of claim 36, further comprising a second controller, the second controller storing the data and electronic code in the buffer memory when the at least one second congestion indicator is below at least one first threshold, and the second controller not storing the data traffic and electronic code in the buffer when the at least one second congestion indicator is greater than or equal to the at least one first threshold.

40. The apparatus of claim 36, wherein the apparatus further comprises:

a first data transfer rate register that indicates at least one communications switch maximum data transfer rate;

a second data transfer rate register that indicates data transfer rate information from at least one data source;

a data source identifying register that provides a data source identifier that indicates at least one data source having a data transfer rate equal to the switch maximum data transfer rate;

a time-out register that indicates a time-out, the time-out being a maximum period of time within which the communications switch maximum data transfer rate must be updated;

a transmitter for transmitting electronic code comprising data transfer rate information to the data sources; and

a second controller for monitoring the at least one second congestion indicator, the at least one communications switch maximum data transfer rate, the time-out, and the data source identifier, the second controller updating the at least one communications switch maximum data transfer rate, the time-out and the data source identifier, and controlling the transmitter to transmit the electronic code to a first group of data sources, each of the data sources in the first group of data sources having a data transfer rate at least equal to a communications switch marking threshold, the communications switch marking threshold being equal to a first function of the at least one communications switch maximum data transfer rate multiplied by a second function of the at least one second congestion indicator when the at least one second congestion indicator equals or exceeds a first threshold, the second controller controlling the transmitter to transmit the electronic code to a second group of data sources, each of the data sources in the second group of data sources having a data transfer rate lower than a communications switch marking threshold, the communications switch marking threshold being equal to the first function of the at least one communications switch maximum data transfer rate multiplied by the second function of the at least one second congestion indicator when the at least one second congestion indicator equals or exceeds the first threshold, the second controller controlling the transmitter to transmit electronic code to all the data sources when the at least one second congestion indicator equals or exceeds a second threshold, the second controller controlling the transmitter to transmit electronic code to all the data sources when the at least one second congestion indicator is lower than the first threshold, and the second controller controlling the transmitter to transmit electronic code to all the data sources when the at least one first congestion indicator is greater than or equal to a third threshold, wherein the data transfer rate information transmitted to the first group of data sources when the at least one second congestion indicator equals or exceeds the first threshold is used by each one of the data sources in the first group of data sources to reduce its data transfer rate, the data transfer rate information transmitted to the second group of data sources when the at least one second congestion indicator equals or exceeds the first threshold is used by each one of the data sources in the second group of data sources to increase its data transfer rate, wherein the data transfer rate information is transmitted to all data sources when the at least one second congestion indicator equals or exceeds the second threshold to reduce the data transfer rates of all the data sources, wherein the data transfer rate information is transmitted to all data sources when the at least one second congestion indicator is lower than the first threshold to increase the data transfer rates of all the data sources, and wherein the data transfer rate information is transmitted to all data sources when the first congestion indicator is greater or equal than the third threshold to decrease the data transfer rates of all the data sources.

41. The apparatus of claim 40, further comprising a receiver for receiving the electronic code from at least one data source, the second controller updating the at least one communications switch maximum data transfer rate and the data source identifier after the receiver receives the electronic code from the one data source, the receiver receiving the electronic code from one of available bit rate data sources and non-available bit rate data sources.

42. The apparatus of claim 40, further comprising a plurality of second congestion indicator registers, each second congestion indicator register storing at least one second congestion indicator, wherein more than one second congestion indicator is compared to the first and second thresholds.

43. The apparatus of claim 40, further comprising means for assigning a first priority to the electronic code received from available bit rate data sources, the first priority equal to a priority for non-available bit rate data sources.

44. The apparatus of claim 40, further comprising a plurality of first congestion indicator registers, each first congestion indicator register storing one first congestion indicator, wherein a plurality of first congestion indicators are compared to the third threshold.