Research On Resources Allocation In Distributed Systems Oriented At Optimal Reliability Design

Referring to the ability of a system to work continuously in a certain period of time,reliability is an important indicator in system design. However, system reliability isoften improved at the expenses of cost increase. To improve the continuous workingability of a system and to achieve the balance between reliability improvement andresources cost increase at the same time, optimal system reliability design has arousedthe attention of many researchers since1960s. With the increase of system scale andcomplexity, it becomes more important and gradually more difficult to optimize systemreliability.The research work in this thesis is supported by the Major Research Project of theNational Natural Science Foundation of China “Behavior monitoring and dependableevolution of large-scale distributed software systems”. Comparing with reliabilityoptimization in traditional systems, the reliability assurance measures in distributedsystems has changed, resulting in new reliability optimization problems. First of all, adistributed system couldn’t be represented as a single-level system due to its large scaleand multilevel structure is often used instead. It becomes a new problem of how toallocate redundancy appropriately in multilevel systems. Secondly, the reliability ofcomponents in distributed system couldn’t be guaranteed by traditional testing method.To improve the component reliability, monitoring mechanism is often used for dynamiccomponent failover. Thus, it is also a major problem of how to optimize systemreliability through monitoring resources allocation. Aiming at solving the new problemsin optimal distributed system reliability design, this thesis generally concentrates on twoaspects: multilevel redundancy allocation and monitoring resources allocation. Tooptimize the system reliability and resources, we concentrated on three fields includingthe algorithm for multilevel system redundancy allocation, multi-objective monitoringresources allocation and the resources allocation with multiple choices of reliabilityassurance. The detailed research results and the major contributions of this paper aresummarized as follows.①A survey is conducted on the system reliability evaluation methods, theresources allocation models for reliability optimization and the correspondingalgorithms. The different ways of reliability representation and the correspondingapplication is summarized including various reliability evaluation methods for single component and the overall system. Existing reliability optimization oriented resourcesallocation problems are divided into four categories, among which the redundancyallocation problem and testing resources allocation problems are studied in detail. Thecommon optimization methods including exact methods and heuristic algorithms arealso analyzed and compared.②The multilevel system redundancy allocation problem has been studied and theallocation algorithm has been improved. Based on the existing multilevel redundancyallocation model, the multilevel system reliability optimization problem under theconstraint of redundancy cost has been analyzed and much attention has been paid onmultilevel optimization algorithm. A two-dimensional array encoding mechanism isemployed to represent the structure of multilevel redundant systems to overcome theshortcomings of existing hierarchical encoding mechanism. A memetic algorithm isdeveloped using this encoding method to search the optimal result for the allocationproblem and a random-walk strategy is used as the local search method to search theneighbors of local best solutions. Experiments are conducted to compare our algorithmwith existing multilevel redundancy allocation algorithms and to prove the effectivenessof our algorithm. The experimental results have shown that the two-dimensionalencoding method could be used in memetic algorithms effectively and the local searchstrategy could improve the global search capabilities of memetic algorithm, resulting inbetter results.③Multi-objective monitoring resources allocation model and the correspondingalgorithms has been studied oriented at system reliability optimization. First of all, themonitoring and dynamic failover mechanism in distributed systems using serviceoriented architecture is analyzed and a reliability model for components using this kindof mechanism is presented. Secondly, a modified architecture-based reliability analysismodel is used to evaluate the overall system reliability. On the top of that, two differentkinds of monitoring resources cost are analyzed and a monitoring resources allocationmodel is built under the system reliability constraint. This model chooses theappropriate monitoring rate for each component through minimizing the monitoringcost. A random walk strategy based memetic algorithm is also used to solve the problem.Monitoring resources allocation model and the algorithm is also used for multilevelredundant systems. Experimental results prove the necessity and impact of monitoringresources allocation in reliability optimization. After analyzing the changing effect ofmonitoring resources allocation with the increase of time, we compare the memetic algorithm used with some existing multi-objective evolutionary algorithms. Thecoverage rate and hypervolume indicator have both proved the superiority of ouralgorithm in this allocation problem.④The resources allocation problem for systems with multiple choices ofreliability assurance strategies are researched the corresponding algorithm has beenpresented. Redundancy and monitoring are the two major mechanisms taken intoconsideration. For both single level system and multilevel system, the reliability andcost of systems are analyzed considering multiple choices on each component. Based onthese models, a multi-objective resources allocation model is presented under thereliability constraint. A triple-element encoding mechanism is used for single levelsystem to encode the choice of reliability assurance mechanism and the correspondingparameters. The two-dimensional encoding mechanism is also modified to represent themultiple choices of strategies in multilevel system, which could encode the redundancyvalue in subsystem and the monitoring rate in components. Finally, the memeticalgorithms for both single level system and multilevel systems are improved to copewith the three-element encoding mechanism. Experimental results have proved theeffectiveness of the three-element encoding mechanism. Comparison with existinggenetic algorithms using three-element encoding method has shown the effectivenessand superiority of our algorithm in searching solution spaces. The changing effect ofresources allocation with the increase of time is also discussed through the results.