Internet Engineering Task Force J. Hou, H.-Y. Tyan, B. Wang INTERNET DRAFT The Ohio State University Y.-M. Chen Fujitsu Labs of America February 1999 QoS Extension to CBT Status of this Memo This document is an Internet-Draft and is in full conformance with all provisions of Section 10 of RFC2026. 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." The list of current Internet-Drafts can be accessed at http://www.ietf.org/ietf/1id-abstracts.txt. The list of Internet- Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html. Abstract This document describes extension to the CBT protocol to maintain a multicast tree with user-specified QoS properties. Specifically, it describes enhancements in the member join/leave and state update/refresh procedures to facilitate the deployment of additive (e.g., end-to-end delay bound), multiplicative (e.g., packet loss ratio along a path) and concave (e.g., minimum bandwidth available) QoS. Eligibility tests are devised to verify whether or not a new member can join a multicast tree at adequate QoS, while not violating the QoS received by on-tree members. Management of router state is based on a simple state update and refresh procedure that can be readily integrated with the tree maintenance mechanism that exists in CBT (i.e., echo-requests and echo-replies). Hou et al. Expires 30 September 1999 [Page 1] Internet-Draft QoS Extension to CBT 15 March 1999 TABLE OF CONTENTS Status of This Memo 1 Abstract 1 1. Introduction 3 1.1. Objective ................................................... 3 1.2. Network Model ............................................... 3 1.3. QoS Parameters Considered ................................... 4 1.4. Terminology ................................................. 5 1.5. Overview of QoS Extension ................................... 5 2. The QoS Extension in the Case of Imposing a Bound on Additive QoS Parameters 7 2.1. State Kept at Each On-Tree Router ........................... 7 2.2. Eligibility Tests and Member Join Procedure ................. 8 2.3. Member Leave Procedure ...................................... 9 3. The QoS Extension in the Case of Imposing a Bound on Multiplicative QoS Parameters 10 3.1. State Kept at Each On-Tree Router .......................... 11 3.2. Eligibility Tests and Member Join Procedure ................ 11 3.3. Member Leave Procedure ..................................... 12 4. The QoS Extension in the Case of Imposing a Bound on Concave QoS Parameters 12 4.1. State Kept at Each On-Tree Router .......................... 13 4.2. Eligibility Tests and Member Join Procedure ................ 13 4.3. Member Leave Procedure ..................................... 14 5. State Update and Refreshed Based on the Soft State Concept 14 5.1. State Establishment ........................................ 14 5.2. State Refresh and Update ................................... 15 6. What if the QoS Requirements are Heterogeneous .................. 17 6.1. Receiver Heterogeneity in the Case of Additive QoS Parameters17 6.2. Receiver Heterogeneity in the Case of Multiplicative QoS Parameters ................................................. 18 7. Security Considerations 18 A. Message Format 18 A.1. CBT Packet Format .......................................... 18 A.2. Options Defined in the QoS Extension ....................... 20 References 24 Hou et al. Expires 30 September 1999 [Page 2] Internet-Draft QoS Extension to CBT 15 March 1999 1. Introduction 1.1. Objective This Internet Draft presents a set of QoS enhancements (in the the member join/leave and state update/refresh procedures), to allow QoS deployment in the Core Based Tree (CBT) Protocol [1,2], with the minimal impact to the existing infrastructure. Specifically, we consider additive QoS (e.g., end-to-end delay bound), multiplicative QoS (e.g., maximum packet loss ratio), and concave QoS (e.g., minimum bandwidth available) [3], and devise a unified QoS extension framework. In particular, we (i) devise eligibility tests to verify whether or not a new member can join a multicast tree at adequate QoS, while not violating the existing QoS to the other on-tree members; (ii) determine the set of states needed to conduct eligibility tests; and (iii) devise a state update/refresh procedure that is based on soft state and can be readily integrated with the tree maintenance mechanism that already exists in CBT, e.g., sending of echo-requests and echo-replies in CBT. Although we focus on CBT in the document, the proposed QoS extension can be applied to any bi-directional multicast routing protocol with the explicit member join procedure and soft state refresh procedure, such as Simple Multicast [9]. 1.2. Network Model We consider a network that supports both best-effort traffic and traffic with QoS requirements. The way in which network resources are split between the two classes is irrelevant to the document, except for the assumption that each router in the network supports the QoS extension and is able to identify and advertise to their immediate neighbors the QoS parameter of interest experienced by packets when traversing links emanating from the router. We represent a network by a weighted digraph G = (V, E), where V denotes the set of routers and E the set of network communication links connecting the routers. We define a link-delay (available bandwidth) function f_D: E --> R+ (f_B: E --> R+) which assigns a non-negative weight to each link in the network. The value of f_D(i) is a measure of the delay which packets experience on link i in E. (The value of f_B(i) is a measure of the bandwidth available on link i in E.) Similarly, we define a packet loss function p_L: E --> [0,1] which assigns a non-negative fractional weight to each link in the network. The value of p_L(i) is the probability of packet loss on link i in E. Hou et al. Expires 30 September 1999 [Page 3] Internet-Draft QoS Extension to CBT 15 March 1999 We denote as M_g (which is a subset of V) a set of routers to which hosts that belong to a group g are attached. For notational simplicity, we call the set M_g a multicast group with each router v in M_g as a group member. (Actually the multicast group is the set of hosts that are directly attached to routers in M_g.) We consider the most general many-to-many multicast paradigm in which each router v in M_g can be a source, in addition to being a receiver in the group. Let M_s denote the set of group members that are also sources. Packets originating from router v in M_s have to be delivered to a set of receiver routers M_g - {v}. We use P_T(v_s, v_d) to denote the path from a source router v_s to a receiver router v_d in M-{v_s} in the tree T. We also use "x in P_T(v_s,v_d)" to denote that P_T(v_s,v_d) traverses either router x or link x. 1.3. QoS Parameters Considered We define m(l) as a QoS metric for link l. For any path P_T(u,v) = (u,i,j,...,k,v), we say metric m is additive if m(u,v) = m(u,i) + m(i,j) + ... + m(k,v). For example, the end-to-end delay d(u,v), which packets forwarded from router u to router v experience, is additive and is equal to the sum of individual link metric m(i,j) along the path P_T(u,v) We say metric m is multiplicative if m(u,v) = m(u,i) x m(i,j) x ... x m(k,v). For example, the probability, 1 - p_L(u,v), for a packet to reach router v from router u along P_T(u,v) is multiplicative and is equal to the product of individual link metric p_L(i,j) along the path P_T(u,v). We say metric m is concave if m(u,v) = min[ m(u,i), m(i,j), ..., m(k,v) ]. For example, the bandwidth b(u,v), available along a path from router u to router v, is concave and is equal to the minimum bandwidth f_B(i,j) among the links in path P_T(u,v) A QoS requirement may be specified as (i) an upper/lower bound on an additive/multiplicative/concave QoS parameter, e.g., an upper bound on the end-to-end delay, a upper bound on the packet loss ratio, or a lower bound on the bandwidth available, from any source to the receiver; or (ii) an upper bound on the inter-destination difference Hou et al. Expires 30 September 1999 [Page 4] Internet-Draft QoS Extension to CBT 15 March 1999 of an (additive or multiplicative) QoS parameter along the paths from a source to any two receivers, e.g., an upper bound on the end-to-end inter-destination delay jitter (defined as the difference between the end-to-end delays along the paths from a source router to any two receiver routers. In this document, we focus on QoS requirements specified in terms of (i). Interested readers are referred to [12] for a detailed account of the QoS extension with respect to requirements specified in terms of (ii). The need for a bounded end-to-end delay, bounded probability of packet loss, and minimal available bandwidth has been well justified [4,5]. The situation in which a bounded inter-destination delay jitter among all the group members arises is also not rare [6]. One possible scenario occurs during a teleconference in which any current speaker should be heard by all participants at approximately the same time to achieve the feeling of multi-party interactive face-to-face discussions. Another application domain is the distributed interactive simulation in which an inter-destination delay jitter bound is needed to constrain the time during which the simulation engines are in inconsistent states. 1.4. Terminology Throughout the document, "downstream" refers to the direction that is away from core. Given a router, a "subtree" refers to the router and the multicast group members reachable by the router through an on- tree path sourced at a downstream interface of the router. 1.5. Overview of QoS Extension In the original CBT protocol, one router for each group is selected as the core router (or termed elsewhere rendezvous point (RP) [11]) for the group. A tree rooted at the core is then constructed to span all the group members. A host first expresses its interest in joining a group by multicasting an IGMP host membership report [7] to its local router which then sends a join-request message to the next hop on the path toward the group's core router. The join-request sets up transient join state (in the form of ) in the routers it traverses. If the transient join state is not ``confirmed'' with a join-acknowledgment message from upstream, the state is eventually timed out. The join- request message travels hop-by-hop toward the core until it reaches the core or an on-tree router, at which point a join-acknowledgment message is sent back along the reverse path, forming a new branch from the tree to the requesting router. When a router receives a Hou et al. Expires 30 September 1999 [Page 5] Internet-Draft QoS Extension to CBT 15 March 1999 join-acknowledgment message, it updates its forwarding cache to reflect the fact that it now becomes an on-tree router, and forwards the join-acknowledgment message back to the requesting router. In the case that a member leaves the group, if the local router (to which the leaving member is attached) does not have any other directly attached members or downstream on-tree routers, the router sends a quit-notification message to its parent router on the tree and deletes the corresponding forwarding cache. To support QoS, we introduce the following QoS extension to the current CBT specification: each join-request message carries, in addition to the interface information, the QoS parameters of interest along the route. When a join-request message reaches the core or an on-tree router, the core/router performs a set of eligibility tests. Although it is preferable that eligibility tests be conducted locally at the on-tree router, the on-tree router may not be able to approve a join-request only based on its local state, and may have to collaborate with other on-tree routers to conduct the eligibility tests. Moreover, the state kept at some other on-tree routers may have to be changed because of the member join. That is, collaboration among on-tree routers is sometimes inevitable in approving a join request. Only after the branch survives the eligibility tests will it be eligible to join the multicast tree (under which case a join-acknowledgment message is then sent back). In the case of member leave, the state kept at the other on-tree routers may have to be updated and proper procedures be taken to notify on-tree routers of the need to update their states. Note that while changes to the current CBT protocol specification seem unavoidable, we have attempted to keep them as small as possible. To realize the above QoS extension, we consider, for each type of QoS requirements, the following issues: (1) What is the minimum set of states each on-tree router has to keep in order to conduct the proposed work? (2) What are the eligibility tests conducted at the time of member join? How are eligibility tests collaboratively conducted among on- tree routers if need be? (3) Whether or not, and how, is the set of states kept at an on-tree router updated in response to member leave? (4) How is the set of states updated and refreshed at each on-tree router? Hou et al. Expires 30 September 1999 [Page 6] Internet-Draft QoS Extension to CBT 15 March 1999 The rest of the document is structured as follows. In Sections 2-4, we present the QoS extension in the cases of imposing a bound on additive QoS parameters, of imposing a bound on multiplicative QoS parameters, and of imposing a bound on concave QoS parameters, respectively. (The case of imposing a bound on the maximum difference of (additive or multiplicative) QoS parameters along the paths from a source to any two receiver routers is elaborated on in [12].) In Section 5, we present the state update and refresh procedure based on the soft state concept. In Section 6, we discuss how to extend the work in Sections 2-4 to the case of heterogeneous receiver-initiated QoS requirements. The security issue is considered in Section 7. Finally, Appendix A gives the message format defined in the QoS extension. 2. The QoS Extension in the Case of Imposing a Bound on Additive QoS Parameters We first consider the case in which the QoS requested is expressed in terms of additive QoS parameters. Without loss of generality, we use the end-to-end delay as an example, and impose an upper bound, D, on the acceptable end-to-end delay perceived by a receiver router along any path from a source router to the receiver router in a multicast group. 2.1. The State Kept at Each On-Tree Router To satisfy the end-to-end delay bound, each on-tree router, u, keeps the following state for each downstream interface: (1) d_{max,i}(u,*): the maximum delay among the on-tree paths from router u to the downstream on-tree group members reachable on interface i, where interface i is a downstream interface and downstream is defined with respect to the core. (2) d_{max,i}(*,u): the maximum delay among the on-tree paths from all the downstream on-tree source group members reachable on interface i to router u. The per-node state d_{max}(u,*) is naturally defined as the maximum d_{max,i}(u,*) value among the downstream interfaces i of router u. Similarly d_{max}(*,u) is defined as the maximum d_{max,i}(*,u) value among the downstream interfaces i of router u. One can interpret d_{max}(u,*) and d_{max}(*,u) as the maximum outgoing and incoming delays, respectively, incurred when a multicast packet traverses the Hou et al. Expires 30 September 1999 [Page 7] Internet-Draft QoS Extension to CBT 15 March 1999 subtree from/to router u, i.e., d_{max}(u,*) = max_{i in DI} d_{max,i}(u,*) and d_{max}(*,u) = max_{i in DI} d_{max,i}(*,u), where DI is the set of downstream interfaces of router u. Let T_s(u) denote the subtree rooted at router u, then each on-tree router keeps the state information for T_s(u). The reason for keeping per- downstream-interface (instead of per-node) state will become clearer when we discuss the member leave procedure in Section 2.3. 2.2. Eligibility Tests and Member Join Procedure When a join-request message from a joining router v arrives at an on-tree router u, router u checks if d_{max}(*,v) = d(u,v) + d_{max}(*,u) <= D. (2.1) In addition, if the joining member v is also a source, router u further checks if d_{max}(v,*) = d(v,u) + d_{max}(u,*) <= D. (2.2) Both parameters d_{max}(u,*) and d_{max}(*,u) are kept at each on- tree router u as the state. Both parameters, d(v,u) and d(u,v), can be carried in the join- request message and updated as the message travels from router v to router u. If Eq. (2.1) holds, it implies the QoS requirement of the new member v is fulfilled by all the source group members in T_s(u). Similarly, if Eq. (2.2) holds, it implies the QoS requirements for the group members in T_s(u) are not violated due to join of the new source member v. If Eq. (2.1) (or Eq. (2.2) in the case that router v is also a source) does not hold, the join request is immediately rejected and a rejection-reply message is sent back to the joining router v. Otherwise, router u forwards upstream to its parent router w the join-request with the updated accumulative delay information (d(w,u) + d(u,v) and, in addition, d(v,u) + d(u,w) if router v is also a source). Upon receipt of the join-request on interface i, Router w Hou et al. Expires 30 September 1999 [Page 8] Internet-Draft QoS Extension to CBT 15 March 1999 conducts the eligibility test (i.e., Eqs. (2.1)-(2.2) except u is replaced by w in the expressions) to verify if join of router v violates the QoS requirements of all the on-tree group members in T_s(w) as well as if the QoS requirement of router v is fulfilled by all the on-tree source members on T_s(w). If the eligibility test succeeds, router w forwards upstream to its parent router the join- request (with the updated accumulative delay information); otherwise, it sends downstream to its child router a rejection-reply message. The process repeats until the join-request is either rejected at some upstream on-tree router or forwarded to, and approved by, the core (which then sends back a join-acknowledgment message along the reversed on-tree path), whichever occurs first. In the former case, the on-tree router, u, where the join-request arrives initially sends back a rejection-reply message to the joining router v. In the latter case, each on-tree router, w, on the path from router u and the core updates its state upon receipt of the join-acknowledgment message from upstream, if d(w,v) > d_{max,i}(w,*) and/or d(v,w) > d_{max,i}(*,w), where interface i is the interface on which router w received the corresponding join-request, and router u sends back a join-acknowledgment message. In short, each on-tree router u keeps only its subtree state information (which eases the job of state update and maintenance at the time of member join). When a join-request arrives at an on-tree router u, it has to pass a sequence of eligibility tests before it is approved, where each test is performed router by router on the tree- path from router u to the core. Note that to avoid potential QoS conflicts among multiple members that intend to join a multicast group at the same on-tree router, an on-tree router will not process the next request until it finishes processing the current join request and sends back either a rejection-reply message or a join-acknowledgment message. As a result, a new join-request may be blocked between the time between a previous join-request is forwarded upstream and the corresponding response returns. We argue that since only the on-tree routers between router u and the core are involved in jointly approving a join-request, this transient period cannot be prohibitively long. 2.3. Member Leave Procedure When a member router v leaves a multicast tree, it sends a quit- notification message (with the accumulative delay information d(v,u)) to its parent router u. Upon receipt of a quit-notification message on interface i, if router u does not have any other local members (on the directly attached subnet) or downstream on-tree routers, it sends Hou et al. Expires 30 September 1999 [Page 9] Internet-Draft QoS Extension to CBT 15 March 1999 a quit-notification message to its parent router w and deletes the corresponding forwarding cache. Otherwise, router u first deletes from the forwarding cache the interface on which the quit- notification message arrives (interface i), and then checks if d(u,v) <= d_{max}(u,*), (2.3) and in addition, in case that router v is a also source router, d(v,u) <= d_{max}(*,u). (2.4) If Eq. (2.3) (and in addition, Eq. (2.4), in the case that router v is also a source router) holds, it implies the state kept at router u as well as other on-tree (upstream) routers will not change as a result of this member leave. Otherwise, router u first updates its per-node state to reflect the fact that router v has left the multicast tree and sends upstream to its parent router w a leave- update message that carries d(u,v) + d(w,u) (and in addition, d(v,u) + d(u,w), if the leaving member is also a source). Upon receipt of a leave-update message, router w checks whether or not its state is affected by the member leave (i.e., Eqs. (2.3)--(2.4) except u is replaced by w). The update process repeats until either the test succeeds at some upstream router or the leave-update message reaches the core. The aforementioned procedure also illustrates why on-tree routers have to keep per-downstream-interface state. If only per-node state were kept, when a leave-request leads to the readjustment of d_{max}(u,*) or d_{max}(*,u), the node would not have information for the new value. 3. The QoS Extension in the Case of Imposing a Bound on Multiplicative QoS Parameters We now consider the case in which the QoS requested is expressed in terms of multiplicative QoS parameters. Recall that for any path P_T(u,v) = (u,i,j,...,k,v), we say metric m is multiplicative if m(u,v) = m(u,i) x m(i,j) x ... x m(k,v). Taking log of the above expression, we have log m(u,v) = log m(u,i) + log m(i,j) + ... + log m(k,v). That is, the QoS extension discussed in Section 2 can be readily applied if the state is kept in the log form of a multiplicative QoS metric. Without loss of generality, we use the packet loss ratio as Hou et al. Expires 30 September 1999 [Page 10] Internet-Draft QoS Extension to CBT 15 March 1999 an example and impose an upper bound, 1-L (0 <= L < 1), on the minimum acceptable packet loss ratio along an on-tree path leading to the receiver router. 3.1. The State Kept at Each On-Tree Router The packet loss ratio, p_L(u,v), along a path from router u to router v can be expressed as 1 - p_L(u,v) = prod_{l in P_T(u,v)} (1 - p_L(l)). Taking log of the above expression, we have log(1 - p_L(u,v)) = sum_{l in P_T(u,v)} log(1 - p_L(l)). We define the successful transmission index, s(u,v), on the path P_T(u,v) as s(u,v) = log (1 - p_L(u,v)). To satisfy the upper bound on the packet loss ratio, each on-tree router, u, keeps the following state for each downstream interface: (1) s_{min,i} s(u,*): the minimum value of log(1 - p_L(u,v)) among the on-tree paths from router u to the downstream on-tree routers v reachable on interface i. (2) s_{min,i} s(*,u): the minimum value of log(1 - p_L(v,u)) among the on-tree paths from the downstream on-tree source routers v reachable on interface i to router u. The per-node state, s_{min}(u,*), defined as the minimum value of log(1 - p_L(u,v)) among the on-tree paths from router u to downstream on-tree routers v, and s_{min}(*,u), defined as the minimum value of log(1 - p_L(v,u)) among the on-tree paths from the downstream on-tree source routers v to router u, can be obtained by taking the minimum of the corresponding per-interface states over all the downstream interfaces. 3.2. Eligibility Tests and Member Join Procedure Now when a join-request message from a joining router v arrives at an on-tree router u, router u checks if s_{min}(*,v) = s(u,v) + s_{min}(*,u) >= L. (3.1) In addition, if router v is also a source, router u further checks if Hou et al. Expires 30 September 1999 [Page 11] Internet-Draft QoS Extension to CBT 15 March 1999 s_{min}(v,*) = s(v,u) + s_{min}(u,*) >= L. (3.2) Both parameters, s(u,v) = log(1-p_L(u,v)) and s(v,u) = log(1- p_L(v,u)), can be carried in the join-request message and updated as the message travels from router v to router u. The process of conducting the eligibility test (Eqs. (3.1)--(3.2)) and forwarding the join request upstream toward the core in the case that the eligibility test succeeds is virtually the same as that described in Section 2.2. Specifically, if Eq. (3.1) (or Eq. (3.2) in the case that router v is also a source) does not hold, the join request is immediately rejected and a rejection-reply message is sent back to the joining router v. Otherwise, router u forwards upstream to its parent router w the join-request with the updated packet loss information (s(w,u) + s(u,v)) and in addition, s(v,u) + s(u,w), if router v is also a source). The process repeats until the join- request either is rejected at some upstream on-tree router or is forwarded to, and approved by, the core, whichever occurs first. In the former case, the first on-tree router, u, at which the join- request arrives sends back a rejection-reply message to the joining router v. In the latter case, each on-tree router w, on the path from router u to the core, checks if state update is necessary upon receipt of the join-acknowledgment message from upstream. The state is updated if d(w,v) > d_{max,i}(w,*) and/or d(v,w) > d_{max,i}(*,w), where interface i is the interface on which router w received the corresponding join-request. Eventually router u receives the join- acknowledgment message and forwards it downstream to v. 3.3. Member Leave Procedure The procedure taken upon receipt of a quit-notification message is virtually the same as that described in Section 2.3, except that Eqs. (2.3)--(2.4) are now replaced by s(u,v) >= s_{min}(u,*), (3.3) and s(v,u) >= s_{min}(*,u). (3.4) 4. The QoS Extension in the Case of Imposing a Bound on Concave QoS Parameters We now consider the case in which the QoS requested is expressed in terms of concave QoS parameters. Without loss of generality, we use Hou et al. Expires 30 September 1999 [Page 12] Internet-Draft QoS Extension to CBT 15 March 1999 the bandwidth available along a path as an example and impose a lower bound, B, on the minimum bandwidth that must be available along any path from a source router to any receiver router in a multicast group. 4.1. The State Kept at Each On-Tree Router To satisfy the minimum bandwidth requirement, B, for a multicast group, each on-tree router u needs only to keep the state B and a counter, C, of how many source routers currently exist in the subtree, T_s(u), rooted at router u (initially C=0). 4.2. Eligibility Tests and Member Join Procedure When a join-request message from a joining router v arrives at an on-tree router u, router u checks if b(u,v) >= B, (4.1) and in addition, if router v is also a source, router u further checks if b(v,u) >= B. (4.2) Both parameters, b(v,u) and b(u,v), can be carried in the join- request message and updated as the message travels from router v to router u. If Eq. (4.1) (or Eq. (4.2) in the case that router v is also a source) does not hold, the join request is immediately rejected and a rejection- reply message is sent back to the joining router v. Otherwise (the join-request passes the local eligibility test), we consider two cases: (C1) In the case that router v is only a receiver, router u sends back a join-acknowledgment message immediately to reserve bandwidth of amount B, along the reversed path, for the multicast group. (Note that if bandwidth reservation is not combined with routing, and a separate signaling protocol such as RSVP [8] is used for resource reservation, then the bandwidth is not reserved.) There is no need to forward the join-request upstream, because the first receiver router in the subtree, T_S(u), rooted at router u, has reserved bandwidth of amount B on the path from the core to router u. (C2) In the case that router v is both a receiver and a source, if Hou et al. Expires 30 September 1999 [Page 13] Internet-Draft QoS Extension to CBT 15 March 1999 the indicator is zero (i.e., no source router exists in the subtree T_s(u) so far), router u (i) reserves bandwidth of amount B on the upstream on-tree link (u,w), (ii) forwards upstream to its parent router w the join-request in order to reserve the bandwidth of amount B on the path from router w to the core for the multicast group; and (iii) increment the counter C by one. Otherwise, router u sends back a join-acknowledgment to reserve bandwidth of amount B, along the reversed path to the requesting router. The process repeats until the join-request is either rejected (because of insufficient bandwidth on its upstream on-tree link) or approved at some upstream on-tree router x, whichever occurs first. In the former case, each on-tree router, w, on the path between router u and router x releases the reserved bandwidth in the upstream direction, and router u sends back a rejection-reply message to the joining router v. In the latter case, router u sends back a join- acknowledgment message to reserve bandwidth of amount B along the reversed path. 4.3. Member Leave Procedure When a member router v leaves a multicast tree, it sends a quit- notification message to its parent router u. If router u does not have any other local members (on the directly attached subnet) or downstream on-tree routers, it sends a quit-notification message to its parent router w and deletes the corresponding forwarding cache. Otherwise, router u deletes from the forwarding cache the interface on which the quit-notification message arrives. In the latter case, if router v is also a source, router u decrements its counter C by one. If after decrement C becomes zero, router u releases the bandwidth of amount B on link (u,w), and sends upstream to its parent router w a leave-update message to release bandwidth reserved in the upward direction. Upon receipt of a leave-update message, router w (i) decrements its counter C by one, and (ii) releases bandwidth and forwards the leave-update message upstream if C hits zero. The update process repeats until either the leave-update message reaches the core or stops at some upstream router with more than 1 source router in its subtree. 5. State Update and Refresh Based on the Soft State Concept We first discuss how the state is established at each on-tree router. Then, we present the state update and refresh mechanism that exploits the soft state approach. 5.1 State Establishment Hou et al. Expires 30 September 1999 [Page 14] Internet-Draft QoS Extension to CBT 15 March 1999 When a new member v joins a multicast tree, each router w on the path from router v to router u establishes its state using the delay information carried in the join-request and join-acknowledgment messages. For example, the accumulative delay information (contained in the join-request message received on interface i) between router v and the current router w can be used by router w to establish its transient state (d_{max,i}(w,*) = d(w,v) and d_{max,i}(*,w) = d(v,w)). When an off-tree router w with a pending join-request receives the corresponding join-acknowledgment from its upstream router, it updates its forwarding cache to reflect that it now becomes an on-tree router, and updates its transient state as an established one. Router w also forwards the message downstream to the requesting router. The other on-tree routers update their state only if they receive join-request messages as a result of a join-request being forwarded upstream (to be jointly approved by the on-tree routers between the on-tree router at which a join-request initially arrives and the core). 5.2. State Refresh and Update To be robust to message loss, many Internet protocols (e.g., DVMRP [10], PIM [11], CBT [1,2], Simple Multicast [9]) have adopted the soft state approach for state maintenance, i.e., the state kept at each router is created and periodically refreshed by certain state- refresh messages. A state is deleted if no matching refresh messages arrive before the expiration of its associated timer. For example, CBT maintains its tree by having each downstream router periodically send a CBT echo-request message to its upstream neighbor router. The receipt of an echo-request message over a valid child interface prompts an echo-reply message that carries a list of groups for which the corresponding interface is a child interface. If no response is forthcoming within UPSTREAM_EXPIRE_TIME seconds, (e.g., a router's upstream neighbor becomes unreachable), the router sends a quit- notification message upstream, and flushes all of its downstream branches by sending flush-tree messages, allowing them to individually rejoin if necessary. We adopt the soft state approach and devise the state refresh and update procedure accordingly. The proposed state refresh procedure can be easily integrated with the CBT tree maintenance procedure (i.e., sending of echo-request and echo-reply messages) thus making the overheads that result from the proposed QoS extension small. Specifically, the state kept at an on-tree router is associated with the same DOWNSTREAM_EXPIRE_TIME timer. When a timer expires, the corresponding state is removed. An on-tree router initiates a state Hou et al. Expires 30 September 1999 [Page 15] Internet-Draft QoS Extension to CBT 15 March 1999 update process by periodically sending an echo-request message and piggybacking its state in the message. Upon receiving an echo- request message, a parent router updates its state if needed, resets the associated timer, responds with an echo-reply message, and initiates (upstream) a state update process if the its state does change. To deal with the situation in which message loss results in the removal of a valid soft state, we investigate whether or not the correctness of the proposed QoS extension is subject to loss of control messages. To deal with the loss of echo-request/echo-reply messages, CBT sets the UPSTREAM_EXPIRE_TIME and DOWNSTREAM_EXPIRE_TIME timer intervals K times larger than the ECHO_INTERVAL timer interval so that echo-request messages can be lost (K-1) consecutive times before the state is (incorrectly) removed. (K=3 in the current CBT protocol specification.) In the case that echo-request messages are lost more than K consecutive times, we consider the following two cases: (C1) If a downstream router does not hear from its upstream router upon the UPSTREAM_EXPIRE_TIME timer expiration, it considers the path to its upstream router as damaged, and sends a quit- notification message upstream, and flush-tree messages downstream to flush the subtree rooted at it. Each downstream group member will then individually find an alternative route to rejoin the tree. This is the approach currently defined in the CBT protocol specification. (C2) If an upstream router w does not hear from its downstream router u upon the DOWNSTREAM_EXPIRE_TIME timer expiration, it removes the state and the forwarding cache entry as if the subtree (rooted at router u) were ``flushed''. Later when a echo-request message from the router u re-appears at router w, router w, instead of re-establishing the state and the forwarding cache (as the current CBT specification specifies), flushes the sub-tree. This is because during the period when router w and its upstream routers believe the sub-tree is ``flushed,'' if a new join-request arrives at one of these on-tree routers, it may be approved when it should actually be denied when the subtree is taken into account. Since consecutive loss of K echo-request messages is usually a good indication of low delivery quality of downstream links, it would actually be better for the downstream group members to re-join the multicast group individually along an alternative route of better quality. Loss of join-request, join-acknowledgment, and quit-notification messages has been dealt with in the current CBT specification: if any Hou et al. Expires 30 September 1999 [Page 16] Internet-Draft QoS Extension to CBT 15 March 1999 of the join-request or join-acknowledgment messages is lost, the transient state established at each router on the path from the requesting router to an on-tree router is removed upon timer expiration. The state created on the path along which a join- acknowledgment message traverses will eventually time out, due to the lack of echo-request messages from downstream. Similarly, if any quit-notification message is lost, the valid state maintained at upstream routers will eventually time out, due to the lack of echo- request messages from downstream. The same strategy can be directly applied to the QoS extension mechanism to deal with loss of these messages (and rejection-replay messages as well). For example, if a join-acknowledgment message is lost on its way back to the on-tree router at which the join-request initially arrives, some (upstream) router(s) have changed their temporary state into valid soft state, while other (downstream) router(s) remove them. This does not affect the correctness of the proposed extension, because the state at upstream routers will be adjusted upon receipt of the next echo- request message. Similarly, when a leave-update message is lost on its way upstream, the soft state maintained at upstream routers will be adjusted upon receipt of the next echo-request message. The net effect is, however, that during the transient period new join requests may be pessimistically rejected because of tighter (outdated) state kept at some upstream routers. (By the same token, leave-update messages may be totally eliminated.) 6. What if the QoS Requirements are Heterogeneous Since CBT is a receiver-initiated multicast routing protocol, it is especially well-suited to support heterogeneous receiver reservation, i.e., each receiver may request different levels of QoS [8]. (Note, however, that it does not make sense for each receiver to request different bounds on the inter-destination delay jitter.) The eligibility tests and the state update procedure can be modified to support receiver heterogeneity as follows. 6.1. Receiver Heterogeneity in the Case of Additive QoS Parameters Let D_v denote the delay bound imposed by a receiver router v, then the eligibility test (Eqs. (2.1)-(2.2)) is modified as d(u,v) + d_{max}(*,u) <= D_v, (6.1) and d(v,u) <= D_w - d(u,w), for all group members w in T_s(u). (6.2) Hou et al. Expires 30 September 1999 [Page 17] Internet-Draft QoS Extension to CBT 15 March 1999 Note that Eq. (5.2) can be rewritten as d(v,u) <= min_{ w in T_s(u) } D_w - d(u,w). (6.3) The per-interface state kept at each on-tree router u is (i) d_{max,i}(*,u) and (ii) the minimum laxity defined as the minimum difference between D_w and d(u,w) among all downstream on-tree group members w reachable on interface i, i.e., min_{w in T_s(u), reachable on interface i} (D_w - d(u,w)). 6.2. Receiver Heterogeneity in the Case of Multiplicative QoS Parameters Let 1-L_v denote the upper bound on the packet loss ratio imposed by a receiver router v, then the eligibility test (Eqs. (3.1)-(3.2)) is modified as s_{min}(*,v) = s(u,v) + s_{min}(*,u) >= L_v, (6.4) and s(v,u) >= L_w - s(u,w), for all group members w in T_s(u). (6.5) The state kept at each on-tree router u is (i) s_{min,i}(*,u); and (ii) the maximum difference between L_w and s(u,w) among all the downstream on-tree group members w reachable on interface i, i.e., max_{w in T_s(u), reachable on interface i} (L_w - s(u,w)). 7. Security Considerations Work in progress. Appendix A. Message Format As mentioned above, we intend to provide the QoS extension to CBT, with the minimum possible impact to the exciting infrastructure. All of the component mechanisms, data structures, and data formats in CBT remain unchanged except the following new option definitions in the message format. A.1 CBT Packet Format CBT packet formats and message types are defined in the CBT protocol Hou et al. Expires 30 September 1999 [Page 18] Internet-Draft QoS Extension to CBT 15 March 1999 specification [1]. For completeness of the document, we briefly summarize below the packet format that pertains to the document. A.1.1. CBT Common Control Packet Header All CBT control messages have a common fixed length header. 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | vers | type | addr len | checksum | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Figure 1. CBT Common Control Packet Header CBT packet types are: +^Ho type 0: HELLO +^Ho type 1: JOIN_REQUEST +^Ho type 2: JOIN_ACK +^Ho type 3: QUIT_NOTIFICATION +^Ho type 4: ECHO_REQUEST +^Ho type 5: ECHO_REPLY +^Ho type 6: FLUSH_TREE +^Ho type 7: Bootstrap Message (optional) +^Ho type 8: Candidate Core Advertisement (optional) +^Ho Addr Length: address length in bytes of unicast or multicast addresses carried in the control packet. +^Ho Checksum: the 16-bit one's complement of the one's complement sum of the entire CBT control packet. A.1.2. Packet Format for CBT Control Packet Types 0 - 6 A CBT control packet is divided into 3 parts: +^Ho Common Control Packet Header, Hou et al. Expires 30 September 1999 [Page 19] Internet-Draft QoS Extension to CBT 15 March 1999 +^Ho Control Packet Payload, and +^Ho Control Packet Option(s). 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Common | CBT Control Packet Header | Header +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ -------- |Payload Length | # of options | reserved | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Control | address #1 | Packet +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Payload | address #2 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | address #n | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ -------- | option type | option len | option value... | Option(s) +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Figure 2. CBT Control Packet Format for Types 0 - 6. Control Packet Field Definitions: +^Ho # Payload Length: the length of the CBT control packet payload, excluding the common control packet header and option(s). +^Ho # of options: the number of distinct options (as defined by option type) carried in this control packet. +^Ho address #n: control packet payload address(es). Different control packet types carry addresses (multicast and/or unicast) as their payload (e.g. JOIN_REQUESTs), and some control packet types carry no addresses in the payload (e.g. HELLOs). +^Ho option type: unique option identifier. +^Ho option len: option length. The number of bytes consumed by this option's value. +^Ho option value: variable length option value. NOTE: all control messages are padded to a 32-bit boundary. A.2. Options Defined in the QoS Extension A.2.1. Definition of New Option Types Hou et al. Expires 30 September 1999 [Page 20] Internet-Draft QoS Extension to CBT 15 March 1999 CBT has defined 5 types of options (Type 1-5). For the QoS extension, we further define the following options. Table 1. Definition of New Option Types in the QoS Extension _________________________________________________________________ Option Type QoS Parameters QoS Parameters (Homogeneous) (Heterogeneous) _________________________________________________________________ 10 D D_v 11 d_{max}(u,*) min_{w in T_s(u)}(D_w - d(u,w)) 12 d_{max}(*,u) d_{max}(*,u) 13 d(u,v) reverse d(u,v) reverse 14 d(v,u) forward d(v,u) forward ----------------------------------------------------------------- 20 L L_v 21 s_{min}(u,*) max_{w in T_s(u)}(L_w - s(u,w)) 22 s_{min}(*,u) s_{min}(*,u) 23 s(u,v) reverse s(u,v) reverse 24 s(v,u) forward s(v,u) forward ----------------------------------------------------------------- 30 B B_v ----------------------------------------------------------------- 40 JOIN_ACK 41 REJECTION_REPLY _________________________________________________________________ Definitions of the QoS parameters in Table 1 are given in the previous sections in the document. A.2.2. Coding of Parameter Values In order to align to a 32-bit boundary, the actual metric field in the option provides only 16 bits to encode the value. As links supporting bandwidth in the range of Gbits/s are becoming reality, linear representation of the available resource metric is not feasible. We adopt the method of exponential encoding using appropriately chosen implicit base value and number of bits for encoding mantissa and the exponent. A detailed discussion on the exponential encoding method is given in [13]. Alternative approaches include the use of more bits to encode parameters (which are currently under investigation). Delay is encoded in microseconds using the same exponential encoding method except that the base is different. Interested readers are Hou et al. Expires 30 September 1999 [Page 21] Internet-Draft QoS Extension to CBT 15 March 1999 referred to [13] for a detailed account. A.2.3. Sample Control Packets In this section, we give examples of several different CBT control packets with the QoS extension. Specifically, we add options to JOIN_REQUEST, JOIN_ACK, QUIT_NOTIFICATION, and ECHO_REQUEST. Depending on the QoS desired, the options added to control packets differ. 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Common | 3 | 1 | 4 | Checksum | Header +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ -------- | 16 | 5 | reserved | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Control | Group Address | Packet +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Payload | Core Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Join-Originating DR | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ -------- | 10 | 2 | D | Option +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 11 | 2 | d_{max}(u,*) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 12 | 2 | d_{max}(*,u) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 13 | 2 | d(u,v) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 14 | 2 | d(v,u) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ------- Figure 3. Sample (*, G) JOIN_REQUEST with delay QoS metric 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Common | 3 | 1 | 4 | Checksum | Header +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ -------- | 16 | 1 | reserved | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Control | Group Address | Packet +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Payload | Core Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Join-Originating DR | Hou et al. Expires 30 September 1999 [Page 22] Internet-Draft QoS Extension to CBT 15 March 1999 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ -------- | 30 | 2 | B | Option +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ------- Figure 4. Sample (*, G) JOIN_REQUEST with bandwidth QoS metric 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Common | 3 | 2 | 4 | Checksum | Header +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ -------- | 12 | 1 | reserved | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Control | Group Address | Packet +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Payload | Join Originating DR (copied from JOIN_REQUEST) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ -------- | 40 | 0 | PADDING | Option +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ------- Figure 5. Sample (*, G) JOIN_ACK 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Common | 3 | 4 | 4 | Checksum | Header +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ -------- | 8 + (n x 4) | 3 | reserved | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Control | ECHO_REQUEST Originating Router | Packet +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Payload | Address #1 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Address #2 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Address #n | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ -------- | 11 | 2 | d_{max}(u,*) | Option +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 12 | 2 | d_{max}(*,u) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 14 | 2 | d(v,u) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ------- Figure 6. Sample ECHO_REQUEST with delay QoS metric We can eliminate the need for a new type of message LEAVE_UPDATE by augmenting the QUIT_NOTIFICATION with options. The only change to the CBT code is for it to check whether or not QUIT_NOTIFICATION packets have options. Hou et al. Expires 30 September 1999 [Page 23] Internet-Draft QoS Extension to CBT 15 March 1999 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Common | 3 | 3 | 4 | Checksum | Header +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ -------- | 16 | 4 | reserved | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Control | Group Address | Packet +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Payload | Core Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Join-Originating DR | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ -------- | 10 | 2 | D | Option +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 11 | 2 | d_{max}(u,*) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 12 | 2 | d_{max}(*,u) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 14 | 2 | d(v,u) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ------- Figure 7. Sample (*, G) QUIT_NOTIFICATION/LEAVE_UPDATE with delay QoS metric There is no need to change ECHO_REPLY. References [1] A. Ballardie, B. Cain, Z. Zhang, "Core based trees (CBT version 3) multicast routing - protocol specification," draft-ietf-idmr-cbt- spec-v3-00.txt, Internet-draft, Inter-domain multicast routing, March 1998. [2] A. Ballardie, "Core based trees (CBT) multicast routing architecture," RFC 2201, ftp://ds.internic.net/rfc/rfc2201.txt. [3] Z. Wang and J. Crowcroft, "Quality-of-service routing for supporting multimedia applications," IEEE Journal on Selected Areas in Communications, Vol. 14, No. 7, pp. 1228--1234, September 1996. [4] C. M. Aras, J. F. Kurose, D. S. Reeves, and H. Schulzrinne, "Real-time communication in packet-switched networks," Proceedings of the IEEE, Vol. 82, No. 1, pp. 122--139, January 1994. [5] H. Zhang, "Service Disciplines for guaranteed performance service in packet-switching networks," Proceedings of the IEEE, Vol. 83, No. Hou et al. Expires 30 September 1999 [Page 24] Internet-Draft QoS Extension to CBT 15 March 1999 10, October 1995. [6] G. N. Rouskas and I. Baldine, "Multicast routing with end-to-end delay and delay variation constraints," IEEE Journal on Selected Areas in Communications, Vol. 15, No. 1, pp. 1--9, April 1997. [7] W. Fenner, "Internet Group Management Protocol: version 2 (IGMPv2)," draft-ietf-idmr-igmp-v2-08.txt, Internet-draft, Inter- domain multicast routing, 1998. [8] R. Braden, L. Zhang, S. Berson, S. Herzog, and S. Jamin, "Resource ReSerVation protocol RSVP - version 1 function specification," draft-ietf-rsvp-spec-15.ps, Internet draft, May 1997. [9] R. Perlman, C.-Y. Lee, A. Ballardie, J. Crowcroft, Z. Wang, and T. Maufer, "Simple multicast: a design for simple, low-overhead multicast," http://www.ietf.org/internet-drafts/draft-perlman- simple-multicast-01.txt, December 1998. [10] T. Pusateri, "Distance vector multicast routing protocol," ftp://ds.internic.net/internet-drafts/draft-ietf-idmr-dvmrp-v3- 04.txt, Internet draft, February 1997. [11] D. Estrin, D. Farinacci, S. Deering, D. Thaler, A. Helmy, M. Handley, V. Jacobson, C. Liu, P. Sharma, L. Wei, "Protocol independent multicast - sparse mode (PIM-SM): protocol specification," http://netweb.usc.edu/pim, RFC 2362 and Internet draft, 1998. [12] H.-Y. Tyan, J. Hou, B. Wang, and Y.-M. Chen, "QoS extension to CBT," Technical report, Dept. of Electrical Engineering, The Ohio State University, Columbus, OH. Available at http://eewww.eng.ohio- state.edu/drcl/pubs.html. [13] G.Apostolopoulos, R. Guerin, S. Kamat, A. Orda, T. Przygienda, and D. Williams, "QoS Routing Mechanisms and OSPF Extensions", draft-guerin-qos-routing-ospf-04.txt. Author Information: Jennifer C. Hou Department of Electrical Engineering The Ohio State University Columbus, OH 43210-1272, USA e-mail: jhou@ee.eng.ohio-state.edu voice: +1 614 292 7290 Fax: +1 614 292 7596 Hou et al. Expires 30 September 1999 [Page 25] Internet-Draft QoS Extension to CBT 15 March 1999 Hung-Ying Tyan Department of Electrical Engineering The Ohio State University Columbus, OH 43210-1272, USA e-mail: tyanh@ee.eng.ohio-state.edu voice: +1 614 292 3430 Bin Wang Department of Electrical Engineering The Ohio State University Columbus, OH 43210-1272, USA e-mail: bwang@ee.eng.ohio-state.edu voice: +1 614 292 3430 Yao-Min Chen Fujitsu Labs of America 595 Lawrence Expressway Sunnyvale, CA 94086-3922, USA e-mail: ychen@fla.fujitsu.com voice: +1 408 530 4513 Fax: +1 408 530 4518 Hou et al. Expires 30 September 1999 [Page 26]