浙江大学学报(工学版), 2020, 54(9): 1746-1752 doi: 10.3785/j.issn.1008-973X.2020.09.010

计算机技术

基于时间槽的可降带宽核心网视频业务动态资源预约算法

成海秀, 李冠霖, 张凌,

Dynamic resource reservation algorithm for core network video business with bandwidth reduction based on time slot

CHENG Hai-xiu, LI Guan-lin, ZHANG Ling,

收稿日期: 2019-09-25  

Received: 2019-09-25  

作者简介 About authors

成海秀(1984—),女,讲师,博士生,从事高速视频网络QoS研究.orcid.org/0000-0002-2856-9851.E-mail:cshx.cheng@mail.scut.edu.cn

摘要

为了解决未来核心网络中大容量、低延时视频业务的服务质量保证问题,以视频会议业务为例,在基于软件定义网络的核心网络框架下,将视频会议请求解析为多个资源请求,以时间槽为单位进行带宽资源的提前预约,提出一种可降带宽的资源预约算法. 在进行动态资源预约时,若发现在某个时间比例内链路不满足视频业务带宽需要,则采用降带宽的方式进行处理,以避免视频业务在某个较短时间段内因带宽不满足需求而导致预约失败. 仿真实验结果表明:相比不采用降带宽的动态资源算法,该算法能够有效提高视频业务资源预约的成功率,参会方个数越多,时间槽越小,成功率的提升越大.

关键词: 核心网 ; 视频业务服务质量(QoS) ; 时间槽 ; 可降带宽 ; 动态资源预约算法

Abstract

Taking video conference service as an example, a resource reservation algorithm that could reduce bandwidth was proposed, in order to solve the problem of service quality assurance for large-capacity and low-latency video services in the core network in the future. The video conference requests were resolved into multiple resource requests, and then the bandwidth resource was reserved in advance in units of time slots, under the core network architecture based on software defined network. When making bandwidth reservation, if it was found that the link did not meet the bandwidth requirements of the video service within a certain time scale, the bandwidth reduction method would be adopted to avoid the reservation failure problem caused by the insufficient bandwidth demand in a short period of time. The simulation experimental results show that, compared with the dynamic resource algorithm without bandwidth reduction, this algorithm can effectively improve the success rate of video service resource reservations; the greater the number of participants and the smaller the time slot, the greater the improvement of the success rate will be.

Keywords: core network ; quality of service (QoS) for video business ; time slot ; bandwidth reduction ; dynamic resource reservation algorithm

PDF (1088KB) 元数据 多维度评价 相关文章 导出 EndNote| Ris| Bibtex  收藏本文

本文引用格式

成海秀, 李冠霖, 张凌. 基于时间槽的可降带宽核心网视频业务动态资源预约算法. 浙江大学学报(工学版)[J], 2020, 54(9): 1746-1752 doi:10.3785/j.issn.1008-973X.2020.09.010

CHENG Hai-xiu, LI Guan-lin, ZHANG Ling. Dynamic resource reservation algorithm for core network video business with bandwidth reduction based on time slot. Journal of Zhejiang University(Engineering Science)[J], 2020, 54(9): 1746-1752 doi:10.3785/j.issn.1008-973X.2020.09.010

近年来,随着互联网技术的发展和有线4K、无线2K、AR/VR等业务的兴起,世界进入了“无处不视频”的大视频时代,视频业务已经由单一的媒体服务应用发展到基于网络的多种交互式视频应用. 近几年,网络中的视频流量剧增,思科在2019年2月公布《思科可视化网络指数:预测和方法,2017—2022 年》白皮书[1]中指出,到2022年,IP视频流量在全部IP流量中的占比将从75%增至82%. 视频业务对带宽和时延都较敏感,既需要有足够的带宽来满足高清视频流的传输要求,又要限制一定的时延来保证音视频流的流畅性. 保证视频业务的服务质量对核心网来说尤为重要.

网络流量可预测是视频业务的一个关键特征. 一般情况下. 视频业务的开始时间、持续时间、视频业务的参与终端个数以及终端所能提供的视频流大小都是可以预知的. 鉴于视频业务流量的可预测性,资源预约是保证视频业务服务质量的一种切实可行方法. 资源预约分为提前预约(advanced reservation,AR)和即时预约(immediate reservation,IR),前者在视频业务开始前为业务预约所需的带宽资源,后者在视频业务的进行过程中为新加入的视频业务终端提供即时的带宽预约[2].

软件定义网络(software defined network,SDN)[3]解耦了控制面和数据面,数据面的Openflow交换机只负责视频流的转发,而决策则由SDN控制器来完成. 一方面,这降低了底层交换机的开销,加快了包的转发速度;另一方面,SDN控制器可以获得网络的全局状态信息,基于全局的决策可以为视频业务进行全局的资源预约.

Barshan等[4-7]在媒体生成网络(media production networks)中对基于时间槽的资源预约算法进行了研究,针对媒体生成网络中业务流的特点,采用固定时间槽或者动态时间槽的方式,结合SDN来保证业务流的服务质量;但所处理的问题并不是实时的业务问题,而是业务请求并无固定开始时间的问题,只关注在最迟期限完成文件流或者多媒体流的传播,这种只关注最迟完成期限的提前资源预约算法并不适合视频会议.

已有学者对企业级视频会议的动态预约算法[8]和变带宽动态预约算法[9]进行了研究,这2种算法属于资源提前预约算法. 当存在某个时间段内的某条链路不满足带宽要求时,这2种算法都会导致整个会议预约的失败. 为此,本研究对上述2种算法进行改进,当出现因短时间内带宽不足而导致的资源预约失败时,为保证视频会议正常进行,在该时间段内采取降低带宽需求的方式重新进行预约.

1. 系统架构

基于SDN的核心网络视频业务服务质量(quality of service,QoS)管理系统架构采用的是文献[8]、[9]中所提到的架构,整个系统架构图如图1所示. 整个框架由3层组成:应用层、控制层和基础设施层,其中应用层包括视频业务管理平台和QoS管理平台,前者提供会议预约、查询等管理控制,后者使用SDN网管平台提供的服务,对视频会议的QoS进行控制;控制层为SDN网管平台,采用FloodLight控制器进行路由选择和转发管理,通过南向接口向下管理基础设施层的路由交换设备,通过北向接口向视频会议QoS管理平台提供QoS服务;基础设施层包括支持OpenFlow协议的核心网、支持OpenvSwitch协议的路由交换设备和视频业务终端设备,其中,核心网内的路由交换设备根据SDN控制器下发的流表进行包转发.

图 1

图 1   基于软件定义网络(SDN)的企业级视频会议服务质量(QoS)管理系统架构图

Fig.1   Architecture of enterprise video conference quality of service(QoS)management system based on software defined network(SDN)


2. 企业级视频会议QoS保证模型

本研究涉及到的模型有会议模型、网络模型和资源请求模型.

1)会议模型.

对文献[8]、[9]中提到的模型进行扩展,增加2个变量:一个变量w用于记录会议用户是否允许在会议预约时接收降带宽的处理;另外一个是可以接受降带宽会议请求所占的时间比例r,这2个变量均在创建会议时由会议用户确定. 会议请求C={C1C2,···,Ci,···,Cn},Ci为某一个视频会议请求,n为会议的个数. 如果暂时不考虑会议间隙,扩展后的会议请求是一个9元组,Ci ={cidFtstepκhwr},其中,cid表示会议编号,F={f1f2,···,fi,···,fn}表示参会终端列表,fi表示第i个终端,fi={fidub},fidub分别代表终端的id、终端名称和终端视频流所要求的带宽,tste分别表示会议的开始时间和结束时间,p为会议的服务优先级,κ为会议类型,h为会议主席.

本研究结合RFC4597[10]中描述的会议场景和实际的视频会议场景,主要研究2种会议场景:报告型会议、讨论型会议,其分别代表非交互式的视频业务和交互式的视频业务.

2)网络模型.

网络用有向图G表示,G={VE},其中V={v1v2,···,vi,···,vm},m为网络中路由交换节点的个数;E={e1e2,···,ei,···,ek},k为网络中链路的个数;ei={lidesedbpba},其中lid为链路的编号,esed分别为一条链路两端的节点编号,bp为物理带宽,ba为链路的可用带宽,记录了该链路在某一段时间(如:一个月或一个周)内每个时间槽下的网络带宽,用于在资源预约时动态计算网络的链路开销.

3)资源请求模型.

会议请求必须被解析为资源请求后才可以进行资源预约操作. 资源请求列表R={r1r2,···,ri,···,rρ},ρ为会议请求被资源解析后产生的资源请求的个数. ri为第i个资源请求,ri={ridcidsdtsteb},其中,rid为资源请求的编号,sd分别为源节点和目标节点,ts_s为该资源请求的开始时间槽编号,te_s为该资源请求的结束时间槽编号.

在上述3种模型中,会议模型和网络模型决定了资源请求模型,其中会议模型中的参会终端列表、会议类型、会议主席确定一个会议请求解析之后的资源请求个数和每个资源请求的源节点和目的节点.

3. 基于时间槽的动态资源预约算法

动态资源预约涉及到的算法有资源解析、资源预约和资源实现. 本研究主要针对资源解析和资源预约算法进行研究.

3.1. 基于时间槽的资源解析

资源解析算法需要将会议请求解析为具体的资源请求. 本研究在文献[8]的资源解析的基础上引入时间粒度,根据会议类型、会议时长、参会终端视频流的大小以及时间粒度进行会议解析. 根据不同的会议类型,一个会议请求被解析为λ个会议终端所在路由交换节点间的资源请求. 资源请求个数λ的计算公式因会议类型而异,如下所示.

1)讨论型会议:

$\lambda = n(n - 1)\frac{{{t_{\rm e}} - {t_{\rm s}}}}{{{t_0}}};$

2)报告型会议:

$\lambda = (n - 1)\frac{{{t_{\rm e}} - {t_{\rm s}}}}{{{t_0}}}.$

式中:g为时间粒度,取值为100、200、300、400、500和600 s,按照时间粒度将时间分割成一个个时间槽. 为了保证视频会议的每一个视频流时刻按照最优的路径进行传送,需要在每个时间槽内计算一次最优路径.

在资源解析时需要确定会议的开始时间和结束时间所在的时间槽. 会议的起止时间与时间槽的关系有4种,如图2所示. 其中,t1t2t3t4t5为时间槽的看时间或结束时间,每一格表示一个时间槽。

图 2

图 2   会议起止时间与时间槽的关系

Fig.2   Relationship between start and end time of meeting and time slot


1)会议的开始时间为某个时间槽的开始时间,会议的结束时间为某个时间槽的结束时间,如图2中的会议4所示.

2)会议的开始时间大于某个时间槽的开始时间,小于该时间槽的结束时间;会议的结束时间大于某个时间槽的开始时间,小于该时间槽的结束时间,如图2中的会议3所示. 在这种情况下,解析时需要包含起止时间所在的整个时间槽.

3)会议的开始时间等于某个时间槽的开始时间,会议的结束时间小于某个时间槽的结束时间,如图2中的会议2所示. 在这种情况下,解析时需要包含结束时间所在的整个时间槽.

4)会议的开始时间大于某个时间槽的开始时间,小于该时间槽的结束时间;会议的结束时间等于某个时间槽的结束时间,如图2中的会议1所示. 图中,t0~t5为时间槽的开始时间或结束时间. 在这种情况下,解析时需要包含开始时间所在的整个时间槽.

资源解析算法的伪代码如算法1所示.

算法1 资源解析算法

输入:会议请求列表

输出:资源请求列表

For 会议 in 会议请求列表 do

  如果会议为报告型会议

    For 终端 in 终端列表 do

      If 该终端不是会议主席 do

        资源请求={资源请求id,会议id,          会议主席,终端,开始时间槽,结          束时间槽,带宽}

        将该资源请求添加的资源请求          列表中

    else

         For 终端A in 终端列表 do

           For 终端B in 终端列表 do

             If 终端A!=终端B do

             资源请求={资源请               求id,会议id,终端               A,终端B,开始时间               槽,结束时间槽,带               宽}

              将该资源请求添                加的资源请求列                 表中

               End if

             End for

           End for

         End if

       End for

     End for

  返回资源请求列表

3.2. 基于时间槽的动态资源预约算法

基于时间槽的动态资源预约算法按照时间槽进行资源预约,以时间粒度为单位进行时间分割,每个会议占有多个时间槽. 该算法是对文献[8]中动态资源调度算法的改进,以时间槽为单位进行资源预约,如算法2所示.

算法2 基于时间槽的动态资源预约算法

输入:资源请求列表

输出:资源预约最短路径列表

For 资源请求 in 资源请求列表 do

   For 时间槽 in(开始时间槽,结束时间槽)do

    寻找源节点和目标节点间的最短路径

     If 找到最短路径 do

      将路径加入到资源预约路径列表中.

     else

      预约失败

      退出循环

     End if

   End for

End for

返回资源预约路径列表

3.3. 基于时间槽的可降带宽动态资源预约算法

在会议预约模块接收到经会议解析模块解析后的资源请求后,首先查询网络的可用带宽列表,排除不满足带宽要求的链路;然后使用最短路径算法求解2个终端之间的最短路径. 在第3.2节的算法中,若会议的某一个时间槽的资源请求得不到满足,则预约失败,网络能够接收视频会议请求的个数受到限制. 本研究考虑当一个会议20%(该值可以由会议用户来指定)以下的请求不被满足时,可以进行二次降带宽预约:首先将要求的带宽降为原来的一半,然后生成新的请求再次进行预约,如果新请求预约成功,那么整个会议预约成功,避免极短时间内因为带宽需求不满足需要而导致的资源预约失败问题,以提高系统的可接收率.

基于时间槽的可降带宽动态资源调度算法如算法3所示.

算法3 基于时间槽的可降带宽动态资源预约算法

输入:资源预约列表

输出:资源预约路径列表

For 资源请求 in 资源请求列表 do

   For 时间槽 in(开始时间槽,结束时间槽)do

      寻找源节点和目标节点间的最短路径

       If找到最短路径 do

        将路径加入到资源预约路径列表中.

       else

        预约失败

        将失败请求添加的失败列表中

       End if

   End for

End for

For 失败的资源请求 in 失败列表 do

  如果一个会议的中20%的时间槽内预约失败

     将失败资源列表作为输入执行算法3

End for

返回资源预约路径列表

4. 仿真及结果分析

4.1. 仿真环境设置

本研究的硬件环境如下:操作系统为64位Win10系统专业版,CPU为Intel(R)Core i5-7200U CPU @2.50 GHz 2.70 GHz,内存为8 G,开发语言为Python,开发工具为Sublimetext3.

本研究以某高校的校园网拓扑为例,该高校具有2个校区,其拓扑图如图3所示. 在该高校的校园网中,2个校区之间通过2个10 G的光纤链路进行连接,具体采用哪条链路进行通信要根据链路的实际状态来决定.

图 3

图 3   某高校的校园网拓扑图

Fig.3   Campus network topology of certain university


在仿真中用到的对比算法2个:一个是采用开放式最短路径优先(open shortest path first,OSPF)的基准算法,一个是动态资源预约算法[8-9]. 两者的基础都是Dijkstra算法. 对于前者,只要网络的拓扑不变,2个节点间的最短路径就不会变,但会随着网络负载的增加出现包的延时或者丢弃;对于后者,需要在每个时间槽内计算链路的开销,保证每个时间槽内的节点间最短路径都是最优路径.

4.2. 仿真建模

仿真中视频会议请求通过程序自动生成,生成规则如下.

规则1:会议的开始时间落在一个月内、某个区间内的次数服从泊松分布;

规则2:会议的持续时间符合指数分布;

规则3:会议类型从报告型会议、讨论型会议中随机选取;

规则4:参会方的个数分别为2~10;

通过该规则生成2方、3方、···、10方会议各100个,共900个会议,每一类会议中报告型会议和讨论型会议的个数基本上持平.

4.3. 仿真结果及分析

4.3.1. 不同时间粒度下的资源解析时间对比

为了确定不同大小的时间槽对资源解析算法的影响,分别在不同大小时间槽下对多方视频会议请求进行资源解析测试,测试结果如图4所示. 其中,N为参会方的个数,T为解析时间. 从图4中可知,当参会方个数确定时,时间槽越大,会议的平均解析时间越小;当时间槽大小确定时,随着参会方个数的增加,平均解析时间没有太大变化.

图 4

图 4   图4时间槽大小不同时多方会议资源解析时间对比

Fig.4   Comparison of resolution time of multi-party conference resources with different slot sizes


4.3.2. 采用不同算法的资源预约时间及成功率对比

为了评估动态资源调度算法、改进的动态调度算法及不同时间槽、不同参会方个数对资源预约成功率的影响,对所提出的2种资源预约算法和1种基准算法进行测试.

在时间槽大小不同、参会方个数不同的情况下,3种不同算法的平均资源预约时间如图5所示. 其中,图5(a)是基准算法OSPF的预约结果,图5(b)是使用基于时间槽的动态资源预约算法的预约结果,图5(c)是使用可降带宽的基于时间槽的动态资源预约算法的预约结果. 从图5可知,这3种不同算法的多方会议平均资源预约时间基本上一致,可降带宽的资源预约算法的平均预约时间稍大于基于时间槽的动态资源预约算法,算法对平均预约时间的影响基本可以忽略;但不同大小的时间槽对预约时间的影响较大,时间槽越小,平均预约时间越大. 如:当时间槽大小为100 s时,平均资源预约时间为800 s左右;而当时间槽大小为600 s时,平均资源预约时间为140 s左右.

图 5

图 5   时间槽大小不同时算法平均资源预约时间的对比

Fig.5   Comparison of algorithm average resource reservation time under different time slot sizes


不同时间槽大小对资源预约成功率的影响如图6所示,其中,Rs为算法的成功率. 从图6(a)中可知,参会方的个数和时间槽的粒度大小对成功率没有影响,但无法保证视频流的服务质量,因为在网络拓扑不发生变化的情况下,节点间的最短路径不变,2个节点间的所有视频流量及其他业务流量都会按照所选择的最短路径进行传输,这就有可能造成网络拥塞,进而导致大量的包延迟或者丢弃,影响视频业务的服务质量. 从图6(b)中可知,当时间槽大小相同时,随着参会方个数的增加,预约的成功率不断下降,直到降为0.

图 6

图 6   不同时间槽大小对不同资源预约算法成功率的影响

Fig.6   Influence of different time slot sizes on success rate of different resource reservation algorithms


对于可降带宽的资源预约算法,时间槽大小并不影响算法的预约成功率,参会方个数对成功率的影响也较小。通过对比图6(b)(c)的结果可知,基于时间槽的可降带宽动态资源预约算法的成功率大大高于基于时间槽的动态资源调度算法,使用该算法可以大大提高核心网络对视频业务的接收率.

相比动态资源预约算法,可降带宽动态资源算法的资源预约成功率显著提高,在参会方个数多、时间槽小的情况下尤为明显,如图7所示,其中,Rg为成功率的增长比例.

图 7

图 7   时间槽大小不同时可降带宽动态资源预约算法成功率的增长趋势

Fig.7   Increasing trend of success rate of dynamic resource reservation algorithm with bandwidth reduction under different time slot sizes


5. 结 语

本文提出了一种基于时间槽的可降带宽动态资源预约算法;该算法是对基于时间槽的动态资源预约算法的改进算法,当发现有某些时间槽不满足带宽需求时,执行降带宽的预约. 仿真结果表明:相比不采用降带宽的动态资源预约算法,对于N(3≤N≤10)方会议,该算法的资源预约成功率提升了1~25倍,参会方越多、时间槽越小,该算法对资源预约成功率的提升越大.

下一步的研究工作将从以下几个方面展开:1)针对大规模网络中的资源预约问题,拟采用分区域的方式提高算法的执行效率,将大型网络进行区域划分及划分效果评价;2)将区域划分、多域资源预约相结合进行算法的优化及分析.

参考文献

思科. 可视化网络指数2017-2022 [EB/OL]. (2019-02-27)[2019-07-23]. https://www.cisco.com/c/en/us/solutions/collateral/service-provider/visual-networking-index-vni/white-paper-c11-741490.html.

[本文引用: 1]

VARVARIGOS E M, SOURLAS V, CHRISTODOULOPOULOS K

Routing and scheduling connections in networks that support advance reservations

[J]. Computer Networks, 2008, 52 (15): 2988- 3006

DOI:10.1016/j.comnet.2008.06.016      [本文引用: 1]

DIEGO KREUTZ, FERNANDO M. V. RAMOS, PAULO ESTEVES VERI´SSIMO, et al

Software-defined networking: a comprehensive survey

[J]. Proceedings of the IEEE, 2015, 103 (1): 14- 76

DOI:10.1109/JPROC.2014.2371999      [本文引用: 1]

BARSHAN M, MOENS H, FAMAEY J, et al. Algorithms for advance bandwidth reservation in media production networks [C] // IFIP/IEEE International Symposium on Integrated Network Management (IM). Ottawa: IEEE, 2015: 183-190.

[本文引用: 1]

BARSHAN M, MOENS H, FAMAEY J, et al

Deadline-aware advance reservation scheduling algorithms for media production networks

[J]. Computer Communications, 2016, 77 (C): 26- 40

SAHHAF S, BARSHAN M, TAVERNIER W, et al. Resilient algorithms for advance bandwidth reservation in media production networks [C] // 2016 12th International Conference on the Design of Reliable Communication Networks. Paris: IEEE, 2016: 130-137.

BARSHAN M, MOENS H, VOLCKAERT B, et al. A comparative analysis of flexible and fixed size timeslots for advance bandwidth reservations in media production networks [C] // 2016 7th International Conference on the Network of the Future (NOF). Búzios: IEEE, 2016: 1-6.

[本文引用: 1]

成海秀, 张凌, 廖志文

企业级视频会议系统动态资源预约算法

[J]. 东南大学学报: 自然科学版, 2017, (Suppl. 1): 72- 74

[本文引用: 6]

CHENG Hai-xiu, ZHANG Ling, LIAO Zhi-wen

Dynamic resource reservation algorithm for enterprise video conference system

[J]. Journal of Southeast University: Natural Science Edition, 2017, (Suppl. 1): 72- 74

[本文引用: 6]

成海秀, 张凌, 邹杜

企业级视频会议变带宽动态资源预约算法研究

[J]. 通信学报, 2018, 39 (增1): 219- 225

[本文引用: 4]

CHENG Hai-xiu, ZHANG Ling, ZOU Du

Research on dynamic resource reservation algorithm for Enterprise video conferencing based on variable bandwidth

[J]. Journal on Communications, 2018, 39 (增1): 219- 225

[本文引用: 4]

EVEN R, ISMAIL N. Conferencing scenarios [EB/OL]. [2019-09-25]. https://www.potaroo.net/ietf/idref/rfc4597/index.html.

[本文引用: 1]

/