面向并發業務的衛星網絡服務功能鏈優化算法

潘成勝，梁芷銘，石懷峰，3，孔志翔，3

（1.大連大學通信與網絡重點實驗室，遼寧大連 116622；2.大連大學信息工程學院，遼寧大連 116622；3.南京理工大學自動化學院，南京 210094）

0 概述

隨著互聯網的快速發展，我國網民數量截至2019年6 月已突破8 億［1］。由于我國通信設施建設水平處于國際領先地位，且衛星發射數量逐年增多，目前衛星在軌數已超過200顆，而傳統衛星網絡設計完成投入使用后，其硬件升級更新迭代的成本巨大，難以滿足提升衛星性能與降低升級難度與成本的網絡需求。文獻［2-3］通過將傳統衛星網絡與網絡虛擬化技術相結合，從硬件中解耦出各種網絡功能需求，以解決衛星上硬件模塊更新困難的問題。為增強這種抽象虛擬化對衛星的改進，相關研究認為服務功能鏈（Service Function Chain，SFC）可以更好地提升空間信息網絡性能，即衛星將接收到的服務請求中所用到的模塊功能抽象為虛擬網絡功能（Virtual Network Function，VNF），并將其串聯起來編排為一個有序的鏈式集合構成服務功能鏈。

目前，針對SFC 的編排可分為構建與映射2 個步驟。在構建過程中將接收到的服務請求按照既定的策略進行處理，而在映射過程中則需要考慮以下3 種情況：從通信資源方面考慮，需要最小化傳輸鏈路與衛星間及層間的跳數；從內存及計算資源方面考慮，由于衛星負載及處理能力有限，需要合理利用衛星上的資源；從鏈路健壯性方面考慮，應有效解決衛星節點動態失效問題［4-5］。文獻［6］提出一種禁忌搜索算法的SFC 部署算法，通過設置禁忌表在全網中搜索服務功能最優的部署位置，但該算法僅考慮了資源利用率情況。文獻［7］采用一種面向VNF 環境的服務功能管理機制，主要通過維特比算法在候選節點中選擇部署開銷最小的服務功能，以降低部署成本，但該方法缺乏對通信資源消耗的考慮。

然而，以上研究未能對通信資源、計算資源消耗進行整體優化。針對該問題，本文構建一種適用于空間信息網絡的抽象模型。該模型在空間信息網絡中動態拓撲形成快照的基礎上，利用流量縮放因子及VNF 間的相互依附關系對服務請求構建出合理的SFC。為解決SFC 映射過程中產生的隨機失效、路由規劃不合理以及資源實例碎片化等問題，本文提出一種最小資源消耗映射算法，以最小資源消耗為目標形成SFC 映射路徑，最終得到SFC 構建與映射間的最優解決方案。

1 空間信息網絡拓撲模型

本文提出一種基于服務功能鏈映射的空間信息網絡抽象模型，具體如圖1 所示。中地球軌道（Medium Earth Orbit，MEO）層具有工作壽命長與仰角度良好等特點，在空間信息網絡的構成中發揮重要作用。將在MEO 層通信范圍內的低軌衛星稱為在足印以內，選擇一顆在低地球軌道（Low Earth Orbit，LEO）層中覆蓋時間最長的MEO 衛星成為控制者，起到控制與轉發功能，一顆MEO 層衛星可與足印范圍中的LEO 層衛星形成集群并加以管控［8-10］。但由于空間信息網絡的高動態特性，MEO 層衛星所在的足印區域內LEO 衛星會發生變化，導致MEOLEO 間的集群關系發生改變。因為同步地球軌道（Geostationary Earth Orbit，GEO）層具有對地靜止的特性，且模型中所有衛星節點均對其可見，所以其可作為制定決策的控制者對網絡整體進行管控，并對鏈路中出現MEO-LEO 的集群改變進行調整，以保證服務請求質量。這種分布式管控模型可有效緩解頻繁調用GEO 造成傳輸時延增大所帶來的缺陷，同時也保證了整個通信環境的穩定性。

圖1 空間信息網絡抽象模型Fig.1 Abstract model of spatial information network

本文提出的空間信息網絡抽象模型工作流程如下：

步驟1當GEO 層收到服務請求后，為降低衛星上資源碎片化的消耗對其進行拆分處理，抽象成一連串的有序SFC 并形成流表，準備下發到LEO/MEO 層衛星以響應服務請求。

步驟2在GEO 層上生成的流表下發到各MEO-LEO 集群中并利用MEO 進行調配，按照流表策略在相應衛星上虛擬出所需功能，以完成映射任務。其中：MEO 衛星負責轉發與LEO 的調配工作，針對衛星間的高動態性，若在某一時刻下的快照中衛星的生命周期不滿足服務需求（LEO 即將脫離MEO 的足印區域），則需要MEO 關注并調配當前LEO 周圍的其他LEO 對服務功能角色進行補充；若當前MEO 衛星足印中沒有可以滿足服務的LEO 衛星，則向GEO 衛星發出申請，并查找其他可部署的MEO-LEO 集群以滿足服務請求。

步驟3LEO 接收到指令后按照流表要求完成SFC 映射以響應服務請求。流表需要安全、穩定以及可靠的約束條件，先保證鏈路的穩定性，再考慮資源消耗以及傳輸效率的情況。

2 服務功能鏈的編排

服務功能鏈的提出是為了提供一個靈活、功能配置可拓展、面向對象與可重構的一種網絡服務［11］。本文提出的SFC 編排設計思路如下：首先以流量縮放因子與VNF 之間的相互依附關系為約束原則，以降低衛星上以及衛星間通信資源開銷為目標對SFC進行構建，為SFC 映射找到最小資源開銷路由策略奠定基礎；其次考慮到星上拓撲的高動態性，采用基于A*算法的本文算法進行SFC 映射，匹配出可得到最小資源開銷的路由策略。

2.1 虛擬網絡功能的流量縮放因子及依附關系

隨著VNF 技術的逐漸成熟，一些功能從硬件實現中解放出來以節約迭代升級成本，實現通過軟件定義的方式處理業務需求逐漸成為一種發展趨勢［7］。在執行網絡請求處理的過程中，一條服務請求對應一條SFC，而每條SFC 由源節點、有序的VNF以及目的節點組合而成。若要處理一條SFC 請求，則需通過相應網絡資源構建出這些虛擬功能模塊，再按照一定的策略映射到網絡當中，才能保證提供可靠而穩定的服務［12-14］。

虛擬網絡功能基于其特性按照一定的比率放大或縮小經過的數據流，本文稱其為流量縮放因子ω。在此假設一個前提：為了避免流性能的退化，不可將流拆分成多條進行傳輸。

圖2 說明了流量縮放因子對構建SFC 的影響。其中：S與D分別為源節點與目的節點，M1、M2、M3均為空間信息網絡中的衛星節點；N1與N2為抽象出的VNF，N1的流量縮放因子為2，即由其功能屬性會導致經過的數據流放大2 倍，N2的流量縮放因子為0.5，則會使經過的數據流縮小1/2，空心圓圈表示該衛星節點僅作為跳轉節點未使用虛擬功能；服務請求為a個單位的數據流大小，橫向箭頭表示鏈路，縱向箭頭表示生成抽象，鏈路上數字表示當前鏈路中的數據流大小。從圖2 可以看出，通過分別將流量縮放因子較大的VNF 與縮放因子較小的VNF 放在構建的服務功能鏈末尾與鏈首，可降低傳輸過程中帶寬資源的壓力。與此同時，還需考慮到在SFC 構建時VNF 間的相互依附關系，需將有上下文聯系的VNF放在一起考慮，比如加密與解密是不可調換順序的功能，不能為降低通信資源壓力而破壞這種相互依附關系。因此，整體關注SFC 的構建可達到降低鏈路通信資源開銷的目的。

圖2 流量縮放因子對帶寬的影響Fig.2 Effect of traffic scaling factor on bandwidth

2.2 建模分析

本文將空間信息網絡抽象為無向圖P(U，E)的形式，其中，V表示網絡中所有提供處理能力的衛星節點集合，對于每個衛星節點u∈U，E表示所有衛星間的物理鏈路集合，每條鏈路e∈E。B(u1，u2)表示帶寬，ζ=(γ1，γ2，…，γn)表示VNF 資源集合，γu，m表示衛星上節點u存在網絡虛擬功能為m的虛擬資源類型，單顆衛星可抽象出多類資源，用C(v)表示衛星節點的計算資源容量。

當系統接收到服務請求f進入到網絡中時，用E表示經過空間網絡中物理節點u1，u2的服務請求路徑：

若衛星上節點針對接收的服務請求f進行處理時產生一條多跳路徑，其中跳轉可能在衛星節點間發生，也可能在一顆衛星抽象出的不同虛擬功能間發生。用f(i，u′)表示服務請求f經過i次跳轉后在物理節點u′的位置上，假設共有N跳，i∈[1，N]，則有：

將服務請求中所需的虛擬網絡功能γ部署到空間信息網中的物理節點u上，則有：

針對服務請求f中考慮到的網絡虛擬功能之間的依附關系，用“＞”表示VNF 間調用的先后順序，γa＞γb表示虛擬網絡功能γb依附γa，需要先處理γa后再處理γb，則有：

這種依附關系具有傳遞性，例如γa＞γb且γb＞γc，則γa＞γc。

用ratio(γ)表示網絡虛擬功能類型為γ的流量縮放因子，定義分別代表服務請求f流入和流出節點u時對流量大小影響的比率：

若存在依附關系γa＞γb，需將a放在b后進行部署，且有如下約束條件：

costi表示VNF 的通信資源開銷，當僅存在一個VNF 時，costi=ωi=ratio(γ)。若處理式（6）這種相互依附關系的VNF 后，對于后續沒有與自身存在依附關系的虛擬網絡功能個體或集群，則需要將γa放在γb前，且存在以下約束：

其中，(1-ratioa)/costa＜(1-ratiob)/costb，將(1-ratioa)/costa看作γa的屬性，其值越小則在SFC 中的擺放位置越靠前。

考慮到減小衛星上VNF 部署實例的碎片化，針對SFC 中的待映射VNF，有且僅有一次被部署到衛星節點上：

考慮到實際傳輸時負載均衡且符合物理實際，對于任意一顆衛星，待處理所需的計算資源總和需小于該衛星節點實際最大值：

同理，所有服務請求f部署到衛星節點所需的通信資源總和應小于該物理節點所能提供的最大帶寬傳輸能力，應滿足：

為了能夠更細粒度地利用衛星上資源，衛星節點u上的虛擬網絡功能可被多條服務請求申請使用：

為了最小化空間信息網絡中衛星節點的計算資源與通信資源，并提高服務請求接收率，將目標函數設置為：

2.3 SFC 映射的問題描述

A*尋路是在Dijskra 算法的基礎上增加預測函數演變而來，通過對其選擇合理的搜索方向逐漸向目標節點靠近，從而找到最短路徑。

其中，f(s，e)表示從起始點s經過當前節點x到目的節點e所需的總開銷，g(s，x)表示從起始點s到當前節點x產生的實際通信開銷，h(x，e)表示從當前節點x到目的節點e的開銷評價。

為了使源節點s找到目的節點e的路徑最短，以μ(x)作為約束h(x，e)的權值，使其小于等于實際開銷可控制算法搜索目標節點范圍，當其值大于1 時可使算法增大預測函數權重以有效增大搜索范圍，且在周圍節點不具備部署能力時可快速跳出局部最優限制。

衛星間通信開銷g(s，x)包括鏈路丟包率、通信資源占用比率以及鏈路間時延，本文將通過綜合這些數據加權對后繼節點進行計算。

其中：l(s，x)表示鏈路丟包率，鏈路丟包率增加表示當前鏈路段擁塞，若達到閾值表示該段鏈路不具備映射條件，需要重新進行路由分配；b(s，x)表示通信資源占用比率，其反映鏈路通信資源使用情況；d(s，x)表示時延，其包括排隊時延、處理時延以及傳播時延；α、β、τ（賦權參數）在算法中以1∶1∶1 進行調配，實際可根據服務需求特點適當調節，且α+β+τ=1。

開銷預測函數h(x，t)是由待選衛星x與其相鄰衛星t的星間通信開銷平均值，以及經過加權處理后的衛星間歐幾里得距離得出，具體如式（15）所示：

其中：開銷預測函數若要達到效果必須小于實際開銷結果；λ為衛星間鏈路帶寬占用率，表示衛星間鏈路傳輸擁塞情況；考慮傳輸距離也是傳播時延產生的條件，用des(x，t)表示衛星間歐幾里得距離，且其值越小傳輸距離越短，通信所用延遲時間越短，即可得到開銷預測函數h(x，t)。

2.4 服務功能鏈的映射算法

本文提出一種空間信息網絡服務功能鏈映射算法，選擇映射路徑時可通過預測函數對衛星節點的選取進行評價分析，并根據服務需求通過減小預測函數的權值來加快搜索范圍收斂速度，或為了獲得全局最優解，增大權值范圍跳出局部最優，算法的具體步驟如下：

本文統計針對當前快照中衛星上資源抽象出的虛擬功能種類，判斷此衛星能否滿足服務請求，open表中存放的都是待處理的衛星節點，通過對當前節點以及周圍相鄰節點F 值的計算與比較，將當前開銷最小的點q標記為父節點，再計算父節點q周圍的節點開銷并進行比較，經過迭代計算持續更新在搜索中找到更優秀開銷的節點作為父節點，并最終得到SFC 映射路徑輸出。

本文采用一種可以避免出現重路由情況發生的策略［15-17］，每當算法搜索過程中出現候選節點與下一跳衛星鏈路通信斷開的情況時，為避免發生重路由會立刻反饋至MEO/GEO 衛星，并同時生成新的服務功能鏈映射路徑。針對節點失效計算時原路徑上局部節點失效的問題，本文可從鏈路通信斷開處的節點進行填補以更新出新的路徑策略。

3 實驗結果與分析

3.1 仿真實驗參數設置

本文仿真實驗配置環境如下：使用配置為64 位Ubuntu操作系統，Intel?CoreTMi7-3770 CPU@3.40 GHz處理器，16 GB 內存的PC 機上運行，使用編程語言Python3.6 在JetBrains PyCharm 2018.1.4 x64 平臺編寫。

OPNET 軟件可模擬空間信息網絡中衛星拓撲以及衛星對于VNF 的抽象，其中三顆GEO 位于對地靜止軌道，經度為0°，東經120°，西經120°。MEO、LEO 分別參照Odyssey 與Iridium 分布，衛星仿真參數如表1所示。

表1 衛星仿真參數Table 1 Satellite simulation parameters

為盡可能還原空間信息網絡中的運行情況，本文模擬出以下3 種情況：

1）使用OpenStack 模擬服務請求需求生成衛星上VNF 并管理，VNF 仿真參數如表2 所示。

表2 VNF 仿真參數Table 2 VNF simulation parameters

2）使用OpenDaylight 控制器對衛星拓撲進行控制管理，采用Openflow 生成模擬服務請求的流，從而實現流量經由虛擬機生成VNF。

3）預設每條服務請求包含的VNF 數量不確定，并服從［3，10］的均勻分布，接收的服務請求服從［100，300］的泊松分布［18-19］。

3.2 算法對比分析

實驗將本文算法與隨機映射RAND 算法以及離線布局OMD［20］算法在統一網絡環境中進行仿真分析比較。由于映射的開銷主要源自于滿足服務需求時達成功能實現的計算資源和內存資源的消耗，以及在通過算法構建鏈路時路徑中產生的通信資源消耗。為最小化映射開銷，本文通過流量縮放因子及VNF 間相互依附關系構建出一條合理的SFC，利用SFC 的構建來降低在衛星間和層間通信時通信資源的消耗，再通過本文算法找到SFC 映射的最佳路徑，以減少衛星上資源碎片化與計算內存資源的開銷。

總資源消耗表示在某一快照中滿足服務請求下，各個節點計算資源、通信資源以及內存資源的使用情況。由于衛星的處理能力主要由CPU 計算資源體現，因此在綜合考慮消耗多種資源的情況下，統一將CPU 占用50%，其他資源平均分配。如圖3 所示，隨著任務請求數增加，本文算法可在預測函數中進行快速擇優，以滿足高并發情況下的服務支持，且本文算法的總資源消耗率較RAND 算法、OMD 算法分別平均降低27%和6%。

圖3 3 種算法的總資源消耗率對比Fig.3 Comparison of total resource consumption rate of three algorithms

在處理請求時延方面，本文算法同樣有穩定的收斂趨勢，隨著SFC 任務請求數的不斷增加，并發業務量提高依舊可以表現出良好的處理能力。圖4 指標反映了本文算法對于服務請求、構建鏈路的路由選擇效率以及擁塞情況的處理能力，且所得結果顯示在高并發環境下，本文算法具有最小的處理請求時延結果，較OMD 算法處理時延平均降低了19%。因此，隨著并發業務量增多，本文算法可更快找到SFC 映射解決方案。

圖4 3 種算法的處理請求時延對比Fig.4 Comparison of processing request delay of three algorithms

4 結束語

本文提出一種適用于SFC 快速構建與映射的空間信息網絡抽象模型。該模型根據流量縮放因子及VNF 間的相互依附關系構建出合理的SFC，并針對SFC 映射過程中的隨機失效等問題，提出一種服務功能鏈優化算法。仿真結果表明，該算法可在較高的并發服務請求下，有效減小請求處理時延、降低映射時的總資源消耗，滿足網絡功能服務需求。下一步將采用神經網絡算法對本文空間信息網絡模型進行優化，通過調整各層空間中GEO、MEO、LEO 的數量得到最優部署方案，在降低空間部署成本的同時顯著提高空間網絡服務請求速率。