题目：面向广域网络的内容发布订阅系统研究

近年来，在广域网络中出现了股票买卖、个性化新闻订阅、分布式拍卖、电子政务信息发布和交互、即时通信等信息驱动型应用。这些应用的特征是信息发布者将信息发布到网络，信息并没有标识特定的接收者而是通过网络所提供的通知服务传递到信息订阅者，通知服务实现了信息发布者和订阅者之间的解耦。传统请求/响应的紧耦合通信模式并不能满足这种信息驱动型应用的松耦合通信需求，而发布订阅技术则反映了其本质特征，成为实现信息驱动型应用的理想选择。主题发布订阅系统已经在局域网络中得到了广泛应用。然而，大多数广域网应用更倾向于基于内容选择信息。但是，目前的发布订阅系统技术在可伸缩性、分布控制、自组织以及性能效率等方面并不能满足大规模、异构、动态广域网环境的要求。本文基于事件空间划分方法针对面向广域网络的内容发布订阅系统的形式模型、关键技术、系统实现方面的问题开展研究，主要的研究结果如下：1． 本文将多维空间划分技术引入内容发布订阅系统中，利用多维空间表示全体事件，利用空间中的点和区域表示单个事件和订阅条件，利用点和区域的包含关系表示事件匹配关系。提出了一种新的内容发布订阅系统设计模型ESPDM。该模型通过区域与代理之间的松耦合映射关系代替了Siena，Rebeca等传统系统模型中内容属性与代理绑定的紧耦合关系，支持通过动态逻辑区域关系的变化调整代理网络的相关属性，例如负载、路由相邻关系等，从而简化了系统关键技术设计。分析了基于ESPDM的系统路由过程，其主要特点是取消了泛洪和广播操作、避免了路由过程中事件匹配操作，减少了系统运行时开销。分析了面向广域网的内容发布订阅系统的时序特征，提出了与系统设计相关的前提假设。上述工作为设计基于事件空间划分的内容发布订阅系统关键算法研究提供了理论基础。2． 基于ESPDM 模型，本文首先提出了一种基于K-D树的多维事件空间划分算法。该算法解决了在数据非均衡分布的场景中事件空间区域的静态负载均衡问题，并保留了系统基于区间的订阅表达能力。其次，利用区域相邻关系与代理链接关系的一一映射，提出了一种基于区域间最短距离的系统贪婪路由算法，该算法实现的O(n1/d)(d是事件空间的维数)的路由效率优于Graphon、Siena、Hermes和Scribe系统O(n)的路由效率。第三，利用K-D树叶子节点的合并和分裂关系提出了系统的分布式动态自组织、容错算法，避免了Siena，Hermes等系统中相应算法采用的泛洪和P2P辅助策略，代价是在10K规模的网络中增加4kbps协议消息流量。由上述关键算法支撑的ESPN(Event Space Partitioning based Network)系统解决方案与典型的Siena,Hermes系统解决方案相比较，其优点是：分布控制(整个系统没有一个集中控制点)、自组织(代理动态的加入和退出)、静态负载均衡、容错、支持基于区间的订阅表达能力。3． 为了进一步优化内容发布订阅系统在广域网络中的路由效率，提出了路由算法Spanhop。该算法的基本思想是：利用K-D树索引结构将代理网络分为逻辑集群，并利用逻辑集群之间的分层结构实现分级路由。Spanhop将路由效率由O(n1/d)进一步提高到O(lnN)。针对层叠网络路由普遍存在的缺少网络层拓扑感知能力的问题，提出了基于网络层拓扑感知的路由优化算法。该算法利用GNP（Global Network Position）坐标空间与事件空间的映射实现了系统网络层拓扑感知能力，将Spanhop下一跳路由在网络层的实际跳数由平均n/2减少到1，其代价是在220规模的网络中每个代理增加10个GNP坐标的存储开销。针对内容发布订阅系统在广域网络中的动态负载失衡问题，利用区域分裂和代理复制技术提出了匹配和路由负载迁移算法，并在此基础上提出了转移加入和动态自适应两种动态负载均衡算法，分别将过载代理的负载比例由50%均衡到36%和29%，欠载代理的负载比例由3%提高到10%和20%。上述算法优化了内容发布订阅系统的路由和动态负载均衡性能。4． 基于上述关键技术的研究，采用分层和插件相结合的动态体系结构设计方法，设计和实现了可配置和可扩展的发布订阅中间件Xinfo。Xinfo作为一种新的发布订阅通信支撑系统在黑龙江省电子政务中得到了实际应用。