论文部分内容阅读
Internet作为一个典型的复杂网络实例,其拓扑结构的分析及建模是当前的研究热点。目前相关的研究工作主要集中在拓扑统计特性的分析上,并且当前的拓扑模型大多是基于“现象”的模型,并不能反映Internet的演化本质。当前一些拓扑模型提出的一些演化机制,比如优先连接和内部边增长,都需要在真实的Internet拓扑数据中进行更进一步的分析与验证。
本文基于CAIDA(The Cooperative Association for Internet Data Analysis) Skitter项目授权的海量数据,从时间序列角度对Internet自治系统级拓扑的演化进行分析,所用数据的时间范围为从2000年1月到2006年9月。首先对基本统计量的时间演化做了分析,并基于一种新的统计方法对优先连接机制在实际Internet中的表现做了计算,分析结果表明在Internet的实际演化中,优先连接机制本身也是存在着变化的,表现为大度值节点在获得新节点连接上的优势不断减弱。
对Internet拓扑内部边增长的分析发现,在实际Internet中,并不存在PFP等模型所描述的内部边交互式增长(IG),而内部边的增长只发生在小度值节点周围,大度值节点间的内部边反而有逐渐消失的趋势。而分析也表明,内部边的重连机制也是网络拓扑演化的一个重要推动力。
为了进一步预测Internet拓扑的演化发展,本文采用了基于度值的分类方法对Internet中优先连接特性进行了刻画,将节点分成弱节点和强节点,以消除数据不足的缺陷。我们统计了弱节点的优先连接概率随时间的变化规律,并利用遗传规划算法对数据进行了拟合以得到最为准确的预测模型。实验结果表明,本文得到的预测方程在一定时间范围内能对优先连接概率进行预测,并且能重现真实Internet拓扑中优先连接机制的演化规律,可以对未来几年的Internet优先连接机制做出定性的评估。
本文对于Internet优先连接机制演化的分析,为进一步研究和改进现有网络拓扑构建模型以及设计下一代Internet路由协议提供了新的思路。