AS级Internet拓扑的特征演化及关联性分析

介绍Internet的复杂网络特征,采用RouteViews项目公布的数据分析了近十年来Internet拓扑特征的演化情况,总结出Internet发展的三个阶段.针对网络拓扑演化过程中不同特征参数之间可能存在的关联性问题,采用相关性计算的方法对网络特征参数进行了聚类分析,并使用主分量分析法指出在Internet演化过程中起主要作用的参数集合.     

Internet自治系统级拓扑复杂网络特征分析与验证

为深入理解和认清Internet复杂巨系统的不变特征和动态规律,分析研究Internet自治系统级拓扑的复杂网络特征,给出幂律分布和无标度条件的数学描述以及寻找两者之间的关系,分析小世界网络的两个重要特征,即较短平均路径长度和较大聚集系数,讨论匹配性问题和富人俱乐部现象,基于上述理论结果和BGP经验数据计算自治系统级拓扑的最大节点度、平均节点度、聚集系数和最大团数,发现自治系统级拓扑具有幂律分布、异配性以及富人俱乐部现象等复杂网络特征,得到幂指数、匹配系数以及富人俱乐部系数等重要特征参数。     

网络风险评估中网络节点关联性的研究

在网络风险评估领域中,为了提高评估的准确性,很多研究工作中都引入了网络节点间的连通性,然而,这种性质还不足以表达出各节点间基于物理连通关系之上的某种特殊的逻辑关系,如一方对另一方独有资源的控制关系.为此,文中引入了网络节点关联性(NNC)的概念,通过对实践过程中若干种访问情景的分析,提出了NNC的分类方法,然后讨论了NNC的发现方法,并举例阐明了NNC在网络风险评估中的应用及作用.通过深入地分析和对比可以看出,利用NNC可以将若干孤立的弱点联系起来,有助于分析网络的安全风险;此外,NNC在包含各协议层连通性的基础上丰富了网络节点间独有的特权关系,利用NNC也有助于提高检测网络弱点和网络攻击的准确性.     

复杂网络理论在Internet拓扑特性分析中的应用

利用复杂网络理论对Intemet进行研究,探索Internet复杂系统的现象,揭示这些现象背后的起源、不变特性以及动态规律,已成为计算机科学领域所关心的重要问题之一。介绍了复杂网络的研究简史,研究的主要内容、方法与工具,以及复杂网络的基本概念和特征量,并对目前在Intemet拓扑特性分析研究方面的研究成果及经验结果进行了归纳总结,同时给出了复杂网络理论在Intemet研究中的发展方向。     

OSPF协议下的网络数学拓扑模型

研究Internet的拓扑结构是认识Internet的必然过程,也是在更高层次上开发利用Internet的基础,拓扑建模就是把这个看似混乱的网络拓扑简单化,建立使人们更容易理解网络的结构。Internet网被分成多个自治系统。自治系统内路由器间的通信通过路由选择协议,目前常用的路由选择协议有RIP,OSPF,EIGRP。该文通过OSPF协议的特点,通过图论的知识抽象出在OSPF协议下网络的地理超图结构,并且通过超图结构用简单的图论语言模拟OSPF自治系统的形成过程。     

互联网AS关系推断算法研究

为了提高自治域(autonomous systems,AS)关系推断的准确性,分析了现有的AS关系推断算法,指出其存在的不足,提出以IRR数据库为基础,由已知As关系推断未知AS关系的改进算法.首先从IRR数据库中提取AS关系,并以此为种子推断未知的AS关系,通过计算AS的度提取包含对等关系的三元组来推断对等关系,最后修正推断结果.实验结果表明,该算法能显著提高AS关系特别是对等关系的准确性.     

Internet网络拓扑建模

首先概述Internet网络拓扑建模的意义和分类;总结现阶段已发现的主要网络拓扑特性与度量指标;然后分析、讨论自治域级和路由器级的Internet网络拓扑建模与最新的研究成果;最后针对目前拓扑建模中存在的难点和问题给出总结,并展望未来的研究发展方向.     

网络实验平台的设计

本文主要讨论了网络实验系统的设计原则和方案,分析了网络实验课程中,实验课程项目应根据各个层次水平进行设计,在兼顾相关重要技术的前提下,尽可能模拟实际应用环境的需求.     

因特网拓扑特征之间的关联性研究

研究拓扑特征之间的关联性对于简化拓扑建模具有重要的意义。dK特征序列理论上能够计算得到所有的网络拓扑特征,因此可以用来进行拓扑特征的关联性研究。在分析dK序列定义的基础上,推导出一些重要的网络拓扑特征与dK序列之间的关系,这些关系可以用来简化拓扑图特征比较,因此有助于减少因特网拓扑建模研究的模型验证部分的工作量。     

基于社区与结构熵的异质网络影响力最大化

影响力最大化的目的是在网络中发现能够触发最大数量的剩余节点参与到信息传播过程的一小群节点.目前异质信息网络中影响力最大化的研究通常从网络中抽取同质子图、或基于节点局部结构的元路径进行节点影响力的评估,没有考虑节点的全局特征和网络中高影响力节点间的集群现象给种子集合最终扩散范围造成的影响损失.文中提出了一种基于社区与结构熵的异质信息网络影响力最大化算法,该算法能够有效地从局部和全局两个方面度量节点的影响.首先,通过构建元结构保留节点在网络中的局部结构信息和异质信息度量节点的局部影响;其次,利用节点所属社区在整个网络中的权重占比对节点的全局影响进行度量;最后,综合求出节点的最终影响并选出种子集合.在真实数据集上进行的大量实验结果表明所提算法有较好的有效性和效率.     

Internet自治系统级拓扑发现系统的研究与实现

Internet由多个自治系统相互连接而成,AS间的互联结构体现了Internet的宏观结构。研究AS间的连接关系可以辅助分析网络特性。该文研究了Internet AS级拓扑发现,实现了一个Internet AS级拓扑发现系统。该系统分析BGP路由表得到Internet AS级拓扑并直观显示出来。分析了AS级拓扑的度分布属性,分析结果显示生成的拓扑具有幂律分布特性。     

一种计算因特网AS拓扑的最短路径的快速算法

最短路径是因特网AS(autonomous system)拓扑的一个重要特征,AS间的路由路径一般是AS之间的最短路径.因特网服务提供商之间复杂的商业关系导致AS之间存在复杂的路由关系,从而影响AS路由路径的选择,因此在计算AS拓扑中最短路径时需要考虑AS间的路由关系.提出了一种计算AS拓扑中最短路径的算法,算法基于无向图的宽度优先最短路径算法,时间复杂度为O(nm),这里n和m分别为拓扑图中节点和边的个数.通过实验发现,与现有的计算AS拓扑最短路径的时间复杂度为O(n3)的算法相比,该算法在实现同样精确度的前提下大幅缩短了计算时间.     

层析成像技术在网络属性估算中的应用研究

网络层析成像技术在网络属性估算中的应用主要分为网络拓扑判定和链路属性估算两个重要应用.主要讨论通过对网络上的主机进行单播的测量来获得网络的逻辑拓扑及链路属性,并提出进行网络属性估算的新方案.首先介绍基于延时的"三明治"测量方案和相关网络拓扑判定算法,随后通过实验对网络拓扑判定的系统聚类树算法进行了分析,在此基础上提出进行网络属性估算的新方案.     

基于信息关联拓扑的互联网社交关系挖掘

针对目前基于监督学习的关系抽取方法需要标注大量训练数据和预先定义关系类型,提出了一种基于词语共现信息构建关联网络并在关联网络上进行图聚类分析的人物关系提取方法。首先,从新闻标题数据获得关联度较高的500个人物对用于关系抽取研究;然后,抓取关联人物对所在新闻数据,对其进行预处理,并利用词频-逆向文档频率（TF-IDF）得到人物对共现句子中的关键词;其次,基于词语共现信息得到词语之间的关联,进而建立关键词关联网络;最后,利用对关联网络进行图聚类分析以获得人物关系。在关系抽取的实验中,与传统基于词语共现和模式匹配的中文实体关系提取方法相比,所提方法在准确率、召回率和平衡F分数（F-score）上分别提升了5.5,3.7和4.4个百分点。实验结果表明,所提算法能够在没有标注训练数据的条件下,有效地从新闻数据中抽取丰富且高质量的人物关系数据。     

互联网前缀劫持攻击研究

前缀劫持攻击是互联网BGP域间路由系统中的首要安全威胁,至今还无有效解决该问题的方案。以前缀劫持攻击为研究对象,分析了前缀劫持攻击产生的具体原因,展现了该攻击在自治系统内部以及在自治系统之间的表现形式与影响;从前缀劫持攻击的危害程度,分析并划分了前缀劫持攻击的基本形态,讨论了各种前缀劫持攻击的基本特性。分析结果表明,子前缀劫持的危害最严重,确切前缀劫持的影响最复杂,而父前缀劫持最易被发现且危害相对较小。     

互联网覆盖路由技术研究

对互联网覆盖路由相关研究工作进行了调研;按照Internet分层概念重点考查了网络层和传输层的覆盖路由的结构和方法;并且考查了覆盖路由其他相关问题的研究,包括覆盖路由性能的影响因素、多个覆盖网络路由之间的相互作用等.分析了已有研究工作的关键技术的优缺点.最后讨论了未来可能的研究方向,为互联网覆盖路由的研究提供参考.     

因特网AS级拓扑的健壮性测度与健壮性演化

以自治系统(autonomous system,AS)为基本组成单元的域间路由系统是因特网(Internet)的核心组成部分,研究Internet AS级拓扑的健壮性对于整个Internet的健壮性设计具有重要意义.2003年的北美停电事故与2006年、2010年的台湾地震表明,当今Internet的健壮性仍亟待增强.本文结合基本的拓扑理论与实际的路由策略约束,利用Internet AS级拓扑的层次特性,从"单个AS"和"全局拓扑"两个不同的层面研究AS级拓扑的健壮性测度与健壮性演化:1)提出了对单个AS的健壮性测度的方法;2)对全局AS级拓扑的健壮性测度提出了k容错模型---任意k个AS级的节点/链路故障不影响任何其他两个AS之间的连通性;3)基于健壮性测度方法和k容错模型,提出了健壮性演化的机制与方法.对当今Internet AS级拓扑的统计分析表明:1)25.8%的AS节点还不能承受1个AS级的链路故障,26.4%的AS节点还不能承受1个AS节点故障;2)将现有的AS级拓扑演化为k容错拓扑不仅能保证任意节点对之间可达性的k容错,在故障数超过k的情况下,k容错拓扑的健壮性也显著优于原拓扑.