針對有限TCAM的SDN網(wǎng)絡(luò)靈活局部路由故障恢復(fù)

孫宇 梁毅娟

摘 要： 在軟件定義網(wǎng)絡(luò)中，使用大量的備份路徑的轉(zhuǎn)發(fā)規(guī)則會頻繁地在交換機上進行數(shù)據(jù)流驅(qū)動，會增加帶寬需求和處理延遲。對此，開發(fā)一組問題優(yōu)化模型，可最小化備份路徑所需的額外規(guī)則和帶寬數(shù)量。由于該問題的計算復(fù)雜性，設(shè)計兩個啟發(fā)式算法計算備份路徑：前向局部路由（FLR）和后向局部路由（BLR），從而提高TCAM和帶寬的使用效率，并基于網(wǎng)絡(luò)狀態(tài)采用FLR和BLR設(shè)計了靈活自適應(yīng)故障恢復(fù)框架。最后，通過在Internet 2網(wǎng)絡(luò)拓撲上的仿真實驗，顯示所提算法在故障數(shù)據(jù)的抑制上要優(yōu)于選取的對比算法，驗證了算法性能優(yōu)勢。

關(guān)鍵詞： 軟件定義網(wǎng)絡(luò)； 局部路由； 內(nèi)容尋址存儲器； 交換機； 備份路徑； 故障恢復(fù)

中圖分類號： TN711?34； TP391 文獻標(biāo)識碼： A 文章編號： 1004?373X（2018）08?0013?04

Abstract： In software defined networks （SDNs）， the forwarding rule involving a large number of backup paths frequently drives data flow over a switch， which may increase the bandwidth requirement and result in processing delay. Therefore， a set of problem optimization models are developed to minimize the amount of extra rules and bandwidth required for backup paths. Two heuristic algorithms of forward local routing （FLR） and back local routing （BLR） are designed due to the computational complexity of the problem to compute backup paths so that the service efficiency of TCAM and bandwidth can be improved. A flexible adaptive fault recovery framework was designed based on network status by means of FLR and BLR. The simulation experiment on the Internet 2 network topology was carried out. The results show that the proposed algorithm outperforms the selected contrast algorithm in fault data suppression， and the performance advantage of the algorithm is verified.

Keywords： SDN； local routing； content addressable memory； switch； backup path； fault recovery

0 引 言

在傳統(tǒng)網(wǎng)絡(luò)中，交換機執(zhí)行路由決策（控制功能）和數(shù)據(jù)轉(zhuǎn)發(fā)（數(shù)據(jù)功能）。因其不支持可編程性，導(dǎo)致使用中存在等效網(wǎng)絡(luò)帶寬過度配置問題[1?2]。軟件定義網(wǎng)絡(luò)（SDN）已成為一種很有前途的網(wǎng)絡(luò)范式，它將控制功能和數(shù)據(jù)功能分離開來，從而使得交換機具有可編程性，網(wǎng)絡(luò)虛擬化成為可能。

為了進行路由決策，SDN依賴于在交換機中安裝的轉(zhuǎn)發(fā)規(guī)則。當(dāng)數(shù)據(jù)流包到達時，如果交換機沒有在其流程表中找到該數(shù)據(jù)流的任何規(guī)則，它將與控制器聯(lián)系。大型網(wǎng)絡(luò)如云數(shù)據(jù)中心網(wǎng)絡(luò)的活躍數(shù)據(jù)流的數(shù)量可達到每服務(wù)器每秒10 000數(shù)據(jù)流，開關(guān)TCAM的大小無法與之相適應(yīng)[3?4]。因此，提高TCAM的效率，即盡可能減少所需的TCAM數(shù)量，對于交通工程、故障管理、網(wǎng)絡(luò)安全等非常重要。雖然研究界探索了SDN的許多優(yōu)點，但對網(wǎng)絡(luò)故障恢復(fù)機制的關(guān)注較少[5?6]。網(wǎng)絡(luò)設(shè)備或鏈路故障導(dǎo)致包轉(zhuǎn)發(fā)的延遲，即使網(wǎng)絡(luò)中有替代路徑，從而影響應(yīng)用程序的性能，這可能導(dǎo)致供應(yīng)商的收入損失。在最近的研究中，谷歌[7]報告指出利用OpenFlow交換機配置會出現(xiàn)0.1%～1%之間的高延遲或傳輸失敗。

本文提出兩種算法，即前向局部路由（FLR）和后向局部路由（BLR）算法，計算可實現(xiàn)主路徑保護的備份路徑。該算法因為需要的TCAM很少，因此其可以忽略TCAM大小的影響。

1 SDN故障恢復(fù)的局部重路由

1.1 轉(zhuǎn)發(fā)規(guī)則和流程表

考慮到限位開關(guān)TCAM對于故障快速恢復(fù)的重要性，建議在動作設(shè)置列表（ACTION SET）中引入一個新的選項即Alternate_port（AP），如圖1所示。而Default_output_port指示數(shù)據(jù)包轉(zhuǎn)發(fā)到下一跳的沿主路上的輸出端口，Alternate_port將用于指示在相應(yīng)的鏈路失效的情況下，轉(zhuǎn)發(fā)數(shù)據(jù)包的輸出端口。其可以通過使用OpenFlow提供的開放接口Optimal action進行實現(xiàn)，也可以利用這個開放接口為存儲備份輸出端口添加額外的動作Alternate_port。

1.2 前向局部重路由

如果在主路徑上存在從故障點到另一下游交換機的多個備份路徑，則選擇最少附加交換機數(shù)量的備份路徑。通過附加開關(guān)，F(xiàn)LR顯著降低TCAM數(shù)量的原因：

1） 通過將數(shù)據(jù)從故障點路由到主路徑上的下游交換機，在主路徑上使用相同的轉(zhuǎn)發(fā)表規(guī)則，通過備份路徑將一部分數(shù)據(jù)包轉(zhuǎn)發(fā)到目的地。

2） 將備份通道上的附加交換機的轉(zhuǎn)發(fā)條目限制為一個，允許所有備份路徑通過附加交換機（對應(yīng)于主路徑的不同鏈路故障），并僅通過一個端口輸出，避免轉(zhuǎn)發(fā)循環(huán)并允許備份帶寬共享。

1.3 后向局部重路由

考慮圖2所示網(wǎng)絡(luò)拓撲，源節(jié)點S1和目的節(jié)點S5間主路徑是S1→S2→S3→S4→S5。當(dāng)S2和S3間的鏈接失敗時，在S2數(shù)據(jù)包報頭中設(shè)置標(biāo)志來標(biāo)記失敗數(shù)據(jù)流。標(biāo)志在S2處由空心變?yōu)閷嵭?。然后采取預(yù)先計算的到目的節(jié)點的不相交鏈路節(jié)點備份路徑，將此通信路由傳回S1，例如在S2處的失敗通信，將通過路徑S2→S1→S8→S9→S10→S5傳回目標(biāo)節(jié)點。

雖然BLR簡單，且復(fù)雜度低，但其在恢復(fù)中增加了額外延遲。當(dāng)S4和S5最后一跳鏈接失敗時，失敗通信須沿主路徑路由到源節(jié)點S1，則通過的備份路徑是S4→S3→S2→S1→S8→S9→S10→S5。在大型網(wǎng)絡(luò)中，鏈路越長情況越糟糕。此外，還需要在數(shù)據(jù)包頭部識別失敗數(shù)據(jù)流，將進一步增加路由延遲。

1.4 基于FLR的備份路徑設(shè)定

令[G=N，E]表示網(wǎng)絡(luò)拓撲圖，其中N是網(wǎng)絡(luò)交換機的節(jié)點集，E是交換機之間鏈路的邊集。使用“節(jié)點”和“開關(guān)”表示網(wǎng)絡(luò)交換機。利用W表示每個數(shù)據(jù)流計算的主路徑集，[Wf∈W]表示數(shù)據(jù)流f的主路徑。給定數(shù)據(jù)流f，其主路徑為[Wf∈W]，算法1可計算臨時備份路徑集，表示為Bff，從而實現(xiàn)對數(shù)據(jù)流f的每個鏈接[lf∈Wf]進行保護。該算法的輸入是網(wǎng)絡(luò)拓撲G和數(shù)據(jù)流f的主路徑[Wf]；算法的輸出是保護流f的備份路徑集Bff。

對于每個鏈接[lf∈Wf]，若其失效，首先確定遍歷最小數(shù)量額外節(jié)點的最好備份路徑，以保護低頻鏈路。令[Slf]為數(shù)據(jù)流f的轉(zhuǎn)發(fā)方向中的鏈接[lf]的來源。從[Slf]出發(fā)，該算法確定所有連接[Slf]的備份路徑，每個[Slf]主路徑上的下游節(jié)點為[Wf]，[Dlf]為[Slf]的下游節(jié)點集。算法1中第5行表示節(jié)點之間的最短路徑。輸出結(jié)果為鏈接[Slf]和下游節(jié)點[Dlf]的備份路徑[Btemplf]。然后將這條路徑添加到保護鏈路[lf]的備份路徑集中，表示為[Blf]。

2 實驗分析

實驗平臺為CPU i7?6400k、RAM 8 GB DDR4?2400、系統(tǒng)WIN7旗艦版。測試對象是Internet 2網(wǎng)絡(luò)拓撲。所有結(jié)果用95%置信區(qū)間繪制。對比算法如下：

1） 基于備用端口的FLR算法（FLR?AP）；

2） 基于備用端口的BLR算法（BLR?AP）；

3） 文獻[8]基于子樹的組播故障檢測與保護方法（SBFD）。

考慮一個邊連通概率為0.6，具有30個節(jié)點的隨機圖。假設(shè)網(wǎng)絡(luò)中所有鏈路都有1 000個帶寬單元。每個數(shù)據(jù)流產(chǎn)生的帶寬要求是均勻分布在0～20之間的隨機數(shù)。在帶寬有限情況下，F(xiàn)LR?AP，BLR?AP和本文算法的附加規(guī)則的數(shù)量均值指標(biāo)的對比結(jié)果如圖3所示。圖4顯示了在鏈路發(fā)送故障時，數(shù)據(jù)到達目的地所需的平均額外跳數(shù)均值。

根據(jù)圖3指標(biāo)對比情況可知，本文算法所需要的附加規(guī)則的數(shù)量均值要比FLR?AP算法低30%左右。原因是，本文算法對流量的優(yōu)先保護順序是首先利用FLR備份路徑，然后采用BLR備份路徑，最后無保護，這種故障恢復(fù)方法更加靈活。同時，因為BLR?AP算法需要的額外規(guī)則數(shù)量最少，因此降低了本文算法所需的額外的規(guī)則數(shù)，要優(yōu)于SBFD算法。但是BLR?AP算法的缺點是會增加一定的傳輸延遲，并且需要增加故障標(biāo)記位。根據(jù)圖4結(jié)果可知，在數(shù)據(jù)流較低時，本文算法與FLR算法和BLR算法在平均額外跳數(shù)均值指標(biāo)上相差不大。但是隨著數(shù)據(jù)流的增加，BLR算法的平均額外跳數(shù)均值指標(biāo)增加非常迅速，而FLR算法的平均額外跳數(shù)均值指標(biāo)增加最為緩慢，本文算法居中。原因在于當(dāng)流量增加時，F(xiàn)LR的備份路徑不可用，因此選擇BLR備份路徑實現(xiàn)對數(shù)據(jù)流的保護。實際上，本文算法所需的額外跳數(shù)均值要比BLR算法少25%左右，優(yōu)于SBFD算法。

此外，還對隨機圖上的算法的帶寬效率進行評估。圖5給出4種算法使用的總帶寬對比情況。圖6給出4種算法的不可用數(shù)據(jù)抑制比指標(biāo)對比情況，

可觀察到，F(xiàn)LR，BLR和本文算法的備份路徑的帶寬共享效率分別為80%，55%和70%。其中FLR算法的帶寬使用情況最佳。結(jié)果顯示，本文算法在此指標(biāo)上優(yōu)于SBFD算法。由圖6結(jié)果可知，利用本文算法的不可用數(shù)據(jù)抑制比可實現(xiàn)大幅降低。因此，對于帶寬受限網(wǎng)絡(luò)，當(dāng)可對延遲和TCAM進行權(quán)衡時，本文算法可以接收更多的數(shù)據(jù)流，從而提高網(wǎng)絡(luò)的傳輸效率。

3 結(jié) 語

本文通過從單一鏈路故障的備份路徑限制開關(guān)TCAM進行數(shù)據(jù)流保護流的軟件定義網(wǎng)絡(luò)的容錯性問題。首先定義一個優(yōu)化問題，在備份路徑中進行最優(yōu)解求取，最大限度地減少備份鏈路的帶寬要求和TCAM組合成本。同時開發(fā)一個高效的局部重路由方法，考慮開關(guān)記憶約束TCAM的SDNS快速故障恢復(fù)。使用這種方法，本文開發(fā)了兩種算法即FLR和BLR，有效解決了備份路徑數(shù)據(jù)流保護過程中的SDN交換機TCAM的大小約束問題。

注：本文通訊作者為梁毅娟。

參考文獻

[1] LEI Ding， WEI Xingzheng. Network?based practical consensus of heterogeneous nonlinear multi?agent systems [J]. IEEE transactions on cybernetics， 2017， 47（8）： 1841?1851.

[2] KOBAYASHI K， HIRAISHI K. Design of probabilistic Boolean networks based on network structure and steady?state probabilities [J]. IEEE transactions on neural networks &； learning systems， 2017， 28（8）： 1966?1971.

[3] YANG E Z， ZHANG L K， YAO Z， et al. A video conferencing system based on SDN?enabled SVC multicast [J]. Frontiers of information technology &； electronic engineering， 2016， 17（7）： 672?681.

[4] HUANG T， YU F R， ZHANG C， et al. A survey on large?scale software defined networking （SDN） testbeds： approaches and challenges [J]. IEEE communications surveys &； tutorials， 2017， 19（2）： 891?917.

[5] LOPES F A， SANTOS M， FIDALGO R， et al. A software engineering perspective on SDN programmability [J]. IEEE communications surveys &； tutorials， 2016， 18（2）： 1255?1272.

[6] NGUYEN V G， DO T X， KIM Y H. SDN and virtualization?based LTE mobile network architectures： a comprehensive survey [J]. Wireless personal communications， 2016， 86（3）： 1401?1438.

[7] KANG S， YOON W. SDN?based resource allocation for heterogeneous LTE and WLAN multi?radio networks [J]. Journal of supercomputing， 2016， 72（4）： 1342?1362.

[8] RAJA V R， LUNG C H， PANDEY A， et al. A subtree?based approach to failure detection and protection for multicast in SDN [J]. Frontiers of information technology &； electronic engineering， 2016， 17（7）： 682?700.

[9] BHOLEBAWA I Z， JHA R K， DALAL U D. Performance analysis of proposed openflow?based network architecture using mininet [J]. Wireless personal communications， 2016， 86（2）： 943?958.

[10] SIQUEIRA M A， HOOFT F N， OLIVEIRA J R， et al. Providing optical network as a service with policy?based transport SDN [J]. Journal of network and systems management， 2015， 23（2）： 360?373.