US5163046A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Dynamic window sizing in a data network
Assignee: Nokia Bell Labs
•
Filing: 1990-11-08
•
Granted: 1992-11-10
•
Expires: 2010-11-08
Abstract
Abstract A method for use in a high-speed virtual circuit digital network for resizing windows of virtual circuits in nodes of the network. The resizing of a virtual circuit's window is initiated by an input router at an edge of the digital network. When the input router determines that resizing is necessary, it sends a first congestion control message to the nodes through which the virtual circuit passes. If the message indicates a larger window, the node receiving the message determines what size window it can provide and sends the message with that window size on to the next node. An output router at the other edge of the digital network receives the message, sets the window size based on the message as altered by the nodes, and returns a second message with the final window size via the nodes. On receipt of the second message, the nodes alter their windows and the input router sends cells as permitted by the new window. Included in the method are novel techniques for determining the ideal window size for a virtual circuit, for determining at the input router when a change in window size is necessary, and for determining the size of the window in the nodes.
Inventors
- 👤 Ellen L. Hahne
- 👤 Samuel P. Morgan
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-25 01:11
CPC Classifications
H; H04; H04L; H04L47/00; H04L47/10; H04L47/17; H04L47/16; H04L47/27; H04L12/00; H04L12/54; H04L12/56; H04L12/5601; H04L2012/5629; H04L2012/5631; H04L2012/5632; H04L2012/5634; H04L2012/5635; H04L2012/5678; H04L2012/5681; H04L47/33
Claims Analysis
Total Claims: 37
Claim 1
Independent Claim
92 words
In a virtual circuit data network having one or more nodes, a method of adjusting the size of a window W k-1 in the node for the kth virtual circuit using a given link from the node, the method comprising the steps of: determining the average number of active virtual circuits J k-1 using the link prior to the addition of the kth virtual circuit; and adjusting the size of the window W k-1 for the kth virtual circuit from the equation ##EQU11## where W 0 is a full-speed round trip window.
Claim 2
Dependent Claim
92 words
In a virtual circuit data network having one or more nodes, a method of adjusting the size of a window W k-1 in the node for the kth virtual circuit using a given link from the node, the method comprising the steps of: determining the average number of active virtual circuits J k-1 using the link prior to the addition of the kth virtual circuit; and adjusting the size of the window W k-1 for the kth virtual circuit from the equation ##EQU11## where W 0 is a full-speed round trip window.
Claim 3
Dependent Claim
60 words
The method set forth in claim 1 wherein: a virtual circuit in intermittent use has an average service time requirement τ in which it is in active use and an average idle time of hτ and the step of determining the average number of active virtual circuits J k-1 is performed using the recurrence ##EQU12## starting from J 0 =0.
Claim 4
Dependent Claim
59 words
The method set forth in claim 1 wherein: a virtual circuit in intermittent use has an average service time requirement τ in which it is in active use and an average idle time of hτ and the step of determining the average number of active virtual circuits J k-1 is performed using the approximation ##EQU13## for J k-1 .
Claim 5
Dependent Claim
46 words
The method set forth in claim 3 wherein: the step of determining the average number of active virtual circuits is performed using the longest round trip time of the network as τ and a value of h such that hτ is a small number of seconds.
Claim 6
Dependent Claim
178 words
In a virtual circuit data network having one or more nodes, a method of adjusting the size of a window W k-1 in the node for the kth virtual circuit using a given link from the node, the method comprising the steps of: determining that there is to be a fixed number M of window sizes; dividing the number N of virtual circuits which can exist simultaneously in the network into a set of M+1 break points such that 0=N 0 <N 1 < . . . <N M =N; associating M window sizes W 0 >W 1 > . . . >W M-1 with the break points N 0 through N M-1 such that N i is associated with W i ; determining the average number of active virtual circuits J Ni using the link prior to the addition of the kth virtual circuit; and adjusting the size of the window W i associated with virtual circuit N i from the equation ##EQU14## where N i <k≦N i+1 and W 0 is a full-speed round trip window.
Claim 7
Dependent Claim
178 words
In a virtual circuit data network having one or more nodes, a method of adjusting the size of a window W k-1 in the node for the kth virtual circuit using a given link from the node, the method comprising the steps of: determining that there is to be a fixed number M of window sizes; dividing the number N of virtual circuits which can exist simultaneously in the network into a set of M+1 break points such that 0=N 0 <N 1 < . . . <N M =N; associating M window sizes W 0 >W 1 > . . . >W M-1 with the break points N 0 through N M-1 such that N i is associated with W i ; determining the average number of active virtual circuits J Ni using the link prior to the addition of the kth virtual circuit; and adjusting the size of the window W i associated with virtual circuit N i from the equation ##EQU14## where N i <k≦N i+1 and W 0 is a full-speed round trip window.
Claim 8
Dependent Claim
70 words
The method set forth in claim 5 wherein: a virtual circuit in intermittent use has an average service time requirement τ in which it is in active use and an average idle time of hτ and the step of determining the average number of active virtual circuits J Ni is performed using the recurrence ##EQU15## starting from J 0 =0 and retaining the result only for each J Ni .
Claim 9
Dependent Claim
59 words
The method set forth in claim 5 wherein: a virtual circuit in intermittent use has an average service time requirement τ in which it is in active use and an average idle time of hτ and the step of determining the average number of active virtual circuits J Ni is performed using the approximation ##EQU16## for J Ni .
Claim 10
Dependent Claim
46 words
The method set forth in claim 7 wherein: the step of determining the average number of active virtual circuits is performed using the longest round trip time of the network as τ and a value of h such that hτ is a small number of seconds.
Claim 11
Dependent Claim
37 words
The method set forth in claim 8 wherein: the normalized total buffer usage b is minimized by solving the system of equations for k=1, 2, . . . , M-1 (W.sub.k-1 -W.sub.k)dN.sub.k /dw.sub.k +N.sub.k+1 -N.sub.k =0, ##EQU17##
Claim 12
Independent Claim
138 words
A method employed at an edge of a virtual circuit data network in which data is transported in cells to determine the size of the window to be requested in the network for a given virtual circuit originating at the edge, the method comprising the steps of: keeping track of the total number of cells TC that the given virtual circuit has at the edge and in the network; keeping track of the cumulative throughput CT of cells of the given virtual circuit during a most recent renegotiation interval; and requesting a window for the virtual circuit in the network which is large enough to accommodate a number of cells which is the larger of TC and the product of CT times the quotient of the round-trip time divided by the length of the most recent renegotiation interval.
Claim 13
Independent Claim
138 words
A method employed at an edge of a virtual circuit data network in which data is transported in cells to determine the size of the window to be requested in the network for a given virtual circuit originating at the edge, the method comprising the steps of: keeping track of the total number of cells TC that the given virtual circuit has at the edge and in the network; keeping track of the cumulative throughput CT of cells of the given virtual circuit during a most recent renegotiation interval; and requesting a window for the virtual circuit in the network which is large enough to accommodate a number of cells which is the larger of TC and the product of CT times the quotient of the round-trip time divided by the length of the most recent renegotiation interval.
Claim 14
Dependent Claim
49 words
The method set forth in claim 10 further including the step of: keeping track of whether a cell buffer for the given virtual circuit at the edge overflows; and if the cell buffer overflows during the renegotiation interval, requesting a round-trip window in the step of requesting a window.
Claim 15
Dependent Claim
69 words
The method set forth in claim 10 wherein: when the requested window is larger than the current window, the step of requesting a window may be performed at any time at which there is no pending request for a window; and when the requested window is smaller than the current window, the step of requesting a window may not be performed until the end of the current renegotiation interval.
Claim 16
Independent Claim
21 words
The method set forth in any of claims 10 through 12 wherein: the renegotiation interval is a small number of seconds.
Claim 17
Independent Claim
280 words
A method employed in a node of a virtual circuit network for sizing a window in the node for a given one of k virtual circuits using a given link from the node in response to a request for a different-sized window in the node, the method comprising the steps of: determining the maximum window to which each of the k virtual circuits is entitled according to a function whereby the maximum window for a virtual circuit j is greater than the maximum window for a virtual circuit j+1, 1≦j≦k; determining the window for each virtual circuit in the node and the rank of each virtual circuit with regard to the current size of its window; determining a potential rank which the given virtual circuit would have if its window were the requested size; and changing the rank of the given virtual circuit in the direction required by the potential rank by exchanging its rank with that of the next ranking virtual circuit in the required direction until the given virtual circuit either attains the potential rank or until further changing the rank of the given virtual circuit would require changing the rank of the next ranking virtual circuit to a rank such that the current size of the window of the next ranked virtual circuit is greater than the maximum window for the rank which the next ranked virtual circuit would receive as a result of the exchange; and sizing the window for the given virtual circuit such that the window's size is the lesser of the size of the requested window and the size of the maximum window for the final rank attained by the given virtual circuit.
Claim 18
Independent Claim
280 words
A method employed in a node of a virtual circuit network for sizing a window in the node for a given one of k virtual circuits using a given link from the node in response to a request for a different-sized window in the node, the method comprising the steps of: determining the maximum window to which each of the k virtual circuits is entitled according to a function whereby the maximum window for a virtual circuit j is greater than the maximum window for a virtual circuit j+1, 1≦j≦k; determining the window for each virtual circuit in the node and the rank of each virtual circuit with regard to the current size of its window; determining a potential rank which the given virtual circuit would have if its window were the requested size; and changing the rank of the given virtual circuit in the direction required by the potential rank by exchanging its rank with that of the next ranking virtual circuit in the required direction until the given virtual circuit either attains the potential rank or until further changing the rank of the given virtual circuit would require changing the rank of the next ranking virtual circuit to a rank such that the current size of the window of the next ranked virtual circuit is greater than the maximum window for the rank which the next ranked virtual circuit would receive as a result of the exchange; and sizing the window for the given virtual circuit such that the window's size is the lesser of the size of the requested window and the size of the maximum window for the final rank attained by the given virtual circuit.
Claim 19
Dependent Claim
66 words
The method set forth in claim 14 wherein: the step of determining the maximum window W i-1 to which a given virtual circuit i is entitled includes the steps of: determining the average number of active virtual circuits J i-1 using the link from the node; and determining the maximum window W i-1 using the equation ##EQU18## , where W 0 is a full-speed round-trip window.
Claim 20
Dependent Claim
60 words
The method set forth in claim 15 wherein: a virtual circuit in intermittent use has an average service time requirement τ in which it is in active use and an average idle time of hτ and the step of determining the average number of active virtual circuits J i-1 is performed using the recurrence ##EQU19## starting from J 0 =0.
Claim 21
Dependent Claim
59 words
The method set forth in claim 15 wherein a virtual circuit in intermittent use has an average service time requirement τ in which it is in active use and an average idle time of hτ and the step of determining the average number of active virtual circuits J i-1 is performed using the approximation ##EQU20## for J i-1 .
Claim 22
Dependent Claim
46 words
The method set forth in claim 16 or claim 17 wherein: the step of determining the maximum window size is performed using the longest round trip time of the network as τ and a value of h such that hτ is a small number of seconds.
Claim 23
Independent Claim
160 words
A method of controlling the congestion of data cells in nodes of a network for carrying cells of data via virtual circuits, the method comprising the steps of: when a virtual circuit is established, assigning a default cell buffer for the virtual circuit at each node; for the duration of the virtual circuit, performing steps including determining from the behavior of the virtual circuit whether a different-sized cell buffer is needed; if a different-sized cell buffer is needed, providing a first resizing signal indicating the different size to the nodes in the virtual circuit; in each node of the virtual circuit, responding to the first resizing signal by indicating the 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 nodes.
Claim 24
Independent Claim
160 words
A method of controlling the congestion of data cells in nodes of a network for carrying cells of data via virtual circuits, the method comprising the steps of: when a virtual circuit is established, assigning a default cell buffer for the virtual circuit at each node; for the duration of the virtual circuit, performing steps including determining from the behavior of the virtual circuit whether a different-sized cell buffer is needed; if a different-sized cell buffer is needed, providing a first resizing signal indicating the different size to the nodes in the virtual circuit; in each node of the virtual circuit, responding to the first resizing signal by indicating the 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 nodes.
Claim 25
Dependent Claim
81 words
The method set forth in claim 19 wherein: the step of determining whether a different-sized cell buffer is needed is performed at a first edge of the network at which the virtual circuit enters the network; and the method includes the further step of receiving the first resizing signal at a second edge of the network at which the virtual circuit leaves the network and selecting the buffer size to which the cell buffers in the nodes are to be set.
Claim 26
Dependent Claim
57 words
The method set forth in claim 20 wherein: the method includes the further step of providing a second resizing signal containing the selected buffer size from the second edge to the nodes; and the step of setting the cell buffer for the virtual circuit is performed using the selected buffer size specified in the second resizing signal.
Claim 27
Dependent Claim
30 words
The method set forth in claim 21 wherein: the step of providing the first resizing signal is performed by serially providing the first resizing signal to every node in turn.
Claim 28
Dependent Claim
30 words
The method set forth in claim 22 wherein: the step of providing the second resizing signal is performed by serially providing the second resizing signal to every node in turn.
Claim 29
Dependent Claim
116 words
The method set forth in claim 20 wherein: the step of determining whether a different-sized cell buffer is needed is performed by doing steps including: keeping track of the total number of cells TC that the given virtual circuit has at the first edge and in the network; keeping track of the cumulative throughput CT of cells of the given virtual circuit during a most recent renegotiation interval; and requesting a window for the virtual circuit in the network which is large enough to accommodate a number of cells which is the larger of TC and the product of CT times the quotient of the round-trip time divided by the length of the most recent renegotiation.
Claim 30
Dependent Claim
50 words
The method set forth in claim 24 further including the step of: keeping track of whether a cell buffer for the given virtual circuit at the first edge overflows; and if the cell buffer overflows during the renegotiation interval, requesting a round-trip window in the step of requesting a window.
Claim 31
Dependent Claim
69 words
The method set forth in claim 24 wherein: when the requested window is larger than the current window, the step of requesting a window may be performed at any time at which there is no pending request for a window; and when the requested window is smaller than the current window, the step of requesting a window may not be performed until the end of the current renegotiation interval.
Claim 32
Dependent Claim
17 words
The method set forth in claim 26 wherein: the renegotiation interval is a small number of seconds.
Claim 33
Dependent Claim
237 words
The method of claim 19 wherein the step of responding to the first resizing signal includes the steps of: determining the rank of each virtual circuit relative to the other virtual circuits from the current size of each virtual circuit's window; determining a potential rank which the given virtual circuit would have if its window were the requested size; changing the rank of the given virtual circuit in the direction required by the potential rank by exchanging its rank with that of the next ranking virtual circuit in the required direction until the given virtual circuit either attains the potential rank or until further changing the rank of the given virtual circuit would require changing the rank of the next ranking virtual circuit to a rank such that the current size of the window of the next ranked virtual circuit is greater than the maximum window for the rank which the next ranked virtual circuit would receive as a result of the exchange, the maximum window for a rank being determined according to a function whereby the maximum window for a virtual circuit j is greater than the maximum window for a virtual circuit j+1, 1≦j≦k; and sizing the window for the given virtual circuit such that the window's size is the lesser of the size of the requested window and the size of the maximum window for the final rank attained by the given virtual circuit.
Claim 34
Dependent Claim
63 words
The method set forth in claim 28 wherein: the maximum window W i-1 to which a given virtual circuit i is entitled is determined by steps including: determining the average number of active virtual circuits J k-1 using the link from the node; and determining the maximum window W i-1 using the equation ##EQU21## , where W 0 is a full-speed round-trip window.
Claim 35
Dependent Claim
60 words
The method set forth in claim 29 wherein: a virtual circuit in intermittent use has an average service time requirement τ in which it is in active use and an average idle time of hτ and the step of determining the average number of active virtual circuits J i-1 is performed using the recurrence ##EQU22## starting from J 0 =0.
Claim 36
Dependent Claim
59 words
The method set forth in claim 29 wherein a virtual circuit in intermittent use has an average service time requirement τ in which it is in active use and an average idle time of hτ and the step of determining the average number of active virtual circuits J i-1 is performed using the approximation ##EQU23## for J i-1 .
Claim 37
Dependent Claim
46 words
The method set forth in claim 30 or claim 31 wherein: the step of determining the maximum window size is performed using the longest round trip time of the network as τ and a value of h such that hτ is a small number of seconds.
References Cited (Backward Citations)
US5014265A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1995-11-10 | 1996-05-11 | 1996-11-10 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1999-11-10 | 2000-05-11 | 2000-11-10 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2003-11-10 | 2004-05-11 | 2004-11-10 | $7700.00 | Window Closed / Lapsed |