【作者】 李超；

【导师】 赵海；

【作者基本信息】 东北大学 ， 计算机应用技术， 2009， 博士

【摘要】 互联网作为一个典型复杂系统,对其行为进行分析一直是研究的热点问题。近年来,人们广泛开展网络测量,促使网络行为的研究完成了从早期经验假设到客观数据分析的飞跃。然而,网络规模膨胀的加剧以及拓扑结构复杂程度的日渐提高,导致现有网络行为测量分析暴露出越来越多的弊端。面对庞大且复杂的互联网,过于强调局部特性及优化控制的传统研究方法阻碍了人们从宏观上对网络整体行为的把握,同时也阻碍了网络进一步的发展建设。将互联网视为一个相互关联的整体,从大规模范围对网络实施测量,进而揭示互联网在宏观拓扑结构下的整体行为和演化趋势,可以为网络业务和资源的优化与调度、安全防范以及大规模网络的设计提供有参考价值的新思想和新方法,因此必然具有重要的意义。针对网络当前发展需要,本文根据复杂网络理论,充分利用CAIDA提供的海量实测样本数据对网络的传播行为进行分析。网络传播行为在表征互联网在宏观拓扑结构下的整体行为特征方面起着重要作用,为此本文以空间为主线统计了一个测量周期内网络传播的整体行为特征,以时间为主线预测了网络在长时间跨度下传播行为的整体演化趋势,其根本目的是为了揭示互联网在宏观拓扑结构下传播行为特征规律。在明确的研究目标下,本文研究工作主要从样本数据获取、特征度量统计以及演化行为预测三个方面展开。根据工作重点,本文首先从CAIDA Skitter监测点探测到的原始样本中提取适于分析的有效样本数据,借鉴复杂网络中的物理特征量,同时结合互联网自身的传播行为特点,在IP层定义了能够表征网络传播行为的物理特征量——访问时间和访问直径。以所得的有效样本数据分别从整体和局部样本上对访问时间和访问直径进行分析,分析结果表明访问直径和访问时间之间的Pearson相关系数仅为0.346,说明两者之间为低度相关,并且主要表现为相近的访问直径其访问时间相差较大。为解释访问直径对访问时间影响较小的原因,本文针对网络的动态复杂性提出修正算法,从有效样本数据中提取网络链路延迟。对链路延迟样本数据的统计结果表明,超过90%以上的路径其最大的链路延迟消耗了访问时间的1/4以上,说明数据包在网络传播过程中,存在对传播行为有重要影响的链路延迟,并以此定义了IP层上的支配延迟。其次,考虑到支配延迟对网络的传播行为有较大影响,本文进一步研究了支配延迟的行为特征。比较了网络在不同访问时间区间上传播行为,发现访问时间相差较大的路径,其支配延迟对访问时间的比例相近,说明支配延迟对网络传播行为的影响与访问时间本身并没有必然联系,但是由于支配延迟本身在数值上相差较大,导致相近访问直径的路径其传播行为有着较大的差异,并直接表现为访问时间呈现出多峰分布特征。之后,讨论了AS自治域上的支配延迟行为特征。通过将IP级节点映射到AS自治域上,结果表明支配延迟更多地出现在AS自治域内部,并从AS自治域上的传播行为解释了支配延迟较少出现在AS自治域之间的原因。通过将产生支配延迟的IP节点对映射到实际地理位置,对支配延迟产生的主要原因进行了讨论,结果表明链路长度主要影响支配延迟的大小。最后,本文从长时间跨度上描述了网络整体的传播行为演化趋势。首先给出了基于演化的网络访问时间的定义,据此整理了近几年访问时间的样本数据,并论证了演化样本的稳定性。在此基础上,以非线性时间序列分析方法计算了访问时间演化序列的混沌特征量,分析结果表明演化序列具有混沌特征。在此基础上,通过对混沌系统中典型的Logistic模型加以改进,提出了一种基于Logistic模型的、带衰减因子的正余弦函数组合模拟振荡涨落的数学模型,以描述网络延迟的演化态势。根据实际的访问时间演化趋势,以微粒群算法分别从算法收敛性、模型拟合准确度及预测准确度等方面对备选模型参数选优。实验结果表明,最终优选模型在结构选择上比较合理,能够在短期内准确预测网络整体的传播行为。更多还原

【Abstract】 Internet is a classical instance of complex system, the analysis on its characteristic behavior has become a hot issue at present. Recently, network measurements have been widely carried out, which promotes the researches of Internet behavior to be changed from the early hypothetical phase to subjective data analysis phase. However, the increasing scale and complexity of Internet and its topological structure reveal the shortcomings of the present measurement technology. Facing the huge and complex Internet, the traditional research methods which emphasize partial characteristic and optimize control hinder people’s understanding of the Internet behaviors from a macroscopic perspective, and hinder the further development of Internet as well. To view Internet as a correlated single unit and carry out the network measurement macroscopically further demonstrate the behavioral characteristics and evolvement trend of Internet under the macro-topological structure. This in turn optimizes the Internet service and resources allotment, and provides valuable solution for the security and design of large-scale network.In order to meet the needs of network development, this dissertation uses complex network theory to analyze the network transmission behavior on the base of the giant sample data authorized by CAIDA. Since the transmission behavior of Internet has its irreplaceable typical character in the aspect of indicating the overall behavioral characteristic of network, this dissertation analyzes the overall behavioral characteristic of it within one measurement cycle with space the main clue, and forecasts its overall evolvement trend of a long period with time the main clue. The purpose is to reveal Internet transmission behavior under macroscopic topology. This research is carried out from three aspects:the collection of sample data, the statistic of network characteristic property and the forecast of network evolvement.This dissertation first uses the data from the CAIDA Skitter monitors to obtain the valid samples fitted for statistic analysis. Then two physical properties-traveling time and traveling diameter which can indicate network transmission behavior are defined on the IP level on basis of the transmission characteristic of Internet and the physical characteristic property in the complex network. Then the sample data is analyzed from both the overall and partial perspectives. It is found that the traveling times of similar traveling diameters differ a lot. The result shows that the Pearson coefficient between traveling time and traveling diameter is 0.346, which indicates that there is a low correlation between the two parameters. In order to explain the reason why the influence of traveling diameter to traveling time is not significant, this dissertation proposes a revising algorithm focusing on the dynamic complexity of network and gets link delay from the giant sample data. The statistical analysis of link delay sample data shows that the biggest link delay of more than 90% paths takes more than 1/4 of the traveling time, and the dominating delay of IP level is defined on this theory.Second, the dissertation further studies the behavior characteristic of dominant delay, because of its great influence on network transmission behavior. The detailed investigation of dominant delay reveals that the ratios of the dominant delay to the traveling time are similar among paths whose traveling time varies greatly. It indicates that there is no necessary relation between the dominant delay’s influence and traveling time. But because the dominant delays themselves differ greatly on numerical values, it causes great difference among the similar diameter’s traveling time and this is directly manifested in the multi-modal distribution of Internet traveling time. Then, a further analysis of dominant delay on AS autonomous domain is taken and it explains the reason why dominant delays seldom occur between the AS autonomous domains. By mapping the nodes from IP level to AS autonomous domain, the dissertation analyzes the transmission behavior of AS autonomous domains on topological structure and discovers that dominant delay tends to appear inside the AS autonomous domain. In addition, the dissertation discusses the main reason which causes the dominant delay by mapping the IP node to its geographical location. The results show that the length of the linking path mainly affects the scale of the dominant delay.Finally, this dissertation describes the evolving trend of transmission behavior of the whole network from great time scale. The definition of traveling time based on evolution was provided and the stability of evolving samples was proved. Basing on this, the saturated correlative dimension of chaotic attractor of Internet traveling time with phase space reconstruction and G-P algorithm are calculated, which approves that the evolvement of Internet traveling time has the characteristic of chaos. A revised logistic model with sine and cosine functions was proposed to describe the evolvement state of network transmission behavior. Moreover, particle swarm optimization (PSO) algorithm is adopted for the parameters estimation of the revised model, which is evaluated from the perspective of convergence, fitting accuracy and forecasting accuracy. The result indicates that the structure of the optimized model is reasonable and is able to reflect the movement of network transmission behavior accurately.更多还原