Network Decomposition: Theory and Practice
Abstract
In this paper we show that significant simplicities can arise in the
analysis of a network when link capacities are large enough to carry
many flows. We develop a network decomposition approach in which
network analysis can be greatly simplified.
We prove that the queuelength 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 at the upstream queue increase.
The precise modes of convergence vary depending on the type of input traffic,
i.e., from regulated traffic arrivals to point process inputs.
Our results thus help simplify network analysis by decomposing
the original network into a simplified network in which all the nodes
with large capacity have been eliminated.
Through an extensive numerical investigation under various network
scenarios, we demonstrate different aspects and implications of our network
decomposition approach. Some of our findings are that our techniques perform
well especially for the cases when (i) many flows are multiplexed and/or
(ii) flows are routed to different nodes, i.e., no single flow dominates
at any node.
