针对无标度网络的紧凑路由方法

作     者：唐明董 张国清 杨景 张国强 TANG Ming-Dong;ZHANG Guo-Qing;YANG Jing;ZHANG Guo-Qiang

作者机构：中国科学院计算技术研究所北京100190 中国科学院研究生院北京100049 湖南科技大学知识处理与网络化制造湖南省普通高校重点实验室湖南湘潭411201 

基　　金：国家自然科学基金Nos.60673168 90818004~~ 

出 版 物：《软件学报》 (Journal of Software)

年 卷 期：2010年第21卷第7期

页      码：1732-1743页

摘      要：衡量一种路由算法优劣的两个重要指标是路由表的大小和路径的长度,但这两个方面通常是互相矛盾的.紧凑路由(compact routing)研究旨在设计路由算法在这两个指标上获得优化的平衡(tradeoff).目前,已有许多学者针对任意拓扑的网络提出了普适(universal)的紧凑路由方法(compact routing scheme).但是,真实的网络都具有特定的拓扑,普适的紧凑路由方法并没有利用真实网络呈现的特定拓扑特征,因而在这类网络上未必能取得最优的性能.最近的研究发现,许多真实网络都具有无标度特征和强聚集特征,利用这两类拓扑特征,提出了一种针对这类网络的紧凑路由方法.该路由方法将网络看成是由一个骨干树和一些捷径组成,在任意源节点和目的节点之间路由,使用路径的长度不超过它们的最短路径长度加上一个整数b.路由表大小限制在O(clog2n)比特,其中,b和c是由网络结构决定的参数.实验结果表明,在无标度网络上,b和c可以同时取较小的值.与以往的紧凑路由方法相比,该方法在平均性能上表现更好.

主 题 词：紧凑路由 无标度网络 网络拓扑 仿真 伸长系数 

学科分类：12[管理学] 1201[管理学-管理科学与工程类] 08[工学] 0835[0835] 0811[工学-水利类] 081201[081201] 0812[工学-测绘类] 

核心收录：

D　O　I：10.3724/SP.J.1001.2010.03582

馆 藏 号：203225830...