- Test - lists.nanog.org

Some Issues for an Inter-domain Multicast Routing Protocol
by David M. Meyer 12 Feb '97

12 Feb '97

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(a)antc.uoregon.edu David Meyer FORMFEED[Page 9]

1 0

A note to the Spam Chasers
by ALAN DORN HETZEL JR 12 Feb '97

12 Feb '97

An open later to all Spam Chasers: Please take care that you don't harm innocent bystanders. There are some real impolite folks running softcell.NET , and they really seem to deserve a blackhole. I have a poor, unlucky customer who inhabits softcell.COM . They are not in ANY WAY related to softcell.NET , but they, and we with them, keep getting blasted by people mad at softcell.NET. As an operational note, if you are trying to deal with SPAM from softcell.NET, please don't nuke softcell.COM, atlanta.com, atlanta.net, or ME in the process. Thanks! Dorn Hetzel

1 0

155.229.2.2 problem
by dorn＠atl.eni.net 12 Feb '97

12 Feb '97

Bill, It appears that 155.229.2.2 (postal.atlanta.net) may be blackholed. We were getting used to relay spam until a couple weeks ago when we worked in some sendmail filters to block use as a relay... -Dorn 32% traceroute 155.229.2.2 traceroute to 155.229.2.2 (155.229.2.2), 30 hops max, 40 byte packets 1 cisco5-160 (128.9.160.5) 1.655 ms 1.577 ms 1.511 ms 2 ln-gw32 (128.9.32.1) 2.283 ms 1.669 ms 1.558 ms 3 f1.border1.lax1.genuity.net (198.32.146.18) 3.674 ms 3.695 ms 3.444 ms 4 core1.sjc1.genuity.net (207.240.0.9) 15.563 ms 16.552 ms 15.574 ms 5 f12.border1.sjc1.genuity.net (207.240.1.34) 15.412 ms 15.767 ms 15.624 ms 6 207.240.24.62 (207.240.24.62) 15.962 ms 16.109 ms 19.516 ms 7 * * * 8 * * 207.240.24.62 (207.240.24.62) 17.361 ms !H 9 * * * 10 * 207.240.24.62 (207.240.24.62) 17.361 ms !H * 11 * * 207.240.24.62 (207.240.24.62) 18.26 ms !H 12 * * * 13 * * * 14 * 207.240.24.62 (207.240.24.62) 17.682 ms !H * 15 207.240.24.62 (207.240.24.62) 16.796 ms !H * * 16 * * * 17 * * * 18 * * * 19 * * * 20 * * * 21 * * * 22 * * * 23 * * * 24 * * * 25 207.240.24.62 (207.240.24.62) 18.063 ms !H * * 26 207.240.24.62 (207.240.24.62) 31.012 ms !H * 16.813 ms !H 33% -- --bill -----End of forwarded message-----

3 3

New Peering Point - Atlanta Internet eXchange (AIX)
by dorn＠atl.eni.net 12 Feb '97

12 Feb '97

Bay Networks, Epoch Networks, Siemens Business Services, and GridNet are sponsoring a new exchange point in Atlanta. For details, see: <A HREF="http://www.com/aix"> http://www.com/aix </A> Dorn Hetzel Epoch Networks

2 1

Re: RFC1918 conformance
by Brett D. Watson 10 Feb '97

10 Feb '97

> As specified in RFC1918 (ftp://ds.internic.net/rfc/rfc1918.txt) the > netblocks 10.0.0.0/16, 172.16.0.0/12 and 192.168.0.0/16 have been > allocated for "Private Internets". Consequently, these netblocks > should not be routed over the Internet. > > As shown below, they are currently advertised from AS6848 and these > advertisements are carried to us (AS6453) through various AS's of the > SprintLink system. while what you say is absolutely true (people shouldn't adversite them) i would say that it's as much your responsibility to block them at your edge routers. -brett > >sh ip bgp reg _6846$ > BGP table version is 9335417, local router ID is 207.45.201.5 > Status codes: s suppressed, d damped, h history, * valid, > best, i - > internal > Origin codes: i - IGP, e - EGP, ? - incomplete > > Network Next Hop Metric LocPrf Weight Path > *> 10.0.0.0 144.228.164.57 0 90 0 1794 1239 1790 6846 ? > *> 172.16.0.0/12 144.228.164.57 0 90 0 1794 1239 1790 6846 ? > *> 192.168.0.0/16 144.228.164.57 0 90 0 1794 1239 1790 6846 ? > [...] > > AS6846 responsibles should take immediate action to remove these > announcements. SprintLink, as any conscientious operator, should take > action to filter out these announcements from any of its peers. > > Regards. > __ > > Pierre Thibaudeau | e-mail: <prt(a)Teleglobe.CA> > TELEGLOBE CANADA | > 1000, rue de La Gauchetiere ouest | Tel: +1-514-868-7257 > Montreal, QC H3B 4X5 | > Canada | fax: +1-514-868-8446 > > > > > -brett

2 1

RE: Routing Loops
by Vernon Walker 10 Feb '97

10 Feb '97

Here is an example a Customer sent me. Sorry for the poor formating... trying to get from www.hyperchat.com to one of our dial up sites in Jacksonville, FL. Sat Feb 08 19:19:06 bd3u * seph said to Minnie: hi!.. *smile*.. it doesnt appear he is being blocked.. but..there does appear to be a routing problem preventing him from getting here... Below is a trace which shows the problem. He needs to send this trace to his provider...and ask them to followup and ask ANS to fix the problem... okay? Thanks...Seph Tracing route to d00016.jax.bellsouth.net [207.53.14.17] over a maximum of 30 hops: 1 10 ms 10 ms 10 ms usa-cisco.hyperchat.net[165.212.218.8] 2 10 ms 10 ms 10 ms 165.212.231.1 3 181 ms 120 ms 110 ms 192.156.196.252 4 100 ms 100 ms 121 ms 192.103.71.33 5 30 ms 50 ms 40 ms 140.222.96.221 6 60 ms 71 ms 50 ms h12.t8-0.San-Francisco.t3.ans.net[140.223.9.17] 7 * 90 ms 110 ms h13.t16-0.Los-Angeles.t3.ans.net[140.223.9.14] 8 80 ms 60 ms 50 ms h12.t8-0.San-Francisco.t3.ans.net[140.223.9.17] 9 101 ms 90 ms 80 ms h13.t16-0.Los-Angeles.t3.ans.net[140.223.9.14] 10 70 ms 90 ms 91 ms h12.t8-0.San-Francisco.t3.ans.net[140.223.9.17] 11 110 ms 160 ms 120 ms h13.t16-0.Los-Angeles.t3.ans.net[140.223.9.14] 12 120 ms 110 ms 100 ms h12.t8-0.San-Francisco.t3.ans.net[140.223.9.17] 13 140 ms 130 ms 120 ms h13.t16-0.Los-Angeles.t3.ans.net[140.223.9.14] 14 171 ms 180 ms 150 ms h12.t8-0.San-Francisco.t3.ans.net[140.223.9.17] 15 131 ms 150 ms 110 ms h13.t16-0.Los-Angeles.t3.ans.net[140.223.9.14] 16 120 ms 111 ms 130 ms h12.t8-0.San-Francisco.t3.ans.net[140.223.9.17] 17 180 ms 130 ms 131 ms h13.t16-0.Los-Angeles.t3.ans.net[140.223.9.14] 18 130 ms 120 ms 120 ms

3 2

Re: Routing Loops
by Michael Ramsey 10 Feb '97

10 Feb '97

>You missed a "u" - nitrous.digex.net. > >:) DOH!!! sorry about that. I hate being on the road and having to use this damn tiny keyboard. The proper URL is http://nitrous.digex.net

1 0

Re: Anything happening on Sunday
by Paul Ferguson 10 Feb '97

10 Feb '97

Yep, I'm sure there will be a Bar BoF after the BGP tutorial. :-0 - paul At 04:25 PM 2/9/97 -0600, Bob Collie wrote: >On Sun, 9 Feb 1997, Dorn Hetzel wrote: >> >>For those of us who are here a bit early, is anything happening in >>or around the Hyatt on Sunday? >> > >I think that there are NetSCARF and BGP tutorials/meetings later >this evening, and someone (I think Dillon) mentioned that the >ISP/C group was thinking about doing something afterwards. >But, beyond that, I've heard nothing. > >-Bob > > >-- >Bob Collie, Chief Technical Officer, Telalink Corporation >mailto:rmc@telalink.net >

1 0

Re: Anything happening on Sunday
by Paul Ferguson 10 Feb '97

10 Feb '97

Looks like CAIS has a reception on in the Bay View at 17:30. :-) - paul At 03:02 PM 2/9/97 -0500, Dorn Hetzel wrote: > >For those of us who are here a bit early, is anything happening in >or around the Hyatt on Sunday? > >Dorn Hetzel >Epoch Networks > > >Attachment Converted: "C:\DATA\EMAIL\ATTACH~1\Anything happening on Sunday" >

1 0

Routing Loops
by Vernon Walker 09 Feb '97

09 Feb '97

Maybe it's just me, but there seems to have been an increase in routing loops lately. Anyone else seen an increase or am I just paranoid?? Worried for no reason??? Vernon Walker Director - Network Operations Center BellSouth.net walkerv(a)bellsouth.net

2 1