Dynamic window sizing in a data network

• US 5,163,046 A
• Filed: 11/08/1990
• Issued: 11/10/1992
• Est. Priority Date: 11/30/1989
• Status: Expired due to Term

• Current Assignee: American Telephone & Telegraph Company (AT&T, Inc.)
• Original Assignee: AT&T, Inc.
• Inventors: Morgan, Samuel P., Hahne, Ellen L.
• Primary Examiner(s): Olms, Douglas W.
• Assistant Examiner(s): BLUM, RUSSELL
• Application Number:
  US07/607,831
• Time in Patent Office: 733 Days
• Field of Search: 370/60, 370/60.1, 370/79, 370/80, 370/94.1, 370/58.1, 370/95.1
• US Class Current: 370/237
• 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/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/27 Evaluation or update of window size, e.g. using information derived from acknowledged [ACK] packets
• CPC Class Codes: H04L 47/33 using forward notification

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.

Claims

1. 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₀ is a full-speed round trip window.

2. 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.

3. 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.

4. 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.

5. 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₀ <

N₁ <

. . . <

N_M =N;

associating M window sizes W₀ >

W₁ >

. . . >

W_M-1 with the break points N₀ 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₀ is a full-speed round trip window.

6. 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 and retaining the result only for each J_Ni.

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

8. 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.

9. 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

space="preserve" listing-type="equation">(W.sub.k-1 -W.sub.k)dN.sub.k /dw.sub.k +N.sub.k+1 -N.sub.k =0, ##EQU17##

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.

11. 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.

12. 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.

13. The method set forth in any of claims 10 through 12 wherein:

the renegotiation interval is a small number of seconds.

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.

15. 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₀ is a full-speed round-trip window.

16. 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.

17. 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.

18. 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.

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.

20. 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.

21. 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.

22. 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.

23. 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.

24. 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.

25. 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.

26. 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.

27. The method set forth in claim 26 wherein:

the renegotiation interval is a small number of seconds.

28. 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.

29. 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₀ is a full-speed round-trip window.

30. 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.

31. 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.

32. 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.