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

摘要：

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

关键词：路由方法、可扩展路由、支撑图、图嵌入、拉伸度

所属期刊栏目：47

分类号：TP393(计算技术、计算机技术)

资助基金：国家自然科学基金项目60673168,90818004

在线出版日期：2010-09-10（万方平台首次上网日期，不代表论文的发表时间）

页数：共9页

页码：1225-1233