移动计算环境下检查点技术研究与Petri网建模

论文摘要

随着无线网络与可移动设备的发展,移动计算正逐步成为分布式计算的主流,移动计算使得人们在保持网络连接的同时能够自由移动,这促进了许多新的分布式应用的出现。但是移动计算的特征也造成其缺乏可靠性,因此提供移动环境下的容错方法对移动计算的发展起着重要的作用。检查点技术是适合移动计算环境的一种重要容错手段。本文讨论了移动计算环境下检查点设置技术的分类,比较了各类检查点技术的优缺点。在分析了移动计算环境对检查点设置的影响后,根据分段确定性假设是否成立设计了两个检查点协议:HMB协议与MNLC协议。HMB是一种基于日志的容错协议。不同于已有的采用固定时间间隔而设置检查点的算法,HMB算法的检查点间隔完全由移动主机握手率与消息到达率决定。HMB算法使得系统在无错执行时的开销与及时恢复间取得更好的平衡。MNLC是一种基于协同检查点的容错协议,MNLC的特点在于区分出真正的检查点依赖进程。通过记录通信向量与消息发送感染向量,MNLC协议实现最少数量进程参与检查点设置及卷回恢复,同时由于MNLC协议的许多操作都是在移动支持站上进行的,因此MNLC具有较小的开销。为了对所设计的协议进行综合的性能评价,本文利用广义随机Petri网和有色Petri网分别为HMB协议和MNLC协议进行了建模,得出了各自的性能指标。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 引言
• 1.2 分布式系统中检查点技术
• 1.2.1 基于检查点的卷回恢复
• 1.2.2 基于日志的卷回恢复
• 1.2.3 各种检查点技术的比较
• 1.3 移动计算环境对检查点设置的影响
• 1.4 检查点协议性能评价与Petri 网建模
• 1.5 本文主要研究内容与结构
• 第2章 基于握手与消息到达率的算法
• 2.1 引言
• 2.2 系统模型
• 2.3 HMB 算法设计动机
• 2.4 HMB 算法描述
• 2.5 本章小节
• 第3章 最少进程参与低代价恢复算法
• 3.1 引言
• 3.2 检查点依赖进程
• 3.3 MNLC 算法在无错执行时的操作
• 3.4 MNLC 算法的检查点设置操作
• 3.5 MNLC 算法的卷回恢复操作
• 3.6 MNLC 算法的正确性证明
• 3.7 本章小结
• 第4章 Petri 网建模检查点协议
• 4.1 引言
• 4.2 GSPN 建模HMB 协议
• 4.2.1 HMB 协议的GSPN 模型
• 4.2.2 HMB 协议的性能
• 4.3 CPN 建模MNLC 协议
• 4.3.1 总体建模
• 4.3.2 通信过程建模
• 4.3.3 检查点设置过程建模
• 4.3.4 MNLC 协议卷回恢复过程建模
• 4.3.5 MNLC 协议性能评价
• 4.4 本章小结
• 结论
• 参考文献
• 致谢