基于最佳匹配拍賣的企業(yè)級網絡資源分配策略

叢鑫，訾玲玲，沈學利

（遼寧工程技術大學電子與信息工程學院，遼寧 葫蘆島 125105）

1 引言

大型企業(yè)需要數據中心來分析和處理每天產生的大量數據。現階段，構建數據中心可以采用租用云計算平臺和企業(yè)自建2 種方式，但租用云計算平臺有泄露數據隱私的風險，因此，企業(yè)往往更愿意建立自己的數據中心。通常大型企業(yè)會在不同地理位置建立子公司，但為每個子公司建立數據中心是巨大的資源浪費。另外，已有調查[1]表明，處于開啟狀態(tài)的計算機絕大部分時間都處于空閑狀態(tài)。鑒于此，利用企業(yè)現有的計算機、服務器和網絡構建數據中心是簡單易行且投資較低的方案。

相比于云平臺，企業(yè)級網絡具有以下特征：1)網絡中的計算機等設備供員工日常使用，員工從完全占用計算機的使用權和不耽誤日常工作的角度出發(fā)，不愿意貢獻自己的計算機作為網絡中任務處理的節(jié)點；2)網絡中的計算機等設備隨著員工日常上下班而開啟和關閉，可用資源數隨著時間發(fā)生變化；3)網絡中的計算機等設備的性能不同，其能提供資源的數目和連續(xù)工作時間長度也不同，即提供服務的質量是有差異的。針對上述特征，當網絡中有可用資源時，如何分配這些資源成為有意義的研究工作。已有資源分配方案，如資源數預測[2]、服務級別協(xié)議（SLA,service level agreement）[3]、工作流和虛擬機分配[4-5]等，都是建立在云平臺內節(jié)點資源充足的情況下，而沒有考慮節(jié)點所提供資源的差異性，這就需要研究新的適用方案。虛擬支付方案是解決節(jié)點激勵和資源分配的有效途徑，其中拍賣機制已經被證明是極其高效的[6]，可以關聯銷售者和購買者以獲取商業(yè)化的收益，最終達到納什均衡[7-8]。例如，文獻[9-11]改進了連續(xù)雙邊拍賣方法，建立了新的資源分配模型，從銷售者的角度實現一定的性能和經濟服務質量。

為了使連續(xù)雙邊拍賣適應企業(yè)級網絡環(huán)境，需要考慮以下幾個方面：1)滿足資源提供者（銷售者）和資源租用者（購買者）的可接受程度需求；2)構建銷售者虛擬支付市場，當銷售者貢獻資源時，給予報酬（虛擬收益），并設置消費機制；3)提升銷售者和購買者匹配程度，在拍賣開始時被標記為高計算能力的節(jié)點可能隨著任務的運行變成低計算能力節(jié)點，此時應避免將有高計算能力需求任務分配到該節(jié)點上。

因此，本文研究的是如何以虛擬市場的方式分配企業(yè)級網絡的計算資源和帶寬資源以滿足任務需求，達到較高的資源分配效率及市場收益率。在虛擬市場中，當銷售者提供的資源和購買者需求有差異、資源價格浮動性較大時，利用基于市場規(guī)律的拍賣機制解決資源分配問題是有效的。企業(yè)級網絡資源分配應達到以下3 個目標：目標1，不同部門銷售者之間的資源負載動態(tài)平衡；目標2，銷售者和購買者的接受程度高；目標3，整個拍賣市場獲取最佳收益。與云平臺的資源節(jié)點可以全天24 h運行服務不同，企業(yè)網的節(jié)點不能持續(xù)長時間的工作（工作時間僅為8～10 小時/天）。因此，資源銷售者感知更多的服務請求到來時，會在本輪拍賣過程中提高請求價格，以獲取更多的收益；當發(fā)現剩余工作時間不充足（為1～2 h）時，會降低請求價格，以獲取更多的服務請求。然而，高價格會導致其他銷售者更容易贏得拍賣，剩余工作時間少的資源銷售者即使降低價格也可能因為剩余服務請求不多而達不到預期收益目標。換言之，服務請求以輕負載原則分配給銷售者，滿足目標1。

銷售者給出的請求價格較低，則在拍賣過程中會獲得較高的優(yōu)先級，從而獲得較多的服務請求。購買者如果有較多的預算，也會獲得較高的優(yōu)先級，從而獲得所需的資源。那么，如何設計拍賣過程中的匹配方案才能滿足上述3 個目標？舉例分析如下：R1和R2都滿足服務請求C 所需的資源，但R1更適合C 的運行，則當R1和R2在拍賣過程中給出相同的請求價格時，R1和C 的最終交易價格要低于R2和C 的，這樣R1才能贏得本輪拍賣并獲取C，從而滿足目標2；從整個市場的角度來看，R1完成C 的運行時間要短于R2，而較短的運行時間能夠使一定時間內，市場能容納的服務數更多，整體收益更高，從而滿足目標3。

基于以上分析，本文提出最優(yōu)匹配資源分配（OMRA,optimized matching resource allocation）策略，相比于已有的連續(xù)雙邊拍賣方案，OMRA 策略額外關注了銷售者和購買者的可接受程度，來衡量銷售者和購買者的最終成交價格和預期價格的差異程度，可以激發(fā)銷售者提供更多的可用資源，購買者在當前拍賣進程中放置更多的服務請求。

本文主要工作如下。

1)設計了節(jié)點的資源歸一化方法，以基準資源節(jié)點數值為標準，分別計算高能力節(jié)點和高I/O 能力節(jié)點資源數，從而計算出不同節(jié)點的運行成本，為拍賣過程中的競拍價格提供依據。

2)設計了銷售者/購買者最佳匹配拍賣算法，以最大化整個拍賣市場的收益。設計了服務請求預留算法，使銷售者以當前價格獲取更多的服務器請求，進一步增加收益。

3)設計了請求價格更新算法，引導銷售者在拍賣過程中動態(tài)調整請求價格，以在下一輪拍賣中得到較高的優(yōu)先級。

4)搭建了由服務器和計算機組成的企業(yè)級網絡模擬環(huán)境，系統(tǒng)評估了服務請求接受率、收益率、支付率、資源分配率和市場共享率等參數。

2 企業(yè)級網絡資源拍賣模型和參數定義

拍賣市場有3 個實體，分別是銷售者、購買者和貨物。虛擬市場的交易行為主要分為3 個階段，商品定價階段、商品交易階段和商品支付階段。相應地，在企業(yè)級網絡中，計算和帶寬資源的擁有者是銷售者，任務的發(fā)布者是購買者，資源是貨物。本文重點關注虛擬市場的貨物拍賣機制，為了避免網絡的服務器成為網絡瓶頸，引入另外2 種實體：服務代理和資源代理。在拍賣過程中，資源沒有起拍的參考價格，以供需關系為原則確定成交價格，銷售者提交當前的請求價格給資源代理，購買者提交當前的競拍價格給服務代理，如果請求價格和競拍價格相匹配，則立即執(zhí)行交易。

2.1 資源拍賣模型

圖1 展示了ORMA 使用的拍賣模型，分為4個過程：服務請求分配過程、拍賣過程、資源分配過程和虛擬網絡映射過程。其中，本文對前3 個過程進行分析討論，而虛擬網絡映射過程是后續(xù)的研究工作。在服務請求分配過程中，服務代理收集購買者的服務請求，依據請求的數量和價格歸一化不同類型資源的價格，并依據此價格建立競拍價格序列。在資源分配過程中，資源代理收集銷售者提供的可用資源，依據提供的資源數量和請求價格歸一化不同類型資源的價格，并依據此價格建立請求價格序列。在拍賣過程中，運行最佳匹配算法匹配銷售者和購買者，匹配成功則計算出最終成交價格，并以此價格交易，同時銷售者執(zhí)行服務請求預取算法，以容納更多的服務請求。經過以上過程，資源被合理地分配給適合的服務請求，最終最大化整個市場的收益。

為了降低整個拍賣過程的計算量，將銷售者分組形成多個資源域，每個資源域設置一個資源代理。分組原則可以采用將連接在同一路由器下的計算機節(jié)點分成一組，這些節(jié)點擁有相似的計算能力和傳輸數據能力。因此，同一資源域的計算機節(jié)點的請求價格相同，分享由購買者支付的費用。此外，拍賣過程存在拍賣人角色，該角色可以用獨立的服務器充當，其作用是運行最佳匹配算法以確定哪些銷售者和購買者相匹配。這可能會導致圖1 的架構是中心化的，但該服務器僅與資源代理和服務代理進行消息通信，通信內容為請求價格和競拍價格、剩余資源數和需求資源數，這些消息內容和數量都較少，且最佳匹配算法的運行時間很短，因此該服務器不會成為瓶頸節(jié)點。同時，利用分布式計算來處理資源分配問題已有成熟的研究方案[12]，可作為服務器非中心化的參考。

2.2 參數定義

為了說明OMRA 策略的運行流程，定義如下參數。

圖1 OMRA 拍賣模型

定義1資源節(jié)點。企業(yè)級網絡中擁有計算和數據傳輸能力的可租用實體可與其他實體協(xié)作并提供服務請求所需軟件的運行環(huán)境。

定義2基準運行時間?；鶞史照埱笤诨鶞寿Y源節(jié)點從開始運行到結束所需要的時間，單位為s?；鶞寿Y源節(jié)點是指由企業(yè)級網絡管理者設定的資源節(jié)點或者虛擬資源節(jié)點，且沒有加速模塊，如未安裝高I/O 數據傳輸能力的網卡等?；鶞史照埱笫侵竷H申請基準資源節(jié)點即可滿足運行條件的任務。

例如，服務請求C 被分配到基準資源節(jié)點上運行，完成C 需要時間為nt，其中，t為基準運行時間，單位為s。C 運行在資源節(jié)點B 上時，需要時間為mt。在此基礎上，如果已知某任務運行在基準資源節(jié)點上需要時間為T，則此任務運行在B 上需要時間為。因此，可以計算出每次執(zhí)行期內服務請求所需的基準資源節(jié)點數量，同時也能判斷出資源節(jié)點的運行速率。

定義3平均服務請求率。一輪拍賣過程中，能夠容納的服務請求數與最大的可用資源數量的比值。平均服務請求率表示達到服務請求預期的QoS 所需的基準資源數量，也能衡量不同資源域的資源數量。服務請求預期的QoS 可以用費用預算來度量，費用預算是服務請求在拍賣過程中可以給出的最大競拍價格。

定義4資源歸一化值。以基準資源節(jié)點的資源數值為標準，用于量化非基準資源節(jié)點的資源數值。假設服務請求在基準資源節(jié)點上運行需要資源為Ri，在節(jié)點B 上運行需要資源為Rj，則基準資源節(jié)點與B 之間的資源歸一化計算為

由于基準資源節(jié)點不含任何加速模塊，通常δji≤1。

根據式(1)可知，對于購買者，從基準資源節(jié)點購買服務請求需要資源為z，從B 購買服務需要資源為zδji。假設基準資源節(jié)點和B 給出相同的請求價格，應將購買者分配給B，因其需要支付的費用少于分配給基準資源節(jié)點的費用。然而，對于銷售者，δji值越低，意味著運行成本越高，即相比于基準資源節(jié)點，銷售者需要提供更多的CPU 內核數，更多的路由器端口才能使δji更低。因此，需要設計成本計算方法以保證銷售者盈利。

2.3 高計算能力和高I/O 能力節(jié)點資源數

隨著CPU 利用率的增加，CPU 的資源占用數也隨之增加[13]?；诖死碚摚哂嬎隳芰?jié)點的資源數計算方法為

其中，Rres是資源節(jié)點當前提供的資源數，該值在每次拍賣過程中是變化的，Rres∈[Rmin,Rmax]，Rmin和Rmax分別是該節(jié)點能提供的最小和最大資源數；CPU(u)是當前CPU 利用率，該值用于量化高計算能力節(jié)點所擁有的資源數值。

數據傳輸規(guī)模主要反映在對路由器的資源占用上[13]。一般來說，路由器包含4 個部分：底盤、交換結構、線卡和端口。底盤和交換結構消耗的資源數在路由器開啟的情況下是固定的，線卡和端口的資源占用數PLC和Pport是隨著進出路由器的數據量而動態(tài)變化的。高I/O 通信能力節(jié)點消耗的資源數為

其中，Δm和Δn是高I/O 通信能力節(jié)點相比于基準資源節(jié)點多出的線卡和端口數量；PLC和Pport的數值可以從文獻[14]獲取，該值用于量化高I/O 通信能力節(jié)點所擁有的資源數值。

根據式(2)和式(3)可知，拍賣過程中，高能力節(jié)點有以下2 種策略給出請求價格：1)請求價格高于基準資源節(jié)點的請求價格，則在拍賣過程中獲得較低的優(yōu)先級，不能贏得拍賣；2)請求價格低于或等于基準資源節(jié)點的請求價格，則能夠贏得拍賣，但獲得的收益要大于運行的成本，如式(4)所示。

其中，trun是在高性能節(jié)點執(zhí)行一次服務請求所需的時間。

圖2 反映在不同CPU 利用率下，運行時間的變化趨勢。橫坐標表示資源節(jié)點當前提供的資源數與基準資源節(jié)點提供資源數的比值。當時，資源節(jié)點提供的資源數小于基準資源節(jié)點提供的資源數，此時服務請求在資源節(jié)點上的運行時間要大于在基準資源節(jié)點運行時間。當，CPU利用率從20%提升到100%時，服務請求運行時間會降低，這意味著可以容納更多的服務請求。在CPU利用率達到80%時，繼續(xù)提升CPU 利用率到100%不會顯著降低服務請求時間，此時，新的服務請求到來時，會被該資源節(jié)點拒絕。

圖2 不同值下的服務請求運行時間比值

3 OMRA 策略拍賣機制

為了降低拍賣過程中的計算量，在構建OMRA策略模型時，需要先對請求價格和競拍價格從高到低進行排序，選擇TOP-M請求價格和TOP-N競拍價格形成請求價格序列和競拍價格序列。

在拍賣過程中，基于上述2 個序列，定義Q1為N'個購買者的集合，Q1中的每個購買者給出的競拍價格都高于集合外的購買者的競拍價格。定義Q2為?M'個銷售者的集合，Q2中的每個銷售者給出的請求價格都低于集合外的銷售者的請求價格。定義Q3為M'個銷售者的集合，Q3中的每個銷售者的δji值都低于集合外的銷售者的δji值。構建企業(yè)級網絡拍賣市場參與者為Q1∪Q2∪Q3，并遵循如下規(guī)則。

1)設t代表拍賣過程的某個時刻，t∈[t0,t1]，t0和t1分別是本輪拍賣開始時刻和結束時刻。拍賣初始，資源代理提交初始請求價格序列，服務代理提交競拍價格序列。在t時刻，資源代理i更新請求價格ri(t)，服務代理j更新競拍價格bj(t)。當可用資源數和服務請求數發(fā)生變化時，立即更新請求價格序列和競拍價格序列。

2)在拍賣過程中，拍賣人服務器持續(xù)關注2 個序列，運行最佳匹配算法以保證整個拍賣市場獲取最大收益。

3)銷售者利用服務請求預留算法確定由資源代理發(fā)送來的服務請求能否滿足需求的資源。如果滿足，則通知資源代理與服務代理進行交易，否則，更新請求價格進入下一輪拍賣。

4)拍賣過程的銷售者和購買者均來自Q1∪Q2∪Q3。

5)執(zhí)行拍賣交易后，如果銷售者還有可用資源，則通知資源代理更新請求價格，形成新的價格請求序列。

3.1 最佳匹配拍賣算法

在企業(yè)級網絡中，服務請求可以在不同資源域上運行，資源域也可以容納不同的服務請求。因此，需要解決的關鍵問題是如何匹配服務請求和資源域（即銷售者和購買者）來最大化整個拍賣市場的收益。為了解決上述問題，提出了最佳匹配拍賣算法，建立數學模型如下。

1)依據請求價格序列和競拍價格序列建立圖G=(V,E)。其中，，X是請求價格序列，Y是競拍價格序列；

2)權重w(xi,yj)。xi和yj相匹配，設置xi當前的請求價格值為xi的權重w(xi)，yj當前競拍價格與δji乘積值為yj的權重，則w(xi,yj)=w(xi)-w(yj)。

上述的模型可利用已有的KM（Kuhn-Munkres）算法進行求解，但已知的KM 算法及其改進算法的時間復雜度均為O(n3)。因此，本文設計了一種改進的KM 算法，使算法復雜度降到O(n2)。

算法1KM 改進算法

1)輸入G。

2)標定xi、yj的頂標值l(xi)和l(yj)，使其滿足條件l(xi)+l(yj)≥w(xi,yj)，其中，x i∈X，yj∈Y。給定頂標值為

形成新的二分圖G' 。

3)計算初始匹配M。在所有的yj范圍內，盡可能地找到xi的可行匹配(xi,yj)。(xi,yj)應滿足以下條件：xi與yj有 max (w(xi,yj))，且xi未與其他yk建立匹配，yk∈Y-{yj}；wij＞wil(j≠l)，且xi與yl已經建立了匹配。如果找到(xi,yj)，則(xi,yj)∈M。

4)如果?xi∈M，KM 改進算法終止。如果?xi?M,則取節(jié)點u，滿足u∈G'且u?M。初始化S={u}，T=?。

5)如果T?N G'(S)，轉至步驟6)；如果T=N G'(S)，NG'(S)是S的每個元素的鄰居節(jié)點組成的集合，計算

6)選擇?yi∈N G'(S)-T。如果y i∈M且(y i,z)∈M，則S←S∪{z} 與T←T∪{yj}，轉至步驟 5)；獲取M的增廣路徑P(u,yj)，計算M←M⊕E(P)，轉至步驟4)。

算法1 的時間復雜度分析如下。在搜索初始匹配時，采用的貪婪算法的時間復雜度為O(n2)。假設可以找到m條匹配路徑，那么，剩余的n-m條匹配路徑需要用KM 算法尋找，則算法時間復雜度為O((n-m)n3)。如果m=n，則算法時間復雜度為O(n2)。如果m=0，算法最壞的時間復雜度為O(n2+n3)。因此，改進的KM 算法的時間復雜度在O(n2)和O(n3)之間，且貪婪思想在匹配過程中不會失效，故改進的KM 算法的時間復雜度要優(yōu)于KM 算法，可以達到 (2)O n。

3.2 服務請求預留算法

最佳匹配算法執(zhí)行完畢時，部分服務請求已和資源域RA 相匹配，但是否能被RA 接受需要進一步計算。另外，相比于當前時間，越臨近拍賣結束時間，RA 給出的請求價格越低，導致成交價格降低，收益銳減。故在當前的請求價格下，如何獲取更多的服務請求是本節(jié)研究的問題。該問題建模如下。

1)設置服務請求j的資源需求矩陣requestj，requestj={r1[j],r2[j],…,rk[j],dl[j]}。其中，k是j需求的資源類型，rk[j]是需求的數量，dl[j]是服務請求的預期截止時間。

2)建立資源節(jié)點i的可用資源數矩陣availablei和最大資源數矩陣maximumi，availablei={a1[i],a2[i],…,ak[i],pt[i]}，maximumi={m1[i],m2[i],…,mk[i],pt[i]}。其中，ak[i]是本輪拍賣過程i提供的k的可用數量；mk[i]是i提供的k的最大數量；pt[i]是i的計劃關閉時間，即企業(yè)級網絡中i將在pt[i]時刻或之后關閉。

設計服務請求預留算法求解上述模型，如算法2 所示。

算法2服務請求預留算法

3.3 請求價格更新算法

在OMRA 策略中，只有當服務請求給出的競拍價格高于其他服務請求時，才能獲取預期的需求資源。相似地，資源域給出的請求價格低于其他資源域時，才能獲取較多的服務請求。而且在拍賣開始時，資源域給出的請求價格高，臨近拍賣結束時，給出的價格低。依據以上價格變化原則，設計請求價格更新算法，詳細表述如下。

令st(t)代表拍賣開始時間，τ代表本輪拍賣持續(xù)的時間，則當前時間t滿足

剩余時間r(t)為

且滿足r(t)∈[ 0,τ]。

其中，κ(x)是相關于r(t)的函數。當r(t)減少時，κ(x)值降低。當r(t)→τ時，，此時κ(τ)=1。當r(t)→ 0時，，此時κ(0)=0。則定義κ(x)[15]為

其中，β∈R+代表請求價格函數的曲率，κ'是實常數，取值范圍為κ' ∈[ 0,1]。特別地，當β→ 0和β→+∞時，κ(x)分別滿足式(9)和式(10)。

聯合式(7)，x是剩余時間，且x=r(t)，因此RA的請求價格更新函數如式(11)所示。

其中，β是請求價格參數。

為了評估請求價格更新函數，設置τ=10 min，分別設置為100 倍和200 倍的基準資源節(jié)點請求價格。圖3 和圖4 中，橫坐標分別代表剩余時間和拍賣時間，縱坐標反映請求價格變化趨勢。從圖3 中可以看出，當β值較小時（β＜0.7），請求價格變化曲線是凹曲線且數值快速降低，此時銷售者有較高的優(yōu)先級，但收益不會太高。從圖4 可以看出，'κ決定了請求價格降低程度。當 'κ值較大時（κ'=0.90），請求價格隨著拍賣進程變化不大。從整體來看，建議β的取值最好大于0.4，'κ取值小于0.1。

圖3 不同β 值下隨r(t)增加的A 的a(t)變化趨勢

圖4 不同 'κ 和β 值下隨拍賣時間增加的請求價格變化趨勢

3.4 支付價格和收益

在OMRA 策略中，由資源代理和服務代理分別管理銷售者和購買者的需求信息，由高性能資源節(jié)點成本核算方法計算銷售者請求價格變化范圍，由最佳匹配算法保證拍賣市場的最大收益，由服務請求預留算法保證在滿足購買者請求條件下盡可能多地以當前的成交價格容納更多的服務請求。上述過程運行完畢之后，交易立即執(zhí)行，最終成交價格為

由第2 節(jié)和第3 節(jié)可知，OMRA 策略對企業(yè)級網絡的特征具有適應性，具體體現為：1)針對企業(yè)網絡節(jié)點自私特性，設立了拍賣激勵機制方案，以加速網絡帶寬速率和軟件免費使用權為激勵條件，此非嚴格激勵機制能促使節(jié)點貢獻資源，保證網絡資源的可用性；2)針對企業(yè)網絡節(jié)點運行任務具有時限性的特征，在設計請求價格策略時，加入了隨時間變化的價格變化函數；3)針對企業(yè)級網絡節(jié)點提供資源差異性特征，在運行最佳匹配算法時，確立了提供較好可用資源和任務運行時間的節(jié)點以較高優(yōu)先級被選中的策略，同時關注了該類節(jié)點隨著任務運行的資源數變化情況；4)最佳匹配算法的依據是保證銷售者和購買者能夠以雙方均滿意的價格達成交易，而不是偏袒某一方，因此，可以實現銷售者獲取比預期多的收益，購買者支付更少的費用的目標；5)為了增加本輪拍賣過程中的銷售者收益，設計了服務預留算法，能夠在滿足任務運行時間需求的條件下，預先容納擬運行的任務。需要注意的是，4)和5)不是沖突的，4)是保證實現預期的交易價格，5)是實現容納任務數的增加。

4 實驗及結果分析

4.1 實驗參數

為了評估 OMRA 策略的性能指標，使用MyEclipse 平臺利用PeerSim 開發(fā)引擎形成了可加載的程序包，搭建了位于不同地理位置的由計算機和服務器組成的網絡來模擬企業(yè)級網絡環(huán)境。一般來說，企業(yè)級網絡的搭建原則是服務器一般連接在核心交換機或者一級交換機上，其他計算機等節(jié)點連接在多級交換機上，因此，服務器具有高計算性能和高I/O 通信性能，全天24 h 運行。針對企業(yè)級網絡一般情況，設計了節(jié)點A1～A5通過有線連接在同一個交換機下，相互之間的數據傳輸速率較快，有較低的計算能力。節(jié)點A6～A8通過無線連接到企業(yè)網絡中，由于地理位置的不同處于不同交換機下，有中等計算能力，相互之間的數據傳輸速率較慢。服務器A9～A10通過有線連接到核心交換機上，有高計算能力和高I/O 數據傳輸能力。為了反映不同需求任務的運行情況，設置服務器A9更傾向于高計算能力，A10更傾向于高I/O 通信能力。物理節(jié)點參數配置詳?見表1。

設置基準資源節(jié)點的計算和帶寬能力分別為1.0 GHz 和10 Mbit/s。節(jié)點A1～A5提供計算資源最小值和最大值設置為Rmin=0×1.0 GHz，Rmax=2×1.0 GHz。節(jié)點A6～A8計算資源最小值和最大值設置為Rmin=1×1.0GHz，Rmax=2.5×1.0GHz。A1～A8的帶寬能力計算參數為Δm=1，Δn∈[1,10]。A9的帶寬能力計算參數為 Δm∈[1,4]， Δn∈[1,100]。A10具有多個CPU 核心，可提供計算資源最小值和最大值設置為Rmin=1×1.0 GHz，Rmax=12×1.0 GHz。本輪拍賣結束后的下一輪的計算請求價格的參數設置為β=0.4，κ'=0.1。對于購買者來講，無論可用資源充足與否，服務請求都應該被滿足。令設置可接受率來衡量服務請求的接受程度，可接受率為被接受的服務請求數與所有的服務請求數的比值。

4.2 結果分析

圖5 展示了服務請求需求對服務請求可接受率的影響。請求的資源數量越大，獲取該資源越困難，原因在于單個的資源節(jié)點不能提供充足的資源。競拍價格越低，在拍賣過程中和資源域匹配的概率越小，原因在于相比于接受其他高競拍價格的服務請求，銷售者得到的收益更低。預期運行時間影響占用資源的釋放速度，進而影響可用資源數量。服務請求預期運行時間越長，則釋放資源越慢，市場上可用資源數越低。基于以上原因，在相同的服務請求到來的條件下，當可用資源數充足（r=4）時，服務請求的可接受率較高，當可用資源數匱乏（r=1）時，可接受率會發(fā)生突變甚至停止。

表1 物理節(jié)點實驗參數設置

圖5 隨拍賣時間增加的服務請求可接受率變化

圖6 顯示了整個拍賣市場銷售者收益率（標識收益增加）和購買者支付率（標識費用節(jié)?。┑脑u估結果。定義收益率brate 和支付率prate 為

圖6 隨資源數增加的收益/支付率變化

收益率brate 和支付率prate 評估了銷售者和購買者的滿意程度。

從圖5 和圖6 可以看出，1)可接受率反映了匹配性能變化趨勢，保證了資源分配的效率；2)r值的增加不會影響匹配性能；3)由于運行服務預留算法能夠使銷售者以當前的價格獲取更多的服務請求，使其收益率保持在一個很窄的范圍；4)購買者支付率與收益率有相似的情形。

圖7 展示了在資源分配率參數上與CRAA/ FA（cloud resource allocating algorithm via fitness-enabled auction）策略[16]對比情況。假設資源域接受服務請求i，相對基準資源節(jié)點的歸一化參數為δi，i請求的資源數為Di。定義資源分配率ralloc 為

圖7 OMRA 與CRAA/FA 機制在資源分配率的比較

資源分配率反映了當資源數增加或者降低時的資源分配情況，同時，在資源數一定的情況下，影響當前購買者的競拍價格參數設置，即評估資源域和服務請求的匹配程度。從圖7 可以看出，當δi確定之后，調動更多的資源到不同的資源域上對資源分配率不會造成太多的影響。

圖8 展示了OMRA 策略與CRAA/FA 策略在收益率的比較情況。從圖8 中可以看出，隨著r的增大并進入到非合理的區(qū)間，收益率會驟降，直至降至0。這種情況是合理的且能引導資源域誠信地給出請求價格，同時能夠避免銷售者之間的聯盟。服務請求預留算法促使資源域能夠提前接收到服務請求，因此OMRA 策略的收斂速度要快于CRAA/FA 策略。

從圖7 和圖8 中可以看出：1)當資源數量或者請求價格在合理區(qū)間時，資源分配率曲線是穩(wěn)定的；2)當請求價格增長時，整個拍賣市場范圍內的收益率不是一直增加的，尤其是當r處于非合理的范圍時，收益率會快速下降。

圖8 OMRA 與CRAA/FA 機制在收益率的比較

從圖9 可以看出：1)沒有特殊需求的服務（非實時應答、無高性能要求、預期截止時間很長）希望租用僅僅滿足其需求的資源，以節(jié)省費用支出；2)當拍賣開始時，A1給出的初始請求價格很低，則最佳匹配算法和成本計算方法能保證很多服務都分配到A1上，但當A1的市場共享率到達了峰值，再增加額外的資源數或者降低r值都不會增加其收益。

圖9 OMRA 與CRAA/FA 機制在市場共享率的比較

4.3 應用及討論

物理網絡資源優(yōu)化分配是云平臺中的典型研究問題，已有的研究是基于資源提供節(jié)點地理位置相對集中，且資源提供節(jié)點能力相對一致的場景下。與之相對，OMRA 策略可應用于網絡中提供資源的計算機節(jié)點位于不同的地理位置，企業(yè)數據中心服務器相對集中，提供的資源數目和持續(xù)在網時長多樣化的企業(yè)級網絡場景下。OMRA策略也可應用于需要抑制節(jié)點自私性的網絡資源分配場景，提升物理資源提供的數量和質量。基于資源分配框架的思想，OMRA 策略可用“包”的形式與其他研究者的算法同時集成，部署到企業(yè)級網絡的服務器和計算機節(jié)點上。

5 結束語

本文提出了一種新的基于最優(yōu)拍賣理論的資源分配機制，能夠適應企業(yè)級網絡資源節(jié)點的特征，將服務請求分配到不同的資源域處，達到銷售者獲取比預期多的收益，購買者支付更少的費用的目標。該機制包含成本計算方法，最佳匹配拍賣算法、服務預留算法、請求價格更新算法最終保證了整個拍賣市場的效率。實驗結果表明，在企業(yè)級網絡規(guī)模不大的情況下，OMRA 能有效地提高網絡資源的分配效率，同時提升拍賣市場的收益率。

現有的實驗模擬是在小范圍內運行的，限于已有的資源限制和技術手段，未開展在大規(guī)模企業(yè)級網絡環(huán)境下的適應性研究。由于資源域分散在不同的地理位置，如何穿過路由器發(fā)現更多資源提供節(jié)點是進一步需要研究的問題。另外，資源域之間存在競爭關系，但壟斷也可能存在于拍賣過程中，原因在于相似的資源節(jié)點可能位于同一個辦公室，會形成聯盟來壟斷某些類型的資源域，例如高性能I/O 資源域，研究的資源分配算法能否用于有此種情況下的資源市場是需要進一步研究的問題。