Delay-based congestion avoidance in computer networks
First Claim
1. For use in a data communication network having a plurality of nodes, including a first node including a processor characterized by a changeable parameter which affects the level of loading imposed on the network by the transmission of data by said first node, the plurality of nodes also including a destination node, a method of congestion avoidance comprising the steps of:
- a) sending a first group of data from the first node to said destination node, loading of said network during travel of said first group of data from said first node to said destination node being at a first loading value which represents the loading imposed on the network when said first group is sent by the first node;
b) receiving at the first node an acknowledgement that at least some of the data in the first group was received by the destination node;
c) measuring by said processor of said first node a first time delay which is the time delay between the sending of the first group of data and the receiving of the corresponding acknowledgement;
d) sending a second group of data from the first node to the destination node, loading of said network during travel of said second group of data from said first node to said destination node being at a second loading value which represents the loading imposed when the second group is sent by the first node;
e) receiving at the first node an acknowledgement that at least some of the data in the second group was received by the destination node;
f) measuring by said processor of said first node a second time delay which is the time delay between the sending of the second group and the receiving of the corresponding acknowledgement;
g) computing by said processor of said first node a quantity which is a function of the ratio between (1) the relative difference between the first and second time delays, and (2) the relative difference between the first and second loading values; and
h) automatically changing by said processor of said first node said changeable parameter so as to increase the loading from any data to be subsequently sent by the first node if the said quantity is less than a predetermined value, and changing at said first node said changeable parameter so as to decrease such loading if said quantity is greater than said predetermined value.
5 Assignments
0 Petitions
Accused Products
Abstract
A packet data communication system employs a congestion avoidance method in which each node measures the round-trip delay occurring when it sends data to a destination and receives an acknowledgement. This delay is measured for different load levels, and a comparison of these delays is used to determine whether to increase or decrease the load level. The load level can be adjusted by adjusting the window size (number of packets sent in to the network) or by adjusting the packet rate (packets per unit time). The objective is operation at the knee in the throughput vs. traffic curve, so that the data throughput is high and the round trip delay is low. Control is accomplished at each node individually, without intervention by the router or server, so system overhead is not increased.
-
Citations
27 Claims
-
1. For use in a data communication network having a plurality of nodes, including a first node including a processor characterized by a changeable parameter which affects the level of loading imposed on the network by the transmission of data by said first node, the plurality of nodes also including a destination node, a method of congestion avoidance comprising the steps of:
-
a) sending a first group of data from the first node to said destination node, loading of said network during travel of said first group of data from said first node to said destination node being at a first loading value which represents the loading imposed on the network when said first group is sent by the first node; b) receiving at the first node an acknowledgement that at least some of the data in the first group was received by the destination node; c) measuring by said processor of said first node a first time delay which is the time delay between the sending of the first group of data and the receiving of the corresponding acknowledgement; d) sending a second group of data from the first node to the destination node, loading of said network during travel of said second group of data from said first node to said destination node being at a second loading value which represents the loading imposed when the second group is sent by the first node; e) receiving at the first node an acknowledgement that at least some of the data in the second group was received by the destination node; f) measuring by said processor of said first node a second time delay which is the time delay between the sending of the second group and the receiving of the corresponding acknowledgement; g) computing by said processor of said first node a quantity which is a function of the ratio between (1) the relative difference between the first and second time delays, and (2) the relative difference between the first and second loading values; and h) automatically changing by said processor of said first node said changeable parameter so as to increase the loading from any data to be subsequently sent by the first node if the said quantity is less than a predetermined value, and changing at said first node said changeable parameter so as to decrease such loading if said quantity is greater than said predetermined value. - View Dependent Claims (2, 3, 4, 5, 6, 7)
-
-
8. A method of operating a computer network, said computer network including a source node and a destination node, wherein said source node includes a processor, comprising the steps of:
-
a) sending first data from said source node to said destination node by said network at a first loading level and receiving at said source node a first acknowledgement from said destination node of said network, said first acknowledgement confirming receipt of at least part of said first data; and
measuring by said processor a first delay between said sending said first data and said receiving said first acknowledgement;b) measuring by said processor in said source node a second delay between sending second data from said source node to said destination node and receiving at said source node a second acknowledgement from said destination node, said second acknowledgement confirming receipt of at least part said second data, said second data being sent by said source node with a second loading level different from said first loading level; c) automatically changing the loading level by said processor of said source node, in response to a function of the difference in said measured first and second delays, said step of changing including decreasing from said second loading level if said second delay is greater than said first delay and increasing from said second loading level if said second delay is less than said first delay. - View Dependent Claims (9, 10, 11, 12)
-
-
13. A method of controlling a source node in a data communications network, said source node including a processor, comprising the steps of:
-
a) sending first data from said source node of said network to a destination node in said network, using a selected data loading; b) receiving at said source node first acknowledgement indicating receipt of at least part of said first data by said destination node; c) measuring by said source node the delay time between said step of sending the first data and said step of receiving the first acknowledgement; d) sending second data from said source node of said network to said destination node, using a different data loading from said selected data loading; e) receiving at said source node a second acknowledgement indicating receipt of at least part of said second data by said destination node; f) measuring said source node the delay time between said step of sending the second data and said step of receiving the second acknowledgement; g) comparing by said processor at said source node said first and second measured delay times to produce a difference value; h) and, at said source node, in response to a function of said difference value, changing the loading by increasing the data loading for further data sent by said source node to said destination node if said second delay time is less than said first delay time and by decreasing the data loading for further data sent by said source node to said destination node if said second delay time is greater than said first delay time. - View Dependent Claims (14, 15, 16, 17, 18)
-
-
19. A method of operating a packet data communications network having a plurality of nodes said nodes including a source node and a destination node, said source node including a processor, comprising the steps of:
-
a) sending first data from said source node of said network to said destination node of said network, using a selected first level of loading for said first data, said first data including a number of packets; b) receiving at said source node a first acknowledgement of receipt of at least part of said first data by said destination node; c) measuring and recording by said processor at said source node a first delay time between said step of sending said first data and said step of receiving said first acknowledgement; d) sending second data from said source node of said network to said destination node, using a second level of loading for said step of sending second data different from said selected first level of loading, said second data including a number of packets; e) receiving at said source node a second acknowledgement of receipt of at least part of said second data by said destination node; f) measuring by said processor at said source node a second delay time between said step of sending said second data and said step of receiving said second acknowledgement, and comparing said recorded first delay time with the second delay time, to determine a change in delay time; and g) subsequently sending from said source node to said destination node third data at a loading greater than said second level if said change is a negative value and at a loading less than said second level if said change is a positive value, to approach an operating point of maximum throughput at minimum delay time. - View Dependent Claims (20, 21)
-
-
22. Apparatus for operating a computer network, wherein said network includes a source node and a destination node, comprising:
- means including a processor at said source node for measuring a first delay between sending first data from said source node to said destination node in said network at a first loading value and receiving at said source node a first acknowledgement from said destination node in said network indicating receipt of at least part of said first data, and means including said processor at said source node for subsequently measuring a second delay between sending second data from said source node to said destination node in said network at a second loading value different from said first loading value and receiving at said source node a second acknowledgement from said destination node in said network indicating receipt of at least part of said second data; and
means including said processor at said source node for thereafter changing the loading by said source for subsequent data sent by said source node to said destination node by varying the loading from said second loading value toward another loading value in response to the difference between said measured first and second delays, the loading being decreased if said difference is positive and increased if said difference is negative. - View Dependent Claims (23)
- means including a processor at said source node for measuring a first delay between sending first data from said source node to said destination node in said network at a first loading value and receiving at said source node a first acknowledgement from said destination node in said network indicating receipt of at least part of said first data, and means including said processor at said source node for subsequently measuring a second delay between sending second data from said source node to said destination node in said network at a second loading value different from said first loading value and receiving at said source node a second acknowledgement from said destination node in said network indicating receipt of at least part of said second data; and
-
24. Apparatus for controlling a first node in a data communications network, comprising:
- transmitter/receiver means including a processor in said first node and having sending means for sending first data from said first node to a destination node using a selected window size and then subsequently sending second data from said first node to said destination node using a second window size different from said selected window size, said transmitter/receiver means having receiving means for receiving at said first node acknowledgements from said destination node indicating receipt of at least parts of said first and second data after first and second delay times, respectively;
control means including said processor in said first node including means for comparing said first delay time between said sending and receiving for said first data with said second delay time between said sending and receiving for said second data; and
said transmitter/receiver means including means for subsequent sending of third data using an altered window size in response to said means for comparing, said means for subsequent sending using an altered window size larger than said second window size if said second delay time is less than said first delay time and less than said second window size if said second delay time is greater than said first delay time. - View Dependent Claims (25, 26, 27)
- transmitter/receiver means including a processor in said first node and having sending means for sending first data from said first node to a destination node using a selected window size and then subsequently sending second data from said first node to said destination node using a second window size different from said selected window size, said transmitter/receiver means having receiving means for receiving at said first node acknowledgements from said destination node indicating receipt of at least parts of said first and second data after first and second delay times, respectively;
Specification