Aggregation, Decomposition, and Equivalence

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.