Internet自治系统级拓扑模型的优化与实现

摘要

复杂网络不同于以前的网络系统，它们是动态开放的，不断成长演化而且具有生命的特点。复杂网络在局部层次上杂乱无序，而在整体层次上都呈现出小世界、高聚类度和scale-free的特点。目前复杂网络的研究方兴未艾，特别是无标度BA网络模型的提出，引发了复杂网络的研究热潮。Intemet是现实世界中重要的复杂网络之一，一直是研究的热点。Intemet作为当今人类社会信息化的标志，其规模正以指数速度高速增长的同时，其“面貌”己与原型ARPANET大相径庭，依其高度的复杂性，可以将其看作一个由计算机构成的“生态系统”。虽然Intemet是人类亲手建造的，但却没有人能说出这个庞然大物看上去到底是个什么样子，运作得如何。 Internet的迅猛发展带来了一系列问题，如网络性能、资源预留和网络管理等问题。由于在Intemet上实验非常昂贵而且因为一些商业因素的限制，研究者不可能直接在Intemet上模拟和仿真实验，因此研究者一般都利用网络拓扑模型进行实验。Intemet拓扑建模能为网络问题的分析提供一个抽象模型结构，使很多问题易于分析。拓扑模型研究经历了从随机型到层次型，再到幂律型的过程。然而目前为止，没有一个公认的模型来全面描述Intemet，研究者只能希望能更好的“逼近”Internet的实际拓扑。 本文主要进行了如下的工作： 1．分析了现有主流的拓扑模型及其算法，包括ER、Waxman、Tiers、Transit-Stub、BA等模型，从节点度分布、聚类系数、特征路径长度等方面分析了各个模型的优缺点。 2．提出了一种遵循幂律的网络拓扑生成算法PLOD+。对传统PLOD算法进行了分析，在节点连接时添加了连通性检测，并对出度大的节点实行优先连接，较好地解决了PLOD算法存在的“出度贷款过剩”问题。实验结果表明了PLOD+算法的可行性和有效性。 3．提出了一种基于幂律的层次型网络拓扑生成算法HIPL。研究表明层次性特征和幂律分布是大型网络拓扑结构的两个固有的性质，这两个性质从不同的方面反映出了大型网络的内在结构特性，层次性质是从宏观的角度反映了网络的结构特性，而幂律则从微观的角度反映了网络中节点的分布规律。各种现存的拓扑生成算法只能在某个方面反映网络的性质。HIPL算法很好地将幂律分布规律融入到层次型拓扑生成算法中，解决了原先的层次型拓扑模型不满足幂律分布规律的问题。通过对群集系数、直径、平均度数等拓扑参数的比较，表明了HIPL的有效性。

目录

文摘

英文文摘

第1章绪 论

1.1复杂网络研究背景

1.2因特网拓扑建模综述

1.3研究基础和相关定义

1.3.1自治系统级拓扑概念

1.3.2实验数据

1.3.3相关参数的定义

1.4论文安排和主要研究成果

第2章经典的网络拓扑模型

2.1随机模型

2.1.1 ER模型

2.1.2 Waxman模型

2.1.3实验与结果分析

2.2层次模型

2.2.1 Tiers模型

2.2.2 Transit-Stub模型

2.2.3实验与结果分析

2.3 BA模型

2.3.1 BA模型的提出

2.3.2 BA模型的生成机制

2.3.3 BA模型的改进

2.4相关拓扑生成器

第3章遵循幂律分布的网络拓扑生成算法PLOD+

3.1引言

3.2幂律的发现

3.3传统的PLOD算法

3.3.1 PLOD（Power-Law Out-Degree Algorithm）算法简介

3.3.2 PLOD算法存在的缺陷

3.4 PLOD+算法

3.4.1 PLOD+的设计思想

3.4.2 PLOD+的算法介绍

3.4.3实验和结果

3.5小结

第4章基于幂律的层次型拓扑模型HIPL

4.1引言

4.2 HIPL的算法描述

4.2.1算法思想

4.2.2算法步骤

4.3实验及相关结果

4.4小结

第5章总结与展望

参考文献

致谢

攻读学位期间发表的论文及参加的科研项目