Dynamic window sizing in a data network

In a virtual circuit data network having one or more nodes, a method of adjusting the size of a window W.sub.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.sub.0 <N.sub.1 <
• . . . <N.sub.M =N;
• associating M window sizes W.sub.0 >W.sub.1 >
• . . . >W.sub.M-1 with the break points N.sub.0 through N.sub.M-1 such that N.sub.i is associated with W.sub.i ;
• determining the average number of active virtual circuits J.sub.Ni using the link prior to the addition of the kth virtual circuit;
• and
• adjusting the size of the window W.sub.i associated with virtual circuit N.sub.i from the equation ##EQU14## where N.sub.i <k.ltoreq.N.sub.i+1 and W.sub.0 is a full-speed round trip window.

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.

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.ltoreq.j.ltoreq.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.

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.