Hierarchical object-oriented modeling of fault-tolerant computer systems

HIERARCHICAL, OB JECT-ORIENTED MODELING OF FAULT-TOLERANT COMPUTER SYSTEMS Juan A. Carrasco* Departament d'Enginyeria Electrbnica, UPC Diagonal 647, plta. 9 OS02S-Barcelona, Spain Abstract A hierarchical, object-oriented modeling language for the specification of dependability models for complex fault-tolerant computer systems is overviewed. The language incorporates the hierarchical notions of cluster, operational mode and configuration and borrows from object-oriented prograniming the concepts of class, parameterization, and instantiation. These features together result in a highly expressive environment allowing the concise specification of sophisticated dependability models for complex systems. In addition, the language supports the declaration of symmetries that systems may exhibit at levels higher than the component level. These symmetries can be used to automatically generate lumped state-level models of significantly reduced size in relation to the state-level models which would be generated from a flat, component-level description of the system. 1. INTRODUCTION cification of arbitrary CThlC dependability models but require complex and t.hus error-prone descriptions for large systems. Another approach [6, 71 is the use of a special-purpose language with an implicit modeling point of view and special constructs easing the specification of often-encountered complex dependencies. In addition to being more user-friendly, the use of a high-level modeling language has the advantage of convey ing semantic knowledge which can be exploited during model solution [S, 9, IO]. This paper overviews a hierarchical, object-oriented modeling language for fault-tolerant computer systems which takes the SAVE modeling language [6,7] as starting point, but introduces many extensions (clusters, operational modes, configurations) enhancing significantly its modeling power and user-friendliness and supporting automatic generation of state-level models of reduced size when, as it is often the case, the system has symmetries at levels higher than the component level. The latter is important since it is the size of the CTLIC what ultimately limits the application of numerical solution methods. The rest _of the paper is organized as follows. Section 2 overviews the description of the language syntax and semantics and additional examples can be found in [ll]). Section 3 discusses the representaLion of the states of the lumped CTSIC's . Section 4 concludes the paper A fault-tolerant computer system can often be conceptualized failure, recovery, and repair processes. Dependencies among components often arise in real fault-tolerant computer systems due to failure propagation, limited recovery efficiency, ieconfigurations, and repair. Stochastic processes allow to consider as made up of components ,-hanging their state as a result of language using Of moderate (a all these important details. Recovery processes are typically several orders of magnitude faster than both failure and repair 2. LANGUAGE OVERVIEW processes and can be modelled by using instantaneous coverage probabilities [l], which can be obt,ained by statistical analysis 2.1. Modeling framework [2] of experimental data collected from fault-injection experiments. Typically, failure and repair times are assumed to have In Our language, a fault-tolerant computer system is conceptuexponential distributions so that the stochastic behavior of the alized as made UP of components and repair teams. Component system can be described by a continuolls time ~~~l;~~, states are modified by failure and repair processes. Failure pro- (CTMC) having failure repair general, de. cesses only affect unfailed components and are associated with pendencies among the behavior of the compoI1eIlts of the sys. Particular components of the spstem but, in general. can he tem are such that the CTMC has to be generated and solved propagated to other components. Repair processes are perusing general-purpose, state-level methods, Except for systems formed by repair teams. The system is either operational or with an small number of components, tile CTP\IC has a size down, as determined by the unfailed/failed condition of the (number of states) sucll that its direct specificat,ion is ,,nprac. conlponents of the system through a coherent structure functical a.nd autolnatic generation from a higher lcvcl specification tion [12]. Lack of coverage can be modeled in our language by is required. failure propagation. This approach is less restrictive than it seems at first glance. For instance, the inefficiency of systemAvailable model specification methodologies show a trntlcoff level recovery procedures can be modelled by introducing a .'rebetween modeling power and 11st.r-friendliness. Wv liav~ in one covery" component without failure processes which is required hand very general specification methodologies like St,ochastic to be unfailed for the system to be operational. and propaPetri nets [3, 41 and Production rules [5], which allow the spegating uncovered failures to the "recovery" component. The repair of the "recovery" component would model the restart 'This work was supported by the ESPRIT project, of the Cotiiiiiis~io~i of action usuaily after that type of system failures. the European Communities no. 1909 "SllART. System RIr.;isiiri,iiicnt aiid Arc hit ec t ure Teclirri qws" CH3001-5/91/0000/0452/$01.00 0 1991 IEEE 452 Lack of coverage taking down only part of the system can be modeled similarly. A component, can be operational, failed, or dormant. As in the SAVE modeling language [6, 71, the failed state can be refined Iiy failed modes, which are determined at the time the failure of tlie component occurs. In addition, in our language, the operat,ional st,ate can be refined by operational modes. Operational ~iiodes provide the basis for modeling differences in the failure processes affecting a component which may result from the configuration in which the system is working, and are an useful gcricralization expanding significantly the modeling power of the language. We also introduce in our language the concept of cluster. Conceptually, a cluster is a collection of components wliicli at a certain abstraction level can be seen as a whole. Clusters can have operational modes and configurations. Configurat,ions are also defined at the system level. A configuration tlefiiies a mapping of components and clusters instantiated at a givm level into operational modes. This allows the concise sp-ification of complex configuration strategies by exploiting th liicrarchical structure of the system. Tlie hchavior of components and clusters is described in parameterizahle classes which can be instantiated. A collection of objects can be instantiated with the same name. The behavior of t,he objects with the same name is undistinguishable and this information is exploited for the generation of lumped models wliose states are defined by factorizing instances with the same iiiiiiie and in the same state. By using clusters, symmetries that, tlir system may have at levels higher than the component 1evc.l (which would be disregarded if a flat, component-level description were used) can be made explicit and exploited. 2.2. An example Tlic constructs of the language will be illustrated through an cxample of moderate complexity. The example is a distributed fanlt-t,olerant database system with 4 sites. Each site contains t,wo processors and two databases, keeping two. copies of the tlat,a.. .4rcess to data is performed through two front-ends. The sitvs and t,lie front-ends are connected by two local-area netivoIlis (LAN’s) as shown in Figure 1. The system is operational if c~acli site has at least one unfaikd processor and one unfailed tlatabase, and at least one front-end and the LAN to which the frolit-end is connected are unfailed. When the system is down all the components are dormant. In addition, when a frontcmtl is failcd the corresponding LAX is dormant and viceversa. Dormtilit components do not fail. Two failed modes are considered for the processors: one recliiiring repair (hard failure) and another requiring only restart (soft failurc). The processor soft failure rate is higher when the sitr has only one operational processor, since in this configuratiori the processor has a higher load. Databases have also two fiiilcd modes: one requiring repair (hard failure) and another rczc1niring only data recovery (soft failure). In order to keep the colicx of the data consistent. write accesses are performed in Imrallcl to all the operational databases of a site. A processor f;iilurc contaminates one (and only one) operational database with a probability nhich depends on the type of failure (hard or soft) of the processor. A contaminated database is in soft failcd mode. Data recovery for databases in soft failure can be done in two modes. The fist mode (restoring) is possible if the the otlier database and at least one processor of the site are op4 ... I1 I Figure 1: A distributed fault-tolerant database system. erational and the site is accessible from at least one operational front-end. When restoring is not possible the database has to be recovered by a more time-consuming reloading operation. Processor restarts also require the site to be available from at least one front-end. Two field engineers repair databases, front-ends, LAN’s, and processors, with the higher priority given to databases, next to front-ends and LAN’s, and next to processors. Processor restarts and database recoveries are carried out by an unlimited number of operators. 2.3. Model constructs In our language, a model is described by a set of parameters and system, cluster class, component class, and repair team descriptions. The PARAMETERS construct for the distributed faulttolerant database system is given beIow. Each parameter can be assigned a default value to be used for CTMC generation if a value is not specified for it. PARAMETERS fefr: lfr: phf r : pdsf r : pssf r : dbhf r : dbsf r : hcov: f err : lrr : prepr : presr : dbrepr : dbresr: dbrelr: scov: 1/3600 1/800 1/20000 1/200 1/100 1/1200 1/3600 1/10 1/20 1/5 1/0.05 1/20 1/0.2 1 /* front-end failure rate */ /* LAN failure rate */ /* processor hard failure rate */ /* proc. soft f. rate in duplex */ /* proc. soft f. rate in simplex */ /* database hard failure rate */ /* database soft failure rate */ /* COV. to proc. hard failures */ /* cov. to proc. soft failures */ /* front-end repair rate */ /* LAN repair rate */ /* processor repair rate */ /* processor restart rate */ /* database repair rate */ /* database restore rate */ /* database reload rate */ In our language, a system is described hierarchically as a set of parameterized instantiations of cluster and component classes. This is done by MADE OF constructs included in the SYSTEM and CLUSTER CLASS constructs. In addition, the SYSTEM construct includes an optional list of resource attributes, either an operational or a down expression, and configurations. Resource attributes are logical variables summarizing the availability of unfailed resources instantiated at the system level and are defined by logical expressions with atoms of the forms component[integer] and cll~ster.res-att[integer], where component (chter) is a component (cluster) class or name instantiated at the current (system) level and res-att is a resource attribute of the cluster class. These atoms are true when at least integer in453 stances are unfailed or have the resource attribute true, respectively. Previously defined resource attributes can also be used. Resource attributes can be used in the construction of the operational/down expression and other expressions included in the description of configurations. The conditions under which the system is operational are described by either an operational expression or a down expression. Both are logical expressions with the same syntax as resource attribute expressions. The operational expression evaluates to true when the system is operational and its atoms have the same semantics as in resource attribute expressions. A down expression evaluates to true when the system is down and its atoms have reversed semantics (at least znteger instances are failed or have the resource attribute false, respectively). Resource attribute, operational, and down expressions have to be built using only the logical and, OT operators. This restriction is imposed to guarantee that the structure function of the system is coherent [12]. A configuration is described by a list of directives mapping unfailed component instances and cluster instances into operational modes. Configurations may have requirements and are tried in the order they appear so that, in a given state, the first one whose requirements are met is used. Thus, semantically, a list of configurations defines a configuration strategy at a given level. Unconfigured (unmapped) component and cluster instances become dormant. A dormant cluster has all its clusters and unfailed components dormant. This implicit behavior is followed by many systems and, thus, turns out to be useful. The SYSTEM construct for the distributed fault-tolerant database system is: SYSTEM MADE OF 2 Channel of ChannelC 4 Site of SiteC OPERATIONAL IF: Channel.UpC11 and Site.UpC41 CONFIGURATION CLUSTERS: Channel.Up, Site.Up operational: all specifying that the system includes two instances with name Channel of the cluster class ChannelC and four instances with name Site of the cluster class SiteC, and that the system is operational if at least one cluster Channel and all clusters Site have their resource attribute up true. A configuration mapping all Up clusters into operational is included. This is necessary because, by default, unmapped clusters are dormant. The keyword operational is used because the cluster classes do not have operational modes. A cluster is a set of components seen as a complex entity which can be configured and can configure t,he components included in it. The cluster concept is hierarchical, i.e., a cluster can be defined in terms of lower level clusters. As components. clusters are seen as instances of classes. The use of clusters makes the specification of the model more concise and allows t,o exploit symmetries which the system may exhibit at levels higher than the component level. This is the case in the distributed faulttolerant database system and two cluster classes are included in the specification of the model. The cluster class ChannelC includes one front-end and the L.4N connected to it and is Up when both components are unfailed. The cluster class SiteC includes the processors and databases of a site. The description of SiteC is: CLUSTER CLASS: SiteC MADE OF 2 Proc of ProcC 2 Db of DbC RESOURCE ATTRIBUTES Up: Proc[l] and DbCl] CONFIGURATION REQUIREMENTS : Proc [21 COMPONENTS: Proc Duplex: 2 COMPONENTS: Db operational: all CONFIGURATION COMPONENTS: Proc Simplex: 1 COMPONENTS: Db operational: all The resource attribute up is true when at least one processor and one database are unfailed. It is possible, in general. to define several resource attributes for a cluster class. The cluster class SiteC has two configurations. The first one is used when d1 its processors are unfailed. The second one is used when only one processor is unfailed. The first configuration maps the two unfailed processors into the operational mode Duplex and all unfailed databases into operational. The second configuration maps the unfailed processor into the operational mode Simplex and all unfailed databases into operational. Cluster or component classes not having operational modes have to be mapped into operational if they are not to become dormant. When the cluster class has operational modes each configuration has to be associated to an operational mode by using the construct CONFIGURATION FOR: op-mode. The behavior of components is also described in classes. The description of a component class includes, in its more general form, lists of parameters, operational modes and failed modes. and descriptions of failure modes and repair modes. Parameters are very useful in practice. For instance, the behavior of frontends and LAN’s, which is qualitatively identical, is described in the example by the following component class with parameters defining the failure and repair rates: COMPONENT CLASS: SimpleC PARAMETERS: failr, repr FAILURE MODE RATE: failr RATE: repr REPAIR TEAM: Fieldengineers PLEPAIR MODE The values of the parameters are defined when the components are instantiated. Thus. a front-end would be instantiated as SimpleC(fefr, ferr). The general form of a component class construct will be illustrated by the description of the component class Procc of the distributed fault-tolerant database: 454 COMPONENT CLASS: ProcC OPERATIONAL MODES: Duplex, Simplex FAILED MODES: Hf, Sf FAILURE MODE FAILED MODE: Hf RATE: phfr PROPAGATION MODE PROBABILITY: I-hcov PROPAGATION EVENT COMPONENTS: Db NUMBER: 1 FAILED MODE: Sf FAILURE MODE FROM: Duplex FAILED MODE: Sf RATE: pdsfr PROPAGATION MODE PROBABILITY: 1-scov PROPAGATION EVENT COMPONENTS: Db NUMBER: 1 FAILED MODE: Sf FAILURE MODE FROM: Simplex FAILED MODE: Sf RATE: pssfr PROPAGATION MODE PROBABILITY: 1-scov PROPAGATION EVENT COMPONENTS: Db NUMBER: 1 FAILED MODE: Sf REPAIR MODE FROM: Hf RATE: prepr REPAIR TEAM: Fieldengineers REPAIR MODE FROM: Sf DEPENDS UPON: /Channel [l] The component class Procc has two repair modes. The first one is used for hard failures and is scheduled to the repair team Fieldengineers; the second one is used for soft failures, is scheduled to the repair team Operators, and can only be undertaken if at least one channel is operational (note that this implies that at least one processor and the other database. of the site are also operational). Repair strategies are specified in REPAIR TEAM constructs which are illustrated by the repair team Fieldengineers of the distributed fault-tolerant database system: REPAIR TEAM: Fieldengineers NUMBER: 2 STRATEGY: priority DbC: 1 SimpleC: 2 ProcC: 3 The team has two repairmen and uses a preemptive priority strategy, in which failed components scheduled to the team are selected according to given priorities, with the selection among components with the same priority being at random when there are more failed components than remaining repainnen. Priorities can be assigned to component with given names as well as classes and can be made dependent of the mode in which the components are failed. It is possible to specify and unlimited number of repairmen. In this case, the STRATEGY construct is omitted. The simpler strategy ros (random order service), in which priorities are not specified, can be used when all the components scheduled to the repair team have the same priority. RATE: presr REPAIR TEAM: Operators 2.4. Metric specification The Same type of metrics which are incorporated in can be evaluated from a model specified using the language described here. These metrics include, among others, time between failures, the mean time to failure, the reliability, and the maintainability, as well as cost and related metrics, which result from the assignment of cost or pedormance indices to the states of the model. The metric to be evaluated is specified using the METRIC construct, This construct includes the OPTION coIlstruct to select the metric and, if required by the chosen option, the INITIAL STATE and INDEX constructs. The INITIAL STATE construct can be omitted for the state in which all components are unfailed and has the structure illustrated in the next section. The INDEX construct specifies a The component class Procc has three failure modes. The first riiodels hard failures and its active in any operational mode. The srcond and third failure modes model soft failures in, reeral, a list of unfailed component states, including operational modes and the keywords operational and dormant, can be given as the argument of the FAILURE MODE FROM construct. The description of a failure mode includes the mode in which the component is failed. which can only be omitted if the component class dors not have failed modes, the rate of the event (for ~nch component instance) and, optionally, a list of propagahn inodrs. spect'ively. the and Simp1ex Operational In gen. the steadystate availability, the point availability, the mean propagation modcs are exclusive events (at most one of tllenl Options requiring an Operational state with the Of the caII occur) and their description includes the probability of motlr and a list of propagation Propagation events are Ilot exclusive (any combination of them can in general occur). .4 propagation event propagates the failure of the component to ii given number of operational instances of a set of components of a given class. The set is specified using a special construct called component selector which allows navigation on the instantiat,ion tree of the system (starting from the level at which t,lie coniponerit is instantiated) using a UNIX-like syntax. The :;ctlrction of t,he set of components to which the failure can be 1,rc)pagated can be refined by specifying a list of operational 111odes in which the components can be affected. The descriptioil of a propagation event includes also the mode in which tllc coniponrnts are affected and the probability of the everit. ProIxd)ilities of propagation modes and events can be omitted \rit,li a dcfault value of 1. function to be used for the Of state indices' 3. EXPLOITING SYMMETRIES A CTRlC is automatically constructed from a model specification after selecting a particular type of metric. Advantage is taken of the symmetries made explicit by the model specification to reduce the size of the generated CTMC. This is done using a hierarchical state description in which cluster macrostates and component states of instances with the same name are factorized out. This is possible because, by construction, components and clusters with the same instantiation name are undistinguishable. We give next for illustration purposes the description of the state of the fault-tolerant distributed database 455 in which one front-end is failed and one piucessor of one site is in hard failed mode. CLUSTERS: Channel MACROSTATE INSTANCES: 1 MODE: dormant COMPONENTS: Fe failed: 1 COMPONENTS: Lan dormant: 1 MACROSTATE INSTANCES: 1 MODE: operational COMPONENTS: Fe COMPONENTS: Lan operational : 1 operational : 1 CLUSTERS: Site MACROSTATE INSTANCES: 1 MODE: operational COMPONENTS: Proc operational: 1 Hf: 1 COMPONENTS: Db operational: 2 MACROSTATE INSTANCES: 3 MODE: operational COMPONENTS: Proc COMPONENTS: Db operational: 2 operational : 2 The reduction of size obtained can be significant. For instance, without using the cluster construct of the language, front-ends, LAN’s, and the processors and databases of different sites have to be considered different, and the generated CTMC required for the computation of the availability has 408,969 states, while the lumped CTMC obtained from the specification using clusters has only 14,850 states (about 27 times less). The reduction is also significant in combination with pruning techniques [13]: 39 states for the reduced CTMC against 227 states when only states with up to two failed components are generated. 4. CONCLUSIONS A hierarchical, object-oriented modeling language for faulttolerant computer systems has been overviewed and its expressive power illustrated by an example of modcrate complexity. We have used the language to specify concisely niodels for substantially more complex systems [ll]. By providing facilities to express symmetries that complex systems often exhibit at levels higher than the component level, it is possible to generate automatically lumped state-level models of much smaller size than would be generated from a flat, component-level system description. This is important since it is the size of the state-level model what restricts the applicability of numcrical solution methods. The kind of symmetries which t,he language captures could be extended by using conccpts reccntly developed in the context of Petri net modeling [14], [15]. REFERENCES K. Trivedi, R. Geist. M. Smotherman, and J. B. Dugan .“Hybrid modeling of fault-tolerant systems” Comput. Elec. Eng. Int. /., vol. 11, no. 2/3, pp. 87-108, 1984. R. Geist. M. Smotherman and R. Talley, “Modeling Recovery Time Distributions in Ultrareliable Fault-Tolerant Systems,” in Proc. 20th fnt. Symp. on Fault-Tolerant Computing (FTCS20), Newcastle upon Tyne, June 1990, pp. 499-504. M. A. Marsan, G. Conte, and G. Balbo, “A class of generalized stochastic Petri nets for the performance evaluation of multiprocessor systems,” ACM Trans. on Computer Systems. vol. 2, pp. 93-122, May 1984. 0. C. ibe, A. Sathaye, R. C. Howe, and K. S. Trivedi, “Stochastic Petri Net Modeling of VAXcluster System Availability,” in Proc. 3rd. Int. Workshop on Petri ‘Vets and Performance Models (PNPMBS), Kyoto, Japan, December 1989. pp. 112121. J. A. Carrasco and J. Figueras, “hIETFAC: Design and Implementation of a Software Tool for Modeling and Evaluation of Complex Fault-Tolerant Computing Systems,” in Proc. 16th Int. Synip. on Fault-Tolerant Computing (FTCS-16), Yienna. July 1986, pp. 421-429. A. Goyal, W. C. Carter, E. de Souza e Silva, S. S. Lavenherg. and K. S. Trivedi, ”The System Availability Estimator.“ in Proc. 16th Int. Synap. on Fault-Tolerant Computing (FTCS16), Vienna, July 1986, pp. 84-89. A. Goyal and S. S. Lavenberg, “hIodeling and Analysis of Computer System .4vailability,” IBA1 Research Rep. RC12158. Yorktoivn Heights, Nov. 1986. A. E. Conway and A. Goyal, “Monte Carlo Simulation of Computer System Availability/Reliability Models,“ in Proc. 17th Int. Symp. on Fault-Tolerant Computing (FTCS-17). Pittsburgh, 1987, pp. 230-235. Juan A. Carrasco. “Failure distance-based simulation of repairable faulttolerant systems.” in Proc. 5th Int. Conf. on .llorlelling Techniques and Tools for Computer Performance Ernluation, Torino, February 1991. pp. 337-351. Juan A. Carrasco, ”Efficient transient simulation of failure/repair markovian models,” Technical Report. UPC, June 1990. submitted for publication. Juan A. Carrasco, “Dependability hiodeling in ShlART“. Report, ESPRIT project 1609: SblART (System hleasurement and Architecture Techniques), January 1990. R. E. Barlow and F. Proschan, Statistical Theory of Reliability and Life Testing: Probability Models, Silver Spring. 1981. R. R. hluntz, E. de Souza e Silva. and -1. Goyal. “Bounding Availability of Repairable Computer Systems.“ IEEE Trans. on Computers, vol. 38, no. 12; December 1989. pp. 17111723. C. Dutheillet and S. Haddad. “Aggregation of States in Colored Stochastic Petri Nets: Application to a Slultiprocessor A4rchitecture,“ in Proc. 3rd Int. Il’orkshop on Petri .\-ets and Performance Jlcdels (P.VP.IfSS), Kyoto. December 1989. pp. 30-49. Juan A. Carrasco, “.Automated Construction of Compound Markov Chains from Generalized Stochastic High-Level Petri Nets,” in Proc. 3rd Int. Ii‘orkshop on Petri ,\-ets and Performance Models (P.YP.tf8S), Kyoto, December 1989. pp. 03-103. 456