基于谈判博弈的分布式协同网络服务布局算法框架

程国振，陈梓桓，张靖羽

（1.国家数字交换系统工程技术研究中心，郑州 450002;2.长沙市长郡中学，长沙410000）

当前，互联网承载着大量服务，并被部署于整个网络中。由于巨大的服务规模以及高动态的互联网负载，分布式的组织和优化服务提供以实现网络效用最大化是一个难点。一方面，数据中心网络（Data Center Network,DCN）、软件定义网络（Software Defined Network,SDN）等新型网络的应用降低了管理大量服务的难度。另一方面，DCN中虚拟化的应用，SDN对网络功能的重新抽象和细粒度分解，又极大地增加了网络服务实体的数量，其组成成分更加复杂。因此，分布式网络服务放置问题[1-2]不论对当前网络还是未来网络都是一个挑战。

网络服务在不同研究领域的含义不同。例如在云计算网络中，网络服务模型分为设备即服务（Infrastructure as a Service）、平台即服务（Platform as a Service）和软件即服务（software as a Service）[3]；在内容中心网络（Content-Centric Network,CCN）[4]中，网络服务为提供视频、文件等内容。本文中提到的网络服务（Network Service,NS）泛指细小网络功能单元或细粒度的网络资源。

服务布局对于优化服务提供，降低网络资源消耗具有现实意义。一个典型例子是云服务提供商。一般地，大型云服务提供商的用户遍布全球。为了实现用户请求就近“消化”的目的，它可能在不同地区建立多个分布式服务群（service farms）。由于服务群的存储容量有限，一般的策略是服务群存储其所在区域被最频繁访问的服务。理想情况下，提供商期望预先载入（布局）本地用户请求的服务，若本地的服务请求由本区域的服务实例响应，用户将避免访问远程服务实例，降低用户通信开销和时延，提高网络效用。因此，如何在服务群中合理布局租户的应用是节省云资源，提高云服务中心容量的关键。

然而，网络服务在整个网络中的最优布局面临以下三个难点。首先，网络服务的类型具有多样性，网络服务总体规模较大。例如，以视频分发服务为核心的P2P网络，其视频内容多样，相同内容的视频资源根据LRU（Least recently used）、LFU（Least frequently used）以及LRFU等缓存策略将其拷贝布局于网络中，以降低用户的访问代价。其次，分布式网络一般分域管理，且不同区域的资源分布情况不同，因此跨区域布局更加困难。最后，网络用户对服务的请求具有动态特性，使得布局难以跟随用户需求动态变化。

综上，网络服务布局通常需要网络全局知识，为此，本文提出了一种基于讨价还价理论（Bargain theory）的分布式协同网络服务布局算法，通过网络节点的分布式协同，获取网络全局知识，以实现服务布局。讨价还价理论是协同博弈论的分支，通过市场上分布式的讨价活动，实现消息最大化的经济理论。该理论可用于指导网络服务布局。本文将不同类型的网络服务看作博弈的参与者（player），博弈的商品（commodity）则是网络节点资源。在网络容量约束和用户请求分布已知的情况下，参与者不断地出价“购买”商品，以布局其服务实例（网络功能实例）。本文的主要贡献如下：

①将分布式布局问题建模为讨价还价的经济活动，并从理论上证明最优布局解的存在，且为纳什谈判解（Nash Bargain Solution,NBS）。

②以梯度映射方法（Gradient Project Algorithm,GPA）为核，设计算法求解上述问题。首先通过松弛服务布局量为非负实数，得到原始问题的对偶分解形式，利用GPA求解计算其NBS解，然后对得到的NBS采用特定策略整数化。

③通过仿真验证了算法的有效性。

1 相关工作

布局问题是一个NP-难问题，其求解算法已经被广泛地研究。下面按应用领域不同展开讨论。

随着数据中心网络的发展，大量研究人员为提高数据中心网络运营效率展开广泛研究。其中，虚拟机的合理布局可以有效降低数据中心资源代价而成为研究热点。Feng等[5]提出了基于讨价还价理论的虚拟机（Virtual Machine,VM）布局方法，但其将VM建模成同质实体，没有考虑实际中VMs之间差异化的特征，本文算法同时考虑不同类型的网络服务的布局问题。Guo等[6]从影子路由（shadow router）的角度提出一种动态的VM布局算法。Rochman等[7]在分布式网络拓扑下的网络布局建模为最小费用流问题。

在内容分发网络和Web缓冲中，高效的内容副本布局问题被广泛研究[8-9]。这些研究把内容副本（网络服务）布局在地理位置不同的节点，提高性能和访问的可达性。这一领域的研究主要集中在给定用户的请求模式和最优化服务器响应请求的成功比例，而对服务器的容量无约束（一般假设服务器具有无限容量），本文的研究则建立在网络节点有限容量的情况下进行。

另一些研究人员聚焦于P2P网络的视频服务代价问题上。Tewari等[10]研究P2P网络的副本布局问题，提出了比例复制（proportional replication），即基于平均需求，最小化下载过程中的链路数。相似的研究工作如参考文献[11]。文献[12]则是基于随机分配策略最小化访问失败率。这些工作假设文件数量和对等体（peers）的数量足够大，使得所有请求均被满足。基于混合整数规划，文献[13]提出了一种描述大规模VoD的布局框架。Tan等[14]基于渐进性分析建立了一种比例复制的网络性能损失模型。而文献[15]假设电影数量小于对等体数量的情况下，提出了一种优化布局副本算法。这些研究主要用于小规模扁平网络中，并未考虑层次化、跨区域情况。

2 模型建立

2.1 网络服务布局问题

将研究的网络抽象为一个无向图模型G=(N,E)，N={v1,v2,…,vN}为节点集合，E为链路集合。该抽象网络模型中的节点可能是仅对应一个物理节点，也可能是一个网络，如在SDN网络中，单控制器控制的局域网络；或者承载于数据中心网络中的一个独立虚拟网（virtual network,VN），亦或者是P2P网络中的一个对等区域（peering area）等。每个节点可布局M类型的服务。设不同类型服务的请求数为随机变量，其分布为，i=1,2,…,M，k=1,2,…,N.N集合中元素存在局部约束，即网络节点vk布局容量为zk。那么，服务布局问题可表述为：已知服务请求分布D，在可行域内，从布局策略集合中选择最优策略，使得网络期望的效用R最大化，其中，i=1,2,…,M，k=1,2,…,N。假设网络中的所有节点掌握其他节点在时刻t的服务承载能力以及处理的服务请求分布等全局知识。那么，基于中心的效用函数最大化问题可表示为

2.2 讨价还价模型

设有M类型的网络服务为谈判博弈参与者，博弈的商品则是网络中的节点。布局一类服务一般需要达到一定规模才能产生效益，因此出于布局成本、效益以及规模效应的考虑，每类服务i网络节点的布局需要保证一个基本量，记为Bi。保证一个基本量的另一个解释是在布局过程中不同类型的请求分布可能出现不均衡现象，即某些服务类型的请求量大，而某些服务的请求量小，为了避免布局过程中过于偏向“受欢迎”服务，而“饿死”“不受欢迎”服务的情况，所以每类服务在网络中的布局数量规定一种最小值，称为基本布局量。

定理1网络中服务布局的最优问题等价于Nash谈判博弈中的联合利益最大化问题。

3 分布式协同布局算法

3.1 对偶分解

由于问题( )Pl的复杂度受服务类型和网络规模的影响，因此，本文从其拉格朗日对偶问题的角度出发求解以消除影响。问题( )Pl可转化为如下等价形式

原始问题分解为N个不同的更加简单的问题，可实现并行计算，提高运算效率。

3.2 基于梯度影射的分布式协同算法

由问题(P l)到其对偶(D r)均是在松弛假设U⊂RN×M条件下推导得到，由GPA算法得到的结果为。但是实际中的nik∈N，因此需要对松弛后的结果进行调整。对于的近似，直观的思路有两种策略：a)直接取，即为小于的整数；b)取，即，大于的整数。策略a可以在节点资源约束下，成功完成部署，但是可能出现用户部分请求得不到响应；策略b虽然能够成功满足当前用户的所有请求，但是可能会因为被布局网络节点资源受限，导致布局策略失效。基于服务本地和远端的效用比，综合两种策略，即，在网络节点资源允许的情况下，尽量在本地满足效用比较大的需求。

4 性能评估

4.1 仿真环境

本文采用GT-ITM工具[22]产生三种200个节点的随机图模拟相同节点规模的网络拓扑，平均图连接度d分别为20，10和5。

假设网络拓扑中所有节点均为同质化节点，具有相同的可支配资源，即，在节点空载情况下，对于任意类型的服务，每个节点可以承载相同数量的该类型服务实例。由于不同服务类型占用资源情况的多样性，每个节点对于不同类型的服务实例的承载数量具有差异性。为了量化这种差异性，本文给出“节点承载量”的概念，且实验中节点承载量服从500～10 000的均匀分布。

定义1节点承载量服务类型i的实例在独占网络节点 j情况下可布局的最大数量，称为服务类型i在节点 j的承载量，记为cij。由于本实验假设网络节点是同质的，因此服务类型i的节点承载量可简记为ci。

为了考察不同规模服务类型情况下算法的性能，实验分别设置服务类型数量不同的三组实验，服务类型数量M分别取10,100,1000。

根据文献[6]对视频网络的用户请求分析，用户对不同视频的请求服从不同参数的正态分布。因此，不同类型的服务在网络节点上的请求分布采用正态分布模拟。一般地，不同类型的服务在用户中受欢迎程度不同，为此，本实验定义“流行度”（Popularity）的概念进行描述。资源消耗型服务代价较高，其在用户中的流行性也会降低。因此，流行度定义为0～1之间的常数，某类型的服务越受欢迎，流行度越高。因此，服务类型i的流行度p(i)计算为

用户请求的正态分布参数可基于流行度设置。流行度越高的服务类型，其请求数越大。因此，设定流行度为用户对不同类型服务的请求分布的均值，方差为常数1，产生的服从正态分布的请求数单位为万次每秒，记为w/s。

4.2 仿真结果

本文的目标是通过合理布局服务，最大化节点资源效用，满足更多用户需求。基于前一节给出的实验环境，本节主要考察三种拓扑下请求响应率、节点资源效率以及不同基本布局量对算法的影响。在对请求响应率和节点效用比的实验中，算法框架的基本布局量门限为1 000，网络中节点的初始布局量服从500～10 000的均匀分布。

首先给出度量用户请求是否被成功响应的量——节点的请求响应率。请求响应率反映了本文算法的布局对用户体验的影响。请求响应率高表明用户体验良好，未出现服务等级承诺违约情况，反之，请求响应率低表明用户体验差，可能出现服务等级承诺违约。

定义2请求响应率（hit ratio of requests）节点i的请求响应率s(i)为节点i实际成功响应的请求数h(i)与节点当前总的请求数r(i)比，即

图1给出了不同拓扑下不同规模服务类型下的请求响应率变化。规模大的服务类型情况下比规模小的情况下的请求响应率高，例如，M=1 000的情况下较M=100和M=10的情况下的请求响应率高。因为在博弈过程中服务类型数量较大时，参与博弈的个体的数量较大，博弈过程也比较充分。由图 1（a）、（b）和（c）可以看出，不同网络拓扑下，其请求响应率不同。d=20和d=10两种情况下，s(i)差异较小，而d=5时，请求响应率下降较大。因为d=5的情况下，链路数量减小，出现资源瓶颈，即使网络节点可以容纳足够的服务实例，但链路资源大幅减少，导致资源不均衡现象，出现性能严重下降。但是在资源充足的情况下，可以看出算法得出的服务布局结果能够迅速使得请求响应率达到95%以上。由图可知，在不同拓扑下初始请求响应率相同或相近。原因是博弈起始阶段，各网络节点的初始布局量相同，等于基本布局量。

图1 请求响应率

4.3 算法比较

最后，本文将基于讨价还价模型的GPA布局算法与经典的LRU、LFU和LRFU布局策略在布局效果上作出比较。设仿真的网络拓扑节点数为200，连接度为d=10，网络中服务类型为100，本节比较不同布局策略下的请求响应率和节点效用比。由图2可以看出，GPA策略优于其他三种布局策略，因为GPA基于讨价还价模型，引入基本布局量，保证了请求响应率。

图2 布局策略比较

5 总结

本文将网络服务布局问题建模为纳什谈判博弈，并设计了一种基于讨价还价理论（bargain theory）的分布式网络服务布局算法框架，通过网络各节点的协同，实现网络全局知识的获得，以实现精准布局。算法框架通过调节基本布局量实现了用户体验与网络效用之间的均衡，仿真结果表明本算法框架的有效性。