CN101611592B

CN101611592B - 光网络中的光信号的动态路由

Info

Publication number: CN101611592B
Application number: CN2006800569209A
Authority: CN
Inventors: 亚历山德·德亚历山德; M·穆拉托里
Original assignee: Telecom Italia SpA
Current assignee: TIM SpA
Priority date: 2006-12-22
Filing date: 2006-12-22
Publication date: 2012-12-05
Anticipated expiration: 2026-12-22
Also published as: US20100086306A1; US8369707B2; CN101611592A; WO2008077420A1; EP2127259A1; EP2127259B1; ATE485657T1; DE602006017755D1

Abstract

公开了一种在包括多个节点的光网络中动态路由光信号的方法，包括：执行核心算法(410)，接收有关源节点(Sn)、目的地节点(Dn)和网络的拓扑结构(To)的输入信息，并提供包括多个节点和连接所述节点的多条弧线的约束最短路径树作为输出，该最短路径树包括光信号沿其累积的有效衰减最多等于预定极限的至少一条分支，该至少一条分支包括具有相应端节点和相关一组波长的端弧线；对于每条端弧线和每个波长，检验(420)相应端节点是否是目的地节点，它是否包括波长转换器，或它是否通过所述波长与进一步的节点连接；如果这些条件没有一个得到满足，则通过排除所述波长(430)来修改与弧线相关联的一组波长，因此更新拓扑结构；以及利用更新的拓扑结构来重新执行核心算法(410)。

Description

光网络中的光信号的动态路由

技术领域

本发明涉及光网络中的光信号的动态路由。

背景技术

在电信网络的复杂情形下，在过去几年中本身已经确立了强化在过去十年中已经在使用的某些技术(IP和以太网)和简化协议栈的趋势，利用新功能(基于以太网的伪线、基于MPLS-TE的QoS)来充实已有的技术，以实现维护起来更简单和更便宜的网络。

然而，在不断搜索旨在遏制网络运行费用(OPEX)的解决方案和在市场上迅速引入新服务的可能性的市场中，不乏创新的解决方案，这些解决方案的繁荣受到许多服务被广泛移植到IP的驱动。ASON/GMPLS(自动交换光网络/通用多协议标记交换)技术代表最近几年的创新解决方案之一，它提供的服务的灵活性、动态特征、和自动化与网络运行商的新出现需求融合得相当好。

运行商和ASP(应用服务提供商)所提供的服务会聚于IP以及广泛使用IP协议用于计算机应用的迄今强化趋势已经引起了分组业务的增长，分组业务的特性难以规范化，尤其关于具有极度不同需求的多个应用的共存。

ASON/GMPLS技术似乎适合提供既灵活又动态的宽带传输网络，由于允许通过采用控制体系结构和特殊信令、路由和发现机制来和谐地使用已有网络技术，ASON/GMPLS技术能够支持IP业务可变性。

例如，可以集成基于分组的网络、基于时分的网络、基于波长交换的网络等。这些技术的每一种都具有充分整合挑战的特性。ASON/GMPLS技术的引入简化了这个过程，例如，利用诸如电路的动态和自动创建、删除和修改的新功能来提高较低的网络水平(基于波长或光纤交换，或时分)。这要求将新的路由机制引入电路世界中，所述新的路由机制不可能代表已经在分组世界中测试过的那些路由机制的简单转置。当它们必须处理诸如在透明/半透明光网络的情况下的新自由度时，这些机制的适应甚至更困难，在透明/半透明光网络中，需要检验光信号没有沿着找到的路由累积过多的降质，并因此在接收器处被正确地解码。

对于本发明来说，“透明光网络”指的是光信号的传输独立于要通过光学层传输的实际数据的特定特性(数字或模拟类型、调制方案、信号格式、位速率)的光网络；“不透明光网络”指的是在沿着连线的(每个)中间节点上利用3R信号再生的光网络；以及“半透明光网络”指的是相对于光传输减损和信号自适应或波长转换要求，尽可能让信号在光域中传播，然后利用3R信号再生来再生信号的光网络。

网络节点体系结构的例子显示在图1中。它包括配备有用于从设备输出/输入到设备的波长的多路复用/多路分用系统M/D₁-M/D₄的多个线路接口I₁-I₄、(透明)波长交换矩阵SM、可以被经过节点的信号访问以恢复它在信号源具有的质量水平的一组再生器3R、如果信号的波长已经在输出接口上使用则可以被经过节点的信号访问的一组波长转换器C、以及用于对输入到节点的信号和它们的精确规范(例如，功率水平)“进行着色”(即，指定严格定义波长)的一组转发器T。

半透明网络的一个例子显示在图2中。它包括：基于边界光学数字交叉连接节点(B-ODXC)的外层，所述边界光学数字交叉连接节点配有转发器T并可选地配有再生器3R和波长转换器C；包括核心光学数字交叉连接节点(C-ODXC)的内层，所述核心光学数字交叉连接节点可选地配有再生器3R和波长转换器C；以及客户设备CE。

至于各种网络节点上再生器和波长转换器的存在，应该认为，可以根据网络规划的结果，以可变数量来配备这些器件(原则上，节点是完全透明的)。而且，它们在网络上的可用性根据网络本身的状态而动态地变化，以及本文给出的路由方法考虑了这种可变性。

因此，在某些网络负载条件下，可以发生再生和/或波长转换功能在所有网络节点上不可用的情形。在这种情形下，由于存在光信号可以在无再生的情况下行进的最大长度，评估新网络路由的可行性是重要的。这个长度取决于许多因素，例如，光纤的类型和长度、交换矩阵的规范、位速率、以及波的数量和它们的波长。由于诸如衰减、色散、非线性效应等的许多物理现象，光信号沿着路由降质。当降质妨碍了在接收器正确重构信号，则需要再生信号。在当前技术状态下，这个过程牵涉到相当昂贵的电子部件。由于这个原因，让网络运行商限制这些资源以及，一般说来，由于它们的高成本而倾向于以有限数量出现在网络上并在下文中被叫做贵重资源的所有那些资源的使用是方便的。

在传统不透明网络(即，节点全部配有再生器的网络)中，每个节点再生接收的光信号。这样，恢复信号在信号源具有的特性，从而使任意路由都是可行的。在这种类型的网络中，由于通过设计保证了每条网络路径的可行性，所以路由机制不考虑物理降质。

为了降低成本，可以构建透明光网络，更确切地说，基于交换光信号而不转换成电形式的节点的那一种光网络。这种类型的电信网络在规模上受到限制，并难以付诸实施。这些局限性通过在网络中引入混合节点，更确切地说，能够以透明方式交换光信号，并当需要时，还能够再生它们或改变波长的节点来克服。这种类型的节点将重要的灵活性引入网络(半透明网络)中，同时也将成本带进来。不过，这种类型的网络也可以与网络规划研究的结果相干地包括完全透明或不透明节点。

用于找出路由和波长的方法一般被叫做“路由和波长指定(RWA)问题”。存在许多旨在以同时方式并通过分解成两个子问题：路由问题和波长指定问题，识别解决这个问题的最佳方式的调查和研究。不过，通常不考虑传输降质。下面提供本领域中的技术状态的小结。

在Li Bo、C.Xiaowen和K.Sohraby发表的文章″Routing andwavelength assignment vs.wavelength conver-ter placement inall-optical networks″，IEEE Optical Communica-tions，pp.S22-S28，Aug.2003中，作者根据搜索一般是链路分离型的k条最短路径的每个源-目的地对之间的一组路径，提出了对RWA问题的解决方案。通过从预先计算的一组路径中选择一条路径，然后从可用的那些波长中指定一个波长(例如，利用首次适合法)，来满足路由请求。与路由相关联的权重不仅取决于波长可用性，而且取决于路径长度。另外，作者建议考虑波长转换器的位置，以便使堵塞的概率最小，并且还建议了用于解决RWA问题的最小堵塞概率优先(MBPF)算法。

在US 6,538,777中，作者提出了根据某种路由之后网络状态的变化而不是根据路由之前的网络状态的路由和波长指定方法。这种手段的目的是获取灵活的网络状态，最小化给定路由的指定排除能够提供一对节点之间的连接的唯一链路的可用性的风险。

在K.Taira、Y.Zhang、H.Takagi和S.K.Das发表的文章″Efficient Lightpath Routing in Wavelength-Routed OpticalNetworks″，ICOIN 2000，LNCS 2343，pp.291-304，2002中，作者提出了解决RWA问题的穷举算法。它首先解决了路由问题，随后解决了波长指定问题。这两个问题被公式化成路由问题，并且在变换与网络相关联的图而获得的相应图上使用最短路径路由技术来解决。

US 2003/0016414提出了考虑光信号在穿过网络传播期间的降质的解决方案。作者指出，就它们的质量下降到某个水平以下之前行进的距离而言，波长具有不同的性能。他们提出了根据在路由阶段识别的路径距离来选择最适合波长的方法。将太长的路径划分成两条或更多条子路径，并且将该方法反复应用于各个分段。这样，就作出了使用最少数量的再生和/或波长转换资源的尝试。该方法应用于交换节点配有波长交换器、和用于再生和/或修改波长的一组再生器和波长转换器的光网络。

Xi Jang和Byrav Ramamurthy的″Interdomain dynamicwavelength routing in next-generation translucent optical internet″，Journal of optical networking，Vol 3，No.3，March 2004(CPA)提出了另一种考虑光信号的物理降质的方法。这种方法关心基于Dijkstra算法(这是用在因特网路由中的最短路径优先(SPF)路由算法的现实世界实现)的叠代过程，Dijkstra算法的成本函数取决于链路的长度、可用再生资源和链路上可用波长的数量。成本函数用参数d来参数化，当搜索路由时，考虑失败叠代的数量L。L的值越高，穿过节点具有更大再生器/波长可用性的解决方案就越有利。

尤其，该文档描述了将域间路由计算分配给域网关的域间动态波长路由方案。域网关上的路由计算被进一步划分成三种功能。首先，域网关使用LRS(本地路由方案)来计算本身与同一域中的每个内部节点之间，以及本身与每个相邻域网关之间的本地路由。其次，下一跳计算功能被用于将这个域的可替代本地路由与相邻域的可替代路由连接，以形成引向希望目的地的下一跳接口。最后，逐跳光路选择功能使用获得的本地和下一跳路由信息来建立域间端到端光路。

发明内容

本申请人已经注意到所有上述解决方案受一些缺陷影响。

关于上面引用的Li Bo等人发表的文章、专利US 6,538,777、和K.Taira等人发表的文章，本申请人观察到，所有所述的解决方案都未考虑信号降质，因此，被证明不适用于透明网络。

至于US 2003/0016414，本申请人观察到，这种方法不能保证路由的可行性(从传输降质的观点来看)，导致极少再生器可用的拥挤网络上的高堵塞概率。

对于上述Xi Jang等人发表的文章，本申请人观察到，这种方法在路由计算中既未考虑网络资源的有效可用性(波长的可用性)也未考虑物理约束的观察(光信号降质、波长连续性等)。路由计算的后面跟着信号质量和波长连续性要求的核实阶段，如果得不到满足，则使当前找到的临时解决方案被放弃，并且使搜索算法借助于新的参数重新开始。该方法在找到解决方案之后或在LMAX次失败叠代之后终止。

此外，本申请人证实，这种方法应用于一些网络拓扑结构表现出下文所述的某些局限性。

让我们首先通过例子考虑图3中的图所代表的网络拓扑结构。可用波长紧靠弧线示出。为了简单起见，让我们假设没有一个节点具有可访问的3R再生器，以及考虑链路长度/降质的参数对于所有链路具有相同值。假设存在节点A与节点E之间的路由请求。在第一种情况下，算法将相同权重指定给所有链路，生成图4的最短路径树。然而，由于波长连续性的条件未得到满足，找到的路由(A-D-E)物理上并不可行。

所考虑的方法通过修改度量并重新运行搜索算法来响应这个状态。然而，对于作出的假设，由于与弧线相关联的权重并不随叠代次数增加而改变，因此，尽管存在两条可行路径：A-C-D-E和A-B-D-E，该算法也坚持相同路线，所以该方法找不到解决方案。

所考虑的方法在处理信号可以在它的传播期间经受的最大降质的约束方面也呈现不令人满意的行为。设L₀是沿着两个节点之间的链路的物理降质的量度(例如，总体代表诸如衰减、色散、非线性现象等的使光信号降质的物理现象的量)，以及3L₀是信息没有损失的最大可接受降质。将如图5所示的拓扑结构作为例子来描述所考虑的方法的行为。作出如下假设：

·由于沿着每条链路可用所有可能波长(在特例中是λ1、λ2和λ3)，所以遵守波长连续性约束；

·节点R是具有再生资源的节点；以及

·节点A是源节点以及G是目的地节点。

该算法的第一次叠代，更确切地说，基于单一权重的指定，在输出中产生如图6所示的解决方案，即，包括两条路径A-C-F-R和A-B-D-E-G。从图中可以推出，沿着路径A-B-D-E-G的解决方案不可行，因为沿着该路径的降质总和(等于4L₀)超过了最大阈值(等于3L₀)。一次又一次地叠代下去，可变权重度量切断与F-R链路有关的权重(最后可以是零)。而与所执行叠代的基数无关，与其它弧线相关联的成本保持不变。与将应用SPF的最后叠代相关联的图形显示在图7中，在F-R链路上具有零权重。

在这种情况下，该方法在输出中也将产生正如已述的那样，由于违反了与最大容许降质相关联的条件而不可行的图6的相同最短路径树。然而，存在不能通过该算法找到的可行路径：路径A-C-F-R-E-G。事实上，两个部分A-C-F-R和R-E-G具有在3L₀的最大阈极限内的各自总降质，并且节点R允许在它们之间再生。

在所示的两个例子中，所考虑的方法不能找到解决方案，因为它构建路由(解决方案)而不考虑物理约束。

所考虑的方法不能找到解决方案的另一个条件是需要跨越相同链路两次的条件。由于所考虑的方法基于相加型的SPF算法，不可以跨越图形的相同分支(即，网络中的相同链路)多于一次。

本发明的目的是，提供解决已知方法的问题的路由方法。通过涉及如所附权利要求书所述的本发明的用于光网络中的光信号的动态路由的方法，来实现这个目的。

本发明分两个阶段实现上述目的：在第一阶段，搜索可行路由，以及在第二阶段，优化沿识别的路由的资源使用。

第一阶段包括线性搜索，如果未成功找到适当路径，则也包括非线性搜索。尤其是，第一阶段包括搜索满足信号降质和波长连续性的物理约束的可能路径。这个阶段包括基于最短路径算法(SPA)的叠代过程，SPA的成本函数取决于在某个时间该解决方案所累积的与如下有关的有效降质：

-最大容许有效信号降质(即，保护信号信息)；

-加入正在进行的解决方案(即，SPF路由过程中的局部解决方案)的最后一个节点与最近的再生节点的距离；

-节点上的可用再生资源；

-链路上的可用波长的数量；以及

-穿过节点的成本。

成本函数还取决于正在评估解决方案的叠代。失败叠代的次数越多，该过程就越有利于波长可用性较大的链路或再生器可用性较大的节点上的解决方案。由该方法提供的解决方案通过构建来满足物理降质约束，因为保证了波长连续性和信号质量要求实现。在这个阶段未找到问题的解决方案的情况下，接着，以稍后详细说明的方式应用非线性搜索过程。

如果找到解决方案，无论是在线性方法的情况下还是在非线性方法的情况下，都跟随第二阶段，以便优化沿着识别的路由的网络资源(选择波长以及分配再生器和波长转换器)。

本发明的技术也可以用于网络规划以及在如此设计的网络的实时路由操作期间应用。

因此，本发明涉及一种在包括多个节点的光网络中动态路由光信号的方法，包括：

·执行最短路径算法，接收有关源节点、目的地节点和网络的拓扑结构的输入信息，并提供包括节点和连接所述节点的弧线的最短路径树作为输出，该最短路径树包括多条分支，光信号沿着所述多条分支累积的有效衰减最多等于预定极限，每条分支包括端节点，以及每个端节点与相应一组波长相关联；

·对于没有波长转换资源的每个端节点和相应一组波长的每个波长，检验所述端节点是否通过所述波长与相应分支之外的至少另一个节点连接；

·对于所述检验的结果对于相应一组波长的至少一个波长为否定的任何端节点，从相应一组波长中排除所述至少一个波长，因此更新拓扑结构；以及

·利用更新的拓扑结构来重新执行最短路径算法。

最好，该方法进一步包括：

·如果所述检验的结果对于所有端节点和相应一组波长的所有波长都是肯定的，则改变参数的值；

·根据所述参数的当前值来更新网络参数，因此更新拓扑结构；

·利用更新的拓扑结构来重新执行最短路径算法。

最好，所述检验是第一次检验，以及该方法进一步包括：

·如果所述第一次检验的结果对于所有端节点和相应一组波长的所有波长都是肯定的，则第二次检验所述端节点的任何一个是否与目的地节点一致；

其中，只有当第二次检验的结果为否定时，才重新执行最短路径算法。

该方法可以进一步包括：

·第三次检验所述参数的当前值是否超过预定阈值；

其中，只有当第三次检验的结果为否定时，才重新执行最短路径算法。

与端节点相关联的一组波长可以包括从源节点到端节点或者由端节点的同一分支和端节点中的波长转换器资源保证波长连续性的所有波长。

执行最短路径算法最好包括通过加入新节点使最短路径树成长。

最好，如果沿着所述分支从源节点到新节点的累积降质损失小于最大容许值，则将新节点加入所述分支。

此外，如果沿着所述分支从源节点到新节点或者由端节点的同一分支和端节点中的波长转换器资源保证波长连续性，则将新节点加入所述分支。

如果沿着所述分支从源节点到新节点的总成本函数相对于其它可能的新节点是最小的，则将新节点加入所述分支。

最好，如果新节点是再生节点，则将累积降质损失取为零。

成本函数最好取决于所述参数。

此外，成本函数最好取决于如下之中的至少一个：

-到新节点的链路中的可用波长；

-新节点中的可用再生资源；

-信号的累积降质损失。

如果信号沿着所述分支的累积降质损失小于极限值，则可以通过第一表达式来计算成本函数，而如果信号沿着所述分支的累积降质损失大于极限值，则可以通过第二表达式来计算成本函数。

第一表达式最好有利于具有较大数量再生资源和可通过较大波长可用性的链路到达的新节点。第二表达式最好有利于事先已知到达再生器的可能性的新节点。

附图说明

·图1是网络节点体系结构的例子；

·图2是半透明网络的例子；

·图3-7、10、11、14-24、26-28和30-33是网络拓扑结构和应用于这样的网络拓扑结构的路由方法的例子；

·图8、9、12、13、25和29是与本发明的方法有关的流程图。

具体实施方式

参照图8，它示出了按照本发明优选实施例的方法的主要步骤的流程图。

该方法的主要阶段如下：

·创建路由数据库(RDB)(方块100)；

·处理路由请求(方块200)；

·计算路由(方块300)；和

·优化沿着所计算路由的资源和指定波长(方块400)。

方块100提供用于创建用于路由搜索的必要初步信息。尤其，方块100包括如下阶段：

·收集网络的拓扑结构信息和节点描述；和

·为部署在网络中的每个同质接口群(即，对于路由来说具有相同特性的接口，例如，TE链路)计算一个向量(一组有序值)，向量的元素量化光信号穿过连接上面的接口群与再生节点的最短路由时所经受的降质。通过应用例如Floyd-Warshall算法或Djistkra算法，应用于每个同质接口群的(按下文所述修改的)最短路径算法(SPA)求解最短路径问题，来获得这些值。光信号在网络上传播期间的总降质被表达成每条链路和节点的成本。如果在SPA计算期间，沿着树的特定分支累积的总成本超过最大允许降质值(对于给定信号，作为例如功率水平、使用的位速率或光波段的函数)，则中断沿着该分支对(SPA的)解决方案的搜索。

在SPA结束时，获得只由成本低于某个阈值的路径组成的约束最短路径树(CSPT)。该成本代表信号穿过链路和节点时遭受的降质。在上面的计算中，利用了考虑上述成本的相加成本函数。

信号沿着给定路由累积的降质(即，沿着路径的总成本)将被叫做“有效距离”。对于给定光信号，可以认为，如果信号为了到达再生节点或目的地节点所必须行进的有效距离低于某个阈值，那么，某条路径是可行的。

为朝向再生节点的每个同质接口群计算的一组有效距离用向量来组织，所述向量向提出的RWA方法提供朝向再生节点的可到达性信息。当光信号的降质达到某个阈值时，也利用那些向量来利于到再生节点的路由。有效距离的计算将在下文作更详细说明。

方块200提供用于处理路由请求。接收的路由请求是将数据从给定源节点S_i(初始源)路由到给定目的地节点D_i(初始目的地)的请求，包括任何信号规范细节和通过适当修改网络拓扑结构或算法的内部参数的路由约束(例如，对节点分离或链路分离路由的请求)。

方块300将在下文作更详细描述，它提供用于两阶段搜索：在第一阶段，通过线性搜索模块来搜索路由；如果未找到路由，则第一阶段后面接着第二阶段，在第二阶段，激活非线性搜索模块用于路由的非线性解决方案。从下文中可明显看出，该方法的不同阶段共享一些功能(即，功能块)。如果找到路由，则在输入中将它传递给包括指定波长和分配再生和波长转换器资源阶段的细化模块(方块400)。

图9更详细地示出了与路由计算有关的方块300的功能。

方块300包括存储上述源节点S_i和目的地节点D_i的第一方块310。

方块310的后面接着方块315，方块315检验源节点S_i和目的地节点D_i是否一致。

如果肯定(源和目的地一致，S_i＝D_i)，那么，存在对路由问题的解决方案，方块315的后面接着方块320，方块320终止方块300的操作并在输出中提供找到的路线(例如，S_i-D_i)。

如果源节点S_i和目的地节点D_i不一致(S_i≠D_i)，则方块315的后面接着方块325，方块325包括将在下文作更详细描述的核心算法(这里和在下文中，用双线框表示)。

方块325试图找出对从源节点S_i到目的地节点D_i的路由问题的线性解决方案。因此，方块325识别线性搜索模块的操作。尤其是，方块325接收源节点S_i、目的地节点D_i、和与网络拓扑结构相关联的图形(存储在RBD中)作为输入，并且输出只由成本低于某个阈值的路径组成的约束最短路径树(CSPT)。成本代表物理减损，以及以保证接收器上的正确信号检测的方式来设置阈值。

在上面的计算中，利用取决于网络状态和路由期间给定临时解决方案的残余有效距离的成本函数。这种手段使某些链路的权重发生变化，有利于到达再生资源。此外，成本函数是参数化的，并且取决于找到解决方案的叠代次数。

将方块325计算的CSPT馈送到方块330，方块330检验目的地节点D_i是否包括在上面的CSPT中。

如果肯定(目的地节点D_i包括在CSPT中)，则方块330的后面接着细化方块335，细化方块335为路由问题的线性解决方案提供细化，否则，方块330的后面接着方块340，方块340根据上面的CSPT激活非线性解决方案搜索。

方块335选择CSPT的包括目的地节点D_i的分支，并且识别沿着那条分支出现的再生器。源-再生器i-...-再生器j-目的地序列(S_i-R_i-...-R_j-D_i)构成所谓“逻辑路径”的路径。

将注意力集中在检测的逻辑路径上，该算法通过优化过程(下文更详细描述的接在方块335之后的方块345)，来确定物理路径，即，代表搜索到的解决方案的从源节点到目的地节点的实际节点和链路序列。这条物理路径可能局部不同于由方块325获得的物理路径。

方块345还在波长连续性方面检验已经找到的路径的可行性。稍后详细描述这种功能。

方块345的后面接着方块348，方块348检验波长连续性是否得到保证。如果否定，则返回错误消息(方块351)。如果肯定，则将找到的路由存储成“基本解决方案”，并且将可变标志设置成值1(方块353)。

方块353的后面接着方块358，正如稍后更详细描述的那样，方块358旨在改善“基本解决方案”。如果方块358找到比“基本解决方案”更好的解决方案，则它将那条路由存储成“改进解决方案”，并且将可变标志设置成值2。

方块358的后面接着方块361，方块361检验是否找到“改进解决方案”。如果肯定，则输出“改进解决方案”(方块363)，否则，输出“基本解决方案”(方块362)。

方块300不在波长、转换和再生资源指定方面细化解决方案。这是在下文中参照图29更详细描述的图8的方块400的目的。

正如前面预期的那样，方块340(在通过核心算法325线性搜索到目的地节点的路由为否定结果的情况下到达的)是通过用虚线方块342整体表示的非线性搜索模块进行的非线性解决方案搜索的第一步。如果在核心算法(方块325)的第一次运行中未找到到目的地的路由，则激活这个非线性解决方案搜索。非线性解决方案搜索包括一次或多次地执行前面所述的核心算法，即进行与方块325相同的动作，这里用方块370表示。方块342进行找出方块325未解决的路由问题的解决方案的非线性操作。

当进入方块340时，识别包括在通过应用核心算法(方块325，或如后所述的方块370)获得的CSPT中的所有再生器R_i。此外，方块340还检验目的地节点是否包括在CSPT中(在如后所述的方块370中执行的核心算法的情况下)。

方块340的后面接着方块355，方块355创建“逻辑分段”，每个逻辑分段由作为一端的源节点S_i或出现在CSPT上的再生器R_y和作为远端的出现在CSPT上的再生器之一构成(例如，S_i-R_i、Si-R_j等，或R_j-R_k，R_j-R_z)。

当在第一次之后的后续叠代中进入方块355时，可能存在远端是目的地节点D_i的逻辑分段(例如，R_k-D_i)。

方块355的后面接着方块360，方块360检验在通过核心算法(方块370)作出的计算步骤中，包括在CSPT中的每个再生器是否起源节点的作用。

如果方块360否定，则从在前面的步骤中计算的并且在核心算法方块中还没有起源节点作用的那些节点当中选择再生器节点R(接在方块360之后的方块365)，以识别朝向目的地节点D_i的解决方案。然后，将所选再生节点R用作源，再次执行核心算法(方块370)，以产生新的CSPT；过程从方块370返回到方块340。

当从方块370进入方块340时，识别并存储包括在CSPT中的再生节点和可能的目的地节点D_i。

如果肯定，方块360的后面接着方块375，方块375检验是否存在包括源S_i的至少一个逻辑分段(S_i-R_i)，以及是否存在包括目的地节点D_i的至少一个逻辑分段(R_i-D_i)。这是存在解决方案的必要(但不充分)条件。

如果这个条件得不到满足，那么，显示错误消息(方块378)，以指示不存在解决方案。

如果这个条件得到满足，那么，方块375的后面接着方块380，方块380计算逻辑路径，即，在源S_i与目的地D_i之间经过再生节点的路由。将不同逻辑分段连接在一起来计算逻辑路径。关于所利用的再生器的数量来排序如此构成的逻辑路径。牵涉到的再生器的数量越大，指定给路径的成本就越大。

方块385检验是否存在至少一条要受到检验的逻辑路径。如果否定，显示错误消息(方块378)，以指示不存在解决方案。如果肯定，方块385的后面接着方块387，方块387考虑最低成本逻辑路径(方块387)。

利用非线性搜索模块找到的解决方案匹配最大降质约束，但不保证沿着源到目的地路径的波长连续性。

方块389进行与方块345相同的动作(波长连续性检验和分段优化)，即，确定最低成本逻辑路径的可行性。通过优化过程来识别物理路径(例如，沿着逻辑路径的节点和链路)，并且保证波长连续性。如果对于某条逻辑路径不能保证波长连续性(方块392)，那么，如果存在，通过方块387选择另一条逻辑路径，并且将它馈送到方块389。

该过程继续执行前述的方块353。

非线性搜索模块(方块342)的操作将针对图10的例子加以描述，图10的例子代表包括五个透明节点(A-E)和一个再生器节点(R)的光网络。S_i＝A和D_i＝E。在这种情况下，假设通过方块325的核心算法产生的CSPT不包括目的地，因此，线性搜索模块不能用于提供解决方案。

如上所示，方块340识别要用于搜索解决方案的再生节点(和在接着的步骤中，目的地节点)。在所考虑的例子中，方块340首先识别包括在由方块325计算的CSPT中的再生器R。

方块355创建沿着树的每条分支的逻辑分段。在该例中，创建并存储逻辑分段A-R。

方块360检验在通过核心算法作出的计算步骤中方块340所识别的每个再生器是否起源的作用。由于再生器R还没有起源的作用，所以出口是NO。

因此，更新源(方块365)：R变成用于R与目的地节点D_i＝E之间的路由搜索的临时源。

在利用节点R更新了源之后，将核心算法(方块370)应用于具有源节点R和目的地节点E的如图10所示的初始拓扑结构。在该例中，核心算法的这种运行将产生包括目的地节点E的CSPT。

因此，当接着执行方块340时，识别目的地节点E。然后，创建(方块355)与新CSPT有关的逻辑分段并与以前的那些一起存储。由于所有再生器都已经起源节点的作用，所以从方块360退到方块375。

由于逻辑分段是正被搜索的解决方案的潜在部分，方块375检验是否存在包括源节点A的至少一个逻辑分段和包括目的地节点E的至少一个逻辑分段。

在所考虑的例子中，逻辑分段A-R包括源节点，而逻辑分段R-E包括目的地节点，因此，处理过程继续执行方块380，方块380使用方块355所识别的逻辑分段来构建逻辑路径。尤其是，在所考虑的例子中，只有逻辑路径A-R-E(方块385和方块387)。

这样构建的逻辑路径构成到“波长连续性检验和分段优化”功能方块389的输入，方块389将输出如图11所示的解决方案。方块389的详细流程图显示在图12中，将在以后加以描述。

图13更详细地表示了用在图9的方块325和方块370中的核心算法功能。核心算法在它的输入端上接收源节点S_t、目的地节点D_t和网络拓扑结构T₀，并且输出CSPT。更具体地说，核心算法功能包括实现受最大累积有效降质值约束的最短路径算法(例如，Dijkstra算法)(约束最短路径算法)的方块410。如果有效累积衰减超过预定最大值，则排除找到的局部解决方案(树的分支)。

方块410在它的输入端上接收源节点S_t、目的地节点D_t和有关网络拓扑结构T₀的信息。在第一次执行约束最短路径算法之前，将参数P设置成1，参数P可以在0到1之间变化，后面将描述它的用法。方块410的输出是沿着它的分支的有效累积衰减不超过预定阈值的CSPT。

方块410的后面接着方块420，方块420检验是否存在“多余”波长。如果波长属于结束在不对应于目的地节点D_t并且不能引向其它节点的叶子(方块410创建的树的端节点)的弧线(链路)，则该波长被认为是“多余”的，因为既没有波长连续性也没有任何波长转换器或再生器可用在叶子上。这种功能的进一步细节稍后给出。

如果方块420未检测到任何“多余”波长，则处理过程转到方块425，否则(存在至少一个多余波长)，则方块420的后面接着方块430。于是，方块430通过去除多余的波长并因此更新用在搜索解决方案中的拓扑结构来进行拓扑结构简化。去除这样的多余波长是因为它们有时是有害的，尤其是，可以排除迫使约束最短路径算法(方块410)沿着错误路径搜索解决方案的某些解决方案。

处理过程返回到方块410，以便使用新拓扑结构来重新执行约束最短路径算法。

如果不再有“多余”波长，则方块425通过将参数P减小通过电信载波预定的数量P₀(固定的，线性的，对数的等)来更新参数P。

方块425的后面接着方块440，方块440检验是否已经到达目的地节点D_t，即，沿着在方块410中计算的CSPT是否包括目的地节点。如果肯定，该功能终止，在输出中提供CSPT。应该注意到，供应的解决方案与已经去除“多余”波长(如果有的话)并且仅仅由物理上可行的路径组成的拓扑结构有关。

如果还没有到达目的地节点，则方块440的后面接着方块445，方块445检验P的实际值；如果P≤0(出口Y)，则方块445终止处理操作，不识别解决方案。换句话说，输出的计算CSPT不包括目的地节点D_t，但它可以构成后续非线性解决方案搜索处理的起点(方块342)。

如果P的值大于0，则方块445的后面接着方块450，方块450更新表征网络参数(例如，方块410根据P值和根据稍后详述的其它参数使用不同度量)。

此外，每当算法在识别解决方案的过程中加入新节点(例如，它是Dijstkra算法中的“基本节点”N_i，即，沿着该树正在为其评估下一跳的节点)并且重新计算与离开所讨论的节点的每个接口相关的成本时，实现CSPT的方块410就询问方块450。

现在更详细地描述方块410的功能的细节。按照这个功能，创建从源节点S_t开始并试图到达目的地节点D_t的路径。该过程试图将新的相邻节点N_j与基本节点N_i(最初与源节点一致)连接。如果满足三个条件(约束)，即：

·从源节点S_t到新节点N_j的总成本相对于可以加入内置CSPT的其它节点是最小的，例如，min∑W_i，j，其中，W_i，j是成本函数；

·从源节点S_t到新节点N_j的累积有效降质损失(如下定义的局部和LS_i)小于最大容许值Q；以及

·对新节点N_j保证波长连续性，

则该连接是可能的。

换句话说，如果所有上述约束都得到满足，则将新节点N_j加入该树。如果这些约束未得到满足，那么，中断包括新节点N_j的树的所考虑路径。

按照考虑到可用资源和信号累积降质两者的如下表达式，来计算成本函数W_i，j。

尤其是，将使用的度量定义如下：

其中：

W_i，j 从节点N_i到节点N_j的链路的成本，其中，N_i是基本节点，而N_j是要加入的新相邻节点；

I_i 与穿过基本节点Ni相关的有效衰减；

P 是范围从0到1(从1开始，在每次循环减小)的上述(方块425)参数；

C_i 与波长转换器的使用相关的有效衰减。这个参数合计波长转换器所引入的所有降质。如果存在波长连续性，那么，C＝0；

b_i，j节点N_i与节点N_j之间的链路上的可用波长的数量；

B_i，j 节点N_i与节点N_j之间的链路上的波长的总数；

r_j 节点N_j上的可用再生器的数量；

R_j 节点N_j上的再生器的总数；如果R_j＝0，那么，将r_j/R_j取为零；

LS_i 沿着从源节点到节点N_i的给定路由累积的有效衰减(下文将LS_i称为局部和)；

Q 光信号可以经受而没有信息损失的最大有效衰减；

α_i，j 沿着节点N_i与N_j之间的链路的有效衰减；以及

D_i，j 有效距离，即，沿着从链路N_i-N_j到最近的再生器的最短路由的有效衰减。它是与单个接口相关联的值，并且只与存在到再生器的可行最短路径的那些链路相关联(D_i，j小于等于Q)。

于是，成本W_i，j特别取决于在上述过程的每次叠代(包括方块410、420、425、440、445和450)中修改的参数P的值。该成本还取决于那时基本节点N_i的状态和相邻新节点N_j(下一跳)上的可用资源。

局部和LS_i描述从源节点直到基本节点N_i的给定光路的有效累积降质，并且是为了考虑存在于透明光网络中的物理约束和确定给定光路的可行性而被引入的。如果在路径确定期间沿着最短路径树的一条分支加入再生节点，则将与那条分支相关联的局部和LS_i取为零。在这个路径搜索阶段，假设使用再生资源，但不进行将发生在专用功能(已提出方法的第二阶段)中的实际指定。

局部和LS_i如从表达式(1)和(2)中看到的那样，还影响成本W_i，j的计算，然后影响路线搜索。更详细地说，在LS_i相对低的情况下(尤其，当它小于极限值时)，在有利于较少使用路由，即，具有较大波长可用性的链路和具有较大数量再生资源的节点的表达式(1)下计算成本函数W_i，j。

由于，例如，源与目的地D_t之间的长距离或网络负载条件(例如，拥挤)，较大的LS_i(即，大于极限值)可以迫使算法搜索较长的路由。在这些情况下，在有利于使用事先已知到达再生节点的可能性的链路(因为已经为它们定义了D_i，j有效距离参数)的表达式(2)下计算成本函数W_i，j，而不超过LS_i的最大允许值。在这种情况下，成本函数有利于局部解决方案朝着可以恢复信号水平的再生节点收敛。如果未定义有效距离向量D_i，j的元素，那么，必须使用方程(1)。

波长连续性(第三条件)通过所谓的连续性向量来核实。连续性向量是其元素是从根节点(源S_t)开始直到基本节点N_i都存在连续性，或可以通过使用波长转换器或再生器来保证连续性的波长的向量。如果基本节点N_i配有转换/再生资源，则可以保证朝向新相邻节点N_j(下一跳)的波长连续性。在这种情况下，与相邻节点N_j相关联的连续性向量将包括在离开基本节点N_i的链路上可用的所有波长。

如果基本节点N_i不具有转换/再生资源，则可以区分如下两种情况：

a)出现在连续性向量中的波长没有一个可用在朝向相邻节点N_j的链路上。在被考虑的链路上不能保证波长连续性，因此必须放弃；

b)出现在连续性向量中的波长的至少一个可用在朝向相邻节点的链路上。在这种情况下，可以保证基本节点N_i与相邻节点N_j之间的连续性。与相邻节点N_j相关联的连续性向量将包括基本节点的连续性向量和被穿过链路所共有的波长。

举例来说，将上述功能应用于如图14所示的网络，其中，假设：

·节点E具有一个可用再生器，而其它节点都不具有可用再生器；

·节点H具有两个可用波长转换器，而其它节点都不具有可用波长转换器；和

·对于每条链路，第一个数字描述沿着链路的有效衰减α_i，j，而括号中的数字代表沿着链路可用的波长的向量。例如，在链路E-H上：70代表有效衰减，5代表可用在WDM系统上的一组波长的第5波长的可用性，以此类推。

设S是源节点，C是目的地节点，Q＝235，以及为了简单起见，C_i＝0和I_i＝0，B_i，j＝5。此外，R_E＝1，因为只在节点E中有一个再生器。度量单位取决于适用于度量成本的特定实现。

CSPT显示在图15中，为每个节点指示在每个节点累积的有效衰减LS_i，以及在括弧中指示连续性向量。可以注意到，由于节点E的再生能力的影响，节点E处的LS_i值是零。图15强调到达目的地C的不可能性。例如，沿着S-A-B-C路径LS_i大于Q，而沿着S-A-I-C路径保证不了波长连续性。

如下的例子将阐明用在上面方程中的参数D_i，j(有效距离)的含义。如上所述，有效距离D_i，j代表光信号在从给定节点的接口传播到最近的再生节点期间所经受的有效衰减。

让我们考虑在图16中提供的例子，图16示出了具有八个节点的图形。在该例中，节点R和C具有再生能力，而其它节点是透明光节点。与弧线(链路)相关联的值代表有效衰减，并且假设最大有效衰减Q＝235。图17a和17b示出了与图16的图形相关联并具有节点R和C作为源节点的两个CSPT。

应该注意到，由于有效衰减(Q＝235)施加的约束，CSPT未覆盖所有节点。图17a和17b还示出了沿着最短路径树的分支的衰减值，即，每个节点到再生器的有效距离。有效距离相对于每个节点的接口。

例如，由此得出，可以例如将有效距离(朝向再生节点R)与沿着链路D-B的节点D上的接口相关联，但不能与沿着链路B-D的节点B上的接口相关联。反之，其它接口用两个值表征，因为可以从它们出发沿着最短路径树到达两个再生器。例如，沿着链路A-C的节点A上的接口具有相对于再生器R为210以及相对于再生器C为70的有效距离。

与图16中的拓扑结构的不同接口相关联的有效距离向量总结在图18中。向量的第1元素代表到R的有效距离，第2元素代表到C的有效距离。

有效距离D_i，j参数影响度量，因为表达式(2)只能用于定义这个参数的接口。

为了有利于搜索最佳解决方案，如果在执行约束最短路径算法功能期间(图13，方块410)CSPT到达具有可用再生资源的节点，那么，将与那个再生器相关联的有效距离D_i，j排除在后续路由判决之外。当约束最短路径算法功能的执行终止时，在方块425(图13)的功能中再次将排除的D_i，j并入可用于路由目的的信息中(更新P参数和装载初始拓扑结构)，用于接着的叠代。

在下文中，将更详细地描述方块430的功能。方块430的目的是通过将被认为不妥的网络资源(特别是波长)排除在路线搜索之外，来简化经受路由过程的拓扑结构。

更具体地说，方块430排除与方块410所计算的CSPT中不具有再生和/或转换资源并且满足某些条件的端节点(叶节点)相关联的连续性向量的波长。为了排除波长，必须核实如下条件中的至少一个：

1.连续性向量的一组波长与离开叶节点的接口上的每组可用波长的交集是空集；或

2.连续性向量的一组波长与可用在离开叶节点的接口上的波长之间的交集是非空集，但只朝向已经是叶节点所属的路径的一部分的相邻节点(循环条件)；或

3.叶节点只具有其到达的接口(更确切地说，不存在离开叶节点的任何链路)。

换句话说，对于不具有波长转换资源的每个端节点和相应一组波长的每个波长，检验端节点是否通过所述波长与相应分支之外的至少另一个节点连接。

在再次参照示出具有五个节点的网络的图3说明的如下例子中将阐明上面的条件。在该例中，不失一般性，假设在连接节点的所有链路上具有相同的有效衰减，以及对于两个普通节点之间的任意路径，局部和小于最大有效衰减(即，整个网络构成透明域)。还假设所有节点都是完全透明节点(即，它们不具有再生和波长转换能力)。在这些假设下，与接口相关联的权重都相同。

设A是源节点以及E是目的地节点。将约束最短路径算法(例如，Dijkstra)应用于所考虑的拓扑结构给出了如图19所示的CSPT。于是，节点B、D和C是CSPT的叶，因为它们是树的端节点。它们没有一个配有再生和转换资源。方块430的拓扑结构简化功能确定不可以去除与叶节点B相关联的连续性向量的波长λ2，因为它与与链路B-D相关联的波长的向量的交集非空(更确切地说，由λ2组成)，并且终止于不是原始路径的一部分的节点(D)(更确切地说，不是循环的情况)。

将相同的考虑应用于叶节点C。

然而，可以去除与节点D相关联的连续性向量的波长λ1，因为它满足第一条件。

在附表中提供了上面情况的总结。

条件	节点B	节点C	节点D
				1	假	假	真
2	假	假	假
				3	假	假	假

因此，更新拓扑结构，排除链路A-D上的波长λ1，并且再次应用约束最短路径算法。新的叠代产生如图20所示的CSPT，其中经由路径A-B-D-E到达目的地。

如前所述，在搜索到目的地的路由的过程中，变量P允许按照失败尝试的次数来修改路由算法的行为，有效地使再生和/或转换资源得到或多或少强化使用。随着失败尝试的次数增加，方块410逐渐有利于有价值网络资源(即，再生和转换资源)的使用。为此目的，在约束最短路径算法和拓扑结构简化功能的每次叠代(方块425)，减小参数P。

相关例子显示在图21中，其中，节点A是源节点，节点G是目的地节点，以及节点R是再生节点。在这个例子中，假设波长连续性得到保证，以及每条链路具有相同波长可用性。还假设成本函数的参数具有如下值：

·I_i＝C_i＝0

·对于节点R，r_j＝2

·R＝7

·Q＝210

·b_i，j＝4

·B_i，j＝10

根据上面的假设，在第一次叠代中，方块410的约束最短路径算法输出如图22所示的CSPT，其中，紧靠每个节点指出了局部和的总成本值。不能从源到达目的地，因为不遵守最大降质的约束。事实上，在图22中，目的地节点G未包括在CSPT中。

在计算出上面的结果之后，该过程从方块410跳到图13的检验方块420。在上面的假设下，由于通过假设保证了波长连续性，所以没有波长是多余的，因此，处理过程转到方块425，以更新“P”参数和装载初始拓扑结构。在这个阶段中，将P参数减小某个量P₀(可以是常数值或任意函数)，并且重新选择方块410以再次执行约束最短路径算法，因为检验方块440的出口是NO，以及方块445的出口也是NO。

对于F-R链路，重复刚刚所述的叠代过程，直到减小的P参数值使能方程成本(2)。相对于在前面的叠代中指定的成本，赋予这条链路较低的成本。

反之，与其它链路相关联的权重值保持依赖于方程(1)的成本函数。方块410输出如图23所示的CSPT，其中，可以注意到，沿着路线A-C-F-R-E-G，在源与目的地之间找到了一条路径。局部和在容许极限之内，因为在节点R上使用再现功能使它被取为零。因此，P参数逐渐修改了路由，使得使用可用在网络上的再生资源。

方块325(图9)的核心算法功能输出满足网络施加的透明约束的CSPT。不过，因为上面的过程基于相加算法(即，赋予网络拓扑结构只穿过每条链路一次的明确取向)，所以不可能找到像例如利用再生功能时那样打算共享相同链路(例如，分配不同波长)的那些解决方案。

为了阐明这个概念，再次考虑如图10所示的网络。可用在链路上的波长用向量(在括弧中，例如，(1，2))来表示，而与每条链路相关联的其它值表示有效衰减。假设Q＝220。

设A是源节点和E是目的地节点。核心算法功能(方块325)在输出中产生如图24所示的CSPT。由于如下原因，该过程不允许到达目的地节点E：

·沿着路径A-B-C-D-E，在链路C-D上没有波长连续性，并且节点C不具有可用转换资源；

·即使波长连续性得到核实，沿着路径A-B-C-D-E的局部和也大于Q。

然而，存在遵守物理约束的路由并在图11中得到强调，其中，节点R使局部和(更确切地说，有效累积衰减)被取为零并使波长从λ₁转换到λ₂。

核心算法功能不能找到这种类型的解决方案，因为方块325的约束最短路径算法不允许穿过相同链路两次。

为了补救这个问题，引入了非线性搜索模块342，该模块允许通过引入逻辑分段和逻辑路径来克服这些局限性。

在图12中更详细地描述了“波长连续性检验和分段优化”过程(图9的方块345和方块389以及如后所述的图25的方块690)。该过程包括存储逻辑路径的方块710。在该过程中，源节点和目的地节点可以改变，因此，在下文中，将它们叫做临时源节点S_a和临时目的地节点D_a。最初，S_a＝S_i，并且将D_a设置成逻辑路径的第二节点。在图10的例子中，D_a＝R。在这个阶段也考虑初始拓扑结构。在输入中将这个信息传递给再次实现核心算法(针对方块325描述过的相同功能，图9)的方块713。

方块713对于拓扑结构应用核心算法，源节点和目的地节点如在前面的步骤710中定义的，并且在它的输出端上产生CSPT。

方块713的后面接着方块715，方块715检验在CSPT中是否包括临时目的地；如果肯定，方块715的后面接着方块719，否则，它的后面接着强调该过程中的可能错误的方块717。

方块719识别到达临时目的地的最短路径树的分支。如果沿着这条分支存在仅有一个允许信号传播的波长的一条或多条链路，那么，需要从对于信号传播不可能撇开那个波长的那些链路或链路序列中消除其它波长的可用性。

更详细地说：

a)如果所考虑的树的分支不具有波长转换器以及波长连续性只通过一个波长来保证，那么，需要沿着分支的整个长度去除它；

b)如果所考虑的树的分支具有波长转换器或再生器，那么，考虑仅具有一个波长的每条链路，并且使处理按如下继续进行：

-从所考虑的每条链路开始，向上游前进直到以透明方式保证波长连续性的地方。上游具有再生或波长转换能力的第一节点或源节点被认为是透明分段的首端。网络拓扑结构被更新，沿着以前识别的每条透明分段去除所选波长；

-类似地，在以透明方式保证波长连续性的同时向下游前进。具有再生或波长转换能力的第一下游节点或目的地节点被认为是透明分段的末端。网络拓扑结构被更新，沿着以前识别的每条透明分段去除所选波长；

-最后，存储逻辑分段(临时源、透明节点和临时目的地)。

方块719的后面接着方块721，方块721更新临时源和目的地节点。尤其是，新临时源取代旧临时目的地S_a＝D_a，而新临时目的地相对于所考虑的新源变成逻辑路径上的第一下游节点。方块721的后面接着方块723，方块723检验临时源是否与实际目的地一致S_a＝D_i；如果肯定，选择方块725，方块725输出由包括源节点S_i和目的地节点D_i两者的单个分段组成的搜索路径。如果否定，该算法选择方块727，方块727在到核心算法的输入中提供更新的拓扑结构、新源节点S_a和新目的地节点D_a。方块727进行与输出CSPT的方块713相同的动作。

方块727的后面接着方块730，方块730检验在CSPT中是否包括临时目的地；如果肯定，方块730的后面接着方块732，否则，它的后面接着方块742。

方块723进行与方块719相同的动作，它的后面接着方块734，方块734以与方块721进行的相同方式更新临时源和目的地节点。方块734的后面接着方块736。方块734的后面接着方块736，方块736检验临时源节点是否与初始目的地节点一致(S_a＝D_i)，如果否定，返回到方块727。如果肯定，方块736的后面接着方块738，方块738级联在前面的步骤中存储的分段，以获得代表方块740的输出的搜索路径。

回到方块742(通过方块730的出口NO到达)，这个方块存储用在最后搜索中的源节点(S_x＝S_a)和目的地节点(D_x＝D_a)。

方块742的后面接着方块744，方块744装载包括在方块719和方块732中应用的简化之前的所有资源(波长和转换器)的初始拓扑结构。

方块744的后面接着方块746，方块746利用在方块742中存储的源和目的地以及初始拓扑结构，再次应用核心算法。它输出逻辑路径。

方块746的后面接着方块748，方块748检验是否到达临时目的地。如果否定，所考虑的逻辑路径不具有解决方案(即，不可能获得从所考虑的逻辑路径开始具有波长连续性的物理路径，方块750)。

如果已经到达临时目的地，方块748的后面接着方块752，方块752进行与方块732的相同操作。方块752的后面接着方块754，方块754更新临时源和临时目的地节点。尤其，新临时目的地与旧临时源一致，而如果存在，新临时源相对于所考虑的新临时目的地变成逻辑路径上的上游节点。

方块754的后面接着方块756，方块756检验临时目的地和实际源是否一致(D_a＝S_i)，如果否定，使该过程移回到方块746。

如果临时目的地和实际源一致，那么，处理过程转到装载在方块742中存储的临时源和目的地标识符的方块758，并且使处理过程返回到方块734。

为了阐明上面说明的内容，让我们再次考虑图10的拓扑结构，其中，A是源以及E是目的地。

通过非线性搜索(方块342)这个拓扑结构找到的相应逻辑路径是A-R-E。非线性搜索包括下面详述的“波长连续性检验和分段优化”方块。

-方块710：将临时源设置成请求的实际源，即，S_a＝A，并且将临时目的地设置成沿着逻辑路径的第一下游节点，即，D_a＝R；

-方块713：将核心算法应用于具有临时源A和临时目的地R的初始拓扑结构，在输出中产生CSPT；

-方块715：由于到达临时目的地R，所以出口是YES，因此，处理过程继续前进到方块719；

-方块719：从链路A-B、B-C和C-R中去除波长λ1(即，沿着至少一条分支的唯一波长)的可用性，于是更新了拓扑结构；存储分段A-B-C-R；

-方块721：新临时源变成S_a＝R，新临时目的地变成节点D_a＝E(与实际目的地一致)，以及利用的拓扑结构是在方块719中更新的那个；

-方块723：临时源(节点R)和实际目的地(节点E)不一致，因此，处理过程继续前进到方块727；

-方块727：利用临时源R、临时目的地E和在方块719中更新的拓扑结构来应用核心算法，在输出中产生CSPT；

-方块730：由于到达临时目的地E，所以出口是YES，因此，处理过程继续前进到方块732；

-方块732：从链路R-C、C-D和D-E中去除波长λ2(即，沿着至少一条分支的唯一波长)的可用性，于是更新了拓扑结构；存储分段R-C-D-E；

-方块734：新临时源变成S_a＝E，而不能更新临时目的地，因为E是路径的最后节点；

-方块736：临时源(S_a)与实际目的地(节点E)一致，因此，处理过程转到方块738；

-方块738：级联在前面的步骤中存储的分段，以获得被搜索的路径(参见图11)。

所述功能被叫做“波长连续性检验和分段优化”，因为它不仅允许检验路径的可行性，而且还通过改善沿着构成整条路径的每个分段的路由而改善了路径本身。

参照图26的网络拓扑结构，通过如下例子进一步强调由“波长连续性检验和分段优化”功能提供的优点。可用在链路上的波长用向量(在括弧中，例如，(1，2))表示，而与每条链路相关联的其它值表示有效衰减。

让我们假设存在从节点A到节点E的路由请求。应用图9的核心算法325，以便寻找路由问题的线性解决方案。核心算法325的输出是如图27所示的CSPT。在第一次运行核心算法时通过路径A-B-R-C-E到达目的地，因此，无需调整参数P。

然而，存在该算法未找到的较低成本的可行路径：A-B-R-D-E。在该算法中，因为在节点R变成基本节点之前已从源A到达节点D，所以未找到这条路径。本发明的方法允许检测到这条路径。

核心算法检测的解决方案(A-B-R-C-E)通过将相关逻辑路径A-R-E馈送到“波长连续性检验和分段优化”模块(方块345，图9)来优化，如前所述，该“波长连续性检验和分段优化”模块将核心算法应用于源节点A和目的地节点R，然后应用于源节点R和目的地节点E。在第一次运行时获得如图28所示的解决方案A-B-R-D-E，它代表“基本解决方案”。通过应用图9的方块338可以获得进一步的可选改善。在图25中对其作了详细描述，结果是叫做“改进解决方案”的可能改善解决方案。该方法预知方块610将源节点S_i存储成“改进解决方案”的一部分，以及将临时源节点S_t装载成S_i值，即，节点A(方块620)。方块630存储以前找到的“基本解决方案”中与源节点A相邻的节点(即，节点B)，作为“改进解决方案”的一部分。此外，利用紧靠其值的节点(即，节点B)更新临时源S_t，然后将它用于该算法的第一次运行。

方块640检验临时源节点S_t是否等于最终目的地节点D_i。如果肯定，将可变标志设置成值2(方块658)，并且从该过程退出。如果否定，将核心算法应用于具有源节点S_t和目的地节点D_i的初始拓扑结构(方块660)。

方块660的后面接着方块670，方块670检验是否到达目的地节点，如果否定，将可变标志设置成值1(方块698)，并且从图9的方块358退出。如果肯定，方块680以图9的方块335进行的相同方式来识别包括临时源节点和目的地节点D_i的逻辑路径。

方块680的后面接着方块690，方块690是进行与图9的方块345相同的动作的“波长连续性检验和分段优化”模块。

方块690的后面接着方块695，方块695检验波长连续性是否得到保证。如果否定，则将可变标志设置成值1(方块698)，并且从该过程退出。如果肯定，则叠代该算法，直到临时源与初始目的地节点(即，节点E)一致(方块640)。

一旦识别出“改进解决方案”，就可以在波长、转换和再生资源指定方面细化该解决方案(图8的方块400，详述在图29中)。细化过程意味着最大化透明分段的长度和最小化转换和再生资源的使用。

上面的细化过程将参照图29的流程图加以描述。

该过程包括存储在路由阶段获得的路径(节点和链路)的方块800。

方块800的后面接着方块810，在方块810中，从路径中去除单个透明节点或一系列透明节点(即，没有转换和/或再生资源的那些节点)和它们的链路(源节点和目的地节点是唯一例外)，并且用单条等效链路取代它们，该单条等效链路的特征在于，有效衰减等于被聚集链路的有效衰减之和加上穿过节点引入的衰减，以及可用波长的向量等于与所考虑的链路相关联的波长向量的交集(例如，所有链路共有的波长)。

方块810的后面接着方块820，方块820包括两个动作：

·动作1：当在输入到仅仅具有波长转换器的可用性的节点的链路与从那些节点输出的链路之间存在波长连续性时，去除那些节点(和相关链路)。去除的节点和链路被等效链路取代，该等效链路的特征在于，有效衰减等于被去除链路和节点的有效衰减之和，以及可用波长的向量等于与所考虑的链路相关联的波长向量的交集；和

·动作2：去除具有再生资源的可用性的节点，因为在输入的链路与输出的链路之间存在波长连续性，以及从所考虑的再生节点开始直到相邻再生节点(或者，向上游直到源节点和向下游直到目的地节点)的上游和下游局部和之和不超过允许的最大有效衰减Q，所以没有必要使用再生资源。

方块820的后面接着方块830，方块830包括两个动作：

·动作1：当从所考虑的节点直到相邻再生节点(或者，向上游直到源节点以及向下游直到目的地节点)的上游和下游局部和之和超过允许的最大有效衰减Q的值时，简化具有再生和转换资源的可用性的节点中的功能。在这种情况下，可以仅仅将再生功能指定给节点；和

·动作2：当从所考虑的节点直到相邻再生器(或者，向上游直到源节点以及向下游直到目的地节点)的上游和下游局部和之和不超过允许的有效衰减Q的最大值并且不存在波长连续性时，简化具有再生和转换资源两者的可用性的节点中的功能。在这种情况下，可以仅仅将转换功能指定给节点。

上述过程之后获得的路径包括源节点、起波长转换器作用的一个或多个节点、起再生节点作用(然后，固有地起波长转换器作用)的一个或多个节点、目的地节点、一些真正链路和一些等效链路。

方块830的后面接着方块840，方块840执行如下步骤：

·沿着获得的路径，识别通过与每条链路(物理或逻辑的)相关联的波长向量的交集来保证沿着路径的波长连续性的多组相邻链路(分段)。对于每个分段，存储保证连续性的波长向量；

·对于从源节点开始的每个分段，从不保证相邻分段上的连续性的波长当中选择要用在该分段上的波长。在那些波长当中，选择沿着路径较不可用的那些波长。最后，从那些波长当中选择最可用的那个波长。作出这种选择是为了保护当为进一步的请求服务时可以保证连续性的那些波长的可用性；

·如果沿着一个或多个分段，由于所有可用波长保证了连续性，所以在前面的步骤中未识别出有用波长，那么，从保证多个分段上的连续性的那些波长当中选择一个波长。对于每个分段，从该组波长中选择一个最可用波长。

最后，考虑波长以及再生和转换资源的分配，构建到目的地的路径。

上述内容将利用如下的例子加以详述。

让我们考虑具有不同特征的节点的如图30所示的路径：

·具有再生资源可用性的节点-节点C；

·具有波长转换器可用性的节点-节点D；

·具有再生和波长转换资源可用性的节点-节点E；

·作为不具有再生和转换能力/可用性的那些节点的透明节点-节点A、B和F。

在图30中，沿着给定链路的波长的可用性用向量表示，以及有效衰减用标量表示。让我们考虑最大有效衰减Q＝235。

如上所述，方块810将透明节点(源节点和目的地节点除外)和相邻链路变换成等效链路。因此，节点B和相邻链路被取代，创建了图31的路径。在该图中，跨在节点A和C之间的等效链路具有等于链路A-B(即，100)和B-C(即，100)的有效衰减之和的有效衰减(200)、以及等于与链路A-B和B-C相关联的波长向量的交集(即，(1，2，3，4)与(1，2，4)＝(1，2，4))的可用波长的向量。节点B的衰减忽略不计。

方块820进行两个动作：取代仅仅具有波长转换器的可用性的节点，因为在输入到那些节点的链路与从那些节点输出的链路之间存在波长连续性，所以没有必要使用波长转换器。在该例中，对于波长1和3来说，在链路C-D与D-E之间存在波长连续性。节点D被等效链路取代，该等效路径的特征在于，有效衰减等于被聚集链路(C-D与D-E)的有效衰减之和(200＝100+100)，以及可用波长的向量等于与链路C-D与D-E相关联的波长向量的交集(即，(1，2，3)与(1，3)＝(1，3))。节点D的衰减忽略不计。

此外，方块820试图通过去除节点C进一步简化路径。节点C是具有再生资源的节点，以及在相邻的A-C和C-E链路之间具有波长连续性。然而，局部和(200dB上游局部和以及200dB下游局部和)之和大于允许的有效衰减Q的最大值，因此，不可能取代节点C。如方块820所改的路径显示在图32中。

方块830如上所述简化具有再生和转换资源的可用性的节点-节点E。

节点E是具有再生和转换资源两者、上游(200dB)和下游(35dB)局部和之和未超过有效衰减Q的最大值、以及输入链路与输出链路之间的波长连续性不被保证的节点。在这种情况下，可以通过仅仅指定转换功能来简化节点E的功能(动作2)。沿着所考虑的路径不存在归入动作1的具有再生和转换资源两者的节点。结果是图33的路径，其中，E现在只是波长转换器节点。

方块840识别通过与每条链路相关联的波长向量的交集来保证沿着路径的波长连续性的分段(真正和/或等效)。在该例中，链路A-C和C-E保证了波长连续性(通过λ₁)，并且构成了一个分段(分段1)。具有相关波长λ₄的链路E-F代表另一个分段(即，分段2)。在第一分段中，λ₁保证波长连续性，并因此不应当被考虑。在链路A-C上应该考虑λ₂和λ₄，在链路C-E上应该考虑λ₃，以及在链路E-F上应该考虑λ₄和λ₅。在分段1上，应该选择λ₂而不是λ₄，因为沿着整条路径λ₄较频繁，以及，沿着分段C-E上应该考虑λ₃。在分段E-F上，应该选择λ₅而不是λ₄，因为沿着整条路径λ₄较频繁。

在所考虑的例子中，所获的路由显示在图34中，其中，这些波长是要用在装置中的波长。应该注意到，节点D用作透明节点。节点C用于再生信号和转换波长两者。沿着从节点A到节点E的路径所选的波长不是λ₁，因为它保证波长连续性。优选使用在那条路径上不能允许透明服务分配的λ₂和λ₃，为路由请求服务需要节点C的再生能力。

Claims

1.一种在包括多个节点的光网络中动态路由光信号的方法，其特征在于，包括：

·执行最短路径算法(410)，接收有关源节点、目的地节点和网络的拓扑结构的输入信息，并提供包括节点和连接所述节点的弧线的最短路径树作为输出，所述最短路径树包括多条分支，光信号沿着所述多条分支累积的有效衰减最多等于预定极限，每条分支包括端节点，每个端节点与相应一组波长相关联；

·对于没有波长转换资源的每个端节点和相应一组波长的每个波长，检验(420)所述端节点是否通过所述波长与相应分支之外的至少另一个节点连接；

·对于所述检验的结果对于相应一组波长的至少一个波长为否定的任何端节点，从相应一组波长中排除(430)所述至少一个波长，因此更新拓扑结构；以及

·利用更新的拓扑结构来重新执行(410)最短路径算法。

2.如权利要求1所述的方法，进一步包括：

·在第一次执行最短路径算法之前，设置一个参数P的值；

·如果所述检验的结果对于所有端节点和相应一组波长的所有波长都是肯定的，则减小(425)所述参数P的值；

·如果所述参数P的值大于0，则更新(450)网络参数，因此更新拓扑结构；

·利用更新的拓扑结构来重新执行(410)最短路径算法。

3.如权利要求2所述的方法，其中，所述检验是第一次检验，以及其中，该方法进一步包括：

·如果所述第一次检验的结果对于所有端节点和相应一组波长的所有波长都是肯定的，则第二次检验(440)所述端节点的任何一个是否与目的地节点一致；

4.如权利要求3所述的方法，进一步包括：

·如果第二次检验的结果为否定，则第三次检验(445)所述参数P的当前值是否≤0；

5.如权利要求1或2所述的方法，其中，与端节点相关联的一组波长包括从源节点到端节点或者由端节点的同一分支和端节点中的波长转换器资源保证波长连续性的所有波长。

6.如权利要求2所述的方法，其中，执行最短路径算法(410)包括通过加入新节点来生长所述最短路径树。

7.如权利要求6所述的方法，其中，如果沿着所述分支从源节点到新节点的累积降质损失小于最大容许值，则将新节点加入所述分支。

8.如权利要求6所述的方法，其中，如果沿着所述分支从源节点到新节点或者由端节点的同一分支和端节点中的波长转换器资源保证波长连续性，则将新节点加入所述分支。

9.如权利要求6所述的方法，其中，如果沿着所述分支从源节点到新节点的总成本相对于其它可能的新节点是最小的，则将新节点加入所述分支。

10.如权利要求7所述的方法，其中，如果新节点是再生节点，则将累积降质损失(S_i)取为零。

11.如权利要求9所述的方法，其中，所述总成本由成本函数W_i，j表示，所述成本函数W_i，j取决于所述参数P，以及按照如下第一和第二表达式来计算所述成本函数W_i，j：

其中：

W_i，j是从节点N_i到节点N_j的链路的成本，其中，N_i是基本节点，而N_j是要加入的新相邻节点；

I_i是与穿过基本节点Ni相关的有效衰减；

P是上述参数P；

C_i是与波长转换器的使用相关的有效衰减；

b_i，j是节点N_i与节点N_j之间的链路上的可用波长的数量；

B是节点N_i与节点N_j之间的链路上的波长的总数；

r_j是节点N_j上的可用再生器的数量；

R_j是节点N_j上的再生器的总数；

LS_i是沿着从源节点到节点N_i的给定路由累积的有效衰减；

Q是光信号可以经受而没有信息损失的最大有效衰减；

α_i，j是沿着节点N_i与N_j之间的链路的有效衰减；以及

D_i，j是沿着从链路N_i-N_j到最近的再生器的最短路由的有效衰减。

12.如权利要求9所述的方法，其中，所述总成本由成本函数W_i，j表示，成本函数W_i，j取决于如下之中的至少一个：

-到新节点的链路中的可用波长；

-新节点中的可用再生资源；

-信号的累积降质损失。

13.如权利要求11所述的方法，其中，第一表达式有利于具有较大数量再生资源并可通过具有较大波长可用性的链路到达的新节点。

14.如权利要求11所述的方法，其中，第二表达式有利于事先已知到达再生器的可能性的新节点。

15.如权利要求1所述的方法，进一步包括：

第四次检验(330)目的地节点是否包括在所述最短路径树中。

16.如权利要求15所述的方法，进一步包括：

如果第四次检验(330)的结果为否定，则激活非线性搜索(342)。

17.如权利要求16所述的方法，其中，当所述执行最短路径算法(410)是第一次执行以及所述最短路径树是第一最短路径树时，所述非线性搜索(342)包括：

第二次执行最短路径算法(370)，接收有关临时源节点和临时目的地节点的输入信息，并提供第二最短路径树作为输出。

18.如权利要求17所述的方法，其中，所述非线性搜索(342)进一步包括：

识别包括在所述第一或第二最短路径树中的所有再生器，以及第五次检验(340)目的地节点是否包括在所述第一或第二最短路径树中。

19.如权利要求18所述的方法，其中，所述非线性搜索(342)进一步包括：

创建多个逻辑分段，其中，每个逻辑分段包括：

作为第一端的源节点或识别的再生器中的第一再生器；和

作为第二端的目的地节点或识别的再生器中的第二再生器。

20.如权利要求19所述的方法，进一步包括：

第六次检验(360)在第二次执行中，识别的再生器中的每个再生器是否起临时源节点的作用。

21.如权利要求20所述的方法，进一步包括：

如果第六次检验(360)的结果为否定，则选择识别的再生器中的临时再生器，其中，所述临时再生器在第二次执行中还没有起临时源节点的作用；以及

将所述临时再生器作为临时源节点，重新执行(370)最短路径算法。

22.如权利要求20所述的方法，进一步包括：

如果第六次检验(360)的结果为肯定，则第七次检验所述多个逻辑分段的至少一个是否包括源节点以及所述多个逻辑分段的至少一个是否包括目的地节点。

23.如权利要求22所述的方法，进一步包括：

如果第七次检验的结果为肯定，则计算(380)源节点和目的地节点之间的逻辑路径。

24.如权利要求23所述的方法，其中，所述计算(380)包括：

经由再生器来连接逻辑分段。

25.如权利要求23所述的方法，进一步包括：

确定(387)逻辑路径的成本并确定最低成本逻辑路径。

26.如权利要求25所述的方法，其中，逻辑路径的成本和与逻辑路径相关联的再生器的数量有关。