INTERNET-DRAFT Roland Bless Expires: September 2002 Klaus Wehrle Internet Draft Universitaet Karlsruhe (TH) March 2002 Document: draft-bless-diffserv-multicast-03.txt IP Multicast in Differentiated Services Networks 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. Distribution of this document is unlimited. Abstract This document presents some of the problems which will arise when IP Multicast is used in DiffServ networks without taking special provisions into account for supplying multicast services. Although the basic DS forwarding mechanisms also work with IP Multicast, some facts have to be considered which are related to the provisioning of multicast resources. The presented problems mainly lead to situations in which other service users are affected adversely in their experienced quality. Bless & Wehrle Expires: September 2002 [Page 1] Table of Contents 1 Introduction..................................................2 1.1 Management of Differentiated Services.........................3 2 Problems of IP Multicast in DS Domains........................4 2.1 Neglected Reservation Subtree Problem (NRS Problem)...........4 2.2 Heterogeneous Multicast Groups...............................11 2.3 Dynamics of Arbitrary Sender Change..........................12 3 Solutions for Enabling IP-Multicast in Differentiated Services Networks.....................................................12 4 Security Considerations......................................12 5 References...................................................13 6 Acknowledgements.............................................14 7 Authors' Addresses...........................................14 A Proof of the Neglected Reservation Subtree Problem...........15 A.1 Test Environment and Execution...............................15 B Simulative Study of the NRS Problem..........................17 B.1 Simulation Scenario..........................................17 B.2 Simulation Results for different router types................18 1 Introduction Services in the Internet offering a better quality than the current best-effort service are increasingly required. Many advanced applications need certain assurances from the network layer, e.g., a maximum delay, a minimum packet loss rate or guaranteed transmission rate. The currently used IP mechanisms are not able to offer such guarantees, especially, if group communication is additionally required. The "Differentiated Services" (DiffServ or DS) approach [1, 2, 3] defines certain building blocks and mechanisms to offer qualitatively better services than the usual "normal" best-effort delivery service in an IP network. In the DiffServ Architecture [2] scalability is achieved by avoiding complexity and maintenance of per-flow state information in core nodes and by pushing unavoidable complexity to the network edges. Therefore, individual flows belonging to the same service are aggregated, thereby eliminating the need for complex classification or managing state information per flow in interior nodes. Bless & Wehrle Expires: September 2002 [Page 2] On the other hand, the reduced complexity in DS nodes makes it more complex to use those "better" services together with IP Multicast (i.e., point-to-multipoint or multipoint-to-multipoint communication). Problems emerging from this fact are described in section 2. Although the basic DS forwarding mechanisms also work with IP Multicast, some facts have to be considered which are related to the provisioning of multicast resources. However, it is important to integrate IP Multicast functionality right from the beginning into the architecture, and, to provide simple solutions for those problems not defeating the gained advantages so far. The EF PHB [9] shows also very interesting properties within a multicast context. The very low packet loss characteristic makes it suitable as a basis for a highly (but not absolute) reliable multicast service. Packet loss cannot be fully precluded, because of aggregation effects which may nevertheless lead to packet losses. However, in reality packet losses should occur so infrequently that many applications can tolerate these losses, or if this is not the case, that at least very simple retransmission schemes can be applied. 1.1 Management of Differentiated Services At least for Per-Domain Behaviors [3] and services based on the EF PHB admission control and resource reservation are required. Furthermore, installation and updating of traffic profiles in boundary nodes is necessary. Most network administrators will not accomplish this task manually, even for long term service level agreements (SLAs). Furthermore, offering services on demand requires some kind of signaling and automatic admission control procedures. Therefore, the concept of Bandwidth Brokers was already suggested by Van Jacobson at a very early stage of DiffServ research [4]. In this concept, the Bandwidth Broker (BB) is a dedicated node in each DS domain, which keeps track of the amount of available and reserved bandwidth for services, and, which processes admission control requests from customers or BBs of adjacent domains. Additionally, it installs or alters traffic profiles in boundary nodes. Protocols for signaling a reservation request to a Differentiated Services Domain are required. For accomplishing end-system signaling to DS domains RSVP [5] may be used with new DS specific reservation objects. RSVP is mainly designed for use in multicast scenarios and is already supported by many operating systems. However, when applying RSVP to a DiffServ network some problems will arise which are described in the next section. Bless & Wehrle Expires: September 2002 [Page 3] 2 Problems of IP Multicast in DS Domains Although potential problems and the complexity of providing multicast with Differentiated Services are considered in a separate section of [2], both aspects have to be discussed in greater detail. The simplicity of the DiffServ Architecture and its router models is necessary to reach high scalability, but it causes also fundamental problems in conjunction with the use of IP Multicast in DS domains. Because Differentiated Services are unidirectional by definition, we also consider the point-to-multipoint communication being of unidirectional nature. In traditional IP Multicast any node can send packets spontaneously and asynchronously to a multicast group, respectively to their multicast group address (therefore, traditional IP Multicast offers a multipoint-to-multipoint service). This feature is discussed in section 2.3. For subsequent considerations we assume, unless stated otherwise, at least a unidirectional point-to-multipoint communication scenario in which the sender generates packets which experience a "better" Per- Hop Behavior than the traditional default PHB, resulting in a service of better quality compared to the default best-effort service. In order to accomplish this, a traffic profile corresponding to the traffic conditioning specification has to be installed in the sender's first-hop router (the first boundary node of the first DS domain receiving those packets). Furthermore, it must be assured that the corresponding resources are available on the path from the sender to all the receivers, possibly requiring adaptation of traffic profiles at involved domain boundaries. Note that the latter process may also be initiated on demand of a receiver. 2.1 Neglected Reservation Subtree Problem (NRS Problem) Typically, resources for Differentiated Services must be reserved before actually using them. But in a multicast scenario group membership is often highly dynamic, therefore limiting the use of a sender-initiated resource reservation in advance. Unfortunately, dynamic addition of new members of the multicast group using Differentiated Services can adversely affect existing other traffic, if resources were not explicitly reserved before use. A practical prove of this problem is given in appendix A.3. IP Multicast packet replication usually takes place when the packet is handled by the "routing" core (cf. Fig. 1), i.e., when it is forwarded according to the routing table. Thus, a DiffServ capable node would also copy the content of the DS field [1] into the IP packet header of every replicate. Consequently, replicated packets get exactly the same DS codepoint (DSCP) as the original packet, and, therefore experience the same forwarding treatment as the incoming packets of this multicast group (see Fig. 1, in this case Bless & Wehrle Expires: September 2002 [Page 4] the egress interface comprises functions for (BA-) classification, traffic conditioning and queueing). Interface A IP-Routing Interface C +-----------+ +--------------+ +-----------+ MC-flow | | | replication | | egress | ---->| ingress |---->|------+-------|----->|(class.,TC,|----> | | | | | | queueing) | +-----------+ | | | +-----------+ | | | Interface B | | | Interface D +-----------+ | | | +-----------+ | | | | | | egress | | ingress | | +-------|----->|(class.,TC,|----> | | | | | queueing) | +-----------+ +--------------+ +-----------+ Figure 1: Multicast packet replication in a DS router Normally, the replicating node cannot test whether a corresponding reservation exists for a particular flow of replicated packets on an output link (resp. its corresponding interface), because a flow- specific traffic profile is usually not available in boundary (except in first-hop nodes) and interior nodes. When a new receiver joins an IP Multicast group, the corresponding multicast routing protocol (e.g., DVMRP [6], PIM-DM [7] or PIM-SM [8]) accomplishes that the multicast tree is expanded by a new subtree which connects the new receiver to the already existing multicast tree. As a result of tree expansion and missing per-flow classification and policing mechanisms, the new receiver will implicitly use the service of better quality, because of the copied "better" DSCP. If the additional amount of resources which are consumed by the new part of the multicast tree are not taken into account by the domain management (cf. section 1.1), the currently provided level of quality of service of other receivers (with correct reservations) will be affected adversely or even violated. This negative effect on existing traffic contracts by a neglected resource reservation -- in the following designated as Neglected Reservation Subtree Problem (NRS Problem) -- must be avoided under any circumstances. One can distinguish two distinct major cases of the NRS Problem. In order to compare their different effects a simple example of a share of bandwidth is illustrated in Fig. 2. Bless & Wehrle Expires: September 2002 [Page 5] 40% 40% 20% +--------------------+---------------------+------------+ |Expedited Forwarding| Assured Forwarding | Best-Effort| +--------------------+---------------------+------------+ ----------------------------------------------------------> output link bandwidth Figure 2: An example bandwidth share of different behavior aggregates Three types of services (respectively their corresponding behavior aggregates) share the bandwidth of the considered output link: Expedited Forwarding [9], Assured Forwarding [10] and the traditional Best-Effort service. In this example we assume that routers perform simple priority queueing, where EF has the highest and Best-Effort the lowest assigned priority. When Weighted Fair Queueing (WFQ) would be used, the described effects would essentially also occur, only with minor differences. The Neglected Reservation Subtree problem appears in two different cases: o Case 1: If the branching point of the new subtree and the previous multicast tree is an (egress) border router, as shown in Fig. 3, the additional multicast flow now increases the amount of used resources for the corresponding aggregate and will be greater than the originally reserved amount on the affected output link. Consequently, the policing component in the egress border router drops packets until the traffic aggregate is in accordance to the traffic contract. But during dropping packets, the router can not identify the responsible flow (because of missing flow classification functionality), and, thus randomly discards packets, whether they belong to a correctly reserved flow or not. As a result, there will be no longer any service guarantee for the reserved flows. Bless & Wehrle Expires: September 2002 [Page 6] Sender +---+ | S | DS domains ....... +---+ ..... / \ . .. || . . .. / \ .. . ..||.. .... .<- ->... .. . || . . . . +---+ +--+ +--+ *) +--+ +--+ +--+ +------+ . |FHN|===|IN|=====|BN|###########|BN|####|IN|######|BN|####|Recv.B| . +---+ +--+ +--+\\ +--+ +--+ +--+ +------+ . \\ \ . \\ . \ . . +--+ +--+ . \\ . \ . . |IN|-----|IN| . \\ .. +--+ . . +--+ +--+ . \\ ... ....|BN|.. . || \ ... +------+ ... +--+ . || \ . |Recv.A| .+--+ ...+--+ +------+ |BN|..... |BN| +--+ +--+ || FHN: First-Hop Node S: Sender BN: Boundary Node Recv.x: Receiver x IN: Interior Node ===: Multicast branch with reserved bandwidth ###: Multicast branch without reservation *) Bandwidth of EF aggregated on the output link is higher than actual reservation, EF aggregate will be limited in bandwidth without considering the responsible flow. Figure 3: The NRS Problem (case 1) Bless & Wehrle Expires: September 2002 [Page 7] +------------------+---------------------+--------------+------+ | Expedited Forw. | Expedited Forw. | Assured Forw.| BE | | | | | | | with reservation | excess flow | with reserv. | | | | without reservation | | | +------------------+---------------------+--------------+------+ | | | | | EF with and without reservation share | 40 % | 20% | | 40% of reserved EF aggregate. | | | | -> EF packets with reservation and | | | | without reservation will be | | | | discarded! | | | | | | | +------------------+---------------------+--------------+------+ (a) Excess flow has EF codepoint +------------------+---------------------+--------------+------+ | Expedited Forw. | Assured Forwarding | Assured Forw.| BE | | | | | | | with reservation | excess flow | with reserv. | | | | without reservation | | | +------------------+---------------------+--------------+------+ | | | | | | AF with & without reservation share| 20 % | | | 40% of reserved EF aggregate. | | | 40% | -> EF packets with reservation and | | | | without reservation will be | | | | discarded! | | | | | | +------------------+---------------------+--------------+------+ (b) Excess flow has AF codepoint Figure 4: Resulting share of bandwidth in a egress border router with a neglected reservation of (a) an Expedited Forwarding flow or (b) an Assured Forwarding flow. Fig. 4 shows the resulting share of bandwidth in cases when (a) Expedited Forwarding and (b) Assured Forwarding is used by the additional multicast branch causing the NRS Problem. Assuming that the additional traffic would use another 30% of the link bandwidth, Fig. 4 (a) illustrates that the resulting aggregate of Expedited Forwarding (70% of the outgoing link bandwidth) is throttled down to its originally reserved 40%. In this case, the amount of dropped EF bandwidth is equal to the amount of excess bandwidth. Consequently the original Expedited Forwarding aggregate (which had 40% of the link bandwidth reserved) is affected by packet losses, too. The other services, e.g., Assured Forwarding or Best-Effort, are not disadvantaged. Bless & Wehrle Expires: September 2002 [Page 8] Fig. 4 (b) shows the same situation for Assured Forwarding. The only difference is that now Assured Forwarding is solely affected by discards, the other services will still get their guarantees. In either case, packet losses are restricted to the misbehaving service class by the traffic meter and policing mechanisms in boundary routers. Moreover, the latter problem (case 1) occurs only in egress border routers, because they are responsible, that not more traffic is leaving the Differentiated Services domain, than the following ingress border router will accept. Therefore, those violations of SLAs will be already detected and processed in egress border routers. Sender +---+ | S | DS domains ....... +---+ ..... / \ . .. || . . .. / \ .. . ..||.. .... .<- ->... .. . || . . . . +---+ +--+ +--+ +--+ +--+ +--+ +-------+ . |FHN|===|IN|=====|BN|===========|BN|====|IN|======|BN|===| Recv.B| . +---+ +--+ +--+\\ +--+ +--+ +--+ +-------+ . \\ \ . \\ . # . . +--+ +--+ . \\ . # *) . . |IN|-----|IN| . \\ .. +--+ . . +--+ +--+ . \\ ... ....|BN|.. . || \ ... +------+ ... +--+ . || \ . |Recv.A| # .+--+ ...+--+ +------+ # |BN|..... |BN| +------+ +--+ +--+ |Recv.C| || +------+ FHN: First-Hop Node S: Sender BN: Boundary Node Recv.x: Receiver x IN: Interior Node ===: Multicast branch with reserved bandwidth ###: Multicast branch without reservation *) Bandwidth of EF aggregated on the output link is higher than actual reservation, EF aggregate will be limited in bandwidth without considering the responsible flow Figure 5: Neglected Reservation Subtree problem case 2 after join of receiver C o Case 2: The Neglected Reservation Subtree problem can also occur, if the branching point between the previous multicast tree and the new subtree is located in an interior router (as shown in Fig. 5). Because the router is not equipped with metering or policing functions it will not recognize any amount of excess traffic and will forward the new multicast flow. If the latter belongs to a Bless & Wehrle Expires: September 2002 [Page 9] higher priority service, such as Expedited Forwarding, bandwidth of the aggregate is higher than the aggregate's reservation and will steal bandwidth from lower priority services. The additional amount of EF without a corresponding reservation is forwarded together with the aggregate which has a reservation. This results in no packets losses for Expedited Forwarding as long as the resulting aggregate is not higher than the output link bandwidth. Because of its higher priority, Expedited Forwarding gets as much bandwidth as needed and as is available (strictly speaking, it is implementation dependent whether interior routers have something like a maximum configured service rate). +------------------+---------------------+--------------+------+ | Expedited Forw. | Expedited Forw. | Assured Forw.| BE | | | | | | | with reservation | excess flow | with reserv. | | | | without reservation | | | +------------------+---------------------+--------------+------+ | | | | | | 40% | 30% | 30% | 0% | | | | | | +------------------+---------------------+--------------+------+ EF with reservation and the excess flow use together 70% of the link bandwidth, because EF (with or without reservation has the highest priority. (a) Excess flow has EF codepoint +------------------+---------------------+--------------+------+ | Expedited Forw. | Assured Forw. | Assured Forw.| BE | | | | | | | with reservation | excess flow | with reserv. | | | | without reservation | | | +------------------+---------------------+--------------+------+ | | | | | 40% | 60% | 0% | | | | | | | 10% loss | | | | | | +------------------+---------------------+--------------+------+ AF with reservation and the excess flow use together 60% of the link bandwidth, because EF has the highest priority (-> 40%). 10% of AF packets will be lost. (b) Excess flow has AF codepoint Figure 6: Resulting share of bandwidth in an interior router with a neglected reservation of (a) a Expedited Forwarding flow or (b) an Assured Forwarding flow Bless & Wehrle Expires: September 2002 [Page 10] The result is, that there is no restriction for Expedited Forwarding, but as Fig. 6 (a) shows, other services will be extremely disadvantaged by this use of non-reserved resources. Their bandwidth is stolen by the new additional flow. In this case, the additional 30% Expedited Forwarding traffic preempts resources from the Assured Forwarding traffic, which in turn preempts resources from the best-effort traffic, resulting in 10% packet losses for the Assured Forwarding aggregate and complete loss of best-effort traffic. The example in Fig. 6 (b) shows that this can also happen with lower priority services like Assured Forwarding. When a reservation for a service flow with lower priority is neglected, other services (with even lower priority) can be reduced in their quality (in this case the best-effort service). As shown in the example, the service's aggregate causing the problem can itself be affected by packet losses (10% of the Assured Forwarding aggregate is discarded). Besides the described problems of case 2, case 1 will arise in the next border router, that performs traffic metering and policing for flows of the service aggregate. Directly applying RSVP to Differentiated Services would also result in an NRS Problem, because a receiver has to join the IP multicast group BEFORE sending a resource reservation request (RESV message), in order to receive the sender's PATH messages at first. Thus, the join for receiving PATH messages will already cause an NRS Problem if this situation is not handled in a special way (e.g., by marking all PATH messages with codepoint 0). 2.2 Heterogeneous Multicast Groups Heterogeneous multicast groups contain one or more receivers, which would like to get another service or quality of service as the sender provides or other receiver subsets currently use. A very important characteristic which should be supported by Differentiated Services is that participants requesting a best-effort quality only should also be able to participate in a group communication which otherwise utilizes a better service class. The next better support for heterogeneity provides concurrent use of more than two different service classes within a group. Things tend to get even more complex when not only different service classes are required, but also different values for quality parameters within a certain service class. A further problem is to support heterogeneous groups with different service classes in a consistent way. It is possible that some services will not be comparable to each other so that one service cannot be replaced by the other and both services have to be provided over the same link within this group. Because an arbitrary new receiver that wants to get the different service can be grafted to any point of the current multicast Bless & Wehrle Expires: September 2002 [Page 11] delivery tree, even interior routers may have to replicate packets with the different service. At a first glance, this seems to be a contradiction with respect to simplicity of the interior routers, because they do not even have any profile available and should now convert the service quality of individual receivers. Consequently, in order to accomplish this, interior routers have to change the codepoint value during packet replication. 2.3 Dynamics of Arbitrary Sender Change Basically, within an IP multicast group any participant (actually, it can be any host not even receiving packets of this multicast group) can act as a sender. This is an important feature which should also be available in case a specific service other than best- effort is used within the group. Differentiated Services possess conceptually a unidirectional character. Therefore, for every multicast tree implied by a sender resources must be reserved separately if simultaneous sending should be possible with a better service. This is even true if shared multicast delivery trees are used (e.g., with PIM-SM or Core Based Trees). If not enough resources are reserved for a service within a multicast tree allowing simultaneous sending of more than one participant, the NRS problem will occur again. The same argument applies to half-duplex traffic which would share the reserved resources by several senders, because it cannot be ensured by the network that exactly one sender sends packets to the group. Accordingly, the corresponding RSVP reservation styles "Wildcard Filter" and "Shared-Explicit Filter" [5] cannot be supported within Differentiated Services. The IntServ approach is able to ensure the half-duplex nature of the traffic, because every router can check each packet for conformance with the installed reservation state. 3 Requirements to Enable Provisioning of IP-Multicast in Differentiated Services Networks The problems described in the previous section are mainly caused by the simplicity of the Differentiated Services Architecture. Solutions have to be developed which do not introduce an additional amount of complexity which diminishes the scalability of the DiffServ approach. An example for such a solution is given in [12], although many other approaches may be possible and feasible. 4 Security Considerations Basically, the security considerations in [1,2] apply. If it is not desired that arbitrary end-systems can join a multicast group anytime the application has usually to preclude these participants by using authentication, authorization or ciphering techniques at application level just as for traditional IP multicast scenarios. Bless & Wehrle Expires: September 2002 [Page 12] 5 References [1] F. Baker, D. Black, S. Blake, and K. Nichols. Definition of the Differentiated Services Field (DS Field) in the IPv4 and IPv6 Headers. RFC 2474, Dec. 1998. [2] S. Blake, D. Black, M. Carlson, E. Davies, Z. Wang, and W. Weiss. An Architecture for Differentiated Services. RFC 2475, Dec. 1998. [3] K. Nichols, B. Carpenter. Definition of Differentiated Services Per Domain Behaviors and Rules for their Specification. RFC 3086, Apr. 2001. [4] V. Jacobson, K. Nichols, and L. Zhang. A Two-bit Differentiated Services Architecture for the Internet. RFC 2638, July 1999. [5] R. Braden, S. Berson, S. Herzog, S. Jamin, and L. Zhang. Resource ReSerVation Protocol (RSVP) -- Version 1. RFC 2205, Sept. 1997. [6] D. Waitzman, C. Partridge, and S. Deering. Distance Vector Multicast Routing Protocol. RFC 1075, Nov. 1988. [7] S. Deering, D. Estrin, D. Farinacci, V. Jacobson, A. Helmy, D. Meyer, and L. Wei. Protocol independent multicast version 2 dense mode specification. Internet-Draft -- draft-ietf-pim-v2- dm-03.txt, June 1999, work in progress. [8] D. Estrin, D. Farinacci, A. Helmy, D. Thaler, S. Deering, M. Handley, V. Jacobson, C. gung Liu, P. Sharma, and L. Wei. Protocol Independent Multicast-Sparse Mode (PIM-SM): Protocol Specification. RFC 2362, June 1998. [9] V. Jacobson, K. Nichols, and K. Poduri. An Expedited Forwarding PHB. RFC 2598, June 1999. [10] F. Baker, J. Heinanen, W. Weiss, and J. Wroclawski. Assured Forwarding PHB Group. RFC 2597, June 1999. [11] R. Bless, K. Wehrle: "Evaluation of Differentiated Services using an Implementation und Linux"; Proceedings of the Intern. Workshop on Quality of Service (IWQOS'99), London, 1999 [12] R. Bless, K. Wehrle. Group Communication in Differentiated Services Networks, Internet QoS for the Global Computing 2001 (IQ 2001), IEEE International Symposium on Cluster Computing and the Grid), May 2001, Brisbane, Australia, IEEE Press Bless & Wehrle Expires: September 2002 [Page 13] [13] K. Wehrle, J. Reber, V. Kahmann. A simulation suite for Internet nodes with the ability to integrate arbitrary Quality of Service behavior, Proceedings of Communication Networks And Distributed Systems Modeling And Simulation Conference (CNDS 2001), Phoenix (AZ), January 2001 6 Acknowledgements The authors like to thank all the people from the Institute of Telematics (University of Karlsruhe) and those from the DiffServ community which contributed to the discussion of all the topics related to this document. Special thanks go to Milena Neumann for the extensive efforts in performing the simulations. We would also like to thank the KIDS simulation team [13]. 7 Authors' Addresses Comments and questions related to this document can be addressed to one of the authors listed below. Roland Bless Institute of Telematics Universitaet Karlsruhe (TH) Zirkel 2 D-76128 Karlsruhe, Germany Phone: +49 721 608 6413 Email: bless@tm.uka.de Klaus Wehrle Institute of Telematics Universitaet Karlsruhe (TH) Zirkel 2 D-76128 Karlsruhe, Germany Phone: +49 721 608 6414 Email: wehrle@tm.uka.de Bless & Wehrle Expires: September 2002 [Page 14] Appendix A Proof of the Neglected Reservation Subtree Problem In the following, it is shown that the NRS problem actually exists and occurs in reality. Hence, we investigated the problem and its solution using a standard Linux Kernel (v2.3.49) and the Linux-based implementation KIDS, which is described in an early version detailed in [11]. Additional measurements with the simulation model simulatedKIDS [13] will be presented in appendix B. They show the effects of the NRS problem, too. A.1 Test Environment and Execution Sender +---+ FHN: First Hop Node | S | BN: Border Node +---+ +# +# +# +---+ +--+ +------+ |FHN|++++++++++++|BN|+++++++++++| host | | |############| |***********| B | +---+ +--+## +------+ +# # +# # +# # +------+ +------+ |host A| |host C| +------+ +------+ +++ EF flow (group1) with reservation ### EF flow (group2) with reservation *** EF flow (group2) without reservation Figure A.1: Evaluation of NRS-Problem described in Figure 3 In order to prove NRS problem case 1, as described in section 2.1, a testbed shown in Figure A.1 was built. It is a reduced version of the network shown in Figure 5 and consists of two DS-capable routers, a first-hop router and an egress border router. The absence of interior routers does not have any effects on to the proof of the described problem. Bless & Wehrle Expires: September 2002 [Page 15] The testbed comprises of two Personal Computers (Pentium III at 450 Mhz, 128 MB Ram, 3 network cards Intel eepro100) used as DiffServ routers, as well as one sender and three receiver systems (also PCs). KIDS has been installed on the routers and an mrouted (Multicast Routing Daemon) was used to perform multicast routing. The network was completely built of separate 10BaseT Ethernet segments in full-duplex mode. In [13] we evaluated the performance of the software routers and found out that even a PC at 200Mhz had no problem to handle up to 10Mbps DS traffic on each link. Therefore, the presented measurements are not a result of performance bottlenecks caused by these software routers. The sender generated two shaped UDP traffic flows of 500kbps (packets of 1.000 byte constant size) each and sends them to multicast group 1 (233.1.1.1) and 2 (233.2.2.2). In both measurements receiver A had a reservation along the path to the sender for each flow, receiver B has reserved for flow 1 and C for flow 2. Therefore, two static profiles are installed in the first- hop router with 500kbps EF bandwidth and a token bucket size of 10.000byte for each flow. In the egress border router one profile has been installed for the output link to host B and one related for the output link to host C. Each of them permits up to 500kbps Expedited Forwarding, but only the aggregate of Expedited Forwarding traffic carried on the outgoing link is considered. In the measurement scenario of Figure A.2 hosts A and B joined to group 1 and A, B and C joined to group 2. Those joins are using a reservation for the group towards the sender. Only the join of host B to group 2 has no admitted reservation. As described in section 2.1 this will cause the NRS problem (case 1). Metering and policing mechanisms in the egress border router throttle down the EF aggregate to the reserved 500kbps, no depending on whether individual flows have reserved or not. +--------+--------+--------+ | Host A | Host B | Host C | +---------+--------+--------+--------+ | Group 1 | 500kbps| 250kbps| 500kbps| +---------+--------+--------+--------+ | Group 2 | 500kbps| 250kbps| | +---------+--------+--------+--------+ Figure A.2: Average bandwidth of each flow. --> Flows of group 1 and 2 on the link to host B share the reserved aggregate of group 1. Figure A.2 shows the obtained results. Host A and C received their flows without any interference. But host B received data from group 1 only with half of the reserved bandwidth, so one half of the Bless & Wehrle Expires: September 2002 [Page 16] packets have been discarded. Figure A.2 also shows that receiver B got the total amount of bandwidth for group 1 and 2, that is exactly the reserved 500kbps. Flow 2 got Expedited Forwarding without actually having reserved any bandwidth and additionally violated the guarantee of group 1 on that link. The above measurements confirm that the Neglected Reservation Subtree problem is to be taken seriously in practice. B Simulative Study of the NRS Problem This section shows some results from a simulative study which shows the described problems. A further proof of the NRS problem has also been given in appendix A and in [12]. B.1 Simulation Scenario In the following scenario Border Routers had a link speed of 10 Mpbs and Interior Routers had a link speed of 12 Mbps. In Border Routers a 5 Mbps aggregate for EF has been reserved. The following topology was used, where Sx is a sender, BRx a Border Router, IRx an Interior Router and Dx a destination/receiver. +--+ +--+ +---+ +--+ |S1| |S0| /=|BR5|=====|D0| +--+ +--+ // +---+ +--+ \\ || // \\ || // +--+ \+---+ +---+ +---+ +---+ +--+ |S2|===|BR1|=====|IR1|=====|IR2|======|BR3|=====|D1| +--+ +---+ /+---+ +---+ +---+ +--+ // \\ +--+ // \\ /=|D2| +--+ +---+ // \\ // +--+ |S3|===|BR2|=/ +---+/ +--+ +---+ /=|BR4|=\ || +--+ // +---+ \\ +--+ +--+ |D4|=/ \=|D3| |S4| +--+ +--+ +--+ Figure B.1: Simulation Topology The following table shows the flows in the simulation runs, e.g., EF0 is sent from Sender S0 to Destination D0 with a rate of 4 Mbps using an EF reservation. In the presented cases (I to IV) different amounts of BE traffic were used. In all simulation models EF sources generated constant rate traffic with constant packet sizes using UDP. Bless & Wehrle Expires: September 2002 [Page 17] The BE sources also generated constant rate traffic, where BE0 used UDP and BE1 used TCP as transport protocol. +----+--------+-------+----------+-----------+-----------+---------+ |Flow| Source | Dest. | Case I | Case II | Case III | Case IV | +----+--------+-------+----------+-----------+-----------+---------+ | EF0| S0 | D0 | 4 Mbps | 4 Mbps | 4 Mbps | 4 Mbps | +----+--------+-------+----------+-----------+-----------+---------+ | EF1| S1 | D1 | 2 Mbps | 2 Mbps | 2 Mbps | 2 Mbps | +----+--------+-------+----------+-----------+-----------+---------+ | EF2| S2 | D2 | 5 Mbps | 5 Mbps | 5 Mbps | 5 Mbps | +----+--------+-------+----------+-----------+-----------+---------+ | BE0| S3 | D3 | 1 Mbps | 2.25 Mbps | 0.75 Mbps |3.75 Mbps| +----+--------+-------+----------+-----------+-----------+---------+ | BE1| S4 | D4 | 4 Mbps | 2.25 Mbps | 0.75 Mbps |3.75 Mbps| +----+--------+-------+----------+-----------+-----------+---------+ Table B.1: Direction, amount and PHB of flows in the four simulation cases (case I to IV) The four cases (I to IV) used in the simulation runs had the following characteristics: Case I: In this scenario, the BE sources sent together exactly 5 Mbps so there is no congestion in the BE queue. Case II: BE0 and BE1 are sending together 4.5 Mbps, so there is residual bandwidth available. Case III: In this case, BE0 and BE1 use together only 1.5 Mbps. Case IV: BE0 and BE1 send together 7.5 Mbps so there is congestion in the BE queue. In each scenario loss rate and throughput of the considered flows and aggregates have been metered. B.2 Simulation Results for different router types B.2.1 Interior Router When the branching point of a newly added multicast subtree is located in an Interior Router the NRS problem can occur as described in section 2.1 (Case 2). In the simulation runs presented in the following four subsections D3 joins to the multicast group of sender S0 without making any reservation or resource allocation. Consequently, a new subtree is added to the existing multicast tree. The branching point issued by Bless & Wehrle Expires: September 2002 [Page 18] the join of D3 is located in IR2. On the link to BR3 no bandwidth was allocated for the new flow (EF0). The metered throughput of flows on the link between IR2 and BR3 in the four different cases is shown in the following four subsections. The situation before the new receiver joins is shown in the second column. The situation after the join of D3 is shown in column three. A.1.1.1 Case I: +--------+-----------------+-----------------+ | | before join | after join | | | | | +--------+-----------------+-----------------+ | | EF0: --- | EF0: 4.007 Mbps | |achieved| EF1: 2.001 Mbps | EF1: 2.003 Mbps | |through-| EF2: 5.002 Mbps | EF2: 5.009 Mbps | |put | BE0: 1.000 Mbps | BE0: 0.601 Mbps | | | BE1: 4.000 Mbps | BE1: 0.399 Mbps | +--------+-----------------+-----------------+ |BA | EF: 7.003 Mbps | EF: 11.019 Mbps | |through-| BE: 5.000 Mbps | BE: 1.000 Mbps | |put | | | +--------+-----------------+-----------------+ | | EF0: --- | EF0: 0 % | |packet | EF1: 0 % | EF1: 0 % | |loss | EF2: 0 % | EF2: 0 % | |rate | BE0: 0 % | BE0: 34.8 % | | | BE1: 0 % | BE1: 59.1 % | +--------+-----------------+-----------------+ A.1.1.2 Case II: +--------+-----------------+-----------------+ | | before join | after join | | | | | +--------+-----------------+-----------------+ | | EF0: --- | EF0: 4.003 Mbps | |achieved| EF1: 2.000 Mbps | EF1: 2.001 Mbps | |through-| EF2: 5.002 Mbps | EF2: 5.005 Mbps | |put | BE0: 2.248 Mbps | BE0: 0.941 Mbps | | | BE1: 2.252 Mbps | BE1: 0.069 Mbps | +--------+-----------------+-----------------+ |BA | EF: 7.002 Mbps | EF: 11.009 Mbps | |through-| BE: 4.500 Mbps | BE: 1.010 Mbps | |put | | | +--------+-----------------+-----------------+ | | EF0: --- | EF0: 0 % | |packet | EF1: 0 % | EF1: 0 % | |loss | EF2: 0 % | EF2: 0 % | |rate | BE0: 0 % | BE0: 58.0 % | | | BE1: 0 % | BE1: 57.1 % | +--------+-----------------+-----------------+ Bless & Wehrle Expires: September 2002 [Page 19] A.1.1.3 Case III: +--------+-----------------+-----------------+ | | before join | after join | | | | | +--------+-----------------+-----------------+ | | EF0: --- | EF0: 3.998 Mbps | |achieved| EF1: 2.000 Mbps | EF1: 2.001 Mbps | |through-| EF2: 5.000 Mbps | EF2: 5.002 Mbps | |put | BE0: 0.749 Mbps | BE0: 0.572 Mbps | | | BE1: 0.749 Mbps | BE1: 0.429 Mbps | +--------+-----------------+-----------------+ |BA | EF: 7.000 Mbps | EF: 11.001 Mbps | |through-| BE: 1.498 Mbps | BE: 1.001 Mbps | |put | | +--------+-----------------+-----------------+ | | EF0: --- | EF0: 0 % | |packet | EF1: 0 % | EF1: 0 % | |loss | EF2: 0 % | EF2: 0 % | |rate | BE0: 0 % | BE0: 19.7 % | | | BE1: 0 % | BE1: 32.6 % | +--------+-----------------+-----------------+ A.1.1.4 Case IV: +--------+-----------------+-----------------+ | | before join | after join | | | | | +--------+-----------------+-----------------+ | | EF0: --- | EF0: 4.001 Mbps | |achieved| EF1: 2.018 Mbps | EF1: 2.000 Mbps | |through-| EF2: 5.005 Mbps | EF2: 5.001 Mbps | |put | BE0: 2.825 Mbps | BE0: 1.000 Mbps | | | BE1: 2.232 Mbps | BE1: --- | +--------+-----------------+-----------------+ |BA | EF: 7.023 Mbps | EF: 11.002 Mbps | |through-| BE: 5.057 Mbps | BE: 1.000 Mbps | |put | | | +--------+-----------------+-----------------+ | | EF0: --- | EF0: 0 % | |packet | EF1: 0 % | EF1: 0 % | |loss | EF2: 0 % | EF2: 0 % | |rate | BE0: 23.9 % | BE0: 73.3 % | | | BE1: 41.5 % | BE1: --- | +--------+-----------------+-----------------+ NOTE: BE1 has undefined throughput and loss in situation "after join", because TCP is going into retransmission back-off timer phase and closes the connection after 512 seconds. Bless & Wehrle Expires: September 2002 [Page 20] A.1.1.5 Summary The effects occur as described in Case 2 of section 2.1: in this particular case (branching point at interior router), the existing BE aggregates are affected adversely by the new EF receiver. B.2.2 Border Router When the branching point of a newly added multicast subtree is located in a Border Router the NRS problem can occur as described in section 2.1 (Case 1). In the simulation runs presented in the following four subsections D3 joins to the multicast group of sender S1 without making any reservation or resource allocation. Consequently, a new subtree is added to the existing multicast tree. The branching point issued by the join of D3 is located in BR3. On the link to BR4 no bandwidth was allocated for the new flow (EF1). The metered throughput of the flows on the link between BR3 and BR4 in the four different cases is shown in the following four subsections. The situation before the new receiver joins is shown in the second column. The situation after the join is shown in column three. A.1.1.6 Case I: +--------+-----------------+-----------------+ | | before join | after join | | | | | +--------+-----------------+-----------------+ | | EF0: --- | EF0: --- | |achieved| EF1: --- | EF1: 1.489 Mbps | |through-| EF2: 5.002 Mbps | EF2: 3.512 Mbps | |put | BE0: 1.000 Mbps | BE0: 1.000 Mbps | | | BE1: 4.000 Mbps | BE1: 4.002 Mbps | +--------+-----------------+-----------------+ |BA | EF: 5.002 Mbps | EF: 5.001 Mbps | |through-| BE: 5.000 Mbps | BE: 5.002 Mbps | |put | | | +--------+-----------------+-----------------+ | | EF0: --- | EF0: --- | |packet | EF1: --- | EF1: 25.6 % | |loss | EF2: 0 % | EF2: 29.7 % | |rate | BE0: 0 % | BE0: 0 % | | | BE1: 0 % | BE1: 0 % | +--------+-----------------+-----------------+ Bless & Wehrle Expires: September 2002 [Page 21] A.1.1.7 Case II: +--------+-----------------+-----------------+ | | before join | after join | | | | | +--------+-----------------+-----------------+ | | EF0: --- | EF0: --- | |achieved| EF1: --- | EF1: 1.520 Mbps | |through-| EF2: 5.003 Mbps | EF2: 3.482 Mbps | |put | BE0: 2.249 Mbps | BE0: 2.249 Mbps | | | BE1: 2.252 Mbps | BE1: 2.252 Mbps | +--------+-----------------+-----------------+ |BA | EF: 5.003 Mbps | EF: 5.002 Mbps | |through-| BE: 4.501 Mbps | BE: 4.501 Mbps | |put | | | +--------+-----------------+-----------------+ | | EF0: --- | EF0: --- | |packet | EF1: --- | EF1: 24.0 % | |loss | EF2: 0 % | EF2: 30.4 % | |rate | BE0: 0 % | BE0: 0 % | | | BE1: 0 % | BE1: 0 % | +--------+-----------------+-----------------+ A.1.1.8 Case III: +--------+-----------------+-----------------+ | | before join | after join | | | | | +--------+-----------------+-----------------+ | | EF0: --- | EF0: --- | |achieved| EF1: --- | EF1: 1.084 Mbps | |through-| EF2: 5.001 Mbps | EF2: 3.919 Mbps | |put | BE0: 0.749 Mbps | BE0: 0.752 Mbps | | | BE1: 0.749 Mbps | BE1: 0.748 Mbps | +--------+-----------------+-----------------+ |BA | EF: 5.001 Mbps | EF: 5.003 Mbps | |through-| BE: 1.498 Mbps | BE: 1.500 Mbps | |put | | | +--------+-----------------+-----------------+ | | EF0: --- | EF0: --- | |packet | EF1: --- | EF1: 45.7 % | |loss | EF2: 0 % | EF2: 21.7 % | |rate | BE0: 0 % | BE0: 0 % | | | BE1: 0 % | BE1: 0 % | +--------+-----------------+-----------------+ Bless & Wehrle Expires: September 2002 [Page 22] A.1.1.9 Case IV: +--------+-----------------+-----------------+ | | before join | after join | | | | | +--------+-----------------+-----------------+ | | EF0: --- | EF0: --- | |achieved| EF1: --- | EF1: 1.201 Mbps | |through-| EF2: 5.048 Mbps | EF2: 3.803 Mbps | |put | BE0: 2.638 Mbps | BE0: 2.535 Mbps | | | BE1: 2.379 Mbps | BE1: 2.536 Mbps | +--------+-----------------+-----------------+ |BA | EF: 5.048 Mbps | EF: 5.004 Mbps | |through-| BE: 5.017 Mbps | BE: 5.071 Mbps | |put | | | +--------+-----------------+-----------------+ | | EF0: --- | EF0: --- | |packet | EF1: --- | EF1: 40.0 % | |loss | EF2: 0 % | EF2: 23.0 % | |rate | BE0: 30.3 % | BE0: 32.1 % | | | BE1: 33.3 % | BE1: 32.7 % | +--------+-----------------+-----------------+ A.1.1.10 Summary The effects occur as described in Case 1 of section 2.1: in this particular case (branching point at border router), the existing EF aggregates are affected adversely by the new EF receiver. Bless & Wehrle Expires: September 2002 [Page 23]