Stochastic Approach to the Design of Communication Networks: An Alternative to
Fluid Modeling
Sponsored by National Science Foundation through CAREER Award
CNS0545893
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,
optimizationbased techniques, and peertopeer networks. This fluid modeling
(or often called the meanfield 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 peertopeer 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 fluidbased 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
additiveincreasemultiplicativedecrease (AIMD) algorithm in TCP corresponds to
f(x,u)=
(x+1)(11{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 (fluidlimit of a Markov
process). However, also quite intuitively, this fluidbased 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 Fluidbased Approach

Do Young Eun, "On the Limitation of Fluidbased Approach for Internet Congestion
Control," IEEE International Conference on Computer Communications and Networks (ICCCN),
San Diego, CA, Oct. 2005 (Best Paper Award)
[talk slides]

Do
Young Eun, "On the Limitation of Fluidbased Approach for Internet Congestion
Control", Telecommunication Systems, Vol. 34, No. 12, pages 311,
Feb. 2007 (Invited as the best paper from IEEE ICCCN 2005)
Buffer Sizing in TCP/AQM
Consider a link (router) with capacity NC shared by N
longlived 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 bandwidthdelay product, i.e., O(N) (proportional to
N). Similarly, the traditional fluidbased 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
fluidbased modeling.
 Do Young Eun and
Xinbing Wang, "Achieving 100% Throughput in TCP/AQM under Aggressive Packet
Marking with Small Buffer," to appear in IEEE/ACM Transactions on Networking

Do Young Eun and Xinbing
Wang, "Performance Analysis of TCP/AQM with Generalized AIMD under Intermediate
Buffer Sizes", to appear in Computer Networks
 Do Young Eun and
Xinbing Wang, "Performance Modeling of TCP/AQM with Generalized AIMD under
Intermediate Buffer Sizes," in proceedings of IEEE International
Performance Computing and Communications Conference (IPCCC), Phoenix,
AZ, April 2006. (Best Paper Award)
[technical report with proofs]
 Do Young Eun and
Xinbing Wang, "A DoublyStochastic Model for a TCP/AQM System under Aggressive
Packet Marking," in proceedings of Conference on Information Science and
Systems (CISS), Princeton, NJ, March 2006
[talk slides]
 Do Young Eun and Xinbing Wang, "Stationary Behavior of TCP/AQM with Many Flows
Under Aggressive Packet Marking," in Proceedings of IEEE ICC 2005, May 2005
Stochastic Convex Ordering for Internet Congestion Control
For a high bandwidthdelay product network, traditional TCP with AIMD type
window update algorithms do not perform well, and many highspeed 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.,
multiplicativeincrease (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 concaveconvex (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 userperceived
performance as well as smaller buffer size in high bandwidthdelay product
networks. In this research thrust, we have noted that the traditional
fluidbased modeling is not suitable for capturing rate variations of different
highspeed 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.
 Han Cai,
Do Young Eun, Sangtae Ha, Injong Rhee, Lisong Xu, "Stochastic Convex Ordering for
Internet Congestion Control,"
submitted to IEEE/ACM Transactions on Networking
 Han Cai,
Do Young Eun, Sangtae Ha, Injong Rhee, Lisong Xu, "Stochastic Ordering for
Internet Congestion Control and its Applications," in Proceedings of
IEEE
INFOCOM, Anchorage, AK, May 2007
Asynchronous Updates in Internet Congestion Control
The aforementioned buffer sizing problem could serve as an example of
discrepancy between the fluidbased theory and real practice in that the reality
performs better than what the current fluidbased 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
fluidbased modeling approach. We have noted that the current fluidbased
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 fluidbased modeling framework, so as to redefine the stability region
of the
system and close the aforementioned gap between the theory and the practice.
Stochastic Approach to PeertoPeer
Networks
Optimal Download Strategy in PeertoPeer Networks: For illustration, we
use the problem of path selection in a peertopeer 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.
 YuhMing Chiu and Do
Young Eun, "Minimizing File Download Time in Stochastic PeertoPeer Networks,"
to appear in IEEE/ACM Transactions on Networking
 YuhMing Chiu and Do
Young Eun, "On the Performance of Download Strategies in a P2P Like Network",
to appear in IEEE GLOBECOM,
Washington DC, Nov. 2007
 YuhMing Chiu and Do
Young Eun, "Minimizing File Download Time over Stochastic Channels in
PeertoPeer Networks," in proceedings of Conference on Information Science
and Systems (CISS), Princeton, NJ, March 2006
Back to Top
Do Young Eun's home page