摘要
在大规模的基于内容发布订阅系统中,路由效率是影响系统性能的关键因素。本文在基于K-D树划分信息空间方法实现内容发布订阅系统的基础上,利用K-D树的索引机制,实现了面向扁平网络的应用层分级路由算法Spanhop。该算法机制减少了应用层路由跳,将路由效率提高到O(lnN)。进一步,针对路由算法中应用层和网络层相邻关系不一致的问题,采用GNP(Global Network Position)空间与ESPN(Event Space Partition Network)空间建立映射关系并在代理网络中维护GNP坐标索引的方法,支持应用层代理基于网络层的相邻关系搜索并选择下一跳路由。该方法减少了Spanhop路由过程中消息在网络层的实际转发路径和响应时间,在低维护代价条件下,提高了路由的效率。算法性能分析表明,上述方法解决了基于信息空间划分的内容发布/订阅系统的路由效率问题。
Routing efficiency is key to design a large scale content-based publish/subscribe system. The K-D tree parti tion method is used to realize content-based publish/subscribe system which is based on partitioning information space. On this basis, a hierarchical application-level routing algorithm which oriented flat network with the K-D trees index mechanism was implemented. This algorithm reduced the application-level routing hops and got routing efficiency to O（INN）. Furthermore, in view of the inconsistencies of neighboring relations between application-level and the network- level in the routing algorithm, the method of constructing mapping relation between two Cartesian spaces which was GNP（Global Network Position） and ESPN （Event Space Partition Network） and maintaining coordinates of GNP in broker network was used to support brokers in application-level search and select next hop based on the neighboring relation of network-level nodes. This method reduced the real message forwarding path length and routing latency and got high routing efficiency with low maintaining cost. Performance analysis shows that these algorithms addressed efficient routing problems in content-based publish/subscribe system based on information space partitioning.
出处
《计算机科学》
CSCD
北大核心
2008年第1期103-107,共5页
Computer Science
基金
国家自然科学基金(No.90412011)
国家“863”计划(No.2003AA119030)
关键词
信息空间
路由
网络
拓扑感知
Publish/subscribe, Routing, Load balancing, Network
