串并联系统中支持实时替换的混合冗余策略优化
|
摘要
在需要长时间可靠运行的软件系统中,由于持续运行时间和任务响应速度的要求增加,工作组件在被探测到失效后将被冗余组件实时替换.但现有可靠性优化研究通常假设冷备份冗余在所有积极冗余组件失效后才使用.针对支持实时替换的混合冗余策略,对其冗余度优化分配进行研究.该策略不仅能够保障系统可靠性,而且能够保障系统性能,故选用实时可用性和任务完成效率两类约束条件,建立冗余配置代价最小化模型.基于马尔可夫链理论对可靠性及性能两类系统指标进行定量分析;采用数值计算方法对非线性的状态分析模型进行计算;改进二元组编码遗传算法对上述优化问题进行求解.采用实例对串并联系统中实时可用性及任务完成效率的分析进行了说明,并对优化冗余分配模型进行了验证.实验结果表明,在相同冗余度下,支持实时替换的混合冗余策略在任务完成效率方面优于传统的混合冗余策略.所以,在相同约束条件下不同混合冗余策略需要采用不同的冗余优化配置方案.
In long-time running reliable software systems, as the demand for continuous execution time and task response speed increases, the redundant component needs to be instantly switched when failure occurs. However, reliability optimization is often conducted under the assumption that cold standby redundancy is only activated when all active components fail. This paper tackles the redundancy allocation problem for a mixed redundancy strategy with instant switching to ensure system reliability as well as performance. The redundancy allocation model is built to minimize redundancy configuration cost under the transient availability and job completion rate constraints. Two system performance metrics are analyzed on top of the state transition diagram using Markov-chain theory. A numerical method is used to compute the non-linear model, and a genetic algorithm is used to solve the optimization model based on the double-element encoding mechanism. Illustrative examples are presented to explain the analysis of system transient availability and job completion rate as well as the allocation result under constraints. Experiment results indicate that with the same redundancy, the job completion rate of systems with the new mixed strategy is higher than the systems with traditional strategy. Thus, different redundancy should be allocated for different kinds of redundancy strategies, even under the same constraints.
In long-time running reliable software systems, as the demand for continuous execution time and task response speed increases, the redundant component needs to be instantly switched when failure occurs. However, reliability optimization is often conducted under the assumption that cold standby redundancy is only activated when all active components fail. This paper tackles the redundancy allocation problem for a mixed redundancy strategy with instant switching to ensure system reliability as well as performance. The redundancy allocation model is built to minimize redundancy configuration cost under the transient availability and job completion rate constraints. Two system performance metrics are analyzed on top of the state transition diagram using Markov-chain theory. A numerical method is used to compute the non-linear model, and a genetic algorithm is used to solve the optimization model based on the double-element encoding mechanism. Illustrative examples are presented to explain the analysis of system transient availability and job completion rate as well as the allocation result under constraints. Experiment results indicate that with the same redundancy, the job completion rate of systems with the new mixed strategy is higher than the systems with traditional strategy. Thus, different redundancy should be allocated for different kinds of redundancy strategies, even under the same constraints.
引文
[1]Qiu W,Zheng Z,Wang X,Yang X,Lyu MR.Reliability-Based design optimization for cloud migration.IEEE Trans.on Services Computing,2014,7(2):223?236.[doi:10.1109/tsc.2013.38]
[2]Kuo W,Wan R.Recent advances in optimal reliability allocation.IEEE Trans.on Systems,Man,and Cybernetics Part A:Systems and Humans,2007,37(2):143?156.[doi:10.1109/tsmca.2006.889476]
[3]Ardakan MA,Hamadani AZ.Reliability optimization of series-parallel systems with mixed redundancy strategy in subsystems.Reliability Engineering&System Safety,2014,130:132?139.[doi:10.1016/j.ress.2014.06.001]
[4]Chern MS.On the computational complexity of reliability redundancy allocation in a series system.Operations Research Letters,1992,11(5):309?315.[doi:10.1016/0167-6377(92)90008-q]
[5]Tavakkoi-Moghaddam R,Safari J,Sassani F.Reliability optimization of series-parallel systems with a choice of redundancy strategies using a genetic algorithm.Reliability Engineering&System Safety,2008,93(4):550?556.[doi:10.1016/j.ress.2007.02.009]
[6]Yang CT,Liu JC,Hsu CH,Chou WL.On improvement of cloud virtual machine availability with virtualization fault tolerance mechanism.Journal of Supercomputing,2014,69(3):1103?1122.[doi:10.1007/s11227-013-1045-1]
[7]Zhang Z,Xiao L,Zhu M,Ruan L.Mvmotion:A metadata based virtual machine migration in cloud.Cluster Computing,2014,17(2):441?452.[doi:10.1007/s10586-013-0245-z]
[8]Caserta M,Voss S.An exact algorithm for the reliability redundancy allocation problem.European Journal of Operational Research,2015,244(1):110?116.[doi:10.1016/j.ejor.2015.01.008]
[9]Liu Y,Huang HZ,Wang Z,Li Y,Yang Y.A joint redundancy and imperfect maintenance strategy optimization for multi-state systems.IEEE Trans.on Reliability,2013,62(2):368?378.[doi:10.1109/tr.2013.2259193]
[10]Coit DW,Liu J.System reliability optimization with k-out-of-n subsystems.Int’l Journal of Reliability,Quality and Safety Engineering,2000,7(2):129?142.[doi:10.1142/S0218539300000110]
[11]Coit DW.Cold-Standby redundancy optimization for nonrepairable systems.IIE Trans.,2001,33(6):471?478.[doi:10.1023/a:1007689912305]
[12]Coit DW.Maximization of system reliability with a choice of redundancy strategies.IIE Trans.,2003,35(6):535?543.[doi:10.1080/07408170304420]
[13]Chambari A,Rahmati SHA,Najafi AA,Karimi A.A bi-objective model to optimize reliability and cost of system with a choice of redundancy strategies.Computers and Industrial Engineering,2012,63(1):109?119.[doi:10.1016/j.cie.2012.02.004]
[14]Chambari A,Najafi AA,Rahmati SHA,Karimi A.An efficient simulated annealing algorithm for the redundancy allocation problem with a choice of redundancy strategies.Reliability Engineering and System Safety,2013,119:158?164.[doi:10.1016/j.ress.2013.05.016]
[15]Safari J.Multi-Objective reliability optimization of series-parallel systems with a choice of redundancy strategies.Reliability Engineering and System Safety,2012,108:10?20.[doi:10.1016/j.ress.2012.06.001]
[16]Ardakan MA,Hamadani AZ.Reliability optimization of series-parallel systems with mixed redundancy strategy in subsystems.Reliability Engineering and System Safety,2014,130:132?139.[doi:10.1016/j.ress.2014.06.001]
[17]Mohamed N,Al-Jaroodi J.Mid Cloud:An agent-based middleware for effective utilization of replicated Cloud services.SoftwarePractice and Experience,2015,45(3):343?363.[doi:10.1002/spe.2235]
[18]Cores I,Rodriguez G,Martin MJ,Gonzalez P,Osorio RR.Improving scalability of application-level checkpoint-recovery by reducing checkpoint sizes.New Generation Computing,2013,31(3):163?185.[doi:10.1007/s00354-013-0302-4]
[19]Cui X,Mills B,Znati T,Melhem R.Shadow replication:An energy-aware,fault-tolerant computational model for green cloud computing.Energies,2014,7(8):5151?5176.[doi:10.3390/en7085151]
[20]Levitin G,Xing LD,Johnson BW,Dai YS.Mission reliability,cost and time for cold standby computing systems with periodic backup.IEEE Trans.on Computers,2015,64(4):1043?1057.[doi:10.1109/tc.2014.2315644]
[21]Pietrantuono R,Russo S,Trivedi KS.Software reliability and testing time allocation:An architecture-based approach.IEEE Trans.on Software Engineering,2010,36(3):323?337.[doi:10.1109/tse.2010.6]
[22]Trivedi KS.Probability and Statistics with Reliability,Queuing,and Computer Science Applications.2nd ed.,New York:John Wiley and Sons,2001.
[23]Reibman A,Trivedi K.Numerical transient analysis of Markov-models.Computers&Operations Research,1988,15(1):19?36.[doi:10.1016/0305-0548(88)90026-3]
[24]Goel AL,Okumoto K.Time-Dependent error-detection rate model for software reliability and other performance-measures.IEEE Trans.on Reliability,1979,28(3):206?211.[doi:10.1109/TR.1979.5220566]
[25]Levitin G,Lisnianski A,Ben-Haim H,Elmakis D.Redundancy optimization for series-parallel multi-state systems.IEEE Trans.on Reliability,1998,47(2):165?172.[doi:10.1109/24.722283]
[26]Tian Z,Levitin G,Zuo MJ.A joint reliability-redundancy optimization approach for multi-state series–parallel systems.Reliability Engineering and System Safety,2009,94(10):1568?1576.[doi:10.1016/j.ress.2009.02.021]
[2]Kuo W,Wan R.Recent advances in optimal reliability allocation.IEEE Trans.on Systems,Man,and Cybernetics Part A:Systems and Humans,2007,37(2):143?156.[doi:10.1109/tsmca.2006.889476]
[3]Ardakan MA,Hamadani AZ.Reliability optimization of series-parallel systems with mixed redundancy strategy in subsystems.Reliability Engineering&System Safety,2014,130:132?139.[doi:10.1016/j.ress.2014.06.001]
[4]Chern MS.On the computational complexity of reliability redundancy allocation in a series system.Operations Research Letters,1992,11(5):309?315.[doi:10.1016/0167-6377(92)90008-q]
[5]Tavakkoi-Moghaddam R,Safari J,Sassani F.Reliability optimization of series-parallel systems with a choice of redundancy strategies using a genetic algorithm.Reliability Engineering&System Safety,2008,93(4):550?556.[doi:10.1016/j.ress.2007.02.009]
[6]Yang CT,Liu JC,Hsu CH,Chou WL.On improvement of cloud virtual machine availability with virtualization fault tolerance mechanism.Journal of Supercomputing,2014,69(3):1103?1122.[doi:10.1007/s11227-013-1045-1]
[7]Zhang Z,Xiao L,Zhu M,Ruan L.Mvmotion:A metadata based virtual machine migration in cloud.Cluster Computing,2014,17(2):441?452.[doi:10.1007/s10586-013-0245-z]
[8]Caserta M,Voss S.An exact algorithm for the reliability redundancy allocation problem.European Journal of Operational Research,2015,244(1):110?116.[doi:10.1016/j.ejor.2015.01.008]
[9]Liu Y,Huang HZ,Wang Z,Li Y,Yang Y.A joint redundancy and imperfect maintenance strategy optimization for multi-state systems.IEEE Trans.on Reliability,2013,62(2):368?378.[doi:10.1109/tr.2013.2259193]
[10]Coit DW,Liu J.System reliability optimization with k-out-of-n subsystems.Int’l Journal of Reliability,Quality and Safety Engineering,2000,7(2):129?142.[doi:10.1142/S0218539300000110]
[11]Coit DW.Cold-Standby redundancy optimization for nonrepairable systems.IIE Trans.,2001,33(6):471?478.[doi:10.1023/a:1007689912305]
[12]Coit DW.Maximization of system reliability with a choice of redundancy strategies.IIE Trans.,2003,35(6):535?543.[doi:10.1080/07408170304420]
[13]Chambari A,Rahmati SHA,Najafi AA,Karimi A.A bi-objective model to optimize reliability and cost of system with a choice of redundancy strategies.Computers and Industrial Engineering,2012,63(1):109?119.[doi:10.1016/j.cie.2012.02.004]
[14]Chambari A,Najafi AA,Rahmati SHA,Karimi A.An efficient simulated annealing algorithm for the redundancy allocation problem with a choice of redundancy strategies.Reliability Engineering and System Safety,2013,119:158?164.[doi:10.1016/j.ress.2013.05.016]
[15]Safari J.Multi-Objective reliability optimization of series-parallel systems with a choice of redundancy strategies.Reliability Engineering and System Safety,2012,108:10?20.[doi:10.1016/j.ress.2012.06.001]
[16]Ardakan MA,Hamadani AZ.Reliability optimization of series-parallel systems with mixed redundancy strategy in subsystems.Reliability Engineering and System Safety,2014,130:132?139.[doi:10.1016/j.ress.2014.06.001]
[17]Mohamed N,Al-Jaroodi J.Mid Cloud:An agent-based middleware for effective utilization of replicated Cloud services.SoftwarePractice and Experience,2015,45(3):343?363.[doi:10.1002/spe.2235]
[18]Cores I,Rodriguez G,Martin MJ,Gonzalez P,Osorio RR.Improving scalability of application-level checkpoint-recovery by reducing checkpoint sizes.New Generation Computing,2013,31(3):163?185.[doi:10.1007/s00354-013-0302-4]
[19]Cui X,Mills B,Znati T,Melhem R.Shadow replication:An energy-aware,fault-tolerant computational model for green cloud computing.Energies,2014,7(8):5151?5176.[doi:10.3390/en7085151]
[20]Levitin G,Xing LD,Johnson BW,Dai YS.Mission reliability,cost and time for cold standby computing systems with periodic backup.IEEE Trans.on Computers,2015,64(4):1043?1057.[doi:10.1109/tc.2014.2315644]
[21]Pietrantuono R,Russo S,Trivedi KS.Software reliability and testing time allocation:An architecture-based approach.IEEE Trans.on Software Engineering,2010,36(3):323?337.[doi:10.1109/tse.2010.6]
[22]Trivedi KS.Probability and Statistics with Reliability,Queuing,and Computer Science Applications.2nd ed.,New York:John Wiley and Sons,2001.
[23]Reibman A,Trivedi K.Numerical transient analysis of Markov-models.Computers&Operations Research,1988,15(1):19?36.[doi:10.1016/0305-0548(88)90026-3]
[24]Goel AL,Okumoto K.Time-Dependent error-detection rate model for software reliability and other performance-measures.IEEE Trans.on Reliability,1979,28(3):206?211.[doi:10.1109/TR.1979.5220566]
[25]Levitin G,Lisnianski A,Ben-Haim H,Elmakis D.Redundancy optimization for series-parallel multi-state systems.IEEE Trans.on Reliability,1998,47(2):165?172.[doi:10.1109/24.722283]
[26]Tian Z,Levitin G,Zuo MJ.A joint reliability-redundancy optimization approach for multi-state series–parallel systems.Reliability Engineering and System Safety,2009,94(10):1568?1576.[doi:10.1016/j.ress.2009.02.021]