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

目录

文摘

英文文摘

第一章 绪论

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 未来的工作

参考文献

致谢