This paper introduces a new framework for re-sampling general time series data. The approach, inspired by computer agent flocking algorithms, can be used to generate inputs to complex simulation models or for generating pseudo-replications of expensive simulation outputs. The method has the flexibility to enable replicated sensitivity analysis for trace driven simulation, which is critical for risk assessment. The paper includes two simple implementations to illustrate the approach. These implementations are applied to non-stationary and state-dependent multivariate time series. Examples using emergency department data are presented.

We consider optimization of expected system performance by random search. There are two sources of random variation in this process: (i) a search induced variability because the expected performance of the system will vary randomly according to the alternatives randomly selected for examination, and (ii) a simulation induced variability, because there will be random error in estimating expected system performance from finite simulation runs. We show that, in altering the balance between these two sources of variability, three distinct forms of asymptotic behavior of the estimate of the optimal expected system performance are possible. The form of the asymptotic results shows that they may be not be easy to apply in practical work. As an alternative, a methodology for fitting a statistical model that accounts for both types of variability is suggested. This then allows the distributional properties of quantities of interest, like the optimum performance value and the best value obtained by the search, to be estimated by resampling and which also allows a test of goodness of fit of the model. Four numerical examples are given.

This paper develops fundamental theory related to the use of simulation-based non-adaptive random search as a means of optimizing a function that can be expressed as an expectation. Our results establish rates of convergence that express the trade-off between exploration and estimation, and fully characterize the limit distributions that arise. Our rates of convergence results should be viewed as a baseline against which to compare more intelligent algorithms.

We consider simulation-optimization (SO) models where the decision variables are integer ordered and the objective function is defined implicitly via a simulation oracle, which for any feasible solution can be called to compute a point estimate of the objective-function value. We develop R-SPLINE--a Retrospective-search algorithm that alternates between a continuous Search using Piecewise-Linear Interpolation and a discrete Neighborhood Enumeration, to asymptotically identify a local minimum. R-SPLINE appears to be among the first few gradient-based search algorithms tailored for solving integer-ordered local SO problems. In addition to proving the almost-sure convergence of R-SPLINE's iterates to the set of local minima, we demonstrate that the probability of R-SPLINE returning a solution outside the set of true local minima decays exponentially in a certain precise sense. R-SPLINE, with no parameter tuning, compares favorably with popular existing algorithms.

Parallel and distributed simulations (PADS) realize the distributed execution of a simulation system over multiple physical resources. To realize the execution of PADS, different simulation infrastructures such as HLA, DIS and TENA have been defined. Recently, the Distributed Simulation Engineering and Execution Process (DSEEP) that supports the mapping of the simulations on the infrastructures has been defined. An important recommended task in DSEEP is the evaluation of the performance of the simulation systems at the design phase. In general, the performance of a simulation is largely influenced by the allocation of member applications to the resources. Usually, the deployment of the applications to the resources can be done in many different ways. DSEEP does not provide a concrete approach for evaluating the deployment alternatives. Moreover, current approaches that can be used for realizing various DSEEP activities do not yet provide adequate support for this purpose. We provide a concrete approach for deriving feasible deployment alternatives based on the simulation system and the available resources. In the approach, first the simulation components and the resources are designed. The design is used to define alternative execution configurations, and based on the design and the execution configuration; a feasible deployment alternative can be algorithmically derived. Tool support is developed for the simulation design, the execution configuration definition and the automatic generation of feasible deployment alternatives. The approach has been applied within a large scale industrial case study for simulating Electronic Warfare systems.

Box intersection checking is a common task used in many large-scale simulations. Traditional methods cannot provide fast box intersection checking with large-scale datasets. This paper presents a parallel algorithm to perform Pairwise Box Intersection checking on Graphics processing units (PBIG). The PBIG algorithm consists of three phases: planning, mapping and checking. The planning phase partitions the space into small cells, the sizes of which are determined to optimize performance. The mapping phase maps the boxes into the cells. The checking phase examines the box intersections in the same cell. Several performance optimizations, including load-balancing, output data compression/encoding, and pipelined execution, are presented for the PBIG algorithm. The experimental results show that the PBIG algorithm can process large-scale datasets and outperforms three well-performing algorithms.

Consider a simulation estimator (c) based on expending c units of computer time to estimate a quantity α. In comparing competing estimators for α a natural figure of merit is to choose the estimator that minimizes the computation time needed to reduce the errorprobability P(|α(c) - α| > ε) to below some prescribed value δ In this paper, we develop large deviations results that provide approximations to the computational budget necessary to reduce the error probability to below δ when δ is small. This approximation depends critically on both the distribution of the estimator itself and that of the random amount of computer time required to generate the estimator, and leads to different conclusions regarding the choice of preferred estimator than those obtained when one requires the error tolerance to be small. The "small ε" regime leads to variance-based selection criteria, and has a long history in the simulation literature going back to Hammersley and Handscomb.

A new method for estimating Sobol' indices is proposed. The new method makes use of 3 independent input vectors rather than the usual 2. It attains much greater accuracy on problems where the target Sobol' index is small, even outperforming some oracles which adjust using the true but unknown mean of the function. The new estimator attains a better rate of convergence than the old one in a small effects limit. When the target Sobol' index is quite large, the oracles do better than the new method.

Consider a system of N identical hard spherical particles moving in a d-dimensional box and undergoing elastic, possibly multi-particle, collisions. We develop a new algorithm that recovers the pre-collision state from the post-collision state of the system, across a series of consecutive collisions, with essentially no memory overhead. The challenge in achieving reversibility for an n-particle collision (where, in general, n << N) arises from the presence of nd-d-1 degrees of freedom (arbitrary angles) during each collision, as well as from the complex geometrical constraints placed on the colliding particles. To reverse the collisions in a traditional simulation setting, all of the particular realizations of these degrees of freedom (angles) during the forward simulation must be tracked. This requires memory proportional to the number of collisions, which grows very fast with N and d, thereby severely limiting the de facto applicability of the scheme. This limitation is addressed here by first performing a pseudo-randomization of angles, which ensures determinism in the reverse path for any values of n and d. To address the more difficult problem of geometrical and dynamic constraints, a new approach is developed which correctly samples the constrained phase space. Upon combining the pseudo-randomization with correct phase space sampling, perfect reversibility of collisions is achieved, as illustrated for n <= 3, d=2, and n=2, d=3. This result enables, for the first time, reversible simulations of elastic collisions with essentially zero memory accumulation. In principle, the approach presented here could be generalized to larger values of n.

BitTorrent is one of the most successful peer-to-peer systems. Researchers have studied a number of aspects of the system, including its scalability, performance, efficiency and fairness. However, the complexity of the system has forced most prior analytical work to make a number of simplifying assumptions, e.g., user homogeneity, or even ignore some central aspects of the protocol altogether, e.g., the rate-based Tit-for-Tat (TFT) unchoking scheme, in order to keep the analysis tractable.
Motivated by this, in this paper we propose two analytical models that accurately predict the performance of the system while considering the central details of the BitTorrent protocol. Our first model is a steady-state one, in the sense that it is valid during periods of time where the number of users remains fixed. Freed by the complications of user time-dynamics, we account for many of the central details of the BitTorrent protocol and accurately predict a number of performance metrics. Our second model combines prior work on fluid models with our first model to capture the transient behavior as new users join or old users leave, while modelling many major aspects of BitTorrent. To our best knowledge, this is the first model that attempts to capture the transient behavior of many classes of heterogeneous users. Finally, we use our analytical methodology to introduce and study the performance of a flexible token-based scheme for BitTorrent, show how this scheme can be used to block freeriders and tradeoff between higher-bandwidth and lower-bandwidth users performance, and evaluate the scheme's parameters that achieve a target operational point.

The Internet has been evolving into a more heterogeneous internetwork with diverse new applications imposing more stringent bandwidth and QoS requirements. Already new applications such as YouTube, Hulu, and Netflix are consuming a large fraction of the total bandwidth. We argue that, in order to engineer future internets such that they can adequately cater to their increasingly diverse and complex set of applications while using resources efficiently, it is critical to be able to characterize the load that emerging and future applications place on the underlying network. In this paper, we investigate entropy as a metric for characterizing per-flow network traffic complexity. While previous work has analyzed aggregated network traffic, we focus on studying isolated traffic flows. Per-application flow characterization caters to the need of network control functions such as traffic scheduling and admission control at the edges of the network. Such control functions necessitate differentiating network traffic on a per-application basis. The "entropy fingerprints" that we get from our entropy estimator summarize many characteristics of each application's network traffic. Not only can we compare applications on the basis of peak entropy, but we can also categorize them based on a number of other properties of the fingerprints.

ABSTRACT

Online variants of the Expectation Maximization (EM) algorithm have recently been proposed to perform parameter inference with large data sets or data streams, in independent latent models and in hidden Markov models. Nevertheless, the convergence properties of these algorithms remain an open problem at least in the hidden Markov case. This contribution deals with a new online EM algorithm which updates the parameter at some deterministic times. Some convergence results have been derived even in general latent models such as hidden Markov models. These properties rely on the assumption that some intermediate quantities are available in closed form or can be approximated by Monte Carlo methods when the Monte Carlo error vanishes rapidly enough. In this paper, we propose an algorithm which approximates these quantities using Sequential Monte Carlo methods. The convergence of this algorithm and of an averaged version is established and their performance is illustrated through Monte Carlo experiments.

This paper deals with binomial logit models where the parameters are estimated within a Bayesian framework. Such models arise, for instance, when repeated measurements are available for identical covariate patterns. To perform MCMC sampling, we rewrite the binomial logit model as an augmented model which involves some latent variables called random utilities. It is straightforward, but inefficient, to use the individual random utility model representation based on the binary observations reconstructed from each binomial observation. Alternatively, we present in this paper a new method to aggregate the random utilities for each binomial observation. Based on this aggregated representation, we have implemented an independence Metropolis-Hastings sampler, an auxiliary mixture sampler, and a novel hybrid auxiliary mixture sampler. A comparative study on five binomial data sets shows that the new aggregation method leads to a superior sampler in terms of efficiency compared to previously published data augmentation samplers.

We consider the inverse reinforcement learning problem, that is, the problem of learning from, and then predicting or mimicking a controller based on state/action data. We propose a statistical model for such data, derived from the structure of a Markov decision process. Adopting a Bayesian approach to inference, we show how latent variables of the model can be estimated, and how predictions about actions can be made, in a unified framework. A new Markov chain Monte Carlo (MCMC) sampler is devised for simulation from the posterior distribution. This step includes a parameter expansion step, which is shown to be essential for good convergence properties of the MCMC sampler. As an illustration, the method is applied to learning a human controller.

Markov chain Monte Carlo (MCMC) methods allow to sample a distribution known up to a multiplicative constant. Most classical MCMC are known to have very poor mixing properties when sampling multimodal distributions. The Equi-Energy sampler is an interacting MCMC sampler proposed by Kou, Zhou and Wong in 2006 to sample difficult multimodal distributions. This algorithm runs several chains at different temperatures in parallel, and allow lower-tempered chains to jump to a state from a higher-tempered chain having an energy 'close' to that of the current state. A major drawback of this algorithm is that it depends on many design parameters and thus, requires a significant effort to tune the simulation parameters (the energy rings, the probability of interaction, etc..)

In this paper, we introduce an adaptive Equi-Energy (AEE) sampler, which automates the choice of the selection mecanism when jumping onto a state of the higher-temperature chain. We prove the ergodicity and a weak law of large numbers for AEE, and for the original Equi-Energy sampler as well. Finally, we apply our algorithm to motif sampling in DNA sequences.

We present a novel method for averaging a sequence of histogram states visited by a Metropolis-Hastings Markov chain whose stationary distribution is the posterior distribution over a dense space of tree-based histograms. The computational efficiency of our posterior mean histogram estimate relies on a statistical data-structure that is sufficient for non-parametric density estimation of massive, multi-dimensional metric data. This data-structure is formalized as statistical regular paving (SRP). A regular paving (RP) is a binary tree obtained by selectively bisecting boxes along their first widest side. SRP augments RP by mutably caching the recursively computable sufficient statistics of the data. The base Markov chain used to propose moves for the Metropolis-Hastings chain is a random walk that data-adaptively prunes and grows the SRP histogram tree. We use a prior distribution based on Catalan numbers and detect convergence heuristically. The performance of our posterior mean SRP histogram is empirically assessed for large sample sizes simulated from several multivariate distributions that belong to the space of SRP histograms.

Improving Importance Sampling estimators for rare event probabilities requires sharp approximations of conditional densities. This is achieved for events defined through large exceedances of the empirical mean of summands of a random walk, in the domain of large or moderate deviations. The approximation of conditional density of the trajectory of the random walk is handled on long runs. The length of those runs which is compatible with a given accuracy is discussed; simulated results are presented, which enlight the gain of the present approach over classical Importance Sampling schemes. Detailed algorithms are proposed.

We discuss a unified approach to stochastic optimization of pseudo-Boolean objective functions based on particle methods, including the cross-entropy method and simulated annealing as special cases. We point out the need for auxiliary sampling distributions, meaning parametric families on binary spaces, which are able to reproduce complex dependency structures, and illustrate their usefulness in our numerical experiments. We provide numerical evidence that particle-driven optimization algorithms based on parametric families yield superior results on strongly multi-modal optimization problems while local search heuristics outperform them on easier problems.A

This paper introduces a new specialized algorithm for equilibrium Monte Carlo sampling of binary-valued systems, which allows for large moves in the state space. This is achieved by constructing self-avoiding walks (SAWs) in the state space. As a consequence, many bits are flipped in a single MCMC step. We name the algorithm SARDONICS, an acronym for SelfAvoiding Random Dynamics on Integer Complex Systems. The algorithm has several free parameters, but we show that Bayesian optimization can be used to automatically tune them. SARDONICS performs remarkably well in a broad number of sampling tasks: toroidal ferromagnetic and frustrated Ising models, 3D Ising models, restricted Boltzmann machines and chimera graphs arising in the design of quantum computers.

Following a series of high-profile drug safety disasters in recent years, many countries are redoubling their efforts to ensure the safety of licensed medical products. Large-scale observational databases such as claims databases or electronic health record systems are attracting particular attention in this regard, but present significant methodological and computational concerns. In this paper we show how high-performance statistical computation, including graphics processing units, relatively inexpensive highly parallel computing devices, can enable complex methods in large databases. We focus on optimization and massive parallelization of cyclic coordinate descent approaches to fit a conditioned generalized linear model involving tens of millions of observations and thousands of predictors in a Bayesian context. We find orders-of-magnitude improvement in overall run-time. Coordinate descent approaches are ubiquitous in high-dimensional statistics and the algorithms we propose open up exciting new methodological possibilities with the potential to significantly improve drug safety.

In Operations Research and Management Science (OR/MS), Discrete Event Simulation (DES) models are typically created using commercial-off-the-shelf simulation packages (CSPs) such as AnyLogic^TM Arena^TM, Flexsim^TM Simul8^TM, SLX^TM, Witness^TM, etc. A DES model represents the processes associated with a system of interest. Some models may be composed of sub-models running in their own CSPs on different computers linked together over a communications network via distributed simulation software. The creation of a distributed simulation with CSPs is still complex and typically requires a partnership of problem owners, modelers, CSP vendors and distributed simulation specialists. In an attempt to simplify this development and foster discussion between modelers and technologists, the SISO-STD-006-2010 Standard for COTS Simulation Package Interoperability Reference Models has been developed. The standard makes it possible to capture interoperability capabilities and requirements at a DES modeling level rather than a computing technical level. For example, it allows requirements for entity transfer between models to be clearly specified in DES terms (e.g. the relationship between departure and arrival simulation time and input element (queue, workstation, etc.), buffering rules and entity priority) instead of using specialist technical terminology. This paper explores the motivations for distributed simulation in this area, related work, and the rationale for the standard. The four Types of Interoperability Reference Model described in the standard are discussed and presented (A: Entity Transfer, B: Shared Resource, C: Shared Event, and D: Shared Data Structure). Case studies in healthcare and manufacturing are given to demonstrate how the standard is used in practice.

We propose new methods to solve simulation optimization problems over multidimensional discrete sets. The proposed methods are based on extending the objective function from a discrete domain to a continuous domain and applying stochastic approximation to the extended function. The extension of the objective function is constructed as a piecewise linear interpolation of the original objective function over a particular partition of R^d. The advantage of the proposed approach lies in that stochastic approximation is applied to the extension, not the original function, over R^d, so the estimated optimal solution at each iteration of the proposed methods is not restricted to be an integer point. Rather, we are free to approach the optimal solution aggressively by moving toward the direction of the steepest descent, thereby skipping over intervening points and resulting in fast convergence in the early stage of the procedures.
We provide a set of such cient conditions under which the proposed methods guarantee the almost sure (a.s.) convergence to the optimal solution. One of such conditions is the multimodularity or L\ {convexity of the objective function, which arises in various inventory systems and queueing networks with controlled admission. Numerical examples illustrate the ectiveness of the proposed methods in such settings.

We present a new method for constructing nearly orthogonal Latin hypercubes that greatly expands their availability to experimenters. Latin hypercube designs have proven useful for exploring complex, high-dimensional computational models, but can be plagued with unacceptable correlations among input variables. To improve upon their effectiveness, many researchers have developed algorithms that generate orthogonal and nearly orthogonal Latin hypercubes. Unfortunately, these methodologies can have strict limitations on the feasible number of experimental runs and variables. To overcome these restrictions, we develop a mixed integer programming algorithm that generates Latin hypercubes with little or no correlation among their columns for most any determinate run-variable combination-including fully saturated designs. Moreover, many designs can be constructed for a specified number of runs and factors-thereby providing experimenters with a choice of several designs. In addition, our algorithm can be used to quickly adapt to changing experimental conditions by augmenting existing designs by adding new variables or generating new designs to accommodate a change in runs.

Distributed simulation allows the treatment of large/complex models by having several interacting simulators running concurrently, each one in charge of a portion of the model. In order to effectively manage integration and interoperability aspects, the standard known as High Level Architecture (HLA) has been developed, which is based on a middleware component known as Run-Time-Infrastructure (RTI). One of the main issues faced by such a standard is synchronization, so that HLA supports both conservative and optimistic approaches. However, technical issues, combined with some peculiarities of the optimistic approach, force most simulators to use the conservative approach. In order to tackle these issues, we present the design and implementation of a Time Management Converter (TiMaC) for HLA based simulation systems. TiMaC is a state machine designed to be transparently interposed between the application layer and the underlying RTI, which performs mapping of the conservative HLA synchronization interface onto the optimistic one. Such a mapping allows transparent optimistic execution (and the related benefits) for simulators originally designed to rely on conservative synchronization. This is achieved without the need to modify the RTI services or alter the HLA standard. An experimental evaluation demonstrating the viability and effectiveness of our proposal is also reported, by integrating our TiMaC implementation with the Georgia Tech B-RTI package and running on it both (A) benchmarks relying on traces from simulated demonstration exercises collected using the Joint Semi-Automated Forces (JSAF) simulation program and (B) a self-federated Personal Communication System simulation application.

A common problem in operations research involves comparing two system designs through simulation of both systems. The comparison can often be made more accurate through careful control (coupling) of the random numbers that are used in simulating each system, with common random numbers being the standard example. We describe a new approach for coupling the random-number inputs to two systems that involves generating realizations of a Gaussian random vector and then transforming the Gaussian random vector into the desired random-number inputs. We use nonlinear semidefinite programming to select the correlation matrix of the Gaussian random vector, with the goal of sharpening the comparison.

Assimilating real time sensor data into large-scale spatial-temporal simulations, such as simulations of wildfires, is a promising technique for improving simulation results. This asks for advanced data assimilation methods that can work with the complex structures and non-linear behaviors associated with the simulation models. This paper presents a data assimilation framework using Sequential Monte Carlo (SMC) methods for wildfire spread simulations. The models and algorithms of the framework are described, and experimental results are provided. This work demonstrates the feasibility of applying SMC methods to data assimilation of wildfire spread simulations. The developed framework can potentially be generalized to other application areas where sophisticated simulation models are used.

In this paper we explain some connections between Lyapunov methods and subsolutions of an associated Isaacs equation for the design of efficient importance sampling schemes. As we shall see, subsolutions can be derived by taking an appropriate limit of an associated Lyapunov inequality. They have been recently proposed in several works of Dupuis, Wang, and others and applied to address several important problems in rare-event simulation. Lyapunov inequalities have been used for testing the efficiency of state-dependent importance sampling schemes in heavy-tailed or discrete settings in a variety of works by Blanchet, Glynn and others. While subsolutions provide an analytic criterion for the construction of efficient samplers, Lya-punov inequalities are useful for finding more precise information, in the form of bounds, for the behavior of the coefficient of variation of the associated importance sampling estimator in the prelimit. In addition, Lyapunov inequalities provide insight into the various mollification procedures that are often required in constructing associated subsolutions. Our aim is to demonstrate that applying Lyapunov inequalities for verification of efficiency can help both, guide the selection of various mollification parameters and sharpen the information on the efficiency gain induced by the sampler.

The simulation of a discrete sample path of a Lévy process reduces to simulating from the distribution of a Lévy increment. For a general Lévy process with exponential moments, the inverse transform method proposed in Glasserman and Liu [2010] is reliable and efficient. The values of the cumulative distribution function (cdf) are computed by inverting the characteristic function and tabulated on a uniform grid. The inverse of the cumulative distribution function is obtained by linear interpolation. In this paper, we apply a Hilbert transform method for the characteristic function inversion. The Hilbert transform representation for the cdf can be discretized using a simple rule highly accurately. Most importantly, the error estimates admit explicit and computable expressions, which allow us to compute the cdf to any desired accuracy. We present an explicit bound for the estimation bias in terms of the range of the grid where probabilities are tabulated, the step size of the grid, and the approximation error for the probabilities. The bound can be computed from the characteristic function directly and allows one to determine the size and fineness of the grid and numerical parameters for evaluating the Hilbert transforms for any given bias tolerance level in one dimensional problems. For multidimensional problems, we present a procedure for selecting the grid and the numerical parameters that is shown to converge theoretically and works well practically. The inverse transform method is attractive not only for Lévy processes that are otherwise not easy to simulate, but also for processes with special structures that could be simulated in different ways. The method is very fast and accurate when combined with quasi-Monte Carlo schemes and variance reduction techniques. The main results we derived are not limited to Lévy processes and can be applied to simulating from tabulated cumulative distribution functions in general and characteristic functions in our analytic class in particular.

Established techniques for generating an instance of a multivariate nonhomogeneous Poisson process (NHPP) such as thinning can become highly inefficient as the dimensionality of the process is increased, particularly if the defining intensity (or rate) function has a pronounced peak. To overcome this inefficiency, we propose an alternative approach where one first generates a projection of the NHPP onto a lower-dimensional space, and then extends the generated points to points in the original space by generating from appropriate conditional distributions. One version of this algorithm replaces a high-dimensional problem with a series of one-dimensional problems. Several examples are presented.

For many discrete simulation-optimization applications, it is often difficult to decide which Ranking and Selection (R&S) procedure to use. To efficiently compare R&S procedures, we present a three-layer performance evaluation process. We show that the two most popular performance formulations, namely the Bayesian formulation and the indifference-zone formulation, have a common representation analogous to convex risk measures used in mathematical finance. We then specify how a decision maker can impose a performance requirement on R&S procedures that is more adequate for her risk attitude than the indifference-zone or the Bayesian performance requirements. Such a performance requirement partitions the space of R&S procedures into acceptable and non-acceptable procedures. The minimal computational budget required for a procedure to become acceptable introduces an easy-to-interpret preference order on the set of R&S policies. We demonstrate with a numerical example how the introduced framework can be used to guide the choice of selection procedure in practice.

Kriging is an increasingly popular metamodeling tool in simulation due to its flexibility in global fitting and prediction. In the fitting of this metamodel, the parameters are often estimated from the simulation data, which introduces parameter estimation uncertainties into the overall prediction error. Traditional plug-in estimators usually ignore these uncertainties, which can be substantial in stochastic simulations. This typically leads to an underestimation of the total variability and an overconfidence in the results. In this paper, a Bayesian metamodeling approach for kriging prediction is proposed for stochastic simulations to more appropriately account for the parameter uncertainties. We derive the predictive distribution under certain assumptions and also provide a general Markov Chain Monte Carlo analysis approach to handle more general assumptions on the parameters and design. Numerical results indicate that the Bayesian approach has better coverage and better predictive variance than a previously proposed modified nugget effect kriging model, especially in cases where the stochastic variability is high. In addition, we further consider the important problem of planning the experimental design. We propose a two stage design approach that systematically balances the allocation of computing resources to new design points and replication numbers in order to reduce the uncertainties and improve the accuracy of the predictions.

Ankenman et al. introduced stochastic kriging as a metamodeling tool for representing stochastic simulation response surfaces, and employed a very simple example to suggest that the use of common random numbers (CRN) degrades the capability of stochastic kriging to predict the true response surface. In this paper we undertake an in-depth analysis of the interaction between CRN and stochastic kriging by analyzing a richer collection of models and performing an empirical study. We also consider the effect of CRN on metamodel parameter estimation and response-surface gradient estimation, as well as response-surface prediction. In brief, we confirm that CRN is detrimental to prediction, but show that it leads to better estimation of slope parameters and superior gradient estimat ion compared to independent simulation.

State-dependent importance sampling algorithms based on mixtures are considered. The algorithms are designed to compute tail probabilities of a heavy-tailed random walk. The increments of the random walk are assumed to have a regularly varying distribution. Suffcient conditions for obtaining bounded relative error are presented for rather general mixture algorithms. Two new examples called, the GPD mixture and the scaling mixture, respectively, are introduced. Both examples have good asymptotic properties and in contrast to some of the existing algorithm s they are very easy to implement. Finally, it is proved that mixture algorithms of this kind can be designed to have vanishing relative error.

Low-discrepancy sequences provide a way to generate quasi-random numbers of high dimensionality with a very high level of uniformity. The nearly orthogonal Latin hypercube and the generalized Halton sequence are two popular methods when it comes to generate low-discrepancy sequences. In this paper, we propose to use evolutionary algorithms in order to find optimized solutions to the combinatorial problem of configuring generators of these sequences. Experimental results show that the optimized sequence generators behave at least as well as generators from the literature for the Halton sequence and significantly better for the nearly orthogonal Latin hypercube.

Quantiles, which are also known as values-at-risk in finance, frequently arise in practice as measures of risk. This paper develops asymptotically valid confidence intervals for quantiles estimated via simulation using variance-reduction techniques (VRTs). We establish our results within a general framework for VRTs, which we show includes importance sampling, stratified sampling, antithetic variates, and control variates. Our method for verifying asymptotic validity is to first demonstrate that a quantile estimator obtained via a VRT within our framework satisfies a Bahadur-Ghosh representation. We then exploit this to show that the quantile estimator obeys a central limit theorem (CLT) and to develop a consistent estimator for the variance constant appearing in the CLT, which enables us to construct a confidence interval. We provide explicit formulae for the estimators for each of the VRTs considered.

Due to the relevance of self-similarity analysis in several research areas, there is an increased interest in methods to generate realisations of self-similar processes, namely in the ones capable of simulating long-range dependence. This paper describes a new algorithm to approximate persistent fractional Brownian motions with a predefined Hurst parameter. The algorithm presents a computational complexity of O(n) and generates sequences with n (n ∈ N) values with a small multiple of log2 (n) variables. Because it operates in a sequential manner, the algorithm is suitable for simulations demanding real-time operation. A network traffic simulator is presented as one of its possible applications.

Given a black box that generates independent Bernoulli samples with an unknown bias p, we consider the problem of simulating a Bernoulli random variable with bias f (p) (where f is a given function) using a finite (computable in advance) number of independent Bernoulli samples from the black box. We show that this is possible if and only if f is a Bernstein polynomial with coeficients between 0 and 1, and we explicitly give the algorithm. Our results differ from Keane and O'Brien (1994) in that our goal is more modest/stringent, since we are considering algorithms that use a finite number of samples as opposed to allowing a random number (such as in acceptance rejection algorithms).

There are a number of sources of randomness that arise in military airlift operations. However, the cost of uncertainty can be difficult to estimate, and is easy to overestimate if we use simplistic decision rules. Using data from Canadian military airlift operations, we study the effect of uncertainty in customer demands as well as aircraft failures, on the overall cost. The system is first analyzed using the types of myopic decision rules widely used in the research literature. The performance of the myopic policy is then compared to the results obtained using robust decisions which account for the uncertainty of future events. These are obtained by modeling the problem as a dynamic program, and solving Bellman's equations using approximate dynamic programming. The experiments show that even approximate solutions to Bellman's equations produce decisions that reduce the cost of uncertainty.

The Global-Scale Agent Model (GSAM) is presented. The GSAM is a high performance distributed platform for agent-based epidemic modeling capable of simulating a disease outbreak in a population of several billion agents. It is unprecedented in its scale, its speed, and its use of Java. Solutions to multiple challenges inherent in distributing massive agent-based models are presented. Communication, synchronization, and memory usage are among the topics covered in detail. The memory usage discussion is Java specific. However, the communication and synchronization discussions apply broadly. We provide benchmarks illustrating the GSAM's speed and scalability.

Several algorithms for sampling exponentially tilted positive stable distributions have recently been suggested. Three of them are known as exact methods, i.e., neither do they rely on approximations nor on numerically critical procedures. One of these algorithms is outperformed by another one uniformly over all parameters. The remaining two algorithms are based on dierent ideas and both have their advantages. After a brief overview of sampling algorithms for exponentially tilted positive stable distributions, the two algorithms are compared. A rule is derived when to apply which for sampling these distributions.

Radio signal strength estimation is essential in many applications, including the design of military radio communications and industrial wireless installations. For scenarios with large or richly-featured geographical volumes, parallel processing is required to meet the memory and computation time demands. Here, we present a scalable and efficient parallel execution of the sequential model for radio signal propagation recently developed by Nutaro et al. Starting with that model, we (a) provide a vector-based reformulation that has significantly lower computational overhead for event handling, (b) develop a parallel decomposition approach that is amenable to reversibility with minimal computational overheads, (c) present a framework for transparently mapping the conservative time-stepped model into an optimistic parallel discrete event execution, (d) present a new reversible method, along with its analysis and implementation, for inverting the vector-based event model to be executed in an optimistic parallel style of execution, and (e) present performance results from implementation on Cray XT platforms. We demonstrate scalability, with the largest runs tested on up to 127,500 cores of a Cray XT5, enabling simulation of larger scenarios and with faster execution than reported before on the radio propagation model. This also represents the first successful demonstration of the ability to efficiently map a conservative time-stepped model to an optimistic discrete-event execution.

This article describes an innovative Decision Support System (DSS) for Placement of Intrusion Detection and Prevention Systems (PIDPS) in large-scale communication networks. PIDPS is intended to support network security personnel in optimizing the placement and configuration of malware filtering and monitoring devices within Network Service Providers' (NSP) infrastructure, and enterprise communication networks. PIDPS meshes innovative and state-of-the-art mechanisms borrowed from the domains of graph theory, epidemic modeling, and network simulation. Scalable network exploitation models enable to define the communication patterns induced by network users (thereby establishing a virtual overlay network), and parallel attack models enable a PIDPS user to define various interdependent network attacks such as: Internet worms, Trojans horses, Denial of Service (DoS) attacks, and others. PIDPS incorporates a set of deployment strategies (employing graph-theoretic centrality measures) in order to facilitate intelligent placement of filtering and monitoring devices; as well as a dedicated network simulator in order to evaluate the various deployments. Experiments with PIDPS indicate that incorporating knowledge on the overlay network (network exploitation patterns) into the placement and configuration of malware filtering and monitoring devices substantially improves the effectiveness of intrusion detection and prevention systems in NSP and enterprise networks.

Cell-based methods for simulating wildfires can be computationally more efficient than techniques based on the fire perimeter expansion. In spite of this, their success has been limited by the distortions that plague the simulated shapes. This paper presents a novel algorithm for wildfire simulation through Cellular Automata (CA), which is able to effectively mitigate the problem of distorted fire shapes. Such a result is obtained allowing spread directions that are not constrained to the few angles imposed by the lattice of cells and the neighborhood size. The characteristics of the proposed algorithm are empirically investigated under homogeneous conditions through some comparisons with the outcomes of a typical CA-based simulator. Also, using two significant heterogeneous landscapes, a comparison with the vector-based simulator FARSITE is discussed. According to the results of this study, the proposed approach performs significantly better, in terms of accuracy, than the CA taken as reference. In addition, at a far less computational cost, it provides burned regions which are equivalent, for practical purposes, to those given by FARSITE.

The British National Health Service (NHS) has a performance management framework that aims to guarantee short waiting times for patients by including mandatory targets for hospitals. DGHPSim is a suite of four components that simulates the activities of an NHS general hospital to show the effect of different policies on waiting times in these hospitals. DGHPSim has a generic structure that is used to simulate a particular hospital by employing data appropriate to that hospital from available data sets. Two of the components of DGHPSim, the accident and emergency simulator and the outpatient simulator, may be used independently as stand-alone simulators of these hospital functions. The DGHPSim suite incorporates a novel way of simulating the multitasking behavior of clinicians and uses transition matrices, extracted from standard datasets, to represent the states through which patients pass and the wards in which they may be treated. As a whole, the DGHPSim suite may be used to investigate improvement options before their implementation or to investigate how a hospital has improved its performance. We show how DGHPSim is used to investigate reported performance improvements in an English general hospital.

The Emergency Department (ED) of a modern hospital is a highly complex system that gives rise to numerous managerial challenges. It spans the full spectrum of operational, clinical and financial perspectives, over varying horizons: operational - few hours or days ahead; tactical - weeks or a few months ahead; and strategic - which involves planning on monthly and yearly scales. Simulation offers a natural framework within which to address these challenges, as realistic ED models are typically intractable analytically. Specifically, we apply a general and flexible ED simulator to address several significant problems that arose in a large Israeli hospital. The paper focuses mainly, but not exclusively, on workforce staffing problems over the above time horizons. First, we demonstrate that our simulation model can support real-time control, which enables short-term prediction and operational planning (physician and nurse staffing) for several hours or days ahead. To this end, we implement a novel simulationbased technique that implements the concept of offered-load and discover that it performs better than a common alternative. Then we evaluate ED staff scheduling that adjusts for midterm changes (tactical horizon, several weeks or months ahead). Finally, we analyze the design and staffing problems that arose from physical relocation of the ED (strategic yearly horizon). Application of the simulation-based approach led to the implementation of our design and staffing recommendations.

Stroke disease places a heavy burden on society, incurring long periods of hospital and community care. Also stroke is a highly complex disease with heterogeneous outcomes and multiple strategies for therapy and care. In this paper we develop a modeling framework which clusters patients with respect to their length of stay (LOS); phase-type models are then used to describe patient flows for each cluster. In most cases, there are multiple outcomes, such as discharge to normal residence, nursing home, or death. We therefore derive a novel analytical model for the distribution of LOS in such situations. A model of the whole care system is developed, based on Poisson admissions to hospital, and results obtained for expected numbers in different states of the system at any time. We can thus describe the whole integrated system of stroke patient care and facilitate planning of services. We also use the basic model to build a discrete event simulation, which incorporates back-up queues to model delayed discharge. Based on stroke patients' data from the Belfast City Hospital, various scenarios are explored with a focus on the potential efficiency gains if LOS, prior to discharge to a private nursing home, can be reduced. Predictions for bed occupancy are also provided. The overall modeling framework characterizes the behavior of stroke patient populations, with a focus on integrated system-wide planning, encompassing hospital and community services. Within this general framework we can develop either analytic or simulation models which take account of patient heterogeneity and multiple care options.

Human immunodeficiency virus (HIV) increases the risks of developing tuberculosis (TB) disease following infection, and speeds up disease progression. This has had a devastating effect on TB epidemics in sub-Saharan Africa, where incidence rates have more than trebled in the past twenty years. Current control methods for TB disease have failed to keep pace with this growth in TB, and there is an urgent need to find TB control strategies that are effective in high-HIV prevalent settings. This paper describes a discrete-event simulation model of endemic TB that includes the effects of HIV and of household structure on the transmission dynamics of TB. Incorporating a social structure allows us to compare the effectiveness of contact-tracing interventions with targeted case-finding at high risk groups. We describe the modeling of the household structure in some detail, as this has applications to the modeling of other infectious diseases.

This paper deals with the use of discrete-event simulation as a decision support tool for estimating the impact of Radio Frequency IDentifiation (RFID) technologies on processes and activities of biological sample storage areas (called biobanks). We first give a detailed description of biobank flows and identify sub-processes improved using RFID technologies. Several indicators, such as inventory reliability and human resource utilization, are compared and discussed for different scenarios involving the use of diffrent RFID technologies. A special emphasis is put on the so-called re-warehousing activity, that RFID makes possible and which consists in reassigning tubes to empty places when boxes are emptied. For this particular activity, optimization algorithms are developed and embedded in the simulator. This study shows the potential interest of RFID in biobanks and the value of simulation for estimating and optimizing its introduction in such complex socio-technical systems.

We develop four algorithms for simulation based optimization under multiple inequality constraints. Both the cost and the constraint functions are considered to be long-run averages of certain state-dependent single-stage functions. We pose the problem in the simulation optimization framework by using the Lagrange multiplier method. Two of our algorithms estimate only the gradient of the Lagrangian while the other two estimate both the gradient and the Hessian of it. In the process, we also develop various new estimators for the gradient and Hessian. All our algorithms use two simulations each. Two of these algorithms are based on the smoothed functional (SF) technique while the other two are based on the simultaneous perturbation stochastic approximation (SPSA) method. We prove the convergence of our algorithms and show numerical experiments on a setting involving an open Jackson network. The Newton-based SF algorithm is seen to show the best overall performance.

Hit-and-run, a class of MCMC samplers that converges to general multivariate distributions, is known to be unique in its ability to mix fast for uniform distributions over convex bodies. In particular, its rate of convergence to a uniform distribution is of a low order polynomial in the dimension. However, when the body of interest is divcult to sample from, typically a hyperrect- angle is introduced that encloses the original body, and a one-dimensional acceptance/rejection is performed. The fast mixing analysis of hit-and-run does not account for this one-dimensional sampling that is often needed for implementation of the algorithm. Here we show that the ect of the size of the hyperrectangle on the emulationciency of the algorithm is only a linear scaling ect. We also introduce a variation of hit-and-run that accelerates the sampler, and demonstrate its capability through a computational study.

Simulation is a low cost and safe alternative to solve complex problems in various areas. To promote reuse and interoperability of simulation applications and link geographically dispersed simulation components, distributed simulation was introduced. The High Level Architecture (HLA) is the IEEE standard for distributed simulation. To optimize communication effciency between simulation components, HLA defines a Data Distribution Management (DDM) service group for fltering out unnecessary data exchange. It relies on the computation of overlap between update and subscription regions, which is called matching. There are many existing matching algorithms, among which a sort-based approach improves effciency by sorting region bounds before the actual matching process and is found to outperform other existing matching algorithms in many situations. However, the existing algorithm performs matching for all regions in one round and cannot dynamically deal with a selective region modification without processing all the regions once again. Realizing that in many spatial applications, only a small subset of all regions are actually modified in each time step, this paper proposes a dynamic sort-based matching algorithm to deal with this effciently. Theoretical analysis has been carried out for the proposed algorithm and experimental results show that the proposed algorithm has significantly better performance than major existing matching algorithms at dynamic matching.

Queuing networks are used widely in computer simulation studies. Examples of queuing networks can be found in areas such as the supply chains, manufacturing work flow, and internet routing. If the networks are fairly small in size and complexity, it is possible to create discrete event simulations of the networks without incurring significant delays in analyzing the system. However, as the networks grow in size, such analysis can be time consuming and thus require more expensive parallel processing computers or clusters. We have constructed a set of tools that allow the analyst to simulate queuing networks in parallel using the fairly inexpensive and commonly available graphics processing units (GPUs) found in most recent computing platforms. We present an analysis of a GPU-based algorithm, describing benefits and issues with the GPU approach. The algorithm clusters events, achieving speedup at the expense of an approximation error which grows as the cluster size increases. We were able to achieve 10-x speedup using our approach with a small error in a specific implementation of a synthetic closed queuing network simulation. This error can be mitigated, based on error analysis trends, obtaining reasonably accurate output statistics. The experimental results of the mobile ad hoc network simulation show that errors occur only in the time-dependent output statistics.

The stochastic root-finding problem (SRFP) is that of finding the zero(s) of a vector function, i.e., solving a nonlinear system of equations, when the function is expressed implicitly through a stochastic simulation. SRFPs are equivalently expressed as stochastic fixed-point problems where the underlying function is expressed implicitly, via a noisy simulation. After motivating SRFPs using a few examples, we review available methods to solve such problems on constrained Euclidean spaces. We present the current literature as three broad categories, and detail the basic theoretical results that are currently known in each of the categories. With a view towards helping the practitioner, we discuss specific variations in their implementable form, and provide references to computer code when easily available. Finally, we list a few questions that are worthwhile research pursuits from the standpoint of advancing our knowledge of the theoretical underpinnings and the implementation aspects of solutions to SRFPs.

Pedestrian simulation has many applications in computer games, military simulations and anima- tion systems. A realistic pedestrian simulation requires a realistic pedestrian behavioral model that takes into account the various behavioral aspects of a real pedestrian. In this paper, we describe our work on such a model that aims to generate human-like pedestrian behaviors. To this end, various important factors in a real-pedestrian's decision-making process are considered in our model. These factors include a pedestrian's sensory, attention, memory and navigational behaviors. In particular, a two-level navigation model has been proposed to generate realistic navigational behavior. As a result, our pedestrian model is able to generate various realistic behaviors such as overtaking, waiting, side stepping and lane-forming in a crowded area. The simulated pedestrians are also able to navigate through complex environment given an abstract map of the environment.

Motivated by excessively high benchmarking efforts caused by a rapidly expanding design space, increasing system complexity, and prevailing practices based on ad-hoc and subjective schemes, this paper seeks to enhance architecture exploration and evaluation efficiency by strategically integrating a genetic algorithm, 3-D geometrical rendering, and multivariate statistical analysis into one unified methodology framework - SubsetTrio - capable of subsetting any given benchmark suite based on its inherent workload characteristics, desired workload space coverage, and total execution time intended by the user. By encoding both representativity (i.e., workload space coverage represented by the Convex Hull volume) and efficiency (i.e., total run time) as a co- optimization objective of a survival-of-the-fittest evolutionary algorithm, we can systematically determine a globally "fittest" (i.e., most representative and efficient) benchmark subset according to the workload space coverage threshold specified by the user. We demonstrate the usage, efficacy, and efficiency of the proposed technique by conducting a thorough case study on the SPEC benchmark suite, and evaluate its validity based on 50 commercial computer systems. Compared to the state-of-the-art statistical subsetting approach based on the Principal Component Analysis (PCA), SubsetTrio could select a significantly more time-efficient subset, while covering the same or higher workload space.

We develop an endcient importance sampling algorithm for estimating the tail distribution of heavy-tailed compound sums, i.e. random variables of the form SM = Z1 + :::: + ZM where the Zi's are i.i.d. random variables in R and M is a non-negative, integer-valued random variable independent of the Zi's. We construct the rst estimator that can be rigorously shown to be strongly endcient only under the assumption that the Zi's are subexponential and M is lighttailed. Our estimator is based on state-dependent importance sampling and we use Lyapunovtype inequalities to control its second moment. The performance of our estimator is empirically illustrated in various instances involving popular heavy-tailed models.

We consider the problem of the exact simulation of random variables Z that satisfy the distributional identity Z ~ VY + (1 V)Z, where V in [0, 1] and Y are independent, and ~ denotes equality in distribution. Equivalently, Z is the limit of a Markov chain driven by that map. We give an algorithm that can be automated under the condition that we have a source capable of generating independent copies of Y, and that V has a density that can be evaluated in a black box format. The method uses a doubling trick for inducing coalescence in coupling from the past. Applications include exact samplers for many Dirichlet means, some two-parameter Poisson Dirichlet means, and a host of other distributions related to occupation times of Bessel bridges that can be described by stochastic ûxed point equations.

Most popular simulation and emulation tools use high-level models of forwarding behavior in switches and routers, and give little guidance on setting model parameters such as buffer sizes. Thus, a myriad of papers report results that are highly sensitive to the forwarding model or buffer size used. Incorrect conclusions are often drawn from these results about transport or application protocol performance, service provisioning, or vulnerability to attacks. In this paper, we argue that measurement-based models for routers and other forwarding devices are necessary. We devise such a model and validate it with measurements from three types of Cisco routers and one Juniper router, under varying traffic conditions. The structure of our model is device-independent, but the model uses device-specific parameters. The compactness of the parameters and simplicity of the model make it versatile for high-fidelity simulations that preserve simulation scalability. We construct a profiler to infer the parameters within a few hours. Our results indicate that our model approximates different types of routers significantly better than the default ns-2 simulator models. The results also indicate that queue characteristics vary dramatically among the devices we measure, and that backplane contention can be a factor.

Importance splitting is a simulation technique to estimate very small entrance probabilities for Markov processes by splitting sample paths at various stages before reaching the set of interest. This can be done in many ways, yielding diㄦent variants of the method. In this context, we propose a new one, called xed number of successes. We prove unbiasedness for the new and some known variants, because in many papers, the proof is based on an incorrect argument. Further, we analyze its behavior in a simplied setting in terms of endciency and asymptotics in comparison to the standard variant. The main diㄦence is that it controls the precision of the estimator rather than the computational eろt. Our analysis and simulation examples show that it is rather robust in terms of parameter choice and we present a two stage procedure which also yields condence intervals.

The expected duration of multi-hop paths can be incorporated at diㄦent layers in the protocol stack to improve the performance of mobile ad hoc networks. This article presents two discretetime and discrete-space Markov chain based methods, DTMC-CA and DTMC-MFT, to estimate the duration of multi-hop road-based paths in vehicular ad hoc networks (VANET). The duration of such paths does not depend on individual nodes because packets can be forwarded by any vehicle located along the roads forming the path. DTMC-CA derives probabilistic measures based only on vehicle density for a trac mobility model, which in this article is the microscopic Cellular Automaton (CA) freeway trac model. DTMC-MFT generalizes the approach used by DTMC-CA to any vehicular mobility model by focusing on the macroscopic information of vehicles rather than their microscopic characteristics. The proposed analytical models produce performance-measure values comparable to simulation estimates from the validated CA trac model. Furthermore, this article demonstrates the benets of incorporating expected path durations into a VANET routing protocol. Simulation results show that the network overhead associated with route maintenance can be reduced to less than half by using the expected path durations.

The simultaneous optimization of multiple responses in a dynamic system is challenging. When a response has a known gradient, it is often easily improved along the path of steepest ascent. On the contrary, a stochastic approximation technique may be used when the gradient is unknown or costly to obtain. We consider the problem of optimizing multiple responses in which the gradient is known for only one response. We propose a hybrid approach for this problem called simultaneous perturbation stochastic approximation steepest ascent, SPSA-SA or SP(SA)2 for short. SP(SA)2 is an SPSA technique that leverages information about the known gradient to constrain the perturbations used to approximate the others. We apply SP(SA)2 to the cross-layer optimization of throughput, packet loss, and end-to-end delay in a mobile ad hoc network (MANET), a self- organizing wireless network. The results show that SP(SA)2 achieves higher throughput and lower packet loss and end-to-end delay than the steepest ascent, SPSA, and the Nelder-Mead stochastic approximation approaches. It also reduces the cost in the number of iterations to perform the optimization.

We present an analytic model and a methodology to determine the optimal packet scheduling policy in a High Speed Downlink Packet Access (HSDPA) system. The optimal policy is the one that maximizes cell throughput while maintaining a level of fairness between the users in the cell. A discrete stochastic dynamic programming model for the HSDPA downlink scheduler is presented. Value iteration is then used to solve for the optimal scheduling policy. We use a FSMC (Finite State Markov Channel) to model the HSDPA downlink channel. A near optimal heuristic scheduling policy is developed. Simulation is used to study the performance of the resulted heuristic policy and compare it to the computed optimal policy. The results show that the performance of the heuristic policy is very close to that of the optimal policy. The heuristic policy has much less computational complexity which makes it easy to deploy, with only slight reduction in performance compared to the optimal policy.

We consider the problem of throughput-optimal cross-layer design of wireless networks. We propose a joint congestion control and scheduling algorithm that achieves a fraction 1/dI (G) of the capacity region, where dI (G) depends on certain structural properties of the underlying connectivity graph G of the wireless network, and also on the type of interference constraints. For a wide Range of wireless networks, dI (G) can be upper bounded by a constant, independent of the number of nodes in the network. The scheduling element of our algorithm is the maximal scheduling policy. Although this scheduling policy has been considered in several previous works, the challenges underlying its practical implementation in a fully distributed manner while accounting for necessary message exchanges have not been addressed in the literature. In this paper, we propose two algorithms for the distributed implementation of the maximal scheduling policy accounting for message exchanges, and analytically show that they still can achieve the performance guarantee under the 1-hop and 2-hop interference models. We also evaluate the performance of our cross-layer solutions in more realistic network settings with imperfect synchronization under the signal-to-interference-plus-noise ratio (SINR) interference model, and compare with the standard layered approaches such as TCP over IEEE 802.11b DCF networks.

Cross-layer design has become one of the most e®ective and e±cient methods to provide quality of service (QoS) over various communication networks, especially over wireless multimedia net- works. However, current research on cross-layer design has been carried out in various piecemeal approaches, and lacks a methodological foundation to gain in-depth understanding of complex cross-layer behaviors such as multiscale temporal-spatial behavior, leading to a design paradox and/or unmanageable design problems. In this paper, we propose a theoretical framework for quantitative interaction measures, which is further extended to sensitivity analysis by quantifying the contribution made by each design variable and by the interactions among them on the design objective. Thus, the proposed framework can signi¯cantly enhance our capability for cross-layer behavior characterization and provide design insights for future design. Furthermore, a case study on cross-layer optimized wireless multimedia communications has been adopted to illustrate major cross-layer design tradeo®s and validate the proposed framework. Both analytical and experimen- tal results show the correctness and e®ectiveness of the proposed framework.

We propose a new framework for worst case performance evaluation of MAC protocols for wireless ad hoc networks. Given a protocol, its performance metrics and a network topology, our framework first generates MAC scenarios which achieve poor performance at MAC-level. In order to evaluate the impact of these MAC scenarios on the end performance, we model the interactions between MAC interface and the MAC layer using a state transition graph and generate high level scenarios using enumeration techniques. These high level scenarios can be simulated and compared with heuristics developed by others to identify high level scenarios that are expected to lead to the worst case end performance.

In order to demonstrate its usefulness, we use our framework to evaluate the worst case performance of IEEE 802.11 DCF protocol by generating a library of MAC and high level scenarios. We simulate the high level scenarios to demonstrate that the scenarios we generate exhibit the worst performance among all the scenarios, including those generated by using heuristics recently proposed by other researchers.

Ultra-wideband (UWB) communications has emerged as a promising technology for high data rate wireless personal area networks (WPANs). In this paper, we address two key issues that impact the performance of a multi-hop UWB-based WPAN: throughput and transmission range. Arbitrary selection of routes in such a network may result in reserving an unnecessarily long channel time, and hence low network throughput and high blocking rate for prospective reservations. To remedy this situation, we propose a novel cross-layer resource allocation design. At the core of this design is a routing technique (called RTERU) that uses the allocated channel time as a routing metric. RTERU exploits the dependence of this metric on the multiple-rate capability of an UWB system. We show that selecting the route that consumes the minimum channel time while satisfying a target packet delivery probability over the selected route is an NP-hard problem. Accordingly, RTERU resorts to approximate path selection algorithms (implemented proactively and reactively) to find near-optimal solutions at reasonable computational/communication overhead. We further enhance the performance of RTERU by integrating into its design a packet overhearing capability. Simulations are used to demonstrate the performance of our proposed solutions.

We present a numerical inversion method for generating random variates from continuous distributions when only the density function is given. The algorithm is based on polynomial interpolation of the inverse CDF and Gauss-Lobatto integration. The user can select the required precision which may be close to machine precision for smooth, bounded densities; the necessary tables have moderate size. Our computational experiments with the classical standard distributions (normal, beta, gamma, t-distributions) and with the noncentral chi-square, hyperbolic, generalized hyperbolic and stable distributions showed that our algorithm always reaches the required precision. The setup time is moderate and the marginal execution time is very fast and nearly the same for all distributions. Thus for the case that large samples with xed parameters are required the proposed algorithm is the fastest inversion method known. Speed-up factors up to 1000 are obtained when compared to inversion algorithms developed for the specic distributions. This makes our algorithm especially attractive for the simulation of copulas and for quasi-Monte Carlo applications.

Scheduling and resource management play an important role in building complex distributed systems, such as grids. In this paper we study the impact on performance of job service demand variability in a two-level grid architecture, given that the grid and local schedulers are unaware of each job’s service demand. We examine two scheduling policies at grid level, which utilize site load information and three policies at local level. A simulation model is used to evaluate performance. Results show that service demand variability degrades performance, and thus a suitable local resource allocation policy is needed to reduce its impact.

Lindley’s recursion is an explicit recursive equation that describes the recursive relationship between consecutive waiting times in a single-stage single-server queue. In this paper, we develop explicit recursive representations for multi-server tandem queues with blocking. We demonstrate the application of these recursive representations with simulations of large-scale tandem queueing networks. We compare the computational efficiency of these representations with two other popular discrete-event simulation approaches, namely, event scheduling and process interaction. Experimental results show that these representations are seven (or more) times faster than their counterparts based on the event-scheduling and process-interaction approaches.

The design, visualization, manipulation, and implementation of models for computer simulation are key parts of the discipline. Models are constructed as a means to understand physical phenomena as state changes occur over time. One issue that arises is the need to correlate models and their components with the phenomena being modeled. For example, a part of an automotive engine needs to be placed into cognitive context with the diagrammatic icon that represents that part's function. A typical solution to this problem is to display a dynamic model of the engine in one window and the engine's CAD model in another. Users are expected to, on their own, mentally blend the dynamic model and the physical phenomenon into the same context. However, this contextualization is not trivial in many applications.

Our approach expands upon this form of user interaction by specifying two ways in which dynamic models and the corresponding physical phenomena may be viewed, and experimented with, within the same human interaction space. We present a methodology and implementation of contextualization for diagram-based dynamic models using an anesthesia machine, and then follow up with a human study of its effects on spatial cognition.

An integrated Belief-Desire-Intention (BDI) modeling framework is proposed for human decision making and planning for evacuation scenarios, whose submodules are based on a Bayesian belief network (BBN), Decision- Field-Theory (DFT), and a probabilistic depth first search (PDFS) technique. A key novelty of the proposed model is its ability to represent both the human decision-making and decision-planning functions in a unified framework. To mimic realistic human behaviors, attributes of the BDI framework are reverse-engineered from human-in-the-loop experiments conducted in the Cave Automatic Virtual Environment (CAVE). The proposed modeling framework is demonstrated for a human’s evacuation behaviors in response to a terrorist bomb attack. The simulated environment and agents (models of humans) conforming to the proposed BDI framework are implemented in AnyLogic® agent-based simulation software, where each agent calls external Netica BBN software to perform its perceptual processing function and Soar software to perform its real-time planning and decision-execution functions. The constructed simulation has been used to test the impact of several factors (e.g., demographics, number of police officers, information sharing via speakers) on evacuation performance (e.g., average evacuation time, percentage of casualties).

We extend and analyze a new class of estimators for the variance parameter of a steady-state simulation output process. These estimators are based on “folded” versions of the standardized time series (STS) of the process, and are analogous to the area and Cram´er–von Mises estimators calculated from the original STS. In fact, one can apply the folding mechanism more than once to produce an entire class of estimators, all of which re-use the same underlying data stream. We show that these folded estimators share many of the same properties as their non-folded counterparts, with the added bonus that they are often nearly independent of the non-folded versions. In particular, we derive the asymptotic distributional properties of the various estimators as the run length increases, as well as their bias, variance, and mean squared error. We also study linear combinations of these estimators, and we show that such combinations yield estimators with lower variance than their constituents. Finally, we consider the consequences of batching, and we see that the batched versions of the new estimators compare favorably to benchmark estimators such as the nonoverlapping batch means estimator.

In this paper, we develop a stochastic approximation method to solve a monotone estimation prob- lem and use this method to enhance the empirical performance of the Q-learning algorithm when applied to Markov decision problems with monotone value functions. We begin by considering a monotone estimation problem where we want to estimate the expectation of a random vector η. We assume that the components of E{η} are known to be in increasing order. The stochastic approximation method that we propose is designed to exploit this information by projecting its iterates onto the set of vectors with increasing components. The novel aspect of the method is that it uses projections with respect to the max norm. We show the almost sure convergence of the stochastic approximation method. After this result, we consider the Q-learning algorithm when applied to Markov decision problems with monotone value functions. We study a variant of the Q-learning algorithm that uses projections to ensure that the value function approximation that is obtained at each iteration is also monotone. Computational results indicate that the performance of the Q-learning algorithm can be improved signi¯cantly by exploiting the monotonicity property of the value functions.

We consider the problem of finding a set of feasible or near-feasible systems among a finite number of simulated systems in the presence of constraints on secondary performance measures. We first present a generic procedure that detects the feasibility of one system in the presence of one constraint and extend it to the case of two or more systems and constraints. To accelerate the elimination of infeasible systems, a method that re-uses collected observations and its varianceupdating version are discussed. Experimental results are presented to compare the performance of the proposed procedures.

Agent-based business process simulation has grown in popularity, in part, because of its analysis capabilities. The analyses depend on the kinds of simulations that can be built, adapted, and extended, which in turn, depend on the underlying simulation framework. We report the results of our analysis of 19 agent-based process simulation tools and their simulation frameworks. We conclude that a growing number of simulation tools are using component-based software techniques. Nevertheless, most simulation tools do not directly support requirements models, their transformation into executable simulations, or the management of model variants over time. Such practices are becoming more widely applied in software engineering, under the term software product line engineering (SPLE). Based on our analysis, agent-based process simulation tools may improve their customization capacity by: (1) supporting object modeling more completely and (2) supporting software product line engineering issues.

This paper considers importance sampling as a tool for rare-event simulation. The focus is on estimating the probability of overflow in the downstream queue of a Jacksonian two-node tandem queue -- it is known that in this setting ‘traditional’ state-independent importance-sampling distributions perform poorly. We therefore concentrate on developing a state-dependent change of measure, that we prove to be asymptotically efficient.

More specific contributions are the following. (i)We concentrate on the probability of the second queue exceeding a certain predefined threshold before the system empties. Importantly, we identify an asymptotically efficient importance-sampling distribution for any initial state of the system. (ii) The choice of the importance-sampling distribution is backed up by appealing heuristics that are rooted in large-deviations theory. (iii) The method for proving asymptotic efficiency relies on probabilistic arguments only. The paper is concluded by simulation experiments that show a considerable speed up.

The field of Game Theory has proved to be of great importance in modeling interactions between self-interested parties in a variety of settings. Traditionally, game theoretic analysis relied on highly stylized models to provide interesting insights about problems at hand. The shortcoming of such models is that they often do not capture vital detail. On the other hand, many real strategic settings, such as sponsored search auctions and supply-chains, can be modeled in high resolution using simulations. Recently, a number of approaches have been introduced to perform analysis of game-theoretic scenarios via simulation-based models. The first contribution of this work is the asymptotic analysis of Nash equilibria obtained from simulation-based models. The second contribution is to derive expressions for probabilistic bounds on the quality of Nash equilibrium solutions obtained using simulation data. In this vein, we derive very general distribution-free bounds, as well as bounds which rely on the standard normality assumptions, and extend the bounds to infinite games via Lipschitz continuity. Finally, we introduce a new maximum-a-posteriori estimator of Nash equilibria based on game-theoretic simulation data and show that it is consistent and almost surely unique.

Computer networks often display nonlinear behaviour when examined over a wide range of oper- ating conditions. There are few strategies available for modelling such behaviour and optimizing such systems as they run. Prole-driven regression is developed and applied to modelling and run-time optimization of throughput in a mobile ad hoc network, a self-organizing collection of mobile wireless nodes without any xed infrastructure. The intermediate models generated in prole-driven regression are used to t an overall model of throughput, and are also used to op- timize controllable factors at run-time. Unlike others, the throughput model accounts for node speed. The resulting optimization is very ective; locally optimizing the network factors at run- time results in throughput as much as six times higher than that achieved with the factors at their default levels.

A setwise Gibbs sampler (SGS) method is developed to simulate stationary distributions and performance measures of network occupancy of Baskett-Chandy-Muntz-Palacios (BCMP) telecommunication models. It overcomes the simulation difficulty encountered in applying the standard Gibbs sampler to closed BCMP networks with constant occupancy constraints. We show Markov chains induced by SGS converge to the target stationary distributions. This paper also investigates the filtered Gibbs sampler (FGS) as an efficient method for estimating various network performance measures. It shows that FGS’s efficiency is considerable but may be improperly overestimated. A more conservative performance estimator is then presented.

When planning simulations of large-scale systems, it is important to anticipate what information is required to model the system and obtain desired output. This can be done without tying the study to a specific simulation package or language. It is valuable to do so to avoid unnecessarily long development and execution times. In this paper, we offer a simulation information model (SIM) designed to help organize system information in the early stages of a project. (It can also be used to analyze existing models.) The SIM allows complexity analysis of the system to be performed, and may lead to a better selection of simulation language. The SIM is illustrated using two examples, and its relationship to current formalisms is discussed.

To enhance efficiency in Monte Carlo simulations, we develop an adaptive stratified sampling algorithm for allocation of sampling effort within each stratum, in which an adaptive variance reduction technique is applied. Given the number of replications in each batch, our algorithm updates allocation fractions to minimize the work-normalized variance of the stratified estimator of the mean. We establish the asymptotic normality of the stratified estimator of the mean as the number of batches tends to infinity. Although implementation of the proposed algorithm requires a small amount of initial work, the algorithm has the potential to yield substantial improvements in estimator efficiency. Equally important is that the adaptive framework avoids the need for frequent recalibration of the parameters of the variance reduction methods applied within each stratum when changes occur in the experimental conditions governing system performance. To illustrate the applicability and effectiveness of our algorithm, we provide numerical results for a Black-Scholes option pricing, where we stratify the underlying Brownian motion with respect to its terminal value and apply an importance sampling method to normal random variables filling in the Brownian path. Relative to the estimator variance with proportional allocation, the proposed algorithm achieved a fourfold reduction in estimator variance with a negligible increase in computing time.

Content Distribution Networks (CDNs) have gained considerable attention in the past few years. As such, there is need for developing frameworks for carrying out CDN simulations. In this pa- per, we present a modeling and simulation framework for CDNs, called CDNsim. CDNsim has been designated to provide a realistic simulation for CDNs, simulating the surrogate servers, the TCP/IP protocol and the main CDN functions. The main advantages of this tool are its high per- formance, its extensibility and its user interface which is used to configure its parameters. CDNsim provides an automated environment for conducting experiments and extracting client, server and network statistics. The purpose of CDNsim is to be used as a testbed for CDN evaluation and experimentation. This is quite useful both for the research community (to experiment with new CDN data management techniques) and for CDN developers (to evaluate profits on prior certain CDN installations).

This article explores possibilities for designing and executing simulation models with specific analysis goals in mind, and shows that a tight coupling of the modeling and analysis phases in a simulation project can lead to dramatic improvements in the study results. Suggestions are made for how simulation analysis, considered in the explicit context of discrete-event simulation models, can create new opportunities for meaningful research and more efficient modeling. Modeling decisions can play a significant role in the performance of analytical procedures. How a simulation model is designed can enable, inhibit, or even invalidate analytical procedures and methodology research results.

Industrial Strength COMPASS (ISC) is a particular implementation of a general framework for optimizing the expected value of a performance measure of a stochastic simulation with respect to integer-ordered decision variables in a finite (but typically large) feasible region defined by linear-integer constraints. The framework consists of a global-search phase, followed by a local-search phase, and ending with a “clean-up” (selection of the best) phase. Each phase provides a probability 1 convergence guarantee as the simulation effort increases without bound: Convergence to a globally optimal solution in the global-search phase; convergence to a locally optimal solution in the local-search phase; and convergence to the best of a small number of good solutions in the clean-up phase. In practice, ISC stops short of such convergence by applying an improvement-based transition rule from the global phase to the local phase; a statistical test of convergence from the local phase to the clean-up phase; and a ranking-and-selection procedure to terminate the clean-up phase. Small-sample validity of the statistical test and ranking-and-selection procedure is proven for normally distributed data. ISC is compared to the commercial optimization via simulation package OptQuest on five test problems that range from 2 to 20 decision variables and on the order of 10⁴ to 10²⁰ feasible solutions. These test cases represent response-surface models with known properties and realistic system simulation problems.

We propose to improve the efficiency of simulation optimization by integrating the notion of optimal computing budget allocation into the Cross-Entropy (CE) method, which is a global optimization search approach that iteratively updates a parameterized distribution from which candidate solutions are generated. This article focuses on continuous optimization problems. In the stochastic simulation setting where replications are expensive but noise in the objective function estimate could mislead the search process, the allocation of simulation replications can make a significant difference in the performance of such global optimization search algorithms. A new allocation scheme is developed based on the notion of optimal computing budget allocation. The proposed approach improves the updating of the sampling distribution by carrying out this computing budget allocation in an efficient manner, by minimizing the expected mean-squared error of the CE weight function. Numerical experiments indicate that the computational efficiency of the CE method can be substantially improved if the ideas of computing budget allocation are applied.

In simulation of complex stochastic systems, such as Discrete-Event Systems (DES), statistical distributions are used to model the underlying randomness in the system. A sensitivity analysis of the simulation output with respect to parameters of the input distributions, such as the mean and the variance, is therefore of great value. The focus of this article is to provide a practical guide for robust sensitivity, respectively, gradient estimation that can be easily implemented along the simulation of a DES. We study the Measure-Valued Differentiation (MVD) approach to sensitivity estimation. Specifically, we will exploit the “modular” structure of the MVD approach, by firstly providing measure-valued derivatives for input distributions that are of importance in practice, and subsequently, by showing that if an input distribution possesses a measure-valued derivative, then so does the overall Markov kernel modeling the system transitions. This simplifies the complexity of applying MVD drastically: one only has to study the measure-valued derivative of the input distribution, a measure-valued derivative of the associated Markov kernel is then given through a simple formula in canonical form. The derivative representations of the underlying simple distributions derived in this article can be stored in a computer library. Combined with the generic MVD estimator, this yields an automated gradient estimation procedure. The challenge in automating MVD so that it can be included into a simulation package is the verification of the integrability condition to guarantee that the estimators are unbiased. The key contribution of the article is that we establish a general condition for unbiasedness which is easily checked in applications. Gradient estimators obtained by MVD are typically phantom estimators and we discuss the numerical efficiency of phantom estimators with the example of waiting times in the G/G/1 queue.

The asymptotic robustness of estimators as a function of a rarity parameter, in the context of rare-event simulation, is often qualified by properties such as bounded relative error (BRE) and logarithmic efficiency (LE), also called asymptotic optimality. However, these properties do not suffice to ensure that moments of order higher than one are well estimated. For example, they do not guarantee that the variance of the empirical variance remains under control as a function of the rarity parameter. We study generalizations of the BRE and LE properties that take care of this limitation. They are named bounded relative moment of order k (BRM-k) and logarithmic efficiency of order k (LE-k), where k ≥ 1 is an arbitrary real number. We also introduce and examine a stronger notion called vanishing relative centered moment of order k, and exhibit examples where it holds. These properties are of interest for various estimators, including the empirical mean and the empirical variance. We develop (sufficient) Lyapunov-type conditions for these properties in a setting where state-dependent importance sampling (IS) is used to estimate first-passage time probabilities. We show how these conditions can guide us in the design of good IS schemes, that enjoy convenient asymptotic robustness properties, in the context of random walks with light-tailed and heavy-tailed increments. As another illustration, we study the hierarchy between these robustness properties (and a few others) for a model of highly reliable Markovian system (HRMS) where the goal is to estimate the failure probability of the system. In this setting, for a popular class of IS schemes, we show that BRM-k and LE-k are equivalent and that these properties become strictly stronger when k increases. We also obtain a necessary and sufficient condition for BRM-k in terms of quantities that can be readily computed from the parameters of the model.