一种混合交换网络中基于业务持续时间的调度方法

摘要

一种混合交换网络中基于业务持续时间的调度方法，步骤如下：1)获取需要进行路径资源分配的网络物理拓扑G，该网络物理拓扑G对应的混合网络包括N个节点；2)收集网络物理拓扑G对应的混合网络的资源状态信息，构建异构链路状态表；3)按异构链路的不同特征，构建分层图模型；4)为网络中的业务请求矩阵D中每一业务进行编号，根据业务请求矩阵D中各个业务的业务特征进行分类；5)根据业务不同类型，缩小路径查询范围，进行基于业务持续时间的资源调度。

说明书

技术领域

本发明涉及一种混合交换网络中基于业务持续时间的调度方法，属于数据通信传输技术。

背景技术

目前，常用的网络调度方法包括分配固定时隙的调度算法、基于优先级队列的调度算法。分配时隙的调度算法通过建立时隙表，为每个业务分配固定的时隙，存在整网的同步控制复杂，对突发业务的适应能力弱等问题；基于优先级队列的调度算法按照一定的优先级规则，将不同输入业务流分别暂存到相应的队列以进行调度和服务，能快速解决电业务的调度问题，但难以适用于缓存困难、大颗粒度的光业务。而现有混合交换网络资源调度方法有采用层叠/分离式的调度方法和联合调度方法，层叠/分离式的资源调度方法将多层多域链路资源分别采用不同的调度方式，没有将层间域间的疏导链路资源进行统一考虑，层间域间的链路资源缺乏必要的协调。联合调度方法核心思想是交换网络中各层各域都不是单独设计的，通过综合考虑相邻层或相邻域之间的资源参数，将各链路资源通过一个跨层跨域决策模块进行整体资源分配，通过将分散在各层的资源参数进行协调融合，但链路资源的多样造成该方法在技术上实现复杂，资源调度方法复杂等问题。

“无缝演化融合光交换节点中的控制机制研究及实现”提出基于流速和缓存占用的流量需求估计方法，利用流量映射完成分组与电路的流量调配，只在电域完成时隙分配。

“业务持续时间的带宽可变节能调度算法”通过业务时续时间列出所有满足业务传输需求的路径时隙资源，通过算法得到能耗最小时隙路径。

“异构无线网络中用户分配和资源分配研究”提出一种基于未来网络负载状态预测的负载调度方案，通过预测未来调度间隙内各个网络的空载持续时间，给出最优调度负载量。。

“一种引入异构用户业务执行系数的动态资源调度方法”，专利号：CN200910030780.3。对异构用户业务进行排序，完成多个不同业务需求用户时间和频谱资源的动态调度。

“一种灵活调整预留型业务传输带宽的光网络节能路由方法”，专利号：CN201510642513.7。根据光路上业务持续时间和带宽使用率情况，重路由光路上只有一个业务的请求到可以与其它业务重合传输时隙的光路上，完成多路业务的疏导到一条光路上。

“一种光网络中基于业务持续时间调度的节能路由方法”，专利号：CN201410288798.4。对光网络中的调度器设置固定的单位时隙，根据业务起始结束时间计算出每个待传输业务传输所需的单位时隙数，为待传输业务选择传输时隙。

发明内容

本发明所要解决的技术问题是：克服现有手段的不足，提供一种混合交换网络中基于业务持续时间的调度方法，该方法考虑业务的持续时间、传输速率等特征，进行业务区分，收集异构链路特征及链路上承载业务的持续时间、缓存排队时间等信息以建立2D的链路资源状态表，在时间、速率/频率两个维度上将不同封装、不同粒度的业务需求与异构链路对应起来，通过对排队时间、保护时间和业务持续时间的更新和计算，进行时间片的统筹管理，完成交换路径的选择，实现交换资源的统一调度。

本发明的技术方案是：一种混合交换网络中基于业务持续时间的调度方法，步骤如下：

(1)获取需要进行路径资源分配的网络物理拓扑G，该网络物理拓扑G对应的混合网络包括N个节点，并分别记为V₁、V₂、V₃、V₄、…、V_N，N为正整数；所述节点V_i具备层间域间疏导能力，i＝1，2....N；

(2)收集网络物理拓扑G对应的混合网络的资源状态信息，构建异构链路状态表；

(3)按异构链路的不同特征，构建分层图模型LG(V^*,E^*)，其中V^*表示节点集合，E^*表示路径集合；

(4)为网络中的业务请求矩阵D中每一业务进行编号1，2，3，…，|D|；其中|D|为交换网络中业务总量，D＝D₁，D₂，D₂，…，D_|D|}，根据业务请求矩阵D中各个业务的业务特征进行分类；

(5)根据业务不同类型，缩小路径查询范围，进行基于业务持续时间的资源调度。

所述步骤2)构建异构链路状态表的具体方法为：

(2a)收集异构链路的链路类型、链路传输速率、链路波长特征，以及链路上承载业务的持续时间、交换单元输入输出缓存排队时间；

(2b)将步骤(2a)中收集到的链路信息分为电传输链路、光传输链路、光电转换链路、波长转换链路四大类，每一类再根据链路传输速率、链路波长、链路上承载业务的持续时间t_i、交换单元输入输出缓存排队时间η_j进行细分，建立交换链路资源状态表。

所述步骤(4)中根据业务请求矩阵D中各个业务的业务特征进行分类的具体方式如下：

当业务持续时间t_D＞T1时，为长时业务流，当业务持续时间T2≤t_D≤T1时，为一般业务流，当业务持续时间t_D＜T2时，为短时业务流；其中T1和T2为设定的两个时间常量阈值，且T1＞T2。

所述步骤(5)中基于业务持续时间的资源调度的具体方式如下：

(5a)删除层间虚拟路径，更新LG(V^*,E^*)，如果请求为长时业务和一般业务，执行步骤(5b)；如果请求为短时业务请求，执行步骤(5d)；

(5b)根据业务的持续时间，与异构链路状态表中的持续时间进行匹配，链路h_i的占用资源t_i满足t_i＜T_a，其中T_a为业务请求的最大等待时间，在分层图中删除不符合持续时间要求的链路h_o，更新LG(V^*,E^*)令E^*＝E^*-h_o；

(5c)在LG(V^*,E^*)分层图拓扑上采用最短路径算法为业务请求寻找最短路径，若找到的路径不止一条，则随机选择一条路径，设选定的路径为p_i，更新业务请求矩阵D和异构链路状态表的t_i，令D＝D-D_i，t_i=t_i+t_D+t_b，其中t_b为业务处理的保护时间；执行步骤(5d)；若未找到路径，执行步骤(5g)；

(5d)根据业务的持续时间，与异构链路状态表中的缓存排队时间进行匹配，路径h_i的缓存排队时间η_i满足η_i＞t_D，在分层图中删除不符合要求的链路h_o，更新LG(V^*,E^*)令E^*＝E^*-h_o；

(5e)在LG(V^*,E^*)中采用最短路径算法寻找最短路径，若找到的路径不止一条，则随机选择一条路径，设选定的路径为p_i，令η_i＝η_i-t_D，D＝D-D_i，执行步骤(5h)；若未找到路径，执行步骤(5f)；

(5f)将业务放入缓存队列，汇聚为长度L的业务，计算其业务持续时间

(5g)恢复步骤(5a)中删除的层间虚拟链路，采用最短路径算法寻找最短路径，若得到的路径不止一条，则随机选择一条路径，设选定的路径为p_i，若p_i中含有光到电的转换链路p_oe，则转换后电链路上的业务持续时间其中v_oe为链路p_oe的上一条电链路速率，v_λoe为路径p_oe的下一条光链路速率，t_x为光电转换时间；若p_i中含有电到光的转换链路p_eo，则转换后电链路上的业务持续时间t_i＝t_i+t_D+t_b+t_x，若p_i中含有波长转换链路，则转换后电链路上的业务持续时间t_i＝t_i+t_D+t_b+t_z，其中t_z为光电转换时间，更新业务矩阵D＝D-D_i，执行步骤(5h)；若未找到路径，执行步骤(5j)；

(5h)基于业务持续时间的调度完成，为业务申请找到路径p_i。

(5j)基于业务持续时间的调度失败，结束。

所述最短路径算法采用Dijkstra算法。

所述路径为业务生成的路径，由交换网络中固有的多个或一个链路组成。

本发明与现有技术相比的优点在于：

(1)本发明建立2D的链路资源状态表，在时间、速率/频率两个维度上将不同封装、不同粒度的业务需求与异构链路对应起来，解决了多层资源表征方式差异巨大的问题，实现了混合交换网络多层多域链路资源的一体化表征，为光电业务提供统一的调度标准；

(2)本发明将不同封装、不同粒度的业务流在时间维度上进行统一，不但细化了光交换的颗粒度，也为电域提供了更多的交换颗粒度选择，同时可满足多种类型、多种粒度以及多种QoS需求业务的路径资源分配的要求。既可为无连接电业务提供保证服务质量的路径，又可为波长粒度的光业务提供子波长级别的路径资源分配，还可高效完成电域和光域业务的聚合疏导；

(3)本发明通过根据业务在时间、频率/速率上的不同特征，利用交换链路资源状态表，在异构链路分层图中运用最短路径算法进行路径资源查找，解决了多颗粒度的异质业务的交换路径资源快速分配问题，，降低控制复杂度，具有算法简单的优点；

(4)本发明将速率转换、波长转换及光电转换多种跨层跨域链路资源纳入考虑，便于完成交换网络资源的层间域间联合优化管理，保证资源调度的成功率，并且最大限度利用现有路径，减小新业务建立对现有业务的影响；

(5)本发明基于时间片的统筹管理来进行异质业务的调度，系统的时域控制较传统的时隙调度简单、灵活。

附图说明

图1为本发明交换网络拓扑；

图2为本发明异构链路分层图。

具体实施方式

下面结合附图对本发明的具体实施方式进行进一步的详细描述。

如图2所示，一种混合交换网络中基于业务持续时间的调度方法包括步骤如下：

(1)获取需要进行路径资源分配的的网络物理拓扑G，该网络物理拓扑G对应的混合网络包括N个节点，并分别记为V₁、V₂、V₃、V₄、…、V_N，如图1所示，N为正整数，节点V_i具备层间域间疏导能力(层间域间疏导能力为将网络中的业务进行合理的分拆、聚合、波长转换及光电转换，在各层间或域间传输)，i不大于N。所述路径指的是业务生成的路径，它由交换网络中固有的多个或一个链路组成。

(2)收集该混合交换网络的资源状态信息，构建异构链路状态表。

(2a)收集异构链路的链路类型、链路传输速率、链路波长特征，以及链路上承载业务的持续时间、交换单元输入输出缓存排队时间等信息。

(2b)将(2a)中收集到的链路信息分为电传输链路、光传输链路、光电转换链路、波长转换链路4大类，每一类再根据传输速率、波长及所在交换单元位置进行细分，建立如下的交换链路资源状态表，其中η_j为交换单元输入输出缓存排队时间。t_i为链路上承载业务的持续时间，i∈N，N为异构传输链路数量。

表1异构链路状态表

(3)根据(1)(2)得到的信息，按异构链路的不同特征，构建分层图模型LG(V^*,E^*)，V^*表示节点集合，E^*表示路径(单向)集合，分层模型的每一层是具备相同链路特征的交换单元间链路的集合，分层图的层间连线是交换单元内层间域间疏导路径资源的集合。

(4)等待业务请求：T(s_D,B_D,t_D)，设网络中的业务请求矩阵为D，为D中每一业务进行编号1，2，3，…，|D|，其中|D|为交换网络中业务总量，D＝D₁，D₂，D₂，…，D_|D|}，B_D为业务D所需带宽或速率资源，t_D为业务D持续时间，s_D为业务类型(电业务、光业务)。然后根据业务请求矩阵D中各个业务的业务特征进行分类。

步骤(4)中将业务按业务特征进行分类的具体方式如下：

设立T1和T2两个时间常量，将业务的持续时间与T1、T2进行比较，得到如下表的业务分类。

表2业务分类

业务流类型持续时间长时业务流t_D＞T1一般业务流T2≤t_D≤T1短时业务流t_D＜T2

(5)根据业务不同类型，缩小路径查询范围，进行基于业务持续时间的资源调度，当未找到符合要求的路径时，在调度中考虑跨层跨域链路。

步骤(5)中为基于业务持续时间的调度的具体方式如下：

(5a)删除层间虚拟路径，更新LG(V^*,E^*)，如果请求为长时业务和一般业务，执行步骤5b；如果请求为短时业务请求，执行步骤5d。

(5b)根据业务的持续时间，与异构链路状态表中的承载业务持续时间进行匹配，链路h_i的占用资源t_i需满足t_i＜T_a，T_a为业务请求的最大等待时间，在分层图中删除不符合要求的链路h_o，更新LG(V^*,E^*)令E^*＝E^*-h_o。

(5c)在LG(V^*,E^*)分层图拓扑上用最短路径算法(如Dijkstra算法)为其寻找最短路径，若得到的路径不止一条，则根据此业务请求的服务质量要求选择一条即可，设选定的路径为p_i，更新业务请求矩阵D和异构链路状态表的t_i，令D＝D-D_i，t_i＝t_i+t_D+t_b(t_b为业务处理的保护时间)。执行步骤(5d)，若未找到，执行步骤(5g)。

(5d)根据业务的持续时间，与异构链路状态表中的进入或离开链路的缓存排队时间进行匹配，需满足路径h_i的缓存排队时间资源为η_i(η_i＞t_D)，在分层图中删除不符合要求的链路h_o，更新LG(V^*,E^*)令E^*＝E^*-h_o。

(5e)在LG(V^*,E^*)中采用最短路径算法(如Dijkstra算法)寻找最短路径，若得到的路径不止一条，则随机选择一条即可，设选定的路径为p_i，令η_i＝η_i-t_D，D＝D-D_i，执行步骤5h。若未找到，执行步骤5f。

(5f)将业务放入缓存队列，汇聚为长度L的业务，计算其业务持续时间，

(5g)恢复步骤4中删除的层间虚拟路径，采用最短路径算法(如Dijkstra算法)寻找最短路径，若得到的路径不止一条，则随机选择一条路径，设选定的路径为p_i，若p_i中含有光到电的转换链路p_oe，则转换后电链路上的业务持续时间(v_oe为链路p_oe的上一条电链路速率，v_λoe为路径p_oe的下一条光链路速率，t_x为光电转换时间)。若p_i中含有电到光的转换链路p_eo，则转换后电链路上的业务持续时间t_i＝t_i+t_D+t_b+t_x。若p_i中含有波长转换链路p_o，则转换后电链路上的业务持续时间t_i＝t_i+t_D+t_b+t_z(t_z为光电转换时间)，最后更新业务矩阵D＝D-D_i，执行步骤(5h)。若未找到路径，执行步骤(5j)；

(5h)基于业务持续时间的调度完成。

(5j)基于业务持续时间的调度失败。

本发明说明书中未作详细描述的内容属本领域技术人员的公知技术。