基于談判博弈的分布式協(xié)同網(wǎng)絡(luò)服務(wù)布局算法框架

程國振，陳梓桓，張靖羽

（1.國家數(shù)字交換系統(tǒng)工程技術(shù)研究中心，鄭州 450002;2.長沙市長郡中學(xué)，長沙410000）

當(dāng)前，互聯(lián)網(wǎng)承載著大量服務(wù)，并被部署于整個(gè)網(wǎng)絡(luò)中。由于巨大的服務(wù)規(guī)模以及高動(dòng)態(tài)的互聯(lián)網(wǎng)負(fù)載，分布式的組織和優(yōu)化服務(wù)提供以實(shí)現(xiàn)網(wǎng)絡(luò)效用最大化是一個(gè)難點(diǎn)。一方面，數(shù)據(jù)中心網(wǎng)絡(luò)（Data Center Network,DCN）、軟件定義網(wǎng)絡(luò)（Software Defined Network,SDN）等新型網(wǎng)絡(luò)的應(yīng)用降低了管理大量服務(wù)的難度。另一方面，DCN中虛擬化的應(yīng)用，SDN對(duì)網(wǎng)絡(luò)功能的重新抽象和細(xì)粒度分解，又極大地增加了網(wǎng)絡(luò)服務(wù)實(shí)體的數(shù)量，其組成成分更加復(fù)雜。因此，分布式網(wǎng)絡(luò)服務(wù)放置問題[1-2]不論對(duì)當(dāng)前網(wǎng)絡(luò)還是未來網(wǎng)絡(luò)都是一個(gè)挑戰(zhàn)。

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

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

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

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

①將分布式布局問題建模為討價(jià)還價(jià)的經(jīng)濟(jì)活動(dòng)，并從理論上證明最優(yōu)布局解的存在，且為納什談判解（Nash Bargain Solution,NBS）。

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

③通過仿真驗(yàn)證了算法的有效性。

1 相關(guān)工作

布局問題是一個(gè)NP-難問題，其求解算法已經(jīng)被廣泛地研究。下面按應(yīng)用領(lǐng)域不同展開討論。

隨著數(shù)據(jù)中心網(wǎng)絡(luò)的發(fā)展，大量研究人員為提高數(shù)據(jù)中心網(wǎng)絡(luò)運(yùn)營效率展開廣泛研究。其中，虛擬機(jī)的合理布局可以有效降低數(shù)據(jù)中心資源代價(jià)而成為研究熱點(diǎn)。Feng等[5]提出了基于討價(jià)還價(jià)理論的虛擬機(jī)（Virtual Machine,VM）布局方法，但其將VM建模成同質(zhì)實(shí)體，沒有考慮實(shí)際中VMs之間差異化的特征，本文算法同時(shí)考慮不同類型的網(wǎng)絡(luò)服務(wù)的布局問題。Guo等[6]從影子路由（shadow router）的角度提出一種動(dòng)態(tài)的VM布局算法。Rochman等[7]在分布式網(wǎng)絡(luò)拓?fù)湎碌木W(wǎng)絡(luò)布局建模為最小費(fèi)用流問題。

在內(nèi)容分發(fā)網(wǎng)絡(luò)和Web緩沖中，高效的內(nèi)容副本布局問題被廣泛研究[8-9]。這些研究把內(nèi)容副本（網(wǎng)絡(luò)服務(wù)）布局在地理位置不同的節(jié)點(diǎn)，提高性能和訪問的可達(dá)性。這一領(lǐng)域的研究主要集中在給定用戶的請求模式和最優(yōu)化服務(wù)器響應(yīng)請求的成功比例，而對(duì)服務(wù)器的容量無約束（一般假設(shè)服務(wù)器具有無限容量），本文的研究則建立在網(wǎng)絡(luò)節(jié)點(diǎn)有限容量的情況下進(jìn)行。

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

2 模型建立

2.1 網(wǎng)絡(luò)服務(wù)布局問題

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

2.2 討價(jià)還價(jià)模型

設(shè)有M類型的網(wǎng)絡(luò)服務(wù)為談判博弈參與者，博弈的商品則是網(wǎng)絡(luò)中的節(jié)點(diǎn)。布局一類服務(wù)一般需要達(dá)到一定規(guī)模才能產(chǎn)生效益，因此出于布局成本、效益以及規(guī)模效應(yīng)的考慮，每類服務(wù)i網(wǎng)絡(luò)節(jié)點(diǎn)的布局需要保證一個(gè)基本量，記為Bi。保證一個(gè)基本量的另一個(gè)解釋是在布局過程中不同類型的請求分布可能出現(xiàn)不均衡現(xiàn)象，即某些服務(wù)類型的請求量大，而某些服務(wù)的請求量小，為了避免布局過程中過于偏向“受歡迎”服務(wù)，而“餓死”“不受歡迎”服務(wù)的情況，所以每類服務(wù)在網(wǎng)絡(luò)中的布局?jǐn)?shù)量規(guī)定一種最小值，稱為基本布局量。

定理1網(wǎng)絡(luò)中服務(wù)布局的最優(yōu)問題等價(jià)于Nash談判博弈中的聯(lián)合利益最大化問題。

3 分布式協(xié)同布局算法

3.1 對(duì)偶分解

由于問題( )Pl的復(fù)雜度受服務(wù)類型和網(wǎng)絡(luò)規(guī)模的影響，因此，本文從其拉格朗日對(duì)偶問題的角度出發(fā)求解以消除影響。問題( )Pl可轉(zhuǎn)化為如下等價(jià)形式

原始問題分解為N個(gè)不同的更加簡單的問題，可實(shí)現(xiàn)并行計(jì)算，提高運(yùn)算效率。

3.2 基于梯度影射的分布式協(xié)同算法

由問題(P l)到其對(duì)偶(D r)均是在松弛假設(shè)U?RN×M條件下推導(dǎo)得到，由GPA算法得到的結(jié)果為。但是實(shí)際中的nik∈N，因此需要對(duì)松弛后的結(jié)果進(jìn)行調(diào)整。對(duì)于的近似，直觀的思路有兩種策略：a)直接取，即為小于的整數(shù)；b)取，即，大于的整數(shù)。策略a可以在節(jié)點(diǎn)資源約束下，成功完成部署，但是可能出現(xiàn)用戶部分請求得不到響應(yīng)；策略b雖然能夠成功滿足當(dāng)前用戶的所有請求，但是可能會(huì)因?yàn)楸徊季志W(wǎng)絡(luò)節(jié)點(diǎn)資源受限，導(dǎo)致布局策略失效?；诜?wù)本地和遠(yuǎn)端的效用比，綜合兩種策略，即，在網(wǎng)絡(luò)節(jié)點(diǎn)資源允許的情況下，盡量在本地滿足效用比較大的需求。

4 性能評(píng)估

4.1 仿真環(huán)境

本文采用GT-ITM工具[22]產(chǎn)生三種200個(gè)節(jié)點(diǎn)的隨機(jī)圖模擬相同節(jié)點(diǎn)規(guī)模的網(wǎng)絡(luò)拓?fù)洌骄鶊D連接度d分別為20，10和5。

假設(shè)網(wǎng)絡(luò)拓?fù)渲兴泄?jié)點(diǎn)均為同質(zhì)化節(jié)點(diǎn)，具有相同的可支配資源，即，在節(jié)點(diǎn)空載情況下，對(duì)于任意類型的服務(wù)，每個(gè)節(jié)點(diǎn)可以承載相同數(shù)量的該類型服務(wù)實(shí)例。由于不同服務(wù)類型占用資源情況的多樣性，每個(gè)節(jié)點(diǎn)對(duì)于不同類型的服務(wù)實(shí)例的承載數(shù)量具有差異性。為了量化這種差異性，本文給出“節(jié)點(diǎn)承載量”的概念，且實(shí)驗(yàn)中節(jié)點(diǎn)承載量服從500～10 000的均勻分布。

定義1節(jié)點(diǎn)承載量服務(wù)類型i的實(shí)例在獨(dú)占網(wǎng)絡(luò)節(jié)點(diǎn) j情況下可布局的最大數(shù)量，稱為服務(wù)類型i在節(jié)點(diǎn) j的承載量，記為cij。由于本實(shí)驗(yàn)假設(shè)網(wǎng)絡(luò)節(jié)點(diǎn)是同質(zhì)的，因此服務(wù)類型i的節(jié)點(diǎn)承載量可簡記為ci。

為了考察不同規(guī)模服務(wù)類型情況下算法的性能，實(shí)驗(yàn)分別設(shè)置服務(wù)類型數(shù)量不同的三組實(shí)驗(yàn)，服務(wù)類型數(shù)量M分別取10,100,1000。

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

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

4.2 仿真結(jié)果

本文的目標(biāo)是通過合理布局服務(wù)，最大化節(jié)點(diǎn)資源效用，滿足更多用戶需求?；谇耙还?jié)給出的實(shí)驗(yàn)環(huán)境，本節(jié)主要考察三種拓?fù)湎抡埱箜憫?yīng)率、節(jié)點(diǎn)資源效率以及不同基本布局量對(duì)算法的影響。在對(duì)請求響應(yīng)率和節(jié)點(diǎn)效用比的實(shí)驗(yàn)中，算法框架的基本布局量門限為1 000，網(wǎng)絡(luò)中節(jié)點(diǎn)的初始布局量服從500～10 000的均勻分布。

首先給出度量用戶請求是否被成功響應(yīng)的量——節(jié)點(diǎn)的請求響應(yīng)率。請求響應(yīng)率反映了本文算法的布局對(duì)用戶體驗(yàn)的影響。請求響應(yīng)率高表明用戶體驗(yàn)良好，未出現(xiàn)服務(wù)等級(jí)承諾違約情況，反之，請求響應(yīng)率低表明用戶體驗(yàn)差，可能出現(xiàn)服務(wù)等級(jí)承諾違約。

定義2請求響應(yīng)率（hit ratio of requests）節(jié)點(diǎn)i的請求響應(yīng)率s(i)為節(jié)點(diǎn)i實(shí)際成功響應(yīng)的請求數(shù)h(i)與節(jié)點(diǎn)當(dāng)前總的請求數(shù)r(i)比，即

圖1給出了不同拓?fù)湎虏煌?guī)模服務(wù)類型下的請求響應(yīng)率變化。規(guī)模大的服務(wù)類型情況下比規(guī)模小的情況下的請求響應(yīng)率高，例如，M=1 000的情況下較M=100和M=10的情況下的請求響應(yīng)率高。因?yàn)樵诓┺倪^程中服務(wù)類型數(shù)量較大時(shí)，參與博弈的個(gè)體的數(shù)量較大，博弈過程也比較充分。由圖 1（a）、（b）和（c）可以看出，不同網(wǎng)絡(luò)拓?fù)湎?，其請求響?yīng)率不同。d=20和d=10兩種情況下，s(i)差異較小，而d=5時(shí)，請求響應(yīng)率下降較大。因?yàn)閐=5的情況下，鏈路數(shù)量減小，出現(xiàn)資源瓶頸，即使網(wǎng)絡(luò)節(jié)點(diǎn)可以容納足夠的服務(wù)實(shí)例，但鏈路資源大幅減少，導(dǎo)致資源不均衡現(xiàn)象，出現(xiàn)性能嚴(yán)重下降。但是在資源充足的情況下，可以看出算法得出的服務(wù)布局結(jié)果能夠迅速使得請求響應(yīng)率達(dá)到95%以上。由圖可知，在不同拓?fù)湎鲁跏颊埱箜憫?yīng)率相同或相近。原因是博弈起始階段，各網(wǎng)絡(luò)節(jié)點(diǎn)的初始布局量相同，等于基本布局量。

圖1 請求響應(yīng)率

4.3 算法比較

最后，本文將基于討價(jià)還價(jià)模型的GPA布局算法與經(jīng)典的LRU、LFU和LRFU布局策略在布局效果上作出比較。設(shè)仿真的網(wǎng)絡(luò)拓?fù)涔?jié)點(diǎn)數(shù)為200，連接度為d=10，網(wǎng)絡(luò)中服務(wù)類型為100，本節(jié)比較不同布局策略下的請求響應(yīng)率和節(jié)點(diǎn)效用比。由圖2可以看出，GPA策略優(yōu)于其他三種布局策略，因?yàn)镚PA基于討價(jià)還價(jià)模型，引入基本布局量，保證了請求響應(yīng)率。

圖2 布局策略比較

5 總結(jié)

本文將網(wǎng)絡(luò)服務(wù)布局問題建模為納什談判博弈，并設(shè)計(jì)了一種基于討價(jià)還價(jià)理論（bargain theory）的分布式網(wǎng)絡(luò)服務(wù)布局算法框架，通過網(wǎng)絡(luò)各節(jié)點(diǎn)的協(xié)同，實(shí)現(xiàn)網(wǎng)絡(luò)全局知識(shí)的獲得，以實(shí)現(xiàn)精準(zhǔn)布局。算法框架通過調(diào)節(jié)基本布局量實(shí)現(xiàn)了用戶體驗(yàn)與網(wǎng)絡(luò)效用之間的均衡，仿真結(jié)果表明本算法框架的有效性。