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.Back to Top
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?