SDN中基于流重定向的MPLS標簽算法

王蒞晟,伊 鵬,谷允捷,江逸茗

(中國人民解放軍戰(zhàn)略支援部隊信息工程大學 信息技術(shù)研究所,鄭州 450002)

0 概述

軟件定義網(wǎng)絡(Software-Defined Network,SDN)作為未來最有可能取代傳統(tǒng)網(wǎng)絡的新型網(wǎng)絡體系結(jié)構(gòu)之一,在近幾年得到了廣泛的應用研究[1-3]。軟件定義網(wǎng)絡采用了數(shù)控分離的機制,相對于傳統(tǒng)網(wǎng)絡架構(gòu),擁有控制邏輯集中、開放可編程、細粒度流管控的優(yōu)勢。

軟件定義網(wǎng)絡的控制平面通過OpenFlow[4]協(xié)議掌握數(shù)據(jù)平面的全局拓撲,當系統(tǒng)中到達一條新流時,交換機首先會在已存儲的流表項中查找是否有匹配條目,如果存在與該流匹配的流表項,則根據(jù)流表項對新流進行轉(zhuǎn)發(fā)。如果沒有匹配條目,則數(shù)據(jù)平面的交換機將元數(shù)據(jù)與新流前128 MB的內(nèi)容封裝成Packet-In消息通過OpenFlow代理(OpenFlow Agent,OFA)向上傳遞給控制平面,控制平面對路由進行計算后通過下放流表的方式在沿途交換機上安裝相應轉(zhuǎn)發(fā)規(guī)則,新流根據(jù)流表中的轉(zhuǎn)發(fā)規(guī)則進行轉(zhuǎn)發(fā),下放的流表均安裝在三態(tài)內(nèi)容尋址存儲器(Ternary Content Addressable Memory,TCAM)[5]中。

在軟件定義網(wǎng)絡中,TCAM模塊負責流表項的更新、存儲和查找工作,然而由于TCAM并非專為OpenFlow交換機設計,其具有成本高、功耗大、容量小、流表更新操作速率較慢等缺陷,導致數(shù)據(jù)包下行鏈路存在性能瓶頸問題,基于Pica8交換機[6]測出的TCAM流表安裝速率僅為每秒200條,相比早期控制平面,單個NOX[7]控制器達到了每秒30 000條處理速度,在使用并行的Maestro控制器[8]下甚至達到每秒600 000條的請求處理速度,每秒200條的流安裝速率很容易出現(xiàn)流表安裝速率跟不上控制器處理速率,進而出現(xiàn)下行控制鏈路擁塞以及流請求無法得到及時傳輸,嚴重影響通信質(zhì)量的情況。

研究人員對TCAM的研究大多集中在流表存儲容量[9-12]。文獻[9]介紹了一種表項聚合的方式,通過將多個表項通過特征合并為一個表項,節(jié)省流表項空間,表項聚合分為非前綴聚合和前綴聚合,然而SDN中許多多元匹配字段不適合聚合,因此表項聚合并不適用于大多數(shù)情況。文獻[10]介紹了一種針對timeout的表項優(yōu)化方式,通過動態(tài)改變表項存活時間來降低表項容量浪費的情況,但是這種方式可能會增加下行控制鏈路的壓力,造成某些流表多次下發(fā)。

現(xiàn)有的研究多數(shù)忽略了交換機下行控制鏈路可能出現(xiàn)的擁塞問題,這可能導致當短時間內(nèi)控制器向交換機下發(fā)大量流表時,交換機TCAM中仍然存在存儲空間,但是由于流表更新速率過慢導致無法快速安裝流表,進而導致下行控制鏈路擁塞,引起TCAM資源的浪費以及用戶服務延時的增加。文獻[13-14]指出現(xiàn)有網(wǎng)絡硬件條件下軟件定義網(wǎng)絡控制鏈路存在性能瓶頸。文獻[8]提出將流請求重定向到虛擬交換機,利用虛擬交換機較強的CPU處理能力進行packet-in消息上傳和流表項安裝,然而虛擬交換機具有較高的部署成本,不適用于大規(guī)模網(wǎng)絡部署。文獻[15]針對該問題提出了一種改進的基于隨機Runting的路由部署(Random Ruting Dployment,RRD)算法,通過添加約束的方法從所有可能路由路徑中選出最優(yōu)路徑,然而該問題是一個NP難問題,只能得到近似解,且計算過程較為復雜。

本文結(jié)合文獻[16]提出的數(shù)據(jù)包封裝多協(xié)議標簽交換(Multi-Protocol Label Switching,MPLS)與分段路由(Segment Routing,SR)的方法,提出一種基于流重定向的MPLS標簽算法FRML。通過設置觸發(fā)閾值,當路徑中需安裝的流表數(shù)超過閾值時,選取路徑上合適的交換機,僅向該交換機下發(fā)添加標簽的流表,之后的交換機只需根據(jù)打好的標簽即可選擇相應端口的轉(zhuǎn)發(fā)操作,以緩解交換機中下行控制鏈路資源緊張的狀況。

1 問題分析與建模

1.1 問題分析

從OpenFlow交換機工作原理可以發(fā)現(xiàn),SDN網(wǎng)絡數(shù)據(jù)包傳輸依賴于OpenFlow交換機與SDN控制器之間的信息交互,然而由于TCAM性能限制,流表項更新速率僅為每秒200條,這就導致當系統(tǒng)內(nèi)突發(fā)流量過大或遇到惡意攻擊時很可能會出現(xiàn)TCAM存儲空間仍然充足,但是流表無法及時更新到TCAM中的情況,使得SDN網(wǎng)絡下行控制鏈路擁塞,進而導致新流無法得到及時傳輸,嚴重影響系統(tǒng)性能。

對于下行控制鏈路擁塞問題,將形成擁塞的流表項分為兩類:一類是下發(fā)到源節(jié)點的流表項,數(shù)據(jù)最初存儲于源節(jié)點的緩存中,因此無論是傳統(tǒng)方法還是本文采用的MPLS算法都需要在源節(jié)點下發(fā)流表,此類流表的負載始終存在,只能通過重定向等方法利用其他交換機分擔;另一類是控制器計算出流路徑后在路徑上的交換機中下發(fā)的流表項,此類流表項可以使用MPLS算法用數(shù)據(jù)前綴的方式代替,因此屬于不是必須的下行控制鏈路負載,但是需要占用數(shù)據(jù)鏈路帶寬,在數(shù)據(jù)鏈路負載和線性控制鏈路負載之間做出權(quán)衡,選擇路徑中部分交換機下發(fā)流表進行數(shù)據(jù)流的轉(zhuǎn)發(fā)操作。

1.2 問題建模

1.2.1 系統(tǒng)元素

系統(tǒng)元素主要包括以下3種:

1)底層網(wǎng)絡。本文考慮將軟件定義網(wǎng)絡結(jié)構(gòu)用一個三元組來表示,即S(U,V,E)。其中,U={u1,u2,…,um}代表所有控制器,V={v1,v2,…,vm}代表所有交換機,m=|U|表示控制器數(shù)量,n=|V|表示交換機數(shù)量。在多控制器SDN中,有m

2)閾值設定。對于交換機vi,用F(vi)(條)表示待下發(fā)流表數(shù),并定義其閾值,如式(1)所示:

Ri=cd(vi)·B

(1)

其中,B為其重定向閾值因子。對于源節(jié)點,當預計下發(fā)流表數(shù)超過閾值時,先將部分流通過通配符的方式重定向到鄰居負載較低的交換機中,用Vi表示與vi距離只有一跳的所有交換機集合,pi=|Vi|。規(guī)定所有超出閾值的交換機集合為V′。當超過閾值時,將ft(vi,vij)條流量從vi重定向到vij,j=1,2,…,pi,vij∈Vi。對于路徑交換機,若某一條流的路徑上有交換機負載超過閾值,則啟用MPLS方式進行流表下發(fā),在路徑交換機中選擇n個負載最低的交換機下發(fā)流表。為方便討論,假設所有下行鏈路具有相同的鏈路容量,即所有交換機鏈路容量均為cd(v)·B,則閾值可以統(tǒng)一表示為:

R=cd(v)·B

(2)

對于源節(jié)點重定向過程,為增加系統(tǒng)彈性,設定重定向下限T,其中T

3)鏈路開銷。每個MPLS標簽的大小為4 MB,因此,定義其額外鏈路開銷如式(3)所示:

(3)

其中,lf表示流f的路徑向量,即:

(4)

(5)

1.2.2 優(yōu)化目標與約束條件

優(yōu)化目標與約束條件如下:

1)優(yōu)化目標

對于本文提出的下行控制鏈路擁塞問題,將該問題定義為一個最優(yōu)化問題,優(yōu)化目標為使下行控制鏈路負載因子最小,交換機下行控制鏈路負載因子如式(6)所示:

(6)

ω越接近于1,證明系統(tǒng)總的負載越大,超過1則證明系統(tǒng)中待安裝流表超過了系統(tǒng)能夠承載的最大值,可能會出現(xiàn)系統(tǒng)崩潰等極其惡劣的情況。

該最優(yōu)化問題優(yōu)化目標如式(7)所示:

minω,?vi∈V

(7)

2)約束條件

約束條件主要包括以下3種:

(8)

(9)

其中:

(10)

(3)數(shù)據(jù)鏈路開銷約束。采用MPLS算法進行流表項下發(fā)的同時,也需要考慮可能會給數(shù)據(jù)鏈路帶來的額外開銷,每條流給數(shù)據(jù)鏈路帶來的額外開銷不得高于給定閾值C(f),則有:

Inf(lf)

(11)

2 算法設計

針對下行控制鏈路擁塞問題,本文采用一種改進的MPLS算法進行解決,主要方法如下:1)基于OpenFlow協(xié)議周期性收集流表安裝分布情況和接口狀況;2)預測下一個周期的各交換機流表安裝負載,將下周期可能超載的源節(jié)點交換機的流量重定向到相鄰的負載較低的交換機,作為新的源節(jié)點進行路徑計算;3)計算路徑中如果存在下行控制鏈路負載超過閾值的交換機,則對該條流采用MPLS方式下發(fā)流表,選取路徑中負載較低的幾個交換機下發(fā)流表,借用一部分數(shù)據(jù)鏈路的帶寬來緩解下行控制鏈路負載過高的問題。

針對上述提出的約束條件和優(yōu)化目標,首先通過一個實例對工作流程進行說明。對于如圖1所示的拓撲,參考文獻[6]的數(shù)據(jù),假設拓撲中交換機安裝流表項的速度為每秒200條,在單位時間內(nèi)存在兩組流f1、f2先后到達交換機v2,流f1目的節(jié)點為v6,流f2目的節(jié)點為v4,兩組流均包含200條子流,且f1先于f2進入系統(tǒng),則進行優(yōu)化前,流傳輸路徑及下行控制鏈路負載如圖1(a)所示?？梢钥闯?流f1與流f2均需經(jīng)過路徑v2～v4,這就導致交換機v2和v4均需安裝400條流表,嚴重超過了交換機安裝速率的每秒200條,此時會導致下行控制鏈路擁塞,流表無法及時安裝到系統(tǒng)中,造成流傳輸?shù)难訒r,影響用戶體驗。

針對以上情況,本文提出的算法流程如圖1(b)所示,首先將f2的流重定向到v1中,由v1作為新的源節(jié)點接收控制器的流表,然后控制器下發(fā)的流表為在f2的數(shù)據(jù)包中插入MPLS標簽,該標簽告知交換機數(shù)據(jù)從哪個端口發(fā)出,發(fā)出后交換機對本交換機對應的MPLS標簽做刪除處理,通過重定向和MPLS標簽的方式共同作用緩解系統(tǒng)下行控制鏈路擁塞問題?？梢钥闯?使用本文方法可以降低復用路徑上的流表安裝負載,且能夠利用鄰居節(jié)點來分擔源節(jié)點的流表安裝負載,付出的代價為增加數(shù)據(jù)鏈路的負擔,如本實例減少了兩個擁塞交換機上的流表安裝負載,在數(shù)據(jù)鏈路每條流增加了(2+1)×4=12個字節(jié)的開銷,單條鏈路每條流最多增加了2×4=8個字節(jié)的開銷,相比于在兩個交換機各多出200條的流表安裝負載,顯然擁有更好的效果。

圖1 MPLS算法流程示意圖Fig.1 Schematic diagram of MPLS algorithm procedure

2.1 源節(jié)點重定向算法

根據(jù)系統(tǒng)對下一單位時間流表下發(fā)的預測,當源節(jié)點可能發(fā)生下行控制鏈路擁塞時,提前在交換機中安裝通配符,將指定數(shù)目的流向鄰居交換機進行重定向,由空閑的鄰居節(jié)點作為新的源節(jié)點進行Packet-In消息的上報和流表下發(fā)節(jié)點,鄰居節(jié)點間負載差距有多種情況,因此針對各種情況制定規(guī)則對流量進行重定向:

假設vi有鄰居交換機vi1,vi2,…,vip∈Vi,且F(vi1)

規(guī)則1當F(vi)

ft(vi,vij)=0

(12)

規(guī)則2若對于vi1,有F(vi1)

ft(vi,vi1)=F(vi)-T

(13)

(14)

ft(vi,vij)=R-F(vij),j=1,2,…,m

(15)

規(guī)則5若對于vi1,有F(vi1)>R,且F(vi)-R>F(vi1)-R,即鄰居節(jié)點均超載但仍有負載低于vi的節(jié)點,則:

(16)

規(guī)則6若對于vi1,有F(vi1)>R,且F(vi)-R

ft(vi,vij)=0

(17)

重定向算法如下:

算法1源節(jié)點流重定向算法

輸入重定向閾值R,鄰接矩陣V,系統(tǒng)內(nèi)節(jié)點負載

輸出重定向流量數(shù)和方向

1.?vi∈V & F(vi)>R

2.for vij∈Vi,i=1,2,…,n

3.if F(vij)

4.if F(vi)-T

5.ft(vi,vi1)=F(vi)-T

6.else

7.ft(vi,vij)=R-F(vij)

8.end if

9.else if F(vi)-R>F(vi1)-R

11.end if

2.2 MPLS算法

利用MPLS算法下發(fā)流表,具體實現(xiàn)過程如圖2所示,MPLS算法將路徑信息作為額外標簽封裝在原始數(shù)據(jù)包中,這樣就只需在源節(jié)點和路徑上某幾個交換機節(jié)點下發(fā)流表項對標簽信息進行封裝,其他交換機只需要讀取MPLS中的端口信息,將數(shù)據(jù)包從相應的端口發(fā)送出去即可,這種方法可以利用數(shù)據(jù)鏈路的帶寬來緩解交換機中下行控制鏈路資源緊張的情況。

圖2 MPLS算法實現(xiàn)過程Fig.2 Implementation process of MPLS algorithm

對于需要利用MPLS算法進行傳輸?shù)牧?最主要的是選取路徑中下發(fā)流表的交換機,本文采用貪心算法,每次選取一個路徑上負載最低的交換機作為中間節(jié)點,直到?jīng)]有負載低于閾值R的交換機可選,或者MPLS算法的路徑開銷低于某個閾值C’為止,然后進行流表下發(fā)并進行下一條流的計算,具體算法流程如下:

算法2MPLS算法交換機選擇

輸入流路徑向量lf,路徑上交換機負載F(vi)

初始化下發(fā)交換機集合Vd={vs}

輸出下發(fā)交換機集合Vd

1.對路徑lf上交換機按負載大小排序,F(v′1)

2.for v′i∈lf,i=1,2,…,n

3.if F(v′i)>R or Inf(lf)

4.break

5.else add v′iin Vd

7.end if

8.end for

2.3 算法復雜度分析

對于每一個單位時間的流表安裝請求,本文算法計算過程如下:1)檢測交換機超載情況;2)遍歷源節(jié)點的鄰居節(jié)點,并選擇合適的鄰居節(jié)點對流量進行重定向;3)選擇流量進行MPLS標簽安裝。其中當檢測到交換機超載時,便會啟動后續(xù)過程,遍歷超載交換機的所有鄰居節(jié)點,進行一次重定向,之后會選擇重定向后的流進行MPLS算法的交換機選擇,最壞的情況是將所有交換機都選擇一遍。因此,可以得到本文算法復雜度為O(m+n)。

3 實驗驗證

3.1 性能指標與對比算法

對比算法選取了兩種算法,第一種是OSPF路由算法[17],其運用經(jīng)典的最短路由算法,另一種是文獻[15]提出的OPT-L算法,即對LRD問題進行線性松弛后的線性最優(yōu)解算法。

3.2 仿真實驗

本文實驗在mininet[18]平臺上搭建了仿真實驗環(huán)境,利用Ryu[19]開源控制器軟件作為系統(tǒng)控制平面,選取了一個擁有100個交換機節(jié)點和50個終端節(jié)點的校園網(wǎng)絡拓撲[20],設定該網(wǎng)絡數(shù)據(jù)鏈路容量為100 Mb/s,運用隨機算法模擬系統(tǒng)中隨機到達的流量。為減少隨機算法對模擬結(jié)果造成影響,對每組實驗進行50次,取平均值得到最終的仿真結(jié)果。仿真實驗平臺為Inter Core i7-8700 3.2 GHz CPU,16 GB內(nèi)存,Linux系統(tǒng)個人電腦。采用Java語言搭建仿真環(huán)境,并借助Matlab對實驗結(jié)果進行分析。

首先對3種算法的系統(tǒng)最大下行控制鏈路負載進行對比,最大下行控制鏈路負載就是系統(tǒng)中負載最大的交換機的負載,可以衡量系統(tǒng)中負載最大的點的情況。仿真結(jié)果如圖3所示,可以看出,隨著系統(tǒng)中某個交換機到達的流數(shù)量增加,OSPF算法的交換機最大下行控制鏈路負載隨之增加,并很快超過了系統(tǒng)最大每秒安裝速率,造成嚴重的擁塞問題。OPT-C算法可以通過重定向方法緩解系統(tǒng)中最大下行控制鏈路負載,但是其重定向單元為宏流,即某一組流,因此受限于宏流的大小,只能將負載降低到OSPF算法的50%,且依然會使系統(tǒng)中負載超過安裝速率,造成較大的下行控制鏈路負載。

圖3 最大下行控制鏈路負載Fig.3 Maximum downlink control link load

本文FRML算法在系統(tǒng)負載到達閾值200前,與OSPF算法負載一致,但是并未超過每秒負載上限。隨著系統(tǒng)中流量數(shù)增加,重定向及MPLS標簽機制觸發(fā),可以將系統(tǒng)中負載降低到閾值200附近,并保持及其緩慢的增長速度,可以看到在負載較低時,FRML算法可以不進行任何操作,降低系統(tǒng)開銷,當超過閾值時,FRML算法可以顯著降低系統(tǒng)負載,且效果優(yōu)于OPT-C算法。

下文對數(shù)據(jù)鏈路負載因子ω與系統(tǒng)最大流表項插入延時進行仿真,仿真結(jié)果如圖4所示。

圖4 負載因子與最大流表項插入延時對比Fig.4 Comparison of load factor and maximum flow table insertion delay

圖4(a)表示負載因子與系統(tǒng)中總流量數(shù)之間的關(guān)系,隨著系統(tǒng)中流量數(shù)增加,系統(tǒng)中出現(xiàn)某些交換機嚴重超載的情況,OSPF系統(tǒng)中負載顯著增加,最后幾乎達到系統(tǒng)滿載,嚴重影響系統(tǒng)性能,OPT-C系統(tǒng)可以通過流重定向機制改善OSPF系統(tǒng)的負載,但是系統(tǒng)中流表下發(fā)數(shù)目并未減少,而只是將某些交換機的負載轉(zhuǎn)移到了其他空閑交換機,因此隨著流量數(shù)增加,系統(tǒng)中負載最終也會達到滿載。FRML算法從根本上減少了下發(fā)到系統(tǒng)中的流表數(shù),能夠變相增加系統(tǒng)容量,大大減緩達到滿載的速率。

圖4(b)表示系統(tǒng)中最大流表插入時延與系統(tǒng)中流量數(shù)的關(guān)系。隨著系統(tǒng)中流量數(shù)增加,OSPF系統(tǒng)逐漸達到滿載,擁塞導致流表項插入延遲指數(shù)增長,造成嚴重的延遲現(xiàn)象。而OPT-C和FRML兩種算法均使用了重定向算法,不會造成某個交換機流表插入延時的顯著增加,但是FRML需要插入的流表數(shù)相對較少,因此FRML算法流表項插入延時相比于OPT-C算法有一定的優(yōu)勢。

最后對系統(tǒng)中的網(wǎng)絡吞吐量進行仿真,結(jié)果如圖5所示,可以看出OSPF算法很容易出現(xiàn)單個交換機負載過高,嚴重影響整個系統(tǒng)的負載能力,限制網(wǎng)絡吞吐量。OPT-C算法可以緩解單個交換機負載能力,但是系統(tǒng)總的負載能力仍然沒變,在流量增加到一定限度時仍然會達到吞吐量瓶頸,本文提出的FRML算法減少了系統(tǒng)中下發(fā)流表項數(shù),使得系統(tǒng)中有限的下行控制鏈路容量可以容納更多的流表項下發(fā),因此可以進一步增加網(wǎng)絡吞吐量及系統(tǒng)的容量。

圖5 網(wǎng)絡吞吐量仿真結(jié)果Fig.5 Simulation results of network throughput

4 結(jié)束語

本文針對SDN系統(tǒng)中下行控制鏈路負載較大的問題,通過重定向和下放MPLS標簽的方法,緩解了源節(jié)點交換機與路徑交換機存在的流表項插入速率較低導致的系統(tǒng)性能下降,并在SDN實驗平臺上進行了驗證,結(jié)果表明,與傳統(tǒng)的OSPF、OPT-C算法相比,該算法鏈路負載分別降低近60%、20%,最大表項插入延時方面相比于OSPF算法降低了近90%,略優(yōu)于OPT-C算法,同時相比于OSPF算法和OPT-C算法網(wǎng)絡吞吐量分別增加了近200%和30%。本文假設條件為流表容量充足條件下的流表下發(fā)策略,未考慮流表容量不足的情況會對本文實驗造成的影響,下一步將針對更復雜的情況進行探討,并在實際實驗平臺中驗證本文算法的高效性與實用性。