一种光网络中基于业务持续时间调度的节能路由方法

技术领域

本发明属于光纤通信技术领域，涉及一种光网络中基于业务持续时间调度 的节能路由方法。

背景技术

面对资源减少和全球气候变化的压力，节能减排成为全世界的关注焦点。 信息通信技术(ICT)行业是全球第五大耗能行业，在未来几年ICT能耗将以每年 5％的幅度递增。倡导高效、节能、环保的通信服务，推动ICT产业可持续发展 已刻不容缓。

为了减少网络的传输能耗，研究人员基于IP over WDM网络提出了光旁路 和业务疏导技术方法。光旁路的思想是被转换成光信号的业务全部在光域中进 行传输，旁路所有中间节点的电层路由器，从而减少对电层路由器的使用以达 到节能的效果。业务疏导则是在一个网络，将多个低速业务通过建立一条光路 进行复用传输，提高光路的带宽利用率。

光旁路能有效节省路由器的端口占用数量，但会导致波长通道的带宽利用 率降低，导致网络拥塞的增加；业务疏导解决了光旁路的带宽碎片问题，但由 于业务疏导需要利用中间节点的电层路由器，所以势必会增加网络端口占用数 目和网络传输能耗。随着电子商务、云计算的兴起，如何通过通信网络将数量 众多的服务器和存储中心进行互联，在实现海量信息数据的存储和高效处理的 同时对不同粒度的用户带宽需求和时隙分配进行灵活调度，成为数据中心实现 光互联的主要挑战。与立即分配(Immediate Reservation)业务相比，带宽预留型 业务的业务需求会在业务开始之前预约，即业务到达时间先于业务开始时间， 且业务的持续时间已知，服务提供商可以提前为业务预留足够的资源。如何合 理利用光旁路与业务疏导技术在保证网络阻塞率足够低的前提下，基于带宽预 留型业务的业务持续时间对业务带宽和时隙分配进行灵活调度，从而降低网络 传输能耗是十分重要的。

发明内容

针对以上现有技术中的不足，本发明的目的在于提供一种降低网络的阻塞 率、降低网络传输能耗的节能路由方法，本发明的技术方案如下：1、一种光网 络中基于业务持续时间调度的节能路由方法，其包括以下步骤：

101、根据光网络当前的空闲可用资源建立一个疏导辅助图，所述疏导辅助 图包括底层网络物理拓扑图及W层独立的波长分层图，所述底层网络物理拓扑 图中包括有若干个待传输业务的路径，所述疏导辅助图建立完成以后，光网络 中的调度器设置固定的单位时隙T，并根据待传输业务的传输开始时刻t_s及结束 时刻t_e，根据计算式m＝(t_e–t_s)/T计算出每个待传输业务传输所需的单位时隙数m， 并对时隙进行顺序编号1、2、3…v,所述v为正整数；

102、采用最短路径算法为步骤101中所述底层网络物理拓扑图中的待传输 业务计算出K条链路分离的备选传输路径，所述每条备选传输路径具有调度权 值S，并根据待传输业务的开始时隙编号v从小到大顺序排列为链表Q；

103、判断链表Q是否为空，若是，则跳转至步骤108，否则，转步骤104；

104、光网络的调度器依次从链表Q中取出待传输业务Ⅰ，光网络的调度器 选择调度权值S最大的备选传输路径作为待传输业务Ⅰ的传输路径，调度权值S 对应的时隙t即为业务传输时隙；

105、在步骤101中建立的疏导辅助图中的W层独立的波长分层图中逐层 查找是否存在与步骤104中已选择的调度权值S最大的备选传输路径及时隙相 同的已建光路，如果不存在这样的光路或者光路无可用带宽，则在带宽足够的 波长分层图中新建一条光路并标记该光路的传输时隙为业务传输时隙，如果该 光路存在且可用带宽资源足够，则此该光路的传输时隙称为带宽充足传输时隙； 如果光路存在但可用带宽资源不足，则记录下此光路的可用带宽资源信息，且 此时隙为业务带宽不足时隙；

106、计算步骤105中带宽充足时隙与带宽不足时隙可传输的业务量是否不 小于待传输业务量，若是，则光网络的调度器为业务已经找到足够的传输时隙 和传输路径，转步骤107，否则，跳转步骤104继续为此业务选择传输时隙和路 径；

107、更新步骤101中的疏导辅助图：即在各个传输时隙t内的业务传输路 径对应光路上减去光网络的调度器为业务所分配的传输带宽，并从链表Q中删 去该待传输业务；

108、当链表Q为空时，光网络的调度器在步骤101中建立的疏导辅助图中 查找只传输一个待传输业务的光路，并确定该光路所待传输业务Ⅱ的传输时隙 编号v，按照传输开始时隙编号从小到大顺序排列为链表L；

109、判断链表L是否为空，若是，算法结束，否则，转步骤110；

110、光网络的调度器依次从链表L中取出存储的业务Ⅱ，并确定业务Ⅱ的 带宽充足时隙，计算带宽充足时隙光路可用带宽总和是否不小于业务Ⅱ的传输 带宽，若是，则增大此时隙的传输带宽，拆除此只传输一个业务的光路，并在 疏导辅助图的带宽充足时隙对应光路上减去上面增大的传输带宽，在链表L中 删除此业务Ⅱ，转步骤109，否则，直接在链表L中删除此业务Ⅱ，转步骤109。

进一步的，步骤101中所述疏导辅助图建立的步骤为：根据光网络中每根 光纤中复用的波长数W将网络物理拓扑映射为由W个波长分层图和底层网络物 理拓扑图组成的疏导辅助图，整个疏导辅助图共有W+1层，底层为网络物理拓 扑图，上W层对应于W个独立的波长分层图。

进一步的，步骤102中所述若干个备选传输路径调度权值S构成待传输业 务的调度权值矩阵即为：$S=\left(\begin{array}{cccc}{S}_{1,(v+1)}& S_{1,(v+2)}& ......& S_{1,(v+m)}\\ S_{2,(v+1)}& S_{2,(v+2)}& ......& S_{2,(v+m)}\\ ......& ......& S_{i,(v+j)}& ......\\ S_{k,(v+1)}& S_{k,(v+2)}& ......& S_{k,(v+m)}\end{array}\right),$S_i,(v+j)表示了业务 的第i条备选传输路径在时隙(v+j)被待传输业务选作业务传输路径的次数，S_i,(v+j)初始值为0，当有业务在时隙(v+j)选择此路径为备选传输路径，那么S_i,(v+j)的值 加1。

本发明的优点及有益效果如下：

本发明方法通过统计疏导辅助图中所有备选传输路径在不同时隙内可能被 待传输业务选作业务传输路径的次数，为业务选择合适的传输路径、传输时隙 以建立最小能耗光路，并且调整业务带宽充足时隙的传输带宽使业务充分利用 已建光路的剩余带宽以降低网络的阻塞率和传输能耗。

附图说明

图1为本发明优选实施例网络疏导辅助图的构造；

图2灵活时间调度业务时序示意图；

图3业务传输时隙、路径选择流程图；

图4带宽调整流程图；

图5业务节能路由的总流程图。

具体实施方式

下面结合附图给出一个非限定性的实施例对本发明作进一步的阐述。

参照图1-5所示，针对现有的基于业务持续时间调度方法不能最小化网络传 输能耗和传输带宽固定导致的网络阻塞率过高的问题，本发明设计了一种基于 业务持续时间调度的节能路由方法，本方法通过运用最短路径算法为业务计算 多条链路分离的路径作为传输备选路径，进而计算每条备选路径在不同时隙内 被所有业务选择的次数来确定业务的传输时隙和传输路径，并通过调整业务传 输带宽来减小网络传输能耗和阻塞率。

为了同时考虑各约束条件对业务选路的影响，在此通过构造疏导辅助图来 进行路由和带宽分配。此方法的优点是在为业务进行寻找最短路径和资源分配 时，综合考虑了各种约束条件：考虑了当前的网络波长资源使用情况，能够同 时完成新业务请求的疏导、路由和波长分配。疏导辅助图将整个网络物理拓扑 映射为W+1层分层图，其中W对应一根光纤中复用的波长数，这样就能避免业务 因波长资源分配引起的冲突竞争，最后一层是网络物理拓扑层。在网络物理拓 扑层中运用最短路径算法为业务计算出多条链路分离的最短路径，并记录下每 条传输路径经过的节点和物理链路。

调度器为每个待传输业务都计算出K条链路分离的备选传输路径后，其中K 值为网络节点平均度数取下限整数，即为待传输业务选择传输时隙、传输路径、 分配网络带宽。

本发明的核心是业务传输时隙、传输路径的选择和根据网络资源情况调整业 务的传输带宽以降低网络能耗和阻塞率。

假设业务请求为R，其中传输时间窗口开始时刻t_s、结束时刻t_e和业务持续时 间t_h需满足t_h<t_e–t_s，为保证整个传输过程在传输时间窗口内完成，即业务实际 传输开始时刻t满足t_s<＝t，且t+t_h<＝t_e；由业务请求传输带宽B，可知业务需传输 的总数据量为：D＝t_h×B。基于端口的网络能耗计算方法，可以根据网络器件能 耗设置，在我们的研究中，各器件能耗值设置为：1)核心路由器端口功率 P_r＝1000w；2)光收发器功率P_t＝43w；3)掺铒光纤放大器功率P_e＝8w。因此，可 知光路传输能耗与其使用的端口数和持续时间相关。如果能在保证满足链路带 宽约束的条件下尽可能地将业务集中在某些时隙、链路中传输，这样就能通过 最小化业务的端口使用数、光路持续时间来最小化业务的传输能耗。

整个业务传输时隙、传输路径的选择过程如下：从当前时刻开始，网络的调 度器设置一个固定长度的时间为一个单位时隙，调度器根据待传输业务的传输 开始时刻t_s、结束时刻t_e计算业务传输时间窗口需要的单位时隙数m＝(t_e–t_s)/T、业 务传输持续时隙数为n＝(t_h/T)、开始时隙编号v，则业务的调度权值矩阵即为： $S=\left(\begin{array}{cccc}{S}_{1,(v+1)}& S_{1,(v+2)}& ......& S_{1,(v+m)}\\ S_{2,(v+1)}& S_{2,(v+2)}& ......& S_{2,(v+m)}\\ ......& ......& S_{i,(v+j)}& ......\\ S_{k,(v+1)}& S_{k,(v+2)}& ......& S_{k,(v+m)}\end{array}\right),$S_i,(v+j)表示了业务的第i条备选传输路径在时 隙(v+j)被待传输业务选作业务传输路径的次数，S_i,(v+j)初始值为0，当有业务在时 隙(v+j)选择此路径为备选传输路径，那么S_i,(v+j)的值加1。调度器将所有待传输业 务按照传输时间窗口开始时隙编号v从小到大排列为链表Q，并依次从链表Q中取 出待传输业务为其选择传输时隙、传输路径。调度器选择调度权值最大的备选 路径作为业务的传输路径，如调度器选择调度权值矩阵中最大的调度权值S_i,(v+j) 对应的第i条备选路径作为业务的传输路径，调度权值S_i,(v+j)对应的时隙(v+j)即为 业务的一个传输时隙，业务在一个传输时隙内只能选择一条传输路径，因而时 隙(v+j)内的其他备选传输路径都不能再被选作传输路径，即时隙为(v+j)的调度 权值都置为0；确定传输路径、时隙后，调度器在疏导辅助图中，从上层到下层 的各波长分层图中逐层查找是否存在与已选择的传输路径、时隙相同的已建光 路，如果不存在这样的光路或者光路无可用带宽，则从带宽足够的波长分层图 中新建一条光路并标记光路的传输时隙为所选传输时隙，如果该光路存在且可 用带宽资源足够，此类时隙称为带宽充足时隙，如果光路存在但可用带宽资源 不足，则记录下此光路的可用带宽资源信息，且此类时隙称为业务带宽不足时 隙；之后调度器会判断为待传输业务分配的传输时隙、传输路径是否满足业务 的传输要求：如果业务带宽充足时隙数记为符号a，当满足B×(n–a)<＝∑B_i时， 表明调度器为待传输业务分配的传输时隙、传输路径足够让业务在传输时间窗 口内传输其所需传输数据量，其中∑B_i为记录下的所有带宽不足时隙的光路可 用带宽总和，为保证整个传输过程满足传输时间窗口约束条件，∑B_i所对应的 时隙总数即带宽不足时隙总数应不大于m–a；此时从链表Q中删除此业务并更新 疏导辅助图：在各个传输时隙内的业务传输路径对应光路上减去调度器为业务 所分配的传输带宽，如果不满足，则调度器继续为此业务选择传输路径。对其 它待传输业务，重复上述业务传输路径、传输时隙选择和分配网络带宽过程， 直到Q表为空。

由上述选择过程可知，调度器根据业务调度权值确定业务的传输时隙和传输 路径。确定业务的传输路径后需在疏导辅助图各波长分层图中根据网络链路可 用带宽为业务分配传输带宽。业务优先选择利用已建光路的可用带宽，当已建 光路无可用带宽后选择新建光路，这样可能会出现某些传输路径对应的多条已 建光路无可用带宽但某条新建的光路只传输一个业务的情况。假设S_e,h＝10，即 有10个业务选择S_e,h对应的时隙h、路径e作为业务的传输时隙、路径。调度器在 辅助图的波长层为第1个业务分配传输带宽时，疏导辅助图中没有与路径e物理 传输路径、传输时隙h相同的光路，那么需为第1个业务新建一条传输路径与e相 同的光路，后面在时隙h选择路径e为传输路径的业务可利用此光路的可用带宽， 直到有业务在时隙h选择选择路径e为传输路径而已建光路的可用带宽为零，调 度器则在新的带宽资源足够的波长分层图中为业务新建一条与上述光路传输路 径相同的光路，不断重复上述过程，直到调度器为这10个业务都成功分配了传 输带宽。假设当调度器为第10个业务分配传输带宽时，前面新建的光路无可用 带宽，调度器为就会为第10个业务新建一条光路，但是此时隙内再没有业务选 择此路径作为传输路径，这样调度器为第10个业务新建的光路就只传输一个业 务。为避免上述情况，调度器为所有待传输业务分配传输带宽后查找只传输一 个业务的光路，并确定光路所传输业务的带宽充足时隙，分析能否增大业务的 带宽充足时隙的传输带宽，若能增大此类时隙的传输带宽，则拆除此只传输一 个业务的光路，并在疏导辅助图的带宽充足时隙对应光路上减去增大的传输带 宽；否则，查找是否还存在只传输一个业务的光路。这一过程的第一步是调度 器查找只传输一个业务的光路，确定光路所传业务的传输开始时隙编号，并按 照业务开始传输时隙编号从小到大将这些业务排列成链表L。第二步是调度器依 次从L中取出待传输业务，计算分析能否通过增大业务带宽充足时隙的传输带 宽，如果能，则在辅助图中带宽充足时隙对应的光路上减去增大的那部分带宽， 并从L中删去此业务；如果不能，则直接从L中删去此业务。调度器依次在链表L 中取出下一个业务进行计算，直到L为空。

下面将结合附图，对本发明进行详细的描述。

附图1表示了疏导辅助图的构造，为了更好为业务选择合适的传输路径、时 隙和分析网络资源情况，根据每根光纤中复用的波长数W将网络物理拓扑映射为 W个波长分层图，此分层方法能保证每个波长分层图资源分配的独立性。整个疏 导辅助图共W+1层，底层为网络物理拓扑层，表示了节点、链路之间的连接情 况，调度器在此层中使用最短路径算法为业务计算出K条链路分离的备选传输路 径，K为网络平均节点度数取下限整数。每个待传输业务都对应一个调度权值矩 阵$S=\left(\begin{array}{cccc}{S}_{1,(v+1)}& S_{1,(v+2)}& ......& S_{1,(v+m)}\\ S_{2,(v+1)}& S_{2,(v+2)}& ......& S_{2,(v+m)}\\ ......& ......& S_{i,(v+j)}& ......\\ S_{k,(v+1)}& S_{k,(v+2)}& ......& S_{k,(v+m)}\end{array}\right),$S_i,(v+j)表示了业务的第i条备选传输路径在 时隙(v+j)被待传输业务选作业务传输路径的次数，S_i,(v+j)初始值为0，当有业务在 时隙(v+j)选择此路径为备选传输路径，那么S_i,(v+j)的值加1。网络基于光旁路技术 利用相应的波长链路为业务建立传输光路后，即在辅助图波长层删除所用波长 链路并建立源节点到目的节点的光路，同时在光路上减去分配的传输带宽并标 注光路的传输时隙。

灵活时间调度业务是带宽预留型业务的一种，其业务属性与一般的业务有很 大差别，附图2就其独特的业务属性进行说明：对于业务请求R，传输时间窗口 开始时刻t_s、结束时刻t_e和业务持续时间t_h需满足t_h<t_e–t_s。调度器需保证业务整 个传输过程在传输时间窗口(t_s，t_e)内完成，即业务实际传输开始时刻t满足t_s<＝t， 且t+t_h<＝t_e；B为业务请求传输带宽，可知业务需传输的总数据量为：D＝t_h×B， 调度器根据待传输业务的传输开始时刻t_s、结束时刻t_e计算业务传输时间窗口需 要的单位时隙数m＝(t_e–t_s)/T、业务传输持续时隙数为n＝t_h/T、开始时隙编号v，其 中T为时隙的大小。通过划分时隙将连续的业务传输过程划分为多个部分独立传 输，这样就能更精细的对业务的传输过程进行控制。

下面将结合附图3对本发明的核心部分—业务传输路径选择流程进行详细的 说明。具体流程可分为下面几个步骤：

Step1:根据每根光纤中复用的波长数W将网络物理拓扑映射为W个波长分 层图的疏导辅助图。整个疏导辅助图共有W+1层，底层为网络物理拓扑图，上W 层对应于W个独立的波长分层图，在疏导辅助图底层使用最短路径算法为每个待 传输业务计算K条链路分离的备选传输路径，K为网络节点平均度数取下限整数。 调度器统计疏导辅助图中所有备选传输路径在不同时隙内可能被待传输业务选 作业务传输路径的次数，此值将作为备选传输路径在对应时隙内的调度权值。 从当前时刻开始，网络的调度器设置一个固定长度的时间为一个单位时隙，调 度器根据待传输业务的传输开始时刻、结束时刻计算业务传输需要的单位时隙 数和开始时隙编号，并根据调度器统计的调度权值建立业务的调度权值矩阵： $S=\left(\begin{array}{cccc}{S}_{1,(v+1)}& S_{1,(v+2)}& ......& S_{1,(v+m)}\\ S_{2,(v+1)}& S_{2,(v+2)}& ......& S_{2,(v+m)}\\ ......& ......& S_{i,(v+j)}& ......\\ S_{k,(v+1)}& S_{k,(v+2)}& ......& S_{k,(v+m)}\end{array}\right).$按照业务的开始时隙编号v从小到大的顺序 将待传输业务排列成链表Q。

Step2：检查链表Q是否为空，若是，则算法结束；否则，转Step3。

Step3：调度器从链表Q中取出待传输业务请求。

Step4：调度器选择调度权值最大的备选传输路径作为业务的传输路径。如： 调度器选择最大调度权值S_i,(v+j)对应的第i条备选路径作为传输路径，其中调度权 值对应的时隙(v+j)即为业务的一个传输时隙，而且这一时隙的所有其他备选传 输路径不能再次被此业务选作传输路径，即将这一时隙内的其他备选传输路径 的调度权值都赋值0。

Step5：在疏导辅导图中查看网络能否为该传输路径分配足够的带宽。在疏 导辅助图中，从上层到下层的各波长分层图中逐层查找是否存在与已选择的传 输路径、时隙相同的已建光路，如果不存在这样的光路或者光路无可用带宽， 则在带宽足够的波长分层图中新建一条光路并标记光路的传输时隙为调度权值 对应的传输时隙，如果该光路存在且可用带宽资源足够，此类时隙称为业务带 宽充足时隙；如果光路存在但可用带宽资源不足，则记录下此光路的可用带宽 资源信息，且此时隙称为业务带宽不足时隙。

Step6：判断此待传输业务传输路径、时隙选择是否完成。调度器计算为待 传输业务分配的传输时隙、传输路径是否足够让业务在传输时间窗口内传输其 所需传输数据量，若是，转Step7，否则，转Step4，继续为此业务选择传输时 隙、路径。在Step1中提到调度器根据待传输业务的传输开始时刻t_s、结束时刻t_e计算业务传输时间窗口需要的单位时隙数m＝(t_e–t_s)/T、业务传输持续时隙数为 n＝(t_h/T)、开始时隙编号。如果待传输业务带宽充足传输时隙总数为a，当满足 B×(n-a)<＝∑B_i时，业务传输时隙、路径选择完成，其中∑B_i为调度器记录下的 带宽不足时隙对应光路的可用带宽总和，为保证整个传输过程满足传输时间窗 口约束条件，∑B_i所对应的带宽不足时隙总数应不大于m–a。

Step7：更新疏导辅助图。如果需要为业务新建一条光路，删去新建光路波 长分层图中相应的波长链路并建立一条源节点到目的节点的光路，并在光路上 减去调度器为业务分配的传输带宽并标记光路的传输时隙；如果可以利用已建 光路的可用带宽，则直接在辅助图所选已建光路上减去调度器为业务分配的传 输带宽，并从链表Q中删除此待传输业务，转Step2。

调度器为所有待传输业务分配的传输时隙、传输路径都足够让业务在传输时 间窗口内传输其所需传输数据量后，整个传输时隙、路径的选择过程就结束了， 此时链表Q为空。

调度器通过选择调度权值最大的备选传输路径促使更多的业务请求在相同 的时隙、利用相同的路径传输数据，减小了网络传输能耗，而通过减小带宽不 足时隙的请求带宽能更大程度上利用已建光路的可用带宽，虽然增大了业务的 传输持续时间，但这也使业务疏导技术与光旁路技术更好地结合，不仅减了网 络传输能耗，也减小了网络的阻塞率。分析上述选择过程可知，传输路径对应 于多个不同波长的光路，业务优先选择利用已建光路的可用带宽，仅当已建光 路无可用带宽后选择新建光路，这样可能会出现某些传输路径对应的多条已建 光路无可用带宽但新建的某条光路只传输一个业务的情况。为避免上述情况， 调度器在为所有待传输业务分配足够的传输时隙、路径后查找只传输一个业务 的光路，并确定光路所传输业务的带宽充足时隙，若能增大此类时隙的传输带 宽，则拆除此只传输一个业务的光路，并在疏导辅助图的带宽充足时隙对应光 路上减去增大的传输带宽；否则，查找是否还存在只传输一个业务的光路。其 主要流程附图4说明如下：

Step1：将只传输一个业务的光路查找出来，记录下此光路所传输业务请求 的信息，例如业务分配的带宽充足传输时隙数、传输光路剩余带宽，业务的传 输带宽等，并按照业务传输开始时隙编号从小到大顺序将业务排列成链表L。

Step2：链表L是否为空，如果不为空，转Step3，否则，算法结束。

Step3：从链表L中取出业务。

Step4：计算业务带宽充足时隙光路可用带宽是否满足带宽调整条件。计算 业务所有带宽充足时隙光路可用带宽总和是否大于业务的传输带宽B，若是，转 Step5，否则，从链表L中删除此业务，转Step2。

Step5：在疏导辅助图上更新业务带宽充足时隙的传输带宽。如果所有带宽 充足时隙光路可用带宽最小值不小于业务传输带宽B除以带宽充足时隙数a的 值：B/a，则每条带宽充足时隙对应光路可用带宽都减去B/a，即每个带宽充足时 隙光路增大的传输带宽一致；如果小于，则从可用带宽最小的带宽充足时隙对 应光路开始，依次减去光路可用带宽，直到减去的带宽总和等于业务传输所需 带宽。

此过程通过增大带宽充足时隙的传输带宽，拆除只传输一个业务的光路， 减小了网络中传输业务的光路数，促使网络更好地利用已建光路的可用带宽， 减小了网络端口和波长的使用量，进而在减小网络能耗的同时提高了链路利用 率。

本方法通过划分时隙，在不同时隙内计算网络路径可能作为业务备选传输 路径的次数作为路径的调度权值，待传输业务选择调度权值最大的路径作为传 输路径，为业务建立最小能耗光旁路，并通过调整业务传输带宽在保证业务成 功传输的前提下减小网络的传输能耗和阻塞率。

以上这些实施例应理解为仅用于说明本发明而不用于限制本发明的保护范 围。在阅读了本发明的记载的内容之后，技术人员可以对本发明作各种改动或 修改，这些等效变化和修饰同样落入本发明方法权利要求所限定的范围。