[發明專利]一種基于共享計數樹的存儲空間優化采樣方法

有效

• 申請號: 202010438372.8
• 申請日: 2020-05-22
• 公開（公告）號: CN111581489B
• 公開（公告）日: 2023-03-24
• 發明（設計）人: 楊武;玄世昌;王巍;苘大鵬;呂繼光;唐德志
• 申請（專利權）人: 哈爾濱工程大學
• 主分類號: G06F16/953
• 分類號: G06F16/953;G06F16/13;G06F16/172;G06F18/2411;G06F18/2431;H04L47/2483
• 代理公司: 暫無信息
• 代理人: 暫無信息

本發明屬于流量采樣技術領域，具體涉及一種基于共享計數樹的存儲空間優化采樣方法。本發明旨在節約采樣設備存儲空間，具體包括根據采樣判斷機制決定是否對到來的數據包進行采樣；如果決定對到來的數據包進行采樣，在哈希流跟蹤表中對該數據包所屬流節點進行檢索；若未檢索到采樣數據包所屬流節點，則為該數據包在流跟蹤表中新建流節點；當對某條流終止采樣時，將該流在流節點和共享計數樹集合中存儲的特征值還原并導入到有序流特征記錄緩沖區中；待緩沖區已滿，將采樣流特征記錄寫入到文件中。

技術領域

本發明屬于流量采樣技術領域，具體涉及一種基于共享計數樹的存儲空間優化采樣方法。

背景技術

近些年，互聯網中應用的種類和數量有了顯著的發展。為應對應用變化對網絡帶來的影響，網絡管理者需要對流量應用特征進行測量，在測量的過程中需要對流量進行應用分類。為支持應用分類，采樣流量應保留足夠的應用特征。現代應用程序的一個具體會話通常是由多條流組成，會話中每一條流的源IP相同但目的IP可能互異。若在某一應用程序會話中采到更多的流，則會為采樣流量保留更多的應用特征，進而有助于機器學習算法準確地對采樣流量進行應用識別。RelSamp只會對一定范圍內的源IP所對應的流進行采樣，而且在有效采樣比恒定的情況下，它可以通過提高流采樣概率，降低包采樣概率來提高在應用程序會話中所采到的流的數量，更多地保留采樣流量的應用特征。但是，針對流的任意一個統計特征，例如，流大小，RelSamp需要為每一條流分配一個計數器來記錄其大小。為每個計數器分配的空間都要一致且要保證計數器的計數范圍能夠涵蓋最大流的計數值。網絡流量分布具有重尾分布的特點，即占小比例的大流占據了網絡流量中的大比例。有研究表明，按照流大小對流進行排序，排在前15％的流占據了流量總體的95％。為每條流分配空間大小一致的計數器來記錄流大小，必然會造成流量采樣設備存儲空間的大量浪費。為每一條流分配空間大小一致的計數器來記錄其他統計特征(例如，采樣過程中，該流FIN，SYN以及ACK包到來的個數)也同樣會對流量采樣設備的存儲空間造成浪費。尤其是當RelSamp部署在網絡流并發量巨大的高速網絡環境中時，會對流量采樣設備造成巨大的存儲壓力。

發明內容

本發明的目的在于提供節約采樣設備存儲空間的一種基于共享計數樹的存儲空間優化采樣方法。

本發明的目的通過如下技術方案來實現：包括以下步驟：

步驟1：根據預先配置的有限采樣比p_e、源IP采樣概率p_h以及目標流采樣概率確定輸出包采樣概率p_p和當前流采樣概率p_f；

步驟2：從數據包緩沖隊列提取數據包，并為該數據包分配兩個取值范圍在[0，1)的隨機數r_f和r_p；

步驟3：獲取數據包的源IP并計算該源IP的哈希值；

步驟4：將源IP的哈希值與源IP選擇概率p_h相乘得到目標值；

步驟5：若目標值落在預先配置好的范圍內，則執行步驟6；否則拋棄該數據包；

步驟6：搜索數據包所屬流節點；

若沒有查找到該數據包對應的流節點且r_f≤p_f，則對該數據包進行采樣并為該數據包創建一個流節點，新建流特征存儲單元，并更新該流的流特征存儲單元；

若查找到該數據包所屬流節點且r_p≤p_p，則對該數據包進行采樣并更新該流的流特征存儲單元；

若沒有查找到該數據包對應的流節點且r_f＞p_f，或查找到該數據包所屬流節點且r_p＞p_p時拋棄該數據包；