【摘要】：21世紀(jì)是信息技術(shù)的時(shí)代,隨著網(wǎng)絡(luò)技術(shù)的提高,信息技術(shù)的發(fā)展,計(jì)算機(jī)科學(xué)的進(jìn)步,信息技術(shù)滲透到人們生活中的各處角落,為人們的工作,學(xué)習(xí),生活帶來了巨大的便利。近年來,互聯(lián)網(wǎng)迅猛發(fā)展,網(wǎng)絡(luò)帶寬爆發(fā)式增大,高速網(wǎng)絡(luò)發(fā)展為人們的生活帶來了便利,促進(jìn)了行業(yè)的發(fā)展,同時(shí)日益發(fā)展的高速網(wǎng)絡(luò)也為軟件系統(tǒng)的設(shè)計(jì)提出了難題。首先是高速網(wǎng)絡(luò)數(shù)據(jù)流量采集的問題,為了對網(wǎng)絡(luò)狀態(tài)進(jìn)行統(tǒng)計(jì),需要對流量進(jìn)行抓取分析,這項(xiàng)技術(shù)被廣泛應(yīng)用在網(wǎng)絡(luò)監(jiān)控,信息安全等方面,然而隨著網(wǎng)絡(luò)流量的爆發(fā)式增長,傳統(tǒng)的數(shù)據(jù)包捕獲方式的弊端開始顯現(xiàn)出來,為了改善這種狀況,國內(nèi)外相關(guān)領(lǐng)域的學(xué)者進(jìn)行 了不懈的努力。近年來,DPDK(Intel Data Plane Development Kit)高性能報(bào)文處理框架技術(shù)的發(fā)展使高速網(wǎng)絡(luò)下的數(shù)據(jù)包捕獲成為了可能。本文中將對DPDK技術(shù)進(jìn)行簡要介紹。在各項(xiàng)高性能數(shù)據(jù)分析技術(shù)中,哈希算法一直占有一席之地。傳統(tǒng)哈希算法在存儲方面已經(jīng)表現(xiàn)出高性能的特點(diǎn),然而在面對高速網(wǎng)絡(luò)復(fù)雜多變的情況下,經(jīng)典哈希算法的性能和健壯性有時(shí)會略顯不足。本文將重點(diǎn)對高速率高并發(fā)網(wǎng)絡(luò)下的哈希算法進(jìn)行優(yōu)化。本文會在三方面對已有的哈希算法進(jìn)行優(yōu)化,首先提出具有普適性的兩種Cache算法,PBS-CPE和Cuckoo_Cache。這兩種算法能夠在不改變哈希算法均勻性的基礎(chǔ)上提升查詢_效率。繼而針對布谷鳥哈希算法的插入性能進(jìn)行優(yōu)化,增加哈希函數(shù)的個(gè)數(shù),設(shè)置溢出棧。最后針對分段哈希算法在高速網(wǎng)絡(luò)環(huán)境下的性能表現(xiàn)提出了兩種優(yōu)化方法:最小下標(biāo)值法和布魯姆過濾器的迭代更新算法,根據(jù)這兩種優(yōu)化提出了具有skew特性的多段哈希算法,該算法在高速率高并發(fā)網(wǎng)絡(luò)環(huán)境下相較于分段哈希算法來說具有更加優(yōu)異的性能表現(xiàn)。在本論文中,設(shè)計(jì)了高速率高并發(fā)網(wǎng)絡(luò)流管理系統(tǒng),該系統(tǒng)利用DPDK技術(shù)對數(shù)據(jù)包進(jìn)行采集,采用各種不同的哈希算法對數(shù)據(jù)包進(jìn)行存儲,在對數(shù)據(jù)包進(jìn)行處理的同時(shí)生成該種哈希算法的性能數(shù)據(jù),在統(tǒng)計(jì)結(jié)束后將該性能數(shù)據(jù)寫入到本地日志中,以便后續(xù)的性能對比。同時(shí),在本論文中,會對各項(xiàng)哈希算法及論文中提出的各項(xiàng)優(yōu)化方面進(jìn)行對比,通過實(shí)驗(yàn)數(shù)據(jù)可知,PBS-CPE和Cuckoo_Cache緩存算法能夠提升哈希算法的查詢效率。針對布谷鳥哈希算法的兩種優(yōu)化方法均能極大提高布谷鳥哈希表容量不高時(shí)其算法的插入性能和健壯性。布魯姆過濾器的迭代更新法能夠減小布魯姆過濾器的假陽性率,因此在一定程度上能夠提升查詢性能。具有skew特性的多段哈希算法在高速網(wǎng)絡(luò)的特定環(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.
【學(xué)位授予單位】：北京郵電大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2017
【分類號】：TP393.0;TP274.2

【相似文獻(xiàn)】

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

1 黃云軻;辛小龍;李成龍;李聿民;;關(guān)于對哈希算法的研究與應(yīng)用[J];計(jì)算機(jī)光盤軟件與應(yīng)用;2012年03期

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

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

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

5 王遠(yuǎn);;可重構(gòu)哈希算法芯片的設(shè)計(jì)與實(shí)現(xiàn)[J];電腦知識與技術(shù);2012年04期

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

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

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

9 賀賢明,邵雷兵;一種基于學(xué)習(xí)的自適應(yīng)哈希算法研究[J];計(jì)算機(jī)應(yīng)用與軟件;2004年11期

10 邵雷兵,莊毅;一種基于學(xué)習(xí)的自適應(yīng)哈希算法研究[J];微電子學(xué)與計(jì)算機(jī);2004年08期

相關(guān)會議論文 前3條

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

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

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

相關(guān)重要報(bào)紙文章 前10條

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

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

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

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

5 賈曉偉;文學(xué),不可遺忘的廢黜之王[N];北京日報(bào);2011年

6 張龍海;哈羅德·布魯姆的文學(xué)觀[N];文藝報(bào);2011年

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

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

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

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

相關(guān)博士學(xué)位論文 前8條

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

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

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

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

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

6 袁鑫攀;基于minwise哈希的文檔復(fù)制檢測的研究及應(yīng)用[D];中南大學(xué);2012年

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

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

相關(guān)碩士學(xué)位論文 前10條

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

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

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

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

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

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

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

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

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

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

本文編號：2345717