一种改进的启发式P圈构造算法

1、一种改进的启发式P圈构造算法     摘 要:原有启发式P圈构造算法Grow没有考虑到在对基本圈上的一条边扩张时可能会抑制其他边的扩张,从而失去一些先验效率较高的P圈。针对这一缺点对Grow算法进行了改进。改进后的算法根据所有的圈上边扩张后得到的P圈先验效率的高低顺序,优先选择引入的P圈具有最高先验效率的边进行扩张,因此每次扩张都最大可能地提高P圈的先验效率,而且P圈平均跳数基本不变。仿真结果表明,此算法可以在减少备选P圈数量的同时,提高网络的资源利用率。 关键词:光网络; 保护; 生存性; 预置圈 Improved heuristic alg

2、orithm for generating P-cycles Abstract:Since the existing heuristic algorithm named Grow did not consider that expansion on a cycle-link might restrict expansion on another one, therefore some P-cycles with high AE might be lost. For this reason, this paper improved Grow algorithm. Among all the on

3、-cycle spans, the improved algorithm first chose the one which could get the P-cycle with the highest AE after expansion, so AE of P-cycle would be increased as high as possible, and average number of hops was more or less the same with Grows. Finally, the simulation results show that the algorithm

4、can reduce the number of candidate P-cycles, and at the same time achieve better capacity utilization than Grow. Key words:optical network; protection; survivability; preconfiguration cycle 自从波分复用技术广泛应用以来,通信网络的容量大幅度提高1,给人们生活中的信息传递带来了速度上的飞跃,但同时也带来很大的风险,一旦网络中断,其造成的损失可能是灾难性的。因此网络生存性自然成为所有人关心的问题。在网络生存性技

5、术中,恢复时间和资源利用率是最重要的两个评价标准。在已有的生存性技术中,环网可以实现快速的保护,但是资源利用率较低;格状网有着较好的资源利用率,恢复时间却远大于环网。基于将两者优点结合起来的考虑,1998年,Grover等人2提出了P圈的概念,P圈是利用空闲资源预先在网络中配置好的圈状结构,P圈和环网中的自愈环最大的不同是P圈不但可以提供圈上边的保护,而且可以提供跨接边的保护。 如图1所示,图中线条加粗部分是利用空闲资源配置好的P圈A-B-C-F-D-E-A。在图2中,当跨接边AF失效时,P圈可以同时有两条通路A-B-C-F和A-E-D-F提供保护;在图3中,当圈上边AB失效时,P圈可以实现像

6、自愈环一样的自动倒换来保护A-B的通路。因此P圈可以为圈上边提供一倍业务的保护,并保护跨接边上两倍的业务。P圈在保留了环网快速保护速度的同时提高了资源利用率,发展前景十分看好。 1 相关工作 P圈实用化的重点和难点在于如何利用空闲资源进行配置,以取得最好的保护效果,这是一个最优化的问题。P圈概念提出以来,国内外学者在关于P圈配置的问题上进行了很多研究,提出了很多方法,这些方法大致可以分为三类:a)完全最优化方法,主要思想是先枚举网络拓扑中所有简单圈作为备选P圈,再利用整数线性规划(ILP)得到最优化的解,如文献2等。该方法对于小型网络可以使用,当网络节点和链路数量很大时,计算所有简单圈并且再去

7、找到最优化的解是非常复杂和困难的,需要耗费很长时间,因此这种方法不适合大型网络。b)启发式算法与最优化方法结合,如文献3等。该算法是指根据约束条件找到其中一部分性能比较好的圈,因此运算速度比传统的枚举法快得多,构造的圈性能良好。此类方法先利用启发式算法在网络拓扑中构造一定量的备选圈,然后利用这些备选圈进行最优化组合得到最优解。这仍然要用到线性规划(LP),需要大量的计算时间,不利于网络扩展。c)完全启发式算法,先利用启发式算法构造出性能较好的一定量的备选圈,再结合实际网络中工作容量将可以实际提供保护能力较大的备选圈优先配置,如文献4等。文献5提出了一种新的启发式算法,将第一步构造备选P圈和第二

8、步选择P圈结合为一步,根据实际网络中P圈的冗余率来选择冗余率最小的P圈,可以减少配置P圈的数量并提高资源利用率;但这种方法的整体性较差,算法应用尚未成熟。 在已经提出的这些启发式算法里,2003年Stamatalakis等人4提出的CIDA-Grow算法计算时间极少,资源利用率接近最优化的结果。其中Grow算法是用来构造备选P圈,CIDA算法是用来配置P圈。笔者在对Grow算法的研究中发现,Grow算法在基本圈的扩张问题上没有考虑到边的扩张顺序对最终结果的影响,而边的扩张顺序不同,最终结果也是不同的。为了更好地选择扩张边的顺序,本文提出了一种改进的算法mateGrow。 2 MateGrow算

9、法的提出 2.1 P圈的评价标准 为了量化单个P圈的保护效率,本文定义一个性能指标6:先验效率AE(P),即这个P圈能保护的所有工作容量和配置这个圈所要消耗网络容量的比值。 AE(P)=isXp,i/is,Xp,i=1Ci(1) 其中:s表示所有链路的集合,Ci表示每条链路上的代价,Xp,i表示这个P圈能够为链路i提供的保护通路的个数。容易知道,当链路i是圈上边时,Xp,i=1;当i是跨接边时,Xp,i=2;当i既不是圈上边也不是跨接边时,Xp,i=0。一个P圈具有比较多的跨接边时,其先验效率AE比较高。 2.2 SLA算法 文献7提出了SLA(straddling link algorith

10、m),主要思想是将一条边i的两个端点作为起点和终点,在这两点之间找出两条节点分离的路,并且这两条路都不包含边i,则这两条节点分离的路首尾连接就成为一个简单P圈,这个P圈至少含有一条跨接边i。SLA的速度很快,产生的P圈数量不超过所有边的数量,但是因为产生的P圈一般只有一条跨接边,其先验效率AE很低。 2.3 SP-Add和Grow算法 基于增加跨接边的考虑,文献4提出了SP-Add和Grow算法,SP-Add算法是在已有的简单圈上进行扩张,将一条圈上边i的两个端点作为起点和终点,找到一条起点到终点的最短路径s,这条路径s与原来的圈是节点分离的;将边i删除,路径s和P圈的剩下部分首尾连接组成了新

11、的P圈,边i变成了跨接边,从而提高了圈的先验效率AE。 Grow主要步骤是这样的:a)用SLA在网络拓扑图中构造一组P圈A;b)对A中的每个P圈上的每条边运行SP-Add算法,得到一组P圈B;c)对于B中的每个P圈,在其圈上的一条边运行SP-Add算法,得到一个新的P圈,这时在这个新的P圈上的一条边上运行SP-Add算法。如果不能得到新的P圈,则接着在下一条边上扩张;如果得到了新的P圈,那么每次得到新的P圈后,都将新的P圈作为扩张使用的基本圈,直到最终的P圈上的任何一条边都不能再构造新的P 圈。在这个过程的中间环节产生的P圈也将被保留,放在最终的备选P圈中。 为了更形象地说明Grow算法,举例

12、如下,在图4中,假设一个基本圈为a-b-e-a,其先验效率AE=3/3=1。在eb边上使用SP-Add算法,得到新的P圈a-b-c-e-a,边eb变成了跨接边,新P圈先验效率AE=6/4=1.5。接着对这个新的P圈上的边bc进行扩张,找不到与原来的圈节点分离的路,可见bc边不能扩张;此时转向下一条边ec,运行SP-Add算法得到又一个新的P圈a-b-c-d-e-a,这时新的P圈上任何一条边都不能再扩张,算法终止。最终的P圈具有两个跨接边be和ce,显然先验效率AE=9/5=1.8,比原来提高了很多。 在上例中,如果在圈a-b-e-a中先选择ae作为扩张边,最终得到的圈为a-f-d-c-e-b-

13、a,其先验效率为2。可见,如果在同一个P圈上选择扩张边的顺序不同,最终结果会有差异,这是因为一个圈上边的扩张可能会抑制另外的边进行扩张。而文献4中提出的Grow算法没有考虑到这一点,在P圈的扩张时没有选择边的顺序,会构造一些质量相对较低的P圈,这样不但增加了备选P圈的数量,也非常可能降低其整体质量。如果要将P圈所有可能的扩展结果都计算出来,又将大大增加计算的时间和P圈数,如何在减少P圈数量的同时增加或不降低其先验效率,本文提出了mateGrow算法,文献8的研究表明,降低P圈的数量可以减少管理上的负担。 2.4 MateGrow算法 MateGrow算法的主要思想是这样的,在对一个P圈扩张时,

14、优先选择引进跨接边较多的边进行扩张。如果引进的跨接边同样多,优先选择引入圈上边较少的边进行扩张。在引入跨接边和圈上边同样多的情况下,优先选择引入所有节点的平均度数较大的边进行扩张。MateGrow算法的主要原理是这样的:在引入跨接边时,引入较多的跨接边,其先验效率AE更大;而跨接边的数量相同时,圈上边较少的P圈先验效率AE更大。当跨接边和圈上边的数量都相等时,度数较大的节点有更多的可能引入新的跨接边。如图2所示,假设以P圈d-c-e-d为基本圈,有两条边ce和ed可以进行扩张,引入跨接边都为一条,而ce引入的新的圈上边为两条(cb和be),de则为三条(ea、af和fd)。按照mateGrow

15、算法,用ce进行扩张得到新的P圈d-c-b-e-d,接着以这个新的P圈为基础圈,同样有两条边be和ed可以选择,但是以ed为扩张边计算将得到两条跨接边ed和ab,而用be只能增加一条跨接边be,应该选择ed为扩张边,最终得到的P圈为d-c-b-e-a-f-d。 2.5 MateGrow算法产生备选P圈的性能检验 本文对Italian(21个节点36条边)、COST239(11个节点26条边)、NSF(14个节点21条边)和USA(28个节点45条边)四种网络进行构造备选P圈的仿真,步骤如下:a)对网络拓扑运行SLA算法产生一组P圈A;b)对A中每个P圈上的每条圈上边运行SP-Add算法得到一组

16、P圈B;c)对B中每个P圈运行mateGrow算法得到一组P圈C1。作为对比,同样运行Grow算法得到另外一组P圈C2,Grow算法中扩张边的顺序是顺时针或者逆时针。因为a)b)产生的P圈是相同的,仅比较c)产生的P圈C1、C2。表1中的代价代表实际的物理距离。 在表1中可以看到,NSF网络中mateGrow和Grow算法得到的P圈数量和质量是一样的,这是因为NSF网络的节点和边的数量较少,在扩张时没有很多选择空间。表2的Italian网络中,mateGrow算法得到P圈数量减少了三分之一的情况下,平均AE仍然稍微高于Grow,而且跳数和代价均少于Grow算法。在USA、COST239中,如表

17、3和4,mateGrow算法的优势更加明显,在P圈数量减少的情况下,平均AE高于Grow算法,圈平均代价相对较低,只是COST239中的平均跳数稍高一点。以上所得到的结果是因为在圈扩张时选择了质量较高的P圈,而丢弃了质量相对较低的P圈,不像Grow算法那样没有选择地进行扩张。MateGrow算法选择较好的边进行扩张可以保证每次所得到的P圈都是这次计算的最佳选择,该理论分析和计算的结果是一致的。 3 容量分配的仿真及数据分析 P圈的先验效率只表示其潜在的保护能力。在实际网络中,P圈的保护能力取决于其保护的实际工作容量和自身配置所消耗的空闲容量的比值。本文定义一个指标保护效率9ER(P): ER(

18、P)=ilWp,i/ilSp,i(2) 其中:Wp,i表示当前情况下链路i上的可以被该P圈保护的工作流量,Sp,i表示配置此P圈在链路i上所消耗的空闲容量。利用保护效率的大小顺序就可以选择保护效率高的P圈优先配置到网络中去。文献4提出的CIDA算法正是基于这样的原理,这是一种启发式算法,耗时短,效果接近最优化的解法。 现在使用mateGrow和Grow算法构造的P圈,分别都加上SLA算法、最小圈算法4产生的P圈作为两组备选P圈,再用CIDA算法进行仿真。在USA、Italian、COST239中,网络连接的需求是任意的,每条边上的工作流量的最高限制为20,分别取5组任意的网络连接需求,将P圈配

19、置到网络中去,保证工作容量的100%保护。假设空闲容量是足够的,容量以波长为单位。两组算法分别记为CIDA-Grow和CIDA-mateGrow。 在表5中看到,要对Italian网络的工作流量提供100%的保护,用CIDA-mateGrow和CIDA-Grow所需要的空闲容量相比,除第三组mateGrow的223略多于Grow的221以外,其他几组都少于后者,整体需要的空闲容量显然更少;mateGrow算法少用了19个波长,在实际配置的P圈数量上,两者总体上相差不大,前者比后者少用一个圈。表6、7中显示的结果与表5中相似,只有在个别组中CIDA-Grow算法比CIDA-mateGrow有非常

20、微小的优势。但总体来说,mateGrow算法产生的P圈的性能要好于Grow算法,mateGrow算法分别少用了5和19个波长。不同网络中mateGrow算法比Grow算法节省资源的比例是不同的,因为不同网络的度数不同,在圈扩张时所具有的选择空间不同,这符合理论分析,可见,用mateGrow算法构造的备选P圈多数情况下可以提高资源利用率。 4 结束语 Grow算法在构造P圈时具有速度快、效率高的优点,但Grow算法没有考虑扩张边的顺序选择对于结果的影响。本文提出的mateGrow算法是在Grow算法的基础上改进的,它优先选择引入先验效率较高的边去扩张,这样做的好处在于:a)每次扩张都选择了先验效

21、率最高的P圈,提高了备选P圈整体的先验效率;b)丢弃了一些先验效率较低的P圈,减少了备选P圈的数量;c)本算法没有以增加计算量或者增加备选P圈的平均跳数作为代价,相反多数情况下会减少其平均跳数。仿真结果表明,用mateGrow产生的备选P圈来进行容量配置,可以得到好于Grow算法的资源利用率。 参考文献: 1韦乐平.光网络的发展、演进和面临的挑战J.中兴通讯技术,2002,8(4):1-5. 2GROVERW D, STAMATELAKIS D. Cycle-oriented distributed preconfiguration: ring-like speed with mesh-lik

22、e capacity for self-planning network restorationC/Proc of IEEE International Conference on Communications. Atlanta: IEEE Press,1998: 537-543. 3KANG B, HABIBI D, LO K, et al. An approach to generate an efficient set of candidate P-cycles in WDM Mesh networksC/Proc of IEEE Asia-Pacific Conference on C

23、ommunications. 2006: 1-5. 4DOUCETTE J, HE D, GROVER W D, et al. Algorithmic approaches for efficient enumeration of candidate P-cycles and capacitated P-cycle network designC/Proc of the 4th International Workshop on Design ofReliable Communication Networks. 2003:212-220. 5DRID H, COUSIN B, LAHOUD S

24、, et al.Multi-criteria P-cycle network designC/Proc of the 33rd IEEE Conference on Local Computer Networks. 2008: 361-366. 6GROVER W D, DOUCETTE J. Advances in optical networks design with P-cycles: joint optimization and pre-selection of candidate P-cyclesC/Proc of IEEE/LEOS Summer Topical Meeting.

25、 2002:49-50. 7ZHANG Han-xi, YANG O.Find protection cycles in DWDM networksC/Proc of IEEE International Conference on Communication. 2002:2756-2760. 8ONGUETOU D P, GROVER W D.P-cycle network design: from fewest in number to smallest in sizeC/Proc of International Workshop on Design of Reliable Commun

26、ication Networks. 2007:3161-3168. 9ZHANG Zhen-rong, ZHONG Wen-de, MUKHERJEE B. A heuristic method for design of survivable WDM network with P-cyclesJ. IEEE Communications Letters, 2004, 8(7): 467-469. 参考文献: 1韦乐平.光网络的发展、演进和面临的挑战J.中兴通讯技术,2002,8(4):1-5. 2GROVERW D, STAMATELAKIS D. Cycle-oriented distri

27、buted preconfiguration: ring-like speed with mesh-like capacity for self-planning network restorationC/Proc of IEEE International Conference on Communications. Atlanta: IEEE Press,1998: 537-543. 3KANG B, HABIBI D, LO K, et al. An approach to generate an efficient set of candidate P-cycles in WDM Mes

28、h networksC/Proc of IEEE Asia-Pacific Conference on Communications. 2006: 1-5. 4DOUCETTE J, HE D, GROVER W D, et al. Algorithmic approaches for efficient enumeration of candidate P-cycles and capacitated P-cycle network designC/Proc of the 4th International Workshop on Design ofReliable Communicatio

29、n Networks. 2003:212-220. 5DRID H, COUSIN B, LAHOUD S, et al.Multi-criteria P-cycle network designC/Proc of the 33rd IEEE Conference on Local Computer Networks. 2008: 361-366. 6GROVER W D, DOUCETTE J. Advances in optical networks design with P-cycles: joint optimization and pre-selection of candidat

30、e P-cyclesC/Proc of IEEE/LEOS Summer Topical Meeting. 2002:49-50. 7ZHANG Han-xi, YANG O.Find protection cycles in DWDM networksC/Proc of IEEE International Conference on Communication. 2002:2756-2760. 8ONGUETOU D P, GROVER W D.P-cycle network design: from fewest in number to smallest in sizeC/Proc o

31、f International Workshop on Design of Reliable Communication Networks. 2007:3161-3168. 9ZHANG Zhen-rong, ZHONG Wen-de, MUKHERJEE B. A heuristic method for design of survivable WDM network with P-cyclesJ. IEEE Communications Letters, 2004, 8(7): 467-469. 参考文献: 1韦乐平.光网络的发展、演进和面临的挑战J.中兴通讯技术,2002,8(4):1

32、-5. 2GROVERW D, STAMATELAKIS D. Cycle-oriented distributed preconfiguration: ring-like speed with mesh-like capacity for self-planning network restorationC/Proc of IEEE International Conference on Communications. Atlanta: IEEE Press,1998: 537-543. 3KANG B, HABIBI D, LO K, et al. An approach to gener

33、ate an efficient set of candidate P-cycles in WDM Mesh networksC/Proc of IEEE Asia-Pacific Conference on Communications. 2006: 1-5. 4DOUCETTE J, HE D, GROVER W D, et al. Algorithmic approaches for efficient enumeration of candidate P-cycles and capacitated P-cycle network designC/Proc of the 4th Int

34、ernational Workshop on Design ofReliable Communication Networks. 2003:212-220. 5DRID H, COUSIN B, LAHOUD S, et al.Multi-criteria P-cycle network designC/Proc of the 33rd IEEE Conference on Local Computer Networks. 2008: 361-366. 6GROVER W D, DOUCETTE J. Advances in optical networks design with P-cyc

35、les: joint optimization and pre-selection of candidate P-cyclesC/Proc of IEEE/LEOS Summer Topical Meeting. 2002:49-50. 7ZHANG Han-xi, YANG O.Find protection cycles in DWDM networksC/Proc of IEEE International Conference on Communication. 2002:2756-2760. 8ONGUETOU D P, GROVER W D.P-cycle network desi

36、gn: from fewest in number to smallest in sizeC/Proc of International Workshop on Design of Reliable Communication Networks. 2007:3161-3168. 9ZHANG Zhen-rong, ZHONG Wen-de, MUKHERJEE B. A heuristic method for design of survivable WDM network with P-cyclesJ. IEEE Communications Letters, 2004, 8(7): 46

37、7-469. 参考文献: 1韦乐平.光网络的发展、演进和面临的挑战J.中兴通讯技术,2002,8(4):1-5. 2GROVERW D, STAMATELAKIS D. Cycle-oriented distributed preconfiguration: ring-like speed with mesh-like capacity for self-planning network restorationC/Proc of IEEE International Conference on Communications. Atlanta: IEEE Press,1998: 537-543.

38、 3KANG B, HABIBI D, LO K, et al. An approach to generate an efficient set of candidate P-cycles in WDM Mesh networksC/Proc of IEEE Asia-Pacific Conference on Communications. 2006: 1-5. 4DOUCETTE J, HE D, GROVER W D, et al. Algorithmic approaches for efficient enumeration of candidate P-cycles and ca

39、pacitated P-cycle network designC/Proc of the 4th International Workshop on Design ofReliable Communication Networks. 2003:212-220. 5DRID H, COUSIN B, LAHOUD S, et al.Multi-criteria P-cycle network designC/Proc of the 33rd IEEE Conference on Local Computer Networks. 2008: 361-366. 6GROVER W D, DOUCE

40、TTE J. Advances in optical networks design with P-cycles: joint optimization and pre-selection of candidate P-cyclesC/Proc of IEEE/LEOS Summer Topical Meeting. 2002:49-50. 7ZHANG Han-xi, YANG O.Find protection cycles in DWDM networksC/Proc of IEEE International Conference on Communication. 2002:2756

41、-2760. 8ONGUETOU D P, GROVER W D.P-cycle network design: from fewest in number to smallest in sizeC/Proc of International Workshop on Design of Reliable Communication Networks. 2007:3161-3168. 9ZHANG Zhen-rong, ZHONG Wen-de, MUKHERJEE B. A heuristic method for design of survivable WDM network with P

42、-cyclesJ. IEEE Communications Letters, 2004, 8(7): 467-469. 参考文献: 1韦乐平.光网络的发展、演进和面临的挑战J.中兴通讯技术,2002,8(4):1-5. 2GROVERW D, STAMATELAKIS D. Cycle-oriented distributed preconfiguration: ring-like speed with mesh-like capacity for self-planning network restorationC/Proc of IEEE International Conference

43、on Communications. Atlanta: IEEE Press,1998: 537-543. 3KANG B, HABIBI D, LO K, et al. An approach to generate an efficient set of candidate P-cycles in WDM Mesh networksC/Proc of IEEE Asia-Pacific Conference on Communications. 2006: 1-5. 4DOUCETTE J, HE D, GROVER W D, et al. Algorithmic approaches f

44、or efficient enumeration of candidate P-cycles and capacitated P-cycle network designC/Proc of the 4th International Workshop on Design ofReliable Communication Networks. 2003:212-220. 5DRID H, COUSIN B, LAHOUD S, et al.Multi-criteria P-cycle network designC/Proc of the 33rd IEEE Conference on Local

45、 Computer Networks. 2008: 361-366. 6GROVER W D, DOUCETTE J. Advances in optical networks design with P-cycles: joint optimization and pre-selection of candidate P-cyclesC/Proc of IEEE/LEOS Summer Topical Meeting. 2002:49-50. 7ZHANG Han-xi, YANG O.Find protection cycles in DWDM networksC/Proc of IEEE

46、 International Conference on Communication. 2002:2756-2760. 8ONGUETOU D P, GROVER W D.P-cycle network design: from fewest in number to smallest in sizeC/Proc of International Workshop on Design of Reliable Communication Networks. 2007:3161-3168. 9ZHANG Zhen-rong, ZHONG Wen-de, MUKHERJEE B. A heurist

47、ic method for design of survivable WDM network with P-cyclesJ. IEEE Communications Letters, 2004, 8(7): 467-469. 参考文献: 1韦乐平.光网络的发展、演进和面临的挑战J.中兴通讯技术,2002,8(4):1-5. 2GROVERW D, STAMATELAKIS D. Cycle-oriented distributed preconfiguration: ring-like speed with mesh-like capacity for self-planning networ

48、k restorationC/Proc of IEEE International Conference on Communications. Atlanta: IEEE Press,1998: 537-543. 3KANG B, HABIBI D, LO K, et al. An approach to generate an efficient set of candidate P-cycles in WDM Mesh networksC/Proc of IEEE Asia-Pacific Conference on Communications. 2006: 1-5. 4DOUCETTE

49、 J, HE D, GROVER W D, et al. Algorithmic approaches for efficient enumeration of candidate P-cycles and capacitated P-cycle network designC/Proc of the 4th International Workshop on Design ofReliable Communication Networks. 2003:212-220. 5DRID H, COUSIN B, LAHOUD S, et al.Multi-criteria P-cycle netw

50、ork designC/Proc of the 33rd IEEE Conference on Local Computer Networks. 2008: 361-366. 6GROVER W D, DOUCETTE J. Advances in optical networks design with P-cycles: joint optimization and pre-selection of candidate P-cyclesC/Proc of IEEE/LEOS Summer Topical Meeting. 2002:49-50. 7ZHANG Han-xi, YANG O.

51、Find protection cycles in DWDM networksC/Proc of IEEE International Conference on Communication. 2002:2756-2760. 8ONGUETOU D P, GROVER W D.P-cycle network design: from fewest in number to smallest in sizeC/Proc of International Workshop on Design of Reliable Communication Networks. 2007:3161-3168. 9ZHANG Zhen-rong,