【作者】 王宏；

【导师】 龚正虎；

【作者基本信息】 国防科学技术大学 ， 计算机科学与技术， 2008， 博士

【摘要】 近年来,随着用户数量和多种业务的急速膨胀,互联网呈爆炸性地增长,已发展成为国家政治、经济和社会生活的重要基础设施。互联网的性能及其运行稳定性成为了事关国家和社会发展的关键性问题。加强网络管理和提高网络性能已成为当务之急。网络综合流量管理研究流量采集、分析、优化的方法,其目的是实现网络流量的科学有效管理。网络综合流量管理是高性能协议设计、网络设备开发、网络规划与建设、网络管理与操作的基础,同时也是开发高性能网络应用的基础,开展网络综合流量管理关键技术研究具有重要的理论意义和实用价值。目前国内外研究人员针对网络流量管理展开研究工作,并取得许多有价值的研究成果。论文面向网络流量管理需求和特点,针对当前网络流量管理技术的不足,从流量数据采集、关键链路选择、关键流量矩阵选择、网络流量分配、网络异常流量检测、流量特征分析和综合流量管理原型系统实现等几个方面展开深入研究。主要完成了以下工作:(1)提出了两个大象流识别算法:Hits和Holds算法,克服了Estan等人提出的大象流识别算法随机丢弃报文带来采集数据不准确和需要同时多次访存无法实现高速实时数据采集的问题。Hits算法将流直接加入到流缓存表中并开始计数,当计数值超过阈值,则加入到流表中;对于在流缓存表中没有入口的报文,使用多级过滤器计数,如果多级过滤器中每一级过滤器均报超过阈值,则将该报文的流标志加入流表中。Holds算法设计了一种解决冲突问题的流缓存表,使用一级过滤器,实现报文的高速采集。论文对两个算法进行了详细描述,并对算法的有效性进行了理论分析,最后使用网络实际流量数据对算法进行了评估,与Estan等人提出的Sample and Hold及Multistage算法进行了比较。理论和实验表明Hits和Holds算法对网络大象流的误检率和漏检率均优于Sample and Hold及Multistage算法。(2)提出了一种基于主成分分析的网络关键链路发现算法PCAR及基于关键链路的网络拓扑优化算法BTop。PCAR算法通过分析网络流量的时间和空间的相关性来发现网络中的关键路径,BTop算法基于关键链路分析和图的顶点割来优化网络拓扑结构。论文用Abilene流量和拓扑数据验证了PCAR算法和BTop算法的有效性。(3)提出了关键流量矩阵发现算法MinMat。该算法引入信息熵和耗费函数等概念,先计算流量矩阵的信息熵并选取信息熵较大的若干个矩阵作为候选关键矩阵,而后对最小耗费的簇进行迭代合并,直到最后获得需要的流量矩阵。使用Abilene提供的网络流量矩阵进行实验,使用TOTEM模拟验证了MinMat算法选择结果的有效性。理论分析与实验表明MinMat比K-means、层次凝聚和CritAC具有更高的效率,选择结果具有更好的代表性。(4)提出了一种面向大象流的动态负载分配算法FEFDA。FEFDA算法采用Hits或holds算法识别长时效的大象流,对大象流采用动态最小负载分配,对小流负载进行静态分配方法,降低流抖动率和提高负载调度效率。使用NLANR数据对算法的有效性进行了评估。理论和实验表明:与传统流量分配算法相比,FEFDA具有更低的流抖动率和更好的负载均衡度。(5)提出了基于PCA和信息熵技术发现网络异常流量算法FilterA。FilterA结合报文统计信息和流的特征信息综合判断网络异常行为,同时提出使用均方差偏移作为判断异常的阈值,在保证准确性的前提下有利于提高判断速度。用校园网的真实流量数据对FilterA算法进行了测试,测试表明FilterA算法具有较低漏判率和误判率,检测方法简单,可以应用于对大规模网络流量进行异常检测。论文还使用R/S方法和聚类方差法对TOTEM公布的AS20965的流量、长沙电信骨干网流量及校园网流量进行了Hurst参数测定。实验显示:这些流量都具有自相似性,但Hurst指数各不相同,AS20965的流量具有更强的自相似性,而校园网流量的自相似性相对较弱一些。同时发现使用聚类方差法分析Hurst指数效果较差,存在较大误差。在上述研究基础之上,设计并实现了网络综合流量管理系统YHTMS。YHTMS实现了本文提出的网络综合流量管理的各种算法,YHTMS采用面向服务的体系结构,有利于实现管理控制与数据平面分离。论文重点阐述了YHTMS的总体结构、系统布署、数据处理流程、数据库设计、核心系统的调用和依赖关系,对实现技术进行了详细描述,最后展示了系统的运行效果。综上所述,本文的工作针对网络综合流量管理技术中的关键问题提出了有效的解决方案,对于推进网络综合流量管理技术的理论研究和实用化具有一定的理论价值和应用价值。更多还原

【Abstract】 With the significant increasing of the number of users and diverse applications, the Internet has grown explosively and become a fundamental infrastructure for national political systems, economic systems and social activities. The performance of internet and its running stability have become the key issues related to the national development of economics and socities. Research on the network traffic management framework and the related techniques including traffic data collection, traffic analysis, traffic control and application-level traffic monitoring, plays an important role in order to improving the network performance, its efficiency, robustness and availability. Network traffic management is the foundation to establish network behavior models and understand the inner principles behind complex network behaviors. It also provides valuable reference for the designing of high performance protocols, the development of network devices, the planning and deployment of networks, the network management and operations, and the development of effective applications.Though many researchers have carried out quite a lot of research work on network traffic management and have made many valuable achievements so far, we argue that the modeling theory, key techniques, implementation methods in this area are still far from the expectation of network operators, with new issues and open problems keeping on emerging. In this thesis, deep research work on network traffic management framework, flow data collection, critical link selection, critical traffic matrices selection, network traffic allocation, abnormal traffic detection, analysis of traffic characteristics, is conducted to meet the requirements of synthetic network traffic management. The main contributions of our work are as follows:(1) Novel algorithms for detecting large flows: Hits and Holds Two novel algorithms, Hits and Holds, are proposed to detect large flows quickly and correctly, which overcome the shortcomings of Estan’s algorithms. In Estan’s algorithms, statistic data is imprecise since packets are sampled randomly, and it is difficult to implement the algorithms in hardware since simultaneous memory accessing is required. Hits and Holds solve the above problems effectively using flow cache table and multi-level filters. The efficiency of the algorithms is analyzed theoretically and evaluated using real-sampled network traffic data. The results show that Hits and Holds have lower ratios of checking error and undetected error than Estan’s algorithms.(2) An efficient algorithm to find critical network links and its application on network topology optimization: PCAR and BTop An algorithm named as PCAR is proposed based on the method of primary component analysis (PCA). In the algorithm, the space and time correlation among traffic flows on long timescales is analyzed to find the critical links of networks. Based on the critical link analysis in PCAR, a network topology optimization algorithm is proposed, called BTop. The efficiency of the two algorithms is verified by the real traffic and topology data sampled from the Abilene network.(3) An entropy-based algorithm for finding critical traffic matrices: MinMat Aim at extracting a small number of“critical”traffic matrices from thousands of measured traffic matrices, we developed an approximation algorithm, called MinMat. It uses the concept of information entropy to select some candidate matrices at first, then merges the clusters of matrices with minimal cost into the final critical matrices. The algorithm is evaluated using a large number of real traffic matrices collected in the Abilene network. The calculation results are verified by the TOTEM simulator. The experimental results demonstrate that the MinMat algorithm is more effective than the K-means, Hierarchical Agglomeration, the CritAC algorithm, and a small number of critical traffic matrices selected by the MinMat algorithm is sufficient to portray the characteristics of all sampled traffic data.(4) A new traffic allocation algorithm for elephant flows: FEFDAA new hybrid approach called FEFDA is proposed to allocate traffic rate for long-lived flows (elephant flows), while forwarding short-lived flows statically. FEFDA uses the Hits algorithm or the Holds algorithm to detect long-lived flows and allocate traffic rates for them in order to achieve dynamic load balance. The effectiveness of the algorithm is evaluated by simulation with NLANR traces. The results show that flow flapping is considerably reduced and better load balance is achieved than traditional schemes.(5) An abnormal traffic detection algorithm based on PCA and information entropy: FilterAThe FilterA algorithm is designed to detect network anomalies. It uses the statistical traffic information and characteristics of flows to determine abnormity. The mean square deviation is used as the threshold metric for decision so that the algorithm can run fast with the guarantee of correctness. The algorithm is tested using the data collected from our campus network. The test results show that the FilterA algorithm has low ratio of detection error and undetected error. It is simple and can be applied in large-scale networks.Traffic character analysis using Hurst parameters,Using the R/S method and the variance-time method, the Hurst parameter values of the traffic data from the Abilene network, the Changsha telecom backbone network and our campus network are calculated. The results verify that all traffic data exhibits the self-similarity feature, although the Hurst parameter values are different for traffic data from different networks. The data of Abilene network shows stronger self-similarity feature than the data of campus network.Based on above research work, a network traffic management prototype named YHTMS is designed and implemented. All the algorithms proposed are integrated in YHTMS. YHTMS adopts service-oriented architecture in favor of the separation of control plane and data plane. The implementation methods are described and the running results are demonstrated.In summary,several efficient algorithms are developed to tackle the key problems in network traffic management, which provides a basis for future research and development.更多还原