Search

We present an importance-sampling simulation method for estimating the probability of a time-bounded rare event in a Semi-Markov chain. Our method is based on generalizing the Path-ZVA method developed earlier for Markov chains, which works by first finding which paths are asymptotically dominant, and then using them to approximate the theoretical zero-variance change of measure. Our method requires only mild assumptions about the tails of the chain's sojourn time distributions. We present an empirical study that shows that our method has desirable efficiency properties in this setting.

In this talk, we consider a non-Markovian tandem queue and we use splitting in order to estimate the probability that the total number of customers in this tandem queue reaches some high level N during a busy cycle of the system. We present a splitting scheme, and we give some insights in how we prove that our splitting scheme results in an asymptotically efficient estimator for the probability of interest. Among these insights, we present the decay rate starting from some general point in the state space.

In this paper, we consider a d-node GI|GI|1 tandem queue with i.i.d. inter-arrival process and service processes that are independent of each other. Our main interest is to estimate the probability to reach a high level N in a busy cycle of the system using simulation. As crude simulation does not give a sufficient precision in reasonable time, we use importance sampling. We introduce a method to find a state-independent change of measure and we show that this is equivalent to a change of measure that was earlier, but implicitly, described by Parekh and Walrand [8]. We also show that this change of measure is the only exponential state-independent change of measure that may result in an asymptotically efficient estimator. Lastly, we provide necessary conditions for this state-independent change of measure to give an asymptotically efficient estimator.

Fault trees (FT) are a popular industrial method for reliability engineering, for which Monte Carlo simulation is an important technique to estimate common dependability metrics, such as the system reliability and availability. A severe drawback of Monte Carlo simulation is that the number of simulations required to obtain accurate estimations grows extremely large in the presence of rare events, i.e., events whose probability of occurrence is very low, which typically holds for failures in highly reliable systems. This paper presents a novel method for rare event simulation of dynamic fault trees with complex repairs that requires only a modest number of simulations, while retaining statistically justified confidence intervals. Our method exploits the importance sampling technique for rare event simulation, together with a compositional state space generation method for dynamic fault trees. We demonstrate our approach using two parameterized sets of case studies, showing that our method can handle fault trees that could not be evaluated with either existing analytical techniques, nor with standard simulation techniques.

Self-management is one of the most popular research topics in network and systems management. Little is known, however, regarding the costs, in particular with respect to performance, of self-management solutions. The goal of this paper is therefore to analyze such hidden per- formance costs. Our analysis will be performed within the context of a specific example, namely automatically moving elephant flows from the routed IP layer to optical light-paths (lambdas) in hybrid networks. The advantage of moving elephant flows to light-paths is that such flows will experience lower delays, lower jitter and lower loss, thus better Quality of Service (QoS), while reducing the load at the IP-level, which means that the remaining flows will also experience better QoS. The lower delay at the optical level may cause temporary reordering of packets, however, since the first packet over the light-path may arrive at the receiver side before the last routed IP packet has arrived. Such reordering may lead to short but severe performance problems at the TCP level. We systemat- ically analyze under which conditions such TCP performance problems occur, and how severe these problems are. Although our conclusions are specific to self-management of hybrid networks, it demonstrates by means of an example that self-management solutions may also introduce new problems, which must further be investigated before conclusions can be drawn regarding the pros and cons of self-management.

In (Parekh and Walrand, 1989) a method is introduced to efficiently estimate the probability of a rare event in a single queue or network of queues. The event they consider is that the total number of customers in the system reaches some level N in a busy cycle. Parekh and Walrand introduce a simple change of measure, which is state-independent, in order to estimate this probability efficiently using simulation. However, they do not provide any proofs of some kind of efficiency of their method. For the single queue (with multiple servers) it has been shown in (Sadowsky, 1991) that the change of measure as proposed by Parekh and Walrand is asymptotically efficient under some mild conditions.In this work we study the state-independent change of measure of the G|G|1 tandem queue, along the lines of Parekh and Walrand, and we provide necessary conditions for asymptotic efficiency. To the best of our knowledge, no results on asymptotic efficiency for the G|G|1 tandem queue had been obtained previously. Looking at the results of the M|M|1 tandem queue, it is expected that this state-independent change of measure is the only state-independent change of measure for the G|G|1 tandem queue that can possibly be asymptotically efficient. We show that, under some conditions, it is indeed the only exponential state-independent change of measure that can be asymptotically efficient. However, we have also identified conditions for the two node G|G|1 tandem queue under which the Parekh and Walrand change of measure is still not asymptotically efficient.

In this report we compare two methods to find a state-independent change of measure in the G|G|1 tandem queue and we show that they are equivalent.