基于着色Petri网的发布/订阅系统的建模与分析

论文摘要

近几年随着科技的发展,Internet技术广泛的被应用,具有松耦合、异步和多点通信的等特点的发布/订阅系统（pub/sub系统）满足了分布式系统在应用范围和应用规模等方面改变的需要,得到了广泛的应用。近年得到很多专家学者的研究,但大多在表达能力、效率和可靠性等方面尚存在着较多的问题。而P2P（peer-to-peer）技术具有分散控制、容错能力高以及自组织等一系列优点,将pub/sub系统与P2P技术结合,会使得系统具有较强的容错能力和消息传输可靠性。在设计构建于P2P网络之上的发布/订阅系统时需要考虑多个因素,这导致了系统的复杂性,在网络协议方面体现出空间分布性、并发性、异步性,不稳定性和多样性等,这使得传统的方法对复杂的发布/订阅系统的形式化描述和分析具有一定的困难。特别是对发布（或订阅）事件的处理流程进行模拟和分析有一定的困难,而且模拟过程是比较费时的。为此我们采用着色Petri网（CPN）对发布/订阅系统的路由协议进行建模和分析,这是因为CPN是一种形式化分析方法,适合描述和分析并发处理之间的同步、通信和资源共享等,通过对token的着色可以对各种复杂的数据进行分类而且可以对模型分层处理,这简化了系统的复杂度并突出重点,正适合模拟和分析复杂的发布/订阅系统。本文就发布/订阅系统中的关键部分—订阅事件和发布事件的处理分别进行了一定的形式化描述和分析。对一个事件的发布（或者订阅）从发送方需要做的处理到接收方收到后所做的处理进行了全面详细的建模、描述和分析。对着色Petri网模型利用CPN Tools进行了状态空间分析,得出了模型的一些动态属性,如模型是有界的,可达的,具有公平性等,继而证明了系统的消息传输是可达的,可行的,而且系统具有较高的可靠性。本文主要贡献有以下两点:第一,从理论角度研究分析了应用CPN这一形式化方法来模拟处理构建于P2P之上的发布/订阅系统的可行性。第二,用CPN方法形式化实现基于编码的路由选择,模拟了一条消息从发送到接收,及在接收方的转发过程。通过路由选择和过滤条件表的匹配,用着色Petri网建模和分析证明了该协议具有较强的容错能力和较高的可靠性,同时在一定条件下可以保证所有订阅者都能收到该事件,且只收到一次。

论文目录

• 摘要
• Abstract
• 第一章 引言
• 1.1 课题的来源、提出背景
• 1.2 国内外研究现状
• 1.3 论文研究的意义
• 1.4 主要内容及创新点
• 1.5 论文组织结构
• 第二章 着色 Petri 网
• 2.1 Petri 网的基本理论
• 2.2 着色Petri 网的基本理论
• 2.2.1 着色Petri 网的基本定义
• 2.2.2 层次着色Petri 网
• 2.2.3 着色Petri 网的动态属性
• 2.3 利用着色Petri 网进行协议分析
• 2.4 着色Petri 网的优点
• 2.5 自动化分析工具CPN TOOLS
• 2.6 本章小结
• 第三章 发布/订阅系统
• 3.1 PUB/SUB 系统概述
• 3.2 P2P 网络上的PUB/SUB 系统
• 3.2.1 P2P 上的pub/sub 系统模型
• 3.2.2 IRBR 的基本思想
• 3.2.3 消息约束
• 3.2.4 处理流程
• 3.3 本章小结
• 第四章 发布/订阅系统的形式化描述
• 4.1 假设或约定
• 4.2 着色Petri 网模型的建模
• 4.2.1 订阅的处理模型
• 4.2.2 发布事件模型
• 4.3 发布事件模型的扩展
• 4.3.1 Top 层模块
• 4.3.2 publisher 子模块
• 4.3.3 network 子模块
• 4.3.4 subscriber 子模块
• 4.4 运行结果
• 4.4.1 订阅模型的结果
• 4.4.2 发布模型的结果
• 4.4.3 扩展发布模型的结果
• 4.5 本章小结
• 第五章 模型的性质验证与分析
• 5.1 订阅模型的分析
• 5.2 发布模型的分析
• 5.3 本章小结
• 结论与展望
• 1 论文总结
• 2 论文研究展望
• 参考文献
• 在学期间的研究成果
• 致谢