《基於資源復用的OPENFLOW流表存儲最佳化方法》是武漢烽火網路有限責任公司於2013年7月22日申請的專利，該專利的公布號為CN103368851A，公布日為2013年10月23日，發明人是戴錦友、余少華、汪學舜、朱國勝。
《基於資源復用的OPENFLOW流表存儲最佳化方法》涉及軟體定義網路中Openflow流表，包括步驟：S1.在Openflow流表的表項中添加掩碼標識欄位和範圍標識欄位，從掩碼標識索引至一個掩碼錶，從範圍標識索引至一個範圍表，流表的表項中僅存儲能檢索到計數器、操作/指令的索引；S2.轉發設備收到增加表項的命令後，遍歷當前流表中已存在表項，分析待增表項與每個已存表項的相關性，將該已存表項與關聯度最大的待增表項合併後寫入流表，刪除已存表項；若相關度為0，該待增表項作為新的表項在流表中創建。該發明最佳化了流表表項的信息存儲，能夠高效利用2013年7月之前的硬體資源，達到在同樣硬體條件下存儲更多的流表表項的目的。
2017年12月11日，《基於資源復用的OPENFLOW流表存儲最佳化方法》獲得第十九屆中國專利優秀獎。
（概述圖為《基於資源復用的OPENFLOW流表存儲最佳化方法》摘要附圖）
基本介紹
- 中文名：基於資源復用的OPENFLOW流表存儲最佳化方法
- 申請人：武漢烽火網路有限責任公司
- 申請日：2013年7月22日
- 申請號：2013103081858
- 公布號：CN103368851A
- 公布日：2013年10月23日
- 發明人：戴錦友、余少華、汪學舜、朱國勝
- 地址：湖北省武漢市東湖開發區關東科技園東信路5號
- 分類號：H04L12/741(2013.01)I、H04L29/06(2006.01)I、G06F17/30(2006.01)I
- 代理機構：北京捷誠信通專利事務所
- 代理人：魏殿紳、龐炳良
- 類別：發明專利
專利背景,發明內容,專利目的,技術方案,有益效果,附圖說明,權利要求,實施方式,榮譽表彰,
專利背景
網際網路作為人類歷史上最重要的發明之一，2013年前已成為世界上覆蓋範圍最廣、規模最大、擁有信息和知識海洋的全球基礎設定。同時，網際網路也已成為人們無法離開的強有力的信息獲取工具，在人們的工作和生活中扮演著極其重要的角色，而且，網際網路對人類工作和生活的影響以及人們對網際網路的依賴日漸加深。
但是，網際網路在發展過程中也已發現存在很多問題，面臨各種挑戰。其體系架構複雜度高、可擴展性差、對硬體設備依賴性強、虛擬化能力弱等等問題，與套用對網路的高效、智慧型、開放、靈活、低成本的矛盾日漸尖銳，難以調和。
SDN（Software Defined Networking，軟體定義網路）為網際網路存在的上述問題帶來了解決契機。它正好是針對2013年7月之前的包括網際網路的各種網路體系架構上的不足而生，基於軟體定義的網路能夠滿足未來套用對網路的各種需求。
軟體定義網路最初起源於史丹福大學提出的Openflow協定。事實上，當前SDN網路的主要代表仍然是以Openflow協定為核心。標準化組織ONF（Open Network Foundation，開放網路基金會）正在進行Openflow的標準化工作，Openflow標準從1.0版本發展到1.3.1版本，而Openflow1.3.1版本是2013年前已經發布的最新版本，更高Openflow標準版本正在研製中。如圖1所示，為Openflow標準1.0中定義的流表表項結構，基本的流表表項至少包含HeaderFields（分組頭欄位）、Counters（計數器）和Actions（操作）三部分，HeaderFields（分組頭欄位）包含一組用於標識流的欄位，Counters包含一組計數器，Actions包含一個或多個操作。如圖2所示，為Openflow標準1.1到1.3.1版本中定義的流表表項結構，基本的流表表項至少包含MatchFields（匹配欄位）、Counters（計數器）和Instructions（指令）三部分，MatchFields（匹配欄位）包含一組用於標識流的欄位，Counters包含一組計數器，Instructions包含一個或多個操作。
由圖1和圖2可知，Openflow雖然是當前SDN網路的主流技術之一，但它也存在一些問題，面臨強大挑戰。首先，標準中關於轉發流表的設計，由於需要的流表存儲空間巨大，在具體硬體設備上實現困難很大。Openflow標準在演進過程中，HeaderFields/MatchFields中的欄位是逐漸增加的，這使得流表的規模越來越龐大，需要的存儲量也越來越大。僅僅按Openflowv1.1標準定義的匹配欄位就達356位，因此理論上其需要的存儲空間將會是天文數字。Counters和Actions需要的存儲空間也很大。而且，由於網路中很多流的轉發行為相同，如果每個流表項都包含Counters和Actions的全部內容，存儲空間浪費很大。
另外，流表的存儲常常用價格昂貴的TCAM（Ternary Tontent Addressable Memory，三重內容定址存儲器）來實現，因此，精細高效的設計更為必要。流表中條目的欄位也在不斷增加，隨著網路規模的擴大，流表的規模將會成指數增長，既難以在硬體上實現，同時，實現的硬體成本也很高。
發明內容
專利目的
針對2013年7月之前的技術中存在的缺陷，該發明的目的在於提供一種基於資源復用的Openflow流表存儲最佳化方法，高效利用已有硬體資源實現，以達到在同樣硬體條件下存儲更多的流表表項的目的。
技術方案
《基於資源復用的OPENFLOW流表存儲最佳化方法》包括步驟：S1.在Openflow流表的表項中添加掩碼標識欄位和範圍標識欄位，從掩碼標識索引至一個掩碼錶，從範圍標識索引至一個範圍表，掩碼錶的表項表示流表中每個分組頭欄位/匹配欄位的掩碼，範圍表的表項表示流表中每個分組頭欄位/匹配欄位的連續範圍，且流表的表項中不直接存儲計數器和操作/指令信息，僅存儲能檢索到計數器、操作/指令的索引；S2.轉發設備收到增加表項的命令後，遍歷當前流表中已存在的表項，分析待增表項與每個已存表項的相關性，找到與待增表項關聯度最大的已存表項，將該已存表項與待增表項合併後寫入流表後，刪除該已存表項；若已存表項與待增表項相關度為0，該待增表項作為新表項在流表中創建。
在上述技術方案的基礎上，所述掩碼標識或範圍標識設定一個特定值，用於表示不需要掩碼值或範圍值的情形。在上述技術方案的基礎上，所述掩碼錶的表項長度、範圍表的表項長度，均與Openflow流表中匹配欄位/分組頭欄位的表項長度相同。在上述技術方案的基礎上，所述待增表項與已存表項的關聯度，根據二者的轉發行為是否一致來判斷，不考慮計數器的影響，若轉發行為不一致，則二者的關聯度為0；若轉發行為一致，則進一步計算關聯度。
在上述技術方案的基礎上，若待增表項與已存表項能用一個表項加掩碼、或一個表項加範圍表示，或者一個表項加掩碼和範圍三者共同表示，則這個公共表項使用的範圍或掩碼的比特長度，即為待增表項與該已存表項的關聯度。在上述技術方案的基礎上，所述合併時，若合併涉及的已存表項對應的數據流在活躍中，則該數據流的轉發行為不受表項合併的影響。
在上述技術方案的基礎上，所述待增表項與已存表項合併後進入流表，在生效前保留參與合併的已存表項。在上述技術方案的基礎上，所述待增表項與已存表項合併後的表項寫入流表時，其優先權比流表中已存在的表項低；若優先權與流表中已存在的表項相同，則其查找順序比已存在的表項低。
有益效果
《基於資源復用的OPENFLOW流表存儲最佳化方法》的有益效果在於：本方法基於Openflow定義的流表結構進行擴展和最佳化，最佳化了表項的信息存儲，並且相互關聯的表項可共用一個硬體表項條目存儲，能夠達到在同等硬體條件下存儲更多流表表項的目的，從而提高轉發設備性能和降低硬體成本的目標，使得昂貴的硬體資源得到充分利用。
附圖說明
圖1為背景技術中Openflow標準1.0定義的流表示意圖；
圖2為背景技術中Openflow標準1.1到1.3.1定義的流表示意圖；
圖3為該發明實施例所定義的流表示意圖；
圖4為該發明實施例步驟S2的具體流程圖；
圖5為該發明實施例流表的表項關聯度示例圖；
圖6為該發明實施例表項合併後寫入流表的流程圖。
權利要求
1.《基於資源復用的OPENFLOW流表存儲最佳化方法》其特徵在於，包括步驟：
S1.在Openflow流表的表項中添加掩碼標識欄位和範圍標識欄位，從掩碼標識索引至一個掩碼錶，從範圍標識索引至一個範圍表，掩碼錶的表項表示流表中每個分組頭欄位/匹配欄位的掩碼，範圍表的表項表示流表中每個分組頭欄位/匹配欄位的連續範圍，且流表的表項中不直接存儲計數器、操作/指令信息，僅存儲能檢索到計數器、操作/指令的索引；
S2.轉發設備收到增加表項的命令後，遍歷當前流表中已存在的表項，分析待增表項與每個已存表項的相關性，找到與待增表項關聯度最大的已存表項，將該已存表項與待增表項合併後寫入流表後，刪除該已存表項；若已存表項與待增表項相關度為0，該待增表項作為新表項在流表中創建。
2.如權利要求1所述的基於資源復用的Openflow流表存儲最佳化方法，其特徵在於：所述掩碼標識或範圍標識設定一個特定值，用於表示不需要掩碼值或範圍值的情形。
3.如權利要求1所述的基於資源復用的Openflow流表存儲最佳化方法，其特徵在於：所述掩碼錶的表項長度、範圍表的表項長度，均與Openflow流表中匹配欄位/分組頭欄位的表項長度相同。
4.如權利要求1所述的基於資源復用的Openflow流表存儲最佳化方法，其特徵在於：所述待增表項與已存表項的關聯度，根據二者的轉發行為是否一致來判斷，不考慮計數器的影響，若轉發行為不一致，則二者的關聯度為0；若轉發行為一致，則進一步計算關聯度。
5.如權利要求4所述的基於資源復用的Openflow流表存儲最佳化方法，其特徵在於：若待增表項與已存表項能用一個表項加掩碼、或一個表項加範圍表示，或者一個表項加掩碼和範圍三者共同表示，則這個公共表項使用的範圍或掩碼的比特長度，即為待增表項與該已存表項的關聯度。
6.如權利要求1所述的基於資源復用的Openflow流表存儲最佳化方法，其特徵在於：所述合併時，若合併涉及的已存表項對應的數據流在活躍中，則該數據流的轉發行為不受表項合併的影響。
7.如權利要求1所述的基於資源復用的Openflow流表存儲最佳化方法，其特徵在於：所述待增表項與已存表項合併後進入流表，在生效前保留參與合併的已存表項。
8.如權利要求7所述的基於資源復用的Openflow流表存儲最佳化方法，其特徵在於：所述待增表項與已存表項合併後的表項寫入流表時，其優先權比流表中已存在的表項低；若優先權與流表中已存在的表項相同，則其查找順序比已存在的表項低。
實施方式
《基於資源復用的OPENFLOW流表存儲最佳化方法》套用涉及2013年7月之前的硬體設備條件下的控制器和轉發設備，還包括關聯度暫存器和最大關聯度表項標識暫存器，二者是為了該方法實施而使用的兩個暫存器，該發明的具體步驟為：
S1.在Openflow流表基礎上設計流表，如圖3所示，在Openflow流表的表項中增加了MaskId（掩碼標識）欄位和RangeId（範圍標識）欄位，為所述MaskId或RangeId設定一個特定值（如0xffffffff），用於表示不需要掩碼值或範圍值的情形，這樣極大的保證表項復用的效率。從MaskId可索引至Mask（掩碼）表，從RangeId可索引至Range（範圍）表，Mask表的表項長度和Range表的表項長度，均與Openflow流表中HeaderFields/MatchFields的長度相同，Mask表的表項表示流表中每個HeaderFields/MatchFields的掩碼，Range表的表項表示流表中每個HeaderFields/MatchFields的連續範圍。並且Counters和Actions/Instructions兩部分內容從流表表項中移出，流表的表項中不直接存儲計數器、操作/指令信息，僅存儲能檢索到Counters、Actions/Instructions兩部分的索引，計數器、操作/指令在其它表中存儲。
S2.轉發設備收到增加表項的命令後，遍歷當前流表中已存在的表項，分析待增表項與每個已存表項的相關性，找到與待增表項關聯度最大的已存表項，將該已存表項與待增表項合併後寫入流表後，刪除該已存表項；若兩者相關度為0，該待增表項作為新表項在流表中創建。如圖4所示，該部分的詳細步驟如下：
S201.控制器得到添加流表的表項需求時，向轉發設備傳送添加表項的命令；轉發設備從控制器得到待增表項。
S202.轉發設備做好添加待增表項的準備，設定相應的工作環境，如清空關聯度暫存器和最大關聯度表項標識暫存器等。
S203.判斷已有流表中是否有未分析的已存表項，若是，進入S204；若否，進入S207。
S204.計算第一個未分析的已存表項與待增表項的關聯度。根據已存表項與待增表項的轉發行為是否一致來判斷關聯度，大部分套用場景判斷轉發行為一般可以不考慮計數器的影響，若轉發行為不一致，則二者的關聯度為0；若轉發行為一致，則進一步計算關聯度。如果待增表項與已存表項能用一個表項加掩碼、或一個表項加範圍表示，或者一個表項加掩碼和範圍三者共同表示，則這個公共表項使用的範圍或掩碼的比特長度，即為待增表項與該已存表項的關聯度。
如圖5所示，為該發明流表的表項關聯度示例圖，圖中省略了源IP和目的IP以外的其它欄位，假定待增表項與給出的幾個已存表項（已存表項1……已存表項4）的轉發行為相同。圖5中，已存表項1與待增表項無法用一個公共表項表示，因此兩者關聯度為0；待增表項的源IP最後一位與已存表項2可藉助於範圍用一個公共表項表示，並且該欄位範圍值可用1比特表示，因此兩者關聯度為1；依次類推，可得出已存表項3與待增表項的關聯度為9，已存表項4與待增表項的關聯度為2。
S205.判斷已存表項與待增表項的關聯度，是否大於關聯暫存器的值，即是否為2013年前最大的關聯度，若是，進入S206；若否，轉入S203。
S206.更新關聯暫存器和最大關聯度表項標識暫存器。
S207.判斷當前關聯度暫存器是否為非0，若是，進入S208；若否，進入S209。
S208.待增表項合併到具有最大關聯度的表項後寫入流表，結束。由於表項合併涉及到流表中已存表項，而已存表項對應的數據流很可能在活躍中，若合併涉及的已存表項對應的數據流在活躍中，則該數據流的轉發行為不受表項合併的影響，此為表項合併的前提條件。所述待增表項與已存表項合併後進入流表，在生效前保留參與合併的已存表項。待增表項與已存表項合併後的表項寫入流表時，為了確保已存表項依然有效，合併後的表項優先權比流表中已存表項低，或者優先權與流表中已存表項相同，則其查找順序比已存表項低。在合併後的表項寫入流表中後，刪除該已存表項，並修改合併後的表項與原流表中已存表項的優先權相同。
S209.待增表項作為流表中新表項創建，結束。
如圖6所示，為該發明實施例表項合併後寫入流表的流程圖，其步驟為：
A1.轉發設備獲取合併後表項的內容。
A2.轉發設備獲取已存表項的優先權。
A3.判斷該已存表項優先權是否為最低，若是，進入A4；若否，進入A7。
A4.找到一個優先權低於該已存表項優先權的空表項。
A5.將合併後表項的內容寫入該空表項。
A6.清空該已存表項，並修改該空表項的優先權為該已存表項優先權，結束。
A7.找到一個優先權可以設定為該已存表項優先權，但是查找順序在該已存表項查找順序之後的空表項。
A8.將合併後表項的內容寫入A7中的該空表項，其優先權為該已存表項優先權。
A9.清空該已存表項，結束。
該發明基於資源復用的Openflow流表存儲最佳化方法所涉及的轉發設備，應同時支持傳統的二、三層轉發模式和基於SDN的轉發模式，兩種模式的切換通過配置的改變來實現，該轉發設備具有多個千兆和萬兆乙太網接口。
榮譽表彰
2017年12月11日，《基於資源復用的OPENFLOW流表存儲最佳化方法》獲得第十九屆中國專利優秀獎。
