System for avoiding network congestion by distributing router resources equally among users and forwarding a flag to those users utilize more than their fair share

• US 5,491,801 A
• Filed: 08/23/1994
• Issued: 02/13/1996
• Est. Priority Date: 04/22/1988
• Status: Expired due to Term

• Current Assignee: Enterasys Networks Incorporated (Extreme Networks, Inc.)
• Original Assignee: Digital Equipment Corporation (HP Inc.)
• Inventors: Chiu, Dah-Ming, Ramakrishnan, K. K., Jain, Rajendra K.
• Primary Examiner(s): Lee, Thomas C.
• Assistant Examiner(s): Luu, Le Hien
• Application Number:
  US08/294,291
• Time in Patent Office: 539 Days
• Field of Search: 395/200, 395/650, 395/550, 395/250, 395/325, 395/800, 370/17, 370/95.3, 370/124, 370/60, 370/58.2, 370/85.5, 370/58.3, 370/84, 370/94.3, 364/514, 379/221
• US Class Current: 709/241
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/11 Identifying congestion
• CPC Class Codes: H04L 47/263 Rate modification at the source after receiving feedback
• 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
• CPC Class Codes: Y02D 30/50 in wire-line communication networks, e.g. low power modes or reduced link rate

Abstract

Method and apparatus for operating a digital communication network to avoid congestion by detecting load conditions at intermediate stations exceeding an overload condition, flagging information packets associated with those streams of traffic accounting for more than their fair share of throughput at such overloaded stations, and reducing at the end systems the throughput of those streams of traffic of which more than a predetermined fraction of the information packets received by the end systems are flagged.

Claims

1. A system for signalling congestion status by a station on a network comprising:

a. means for receiving at said station a plurality of streams of traffic passing through said network;

b. calculation means for determining if a congestion avoidance calculation should be begun at the present time, and if the determination is to begin a congestion avoidance calculation;

calculating a fair share of unallocated capacity of said station for each user,

identifying users which are utilizing less than or equal to their fair share, and

removing identified users from subsequent iterations and recalculating unallocated capacity until no further users can be removed,

c. means for setting a congestion avoidance flag on packets received from remaining unidentified users; and

d. means for forwarding a packet having said congestion avoidance flag set.

2. The system of claim 1 further including means for transmitting congestion avoidance information to said remaining unidentified users, said information causing said users to reduce their packet transmission rates.

3. The system of claim 2 wherein said means for transmitting congestion avoidance information transmits congestion avoidance information to said remaining unidentified users by transmitting said congestion avoidance information to one or more selected source end stations associated with said users.

4. 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 one intermediate system, a method for identifying streams of traffic which account for a throughput at an intermediate system that is greater than an-allocated share of the throughput capacity of said intermediate system, comprising the steps of:

identifying streams of traffic passing through the intermediate system during a traffic measuring interval;

allocating the throughput capacity of said intermediate system among streams of traffic passing through said intermediate system; and

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 throughput capacity of said intermediate system;

determining at said intermediate system whether the intermediate system is in an overload condition;

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 accounting for a throughput at the intermediate system, during a traffic measuring interval, that is greater than an allocated share of throughput capacity of said intermediate system.

5. The method of claim 4, wherein said step of identifying those streams of traffic that account for a throughput that is greater than an allocated share of throughput capacity further comprises:

determining the average throughputs of the interval-identified streams of traffic during said traffic measuring interval;

in an iterative procedure, starting with an unallocated capacity equal to an estimated capacity of the intermediate system,

further identifying each interval-identified stream of traffic with an average throughput 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;

subtracting the average throughput of the further identified streams of traffic from the unallocated capacity among each interval-identified stream of traffic to be considered in a current iteration;

subtracting the average throughput of the further identified streams of traffic from the unallocated capacity; and

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 streams of traffic causing an overload condition.