一種應用于無線軟件定義網絡的流表數量約減方法

孔劍鋒 劉振海

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

0 引 言

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

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

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

綜上所述，本文的貢獻主要如下：

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

(2) 研究了最優的LSP規劃問題；建立了最小化流表數量的數學模型；提出了求解數學模型的啟發式算法。

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

1 無線軟件定義網絡中的流表約減

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

圖1 W-SDN的體系結構

1.1 示例說明

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

(a) 無線網絡拓撲以及兩條LSP

(b) LSP重用的工作過程圖2 LSP重用機制的示例網絡

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

1.2 LSP重用

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

1) LSP規劃 LSP規劃過程由中央控制器執行，而非采用傳統的LDP或RSVP協議。LSP規劃過程的目標是用盡可能少的LSP覆蓋整個網絡。

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

圖3 數據包頭部中的標簽編輯流程與流表結構

3) 分組轉發 該過程主要在中繼節點或基站進行。但是，與傳統的MPLS報文轉發不同，我們設置TTL閾值來彈出MPLS標簽。正常情況下，路由器按照最外層標簽轉發數據包，當標簽的TTL等于閾值時，路由器將彈出最外面的標簽。繼續按照下一層標簽轉發數據包，直到數據包到達目的地。處理流程如圖4所示。

圖4 數據包轉發過程中的標簽和TTL處理流程與流表結構

這一轉發邏輯可能需要對傳統的網絡設備進行更改，或引入Openflow的支持來實現。然而，通過最終的實驗仿真結果，我們認為這些開銷與成本與LSP重用方法帶來的改進相比是值得的。

2 LSP規劃問題優化模型

(1)

目標函數表示優化模型希望最小化LSP集合中所有LSP的總長度，以便在給定的LSP數量下，網絡中所需的流表數量能夠最小。

(2)

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

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

(3)

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

(4)

(5)

(6)

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

算法1LSP規則

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;

在算法中，我們使用兩種拓撲：覆蓋拓撲和連接拓撲。前者表示鏈路是否被LSP覆蓋，后者表示網絡中每個節點的連通性。在算法的過程中，覆蓋拓撲將不斷更新，但連接拓撲將保持不變。從第4行到第17行的循環中，我們使用動態規劃從圖中找出從源到任何終點(LER)的最佳路徑，該路徑能夠覆蓋最多的未覆蓋鏈路。然后，通過從第3行到第18行的循環，我們計算每個點的最佳路徑，并找到覆蓋當前圖中大多數鏈路的最佳路徑。每次我們計算出最優路徑后，我們根據最佳路徑刪除覆蓋拓撲中選定的鏈路，如第19行所示。當所有鏈路被LSP覆蓋時，算法停止(第20-21行)。

3 實驗仿真

在本節中，我們使用仿真實驗來評估所提出方法的性能。不失一般性，我們在仿真中使用n×n矩陣網絡拓撲，如圖5所示。

圖5 仿真實驗拓撲圖

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

圖6 不同路由數量下的流表數量

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

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

圖7 不同網絡規模下的流表數量

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

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

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

圖9 不同包長下的帶寬浪費比率

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

4 結 語

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