一种SDN中用户群博弈的OpenFlow流调度策略

2016-12-01林晓勇朱园园梅杰糜正琨

电信科学 2016年8期

关键词：用户群交换机链路

林晓勇，朱园园，梅杰，糜正琨

（1.南京邮电大学通信与信息工程学院，江苏南京 210003；2.北京邮电大学信息与通信工程学院，北京 100876）

一种SDN中用户群博弈的OpenFlow流调度策略

林晓勇1，朱园园1，梅杰2，糜正琨1

（1.南京邮电大学通信与信息工程学院，江苏南京 210003；2.北京邮电大学信息与通信工程学院，北京 100876）

提出了一种基于用户中心网络的软件定义网络框架，建立了一种基于用户群博弈策略的OpenFlow流调度模型，提取用户群属性及用户最佳体验参数，从用户层面跨层至控制层进行调度，对比了非合作博弈调度与合作博弈调度。仿真结果显示，合作博弈调度的用户群整体满意度最佳，有助于通信运营商实现“用户为王”的理念。

用户中心网络；软件定义网络；用户群博弈；合作博弈；满意度

1 引言

4G／5G 时代，软件定义网络（software defined networking，SDN）、网络功能虚拟化（network function virtualization，NFV）和云计算（cloud computing，CC）技术使网络与底层物理基础设施分开，变成更抽象、灵活的，以软件为中心的构架，可以通过编程调度来提供更佳的业务连接。互联网+、移动应用技术、挖掘用户行为特征的社交网络的发展，演变为以用户最佳体验（user best experience，UBE）为中心的用户中心网络（user centric networking，UCN）。UCN 用户可以基于某种激励机制来交互和获取信息，与传统SDN相比，UCN能识别用户的身份、喜好、认证等信息，实现由用户而非仅设备驱动的流调度机制［1-3］。

2 相关研究工作

时代飞速发展，传统的资源共享型互联网转变为用户服务型网络。封闭的运营商管道体系与以用户为中心的客观需求产生了不对称性，如何在运营商“管道”上体现用户“自定义服务”的特色，是SDN技术的起源。2008年，美国斯坦福大学Mckeown N教授的研究团队［1］首次提出了OpenFlow的概念，之后进一步阐述SDN的概念［2］，受到了学术界和产业界的广泛支持。

SDN与传统网络的最大不同在于控制平面（control plane，CP）与数据平面（data plane，DP）相分离，并将 CP 挪到交换机／路由器之外的应用中，通过安全套接层（secure sockets layer，SSL）通道连接应用与网络设备。开放网络基金会（Open Network Foundation，ONF）正式发布一个名为OpenFlow协议的开放式信令标准（OpenFlow protocol，OFP），用于控制器和交换机之间的信令交互［3］。OpenFlow作为SDN的标准协议，通过流表进行消息传递，每张流表都由多个流表项组成，每个流表项对应网络中传输的一条流，因此能合理高效地进行流调度，并为用户提供无缝服务。CP中核心的控制器（controller）拥有全局网络状态并管控整个网络，代表所有交换机做决定。DP仍然在交换机中，但不能独立做决定，每当控制器做一个决定，它会给相应交换机发送消息来修改其流表，所有交换机只是根据它们流表中的指令来转发数据分组。

可编程SDN的自适应结构可以很好地满足定制业务（ordered service，OS）的需求，恰恰符合运营商以用户为中心的需求，因此控制器控制并刷新网络状态，提高网络资源利用率和降低运营成本，通过监控底层网络流量来提供自我配置，通过区分、独立的流量种类可以获得更好的用户体验。

当前用户数据全IP化，IPv4报文中的服务类型（type of service，ToS）占1 byte，将数据流简化为8个优先级，RFC2474重新定义ToS为差分业务控制点（differentiated services code point，DSCP），至 64 级别，仍然只从数据流属性角度衡量网络服务质量（quality of service，QoS），未达到UCN以用户为中心的体验质量（quality of experience，QoE）的要求，因此本文的创新点为跨层获取用户属性参数，从而重新优化资源调度。

传统的资源分配方法是以各种最优化结果为目标，使端系统被动地得到资源［4］，用户在竞争有限网络资源的过程中，参与者恶性的竞争行为会使资源调度问题变得更为复杂，需要参与竞争的主体是“理性的”，因此借鉴经济学中估量用户“付费服务”的有效工具——博弈论来研究上述问题。在博弈论模型中，每个主体的收益不仅取决于它自身的行为属性，也取决于其他人的行为属性，理论界的博弈论算法以递归计算求最优值为主，迭代运算量大且耗时长，不符合路由器算法执行的有效性。本文以博弈论为基础，设计出适合硬件执行的分布式博弈论算法来实现最优化、相对公平的资源调度。

3 基于UCN的改进SDN转发机制

基于UCN的改进SDN架构如图1所示。基础设施层为网络的底层转发设备，主要由OpenFlow交换机组成；控制层集中维护网络状态及保证QoS，并通过南向接口（如OpenFlow）获取底层基础设施信息，同时为应用层提供可扩展的北向接口，用于应用程序检测网络状态、下发控制策略［5］；UCN层可以是多媒体视频网站（视频流大客户），也可以是社交网络应用，或者是运营商分类业务用户，包含各自的QoE指标。

UCN层用来提取用户及用户群的各种属性参数，然后映射到UGG（user group gaming，用户群博弈）调度策略中，从而实现以用户群为中心的跨层调度。图2给出了在OpenFlow1.4版本下，多OFP媒体流进入组入口（group entry）［6，7］，采用 UGG 策略的 SDN 调度机制。OFP 消息的结构如图3所示，其中，0x16H在使用0x0F异或解析处理时，可以适配成标准的OpenFlow1.5协议［8］；也可在检测到0x16H时调用UGG策略，同时在OFP净荷的IP报文的头部option字段提取用户博弈因子（user gaming index，UGI）和用户期望带宽（user expected bandwidth，UEB）参数，执行UGG策略，OFP交换机的流表结构保持不变［9］。

图1 改进的SDN架构

图2 简化的兼容UGG策略机制

图3 改进的OFP消息结构

4 基于UGG的OpenFlow调度模型

已注册UGG策略服务的用户才会启用博弈机制，未注册用户执行兼容的OpenFlow机制。UGG分布式部署在控制器中，会略微增加控制器的负荷，在OpenFlow1.5里引入数据分组类型识别流程和入口表（egress table）后，可以下发到OpenFlow交换机，从而增强了UGG模型的合理性。

4.1 UGG调度策略建模

首先对用户的所有属性进行模糊聚类划分，将同类用户归为一个用户群，这个网络被用户群集合S={1，…，S}共享，每个用户群业务流速率为xs，s∈S，其动态范围IS=［ms，Ms］，s∈S，其中，ms＞0，Ms＜+∞。

一个网络包含单向的链路集合为：L={1，…，L}，每条链路的容量为 cl，l∈L。

L（s），（1≤s≤S）∩（L（s）⊆L）表示用户群 S 的业务流路径的集合，S（l）表示路由路径经过链路l的用户群集合，可以用矩阵A来表示所属关系：

所以流的容量约束可定义为：AX≤C，其中，X=（x1，x2，…，xs）表示流速率向量，C=（c1，c2，…，cL）表示链路容量矢量。

用户群的利益（效用）都由效用函数 Uβ（xs）表示，其中，β表示效用函数的类型。Uβ（xs）的数学表达式为：

Uβ（xs）的公平性由参数 β决定［10］，当 β→0 时，带宽资源分配结果接近系统最优均值（system optimal fairness）；当β→1 时，接近均衡平均值（proportional fairness）；当 β→2时，接近谐波均值（harmonic fairness）；当 β→+∞ 时，接近最大最小均值（max-min fairness）。由此可见，可以通过更改β的值来达到系统所需的“公平”。

引入用户群博弈因子，该因子可以在生成用户数据时打入IP报文的头部标签，通过对用户参数的调研发现基于用户行为的资源分配算法［11］，主要研究用户群体的行为特征对资源分配的影响，从而统计信息，寻找规律动态分配资源，UGG策略模型只需能有效地区分不同用户群的UGI参数以及用户的内容划分等级，对数据流的等级划分可依据其对时延和分组丢失率等的要求做出评判。

对系统满意度的定义如下：每个用户有其期望的带宽（UEB）和实际得到的带宽（AB），定义用户的期望满意度（expected satisfaction degree，ESD）为 ESD=AB／UEB×100%，另外，对每个用户群定义一个系统满意度（system satisfaction degree，SSD），考察在一段时间内每个用户群对带宽分配的满意度，在某一段时间内随机取N个点，当用户的实际带宽超过最低满意带宽（minimum bandwidth，MIB）就认为达到满意，则有SSD=AB＞MIB的次数×100%。这样可以通过对比合作与非合作博弈论下SSD的高低来分析不同策略的优劣。

4.2 用户群排队模型

单用户访问网络符合泊松分布，独立用户访问为离散独立不相关事件，因此虽然不同用户属性的数学期望与方差不同，群变量的叠加符合线性组合关系，因此用户群排队模型符合设置用户的概率分布，以最大限度地接近真实用户群的上网特性。可以设置用户群的上线人数服从泊松（Poisson）分布（到达率为λ），且每类用户群的泊松分布参数不同；用户群的在线（在线视频业务）时长服从指数分布，数学期望为T。

4.3 用户群的NCG调度策略建模

4.3.1 NCG调度策略

非合作博弈（non-cooperative gaming，NCG）研究人们在利益相关中如何使自己的收益最大［12］。相应在网络中，每个自私的参与者都力图使自己所占的带宽达到最大，所谓“自私即私自”，采用ToS模式的IP网络即以高优先级数据流牺牲低优先级数据流，类似于最残酷的非合作博弈竞争。

非合作博弈论提供了一种类似市场机制的机制，参与者并不知道其他竞争者的具体消息，这使参与者之间的合作变得不可能。参考文献［13］证明了纳什均衡点在经典费用函数条件下的唯一性、存在性以及最优性。

非合作即竞争，因此比最大最小公平资源调度方法和成比例公平资源调度方法更容易造成恶性竞争，NCG思想是博弈论不可或缺的一部分，因此本文选择NCG调度策略作为对比。

4.3.2 NCG模型的建立

定义x-i，1≤i≤S是除了第i个用户群之外的所有用户群生成的向量。定义任意一用户群i的业务流流量上限为 ni（x-i），并且有：

定义有关用户群i的费用函数Ji。Ji可以看成由价格函数 Pi和效用函数 Uβ（xi）两项构成，Pi是通过价格来反映网络的真实状态，可以理解为用户使用网络所需付的费用：当网络拥塞时，所需付的费用高；当网络空闲时，所需付的费用低。综上所述，可以定义费用函数Ji等于价格函数 Pi与效用函数 Uβ（xi）之差，即：

纳什均衡点就是这个博弈对于每个参与者的最优解，从数学角度来讲，在所有参与者达到均衡点时，用户群i的费用最低，目标函数为：

4.4 用户群的CG调度策略建模

4.4.1 用户群CG策略思想

CG（cooperative gaming，合作博弈）是以最大化整个系统效用（利益）为最终目标［14］，CG采用了纳什议价框架，核心思想［15］为：每个用户群都会预定所需的最低带宽，然后根据总效用函数最大化这个目标来进行调度。在CG模式下，首先要保证每个用户群最基本的带宽要求，然后适当地减少高等级用户不必要的资源分配，这样虽然损害了一方的些许利益，但系统满意度（即运营商层面的服务满意度指标）会提高。UCG策略就是要找到一种基于用户群的最佳体验，同时，即使运营商的交换机端“自主”调整业务流的流量，网络资源逼近最佳带宽分配点，也可以完成用户群流调度的目标。

4.4.2 CG模型的建立

由于合作博弈论的核心思想是使系统利益（效用函数）之和达到最大，可以表述为：对式（6）的极值问题进行拉格朗日变换，得到：

其中，pl是链路l的使用价格。所以转化为给定链路价格的条件下满足最大用户收益的对偶问题：

其中，ps是用户群s单位流量的价格，所以xsps可以看作用户群s在流量为xs状态下的总费用，并且 Bs（ps）可以看成用户群s在给定价格ps下能获得的最大效益。对于每个用户，通过价格ps来引导解决最大值问题。对于任意的价格，当Uβ（xs）是严格凹函数时，用户群s存在一个独立的流量最大值解。

从对偶理论上讲，只要找到问题D的最优解p*，对应的最佳带宽解x*即可求出。最重要的一点是，每个网络中的用户群s在已知p*的情况下，独自求出自身的最佳带宽xs*，这一过程并不需要用户之间的同步，易于实现。

5 仿真过程与结果

5.1 网络构造

设置仿真网络场景如图4所示：共有13条链路、8个节点，代表OpenFlow交换机，共同隶属于一个控制器，默认所有8个交换机都被同一自治域（autonomous system，AS）的控制器调度，OpenFlow交换机与控制器的消息交互符合OpenFlow协议规范，链路容量为1 000 Mbit／s，共 10条光纤链路，这10条链路相当于骨干链路，其余链路的容量均为100 Mbit／s（代表电接口），网络里面的每条链路都有接近实际情况的背景流，仿真计算时，左侧的入口边缘路由发送OFP消息数据流给右侧边缘路由器的出口端，数据流可以根据网络状态走不同的链路，步长为2 000个周期。

图4 复杂网络的拓扑结构

5.2 用户参数的设定

根据某运营商服务器上的数据分析，设置3个等级A、B、C，具体参数见表 1。

表1 3类用户的具体参数

对接近3类用户的数目按 1：2：3的比例设置，结果见表 2。

表2 3类用户人数的设置

5.3 链路背景流的设定

为了贴近实际网络，考察了实际交换机一个端口一天内的流量图，并进行了数学拟合，得到：

其中，N为周期，Am为正弦函数振幅，range为所取符合背景流的正弦函数幅度，random为生成的随机函数，CI为链路容量。生成的背景流量如图5所示，与实际端口流量走势图相比，具有极高的一致性。

图5 仿真生成的链路背景流量

5.4 UCG策略实施机制

在交换机入口的OFP分组检测到兼容UGG的0x16字节，入口首先完成差错检测和安全检验、分类或解多路复用、流量管理和控制等常规功能，然后提取该OPF分组携带的UGI和UEB参数，UEB采用速率模板形式映射等值带宽，交换机如执行UGG策略，则向控制器发出OFPT_packet_in消息，控制器使用OFPT_features_request消息确认交换机并读取其UGG请求参数，在单个执行周期内，对所有当前UGG请求执行NCG或CG算法，为每个目标用户生成资源分配参数，生成的附加参数值插入OFP消息的填充（padding）字段，通过 OFPT_set_config消息发送给对应的交换机，交换机不再进行OFPT_features_reply响应确认，而是直接执行新参数对应的逻辑链路中的下一跳OFP交换机完成数据分组转发。

5.5 UGG仿真结果

非合作博弈仿真计算结果见表3，合作博弈仿真计算结果见表4。

仿真结果用每类用户群的平均带宽来表示带宽分配情况。图6给出了数量最多的C类用户的任一时刻的平均带宽，可以看出即使在网络背景流最大的情况下，链路也保持了较好的运行状态。

表3 非合作博弈UGG中3类用户带宽分配情况

表4 合作博弈UGG中3类用户带宽分配

图6 合作博弈UGG策略下C用户群带宽分配

通过基于CG的UG策略和NCG的对比可以看出，每个用户群在合作博弈论的框架下被分配到更多的带宽。

5.6 性能对比分析

综合表3和表4可以看出，用户采用CG的UGG策略时，各用户群可以获取比NCG框架下更大的平均带宽，具体结果如图7所示。

图7 两种算法在分配带宽上的对比

而在系统满意度这个指标上，NCG框架下A类用户满意度优于CG框架下的A类用户，原因是CG框架更注重公平，它略微减少了A类用户的高带宽分配次数，从而满足其他用户群的要求，在基本不影响A类用户满意度的情况下使得所有用户的满意度得到提高，而NCG则忽略了这一点，从图8可以看出，除了A类用户的满意度略有下降，但B、C类用户的系统满意度有较大增长。由此可见，采用CG框架的UGG调度策略在兼顾公平的基础上能很好地分配资源，使所有用户群都较为满意。

图8 两种算法在系统满意度上的对比

6 结束语

本文提出了一种在UCN思想下的SDN体系结构，给出一种新的OpenFlow流调度机制，从用户群的角度出发，提出了用户群博弈UGG的OpenFlow流调度策略，UGG的核心是采用合作博弈CG模型，在仿真中通过CG和NCG的对比，对UGG策略进行了效用评估，得到了预期的效果。本文侧重结合用户群的优先级和用户满意度体验进行合作博弈资源调度，提出了一种有助于运营商实现“以用户为中心”理念的网络路由的新思路。

［1］MCKEOWN N，ANDERSON T，BALAKRISHNAN H.OpenFlow：enabling innovation in campus networks ［J］.ACM SIGCOMM Computer Communication Review，2008，38（2）：69-74.

［2］Open Networking Foundation.Software-defined networking：the new norm for networks［EB／OL］.（2012-04-13）［2013-06-30］.https：／／www.opennetworking.org／images／stories／downloads／sdn-resources／white-papers／wp-sdn-newnorm.pdf.

［3］Open Networking Foundation.OpenFlow switch specification 1.0.0［EB／OL］.（2009-12-31）［2012-07-25］.https：／／www.opennetworking.org／images／stories／downloads／sdn-resources／onf-specifications／OpenFlow／OpenFlow-spec-v1.0.0.pdf.

［4］陶军，吴清亮，吴强.基于非合作竞价博弈的网络资源分配算法的应用研究［J］.电子学报，2006，34（2）：241-246.TAO J，WU Q L，WU Q.Application research of network resource allocation algorithm based on non-cooperative bidding game［J］.Acta Electronica Sinica，2006，34（2）：241-246.

［5］左青云，陈鸣，赵广松，等.基于 OpenFlow的 SDN技术研究［J］.软件学报，2013（5）：1078-1097.ZUOQY，CHENM，ZHAOGS，etal.Researchon OpenFlow-based SDN technologies［J］.Journal of Software，2013（5）：1078-1097.

［6］BAIK S，LIM Y，KIM J.Adaptive flow monitoring in SDN architecture ［C］／／17th Asia-PacificNetwork Operationsand Management Symposium （APNOMS），Aug 19-21，2015，Busan，Korea.New Jersey：IEEE Press，2015：468-470.

［7］梁昊驰.SDN可扩展路由及流表资源优化研究［D］.合肥：中国科学技术大学，2015.LIANG H C.Research on scalable routing and flow table resource optimization in software defined networks ［D］.Hefei：University of Science and Technology of China，2015.

［8］孔祥欣.软件定义网络分布式控制平台的研究与实现［D］.北京：清华大学，2013.KONG X X.Research and implementation of distributed control plane of software-defined networking ［D］.Beijing：Tsinghua University，2013.

［9］Open Networking Foundation.OpenFlow switch specification 1.5.1 ［EB／OL］. （2009-12-31）［2015-06-16］. https：／／www.opennetworking.org／images／stories／downloads／sdn-resources／onfspecifications／OpenFlow／OpenFlow-switch-v1.5.1.pdf.

［10］FANG Z Y，BENSAOU B.Fair bandwidth sharing algorithms based on game theory frameworks for wireless ad-hoc networks［C］／／23th Annual Joint Conference of the IEEE Computer and Communications Societies，March 7-11，2004，Tel Aviv，Israel.New Jersey：IEEE Press，2004：1284-1295.

［11］周景才，张沪寅，查文亮，等.云计算环境下基于用户行为特征的资源分配策略［J］.计算机研究与发展，2014，51（5）：1108-1119.ZHOU J C，ZHANG H Y，ZHA W L，et al.User-aware resource provision policy for cloud computing ［J］.Journal of Computer Research and Development，2014，51（5）：1108-1119.

［12］ORDA A，ROM R，SHIMKIN N.Competitiveroutingin multiuser communication networks ［J］.IEEE／ACM Transactions on Networking，1993，1（5）：510-521.

［13］ALPCAN T，BASAR T.A game-theoreticframework for congestion control in general topology networks ［C］／／41st IEEE Conference on Decision and Control，Dec 10-13，2002，Las Vegas，NV，USA.New Jersey：IEEE Press，2002：1218-1224.

［14］YAICHE H，MAZUMDAR R R，ROSENBERG C.A game theoretic framework for bandwidth allocation and pricing in broadband networks［J］.IEEE／ACM Transactions on Networking，2000，8（5）：667-678.

［15］ROMANOUS B，BITAR N，ZAIDI S A R.A game theoretic approach for optimizing density of remote radio heads in user centric cloud-based radio access network［C］／／2015 IEEE Global Communications Conference （GLOBECOM），Dec 6-10，2015，San Diego，CA，USA.New Jersey：IEEE Press，2015：1-6.

A user group gaming policy of OpenFlow stream scheduling in SDN

LIN Xiaoyong1，ZHU Yuanyuan1，MEI Jie2，MI Zhengkun1
1.College of Communication and Information Engineering，Nanjing University of Postsamp;Telecommunications，Nanjing 210003，China 2.School of Information and Communication Engineering，Beijing University of Postsamp;Telecommunications，Beijing 100876，China

A user centric networking （UCN）structure based on SDN framework was proposed，which established an OpenFlow stream scheduling model named user group gaming policy.Non-cooperative and cooperative cross-layer scheduling were compared from UCN to control plane by extracting parameters of user gaming index and user expected bandwidth.Simulation results show that the user group satisfaction degree of cooperative gaming scheduling is the best and will help the communication operators to realize the concept of customer being king.

user centric networking，software defined networking，user group gaming，cooperative gaming，satisfaction degree

s： The NationalNaturalScience Foundation ofChina（No.61471203），Jiangsu ProvincialEducation Department Project（No.14KJA510004），Jiangsu Provincial Technology Department Project（No.BY2013095-2-12），2016 JPED Postgraduate Educationamp;Innovation Project

TN393.01

10.11959／j.issn.1000-0801.2016208

2016-06-22；

2016-07-29

糜正琨，mizk@njupt.edu.cn

国家自然科学基金资助项目（No.61471203）；江苏省教育厅资助项目（No.14KJA510004）；江苏省科技厅资助项目（No.BY2013095-2-12）；2016江苏省教育厅研究生教育创新工程