Container technology, as the key enabler behind microservice architectures, is widely applied in Cloud and Edge Computing. A long and continuous running of operating system (OS) hosting container-based services can encounter software aging that leads to performance deterioration and even causes system failures. OS rejuvenation techniques can mitigate the impact of software aging but the rejuvenation trigger interval needs to be carefully determined to reduce the downtime cost due to rejuvenation. This paper proposes a comprehensive semi-Markov-based approach to quantitatively evaluate the effect of OS rejuvenation on the dependability and the performance of a container-based service. In contrast to the existing studies, we neither restrict the distributions of time intervals of events to be exponential nor assume that backup resources are always available. Through the numerical study, we show the optimal container-migration trigger intervals that can maximize the dependability or minimize the performance of a container-based service.

Given heavy dependence on man-made systems in our daily lives, reliability and availability of these systems clearly gain great importance. Together with methods of enhancing reliability and availability of systems, methods of quantitative assessment of these attributes thus needs attention. Quantification of these attributes via analytic-numeric solution of a probability model based on a deep understanding of system's failure/repair dynamics is briefly discussed in this article.

Traditional software fault tolerance makes use of design-diversity-based redundancy. While proven to be effective, the independent development of multiple versions of a program or component is connected with high costs. This article shows that failures caused by so-called Mandelbugs (i.e., software faults whose activation and/or error propagation depends on the system environment) can often be treated by generating or forcing a new or modified execution environment. In the case of aging-related bugs, a subtype of Mandelbugs, failures can be postponed/prevented via a proactive technique known as software rejuvenation. Indeed, techniques based on environmental diversity, such as retry, reboot, or failover to an identical replica, are successfully used in practice. We discuss two such real-case examples, the IBM Session Initiation Protocol (SIP) Application Server cluster and Avaya gateway servers.

This paper aims to use analytical modeling technique to quantitatively study the dependability of Vehicle Platooning Application, which consists of Multiple Sub-Services (VPP-MSS) to achieve its functionality. Each sub-service (SS), based on network function virtualization technology, is executed in a container. Both SSes and OSes which SSes run on can suffer from software aging after a long and continuous running, reducing VPP-MSS dependability. Rejuvenation techniques are usually used to combat software aging, but they require the support of backup components. Quantitative study of VPP-MSS dependability enables in-depth understanding of the effectiveness of rejuvenation techniques based on analytical models. In contrast to the existing studies, we develop a semi-Markov process (SMP) model to jointly analyze the impact of rejuvenation technique trigger intervals (RTTIs), backup components’ behaviors, time-dependent interactions between various behaviors and the number of active SSes deployed on an OS on the effectiveness of rejuvenation technique. Sensitivity analysis helps identify key parameters for improving the dependability of VPP-MSS. Extensive numerical experiments demonstrate the necessity of considering backup components’ behaviors and investigating non-exponentially distributed failure times. We also determine both the optimal RTTI combination and the optimal combination of SSes and OSes, which can maximize VPP-MSS dependability.

The Multi-access Edge Computing (MEC) and Network Function Virtualization (NFV) integrated architecture is a key enabling platform for 5G to run multiple customized services in the form of service function chain (SFC) configured as an ordered set of service functions (SFs). However, memory-related software aging in the SF that can be exploited by attackers becomes a new threat to the dependability of MEC-SFC services. To provide dependable MEC-SFC services, proactive rejuvenation techniques to counteract the SF aging problem are essential. In this paper, we develop a semi-Markov model to quantitatively investigate the transient availability and steady-state dependability (availability and reliability) of MEC-SFC services. Our model enables the analysis of a MEC-SFC with any number of SFs, and can capture complex time-dependent behaviors of aging, failure, and recovery. The approximate accuracies of the presented model on dependability measures are comprehensively evaluated through comparative studies with simulation experiments. We then detect potential bottlenecks for a MEC-SFC system through sensitivity analysis and further analyze the impact of event-time interval distributions on steady-state dependability. Finally, we investigate the transient behaviors of a MEC-SFC service when varying system parameters during MEC-SFC operation.

As software plays an increasingly important role in our lives, it is essential to maintain its reliability, and generally dependability. Software bugs can cause huge financial losses and dangerous accidents; the safety risks from software are underscored these days to even the non-technical public by the emergence of autonomous software-based systems. Thus, it is important to explore principled approaches to reduce the harm from defects in software, preferably by removing them as early as possible, but also by fault tolerance and by predicting their effects so as to inform mitigation actions.

Multi-accessedgecomputing (MEC)-enabledInternetofThings (IoT) is considered as a promising paradigm to deliver computation-intensive and delay-sensitive services to users. IoT service requests can be served by multiplemicroservices (MSs) that form a chain, called amicroservicechain (MSC). However, the high complexity of MSs and security threats in MEC-enabled IoT pose new challenges to MSC dependability. Proactive rejuvenation techniques can mitigate the impact of resource degradation of MSs and hostoperatingsystems (OSes) executing them. In this article, we develop a multi-dimensional semi-Markov model to investigate the effectiveness of proactive rejuvenation techniques in improving the dependability (availability and reliability) of a dynamic and heterogeneous MSC. The results of numerical experiments firstly reveal how MSs can be effectively combined, in different deployment configurations, with host OSes to improve MSC dependability, secondly jointly optimize the rejuvenation trigger intervals of host OS and MSs running on it, and finally show the impact of time-varying parameters. We also identify the bottlenecks for MSC dependability improvement by sensitivity analysis, and give the ranges of important parameter values guaranteeing five-nines availability. In addition, the superiority of our model is demonstrated by comparison with the continuous-time Markov chain model.

With the rapid and wide development and deployment of system virtualization, service availability analysis has become increasingly important in a virtualized system (VS) which suffers from software aging. Software rejuvenation techniques can be applied to improve service availability but its effectiveness depends on the rejuvenation policy, which defines when and where to rejuvenate, and which rejuvenation technique to be triggered. This article aims to analyze the optimal inspection time interval for maximizing application service (AS) availability under a three-level rejuvenation policy, in which rejuvenation techniques are deployed at each level, namely, AS, virtual machine (VM), and virtual machine monitor (VMM) levels. We first apply Markov regenerative process to construct an analytical model for the VS. Experiments of injecting memory leaks are conducted to measure aging-related parameters. Furthermore, numerical analysis is carried out to study the quantitative relationship between AS availability and inspection time interval, and determine the approximate optimal inspection time interval.

Understanding and predicting types of bugs are of practical importance for developers to improve the testing efficiency and take appropriate steps to address bugs in software releases. However, due to the complex conditions under which faults manifest and the complexity of the classification rules, the automatic classification of Mandelbugs is a difficult task. In this article, we present a deep semantic information-based Mandelbug classification method that combines a semantic model with a deep learning classifier and makes use of both labeled and unlabeled bug reports. By training the bug report semantic model on millions of bug reports, each word in the text of a bug report is represented as a word embedding that preserves the semantic relationship among the words. Then, a convolutional neural network model is designed to capture the high-level features of bug reports to obtain a more accurate classification. Moreover, the effects of the semantic model size and domain on the classification results are investigated, and the quality of word embeddings is evaluated by analyzing several important parameters.

Migration-based Dynamic Platform (MDP) technique, a type of Moving Target Defense (MTD) techniques, defends against sophisticated cyber-attacks by randomly and dynamically selecting a platform for executing service/job. Security defense mechanisms protect service/job usually at the cost of degrading its performance. Therefore, it is valuable to make a trade-off between service/job security and its performance. However, previous researches on MTD techniques either focused on analyzing MTD effectiveness of protecting service/job or studied service/job performance with the assumption that attacks on service/job make no influence on its execution. This article aims to apply analytical modeling techniques to investigate the impact of MDP technique on job completion time in a system under attack. We use Stochastic Reward Nets (SRNs) to develop a Markov chain-based model for capturing typical behaviors of the adversary, the vulnerable system and a job. The formulas are derived for calculating the metrics of interest. Numerical analysis is conducted to study the impact of key parameters on job completion time and job security loss.

The Workshop on Education and Practice of Performance Engineering, in its 3rd edition, brings together University researchers and Industry Performance Engineers to share education and practice experiences. The recommendations from previous WEPPE workshops pointed to the need to form a team of critical thinkers that also have good communication skills.

The safety-critical applications of vehicular ad hoc networks (VANETs) require high reliability and low transmission latency. IEEE 802.11p and IEEE 802.11bd are two standards proposed for such vehicular communication systems. In this paper, we propose an effective SINR-based model to conduct the QoS analysis of IEEE 802.11p/bd driven VANETs for safety applications. First, a semi-Markov process (SMP) model with a D/G/1/1 queue is tailored and modified for characterizing channel access behavior of IEEE 802.11 broadcast networks with deterministic message generation rate. Then, a novel approach is developed to derive the distribution of signal-to-interference-to-noise ratio (SINR) on each receiver in the VANET, given general channel fading/shadowing models as well as general node geometry distributions. Consequently, various QoS metrics in Physical/MAC/Application layer of VANETs are defined and evaluated. Compared with the existed analytic SINR-based models for broadcast VANETs, the proposed models are more general, more accurate, and are faster to solve. Finally, a new mechanism is shown to map the performance in physical layer into the QoS quantification in higher layer so that the QoS prediction of IEEE 80211bd driven VANETs is enabled. Furthermore, comparison between 802.11p and 802.11bd is conducted regarding how the stringent QoS requirements of selected safety applications in both human driving VANETs and autonomous driving VANETs are met by the two communication systems. Constructive conclusions are given on the suitability of IEEE 802.11bd for VANET critical safety services and the directions of future development.

The recent trend of network softwarization suggests a radical shift in the implementation of traditional network intelligence. In Software Defined Networking (SDN), for instance, the control plane functions of forwarding devices are outsourced to the controller. Softwarized network components are expected to provide uninterrupted service during long periods of time, which makes them prone to the effects ofsoftware aging, a phenomena that has been observed in operational software systems where the failure rate increases or the performance of the software degrades with the elapsed time since the last restart. The effects of software aging in operational networks are typically mitigated bysoftware rejuvenation, i.e., planned restarts cleaning the internal system state in order to prevent or postpone aging-related failures. This article presentsARES, a three-step methodological framework for the management of the effects of software aging in softwarized networks, applied to the case study of open source SDN orchestration platforms. Using ARES, we demonstrate that software aging is a systematic problem that cannot be neglected in network orchestration systems. It stems not only from aging-related bugs and natural aging due to fragmentation, but also from design choices, e.g., when implementing distributed systems. Measurements for Open Network Operating System (ONOS) and OpenDaylight (ODL) demonstrate how “simple” and common networking tasks let network performance degrade rapidly and even lead to crashes: for instance, adding and removing 300 intents per second in ONOS significantly increases the response time by 50% per day and depletes the memory at the rate of 18GB per day. Moreover, we demonstrate a first rejuvenation approach that can mitigate the effects of aging in ONOS.

Mandelbug-caused software failures are significant threats to system availability, especially in the context of mission-critical and safety-critical systems. However, there is still no systematic method for keeping the software free from Mandelbugs before release. To guarantee the availability of systems suffering from Mandelbugs, environmental-diversity-based fault tolerance techniques have been proposed to recover from the failures caused by them. In this article, we develop and study an analytic model to assess the availability of systems that utilize a sequence of environmental-diversity-based recovery methods. Improving over previous relevant studies, the availability formula we obtain in this article works for any number of recovery methods the system is equipped with; it is also independent on both the nature of those recovery methods and the order of their utilization. In addition, we consider the problem of how to arrange the set of available recovery methods to achieve the largest system availability. Based on the results of our analysis, we develop an open-source tool, called OPENS, which assists in the calculation of the optimal system availability. We validate the effectiveness of the proposed modeling approach in two ways, namely by comparing our results with those obtained for specific systems considered in relevant studies and by conducting numerical analyses for more general scenarios of its application.

Intrusion tolerance is an ability to keep the correct service by masking the intrusion based on fault-tolerant techniques. With the rapid development of virtualization, the virtual machine (VM)-based intrusion tolerance scheme has been developed according to the concept of state machine replication with Byzantine fault tolerant technique. In this article, we present the quantitative security evaluation of the VM-based intrusion tolerant system with the time to security failure. We assume that the arrival stream follows a Markovian arrival process (MAP), which is one of the most general stochastic processes, and analytically derive the Laplace-Stieltjes transform of time to security failure based on the analysis of the MAP/G/1/∞ queue.

The Internet world is moving toward a scenario where users and applications have very diverse service expectation, making the current best-effort model inadequate and limiting. To be able to design high-availability service systems, it is essential to consider not only the actual failure and recovery behavior of the service infrastructure, but also the behavioral aspects of its user and their subjective perceptions and reactions in the wake of failure events. In this paper, we propose to use Markov regenerative process (MRGP) models to study the availability of Internet-based services perceived by a Web user on two different online service scenarios: (1) single-user-single-host and (2) single-user-multiple-host. The MRGP models capture the interactions between the service facility and the user. We also detect its parameter bottlenecks by applying the formal sensitivity analysis technique. The trends of the users' perceived unavailability are analyzed with the changed different parameter values, and the necessity of the sophisticated MRGP modeling is evidenced by the comparisons with the corresponding continuous time Markov chain (CTMC) models, which show that the popular convenient CTMC models tend to overestimate user-perceived service unavailability. Finally, controlled experiments are carried out on a real Web service to demonstrate the proposed approach.

In Software Defined Networking (SDN), network programmability is enabled through a logically centralized control plane. Production networks deploy multiple controllers for scalability and reliability reasons, which in turn rely on distributed consensus protocols to operate in a logically centralized manner. However, bugs in distributed control plane can have disastrous effects on the data plane, e.g., losing traffic by installing paths containing blackholes. In this paper we study the prevalence of issues in state-of-the-art distributed frameworks in SDN, by analyzing 500+ issues reported in two of the largest open source SDN controller platforms: Open Network Operating System (ONOS) and OpenDaylight (ODL), during the period between 2014-2019. We identify system vulnerabilities, localize dependability bottlenecks, and provide stochastic models for a holistic assessment of system dependability.

Software failures caused by data race bugs have always been major concerns in parallel and distributed systems, despite significant efforts spent in software testing. Due to their nondeterministic and hard-to-reproduce features, when evaluating systems' operational reliability, a rather long period of experimental execution time is expected to be spent on observing failures caused by data race conditions. To address this problem, in this paper, we make two contributions. First, this paper proposes stress testing with influencing factors, in which the system runs under certain workloads for a long time with controlled stress conditions to accelerate the occurrence of data race failures. Second, it explores and formulates mathematical relationship models between data races' statistical characteristics of time to failure (TTF) or mean TTF (MTTF) and the influencing factors. Such relationship models are used for TTF/MTTF extrapolation under different operational conditions and are essential to reduce systems' reliability evaluation time. The proposed method is empirically evaluated on six applications suffering from failures caused by real-world data race bugs. Through analysis of the experimental results, we obtain several important findings: First, the reduction in the manifestation time to data race failures achieved by controlling the influencing factors is statistically significant. Second, Power model is the best-fitting model of the relationship between the MTTF and the influencing factors. Third, Power Weibull distribution is the best-fitting probability distribution between the TTF and the influencing factors. Finally, the TTF/MTTF can be accurately estimated with the approach proposed in this paper.

High reliability and availability is a requirement for most technical systems. Reliability and availability assurance methods based on probabilistic models is the topic addressed in this talk. Non-state-space solution methods are often used to solve models based on reliability block diagrams, fault trees and reliability graphs. Relatively efficient algorithms are known to handle systems with hundreds of components and have been implemented in many software packages. Nevertheless, many practical problems cannot be handled by such algorithms. Bounding algorithms are then used in such cases as was done for a major subsystem of Boeing 787. Non-state-space methods derive their efficiency from the independence assumption that is often violated in practice. State space methods based on Markov chains, stochastic Petri nets, semi-Markov and Markov regenerative processes can be used to model various kinds of dependencies among system components. However, the resulting state space explosion severely restricts the size of the problem that can be solved. Hierarchical and fixed-point iterative methods provide a scalable alternative that combines the strengths of state space and non-state-space methods and have been extensively used to solve real-life problems. We will take a journey through these model types via interesting real-world examples chosen from IBM, Cisco, Sun Microsystems, and Boeing. These methods and applications are fully described in a recently completed book: Reliability and Availability Engineering: Modeling, Analysis and Applications, Cambridge University Press, 2017.

Software aging, which is caused by Aging-Related Bugs (ARBs), tends to occur in long-running systems and may lead to performance degradation and increasing failure rate during software execution. ARB prediction can help developers discover and remove ARBs, thus alleviating the impact of software aging. However, ARB-prone files occupy a small percentage of all the analyzed files. It is usually difficult to gather sufficient ARB data within a project. To overcome the limited availability of training data, several researchers have recently developed cross-project models for ARB prediction. A key point for cross-project models is to learn a good representation for instances in different projects. Nevertheless, most of the previous approaches neither consider the reconstruction property of new representation nor encode source samples' label information in learning representation. To address these shortcomings, we propose a Supervised Representation Learning Approach (SRLA), which is based on double encoding-layer autoencoder, to perform cross-project ARB prediction. Moreover, we present a transfer cross-validation framework to select the hyper-parameters of cross-project models. Experiments on three large open-source projects demonstrate the effectiveness and superiority of our approach compared with the state-of-the-art approach TLAP.

The study of software failures has now become more important since it has been recognized that computer system outages are more due to software faults than due to hardware faults. The phenome- non of "software aging", in which the state of the software system degrades with time, has been reported in widely used software and also in high-availability and safety-critical systems. The primary causes of this degradation are the exhaustion of operating system resources, data corruption and numerical error accumulation. This may eventually lead to performance degradation of the software system or crash/hang failure or both. To counteract this phenome- non, a proactive approach to fault management, called "software rejuvenation" has been proposed. This essentially involves grace- fully terminating an application or a system and restarting it in a clean internal state. This process removes the accumulated errors and frees up operating system resources. This method therefore avoids or postpones unplanned and potentially expensive system outages due to software aging. In this talk, we discuss methods of evaluating the effectiveness of proactive fault management in operational software systems and determining optimal times to perform rejuvenation.

Infrastructure as a Service (IaaS) is one of the most significant and fastest growing fields in cloud computing. To efficiently use the resources of an IaaS cloud, several important factors such as performance, availability, and power consumption need to be considered and evaluated carefully. Evaluation of these metrics is essential for cost-benefit prediction and quantification of different strategies which can be applied to cloud management. In this paper, analytical models based on Stochastic Reward Nets (SRNs) are proposed to model and evaluate an IaaS cloud system at different levels. To achieve this, an SRN is initially presented to model a group of physical machines which are controlled by a management layer. Afterwards, the SRN models presented for the groups of physical machines in the first stage are combined to capture a monolithic model representing an entire IaaS cloud. Since the monolithic model does not scale well for large cloud systems, two approximate SRN models using folding and fixed-point iteration techniques are proposed to evaluate the performance, availability, and power consumption of the IaaS cloud. The existence of a solution for the fixed-point approximate model is proved using Brouwer's fixed-point theorem. A validation of the proposed monolithic and approximate models against both an ad-hoc discrete-event simulator developed in Java and the CloudSim framework is presented. The analytic-numeric results obtained from applying the proposed models to sample cloud systems show that the errors introduced by approximate models are insignificant while an improvement of several orders of magnitude in the state space reduction of the monolithic model is obtained.

In some applicable scenarios, such as community patrolling, mobile nodes are restricted to move only in their own communities. Exploiting the meetings of the nodes within the same community and the nodes within the neighboring communities, a delay tolerant network (DTN) can provide communication between any two nodes. In this paper, two analytical models based on stochastic reward nets (SRNs) are proposed to evaluate the performance of the epidemic content retrieval in such multi-community DTNs. Performance measures computed by the proposed models are the average retrieval delay and the average number of transmissions. The monolithic SRN model proposed in the first step is not scalable, in terms of the number of communities and nodes, due to the state space explosion in the underlying Markov chain. In order to solve the scalability problem of the monolithic model, an approximate model based on the folding technique is presented which allows us to evaluate the performance of large-scale DTNs. In order to cross-validate the results obtained from the proposed models, we extend the ONE simulator to support our network model. The analytic-numeric results indicate that both models have good accuracy, and the folded model reduces the state space highly, achieving good scalability without any significant loss of accuracy.

The Android operating system (OS) is a sophisticated man-made system and is the dominant OS in the current smartphone market. Due to the accumulation of errors in the system internal state and the incremental consumption of resources, such as the Dalvik heap memory of software applications and the physical memory, software aging is observed frequently and recognized as a chronic problem of Android smartphones. To mitigate this problem, we propose a two-level software rejuvenation, with the two levels referring to software applications and the OS, in this paper. Based on this strategy, a Markov regenerative process model is constructed to evaluate the steady-state availability and to optimize the time required to trigger rejuvenation for Android smartphones. The parameters of the model, such as the degradation rate and failure rate of software applications and the Android OS, are obtained via our testing platform. Experiments on two real Android applications show that the availability of an Android smartphone increases by 10.81% and 10.18% for the two subjects in our experiments, respectively. An empirical study comparing our two-level strategy with one-level strategies (single application-level and system-level rejuvenation) further verifies the effectiveness of our approach.

In long running systems, software tends to encounter performance degradation and increasing failure rate during execution. This phenomenon has been named software aging, which is caused by aging-related bugs (ARBs). Testing resource allocation can be optimized by identifying ARB-prone modules with ARB prediction. However, due to the low presence and reproducing difficulty of ARBs, it is usually hard to collect sufficient training data to carry out within-project ARB prediction. In this paper, we propose an approach named transfer learning based aging-related bug prediction (TLAP) to perform cross-project ARB prediction. TLAP first takes advantage of transfer learning to reduce distribution difference between training and testing project. Then, class imbalance learning is conducted to mitigate the severe class imbalance between ARB-prone and ARB-free modules. Finally, machine learning methods are used to handle bug prediction tasks. The effectiveness of this approach is validated and evaluated by nine groups of experiments on real software systems. Major conclusions from the experiments include the following: first, TLAP improves cross-project ARB prediction on average compared with traditional machine learning methods; second, utilizing information from multiple-projects can further improve the prediction performance on average. In the best case, it outperforms within-project prediction; third, the number of ARB-prone files and distribution similarity can influence TLAP performance.

This paper presents an empirical study of 5741 bug reports for the Linux kernel from an evolutionary perspective, with the aim of obtaining a deep understanding of bug characteristics in the Linux operating system. Bug classification is performed based on the fault triggering conditions, followed by an analysis of the proportions and evolution of the bug types as well as comparisons among versions, products, and repair locations. In addition, an analysis of regression bugs and the relationship between the types of bugs and the time needed to fix them are presented. Moreover, a procedure for the analysis of bug type characteristics based on complex network metrics is proposed, and four network metrics, i.e., degree, clustering coefficient, betweenness, and closeness, are utilized to further investigate the relationship between bug types and software metrics. In this paper, 22 interesting findings based on the empirical results are revealed, and guidance based on these findings is provided for developers and users.

This paper aims to analyze transient security and dependability of a vulnerable critical system, under vulnerability-related attack and two reactive defense strategies, from a severe vulnerability announcement until the vulnerability is fully removed from the system. By severe, we mean that the vulnerability-based malware could cause significant damage to the infected system in terms of security and dependability while infecting more and more new vulnerable computer systems. We propose a Markov chain-based survivability model for capturing the vulnerable critical system behaviors during the vulnerability elimination process. A high-level formalism based on Stochastic Reward Nets is applied to automatically generate and solve the survivability model. Survivability metrics are defined to quantify system attributes. The proposed model and metrics not only enable us to quantitatively assess the system survivability in terms of security risk and dependability, but also provide insights on the system investment decision. Numerical experiments are constructed to study the impact of key parameters on system security, dependability and profit.

Hyperledger Fabric (HLF) is an open-source implementation of a distributed ledger platform for running smart contracts in a modular architecture. In this paper, we present a performance model of Hyperledger Fabric v1.0+ using Stochastic Reward Nets (SRN). From our detailed model, we can compute the throughput, utilization and mean queue length at each peer and critical processing stages within a peer. To validate our model, we setup an HLF network in our lab and run workload using Hyperledger Caliper. From our analysis results, we find that time to complete the endorsement process is significantly affected by the number of peers and policies such as AND (). The performance bottleneck of the ordering service and ledger write can be mitigated using a larger block size, albeit with an increase in latency. For the committing peer, the transaction validation check (using Validation System Chaincode (VSCC)) is a time-consuming step, but its performance impact can be easily mitigated since it can be parallelized. However, its performance is critical, since it absorbs the shock of bursty block arrivals. We also analyze various what-if scenarios, such as peers processing transactions in a pipeline, and multiple endorsers per organization.

In this paper, the performance of a grid resource is modeled and evaluated using stochastic reward nets (SRNs), wherein the failure–repair behavior of its processors is taken into account. The proposed SRN is used to compute the blocking probability and service time of a resource for two different types of tasks: grid and local tasks. After modeling a grid resource and evaluating the performability measures, an algorithm is presented to find the probability mass function (pmf) of the service time of the grid resource for a program which is composed of grid tasks. The proposed algorithm exploits the universal generating function to find the pmf of service time of a single grid resource for a given program. Therefore, it can be used to compute the pmf of the service time of entire grid environment for a workflow with several dependent programs. Each possible scheduling of programs on grid resources may result in different service times and successful execution probabilities. Due to this fact, a genetic-based scheduling algorithm is proposed to appropriately dispatch programs of a workflow application to the resources distributed within a grid computing environment. Numerical results obtained by applying the proposed SRN model, the algorithm to find the pmf of grid service time, and the genetic-based scheduling algorithm to a comprehensive case study demonstrate the applicability of the proposed approach to real systems.

Heterogeneity prevails not only among physical machines but also among workloads in real IaaS Cloud data centers (CDCs). The heterogeneity makes performance modeling of large and complex IaaS CDCs even more challenging. This paper considers the scenario where the number of virtual CPUs requested by each customer job may be different. We propose a hierarchical stochastic modeling approach applicable to IaaS CDC performance analysis under such a heterogeneous workload. Numerical results obtained from the proposed analytic model are verified through discrete-event simulations under various system parameter settings.

This paper presents a performability model for RAID storage systems using Markov regenerative process to compare different RAID architectures. While homogeneous Markov models are extensively used for reliability analysis of RAID storage systems, the memory-less property of the sojourn time assumed in such models is not satisfied in reality, especially in disk rebuild process whose progress is not interrupted even at an event of another disk failure. In this paper, we use Markov regenerative process which allows us to model the generally distributed rebuild times providing a needed extension of the traditional Markov models. The Markov regenerative process is then used to assess the performability of the storage system by assigning reward rates to each state based on the real storage benchmark results. Our numerical study characterizes the performability advantage of RAID6 architecture over RAID10 architecture in terms of sequential read access. Our findings include that the effect of exponential assumption for the rebuild times has practically negligible effect when we focus on data availability. However, the effect this approximation on performability prediction may not be negligible especially when the performance level drastically changes in degraded states. Our MRGP model provides more accurate prediction of performability in such cases.

In software defined networking (SDN), critical control plane functions are offloaded to a software entity known as the SDN controller. Today's SDN controllers are complex software systems, owing to heterogeneity of networks and forwarding devices they support, and are inherently prone to bugs. Our previous work showed that software reliability growth models (SRGM) can model the stochastic nature of bug manifestation process open source SDN controllers. In this paper, we focus on different applications of our SRGM framework crucial for an efficient management of SDN-based networks. We provide guidelines for network operators to decide when the controller software is mature enough to be deployed in operational environment, based on the reliability requirements of network applications, and quantify the marginal benefits of the prolonged testing phase on the software quality. We show how the accuracy of software reliability prediction in the early phase of the software lifecycle can be improved by extrapolating the behavior of previous controller software releases. We also propose software maturity metrics that can be used by operators to discriminate between the competing SDN controller designs, i.e., ONOS and OpenDaylight, when software reliability is a major concern.

Software Defined Networking (SDN) exposes critical networking decisions, such as traffic routing or enforcement of the critical security policies, to a software entity known as the SDN controller. Controller software, as written by humans, is intrinsically prone to bugs, which may impair the network performance as a whole, if activated. Software reliability growth models (SRGM) are often used to estimate and predict the reliability of the software in the operational phase based on the fault report data during the testing phase. These models can be used to predict the number of residual bugs in the software, as well as failure intensity, software reliability and optimal software release time. In this paper we analyze ten releases of ONOS open source controller, whose uncensored fault reports are available online.

Datarace is a common problem on shared-memory parallel computers, including multicores. Due to its dependence on the thread scheduling scheme of its execution environment, the time to a datarace failure is usually very long. How to accelerate the occurrence of a datarace failure and further estimate the mean time to failure (MTTF) is an important topic to be studied. In this paper, the influencing factors for failures triggered by datarace bugs are explored and their influences on the time to datarace failure including the relationship with the MTTF are empirically studied. Experiments are conducted on real datarace suffering programs to verify the factors and their influences. Empirical results show that the influencing factors do have influences on the time to datarace failure of the subjects. They can be used to accelerate the occurrence of datarace failures and accurately estimate the MTTF.

Linux operating system is a complex system that is prone to suffer failures during usage, and increases difficulties of fixing bugs. Different testing strategies and fault mitigation methods can be developed and applied based on different types of bugs, which leads to the necessity to have a deep understanding of the nature of bugs in Linux. In this paper, an empirical study is carried out on 5741 bug reports of Linux kernel from an evolution perspective. A bug classification is conducted based on fault triggering conditions, followed by the analysis of the evolution of bug type proportions over versions and time, together with their comparisons across versions, products and regression bugs. Moreover, the relationship between bug type proportions and clustering coefficient, as well as the relation between bug types and time to fix are presented. This paper reveals 13 interesting findings based on the empirical results and further provides guidance for developers and users based on these findings.

The growing popularity and complexity of Android operating system makes it prone to suffer failures during usage, which increases difficulties of fixing bugs. Different strategies and mitigation methods can be developed and applied based on different types of bugs, which gives rise to the necessity to have a deep understanding of the nature of bugs in this system. In this paper, an empirical study is taken on 513 bug reports from Android operating system. A bug classification is conducted according to fault triggering conditions, followed by the analysis of bug types and bug attributes. Moreover, the comparison of bug types between Android and Linux is carried out. This paper reveals ten interesting findings based on the empirical results from these three aspects and further provides guidance for developers and users based on these findings.

While Blockchain network brings tremendous benefits, there are concerns whether their performance would match up with the mainstream IT systems. This paper aims to investigate whether the consensus process using Practical Byzantine Fault Tolerance (PBFT) could be a performance bottleneck for networks with a large number of peers. We model the PBFT consensus process using Stochastic Reward Nets (SRN) to compute the mean time to complete consensus for networks up to 100 peers. We create a blockchain network using IBM Bluemix service, running a production-grade IoT application and use the data to parameterize and validate our models. We also conduct sensitivity analysis over a variety of system parameters and examine the performance of larger networks

When combining several services into a composite service, it is non-trivial to determine, prior to service deployment, performance and reliability values of the composite service. Moreover, once the service is deployed, it is often the case that during operation it fails to meet its service-level agreement (SLA) and one needs to detect what has gone wrong (i.e., performance/reliability bottlenecks). To study these issues, we develop a Semi-Markov Process (SMP) formulation of composite services with failures and restarts. By explicitly including failure states into the SMP representation of a service, we can compute both its performance and reliability using a single SMP. We can also detect its performance and reliability bottlenecks by applying the formal sensitivity analysis technique. We demonstrate our approach by choosing a representative example that is validated using experiments on real Web services.

Transient survivability analysis of a virtualized system (VS) is critical to the wide deployment of cloud services. The existing research of VS availability and/or reliability focused on the steady-state analysis. This paper presents a model and the closed-form solutions to analyze the survivability of both cloud service and VS after a service breakdown occurrence by using continuous-time Markov chain. Service breakdown may be caused by software rejuvenation of virtual machine (VM) and/or VM monitor (VMM), or caused by VM and/or VMM bugs. The VS applies two techniques for improving service survivability: VM failover and live VM migration. The proposed model and the defined survivability metrics not only enable us to quantitatively assess the system survivability but also provide insights on the investment efforts in system recovery strategies. Sensitivity analysis through numerical analysis is carried out to study the impact of key parameters on system survivability.

In this paper, we present the software reliability analysis of the flight software of a recently launched space mission. For our analysis, we use the defect reports collected during the flight software development. We find that this software was developed in multiple releases, each release spanning across all software life-cycle phases. We also find that the software releases were developed and tested for four different hardware platforms, spanning from off-the-shelf or emulation hardware to actual flight hardware. For releases that exhibit reliability growth or decay, we fit Software Reliability Growth Models (SRGM); otherwise we fit a distribution function. We find that most releases exhibit reliability growth, with Log-Logistic (NHPP) and S-Shaped (NHPP) as the best-fit SRGMs. For the releases that experience reliability decay, we investigate the causes for the same. We find that such releases were the first software releases to be tested on a new hardware platform, and hence they encountered major hardware integration issues. Also such releases seem to have been developed under time pressure in order to start testing on the new hardware platform sooner. Such releases exhibit poor reliability growth, and hence exhibit high predicted failure rate. Other problems include hardware specification changes and delivery delays from vendors. Thus, our analysis provides critical insights and inputs to the management to improve the software development process. As NASA has moved towards a product line engineering for its flight software development, software for future space missions will be developed in a similar manner and hence the analysis results for this mission can be considered as a baseline for future flight software missions.

Software failures are still a major concern in mission- and enterprise-critical contexts, despite significant efforts spent in software testing. In fact, while software testing is effective against easily-reproducible bugs (Bohrbugs), it is considerably less suitable for dealing with bugs that lead to hard-to-reproduce failures (Mandelbugs). On the positive side, the elusive nature of Mandelbugs provides opportunities for failure recovery, which are investigated in this paper. Based on real cases of Mandelbugs in eleven Information Technology (IT) systems running in production, the paper proposes a model that describes the recovery processes in IT systems. It then presents closed-form expressions, and a numerical analysis, of the mean time to recovery, and the software (un)availability. This analysis allows the designer to compare recovery strategies, as well as to determine the parameters having a high influence on the efficacy of recovery from failures caused by Mandelbugs.

Software rejuvenation is a proactive software control technique that is used to improve a computing system performance when it suffers from software aging. In this paper, a two-granularity inspection-based software rejuvenation policy, which works as a closed-loop control technique, is proposed. This policy mitigates the negative impact of two-level software aging. The two levels considered are the user-level applications and the operating system. A Markov regenerative process model is constructed based on the system condition. We obtain the degradation rate of the application software and operating system from fault injection experiments. The diagnostic accuracy of the adopted monitor and analysis system, which is applied to inspect the application software and operating system, is considered as we provide the optimal rejuvenation strategies. Finally, the availability and the overall loss probability with their corresponding optimal inspection time intervals are obtained numerically based on the parameter values estimated from the experiments. Experimental results show that two-granularity software rejuvenation is much more effective than traditional single-level software rejuvenation. In our experimental study, when two-granularity software rejuvenation is used, the unavailability and the overall loss probability of the system were reduced by 17.9% and 2.65%, respectively, in comparison with the single-level rejuvenation.

Cloud computing infrastructures provide services to a wide number of users whose behavior can deeply change at the occurrence of particular events. To correctly handle such situations a cloud infrastructure have to be reconfigured in a way that does not cause degradation in the overall performance. Otherwise, the quality of service specified in the service level agreement could be violated. To prevent such situations, the infrastructure could be organized as an autonomic system where self-adaptation and self-configuration techniques are implemented. Appropriate design choices become important in order not to fail in this goal. We propose a technique, based on a Petri net model and a specific analytical analysis approach, to represent Infrastructure-as-a-Service (IaaS) systems in the case in which the load conditions can suddenly change and reactive autonomic management techniques are applied to mitigate the consequences of the change. The model we propose is able to appropriately evaluate performance metrics in such critical situations making it suitable as a design tool for IaaS cloud systems.

This paper provides a summary of the First International Workshop on Model Based Design for Cyber- Physical Systems (MB4CP 2015) in conjunction with DSN 2015 conference in Rio de Janeiro, Brazil.

Explosive growth of data generation and increasing reliance of business analysis on massive data make data loss more damaging than ever before. Thus it has also become a critical issue for businesses to protect important data effectively. In a system with multiple data sets, complex system configurations and data protection requirements, backup planning plays an important role for maintaining the desired level of data protection while minimizing the impact on system operation. In this paper we investigate the use of Markov Decision Process (MDP) to guide the planning of data backup operations. To improve the applicability of the MDP framework to large systems, we present a novel approximation method to enhance its scalability. The benefit of the framework is demonstrated through numerical examples, where our MDP method reduces the storage system downtime by over 50% compared to the best heuristic approach.

In this paper, performance of grid computing environment is studied in the presence of failure-repair of the resources. To achieve this, in the first step, each of the grid resource is individually modeled using Stochastic Reward Nets (SRNs), and mean response time of the resource for grid tasks is computed as a performance measure. In individual models, three different scheduling schemes called random selection, non-preemptive priority, and preemptive priority are considered to simultaneously schedule local and grid tasks to the processors of a single resource. In the next step, single resource models are combined to shape an entire grid environment. Since the number of the resources in a large-scale grid environment is more than can be handled using such a monolithic SRN, two approximate SRN models using folding and fixed-point techniques are proposed to evaluate the performance of the whole grid environment. Brouwer's fixed-point theorem is used to theoretically prove the existence of a solution to the fixed-point approximate model. Numerical results indicate an improvement of several orders of magnitude in the model state space reduction without a significant loss of accuracy.

Traditional system-oriented dependability metrics like reliability and availability do not fully reflect the impact of system failure-repair behavior in service-oriented environments. The telecommunication systems community prefers to use Defects Per Million (DPM), defined as the number of calls dropped out of a million calls due to failures, as a user-perceived dependability metric. In this paper, we provide new formulation for the computation of the DPM metric for a system supporting Voice over IP functionality using the Session Initiation Protocol (SIP). We evaluate different replication schemes that can be used at the SIP application server. They include the effects of software failure, failure detection, recovery mechanisms, and imperfect coverage for recovery mechanisms. We derive closed-form expressions for the DPM taking into account the transient behavior of recovery after a failure. Our approach and underlying models can be readily extended to other types of service-oriented environments.

The explosive growth of data generation and increasing reliance of business analysis on massive data make data loss more damaging than ever before. Nowadays many organizations start relying on cloud services for keeping their valuable data. It is a critical issue for cloud service provider to protect the data for individual users securely and effectively. To protect the data in a system with multiple data sources, backup schedule plays an important role for achieving the desired level of data protection while minimizing the impact on system operation. In this paper we investigate the use of Markov Decision Process (MDP) to guide the scheduling of data backup operation and propose a framework to automatically generate an MDP instance from system specifications and data protection requirements. We then demonstrate the benefits of the MDP approach.

We investigate the dependence of software failure reproducibility on the environment in which the software is executed. The existence of such dependence is ascertained in literature, but so far it is not fully characterized. In this paper we pinpoint some of the environmental components that can affect the reproducibility of a failure and show this influence through an experimental campaign conducted on the My SQL Server software system. The set of failures of interest is drawn from My SQL's failure reports database and an experiment is designed for each of these failures. The experiments expose the influence of disk usage and level of concurrency on My SQL failure reproducibility. Furthermore, the results show that high levels of usage of these factors increase the probabilities of failure reproducibility.

Virtual machines (VM) are used in cloud computing systems to handle user requests for service. A typical user request goes through several cloud service provider specific processing steps from the instant it is submitted until the service is completed. In the process of providing the service, VM failures cause the user's request to be dropped. To mitigate the adverse impact of VM failure, replication mechanisms, either using cold, warm or hot replication, can be used. In this paper, we model the system behavior with a structure-state process to characterize the failure-recovery behavior of a VM in a cloud that uses one of the aforementioned replication schemes. We use a service-oriented dependability metric called Defects Per Million (DPM), defined as the number of user requests dropped out of a million. The structure-state process approach is used to analyze the job completion time distribution and subsequently we compute the DPM by counting the number of requests exceed the specified deadline. The effectiveness of replication schemes are demonstrated through numerical results.

Software systems running continuously for a long time often confront software aging, which is the phenomenon of progressive degradation of execution environment caused by latent software faults. Removal of such faults in software development process is a crucial issue for system reliability. A known major obstacle is typically the large latency to discover the existence of software aging. We propose a systematic approach to detect software aging which has in a shorter test time and higher accuracy compared to traditional aging detection via stress testing and trend detection with high confidence. The approach is based on a comparative differential analysis where a software version under test is compared with against a previous robust version by observing in terms of behavioral (signal) changes during system tests of resource metrics. A key instrument adopted is a divergence chart, which expresses time-dependent differences between two signals, allowing us to detect changes in the system metrics' values which indicate the existence of software aging. In our experimental study, we focuses on memory-leak detection and the and evaluates divergence charts are computed using various multiple statistical techniques combined paired with different application-level memory related metrics (RSS and Heap Usage). The experimental results show that the statistical process control techniques used in our approach proposed method achieves good performance for memory-leak detection, when compared with other in comparison to techniques widely adopted in previous works (e.g., linear regression, moving average and median).

SUMMARY Smart grids are fostering a paradigm shift in the realm of power distribution systems. Whereas traditionally different components of the power distribution system have been provided and analyzed by different teams through different lenses, smart grids require a unified and holistic approach that takes into consideration the interplay of communication reliability, energy backup, distribution automation topology, energy storage, and intelligent features such as automated fault detection, isolation, and restoration (FDIR) and demand response. In this paper, we present an analytical model and metrics for the survivability assessment of the distribution power grid network. The proposed metrics extend the system average interruption duration index, accounting for the fact that after a failure, the energy demand and supply will vary over time during a multi‐step recovery process. The analytical model used to compute the proposed metrics is built on top of three design principles: state space factorization, state aggregation, and initial state conditioning. Using these principles, we reduce a Markov chain model with large state space cardinality to a set of much simpler models that are amenable to analytical treatment and efficient numerical solution. In case demand response is not integrated with FDIR, we provide closed form solutions to the metrics of interest, such as the mean time to repair a given set of sections. Under specific independence assumptions, we show how the proposed methodology can be adapted to account for multiple failures. We have evaluated the presented model using data from a real power distribution grid, and we have found that survivability of distribution power grids can be improved by the integration of the demand response feature with automated FDIR approaches. Our empirical results indicate the importance of quantifying survivability to support investment decisions at different parts of the power grid distribution network. Copyright © 2014 John Wiley & Sons, Ltd.

The need for high reliability, availability and performance has significantly increased in modern applications, that handle rapidly growing demands while providing uninterruptible services. Cloud computing systems fundamentally provide access to large pools of data and computational resources. Eucalyptus is a software framework largely used to implement private clouds and hybrid-style Infrastructure as a Service. It implements the Amazon Web Service (AWS) API, allowing interoperability with other AWS-based services. This article investigates the software aging effects in the Eucalyptus framework, considering workloads composed of intensive requests for remote storage attachment and virtual machine instantiations. We found problems that may be harmful to system dependability and performance, specifically regarding to RAM memory and swap space exhaustion, besides highly excessive CPU utilization by the virtual machines. We also present an approach that applies time series analysis to schedule rejuvenation, so as to reduce the downtime by predicting the proper moment to perform the rejuvenation. We experimentally evaluate our approach using an Eucalyptus test bed. The results show that our approach achieves higher availability, when compared to a threshold-triggered rejuvenation method based on continuous monitoring of resources utilization.

This article analyzes the completion time of a job running on a virtualized server subject to software aging and rejuvenation in a virtual machine monitor (VMM). A job running on the server may be interrupted by virtual machine (VM) failure, VMM failure or VMM rejuvenation. The job interruption is categorized as either preemptive-repeat ( prt ), in which case the interrupted job needs to restart from the beginning, or preemptive-resume ( prs ), in which case the job resumes execution from the point of interruption. Using a semi-Markov process (SMP) to model the server behavior, the steady-state server availability is computed and the theory developed in Kulkarni et al. [1987] is used to obtain the Laplace-Stieltjes transform (LST) of the job completion time. In the numerical experiments, we introduce four types of aging behavior of VMM. The effectiveness of VMM rejuvenation on job completion time is discussed in association with the type of interruption it causes and the VMM aging type. With our parameter settings, VMM rejuvenation with prs job interruption improves the performance of job execution regardless of the aging type, with performance degradation is taken into account.

A number of studies have reported the phenomenon of “Software aging”, caused by resource exhaustion and characterized by progressive software performance degradation. In this article, we carry out an experimental study of software aging and rejuvenation for an on-line bookstore application, following the standard configuration of TPC-W benchmark. While real website is used for the bookstore, the clients are emulated. In order to reduce the time to application failures caused by memory leaks, we use the accelerated life testing (ALT) approach. We then select the Weibull time to failure distribution at normal level, to be used in a semi-Markov process, to compute the optimal software rejuvenation trigger interval. Since the validation of optimal rejuvenation trigger interval with emulated browsers will take an inordinate long time, we develop a simulation model to validate the ALT experimental results, and also estimate the steady-state availability to cross-validate the results of the semi-Markov availability model.

IEEE 1609.4 protocol defines a channel switching mechanism to enable a single radio operating efficiently on multiple channels to support both safety and non-safety services. Basic safety message (BSM) is transmitted only through the control channel at regular intervals. In this paper, we propose an analytic model based on interacting semi-Markov process (SMP) to evaluate both Medium Access Control (MAC) and application level performance and reliability of safety message broadcasting incorporating the impact of multi-channel operations. Message service time distribution is derived using Laplace-Stieltjes transform based on the proposed model. Due to the cyclic interactions between the SMP models for vehicles contending the same channel, fixed-point iteration is used to obtain converged solutions. Subsequently, MAC and application-level performance and reliability metrics are derived based on the converged solutions. Channel fading with path loss is taken into consideration in this derivation. The analytic models are validated through extensive simulations in NS2 to verify the effectiveness and accuracy of our proposed fixed-point iteration based model decomposition. The effects of channel switching mechanism and channel fading are also evaluated by comparing with other analytic models.

In a large Infrastructure-as-a-Service (IaaS) cloud, component failures are quite common. Such failures may lead to occasional system downtime and eventual violation of Service Level Agreements (SLAs) on the cloud service availability. The availability analysis of the underlying infrastructure is useful to the service provider to design a system capable of providing a defined SLA, as well as to evaluate the capabilities of an existing one. This paper presents a scalable, stochastic model-driven approach to quantify the availability of a large-scale IaaS cloud, where failures are typically dealt with through migration of physical machines among three pools: hot (running), warm (turned on, but not ready), and cold (turned off). Since monolithic models do not scale for large systems, we use an interacting Markov chain based approach to demonstrate the reduction in the complexity of analysis and the solution time. The three pools are modeled by interacting sub-models. Dependencies among them are resolved using fixed-point iteration, for which existence of a solution is proved. The analytic-numeric solutions obtained from the proposed approach and from the monolithic model are compared. We show that the errors introduced by interacting sub-models are insignificant and that our approach can handle very large size IaaS clouds. The simulative solution is also considered for the proposed model, and solution time of the methods are compared.

In modern IT systems, data backup and restore operations are essential for providing protection against data loss from both natural and man-made incidents. On the other hand, data backup and restore operations can be resource-intensive and lead to performance degradation, or may require the system to be offline entirely. Therefore, it is important to properly choose backup and restore techniques and policies to ensure adequate data protection while minimizing the impact on system availability and performance. In this paper, we present an analytical modeling approach for such a purpose. We study a file service system that undergoes periodic data backups, and investigate metrics concerning system availability, data loss and rejection of user requests. To obtain the metrics, we combine a variety of model types, including Markov chains, queuing networks and Stochastic Reward Nets, to construct a set of analytical models that capture the operational details of the system. We then compute the metrics of interest under different backup/restore techniques, policies, and workload scenarios. The numerical results allow us to compare the effects of different backup/restore techniques and policies in terms of the tradeoff between protective power and impact on system performance and availability.

Failures due to software aging are typically caused by resource exhaustion, which is often preceded by progressive software performance degradation. Response time as a customer-affecting metric can thus be used to detect the onset of software aging. In this paper, we propose the distribution-based rejuvenation algorithm (DBRA), which uses a validated M/E2/1/K queuing model of the Apache HTTP server to decide when to trigger rejuvenation. We compare the performance of the DBRA with the one of the static rejuvenation algorithm with averaging (SRAA) presented by Avritzer et al. Simulation results show the effectiveness of the DBRA and its advantages over the SRAA in reducing the average response time. However, the DBRA generally tends to trigger rejuvenation more frequently than the SRAA, which increases the request blocking probability.

From an enterprise perspective, one key motivation to transform the traditional IT management into Cloud is the cost reduction of the hosted services. In an Infrastructure-as-a-Service (IaaS) Cloud, virtual machine (VM) instances share the physical machines (PMs) in the provider's data center. With large number of PMs, providers can maintain low cost of service downtime at the expense of higher infrastructure and other operational costs (e.g., power consumption and cooling costs). Hence, determining the optimal PM capacity requirements that minimize the overall cost is of interest. In this paper, we show how a cost analysis and optimization framework can be developed using stochastic availability and performance models of an IaaS Cloud. Specifically, we study two cost minimization problems to address the capacity planning in an IaaS Cloud: (1) what is the optimal number of PMs that minimizes the total cost of ownership for a given downtime requirement set by service level agreements? and, (2) is it more economical to use cheaper but less reliable PMs or to use costlier but more reliable PMs for insuring the same availability characteristics? We use simulated annealing, a well-known stochastic search algorithm, to solve these optimization problems. Results from our analysis show that the optimal solutions are found within reasonable time.

Faults in software systems can have different characteristics. In an earlier paper, the anomaly reports for a number of JPL/NASA missions were analyzed and the underlying faults were classified as Bohrbugs, non-aging-related Mandelbugs, and aging-related bugs. In another paper the times to failure for each of these fault types were examined to identify trends within missions as well as across the missions. The results of those papers are now starting to provide guidance to improve the dependability of space mission software. Just as there are different types of faults, there are different kinds of mitigations of faults and failures. This paper analyzes the mitigations associated with each fault studied in our previous papers. We identify trends of mitigation type proportions within missions as well as from mission to mission. We also look for relationships between fault types and mitigation types. The results will be used to increase the reliability of space mission software.

Understanding the bugs in software platforms is extremely valuable for developers, especially during the testing phase. However, this is a rarely investigated issue for open source Cloud platforms till date. In this paper, we present the analysis of 146 bug reports from Apache Virtual Computing Lab, a representative open source Cloud platform. Analysis is performed by means of an empirical approach tailored to open source Clouds. For VCL development and test teams, these results provide useful guidelines, e.g., directing volunteers' effort to components where more residual bugs are expected to be found.

Continuous or high availability is a key requirement for many modern IT systems. Computer operating systems play an important role in IT systems availability. Due to the complexity of their architecture, they are prone to suffer failures due to several types of software faults. Software aging causes a nonnegligible fraction of these failures. It leads to an accumulation of errors with time, increasing the system failure rate. This phenomenon can be accompanied by performance degradation and eventually system hang or even crash. As a countermeasure, software rejuvenation entails stopping the system, cleaning its internal state, and resuming its operation. This process usually incurs downtime. For an operating system, the downtime impacts any application running on top of it. Several solutions have been developed to speed up the boot time of operating systems in order to reduce the downtime overhead. We present a study of two fast OS reboot techniques for rejuvenation of Linux-based operating systems, namely Kexec and Phase-based reboot. The study measures the performance penalty they introduce and the gain in reduction of downtime overhead. The results reveal that the Kexec and Phase-based reboot have no statistically significant impact in terms of performance penalty from the user perspective. However, they may require extra resource (e.g., CPU) usage. The downtime overhead reduction, compared with normal Linux and VM reboots, is 77% and 79% in Kexec and Phase-based reboot, respectively.

With software systems becoming increasingly large and complex, many difficulties in coping with software bugs arise for developers. Despite good development practices, thorough testing, and proper maintenance policies, a non-negligible number of bugs remain in the released software. Understanding the type of residual bugs is fundamental for adopting proper countermeasures in current and future software releases. Depending on the fault triggering conditions that lead to a failure, developers can introduce fault-tolerance mechanisms and plan verification and validation strategies. In this paper, we analyze bugs in four large open-source software systems during their lifecycle, based on the concept of fault triggers. We first investigate how the type of system affects the bug type proportions, and their evolution over years. Then, an analysis of bug subtypes is performed, so as to better understand their nature, followed by a comparison with respect to attributes such as their average time to fix and severity.

Smart grids are fostering a paradigm shift in the realm of power distribution systems. Whereas traditionally different components of the power distribution system have been provided and analyzed by different teams, smart grids require a unified and holistic approach taking into consideration the interplay of distributed generation, distribution automation topology, intelligent features, and others. In this paper, we use transient survivability metrics to create better distribution automation network designs. Our approach combines survivability analysis and power flow analysis to assess the survivability of the distribution power grid network. Additionally, we present an initial approach to automatically optimize available investment decisions with respect to survivability and investment costs. We have evaluated the feasibility of this approach by applying it to the design of a real distribution automation circuit. Our empirical results indicate that the combination of survivability analysis and power flow can provide meaningful investment decision support for power systems engineers.

This paper develops a new analytic model for the performance and reliability analysis of safety-related message broadcast in vehicular ad hoc networks (VANETs) at rural intersections. First, a semi-Markov process (SMP) model for characterizing channel behavior of IEEE 802.11 based VANET is deployed to interact with the M/G/1 queue through fixed-point iteration. Then, the mean transmission delay between two nodes is derived. Furthermore, given two communicating nodes placed at the same intersection, the node reception probability that a node successfully receives the broadcast message from a sending node is computed. Consequently, the packet reception ratios are derived through integration of the node reception probabilities over the intended range of the sending node. The analytical model takes intersection geometry, IEEE 802.11 backoff counter process, hidden terminal problem, and non-saturated message arrival into account. From the obtained numerical results under various network parameters, the new model is validated and new observations are obtained.

In this paper, we propose an accurate and efficient analytic model to evaluate the impact of channel fading on multi-hop safety message disseminations in vehicular ad hoc networks (VANET). A multi-hop relay strategy is also proposed by setting distance-based timers (the longer the distance, the shorter the timer) so that the farther receiver has the higher priority for it to rebroadcast the message. Important performance and reliability metrics are derived and analyzed for a thorough understanding of the safety message transmission behavior. Extensive simulations are conducted in Matlab to verify the correctness of our proposed model under realistic network parameter settings.

To support both safety and non-safety applications in vehicular communications, IEEE 1609.4 protocol defines a channel switching mechanism to enable a single radio to operate efficiently on multiple channels. Basic safety message is transmitted only through control channel at regular intervals. In this paper, an analytic model based on semi-Markov process is proposed to evaluate MAC level performance and reliability of safety message dissemination incorporating the impact of the multi- channel operations. Safety message service time distribution is derived using Laplace-Stieltjes transform based on the proposed model. Subsequently, fixed-point iteration is used to obtain converged solutions. MAC level performance metrics are then derived. Channel fading with path loss is taken into account in this derivation. The analytic models are validated through simulations in NS2 to verify the effectiveness and accuracy of the proposed model.

Smart grids are fostering a paradigm shift in the realm of power distribution systems. Whereas traditionally different components of the power distribution system have been provided and analyzed by different teams through different lenses, smart grids require a unified and holistic approach that takes into consideration the interplay of communication reliability, energy backup, distribution automation topology, energy storage and intelligent features such as automated failure detection, isolation and restoration (FDIR) and demand response.

In this paper, an analytic model is proposed for the performance evaluation of vehicular safety related services in the dedicated short range communications (DSRC) system on highways. The generation and service of safety messages in each vehicle is modeled by a generalized M/G/1 queue. The overall model is a set of interacting M/G/1 queues, one queue for each vehicle. The interaction is that the server is shared as it is the contention medium. To make the model scalable, we use semi-Markov process (SMP) model to capture the shared server's behavior from one tagged vehicle's perspective, where the medium contention and back off behavior for this vehicle and influences from other vehicles are considered. Furthermore, this SMP interacts with the tagged vehicle's own M/G/1 queue through fixed-point iteration. The proof for the existence, uniqueness and convergence of the fixed point is provided. Based on the fixed-point solution, performance indices including mean transmission delay, packet delivery ratio (PDR), and packet reception ratio (PRR) are derived. Analytic-numeric results are verified through extensive simulations under various network parameters. Compared with the existing models, the proposed SMP model facilitates the impact analysis of hidden terminal problem on the PDR and PRR computation in a more precise manner.

This special issue deals with open problems related to Cloud computing assessment, and the interest raised in the scientific community is confirmed by the high quality of the papers received, which were selected after a review process started on July 2012 and ended on February 2013. Some relevant numbers are: 43 total submissions, nine papers accepted (approximately 0.2 acceptance ratio) after three rounds of reviews by more than 190 reviewers involved in the process. We would like to thank the authors of all the submitted papers for the high quality of their scientific contributions, and the prompt and timely reaction to the continual requests from the editors. We also thank all reviewers for their dedication and timeless efforts, which allowed us to select very high quality papers and respect the strict deadlines we have imposed. Different nonfunctional properties are considered in the special issue, mainly investigating Clouds behavior from the different perspectives of security and performance. For this reason we decided to split the special issue into two parts: the first that deals with security-related aspects (part I), and the second related to performance aspects (part II) of Cloud systems. Part I of this special issue addresses security aspects of Cloud computing such as trustworthiness, privacy, security vulnerabilities, countermeasures and threats to both physical (hardware) and logical (software, applications, data) architecture and infrastructure.

The articles in this special section focus on the measuremnet and analysis of cloud computing applications.

The optimal rate of periodic preventive maintenance to achieve the best availability is studied for Markov systems with multiple degraded operational stages, where the time-to-failure has a hypo-exponential distribution. An analytical expression is developed for the availability of such systems havingnoperational stages, and a necessary and sufficient condition is derived for a non-trivial optimal rate of periodic maintenance to exist. Numerical procedures for finding the optimal rate of periodic maintenance are given, and examples are presented.

Constraints such as limited security investment cost precludes a security decision maker from implementing all possible countermeasures in a system. Existing analytical model-based security optimization strategies do not prevail for the following reasons: (i) none of these model-based methods offer a way to find optimal security solution in the absence of probability assignments to the model, (ii) methods scale badly as size of the system to model increases and (iii) some methods suffer as they use attack trees (AT) whose structure does not allow for the inclusion of countermeasures while others translate the non-state-space model (e.g., attack response tree) into a state-space model hence causing state-space explosion. In this paper, we use a novel AT paradigm called attack countermeasure tree (ACT) whose structure takes into account attacks as well as countermeasures (in the form of detection and mitigation events). We use greedy and branch and bound techniques to study several objective functions with goals such as minimizing the number of countermeasures, security investment cost in the ACT and maximizing the benefit from implementing a certain countermeasure set in the ACT under different constraints. We cast each optimization problem into an integer programming problem which also allows us to find optimal solution even in the absence of probability assignments to the model. Our method scales well for large ACTs and we compare its efficiency with other approaches.

The growing complexity of mission-critical space mission software makes it prone to suffer failures during operations. The success of space missions depends on the ability of the systems to deal with software failures, or to avoid them in the first place. In order to develop more effective mitigation techniques, it is necessary to understand the nature of the failures and the underlying software faults. Based on their characteristics, software faults can be classified into Bohrbugs, non-aging-related Mandelbugs, and aging-related bugs. Each type of fault requires different kinds of mitigation techniques. While Bohrbugs are usually easy to fix during development or testing, this is not the case for non-aging-related Mandelbugs and aging-related bugs due to their inherent complexity. Systems need mechanisms like software restart, software replication or software rejuvenation to deal with failures caused by these faults during the operational phase. In a previous study, we classified space mission flight software faults into the three above-mentioned categories based on problems reported during operations. That study concentrated on the percentages of the faults of each type and the variation of these percentages within and across different missions. This paper extends that work by exploring the nature of the times to software failure due to Bohrbugs and non-aging-related Mandelbugs for eight JPL/NASA missions. We start by applying trend tests to the times to failure to check if there is any reliability growth (or decay) for each type of failure. For those times to failure sequences with no trend, we fit distributions to the data sets and carry out goodness-of-fit tests. The results will be used to guide the development of improved operational failure mitigation techniques, thereby increasing the reliability of space mission software.

In this paper we consider the optimal design problems for two cellular networks with guard channel, and develop fast algorithms to derive the optimal number of channels in terms of both the dropping and blocking probabilities. First we examine algebraic properties of the new call blocking probability and the handoff call dropping probability for the base station system with both guard channel and mobile-assisted handoff, and give a stable optimization algorithm under three conjectures which can be numerically validated. Next, we consider an extended model for a cellular network, where the base station system with channel failure and repair are assumed. We provide the exact steady-state probabilities for the associated continuous-time Markov chain, and also develop an optimal design algorithm to determine the number of channels and guard channels simultaneously under the same conjectures.

Data backup operation is an essential part of common IT system administration to protect against data loss caused by any storage failures, human errors, or disasters. Lost data can be recovered from the backed up data if it exists. Since the backup and restore operations accrue downtime overhead or performance degradation, they have to be designed to ensure the data reliability while minimizing the performance and availability overhead. In this paper, we study the impacts of different backup policies on availability measures such as storage availability, system availability, and user-perceived availability. Backup and restore operations are designed using SysML Activity diagrams that are automatically translated into Stochastic Reward Net (SRN) to compute the availability measures. Our numerical results show the effectiveness of the combination of full backup and partial backup in terms of user-perceived data availability and data loss rate. Furthermore, the sensitivity ranking can help improve the availability measures.

ABSTRACT Attack tree (AT) is one of the widely used non‐state‐space models for security analysis. The basic formalism of AT does not take into account defense mechanisms. Defense trees (DTs) have been developed to investigate the effect of defense mechanisms using measures such as attack cost, security investment cost, return on attack (ROA), and return on investment (ROI). DT, however, places defense mechanisms only at the leaf nodes and the corresponding ROI/ROA analysis does not incorporate the probabilities of attack. In attack response tree (ART), attack and response are both captured but ART suffers from the problem of state‐space explosion, since solution of ART is obtained by means of a state‐space model. In this paper, we present a novel attack tree paradigm called attack countermeasure tree (ACT) which avoids the generation and solution of a state‐space model and takes into account attacks as well as countermeasures (in the form of detection and mitigation events). In ACT, detection and mitigation are allowed not just at the leaf node but also at the intermediate nodes while at the same time the state‐space explosion problem is avoided in its analysis. We study the consequences of incorporating countermeasures in the ACT using three case studies (ACT for BGP attack, ACT for a SCADA attack and ACT for malicious insider attacks). Copyright © 2011 John Wiley & Sons, Ltd.

Server virtualization is a technology used in many enterprise systems to reduce operation and acquisition costs, and increase the availability of their critical services. Virtualized systems may be even more complex than traditional nonvirtualized systems; thus, the quantitative assessment of system availability is even more difficult. In this paper, we propose a sensitivity analysis approach to find the parameters that deserve more attention for improving the availability of systems. Our analysis is based on Markov reward models, and suggests that host failure rate is the most important parameter when the measure of interest is the system mean time to failure. For capacity oriented availability, the failure rate of applications was found to be another major concern. The results of both analyses were cross-validated by varying each parameter in isolation, and checking the corresponding change in the measure of interest. A cost-based optimization method helps to highlight the parameter that should have higher priority in system enhancement.

High-availability assurance of server systems is becoming an important issue, since many mission-critical applications are implemented on server systems. To achieve high-availability, software rejuvenation is a practical technique to reduce unexpected downtime caused by software aging in software applications running on server systems. Although analytic models of software rejuvenation are well-studied, such analysis is not used in server system administration due to the complexity of modeling. In this paper, we present an availability modeling method for server system with software rejuvenation based on SysML that is used to describe system configurations and maintenance operations semi-formally. The proposed approach allows system administrators, who do not have expertise in availability modeling, to design and study the effects of different rejuvenation policies deployed in server systems. To show the applicability of the proposed modeling and evaluation process, a case study of a web application server is presented. We show the correctness of our modeling method by comparing the conventional models for condition-based and time-based software rejuvenation.

High availability is one of the key characteristics of Infrastructure-as-a-Service (IaaS) cloud. In this paper, we show a scalable method for availability analysis of large scale IaaS cloud using analytic models. To reduce the complexity of analysis and the solution time, we use an interacting Markov chain based approach. The construction and the solution of the Markov chains is facilitated by the use of a high-level Petri net based paradigm known as stochastic reward net (SRN). Overall solution is composed by iteration over individual SRN sub-model solutions. Dependencies among the sub-models are resolved using fixed-point iteration, for which existence of a solution is proved. We compare the solution obtained from the interacting sub-models with a monolithic model and show that errors introduced by decomposition are insignificant. Additionally, we provide closed form solutions of the sub-models and show that our approach can handle very large size IaaS clouds.

Over the last decade, research on dependable computing has undergone a shift from reactive towards proactive methods: In classical fault tolerance a system reacts to errors or component failures in order to prevent them from turning into system failures, and maintenance follows fixed, time-based plans. However, due to an ever increasing system complexity, use of commercial-off-the-shelf components, virtualization, ongoing system patches and updates and dynamicity such approaches have become difficult to apply. Therefore, a new area in dependability research has emerged focusing on proactive approaches that start acting before a problem arises in order to increase time-to-failure and/or reduce time-to-repair. These techniques frequently build on the anticipation of upcoming problems based on runtime monitoring. Industry and academia use several terms for such techniques, each focusing on different aspects, including self-* computing, autonomic computing, proactive fault management, trustworthy computing, software rejuvenation, or preventive/proactive maintenance.

As online service providers utilize cloud computing to host their services, they are challenged by evaluating the quality of experience and designing redirection strategies in this complicated environment. We propose a hierarchical modeling approach that can easily combine all components of this environment. Identifying interactions among the components is the key to construct such models. In this particular environment, we first construct four sub-models: an outbound bandwidth model, a cloud computing availability model, a latency model and a cloud computing response time model. Then we use a redirection strategy graph to glue them together. We also introduce an all-in-one barometer to ease the evaluation. The numeric results show that our model serves as a very useful analytical tool for online service providers to evaluate cloud computing providers and design redirection strategies.

Stochastic models are often employed to study dependability of critical systems and assess various hardware and software fault-tolerance techniques. These models take into account the randomness in the events of interest (aleatory uncertainty) and are generally solved at fixed parameter values. However, the parameter values themselves are determined from a finite number of observations and hence have uncertainty associated with them (epistemic uncertainty). This paper discusses methods for computing the uncertainty in output metrics of dependability models, due to epistemic uncertainties in the model input parameters. Methods for epistemic uncertainty propagation through dependability models of varying complexity are presented with illustrative examples. The distribution, variance and expectation of model output, due to epistemic uncertainty in model input parameters are derived and analyzed to understand their limiting behavior.

A number of studies have reported the phenomenon of "Software aging", caused by resource exhaustion and characterized by progressive software performance degradation. We develop experiments that simulate an on-line bookstore application, following the standard configuration of TPC-W benchmark. We study the application failures caused by memory leaks, using the accelerated life tests method. In our experiments, the memory consumption rate is selected as the acceleration factor, and an IPL-lognormal model is used to estimate the time to failure at each acceleration level. Subsequently, the estimate of the time to failure distribution at normal condition is obtained. Our acceleration experimental results based on the IPL-lognormal model show that it can be used to greatly reduce the cost to obtain the time to failure at normal level, which can be used in scheduling software rejuvenation. Finally, we select the Weibull time to failure distribution at normal level, to be used in a semi-Markov process, to optimize the software rejuvenation trigger interval.

Several studies have been carried out on software bugs analysis and classification for life and mission critical systems, which include reproducible bugs called Bohrbugs, and hard to reproduce bugs called Mandelbugs. Although software reliability in IT systems has been studied for years, there are only a few formal analytic models for recovery from Mandelbugs. This paper discusses in detail several real cases of Mandelbugs and presents a simple flowchart which describes the recovery processes implemented in IT systems for a large variety of Mandelbugs. The flowchart is based on more than 10 IT systems that are running in production. The paper then presents a closed-form expression of the mean time to recovery from these bugs. Measures of interest including mean time to recovery and system unavailability are computed. A numerical and parametric sensitivity analysis of the model parameters are carried out. This analysis allows the designer to find out important parameter(s) for the recovery from failures due to Mandelbugs.

High-availability assurance of cloud service is a critical and challenging issue for cloud service providers. To quantify the availability of cloud services from both architectural and operational points of views, availability modeling and evaluation are essential. This paper presents a component-based availability modeling framework, named Candy, which constructs a comprehensive availability model semi-automatically from system specifications described by Systems Modeling Language (SysML). SysML diagrams are translated into components of availability model and the components are assembled together to form the entire availability model in Stochastic Reward Nets (SRNs). In order to incorporate the maintenance operations of cloud services in availability models, Candy defines the translation rules from Activity diagram to SRN and synchronizes the related SRNs according to SysML allocation notations. The feasibility of the proposed modeling and availability evaluation process is studied by an illustrative example of a web application service hosted on a cloud infrastructure having multiple failure isolation zones and automatic scale-up function.

IEEE- and ASTM-adopted Dedicated Short Range Communications (DSRC) vehicle safety-related communication services, which require reliable and fast message delivery, usually demand broadcast communications in vehicular ad hoc networks (VANETs). In this paper, we propose and justify a distributive robust scheme for DSRC one-hop safety-critical services. The new scheme enhances broadcast reliability using dynamic receiver-oriented packet repetitions and mini-slot within DIFS in IEEE 802.11 for one-hop emergency warning message dissemination. In addition, we investigate the reliability and performance of the proposed broadcast scheme for DSRC VANET safety-related services on highway analytically and by simulations. The analytic model accounts for the impact of the beacon message broadcast and the fading channel conditions on the reliability and performance.

As space mission software becomes more complex, the ability to effectively deal with faults is increasingly important. The strategies that can be employed for fighting a software bug depend on its fault type. Bohrbugs are easily isolated and removed during software testing. Mandelbugs appear to behave chaotically. While it is more difficult to detect these faults during testing, it may not be necessary to correct them; a simple retry after a failure occurrence may work. Aging-related bugs, a sub-class of Mandelbugs, can cause an increasing failure rate. For these faults, proactive techniques may prevent future failures. In this paper, we analyze the faults discovered in the on-board software for 18 JPL/NASA space missions. We present the proportions of the various fault types and study how they have evolved over time. Moreover, we examine whether or not the fault type and attributes such as the failure effect are independent.

Proactive approaches to failure avoidance, recovery and maintenance have recently attracted increased interest among researchers and practitioners from various areas of dependable system design and operation. This first workshop provided a stimulating, and fruitful forum to foster collaboration among researchers working on proactive fault management, to discuss ideas, exchange experiences and to find new answers to the overall challenge of significantly improving system dependability in contemporary computing and communication systems.

Software aging is a phenomenon defined as the continuing degradation of software systems during runtime, being particularly noticeable in long-running applications. Aging-related failures are very difficult to observe, because the accumulation of aging effects usually requires a long-term execution. Thus, collecting a statistically significant sample of times to aging-related failures so as to estimate the system's lifetime distribution is a very hard task. This is an important problem that prevents many experimental and analytical studies, mainly those focused on modeling of software aging aspects, of using representative parameter values. In this paper we propose and evaluate the use of quantitative accelerated life tests (QALT) to reduce the time to obtain the lifetime distribution of systems that fail due to software aging. Since QALT was developed for hardware failures, in this paper, we adapt it to software aging experiments. We test the proposed approach experimentally, estimating the lifetime distribution of a real web server system. The accuracy of the estimated distribution is evaluated by comparing its reliability estimates with a sample of failure times observed from the real system under test. The mean time to failure calculated from the real sample falls inside the 90% confidence interval constructed from the estimated lifetime distribution, demonstrating the high accuracy of the estimated model. The proposed approach reduces the time required to obtain the failure times by a factor of seven, for the real system investigated.

Defects per million (DPM), defined as the number of calls out of a million dropped due to failures, is an important service (un)reliability measure for telecommunication systems. Most previous research derives the DPM from steady-state system availability model. In this paper, we develop a novel method for DPM computation which takes into consideration not only system availability, but also the impact of service application as well as the transient behavior of failure recovery. We illustrate this approach using a real system which is the IBM SIP SLEE cluster. Our method takes into account software/hardware failures, different stages of recovery, different phases of call flow, retry attempts and the interactions between call flow and failure/recovery behavior.

Handling diverse client demands and managing unexpected failures without degrading performance are two key promises of a cloud delivered service. However, evaluation of a cloud service quality becomes difficult as the scale and complexity of a cloud system increases. In a cloud environment, service request from a user goes through a variety of provider specific processing steps from the instant it is submitted until the service is fully delivered. Measurement-based evaluation of cloud service quality is expensive especially if many configurations, workload scenarios, and management methods are to be analyzed. To overcome these difficulties, in this paper we propose a general analytic model based approach for an end-to-end perform ability analysis of a cloud service. We illustrate our approach using Infrastructure-as-a-Service (IaaS) cloud, where service availability and provisioning response delays are two key QoS metrics. A novelty of our approach is in reducing the complexity of analysis by dividing the overall model into sub-models and then obtaining the overall solution by iteration over individual sub-model solutions. In contrast to a single one-level monolithic model, our approach yields a high fidelity model that is tractable and scalable. Our approach and underlying models can be readily extended to other types of cloud services and are applicable to public, private and hybrid clouds.

Prior to field deployment, mission critical sensor networks should be analyzed for high reliability assurance. Past research only focused on reliability models for sensor node or network in isolation. This paper presents a comprehensive approach for reliability analysis of a cluster-based sensor network. We use a three-level hierarchical model for sensor networks using fault trees and use Markov chains at the bottom level to model the reliability of individual sensor nodes. We summarize the developed models, showcase the initial numerical results and outline the future avenues of research in the following sections.

In this paper, we discuss a Monte Carlo sampling based method for propagating the epistemic uncertainty in model parameters, through the system availability model. We also outline methods to compute the number of samples needed to obtain a desired confidence interval for various scenarios. We illustrate this method with a real system example and discuss the results obtained. While our example discusses confidence interval for system availability, this method can be directly applied to compute uncertainty for other dependability, performance and perform ability measures, computed by solving stochastic analytic models. We also emphasize the fact that no simulation is carried out in our method but a repeated sampling is performed over the parameter space followed by the execution of the analytic model with the final phase being the statistical analysis of the output vector.

Cloud based services may experience changes - internal, external, large, small - at any time. Predicting and quantifying the effects on the quality-of-service during and after a change are important in the resiliency assessment of a cloud based service. In this paper, we quantify the resiliency of infrastructure-as-a-service (IaaS) cloud when subject to changes in demand and available capacity. Using a stochastic reward net based model for provisioning and servicing requests in a IaaS cloud, we quantify the resiliency of IaaS cloud w.r.t. two key performance measures - job rejection rate and provisioning response delay.

A distinct characteristic of multistate systems (MSS) is that the systems and/or their components may exhibit multiple performance levels (or states) varying from perfect operation to complete failure. MSS can model behaviors such as shared loads, performance degradation, imperfect fault coverage, standby redundancy, limited repair resources, and limited link capacities. The nonbinary state property of MSS and their components as well as dependencies existing among different states of the same component make the analysis of MSS difficult. This paper proposes efficient algorithms for analyzing MSS using multivalued decision diagrams (MDD). Various reliability, availability, and performability measures based on state probabilities or failure frequencies are considered. The application and advantages of the proposed algorithms are demonstrated through two examples. Furthermore, experimental results on a set of benchmark examples are presented to illustrate the advantages of the proposed MDD-based method for the performability analysis of MSS, as compared to the existing methods.

In the past ten years, the software aging phenomenon has been systematically researched, and recognized by both academic, and industry communities as an important obstacle to achieving dependable software systems. One of its main effects is the depletion of operating system resources, causing system performance degradation or crash/hang failures in running applications. When conducting experimental studies to evaluate the operational reliability of systems suffering from software aging, long periods of runtime are required to observe system failures. Focusing on this problem, we present a systematic approach to accelerate the software aging manifestation to reduce the experimentation time, and to estimate the lifetime distribution of the investigated system. First, we introduce the concept of ¿aging factor¿ that offers a fine control of the aging effects at the experimental level. The aging factors are estimated via sensitivity analyses based on the statistical design of experiments. Aging factors are then used together with the method of accelerated degradation test to estimate the lifetime distribution of the system under test at various stress levels. This approach requires us to estimate a relationship model between stress levels and aging degradation. Such models are called stress-accelerated aging relationships. Finally, the estimated relationship models enable us to estimate the lifetime distribution under use condition. The proposed approach is used in estimating the lifetime distribution of a web server with software aging symptoms. The main result is the reduction of the experimental time by a factor close to 685 in comparison with experiments executed without the use of our technique.

With software systems increasingly being employed in critical contexts, assuring high reliability levels for large, complex systems can incur huge verification costs. Existing standards usually assign predefined risk levels to components in the design phase, to provide some guidelines for the verification. It is a rough-grained assignment that does not consider the costs and does not provide sufficient modeling basis to let engineers quantitatively optimize resources usage. Software reliability allocation models partially address such issues, but they usually make so many assumptions on the input parameters that their application is difficult in practice. In this paper, we try to reduce this gap, proposing a reliability and testing resources allocation model that is able to provide solutions at various levels of detail, depending upon the information the engineer has about the system. The model aims to quantitatively identify the most critical components of software architecture in order to best assign the testing resources to them. A tool for the solution of the model is also developed. The model is applied to an empirical case study, a program developed for the European Space Agency, to verify model's prediction abilities and evaluate the impact of the parameter estimation errors on the prediction accuracy.

OSPF is a popular interior gateway routing protocol. Commercial OSPF routers limit their processing load by using a hold time between successive routing table calculations as new link state advertisements (LSAs) arrive following a topology change. A large hold time value limits the frequency of routing table calculations but also causes large delays in convergence to the topology change. Hence, commercial routers now use an exponential back off scheme, where the hold time is initially set to a small value that is expected to rapidly increase, and hence limit the frequency of routing table calculations, in face of continuous LSA arrivals. In this paper, we analyze the ability of different hold time schemes to limit the frequency of routing table calculations under continuous LSA arrivals starting with a small value for the hold time. This analysis is performed using Markov regenerative process based stochastic models as well as simulations using an extensively modified OSPFD simulator.

Proactive approaches to failure avoidance, recovery and maintenance have recently attracted increased interest among researchers and practitioners from various areas of dependable system design and operation. This first workshop aimed to provide a stimulating, and fruitful forum to foster collaboration among researchers working on proactive fault management, to discuss ideas, exchange experiences and to find new answers to the overall challenge of significantly improving system dependability in contemporary computing and communication systems.

The term resilience is used differently by different communities. In general engineering systems, fast recovery from a degraded system state is often termed as resilience. Computer networking community defines it as the combination of trustworthiness (dependability, security, performability) and tolerance (survivability, disruption tolerance, and traffic tolerance). Dependable computing community defined resilience as the persistence of service delivery that can justifiably be trusted, when facing changes. In this paper, resilience definitions of systems and networks will be presented. Metrics for resilience will be compared with dependability metrics such as availability, performance, performability. Simple examples will be used to show quantification of resilience via probabilistic analytic models.

This paper develops an availability model of a virtualized system. We construct non-virtualized and virtualized two hosts system models using a two-level hierarchical approach in which fault trees are used in the upper level and homogeneous continuous time Markov chains (CTMC) are used to represent sub-models in lower level. In the models, we incorporate not only hardware failures (e.g., CPU, memory, power, etc) but also software failures including Virtual Machine Monitor (VMM), Virtual Machine (VM), and application failures. We also incorporate high availability (HA) service and VM live migration in the virtualized system. Metrics we use are system steady state availability, downtime in minutes per year and capacity oriented availability.

Our society is heavily dependent on a wide variety of communication services. These services must be available even when undesirable events like sabotage, natural disasters, or network failures happen. The network survivability as defined by the ANSI T1A1.2 committee is the transient performance from the instant an undesirable event occurs until steady state with an acceptable performance level is attained. In this paper we assess the survivability of a network with virtual connections exposed to link or node failures. We have developed both simulation and analytic models to cross validate our assumptions. In order to avoid state space explosion while addressing large networks we decompose our models first in space by studying the nodes independently and then in time by decoupling our analytic performance and recovery models which gives us a closed form solution. The modeling approaches are applied to two network examples. The results show very good correspondence between the transient loss and delay performance in our simulations and in the analytic approximations.

Design of reliable systems meeting stringent quality, reliability, and availability requirements is becoming increasingly difficult in advanced technologies. The current design paradigm, which assumes that no gate or interconnect will ever operate incorrectly within the lifetime of a product, must change to cope with this situation. Future systems must be designed with built-in mechanisms for failure tolerance, prediction, detection and recovery during normal system operation. This tutorial will focus on models and metrics for designing reliable systems, algorithms and tools for modeling and evaluating such systems, will discuss a broad spectrum of techniques for building such systems with support for concurrent error detection, failure prediction, error correction, recovery, and self-repair. Complex interplay between power, performance and reliability requirements in future systems, and associated constraints will also be discussed.

We discuss availability aspects of large software- based systems. We classify faults into Bohrbugs, Mandelbugs and aging-related bugs, then examine mitigation methods for the last two bug types. We also consider quantitative approaches to availability assurance.

We present the availability model of a high availability SIP Application Server configuration on WebSphere. Hardware,operating system and application server failures are considered. Different types of fault detectors, detection delays,failover delays, restarts, reboots and repairs are considered.Imperfect coverages for detection, failover and recovery are incorporated. Computations are based on a set of interacting sub-models of all system components capturing their failure and recovery behavior. The parameter values used in the calculations are based on several sources,including field data, high availability testing, and agreed upon assumptions. In cases where a parameter value is uncertain,due to assumptions or limited test data, a sensitivity analysis of that parameter has been provided. Our analysis indicates the failure types and recovery parameters that are most critical in their impact on overall system availability. These results will help guide system improvement efforts throughout future releases of these products.

In this paper, we present a variational Bayesian (VB) approach to computing the interval estimates for nonhomogeneous Poisson process (NHPP) software reliability models. This approach is an approximate method that can produce analytically tractable posterior distributions. We present simple iterative algorithms to compute the approximate posterior distributions for the parameters of the gamma-type NHPP-based software reliability model using either individual failure time data or grouped data. In numerical examples, the accuracy of this VB approach is compared with the interval estimates based on conventional Bayesian approaches, i.e., Laplace approximation, Markov chain Monte Carlo (MCMC) method, and numerical integration. The proposed VB approach provides almost the same accuracy as MCMC, while its computational burden is much lower.

Grid computing is a newly emerging technology aimed at large-scale resource sharing and global-area collaboration. It is the next step in the evolution of parallel and distributed computing. Due to the largeness and complexity of the grid system, its performance and reliability are difficult to model, analyze, and evaluate. This paper presents a model that relaxes some assumptions made in prior research on distributed systems that were inappropriate for grid computing. The paper proposes a virtual tree-structured model of the grid service. This model simplifies the physical structure of a grid service, allows service performance (execution time) to be efficiently evaluated, and takes into account data dependence and failure correlation. Based on the model, an algorithm for evaluating the grid service time distribution and the service reliability indices is suggested. The algorithm is based on Graph theory and probability theory. Illustrative examples and a real case study of the BioGrid are presented.

Recently, measurement-based studies of software systems have proliferated, reflecting an increasingly empirical focus on system availability, reliability, aging, and fault tolerance. However, it is a nontrivial, error-prone, arduous, and time-consuming task even for experienced system administrators, and statistical analysts to know what a reasonable set of steps should include to model, and successfully predict performance variables, or system failures of a complex software system. Reported results are fragmented, and focus on applying statistical regression techniques to monitored numerical system data. In this paper, we propose a best practice guide for building empirical models based on our experience with forecasting Apache web server performance variables, and forecasting call availability of a real-world telecommunication system. To substantiate the presented guide, and to demonstrate our approach in a step by step manner, we model, and predict the response time, and the amount of free physical memory of an Apache web server system, as well as the call availability of an industrial telecommunication system. Additionally, we present concrete results for a) variable selection where we cross benchmark three procedures, b) empirical model building where we cross benchmark four techniques, and c) sensitivity analysis. This best practice guide intends to assist in configuring modeling approaches systematically for best estimation, and prediction results.

This paper proposes a hierarchical modeling approach for the reliability analysis of phased-mission systems with repairable components. The components at the lower level are described by continuous time Markov chains which allow complex component failure/repair behaviors to be modeled. At the upper level, there is a combinatorial model whose structure function is represented by a binary decision diagram (BDD). Two BDD ordering strategies, and consequently two evaluation algorithms, are proposed to compute the phased-mission system (PMS) reliability based on Markov models for components, and a BDD representation of system structure function. The performance of the two evaluation algorithms is compared. One algorithm generates a smaller BDD, while the other has shorter execution time. Several examples, and experiments are presented in the paper to illustrate the application, and the advantages of our approach.

Performance engineering is an important activity for software architects and designers. Assessment and tuning of performance can help to make key changes in the system, especially if done early in its development. In this paper, we present a tool for the performance assessment and tuning for systems following the tiered architecture, which is a very commonly used architecture style. The Web-based tool allows a software designer to specify the system under design and ascertain the different performance attributes as well as the variation in performance with load. If the predicted performance is not satisfactory, the tool helps the designer with ascertaining the changes that need to be done for achieving the desired performance. Using an iterative analysis, it presents the designer with detailed steps in terms of improvements at the software and the hardware level that are necessary to improve the system performance to the desired level. We present an overview of the analysis and tuning approach, along with an example to illustrate the use of the tool

We present three algorithms for detecting the need for software rejuvenation by monitoring the changing values of a customer-affecting performance metric, such as response time. Applying these algorithms can improve the values of this customer-affecting metric by triggering rejuvenation before performance degradation becomes severe. The algorithms differ in the way they gather and use sample values to arrive at a rejuvenation decision. Their effectiveness is evaluated for different sets of control parameters, including sample size, using simulation. The results show that applying the algorithms with suitable choices of control parameters can significantly improve system performance as measured by the response time

High reliability and performance are vital for software systems handling diverse mission critical applications. Such software systems are usually component based and may possess multiple levels of fault recovery. A number of parameters, including the software architecture, behavior of individual components, underlying hardware, and the fault recovery measures, affect the behavior of such systems, and there is a need for an approach to study them. In this paper we present an integrated approach for modeling and analysis of component based systems with multiple levels of failures and fault recovery both at the software, as well as the hardware level. The approach is useful to analyze attributes such as overall reliability, performance, and machine availabilities for such systems, wherein failures may happen at the software components, the operating system, or at the hardware, and corresponding restarts, retries, reboots or repairs are used for mitigation. Our approach encompasses Markov chain, and queueing network modeling, for estimating system reliability, machine availabilities and performance. The approach is helpful for designing and building better systems and also while improving existing systems

Recently, measurement based studies of software systems proliferated, reflecting an increasingly empirical focus on system availability, reliability, aging and fault tolerance. However, it is a non-trivial, error-prone, arduous, and time-consuming task even for experienced system administrators and statistical analysis to know what a reasonable set of steps should include to model and successfully predict performance variables or system failures of a complex software system. Reported results are fragmented and focus on applying statistical regression techniques to captured numerical system data. In this paper, we propose a best practice guide for building empirical models based on our experience with forecasting Apache Web server performance variables and forecasting call availability of a real world telecommunication system. To substantiate the presented guide and to demonstrate our approach step-by-step we model and predict the response time and the amount of free physical memory of an Apache Web server system. Additionally, we present concrete results for a) variable selection where we cross benchmark three procedures, b) empirical model building where we cross benchmark four techniques and c) sensitivity analysis. This best practice guide intends to assist in configuring modeling approaches systematically for best estimation and prediction results

Carrier grade high availability platforms are designed to enable the development and deployment of highly available services in the telecommunications industry. In order to build-in high availability and compare availabilities that differ in the sixth decimal place during the design phase, fairly detailed stochastic models are needed to evaluate the design and perform design tradeoffs. This paper describes an availability model for a high availability platform using three-level hierarchical decomposition that mixes reliability block diagrams and Markov chains. The model is built and evaluated using the SHARPS software package. Sensitivity analysis is performed to identify the effects of critical parameters

A large number of software reliability growth models have been proposed to analyse the reliability of a software application based on the failure data collected during the testing phase of the application. To ensure analytical tractability, most of these models are based on simplifying assumptions of instantaneous & perfect debugging. As a result, the estimates of the residual number of faults, failure rate, reliability, and optimal software release time obtained from these models tend to be optimistic. To obtain realistic estimates, it is desirable that the assumptions of instantaneous & perfect debugging be amended. In this paper we discuss the various policies according to which debugging may be conducted. We then describe a rate-based simulation framework to incorporate explicit debugging activities, which may be conducted according to the different debugging policies, into software reliability growth models. The simulation framework can also consider the possibility of imperfect debugging in conjunction with any of the debugging policies. Further, we also present a technique to compute the failure rate, and the reliability of the software, taking into consideration explicit debugging. An economic cost model to determine the optimal software release time in the presence of debugging activities is also described. We illustrate the potential of the simulation framework using two case studies.

Traditional approaches to software reliability modeling are black box-based; that is, the software system is considered as a whole, and only its interactions with the outside world are modeled without looking into its internal structure. The black box approach is adequate to characterize the reliability of monolithic, custom, built-to-specification software applications. However, with the widespread use of object oriented systems design & development, the use of component-based software development is on the rise. Software systems are developed in a heterogeneous (multiple teams in different environments) fashion, and hence it may be inappropriate to model the overall failure process of such systems using one of the several software reliability growth models (black box approach). Predicting the reliability of a software system based on its architecture, and the failure behavior of its components, is thus essential. Most of the research efforts in predicting the reliability of a software system based on its architecture have been focused on developing analytical or state-based models. However, the development of state-based models has been mostly ad hoc with little or no effort devoted towards establishing a unifying framework which compares & contrasts these models. Also, to the best of our knowledge, no attempt has been made to offer an insight into how these models might be applied to real software applications. This paper proposes a unifying framework for state-based models for architecture-based software reliability prediction. The state-based models we consider are the ones in which application architecture is represented either as a discrete time Markov chain (DTMC), or a continuous time Markov chain (CTMC). We illustrate the DTMC-based, and CTMC-based models using examples. A detailed discussion of how the parameters of each model may be estimated, and the life cycle phases when the model may be applied is also provided

Several recent studies have reported & examined the phenomenon that long-running software systems show an increasing failure rate and/or a progressive degradation of their performance. Causes of this phenomenon, which has been referred to as “software aging”, are the accumulation of internal error conditions, and the depletion of operating system resources. A proactive technique called “software rejuvenation” has been proposed as a way to counteract software aging. It involves occasionally terminating the software application, cleaning its internal state and/or its environment, and then restarting it. Due to the costs incurred by software rejuvenation, an important question is when to schedule this action. While periodic rejuvenation at constant time intervals is straightforward to implement, it may not yield the best results. The rate at which software ages is usually not constant, but it depends on the time-varying system workload. Software rejuvenation should therefore be planned & initiated in the face of the actual system behavior. This requires the measurement, analysis, and prediction of system resource usage. In this paper, we study the development of resource usage in a web server while subjecting it to an artificial workload. We first collect data on several system resource usage & activity parameters. Non-parametric statistical methods are then applied toward detecting & estimating trends in the data sets. Finally, we fit time series models to the data collected. Unlike the models used previously in the research on software aging, these time series models allow for seasonal patterns, and we show how the exploitation of the seasonal variation can help in adequately predicting the future resource usage. Based on the models employed here, proactive management techniques like software rejuvenation triggered by actual measurements can be built.

In this paper, we describe three different state space models for analyzing the security of a software system. In the first part of this paper, we utilize a semi-Markov process (SMP) to model the transitions between the security states of an abstract software system. The SMP model can be solved to obtain the probability of reaching security failed states along with the meantime to security failure (MTTSF). In the second part of the paper, we use a discrete event dynamic system model of security dynamics. We show how to derive events and transitions from existing security taxonomies. We then apply theory of discrete event control to define safety properties of the computer system in terms of the basic concepts of controllability used in discrete event control for two special sublanguages K/sub s/ and K/sub v/. These languages correspond to maximally robust controllable sub-languages. In the third approach, we show that by associating cost with the state transitions, the security quantification problem can be casted as Markov decision problem (MDP). This MOP can be solved to obtain an optimal controllable language K/sub s//spl sube/K/sub v/ the gives the minimal cost safe security policy.

Many software reliability growth models assume that the time to next failure may be infinite; i.e., there is a chance that no failure will occur at all. For most software products this is too good to be true even after the testing phase. Moreover, if a non-zero probability is assigned to an infinite time to failure, metrics like the mean time to failure do not exist. In this paper, we try to answer several questions: Under what condition does a model permit an infinite time to next failure? Why do all non-homogeneous Poisson process (NHPP) models of the finite failures category share this property? And is there any transformation mending the time to failure distributions? Indeed, such a transformation exists; it leads to a new family of NHPP models. We also show how the distribution function of the time to first failure can be used for unifying finite failures and infinite failures NHPP models.

Recently, the phenomenon of software aging, one in which the state of the software system degrades with time, has been reported. This phenomenon, which may eventually lead to system performance degradation and/or crash/hang failure, is the result of exhaustion of operating system resources, data corruption, and numerical error accumulation. To counteract software aging, a technique called software rejuvenation has been proposed, which essentially involves occasionally terminating an application or a system, cleaning its internal state and/or its environment, and restarting it. Since rejuvenation incurs an overhead, an important research issue is to determine optimal times to initiate this action. In this paper, we first describe how to include faults attributed to software aging in the framework of Gray's software fault classification (deterministic and transient), and study the treatment and recovery strategies for each of the fault classes. We then construct a semi-Markov reward model based on workload and resource usage data collected from the UNIX operating system. We identify different workload states using statistical cluster analysis, estimate transition probabilities, and sojourn time distributions from the data. Corresponding to each resource, a reward function is then defined for the model based on the rate of resource depletion in each state. The model is then solved to obtain estimated times to exhaustion for each resource. The result from the semi-Markov reward model are then fed into a higher-level availability model that accounts for failure followed by reactive recovery, as well as proactive recovery. This comprehensive model is then used to derive optimal rejuvenation schedules that maximize availability or minimize downtime cost.

We present a hierarchical model for the analysis of proactive fault management in the presence of system resource leaks. At the low level of the model hierarchy is a degradation model in which we use a nonhomogeneous Markov chain to establish an explicit connection between resource leaks, and the failure rate. With the degradation model, we prove that the failure rate is asymptotically constant in the absence of resource leaks, and it is increasing as leaks occur & accumulate, which confirms the resource leaks as an aging source. The proactive fault management (PFM) is modeled at the higher level as a semi-Markov process. The PFM model takes as input the degradation analysis from the low-level model, and allows us to determine optimal rejuvenation schedules with respect to various system measures.

Mean time to failure (MTTF) is an important reliability measure. Previous research is mainly concerned with the MTTF computation of coherent systems. In this paper, we derive equations to calculate the steady-state MTTF for noncoherent systems. Based on the equations, we extend the BDD by adding an intersection edge in each BDD node to efficiently store additional information for MTTF computation of noncoherent systems. A recursive algorithm is developed for MTTF computation using the extended BDD. To accelerate building the extended BDD, a method is proposed to avoid calculating the intersection edge for some nodes by keeping node monotonicity during the BDD construction. We show the efficiency of our algorithm by applying it to some example fault trees, real-life applications, and large fault tree benchmarks.

In general, the software reliability models based on the nonhomogeneous Poisson processes (NHPPs) are quite popular to assess quantitatively the software reliability and its related dependability measures. Nevertheless, it is not so easy to select the best model from a huge number of candidates in the software testing phase, because the predictive performance of software reliability models strongly depends on the fault-detection data. The asymptotic trend of software fault-detection data can be explained by two kinds of NHPP models; finite fault model and infinite fault model. In other words, one needs to make a hypothesis whether the software contains a finite or infinite number of faults, in selecting the software reliability model in advance. In this article, we present an approach to treat both finite and infinite fault models in a unified modeling framework. By introducing an infinite server queueing model to describe the software debugging behavior, we show that it can involve representative NHPP models with a finite and an infinite number of faults. Further, we provide two parameter estimation methods for the unified NHPP based software reliability models from both standpoints of Bayesian and nonBayesian statistics. Numerical examples with real fault-detection data are devoted to compare the infinite server queueing model with the existing one under the same probability circumstance.

As the new generation high-availability commercial computer systems incorporate deferred repair service strategies, steady-state availability metrics may no longer reflect reality. Transient solution of availability models for such systems to calculate interval availability over shorter time horizon is desirable. While many solution methods for transient analysis have been proposed, how to apply these methods on hierarchical models has not been well addressed. This paper describes an approach to computing interval availability and related metrics for hierarchical Markov models. The approach divides the time interval of interest into small subintervals such that the input parameters can be treated as constants in each subinterval to make the model satisfy the homogeneous Markov property, and then pass the output interval availability metrics as constants from the sub-model to its parent model. Finally, these quantities are integrated to obtain the expected interval availability for the entire interval. The study also addresses methods of passing parameters across levels for generating multiple metrics from a hierarchical model. The approach is illustrated with an example model and has been implemented in RAScad. All computations for the example model have also been carried out using the SHARPE textual language interface.

The telecommunications industry has achieved high reliability and availability for telephone service over decades of development. However, the current design does not aim at providing service survivability when a local switching office fails due to catastrophic damage. In this paper, several survivable architectures for telephone subscriber network are proposed based on common survivability principles. In order to quantitatively assess the effectiveness of design alternatives, a set of analytical models are developed to derive various survivability measures. Numerical results are provided to show how a comprehensive understanding of the system behavior after failure can be achieved through different survivability aspects.

We analyze two software rejuvenation policies of cluster server systems under varying workload, called fixed rejuvenation and delayed rejuvenation. In order to achieve a higher average throughput, we propose the delayed rejuvenation policy, which postpones the rejuvenation of individual nodes until off-peak hours. Analytic models using the well known paradigm of Markov chains are used. Since the size of the Markov model is nontrivial, automated specification generation, and the solution via stochastic Petri nets is utilized. Deterministic time to trigger rejuvenation is approximated by a 20-stage Erlangian distribution. Based on the numerical solutions of the models, we find that under the given context, although the fixed rejuvenation occasionally yields a higher throughput, the delayed rejuvenation policy seems to outperform fixed rejuvenation policy by up to 11%. We also compare the steady-state system availabilities of these two rejuvenation policies.

The development of techniques for quantitative, model-based evaluation of computer system dependability has a long and rich history. A wide array of model-based evaluation techniques is now available, ranging from combinatorial methods, which are useful for quick, rough-cut analyses, to state-based methods, such as Markov reward models, and detailed, discrete-event simulation. The use of quantitative techniques for security evaluation is much less common, and has typically taken the form of formal analysis of small parts of an overall design, or experimental red team-based approaches. Alone, neither of these approaches is fully satisfactory, and we argue that there is much to be gained through the development of a sound model-based methodology for quantifying the security one can expect from a particular design. In this work, we survey existing model-based techniques for evaluating system dependability, and summarize how they are now being extended to evaluate system security. We find that many techniques from dependability evaluation can be applied in the security domain, but that significant challenges remain, largely due to fundamental differences between the accidental nature of the faults commonly assumed in dependability evaluation, and the intentional, human nature of cyber attacks.

In this paper, an optimal training equalization for wireless communication is proposed and analyzed. By our scheme, the training of the equalizer is carried out periodically, with the training interval optimized for a maximal channel utilization. A closed-form expression for the optimal training interval is derived via a semi-Markov process which requires the knowledge of the channel equalization failure time distribution. A statistical estimation algorithm with complexity O(n/sup 2/) is presented and applied to adaptively estimate and track the optimal interval when the failure time distribution is not available. Numerical results show that by choosing the optimal training interval, the channel utilization can be improved and the statistical estimation algorithm can effectively approach the optimal solution with a reasonable number of failure time data points. By comparing this scheme with nonperiodic training scheme and the mean time to failure (MTTF)-based heuristic scheme, we find that our scheme outperforms the nonperiodic training scheme and provides an upper bound for MTTF-heuristic scheme.

We present a framework of adaptive estimation and rejuvenation of software system performance in the presence of aging sources. The framework specifies that a degradation model not only describe an aging process but also enable the adaptation of model-based performance estimates to on-line measurements of data pertaining to the aging process. The adaptive estimation uses model-based a priori estimation and obtains a posteriori estimation based on the data measurements. With the adaptive estimation, the rejuvenation policy determines the time epochs for data collection and rejuvenation according to system dynamics. In the specific context of resource leaks previously assumed to lead to aging, we present a non-homogeneous Markov model to explicitly establish a connection between resource leaks and the failure rate. We demonstrate an increasing failure rate in the presence of resource leaks. 1. Introduction: the Adaptation Problem We present a framework for adaptive estimation and rejuvenation of software system performance in the presence of aging sources. We are concerned with system resource loss, in particular, memory leakage. Memory is indispensable in computer and communication systems. Memory leakage is a typical aging source for server systems due to software bugs in the client applications that use server resources. Our framework for adaptive estimation and rejuvenation consists of three integral components: a degradation model, an adaptive estimation scheme, and an adaptive rejuvenation scheduling policy. The degradation model allows adaptation of model-based performance estimates to on-line measurements of data pertaining to the aging process. The adaptive estimation scheme uses the model-based a priori estimation and obtains a posteriori estimation based on the measurements. With the adaptive estimation, the rejuvenation scheduling policy determines time epochs for data

The presence of physical obstacles and radio interfer-ence results in the so called “shadow regions ” in wireless networks. When a mobile station roams into a shadow re-gion, it loses its network connectivity. In cellular networks, in order to minimize the connection unreliability, careful cell planning is required to prevent the occurrance of the shadow regions in the first place. In 802.11b/g wireless LANs, however, due to the limited frequency spectrum, it is not always possible to prevent a shadow region by adding another cell at a different frequency. Our contribution in this paper is to propose the alternate approach of tolerating the existence of “shadow regions ” as opposed to prevention in order to enhance the connection dependability. A redundant access point (AP) is placed in

We propose to use Markov regenerative process (MRGP) models to study the availability of Internet-based services perceived by a web user, which capture the interactions between the service facility and the user. The necessity of the sophisticated MRGP modeling is evidenced by the comparisons with the corresponding continuous time Markov chain (CTMC) models, which show that the popular convenient CTMC models tend to overestimate user-perceived service unavailabilities by 26% to 125%. We study two different online service scenarios: (1) single-user-single-host and (2) single-user-multiple-host. It is found that user-perceived service unavailability depends not only on the infrastructure's failure-recovery characteristics but also, more importantly, on the user's behavior. Also, for a service provider, to improve users' satisfaction, inventing a fast recovery mechanism is more effective than striving for a more reliable platform given the platform availability is the same.

Software aging often affects the performance of a software system and eventually causes it to fail. A novel approach to handle transient software failures is called software rejuvenation which can be regarded as a preventive and proactive solution that is particularly useful for counteracting the phenomenon of software aging. In this paper, we consider the optimal software rejuvenation policy maximizing the interval reliability in the general semi-Markov framework. We derive analytically the optimal software rejuvenation timing which maximizes the limiting interval reliability or the interval reliability with exponentially distributed operation times. Further, we examine numerically the transient behavior of the interval reliability at an arbitrary operation time. Our results under the interval reliability criteria are extentions of some earlier work, since the interval reliability can be specialized to the pointwise availability and the common reliability function.

Real-time systems are an important class of process control systems that need to respond to events under time constraints, or deadlines. Such systems may also be required to deliver service in spite of hardware or software faults in their components. This fault-tolerant characteristic is especially critical in systems whose failure can cause economic disaster and/or loss of lives. This paper reports recent research in the area of analytical modeling of the three major characteristics of real-time systems: timeliness, dependability, and external environmental dependencies. The paper starts with a brief introduction to analytical modeling frameworks such as Markov models and stochastic petri nets. This is followed by an examination of advances in modeling response-time distributions, reliability, distributed messaging services, and software fault-tolerance in real-time systems.

A new algorithm based on binary decision diagram (BDD) for the analysis of a system with multistate components is proposed. Each state of a multistate component is represented by a boolean variable, and a multistate system is represented by a series of multistate fault trees. A Boolean algebra with restrictions on variables is used to address the dependence among these boolean variables that collectively represent the same component and a new BDD operation is proposed to realize this Boolean algebra. Due to the nature of the BDD, the sum of disjoint products (SDP) can be implicitly represented, which avoids huge storage and high computational complexity for large multistate systems. Some applications are given to illustrate the use of our new algorithm.

Telecommunication systems are large and complex, consisting of multiple intelligent modules in shelves, multiple shelves in frames, and multiple frames to compose a single network element. In the availability and performability analysis of such a complex system, combinatorial models are computationally efficient but have limited expressive power. State-based models are expressive but computationally complex. Furthermore, this complexity grows exponentially with the size of the model. This state-space explosion problem must be solved in order to model complex-systems using state-based models. The solution, in this paper, is to partition complex models into a hierarchy of submodels, to transform lower-level n-state, m-transition Markov reward models and stochastic reward nets into equivalent (with respect to their steady-state behavior) 2-state, 2-transition models, and then to back-substitute the equivalent submodels into the higher-level models. This paper also proposes a canonical form for the equivalent submodels. This technique is defined for availability models, where the state of the system is either up of down, and for performability models, where the state of the system may be up, down, or partially-up/partially-down. This paper also shows how this technique can be used to obtain common availability measures for telecommunication systems, and when to apply it to availability models and when to use it in performability models. For future work, it would be interesting to more tightly integrate this technique with modeling tools, perhaps coupled with a graphic front-end to facilitate the navigation of the model hierarchy.

The NASA Remote Exploration and Experimentation (REE) Project, managed by the Jet Propulsion Laboratory, has the vision of bringing commercial supercomputing technology into space, in a form which meets the demanding environmental requirements, to enable a new class of science investigation and discovery. Dependability goals of the REE system are 99% reliability over 5 years and 99% availability. In this paper we focus on the reliability/availability modeling and analysis of the REE system. We carry out this task using fault trees, reliability block diagrams, stochastic reward nets and hierarchical models. Our analysis helps to determine the ranges of parameters for which the REE dependability goal will be met. The analysis also allows us to assess different hardware and software fault-tolerance techniques.

We characterize a broad class C of prefetching algorithms and prove that, for any prefetching algorithm in this class, its total elapsed time is no more than twice the smallest possible total elapsed time. This result provides a performance guarantee for several practical prefetching algorithms, which fall into this class and have no previously proven performance bound. Prefetching involves making two fundamental decisions: when to begin a prefetch operation and which page to replace. Provably optimal prefetching algorithms are rendered impractical because of complicated techniques to decide when to issue prefetches. However, a class C algorithm only has to obey certain simple (previously known) guidelines governing these decisions. The performance guarantee for this class strongly relies on the optimal replacement requirement, and this suggests that more so than the decision of when to start prefetching the next missing page, the replacement decision remains the most important decision to be made in prefetching algorithms.

Quite often failures in network based services and server systems may not be accidental, but rather caused by deliberate security intrusions. We would like such systems to either completely preclude the possibility of a security intrusion or design them to be robust enough to continue functioning despite security attacks. Not only is it important to prevent or tolerate security intrusions, it is equally important to treat security as a QoS attribute at par with, if not more important than other QoS attributes such as availability and performability. This paper deals with various issues related to quantifying the security attribute of an intrusion tolerant system, such as the SITAR system. A security intrusion and the response of an intrusion tolerant system to the attack is modeled as a random process. This facilitates the use of stochastic modeling techniques to capture the attacker behavior as well as the system's response to a security intrusion. This model is used to analyze and quantify the security attributes of the system. The security quantification analysis is first carried out for steady-state behavior leading to measures like steady-state availability. By transforming this model to a model with absorbing states, we compute a security measure called the "mean time (or effort) to security failure" and also compute probabilities of security failure due to violations of different security attributes.

Discusses SHARPE, a well known package in the field of reliability and performability, used in universities as well as in companies. A modeler who is familiar with many different kinds of models, can easily choose models that best suit a particular system and the kind of measure that is needed at each stage of the design. It is also possible to use different kinds of models hierarchically for different physical or abstract levels of the system and to use different kinds of models to validate each other's results. Steady-state and transient computations are available in the tool.

Although several tools have been developed for the estimation of software reliability, they are highly specialized in the approaches they implement and the particular phase of the software life-cycle in which they are applicable. Also the conventional techniques for software reliability evaluation, which treat the software as a monolithic entity are inadequate to assess the reliability of heterogeneous systems. We present a tool called Software Reliability Estimation and Prediction Tool (SREPT) that seeks to address these limitations.

An optimal training equalization for wireless communication is proposed and analyzed. By our scheme, the training of the equalizer is carried out periodically, with the training interval optimized for a maximal channel utilization. A closed-form expression for the optimal training interval is derived via a semi-Markov process (SMP) which requires knowledge of the channel equalization failure time distribution. A statistical estimation algorithm is presented and applied to adaptively estimate and track the optimal interval when the failure time distribution is not available. Numerical results show that by choosing the optimal training interval, the channel utilization can be improved, and the statistical estimation algorithm can effectively approach the optimal solution with a reasonable number of failure time data points.

Spatial reuse protocol (SRP) is a media access control (MAC)-layer protocol that operates over a double counter-rotating ring network topology. SRP is designed to enhance the SONET network so that it can handle data traffic more efficiently. We study the all-terminal reliability of an SRP ring implementing intelligent protection switch (IPS) and enhanced intelligent protection switch (E-IPS). We calculate reliability for all scenarios under which all-terminal connectivity is maintained. By summing up the results arising from individual mutually exclusive events, all-terminal reliabilities for IPS and E-IPS are obtained. By further assuming constant and time-dependent component failure rates, mean time to failure (MTTF) and mean time to failure improvement factor (MTIF) measures are calculated. Results show that MTTF/MTIF vary as functions of network size, component reliability and coverage factor. The advantage of E-IPS over IPS is more obvious when network size is big and concentrator failure rate is small. Our analysis could be helpful to network designers who wish to determine whether the additional cost/complexity added by the E-IPS scheme is justified.

Messaging services are a useful component in distributed systems that require scalable dissemination of messages (events) from suppliers to consumers. These services decouple suppliers and consumers, and take care of client registration and message propagation, thus relieving the burden on the supplier Recently performance models for the configurable delivery and discard policies found in messaging services have been developed, that can be used to predict response time distributions and discard probabilities under failure-free conditions. However, these messaging service models do not include the effect of failures. In a distributed system, supplier, consumer and messaging services can fail independently leading to different consequences. In this paper we consider the expected loss rate associated with messaging services as a performability measure and derive approximate closed-form expressions for three different quality of service settings. These measures provide a quantitative framework that allows different messaging service configurations to be compared and design trade-off decisions to be made.

Prevalent approaches to characterize the behavior of monolithic applications are inappropriate to model modern software systems which are heterogeneous, and are built using a combination of components picked off the shelf, those developed in-house and those developed contractually. Development of techniques to characterize the behavior of such component-based software systems based on their architecture is then absolutely essential. Earlier efforts in the area of architecture-based analysis have focused on the development of composite models which are quite cumbersome due to their inherent largeness and stiffness. In this paper we develop an accurate hierarchical model to predict the performance and reliability of component-based software systems based on their architecture. This model accounts for the variance of the number of visits to each module, and thus provides predictions closer to those provided by a composite model. The approach developed in this paper enables the identification of performance and reliability bottlenecks. We also develop expressions to analyze the sensitivity of the performance and reliability predictions to the changes in the parameters of individual modules. In addition, we demonstrate how the hierarchical model could be used to assess the impact of changes in the workload on the performance and reliability of the application. We illustrate the performance and reliability prediction as well as sensitivity analysis techniques with examples.

In order to reduce system outages and the associated downtime cost caused by the "software aging" phenomenon, we propose to use software rejuvenation as a proactive system maintenance technique deployed in a CMTS (Cable Modem Termination System) cluster system. Different rejuvenation policies are studied from the perspective of cost and availability. To evaluate these policies, stochastic reward net models are developed and solved by SPNP (Stochastic Petri Net Package). Numerical results show that significant improvement in capacity-oriented availability and decrease in downtime cost can be achieved. The optimization of the rejuvenation interval in the time-based approach and the effect of the prediction coverage in the measurement-based approach are also studied in this paper.

Network survivability reflects the ability of a network to continue to function during and after failures. Our purpose in this paper is to propose a quantitative approach to evaluate network survivability. We perceive the network survivability as a composite measure consisting of both network failure duration and failure impact on the network. A wireless ad-hoc network is analyzed as an example, and the excess packet loss due to failures (ELF) is taken as the survivability performance measure. To obtain ELF, we adopt a two phase approach consisting of the steady-state availability analysis and transient performance analysis. Assuming Markovian property for the system, this measure is obtained by solving a set of Markov models. By utilizing other analysis paradigms, our approach in this paper may also be applied to study the survivability performance of more complex systems.

In this paper, we consider a new stochastic model for file recovery action with checkpointing when a system failure occurs according to a homogeneous Poisson process. The present checkpoint model strongly depends on the system age and is quite different from the models by Gelenbe (1979) and Goes and Sumita (1995). We propose three kinds of approximation schemes to determine the optimal checkpoint interval which maximizes system availability, taking account of queueing effect due to idle periods in the transaction processing system. In numerical examples, the checkpoint model based on three approximation schemes is compared with earlier models quantitatively, and it is shown that it can reduce system overhead which may occur in unplanned system downtime.

Recently, the phenomenon of "software aging", one in which the state of a software system gradually degrades with time and eventually leads to performance degradation or crash/hang failure, has been reported. Preventive maintenance of operational software systems is used specifically to counteract this phenomenon. However preventive maintenance incurs an overhead in terms of downtime and cost and this must be traded off with the cost of failures to obtain maximum benefits. We present an analytical model of a software system employing inspection-based preventive maintenance, through a Markov Regenerative Process (MRGP) with a subordinated semi-Markov reward process. Furthermore, we consider preemptive-resume type transitions. The model is solved for steady state as well as transient conditions and expressions for expected downtime and expected cost are derived. Numerical examples are presented to illustrate the applicability of the models. With the help of these models, optimal strategies for preventive maintenance techniques such as "software rejuvenation" could be formulated.

This paper studies the steady-state availability of systems with times to outages and recoveries that are generally distributed. Availability bounds are derived for systems with limited information about the distributions. Also investigated are the applicability of convenient exponential models in evaluating availability for systems that have two-sided bounded distributions of times to planned outages. A general closed-form formula is derived for the steady-state availability of a system with multiple outage types of arbitrary distributions. The formula shows that only the mean values of times to repair (TTR/sub i/, i = 1, 2,..., n) affect the steady-state availability; i.e., distributions of TTR/sub i/ with the same mean value have the same effect in determining the steady-state system availability. However, the distributions of times to outages, (TTO/sub i/, i = 1, 2,..., n), have an important impact on the steady-state system availability. Bounds are provided for the steady-state availability for a system subject to unplanned outages, for which times-to-outages are exponentially distributed and planned outages for which times-to-outages have bounded distributions. In practice, the distribution of time to planned outages is generally bounded due to economic constraints and industrial competition. The bounds derived here are good estimates of the system's steady-state availability, if the only known information of time-to-planned-outage is its two-sided bounds. Popular all-exponential models that assume that all times to outages and recoveries are exponentially distributed can under-estimate or over-estimate system availability if used for a system with generally distributed times to outages, of which limited information is known. Therefore explicit criteria are presented for determining when an all-exponential model, if applied to systems with outages of two-sided bounded general distributions, is a good approximation.

The article gives detailed mathematical results on the hypergeometric distribution software reliability model (HGDSRM) proposed by Y. Tohma et al. (1989; 1991). In the above papers, Tohma et al. developed the HGDSRM as a discrete-time stochastic model and derived a recursive formula for the mean cumulative number of software faults detected up to the i-th (>0) test instance in testing phase. Since their model is based on only the mean value of the cumulative number of faults, it is impossible to estimate not only the software reliability but also the other probabilistic dependability measures. We introduce the concept of cumulative trial processes, and describe the dynamic behavior of the HGDSRM exactly. In particular, we derive the probability mass function of the number of software faults detected newly at the i-th test instance and its mean as well as the software reliability defined as the probability that no faults are detected up to an arbitrary time. In numerical examples with real software failure data, we compare several HGDSRMs with different model parameters in terms of least squared sum and show that the mathematical results obtained here are very useful to assess the software reliability with the HGDSRM.

Many architecture-based software reliability models have been proposed in the past without any attempt to establish a relationship among them. The aim of this paper is to fill this gap. First, the unifying structural properties of the models are exhibited and the theoretical relationship is established. Then, the estimates provided by the models are compared using an empirical case study. The program chosen for the case study consists of almost 10,000 lines of C code divided into several components. The faulty version of the program was obtained by reinserting the faults discovered during integration testing and operational usage and the correct version was used as an oracle. A set of test cases was generated randomly accordingly to the known operational profile. The results show that 1) all models give reasonably accurate estimations compared to the actual reliability and 2) faults present in the components influence both components reliabilities and the way components interact.

Preventive maintenance is applied to improve system availability or decrease operational cost. Preventive maintenance with generally distributed parameters is discussed, and a steady-state solution is obtained by solving the underlying semi-Markov process (SMP). Specifically, periodic preventive maintenance with deterministically distributed repair time and maintenance time is discussed in detail, and closed-form results are presented. The behavior of the preventive maintenance mechanism is evaluated by numerical examples. Using our results, system operational cost can be reduced by the proper choice of optimal maintenance intervals.

As CORBA (Common Object Request Broker Architecture) gains popularity as a standard for portable, distributed, object-oriented computing, the need for a CORBA messaging solution is being increasingly felt. This led the Object Management Group (OMQ) to specify a Notification Service that aims to provide a more flexible and robust messaging solution than the earlier Event Service. The Notification Service provides several configurable quality of service (QoS) and administrative settings that deal with issues such as reliability, event (message) delivery order and discard policies. Unlike in conventional queuing systems, some Notification Service QoS configurations can lead to discards from within the internal queues, requiring careful analysis and configuration if such discards are to be avoided or minimized. This paper presents stochastic models (based on continuous time Markov chains and queuing theory) to analyze the Notification Service delivery and discard policies in detail.

Software rejuvenation is a preventive maintenance technique that has been extensively studied in recent literature. In this paper, we extend the classical result by Huang et al. (1995), and in addition propose a modified stochastic model to generate the software rejuvenation schedule. More precisely, the software rejuvenation models are formulated via the semi-Markov reward process, and the optimal software rejuvenation schedules are derived analytically in terms of the reward rate. In particular, we consider the two special cases: steady-state availability and expected cost per unit time in the steady state. Further, we develop non-parametric algorithms to estimate the optimal software rejuvenation schedules, provided that the statistically complete (unsensored) sample data of failure time is given. In numerical examples, we compare two models from the viewpoints of system availability and economic justification, and examine asymptotic properties for the statistical estimation algorithms.

We develop performance models of the broadcast and unknown server (BUS) in the LANE. The traffic on the BUS is divided into two classes: the broadcast and multicast traffic, and the unicast relay flow. The broadcast and multicast traffic is assumed to form a Markov modulated Poisson process (MMPP). The traffic for a particular unicast relay flow is an MMPP as well. However, the number of active unicast relay flows sojourning on the BUS is determined by a tandem queueing system, where the flow arrival process is Poisson, the address resolution delay is exponentially distributed, and the connection setup delay is three-stage Erlang distributed. The size of data frames in traffic flows is a random variable with three possible values: short, medium, and large. In order to deal with the intractability (i.e., largeness and stiffness) of the underlying Markov chain, a hierarchical model is used to decompose the system. With the help of the Stochastic Petri Net Package (SPNP), a software package for the automated generation and solution of Markovian stochastic systems, and the decomposition method, we study the performance of the BUS module under different loads. We also investigate the effect of address resolution delay and connection setup delay on the performance of the BUS.

The traditional pure performance model that ignores failure and recovery but considers resource contention generally overestimates the system's ability to perform a certain job. On the other hand, pure availability analysis tends to be too conservative since performance considerations are not taken into account. To obtain realistic composite performance and availability measures, one should consider performance changes that are associated with failure recovery behavior. In this paper, a brief review is first given of the advances in composite performance and availability analysis. Then three techniques for composite performance and availability analysis are discussed in detail through a queueing system in a wireless communications network.

Call admission control algorithms that reduce dropped calls in CDMA cellular systems are discussed in this paper. The capacity of a CDMA system is confined by the interference of users from both inside and outside of the target cell. Earlier algorithms for call admission control have been based on the effective traffic load for the target cell if one call is accepted. These algorithms ignore the interference effect of the to-be-accepted call on the neighboring cells. In our algorithms, the call admission decision is based on the effective traffic loads for both the target cell and the neighboring cells. In addition, to prioritize handoff calls, we also introduce the idea of a soft guard channel, which reserves some traffic load exclusively for handoff calls. Stochastic reward net (SRN) models are constructed to compare the performance of the algorithms. The numerical results show that our algorithms can significantly reduce the dropped calls with a price of increasing the blocked calls. To show the potential gain due to our algorithms, we introduce two new metrics: the increased blocking ratio for our algorithms and the increased dropping ratio for the conventional algorithms. From the numerical results, it is shown that our algorithms can reduce the dropped calls significantly while the blocked calls are increased at a relatively small rate under both homogeneous and hot spot traffic loads.

The GMDH (group method of data handling) network is an adaptive learning machine based on the principle of heuristic self-organization. The authors apply the GMDH networks to predict software reliability in the testing phase. Three kinds of networks: the basic GMDH and its improved versions based on PSS (prediction sum of squared) and AIC (Akaike information criterion), are introduced for the prediction of the failure-occurrence times observed in the testing phase of the software system. In numerical examples, the GMDH networks, the usual MLP (multi-layer perceptron) neural networks and existing SRGMs (software reliability growth models) are compared from the view point of predictive performance. It is shown that the GMDH networks can overcome the problem of determining a suitable network size in the use of an MLP neural network, and can provide a more accurate measure in the software reliability assessment than other prediction devices. Further, the problem of determining the optimal software release schedule, which minimizes the relevant expected total software cost, is considered in the framework of the GMDH network architecture.

In this paper, we extend the classical result by Huang, Kintala, Kolettis and Fulton (1995), and in addition propose a modified stochastic model to determine the software rejuvenation schedule. More precisely, the software rejuvenation models are formulated via the semi-Markov processes, and the optimal software rejuvenation schedules which maximize the system availabilities are derived analytically for respective cases. Further, we develop nonparametric statistical algorithms to estimate the optimal software rejuvenation schedules, provided that the statistical complete (unsensored) sample data of failure times is given. In numerical examples, we examine asymptotic properties for the statistical estimation algorithms.

Since the early 1970's a number of models have been proposed for estimating software reliability. However, the realism of many of the underlying assumptions and the applicability of these models continue to be questioned. Our research work was motivated by the fact that although there are practical situations in which the assumption of independence among successive software failures could be easily violated, much of the published literature on software reliability modeling does not seriously address this issue. In this paper we present a modeling framework based on Markov renewal processes which naturally introduces dependence among successive software runs and enables the phenomena of failure correlation to be precisely characterized. Thus, incorporating failure correlation into dependability and performability predictions contributes toward more realistic modeling of software systems in operation.

The event service is the earliest CORBA solution to the message queue model of communication in distributed systems. Typical implementations, however, suffer from the lack of event delivery guarantees. The loss of messages is aggravated by the presence of burstiness in the input to the event service, and occurrences of isolated bursts of traffic could also have serious effects. In this paper, we develop stochastic reward net (SRN) models that can aid in the study and configuration of the event service to conform to design specifications. To capture burstiness in the input, a Markov-modulated Poisson process (MMPP) is used as the input source. Erlang distributed event consumption times are used in the models to accommodate more general distributions and a wider range of variances. The models also take into consideration the FIFO discard policy adopted in many event service implementations. The SRN models are solved using the tool SPNP (Stochastic Petri Net Package). The applicability of the models to the CORBA notification service is also briefly discussed.

Perhaps the most stringent restriction in most software reliability models is the assumption of statistical independence among successive software failures. The authors research was motivated by the fact that although there are practical situations in which this assumption could be easily violated, much of the published literature on software reliability modeling does not seriously address this issue. The research work in this paper is devoted to developing the software reliability modeling framework that can consider the phenomena of failure correlation and to study its effects on the software reliability measures. The important property of the developed Markov renewal modeling approach is its flexibility. It allows construction of the software reliability model in both discrete time and continuous time, and (depending on the goals) to base the analysis either on Markov chain theory or on renewal process theory. Thus, their modeling approach is an important step toward more consistent and realistic modeling of software reliability. It can be related to existing software reliability growth models. Many input-domain and time-domain models can be derived as special cases under the assumption of failure s-independence. This paper aims at showing that the classical software reliability theory can be extended to consider a sequence of possibly s-dependent software runs, viz, failure correlation. It does not deal with inference nor with predictions, per se. For the model to be fully specified and applied to estimations and predictions in real software development projects, we need to address many research issues, e.g., the detailed assumptions about the nature of the overall reliability growth, way modeling-parameters change as a result of the fault-removal attempts.

Network management provides the central nervous system for the networks of telecommunications providers. A telco's network management system (NMS) needs to support uninterrupted management functionality of complex networks. The reliability of such systems has direct impact on the quality of services (QoS) provided to the consumers. Even a short down-time of the NMS may cause customer dissatisfaction, revenue losses, and may even jeopardize life. In order to expedite the process of transforming technological capabilities into services and to shorten the development cycle of its NMS, the telecommunication industry is adopting CORBA as an underlying architecture. However, neither the CORBA specifications nor the available services currently provide direct support for fault-tolerant objects. Consequently, NMS developers using CORBA must provide their own fault-tolerance mechanism for mission-critical objects. This paper reviews available fault-tolerance approaches in the research literature, presents the architecture of GTE's next generation NMS, discusses the reliability issues involved in such systems, and provides our approaches to solve them. Specifically, we present in detail our fault-tolerance approaches for the naming server, event channels, and other inhouse built critical business objects. A brief comparison of our approaches with others is also given.

Perhaps the most stringent restriction that is present in most software reliability models is the assumption of independence among successive software failures. Our research was motivated by the fact that although there are practical situations in which this assumption could be easily violated, much of the published literature on software reliability modeling does not seriously address this issue. In this paper we present a software reliability modeling framework based on Markov renewal processes which naturally introduces dependence among successive software runs. The presented approach enables the phenomena of failure clustering to be precisely characterized and its effects on software reliability to be analyzed. Furthermore, it also provides bases for a more flexible and consistent model formulation and solution. The Markov renewal model presented in this paper can be related to the existing software reliability growth models, that is, a number of them can be derived as special cases under the assumption of failure independence. Our future research is focused on developing more specific and detailed models within this framework, as well as statistical inference procedures for performing estimations and predictions based on the experimental data.

Software systems are known to suffer from outages due to transient errors. Recently, the phenomenon of "software aging", in which the state of the software system degrades with time, has been reported (S. Garg et al., 1998). The primary causes of this degradation are the exhaustion of operating system resources, data corruption and numerical error accumulation. This may eventually lead to performance degradation of the software or crash/hang failure, or both. Earlier work in this area to detect aging and to estimate its effect on system resources did not take into account the system workload. In this paper, we propose a measurement-based model to estimate the rate of exhaustion of operating system resources both as a function of time and the system workload state. A semi-Markov reward model is constructed based on workload and resource usage data collected from the UNIX operating system. We first identify different workload states using statistical cluster analysis and build a state-space model. Corresponding to each resource, a reward function is then defined for the model based on the rate of resource exhaustion in the different states. The model is then solved to obtain trends and the estimated exhaustion rates and the time-to-exhaustion for the resources. With the help of this measure, proactive fault management techniques such as "software rejuvenation" (Y. Huang et al., 1995) may be employed to prevent unexpected outages.

Software reliability growth models, such as the non-homogeneous Poisson process (NHPP) models, are frequently used in software reliability prediction. The estimation of parameters in these models is often done by point estimation. However, some numerical problems arise with this approach, and make the actual computation hard, especially for automated reliability prediction tools. In this paper, confidence interval computation is studied in the Goel-Okumoto (1979) model and the S-shaped model (S. Yamada et al., 1983). The upper and the lower bounds of the parameters can be obtained. For reliability prediction, we implement a simplified Bayesian approach, which delivers improved results. The bounds on the predicted reliability are also computed. Furthermore, the numerical problems encountered in earlier point estimation methods are removed by this approach. Our results can thus be used as an important part of the assessment of software quality.

In this paper, we compare the availability and performance of a wireless TDMA system with and without automatic protection switching. Stochastic reward net models are constructed and solved by SPNP (Stochastic Petri Net Package). Hierarchical decomposition is adopted to simplify the analysis. The optimization of the number of guard channels reserved for the handoff calls is studied. Numerical results prove the accuracy of the decomposition and show the significant improvement of the availability and the performance indexed as the new call blocking probability and handoff call dropping probability, brought by automatic protection switching.

An RF channel at a cell is assigned to a call during the call set-up process. The channel is dedicated to the subscriber until the call is terminated (normal termination) or the subscriber leaves the cell (handoff). However, the RF channel may fail due to equipment failure or environment changes (failure-termination). In order to increase system end-to-end availability, an RF channel recovery method is proposed in this paper. When an RF channel fails, the channel is replaced by another working channel and the call continues. The method to replace failed RF channels of ongoing calls and to handle channel failures of handoff and new calls is investigated. The numerical results show that the recovery scheme reduces the dropped calls and the blocked calls significantly under both light and normal traffic. In addition, the numerical results for the recovery model and the pure performance model are nearly the same, which indicates that the recovery scheme can almost eliminate the dropped/blocked calls caused by channel impairment.

The purpose of this paper is to describe a method for the simulation of the recently introduced fluid stochastic Petri nets. Since such nets result in rather complex system of partial differential equations, numerical solution becomes a formidable task. Because of a mixed (discrete and continuous) state space, simulative solution also poses some interesting challenges, which are addressed in the paper.

The phenomenon of software aging refers to the accumulation of errors during the execution of the software which eventually results in it's crash/hang failure. A gradual performance degradation may also accompany software aging. Pro-active fault management techniques such as "software rejuvenation" (Y. Huang et al., 1995) may be used to counteract aging if it exists. We propose a methodology for detection and estimation of aging in the UNIX operating system. First, we present the design and implementation of an SNMP based, distributed monitoring tool used to collect operating system resource usage and system activity data at regular intervals, from networked UNIX workstations. Statistical trend detection techniques are applied to this data to detect/validate the existence of aging. For quantifying the effect of aging in operating system resources, we propose a metric: "estimated time to exhaustion", which is calculated using well known slope estimation techniques. Although the distributed data collection tool is specific to UNIX, the statistical techniques can be used for detection and estimation of aging in other software as well.

Prevalent Markovian and semi Markovian methods to predict the reliability and performance of component based heterogeneous systems suffer from several limitations: they are subject to an intractably large state space for more complex scenarios, and they cannot take into account the influence of various parameters such as reliability growth of individual components, dependencies among components, etc., in a single model. Discrete event simulation offers an alternative to analytical models as it can capture a detailed system structure, and can be used to study the influence of different factors separately as well as in a combined fashion on dependability measures. We demonstrate the flexibility offered by discrete event simulation to analyze such complex systems through two case studies, one of a terminating application, and the other of a real time application with feedback control. We simulate the failure behavior of the terminating application with instantaneous as well as explicit repair. We also study the effect of having fault tolerant configurations for some of the components on the failure behavior of the application. In the second case of the real time application, we initially simulate the failure behavior of a single version taking into account its reliability growth. We also study the failure behavior of three fault tolerant systems: DRB, NVP and NSCP which are built from the individual versions of the real time application. Results demonstrate the flexibility offered by simulation to study the influence of various factors on the failure behavior of the applications for single as well as fault tolerant configurations.

The software reliability measurement problem can be approached by obtaining the estimates of the residual number of faults in the software. Traditional black box based approaches to software reliability modeling assume that the debugging process is instantaneous and perfect. The estimates of the remaining number of faults, and hence reliability, are based on these oversimplified assumptions and they tend to be optimistic. We propose a framework relying on rate based simulation technique for incorporating explicit debugging activities along with the possibility of imperfect debugging into the black box software reliability models. We present various debugging policies and analyze the effect of these policies on the residual number of faults in the software. In addition, we propose a methodology to compute the reliability of the software, taking into account explicit debugging activities. An economic cost model to determine the optimal software release criteria in the presence of debugging activities is described. Finally, we present the high level architecture of a tool, called SRSIM, for the purpose of automating the simulation techniques presented.

Preventive maintenance of operational software systems, a novel technique for software fault tolerance, is used specifically to counteract the phenomenon of software "aging". However, it incurs some overhead. The necessity to do preventive maintenance, not only in general purpose software systems of mass use, but also in safety-critical and highly available systems, clearly indicates the need to follow an analysis based approach to determine the optimal times to perform preventive maintenance. In this paper, we present an analytical model of a software system which serves transactions. Due to aging, not only the service rate of the software decreases with time, but also the software itself experiences crash/hang failures which result in its unavailability. Two policies for preventive maintenance are modeled and expressions for resulting steady state availability, probability that an arriving transaction is lost and an upper bound on the expected response time of a transition are derived. Numerical examples are presented to illustrate the applicability of the models.

As switched networks providing services to end users become more commonplace, the integral components of these networks must have an increasing level of dependability. One area of interest is determining the optimal number of network servers required for a switched network application by taking into consideration the characteristics of the network traffic and failure rate of the servers. A stochastic reward net model is developed for this purpose. Such models allow performance and availability measures to be combined.

A combined performance and dependability (called performability) model for dealing with handoff calls is introduced. Stochastic reward nets (SRNs) are used for this purpose. An SRN model of channel assignment is developed and analyzed. The method of phase type expansion is used is approximate non-exponential call holding time distribution. A discussion, of how hand-off models with failure relate to Markov reward models is also given.

With the increased attention ATM is receiving to meet the needs of a wide variety of applications, tools are needed to help a network designer focus on the design at hand, rather than to spend time exhaustively learning the tools themselves. This is the concept behind IDEA. This paper introduces "modeling engines" chosen to be integrated into IDEA and presents a user interface for networking design. The first objective for IDEA is to demonstrate its usefulness for dependability modeling. Later objectives include incorporating performance and performability modeling.

We characterize the time-dependent behavior of a typical queuing system that arise in ATM networks under the presence of overloads. The transient queue length distribution and transient cell loss probability are obtained numerically and transient characteristics such as maximum overshoot and relaxation time are used to quantify the effects of congestion periods. A new measure, expected excess loss in overload (EELO) is defined to quantify the effects of overload when compared with the system behavior in the steady-state regime. The basic modeling technology that we use is an extended form of stochastic Petri nets and a software tool called the stochastic Petri net package (SPNP).

A number of analytical software reliability models have been proposed for estimating the reliability growth of a software product. We present an Enhanced Non-Homogeneous Poisson Process (ENHPP) model and show that previously reported Non-Homogeneous Poisson Process (NHPP) based models, with bounded mean valve functions, are special cases of the ENHPP model. The ENHPP model differs from previous models in that it incorporates explicitly the time varying test coverage function in its analytical formulation, and provides for defective fault detection and test coverage during the testing and operational phases. The ENHPP model is validated using several available failure data sets.

Checkpointing with rollback-recovery is a well known technique to reduce the completion time of a program in the presence of failures. While checkpointing is corrective in nature, rejuvenation refers to preventive maintenance of software aimed to reduce unexpected failures mostly resulting from the "aging" phenomenon. In this paper, we show how both these techniques may be used together to further reduce the expected completion time of a program. The idea of using checkpoints to reduce the amount of rollback upon a failure is taken a step further by combining it with rejuvenation. We derive the equations for expected completion time of a program with finite failure free running time for the following three cases when; (a) neither checkpointing nor rejuvenation is employed, (b) only checkpointing is employed, and finally (c) both checkpointing and rejuvenation are employed.We also present numerical results for Weibull failure time distribution for the above three cases and discuss optimal checkpointing and rejuvenation that minimizes the expected completion time. Using the numerical results, some interesting conclusions are drawn about benefits of these techniques in relation to the nature of failure distribution.

Two arcs are missing in a figure of Malhotra & Trivedi (see ibid., vol. 44, p. 428-40, 1995); these arcs are necessary for the proper functioning of the generalized stochastic Petri net (GSPN). Also, priorities of immediate transitions in that figure must be clearer. This note presents a correctly drawn GSPN and describes the priority assignment to immediate transitions in this GSPN.

Stochastic Petri net models of large systems that are solved by generating the underlying Markov chain pose the problem of largeness of the state-space of the Markov chain. Hierarchical and iterative models of systems have been used extensively to solve this problem. A problem with models which use fixed-point iteration is the theoretical proof of the existence, uniqueness and convergence of the fixed-point equations, which still remains an "art". In this paper, we establish conditions, in terms of the net structure and the characteristics of the iterated variables, under which existence of a solution is guaranteed when fixed-point iteration is used in stochastic Petri nets. We use these conditions to establish the existence of a fixed point for a model of a priority scheduling system, at which tasks may arrive according to a Poisson process or due to spawning or conditional branching of other tasks in the system.

In a client-server type system, the server software is required to run continuously for very long periods. Due to repeated and potentially faulty usage by many clients, such software "ages" with time and eventually fails. (Huang et al., 1995) proposed a technique called "software rejuvenation" in which the software is periodically stopped and then restarted in a "robust" state after proper maintenance. This "renewal" of software prevents (or at least postpones) the crash failure. As the time lost (or the cost incurred) due to the software failure is typically more than the time lost (or the cost incurred) due to rejuvenation, the technique reduces the expected unavailability of the software. We present a quantitative analysis of software rejuvenation. The behavior of the system is represented through a Markov Regenerative Stochastic Petri Net (MRSPN) model which is solved both for steady state as well as transient conditions. We provide a closed-form analytical solution for the steady state expected down time (and the expected cost incurred) due to system unavailability. We also evaluate the optimal rejuvenation interval which minimizes the expected unavailability of the software.

Non-Markovian models allow us to capture a very wide range of circumstances in which it is necessary to model phenomena whose times to occurrence is not exponentially distributed. Events such as timeouts in a protocol, service times at a machine performing the same task on each part, and memory access or instruction execution in a low-level h/w or s/w model, have durations which are constant or with a very low variance. Phase-type distributions can be used to approximate a non-exponential, but they increase the size of the state space.The analysis of stochastic systems with non-exponential timing is of increasing interest in the literature and requires the development of suitable modeling tools. Recently, some effort has been devoted to generalize the concept of Stochastic Petri Nets (SPN), by allowing the firing times to be generally distributed.A particular case of non-Markovian SPN, is the class of Deterministic and SPN (DSPN) [1]. A DSPN is a non-Markovian SPN where, in each marking, at most one transition is allowed to have a deterministic firing time with enabling memory policy.A new class of stochastic Petri nets has recently been defined [2, 3] by generalizing the deterministic firing times of the DSPN to generally distributed firing times. The underlying stochastic process for these classes of Petri nets is a Markov Regenerative Process (MRGP). This observation has opened a very fertile line of research aimed at the definition of solvable classes of models whose underlying marking process is an MRGP, and therefore referred to as Markov Regenerative Stochastic Petri Nets (MRSPN).Some of the results in this filed will be described in the session. In particular, Ciardo investigates stochastic confusion by defining the selection probability for transitions attempting to fire at the same time. German introduces the "method of supplementary variables" for the derivation of state equations describing the transient behavior of the marking process. Puliafito describes how, under some constraints, concurrent enabling of several generally distributed timed transitions is allowed. Bobbio and Telek discuss how age memory policy can be included to capture preemptive mechanisms of the resume (prs) type.

Abstract Several algorithms have been developed to solve the reliability problem for nonseries‐parallel networks using thesum of disjoint products (SDP)approach. This paper provides a general framework for most of these techniques. It reviews methods that help improve computer time and memory requirements in reliability computation. These parameters are generally used to compare SDP algorithms. We also overview three multiple variable inversion algorithms that result in sum of disjoint products expressions with fewer terms than that of algorithms that use only a single‐variable inversion. One common network is solved for two‐terminal network reliability using each of these algorithms. Finally, we have provided a comparison among these techniques.

Derives expressions for the time-dependent state probabilities and the time-averaged state-probabilities for the leaky bucket rate control scheme. The model is based on the theory of Markov regenerative processes. The results specialize to those obtained by Sidi et al. (1993) for the steady-state behavior of the leaky bucket. The present results are more general, however, in that they apply to the transient regime and to more general arrival processes.>

Most reliability analysis techniques and tools assume that a system is used for a mission consisting of a single phase. However, multiple phases are natural in many missions. The failure rates of components, system configuration, and success criteria may vary from phase to phase. In addition, the duration of a phase may be deterministic or random. Recently, several researchers have addressed the problem of reliability analysis of such systems using a variety of methods. We describe a new technique for phased-mission system reliability analysis based on Boolean algebraic methods. Our technique is computationally efficient and is applicable to a large class of systems for which the failure criterion in each phase can be expressed as a fault tree (or an equivalent representation). Our technique avoids state space explosion that commonly plague Markov chain-based analysis. We develop a phase algebra to account for the effects of variable configurations and success criteria from phase to phase. Our technique yields exact (as opposed to approximate) results. We demonstrate the use of our technique by means of an example and present numerical results to show the effects of mission phases on the system reliability.

We discuss the role of modeling in the design and validation of life-critical, real-time systems. The basics of Markov, Markov reward, and stochastic reward net models are covered. An example of a nuclear power plant cooling system is developed in detail. Multilevel models, model calibration, and model validation are also discussed.>

The need for the combined performance and reliability analysis of fault tolerant systems is increasing. The common approach to formulating and solving such problems is to use (semi-)Markov reward models. However, the large size of state spaces is a problem that plagues Markovian models. Combinatorial models have been used for modeling reliability and availability of complex systems without paying the price of large Markov models. However, assumptions of two-state behavior of components (and that of the system), independence assumptions of component state transitions, and restrictive repair assumptions decrease the potential of combinatorial models for realistic systems. The authors propose a combinatorial algorithm for the combined performance and reliability analysis of coherent repairable systems with multistate components, allowing interdependent component state transitions. An example illustrating the algorithm is also presented.>

The inherently weak reliability behavior of the ring architecture has led network designers to consider various design choices to improve network reliability. We assess the impact of provisions such as node bypass, secondary ring and concentrator trees on network reliability. For this reason, we develop closed-form expressions for the reliability and the mean time-to-failure of the double counter-rotating ring architecture. For our comparisons we adopt the 2-terminal, and the all-terminal reliability criteria. Our network reliability expressions are valid for any time-to-failure distributions of links and nodes.>

Presents a performance analysis of a heterogeneous multiprocessor system where tasks may arrive from Poisson sources as well as by spawning and probabilistic branching of other tasks. Non-preemptive priority scheduling is used between different tasks. Stochastic reward nets are used as the system model, and are solved analytically by generating the underlying continuous-time Markov chain. An approximation technique is used, that is based on fixed-point iteration to avoid the problem of a large underlying Markov chain. The iteration scheme works reasonably well, and the existence of a fixed point for the iterative scheme is guaranteed under certain conditions.>

Five different attachment schemes proposed for the FDDI (fiber distributed data interface) token ring are compared in terms of reliability. For this purpose, the topologies are first studied in isolation (reliability of the path to the backbone) and subsequently end-to-end user reliabilities are computed by combining backbone reliability with the reliability of the path to the backbone.>

We consider the sensitivity of transient solutions of Markov models to perturbations in their generator matrices. The perturbations can either be of a certain structure or can be very general. We consider two different measures of sensitivity and derive upper bounds on them. The derived bounds are sharper than previously reported bounds in the literature. Since the sensitivity analysis of transient solutions is intimately related to the condition of the exponential of the CTMC matrix, we derive an expression for the condition number of the CTMC matrix exponential which leads to some interesting implications. We compare the derived sensitivity bounds both numerically and analytically with those reported in the literature.

The common approach to formulating and solving combined reliability/availability and performance problems is to use Markov reward models. However, the large size of state spaces is a problem that plagues Markovian models. Combinatorial models have been used for modeling reliability and availability of complex systems without paying the price of large Markov models. Yet, assumptions of two-state behavior of components (and that of the system), independence assumptions of component failure behavior, and restrictive repair assumptions decrease the potential of combinatorial models for realistic systems. A combinatorial approach is proposed for the combined performance and availability analysis of coherent repairable systems with multi-state components, allowing inter-dependent component state transitions. Examples showing the usefulness of the approach are presented.>

The authors describe a technique for computing the distribution of the completion time of a program on a server subject to failure and repair. Several realistic aspects of the system are included in the model. The server behavior is modeled by a semi-Markov process in order to accommodate nonexponential repair-time distributions. More importantly, the effect on the job completion time of the work lost due to the occurrence of a server failure is modeled. They derive a closed-form expression for the Laplace-Stieltjes transform (LST) of the time to completion distribution of programs on such systems. They then describe an effective numerical procedure for computing the completion time distribution. They show how these results apply to the analysis of different computer system structures and organizations of fault-tolerant systems. Finally, they use numerical solution methods to find the distribution of time to completion on several systems.>

A client-server system is a distributed system where a server station receives requests from its client stations, processes the requests and returns replies to the requesting stations. The authors consider client-server systems in which a set of workstations access a file server over a local area network. The systems are modelled by a class of stochastic Petri nets. The mean response time, the throughput and the parametric sensitivities are evaluated for a client-server system based on token ring network and a system based on CSMA/CD network. These models are different from the prevalent performance models of token ring or CSMA/CD network systems because of the message interdependencies introduced by the clients-server structure. An approximate analytic-numeric method rather than simulation is used to solve the models. The solution method and the accuracy of approximation are also discussed.>

The authors examine the problem of accurately modeling the software fault-tolerance technique based on recovery blocks. Analysis of some systems have investigated the correlation between software modules, which may be due to a portion of the functional specification that is common to all software modules, or to the inherent hardness of some problems. Three types of dependence which can be captured using measurements are considered. These are correlation between software modules for a single input, correlation between successive acceptance tests on correct module outputs and incorrect module outputs, and correlation between subsequent inputs. The authors' technique is quite general and can be applied to other types of correlation. In accounting for dependence, they use the intensity distribution introduced by D.E. Eckhardt and L.D. Lee (1985). A method of generating the intensity distribution that is based on the pairwise correlation between modules is discussed. This method is contrasted with the assumption of independent modules as well as the use of the beta-binomial density introduced by V.F. Nicola and A. Goyai (1990). The effects of dependencies were studied using a Stochastic Reward Network (SRN) that incorporates all of the above dependencies and a modeling tool called Stochastic Petri Net Package (SPNP).>

The performance of a polling system is modeled by stochastic Petri nets and its analysis is done by numerically solving the underlying Markov chain. One key problem in using stochastic Petri nets for real applications is that the size of underlying Markov chain tends to be large, and thus to be computationally intractable. In order to carry out the performance analysis of a large complex system in practice, the authors develop approximation methods at the Petri net level for the finite population, asymmetric polling systems and analyze the error due to the approximation. The mean cycle time and the mean response time of the system are approximated by the folding method and by the fixed-point iteration method. The effect of an increasing number of customers on the polling systems is studied using these approximations. The approximation methods are shown to save more than 95% of computation cost without a concomitant loss in accuracy. The methods perform very well at low offered loads.>

The paper develops reliability models and derives closed-form results for network reliability and network mean time to failure, including both node and link failures, for a very popular high speed LAN, the FDDI (fiber distributed data interface). It then extends the results to composite measures of performance and reliability.>

An efficient Boolean algebraic algorithm for the symbolic reliability and sensitivity analysis of coherent two-terminal networks with s independent components is described. The algorithm is also applicable to a fault tree model without NOT gates. The algorithm uses the concept originally proposed by A. Grnarov, L. Kleinrock, and M. Gerla (1979). After the algorithm is presented, the errors in the original technique are illustrated by two examples. The algorithm is extended t compute the reliability importance of a given component (sensitivity of system reliability to a given component's reliability). A computer program implementing the modified algorithm is used to solve and obtain measured time complexities for a large set of network and fault tree models.>

Finite population and finite capacity polling systems are considered. The behavior of these systems is described by means of generalized stochastic Petri nets. The exact results for the mean response times are obtained numerically by means of a stochastic Petri net package. Finite population polling systems are generally difficult to analyze. The results obtained can be used to validate approximate solutions to the above class of polling systems when such solutions become available.>

An aggregation method for computing transient cumulative measures of large, stiff Markov models is presented. The method is based on classifying the states of the original problem into slow, fast-transient, and fast-current states. The authors aggregate fast-transient states and fast-recurrent states so that an approximate value to the desired cumulative measure can be obtained by solving a nonstiff set of linear differential equations defined over a reduced subset of slow states only. Several examples are included to illustrate how stiffness arises naturally in actual queuing and reliability models, and to show that cumulative measures provide a better characterization of the time-dependent system behavior.>

M.D. Beaudry (1978) proposed a simple method of computing the distribution of performability in a Markov reward process. Two extensions of Beaudry's approach are presented. The authors generalize the method to a semi-Markov reward process by removing the restriction requiring the association of zero reward to absorbing states only. The algorithm proceeds by replacing zero reward nonabsorbing states by a probabilistic switch; it is therefore related to the elimination of vanishing states from the reachability graph of a generalized stochastic Petri net and to the elimination of fast transient states in a decomposition approach to stiff Markov chains. The use of the approach is illustrated with three applications.>

The problem of predicting the reliability of a distributed system based on the principles of Byzantine agreement is addressed. The system is considered inoperable or failed if Byzantine agreement cannot be guaranteed. The reliability models depend on a unified model of interactive consistency, which is based on a unique fault taxonomy appropriate for distributed systems. The unified model takes advantage of the fact that some faults may not be of an arbitrary nature, while still allowing for the fact that some faults may be arbitrary. A closed-form expression for the reliability and the mean time to failure of systems base on the unified model is derived. Each processor is allowed to have multiple failure modes, and the contribution of the interactive consistency algorithm is explicitly taken into account. The practical value of this unified model in designing ultrareliable systems is demonstrated by several examples.>

A novel technique that allows a single system to guarantee the execution of both periodic and aperiodic tasks within hard deadlines is presented. The approach is based on dynamically changing the replication factor of periodic tasks in response to aperiodic tasks. The technique is directly applicable to the problem of transient overloads that are time-critical. Preliminary results that show the applicability and the tradeoffs involved are presented.>

Continuous-time Markov chains (CTMC) are widely used mathematical models. Reliability models, queueing networks, and inventory models all require transient solutions of CTMC. The cost of CTMC transient solution increases with size, stiffness, and mission time. To eliminate stiffness and reduce the cost of solution, approximation techniques have been proposed. In this paper, we describe a software package for the specification and solution of stiff CTMC. As an interface, we use a language for the description of Markov chains. The language also provides facilities for controlling the solution procedure. Both exact and approximate solution techniques are provided. To conclude the paper, we use several examples to show the use of our specification language and the utility of our approximation technique. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.

The authors examine the reliability of a unique-path multistage interconnection network (MIN) and a fault-tolerant scheme aimed at improving system reliability. They derive closed-form expressions for the time-dependent reliability of the 8*8 and 16*16 shuffle-exchange multistage interconnection networks (SENs) and SENs with an addition state (SEN+). These expressions are derived without any assumptions regarding the underlying component-lifetime distributions. They derive a tight reliability lower bound that is useful for the analysis of larger networks. They provide numerical results for networks as large as 1024*1024.>

Several different models for predicting coverage in a fault-tolerant system, including models for permanent, intermittent, and transient errors, are discussed. Markov, semi-Markov, nonhomogeneous Markov, and extended stochastic Petri net models for computing coverage are developed. Two types of events that interfere with recovery are examined; and methods for modeling such events, whether they are deterministic or random, are given. The sensitivity of system reliability/availability to the coverage parameter and the sensitivity of the coverage parameter to various error-handling strategies are investigated. It is found that a policy of attempting transient recovery upon detection of an error (as opposed to automatically reconfiguring the affected component out of the system) can actually increase the unreliability of the system.>

Traditional evaluation techniques for multiprocessor systems use Markov chains and Markov reward models to compute measures such as mean time to failure, reliability, performance, and performability. In this paper, we discuss the extension of Markov models to include parametric sensitivity analysis. Using such analysis, we can guide system optimization, identify parts of a system model sensitive to error, and find system reliability and performability bottlenecks.

A measurement-based performability model is described that is based on error and resource-usage data collected on a multiprocessor system. A method for identifying the model structure is introduced, and the resulting model is validated against real data. Model development from the collection of raw data to the estimation of the expected reward is described. Both normal behavior and error behavior of the system are characterized. The measured data show that the holding times in key operational and error states are not simple exponentials and that a semi-Markov process is necessary to model the system behavior. A reward function, which is based on the service rate and the error rate in each state, is defined in order to estimate the performability of the system and to depict the cost of different types of errors.>

The behavior of the multiprocessor system is described as a continuous Markov chain, and a reward rate (performance measure) is associated with each state. The distribution of performability is evaluated for analytical models of a multiprocessor system using a polynomial-time algorithm that obtains the distribution of performability for repairable, as well as nonrepairable, systems with heterogeneous components with a substantial speedup over earlier work. Numerical results indicate that distributions of cumulative performance measures over finite intervals reveal behavior of multiprocessor systems not indicates by either steady-state or expected values alone.>

In this paper we consider the queueing analysis of a fault-tolerant computer system. The failure/repair behavior of the server is modeled by an irreducible continuous-time Markov chain. Jobs arrive in a Poisson fashion to the system and are serviced according to FCFS discipline. A failure may cause the loss of the work already done on the job in service, if any; in this case the interrupted job is repeated as soon as the server is ready to deliver service. In addition to the delays due to failures and repairs, jobs suffer delays due to queueing. We present an exact queueing analysig of the system and study the steady-state behavior of the number of jobs in the system. As a numerical example, we consider a system with two processors subject to failures and repairs.

A graph-based modeling technique has been developed for the stochastic analysis of systems containing concurrency. The basis of the technique is the use of directed acyclic graphs. These graphs represent event-precedence networks where activities may occur serially, probabilistically, or concurrently. When a set of activities occurs concurrently, the condition for the set of activities to complete is that a specified number of the activities must complete. This includes the special cases that one or all of the activities must complete. The cumulative distribution function associated with an activity is assumed to have exponential polynomial form. Further generality is obtained by allowing these distributions to have a mass at the origin and/or at infinity. The distribution function for the time taken to complete the entire graph is computed symbolically in the time parameter t. The technique allows two or more graphs to be combined hierarchically. Applications of the technique to the evaluation of concurrent program execution time and to the reliability analysis of fault-tolerant systems are discussed.

Queueing models provide a useful tool for predicting the performance of many service systems including computer systems, telecommunication systems, computer/communication networks and flexible manufacturing systems. Traditional queueing models predict system performance under the assumption that all service facilities provide failure-free service. It must, however, be acknowledged that service facilities do experience failures and that they get repaired. In recent years, it has been increasingly recognized that this separation of performance and reliability/availability models is no longer adequate.

An approximation algorithm for systematically converting a stiff Markov chain into a nonstiff chain with a smaller state space is discussed in this paper. After classifying the set of all states into fast and slow states, the algorithm proceeds by further classifying fast states into fast recurrent subsets and a fast transient subset. A separate analysis of each of these fast subsets is done and each fast recurrent subset is replaced by a single slow state while the fast transient subset is replaced by a probabilistic switch. After this reduction, the remaining small and nonstiff Markov chain is analyzed by a conventional technique.

Provably conservative (and optimistic) reliability models can be systematically derived from more complex models. These derived models incorporate a reduced state space and fewer transitions, and, therefore, have solutions that are more cost- effective than those of the original complex models. The designer can extensively explore the design space without incurring the expense of solving multiple complex models. A conservative- optimistic pair of derived models produces a band that includes the solution to the complex model. Sensitivity analysis can be performed on this pair of models to determine those parameters of the original model that are most sensitive to change (i.e., uncertainty) and hence warrant further expense in obtaining tighter specifications.

In order to remain tractable, mhany reliability models do not include the states and transitions necessary to represent fault/error-handling details. Instead, the effectiveness of fault/ error-handling mechanisms is represented by the use of instantaneous coverage probabilities. This paper investigates the effect of the error introduced by the assumption of instantaneous coverage probabilities on the predictions of the reliability model, and it shows that the reliability estimates thus obtained are lower bounds on the reliability estimates of the composite model with embedded fault/error-handling states and transitions. The paper also discusses the choice of the calculation method for the instantaneous coverage probabilities and defines a near-coincident-fault coverage model that yields conservative instantaneous coverage probabilities.

A review and a critical evaluation of a representative class of state-of-the-art models for ultrahigh reliability prediction is presented. This evaluation naturally leads us to a new model for ultrahigh reliability prediction now under development. The new model combines the flexibility and accuracy of simulation with the speed of analytic models.

Analytic queueing models of programs with internal concurrency are considered. The program behavior model allows a process to spawn two or more concurrent tasks at some point during its execution. Except for queueing effects, the tasks execute independently of one another, and at the end of their execution, either wait for all of their siblings to finish execution or merge with the parent if all have finished execution. Two approximate solution methods for the performance prediction of such systems are developed, and results of the approximations are compared to those of simulations. The approximations are both computationally efficient and highly accurate. The gain in performance due to multitasking and multiprocessing is studied with a series of examples.

An optimization model is developed for assigning a fixed set of files across an assemblage of storage devices so as to maximize system throughput. Multiple levels of executable memories and distinct record sizes for separate files are allowed. Through the use of this model, a general class of file assignment problems is reduced to the optimization of a convex function over a convex feasible region. A high-speed search procedure specifically tailored to solve this optimization problem is then presented, along with numerical examples from real systems which demonstrate orders of magnitude improvement in execution time over existing routines for solving the file-assignment problem. The optimal device capacity selection problem is then solved by simply calling the file assignment routine for each candidate set of device capacities.

Computer performance models of parallel processing systems in which a job subdivides into two or more tasks at some point during its execution are considered. Except for queueing effects, the tasks execute independently of one another and do not require synchronization. An approximate solution method is developed and results of the approximation are compared to those of simulations. Bounds on the performance improvement due to overlap are derived.

The performance-oriented design of linear storage hierarchies whtch are operating m muluprogramming environments ~s constdered An opt~mtzaUon model is superimposed upon an exponential queuing network model of the hterarchy, yteldmg a problem whose objectwe is to maxlmme throughput subject to a cost constraint.The dects~on variables are the speeds and capacmes of the various memory levels.It is shown that any local optimum is indeed a globally opumal solution to the problem.Several specml cases of and extensions to the basic problem are discussed, and some examples are given to dlustrate the usefulness and computational tractabihty of the problem KEY WORDS AND PHRASES linear storage hierarchies, miss ratio, multiprogrammmg, nonlinear programming, opttmization, performance-oriented design, queuing networks, storage technologies, systems modehng CR CATEGORIES 2 44, 4 32, 4.35, 4.6, 5 41, 5 5, 6 2, 6 34, 8 1, 8 3

A geometric programming model is proposed to determine the optimal design of the CPU and its matching storage hierarchy. The objective function is the maximization of system reliability subject to performance and budgetary limitations. Examples illustrating the use of the model are presented.

article Free Access Share on Optimal Selection of CPU Speed, Device Capacities, and File Assignments Authors: Kishor S. Trivedi Department of Computer Science, Duke University, Durham, NC Department of Computer Science, Duke University, Durham, NCView Profile , Robert A. Wagner Department of Computer Science, Duke University, Durham, NC Department of Computer Science, Duke University, Durham, NCView Profile , Timothy M. Sigmon Department of Computer Science, Duke University, Durham, NC Department of Computer Science, Duke University, Durham, NCView Profile Authors Info & Claims Journal of the ACMVolume 27Issue 3July 1980 pp 457–473https://doi.org/10.1145/322203.322208Published:01 July 1980Publication History 44citation552DownloadsMetricsTotal Citations44Total Downloads552Last 12 Months35Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my Alerts New Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

In this paper, a comparison of the performance of optimally designed computer systems with and without virtual memory is made. The computer systems in question are modeled by closed queuing networks of the central server type. The design of the systems is formulated as a nonlinear optimization problem where the objective function is to maximize the throughput subject to a nonlinear cost constraint. The decision variables are the speeds of the individual devices. This optimization problem is then solved by use of the Lagrange multiplier technique. The comparisons of the systems demonstrate the affect on performance of the addition of another I/O device to handle paging and the affect on performance of the additional overhead generated by the page fault handler. Also, the optimal amount of money to be spent on main memory is investigated.

This paper considers a computer configuration design problem. The computer system is modeled by a closed queuing network. The system throughput is the objective function to be maximized and the speed of the devices are the decision variables. A rich class of non-linear cost functions is considered.

We present a formal proof of correctness of the on-line division algorithm specified in an earlier paper [1]. We also derive two radix 4 on-line division algorithms, with non-redundant and redundant operands respectively.

Recently, there has been some interest in the use of continued fractions for digital hardware calculations. We require that the coefficients of the continued fractions be integral powers of 2 and, therefore, well-known continued fraction expansions of functions cannot be used. Methods of expansion of a large number of functions are presented. We show that the problem of selection of coefficients of the continued fractions does not have practical solution in most of the cases we have considered.

Data paging is of primary concern for problems with large data bases and for many types of array problems. We show that prepaging reduces the paging problems of array algorithms operating on large arrays. We also show that the use of a submatrix algorithm considerably improves the locality. Finally, we consider methods of automating these performance-improvement techniques by means of a compiler in the context of a structured array language.

In this paper, on-line algorithms for division and multiplication are developed. It is assumed that the operands as well as the result flow through the arithmetic unit in a digit-by-digit, most significant digit first fashion. The use of a redundant digit set, at least for the digits of the result, is required.

A demand prepaging algorithm DPMIN is defined and proved to be an optimal demand prepaging algorithm. However, it cannot be used in practice since it requires that the future refreence string be completely known in advance. Several practical prepaging algorithms are also defined which require only a partial knowledge of the future reference string. Finally, we show that these prepaging algorithms reduce the paging problems of array algorithms operating on large arrays.

Recently, there has been some interest in the use of continued fractions for digital hardware calculations. We require that the coefficients of the continued fractions be integral powers of two. As a result well known continued fraction expansions of functions cannot be used. Methods of expansion of a large number of functions are presented. We show that the problem of selection of coeffiients of the continued fractions does not have practical solution in most of the cases we have considered. We conjecture that the solution of a polynomial equation is the only problem that can be solved in our formulation.

In this paper we are considering problems of division and multiplication in a computational environment in which all basic arithmetic algorithms satisfy "on-line" property: to generate jthdigit of the result it is necessary and sufficient to have argument(s) available up to the (j+δ)th digit, where the index difference 6 is a small positive constant. Such an environment, due to its potential to perform a sequence of operations in an overlapped fashion, could conveniently speed up an arithmetic multiprocessor structure or it could be useful in certain real-time applications, with inherent on-line properties. The on-line property implies a left-to-right digit-by-digit type of algorithm and consequently, a redundant representation, at least, of the results. For addition and subtraction such algorithms, satisfying on-line property, can be easily specified. Multiplication requires a somewhat more elaborate approach and there are several possible ways of defining an on-line algorithm. However, the existence of an on-line division algorithm is not obvious and its analysis appears interesting.

The purpose of this paper is to demonstrate that representations of numbers other than positional notation may lead to practical hardware realizations for digital calculation of classes of algorithms. This paper describes current research in the use of continued fractions. Although practicality has not been demonstrated, theoretical results are promising.

The purpose of this paper is to demonstrate that representations of numbers other than positional notation may lead to practical hardware realizations for the digital calculation of classes of algorithms. It is the authors' opinion that practicality of the use of continued products has been demonstrated. This paper describes current research in the use of continued fractions. Although practicality has not been demonstrated, theoretical results are promising, and the results thus far are presented as a case study of the difficulties which arise when use of a new representation is attempted.