Merit Network
Can't find what you're looking for? Search the Mail Archives.
  About Merit   Services   Network   Resources & Support   Network Research   News   Events   Home

Discussion Communities: Merit Network Email List Archives

North American Network Operators Group

Date Prev | Date Next | Date Index | Thread Index | Author Index | Historical

Some Issues for an Inter-domain Multicast Routing Protocol

  • From: David M. Meyer
  • Date: Wed Feb 12 18:14:11 1997



	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]


- - - - - - - - - - - - - - - - -




Discussion Communities


About Merit | Services | Network | Resources & Support | Network Research
News | Events | Contact | Site Map | Merit Network Home


Merit Network, Inc.