Internet拓扑中连接机制的演化分析及预测

论文摘要

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路由协议提供了新的思路。

论文目录

• 摘要
• Abstract
• 目录
• 第一章 绪论
• 1.1 Internet拓扑研究概述
• 1.1.1 Internet拓扑研究背景
• 1.1.2 Internet拓扑研究现状
• 1.1.3 Internet拓扑研究的意义
• 1.2 课题的提出
• 1.3 课题的可行性研究
• 1.4 本文的组织结构
• 第二章 Internet拓扑研究方法
• 2.1 Internet的复杂性
• 2.2 Internet的统计特性
• 2.3 本文用到的主要拓扑模型
• 2.3.1 BA模型
• 2.3.2 PFP模型
• 2.3.3 Inet模型
• 2.4 数据的可靠性研究
• 2.4.1 数据来源
• 2.4.2 数据结构
• 2.4.3 数据甄选
• 2.5 本章小结
• 第三章 Internet拓扑特征量分析
• 3.1 Internet拓扑常规特征量分析
• 3.1.1 节点数
• 3.1.2 节点度
• 3.1.3 聚类系数
• 3.2 优先连接机制分析
• 3.2.1 优先连接的定义
• 3.2.2 富人俱乐部连通性分析
• 3.2.3 优先连接机制的演化分析
• 3.2.4 Internet网络的幂律分析
• 3.3 本章小结
• 第四章 内部边演化分析
• 4.1 边的有效性分析
• 4.2 内部边的变化
• 4.2.1 内部边的增长
• 4.2.2 内部边的消亡
• 4.2.3 内部边的重连
• 4.3 内部边增长的成因
• 4.4 内部边演化分析的意义
• 4.5 本章小结
• 第五章 Internet网络的优先连接预测模型
• 5.1 Internet拓扑建模意义
• 5.2 遗传规划建模相关性质
• 5.2.1 建模的对象
• 5.2.2 GP建模方法
• 5.2.3 实验结果及模型评价
• 5.3 优先连接概率预测模型的应用
• 5.4 本章小结
• 第六章 总结与展望
• 6.1 本文的贡献
• 6.2 未来的工作
• 参考文献
• 致谢