Perturbation Analysis of Discrete Event Dynamic Systems

As we sketched out in Appendices A and B, by and large there are two approaches to the performance oriented study of DEDS, namely, the analytical or the simulation-based approaches. The former has as its centerpiece the product-form formula of Jackson-Newell-Gordon and their various extensions (see Appendix A); the latter, simulation languages such as SIMSCRIPT, GPSS, SLAM, SIMAN, and their mathematical formalization, GSMP (see Appendix B). Perturbation Analysis in some sense attempts to combine the advantages of both the theoretical and the simulation approaches. PA is time-domain based. It views a queueing network as a stochastic dynamical system evolving in time and analyzes the sample realization of its state process. To this extent, it is no different from the viewpoint (and, hence, enjoys the same advantages) of the simulation approach to DEDS. However, by observing a sample path (trajectory) of the network trajectory, we use analysis to derive answers to the question: “what” will happen “if’ we repeat the sample path exactly except for a small perturbation of the timing of some event at some time t? The efficiency of our approach lies in the fact that we can answer a multitude of such ”what if“ questions simultaneously, while a single sample path is being observed. Thus, compared with the brute-force simulation study, our approach has a computational advantage of N+1: 1, where N is the number of ”what if“ questions asked (the brute-force simulation method requires one additional simulation experiment for each question asked).

The idea of aggregation is a fundamental concept in engineering. Whenever we make a model of a real system for analysis or optimization purposes, we are consciously or unconsciously making aggregation decisions as to what features to include and what details to gloss over in our model. Of course, depending on the problem, the actual aggregation methodology may be intuitive, informal, approximate, formal, precise, or exact. However, there are two universal desirable characteristics for any aggregation technique. We denote the first characteristic as External Independence. By this we mean that whatever aggregated equivalent we synthesize to represent a complex part of a system, it can only depend on the part to be aggregated and should not depend on anything external to the part. From the practical and computational viewpoint, this is a necessary requirement. The idea is that the aggregation effort is similar to a one-time set-up charge. Once carried out, the simpler equivalent model can be used over and over in analysis when other parts of the system change. Only through external independence, can one realize any practical computational saving. If each time the external part of the system changes, the aggregated equivalent, whether exact or approximate, must be re-computed, then no saving results. The second less important but still desirable aggregation property is what we shall call Closure. The idea here is that each time we aggregate a system into a simpler equivalent, the resultant system should contain no new constructs that do not present in the original system. For example, A complex queueing network is aggregated to form another simpler queueing network. Both networks contain only customers and servers. We do not require the creation of any new element. Similarly, a Markov system when aggregated should retain the Markov property. Otherwise, much of the advantage is lost. This closure property is particularly important when a hierarchical view of aggregating a complex system into many levels is adopted. We shall in this chapter judge various aggregation and PA techniques using the external independence and closure yardsticks and measure the extent to which they exactly or approximately achieve these requirements. After a review of the known results on aggregation of queueing networks in Section 1, we treat in Section 2 the relationship between aggregation and perturbation analysis. The principal idea here is that aggregation properly used actually extends the applicability of IPA. In Sections 3 and 4 we take a rather broad view of aggregation and demonstrate a new approach to the computation of the performance measures and their derivatives of very large arbitrary Markov chains.