本文選題：流量測量 + 公平抽樣　； 參考：《解放軍信息工程大學(xué)》2014年碩士論文

【摘要】：網(wǎng)絡(luò)流量測量是認(rèn)識和理解互聯(lián)網(wǎng)運(yùn)行行為、收集和分析網(wǎng)絡(luò)協(xié)議運(yùn)行性能、重新規(guī)劃和優(yōu)化網(wǎng)絡(luò)結(jié)構(gòu)并改善網(wǎng)絡(luò)服務(wù)質(zhì)量的重要手段。高速骨干網(wǎng)上的數(shù)據(jù)具有高速、海量的特點(diǎn),為減輕流量測量系統(tǒng)中存儲器和處理器的壓力,面向高速骨干網(wǎng)的網(wǎng)絡(luò)流量測量普遍采用部分流狀態(tài)維護(hù)的方法,該方法包括數(shù)據(jù)抽取、流信息存儲和查詢以及超時(shí)流管理三部分。目前,主要存在以下三方面問題:1)現(xiàn)有抽樣算法偏重于大流抽樣,造成小流的統(tǒng)計(jì)結(jié)果準(zhǔn)確性低,算法的公平性差;2)現(xiàn)有查詢算法使用k次哈希以降低信息查詢時(shí)的誤判率,但是增加了算法的計(jì)算復(fù)雜度,導(dǎo)致算法的實(shí)時(shí)性差;3)缺乏結(jié)合大流保護(hù)和超時(shí)流表項(xiàng)及時(shí)刪除的方法,導(dǎo)致現(xiàn)有超時(shí)流管理算法的實(shí)時(shí)性和準(zhǔn)確性差。針對上述問題,論文依托國家863計(jì)劃重大專項(xiàng)——“面向三網(wǎng)融合的統(tǒng)一安全管控網(wǎng)絡(luò)”,對面向高速骨干網(wǎng)的網(wǎng)絡(luò)流量測量關(guān)鍵技術(shù)展開研究。首先,針對現(xiàn)有抽樣算法公平性差的問題,提出一種基于流數(shù)約減的公平抽樣算法。然后,從信息的存儲、查詢和管理角度出發(fā),提出基于二維空間地址和Sketch的查詢算法和基于有區(qū)分LRU(least recent used)的超時(shí)流管理算法。本文主要研究內(nèi)容如下:1、提出了一種基于流數(shù)約減的公平抽樣算法(Adaptive Fair Sampling based on Reducing Flow Numbers,AFS-RFN)�；诮档涂臻g復(fù)雜度并保證流公平抽樣的原則,算法對新到達(dá)的分組,采取流數(shù)約減或非線性抽樣的策略抽樣,創(chuàng)建并維護(hù)樣本流集合。性能分析和仿真結(jié)果表明,與ANLS(Adaptive Non-Linear Sampling)算法相比,AFS-RFN算法可處理速率為42.7Gbps鏈路上的流量測量任務(wù),通過降低流數(shù)約減概率Pf,算法可適用于更高速率鏈路;并提高了算法的公平性。2、提出了基于二維空間地址和Sketch的查詢算法(Two-Dimensional Space Address and Sketch,TDSAS)。基于提高查詢實(shí)時(shí)性的原則,算法根據(jù)柯西不等式——兩數(shù)之和與兩數(shù)之積之間的關(guān)系,將信息的線空間查詢擴(kuò)展到面空間查詢,通過將二維空間地址和二維數(shù)據(jù)結(jié)構(gòu)Sketch結(jié)合存儲和查詢信息,降低算法查詢時(shí)的計(jì)算復(fù)雜度。基于理論分析和仿真結(jié)果表明,在相同誤判率的情況下,與CMS(Count-min Sketch)查詢算法相比,TDSAS查詢算法將算法的計(jì)算復(fù)雜度由O(d)降低至O(d),并將算法的實(shí)時(shí)性提高24.4%。3、提出了基于有區(qū)分LRU的超時(shí)流管理算法。基于降低大流漏判率并保證超時(shí)流實(shí)時(shí)刪除的原則,設(shè)計(jì)一個(gè)由大流保護(hù)端(熱端)和超時(shí)流處理端(冷端)構(gòu)成的有區(qū)分LRU隊(duì)列,根據(jù)其兩端長度比l和區(qū)分新到分組應(yīng)歸屬熱端或冷端的閾值T,推導(dǎo)出流大小n和l與漏判率之間的關(guān)系式,并由n設(shè)置T值。理論分析和仿真結(jié)果表明,與傳統(tǒng)LRU算法相比,根據(jù)該關(guān)系式合理設(shè)置T和l值,可將大流的漏判率降低一個(gè)數(shù)量級,同時(shí)可支持速率為40.9Gbps鏈路上流量的實(shí)時(shí)測量。
[Abstract]:Network traffic measurement is an important means to understand and understand the behavior of Internet, to collect and analyze the performance of network protocols, to replan and optimize the network structure and to improve the quality of service.The data of high-speed backbone network has the characteristics of high speed and mass. In order to reduce the pressure of memory and processor in the traffic measurement system, the method of partial stream state maintenance is widely used in network traffic measurement for high-speed backbone network.The method includes data extraction, stream information storage and query, and timeout flow management.At present, there are three main problems: 1) the existing sampling algorithms focus on the large stream sampling, which results in the low accuracy of the statistical results of the stream, and the poor fairness of the algorithm. 2) the existing query algorithms use k hashes to reduce the misjudgment rate when the information is queried.However, the computational complexity of the algorithm is increased, which leads to the lack of the method of combining the large flow protection and the timely deletion of timeout flow table items, which leads to the poor real-time and accuracy of the existing time-out flow management algorithms.In view of the above problems, the paper studies the key technology of network traffic measurement for high-speed backbone network based on the national 863 project, "the unified security management and control network for the integration of three networks".Firstly, aiming at the problem of poor fairness of the existing sampling algorithms, a fair sampling algorithm based on the reduction of the number of streams is proposed.Then, from the point of view of information storage, query and management, a query algorithm based on two-dimensional spatial address and Sketch and a time-out flow management algorithm based on differentiated LRU(least recent are proposed.The main contents of this paper are as follows: 1. An adaptive Fair Sampling based on Reducing Flow numbers (AFS-RFN) algorithm based on reduced stream number is proposed.Based on the principle of reducing the space complexity and ensuring fair sampling of the flow, the algorithm adopts the strategy of reducing the number of flows or nonlinear sampling to create and maintain the set of sample flows for the newly arrived packets.The performance analysis and simulation results show that compared with the ANLS(Adaptive Non-Linear sampling algorithm, the AFS-RFN algorithm can handle the traffic measurement task on the 42.7Gbps link, and the algorithm can be applied to the higher rate link by reducing the probability of the reduction of the flow number.The fairness of the algorithm is improved, and a two-dimensional Space Address and Sketchn algorithm based on 2-D spatial address and Sketch is proposed.Based on the principle of improving the real-time performance of the query, the algorithm extends the line space query of information to the surface space query according to the relation between the sum of two numbers and the product of two numbers.By combining two-dimensional spatial address and two-dimensional data structure Sketch to store and query information, the computational complexity of the algorithm is reduced.Based on the theoretical analysis and simulation results, it is shown that, in the case of the same error rate,Compared with the CMS(Count-min search algorithm, the computational complexity of the algorithm is reduced from LRU to Odetd, and the real-time performance of the algorithm is improved by 24.40.3. an algorithm of time-out flow management based on differentiated LRU is proposed.Based on the principle of reducing the large flow leakage rate and ensuring the real-time deletion of the time-out flow, a differentiated LRU queue is designed, which consists of a large stream protection end (hot end) and a time-out flow processing terminal (cold end).Based on the ratio of length of two ends to l and the threshold T which distinguishes that the new to the packet should be assigned to the hot or cold end, the relationship between the flow size n and l and the leakage rate is derived, and the T value is set by n.The theoretical analysis and simulation results show that compared with the traditional LRU algorithm, the leakage rate of large flow can be reduced by one order of magnitude according to the reasonable setting of T and l values, and the rate of real-time measurement on 40.9Gbps link can be supported.
【學(xué)位授予單位】：解放軍信息工程大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2014
【分類號】：TP393.06

【參考文獻(xiàn)】

相關(guān)期刊論文 前10條

1 朱海婷;丁偉;繆麗華;龔儉;;UDP流量對TCP往返延遲的影響[J];通信學(xué)報(bào);2013年01期

2 張震;汪斌強(qiáng);陳庶樵;郭通;;幾何布魯姆過濾器的設(shè)計(jì)與分析[J];電子學(xué)報(bào);2012年09期

3 李玉峰;蘭巨龍;薛向陽;;面向三網(wǎng)融合的統(tǒng)一安全管控技術(shù)[J];中興通訊技術(shù);2011年04期

4 張進(jìn);鄔江興;鈕曉娜;;空間高效的數(shù)據(jù)包公平抽樣算法[J];軟件學(xué)報(bào);2010年10期

5 張玉;方濱興;張永錚;;高速網(wǎng)絡(luò)監(jiān)控中大流量對象的識別[J];中國科學(xué):信息科學(xué);2010年02期

6 陳一驕;盧錫城;孫志剛;;面向流管理的哈希算法研究[J];計(jì)算機(jī)工程與科學(xué);2008年04期

7 謝鯤;秦拯;文吉剛;張大方;謝高崗;;聯(lián)合多維布魯姆過濾器查詢算法[J];通信學(xué)報(bào);2008年01期

8 王風(fēng)宇;云曉春;王曉峰;王勇;;高速網(wǎng)絡(luò)監(jiān)控中大流量對象的提取[J];軟件學(xué)報(bào);2007年12期

9 王洪波;韋安明;林宇;程時(shí)端;;流測量中基于測量緩沖區(qū)的時(shí)間分層分組抽樣[J];軟件學(xué)報(bào);2006年08期

10 程光,龔儉,丁偉,徐加羚;面向IP流測量的哈希算法研究[J];軟件學(xué)報(bào);2005年05期

，

本文編號：1737887