分布式网络中基于内容的发布订阅路由算法研究
|
摘要
随着Internet技术的发展和广泛的应用以及移动网络平台的计算的快速发展,要求分布式系统能够满足大规模、异步交互通信的计算环境需要。发布订阅系统的时间、空间和控制流方面的全面解耦合的特性,适应了现在大规模分布式应用的环境的需要,成为了支持新一代网络应用的重要的中间件平台。伴随发布订阅模型研究的发展,具有更好的适应性和更强的表达能力的基于内容的发布订阅模型成为了目前学术界研究的热点。而基于内容的发布订阅路由算法作为一个重点的研究领域,有着重要的研究价值。
本文研究了基于内容的发布订阅路由算法,重点分析了基于内容的订阅覆盖路由算法中存在的问题。在考虑了实际网络中结点性能和网络环境的差异性的基础上,结合层次分析法给出了一种强结点选择的层次计算模型。针对区域内用户兴趣关注点时段性聚集现象导致相似的订阅和发布内容的大量重复出现的现象,提出了改进的基于内容的发布订阅路由算法。为了提高单个结点的匹配计算效率,针对应用实例,给出了基于粗糙集的差别矩阵属性约简过程。最后通过仿真实验和性能分析表明,以上算法和设计整体上可以提高发布订阅的路由效率,可以减少路由表的大小、网络通信开销和时间开销并且一定程度上解决企业级的信息集成问题。
With the rapid development of Internet technology and the computing of mobile network platform, it needs distributed system that can support the computing environment of large-scale and asynchronous interactive communication. The characteristics of Publish/subscribe system is absolutely loose coupling on time, space, and the flow of control, which is suitable to large scale distributed application environment. The publish/subscribe system becomes an important middleware for supporting the next generation network. With the rapid development of research on the publish/subscribe model. The content-based publish/subscribe model which has better flexibility and more flexible ability of expression. Content-based publish/subscribe routing algorithm as an important research field has very important research value.
This paper made a research on the content-based routing algorithms of publish/subscribe. And this paper selectively analyzes the problems that exist in the content-based and subscription covering routing algorithm. This paper gives a hierarchy computing model of excellent node selection with Analytic Hierarchy Process and takes the different node performance in the different distributed network environment into account. The phenomenon that the concentration of user in the time interval will lead to many similar subscriptions and events produced, this paper gives an improved content-based routing algorithm. In order to raise the matching calculations efficiency to solve the example of application, this paper gives a process of discernible Matrix based attribute reduction in the rough set. Finally, the simulation experiments and performance analysis evaluates the algorithm in reducing routing table size, network traffic and time, and improves the matching calculation efficiency and routing efficiency for content-based publish-subscribe. It also solves the problems that exist in the enterprise information integration.
本文研究了基于内容的发布订阅路由算法,重点分析了基于内容的订阅覆盖路由算法中存在的问题。在考虑了实际网络中结点性能和网络环境的差异性的基础上,结合层次分析法给出了一种强结点选择的层次计算模型。针对区域内用户兴趣关注点时段性聚集现象导致相似的订阅和发布内容的大量重复出现的现象,提出了改进的基于内容的发布订阅路由算法。为了提高单个结点的匹配计算效率,针对应用实例,给出了基于粗糙集的差别矩阵属性约简过程。最后通过仿真实验和性能分析表明,以上算法和设计整体上可以提高发布订阅的路由效率,可以减少路由表的大小、网络通信开销和时间开销并且一定程度上解决企业级的信息集成问题。
With the rapid development of Internet technology and the computing of mobile network platform, it needs distributed system that can support the computing environment of large-scale and asynchronous interactive communication. The characteristics of Publish/subscribe system is absolutely loose coupling on time, space, and the flow of control, which is suitable to large scale distributed application environment. The publish/subscribe system becomes an important middleware for supporting the next generation network. With the rapid development of research on the publish/subscribe model. The content-based publish/subscribe model which has better flexibility and more flexible ability of expression. Content-based publish/subscribe routing algorithm as an important research field has very important research value.
This paper made a research on the content-based routing algorithms of publish/subscribe. And this paper selectively analyzes the problems that exist in the content-based and subscription covering routing algorithm. This paper gives a hierarchy computing model of excellent node selection with Analytic Hierarchy Process and takes the different node performance in the different distributed network environment into account. The phenomenon that the concentration of user in the time interval will lead to many similar subscriptions and events produced, this paper gives an improved content-based routing algorithm. In order to raise the matching calculations efficiency to solve the example of application, this paper gives a process of discernible Matrix based attribute reduction in the rough set. Finally, the simulation experiments and performance analysis evaluates the algorithm in reducing routing table size, network traffic and time, and improves the matching calculation efficiency and routing efficiency for content-based publish-subscribe. It also solves the problems that exist in the enterprise information integration.
引文
[1]Eugster P.T, Felber P., Guerraoui R.,et al. The many faces of Publish/Subscribe. ACM Journal of Computing,2003,35(2):114-131.
[2]Marchetti C., Mecella M., Scannapieco M., et al. Enabling data quality notification in cooperative information systems through a web-service based architecture. In Proceeding of the 4th International Conference on Web Information systems engineering, Roma, Italy,2003, pp.329-332.
[3]Opurchal L., Astley M., Auerbach J.S., et al. Exploiting IP multicast in content-based publish-subscribe systems. In Proceeding of the Middleware 2000, New York, USA,2000, pp.185-207.
[4]Riabov A., Liu Z.,Wolf, et al. Clustering algorithms for content-based publication-subscription systems. In Proceeding of the IEEE ICDCS'02, Vienna, Austria,2002, pp.133-142.
[5]Wong T., Katz R., Canne S.M... An evaluation of preference clustering in large scale multicast applications. In Proceedings of the IEEE INFOCOM 2000, Tel AVIV, Israel,2000, pp.451-460.
[6]Banavar G., Chandra T., Nyjgerhee B. et al. An efficient multicast protocol for content-based publish-subscribe systems. In Proceeding of the IEEE ICDCS'99, Austin, Texas,1999, pp.262-272.
[7]Xue Tao, Feng Bo-Qin. Research on routing algorithm and self-configuration in content-based publish-subscribe systems. Journal of software,2005,16(2):251-259.
[8]Carzaniga A., Rosenblum D. S., Wolf D. S.. Design and evaluation of a wide-area event notification service. ACM Transactions on Computer Systems,2001, 19(3):332-383.
[9]Li Guo-Li, Hou Shuang, Jacobsen Hans-Arno. A unified approach to routing covering and merging in publish/subscriber systems based on modified binary decision diagrams. In Proceedings of the IEEE ICDCS'05, Columbus, Ohio, USA, 2005, pp.447-457.
[10]IBM Corporation. Gryphon:publish/subscribe over public networks. IBM T.J. Watson Research Center:Technical Report,2001.
[11]Cao Feng-Yun, Singh J. P.. Efficient event routing in content-based publish-subscribe service networks. In Proceedings of the IEEE INFOCOM 2004, California, USA,2004, pp.924-940.
[12]Cugola G., Nitto E.D., Fugetta A.. The JEDI event-based infrastructure and its application to the development of the OPSS WFMS. IEEE Transactions on Software Engineering,2001,27(9):827-850.
[13]Cugola G., Nitto E. D., Fugetta. Exploiting an event-based infrastructure to develop complex distributed systems. In:Proceedings of the 20th International Conference on Software Engineering (ICSE'98), Kyoto, Japan,1998, pp.260-270.
[14]Muhl G. Large-scale content-based publish/subscribe systems [Ph.D. dissertation].Technical university of Darmstadt, Darmstadt, Germany,2002.
[15]http://www.inf.usi.ch/carzaniga/Carzaniga A., Wolf A. L...Forwarding in a Content-Based Network. In Proceedings of ACM SIGCOMM 2003 Karlsruhe, Germany, August,2003, pp.163-174.
[16]Hall C.P., Carzaniga A., Rose J., et al. A content-based networking protocol for networks. Department of Computer Science, University of Colorado:Technical Report CU-CS-979-04,2004, pp.24-28.
[17]Parzyjehla H, Miihl G.., Jaeger M.A. Reconfiguring Publish/Subscribe Overlay Topologies. In Proceeding of the 26th IEEE Int'l Conf. on Distributed Computing systems Workshops,2006, pp.182-189.
[18]Carzaniga A. Architectures for an Event Notification Service Scalable to Wide-Area Networks:[Ph D Thesis]. Politecnico di Milano,1998.
[19]Jaeger M. A., Parzyjehla H., Herrmann K. Self-Organizing Broker Topologies for Publish/Subscribe systems. In Proceeding of SAV'07,2007, pp.543-550.
[20]Saroiu S., Gummadi K. P., Dunn R. J., Gribble S. D., and H. M. Levy. Analysis of the Internet Content Delivery Systems. In Proceedings of the Fifth Symposium on Operating Systems Design and Implementation (OSDI 2002), December 2002.
[21]Object Management Group(OMG), UML Profile and Interchange Models for Enterprise Application Integration, OMG Document Formal.
[22]D. S. Rosenblum, A. L. Wolf. A Design Framework for Internet. Scale Event Observation and Notification. In Proceedings of the Sixth European Software Engineering Conference, Zurich, Switzerland, Sept.,1997, Springer-Verlag, pp.92-100.
[23]Song Jiang, Lei Guo, Xiaodong Zhang, et al. Light Flood:Minimizing Redundant Messages and Maximizing Scope of Peer-to-Peer Search. IEEE Transaction on Parallel and Distributed Systems, May 2008, VOL.19, NO.5, pp.61-614.
[24]S.Saroiu, P.Gummadi and S. Grible. A Measurement Study of Peer-to-Peer File Sharing Systems. In Proceedings of Multimedia Computing and networking Conf. (MMCN),2002.
[25]汪洋,谢江,王振宇.基于事件的发布/订阅系统模型.计算机科学.2006,33(1)：111-115.
[26]G. Starovic, V. Cahill, B. Tangney. An Event Based Object Model for Distributed Programming. In Proceedings of the International Conference on Object Oriented Information System, London, UK:Springer-Verlag,1995, pp.72-86.
[27]马建刚,黄涛,汪锦岭等.面向大规模分布式计算发布订阅系统核心技术.软件学报.2006,17(1)：135-147.
[28]P. Pietzuch, J. Bacon. Hermes:A distributed event-based middleware architecture. In Proceedings of the 22nd International Conference on Distributed Computing Systems Workshops (ICDCSW 2002).Washington:IEEE Computer Society Press, 2002,pp.611-618.
[29]J. Bacon, K. Moody, J. Bates, et al. Generic Support for Distributed Applications. IEEE Computer, March 2000, pp.68-77.
[30]B. Segall, D. Arnold, J. Boot, et al. Content based routing with Elvin. In Proceedings of AUUG2K, Canberra, Australia, and June,2000.
[31]汪锦岭,金蓓弘,李京等.基于本体的发布/订阅系统的数据模型和匹配算法.软件学报.2005,16(9)：1625-1635.
[32]H. Krawczyk, M. Bellare, and R. Canetti. HMAC:Keyed-hashing for message Authentication [EB/OL]. http://www.Faqs.org/rfcs/rfe2104.html.
[33]蔡锁章著.数学建模原理与方法.北京：海洋出版社.2000,pp.20-45.
[34]苑洪亮,史殿习,王怀民等.内容发布订阅中支持订阅覆盖的路由算法研究.计算机学报.2006,29(10)：1804-1811.
[35]http://www.cs.colorado.edu/serl/siena/.
[36]胡昔祥.基于P2P和XML内容的发行订阅系统.计算机工程与应用.2007年,43(29)：101-125.
[37]陈勤,刘昊,张旻.有环图下基于内容的发布订阅系统路由算法改进.计算机工程与科学.2009,31(4)：1-3.
[38]Pawlak Z.. Rough Sets. International Journal of Computer and Information Science,1982,11(5):311-356.
[39]Skowron A., Rauszer C.. The Discernibility Matrics and Functions in Information System Intelligent Decision Support Handbook of Applications and Advances of the Rough Sets Theory. Dordrecht:Kluwer Academic Publishers,1992, pp. 331-362.
[40]Hu X. H., Cercone N.. Learning in Relational Databases:A Rough Set Approach. International Journal of Computational Intelligence,1995,11(2):323-338.
[41]刘少辉.Rough集高效算法的研究设计.计算机学报.2003,26(5)：521-529.
[42]王珏,王任,苗夺谦等.基于Rough Set理论的“数据浓缩”计算.机器人学报.1998,21(5)：393-399.
[43]Guan J.W., Bell D.A., Rough Computational Methods for Information System. Artificial Intelligence.1998,105(1-2):77-103.
[44]刘清著Rough集及Rough推理.北京：科学出版社.2001,pp.10-28
[45]曾黄麟著.粗集理论及其应用一关于数据推理的新方法.重庆：重庆大学出版社.1996,pp.2-44
[2]Marchetti C., Mecella M., Scannapieco M., et al. Enabling data quality notification in cooperative information systems through a web-service based architecture. In Proceeding of the 4th International Conference on Web Information systems engineering, Roma, Italy,2003, pp.329-332.
[3]Opurchal L., Astley M., Auerbach J.S., et al. Exploiting IP multicast in content-based publish-subscribe systems. In Proceeding of the Middleware 2000, New York, USA,2000, pp.185-207.
[4]Riabov A., Liu Z.,Wolf, et al. Clustering algorithms for content-based publication-subscription systems. In Proceeding of the IEEE ICDCS'02, Vienna, Austria,2002, pp.133-142.
[5]Wong T., Katz R., Canne S.M... An evaluation of preference clustering in large scale multicast applications. In Proceedings of the IEEE INFOCOM 2000, Tel AVIV, Israel,2000, pp.451-460.
[6]Banavar G., Chandra T., Nyjgerhee B. et al. An efficient multicast protocol for content-based publish-subscribe systems. In Proceeding of the IEEE ICDCS'99, Austin, Texas,1999, pp.262-272.
[7]Xue Tao, Feng Bo-Qin. Research on routing algorithm and self-configuration in content-based publish-subscribe systems. Journal of software,2005,16(2):251-259.
[8]Carzaniga A., Rosenblum D. S., Wolf D. S.. Design and evaluation of a wide-area event notification service. ACM Transactions on Computer Systems,2001, 19(3):332-383.
[9]Li Guo-Li, Hou Shuang, Jacobsen Hans-Arno. A unified approach to routing covering and merging in publish/subscriber systems based on modified binary decision diagrams. In Proceedings of the IEEE ICDCS'05, Columbus, Ohio, USA, 2005, pp.447-457.
[10]IBM Corporation. Gryphon:publish/subscribe over public networks. IBM T.J. Watson Research Center:Technical Report,2001.
[11]Cao Feng-Yun, Singh J. P.. Efficient event routing in content-based publish-subscribe service networks. In Proceedings of the IEEE INFOCOM 2004, California, USA,2004, pp.924-940.
[12]Cugola G., Nitto E.D., Fugetta A.. The JEDI event-based infrastructure and its application to the development of the OPSS WFMS. IEEE Transactions on Software Engineering,2001,27(9):827-850.
[13]Cugola G., Nitto E. D., Fugetta. Exploiting an event-based infrastructure to develop complex distributed systems. In:Proceedings of the 20th International Conference on Software Engineering (ICSE'98), Kyoto, Japan,1998, pp.260-270.
[14]Muhl G. Large-scale content-based publish/subscribe systems [Ph.D. dissertation].Technical university of Darmstadt, Darmstadt, Germany,2002.
[15]http://www.inf.usi.ch/carzaniga/Carzaniga A., Wolf A. L...Forwarding in a Content-Based Network. In Proceedings of ACM SIGCOMM 2003 Karlsruhe, Germany, August,2003, pp.163-174.
[16]Hall C.P., Carzaniga A., Rose J., et al. A content-based networking protocol for networks. Department of Computer Science, University of Colorado:Technical Report CU-CS-979-04,2004, pp.24-28.
[17]Parzyjehla H, Miihl G.., Jaeger M.A. Reconfiguring Publish/Subscribe Overlay Topologies. In Proceeding of the 26th IEEE Int'l Conf. on Distributed Computing systems Workshops,2006, pp.182-189.
[18]Carzaniga A. Architectures for an Event Notification Service Scalable to Wide-Area Networks:[Ph D Thesis]. Politecnico di Milano,1998.
[19]Jaeger M. A., Parzyjehla H., Herrmann K. Self-Organizing Broker Topologies for Publish/Subscribe systems. In Proceeding of SAV'07,2007, pp.543-550.
[20]Saroiu S., Gummadi K. P., Dunn R. J., Gribble S. D., and H. M. Levy. Analysis of the Internet Content Delivery Systems. In Proceedings of the Fifth Symposium on Operating Systems Design and Implementation (OSDI 2002), December 2002.
[21]Object Management Group(OMG), UML Profile and Interchange Models for Enterprise Application Integration, OMG Document Formal.
[22]D. S. Rosenblum, A. L. Wolf. A Design Framework for Internet. Scale Event Observation and Notification. In Proceedings of the Sixth European Software Engineering Conference, Zurich, Switzerland, Sept.,1997, Springer-Verlag, pp.92-100.
[23]Song Jiang, Lei Guo, Xiaodong Zhang, et al. Light Flood:Minimizing Redundant Messages and Maximizing Scope of Peer-to-Peer Search. IEEE Transaction on Parallel and Distributed Systems, May 2008, VOL.19, NO.5, pp.61-614.
[24]S.Saroiu, P.Gummadi and S. Grible. A Measurement Study of Peer-to-Peer File Sharing Systems. In Proceedings of Multimedia Computing and networking Conf. (MMCN),2002.
[25]汪洋,谢江,王振宇.基于事件的发布/订阅系统模型.计算机科学.2006,33(1)：111-115.
[26]G. Starovic, V. Cahill, B. Tangney. An Event Based Object Model for Distributed Programming. In Proceedings of the International Conference on Object Oriented Information System, London, UK:Springer-Verlag,1995, pp.72-86.
[27]马建刚,黄涛,汪锦岭等.面向大规模分布式计算发布订阅系统核心技术.软件学报.2006,17(1)：135-147.
[28]P. Pietzuch, J. Bacon. Hermes:A distributed event-based middleware architecture. In Proceedings of the 22nd International Conference on Distributed Computing Systems Workshops (ICDCSW 2002).Washington:IEEE Computer Society Press, 2002,pp.611-618.
[29]J. Bacon, K. Moody, J. Bates, et al. Generic Support for Distributed Applications. IEEE Computer, March 2000, pp.68-77.
[30]B. Segall, D. Arnold, J. Boot, et al. Content based routing with Elvin. In Proceedings of AUUG2K, Canberra, Australia, and June,2000.
[31]汪锦岭,金蓓弘,李京等.基于本体的发布/订阅系统的数据模型和匹配算法.软件学报.2005,16(9)：1625-1635.
[32]H. Krawczyk, M. Bellare, and R. Canetti. HMAC:Keyed-hashing for message Authentication [EB/OL]. http://www.Faqs.org/rfcs/rfe2104.html.
[33]蔡锁章著.数学建模原理与方法.北京：海洋出版社.2000,pp.20-45.
[34]苑洪亮,史殿习,王怀民等.内容发布订阅中支持订阅覆盖的路由算法研究.计算机学报.2006,29(10)：1804-1811.
[35]http://www.cs.colorado.edu/serl/siena/.
[36]胡昔祥.基于P2P和XML内容的发行订阅系统.计算机工程与应用.2007年,43(29)：101-125.
[37]陈勤,刘昊,张旻.有环图下基于内容的发布订阅系统路由算法改进.计算机工程与科学.2009,31(4)：1-3.
[38]Pawlak Z.. Rough Sets. International Journal of Computer and Information Science,1982,11(5):311-356.
[39]Skowron A., Rauszer C.. The Discernibility Matrics and Functions in Information System Intelligent Decision Support Handbook of Applications and Advances of the Rough Sets Theory. Dordrecht:Kluwer Academic Publishers,1992, pp. 331-362.
[40]Hu X. H., Cercone N.. Learning in Relational Databases:A Rough Set Approach. International Journal of Computational Intelligence,1995,11(2):323-338.
[41]刘少辉.Rough集高效算法的研究设计.计算机学报.2003,26(5)：521-529.
[42]王珏,王任,苗夺谦等.基于Rough Set理论的“数据浓缩”计算.机器人学报.1998,21(5)：393-399.
[43]Guan J.W., Bell D.A., Rough Computational Methods for Information System. Artificial Intelligence.1998,105(1-2):77-103.
[44]刘清著Rough集及Rough推理.北京：科学出版社.2001,pp.10-28
[45]曾黄麟著.粗集理论及其应用一关于数据推理的新方法.重庆：重庆大学出版社.1996,pp.2-44