基于频谱切片的弹性光网络中可调度请求资源分配算法_刘焕淋.pdf

第 卷第 期重庆邮电大学学报（自然科学版）年 月 （）：基于频谱切片的弹性光网络中可调度请求资源分配算法收稿日期：修订日期：通讯作者：刘焕淋 基金项目：国家自然科学基金（）；重庆市自然科学基金（，）：（）；（，）刘焕淋，谭明明，任 杰，陈 勇，邱 艳，胡俊岭（重庆邮电大学 通信与信息工程学院，重庆；重庆邮电大学 自动化学院，重庆）摘 要：针对确定业务开始时间和结束时间特性的可调度请求加重了弹性光网络的资源碎片率和带宽阻塞率的问题，设计了一种配置频谱切片机的弹性光网络节点结构，并提出一种基于频谱切片的可调度请求路由频谱和时间分配（）算法。在路由选择阶段，设计了一种综合考虑路径长度、路径碎片率和节点可用频谱切片机数量的路径权重值的路由选择策略，为可调度请求选择路径权重值最大的路由；在资源分配阶段，采用链路的资源碎片感知方法为可调度请求选择可用的频谱和时间资源窗口；当资源分配失败时，采用频谱切片准则将可调度请求切分为多个子带宽请求，以增加可调度请求频谱分配成功的概率，提高频谱时间碎片的利用率。仿真结果表明，所提算法可改善网络的带宽阻塞率和提高网络的频谱利用率。关键词：弹性光网络；频谱切片；可调度请求；资源分配；带宽阻塞率中图分类号：文献标志码：文章编号：（），（，；，）：，（），：；引 言近年来，视频会议、在线学习和云存储等多样化带宽需求的新兴互联网应用的兴起，正悄然改变着人们的生活方式。同时，大量的数据中心应用程序，如云计算、网格计算等用于数据存储和转发服务成为光网络中互联网协议（，）流量爆炸性增长的主要驱动因素。为了确保服务质量，这些应用程序以具有确定开始时间和结束时间特性的可调度请求（，）传输耐延迟的服务，成为光网络中 流量的重要组成部分。为了满足这些多样化新兴业务的灵活带宽需求，弹性光网络（，）技术的提出解决了传统的波分复用由于其固定的频谱栅格特性而造成的频谱浪费的问题，使弹性光网络成为极具前景的新兴光骨干网技术。技术带来了灵活的资源分配和高效的频谱利用率，但由于连接请求动态建立和释放光路所引发的频谱时间资源碎片问题影响了 频谱利用率的提高。同时，可调度请求的时间特性使 的频谱时间碎片问题更加严重，为了减少频谱时间的资源碎片率，设计有效的路由频谱分配（，）算法是提高弹性光网络资源利用率的重要手段。解决频谱碎片问题的方法主要有碎片整理和碎片感知资源分配方法。碎片整理是对当前已占用的频谱资源重新配置，大多数碎片整理方法可以分为主动型和被动型。在主动型碎片整理策略中，不考虑网络连接是否存在阻塞，在一定时间周期后定期进行频谱碎片整理操作，其主要目标是优化整个网络的频谱资源；在被动型碎片整理策略中，需要设计一定碎片整理触发条件，如基于业务连接阻塞触发的频谱碎片整理方法，即当前频谱资源下无法为连接请求提供足够的资源。碎片感知资源分配方法是在连接请求到来前根据碎片度量公式对当前频谱资源占用情况进行预分配，以便为后续连接请求保留尽可能多的频谱资源。文献提出了一种多路径碎片感知路由频谱分配算法，该算法定义了频域的频谱资源块，采用碎片感知方法为每个连接请求预先选择产生频谱碎片较小的频谱资源块，其目的是改善阻塞率性能，但当路由可用频谱资源无法满足请求所需带宽时，该请求直接被阻塞，频谱利用率较低。在 中，考虑交换节点端口数据速率与光纤链路上频谱资源可用情况，在端口配置频谱切片机也可以在频域一定程度上松弛频谱分配的连续性约束，减少频谱碎片的产生，但在节点中配置频谱切片机技术复杂，成本代价昂贵。文献提出了基于三级频谱切片交换节点架构的路由频谱分配算法，但是在频谱资源分配策略上对于频谱切片机的切片准则没有进行准确的划分，且仿真网络架构单一，在实际网络拓扑中可拓展性不强。对于确定开始时间和结束时间特性的可调度请求已有文献进行了频谱时间资源分配算法研究。文献提出混合可调度请求和即时请求的路由频谱和时间分配算法，能对频谱时间资源进行专有分区，将请求划分为不同的频谱资源区域和持续时间资源区域，但对于具有开始时间滑动窗口的可调度请求难以满足其时间灵活性；文献提出一个流量均衡二维频谱时间路由频谱分配（，）算法，将可调度请求时域分布视为具有周期特性，在一个周期内时域被分为工作时间和非工作时间，进行时域滑动和位移，在频谱时间 个维度达到流量均衡，但是工作时间和非工作时间窗口划分具有地域特殊性；文献提出空时频最小化串扰的路由频谱纤芯和时间分配算法，并提出针对单芯光纤未考虑芯间串扰的最小资源消耗的路由频谱和时间分配（，）算法，该算法根据可调度请求的所需带宽和持续时间，划分频谱资源和时间资源窗口，减少频谱时间资源的消耗，但该算法未考虑在节点配置频谱切片机，不能充分利用频谱时间的碎片资源实现业务的传输。结合可调度请求的时间特性和大带宽的需求，对弹性光网络中同时优化光节点结构和频谱时间第 期 刘焕淋，等：基于频谱切片的弹性光网络中可调度请求资源分配算法资源碎片的研究较少，尤其是在动态业务场景下，更加灵活的请求分布增加了资源分配的难度，传统静态业务模型和资源分配算法也不再适用。因此，论文提出一个基于频谱切片的可调度请求路由频谱和时间分配（，）算法。在路由选择阶段，基于 条最短路径（，）算法筛选出候选路径集合，并根据综合情况考虑路径长度、路径上碎片率和节点可用频谱切片机数量的路径权重值对候选路径集合排序；在资源分配阶段，采用链路碎片感知方法为可调度请求选择可用的频谱时间资源窗口；当资源分配失败时，使用频谱切片准则将原可调度请求从源节点到目的节点切分为多个带宽子部分，提高请求成功传输概率的同时将分配资源产生的频谱时间碎片最小化，提升频谱利用率，降低业务的带宽阻塞率。系统模型 基于频谱切片的 节点架构弹性光网络中基于频谱切片的节点架构如图 所示，包括 个模块：频谱选择开关（，）、光交换模块（）和频谱切片机（）。图 基于频谱切片的节点架构 与输入端口和输出端口分别连接，并根据 控制器的决定为每个频谱切片器选择频率梳。个频谱切片器以节点共享的方式与光交换模块连接，形成共享反馈型频谱切片模块。在节点配置频谱切片机，当资源分配失败时，将原可调度请求进行频谱切分，从而放松频谱连续性的约束。业务模型设网络拓扑结构为（，），其中，和 分别表示节点集合和链路集合，为每条光纤链路所包含的频隙集合；可调度请求表示为（，），其中，分别表示可调度请求 的源目的节点对，为可调度请求带宽需求，分别表示可调度请求的开始时间、持续时间和结束时间。根据可调度请求源目的节点对，使用 算法得出请求候选路径集合，以及业务带宽需求，计算出请求所需频隙数量，即|（）（）式中：表示请求带宽需求；为每频隙带宽，大小为 ；为调制格式对应的调制等级；为保护频隙数。路由频谱分配受频谱连续性约束，限制请求在路由传输过程中分配的频隙必须是连续的。由（）式计算出的 和搜寻候选路由可用的频谱资源，得到候选频谱资源窗口（）集合，如图 所示。图 候选频谱资源窗口示意图 可调度请求在传输过程中时域分配的时隙必须是连续的，且等于请求持续时间，根据可调度请求的开始时间 和结束时间，搜寻候选路由链路可用的时间资源，得到可用候选时间资源窗口（）集合，如图 所示。图 候选时间资源窗口示意图 在频谱和时间资源分配阶段，根据图 和图 重 庆 邮 电 大 学 学 报（自然科学版）第 卷得到的候选频谱时间资源窗口作为可调度请求的候选资源窗口。算法本文基于频谱切片的 节点架构，根据可调度请求，资源分配可分为 个阶段：当可用资源充足时，在路由选择阶段采用 算法选择 条候选路径；在频谱时间分配阶段，采用链路资源碎片感知方法为可调度请求选择路径碎片率最小值对应的频谱时间资源窗口；当资源分配失败时，在路由选择阶段，设计综合考虑路径长度、路径的资源碎片率和节点配置的可用切片机数目的路径权重值计算公式，并根据路径权重值降序排列原 条候选路径，存入新的候选路径集合；在频谱时间分配阶段，使用频谱切片准则将原可调度请求切分为多个子带宽请求，增加可调度请求频谱分配成功的概率，提高资源碎片的利用率。本文设计的综合考虑路径长度、路径的资源碎片率和节点配置的可用切片机数目的路径权重值计算方法为 （）（）式中：表示候选路径 的路径权重值；，分别为离差标准化后的路径长度，归一化路径碎片率 和可用频谱切片机数目 的权重系数，且。本文通过试错法，设定提高频谱时间碎片利用率为目标进行不断试验和消除误差，确定，的取值。候选路径 的资源碎片率的计算公式为，（）（）式中，表示将业务分配在候选路径 的频谱时间资源窗口，的资源碎片率；表示候选路径 的资源碎片的最大值。，表示为，|（）（）式中：表示候选路径 的空闲频谱块数目；，表示第 个空闲频谱资源窗口所包含的频隙数。表示为|（）（）式中，为包含频隙数。最大路径碎片率示意图如图 所示，即候选路径 包含 个频隙的资源碎片率 的最大值。图 最大路径碎片率示意图 若在当前路径 中没有满足可调度请求所需的频隙，即频谱分配失败，则采用频谱切片准则，将原请求所需带宽切片为多个子带宽请求，增加可调度请求频谱分配成功的概率，提高网络的频谱时间资源碎片的利用率。其中，频谱切片准则的终止条件表示为 ，（）（）式表示业务依次从候选路径的频谱碎片集合中选择多个空闲频谱资源窗口，当 个空闲频谱窗口之和大于等于可调度请求所需的频隙数目，则结束频谱切片操作。此目的是在满足请求频谱资源分配的基础上，尽可能少地使用频谱切片机。算法 算法输入：网络拓扑（，），可调度请求（，）；输出：输出业务传输的路由，频谱时间资源窗口和更新可用切片机数量。步骤 计算网络拓扑结构（，）中节点度数的平均值，记为，为每个节点配置数目为 的频谱切片机，转步骤。步骤 采用 算法为业务 选择 条候选路径，利用（）式计算业务所需频隙，得到业务 的候选频谱时间资源窗口集合，；根据（）式，计算 条候选路径的路径权重值，并降序排列存入候选路径集合，转步骤。步骤 依次判断候选路径 是否有满足可调度请求 所需的连续空闲频谱时间资源窗口，若满足，转步骤；否则，执行步骤。步骤 采用频谱切片准则为业务选择频谱时间资源窗口：步骤：检查候选路径 的频谱占用情况，将路径中空闲频谱资源窗口所包含的频隙数从大到小依次降序排列在集合，中，转步骤；步骤：根据可调度请求所需频隙数，依次从集合，中选择切片的频谱窗口，直至切片频谱窗口总和满足（）式，转步骤；步骤：根据（）式计算频谱切分后候选路径 的资源碎片率，若有资源碎片率相同的多个候选频谱资源窗口，则使用首次命中（，）频谱分配策略，为可调度请求分配频谱窗口和满足业务时间需求时间窗口，转步骤。步骤 根据候选路径 频谱时间资源占用情况，利用（）第 期 刘焕淋，等：基于频谱切片的弹性光网络中可调度请求资源分配算法式计算路径 上不同频谱时间资源窗口的资源碎片率，为业务选择，值最小的频谱时间资源窗口，转步骤。步骤 若路径 上存在多个频谱时间资源窗口具有相同的最小，值，则使用首次命中（，）频谱分配策略，为可调度请求分配频谱和时间窗口资源，转步骤。步骤 输出业务选择的路由、频谱时间资源窗口，更新节点的可用切片机数量。算法示例如图 所示。图 为网络拓扑结构（，），节点集合 中的节点数目为，链路集合 中的链路数目为，每链路包含频隙数为 ，时隙数为 ；网络拓扑中节点间数值表示路径长度值，每个节点配置 个频谱切片机，为简单起见，设候选路径 ；可调度请求（，）和（，）。在图 中，根据（）式计算请求 和 所需频隙数分别为 和 ；由 算法得到请求的候选路径为，图 表示候选路径 的频谱时间资源占用情况。根据 算法，首先根据链路的频谱时间占用情况，发现候选路径 没有满足请求所需的空闲频谱时间资源窗口，若不使用频谱切片准则为业务分配资源，则业务将被阻塞；若执行 算法的频谱切片准则分配资源，对候选路由路径 从源节点到目的节点上采用频谱切片准则；将候选路径 的空闲频谱时间资源窗口从大到小排序在集合（，），（，），（，）中；利用（）式，节点 到节点 分别使用一个频谱切片机，将原可调度请求 切分为 个频谱时间窗口，即频谱时间资源窗口（，），