基于談判博弈的分布式協同網絡服務布局算法框架

程國振，陳梓桓，張靖羽

（1.國家數字交換系統工程技術研究中心，鄭州 450002;2.長沙市長郡中學，長沙410000）

當前，互聯網承載著大量服務，并被部署于整個網絡中。由于巨大的服務規模以及高動態的互聯網負載，分布式的組織和優化服務提供以實現網絡效用最大化是一個難點。一方面，數據中心網絡（Data Center Network,DCN）、軟件定義網絡（Software Defined Network,SDN）等新型網絡的應用降低了管理大量服務的難度。另一方面，DCN中虛擬化的應用，SDN對網絡功能的重新抽象和細粒度分解，又極大地增加了網絡服務實體的數量，其組成成分更加復雜。因此，分布式網絡服務放置問題[1-2]不論對當前網絡還是未來網絡都是一個挑戰。

網絡服務在不同研究領域的含義不同。例如在云計算網絡中，網絡服務模型分為設備即服務（Infrastructure as a Service）、平臺即服務（Platform as a Service）和軟件即服務（software as a Service）[3]；在內容中心網絡（Content-Centric Network,CCN）[4]中，網絡服務為提供視頻、文件等內容。本文中提到的網絡服務（Network Service,NS）泛指細小網絡功能單元或細粒度的網絡資源。

服務布局對于優化服務提供，降低網絡資源消耗具有現實意義。一個典型例子是云服務提供商。一般地，大型云服務提供商的用戶遍布全球。為了實現用戶請求就近“消化”的目的，它可能在不同地區建立多個分布式服務群（service farms）。由于服務群的存儲容量有限，一般的策略是服務群存儲其所在區域被最頻繁訪問的服務。理想情況下，提供商期望預先載入（布局）本地用戶請求的服務，若本地的服務請求由本區域的服務實例響應，用戶將避免訪問遠程服務實例，降低用戶通信開銷和時延，提高網絡效用。因此，如何在服務群中合理布局租戶的應用是節省云資源，提高云服務中心容量的關鍵。

然而，網絡服務在整個網絡中的最優布局面臨以下三個難點。首先，網絡服務的類型具有多樣性，網絡服務總體規模較大。例如，以視頻分發服務為核心的P2P網絡，其視頻內容多樣，相同內容的視頻資源根據LRU（Least recently used）、LFU（Least frequently used）以及LRFU等緩存策略將其拷貝布局于網絡中，以降低用戶的訪問代價。其次，分布式網絡一般分域管理，且不同區域的資源分布情況不同，因此跨區域布局更加困難。最后，網絡用戶對服務的請求具有動態特性，使得布局難以跟隨用戶需求動態變化。

綜上，網絡服務布局通常需要網絡全局知識，為此，本文提出了一種基于討價還價理論（Bargain theory）的分布式協同網絡服務布局算法，通過網絡節點的分布式協同，獲取網絡全局知識，以實現服務布局。討價還價理論是協同博弈論的分支，通過市場上分布式的討價活動，實現消息最大化的經濟理論。該理論可用于指導網絡服務布局。本文將不同類型的網絡服務看作博弈的參與者（player），博弈的商品（commodity）則是網絡節點資源。在網絡容量約束和用戶請求分布已知的情況下，參與者不斷地出價“購買”商品，以布局其服務實例（網絡功能實例）。本文的主要貢獻如下：

①將分布式布局問題建模為討價還價的經濟活動，并從理論上證明最優布局解的存在，且為納什談判解（Nash Bargain Solution,NBS）。

②以梯度映射方法（Gradient Project Algorithm,GPA）為核，設計算法求解上述問題。首先通過松弛服務布局量為非負實數，得到原始問題的對偶分解形式，利用GPA求解計算其NBS解，然后對得到的NBS采用特定策略整數化。

③通過仿真驗證了算法的有效性。

1 相關工作

布局問題是一個NP-難問題，其求解算法已經被廣泛地研究。下面按應用領域不同展開討論。

隨著數據中心網絡的發展，大量研究人員為提高數據中心網絡運營效率展開廣泛研究。其中，虛擬機的合理布局可以有效降低數據中心資源代價而成為研究熱點。Feng等[5]提出了基于討價還價理論的虛擬機（Virtual Machine,VM）布局方法，但其將VM建模成同質實體，沒有考慮實際中VMs之間差異化的特征，本文算法同時考慮不同類型的網絡服務的布局問題。Guo等[6]從影子路由（shadow router）的角度提出一種動態的VM布局算法。Rochman等[7]在分布式網絡拓撲下的網絡布局建模為最小費用流問題。

在內容分發網絡和Web緩沖中，高效的內容副本布局問題被廣泛研究[8-9]。這些研究把內容副本（網絡服務）布局在地理位置不同的節點，提高性能和訪問的可達性。這一領域的研究主要集中在給定用戶的請求模式和最優化服務器響應請求的成功比例，而對服務器的容量無約束（一般假設服務器具有無限容量），本文的研究則建立在網絡節點有限容量的情況下進行。

另一些研究人員聚焦于P2P網絡的視頻服務代價問題上。Tewari等[10]研究P2P網絡的副本布局問題，提出了比例復制（proportional replication），即基于平均需求，最小化下載過程中的鏈路數。相似的研究工作如參考文獻[11]。文獻[12]則是基于隨機分配策略最小化訪問失敗率。這些工作假設文件數量和對等體（peers）的數量足夠大，使得所有請求均被滿足。基于混合整數規劃，文獻[13]提出了一種描述大規模VoD的布局框架。Tan等[14]基于漸進性分析建立了一種比例復制的網絡性能損失模型。而文獻[15]假設電影數量小于對等體數量的情況下，提出了一種優化布局副本算法。這些研究主要用于小規模扁平網絡中，并未考慮層次化、跨區域情況。

2 模型建立

2.1 網絡服務布局問題

將研究的網絡抽象為一個無向圖模型G=(N,E)，N={v1,v2,…,vN}為節點集合，E為鏈路集合。該抽象網絡模型中的節點可能是僅對應一個物理節點，也可能是一個網絡，如在SDN網絡中，單控制器控制的局域網絡；或者承載于數據中心網絡中的一個獨立虛擬網（virtual network,VN），亦或者是P2P網絡中的一個對等區域（peering area）等。每個節點可布局M類型的服務。設不同類型服務的請求數為隨機變量，其分布為，i=1,2,…,M，k=1,2,…,N.N集合中元素存在局部約束，即網絡節點vk布局容量為zk。那么，服務布局問題可表述為：已知服務請求分布D，在可行域內，從布局策略集合中選擇最優策略，使得網絡期望的效用R最大化，其中，i=1,2,…,M，k=1,2,…,N。假設網絡中的所有節點掌握其他節點在時刻t的服務承載能力以及處理的服務請求分布等全局知識。那么，基于中心的效用函數最大化問題可表示為

2.2 討價還價模型

設有M類型的網絡服務為談判博弈參與者，博弈的商品則是網絡中的節點。布局一類服務一般需要達到一定規模才能產生效益，因此出于布局成本、效益以及規模效應的考慮，每類服務i網絡節點的布局需要保證一個基本量，記為Bi。保證一個基本量的另一個解釋是在布局過程中不同類型的請求分布可能出現不均衡現象，即某些服務類型的請求量大，而某些服務的請求量小，為了避免布局過程中過于偏向“受歡迎”服務，而“餓死”“不受歡迎”服務的情況，所以每類服務在網絡中的布局數量規定一種最小值，稱為基本布局量。

定理1網絡中服務布局的最優問題等價于Nash談判博弈中的聯合利益最大化問題。

3 分布式協同布局算法

3.1 對偶分解

由于問題( )Pl的復雜度受服務類型和網絡規模的影響，因此，本文從其拉格朗日對偶問題的角度出發求解以消除影響。問題( )Pl可轉化為如下等價形式

原始問題分解為N個不同的更加簡單的問題，可實現并行計算，提高運算效率。

3.2 基于梯度影射的分布式協同算法

由問題(P l)到其對偶(D r)均是在松弛假設U?RN×M條件下推導得到，由GPA算法得到的結果為。但是實際中的nik∈N，因此需要對松弛后的結果進行調整。對于的近似，直觀的思路有兩種策略：a)直接取，即為小于的整數；b)取，即，大于的整數。策略a可以在節點資源約束下，成功完成部署，但是可能出現用戶部分請求得不到響應；策略b雖然能夠成功滿足當前用戶的所有請求，但是可能會因為被布局網絡節點資源受限，導致布局策略失效。基于服務本地和遠端的效用比，綜合兩種策略，即，在網絡節點資源允許的情況下，盡量在本地滿足效用比較大的需求。

4 性能評估

4.1 仿真環境

本文采用GT-ITM工具[22]產生三種200個節點的隨機圖模擬相同節點規模的網絡拓撲，平均圖連接度d分別為20，10和5。

假設網絡拓撲中所有節點均為同質化節點，具有相同的可支配資源，即，在節點空載情況下，對于任意類型的服務，每個節點可以承載相同數量的該類型服務實例。由于不同服務類型占用資源情況的多樣性，每個節點對于不同類型的服務實例的承載數量具有差異性。為了量化這種差異性，本文給出“節點承載量”的概念，且實驗中節點承載量服從500～10 000的均勻分布。

定義1節點承載量服務類型i的實例在獨占網絡節點 j情況下可布局的最大數量，稱為服務類型i在節點 j的承載量，記為cij。由于本實驗假設網絡節點是同質的，因此服務類型i的節點承載量可簡記為ci。

為了考察不同規模服務類型情況下算法的性能，實驗分別設置服務類型數量不同的三組實驗，服務類型數量M分別取10,100,1000。

根據文獻[6]對視頻網絡的用戶請求分析，用戶對不同視頻的請求服從不同參數的正態分布。因此，不同類型的服務在網絡節點上的請求分布采用正態分布模擬。一般地，不同類型的服務在用戶中受歡迎程度不同，為此，本實驗定義“流行度”（Popularity）的概念進行描述。資源消耗型服務代價較高，其在用戶中的流行性也會降低。因此，流行度定義為0～1之間的常數，某類型的服務越受歡迎，流行度越高。因此，服務類型i的流行度p(i)計算為

用戶請求的正態分布參數可基于流行度設置。流行度越高的服務類型，其請求數越大。因此，設定流行度為用戶對不同類型服務的請求分布的均值，方差為常數1，產生的服從正態分布的請求數單位為萬次每秒，記為w/s。

4.2 仿真結果

本文的目標是通過合理布局服務，最大化節點資源效用，滿足更多用戶需求。基于前一節給出的實驗環境，本節主要考察三種拓撲下請求響應率、節點資源效率以及不同基本布局量對算法的影響。在對請求響應率和節點效用比的實驗中，算法框架的基本布局量門限為1 000，網絡中節點的初始布局量服從500～10 000的均勻分布。

首先給出度量用戶請求是否被成功響應的量——節點的請求響應率。請求響應率反映了本文算法的布局對用戶體驗的影響。請求響應率高表明用戶體驗良好，未出現服務等級承諾違約情況，反之，請求響應率低表明用戶體驗差，可能出現服務等級承諾違約。

定義2請求響應率（hit ratio of requests）節點i的請求響應率s(i)為節點i實際成功響應的請求數h(i)與節點當前總的請求數r(i)比，即

圖1給出了不同拓撲下不同規模服務類型下的請求響應率變化。規模大的服務類型情況下比規模小的情況下的請求響應率高，例如，M=1 000的情況下較M=100和M=10的情況下的請求響應率高。因為在博弈過程中服務類型數量較大時，參與博弈的個體的數量較大，博弈過程也比較充分。由圖 1（a）、（b）和（c）可以看出，不同網絡拓撲下，其請求響應率不同。d=20和d=10兩種情況下，s(i)差異較小，而d=5時，請求響應率下降較大。因為d=5的情況下，鏈路數量減小，出現資源瓶頸，即使網絡節點可以容納足夠的服務實例，但鏈路資源大幅減少，導致資源不均衡現象，出現性能嚴重下降。但是在資源充足的情況下，可以看出算法得出的服務布局結果能夠迅速使得請求響應率達到95%以上。由圖可知，在不同拓撲下初始請求響應率相同或相近。原因是博弈起始階段，各網絡節點的初始布局量相同，等于基本布局量。

圖1 請求響應率

4.3 算法比較

最后，本文將基于討價還價模型的GPA布局算法與經典的LRU、LFU和LRFU布局策略在布局效果上作出比較。設仿真的網絡拓撲節點數為200，連接度為d=10，網絡中服務類型為100，本節比較不同布局策略下的請求響應率和節點效用比。由圖2可以看出，GPA策略優于其他三種布局策略，因為GPA基于討價還價模型，引入基本布局量，保證了請求響應率。

圖2 布局策略比較

5 總結

本文將網絡服務布局問題建模為納什談判博弈，并設計了一種基于討價還價理論（bargain theory）的分布式網絡服務布局算法框架，通過網絡各節點的協同，實現網絡全局知識的獲得，以實現精準布局。算法框架通過調節基本布局量實現了用戶體驗與網絡效用之間的均衡，仿真結果表明本算法框架的有效性。