rfc1585.txt

RFC 的详细文档！

              |  +---+         +---+    +---+   |
              |  |RT5|---------|RT2|    |NAZ|   |
              |  +---+    +----+---+    +---+   |
              |           |      |        |     |
              |           |   +------------------------+
              |           |                         |      +
              |           |                         |      |
              |           |                         |      |  +---+
              |   +------------+      +             |      |--|RT7|
              |            |          |             |      |  +---+
              |          +---+        |           +---+    |
              |          |RT4|--------|-----------|RT3|----|
              |          +---+        |           +---+    |
              |                       |                    |
              |               +       +                    |
              |               |           +---+            |
              +---------------|-----------|RT6|------------|
                              |           +---+            |
                              +                            +

                  Figure 1: Initial MOSPF test setup






Moy                                                             [Page 7]

RFC 1585             MOSPF: Analysis and Experience           March 1994


   Due to the commercial tunneling applications developed by Proteon
   that use IP multicast, MOSPF has been deployed in a number of
   operational but non-Internet-connected sites.  MOSPF has been also
   deployed in some Internet-connected sites (e.g., OARnet) for testing
   purposes. The desire of these sites is to use MOSPF to attach to the
   "mbone".  However, an implementation of both MOSPF and DVMRP in the
   same box is needed; without this one way communication has been
   achieved (sort of like lecture mode in vat) by configuring multicast
   static routes in the MOSPF implementation. The problem is that there
   is no current way to inject the MOSPF source information into DVMRP.

   The MOSPF features that have not yet been tested are:

   o   The interaction between MOSPF and virtual links.

   o   Interaction between MOSPF and other multicast routing protocols
       (e.g., DVMRP).

   o   TOS-based routing in MOSPF.

6.  A brief analysis of MOSPF scaling

   MOSPF uses the Dijkstra algorithm to calculate the path of a
   multicast datagram through any given OSPF area. This calculation
   encompasses all the transit nodes (routers and networks) in the area;
   its cost scales as O(N*log(N)) where N is the number of transit nodes
   (same as the cost of the OSPF unicast intra-area routing
   calculation). This is the cost of a single path calculation; however,
   MOSPF calculates a separate path for each [source network, multicast
   destination, TOS] tuple. This is potentially a lot of Dijkstra
   calculations.

   MOSPF proposes to deal with this calculation burden by calculating
   datagram paths in an "on demand" fashion. That is, the path is
   calculated only when receiving the first datagram in a stream.  After
   the calculation, the results are cached for use by later matching
   datagrams. This on demand calculation alleviates the cost of the
   routing calculations in two ways: 1) It spreads the routing
   calculations out over time and 2) the router does fewer calculations,
   since it does not even calculate the paths of datagrams whose path
   will not even touch the router.

   Cache entries need never be timed out, although they are removed on
   topological changes.  If an implementation chooses to limit the
   amount of memory consumed by the cache, probably by removing selected
   entries, care must be taken to ensure that cache thrashing does not
   occur.




Moy                                                             [Page 8]

RFC 1585             MOSPF: Analysis and Experience           March 1994


   The effectiveness of this "on demand" calculation will need to be
   proven over time, as multicast usage and traffic patterns become more
   evident.

   As a simple example, suppose an OSPF area consists of 200 routers.
   Suppose each router represents a site, and each site is participating
   simultaneously with three other local sites (inside the area) in a
   video conference. This gives 200/4 = 50 groups, and 200 separate
   datagram trees. Assuming each datagram tree goes through every router
   (which probably won't be true), each router will be doing 200
   Dijkstras initially (and on internal topology changes). The time to
   run a 200 node Dijkstra on a 10 mips processor was estimated to be 15
   milliseconds in "OSPF protocol analysis" ([RFC 1245]). So if all 200
   Dijkstras need to be done at once, it will take 3 seconds total on a
   10 mips processor. In contrast, assuming each video stream is
   64Kb/sec, the routers will constantly forward 12Mb/sec of application
   data (the cost of this soon dwarfing the cost of the Dijkstras).

   In this example there are also 200 group-membership-LSAs in the area;
   since each group membership-LSA is around 64 bytes, this adds 64*200
   = 12K bytes to the OSPF link state database.

   Other things to keep in mind when evaluating the cost of MOSPF's
   routing calculation are:

   o Assuming that the guidelines of "OSPF protocol analysis" ([RFC
     1245]) are followed and areas are limited to 200 nodes, the cost
     of the Dijkstra will not grow unbounded, but will instead be
     capped at the Dijkstra for 200 nodes.  One need then worry about
     the number of Dijkstras, which is determined by the number of
     [datagram source, multicast destination] combinations.

   o A datagram whose destination has no group members in the domain
     can still be forwarded through the MOSPF system. However, the
     Dijkstra calculation here depends only on the [datagram source,
     TOS], since the datagram will be forwarded along to "wild-card
     receivers" only. Since the number of group members in a 200
     router area is probably also bounded, the possibility of
     unbounded calculation growth lies in the number of possible
     datagram sources. (However, it should be noted that some future
     multicast applications, such as distributed computing, may generate
     a large number of short-lived multicast groups).

   o By collapsing routing information before importing it into the
     area/AS, the number of sources can be reduced dramatically. In
     particular, if the AS relies on a default external route, most
     external sources will be covered by a single Dijkstra calculation
     (the one using 0.0.0.0 as the source).



Moy                                                             [Page 9]

RFC 1585             MOSPF: Analysis and Experience           March 1994


   One other factor to be considered in MOSPF scaling is how often cache
   entries need to be recalculated, as a result of a network topology
   change. The rules for MOSPF cache maintenance are explained in
   Section 13 of [MOSPF]. Note that the further away the topology change
   happens from the calculating router, the fewer cache entries need to
   be recalculated. For example, if an external route changes, many
   fewer cache entries need to be purged as compared to a change in a
   MOSPF domain's internal link. For scaling purposes, this is exactly
   the desired behavior. Note that "OSPF protocol analysis" ([RFC 1245])
   bears this out when it shows that changes in external routes (on the
   order of once a minute for the networks surveyed) are much more
   frequent than internal changes (between 15 and 50 minutes for the
   networks surveyed).

7.  Known difficulties

   The following are known difficulties with the MOSPF protocol:

   o When a MOSPF router itself contains multicast applications, the
     choice of its application datagrams' source addresses should be
     made with care.  Due to OSPF's representation of serial lines,
     using a serial line interface address as source can lead to
     excess data traffic on the serial line.  In fact, using any
     interface address as source can lead to excess traffic, owing to
     MOSPF's decision to always multicast the packet onto the source
     network as part of the forwarding process (see Section 11.3 of
     [MOSPF]). However, optimal behavior can be achieved by assigning
     the router an interface-independent address, and using this as
     the datagram source.

     This concern does not apply to regular IP hosts (i.e., those
     that are not MOSPF routers).

   o It is necessary to ensure, when mixing MOSPF and non-multicast
     routers on a LAN, that a MOSPF router becomes Designated Router.
     Otherwise multicast datagrams will not be forwarded on the LAN,
     nor will group membership be monitored on the LAN, nor will the
     group-membership-LSAs be flooded over the LAN. This can be an
     operational nuisance, since OSPF's Designated Router election
     algorithm is designed to discourage Designated Router transitions,
     rather than to guarantee that certain routers become
     Designated Router. However, assigning a DR Priority of 0 to all
     non-multicast routers will always guarantee that a MOSPF router
     is selected as Designated Router.







Moy                                                            [Page 10]

RFC 1585             MOSPF: Analysis and Experience           March 1994


8.  Future work

   In the future, it is expected that the following work will be done on
   the MOSPF protocol:

   o More analysis of multicast traffic patterns needs to be done, in
     order to see whether the MOSPF routing calculations will pose an
     undue processing burden on multicast routers.  If necessary,
     further ways to ease this burden may need to be defined. One
     suggestion that has been made is to revert to reverse path
     forwarding when the router is unable to calculate the detailed
     MOSPF forwarding cache entries.

   o Experience needs to be gained with the interactions between multiple
     multicast routing algorithms (e.g., MOSPF and DVMRP).

   o Additional MIB support for the retrieval of forwarding cache
     entries, along the lines of the "IP forwarding table MIB" ([RFC
     1354]), would be useful.
































Moy                                                            [Page 11]

RFC 1585             MOSPF: Analysis and Experience           March 1994


9.  References

    [Bharath-Kumar] Bharath-Kumar, K., and J. Jaffe, "Routing to
                    multiple destinations in Computer Networks", IEEE
                    Transactions on Communications, COM-31[3], March
                    1983.

    [Deering]       Deering, S., "Multicast Routing in Internetworks
                    and Extended LANs", SIGCOMM Summer 1988
                    Proceedings, August 1988.

    [Deering2]      Deering, S., "Multicast Routing in a Datagram
                    Internetwork", Stanford Technical Report
                    STAN-CS-92-1415, Department of Computer Science,
                    Stanford University, December 1991.

    [OSPF]          Moy, J., "OSPF Version 2", RFC 1583, Proteon,
                    Inc., March 1994.

    [OSPF MIB]      Baker F., and R. Coltun, "OSPF Version 2 Management
                    Information Base", RFC 1253, ACC, Computer Science
                    Center, August 1991.

    [MOSPF]         Moy, J., "Multicast Extensions to OSPF", RFC 1584,
                    Proteon, Inc., March 1994.

    [RFC 1075]      Waitzman, D., Partridge, C. and S. Deering,
                    "Distance Vector Multicast Routing Protocol", RFC
                    1075, BBN STC, Stanford University, November 1988.

    [RFC 1112]      Deering, S., "Host Extensions for IP Multicasting",
                    Stanford University, RFC 1112, May 1988.

    [RFC 1209]      Piscitello, D., and J. Lawrence, "Transmission of IP
                    Datagrams over the SMDS Service", RFC 1209, Bell
                    Communications Research, March 1991.

    [RFC 1245]      Moy, J., Editor, "OSPF Protocol Analysis", RFC
                    1245, Proteon, Inc., July 1991.

    [RFC 1246]      Moy, J., Editor, "Experience with the OSPF
                    Protocol", RFC 1245, Proteon, Inc., July 1991.

    [RFC 1264]      Hinden, R., "Internet Routing Protocol
                    Standardization Criteria", RFC 1264, BBN, October
                    1991.





Moy                                                            [Page 12]

RFC 1585             MOSPF: Analysis and Experience           March 1994


    [RFC 1390]      Katz, D., "Transmission of IP and ARP over FDDI
                    Networks", RFC 1390, cisco Systems, Inc., January
                    1993.

    [RFC 1354]      Baker, F., "IP Forwarding Table MIB", RFC 1354,
                    ACC, July 1992.

Security Considerations

   Security issues are not discussed in this memo, tho see Section 2.

Author's Address

   John Moy
   Proteon, Inc.
   9 Technology Drive
   Westborough, MA 01581

   Phone: [phone]
   EMail: [e-mail]































Moy                                                            [Page 13]