徐 冉 王文東 龔向陽 闕喜戎

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

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

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

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

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

1 相關(guān)工作

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

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

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

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

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

在問題模型中，我們用S來表示網(wǎng)絡(luò)服務(wù)集，模型中的|S|代表服務(wù)集S的數(shù)量，[1,|S|]表示1～|S|的整數(shù)集合，其他類似表示以此類推；si表示對應(yīng)網(wǎng)絡(luò)服務(wù)i的服務(wù)鏈，其中i∈[1,|S|].每條服務(wù)鏈si對應(yīng)著一系列需要按規(guī)定順序經(jīng)過的網(wǎng)絡(luò)功能，在此用F表示網(wǎng)絡(luò)功能fj的集合，fij表示網(wǎng)絡(luò)服務(wù)i所對應(yīng)的虛擬網(wǎng)絡(luò)功能fj，(i∈[1,|S|],j∈[1,|Fi|]).在研究中用G=(N,E)來表示節(jié)點集為N、邊集為E的網(wǎng)絡(luò).此外，不論處理網(wǎng)絡(luò)功能虛擬化虛擬機是位于服務(wù)器還是交換機，在這里統(tǒng)一為物理機，因此都用網(wǎng)絡(luò)節(jié)點N來表示.不同的虛擬機節(jié)點可能配備不同的虛擬網(wǎng)絡(luò)功能，因此我們定義虛擬機集合V={v1,v2,…,vv}中各虛擬機所配備的功能為虛擬網(wǎng)絡(luò)功能F={f1,f2,…}的子集.比如，如果表示節(jié)點vk的網(wǎng)絡(luò)功能為{f1,f5,f8}，意思就是在虛擬機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é)點部分延遲和節(jié)點之間通信的延遲.雖然之前有部分的研究，如文獻[14-16,18]等，在NFV節(jié)點資源調(diào)度帶來的處理時延上取得顯著的成果，也有個別的工作考慮了NFV節(jié)點資源調(diào)度帶來的傳輸時延問題[24].在本研究中同時考慮了網(wǎng)絡(luò)時延和處理時延，所謂的網(wǎng)絡(luò)時延就是在資源分配與調(diào)度時帶來的傳輸時延和傳播時延.傳輸時延主要由包的大小和鏈路的傳輸能力決定，如果把某虛擬鏈路傳輸速率表示為bl、某網(wǎng)絡(luò)服務(wù)si需要傳輸?shù)臄?shù)據(jù)包大小表示為Di，傳輸延遲就可以很容易通過Di÷bl算出.而傳播時延就是在資源調(diào)度時對源點與目的節(jié)點的路徑選擇帶來的延遲，具體的延遲是由對應(yīng)的網(wǎng)絡(luò)拓撲和傳輸方式?jīng)Q定.如果細分的話網(wǎng)絡(luò)服務(wù)總體延遲還需要包含隊列時延，隊列時延主要由輸出接口鏈路負載、調(diào)度策略以及隊列模型(比如經(jīng)典的MM1模型[25])和緩存區(qū)的大小[19]影響，關(guān)于隊列已經(jīng)有了很成熟的研究，不屬于本研究的范疇.為了簡化，本研究遵循文獻[18,24]的設(shè)定，即服務(wù)鏈已知情況下，每個虛擬節(jié)點最多只能同時處理一種網(wǎng)絡(luò)功能并且在轉(zhuǎn)發(fā)完一條服務(wù)流之后才能轉(zhuǎn)發(fā)下一條網(wǎng)絡(luò)服務(wù)流.

2.2 問題描述

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

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

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

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

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

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

2.3 問題模型

(1)

(2)

(3)

(4)

(5)

(6)

3 算法設(shè)計

3.1 算法描述

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

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

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

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

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

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

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

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

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

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

4 實驗結(jié)果與分析

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

4.1 實驗設(shè)置與案例分析

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

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

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

Fig. 5 Performance increase ratio of scheduling in real network topology圖5 真實網(wǎng)絡(luò)拓撲中調(diào)度方案性能提升比例

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

5 結(jié)束語

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