idnits 2.17.1 draft-zappala-multicast-routing-me-00.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** Cannot find the required boilerplate sections (Copyright, IPR, etc.) in this document. Expected boilerplate is as follows today (2024-04-26) according to https://trustee.ietf.org/license-info : IETF Trust Legal Provisions of 28-dec-2009, Section 6.a: This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79. IETF Trust Legal Provisions of 28-dec-2009, Section 6.b(i), paragraph 2: Copyright (c) 2024 IETF Trust and the persons identified as the document authors. All rights reserved. IETF Trust Legal Provisions of 28-dec-2009, Section 6.b(i), paragraph 3: This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (https://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- ** Missing expiration date. The document expiration date should appear on the first and last page. ** The document seems to lack a 1id_guidelines paragraph about Internet-Drafts being working documents. ** The document seems to lack a 1id_guidelines paragraph about the list of current Internet-Drafts. ** The document seems to lack a 1id_guidelines paragraph about the list of Shadow Directories. == No 'Intended status' indicated for this document; assuming Proposed Standard Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack an IANA Considerations section. (See Section 2.2 of https://www.ietf.org/id-info/checklist for how to handle the case when there are no actions for IANA.) ** The document seems to lack separate sections for Informative/Normative References. All references will be assumed normative when checking for downward references. Miscellaneous warnings: ---------------------------------------------------------------------------- -- The document seems to lack a disclaimer for pre-RFC5378 work, but may have content which was first submitted before 10 November 2008. If you have contacted all the original authors and they are all willing to grant the BCP78 rights to the IETF Trust, then this is fine, and you can ignore this comment. If not, you may need to add the pre-RFC5378 disclaimer. (See the Legal Provisions document at https://trustee.ietf.org/license-info for more information.) -- The document date (March 26, 1997) is 9893 days in the past. Is this intentional? Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) -- Possible downref: Non-RFC (?) normative reference: ref. '1' -- Possible downref: Non-RFC (?) normative reference: ref. '2' -- Possible downref: Non-RFC (?) normative reference: ref. '3' -- Possible downref: Non-RFC (?) normative reference: ref. '4' ** Downref: Normative reference to an Historic RFC: RFC 1584 (ref. '5') ** Downref: Normative reference to an Experimental RFC: RFC 1075 (ref. '6') -- Possible downref: Non-RFC (?) normative reference: ref. '7' -- Possible downref: Non-RFC (?) normative reference: ref. '8' Summary: 9 errors (**), 0 flaws (~~), 1 warning (==), 8 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Internet Draft Daniel Zappala 3 Expiration: September 1997 USC Information Sciences Institute 4 File: draft-zappala-multicast-routing-me-00.txt 6 A Route Setup Mechanism For Multicast Routing 8 March 26, 1997 10 Status of Memo 12 This document is an Internet-Draft. Internet-Drafts are working 13 documents of the Internet Engineering Task Force (IETF), its areas, 14 and its working groups. Note that other groups may also distribute 15 working documents as Internet-Drafts. 17 Internet-Drafts are draft documents valid for a maximum of six months 18 and may be updated, replaced, or obsoleted by other documents at any 19 time. It is inappropriate to use Internet-Drafts as reference 20 material or to cite them other than as "work in progress." 22 To learn the current status of any Internet-Draft, please check the 23 "1id-abstracts.txt" listing contained in the Internet-Drafts Shadow 24 Directories on ds.internic.net (US East Coast), nic.nordu.net 25 (Europe), ftp.isi.edu (US West Coast), or munnari.oz.au (Pacific 26 Rim). 28 Abstract 30 This document describes a multicast route setup protocol that can be 31 used to install alternate paths and pinned routes when they are 32 requested by receivers. We describe the protocol, derive some of its 33 properties, and address its applicability to unicast route setup. 35 1. Introduction 37 This document describes a multicast route setup protocol that can be 38 used to install alternate paths and pinned routes when they are 39 requested by receivers. This protocol is designed as part of the 40 interdomain multicast routing architecture described in [7]. In 41 general, this protocol is useful when multicast routers wish to 42 install explicit routes in a multicast tree without coordinating the 43 routing of the entire tree according to a globally defined metric. 44 Thus, in addition to being used as prescribed in [7], this protocol 45 may also be used to install a QoS route for a receiver. We have 46 focused on designing a multicast route setup protocol; a later 47 section describes the relevance of our work to unicast route setup. 49 For the purposes of this document, we assume that receivers use a 50 reservation protocol such as RSVP [8,2] to reserve resources for 51 unicast and multicast flows. By default, these reservations are 52 obtained over an opportunistic, shortest-path multicast tree computed 53 and installed by a multicast routing protocol, likely either DVMRP 54 [6], MOSPF [5], PIM [4] or CBT [1]. Each sender may have its own 55 tree, or all senders may use a shared tree. Throughout this document 56 we assume sender trees, although the mechanism is equally applicable 57 to shared trees. 59 We also assume that a receiver, or some entity acting on behalf of a 60 receiver, may request several services in place of its current 61 opportunistic route: 63 o "Alternate Path": A route that is an alternative to the 64 currently installed route. A receiver may wish to use an 65 alternate path when it is unable to reserve resources along its 66 current path. 68 o "Pinned Route": A route that remains unchanged unless a node 69 along the route fails. A receiver may wish to know that once it 70 has secured a reservation, the route will not change unless it 71 fails, and hence the reservation will likely remain in place. 72 When an application does not use a pinned route (the route is 73 opportunistic), the reservation protocol must adapt the 74 reservation whenever the route adapts to a shorter path, even if 75 the original path is still working. 77 Using these basic services, a receiver may ask for an alternate path 78 that is opportunistic, an alternate path that is pinned, or it may 79 ask to pin its current route. Note that an opportunistic alternate 80 path has some pinned hops while the remaining hops are opportunistic; 81 see [7] for more details. 83 As part of the architecture described in [7], we assume that a 84 receiver asks its first-hop router for an alternate path or a pinned 85 route. This router in turn contacts a local route construction agent 86 to construct a route and encodes the response as an explicit route. 87 The setup protocol connects the receiver to the multicast tree along 88 this new path. Along the way, the setup protocol pins any hop that 89 is listed in the route; thus if the receiver wants a pinned route, 90 then every hop between the receiver and the sender must be listed. 92 2. The MORF Multicast Route Setup Protocol 94 We have designed the MORF multicast route setup protocol to install 95 routes provided by local route construction agents. For each 96 multicast tree built by the multicast routing protocol, MORF creates 97 its own parallel multicast tree consisting of alternate paths and 98 pinned routes. Each branch of this tree, called the Setup Tree, is 99 constructed using a Setup message originated by a leaf router on 100 behalf of local receivers. The Setup message contains an explicit 101 route indicating the path the Setup should travel (Table 1). As the 102 Setup travels upstream, MORF notifies the multicast routing protocol 103 that it is overriding some local portions of the multicast tree with 104 some branches in the Setup Tree. The multicast routing protocol adds 105 these branches to the multicast tree and prunes any conflicting 106 branches from the original tree (Figure 1a). The resulting multicast 107 tree reflects the path installed by MORF (Figure 1b). The multicast 108 tree may be for a single sender [4], or multiple senders may 109 rendezvous via a core [4,1]. In either case, the protocol is the 110 same; in the following discussion we refer to sender-based trees for 111 simplicity. 113 Table 1: MORF Protocol Messages 115 Messages Parameters 116 ----------------------------------------------------------------- 117 Setup(Group,Target,Route) Group : multicast group 118 Failure(Group,Target,JoinRt,TreeRt) Target : sender or core 119 Teardown(Group,Target) Route : explicit route 120 SetupRt: route from Setup 121 TreeRt : route used by tree 123 [See postscript version for figures] 125 Figure 1: Using a Setup Message to Install a Route 127 Since the Setup Tree overrides default opportunistic routing, each 128 router in the Setup Tree must have a mechanism to detect failures of 129 an alternate path or a pinned route. The setup protocol may rely on 130 a unicast routing protocol to exchange query messages with its 131 neighbors to determine whether they are alive, or it may use its own 132 similar mechanism. Once a failure is detected, MORF sends a Teardown 133 message both upstream and downstream of the failure to remove failed 134 branches from the Setup Tree (Figure 2a). At each hop, MORF notifies 135 the multicast routing protocol of the branches it is removing. The 136 multicast routing protocol re-builds the multicast tree to reflect 137 its metric, often the shortest path to the sender (Figure 2b). 139 [See postscript version for figures] 141 Figure 2: Using a Teardown to Remove a Failed Route 143 The above examples represent the simplified case when a Setup does 144 not conflict with the rest of the Setup Tree. However, the setup 145 protocol must also resolve Setup messages from different leaves that 146 use conflicting routes, because leaf routers may use independent 147 route construction agents. MORF resolves conflicts by choosing the 148 first route that is installed for any given branch of the tree. 149 Where subsequent routes meet this branch, they must conform to the 150 route used from that point upward toward the source. If the setup 151 protocol does not follow this restriction, then a number of looping 152 scenarios may arise; Section 2.1 discusses these cases and the manner 153 in which they are prevented. 155 Figure 3 shows an example of how all Setup messages except the first 156 one must match the route already used by the Setup Tree. When a Setup 157 message adds a node to the Setup Tree, it caches the route it will 158 use to travel from that node upward toward the sender. If a 159 subsequent Setup message arrives at that node, it compares the 160 remaining route it must travel to the route cached locally. If the 161 routes do not match, the node stops processing the Setup and sends a 162 Failure message downstream (Figure 3a). The Failure message contains 163 the route used by the failed Setup and the route used by the tree 164 from the rejecting node upward (Table 1). A router receiving a 165 Failure message merges the two routes it contains to construct a new 166 route that will match the tree, then sends a second Setup with this 167 route (Figure 3b). 169 [See postscript version for figures] 171 Figure 3: Matching Setup Messages 173 It is from this mechanism -- "Match or Fail" -- that MORF derives its 174 name. By using this restriction, MORF may increase the setup 175 latency, but it prevents any loops from forming while the tree is 176 constructed. The remainder of this section discusses potential 177 looping scenarios and analyzes the tradeoffs of MORF versus other 178 potential solutions for preventing loops. 180 2.1 Looping Scenarios 182 When Setup messages are not restricted to matching the rest of the 183 Setup Tree, a number of possible looping scenarios arise. Figure 184 4a shows two Setups, each using a strict explicit route. Based on 185 their order of arrival, as shown, if the Setups merge they form a 186 loop. This loop can be prevented if nodes A and C compare the 187 routes and detect the loop will form. However, when three joins 188 are involved, as in Figure 4b, a single node cannot prevent the 189 loop from forming without having more information available. 191 [See postscript version for figures] 193 Figure 4: Loops Formed by Setup Messages 195 To prevent loops, a node can use one of two strategies: 197 1. Before adding a parent, the node checks all its descendants 198 to be sure the parent is not already a descendant. 200 2. Before adding a child, the node checks all its ancestors to 201 be sure the new child is not already an ancestor. 203 We discuss each of these in turn. Due to the dynamic nature of 204 multicast trees, a node may not know all of its ancestors or 205 descendants. While a node knows the route embedded in the Setup 206 message it has sent upstream, that message may have merged with 207 another Setup carrying a different route. Likewise, other Setups 208 may have merged downstream, adding new descendants. 210 One approach to keep nodes updated concerning upstream and 211 downstream merges is to distribute information after each merge. 212 Following solution (1) above, each Setup that merges can send a 213 Merge message upstream containing its route (Figure 5a). Every 214 node can then know all its descendants and thereby detect any 215 loops. Alternatively, in keeping with solution (2) above, each 216 Setup that merges can send a Merge message downstream containing 217 the upstream portion of the route it merged with (Figure 5b). 218 This allows every node to detect loops by knowing all its 219 ancestors. We denote these two mechanisms as "Merge Up" and 220 "Merge Down", respectively. In both of these approaches, 221 information distributed by the Merge messages may be stale, so 222 loops such as that shown in Figure 4 may still form temporarily 223 before being broken. 225 [See postscript version for figures] 227 Figure 5: Merging Setup Messages Instead of Matching 229 As opposed to these solutions, which in some cases will only 230 detect loops after they have been formed, the strategy we use in 231 MORF prevents any loops from forming. By requiring each Setup to 232 match the upstream route already in place on the tree, MORF in 233 effect enforces solution (2) by requiring that each node know its 234 ancestors before it is added to the tree. Once a node is added to 235 the multicast tree, its ancestors do not change. The cost of this 236 strategy is that each Setup may take an extra roundtrip between 237 itself and the rest of the tree. The following section more 238 completely analyses the tradeoffs of MORF versus the other 239 mechanisms discussed above. 241 2.2 Analysis of Setup Mechanisms 243 Table 2: Comparison of Setup Mechanisms 245 Mechanism Message Storage Setup Loop 246 Name Overhead Overhead Latency Handling 247 ----------------------------------------------------------------- 248 MORF O(1) O(a) 1 or 3 trips Prevent 249 Merge Down O(1) O(a) 1 trip Detect/Break 250 Merge Up O(d) O(d) 1 trip Detect/Break 252 Table 2 compares the setup mechanisms discussed above when 253 building a single multicast tree, assuming there is no packet loss 254 and that one receiver joins the tree at a time. The columns 255 listing message and storage overhead consider the behavior of each 256 mechanism at a single node. Overhead in these cases is expressed 257 in terms of a, the number of ancestors of a node, or d, the number 258 of descendants of a node. The setup latency column lists time in 259 terms of the number of trips taken between a receiver and the 260 multicast tree. 262 Clearly the Merge Up mechanism does not scale well because each 263 node must store each descendent as well as send one message 264 upstream for each descendant. The advantages of using a 265 receiver-oriented mechanism are lost with Merge Up; a sender- 266 oriented mechanism has the same message overhead, but only the 267 sender must store the descendants. 269 The MORF and Merge Down mechanisms have a similar overhead in this 270 situation. The MORF mechanism may have a longer setup latency, 271 but in return has the distinct advantage that it may prevent 272 rather than just detect loops, as discussed above. 274 When we relax the assumption that one receiver joins the tree at 275 time, thus allowing multiple simultaneous Setups, the other 276 tradeoffs of these two mechanisms become more apparent. In this 277 situation, MORF must take into account conflicting Setups. We 278 assume that it will use a binary exponential backoff to prevent 279 thrashing. If we also assume a message transmission takes a 280 uniform time t when sent over any link, then the dynamic setup 281 latency for MORF: 283 Latency_MORF = 3Lt(c+1) + sum{i=1->c} b*2^{i-1}, 285 where L is the average length of the branch from a receiver to the 286 rest of the tree, b is the backoff constant, and c is the number 287 of conflicts the Setup encounters. 289 When considering these dynamic conditions, each node using the 290 Merge Down mechanism may potentially send O(a) messages 291 downstream, since each ancestor may send the node one Merge 292 message. In addition, the setup latency for Merge Down must take 293 into account the time required to break loops. The worst case 294 time to break a loop of m nodes is t(m-1), so the setup latency 295 can be given by: 297 Latency_MergeDown = 2Lt + sum{i=1->l} (m_i-1)t, 299 where l is the number of loops encountered and m_i is the number 300 of nodes in loop i. 302 As can be seen from this analysis, the Merge Down mechanism 303 requires a robust protocol design to ensure that loops are quickly 304 detected and broken. The more merges that occur simultaneously, 305 the longer it will take for the mechanism to distribute the 306 information needed to break the loops. The Merge Down mechanism 307 will also have to detect when a Merge message is lost, as that 308 event can cause a loop to persist. In contrast, MORF uses a 309 simpler protocol to prevent loops and uses more complexity only at 310 the edges of the network. 312 2.3 Unicast Route Setup 314 Previous work has studied the efficacy of using source routing to 315 support unicast real-time applications [3]. One way to use source 316 routes to provide alternate paths or pinned routes is to embed the 317 source route in an application's packets. Assuming the route will 318 be inserted by a filter at a sender's nearest router, no 319 modifications to applications will be needed. However, because 320 many routers currently delay processing of source routed packets, 321 this mechanism may not be applicable to applications with strict 322 delay requirements. 324 An alternative is for the sender's nearest router to insert a 325 label in the application's packets rather than a source route. 326 This label can reference an alternate path or pinned route that is 327 installed using MORF. Because unicast applications involve only 328 one receiver, the setup latency will only be 1 trip. Either the 329 sender or receiver can initiate the route setup, although 330 initiating at the sender will require trivial modifications to the 331 protocol. 333 3. Acknowledgments 335 Bob Braden, Deborah Estrin, and Scott Shenker provided valuable 336 feedback on this work. 338 References 340 [1] A. J. Ballardie, P.F. Francis, and J. Crowcroft, "Core Based Trees", 341 In "ACM SIGCOMM", August 1993. 343 [2] R. Braden, L. Zhang, S. Berson, S. Herzog, and S. Jamin, "Resource 344 ReSerVation Protocol (RSVP) - Version 1 Functional Specification", 345 work in progress, November 1996. 347 [3] Lee Breslau, ""Adaptive Source Routing of Real-Time Traffic in 348 Integrated Services Networks"", PhD thesis, University of Southern 349 California, December 1995. 351 [4] Stephen Deering, Deborah Estrin, Dino Farinacci, Van Jacobson, 352 Ching-Gung Liu, and Liming Wei, An Architecture for Wide-Area 353 Multicast Routing, In "ACM SIGCOMM", August 1994. 355 [5] J. Moy, "Multicast Extensions to OSPF", RFC 1584, March 1994. 357 [6] D. Waitzman, C. Partridge, and S. Deering, "Distance Vector 358 Multicast Routing Protocol", RFC 1075, November 1988. 360 [7] Daniel Zappala, Bob Braden, Deborah Estrin, and Scott Shenker, 361 "Interdomain Multicast Routing Support for Integrated Services 362 Networks", work in progress, March 1997. 364 [8] Lixia Zhang, Steve Deering, Deborah Estrin, Scott Shenker, and 365 Daniel Zappala, "RSVP: A New Resource ReSerVation Protocol", "IEEE 366 Network", September 1993. 368 Security Considerations 370 Security considerations are not discussed in this memo. 372 Author's Address 374 Daniel Zappala 375 USC Information Sciences Institute 376 4676 Admiralty Way, Floor 10 377 Marina del Rey, CA 90292 378 EMail: daniel@isi.edu