US5675742A — System for setting congestion avoidance flag at i…

Claim 1

Independent Claim 147 words

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 being performed at the intermediate system and comprising the steps of: A. determining whether the intermediate system is in an overload condition characterized by operation of the intermediate system above an optimal operating level but below a congestion level; B. if the intermediate system is in the overload condition; i. selecting the end systems that are transmitting information packets at rates that are above their respective allocated fair shares; and ii. signaling one or more of the selected end systems by setting at the intermediate system a congestion avoidance flag in information packets routed through the intermediate system to one or more of the selected end systems.

Claim 2

Dependent Claim 147 words

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 being performed at the intermediate system and comprising the steps of: A. determining whether the intermediate system is in an overload condition characterized by operation of the intermediate system above an optimal operating level but below a congestion level; B. if the intermediate system is in the overload condition; i. selecting the end systems that are transmitting information packets at rates that are above their respective allocated fair shares; and ii. signaling one or more of the selected end systems by setting at the intermediate system a congestion avoidance flag in information packets routed through the intermediate system to one or more of the selected end systems.

Claim 3

Dependent Claim 70 words

The method of claim 1, wherein said intermediate system temporarily stores packets to create a queue having a queue length equal to the sum of the number of packets in the queue and the number of packets being serviced by the intermediate system, and wherein the overload condition is determined by determining, over a load averaging interval, an average queue length, that is greater than a first preselected queue length.

Claim 4

Dependent Claim 41 words

The method of claim 2, wherein operation of the intermediate system includes cycles of activity, each of which includes a busy period and an idle period, and wherein said load averaging interval includes at least one completed previous cycle of activity.

Claim 5

Dependent Claim 15 words

The method of claim 2, wherein the first preselected length is approximately equal to one.

Claim 6

Dependent Claim 67 words

The method of claim 1, wherein different streams of traffic comprising information packets are routed through said intermediate system, said method further comprising the step of: A1. identifying those streams of traffic that are causing the overload condition; and in step (B), setting a congestion avoidance flag only in an information packet that is a constituent of a stream of traffic identified as causing the overload condition.

Claim 7

Dependent Claim 51 words

The method of claim 5, wherein a stream of traffic is identified as causing the overload condition if its constituent information packets account for a throughput at said intermediate system, during a traffic measuring interval, that is greater than an allocated share of an estimated throughput capacity of the intermediate system.

Claim 8

Dependent Claim 41 words

The method of claim 6, wherein the throughput of the intermediate system as a function of load is characterized by a knee, and the estimated throughput capacity of the intermediate system is set to equal approximately the throughput at the knee.

Claim 9

Dependent Claim 56 words

The method of claim 6, wherein the estimated throughput capacity of the intermediate system is determined by setting the estimated capacity of 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, and multiplying the estimated capacity by a capacity factor.

Claim 10

Dependent Claim 14 words

The method of claim 8, wherein the capacity factor is approximately equal to 0.9.

Claim 11

Dependent Claim 15 words

The method of claim 1 wherein the congestion avoidance flag consists of a single bit.

Claim 12

Dependent Claim 121 words

In a network of end systems communicating by means of transmission and reception of digital 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; and B. if the intermediate system is in the overload condition, the intermediate system i. selecting end systems that are transmitted packets at rates that are above their respective fair shares; and ii. signaling selected end systems by including at the intermediate system congestion avoidance information in the packets routed through the intermediate system to one or more of the selected end systems.

Claim 13

Dependent Claim 121 words

In a network of end systems communicating by means of transmission and reception of digital 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; and B. if the intermediate system is in the overload condition, the intermediate system i. selecting end systems that are transmitted packets at rates that are above their respective fair shares; and ii. signaling selected end systems by including at the intermediate system congestion avoidance information in the packets routed through the intermediate system to one or more of the selected end systems.

Claim 14

Dependent Claim 70 words

The method of claim 11, wherein said intermediate system temporarily stores packets to create a queue having a queue length equal to the sum of the number of packets in the queue and the number of packets being serviced by the intermediate system, and wherein the overload condition is determined by determining, over a load averaging interval, an average queue length that is greater than a first preselected queue length.

Claim 15

Dependent Claim 41 words

The method of claim 12, wherein operation of the intermediate system includes cycles of activity, each of which includes a busy period and an idle period, and wherein said load averaging interval includes at least one completed previous cycle of activity.

Claim 16

Dependent Claim 15 words

The method of claim 12, wherein the first preselected length is approximately equal to one.

Claim 17

Dependent Claim 76 words

The method of claim 11, wherein different streams of traffic comprising packets are routed through said intermediate system, said method further comprising the steps of: identifying those streams of traffic that are causing the overload condition; in step Bi selecting end stations that are associated with the identified streams of traffic; and in step Bii, including congestion avoidance information only in packets that are constituents of the streams of traffic identified as causing the overload condition.

Claim 18

Dependent Claim 50 words

The method of claim 15, wherein the stream of traffic is identified as causing the overload condition if its constituent packets account for a throughput at said intermediate system, during a traffic measuring interval, that is greater than an allocated share of an estimated throughput capacity of the intermediate system.

Claim 19

Dependent Claim 41 words

The method of claim 16, wherein the throughput of the intermediate system as a function of load is characterized by a knee, and the estimated throughput capacity of the intermediate system is set to equal approximately the throughput at the knee.

Claim 20

Dependent Claim 58 words

The method of claim 16, wherein the estimated throughput capacity of the intermediate system is determined by (i) setting the estimated capacity of 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, and (ii) multiplying the estimated capacity by a capacity factor.

Claim 21

Dependent Claim 14 words

The method of claim 18, wherein the capacity factor is approximately equal to 0.9.

Claim 22

Dependent Claim 16 words

The method of claim 11, wherein the congestion avoidance information consists of a congestion avoidance flag.

Claim 23

Dependent Claim 24 words

The method of claim 11, wherein the congestion avoidance information consists of information about one or more desired operating conditions of the intermediate station.

Claim 24

Dependent Claim 137 words

A feedback device, for use in a network of end systems communicating by transmission and reception of digital packets routed through at least one intermediate system, comprising, 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 and below a congestion operating level; B. means at said intermediate system for selecting end systems that are operating above their respective allocated fair shares of throughput; and C. means for signaling one or more of the selected end systems by setting at the intermediate system a congestion avoidance flag in information packets routed through the intermediate system to one or more of the selected end systems when the intermediate system determines that said intermediate system is in said overload condition.

Claim 25

Dependent Claim 137 words

A feedback device, for use in a network of end systems communicating by transmission and reception of digital packets routed through at least one intermediate system, comprising, 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 and below a congestion operating level; B. means at said intermediate system for selecting end systems that are operating above their respective allocated fair shares of throughput; and C. means for signaling one or more of the selected end systems by setting at the intermediate system a congestion avoidance flag in information packets routed through the intermediate system to one or more of the selected end systems when the intermediate system determines that said intermediate system is in said overload condition.

Claim 26

Dependent Claim 77 words

The feedback device of claim 22, wherein said intermediate system temporarily stores packets to create a queue having a queue length equal to the sum of the number of packets in the queue and the number of packets being serviced by the intermediate system, and wherein said means for determining an overload condition further comprises means for comparing average queue length at the intermediate system, averaged over a load averaging interval, to a first preselected queue length.

Claim 27

Dependent Claim 42 words

The feedback device of claim 23, wherein operation of the intermediate system includes cycles of activity, each of which includes a busy period and an idle period, and wherein said load averaging interval includes at least one completed previous cycle of activity.

Claim 28

Dependent Claim 16 words

The feedback device of claim 23, wherein the first preselected length is approximately equal to one.

Claim 29

Dependent Claim 48 words

The feedback device of claim 23 further comprising means for determining that all streams of traffic routed through said intermediate system are causing the overload condition, said means comprising means for comparing the average queue length to a second preselected queue length, longer than the first preselected length.

Claim 30

Dependent Claim 16 words

The feedback device of claim 26 wherein the second preselected length is approximately equal to two.

Claim 31

Dependent Claim 38 words

The feedback device of claim 22, wherein said means for selecting includes means for identifying streams of traffic that are causing the overload condition said means selecting end systems that are part of the identified streams of traffic.

Claim 32

Dependent Claim 63 words

The feedback device of claim 28, wherein said means for identifying streams of traffic as causing the overload condition comprises: A11. means for comparing the number of information packets associated with a stream of traffic passing through the intermediate system during a traffic measuring interval with a share of an estimated throughput capacity of the intermediate system allocated to said stream of traffic.

Claim 33

Dependent Claim 54 words

The feedback device of claim 29, wherein said means for identifying streams of traffic as causing the overload condition further comprises means for determining the estimated throughput capacity of the intermediate system by measuring a total intermediate system throughput from all streams of traffic passing through the intermediate system during said traffic measuring interval.

Claim 34

Dependent Claim 54 words

The feedback device of claim 29, wherein operation of the intermediate system includes cycles of activity, each of which includes a busy period and an idle period, and wherein said means for identifying streams of traffic as causing the overload condition further comprises means for detecting when such cycles of activity begin and end.

Claim 35

Dependent Claim 15 words

The device of claim 22 wherein the congestion avoidance flag consists of a single bit.

Claim 36

Dependent Claim 88 words

A network of end systems communicating by means of transmission and reception of digital packets routed through at least one intermediate system, the intermediate system including: A. means for determining whether the intermediate system is in an overload condition; B. means for selecting end systems that are operating above their respective allocated fair shares of throughput; and C. means for signaling one or more of the selected end systems, said means including congestion avoidance information in the packets routed through the intermediate system to the selected end systems.

Claim 37

Dependent Claim 88 words

A network of end systems communicating by means of transmission and reception of digital packets routed through at least one intermediate system, the intermediate system including: A. means for determining whether the intermediate system is in an overload condition; B. means for selecting end systems that are operating above their respective allocated fair shares of throughput; and C. means for signaling one or more of the selected end systems, said means including congestion avoidance information in the packets routed through the intermediate system to the selected end systems.

Claim 38

Dependent Claim 15 words

The system of claim 33, wherein the means for signaling sets a congestion avoidance flag.

Claim 39

Dependent Claim 26 words

The system of claim 33, wherein the means for signaling includes in the packets information about one or more desired operating conditions of the intermediate station.

Annuity Stage	Window Opens	Payment Deadline	Surcharge Period Until	Estimated Fee	Status
3.5 Years (Year 4)	2000-10-06	2001-04-07	2001-10-07	$2000.00	Window Closed / Lapsed
7.5 Years (Year 8)	2004-10-06	2005-04-07	2005-10-07	$3760.00	Window Closed / Lapsed
11.5 Years (Year 12)	2008-10-06	2009-04-07	2009-10-07	$7700.00	Window Closed / Lapsed

System for setting congestion avoidance flag at intermediate node to reduce rates of transmission on selected end systems which utilizing above their allocated fair shares

Abstract

Inventors

Bibliographic Details

Claims Analysis

References Cited (Backward Citations)

USPTO Annuity & Maintenance Windows

Assigned Categories & Tags

Assign Category Tag