基于谓词式覆盖技术的发布/订购机制及算法研究

Content-Based Publish Subscribe Mechanism and Algorithm Based on Predicate Covering

基于内容路由的发布/订购(Pub/Sub)技术具有异步、松散耦合和多对多通信等特点,使得能更好地应用于大规模分布式交互系统.而高效率的匹配算法、路由算法及较低的订购维护成本(规模)是实现基于内容路由的大规模Pub/Sub系统所要解决的关键问题.提出了谓词式关系(二叉树)的概念,在此基础上提出并实现了基于谓词式覆盖技术的订购算法、退订算法及启发式匹配算法(合称PRBT-*算法).通过将谓词式覆盖技术同选择性订购转发策略相结合,在提高事件匹配效率及路由效率的同时,显著降低了各级内容路由器订购规模.理论分析及大量实验对比表明,谓词式覆盖技术的引入,在降低各级内容路由器订购规模及提高算法效率和系统整体性能方面获得了良好的效果.

The content-based publish subscribe system is adapted to large-scale distributed interaction applications well and widely due to its asynchronous,many-to-many and loosely-coupled communication properties.Efficient matching and routing algorithm and dynamic adaptability are the key issues in the large-scale content-based publish subscribe systems.Consequently,in order to enhance publish subscribe system＇s matching and routing efficiency,the methods,which can reduce subscription scale and routing table sizes at internal content-based routing routers and optimize the structure of subscription expressions,are much feasible.On analysis of publish subscribe system＇s related technologies,this paper proposes the concept of predicate relation and a new structure called the predicate relation binary tree（PRBT）.PRBT describes the relations among predicates;designs and implements the subscription maintaining,unsubscription and matching algorithm based on the PRBT.By optimizing the structure of the predicate relation and subscription selectivity transmitting strategy,it not only reduces the maintained subscription sizes at each internal router,but also enhances the publish subscribe system＇s performance,such as events matching and routing efficiency.In addition,this paper explains some cases of publish subscribe system and proves the validity of the PRBT-＊ algorithm＇s properties.The theory analysis and extensive experiments reveal that the method of the predicate covering obtains better results in maintenance overhead of subscription scale,algorithm＇s efficiency and publish subscribe system＇s performance.