張?jiān)弃Q，朱艷琴，紀(jì)其進(jìn)

(1. 蘇州大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇 蘇州 215006；2. 江蘇省計(jì)算機(jī)信息處理技術(shù)重點(diǎn)實(shí)驗(yàn)室，江蘇 蘇州 215006)

1 引言

P2P內(nèi)容分發(fā)網(wǎng)絡(luò)中的節(jié)點(diǎn)可以自由地提供或者獲取服務(wù)，沒有中心控制節(jié)點(diǎn)約束它們的行為，因此可能存在大量的自私節(jié)點(diǎn)。當(dāng)這些節(jié)點(diǎn)面對(duì)這樣一種處境，即將自己有限的資源用于服務(wù)自己，還是無(wú)私地奉獻(xiàn)給其他節(jié)點(diǎn)，以期待將來(lái)其他節(jié)點(diǎn)也會(huì)無(wú)私的幫助自己時(shí)，通常會(huì)選擇將有限的資源保留給自己使用。此外，由于獲取服務(wù)時(shí)無(wú)需付出任何代價(jià)，自私節(jié)點(diǎn)會(huì)無(wú)節(jié)制地使用整個(gè)系統(tǒng)中緊缺的帶寬資源。這使得P2P網(wǎng)絡(luò)中存在較為嚴(yán)重的搭便車（free-riding[1]）現(xiàn)象，甚至最后出現(xiàn)“公共地悲劇”[2]。當(dāng)前，針對(duì)這一類問(wèn)題的基本解決方案是引入各種虛擬貨幣機(jī)制，但這些機(jī)制均需中心控制節(jié)點(diǎn)，有違P2P網(wǎng)絡(luò)最初的構(gòu)想目標(biāo)。

隨著應(yīng)用P2P技術(shù)共享節(jié)點(diǎn)資源的日漸盛行，越來(lái)越多的研究者致力于P2P系統(tǒng)資源交易激勵(lì)機(jī)制的研究。文獻(xiàn)[3]中的作者給出基于VCG機(jī)制的網(wǎng)絡(luò)資源分配機(jī)制，雖然能夠解決自私用戶搶占網(wǎng)絡(luò)資源，但是該機(jī)制假設(shè)資源管理者存儲(chǔ)著所有用戶的效用函數(shù)，形成了中心節(jié)點(diǎn)瓶頸，故會(huì)嚴(yán)重影響P2P網(wǎng)絡(luò)的擴(kuò)展性；文獻(xiàn)[4]提出了一種基于節(jié)點(diǎn)歷史貢獻(xiàn)值的差分服務(wù)機(jī)制，但由于依據(jù)的是歷史貢獻(xiàn)值，故無(wú)法遏制當(dāng)前節(jié)點(diǎn)的自私行為；BitTorrent[5]使用“tit-for-tat”機(jī)制激勵(lì)節(jié)點(diǎn)為其他節(jié)點(diǎn)服務(wù)，能夠減少搭便車現(xiàn)象的發(fā)生，但是并沒有考慮接入帶寬的異質(zhì)性，使得接入帶寬較小的節(jié)點(diǎn)失去公平競(jìng)爭(zhēng)的機(jī)會(huì)。

本文借用經(jīng)濟(jì)學(xué)中的拍賣方法設(shè)計(jì)合理的帶寬分配機(jī)制，使得P2P節(jié)點(diǎn)的帶寬分配依賴于其“帶寬支付”能力，迫使獲取服務(wù)的節(jié)點(diǎn)主動(dòng)貢獻(xiàn)相應(yīng)的帶寬，用于服務(wù)潛在的資源請(qǐng)求節(jié)點(diǎn)。本文中的機(jī)制將無(wú)需增加額外的中心服務(wù)器，它將請(qǐng)求節(jié)點(diǎn)所獲得的帶寬資源與該節(jié)點(diǎn)愿意貢獻(xiàn)的帶寬資源相關(guān)聯(lián)，能夠有效避免“公共地悲劇”的發(fā)生，并且不影響新節(jié)點(diǎn)公平競(jìng)爭(zhēng)資源，從而可以使得整個(gè)P2P系統(tǒng)中的節(jié)點(diǎn)良性競(jìng)爭(zhēng)使用帶寬資源。

2 P2P帶寬分配的基本拍賣模型

2.1 系統(tǒng)模型

在本文中考慮由N個(gè)節(jié)點(diǎn)組成的網(wǎng)狀結(jié)構(gòu)P2P內(nèi)容分發(fā)網(wǎng)絡(luò)。節(jié)點(diǎn)間定期交換資源請(qǐng)求以及進(jìn)行資源分配，假設(shè)在資源分配期間網(wǎng)絡(luò)是穩(wěn)定的，即不考慮節(jié)點(diǎn)的加入或者退出。對(duì)于節(jié)點(diǎn)的動(dòng)態(tài)加入和離開的情況，本文應(yīng)用周期性的更新系統(tǒng)信息和節(jié)點(diǎn)數(shù)量的方法處理。在本文研究中，資源節(jié)點(diǎn)只考慮其他節(jié)點(diǎn)對(duì)于自己擁有的內(nèi)容數(shù)據(jù)的請(qǐng)求信息。由于數(shù)據(jù)傳輸?shù)闹饕Y源是帶寬，因而可以把資源請(qǐng)求抽象成帶寬請(qǐng)求。由于P2P網(wǎng)絡(luò)中請(qǐng)求節(jié)點(diǎn)和資源節(jié)點(diǎn)的對(duì)稱性，本文以某個(gè)資源節(jié)點(diǎn)為主要建模對(duì)象。

每個(gè)節(jié)點(diǎn)接入骨干網(wǎng)時(shí)擁有接入帶寬為Cibit/s，且上載帶寬和下載帶寬共享該接入帶寬。假設(shè)骨干網(wǎng)擁有足夠高的帶寬容量，則無(wú)需考慮骨干網(wǎng)中的路由及時(shí)延問(wèn)題。整個(gè)P2P系統(tǒng)的性能瓶頸集中在接入帶寬上，實(shí)質(zhì)問(wèn)題是上載和下載帶寬的比例如何設(shè)置。由于節(jié)點(diǎn)的自私性，傳統(tǒng)機(jī)制下節(jié)點(diǎn)通常會(huì)設(shè)置較低的上載帶寬比例，甚至為零，這使得整個(gè)系統(tǒng)中可為其他節(jié)點(diǎn)服務(wù)的上載帶寬資源極其稀缺。

拍賣問(wèn)題的原型是將N個(gè)物品通過(guò)競(jìng)拍分配給M個(gè)購(gòu)買者，其中，M＞N，以達(dá)到最大化社會(huì)效益或者最大化拍賣者利益的目標(biāo)。20世紀(jì)末開始，一些研究者將拍賣機(jī)制從微觀經(jīng)濟(jì)學(xué)引入到網(wǎng)絡(luò)資源的分配中[6～9]。故對(duì)于上述 P2P網(wǎng)絡(luò)中的某個(gè)資源節(jié)點(diǎn)，可以將其擁有的可提供給其他節(jié)點(diǎn)的上載帶寬視為可分割的拍賣物品，向該資源節(jié)點(diǎn)發(fā)出資源請(qǐng)求的節(jié)點(diǎn)視為購(gòu)買者，則帶寬分配問(wèn)題可以采用拍賣模型來(lái)建模。為了遏制節(jié)點(diǎn)的搭便車行為，成功拍得所需帶寬的請(qǐng)求節(jié)點(diǎn)需要以上載帶寬作為支付。

定義 1 節(jié)點(diǎn)擁有的空閑的、未分配的上載帶寬稱為可拍賣帶寬，也稱可提供服務(wù)帶寬。

定義 2 用于表示節(jié)點(diǎn)對(duì)于所分配到的上載帶寬滿意程度的函數(shù)稱為效用函數(shù)，該函數(shù)具有如下性質(zhì)：連續(xù)性、遞增性、嚴(yán)格凹的和可微性。

假設(shè)資源節(jié)點(diǎn)擁有可拍賣帶寬為 Ws，請(qǐng)求節(jié)點(diǎn)有N個(gè)，節(jié)點(diǎn)的私有效用函數(shù)為 Ui(?)，xi是資源節(jié)點(diǎn)依據(jù)競(jìng)價(jià) bi分配給請(qǐng)求節(jié)點(diǎn)i的帶寬數(shù)，則為帶寬分配向量。在該模型下，系統(tǒng)最優(yōu)化問(wèn)題就是求解式（1）。

式（1）～式（3）組成的是一個(gè)非線性規(guī)劃問(wèn)題，對(duì)于此類問(wèn)題在特定條件下是可解的（目標(biāo)函數(shù)是一個(gè)嚴(yán)格的凹函數(shù)，約束條件是凸集）。但是目標(biāo)函數(shù)中的效用函數(shù) Ui(?)是各個(gè)節(jié)點(diǎn)的私有信息，資源節(jié)點(diǎn)并不擁有該信息。考慮到P2P網(wǎng)絡(luò)的分布特性，該模型應(yīng)用到P2P網(wǎng)路中求解時(shí)必須對(duì)上述問(wèn)題進(jìn)行分解和轉(zhuǎn)換。

2.2 問(wèn)題分解

結(jié)合整個(gè)網(wǎng)絡(luò)中分為資源節(jié)點(diǎn)和請(qǐng)求節(jié)點(diǎn)這一特點(diǎn)，本文應(yīng)用優(yōu)化的標(biāo)準(zhǔn)方法拉格朗日對(duì)偶理論將上述問(wèn)題分為2部分處理，即資源節(jié)點(diǎn)和請(qǐng)求節(jié)點(diǎn)，并通過(guò)梯度法更新拉格朗日乘數(shù)求解整個(gè)問(wèn)題。

假設(shè)請(qǐng)求節(jié)點(diǎn)i為了獲取帶寬資源 wi向資源節(jié)點(diǎn)提交競(jìng)價(jià) bi≥ 0 ，則獲得的帶寬資源為 xi(bi)，需要付出的資源代價(jià)為 ci( bi)。 ci(?)稱為支付函數(shù)，該函數(shù)是連續(xù)的、遞增的、凸的，表示節(jié)點(diǎn)i獲取資源 xi(bi)需付出的代價(jià)，即在接受資源節(jié)點(diǎn)服務(wù)時(shí)需要保留 ci(bi) 單位的帶寬作為自己的上載帶寬，以便為其他潛在的請(qǐng)求節(jié)點(diǎn)提供服務(wù)，由此限制條件式（3）轉(zhuǎn)化為式（6）。通過(guò)這種方式使得原來(lái) P2P網(wǎng)絡(luò)中的無(wú)償獲取資源變?yōu)橛袃敨@取資源，從而讓自私請(qǐng)求節(jié)點(diǎn)選擇真實(shí)的帶寬需求，避免了“公共地悲劇”的發(fā)生，提高整個(gè)P2P網(wǎng)絡(luò)帶寬的有效利用率。

節(jié)點(diǎn)提交競(jìng)價(jià)后，下一步對(duì)于資源節(jié)點(diǎn)來(lái)說(shuō)就是求解式（1）所示的系統(tǒng)最優(yōu)化問(wèn)題，但由于效用函數(shù)是各個(gè)節(jié)點(diǎn)的私有信息，故資源節(jié)點(diǎn)無(wú)法得到每個(gè)請(qǐng)求節(jié)點(diǎn)的效用函數(shù)。在本機(jī)制中采用估值效用函數(shù)[10]bilog(xi+ 1 )代替式（1）中的效用函數(shù)，則在資源節(jié)點(diǎn)處系統(tǒng)最優(yōu)化問(wèn)題轉(zhuǎn)化為式（4）至式（6）。

其中， Ci表示節(jié)點(diǎn)當(dāng)前的空閑帶寬。

對(duì)于上述SYSTEM最優(yōu)化問(wèn)題，可以構(gòu)造如下拉格朗日對(duì)偶函數(shù)

由于 L (X,B,λ,μ)是嚴(yán)格凹的，故由凸優(yōu)化理論可知上述SYSTEM問(wèn)題有最優(yōu)解，且是唯一的。最優(yōu)解滿足如下的庫(kù)恩—塔克條件

對(duì)于式（8）有2種情況。

1) xi= 0 ，此時(shí)表示請(qǐng)求節(jié)點(diǎn)i給出的競(jìng)價(jià)為0。

2) xi≠ 0 ，此時(shí)表示請(qǐng)求節(jié)點(diǎn)i給出的競(jìng)價(jià)不為0，則得到式（9）

為了將上述2種情況統(tǒng)一，將式（9）修正為

為了求解原問(wèn)題，還必須知道拉格朗日乘數(shù)向量μ以及參數(shù)λ，通過(guò)原問(wèn)題的對(duì)偶問(wèn)題就可求解得到。根據(jù)拉格朗日對(duì)偶理論，對(duì)偶方程為

其中，Ω = {(X,B ) ∶xi≥ 0 ,bi≥ 0 }。對(duì)應(yīng)于原問(wèn)題的對(duì)偶問(wèn)題為

由前一輪的參數(shù)已得到當(dāng)前的B和X，下面計(jì)算使得 g (λ,μ)最小化的參數(shù)λ和μ。最小化可以通過(guò)以下2步計(jì)算得到

對(duì)于給定的 bi(t)和xi(t)，上述對(duì)偶問(wèn)題可以簡(jiǎn)化為

由于對(duì)偶函數(shù) g (?)可微，則請(qǐng)求節(jié)點(diǎn)和資源節(jié)點(diǎn)可分別應(yīng)用梯度迭代法求解式（15），進(jìn)而求解原問(wèn)題。運(yùn)用梯度法按如下方式更新上述參數(shù)

2.3 防止節(jié)點(diǎn)欺騙性行為

由于本文的方案是用現(xiàn)有的空閑上載帶寬支付獲取資源節(jié)點(diǎn)帶寬的代價(jià)，因此會(huì)涉及到如何保證節(jié)點(diǎn)誠(chéng)實(shí)支付的問(wèn)題?？赡馨l(fā)生如下情況：某個(gè)節(jié)點(diǎn)為了獲取盡可能多的帶寬資源，在競(jìng)拍時(shí)申明比實(shí)際能夠提供的更大的上載帶寬（即競(jìng)價(jià)）。由于競(jìng)價(jià)帶寬是為潛在需求節(jié)點(diǎn)服務(wù)，故資源節(jié)點(diǎn)無(wú)法認(rèn)證是否如實(shí)支付。監(jiān)測(cè)整個(gè)P2P網(wǎng)絡(luò)中節(jié)點(diǎn)的行為非常復(fù)雜，本文建議采用文獻(xiàn)[12]中的日志審計(jì)法，將所有請(qǐng)求節(jié)點(diǎn)的最終競(jìng)價(jià)以及資源節(jié)點(diǎn)的分配方案記入日志，并發(fā)送給區(qū)域控制節(jié)點(diǎn)（RC）。RC周期性的隨機(jī)檢測(cè)某些節(jié)點(diǎn)的日志，若發(fā)現(xiàn)有欺騙行為，則采取嚴(yán)厲的懲罰措施，如永久性封停該賬號(hào)。

3 分布式算法實(shí)現(xiàn)

由于P2P網(wǎng)絡(luò)沒有中心控制節(jié)點(diǎn)，故本文設(shè)計(jì)了一個(gè)不依賴于中心節(jié)點(diǎn)的分布式算法。該算法通過(guò)梯度法更新拉格朗日參數(shù)μ和λ。對(duì)于資源節(jié)點(diǎn)，當(dāng)前分配方案帶寬總和大于 Ws時(shí)增大λ，反之則減小λ；對(duì)于請(qǐng)求節(jié)點(diǎn)，當(dāng)分配到的帶寬小于需求帶寬 wi時(shí)提高競(jìng)價(jià) bi，但需滿足，反之則降低競(jìng)價(jià) bi。該算法指導(dǎo)請(qǐng)求節(jié)點(diǎn)選擇帶來(lái)最大收益的競(jìng)價(jià)，并最終使得分配方案趨于穩(wěn)定。令t表示迭代輪數(shù)， bi(t)表示節(jié)點(diǎn)i在t輪迭代時(shí)給出的競(jìng)價(jià)， μi(t)是節(jié)點(diǎn)i在t輪迭代時(shí)給出的參數(shù)，λ(t)是資源節(jié)點(diǎn)在t輪迭代時(shí)給出的參數(shù)，為資源節(jié)點(diǎn)在t輪迭代時(shí)給出的資源分配方案。下面是基于拍賣的分布式帶寬分配（AB-DBA）算法的具體描述。

1) 初始化參數(shù)。令 t = 0 ，資源節(jié)點(diǎn)初始化參數(shù) λ(0)，各請(qǐng)求節(jié)點(diǎn)初始化參數(shù) μi(0)、ws和競(jìng)價(jià) bi(0)，并將競(jìng)價(jià)提交給資源節(jié)點(diǎn)。

2) 資源分配。資源節(jié)點(diǎn)接收到各個(gè)請(qǐng)求節(jié)點(diǎn)的競(jìng)價(jià) bi(t)后，依據(jù)式（10）調(diào)整帶寬分配方案 X(t)，即

3) 調(diào)整參數(shù)。資源節(jié)點(diǎn)和請(qǐng)求節(jié)點(diǎn)根據(jù)當(dāng)前的帶寬分配方案 X(t)，運(yùn)用梯度下降法調(diào)整參數(shù)λ和μi

4) 調(diào)整競(jìng)價(jià)。請(qǐng)求節(jié)點(diǎn)i依據(jù)當(dāng)前的 X(t)調(diào)整下一輪的競(jìng)價(jià)。若 x(t)= w ，則競(jìng)價(jià)不變；若i sx(t)＜w，則依據(jù)式（21）提高競(jìng)價(jià)；若x(t)＞w，i si s則依據(jù)式（22）降低競(jìng)價(jià)。

該方案正確運(yùn)行時(shí)存在一個(gè)假設(shè)，即所有請(qǐng)求節(jié)點(diǎn)與資源節(jié)點(diǎn)交換信息必須是同步進(jìn)行的，但是可以利用文獻(xiàn)[13]中的方法將其轉(zhuǎn)化為異步方式。由凸優(yōu)化理論可知，當(dāng)目標(biāo)函數(shù)是可微的并且是嚴(yán)格凹時(shí)，上述算法一定是收斂的。上述方案中的迭代步長(zhǎng)依據(jù)文獻(xiàn)[14]選取。

將該算法應(yīng)用于實(shí)際的P2P網(wǎng)絡(luò)中時(shí)，需要在請(qǐng)求節(jié)點(diǎn)與資源結(jié)點(diǎn)之間傳遞的信號(hào)包括拉格朗日乘數(shù)μ、λ、競(jìng)價(jià)向量B和資源分配向量X，其中，λ實(shí)際表示單位帶寬資源的價(jià)格。資源節(jié)點(diǎn)根據(jù)請(qǐng)求節(jié)點(diǎn)的需求調(diào)整該價(jià)格，起到類似市場(chǎng)經(jīng)濟(jì)中的價(jià)格杠桿作用，從而達(dá)到合理分配資源的目的。

4 仿真實(shí)驗(yàn)

4.1 實(shí)驗(yàn)設(shè)置

OMNeT++[15]是基于 C++的離散事件仿真平臺(tái)，它可以用來(lái)仿真通信網(wǎng)絡(luò)、多處理器系統(tǒng)和其他分布式并行系統(tǒng)。本文基于 OMNeT++平臺(tái)上的Swarming內(nèi)容分發(fā)仿真模塊實(shí)現(xiàn)了本文設(shè)計(jì)的P2P內(nèi)容分發(fā)網(wǎng)絡(luò)資源分配算法。

在本文的仿真模型中，只有一個(gè)內(nèi)容源服務(wù)器。為了更接近現(xiàn)實(shí)中接入帶寬的異質(zhì)性，設(shè)置了多類節(jié)點(diǎn)，它們具有不同的接入帶寬，如表1所示。

表1 節(jié)點(diǎn)信息

在仿真模型中，源服務(wù)器的上下載帶寬為10Mbit/s。每個(gè)數(shù)據(jù)塊大小為 256kbit，整個(gè)數(shù)據(jù)文件為100MB。

為了驗(yàn)證本文提出的基于拍賣機(jī)制的P2P網(wǎng)絡(luò)帶寬分配機(jī)制的性能以及AB-DBA算法的收斂性，進(jìn)行了如下2組實(shí)驗(yàn)，第一組為實(shí)驗(yàn)1和實(shí)驗(yàn)2，主要驗(yàn)證AB-DBA算法的收斂性，第二組為實(shí)驗(yàn)3至實(shí)驗(yàn)5，驗(yàn)證AB-DBA算法對(duì)系統(tǒng)性能的影響，其中主要與文獻(xiàn)[5]中的“tit-for-tat”機(jī)制以及隨機(jī)資源分配機(jī)制相比較。實(shí)驗(yàn)數(shù)據(jù)初始化設(shè)置如下，本實(shí)驗(yàn)采用動(dòng)態(tài)迭代步長(zhǎng) Δt=1.0/t，可以達(dá)到前期快速逼近，后期隨著迭代步長(zhǎng)的變小，緩慢逼近，提高精確度。其他參數(shù)初始化值分別為ε=0.01，，即初始出價(jià)為節(jié)點(diǎn)空閑帶寬的20%。

4.2 實(shí)驗(yàn)結(jié)果

實(shí)驗(yàn) 1 節(jié)點(diǎn)給出真實(shí)競(jìng)價(jià)時(shí)的資源分配及收斂情況

在實(shí)驗(yàn)1和實(shí)驗(yàn)2中，選了系統(tǒng)中4類具有代表性的節(jié)點(diǎn)，接入帶寬分別為256kbit/s、512kbit/s、1 024kbit/s、2 048kbit/s，這4類節(jié)點(diǎn)占到整個(gè)系統(tǒng)的90%。由于整個(gè)系統(tǒng)由多個(gè)拍賣組組成，為了簡(jiǎn)單清晰地顯示拍賣的收斂過(guò)程，選取系統(tǒng)中局部的一個(gè)拍賣組，該組由5個(gè)節(jié)點(diǎn)組成，分別為1個(gè)拍賣執(zhí)行者和4個(gè)競(jìng)拍者，拍賣執(zhí)行者的可拍賣帶寬為2 048kbit/s，4個(gè)競(jìng)拍節(jié)點(diǎn)為ND-256、ND-512、ND-1024和ND-2048，空閑帶寬分別為256kbit/s，512kbit/s、1 024kbit/s和 2 048kbit/s。

如圖1和圖2所示，在空閑帶寬不同的情形下，各個(gè)節(jié)點(diǎn)依據(jù)自己的帶寬需求及自己空閑帶寬調(diào)整自己的競(jìng)價(jià)，最終系統(tǒng)達(dá)到平衡。依據(jù)圖1可知，節(jié)點(diǎn)ND-256、ND-512、ND-1024和ND-2048獲得的下載帶寬分別為136kbit/s、273kbit/s、546kbit/s、1 092kbit/s。而此時(shí)它們的競(jìng)價(jià)由圖 2可知分別為121kbit/s、241kbit/s、483kbit/s和 967kbit/s?？梢姼?jìng)價(jià)越高，即愿意提供的上載帶寬越多，獲得的下載帶寬也越多，且兩者成比例，體現(xiàn)了資源分配的公平性。由圖可知，該算法在迭代 18次左右可趨于穩(wěn)定，收斂速度較快。

圖1 節(jié)點(diǎn)資源分配情況

圖2 節(jié)點(diǎn)競(jìng)價(jià)情況

實(shí)驗(yàn)2 存在自私節(jié)點(diǎn)時(shí)資源分配及收斂情況

如圖3所示，自私節(jié)點(diǎn)在前30次迭代時(shí)提供的都是真實(shí)競(jìng)價(jià)。而第 31次迭代開始，節(jié)點(diǎn)ND-1024企圖保留0單位的上載帶寬獲取資源，即不提供服務(wù)給潛在的節(jié)點(diǎn)，此時(shí)該節(jié)點(diǎn)立即遭到本機(jī)制的懲罰，分配到的資源為 0。系統(tǒng)經(jīng)過(guò)若干輪迭代后再次達(dá)到平衡狀態(tài)。由于其他3個(gè)節(jié)點(diǎn)之前并沒有獲取到全部需求的帶寬資源，故當(dāng)一開始分配給節(jié)點(diǎn)ND-1024的資源釋放后，其他節(jié)點(diǎn)分配到的資源自然上升，表明即使有自私節(jié)點(diǎn)存在也不會(huì)影響其他節(jié)點(diǎn)的正常資源分配。這顯示了本機(jī)制能夠有效遏制搭便車現(xiàn)象的發(fā)生，具有使節(jié)點(diǎn)合作的強(qiáng)制性。

圖3 包含自私節(jié)點(diǎn)時(shí)的資源分配情形

實(shí)驗(yàn)3 節(jié)點(diǎn)獲取內(nèi)容平均完成時(shí)間

圖4中，TIT-TAT表示BitTorrent中的資源分配機(jī)制，RND表示隨機(jī)資源分配，AB-DBA表示本文提出的資源分配機(jī)制。從圖中可知，不管哪種機(jī)制，隨著節(jié)點(diǎn)數(shù)的增加，節(jié)點(diǎn)獲取內(nèi)容的平均完成時(shí)間都會(huì)隨之增加。這是由于節(jié)點(diǎn)具有自私性，節(jié)點(diǎn)的帶寬設(shè)置通常是上載帶寬小于下載帶寬，故隨著節(jié)點(diǎn)的增加，上載帶寬供需矛盾越突出。TIT-TAT和RND機(jī)制并沒有處理好該供需矛盾，故隨著節(jié)點(diǎn)的增加，獲取內(nèi)容的平均完成時(shí)間大幅增加。而運(yùn)用 AB-DBA機(jī)制的平均完成時(shí)間與這 2種機(jī)制相比具有明顯優(yōu)勢(shì)，在節(jié)點(diǎn)數(shù)為100時(shí)，分別比TIT-TAT和RND機(jī)制減少40%和55%的時(shí)間，而在節(jié)點(diǎn)數(shù)為500時(shí)，更是減少55%和70%。說(shuō)明該機(jī)制能夠通過(guò)浮動(dòng)的帶寬價(jià)格調(diào)節(jié)系統(tǒng)中上載帶寬的供需關(guān)系，當(dāng)上載帶寬資源緊缺時(shí)，迫使節(jié)點(diǎn)獲取同樣的資源時(shí)需要貢獻(xiàn)更多的上載帶寬，避免“公共地悲劇”發(fā)生。

圖4 不同資源分配機(jī)制中節(jié)點(diǎn)獲取內(nèi)容的平均完成時(shí)間

實(shí)驗(yàn)4 系統(tǒng)中上載帶寬與總帶寬之比

由圖5可知，采用隨機(jī)資源分配時(shí)，系統(tǒng)上載帶寬與總帶寬的比值在0.1附近波動(dòng)，總體呈現(xiàn)上載帶寬極度匱乏的局面，有時(shí)甚至逼近 0，此時(shí)上載帶寬枯竭，即產(chǎn)生“公共地悲劇”，嚴(yán)重影響整個(gè)系統(tǒng)的性能及用戶體驗(yàn)。采用TIT-TAT資源分配策略時(shí)，起初上載帶寬與總帶寬的比值在(0.4,0.6)區(qū)間內(nèi)，說(shuō)明上載帶寬供需處于較為合理水平，但隨著時(shí)間的推移，系統(tǒng)中產(chǎn)生一些特權(quán)節(jié)點(diǎn)，這些節(jié)點(diǎn)具有較高的接入帶寬，可以獲得優(yōu)質(zhì)的服務(wù)，造成接入帶寬較小的節(jié)點(diǎn)失去貢獻(xiàn)資源的動(dòng)力，從而造成整體上載帶寬資源的逐步減少，系統(tǒng)性能下降。而本文提出的AB-DBA資源分配機(jī)制上載帶寬與總帶寬的比值雖然有一定波動(dòng)，但是總體平穩(wěn)，且基本維持在(0.4,0.6)區(qū)間內(nèi)，表明系統(tǒng)中上載帶寬與下載帶寬比達(dá)到一個(gè)較為平衡的狀態(tài)，提升了整體系統(tǒng)的性能，由圖4中的節(jié)點(diǎn)獲取內(nèi)容平均完成時(shí)間可以驗(yàn)證。

圖5 系統(tǒng)上載帶寬占總帶寬比

實(shí)驗(yàn)5 源服務(wù)器上傳數(shù)據(jù)比例

由圖6可知，隨著節(jié)點(diǎn)數(shù)的增加，源服務(wù)器上傳數(shù)據(jù)占總數(shù)據(jù)量的比例趨于穩(wěn)定，即 RND機(jī)制中源服務(wù)器上傳數(shù)據(jù)比在50%以上，TIT-TAT機(jī)制中源服務(wù)器上傳數(shù)據(jù)比在25%左右，而本文提出的AB-DBA機(jī)制中源服務(wù)器上傳數(shù)據(jù)比例在 15%左右，具有一定的優(yōu)勢(shì)。顯然，當(dāng)總的下載數(shù)據(jù)量相對(duì)固定時(shí)，源服務(wù)器上傳數(shù)據(jù)比例越低，則其他節(jié)點(diǎn)貢獻(xiàn)的資源越多，從側(cè)面表明該系統(tǒng)中自私節(jié)點(diǎn)數(shù)量越少，系統(tǒng)的可擴(kuò)展性也越好。這表明AB-DBA機(jī)制能夠遏制節(jié)點(diǎn)的自私性行為，提高系統(tǒng)的可擴(kuò)展性。

圖6 源服務(wù)器數(shù)據(jù)上傳比例

5 結(jié)束語(yǔ)

P2P內(nèi)容分發(fā)網(wǎng)絡(luò)中存在大量自私節(jié)點(diǎn)希望無(wú)償使用網(wǎng)絡(luò)資源，從而造成網(wǎng)絡(luò)資源匱乏且分配不合理，甚至導(dǎo)致“公共地悲劇”的發(fā)生。為了解決上述問(wèn)題，本文利用微觀經(jīng)濟(jì)學(xué)中的拍賣模型對(duì)P2P內(nèi)容分發(fā)網(wǎng)絡(luò)中的帶寬分配問(wèn)題進(jìn)行建模，通過(guò)請(qǐng)求節(jié)點(diǎn)保留部分上載帶寬以獲取資源節(jié)點(diǎn)的下載帶寬的支付方式，構(gòu)建了一種基于拍賣的P2P帶寬分配機(jī)制。仿真結(jié)果表明，該機(jī)制可以有效遏制節(jié)點(diǎn)的自私性行為，避免“公共地悲劇”的發(fā)生，保證了可提供服務(wù)的上載帶寬量，從而縮短P2P內(nèi)容分發(fā)的平均完成時(shí)間，降低內(nèi)容源服務(wù)器的上傳數(shù)據(jù)比例，提升了系統(tǒng)的可擴(kuò)展性。

本文設(shè)計(jì)的基于拍賣模型的P2P網(wǎng)絡(luò)帶寬分配機(jī)制只遏制了需要獲取資源的節(jié)點(diǎn)的自私性行為，并沒有考慮如何激勵(lì)當(dāng)前不在享用系統(tǒng)資源的節(jié)點(diǎn)主動(dòng)貢獻(xiàn)上載帶寬以提高系統(tǒng)的整體性能。作者正在探索該問(wèn)題的解決方案。

[1] ADAR E, HUBERMAN B A. Free Riding on Gnutella[R]. Xerox PARC, 2000.

[2] HARDIN G. The tragedy of the commons[J]. Science, 1968, 162(3859)∶ 1243-1248.

[3] 劉志新,申妍燕,關(guān)新平. 一種基于 VCG 拍賣的分布式網(wǎng)絡(luò)資源分配機(jī)制[J].電子學(xué)報(bào), 2010, 38(8)∶1929-1933.LIU Z X, SHEN Y Y, GUAN X P. A VCG-auction based distributed mechanism for network resource allocation[J]. Acta Electronica Sinica,2010, 38(8)∶1929-1933.

[4] RICHARD T B M, SAM C M L, JOHN C S L. Incentive and service differentiation in P2P networks∶ a game theroretic approcach[J].IEEE/ACM Transactions on Networking, 2006, 14(5)∶ 978-991.

[5] COHEN B. Incentives build robustness in BitTorrent[A]. Workshop on Economics of Peer-to-Peer Systems [C]. Berkeley, CA, USA,2003.

[6] KLEMPERER P. Auction theory∶ a guide to the literature[J]. Journal of Economic Surveys, 1999, 13(3)∶227-286.

[7] KRISHNA V. Auction Theory (2nd ed)[M]. Academic Press, USA,2010.

[8] COURCOUBETIS C, WEBER R. Pricing Communication Network∶Economics, Technology and Modeling[M]. Wiley Online Library, 2003.

[9] YANG S, HAJEK B. VCG-Kelly mechanisms for allocation of divisible goods∶ adapting VCG mechanisms to one-dimensional signals[J].IEEE Journal on Selected Areas in Communications, 2007,25(6)∶1237-1243.

[10] KELLY F P, MAULLOO A K, TAN D. Rate control in communication networks∶ shadow prices, proportional fairness and stability[J]. Journal of the Operational Research Society, 1998, 49(3)∶237-252.

[11] BERTSEKAS D P, NEDIC A, OZDAGLAR A. Convex Analysis and Optimization[M]. Nashua∶ Athena Scientific, 2003.

[12] KABUS P, TERPSTRA W W, CILIA M. Addressing cheating in distributed MMOGS[A]. Proc NetGames[C]. New York, NY, USA, 2005.1-6.

[13] BERTSEKAS D P, TSITSIKLIS J N. Parallel and Distributed Computation[M]. New York∶ Prentice Hall Inc, 1989.

[14] BOYD S, VANDENBERGHE L. Convex Optimization[M]. Cambridge∶ Cambridge University Press, 2004.

[15] OMNeT++ community site[EB/OL]. http∶//www.omnetpp.org, 2012.