• 
    

    
    

      99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看 ?

      利用抽樣技術(shù)和分層多哈希方法實(shí)現(xiàn)長(zhǎng)流的識(shí)別

      2016-09-22 12:50:02景泉
      現(xiàn)代經(jīng)濟(jì)信息 2016年5期
      關(guān)鍵詞:長(zhǎng)流存儲(chǔ)空間哈希

      景泉

      摘要:本文提出了一種利用抽樣技術(shù)和分層多哈希的方法來(lái)識(shí)別長(zhǎng)流,選取合適的哈希函數(shù),能夠方便還原出五元組信息,減少了資源的開(kāi)銷(xiāo);使用多哈希函數(shù),可以極大的降低哈希沖突,保證數(shù)據(jù)的準(zhǔn)確性。

      關(guān)鍵詞:抽樣技術(shù);分層多哈希

      中圖分類(lèi)號(hào):TP393.08 文獻(xiàn)識(shí)別碼:A 文章編號(hào):1001-828X(2016)005-000-01

      隨著互聯(lián)網(wǎng)規(guī)模和用戶(hù)數(shù)量的迅速擴(kuò)大,導(dǎo)致網(wǎng)絡(luò)流量不斷增大,網(wǎng)絡(luò)行為越劇復(fù)雜,安全攻擊的頻率和對(duì)網(wǎng)絡(luò)造成的破壞性也在急劇的增長(zhǎng)。為了更好的保障網(wǎng)絡(luò)安全,需要對(duì)網(wǎng)絡(luò)流量進(jìn)行有效的監(jiān)測(cè)和分析。現(xiàn)代網(wǎng)絡(luò)面臨的又一緊迫任務(wù)是為用戶(hù)提供可靠的業(yè)務(wù)質(zhì)量保障。而用戶(hù)獲得的服務(wù)質(zhì)量以及網(wǎng)絡(luò)供應(yīng)商可提供的服務(wù)能力都必須通過(guò)流量數(shù)據(jù)分析獲得。因此,研究網(wǎng)絡(luò)流量特性是改善網(wǎng)絡(luò)服務(wù)質(zhì)量問(wèn)題的一個(gè)關(guān)鍵。而網(wǎng)絡(luò)流量測(cè)量技術(shù)是目前唯一能用于分析網(wǎng)絡(luò)狀況、掌握流量特性的有效方法。

      一、國(guó)內(nèi)外研究概況、水平和發(fā)展趨勢(shì)

      Cristian Estan在長(zhǎng)流識(shí)別的過(guò)程中就提出了一種抽樣技術(shù)和哈希技術(shù)結(jié)合的算法——sample and hold算法。sample and hold 算法是按照一定的概率對(duì)字節(jié)進(jìn)行抽樣,如果一個(gè)報(bào)文被抽到,且其所屬的流標(biāo)識(shí)未被創(chuàng)建,則以概率P創(chuàng)建這個(gè)流標(biāo)識(shí);而一個(gè)流的標(biāo)識(shí)在內(nèi)存中已經(jīng)存在,則更新屬于該流標(biāo)識(shí)的報(bào)文的記錄。這種方法可以較精確地識(shí)別長(zhǎng)流,所用的內(nèi)存空間也較小,但它對(duì)每個(gè)報(bào)文進(jìn)行處理的同時(shí)都要訪(fǎng)問(wèn)內(nèi)存,因此要求內(nèi)存的速度達(dá)到線(xiàn)速,給測(cè)量系統(tǒng)帶來(lái)很大的壓力。同時(shí)哈希的過(guò)程中也會(huì)造成一定的沖突,導(dǎo)致一定的誤差。并且在哈希的過(guò)程中還要記錄流標(biāo)識(shí)的信息,會(huì)帶來(lái)存儲(chǔ)空間的增加。

      國(guó)內(nèi)的網(wǎng)絡(luò)測(cè)量研究起步較晚,近年研究網(wǎng)絡(luò)行為學(xué)逐步增加。長(zhǎng)流占據(jù)了大部分的網(wǎng)絡(luò)通信量,了解長(zhǎng)流的信息就能對(duì)一次通信行為有著很好的描述。長(zhǎng)流識(shí)別在網(wǎng)絡(luò)測(cè)量領(lǐng)域也有很大的研究,提出了多種識(shí)別長(zhǎng)流的方法。

      二、識(shí)別過(guò)程

      (一)分層隨機(jī)抽樣

      分層隨機(jī)抽樣:如果每層中的抽樣都是獨(dú)立地按照簡(jiǎn)單隨機(jī)抽樣進(jìn)行的,那么這樣的抽樣稱(chēng)為分層隨機(jī)抽樣,所得的樣本稱(chēng)為分層隨機(jī)樣本。

      分層隨機(jī)抽樣由于抽樣在每一層中獨(dú)立進(jìn)行,所以各層的數(shù)據(jù)可以用于對(duì)本層(子總體)進(jìn)行較精確的參數(shù)估計(jì),然后將這些總和全部累加,就能得到對(duì)總體的一個(gè)較精確的參數(shù)估計(jì)。使用分層隨機(jī)抽樣可使樣本中分布更加均勻,從而具有更好的代表性。這樣就避免了樣本分布不平衡的現(xiàn)象。

      (二)Bloom Filter的使用

      Bloom Filter最早由Burton Bloom提出,并開(kāi)始廣泛的應(yīng)用到數(shù)據(jù)庫(kù)領(lǐng)域中,最近在網(wǎng)絡(luò)研究中得到了廣泛的應(yīng)用,并取得了一些進(jìn)展。如在高速網(wǎng)絡(luò)測(cè)量方面。

      Bloom Filter是一個(gè)基于多個(gè)哈希函數(shù)映射來(lái)壓縮參數(shù)空間的數(shù)據(jù)結(jié)構(gòu),它支持成員查詢(xún)、隨機(jī)存儲(chǔ)。其具體的工作原理是,它描述了一個(gè)源串的集合S={x1, x2…, xn},我們把xi稱(chēng)作是一個(gè)源串。申請(qǐng)一個(gè)內(nèi)存大小為m比特位的存儲(chǔ)空間A,并定義一個(gè)哈希函數(shù)集合H={H1, H2,…, Hk},我們把Hi稱(chēng)作是一個(gè)哈希函數(shù)。對(duì)于源串集合S中的任何一個(gè)元素xi來(lái)說(shuō),通過(guò)集合H中的K個(gè)獨(dú)立的哈希函數(shù)映射到存儲(chǔ)空間A中,得到K個(gè)[1…m]之間的數(shù),并把存儲(chǔ)空間A中的這K個(gè)對(duì)應(yīng)比特位置1。也可以利用哈希函數(shù)集合H的映射過(guò)程來(lái)檢驗(yàn) 是否屬于集合S。下面的兩個(gè)算法分別描述了源串集合S中的元素被哈希到存儲(chǔ)空間的過(guò)程和驗(yàn)證給定元素 是否屬于源串集合S的過(guò)程。

      (三) 閾值的確定

      識(shí)別長(zhǎng)流的第一步就是要確定閾值。中給出了兩種確定閾值的辦法。第一種方法是考慮到收集的數(shù)據(jù)集合存在著重尾分布的特征。第二種方法更加的直接。閾值的確定會(huì)考慮到操作的環(huán)境。它要求計(jì)算一個(gè)參數(shù),這個(gè)參數(shù)與總通信量有著密切的關(guān)系。利用這一參數(shù)可以把流分為兩類(lèi):一類(lèi)就是超出了這個(gè)參數(shù)值,我們這一類(lèi)的流定義為長(zhǎng)流。另一類(lèi)是沒(méi)有超過(guò)這個(gè)參數(shù)值,就把它們定義為短流。

      本文采用的確定閾值的方法類(lèi)似第二種辦法。即在測(cè)量的過(guò)程中利用一個(gè)計(jì)數(shù)器記錄總的報(bào)文數(shù),設(shè)為M。我們約定把占據(jù)報(bào)文總數(shù)1%以上的流記為長(zhǎng)流,則閾值T=M/100。在測(cè)量結(jié)束后,Bloom Filter中具有相同流標(biāo)識(shí)的報(bào)文的命中次數(shù)如果超出了T值,就把這個(gè)流識(shí)別出來(lái)。

      然后,我們要在測(cè)量的時(shí)間內(nèi)選用簡(jiǎn)單的哈希函數(shù)對(duì)到來(lái)的報(bào)文按照?qǐng)?bào)文頭中的流標(biāo)識(shí)分組,并對(duì)分組后的流標(biāo)識(shí)進(jìn)行Counting Bloom Filter變換。測(cè)量結(jié)束后,利用第二部分中所介紹的長(zhǎng)流的定義,對(duì)每個(gè)哈??臻g中的命中次數(shù)加以統(tǒng)計(jì),把超出閾值的流識(shí)別出來(lái),并存儲(chǔ)在存儲(chǔ)器中。我們利用段地址重疊的比特還原出主機(jī)的原始信息。中指出活躍IP分布是非常不均勻的重尾分布,相鄰網(wǎng)段或者IP活躍度較大。但是他們的活躍度相差較大不會(huì)影響我們分析的結(jié)論,我們可以用短標(biāo)簽重疊的比特進(jìn)行糾正。

      (四)識(shí)別的基本步驟

      1.構(gòu)建一個(gè)多哈希站的模塊,每個(gè)哈希站都存放一個(gè)獨(dú)立的哈希函數(shù)

      2.利用分層哈希方法依次哈希到對(duì)應(yīng)的存儲(chǔ)空間

      3.統(tǒng)計(jì)在某一時(shí)間粒度下總的報(bào)文數(shù),并計(jì)算閾值。

      4.對(duì)TCP的五元組進(jìn)行Counting Bloom Filter變換。

      5.統(tǒng)計(jì)每個(gè)流的報(bào)文數(shù),把超過(guò)閾值的流記錄下來(lái)。

      6.對(duì)記錄下的長(zhǎng)流進(jìn)行原始信息的還原。

      圖1利用Counting Bloom Filter進(jìn)行長(zhǎng)流識(shí)別的過(guò)程。結(jié)構(gòu)體BF由兩個(gè)成員組成。分別攜帶了主機(jī)原始信息和經(jīng)過(guò)哈希函數(shù)作用后所命中該存儲(chǔ)空間中的報(bào)文數(shù)。圖中把IP地址分為三段,每一段都維護(hù)一個(gè)相應(yīng)的Bloom Filter數(shù)據(jù)結(jié)構(gòu)。把超出閾值的信息存儲(chǔ)在存儲(chǔ)器中。

      圖1 ?利用Counting Bloom Filter進(jìn)行長(zhǎng)流識(shí)別的過(guò)程

      三、結(jié)論

      本文使用抽樣技術(shù)和分層多哈希方法實(shí)現(xiàn)了長(zhǎng)流的識(shí)別,利用Bloom Filter這種數(shù)據(jù)結(jié)構(gòu)在識(shí)別長(zhǎng)流的過(guò)程中可以不用維護(hù)五元組信息,降低了在維護(hù)五元組信息的過(guò)程中帶來(lái)的資源的開(kāi)銷(xiāo)。經(jīng)數(shù)據(jù)測(cè)試,本文提出的識(shí)別長(zhǎng)流的算法在識(shí)別長(zhǎng)流的同時(shí),可以還原成五元組信息,使用多哈??梢越档蜎_突,保證數(shù)據(jù)的準(zhǔn)確性。

      參考文獻(xiàn):

      [1] Veru Paxson,Jamshid Mahdavi. Scale Internet measurement[J].IEEE Communications,1998, 36(8):48-54.

      [2]彭艷兵,龔儉,劉衛(wèi)江,等. Bloom Filter哈??臻g的元素還原[J]. 電子學(xué)報(bào),2006,34(5):822-827.

      [3]龔儉,彭艷兵,楊望,等.基于Bloom Filter的大規(guī)模異常TCP連接參數(shù)再現(xiàn)方法[J].軟件學(xué)報(bào), 2006,17(3):434-444.

      猜你喜歡
      長(zhǎng)流存儲(chǔ)空間哈希
      基于多種群協(xié)同進(jìn)化算法的數(shù)據(jù)并行聚類(lèi)算法
      蘋(píng)果訂閱捆綁服務(wù)Apple One正式上線(xiàn)
      我的愛(ài)就是長(zhǎng)流的水
      用好Windows 10保留的存儲(chǔ)空間
      法治,讓赤水河碧水長(zhǎng)流
      愿歲月簡(jiǎn)單愛(ài)長(zhǎng)流
      細(xì)水長(zhǎng)流的感覺(jué)
      基于OpenCV與均值哈希算法的人臉相似識(shí)別系統(tǒng)
      基于維度分解的哈希多維快速流分類(lèi)算法
      基于同態(tài)哈希函數(shù)的云數(shù)據(jù)完整性驗(yàn)證算法
      营口市| 交口县| 三穗县| 海城市| 聊城市| 台湾省| 南投县| 阿尔山市| 平阳县| 赣榆县| 肥西县| 云霄县| 泰兴市| 海宁市| 凌海市| 丁青县| 筠连县| 郁南县| 新泰市| 尤溪县| 武义县| 仙游县| 桦南县| 莒南县| 大余县| 临城县| 苏尼特左旗| 偏关县| 精河县| 宜宾县| 无锡市| 哈密市| 宜城市| 通榆县| 三台县| 东港市| 平潭县| 诸城市| 东乡族自治县| 道真| 温宿县|