Network Decomposition
Do Young Eun
(Dept. of ECE, North Carolina State University)
Ness B. Shroff
(Dept. of ECE, Purdue University)
Publications:
Theory
Engineering Implications
Research Summary
The Internet has undergone a tremendous increase both in network
capacity and in the number of endusers, and this trend is
expected to continue for the next several years. Further,
these endusers are becoming increasingly sophisticated and demand
highbandwidth, lowdelay network services at affordable prices.
The conflicting requirements of maintaining a high level of
network utilization (for affordable prices or high revenue), while
at the same time keeping network congestion under check
(for ensuring a good level of quality of service), make it imperative
to understand at a fundamental level how to design and control the
next generation of networks.
The issues mentioned above appear to be daunting within the
confines of traditional stochastic and queueing techniques.
Indeed, except in special cases such as Markovian queueing
networks, for which productform solutions are available,
the problem of analyzing queueing networks has been notoriously
difficult. The reason is that traffic flows lose their original
statistical characteristics as they traverse through the network,
due to the interaction among other flows at various nodes in the
network. However, we have found that the fact that a large number of
traffic flows will be supported on the network can actually be
exploited to help obtain results for predicting performance
and allocating network resources.
Although our
measurementanalytic techniques provide a framework for estimating
the queuelength distribution (QLD) as long as we can measure the
traffic at the node in hand, direct measurements at the interior
nodes often could be costly or even practically infeasible.
For example, the corerouters where hundreds to thousands of
flows are served may not allow adding a measurementunit
possibly because of its enormous speed, heterogeneity, or scalability
issues. Motivated by these observations, we set out to see if we
could decompose a queueing network into a single queue,
where a lot of flows are aggregated inside the network.
Such a decomposition result would also have interesting implications
for network design. A typical scenario in our mind was to
analyze a queue, which is located deep inside a network or
at egress routers so that the traffic flows feeding that
queue are essentially unreachable and statistically different
from their exogenous counterparts (original traffic arrivals
to the network). We first considered a twostage queueing
network where the upstream queue serves many flows, of which a
fixed subset of flows feed the downstream queue while the rest
of them depart the system. We then showed that the QLD at the
downstream queue converges to that of a single queue obtained
by removing the upstream queue, as the capacity and the number
of flows being served at the upstream queue increase.
We have rigorously proven the convergence both for fluidlike
traffic processes and for point process inputs. In particular,
we derived the speed of convergence for fluidlike traffic and
showed that it is uniform (over buffer levels) and
at least exponentially fast.
Our extensive simulation results also confirmed that
removing nodes serving many flows does not incur any sizable error
in estimating the QLD at the downstream nodes or the endtoend
delay distribution of flows of our interest. These results can
then be iteratively applied from a twostage system to a
multistage network. We also demonstrated that our decomposition
approach performs especially well for the cases when (i)
many flows are multiplexed as expected from our theoretical
results and/or (ii) flows are routed to different nodes, i.e.,
no single flow dominates at any node, as expected in current and
future networks.
Back to Top
Current and Future Work
Network Decomposition for ClosedLoop Systems:
Since TCP prevails in the current Internet and also will do
in the future, understanding the performance of a large closedloop
network is of utmost importance. However, due to the feedback,
the analysis of the enduser's QoS such as the endtoend delay or
the QLD at router buffers is extremely difficult. Moreover, in
reality, a number of TCP flows and realtime traffic flows may
coexist at router buffers. In the literature, most work on analyzing
TCP have been devoted to the stability analysis of the system.
For closedloop systems, it is unclear whether it is
possible to develop any simplifying technique similar to our
decomposition approach.
How do we simplify the network? What are the AQM schemes?
How do we scale the system?
Network Decomposition for Dynamic Systems:
We expecet that similar results will go through for a system with
dynamic flow arrivals and departures. An immediate candidate
for modeling the flow arrivals and departures is to use the M/G/\infty
model for flow dynamics, while each flow is still modeled as a general
(possibly longrange dependent) traffic process.
This is intuitively obvious (really?), but could be tremendously
difficult when you go into the technical details for proof.
Back to Top
Some Related Papers (in arbitrary order):

Xiaojun Lin and Ness B. Shroff,
``Simplification of Network Dynamics in Large Systems," in
Tenth International Workshop on Quality of Service(IWQoS 2002), Miami
Beach, Florida, May 2002
[ps] .
An extended version is
submitted to IEEE/ACM Transactions on Networking
[ps] .

D.D. Botvich, and N.G. Duffield,
"Large deviations, economies of scale, and the shape of the loss curve
in large multiplexers," Queueing Systems, 20, 293320 (1995).

C. Courcoubetis, R. Weber.
"Buffer Overflow Asymptotics for a Buffer Handling many Traffic Sources,"
Journal of Applied Probability, vol. 33, 1996.
 F. P. Kelly,
Notes on
effective bandwidths .
In "Stochastic Networks: Theory and Applications" (Editors F.P. Kelly, S.
Zachary and I.B. Ziedins)
Royal Statistical Society Lecture Notes Series, 4.
Oxford University Press, 1996. 141168.
 Damon Wischik,
"The output of a switch, or, effective bandwidths for networks"
Queueing Systems. Volume 32, pages 383396, 1999.
 Peerapol Tinnakornsrisuphap, and Armand M.
Makowski. "Limit Behavior of ECN/RED Gateways Under a Large
Number of TCP Flows", In Proceedings of
IEEE INFOCOM 2003,
San Francisco, CA, April 2003.
[ full paper 279K (PDF)] [slides (powerpoint 600K)]

Hong, D. and Lebedev, D. (2001)
"Many TCP User Asymptotic Analysis of the AIMD Model"
Technical Report, July 2001,
RR4229 (.pdf).
 J. Cao and Kavita Ramanan,
"A Poisson Limit for the Unfinished Work of Superposed Point Processes"
Bell Labs Tech. Report, 2001.
 Ozturk, O., Mazumdar, R. and Likhanov, N.;
"Many sources asymptotics for a feedforward network with small buffers,"
Proceedings of the Allerton Conference 2002, Montecello, Ill. , Oct. 2002

Iaonnis (Yannis) Ch. Paschalidis and Y. Liu,
``Pricing in Multiservice Loss Networks: Static Pricing, Asymptotic
Optimality, and Demand Substitution Effects''
IEEE/ACM Transactions on Networking,
Vol. 10 (2002), No. 3, pages 425438.
Abstract: [PS]
[PDF]
Paper (Revised 8/6/02): [PS] [PDF]
Paper Companion: [PS] [PDF]
Back to Top
Do Young Eun's home page