idnits 2.17.1 draft-boudani-gxcast-02.txt: -(355): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** Cannot find the required boilerplate sections (Copyright, IPR, etc.) in this document. Found some kind of copyright notice around line 385 but it does not match any copyright boilerplate known by this tool. Expected boilerplate is as follows today (2024-04-26) according to https://trustee.ietf.org/license-info : IETF Trust Legal Provisions of 28-dec-2009, Section 6.a: This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79. IETF Trust Legal Provisions of 28-dec-2009, Section 6.b(i), paragraph 2: Copyright (c) 2024 IETF Trust and the persons identified as the document authors. All rights reserved. IETF Trust Legal Provisions of 28-dec-2009, Section 6.b(i), paragraph 3: This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (https://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- ** The document seems to lack a 1id_guidelines paragraph about Internet-Drafts being working documents. ** The document seems to lack a 1id_guidelines paragraph about 6 months document validity -- however, there's a paragraph with a matching beginning. Boilerplate error? == There are 2 instances of lines with non-ascii characters in the document. == No 'Intended status' indicated for this document; assuming Proposed Standard == The page length should not exceed 58 lines per page, but there was 7 longer pages, the longest (page 1) being 62 lines == It seems as if not all pages are separated by form feeds - found 0 form feeds but 7 pages Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack an Introduction section. ** The document seems to lack a Security Considerations section. ** The document seems to lack an IANA Considerations section. (See Section 2.2 of https://www.ietf.org/id-info/checklist for how to handle the case when there are no actions for IANA.) ** There are 17 instances of too long lines in the document, the longest one being 1 character in excess of 72. ** The abstract seems to contain references ([15], [2], [16], [3], [17], [4], [18], [5], [6], [7], [8], [9], [10], [11], [12], [13], [14], [1]), which it shouldn't. Please replace those with straight textual mentions of the documents in question. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the RFC 3978 Section 5.4 Copyright Line does not match the current year == The "Author's Address" (or "Authors' Addresses") section title is misspelled. == Line 149 has weird spacing: '...ns. The fragm...' == Line 258 has weird spacing: '... to the desti...' -- The document seems to lack a disclaimer for pre-RFC5378 work, but may have content which was first submitted before 10 November 2008. If you have contacted all the original authors and they are all willing to grant the BCP78 rights to the IETF Trust, then this is fine, and you can ignore this comment. If not, you may need to add the pre-RFC5378 disclaimer. (See the Legal Provisions document at https://trustee.ietf.org/license-info for more information.) -- The document date (October 2004) is 7133 days in the past. Is this intentional? Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) -- Missing reference section? '1' on line 315 looks like a reference -- Missing reference section? '2' on line 317 looks like a reference -- Missing reference section? '3' on line 318 looks like a reference -- Missing reference section? '4' on line 319 looks like a reference -- Missing reference section? '5' on line 322 looks like a reference -- Missing reference section? '6' on line 325 looks like a reference -- Missing reference section? '7' on line 328 looks like a reference -- Missing reference section? '8' on line 330 looks like a reference -- Missing reference section? '9' on line 332 looks like a reference -- Missing reference section? '10' on line 334 looks like a reference -- Missing reference section? '11' on line 337 looks like a reference -- Missing reference section? '12' on line 340 looks like a reference -- Missing reference section? '13' on line 343 looks like a reference -- Missing reference section? '14' on line 346 looks like a reference -- Missing reference section? '15' on line 348 looks like a reference -- Missing reference section? '18' on line 353 looks like a reference -- Missing reference section? '16' on line 349 looks like a reference -- Missing reference section? '17' on line 351 looks like a reference Summary: 8 errors (**), 0 flaws (~~), 8 warnings (==), 20 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 INTERNET DRAFT Ali Boudani 3 Expires: April 2005 Alexandre Guitton 4 Bernard Cousin 5 IRISA-France 7 October 2004 9 GXcast: Generalized Explicit Multicast Routing Protocol 10 12 Status of this Memo 14 By submitting this Internet-Draft, I certify that any applicable 15 patent or other IPR claims of which I am aware have been disclosed, 16 or will be disclosed, and any of which I become aware will be 17 disclosed, in accordance with RFC 3668." 19 Internet Drafts are working documents of the Internet Engineering 20 Task Force (IETF), its areas, and working groups. Note that other 21 groups may also distribute working documents as Internet-Drafts. 23 Internet-Drafts are draft documents valid for a maximum of six 24 months and may be updated, replaced, or obsolete by other documents 25 at anytime. It is inappropriate to use Internet Drafts as reference 26 material or to cite them other than as "work in progress." 28 The list of current Internet-Drafts can be accessed at 29 http://www.ietf.org/ietf/1id-abstracts.txt. 31 The list of Internet-Draft Shadow Directories can be accessed at 32 http://www.ietf.org/shadow.html. 34 Abstract 36 Recently several multicast mechanisms were proposed that scale better 37 with the number of multicast groups than traditional multicast does. 38 These proposals are known as small group multicast (SGM) or explicit 39 multicast (Xcast). Explicit multicast protocols, such as the Xcast 40 protocol, encode the list of group members in the Xcast header of 41 every packet. If the number of members in a group increases, routers 42 may need to fragment an Xcast packet. Fragmented packets may not be 43 identified as Xcast packets by routers. In this paper, we show that 44 the Xcast protocol does not support the IP fragmentation and we show 45 also that avoiding fragmentation induces hard-coded limits inside the 46 protocol itself in terms of group size. First, we describe the Xcast 47 protocol, the Xcast+ protocol (which is an extension of Xcast) and we 48 compare these two protocols with traditional multicast protocols.We 49 propose then a generalized version of the Xcast protocol, called 50 GXcast, intended to permit the Xcast packets fragmentation and to 51 support the increasing in the number of members in a multicast 52 group. 54 I. INTRODUCTION 55 Multicast, the ability to efficiently send data to a group of 56 destinations, has become increasingly important with the emergence of 57 network-based applications like IP telephony, videoconferencing, 58 distributed interactive simulation and software upgrading. A 59 multicast routing protocol should be simple to implement, scalable, 60 robust, use minimal network overhead consume minimal memory resources 61 , and inter-operate with other multicast routing protocols. 62 Most of proposed multicast protocols like DVMRP [1] and MOSPF ([2], 63 [3]) perform well if group members are densely packed. However, the 64 fact that DVMRP periodically floods the network and the fact that 65 MOSPF sends group membership information over the links, make these 66 protocols not efficient in cases where group members are sparsely 67 distributed among regions and the bandwidth is not plentiful. 68 To address these issues, the Protocol Independent Multicast (PIM) 69 routing protocols are being developed by the Inter-Domain Multicast 70 Routing (IDMR), working group of the IETF. PIM contains two 71 protocols: PIM-Dense Mode (PIMDM) [4] which is more efficient with 72 applications where group members are densely distributed, and 73 PIM-Sparse Mode (PIM-SM) [5] which performs better with applications 74 where group members are sparsely distributed. Although these two 75 protocols share similar control messages, they are essentially 76 proposed for two different kinds of applications. Today's multicast 77 protocols [6] can be used to minimize bandwidth consumption, but it 78 suffers from a scalability problem with the number of concurrently 79 active multicast groups because it requires a router to keep a 80 forwarding state for every multicast tree passing through it and the 81 number of forwarding states grows with the number of groups. There 82 seem to be two kinds of multicast that are important: a broadcast- 83 like multicast that sends data to a large number of destinations and 84 a narrowcast multicast that sends data to a fairly small group. An 85 example of the first kind of multicast is the audio and video 86 multicasting of a presentation to all employees in a corporate 87 intranet. An example of the second kind of multicast is a 88 videoconference involving three or four parties [6]. Thus, a 89 one-size-fits-all protocol will be unable to meet the requirements 90 of all applications [7]. Providing for many groups of small 91 conferences (a small number of widely dispersed people) with global 92 topological scope scales badly given the current multicast model [8]. 93 Recently several multicast mechanisms were proposed that scale better 94 with the number of multicast groups than traditional multicast does. 95 These proposals are known as small group multicast (SGM) [9] or 96 explicit multicast (Xcast) [10]. Explicit multicast protocols, such 97 as the Xcast protocol, encode the list of group members in the Xcast 98 header of every packet. Xcast assumes that there is no packet 99 fragmentation. However, if fragmentation occurs (e.g. if the group 100 size or the data is too large) the fragmented packets will not be 101 identified as Xcast packets by routers. In this paper we propose a 102 generalized Xcast protocol to support the group size increasing and 103 to overcome the fragmentation problem. 105 II. THE XCAST AND THE XCAST+ PROTOCOLS 106 To solve the problems of traditional multicast protocols, Boivie et 107 al. propose the Explicit Multicast protocol (Xcast). 109 A. The Xcast protocol 111 The Xcast protocol is a newly proposed multicast protocol to support 112 a very large number of small multicast groups. To send data to a 113 given group, the source first explicitly encodes the list of 114 destinations in the Xcast header of the packet. Then, the source 115 parses the header, partitions the destinations based on each next 116 unicast hop and forwards a packet with an appropriate header to each 117 of the next hops. Each router along the path to destinations repeats 118 the same processing on receiving an Xcast packet. If a router 119 detects that there is only one destination in the destination list 120 of a packet, the packet is converted to unicast. The algorithm 121 realizing the conversion of an Xcast packet to a unicast packet is 122 called Xcast-to-Unicast (X2U). This packet is then forwarded in 123 unicast along the remainder of the route. 125 B. The Xcast+ protocol 127 Xcast+ is an extension of Xcast for a more efficient delivery of 128 multicast packets [11]. Every source or destination is associated to 129 a Designated Router (DR). Instead of encoding in the Xcast packet 130 header the set of group members, Xcast+ encodes the set of their DRs. 131 When a new member wants to join the group G of source S, it sends an 132 IGMP-join message [12] to its DR. The DR will send a join-request 133 message to the source S. The DR of the source intercepts this message 134 and analyzes it in order to keep track of all concerned DR addresses. 135 When the source S wants to send a message to the group G, it sends a 136 multicast packet. This packet is received by its DR and converted to 137 an Xcast packet using the Multicast-to-Xcast algorithm (M2X). The 138 packet is then forwarded as in Xcast to the DRs, since the 139 destination list in the Xcast header contains the DR addresses 140 instead of the member addresses. Then, each DR converts the Xcast 141 packet to a multicast packet using the Xcast-to-Multicast protocol 142 (X2M) and sends it in its subnetworks. 144 C. The IP fragmentation mechanism 146 Due to physical reasons, every link can transfer only a limited 147 volume of information in each packet. The Internet protocol (IP) 148 [13] contains a mechanism called fragmentation which makes this 149 limitation transparent for end stations. The fragmentation 150 mechanism allows a packet to be cut into fragments in order to be 151 suitably transferred on a link. Suppose that a router receives a 152 packet. After having decided on which link this packet should be 153 forwarded, the router checks the maximum capacity of this 154 link which is the Maximum Transmission Unit (MTU). If the packet is 155 too large and unless it is explicitly forbidden, the router cuts out 156 it in order to respect the following constraints: each resulting 157 fragment is an autonomous IP packet, with a valid IP header, each 158 resulting fragment has a size less than or equal to the MTU, the 159 data is distributed between the fragments. The algorithm used to 160 fragment IPv4 packets is explained in [13]. The IPv6 protocol also 161 have a fragmentation mechanism, described in [14]. Note that one goal 162 of IPv6 is to avoid the fragmentation. This will be discussed later. 164 D. Xcast packet fragmentation 166 Since the Xcast packet header may be large, two cases can be 167 considered: either the whole Xcast packet header is short enough to 168 be kept in the first fragment, or the Xcast header has to be cut out. 169 In both cases, the second fragment is not a valid Xcast packet since 170 it has no Xcast header. Thus, these packets cannot be forwarded to 171 receivers and the data they contain is lost. Moreover, in the second 172 case the first fragment contains only a subset of receivers and no 173 data. The first fragment may however be forwarded up to the mentioned 174 receivers, inducing meaningful traffic. 175 These problems show that the fragmentation of an Xcast packet should 176 be forbidden. This can be done in IPv4 by setting the appropriate 177 flag (Don't Fragment, DF) in the IP header. In order to reach the 178 receivers, the source has to limit the size of its packets to 576 179 bytes which is the minimum MTU guaranteed by IPv4 on any link. This 180 size limits the number of receivers in an Xcast group to 134. In 181 IPv6, since the minimum MTU is 1280 bytes and since IPv6 addresses 182 are stored using 16 bytes, the limit in the size of the Xcast group 183 is 76. Having these limits hardly coded in protocols is restrictive. 184 What we propose is a simple mechanism to cancel these limitations 185 in the size of Xcast groups. The performance and the scalability of 186 our proposition will be analyzed. 188 E. Comparison between explicit multicast protocols and traditional 189 multicast protocols 191 Traditional multicast protocols and explicit multicast protocols are 192 two different approaches designed to handle multicast groups. We 193 will try to emphasis the main advantages of each method, compared to 194 the other one. 195 1) Drawbacks of explicit multicast protocols: In addition to the 196 important Xcast packet fragmentation problem, other related 197 drawbacks also exist. 198 a) Limited payload: packet size is limited as a result of network 199 MTU. In explicit multicast protocols, the larger the list of 200 destinations is, the lower the payload is.As a consequence, more 201 packets should be generated to transmit a given amount of data. 202 b) Complex header processing: in explicit multicast protocols, each 203 destination in the header needs a routing table lookup. A packet with 204 destinations in the list of destinations will require n+1 unicast 205 routing table lookups1. Additionally, a different header has to be 206 constructed per next hop. However, it can be noticed that since such 207 protocols are typically designed for sparse sessions, there will be 208 a limited number of branching routers compared to non-branching 209 routers. The construction of different headers only occurs in 210 branching points. The header construction can moreover be reduced 211 to a simple operation: the modification of a bitmap. 212 2) Advantages of explicit multicast protocols: Explicit multicast 213 protocols make easier the routing of multicast packets. It has many 215 advantages over traditional multicast protocols. 216 a) Routing state and signalisation messages management: in explicit 217 multicast protocols, routers do not have to maintain a state per 218 group. Indeed, there is no multicast forwarding table since only 219 unicast tables are used. This makes the Xcast protocol very scalable 220 in terms of the number of groups that can be supported 221 simultaneously since the routers in the network do not need to 222 disseminate information for the groups. 223 b) Automatic reaction to unicast reroutes and simplified traffic 224 engineering: explicit multicast protocols react immediately to 225 unicast route changes. Traditional multicast protocols need to 226 exchange information with unicast protocols in order to have an 227 adequate reaction. This is achieved on a polling basis in many 228 implementations, yielding a slower reaction to e.g. link failures. 229 This delay may also depend on the number of concerned groups. 230 Additionnaly, there is no need for a specific multicast traffic 231 engineering tool since packets follow traffic engineered unicast 232 paths. 233 c) Easier security and accounting: in explicit multicast protocols, 234 the source has a complete knowledge about members (or about DR 235 members). It will be able to drop dynamically some members and a 236 border router can be able to determine approximately how many times 237 a packet will be duplicated in its domain (especially when 238 link-state protocols like OSPF [15] are used in the domain). 240 Other advantages can be mentionned: 242 No multicast address allocation is needed except eventually in the 243 DR of the source in the case of the Xcast+ protocol. 245 Shortest path is always used even in an asymmetric network. 247 III. THE GXCAST PROTOCOL 248 As explained in the previous section, the Xcast protocol can not 249 support large groups due to its incompatibility with the IP 250 fragmentation mechanism. In this section, we propose a generalized 251 Xcast routing protocol, the GXcast protocol, which is designed 252 basically to avoid the fragmentation. Moreover, the GXcast protocol 253 can be parameterized in order to improve the Xcast behaviour. 255 A. The GXcast protocol 257 The GXcast protocol [18] is a simple generalized version of the 258 Xcast protocol: instead of sending a message to the destinations, 259 the source limits the number of destinations in a packet to nM. Thus, 260 the list of destinations is cutted into sub-lists of at most nM 261 destinations. Each sub-list corresponds to a destination list for 262 an Xcast packet. Several packets may have to be sent in order to 263 deliver data to all the destinations. is the parameter of the GXcast 264 protocol and it impacts the protocol performance in terms of several 265 criteria. GXcast packets are similar to Xcast packets: they have the 266 same header and are treated in the same way by intermediate routers, 267 DR destinations and destinations. The only difference between the 268 Xcast protocol and the GXcast protocol is done in the source or in 269 the DR of the source. The Xcast protocol and the GXcast protocol can 270 therefore inter-operate easily. 272 B. Study of the GXcast parameter 274 The behaviour of the GXcast protocol greatly depends on the value of 275 the parameter. Indeed, as we will see in this subsection, there is a 276 number of criteria that are directly influenced by the chosen value. 277 In the following, we will denote by MTU the value of the MTU which 278 depends on the IP version used, by E the size of the header plus 279 the size of the Xcast header (typically 16 bytes) and by IP the size 280 of an IP address. n will represent the number of destinations in the 281 group and d the volume in bytes of data to transfer. 282 1) Simple behaviour: 283 Since a packet has to contain at least one byte of data, the maximum 284 number of destinations n_max allowed in an Xcast packet is defined 285 as: 287 The values n_max = 134 and n_max = 76 correspond respectively to the 288 IPv4 and to the IPv6 specifications. The simplest behaviour GXcast 289 can have is to fix the value to the nM value. However, this is not 290 efficient for groups having a lot of members (typically more than 291 n_max). 293 2) The number of members influenced by a fault: if a drop occurred 294 on a GXcast packet, every member having its address in the member 295 list will be concerned by the drop. To reduce the number of 296 destinations concerned by such errors, small values of should be 297 chosen. 298 3) Number of generated packets: after studying the packet generating 299 functtion , we found that this function admits a minimum value for: 300 nM= n_max/2. Since this optimal value does not depend on n and on d 301 and since it is very simple to calculate it and provides good results 302 in terms of the number of generated packets, we propose it as a 303 default value for the GXcast protocol. 305 4) Using Path MTU instead of minimum MTU: At the beginning of this 306 section, we defined MTU as the minimum MTU guaranteed by IP. 307 However, the value of the Path MTU (PMTU) can also be used since we 308 don't make any assumptions on the stability of the MTU value in our 309 study. The PMTU is the minimum value of the MTU on the links of a 310 path. It can be noticed that the PMTU value is easy to obtain in 311 GXcast, since unicast paths are used. 313 References 315 [1] D. Waitzman, C. Partridge, and S. Deering. Distance Vector 316 Multicast Routing Protocol. IETF RFC 1075, 1988. 317 [2] J. Moy. Multicast Extensions to OSPF. IETF RFC 1584, 1994. 318 [3] J. Moy. MOSPF: Analysis and Experience. IETF RFC 1585, 1994. 319 [4] S. Deering et al. Protocol Independent Multicast version 2-Dense 320 Mode Specification. IETF Internet Draft, 321 http://catarina.usc.edu/pim/pimdm/pim-dm-06.txt, 1997. 322 [5] D. Estrin et al. Protocol Independent Multicast-Sparse Mode 323 (PIM-SM): Protocol Specification. IETF RFC 2362, 1998. 325 [6] M. Ramalho. Intra- and Inter-domain multicast routing protocols: 326 A survey and taxonomy. IEEE Communications Surveys and Tutorials, 327 First Quarter 2000. 328 [7] Reliable Multicast Transport Working Group Web Site. 329 http://www.ietf.org/html.charters/rmt-charter.html, February 2003. 330 [8] S. Deering, S. Hares, C. Perkins, and R. Perlman. Overview of 331 the 1998 IAB Routing Workshop. IETF RFC 2902, August 2000. 332 [9] D. Ooms. Taxonomy of xcast/sgm proposals. IETF Internet draft, 333 July 2000. 334 [10] R. Boivie, N. Feldman, Y. Imai, W. Livens, D. Ooms, and O. 335 Paridaens. Explicit multicast (Xcast) basic specification. IETF 336 Internet draft, October 2000. 337 [11] S. Myung-KI, K. Yong-Jin, P. Ki-Shik, and K. Sang-Ha. Explicit 338 multicast extension (xcast+) for efficient multicast packet delivery. 339 ETRI Journal, 23(4), December 2001. 340 [12] B. Cain, S. Deering, B. Fenner, I. Kouvelas, and A. 341 Thyagarajan. Internet group management protocol, version 3. IETF 342 Internet draft, January 2002. 343 [13] University of Southern California J. Postel from the 344 Information Sciences Institute. Internet Protocol. IETF RFC 791, 345 1981. 346 [14] S.Deering and R. Hinden. Internet Protocol, version 6 (ipv6) 347 Specification. IETF RFC 2460, 1998. 348 [15] J. Moy. Ospf version 2. IETF RFC1247, July 1991. 349 [16] K. Fall. and K. Varadhan. The NS Manual. UC Berkeley, LBL, 350 USC/ISI, and Xerox PARC, January 2001. 351 [17] E. Zegura, K. Calvert, and S. Bhattacharjee. How to model an 352 internetwork. In INFOCOM, 1996. 353 [18] A. Boudani, A. Guitton, B. Cousin. GXcast: Generalized Explicit 354 Multicast Routing Protocol. 9th IEEE Symposium on Computers and 355 Communications (ISCC 2004) [organis�e par l'IEEE], Alexandria, Egypt, 356 June 2004 (ask authors for a hard copy). 358 Authors Addresses 360 Ali Boudani 361 IRISA/INRIA Rennes 362 Campus Universitaire de Beaulieu 363 Avenue du General Leclerc 35042 Rennes France 364 Phone : (33) 02 99 84 25 37 365 Fax : (33) 02 99 84 25 29 366 E-mail : aboudani@irisa.fr 367 Alexandre Guitton 368 IRISA/Universit� de Rennes1 369 Campus Universitaire de Beaulieu 370 Avenue du General Leclerc 35042 Rennes France 371 Phone : (33) 02 99 84 25 37 372 Fax : (33) 02 99 84 25 29 373 E-mail : alexandre.guitton@irisa.fr 375 Bernard Cousin 376 IRISA/INRIA Rennes 377 Campus Universitaire de Beaulieu 378 Avenue du General Leclerc 35042 Rennes France 379 Phone : (33) 02 99 84 73 33 380 Fax : (33) 02 99 84 71 71 381 E-mail : bcousin@irisa.fr 383 Copyright Statement 385 Copyright (C) The Internet Society (2004). This document is subject 386 to the rights, licenses and restrictions contained in BCP 78, and 387 except as set forth therein, the authors retain all their rights." 389 "This document and the information contained herein are provided on an 390 "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS 391 OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET 392 ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED, 393 INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE 394 INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED 395 WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE." 397 Expiration Date: April 2005