一種應(yīng)用于無線軟件定義網(wǎng)絡(luò)的流表數(shù)量約減方法

孔劍鋒 劉振海

1(鹽城工學(xué)院教務(wù)處 江蘇 鹽城 224051)2(鹽城工學(xué)院信息工程學(xué)院 江蘇 鹽城 224051)

0 引 言

近年來，無線SDN(W-SDN)技術(shù)被廣泛應(yīng)用于傳感器網(wǎng)絡(luò)[1-2]、5G通信網(wǎng)絡(luò)、M2M通信等應(yīng)用場景中，用來實(shí)現(xiàn)可控路由、靈活流量工程和集中式網(wǎng)絡(luò)管理等功能。然而，由于SDN技術(shù)最初的設(shè)計目標(biāo)為有線局域網(wǎng)場景，因此在將SDN技術(shù)應(yīng)用于無線網(wǎng)絡(luò)環(huán)境之前，仍然存在一些問題需要解決。其中，如何有效地減少W-SDN中所需的流表數(shù)量從而提高網(wǎng)絡(luò)的性能和效率，是當(dāng)前最迫切需要解決的問題之一。

由于W-SDN繼承了SDN的框架以及基于流表的轉(zhuǎn)發(fā)模式，因此為了實(shí)現(xiàn)W-SDN中對于流量路由的可控性，W-SDN的中央控制器必須為每流在路由的每一跳上安裝流表。因此，每個無線節(jié)點(diǎn)必須以流表的形式存儲較多的狀態(tài)信息，從而導(dǎo)致三個問題：首先，通常情況下，無線節(jié)點(diǎn)的存儲空間比有線網(wǎng)絡(luò)中的網(wǎng)絡(luò)設(shè)備小得多，從而只能安裝少量流表在每個節(jié)點(diǎn)中。因此，網(wǎng)絡(luò)可容納的最大流量數(shù)量相當(dāng)有限。其次，當(dāng)流表數(shù)量較多時，流表匹配過程可能消耗過多的能量，從而縮短無線節(jié)點(diǎn)的使用壽命。第三，無線節(jié)點(diǎn)的處理能力通常較弱，以至于太多的流表可能會帶來較大的查表延遲。

一般情況下，解決W-SDN流表數(shù)量的方法有兩種。第一種方式是流量工程[3-5]，通過這種方式流量可以更加均勻地分布，因此每個節(jié)點(diǎn)中的流表數(shù)量也獲得了平均，從而能夠避免某個節(jié)點(diǎn)存儲過多的流表。第二種方式是源路由，它將路由信息存儲在分組報頭中，而不是無線節(jié)點(diǎn)的流表中[6-7]。因此，使用源路由，無線節(jié)點(diǎn)不需要存儲流量狀態(tài)信息，但是需要數(shù)據(jù)包帶有更長的包頭，從而導(dǎo)致帶寬浪費(fèi)和可擴(kuò)展性的降低。針對以上兩種方法的不足，在本文中，我們提出了一種稱為LSP(Label Switch Path)重用的新型機(jī)制，相比于以上兩種方法，它可以通過更短的數(shù)據(jù)包頭部，實(shí)現(xiàn)最好的流表約減效果。為了實(shí)現(xiàn)這種方法，我們將MPLS中的標(biāo)簽交換路徑LSP(Label Switch Path)引入到W-SDN中。基于Openflow支持的標(biāo)簽彈出(Pop)，壓入(Push)和交換(Swap)操作，我們在數(shù)據(jù)包頭中嵌入多個標(biāo)簽，并使用生存時間TTL(Time To Live)控制數(shù)據(jù)包在某個LSP上傳輸?shù)奶鴶?shù)，從而使得數(shù)據(jù)包能夠在不同的LSP之間切換。因此，同一條LSP可以具有不同源和目的地的流量重用，單個流量可以使用不同的LSP完成端到端的傳輸。在這種機(jī)制下，安裝在每個無線節(jié)點(diǎn)中的流表僅與通過節(jié)點(diǎn)的LSP相關(guān)，而與流量的數(shù)量無關(guān)。因此，可以有效減少每個節(jié)點(diǎn)維護(hù)的狀態(tài)信息。

綜上所述，本文的貢獻(xiàn)主要如下：

(1) 提出了一種LSP重用方法來解決無線SDN中的流表數(shù)量約減問題；給出了該方法的詳細(xì)設(shè)計和實(shí)現(xiàn)，并在軟件平臺上實(shí)現(xiàn)了原型系統(tǒng)。

(2) 研究了最優(yōu)的LSP規(guī)劃問題；建立了最小化流表數(shù)量的數(shù)學(xué)模型；提出了求解數(shù)學(xué)模型的啟發(fā)式算法。

(3) 采用仿真實(shí)驗，評估了不同W-SDN流表數(shù)量約減方法的性能，并證明了本文提出方法的可行性和有效性。

1 無線軟件定義網(wǎng)絡(luò)中的流表約減

從邏輯上講，W-SDN主要由一個中央控制器和一些SDN使能的節(jié)點(diǎn)組成。通過中央控制器根據(jù)標(biāo)準(zhǔn)SDN范式安裝的流表，每個節(jié)點(diǎn)可以實(shí)現(xiàn)針對每流的可控性。通過這種機(jī)制，每個節(jié)點(diǎn)的控制功能集中在中央控制器中，因此控制平面和無線網(wǎng)絡(luò)的轉(zhuǎn)發(fā)平面是分離的，而這種分離機(jī)制能夠為無線通信網(wǎng)絡(luò)帶來網(wǎng)絡(luò)的可全局視圖、網(wǎng)絡(luò)可編程性、網(wǎng)絡(luò)可虛擬化等好處。無線軟件定義網(wǎng)絡(luò)(W-SDN)是SDN技術(shù)在包含多個無線和有線網(wǎng)絡(luò)的無線異構(gòu)網(wǎng)絡(luò)中的應(yīng)用，其基本結(jié)構(gòu)如圖1所示。目前，已經(jīng)存在多種W-SDN架構(gòu)或項目，如SoftCell[8]、SoftRAN、MobileFlow、OpenRadio[9]等。但是，這些架構(gòu)均沒有關(guān)注減少無線節(jié)點(diǎn)中流表數(shù)量的重要性。為了解決這個問題，本文提出了一種稱為LSP重用的新機(jī)制。

圖1 W-SDN的體系結(jié)構(gòu)

1.1 示例說明

如圖2所示，我們首先用一個例子來說明LSP重用的工作機(jī)制。

(a) 無線網(wǎng)絡(luò)拓?fù)湟约皟蓷lLSP

(b) LSP重用的工作過程圖2 LSP重用機(jī)制的示例網(wǎng)絡(luò)

假設(shè)一個無線網(wǎng)絡(luò)如圖2(a)所示。有兩個LSP是LSP1：LER2→LSR2→LSR3→LER4和LSP2：LER1→LSR1→LSR2→LER3。我們假設(shè)有一個新的流從LER1傳輸?shù)絃ER4。但是，沒有LSP連接LER1和LER4，因此需要使用LDP、RSVP等建立新的LSP。因此，隨著流量的增加，LSP的數(shù)量將會擴(kuò)大。LSP的數(shù)量可能會達(dá)到n2，其中n是標(biāo)簽邊緣路由器(LER)的數(shù)量。我們認(rèn)為，通過LSP重用技術(shù)可以有效降低網(wǎng)絡(luò)中需要的LSP，因為LSP可以被不同目的地的流共享。如圖2(b)所示，在啟用Openflow的LER1中，兩個MPLS標(biāo)簽被堆疊到數(shù)據(jù)包標(biāo)頭中。最外面的標(biāo)簽沿著LSP1發(fā)送分組，而第二層標(biāo)簽沿著LSP2發(fā)送分組。我們將閾值設(shè)置為4?；贠penflow提供的數(shù)據(jù)包編輯能力，最外層標(biāo)簽的TTL設(shè)置為6，內(nèi)層標(biāo)簽的TTL設(shè)置為6。當(dāng)數(shù)據(jù)包從LER1傳輸?shù)絃SR2時，沿著LSP2交換機(jī)的路由器最外面的標(biāo)簽如圖2(b)所示，當(dāng)數(shù)據(jù)包到達(dá)LSR2時，最外層標(biāo)簽的TTL減少到4，LSR2脫去最外層標(biāo)簽，并露出內(nèi)層標(biāo)簽。因此，LSR2檢查內(nèi)層標(biāo)簽并通過LSP1傳輸數(shù)據(jù)包。然后沿著LSP1的路由器交換內(nèi)部標(biāo)簽，直到數(shù)據(jù)包達(dá)到LER4。從以上例子可以看到，在傳統(tǒng)情況下，需要安裝4個新的流表項來完成從LER1到LER4的傳輸。但是，使用LSP重用技術(shù)，可以使用LSP2和LSP1的片段來完成整個端到端傳輸，因此不需要安裝新的流表。

1.2 LSP重用

標(biāo)簽交換路徑(LSP)指的是在MPLS(Multi-Protocol Label Switch)網(wǎng)絡(luò)中，由包頭中MPLS標(biāo)簽標(biāo)識的一條已建立的邏輯隧道。由于Openflow協(xié)議完全支持MPLS操作，如標(biāo)簽壓入，彈出和交換等，因此我們可以將MPLS和LSP直接部署于W-SDN，而無需對軟件或硬件進(jìn)行任何修改。使用LSP傳輸數(shù)據(jù)類似于源路由，但每個無線節(jié)點(diǎn)維護(hù)的狀態(tài)信息(也就是流表數(shù)量)不低于使用分布式路由協(xié)議的狀態(tài)信息，因為它必須建立n2條LSP來實(shí)現(xiàn)整個網(wǎng)絡(luò)的互聯(lián)，其中n是網(wǎng)絡(luò)中標(biāo)簽邊緣路由器(LER)的數(shù)量。我們對傳統(tǒng)的MPLS轉(zhuǎn)發(fā)模式進(jìn)行了修改，并通過在數(shù)據(jù)包報頭中嵌套多個標(biāo)簽并利用TTL彈出最外層標(biāo)簽實(shí)現(xiàn)了一種LSP重用機(jī)制。LSP重用機(jī)制主要需要執(zhí)行三個功能：

1) LSP規(guī)劃 LSP規(guī)劃過程由中央控制器執(zhí)行，而非采用傳統(tǒng)的LDP或RSVP協(xié)議。LSP規(guī)劃過程的目標(biāo)是用盡可能少的LSP覆蓋整個網(wǎng)絡(luò)。

2) 路由編輯 路由編輯功能主要在中央控制器和網(wǎng)絡(luò)邊緣節(jié)點(diǎn)上執(zhí)行。路由編輯的主要任務(wù)是將MPLS標(biāo)簽壓入數(shù)據(jù)包報頭并設(shè)置標(biāo)簽的TTL值。根據(jù)用戶需求和網(wǎng)絡(luò)狀況，路由計算由中央控制器或分布式路由算法完成，并通過Openflow協(xié)議以流表的形式發(fā)送并安裝到流量流入的網(wǎng)絡(luò)邊緣設(shè)備。之后，包頭編輯過程在該設(shè)備處完成，如圖3所示。

圖3 數(shù)據(jù)包頭部中的標(biāo)簽編輯流程與流表結(jié)構(gòu)

3) 分組轉(zhuǎn)發(fā) 該過程主要在中繼節(jié)點(diǎn)或基站進(jìn)行。但是，與傳統(tǒng)的MPLS報文轉(zhuǎn)發(fā)不同，我們設(shè)置TTL閾值來彈出MPLS標(biāo)簽。正常情況下，路由器按照最外層標(biāo)簽轉(zhuǎn)發(fā)數(shù)據(jù)包，當(dāng)標(biāo)簽的TTL等于閾值時，路由器將彈出最外面的標(biāo)簽。繼續(xù)按照下一層標(biāo)簽轉(zhuǎn)發(fā)數(shù)據(jù)包，直到數(shù)據(jù)包到達(dá)目的地。處理流程如圖4所示。

圖4 數(shù)據(jù)包轉(zhuǎn)發(fā)過程中的標(biāo)簽和TTL處理流程與流表結(jié)構(gòu)

這一轉(zhuǎn)發(fā)邏輯可能需要對傳統(tǒng)的網(wǎng)絡(luò)設(shè)備進(jìn)行更改，或引入Openflow的支持來實(shí)現(xiàn)。然而，通過最終的實(shí)驗仿真結(jié)果，我們認(rèn)為這些開銷與成本與LSP重用方法帶來的改進(jìn)相比是值得的。

2 LSP規(guī)劃問題優(yōu)化模型

(1)

目標(biāo)函數(shù)表示優(yōu)化模型希望最小化LSP集合中所有LSP的總長度，以便在給定的LSP數(shù)量下，網(wǎng)絡(luò)中所需的流表數(shù)量能夠最小。

(2)

式(2)保證網(wǎng)絡(luò)的每個鏈路至少被一個LSP覆蓋。

?p∈S,?(i,j)∈E,?(j,k)∈E

(3)

式(3)確保每個LSP都是連續(xù)的。

(4)

(5)

(6)

式(4)-式(6)保證了LSP無環(huán)路。為了找到包含最少LSP的集合P，我們需要讓|P|從0增長到|E|，并針對每個給定的P求解上述數(shù)學(xué)模型。但是，由于數(shù)學(xué)模型中的變量是|P|×|N|維的，因此在大規(guī)模網(wǎng)絡(luò)場景中，計算復(fù)雜度會較高，然而LSP規(guī)劃過程一般需要快速完成，以防止網(wǎng)絡(luò)發(fā)生鏈路故障或路由變化等時業(yè)務(wù)中斷，因此需要提高LSP規(guī)劃算法的效率。出于這個原因，我們提出了一個啟發(fā)式算法，解決LSP的最優(yōu)規(guī)劃問題。算法的基本思想是，在每次迭代中，規(guī)劃一個無環(huán)LSP，使其可以覆蓋盡可能多的未覆蓋的鏈路，直到所有鏈路都被LSP覆蓋。該算法的偽代碼如下所示:

算法1LSP規(guī)則

Input: overlay,topology;

Output:P;

1:booleanstop=false;booleanloop=false

2:whilestop!=truedo

3:forsource=0to|V|do

4:whileloop!=truedo

5: loop=true;

6:forj=0to|V|do

7:fork=0 to |V|do

8:ifnodekandjareconnectedandtheroutefromsourcetokdoesn’tcontainnodejthen

9:ifcover(source,k)+cover(k,j)

>cover(source,j)then

10: route(source,j)=

route(source,k)+route(k,j)

11:endif;

12:endif;

13:endfor;

14:endfor;

15:ifthereisanyroute(source,j)ischangedthenloop=false;

16:endif;

17:endwhile;

18:endfor;

19:findtheoptimalrouteandupdatetheoverlaytopologywiththeoptimalroute;

20:ifalllinksarecoveredthenstop=true

21:elseifstop=false;

22:endif;

23:endwhile;

在算法中，我們使用兩種拓?fù)洌焊采w拓?fù)浜瓦B接拓?fù)?。前者表示鏈路是否被LSP覆蓋，后者表示網(wǎng)絡(luò)中每個節(jié)點(diǎn)的連通性。在算法的過程中，覆蓋拓?fù)鋵⒉粩喔?，但連接拓?fù)鋵⒈３植蛔?。從?行到第17行的循環(huán)中，我們使用動態(tài)規(guī)劃從圖中找出從源到任何終點(diǎn)(LER)的最佳路徑，該路徑能夠覆蓋最多的未覆蓋鏈路。然后，通過從第3行到第18行的循環(huán)，我們計算每個點(diǎn)的最佳路徑，并找到覆蓋當(dāng)前圖中大多數(shù)鏈路的最佳路徑。每次我們計算出最優(yōu)路徑后，我們根據(jù)最佳路徑刪除覆蓋拓?fù)渲羞x定的鏈路，如第19行所示。當(dāng)所有鏈路被LSP覆蓋時，算法停止(第20-21行)。

3 實(shí)驗仿真

在本節(jié)中，我們使用仿真實(shí)驗來評估所提出方法的性能。不失一般性，我們在仿真中使用n×n矩陣網(wǎng)絡(luò)拓?fù)?，如圖5所示。

圖5 仿真實(shí)驗拓?fù)鋱D

我們選擇的比較方法是多點(diǎn)對點(diǎn)隧道合并方式(MP2P)[10-12]，這是最常用的轉(zhuǎn)發(fā)表約簡方法；以及Splano等提出的MPLS網(wǎng)絡(luò)中最新的轉(zhuǎn)發(fā)表約減方式—非對稱合并隧道方法(AMT)[13-14]。圖6給出了不同路由數(shù)目的情況下，網(wǎng)絡(luò)所需的最小流表數(shù)量。

圖6 不同路由數(shù)量下的流表數(shù)量

根據(jù)圖6所示，流表數(shù)量隨路由數(shù)量的增加而增加，但是無論路由數(shù)量多少，采用LSP重用方法總能達(dá)到最小的流表數(shù)量。同時，隨著路由數(shù)量的增加，LSP重用相比于其他方式的優(yōu)勢逐漸擴(kuò)大。當(dāng)路由數(shù)量為100時，與MP2P合并相比，LSP重用可以將流表數(shù)量減少71.9%，與AMT方法相比，可將流表數(shù)量減少58.3%。之后，我們評估不同網(wǎng)絡(luò)規(guī)模下不同方法的性能。

路由數(shù)量設(shè)置為100，不同網(wǎng)絡(luò)規(guī)模下的流表數(shù)量如圖7所示。從圖7中可以看出，隨著網(wǎng)絡(luò)規(guī)模的增加，所有三種方法的流表數(shù)量都會增加。同時，LSP重用方法在任何網(wǎng)絡(luò)規(guī)模下始終能夠達(dá)到最小的流表數(shù)量。因此可以證明，本文提出的方法具有良好的可擴(kuò)展性，可以應(yīng)用于大規(guī)模無線網(wǎng)絡(luò)。除了減少網(wǎng)絡(luò)中流表數(shù)量之外，我們還希望流表數(shù)量的分配盡可能均勻，以避免在某些特定節(jié)點(diǎn)處安裝太多流表，從而導(dǎo)致性能或能耗瓶頸。

圖7 不同網(wǎng)絡(luò)規(guī)模下的流表數(shù)量

圖8顯示了采用三種不同方法時的流表數(shù)量分配情況，從圖8的結(jié)果可以看出，LSP重用方法不僅可以實(shí)現(xiàn)最小的流表數(shù)量，而且可以實(shí)現(xiàn)比其他方法更加均勻的流表分布。

(a) MP2P合并方法 (b) 非對稱合并隧道方法 (c) LSP重用圖8 采用不同方法時的流表數(shù)量分布

此外，當(dāng)使用LSP重用時，數(shù)據(jù)包頭的長度等于僅在最壞情況下等于使用源路由方法時的長度。所以LSP重用導(dǎo)致的帶寬浪費(fèi)比源路由造成的帶寬浪費(fèi)要小得多。在不同最大包長的情況下，兩種方法造成的帶寬浪費(fèi)如圖9所示。

圖9 不同包長下的帶寬浪費(fèi)比率

那么可以得出這樣的結(jié)論：LSP重用可以實(shí)現(xiàn)類似于源路由的路由控制能力，而只需要更短的頭部長度。

4 結(jié) 語

本文研究了W-SDN中的流表數(shù)量約減問題，提出了一種基于MPLS網(wǎng)絡(luò)中LSP概念和Openflow網(wǎng)絡(luò)編程能力的LSP重用方法。通過在數(shù)據(jù)包頭部中嵌套多個MPLS標(biāo)簽并設(shè)置這些標(biāo)簽的TTL值，我們可以控制數(shù)據(jù)包在不同的LSP之間切換，以便利用不同LSP的片段來完成端到端的傳輸。因此，以流表形式存儲的狀態(tài)信息可以顯著減少。通過仿真和實(shí)驗，證明本文提出的方法能夠以很小的流量開銷實(shí)現(xiàn)最佳的流表約減效果。