基于博弈論的命名數據網絡擁塞控制策略

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

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

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

NDN架構具有興趣包和數據包一對一傳輸的特點，可以通過調節興趣包的發送速率來實現對數據包返回速率的控制[4]。文獻[5-6]通過重傳超時計時器和擁塞窗口調節發送端的興趣包發送速率來調節網絡流量，較好地實現了帶寬利用率，這種控制算法需要在接收端檢測擁塞是否發生，往往具有較大的難度。Bazmi等[7]通過中間路由器周期性檢測擁塞狀態，即如果發生擁塞，則通過在數據包中加入特定字段，顯式反饋給接收端，然后接收端根據反饋的擁塞狀態，相應地增加或減少興趣包的發送速率。Rozhnova等[8]利用中間路由器根據數據流輸出隊列長度調整興趣包的轉發速率，以實現數據包轉發速率的改變。文獻[9-10]采用動態計算興趣流/數據流的公平共享帶寬，調整超過公平速率的數據流的轉發速率，并向下游路由節點發送超速信息，以調整下游路由節點對應興趣包的轉發速率或尋找其他可用接口轉發興趣包。Carofiglio等[11]提出HR-ICP(hop-by-hop and receiver- driven interest control protocol)擁塞控制算法，該算法在路由器中間節點檢測擁塞狀態并反饋給下游節點和接收端，實現更快調整興趣包/數據包的轉發速率。Zhang等[12]提出CHoPCoP(chunk-switched hop pull control protocol)算法，該算法在接收端擁塞控制算法的基礎上增加了基于隊列長度的路由器中間節點擁塞控制算法，考慮數據流之間的公平性，獲得較好的性能。

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

綜上所述，NDN擁塞控制問題的研究聚焦于通過降低興趣包發送速率解決或緩解網絡擁塞，缺乏對各數據流公平性的分析。考慮到NDN中數據傳輸的方式，對于實現資源分配的公平性，基于博弈論的擁塞控制具有可行性，同時也具有較大的挑戰性和研究意義。

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

1 系統模型

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

圖1 系統模型Fig.1 System model

由圖1可知，路由器定價和各個數據流之間的帶寬需求動態交互過程構成了一個單主多從的Stackelberg博弈。

2 博弈算法設計與實現

2.1 Stackelberg博弈模型

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

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

2.2 效用函數

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

2.2.1 路由器效用函數

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

UR(p，q)=ps-cs

(1)

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

p*=argmaxUR(p*，q*)

(2)

式中：q*表示所有數據流的最優帶寬資源需求策略。

2.2.2 數據流效用函數

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

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

(3)

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

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

Pi(p，qi)=pqi

(4)

根據以上分析，定義數據流i的效用函數為

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

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

(5)

2.3 納什均衡解的存在性

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

(6)

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

(7)

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

證明由前面數據流帶寬需求策略和數據流效用函數的定義容易看出，對于任意的i，數據流i的帶寬需求策略{qi}是歐氏空間的有界閉集，且其效用函數USi(p，qi，q-i)在策略空間上是連續的。可得USi(p，qi，q-i)關于qi的一階偏導數為

(8)

二階偏導數為

(9)

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

2.4 納什均衡解的求解

針對各個數據流無法獲得彼此帶寬需求策略的假設，根據進化博弈的最優動態反應，為求解納什均衡解，采用分布迭代法。

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

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

(10)

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

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

(11)

式中：ω>0表示路由器的價格策略調節步長。

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

(12)

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

設定參數初始值后，迭代過程如下：

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

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

(3) 在t+1時刻，如果路由器的收益達到了最大值，則停止迭代，否則，返回步驟(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算法在路由器上運行，并通過添加的速率調整(rate adjust， RA)模塊來調整數據流的轉發速率。RA模塊由隊列緩存和令牌桶算法組成[4]，對不同的數據流經過哈希函數映射進入不同的動態隊列，令牌桶算法根據單主多從式的Stackelberg博弈納什均衡解，將路由器分配給各個數據流的帶寬轉化為對應的轉發速率并存放到令牌桶。在RA模塊中，數據包的處理過程如圖2所示。

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

從數據流緩存隊列中調度的數據包，若其轉發速率未超過路由器根據納什均衡解分配的速率則直接轉發，不改變數據流的轉發速率；若超過則認為對網絡擁塞做出了“貢獻”，需要通過RA模塊調整數據流的轉發速率，對數據流進行整形，同時借助顯式反饋機制通知下游路由器和請求端，以達到減小相應數據流的轉發速率。

2.6 顯式反饋機制

在ndnSIM1.0軟件的數據包中添加調整速率(adjust rate， AR)和擁塞貢獻(congestion contribution， CC)這兩個字段，擴展后的數據包結構如表1所示。

表1 擴展之后的數據包Table 1 Extended packet

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

3 仿真與分析

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

圖3 單瓶頸鏈路拓撲結構Fig.3 The topology of single bottleneck link

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

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

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

圖5 丟包率Fig.5 Packet loss rate

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

4 結 語

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

今后的研究，將加強理論分析，對算法的公平性進行量化評估，同時將進一步考慮更一般的網絡結構，使本算法在保證高效性和公平性的同時兼顧普適性。