一种降低光传送网端到端时延的网络分域方法

摘要

本发明公开了一种降低光传送网端到端时延的网络分域方法，属于光通信技术领域。首先输入待优化的拓扑，理想分区数m以及参选节点集合N；从集合N中任选m个节点构建节点组合；然后对每个节点组合重新划分拓扑区域，得到各自对应的拓扑方案；计算每一个组合更新后的拓扑方案的平均端到端时延值；最后选择平均端到端时延值最小的拓扑方案作为时延最优的分域拓扑方案。本发明通过合理的网络规划，在进行业务端到端传送时能够避免业务绕路，既减少了链路时延，也减少了节点时延，使得网络时延性能提升，能够更好地保障低时延及时延敏感业务的需求。

说明书

技术领域

本发明属于光通信技术领域，涉及光传送网技术，具体是一种降低光传送网端到端时延的网络分域方法。

背景技术

随着通信技术的发展和互联网应用的普及，部分行业和业务对网络的时延性能提出了极为严苛的要求，网络时延性能逐渐成为通信领域的新兴热点之一。光传送网(OTN)技术以波分复用(WDM)技术为基础，融合了同步数字体系(SDH)技术的电层处理和网络管理能力，具有业务调度灵活和大容量传输的优势；此外，由于业务层级较低且为刚性管道传输，OTN技术还具有低时延和低时延抖动的优势，是构建低时延网络的最优选择。

传统的通信网络通常采用分层集中的控制方式，将网络划分为多个区域，每个区域包含一个服务器，对该区域内的业务请求进行响应，同时，这些区域服务器又由总部的服务器进行调控。当业务向区域服务器请求内容时，若该服务器包含此内容，则由区域服务器对该请求进行响应，否则由该服务器向总部服务器发送请求，并由总部服务器对该请求进行响应。尽管OTN具有时延优势，但链路时延仍是不可避免的。在这种分层集中控制方式下，对于规模较大的骨干传送网而言，部分节点与总部服务器间的距离过大，导致链路时延较大，从而影响业务的时延性能。

为了改善网络时延性能，应采用网络扁平化的策略，以多中心协同控制取代传统的分层集中式控制，即将原有的总部服务器的功能分散至各个区域服务器，由各区域服务器协同控制调度。在多中心协同控制方式下，各区域服务器中除了存储本地内容外，还存储其他区域服务器中的内容列表，当本地区域服务器不包含所请求的内容时，搜索内容列表并向包含该内容且距离最近的区域服务器发起请求，由该区域服务器对该业务请求进行响应。多中心协同控制方式能够有效减少业务的传输距离，从而降低端到端时延。为实现上述目标，首先要对网络进行区域划分并确定区域中心。当网络区域划分及中心节点选择不合理时，会造成业务绕路等问题，从而使端到端传送时延增加。运营商网络等传统的通信网络通常以行政区划为依据来进行网络划分并确定中心节点，从网络时延性能角度来说，这种划分方式并非最优。为了满足日益严苛的时延需求，需以端到端时延为依据，设计算法来实现对网络区域的合理划分并确定各区域的最优调度中心节点。

发明内容

本发明针对上述问题，采用遍历的方式，通过对具体输入条件下所有可能的网络分域方案进行平均端到端时延计算，得到该输入条件下时延最优的网络分域方案，使得网络的区域划分及中心节点的确定更为合理，减少了业务绕路的可能，从而达到降低业务端到端时延的技术效果，具有提高网络时延性能的优势，在保障低时延及时延敏感业务需求方面具有现实意义。

具体步骤如下：

步骤一、输入待优化的拓扑G，理想分区数m，以及参选节点集合N＝{n₁,n₂,…,n_a}；

集合N中元素的个数为a，a>1，且a为整数；每个分区由一个节点控制，即m≤a；集合N中的元素为拓扑G中的全部节点或满足一定条件的部分节点。

步骤二、从集合N的a个节点中，任选m个节点构建一个节点组合，共形成了个节点组合。

步骤三、对每一个节点组合重新划分拓扑区域，得到各自对应的拓扑方案

分为以下步骤：

步骤301、输入待优化拓扑G及第i个节点组合C_i＝{n₁,n₂,…,n_m}。

步骤302、针对拓扑G中不属于组合C_i的某个节点A，用Dijkstra算法依次计算该节点A>i中每个节点之间的端到端路由路径，并分别计算各路径对应的端到端时延值t₁,t₂,…,t_m。

每个路由路径分别对应一个端到端时延值，端到端时延计算方法的步骤如下：

步骤1：针对某个路由路径，根据网络拓扑属性与用户指定的带宽，得到该路由路径经过的节点和链路列表。

步骤2：根据链路列表中的每段链路的长度，计算各段链路的时延，求和得到链路总时延T_l。

步骤3：判断该路由路径经过的各节点所处的位置，结合带宽计算各节点的时延，求和得到节点总时延T_n。

步骤4：进一步得到端到端总时延T_t＝T_l+T_n。

步骤303、对不属于组合C_i的节点A，从m个端到端时延值中选出最小值t_k，并将时延最小值t_k对应的组合内的节点n_k作为节点A的中心节点。

t_k＝min{t₁,t₂,…,t_m}。

步骤304、同理，每个不属于组合C_i的节点，都能根据最小端到端时延值，在组合C_i内找到各自的中心节点。

步骤305、针对组合C_i内的某节点n_k，根据端到端最小时延值对应的各不属于该组合的节点作为节点n_k的下属节点；

步骤306、将该节点n_k和其下属节点划分为一个区域，更新拓扑G，得到组合C_i对应的拓扑方案G_i。

拓扑方案G_i中包括m个区域，每个区域包含一个中心节点及其全部下属节点，节点及节点间的链路均与原拓扑G相同。

步骤307、同理，将每个节点组合分别进行优化，得到各个组合对应的更新拓扑；

每个更新的拓扑中都包括组合中的中心节点以及各自连接的各下属节点。

步骤四、计算每一个组合更新后的拓扑方案的平均端到端时延值；

分为以下步骤：

首先、针对更新后的某个拓扑方案G_i，包括的节点集合为：对集合 R中的每个节点，计算该节点到集合R中其他每个节点之间的分域路由路径；

集合R中的每一个节点均将作为源节点，并将集合R中其他节点作为宿节点，依次计算源宿节点各自对应的分域路由路径；具体过程如下：

输入划分区域的拓扑方案G_i、源节点src和宿节点des；获取源节点和宿节点各自所属的区域中心节点H_src和H_des。然后，判断源节点src和宿节点des的区域中心节点是否相同，如果是，源节点src和宿节点des属于同一区域，利用Dijkstra算法计算分域路由路径path：为>src→des；否则不同域，根据节点属性进行如下划分后再利用Dijkstra算法计算路由路径：

最终，得到分域路由路径集合

然后、计算集合P中每个分域路由路径对应的端到端时延值，并组成集合Q；

端到端时延结果集合

最后、根据端到端时延结果集合Q，计算拓扑方案G_i的全网平均端到端时延值T_i。

其中j＝1,2,…,|G_i|×(|G_i|-1)。

同理，得到每个更新后的拓扑方案的全网平均端到端时延值；

步骤五、选择平均端到端时延值最小的拓扑方案作为时延最优的分域拓扑方案。

本发明的优点在于：

(1)一种降低光传送网端到端时延的网络分域方法，可根据输入的区域数目和满足条件的节点，以时延为约束对网络进行区域划分并选定区域中心节点，能够有效降低业务的端到端传送时延，提高网络时延性能。

(2)一种降低光传送网端到端时延的网络分域方法，基于多中心协同控制特征，根据业务的源宿节点及所属区域采用经典的Dijkstra算法进行分段最短路径计算，可得到业务的最短分域路由，减少链路时延。

(3)一种降低光传送网端到端时延的网络分域方法，基于OTN网络的时延构成，可根据OTN设备特征和具体业务的带宽及路由计算得到业务的端到端时延，从而得到网络的平均端到端时延，是进行低时延网络分域的基础。

附图说明

图1为本发明一种降低光传送网端到端时延的网络分域方法的步骤流程图；

图2为本发明一种分域路由计算方法的步骤流程图；

图3为本发明一种OTN端到端业务时延计算方法的步骤流程图；

图4为本发明实施例中所用的未分域的六节点拓扑图；

图5为本发明实施例中所用的已分域的六节点拓扑图。

具体实施方案

下面将结合附图和实例对本发明作进一步的详细说明。

本发明一种降低光传送网端到端时延的网络分域方法，如图1所示，分为以下步骤：

步骤一、输入待优化的拓扑G，理想分区数m，以及参选节点集合N＝{n₁,n₂,…,n_a}；

集合N中元素的个数为a，a>1，且a为整数；每个分区由一个节点控制，即m≤a；集合N中的元素为拓扑G中的全部节点或满足一定条件的部分节点。

步骤二、从集合N的a个节点中，任选m个节点构建一个节点组合，共形成了个节点组合。

其中，每个节点组合中包含参选中心节点集合N中的m个中心节点。

步骤三、对每一个节点组合重新划分拓扑区域，得到各自对应的拓扑方案；

分为以下步骤：

步骤301、输入待优化拓扑G及第i个节点组合C_i＝{n₁,n₂,…,n_m}。

步骤302、针对拓扑G中不属于组合C_i的某个节点A，用Dijkstra算法依次计算该节点A>i中每个节点之间的端到端路由路径，并分别计算各路径对应的端到端时延值t₁,t₂,…,t_m。

每个路由路径分别对应一个端到端时延值，如图3所示，端到端时延计算方法的步骤如下：

第一步，输入拓扑图G和某业务traffic＝(B,P)；

其中，B为业务的带宽，用户指定值；P为该业务的路由路径，每个业务有唯一的路由路径。

第二步，获取该条路由路径P所经的节点集合n_list＝{n₁,n₂,…,n_k}和链路集合l_list＝{l₁,l₂,…,l_k-1}。

第三步，根据l_list计算业务的链路时延；

对l_list中的每条链路l_i，获取拓扑G中该条链路的长度当时该条链路的时延当时该条链路的时延

则该条业务的总链路时延其中，i＝1,2,…,k-1。

第四步，根据n_list计算业务的节点时延；

对n_list中的每个节点n_i，根据其所处位置计算其时延则该条业务的总节点时延其中，i＝1,2,…,k。

节点n_i的时延值与其所处位置的关系如下：

其中：

(1)中间节点的时延与选择的交换方式有关，若信号经过节点时通过光层设备实现光层直达，则为光穿通时延T_through；否则为电交换时延T_switch；

(2)电交换时延T_switch和光穿通时延T_through与具体设备能力有关，需根据具体情况来设置。

(3)封装时延T_encap和解封装时延T_decap与设备能力、业务带宽及具体的映射复用路径有关：

当业务带宽大于设备能力时，需对业务进行拆分后再进行封装映射；每增加一级复用，时延增加0.512us。由于解封装时按照封装映射复用路径逆向进行，T_encap＝T_decap。

a)若设备能力满足业务带宽，则T_encap＝T_decap＝0.512×u，其中，u为业务映射复用级数；

b)若设备能力无法满足业务带宽，将原业务进行拆分为v个子业务和1个剩余业务，使得原始业务带宽＝设备最大速率×v+剩余业务带宽，T_encap＝T_decap＝0.512×(u₁×v+u₂)，其中u₁和u₂分别为子业务和剩余业务的映射复用级数。

(4)FEC编码时延T_code和FEC解码时延T_decode与FEC算法的复杂度、业务带宽及业务传送距离有关，具体的时延值应根据所选择的FEC算法及具体的应用场景来确定。

第五步，计算得到该条业务的路由路径对应的端到端总时延T_t＝T_l+T_n。

步骤303、对不属于组合C_i的节点A，从m个端到端时延值中选出最小值t_k，并将时延最小值t_k对应的组合内的节点n_k作为节点A的中心节点。

t_k＝min{t₁,t₂,…,t_m}。

步骤304、同理，每个不属于组合C_i的节点，都能根据最小端到端时延值，在组合C_i内找到各自的中心节点。

步骤305、针对组合C_i内的某节点n_k，根据端到端最小时延值对应的各不属于该组合的节点作为节点n_k的下属节点；

步骤306、将该节点n_k和其下属节点划分为一个区域，更新拓扑G，得到组合C_i对应的拓扑方案G_i。

拓扑方案G_i中包括m个区域，每个区域包含一个中心节点及其全部下属节点，节点及节点间的链路均与原拓扑G相同。

步骤307、同理，将每个节点组合分别进行优化，得到各个组合对应的更新拓扑；

每个更新的拓扑中都包括组合中的中心节点以及各自连接的各下属节点。

步骤四、计算每一个组合更新后的拓扑方案的平均端到端时延值；

对每一个节点组合C_i重新划分拓扑区域，得到拓扑方案G_i，并计算其平均端到端时延值T_i。拓扑方案G_i应使原拓扑G中不属于组合C_i的其他节点到其所属的中心节点时延最小。

分为以下步骤：

首先、针对更新后的某个拓扑方案G_i，包括的节点集合为：对集合 R中的每个节点，计算该节点到集合R中其他每个节点之间的分域路由路径；

如图2所示，具体过程如下：输入划分区域的拓扑方案G_i、源节点src和宿节点des；获取源节点和宿节点各自所属的区域中心节点H_src和H_des。然后，判断源节点src和宿节点des>src→des；否则不同域，根据节点属性进行如下划分后再利用Dijkstra>

最后得到最终的分域路由路径集合

然后、计算集合P中每个分域路由路径对应的端到端时延值，并组成集合Q；

端到端时延结果集合

最后、根据端到端时延结果集合Q，计算拓扑方案G_i的全网平均端到端时延值T_i。

其中j＝1,2,…,|G_i|×(|G_i|-1)。

同理，得到每个更新后的拓扑方案的全网平均端到端时延值；

步骤五、选择平均端到端时延值最小的拓扑方案作为时延最优的分域拓扑方案。

实施例1

以六节点拓扑为例进行说明，如图4所示，假设该网络中全部节点均可作为中心节点，将该网络划分为两个区域，具体步骤如下：

1、输入六节点拓扑作为待优化拓扑G，理想分区数m＝2，参选中心节点集合 N＝{n₁,n₂,n₃,n₄,n₅,n₆}。

2、根据待优化拓扑G、理想分区数m和参选中心节点集合N，得到全部共个中心节点组合。

其中，每个中心节点组合中包含参选中心节点集合N中的2个中心节点，分别为：

C₁＝(n₁,n₂),C₂＝(n₁,n₃),C₃＝(n₁,n₄),C₄＝(n₁,n₅),C₅＝(n₁,n₆),C₆＝(n₂,n₃),C₇＝>2,n₄),C₈＝(n₂,n₅),C₉＝(n₂,n₆),C₁₀＝(n₃,n₄),C₁₁＝(n₃,n₅),C₁₂＝(n₃,n₆),C₁₃＝>4,n₅),C₁₄＝(n₄,n₆),C₁₅＝(n₅,n₆)。

3、对每一个中心节点组合C_i，根据C_i重新划分拓扑区域，得到拓扑方案G_i，并计算其平均端到端时延值T_i。

以C₁＝(n₁,n₂)的拓扑方案G₁为例，具体步骤如下：

a)输入待优化拓扑G及中心节点组合C₁＝(n₁,n₂)。

b)对拓扑G中每一个不属于C₁＝(n₁,n₂)的节点，调用分域路由方法和端到端时延计算方法，依次计算该节点到C₁中两个中心节点的端到端时延值，具体结果如下表所示：

其他节点中心节点时延值/us中心节点时延值/usn₃n₁1656.998n₂1156.448n₄n₁1907.048n₂1406.498n₅n₁1656.998n₂1156.448n₆n₁655.948n₂905.948

c)对拓扑G中每一个不属于C₁＝(n₁,n₂)的节点，在C₁中找到一个对应的节点p作为其中心节点，使该节点到节点p的端到端时延值比到C₁中其他节点小，即：

其他节点中心节点时延值/usn₃n₂1156.448n₄n₂1406.498n₅n₂1156.448n₆n₁655.948

d)将每个中心节点及其下属节点划分为一个区域，更新拓扑G，得到拓扑方案G₁，即：

4、按照上述方法得到全部拓扑方案G₁,G₂,…,G₁₅，对每个拓扑方案G_i，计算其全网平均端到端时延值T_i。

以计算G₁的时延值T₁为例，具体步骤如下：

a)输入已分区的拓扑方案G₁。

b)R＝{n₁,n₂,n₃,n₄,n₅,n₆}，为拓扑G₁的节点集合。对集合R中的每个节点，计算该节点到R中其他节点的分域路由路径，得到路由结果集合：

P＝{p₁₂,p₁₃,p₁₄,p₁₅,p₁₆,p₂₁,p₂₃,p₂₄,p₂₅,p₂₆,p₃₁,p₃₂,p₃₄,p₃₅,p₃₆,>41,p₄₂,p₄₃,p₄₅,p₄₆,p₅₁,p₅₂,p₅₃,p₅₄,p₅₆,p₆₁,p₆₂,p₆₃,p₆₄,p₆₄}

c)根据路由结果集合P，计算拓扑G₁中各节点到其他节点的端到端时延值，得到端到端时延结果集合：

Q＝{t₁₂,t₁₃,t₁₄,t₁₅,t₁₆,t₂₁,t₂₃,t₂₄,t₂₅,t₂₆,t₃₁,t₃₂,t₃₄,t₃₅,t₃₆,>41,t₄₂,t₄₃,t₄₅,t₄₆,t₅₁,t₅₂,t₅₃,t₅₄,t₅₆,t₆₁,t₆₂,t₆₃,t₆₄,t₆₄}

d)根据端到端时延结果集合Q，计算拓扑方案G₁的全网平均端到端时延值T₁，即对T₁中所有时延值取平均值。

5、按照上述方法得到全部拓扑方案G₁,G₂,…,G₁₅的全部端到端时延值T₁,T₂,…,T₁₅，具体结果如下：

6、选择平均端到端时延值最小的拓扑方案G₁₅作为优化拓扑方案G_o，G_o即为最终得到的时延最优的分域拓扑。如图5所示，具体分域情况如下：

区域中心节点其他节点area1n₅n₃,n₄area2n₆n₁,n₂

实施例2

如图5所示，六节点拓扑G已划分区域，分别计算在此拓扑上节点对>3,n₄),(n₅,n₆),(n₅,n₁),(n₃,n₆),(n₄,n₁)之间的分域路由路径。

(A)源节点src＝n₃，宿节点des＝n₄

1、输入已划分区域的拓扑G、源节点src＝n₃、宿节点des＝n₄；

2、根据G的区域划分得到源、宿节点的中心节点分别为H_src＝n₅、H_des＝n₅；

3、根据G的区域划分可知源、宿节点同属area1，故利用D算法计算src→H_des→des，可得到path＝[n₃,n₅,n₄]。

(B)源节点src＝n₅，宿节点des＝n₆

1、输入已划分区域的拓扑G、源节点src＝n₅、宿节点des＝n₆；

2、根据G的区域划分得到源、宿节点的中心节点分别为H_src＝n₅、H_des＝n₆；

3、根据G的区域划分可知源、宿节点分属area1、area2，且节点n₅、n₆均为区域中心节点，故利用D算法计算src→des，可得到path＝[n₅,n₆]。

(C)源节点src＝n₅，宿节点des＝n₁

1、输入已划分区域的拓扑G、源节点src＝n₅、宿节点des＝n₁；

2、根据G的区域划分得到源、宿节点的中心节点分别为H_src＝n₅、H_des＝n₆；

3、根据G的区域划分可知源、宿节点分属area1、area2，且节点n₅为中心节点，节点n₁非中心节点，故利用Dijkstra算法计算src→H_des→des，可得到path＝[n₅,n₆,n₁]。

(D)源节点src＝n₃，宿节点des＝n₆

1、输入已划分区域的拓扑G、源节点src＝n₃、宿节点des＝n₆；

2、根据G的区域划分得到源、宿节点的中心节点分别为H_src＝n₅、H_des＝n₆；

3、根据G的区域划分可知源、宿节点分属area1、area2，且节点n₃非中心节点，节点n₆为中心节点，故利用D算法计算src→H_src→des，可得到path＝[n₃,n₅,n₆]。

(E)源节点src＝n₄，宿节点des＝n₁

1、输入已划分区域的拓扑G、源节点src＝n₄、宿节点des＝n₁；

2、根据G的区域划分得到源、宿节点的中心节点分别为H_src＝n₅、H_des＝n₆；

3、根据G的区域划分可知源、宿节点分属area1、area2，且节点n₄、n₁均非中心节点，故利用D算法计算src→H_src→H_des→des，可得到path＝[n₄,n₅,n₆,n₁]。

实施例3

如图5所示，六节点拓扑G已划分区域，已知业务路由路径P＝[n₄,n₅,n₆,n₁]，假设业务带宽B＝1000MHz，计算此拓扑上节点对(n₄,n₁)之间的业务端到端时延。为方便叙述，假设拓扑中节点均为100Gbps>

1、输入拓扑G，业务traffic＝(B,P)＝(1000MHz,[n₄,n₅,n₆,n₁])；

2、得到该条业务所经节点集合n_list＝{n₄,n₅,n₆,n₁},链路集合>list＝{(n₄,n₅),(n₅,n₆),(n₆,n₁)}；

3、根据l_list计算业务的链路时延：

即，该条业务的端到端链路总时延T_l＝1750.1us。

4、根据n_list计算业务的节点时延：

节点所处位置节点时延构成n₄源T_switch+T_encap+T_coden₅中间T_throughn₆中间T_throughn₁宿T_switch+T_decap+T_decode

上述各取值说明如下：

(1)OTN设备的电交换时延和光穿通时延与具体的设备能力有关，此处取值为T_switch＝2us、T_through＝0.05us；

(2)本例中设备能力为100Gbps，业务带宽为1000MHz，无须对业务进行拆分。

具体的业务映射路径为traffic→ODU0→ODU1→OTU1，即业务映射复用级数u＝3，故T_encap＝T_decap＝0.512×3＝1.536us。

(3)本例中选用的FEC算法在长距/超长距传送场景下针对不同业务传输速率不同，其收发设备总体时延实测值如下表所示：

本例中业务封装映射至OTU1，即在OTN线路侧的传输速率为2.5Gbps，故有收发设备总体时延之和T_code+T_decode＝149.4us。

即，通过计算可得该条业务的端到端节点总时延为：

T_n＝2×T_switch+2×T_through+T_encap+T_decap+T_code+T_decode

＝2×2+2×0.05+1.536+1.536+149.4＝156.572us

5、计算得到该条业务的总时延：

T_t＝T_l+T_n＝1750.1+156.572＝1906.672us。

实施例1为本发明一种降低光传送网端到端时延的网络分域方法的具体实施案例。实施例2、3为本发明中采用的一种分域路由计算方法和一种OTN端到端业务时延计算方法的具体实施案例。从实施例1中步骤5所示表格中的数据可以看出，不同的分域方案将对网络的端到端平均时延产生不同的影响，当网络分域及中心节点选择合理时，可有效降低网络的端到端时延值。从实施例1最终的结果可以看出，通过本发明一种降低光传送网端到端时延的网络分域方法，可得到最佳的网络分域方案，使网络的平均端到端时延最优，网络的时延性能得以提升，能够更好地保障业务的时延需求。