[發明專利]滑動窗口下基于GPU的網絡訪問超點連接數估算方法

有效

• 申請號: 201810618223.2
• 申請日: 2018-06-15
• 公開（公告）號: CN108809764B
• 公開（公告）日: 2021-11-02
• 發明（設計）人: 徐杰;丁偉;胡曉燕
• 申請（專利權）人: 東南大學
• 主分類號: H04L12/26
• 分類號: H04L12/26;G06F9/50;G06F9/48
• 代理公司: 南京眾聯專利代理有限公司 32206
• 代理人: 葉涓涓

1.滑動窗口下基于GPU的網絡訪問超點連接數估算方法，其特征在于，包括如下步驟：

數據結構初始化，所述數據結構包括滑動估值器矩陣和滑動候選超點列表；

掃描一個時間片里的所有數據包，利用滑動估值器矩陣記錄主機連接數，在掃描數據包時，判斷主機是否為超點，將檢測出的超點添加到滑動候選超點列表里；

在時間片結束時，根據滑動估值器矩陣計算滑動候選超點列表里的每個主機的連接數，輸出連接數大于閾值的主機及其估算值；估算完所有候選超點主機的連接數后，更新滑動估值器矩陣和滑動候選超點列表；

將窗口向前滑動一個時間片，開始掃描下一個時間片里的數據包，估算下一個滑動窗口里的超點連接數；

具體包括如下步驟：

第一步，設置參數

設置由u行v列的滑動估值器組成的滑動估值器矩陣，每個滑動估值器包含：由n個比特組成的超點指示器、由g個整數組成的滑動模糊估計器、由g’個整數組成的滑動線性估值器；設置用于保存檢測到的候選超點的滑動候選超點列表；

第二步，在GPU上初始化數據結構

在GPU的顯存上分配滑動估值器矩陣的內存空間，初始化滑動估值器矩陣，將滑動估值器矩陣里所有滑動模糊估計器的整數設置為最大值，將滑動估值器矩陣里所有滑動線性估計器的整數設置為最大值，在GPU上預留用于保存滑動候選超點列表的顯存空間；

第三步，掃描IP數據包，提取IP地址對

掃描每個時間片里的數據包，提取每個數據包的IP地址，得到每個數據包的IP地址對，IP地址對是結構為aip,bip的二元組，其中，aip是要測量的網絡里的一個主機，bip是通過邊界路由器與aip通信的主機；在服務器上先對這些IP對進行緩存，當緩沖區滿或者一個時間片里的數據包掃描完成時，將服務器上緩沖區里的IP地址對通過PCIe總線拷貝到GPU的顯存里；

第四步，啟動GPU線程，掃描IP地址對

當復制完成后，GPU啟動與IP地址對相同數量的線程來處理收到的IP地址對；

每個GPU線程讀取IP地址對緩沖區的一個IP地址aip,bip對進行處理；

滑動估值器矩陣的每一行對應一個哈希函數RHi，i∈[ 0,v-1] ；RHi(aip)將aip映射到第i行的任意一個滑動估值器，對于第i行，第RHi(aip)個滑動估值器會被更新，保存aip的連接數；

第五步，時間片結束時，估算超點連接數

在一個時間片結束時掃描完該時間片里的所有數據包后，開始進行超點連接數估算：

對滑動候選超點列表里的主機進行分組，每組1024個主機，對于每組主機，分別在GPU上進行超點連接數估算；估算方法為：

對于一組超點主機，啟動1024個線程，每個線程分別估算一個主機的連接數，每個線程估算候選主機連接數的方法如下：

設第i行所有滑動估值器的滑動線性估值器的值小于k的整數的個數為|LDR(i)|_k；

計算滑動估值器矩陣里滑動線性估值器的每個整數被設置的概率

對于主機aip，將滑動估值器矩陣每一行里與aip對應的滑動估值器的滑動線性估值器進行合并：將每一個滑動估值器的滑動線性估值器的整數按取所有相同位置的最大整數的操作進行合并得到一個新的滑動線性估值器；

掃描該合并后的滑動線性估值器，得到值小于k的整數的個數|ULE(aip)|_k；根據公式-g'* 計算aip的連接數；

滑動候選超點列表里的每個主機按上述方法被一個GPU線程處理得到它的連接數估算值；

輸出所有估算值大于等于θ的主機及其連接數估算值就完成了一個滑動窗口下的超點連接數估算，θ是超點的閾值；

第六步，更新滑動估值器矩陣和滑動候選超點列表：

完成一個滑動窗口下的超點連接數估算后對滑動估值器矩陣和滑動候選超點列表進行更新：

將滑動估值器矩陣里的每個滑動估值器的超點指示器的每個比特設置為0；

對于每個滑動估值器里的滑動模糊估值器的每個整數，如果其值小于最大值，則將其加1；

對于每個滑動估值器里的滑動線性估值器的每個整數，如果其值小于最大值，則將其加1；

掃描滑動候選超點列表里的每個主機，確定其在更新后的滑動估值器矩陣里是否仍然為候選超點，如果是，則將其加入新的滑動候選超點列表并更新對應的超點指示器的比特位；

掃描完所有的候選超點主機后，用新的滑動候選超點列表替換當前的滑動候選超點列表；

第七步，將窗口滑動一個時間片，重復從第三步開始執行

估算完一個滑動時間窗口里的超點連接數，并更新完滑動估值器矩陣和滑動候選超點列表后，將時間窗口滑動一個時間片，回到第三步，開始掃描下一個時間片里的所有數據包。