Stochastic Ordering for Internet Congestion Control

Overview

As the Internet evolves in its capacity and characteristics, demands for new congestion control adapting to the new operating conditions and goals are constantly increasing. As a result, many new protocols whose behaviors significantly deviate from TCP have lately been proposed. An emerging class of congestion control, called high-speed TCP variants are designed specifically for high bandwidth-delay product networks.

Many of these protocols differ mainly in their choices of window adjustment algorithms, in particular in the functions used in the growth phase of the congestion window. The choices of growth functions are diverse from exponential to some polynomial functions. For instance, STCP uses an exponential growth function, HSTCP uses a polynomial function, HTCP uses a square function, BIC uses a combination of logarithmic and exponential functions, and CUBIC uses a cubic function. Fig.1 shows the growth functions of five High-speed protocols.

Fig.1 the growth function of five High-speed TCP variants

The goal of stochastic ordering is to compare these growth functions, especially in terms of the second or higher-order stochastic behaviors of the protocols that employ these functions. A higher-order stochastic analysis offers a rich set of information about protocols, including the distribution of transmission rates, its variance and protocol stability. These are important information about protocols.

Further, stability is an important goal of congestion control as it can affect the general well-beings of the network including utilization, queue oscillations and packet loss characteristics. Thus, measuring the rate variations of flows is commonly used in practice to quantify the practical sense of “protocol stability”. For instance, many practitioners use the CoV (coefficient of variance, defined by the standard deviation over its mean) of per-flow transmission rate to measure stability. Therefore, it is clear that in practice, a quantifiable degree of stability is closely related to some higher order behaviors of protocols. Calculating the exact distribution of transmission rates¤ stochastically is non-trivial because of states involved in describing the behavior of protocols.

However, there is a hope. The main contribution of this paper is to use an alternative tool, called convex ordering, that provides a powerful insight into the high-order behaviors of protocols. Although it cannot be used to compute the rate distribution itself, convex ordering is extremely useful in comparing any convex function of congestion window sizes of protocols.

We find that convex ordering can be applied to many existing protocols that use multiplicative decrease (we call MD-style protocols) such as Scalable TCP, HSTCP, BIC, HTCP, etc. At the minimum, we can use it to compare the rate variance or CoV of per-flow rates of protocols (note that the function is convex). Our study of convex ordering on various existing growth functions has revealed the followings:

• Under stationary conditions, protocols with a more concave growth function has a lower convex ordering than those with a more convex function.
• Under non-stationary conditions, a protocol with a growth function that starts off with a concave function and then switches to a convex function at the origin (which we call a concave-convex function) has a lower convex ordering than those with just concave or convex functions.

Our results indicate that, under a variety of network conditions, a protocol with a concave-convex window growth function that uses the maximum window size in the last congestion epoch to be the inflection point, has mostly a concave window growth profile during steady state where available bandwidth remains stationary and a concave-convex window growth profile during non-stationary conditions where available bandwidth undergoes abrupt change. Thus according to our analysis, such a protocol has the lowest convex ordering. Among the existing protocols, BIC and CUBIC have this property. Our NS-2 simulation and Linux-based experimental results confirm these findings.

Download

NS2 Simulation Code

You need to replace following four files into NS-2.29.3.

File Name	Comment
errmodel.h	error model header
errmodel.cc	error model code
tcp.h	tcp.h modification
tcp.cc	tcp.cc modification

Experimental Results

• Click here to see the details of setup (topology, background traffic, RTT model, etc.) and huge number of raw results.

-- Main.sha2 - 08 Sep 2007