基于時序與集合的SDN流表更新策略

劉振鵬，李明，王鑫鵬，任少松，李小菲

(1. 河北大學 電子信息工程學院，河北 保定 071002；2.河北大學 信息技術中心，河北 保定 071002)

軟件定義網絡(SDN)中流表更新一致性問題是一個重要的問題[1-3]，在SDN主流的南向接口OpenFlow協議[4]中由于控制器與各交換機間存在時延，交換機更新沒有順序性，可能導致數據包同時按照新舊規則進行處理，可能導致數據包的丟失，甚至造成網絡擁塞.

針對此問題，研究人員提出許多方案，文獻[5]提出基于中間流表的流表更新一致性方案，該方案基于新舊流表提出新的中間流表.中間流表將所有數據包發送至控制器，然后在交換機中寫入中間流表.等待一個端到端時延，然后在交換機中寫入新流表，最后將上傳數據包發送回網絡中.該方案引入中間流表，新流表更新過程中，數據包發送至控制器，更新完成后發回網絡.文獻[6]提出基于額外標簽的流表更新一致性方案，該方案以額外的數據標簽(VLAN)來將新舊規則分類，舊流表的VLAN=0，新流表的VLAN=1，設置數據包的包頭信息為VLAN=0，新規則寫入交換機后更新數據包包頭信息(由0更新為1)，更新完成后，所有數據包按照新規則處理，舊規則刪除即完成更新.文獻[7]提出了基于分類的流表更新一致性策略，該策略利用軟件定義網絡集中控制特性，首先對新舊流表和交換機進行分類，將入口交換機的數據包上傳至控制器，等待一個端到端時延后更新新路徑交換機上的流表，完成后更新入口交換機的流表，新路徑完成后將舊路徑交換機流表刪除，最后將之前向控制器上傳的數據包發回網絡中.由于將數據包上傳后，完成所有交換機流表更新后下發數據包，所以數據包在任意時刻只按一種流表進行處理.文獻[8]提出了基于分類和時序的SDN流表更新一致性方案，該方案首先在新路徑交換機上安裝新流表，更新入口交換機后數據包即按新流表處理，一個端到端時延后舊路徑的舊流表被刪除，更新過程即完成.

交換機流表空間占用也是一個易被忽視的問題[9-10]，交換機流表的空間是有限的，可造成流表空間溢出[11-12]等嚴重問題.為此提出基于時序與集合的流表更新一致性方案，在保證流表更新過程中的控制負載的情況下，減小交換機空間負載，降低交換機流表空間溢出問題發生的概率.

1 基于時序與集合的流表更新策略

1.1 方案設計

假設所有流表規則更新涉及到的交換機集合為C，在流表更新中可以就交換機的流表更新時間將交換機進行分類，所用符號描述如表1.

表1 符號及其描述

流表的更新過程是控制器對交換機轉發規則的修改，首先要保證的是數據包的不丟失，以及保證交換機對數據流的轉發規則唯一性，方案步驟如下.

第1階段：準備階段，控制器在這個階段分析新舊轉發規則，準確定義交換機集合C，以及B、N、V.

第4階段：在數據流上傳至控制器開始，延遲時長tmax(tmax為網絡內最長端到端時延)，以保證在上傳開始前已轉發的數據流最終到達，防止丟包.然后開始更新新舊路徑共用交換機集合V中的對應流表和安裝入口交換機流表.

在該方法中，可以在保證控制負載的前提下，減小交換機負載，降低交換機流表空間溢出等問題的出現.

1.2 算法描述

輸入: G(V,L) //數據中心網絡拓撲 B={s01,s02,…,s0a} //新路徑交換機集合N N={s11,s12,…,s1b} //舊路徑交換機集合B R0i //舊路徑交換機對應流表輸出: R1j //新路徑交換機流表 1)V=B∩N //定義新舊路徑共用交換機集合為V2)G=(N-V) //定義G為V對N的補集3)for(s1j in G) //判斷新路徑交換機是否為集合G的元素4)update R1j //更新集合G中的交換機流表5)delete R00 //刪除入口交換機流表,這里有R00=R10,6)等待最長端到端時延tmax7)n=08)while n≤len(V)9)v=V[n]10)update R1j //更新v對應的交換機的新流表11)n+=112)endwhile //更新共用交換機流表13)update R10 //更新入口交換機新流表14)Delivery packet // 下發數據包 15)F=(B-V) //F為V對B的補集16)for (s0i in F) //判斷交換機為舊路徑剩余交換機17) delete R0i //刪除交換機舊流表18) return R1j

2 一致性證明

方案保證流表更新規則的一致性，在證明中借鑒相關研究的思路，對流表更新的一致性證明.

F(x)=F0(x),

(1)

第2階段:保持新舊路徑共用交換機流表不變，開始時刻為t0，t0時刻開始更新除新舊路徑共用交換機V的新路徑交換機N(即集合N對集合V的補集)，此階段數據包處理規則不變，此時的處理規則不變，即為式(1)，仍按舊規則處理.

(2)

F(x)=c，

(3)

更新完成時間為t3，此階段完成后新路徑更新完畢.

(4)

F(x)=F1(x).

(5)

以上過程中對應數據包的狀態分為2種：上傳至控制器和轉發.在轉發過程中，其新舊規則并未同時轉發數據包，在邏輯上保證了流表更新的一致性.

3 仿真實驗

目前關于流表更新一致性問題提出了很多的方案，方案自身的復雜程度以復雜度表示，復雜度表示方案實現的難易程度.更新時間是完成流表更新的時間，其較為直觀地展現方案的可用性.控制負載是流表更新過程中對控制器產生的負載，控制負載差會直接影響控制層的運行效率[13-16].本文添加交換機負載指標.交換機流表空間有限，更新過程中對交換機流表空間占用的多少也是判斷方案優劣的重要指標[17-20].

選取較為經典的4個方案[5-8]與本文提出方案進行對比，包括國外MCGEER[5]、REITBLATT[6]方案和國內2個方案[7-8]，將以本方案與上述方案進行相應性能指標對比.

3.1 實驗環境

本文實驗環境為虛擬機Ubuntu16.04系統環境，安裝Mininet應用，Ryu控制器.

首先對比控制負載的優化情況，采用簡單拓撲圖1進行實驗，其中s1、s2、s3、s4、s5、s6為交換機，h1、h2為主機.

圖1 數據中心交換機拓撲示意Fig.1 Schematic diagram of data center switch topology

如圖1所示，由h1向h2發送數據包，交換機舊路徑為s1→s2→s3→s4，新路徑為s1→s5→s6→s4.

3.2 實驗結果

控制負載的情況可以轉化為相同網絡傳輸下上傳控制器數據包的個數.進行10次實驗并記錄實驗結果，如圖2所示.

文獻[5]向舊路徑交換機s1、s2、s3、s4寫入中間流表，中間流表即將數據包上傳至控制器，全部寫入完成后等一個端到端時延，之后刪除舊流表寫入新流表，數據包發回網絡.由于引入中間流表，其更新時間較長，更新過程中上傳數據包也最多.文獻[6]中沒有向控制器上傳數據包的過程，所以整個更新過程中沒有數據包上傳至控制器.由于文獻[7]中在上傳數據包后等待一個端到端時延后再更新所有新路徑交換機s5、s6、s4，而本方案只需在端到端時延后更新s4以及安裝s1流表即可，所以在相同網絡傳輸速率下，本文方案在上傳時間上少于文獻[8]，因此更新過程中上傳數據包數量也更少.文獻[8]控制負載較其他方案，只需更新入口交換機s1即可下發數據包，所以其在控制負載方面較優.

各方案和本方案在交換機s4流表存儲空間占用方面的比較，如圖3所示.由于幾種方案的更新策略不同，新舊路徑共用交換機s4存儲空間相關流表個數占總更新時間比例不同.

文獻[5]首先在入口交換機s1和舊路徑交換機中更新中間流表，然后新路徑更新新流表，整個過程中交換機s4從舊流表更新為中間流表，后更新為新流表，更新前后新舊流表并沒有長時間共存，此狀態時長約占更新過程的90%，效果較好.文獻[6]中額外標簽完成后，將新流表寫入入口交換機以及新路徑交換機中，更新數據包VLAN后，等待一個端到端時延即刪除舊流表，其整個更新過程中交換機s4始終存有新舊2套流表，其交換機負載較大.文獻[7]先將數據包上傳，然后向新路徑交換機下發新流表，因此s4交換機流表空間中有新舊2套流表，一個最長端到端時延后，新路徑交換機刪除舊流表，即s4舊流表刪除，其過程中s4流表空間中有新舊2套流表時間較長，該時長占整個更新時間約為90%，交換機負載相對較大.文獻[8]方案中首先向新路徑交換機中安裝新流表，s4中新增新流表，而后完成對s1流表的更新、下發數據包等，最后刪除新路徑交換機中的舊流表，此時更新過程結束.所以在整個更新完成過程中s4交換機流表空間中始終存有新舊2套流表，交換機負載較大.

圖2 上傳數據包對比Fig.2 Comparison of the number of uploaded data packets

圖3 交換機s4流表更新時間占比Fig.3 Proportion of update time of s4 flow tables

本文方案則是一開始對s5、s6流表進行更新，而后刪除s1中舊流表，并等待延時后即更新s4流表，寫入新流表后隨即刪除舊流表，所以在整個過程中s4交換機中流表數量基本不變，且相對文獻[5]沒有引入中間流表，總體效果最好.

3.3 結果分析

在復雜度方面，文獻[6]中的基于額外標簽的流表更新一致性方案需要添加額外標簽，其復雜度最大.文獻[5]中基于中間流表的流表更新策略因為引入中間流表，其復雜度適中.文獻[7]實現過程簡單，復雜度最小.本方案與文獻[8]復雜度也相對較小.

文獻[6]更新過程中不需要將數據包上傳至控制器，所以其更新時間最短.文獻[5]由于需要更新中間流表和等待端到端時延由此更新時間也相對較長.本方案對交換機集合分別更新，其更新時間較短.

本方案在控制負載方面由于減少了上傳數據包的時間，對控制器資源占用相對較小，文獻[5]更新過程中可能會出現下發數據包的交換機中規則依然是中間流表的情況，交換機會將數據包重新發回控制器，所以其控制負載相對本方案較大.文獻[6]更新過程中不需要將數據包上傳至控制器，由此控制負載相對本方案有優勢.

交換機負載本方案相對于文獻[8]由于對新舊路徑共用交換機的處理，保證了新舊流表不同時存在于一個交換機中.文獻[6]由于對數據包和流表添加額外的標簽，新舊流表持續存在于相應的交換機中，交換機負載最大.

各方案具體對比如表2.

表2 各方案比較

4 結束語

提出了一種流表更新一致性的策略，對傳統更新策略進行改進，合理地保證了流表更新的一致性.該方案在與其他方案的對比中可以看出一些優勢，在交換機負載可控的范圍內，減小了控制負載，更新時間較快，且較其他方案來說其各項指標更均衡，有效地減小了易被忽視的交換機負載問題，總體上流表更新效果較好.