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

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

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

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

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

1 基于時(shí)序與集合的流表更新策略

1.1 方案設(shè)計(jì)

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

表1 符號(hào)及其描述

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

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

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

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

1.2 算法描述

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

2 一致性證明

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

F(x)=F0(x),

(1)

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

(2)

F(x)=c，

(3)

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

(4)

F(x)=F1(x).

(5)

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

3 仿真實(shí)驗(yàn)

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

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

3.1 實(shí)驗(yàn)環(huán)境

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

首先對比控制負(fù)載的優(yōu)化情況，采用簡單拓?fù)鋱D1進(jìn)行實(shí)驗(yàn)，其中s1、s2、s3、s4、s5、s6為交換機(jī)，h1、h2為主機(jī).

圖1 數(shù)據(jù)中心交換機(jī)拓?fù)涫疽釬ig.1 Schematic diagram of data center switch topology

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

3.2 實(shí)驗(yàn)結(jié)果

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

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

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

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

圖2 上傳數(shù)據(jù)包對比Fig.2 Comparison of the number of uploaded data packets

圖3 交換機(jī)s4流表更新時(shí)間占比Fig.3 Proportion of update time of s4 flow tables

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

3.3 結(jié)果分析

在復(fù)雜度方面，文獻(xiàn)[6]中的基于額外標(biāo)簽的流表更新一致性方案需要添加額外標(biāo)簽，其復(fù)雜度最大.文獻(xiàn)[5]中基于中間流表的流表更新策略因?yàn)橐胫虚g流表，其復(fù)雜度適中.文獻(xiàn)[7]實(shí)現(xiàn)過程簡單，復(fù)雜度最小.本方案與文獻(xiàn)[8]復(fù)雜度也相對較小.

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

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

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

各方案具體對比如表2.

表2 各方案比較

4 結(jié)束語

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