基于拍賣博弈的可重構服務承載網(wǎng)動態(tài)構建算法

梁寧寧，蘭巨龍，程國振，楊 琴

（1.國家數(shù)字交換系統(tǒng)工程技術研究中心 鄭州450002；2.78006部隊 成都610066）

1 引言

隨著網(wǎng)絡業(yè)務形態(tài)的不斷豐富、應用規(guī)模的不斷擴大，互聯(lián)網(wǎng)為人類工作生活提供了便利。然而，由于當前IP承載模式的簡單僵化、功能單一，基礎網(wǎng)絡所能提供的服務與業(yè)務需求之間的差距日趨顯著[1]。

基于此，可重構信息通信基礎網(wǎng)絡體系將底層網(wǎng)絡與服務提供在邏輯上相分離，底層網(wǎng)絡為承載網(wǎng)提供網(wǎng)絡資源，可重構信息通信基礎網(wǎng)絡為用戶提供定制服務，而網(wǎng)絡服務的提供主要通過為用戶構建服務承載網(wǎng)的方式實現(xiàn)[2]?？芍貥嫹粘休d網(wǎng)（reconfigurable service carrying network，RSCN）優(yōu)先考慮業(yè)務需求與網(wǎng)絡拓撲、資源狀態(tài)等條件，構建出多個在底層物理資源上存在交集，能夠提供不同服務能力的承載子網(wǎng)，如圖1所示。

圖1 可重構服務承載網(wǎng)示意

服務承載網(wǎng)的構建是指依據(jù)某種約束條件，將業(yè)務需求映射到底層網(wǎng)絡的相應物理路徑，并在路徑上分配帶寬的過程。其本質(zhì)是底層資源分配問題。現(xiàn)有服務承載網(wǎng)構建存在以下兩個問題：首先，現(xiàn)有構建方法一般假設不同業(yè)務并發(fā)地申請有限的底層資源，業(yè)務之間相互隔離，忽略了業(yè)務間的競爭；其次，現(xiàn)有服務承載網(wǎng)構建算法一般是在底層網(wǎng)絡拓撲變化（底層節(jié)點或鏈路失效）或者新到達請求被拒絕時執(zhí)行重映射，沒有涉及不同業(yè)務場景下的動態(tài)構建措施。

在不同業(yè)務對有限的底層網(wǎng)絡進行共享時，如何根據(jù)業(yè)務需求建立服務承載網(wǎng)，并實時感知業(yè)務變化，動態(tài)調(diào)整服務承載網(wǎng)的構建，以期實現(xiàn)整體系統(tǒng)的利益最大化，這是本文要討論的問題。

為解決上述問題，本文提出了一種基于拍賣博弈的可重構服務承載網(wǎng)動態(tài)構建 （dynamic auction game-based reconfigurable service carrying network construction，DAGR）算法，以拍賣機制為基礎，設計簡單的定價方式，降低系統(tǒng)的附加處理和計算負擔。引入合作博弈理論并進行周期映射，在最大化承載網(wǎng)總體構建收益的同時，減少系統(tǒng)開銷。具體過程如圖2所示。首先各業(yè)務提出自身的構建需求，由基于拍賣的定價機制計算各業(yè)務需支付的費用，并返回業(yè)務，然后對于確定加入網(wǎng)絡的業(yè)務，引入以最大化系統(tǒng)效用為目標的合作博弈理論構建服務承載網(wǎng)，對底層資源進行分配。

圖2 基于拍賣博弈的可重構服務承載網(wǎng)架構

2 相關研究

當前有關服務承載網(wǎng)構建的研究主要集中在資源分配和網(wǎng)絡映射等方面[3～7]。參考文獻[8]以負載均衡為目標，首先將虛擬節(jié)點映射到距離已映射虛擬節(jié)點較近且負載最輕的底層節(jié)點上，而后使用最短路徑算法映射虛擬鏈路，并根據(jù)底層網(wǎng)絡資源狀況對承載網(wǎng)進行重映射。參考文獻[9]提出了節(jié)點與鏈路同時考慮的一步映射算法，然而由于該算法是基于分布式的，在性能和最優(yōu)性方面都與集中式存在差距。且算法沒有動態(tài)考慮構建請求的生存時間，即為已允許的構建需求所分配的資源將持久分配，這對新進請求的加入造成限制。參考文獻[10]提出了一種協(xié)調(diào)節(jié)點和鏈路映射的數(shù)學規(guī)劃。使用虛擬節(jié)點地理位置作為啟發(fā)式信息減少搜索空間，將造成熱點問題。且映射方案基于簡單經(jīng)濟模型構建，其定價/花費是線性函數(shù)，沒有提供能夠最大化底層網(wǎng)絡的承載網(wǎng)構建請求之間的競爭機制。

為了提高服務承載網(wǎng)請求接受率，最大化成本收益，博弈論也日益受到研究者的關注。參考文獻[11]設計了一種分布式算法，以實現(xiàn)數(shù)據(jù)中心網(wǎng)絡中有效公平的帶寬分配。算法通過調(diào)整基礎帶寬，為云提供者提供了公平共享與最小數(shù)據(jù)保障之間的均衡折中。參考文獻[12]針對視頻數(shù)據(jù)爆發(fā)性增長，提出了一種整數(shù)規(guī)劃算法；并通過綜合考慮視頻片段的大小和流行分布，提出了一種快速貪婪的方法解決這一NP難問題。參考文獻[13]引入博弈論，提出了一種解決服務器上視頻需求瞬間擁擠的遷移方法。但是，以上算法僅針對視頻需求，并未建立承載網(wǎng)構建的一般模型。參考文獻[14]以底層節(jié)點和鏈路作為參與者，通過構建合作博弈模型進行承載網(wǎng)映射。然而，算法將節(jié)點映射與鏈路映射相分離，分別進行博弈模型構建，而后將兩個博弈進行嵌套，增加了算法復雜度。

基于此，本文提出了一種基于拍賣的周期映射承載網(wǎng)構建算法。算法通過構建合作博弈模型，最大化承載網(wǎng)整體構建效益。通過周期映射，將時間周期內(nèi)的業(yè)務請求聚類，在最大化構建收益和最小化構建請求與建立的等待時間之間進行平衡。

3 問題描述

3.1 底層資源

構建底層資源模型，將底層物理網(wǎng)絡抽象為無向圖Gs=(Ns,Ls,Cs)，其中，Ns和Ls分別代表底層網(wǎng)絡中節(jié)點和鏈路的集合，Cs代表底層資源，即底層物理網(wǎng)絡所能提供的能力。底層資源通常包括節(jié)點資源和鏈路資源。其中，節(jié)點資源包括節(jié)點CPU和內(nèi)存容量，鏈路資源則主要指帶寬資源。同時，引入鏈路資源單位花費Clink和節(jié)點資源單位花費Cnode。

3.2 業(yè)務需求

RSCN業(yè)務需求模型可表示為無向圖Gr=(Nr,Lr,Rr)，其中，Nr和Lr分別表示RSCN中虛擬節(jié)點和虛擬鏈路的集合，分別是Ns和Ls的子集，RSCN構建請求通常包含對底層物理節(jié)點和鏈路的約束，用Rr代表對虛擬節(jié)點和虛擬鏈路的需求，包括虛擬節(jié)點的計算資源需求和存儲資源需求，虛擬鏈路的帶寬資源需求及時延需求。

同時，業(yè)務需求中還包括每個業(yè)務構建服務承載網(wǎng)的請求函數(shù)，包括愿購買資源量、愿出價格及使用時間等。

3.3 服務承載映射

RSCN構建問題可以表述成滿足Gr中約束條件Rr的由Gr到Gs子集的一個映射，表示如下：

其中，Nv奐Ns，Lv奐Ls，Gv表示構建RSCN的底層物理網(wǎng)絡的服務能力。RSCN構建可以分割成節(jié)點映射和鏈路映射。

節(jié)點映射：

鏈路映射：

其中，RrN和RrL分別表示RSCN構建中對虛擬節(jié)點和虛擬鏈路的限制條件，CvN和CvL分別代表構建RSCN的底層資源情況，即底層物理節(jié)點和鏈路所能提供的服務承載能力。

3.4 服務承載網(wǎng)構建目標

（1）底層資源最大化利用

構建服務承載網(wǎng)的初衷即在存在交集的多個物理資源上，提供具有不同服務能力的承載子網(wǎng)，對于有限的底層網(wǎng)絡，最大化底層資源利用，最大化總體構建收益即服務承載網(wǎng)的構建目標。因此，定義承載網(wǎng)整體構建收益如下：

（2）周期性映射

在服務承載網(wǎng)映射中，構建請求通常不會按照某種特定規(guī)律的時間間隔到達，本文算法提出周期映射的方式。將某一時間周期到達的服務承載網(wǎng)構建請求聚類處理，而后針對不同業(yè)務類型進行映射，既減少了系統(tǒng)開銷，又最優(yōu)化了構建收益。定義時間周期為T，則服務承載網(wǎng)構建請求集合為Gr(T)。

4 博弈論模型的構建

對于每個提出服務承載網(wǎng)構建請求的業(yè)務，構建的服務承載網(wǎng)為其分配相應的底層資源，而其終極目標即最大化系統(tǒng)總體效用，試圖使每個業(yè)務相互合作，形成合作博弈模型。這里假設業(yè)務都是按照自己的需求真實上報，并不存在謊報的情況。

4.1 模型要素

（1）參與者

定義業(yè)務為博弈參與者，用N={1,2,3,…,n}表示。

（2）策略

構建博弈的策略集合C={Bw,Dl,Cbm,CPcpu}，其中，Bw表示鏈路帶寬，Dl表示時延需求，即業(yè)務提出的相應的鏈路需求；節(jié)點需求分別由Cbm和CPcpu表示，Cbm為緩存容量（buffer memory capacity），CPcpu為CPU計算能力（CPU calculate power）。

（3）效用函數(shù)

效用函數(shù)定義為最大化服務承載網(wǎng)構建整體收益，即由業(yè)務的支付總和減去滿足業(yè)務需求所構建服務承載網(wǎng)的花費的“凈收入”，即：

那么，最大化整體收益問題可以表示為：

其中，式(7)表示構建請求出價大于底層資源損耗；式(8)表示所選路徑時延小于構建請求的時延需求；式(9)表示當前承載的n個業(yè)務的虛擬節(jié)點消耗的緩存資源之和小于節(jié)點最大緩存容量；式(10)表示當前承載的n個業(yè)務的虛擬節(jié)點消耗的CPU計算資源之和小于節(jié)點最大CPU計算能力；式(11)表示當前承載的n個業(yè)務的虛擬鏈路消耗的帶寬資源之和小于鏈路的最大帶寬。

4.2 定價機制

現(xiàn)有定價機制主要包括針對特定用戶、協(xié)商及拍賣等。針對特定用戶的定價，一是缺乏普適應，二是增加系統(tǒng)開銷；協(xié)商定價需要服務提供方與業(yè)務就價格反復商議，直到達成共識，其收斂時間較長，系統(tǒng)開銷大；而拍賣定價機制只需業(yè)務向服務提供方提出所需資源及支付意愿，服務提供方據(jù)此進行服務承載網(wǎng)構建，分配底層資源并收費。當然，其前提條件是提出構建服務承載網(wǎng)需求的業(yè)務真實地表達了自身的業(yè)務需求。因此，本算法基于拍賣機制定價。

4.2.1 業(yè)務需求函數(shù)

所謂業(yè)務需求函數(shù)qn(Pn,tn)，是在使用時間tn內(nèi)，業(yè)務n愿意為所需資源qn支付的價格Pn。本文定義業(yè)務需求函數(shù)中的參數(shù)包括：愿出價格、購買資源量、資源使用時間，表示為

4.2.2 拍賣規(guī)則

假設在某一周期T，n個業(yè)務提出構建服務承載網(wǎng)的請求，競爭總量為Q的底層資源，已知在不同的資源價格Pn下，業(yè)務n愿意購買資源qn。首先根據(jù)各業(yè)務的出價確定周期T內(nèi)的單位資源價格：

式(12)表示，在滿足n個業(yè)務構建總需求不大于底層總資源量Q的情況下，將n個業(yè)務中單位資源價格的最大值作為周期T內(nèi)的單位資源價格，由此可得：

業(yè)務n可分得的資源qn(T)為：

業(yè)務n需為此支付的費用cn為：

4.2.3 拍賣規(guī)則性質(zhì)

當業(yè)務的出價qn(Pn,tn)是真實的，由式(12)所得為市場出清價格，這將使資源配置達到最優(yōu)，即當所有參與者都已知業(yè)務數(shù)量n和資源總量Q時，且Q不變，則在拍賣結果中存在Nash均衡[15]。即若參與的某業(yè)務有意壓低報價，將導致服務承載網(wǎng)構建的整體效益降低。

實際情況中，n和Q不可能成為所有業(yè)務的公共知識，對業(yè)務而言，n和Q是不確定的，這就迫使業(yè)務要真實的表達自身需求。同時，在網(wǎng)絡條件下，業(yè)務對底層網(wǎng)絡的信息優(yōu)勢受到抑制，這也促使業(yè)務要“講真話”。

4.2.4 拍賣中存在的問題

算法采用的拍賣機制是周期性的。在不同周期T，資源價格是變化的。然而對于跨越幾個計費周期的業(yè)務而言，按照各周期的資源價格進行收費顯然是不現(xiàn)實的，這將給業(yè)務造成超出預算的風險和負擔。因此，算法規(guī)定，單位資源價格以業(yè)務加入網(wǎng)絡時為準，其生存時間內(nèi)，不隨周期性的拍賣機制變化。但當前生存周期結束，再次請求資源時，就需按當時的單位資源繳費。

4.3 基于拍賣博弈的服務承載網(wǎng)動態(tài)構建模型DAGR

假設時間周期T內(nèi)，到達了n個業(yè)務的服務承載網(wǎng)構建請求，每個構建請求提交信息分別包括使用時間tn、資源需求qn和愿付價格Pn。由拍賣機制確定業(yè)務需要為此支付的費用cn，并將其反饋給相應業(yè)務。對于接受費用的業(yè)務請求構建請求集合，進行服務承載網(wǎng)構建。

在服務承載網(wǎng)映射中，首先將業(yè)務請求構建為集合Qn，并按照業(yè)務類型將其聚類為Qi。收集底層網(wǎng)絡資源信息，計算得到滿足業(yè)務需求的所有可行路徑集合，將各條路徑代入式(5)，得到最優(yōu)路徑及最優(yōu)帶寬，至此，將Qi映射到滿足其業(yè)務需求的底層網(wǎng)絡，完成服務承載網(wǎng)構建。算法流程如圖3所示。

圖3 基于拍賣博弈的可重構服務承載網(wǎng)構建流程

5 實驗仿真

為評估算法的效能，本文將與基于簡單經(jīng)濟模型并協(xié)調(diào)節(jié)點與鏈路映射的ViNEYard[10]算法和以負載均衡為目標的G-SP[8]算法進行性能比較。

5.1 實驗環(huán)境構建

仿真實驗中的基礎網(wǎng)絡拓撲由BRITE工具隨機產(chǎn)生的150個節(jié)點組成，節(jié)點連接率為0.5，節(jié)點與鏈路資源服從50～100的均勻分布。RSCN節(jié)點個數(shù)需求滿足2～10的均勻分布，鏈路帶寬需求、節(jié)點CPU能力及緩存容量均服從0～30的均勻分布，節(jié)點連接率為0.5。業(yè)務請求構建RSCN的到達過程服從時間單位為100、強度為10的泊松過程；每個RSCN的生存時間服從期望值為1000的指數(shù)分布。映射周期為一個單位時間T。假設各業(yè)務構建請求單位資源出價服從1～3的均勻分布，而底層節(jié)點單位花費和鏈路單位花費相等且均為1。并假設只要通過拍賣機制后的單位資源價格不高于該業(yè)務出價的兩倍，業(yè)務都可接受。為了仿真結果的準確性，本文共進行仿真實驗20次，所取結果為所有實驗結果的平均值。

5.2 服務承載網(wǎng)構建總收益

圖4 服務承載網(wǎng)構建總收益

圖4 所示為10個周期T內(nèi)，不同算法構建服務承載網(wǎng)的總收益?？梢钥闯觯珼AGR算法較之其他算法，能帶來更多的收益。雖然G-SP算法以負載均衡為目標，但在進行服務承載網(wǎng)映射時，將節(jié)點映射與鏈路映射分兩階段處理，大大限制了方案空間，因此總收益比同時考慮節(jié)點和鏈路映射的ViNEYard算法略低。而基于拍賣機制的DAGR算法激發(fā)了各業(yè)務之間的競爭，比其他兩種算法相應地得到了更高的構建總收益。

5.3 服務承載網(wǎng)構建成功率

定義1（RSCN構建成功率）RSCN已構建成功的請求個數(shù)與構建請求總數(shù)之比，即：

式（15）中，Csuccess表 示RSCN成 功 構 建 的 請 求 數(shù)，Call表示構建請求總數(shù)。如圖5所示為不同時間周期內(nèi)的服務承載網(wǎng)構建成功率。由于ViNEYard算法進行承載網(wǎng)映射時，將節(jié)點映射和鏈路映射協(xié)調(diào)為一階段，因此，其構建成功率比采用節(jié)點、鏈路分別映射的G-SP算法高。DAGR算法以構建總收益為目標，存在定價時與業(yè)務的“雙向選擇”問題。實驗中設定，業(yè)務對于超過雙倍價于自己報價的定價，不予接受，基于此，在構建初期，會有部分業(yè)務主動放棄構建服務承載網(wǎng)的請求。因此，該算法的構建成功率在某些周期相對ViNEYard算法較低，在75%左右。

圖5 服務承載網(wǎng)構建成功率

6 結束語

針對不同業(yè)務對有限的底層網(wǎng)絡共享時存在的競爭問題，本文提出了一種基于拍賣博弈的服務承載網(wǎng)動態(tài)構建算法。算法能夠根據(jù)業(yè)務需求建立服務承載網(wǎng)，并實時感知業(yè)務變化，動態(tài)調(diào)整服務承載網(wǎng)的構建，最終實現(xiàn)整體系統(tǒng)的利益最大化。

1 蘭巨龍，程東年，胡宇翔．可重構信息通信基礎網(wǎng)絡體系研究．通信學報,2014，35（1）：128～139 Lan J L,Cheng D N,Hu Y X.Research on reconfigurable information communication basal network architecture.Journal on Communications,2014,35(1):128～139

2 中華人民共和國科學技術部．《可重構信息通信基礎網(wǎng)絡體系研究》項目計劃任務書,2011 Ministry of Science and Technology of the People’s Republic of China.Project Plan of Research on Reconfigurable Information Communication Basal Network Architecture,2011

3 Fischer A,Botero J F,Beck M T,et al.Virtual network embedding:a survey.IEEE Communications Surveys & Tutorials,2013,15(4):1888～1906

4 Gomes R L,Bittencourt L F,Madeira E R M.A bandwidth-feasibility algorithm for reliable virtual network allocation.Proceedings of IEEE 28th International Conference on Advanced Information Networking and Applications,Victoria,Australia,2014:504～511

5 Kareche S,Ductor S,Mezghiche M.A new robust heuristic for assigning substrate network resources to virtual networks.Proceedings of International Conference on Advanced Networking Distributed Systems and Applications,Bejaia,Algeria,2014:47～52

6 Chase J,Kaewpuang R,Wen Y G,et al.Joint virtual machine and bandwidth allocation in software defined network(SDN)and cloud computing environments.Proceedings of IEEE ICC,Sydney,Australia,2014:2969～2974

7 江逸茗，蘭巨龍，周慧琴．網(wǎng)絡虛擬化環(huán)境下的資源監(jiān)控策略．電子與信息學報,2014，36（3）：708～714 Jiang Y M,Lan J L,Zhou H Q.Resource monitoring policy for network virtualization environment.Journal of Electronics &Information Technology,2014,36(3):708～714

8 Zhu Y,Ammar M.Algorithms for assigning substrate network resources to virtual network components.Proceedings of IEEE INFOCOM,Barcelona,Spain,2006:1～12

9 He J,Zhang S R,Li Y,et al.Davinci:dynamically adaptive virtual networks for a customized internet.Proceedings of ACM CoNEXT,Madrid,Spain,2008:1～12

10 Chowdhury N,Rahman M,Boutaba R.ViNEYard:virtual network embedding algorithms with coordinated node and link mapping.ACM/IEEE Transaction on Networking,2011,20(1):206～219

11 Guo J,Liu F M,Zeng D,et al.A cooperative game based allocation for sharing data center networks.Proceedings of IEEE INFOCOM,Turin,Italy,2013:2139～2147

12 He J,Zhao X M,Zhao B H.A fast,simple and near-optimal content placement scheme for a large-scale VoD system.Proceedings of 2012 IEEE International Conference on Communication Systems(ICCS),Singapore,2012:378～382

13 Feng Y,Li B.Bargaining towards maximized resource utilization in video streaming datacenters.Proceedings of IEEE INFOCOM,Orlando,2012:1134～1142

14 Soualah O,Fajjari I,Aitsaadi N,et al.A reliable virtual network embedding algorithm based on game theory within cloud’s backbone.Proceedings of IEEE International Conference on Communications(ICC),Sydney,Australia,2014:2975～2981

15 Back K,Zender J F.Auctions of divisible goods:on the rationale for the Treasury experiment.Review of Financial Studies,1993,30(3):733～764