on nodes connections
Figure2: TheXMLdenitionoftheFT Metaclass
AMetaclassdenesthekindofnodesandedges thatamodelmayinclude,e.g. types
ofevents,gatesandarcsinFig.2. Nodes,edges, andformalismsthemselvesareallcalled
elements.
Edgeshavealsoassociatedasetofconstraintsthattellwhichkindofelementsthatedge
mayconnect. Forexample,the\Arc"elementdenedinFig.2specieswhichconnections
areallowedbetween eventsandgates. Constraintscanalsospecifya cardinality: thatis
themaximumnumberofedgesofthatkindthatmaystart\from"orend\to"aparticular
element.
Sinceconstraintsareexpressedintermsofelements,anedgecanconnectnotonlytwo
nodes,butalsootheredgesandsub-models. Asaresult,ModelClassesorModelObjects
canbehandledastheywerenodes.
All elementshave one or more \properties" that arethe private attributes ofthe
ModelClassesandthatwillbesetwhencreatingaModelObject. Anadditionalattribute
calledvisibility isused to denethe interfaceelements: the edges can connect elements
accordingtotheirconstraints,andalsotheelementsofsub-modelsthathavethevisibility
propertysettotrue.
Turningtoourexample,anextension ofthe FTMetaclasswithaRepairEvent(RE)
isnecessarytoextendtheFTformalismandanalysistechniquesbyaddingrepairactions.
InFig. 3 the RFT Metaclass is shown that inheritsfrom FT and extends it by adding
a \Repair" node and a proper edge so that the \Repair"node can be linked to one of
the events in the tree. The \Repair" node isan implicitnode: it relies onan external
specicationoftherepairpolicy.
A\Repair"nodecorrespondstoaRB(RepairBlock),andsinceseveralrepairpolicies
<?xml version="1.0" encoding="UTF-8" standalone="no"?>
<!DOCTYPE formalism SYSTEM "formalism.dtd">
<formalism parent="FT.xml" name="RFT">
<nodeType parent="BasicEvent" name="RepBE">
<propertyType name="RepairDistribution" default="EXP 1.0"/>
</nodeType>
<nodeType parent="" name="RepairNode">
<propertyType name="Name" default=""/>
<propertyType name="RepairDistribution" default="EXP 1.0"/>
<propertyType name="Policy" default="SingleRepairTime"/>
</nodeType>
<edgeType parent="" name="RepairArc">
<propertyType name="RepLabel" default=""/>
<propertyType name="EventLabel" default=""/>
<constraint fromType="RepairNode" fromCardinality="1"
toType="Event" toCardinality="1"/>
</edgeType>
</formalism>
Figure3: TheRFTMetaclassderivedfromFT
arepossible, itmustinclude someinformation onthe particular policy itrepresents. In
this paper we assume that a repair block causes the elimination of the fault event by
eliminating all its potential causes. The properties \Policy" and \RepairDistribution"
willbe usedtodenetheimplicitbehavioratthe solutiontime.
Finally, the RFT Metaclassredenes the \BasicEvent" node ('RepBE' in Fig.3) by
addinganew property\RepairDistribution"usedto specify the timedistributionofthe
repairaction neededwhenthatBE occurs.
3.2 Model Classesand Model Objects in DrawNET++
Classesareusefultocreatealibraryofsub-modelstobeusedbyanenduser. Fig.4showsa
FTatmodelrepresentingasubsystemofthesecondversionofthemultiprocessorsystem
(withnoshared memory). AFT sub-modelisa subtreewhoseinterfaceisdenedto be
thetopeventofthesubtree.
OncetheFTatmodelofthesubsystemhasbeencreated,itcanbesavedasaModel
Class,since it representsanabstractionof a systemcomponent. The nal modelofthe
multiprocessorsystemwillbeacomposedmodelcontainingthreeinstancesofthisModel
Class,i.e. the threeModel Objects SUB IND1;SUB IND2;SUB IND3 graphically
representedbysquaresinFig.5 (a). They areobtainedbyspecifyingdierentnamesfor
eachobjectandgivingdistinctvaluestothepropertiesoftheelementsoftheModelClass
inFig.4,forexamplethepropervaluesofthefaultratesoftheBEs. ThemodelinFig.5(a)
isaweakaggregation(i.e.,amodelobtainedbyinstantiatingandconnectingsubmodels).
Fig.5 (b)showsahigh levelrepresentation ofthesystemobtainedafterapplyingstrong
aggregation(i.e. transformingthemodelinFig.5(a)intoanewsubmodelwhichhidesthe
interfacesofthethreesubmodelscomposingit).Theinterfaces(eventsSUB
i
,i2f1;2;3g)
usedtoconnectthethreeModelObjectstotheG2of3gate(inFig.5(a))havebeenhidden
andtheyarenolongervisible. Thewholeprocessorsubsystemhas been encapsulatedin
aModelClasswhoseinstance named\processing"isusedtobuildthecompletemodel.
4 GSPN representation of RFTs
Thissection introducesthe basic conceptsneededto describethe multi-solutionmethod
ofSec. 5. Inparticular itisexplained howanRFT component canbe transformedinto
aGSPNmodelby(1)automatic translationofFT objectsand(2)compositionwiththe
GSPNimplicitlydenedbyeach RB.
Automatic translation of a FT into a GSPN. Let us briey explain the FT to
GSPNtranslationalgorithm: formoredetailsthe readercanrefer to[11 ,4 ]. Each Basic
Event BE in the FT ismodeled withthe subnetin Fig. 6(a): the ringtime associated
with the timed transition represents the time to failure of that BE. Each gate in the
FT is translated into one or more transitions, connected to the places representing the
input/outputeventsofthe gate(see Fig.6(b)and(c)).
ThesubnetrepresentingallBEs,andthoserepresentingthegates,arethensuperposed
onplaceswithequallabel,formingthe logicstructureofthe FT.Anexampleisgivenin
Fig.6(d),wherethe translationofthesubtreeofthe multiprocessorFTstartingatevent
CD1isshown. ThestatespaceoftheGSPNrepresentsallpossibleevolutionsofthemodel
throughitspossiblefailurestates.
GSPNmodelsofrepairboxes. LetusintroducesomepossiblesemanticsfortheRBs
andtheir translationinterms ofa GSPNthat canbe automaticallycomposed(through
STEP 1 STEP 2
STEP 2
STEP 3
(a)
(b)
Figure5: Anexampleofweakandstrongaggregation: theFTmodelof(a)theprocessor
subsystemand(b)themultiprocessorsystem
(a) (b) (c)
Figure6: FTtoGSPNtranslationrules: (a)BE (b)OR(c)AND (d)asubtree
placeandtransitionsuperposition)withtheGSPNofthe FT(generatedas explainedin
theprevioussubsection).
Let OE
1
be a repairable event of an FT (i.e. an event connected with an RB): it
identiesa subtreeofalleventsthatmay leadtothe occurrenceofOE
1
. Let usassume
that OE
1
represents the failureof a givensystem component C: dependingonthe type
of tree originating in OE
1
, the repair actions allowing to bringcomponent Cback into
the operational state may dier. Hence the RB should include enough information to
express the repairstrategy tobe followed: inthe rest ofthissection we shallconsidera
repairstrategycalledcomplete repair,consistingofrepairingallthe basicsubcomponents
corresponding to the BE leaves of the subtree originating in OE
1
(which has the side
eect ofrepairing allthe eventson the path from the leaves to OE
1
). Otherstrategies
areconceivable, andinprincipleanystrategythatmaybemodeledbyaGSPNmightbe
directlyembeddedin the RB node by explicitlyassociating a GSPNsubmodelto it. In
thissection we show howthe GSPNof the complete repair strategycan be describedin
parametricformandautomaticallygenerated.
LetusconsiderthemultiprocessorFTexampleinFig.1. Ifarepairboxisconnectedto
eventCD1,thecomplete repairstrategywouldrequiretorepairthe BEDisk11,Disk12
andCPU1 (andhence indirectlyalsoD1). Observe that repairingCD1 mayaectalso
thefaultstatusofSUB 1,ProcandtheTE.
Therearesomepossiblechoicesinmodelingthe completerepairstrategy:
(1) the time required to perform the whole repair may be modeled by a single timed
transitionorasa(parallelorsequential)compositionofseveraltimes,oneforeachoccurred
BEinthesubtree;intheformercase,thistimeshoulddependonwhichsubsetofBE has
causedfailureeventOE
1
;
(2) possibility of new BE occurrence during the repair of OE
1
: when component C is
underrepair,isitpossiblethatsomenotyetfailedBE failsduringthe repair? Andonce
a subcomponent has been repaired, may it fail again before the whole repair of C has
completed? (this last case of course can be considered only if the OE
1
repair action is
modeledasa setofseparate repairactions,oneforeachbasicsubcomponent);
(3)innite versus niterepair facilities: it mightbe necessary toconsider the fact that
a repair action can take place onlyif a repair facilityis availableto perform it. Repair
facilitiesmaybelocaltoaRB,orsharedbyseveralRBs. Ifatmostnrepairfacilitiesare
availabletoagivenRB, thetimeneededto completethe repairwillhave tobeadjusted
for the assignment of such facilities to RBs (e.g. a policy based on priorities, with or
withoutpreemption).
LetussketchtwoparametricGSPNsmodelingtherepairofagivencomponent,both
assumingthatnewBEsmayoccurduringtherepair,anddieringinthenumberoftimed
transitionsusedtorepresentthe wholerepair. Incaseseveraltimedtransitionsareused
tomodeltherepairweassumethatanalreadyrepairedBEcannotoccuragainbeforethe
wholecomponent Crepair has completed. For the sake ofspace we make a simplifying
assumption: the subtree originating in OE
1
does not contain any shared BE (in other
words, anypath fromthe TEto the leaves ofOE
1
, contain OE
1
). Observe that shared
BEs may exist since anFT may actually be a DAG instead of a tree (as is in the case
oftherunningexamplewhena uniquesharedmemoryisusedforreplacingafailedlocal
memory).
Thetwo GSPNmodelsofa repairboxforCD1aredepictedinFig.7andFig.8: the
subtreeoriginatingin CD1includes the eventD1 andbasic eventsDisk11;Disk12and
CPU1. Moreover,onthepathfromtheTEtoCD1therearetwoevents,namelySUB 1
andProc. The two modelscanbeeasilygeneralized toanarbitrarynumber ofBEsand
intermediate events (by repeating the same pattern for each BE and event in the
sub-tree). Therstmodelcomprisesanimmediatetransitionandaplace(StartRepCD1and
RepCD1) representingthe startofrepair,a timedtransitionRepTimeCD1 modelingthe
timeneededtocompletetherepairandasubnetforthedeletionofthetokensrepresenting
afailurefromallplacescorrespondingtoeventsinCD1subtree,aswellasfromtheplaces
correspondingtotheTEandtheeventsonthepathfromtheTEtoCD1(intheexample
SUB 1andProc). By sodoing,not onlyalleventspotentially causingCD1arecleared
uponrepair,buttheeectoftherepairisalsopropagatedtoalltheeventswhichdepend
onCD1,allthewayuptotheTE:incasetherepairofCD1isnotsuÆcienttomakethe
uppereventsoperational,thentheGSPNshallautomaticallyregenerate theappropriate
tokens in the correspondingplaces usingthe immediate transitions representing the FT
gateslogic(transitionstor1;t or2andt andintheexampleofFig.6(d)).
Thesecondmodelisslightlymorecomplex,sinceseveraltimedtransitionsareincluded
(R epDisk11, R epDisk12 andR epCPU1), representing the repair timeof a single basic
subcomponent. The enablingofthistransitionsisconditionedonthe factthatthe
corre-spondingfailurehasoccurred(e.g. inputplaceCPU1 ko)andthat therepairaction has
started(inputplaceRepCD1). Whentherepairhascompleted,placeCPU1repbecomes
marked, place CPU1ko is emptied, while place CPU1 remains marked (preventing the
occurrenceoffurtherfailuresforCPU1). The sameholdsforeach basiceventBEiinthe
subtree. WhenallBEsareOK(placesBEiko allempty)the repairhasnished,andall
failuretokenscanberemoved(bythesamesubnetofhighpriorityimmediatetransitions
alreadyexplained forthe GSPNinFig. 7). Observe thatin thismodel we areassuming
thatthere areat least asmanyrepairfacilities as the number ofBEs in the subtree: in
fact,therepairactionsofallBEscanproceedinparallel.
Othervariantsofthesemodelsarepossible,forexampleforhandlingsharedBEs,for
modelinglimitedrepairfacilities,orforforcingagivenorderin therepairofthe BEin a
subtree: forspacereasontheyarenotpresentedinthispaper.
Therepairsubmodel(s)canbecomposedwiththeGSPNrepresentationoftheFTby
applyinga compositionoperator whichglues togethertwo modelsby superposingplaces
or transitions withsame labelin the two nets: in our case the models shouldbe
super-posedovertheplacesrepresentingevents,andonthetransitionsBEiFail,representingthe
D1
nexttoanimmediatetransitiontmeansthatthaspriorityi.
Figure7: Sketchofrepairnetwithonlyonerepairtime
Disk11ko
Figure8: Sketch ofrepairnetwithseveralrepairtimes.