基于事件空间划分的高效发布订阅路由算法  

Event Space Partition-based Routing Algorithm of Publish Subscribe System

作　　者：逯鹏[1] 刘旭东[1] 林学练[1] 王斌[1] 

机构地区：[1]北京航空航天大学计算机学院,北京100083

出　　处：《计算机应用研究》2007年第7期238-241,共4页Application Research of Computers

基　　金：国家自然科学基金资助项目(90412011);国家"863"计划资助项目(2003AA119030)

摘　　要：传统的逆向路径转发的路由效率是O(N),基于事件空间划分的贪婪路由技术将效率提高到O(N1/d)。在此基础上,采用祖先队列的路由数据结构,建立虚拟层叠网络中不同路由域之间的相邻关系,并通过祖先队列记录域间代理的相邻关系,实现了分层分路由域的代理之间的分级跨跳路由,称为Spanhop路由。通过性能分析表明,使用该路由算法,路由的平均路径减少到O(lnN),同时取消了事件空间维度d对路由效率的影响。这种方法通过增加少量的存储代价,提高了在大规模的面向广域网的发布订阅系统当中的路由效率。Publish/subscribe routing technology was the key technology of the publish/subscribe system. The routing efficiency of the traditional method which was reverse path forwarding was O（N）. The method which based on event space partition improve the efficiency to O（ N^1/d ）. This paper used a data structure named ancestor queue in building up neighborhood relations among different routing areas in the virtual overlay network ,and recording these realations in the ancestor queue. This ancestor queue could aid to implement the Spanhop routing between the delegates of the routing areas. The routing performance analysis shows that the Spanhop method impoves routing efficiency to O（In N）. It also eliminate the effect of the event space dimensions to routing efficiency. Spanhop is an efficient routing method in the publish/subscribe system which oriente wide area network with a few more storage cost.

关 键 词：分布式系统 路由 发布订阅 二叉树 

分 类 号：TP393.2[自动化与计算机技术—计算机应用技术]