Key algorithm in content-based publish/subscribe system based on subscription partitioning
-
摘要: 在基于内容发布订阅系统中,将订阅兴趣在多个代理之间划分是代理负载均衡的重要方法.提出了基于事件空间的K-D树划分方法.通过将事件空间划分成负载相同的区域,优化了系统负载均衡的性能.基于逻辑空间最短距离的概念提出了与划分相关的事件和兴趣路由算法以及单播和多播混和的通知路由方法.两种路由算法减少了事件匹配操作,提高了路由的效率.利用事件空间的区域合并和分裂实现了系统的自组织.实验和与相关工作比较表明,划分方法及其相关算法的引入提高了系统的可伸缩、容错和负载均衡性能.Abstract: Partitioning subscriptions interest among multi-brokers acts as an important way to resolve load balancing problem in content-based publish/subscribesystem. A new method of event space-based subscription partition with K-D tree was proposed. With this method, the event space was partitioned into zones with equal load and so the system performance of load balancing was improved. Based on the minimum distance of logical event space, new routing algorithms were proposed for event and subscription routing and another hybrid of unicast and multicast routing policy for notification routing. All these algorithms and policy significantly reduced the event matching cost and promoted the routing efficiency in content-based publish/subscribe system. At the same time, the method of splitting and merging zones of event space was used to realize the self-organizing of the publish/subscribe system. The experiment and related works show that the introduction of partitioning methods and related algorithms can improve the scalability, fault tolerant and load balancing performance of content-based publish/subscribe system.
-
Key words:
- distributed computer systems /
- routers /
- load balancing /
- network protocols
-
[1] Eugster P Th,Felber P A,Guerraoui R,et al. The many faces of publish/subscribe[J].ACM Comput Surv,2003,35(2):114-131 [2] Fitzpatrick G,Kaplan S,Mansfield T, et al. Supporting public availability and accessibility with Elvin:experiences and reflections[J]. Comput Supported Coop Work CSCW Int J,2002,11(3-4):447-474 [3] IBM Corporation. Achieving scalability and throughput in a publish/subscribe system . RC23103(W0402-026),2004 [4] Carzaniga A,Rosenblum D S,Wolf A L.Design and evaluation of a wide-area event notification service[J]. ACM Trans Comput Syst, 2001,19(3):332-383 [5] Cugola G,Di Nitto E,Fuggetta A.The JEDI event-based infrastructure and its application to the development of the OPSS WFMS[J]. IEEE Trans Software Eng,2001,27(9):827-850 [6] 薛涛,冯博琴.内容发布订阅系统路由算法和自配置策略研究[J].软件学报,2005,16(2):251-259 Xue Tao,Feng Boqin.Research on routing algorithm and self-configuration in content-based publish-subscribe system[J].Journal of Software,2005,16(2):251-259(in Chinese) [7] Riabov A,Liu Zhen,Wolf J L,et al.Clustering algorithms for content-based publication-subscription systems Proc Int Conf Distrib Comput Syst. Piscataway,NJ:IEEE,2002:133-142 [8] Banavar G, Chandra T, Mukherjee B,et al.Efficient multicast protocol for content-based publish-subscribe systems Proc Int Conf Distrib Comput Syst. Piscataway,NJ:IEEE,1999:262-272 [9] Wang Y M,Qiu L,Achlioptas D,et al.Subscription partitioning and routing in content-based publish/subscribe networks Dahlia M.16th International Symposium on Distributed Computing.Berlin:Springer-Verlag,2002:28-30
点击查看大图
计量
- 文章访问数: 2823
- HTML全文浏览量: 63
- PDF下载量: 912
- 被引次数: 0