CN104202111B

CN104202111B - 基于通道密度和最小间隙的触发式聚合光路重构方法

Info

Publication number: CN104202111B
Application number: CN201410465308.3A
Authority: CN
Inventors: 丁喆; 周志强; 徐展琦; 曾晓东; 马方
Original assignee: Fiberhome Telecommunication Technologies Co Ltd; Xidian University
Current assignee: Fiberhome Telecommunication Technologies Co Ltd; Xidian University
Priority date: 2014-09-12
Filing date: 2014-09-12
Publication date: 2017-04-19
Anticipated expiration: 2034-09-12
Also published as: CN104202111A

Abstract

本发明公开一种基于通道密度和最小间隙的触发式聚合光路重构方法，主要解决现有技术中无法选择最佳重构方案、只进行频谱搬移、阻塞率改善较小和频谱利用率较低的问题。其实现步骤是：1)使用迪杰斯特拉方法和首次命中方法为新到达的连接请求选路和频谱分配；2)找出与频谱分配失败的连接请求相冲突的光路；3)对每一条相冲突的光路都选择通道密度最大和最小间隙最小的备选光路进行重构；4)重构结束后再对连接请求重新分配频谱。本发明相比现有技术其阻塞率低，频谱利用率高，减轻了关键链路的负担，使得网络流量更加均衡，可用于弹性光网络中对频谱碎片的整理。

Description

基于通道密度和最小间隙的触发式聚合光路重构方法

技术领域

本发明属于通信技术领域，更进一步涉及光路重构方法，可用弹性光网络中对频谱碎片的整理。

背景技术

传统的波分多路复用WDM网络中每个波长容量固定，且相邻波长之间用保护带宽分开以确保信号质量与接收端的滤波，缺点是带宽粒度大且使用不灵活，波长间的保护带宽也会造成频谱资源的浪费，为此需要一个数据速率更加弹性、灵活、可重构以及资源更有效利用的光网络。最近提出的频谱分片弹性光网络,SLICE可灵活地给业务分配可变带宽，并高效地利用频谱资源。在实际应用中，为确保接收端的信号质量与滤波效果，在分配频谱资源时，要遵守频谱一致性约束、频谱连续性约束和频谱冲突约束，链路中不满足这三个约束条件的频隙不能被分配。在一个动态业务场景中，光通道的建立与拆除过程会引起频谱的碎片化。在小的非连续频带中的可用频谱即碎片会导致网络中的频谱效率受影响，降低了为一个连接找到足够连续频谱的可能性。尽管有足够的频谱可用，新到达的请求要么必须使用更多的网络频谱，要么被阻塞。因此，频谱碎片会导致频谱利用率降低和业务阻塞率上升。目前，对频谱碎片这一问题有以下几种解决方案：

Patel A.N.等人在文献“Defragmentation of Transparent Flexible OpticalWDM(FWDM)Networks”(Optical Fiber Communication Conference and Exposition,2011,pp.1-3)中首次提出了频谱碎片的概念并给出了两种周期式光路重构算法：Greedy算法和最短路径SP算法。Greedy算法和最短路径SP算法，是将占有最大序号频谱的连接请求重新分配到最小序号的频谱上，并且是按照所占用频谱序号降序重构所有存在的连接请求。这样可以使得所有存在的连接请求集中到小序号的频谱范围内，但是每一次重构所选择的并不是最佳方案，重构完成后仍然会占用较多的频谱，使得阻塞率比较高。

Weiguo Ju,Shanguo Huang,Zhenzhen Xu,Jie Zhang,Wanyi Gu等人在文献“Dynamic Adaptive Spectrum Defragmentation Scheme in Elastic Optical PathNetworks”,(Opto-Electronics and Communications Conference,2012,pp.21-22)中提出了最大频谱增益重路由算法MSGR和动态频谱移动算法DSSD，这两种算法都是触发式光路重构算法。MSGR算法只有在大颗粒度的连接请求离开后，释放出足够的频谱资源时才能被触发，该算法只允许具有最大频谱增益的连接请求被重构，该算法虽然进行光路重构的次数较少，但是对后续到达的连接请求影响不大，除非后续的连接请求正好占用被释放的频谱资源。DSSD算法只有在最小间隙超过某个门限值时才能被触发，该算法只进行频谱搬移，而不对连接请求重新选路，这样频谱碎片仍然很大，对阻塞率改善不大。

Alberto Castro,Luis Velasco,Marc Ruiz等人在文献“Dynamic routing andspectrum(re)allocation in future flexgrid optical networks”(Journal ofComputer Networks,2012,Volume 56,Issue12,pp.2869-2883)中提出动态选路与频谱分配算法RSA和SPRESSO算法。SPRESSO算法是触发式光路重构算法，当新到达的连接请求无法建立时算法被触发。该算法将与新到达连接请求最短路径上有冲突的连接请求进行频谱搬移，但是路径不会发生改变。

Yawei Yin,Ke Wen,David J.Geisler,Ruiting Liu,and S.J.B.Yoo等人在文献“Dynamic on-demand defragmentation in flexible bandwidth elastic opticalnetworks”(OPTICS EXPRESS,2012,Volume 20,pp.1798-1804)中通过建立辅助图，将光路重构转换为求辅助图最大独立集MIS的问题。当网络规模较小时，求解MIS问题所花费时间不多，但是当网络规模增大，MIS求解的复杂度大大增加，计算时间很长，而且不适合于动态场景。

发明内容

本发明的目的在于针对上述现有技术的不足，提出一种基于通道密度和最小间隙的触发式聚合光路重构方法，以在动态场景下提高频谱利用率，降低阻塞率。

实现本发明目的技术思路是：将分布“疏松”的连接请求聚合成“紧密”状态，即将具有小通道密度和大最小间隙的连接请求转换为大通道密度和小最小间隙，从而提高网络资源利用率。具体步骤包括如下：

(1)对网络中新到达的连接请求(s_new,d_new,B_new)用迪杰斯特拉方法选择一条从源节点s_new到宿节点d_new的路径，并按照首次命中的方法在有限的频谱资源内分配频谱，如果所选通路上连续的空闲频谱大于等于请求带宽B_new，则成功建立了一条从s_new到d_new占用连续频谱的光路，结束并等待下一个连接请求；否则，执行步骤(2)；

(2)遍历所选路径上大于等于请求带宽B_new的频谱c_i,i＝1,2,…,N-B_new+1，将与ci相冲突的连接请求组成冲突集合i＝1,2,…,N-B_new+1，其中N表示有限的频谱资源宽度，并从这些冲突集合中找出元素个数最少的集合，命名为重构集合T_r；

(3)统计重构集合T_r中所有的连接请求已建光路的通道密度和最小间隙，并对重构集合T_r中的连接请求进行排序，其排序规则是：先按通道密度升序排序，再对通道密度相等的连接请求按照最小间隙降序排序；

(4)找出排序后重构集合T_r中每个连接请求的所有与原光路频谱不冲突的新光路，计算每条新光路的通道密度和最小间隙，并对所有新光路进行排序，其排序规则是：先按通道密度降序排序，再对通道密度相等的新光路按照最小间隙升序排序；选择排序后第一个新光路进行重构操作，即给新光路分配频谱并释放原光路上的频谱；

(5)判断重构集合T_r中所有连接请求是否都进行了重构操作，若是，则返回到步骤(1)；否则，丢弃该连接请求，结束并等待下一个连接请求。

本发明与现有技术比较具有以下优点：

第一，减少了阻塞率，提高了频谱利用率。

本发明选择通道密度最大和最小间隙最小的新光路进行重构；通道密度越大，反映在相同的频谱范围内连接请求在网络中占用的链路数越多且所建路径的平均跳数越少；占用的链路数越多说明链路的使用效率越高，那些不常用的链路被使用的机率增大，从而减轻了关键链路的负担；平均跳数越少说明连接请求占用的平均资源越少，这里的资源指的是连接请求在链路上占用的频谱之和。最小间隙越小，反映相邻连接请求在频谱上排列越紧密。克服了现有技术中只片面考虑连接请求在频谱上紧密排列的缺点。可以使得频谱碎片更小，从而可以减少阻塞率并提高频谱利用率。

第二，节省了更多的频谱资源。

本发明每一次重构操作选择的都是最佳的新光路，克服了现有技术中每一次重构所选择的并不是最佳方案的缺点，使用更少的频谱资源达到相同的效果，节省了更多的频谱资源。

第三，减轻了关键链路的负担，使得网络流量更加均衡。

本发明不仅对连接请求进行频谱搬移，而且对其进行重新选路，克服了现有技术只进行频谱搬移，而不对连接请求重新选路的缺点。可以减轻关键链路的负担，将连接请求所建路径重新调整到那些比较空闲的链路上，提高了链路使用效率，使得网络流量更加均衡。

附图说明

图1为本发明使用的网络结构图；

图2为本发明的实现流程图；

图3本发明与现有方法的阻塞率性能仿真对比图；

图4为本发明与现有方法的频谱利用率仿真对比图；

图5为本发明与现有方法的平均计算时间仿真对比图；

图6为本发明与现有方法的重构次数仿真对比图。

具体实施方式

下面结合附图对本发明的技术方案和效果做进一步的详细描述。

参照图1，本发明使用的网络是由14个节点和21条链路组成的NSFNET网络。为了更清晰的标识网络，将节点进行编号为从0到13。链路是相邻两个节点之间的物理连接，如链路(0,7)表示0号节点和7号节点之间存在一条物理连接，这条链路的长度为480公里。连接请求用(s,d,B)表示，s是源节点，d是宿节点，B是请求带宽。其中源节点s和宿结点d都在NSFNET的14个节点中选取，请求带宽B不能超过频隙集合F中频隙的个数。本发明也可以使用其他网络，比如CHNNET等。

参照图2，本发明的实现步骤如下：

步骤1，对新到达的连接请求进行选路。

采用迪杰斯特拉方法为新到达的连接请求(s_new,d_new,B_new)在网络中选择一条从源节点s_new到宿结点d_new的一条最短路径p_new。例如对于使用的NSFNET网络，如果源节点为0，宿结点为12，则迪杰斯特拉方法算出的最短路径为0→7→8→12，路径总长度为690公里。

步骤2，对选路后的连接请求进行频谱分配。

给选路后的连接请求分配频谱资源，可采用首次命中、随机分配和最大总数等方法，本实例中采用了首次命中方法，本步骤的具体步骤如下：

2a)采用频隙集合F＝{fs₁,fs₂,…,fs_i,…,fs_N},1≤i≤N构成网络中有限的频谱，其中频隙fsi是承载信息的低速子载波，相邻频隙有1/2的频谱重叠,N是频隙个数；

2b)令i＝1；

2c)从频隙集合F中第i个频隙fsi开始，取出连续B_new个频隙，B_new是新到达连接请求的请求带宽，组成通道

2d)判断最短路径p_new中各条链路上通道c_i内的每个频隙是否都空闲：如果空闲，则将该最短路径p_new中各条链路中的B_new个连续频隙分配给连接请求，即资源分配成功，等待下一个连接请求到达，返回步骤1；否则，执行步骤2e)；

2e)改变i值，使其自动增1；再判断i的大小，如果i≤N-B_new+1，则返回步骤2c)；否则，资源分配失败，执行步骤3。

步骤3，找出与频谱分配不成功的连接请求相冲突的已有连接请求，并组成重构集合T_r。

3a)令j＝1；

3b)从频隙集合F中第j个频隙fs_j开始，取出连续B_new个频隙，组成通道

3c)将与最短路径p_new中各条链路上与通道c_j频谱重叠的连接请求组成冲突集合

3d)j值自动增1；判断j值大小，如果j≤N-B_new+1，则返回步骤3b)；否则，执行步骤3e)；

3e)找出所有冲突集合中的元素个数最少的冲突集合，将其命名为重构集合T_r，记录其通道c_min。

步骤4，基于通道密度和最小间隙对重构集合Tr中的连接请求进行排序。

本发明提出了通道密度和最小间隙的概念。通道密度是指网络中所有链路被通道覆盖的连接请求个数。通道密度越大，反映在相同的频谱范围内连接请求在网络中占用的链路数越多且所建路径的平均跳数越少；占用的链路数越多说明链路的使用效率越高，那些不常用的链路被使用的机率增大，从而减轻了关键链路的负担；平均跳数越少说明连接请求占用的平均资源越少，这里的资源指的是连接请求在链路上占用的频谱之和。最小间隙是指在连接请求所选路径的所有链路中，与相邻的连接请求频谱之间数值最小的间隔。最小间隙越小，反映相邻连接请求在频谱上排列越紧密。

本步骤的具体步骤如下：

4a)令k＝1；

4b)根据重构集合T_r中第k个连接请求已建光路占用的通道，统计其通道密度；

4c)根据重构集合T_r中第k个连接请求已建光路中的链路，统计其最小间隙；

4d)k值自动增1；判断k值大小，如果k≤|T_r|，返回步骤4b)，否则，执行步骤4e)，其中|T_r|是重构集合T_r的模，表示重构集合T_r中元素的个数；

4e)对重构集合T_r中的连接请求进行排序，即先按通道密度升序排序，再对通道密度相等的连接请求按照最小间隙降序排序，形成新的重构集合T_r'。

步骤5，对排序后的重构集合T_r'中连接请求使用最佳备选光路的进行重构操作。

5a)令m＝1，m表示重构集合T_r'中元素的序号；

5b)选择重构集合T_r'中的第m个连接请求(s_m,d_m,B_m)；

5c)为第m个连接请求重新选路，得到最小跳数路径p_m；

将附图1中NSFNET网络的所有链路长度改为1，再使用迪杰斯特拉方法重新为第m个连接请求选路，得到最小跳数路径p_m；在本实例中，假如源节点为1，宿结点为7，最小跳数路径则为1→0→7，路径总长度为690公里，路径跳数为2；

5d)令n＝1，n表示频隙集合F中频隙的序号；

5e)从频隙集合F中第n个频隙fs_n开始，取出连续B_m个频隙，B_m是重构集合T_r'中的第m个连接请求的请求带宽，组成通道

5f)判断最小跳数路径p_m中各条链路上通道c_n内的每个频隙是否都空闲：如果空闲，则将(p_m,c_n)作为一个备选光路加入到重构集合T_r'中的第m个连接请求的备选集合LP_m中，否则，执行步骤5g)；

5g)n值自动加1；判断n值大小：如果n≤N-B_m+1，则返回步骤5e)；否则，执行步骤5h)；

5h)判断备选集合LP_m是否为空集：如果是，表示找不到新的光路进行重构，重构操作失败，等待下一个连接请求到达，返回步骤1；否则，执行步骤5i)；

5i)分别统计备选集合LP_m中的所有备选光路的通道密度和最小间隙；

5j)对备选集合LP_m中的备选光路进行排序，即先按通道密度降序排序，再对通道密度相等的连接请求按照最小间隙升序排序，形成新的备选集合LP_m'；

5k)选择排序后的备选集合LP_m'中排在第一位的备选光路进行重构操作：

首先，为第m个连接请求建立新光路(p_m,c_n)；

然后，再释放原光路上的频谱，即设置原光路上的频谱资源为空闲；

5l)m值自动加1；判断m值大小：如果m≤|T_r'|，则返回步骤5b)；否则，重构操作结束，执行步骤6，其中|T_r'|是重构集合T_r'的模，表示重构集合T_r'中元素的个数。

步骤6，为新到达的连接请求重新分配频谱。

将最短路径p_new中各条链路中的频谱分配给新到达的连接请求，然后等待下一个连接请求到达，返回步骤1，其中c_min是与新到达的连接请求冲突个数最少的通道。

本发明的效果可以通过以下仿真进一步说明：

1.仿真环境设置

为了说明本发明在实际网络中的性能，采用了计算机仿真的方法。硬件环境：I3CPU,3.30GHz/4GB RAM。在仿真实验中，连接请求的产生服从到达率为λ的泊松分布，每个连接请求的持续时间服从均值为μ的负指数分布，其中平均持续时间为10小时。每个连接请求的原宿结点对是在图1所示NSFNET拓扑上随机产生，请求带宽的频隙数均匀的在[1,10]之间生成，每个频隙所占频谱宽度为2.5GHz，每条链路上有160个频隙。相邻连接请求之间需要有2个保护频隙。拓扑上的权值表示的是相邻结点间的距离。

2.仿真内容与结果分析

仿真1，用本发明和现有的MSGR算法、DSSD算法、SPRESSO算法以及无光路重构的D-FF方法，分别在相同的仿真环境中对阻塞率进行仿真，结果如图3。图3中，横轴表示网络业务量，纵轴表示阻塞率。

从图3中可以看出，无光路重构的D-FF算法阻塞率最大，MSGR、DSSD和SPRESSO算法性能均有不同程度的改善，本发明阻塞率最低。本发明与无光路重构的D-FF方法相比，当业务量从100爱尔兰增加到300爱尔兰时，其阻塞率的改善程度从6.46％增加到了16.7％。

仿真2，用本发明和现有的MSGR算法、DSSD算法、SPRESSO算法以及无光路重构的D-FF方法，分别在相同的仿真环境中对频谱利用率进行仿真，结果如图4。图4中，横轴表示网络业务量，纵轴表示频谱利用率。

从图4中可以看出，本发明的频谱利用率最高，无碎片整理的D-FF方法最低。本发明比无碎片整理的D-FF方法的频谱利用率提高了27.66％～56.03％。

仿真3，用本发明和现有的MSGR算法、DSSD算法和SPRESSO算法，分别在相同的仿真环境中对平均计算时间进行仿真，结果如图5。图5中横轴表示网络业务量，纵轴表示平均计算时间。

从图5中可以看出，这几种方法的计算时间都在0.16～0.52秒之间，其中SPRESSO算法最少，本发明的平均计算时间在业务量较低时略大于SPRESSO算法，当业务量达到270爱尔兰时，本发明的平均计算时间低于SPRESSO算法。

仿真4，用本发明和现有的MSGR算法、DSSD算法和SPRESSO算法，分别在相同的仿真环境中对重构次数进行仿真，结果如图6。图6中横轴表示网络业务量，纵轴表示重构次数。

从图6中可以看出，MSGR算法重构次数最，DSSD算法和SPRESSO算法的重构次数都在一定范围内波动，本发明在业务量小的时候重构次数最少，随着业务量增加，重构次数随着增多，而业务量达到190爱尔兰时，重构次数就会超过DSSD算法和SPRESSO算法。

综上，本发明可以最大程度的降低阻塞率，并有着最高的频谱利用率，实时性较好，重构次数较多。

Claims

1.一种基于通道密度和最小间隙的触发式聚合光路重构方法，包括如下步骤：

(2)遍历所选路径上大于等于请求带宽B_new的频谱ci,i＝1,2,…,N-B_new+1，将与c_i相冲突的连接请求组成冲突集合i＝1,2,…,N-B_new+1，其中N表示有限的频谱资源宽度，并从这些冲突集合中找出元素个数最少的集合，命名为重构集合T_r；

2.根据权利要求1所述的方法，其中所述步骤(1)中按照首次命中的方法在有限的频谱资源内分配频谱，包括如下步骤：

1a)采用频隙集合F＝{fs₁,fs₂,…,fs_i,…,fs_N},1≤i≤N构成网络中有限的频谱，其中频隙fs_i是承载信息的低速子载波，相邻频隙有1/2的频谱重叠,N是频隙个数；

1b)令i＝1；

1c)从频隙集合F中第i个频隙fsi开始，取出连续B_new个频隙，组成通道

c_{i} = {{fs}_{i}, {fs}_{i + 1}, \cdot \cdot \cdot, {fs}_{i + B_{new} - 1}}, B_{new} \leq N;

1d)判断经过迪杰斯特拉方法所选路径中各条链路上通道c_i内的每个频隙是否都空闲：如果空闲，则将通道c_i中的B_new个连续频隙分配给连接请求，结束资源分配；否则，执行步骤1e)；

1e)改变i值，使其自动增1；再判断i的大小，如果i≤N-B_new+1，则返回步骤1c)；否则，资源分配失败并结束。

3.根据权利要求1所述的方法，其中所述步骤(3)中的通道密度，是指网络中所有链路被通道覆盖的连接请求个数。

4.根据权利要求1所述的方法，其中所述步骤(3)中的最小间隙，是指在连接请求所选路径的所有链路中，与相邻的连接请求频谱之间数值最小的间隔。