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

What is claimed as new and desired to be secured by Letters Patent of the United States is:

1. 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.

2. 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.

3. 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.

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

5. 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.

6. 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.

7. 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.

8. 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.

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

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

11. 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.

12. 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.

13. 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.

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

15. 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.

16. 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.

17. 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.

18. 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.

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

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

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

22. 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.

23. 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.

24. 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.

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

26. 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.

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

28. 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.

29. 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.

30. 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.

31. 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.

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

33. 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.

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

35. 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.

Description Submit all comments and votes

FIELD OF THE INVENTION

This invention relates generally to the field of computer networks, and particularly to a congestion avoidance scheme for computer networks.

BACKGROUND OF THE INVENTION

In general terms, a computer network is a collection of end systems interconnected through one or more routers. Generally, the end systems both send data to other end systems on the network and receive data sent by other end systems on the network. When an end system is a sender of data, it is referred to as a source for that data; whereas, when it is a receiver of data, it is referred to as a destination for the data. Typically, end systems act as both sources and destinations depending upon whether they are sending or receiving data. When acting as a source, the end system sends data in the form of messages over a communication link to a router, which is also known as an intermediate system or gateway. Emanating from the router are a number of other communication links, each one representing a connecting path over which messages can flow back and forth to other routers and end systems within the network. Essentially, the router is a switching element which processes messages by transferring the messages arriving over one link onto another link for transmission to an end system or another router.

Each message comprises a sequence of information bits. Typically, however, the messages sent over the network are not sent as a continuous, uninterrupted stream of bits. Rather, they are divided up into smaller blocks of information called packets, which are then transmitted individually. Each packet has a predetermined maximum length. In addition to a data field which contains the data to be transferred, a packet also includes a header field which contains control information such as format, identifiers which indicate what portion of the message is contained in the packet, the source of the packet and the intended destination of the packet. When the packets which together contain a message reach the destination, the destination processes them by assembling their data fields into proper order to reconstruct the full message.

An important design objective in networks is controlling the flow of packets so that they will not be transmitted at a faster rate than they can be processed by the routers through which the packets will pass or by the destinations. Even in the simplest network consisting of two end .systems interconnected by a router, the source may flood the destination if it transmits packets faster than they can be processed by the destination. In more complicated networks consisting of many end systems, numerous routers and alternative communication paths between the end systems, the likelihood of problems from excess communication traffic is significantly greater. This becomes especially true as the number of active end systems on the network increases and if communication speeds of the equipment within the network are mismatched. A mismatch may exist if, for example, a router cannot transfer packets as fast as they are being sent to it by the source. A mismatch may also exist between the speed at which the link can transmit packets, namely the link speed, and the rate at which the router can transfer packets. Predictably, as the complexity of the network increases, achieving an acceptable traffic control also becomes more difficult.

On most networks, at least two basic mechanisms are normally used for dealing With excess traffic arriving at a destination. One mechanism involves the use of buffers and the other involves flow control. In buffered systems, both the routers and the end systems are provided with buffer memory to handle overloads. Arriving traffic which exceeds the processing rate of the device is temporarily stored in the buffer memory until the device can process it. Buffers offer a satisfactory solution to excess traffic problems only if the overload is transitory. If the overload persists for too long, the buffers may become full after which the additional packets are rejected or destroyed.

The other mechanism, generally referred to as flow control, deals with the allocation of resources at the destination, such as memory and processing. Generally, in accordance with flow control, the destination sets a limit on the rate at which each source sending data to the destination may transmit that data. The sources and the destinations coordinate the transfer of data by an exchange of messages containing requests and acknowledgements. Before the source starts sending packets, it will send a request to the destination seeking permission to begin transmission. In response to the request, the destination sends a message containing an identification of the number of packets the source may dispatch toward the destination without further authorization. This number is commonly referred to as the window size. The source then proceeds to transmit the authorized number of packets toward the destination and waits for the destination to verify their receipt. After the destination successfully receives a packet, it sends a message back to the source containing an acknowledgement indicating the successful receipt of the packet and, in some cases, authorizing the source to send another packet. In this way, the number of packets on the network traveling from the source toward the destination will never be more than the authorized window size.

Neither of these mechanisms, however, satisfactorily deals with the distribution of traffic within the network. Even with these mechanisms in place, on a busy network it is likely that many sources will simultaneously send traffic over the network to more than one destination. If too much of this traffic converges on a single router in too short a time, the limited buffer capacity of the router will be unable to cope with the volume and the router will reject or destroy the packets. When this happens, the network is said to be congested.

When the network is congested, network performance degrades significantly. The affected sources have to retransmit the lost or rejected packets. Retransmissions, however, necessarily use network resources such as buffer storage, processing time and link bandwidth to handle old traffic thereby leaving fewer resources for handling those portions of the messages still waiting to be transmitted for the first time. When that occurs, network delays increase drastically and network throughput drops. Indeed, since some network resources are being dedicated to handling retransmissions at a time when the network is already experiencing a heavy load, there is a substantial risk of the congestion spreading and locking up the entire network. As a consequence, it takes the network much longer to extricate itself from congestion than to get into it.

A variety of alternative approaches exist for dealing with network congestion. Generally, the approaches fall into two categories. One category involves placing limitations on the amount of traffic which will be permitted on the network at any given time. The other category involves methods of limiting the spread of congestion once it occurs and then extricating the network from its congested state.

An approach which falls under the first category is the isarithmic method. According to this approach, a user can send a packet over the network only if it has a permit. There are, however, only a limited number of available permits to be shared by all end systems on the network. As a result, the number of packets on the network at any one time is also limited. A proper choice of the number of available permits significantly reduces the likelihood of congestion. The price paid for this method of control, however, is substantial. First, this method may yield an inefficient use of network resources. To protect against the possibility of traffic converging on a single router and causing congestion, network traffic must be limited to a level which is significantly below network capacity. Thus, a slow router may impact end systems that do not even have traffic flowing through that router. Secondly, distributing permits becomes a serious problem. While inactive end systems are holding onto permits, other end systems who need them cannot use the available network resources. And third, the method really does not address the distribution of traffic on the network which is the real cause of network congestion.

Another example from the first category involves the preallocation of buffers at the routers. This approach is used on networks which create a virtual circuit through the router to handle communications between two end systems. A virtual circuit is essentially a channel over the network which is dedicated to handling only the communications between the two end systems and which appears as though it is an actual physical circuit. The virtual circuit, however, is not an actual physical circuit connecting the two end systems but rather is a mechanism for transporting messages between them. When the network establishes the virtual circuit between two end systems, routers along the path over which the packets will pass set aside buffers and other router resources to handle only the traffic between the two end systems. By preallocating buffers in this manner, the routers will always have memory available to store arriving packets until they can be forwarded. As with the isarithmic method, a major drawback to this approach is that it is inefficient. Even during periods of inactivity, buffers and other router resources committed to one virtual circuit cannot be used to handle packet transfers associated with communications between other end systems.

The second category of approaches for dealing with network congestion is commonly referred Go as congestion control. Congestion control typically involves feedback which signals the onset of congestion and instructs end systems to decrease the rate at which they initiate transmission of packets. Under one approach, the routers send special messages, commonly referred to as "choke packets" or "source quench packets", to the sources, requiring the sources to reduce their traffic on the network. To determine which sources are to receive the choke packets, the router monitors its communication links to detect when their utilization rates rise above a preselected threshold level. When the threshold level is exceeded, the router sends a choke packet back to the sources that generated the packets which are arriving at the router. In response, the sources decrease their output. The most obvious disadvantage of this approach is that it requires adding traffic, in particular, the choke packets, to the network at a time when the network is least able handle the added traffic. A second disadvantage is it penalizes sources which may not be significant contributors to the traffic overload.

Another method of congestion control which has been used is delay sensitive routing. According to this method, the routers maintain tables which indicate the delays associated with the different paths passing through them. As traffic moves through the network, paths are selected by the routers to yield the lowest delays to the intended destinations. To update the delay tables maintained by the routers, the routers periodically measure the delays on the various paths and then communicate the delay information to each other over the network. As with the previous method, delay-sensitive routing requires adding traffic to the network, which may not be desirable. In addition, delays may vary too quickly to provide an effective method for routing. Moreover, any attempt to keep them current results in high overhead due to the large volume of required updating activity and the inter-router communication of delay information.

A third approach to congestion control involves piggybacking the feedback information onto packets which are traveling back in the direction from which the traffic causing the congestion is coming. Unlike the previous two examples, this does not result in additional traffic. However, the drawback to the approach is that the reverse traffic may not be going to the sources which are the cause of or even participants in the congestion on the forward path.

SUMMARY OF THE INVENTION

The invention provides a new and improved mechanism, and associated method, for avoiding congestion on a network. The responsibility for implementing the method is distributed throughout the network and is shared by the routers and the end systems. In accordance with the invention, each router, independent of the other routers in the network, seeks to constrain the total traffic which it handles, i.e. its load, to within a region of optimum performance for that router.

The method comprises two processes, namely, a feedback process, which is implemented by routers in the network, and a control process, which is implemented by the end systems in the network. In performing the feedback process, a router determines the existence of an overload condition by detecting when it is operating beyond an estimated capacity level, it calculates a fair share of the estimated capacity level for each end system sending packets to the router and then, it identifies which end systems are sending more than a fair share of traffic received by the router. By conditioning a flag in the packets coming from the identified end systems, the router generates feedback indicating that the identified end systems are contributing to the overload condition in the router and that they should decrease their output.

The router transfers the packet carrying the information contained in the flag on toward its intended destination. After the destination receives the packet, it responds in one of two ways depending upon how the invention is implemented. If the destination has responsibility for processing the information contained in the flag, the destination will determine how the source should adjust its output by performing the control process and then feed this determination back to the source in a message carrying the acknowledgement. On the other hand, if the source has responsibility for processing the information contained in the flag, the destination will transfer the flag to the message carrying the acknowledgement back to the source and the source will then determine how it should adjust its output by performing the control process.

In accordance with the control process, the end system monitors the congestion avoidance flags which it receives to determine whether corrective action is called for. If the condition of the flags indicates that corrective action is called for, the end system implements a load adjustment algorithm which causes the rate at which the source is transmitting packets onto the network to decrease. If, however, the condition of the flag indicates that no corrective action is called for, the load adjustment algorithm permits the rate at which the source is transmitting packets to increase.

BRIEF DESCRIPTION OF THE DRAWINGS

The invention is pointed out with particularity in the appended claims. The above, and further, advantages and aspects of this invention may be attained by referring to the following detailed description taken in conjunction with the accompanying drawings, in which:

FIG. 1 depicts the o