Congestion avoidance scheme for computer networks
First Claim
Patent Images
1. A method for operating a network in which end systems communicate by means of transmission and reception of digital information packets routed through at least one intermediate system, said method comprising the steps of:
- A. transmitting information packets at a source end system toward a destination end system, wherein only a maximum number of said information packets may be transmitted within an interval;
B. determining at an intermediate system whether the intermediate system is in an overload condition;
C. if the intermediate system is in an overload condition, identifying a stream of traffic as causing said overload condition if, during a traffic measuring interval, its constituent information packets account for a throughput at the intermediate system that is greater than an allocated share of an estimated throughput capacity of the intermediate system;
D. setting at said intermediate system, if it is determined to be in said overload condition, a congestion avoidance flag in each information packet that is a constituent of a stream of traffic identified as causing said overload condition in step C;
E. determining whether a sequence of information packets received by said destination end system from said source end system includes a fraction with set congestion avoidance flags wherein said fraction exceeds a threshold fraction; and
F. adjusting at said source end system, in response to said determination whether said fraction exceeds said threshold fraction, said maximum number of information packets to be transmitted within said interval towards said destination end system.
6 Assignments
0 Petitions
Accused Products
Abstract
Method and apparatus for operating a digital communication network to avoid congestion by detecting load conditions at the routers exceeding their knee capacities, flagging information packets associated with those streams of traffic accounting for more than their fair share of throughput at such overloaded routers, and reducing at the end systems the throughput of those streams of traffic for which more than a predetermined fraction of information packets received by the end systems are flagged.
168 Citations
10 Claims
-
1. A method for operating a network in which end systems communicate by means of transmission and reception of digital information packets routed through at least one intermediate system, said method comprising the steps of:
-
A. transmitting information packets at a source end system toward a destination end system, wherein only a maximum number of said information packets may be transmitted within an interval; B. determining at an intermediate system whether the intermediate system is in an overload condition; C. if the intermediate system is in an overload condition, identifying a stream of traffic as causing said overload condition if, during a traffic measuring interval, its constituent information packets account for a throughput at the intermediate system that is greater than an allocated share of an estimated throughput capacity of the intermediate system; D. setting at said intermediate system, if it is determined to be in said overload condition, a congestion avoidance flag in each information packet that is a constituent of a stream of traffic identified as causing said overload condition in step C; E. determining whether a sequence of information packets received by said destination end system from said source end system includes a fraction with set congestion avoidance flags wherein said fraction exceeds a threshold fraction; and F. adjusting at said source end system, in response to said determination whether said fraction exceeds said threshold fraction, said maximum number of information packets to be transmitted within said interval towards said destination end system. - View Dependent Claims (2, 3, 4, 5, 6, 7)
-
-
8. In a network of end systems communicating by means of transmission and reception of digital information packets routed through at least one intermediate system, a method for indicating when the intermediate system is approaching a state of congestion, said method comprising the steps of:
-
A. determining at an intermediate system whether the intermediate system is in an overload condition; B. if the intermediate system is in an overload condition, identifying those streams of traffic that are causing the overload condition by; a. identifying streams of traffic passing through the intermediate system during a traffic measuring interval; b. determining the average throughputs at the intermediate system of the interval-identified streams of traffic during said traffic measuring interval; c. in an iterative procedure, starting with an unallocated capacity equal to an estimated capacity of the intermediate system, i. further identifying each interval-identified stream of traffic with an average throughput at the intermediate system less than or equal to its share of unallocated capacity according to a weighted division of the unallocated capacity among each interval-identified stream of traffic to be considered in a current iteration; ii. subtracting the average throughput of the further identified streams of traffic from the unallocated capacity; and iii. removing the further identified streams of traffic from consideration in the next iteration, until no further identifications are made, at which point, the interval-identified streams of traffic which have not been further identified are identified as the streams of traffic causing the overload condition; and C. if the intermediate system is in the overload condition, signaling end systems by setting at the intermediate system a congestion avoidance flag in an information packet routed through the intermediate system that is a constituent of a stream of traffic identified in step B as causing the overload condition.
-
-
9. In a network of end systems communicating by means of transmission and reception of digital information packets forming at least two different streams of traffic routed through at least on intermediate system, a method for identifying streams of traffic which are causing an overload condition at the intermediate system, said method comprising the steps of:
-
A. determining whether the intermediate system is in an overload condition characterized by operation above an optimal operating level; B. identifying streams of traffic passing through the intermediate system during a traffic measuring interval; C. setting an estimated capacity for the intermediate system equal to a total intermediate system throughput, from all streams of traffic passing through the intermediate system during said traffic measuring interval, multiplied by a capacity factor; D. allocating the estimated throughput capacity among streams of traffic passing through the intermediate system; and E. identifying those streams of traffic that account for a throughput at the intermediate system, during a traffic measuring interval, that is greater than an allocated share of an estimated throughput capacity of the intermediate system by a. determining the average throughputs at the intermediate system of the interval-identified streams of traffic during said traffic measuring interval; b. in an iterative procedure, starting with an unallocated capacity equal to an estimated capacity of the intermediate system, i. further identifying each interval-identified stream of traffic with an average throughput at the intermediate system less than or equal to its share of unallocated capacity according to a weighted division of the unallocated capacity among each interval-identified stream of traffic to be considered in a current iteration; ii. subtracting the average throughput of the further identified streams of traffic from the unallocated capacity; and iii. removing the further identified streams of traffic from consideration in the next iteration, until no further identifications are made, at which point, the interval-identified streams of traffic which have not been further identified are identified as the streams of traffic causing the overload condition.
-
-
10. A feedback device, for use in a network of end systems communicating by transmission and reception of digital information packets associated with streams of traffic routed through at least one intermediate system:
-
A. means for determining at an intermediate system whether said intermediate system is in an overload condition characterized by operation of the intermediate system above an optimal operating level; B. means for identifying those streams of traffic that are causing the overload condition, if said intermediate system is in an overload condition, said means including a. means for identifying streams of traffic passing through the intermediate system during a traffic measuring interval; b. means for determining the average throughputs at the intermediate system of the interval-identified streams of traffic during said traffic measuring interval; c. means for performing iteratively, starting with an unallocated capacity equal to an estimated capacity of the intermediate system, the steps of i. further identifying each interval-identified stream of traffic with an average throughput at the intermediate system less than or equal to its share of unallocated capacity according to a weighted division of the unallocated capacity among each interval-identified stream of traffic to be considered in a current iteration; ii. subtracting the average throughput of the further identified streams of traffic from the unallocated capacity; and iii. removing the further identified streams of traffic from consideration in the next iteration, until no further identifications are made, at which point, the interval-identified streams of traffic which have not been further identified are identified as the streams of traffic causing the overload condition; and C. means for signaling end systems by setting at the intermediate system a congestion avoidance flag in information packets routed through the intermediate system when the intermediate system is determined to be in said overload condition.
-
Specification