Method and apparatus for congestion control in a data network

• US 5,014,265 A
• Filed: 11/30/1989
• Issued: 05/07/1991
• Est. Priority Date: 11/30/1989
• Status: Expired due to Term

• Current Assignee: American Telephone & Telegraph Company (AT&T, Inc.), Bell Telephone Laboratories, Inc. (Nokia Corporation)
• Original Assignee: AT&T, Inc.
• Inventors: Hahne, Ellen L., Kalmanek, Charles R., Morgan, Samuel P.
• Primary Examiner(s): NOT, DEFINED
• Assistant Examiner(s): Marcelo, Melvin
• Application Number:
  US07/443,975
• Time in Patent Office: 523 Days
• Field of Search: 370/60, 370/60.1, 370/61, 370/79, 370/80, 370/94.1, 370/58.1
• US Class Current: 370/236
• CPC Class Codes: H04L 2012/5631 Resource management and allocation
• CPC Class Codes: H04L 2012/5634 In-call negotiation
• CPC Class Codes: H04L 2012/5635 Backpressure, e.g. for ABR
• CPC Class Codes: H04L 2012/5681 Buffer or queue management
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/16 in connection oriented networks, e.g. frame relay
• CPC Class Codes: H04L 47/17 Interaction among intermediate nodes, e.g. hop by hop
• CPC Class Codes: H04L 47/263 Rate modification at the source after receiving feedback
• CPC Class Codes: H04L 47/27 Evaluation or update of window size, e.g. using information derived from acknowledged [ACK] packets
• CPC Class Codes: H04L 47/283 in response to processing delays, e.g. caused by jitter or round trip time [RTT]
• CPC Class Codes: H04L 47/33 using forward notification
• CPC Class Codes: H04L 47/43 Assembling or disassembling of packets, e.g. segmentation and reassembly [SAR]

Abstract

A method of controlling congestion in a virtual circuit packet network. A initial packet buffer is assigned to each virtual circuit at each node into which incoming packets are stored and later removed for forward routing. If a larger buffer is desired for a virtual circuit to service a larger amount of data, then additional buffer space is dynamically allocated selectively to the virtual circuit on demand if each node has sufficient unallocated buffer space to fill the request. In one embodiment, the criterion for dynamic allocation is based on the amount of data buffered at the data source. In alternative embodiments, the criteria for dynamic allocation may be further based on the amount of data buffered at each node for a virtual circuit and the total amount of free buffer space at each node of a virtual circuit. Signaling protocols are disclosed whereby data sources and virtual circuit nodes maintain consistent information describing the buffer allocations at all times.

Claims

1. A method employed to control congestion of data cells in switching nodes of a network wherein one or more virtual circuits for transferring the data cells between endpoints pass through one or more of the switching nodes, said method comprising the steps of

assigning an initial cell buffer to the virtual circuit at each node through which it passes,

storing incoming cells for the virtual circuit in its buffer and removing cells from the buffers for forward routing, characterized by

dynamically allocating buffer space for the virtual circuit in the nodes in response to signals from at least one of the endpoints requesting an increased or decreased data window in the nodes.

2. The method of claim 1 wherein the step of assigning an initial buffer further comprises

assigning an initial buffer of predetermined size to each virtual circuit.

3. The method of claim 2 wherein the predetermined size of the initial buffer is less than the size of a full data window, wherein a full data window is defined as the product of the maximum transmission bit rate of the virtual circuit multiplied by a nominal factor representing round trip propagation time in the network.

4. The method of claim 1 wherein the step of dynamically allocating buffer space to the virtual circuit further comprises allocating a full data window in response to a signal requesting a larger buffer space, wherein a full data window is defined as the product of the maximum transmission bit rate of the virtual circuit multiplied by a nominal factor representing round trip propagation time in the network.

5. The method of claim 4 further comprising the step of requesting a larger buffer space based on the amount of data waiting to be sent for the said virtual circuit at the cell source.

6. The method of claim 4 wherein the step of dynamically allocating a full data window further comprises determining if sufficient free buffer space exists at each node of the virtual circuit to perform the allocation and denying the request otherwise.

7. The method of claim 1 wherein the step of dynamically allocating buffer space further comprises allocating space to the virtual circuit in one or more blocks of fixed size.

8. The method of claim 1 wherein the step of allocating buffer space further comprises allocating space to the virtual circuit in blocks of variable size.

9. The method of claim 7 or claim 8 further comprising the step of determining the size of a block to be allocated at each node of the virtual circuit based on the amount of data waiting to be sent for the said virtual circuit at the endpoint preceding the first node.

10. The method of claim 9 wherein the step of dynamically allocating buffer space in response to a request for a larger buffer further comprises determining if sufficient free buffer space exists at each node of the virtual circuit to perform the allocation and denying the request otherwise.

11. The method of claim 9 further comprising the step of determining the size of a block to be allocated based on the amount of packet data already buffered for the said virtual circuit at each said node.

12. The method of claim 11 further comprising the step of determining the size of a block to be allocated at each node of the virtual circuit based on the amount of free buffer space at each said node.

13. The method of claim 11 wherein the step of dynamically allocating buffer space in response to a request for a larger buffer further comprises determining if sufficient free buffer space exists at each node of the virtual circuit to perform the allocation and denying the request otherwise.

14. The method of claim 13 wherein the step of determining if sufficient free buffer space exists at each node further comprises

transmitting a control message along the virtual circuit from the first node in the circuit to the last node in the circuit,

writing information into the control message as it passes through each node describing the amount of free buffer space that can be allocated at the node, and

selecting the amount of buffer space assigned to the virtual circuit at each node to be equal to the smallest amount available at any node of the virtual circuit based on the final results in the control message.

15. The method of claim 13 wherein the step of determining if sufficient free buffer space exist at each node further comprises

transmitting a control message along the virtual circuit from the first node in the circuit to the last node in the circuit, the control message containing information representing whether a large or small amount of data is buffered at the initial node for the virtual circuit and information representing the availability of free buffer space at the initial node,

overwriting said information in the control message with new information as it passes through each node if the new information at a node is more restrictive, and

selecting the amount of buffer space assigned to the virtual circuit at each node based on the final results in the control message.

16. The method of claim 14 wherein the step of determining if sufficient free buffer space exists at each node further comprises

performing the selecting step at the endpoint following the last node, and

returning a second control message from the endpoint following the last node to each node of the virtual circuit, and

adjusting the allocation at each node in response to the second control message.

17. The method of claim 14 wherein the step of determining if sufficient free buffer space exists at each node further comprises

returning the control message from the endpoint following the last node to the endpoint preceding the first node,

performing the selecting step at the endpoint preceding the first node, and

transmitting a second control message from the endpoint preceding the first node to each node of the virtual circuit to perform the allocation.

18. The method of claim 2 wherein the size of the initial cell buffer is equal to the size of a full data window divided by the square root of the maximum number of virtual circuits that can simultaneously exist in any node, wherein a full data window is defined as the product of the maximum transmission bit rate of the virtual circuit multiplied by a nominal factor representing round trip propagation time in the network

19. The method of claim 1 or claim 2 or claim 3 or claim 4 or claim 7 or claim 8 further comprising the step of discarding data for the virtual circuit during buffer overflow for the said virtual circuit.

20. The method of claim 1 or claim 2 or claim 3 or claim 4 or claim 7 or claim 8 further comprising the step of requesting a reduction in the allocated buffer space for the virtual circuit after a prior increase of the buffer space above the initial buffer space based on the amount of data waiting to be sent for the said virtual circuit at the endpoint preceding the first node.

21. The method of claim 20 wherein the step of requesting a reduction in the allocated buffer space for the virtual circuit after a prior increase of the buffer space above the initial buffer space is further based on the amount of data already buffered for the said virtual circuit at each said node.

22. The method of claim 21 wherein the step of requesting a reduction in the allocated buffer space for the virtual circuit after a prior increase of the buffer space above the initial buffer space is further based on the amount of free buffer space at each said node.

23. The method of claim 1 wherein the step of dynamically allocating buffer space further comprises

transmitting a control message along the virtual circuit from the first node in the circuit to the last node in the circuit,

writing information into the control message as it passes through each node describing the amount of free buffer space that can be allocated at the node, and

selecting the amount of buffer space assigned to the virtual circuit at each node to be no more than the smallest amount available at any node of the virtual circuit based on the final results in the control message.

24. The method of claim 23 wherein the step of dynamically allocating buffer space further comprises

performing the selecting step at the endpoint following the last node, and

returning a second control message from the endpoint following the last node through each node of the virtual circuit, and

adjusting the allocation at each node in response to the second control message.

25. The method of claim 24 wherein the step of dynamically allocating buffer space at each node further comprises

returning the control message from the endpoint following the last node to the endpoint preceding the first node,

performing the selecting step at the endpoint preceding the first node, and

transmitting a second control message from the endpoint preceding the first node to each node of the virtual circuit to perform the allocation.

26. A method employed to control congestion of data cells in switching nodes of a network wherein one or more virtual circuits for transferring the data cells between endpoints pass through one or more of the switching nodes, each switching node including a cell buffer for each virtual circuit passing therethrough and said method comprising the steps of:

for the duration of the virtual circuit, performing steps including

determining at an endpoint whether a different-sized cell buffer is needed for the virtual circuit in the virtual circuit'"'"'s switching nodes;

if a different-sized cell buffer is needed, providing a first resizing signal from the endpoint to the virtual circuit'"'"'s switching nodes;

in each of the virtual circuit'"'"'s nodes, responding to the first resizing signal by indicating the cell buffer size which the node can provide if that is less than the different size; and

in each node of the virtual circuit, setting the cell buffer for the virtual circuit to a buffer size which is no greater than the smallest buffer size indicated by any of the switching nodes.