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

Claim 3

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.

Claim 4

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.

Claim 5

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.

Claim 6

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.

Claim 7

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.