The Rate Control Algorithm

The NBP rate control algorithm regulates the rate at which each flow enters the network. Its primary goal is to converge on a set of per-flow transmission rates (hereinafter called ingress rates) that prevents congestion collapse from undelivered packets. It also attempts to lead the network to a state of maximum link utilization and low router buffer occupancies, and it does this in a manner that is similar to TCP.

Figure 6: Pseudocode for ingress router rate control algorithm

In the NBP rate control algorithm, shown in Figure 6, a flow may be in one of two phases, slow start or congestion avoidance, which are similar to the phases of TCP congestion control. New flows enter the network in the slow start phase and proceed to the congestion avoidance phase only after the flow has experienced congestion. The rate control algorithm is invoked whenever a backward feedback (BF) packet arrives at an ingress router. Recall that egress routers send two types of BF packets to ingress routers: normal BF packets, which are generated when an egress router receives a forward feedback (FF) packet, and asynchronous BF packets, which egress routers generate without any prompting from an ingress router. Both types of BF packets contain a list of flows arriving at the egress router from the ingress router as well as the monitored egress rate for each flow. However, only normal BF packets contain meaningful time stamps which are copied from arriving FF packets.

If the arriving BF packet is a normal BF packet, then the algorithm calculates the current round trip time and updates the base round trip time, if necessary. It then calculates deltaRTT, which is the difference between the current round trip time (e.currentRTT) and the base round trip time (e.baseRTT). A deltaRTT value greater than zero indicates that packets are requiring a longer time to traverse the network than they once did, and this can only be due to the buffering of packets within the network.

NBP's rate control algorithm decides that a flow is experiencing congestion whenever it estimates that the network has buffered the equivalent of more than one of the flow's packets at each router hop. To do this, the algorithm first computes the product of the flow's ingress rate and deltaRTT. This value provides an estimate of the amount of flow data that is buffered somewhere in the network. If it is greater than the number of router hops between the ingress and the egress router multiplied by the size of the largest possible packet, then the flow is considered to be experiencing congestion. The rationale for determining congestion in this way is to maintain both high link utilization and low queueing delay. Ensuring there is always at least one packet buffered for transmission on a network link is the simplest way to achieve full utilization of the link, and deciding that congestion exists when more than one packet is buffered at the link keeps queueing delays low.

When the rate control algorithm determines that a flow is not experiencing congestion, it increases the flow's ingress rate. If the flow is in the slow start phase, its ingress rate is doubled. Doubling the ingress rate allows a new flow to rapidly capture available bandwidth if the network is underutilized. If the flow is in the congestion avoidance phase, its ingress rate is conservatively incremented by a minimum rate change (MRC) value in order to avoid the creation of congestion. MRC is computed as the maximum segment size divided by the current round trip time between the edge routers. This results in rate growth behavior that is similar to TCP in its congestion avoidance phase. Furthermore, MRC is not allowed to exceed the flow's current egress rate divided by a constant factor (MF). This guarantees that rate increments are not excessively large when the round trip time is small.

When the rate control algorithm determines that a flow is experiencing congestion, it reduces the flow's ingress rate. If a flow is in the slow start phase, it enters the congestion avoidance phase. If a flow is already in the congestion avoidance phase, its ingress rate is reduced to the flow's egress rate decremented by MRC. In other words, an observation of congestion forces the ingress router to send the flow's packets into the network at a rate slightly lower than the rate at which they are leaving the network.

The actions described above are taken only when a normal BF packet arrives at an ingress router. A different set of actions is taken when an asynchronous BF packet arrives. This is because, unlike normal BF packets, asynchronous BF packets are not generated in response to FF packets and thus do not carry meaningful time stamps. Therefore, the congestion status of the network cannot be determined through the use of round trip time measurements. Instead, it is determined by comparing a flow's ingress and egress rates. In the slow start phase, a flow is considered to be experiencing congestion when its current ingress rate exceeds its reported egress rate by a factor of eight. The reason for the choice of the value eight is that we found a delay of three round trip times is typically required for a change in the ingress rate to be fully reflected in the egress rate of a backward feedback packet. During this time, the flow may double its ingress rate three times, increasing it by at most a factor of eight. Similarly, in the congestion avoidance phase, a flow is considered to be experiencing congestion whenever its current ingress rate exceeds its reported egress rate by three MRC increments. The reasoning in this case is similar to the reasoning used in the slow start case, except that a flow in the congestion avoidance phase may only increase its ingress rate by at most three MRC increments during three round trip times.

Clearly, the steps taken to determine congestion when an asynchronous BF packet arrives are more tolerant of transient congestion than the steps taken to determine congestion when a normal BF packet arrives. This is because asynchronous BF packets are only meant to be used as a stopgap measure to prevent serious congestion from developing during the interval between normal BF packet arrivals.