INTERNET DRAFT Ali Boudani Expires: April 2005 Alexandre Guitton Bernard Cousin IRISA-France October 2004 GXcast: Generalized Explicit Multicast Routing Protocol Status of this Memo By submitting this Internet-Draft, I certify that any applicable patent or other IPR claims of which I am aware have been disclosed, or will be disclosed, and any of which I become aware will be disclosed, in accordance with RFC 3668." Internet Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and 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 obsolete by other documents at anytime. It is inappropriate to use Internet Drafts as reference material or to cite them other than as "work in progress." The list of current Internet-Drafts can be accessed at http://www.ietf.org/ietf/1id-abstracts.txt. The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html. Abstract Recently several multicast mechanisms were proposed that scale better with the number of multicast groups than traditional multicast does. These proposals are known as small group multicast (SGM) or explicit multicast (Xcast). Explicit multicast protocols, such as the Xcast protocol, encode the list of group members in the Xcast header of every packet. If the number of members in a group increases, routers may need to fragment an Xcast packet. Fragmented packets may not be identified as Xcast packets by routers. In this paper, we show that the Xcast protocol does not support the IP fragmentation and we show also that avoiding fragmentation induces hard-coded limits inside the protocol itself in terms of group size. First, we describe the Xcast protocol, the Xcast+ protocol (which is an extension of Xcast) and we compare these two protocols with traditional multicast protocols.We propose then a generalized version of the Xcast protocol, called GXcast, intended to permit the Xcast packets fragmentation and to support the increasing in the number of members in a multicast group. I. INTRODUCTION Boudani et al. [Page 1] INTERNET-DRAFT GXcast October 2004 Multicast, the ability to efficiently send data to a group of destinations, has become increasingly important with the emergence of network-based applications like IP telephony, videoconferencing, distributed interactive simulation and software upgrading. A multicast routing protocol should be simple to implement, scalable, robust, use minimal network overhead consume minimal memory resources , and inter-operate with other multicast routing protocols. Most of proposed multicast protocols like DVMRP [1] and MOSPF ([2], [3]) perform well if group members are densely packed. However, the fact that DVMRP periodically floods the network and the fact that MOSPF sends group membership information over the links, make these protocols not efficient in cases where group members are sparsely distributed among regions and the bandwidth is not plentiful. To address these issues, the Protocol Independent Multicast (PIM) routing protocols are being developed by the Inter-Domain Multicast Routing (IDMR), working group of the IETF. PIM contains two protocols: PIM-Dense Mode (PIMDM) [4] which is more efficient with applications where group members are densely distributed, and PIM-Sparse Mode (PIM-SM) [5] which performs better with applications where group members are sparsely distributed. Although these two protocols share similar control messages, they are essentially proposed for two different kinds of applications. Today's multicast protocols [6] can be used to minimize bandwidth consumption, but it suffers from a scalability problem with the number of concurrently active multicast groups because it requires a router to keep a forwarding state for every multicast tree passing through it and the number of forwarding states grows with the number of groups. There seem to be two kinds of multicast that are important: a broadcast- like multicast that sends data to a large number of destinations and a narrowcast multicast that sends data to a fairly small group. An example of the first kind of multicast is the audio and video multicasting of a presentation to all employees in a corporate intranet. An example of the second kind of multicast is a videoconference involving three or four parties [6]. Thus, a one-size-fits-all protocol will be unable to meet the requirements of all applications [7]. Providing for many groups of small conferences (a small number of widely dispersed people) with global topological scope scales badly given the current multicast model [8]. Recently several multicast mechanisms were proposed that scale better with the number of multicast groups than traditional multicast does. These proposals are known as small group multicast (SGM) [9] or explicit multicast (Xcast) [10]. Explicit multicast protocols, such as the Xcast protocol, encode the list of group members in the Xcast header of every packet. Xcast assumes that there is no packet fragmentation. However, if fragmentation occurs (e.g. if the group size or the data is too large) the fragmented packets will not be identified as Xcast packets by routers. In this paper we propose a generalized Xcast protocol to support the group size increasing and to overcome the fragmentation problem. II. THE XCAST AND THE XCAST+ PROTOCOLS To solve the problems of traditional multicast protocols, Boivie et Boudani et al. [Page 2] INTERNET-DRAFT GXcast October 2004 al. propose the Explicit Multicast protocol (Xcast). A. The Xcast protocol The Xcast protocol is a newly proposed multicast protocol to support a very large number of small multicast groups. To send data to a given group, the source first explicitly encodes the list of destinations in the Xcast header of the packet. Then, the source parses the header, partitions the destinations based on each next unicast hop and forwards a packet with an appropriate header to each of the next hops. Each router along the path to destinations repeats the same processing on receiving an Xcast packet. If a router detects that there is only one destination in the destination list of a packet, the packet is converted to unicast. The algorithm realizing the conversion of an Xcast packet to a unicast packet is called Xcast-to-Unicast (X2U). This packet is then forwarded in unicast along the remainder of the route. B. The Xcast+ protocol Xcast+ is an extension of Xcast for a more efficient delivery of multicast packets [11]. Every source or destination is associated to a Designated Router (DR). Instead of encoding in the Xcast packet header the set of group members, Xcast+ encodes the set of their DRs. When a new member wants to join the group G of source S, it sends an IGMP-join message [12] to its DR. The DR will send a join-request message to the source S. The DR of the source intercepts this message and analyzes it in order to keep track of all concerned DR addresses. When the source S wants to send a message to the group G, it sends a multicast packet. This packet is received by its DR and converted to an Xcast packet using the Multicast-to-Xcast algorithm (M2X). The packet is then forwarded as in Xcast to the DRs, since the destination list in the Xcast header contains the DR addresses instead of the member addresses. Then, each DR converts the Xcast packet to a multicast packet using the Xcast-to-Multicast protocol (X2M) and sends it in its subnetworks. C. The IP fragmentation mechanism Due to physical reasons, every link can transfer only a limited volume of information in each packet. The Internet protocol (IP) [13] contains a mechanism called fragmentation which makes this limitation transparent for end stations. The fragmentation mechanism allows a packet to be cut into fragments in order to be suitably transferred on a link. Suppose that a router receives a packet. After having decided on which link this packet should be forwarded, the router checks the maximum capacity of this link which is the Maximum Transmission Unit (MTU). If the packet is too large and unless it is explicitly forbidden, the router cuts out it in order to respect the following constraints: each resulting fragment is an autonomous IP packet, with a valid IP header, each resulting fragment has a size less than or equal to the MTU, the Boudani et al. [Page 3] INTERNET-DRAFT GXcast October 2004 data is distributed between the fragments. The algorithm used to fragment IPv4 packets is explained in [13]. The IPv6 protocol also have a fragmentation mechanism, described in [14]. Note that one goal of IPv6 is to avoid the fragmentation. This will be discussed later. D. Xcast packet fragmentation Since the Xcast packet header may be large, two cases can be considered: either the whole Xcast packet header is short enough to be kept in the first fragment, or the Xcast header has to be cut out. In both cases, the second fragment is not a valid Xcast packet since it has no Xcast header. Thus, these packets cannot be forwarded to receivers and the data they contain is lost. Moreover, in the second case the first fragment contains only a subset of receivers and no data. The first fragment may however be forwarded up to the mentioned receivers, inducing meaningful traffic. These problems show that the fragmentation of an Xcast packet should be forbidden. This can be done in IPv4 by setting the appropriate flag (Don't Fragment, DF) in the IP header. In order to reach the receivers, the source has to limit the size of its packets to 576 bytes which is the minimum MTU guaranteed by IPv4 on any link. This size limits the number of receivers in an Xcast group to 134. In IPv6, since the minimum MTU is 1280 bytes and since IPv6 addresses are stored using 16 bytes, the limit in the size of the Xcast group is 76. Having these limits hardly coded in protocols is restrictive. What we propose is a simple mechanism to cancel these limitations in the size of Xcast groups. The performance and the scalability of our proposition will be analyzed. E. Comparison between explicit multicast protocols and traditional multicast protocols Traditional multicast protocols and explicit multicast protocols are two different approaches designed to handle multicast groups. We will try to emphasis the main advantages of each method, compared to the other one. 1) Drawbacks of explicit multicast protocols: In addition to the important Xcast packet fragmentation problem, other related drawbacks also exist. a) Limited payload: packet size is limited as a result of network MTU. In explicit multicast protocols, the larger the list of destinations is, the lower the payload is.As a consequence, more packets should be generated to transmit a given amount of data. b) Complex header processing: in explicit multicast protocols, each destination in the header needs a routing table lookup. A packet with destinations in the list of destinations will require n+1 unicast routing table lookups1. Additionally, a different header has to be constructed per next hop. However, it can be noticed that since such protocols are typically designed for sparse sessions, there will be a limited number of branching routers compared to non-branching routers. The construction of different headers only occurs in branching points. The header construction can moreover be reduced Boudani et al. [Page 4] INTERNET-DRAFT GXcast October 2004 to a simple operation: the modification of a bitmap. 2) Advantages of explicit multicast protocols: Explicit multicast protocols make easier the routing of multicast packets. It has many advantages over traditional multicast protocols. a) Routing state and signalisation messages management: in explicit multicast protocols, routers do not have to maintain a state per group. Indeed, there is no multicast forwarding table since only unicast tables are used. This makes the Xcast protocol very scalable in terms of the number of groups that can be supported simultaneously since the routers in the network do not need to disseminate information for the groups. b) Automatic reaction to unicast reroutes and simplified traffic engineering: explicit multicast protocols react immediately to unicast route changes. Traditional multicast protocols need to exchange information with unicast protocols in order to have an adequate reaction. This is achieved on a polling basis in many implementations, yielding a slower reaction to e.g. link failures. This delay may also depend on the number of concerned groups. Additionnaly, there is no need for a specific multicast traffic engineering tool since packets follow traffic engineered unicast paths. c) Easier security and accounting: in explicit multicast protocols, the source has a complete knowledge about members (or about DR members). It will be able to drop dynamically some members and a border router can be able to determine approximately how many times a packet will be duplicated in its domain (especially when link-state protocols like OSPF [15] are used in the domain). Other advantages can be mentionned: No multicast address allocation is needed except eventually in the DR of the source in the case of the Xcast+ protocol. Shortest path is always used even in an asymmetric network. III. THE GXCAST PROTOCOL As explained in the previous section, the Xcast protocol can not support large groups due to its incompatibility with the IP fragmentation mechanism. In this section, we propose a generalized Xcast routing protocol, the GXcast protocol, which is designed basically to avoid the fragmentation. Moreover, the GXcast protocol can be parameterized in order to improve the Xcast behaviour. A. The GXcast protocol The GXcast protocol [18] is a simple generalized version of the Xcast protocol: instead of sending a message to the destinations, the source limits the number of destinations in a packet to nM. Thus, the list of destinations is cutted into sub-lists of at most nM destinations. Each sub-list corresponds to a destination list for an Xcast packet. Several packets may have to be sent in order to Boudani et al. [Page 5] INTERNET-DRAFT GXcast October 2004 deliver data to all the destinations. is the parameter of the GXcast protocol and it impacts the protocol performance in terms of several criteria. GXcast packets are similar to Xcast packets: they have the same header and are treated in the same way by intermediate routers, DR destinations and destinations. The only difference between the Xcast protocol and the GXcast protocol is done in the source or in the DR of the source. The Xcast protocol and the GXcast protocol can therefore inter-operate easily. B. Study of the GXcast parameter The behaviour of the GXcast protocol greatly depends on the value of the parameter. Indeed, as we will see in this subsection, there is a number of criteria that are directly influenced by the chosen value. In the following, we will denote by MTU the value of the MTU which depends on the IP version used, by E the size of the header plus the size of the Xcast header (typically 16 bytes) and by IP the size of an IP address. n will represent the number of destinations in the group and d the volume in bytes of data to transfer. 1) Simple behaviour: Since a packet has to contain at least one byte of data, the maximum number of destinations n_max allowed in an Xcast packet is defined as: The values n_max = 134 and n_max = 76 correspond respectively to the IPv4 and to the IPv6 specifications. The simplest behaviour GXcast can have is to fix the value to the nM value. However, this is not efficient for groups having a lot of members (typically more than n_max). 2) The number of members influenced by a fault: if a drop occurred on a GXcast packet, every member having its address in the member list will be concerned by the drop. To reduce the number of destinations concerned by such errors, small values of should be chosen. 3) Number of generated packets: after studying the packet generating functtion , we found that this function admits a minimum value for: nM= n_max/2. Since this optimal value does not depend on n and on d and since it is very simple to calculate it and provides good results in terms of the number of generated packets, we propose it as a default value for the GXcast protocol. 4) Using Path MTU instead of minimum MTU: At the beginning of this section, we defined MTU as the minimum MTU guaranteed by IP. However, the value of the Path MTU (PMTU) can also be used since we don't make any assumptions on the stability of the MTU value in our study. The PMTU is the minimum value of the MTU on the links of a path. It can be noticed that the PMTU value is easy to obtain in GXcast, since unicast paths are used. References Boudani et al. [Page 6] INTERNET-DRAFT GXcast October 2004 [1] D. Waitzman, C. Partridge, and S. Deering. Distance Vector Multicast Routing Protocol. IETF RFC 1075, 1988. [2] J. Moy. Multicast Extensions to OSPF. IETF RFC 1584, 1994. [3] J. Moy. MOSPF: Analysis and Experience. IETF RFC 1585, 1994. [4] S. Deering et al. Protocol Independent Multicast version 2-Dense Mode Specification. IETF Internet Draft, http://catarina.usc.edu/pim/pimdm/pim-dm-06.txt, 1997. [5] D. Estrin et al. Protocol Independent Multicast-Sparse Mode (PIM-SM): Protocol Specification. IETF RFC 2362, 1998. [6] M. Ramalho. Intra- and Inter-domain multicast routing protocols: A survey and taxonomy. IEEE Communications Surveys and Tutorials, First Quarter 2000. [7] Reliable Multicast Transport Working Group Web Site. http://www.ietf.org/html.charters/rmt-charter.html, February 2003. [8] S. Deering, S. Hares, C. Perkins, and R. Perlman. Overview of the 1998 IAB Routing Workshop. IETF RFC 2902, August 2000. [9] D. Ooms. Taxonomy of xcast/sgm proposals. IETF Internet draft, July 2000. [10] R. Boivie, N. Feldman, Y. Imai, W. Livens, D. Ooms, and O. Paridaens. Explicit multicast (Xcast) basic specification. IETF Internet draft, October 2000. [11] S. Myung-KI, K. Yong-Jin, P. Ki-Shik, and K. Sang-Ha. Explicit multicast extension (xcast+) for efficient multicast packet delivery. ETRI Journal, 23(4), December 2001. [12] B. Cain, S. Deering, B. Fenner, I. Kouvelas, and A. Thyagarajan. Internet group management protocol, version 3. IETF Internet draft, January 2002. [13] University of Southern California J. Postel from the Information Sciences Institute. Internet Protocol. IETF RFC 791, 1981. [14] S.Deering and R. Hinden. Internet Protocol, version 6 (ipv6) Specification. IETF RFC 2460, 1998. [15] J. Moy. Ospf version 2. IETF RFC1247, July 1991. [16] K. Fall. and K. Varadhan. The NS Manual. UC Berkeley, LBL, USC/ISI, and Xerox PARC, January 2001. [17] E. Zegura, K. Calvert, and S. Bhattacharjee. How to model an internetwork. In INFOCOM, 1996. [18] A. Boudani, A. Guitton, B. Cousin. GXcast: Generalized Explicit Multicast Routing Protocol. 9th IEEE Symposium on Computers and Communications (ISCC 2004) [organis‰e par l'IEEE], Alexandria, Egypt, June 2004 (ask authors for a hard copy). Authors Addresses Ali Boudani IRISA/INRIA Rennes Campus Universitaire de Beaulieu Avenue du General Leclerc 35042 Rennes France Phone : (33) 02 99 84 25 37 Fax : (33) 02 99 84 25 29 E-mail : aboudani@irisa.fr Boudani et al. [Page 7] INTERNET-DRAFT GXcast October 2004 Alexandre Guitton IRISA/Universit‰ de Rennes1 Campus Universitaire de Beaulieu Avenue du General Leclerc 35042 Rennes France Phone : (33) 02 99 84 25 37 Fax : (33) 02 99 84 25 29 E-mail : alexandre.guitton@irisa.fr Bernard Cousin IRISA/INRIA Rennes Campus Universitaire de Beaulieu Avenue du General Leclerc 35042 Rennes France Phone : (33) 02 99 84 73 33 Fax : (33) 02 99 84 71 71 E-mail : bcousin@irisa.fr Copyright Statement Copyright (C) The Internet Society (2004). This document is subject to the rights, licenses and restrictions contained in BCP 78, and except as set forth therein, the authors retain all their rights." "This document and the information contained herein are provided on an "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIM 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." Expiration Date: April 2005