摘要
传统的逆向路径转发的路由效率是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.
出处
《计算机应用研究》
CSCD
北大核心
2007年第7期238-241,共4页
Application Research of Computers
基金
国家自然科学基金资助项目(90412011)
国家"863"计划资助项目(2003AA119030)
关键词
分布式系统
路由
发布订阅
二叉树
distributed system
routing
publish/subscribe
binary tree
