【摘要】：21世紀是信息技術的時代,隨著網(wǎng)絡技術的提高,信息技術的發(fā)展,計算機科學的進步,信息技術滲透到人們生活中的各處角落,為人們的工作,學習,生活帶來了巨大的便利。近年來,互聯(lián)網(wǎng)迅猛發(fā)展,網(wǎng)絡帶寬爆發(fā)式增大,高速網(wǎng)絡發(fā)展為人們的生活帶來了便利,促進了行業(yè)的發(fā)展,同時日益發(fā)展的高速網(wǎng)絡也為軟件系統(tǒng)的設計提出了難題。首先是高速網(wǎng)絡數(shù)據(jù)流量采集的問題,為了對網(wǎng)絡狀態(tài)進行統(tǒng)計,需要對流量進行抓取分析,這項技術被廣泛應用在網(wǎng)絡監(jiān)控,信息安全等方面,然而隨著網(wǎng)絡流量的爆發(fā)式增長,傳統(tǒng)的數(shù)據(jù)包捕獲方式的弊端開始顯現(xiàn)出來,為了改善這種狀況,國內外相關領域的學者進行 了不懈的努力。近年來,DPDK(Intel Data Plane Development Kit)高性能報文處理框架技術的發(fā)展使高速網(wǎng)絡下的數(shù)據(jù)包捕獲成為了可能。本文中將對DPDK技術進行簡要介紹。在各項高性能數(shù)據(jù)分析技術中,哈希算法一直占有一席之地。傳統(tǒng)哈希算法在存儲方面已經(jīng)表現(xiàn)出高性能的特點,然而在面對高速網(wǎng)絡復雜多變的情況下,經(jīng)典哈希算法的性能和健壯性有時會略顯不足。本文將重點對高速率高并發(fā)網(wǎng)絡下的哈希算法進行優(yōu)化。本文會在三方面對已有的哈希算法進行優(yōu)化,首先提出具有普適性的兩種Cache算法,PBS-CPE和Cuckoo_Cache。這兩種算法能夠在不改變哈希算法均勻性的基礎上提升查詢_效率。繼而針對布谷鳥哈希算法的插入性能進行優(yōu)化,增加哈希函數(shù)的個數(shù),設置溢出棧。最后針對分段哈希算法在高速網(wǎng)絡環(huán)境下的性能表現(xiàn)提出了兩種優(yōu)化方法:最小下標值法和布魯姆過濾器的迭代更新算法,根據(jù)這兩種優(yōu)化提出了具有skew特性的多段哈希算法,該算法在高速率高并發(fā)網(wǎng)絡環(huán)境下相較于分段哈希算法來說具有更加優(yōu)異的性能表現(xiàn)。在本論文中,設計了高速率高并發(fā)網(wǎng)絡流管理系統(tǒng),該系統(tǒng)利用DPDK技術對數(shù)據(jù)包進行采集,采用各種不同的哈希算法對數(shù)據(jù)包進行存儲,在對數(shù)據(jù)包進行處理的同時生成該種哈希算法的性能數(shù)據(jù),在統(tǒng)計結束后將該性能數(shù)據(jù)寫入到本地日志中,以便后續(xù)的性能對比。同時,在本論文中,會對各項哈希算法及論文中提出的各項優(yōu)化方面進行對比,通過實驗數(shù)據(jù)可知,PBS-CPE和Cuckoo_Cache緩存算法能夠提升哈希算法的查詢效率。針對布谷鳥哈希算法的兩種優(yōu)化方法均能極大提高布谷鳥哈希表容量不高時其算法的插入性能和健壯性。布魯姆過濾器的迭代更新法能夠減小布魯姆過濾器的假陽性率,因此在一定程度上能夠提升查詢性能。具有skew特性的多段哈希算法在高速網(wǎng)絡的特定環(huán)境下相較于分段哈希算法來說具有更佳的查詢性能。
[Abstract]:The 21st century is the era of information technology. With the improvement of network technology, the development of information technology and the progress of computer science, information technology permeates into every corner of people's life, and it can work and learn for people. Life brings great convenience. In recent years, with the rapid development of the Internet and the explosive increase of the network bandwidth, the development of high-speed network has brought convenience to people's life and promoted the development of the industry. At the same time, the increasingly developing high-speed network has also posed a difficult problem for the design of software system. First of all, the problem of high-speed network data flow collection. In order to statistics the network status, it is necessary to grasp and analyze the traffic. This technology has been widely used in network monitoring, information security, and so on. However, with the explosive growth of network traffic, the malpractice of traditional packet capture has begun to appear. In order to improve this situation, scholars at home and abroad have made unremitting efforts. In recent years, the development of, DPDK (Intel Data Plane Development Kit) high performance packet processing framework makes it possible to capture packets in high speed networks. In this paper, the DPDK technology will be briefly introduced. Among the high performance data analysis techniques, the hash algorithm has always occupied a place. The traditional hash algorithm has shown high performance in storage. However, in the face of complex and changeable high-speed network, the performance and robustness of the classical hash algorithm are sometimes slightly inadequate. This paper focuses on the optimization of hash algorithm in high speed and high speed concurrent networks. In this paper, we will optimize the existing hash algorithms in three aspects. First, we propose two universal Cache algorithms, PBS-CPE and Cuckoo_Cache.. These two algorithms can improve the query _ efficiency without changing the uniformity of the hash algorithm. Then the insertion performance of the cuckoo hashing algorithm is optimized to increase the number of hash functions and set the overflow stack. Finally, two optimization methods are proposed for the performance of piecewise hash algorithm in high-speed network: minimum subscript method and iterative updating algorithm of Bloom filter. According to these two optimization methods, a multi-segment hash algorithm with skew characteristics is proposed. The performance of this algorithm is better than that of piecewise hash algorithm in high speed and high concurrency network environment. In this paper, a high speed and high concurrency network flow management system is designed. The system uses DPDK technology to collect data packets, and uses various hash algorithms to store data packets. The performance data of the hashing algorithm is generated at the same time when the packet is processed, and the performance data is written to the local log at the end of the statistics for the subsequent performance comparison. At the same time, in this paper, the hashing algorithms and the proposed optimization aspects are compared. Through the experimental data, we can see that PBS-CPE and Cuckoo_Cache cache algorithms can improve the query efficiency of the hash algorithm. The two optimization methods for the cuckoo hashing algorithm can greatly improve the insertion performance and robustness of the cuckoo hashing algorithm when the capacity of the cuckoo hash table is not high. The iterative updating method of the Bloom filter can reduce the false positive rate of the Bloom filter, so it can improve the query performance to some extent. Multi-segment hash algorithm with skew characteristics has better query performance than segmented hash algorithm in the specific environment of high-speed network.
【學位授予單位】：北京郵電大學
【學位級別】：碩士
【學位授予年份】：2017
【分類號】：TP393.0;TP274.2

【相似文獻】

相關期刊論文 前10條

1 黃云軻;辛小龍;李成龍;李聿民;;關于對哈希算法的研究與應用[J];計算機光盤軟件與應用;2012年03期

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

3 鄒保平;;基于一致哈希算法的用電信息采集系統(tǒng)研究[J];電力信息化;2011年06期

4 劉華珠;賀前華;;基于哈希算法的網(wǎng)絡橋接器地址維護方法(英文)[J];科學技術與工程;2008年17期

5 王遠;;可重構哈希算法芯片的設計與實現(xiàn)[J];電腦知識與技術;2012年04期

6 張江,傅鶴崗;基于關聯(lián)規(guī)則的二維哈希算法的改進[J];計算機工程與設計;2005年08期

7 唐銘;史長瓊;周愷卿;張大方;;倒插入分段哈希算法[J];計算機應用;2011年02期

8 孫陽;朱宏峰;劉天華;;一種新型抗旋轉攻擊的魯棒哈希算法[J];小型微型計算機系統(tǒng);2011年04期

9 賀賢明,邵雷兵;一種基于學習的自適應哈希算法研究[J];計算機應用與軟件;2004年11期

10 邵雷兵,莊毅;一種基于學習的自適應哈希算法研究[J];微電子學與計算機;2004年08期

相關會議論文 前3條

1 劉宗斌;馬原;荊繼武;夏魯寧;;SM3哈希算法的硬件實現(xiàn)與研究[A];第26次全國計算機安全學術交流會論文集[C];2011年

2 文振q;朱為總;歐陽杰;高金花;;一種魯棒可區(qū)分的視頻感知哈希算法[A];第18屆全國多媒體學術會議（NCMT2009）、第5屆全國人機交互學術會議（CHCI2009）、第5屆全國普適計算學術會議（PCC2009）論文集[C];2009年

3 文振q;高金花;劉朋飛;杜以華;張萌;;基于分塊DCT和PCA的圖像感知哈希算法研究[A];第十五屆全國圖象圖形學學術會議論文集[C];2010年

相關重要報紙文章 前10條

1 徐魯　作家，，書評人;布魯姆博士的快樂哲學[N];中國圖書商報;2007年

2 錢文亮;布魯姆的影響詩學與修正理論[N];中華讀書報;2001年

3 喬納森;稱賞者布魯姆[N];東方早報;2011年

4 王敖;布魯姆的“最佳英語詩歌”[N];21世紀經(jīng)濟報道;2006年

5 賈曉偉;文學,不可遺忘的廢黜之王[N];北京日報;2011年

6 張龍海;哈羅德·布魯姆的文學觀[N];文藝報;2011年

7 許知遠;想起了艾倫·布魯姆[N];經(jīng)濟觀察報;2005年

8 山東社科院 戰(zhàn)旭英;艾倫·布魯姆：美國精神的沒落[N];社會科學報;2007年

9 馮克利;以古典情懷針砭現(xiàn)代性困局[N];南方周末;2007年

10 本報記者 周帆 陳姍姍;特里·布魯姆：全球化和多元化比專業(yè)化更重要[N];第一財經(jīng)日報;2005年

相關博士學位論文 前8條

1 金仲明;基于哈希算法的海量多媒體數(shù)據(jù)檢索研究[D];浙江大學;2015年

2 焦玉華;音頻感知哈希算法研究[D];哈爾濱工業(yè)大學;2010年

3 趙玉鑫;多媒體感知哈希算法及應用研究[D];南京理工大學;2009年

4 趙杠;對偶連接問題的哈希算法研究[D];復旦大學;2010年

5 胡媛媛;基于視覺模型的圖像感知哈希算法研究[D];哈爾濱工業(yè)大學;2011年

6 袁鑫攀;基于minwise哈希的文檔復制檢測的研究及應用[D];中南大學;2012年

7 艾潔;哈羅德·布魯姆文學批評理論研究[D];山東大學;2011年

8 翟乃海;哈羅德·布魯姆詩學研究[D];山東師范大學;2012年

相關碩士學位論文 前10條

1 杜研哲;高性能網(wǎng)絡流量采集和分析技術的實現(xiàn)[D];北京郵電大學;2017年

2 劉弘;基于Markov圖模型的特征哈希算法[D];江西師范大學;2015年

3 杜丹丹;基于稀疏哈希算法的目標跟蹤方法研究[D];大連理工大學;2015年

4 倪康康;基于哈希算法的圖像檢索系統(tǒng)[D];西安電子科技大學;2015年

5 高憲軍;半監(jiān)督哈希算法研究[D];西安電子科技大學;2014年

6 余俊偉;基于局部不變矩和DWT特征矩陣的圖像哈希算法[D];廣西師范大學;2015年

7 阮林林;基于局部線性嵌入和局部保持投影的圖像哈希算法[D];廣西師范大學;2015年

8 董獻倫;基于關系型數(shù)據(jù)庫的數(shù)據(jù)切分問題研究[D];山東大學;2016年

9 王建;快速近似近鄰檢索的哈希方法研究[D];山東大學;2016年

10 李秀琴;基于DWT特征點和方向直方圖的圖像哈希算法[D];廣西師范大學;2016年

本文編號：2345717