基于软件定义网络的分层路径规划策略

何杰挺,王子磊,奚宏生

(中国科学技术大学 自动化系,合肥 230027)

0 概述

随着云计算技术的日趋成熟,流媒体业务也由传统的内容分发网络(Content Distribution Network,CDN)、对等网络(Peer-to-peer Network,P2P)等模式向流媒体云模式转变。流媒体云不仅具有云计算高度动态、灵活易扩展的特性,还主动将原位于网络核心的服务内容外推至网络边缘,显著减少了用户服务请求时延和骨干网络流量负载。目前,已有多种形式的流媒体云平台被提出并投入使用[1-2]。

作为一种资源密集型的服务模式,如何对其系统内部的存储、计算、网络等资源进行合理分配,以提升系统整体服务能力,是流媒体云资源调度的重点。而沿用TCP/IP协议族的传统流量工程(Traffic Engineering,TE)因缺乏必要的管控能力,导致不能在有限资源下向用户提供更好服务[3]。软件定义网络(Software Defined Networking,SDN)能够较好地解决该问题,因此,其一经提出便得到了业界的广泛关注。控制平面与转发平面相分离的设计模式,为网络流量的行为控制带来了众多机遇和优势[4]。

在有限网络资源下,用户请求模式的变动会导致资源使用率的失衡和系统整体服务能力的下降。如何对SDN中的资源进行合理优化,以提升系统的整体服务能力,业界对此进行了大量的研究。文献[5]提出一种保障视频流端到端服务质量的动态资源分配框架,并使用带约束的最短路径(Constrained Shortest Path,CSP)模型为业务流提供最佳路径。文献[6]针对可伸缩视频编码(Scalabel Video Coding,SVC)提出一种自适应路由策略,通过对不同层次视频流路径进行优化,达到系统整体最优。但是,上述路径规划策略都没有充分利用用户请求产生的应用层信息,仅采用网络拓扑结构和链路使用率对业务流进行路径优化,容易在最短路径上产生拥塞和丢包。因此,利用单一网络信息对业务流进行优化的策略,不仅没有很好的优化效果,而且不易于系统的动态扩展。

为了提升系统的优化效果,本文提出一种适用于SDN的动态路径优化策略,使用用户请求的区域信息,将优化问题分治为多个区域内的子问题,通过对物理网络资源的虚拟化处理为各个用户区域提供独立的逻辑网络资源。当区域使用量产生波动时,对分配结果进行动态柔性调整,尽可能多地满足各个区域的用户需求。在子优化问题的求解中,充分利用当前流行度信息,当视频流行度发生变化时,综合考虑网络资源使用率和服务现状,并对分配结果进行动态调整。此外,在将数据流的具体转发规则通过SDN中心控制器下发给各交换机时,如校园网络[7]、企业网络[8]和数据中心网络[9-10]的控制方式会产生众多的流表项,为缓解流表项和交换机存储空间间的矛盾,本文提出一种结合队列调度的执行机制:业务流数据包在包头携带特定标签,交换机根据标签上的路径信息选路,根据权重信息设定转发速率。

1 边缘云服务模型

本文处理的一种流媒体边缘云(Streaming Media Edge Cloud,SMEC)服务系统模型如图1所示。SMEC部署在网络边缘,通过基于SDN技术的承载网络向周边地区提供视频服务。由支持OpenFlow协议的控制器和交换机组成视频流承载网络的主体。

图1 基于SDN的SMEC服务架构

SMEC内部由多个流媒体服务器和业务管理服务器组成。其中,流媒体服务器上部署了相应的视频资源;业务管理服务器用于处理用户的服务请求,并将服务信息提供给OpenFlow控制器。众多的客户端从网络边缘接入,从相同交换机接入的客户端被抽象成一个用户区域。

针对接入SMEC系统的众多视频请求,需要在网络中分配合适的承载路径,系统中的整体请求可以看作各个用户区域请求的叠加。不同区域间的服务请求除了共享系统网络资源外,还具有一定的独立性。通过网络资源虚拟化的手段将物理网络按照用户区域划分成多个独立子网络,可将原路径优化问题分治为多个用户区域内的子问题。为了更好地分治优化问题并动态适应各个分治区域请求的波动性,本文提出如图2所示的分层优化方案:资源虚拟化为分治问题,产生网络切片,运用路径规划求解各个分治子问题。

图2 OpenFlow控制器分层策略示意图

在上述模型下,本文的研究问题可以描述为:在网络拓扑G已知的情况下,利用不同视频的流行度信息,结合当前网络的运行状态,通过动态调整网络中视频流的承载链路和带宽,使得网络资源能够承载更多的视频流。

2 分层路径规划方案

2.1 方案描述

考虑到OpenFlow交换机中有限的流表空间,本文提出一种基于队列调度的带宽分配方案,该方案能有效减少流表空间的占用,适用于拓扑复杂、业务繁重的SMEC等系统。

2.2 资源虚拟化策略

对完整的物理网络进行虚拟化分割,为上层路径规划提供数据源到目的地的连通性保证,并根据各子网的实际网络使用情况重新调整分割方案,使网络尽可能多地承载业务数据流。

为使对各子网的资源分配达到网络层面的公平,本文采用将网络中最小割链路扩展为完整路径的方法,为每个独立的子网Gk选取J(常数)条从SMEC到用户区域的完整路径,并对物理网络按上述路径进行带宽资源预分配,分配阈值矩阵记为M=(mkj)K×J,其中,元素mkj表示子网Gk中第j条路径分配的阈值带宽。当新的视频服务需求到达时,如果子网内的整体使用流量uk没有超过预分配值,则直接提供服务。考虑到网络流量的波动性,当预分配值不能满足服务流量需求时,需要对分配矩阵M进行调整。

考虑到在SDN中,控制器需要通过下发流表的方式将决策信息告之相关的交换机,且虚拟子网的阈值改变也会触发路径规划策略的执行,因此,在对矩阵M进行动态调整时,尽量使每次调整涉及的路径较少,故给出如下优化目标:

(1)

综上,以带宽分配矩阵m*为决策变量,给出如下动态调整模型:

Subject to:

在该优化模型中,包含一个l0-范数的优化目标,然而l0-范数的非凸性使得优化模型无法通过凸优化的方式进行求解。在实际中,可用l0-范数的最优凸近似l1-范数替换l0-范数[13],再通过凸优化进行求解。

2.3 路径规划策略

2.3.1 静态初始化过程

(2)

该目标即为在各视频分配的有效带宽之和最大。

subject to:

该模型是一个凸优化模型,可以通过凸优化的方式进行求解。

2.3.2 动态调整过程

在实际服务过程中,不可避免地存在视频流行度发生变化的情况,这时需要对分配矩阵Fk进行重新调整。在保证有效分配带宽尽可能大的同时,对视频带宽在不同路径上的分配作出指导,使得路径的负载趋于均衡,引入次优化目标:

(3)

subject to:

该模型是一个多目标凸优化模型,可使用分层序列法对其进行求解,首先针对第1个优化目标进行凸优化求解,得到最优值后将第1个优化目标转换为新增最优值约束,再对第2个优化目标进行凸优化求解。

2.4 执行策略

在CDN中,交换机的转发策略需要中心控制器统一下发。在交换机一侧,用于存储流表项的三态内容寻址存储器(Ternary Content Addressable Memory,TCAM)因其高昂的造价而无法大规模应用[14]。随着网络拓扑和应用业务规模的增加,中心控制器的性能和交换机的流表内存容易成为CDN发展的瓶颈。

3 性能仿真与分析

3.1 仿真实验设置

仿真所用网络拓扑由波士顿大学的拓扑生成器BRITE[16]生成,各用户区域使用的流量数据基于中国科学技术大学校园网络多个互联网服务供应商(Internet Server Provider,ISP)出口处的真实网络使用量产生:每5 min测量一次校园网5个独立ISP网络出口的带宽使用情况,选用连续20 d的测量数据,共(20×24×60)/5=5 760个数据点。使用真实网络带宽数据进行仿真实验时,考虑到测量数据一定小于物理链路带宽,因此,本文对真实数据进行了线性放大处理,并在放大实际数据量的同时,保留了原始数据良好的周期性和波动性。

(4)

其中,ψ为倾斜系数,本次实验中ψ=0.7。

仿真中请求的到达过程符合参数为λ的泊松过程[18],会话时长符合文献[19]分布,并设平均时长为50 min。其他子网仍使用采集的真实网络流量数据作为背景流量。设定总仿真时长为500 min。

3.2 资源虚拟化动态调整

当网络流量大于分配的资源阈值时,可以认为网络中会产生拥塞、丢包等现象。选用仿真过程中产生拥塞的次数作为性能指标,分别测试并统计不同放大倍数下的策略性能。为更好地反映动态调整的效果,仿真实验中加入了2组对照实验:无动态调整策略和理论最大流限制策略,实验结果如图3所示。其中,理论最大流是指在给定网络拓扑下,不考虑不同区域流量间的相互影响时各独立区域所能达到的网络最大流,该值即为网络理论服务能力的上限。

图3 3种方案拥塞总数统计

由图3可以看出,本文提出的动态调整策略能够对分配方案进行有效调整,大幅降低了拥塞次数,在满负载前(放大倍数小于1.20),该策略几乎不产生拥塞;当网络满载后(放大倍数大于等于1.20),该策略产生的拥塞数略高于理论最优情况,但明显优于无调整的情况。综上,本文提出的动态调整策略能够显著提升网络服务能力。

3.3 路径规划

在上层路径规划过程中,因为考虑到各子网规划问题的独立性,所以仅在一个子网内部仿真视频请求,其余子网均使用采集的真实流量数据作为背景流量。实验时,背景流量和泊松过程产生的服务均具有波动性,资源虚拟化过程会动态执行并为各子网分配合适的资源。在选中子网内部,每100 min对视频请求的流行度进行一次旋转,用来模拟用户区域流行度的变化情况。实验分别从请求波动性、服务接受性能和迁移代价三方面对本文策略进行验证。

首先验证请求波动性对本文策略的影响。因为对用户区域内的请求整体进行路径规划,所以单个用户请求的突发性综合表现为整个用户区域内视频流行度的变化。采用对视频编号进行旋转的方法[20]产生流行度的波动,旋转因子π表示波动的大小。选取请求到达率λ=55使系统处于刚满载状态,多次实验得出请求拒绝率和迁移比例,结果如表1所示。由表1可以看出,本文策略能够较好应对视频流行度的波动变化。

表1 旋转因子对本文策略影响统计 %

为了说明本文策略中采用流行度信息和最低负载对服务接入的指导性,使用请求拒绝率和路径迁移比例作为调整代价。在对比实验方面,选用文献[5-6]中的CSP算法。此外,随机策略作为网络技术中常用的手段,在实际应用中被广泛采用,因此,再挑选“动态调整(Dynamic Adjust,DA)+随机接入(Random Access,RA)”策略作为另一组对比实验。DA+RA策略是指当流行度发生变化后,对矩阵Fk进行与本文类似的动态调整,优化接入系统的服务总量,但对每个服务采用随机化的方式接入,不考虑其他信息。表2给出了本文策略、DA+RA策略与CSP策略的拒绝率统计情况。由表2可以看出,本文策略和DA+RA策略的请求拒绝率远低于CSP策略,原因是CSP策略没有利用应用层的请求信息,其根据网络信息对路径进行动态规划,容易在物理网络中形成瓶颈资源,影响系统的整体性能。

表2 不同策略拒绝率对比

为说明本文策略对迁移代价的优化,在不同请求到达率下对不同策略进行迁移比例统计,结果如表3所示。从表3的数据中可以看出,本文策略的迁移比例明显低于CSP策略和DA+RA策略,原因是本文的接入指导策略能够避免由随机接入造成的盲目迁移,其通过有效减少视频流的迁移次数降低了系统的整体服务代价,而CSP策略因对请求进行了大量的拒绝,导致迁移比例低于DA+RA策略。

表3 不同策略迁移比例对比

综上,本文提出的分层策略充分利用视频流行度信息和网络负载状态,能在有限的性能损失下为视频流提供合适的路径。

4 结束语

本文提出一种分层优化的路径规划策略,该策略的底层优化保证了路径的连通性,对物理网络进行虚拟化的子网划分缩减了优化规模,充分利用视频的流行度信息降低了视频流迁移代价。考虑到实际应用中CDN的性能瓶颈,本文还提出一种基于队列调度的执行策略,通过数据包头部的标签保证数据的正确转发和带宽分配。该策略能够明显减少控制流表的下发和存储,使得其在大规模CDN上的应用成为可能。下一步将把网络路径规划与SMEC内部视频部署、SMEC自身部署相结合,通过对系统不同层面的资源进行综合优化,以提升SMEC平台的服务能力。

[1] JADHAV S,KAKADE V,KAMBLE S,et al.Media streaming applications using cloud[J].International Research Journal of Engineering and Technology,2016,3(5):2091-2096.

[2] 北京原力创新科技有限公司.云模式流媒体服务平台:200910091537.2[P].2010-01-27.

[3] 高翔宇.一种POF控制器的实现与流量管理研究[D].合肥:中国科学技术大学,2016.

[4] AKYILDIZ I F,LEE A,WANG P,et al.A roadmap for traffic engineering in SDN-OpenFlow networks[J].Computer Networks,2014,71:1-30.

[5] XU C,CHEN B,FU P,et al.A dynamic resource allocation model for guaranteeing quality of service in software defined networking based cloud computing environment[C]//Proceedings of International Confe-rence on Cloud Computing and Security.Berlin,Germany:Springer,2015:206-217.

[6] YU T F,WANG K,HSU Y-H.Adaptive routing for video streaming with QoS support over SDN networks[C]//Proceedings of 2015 International Conference on Infor-mation Networking.Washington D.C.,USA:IEEE Press,2015:318-323.

[7] MCKEOWN N,ANDERSON T,BALAKRISHNAN H,et al.OpenFlow:enabling innovation in campus networks[J].ACM SIGCOMM Computer Communication Review,2008,38(2):69-74.

[8] CASADO M,FREEDMAN M J,PETTIT J,et al.Rethinking enterprise network control[J].IEEE/ACM Transactions on Networking,2009,17(4):1270-1283.

[9] JAIN S,KUMAR A,MANDAL S,et al.B4:experience with a globally-deployed software defined WAN[C]//Proceedings of SIGCOMM’13.New York,USA:ACM Press,2013:3-14.

[10] HONG C Y,KANDULA S,MAHAJAN R,et al.Achieving high utilization with software-driven WAN[C]//Proceedings of SIGCOMM’13.New York,USA:ACM Press,2013:15-26.

[11] SCHWARZ H,MARPE D,WIEGAND T.Overview of the scalable video coding extension of the H.264/AVC standard[J].IEEE Transactions on Circuits and Systems for Video Technology,2007,17(9):1103-1120.

[12] NIU D,XU H,LI B,et al.Quality-assured cloud bandwidth auto-scaling for video-on-demand applications[C]//Proceedings of 2012 IEEE INFOCOM.Washington D.C.,USA:IEEE Press,2012:460-468.

[13] DONOHO D L.For most large underdetermined systems of linear equations the minimal L(1)-norm solution is also the sparsest solution[J].Communications on Pure and Applied Mathematics,2006,59(6):797-829.

[14] BRAUN W,MENTH M.Wildcard compression of inter-domain routing tables for OpenFlow-based software-defined networking[C]//Proceedings of the 3rd European Workshop on Software Defined Networks.Washington D.C.,USA:IEEE Press,2014:25-30.

[15] 尹德斌,谢剑英.一种新的加权公平队列调度算法[J].计算机工程,2008,34(4):28-30.

[16] MEDINA A,LAKHINA A,MATTA I,et al.BRITE:an approach to universal topology generation[C]//Proceedings of the 9th International Symposium on Modeling,Analysis and Simulation of Computer and Telecommunication Systems.Washington D.C.,USA:IEEE Press,2001:346-353.

[17] QIU T,GE Z,LEE S,et al.Modeling channel popularity dynamics in a large IPTV system[C]//Proceedings of the 7th International Joint Conference on Measurement and Modeling of Computer Systems.New York,USA:ACM Press,2009:275-286.

[18] YU H,ZHENG D,ZHAO B Y,et al.Understanding user behavior in large-scale video-on-demand systems[C]//Proceedings of the 1st ACM SIGOPS/EuroSys European Conference on Computer Systems.New York,USA:ACM Press,2006:333-344.

[19] CHEN L,ZHOU Y,CHIU D M.Smart streaming for online video services[J].IEEE Transactions on Multimedia,2015,17(4):485-497.

[20] WEI X,YANG J,XI H.A novel content updating policy based on dynamic storage balancing for clustered streaming media system[C]//Proceedings of IEEE International Conference on Control and Automation.Washington D.C.,USA:IEEE Press,2009:2031-2036.