基于博弈論的命名數(shù)據(jù)網(wǎng)絡(luò)擁塞控制策略

楊 華， 孫欣伊， 賈宗星， 舒慧生

(1.山西農(nóng)業(yè)大學(xué) 信息科學(xué)與工程學(xué)院，山西 太谷 030801; 2.東華大學(xué) 理學(xué)院，上海 201620)

隨著網(wǎng)絡(luò)技術(shù)的快速發(fā)展及網(wǎng)絡(luò)應(yīng)用范圍的大規(guī)模推廣，TCP/IP網(wǎng)絡(luò)體系結(jié)構(gòu)暴露出諸多不足之處，例如IP地址不夠多，安全性、移動性和擴(kuò)展性差[1]。網(wǎng)絡(luò)用戶真正關(guān)心的是數(shù)據(jù)本身，而非數(shù)據(jù)的存放地址，于是出現(xiàn)了信息中心網(wǎng)絡(luò)，其中，最有代表性的是命名數(shù)據(jù)網(wǎng)絡(luò)(named data networking， NDN)。NDN支持多路徑轉(zhuǎn)發(fā)，這可能會使網(wǎng)絡(luò)轉(zhuǎn)發(fā)大量冗余信息，導(dǎo)致網(wǎng)絡(luò)擁塞。如何解決網(wǎng)絡(luò)擁塞控制是NDN架構(gòu)中的一個關(guān)鍵問題，引起了大量科研工作者的關(guān)注[2-3]。

NDN架構(gòu)具有興趣包和數(shù)據(jù)包一對一傳輸?shù)奶攸c(diǎn)，可以通過調(diào)節(jié)興趣包的發(fā)送速率來實(shí)現(xiàn)對數(shù)據(jù)包返回速率的控制[4]。文獻(xiàn)[5-6]通過重傳超時計(jì)時器和擁塞窗口調(diào)節(jié)發(fā)送端的興趣包發(fā)送速率來調(diào)節(jié)網(wǎng)絡(luò)流量，較好地實(shí)現(xiàn)了帶寬利用率，這種控制算法需要在接收端檢測擁塞是否發(fā)生，往往具有較大的難度。Bazmi等[7]通過中間路由器周期性檢測擁塞狀態(tài)，即如果發(fā)生擁塞，則通過在數(shù)據(jù)包中加入特定字段，顯式反饋給接收端，然后接收端根據(jù)反饋的擁塞狀態(tài)，相應(yīng)地增加或減少興趣包的發(fā)送速率。Rozhnova等[8]利用中間路由器根據(jù)數(shù)據(jù)流輸出隊(duì)列長度調(diào)整興趣包的轉(zhuǎn)發(fā)速率，以實(shí)現(xiàn)數(shù)據(jù)包轉(zhuǎn)發(fā)速率的改變。文獻(xiàn)[9-10]采用動態(tài)計(jì)算興趣流/數(shù)據(jù)流的公平共享帶寬，調(diào)整超過公平速率的數(shù)據(jù)流的轉(zhuǎn)發(fā)速率，并向下游路由節(jié)點(diǎn)發(fā)送超速信息，以調(diào)整下游路由節(jié)點(diǎn)對應(yīng)興趣包的轉(zhuǎn)發(fā)速率或?qū)ふ移渌捎媒涌谵D(zhuǎn)發(fā)興趣包。Carofiglio等[11]提出HR-ICP(hop-by-hop and receiver- driven interest control protocol)擁塞控制算法，該算法在路由器中間節(jié)點(diǎn)檢測擁塞狀態(tài)并反饋給下游節(jié)點(diǎn)和接收端，實(shí)現(xiàn)更快調(diào)整興趣包/數(shù)據(jù)包的轉(zhuǎn)發(fā)速率。Zhang等[12]提出CHoPCoP(chunk-switched hop pull control protocol)算法，該算法在接收端擁塞控制算法的基礎(chǔ)上增加了基于隊(duì)列長度的路由器中間節(jié)點(diǎn)擁塞控制算法，考慮數(shù)據(jù)流之間的公平性，獲得較好的性能。

為實(shí)現(xiàn)資源分配的公平性，部分學(xué)者把博弈論應(yīng)用于擁塞控制。王汝言等[13]通過將視頻報務(wù)提供商從網(wǎng)絡(luò)運(yùn)營商處購買的存儲空間的緩存模型建模為多主多從的Stackelberg博弈問題，獲得了視頻報務(wù)提供商的最優(yōu)緩存策略和網(wǎng)絡(luò)運(yùn)營商的最優(yōu)價格策略。王磊等[14]提出一種基于Stackelberg博弈的多任務(wù)資源分配策略，將無線傳感網(wǎng)絡(luò)定義為領(lǐng)導(dǎo)者，把承載不同業(yè)務(wù)的多個虛擬傳感器網(wǎng)絡(luò)定義為跟隨者，利用分布式迭代方法，獲得無線傳感網(wǎng)絡(luò)的最優(yōu)價格策略和虛擬傳感器網(wǎng)絡(luò)的最優(yōu)資源需求量。

綜上所述，NDN擁塞控制問題的研究聚焦于通過降低興趣包發(fā)送速率解決或緩解網(wǎng)絡(luò)擁塞，缺乏對各數(shù)據(jù)流公平性的分析?？紤]到NDN中數(shù)據(jù)傳輸?shù)姆绞?，對于?shí)現(xiàn)資源分配的公平性，基于博弈論的擁塞控制具有可行性，同時也具有較大的挑戰(zhàn)性和研究意義。

本文提出一種博弈擁塞控制(congestion control based on game theory， CCGT)算法。通過將路由器定義為領(lǐng)導(dǎo)者，將數(shù)據(jù)流定義為跟隨者，構(gòu)建帶寬分配者(路由器)和帶寬需求者(數(shù)據(jù)流)之間的單主多從Stackelberg博弈模型。

1 系統(tǒng)模型

考慮系統(tǒng)模型如圖1所示的場景，假設(shè)路由器中有n個數(shù)據(jù)流，不同的數(shù)據(jù)流對應(yīng)不同的業(yè)務(wù)，有不同的帶寬需求，各個數(shù)據(jù)流之間存在競爭關(guān)系，假定各個數(shù)據(jù)流無法獲得彼此的帶寬需求，由路由器給每個數(shù)據(jù)流分配帶寬，可分配的帶寬上限為瓶頸鏈路帶寬sa。路由器制定單位帶寬的價格來最大化自身的收益，數(shù)據(jù)流根據(jù)路由器制定的價格策略來決定帶寬購買量，以滿足用戶的需求，從而最大化自身利益。

圖1 系統(tǒng)模型Fig.1 System model

由圖1可知，路由器定價和各個數(shù)據(jù)流之間的帶寬需求動態(tài)交互過程構(gòu)成了一個單主多從的Stackelberg博弈。

2 博弈算法設(shè)計(jì)與實(shí)現(xiàn)

2.1 Stackelberg博弈模型

圖1所示的模型有一個路由器和多個數(shù)據(jù)流兩類對象，把路由器定義為領(lǐng)導(dǎo)者，把n個數(shù)據(jù)流定義為跟隨者。領(lǐng)導(dǎo)者制定帶寬價格并對所擁有的帶寬進(jìn)行分配，跟隨者可根據(jù)領(lǐng)導(dǎo)者給出的價格結(jié)合自身的利益確定自己的帶寬需求量。

領(lǐng)導(dǎo)者根據(jù)剩余帶寬給出定價策略，其具體的帶寬分配與管理過程由CCGT算法執(zhí)行。跟隨者可根據(jù)領(lǐng)導(dǎo)者給出的價格調(diào)整帶寬需求量。領(lǐng)導(dǎo)者和跟隨者之間的單主多從式Stackelberg博弈分兩個階段完成。在第1階段，領(lǐng)導(dǎo)者制定單位帶寬價格策略p，同時將該價格策略通知所有跟隨者。跟隨者收到單位帶寬價格后，結(jié)合自身的效用函數(shù)，確定帶寬需求策略q=(q1，q2， …，qn)。由于每個跟隨者不能獲知其他跟隨者的帶寬需求策略，則如何確定跟隨者之間的帶寬需求q是一個非合作博弈問題，納什均衡是該問題的解。在第2階段，領(lǐng)導(dǎo)者為獲得更高的收益，根據(jù)跟隨者反饋的帶寬需求策略q，重新調(diào)整自己的單位帶寬定價策略。

2.2 效用函數(shù)

效用函數(shù)用來直觀描述路由器和數(shù)據(jù)流在博弈過程中獲得的利益或滿意程度。

2.2.1 路由器效用函數(shù)

路由器的效用函數(shù)等于其銷售總額與成本之差，其中銷售總額來自于各個數(shù)據(jù)流購買帶寬向其支付的費(fèi)用。路由器效用函數(shù)定義為

UR(p，q)=ps-cs

(1)

路由器如果定價過高則會導(dǎo)致各個數(shù)據(jù)流對帶寬的需求量減少，這將致使路由器的收益降低。相反，路由器如果定價過低，則將使各個數(shù)據(jù)流對帶寬的需求增大，此時，即使路由器出售全部帶寬資源，也將不會獲得更大的收益。因此，在博弈過程中，路由器希望制定合理的價格，以保證最大化自身的收益。路由器的最優(yōu)價格策略p*滿足式(2)。

p*=argmaxUR(p*，q*)

(2)

式中：q*表示所有數(shù)據(jù)流的最優(yōu)帶寬資源需求策略。

2.2.2 數(shù)據(jù)流效用函數(shù)

在路由器給定單位帶寬價格策略p的情況下，所有數(shù)據(jù)流彼此競爭決定自身的帶寬需求策略。數(shù)據(jù)流的效用函數(shù)由其收益和開銷兩部分組成，其效用函數(shù)定義為收益減去開銷。

數(shù)據(jù)流的收益來自為用戶所提供的服務(wù)，對于數(shù)據(jù)流i，其收益函數(shù)[13]定義為

(3)

式中：ai=1+1/(1+exp(-qi/hi))，hi為數(shù)據(jù)流i所對應(yīng)的服務(wù)能滿足用戶需求的閾值。

假定數(shù)據(jù)流從路由器請求帶寬資源需要支付相應(yīng)的費(fèi)用，數(shù)據(jù)流的開銷與路由器給定單位帶寬價格策略p和數(shù)據(jù)流的帶寬需求量成正比。對于數(shù)據(jù)流i，其開銷函數(shù)定義為

Pi(p，qi)=pqi

(4)

根據(jù)以上分析，定義數(shù)據(jù)流i的效用函數(shù)為

USi(p，qi，q-i)=Gi(qi)-Pi(p，qi)=

式中：q-i=(q1，q2， …，qi-1，qi+1， …，qn)表示除數(shù)據(jù)流i外其他數(shù)據(jù)流帶寬需求量。

(5)

2.3 納什均衡解的存在性

路由器給定單位帶寬價格策略后，各個數(shù)據(jù)流之間存在非合作博弈，當(dāng)路由器和每個數(shù)據(jù)流的利益達(dá)到最優(yōu)時，路由器不能通過變更其單位帶寬價格策略獲得更大的收益，每個數(shù)據(jù)流也不能通過單方面改變自己的帶寬需求策略增加收益，可表示為

(6)

UR(p*，q*)≥UR(p，q*)

(7)

此時稱單主多從Stackelberg博弈達(dá)到納什均衡。下面的定理給出了納什均衡解的存在性。

證明由前面數(shù)據(jù)流帶寬需求策略和數(shù)據(jù)流效用函數(shù)的定義容易看出，對于任意的i，數(shù)據(jù)流i的帶寬需求策略{qi}是歐氏空間的有界閉集，且其效用函數(shù)USi(p，qi，q-i)在策略空間上是連續(xù)的?？傻肬Si(p，qi，q-i)關(guān)于qi的一階偏導(dǎo)數(shù)為

(8)

二階偏導(dǎo)數(shù)為

(9)

由此可知，數(shù)據(jù)流i效用函數(shù)USi(p，qi，q-i)的二階偏導(dǎo)數(shù)為負(fù)，這說明其效用函數(shù)為嚴(yán)格凹函數(shù)，從而數(shù)據(jù)流i存在納什均衡解[13]。

2.4 納什均衡解的求解

針對各個數(shù)據(jù)流無法獲得彼此帶寬需求策略的假設(shè)，根據(jù)進(jìn)化博弈的最優(yōu)動態(tài)反應(yīng)，為求解納什均衡解，采用分布迭代法。

假定在時刻t路由器向數(shù)據(jù)流發(fā)布其制定的單位帶寬價格策略p(t)，各個數(shù)據(jù)流在收到路由器報價后，結(jié)合自身情況調(diào)整帶寬需求量，使其自身利益最大化。假定數(shù)據(jù)流帶寬需求量迭代周期為Δτ，則數(shù)據(jù)流的帶寬需求策略迭代方程可表示為

qi(t+Δτ)=qi(t)+θiΔqi

(10)

式中：θi表示數(shù)據(jù)流帶寬需求策略調(diào)節(jié)步長；Δqi表示數(shù)據(jù)流i帶寬需求變化率，其同自身效用函數(shù)的梯度成正比，即

假定路由器價格策略迭代周期為Δt，且滿足Δt為Δτ的正整數(shù)倍。路由器根據(jù)數(shù)據(jù)流達(dá)到納什均衡時反饋的帶寬需求策略調(diào)節(jié)自已的價格策略，其價格迭代公式為

(11)

式中：ω>0表示路由器的價格策略調(diào)節(jié)步長。

路由器效用函數(shù)關(guān)于價格的偏導(dǎo)數(shù)可以通過一個很小的價格變化量ε(ε=10-5)來計(jì)算，其計(jì)算公式為

(12)

對于整個博弈過程而言，迭代的結(jié)果是路由器和數(shù)據(jù)流各自取得最優(yōu)的價格策略p*和帶寬需求策略q*，由于數(shù)據(jù)流和路由器都達(dá)到了利益最大化，對于單主多從Stackelberg博弈而言，取得了納什均衡(p*，q*)。

設(shè)定參數(shù)初始值后，迭代過程如下：

(1) 路由器帶寬價格策略調(diào)整。在時刻t，路由器根據(jù)式(11)和式(12)調(diào)整自己的單位帶寬價格，并將價格策略向各個數(shù)據(jù)流公布。

(2) 數(shù)據(jù)流帶寬需求策略調(diào)整。數(shù)據(jù)流收到路由器新的帶寬價格策略后，在每個迭代周期Δτ內(nèi)，根據(jù)式(9)和式(10)調(diào)整其帶寬需求策略，直到所有數(shù)據(jù)流的收益達(dá)到最大值。

(3) 在t+1時刻，如果路由器的收益達(dá)到了最大值，則停止迭代，否則，返回步驟(1)。

迭代算法偽代碼描述如下：

Initializet=0;p(0);qi(0);ε；

while (the termination conditions are not met) do

Router adjusts price strategyp(t+1) according to (11) and (12);

for (i=0 ton) do

during each epoch Δτ，data streamiadjusts its bandwidth demand strategy by equations (10);

i=i+1;

end for

end while

if (|p(t+1)-p(t)|≤ε) then

break;

else

t=t+1;

end if

end while

2.5 CCGT算法

CCGT算法在路由器上運(yùn)行，并通過添加的速率調(diào)整(rate adjust， RA)模塊來調(diào)整數(shù)據(jù)流的轉(zhuǎn)發(fā)速率。RA模塊由隊(duì)列緩存和令牌桶算法組成[4]，對不同的數(shù)據(jù)流經(jīng)過哈希函數(shù)映射進(jìn)入不同的動態(tài)隊(duì)列，令牌桶算法根據(jù)單主多從式的Stackelberg博弈納什均衡解，將路由器分配給各個數(shù)據(jù)流的帶寬轉(zhuǎn)化為對應(yīng)的轉(zhuǎn)發(fā)速率并存放到令牌桶。在RA模塊中，數(shù)據(jù)包的處理過程如圖2所示。

圖2 數(shù)據(jù)包在RA模塊中的處理過程Fig.2 Processing of packets in RA module

從數(shù)據(jù)流緩存隊(duì)列中調(diào)度的數(shù)據(jù)包，若其轉(zhuǎn)發(fā)速率未超過路由器根據(jù)納什均衡解分配的速率則直接轉(zhuǎn)發(fā)，不改變數(shù)據(jù)流的轉(zhuǎn)發(fā)速率；若超過則認(rèn)為對網(wǎng)絡(luò)擁塞做出了“貢獻(xiàn)”，需要通過RA模塊調(diào)整數(shù)據(jù)流的轉(zhuǎn)發(fā)速率，對數(shù)據(jù)流進(jìn)行整形，同時借助顯式反饋機(jī)制通知下游路由器和請求端，以達(dá)到減小相應(yīng)數(shù)據(jù)流的轉(zhuǎn)發(fā)速率。

2.6 顯式反饋機(jī)制

在ndnSIM1.0軟件的數(shù)據(jù)包中添加調(diào)整速率(adjust rate， AR)和擁塞貢獻(xiàn)(congestion contribution， CC)這兩個字段，擴(kuò)展后的數(shù)據(jù)包結(jié)構(gòu)如表1所示。

表1 擴(kuò)展之后的數(shù)據(jù)包Table 1 Extended packet

表1底部兩行虛線部分是因試驗(yàn)需要添加的字段，其中，AR字段封裝的是由CCGT算法給出的相應(yīng)數(shù)據(jù)包的發(fā)送速率，CC字段存放的是數(shù)據(jù)包對擁塞作出貢獻(xiàn)的次數(shù)。AR初始化為數(shù)據(jù)包所對應(yīng)的興趣包發(fā)送速率，擁塞貢獻(xiàn)CC置零。當(dāng)數(shù)據(jù)包經(jīng)過路由器時，若數(shù)據(jù)包的轉(zhuǎn)發(fā)速率未超過CCGT算法給定的速率則不改變AR字段的值；若超過則將AR字段的值更新為CCGT算法計(jì)算得到的轉(zhuǎn)發(fā)速率，并認(rèn)為該數(shù)據(jù)包對此路由器的擁塞做出了“貢獻(xiàn)”，將CC字段的值加1。同時，把封裝AR和生存時間TTL=2的擁塞通知NACK發(fā)送給該數(shù)據(jù)包進(jìn)入的接口。上游路由器若收到NACK，則提取AR字段的值作為新的該數(shù)據(jù)包轉(zhuǎn)發(fā)速率。另外，當(dāng)請求端收到數(shù)據(jù)包后，檢查數(shù)據(jù)包中的擁塞貢獻(xiàn)值，若大于零，則取出AR字段的值，并把這個值作為興趣包新的發(fā)送速率。

3 仿真與分析

試驗(yàn)設(shè)置的單瓶頸鏈路拓?fù)浣Y(jié)構(gòu)如圖3所示，其中，C1～C20為20個消費(fèi)者，興趣包的發(fā)送速率為2 000個/s，鏈路傳播時延設(shè)為10 ms，假定包緩沖區(qū)大小為帶寬和延遲的乘積。采用LRU(least recently used)為緩存放置和替換策略[4]，選取BestRoute轉(zhuǎn)發(fā)策略。為驗(yàn)證CCGT算法的有效性，將該算法與文獻(xiàn)[5， 11]中的ICP(interest control protocol)和HR-ICP (hop-by-bop and receiver-driven interest control protocal)算法進(jìn)行對比試驗(yàn)，考慮瓶頸帶寬從30 Mibit/s增加到80 Mibit/s時3種擁塞控制算法的瓶頸鏈路利用率和丟包率的仿真結(jié)果見圖4和圖5。

圖3 單瓶頸鏈路拓?fù)浣Y(jié)構(gòu)Fig.3 The topology of single bottleneck link

圖4 瓶頸鏈路利用率Fig.4 Utilization of bottleneck link

圖4給出了ICP、 HR-ICP和CCGT這3種算法的瓶頸鏈路利用率隨瓶頸鏈路帶寬變化的趨勢曲線。由圖4可以看出，基于CCGT算法的網(wǎng)絡(luò)瓶頸鏈路利用率隨著瓶頸帶寬的增加而增加，這是由于CCGT根據(jù)納什均衡點(diǎn)給各數(shù)據(jù)流分配最優(yōu)帶寬和采用顯式反饋機(jī)制，使得該算法能夠根據(jù)網(wǎng)絡(luò)瓶頸鏈路帶寬增加更好地利用帶寬。隨著瓶頸帶寬的增加，ICP算法對瓶頸鏈路的利用率從84%下降到77%，這是由于該算法采用擁塞窗口對興趣包進(jìn)行轉(zhuǎn)發(fā)，興趣包增多會使隊(duì)列長度快速增加，導(dǎo)致瓶頸鏈路利用率降低。相對于ICP算法，HR-ICP算法增加了中間路由器判斷是否擁塞的功能，這使得該算法比ICP算法能更好地適應(yīng)瓶頸鏈路帶寬變化及提高帶寬利用率；相比CCGT算法將數(shù)據(jù)包最優(yōu)速率直接反饋給上游路由器和發(fā)送端，HR-ICP算法只通過發(fā)送端的擁塞窗口機(jī)制來調(diào)節(jié)興趣包的發(fā)送速率，該算法還不能有效地利用帶寬。

路由器給各數(shù)據(jù)流分配帶寬的主要目標(biāo)就是在充分利用可用帶寬的同時對不同數(shù)據(jù)流分配的帶寬維持一定的公平性。在本文中，公平性是指在滿足約束的條件下，路由器根據(jù)Stackelberg博弈納什均衡解得到數(shù)據(jù)流的最優(yōu)帶寬需求量給數(shù)據(jù)流分配網(wǎng)絡(luò)帶寬。為實(shí)現(xiàn)公平性，路由器根據(jù)數(shù)據(jù)流所分配的網(wǎng)絡(luò)帶寬調(diào)整該數(shù)據(jù)流的轉(zhuǎn)發(fā)速率，且兩者呈正比例關(guān)系。本文運(yùn)用分布式迭代方法直接求得納升均衡解，故沒有考慮基于網(wǎng)絡(luò)資源利用率滿足特定條件下的線性和非線性激勵策略。

圖5 丟包率Fig.5 Packet loss rate

由圖5可知，采用CCGT時丟包率隨著瓶頸鏈路帶寬的增加而快速減少，這是因?yàn)镃CGT算法可以給各個數(shù)據(jù)流分配最優(yōu)帶寬，并把此最優(yōu)帶寬反饋給上游路由器和發(fā)送端，從而提前防止擁塞的發(fā)生及平滑網(wǎng)絡(luò)流量，減少丟包的發(fā)生。ICP算法在數(shù)據(jù)包傳送超時后才認(rèn)為網(wǎng)絡(luò)發(fā)生擁塞，這會延遲對擁塞的處理，從而導(dǎo)致較高的丟包率。HR-ICP算法的性能介于CCGT算法和ICP算法之間，該算法相比CCGT算法沒有考慮數(shù)據(jù)流帶寬的最優(yōu)分配，相比ICP算法可以更快發(fā)現(xiàn)擁塞。

4 結(jié) 語

將單主多從式Stackelberg博弈引入NDN并提出了CCGT算法。該算法每個數(shù)據(jù)流由路由器給出一個最優(yōu)轉(zhuǎn)發(fā)速率，并通過緩沖隊(duì)列和令牌桶實(shí)現(xiàn)此速率；該算法還提出了一種顯式反饋機(jī)制，利用數(shù)據(jù)包將算法給出的該數(shù)據(jù)包最優(yōu)發(fā)送速率和擁塞信息反饋給上游路由器和請求端。仿真結(jié)果表明，該算法可以提高鏈路利用率，降低丟包率以及縮短數(shù)據(jù)流平均完成時間，從而提高網(wǎng)絡(luò)性能。

今后的研究，將加強(qiáng)理論分析，對算法的公平性進(jìn)行量化評估，同時將進(jìn)一步考慮更一般的網(wǎng)絡(luò)結(jié)構(gòu)，使本算法在保證高效性和公平性的同時兼顧普適性。