MPLS环路预防机制(RFC3063)

《MPLS环路预防机制(RFC3063)》由会员分享，可在线阅读，更多相关《MPLS环路预防机制(RFC3063)（29页珍藏版）》请在装配图网上搜索。

1、组织：中国互动出版网（http:/www.china-（http:/www.china-E-mail：ouyangchina-译者：徐春红（airria air_xu ）译文发布时间：2001-3-29版权：本中文翻译文档版权归中国互动出版网所有。可以用于非商业用途自由转载，但必须保留本文档的翻译及版权信息。 MPLS（多协议标签交换）环路预防机制摘要 本文讲述了一种基于“线程”的、用于防止多协议标签交换协议（MPLS）设置含有环路的标签交换路径(LSP)的简单机制。此机制与虚电路（VC）的合并相兼容，但此兼容u并不是必需的。该机制还可用于下游按需等级分配也可用于下游等级分配。在协议消息中对要

2、传输的信息进行了紧密的捆绑（也就是，不需使用路径矢量）。当一个节点需要转换到它的下一跳时，分布式程序被执行。不过，这只针对那些下游变化的节点。目录摘要11.介绍22基本的定义33.线程基础43.1 线程属性43.2. 线程环53.3. 线程的基本行为53.4 线程基本行为实例74线程算法95. 算法的适用性105.1 LSP路由环的预防/检测105.2 当新路径上有路由环时使用旧路径105.3 如何处理下游等级分配105.4. 如何实现负载的分离106为什么算法是有效的？116.1 为什么一个带有未知跳数的线程被扩展116.2. 为什么一个回绕的线程不能包含一个环？116.3. 为什么L3路由

3、环被检测126.4. 为什么L3不被错误地检测1265一个滞留线程怎样自动地从环路中恢复126.6. 为什么不同颜色的线程不能相互追赶？127. 环预防的例子137.1 第一个例子137.2. 第二个例子168. 线程控制时钟168.1. 有限状态机制179. 与路径矢量/扩散方法进行比较2010 .安全考虑20附录A-算法的进一步讨论20A.1. 环路预防的强制方法20A.2. 强制方法有哪些不妥？21A.3. 线程跳数21A.4. 线程颜色22A.5. 颜色和跳数之间的关系23A.6. 检测线程环23A.7. 预防LSPs环路的建立24A.8. 撤销线程25A.9. 修改现有线程的跳数和颜

4、色25A.10.什么时候没有下一跳？25A.11. 下一跳的变化和先前存在的有颜色的输入线程25A.12. 一个环中有多少个线程在运行？26A.13. 关于跳数U的一些特殊规则27A.14. 从环路中恢复27A.15. 继续使用旧路径281.介绍 本文讲述了一种基于线程，用于防止MPLS设置具有路由环的标签转换路径（LSPs）的简单机制。 当一个LSR(标签交换路由器)发现其有一个新的特定的跳向FEC（等效前传类）1的下一跳时，它就创建一个线程并且将其扩展为下游。每一个这样的线程都被分配唯一的一种颜色来标识，这样就可保证网络上的任何两个线程都不会有相同的颜色。 对于一个给定的LSP，若从节点到

5、最远的上 游节点上都没有跳数变化，那么一旦一个线程被扩展为一个特定的下一跳，其它的线程就不能再被扩展为这样的下一跳。与特定LSP的 特定的下一跳相关联的仅有的状态信息就是线程的颜色和跳数。 如果存在路由环，那么某一线程将会返回至它已经经过的LSR处。因为线程有特定的颜色，所以这一点很容易检测。 第三部分和第四部分提供了用于检测的没有路由环的程序。当线程被检测的时候，线程被回绕至其创建处。当他们被回绕时，标签被分配。因而，标签只有在保证自由路由环时才被分配。 当一个线程被扩展时，它所经过的LSRs必须记录它的颜色和跳数，但是当线程已被回绕时，LSRs就只需要记录线程的跳数。 如果LSP中有一些，

6、或全部，或根本就不存在LSRs支持VC-合并，线程机制同样有效。它可以被用于请求的下游按需标签分配或者用于未经请求的下游标签分配2,3。该机制也可用于路由环检测，旧路由的保留和负载分离。 协议消息必须携带的并且必须保留在状态表内部的那些状态信息大小是固定的，与网络大小无关。因而线程机制比那些需带有路径矢量的选择对象更具有可伸缩性。 为了在路由变化后，建立一个新的LSP，线程机制仅需要在变化点的下游节点之间进行通信，而不需要在变化点的上游节点之间进行通信。所以，线程机制比要求执行扩散算法的选择对象更加健壮。（参看第9部分）2基本的定义LSP 我们将运用术语LSP参照一个根结点为出口点的多点到一点

7、的树。参见3.53部分。 下面，我们假设网络中只设有一个LSP来讨论。这使得我们在谈到输入、输出链接时不需要老是说“对于同一个LSP”这样的话。输入链接，上游链接输出链接，下游链接 在给定的节点处，一个LSP将有一个或更多个输入或上游链接和一个输出链接或下游链接。一个“链接”实际上是邻近LSR的一种抽象的联系；它是“树”的一个“边缘”，且就象一个“接口”一样不必是一个特别的具体实例。 叶节点，入口节点 没有上游链接的节点 符合条件的叶节点 能够成为叶节点的节点。例如，如果一个节点不能直接创建一个L3包或者在其输出链 接上不能接收一个L3包，那么此节点就不是一个符合条件的叶节点。链接跳数 每个链

8、接用一个“链接跳数”标识。此“链接跳数”就是给定链接与其最远的上游叶节点之间的跳的数目。在任何一个节点上，下游链接的链接跳数总是比与之相关的最大的上游链接跳数大1。 在一个给定节点上，我们用Hmax来定义节点上所有的输入链接跳数的最大值。注意：下游链接跳数等于Hmax+1。在一个叶节点上，Hmax被置为0。 图1显示了一个链接跳数的例子。 1 2 A-B-C K | | |3 |1 | | | 4 5 | 6 7 D-G-H-I-J | |2 1 | E-F 图1一个链接跳数例子 下一跳的获取 虽然以前节点N认为FEC F是不可到达的，但是现在它却可以有通向它的下一跳。下一跳的丢失 节点N以前

9、认为节点A是通向FEC F的下一跳，但是现在在节点A再也没有通向FEC F的下一跳了。无论何时下一跳向下传，节点A总会丢失一个下一跳。下一跳的变化 在节点N，通向FEC F的下一跳从节点A变化到B，这里节点A与B是不同的。下一跳的变化可以看作是老的下一跳丢失事件与新下一跳获取事件的结合。3.线程基础 在下游按需等级分配形式（入口初始化分配控制）中，线程即是用于建立一个LSP的消息序列。3.1 线程属性 线程有三个属性。这些属性可被编码到如下一个单独的线程对象中。 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-

10、+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | + Color + | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Hop Count | TTL | Reserved | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+线程颜色 每当一个节点产生一个路径控制消息时，节点就会分配一种唯一的颜色给此

11、消息。此颜色在时间和空间都是唯一的：它的编码包含一个节点的IP地址，而此地址与该节点所保留的编号空间的唯一的事件确认相关联。节点发送给下游的路径设置消息将包含该颜色。另外，当一个节点发送包含颜色的消息给下游时，节点将记录此颜色并且将此颜色设为下游链接的颜色。 当一个带有颜色信息的消息被接收时，它的颜色就成为输入链接的颜色。包含某一特定颜色消息的线程就被标识为具有那种颜色的线程。 特别的颜色值“透明色”（全0）被保留。 分配唯一的颜色值的一个可行方法是：从事件标识符的初始值开始，每分配一种颜色值对其加1（对最大值取模）。用这种方法，最初的事件标识符可以随机选取也可以分配一个比以前系统赋值所使用的

12、最大的事件标识符更大的值。线程跳数 为了保持链接跳数，我们需要在路径控制消息中携带跳数。例如，一个叶节点将分配跳数1给它的下游链接并将此值存储到它发往下游的路径建立消息中。当一个路径建立消息被发往下游时，一个节点将分配一个比其最大的输入链接跳数大1的跳数值给它的下游链接，它也会将此值存储到其发往下游的路径控制消息中。一旦跳数值被存储到路径控制消息中，我们就可将此值当作一个“线程跳数”。 一个特别的跳数值“未知的”（=0xff）比任何一个已知的值都要大，它被用于存在路由环的情况下。一旦线程跳数值成为“未知的”，那么当线程被扩展时，它的跳数值就不再会被增加。线程TTL 为了避免某些情况下的未定义的

13、控制信息环，一个TTL线程就会被创建。当一个节点产生一个路径控制消息时并且将其发送到下游时，它就为其消息产生一个TTL线程。该TTL线程在每一跳上都被减1。当TTL线程到达0时，消息就不能再向前传了。与线程跳数和线程颜色不同，TTLs线程不需要被存储在输入链接中。3.2. 线程环 当同一颜色的线程在多个输入链接中被接收到或者接收到的线程颜色是由接收节点分配时，我们就称线程形成了循环。通过检查接收线程颜色中的IP地址部分，一个线程创建者就可以判断出它是否分配了它接收到的线程的颜色。3.3. 线程的基本行为 为了防止LSP路由环，通过使用线程：“扩展”、“回绕”、“撤销”、“合并”、“滞留”来定义

14、线程的五个基本行为。本部分仅描述每个基本行为，并不描述这些基本行为是如何相互作用以及整个算法是如何起作用的。算法的主体部分将在每4部分描述。线程的扩展(extending) 当一个节点开始发送一个带有一组线程属性的路径建立消息给它的下一跳时，我们就说“此节点创建了一个线程并将之向下游扩展”。当一个节点从其上游节点接收到带有一组线程属性的路径建立消息并将其发向它的下游时，我们就说“此节点接收到一个线程并将之向下游扩展”。线程的颜色和跳数就成为输出链接的颜色和跳数。在一个特定的链接处，不管何时接收到一个线程，线程的颜色都将代替链接先前所具有的任何颜色和跳数而成为该输入链接当前的颜色和跳数。 例如，

15、当一个入口节点初始化一个路径建立时，它就创建了一个线程并通过发送一个路径建立消息将其扩展到下游。线程跳数被设置为1，线程颜色用一个合适的事件标识符被设置为入口节点的地址，TTL线程被设置为它的最大值。 当一个节点接收一个线程并且将之扩展至下游时，节点或者（i）不改变颜色扩展线程或者(ii)改变颜色扩展线程。如果线程是在一个新的输入链接上被接收并在一个已经存在的输出链接上被扩展，那么这个被接收的线程就会被改变颜色扩展，其他情况下，线程的扩展就不用改变颜色。当一个线程被改变颜色扩展时，一个新的颜色的线程就被创建和并被扩展。 线程的创建不仅仅只在叶节点才会发生。如果一个中间节点有一个输入链接，无论何

16、时它获得一个新的下一跳时，它就会创建和扩展一个新的线程。 当一个节点注意到一个链接跳数减少的下一跳节点时，只要它不是在扩展一个带颜色信息的线程，一个透明线程就会被扩展。线程合并(merging) 当一个具有颜色的输出链接的节点接收到一个新线程时，它不必一定要扩展新线程。相反，它可以将新线程“合并”到现有的输出线程中。在这种情况下，没有消息被送往下游。而且 ，如果一个新的输入线程被扩展至下游时，但同时还有其它的输入线程时，这些其它的输入线程将被考虑合并到新的输出线程中。 特别的是，如果具有所有下列情形，那么一个接收线程就被合并：1) 一个带颜色信息的线程被节点N接收2) 线程不形成循环3) N是

17、一个出口节点4) N的输出链接是带有颜色的5) N的输出链接跳数至少比新近接收到的线程跳数大16) 当一个输出线程回绕时，（参看下面），任何一个与之合并的输入线程也将回绕。线程滞留(stalling) 当一个带颜色信息的线程被接收到时，如果线程形成了一个环路，则接收到的线程不被扩展，且它的颜色和跳数将被存储到接收线程的链接中。这是线程合并的特例，仅适用于形成环路的线程，并被称为“线程滞留”。存储滞留线程的输入链接被称为“滞留输入链接”。滞留输入链接与非滞留输入链接之间存在显著的差别。 线程回绕（rewinding） 当线程到达一个能实现特殊的自由环路节点时，该节点能够在线程被扩展的相反路径上返

18、回一个应答消息给消息的产生者。应答消息的传送过程就是线程的“回绕”。 自由环路情况如下： 一个带颜色信息的线程被出口节点接收，或 包含下列所有情况：(a) 一个带颜色信息的线程被节点N接收，并且(b) N节点的输出链接是透明色，并且 (c) N节点的输出链接跳数至少比新近接收的线程跳数大1 当一个节点回绕一个在特殊链接上接收到的线程时，它就将链接的颜色改为透明色。 如果从节点M到节点N有一个链接，并且M在此链接上扩展了一个线程到N，而M确定了（通过接收N的一条消息）N已经回绕了那个线程，那么M就设置输出链接的颜色为透明色。然后M继续回绕线程，除此而外，还回绕任何已经被回绕的线程合并的输入线程，

19、其中包含滞留线程。 每一个节点均可在所有的输入输出链接变为透明色之后开始标签交换。 注意透明色的线程是已经被回绕的线程；因此，不存在回绕一个具有透明色的线程这样的事情。 线程撤销（Withdrawing） 从路径上退出对于一个线程而言是可能的。一个节点通过向它的下一跳发送一个退出消息从其下游路径的某一部分退出。这个过程被称为“线程撤销。” 例如，假设一个节点正试图建立一条路径，然后遇到了下一跳变化或者下一跳丢失的情况。它就会撤销掉那个向旧的下一跳扩展的线程。 如果节点M已经扩展了一个线程到节点N并且节点M然后又撤销了那个线程，那么现在节点N的输入链接就会比先前要少1。如果现在节点N没有其它的非

20、滞留线程并且也不是符合条件的叶节点，那么它就必须撤销掉它的输出线程。如果节点仍然还有一个非滞留输入链接或者节点N是一个符合条件的叶节点，它就可能（也可能不）需要改变输出链接的跳数。 下列情况下，节点N需要改变输出跳数： 1）刚消除的输出链接跳数比现存的任何输入链接的跳数都要大，并且 2）包含下列情形之一 a)输出链接是透明色的，或者 b)输出链接具有一个已知的跳数 如果输出链接是透明色的，那么它仍然保持透明色，不过，新的跳数仍需要被送至下游。如果输出链接是带有颜色信息的，一个新的线程（带有一种新颜色）需要被创建并且被扩展到下游。 3.4 线程基本行为实例 下面的符号用于描述线程基本行为的实例。

21、 每个链接中的两个线程属性通过“(C,H)”来表示，这里C和H分别代表线程的颜色和线程跳数。 被标以“+”号的线程表示它正在被创建或接收。标以“-”号的线程表示它正在被撤销。 用一个方括号标记的链接（也就是，“a”）表示它是一个非滞留的链接。用一个花括号标记的链接（也就是，“a”）表示它是一个滞留链接。 图2显示了一个叶节点创建一个蓝色线程并将其向下游扩展的例子。 (bl,1) A-o1- 图2 . 在叶节点扩展的线程 图3显示了在中间节点处不改变颜色对线程进行扩展的例子。假设节点B在接收到蓝色线程之前没有输入，输出链接。当节点B在一新链接i1处接收到一个跳数为1的蓝色线程时，它将线程扩展到下

22、游并且不改变线程的颜色（图3(a)）。在蓝色线程被扩展后，节点B又在输入链接i1处接收到一不知跳数的红色线程（图3(b)）。红色线程也被不改变颜色地扩展，因为i1和o1都已经存在了。 (bl,1)+ (bl,2) (re,U)+ (re,U) -i1-B-o1- -i1-B-o1- 图3(a) 图3(b) 图3. 不改变颜色的线程扩展例子 图4显示了改变颜色的线程扩展例子。图4(a)中只有一个输入链接i1和一个输出链接o1。然后跳数为3的一个红色线程在新的输入链接i2处被接收。在这种情况下，接收的线程将会改变颜色进行扩展，也就是，一个绿色线程被创建并被扩展（图4(b)），因为o1已经存在了。

23、(bl,1) (bl,2) (bl,1) (gr,4) -i1-B-o1- -i1-B-o1- | -i2-+ (re,3)+ 图4(a) 图4(b) 图4. 改变颜色的线程扩展例子 图5显示了一个线程合并的例子。当一个节点B接收到一个跳数为3的红色线程时，因为输出链接跳数至少比接收的线程跳数大1，故而此接收到的线程并不被扩展。当输出链接o1处的蓝色线程被回绕时，红色线程和蓝色线程都将被回绕。 (bl,3) (bl,4) -i1-B-o1- | -i2-+ (re,3)+ 图5. 线程合并 图6和7显示了线程滞留的例子。当一个节点B在图6中的输入链接i2处接收到一个跳数为10的蓝色线程时，由于

24、蓝色线程形成了一个环路，它“滞留”了接收的线程。在图7中，一个叶节点A找到了其自身线程的环路。 (bl,3) (bl,4) -i1-B-o1- | -i2-+ (bl,10)+ 图6 线程滞留（1） (bl,10)+ (bl,1) -i1-A-o1- 图7 线程滞留（2） 图8显示了一个线程回绕的例子。当一个正被扩展的黄色线程被回绕时（图8(a)），节点会将会把所有的输入输出线程的颜色改变为透明色，并且将线程的回绕传播至上游节点（图8(b)）. (bl,1) (ye,2) (tr,1) (tr,2) -i2-B-o1- -i2-B-o1- | | -i3-+ -i3-+ (ye,1) (tr,

25、1) 图8(a) 图8(b) 图8 线程回绕 图9显示了一个线程撤销的例子。在图9(a)中，在输入链接i2中红色线程被撤销了。然后Hmax从3减小至1。节点B创建了一个新的绿色线程并且将它向下游扩展，如图9(b)所示。 (bl,1) (re,4) (bl,1) (gr,2)+ -i1-B-o1- -i1-B-o1- | -i2-+ (re,3)- 图9(a) 图9(b) 图9 线程撤销(1) 图10显示了线程撤销的另一个例子。在图10(a)中，输入链接i3处的红色线程被撤销了。在这种情况下，Hmax从未知减至1，然而，如图10(b)所示，此时没有线程被扩展，因为输出链接有一个带有颜色信息的线程

26、并且跳数是未知的。 (bl,1) (re,U) (bl,1) (re,U) -i2-B-o1- -i2-B-o1- | -i3-+ (re,U)- 图10(a) 图10(b) 图10 线程撤销(2) 图11显示了另一个线程撤销的例子。在图11(a)中，输入链接i3上的透明线程被撤销了。在这种情况下，一个透明线程被扩展（图11(b)）,因为Hmax减小了而且输出链接又是透明的。 (tr,1) (tr,U) (tr,1) (tr,2)+ -i2-B-o1- -i2-B-o1- | -i3-+ (tr,U)- 图11(a) 图11(b) 图11 线程撤销(3) 4线程算法 这里假设为下游按需等级分配

27、，然而，此算法也适用于下游等级分配，这将在第5部分讲述。 在此算法中，下一跳的变化事件将被分成两个事件：依次为旧下一跳上的下一跳丢失事件和新下一跳上的下一跳获取事件。 下面的符号被定义： Hmax: 最大的输入链接跳数 Ni: 非滞留输入链接数目 线程算法描述如下： 当一个节点获得一个新下一跳时，它就创建一个事带有颜色信息的线程并且把它扩展到下游。 当一个节点丢失它向之扩展线程的下一跳时，它可能会撤销掉那个线程。正如第3部分所描述的那样，这将可能会也可能不会引起下一跳的某种反应。在这些反应中，下一跳采取的可能反应就是从它自己的下一跳中撤销掉线程，或者扩展一个新线程到它自己的下一跳。 一个收到的

28、带有颜色信息的线程或者被滞留，或者被合并，或者被回绕，或者被扩展。一个带有TTL为0的线程永远不会被扩展。 当一个接收线程在一个节点被滞留时，如果Ni=0并且此节点不是一个符合条件的叶节点，就会产生线程的撤销。否则，如果Ni0并且接收线程的跳数是未知的，一个带有颜色信息的线程被创建并被扩展。如果接收的线程跳数是未知的，则就不会有线程被扩展，节点也不会采取有进一步。 当一个正在被扩展的线程被回绕时，如果线程的跳数比Hmax还大1，一个跳数为(Hmax+1)的线程将被扩展至下游。 当一个具有透明色的输出链接节点接收到一个有透明色的线程时，如果Hmax减少的话，那么节点将对它进行不改变颜色的下游扩展

29、。5. 算法的适用性 第4部分描述的线程算法可以运用于不同的LSP管理决策。5.1 LSP路由环的预防/检测 同一个线程算法既可以适用于LSP路由环的预防也可以适用于检测。 在路由环预防模式中，只有当节点为LSP回绕线程时，它才会传送一个标签映射（包含一个线程对象）给LSP。只有线程被回绕时，才会有映射消息被发送。 另一方面，如果一个节点在路由环检测模式下，它在接收到一个带有颜色信息的线程时，它会立刻返回一个不含线程对象的标签映射消息。一个接收不含有线程对象的标签映射消息的节点不能回绕线程。 5.2 当新路径上有路由环时使用旧路径 当一个路由发生变化时，如果新路由是路由环时，你可能会想继续使用

30、旧的路径。这很简单，只要将分配给旧路径上的下游链接的标签一直保留到新路由上被扩展的线程被回绕。这是一个执行选择。5.3 如何处理下游等级分配 线程机制也可适用于下游等级分配模式（或由出口控制等级），但前提是将新近从下一跳接收一条标签映射消息的事件看作是下一跳获取事件。 注意一个没有输入链接的节点可看作是一个叶节点。在树刚被建立的情况下（例如，出口节点刚刚出现），每一个节点在短期内将依次被看作是一个叶节点。5.4. 如何实现负载的分离 一个叶节点通过为同一个FEC建立两个不同的LSPs可以很容易的实现负载的分离。只不过两个LSPs的下游链接要被分配不同的颜色。这里的线程算法不但在两条路径上都可防

31、止路由环，而且还允许两条路径有一个公共的下游节点。 若一些中间节点也想进行负载分离，则需做如下修改。假设同一个FEC有多个下一跳。如果一个特定的FEC有n个下一跳，那么为FEC的LSP的建立输入链接将被划分为建立n个子链接，每一子链接对应到一个不同的输出链接上。 这为为FEC提供了n个LSPs。每一个这样的LSP为各自的输出链接使用不同的颜色。这里，线程算法不但防止了任何一条路径上的路由环，而且还允许其中两个路径或更多的路径有一个公共的下游节点。 在这种情况下，将会发生一个有趣的现象。我们用图12来说明这一点：节点B有两个输入链接,i1和i2,两个输出链接o1和o2，这样i1就被映射到o1,同

32、时i2被映射到o2。 若一在i1处被接收并在o1处被扩展的蓝色线程又在节点B处的i2被接收，这个蓝色线程并不被认为是形成了一个环，因为i1和i2被认为属于不同的子链接。另一种情况是，蓝色线程在i2被接收并在o2被扩展。如果在o2被扩展的线程被回绕，一个独特的穿过节占B的自由环路LSP就会被建立。 +-.-+ . (bl,3) (bl,4) | . -i1-+ +-o1- . -+ . / . v / | B | +-i2-B-o2- (bl,10)+ (bl,11) 图12 中间节点处的负载分离 还有一种类型的负载分离，在此类型中，到达单个输入链接中的包将被标签交换到任何一个多输出链接中。这种

33、方法并不是一个好的负载分离的好方案，因为同一个FEC中的包的次序并没有被保存。因此，本文并不着重讲这种情况。 不管是不是一个好的负载分离方案，由于ATM交换不能在每一个包的基础上作转发决定，故而仍存在ATM-LSRs不能照前面的方案进行负载分离的实际情况。6为什么算法是有效的？6.1 为什么一个带有未知跳数的线程被扩展 在算法中，当一个线程环被检测时，一个未知跳数的线程就被扩展。这样可以通过合并那些具有未知跳数流入流出路由环的线程来减少路由环预防信息的数目。参看附录A.12 6.2. 为什么一个回绕的线程不能包含一个环？6.2.1. 情况1：具有已知跳数的LSP 当输出链接跳数不是“未知的”时

34、，我们怎样才能保证一个已被建立的路径不含有路由环呢？ 考虑一个LSRs序列，这样在序列中就存在一个穿过LSRs的路由环。（例如，包从R1传到R2,再传到R3,等等，再到Rn，然后再从Rn传到R1）。 假设R1和R2之间的链接的线程跳数是k,那么通过上述过程，在Rn和R1之间的跳数必定为k+n-1。但是算法也保证了如果一个节点有一个输入跳数为j，则它的输出跳数必须至少是j+1。因此，如果我们假设由于线程回绕而建立的LSP具有一个路由环，在R1和R2之间的跳数至少是k+n。从这一点来看，我们可能会得出一个很可笑的结论：n=0，我们因此也许会得出结论：根本不存在这样的LSRs序列。6.2.2. 情况

35、2：具有未知跳数的LSP 当输出链接跳数是“未知的”时，一个已建立的路径也不包含一个路由环。这是因为一个带有颜色信息和未知跳数的线程只有在它到达出口时才会被回绕。6.3. 为什么L3路由环被检测 不管线程跳数是已知的还是未知的，如果存在一个路由环，那么环路中的某一节点将是通过一个新的输入链接接收线程的最后一个节点。这个线程将总是不改变颜色信息地回到那个节点。因此路由环总是可以通过环路中的至少一个节点被检测。6.4. 为什么L3不被错误地检测 因为从没有一个节点会将具有同样颜色的线程向下游扩展两次，故只有存在L3路由环时，一个线程环才会被检测到。65一个滞留线程怎样自动地从环路中恢复 一旦线程在

36、环路中被滞留，线程（或路径建立请求）有效地保留在环路中，所以路径的重配置（也就是，旧路径上的线程撤销和新路径上的线程扩展）来源于任何一个接收路由变化事件以打破环的节点。6.6. 为什么不同颜色的线程不能相互追赶？ 在算法中，如果同一时间内有几个节点开始扩展线程，那么就会发生多个线程颜色和/或者跳数的更新。我们怎样才能预防多个线程无限制地循环呢？ 首先，当一个节点发现有一个线程形成环时，它就创建一个带有“未知的”跳数的线程。所有的此后到达节点，带有已知跳数的环线程都将被合并到这个线程。这样一个线程就象一个线程吸收器。 其次，“改变颜色的线程扩展”预防了两个线程的相互追赶。 假定一个接收线程总是被

37、不改变颜色的扩展。那么我们就遇到下列的情形。 G Y | | v v R1-R2 | | v R4-R3 图13 线程追赶的例子 在图13中，(1)节点G获得R1作为其下一跳并且开始扩展一跳数为1的绿色线程，（2）节点Y获得R2作为其下一跳，并且开始扩展一跳数为1的黄色线程。(3)节点G和节点Y会在这些线程向前流传之前撤销它们。 在这种情况下，黄色和绿色线程会回转并各自回到R2和R1。然而当线程回到R2和R1时，存放线程颜色的输入链接已不存在了。结果，黄色和绿色线程将永远在环中相互追赶。 不过，既然我们有“改变颜色的扩展”机制，所以上述现象实际上不会发生。当R2处接收到一个绿色线程时，R2通过

38、改变其颜色来扩展它，也就是，创建一个新的红色线程并扩展它。类似地，当R1处接收到一个黄色线程时，R1就创建一个新的紫色线程并扩展它。因此，甚至在节点G和Y已经撤销掉线程之后，线程环也会被检测到。这就确保了环附近的带有环中某节点所分配的颜色的线程被扩展。 至少还存在着一种甚至“改变颜色的扩展”也不能处理的情形。这就是“自追赶”。在自追赶中，线程的扩展和撤销都是根据环中相互追赶的同一个线程进行的。这种情况将发生在节点扩展一个线程到一个L3环后立刻撤销掉该线程时。 一种探测自追赶的方法就是在撤销线程的节点处延迟线程撤销的执行。不管怎样，TTL线程机制可以删除任何种类的线程环。7. 环预防的例子 本部

39、分，我们将用两个例子来显示在给定网络中算法是如何实现LSP环预防的。 我们假定使用下游等级按需分配，并且所有的LSPs都与同一个FEC相关，而且所有的节点是能够VC合并的。7.1 第一个例子 考虑图14所示的一个MPLS网，其中存在一个L3环。每个直接链接表示每个节点当前的FEC下一跳。这里，叶节点R1和R6产生LSP的创建。 R11 - R10 R2 - R3 - R4 - R5 leaf | | | R6 - R7 - R8 leaf 图 14 MPLS网络的例子（1） 假设R1和R6同时发送一个标签请求消息并且将TTL线程初始化为255。下面我们将先显示一个如何预防LSP环的例子。 线程

40、属性的设置通过（颜色，跳数，TTL）来表示。 来自R1和R6的请求各包含（re,1,255）和（b1,1,255）。 假设R3在收到R6的请求之前收到了R1的请求。当R3接收到第一个带红色线程的请求时，R3不改变它的颜色且赋之属性（re,3,253）转发，因为接收的输入和输出链接都是刚刚创建的。然后R3收到了第二个带蓝色线程的请求。此时，输出链接已经存在了。因而，R3就执行改变颜色的线程扩展，也就是，创建一个新的棕色线程并赋予属性（br,4,255）转发。 当R2接收到R10的属性为（re,6,250）的请求时，它发现R3形成了一个环且滞留了红色线程。然后，R2通过发送一个带属性为(pu,U,

41、255)的请求给R3，创建一个紫色带有未知跳数的线程并将它扩展至下游，这里“U”代表“未知的”。 此后，R2从R10接收到另一个属性为（br,7,252）的请求。棕色线程被合并到紫色线程中。R2不需要向R3发送请求。 另一方面，紫色线程通过现存的链接不改变颜色回转。R2发现线程环并滞留紫色线程。因为接收到的线程跳数是未知的，因而再没有线程被创建。在这种情况下，没有线程回绕发生。当前的网络状态如图15所示。 *: 线程被滞留的位置 (pu,U) R11 - R10 R2 - R3 - R4 - R5 leaf (re,1) (pu,U) (pu,U) | | (bl,3) | R6 - R7 -

42、 R8 leaf (bl,1) (bl,2) 图15 网络状态 然后R10将它的下一跳从R2换到R11。 因为R10在旧的下游链接上有一个紫色线程，为了撤销紫色线程它要先发送一个拆卸消息给它的旧的下一跳R2。接着，它创建一个未知跳数的绿色线程并发送属性为（gr,U,255）的请求给R11。 当R2接收到来自R10的拆卸消息时，R2就将R10和R2之间的被滞留的输入链接移去。 另一方面，绿色线程到达R1时，Hmax从0更新到未知。在这种情况下，由于线程是在新的输入链接上被接收并在已存在的输出链接上被扩展，所以R1执行改变颜色的线程扩展。结果就是，R1创建了一个桔黄色的具未知跳数的线程并将之扩展至R2。 桔黄色的线程通过已有的链接进行不改变颜色的回转，最终它被滞留在R1。 现在的网络状态如图16所示。 *: 线程滞留的位置 (or,U) (or,U) R11