EP0415843A2
Expired / Lapsed
EP
⏱️ 0.0 years remaining
Delay-based congestion avoidance in computer networks
Assignee: Cabletron Systems Inc
•
Filing: 1990-08-28
•
Granted: —
•
Expires: 2010-08-28
Abstract
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 pf 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.
Inventors
- 👤 Rajendra K. Jain
Bibliographic Details
Application Number
—
Jurisdiction
EP
Data Source
google_patents
Last Synchronized
2026-10-25 19:54
CPC Classifications
H; H04; H04L; H04L47/00; H04L47/10; H04L47/26; H04L47/263; H04L47/12; H04L47/27; H04L47/28; H04L47/283; Y; Y02; Y02D; Y02D30/00; Y02D30/50
Claims Analysis
Total Claims: 33
Claim 1
Independent Claim
323 words
For use in a data communication network having a plurality of nodes, including a first node characterized by a tuning parameter which affects the level of loading imposed on the network by the transmission of data by said first node, a method of congestion avoidance comprising the steps of: a) sending a first group of data from the first node to a destination node; b) determining a first loading value which represents the loading imposed on the network by data sent by the first node immediately prior to the sending of the first group of data; c) receiving at the first node an acknowledgement that at least some of the data in the first group was received by the destination; d) measuring 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; e) changing the tuning parameter; f) sending a second group of data from the first node to the destination node; g) determining a second loading value which represents the loading imposed by the data sent by the first node immediately prior to the sending of the second group; h) receiving at the first node an acknowledgement that the destination received at least some of the data in the second group; i) measuring a second time delay which is the time delay between the sending of the second group and the receiving of the corresponding acknowledgement; j) computing 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 k) changing the tuning parameter so as to increase the loading from any data to be subsequently sent by the first node if the said ratio is less than a predetermined value, and changing the tuning parameter so as to decrease such loading if said ratio is greater than said predetermined value.
Claim 2
Dependent Claim
323 words
For use in a data communication network having a plurality of nodes, including a first node characterized by a tuning parameter which affects the level of loading imposed on the network by the transmission of data by said first node, a method of congestion avoidance comprising the steps of: a) sending a first group of data from the first node to a destination node; b) determining a first loading value which represents the loading imposed on the network by data sent by the first node immediately prior to the sending of the first group of data; c) receiving at the first node an acknowledgement that at least some of the data in the first group was received by the destination; d) measuring 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; e) changing the tuning parameter; f) sending a second group of data from the first node to the destination node; g) determining a second loading value which represents the loading imposed by the data sent by the first node immediately prior to the sending of the second group; h) receiving at the first node an acknowledgement that the destination received at least some of the data in the second group; i) measuring a second time delay which is the time delay between the sending of the second group and the receiving of the corresponding acknowledgement; j) computing 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 k) changing the tuning parameter so as to increase the loading from any data to be subsequently sent by the first node if the said ratio is less than a predetermined value, and changing the tuning parameter so as to decrease such loading if said ratio is greater than said predetermined value.
Claim 3
Dependent Claim
30 words
A method according to claim 1, wherein the tuning parameter is the window size equal to the maximum number of data packets the first node may transmit at a time.
Claim 4
Dependent Claim
23 words
A method according to claim 1, wherein the tuning parameter is the maximum bit rate at which the first node may transmit data.
Claim 5
Dependent Claim
23 words
A method according to claim 1, wherein the tuning parameter is the maximum packet rate at which the first node may transmit data.
Claim 6
Dependent Claim
36 words
A method according to claim 2, wherein the first and second loading values are the respective window sizes used by the first node when sending data immediately prior to sending the first and second groups, respectively.
Claim 7
Dependent Claim
35 words
A method according to claim 3, wherein the first and second loading values are the respective bit rates at which the first node sent data immediately prior to sending the first and second groups, respectively.
Claim 8
Dependent Claim
35 words
A method according to claim 4, wherein the first and second loading values are the respective packet rates at which the first node sent data immediately prior to sending the first and second groups, respectively.
Claim 9
Independent Claim
80 words
A method for congestion avoidance in a computer network, comprising the steps of: a) measuring the delay between sending first data from a source and receiving an acknowledgement from a destination; b) measuring the delay between sending second data from said source and receiving an acknowledgement from said destination, with a different loading of said data by said source; and c) changing the loading by said source to an optimum value in response to the difference in said measured delays.
Claim 10
Independent Claim
80 words
A method for congestion avoidance in a computer network, comprising the steps of: a) measuring the delay between sending first data from a source and receiving an acknowledgement from a destination; b) measuring the delay between sending second data from said source and receiving an acknowledgement from said destination, with a different loading of said data by said source; and c) changing the loading by said source to an optimum value in response to the difference in said measured delays.
Claim 11
Dependent Claim
45 words
A method according to claim 8 wherein said step of changing the loading includes either changing the number of packets of data sent by said source or changing the rate of packets sent by said source, said number of packets being termed the "window size".
Claim 12
Dependent Claim
29 words
A method according to claim 8 wherein said sending includes transmitting a number of packets of data from one node of the network to another node of the network.
Claim 13
Dependent Claim
29 words
A method according to claim 10 wherein said step of changing the loading includes decreasing the number or rate of packets or increasing the number or rate of packets.
Claim 14
Dependent Claim
42 words
A method according to claim 11 wherein said step of changing the loading is also in response to the relative change in the measured delays as a function of the relative change in the window sizes, or bit rates, or packet rates.
Claim 15
Independent Claim
171 words
A method of controlling a node in a data communications network, comprising the steps of: a) sending first data from said node of said network to a destination node, using a selected window size or rate; b) receiving at said node an acknowledgement of said data from said destination node; c) measuring the delay time between said step of sending the first data and said step of receiving the acknowledgement of the first data; d) sending second data from said source node of said network to said destination node, using a different window size or a different rate from that used when sending the first data; e) receiving at said node an acknowledgement of said second data from said destination node; f) measuring the delay time between said step of sending the second data and said step of receiving the acknowledgment of the second data; g) comparing said first and second measured delay times; and h) increasing or decreasing the window size or rate in response to said step of comparing.
Claim 16
Independent Claim
171 words
A method of controlling a node in a data communications network, comprising the steps of: a) sending first data from said node of said network to a destination node, using a selected window size or rate; b) receiving at said node an acknowledgement of said data from said destination node; c) measuring the delay time between said step of sending the first data and said step of receiving the acknowledgement of the first data; d) sending second data from said source node of said network to said destination node, using a different window size or a different rate from that used when sending the first data; e) receiving at said node an acknowledgement of said second data from said destination node; f) measuring the delay time between said step of sending the second data and said step of receiving the acknowledgment of the second data; g) comparing said first and second measured delay times; and h) increasing or decreasing the window size or rate in response to said step of comparing.
Claim 17
Dependent Claim
17 words
A method according to claim 13 wherein said data is sent in a plurality of separate packets.
Claim 18
Dependent Claim
23 words
A method according to claim 14 wherein said step of increasing or decreasing the window size is in an integral number of packets.
Claim 19
Dependent Claim
27 words
A method according to claim 13 wherein said data communications network includes a plurality of nodes and said steps are performed independently at each of said nodes.
Claim 20
Dependent Claim
31 words
A method according to claim 13 wherein said step of increasing of decreasing said window size or rate is to provide an operating point of maximum throughput at minimum delay time.
Claim 21
Dependent Claim
19 words
A method according to claim 16 wherein said nodes are connected to a router or server by serial links.
Claim 22
Independent Claim
190 words
A method of congestion avoidance in a packet data communications network having a plurality of nodes, comprising, in each of said nodes, the steps of: a) sending data from a source node of said network to a destination node, using a selected window size or rate including a number of packets by which said step of sending takes place; b) receiving at said source node an acknowledgement of said data from said destination node; c) recording the delay time between said step of sending and said step of receiving; d) again sending data from said source node of said network to a destination node, using a window size or rate for said step of sending different from said selected window size or rate; e) again receiving at said source node an acknowledgement of said data from said destination node; f) comparing said recorded delay time with the delay time between said step of again sending and said step of again receiving; and g) increasing or decreasing the window size or rate in response to said step of comparing to provide an operating point of maximum throughput at minimum delay time.
Claim 23
Independent Claim
190 words
A method of congestion avoidance in a packet data communications network having a plurality of nodes, comprising, in each of said nodes, the steps of: a) sending data from a source node of said network to a destination node, using a selected window size or rate including a number of packets by which said step of sending takes place; b) receiving at said source node an acknowledgement of said data from said destination node; c) recording the delay time between said step of sending and said step of receiving; d) again sending data from said source node of said network to a destination node, using a window size or rate for said step of sending different from said selected window size or rate; e) again receiving at said source node an acknowledgement of said data from said destination node; f) comparing said recorded delay time with the delay time between said step of again sending and said step of again receiving; and g) increasing or decreasing the window size or rate in response to said step of comparing to provide an operating point of maximum throughput at minimum delay time.
Claim 24
Dependent Claim
17 words
A method according to claim 19 wherein said data is sent in a plurality of separate packets.
Claim 25
Dependent Claim
23 words
A method according to claim 20 wherein said step of increasing or decreasing the window size is in an integral number of packets.
Claim 26
Dependent Claim
79 words
Apparatus for providing congestion avoidance in a computer network, comprising: means for measuring the delay between sending data from a source and receiving an acknowledgement from a destination, and for again measuring the delay between sending data from a source and receiving an acknowledgement from a destination, with a different loading of said data by said source; and means for changing the loading by said source to an optimum value in response to the difference in said measured delays.
Claim 27
Dependent Claim
79 words
Apparatus for providing congestion avoidance in a computer network, comprising: means for measuring the delay between sending data from a source and receiving an acknowledgement from a destination, and for again measuring the delay between sending data from a source and receiving an acknowledgement from a destination, with a different loading of said data by said source; and means for changing the loading by said source to an optimum value in response to the difference in said measured delays.
Claim 28
Dependent Claim
23 words
Apparatus according to claim 22 wherein said means for changing the loading changes the number of packets of data sent by said source.
Claim 29
Dependent Claim
34 words
Apparatus according to claim 22 wherein said means for sending transmits a number of packets of data from one node of the network through at least one router to another node of the network.
Claim 30
Dependent Claim
105 words
Apparatus for controlling a node in a data communications network, comprising: transmitter/receiver means for sending data of a selected window size and of a second window size different from said selected window size from said node of said network to a destination node and for receiving at said node acknowledgement from said destination node of said data sent; means for comparing the delay time between said sending and receiving for said selected window size with the delay time between said sending and receiving for said second window size and increasing or decreasing the window size in response to said comparing for subsequent sending of data.
Claim 31
Dependent Claim
105 words
Apparatus for controlling a node in a data communications network, comprising: transmitter/receiver means for sending data of a selected window size and of a second window size different from said selected window size from said node of said network to a destination node and for receiving at said node acknowledgement from said destination node of said data sent; means for comparing the delay time between said sending and receiving for said selected window size with the delay time between said sending and receiving for said second window size and increasing or decreasing the window size in response to said comparing for subsequent sending of data.
Claim 32
Dependent Claim
18 words
Apparatus according to claim 25 wherein said window sizes each consists of an integral number of data packets.
Claim 33
Dependent Claim
30 words
Apparatus according to claim 26 wherein said means for comparing causes said window size to increase when said comparing of the delays shown there is no difference in the delays.
References Cited (Backward Citations)
US109503A
Cited
US110009A
Cited
US110513A
Cited
US4063220A
Cited
US4490785A
Cited
US4560985A
Cited
US4777595A
Cited
US4560985B1
Cited
USPTO Annuity & Maintenance Windows
Maintenance schedule is calculated for granted US utility patents.