Dynamic window sizing in a data network
First Claim
1. In a virtual circuit data network having one or more nodes, a method of adjusting the size of a window Wk-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 Jk-1 using the link prior to the addition of the kth virtual circuit; and
adjusting the size of the window Wk-1 for the kth virtual circuit from the equation ##EQU11## where W0 is a full-speed round trip window.
3 Assignments
0 Petitions
Accused Products
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.
163 Citations
32 Claims
-
1. In a virtual circuit data network having one or more nodes, a method of adjusting the size of a window Wk-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 Jk-1 using the link prior to the addition of the kth virtual circuit; and adjusting the size of the window Wk-1 for the kth virtual circuit from the equation ##EQU11## where W0 is a full-speed round trip window. - View Dependent Claims (2, 3, 4)
-
-
5. In a virtual circuit data network having one or more nodes, a method of adjusting the size of a window Wk-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=N0 <
N1 <
. . . <
NM =N;associating M window sizes W0 >
W1 >
. . . >
WM-1 with the break points N0 through NM-1 such that Ni is associated with Wi ;determining the average number of active virtual circuits JNi using the link prior to the addition of the kth virtual circuit; and adjusting the size of the window Wi associated with virtual circuit Ni from the equation ##EQU14## where Ni <
k≦
Ni+1 and W0 is a full-speed round trip window. - View Dependent Claims (6, 7, 8, 9)
-
-
10. 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. - View Dependent Claims (11, 12, 13)
-
-
14. 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. - View Dependent Claims (15, 16, 17, 18)
-
-
19. 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. - View Dependent Claims (20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32)
-
Specification