Performability analysis of guarded-operation duration: a translation approach for reward model solutions

Performability measures are often defined for analyzing the worth of fault-tolerant systems whose performance is gracefully degradable. Accordingly, performability evaluation is inherently well suited for application of reward model solution techniques. On the other hand, the complexity of performability evaluation for solving engineering problems may prevent us from utilizing those techniques directly, suggesting the need for approaches that would enable us to exploit reward model solution techniques through problem transformation. In this paper, we present a performability modeling effort that analyzes the guarded-operation duration for onboard software upgrading. More specifically, we define a “performability index” Y that quantifies the extent to which the guarded operation with a duration φ reduces the expected total performance degradation. In order to solve for Y, we progressively translate its formulation until it becomes an aggregate of constituent measures conducive to efficient reward model solutions. Based on the reward-mapping-enabled intermediate model, we specify reward structures in the composite base model which is built on three stochastic activity network reward models. We describe the model-translation approach and show its feasibility for design-oriented performability modeling.     

Reward model solution methods with impulse and rate rewards: an algorithm and numerical results

Reward models have become an important method for specifying performability models for many types of systems. Many methods have been proposed for solving reward models, but no method has proven itself to be applicable over all system classes and sizes. Furthermore, specification of reward models has usually been done at the state level, which can be extremely cumbersome for realistic models. We describe a method to specify reward models as stochastic activity networks (SANs) with impulse and rate rewards, and a method by which to solve these models via uniformization. The method is an extension of one proposed by de Souza e Silva and Gail in which impulse and rate rewards are specified at the SAN level, and solved in a single model. Furthermore, we propose a new technique for discarding paths in the uniformized process whose contribution to the reward variable is minimal, which greatly reduces the time and space required for a solution. A bound is calculated on the error introduced by this discarding, and its effectiveness is illustrated through the study of the performability and availability of a degradable multi-processor system.     

Specification techniques for Markov reward models

Markov reward models (MRMs) are commonly used for the performance, dependability, and performability analysis of computer and communication systems. Many papers have addressed solution techniques for MRMs. Far less attention has been paid to the specification of MRMs and the subsequent derivation of the underlying MRM. In this paper we only briefly address the mathematical aspects of MRMs. Instead, emphasis is put on specification techniques. In an application independent way, we distinguish seven classes of specification techniques: stochastic Petri nets, queuing networks, fault trees, production rule systems, communicating processes, specialized languages, and hybrid techniques. For these seven classes, we discuss the main principles, give examples and discuss software tools that support the use of these techniques. An overview like this has not been presented in the literature before. Finally, the paper addresses the generation of the underlying MRM from the high-level specification, and indicates important future research areas. This work was supported in part by the Naval Surface Warfare Center under contract N60921-92-C-0161 and by the National Science Foundation under grant CCR-9108114.     

Component-Oriented Specification of Performance Measures

Formal notations for system performance modeling need to be equipped with suitable notations for specifying performance measures. These companion notations have been traditionally based on reward structures and, more recently, on temporal logic. In this paper we propose a mixed approach, which aims at facilitating the specification of performance measures by allowing the designer to express them in a component-oriented way. The resulting Measure Specification Language MSL, which is being integrated in Æmilia/TwoTowers, is interpreted both on action-labeled continuous-time Markov chains and on stochastic process algebras. The latter interpretation provides a compositional framework for performance-sensitive model manipulations and emphasizes the increased expressiveness with respect to traditional reward structures for modeling notations in which the concept of state is implicit.     

Performability of disk-array-based video servers

Video services are likely to dominate the traffic in future broadband networks. Most of these services will be provided by large- scale public-access video servers. Research to date has shown that disk arrays are a promising technology for providing the storage and throughput required to serve many independent video streams to a large customer population. Large disk arrays, however, are susceptible to disk failures which can greatly affect their reliability. In this paper, we discuss suitable redundancy mechanisms to increase the reliability of disk arrays and compare the performance of the RAID-3 and RAID-5 redundancy schemes. We use cost and performability analyses to rigorously compare the two schemes over a variety of conditions. Accurate cost models are developed and Markov reward models (with time-dependent reward structures) are developed and used to give insight into the tradeoffs between system cost and revenue earning potential. The paper concludes that for large-scale video servers, coarse-grained striping in a RAID-5 style of disk array is most cost effective.     

On Markov reward modelling with FSPNs

In this paper, fluid stochastic Petri nets (FSPNs) will be used for modelling reward in a performability model. Two variations of a known performability model are presented in order to demonstrate the ability of FSPNs in modelling accumulated rate reward as well as accumulated impulse reward. In the first model two fluid places are used, one of which represents the profit (reward) obtained by operating the system and the other one the buffer that is approximated continuously. In the second model only one fluid place is used, representing the costs (negative reward) arising due to repair of system components. The costs increase continuously at deterministic rate while the system is in state of repair (which is a rate reward in the model). Additional costs incur each time the buffer fails (which is an impulse reward in the model). With a numerical solution algorithm the distribution of the reward and its mean are computed. The accuracy of the numerical algorithm is studied by showing for the first model the impact of the choice of the discretization stepsizes on the obtained solution. Different boundary conditions are discussed for the second model.     

Measure-adaptive state-space construction

Measure-adaptive state-space construction is the process of exploiting symmetry in high-level model and performance measure specifications to automatically construct reduced state-space Markov models that support the evaluation of the performance measure. This paper describes a new reward variable specification technique, which combined with recently developed state-space construction techniques will allow us to build tools capable of measure-adaptive state-space construction. That is, these tools will automatically adapt the size of the state space to constraints derived from the system model and the user-specified reward variables. The work described in this paper extends previous work in two directions. First, standard reward variable definitions are extended to allow symmetry in the reward variable to be identified and exploited. Then, symmetric reward variables are further extended to include the set of path-based reward variables described in earlier work. In addition to the theory, several examples are introduced to demonstrate these new techniques.     

Behavioral-based performability modeling and evaluation of e-commerce systems

Assuring high quality of web services, especially regarding service reliability, performance and availability of e-commerce systems (unified under the term performability), has turned into an imperative of the contemporary way of doing business on the Internet. Recognizing the fact that customers’ online shopping behavior is largely affecting the conduct of e-commerce systems, the paper promotes a customer-centric, holistic approach: customers are identified as the most essential “subsystem” with a number of important, but less well-understood behavioral factors. The proposed taxonomy of customers and the specification of operational profiles is a basis to building predictive models, usable for evaluating a range of performability measures. The hierarchical composition of sub-models utilizes the semantic power of deterministic and stochastic Petri nets, in conjunction with discrete-event simulation. A handful of variables are identified in order to turn performability measures into business-oriented performance metrics, as a cornerstone for conducting relevant server sizing activities.     

Performability analysis for degradable computer systems

Degradable performance of fault-tolerant computer systems has given rise to considerable interest in mathematical models for combined evaluation of performance and reliability. Most of these models are based upon Markov processes. Several methods have been proposed for the computation of the probability distribution of performability upon an interval of time [0, t]. In this paper, we present a new algorithm based on the uniformization technique to compute this distribution for block degradable models. The main advantage of this method is its low polynomial computational complexity and its numerical stability, since it only deals with a nonincreasing sequence of positive numbers bounded by 1. This important property allows us to determine new truncation steps which improve the execution time of the algorithm. We apply this method to a degradable computer system.     

Performability analysis of computer systems: from model specification to solution

Computer systems reliability/availability modeling deals with the representation of changes in the structure of the system being modeled, which are generally due to faults, and how such changes affect the availability of the system. On the other hand, performance modeling involves representing the probabilistic nature of user demands and predicting the system capacity to perform useful work, under the assumption that the system structure remains constant. With the advent of degradable systems, the system may be restructured in response to faults and may continue to perform useful work, even though operating at lower capacity. Performability modeling considers the effect of structural changes and their impact on the overall performance of the system. The complexity of current computer systems and the variety of different problems to be analyzed, including the simultaneous evaluation of performance and availability, demonstrate the need for sophisticated tools that allow the specification of general classes of problems while incorporating powerful analytic and/or simulation techniques. Concerning model specification, a recently proposed object oriented modeling paradigm that accommodates a wide variety of applications is discussed and compared with other approaches. With respect to solution methods, a brief overview of past work on performability evaluation of Markov models is presented. Then it is shown that many performability related measures can be calculated using the uniformization or randomization technique by coloring distinguished states and/or transitions of the Markov model of the system being studied. Finally, the state space explosion problem is addressed and several techniques for dealing with the problem are discussed.     

入侵容忍系统安全属性分析

首先提出一个优化的系统状态转移模型,用以描述具有自我演进能力的入侵容忍系统的动态行为,并提高了对攻击行为的描述能力,以该模型为基础,建立SMP模型并对系统安全属性及可执行性进行定量分析,进而计算出系统平均安全故障时间（MTTSF）;最后给出数值分析结果,并通过计算模型中时间参数的敏感度,得出入侵容忍技术研究的关键点．     

A generalized formulation for the performability indicator

The main objective of this paper is to propose a generalized form of the performability measure, which has been initially defined for the purpose of studying the performance and reliability analysis of fault tolerant systems. This generalized form takes into account more detailed rewards and can be used in general for maintenance cost analysis as well as in the modeling of the website users behavior. We give different formulations by means of a homogeneous Markov chain and a cyclic nonhomogeneous Markov chain and their asymptotic expression.     

A hybrid approach to minimize state space explosion problem for the solution of two stage tandem queues

Two stage open queuing networks are used for modeling the subsystem-behaviour in computers and communication networks, mass storage devices, memory servers, and queuing analysis of wireless mobile cellular networks. The queuing analysis of wireless systems is essential in order to quantify the impact of different factors on quality of service (QoS); performance measures so that wireless protocols can be designed and/or tuned in an optimal manner. In that sense two stage open queuing systems are particularly important to model handoff phenomena, especially for the integration of two different systems such as cellular and wireless local area networks (WLANs). Analytical solutions for two-dimensional Markov processes suffer from the state space explosion problem. The numerical difficulties caused by large state spaces, make it difficult to handle multiple servers at the second stage of a tandem queuing system together with server failures and repairs. This study presents a new approach to analytical modeling of open networks offering improvements in alleviating this problem. The proposed solution is a hybrid version, which combines well known spectral expansion, and hierarchical Markov reward rate approaches. Using this approach, two-stage open networks with multiple servers, break-downs, and repairs at the second stage and feedback can be modeled as three-dimensional Markov processes and solved for performability measures. Comparative results show that the new algorithm used for solution, provides a high degree of accuracy, and it is computationally more efficient than the existing approaches. The proposed model is capable of solving other three-dimensional Markov processes.     

Backward Bisimulation in Markov Chain Model Checking

Equivalence relations can be used to reduce the state space of a system model, thereby permitting more efficient analysis. We study backward stochastic bisimulation in the context of model checking continuous-time Markov chains against continuous stochastic logic (CSL) properties. While there are simple CSL properties that are not preserved when reducing the state space of a continuous-time Markov chain using backward stochastic bisimulation, we show that the equivalence can nevertheless be used in the verification of a practically significant class of CSL properties. We consider an extension of these results to Markov reward models and continuous stochastic reward logic. Furthermore, we identify the logical properties for which the requirement on the equality of state-labeling sets (normally imposed on state equivalences in a model-checking context) can be omitted from the definition of the equivalence, resulting in a better state-space reduction     

Convergence of concurrent Markov chain Monte-Carlo algorithms

We examine the parallel execution of a class of stochastic algorithms called Markov chain Monte-Carlo (MCMC) algorithms. We focus on MCMC algorithms in the context of image processing, using Markov random field models. Our parallelisation approach is based on several, concurrently running, instances of the same stochastic algorithm that deal with the whole data set. Firstly we show that the speed-up of the parallel algorithm is limited because of the statistical properties of the MCMC algorithm. We examine coupled MCMC as a remedy for this problem. Secondly, we exploit the parallel execution to monitor the convergence of the stochastic algorithms in a statistically reliable manner. This new convergence measure for MCMC algorithms performs well, and is an improvement on known convergence measures. We also link our findings with recent work in the statistical theory of MCMC.     

State-space support for path-based reward variables

Many sophisticated formalisms exist for specifying complex system behaviors, but methods for specifying performance and dependability variables have remained quite primitive. To cope with this problem, modelers often must augment system models with extra state information and event types to support particular variables. This often leads to models that are non-intuitive, and must be changed to support different variables. To address this problem, we extend the array of performance measures that may be derived from a given system model, by developing new performance measure specification and model construction techniques. Specifically, we introduce a class of path-based reward variables, and show how various performance measures may be specified using these variables. Path-based reward variables extend the previous work with reward structures to allow rewards to be accumulated based on sequences of states and transitions. To maintain the relevant history, we introduce the concept of a path automaton, whose state transitions are based on the system model state and transitions. Furthermore, we present a new procedure for constructing state spaces and the associated transition rate matrices that support path-based reward variables. Our new procedure takes advantage of the path automaton to allow a single system model to be used as the basis of multiple performance measures that would otherwise require separate models or a single more complicated model.     

Composing, analyzing and validating software models to assess the performability of competing design candidates

In a perfect world, verification and validation of a software design specification would be possible before any code was generated. Indeed, in a perfect world we would know that the implementation was correct because we could trust the class libraries, the development tools, verification tools and simulations, etc. These features would provide the confidence needed to know that all aspects (complexity, logical and timing correctness) of the design were fully satisfied (i.e., everything was right). Right in the sense that we built it right (it is correct with respect to its specification) and it solves the right problem. Unfortunately, it is not a perfect world, and therefore we must strive to continue to refine, develop and validate useful methods and tools for the creation of safe and correct software. This paper considers the analysis of systems expressed using formal notations. We introduce our framework, the modeling cycle, and motivate the need for tool supported rigorous methods. Our framework is about using systematic formal techniques for the creation and composition of software models that can further enable reasoning about high‐assurance systems. We describe several formal modeling techniques within this context (i.e., reliability and availability models, performance and functional models, performability models, etc.). This discussion includes a more precise discourse on stochastic methods (i.e., DTMC and CTMC) and their formulation. In addition, we briefly review the underlying theories and assumptions that are used to solve these models for the measure of interest (i.e., simulation, numerical and analytical techniques). Finally, we present a simple example that employs generalized stochastic Petri nets and illustrates the usefulness of such analysis methods. This revised version was published online in June 2006 with corrections to the Cover Date.     

Semi-Markov adaptive critic heuristics with application to airline revenue management

The adaptive critic heuristic has been a popular algorithm in reinforcement learning(RL) and approximate dynamic programming(ADP) alike.It is one of the first RL and ADP algorithms.RL and ADP algorithms are particularly useful for solving Markov decision processes(MDPs) that suffer from the curses of dimensionality and modeling.Many real-world problems,however,tend to be semi-Markov decision processes(SMDPs) in which the time spent in each transition of the underlying Markov chains is itself a random variable.Unfortunately for the average reward case,unlike the discounted reward case,the MDP does not have an easy extension to the SMDP.Examples of SMDPs can be found in the area of supply chain management,maintenance management,and airline revenue management.In this paper,we propose an adaptive critic heuristic for the SMDP under the long-run average reward criterion.We present the convergence analysis of the algorithm which shows that under certain mild conditions,which can be ensured within a simulator,the algorithm converges to an optimal solution with probability 1.We test the algorithm extensively on a problem of airline revenue management in which the manager has to set prices for airline tickets over the booking horizon.The problem has a large scale,suffering from the curse of dimensionality,and hence it is difficult to solve it via classical methods of dynamic programming.Our numerical results are encouraging and show that the algorithm outperforms an existing heuristic used widely in the airline industry.     

Improving probabilistic inference in graphical models with determinism and cycles

Many important real-world applications of machine learning, statistical physics, constraint programming and information theory can be formulated using graphical models that involve determinism and cycles. Accurate and efficient inference and training of such graphical models remains a key challenge. Markov logic networks (MLNs) have recently emerged as a popular framework for expressing a number of problems which exhibit these properties. While loopy belief propagation (LBP) can be an effective solution in some cases; unfortunately, when both determinism and cycles are present, LBP frequently fails to converge or converges to inaccurate results. As such, sampling based algorithms have been found to be more effective and are more popular for general inference tasks in MLNs. In this paper, we introduce Generalized arc-consistency Expectation Maximization Message-Passing (GEM-MP), a novel message-passing approach to inference in an extended factor graph that combines constraint programming techniques with variational methods. We focus our experiments on Markov logic and Ising models but the method is applicable to graphical models in general. In contrast to LBP, GEM-MP formulates the message-passing structure as steps of variational expectation maximization. Moreover, in the algorithm we leverage the local structures in the factor graph by using generalized arc consistency when performing a variational mean-field approximation. Thus each such update increases a lower bound on the model evidence. Our experiments on Ising grids, entity resolution and link prediction problems demonstrate the accuracy and convergence of GEM-MP over existing state-of-the-art inference algorithms such as MC-SAT, LBP, and Gibbs sampling, as well as convergent message passing algorithms such as the concave–convex procedure, residual BP, and the L2-convex method.