Internet路由级宏拓扑结构的TL模型

摘要

Internet作为一个典型的复杂网络实例，对其宏观拓扑结构的特征分析及建模研究是目前研究的热点问题，受到学术界广泛关注。近年来人们在该领域的研究取得了长足的进展，尤其是在Internet拓扑结构的分析中发现了幂律分布规律之后，提出了许多遵循幂律特征的拓扑生成算法以及拓扑模型，完成了从早期纯粹的经验假设到客观数据分析，从单纯的计算机网络研究到复杂系统特征化研究的建模过程的飞跃。但这些提出的模型大多为自治系统层面(autonomous system，AS-level)的Internet拓扑模型，而在相对更细粒度的，更能表现：Intemet本质特征的路由器层面(router-level)Internet拓扑建模，由于规模巨大，以及获取完整的路由级拓扑方面的困难，目前研究还较少。揭示路由级Internet宏观拓扑结构的特征规律并建模，是帮助人们用其来对Internet进行分析、预报、决策或控制的需要，也是进行Internet相关的研究的基础，因此必然具有重要的意义。 Internet拓扑研究与复杂网络学术界将Internet拓扑建模研究的内容大致归结为三个问题：(1)如何获得一份完整而准确的Internet拓扑数据；(2)如何对Internet网络拓扑特征进行分析并建立模型；(3)如何使用模型构造一幅类似于Internet的拓扑图。这三个问题分别对应于三个研究方向，即拓扑结构测量、拓扑特征发现与建模以及可视化拓扑生成器开发。其中拓扑特征发现与建模是重点，拓扑特征发现指针对Internet测量拓扑结构的特征分析与特征参量提取，建立模型指根据特征参量建立拓扑模型，即本文提出的TL模型，这是本文研究的核心内容；拓扑结构测量作为拓扑特征分析与建模的基础与前提，也是本文中比较重要的部分；而拓扑结构的可视化问题由于涉及范围较广，可单独做为研究课题，因此不在本文中做为重点研究内容。 本文首先针对分布在世界范围内的21个CAIDA监测点通过主动探测方法得到的路由级Internet拓扑测量结果，分别进行同名IP解析与单点测量导致的采样偏见问题分析。在使用CAIDA iffinder同名IP测量结果集对多组Internet测量数据解析时，发现每组中合并的路由数占总路由数的3％～8％，边数则从7％～30％不等。合并路由数增长比较平缓，说明测量结果集数量庞大，基本上已经完全覆盖了iffinder提供了同名解析空间。在单点测量问题分析中发现，随着测量点数的增加，新测量到的路由增量呈y=88782.0-18993×ln(x)的对数曲线分布形式。进一步分析表明，以目前CAIDA监测点的分布情况，只有当测量点数达到至少107个时才可能完全解决采样偏见问题，即没有路由器在测量中遗失。而本文测量结果集中CAIDA监测点数为21，因此需要在未来工作中对拓扑测量问题做进一步研究。其次，本文对Internet拓扑结构特征进行了不同层面的分析与研究。首先论述了Internet测量拓扑的幂律分布特征，包括frequency-degree幂律分布、degree-rank幂律分布与CCDF(d)-degree幂律分布等，发现Internet测量拓扑具有非常明显的frequency-degree幂律分布与degree-rank幂律分布规律。其中。frequency-degree幂律分布符合幂律指数为2.1406的分布规律，而degree-rank幂律分布则分为两部分，主体节点服从幂律指数为0.84639的分布，而度值最大的部分节点却符合幂律指数为0.29981的分布规律。在CCDF(d)-degree幂律分布研究中发现，Weibull分布要比幂律分布拟合效果更好，也就是说，对于本文Internet拓扑来说，其节点度的CCDF不一定符合幂律分布。其次研究了Internet平均度值分布情况，并统计得出叶子路由在Internet测量路由总数所占比重平稳地保持在17％附近的结论，说明Internet拓扑结构中，叶子路由的分布具有一定规律性；之后研究了Internet拓扑结构的谱密度分布与无符号拉普拉斯谱(SLS)分布结果，通过对拓扑结构各异的五种采样拓扑图，分别进行谱密度．特征值分布分析，发现五组分析结果表现出高度的一致性，证明了Internet拓扑结构的自相似性。而通过四组3000点采样拓扑进行SLS分布分析，发现尽管四组3000点采样路由与连接互不相同，但SLS谱分布却非常相似，四组采样拓扑在特征值λ=1处重数均较高，重数次高的特征值都群聚在λ=2处。在特征值从2～10<'3>变化过程中表现出较明显的幂律分布特性，其幂指数值保持在3.2813至3.8013之间，特征指数接近。这同样从另一个角度证明了Internet拓扑结构的自相似性。 之后，本文根据Internet拓扑特征分析结果(特征参量)提出了一个基于三层(ThreeLevel)路由节点的TL模型。针对部分源于Internet拓扑统计分析的模型特征参数，进行了以无符号拉普拉斯谱密度(SLS)分布结果的为校验值(评估函数)的遗传优化。对优化后模型，本文从定性分析、定量分析与可视化结果的直观视觉角度予以了分析与评价。定性分析结果表明，TL模型兼具纯静态与纯动态模型的优点，即避免了纯静态模型下过多的人为干预与控制，也避免部分纯动态模型不能产生叶子节点的问题。在定量分析部分，对两份3000节点的TL生成拓扑分别进行了幂律分布分析、谱密度分布分析及规格化拉普拉斯谱(NLS)分析，分析结果表明，TL生成拓扑表现了Internet拓扑特征，TL模型可接受。本文最后给出了TL模型的生成算法。

目录

文摘

英文文摘

声明

第一章绪论

1.1 Internet宏拓扑建模概述

1.1.1 Internet研究现状

1.1.2 Internet拓扑建模的研究现状

1.1.3拓扑建模的层次

1.2本文研究目标和主要研究内容

1.3论文的章节安排

第二章Internet拓扑特征分析

2.1 Internet的复杂网络特征

2.1.1网络的拓扑特征量

2.1.2复杂网络的基本模型及分类

2.1.3 Internet的复杂网络本质

2.2 Internet的拓扑结构模型

2.2.1随机图模型

2.2.2 Inet模型

2.2.3 BA及其改进模型

2.3 Internet的拓扑测量

2.3.1测量方法

2.3.2测量结果

2.4本章小结

第三章测量拓扑数据分析

3.1同名IP解析

3.1.1解析方法

3.1.2解析结果

3.2单点测量

3.2.1单点测量的量化分析

3.2.2单点测量对幂律的影响

3.3本章小结

第四章Internet拓扑的TL模型

4.1 Internet幂律分析

4.1.1幂律分布特征

4.1.2分析结果

4.2 Internet拓扑的度分析

4.3谱密度分析

4.3.1采样算法

4.3.2采样拓扑的谱密度分布

4.3.3无符号拉普拉斯谱(SLS)

4.3.4分析结果

4.4 TL拓扑模型

4.4.1 TL模型形式

4.4.2参数优化

4.4.3 TL模型生成算法

4.5本章小结

第五章模型分析与评价

5.1定性分析

5.2定量分析

5.2.1幂律分析

5.2.2谱密度分析

5.2.3规格化拉普拉斯谱(NLS)分析

5.3可视化结果

5.3.1算法思想

5.3.2可视化Internet拓扑

5.4本章小结

第六章总结与展望

6.1本文的总结

6.2本文的主要贡献

6.3未来工作

参考文献

致谢

作者从事科学研究和学习经历的简历

攻读博士学位期间发表的论著、获奖情况