摘  要： 在虛擬網絡環境中，提出了基于效用的鏈路資源分配模型，使鏈路資源在存在擁塞的情況下達到最優分配。模型設計了單寡頭壟斷情況下虛擬業務提供用戶與壟斷者的效用函數，以及其達到均衡的條件，同時增加寡頭數來討論企業進入條件以及資源最優分配下的企業數量。由仿真分析可以得出，基于效用的資源分配模型能夠有效地促進用戶與企業之間、企業與企業之間的博弈，在雙方利益最大化基礎上實現資源最優分配。

　　關鍵詞： 虛擬化；資源分配；效用

0 引言

　　互聯網的迅猛發展引領了信息社會的發展，推動經濟不斷進步，互聯網規模不斷擴張的同時也面臨著瓶頸，主要表現在網絡中大量高帶寬應用對帶寬的要求，使得有限的網絡資源無法滿足需求；實時多媒體對網絡帶寬和延時要求讓盡力而為的路由協議無法保證服務質量[1]。現有方案對網絡模型的完善是基于具體問題上的局部性調整，這使得現有互聯網成為了一個層、技術的混合堆砌模型，從而導致互聯網僵化[2]。為了提高互聯網網絡資源利用效率，保證業務競爭和業務的多樣性，網絡虛擬化[3-4]勢在必行。

　　目前，網絡虛擬化的研究主要關注于虛擬化網絡平臺的映射及實現問題[5]，而用戶與業務提供者之間的效用以及內在交互問題沒有得到系統的理解和分析。參考文獻[6]利用博弈理論分析了網絡帶寬資源的分配問題，但其沒有涉及定價策略。參考文獻[7]針對網絡資源定價分配問題提出了一個初步的理論性框架，通過博弈理論來分析擁塞網絡中不同壟斷者之間的交互過程以及不同價格下的分配情況。本文主要基于用戶與業務提供者之間的具體交互過程，結合經濟學相關理論[8-9]，在雙方效用最大化的基礎上提出一個價格制定機制，從而分析壟斷情況下的均衡價格制定策略以及寡頭競爭情況下的市場進入與寡頭價格制定策略。

　　本文首先提出虛擬網絡資源分配的分層模型，然后提出了基于效用的虛擬網絡資源分配及定價策略，最后進行仿真分析。

1 虛擬網絡模型結構

　　本節主要介紹虛擬環境下的基本模型結構。在網絡虛擬化環境中，網絡資源主要包括節點、鏈路、接口等[10]。為了方便分析，本文主要以鏈路帶寬作為網絡資源來分析不同鏈路的流量情況。

　　在虛擬網絡環境中，本文將傳統的網絡服務提供商分為3個部分，如圖1所示。最底層是端到端的物理資源，由節點、鏈路等組成，主要負責部署和管理底層網絡，即底層物理資源。中間層是虛擬網絡運營者（Virtual Network Operator，VNO）。VNO可以看成一個虛擬資源池，該資源池是虛擬節點以及鏈路的集合，其中鏈路帶寬與虛擬核心節點的內存空間均為有限值。頂層是與業務相關的虛擬網絡（VN），為用戶提供各種業務。

　　2 基于效用的虛擬網絡資源分配策略

　　2.1 單一VNO壟斷模型

　　單一VNO資源分配模型主要由存在擁塞狀況的網絡、希望利益最大化的VNO和VN業務提供用戶組成。

　　假設VNO擁有的鏈路條數為I={1，2，…，I}，用戶數為J={1，2，…，J}。用Xji表示用戶j在鏈路i上的數據流量，ri表示鏈路i上總的流量數，Xj表示用戶j使用的總流量數，則有：

　　由于擁塞影響，鏈路流量的增加會引起延時增加。引入延時函數Li（ri）來表示數據在鏈路i上的傳輸延時，Pi={P1，P2，…，PI}表示鏈路i上每帶寬的鏈路價格大小。

　　2.2 效用函數

　　對VN用戶而言，租用鏈路的總效用是用戶在每條鏈路上得到的純效用減去因為延時和租用費產生的消耗。用uj（Xj）表示用戶j由于租用鏈路數Xj得到的自身效用，則用戶j的總效用為：

　　當所有用戶追求總效用最大化時，存在X={X1，X2，…，XJ}為用戶所選擇的流量數，該流量數達到均衡。式（3）表明，每一個用戶的總效用是由所有用戶的流量分布決定的，用戶既能決定鏈路的延時函數，又能決定鏈路的價格，因為用戶不同的流量分布會改變鏈路負載和延時，進一步改變VNO對鏈路價格的制定。

　　對VNO而言，由于其希望得到利益最大化，因此VNO根據各條鏈路的流量情況制定價格，這里忽略了數據傳輸成本。VNO制定的價格值即為式（4）的最優化：

　　其中，ri（P）是鏈路i在價格為p的情況下達到均衡時的總流量數。

　　由于ri（P）是P上的連續函數，因此式（4）必然存在最優解P*。當價格為P*時，存在X*為用戶選擇的流量數，用（P*，X*）表示。

　　2.3 多VNO寡頭競爭模型

　　當鏈路資源不再由一個VNO獨有，而是由多個VNO共有時，VNO之間就產生競爭。假設每個潛在企業都有可能進入市場。現市場中已有一個企業IVNO（Incumbent VNO），下面討論第一個企業EVNO（Entry VNO）進入的情況。

　　由于EVNO不擁有任何物理鏈路資源，因此當EVNO進入市場時，需要向IVNO租用物理鏈路資源。設λ∈[0，1]為允許EVNO與自己共用資源的程度。若λ=0，IVNO不允許EVNO使用自己的物理資源，則EVNO需要構建自己的底層資源。若λ=1，IVNO允許EVNO完全自由地使用自己的物理資源，則EVNO不需要花費另外的資金進行底層資源的構建。這里用d（λ）表示自己構建底層資源的費用，則d（λ）是一個λ的遞減函數。

　　對于EVNO的市場進入，可以將其看成是一個三階段博弈過程，下面從第三階段開始討論，然后進行逆向分析。

　　階段3：競爭

　　如果EVNO進入市場，則根據IVNO制定的允許接入度λ∈[0，1]和啟動成本，EVNO的進入成本T可以表示為T=rq2+K，其中，r為每單位鏈路的租賃費用，K為固定的啟動成本。若在階段1中IVNO已經確定λ和K的大小，則各企業的利潤IIi具體如下：

　　II1（λ，r，K）=II1+K（5）

　　II2（λ，r，K）=II2-K-d（λ）（6）

　　II1=（P1-c）q1+rq2（7）

　　II2=（P2-c-r）q2（8）

　　其中，Pi為不同VNO的鏈路價格，qi為不同VNO的鏈路產量，c為每單位鏈路的成本。

　　由于企業與企業以及企業與用戶之間相互博弈，因此企業之間的競爭均衡價格可以用式（9）求得：

　　max{II1（λ，r，K），II2（λ，r，K）}（9）

　　階段2：EVNO進入決策

　　EVNO的進入策略為：只有在滿足II2（λ，r，K）≥II2的條件下，才會選擇進入。IIi表示當VNO之間不存在租賃關系時，各VNO所獲得的利潤，因此有II1=II（s）和II2= II（s）-d（0），其中s表示各VNO的平均產量。由式（6）可求出EVNO的進入條件II2（λ，r，K）≥II2可轉化為：K≤?準（r），其中：

　　?準（r）=II2-d（λ）-II（s）+d（0）（10）

　　階段1：IVNO準入策略

　　現在考慮IVNO確定λ、K和r大小的策略。IVNO的威懾存在3種情形：EVNO不進入；EVNO的進入不可避免；威懾能夠阻礙但不能阻止EVNO的進入。

　　（1）若EVNO選擇不進入，則表示啟動成本K太高，進入市場競爭不值得。在這種情況下，EVNO的進入受到威懾而阻止，IVNO在市場中形成壟斷。

　　（2）若EVNO一定要進入，則表示進入市場競爭所獲得的利潤遠大于啟動成本，IVNO的威懾不起作用。

　　（3）若EVNO受到一定的威懾但沒有被完全阻止，則分析在給定接入度λ的情況下，IVNO需要滿足條件：

　　maxII1（λ，r，K）=maxr，K{II1+K}

　　=maxr，K{（P1-c）q1+rq2+K}（11）

　　s.t.K≤（r），K≥0

　　由式（8）可知，II2是單價r的遞減函數；而由式（10）可知，對于給定的λ，存在對應r（λ），使得（r）=0。當r>r（λ）時，（r）<0，反之亦然。因此，為了滿足式（11）中的兩個約束條件，必須有r<r（λ）。

　　2.4 社會福利函數

　　當EVNO可以自由進入時，討論達到均衡時EVNO的數量。為了簡單處理，假設EVNO一旦進入就不改變其決定，且規模產量相同。這樣，當市場中的VNO數量達到均衡時，存在J個VNO的條件當且僅當：

　　IIJ≥K（12）

　　IIJ+1<K（13）

　　根據市場中企業進入的數量，可以得到社會福利大小，社會福利就是社會各VNO總利潤與消費者剩余之和。用qJ表示J個VNO存在于市場的情況下，均衡時每個VNO的產量用P（.）表示。因此每個VNO的利潤可以表示為：IIJ=P（JqJ）qJ-c（qJ），其中c（qJ）表示每個企業的成本函數，并有c（0）=0。

　　用馬歇爾總剩余來衡量福利大小，則當市場上有J個企業時，社會福利可以表示為：

　　W（J）=P（s）ds-Jc（qJ）-JK（14）

　　當W（J 0）=0，得到整數解J 0，該J 0就是社會最優分配下的VNO數量。

3 仿真分析

　　根據前文提出的基于效用的資源分配策略，采用仿真實驗來驗證其效果。為了便于分析，實驗主要假設市場中存在兩個VN業務提供用戶，VNO擁有4條虛擬鏈路資源。設效用函數為u（X）=Xa，0<a≤1；延時函數為 L（r）=rb，b≥0。仿真結果如圖2和圖3所示。

　　由圖2可知，隨著時間的推進，VNO最后達到均衡狀態。初始價格低的鏈路雖然最初利用率高，但會導致長延時，用戶效用低，用戶轉而選擇其他鏈路。各條鏈路的選擇情況最終處于穩定狀態。而由圖3用戶的歸一化效用變化可知，用戶在不斷選擇鏈路的過程中效用不斷增大，當鏈路選擇達到穩定時，各用戶和VNO也得到最大的效用。

　　對于多VNO進入，本文主要分析古諾競爭均衡下市場中VNO的數量。為了便于分析，將三階段博弈中的第二階段簡化成古諾模型，即每個VNO都存在固定的單位鏈路成本c，c（q）=c*q，且價格函數為P（q）=a-b*q，a>c≥0，b>0。由式（14）可以得到隨著數量增加時的社會福利大小。仿真結果如圖4所示。

　　由圖4可知，在不同VNO數量進入市場的情況下，社會福利的大小也不同，由此可知在給定單位鏈路成本c和價格函數P（q）的情況下，存在J 0使社會福利達到最大，并可以認為當市場中VNO數量為J 0時，社會資源在社會層面上到達最優分配。

4 結論

　　本文是將虛擬網絡資源分配與經濟效用相結合的一次探索。本文主要分析了擁塞網絡中基于效用的虛擬網絡資源分配模型。該模型所運用的資源分配思想是多個用戶根據自身要求選擇鏈路和路由方法，使其效用最大；而虛擬網絡運營者則根據用戶的選擇實時調整定價，同時考慮多個VNO之間的競爭，使其收益最大。在模型分析過程中，分別對單個VNO的壟斷情形和多個VNO的寡頭競爭情形進行剖析，證明該定價策略能夠在利益最大化的基礎上實現資源最優分配。

參考文獻

　　[1] KNIGHTSON K. NGN architecture： generic principles[J]. IEEE Communications Magazine，2005，43（10）：49-56

　　[2] AOYAMA T. A new generation network： beyond the Internet and NGN[J]. IEEE Communications Magazine， 2011，47（5）：82-87

　　[3] ANDERSON T， PETERSON L， SHENKER S， et al. Overcoming the Internet impasse through virtualization[J]. Computer， 2005，38（4）：34-41

　　[4] 羅娟，徐岳陽，李仁發.網絡虛擬化中動態資源分配算法研究[J].通信學報，2011，7（32）：64-69.

　　[5] 楊宇，陳山枝，李昕，等.虛擬環境中基于Stackelberg博弈的資源分配[J].華中科技大學學報，2012，40（S1）：311-315.

　　[6] Zhou Ye， Li Yong， Sun Guang， et al. Game theory based bandwidth allocation scheme for network virtualization[C]. 2010 IEEE Global Telecommunications Conference， GLOBECOM 2010， 2010：1-5

　　[7] 張小慶，李春林，錢瓊芳，等.基于合作博弈的虛擬化資源效用分配策略[J].計算機科學，2012，6（39）：51-53.

　　[8] 鄧德傳，蔣從鋒，徐向華，等.虛擬機資源分配的非合作博弈標價模型[J].計算機科學，2012，39（6）：380-383.

　　[9] 黃智興.基于經濟機制的資源管理與網絡經濟研究進展[J].計算機科學，2006，33（9）：110-114

　　[10] JURNER J S， TAYLOR D E. Diversifying the Internet[C]. IEEE Global Telecommunications Conference， GLOBECOM 2005，2005，2：1-6