Internet Draft Daniel Zappala Expiration: September 1997 USC Information Sciences Institute File: draft-zappala-multicast-routing-me-00.txt A Route Setup Mechanism For Multicast Routing March 26, 1997 Status of 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 ds.internic.net (US East Coast), nic.nordu.net (Europe), ftp.isi.edu (US West Coast), or munnari.oz.au (Pacific Rim). Abstract This document describes a multicast route setup protocol that can be used to install alternate paths and pinned routes when they are requested by receivers. We describe the protocol, derive some of its properties, and address its applicability to unicast route setup. Zappala Expiration: September 1997 [Page 1]
Internet Draft Multicast Route Setup March 1997 1. Introduction This document describes a multicast route setup protocol that can be used to install alternate paths and pinned routes when they are requested by receivers. This protocol is designed as part of the interdomain multicast routing architecture described in [7]. In general, this protocol is useful when multicast routers wish to install explicit routes in a multicast tree without coordinating the routing of the entire tree according to a globally defined metric. Thus, in addition to being used as prescribed in [7], this protocol may also be used to install a QoS route for a receiver. We have focused on designing a multicast route setup protocol; a later section describes the relevance of our work to unicast route setup. For the purposes of this document, we assume that receivers use a reservation protocol such as RSVP [8,2] to reserve resources for unicast and multicast flows. By default, these reservations are obtained over an opportunistic, shortest-path multicast tree computed and installed by a multicast routing protocol, likely either DVMRP [6], MOSPF [5], PIM [4] or CBT [1]. Each sender may have its own tree, or all senders may use a shared tree. Throughout this document we assume sender trees, although the mechanism is equally applicable to shared trees. We also assume that a receiver, or some entity acting on behalf of a receiver, may request several services in place of its current opportunistic route: o "Alternate Path": A route that is an alternative to the currently installed route. A receiver may wish to use an alternate path when it is unable to reserve resources along its current path. o "Pinned Route": A route that remains unchanged unless a node along the route fails. A receiver may wish to know that once it has secured a reservation, the route will not change unless it fails, and hence the reservation will likely remain in place. When an application does not use a pinned route (the route is opportunistic), the reservation protocol must adapt the reservation whenever the route adapts to a shorter path, even if the original path is still working. Using these basic services, a receiver may ask for an alternate path that is opportunistic, an alternate path that is pinned, or it may ask to pin its current route. Note that an opportunistic alternate path has some pinned hops while the remaining hops are opportunistic; see [7] for more details. Zappala Expiration: September 1997 [Page 2]
Internet Draft Multicast Route Setup March 1997 As part of the architecture described in [7], we assume that a receiver asks its first-hop router for an alternate path or a pinned route. This router in turn contacts a local route construction agent to construct a route and encodes the response as an explicit route. The setup protocol connects the receiver to the multicast tree along this new path. Along the way, the setup protocol pins any hop that is listed in the route; thus if the receiver wants a pinned route, then every hop between the receiver and the sender must be listed. 2. The MORF Multicast Route Setup Protocol We have designed the MORF multicast route setup protocol to install routes provided by local route construction agents. For each multicast tree built by the multicast routing protocol, MORF creates its own parallel multicast tree consisting of alternate paths and pinned routes. Each branch of this tree, called the Setup Tree, is constructed using a Setup message originated by a leaf router on behalf of local receivers. The Setup message contains an explicit route indicating the path the Setup should travel (Table 1). As the Setup travels upstream, MORF notifies the multicast routing protocol that it is overriding some local portions of the multicast tree with some branches in the Setup Tree. The multicast routing protocol adds these branches to the multicast tree and prunes any conflicting branches from the original tree (Figure 1a). The resulting multicast tree reflects the path installed by MORF (Figure 1b). The multicast tree may be for a single sender [4], or multiple senders may rendezvous via a core [4,1]. In either case, the protocol is the same; in the following discussion we refer to sender-based trees for simplicity. Table 1: MORF Protocol Messages Messages Parameters ----------------------------------------------------------------- Setup(Group,Target,Route) Group : multicast group Failure(Group,Target,JoinRt,TreeRt) Target : sender or core Teardown(Group,Target) Route : explicit route SetupRt: route from Setup TreeRt : route used by tree Zappala Expiration: September 1997 [Page 3]
Internet Draft Multicast Route Setup March 1997 [See postscript version for figures] Figure 1: Using a Setup Message to Install a Route Since the Setup Tree overrides default opportunistic routing, each router in the Setup Tree must have a mechanism to detect failures of an alternate path or a pinned route. The setup protocol may rely on a unicast routing protocol to exchange query messages with its neighbors to determine whether they are alive, or it may use its own similar mechanism. Once a failure is detected, MORF sends a Teardown message both upstream and downstream of the failure to remove failed branches from the Setup Tree (Figure 2a). At each hop, MORF notifies the multicast routing protocol of the branches it is removing. The multicast routing protocol re-builds the multicast tree to reflect its metric, often the shortest path to the sender (Figure 2b). [See postscript version for figures] Figure 2: Using a Teardown to Remove a Failed Route The above examples represent the simplified case when a Setup does not conflict with the rest of the Setup Tree. However, the setup protocol must also resolve Setup messages from different leaves that use conflicting routes, because leaf routers may use independent route construction agents. MORF resolves conflicts by choosing the first route that is installed for any given branch of the tree. Where subsequent routes meet this branch, they must conform to the route used from that point upward toward the source. If the setup protocol does not follow this restriction, then a number of looping scenarios may arise; Section 2.1 discusses these cases and the manner in which they are prevented. Figure 3 shows an example of how all Setup messages except the first one must match the route already used by the Setup Tree. When a Setup message adds a node to the Setup Tree, it caches the route it will use to travel from that node upward toward the sender. If a subsequent Setup message arrives at that node, it compares the remaining route it must travel to the route cached locally. If the Zappala Expiration: September 1997 [Page 4]
Internet Draft Multicast Route Setup March 1997 routes do not match, the node stops processing the Setup and sends a Failure message downstream (Figure 3a). The Failure message contains the route used by the failed Setup and the route used by the tree from the rejecting node upward (Table 1). A router receiving a Failure message merges the two routes it contains to construct a new route that will match the tree, then sends a second Setup with this route (Figure 3b). [See postscript version for figures] Figure 3: Matching Setup Messages It is from this mechanism -- "Match or Fail" -- that MORF derives its name. By using this restriction, MORF may increase the setup latency, but it prevents any loops from forming while the tree is constructed. The remainder of this section discusses potential looping scenarios and analyzes the tradeoffs of MORF versus other potential solutions for preventing loops. 2.1 Looping Scenarios When Setup messages are not restricted to matching the rest of the Setup Tree, a number of possible looping scenarios arise. Figure 4a shows two Setups, each using a strict explicit route. Based on their order of arrival, as shown, if the Setups merge they form a loop. This loop can be prevented if nodes A and C compare the routes and detect the loop will form. However, when three joins are involved, as in Figure 4b, a single node cannot prevent the loop from forming without having more information available. [See postscript version for figures] Figure 4: Loops Formed by Setup Messages To prevent loops, a node can use one of two strategies: 1. Before adding a parent, the node checks all its descendants to be sure the parent is not already a descendant. Zappala Expiration: September 1997 [Page 5]
Internet Draft Multicast Route Setup March 1997 2. Before adding a child, the node checks all its ancestors to be sure the new child is not already an ancestor. We discuss each of these in turn. Due to the dynamic nature of multicast trees, a node may not know all of its ancestors or descendants. While a node knows the route embedded in the Setup message it has sent upstream, that message may have merged with another Setup carrying a different route. Likewise, other Setups may have merged downstream, adding new descendants. One approach to keep nodes updated concerning upstream and downstream merges is to distribute information after each merge. Following solution (1) above, each Setup that merges can send a Merge message upstream containing its route (Figure 5a). Every node can then know all its descendants and thereby detect any loops. Alternatively, in keeping with solution (2) above, each Setup that merges can send a Merge message downstream containing the upstream portion of the route it merged with (Figure 5b). This allows every node to detect loops by knowing all its ancestors. We denote these two mechanisms as "Merge Up" and "Merge Down", respectively. In both of these approaches, information distributed by the Merge messages may be stale, so loops such as that shown in Figure 4 may still form temporarily before being broken. [See postscript version for figures] Figure 5: Merging Setup Messages Instead of Matching As opposed to these solutions, which in some cases will only detect loops after they have been formed, the strategy we use in MORF prevents any loops from forming. By requiring each Setup to match the upstream route already in place on the tree, MORF in effect enforces solution (2) by requiring that each node know its ancestors before it is added to the tree. Once a node is added to the multicast tree, its ancestors do not change. The cost of this strategy is that each Setup may take an extra roundtrip between itself and the rest of the tree. The following section more completely analyses the tradeoffs of MORF versus the other mechanisms discussed above. Zappala Expiration: September 1997 [Page 6]
Internet Draft Multicast Route Setup March 1997 2.2 Analysis of Setup Mechanisms Table 2: Comparison of Setup Mechanisms Mechanism Message Storage Setup Loop Name Overhead Overhead Latency Handling ----------------------------------------------------------------- MORF O(1) O(a) 1 or 3 trips Prevent Merge Down O(1) O(a) 1 trip Detect/Break Merge Up O(d) O(d) 1 trip Detect/Break Table 2 compares the setup mechanisms discussed above when building a single multicast tree, assuming there is no packet loss and that one receiver joins the tree at a time. The columns listing message and storage overhead consider the behavior of each mechanism at a single node. Overhead in these cases is expressed in terms of a, the number of ancestors of a node, or d, the number of descendants of a node. The setup latency column lists time in terms of the number of trips taken between a receiver and the multicast tree. Clearly the Merge Up mechanism does not scale well because each node must store each descendent as well as send one message upstream for each descendant. The advantages of using a receiver-oriented mechanism are lost with Merge Up; a sender- oriented mechanism has the same message overhead, but only the sender must store the descendants. The MORF and Merge Down mechanisms have a similar overhead in this situation. The MORF mechanism may have a longer setup latency, but in return has the distinct advantage that it may prevent rather than just detect loops, as discussed above. When we relax the assumption that one receiver joins the tree at time, thus allowing multiple simultaneous Setups, the other tradeoffs of these two mechanisms become more apparent. In this situation, MORF must take into account conflicting Setups. We assume that it will use a binary exponential backoff to prevent thrashing. If we also assume a message transmission takes a uniform time t when sent over any link, then the dynamic setup latency for MORF: Latency_MORF = 3Lt(c+1) + sum{i=1->c} b*2^{i-1}, where L is the average length of the branch from a receiver to the rest of the tree, b is the backoff constant, and c is the number of conflicts the Setup encounters. Zappala Expiration: September 1997 [Page 7]
Internet Draft Multicast Route Setup March 1997 When considering these dynamic conditions, each node using the Merge Down mechanism may potentially send O(a) messages downstream, since each ancestor may send the node one Merge message. In addition, the setup latency for Merge Down must take into account the time required to break loops. The worst case time to break a loop of m nodes is t(m-1), so the setup latency can be given by: Latency_MergeDown = 2Lt + sum{i=1->l} (m_i-1)t, where l is the number of loops encountered and m_i is the number of nodes in loop i. As can be seen from this analysis, the Merge Down mechanism requires a robust protocol design to ensure that loops are quickly detected and broken. The more merges that occur simultaneously, the longer it will take for the mechanism to distribute the information needed to break the loops. The Merge Down mechanism will also have to detect when a Merge message is lost, as that event can cause a loop to persist. In contrast, MORF uses a simpler protocol to prevent loops and uses more complexity only at the edges of the network. 2.3 Unicast Route Setup Previous work has studied the efficacy of using source routing to support unicast real-time applications [3]. One way to use source routes to provide alternate paths or pinned routes is to embed the source route in an application's packets. Assuming the route will be inserted by a filter at a sender's nearest router, no modifications to applications will be needed. However, because many routers currently delay processing of source routed packets, this mechanism may not be applicable to applications with strict delay requirements. An alternative is for the sender's nearest router to insert a label in the application's packets rather than a source route. This label can reference an alternate path or pinned route that is installed using MORF. Because unicast applications involve only one receiver, the setup latency will only be 1 trip. Either the sender or receiver can initiate the route setup, although initiating at the sender will require trivial modifications to the protocol. 3. Acknowledgments Bob Braden, Deborah Estrin, and Scott Shenker provided valuable feedback on this work. Zappala Expiration: September 1997 [Page 8]
Internet Draft Multicast Route Setup March 1997 References [1] A. J. Ballardie, P.F. Francis, and J. Crowcroft, "Core Based Trees", In "ACM SIGCOMM", August 1993. [2] R. Braden, L. Zhang, S. Berson, S. Herzog, and S. Jamin, "Resource ReSerVation Protocol (RSVP) - Version 1 Functional Specification", work in progress, November 1996. [3] Lee Breslau, ""Adaptive Source Routing of Real-Time Traffic in Integrated Services Networks"", PhD thesis, University of Southern California, December 1995. [4] Stephen Deering, Deborah Estrin, Dino Farinacci, Van Jacobson, Ching-Gung Liu, and Liming Wei, An Architecture for Wide-Area Multicast Routing, In "ACM SIGCOMM", August 1994. [5] J. Moy, "Multicast Extensions to OSPF", RFC 1584, March 1994. [6] D. Waitzman, C. Partridge, and S. Deering, "Distance Vector Multicast Routing Protocol", RFC 1075, November 1988. [7] Daniel Zappala, Bob Braden, Deborah Estrin, and Scott Shenker, "Interdomain Multicast Routing Support for Integrated Services Networks", work in progress, March 1997. [8] Lixia Zhang, Steve Deering, Deborah Estrin, Scott Shenker, and Daniel Zappala, "RSVP: A New Resource ReSerVation Protocol", "IEEE Network", September 1993. Security Considerations Security considerations are not discussed in this memo. Author's Address Daniel Zappala USC Information Sciences Institute 4676 Admiralty Way, Floor 10 Marina del Rey, CA 90292 EMail: daniel@isi.edu Zappala Expiration: September 1997 [Page 9]