一种容量相对最小影响波长分配算法

摘要

本发明涉及光通信技术领域，尤其涉及底层光网络中的一种容量相对最小影响波长分配算法，它通过步骤S101至步骤S112实现技术方案，利用容量相对最小影响波长分配算法进行波长分配时，有效的避免了当前波长分配造成某些路径在某些波长上无可用信道的情况，致使其传送能力丧失。由此可见容量相对最小影响波长分配算法充分考虑当前波长分配对于其他可能到达的业务请求的影响，使得算法能够更加合理的为请求业务分配波长，以达到优化网络整体性能的要求。

主权项

1.一种容量相对最小影响波长分配算法，其特征是：包括如下步骤：步骤S101中，光网络中业务请求到达，网络入口节点获取所述业务请求的源/宿节点地址信息和所占用信道数的信息；步骤S102中，根据获取的源/宿节点地址信息，采用固定选路的方法进行路由选择，得到路由路径；步骤S103中，根据步骤S102得到的路由路径判断路由路径上各波长是否有可用信道；如果有转步骤S111，如果没有转步骤S104；步骤S104中，根据步骤S101中获取的业务请求占用信道数，计算受到当前波长分配影响之后各条路径在各个波长上的受影响后可用信道数P′_c(p_k,λ_i)；步骤S105中，依据可用信道数P_c′(p_k,λ_i)，计算各波长情况下的“受影响路径集合”I(p^*,λ_i)；步骤S106中，计算“受影响路径集合”I(p^*,λ_i)内各条路径在各个波长上的瓶颈链路个数；步骤S107中，依据可用信道数P′_c(p_k,λ_i)和“受影响路径集合”I(p^*,λ_i)的基础上，求出各个波长情况下的“影响可用信道数”C(p^*,λ_i)的值；步骤S108中，依据瓶颈链路个数和“影响可用信道数”C(p^*,λ_i)，求出各个波长情况下的“基于容量的影响因子”C_BR(p^*,λ_i)的值；步骤S109中，根据各波长“基于容量的影响因子”C_BR(p^*,λ_i)值由大到小，对各波长进行排序；步骤S110中，将“基于容量的影响因子”C_BR(p^*,λ_i)值最大的波长分配给到达业务，建立光路径之后转步骤S112；步骤S111中，根据S103的判断得到，在该业务请求所经过的路径各波长上均没有可用信道数，则拒绝该业务请求，该业务请求建立光路链接请求失败；步骤S112，重新返回步骤S101；所述的步骤S106中波长上瓶颈链路个数的定义是：如果：L_c(l_ij,λ_i)=P_c(p,λ_i)    （公式2）L_c(l_ij,λ_i)为链路l_ij上波长λ_i的当前可用信道数；P_c(p,λ_i)为路径p在波长λ_i上的可用信道数；则称l_ij为路径p上的瓶颈链路，波长上的瓶颈链路由下式进行计算：$\underset{p_k\in I(p^{*},{\lambda }_i)}{\Sigma }\left(\underset{l_{\mathrm{ij}}L\left(p_k\right)\cap L\left(P^{*}\right)}{\Sigma }D(L_c(l_{\mathrm{ij}},{\lambda }_i),P_c(p_k,{\lambda }_i))\right)$    （公式3）其中函数D（A，B）函数定义如下：（公式4）所述的步骤S107中影响可用信道数C(p^*,λ_i)定义为：受影响路径集合内的路径，在受到当前波长分配影响之后的路径上可用信道数之和：$C(p^{*},{\lambda }_i)=\underset{p\in I(p^{*},{\lambda }_i)}{\Sigma }{p}_c^{\prime }(p,{\lambda }_i)$    （公式5）所述的步骤S108中基于容量的影响因子的定义如下，一条路径p^*在λ_i上的“基于容量的影响因子”C_BR(p^*,λ_i)，是p^*在λ_i上的影响可用信道数C(p^*,λ_i)与p^*的“受影响路径集合”I(p^*,λ_i)内的路径p在λ_i上遭遇的瓶颈链路总数的比值：$C_{\mathrm{BR}}(p^{*},{\lambda }_i)=\frac{\underset{p\in I(p^{*},{\lambda }_i)}{\Sigma }{p}_c^{\prime }(p_k,{\lambda }_i)}{\underset{p_k\in I(p^{*},{\lambda }_i)}{\Sigma }\left(\underset{l_{\mathrm{ij}}\in L\left(p_k\right)\cap L\left(P^{*}\right)}{\Sigma }D(L_c(l_{\mathrm{ij}},{\lambda }_i),P_c(p_k,{\lambda }_i))\right)}$    （公式6）所述的选择“基于容量的影响因子”C_BR(p^*,λ_i)值最大的波长分配给p^*，可用下式描述：${\max }_{{\lambda }_i\in A\left(P^{*}\right)}{C}_{\mathrm{BR}}(p^{*},{\lambda }_i)=\frac{\underset{p\in I(p^{*},{\lambda }_i)}{\Sigma }{p}_c^{\prime }(p_k,{\lambda }_i)}{\underset{p_k\in I\left(p^{*},{\lambda }_i\right)}{\Sigma }\left(\underset{l_{\mathrm{ij}}\in L\left(p_k\right)\cap L\left(P^{*}\right)}{\Sigma }D(L_c(l_{\mathrm{ij}},{\lambda }_i),P_c(p_k,{\lambda }_i))\right)}$    （公式7）所述的步骤S102中固定选路的方法，是指为每一个相应的源宿节点对之间计算得到一条唯一的固定的路由路径，当业务到达后，入口节点分析其所携带的源宿节点地址信息，确定业务所经过的路由路径；所述的“受影响路径集合”I(p^*,λ_i)表示给路径p^*分配波长λ_i时，p^*的“邻域”中在波长λ_i上可用信道数受到影响的路径的集合，在这里“受到影响”主要是指路径在波长上的可用信道数发生改变，下式为I(p^*,λ_i)的数学定义公式：$\left\{\begin{array}{c}{P}_c^{\prime }(p_i,{\lambda }_i)<P_c(p_i,{\lambda }_i),p_i\in I(p^{*},{\lambda }_i)\\ P_c^{\prime }(p_i,{\lambda }_i)=P_c(p_i,{\lambda }_i),p_i\notin I(p^{*},{\lambda }_i)\end{array}\right.$    （公式1）这里I(p^*,λ_i)∈G(p^*)；G(p^*)为路径p^*的“邻域”；由2根光纤组成且每根光纤包含2个波长的网络的一种容量相对最小影响波长分配算法：步骤S301中，光网络业务到达，获取的地址信息，源节点为2，目的节点为5；获得占用信道信息，得到业务请求占用1个信道；步骤S302中，通过获取到达业务地址信息得到利用固定路由方法，得到业务经过的路由路径为p₁（2～5），从节点2到达节点5，经过节点2、节点3、节点4、节点5；与p₁有共享链路的路径包括p₂（1～3），从节点1到达节点3，经过节点1、节点2、节点3以及p₃（3～6），从节点3到达节点6达，经过节点3、节点4、节点5、节点6；通过获得占用信道信息得到，业务请求占用1个信道；步骤S303中，计算当前各条路径在各个波长上的可用信道数，p₁经过从节点2到节点5之间的链路记为l₂₃，l₃₄和l₄₅；这些链路在波长λ₀上相应的可用信道数为L_c(l₂₃,λ₀)=2，L_c(l₃₄,λ₀)=2，L_c(l₄₅,λ₀)=2；因为路径上可用信道数所以路径p₁在波长λ₀上的可用信道数P_c(p₁,λ₀)=2；同理可得P_c(p₂,λ₀)=2，P_c(p₃,λ₀)=2；P_c(p₁,λ₁)=1，P_c(p₂,λ₁)=1，P_c(p₃,λ₁)=1；步骤S304中，分别计算将波长λ₀和λ₁分配给路径p₁后，受到影响之后p₂和p₃分别在波长λ₀和λ₁上的可用信道数；在将λ₀分配给p₁后，链路l₃₄，l₄₅和l₅₆在波长λ₀上相应的可用信道数减少1，变为L_c(l₂₃,λ₀)=1，L_c(l₃₄,λ₀)=1和L_c(l₄₅,λ₀)=1；这样，p₁在λ₀上的影响后可用信道数P′_c(p₁,λ₀)=1，P′_c(p₂,λ₀)=1，P′_c(p₃,λ₀)=1；同理，P′_c(p₁,λ₁)=0，P′_c(p₂,λ₁)=0，P′_c(p₃,λ₁)=1；步骤S305中，求受影响路径集合I(p₁,λ_i)，在波长λ₀情况下，有P′_c(p₁,λ₀)<P_c(p₁,λ₀)，P′_c(p₂,λ₀)<P_c(p₂,λ₀)和P′_c(p₃,λ₀)<P_c(p₃,λ₀)，所以I(p₁,λ₀)={p₁,p₂,p₃}；同理得到I(p₁,λ₁)={p₁,p₂}；步骤S306中，计算p₁、p₂、p₃和p₄分别在波长λ₀和λ₁上的瓶颈链路数；$\underset{l_{\mathrm{ij}}\in L\left(p_1\right)\cap L\left(P_1\right)}{\Sigma }D(L_c(l_{\mathrm{ij}},{\lambda }_0),P_c(p_1,{\lambda }_0))=3,$$\underset{l_{\mathrm{ij}}\in L\left(p_2\right)\cap L\left(P_1\right)}{\Sigma }D(L_c(l_{\mathrm{ij}},{\lambda }_0),P_c(p_2,{\lambda }_0))=1,$所以在波长λ₀上总的瓶颈链路数为3+1+2=6，其中p₁,p₂和p₃均属于受影响路径集合；同理得到在波长λ₁上总的瓶颈链路数为1+1=2；步骤S307中，计算影响可用信道数C(p₁,λ_i)，利用公式得到C(p₁,λ₀)=1+1+1=3；C(p₁,λ₁)=0+0=0；步骤S308中，计算容量的影响因子C_BR(p₁,λ_i)，C_BR(p₁,λ₀)等于C(p₁,λ₀)除以波长λ₀上总的瓶颈链路数，即C_BR(p₁,λ₀)=3/6=0.5；同理得到C_BR(p₁,λ₁)=0/2=0；步骤S309中，选择C_BR(p₁,λ_i)最大的波长，将其分配给路径p₁；通过比较C_BR(p₁,λ₁)最大，所以将波长λ₀分配给路径p₁，建立光路径。