基于拍賣博弈的可重構服務承載網動態構建算法

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

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

1 引言

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

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

圖1 可重構服務承載網示意

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

在不同業務對有限的底層網絡進行共享時，如何根據業務需求建立服務承載網，并實時感知業務變化，動態調整服務承載網的構建，以期實現整體系統的利益最大化，這是本文要討論的問題。

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

圖2 基于拍賣博弈的可重構服務承載網架構

2 相關研究

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

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

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

3 問題描述

3.1 底層資源

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

3.2 業務需求

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

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

3.3 服務承載映射

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

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

節點映射：

鏈路映射：

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

3.4 服務承載網構建目標

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

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

（2）周期性映射

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

4 博弈論模型的構建

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

4.1 模型要素

（1）參與者

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

（2）策略

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

（3）效用函數

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

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

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

4.2 定價機制

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

4.2.1 業務需求函數

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

4.2.2 拍賣規則

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

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

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

業務n需為此支付的費用cn為：

4.2.3 拍賣規則性質

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

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

4.2.4 拍賣中存在的問題

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

4.3 基于拍賣博弈的服務承載網動態構建模型DAGR

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

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

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

5 實驗仿真

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

5.1 實驗環境構建

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

5.2 服務承載網構建總收益

圖4 服務承載網構建總收益

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

5.3 服務承載網構建成功率

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

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

圖5 服務承載網構建成功率

6 結束語

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

1 蘭巨龍，程東年，胡宇翔．可重構信息通信基礎網絡體系研究．通信學報,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 中華人民共和國科學技術部．《可重構信息通信基礎網絡體系研究》項目計劃任務書,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 江逸茗，蘭巨龍，周慧琴．網絡虛擬化環境下的資源監控策略．電子與信息學報,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