Skip to main content
Prof Do Young Eun

Network Decomposition

Do Young Eun (Dept. of ECE, North Carolina State University) 
Ness B. Shroff (Dept. of ECE, Purdue University) 

Publications:

Theory

  • Do Young Eun and Ness B. Shroff,  “Network Decomposition in the Many-Sources Regime”, Advances in Applied Probability, Sept. 2004, To appear.
  • Do Young Eun and Ness B. Shroff,  “Analyzing a two-stage queueing system with many Point Process arrivals at upstream queue”, submitted to Queueing Systems, accepted for publication, 2004. 

Engineering Implications

  • Do Young Eun and Ness B. Shroff,  “Network Decomposition: Theory and Practice”, submitted to IEEE/ACM Transactions on Networking, Jan. 2003 (accpeted for publication) [full paper available upon request]
  • Do Young Eun and Ness B. Shroff, “Simplification of Network Analysis in Large-Bandwidth Systems”, in Proceedings of IEEE INFOCOM, April 2003

Research Summary

The Internet has undergone a tremendous increase both in network capacity and in the number of end-users, and this trend is expected to continue for the next several years. Further, these end-users are becoming increasingly sophisticated and demand high-bandwidth, low-delay 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 product-form 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 measurement-analytic techniques provide a framework for estimating the queue-length 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 core-routers where hundreds to thousands of flows are served may not allow adding a measurement-unit 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 two-stage 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 fluid-like traffic processes and for point process inputs. In particular, we derived the speed of convergence for fluid-like 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 end-to-end delay distribution of flows of our interest. These results can then be iteratively applied from a two-stage system to a multi-stage 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.

Current and Future Work

Network Decomposition for Closed-Loop Systems:

Since TCP prevails in the current Internet and also will do in the future, understanding the performance of a large closed-loop network is of utmost importance. However, due to the feedback, the analysis of the end-user’s QoS such as the end-to-end delay or the QLD at router buffers is extremely difficult. Moreover, in reality, a number of TCP flows and real-time 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 closed-loop 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 long-range dependent) traffic process. This is intuitively obvious (really?), but could be tremendously difficult when you go into the technical details for proof. 

Some Related Papers (in arbitrary order):