刘焕淋,谭明明,任 杰,陈 勇,邱 艳,胡俊岭
(1. 重庆邮电大学 通信与信息工程学院,重庆 400065;2. 重庆邮电大学 自动化学院,重庆 400065)
近年来,视频会议、在线学习和云存储等多样化带宽需求的新兴互联网应用的兴起,正悄然改变着人们的生活方式[1-2]。同时,大量的数据中心应用程序,如云计算、网格计算等用于数据存储和转发服务成为光网络中互联网协议(internet protocol, IP)流量爆炸性增长的主要驱动因素[3-5]。为了确保服务质量,这些应用程序以具有确定开始时间和结束时间特性的可调度请求(scheduled lightpath demands, SLD)传输耐延迟的服务,成为光网络中IP流量的重要组成部分[6]。为了满足这些多样化新兴业务的灵活带宽需求,弹性光网络(elastic optical networks, EONs)技术的提出解决了传统的波分复用由于其固定的频谱栅格特性而造成的频谱浪费的问题,使弹性光网络成为极具前景的新兴光骨干网技术[7]。
EONs技术带来了灵活的资源分配和高效的频谱利用率,但由于连接请求动态建立和释放光路所引发的频谱-时间资源碎片问题影响了EONs频谱利用率的提高[8]。同时,可调度请求的时间特性使EONs的频谱-时间碎片问题更加严重,为了减少频谱-时间的资源碎片率,设计有效的路由频谱分配(routing and spectrum allocation, RSA)算法是提高弹性光网络资源利用率的重要手段。
解决频谱碎片问题的方法主要有碎片整理[9-11]和碎片感知[12-13]资源分配方法。碎片整理是对当前已占用的频谱资源重新配置,大多数碎片整理方法可以分为主动型和被动型。在主动型碎片整理策略中,不考虑网络连接是否存在阻塞,在一定时间周期后定期进行频谱碎片整理操作[10],其主要目标是优化整个网络的频谱资源;在被动型碎片整理策略中,需要设计一定碎片整理触发条件,如基于业务连接阻塞触发的频谱碎片整理方法,即当前频谱资源下无法为连接请求提供足够的资源[11]。
碎片感知资源分配方法是在连接请求到来前根据碎片度量公式对当前频谱资源占用情况进行预分配,以便为后续连接请求保留尽可能多的频谱资源[12]。文献[13]提出了一种多路径碎片感知路由频谱分配算法,该算法定义了频域的频谱资源块,采用碎片感知方法为每个连接请求预先选择产生频谱碎片较小的频谱资源块,其目的是改善阻塞率性能,但当路由可用频谱资源无法满足请求所需带宽时,该请求直接被阻塞,频谱利用率较低。
在EONs中,考虑交换节点端口数据速率与光纤链路上频谱资源可用情况,在端口配置频谱切片机也可以在频域一定程度上松弛频谱分配的连续性约束,减少频谱碎片的产生,但在节点中配置频谱切片机技术复杂,成本代价昂贵[14]。文献[15]提出了基于三级频谱切片交换节点架构的路由频谱分配算法,但是在频谱资源分配策略上对于频谱切片机的切片准则没有进行准确的划分,且仿真网络架构单一,在实际网络拓扑中可拓展性不强。
对于确定开始时间和结束时间特性的可调度请求已有文献进行了频谱-时间资源分配算法研究。文献[16]提出混合可调度请求和即时请求的路由频谱和时间分配算法,能对频谱-时间资源进行专有分区,将请求划分为不同的频谱资源区域和持续时间资源区域,但对于具有开始时间滑动窗口的可调度请求难以满足其时间灵活性;文献[17]提出一个流量均衡二维频谱-时间路由频谱分配(traffic balancing based RSA in bandwidth and time domain, TBRSA-BT)算法,将可调度请求时域分布视为具有周期特性,在一个周期内时域被分为工作时间和非工作时间,进行时域滑动和位移,在频谱-时间2个维度达到流量均衡,但是工作时间和非工作时间窗口划分具有地域特殊性;文献[18]提出空-时-频最小化串扰的路由频谱纤芯和时间分配算法,并提出针对单芯光纤未考虑芯间串扰的最小资源消耗的路由频谱和时间分配(minimize resource consumption based routing, spectrum and time allocation , MR-RSTA)算法,该算法根据可调度请求的所需带宽和持续时间,划分频谱资源和时间资源窗口,减少频谱-时间资源的消耗,但该算法未考虑在节点配置频谱切片机,不能充分利用频谱-时间的碎片资源实现业务的传输。
结合可调度请求的时间特性和大带宽的需求,对弹性光网络中同时优化光节点结构和频谱-时间资源碎片的研究较少,尤其是在动态业务场景下,更加灵活的请求分布增加了资源分配的难度,传统静态业务模型和资源分配算法也不再适用。因此,论文提出一个基于频谱切片的可调度请求路由频谱和时间分配(routing spectrum and time allocation for scheduled lightpath demands based on spectrum slicing, SS-RSTA)算法。在路由选择阶段,基于K条最短路径(K-shortest paths,KSP)算法筛选出候选路径集合,并根据综合情况考虑路径长度、路径上碎片率和节点可用频谱切片机数量的路径权重值对候选路径集合排序;在资源分配阶段,采用链路碎片感知方法为可调度请求选择可用的频谱-时间资源窗口;当资源分配失败时,使用频谱切片准则将原可调度请求从源节点到目的节点切分为多个带宽子部分,提高请求成功传输概率的同时将分配资源产生的频谱-时间碎片最小化,提升频谱利用率,降低业务的带宽阻塞率。
1.1 基于频谱切片的EONs节点架构
弹性光网络中基于频谱切片的节点架构如图1所示,包括3个模块:频谱选择开关(spectrum selective switch, SSS)、光交换模块(optical switch)和频谱切片机(Slicer)。
图1 基于频谱切片的节点架构Fig.1 Node architecture based on spectrum slicing
SSS与输入端口和输出端口分别连接,并根据EONs控制器的决定为每个频谱切片器选择频率梳。D个频谱切片器以节点共享的方式与光交换模块连接,形成共享反馈型频谱切片模块。在节点配置频谱切片机,当资源分配失败时,将原可调度请求进行频谱切分,从而放松频谱连续性的约束[19-20]。
1.2 业务模型
设网络拓扑结构为G(N,E,F),其中,N和E分别表示节点集合和链路集合,F为每条光纤链路所包含的频隙集合;可调度请求表示为di(s,d,b,st,ht,dt),其中,s,d分别表示可调度请求di的源目的节点对,b为可调度请求带宽需求,st,ht,dt分别表示可调度请求的开始时间、持续时间和结束时间。
根据可调度请求源目的节点对s,d,使用KSP算法得出请求候选路径集合,以及业务带宽需求b,计算出请求所需频隙数量,即
(1)
(1)式中:b表示请求带宽需求;bfs为每频隙带宽,大小为12.5 GHz;m为调制格式对应的调制等级;FG为保护频隙数。
图2 候选频谱资源窗口示意图Fig.2 Candidate spectrum resource window
可调度请求在传输过程中时域分配的时隙必须是连续的,且等于请求持续时间ht,根据可调度请求的开始时间st和结束时间dt,搜寻候选路由链路可用的时间资源,得到可用候选时间资源窗口(TWj)集合,如图3所示。
图3 候选时间资源窗口示意图Fig.3 Candidate time resource window
在频谱和时间资源分配阶段,根据图2和图3得到的候选频谱-时间资源窗口作为可调度请求的候选资源窗口。
本文基于频谱切片的EONs节点架构,根据可调度请求,资源分配可分为2个阶段: ①当可用资源充足时,在路由选择阶段采用KSP算法选择K条候选路径;在频谱-时间分配阶段,采用链路资源碎片感知方法为可调度请求选择路径碎片率最小值对应的频谱-时间资源窗口;②当资源分配失败时,在路由选择阶段,设计综合考虑路径长度、路径的资源碎片率和节点配置的可用切片机数目的路径权重值计算公式,并根据路径权重值降序排列原K条候选路径,存入新的候选路径集合;在频谱-时间分配阶段,使用频谱切片准则将原可调度请求切分为多个子带宽请求,增加可调度请求频谱分配成功的概率,提高资源碎片的利用率。
本文设计的综合考虑路径长度、路径的资源碎片率和节点配置的可用切片机数目的路径权重值计算方法为
(2)
(2)式中:Wp表示候选路径P的路径权重值;α,β,γ分别为离差标准化后的路径长度Lp,归一化路径碎片率NFRp和可用频谱切片机数目SLav的权重系数,且α+β+γ=1。本文通过试错法,设定提高频谱-时间碎片利用率为目标进行不断试验和消除误差,确定α,β,γ的取值[21]。
候选路径Pi的资源碎片率的计算公式为
(3)
(3)式中,PFRSWi,TWj表示将业务分配在候选路径Pi的频谱-时间资源窗口{SWi,TWj}的资源碎片率;MPFR表示候选路径Pi的资源碎片的最大值。
(4)
(4)式中:Kp表示候选路径Pi的空闲频谱块数目;fp,k表示第kp个空闲频谱资源窗口所包含的频隙数。
MPFR表示为
(5)
(5)式中,N为包含频隙数。最大路径碎片率示意图如图4所示,即候选路径Pi包含N个频隙的资源碎片率PFR的最大值。
图4 最大路径碎片率示意图Fig.4 Schematic of maximum path fragmentation ratio
若在当前路径Pi中没有满足可调度请求所需的频隙,即频谱分配失败,则采用频谱切片准则,将原请求所需带宽切片为多个子带宽请求,增加可调度请求频谱分配成功的概率,提高网络的频谱-时间资源碎片的利用率。其中,频谱切片准则的终止条件表示为
(6)
(6)式表示业务依次从候选路径的频谱碎片集合中选择多个空闲频谱资源窗口,当M个空闲频谱窗口之和大于等于可调度请求所需的频隙数目,则结束频谱切片操作。此目的是在满足请求频谱资源分配的基础上,尽可能少地使用频谱切片机。
算法1SS-RSTA算法
输入:网络拓扑G(N,E,F),可调度请求di(s,d,b,st,ht,dt);
已经79岁高龄的东莞市交通运输局原副局长卢锐平对当年经历记忆犹新：“广深高速公路的集资模式，成为后来省内其他高速公路建设纷纷效仿的样板，当年参与广深项目的交通人才，被全国各地高速公路建设工程抢夺，广深高速公路被称为中国高速公路的‘黄埔军校’。”
输出:输出业务传输的路由,频谱-时间资源窗口和更新可用切片机数量SLav。
步骤1 计算网络拓扑结构G(N,E,F)中节点度数的平均值,记为D,为每个节点配置数目为D的频谱切片机,转步骤2。
步骤3 依次判断候选路径Pi是否有满足可调度请求di所需的连续空闲频谱-时间资源窗口,若满足,转步骤5;否则,执行步骤4。
步骤4 采用频谱切片准则为业务选择频谱-时间资源窗口:
步骤4-1:检查候选路径Pi的频谱占用情况,将路径Pi中空闲频谱资源窗口所包含的频隙数从大到小依次降序排列在集合{b1,b2,…,bk}中,转步骤4-2;
步骤4-3:根据(3)式计算频谱切分后候选路径Pi的资源碎片率,若有资源碎片率相同的多个候选频谱资源窗口,则使用首次命中(FirstFit,FF)频谱分配策略,为可调度请求分配频谱窗口和满足业务时间需求时间窗口,转步骤7。
步骤7 输出业务选择的路由、频谱-时间资源窗口,更新节点的可用切片机数量SLav。
SS-RSTA算法示例如图5所示。图5a为网络拓扑结构G(N,E,F),节点集合N中的节点数目为6,链路集合E中的链路数目为9,每链路包含频隙数为10 FSs,时隙数为10 TSs;网络拓扑中节点间数值表示路径长度值,每个节点配置3个频谱切片机,为简单起见,设候选路径K=1;可调度请求d1(A,D,b,4,3,6)和d2(A,C,b,4,4,7)。
在图5a中,根据(1)式计算请求d1和d2所需频隙数分别为4 FSs和2 FSs;由KSP算法得到请求d1的候选路径为A-D,图5b表示候选路径A-D的频谱-时间资源占用情况。根据SS-RSTA算法,首先根据链路的频谱-时间占用情况,发现候选路径A-D没有满足请求所需的空闲频谱-时间资源窗口,若不使用频谱切片准则为业务分配资源,则业务将被阻塞;若执行SS-RSTA算法的频谱切片准则分配资源,对候选路由路径A-D从源节点到目的节点上采用频谱切片准则;将候选路径A-D的空闲频谱-时间资源窗口从大到小排序在集合{(SW8-9,TW4-6),(SW5,TW4-6),(SW1-2,TW4-6)}中;利用(6)式,节点A到节点D分别使用一个频谱切片机,将原可调度请求d1切分为2个频谱-时间窗口,即频谱-时间资源窗口{(SW1-2,TW4-6),(SW8-9,TW4-6)},则可调度请求d1频谱分配成功。
同理,采用KSP算法,得到可调度请求d2的候选路径为A-B-C,图5c表示候选路径A-B-C的频谱-时间资源占用情况。根据SS-RSTA算法,首先统计路由A-B-C频谱-时间占用情况,将候选路径A-B-C满足请求所需的空闲频谱-时间资源窗口保存在集合{(SW1-2,TW4-7),(SW7-8,TW4-7),(SW8-9,TW4-7)}中;使用(3)式计算上述不同候选频谱-时间资源窗口的路径A-B-C的资源碎片率,其值分别为NFRSW1-2,TW4-7=0.013,NFRSW7-8,TW4-7=0.12,NFRSW8-9,TW4-7=0.12;选择路径资源碎片率最小值对应的频谱-时间资源窗口,即{(SW1-2,TW4-7)},分配给可调度请求d2。
图5 候选路径A-B-C的频谱-时间资源占用情况Fig.5 Spectrum-time resource occupation of candidate path A-B-C
3.1 仿真环境及评价指标
为了验证本文所提SS-RSTA算法的性能,选择的对比算法分别为基准算法(K shortest paths-first fit, KSP-FF)[22]、TBRSA-BT算法[17]和MR-RSTA算法[18],性能指标为带宽阻塞率和频谱利用率。
仿真网络拓扑如图6所示, 包含14个节点、21条链路的国家科学基金网(national science foundation network,NSFNET)以及24个节点、43条链路的美国网络(united states of America network,USNET)。网络拓扑节点度数的平均值记为D,为每个节点配置数目为D的频谱切片机,每条光纤链路包含360个频隙,每频隙带宽大小为12.5 GHz,保护频隙FG的数目为1,候选路径集合数目K=3,路径权重系数α=0.3,β=0.4,γ=0.3[21]。可调度请求流量大小在50、100、200和400 Gbit/s之间均匀分布,可调度请求到达率服从参数为λ的泊松分布,持续时间服从参数为τ的负指数分布,仿真中可调度请求数目为106,仿真结果的置信区间为95%,误差率在5%以内。
图6 仿真网络拓扑Fig.6 Simulation network topology
带宽阻塞率和频谱利用率的计算式分别为
(7)
(8)
(7)—(8)式中:BRblock为所有阻塞业务的总带宽;BRtotal为所有传输业务的总带宽;τ为业务平均持续时间;NFS是每条链路的频隙数;Nlink是网络中的链路数;clock是仿真时间。
3.2 仿真结果分析
仿真不同网络负载下4种算法的带宽阻塞率性能,如图7所示。从图7可以发现,带宽阻塞率随网络负载的增加而逐渐增加,本文所提SS-RSTA算法获得最低的带宽阻塞率,基准算法KSP-FF的带宽阻塞率最高。这是因为本文所提SS-RSTA算法采用基于频谱切片的节点架构和链路碎片感知方法将频谱-时间碎片的影响降到最低,当资源分配失败时,采用频谱切片准则将可调度请求切分为多个子带宽请求,增加了可调度请求频谱分配成功的概率,避免了系统出现瓶颈链路。对比算法TBRSA-BT的性能略优于算法MR-RSTA,这是由于TBRSA-BT算法在节点架构上也考虑了配置频谱切片机,但频谱切片准则采用均分策略,没有综合考量当前候选路由的频谱-时间资源状态,因此,带宽阻塞率性能相较于本文算法较差。相比于NSFNET网络,USNET网络平均节点度数更高,具有更高的网络连通度,所以在相同网络负载下,USNET网络不易发生阻塞,其带宽阻塞率较低。
图7 不同网络负载下带宽阻塞率的对比Fig.7 Bandwidth blocking probability under different traffic loads
4种算法在不同网络负载下的频谱利用率性能如图8所示。其中,本文所提的SS-RSTA算法在2种网络拓扑下都获得了最高的频谱利用率,对比算法TBRSA-BT获得了次优的频谱利用率,基准算法KSP-FF的频谱利用率最低。这是因为,本文所提SS-RSTA算法考虑了可调度请求的频谱-时间特性。针对资源无法满足可调度请求的情况,在选路阶段,综合考虑了候选路径的资源碎片率和可用频谱切片机数量;在频谱-时间资源分配阶段,使用频谱切片准则,将可调度请求切片为多个子带宽,并结合链路资源碎片度量公式,为可调度请求选取多个空闲频谱-时间资源窗口满足业务需求,且产生最少的频谱-时间资源碎片,提高频谱-时间碎片资源的利用率。
图8 不同网络负载下频谱利用率的对比Fig.8 Spectrum utilization under different traffic loads
4.1 工作总结
论文针对弹性光网络中可调度请求的时间特性造成网络频谱-时间资源碎片化的问题,提出了SS-RSTA算法。算法定义了可调度请求的候选频谱-时间资源窗口,并根据候选路径的资源状态,得出候选资源窗口集合;在资源分配阶段,当候选路径可用资源不满足可调度请求所需频隙数,则对该请求执行从源节点到目的节点的频谱切片操作,提高可调度请求资源分配成功的概率,减少频谱-时间碎片的产生。仿真结果表明,本文所提算法能提高碎片化的频谱-时间窗口的资源利用率,降低业务的带宽阻塞率。随着互联网应用的发展和可调度请求业务的增长,有效的资源分配方法可以提高弹性光网络的服务能力和服务质量。
4.2 未来展望
本文重点研究了弹性光网络中的节点冲突调度和频谱-时间碎片化解决问题,提出了基于频谱切片的可调度请求路由频谱和时间分配算法,提高了频谱利用率,降低了业务的带宽阻塞率。随着业务量增长,碎片频谱的有效利用能增加业务成功传输概率;同时,随着网络规模化发展,未来的业务传输路由和资源分配可以考虑节能需求,提高频谱切片机的能效。后续工作中可综合考虑网络传输能耗和本文所提优化指标,提高业务成功传输概率的同时改善网络传输能耗。
猜你喜欢切片机切片频谱一种用于深空探测的Chirp变换频谱分析仪设计与实现空间科学学报(2021年6期)2021-03-09基于3DMAX的切片机三维及切片动作仿真设计锦绣·中旬刊(2020年4期)2020-10-20介绍一种石蜡切片机的防废蜡屑装置临床与实验病理学杂志(2020年1期)2020-03-05一种基于稀疏度估计的自适应压缩频谱感知算法测控技术(2018年7期)2018-12-09基于SDN与NFV的网络切片架构电信科学(2016年11期)2016-11-23Salient pairwise spatio-temporal interest points for real-time activity recognitionCAAI Transactions on Intelligence Technology(2016年1期)2016-04-11肾穿刺组织冷冻切片技术的改进方法中国组织化学与细胞化学杂志(2016年3期)2016-02-27冰冻切片、快速石蜡切片在中枢神经系统肿瘤诊断中的应用价值比较中国当代医药(2015年17期)2015-03-01切片机安全控制系统的改进设计山东工业技术(2014年14期)2014-11-30一种基于功率限制下的认知无线电的频谱感知模型电子设计工程(2014年19期)2014-02-27