[發明專利]基于布魯姆過濾器的SDN流規則沖突檢測方法及系統

有效

• 申請號: 201810258532.3
• 申請日: 2018-03-27
• 公開（公告）號: CN108566388B
• 公開（公告）日: 2020-10-16
• 發明（設計）人: 閆崢;姚震;靖旭陽
• 申請（專利權）人: 西安電子科技大學
• 主分類號: H04L29/06
• 分類號: H04L29/06;H04L12/26;H04L12/851;H04L9/06
• 代理公司: 西安長和專利代理有限公司 61227
• 代理人: 黃偉洪;何畏

1.一種基于布魯姆過濾器的SDN流規則沖突檢測方法，其特征在于，所述基于布魯姆過濾器的SDN流規則沖突檢測方法包括：

首先對控制器中的流規則及新插入控制器的流規則進行流規則擴展、序號編排、匹配域模塊哈希預處理，預處理后對流規則的編碼進行多重布魯姆過濾器篩選，選擇出出現沖突的流規則集合，對出現沖突的流規則集合進行二次篩選，選擇出匹配域相同的流規則集合；

最后通過對匹配域相同的集合中流規則必備動作的比較，最終檢測出有沖突的流規則。

2.如權利要求1所述的基于布魯姆過濾器的SDN流規則沖突檢測方法，其特征在于，所述基于布魯姆過濾器的SDN流規則沖突檢測方法具體包括：

步驟一，對控制器流表中的所有流規則進行流規則擴展、序號編排、匹配域模塊哈希的數據預處理；

步驟二，將步驟一輸出的所有流規則匹配域哈希值放入多個并聯的布魯姆過濾器中進行過濾，并將這些流規則的編號分別存入各級布魯姆過濾器中對應的存儲位置上；

步驟三，對新插入的流規則按步驟一和步驟二進行操作后提取出每條新插入流規則所在各級布魯姆過濾器存儲位置中的序號集，進一步對這些序號集取交集選擇出出現沖突的流規則編號集合；

步驟四，對步驟三輸出的每個出現沖突的流規則編號集進行二次篩選，比較每個序號集中對應流規則的匹配域，篩選出匹配域相同的流規則集合；

步驟五，對步驟四輸出的所有匹配域相同的流規則集合進行最終判斷，對比每個集合中流規則的動作域；必備動作相同，則判定這個集合的流規則無沖突，反之，則判定這個集合的流規則有沖突，最后輸出所有檢測到的有沖突流規則集合。

3.如權利要求2所述的基于布魯姆過濾器的SDN流規則沖突檢測方法，其特征在于，

所述步驟一對控制器中所有流規則進行數據預處理，包括：

1)將控制器中的流規則的動作域展開，擴充成包含更改前和更改后匹配域的多條流規則；

2)對擴充后的流規則進行排序編號，從1開始順序編號直至為控制器中所有的流規則添加序號1～N；

3)選取擴充后流規則匹配域中的關鍵位，將第一條流規則關鍵位的數據按固定比特長度劃分為n塊x₁～x_n后用不同的哈希函數h₁(x)～h_n(x)計算出x₁～x_n的哈希值h₁(x₁)～h_n(x_n)；最后將這些哈希值連接起來得到第一條流規則匹配域的整體哈希值m₁，進行循環直至得到所有流規則的匹配域整體哈希值m₁～m_N；

所述步驟二對進行過數據預處理的控制器中的流規則進行多級布魯姆過濾器過濾，具體包括：將進行過數據預處理的流規則輸入多級布魯姆過濾器中，按照各級布魯姆過濾器不同的模哈希算法h′₁(x)～h′_n(x)計算出第一條流規則在各級布魯姆過濾器中的存儲位置h′₁(m₁)～h′_n(m₁)，并將該流規則的編號1存入其對應的存儲位置中，如此循環直至控制器中所有的流規則都存入對應的各級布魯姆過濾器的存儲位置中；

步驟三篩選出與新插入流規則有沖突的流規則集合S′，具體包括：

a)將新插入的流規則擴展為M條，并從N+1開始順序編號至N+M，對擴展后的每條流規則的匹配域進行分塊哈希并得到分塊匹配域的整體哈希值；

b)對進行過數據預處理的每條新插入流規則按步驟二操作，直至所有的新插入流規則的編號都存入對應的各級布魯姆過濾器的存儲位置中；

c)從第一條新插入的流規則開始，提取出該流規則所在各級布魯姆過濾器存儲位置上的流規則編號集S₁～S_N′，其中，N′為多級布魯姆過濾器的個數，并對這些集合取交集S₁∩S₂∩...∩S_N′，得到與第一條流規則有沖突的流規則集合S′，進行重復直至得到所有與新插入流規則有沖突的流規則集合。