淡江大學覺生紀念圖書館 (TKU Library)
進階搜尋


  查詢圖書館館藏目錄
系統識別號 U0002-0706200520080700
中文論文名稱 非齊次分散式系統元件配置決策模型
英文論文名稱 Task Allocation Model for Heterogeneous Distributed Computing System
校院名稱 淡江大學
系所名稱(中) 資訊管理學系碩士班
系所名稱(英) Department of Information Management
學年度 93
學期 2
出版年 94
研究生中文姓名 彭寶嶙
研究生英文姓名 Pao-Lin Peng
學號 692521411
學位類別 碩士
語文別 中文
口試日期 2005-05-21
論文頁數 59頁
口試委員 指導教授-徐煥智
委員-張昭憲
委員-莊裕澤
委員-呂芳懌
中文關鍵字 分散式系統  系統可靠度  任務配置 
英文關鍵字 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.
論文使用權限
  • 同意紙本無償授權給館內讀者為學術之目的重製使用,於2005-06-09公開。
  • 不同意授權瀏覽/列印電子全文服務。


  • 若您有任何疑問,請與我們聯絡!
    圖書館: 請來電 (02)2621-5656 轉 2281 或 來信