中文摘要：

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

英文摘要：

It is important in large networks to use routes that are as short as possible while keeping routing tables small. Generic shortest-path routing does extremely well in optimizing routes, but each node has to maintain state for all nodes. Thus generic shortest-path routing does not scale well as routing table size grows linearly with network size. The authors study scalable routing via graph embedding, i.e. embedding networks into specific coordinate spaces such that packets can be delivered with greedy forwarding. However, generic embedding usually can not guarantee packet delivery. To obtain guaranteed delivery and high routing efficiency, the idea of embedding graph spanners is presented in this paper. Based on the fact that most real-world networks have small-world and scale-free topologies, a embedding ＆ routing scheme is proposed, namely GEROUTE, which uses the shortest-path trees rooted at high-degree nodes as spanners, and assigns to each node a set of short labels such that the distance between any two nodes in the spanners can be inferred from their labels. Over the metric space defined by labels, each node only stores the labels of its neighbors and always picks the neighbor closest to the destination as next hop when routing packets. Analysis and simulations show that the scheme can perform particularly well on Internet-like graphs, outperforming prior related routing schemes.