论文部分内容阅读
随着互联网的普及和计算机技术的发展,出现了各种大规模网络形态如社交网络、生物网络、交通网络、电力网络等,这些网络形态有着很多的共性,学术界统称“复杂网络”,复杂网络如今已经成为一种很热门的交叉学科。复杂网络表现小世界效应、无标度性、聚类特性等。Internet网络同样符合这样的统计特性,复杂网络的发展有助于对Internet网络的深入研究。Internet上表现无标度特性、高聚类性质,这些对Internet上的路由策略研究有着重要意义。随着当今Internet网络规模的膨胀,传统的最短路径路由算法已经很难满足需求,学术界和工业界正在寻求更好的可扩展的路由策略。针对这一困境,本文主要对基于局域信息无标度网络路由策略进行了一系列研究工作。研究的方向主要有两块:紧凑路由策略和图嵌入贪婪路由策略。具体研究工作如下:
1.实证分析了2000年和2006年Internet AS图这样的无标度网络的网络特性。网络特性表明Internet AS呈现小世界特性,高的聚类系数,度分布幂率特征。
2.在TZ紧凑路由算法的基础上重新构建了地标节点集合。提出了基于度和基于PageRank两种地标节点集合构建机制,在2000年和2006年Internet AS图上仿真表明改进的路由算法均有较好的表现。具体表现如下:基于节点度和基于PageRank算法的紧凑路由算法相对于TZ算法,平均路由表大小都大大降低了,其中2000年Internet AS图上平均路由表大小均降低了17%,2006年AS图上平均路由表大小均降低了21%,且随着网络规模的增加,差距越来越明显。
3.基于随机游走理论和降维技术构建图嵌入的贪婪路由策略。通过随机游走构建节点的转移矩阵和降维技术(PCA)得到节点的隐式空间坐标,解决网络拓扑结构和空间坐标的对应关系。通过节点连接关系和空间坐标,进行贪婪路由。通过在一系列无标度网络如足球俱乐部网络,BA无标度网络,P2P网络,Internet AS网络上进行仿真实验来测量路由性能。主要衡量了3个路由参数:成功路径比率、平均路径长度、平均伸长系数。实验结果表明在无标度网络上,论文提出的贪婪路由策略能达到很好的成功路径比率和很接近最短路由路径。在BA无标度网络上能达到90%以上的路径成功率,几乎接近于1的伸长系数。在Internet AS图上也能达到68%左右的路径成功率。