宋 滸，甘讓興，夏 飛，鄒昊東

(1.南京大學(xué)計(jì)算機(jī)軟件新技術(shù)國家重點(diǎn)實(shí)驗(yàn)室,江蘇 南京 210023;2.國網(wǎng)江蘇省電力有限公司信通分公司，江蘇 南京 210023)

1 引言

企業(yè)使用邊緣計(jì)算技術(shù)將服務(wù)部署在離用戶更近的邊緣設(shè)備上，以滿足用戶對(duì)超低時(shí)延服務(wù)(虛擬現(xiàn)實(shí)[1]、流媒體[2]、自動(dòng)駕駛[3]和圖像處理程序[4]等)的需求。同時(shí)，虛擬化技術(shù)使網(wǎng)絡(luò)功能脫離了專用硬件的束縛，能夠靈活地部署在虛擬機(jī)和容器等設(shè)備虛擬實(shí)例上，大大降低了企業(yè)的成本，并且用戶可以根據(jù)自身需求，將豐富的虛擬網(wǎng)絡(luò)功能以服務(wù)鏈[5]的形式組合在一起，以提供不同的網(wǎng)絡(luò)服務(wù)[6,7]，這極大地提高了邊緣設(shè)備部署網(wǎng)絡(luò)功能的靈活性和有效性。

但是，承載網(wǎng)絡(luò)功能服務(wù)的邊緣設(shè)備(無線路由器、網(wǎng)關(guān)等)通常只有有限的硬件資源[8,9]。例如，近年來發(fā)布的TP-LINK Archer C9無線路由器僅有1 GHz雙核CPU[10]。面對(duì)不斷增長的業(yè)務(wù)流量，這些資源有限的邊緣設(shè)備極易發(fā)生過載現(xiàn)象。另外，隨著物聯(lián)網(wǎng)的高速發(fā)展，企業(yè)在城市周圍部署了越來越多的智能設(shè)備，這些設(shè)備將收集大量的數(shù)據(jù)，導(dǎo)致在網(wǎng)絡(luò)邊緣處理的流量變化較大。智能設(shè)備上運(yùn)行的應(yīng)用程序流量模式的不同也會(huì)影響設(shè)備的負(fù)載。這些流量頻繁變化的用戶請(qǐng)求同樣會(huì)造成邊緣設(shè)備過載。

為了應(yīng)對(duì)邊緣設(shè)備過載問題，首先需要對(duì)服務(wù)鏈的資源消耗進(jìn)行精準(zhǔn)的測(cè)量。服務(wù)鏈的資源消耗主要指網(wǎng)絡(luò)功能計(jì)算所需要的資源消耗。文獻(xiàn)[11]表明，數(shù)據(jù)包傳輸在邊緣設(shè)備上會(huì)消耗大量的資源，而已有工作通常忽略這類資源消耗。本文對(duì)服務(wù)鏈負(fù)載模型進(jìn)行了細(xì)粒度建模，充分考慮了網(wǎng)絡(luò)功能計(jì)算和數(shù)據(jù)包傳輸2種類型的資源消耗。相比已有的研究，本文設(shè)計(jì)的負(fù)載模型對(duì)服務(wù)鏈中多實(shí)例的資源消耗進(jìn)行了更準(zhǔn)確的建模。面向邊緣環(huán)境的多實(shí)例服務(wù)鏈部署模型，包括邊緣設(shè)備負(fù)載模型和基于虛擬實(shí)例通信的時(shí)延約束模型2個(gè)組成部分。在此基礎(chǔ)上形式化地描述了最小化最大邊緣設(shè)備CPU負(fù)載率的最優(yōu)化問題。

基于細(xì)粒度的服務(wù)鏈負(fù)載模型，本文證明了多實(shí)例服務(wù)鏈在線部署問題為NP難問題。因此，為了能在滿足時(shí)延約束的情況下，在邊緣環(huán)境進(jìn)行多實(shí)例服務(wù)鏈的部署，以期望達(dá)到邊緣環(huán)境下邊緣設(shè)備間負(fù)載均衡的效果，本文設(shè)計(jì)了面向邊緣環(huán)境的多實(shí)例服務(wù)鏈在線部署算法。該算法包括3個(gè)階段：(1)時(shí)延滿足路徑搜索:查找當(dāng)前網(wǎng)絡(luò)拓?fù)湎聺M足時(shí)延約束的路徑集合；(2)部署路徑選擇:選擇路徑集合內(nèi)的一些路徑部署服務(wù)鏈；(3)網(wǎng)絡(luò)功能部署:將服務(wù)鏈的網(wǎng)絡(luò)功能按照用戶要求的部署策略部署在優(yōu)選的路徑集合內(nèi)的邊緣設(shè)備上。

仿真實(shí)驗(yàn)表明，該算法在最大邊緣設(shè)備CPU負(fù)載率這一評(píng)價(jià)指標(biāo)上優(yōu)于忽視服務(wù)鏈網(wǎng)絡(luò)功能間存在通信開銷的基準(zhǔn)算法。通過對(duì)比小規(guī)模網(wǎng)絡(luò)拓?fù)涞淖顑?yōu)部署結(jié)果，該算法結(jié)果接近最優(yōu)部署結(jié)果。

本文的組織結(jié)構(gòu)如下：第2節(jié)通過路由器容器部署實(shí)驗(yàn)分析影響網(wǎng)絡(luò)功能實(shí)例的CPU負(fù)載的因素；第3節(jié)對(duì)多實(shí)例服務(wù)鏈在線部署問題進(jìn)行建模；第4節(jié)對(duì)部署問題進(jìn)行算法設(shè)計(jì)；第5節(jié)對(duì)部署算法進(jìn)行評(píng)估；第6節(jié)對(duì)本文內(nèi)容進(jìn)行總結(jié)。

2 容器化網(wǎng)絡(luò)功能通信開銷

為了應(yīng)對(duì)邊緣設(shè)備過載問題，本文首先對(duì)提供服務(wù)的服務(wù)鏈網(wǎng)絡(luò)功能的資源消耗進(jìn)行細(xì)粒度的測(cè)量。本文在無線路由器內(nèi)通過容器化部署服務(wù)鏈設(shè)計(jì)了一個(gè)基準(zhǔn)實(shí)驗(yàn)。實(shí)驗(yàn)中使用了一個(gè)無線路由器和一臺(tái)服務(wù)器。無線路由器中部署虛擬網(wǎng)絡(luò)功能鏈，服務(wù)器同時(shí)作為流量的發(fā)送方和接收方。該實(shí)驗(yàn)將服務(wù)鏈的網(wǎng)絡(luò)功能設(shè)置為數(shù)據(jù)包轉(zhuǎn)發(fā)過程，忽略網(wǎng)絡(luò)功能計(jì)算資源的消耗，從而得到數(shù)據(jù)包在網(wǎng)絡(luò)功能間傳遞的通信開銷。通過調(diào)整服務(wù)鏈長度、數(shù)據(jù)包速率和數(shù)據(jù)包大小3個(gè)關(guān)鍵參數(shù)，同時(shí)持續(xù)讀取無線路由器CPU利用率，得到CPU利用率與3個(gè)參數(shù)的關(guān)系。通過控制變量的方式。分別分析了CPU利用率和服務(wù)鏈長度、數(shù)據(jù)包速率和數(shù)據(jù)包大小的關(guān)系，實(shí)驗(yàn)結(jié)果如圖1所示。圖1中采樣點(diǎn)代表實(shí)驗(yàn)數(shù)據(jù)，通過最小二乘法得到擬合線(未進(jìn)行實(shí)驗(yàn)時(shí)，無線路由器的CPU利用率為1%～2%，所以擬合線未過原點(diǎn))。

Figure 1 Relationship between CPU utilization and service chain length, packet rate and packet size

load(T)=comm(T)+comp(T)=

(1)

其中，αf是網(wǎng)絡(luò)功能f計(jì)算開銷和通信開銷的比率。注意到，該模型不同于傳統(tǒng)的僅考慮計(jì)算開銷的服務(wù)鏈負(fù)載模型(簡稱為服務(wù)鏈負(fù)載傳統(tǒng)模型)：

(2)

另一方面，為了降低設(shè)備的負(fù)載，提高服務(wù)的穩(wěn)定性，通常會(huì)在不同設(shè)備的虛擬實(shí)例內(nèi)部署同一網(wǎng)絡(luò)服務(wù)[12-14]，在對(duì)用戶流量進(jìn)行劃分后通過部署某個(gè)網(wǎng)絡(luò)功能的多個(gè)虛擬實(shí)例實(shí)現(xiàn)負(fù)載均衡。但可惜的是，目前缺乏結(jié)合上述2個(gè)方面的服務(wù)鏈部署算法研究工作。因此，本文設(shè)計(jì)并實(shí)現(xiàn)了一種面向邊緣環(huán)境的多實(shí)例服務(wù)鏈在線部署算法，在現(xiàn)有的邊緣環(huán)境下，提供低時(shí)延、低負(fù)載的網(wǎng)絡(luò)功能服務(wù)。

3 多實(shí)例服務(wù)鏈在線部署問題建模

在邊緣環(huán)境下存在著大量的邊緣設(shè)備，這些邊緣設(shè)備的CPU和內(nèi)存資源使用情況各不相同。企業(yè)可以使用這些邊緣設(shè)備，將服務(wù)鏈中的網(wǎng)絡(luò)功能部署在具有較低負(fù)載和較近距離的對(duì)等邊緣設(shè)備上，提供低時(shí)延的服務(wù)，同時(shí)緩解設(shè)備過載的問題。本節(jié)在模型假設(shè)的基礎(chǔ)上，首先對(duì)邊緣環(huán)境進(jìn)行建模；然后通過虛擬實(shí)例通信圖來描繪多實(shí)例服務(wù)鏈部署的通信情況；接著，提出了衡量設(shè)備負(fù)載的邊緣設(shè)備負(fù)載模型和概括服務(wù)鏈時(shí)延約束的時(shí)延約束模型；最后，給出了問題求解的目標(biāo)函數(shù)和難度論證。

3.1 模型假設(shè)

由于邊緣設(shè)備的資源有限性，本文假定虛擬實(shí)例以容器的方式部署在邊緣設(shè)備。為了簡化邊緣環(huán)境模型，本文采用如下假設(shè)：

(1)邊緣設(shè)備上運(yùn)行的容器可以部署任意類型虛擬網(wǎng)絡(luò)功能VNF(Virtual Network Function)。

(2)任何虛擬實(shí)例只能部署一個(gè)虛擬網(wǎng)絡(luò)功能。

(3)僅關(guān)注邊緣設(shè)備之間的傳播時(shí)延，不考慮設(shè)備內(nèi)部處理流量導(dǎo)致的傳輸時(shí)延。

3.2 邊緣環(huán)境模型

由于VNF實(shí)例可能改變通過該功能的流量大小，例如IPSec/SSL VPN和媒體網(wǎng)關(guān)會(huì)將通過的數(shù)據(jù)包進(jìn)行封裝和解封裝操作而改變數(shù)據(jù)包的大小[15]；防火墻和入侵檢測(cè)系統(tǒng)會(huì)丟棄違反安全策略的數(shù)據(jù)包而改變數(shù)據(jù)包的數(shù)量[16]。本文定義αTr,i表示服務(wù)鏈第i個(gè)網(wǎng)絡(luò)功能改變流量的比率，βTr,i表示服務(wù)鏈第i個(gè)網(wǎng)絡(luò)功能計(jì)算開銷和通信開銷的比率。由于單位時(shí)間間隔內(nèi)存在多個(gè)用戶部署服務(wù)鏈的情況，所以本文用符號(hào)N表示單位時(shí)間間隔內(nèi)用戶請(qǐng)求的數(shù)量，并將時(shí)間間隔t內(nèi)，對(duì)邊緣設(shè)備有負(fù)載作用的用戶請(qǐng)求集合表示為R(t)。邊緣設(shè)備v的負(fù)載容量表示為Cv。本文使用|X|表示集合[X]的大小，例如，符號(hào)|Tr|表示服務(wù)鏈長度，|Tr,i|表示部署服務(wù)鏈第i個(gè)網(wǎng)絡(luò)功能的實(shí)例個(gè)數(shù)。

3.3 虛擬實(shí)例通信圖

為了降低設(shè)備的負(fù)載，提高服務(wù)的穩(wěn)定性，通常將服務(wù)鏈的網(wǎng)絡(luò)功能部署在多個(gè)邊緣設(shè)備容器中。虛擬實(shí)例通信圖能描繪服務(wù)鏈部署的情況。如圖2所示，圓形代表邊緣設(shè)備，方形代表虛擬實(shí)例，箭頭上方數(shù)字代表流量大小。例如，虛擬實(shí)例Tr,1,1和虛擬實(shí)例Tr,2,1有通信關(guān)系，而和虛擬實(shí)例Tr,2,2沒有通信關(guān)系。

Figure 2 An example of virtual instance communication graph

軟件定義網(wǎng)絡(luò)技術(shù)可以通過下發(fā)流表項(xiàng)到邊緣設(shè)備的方式調(diào)度用戶網(wǎng)絡(luò)流通過特定虛擬實(shí)例。但是，受網(wǎng)絡(luò)流數(shù)量|fr|的影響，部署服務(wù)鏈第i個(gè)網(wǎng)絡(luò)功能的虛擬實(shí)例個(gè)數(shù)需滿足以下不等式：

|Tr,i|≤|fr|,i∈[1,|Tr|]

(3)

等號(hào)成立當(dāng)且僅當(dāng)部署服務(wù)鏈第i個(gè)網(wǎng)絡(luò)功能的虛擬實(shí)例運(yùn)行在完全不同的邊緣設(shè)備上。從圖2中可以看出，用戶請(qǐng)求從某網(wǎng)絡(luò)流的源節(jié)點(diǎn)出發(fā)，依次通過運(yùn)行在邊緣設(shè)備v1、v2和v3上的VNF實(shí)例，最終到達(dá)目標(biāo)節(jié)點(diǎn)。

3.4 邊緣設(shè)備負(fù)載模型

為了達(dá)到邊緣設(shè)備間負(fù)載均衡的目標(biāo)，本文需要對(duì)邊緣設(shè)備的負(fù)載情況進(jìn)行建模。部署服務(wù)鏈第i個(gè)網(wǎng)絡(luò)功能的虛擬實(shí)例的入口流量和出口流量的關(guān)系為：

(4)

由于信道不會(huì)改變流量大小，所以由流量守恒可知，部署服務(wù)鏈第i個(gè)網(wǎng)絡(luò)功能的虛擬實(shí)例j的入口流量等于和該虛擬實(shí)例有通信關(guān)系的部署第i-1個(gè)網(wǎng)絡(luò)功能的虛擬實(shí)例的出口流量之和：

(5)

其中，hTr,i-1,k,i,j∈{0,1}是通信二值變量，當(dāng)hTr,i-1,k,i,j=1時(shí)，表示部署服務(wù)鏈第i-1個(gè)網(wǎng)絡(luò)功能的虛擬實(shí)例k和部署服務(wù)鏈第i個(gè)網(wǎng)絡(luò)功能的虛擬實(shí)例j有通信關(guān)系；否則，hTr,i-1,k,i,j=0。另一方面，初始帶寬等于部署服務(wù)鏈第1個(gè)000網(wǎng)絡(luò)功能的虛擬實(shí)例的入口流量之和：

(6)

在時(shí)間間隔t內(nèi)，部署服務(wù)鏈第i個(gè)網(wǎng)絡(luò)功能的虛擬實(shí)例j的入口流量和邊緣設(shè)備v的關(guān)系為：

(7)

其中，xt,Tr,i,j,v∈{0,1}被稱為設(shè)備二值變量，當(dāng)xt,Tr,i,j,v=1時(shí)，表示在時(shí)間間隔t內(nèi)，部署服務(wù)鏈第i個(gè)網(wǎng)絡(luò)功能的虛擬實(shí)例j運(yùn)行在邊緣設(shè)備v上；否則，xt,Tr,i,j,v=0。同理，在時(shí)間間隔t內(nèi)，部署服務(wù)鏈第i個(gè)網(wǎng)絡(luò)功能的虛擬實(shí)例j的出口流量和邊緣設(shè)備v的關(guān)系為：

(8)

基于服務(wù)鏈網(wǎng)絡(luò)功能間存在通信開銷的服務(wù)鏈負(fù)載模型，在時(shí)間間隔t內(nèi)，邊緣設(shè)備v的負(fù)載為：

loadv(t)=∑r∈R(t)((ω+αTr,i)·

(9)

同理，在服務(wù)鏈負(fù)載傳統(tǒng)模型下，在時(shí)間間隔t內(nèi)，邊緣設(shè)備v的負(fù)載為：

(10)

3.5 時(shí)延約束模型

邊緣環(huán)境模型規(guī)定的流量必須通過源節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)。為了統(tǒng)一時(shí)延約束表示，本節(jié)為服務(wù)鏈添加2個(gè)不增加負(fù)載的網(wǎng)絡(luò)功能Tr,0和Tr,|Tr|+1，并將其分別置于服務(wù)鏈的首端和尾端(保持服務(wù)鏈長度不變，通過額外下標(biāo)表示這2個(gè)假設(shè)的網(wǎng)絡(luò)功能)，而且人為規(guī)定部署網(wǎng)絡(luò)功能Tr,0的虛擬實(shí)例必須運(yùn)行在源節(jié)點(diǎn)上，部署網(wǎng)絡(luò)功能Tt,|Tr|+1的虛擬實(shí)例必須運(yùn)行在目標(biāo)節(jié)點(diǎn)上，由式(11)表示如下：

(11)

Table 1 Constraint relationship between equipment binary variable and delay binary variable

?t,?r∈R(t),?v,v′∈V,hTr,i-1,j,i,k=1

i∈[1,|Tr|+1],

j∈[1,|Tr,i-1|],k∈[1,|Tr,i|]

(12)

綜上可以得出，服務(wù)鏈的時(shí)延約束滿足不等式：

?r∈R(t),hTr,i-1,j,i,k=1,i∈[1,|Tr|+1],

j∈[1,|Tr,i-1|],k∈[1,|Tr,i|]

(13)

3.6 目標(biāo)函數(shù)

s.t. (3)～(9),(11)～(13)

(14)

該目標(biāo)函數(shù)F旨在時(shí)延約束以及所有時(shí)間間隔內(nèi)，最小化最大邊緣設(shè)備CPU負(fù)載率，即對(duì)邊緣環(huán)境下的邊緣設(shè)備進(jìn)行負(fù)載均衡。

求解該問題存在2個(gè)難點(diǎn)：(1)由于邊緣環(huán)境下用戶的移動(dòng)性，用戶請(qǐng)求會(huì)頻繁加入和退出，不同于服務(wù)鏈的靜態(tài)部署，最大邊緣設(shè)備負(fù)載和時(shí)間維度有關(guān)；(2)邊緣設(shè)備的負(fù)載均衡問題必須同時(shí)考慮時(shí)延約束和網(wǎng)絡(luò)功能的負(fù)載差異性。一方面，時(shí)延約束限定了對(duì)等邊緣設(shè)備的選?。涣硪环矫?，網(wǎng)絡(luò)功能負(fù)載的差異性增加了在對(duì)等邊緣設(shè)備間保持負(fù)載均衡的難度。

3.7 NP完全性證明

首先，問題能在多項(xiàng)式時(shí)間內(nèi)驗(yàn)證候選解是否滿足約束條件。其次，本節(jié)首先簡短介紹已被證明為NP完全問題的多處理器調(diào)度MPS(Multi-Processor Scheduling)問題[17]，然后證明MPS問題可以歸約到F的一個(gè)子問題F1，該子問題是面向邊緣環(huán)境的只考慮計(jì)算開銷的線性服務(wù)鏈部署問題。

MPS：給定n個(gè)任務(wù)J={J1,J2,…,Jn}，每個(gè)任務(wù)需要pj時(shí)間去處理；m臺(tái)機(jī)器M={M1,M2,…,Mm}(n>m)，由這m臺(tái)機(jī)器來完成這n個(gè)任務(wù)。如何調(diào)度這些任務(wù)，使得最后完成所有任務(wù)的時(shí)間最短。

定義F1：在保持F其它條件不變的情況下，改變以下4個(gè)條件：

(1)用戶請(qǐng)求r流量內(nèi)網(wǎng)絡(luò)流數(shù)量|fr|為1。

(2)時(shí)間間隔數(shù)量TN=1，且用戶請(qǐng)求數(shù)N=1。

(3)忽略服務(wù)鏈網(wǎng)絡(luò)功能間的通信開銷，即commTr,i=0。

(4)時(shí)延約束lr被設(shè)定為無窮大。

下面證明F1是NP難問題：

證明構(gòu)造規(guī)約過程如下，將MPS問題的輸入構(gòu)造成子問題的輸入，即服務(wù)鏈具有n個(gè)網(wǎng)絡(luò)功能，每個(gè)網(wǎng)絡(luò)功能會(huì)產(chǎn)生pj的計(jì)算開銷，邊緣環(huán)境下有m個(gè)邊緣設(shè)備。為達(dá)到設(shè)備間負(fù)載均衡當(dāng)且僅當(dāng)所有邊緣設(shè)備的負(fù)載情況相同。已知MPS問題的輸出，即所用時(shí)間最短當(dāng)且僅當(dāng)所有機(jī)器的處理時(shí)間相等。由于邊緣設(shè)備和機(jī)器具有一一對(duì)應(yīng)關(guān)系,且在子問題以及MPS問題的輸出中,任意邊緣設(shè)備的負(fù)載和對(duì)應(yīng)機(jī)器的處理時(shí)間在數(shù)值上相等。因此，在多項(xiàng)式時(shí)間內(nèi)，MPS問題的輸入可以轉(zhuǎn)換成子問題的輸入，且子問題的輸出可以轉(zhuǎn)換成MPS問題的輸出，證畢。

□

該證明說明子問題F1是NP難問題，進(jìn)而F是NP難問題，從而F是NP完全問題，除非能證明P=NP，否則不可能為F找到一個(gè)高效的多項(xiàng)式算法，基于求解問題F的難度論證，本文將在下一節(jié)中給出一個(gè)啟發(fā)式算法DS-PC-ND(Delay Statisfaction-Path Collection-Network function Development)去解決該問題。

4 DS-PC-ND算法設(shè)計(jì)

4.1 DS-PC-ND算法框架

為了能在滿足時(shí)延約束的情況下，在邊緣環(huán)境進(jìn)行多實(shí)例服務(wù)鏈在線部署，以期望達(dá)到邊緣環(huán)境下邊緣設(shè)備負(fù)載均衡的效果，算法框架分為如下3個(gè)階段：

(1)階段1(時(shí)延滿足路徑搜索)：搜索當(dāng)前網(wǎng)絡(luò)拓?fù)湎聺M足時(shí)延約束的路徑集合P1。

(2)階段2(部署路徑選擇)：選擇路徑集合P1內(nèi)的|fr|個(gè)路徑組成路徑集合P2作為部署路徑集合。

(3)階段3(網(wǎng)絡(luò)功能部署)：將服務(wù)鏈的網(wǎng)絡(luò)功能按照某種部署策略部署在路徑集合P2的邊緣設(shè)備上。

這3個(gè)階段表明多實(shí)例服務(wù)鏈的部署涉及到將服務(wù)鏈分配到滿足時(shí)延約束的若干路徑(P2)上，并將服務(wù)鏈的網(wǎng)絡(luò)功能部署在路徑中資源較為充足的邊緣設(shè)備上。需要說明的是，由于網(wǎng)絡(luò)流數(shù)量|fr|不等于|P1|，所以階段2在時(shí)延約束路徑集合P1內(nèi)選出部署路徑集合P2，這能簡化階段3內(nèi)網(wǎng)絡(luò)功能部署的過程。算法框架如圖3所示。下面小節(jié)將依次介紹時(shí)延滿足路徑搜索DS(Delay Statisfaction)算法、部署路徑選擇PC(Path Collection)算法和網(wǎng)絡(luò)功能部署ND(Network function Development)算法。

Figure 3 Framework of DS-PC-ND algorithm

4.2 時(shí)延滿足路徑搜索算法

由于邊緣環(huán)境模型假定用戶請(qǐng)求必須通過已知的源節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)，所以時(shí)延滿足路徑搜索可以看成在已知源節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)的情況下，找出滿足時(shí)延約束lr的路徑集合P1。為了降低問題的難度，本文假定時(shí)延滿足路徑搜索(DS)算法搜索的是簡單路徑，即路徑中的節(jié)點(diǎn)不能出現(xiàn)重復(fù)，這樣得到路徑集合P′1，顯然P′1?P1。

本文使用雙棧數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)了一個(gè)基于剪枝搜索策略的非遞歸算法去求解時(shí)延滿足路徑搜索問題。如算法1所示，該算法首先準(zhǔn)備2個(gè)棧(主棧S1和輔棧S2)，主棧中的每個(gè)元素是單個(gè)值，表示當(dāng)前路徑的某個(gè)節(jié)點(diǎn)，輔棧中的每個(gè)元素是一個(gè)列表，表示主棧對(duì)應(yīng)元素的鄰接節(jié)點(diǎn)集合，即主棧記錄的是某一條以源節(jié)點(diǎn)為起點(diǎn)的路徑，而輔棧記錄主棧路徑可能的下一跳。本文使用變量時(shí)延和delay來記錄目前主棧路徑的時(shí)延之和。當(dāng)主棧棧頂元素為目標(biāo)節(jié)點(diǎn)時(shí)，主棧棧底到棧頂?shù)脑匦蛄杏洖榉蠒r(shí)延約束的一條簡單路徑。為了使選擇出來的路徑是簡單路徑，算法1保證主棧壓入的下一跳不會(huì)和主棧已有元素重復(fù)。函數(shù)Neig返回鄰接節(jié)點(diǎn)列表；函數(shù)First返回列表第1個(gè)元素；函數(shù)Remain表示將列表第1個(gè)元素去除后，組成一個(gè)新的列表；函數(shù)Seq返回棧底到棧頂元素序列；函數(shù)Delay返回2個(gè)節(jié)點(diǎn)之間的時(shí)延；函數(shù)RmRp(X,Y)去除列表X內(nèi)Y包含的元素。

算法1時(shí)延滿足路徑搜索算法

輸入：圖G(V,E)，用戶請(qǐng)求。

輸出：滿足時(shí)延約束的簡單路徑集合P′1。

S1←sr，S2←Neig(sr)；

Repeat

neigs←S2.pop()；

If!neigs.empty()then

S2.push(Remain(neigs))；

next←Delay(S1.top(),First(neigs))；

Ifdelay+next≤lrthen

delay+=next；

S1.push(First(neigs))；

S2.push(RmRp(Neig(S1.top()),S1))；

Endif

Else

S1.pop();continue；

Endif

IfS1.top()==drthen

P′1.push(Seq(S1))；

delay-=Delay(S1.top(),S1.nextTop())；

S1.pop();S2.pop()；

Endif

UntilS1.empty()；

ReturnP′1；

4.3 部署路徑選擇算法

通過時(shí)延滿足路徑搜索算法，本文找到滿足時(shí)延約束的簡單路徑集合P′1。由于本文設(shè)定用戶請(qǐng)求內(nèi)網(wǎng)絡(luò)流流通的路徑是固定的，且網(wǎng)絡(luò)流數(shù)量為|fr|，所以需要在P′1內(nèi)選擇|fr|條路徑來作為部署服務(wù)鏈的部署路徑集合P2。但是，為了降低時(shí)間復(fù)雜度，本節(jié)使用嵌套TopK策略在路徑集合P′1中找出將要部署多實(shí)例服務(wù)鏈的路徑集合P2。本文將該算法稱為部署路徑選擇(PC)算法，其具體實(shí)現(xiàn)包含嵌套函數(shù)(函數(shù)1嵌入函數(shù)2內(nèi)，作為函數(shù)2的一條語句執(zhí)行，函數(shù)2返回最終的部署路徑集合P2)。

函數(shù)1內(nèi)容說明：對(duì)于p∈P′1，本函數(shù)選取路徑p內(nèi)負(fù)載最小的K1(|Tr|)個(gè)邊緣設(shè)備來代表路徑p內(nèi)所有邊緣設(shè)備的負(fù)載情況，并將這K1個(gè)邊緣設(shè)備負(fù)載和的均值記為loadp，并將該值返回給函數(shù)2。

函數(shù)2內(nèi)容說明：由于總共有|P′1|條路徑，而本函數(shù)的目標(biāo)是選擇出|fr|(記為K2)條路徑作為部署路徑集合P2(該集合是算法3的輸入)，而一般情況下|P′1|都不等于|fr|，所以需要設(shè)計(jì)一種策略在P′1中選擇|fr|條路徑。本文設(shè)定函數(shù)2使用函數(shù)1返回的loadp值來進(jìn)行選擇，即選取P′1內(nèi)loadp值最小的|fr|條路徑(loadp值和p存在一一對(duì)應(yīng)關(guān)系)。

基于嵌套TopK策略中，函數(shù)1和函數(shù)2包含嵌套關(guān)系，并且函數(shù)1和函數(shù)2的運(yùn)算過程涉及到選擇K個(gè)元素(函數(shù)1中K=K1，函數(shù)2中K=K2)。

算法2部署路徑選擇算法(函數(shù)1)

輸入：時(shí)延滿足路徑集合P′1，用戶請(qǐng)求r，邊緣環(huán)境模型。

輸出：部署路徑集合P2。

初始化最大堆D1；

進(jìn)入函數(shù)1(p由函數(shù)2傳遞給函數(shù)1)；

Foreachnode∈pdo

IfD1.top()>Load(node)then

D1.pop()，D1.push(Load(node))；

Endif

Endfor

loadp←D1內(nèi)有效元素和的均值；

重置D1；

Returnloadp；

本文使用堆來處理TopK選擇問題，使用了2個(gè)最大堆D1和D2。維持D1大小為|Tr|，維持D2大小為|fr|。顯然，很容易得到函數(shù)1的時(shí)間復(fù)雜度為O(|p|·log2(|Tr|))，函數(shù)2的時(shí)間復(fù)雜度為O(|P′1|·log2(|f4|))，但由于函數(shù)1要運(yùn)行|P′1|次，所以算法2的時(shí)間復(fù)雜度為O(|P′1|·|p|·log2(|Tr|)+|P′1|·log2(|fr|))。另一方面，由于算法2需要維護(hù)2個(gè)最大堆，所以該算法的空間復(fù)雜度為O(|Tr|+|fr|)。

4.4 網(wǎng)絡(luò)功能部署算法

得到了將要部署多實(shí)例服務(wù)鏈的簡單路徑集合P2后，本節(jié)設(shè)計(jì)了一個(gè)基于貪心策略的啟發(fā)式算法將多實(shí)例服務(wù)鏈的網(wǎng)絡(luò)功能部署在這些路徑上的邊緣設(shè)備上。如算法3所示，對(duì)于每一條部署路徑p∈P2，部署算法首先找到該路徑的最小負(fù)載節(jié)點(diǎn)node，然后將服務(wù)鏈的第1個(gè)網(wǎng)絡(luò)功能部署在該節(jié)點(diǎn)上,之后將部署路徑p的起點(diǎn)設(shè)置為node。如此往復(fù)，直至服務(wù)鏈的全部網(wǎng)絡(luò)功能部署完畢。

算法3網(wǎng)絡(luò)功能部署算法

輸入：部署路徑集合P2，用戶請(qǐng)求r，邊緣環(huán)境模型。

輸出：部署結(jié)果。

Foreachp∈P2do

ForeachTr,i∈Trdo

獲取p內(nèi)最小負(fù)載節(jié)點(diǎn)node；

更新邊緣設(shè)備node的負(fù)載；

將p的起點(diǎn)設(shè)置為node；

Endfor

Endfor

算法3的時(shí)間復(fù)雜度為O(|P2|·|Tr|·|p|)，因?yàn)樵撍惴ò?層循環(huán)，外層循環(huán)要進(jìn)行|P2|次，內(nèi)層循環(huán)要進(jìn)行|Tr|次，內(nèi)層循環(huán)中查找最小負(fù)載節(jié)點(diǎn)要對(duì)路徑p遍歷一次(時(shí)間復(fù)雜度為O(|p|))。該算法只使用常數(shù)個(gè)額外變量，空間復(fù)雜度為O(1)。

5 DS-PC-ND算法評(píng)估

對(duì)于多實(shí)例服務(wù)鏈在線部署算法DS-PC-ND，本文將從2個(gè)方面來評(píng)估其性能：一方面，由于服務(wù)鏈網(wǎng)絡(luò)功能間存在通信開銷，所以希望知道該算法能多大程度緩解負(fù)載失衡現(xiàn)象；另一方面，評(píng)估該算法與最優(yōu)部署結(jié)果之間的差距。

5.1 仿真環(huán)境與仿真參數(shù)

仿真實(shí)驗(yàn)在Linux環(huán)境下進(jìn)行，使用LEMON網(wǎng)絡(luò)仿真庫[18]隨機(jī)生成2個(gè)網(wǎng)絡(luò)拓?fù)洹＞W(wǎng)絡(luò)拓?fù)銩包含30個(gè)節(jié)點(diǎn)和47條邊，網(wǎng)絡(luò)拓?fù)銪包含6個(gè)節(jié)點(diǎn)和7條邊。對(duì)于每個(gè)用戶請(qǐng)求，本文隨機(jī)從所有節(jié)點(diǎn)中選擇源節(jié)點(diǎn)sr和目標(biāo)節(jié)點(diǎn)dr，并保證sr和dr不會(huì)重復(fù)。同時(shí)，假定用戶請(qǐng)求r的網(wǎng)絡(luò)流均分初始流量br。仿真參數(shù)如表2所示。其中，[X′,Y′]表示仿真參數(shù)隨機(jī)且均勻地從X′～Y′中生成，{I,J}表示仿真參數(shù)隨機(jī)地從I～J中生成(取整數(shù))。另外，本文將單位時(shí)間間隔設(shè)定為1 s，為了研究單位時(shí)間間隔內(nèi)用戶請(qǐng)求數(shù)N對(duì)設(shè)備負(fù)載的影響，本文將N設(shè)置成不同數(shù)值后進(jìn)行仿真實(shí)驗(yàn)。為了避免設(shè)定固定數(shù)值的時(shí)延約束lr對(duì)算法評(píng)估的負(fù)面影響，本文將時(shí)延約束lr設(shè)定為sr到dr的最短路徑時(shí)延和的2倍。

Figure 4 Comparison of DS-PC-ND and DS-PC-ND-Comp

5.2 評(píng)價(jià)指標(biāo)

評(píng)估問題的目標(biāo)函數(shù)為最大邊緣設(shè)備CPU負(fù)載率，即對(duì)最大的邊緣設(shè)備CPU負(fù)載進(jìn)行歸一化后的結(jié)果。顯然，最大邊緣設(shè)備CPU負(fù)載率值越低，說明算法性能越好。

Table 2 Simulation parameter table

5.3 基準(zhǔn)算法

基準(zhǔn)算法DS-PC-ND-Comp是為驗(yàn)證服務(wù)鏈網(wǎng)絡(luò)功能間通信開銷對(duì)邊緣設(shè)備負(fù)載均衡的影響而設(shè)計(jì)的。具體算法如下所示：保持DS-PC-ND算法框架不變，將服務(wù)鏈負(fù)載模型由服務(wù)鏈負(fù)載事實(shí)模型替換為服務(wù)鏈負(fù)載傳統(tǒng)模型，即認(rèn)為服務(wù)鏈網(wǎng)絡(luò)功能間只存在計(jì)算開銷，并基于該認(rèn)識(shí)去運(yùn)行部署路徑選擇算法和網(wǎng)絡(luò)功能部署算法。

5.4 DS-PC-ND vs.DS-PC-ND-Comp

本節(jié)將評(píng)估DS-PC-ND算法相對(duì)于基準(zhǔn)算法DS-PC-ND-Comp的優(yōu)勢(shì)，以驗(yàn)證忽略服務(wù)鏈網(wǎng)絡(luò)功能間存在通信開銷這一事實(shí)的不良影響，對(duì)比結(jié)果如圖4所示?？梢钥闯觯珼S-PC-ND算法優(yōu)于基準(zhǔn)算法DS-PC-ND-Comp 3%～10%個(gè)單位邊緣設(shè)備CPU負(fù)載率。

更具體地說，圖4a和圖4b的βTr,i設(shè)置不同，這使得圖4b中通過網(wǎng)絡(luò)功能的流量可能變大，這增加了邊緣環(huán)境的流量總量，使得最大邊緣設(shè)備CPU負(fù)載率變大，同理可得圖4c和圖4d的結(jié)果對(duì)比；圖4a和圖4c的αTr,i設(shè)置不同，這增加了圖4c中服務(wù)鏈的計(jì)算開銷占比，使得最大邊緣設(shè)備CPU負(fù)載負(fù)載率變大，同理可得圖4b和圖4d的結(jié)果對(duì)比。

5.5 DS-PC-ND vs.Optimal

本節(jié)將評(píng)估DS-PC-ND算法和基于最優(yōu)化方程求解的最優(yōu)部署結(jié)果Optimal(使用規(guī)劃問題求解器Gurobi求解)的差距。為了降低求解最優(yōu)部署結(jié)果的問題規(guī)模，本節(jié)將邊緣環(huán)境網(wǎng)絡(luò)拓?fù)湫薷臑榫W(wǎng)絡(luò)拓?fù)銪。在多個(gè)時(shí)間維度(TN=10,TN=20)下進(jìn)行了仿真實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如圖5所示。

Figure 5 DS-PC-ND vs.Optimal

從圖5可以看出，DS-PC-ND算法的部署結(jié)果接近最優(yōu)部署結(jié)果，這是由于部署路徑選擇算法盡可能選擇負(fù)載較小的部署路徑，而且網(wǎng)絡(luò)功能部署算法也盡可能地將網(wǎng)絡(luò)功能部署在負(fù)載較小的邊緣設(shè)備上，這些啟發(fā)式策略能保證接近最優(yōu)部署結(jié)果。

6 結(jié)束語

在基于服務(wù)鏈網(wǎng)絡(luò)功能間存在通信開銷以及服務(wù)鏈網(wǎng)絡(luò)功能同時(shí)部署在多個(gè)虛擬實(shí)例內(nèi)這2個(gè)事實(shí)基礎(chǔ)上，本文對(duì)面向邊緣環(huán)境的多實(shí)例服務(wù)鏈在線部署問題進(jìn)行了建模，并提出了一個(gè)3階段算法DS-PC-ND進(jìn)行求解。仿真實(shí)驗(yàn)結(jié)果表明，該算法緩解了設(shè)備間的負(fù)載失衡現(xiàn)象，并且接近最優(yōu)部署結(jié)果。由于該算法中包含啟發(fā)式算法，因此未來還有比較大的改進(jìn)空間。