rfc3063.txt

283个中文RFC文档

        当一个具有颜色的输出链接的节点接收到一个新线程时，它不必一定要扩展新线程。相反，它可以将新线程“合并”到现有的输出线程中。在这种情况下，没有消息被送往下游。而且 ，如果一个新的输入线程被扩展至下游时，但同时还有其它的输入线程时，这些其它的输入线程将被考虑合并到新的输出线程中。
        特别的是，如果具有所有下列情形，那么一个接收线程就被合并：
1) 一个带颜色信息的线程被节点N接收
2) 线程不形成循环
3) N是一个出口节点
4) N的输出链接是带有颜色的
5) N的输出链接跳数至少比新近接收到的线程跳数大1
6) 当一个输出线程回绕时，（参看下面），任何一个与之合并的输入线程也将回绕。

线程滞留(stalling)      
      当一个带颜色信息的线程被接收到时，如果线程形成了一个环路，则接收到的线程不被扩展，且它的颜色和跳数将被存储到接收线程的链接中。这是线程合并的特例，仅适用于形成环路的线程，并被称为“线程滞留”。存储滞留线程的输入链接被称为“滞留输入链接”。滞留输入链接与非滞留输入链接之间存在显著的差别。
   
线程回绕（rewinding）
        当线程到达一个能实现特殊的自由环路节点时，该节点能够在线程被扩展的相反路径上返回一个应答消息给消息的产生者。应答消息的传送过程就是线程的“回绕”。            
        自由环路情况如下：
        一个带颜色信息的线程被出口节点接收，或
       包含下列所有情况：
(a) 一个带颜色信息的线程被节点N接收，并且
(b) N节点的输出链接是透明色，并且
         (c) N节点的输出链接跳数至少比新近接收的线程跳数大1
      当一个节点回绕一个在特殊链接上接收到的线程时，它就将链接的颜色改为透明色。
      如果从节点M到节点N有一个链接，并且M在此链接上扩展了一个线程到N，而M确定了（通过接收N的一条消息）N已经回绕了那个线程，那么M就设置输出链接的颜色为透明色。然后M继续回绕线程，除此而外，还回绕任何已经被回绕的线程合并的输入线程，其中包含滞留线程。
      每一个节点均可在所有的输入输出链接变为透明色之后开始标签交换。
      注意透明色的线程是已经被回绕的线程；因此，不存在回绕一个具有透明色的线程这样的事情。

   线程撤销（Withdrawing）
   
      从路径上退出对于一个线程而言是可能的。一个节点通过向它的下一跳发送一个退出消息从其下游路径的某一部分退出。这个过程被称为“线程撤销。”     
        例如，假设一个节点正试图建立一条路径，然后遇到了下一跳变化或者下一跳丢失的情况。它就会撤销掉那个向旧的下一跳扩展的线程。      
        如果节点M已经扩展了一个线程到节点N并且节点M然后又撤销了那个线程，那么现在节点N的输入链接就会比先前要少1。如果现在节点N没有其它的非滞留线程并且也不是符合条件的叶节点，那么它就必须撤销掉它的输出线程。如果节点仍然还有一个非滞留输入链接或者节点N是一个符合条件的叶节点，它就可能（也可能不）需要改变输出链接的跳数。      
      下列情况下，节点N需要改变输出跳数：
       1）刚消除的输出链接跳数比现存的任何输入链接的跳数都要大，并且
       2）包含下列情形之一
       a)输出链接是透明色的，或者
       b)输出链接具有一个已知的跳数          
       如果输出链接是透明色的，那么它仍然保持透明色，不过，新的跳数仍需要被送至下游。如果输出链接是带有颜色信息的，一个新的线程（带有一种新颜色）需要被创建并且被扩展到下游。         
   
3.4   线程基本行为实例   
        下面的符号用于描述线程基本行为的实例。  
        每个链接中的两个线程属性通过“(C,H)”来表示，这里C和H分别代表线程的颜色和线程跳数。   
        被标以“+”号的线程表示它正在被创建或接收。标以“-”号的线程表示它正在被撤销。   
        用一个方括号标记的链接（也就是，“[a]”）表示它是一个非滞留的链接。用一个花括号标记的链接（也就是，“{a}”）表示它是一个滞留链接。 
        图2显示了一个叶节点创建一个蓝色线程并将其向下游扩展的例子。
                                       (bl,1)
                                 A---[o1]--->
                 图2  .  在叶节点扩展的线程

        图3显示了在中间节点处不改变颜色对线程进行扩展的例子。假设节点B在接收到蓝色线程之前没有输入，输出链接。当节点B在一新链接i1处接收到一个跳数为1的蓝色线程时，它将线程扩展到下游并且不改变线程的颜色（图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已经存在了。
       (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的蓝色线程时，由于蓝色线程形成了一个环路，它“滞留”了接收的线程。在图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,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)所示，此时没有线程被扩展，因为输出链接有一个带有颜色信息的线程并且跳数是未知的。
           (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．线程算法
        这里假设为下游按需等级分配，然而，此算法也适用于下游等级分配，这将在第5部分讲述。
        在此算法中，下一跳的变化事件将被分成两个事件：依次为旧下一跳上的下一跳丢失事件和新下一跳上的下一跳获取事件。
       下面的符号被定义：
         Hmax: 最大的输入链接跳数
         Ni:   非滞留输入链接数目

        线程算法描述如下：   
        当一个节点获得一个新下一跳时，它就创建一个事带有颜色信息的线程并且把它扩展到下游。   
        当一个节点丢失它向之扩展线程的下一跳时，它可能会撤销掉那个线程。正如第3部分所描述的那样，这将可能会也可能不会引起下一跳的某种反应。在这些反应中，下一跳采取的可能反应就是从它自己的下一跳中撤销掉线程，或者扩展一个新线程到它自己的下一跳。   
        一个收到的带有颜色信息的线程或者被滞留，或者被合并，或者被回绕，或者被扩展。一个带有TTL为0的线程永远不会被扩展。   
        当一个接收线程在一个节点被滞留时，如果Ni=0并且此节点不是一个符合条件的叶节点，就会产生线程的撤销。否则，如果Ni>0并且接收线程的跳数是未知的，一个带有颜色信息的线程被创建并被扩展。如果接收的线程跳数是未知的，则就不会有线程被扩展，节点也不会采取有进一步。   
        当一个正在被扩展的线程被回绕时，如果线程的跳数比Hmax还大1，一个跳数为(Hmax+1)的线程将被扩展至下游。  
        当一个具有透明色的输出链接节点接收到一个有透明色的线程时，如果Hmax减少的话，那么节点将对它进行不改变颜色的下游扩展。