rfc1585.txt

<VC++网络游戏建摸与实现>源代码

Network Working Group                                             J. Moy
Request for Comments: 1585                                 Proteon, Inc.
Category: Informational                                       March 1994


                     MOSPF: Analysis and Experience

Status of this Memo

   This memo provides information for the Internet community.  This memo
   does not specify an Internet standard of any kind.  Distribution of
   this memo is unlimited.

Abstract

   This memo documents how the MOSPF protocol satisfies the requirements
   imposed on Internet routing protocols by "Internet Engineering Task
   Force internet routing protocol standardization criteria" ([RFC
   1264]).

   Please send comments to [e-mail].

1.  Summary of MOSPF features and algorithms

   MOSPF is an enhancement of OSPF V2, enabling the routing of IP
   multicast datagrams.  OSPF is a link-state (unicast) routing
   protocol, providing a database describing the Autonomous System's
   topology.  IP multicast is an extension of LAN multicasting to a
   TCP/IP Internet.  IP Multicast permits an IP host to send a single
   datagram (called an IP multicast datagram) that will be delivered to
   multiple destinations.  IP multicast datagrams are identified as
   those packets whose destinations are class D IP addresses (i.e.,
   addresses whose first byte lies in the range 224-239 inclusive).
   Each class D address defines a multicast group.

   The extensions required of an IP host to participate in IP
   multicasting are specified in "Host extensions for IP multicasting"
   ([RFC 1112]).  That document defines a protocol, the Internet Group
   Management Protocol (IGMP), that enables hosts to dynamically join
   and leave multicast groups.

   MOSPF routers use the IGMP protocol to monitor multicast group
   membership on local LANs through the sending of IGMP Host Membership
   Queries and the reception of IGMP Host Membership Reports.  A MOSPF
   router then distributes this group location information throughout
   the routing domain by flooding a new type of OSPF link state
   advertisement, the group-membership-LSA (type 6). This in turn
   enables the MOSPF routers to most efficiently forward a multicast



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


   datagram to its multiple destinations: each router calculates the
   path of the multicast datagram as a shortest-path tree whose root is
   the datagram source, and whose terminal branches are LANs containing
   group members.

   A separate tree is built for each [source network, multicast
   destination] combination.  To ease the computational demand on the
   routers, these trees are built "on demand", i.e., the first time a
   datagram having a particular combination of source network and
   multicast destination is received. The results of these "on demand"
   tree calculations are then cached for later use by subsequent
   matching datagrams.

   MOSPF is meant to be used internal to a single Autonomous System.
   When supporting IP multicast over the entire Internet, MOSPF would
   have to be used in concert with an inter-AS multicast routing
   protocol (something like DVMRP would work).

   The MOSPF protocol is based on the work of Steve Deering in
   [Deering].  The MOSPF specification is documented in [MOSPF].

1.1.  Characteristics of the multicast datagram's path

   As a multicast datagram is forwarded along its shortest-path tree,
   the datagram is delivered to each member of the destination multicast
   group. In MOSPF, the forwarding of the multicast datagram has the
   following properties:

      o The path taken by a multicast datagram depends both on the
        datagram's source and its multicast destination. Called
        source/destination routing, this is in contrast to most unicast
        datagram forwarding algorithms (like OSPF) that route
        based solely on destination.

      o The path taken between the datagram's source and any particular
        destination group member is the least cost path available. Cost
        is expressed in terms of the OSPF link-state metric.

      o MOSPF takes advantage of any commonality of least cost paths
        to destination group members. However, when members of the
        multicast group are spread out over multiple networks, the
        multicast datagram must at times be replicated. This replication
        is performed as few times as possible (at the tree branches),
        taking maximum advantage of common path segments.

      o For a given multicast datagram, all routers calculate an
        identical shortest-path tree.  This is possible since the
        shortest-path tree is rooted at the datagram source, instead



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


        of being rooted at the calculating router (as is done in the
        unicast case). Tie-breakers have been defined to ensure
        that, when several equal-cost paths exist, all routers agree
        on which single path to use. As a result, there is a single
        path between the datagram's source and any particular
        destination group member. This means that, unlike OSPF's
        treatment of regular (unicast) IP data traffic, there is no
        provision for equal-cost multipath.

      o While MOSPF optimizes the path to any given group member, it
        does not necessarily optimize the use of the internetwork as
        a whole. To do so, instead of calculating source-based
        shortest-path trees, something similar to a minimal spanning
        tree (containing only the group members) would need to be
        calculated.  This type of minimal spanning tree is called a
        Steiner tree in the literature.  For a comparison of
        shortest-path tree routing to routing using Steiner trees,
        see [Deering2] and [Bharath-Kumar].

      o When forwarding a multicast datagram, MOSPF conforms to the
        link-layer encapsulation standards for IP multicast
        datagrams as specified in "Host extensions for IP multicasting"
        ([RFC 1112]), "Transmission of IP datagrams over the
        SMDS Service" ([RFC 1209]) and "Transmission of IP and ARP
        over FDDI Networks" ([RFC 1390]). In particular, for ethernet
        and FDDI the explicit mapping between IP multicast
        addresses and data-link multicast addresses is used.

1.2.  Miscellaneous features

   This section lists, in no particular order, the other miscellaneous
   features that the MOSPF protocol supports:

      o MOSPF routers can be mixed within an Autonomous System (and
        even within a single OSPF area) with non-multicast OSPF
        routers. When this is done, all routers will interoperate in
        the routing of unicasts.  Unicast routing will not be
        affected by this mixing; all unicast paths will be the same
        as before the introduction of multicast. This mixing of
        multicast and non-multicast routers enables phased
        introduction of a multicast capability into an internetwork.
        However, it should be noted that some configurations of MOSPF
        and non-MOSPF routers may produce unexpected failures in
        multicast routing (see Section 6.1 of [MOSPF]).

      o MOSPF does not include the ability to tunnel multicast
        datagrams through non-multicast routers. A tunneling capability
        has proved valuable when used by the DVMRP protocol in the



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


        MBONE.  However, it is assumed that, since MOSPF is an intra-AS
        protocol, multicast can be turned on in enough of the Autonomous
        System's routers to achieve the required connectivity without
        resorting to tunneling. The more centralized control that exists
        in most Autonomous Systems, when compared to the Internet as a
        whole, should make this possible.

      o In addition to calculating a separate datagram path for each
        [source network, multicast destination] combination, MOSPF
        can also vary the path based on IP Type of Service (TOS). As
        with OSPF unicast routing, TOS-based multicast routing is
        optional, and routers supporting it can be freely mixed with
        those that don't.

      o MOSPF supports all network types that are supported by the base
        OSPF protocol: broadcast networks, point-to-points networks and
        non-broadcast multi-access (NBMA) networks.  Note however that
        IGMP is not defined on NBMA networks, so while these networks
        can support the forwarding of multicast datagrams, they cannot
        support directly connected group members.

      o MOSPF supports all Autonomous System configurations that are
        supported by the base OSPF protocol. In particular, an algorithm
        for forwarding multicast datagrams between OSPF areas
        is included.  Also, areas with configured virtual links can
        be used for transit multicast traffic.

      o A way of forwarding multicast datagrams across Autonomous
        System boundaries has been defined. This means that a multicast
        datagram having an external source can still be forwarded
        throughout the Autonomous System. Facilities also exist for
        forwarding locally generated datagrams to Autonomous System exit
        points, from which they can be further distributed. The
        effectiveness of this support will depend upon the nature of the
        inter-AS multicast routing protocol.  The one assumption that
        has been made is that the inter-AS multicast routing protocol
        will operate in an reverse path forwarding (RPF) fashion:
        namely, that multicast datagrams originating from an external
        source will enter the Autonomous System at the same place that
        unicast datagrams destined for that source will exit.

      o To deal with the fact that the external unicast and multicast
        topologies will be different for some time to come, a
        way to indicate that a route is available for multicast but
        not unicast (or vice versa) has been defined. This for example
        would allow a MOSPF system to use DVMRP as its inter-AS
        multicast routing protocol, while using BGP as its inter-AS
        unicast routing protocol.



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


      o For those physical networks that have been assigned multiple
        IP network/subnet numbers, multicast routing can be disabled
        on all but one OSPF interface to the physical network.  This
        avoids unwanted replication of multicast datagrams.

      o For those networks residing on Autonomous System boundaries,
        which  may  be  running multiple multicast routing protocols
        (or multiple copies of the same multicast routing protocol),
        MOSPF  can  be configured to encapsulate multicast datagrams
        with unicast (rather than multicast) link-level destinations.
        This also avoids unwanted replication of multicast datagrams.

      o MOSPF provides an optimization for IP multicast's "expanding
        ring search" (sometimes called "TTL scoping") procedure. In
        an expanding ring search, an application finds the nearest
        server by sending out successive multicasts, each with a
        larger TTL. The first responding server will then be the
        closest (in terms of hops, but not necessarily in terms of
        the OSPF metric). MOSPF minimizes the network bandwidth
        consumed by an expanding ring search by refusing to forward
        multicast datagrams whose TTL is too small to ever reach a
        group member.

2.  Security architecture

   All MOSPF protocol packet exchanges (excluding IGMP) are specified by
   the base OSPF protocol, and as such are authenticated. For a
   discussion of OSPF's authentication mechanism, see Appendix D of
   [OSPF].

3.  MIB support

   Management support for MOSPF has been added to the base OSPF V2 MIB
   [OSPF MIB]. These additions consist of the ability to read and write
   the configuration parameters specified in Section B of [MOSPF],
   together with the ability to dump the new group-membership-LSAs.

4.  Implementations

   There is currently one MOSPF implementation, written by Proteon, Inc.
   It was released for general use in April 1992. It is a full MOSPF
   implementation, with the exception of TOS-based multicast routing. It
   also does not contain an inter-AS multicast routing protocol.

   The multicast applications included with the Proteon MOSPF
   implementation include: a multicast pinger, console commands so that
   the router itself can join and leave multicast groups (and so respond
   to multicast pings), and the ability to send SNMP traps to a



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


   multicast address. Proteon is also using IP multicast to support the
   tunneling of other protocols over IP.  For example, source route
   bridging is tunneled over a MOSPF domain, using one IP multicast
   address for explorer frames and mapping the segment/bridge found in a
   specifically-routed frame's RIF field to other IP multicast
   addresses.  This last application has proved popular, since it
   provides a lightweight transport that is resistant to reordering.

   The Proteon MOSPF implementation is currently running in
   approximately a dozen sites, each site consisting of 10-20 routers.

   Table 1 gives a comparison between the code size of Proteon's base
   OSPF implementation and its MOSPF implementation. Two dimensions of

                      lines of C   bytes of 68020 object code
          ___________________________________________________
          OSPF base   11,693       63,160
          MOSPF       15,247       81,956

            Table 1: Comparison of OSPF and MOSPF code sizes

   size are indicated: lines of C (comments and blanks  included),  and
   bytes  of 68020 object code. In both cases, the multicast extensions
   to OSPF have engendered a 30% size increase.

   Note that in these sizes, the code used to configure and monitor the
   implementation has been included. Also, in the MOSPF code size
   figure, the IGMP implementation has been included.

5.  Testing

   Figure 1 shows the topology that was used for the initial debugging
   of Proteon's MOSPF implementation.  It consists of seven MOSPF
   routers, interconnected by ethernets, token rings, FDDIs and serial
   lines. The applications used to test the routing were multicast ping
   and the sending of traps to a multicast address (the box labeled
   "NAZ" was a network analyzer that was occasionally sending IGMP Host
   Membership Reports and then continuously receiving multicast SNMP
   traps). The "vat" application was also used on workstations (without
   running the DVMRP "mrouted" daemon; see "Distance Vector Multicast
   Routing Protocol", [RFC 1075]) which were multicasting packet voice
   across the MOSPF domain.









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


   The MOSPF features tested in this setup were:

   o   Re-routing in response to topology changes.

   o   Path verification after altering costs.

   o   Routing multicast datagrams between areas.

   o   Routing multicast datagrams to and from external addresses.

   o   The various tiebreakers employed when constructing datagram
       shortest-path trees.

   o   MOSPF over non-broadcast multi-access networks.

   o   Interoperability of MOSPF and non-multicast OSPF routers.



                                              +---+
              +-------------------------------|RT1|
              |                               +---+
              |             +---------+         |
              |                  |              |