rfc2174.txt

著名的RFC文档,其中有一些文档是已经翻译成中文的的.

    Routing    V   T       T       T   V   T       T       T   V
    Table      +-------+-------+-------+-------+-------+-------X
    Entry             metric < 16      |       metric = 16     |

               ----------------------->|---------------------->|
                   EXPIRATION_TIMER            GC_TIMER
                                                       Stop Advertising
                                                               |
    Advertised                                                 V
    Metric     --   metric <16   ------+--  metric = 16 -------X

                                                    T: FULL_UPDATE_TIME

                       Figure 3. Route Expiration

3.4.3 Slow Convergence Prevention

   To prevent slow convergence of routing information, two techniques,
   split horizon with poisoned reverse, and triggered update are
   employed.








Murakami & Maruyama          Informational                      [Page 6]

RFC 2174                         MAPOS                         June 1997


           Sn <------------- S3 <- S2 <- S1

                   (i) Before Outage

                                ->
           Sn <--    X    -- S3 <- S2 <- S1

                   (ii) After Outage

                Figure 4 An Example of Slow Convergence

   Figure 4 shows an example of slow convergence[6]. In (i), three
   switches, S1, S2, and S3, are assumed to have a route to Sn. In (ii),
   the connection to Sn has disappeared because of an outage, but S2
   continue to advertise the route since there is no means for S2 to
   detect the outage immediately and it has the route to Sn in its
   routing table. Thus, S3 misunderstand that S2 has the best route to
   Sn and S2 is the next hop. This results in a transitive loop between
   S2 and S3. S2 and S3 increments the metric of the route to Sn every
   time they advertise the route and the loop continues until the metric
   reaches 16. To suppress the slow convergence problem, split horizon
   with poisoned reverse is used.

   In split horizon with poisoned reverse, a route is advertised as
   unreachable to the next hop. The metric is the received metric value
   plus 16. For example, in Figure 4, S2 advertises the route to Sn with
   the metric unreachable only to S3. Thus, S3 never considers that S2
   is the next hop to Sn. This ensures fast convergence on disappearance
   of a route.

   Another technique, triggered update, forces a switch to send an
   immediate update instead of waiting for the next periodic update when
   a switch detects a local port failure, or when it receives a message
   that a route has become unreachable, or that its metric has
   increased. This makes the convergence faster.

4. Broadcast/multicast Routing in SSP

   This section explains VRPB algorithm and the outline of
   broadcast/multicast routing protocol.











Murakami & Maruyama          Informational                      [Page 7]

RFC 2174                         MAPOS                         June 1997


4.1 Virtual Reverse Path Broadcast/Multicast Algorithm

   SSP provides broadcast/multicast routing based on a spanning tree
   algorithm.  As described in Section 2, the routing is based on the
   VRPB(Virtual Reverse Path Broadcast) algorithm.  In VRPB, each switch
   assumes that all broadcast and multicast frames are generated by a
   specific switch, VSS(Virtual Source Switch). Thus, unlike DVMRP, a
   MAPOS network has only one spanning tree at any given time.

   The frames are forwarded along the reverse path by computing the
   shortest path from the VSS to all possible recipients.  VSS is the
   switch which has the lowest switch number in the network.  Because
   the routing table contains all the unicast destination addresses
   including the switch numbers, each switch can identify the VSS
   independently by searching for the smallest switch number in its
   unicast routing table.

   In Figure 2, switch S1 is the VSS.  Each switch determines its place
   in the spanning tree, relative to the VSS, and which of its ports are
   on the shortest path tree.  Thus, the spanning tree is as shown in
   Figure 5. Except for the VSS, each switch has one upstream port and
   zero or more downstream ports. VSS have no upstream port, since it is
   the root of the spanning tree. In Figure 2.  switch S2's upstream
   port is port 0x09 and it has no downstream port.

                   S1 (VSS)
                  /  \
                 /    \
                /      \
               S2      S3

                      Figure 5  VRPB Spanning Tree

   When a switch receives a broadcast/multicast frame, it forwards the
   frame to all of the upstream switch, the downstream switches, and the
   directly connected nodes. However, it does not forward to the switch
   which sent the frame to it. For that purpose, a bit mapped
   broadcast/multicast routing table may be employed.  The
   broadcast/multicast routing process marks all the bits corresponding
   to the ports to which frames should be forwarded. The forwarding
   process refers to it and broadcasts a frame to all the ports with its
   corresponding bit marked.

4.2 Forwarding Broadcast/multicast Frames

   When a switch forwards a broadcast/multicast frame, (1) it first
   decides the VSS by referring to its unicast routing table. Then, (2)
   it refers to its broadcast/multicast routing table corresponding to



Murakami & Maruyama          Informational                      [Page 8]

RFC 2174                         MAPOS                         June 1997


   the VSS. A cache may be used to reduce the search overhead. (3) Based
   on the routing table, the switch forwards the frame.

   Figure 6 shows an example of S2's broadcast/multicast routing table
   for the VSS S1. It is a bit map table and each bit corresponds to a
   port. The value 1 indicates that frames should be forwarded to a node
   or a switch through the port.  If no bit is marked, the frame is
   silently discarded. In the example of Figure 6, port 0x09 is the
   upstream port to its VSS, that is, S1. Other ports, ports 0x05 and
   0x03 are path to N2 and N1 nodes, respectively.

             0F  0D  0B  09  07  05  03  01   ---   port number
           +---+---+---+---+---+---+---+---+
           | 0 | 0 | 0 | 1 | 0 | 1 | 1 | 0 |  ---   1: forward
           +---+---+---+---+---+---+---+---+        0: inhibit

            Figure 6 Broadcast/Multicast Routing Table of S2

4.3 Forwarding Path Examples

   Assume that a broadcast frame is generated by N2 in Figure 2. The
   frame is received by S2.

   Then, S2 passes it to all the connected nodes except for the source
   N2. That is, only to N1. At the same time, it also forwards the frame
   to all its upstream and downstream switches. Since S2 has no
   downstream switch, S2 forwards the frame to S1 though its upstream
   port 0x09.

   S1 is the VSS and it passes the frame to all the local nodes, that
   is, only to N3. Since it has no upstream switch and S2 is the switch
   which sent the frame to S1, the frame is eventually forwarded only to
   a downstream switch S3.

   S3 passes the frame to its local node, N4. Since S3 has only an
   upstream and the frame was received through that port, S3 does not
   forward the frame to any switch.

   The resulting path is shown in Figure 7. Although this is not the
   optimal path, VRPB ,at least, ensures that broadcast/multicast frames
   are delivered all the nodes without a loop. Figures 8 and 9 show the
   forwarding path for frames generated by a node under S3 and S4,
   respectively.








Murakami & Maruyama          Informational                      [Page 9]

RFC 2174                         MAPOS                         June 1997


                             +-> N3
                             |
             N2 -> S2 +-> S1 +-> S3 -> N4
                      |
                      +-> N1

                   Figure 7  Forwarding Path from N2

                             +-> N1
                             |
             N3 -> S1 +-> S2 +-> N2
                      |
                      +-> S3 --> N4

                   Figure 8  Forwarding Path from N3


                             +-> N3
                             |
             N4 -> S3 +-> S1 +-> S2 +-> N1
                                    |
                                    +-> N2

                   Figure 9  Forwarding Path from N4

4.4 Suppressing Routing Loop

   To suppress transitive routing loop, forward delay is employed. A
   switch suspends broadcast/multicast forwarding for a period after a
   new VSS is found in the routing table. This prevents transitive
   routing loop by waiting for all the switches to have the same routing
   information and become synchronized. In addition to controlling
   sending of frames by forward delay, another mechanism is employed to
   prevent transitive routing loop by controlling reception of frames.
   That is, broadcast/multicast frames received through ports other than
   the upstream and downstream ports are discarded.

4.5 Upstream Switch Discovery

   The upstream port is determined by the shortest reverse path to the
   VSS.  It is identified by referring to the next hop port of the route
   to VSS in the local unicast routing table. When a new next hop to the
   VSS is discovered, the bit corresponding to the old next hop port is
   cleared, and the bit corresponding to the new one is marked as the
   upstream port in the broadcast/multicast routing table.






Murakami & Maruyama          Informational                     [Page 10]

RFC 2174                         MAPOS                         June 1997


4.6 Downstream Switch Discovery

   To determine the downstream ports, split horizon with poisoned
   reverse is employed. When a switch receives a route with a metric
   poisoned by split horizon processing through a port as described in
   Section 3.4.3, the port is considered to be a downstream port. In
   Figure 2, S1 is the VSS and the route information is sent back from
   S2 to S1 with metric unreachable based on the split horizon with
   poisoned reverse. Thus, S1 knows that S2 is one of its downstreams.

4.7 Downstream Port Expiration

   When a poison reversed packet is newly received from a port, the
   local switch knows that a new downstream switch has appeared. Then,
   it marks the bit corresponding to the port and starts
   FORWARD_DELAY_TIMER (30second by default, that is, FULL_UPDATE_TIME *
   3) for the port. The forwarding of broadcast/multicast frames to the
   port is prohibited until the timer expires.  Every time the local
   switch receives a poison reversed packet through a port, it
   initializes PORT_EXPIRATION_TIMER(30 seconds by default, that is,
   FULL_UPDATE_TIME *3) corresponding to the port. A continuous loss of
   poison reversed packets or a failure of downstream port results in
   expiration of PORT_EXPIRATION_TIMER, and the corresponding bit is
   cleared.

               First Update               Last Update
                   |                           |
                   V T   T   T   T   T   T   T V
                   +---+---+---+---+---+---+---+---+---+---+---+---+---
   A bit in
   the routing      0   0   0   1   1   1   1   1   1   1   0   0   0
   table                       ^                           ^
                    <--------->|                <--------->|
                        ^   route up                 ^ route down
                        |                            |
                  FORWARD_DELAY               PORT_EXPIRATION

                                           T: FULL_UPDATE_TIME

                       Figure 10. Port Expiration

   When a downstream switch discovers another best path to the VSS or a
   new VSS, it stops split horizon with poison reverse and sends
   ordinary update messages. Whenever the local switch receives an
   ordinary update message from its downstream switch, it SHOULD
   immediately clear the corresponding bit in the routing table and stop
   forwarding of broadcast/multicast frames.




Murakami & Maruyama          Informational                     [Page 11]