Stochastic Approach to the Design of Communication Networks: An Alternative to Fluid Modeling

Sponsored by National Science Foundation through CAREER Award CNS-0545893

Do Young Eun (Dept. of ECE, North Carolina State University)

Motivation

"Fluid" modeling has provided the basis for the understanding and design of various important networking problems including congestion control, stability analysis, optimization-based techniques, and peer-to-peer networks. This fluid modeling (or often called the mean-field approach) allows us to describe the average macroscopic behavior of network dynamics in terms of a set of relatively simple and deterministic difference/differential equations with averaged quantities. For example, the popular TCP/AQM congestion controls are mostly described by a set of delayed differential/difference equations where the focus is on the stability (or convergence) of the deterministic trajectory (solution of the differential/difference equations). Similarly, path selection problems in a peer-to-peer like network usually focus on some algorithmic aspects of the optimal selection process by assuming that the bandwidth of each peer is a fixed, averaged, and deterministic quantity, thus the optimal path becomes simply the path with the maximum averaged bandwidth.

Mathematically speaking, the fluid-based approach is equivalent to simplifying the originally complicated stochastic network dynamics by considering their averaged counterparts up front. For instance, suppose that a random process X(t) represents the `state' of a network (e.g., transmission rates of users), which evolves according to a given network algorithm (protocol), i.e., X(t+1)= f (X(t), U(t))  for some suitable function f with i.i.d. uniform random variables U(t) over [0,1]. (For example, the popular additive-increase-multiplicative-decrease (AIMD) algorithm in TCP corresponds to

f(x,u)= (x+1)(1-1{u £ p(x)}) + (x/2) 1{u £ p(x)}

where X  here is the window size or transmission rate of a user and p(x) is the probability of congestion or packet loss. 1{A} is the indicator function taking value of 1 if A is true and 0 otherwise.) The fluid modeling then intends to capture the average dynamics of the above random recursion via the following deterministic recursion

x(t+1) = E {X(t+1) | X(t) = x(t)}  = E { f (x(t), U(t)) } = G(x(t)),

and focus on the equilibrium point x* = G(x*) and its stability property (convergence of x(t) to x*). This approximation has received much attention mainly due to its simplicity and tractability and been shown to perform well if the system is indeed scaled as required by the underlying theory (fluid-limit of a Markov process). However, also quite intuitively, this fluid-based approach may collapse especially when we are interested in different ways of scaling the system (different ways of designing the network) for which the aforementioned fluid approximation no longer holds.

Stochastic Approach to TCP Congestion Control

Limitation of Fluid-based Approach

Buffer Sizing in TCP/AQM

Consider a link (router) with capacity NC shared by N long-lived TCP flows, such that each flow has about the same bandwidth share as N varies. The question is: how to choose the buffer size at this link and the associated AQM schemes? Traditional design guidelines are to put a buffer of size equal to the bandwidth-delay product, i.e., O(N) (proportional to N). Similarly, the traditional fluid-based congestion control analysis also supports that the buffer size as well as the scaling for AQM be at least O(N) for system stability. However, recent empirical results show that we can go with much smaller buffer of size O(sqrt{N}) without sacrificing the network performance (e.g., throughput of each user). Our research activities in this respect are to investigate the performance of the system under various types of scaling for the buffer size and the AQM (other than O(sqrt{N})) and to develop a stochastic framework to support our findings as an alternative to the fluid-based modeling.

Stochastic Convex Ordering for Internet Congestion Control

For a high bandwidth-delay product network, traditional TCP with AIMD type window update algorithms do not perform well, and many high-speed TCP variants have thus been proposed so far. These variants are mainly categorized by how they increase the window size under no packet loss. In particular, the window growth functions can be classified as of convex type (e.g., multiplicative-increase (MIMD) algorithms where the window size increases exponentially under no packet loss), a concave type (the window size initially increases very fast and then slows down), or a mixture of concave-convex (e.g., BIC or Cubic algorithms). The problem under investigation is to choose a best window growth function such that it achieves high throughput and small variations in the transmission rate, thereby leading to better user-perceived performance as well as smaller buffer size in high bandwidth-delay product networks. In this research thrust, we have noted that the traditional fluid-based modeling is not suitable for capturing rate variations of different high-speed TCP variants and instead a fully stochastic approach would serve better to capture the stochastic variations of the transmission rates of users under different TCP protocols.

Asynchronous Updates in Internet Congestion Control

The aforementioned buffer sizing problem could serve as an example of discrepancy between the fluid-based theory and real practice in that the reality performs better than what the current fluid-based modeling theory suggests. In addition to the above stochastic approach to develop better design guidelines on buffer sizing and TCP/AQM congestion control, we have looked into the possibility where we can close this gap by modifying the current popular fluid-based modeling approach. We have noted that the current fluid-based modeling does not capture the fact that different TCP flows see slightly different `snapshots' of the network, although they all see the same averaged picture of the network as a whole. We have attempted to incorporate this asynchronous nature of the Internet congestion control into the traditional simple fluid-based modeling framework, so as to re-define the stability region of the system and close the aforementioned gap between the theory and the practice.

Stochastic Approach to Peer-to-Peer Networks

Optimal Download Strategy in Peer-to-Peer Networks: For illustration, we use the problem of path selection in a peer-to-peer network. For example, consider a network with two paths whose average bandwidths are c1 = 100kbps and c2 = 150kbps, respectively. Assume that for path 1, the bandwidth is 100kbps all the time, while for path 2, the bandwidth is either 50 or 250kbps with equal probability (the average is still 150kbps). Then, to download a file of size 1 Mbits, it will take 10 seconds to complete the download for path 1, whereas for path 2, it will take on average (1M/50k + 1M/250k)/2 = 12 seconds for download! In other words, it may take longer to complete the download when we simply choose the path with the larger average bandwidth, or, the path with the maximum average capacity may not correspond to the path with the minimum average download time. In reality, the capacity fluctuation of a path (overlay) in a P2P network displays typically exhibits high degree of temporal correlations as well as spatial heterogeneity. We are currently investigating this problem and have recently developed a simple, yet very effective downloading strategy by taking into account the stochastic fluctuation of the path bandwidth directly.

Back to Top

Do Young Eun's home page