網(wǎng)絡(luò)功能虛擬化中延時(shí)感知的資源調(diào)度優(yōu)化方法

徐 冉 王文東 龔向陽(yáng) 闕喜戎

(網(wǎng)絡(luò)與交換技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室(北京郵電大學(xué)) 北京 100876) (ranxu@bupt.edu.cn)

NFV如今作為業(yè)界與學(xué)術(shù)界的熱點(diǎn)，它支持NFs的快速創(chuàng)建、撤銷或遷移，依托著虛擬技術(shù)降低了網(wǎng)絡(luò)成本從而得以迅速發(fā)展.由于安全或者性能的需求，網(wǎng)絡(luò)操作者往往要求數(shù)據(jù)流以特定的序列通過多個(gè)NFs(例如數(shù)據(jù)包需要經(jīng)過防火墻，然后經(jīng)過入侵檢測(cè)系統(tǒng)，最后經(jīng)過負(fù)載均衡器)，即通常所稱的服務(wù)鏈(service chaining)[4-5].網(wǎng)絡(luò)功能虛擬化的主要挑戰(zhàn)之一是根據(jù)服務(wù)鏈規(guī)則執(zhí)行所需服務(wù)時(shí)，實(shí)現(xiàn)快速和動(dòng)態(tài)的網(wǎng)絡(luò)功能資源分配，因此虛擬網(wǎng)絡(luò)功能資源調(diào)度優(yōu)化得到了研究者們的關(guān)注.

根據(jù)應(yīng)用或者用戶的需求不同，虛擬網(wǎng)絡(luò)功能資源調(diào)度有著不同的優(yōu)化目標(biāo)，比如，對(duì)于電信服務(wù)商來(lái)說，他們的長(zhǎng)遠(yuǎn)目標(biāo)是實(shí)現(xiàn)最大化所接受服務(wù)請(qǐng)求的經(jīng)濟(jì)收益，這就要求網(wǎng)絡(luò)功能虛擬化在分配與調(diào)度資源的時(shí)候提高對(duì)服務(wù)請(qǐng)求的接受率；但是對(duì)于提供語(yǔ)音IP網(wǎng)絡(luò)服務(wù)商來(lái)說，一定程度的帶寬和低延遲保證是首先需要考慮的，此外類似的優(yōu)化目標(biāo)包括容錯(cuò)能力、負(fù)載均衡和能源消耗[6]等.近些年來(lái)，由于互聯(lián)網(wǎng)絡(luò)和網(wǎng)絡(luò)應(yīng)用的發(fā)展，使得如今網(wǎng)絡(luò)具有更大的帶寬和存儲(chǔ)容量，但是包括移動(dòng)應(yīng)用、在線交互或者交易等新業(yè)務(wù)模型的激增，對(duì)于業(yè)務(wù)延遲的需求越來(lái)越高.比如，包括監(jiān)控系統(tǒng)、在線金融分析、算法交易等對(duì)實(shí)時(shí)性要求較高的應(yīng)用場(chǎng)景[7]；包括高清晰度、低延遲視頻流、遠(yuǎn)程手術(shù)觸覺互聯(lián)網(wǎng)、虛擬或增強(qiáng)現(xiàn)實(shí)等在內(nèi)的應(yīng)用場(chǎng)景[8].現(xiàn)有的一些延遲保證的研究實(shí)例包括：在5G系統(tǒng)中為了處理和傳達(dá)用戶的上下文信息，系統(tǒng)需要充分保證低的或者可預(yù)測(cè)的數(shù)據(jù)傳輸延遲來(lái)收集和共享上下文信息，并以及時(shí)和自動(dòng)的方式執(zhí)行服務(wù)[9]；“雙十一”期間對(duì)網(wǎng)絡(luò)延遲敏感的在線交易；移動(dòng)端或者電腦端的在線游戲[10]；計(jì)算機(jī)輔助協(xié)同的設(shè)計(jì)與工程[11]和基于網(wǎng)絡(luò)的電子學(xué)習(xí)[12]以及視頻會(huì)議等.對(duì)于服務(wù)提供商來(lái)說為了給用戶提供良好的服務(wù)體驗(yàn)就需要保證服務(wù)延遲在用戶可接受范圍內(nèi).

面臨著基于延遲保證的業(yè)務(wù)激增的現(xiàn)狀，在應(yīng)對(duì)用戶網(wǎng)絡(luò)功能請(qǐng)求的時(shí)候，需要按照不同的服務(wù)鏈順序在網(wǎng)絡(luò)中多個(gè)功能節(jié)點(diǎn)處執(zhí)行對(duì)應(yīng)的請(qǐng)求功能，因?yàn)榫W(wǎng)絡(luò)資源是有限的，這樣以來(lái)就會(huì)帶來(lái)不可忽視的服務(wù)延遲，而過高的服務(wù)延遲將會(huì)降低整體的網(wǎng)絡(luò)性能和用戶體驗(yàn).對(duì)于網(wǎng)絡(luò)中包含大量的服務(wù)延遲敏感型業(yè)務(wù)需求，NFV在資源部署中就需要考慮到服務(wù)延遲對(duì)系統(tǒng)性能的影響，合理的節(jié)點(diǎn)資源分配可以大大減少節(jié)點(diǎn)端的處理延遲，但由于在網(wǎng)絡(luò)功能服務(wù)需要網(wǎng)絡(luò)中特定序列的服務(wù)鏈，網(wǎng)絡(luò)延遲同樣成為實(shí)現(xiàn)網(wǎng)絡(luò)功能服務(wù)中低延時(shí)高質(zhì)量體驗(yàn)的主要障礙[13].因此在虛擬網(wǎng)絡(luò)功能資源調(diào)度中存在的挑戰(zhàn)包括：1)確定流路徑，以正確的順序遍歷合適的處理節(jié)點(diǎn)，以滿足給定服務(wù)鏈的需求；2)在通過現(xiàn)有的虛擬網(wǎng)絡(luò)功能節(jié)點(diǎn)時(shí)考慮節(jié)點(diǎn)負(fù)載和其他動(dòng)態(tài)特征.為實(shí)現(xiàn)有效的服務(wù)協(xié)調(diào)和管理，解決如何快速合理地分配和調(diào)度網(wǎng)絡(luò)資源的問題，目前一些研究文獻(xiàn)[14-16]等在功能節(jié)點(diǎn)處理延遲上取得了矚目的成果，比如文獻(xiàn)[14]考慮到虛擬網(wǎng)絡(luò)功能的位置不確定情況下嵌入移動(dòng)核心虛擬網(wǎng)絡(luò)功能(VNF)的順序，文獻(xiàn)[15]提高了節(jié)點(diǎn)利用率并減少處理節(jié)點(diǎn)對(duì)請(qǐng)求的響應(yīng)延遲.不同于之前的研究，本研究首先以降低資源調(diào)度中總體服務(wù)延遲作為目標(biāo)，然后結(jié)合具體網(wǎng)絡(luò)提供動(dòng)態(tài)性較高的調(diào)度算法，其現(xiàn)實(shí)意義在于使得服務(wù)商能夠滿足更為嚴(yán)格的延遲約束服務(wù)，從而可以為更多的客戶提供良好服務(wù).

考慮到在軟件定義的網(wǎng)絡(luò)和網(wǎng)絡(luò)功能虛擬化共存的背景下，NFV在創(chuàng)建服務(wù)方面更為動(dòng)態(tài)靈活，通過SDN與NFV結(jié)合還可以輕易操縱網(wǎng)絡(luò)流經(jīng)過指定節(jié)點(diǎn)從而實(shí)現(xiàn)各種復(fù)雜的網(wǎng)絡(luò)功能以及靈活的服務(wù)鏈規(guī)則[17].更為具體的解釋即為：SDN控制器借助全網(wǎng)視圖的優(yōu)勢(shì)可下發(fā)細(xì)粒度的規(guī)則到網(wǎng)絡(luò)轉(zhuǎn)發(fā)設(shè)備，網(wǎng)絡(luò)轉(zhuǎn)發(fā)設(shè)備根據(jù)規(guī)則執(zhí)行對(duì)網(wǎng)絡(luò)流的操作，通過這種方式運(yùn)營(yíng)商或者用戶引導(dǎo)網(wǎng)絡(luò)流按照正確的順序經(jīng)過NFs.因此在這項(xiàng)工作中，基于SDN與NFV結(jié)合的研究背景，我們將借助SDN與NFV的優(yōu)勢(shì)，同時(shí)考慮影響網(wǎng)絡(luò)功能總體服務(wù)延時(shí)的多個(gè)因素，通過采用構(gòu)建輔助圖和多路技術(shù)等方式為用戶選擇NFV的有序序列和連接它們的數(shù)據(jù)傳遞路徑，以最小化延遲來(lái)最大程度地保證整體服務(wù)質(zhì)量，具體內(nèi)容將在第2節(jié)和第3節(jié)中詳細(xì)介紹.

1 相關(guān)工作

為了解決虛擬網(wǎng)絡(luò)功能資源調(diào)度的延遲問題，目前一些研究在網(wǎng)絡(luò)功能節(jié)點(diǎn)端的資源調(diào)度方面取得了豐富的成果.其中文獻(xiàn)[14]在延遲限定情況下對(duì)移動(dòng)核心網(wǎng)絡(luò)功能虛擬化映射問題做了研究，它考慮到虛擬網(wǎng)絡(luò)功能的位置不確定情況下嵌入移動(dòng)核心虛擬網(wǎng)絡(luò)功能(VNF)的順序，其延時(shí)限定包括處理、排隊(duì)和傳播引起的延遲.另外為提高節(jié)點(diǎn)利用率并減少處理節(jié)點(diǎn)對(duì)請(qǐng)求的響應(yīng)延遲，文獻(xiàn)[15]提出了基于服務(wù)優(yōu)先級(jí)的加權(quán)服務(wù)鏈放置算法和基于組合優(yōu)化的請(qǐng)求調(diào)度算法.文獻(xiàn)[9]認(rèn)為如今虛擬網(wǎng)絡(luò)功能通常分布式地部署在網(wǎng)絡(luò)邊緣，在5G系統(tǒng)中，動(dòng)態(tài)的服務(wù)需要在分布式和虛擬化的資源設(shè)施中靈活地配置并完成異構(gòu)服務(wù)，在他們的工作中通過組合優(yōu)化選擇虛擬網(wǎng)絡(luò)功能節(jié)點(diǎn)從而達(dá)到最小化的網(wǎng)絡(luò)與處理延遲.文獻(xiàn)[18]通過整數(shù)線性規(guī)劃模型有效地放置虛擬網(wǎng)絡(luò)功能和部署服務(wù)功能鏈，研究?jī)?nèi)容包括虛擬功能節(jié)點(diǎn)數(shù)目，優(yōu)化目標(biāo)包括CPU和帶寬資源消耗以及端到端延遲等.文獻(xiàn)[19]考慮虛擬網(wǎng)絡(luò)功能的傳輸和處理延遲，在這里作者探討了動(dòng)態(tài)虛擬鏈路帶寬分配的好處，作者對(duì)到達(dá)的業(yè)務(wù)通過遺傳算法的帶寬分配的決策處理作為提高網(wǎng)絡(luò)性能的有效手段.在文獻(xiàn)[20]中，研究者們針對(duì)網(wǎng)絡(luò)功能虛擬化服務(wù)商為用戶提供動(dòng)態(tài)靈活的虛擬網(wǎng)絡(luò)功能服務(wù)中面臨的服務(wù)流波動(dòng)問題，作者采用主動(dòng)預(yù)測(cè)流的方式最小化預(yù)測(cè)產(chǎn)生的錯(cuò)誤，并且采用自適應(yīng)的調(diào)整策略，降低虛擬網(wǎng)絡(luò)功能的部署成本.文獻(xiàn)[21]設(shè)計(jì)實(shí)現(xiàn)了NFV-RT系統(tǒng)，此系統(tǒng)的目的是：在云計(jì)算環(huán)境中滿足服務(wù)鏈時(shí)間限定的前提下最大化所接受的服務(wù)鏈請(qǐng)求數(shù)目.文獻(xiàn)[22]通過測(cè)量不同類型的虛擬網(wǎng)絡(luò)功能間協(xié)作干擾，研究不同VNF因競(jìng)爭(zhēng)資源對(duì)性能產(chǎn)生的影響，并根據(jù)測(cè)量結(jié)果給出了更加有效的VNF放置方法，對(duì)于虛擬網(wǎng)絡(luò)功能的研究和應(yīng)用有著顯著的現(xiàn)實(shí)意義.此外，在虛擬網(wǎng)絡(luò)功能負(fù)載均衡對(duì)性能的影響方面，文獻(xiàn)[23]首次提出主要控制荷載(dominant load)的概念作為衡量節(jié)點(diǎn)負(fù)載的標(biāo)準(zhǔn)，研究中提出的解決NFV中多資源負(fù)載均衡問題的優(yōu)化算法比傳統(tǒng)的標(biāo)準(zhǔn)算法更加快捷和高效.

但是，這些調(diào)度方法沒有考慮到如下問題：當(dāng)網(wǎng)絡(luò)存在多個(gè)相同功能點(diǎn)的時(shí)候，采用多點(diǎn)處理方式會(huì)進(jìn)一步降低系統(tǒng)的總體服務(wù)延遲，但前提在多點(diǎn)處理的時(shí)候必須考慮到路徑不對(duì)等帶來(lái)的延遲差異，所以此問題需要結(jié)合具體拓?fù)溆懻摚系难芯恐幸矝]有考慮到網(wǎng)絡(luò)拓?fù)鋯栴}；另外，由于如今網(wǎng)絡(luò)動(dòng)態(tài)性較高，需要提供一種計(jì)算復(fù)雜度和運(yùn)行時(shí)間較低的算法.本研究提出了一種提前構(gòu)建輔助圖，根據(jù)不同服務(wù)鏈間延時(shí)影響分析確定調(diào)度順序而且采用多路傳輸?shù)馁Y源調(diào)度方案，最后設(shè)計(jì)了一種基于貪婪的啟發(fā)式算法，以提高虛擬網(wǎng)絡(luò)資源調(diào)度中保障時(shí)效性的能力.

(一)梁廷燦《歷代名人生卒年表》謂金門詔“生于康熙十二年癸丑”。陶容、于士雄《歷代名人生卒年表補(bǔ)》則對(duì)梁表進(jìn)一步補(bǔ)充，著錄生年一致，卒年則說據(jù)《光緒江都續(xù)志》“年八十卒”，著錄為“乾隆十六年辛未”(北京圖書館出版社2002年版，第504頁(yè))。如果按“生于康熙十二年”而“年八十卒”推算，則金門詔卒年按虛歲當(dāng)為乾隆十七年。另外，查核《光緒江都續(xù)志》并未載金門詔生卒年月，“年八十卒”不知何據(jù)。

2 網(wǎng)絡(luò)與問題模型

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

在問題模型中，我們用S來(lái)表示網(wǎng)絡(luò)服務(wù)集，模型中的|S|代表服務(wù)集S的數(shù)量，[1,|S|]表示1～|S|的整數(shù)集合，其他類似表示以此類推；si表示對(duì)應(yīng)網(wǎng)絡(luò)服務(wù)i的服務(wù)鏈，其中i∈[1,|S|].每條服務(wù)鏈si對(duì)應(yīng)著一系列需要按規(guī)定順序經(jīng)過的網(wǎng)絡(luò)功能，在此用F表示網(wǎng)絡(luò)功能fj的集合，fij表示網(wǎng)絡(luò)服務(wù)i所對(duì)應(yīng)的虛擬網(wǎng)絡(luò)功能fj，(i∈[1,|S|],j∈[1,|Fi|]).在研究中用G=(N,E)來(lái)表示節(jié)點(diǎn)集為N、邊集為E的網(wǎng)絡(luò).此外，不論處理網(wǎng)絡(luò)功能虛擬化虛擬機(jī)是位于服務(wù)器還是交換機(jī)，在這里統(tǒng)一為物理機(jī)，因此都用網(wǎng)絡(luò)節(jié)點(diǎn)N來(lái)表示.不同的虛擬機(jī)節(jié)點(diǎn)可能配備不同的虛擬網(wǎng)絡(luò)功能，因此我們定義虛擬機(jī)集合V={v1,v2,…,vv}中各虛擬機(jī)所配備的功能為虛擬網(wǎng)絡(luò)功能F={f1,f2,…}的子集.比如，如果表示節(jié)點(diǎn)vk的網(wǎng)絡(luò)功能為{f1,f5,f8}，意思就是在虛擬機(jī)vk上只能處理網(wǎng)絡(luò)功能f1,f5和f8.

Fig. 1 Virtual network function scheduling scheme example圖1 虛擬網(wǎng)絡(luò)功能調(diào)度方案示例

在我們的虛擬網(wǎng)絡(luò)功能資源分配優(yōu)化的研究中，使用延遲作為成本度量，因此在網(wǎng)絡(luò)模型中需要包含節(jié)點(diǎn)部分延遲和節(jié)點(diǎn)之間通信的延遲.雖然之前有部分的研究，如文獻(xiàn)[14-16,18]等，在NFV節(jié)點(diǎn)資源調(diào)度帶來(lái)的處理時(shí)延上取得顯著的成果，也有個(gè)別的工作考慮了NFV節(jié)點(diǎn)資源調(diào)度帶來(lái)的傳輸時(shí)延問題[24].在本研究中同時(shí)考慮了網(wǎng)絡(luò)時(shí)延和處理時(shí)延，所謂的網(wǎng)絡(luò)時(shí)延就是在資源分配與調(diào)度時(shí)帶來(lái)的傳輸時(shí)延和傳播時(shí)延.傳輸時(shí)延主要由包的大小和鏈路的傳輸能力決定，如果把某虛擬鏈路傳輸速率表示為bl、某網(wǎng)絡(luò)服務(wù)si需要傳輸?shù)臄?shù)據(jù)包大小表示為Di，傳輸延遲就可以很容易通過Di÷bl算出.而傳播時(shí)延就是在資源調(diào)度時(shí)對(duì)源點(diǎn)與目的節(jié)點(diǎn)的路徑選擇帶來(lái)的延遲，具體的延遲是由對(duì)應(yīng)的網(wǎng)絡(luò)拓?fù)浜蛡鬏敺绞經(jīng)Q定.如果細(xì)分的話網(wǎng)絡(luò)服務(wù)總體延遲還需要包含隊(duì)列時(shí)延，隊(duì)列時(shí)延主要由輸出接口鏈路負(fù)載、調(diào)度策略以及隊(duì)列模型(比如經(jīng)典的MM1模型[25])和緩存區(qū)的大小[19]影響，關(guān)于隊(duì)列已經(jīng)有了很成熟的研究，不屬于本研究的范疇.為了簡(jiǎn)化，本研究遵循文獻(xiàn)[18,24]的設(shè)定，即服務(wù)鏈已知情況下，每個(gè)虛擬節(jié)點(diǎn)最多只能同時(shí)處理一種網(wǎng)絡(luò)功能并且在轉(zhuǎn)發(fā)完一條服務(wù)流之后才能轉(zhuǎn)發(fā)下一條網(wǎng)絡(luò)服務(wù)流.

2.2 問題描述

虛擬網(wǎng)絡(luò)功能的調(diào)度與路由問題的約束有2個(gè)方面：1)維持提供服務(wù)的服務(wù)鏈順序；2)以最小的代價(jià)找到從源到目的地的路徑，在此項(xiàng)研究中的代價(jià)將由延遲來(lái)表示.具體來(lái)說，給定網(wǎng)絡(luò)服務(wù)集，每項(xiàng)服務(wù)是由特定的序列構(gòu)成，在網(wǎng)絡(luò)資源限定的條件之下構(gòu)建模型，根據(jù)規(guī)則序列為所有的用戶流選擇總體服務(wù)時(shí)間最短的網(wǎng)絡(luò)功能實(shí)例和傳輸路徑，通過最小化延遲來(lái)保證網(wǎng)絡(luò)的整體服務(wù)質(zhì)量.為了更好地描述問題，在此以圖1所示的方式表示在虛擬網(wǎng)絡(luò)功能調(diào)度中不同的調(diào)度方案對(duì)最終服務(wù)延遲的影響.在圖1中，存在VM1，VM2，VM3三個(gè)不同的虛擬機(jī)，橢圓表示每個(gè)虛擬機(jī)所配置的網(wǎng)絡(luò)功能，另外還有3種網(wǎng)絡(luò)功能服務(wù)鏈，每種服務(wù)鏈對(duì)應(yīng)不同的網(wǎng)絡(luò)功能.

在圖1(a)中，表示時(shí)間軸的箭頭下方為一種網(wǎng)絡(luò)功能資源調(diào)度方案，此方案中首先由VM1的服務(wù)鏈1中的f1，緊接著是服務(wù)鏈2中的f2，然后經(jīng)過4t的傳輸時(shí)間服務(wù)鏈1接受VM2的f5功能處理，在此期間服務(wù)鏈2必須等待至?xí)r間4t才能得到所需服務(wù)，其他服務(wù)以此類推，最終完成所有服務(wù)總體所耗費(fèi)時(shí)間為11t(由圖2(a)中的VM3-1得到).但是如果采用箭頭上方所示的另外一種方案，也就是在VM1處理完f1和f2時(shí)，調(diào)度的時(shí)候首先選擇傳輸服務(wù)鏈2中f2至VM3，最終可以得到總體所需服務(wù)時(shí)間為10.5t(由圖2(a)中的VM2得到)，由此可知通過控制器對(duì)網(wǎng)絡(luò)功能資源合理調(diào)度就能減少網(wǎng)絡(luò)的總體服務(wù)時(shí)延.另外網(wǎng)絡(luò)中還存在的常見情形就是在網(wǎng)絡(luò)中具備多個(gè)相同功能的服務(wù)節(jié)點(diǎn)(比如有多個(gè)代理服務(wù)器的情況)，或者下一個(gè)服務(wù)功能點(diǎn)同時(shí)受到多個(gè)上游功能節(jié)點(diǎn)制約(比如文獻(xiàn)[17]中的防火墻與監(jiān)聽器并行處理對(duì)應(yīng)著下個(gè)序列的負(fù)載均衡器).如圖1(b)所示，f7同時(shí)受到f6與f3制約，VM1與VM2同時(shí)具備網(wǎng)絡(luò)服務(wù)功能f6，通過計(jì)算選擇VM1與VM2同時(shí)處理服務(wù)鏈3中所需的網(wǎng)絡(luò)功能f6，即使存在傳輸時(shí)延，但通過VM2-1與VM2-2的服務(wù)結(jié)束時(shí)間對(duì)比可得，總體服務(wù)時(shí)延由10.5t降為10.1t，采用上面的調(diào)度方式，網(wǎng)絡(luò)的服務(wù)延遲會(huì)降低，進(jìn)而提升用戶的體驗(yàn).

表1表示的是每個(gè)服務(wù)鏈所需網(wǎng)絡(luò)功能的服務(wù)時(shí)間，我們用時(shí)間片t來(lái)表示，除了服務(wù)鏈1的f1→f5虛擬傳輸時(shí)延為4t以及服務(wù)鏈2的f2→f4和服務(wù)鏈3的f6→f7的傳輸時(shí)延為2t之外，其他的網(wǎng)絡(luò)功能跳轉(zhuǎn)切換虛擬機(jī)的傳輸時(shí)延均為t，比如在服務(wù)鏈2中，VM1處理網(wǎng)絡(luò)功能f1之后跳轉(zhuǎn)到VM2處理網(wǎng)絡(luò)功能f4，所需傳輸時(shí)延為時(shí)間t.以上雖然是為了在圖例中清晰表述而做出的設(shè)定，但在實(shí)際情況中這些都是可以由控制器計(jì)算得出.

Table 1 Required Service Time Value表1 所需服務(wù)時(shí)間值

直觀上來(lái)說，如果存在一個(gè)合理的網(wǎng)絡(luò)功能調(diào)度方案使得對(duì)用戶的服務(wù)延遲最小，在網(wǎng)絡(luò)傳播的時(shí)候選擇，把延遲作為權(quán)重，選擇最短路徑算法(比如Dijkstra)，用戶就能得到總體最小延遲.但是如上所述，當(dāng)網(wǎng)絡(luò)中存在多個(gè)相同功能的網(wǎng)絡(luò)功能節(jié)點(diǎn)時(shí)，不對(duì)等的路徑就會(huì)帶來(lái)額外的延遲.在此我們使用圖2所示的例子來(lái)解釋這些問題，其中實(shí)線的箭頭表示從源s到目的地d的路徑，虛線代表路徑節(jié)點(diǎn)的其他可用鏈接下一跳.比如圖2中選擇源點(diǎn)s到目的地d的一條路徑為{s→u→w→y→d}，其中y為用戶所需服務(wù)節(jié)點(diǎn).但是網(wǎng)絡(luò)中若存在與y節(jié)點(diǎn)功能相同的另外節(jié)點(diǎn)x，如果因?yàn)殒溌坟?fù)載或者多路傳輸減少服務(wù)延遲等原因使x作為網(wǎng)絡(luò)功能服務(wù)節(jié)點(diǎn)，就會(huì)存在途徑x的另一條路徑x.比如現(xiàn)在與網(wǎng)絡(luò)功能虛擬化相關(guān)的部分研究成果文獻(xiàn)[18]和文獻(xiàn)[24]，作者根據(jù)自己的研究目標(biāo)提到在實(shí)現(xiàn)過程中可以考慮采用多路傳輸?shù)姆绞?雖然多路傳輸?shù)姆绞娇梢砸欢ǔ潭冉档途W(wǎng)絡(luò)的總體服務(wù)延遲，但是如果路徑x與路徑y(tǒng)延遲不等就有可能帶來(lái)額外延遲，所以在虛擬網(wǎng)絡(luò)資源調(diào)度時(shí)，如果存在多路傳輸?shù)那闆r，需要把傳播延遲也要考慮其中.

Fig. 2 Multipath transmission example圖2 多路傳輸示例

2.3 問題模型

(1)

(2)

(3)

(4)

(5)

(6)

3 算法設(shè)計(jì)

3.1 算法描述

事實(shí)上，在虛擬網(wǎng)絡(luò)功能調(diào)度與路由問題中，想獲得最佳的資源調(diào)度是一個(gè)組合難題.在基于延遲的虛擬網(wǎng)絡(luò)資源調(diào)度問題中，需要考慮到給定的服務(wù)器或者其他硬件資源的限制，同時(shí)還要服從于虛擬網(wǎng)絡(luò)功能的服務(wù)鏈順序限定，必須為不同的網(wǎng)絡(luò)服務(wù)找到對(duì)應(yīng)的網(wǎng)絡(luò)功能，并且根據(jù)已知的源與目的節(jié)點(diǎn)選取延遲最小的功能執(zhí)行時(shí)隙和路徑延遲，根據(jù)已有的研究結(jié)果可得出，此組合問題為NP難問題[19,25-27].由于網(wǎng)絡(luò)功能資源調(diào)度問題的復(fù)雜度，實(shí)際中尋求最優(yōu)結(jié)果的組合在計(jì)算復(fù)雜度和應(yīng)用時(shí)間上是不現(xiàn)實(shí)的，本研究中我們選擇采用啟發(fā)式貪婪算法作為算法設(shè)計(jì)的基礎(chǔ)思想.

一般來(lái)說，貪婪算法的基本思想是迭代選擇每一步的最佳解決方案，這樣有可能使得最終結(jié)果陷入局部最優(yōu)，但是比起禁忌搜索和遺傳算法等啟發(fā)式算法來(lái)說貪婪算法的好處是運(yùn)算時(shí)間較短，較為適合用戶請(qǐng)求動(dòng)態(tài)性比較高的網(wǎng)絡(luò)場(chǎng)景.我們算法設(shè)計(jì)主要想法是首先將網(wǎng)絡(luò)轉(zhuǎn)換為分步驟處理的輔助圖，然后通過保證延遲的多路徑傳輸算法解決虛擬網(wǎng)絡(luò)功能資源分配的延遲問題.如圖3所示，目標(biāo)是找到原點(diǎn)到D的最短延遲路徑，首先我們先構(gòu)造與圖3類似的輔助圖層，其中實(shí)線代表遵循服務(wù)順序的最短路徑，虛線代表其他路徑或者其他功能節(jié)點(diǎn)路徑.比如圖3中VM1與VM2同時(shí)具備網(wǎng)絡(luò)功能fn，VM3配置的網(wǎng)絡(luò)功能為fn-1，則服務(wù)鏈s2(fn→fn-1)所對(duì)應(yīng)的輔助圖即為S2→S3→S10→D和S2→S7→S10→D，輔助圖邊上的權(quán)重由網(wǎng)絡(luò)傳播延遲計(jì)算可以得出.通過構(gòu)建輔助圖層的方式，加上節(jié)點(diǎn)的處理延遲和傳輸延遲以及等限定，問題就可以轉(zhuǎn)化為在多個(gè)服務(wù)流共存的情況下找到總體延遲最短的路徑.

Fig. 3 Network example and auxiliary figure example圖3 網(wǎng)絡(luò)示例與輔助圖示例

3.2 虛擬網(wǎng)絡(luò)功能延遲服務(wù)算法

算法1. 延時(shí)感知的資源調(diào)度算法(AGM).

步驟1. 預(yù)處理生成輔助圖形.根據(jù)請(qǐng)求服務(wù)集S中循環(huán)獲取服務(wù)si及其對(duì)應(yīng)的服務(wù)功能fij集合，并根據(jù)fij對(duì)應(yīng)的功能節(jié)點(diǎn)集Mfij由Dijkstra算法尋找最短路徑生成si的輔助圖.

步驟2. 根據(jù)構(gòu)建的輔助圖,循環(huán)計(jì)算出各功能節(jié)點(diǎn)所需處理的服務(wù)鏈時(shí)延之和,按照遞減排序?yàn)镸r.

步驟4. 對(duì)比si和sj，如果上游節(jié)點(diǎn)存在多路傳輸?shù)那闆r，選取該項(xiàng)，跳轉(zhuǎn)到步驟5；否則對(duì)si和sj項(xiàng)做交叉對(duì)比處理時(shí)延和傳輸時(shí)延的差值，選取絕對(duì)值最小的服務(wù)項(xiàng)，若下游節(jié)點(diǎn)存在多個(gè)可選功能節(jié)點(diǎn)對(duì)網(wǎng)絡(luò)服務(wù)功能流進(jìn)分解，跳轉(zhuǎn)到步驟5.

步驟5. 多路傳輸處理，若存在多個(gè)可選功能節(jié)點(diǎn)，根據(jù)服務(wù)延時(shí)和路徑時(shí)延計(jì)算比例函數(shù)，然后根據(jù)比例函數(shù)θj分別進(jìn)行傳輸，θj由下式算出：

鑒于本研究的目標(biāo)是最小化服務(wù)延遲與節(jié)點(diǎn)之間通信的延遲，我們的算法循環(huán)原則是從資源沖突最大的功能節(jié)點(diǎn)中優(yōu)先選取對(duì)其他服務(wù)延時(shí)影響最小和能多點(diǎn)同時(shí)處理的服務(wù)鏈.算法中dij代表選定服務(wù)項(xiàng)si所在路徑與備選點(diǎn)之間的路徑延遲差值，其中比例函數(shù)θj可以由用戶根據(jù)實(shí)際情況定義，比如下游節(jié)點(diǎn)負(fù)載，在這里采用和文獻(xiàn)[24]類似的想法，但是目標(biāo)是采用路徑總體延遲等價(jià)的比例因子.因?yàn)镈ijkstra算法的時(shí)間復(fù)雜度為O(n2)，其中n代表的是網(wǎng)絡(luò)圖中的節(jié)點(diǎn)個(gè)數(shù)，考慮在l條邊的圖中有k條服務(wù)鏈請(qǐng)求中，每條服務(wù)最多包含m(m≤n)個(gè)功能節(jié)點(diǎn)，則求每個(gè)節(jié)點(diǎn)到目的節(jié)點(diǎn)的路徑需要的時(shí)間花費(fèi)為O(k×(l+mlogm))，因此算法的復(fù)雜度為O(n2+k×(l+mlogm)).

4 實(shí)驗(yàn)結(jié)果與分析

在本節(jié)中，我們對(duì)本研究中虛擬網(wǎng)絡(luò)功能調(diào)度和資源分配方法在延遲方面的性能進(jìn)行了數(shù)值評(píng)估，通過與資源調(diào)度中的先來(lái)先服務(wù)方案對(duì)比得到延時(shí)性能提升比例，證明本研究方案的可行性和優(yōu)越性.

4.1 實(shí)驗(yàn)設(shè)置與案例分析

在實(shí)驗(yàn)中我們使用與文獻(xiàn)[18]和文獻(xiàn)[20]相同的處理延時(shí)和傳輸延時(shí)設(shè)定，首先設(shè)定每個(gè)功能的處理時(shí)間隨機(jī)選擇區(qū)間為10～20 ms，對(duì)應(yīng)的傳輸時(shí)延從5～20 ms中隨機(jī)選擇，并且保證每個(gè)網(wǎng)絡(luò)功能至少配置在一個(gè)VM節(jié)點(diǎn)中.

Fig. 4 Performance increase ratio of scheduling in simulated network topology圖4 模擬的網(wǎng)絡(luò)拓?fù)渲姓{(diào)度方案性能提升比例

在第1個(gè)實(shí)驗(yàn)案例中，采用了圖3的例子對(duì)研究方案性能進(jìn)行分析，在圖3的3個(gè)VM節(jié)點(diǎn)中一共隨機(jī)設(shè)定了5種網(wǎng)絡(luò)功能，并且保證有2個(gè)節(jié)點(diǎn)存在相同的網(wǎng)絡(luò)功能;然后進(jìn)行了1 000次的循環(huán)實(shí)驗(yàn)，每次實(shí)驗(yàn)中都隨機(jī)生成40條服務(wù)鏈請(qǐng)求并隨機(jī)選擇具備重復(fù)功能的節(jié)點(diǎn);最后得到圖4所示結(jié)果.圖4中圓點(diǎn)代表我們的調(diào)度方案與隨機(jī)的先來(lái)先服務(wù)調(diào)度方案在延時(shí)性能的提升比值(用AGM表示)，可以看出在這些實(shí)驗(yàn)室中性能比例提升大部分都落在0.2～0.4的區(qū)間內(nèi)，也就是20%～40%；星號(hào)點(diǎn)代表采用多路傳輸來(lái)同時(shí)處理相同網(wǎng)絡(luò)功能在延時(shí)性能提升方面所占的比例(用MR表示)，觀察得出提升比率在5%～15%的區(qū)間.另外在文獻(xiàn)[20]中提到，在資源調(diào)度中，對(duì)于一個(gè)5個(gè)節(jié)點(diǎn)的小型網(wǎng)絡(luò)(對(duì)應(yīng)的遺傳算法運(yùn)行時(shí)間為0.45 s)，解決這個(gè)問題的最優(yōu)解運(yùn)行時(shí)間高達(dá)1 000 s，而我們的算法平均執(zhí)行時(shí)間為0.16 s；而在具有2個(gè)網(wǎng)絡(luò)服務(wù)的10個(gè)節(jié)點(diǎn)網(wǎng)絡(luò)中，模型運(yùn)行時(shí)獲得最佳解決方案是按小時(shí)進(jìn)行的.綜上可以看出，我們基于貪婪的算法設(shè)計(jì)能更好地適應(yīng)于網(wǎng)絡(luò)的動(dòng)態(tài)性需求.

Fig. 5 Performance increase ratio of scheduling in real network topology圖5 真實(shí)網(wǎng)絡(luò)拓?fù)渲姓{(diào)度方案性能提升比例

Fig. 6 Delay comparison for different schedules圖6 不同調(diào)度方案延時(shí)對(duì)比

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

本文針對(duì)網(wǎng)絡(luò)功能虛擬化資源分配與調(diào)度過程中任務(wù)的調(diào)度順序和傳輸方式影響網(wǎng)絡(luò)總體服務(wù)延時(shí)的問題，本研究根據(jù)對(duì)服務(wù)鏈之間調(diào)度造成的延遲影響轉(zhuǎn)移到其他能夠降低該延遲的服務(wù)鏈順序和多個(gè)處理節(jié)點(diǎn)之上的思路，提出創(chuàng)建輔助圖與多點(diǎn)處理的策略，然后借助輔助圖的簡(jiǎn)潔性設(shè)計(jì)了滿足網(wǎng)絡(luò)動(dòng)態(tài)需求的啟發(fā)式算法，實(shí)現(xiàn)對(duì)虛擬網(wǎng)絡(luò)資源的合理調(diào)度并采用了多路傳輸方式進(jìn)一步減少資源調(diào)度對(duì)總體服務(wù)延遲的影響.最后，通過模擬實(shí)驗(yàn)結(jié)果顯示，本研究能夠有效提高虛擬化網(wǎng)絡(luò)功能時(shí)效性的能力，減少虛擬網(wǎng)絡(luò)功能服務(wù)系統(tǒng)的總體服務(wù)延遲.

[1]Guerzoni R. Network functions virtualization: An introduction, benefits, enablers, challenges and call for action, introductory white paper[C]Darmstadt. SDN and OpenFlow World Congress, 2012 [2017-11-01]. https:portal.etsi.orgnfvnfv_white_paper.pdf

[2]Kreutz D, Ramos F M V, Verissimo P E, et al. Software-defined networking: A comprehensive survey[J]. Proceedings of the IEEE, 2015, 103(1): 14-76

[3]Yu Tao, Bi Jun, Wu Jianping. Research on the future virtualization of the Internet[J]. Journal of Computer Research and Development, 2015, 52 (9): 2069-2082 (in Chinese)(余濤, 畢軍, 吳建平. 未來(lái)互聯(lián)網(wǎng)虛擬化研究[J]. 計(jì)算機(jī)研究與發(fā)展, 2015, 52(9): 2069-2082)

[4]Bremler-Barr A, Harchol Y, Hay D. OpenBox: A software-defined framework for developing, deploying, and managing network functions[C]Proc of the 2016 ACM SIGCOMM Conf (SIGCOMM’16). New York: ACM, 2016: 511-524

[5]Qazi Z A, Tu C C, Chiang L, et al. SIMPLE-fying middlebox policy enforcement using SDN[J]. ACM SIGCOMM Computer Communication Review, 2013, 43(4): 27-38

[6]Herrera J G, Botero J F. Resource allocation in NFV: A comprehensive survey[J]. IEEE Trans on Network and Service Management, 2016, 13(3): 518-532

[7]Cui Xingcan, Yu Xiaohui, Liu Yang, et al. A survey of distributed stream processing technology[J]. Journal of Computer Research and Development, 2015, 52(2): 318-332 (in Chinese)(崔星燦, 禹曉輝, 劉洋, 等. 分布式流處理技術(shù)綜述[J]. 計(jì)算機(jī)研究與發(fā)展, 2015, 52(2): 318-332)

[8]Cziva R, Pezaros D P. On the latency benefits of edge NFV[C]Proc of the Symp on Architectures for Networking and Communications Systems. Piscataway, NJ: IEEE, 2017: 105-106

[9]Martini B, Paganelli F, Cappanera P, et al. Latency-aware composition of virtual functions in 5G[C]Proc of the 1st IEEE Conf on Network Softwarization (NetSoft 2015).Piscataway, NJ: IEEE, 2015: 1-6

[10]Claypool M, Claypool K. Latency can kill: Precision and deadline in online games[C]Proc of the 1st Annual ACM SIGMM Conf on Multimedia Systems (MMSys’10). New York: ACM, 2010: 215-222

[11]Agustina, Liu Fei, Xia S, et al. CoMaya: Incorporating advanced collaboration capabilities into 3D digital media design tools[C]Proc of the 2008 ACM Conf on Computer Supported Cooperative Work. New York: ACM, 2008: 5-8

[12]Ahmad L, Boukerche A, Al Hamidi A, et al. Web-based e-learning in 3D large scale distributed interactive simulations using HLARTI [C]Proc of the 2008 IEEE Int Symp on Parallel and Distribution Processing. Piscataway, NJ: IEEE, 2008: 1-4

[13]Zheng Hanying, Tang Xueyan. Analysis of server provisioning for distributed interactive applications[J]. IEEE Trans on Computers, 2015, 64(10): 2752-2766

[14]Baumgartner A, Reddy V S, Bauschert T. Combined virtual mobile core network function placement and topology optimization with latency bounds[C]Proc of the 4th European Workshop on Software Defined Networks (EWSDN). Piscataway, NJ: IEEE, 2015: 97-102

[15]Zhang Qixia, Xiao Yikai, Liu Fangming, et al. Joint optimization of chain placement and request scheduling for network function virtualization[C]Proc of the 37th IEEE Int Conf on Distributed Computing Systems (ICDCS 2017). Piscataway, NJ: IEEE, 2017: 731-741

[16]Xia Ming, Shirazipour M, Zhang Ying, et al. Network function placement for NFV chaining in packetoptical datacenters[J]. Journal of Lightwave Technology, 2015, 33(8): 1565-1570

[17]Sun Chen, Bi Jun, Zheng Zhilong, et al. NFP: Enabling network function parallelism in NFV[C]Proc of the Conf of the ACM Special Interest Group on Data Communication. New York: ACM, 2017: 43-56

[18]Luizelli M C, Bays L R, Buriol L S, et al. Piecing together the NFV provisioning puzzle: Efficient placement and chaining of virtual network functions[C]Proc of 2015 IFIPIEEE Int Symp on Integrated Network Management. Piscataway, NJ: IEEE, 2015: 98-106

[19]Qu Long, Assi C, Shaban K. Delay-aware scheduling and resource optimization with network function virtualization[J]. IEEE Trans on Communications, 2016, 64(9): 3746-3758

[20]Fei Xincai, Liu Fangming, Xu Hong, et al. Adaptive VNF scaling and flow routing with proactive demand prediction [C]Proc of IEEE Int Conf on Computer Communications (INFOCOM 2018). Piscataway, NJ: IEEE, 2018 [2018-01-20]. http:grid.hust.edu.cnfmliuvnf-scaling-infocom18.pdf

[21]Li Yang, Phan L T X, Loo B T. Network functions virtualization with soft real-time guarantees[C]Proc of the 35th Annual IEEE Int Conf on Computer Communications. Piscataway, NJ: IEEE, 2016: 1-9

[22]Zeng Chaobing, Liu Fangming, Chen Shutong, et al. Demystifying the performance interference of co-located virtual network functions [C]Proc of IEEE Int Conf on Computer Communications (INFOCOM 2018). Piscataway, NJ: IEEE, 2018 [2018-01-20]. http:grid.hust.edu.cnfmliuvnf-interference-infocom18.pdf

[23]Wang Tao, Xu Hong, Liu Fangming. Multi-resource load balancing for virtual network functions[C]Proc of the 37th IEEE Int Conf on Distributed Computing Systems (ICDCS 2017). Piscataway, NJ: IEEE, 2017: 1322-1332

[24]Huang Huawei, Guo Song, Wu Jinsong, et al. Joint middlebox selection and routing for software-defined networking[C]Proc of 2016 IEEE Int Conf on Communications (ICC). Piscataway, NJ: IEEE, 2016: 1-6

[25]Mijumbi R, Serrat J, Gorricho J L, et al. Design and evaluation of algorithms for mapping and scheduling of virtual network functions[C]Proc of the 1st IEEE Conf on Network Softwarization (NetSoft 2015). Piscataway, NJ: IEEE, 2015: 1-9

[26]Riera J F, Escalona E, Batalle J, et al. Virtual network function scheduling: Concept and challenges[C]Proc of the 2014 Int Conf on Smart Communications in Network Technologies (SaCoNeT). Piscataway, NJ: IEEE, 2014: 1-5

[27]Nakibly G, Cohen R, Katzir L. Optimizing data plane resources for multipath flows[J]. IEEEACM Trans on Networking, 2015, 23(1): 138-147

[28]Mahajan R, Spring N, Wetherall D, et al. Inferring link weights using end-to-end measurements[C]Proc of the 2nd ACM SIGCOMM Workshop on Internet Measurement. New York: ACM, 2002: 231-236

XuRan, born in 1988. PhD candidate at the State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications, Beijing, China. His main research interests include software-defined networking and network function virtualization.