论文部分内容阅读
互联网在过去的二十年经历了迅猛的发展,从最初简单的科研网络ARPANET发展成目前庞大而复杂的系统。了解互联网的拓扑结构、理解互联网的演化机制以及利用拓扑结构知识来优化网络性能、评价网络的安全性和抗毁性等对于理解互联网的整体行为具有重要的意义。作为最近兴起的复杂网络研究的一个实例,互联网拓扑结构的研究也能对复杂网络的研究起到促进作用。此外,互联网建设目的是为用户提供快速和优质的信息传输服务,对于互联网结构的深入理解也为设计更高效的路由协议提供了理论依据。本论文的研究内容主要涵盖两个方面:一是互联网自治系统(AS)级拓扑结构的研究,另一部分是静态网络拓扑结构和动态网络流的相互关系研究。在对这两个方面进行了深入的研究基础上,本文取得了以下独创性的成果:
(1)获取了更准确的中国互联网AS拓扑图,并以此为基础量化分析了采样偏好对互联网拓扑测量和推测的影响。准确的拓扑数据是互联网结构研究的基础,但互联网拓扑数据的采集通常受制于采集资源的限制,导致测量出的拓扑与真实的拓扑存在偏差。本文对中国互联网进行了大规模的主动测量,将IP层的拓扑转换成AS拓扑。得出的AS拓扑比CAIDA测量的结果多出一倍的节点数和连接数,比Routeviews的测量结果多40%的连接数。测量结果一方面验证了采样偏好会系统地丢失大量的peer-peer连接,另一方面也发现由于多宿主现象和路由聚合的存在,偏好采样也会丢失很大比例的provider-customer连接。另一方面,采样偏好也会导致互联网AS关系推测的错误。真实的互联网存在两个层次的核心:tier-1核心和tier-2核心。二者在保证互联网的连通性上具有不同的作用。
(2)发现了互联网自治系统级拓扑存在局部连接偏好性,通过改进PFP模型提出了模拟AS级拓扑的LDPFP模型。互联网的建设受诸多因素的影响。一方面要保证网络的连通性和路由的高效性,另一方面网络之间连接的建立也受制于经济因素和地区政策的限制。实际的互联网AS拓扑呈现出很强的局部连接偏好性和较高的局部连接冗余度。然而现有的互联网AS拓扑生成模型在连接选择时大多只考虑节点的度数,使得这类模型无法模拟实际互联网的局部连接行为,即使是当前最准确的互联网AS模型——PFP模型——也不例外。本论文改进了PFP模型,在新建连接时加入了对网络建设代价的考虑,提出了LDPFP(Locality-Driven PFP)模型,较好地模拟了实际互联网AS拓扑的局部聚集现象和三角形的分布。
(3)BGP策略限制的AS拓扑研究:提出了一个高效的AS路径推测算法和策略限制Betweenness的概念和计算方法。互联网自治系统之间通过边界网关路由协议(目前是BGP4)来进行路由信息交换和路由决策。BGP是基于策略的路由,它允许各个自治系统独立制订自己的路由策略。AS之间的商业关系使得实际互联网AS路径要满足一定的限制,而不总是与最短路径相符。本文提出了一种在BGP策略限制的AS拓扑中推测所有节点对之间最短AS策略路径的有效算法,在稀疏的AS互联网上算法运行的时间复杂度为D(|V|2),比现有的D(|V|3)的算法复杂度大为降低。另外,原来许多的拓扑特征分析都基于最短路径,比如Betweenness中心度。但在策略限制的AS拓扑中,Betweenness不再能准确刻画一个节点在网络中的重要程度。在有效计算AS策略路径的基础上,本文提出了策略限制Betweenness(Policy-CompliantBetweenness)的概念及计算方法,同样,在稀疏的AS网络环境下时间运行复杂度为O(|V|2)。
(4)系统地提出了依据网络结构参数预测网络拥塞的理论方法,并指出网络设计是一个多目标的优化过程,提出了网络设计效率指标来衡量一种网络设计方案的有效性。本文系统地研究了网络拓扑结构和动态网络流之间的关系,提出了网络设计是一个多目标优化的过程:一方面要提高网络的传输能力,避免拥塞,另一方面又要降低设计成本。给出了在不同网络拓扑结构、网络节点能力、路由算法和网络报文注入方式的组合下网络拥塞的系统预测方法。提出了综合衡量网络设计效率的指标(ED),用于衡量任何一种网络设计的有效性,指导宏观网络的设计。