一种基于谓词覆盖技术的启发式事件匹配算法

基于内容路由的发布/订购(Pub/Sub)技术具有异步、松散耦合和多对多通信等特点,使得它能更好地应用于大规模分布式交互系统.而高效率的发布事件匹配算法是实现基于内容路由的大规模Pub/Sub系统所要解决的关键问题.针对基于内容的发布/订购模型主要性能的事件匹配问题做了重点研究,提出了谓词关系(二叉树)的概念.并在此基础上,通过将谓词覆盖技术同启发式匹配策略相结合,设计并实现了启发式发布事件匹配算法--PRBT-Match算法.实验结果表明,PRBT-Match算法相对于其他常用匹配算法有更好的匹配性能.     

发布订阅系统在移动Ad Hoc网络中的三种路由算法

介绍了分布式发布/订阅系统的原型，为Ad Hoc网络中的发布/订阅系统设计了三种基于内容的路由算法，分别说明了它们的运行方式，并进行了仿真与比较。结果表明：基于内容的可靠容错路由算法能够100%保证信息的传输，有容错机制，可靠性较强，但出现了传输延迟；基于内容的路由算法的可靠性不强，适合有线网络中分布式发布订阅系统的信息传输，传输延迟小；基于内容的容错路由算法有容错机制，传输延迟小     

A scalable publish/subscribe system for large mobile ad hoc networks

Since nodes that compose mobile ad hoc networks (MANETs) does not have any prior knowledge about other nodes in many cases, the publish/subscribe communication paradigm that has the decoupling and asynchrony properties can be useful to share information between nodes. Existing publish/subscribe services for MANETs can be categorized into document flooding (DF), destination-based routing (DBR), and content-based routing (CBR). Although those approaches may work well when the size of network is small, all of them suffer from the performance decline as the size of the network increases. In this paper, we compare those approaches, and then propose a scalable publish/subscribe communication scheme in large MANETs by combining DF and CBR hierarchically. Our approach is to cluster all nodes in networks and to exploit CBR and DF for the intra- and inter-cluster communication, respectively. By using this approach, we can effectively utilize benefits of both approaches. Then, we present performance evaluation results which validate our idea with respect to system performance and scalability.     

一种基于内容的双向共享组播路由协议

针对组播协议在大规模分布式交互系统应用中面临的可扩展性问题,提出一种基于内容的双向共享组播路由协议CBSMRP(content-based bi-directional shared multicast routing protocol).该协议结合运用了主动路由思想和基于内容的发布-订购模式,在基于CBT(core-based tree)结构的双向共享组播树中,根据数据包的内容实现主动路由和双向过滤,不仅解决了组播地址的维护和分配等问题,而且能够有效地减轻系统的网络负载.仿真实验及实际应用表明,该协议具有较好的扩展性,能够满足大规模分布式交互系统的网络通信要求.     

一种基于速率的发布/订阅系统的准入控制机制

提出了基于内容发布/订阅系统的一种准入控制机制RacsCBPS来保障客户端的服务质量.首先分析了基于内容发布/订阅系统中实现准入控制机制的难点,给出了RacsCBPS的基本模型,在此基础上,提出了基于覆盖关系的资源需求计算方法和以订阅分发路径为基础的准入控制算法.RacsCBPS在不影响发布/订阅系统松散耦合性的情况下,能够有效地解决因系统资源不足而导致的事件过载问题,同时为系统提供了不同的准入准则,以便在系统资源利用率和服务质量保证程度之间作出不同的权衡.最后通过实验验证了准入控制机制的有效性和相应的系统资源利用率.     

面向大规模分布式计算发布订阅系统核心技术

发布/订阅系统技术具有异步、松散耦合和多对多通信的特点,适应了目前动态多变的大规模分布式计算环境的需求,有着广阔的应用前景.分析了国内外发布/订阅系统的研究现状,并从拓扑结构、事件模型和订阅模型等不同角度进行了系统的分类,然后分别就其关键问题从匹配算法、基于内容的路由算法、形式化建模和服务质量等方面进行了阐述,并对已有的典型系统进行了分析比较,指出了当前该领域研究存在的问题和不足.同时,分析了在支持语义和近似匹配来增强系统智能性所面临的挑战,展望了发布/订阅系统在支持移动计算、P2P等新型计算环境下的研究趋势.     

Effective multicast programming in large scale distributed systems

Many distributed applications have a strong requirement for efficient dissemination of large amounts of information to widely spread consumers in large networks. These include applications in e‐commerce and telecommunication. Publish/subscribe is considered one of the most important interaction styles with which to model communication on a large scale. Producers publish information on a topic and consumers subscribe to the topics they wish to be informed of. The decoupling of producers and consumers in time, space, and flow makes the publish/subscribe paradigm very attractive for large scale distribution, especially in environments like the Internet. This paper describes the architecture and implementation of DACE (Distributed Asynchronous Computing Environment), a framework for publish/subscribe communication based on an object‐oriented programming abstraction in the form of Distributed Asynchronous Collection (DAC). DACs capture the variants of publish/subscribe, without blurring their respective advantages. The architecture we present is tolerant of network partitions and crash failures. The underlying model is based on the notion of Topic Membership: a weak membership for the parties involved in a topic. We present how Topic Membership enables the realization of a robust and efficient reliable multicast on a large scale. The protocol ensures that, inside a topic, even a subscriber who is temporarily partitioned away eventually receives a published message. Copyright © 2001 John Wiley & Sons, Ltd.     

CAER:一种基于内容的自适应事件路由算法

基于内容的发布/订阅模式正受到日益广泛的重视,为构建大规模分布式系统提供了一个很好的选择。在基于内容的事件分发中,事件发布结点无需指定分发的目标地址,事件在转发的过程中根据其内容逐步路由到对事件感兴趣的目标结点。针对已有的基于内容的路由算法不能适应订阅动态变化、网络通讯开销较大的问题,提出了一种基于内容的自适应事件路由算法CAER。通过在基于内容的路由表中将订阅与订阅源结点相绑定的方式,来实现路由表的构建和维护,使得路由算法适应订阅的动态变化。实验结果表明,该算法不仅提高了事件分发的准确率,而且降低了网络的通讯开销。     

内容发布订阅系统路由算法和自配置策略研究

路由算法和动态自配置特性是实现大规模基于内容的发布订阅系统的两个关键问题.尽管已经有多种路由算法被提了出来,但是它们没有充分利用组播技术提高系统性能和节省网络带宽;此外,已有系统的网络都是静态的,不能够进行网络的自动配置.首先,提出了具有组播集群的层次性系统模型,设计了混合式路由算法,充分利用物理网络组播的特性,节省网络带宽.然后,提出了组播集群复制协议和基于内容的组播树协议CMTP,分别处理节点或者链路失效导致的网络分割以及路由的重建.实验结果表明,这些算法和协议的引入节省了网络带宽,显著提高了系统的性能,保证了系统的自配置特性.     

On the cost and safety of handoffs in content-based routing systems

Content-based routing of information and publish/subscribe have been proposed as a communication paradigm for advanced and mobile applications. In content-based routing, messages are forwarded based on queries on their content that clients and routers establish beforehand. In this paper, we examine the cost and safety of handoff protocols for subscribers and publishers in content-based routing networks. We examine two useful properties for mobility-aware content-based routing systems, namely completeness and mobility-safety. Then we determine the upper and lower bound handoff costs for three interesting topologies, a number of optimizations, and show that if completeness cannot be assumed the signalling cost is considerably higher and flooding needs to be used. We present simulation results for subscriber mobility and mobility-safety proofs for the investigated protocols. Both theoretical and experimental results show that rendezvous points may be used to significantly reduce the signalling cost of handoffs.     

基于发布/订阅模型的异构网络数据交换方法

消息数据高效传输是混合式网络的一个研究重点. 发布/订阅模型实现了消息发布者和消息订阅者之间解耦的消息传递模式, 适用于混合网络之间的消息数据传输. 通过将发布/订阅模型应用于消息数据交换, 规范了消息数据的格式, 实现了对各类通信设备的灵活管理以及基于消息内容的动态数据路由; 并利用一种基于循环调度的动态负载均衡算法, 对低速率网络和高速率网络之间的性能进行合理调度, 提高了低速率网络的性能. 模拟实验结果表明, 在混合式网络中发布/订阅模型能实现可靠的消息数据交换, 在负载平衡算法下性能更好.     

结构化P2P网络上可靠的基于内容路由协议

在结构化P2P网络上构建基于内容的发布/订阅系统,可以很好地支持大规模、高度动态的分布式应用.然而,现有的基于内容的路由协议在P2P网络上只能提供弱的可靠性保证.根据结构化P2P网络的路由协议的特点,设计了一种新型的基于内容的路由协议--基于编码区间的路由(identifier range based routing,简称IRBR)协议.IRBR协议具有良好的容错性,只要事件的发布者与订阅者之间在P2P网络中是可达的,则订阅者一定能够收到它所订阅的事件,且只收到一次.同时,该协议也比现有的协议具有更高的事件路由效率.在Pastry上开发了一个原型系统,模拟实验表明了该协议的效率和容错性.     

内容发布订阅系统的组播路由

基于内容的发布订阅系统多数采用泛洪和匹配优先的路由算法。本文提出了基于事件空间划分的发布订阅系统的实现方法,采用组播的方式实现了目标代理到多个订阅者之间的通知路由算法。与采用贪婪路由思想的单播路由算法相比较,该算法提高了在通知路由阶段的发布订阅系统的路由效率。算法对解决基于内容的发布订阅系统中相关的路由问题具有重要的作用和意义。最后给出了算法的仿真实验。     

基于信息空间划分的高效发布订阅路由技术

在大规模的基于内容发布订阅系统中,路由效率是影响系统性能的关键因素.本文在基于K-D树划分信息空间方法实现内容发布订阅系统的基础上,利用K-D树的索引机制,实现了面向扁平网络的应用层分级路由算法Spanhop.该算法机制减少了应用层路由跳,将路由效率提高到O(lnN).进一步,针对路由算法中应用层和网络层相邻关系不一致的问题,采用GNP(Global Network Position)空间与ESPN(Evem Space Partition Network)空间建立映射关系并在代理网络中维护GNP坐标索引的方法,支持应用层代理基于网络层的相邻关系搜索并选择下一跳路由.该方法减少了Spanhop路由过程中消息在网络层的实际转发路径和响应时间,在低维护代价条件下,提高了路由的效率.算法性能分析表明,上述方法解决了基于信息空间划分的内容发布/订阅系统的路由效率问题.     

一种支持语义的发布／订阅系统

针对基于内容的发布／订阅系统中消息异构导致匹配准确率降低的问题,本文通过定义事件和订阅属性间的语义关系,利用语义转换模块,提出一种支持语义的发布／订阅系统的设计方法,并将其应用于SINEA发布订阅系统中。实验结果表明,该方法可在一定程度上支持语义异构,提高匹配的准确度。     

A scalable and self-adapting notification framework for healthcare information systems

There has been a great interest in publish/subscribe systems in recent years. This interest, coupled with the pervasiveness of light-weight electronic devices, such as cellular phones and personal digital assistants, has opened a new arena in publish/subscribe networks. Currently, many broker overlay networks are static and rarely change in structure. Often, a network overlay structure is predefined or manually modified. This paper presents a dynamic broker network for disseminating critical lab and patient information in a Healthcare information system. The reported work builds upon previous network optimization research on ad hoc publish/subscribe networks. The underlying framework utilizes user-defined cost functions to satisfy quality of service constraints. In essence, the broker network optimization problem is reduced to an incremental search problem to generate low cost network configurations. Certain reliability issues are also addressed by providing a scheduling algorithm to selectively retransmit information and handle broker connectivity failures.     

Top-k/w publish/subscribe: A publish/subscribe model for continuous top-k processing over data streams

Continuous processing of top-k queries over data streams is a promising technique for alleviating the information overload problem as it distinguishes relevant from irrelevant data stream objects with respect to a given scoring function over time. Thus it enables filtering of irrelevant data objects and delivery of top-k objects relevant to user interests in real-time. We propose a solution for distributed continuous top-k processing based on the publish/subscribe communication paradigm—top-k publish/subscribe over sliding windows (top-k/w publish/subscribe). It identifies k best-ranked objects with respect to a given scoring function over a sliding window of size w, and extends the publish/subscribe communication paradigm by continuous top-k processing algorithms coming from the field of data stream processing.In this paper, we introduce, analyze and evaluate the essential building blocks of distributed top-k/w publish/subscribe systems: first, we present a formal top-k/w publish/subscribe model and compare it to the prevailing Boolean publish/subscribe model. Next, we outline the top-k/w processing tasks performed by publish/subscribe nodes and investigate the properties of supported scoring functions. Furthermore, we explore potential routing strategies for distributed top-k/w publish/subscribe systems. Finally, we experimentally evaluate model properties and provide a comparative study investigating traffic requirements of potential routing strategies.