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

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

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

0 概述

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

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

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

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

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

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

1 問題分析與建模

1.1 問題分析

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

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

1.2 問題建模

1.2.1 系統元素

系統元素主要包括以下3種:

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

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

Ri=cd(vi)·B

(1)

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

R=cd(v)·B

(2)

對于源節點重定向過程,為增加系統彈性,設定重定向下限T,其中T

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

(3)

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

(4)

(5)

1.2.2 優化目標與約束條件

優化目標與約束條件如下:

1)優化目標

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

(6)

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

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

minω,?vi∈V

(7)

2)約束條件

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

(8)

(9)

其中:

(10)

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

Inf(lf)

(11)

2 算法設計

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

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

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

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

2.1 源節點重定向算法

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

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

規則1當F(vi)

ft(vi,vij)=0

(12)

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

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

(13)

(14)

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

(15)

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

(16)

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

ft(vi,vij)=0

(17)

重定向算法如下:

算法1源節點流重定向算法

輸入重定向閾值R,鄰接矩陣V,系統內節點負載

輸出重定向流量數和方向

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

圖2 MPLS算法實現過程Fig.2 Implementation process of MPLS algorithm

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

算法2MPLS算法交換機選擇

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

初始化下發交換機集合Vd={vs}

輸出下發交換機集合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)遍歷源節點的鄰居節點,并選擇合適的鄰居節點對流量進行重定向;3)選擇流量進行MPLS標簽安裝。其中當檢測到交換機超載時,便會啟動后續過程,遍歷超載交換機的所有鄰居節點,進行一次重定向,之后會選擇重定向后的流進行MPLS算法的交換機選擇,最壞的情況是將所有交換機都選擇一遍。因此,可以得到本文算法復雜度為O(m+n)。

3 實驗驗證

3.1 性能指標與對比算法

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

3.2 仿真實驗

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

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

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

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

下文對數據鏈路負載因子ω與系統最大流表項插入延時進行仿真,仿真結果如圖4所示。

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

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

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

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

圖5 網絡吞吐量仿真結果Fig.5 Simulation results of network throughput

4 結束語

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