大规模网络上基于图嵌入的可扩展路由方法

作者：唐明董; 张国清; 杨景

来源：Z201007013, 2010, (07): 1225-1233.

• 路由方法
• 可扩展路由
• 支撑图
• 图嵌入
• 拉伸度 routing scheme
• scalable routing
• spanner
• graph embeddings
• stretch

大规模网络上理想的路由方法必须同时具有较小的路由表和较短的路径.传统的最短路径路由算法只考虑优化路径,但是路由表需要维护到所有节点的路由信息,故路由表项数至少随网络规模线性增长,因此呈现较差的扩展性.针对基于图嵌入的可扩展路由进行了研究,提出将网络嵌入到由它的支撑图(spanner)导出的度量空间.利用真实网络普遍存在的小世界和无标度拓扑特征,提出了一种嵌入和路由方法——GEROUTE,它用源于高度节点的树形支撑图来构造嵌入,对节点分配较短的标记,使得节点在支撑图上的距离能够由标记推算出来,在节点标记定义的度量空间中使用贪心路由,而节点的路由表只需要存放邻居的标记.分析和仿真表明该路由方法在像...

• 出版日期2010
• 单位湖南科技大学; 中国科学院计算技术研究所; 中国科学院大学