[發(fā)明專利]基于流集合隨機(jī)抽樣的報(bào)文測(cè)量方法

無效

• 申請(qǐng)?zhí)枺?/td>: 200710190188.0
• 申請(qǐng)日: 2007-11-20
• 公開（公告）號(hào): CN101163058A
• 公開（公告）日: 2008-04-16
• 發(fā)明（設(shè)計(jì)）人: 程光;龔儉;強(qiáng)士卿;丁偉;吳樺
• 申請(qǐng)（專利權(quán)）人: 東南大學(xué)
• 主分類號(hào): H04L12/26
• 分類號(hào): H04L12/26;H04L12/56
• 代理公司: 南京經(jīng)緯專利商標(biāo)代理有限公司
• 代理人: 奚幼堅(jiān)

1.一種基于流集合隨機(jī)抽樣的報(bào)文測(cè)量方法，其特征是將測(cè)量時(shí)間區(qū)間分為若干子區(qū)間，子區(qū)間的數(shù)量為抽樣比率的倒數(shù)，為每個(gè)子區(qū)間分配一個(gè)不同的匹配比特串，在每個(gè)子區(qū)間中采用隨機(jī)抽樣網(wǎng)絡(luò)流的測(cè)量方法抽樣報(bào)文，抽樣過程中使用該子區(qū)間被分配的匹配比特串匹配網(wǎng)絡(luò)流標(biāo)識(shí)的哈希值，該過程中采用一個(gè)哈希函數(shù)處理所有的報(bào)文流標(biāo)識(shí)以生成哈希值比特串，這個(gè)哈希函數(shù)的輸入為報(bào)文流標(biāo)識(shí)，輸出為和匹配比特串長(zhǎng)度相同的哈希值比特串，將該子區(qū)間被分配的匹配比特串和輸出的哈希值比特串之間進(jìn)行比較，如果兩個(gè)比特串相同，則該報(bào)文被抽樣，否則這個(gè)報(bào)文將被丟棄。

2.根據(jù)權(quán)利要求1所述基于流集合隨機(jī)抽樣的報(bào)文測(cè)量方法，其特征是所述將測(cè)量時(shí)間區(qū)間分為若干子區(qū)間的具體方法如下：假設(shè)測(cè)量匹配比特串的長(zhǎng)度為n比特，n是大于0的正整數(shù)，這個(gè)n個(gè)比特串的取值空間大小為2ⁿ，因此采用n比特匹配比特串的隨機(jī)抽樣網(wǎng)絡(luò)流的測(cè)量方法的抽樣概率為1/2ⁿ，測(cè)量器事先將測(cè)量的時(shí)間區(qū)間T分為抽樣比率的倒數(shù)等份，即2ⁿ等份，每個(gè)子時(shí)間區(qū)間按照先后順序進(jìn)行編號(hào)，第一個(gè)子時(shí)間區(qū)間編號(hào)為0，最后一個(gè)子時(shí)間區(qū)間編號(hào)為2ⁿ-1。

3.根據(jù)權(quán)利要求1或2所述基于流集合隨機(jī)抽樣的報(bào)文測(cè)量方法，其特征是所述為每個(gè)子區(qū)間分配一個(gè)不同的匹配比特串，具體方法如下：設(shè)置一個(gè)大小為2ⁿ的數(shù)組t，數(shù)組t記錄每個(gè)子時(shí)間區(qū)間中被分配的n比特長(zhǎng)度的匹配比特串，數(shù)組t中的每個(gè)元素t(i)是一個(gè)n比特的比特串，i是子時(shí)間區(qū)間的編號(hào)，i大于等于0且小于等于2ⁿ-1，將0到2ⁿ-1之間的2ⁿ個(gè)不同的數(shù)隨機(jī)分配到這個(gè)大小為2ⁿ的數(shù)組t的每個(gè)元素中，每個(gè)子時(shí)間區(qū)間中被分配的數(shù)為該子時(shí)間區(qū)間中被分配的n比特匹配比特串。

4.根據(jù)權(quán)利要求3所述基于流集合隨機(jī)抽樣的報(bào)文測(cè)量方法，其特征是測(cè)量方法步驟具體如下：

第一步：設(shè)置初始參數(shù)

設(shè)置抽樣測(cè)量時(shí)間區(qū)間長(zhǎng)度為T，將測(cè)量時(shí)間區(qū)間T分為2ⁿ等份，每個(gè)子區(qū)間時(shí)間長(zhǎng)度為T/2ⁿ，設(shè)開始的測(cè)量子時(shí)間區(qū)間序號(hào)itime等于0；

設(shè)置一個(gè)大小為2ⁿ的數(shù)組t，數(shù)組t中的每個(gè)元素t(i)是一個(gè)n比特的數(shù)，i大于等于0且小于等于2ⁿ-1，將0到2ⁿ-1之間的2ⁿ個(gè)數(shù)隨機(jī)分配到大小為2ⁿ的數(shù)組t的每個(gè)元素中；

選擇一個(gè)哈希函數(shù)hash，哈希函數(shù)的輸入流標(biāo)識(shí)ID，哈希函數(shù)生成的哈希值value為n個(gè)比特長(zhǎng)度，其取值范圍為大于等于0且小于2ⁿ；

設(shè)置報(bào)文內(nèi)存空間大小S；

設(shè)當(dāng)前測(cè)量時(shí)間區(qū)間開始時(shí)間為current，結(jié)束時(shí)間end＝current+T；

第二步：計(jì)算當(dāng)前測(cè)量子時(shí)間區(qū)間結(jié)束時(shí)間

當(dāng)前測(cè)量子時(shí)間區(qū)間結(jié)束時(shí)間time為測(cè)量子時(shí)間區(qū)間開始時(shí)間加上測(cè)量子時(shí)間區(qū)間大小T/2ⁿ，time＝current+itime*T/2ⁿ+T/2ⁿ，其中time為當(dāng)前測(cè)量子時(shí)間區(qū)間結(jié)束時(shí)間，current為當(dāng)前測(cè)量時(shí)間區(qū)間開始時(shí)間，itime為當(dāng)前子時(shí)間區(qū)間序號(hào)，T為測(cè)量時(shí)間區(qū)間長(zhǎng)度，n為大于等于0的正整數(shù)，T/2ⁿ為子區(qū)間的時(shí)間長(zhǎng)度，itime*T/2ⁿ為當(dāng)前子時(shí)間區(qū)間的開始時(shí)間，進(jìn)入第三步；

第三步：判斷當(dāng)前子測(cè)量時(shí)間區(qū)間結(jié)束

如果當(dāng)前測(cè)量器時(shí)間大于等于當(dāng)前子測(cè)量時(shí)間區(qū)間結(jié)束時(shí)間time，輸出報(bào)文內(nèi)存空間M中的數(shù)據(jù)到硬盤中進(jìn)行存儲(chǔ)，清空?qǐng)?bào)文內(nèi)存空間M中的報(bào)文記錄，設(shè)置目前報(bào)文內(nèi)存空間M中的報(bào)文記錄個(gè)數(shù)m等于0，進(jìn)入第七步；否則如果當(dāng)前測(cè)量器時(shí)間小于當(dāng)前子測(cè)量時(shí)間區(qū)間結(jié)束時(shí)間time，進(jìn)入第四步；

第四步：抽樣到達(dá)測(cè)量器的報(bào)文

等待報(bào)文到達(dá)測(cè)量器，如果一個(gè)報(bào)文到達(dá)測(cè)量器，提取其流標(biāo)識(shí)ID，使用哈希函數(shù)hash計(jì)算其哈希值value，value＝hash(ID)，value是一個(gè)n比特的數(shù)；如果value等于當(dāng)前子時(shí)間區(qū)間對(duì)應(yīng)的事先設(shè)定的n比特?cái)?shù)t(itime)，(其中itime為當(dāng)前時(shí)間序號(hào)，t是大小為2ⁿ的數(shù)組)，則進(jìn)入第五步，否則回到第三步；

第五步：處理被抽樣的報(bào)文

將被抽樣的報(bào)文信息記錄在報(bào)文內(nèi)存空間M中，并將報(bào)文內(nèi)存空間中的報(bào)文記錄數(shù)量m增加1，即m＝m+1；如果報(bào)文內(nèi)存空間中報(bào)文記錄數(shù)量m小于S，則回到第三步；否則進(jìn)入第六步；

第六步：報(bào)文內(nèi)存空間記錄輸出

將報(bào)文內(nèi)存空間M中的報(bào)文記錄輸出到硬盤中，同時(shí)將報(bào)文內(nèi)存空間中的記錄清空，并設(shè)置報(bào)文內(nèi)存空間報(bào)文記錄數(shù)量m等于0，回到第三步。

第七步：測(cè)量結(jié)束時(shí)間判斷

如果測(cè)量子時(shí)間區(qū)間序號(hào)itime等于測(cè)量子時(shí)間總數(shù)2ⁿ-1，停止測(cè)量；否則設(shè)置新的當(dāng)前子時(shí)間區(qū)間序號(hào)itime＝itime+1，進(jìn)到第二步。