基于内容的“发布/订阅”若干关键技术研究

论文摘要

分布对象通信中间件以解决异构网络环境下分布应用系统之间的互操作为目标,可以屏蔽网络通信的实现细节,提高系统的可移植性,因而在诸多领域得到了广泛应用,成为分布计算的主流技术之一。随着Internet的飞速发展,软件应用形态逐步从相对封闭、面向熟识用户群体和相对静态的紧耦合形式向开放、公共可访问和动态协作的松耦合模式转变。采用RPC同步机制的传统分布对象中间件其所提供的单一同步通信机制无法适应Internet的动态特性,为应对这一挑战,能够为构建上层分布应用提供异步的、松耦合的通信机制变得非常必要。“发布/订阅”(Publish/Subscribe)是一种基于事件的通信范型,与异步RPC、分布共享内存、消息队列等异步通信范型相比,能够使通信的参与者在空间、时间和控制流上完全解耦,因此能够较好地满足许多大型分布式系统松散耦合通信的需求,近年来受到广泛关注和深入研究。根据对事件通知选择方式的不同,“发布/订阅”系统可以分为基于通道、基于主题和基于内容等。基于通道和基于主题的“发布/订阅”相对简单,基于内容的“发布/订阅”具有更强大、更灵活、适应性更广的特性,后者是构建未来新型大规模分布式应用系统的基础设施之一。然而,相比之下,基于内容的“发布/订阅”要复杂的多,它要成为一个真正实用的、支持大规模分布式应用的支撑平台,许多关键技术问题仍然亟待解决。本文围绕着支持基于内容“发布/订阅”的关键技术性问题,在如下几个方面展开了研究工作:1、路由算法研究方面。应用订阅间的覆盖关系可以减少需要转发的订阅数,从而可以减小中间代理的路由表大小,继而可以缩短事件的匹配时间。我们将订阅覆盖路由区分为最优(optimal)和次优(suboptimal)的策略,提出了严格的基于订阅覆盖的路由(SSCBR)和放松的基于订阅覆盖的路由(RSCBR)策略,前者考虑最优订阅覆盖路由策略,后者使用次优订阅覆盖路由策略。针对SSCBR的最优订阅覆盖路由策略,提出了使用SSCBR时路由表配置正确的充要条件,通过该充要条件证明了SSCBR和RSCBR路由算法的正确性。2、事件消息的可靠传递研究方面。我们提出了一个两层的可靠性模型来保证事件消息传递的可靠:可靠的P/S协议层和可靠流传输层。可靠的P/S协议层理解P/S系统的消息格式,而可靠流传输层将P/S消息看作数据流,两层都提供事件的可靠传递支持,用户可以选择只使用其中的一层,也可以同时使用两层。在可靠的P/S协议层,应用混合的基于Gossip算法的push和pull方法,提出了支持订阅覆盖的事件丢失检测与恢复算法。算法利用了pull方法开销小的优点,又克服了pull方法在某些特殊场景下无法检测出事件丢失的缺点,具有较好的性能。在可靠流传输层,通过网络链路速率探测、断点续传等机制来适应不同的链路质量,保证消息流的点到点可靠传递。3、移动计算环境的扩展支持技术研究方面。对订阅者暂时断连问题,提出了一种保持“at most once”语义的快速重连算法。对使用持久订阅的订阅者发生漫游后需要进行事件迁移的问题,分析了已有研究提出的同步算法的有效性以及迁移算法对路由算法的依赖,并提出了两种改进方法:预转移与预恢复。预转移方法通过提前将事件转发到新代理,预恢复方法利用事件迁移算法进行同步过程的空隙,从新代理和其邻居代理上预恢复需要迁移的事件,两者都减少了需要迁移的事件数,从而缩短了事件迁移的过程。4、系统实现方面。基于本文的研究成果,实现了一个通知服务原型系统Densa。Densa具有较好的可配置与可扩展能力,应用系统可根据需要对路由策略、传输的可靠性QoS等进行配置,以更好地满足它们的需求。Densa通过多协议管理框架可以支持多种协议,使其可以较好地应用于复杂的应用环境。综上所述,本文针对支持基于内容“发布/订阅”亟待解决的几个关键问题提出了初步的解决方法,但求对推进基于内容的“发布/订阅”的理论研究和实用化进程能带来一定的理论启迪和应用参考。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 研究背景
• 1.1.1 异步通信机制的应用需求
• 1.1.2 可选的异步通信范型
• 1.1.3 课题来源
• 1.2 “发布/订阅”通信范型
• 1.2.1 概念模型
• 1.2.2 解耦特性
• 1.2.3 分类
• 1.3 研究工作定位
• 1.4 本文贡献
• 1.5 论文结构
• 第二章 相关研究工作
• 2.1 基于内容的P/S
• 2.1.1 可表达能力
• 2.1.2 拓扑结构
• 2.1.3 事件匹配
• 2.2 事件路由算法
• 2.2.1 研究现状
• 2.2.2 存在的不足
• 2.3 事件的可靠传输
• 2.3.1 研究现状
• 2.3.2 存在的不足
• 2.4 移动计算环境的支持
• 2.4.1 断线
• 2.4.2 客户端漫游
• 第三章 支持订阅覆盖的路由算法
• 3.1 概述
• 3.1.1 简单值类型约束的覆盖判定规则
• 3.1.2 字符串类型约束的覆盖判定规则
• 3.2 订阅覆盖路由策略
• 3.2.1.55 CBR 路由策略
• 3.2.2.R SCBR 路由策略
• 3.3 路由表正确的充要条件
• 3.4 路由算法
• 3.4.1.55 CBR 算法
• 3.4.2.R SCBR 算法
• 3.5 实验与评估
• 3.5.1 路由表大小实验
• 3.5.2 网络通信开销实验
• 3.5.3 时间性能实验
• 3.6 小结
• 第四章 事件的可靠传递研究
• 4.1 可靠性模型
• 4.2.G ossip 算法
• 4.2.1 基本概念
• 4.2.2 优点和动机
• 4.3 可靠PS 协议层（RPSL）
• 4.3.1 支持订阅覆盖的事件丢失检测算法
• 4.3.2 事件恢复算法
• 4.3.3 算法对系统性能的影响分析
• 4.4 可靠流传输层（RSTL）
• 4.4.1 链路速率自适应算法
• 4.4.2 断点续传
• 4.5 实验与评估
• 4.5.1.R PSL 实验
• 4.5.2.R STL 实验
• 4.6 小结
• 第五章 移动计算的扩展支持技术
• 5.1 断线重连
• 5.1.1 断线分析
• 5.1.2 暂时断线快速重连算法（FRTD）
• 5.1.3.F RTD 的断线分析
• 5.2 订阅者漫游
• 5.2.1 订阅的持久性
• 5.2.2 事件迁移算法
• 5.2.3 算法改进
• 5.3 实验与评估
• 5.3.1.F RTD 实验
• 5.3.2 事件迁移实验
• 5.4 小结
• 第六章 通知服务原型系统
• 6.1 分布计算中间件StarBus+
• 6.2 原型系统Densa 的设计
• 6.2.1 设计原则
• 6.2.2 系统结构
• 6.2.3 可扩展与可配置能力
• 6.3.D ensa 的实现
• 6.3.1 用户接口实现
• 6.3.2 可靠传输服务
• 6.3.3.G IOP 协议扩展
• 6.4 应用举例
• 6.4.1 总体结构
• 6.4.2 数据复制
• 6.5 小结
• 第七章 结束语
• 7.1 本文总结
• 7.2 未来工作
• 致谢
• 参考文献
• 作者在学期间取得的学术成果
• 攻读博士学位期间参加的科研工作
• 附录 发布/订阅研究的技术资源