Congestion control for cell networks

• US 5,313,454 A
• Filed: 04/01/1992
• Issued: 05/17/1994
• Est. Priority Date: 04/01/1992
• Status: Expired due to Term

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: StrataCom, Inc. (Cisco Systems, Inc.)
• Inventors: Daley, Patrick D., Corbalis, Charles M., Bustini, Lionel A.
• Primary Examiner(s): Chin, Wellington
• Application Number:
  US07/861,761
• Time in Patent Office: 776 Days
• Field of Search: 370/13, 370/17, 370/94.1, 370/94.2, 370/94.3, 370/60, 370/60.1, 370/58.1, 370/58.2, 370/58.3
• US Class Current: 370/231
• CPC Class Codes: H04L 12/5602 Bandwidth control in ATM Networks, e.g. leaky bucket
• CPC Class Codes: H04L 2012/5614 User Network Interface
• CPC Class Codes: H04L 2012/5619 Network Node Interface, e.g. tandem connections, transit switching
• CPC Class Codes: H04L 2012/563 Signalling, e.g. protocols, reference model
• CPC Class Codes: H04L 2012/5632 Bandwidth allocation
• CPC Class Codes: H04L 2012/5635 Backpressure, e.g. for ABR
• CPC Class Codes: H04L 2012/5638 Services, e.g. multimedia, GOS, QOS
• CPC Class Codes: H04L 2012/5652 Cell construction, e.g. including header, packetisation, depacketisation, assembly, reassembly

Abstract

A feedback control system for congestion prevention in a cell (packet) switching communication network is described. Congestion control is accomplished by controlling the transmission rate of bursty traffic in the presence of high priority, voice, low speed statistical, high speed deterministic and multicast data. Because bursty traffic is relatively insensitive to delay, adequate buffer capacity can be provided at the network nodes in order to minimize bursty data cell loss. By monitoring the buffer queue lengths at the nodes, a control signal can be generated at each intermediate node indicating the state of congestion. Excess queue length indicates incipient congestion while short queue lengths indicate excess capacity. Queue status is forwarded to the destination node where it is interpreted and sent back to the source node as a feedback rate control signal using a 2-bit code. The source node regulates the rate of bursty data transmission over the cell network in accordance with the feedback control signal thus minimizing congestion and concomitant data loss while efficiently utilizing available network bandwidth.

Claims

1. A feedback control system for congestion prevention control on a virtual connection of a cell switching communications network handling bursty traffic, the feedback control system comprising:

a) a source node for accepting, queuing, and buffering user framed bursty data, for formatting the bursty data into bursty data cells, and for transmitting the bursty data cells over the virtual circuit connection through the cell switching communications network at an incrementally variable controllable transmission rate in response to a rate control signal to avoid congestion, wherein the source node and any intermediate node comprising the virtual connection include means for accepting, queuing, and buffering, the bursty data cells, means for detecting incipient congestion in the virtual connection queues and buffers, means for setting an incipient congestion indicator to a first state if incipient congestion is detected and setting the incipient congestion indicator to a second state if incipient congestion is not detected, and means for forwarding the bursty data cells over the virtual connection together with the incipient congestion indicator; and

b) a destination node, which is a terminus of the virtual connection, for accepting the bursty data cells and the incipient congestion indicator, for reconstructing, formatting, and outputting the framed bursty data, for monitoring the incipient congestion indicator, for generating the rate control signal based on the incipient congestion indicator, for transmitting the rate control signal back to the source node.

2. The feedback control system of claim 1, wherein the source node further comprises means for accepting data and control cells from the destination node using a same virtual connection between the source node and the destination node.

3. The feedback control system of claim 1 wherein the rate control signal is transmitted in a cell header by the destination node over a same virtual connection between the source node and the destination node.

4. The feedback control system of claim 3, wherein the rate control signal is transmitted in a supervisory cell header if no return cell traffic is available.

5. The feedback control system of claim 1, further comprising means for measuring virtual connection round-trip delay times, wherein the measuring means comprise:

a) destination node means for generating a high priority (HP) timestamped cell and for transmitting the HP timestamped cell to the source node;

b) source node means for echoing HP timestamped cell back to the destination node;

c) means for comparing a time-stamp of the HP timestamped cell with a destination node arrival time to determine round-trip delay time.

6. The feedback control system of claim 1, wherein the source node further comprises:

a) cell transmitter rate controller that permits a queued bursty data cell to be transmitted only if an accumulated transmission credit is greater than zero and, if transmission is permitted, decrements the accumulated transmission credit.

b) credit manager for incrementing the accumulated transmission credit each time a prescribed interval of time has elapsed, wherein the prescribed time interval corresponds to a clock period of the assigned cell rate, wherein the accumulated transmission credit is sent to the cell transmitter rate controller.

7. The feedback control system of claim 6, wherein the credit manager further comprises:

a) means for accepting a maximum credit count configuration parameter; and

b) means for limiting the accumulated transmission credit to the maximum credit count configuration parameter.

8. The feedback control system of claim 1, wherein the nodes are two-way nodes using a common virtual connection between source and destination nodes.

9. The feedback control system of claim 1 wherein the user framed data includes frames of data, each frame of data including a multiplicity of cells and a header, each cell including a multiplicity of bits, the multiplicity of bits including a cell loss priority (CLP) bit and wherein the means for accepting, queuing and buffering includes a queue for queuing the bursty data cells and wherein the source node further comprises:

a) means for measuring an instantaneous bit rate of incoming frames of data;

b) means for comparing the instantaneous bit rate of incoming frames of data against a committed burst size (Bc) and against a minimum information rate (MIR);

c) means for setting a data expendable (DE) bit included in the header of each frame for each frame of data having an instantaneous bit rate exceeding Bc and MIR; and

d) means for discarding each frame in which the DE bit is set if the queue length exceeds a threshold length; and

e) means for copying the DE bit of each frame into the CLP bit of each cell associated with the frame.

10. A feedback control system for congestion prevention control on a virtual connection of a cell switching communications network handling bursty traffic, comprising:

a) a source node for accepting, queueing, and buffering user framed bursty data, for formatting the bursty data into bursty data cells, and for transmitting the cells over the virtual circuit connection through the cell switching communications network at an incrementally variable controllable transmission rate wherein the source node and any intermediate node comprising the virtual connection include means for accepting, queueing, and buffering the bursty data cells, means for detecting incipient congestion in the virtual connection queues and buffers, and means for forwarding the bursty data cells over the virtual connection together with an associated incipient congestion indicator; and

b) a destination node, being the terminus of the communication network virtual connection for accepting the bursty data cells and the associated incipient congestion indicator, for reconstructing, formatting, and outputting the framed bursty data, for monitoring the congestion indicators, for creating a four state, two binary bit, rate control signal representing rate increase, rate decrease, fast rate decrease, and no-rate-change messages based on the congestion indicators, transmitting the rate control signal back to the source node, wherein the incrementally controllable transmission rate of the source node is adjusted in response to the rate control signal sent from the destination node in order to minimize congestion.

11. The feedback control system of claim 10 wherein the means for incrementally controlling the transmission rate is responsive to the four state control signal causing an additive fractional increase in response to a rate increase signal, a large fractional multiplicative factor decrease in response to a rate decrease signal, and a small fractional multiplicative factor rate decrease in response to a fast rate decrease signal.

12. The feedback control system of claim 10 wherein the user framed bursty data includes frames of data, each frame of data including a multiplicity of cells and a header, each cell including a multiplicity of bits, the multiplicity of bits including a cell loss priority (CLP) bit and wherein the means for accepting, queuing and buffering includes a queue for queuing the bursty data cells and wherein the source node further comprises:

a) means for measuring an instantaneous bit rate of incoming frames of data;

b) means for comparing the instantaneous bit rate of incoming frames of data against a committed burst size (Bc) and against a minimum information rate (MIR);

c) means for setting a data expendable (DE) bit included in the header of each frame for each frame of data having an instantaneous bit rate exceeding Bc and MIR; and

d) means for discarding each frame in which the DE bit is set if the queue length exceeds a threshold length; and

e) means for copying the DE bit of each frame into the CLP bit of each cell associated with the frame

13. A feedback control system for congestion prevention control on a virtual connection of a cell switching communications network handling bursty traffic, comprising:

a) a source node for accepting, queueing, and buffering user framed bursty data, for formatting the bursty data into bursty data cells, and for transmitting the cells over the virtual circuit connection through the cell switching communications network at an incrementally variable controllable transmission rate that is variable between a prescribed lower guaranteed minimum rate and an upper maximum rate, the source node and any intermediate node comprising the virtual connection include means for accepting, queueing and buffering the bursty data cells, means for detecting incipient congestion in the virtual connection queues and buffers, and means for forwarding the cells over the network virtual connection together with an associated incipient congestion indicator; and

b) a destination node being the terminus of the communication network virtual connection having means for accepting the bursty data cells and the associated incipient congestion indicator, for reconstructing, formatting and outputting the framed bursty data, for monitoring the congestion indicators, for creating a rate control signal based on the congestion indicators, for transmitting the rate control signal back to the source node, wherein the incrementally controllable transmission rate of the source node is adjusted in response to the rate control signal sent from the destination node in order to minimize congestion.

14. The feedback control system of claim 13, wherein the rate control further comprises means for assigning an initial quiescent rate between the lower and upper rate.

15. The feedback control system of claim 14, wherein the rate control further comprises means for sensing lack of user input bursty data activity and resetting the rate to the quiescent rate.

16. The feedback control system of claim 13, wherein the rate control means ignores the rate control signal if the user input rate does not create an excess virtual circuit queue load.

17. The feedback control system of claim 13 wherein the user framed bursty data includes frames of data, each frame of data including a multiplicity of cells and a header, each cell including a multiplicity of bits, the multiplicity of bits including a cell loss priority (CLP) bit and wherein the means for accepting, queueing and buffering includes a queue for queuing the bursty data cells and wherein the source node further comprises:

a) means for measuring an instantaneous bit rate of incoming frames of data;

b) means for comparing the instantaneous bit rate of incoming frames of data against a committed burst size (Bc) and against a minimum information rate (MIR);

c) means for setting a data expendable (DE) bit included in the header of each frame for each frame of data having an instantaneous bit rate exceeding Bc and MIR; and

d) means for discarding each frame in which the DE bit is set if the queue length exceeds a threshold length; and

e) means for copying the DE bit of each frame into the CLP bit of each cell associated with the frame.

18. A feedback control system for congestion prevention control on a virtual connection of a cell switching communications network handling bursty traffic, the feedback control system comprising:

a) a source node for accepting, queuing and buffering user framed bursty data, for formatting the bursty data into bursty data cells, and for transmitting the cells over the virtual circuit connection through the cell switching communications network at an incrementally variable controllable transmission rate in response to a rate control signal to minimize congestion, the source node and any intermediate node comprising the virtual connection include means for accepting, queuing and buffering the bursty data cells, means for detecting incipient congestion in the virtual connection queues and buffers by monitoring the average queue length over a regeneration cycle time interval, means for comparing the average queue length to an incipient congestion threshold, means for setting an incipient congestion indicator to a first state when the incipient congestion threshold is exceeded and setting the incipient congestion indicator to a second state when the incipient congestion threhsold is not exceeded, and means for forwarding the cells over the network virtual connection together with the incipient congestion indicator; and

b) a destination node being the terminus of the communication network virtual connection having means for accepting the bursty data cells and the incipient congestion indicator, for reconstructing, formatting, and outputting the framed bursty data, for monitoring the incipient congestion indicators, for revising the rate control signal based on the incipient congestion indicators, for transmitting the rate control signal back to the source node.

19. The feedback control system of claim 18, wherein the incipient congestion threshold is set to provide a tolerable delay in combination with a tolerable concomitant cell loss rate.

20. The feedback system of claim 18, further comprising means for discarding cells that arrive while queue length exceeds the incipient congestion threshold.

21. The feedback control system of claim 18, wherein the incipient congestion indicator is encoded in a cell header.

22. The feedback control system of claim 18 wherein the user framed bursty data includes frames of data, each frame of data including a multiplicity of cells and a header, each cell including a multiplicity of bits, the multiplicity of bits including a cell loss priority (CLP) bit and wherein the means for accepting, queuing and buffering includes a queue for queuing the bursty data cells and wherein the source node further comprises:

a) means for measuring an instantaneous bit rate of incoming frames of data;

b) means for comparing the instantaneous bit rate of incoming frames of data against a committed burst size (Bc) and against a minimum information rate (MIR);

c) means for setting a data expendable (DE) bit included in the header of each frame for each frame of data having an instantaneous bit rate exceeding Bc and MIR; and

d) means for discarding each frame in which the DE bit is set if the queue length exceeds a threshold length; and

e) means for copying the DE bit of each frame into the CLP bit of each cell associated with the frame.

23. A feedback control system for congestion prevention control on a virtual connection of a cell switching communications network handling bursty traffic, comprising:

a) a source node for accepting, queueing and buffering user framed bursty data, for formatting the bursty data into bursty data cells, and for transmitting the cells over the virtual circuit connection through the cell switching communications network at an incrementally variable controllable transmission rate, the source node and any intermediate node comprising the virtual connection having means for accepting, queueing and buffering the bursty data cells, means for detecting incipient congestion in the virtual connection queues and buffers, and means for forwarding the cells over the network virtual connection together with an associated incipient congestion indicator; and

b) a destination node being the terminus of the communication network virtual connection having means for accepting the bursty data cells and the associated incipient congestion indicator, for reconstructing, formatting and outputting the framed bursty data, for counting cells with the associated incipient congestion indicator asserted, for creating a rate control signal based on the cell count, for transmitting the rate control signal back to the source node, wherein the incrementally controllable transmission rate of the source node is adjusted in response to the rate control signal sent from the destination node in order to minimize congestion.

24. The feedback control system of claim 23, wherein the cell count means begins counting after a round-trip delay interval following a transmission of the rate control signal from the destination node to the source node.

25. The feedback control system of claim 23, wherein the means for generating the rate control signal further comprises means for indicating a rate increase if a threshold is not exceeded by an average incipient congestion count, and for indicating a rate decrease if the threshold is exceeded.

26. The feedback control system of claim 23, wherein the means for generating the rate control signal further comprises means for detecting cell loss together with the detection of the average incipient congestion count exceeding threshold, means for indicating a fast reduction when the threshold is exceeded and cell loss in detected.

27. The feedback control system of claim 23, wherein the means for generating the rate control signal indicates no-rate-change for each cell while waiting for the effects on congestion due to a previous transmission of the rate control signal.

28. The feedback control system of claim 23 wherein the user framed bursty data includes frames of data, each frame of data including a multiplicity of cells and a header, each cell including a multiplicity of bits, the multiplicity of bits including a cell loss priority (CLP) bit and wherein the means for accepting, queuing and buffering includes a queue for queuing the bursty data cells and wherein the source node further comprises:

a) means for measuring an instantaneous bit rate of incoming frames of data;

b) means for comparing the instantaneous bit rate of incoming frames of data against a committed burst size (Bc) and against a minimum information rate (MIR);

c) means for setting a data expendable (DE) bit included in the header of each frame for each frame of data having an instantaneous bit rate exceeding Bc and MIR; and

d) means for discarding each frame in which the DE bit is set if the queue length exceeds a threshold length; and

e) means for copying the DE bit of each frame into the CLP bit of each cell associated with the frame.

29. A feedback control system for congestion prevention control on a virtual connection of a cell switching communications network handling bursty traffic, comprising:

a) a source node for accepting, queueing and buffering user framed bursty data, for formatting the bursty data into bursty data cells, for indicating those cells derived from user input data received at rates exceeding a prescribed guaranteed minimum rate, and for transmitting the cells together with the indicators over the virtual circuit connection through the cell switching communications network at an incrementally variable controllable transmission rate, the source node and any intermediate node comprising the virtual connection having means for accepting, queueing and buffering the bursty data cells, means for detecting incipient congestion in the virtual connection queues and buffers, and means for forwarding the cells over the network virtual connection together with an associated incipient congestion indicator; and

b) a destination node being the terminus of the communication network virtual connection having means for accepting the bursty data cells and the associated incipient congestion indicator, for reconstructing, formatting and outputting the framed bursty data, means for monitoring the congestion indicators, for creating a rate control signal based on the congestion indicators, means for transmitting the rate control signal back to the source node, wherein the incrementally controllable transmission rate of the source node is adjusted in response to the rate control signal sent from the destination node in order to minimize congestion.

30. The feedback control system of claim 29, wherein the means for indicating those cells derived from user input frames rates exceeding a prescribed guaranteed minimum rate further comprises means for encoding the indications in the cell header.

31. The feedback control system of claim 29, wherein the source node and any intermediate node further comprises means for discarding the cells which have been indicated as being derived from input data exceeding the minimum guaranteed rate whenever the virtual connection queues exceed a prescribed cell loss priority threshold length.

32. The feedback control system of claim 31, wherein the means for discarding cells discards all cells belonging substantially to a same data frame as that which was being queued when the prescribed cell loss threshold length was exceeded.

33. A feedback control system for congestion prevention control on a virtual connection of a cell switching communications network handling bursty traffic, comprising:

a) a source node for accepting, queueing and buffering user framed bursty data including an associated expendable data indicator that indicates an excess input frame data rate, for formatting the bursty data into bursty data cells, for encoding the expendable data indicator in the cell header, for discarding cells bearing the indicator for relief of congestion, and for transmitting the non-discarded cells over the virtual circuit connection through a cell switching communications network at an incrementally variable controllable transmission rate, the source node and any intermediate nodes comprising the virtual connection having means for accepting, queueing and buffering the bursty data cells, means for detecting incipient congestion in the virtual connection queues and buffers, and means for forwarding the cells over the network virtual connection together with an associated incipient congestion indicator; and

b) a destination node being the terminus of the communication network virtual connection having means for accepting the bursty data cells and the associated incipient congestion indicator, for reconstructing, formatting and outputting the framed bursty data, for monitoring the congestion indicators, for creating a rate control signal based on the congestion indicators, means for transmitting the rate control signal back to the source node, wherein the incrementally controllable transmission rate of the source node is adjusted in response to the rate control signal sent from the destination node in order to minimize congestion.

34. The feedback control system of claim 33, wherein the source node and any intermediate node further comprises means for discarding cells associated with the expendable data indicator.

35. The feedback control system of claim 33, wherein the destination node further comprises:

a) at least one output queue for buffering reconstructed data frames;

b) means for monitoring the output queue length;

c) means for comparing the output queue length with a prescribed threshold; and

d) means for discarding the reconstructed bursty data frames having an associated asserted expendable data indicator whenever the prescribed output queue threshold is exceeded.

36. The feedback control system of claim 35, further comprising:

a) means for calculating an average queue length of the port transmit queue associated with the virtual connection;

b) means for comparing the average output port transmit queue length with a prescribed average output port transmit queue length threshold; and

c) means for generating a rate decrease signal if the average output port transmit queue length threshold is exceeded.

37. The feedback control system of claim 36, wherein the average output queue length is computed over a regeneration cycle time interval.

38. A feedback control method for congestion prevention on a virtual circuit connection of a cell switching network handling bursty data traffic, the method comprising the steps of:

a) queuing and buffering user bursty data frames at an input source node;

b) formatting the bursty data frames into bursty data cells;

c) queuing and buffering the bursty data cells within the input source node and intermediate nodes, for transmission to a next node of the virtual connection;

d) detecting incipient congestion of the bursty data cells that are buffered and queued for transmission to the next node by monitoring queue lengths;

e) setting an incipient congestion indicator to a first state when incipient congestion is detected;

f) setting the incipient congestion indicator to a second state when incipient congestion is not detected;

g) associating the incipient congestion indicator with corresponding cells that are contributing to the incipient congestion;

h) transmitting the cells and incipient congestion indicators to the destination node over a virtual circuit connection at a controllable rate;

i) incrementally controlling the transmission rate of bursty cells in response to a rate control signal so as to control congestion;

j) reconstructing frames at the destination node from received bursty cells;

k) monitoring the congestion indicators at the destination node for determining a congestion status of the virtual connection;

l) revising the rate control signal based on the congestion status; and

m) transmitting the rate control signal to the source node.

39. The feedback control method of claim 38, wherein the step of revising the rate control signal based on the congestion status comprises generating a four state, two binary bit, signal representing rate increase, rate decrease, fast rate decrease, and no-rate-change.

40. The feedback control method of claim 39, wherein the step of incrementally controlling the transmission rate of bursty cells is in response to the four state control signal causing an additive fractional increase in response to rate increase signal, a moderate fractional multiplicative factor decrease in response to a rate decrease signal, a large fractional multiplicative factor decrease in response to a fast decrease signal, and no rate change in response to a no-rate-change signal.

41. The feedback control method of claim 40, wherein the step of incrementally controlling the transmission rate of bursty cells includes maintaining the transmission rate between a lower guaranteed minimum rate and an upper maximum rate.

42. The feedback control method of claim 41 wherein the step of incrementally controlling the transmission rate of bursty cells includes assigning an initial transmission rate that is between the lower guaranteed rate and upper maximum rate.

43. The feedback control method of claim 41, wherein the step of controlling the transmission rate of bursty cells includes sensing a lack of user input bursty data activity, causing the transmission rate to be reset to a prescribed quiescent rate.

44. The feedback control method of claim 41, wherein the step of incrementally controlling the transmission rate of bursty cells includes ignoring the rate increase signal if the user input rate does not create an excess virtual circuit queue load.

45. The feedback control method of claim 41, wherein the step of incrementally controlling the transmission rate of bursty cells further comprises the following steps:

a) determining the assigned inner-cell interval corresponding to the assigned virtual circuit transmission rate expressed in queue server tick intervals;

b) decrementing the assigned interval each base rate period;

c) incrementing a transmission credit counter whenever the decremented assigned interval is equal to or less than zero, and renewing the decremented assigned interval by adding to it the prior assigned interval thereby creating a new assigned interval for user in step(b);

d) transmitting bursty cells at queue server tick intervals whenever the transmission credit count is greater than zero and a bursty cell is queued for transmission; and

e) decrementing the credit counter whenever a bursty cell is transmitted.

46. The feedback control method of claim 45, further comprising the step of limiting the transmission credit counter to a prescribed maximum count.

47. The feedback control method of claim 38, further comprising the following additional steps:

(a) monitoring the average length of any output port transmit queue associated with the bursty cell virtual connection;

(b) comparing the average queue length to a configurable queue length threshold value; and

(c) generating a rate decrease signal if the threshold level is exceeded.