Adaptive rate-based congestion control in packet networks

• US 5,936,940 A
• Filed: 08/22/1996
• Issued: 08/10/1999
• Est. Priority Date: 08/22/1996
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Huynh, Lap T., Gun, Levent, Marin, Gerald Arnold, Vu, Ken Van, Lin, Bouchung, Onvural, Raif O.
• Primary Examiner(s): Kizou, Hassan
• Application Number:
  US08/701,624
• Time in Patent Office: 1,083 Days
• Field of Search: 370/229, 370/230, 370/232, 370/235, 370/236, 370/237, 370/238, 370/395, 370/396, 370/400, 370/465, 370/231, 370/233, 370/234, 370/389, 395/200.64, 395/200.65, 395/200.68
• US Class Current: 370/232
• CPC Class Codes: H04L 12/5602 Bandwidth control in ATM Networks, e.g. leaky bucket
• CPC Class Codes: H04L 2012/5619 Network Node Interface, e.g. tandem connections, transit switching
• CPC Class Codes: H04L 2012/5636 Monitoring or policing, e.g. compliance with allocated rate, corrective actions

Abstract

An enhanced adaptive rate-based congestion control system for packet transmission networks uses the absolute rather than the relative network queuing delay measure of congestion in the network. Other features of the congestion control system include test transmissions only after a predetermined minimum time, after the receipt of an acknowledgment from the previous test, or transmission of a minimum data burst, whichever takes longest. The congestion control system also provides a small reduction in rate at low rates and a large reduction in rates at high rates. A logarithmic rate control function provides this capability. Rate damping is provided by changing all of the values in a rate look-up tables in response to excessive rate variations. Finally, the fair share of the available bandwidth is used as the starting point for rates at start-up or when a predefined rate damping region is exited.

Claims

1. A packet transmission network comprising

a plurality of transmission nodes interconnected by transmission links,

a plurality of user applications for transmitting data streams on said network, said data streams including data streams requiring reserved data paths of predefined levels of service quality and data streams requiring best efforts transmission paths,

means for selecting reserved data paths through said network between pairs of said user applications wherein said reserved data paths have said guaranteed pre-defined levels of service quality,

means for transmitting best efforts data on said best efforts transmission paths during those times when said reserved data paths are partially idle,

means for controlling the access of said best efforts data to said network in order to prevent interference with data on said reserved data paths, said means for controlling the access of said best efforts data comprising

means for detecting the level of congestion in said network,

table driven means for controlling the rate of said best efforts data in response to said level of congestion, and

means for multiplicatively changing the values in said table driven means in response to excessive changes in said rate of said best efforts data.

2. The packet transmission network according to claim 1 wherein said means for detecting congestion in said network comprises

means for estimating the absolute value of the queuing delay in said network.

3. The packet transmission network according to claim 1 further comprising

means for inserting a spacer between successive cells of said best efforts data.

4. The packet transmission network according to claim 3 wherein said spacer length is responsive to a time-out function, an acknowledgment, or the transmission of a minimum burst of said best efforts traffic, whichever occurs first.

5. The packet transmission network according to claim 1 wherein said means for determining the congestion in said network comprises

means for transmitting a series of test samples through said network each having a time stamp containing the time of launch,

means for comparing successive test samples to determine total delay through said network, and

means for determining the minimum value of said total delay through said network for the duration of a connection.

6. The packet transmission network according to claim 1 further comprising

means for reducing said rate of said best efforts data by a first value when said rate is less than a predetermined value, and

means for reducing said rate of said best efforts data by a second value greater than said first value when said rate is at a higher value than said predetermined value.

7. The packet transmission network according to claim 1 further comprising

means for initializing said rate of said best efforts data at the fair share value of the currently available bandwidth in said network.

8. A method for transmitting maximum data on a packet transmission network comprising the steps of

interconnecting a plurality of transmission nodes by transmission links,

transmitting data streams from a plurality of user applications on said network, said data streams including reserved path data streams requiring guaranteed levels of transmission quality and best efforts data streams requiring only the best efforts available levels of transmission quality,

selecting reserved data paths through said network between pairs of said user applications wherein said reserved data paths have said guaranteed levels of service quality,

transmitting best efforts data on said network during those times when said reserved data paths are partially idle,

controlling the access of said best efforts data to said network in order to prevent interference with data on said reserved data paths, said step of controlling the access of said best efforts data comprising the steps of

detecting the level of congestion in said network,

controlling by means of a look-up table the rate of said best efforts data in response to said level of congestion, and

multiplicatively changing the values in said table driven means in response to excessive changes in said rate of said best efforts data.

9. The method according to claim 8 wherein said step of detecting congestion in said network comprises the steps of

estimating the absolute value of the queuing delay in said network.

10. The method according to claim 8 further comprising the step of

inserting a spacer between successive cells of said best efforts data.

11. The method according to claim 10 wherein said step of inserting a spacer comprises the step of

selecting said spacer length in response to a time-out function, to an acknowledgment, or to the transmission of a minimum burst of said best efforts traffic, whichever occurs first.

12. The method according to claim 8 wherein said step of determining the congestion in said network comprises the steps of

transmitting a series of test samples through said network each having a time stamp containing the time of launch,

comparing successive test samples to determine total delay through said network, and

determining the minimum value of said total delay through said network during the duration of a connection.

13. The method according to claim 8, further comprising the steps of

reducing said rate of said best efforts data by a first smaller value when said rate is less than a predetermined value, and

reducing said rate of said best efforts data by a second value greater than said first value when said rate is at a higher value than said predetermined value.

14. The method according to claim 8 further comprising the step of

initializing said rate of said best efforts data at the fair share value of the currently available bandwidth in said network.

15. A packet network access system having an instantaneously variable available transmission capacity at any time, said access system comprising

means for detecting the level of congestion in said network,

means for controlling the rate of data transmission into said network in response to said level of congestion,

means for initializing said rate of data transmission into said network at a fair share of the transmission capacity available on said network at the time of initialization,

means for reducing said rate of transmission by a first smaller value when said rate of transmission is less than a predetermined value, and

means for reducing said rate of of transmission by a second value greater than said first value when said rate of transmission is at a higher value than said predetermined value.

16. A packet network access method for a packet network having an instantaneously variable available transmission capacity at any time, said access method comprising the steps of

detecting the level of congestion in said network by transmitting a series of test samples through said network each having a time stamp containing the time of launch, and comparing successive test samples to determine total delay through said network, and determining the minimum value of said total delay through said network for the duration of a connection,

controlling the rate of data transmission into said network in response to said level of congestion, and

initializing said rate of data transmission into said network at a fair share of the transmission capacity available on said network at the time of initialization.

17. The packet network access method according to claim 16 further comprising the steps of

reducing said rate of transmission by a first smaller value when said rate of transmission is less than a predetermined value, and

reducing said rate of transmission by a second value greater than said first value when said rate of transmission is at a higher value than said predetermined value.