Efficient Distributed Method for Computing Max-Min Fair Rates of a Limited Resource in ATM Networks

This invention relates to data communications, and more particularly to congestion avoidance in networks.

In any computer communications network, one may find a large number of source nodes vying for a limited number of resources in order to transfer data to a number of destination nodes. Typically, messages are sent from a source node via a communications line to one or more switches in a network, and then forwarded to a destination node. In addition, destination nodes will respond to message received from source nodes via a communication line, and this communication results in feedback from the destination node to the source node. As can be appreciated, when any number of source nodes begin transmitting data toward a network comprised of one or more network connections that may be described generally as network resources, each of these nodes would like to obtain the greatest amount of throughput possible in order to get the data transferred through the network resource to the respective destination nodes. Thus, the situation occurs that a number of nodes vie for the same network resource. When this occurs, a situation called "bottleneck" may occur. Bottleneck can be described generally as a condition that occurs in a network resource when all of the bandwidth within the network resource is used up by the competing source nodes trying to transfer data through it.

Various methods to control congestion at various network resources within a network are known. For example, a node wishing to send data to a network resource captures a channel to that network resource, sends data to that network resource, which subsequently transfers that data from the network resource to a destination node. In turn, the destination node may return an acknowledgment, sometimes referred to as an ACK, to the source node. In this method, the message being transferred to the network resource may carry a flag, which when a bottleneck situation is discovered in the network resource, the network resource in turn sets this flag (or bit) on the incoming message, and routes it to the destination node. The destination node, upon checking the bit or flag, finds the bit set and returns a message through the network resource back to the source node that originated the message, indicating that the source node should slow down sending messages.

Another method that is well known in the art is known as rate based congestion control. As is well known, this scheme requires a distributed computation of fair rate allocations of the total bandwidth for each network resource in the network. The generally accepted fairness metric for this method is known as max-min fair rates. With this method, the network looks at the worst bottleneck within the network, i.e., the network resource with the largest number flows passing through. Once this network resource is discovered, the rate of flows through the network resource are adjusted, and the method continues by removing that network resource from the network and then looking at the next worst bottleneck network resource. This process is continually repeated until there are no bottlenecks found.

In the so-called "end-to-end" scheme, a source node will send a rate request in an information cell to a network resource, that network resource will look at the rate request and decide which rate is appropriate to give for that connection. The network source then includes that rate in the resource cells going back to the source, and the source adjusts its throughput accordingly. As is well known with this method, the problem is how should the network resource allocate bandwidths to each flow. As is currently known, rate allocation of bandwidth is done on a "per outgoing network resource" basis.

What is desired is a method that works locally on a network resource, such as an asynchronous transfer mode (ATM) switch, to determine a specific rate allocation. With such a method, a specific rate allocation would be requested by each virtual circuit (VC), and the maximum fair rate that can be allocated for that VC by that network resource would be computed. This method would result in a computed allocation of bandwidth that is always less than or equal to the requested rate.

A method for computing fair rates in a computer network is provided including the steps of providing a plurality of source nodes, providing a plurality of destination notes, providing a plurality of switches to connect each one of the plurality of source nodes to each one of the plurality of destination nodes, selecting a first switch, the first switch having an associated allocated bandwidth, selecting a first source node, the first source node establishing a first connection to the first switch, selecting a first destination node, the first destination node establishing a second connection to the first switch, sending a plurality of data cells from the first source node via the first connection to the first switch, one of the data cells being a forward resource management cell containing a forward rate request value, reading the forward rate request value, computing a computed fair rate request value from the forward rate request value, sending a plurality of data cells from the first destination via the second connection to the first switch, one of the data cells being a reverse resource management cell having a reverse rate request value, reading the reverse rate request value, comparing the computed rate request value and the reverse rate request value, inserting the computed rate request value into the reverse resource management cell if the computed rate request value is less than the reverse rate request value, and adjusting a rate at which the plurality of cells are sent from the first source node acceding to the rate request value in the reverse resource management cell.

The novel features believed characteristic of the invention are set forth in the appended claims. The invention itself, however, as well as features and advantages thereof, will be best understood by reference to the detailed description of specific embodiments, which follow, when read in conjunction with accompanying drawings, wherein:

FIG. 1 is a block diagram of an exemplary computer network in which the present invention may be used;

FIG. 2 is a block diagram of one of the switches of FIG. 1;

FIG. 3 is a block diagram of the rate processing engine of the switch shown in FIG. 2; and

FIG. 4 is a flow chart illustrating the invention as it resides in the rate processing engine of FIG. 3.

Referring to FIG. 1, an exemplary asynchronous transfer mode (ATM) network is shown to include seven nodes labeled as 10, 12, 14, 16, 18, 20, and 22, respectively. Nodes 10, 12, 14, and 16, may generally be referred to as source nodes, while nodes 18, 20, and 22 may generally be referred to as destination nodes. However, in actual operation, any one node in the exemplary network of FIG. I may send data to any one or more of the other nodes in the exemplary network. The exemplary network of FIG. I is also shown to include three network resources referred to switch 24, switch 26, and switch 28. The exemplary network also shows a link 30 and a link 32.

By way of example, a connection has been established between nodes 10 and 18, respectively. This connection consists of link 34, switch 26, link 32, and link 36. Each connection between a source node and a destination node is as referred as a virtual circuit (VC).

As mentioned above, the exemplary VC contains the link 32. Generally, a link provides communication between two switches. Specifically, link 32 provides communication between switch 26 and switch 28, while link 30 provides communication between switch 24 and 26.

As can be seen in FIG. 1, link 32 is a primary bottleneck in the exemplary network, while link 30 is a secondary bottleneck in the exemplary network.

An exemplary communication from source node 10 to destination node 18 may occur in the following manner. Node 10 establishes a VC to node 18. The source node 10 begins sending data in the form of cells of information on line 34 to switch 26. For ease of discussion, this flow of cells from source node 10 is referred to as the forward direction. One of these cells is referred to as a resource management cell or RM cell and contains a rate request. The rate request in the RM cell is what source node 10 would like for bandwidth through the switch 26. If a congestion condition exists in switch 26, the switch 26 fills in the rate request that it can accommodate for the VC in an RM cell traveling in the reverse direction, i.e., traveling to source node 10. This returning RM cell will be read by node 10 and inform it that congestion has occurred somewhere in the network and that source node 10 should decrease the flow rate at which it is sending cells on the VC to node 18 to the rate specified in the RM cell.

The mechanism just described in which a source node 10 sends information through a network to a destination node 18 and the destination node 18 sends feedback information to the source node 10 is known generally as a rate based congestion control scheme. Referring now to FIG. 2, the switch 26 is shown in greater detail. The switch 26 is shown to include a receive buffers 40, a rate processing engine 42, a transmit buffers 44, a receive buffers 46, and a transmit buffers 48. In an typical fashion, cells are sent from node 10 to receive buffers 40. In rate processing engine 42, any RM cells are read. Other cells continue to transmit buffers 44, and then on to node 18. Node 18 also sends cells toward switch 26; these cells from node 18 arrive in the receive buffers 46. The cells then flow through the rate processing engine 42 and enter transmit buffers 48. From there, the cells flow to node 10. The cells sent from node 18 to node 10 also contain RM cells. All cells from the node 18 to the node 10 are generally referred as flowing in the reverse direction. The RM cells flowing in the reverse direction are read by the rate processing engine 42, and then injected back into the flow of cells toward the node 10.

Referring now to FIG. 3, the rate processing engine 42 of FIG. 2 is shown in greater detail. Cells flowing in the forward direction 50 contain RM cells. The rate processing engine 42 reads the rate request contained an RM cell flowing in the forward direction and submits it to the process engine 52. The process engine adjusts the rate request according to principles to be fully described with reference to FIG. 4. Once the process engine calculates a rate, the rate processing engine reads a rate request from a RM cell flowing in the reverse direction 54, compare the actual rate to the calculated rate, and injects the calculated rate back into the RM cell flowing in the reverse direction if the requested rate found in the RM cell flowing in the reverse direction is equal to or greater than the calculated rate.

Referring now to FIG. 4, the rate processing engine 42, calculates a max-min fair rate for the switch 26 in the indicated steps. At step 100, the rate processing engine performs a four part initialization. First, the max-min fair rate allocated for the particular connection based on the requested allocation rate is set to zero. Next, the bottleneck status of the connection is set to zero. Third, the number of connections bottleneck at the switch 26 is set equal to zero. Lastly, the total bandwidth allocated to non-bottleneck connections is set to zero. At step 102, a RM cell is received in a forward direction. If no RM cell is received, the method waits until there is a RM cell received. At step 104, the RM cell, with its rate request is read by the rate processing engine. At step 106, the bottleneck connection of the requested connection is checked. At step 108, the rate processing engine 42 determines whether the connection is bottlenecked or not. If the connection is bottlenecked, the rate processing engine proceeds to step 110 where the total number of bottleneck connections is reduced by one. If at step 108 the connection is not bottlenecked, at step 112 the rate processing engine removes the requested rate amount from the total bandwidth available at the switch 26. At step 114, a fair rate allocation is computed First, a connection is said to be bottlenecked if the requested rate is greater than or equal to the quantity "link capacity minus the total bandwidth allocated to non-bottlenecked connections, divided by the number of connections bottlenecked at this link plus one." If the connection is not bottlenecked, the max-min fair rate allocated for the connection based on the requested allocation is set equal to the requested allocation. If the connection was determined to be bottlenecked, the max-min fair rate allocation for the connection based on the requested rate is set equal to the link capacity minus the total bandwidth allocated to non-bottlenecked connections, divided by the number of connections bottlenecked at the link plus one. Now that the fair rate allocation has been computed at step 114, the computed fair rate allocation is injected into a RM cell proceeding in the reverse direction at step 116. The process then cycles back to step 100.

Thus, the method shown in FIG. 4 computes the optimal rate by performing a single lookup of the state for the particular connection. The discrepancies due to omitting the lookup for other connections are corrected when those connections request a rate allocation.

Having described a preferred embodiment of the invention, it will now become apparent to those skilled in the art that other embodiments incorporating its concepts may be provided. It is felt therefore, that this invention should not be limited to the disclosed invention, but should be limited only by the spirit and scope of the appended claims.