rfc3063.txt

283个中文RFC文档

5. 算法的适用性
   
   第4部分描述的线程算法可以运用于不同的LSP管理决策。

5.1   LSP路由环的预防/检测
 
        同一个线程算法既可以适用于LSP路由环的预防也可以适用于检测。
        在路由环预防模式中，只有当节点为LSP回绕线程时，它才会传送一个标签映射（包含一个线程对象）给LSP。只有线程被回绕时，才会有映射消息被发送。
        另一方面，如果一个节点在路由环检测模式下，它在接收到一个带有颜色信息的线程时，它会立刻返回一个不含线程对象的标签映射消息。一个接收不含有线程对象的标签映射消息的节点不能回绕线程。
   
5.2  当新路径上有路由环时使用旧路径
   
        当一个路由发生变化时，如果新路由是路由环时，你可能会想继续使用旧的路径。这很简单，只要将分配给旧路径上的下游链接的标签一直保留到新路由上被扩展的线程被回绕。这是一个执行选择。

5.3    如何处理下游等级分配
   
         线程机制也可适用于下游等级分配模式（或由出口控制等级），但前提是将新近从下一跳接收一条标签映射消息的事件看作是下一跳获取事件。  
        注意一个没有输入链接的节点可看作是一个叶节点。在树刚被建立的情况下（例如，出口节点刚刚出现），每一个节点在短期内将依次被看作是一个叶节点。

5.4.  如何实现负载的分离
        一个叶节点通过为同一个FEC建立两个不同的LSPs可以很容易的实现负载的分离。只不过两个LSPs的下游链接要被分配不同的颜色。这里的线程算法不但在两条路径上都可防止路由环，而且还允许两条路径有一个公共的下游节点。
        若一些中间节点也想进行负载分离，则需做如下修改。假设同一个FEC有多个下一跳。如果一个特定的FEC有n个下一跳，那么为FEC的LSP的建立输入链接将被划分为建立n个子链接，每一子链接对应到一个不同的输出链接上。    
        这为为FEC提供了n个LSPs。每一个这样的LSP为各自的输出链接使用不同的颜色。这里，线程算法不但防止了任何一条路径上的路由环，而且还允许其中两个路径或更多的路径有一个公共的下游节点。   
        在这种情况下，将会发生一个有趣的现象。我们用图12来说明这一点：节点B有两个输入链接,i1和i2,两个输出链接o1和o2，这样i1就被映射到o1,同时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   中间节点处的负载分离
        还有一种类型的负载分离，在此类型中，到达单个输入链接中的包将被标签交换到任何一个多输出链接中。这种方法并不是一个好的负载分离的好方案，因为同一个FEC中的包的次序并没有被保存。因此，本文并不着重讲这种情况。   
        不管是不是一个好的负载分离方案，由于ATM交换不能在每一个包的基础上作转发决定，故而仍存在ATM-LSRs不能照前面的方案进行负载分离的实际情况。

6．为什么算法是有效的？

6.1   为什么一个带有未知跳数的线程被扩展
   
        在算法中，当一个线程环被检测时，一个未知跳数的线程就被扩展。这样可以通过合并那些具有未知跳数流入流出路由环的线程来减少路由环预防信息的数目。参看附录A.12 

6.2.  为什么一个回绕的线程不能包含一个环？

6.2.1.  情况1：具有已知跳数的LSP

        当输出链接跳数不是“未知的”时，我们怎样才能保证一个已被建立的路径不含有路由环呢？    
       考虑一个LSRs序列<R1,...,Rn>，这样在序列中就存在一个穿过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.  情况2：具有未知跳数的LSP

        当输出链接跳数是“未知的”时，一个已建立的路径也不包含一个路由环。这是因为一个带有颜色信息和未知跳数的线程只有在它到达出口时才会被回绕。

6.3.  为什么L3路由环被检测

        不管线程跳数是已知的还是未知的，如果存在一个路由环，那么环路中的某一节点将是通过一个新的输入链接接收线程的最后一个节点。这个线程将总是不改变颜色信息地回到那个节点。因此路由环总是可以通过环路中的至少一个节点被检测。

6.4.  为什么L3不被错误地检测
   
       因为从没有一个节点会将具有同样颜色的线程向下游扩展两次，故只有存在L3路由环时，一个线程环才会被检测到。

6．5一个滞留线程怎样自动地从环路中恢复

        一旦线程在环路中被滞留，线程（或路径建立请求）有效地保留在环路中，所以路径的重配置（也就是，旧路径上的线程撤销和新路径上的线程扩展）来源于任何一个接收路由变化事件以打破环的节点。

6.6.  为什么不同颜色的线程不能相互追赶？

       在算法中，如果同一时间内有几个节点开始扩展线程，那么就会发生多个线程颜色和/或者跳数的更新。我们怎样才能预防多个线程无限制地循环呢？   
        首先，当一个节点发现有一个线程形成环时，它就创建一个带有“未知的”跳数的线程。所有的此后到达节点，带有已知跳数的环线程都将被合并到这个线程。这样一个线程就象一个线程吸收器。
        其次，“改变颜色的线程扩展”预防了两个线程的相互追赶。 
        假定一个接收线程总是被不改变颜色的扩展。那么我们就遇到下列的情形。
                                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通过改变其颜色来扩展它，也就是，创建一个新的红色线程并扩展它。类似地，当R1处接收到一个黄色线程时，R1就创建一个新的紫色线程并扩展它。因此，甚至在节点G和Y已经撤销掉线程之后，线程环也会被检测到。这就确保了环附近的带有环中某节点所分配的颜色的线程被扩展。   
        至少还存在着一种甚至“改变颜色的扩展”也不能处理的情形。这就是“自追赶”。在自追赶中，线程的扩展和撤销都是根据环中相互追赶的同一个线程进行的。这种情况将发生在节点扩展一个线程到一个L3环后立刻撤销掉该线程时。
        一种探测自追赶的方法就是在撤销线程的节点处延迟线程撤销的执行。不管怎样，TTL线程机制可以删除任何种类的线程环。

7.  环预防的例子

        本部分，我们将用两个例子来显示在给定网络中算法是如何实现LSP环预防的。
        我们假定使用下游等级按需分配，并且所有的LSPs都与同一个FEC相关，而且所有的节点是能够VC合并的。

7.1 第一个例子

       考虑图14所示的一个MPLS网，其中存在一个L3环。每个直接链接表示每个节点当前的FEC下一跳。这里，叶节点R1和R6产生LSP的创建。
               R11 ------- R10 <----------------------R9
                |                   |                                     ^
                |                   |                                      |
                |                   |                                      |
               v                  v                                      |
               R1 --------> R2 --------> R3 --------> R4 --------- R5
              [leaf]                                ^
                                                       |
                                                       |
                                                       |
                R6 -------> R7 --------> R8
              [leaf]

                      图 14   MPLS网络的例子（1）

   
        假设R1和R6同时发送一个标签请求消息并且将TTL线程初始化为255。下面我们将先显示一个如何预防LSP环的例子。
        线程属性的设置通过（颜色，跳数，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,255)的请求给R3，创建一个紫色带有未知跳数的线程并将它扩展至下游，这里“U”代表“未知的”。
        此后，R2从R10接收到另一个属性为（br,7,252）的请求。棕色线程被合并到紫色线程中。R2不需要向R3发送请求。  
        另一方面，紫色线程通过现存的链接不改变颜色回转。R2发现线程环并滞留紫色线程。因为接收到的线程跳数是未知的，因而再没有线程被创建。在这种情况下，没有线程回绕发生。当前的网络状态如图15所示。
           *: 线程被滞留的位置 

                                      (pu,U)
               R11 ------- R10 <--------------------- R9
                |                   |                                     ^
                |                   |(pu,U)*                         |
                |                   |                                     |(pu,U)
                v                 v                                     |
                R1 -------> R2 --------> R3 --------> R4 --------- R5
              [leaf] (re,1)      (pu,U)     ^  (pu,U)
                                                      |   
                                                      |  (bl,3)
                                                      |  
                R6 -------> R7 --------> 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 <------ R10 <-------------------- R9
                |                   |                                    ^
                |(or,U)*       |                                     |
                |                   |                                     |(or,U)
                v                  |                                     |
                R1 -------> R2 --------> R3 --------> R4 --------- R5
              [leaf] (or,U)      (or,U)    ^     (or,U)
                                                      |
                                                      | (bl,3)
                                                      |
                R6 -------> R7 --------> R8