US5014265A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for congestion control in a data network
Assignee: Nokia Bell Labs
•
Filing: 1989-11-30
•
Granted: 1991-05-07
•
Expires: 2009-11-30
Abstract
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.
Inventors
- 👤 Ellen L. Hahne
- 👤 Charles R. Kalmanek
- 👤 Samuel P. Morgan
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-25 15:40
CPC Classifications
H; H04; H04L; H04L47/00; H04L47/10; H04L47/17; H04L47/16; H04L47/26; H04L47/263; H04L47/27; H04L47/28; H04L47/283; H04L47/33; H04L47/43; H04L12/00; H04L12/54; H04L12/56; H04L12/5601; H04L2012/5629; H04L2012/5631; H04L2012/5632; H04L2012/5634; H04L2012/5635; H04L2012/5678; H04L2012/5681
Claims Analysis
Total Claims: 28
Claim 1
Independent Claim
112 words
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.
Claim 2
Independent Claim
112 words
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.
Claim 3
Dependent Claim
26 words
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.
Claim 4
Dependent Claim
56 words
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.
Claim 5
Dependent Claim
67 words
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.
Claim 6
Dependent Claim
34 words
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.
Claim 7
Dependent Claim
40 words
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.
Claim 8
Dependent Claim
29 words
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.
Claim 9
Dependent Claim
25 words
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.
Claim 10
Dependent Claim
51 words
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.
Claim 11
Dependent Claim
47 words
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.
Claim 12
Dependent Claim
37 words
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.
Claim 13
Dependent Claim
38 words
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.
Claim 14
Dependent Claim
47 words
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.
Claim 15
Dependent Claim
108 words
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.
Claim 16
Dependent Claim
130 words
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.
Claim 17
Dependent Claim
66 words
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.
Claim 18
Dependent Claim
74 words
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.
Claim 19
Dependent Claim
75 words
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
Claim 20
Dependent Claim
39 words
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.
Claim 21
Dependent Claim
72 words
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.
Claim 22
Dependent Claim
53 words
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.
Claim 23
Dependent Claim
48 words
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.
Claim 24
Dependent Claim
103 words
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.
Claim 25
Dependent Claim
60 words
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.
Claim 26
Dependent Claim
71 words
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.
Claim 27
Independent Claim
177 words
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.
Claim 28
Independent Claim
177 words
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.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1994-05-06 | 1994-11-05 | 1995-05-07 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1998-05-06 | 1998-11-05 | 1999-05-07 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2002-05-06 | 2002-11-05 | 2003-05-07 | $7700.00 | Window Closed / Lapsed |