Performance preserving downscaling laws in computer communication networks

UnrestrictedUnderstanding and predicting the performance of today's communication networks under new algorithms, architectures and load conditions, are important and challenging research problems.; The largest and most complex network of all is the Internet. Researchers use a suite of tools and techniques in order to understand its performance: measurements, simulations, and deployments on small to medium-scale testbeds. However, because of the Internet's large size, heterogeneity and high speed of operation these techniques often impose many limitations.; To sidestep many of these limitations, in the first part of this thesis we introduce a class of methods to scaled-down the topology of the Internet that enables researchers to create and observe a smaller replica, and extrapolate its performance to the expected performance of the larger Internet.; The key insight that we leverage is that only the congested links along the path of each flow introduce sizable queueing delays and dependencies among flows. Hence, one might hope that the network properties can be captured by a topology that consists of the congested links only. We verify this using extensive simulations with TCP traffic and theoretical arguments. Further, we also show that simulating a scaled topology can be up to two orders of magnitude faster than simulating the original topology.; Another important problem, directly related to the practicability of downscaling, is whether there exist efficient and scalable ways for identifying uncongested links, in large and complex Internet-like networks. Of course, such a question is not only very important for scaling down Internet's topology, but also in many other contexts, e.g. such as in traffic engineering and capacity planning.; With this in mind, in the first part of this thesis we also present simple rules that can be used to efficiently identify uncongested Internet links. In particular, we first identify scenarios under which one can easily deduce whether a link is uncongested by inspecting the network topology. Then, we identify scenarios in which this is not possible, and propose an efficient methodology, based on the large deviations theory and flow-level statistics, to approximate the queue length distribution, and in turn, to deduce the congestion level of a link. We further demonstrate how simple commonly used metrics, such as the link utilization, can be quite misleading in classifying an Internet link.; The second part of the thesis focuses on the design of performance-preserving downscaling techniques for wireless networks. In such networks, the difficulty in managing testbeds deployed on large-scale physical areas, as well as the complexity of the wireless channel and medium access control, are the primary limiting factors for realistic analysis and performance prediction.; We first show that the full behavior of an arbitrary wireless network deployed at one spatial scale can be preserved by a suitably scaled replica consisting of the same number of nodes, but deployed at another (e.g. smaller) spatial scale, as long as the link statistics are preserved. Then, we consider wireless access networks utilizing the IEEE 802.11 standard for medium access control. We identify a set of the IEEE 802.11 protocol parameters, whose simultaneous scaling leaves the system performance virtually independent of the number of users sharing the wireless channel. This result is not only important for facilitating scalable performance prediction of currently deployed networks, but also, sets guidelines for the protocol parameters that we should aim to scale in future versions of the protocol (or in new protocols that utilize similar ideas), so that the system can support a very large number of users, while continuing to deliver to each user at least as good performance as before