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).

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.

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.