On the Design of Efficient Simulations for Complex Queueing Networks

Abstract

Traditional network models have played an important role over the last four decades in providing insight in the dynamics of telecommunication, computer and manufacturing systems. At the core of various modern technologies such as database management systems, high-speed packet switching architectures, online computing, web server architectures, etc, one finds the fundamental features of Parallel and Distributed Processing systems. Such systems due to the interaction and sharing of available resources exhibit highly complex dynamics. When studying complex networks, we need to understand the behavior of the following performance measures: (i) throughput and (ii) backlogs, delays, as well as other general cost/revenues associated with their operation. Over the years a fairly rich literature has been developed for determining the throughput capacity of complex systems, as well as constructing control protocols that achieve maximum throughput under different stochastic assumptions on the input and service processes; for example, drift analysis, fluid models, sample path analysis. For backlogs and delays there are considerably fewer results using stochastic comparisons, coupling arguments, large deviation principles, but also requiring strong structural assumptions of the system. Therefore, an important tool for understanding the complex dynamics of complex control policies becomes "simulation". Simulation can provide insight to the behavior of a complex system by identifying the response surface of several performance measures, such as backlogs and delays. However, simulations of large systems are expensive both in terms of CPU time and of time required to write the usually custom-made computer code. It becomes apparent that it is of paramount importance to carefully select the inputs of the simulation runs in order to (i) adequately capture the underlying response surface of interest and (ii) minimize the required number of simulation runs. In this study, we present a methodological framework for designing efficient simulations for complex networks. We also demonstrate our methodology with a few examples.