互联网自治系统级拓扑特征分析与建模

摘要

网络拓扑作为Internet系统的“骨髓”，其与流量和协议共同构成模拟Internet网络环境的三个基本组成部分。对Internet网络拓扑的研究一般包括：发现、解释、建模、验证以及控制等五个方面内容。目前相关研究成果主要集中于前三项，而本论文将利用经验数据对Internet拓扑（特别是AS(autonomous system，自治系统）级拓扑）特征和模型进行验证、修正及定量化。
　　 首先，给出Internet拓扑的分级方法和按粒度划分的Internet拓扑的五级结构模型；分析Internet AS级拓扑的数据BGP（border gateway protocol，边界网关协议）的来源、获取BGP数据的方法以及BGP路由表中各项数据的含义。
　　 其次，给出幂律的数学定义，分析幂律与无标度特性的关系，综述Internet AS级拓扑的四种幂律关系、以及基于经验数据的各种幂指数；分析Internet AS级拓扑的小世界效应，给出平均路径长度和聚集系数的计算公式；分析Internet AS级拓扑介数的计算方法和Internet拓扑的异配性问题；讨论Internet拓扑的富人俱乐部特性；利用AS经验数据对其幂律分布、小世界效应、异配性和富人俱乐部现象进行验证。
　　 最后，引入包括最小节点度和最大节点度在内的参数，建立满足幂律分布的Internet AS级拓扑模型；分析比较现有参数估计法的优缺点，进而提出一种基于KS的参数估计新算法；使用经验数据对该模型和算法进行分析研究。
　　 经过分析验证发现：(1)Internet AS级拓扑具有复杂网络的一般特征；(2)引入最小节点度和最大节点度等参数的幂律模型更适合Internet AS级拓扑建模；(3)利用基于KS的参数估计算法能够估计幂律模型的各参数。