于约束的GMPLS恢复算法

在分析与恢复威廉希尔官方网站 有关的GMPLS威廉希尔官方网站 特性基础上，提出了一种基于约束的GMPLS恢复算法(CGR)，并对相关的约束条件的设置做了具体的规定和说明，以网状网为例，详细介绍了所提出算法的实现方法和特点。该算法借鉴了传统恢复威廉希尔官方网站 的优点，又充分考虑到GMPLS网的特性，使其具有继承性和兼容性。
关 键 词 通用多协议标签交换; 标签交换路径; 生存性; 恢复

随着IP威廉希尔官方网站 的发展，用户对IP网的依赖越来越大，但由于威廉希尔官方网站 的局限性，使得采用IP威廉希尔官方网站 进行实时和宽带业务的传递时，无法保证所传业务的服务质量。光传送网的发展为IP威廉希尔官方网站 的应用提供了一个可靠的传送平台，通用多协议标签交换 (Generalized Multi-protocol Label Switching, GMPLS)威廉希尔官方网站 则是实现IP威廉希尔官方网站 与光传送威廉希尔官方网站 结合的最佳途径。为了适应对这种网络进行动态控制的要求,GMPLS对传统的[1]多协议标签交换(Multi-protocol Label Switching, MPLS)进行了扩展更新。在这种通用、高带宽网络环境下，网络中的任何故障都会造成大量数据的丢失。因此无论是从用户的角度，还是从运营商的角度，都迫切需要在网络发生故障后能尽快地将受故障影响的业务恢复，特别是一些对实时性要求高的业务，其恢复速度必须满足业务的需求[2]。
恢复算法是网络在发生故障后对受故障影响的业务进行重新建立路由的过程。这里，路由的重新建立一定要遵循“在中断前完成”的原则，即在新通道被建立时仍使用原通道，执行完路由倒换后再将原路由拆除。传统的IP网中故障恢复采用集中控制的方式，当故障发生时，网络管理员发现故障告警信号后，对受故障影响的业务流进行手动重新配置。与IP网不同，基于GMPLS的网络是在传送数据前建立标签交换路径(Label Switch Paths, LSPs)，GMPLS 的恢复是基于LSP的恢复，这为基于GMPLS网络的恢复威廉希尔官方网站 提供了很多方便，可大大提高恢复速度[3,4]。

有关GMPLS恢复威廉希尔官方网站 的研究则刚刚开始，在进行这方面的研究时，一方面要借鉴传统恢复威廉希尔官方网站 的优点，使其具有继承性和兼容性，同时还要充分考虑到GMPLS网的特性[5]。本文正是在这种背景下提出一种基于约束的GMPLS恢复算法。
1 恢复算法的基本思想
在进行GMPLS恢复算法的设计时，首先要充分考虑到其网络特性。从网络恢复威廉希尔官方网站 的角度来看，GMPLS有以下特性：1) 多类型的交换和转发层次。GMPLS可以支持时分复用(Time Division Multiplexing, TDM)、波长交换(Lambda Switch Capable, LSC)和光纤交换(Fiber Switch Capable, FSC)，这些新型的交换设备可以提供多种不同速率的交换接口，适用于在网络边缘对多种不同业务的接入。2) GMPLS 对IGP的扩展。GMPLS对内部网关协议(Internal Gateway Protocol, IGP)进行扩展，使它能够将各种类型的链路广播发送到常规链路上或非包/分组(TDM时隙、波长或光纤)链路上，并支持邻近转发(Adjacent Forwarding)。3) GMPLS中LSP的分级。GMPLS通过定义LSP的等级来完成LSP的嵌套，从而支持业务量干线隧道的建立。最低等级的LSP(FSC接口)是开始和终结于分组交换的节点上，比它高一级的LSP(TDM接口)是开始和终结在TDM交换节点上，更高一级的LSP(LSC接口)是开始和终结在波长交换节点上，最高等级的LSP(FSC接口)是开始和终结在光纤交换节点上[5]。4) 双向LSP的建立。在GMPLS中，双向LSP的建立是被允许的。无论上游或者下游通道，都使用相同的一套信令系统，从而降低了延迟时间，减少了控制开销。5) 链路绑定。为了提高流量工程的可扩展性并减少标签资源的使用，GMPLS允许把一套平行的链路归并到同一个IGP中作为单个链路使用，产生的这条逻辑链路称为绑定链路(Bundled Link)，其物理链路被称作组成链路(Component Link)。6) 约束路由。GMPLS使用约束路由机制来分配相关的传输网络拓扑信息，包括使用IGP转发相邻节点的状态信息。约束路由的出现使传统的路由算法有了改进的可能，基于约束的GMPLS恢复算法就是基于这种约束的路由算法。
在进行恢复路由的选择时，考虑到GMPLS的威廉希尔官方网站 特性，对所选的路由给出相应的约束条件(包括带宽需求、最大跳数等)，从而使选出的恢复路由不仅最短，同时能合理地利用带宽资源，并适应不同业务及交换类型对恢复路由的要求，使恢复算法达到最优。
2 约束条件的设置
GMPLS的约束条件通常对信令类、编解码类和交换类三个方面进行考虑，具体又可分为对LSP的约束和对LINK的约束两部分。
2.1 LSP的约束条件
1) 带宽需求。即当此LSP加载在该链路或路径上的时候，该链路或者路径是否能够具有足够的带宽加载这条LSP。
2) 节点限制。节点限制包括编解码类型限制和交换类型限制。其中编解码类型限制是说在源节点和目的节点之间应具有相同的编解码类型，这种类型由目的节点确定，源节点与之相匹配。
3) 优先权。优先权包括建立优先权和保持优先权，即如果网络中LSP存在优先权问题则优先权低的LSP在和优先权高的LSP发生抢占资源的时候，应首先满足优先权高的LSP的要求。
4) 路由类型。路由类型指的是显示路由或者逐跳路由，其中显示路由还包括严格显示路由和松散显示路由。
2.2 LINK的约束条件
1) 链路保留带宽：链路保留带宽即安全带宽，当链路加载某个LSP的时候，如果不能保证剩余10％的安全带宽则认为不能加载此LSP。
2) 链路限制：链路限制是因链路的具体状况确定该链路的优先级别，包括闲忙参数α和故障参数β。
3 算法的实现
CGR算法要求网络上所有的节点都具有一张邻接节点路由状况表。有了状况表，节点只要知道它到与它邻接的节点的链路开销，而不用获得它到目标节点的路径开销就可以绘制出一张恢复路由表。环路的问题在CGR算法中不予考虑，因为每个节点都具有整个网络的拓扑结构，而且CGR算法通过对节点是否已标记来判断选路的走向，根本不会出现环路现象。
节点的邻接节点路由状况表记录的信息包括源节点地址，邻接节点地址，邻接节点开销，邻接链路状况参数α 和β，以及节点参数τ 等5个部分。因此，如果节点A通过一条开销为3的链路直接连接到节点B(不经过中间节点)，并且路由器A通过一条开销为5的链路直接连接到节点C，那么节点A将把将会向网络上所有的节点广播链路状态包。每个节点将可以从接收到的链路状态包中推算出一条通向目的节点的最短路径。下面我们就来具体的讲解一下CGR算法的实现过程。
3.1 CGR算法的建立
CGR算法的建立阶段主要有以下几部分组成：1) 建立邻接节点路由状况表。网络中节点A通过发送Hello包到它的邻接节点，获得邻接节点的地址、开销、链路参数和节点参数等信息，建立了邻接关系，所得到的信息都记录在邻接节点路由状况表。2) 建立链路状态数据库。将本节点的数据收集起来，构建链路状态数据库。节点间的数据发送和收集是通过泛洪(Flood)算法来完成的。3) CGR算法计算最优路径。CGR算法把某一节点(假设为节点A)设为源节点，初始状态下通过链路状态数据库提供的信息进行最优路径的计算；发生故障之后，通过更新后的链路状态数据库计算最佳恢复路径。
3.2 算法的步骤 节点，其他节点均设为未标记数n，邻接节点开销识节点中选择一个进行标识的其中一个邻接节点该节点和邻接链路置断
假设网络中源节点为s，任意一点j都对应两个参量dj和pj。其中dj表示从源点s到点j的最优路径开销；pj则是表示从s到j的最优路径中j点的前一节点。求解从源点s到网络中任意点j的最优路径算法的基本过程如下：1) 初始化节点的开销。源节点为0，其他所有节点为∞；标记源点s，其它所有节点设为未标记。2) 检测是否满足节点限制。检验该节点到其邻接的未标记节点的链路是否满足节点限制。如果编解码类型τ1和交换类型τ 2都满足则置通过；如果仅不满足τ1则可作为中间节点，不可作目的节点；如果τ 2不满足则无论编解码类型是否满足都置为断点，表示链路和节点均不可用。3) 检测是否带宽需求。检验所选链路是否满足带宽需求和链路保留带宽需求。满足则通过，跳到步骤5)，不满足跳到步骤4)。4) 检测优先权。检测LSP优先权等级，如果高于已加载LSP，且断开低等级LSP后，可成功加载高等级LSP则加载；否则置丢弃。5) 计算邻接链路的CGR算法开销。γ =γ×α (β=1) 或者γ =γ×β (β ≠1)。6) 选择链路。比较邻接链路的CGR算法开销值，选取其中最小的一条进行加载。如果有两条或者以上开销相同的链路，则选择跳数最少的一条。7) 检验链路开销。如果小于以前的CGR算法开销则替代；大于则丢弃，如果相等，则选择跳数少的路径丢弃跳数多的。8) 找寻上一节点进行标记。如果步骤6)中替代了原有CGR算法开销则找寻上一节点进行标记。9) 检测算法是否完成。检测是否所有节点都已标记，如果都已标记则算法完成；否则将步骤8中的上一节点转到步骤2)继续进行计算。
在实现过程中需要配合链路状态数据库完成。此算法由于添加了故障参数和闲忙参数，因此可以在一定的程度上避开故障易发节点和链路，与其他恢复算法相比在网络的生存性方面具有一定的优势。
图1给出了CGR算发法的流程图。