服務功能鏈中基于單純形法的路徑規(guī)劃算法

居 翔，李沛武，王 奇，韓 飛，章榮輝

（1.南昌工程學院信息工程學院，江西 南昌 330099；2.江西省水信息協同感知與智能處理重點實驗室，江西 南昌330099；3.常州大學機械與軌道交通學院，江蘇 常州 213164）

0 引言

隨著網絡技術的迅速發(fā)展，互聯網產品也越來越豐富，其逐漸融入人類的衣食住行，成為學習、工作、生活不可或缺的一部分。2020年新冠疫情席卷全球，為避免因人員聚集而引起病毒擴散，各大中小學將課堂從線下搬到了線上、研究生復試也由傳統(tǒng)形式改為網絡視頻復試……這使得網絡安全益發(fā)重要，一旦網絡出現故障，網絡通信就會受到影響，輕則網絡跌宕，重則網絡癱瘓。傳統(tǒng)鏈路下網絡故障處理的成本較高，如2011年日本東北地區(qū)發(fā)生了地震，該地區(qū)大部分信號基站停運，網絡歷時7天才被恢復[1]，流量報文解析速率是正常周期的1.8倍[2]，期間各大運營商、設備商調用大量運維人員、庫存設備等資源；此外，用戶所在園區(qū)網的通暢還需人工排故等。因而，降低網絡不可達故障對用戶的影響一直以來都是網絡工程師的追求。

目前，解決這一系問題潛在的方案有網絡功能虛擬化（Network Fuctions Virtualization，NFV）和軟件定義網絡（Software Defined Network，SDN）。NFV通過一系列軟件將網絡功能虛擬化，在NFV框架中運行網絡功能。NFV減少運維商在設備配置方面的開銷、縮短網絡服務部署周期、簡化了系統(tǒng)管理難度、動態(tài)實現網絡服務擴展、提升了通信系統(tǒng)的靈活性；但NFV目前需要對網絡的延遲、吞吐量、處理開銷、安全性、穩(wěn)定性、平臺復雜等方面作出提升[3]。SDN框架的核心思想在于將數據平面與管理平面分離[4]，使網絡可拓展性、部署的便捷性突出，其逐漸被廠商接受，成為新一代的網絡框架?；赟DN框架的網絡功能服務鏈（Service Function Chain，SFC），采用OpenFlow協議實現數據層與控制層的通信，將底層網絡通信設備有機地整合，合理分配資源，提高網絡的效率。SDN框架把網絡當成一個資源池，對其展開協調調度，提升網絡利用率[5]。SFC能夠對網絡進行靈活編排、部署、割接，從而使網路的管理基于管理員的意志，為用戶提供高質量的網絡服務。

由于TCP/IP模型中的三層（Internet層）多故障、延時、易丟包等缺點（IP協議不靠譜），使得SFC在路由模式（Routering Model，RM）面臨一些挑戰(zhàn)。主要體現在：動態(tài)部署、路徑規(guī)劃、三層節(jié)點跌宕方面。需要解決這些問題需，才能發(fā)揮SFC的智能管理功效。鑒于此，本文提出基于單純形法的路徑規(guī)劃算法來解決SFC在RM模式下的路徑規(guī)劃（Path Planning，PP）問題，增強SFC的流量調度處理能力，提高其最優(yōu)選路速度，提升SDN網絡的智能性。

1 相關工作

線性規(guī)劃（Liner Programming）是運籌學、決策科學和管理科學最重要的基礎，現在已經成為人們合理利用、調配有限資源并作出最佳決策的有力工具[6-7]。隨著科學技術的快速發(fā)展，一般線性規(guī)劃已經不能滿足工程人員對工程問題的低消耗、高回報的要求，因此對項目最優(yōu)化也應運而生。由于網絡路徑問題的變量和約束的數量不是很大，因而有很多算法可以有效得到最優(yōu)解，例如單純形法。單純形法作為線性規(guī)劃的最優(yōu)化方法之一，在工程項目中實施的過程中起到了決定性作用。下面我們將對單純形法以及NP模型作出簡單的介紹。

1.1 單純形法算法

單純形法算法（Simplex Algorithm）由丹西格于1947年提出，是一種解決線性規(guī)劃問題的有效方法[8-9]，它的原理：把線性規(guī)劃問題的解的可實施部分看作一個n維向量空間中的凸集，單純形法能夠找到可形基與可行解，且能夠判斷其是否為最優(yōu)解；若不是最優(yōu)解，則尋找下一個更優(yōu)的可行基和基本可行解。

線性規(guī)劃問題可用公式（1）表示，它的目標函數可使用min（也可以使用max），其約束條件表示為Ax=b。單純形法中，約束矩陣A可表示成m×n的矩陣，A=（p1，p2…pm），b=（b1，b2…bn），C=（c1，c2…cn）。采 用B=（p1，p2，…，ps）（s＜m）來表示可行基，B的數量滿足 個，對應的可行解不超過 個，j為可行基的下標。若不滿足非負，則Bj為非可行基，操作停止；若滿足非負，則Bj為可行基，計算得到約束行列式的列系數，求解得非基變量的檢驗數[8]，并依據檢驗數的正負判斷公式（2）是否為當前最優(yōu)解。

1.2 網絡模型

為降低網絡開銷成本，本文以網絡程序模型（Network Program，NP）基采用F=（V，E）機制來獲取網絡實時流量狀態(tài)，其中，頂點V對應行（約束或網絡節(jié)點的集合），E對應邊緣響應列（變量或網絡中的有向邊緣設備）。系數矩陣A的行由服務功能鏈（SFC）中的服務功能（SFs）決定，列由SFs三層模式（RM）下的路由表決定。如果F是n（n＞0）個SFs（節(jié)點）的鏈接有向圖，則表明它的列不依賴于線性，所以但是由于將A的所有行相加，最后將NP轉化為線性規(guī)劃問題，具有以下特征：每一列的系數都有一個1其形式也可使用公式（1）所示，其中，和一個-1，剩下的系數都是0；m表示約束的數量，n表示變量的數量；行由節(jié)點（SFs）的數量決定。

1.2.1 節(jié)點模型

在SFC中，SFs的狀態(tài)分別為“Up”“Down”（分別對應二進制1、0），我們將其建成一個元組Node（id，Nstate，Nset）。其中，id表示SFs的序列號，Nstate表示SFs的狀態(tài)，Nset表示相鄰的兩個節(jié)點之間Edge的集合。

OpenFlow控制器通過OpenFlow協議在SFC中收集各個SFs的信息，并將響應的信息分析并存儲在列表。節(jié)點狀態(tài)為“Up”，轉換為數值1；節(jié)點狀態(tài)為“Down”，轉換為數值0。由于SFC中SDN交換機的端口分為：常用端口和特殊端口；常用端口為與交換機、路由器、防火墻等設備相連接的設備，在設備未啟動的狀態(tài)下，SDN對應端口無法通過數據流，則狀態(tài)為0；特殊端口為特殊服務如鏡像、監(jiān)控等端口，此類端口需要實時監(jiān)控網絡流量狀態(tài)，因而其狀態(tài)必須為1。

1.2.2 鏈路模型

由于SFC的上、下行鏈路以及SFs的上、下行鏈路的通信方式都可選為全雙工模式，因而本文對網絡鏈路抽象成有向連接圖（見圖1），每一條邏輯鏈路對應一條相應的有向 表示，其中，id表示Edge的序號，s表示Edge的源SFs，d表示Edge的目的SFs，cn表示鏈路的開銷，ln表示容量下限，un表示容量上限，bn表示總流量，bw為Edge的帶寬，rw表示Edge的剩余帶寬?？蓪D2描述為：每一個變量（Edge）xj是沿著第j個邊緣設備發(fā)送的Flow；發(fā)送1單位Flow的cost是cj；流不能超過容量uj，必須有一個最小流lj（最小流通常為0）；頂點i處的總流量是由bi所決定。因此，網絡流量的求解就是沿著圖尋找可行流程，使cost最小化。節(jié)點設備R1、R2、R3的有向邊Edge表示為x1、x2、x3、x4，其對應的總流量bi由花括號中的5、0、-5；中括號中的元素對應cj、lj、uj。

圖1 網絡鏈接圖

將鏈路的路徑表示為 ，路徑周期如式（3）所示，其中，ae是e在頂點邊緣射入矩陣A的列，ev是第v個單位向量（除了束引v處的1外，所有為0）。

2 算法描述

本文提出RM模式下SFC的基于單純形法的路徑規(guī)劃算法采用了單純形法、NP模型，它能夠籌劃SFC在RM模式下的網絡流量的路徑，即通過檢測獲取網絡流量的數據報頭部的源和目的地址、服務功能（SFs）的數量進行計算，并采用遍歷比較cost從而獲取最優(yōu)路徑。對于算法的參數，選取5個自適應的參數。自適應是指根據算法的演化狀態(tài)動態(tài)地更新算法各策略中用到的關鍵參數以及恰當地進行策略的調用、轉換和設置[10-11]。算法啟動時需要同時開啟2個線程，一個用于檢測、規(guī)劃路徑如算法1所示，另一個用于發(fā)生故障為處理故障爭取時間的流量調度（Traffic Schedule， SHC）如算法2所示。

2.1 路徑規(guī)劃算法

路徑規(guī)劃算法，顧名思義通過檢測、分析、計算得到LAN的最優(yōu)路徑以及備用路徑（多條），將有效路徑設置優(yōu)先級存并儲進OpenFlow控制器，方便SFC在遇到網絡故障的情況下（自然災害等）查找、調用網絡路徑，從而使故障網絡能夠快速恢復正常。

2.1.1 算法簡介

普遍而言，使用蠻力法解決網絡問題是最簡單的方法，但蠻力法的成本較高，后期可擴展性較差；而貪心算法核心是用最小的代價，獲取最大利潤[12]。此外，貪心算法處理事件速率是非常迅速的，可以用在線性規(guī)劃問題中[13]。因而，為了減少跳躍贅余的節(jié)點，我們開發(fā)了一種多路徑、快速替換的路徑規(guī)劃算法。該算法對流量集進行最優(yōu)化分析與計算，從而得到損耗最小的三層模式（RM）路徑，具體步驟如算法1：①SFC采集并提取SDN網絡中流量的SFs和連接在SFs上Edge的數量，將其放入SFC的數據庫中，遍歷輸入量使其初始化，使其通過NP模型映射于單純形法的約束變量，尋找輸入量的可行基B，計算B-1、B-1b、CTBB-1b，其中Nnode、nedge分別表示SFs（或節(jié)點）數量、邊緣設備的數量；②計算路徑的成本（即單純形法的最優(yōu)解），計算則返回最優(yōu)值，否則令dq＜0的情況下計算；③接下來，計算測試比例，判斷是否綁定；④存儲單純形法的最優(yōu)、次優(yōu)值；⑤更新數據庫中的路徑；⑥輸出最優(yōu)路徑。

2.1.2 參數設定

在SDN環(huán)境下的SFC中，三層模式下SFs的正?；ㄐ?，關系著SFC的推廣以及市場化。本文采用服務功能數量、源目地址作為算法參數，cost作為評估參數，以確保在基于單純形法的路徑算法下SFC能夠提供更高質、安全、便捷、可靠的服務。

（1）Node數量、Edge數量，可通過SFC向鏈路發(fā)送LLDP數據報進行網絡檢測，獲取網絡的網元設備狀況信息而得知；具體過程如圖2所示：①OpenFlow控制器向SDN交換機發(fā)送Packet_Out消息（含有LLDP數據包），來檢測服務功能鏈（SFC）的服務功能（SF）以及設備。SDN交換機將LLDP幀添加到Packet_In消息中，然后發(fā)送給OpenFlow控制器[14]。OpenFlow控制器依據接收到的Packet_In消息（LLDP幀），構建用于網絡拓撲檢測的數據庫。②服務功能（SFs）由控制器實時管理，以確保為網絡提供持續(xù)、穩(wěn)定、可靠的服務。

圖2 SFC中LLDP數據報傳輸

（2）源、目的地址，服務功能鏈（SFC）觸發(fā)后，通過接收其上、下行鏈路上的ARP報文來學習地址等相關信息；

（3）cost，由于其是OSPF協議選路的重要參考度量，因而將其用于用于檢測單純形法的路徑是否最優(yōu)；

對于傳輸過程以及存儲過程中因參數的缺失或遺失，本算法采用拉格朗日插值法[15]取參數的近似值，以降低算法的錯誤，見式（4）。

2.2 故障路徑流量調度算法

在SDN網絡中，在SFC上動態(tài)部署、下線服務功能（SFs）或服務功能組（SFG），調度網絡流量成為了非常重要的問題。流量調度是一個NP-hard問題，即使使用一些啟發(fā)式算法，獲得接近最佳的調度方案也非常耗時[13]。當下主流的協調調用方法共同優(yōu)化NFV中的資源分配（Jointly Optimize the Resource Allocation in NFV，JoraNFV），其主要方向在運營成本和鏈路消耗的混合型整數線性規(guī)劃調用，其一般運用于大型運營商網絡，對于園區(qū)網的本地局域網（LAN）而言其代價太高。將SFs的下一跳可以視為線性規(guī)劃問題，盡管它不能保證全局流量調度是最佳解決方案，但其能夠將下一跳調度性能作為衡量SFC的性能指標[16]，可以使用單純形法來解決該問題。本文的故障路徑流量調度算法基于故障SFs流量的數據報文進行流量處理，其消耗成本較低。

SFC在SDN網絡的三層模式下，檢測到SFs下線（由斷電、人為下線等引起故障），此時流經下線SFs的流量需要被調度，以保持網絡的穩(wěn)定性，同時為備用路徑的啟用預留反應時間。故障SFs流量調度算法具體步驟如下：

Step1：將途徑流量的IP數據報頭部字段、故障SFs的物理地址映射到算法中，其中msrc、Mdst、isrc、Idst分別表示源Mac地址、目的Mac地址、源IP地址、目的IP地址，將點分十進制的IP地址初始化轉換成十六進制，并使用列表存儲。

Step2：將轉換成十六進制的目的IP地址分別存入新生成的偽地址（）的0-3號，將SFC的ID號轉換成十六進制作為4號元素，最后將本算法的代號H7（次數作為參考數據）作為5號元素。

Step3：當SFC檢測到其SFs發(fā)生故障并停止工作時，途徑SFs去往邊緣設備的流量報文急需處理，此時故障路徑流量調度將偽MAC地址封裝進報文的目的MAC地址，得到ARP響應報文，使得SFs（處于故障狀態(tài)）的上、下行鏈路通暢。

Step4：待路徑規(guī)劃算法的備用路徑啟動后，若備用路徑正常則調度算法將偽Mac地址更改成真實的備用SFs的端口Mac，通過Packet_In消息發(fā)送給OpenFlow控制器；若備用路徑故障，返回執(zhí)行Step2。

Step5：OpenFlow控制器向SDN交換機下發(fā)啟用備用路徑的流表。

3 實驗驗證與分析

在本節(jié)中，我們著重介紹實驗環(huán)境和最終的性能評估。為了測試基于單純形法的路徑規(guī)劃算法，將其與JoraNFV算法、傳統(tǒng)網絡做對比實驗。首先，我們在SDN網絡中搭建SFC環(huán)境以及搭建傳統(tǒng)網絡鏈路。之后，為了檢驗動態(tài)部署、三層節(jié)點跌宕引發(fā)的路徑故障，我們通過在網絡中的添加、刪除網元設備（節(jié)點）。SFC實驗拓撲如圖3所示，定義了SFs在SFC環(huán)境中的流量上、下行鏈路，將SFs部署為三層模式，以便于網絡流量在SFC上流通。傳統(tǒng)網絡環(huán)境實驗拓撲如圖4所示。

圖3 SFC實驗拓撲

3.1 動態(tài)部署測試

傳統(tǒng)網絡由于數據層平面與鏈路層平面的深度耦合，其網絡拓撲一經搭建，不易動態(tài)調整[17]，無法捕獲網絡演化趨勢[18]，也無法智能編排。服務功能鏈由于其高效、可編排等優(yōu)點，可實現快速自動部署[14]；尋找網絡節(jié)點間聯系，適應網絡實時變化，生成更精確的網絡表示[18]。下面通過對SFC進行動態(tài)部署服務功能（SFs），將本文算法與JoraNFV算法、傳統(tǒng)網絡算法面對此類情況下引起故障做對比。如圖5所示，PC機在訪問百度的服務器時，通過追蹤PC機所在的服務功能上動態(tài)添加網元設備，對比3種算法的每分鐘內千條請求通過節(jié)點所耗時間可知：隨著動態(tài)添加節(jié)點設備數量的增加，三層模式下的傳統(tǒng)算法無法在短時間內處理轉發(fā)數據包；JoraNFV隨著添加節(jié)點數量的增加，其對添加節(jié)點的新路徑轉發(fā)數據報的能力下降；基于單純形法的路徑規(guī)劃算法相比JoraNFV而言，其對動態(tài)部署節(jié)點設備更加友好，能大量添加網元設備，耗時0.5s內。

圖5 動態(tài)部署測試

3.2 路徑故障處理測試

為了展示基于單純形法的路徑規(guī)劃算法處理路徑故障的能力，我們對服務功能進行下線或斷電。使用ping、tracert等請求命令來探索網絡流量途徑下線的服務功能設備（導致鏈路故障）時數據報文是否可達以及顯示處理網絡不可達節(jié)點時使用時間，本算法與JoraNFV、傳統(tǒng)網絡算法進行比較，其結果如圖6所示：隨著故障路徑數量的增加，三種處理故障方法所消耗的間也隨之增加。傳統(tǒng)網絡鏈路，一旦遇到鏈路上的網元設備下線，途徑網絡的數據流將陷入不可達狀態(tài)；無法智能處理，需要手工重啟網元設備并配置命令，時間成本較高，與此同時，隨著路徑故障數量增多，其消耗時間大幅上升；JoraNFV方法在處理路徑故障時其消耗時間上升率較穩(wěn)定；單純形法的路徑規(guī)劃算法面對大量路徑故障時由于其流量調度子算法為其節(jié)約時間，在面對大量路徑故障時其消耗時間降（40秒內），較JoraNFV有優(yōu)勢。

圖6 路徑故障處理時間

傳統(tǒng)網絡鏈路路徑故障處理與JoraNFV、單純形法算法的路徑故障處理的最優(yōu)率對比如圖7所示。

圖7 故障處理的最優(yōu)率對比圖

3.3 鏈路cost測試

接下來，我們將重點討論SFC的SFs上鏈路（上、下行）的cost實驗。如圖8所示，我們繪制了部署SFs的數量以及標注了鏈路Edge的cost。SF1、SF2上部署了實例Router3、Router4、Router5，SF1有50單元流量，SF2有40單元流量，這些流量需要被調度到3個實例中，由于每條鏈路的傳輸延遲和轉發(fā)時間都不同，從而產生了鏈路cost（公式5）。傳統(tǒng)鏈路算法、JoraNFV和單純形法算法對不同請求的轉發(fā)執(zhí)行機制是一致的；鏈路的cost在遇到請求量較大的通信數據流，在鏈路上部署更多網元設備時會話質量會下降。

圖8 SFs和鏈路cost

基于圖8實驗環(huán)境，圖9中請求的流量數據量設置為5、10、15、20個單位，分別表示為T5、T10、T15、T20。圖9（a）描述在不同請求流量部署實例（WAF、FireWall、IPS、Qos等）的數量，圖9（b）表示不同請求流量的鏈接成本?？紤]到鏈接成本和部署實例，不同的請求流量在3種算法在上執(zhí)行方法上是相同的。它表明，隨著Traffic請求量增大、部署的實例增多時，傳統(tǒng)網絡鏈路方法的性價比會變得更差，這會導致網絡資源的分散；單純形法的路徑算法與JoraNFV算法也存在差異，當請求流量達到T5時，基于JoraNFV的算法性能高于單純形法算法；但請求量超過T5時，單純形法算法其在相同請求流量時的實例部署隨著請求流的增加而成本趨于最低且能夠部署的實例最多，綜合性能高于JoraNFV。

圖9 (a) 在不同請求流量上部署實例

圖9 (b) 在不同請求流量上的鏈路cost

3.4 算法評估

為了評估3種算法面對故障的處理準確率，其具體計算公式為：

式中，Nnode表示節(jié)點的數量；Na表示節(jié)點的可達數量；p表示算法的精確度；cost表示網絡鏈路的開銷。對比的結果如表1所示，由表1實驗結果可知，在同類型的流量請求等數量節(jié)點中在面對網絡不可達時，傳統(tǒng)網絡鏈路算法的可達節(jié)點數量伴隨著請求類型過節(jié)點數量的增加而其節(jié)點的可達性大幅降低，算法的準確率中等；JoraNFV算法在服務功能數量增幅時，其節(jié)點的可達性、算法的準確率較穩(wěn)定；基于單純形法的路徑規(guī)劃算法在面對不同類型請求跳躍節(jié)點時，通過故障路徑的流量調度保持了節(jié)點可達性和算法高精確率。

表1 算法精準度對比

4 結束語

本文提出的基于單純形法的路徑規(guī)劃算法，解決了SDN服務功能鏈SFC在三層模式下，服務功能的動態(tài)部署、割接、下線引發(fā)網絡不通暢問題。在本文算法中，在SFC啟動時，SDN交換機轉發(fā)服務功能的ARP請求報文，OpenFlow控制器學習SF的真實MAC并生成偽MAC，下發(fā)給SF[19]；本文算法通過將流量牽引到偽MAC，為SFC的路徑替換爭取時間，并保障更改時間段內網絡通暢。最后，與JoraNFV、傳統(tǒng)網絡鏈路算法進行對比實驗。結果表明，單純形法算法能夠有效地解決SFC由動態(tài)添加節(jié)點、三層網元跌宕、節(jié)點下線及斷電產生的路徑故障，進一步提高了SFC的安全性、集成性、靈活性。從性價比方面講，單純形法算法相比Bypass等硬件設備，能夠節(jié)約網絡建設、改造的成本；相比JoraNFV、傳統(tǒng)網絡算法，其可擴展性強、處理速度快、穩(wěn)定性強。因而，接下來的研究是進一步深入探索出SDN的轉發(fā)圖嵌入（SDN Forwarding Graph Embedding），并進一步提高算法的準確性和智能性。