基于博弈论的命名数据网络拥塞控制策略

杨 华， 孙欣伊， 贾宗星， 舒慧生

(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算法。该算法每个数据流由路由器给出一个最优转发速率，并通过缓冲队列和令牌桶实现此速率；该算法还提出了一种显式反馈机制，利用数据包将算法给出的该数据包最优发送速率和拥塞信息反馈给上游路由器和请求端。仿真结果表明，该算法可以提高链路利用率，降低丢包率以及缩短数据流平均完成时间，从而提高网络性能。

今后的研究，将加强理论分析，对算法的公平性进行量化评估，同时将进一步考虑更一般的网络结构，使本算法在保证高效性和公平性的同时兼顾普适性。