叢鑫，訾玲玲，沈?qū)W利

（遼寧工程技術(shù)大學(xué)電子與信息工程學(xué)院，遼寧 葫蘆島 125105）

1 引言

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

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

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

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

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

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

本文主要工作如下。

1)設(shè)計(jì)了節(jié)點(diǎn)的資源歸一化方法，以基準(zhǔn)資源節(jié)點(diǎn)數(shù)值為標(biāo)準(zhǔn)，分別計(jì)算高能力節(jié)點(diǎn)和高I/O 能力節(jié)點(diǎn)資源數(shù)，從而計(jì)算出不同節(jié)點(diǎn)的運(yùn)行成本，為拍賣過程中的競拍價(jià)格提供依據(jù)。

2)設(shè)計(jì)了銷售者/購買者最佳匹配拍賣算法，以最大化整個(gè)拍賣市場的收益。設(shè)計(jì)了服務(wù)請求預(yù)留算法，使銷售者以當(dāng)前價(jià)格獲取更多的服務(wù)器請求，進(jìn)一步增加收益。

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

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

2 企業(yè)級網(wǎng)絡(luò)資源拍賣模型和參數(shù)定義

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

2.1 資源拍賣模型

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

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

2.2 參數(shù)定義

為了說明OMRA 策略的運(yùn)行流程，定義如下參數(shù)。

圖1 OMRA 拍賣模型

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

定義2基準(zhǔn)運(yùn)行時(shí)間。基準(zhǔn)服務(wù)請求在基準(zhǔn)資源節(jié)點(diǎn)從開始運(yùn)行到結(jié)束所需要的時(shí)間，單位為s?；鶞?zhǔn)資源節(jié)點(diǎn)是指由企業(yè)級網(wǎng)絡(luò)管理者設(shè)定的資源節(jié)點(diǎn)或者虛擬資源節(jié)點(diǎn)，且沒有加速模塊，如未安裝高I/O 數(shù)據(jù)傳輸能力的網(wǎng)卡等?；鶞?zhǔn)服務(wù)請求是指僅申請基準(zhǔn)資源節(jié)點(diǎn)即可滿足運(yùn)行條件的任務(wù)。

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

定義3平均服務(wù)請求率。一輪拍賣過程中，能夠容納的服務(wù)請求數(shù)與最大的可用資源數(shù)量的比值。平均服務(wù)請求率表示達(dá)到服務(wù)請求預(yù)期的QoS 所需的基準(zhǔn)資源數(shù)量，也能衡量不同資源域的資源數(shù)量。服務(wù)請求預(yù)期的QoS 可以用費(fèi)用預(yù)算來度量，費(fèi)用預(yù)算是服務(wù)請求在拍賣過程中可以給出的最大競拍價(jià)格。

定義4資源歸一化值。以基準(zhǔn)資源節(jié)點(diǎn)的資源數(shù)值為標(biāo)準(zhǔn)，用于量化非基準(zhǔn)資源節(jié)點(diǎn)的資源數(shù)值。假設(shè)服務(wù)請求在基準(zhǔn)資源節(jié)點(diǎn)上運(yùn)行需要資源為Ri，在節(jié)點(diǎn)B 上運(yùn)行需要資源為Rj，則基準(zhǔn)資源節(jié)點(diǎn)與B 之間的資源歸一化計(jì)算為

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

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

2.3 高計(jì)算能力和高I/O 能力節(jié)點(diǎn)資源數(shù)

隨著CPU 利用率的增加，CPU 的資源占用數(shù)也隨之增加[13]。基于此理論，高計(jì)算能力節(jié)點(diǎn)的資源數(shù)計(jì)算方法為

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

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

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

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

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

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

圖2 不同值下的服務(wù)請求運(yùn)行時(shí)間比值

3 OMRA 策略拍賣機(jī)制

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

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

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

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

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

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

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

3.1 最佳匹配拍賣算法

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

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

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

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

算法1KM 改進(jìn)算法

1)輸入G。

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

形成新的二分圖G' 。

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

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

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

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

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

3.2 服務(wù)請求預(yù)留算法

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

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

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

設(shè)計(jì)服務(wù)請求預(yù)留算法求解上述模型，如算法2 所示。

算法2服務(wù)請求預(yù)留算法

3.3 請求價(jià)格更新算法

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

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

剩余時(shí)間r(t)為

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

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

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

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

其中，β是請求價(jià)格參數(shù)。

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

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

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

3.4 支付價(jià)格和收益

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

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

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

4.1 實(shí)驗(yàn)參數(shù)

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

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

4.2 結(jié)果分析

圖5 展示了服務(wù)請求需求對服務(wù)請求可接受率的影響。請求的資源數(shù)量越大，獲取該資源越困難，原因在于單個(gè)的資源節(jié)點(diǎn)不能提供充足的資源。競拍價(jià)格越低，在拍賣過程中和資源域匹配的概率越小，原因在于相比于接受其他高競拍價(jià)格的服務(wù)請求，銷售者得到的收益更低。預(yù)期運(yùn)行時(shí)間影響占用資源的釋放速度，進(jìn)而影響可用資源數(shù)量。服務(wù)請求預(yù)期運(yùn)行時(shí)間越長，則釋放資源越慢，市場上可用資源數(shù)越低?；谝陨显颍谙嗤姆?wù)請求到來的條件下，當(dāng)可用資源數(shù)充足（r=4）時(shí)，服務(wù)請求的可接受率較高，當(dāng)可用資源數(shù)匱乏（r=1）時(shí)，可接受率會(huì)發(fā)生突變甚至停止。

表1 物理節(jié)點(diǎn)實(shí)驗(yàn)參數(shù)設(shè)置

圖5 隨拍賣時(shí)間增加的服務(wù)請求可接受率變化

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

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

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

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

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

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

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

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

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

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

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

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

4.3 應(yīng)用及討論

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

5 結(jié)束語

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

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