Analysis, QOS estimation, and decomposition of large networks

The Internet has undergone a tremendous increase both in network capacity and in the number of end-users. To maintain a high-level of network utilization as well as keep network congestion under check, it is imperative to understand at a fundamental level how to design and control such a large network. This problem of analyzing the network appears to be daunting within the confines of traditional stochastic and queueing techniques. However, in this thesis, we show that we can greatly simplify the network analysis by exploiting the “largeness” of the network. We first present a measurement-analytic framework in which we are able to accurately estimate the queue-length distribution (QLD) at any node where a number of flows are aggregated. We use the notion of the Dominant Time Scale (DTS) in that input statistics only up to the DTS really matter in estimating the QLD. However, since the DTS itself is defined as a global maximizer of certain statistics of the input traffic over all time, we would still have to know or estimate the statistics over all time to find the DTS. This results in a chicken-and-egg type of cycle, which appears to make the problem hopeless. We develop a stopping criterion to break this cycle and obtain a bound on the DTS. This stopping criterion enables us to efficiently estimate the QLD through on-line measurements. We next show how to decompose a network and thus simplify the end-to-end analysis. In particular, we show that the performance measure (e.g., QLD) of the original network converges to that of the simplified network, which is obtained by ignoring several nodes with large capacity from the original network, as the number of flows and capacity increases. We prove the convergence both for fluid-like traffic processes and for point process inputs. We also derive the speed of convergence for fluid-like traffic and show that it is uniform and at least exponentially fast. We then demonstrate that our decomposition approach performs especially well for the cases when (i) many flows are multiplexed as expected from the theoretical results and/or (ii) flows are routed to different nodes, i.e., no single flow dominates at any node