-
摘要: 覆盖路由是一种应用于基于内容的P/S系统的典型优化方案。它能够有效地删除网络中冗余的订阅，以有效的压缩路由表，减少网络通信和匹配运算开销。覆盖路由在采用无环拓扑结构的P/S系统中获得了广泛的应用，但是在有环网中的研究尚未展开。
由于在有环拓扑中两个代理间存在多条路径，因此，有环拓扑在负载均衡、出错路径/代理恢复、最佳路径选择等关键领域上，具有无环拓扑无法比拟的优势。扩展P/S系统的基于内容的路由协议（CBR），以支持有环拓扑成为了一个新的研究课题。
根据有环网的特性可知，订阅S1能够代表S2的订阅兴趣，当且仅当：①S1 S2；②S1的订阅路径与S2的订阅路径有交集。因此，为了在有环网上实现有效优化，必须使S1与S2的订阅路径最大程度重合，根据覆盖优化的定义，在重合的路径上，S2可以停止发送。
本文在Padres提出的有环网协议(ECBR)的基础上提出了有环网覆盖（Cycle Covering-based Routing CCBR）协议，通过嫁接的方式为被覆盖的订阅建立订阅路径，使S1与S2的订阅路径最大程度重合，从而有效实现覆盖优化。
文章对网络中的订阅分为独立订阅与嫁接订阅：如果订阅者提交的订阅不被网络中其他订阅覆盖、或者订阅者对收取事件的时延要求较高，则称订阅为独立订阅。如果订阅者提交的订阅被网络中其他订阅覆盖，且订阅者没有对时延提出严格要求，则称订阅为嫁接订阅。二者的区别在于，独立订阅必须洪泛到整个网络，而嫁接订阅必须嫁接在独立订阅的订阅路径上。根据CCBR协议，嫁接订阅的订阅路径由树状结构压缩为线性结构，从而大大的减少了传输开销。
文章中指出对于任意嫁接订阅GS，若存在独立订阅IS，IS GS。则：GS只需沿着IS的订阅树，建立从GS所在结点到IS所在结点的订阅路径，就可以收到所有与自己匹配的事件。文章分别针对建立和取消独立订阅和嫁接订阅的订阅路径，设计了相应的算法。
文章在Padres提供的分布式平台上针对不同的覆盖度和不同的订阅分布情况做了大量的实验，实验环境由20台内存为4GB的1.86 GHz机器构成，一共开启了42个结点，实验结果显示，在覆盖度较高的情况下(CovDeg=15)，路由表大小可以压缩至原有的25%，网络中传播的消息备份数量压缩至原有的20%，消息在单点的匹配时间压缩到原有的10%。此外消息端到端的传输时间也显著的减少。
CCBR协议保留了原有的发布订阅接口，兼容原有的匹配算法，因此能轻松移植到现有发布订阅系统中。本文对不带广告过滤器的CCBR算法进行了详细的阐述及证明；类似的，CCBR也能运用于带广告过滤器的有环网中，实现有环网上广告过滤器的覆盖。
CCBR协议为订阅提供了多种建立订阅路径的选择，因此，以CCBR协议为基础，设计相应的负载均衡和路径选择算法，成为了下一步的研究工作。Abstract: Content-based routing (CBR) publish/subscribe (P/S) system is an important class of distributed systems. This system differs from classical paradigms as messages are routed based on their content rather than their destination address, so as to provide a fine-granularity event dissemination, and support more flexibility decoupling applications. Covering-based routing is a typical optimization method of CBR and has been widely used as a building block in many distributed P/S systems, for it maintains a compact routing table and reduces the costs of communications and matching computations. So far as we know, this optimization method can only be implemented on acyclic overlay network, but cannot be directly utilized on cyclic networks. As the CBR in cyclic systems becomes a new focus of research, developing covering-based protocols and algorithms for cyclic P/S system is becoming significantly important. This paper contributes the cyclic covering-based routing protocol with corresponding algorithms to support covering-based protocol in cyclic P/S system, and implements it in PADRES, a distributed event management infrastructure based on the publish/subscribe model. -
-
[1] Eugster P T, Felber P A, Guerraoui R, Kermarrec A M. The many faces of publish/subscribe. ACM Computing Surveys, 2003, 35(2): 114-131.
[2] Carzaniga A, Rosenblum D S, Wolf A L. Design and evaluation of a wide-area event notification service. ACM ToCS, 2001, 19(3): 332-383.
[3] Carzaniga A, Wolf A L. Forwarding in a content-based network. In Proc. Conf. Applications, Technologies, Architectures, and Protocols for Computer Communications, Karlsrule, Germany, Aug. 25-29, 2003, pp.163-174.
[4] Li G L, Muthusamy V, Jacobsen H A. Adaptive content-based routing in general overlay topologies. In Proc. the 9th ACM/IFP/USENIX Int. Conf. Middleware, Leuven, Belgium, Dec. 1-5, 2008, pp.1-21.
[5] Li G L, Jacobsen H A. Composite subscriptions in content-based publish/subscribe systems. In Proc. ACM/IFIP/USENIX Int. Conf. Middleware, Grenoble, France, Nov. 1, 2005, pp.249-269.
[6] Muhl G, Fiege L, Gartner F, Buchmann A. Evaluating advanced routing algorithms for content-based publish/subscribe systems. In Proc. MASCOTS 2002, Fort Worth, USA, Oct. 11-16, 2002, pp.167-176.
[7] Yan W, Hu S L, Muthusamy V, Jacobsen H A, Zha L. Efficient event-based resource discovery. In Proc. DEBS, Nashville, USA, Jul. 6-9, 2009, Article No. 19.
[8] Hu S L, Muthusamy V, Li G L, Jacobsen H A. Distributed automatic service composition in large-scale systems. In Proc. DEBS, Rome, Italy, Jul. 1-4, 2008, pp.233-244.
[9] Chen M W, Hu S L, Liu Z Y. Covering-based routing algorithms for cyclic content-based P/S system. In Proc. the 3rd International Workshop on Frontiers in Algorithmics, Hefei, China, Jun. 20-23, 2009, pp.51-62.
[10] Dalal Y K, Metcalfe R M. Reverse path forwarding of broadcast packets. Communications of the ACM, 1978, 21(12): 1040-1047.
[11] Li G L, Hou S, Jacobsen H A. A unified approach to routing, covering and merging in publish/subscribe systems based on modified binary decision diagrams. In Proc. ICDCS, Columbus, USA, Jun. 6-10, 2005, pp.447-457.
[12] Carzaniga A. Architectures for an event notification service scalable to wide-area networks
[Dissertation]. Politecnico di Milano, Milano, Italy, 1998.[13] Muhl G. Large-scale content-based publish/subscribe systems
[Dissertation]. Darmstadt University of Technology, Germany, 2002.[14] Yuan H L, Shi D X, Wang H M, Zou P. Research on routing algorithm based on subscription covering in content-based publish/subscribe. Chinese Journal of Computers, 2006, 29(10): 1804-1812. (in Chinese)
[15] Riabov A, Liu Z, Wolf J L, Yu P S, Zhang L. Clustering algorithms for content-based publication-subscription systems. In Proc. the 22nd International Conference on Distributed Computing Systems (ICDCS 2002), Vienna, Austria, Jul. 2-5, 2002, p.133.
[16] Aguilera M K, Strom R E, Sturman D C, Astley M, Chandra T D. Matching events in a content-based subscription system. In Proc. the Eighteenth Annual ACM Symposium on Principles of Distributed Computing, Atlanta, USA, May 4-6, 1999, pp.53-61.
计量
- 文章访问数: 31
- HTML全文浏览量: 0
- PDF下载量: 1659
下载:
