基于合作博弈的数据中心骨干网带宽分配策略

孟　飞　兰巨龙　胡宇翔

(国家数字交换系统工程技术研究中心　郑州　450002)(mf472933350@126.com)



基于合作博弈的数据中心骨干网带宽分配策略

孟飞兰巨龙胡宇翔

(国家数字交换系统工程技术研究中心郑州450002)(mf472933350@126.com)

摘要数据中心(data center, DC)之间通过部署流量工程来提高连接各个数据中心骨干网的利用率，虽然效率提升显著，但对不同类型汇聚流的带宽分配的公平性没有考虑.将多个汇聚流对带宽分配的竞争行为建模为一个合作博弈，通过寻求此博弈的纳什谈判解(Nash bargaining solution, NBS)来确定优化的带宽分配策略CGBA(cooperation game based bandwidth allocation)，权衡各汇聚流的最小带宽保证与带宽分配的公平性.在Mininet平台上进行实验仿真并和典型的带宽分配策略对比，结果表明CGBA不但可保证各汇聚流的最小带宽需求，还确保了各类流对带宽资源竞争的公平性.

关键词数据中心；合作博弈理论；纳什谈判解；带宽分配；Mininet

随着云计算技术的迅速发展，数据中心(data center, DC)已成为一种重要的信息通信基础设施，它采用虚拟化技术将海量的计算、存储、网络等物理资源高度整合为一个共享虚拟资源池[1]，实现资源的高效共享.为了提高数据中心服务的性能和可靠性，数据中心通常分布在地理位置相距很远的世界各地，彼此之间通过高速骨干网络互连[2-3].这些骨干网络通常属于同一个在线服务提供商(online service providers， OSPs)，如Google的G-scale[4]，这些网络的建设成本巨大且其中发生数据丢包是不可接受的[5]，因此，高效合理地分配利用数据中心骨干网带宽资源且保证数据流的传输服务质量(quality of service， QoS)十分必要.

目前，对于数据中心骨干网带宽分配的研究已经成为学术界的一个重要研究课题，并取得了大量研究成果.LBAPS[6]，NetStitcher[7]都是通过感知带宽使用状况，前者优先把待传输数据块上传到空闲带宽大的节点，即通过占用空闲带宽来减少传输时延；后者使用存储-转发算法调度数据块，并根据带宽使用状况而实时调整变化.GRESE[8]是1个可以减少峰值带宽消耗的调度算法，在流量高峰时段传输实时或时延敏感数据，而在非流量高峰时期传输非时延敏感流量，通过在不同时段对带宽进行分配，可使带宽的使用代价显著减少.以上3种方案均是通过调度策略对带宽在时间轴上进行的分配，虽可减少数据流传输的带宽开销，但是没有考虑不同类型数据流的带宽需求差异，即没有对不同数据流的差异需求区分对待.Ghosh等人[9]提出了一种数据中心骨干网可扩展多类流管理策略，通过网络分层实现管理可扩展，根据需求的不同为每类流进行带宽分配，定义每类流的效用函数并以整体效用最大化为目标，但是它没有考虑不同流之间带宽分配的公平性.OSPs通常通过部署流量工程合理布局流量来提高数据中心骨干网的链路带宽利用率，例如Google的B4[5]通过使用基于OpenFlow的SDN架构实施流量工程，把应用流分隔部署到多条路径上来均衡流量，链路的平均带宽利用率高达70%，它使用最大最小公平(max-min fairness)[10]算法为各类流分配带宽，提供了较高的公平性.但鉴于最大最小公平算法固有的缺陷，B4对各类流的带宽需求差异性考虑不足，因而使得对带宽需求较大的流的QoS保障受限.在数据中心骨干网链路带宽分配过程中，公平和效率是要综合考虑的2个方面，只有这样才能在保证带宽资源高效利用的同时为各类流提供可预测的传输性能，提供较高水平的QoS保障.

博弈论[11]是应用数学的一个分支，适合于研究具有竞争或对抗性质的各种行为.在带宽分配过程中，不可避免地会存在多个任务对有限带宽资源的竞争，而博弈论又恰好能有效地解决多个自私个体之间的竞争问题，从而达到全局任务效用值最优.合作博弈纳什谈判解(Nash bargaining solution, NBS)已广泛用于解决资源分配中效率和公平的权衡[12].受文献[12-14]启发，本文将数据中心骨干网链路上多类汇聚流对共享带宽的竞争分配问题建模为一个合作博弈，各汇聚流之间竞争带宽并以最大化整体效用为目标，通过设计集中式的带宽分配算法来寻求该博弈问题的纳什谈判解，得到优化的带宽分配策略，并将该策略称为基于合作博弈的带宽分配(cooperation game based bandwidth allocation, CGBA).最后基于Mininet[15]对所设计的模型进行实验仿真验证，并与现有典型策略的实验结果对比以表明其优势.

1基于合作博弈的带宽分配模型

1.1网络模型

Fig. 1　Network architecture.图1　网络架构

如图1所示，本文的网络架构采用2层控制架构，该结构目前已被大多数基于SDN的数据中心网络所普遍采用[4-5,14].网络中有2种类型控制器:多个本地控制器和1个全局控制器，前者对所属单个数据中心(DC)进行管理，不同DC之间相互独立，地位相同；1个集中式全局控制器管理整个网络.数据中心间通过可编程边界网关(programmable border gateways)互连，数据中心内部虚拟机(virtual machine, VM)流量在边界网关汇聚分类，两DC间的通信可简化为分属的两网关间的通信.本文基于博弈理论的思想对数据中心骨干网链路上多个汇聚流的带宽分配问题进行建模分析.带宽资源被多条流共享，在进行带宽分配时除了要使带宽资源整体利用率最大化外还要对各个不同类型数据流提供最小带宽保障及保证分配的公平性，合作博弈的解——纳什谈判解(NBS)可有效权衡公平性和效率的关系，因此基于合作博弈模型分析解决此问题更为合适.

Fig. 2　N flow contend the share bandwidth.图2　N条汇聚流竞争链路带宽资源

定义2. 矩阵F=(fij)N×M表示DC骨干网中各汇聚流的分布，二进制变量fij定义如下：

(1)

1.2博弈建模

(2)

定理1. 存在唯一满足定义3中条件的解，且是下述问题的最优解：

(3)

NBS的存在性与唯一性证明见文献[11].

将目标函数取对数，式(3)等价于：

(4)

由定理1可知，CGBA博弈的NBS是下述全局最优问题的解：

(5)

定理2. 存在αi≥0，βi≥0(i∈{1,2,…,N})和γm≥0(m∈{1,2,…,M})，使得∀i∈{1,2,…,N}，∀m∈{1,2,…,M}有

(6)

(7)

(8)

(9)

证明. 利用拉格朗日乘子方法分析最优化问题式(5)，其拉格朗日函数定义为

(10)

其中,αi，βi，γm为非负的拉格朗日乘子.求关于bi的一阶导数，并根据Karush-Kuhn-Tucker(KKT)[16]条件，则有式(6)～(9)成立.

证毕.

“互补问题”作为一类新的数学模型，是1964年美国Cottle[17]在其博士学位论文中提出的.非线性互补问题(nonlinear complementarity problem， NCP)是研究非线性互补条件的问题，其定义为：映射S:n→n，求向量x∈n，满足x≥0,S(x)≥0,xTS(x)=0，非线性互补问题记为NCP(S)，其中n表示n维欧氏空间，n中的矢量均为列矢量，xTy表示x与y的内积.

NCP函数的定义为：函数φ:2→，对∀x,y∈2，φ(x,y)=0，当且仅当x≥0,y≥0,xTy=0.因为NCP函数可自动保证非线性互补条件的成立，利用某些NCP函数，我们可将互补问题转化为等价的方程组.对于任意一个NCP函数φ(·,·)，非线性互补问题NCP(S)可等价地转化为方程组：

(11)

本文选择Mangasarian[18]提出的NCP函数φ(a,c)=|a-c|3-a3-c3，这个函数关于a，c是光滑的.利用这个NCP函数将不等式约束问题的KKT条件，即式(6)～(9)，转化为等价光滑方程组：

(12)

后续的问题就是如何选择简单适当的算法去求解这个光滑方程组.带一维搜索的Newton法克服了传统Newton法的局部收敛缺点，使此方法具有全局收敛性的同时保持了传统Newton法的简单、收敛快的优点.共轭梯度法(conjugate gradient， CG)[19]是带有特殊性质的共轭方向法，仅需利用一阶导数信息，在产生共轭向量计算新向量时，只要用一个相邻的前面的向量，所需存储和计算量很少.为了不失效率而又保持收敛性，对Newton方程运用CG法迭代，在达到系统的某些非精确近似解时终止迭代，用非精确一维搜索 Newton-CG法来求解大型非线性光滑方程组，算法描述如下:

算法1. 基于Newton-CG算法的带宽分配计算.

输入：初始点z0∈R2N+M、流分布矩阵F=(fij)N×M、带宽需求向量D=(D1,D2,…,DN)、链路带宽容量Cm(m∈{1,2,…,M})、迭代次数k=0、参数ηk和精度ε；

输出：带宽分配计算结果b=(b1,b2,…,bN).

① if ‖F(zk)‖≤ε，结束，else转②；

② 用CG算法解线性方程组

③ 令xk+1=xk+αkpk，其中αk满足

Wolfe或Armijo后退准则等；

④k=k+1，转①.

本算法的计算复杂度主要集中在步骤②③，在使用CG算法求解线性方法组时，终止条件‖rk‖≤ηk‖F(zk)‖使得算法计算量减少，计算复杂度降低；在进行迭代求解时，仅需知道前面一个向量，存储空间可重复利用，算法空间复杂度低.非精确的一维Newton搜索算法简单，全局收敛速度快，计算复杂度低.因此，本算法的计算复杂度和空间复杂度均较低.本算法的实质是用共轭梯度法解Newton方程，具有单步收敛性，高稳定性，关于共轭梯度法的收敛性证明可参见文献[20].

2集中式带宽分配算法

在进行带宽分配时，控制器需要监测底层网络资源使用状况，网络状态信息的获取是由各交换机上报本地控制器，然后再上报全局控制器而得到的.CGBA部署在集中式全局控制器上计算全网的带宽分配结果，其中，算法1计算得到带宽分配结果，算法2控制带宽分配的迭代收敛.得到结果后全局控制器向特定的某条流的源、目的DC本地控制器下发结果，本地控制器再向相关交换机下发配置命令，通过对特定队列的流表的配置实现数据包转发速率控制.

Fig. 3　The simulation topology.图3　仿真拓扑图

算法2. 集中式带宽分配控制.

输出：带宽分配向量b=(b1,b2,…,bN).

① for 所有的流：∀i∈{1,2,…,N}，do

⑤ 在集中式控制器中运行算法 1；

⑥ end while

⑦ end for

由于要保持全网信息的一致性，SDN网络中控制器会周期性地向交换机节点下发询问信息，因此通过在下发询问信息时捎带控制器对节点的带宽配置信息则避免了对节点配置时的一部分额外开销.

本算法的计算复杂度主要在步骤④⑤，算法最多迭代S次，因此其计算复杂度最大为S倍的算法1的计算复杂度，S为定值且算法1复杂度低，则本算法计算复杂度较低.

3CGBA的仿真实验与性能分析

3.1实验场景建立

类比Falloc[12]建立实验仿真验证环境，在基于OpenFlow的Mininet仿真平台上对CGBA进行仿真验证.建立同图1所示架构的网络拓扑，为不失一般性同时为简便分析起见，建立3个相互连通的DC域，即存在3条链路；此网络中共有5条流，则M=3，N=5.如图3所示，3个交换机相互连通，每个交换机连接4个主机对外等价于一个DC域，链路的带宽向量为C=(1 Gbps，2 Gbps，3 Gbps).在进行带宽分配时，要从效率和公平2方面综合比较分配策略的性能，效率主要从对各流的最小带宽的保障考虑，根据对需求的满足程度衡量效率的高低，定义平均带宽分配满足度(satisfaction degree,SD)为

(13)

其中，SD越接近于1，说明对各流的带宽分配满足较好，效率越高；反之则效率越低.对公平性的考量，选用文献[21-22]中的公平指数(fairness index,FI)来进行评价，本文公平指数的定义为

(14)

其中，FI越接近于1, 说明公平性越高; 反之，则说明公平性越低.

在资源饱和场景(所有链路均能满足其上的全部流的带宽需求之和)中，全部流需求都会获得满足，没必要进行带宽博弈，按需分配即可，因此本文重点研究资源匮乏(至少存在一条链路的带宽容量不能满足其上的所有流的带宽需求之和)的情况，并将CGBA和其他策略进行对比.

3.2数值结果与讨论

基带宽的选取是根据每条流的历史需求信息选取的，越接近博弈结果则求解得到最终结果的速度越快，博弈时间越短.不同的流分布对CGBA本身不产生影响，即不会影响CGBA的性能，因此随机取定流分布矩阵

本文把CGBA和按比例带宽分配策略(pro-portionalpolicy，PP)、基于优先级的带宽分配策略(prioritybasedpolicy，PBP)及最大最小公平分配(max-minfairness，MMF)进行比较.这3种策略的描述如下：

3) 最大最小公平分配(MMF).若分布在带宽容量为Ci的链路linki上的流为flow1，flow2，…，flown，其带宽需求从小到大排序为D1，D2，…，Dn，那么，我们初始把Cin带宽分配给flow1，这可能会超过flow1的需求，将超出flow1需求的那部分加上剩余没有分配的带宽平均分给其他流，依次按此方法处理，则bi=(1≤i≤n).该过程结束时，每条流得到的带宽不会比自己要求的多，而且，如果其需求得不到满足，得到的带宽也不会比其他得到最多带宽的流得到的少.

Fig. 4　The results of average satisfaction degree.图4　平均带宽分配满足度

图4、图5表示基带宽为1 Gbps，D3=D5=1 Gbps，D2=D4=D(为仿真分析简便，其他情况仅是变量个数的增加、维度的扩展)时，运用4种策略分别进行带宽分配的所得结果.在带宽资源充足(带宽需求D在0到1 Gbps之间)时，即资源饱和场景中，4种策略结果相同.在带宽资源匮乏场景中，CGBA通过合作博弈对带宽进行最优分配，满足各流的最小带宽需求之后，剩余带宽按照需求差异按比例分配，可以提供一个唯一且公平的帕累托最优点，兼顾了不同的需求和最小性能保证，具有很高的公平性，效率和公平2方面性能均优于其他策略.MMF是一种对低需求用户按需保障、高需求用户“尽力而为”保障的分配策略，因其过于追求流量公平，没有考虑各个流之间的需求差异性，所以当各流的需求差异较大时，对需求大的流的保障则会造成限制，反而造成MMF公平性不是很好；同时因为没有对流需求差异加以区分，导致需求较大的流的带宽分配满足度较低(随需求的增大呈反比例降低)，故整体QoS保障水平受限，效率较低.PP实质上是一种按需求大小加权的分配策略，对不同需求用户机械地“一视同仁”对待，仅根据需求的占比决定分配的大小，因此平均带宽分配满足度和公平指数均较低.PBP仅考虑各类流的优先级的不同，对高优先级的流按需满足，而对优先级低的流可能会造成带宽分配“饿死”现象，平均带宽分配满足度和分配公平性在4种策略中最低.

Fig. 5　The results of fairness index.图5　公平指数

Fig. 6　Comparison of convergence speed.图6　收敛速度比较

按照“天下没有免费的午餐(no free lunch, NFL)”[23]理论，一种算法不可能在任何方面或在任何问题上都能够提供比其他所有算法更好的性能.在我们的实验结果中也观察到了这点.如图6所示，考察在给定基带宽为1 Gbps，flow2和flow4的带宽需求分别为1.5 Gbps，2.5 Gbps，3.5 Gbps时3种策略的迭代收敛情况.图6表明：选取的基带宽合适与否影响迭代的周期，即带宽分配博弈的时间，越接近最优值则所需寻优迭代次数越少，收敛越快；CGBA的收敛速度比MFF快，较PP和PBP慢,并将4种策略分别进行50次实验，每种策略达到博弈稳定所需的平均计算时间如图7所示:

Fig. 7　Comparison of computational complexity.图7　不同策略计算复杂度比较

从图7可以看出，CGBA的计算复杂度要明显高于PP和PBP，但是却低于MFF.这表明，CGBA具有较高带宽分配满足度和较高公平性是以牺牲一定计算复杂度为代价的，并进一步验证了文献[23]中NFL理论的正确性.

4结束语

本文深入研究了数据中心骨干网络中的带宽分配问题，将各条流对共享带宽的竞争分配问题建模为一个合作博弈模型，并通过寻求该博弈模型的Nash谈判解NBS得到优化的带宽分配策略CGBA.将CGBA与3种典型的带宽分配策略进行了详尽的实验对比.实验结论表明，CGBA在各种网络场景中都能较好地提高带宽分配的满足度，为每条流提供最小带宽保障，效率较高；同时可保证较高的带宽分配公平性.本文提出的带宽分配策略为设计性能更佳的数据中心骨干网络带宽分配系统提供了借鉴和理论支持.

参考文献

[1]Bari M F, Boutaba R, Esteves R, et al. Data center network virtualization: A survey[J]. IEEE Communications Surveys & Tutorials, 2013, 15(2): 909-928

[2]Mahimkar A, Chiu A, Doverspike R, et al. Bandwidth on demand for inter-data center communication[C] //Proc of the 10th ACM Workshop on Hot Topics in Networks. New York: ACM, 2011: 24:1-24: 6

[3]Greenberg A, Hamilton J, Maltz D A, et al. The cost of a cloud: Research problems in data center networks[J]. ACM SIGCOMM Computer Communication Review, 2008, 39(1): 68-73

[4]Google. Inter-datacenter WAN with centralized TE using SDN and OpenFlow[EB/OL]. 2012[2014-12-22]. https://www.opennetworking.org/images/stories/downloads/misc/googlesdn.pdf

[5]Jain S, Kumar A, Mandal S, et al. B4: Experience with a globally-deployed software defined WAN[C] //Proc of the ACM SIGCOMM 2013. New York: ACM, 2013: 3-14

[6]Huang Yongfeng, Dong Yongqiang, Zhang Sanfeng, et al. Leftover bandwidth-aware peer selection algorithm for inter-datacenter content distribution[J]. Journal on Communications, 2013, 34(7): 24-33 (in Chinese)(黄永锋, 董永强, 张三峰, 等. 数据中心间空闲带宽感知的内容分发算法[J]. 通信学报, 2013, 34(7): 24-33)

[7]Laoutaris N, Sirivianos M, Yang X, et al. Inter-datacenter bulk transfers with NetStitcher[J]. ACM SIGCOMM Computer Communication Review, 2011, 41(4): 74-85

[8]Thyaga N, Krishna P N P. Lowering inter-datacenter bandwidth costs via bulk data scheduling[C] //Proc of the 12th IEEE/ACM Int Symp on Cluster, Cloud and Grid Computing. New York: ACM, 2012: 244-251

[9]Ghosh A, Ha S, Crabbe E, et al. Scalable multi-class traffic management in data center backbone networks[J]. IEEE Journal on Selected Areas in Communications, 2013, 31(12): 2673-2684

[10]Danna E, Hassidim A, Kaplan H, et al. Upward max min fairness[C] //Proc of the IEEE Int Conf on Computer Communications (INFOCOM 2012). Piscataway, NJ: IEEE, 2012: 837-845

[11]Osborne M J, Rubinste A. A Course in Game Theory[M]. Cambridge, MA: MIT Press, 1994: 12-30

[12]Guo Jian, Liu Fangming, Tang Haowen, et al. Falloc: Fair network bandwidth allocation in IaaS datacenters via a bargaining game approach[C] //Proc of the 21st IEEE Int Conf on Network Protocols (ICNP). Piscataway, NJ: IEEE, 2013: 1-10

[13]Vitaly A, Ruslan S. Global network modelling based on mininet approach[C] //Proc of the 2nd ACM SIGCOMM Workshop on Hot Topics in Software Defined Networking. New York: ACM, 2013: 145-146

[14]Liu Zhongjin, Li Yong, Su Li, et al. M2cloud: Software defined multi-site data center network control framework for multi-tenant[J]. ACM SIGCOMM Computer Communication Review, 2013, 43(4): 517-518

[15]Lantz B, Heller B, McKeown N. A network in a laptop: Rapid prototyping for software-defined networks[C] //Proc of the 9th ACM SIGCOMM Workshop on Hot Topics in Networks. New York: ACM, 2010: 19:1-19:6

[16]Yaïche H, Mazumdar R, Rosenberg C. A game theoretic framework for bandwidth allocation and pricing in broadband networks[J].IEEE/ACM Trans on Networking, 2000, 8(5): 667-678

[17]Cottle R W. Nonlinear programs with positively bounded jacobians[J]. SIAM Journal on Applied Mathematics, 1964, 14(1): 147-158

[18]Mangasarian O L. Equivalence of the complementarity problem to a system of nonlinear equations[J]. SIAM Journal on Applied Mathematics, 1976, 31(1): 89-92

[19]Hager W W, Zhang Hongchao. A survey of nonlinear conjugate gradient methods[J]. Pacific Journal of Optimization, 2006, 2(1): 35-58

[20]Chen Yu. The convergence research on conjugate gradient method[D]. Jingzhou, Hubei: Yangtze University, 2012 (in Chinese)(陈禹. 共轭梯度法的收敛性研究[D]. 湖北荆州: 长江大学, 2012)

[21]Jain R, Chiu D M, Hawe W. A quantitative measure of fairness and discrimination for resource allocation in shared computer system，TR-301[R]. Saint Louis, Missouri: Washington University, 1984

[22]Chiu D M, Jain R. Analysis of the increase and decrease algorithms for congestion avoidance in computer networks[J]. Computer Networks and ISDN Systems, 1989, 17(1): 1-14

[23]Wolpert D H，Macready W G. No free lunch theorems for optimization[J]. IEEE Trans on Evolutionary Computation, 1997, 1(1): 67-82

Meng Fei, born in 1989. Master candidate. His main research interests include new network architecture, QoS.

Lan Julong, born in 1962. Professor and PhD supervisor. His main research interests include new network architecture, information security, and computer network.

Hu Yuxiang, born in 1982. Lecturer. His main research interests include new network architecture, information security.

A Cooperative Game Based Data Center Backbone Network Bandwidth Allocation Policy

Meng Fei, Lan Julong, and Hu Yuxiang

(NationalDigitalSwitchingSystemEngineering&TechnologicalR&DCenter,Zhengzhou450002)

AbstractCurrently, traffic engineering is typically deployed to improve the utilization of data centers (DC) backbone networks, which usually belongs to the same online service providers. Although the efficiency is remarkable, the bandwidth allocation fairness of different aggregate flow isn’t considered. Hence, the QoS guarantee is restricted. Because the bandwidth resource is expensive and packet loss is typically thought unacceptable, the bandwidth utilization should be maximized, at the same time, the QoS guarantee of different flow should be improved. In this paper, the problem of contending the share bandwidth is modeled as a cooperative game, and different aggregate flow compets the share bandwidth and maximizes the overall bandwidth resource utilization simultaneously, and the optimal bandwidth allocation policy, called cooperation game based bandwidth allocation (CGBA), is obtained through searching the Nash bargaining solution (NBS) of the game and balancing the tradeoff between minimum bandwidth guarantee and bandwidth allocation fairness. Simulation on a Mininet testbed shows that the proposed policy can effectively guarantee minimum bandwidth of each aggregate flow while ensuring the allocation fairness, compared with three other classical bandwidth allocation policies.

Key wordsdata centers (DC); cooperative game theory; Nash bargaining solution (NBS); bandwidth allocation; Mininet

收稿日期：2014-12-23；修回日期：2015-03-19

基金项目：国家“九七三”重点基础研究发展计划基金项目(2012CB315901，2013CB329104)；国家自然科学基金项目(61372121)；国家“八六三”高技术研究发展计划基金项目(2013AA013505)

中图法分类号TP391

This work was supported by the National Basic Research Program of China (973 Program) (2012CB315901,2013CB329104), the National Natural Science Foundation of China (61372121), and the National High Technology Research and Development Program of China (863 Program) (2013AA013505).