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

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

（1.南昌工程學(xué)院信息工程學(xué)院，江西 南昌 330099；2.江西省水信息協(xié)同感知與智能處理重點(diǎn)實(shí)驗(yàn)室，江西 南昌330099；3.常州大學(xué)機(jī)械與軌道交通學(xué)院，江蘇 常州 213164）

0 引言

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

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

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

1 相關(guān)工作

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

1.1 單純形法算法

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

線性規(guī)劃問(wèn)題可用公式（1）表示，它的目標(biāo)函數(shù)可使用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）來(lái)表示可行基，B的數(shù)量滿足 個(gè)，對(duì)應(yīng)的可行解不超過(guò) 個(gè)，j為可行基的下標(biāo)。若不滿足非負(fù)，則Bj為非可行基，操作停止；若滿足非負(fù)，則Bj為可行基，計(jì)算得到約束行列式的列系數(shù)，求解得非基變量的檢驗(yàn)數(shù)[8]，并依據(jù)檢驗(yàn)數(shù)的正負(fù)判斷公式（2）是否為當(dāng)前最優(yōu)解。

1.2 網(wǎng)絡(luò)模型

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

1.2.1 節(jié)點(diǎn)模型

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

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

1.2.2 鏈路模型

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

圖1 網(wǎng)絡(luò)鏈接圖

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

2 算法描述

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

2.1 路徑規(guī)劃算法

路徑規(guī)劃算法，顧名思義通過(guò)檢測(cè)、分析、計(jì)算得到LAN的最優(yōu)路徑以及備用路徑（多條），將有效路徑設(shè)置優(yōu)先級(jí)存并儲(chǔ)進(jìn)OpenFlow控制器，方便SFC在遇到網(wǎng)絡(luò)故障的情況下（自然災(zāi)害等）查找、調(diào)用網(wǎng)絡(luò)路徑，從而使故障網(wǎng)絡(luò)能夠快速恢復(fù)正常。

2.1.1 算法簡(jiǎn)介

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

2.1.2 參數(shù)設(shè)定

在SDN環(huán)境下的SFC中，三層模式下SFs的正常化通信，關(guān)系著SFC的推廣以及市場(chǎng)化。本文采用服務(wù)功能數(shù)量、源目地址作為算法參數(shù)，cost作為評(píng)估參數(shù)，以確保在基于單純形法的路徑算法下SFC能夠提供更高質(zhì)、安全、便捷、可靠的服務(wù)。

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

圖2 SFC中LLDP數(shù)據(jù)報(bào)傳輸

（2）源、目的地址，服務(wù)功能鏈（SFC）觸發(fā)后，通過(guò)接收其上、下行鏈路上的ARP報(bào)文來(lái)學(xué)習(xí)地址等相關(guān)信息；

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

對(duì)于傳輸過(guò)程以及存儲(chǔ)過(guò)程中因參數(shù)的缺失或遺失，本算法采用拉格朗日插值法[15]取參數(shù)的近似值，以降低算法的錯(cuò)誤，見(jiàn)式（4）。

2.2 故障路徑流量調(diào)度算法

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

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

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

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

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

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

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

3 實(shí)驗(yàn)驗(yàn)證與分析

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

圖3 SFC實(shí)驗(yàn)拓?fù)?/p>

3.1 動(dòng)態(tài)部署測(cè)試

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

圖5 動(dòng)態(tài)部署測(cè)試

3.2 路徑故障處理測(cè)試

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

圖6 路徑故障處理時(shí)間

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

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

3.3 鏈路cost測(cè)試

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

圖8 SFs和鏈路cost

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

圖9 (a) 在不同請(qǐng)求流量上部署實(shí)例

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

3.4 算法評(píng)估

為了評(píng)估3種算法面對(duì)故障的處理準(zhǔn)確率，其具體計(jì)算公式為：

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

表1 算法精準(zhǔn)度對(duì)比

4 結(jié)束語(yǔ)

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