2001年度日本オペレーションズ・リサーチ学会 秋季研究発表会
2−D−8
Optimal Software Rejuvenation Policies with Discounting
TadashiDohi（01307065），1もkashiDanjou，HiroyukiOkamura（01013754） DepartmentofInbrmationEngineerlng，HiroshimaUniversity thedistributionfunctionsofthetimetosoftwarerquve− nationanditssystemoverhead by F（t）and凡（t）（with densityふ（t）andmeanFLr（＞0）），reSpeCtively・Aftercom− pletingtherepairortherejuvenation，thesoftwaresystem becomesasgoodasnew，andthesoftwareageisinitiated at the beginingofthe next high1y robust state・Conse− quently，Wedefinethetimeintervalfromthebeginingof the system operation to the next one as one cycle，and thesamecycleisrepeatedagalnandagalnOVeraninfinite
time horizon．
Note that the software rejuvenation cycle is measured fromthetimeinstantjustafterthesystementersStatel fromStateO．Ifweconsiderthetimetosoftwarerqiuve− nationasaconstantto，thenitb1lowsthat 〈 珊＝U（f−lo）＝ 0 （1） Wecall亡0（≧0）舶亡んe叩βぴα代rり祝γeγlα如れβCんe血gein thispaperandU（・）istheunitstepfunction・Hence，the underlying stochastic process is a semi-hlarkov rprocess
Withfourregenerativestatest 3．Analysis 1．Introduction SoftwarerqjuvenationisapreventivemaintenanCeteCh− nlquethathasbeenextensivelystudiedintherecentliter− ature【1，2］・Inthispaper，WeCOnSiderageneralizedprob− 1emtoestimatetheoptimalsoftwarerqiuvenationsched− ule．Moreprecisely，thesoftwarerqjuvenationmodelsare formulatedviathesemiTMarkov processes，and theopti− malsoftware rquvenation schedule which minimizes the
expectedtotaldiscountedcostoveraninfinitetimehori− ZOnarederivedanalytically，
2．ModelDescription
Fb1lowingHuanget．al［1】andDohietal・（2】，WeCOn−
Siderthetwo−Stepfailuremodeltodescribetheaglngphe− nomenonin telecommunications bi11ingapplications・De−
finethefo1lowlngfourstates： StateO：high1yrobuststate（normaloperationstate） Statel：failureprobablestate State2：failurest，ate State3：SOftwarerqjuvenationstate
Supposethatallthestatesmentionedaboveareregen−
erationpoints．Morespecifically，1etZbetherandomtime intervalwhenthehigh1yrobuststatechangeStOthefail− ureprobablestate，havingthecommondistributionfunc− tionPr（Z≦t）＝Fb（l）withdensityfo（t）and丘nitemean FLo（＞0）・Justafterthestatebecomesthefailureprobable State，aSyStemfailuremayoccurwithapositiveprobabil− ity．Withoutanylossofgenerality，itisassumedthatthe randomvariableZisobservableduringthesystemopera− tion【1，2】・ DefinethefailuretimeX（fromStatel）andtherepair time Y，having thedistribution functions Pr（X≦t）＝ Fj（t）andPr（Y≦t）＝FL（t），reSpeCtively，Where ff（t） andん（t）aretheassociatedprobabilitydensityfunctions and入f（＞0）andFLa（＞0）aretheirmeanvalues，reSpeC− tively．IfthesystemfailureoccursbeforetriggerlngaSOft− WarereJuVenation，thentherepalrisstartedimmediatelyat that time and is completed after the random time Y
elapses．Otherwise，thesoftwarerqjuvenationisstartedas apreventivemaintenanceofthesoftwaresystem．Denote DefinethefbllowlngCOStCOmpOnentS‥ Cs（＞0）：repaircostperunittime cp（＞0）：rqjuvenationcostperunittime β（＞0）：discounthctor・ Forconvenience，Wedefine
ノ：、㍉
exp（−α5）J（5）d5 （2） ￡（J（α））＝for an arbitrary continuousfunction f（・）and acomplex numberα．Thatis，thefunCtionL：（f（α））istheLaplace transformofthefunctionf（・），
The discounted unit cost for one cycle，i・e・the net presentvalueofonedollarafteronecycle，isformulatedas ∂（fo）＝ ‘し （ 。 〃−ん ト・州、︰ ∞ 〝／ム 〝′−悪
∞ ′ム
♪−−JO ＋ 上 e￣β（坤0＋5）d巧（ご）d凡（z）d凡（5）． −234一 © 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.（i）Ifq（0）＜Oandq（∞）＞0，thenthereexistsafinite andunlqueOptimalsoftwarereJuVenationschedulet岩 （0＜t岩＜∞）satisfyingq（t岩）＝0，andtheminimum expectedtotaldiscountedcostis rC（t岩）＝ c5Z（Jα（β））rJ（f岩トcpZ（ん（β））（β＋り（f岩）） （3） Theexpectedtotaldiscountedcostfbronecycleis c5e−β（トトエ＋欄） V（￡0） ×d亡dF′（諾）d凡（z）d凡（y） ＋上 上
．（．
J5
cpe榊0再） β〈β姉（β）｝＋［瑚（β））−qん（β）｝］γ∫㈲）■ （8） （ii）Ifq（0）≧0，thentheoptimalsoftwarer毎uvenation SCheduleis t岩 ＝0，i．e．itis optimalto start the SOftware rQjuvenationjust after entering the failureprobablestate，andtheminimumexpectedtotaldis− COuntedcostisgivenbyTC（0）． （iii）Ifq（∞）≦0，thentheoptimalsoftwarerQjuvenation SCheduleist岩→∞，！．e．itisoptimalnottocarryout theso軋warerquvenation，andtheminimumexpected totaldiscountedcostisgivenbyTC（∞）・ （2）SupposethatthefailuretimedistributionisDFR（de− CreaSingfailurerate）undertheassumption（A−1）・Then， the expected totaldiscounted costfunction TC（to）is a
COnCaVefunctionoflo，andtheoptimalsoftwarerQjuvena− tionscheduleisl岩＝00rt岩→00．
From the theorem above，itis seen that the optimal SOftware rquvenation policy t岩can be calculatedif the underlyingfailuretimedistributionFj（t）andothermodel
parametersaregiven．Ontheotherhand，iftheknowledge
OfFj（t）isnot available，anOnparametricmethod based On the modified totaltime on test statistics［3】can be appliedtoestimatet岩fromthecompletesampleoffailure
timedata・These detailed resultswi11be reportedin the
conference．
×dtd巧（ェ）d穐（z）dn（5） （4）
Theexpected totaldiscounted cost over aninfinite time horizonisglVenby Cく：） rc（to）＝∑v（瑚（fo）k＝咋0）／和0）・ た＝0 （5） Thentheproblemistoseektheoptimalsoftwarerqiuve− nationschedulet岩whichminimizesTC（to）． DefinethenumeratorofthederivativeofTC（壬0）with respecttoto，dividedbythefactor戸，（to）e▼βto，aSq（to）， 慮．e． ￡（ふ（β）） ト恥（β）輌0）−Cp恥（β）｝ 9（to） o ））］恥）＋瑚（β）） ×（β＋り（f ×［（拙（β）｝一姉（β）｝）γ㈲ −β￡（ん（β）） V（to）， （6） whererf（t）＝fI（t）／戸f（t）isthehilurerateandingeneral 石（・）＝1−4）（・）．Itisassumedthatrf（t）iscontinuousand di鮎rentiablewithrespecttot． Wemakethefo1lowlngaSSumption： （A−1）C諾嶽鵠ヱ嵩謂）＞rC（fo）・ In［2】，itisprovedthroughthereductionargument that （cβ〃α一年〃r）／（〝α−〝r）＞1imβ→0β・rC（fo）bralltoif twoparametricassumptionsFLa＞〃，andcs＞cphold・In theassumption（A−1），takingβ→Oyields Refもrences 【1】Huang，Y・，Kintala，C・，Kolettis，N・andFunton，N・D・ （1995），SoftwarerQjuvenation‥analysis，mOduleand applications，PrDC・25thlEEEInt，lSymp・On
nlerant Computin9，381−390，IEEE CS Press，Los Alamitos，CA．
【2］Dohi，T・，Go畠eva−Popstojanova，K・andTヒivedi，K・S， （2000），Estimatingsoftwarerqjuvenationschedulein highassuranCe SyStemS，77Le ContputerJoumal（in press）．
【3］Bergman，B・and Kle勾6，B・（1983），TTT−tranSform and age replacements with discounted costs，Naval
月e5．⊥0タ由．Q祝αr豪．，30，63ト639． c占Z（揖β））−CpZ（〃β））＿C町 （7） 1illl β二らβ【￡（ム（β））−￡（ん（β））】 〃α∼〃r 丘omthel’Hospital’stheorem．Inotherwords，theassump− tion（A−1）may holdin the most cases with su瓜ciently
smal1discount，factor．
Thefbllowlng reSultgives theoptimalsoftware rejuve− nationpolicywithdiscounting． Theorem：（1）Supposethatthefailuretimedistribution isstrictlyIFR（increasingfailurerate）undertheassump− tion（A−1）・ ー235− © 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.
