一種競拍機制下的低時延服務功能鏈部署算法

趙季紅，季文君，曲 樺，吳豆豆

(1.西安郵電大學 通信與信息工程學院,陜西 西安 710121; 2.西安交通大學 電信學院，陜西 西安 710054)

在傳統網絡中，網絡功能直接部署在專有硬件設備上，如網絡地址轉換、負載均衡、防火墻、網關和入侵檢測等功能[1]。傳統的部署方式降低了網絡適應社會發展和變化的能力。此外，為滿足用戶的需求，運營商需部署更具專業化的網絡功能，將導致巨額的投資成本和運營成本,而由此產生的網絡膨脹和高昂的建設成本阻礙著網絡的進步和發展[2]。隨著社會和技術的快速發展，用戶所需網絡功能的數量和類型呈幾何式增加。為此，網絡功能虛擬化(Network Function Virtualization,NFV)作為一種能夠根據用戶需求快速、靈活地部署網絡功能的新技術，為網絡的發展提供了新的解決方案[3]。軟件定義網絡(Software Defined Network,SDN)利用OpenFlow技術將網絡的控制平面和數據平面分離，通過軟件實現集中控制，加速網絡的創新周期[4]。

為了更好地應對多樣化的應用場景和差異化的服務質量要求(Quality of Service,QoS)，SDN/NFV協同的未來網絡架構作為第5代移動通信(5th Generation Mobile Networks,5G)網絡技術領域中的革新技術，為運營商的發展帶來機遇和挑戰[5]。為部署5G網絡，網絡運營商正在轉向虛擬化網絡功能(Virtualized Network Function,VNF)，與易于出現故障的專用硬件相比，VNF僅需較少的維護便可提供更高的靈活性[6]。服務功能鏈(Service Function Chains,SFC)作為網絡虛擬技術中的一種常見用例，能夠使網絡運營商和基礎設施提供商在軟件定義的虛擬網絡上的各個位置靈活地協調VNF[7]。

隨著5G商用服務的到來，一大批新興應用對時延保障問題提出了新的要求[8]。以4K技術為例，其要求的網絡時延需在12～17 ms之間，虛擬現實(Virtual Reality,VR)技術要求端到端時延需小于7 ms。然而，對于超高可靠超低時延通信場景(ultra Reliable & Low Latency Communication,uRLLC)要求業務端到端時延為3～5 ms，以時延更為敏感的車聯網場景為例，業界公認的時延需小于3 ms[9]。

在相關研究中，文獻[10]為低時延服務提出一種成本高效的服務功能鏈編排方法，通過引入深度學習算法和交叉熵為用戶提供具有優異性能和低資源成本的SFC，但是該算法具有較高的時間復雜度，不適用于大規模網絡中SFC的部署，且較高的算法時間復雜度終將影響服務的端到端時延。文獻[11]提出了一種基于時延感知的VNF選擇算法，通過選擇合適的VNF控制SFC的端到端時延，在實際網絡環境中該選擇算法會使網絡資源逐步向高等級用戶集中，資源的不平衡將直接影響用戶的接受率。文獻[12]提出一種服務可持續的自主資源調整算法，通過動態資源調整實現用戶時延要求的實時保障，其優點在于保證了服務的可持續性，局限性在于該算法適用于小范圍內的資源調整，對整個服務功能鏈的低時延保障能力有限。基于QoS感知的VNF部署模型[13]，在時延約束中考慮虛擬化開銷帶來的時延變化，但是其局限性在于缺少對網絡資源環境的感知，在處理時延敏感型服務請求時無法為其提供低時延保障。在文獻[14]提出的基于機器學習的SFC部署算法中，時延模型以流量負載和CPU利用率為特征，利用隨機森林回歸對VNF處理時延進行預測，雖然體現出對當前網絡狀態的感知，但是缺少對底層網絡資源的優化，SFC部署的成功率也會因此受限于當前網絡資源環境的狀態。

基于上述研究成果及不足之處，在對時延敏感型服務功能鏈部署算法進行設計時，主要考慮了以下3個方面的內容：1)以保障服務的低時延要求為基本前提；2)對時延敏感型服務進行底層資源的優化設計，通過對底層資源的競拍實現資源利用率的提升，進而實現對運營商利益的保障，推動網絡虛擬技術的發展；3)保證部署算法具有較低的時間復雜度。

在SDN/NFV協同的未來網絡中，針對時延敏感型服務功能鏈的部署問題，基于網絡資源環境的實時變化，先利用資源優化模型實現服務功能鏈對底層資源的高效利用，通過引入拍賣模型平衡時延要求與高資源利用率間的關系。再將博弈論中的拍賣模型引入服務功能鏈的部署問題中，并且擬提出一種啟發式多路徑拍賣(Multi-Path Auction,MPA)算法，MPA基于博弈論中的競爭與激勵機制，通過網絡資源競爭實現SFC的最終部署，即為時延敏感型服務提供一種資源高效的服務功能鏈的部署算法。

1 方法概述

1.1 網絡模型

首先，將物理網絡抽象為一個加權無向圖G=(N,L)，對應網絡場景，N代表底層網絡服務器節點集合，L表示連接服務器節點的鏈路集合，每個節點服務器n∈N配置有一定大小的處理器(Central Processing Unit,CPU)和存儲資源，每一條物理鏈路ln∈L配置有一定大小的帶寬資源。其次，定義服務請求與服務功能鏈一一對應，用s={(np,nt);V}表示用戶的服務請求，其中：np∈N表示服務請求的源節點；nt∈N表示服務請求的目的節點；V∈{A,B,C,D,E}表示該服務請求所需的VNF集合。

1.2 問題描述

設服務請求s={(n1,n3);(A,B,C)}，服務功能鏈r1和r2均可為該用戶提供所需服務，但是兩條服務功能鏈在節點和鏈路資源配置上存在明顯差異，在應對相同的服務請求時，兩條服務功能鏈對底層資源的利用率也會存在高低的差異，不同服務功能鏈資源配置如圖1所示。

不同的部署方案會顯著影響通信時延，從而影響SFC的性能和用戶體驗?？紤]VNF處理時延取決于所部署節點的資源配置，包括該服務器的CPU和存儲資源的利用率，而傳輸時延主要取決于網絡擁塞程度。為滿足用戶更低的時延要求，可以通過提高VNF的CPU和存儲資源的配置降低其處理時延，通過平衡鏈路帶寬資源的利用率，避免交換機的擁塞排隊可以降低傳輸時延?；谫Y源配置與時延間的關系，考慮在實際的網絡環境中：一方面，對于時延敏感型服務，為保證用戶更低的時延要求需要為其服務功能鏈配置更多的底層資源，以實現服務請求的正常交付，避免因服務協議(Service Level Agreement,SLA)的違規造成不必要的經濟損失；另一方面，網絡運營商需要通過不斷提高對底層資源的利用率降低投資成本和運營成本。因此，保證對底層資源高效利用的時延敏感型服務功能鏈的部署問題亟待解決。

1.3 拍賣原理

經濟學理論中的拍賣模型越來越多地被應用在通信領域的網絡資源分配問題中。拍賣模型按照不同的拍賣規則分為公開拍賣和密封拍賣兩種，其中常用的拍賣模型有公開增價拍賣、公開減價拍賣、一級密封拍賣和二級密封拍賣。

公開增價拍賣又稱英式拍賣，在該拍賣過程中，賣家進行由低到高的階梯式喊價，買家通過舉手參與競拍，在賣家不斷提高價格的過程中有買家退出競拍，當買家僅剩一人時拍賣結束，此時的拍品價格即為成交價格。英式拍賣有以下4個特點：1)公開競價，即拍品對每一個潛在的競拍者具有相同的價值，但競拍者對拍品的估價會因各自利益的考量而不同；2)競價逐輪上升至僅剩一位競拍者為止；3)拍品由最高競價者得；4)最高競價者支付款項。拍賣的目標是保證帕累托效率，即拍品由最高估價者得。整個拍賣模型中包含競拍者對拍品的估價e、拍品的成本c、成交價g和競拍者收益u等幾個重要參數。

在SFC部署問題中引入英式拍賣模型，以實現服務功能鏈底層資源的合理配置。在利用拍賣模型表述服務功能鏈部署問題中存在的競爭關系時，將其具體表述為當服務請求到達時，滿足該服務請求的備選路徑間存在競爭關系，即圖1中r1和r2的關系，通過競拍流程平衡服務請求的時延要求與底層資源占用間的關系，包括CPU、存儲和鏈路資源。因此，整個服務功能鏈的部署過程被分為路徑發現模塊和拍賣競爭模塊兩個部分。當用戶請求到達時，基于資源優化模型的路徑發現模塊確定該SFC的備選路徑集合，再基于拍賣模型的競拍流程確定當前虛擬網絡(Virtual Network,VN)中滿足用戶時延要求且資源成本最小的SFC，所得SFC部署方案即為最終輸出。

實際網絡環境中的上述競爭過程存在天然的約束，即拍品對每一個競拍者有一份私有價值，其他競拍者不知道該價值，拍賣的目標是使成功部署的服務功能鏈具有對低時延的保證能力和更高的底層資源的利用率。

2 路徑發現模塊

2.1 資源優化模型

當給定一物理網絡拓撲，SFC部署的目標是確定VNF最優的放置節點以及虛擬鏈路到物理鏈路的映射關系，同時保證資源成本的最小化。因此，所提資源優化模型的輸出結果為一組嵌入在底層網絡上的鏈式有序的VNF，定義優化目標為最小化SFC占用的底層資源成本，并通過約束條件保證模型的有效性，需滿足的約束有節點資源約束、鏈路約束、實例化約束和流量守恒約束。資源優化模型的目標函數為

鏈路約束保證物理鏈路具有的帶寬資源hln能夠成功映射虛擬鏈路lv∈Lv，將其表示為

?s∈S,?n∈N,?v∈V

流量守恒約束保證除源節點和目的節點外的其他部署節點均處于流量平衡狀態，將該約束表示為

2.2 路徑發現流程

路徑發現流程是基于資源優化模型提出的，主要目的是確定備選路徑集合R={r1,r2,…,rn}，集合中的ri∈R代表該鏈路是一條基于資源優化模型確定的且滿足用戶服務請求的SFC，同時，?ri∈R滿足ri∩rj=?,i≠j的條件。

定義競拍決策為二進制決策變量，其表達式為

3 競爭拍賣模塊

3.1 拍賣模型

確定備選路徑集合后，拍賣模型的目標是通過備選路徑ri∈R間的競拍實現服務請求的最終部署，即到達的服務請求作為拍賣者，多條備選路徑為競拍者，輸出的是滿足用戶低時延要求的且資源成本最小的SFC。

在競拍過程中，競拍者給出的估價與競拍者自身擁有的資源配置有關，體現在ri的資源成本和其時延表現上。將SFC中的時延問題劃分為處理時延和傳輸時延。處理時延主要取決于所有承載VNF的物理節點的處理負載，即總處理需求與節點處理能力的比率關系，表示為

傳輸時延主要取決于在傳輸數據流的過程中涉及的所有物理節點間的鏈路利用率，即總流量請求與鏈路容量之比，表達式為

利用M/M/1排隊模型對排隊和處理時延進行建模并計算[13]，得出部署在節點n處的虛擬網絡功能v所需處理時延，表示為

同理，節點n處的排隊時延可表示為

將備選路徑ri的時延計算表示為

對數據進行標準化處理，估價ei與ri的資源成本f和時延δ有關，但是數據f和δ并不在同一量級，需要將數據資源成本和時延歸一化到區間[a,β]范圍內，表示為

其中，參數a=-100，β=100。

對數據進行同趨化處理，競拍者基于自身資源配置的差異給出的估價各不相同，時延越低給出的估價越高，資源成本越低給出的估價越高，而競拍者的估價越高在競拍中越會占有優勢，數據性質不同便無法正確反映不同作用力的綜合結果，因此，通過改變逆指標數據的性質使所有指標對估價的作用力同趨化。競拍者ri給出的估價為

ei=-(δ′+f′)

競拍過程中，利用拍賣者的收益實現SFC的時延約束。拍賣者的收益是在第j輪競拍中ri給出的成交價減去拍品成本，可表示為

φij=gij-ci

其中，拍品的成本與服務請求的最低時延要求δq有關，通過將δq標準化處理得到δ′q，最后的成交價將由最高估價給出，并考慮通過拍賣者收益實現時延約束，將拍品成本定義為

ci=-(δ′q+f′)

進而有，φij>0時，表示滿足時延要求，φij<0時，表示競拍者ri的時延不滿足服務要求。

3.2 競拍流程

競拍中，服務請求作為拍賣方，集合R中的備選路徑組成具有多個競拍者的競拍者集合，通過拍賣獲得對服務請求的SFC部署的權限。針對時延敏感型服務部署過程中存在的資源優化欠缺的問題，通過競拍流程在保證時延服務低時延要求前提下實現其對底層資源利用率的提升。具體的MPA算法如下。

輸入：服務功能鏈備選路徑集R，

物理網絡拓撲G=(N,L)。

輸出：服務功能鏈部署方案ro

步驟1?ri∈R獲取估價集合E={e1,e2,…,en}。

步驟2對E中的元素進行循環計算。

步驟3排序獲取最高估價者r′i和e′i，若估價相同則占用物理節點較少的路徑優先。

步驟4拍賣方將此輪成交價gij廣播給競拍方。

步驟5如果φij>0，則跳出循環。

步驟6或者將xn賦值為 0。

步驟7輸出服務功能鏈部署策略。

4 仿真結果

4.1 實驗設置

通過仿真實驗，驗證所提MPA算法各個性能的有效性。對比算法選擇經典貪心最短路徑(Greedy Shortest Path,GSP)算法和文獻[10]提出的反饋調整(Closed-Loop Feedback,CLF)算法。其中，GSP算法通過尋求最短路徑實現SFC端到端時延的最小化，CLF算法通過結合網絡功能的整合分裂和尋求長度受限的最短路徑實現SFC的部署，同時，引入深度學習算法進行反饋調整以進一步提高部署的成功率，并且該算法的目的同樣是為低時延服務提供一種成本高效的服務功能鏈部署方法。仿真中選擇和比較的性能參數主要有用戶接受率、時延、部署時間以及資源利用率。

利用輕量級軟件定義網絡和測試平臺mininet繪制物理網絡拓撲，底層網絡拓撲如圖2所示，包含有24個節點和43條鏈路，鏈路上的數字表示鏈路通信延遲，單位為ms。

圖2 底層網絡拓撲

首先，定義實驗中資源配置包括鏈路的帶寬資源以及節點中的CPU資源和存儲資源。其次，將所有節點的CPU和存儲資源隨機設置在10～20個單位之間，并將鏈接資源隨機設置在50～100個單位之間。在實際的網絡環境中，VN在長期為用戶提供服務的過程中即使是相同類型VNF，其資源配置也存在差異，因此，實驗中對網絡拓撲中每個節點服務器進行初始化，使得每個節點中的VNF類型和資源配置不盡相同。

4.2 實驗結果分析

針對時延敏感型服務的底層資源配置問題，3種不同算法的用戶接受率對比情況，如圖3所示。

圖3 3種不同算法的用戶接受率對比

由圖3可以看出，所提的MPA算法在用戶接受率方面的性能表現明顯優于CLF和GSP算法。實驗中：對于CLF算法，當SFC的長度大于5個單位時其用戶接受率低于90%；對于GSP算法，其平均用戶接受率僅為73.5%，在面對用戶連接數密度較大的情境時，將嚴重影響SFC部署的成功率，進而影響用戶體驗；對于所提的MPA算法，即使在SFC長度不斷增加的情況下(SFC的長度從4個單位增加到8個單位)，MPA算法的用戶接受率依然穩定在90%以上。

服務功能鏈在不同長度下的時延對比情況如圖4所示。

圖4 3種不同算法的時延對比情況

由圖4可以看出，與GSP算法相比，所提的MPA算法同時考慮了時延與資源成本的雙重指標，避免陷入局部最優，并且SFC的時延降低了29%左右。在時延敏感型服務的低時延保障方面，與CLF算法相比，MPA算法同樣具有優異的表現。

3種部署算法的部署時間對比情況，如圖5所示。

圖5 3種不同算法的部署時間對比

CLF算法通過整合和拆分虛擬網絡功能實現底層資源利用率的提升，并利用反饋調整模塊實現節點和鏈路的資源調整，整個算法時間復雜度較高。實際的網絡環境中，對VNF整合拆分的時間以及映射過程中反饋調整的時間都將額外增加部署時間的成本，最終作用在鏈路的時延上，在實驗中該時間成本設置為一個范圍在[5,8]的隨機值。實驗結果表明，MPA算法的部署時間始終低于CLF和GSP算法。對于時延敏感型服務更低的SFC部署時間成本將顯著改善用戶體驗，有利于保障運營商和用戶的利益。

3種不同算法的資源利用率對比情況，如圖6所示。

圖6 3種不同算法的資源利用率對比情況

由圖6可以看出，與其他兩種算法對比，所提的MPA算法對底層資源利用率更加高效。與CLF算法相比，并結合時延方面的性能表現，MPA算法在保證低時延要求的前提下，最大程度地利用網絡資源，在降低投資成本和運營成本問題中具有實際意義。

5 結語

為解決時延敏感型服務資源優化欠缺的問題，并考慮在降低投資和運營成本方面具有實際的應用價值，提出了一種基于拍賣模型的啟發式多路徑拍賣算法實現時延敏感型服務對底層資源的高效利用。實驗結果表明，所提出的算法通過引入拍賣模型降低了算法的部署時間，同時在保障了服務低時延要求的基礎上提高了資源的利用率，從而使得該算法能夠更加適用于低時延的應用場景。考慮到時延敏感型服務對時延的敏感性以及低時延的特性，在服務請求期間結合機器學習算法實現服務時延的可預見性，保證時延的穩定性，提高部署算法的靈活性以適應網絡資源環境的實時變化是后續的研究方向之一。