›› 2010, Vol. 25 ›› Issue (6): 1214-1224.doi: 10.1007/s11390-010-1096-1

• Sprcial Section on Software/Service in Networked Enviroments • Previous Articles     Next Articles

Covering-Based Routing Algorithms for Cyclic Content-Based P/S Overlays

Ming-Wen Chen1,2 (陈明文), Jian Zhang1,2 (张健), Song-Lin Hu1 (虎嵩林), Senior Member, CCF and Zhi-Yong Liu1 (刘志勇), Senior Member, CCF   

  1. 1. Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100190, China;
    2. Graduate University of Chinese Academy of Sciences, Beijing 100049, China
  • Received:2007-07-15 Revised:2010-05-12 Online:2010-11-01 Published:2010-11-01
  • About author:Ming-Wen Chen received her Bachelor's degree from Beijing University of Technology in 2004. She is currently pursuing her Ph.D. degree in Institute of Computing Technology, the Chinese Academy of Sciences. Her research focuses on distributed computing and publish/subscribe paradigm in particular.
    Jian Zhang received his Bachelor's degree from Huazhong University of Science and Technology in 2008. He is currently pursuing his M.S. degree in Institute of Computing Technology, the Chinese Academy of Sciences.
    Song-Lin Hu received his Ph.D. degree from Beijing University of Aeronautics and Astronautics in 2001. He has been working in Institute of Computing Technology, the Chinese Academy of Sciences as an associate professor since 2002, and went to Middleware System Research Group at the University of Toronto as a visiting scholar in 2005. He is a senior member of China Computer Federation. His research interests include distributed event based system, service computing, etc.
    Zhi-Yong Liu received his M.S. degree from Northwest Telecommunication Institute and Ph.D. degree from the Institute of Computing Technology, the Chinese Academy of Sciences in 1983 and 1987, respectively. He worked as a post doctorial fellow and a visiting scientist in The Pennsylvania University (USA), The University of Alberta (Canada), and MIT (USA) from 1988 through 1992, and 1996. He worked as the Deputy (Executive) Director General of The Directorate of Information Sciences, National Natural Science Foundation of China from 1995 through 2006. He is currently a professor in the Institute of Computing Technology, the Chinese Academy of Sciences. He is a senior member, and a council member, of the China Computer Federation. His research interests include computer algorithms, architectures, networks, and parallel and distributed processing.
  • Supported by:

    The paper is supported by the National Natural Science Foundation of China under Grant Nos. 61070027, 60752001, the National Basic Research 973 Program of China under Grant No. 2007CB310805, the National High-Tech Research and Development 863 Program of China under Grant No. 2006AA01A106, the Beijing Science and Technology Plan Projects under Grant No. Z09000100960907, the Beijing Natural Science Foundation under Grant No. 4092043, and the Co-Building Program of Beijing Municipal Education Commission.

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.

No related articles found!
Full text



[1] Su Bogong; Wang Jian; Xia Jinshi;. TST——An Algorithm for Global Microcode Compaction with Timing Constraints[J]. , 1991, 6(1): 97 -107 .
[2] Sui Yuefei;. The Polynomially Exponential Time Restrained Analytical Hierarchy[J]. , 1991, 6(3): 282 -284 .
[3] Zeng Jianchao; Hidehiko Sanada; Yoshikazu; Tezuka Xu Guangyou;. A Form-Correcting System of Chinese Characters Using a Model of Correcting Procedures of Calligraphists[J]. , 1995, 10(1): 23 -34 .
[4] Ma Xiaohu; Pan Zhigeng; Zhang Fuyan;. The Automatic Generation of Chinese Outline Font Based on Stroke Extraction[J]. , 1995, 10(1): 42 -52 .
[5] Gao Qingshi; Liu Zhiyong;. K-Dimensional Optimal Parallel Algorithm for the Solution of a General Class of Recurrence Equations[J]. , 1995, 10(5): 417 -424 .
[6] Zheng Fang; Wu Wenhu; Fang Ditang;. Center-Distance Continuous Probability Models and the Distance Measure[J]. , 1998, 13(5): 426 -437 .
[7] NIE Xumin; GUO Qing;. Renaming a Set of Non-Horn Clauses[J]. , 2000, 15(5): 409 -415 .
[8] Heng-Chang Liu and Bao-Hua Zhao. A Near-Optimal Optimization Algorithm for Link Assignment in Wireless Ad-Hoc Networks[J]. , 2006, 21(1): 89 -94 .
[9] Jian Yu and Cui-Xia Li. Novel Cluster Validity Index for FCM Algorithm[J]. , 2006, 21(1): 137 -140 .
[10] Zhong-Xuan Liu, Shi-Guo Lian, and Zhen Ren. Quaternion Diffusion for Color Image Filtering[J]. , 2006, 21(1): 126 -136 .

ISSN 1000-9000(Print)

CN 11-2296/TP

Editorial Board
Author Guidelines
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
E-mail: jcst@ict.ac.cn
  Copyright ©2015 JCST, All Rights Reserved