All, I've posted to draft below to the MBONE Deployment Working Group. Is summarizes some of my thoughts on the problems with current approaches to inter-domain multicast routing. My hope is that this document will stimulate some discussion and thought about multicast routing from the service provider perspective. As usual, any comments would be greatly appreciated. Thanks, Dave ------- MBONE Deployment Working Group David Meyer Internet Draft University of Oregon Expiration Date: August 1997 February 1997 Some Issues for an Inter-domain Multicast Routing Protocol draft-ietf-mboned-imrp-some-issues-00.txt 1. Status Of This Memo This document is an Internet-Draft. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet-Drafts. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as ``work in progress.'' To learn the current status of any Internet-Draft, please check the ``1id-abstracts.txt'' listing contained in the Internet-Drafts Shadow Directories on ftp.is.co.za (Africa), nic.nordu.net (Europe), munnari.oz.au (Pacific Rim), ds.internic.net (US East Coast), or ftp.isi.edu (US West Coast). 2. Introduction The IETF's Inter-Domain Multicast Routing (IDMR) working group has produced several multicast routing protocols, including Core Based Trees [CBT] and Protocol Independent Multicasting [PIMARCH]. In addition, the IDMR WG has formalized the specification of the Distance Vector Multicast Routing Protocol [DVMRP]. Various specifications for protocol inter-operation have also been produced (see, for example, [THALER96] and [PIMMBR]). However, none of these protocols seems ideally suited to the inter-domain routing case; that is, while these protocols are appropriate for the intra-domain routing environment, they break down in various ways when applied in to the multi-provider inter-domain case. This document considers some of the scaling, stability and policy issues that are of primary importance in a inter-domain, multi- David Meyer FORMFEED[Page 1] Internet Draft draft-ietf-mboned-imrp-some-issues-00.txt February 1997 provider multicast environment. 3. Forwarding State Requirements Any scalable protocol will have to minimize forwarding state requirements. In the case of dense mode protocols [DVMRP][PIM-DM], routers may carry forwarding or prune state for every (S,G) pair in the Internet. This is true even for routers that may not be on any delivery tree. It seems likely that as multicast deployment scales to the size of the Internet, maintenance of (S,G) state will become intractable. Shared tree protocols, on the other hand, have the advantage of maintaining a single (*,G) entry for a group's receivers (thus relaxing the requirement of maintaining (S,G) for the entire Internet). However, this is not without its own disadvantages; see the section on "Third-party Resource Dependencies" below. 4. Forwarding State Distribution The objective of a multicast forwarding state distribution mechanism is to ensure that multicast traffic is efficiently distributed to those parts of the topology where there are receivers. Dense and sparse mode protocols will accept differing overheads based on design tradeoffs. In the dense mode case, the data-driven nature state distribution has disadvantage that data is periodically distributed to branches of the distribution tree which don't have receivers ("Flood and Prune" behavior). It seems unlikely that this mechanism will be scalable to Internet-wide case. On the other hand, sparse mode protocols use receiver-initiated, explicit joins to establish a forwarding path along a shared distribution tree. While the on-demand nature of sparse mode protocols have favorable properties with respect to distribution of forwarding state, it also has the possible disadvantage of creating dependencies on shared resources (again, see the section on "Third- Party Resource Dependencies" below). David Meyer FORMFEED[Page 2] Internet Draft draft-ietf-mboned-imrp-some-issues-00.txt February 1997 5. Forwarding State Maintenance The many current multicast protocols attempt to accurately and rapidly maintain distribution trees that are as close to optimal as possible. This means that the shape of a distribution tree can be rapidly changing. In addition, since distribution trees can be global, they can be subject to high frequency control traffic. In contrast, the focus in the inter-domain unicast routing environment is on minimizing routing traffic (see, for example, [VILLAM95]), and controlling stability [LABOV97]. The implication is that protocol overhead and stability must be controlled if we hope multicast to scale to Internet sizes. Thus it seems likely that Inter-domain multicast routing protocols will have to do less forwarding state maintenance, and hence be less aggressive in reshaping distribution trees. Note that this reshaping is related to what has been termed "routing flux" (again, see [LABOV97]), since the routing traffic does not directly affect path selection. Rather, the primary effect is to require significant processing resources in a border router. Finally, note that unlike the unicast case, we do not have good data characterizing this effect for multicast routers. 5.1. Bursty Source Problem The "Bursty Source Problem" can be described as those cases in which sources loose data because there is very long join latency and/or initial send latency. The current set of multicast routing protocols attempt, where possible, to avoid this problem (i.e., maximize response to bursty sources). Further, the combination of long latencies with flooding joins can become a problem where a large number of groups are joined and left at high frequency. 6. Mixed Control Mixing control of topology discovery and distribution tree construction can lead to efficiencies but also imposes various constraints on topology discovery mechanisms. For example, DVMRP [DVMRP] uses topology discovery facilities ("split horizon with poison reverse") to eliminate duplicate packets on a LAN, and to detect non-leaf networks (an upstream router uses this information when pruning downstream interfaces). On the other hand, PIM [PIM-DM] does not use any topology discovery algorithm features when building delivery trees. However, this independence is not without cost: PIM-DM accepts some duplicates on multi-access LANs as a tradeoff for reduced protocol complexity. David Meyer FORMFEED[Page 3] Internet Draft draft-ietf-mboned-imrp-some-issues-00.txt February 1997 7. Neighbor Model The current inter-domain unicast routing model has some key differences with proposed inter-domain multicast routing models with respect to neighbor (peer) discovery. In particular, the current set of multicast protocols depend heavily on dynamic neighbor discovery. This is analogous to the situation with intra-domain unicast routing, but is unlike current inter-domain unicast routing, where neighbors are typically statically configured. The static neighbor configuration model has several benefits for inter-domain routing. First, neighbors are predefined, which is a policy requirement in most cases. In addition, the set of peers in the inter-domain unicast routing system defines the set of possible inter-domain topologies (with the current active topology represented by the collection of AS paths). Another important difference relates to how inter-domain regions are modeled. For purposes of this document, consider an inter-domain region defined to be a part of an arbitrary topology in which a higher level (inter-domain) routing protocol is used to calculate paths between regions. In addition, each pair of adjacent regions is connected by one or more multicast border routers. Current IDMR proposals (e.g., [HDVMRP], [THALER96]) model an inter-domain region as a routing domain. That is, border routers internetwork between one or more intra-domain regions and an inter-domain region (again, possibly more than one). In this model, inter-networking occurs "inside" router. However, the inter-provider unicast routing model in use today is quite different. In particular, the "peering" between two providers occurs in neither of the provider's routing domains, nor does it occur in some shared "inter-domain" routing domain. The separation provides the administrative and policy control that is required in today's Internet. 8. Unicast Topology Dependency Ideally, unicast and multicast topologies are congruent in the Internet. However, since it is frequently difficult to field new facilities (such as IP multicast) in the "core" the Internet infrastructure, there will continue to be many cases in which unicast and multicast topologies are not congruent (either because a region is not multicast capable at all, or because the region is not natively forwarding multicast traffic). Thus, it is unlikely that the entire IPv4 Internet will be able to carry native multicast traffic in the foreseeable future. In addition, various policy requirements will in certain cases cause to topologies to further diverge. The David Meyer FORMFEED[Page 4] Internet Draft draft-ietf-mboned-imrp-some-issues-00.txt February 1997 implication is that a successful IDMR will need a topology discover mechanism, or have other mechanisms for dealing with those cases in which unicast and multicast topologies are not congruent. 9. Third-Party Resource Dependencies Shared tree protocols require one or more globally shared Rendezvous Points (RPs) [PIM-SM] or Cores [CBT]. The RP or Core effectively serves as the root of a group specific shared tree. Data is sent to the RP/Core for delivery on the shared tree. This means that some groups may have an RP (or core) that is fielded by a third party. For example, if providers A, B and C share a PIM-SM inter-domain region, then there will exist an RP that is mapped to C's multicast border router. In this case, C is hosting a kind of "transit RP" for A and B (A and B register to C to communicate between themselves, even if C has no receivers for the group(s) served by the RP. 10. Traffic Concentration Problem Traffic can be "concentrated" on a shared tree. This can lead to increased latency or packet loss. However, this is less of a problem in the shared-media exchange point environment. 11. Distant RP/Core Problem In the shared tree model, if the RP or Core is distant (topologically), then joins will travel to the distant RP/Core, even if the data is being delivered locally. Note that this problem is exacerbated by the global nature of the RP/Core space; if a router is registering to a RP/Core that is not in the local domain (say, fielded by the site's direct provider), then the routing domain is flat. David Meyer FORMFEED[Page 5] Internet Draft draft-ietf-mboned-imrp-some-issues-00.txt February 1997 12. Multicast Internal Gateway Protocol (MIGP) Independence A shared tree, explicit join protocol inter-domain routing protocol may require modification to a leaf domain's internal multicast routing mechanism. The problem arises when a domain is running a "flood and prune" protocol such as DVMRP or PIM-DM internally while participating in a shared tree inter-domain protocol. In this case, those areas of the (internal) topology where there are no sources will not receive inter-domain traffic. It has been suggested that these protocols be modified to use Domain Wide Reports [HDVMRP] to communication domain-wide group membership to a domain's border routers. 13. Encapsulations An IDMRP should minimize encapsulations where ever possible. PIM-SM encapsulates packets sent to the shared tree in PIM Register messages (data can be delivered natively if the last hop router or the RP switches to the shortest path tree). HDVMRP requires every inter- domain packet to be rewritten with an additional level of encapsulation for inter-domain forwarding. Further, the number of encapsulations/decapsulations for paths that traverse N administrative domains is O(N); each border border router "registers" to a group specific RP, which then decapsulates the packet for distribution on the shared tree. 14. Policy Provisions Current inter-domain unicast routing protocols have a rich and well developed policy model. In contrast, multicast routing protocols have little or no provision for implementing routing policy (administrative scoping is one major exception). A concrete example of this need is the various problems with inadvertent injection of unicast routing tables into the MBONE, coupled with our inability to propagate the resultant large DVMRP routing tables, point out the need for such policy oriented controls. A simple example illustrates why a successful inter-domain multicast routing protocol will need to have a well developed policy model: Consider three providers, A, B, and C, that have connections to a shared-media exchange point. Assume that connectivity is non- transitive due to some policy (the common case, since bi-lateral agreements are a very common form of peering agreement). That is, A and B are peers, B and C are peers, but A and C are not peers. Now, consider a source prefix P, where P belongs to a customer of A (i.e., David Meyer FORMFEED[Page 6] Internet Draft draft-ietf-mboned-imrp-some-issues-00.txt February 1997 P is advertised by A). Now, multicast packets forwarded by A's border router will be correctly accepted by B, since B sees the RPF interface for P to be the shared-media of the exchange. Likewise, C's border router will reject the packets forwarded by A's border router because, by definition, C does not have A's routes through its interface on the exchange (so packets sourced "inside" A fail the RPF check in C's border router). In the example above, RPF is a powerful enough mechanism to inform C that it should not accept packets sourced in P from A over the exchange. However, consider the common case in which P is multi- homed to both A and B. C now sees a route for P from B though its interface on the exchange. Without some form of multi-provider cooperation and/or packet filtering, C could accept multicast packets from A across the exchange, even though A and C don't peer. Clearly, this is an unintended consequence. In addition, note that RPF itself is essentially a packet filtering technology, and as such has qualitatively different resource requirements than the route filters that are commonly deployed in border routers. 14.1. Today's MBONE Another way to view the policy issues described above is to consider the perspective of unicast reachability. Today's MBONE is comprised of a single flat AS. Further, this AS running a simple distance vector topology discovery protocol. This arrangement is unlikely to scale gracefully or provide the same rich policy control that we find in the unicast Internet. There are additional problems with a flat AS model: the flat AS model fits neither the operational or organizational models commonly found in Internet today. 15. Equal Cost Multipath A common way to incrementally scale available bandwidth is to provide parallel equal cost paths. It would be an advantage if a multicast routing protocol could support this. However, this would seem difficult to achieve when using Reverse Path Forwarding, so it is unclear whether this goal is achievable. David Meyer FORMFEED[Page 7] Internet Draft draft-ietf-mboned-imrp-some-issues-00.txt February 1997 16. Conclusion Deployment of a general purpose IP multicast infrastructure for the Internet has been slowed by various factors. One of the primary reasons, however, is the lack of a true inter-domain Multicast Routing Protocol. Several proposals have been advanced to solve this problem, including PIM-SM [PIM-SM], DVMRP [PIMMBR], and Hierarchical DVMRP [HDVMRP]. However, the concerns outlined above have prevented any of these protocols from being adopted as the standard inter- domain multicast routing protocol. Finally, it is worth noting that DVMRP, since it is the common denominator among router vendor offerings, is currently the de-facto inter-domain routing protocol. 17. Security Considerations Security considerations are not discussed in this memo. 18. References [CBT] A. Ballardie, et. al., "Core Based Trees (CBT) Multicast -- Protocol Specification --", draft-ietf-idmr-cbt-spec-06.txt, September, 1996. [DVMRP] T. Pusateri, "Distance Vector Multicast Routing Protocol", draft-ietf-idmr-dvmrp-v3-03, September, 1996. [HDVMRP] Ajit S.. Thyagarajan and Steve Deering, " Hierarchical Distance-Vector Multicast Routing for the MBone", In Proceedings of the ACM SIGCOMM, pages 60-66, October, 1995. [LABOV97] Labovitz, Craig, et. al., "Internet Routing Instability", Submitted to SIGCOMM97. [PIMARCH] Estrin, D, et. al., "Protocol Independent Multicast Sparse Mode (PIM-SM): Motivation and Architecture", draft-ietf-idmr-pim-arch-04.ps , October, 1996. [PIM-DM] Estrin, D, et. al., "Protocol Independent Multicast Dense Mode (PIM-DM): Protocol Specification", draft-ietf-idmr-PIM-DM-spec-04.ps, September, 1996. [PIMMBR] Estrin, D, et. al., "PIM Multicast Border Router (PMBR) specification for connecting PIM-SM domains to a DVMRP Backbone", draft-ietf-idmr-PIMBR-spec-01.ps, David Meyer FORMFEED[Page 8] Internet Draft draft-ietf-mboned-imrp-some-issues-00.txt February 1997 September, 1996. [PIM-SM] Estrin, D, et. al., "Protocol Independent Multicast Sparse Mode (PIM-SM): Protocol Specification", draft-ietf-idmr-PIM-SM-spec-09.ps, October, 1996. [THALER96] D. Thaler, "Interoperability Rules for Multicast Routing Protocols", draft-thaler-interop-00.ps, November, 1996. [VILLAM95] C Villamizar, Ravi Chandra, and Ramesh Govindan, "Controlling BGP/IDRP Routing Overhead", draft-ietf-idr-rout-dampen-00.ps, July, 1995. 19. Acknowledgments Dino Farinacci and Dave Thaler provided several insightful comments on earlier drafts of this document. 20. Author Information David Meyer University of Oregon 1225 Kincaid St. Eugene, OR 97403 Phone: (541) 346-1747 e-mail: meyer@antc.uoregon.edu David Meyer FORMFEED[Page 9]