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

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

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

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

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

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

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

1.1 方案設計

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

表1 符號及其描述

流表的更新過程是控制器對交換機轉(zhuǎn)發(fā)規(guī)則的修改，首先要保證的是數(shù)據(jù)包的不丟失，以及保證交換機對數(shù)據(jù)流的轉(zhuǎn)發(fā)規(guī)則唯一性，方案步驟如下.

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

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

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

1.2 算法描述

輸入: G(V,L) //數(shù)據(jù)中心網(wǎng)絡拓撲 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 // 下發(fā)數(shù)據(jù)包 15)F=(B-V) //F為V對B的補集16)for (s0i in F) //判斷交換機為舊路徑剩余交換機17) delete R0i //刪除交換機舊流表18) return R1j

2 一致性證明

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

F(x)=F0(x),

(1)

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

(2)

F(x)=c，

(3)

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

(4)

F(x)=F1(x).

(5)

以上過程中對應數(shù)據(jù)包的狀態(tài)分為2種：上傳至控制器和轉(zhuǎn)發(fā).在轉(zhuǎn)發(fā)過程中，其新舊規(guī)則并未同時轉(zhuǎn)發(fā)數(shù)據(jù)包，在邏輯上保證了流表更新的一致性.

3 仿真實驗

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

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

3.1 實驗環(huán)境

本文實驗環(huán)境為虛擬機Ubuntu16.04系統(tǒng)環(huán)境，安裝Mininet應用，Ryu控制器.

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

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

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

3.2 實驗結(jié)果

控制負載的情況可以轉(zhuǎn)化為相同網(wǎng)絡傳輸下上傳控制器數(shù)據(jù)包的個數(shù).進行10次實驗并記錄實驗結(jié)果，如圖2所示.

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

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

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

圖2 上傳數(shù)據(jù)包對比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交換機中流表數(shù)量基本不變，且相對文獻[5]沒有引入中間流表，總體效果最好.

3.3 結(jié)果分析

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

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

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

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

各方案具體對比如表2.

表2 各方案比較

4 結(jié)束語

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