Internet Engineering Task Force G. Bianchi INTERNET-DRAFT University of Palermo, Italy Document: N. Blefari-Melazzi draft-bianchi-qos-multicast-over-diffserv-00.txt University of Roma, Tor Vergata, Italy G. Bonafede University of Roma, La Sapienza, Italy E. Tintinelli University of Roma, La Sapienza, Italy Category: Informational December 2002 Expires June 2003 MultiGRIP: Quality of Service Aware Multicasting over DiffServ 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. 1 Abstract Efficient delivery of real-time multicast traffic imposes on the underlying network infrastructure the burden of supporting Quality of Service (QoS). This can be quite a complex issue in a Differentiated Services (DiffServ) IP network, especially if multicast users are allowed to dynamically join and leave the multicast tree. In fact, since DiffServ lacks of explicit reservation states, i) a replicating node cannot test whether a corresponding reservation exists on an output link, and ii) upon a dynamic join of a QoS multicast user, the DiffServ network lacks of control functions to verify whether resources are available along the new path. In this document, we present a solution to support dynamic multicast with QoS over a DiffServ network. Our solution combines two ideas. First, resource availability along a new QoS path is verified via a probe-based approach. Second, QoS is maintained by marking replicated packets with a special DSCP value, before forwarding them on the QoS path. We are fully aware that the possible application of the principles described in this draft in the Internet raises many Bianchi&Blefari Informational - Expires June 2003 [Page 1] Quality of Service Aware Multicasting over DiffServ December 2002 issues, which we do not address. Our aim, then, is not proposing a fully-fledged solution, but contributing to the on-going discussions in the international arena on these matters, by means of what we may see also as a problem statement document. Table of Contents 1 Abstract...........................................................1 2 Introduction.......................................................2 3 Motivation and directions..........................................4 4 QoS Multicast forwarding...........................................5 5 Establishing QoS...................................................8 6 Numerical Results.................................................13 7 Conclusions.......................................................16 8 Appendix: Security considerations.................................16 9 References........................................................17 10 Author's Addresses...............................................18 11 Full Copyright Statement.........................................19 2 Introduction The Internet is witnessing the emergence of several Web-based real-time multimedia and multicast applications, such as video-conferencing, staggered multimedia information retrieval, etc. Unfortunately, the current best-effort Internet does not offer Quality of Service (QoS) guarantees to effectively support unicast streaming services, let alone multicast ones. Several proposals have appeared in the literature in the area of QoS multicast (see [1]). Most of the work concerns the development of multicast QoS routing protocols (e.g., [2], [3]and references therein contained), i.e., protocols that select multicast paths under QoS constraints. Conversely, the issue of endowing current multicast protocols with resource reservation and admission control mechanisms has been generally confined to be a somehow straightforward extension of related unicast protocols. For example, [4] proposes a reservation mechanism for multicast traffic based on a reference Internet model very similar to that proposed in the Integrated Services approach. In addition, the RSVP protocol specification, version 1, [5] has been devised to efficiently support multicast traffic. We argue that novel problems arise in QoS multicast when the reference unicast QoS architecture is not based on explicit and stateful resource reservation protocols. This is specifically the case for the Differentiated Services (DiffServ) framework [6]. DiffServ is a current trend in the Internet community for the development of a QoS architecture not burdened with the complex task of reservation states creation and maintenance. The potential problems, and the complexity of supporting multicast in a DiffServ environment are sketched in [6] and, in greater details, in [7], [8], [9] (and therein contained references). In particular, [7] highlight the following issues. Bianchi&Blefari Informational - Expires June 2003 [Page 2] Quality of Service Aware Multicasting over DiffServ December 2002 - First, dynamic addition of new members to a multicast group can adversely affect existing other traffic, if resources are not explicitly reserved after each join, since replicated packets get the same Differentiated Services Code Point (DSCP) [6] of the original packet and thus experience the relevant treatment, consuming un-reserved resources. - Second, resources should be reserved separately for each multicast tree associated to a given sender, to allow simultaneous sending by multiple sources, with QoS constraints. - Finally, it appears difficult to support heterogeneous multicast groups, i.e., groups in which different users have different necessities. More into details, as regards the last point, participants who can cope with a best-effort service should coexist with participants needing specified and different levels of QoS assurances, so that the same multicast group can deliver differentiated services. For instance, a user could browse a multicast multimedia session in best-effort mode and then decide to switch to a QoS mode (eventually by paying for it). Other related works are the following. The paper [8] proposes a solution for QoS support in DiffServ based on tunneling mechanisms (multicast packets encapsulated in DiffServ), which, in coherence with Internet principles, pushes the complexity to the borders of the DiffServ domains. The paper [9] devises a solution which succeeds in maintaining the integrity of negotiated Service Level Agreement (SLA) by means of weighted traffic conditioning and receiver-initiated marking schemes; admission control operations are performed by suitably signaling network management entities (e.g., Bandwidth Brokers û BB -, or suitable functionality within ingress routers). This solution also supports heterogeneous requirements within a multicast group by encapsulating the markings for each of the branches with such heterogeneous QoS requirements in the packet header, at the ingress router of the domain. Finally, it is worth pointing out that QoS multicasting is a challenging issue also because DiffServ is a sender-driven paradigm whereas multicasting is inherently receiver-driven (more details on this aspect can be found in [9]). In this document, we propose a QoS multicast solution for DiffServ IP networks. The goal of our proposed solution is i) to provide flexible QoS support with respect to heterogeneous multicast groups, and ii) to maintain compatibility with currently deployed multicast protocols, with specific reference to PIM (Protocol Independent Multicast) [10], [11]. The rest of this document is organized as follows. The basic motivations and directions of our proposed solution are outlined in section 3. Our solution is illustrated in section 4, which explains how a QoS user joins a multicast tree, and in section 5, which details how resource reservation is performed on a QoS branching path. For convenience of the reader, section 5 contains also a sub-section that is devoted to briefly Bianchi&Blefari Informational - Expires June 2003 [Page 3] Quality of Service Aware Multicasting over DiffServ December 2002 review a unicast DiffServ QoS solution, formerly proposed in [12], [13] by some authors of this document, and used as a basic brick for our multicast solution. Section 6 contains some introductory performance evaluation results, based on simulations. Conclusions and further research issues are presented in section 7. 3 Motivation and directions The design requirements for our proposed solution were: - QoS should be envisioned as an incremental addition to existing multicast protocols devised for Best-Effort traffic - in other terms, the QoS multicast solution should be backward compatible; - We aim at devising an overlay solution, i.e., whose applicability over the DiffServ network should be done with minimal modification in the DiffServ router operation and in the underlying routing protocols; - The solution should be flexible with respect to heterogeneity of users within a group, and of distribution trees (source-based or core-based); Because of these design requirements, we have selected PIM (Protocol Independent Multicast), in the Sparse Mode (SM) version [10], [11], as the reference multicast routing protocol. The reason is that PIM is independent on the underlying unicast routing protocols, and it allows several different configurations of the multicast distribution tree (unique group shared distribution tree based on a central Core Router; different distribution trees per specific source sending to a group; coexistence of shared and source-specific trees for the same group). To provide QoS multicast over DiffServ, two important issues need to be considered. The first issue is how to differentiate the service level supported on different paths inside the multicast distribution tree. The second one is how to provide an admission control function in order to support dynamic Joins, from QoS-enabled users. In both cases, recall that no per-flow reservation state can be employed in the DiffServ routers, whose role, as specified in the DiffServ architecture [6], is simply to apply different forwarding disciplines to packet aggregates, based on their DSCP value. To solve the first issue, Bless and Wherle [7] suggest to add an additional field in the Multicast Routing Table (MRT), which specifies the DSCP(s) to be used for each output link. It is thus possible to specify whether the next hop is QoS-enabled (i.e., mark packets with a specified DSCP, corresponding to a negotiated QoS level), or not (i.e., mark packets with the Best-Effort DSCP). This solution allows heterogeneous users to share the same multicast distribution tree, as well as it allows deployment of several different QoS levels in the network. Bianchi&Blefari Informational - Expires June 2003 [Page 4] Quality of Service Aware Multicasting over DiffServ December 2002 As discussed in section III below, our solution inherits from [7] this marking strategy. However, this handy tool is not sufficient by itself to provide QoS-aware and differentiated services in a multicast environment. As a matter of fact, the authors of [7] assume to rely on nonspecific control plane entities (e.g., Bandwidth Brokers), which performs an admission control test, and list the following requirements: - "there must be a mechanism for DiffServ nodes to inform a management entity about the join request of a new subtree"; - "a mechanism must be supplied for instructing a router to suitably change (and update) the DSCP value in the related multicast routing table entry. This mechanism may be also incorporated into an existing multicast routing protocol as an extension." In our proposal, we combine a marking strategy very similar to that proposed in [7] with a data plane DiffServ-compliant admission control function, called GRIP (Gauge & Gate Reservation with Independent Probing [12], [13]). As explained in section 5, GRIP can be adapted to the PIM- SM framework. 4 QoS Multicast forwarding This section shows the basic protocol operation. More details on the joining operation of a QoS user to the multicast distribution tree will be given in section 5. For convenience of presentation, we focus on the example network scenario illustrated in Fig. 1. Our discussion will assume PIM-SM as the multicast protocol of reference, being the particularization to PIM-SSM (Source-Specific Multicast) rather straightforward. In the basic operation of PIM-SM, a router, called Rendez-vous Point (RP), is used, for all traffic sources S, as the root of the distribution tree for the multicast group. Destination hosts Hi avail themselves of Designated Routers (DRi) on their LAN, which act on behalf of those hosts as far as the PIM-SM protocol is concerned. In other words, the DR manages, on one side, all local group management information (e.g., via the IGMP protocol), and, on the other side, it emits PIM join/prune messages towards the RP. We assume that all routers are DiffServ capable. In addition, we assume that while routers A, B and C in Fig. 1 support PIM, intermediate DiffServ routers, indicated with the label "R", are transparent to the multicast protocol. Multicast packets are replicated at each multicast router (these routers are the nodes of the multicast tree), and are delivered to the multicast destinations according to the routing information provided by the PIM protocol operation (see [11]) and stored in a table called Multicast Routing Table (MRT). Obviously, multicast routers are stateful, according to the standard multicast protocols, while DiffServ routers are stateless. In this scenario, scalability derives from the fact that only a fraction (possibly small) of the network routers should be multicast capable. Note that the tunneling solution adopted in [8] has the effect of pushing all the handling of multicast states at the border Bianchi&Blefari Informational - Expires June 2003 [Page 5] Quality of Service Aware Multicasting over DiffServ December 2002 of the domains. In this sense, also [8] improves scalability by limiting the number of stateful routers. Following [7], we also assume that each multicast routing table (MRT) stores, for each router output interface (oif), an additional entry. This entry represents the Differentiated Services Code Point (DSCP) value, which is used to mark replicated packets that are forwarded along the considered interface. Fig. 1 shows, in the leftmost column, labeled "Only H1+H2", the MRT states for routers A, B, and C, in the assumption that only hosts H1 (QoS-enabled) and H2 (Best-Effort) are members of the multicast group. In Fig. 1, we use the label "BE" to denote a Best-Effort service, (i.e., DSCP 000000) and the label "QoS" to denote a service with pre-defined QoS requirements. For the sake of simplicity, in what follows we assume that the network provides a single QoS level, in addition to the Best- Effort service. Extension to multiple QoS levels is discussed in section 7. +--+ time |S | ---------------------------------> +--+ Only H1+H2 H3 joins H4 joins || +--------+ +--------+ +--------+ +--+ +------> | MRT-A |->| MRT-A |->| MRT-A | |RP| | |oif|DSCP| |oif|DSCP| |oif|DSCP| +--+ | | 1 | BE| | 1 | BE| | 1 | QoS| +---+ || | | 2 | QoS| | 2 | QoS| | 2 | QoS| |DR1|\ +--+ | +---+----+ +---+----+ +---+----+ +---+\===|A |-----------+ +--------+ +--------+ +--------+ || +--+ +---> | MRT-B |->| MRT-B |->| MRT-B | +--+ || | |oif|DSCP| |oif|DSCP| |oif|DSCP| |H1| +--+ | | 1 | BE| | 1 | BE| | 1 | BE| +--+ |R | -----------+ | 2 | -| | 2 | BE| | 2 | QoS| QoS User +--+ / +---+----+ +---+----+ +---+----+ || / +--------+ +--------+ +--------+ +---+ +--+/ +--+ +--+-------> | MRT-C |->| MRT-C |->| MRT-C | |DR2|===|B |==|R |=|C |=\ |oif|DSCP| |oif|DSCP| |oif|DSCP| +---+ +--+ +--+ +--+ \\ | 1 | -| | 1 | BE| | 1 | BE| || // \\ | 2 | -| | 2 | -| | 2 | QoS| +--+ // \\ +---+----+ +---+----+ +---+----+ |H2| +---+ +---+ +--+ |DR3| |DR4| BE user +---+ +---+ |RP: Rendez-vous Point || || |A,B,C: Multicast routers +--+ +--+ |R: Non multicast routers |H3| |H4| |DR: Designated Router +--+ +--+ |oif: output interface BE user QoS user |BE: Best Effort Fig. 1 û Example network scenario By looking at Fig. 1, we see that the MRT of router A marks packets directed to host H1 (interface 2) with a QoS marking, while it labels Bianchi&Blefari Informational - Expires June 2003 [Page 6] Quality of Service Aware Multicasting over DiffServ December 2002 packets forwarded to interface 1 as BE. In the MRT of router B, clearly, only the interface 1 is active, while router C has no multicast state, at the moment. Let us now discuss what happens when, first the Best- Effort host H3, and then the QoS host H4, join the multicast group. In the case of H3, we adopt a standard PIM Join operation. The Designated Router of H3, DR3, sends a PIM Join(*,G) message towards the RP. When a multicast router receives this message, it adds a new entry to its multicast routing table (MRT), with a BE value, for the associated DSCP marking field. This state will indicate that future datagrams destined for group G must be marked as BE, and forwarded on the interface where the join message came from. The Join(*,G) message is regenerated upstream along what we define as the Branching Path. This is the path from the requesting DR to the first router that already has a Join(*,G) state for that group, which is called Branching Router. Eventually, the Branching Router could coincide with the RP itself. In the specific case of Fig. 1, the Branching Path goes from DR3 to router B, which is the Branching Router, since it already has a (*,G) state created by the Join message coming from host H2, by way of DR2. The second column of Fig. 1, labeled "H3 joins", shows the modified multicast routing tables in routers A, B and C after a successful join of the BE host H3. In the case of QoS-host H4, a fundamental difference is the extent of the Branching Path. If the Designated Router DR4 were to send a standard Join(*,G) message, the Branching Router would have been router C, since it already has a (*,G) state. However, when a QoS host wants to join the group, it needs to send a modified join message, hereafter referred to as Join(*,G,QoS) message, which explicitly carries the QoS level the host is requesting. (note that the new PIM messages considered in this document, i.e., Join(*,G,QoS), Confirm(*,G,QoS), Prune(*,G,QoS), can be built upon the PIM message format specifications, as extensions. In fact, PIM defines only 8 different packets, while a 4-bit packet type field (i.e., 16 possibilities) is available.) This Join(*,G,QoS) message travels upstream until it either reaches the RP, or a router with a (*,G,QoS) state (i.e., a state that instructs a router to send QoS marked traffic over at least one of its interfaces). We define "QoS Branching Path" the path from the Designated Router to the first router that already has a Join(*,G,QoS) state for that group. We name such a router as QoS Branching Router (note that it may be the RP itself). In Fig. 1, the QoS Branching Router for host H4 results to be router A. The rightmost column of Fig. 1, labeled "H4 joins", shows the modified multicast routing tables in routers A, B and C after a successful join of the QoS host H4. As a side comment, note that now the distribution tree has a QoS path from RP to DR4. Therefore, hosts H2 and H3 will receive a BE service only on the last hop of their path. In other words, Bianchi&Blefari Informational - Expires June 2003 [Page 7] Quality of Service Aware Multicasting over DiffServ December 2002 the fact that some members of the multicast groups require QoS, indirectly brings benefits also to Best-Effort users of the same group, even if they are not paying for such benefitsà(see section 6 for performance results). Finally, note that a given host may upgrade its service level. For example, an host may first send a Join(*,G) message to preview the multicast group, and then upgrade to QoS by sending a Join(*,G,QoS). This second message is regenerated upstream along the QoS Branching Path, and, along its way, it modifies the state of the crossed multicast router(s). It remains to show, in the following section, how resource availability along the QoS Branching Path is checked and reserved during a Join(*,G,QoS) procedure. 5 Establishing QoS This section focuses on the detailed operation necessary for a QoS user joining the multicast tree to establish QoS on the new QoS Branching Path. With reference to the example discussed in Fig. 1, in our presentation we focus on the establishment of QoS on the QoS Branching Path from router A as a starting point (the network path from RP to router A is already QoS enabled, because of QoS user H1), to designated router DR4 as a destination point. (we assume that QoS on the last hop DR4 -> H4 is provided by some layer-2 mechanism, or, in other words, that when the host H4 wants to join the multicast tree with QoS, a local admission control function on the last-hop segment has been already performed with positive answer.) Our proposal consists in adapting, to the multicast case, a DiffServ compatible stateless admission control operation based on pure data- plane operation, called GRIP, proposed in [12], [13] with unicast traffic in mind. For convenience of the reader, the basic principles of GRIP are briefly reviewed in section 5.1, while the adaptations of GRIP to multicast are tackled in sections 5.2 and 5.3. 5.1 Review of the basic, unicast, GRIP operation Provisioning of QoS in DiffServ networks is frequently assumed to be accomplished via static over-provisioning (i.e., over-dimensioning of core network links with respect to the expected offered traffic). When dynamic provisioning of DiffServ domains is considered, the traditional approach is to rely on centralized control entities, often referred to as Bandwidth Brokers (BB). A BB is an agent that has sufficient knowledge of resource availability and network topology to make admission control decisions. Border routers use control protocols to interact with this agent. The existence of BBs has been assumed in [7], [9] to manage multicast traffic handling strategies. Bianchi&Blefari Informational - Expires June 2003 [Page 8] Quality of Service Aware Multicasting over DiffServ December 2002 We have shown in [12], [13] that per-flow admission control can be supported on stateless DiffServ domains, i.e., with no need of managing per-flow states within each core router. We recall that, in the DiffServ approach, core routers should not support any explicit signaling protocol (this would imply parsing and interpreting higher layer information contained in signaling packets payload). Instead, their unique duty is to implement low-layer mechanisms devised to forward/drop packets, and apply packet scheduling mechanisms, on the basis of the DSCP value marked on each IP packet header. Our admission control procedure, named GRIP (Gauge & Gate Reservation with Independent Probing), is based on the idea of using "implicit signaling", i.e., GRIP uses pure data-plane operation (packet dropping/forwarding) to convey, at the network borders, the information that the network is congested and a new flow cannot be accepted. A GRIP router is a plain DiffServ router, which handles a number of aggregate classes. A packet belongs to a class on the basis of its DSCP value. A GRIP router supports at least three different DSCP values: Best Effort (BE) packets, QoS information packets, and QoS probing packets. The following description will assume that only one QoS level and one traffic class is supported (i.e., only one information and one probing DSCP label in addition to BE), although we remark that the GRIP router operation can be extended to support several levels of QoS and different traffic classes. (to support several levels of QoS it is necessary to: i) add a new pair of DSCP values (for information and probing packets) for each additional QoS class, and ii) by suitably configuring the (standard) DiffServ scheduling rules among the supported QoS classes to reciprocally protect each of them from congestion eventually arising on other QoS classes. This is perfectly coherent with the DiffServ paradigm, as different QoS classes are handled in a differentiated way. It is worth to note that different DSCP pairs can also be used to manage heterogeneous traffic classes (where a traffic class is defined as a set of sources with equal or very similar traffic parameters, e.g., peak rate, sustainable rate, etc.). In this case, different traffic classes are handled by separate GRIP modules, each implementing a suitably engineered measurement module and decision criterion. Other ways to handle different traffic classes without using separate GRIP modules and DSCP tags, but at the expense of a loss in efficiency, can be found in [15]. Thus, defining the number of traffic classes is a matter of a trade-off between complexity and efficiency. However, we note that separate traffic classes are not necessarily a synonym of complexity and simplistic treatment, but can lead to a greater flexibility). A measurement element in each GRIP module is in charge of taking a smoothed and filtered measure of the load offered by information packets. It will soon be clear that this is a measure of the aggregate Bianchi&Blefari Informational - Expires June 2003 [Page 9] Quality of Service Aware Multicasting over DiffServ December 2002 accepted traffic. On the basis of these traffic measurements, and according to a suitable Decision Criterion, the measurement module drives an Accept/Reject switch. When the switch is in the ACCEPT state, incoming probing packets are forwarded to the output interface. Conversely, probing packets are dropped when the switch is in the REJECT state. In other words, the router acts as a gate for packets labeled as probing, where the gate is opened or closed on the basis of traffic estimates taken on the aggregate accepted load (hence the Gauge&Gate in the acronym GRIP). As thoroughly shown in [12], the described operation is not only compatible with DiffServ, but it is already supported in the specification of the DiffServ Assured Forwarding Per-Hop Behavior (AF- PHB) [14]. Admission control support via implicit signaling arises when the above described operation (localized and independent within each core router) is combined with a suitable end-point operation. When a user terminal requests a unicast connection for the considered QoS and traffic class, the source node transmits a packet whose DSCP is marked as probing. Meanwhile, the source node activates a probing phase timeout, lasting for a reasonable time. If no response is received from the destination node before the timeout expiration, the source node enforces rejection of the connection setup attempt. Otherwise, if a feedback packet is received in time, the connection is accepted, and control is given back to the user application, which starts a data phase, simply consisting in the transmission of data packets, whose DSCP is marked as information. In order for a call setup procedure to succeed, the probing packet needs to find all the routers along the path in the ACCEPT state (if the probing packet encounters a router in the REJECT state, it gets discarded; hence it does not reach the destination, no feedback packet will be relayed back, and the call will be blocked as soon as the probing phase timeout expires). It remains to understand which level of QoS provisioning can be offered by the GRIP operation. Since the decision criterion is locally taken by each router, on the basis of filtered and smoothed measurements taken on the aggregate accepted load (i.e., throughput), GRIP effectiveness is comparable to Measurement Based Admission Control (MBAC) schemes. In fact, GRIPÆs measurement module can make use of state-of-the art MBAC mechanisms (e.g., [16] and references therein contained), for which it has been shown that a target QoS performance can be obtained by simply controlling throughput. An example of a very simple Decision Criterion is to switch from ACCEPT to REJECT state when the aggregate load measurement exceeds a given threshold, and conversely. A more specific example of a Decision Criterion is proposed in [13], where we show that, with suitable additional assumptions, it is possible to provide as much as hard performance guarantees. To conclude, it is useful to recall that, even if GRIP bases the accept/reject decision on end-point operations, it does not strictly belong to the family of schemes generally referred to as Endpoint Bianchi&Blefari Informational - Expires June 2003 [Page 10] Quality of Service Aware Multicasting over DiffServ December 2002 Admission Control (EAC - see [17] and references therein contained). In fact, these schemes assume that the admission control decision is taken at the end-point, as a result of a probing phase whose goal is to allow the end-points to measure whether network resources are available (i.e., external network measures). Conversely, in GRIP the probing phase is limited in principle to a single probing packet transmitted in the network; the goal of the probing packet is to cross through the core routers, and being dropped or forwarded on the basis of internal network measurements, which clearly result to be much more effective, as they are not bounded to last (as in EAC schemes) for just the call setup duration, i.e., few hundreds of ms, for reasonably bounded call set-up times. Finally, we remark that GRIP does not require modifying the basic router operation by introducing packet marking schemes within routers or by forcing routers to parse and interpret higher layer information, as done in some literature proposal (quoted in [13]). 5.2 Adaptation of unicast GRIP to multicast Let us look back at Fig. 1, remembering that we want to establish QoS, considering the network router A as a starting point and the designated router DR4 as a destination point. When the QoS Branching Router A first receives a Join(*,G,QoS) message, it sends a GRIP Probe down on the multicast tree. As reviewed above, the probe is a normal packet, which is distinguished from information packets via a special DSCP marking. Specifically, if QoS packets are marked with DSCP value, say X1, GRIP Probes are marked with a different DSCP value, say X2, which is logically associated to X1. For each QoS level, a different pair of DSCPs should be reserved. All network routers (i.e., both multicast- capable routers and non-multicast capable routers) support a DiffServ Per-Hop-Behavior (i.e., a data-plane mechanism) which consists in letting packets marked as X2 go through only, for instance, if the load run-time measured on X1-marked packets is lower than a given threshold. The result of this operation is that a GRIP Probe is received at the destination DR4 only if all the routers along the path are found in a non-congested state, defined with a suitable criterion (see e.g., [13]). When the GRIP Probe arrives at DR4, a Confirm(*,G,QoS) message is sent back as a feedback packet, to notify the sender node A that all the routers along the QoS Branching Path can accept a QoS connection. When the Confirm(*,G,QoS) message is finally received at router A, the multicast data can be forwarded on the new path. As discussed in section 4, subsequent replicated packets are marked according to the DSCP value specified in the Multicast Routing Table. 5.3 State handling in Multicast Routers While this basic operation appears a straightforward extension of GRIP, there are several details than need to be clarified. A first problem is that, although the aim of the GRIP Probe is to check whether the "point- to-point" communication from A to DR4 can support QoS, in practice it is necessary to route the GRIP Probe as a Multicast packet. In fact, the Bianchi&Blefari Informational - Expires June 2003 [Page 11] Quality of Service Aware Multicasting over DiffServ December 2002 GRIP probe needs to follow the same path of the multicast data packets. We have solved this problem by using a multicast packet type, for the GRIP probe, and by updating the Multicast State within each multicast node so as to route the GRIP Probe down to the appropriate output interfaces only. This is accomplished by extending the PIM-SM state machine associated to each multicast router interface, to manage two additional states per QoS class (see Fig. 2): - Probing State (PRB state): when a multicast router output interface is in the PRB state, it means that a Join(*,G,QoS) message has been received, but no Confirm(*,G,QoS) message has been received yet. - Join-QoS state: this state is activated after a confirmation message, and it implies that the router output interface is QoS- enabled. When in the Join-QoS state, the multicast routing table is set as described in section 4. - When in the PRB state, packets are forwarded according to the following rules: - Packets labeled as information packets are replicated and forwarded according to the existing Multicast Routing Table. With reference to the example of Fig. 1, while host H4 is joining the multicast group (i.e., before a Confirm(*,G,QoS) has arrived), routers A and B continue to operate according to the previous MRT (central column in Fig. 1), i.e., they replicate and forward packets labeled as BE, while router C does not replicate multicast data packets on the output interface 2. - Probes are recognized based on their special DSCP value. They are forwarded only toward interfaces whose state is PRB. With reference to the considered example, a Probe packet is generated at router A and forwarded only on interface 1, while the same Probe packet is forwarded only on interface 2 at both routers B and C. The extended PIM-SM state machine is illustrated in Fig. 2, in the assumption of a single QoS class. In case of more QoS classes, each class will have its own Probing and Join-QoS state. Moreover, for convenience of illustration, we have not explicitly reported in the figure the PIM-SM Prune-Pending state, and a similar QoS-Prune-Pending state necessary to handle the QoS class. Entrance in this state occurs when a Prune(*,G) message (or, in the case of QoS, a Prune(*,G,QoS) message) is received. The system remains in this state until a timeout expires, or a Join(*,G) (or Join(*,G,QoS), in the case of QoS) is received to refresh the multicast state. In fact, we recall that multicast states are "soft" i.e., as long as a group G is active on a router interface, the router will periodically receive Join(*,G) messages in order to refresh the relevant states. When information transfer for this group is no longer desired, the requiring entity should stop sending joins for that group, so that the relevant state expire. In alternative, an explicit PIM Prune(*,G) message (or a Prune(*,G,QoS) in the case of QoS) can be sent towards the RP for that multicast group. Bianchi&Blefari Informational - Expires June 2003 [Page 12] Quality of Service Aware Multicasting over DiffServ December 2002 Prune(*,G) [Via Prune-Pending-QoS] +---------------------------------------------------+ | | | +---------+ Confirm(*,G,QoS) +--------+ | | Probing |-------------------------------->|Join-QoS| | +---------+ +--------+ | A A | | | | Prune(*,G,QoS)| | | | [via Prune-Pending-QoS]| | | | | | | +------------------------------------- | | | | | | |Join(*,G,QoS) Join(*,G,QoS)| | | | | V | +---------+ Join(*,G) +--------+ +->| No Info |-------------------------------->| Join | +---------+ +--------+ A | | Prune(*,G) [via Prune Pending] | +-------------------------------------------+ Fig. 2 û PIM-SM extended state machine 6 Numerical Results As discussed in 5.1, GRIP requires a suitable Decision Criterion, to drive the Accept/Reject switch. Here, we adopt the Decision Criterion proposed in [13], which is based on the runtime estimation of the number of active traffic sources, assumed to be suitably regulated at the boundary of the domain by standard Dual Leaky Buckets (DLBs). In the presence of DLB regulated sources, specific target performance (e.g., loss/delay) levels can be hard-guaranteed whenever the maximum number of admitted flows does not overflow a suitable threshold K. We consider K as a "tuning knob", which allows the domain operator to set target performance levels. The relationship between K and the guaranteed performance levels results from an off-line computation (see [13]). In other words, we choose target performance levels; we map such performances in a value of K by means of a suitable algorithm and then GRIP enforces such value; as a consequence the QoS traffic will perceive the desired performance. In state-based admission control schemes, the enforcement of the threshold K is very simple: it is sufficient to keep track, by means of signaling exchanges, of the number of admitted flows N, and accept a new connection setup request as long as N.K-1. In our, stateless, procedure we estimate at runtime the number of flows, N, avoiding signaling and state maintenance, but incurring in possible inefficiencies (see [13] for details). Bianchi&Blefari Informational - Expires June 2003 [Page 13] Quality of Service Aware Multicasting over DiffServ December 2002 Our criterion does not need assumptions on the traffic source behavior beyond the DLB characterization. However, to generate the simulated traffic, we have to load the DLBs with specific sources. Our simulator has been developed in ns (network simulator, developed at ISI, University of Southern California), which allows using several traffic models (including recorded traces). For the sake of simplicity, here we present results relevant to on-off exponential voice sources. However, we performed other experiments by loading the DLBs with, e.g., MPEG, H.263 (video) and G.7xx (audio) traces. The sources used in the following have On and Off state durations with average values of 352 ms and 650 ms, respectively. The bit rate during the On period is equal to 8 Kbytes/s. The sources are regulated by DLBs with parameters: Peak rate= 8 Kbytes/s; Sustainable rate= 3.4 Kbytes/s; Token Bucket Size= 10600 bytes. The packet size is 106 bytes. In [18] we report graphically the performance experienced by different sets of users in a specific network scenario. Members that joined the multicast tree in QoS mode experience differentiated performance, and lose no packet in our simulation runs, at the expense of BE members. As regards delay, we showed in [18] that by increasing without bound the BE load, queuing delay increases up to queue saturation, while our scheme protects users who requested QoS, by keeping the relevant mean delay constant and under 1 ms, for whatever value of the BE traffic load. (zero loss and 1ms of delay were the pre-tuned performance figures to be guaranteed to QoS traffic by our scheme). A more complex simulation scenario, devised to analyze the interaction between QoS and BE flows, is plotted in Fig. 3. Here we load the system with 100 QoS multicast sources (the same On-Off ones described above); their destinations are located in hosts attached to DR1, DR2, DR3 and DR4. Background unicast BE traffic is added over links L1 and L2, to create bottlenecks (L1 has an offered load of 120% and L2 of 101%). We run three different experiments. In the first one, only users attached to DR1 request QoS, while all other users are in BE mode. In the second and third experiment QoS is requested only by users attached to DR2 and DR3, respectively. The aim of this scenario is to show that when some members of a multicast group require QoS, they indirectly bring benefits also to BE users belonging to the same multicast group and sharing part of the distribution tree. This is shown in Tab. 1. For instance, users attached to DR1 experience zero loss and minimum delay in all experiments, even if they actually request QoS only in experiment 1. Users attached to DR4, who never requested QoS, experience better performances when users in QoS mode get closer. We note that this effect could be an advantage from the network efficiency point of view. Bianchi&Blefari Informational - Expires June 2003 [Page 14] Quality of Service Aware Multicasting over DiffServ December 2002 +-----+ +-----+ 100 QoS sources -> | SQ1 |..|SQ100| +-----+ +-----+ \\ // \\ // +---+ |RP | +---+ || 20 Mbps +---+ | A |=======\ ** +---+ \\ L1, 100 BE unicast * || +---+ Host attached here background traffic * || |DR1| request QoS only in <** +---+ +---+ Experiment 1 | B |=======\ ** +---+ \\ L2, 65 BE unicast * || +---+ Host attached here background traffic * || |DR2| request QoS only in <** +---+ +---+ Experiment 2 | C | +---+ // \\ // \\ Host attached here +---+ +---+ Hosts attached request QoS only in |DR3| |DR4| here request Experiment 3 +---+ +---+ always BE Fig. 3 û Simulator topology However, from a commercial point of view, this might ultimately be a concern: best effort users experiencing excellent performance (because of their closeness to QoS users) might be unwilling to pay in order to upgrade the multicast service to QoS-mode. The Limited Effort (LE) PHB proposed in [7], could be applied to mitigate this problem. Ploss Experim. 1 Experim. 2 Experim. 3 DR1 0.00% 0.00% 0.00% DR2 17.49% 0.00% 0.00% DR3 17.49% 2.39% 0.00% DR4 17.49% 2.39% 0.00% Mean delay Experim. 1 Experim. 2 Experim. 3 DR1 0.2 0.2 0.2 DR2 413.3 0.3 0.3 DR3 414.6 374.8 0.3 DR4 414.6 374.8 0.3 Tab. 1û Loss (percentage) and delay (in ms), scenario B Bianchi&Blefari Informational - Expires June 2003 [Page 15] Quality of Service Aware Multicasting over DiffServ December 2002 7 Conclusions In this document, we have proposed a QoS multicast solution for DiffServ domains. Our solution is built on top of existing multicast protocols (PIM) and allows support for both best-effort and QoS users as well as upgrading a BE user to a QoS one. Additional research activities, not presented here because of space limitations, include issues such as the simultaneous and flexible handling of both source-based and core-based multicast trees. Since PIM allows to dynamically change from the latter to the former during a multicast session, our solution supports this feature via suitably upgraded state machines and procedures; this material is available on request [18]. In addition, we defined in details state machines, procedure and message formats of our solution, taking PIM as the reference protocol. On the other hand, we remark that our solution could be deployed starting also from other existing multicast models, such as Core Based Tree (CBT) and Source Specific Multicast (SSM). A number of possible issues deserving future research include: - extension to the support of multiple QoS levels, especially those appearing when different PHBs are simultaneously operating on the same link; a possible solution to this issue is addressed in [9]; - support of the so-called Limited Effort (LE) PHB, proposed in [7] to protect already existing traffic (including BE) from new users joining the multicast tree. - end-to-end, inter-domain issues: this document is essentially limited to intra-domain issues, even if the unicast GRIP definition does take into account inter-domain operation and some inter-domain issues are addressed in [8]; - fault tolerance: unicast GRIP faults are discussed in [13], PIM faults are taken into account in the protocol specification, but we still have to address faults deriving from the combination of these two techniques; 8 Appendix: Security considerations As all admission control functions, our solution presents the risk of theft of resources through the unauthorized admission of traffic. Although, logically, user terminals are the natural nodes where the endpoint admission control should operate, this is not always realistic, for the obvious reason that the user may bypass the admission control test and directly send probe packets. Identity authentication and integrity protection are therefore needed in order to mitigate this potential for theft of resources [see RFC2990]. Administrators are then expected to protect network resources by configuring secure policers at interfaces (e.g., access routers) with untrusted customers. Similar protections must be provided at the interface between different domains. In particular, it may be necessary to restrict the access to the DS Bianchi&Blefari Informational - Expires June 2003 [Page 16] Quality of Service Aware Multicasting over DiffServ December 2002 class(es) used for admission controlled traffic. For example, a DS domain should re-mark packets when they come from an un-trusted adjacent DS domain. In more generality, we remark that policing and conditioning rules enforced at the border routers of each domain depend on the usage of the considered class within the specific domain and thus have to be accounted of in the definition of each specific PDB supporting admission control. A quite obvious security hazard is flooding the network with probe packets. The objective is twofold. On one side, denial of service situations can be easily created, as a massive loading of the network with probe packets prevent the setup of normal connection. On the other side, the goal might be to affect fairness: the continuous transmission of probe packets at a rate higher than normal connection requests is a mean to gain faster access to resources when these are made available by a router along the path. This implies that some form of traffic conditioning and policing is necessary over probe streams. While it is simple to recognize an hard attack, by monitoring the probe packets crossing an edge router (the probe traffic û at most a few packets per originating connection - is minimal in normal conditions, and thus sudden increments of the probe load are suspicious), it may be not straightforward for DS boundary routers to recognize smoother fairness attacks. However, note that the same fairness problem is present also in more complex reservation mechanisms, such as RSVP (malicious users can continuously require setup to increase their access possibility with respect to normal users). Finally, all the security considerations expressed in [RFC2990] and in multicasting related RFCs apply also to our solution. 9 References [1] Striegel, G. Manimaran: "A survey of QoS multicasting issues", IEEE Communications, pp. 82-87, June 2002. [2] S. Chen, K. Nahrstedt, Y. Shavitt: "A QoS-aware multicast routing protocol", IEEE JSAC, Vol. 18, No. 12, Dec. 2000. [3] Y. Shuqian Yan, M. Faloutsos, A. Banerjea: "QoS-aware multicast routing for the Internet: the design and evaluation of QoSMIC", IEEE/ACM Transactions on Networking, Vol. 10, No. 1, pp. 54-66, Feb. 2002. [4] V. Firoiu, D. Towsley: "Call admission and resource reservation for multicast sessions", IEEE INFOCOM 1996, pp. 94-101. [5] R. Braden, L. Zhang, S. Berson, S. Herzog, S. Jamin: "Resource ReSerVation Protocol (RSVP) - Version 1 Functional Specification", RFC 2205, Sep. 1997. [6] S. Blake, D. Black, M. Carlson, E. Davies, Z. Wang, W. Weiss: "An Architecture for Differentiated Services", RFC 2475, Dec. 1998. [7] R. Bless, K. Wehrle: "IP Multicast in Differentiated Services Networks", Internet Draft, draft-bless-diffserv-multicast- 03.txt, March 2002, work in progress. Bianchi&Blefari Informational - Expires June 2003 [Page 17] Quality of Service Aware Multicasting over DiffServ December 2002 [8] Striegel, G. Manimaran: "A Scalable Protocol for Member Join/Leave in DiffServ Multicast", in Proc. of Local Computer Networks (LCN) 2001, Tampa, Florida, Nov. 2001. [9] Yang, P. Mohapatra: "Multicasting in Differentiated Service Domains", IEEE Globecom 2002. [10] Estrin, D. Farinacci, A. Helmy, D. Thaler, S. Deering, M. Handley, V. Jacobson, C. Liu, P. Sharma, L. Wei: "Protocol Independent Multicast-Sparse Mode (PIM-SM): Protocol Specification", RFC 2362, June 1998. [11] Fenner, M. Handley, H. Holbrook, I. Kouvelas: "Protocol Independent Multicast - Sparse Mode (PIM-SM) Protocol Specification (Revised)", draft-ietf-pim-sm-v2-new-05.txt, Internet-Draft, work in progress, March 2002. [12] G. Bianchi, N. Blefari-Melazzi: "Admission Control over Assured Forwarding PHBs: a Way to Provide Service Accuracy in a DiffServ Framework", IEEE Globecom 2001, San Antonio, Texas, USA, 25-29 November 2001. [13] G. Bianchi, N. Blefari-Melazzi, M. Femminella: "Per-flow QoS Support over a Stateless DiffServ Domain", Computer Networks, Elsevier, special issue on "Towards a New Internet Architecture", Vol. 40, Issue 1, September 2002, pp. 73 û 87. [14] J. Heinanen, T. Finland, F. Baker, W. Weiss, J. Wroclawski: "Assured Forwarding PHB Group", IETF, RFC 2597, June 1999. [15] G. Bianchi, N. Blefari-Melazzi, M. Femminella, F. Pugini: "Performance Evaluation of a Measurement-Based Algorithm for Distributed Admission Control in a DiffServ Framework", IWDC 2001, 17-20 September, 2001, Taormina, Italy (in Lecture Notes in Computer Science, Springer-Verlag, Sergio Palazzo, Ed.). [16] L. Breslau, S. Jamin, S. Schenker: "Comments on the performance of measurement-based admission control algorithms", IEEE Infocom 2000, Tel-Aviv, March 2000. [17] L. Breslau, E. W. Knightly, S. Schenker, I. Stoica, H. Zhang: "Endpoint Admission Control: Architectural Issues and Performance", ACM SIGCOMM 2000, Stockholm, Sweden, August 2000. [18] G. Bianchi, N. Blefari-Melazzi, G. Bonafede, E. Tintinelli: "QUASIMODO: QUAlity of ServIce-aware Multicasting Over DiffServ and Overlay networks", to appear on IEEE Network, special issue on "Multicasting: An Enabling Technology", January/February 2003. Available on request. 10 Author's Addresses Giuseppe Bianchi DIE, University of Palermo Viale delle Scienze, Parco d'Orleans 90128 Palermo, ITALY Tel: +39 091 6566 276 E-mail: bianchi@elet.polimi.it Nicola Blefari-Melazzi DIE, University of Roma, Tor Vergata Bianchi&Blefari Informational - Expires June 2003 [Page 18] Quality of Service Aware Multicasting over DiffServ December 2002 Via del Politecnico, 1 00133 - Roma, ITALY Tel: +39 06 7259 7501 e-mail: blefari@uniroma2.it Giuliano Bonafede Infocom Dpt, University of Roma, La Sapienza Via Eudossiana, 18 00184 - Roma, ITALY Emiliano Tintinelli Infocom Dpt, University of Roma, La Sapienza Via Eudossiana, 18 00184 - Roma, ITALY 11 Full Copyright Statement "Copyright (C) The Internet Society (date). All Rights Reserved. This document and translations of it may be copied and furnished to others, and derivative works that comment on or otherwise explain it or assist in its implementation may be prepared, copied, published and distributed, in whole or in part, without restriction of any kind, provided that the above copyright notice and this paragraph are included on all such copies and derivative works. However, this document itself may not be modified in any way, such as by removing the copyright notice or references to the Internet Society or other Internet organizations, except as needed for the purpose of developing Internet standards in which case the procedures for copyrights defined in the Internet Standards process must be followed, or as required to translate it into languages other than English. The limited permissions granted above are perpetual and will not be revoked by the Internet Society or its successors or assignees. This document and the information contained herein is provided on an "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. Bianchi&Blefari Informational - Expires June 2003 [Page 19]