分散式系統K節點集合之可靠度

Abstract

在分散式系統的可靠度分析中，K節點的可靠度是所有在集合K（從分散式系統中所有的處理單元內，選取部分處理單元所組成的集合）中的處理單元皆連通的機率。計算K節點的可靠度有時是非常耗時的，且在許多情況是呈指數複雜度。不同的設計目標、變動的系統假設、以及限制產生了Κ節點可靠度之最佳化有所不同。本論文將焦點集中在具有容量限制的Κ節點可靠度、可靠度導向之工作分配、具有節點個數限制的Κ節點可靠度及分散式系統最小生成樹等之最佳化。具有容量限制的Κ節點可靠度之最佳化之問題，乃是在分散式系統的節點中，選出一組K節點集合，使得K節點集合可靠度為最大，並且擁有足夠的節點容量。顯見這是一個NP-Hard問題。”精確方法”及”k-樹減縮方法”，已探討具有容量限制的k-節點可靠度之最佳化。這些方法不是花費指數比例的計算時間，就是無法求得最佳解。在工作分配問題上，已有許多文獻提出探討。k-DTA模型是在具有某些資源限制下，分配 k個複本的多個程式及其資料檔到分散式系統中，並使其可靠度為最大。這亦是一個NP-Hard問題。傳統演算法在建構分散式系統最小生成樹的困難，在於通訊及同步之問題上。 雖然 窮舉法可求得最佳解，卻不能減少計算時間，所以只適用於處理單元很少時。有時候，一個有效率的演算法且能求得精確解或近似精確解較吸引人。 實用基因演算法領域源自1973年J.H. Holand論文。基因演算法能應用在搜尋龐大、複雜的問題空間。其主要步驟為複製、選取、交配和突變。重複這些步驟，直到終止條件滿足。 Leonard M. Adleman於1994年提出一個生物實驗，利用DNA來解決計算問題。DNA的計算模式在平行處理能力上，提供非常大的潛能。 為減少計算時間和誤差，本論文提出一些啟發式演算法與基因演算法求具有容量限制的Κ節點可靠度、可靠度導向之工作分配與具有節點個數限制的Κ節點可靠度。此外，利用DNA來解決分散式系統最小生成樹。 結果顯示本論文所提方法所需計算可靠度的次數為常數。除此之外，本論文所提方法絕大部分情況皆可求得精確解，當所求得的不是精確解時，其誤差值也非常小。總之，本論文所提方法可以很有效減少計算時間和誤差。

In the reliability analysis of a distributed system, k-node set reliability is defined as the probabilities that all nodes in K are connected, where K denotes a subset of set of processing elements. A k-node set reliability computation can be very hard with exponential in many cases. Differing design goals, varying system assumptions, and constraints yield a disparity of optimal k-node set reliability. This dissertation focuses on the optimization of a k-node set reliability with capacity constraint, reliability-oriented task assignment, a k-node set reliability with order constraint and the minimal spanning trees of a distributed system. A k-node set reliability optimization with a capacity constraint problem is to select a k-node set of nodes in a distributed system such that the k-node set reliability is maximal and possesses sufficient node capacity. It is evident that this is an NP-hard problem. An exact method and a k-tree reduction method have been used to examine k-node set reliability optimization with capacity constraint. Such investigations either spent an exponential time or rarely obtained an optimal solution. There are many investigations has examined the task assignment problem. The k-DTA models the assignment of k copies of both distributed programs and their data-files to maximize the distributed system reliability under some resource constraints. This is also an NP-hard problem. The difficulty of conventional algorithms for constructing minimal spanning trees of a distributed system arises from a communication and synchronization problem. Although the exhaustive method can obtain an optimal solution, it cannot reduce the computational time. Occasionally, an efficiency algorithm with an exact or nearly exact solution is attractive. The field of practical genetic algorithm (GA) opened in 1973 with the J. H. Holland’s paper. GA can be applied to search large, complex problem spaces. The main steps for GA are reproduction, selection, crossover, and mutation. The process of selection, crossover, and mutation is repeated until the termination condition is satisfied. In 1994, Leonard M. Adleman used biological experiments with DNA strands to solve computation problem. The potential benefits of using this particular molecule are enormous due to the massive inherent parallelism of performing concurrent operations on trillions of strands. In this work, to reduce the computational time and the absolute error from the exact solution, some algorithms based on heuristic, and genetic algorithm are proposed for k-node set reliability with capacity constraint, reliability-oriented task assignment, a k-terminal reliability with order constraint. In addition, a DNA algorithm for solution of minimal spanning tree of a DS is also considered. Computational results demonstrate that the number of reliability computation is constant. In addition, the proposed methods can obtain an exact solution in most case. When the proposed methods fail to provide an exact solution, the deviation from the exact solution is only slight. We conclude that these proposed algorithms may effectively reduce the computational time and the deviation from an exact solution. CHINESE ABSTRACT ………………………………………… i ENGLISH ABSTRACT ………………………………………… iii ACKNOWLEDGEMENT ………………………………………v LIST OF TABLES ………………………………………………xiv LIST OF FIGURES …………………………………………….xvi CHAPTER 1 INTRODUCTION ………………………………… 1 1.1 INTRODUCTION …………………………………………………. 1 1.2 NOTATIONS AND ACRONYMS ………………………………….. 5 1.3 DEFINITIONS ……………………………………………………11 1.4 PROBLEM STATEMENTS ………………………………………14 1.4.1 K-terminal reliability with order constraint problem ………14 1.4.2 K-node set reliability with capacity constraint problem ……15 1.4.3 Task assignment reliability …………..……………………16 1.4.4 Minimal spanning tree ………..……………………………17 1.5 SIMULATION ENVIRONMENT ……………………………18 CHAPTER 2 COMPUTATION OF DISTRIBUTED SYSTEM RELIABILITY ………………………………….19 2.1 K-TERMINAL RELIABILITY WITH ORDER CONSTRAINT …19 2.2 K-node set RELIABILITY WITH CAPACITY CONSTRAINT .22 2.2.1 The description of an EM ………….………………………22 2.2.2 The description of an k-tree reduction method (KM) …27 2.3 DISTRIBUTED PROGRAM RELIABILITY ..….………………29 2.4 MINIMAL SPANNING TREE ………………………..…………33 CHAPTER 3 HEURISTIC METHODS ……………………….35 3.1 THE WEIGHT OF A NODE, A LINK AND A VIRTUAL LINK ..35 3.1.1 Compute the weight of each node ………………………….35 3.1.2 Compute the weight of each link ..…………………………37 3.1.3 Compute the weigh of a virtual link .………………………39 3.2 K-TERMINAL RELIABILITY WITH ORDER CONSTRAINT ..40 3.2.1 The concept of KTRPM1 algorithm ……………………….41 3.2.2 The KTRPM1 algorithm …………………………………43 3.2.3 Illustrative examples ………………………………………45 3.2.4 Comparison and discussion ……………………………….48 3.2.5 Conclusions ……………………………………………….54 3.3 k-NODE SET RELIABILITY ……………………………………55 3.3.1 KNRPM1 …………………………………………………..55 3.3.1.1 The KNRPM1 algorithm …….……………………..56 3.3.1.2 An illustrative example ….………………………….59 3.3.1.3 Simulation ………………………………………….60 3.3.1.4 Results and discussion ………………………………61 3.3.2 KNRPM2 …………………………………………………..65 3.3.2.1 The KNRPM2 algorithm …….……………………..66 3.3.2.2 An illustrative example ….…………………………69 3.3.2.3 Simulation …………………………………………72 3.3.2.4 Results and discussion ………………………………72 3.3.3 KNRPM3 …………………………………………………76 3.3.3.1 The KNRPM3 algorithm …….…………………….76 3.3.3.2 An illustrative example ….…………………………80 3.3.3.2 An illustrative example ….…………………………83 3.3.3.4 Results and discussion ………………………………83 3.3.4 KNRPM4 ………………………………………………….89 3.3.4.1 The KNRPM4 algorithm …….…………………….90 3.3.4.2 An illustrative example ….………………………….99 3.3.4.3 Simulation …………………………………………..102 3.3.4.4 Results and discussion ………………………………103 3.3.5 Conclusions …………………………………………………112 3.4 TASK ASSIGNMENT RELIABILITY ………………………113 3.4.1 Construct lists and task assignment ………………………113 3.4.1.1 Construct list APL(fi), AFL(pi) and AR-list …………113 3.4.1.2 Allocate each program and data file according to AR- list and Q1 …………………………………………116 3.4.2 DTAPM1 …………………………….…………………….119 3.4.2.1 The DTAPM1 algorithm ……………………………119 3.4.2.2 An illustrate example ……………………………….121 3.4.3 DTAPM2 …………………………….…………………123 3.4.3.1 The DTAPM2 algorithm ……………………………123 3.4.3.2 An illustrate example ……………………………….126 3.4.4 DTAPM3 …………………………….……………………128 3.4.4.1 The DTAPM3 algorithm ……………………………128 3.4.4.2 An illustrate example ………………………………128 3.4.5 Results and discussion …………………………………….132 3.4.6 Conclusion …………………………………………………136 CHAPTER 4 GENETIC ALGORITHM METHODS ……..…137 4.1 GA BACKGROUND …………………………………………137 4.2 K-NODE SET RELIABILITY—GAKNR ……….………………139 4.2.1 Chromosomal-coding scheme ……………………………..139 4.2.2 Initialization approach …………………………………….139 4.2.3 The objective function …………………………………….140 4.2.4 Genetic reproduction and selection ……………………….141 4.2.5 Genetic crossover operators ……………………………….141 4.2.6 Genetic mutation operator …………………………………142 4.2.7 Replacement strategy and termination rules ……………….142 4.2.8 Genetic algorithm parameter ..……………………………..143 4.2.9 The GAKNR algorithm ……..…………………………….143 4.2.10 An illustrate example ……………………………………147 4.2.11 Results and discussion …….…………………………….149 4.3 TASK ASSIGNMET RELIABILITY …………….……….……….151 4.3.1 Chromosomal-coding scheme ……………………………152 4.3.2 Valid chromosome …………….………………………….153 4.3.3 Initialization approach ……………………………………154 4.3.4 Mask string generation ……………………………………155 4.3.5 Fast valid chromosome generation for population initialization 155 4.3.6 The weight of a 2-terminal for all pairs .…………………..159 4.3.7 Computing the 2-terminal access weight for all pairs ……..160 4.3.8 Computing the access weight of a program and chromosome 160 4.3.9 Computing the fitness value of chromosome using objective function ……………………………………………………162 4.3.10 Genetic reproduction and selection …………………..….163 4.3.11 Genetic crossover operator ………………………….…..163 4.3.12 Genetic mutation operator ………………………………..165 4.3.13 Replacement strategy and termination rules ….…………..166 4.3.14 The GADTA algorithm ………………………………….167 4.3.15 An illustrate example …………………………………….172 4.3.16 Results and discussion ………………………….……….175 4.4 DISCUSSION ……………………………………………………..178 CHAPTER 5 DNA COMPUTATION ………………………….179 5.1 DNA BACKGROUND AND ITS OPERATIONS ……………179 5.1.1 DNA structure …………………………………….180 5.1.2 DNA operations ……………………………………………181 5.1.2.1 Synthesis ……………………………………………181 5.1.2.2 Melting and annealing ………………………………181 5.1.2.3 Ligation ……………………………………………182 5.1.2.4 Polymerase extension …………………………….182 5.1.2.5 Separate by subsequence …………………………182 5.1.2.6 Cut …………………………………………………183 5.1.2.7 Separate by length ………………………………….183 5.1.2.8 Destroy ………………………………………………183 5.1.2.9 Amplify ……………………………………………..184 5.2 DNA ALGORITHM FOR MINIMAL SPANNING TREE OF A DISTRIBUTED SYSTEM ………………………………………184 5.2.1 Arithmetic operations with DNA ………………………….184 5.2.2 Development of DNAMST ……………………………….186 5.2.2.1 Encoding scheme …………………………………….186 5.2.2.2 The DNAMST algorithm ……………………………188 5.3 DISCUSSION ……………………………………………………..193 5.4 CONCLUSION ……………………………………………………196 CHAPTER 6 FURTHER RESEARCHES AND CONCLUSIONS ….197 6.1 FURTHER RESEARCHES ………………………………………197 6.2 CONCLUSIONS ………………………………………………….199 BIBLIOGRAPHY ……………………………………..………..202 VITA …………………………………………………………….209 PUBLICATION LISTS …………………………………………211