diff options
Diffstat (limited to 'doc/rfc/rfc1585.txt')
-rw-r--r-- | doc/rfc/rfc1585.txt | 731 |
1 files changed, 731 insertions, 0 deletions
diff --git a/doc/rfc/rfc1585.txt b/doc/rfc/rfc1585.txt new file mode 100644 index 0000000..5a251e1 --- /dev/null +++ b/doc/rfc/rfc1585.txt @@ -0,0 +1,731 @@ + + + + + + +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 mospf@gated.cornell.edu. + +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| + | +---+ + | +---------+ | + | | | + | +---+ +---+ +---+ | + | |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: (508) 898-2800 + EMail: jmoy@proteon.com + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +Moy [Page 13] + |