系統識別號 | U0002-0706200520080700 |
---|---|
DOI | 10.6846/TKU.2005.00815 |
論文名稱(中文) | 非齊次分散式系統元件配置決策模型 |
論文名稱(英文) | Task Allocation Model for Heterogeneous Distributed Computing System |
第三語言論文名稱 | |
校院名稱 | 淡江大學 |
系所名稱(中文) | 資訊管理學系碩士班 |
系所名稱(英文) | Department of Information Management |
外國學位學校名稱 | |
外國學位學院名稱 | |
外國學位研究所名稱 | |
學年度 | 93 |
學期 | 2 |
出版年 | 94 |
研究生(中文) | 彭寶嶙 |
研究生(英文) | Pao-Lin Peng |
學號 | 692521411 |
學位類別 | 碩士 |
語言別 | 繁體中文 |
第二語言別 | |
口試日期 | 2005-05-21 |
論文頁數 | 59頁 |
口試委員 |
指導教授
-
徐煥智(shyur@mail.im.tku.edu.tw)
委員 - 張昭憲 委員 - 莊裕澤 委員 - 呂芳懌 |
關鍵字(中) |
分散式系統 系統可靠度 任務配置 |
關鍵字(英) |
Distributed Computing System System Reliability Task Allocation |
第三語言關鍵字 | |
學科別分類 | |
中文摘要 |
以標準元件為基礎所構建的分散式資訊應用系統是軟體系統發展的一個重要趨勢。利用租用或自行開發的系統元件並透過網路資料傳輸,採用軟體標準與通訊協定來達到互相連結結的目的,將可加速系統的開發與更新並且提升資訊分享與作業處理能力。然而建構如此的分散式環境下企業應用系統的可靠度將直接影響系統的成敗。分散式的作業環境提供了系統容錯與平行處理的能力,因此提升了部分的系統可靠度。但是因為在分散式作業環境下,元件分散在各處理節點且需要有資料的傳輸,因此系統可靠度的評估成為一個比較複雜的問題。 由於在分散式系統建置規劃中的元件配置決策中系統可靠度,執行效率與建置成本是重要的決策關鍵因素(Kartik and Murthy ,1997; Hsieh and Hsieh, 2003)。在現行相關的研究中,我們發現系統可靠度的評估,都忽略了軟體執行的特性及假設所有的執行單元為Homogeneous。在分散式系統中每次的系統執行並非所有的元件或系統節點都會參與運算,且使用的硬體設備也不會有相同的Failure Rate。因此本研究中將以符合軟體執行特性與系統執行環境的系統可靠度評估模式為基礎,來建構一個分散式系統元件配置問題的決策模式,本模式亦將3-Version Programming 的Fault Tolerance 技術納入決策考,並將採用Constraint Programming 技術來協助求解。 |
英文摘要 |
There has been a proliferation of distributed computing systems in the past few years. A distributed computing system presents a platform consisting of multiple computing nodes connected in some fashion to which various components (or modules) of a task could be assigned. Such a system can speed up the development process and improve information sharing and operational capabilities. Yet, such a system must be reliable to be successful. A distributed computing system may execute a task with higher reliability if the various components of the given task are assigned to appropriate nodes considering the reliability of the nodes and links. However, the estimation of system reliability is a complex problem. The module allocation problem in distributed computing systems deals with finding a suitable assignment of modules to processors so that the sum of execution and communication costs is minimized and the system reliability is acceptable. However, for such a problem the software operational characteristics are not considered for the procedure of system reliability estimation in current studies and the system is assumed operation in a homogeneous environment. These characteristics will affect the accuracy of the system reliability estimation. Therefore, we will need to develop a new decision model for task allocation in distributed computing systems with a consideration of software component reliability and heterogeneous operation environment. In this research, we consider 3-version software fault tolerance technique to improve system reliability and conduct the technique of constraint programming to solve the optimal task allocation problem. |
第三語言摘要 | |
論文目次 |
目錄 第1章 緒論 1 1.1 研究背景與動機 1 1.2 研究目的 2 1.3 論文架構 4 第2章 文獻探討 6 2.1 分散式系統可靠度計算相關文獻 6 2.2 分散式系統元件配置相關文獻 7 2.3 分散式系統元件配置求解相關文獻 10 第3章 模型建構 15 3.1 環境假設 15 3.2 模型的建構 17 3.2.1. 環境變數 17 3.2.2. 決策變數 19 3.2.3. 環境限制 20 3.3 模型求解計算方式 20 3.3.1. 可靠度計算 20 3.3.2. 成本計算 23 3.4 最佳可靠度模型 25 3.5 最佳成本模型 27 第4章 模型案例與敏感性分析 29 4.1 模式案例說明 29 4.2 最佳可靠度模型 29 4.3 最佳成本模型 32 4.4 軟體模組錯誤偵測率估計誤差對系統可靠度的影響 34 第5章 結論與未來研究方向 36 5.1 結論 36 5.2 未來研究方向 37 參考文獻 39 附錄一 案例說明使用的數據 42 附錄二 本模式使用ILOG撰寫的C++程式碼-Ring網路架構 43 附錄三 本模式使用ILOG撰寫的C++程式碼-Star網路架構 52 圖目錄 圖1 1本論文研究架構 5 圖3 1 網路架構(左:Star,右:Ring) 16 圖4 1 Star架構各軟體模組改變錯誤偵測率對系統可靠度的影響 35 圖4 2 Ring架構各軟體模組改變錯誤偵測率對系統可靠度的影響 35 表目錄 表4 1 案例一(C≦1,000,000)Star網路架構 31 表4 2 案例一(C≦1,000,000)Ring網路架構 31 表4 3 案例二(C≦1,500,000)Star網路架構 32 表4 4 案例二(C≦1,500,000)Ring網路架構 32 表4 5 Star網路架構 33 表4 6 Ring網路架構 33 附表目錄 附表1 硬體運算單元相關設定與限制 42 附表2 溝通連結相關設定與限制 42 附表3 軟體模組相關設定與限制 42 附表4 模組傳輸資料量(MB) 42 |
參考文獻 |
Ajith, T.P. and Murthy, C.S.R., "An Improved Algorithm for Module Allocation in Distributed Computing Systems," Journal of Parallel and Distributed Computing, 1997, Vol. 42, pp.82-90. Bannister, J.A. and Trivedi, K.S., "Task Allocation in Fault-Tolerant Distributed Systems," Acta Informatica, 1983, Vol. 20, pp.261-281. Chang, M.S., Chen, D.J., Lin, M.S. and Ku, K.L., "The Distributed Program Reliability Analysis on Star Topologies," Computers & Operations Research, 2000, Vol. 27, pp.129-142. Hsieh, C.C. and Hsieh, Y.C., "Reliability and cost optimization in distributed computing systems", Computers & Operations Research, 2003,Vol. 30, pp 1103-1119. Kartik, S. and Murthy, C.S.R., "Task allocation algorithms for maximizing reliability of distributed computing systems," IEEE Transactions on Computers, 1997, Vol. 46, pp.719-724. Lin, M.S., Chang, M.S., Chen, D.J. and Ku, K.L., "The Distributed Program Reliability Analysis on Ring-Type Topologies," Computers & Operations Research, 2001, Vol. 28, pp.625-635. Pape, C.L., "Implementation of resource constraints in ILOG SCHEDULE a library for the development of constraint-based scheduling systems," Intelligent Systems Engineering, 1994, Vol. 3, pp.55-66. Raghavendra, C.S. and Hariri, S., "Reliability optimization in the design of distributed system," IEEE Trans. Software Engineering, 1985, Vol. 11, pp.1184-1193. Shatz, S.M and Wang, J.P., "Models & algorithms for reliability-oriented task-allocation in redundant distributed-computer systems", IEEE Transactions on Reliability, 1989, Vol. 38, pp. 16-27 Shatz, S.M., Wang ,J.P., and Goto, M., "Task Allocation for Maximizing Reliability of Distributed Computer Systems," IEEE Trans. Computers, 1992, Vol. 41, pp.1,156-1,168. Shin, K.G., Lin, T.H. and Lee, Y.H., "Optimal check pointing of real-time tasks," IEEE Trans. Computer, 1987, Vol. 36, pp.1328-1341. Varvarigou, T.A. and Trotter, J., "Module replication for fault-tolerant real-time distributed systems," IEEE Transactions on Reliability, 1998, Vol. 47, pp.8-18. Vidyarthi, D.P., Tripathi, A.K., "Maximizing Reliability of Distributed Computing System with Task Allocation Using Simple Genetic Algorithm," Journal of Systems Architecture, 2001, Vol. 47, pp.549-554. Wang, J.P. and Shatz, S.M., "Task allocation for optimized system reliability," Symposium on Reliable Distributed Systems, 1988, pp.82 - 90. Weil, G., Heus, K., Francois, P. and Poujade, M., "Constraint programming for nurse scheduling," IEEE Engineering in Medicine and Biology, 1995, Vol.14, pp.417-422. 林詩芹, 以限制規劃構建全年無休服務人員排班模型-以客服人員排班為例, 國立交通大學運輸科技與管理學系碩士論文,2003. 陳彥良, 分散式系統中考量可靠度與執行時間之最佳任務配置, 國立成功大學工業管理研究所碩士論文, 2001. |
論文全文使用權限 |
如有問題,歡迎洽詢!
圖書館數位資訊組 (02)2621-5656 轉 2487 或 來信