(3.238.250.105) 您好!臺灣時間:2021/04/20 06:41
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:張炳煌
研究生(外文):Chang, Bing-Huang
論文名稱:回溯相依可追蹤性及免骨牌效應檢查點通訊協定之模擬研究
論文名稱(外文):A Simulation Study of RDT and DEF Checkpointing Protocols
指導教授:蔡智強蔡智強引用關係
指導教授(外文):Jichiang Tsai
學位類別:碩士
校院名稱:國立中興大學
系所名稱:電機工程學系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2004
畢業學年度:92
語文別:中文
論文頁數:120
中文關鍵詞:回溯復原檢查點回溯相依可追蹤性免骨牌效應分散式計算軟體模擬
外文關鍵詞:rollback recoverycheckpointRollback-Dependency TrackabilityDomino-Effect Freedomdistributed computationSoftware Simulation
相關次數:
  • 被引用被引用:2
  • 點閱點閱:127
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:10
  • 收藏至我的研究室書目清單書目收藏:0
在網路環境中,分散式計算(distributed computation)系統訊息傳遞的正確性顯得相當重要且必須。但傳送過程中常由於外界不明原因而引起錯誤的訊息傳送,此時有效的回溯復原(rollback recovery)將是使得系統能否恢復正常運作的重要因素。
利用檢查點(checkpoint)的設定來進行系統回溯復原是一種有效解決傳送錯誤的方法。藉由檢查點所提供的資訊將工作程序(process)恢復到設定的那個階段,系統將可由此階段繼續正常的執行。
檢查點的設定有不同協定(protocol)被提出,著名的有回溯相依可追蹤性(Rollback-Dependency Trackability, RDT)協定,以及免骨牌效應(Domino-Effect Freedom, DEF)協定。許多文獻中已有眾多在這些主題上進行理論的效益分析。
本篇論文藉由PARSEC軟體模擬方法,針對上述RDT及DEF兩類型的許多協定,在多種不同的網路環境下,做統整性的效能模擬比較,其研究成果可明確指出那些是有效率的協定,並可有效的提供給網路檢查點設計與評估者的指導方針。
In a network environment, the data transfer accurately of Distributed Computation is critical. However, error often occurs during data transfer due to unexplained outside interference. It is then that effective Rollback Recovery becomes an important element in restoring system functions.
Setting Checkpoint locations to facilitate trace recovery is an effective method of solving data transfer errors. With the information stored on checkpoints, a system is can backtrack to the process in question, and continue normally from there.
Many protocols for checkpoint designs have been published; popular ones include algorithms of types Rollback-Dependency Trackability (RDT), and Domino-Effect Freedom (DEF). Numerous papers have analyzed the issue of effectiveness of protocols of these two types.
This Thesis paper employs PARSEC Software Simulation, targets the above two types of protocol and simulated under numerous networked environments to do systematic analysis and performance comparisons. The research results here can accurately highlight the most efficient protocols, and conveniently provide designers and system analysts with directions for various network designs.
目 錄
中文摘要 i
英文摘要 ii
誌 謝 iii
目錄 iv
第一章 緒論 1
第一節研究背景 1
第二節研究動機與目的 1
第三節研究範圍 2
第四節章節結構 4
第二章 相關文獻探討 6
第一節專有名詞定義與描述 6
第二節RDT檢查點協定 DEF檢查點協定 10
第三節Basic checkpoint 與 Forced checkpoint 21
第三章 模擬工具測試與實務 24
第一節模擬環境軟硬體需求介紹 24
第二節PARSEC模擬語言用法簡介 24
第三節網路環境模型模擬介紹 27
第四章 模擬及數值結果分析 30
第一節NNVD-PMM NO-PMM-Path No-EPSCM-Path NO-EPCM-Path模擬比較分析 31
第二節NO-PMM-Cycle NO-PMM NRAS FDI模擬比較分析 39
第三節BCS NMMP HMNR1 HMNR2 模擬比較分析 47
第四節Lazy-BCS Lazy-HMNR1 Lazy-HMNR2 BQF 模擬比較分析 55
第五節SPZC SCZC PRL NNVD-PMM 模擬比較分析 63
第六節PRL HMNR1 Lazy-HMNR1 NRAS模擬比較分析 71
第五章 數值結果驗證與評估 79
第一節P2P之 Basic checkpoint數值變化驗證及評估 80
第二節P2P之Message 傳送率變化驗證及評估 86
第六章 結論與建議 92
參考文獻 95
附錄(相關程式) 99
參考文獻
[1] Jichiang Tsai, Sy-Yen Kuo, and Yi-Min Wang, “Theoretical Analysis for Communicati- on-Induced Checkpointing Protocols with Rollback-Dependency Trackability, ” IEEE Transactions on Parallel and Distributed Systems, 9(10):963-971, October 1998.
[2] Jichiang Tsai, “Simulation Comparisons of Communication-Induced Checkpointing Protocols with Rollback-Dependency Trackability,” submitted to Journal of Information Science and Engineering, Dec , 2003
[3] Jichiang Tsai: On Properties of RDT Communication-Induced Checkpointing Protocols. IEEE Trans. Parallel Distrib. Syst. 14(8): 755-764 (2003)
[4] Chi-Yi Lin, Jichiang Tsai, Sy-Yen Kuo, Yennun Huang: Communication-Induced Checkpointing Protocols with K-Bounded Domino-Effect Freedom. ICDCS Workshop on Distributed Real-Time Systems 2000: B7-B13
[5] Mostefaoui, J. M. Helary, R. H. B. Netzer, and M. Raynal, “Communication based prevention of useless checkpoints in distributed computations,” Distributed Computing, pp. 29-43, Vol. 13, 2000.
[6] R.Bagrodia et al., “Parsec: A Parallel Simulation Environment for Complex Systems,” Computer, pp77-85 ,October 1998.
[7] J. Tsai, Y. M. Wang, and S. Y. Kuo, “Evaluations of domino free communication-induced checkpointing protocols , ” Information Processing Letters, 69:31—37, Jan. 1999.
[8] R.Bagrodia, “Parallel Language for Discrete-Event Simulation Models,” IEEE Computational Science and Engineering , pp.27-38 Apr.-June 1998.
[9] Richard A. Meyer and Rajive Bagrodia, “PARSEC User Manual For PARSEC Release 1.1,” Revised in September 1999, http://pcl.cs.ucla.edu/projects/parsec
[10] Y. M. Wang, A. Lowry, and W. K. Fuchs, “Consistent global checkpoints based on direct dependency tracking,” Information Processing Letters, Vol. 50, 1994, pp. 223-230.
[11] K. M. Chandy and L. Lamport, “Distributed snapshots: Determining global states of distributed systems,” ACM Transactions on Computing Systems, Vol. 3, 1985, pp. 63-75.
[12] B. Randell, “System structure for software fault-tolerant,” IEEE Transactions on Software Engineering, Vol.1, 1975, pp. 220-232.
[13] E. N. Elnozahy, L. Alvisi, Y. M. Wang, and D. B. Johnson, “A survey of rollback-recovery protocols in message-passing systems,” ACM Computing Surveys, Vol. 34, 2002, pp. 375-408.
[14] R. Koo and S. Toueg, “Checkpointing and rollback-recovery for distributed systems,” IEEE Transactions on Software Engineering, Vol. 13, 1987, pp. 23-31.
[15] B. Janssens and W. K. Fuchs, “Experimental evaluation of multiprocessor cache-based error recovery,” in Proceedings of International Conference on Parallel Processing, 1991, pp. 505-508.
[16] Y. M. Wang, “Consistent global checkpoints that contain a given set of local checkpoin- ts,” IEEE Transactions on Computers, Vol. 46, 1997, pp. 456-468.
[17] R. H. B. Netzer and J. Xu, “Necessary and sufficient conditions for consistent global snapshots,” IEEE Transactions on Parallel and Distributed Systems, Vol. 6, 1995, pp. 165-169.
[18] R. Baldoni, J. M. Helary, A. Mostefaoui, and M. Raynal, “A communication-induced checkpointing protocol that ensures rollback-dependency trackability,” in Proceedings of IEEE Fault-Tolerant Computing Symposium, 1997, pp. 68-77.
[19] D. L. Russell, “State restoration in systems of communicating processes,” IEEE Transactions on Software Engineering, Vol. 6, 1980, pp. 183-194.
[20] R. Baldoni, J. M. Helary, and M. Raynal, “Rollback-dependency trackability: A minimal characterization and its protocol,” Information and Computation, Vol. 165, 2001, pp. 144-173.
[21] I. C. Garcia, G. M. D. Vieira, and L. E. Buzato, “RDT-partner: An efficient checkpointing protocol that enforces rollback-dependency trackability,” in Proceedings of IX Brazilian Symposium on Fault-Tolerant Computing, 2001.
[22] I. C. Garcia and L. E. Buzato, “A linear approach to enforce the minimal characterization of the rollback-dependency trackability property,” Technical Report, TR-IC-01-17, University of Campinas, Brazil, 2001.
[23] D. Manivannan and M. Singhal, “Quasi-synchronous checkpointing: Models, characterization, and classification,” IEEE Transactions on Parallel and Distributed Systems, Vol. 10, 1999, pp. 703-713.
[24] R. Baldoni, J. M. Helary, and M. Raynal, “Rollback-dependency trackability: Visible characterizations,” in Proceedings of 18th ACM Symposium on Principles of Distributed Computing, 1999, pp. 33-42.
[25] R. Baldoni, J. M. Helary, and M. Raynal, “Impossibility of scalar clock-based communication-induced check-pointing protocols ensuring the RDT property,” Information Processing Letters, Vol. 80, 2001, pp. 105-111.
[26] I. C. Garcia and L. E. Buzato, “On the minimal characterization of the rollback-dependency trackability property,” in Proceedings of 21st IEEE International Conference on Distributed Computing Systems, 2001, pp. 342-349.
[27] J. Tsai, S. Y. Kuo, and Y. M. Wang, “Some characteristics of communication-induced checkpointing protocols with rollback-dependency trackability,” submitted to Journal of Parallel and Distributed Computing, 2003.
[28] L. Lamport, “Time, clocks and the ordering of events in a distributed system,” Communications of the ACM, Vol. 21, 1978, pp. 558-565.
[29] D. Briatico, A. Ciufoletti, and L. Simoncini, “A distributed domino-effect free recovery algorithm,” Proc. 4th IEEE Symp. on Reliability in Distributed Software and Database Syst., pp. 207-215, Oct. 1984.
[30] D. Manivannan and M. Singhal, “A low overhead recovery technique using quasi- synchronous checkpointing,”Proc. 16th IEEE Int''l Conf. on Distributed Computing Syst., pp. 100-107, May 1996.
[31] G. M. D. Vieira, I. C. Garcia, and L. E. Buzato, “Systematic analysis of index-based checkpointing algorithms using simulation,” Proc. Of IX Brazilian Symp. on Fault-Tolerant Comput., 2001.
[32] F. Quaglia, R. Baldoni, and B. Ciciani, “On the no-Z-cycle property in distributed executions,” Journal of Computer and Systems Sciences, vol. 61, no. 3, pp. 400-427, Dec. 2000.
[33] J. M. Helary, A. Mostefaoui, and M. Raynal, “Virtual precedence in asynchronous systems: concept and applications,” 11th Int''l Workshop on Distributed Algorithms, pp. 170-184, Sept. 1997.
[34] C. J. Fidge, “Logical time in distributed computing systems,” IEEE Computer, vol. 24, no. 8, pp. 11-76,1991.
[35] L. Alvisi, E. Elnozahy, S. Rao, S. A. Husain, and A. De Mel, “Ananalysis of communication-induced checkpointing, ” IEEE Fault-Tolerant Comput. Symp., pp. 242-249, 1999.
[36] Jichiang Tsai, “Performance Comparisons of Index-Based DEF Checkpointing Protocols, ” submitted to IEEE Transactions on Parallel and Distributed Systems, October 2003.
[37]Jichiang Tsai, “Systematic comparisons of RDT communication-induced checkpointing protocols, ” Pacific Rim International Symposium on Dependable Computing, Mar. 2004.
[38]叢震,”分散式系統中基於免骨牌效應檢查點通訊協定模擬比較分析 ”,國立中興大學電機工程研究所碩士論文,民國92年7月
[39]林炳源,”模擬比較具回溯相依可追蹤性之檢查點通訊協定 ”,國立中興大學電 機工程研究所碩士論文,民國92年7月
[40]方世榮,”統計學導論 ”,華泰書局,民國80年7月
[41]施威銘,”最新c語言學習實務 ”,旗標出版社,民國88年3月
[42]祥宇開發創新科技小組,”物件導向的c++ ”,知行文化,民國89年7月
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔