idnits 2.17.1 draft-ooms-cl-multicast-01.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** Looks like you're using RFC 2026 boilerplate. This must be updated to follow RFC 3978/3979, as updated by RFC 4748. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- == No 'Intended status' indicated for this document; assuming Proposed Standard Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** 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 5 instances of too long lines in the document, the longest one being 3 characters in excess of 72. ** The abstract seems to contain references ([HAND], [DEER]), which it shouldn't. Please replace those with straight textual mentions of the documents in question. Miscellaneous warnings: ---------------------------------------------------------------------------- == The "Author's Address" (or "Authors' Addresses") section title is misspelled. == Line 86 has weird spacing: '... mp2mp mult...' -- 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.) -- Couldn't find a document date in the document -- date freshness check skipped. -- Found something which looks like a code comment -- if you have code sections in the document, please surround them with '' and '' lines. 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? 'DEER' on line 824 looks like a reference -- Missing reference section? 'HAND' on line 833 looks like a reference -- Missing reference section? 'PERL' on line 842 looks like a reference -- Missing reference section? 'HOLB' on line 836 looks like a reference -- Missing reference section? 'OIKA' on line 839 looks like a reference -- Missing reference section? 'FARI' on line 827 looks like a reference -- Missing reference section? 'AGUI' on line 821 looks like a reference -- Missing reference section? 'GRAF' on line 830 looks like a reference -- Missing reference section? 'A-Z' on line 719 looks like a reference Summary: 4 errors (**), 0 flaws (~~), 3 warnings (==), 12 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 1 D. Ooms 2 INTERNET DRAFT W. Livens 3 Alcatel 5 October, 1999 6 Expires April, 2000 8 Connectionless Multicast 10 Status of this Memo 12 This document is an Internet-Draft and is in full conformance with 13 all provisions of Section 10 of RFC2026. 15 Internet-Drafts are working documents of the Internet Engineering 16 Task Force (IETF), its areas, and its working groups. Note that 17 other groups may also distribute working documents as Internet- 18 Drafts. 20 Internet-Drafts are draft documents valid for a maximum of six months 21 and may be updated, replaced, or obsoleted by other documents at any 22 time. It is inappropriate to use Internet-Drafts as reference 23 material or to cite them other than as "work in progress." 25 The list of current Internet-Drafts can be accessed at 26 http://www.ietf.org/ietf/1id-abstracts.txt 28 The list of Internet-Draft Shadow Directories can be accessed at 29 http://www.ietf.org/shadow.html. 31 Abstract 33 This draft proposes a new mechanism for multipoint-to-multipoint 34 (mp2mp) communication in IP networks, namely Connectionless Multicast 35 (CLM). Instead of a group address, a list of member addresses is 36 encoded in the data packets. 38 The traditional Host Group Model [DEER] for IP multicast requires a 39 globally unique address for each session. To support this model, 40 multicast routing protocols create state per group in the routers. 41 Like any connection oriented protocol, it suffers from scalability 42 problems in backbone networks where the number of groups to be 43 maintained can be huge. CLM does not have this problem, and 44 additionally has some other advantages. Its limitation lies in the 45 number of members per multicast session, not in the number of 46 sessions. CLM will not replace the traditional multicast model. CLM 47 offers an alternative for mp2mp communication in the cases that 48 traditional multicast becomes problematic. 50 The pros and cons of CLM are described and suggestions are made to 51 alleviate the disadvantages. Furthermore different modes of 52 operation are described: an end-to-end mode in close conjunction with 53 SIP (Session Initiation Protocol [HAND]), as well as an interworking 54 mode with PIM-SM and Simple Multicast. Both IPv4 and IPv6 are 55 considered. 57 Table of Contents 59 1. Introduction 60 2. The critique on the traditional multicast model 61 3. Description 62 4. Working modes 63 4.1 CLM as an end-to-end multicast routing solution 64 4.2. CLM as an interdomain multicast routing protocol 65 4.2.1. Simple Multicast 66 4.2.2 PIM-SM 67 4.3. Summary 68 5. Cloning 69 6. Caching 70 7. Address list encoding 71 8. IP Protocol extensions 72 8.1. IPv4 73 8.2. IPv6 74 9. Security Considerations 75 10. Acknowledgements 76 A Hierarchical Address List Encoding 77 A.1. Compound addresses 78 A.2. Processing of a compound address 79 A.3. Compound address encoding example 81 Table of Abbreviations 83 CLM ConnectionLess Multicast 84 HALE Hierarchical Address List Encoding 85 IRC Internet Relay Chat 86 mp2mp multipoint-to-multipoint 87 PIM-SM Protocol Independent Multicast Sparse Mode 88 RUN Receiver Update Notification 89 SM Simple Multicast 91 1. Introduction 92 The main goal of multicast is to avoid duplicate information flowing 93 over the same link. By using traditional multicast instead of 94 unicast, bandwidth consumption decreases while the state and 95 signalling per session increases. Apart from these two dimensions, 96 we identify a third one: the header processing per packet. This 97 three dimensional space is depicted in Figure 1. 99 state&signaling 100 per session 101 in router 102 ^ 103 | 104 | 105 .... 106 B | .... 107 . | .... 108 . | .... 109 . | .... 110 . +------------------..---> processing 111 . / .... C per packet 112 . / ..... in router 113 . / ..... 114 . / ..... 115 ./ ..... 116 /A.... 117 / 118 / 119 link bandwidth 121 Figure 1 123 A first method to deliver identical information from a source to n 124 destinations is to unicast the information n times (A in Figure 1). 125 A second method, the traditional multicast model (B in Figure 1) 126 sends the information only once to a multicast address. In the third 127 alternative (CLM), which is the subject of this draft, the 128 information is sent only once, but the packet contains a list of 129 destinations (point C). For a detailed description of CLM we refer 130 to section 3. 132 The three points A, B and C define a plane (indicated with dots in 133 Figure 1): a plane of conservation of misery. All three approaches 134 have disadvantages: the link bandwidth is a scarce resource in the 135 access network, while state&signaling/session and processing/packet 136 encounter limitations in the core of the network. 138 Traditional multicast can move a little bit along the line A-B by 139 switching between source and shared trees. However, this flexibility 140 is very limited. Thus state&signaling/session is, amongst others 141 (see section 2) a problem for the traditional multicast model in the 142 backbone. 144 Also pure CLM encounters limitations in the core of the network 145 (processing/packet), but the nice and differentiating feature of CLM 146 is that it gives the router the choice to make its own tradeoffs. 147 CLM has three mechanisms built in (caching, premature cloning and 148 optimized address list encoding) that allows the router to move in 149 this plane of conservation of misery, according to its own needs, 150 which could be e.g. its location in the network. Caching allows a 151 router to move from C to B, while premature cloning allows a shift 152 from C to A. 154 It is often argumented that it is not worthwhile to use multicast for 155 mp2mp communication with a limited number of members, and use unicast 156 instead. This is definitely untrue as following example illustrates: 157 assume n residential users set up a video conference. For e.g. xDSL, 158 GPRS or cable modem access technologies a host has no problem 159 receiving n-1 basic 100kb/s video flows, but the host is not able to 160 send its own video data n-1 times at this rate. Because of the 161 limited and often asymmetric access capacity, some type of multicast 162 is mandatory. 164 In CLM, a host sends a packet with the addresses of the other n-1 165 members. The first router beyond the access link can probably 166 process the packets in pure CLM mode since the link speed is 167 relatively small here. Further in the network, where link speeds 168 increase, routers can decide to maintain a cache entry for this 169 session. Once arrived in a backbone network, where bandwidth is 170 plentiful, the CLM packets could be prematurely cloned into multiple 171 unicast packets to avoid the heavy header processing in the core 172 routers. 174 A simple but important application of CLM lies in bridging the local 175 loop for mp2mp communication. The host sends the CLM packet with the 176 list of unicast addresses and the first router prematurely clones the 177 CLM packet to multiple normal unicast packets. 179 We believe that the flexibility of CLM to adapt to local network 180 conditions makes CLM an excellent multicast forwarding mechanism in 181 the heterogeneous internetworks, as we currently know them. 183 2. The critique on the traditional multicast model 185 The characteristics of the traditional IP multicast model are 186 determined by its two components: the Host Group model [DEER] and a 187 Multicast Routing Protocol. Both components add to the difference in 188 nature between unicast and multicast. 190 In the Host Group model, a group of hosts is identified by a 191 multicast group address, which is used both for subscriptions and 192 forwarding. This model has two main disadvantages: 194 - Multicast address allocation: The creator of a multicast group must 195 allocate a multicast address which is unique in its scope (scope will 196 often be global). This issue is being addressed by the Malloc 197 working group, which is proposing a set of Multicast Address 198 Allocation Servers (MAAS) and three protocols (MASC, AAP, MADCAP). 200 - Destination unawareness: When a multicast packet arrives in a 201 router, the router can determine the next hops for the packet, but 202 knows nothing about the ultimate destinations of the packet, nor 203 about how many times the packet will be duplicated later on in the 204 network. This complicates the security, accounting and policy 205 functions. 207 In addition to the Host Group model, a routing algorithm is required 208 to maintain the member state and the delivery tree. This can be done 209 using a (truncated) broadcast algorithm or a multicast algorithm 210 [DEER]. Since the former consumes too much bandwidth by 211 unnecessarily forwarding packets to some routers, only the multicast 212 algorithms are considered. These multicast routing protocols have 213 the following drawbacks: 215 - Connection state scalability: The multicast routing protocols 216 exchange messages that create state for each multicast group in all 217 the routers that are part of the point-to-multipoint tree. This can 218 be viewed as a kind of signaling that creates multicast connection 219 state, yielding huge multicast forwarding tables that have to be 220 maintained in the backbone. The name Connectionless Multicast refers 221 to the elimination of this connection state. 223 - Source advertisement mechanism scalability: Multicast routing 224 protocols provide a mechanism by which members get 'connected' to the 225 sources for a certain group without knowing the sources themselves. 226 In sparse-mode protocols (CBT, PIM-SM), this is achieved by having a 227 core node, which needs to be advertised in the complete domain. On 228 the other hand, in dense-mode protocols (PIM-DM, DVMRP) this is 229 achieved by a "flood and prune" mechanism. Both approaches raise 230 additional scalability issues. 232 Multicast address allocation, destination unawareness and scalability 233 issues are delaying widescale deployment of multicast, leading to a 234 search for other multicast schemes. Recently, several changes to the 235 Host Group Model were proposed to address these drawbacks: 237 - Simple Multicast [PERL] uses the couple of core and multicast 238 addresses as the group identifier. In this way core advertisement 239 and multicast address allocation can be avoided. Furthermore, state 240 can be avoided in parts of the network by creating tunnels. Note 241 however that these tunnels are point-to-point and if e.g. a link has 242 n tunnels for a certain group it will still carry n times the same 243 data. 245 - In Express [HOLB], a multicast channel is identified by source and 246 multicast addresses. Thus address allocation is not required and 247 since there is no core, there is no core advertisement either. 248 Creating a multicast session with multiple changing sources is 249 implemented by using a session manager and a set of multicast 250 channels. Note that each on-tree node still keeps state for each 251 source of the multicast session. 253 3. Description 255 In the Host Group Model the packet carries a multicast address as a 256 logical identifier of all group members. In Connectionless Multicast 257 (CLM) the packet carries all the IP addresses of the multicast 258 session members (in the context of CLM the term 'multicast session' 259 will be used instead of 'multicast group' to avoid the strong 260 association of multicast group with multicast address in traditional 261 IP multicast). 263 In each router the next hop for each destination is determined and 264 for every distinct next hop a new header is constructed. This header 265 only contains the destinations for which that next hop is on the 266 shortest path to these destinations. When there is only one 267 destination left the CLM packet turns into a normal unicast packet, 268 which can be unicasted along the remainder of the route. 270 Although not restricted to this type of multicast session, the most 271 beneficial application of CLM is for sessions with a limited number 272 of members (super-sparse sessions). 274 For sessions with a large number of members (broadcast applications), 275 CLM can be used as an interdomain multicast routing mechanism between 276 a limited number of domains which run either PIM-SM or Simple 277 Multicast. 279 So, CLM will not replace the traditional multicast model, but offers 280 an alternative for mp2mp communication where traditional multicast 281 becomes problematic. 283 In practice, traditional multicast routing protocols impose 284 limitations on the number of groups and the size of the network in 285 which they are deployed. For CLM these limitations do not exist. 287 CLM has the following advantages: 289 1) No multicast address allocation required. 291 2) Routers do not have to maintain state per session (or per source- 292 session). 294 3) Easy transition phase. The destination address field of the IPv4 295 header will carry one of the addresses of the list of receivers. 296 This enables a gradual introduction of CLM in the network. If a 297 router does not understand CLM, it forwards the CLM packet as a 298 normal unicast packet. The downstream CLM-upgraded routers will then 299 take care of the branching of the tree. The minimal condition to 300 make CLM work in the current Internet is that the designated router 301 (= first router connected to host) of all the destinations 302 participating in a CLM session are CLM-upgraded. When at least these 303 routers are CLM-upgraded correct packet delivery is assured. 305 4) No symmetrical paths required. Traditional multicast routing 306 protocols assume (for optimal functioning) symmetrical paths, i.e. 307 the shortest path from A to B is the same as the shortest path from B 308 to A. This is a false assumption in the current Internet and it is 309 expected that this statement will become even more false when traffic 310 engineering and more policy routing is introduced in the Internet. 312 5) Automatic reaction to unicast reroutes. CLM will react 313 immediately to unicast route changes. In traditional multicast 314 routing protocols a communication between the unicast and the 315 multicast routing protocol needs to be established. In many 316 implementations this is on a polling basis, yielding a slower 317 reaction to e.g. link failures. 319 6) Easy security and accounting. In contrast with the Host Group 320 Model, in CLM all the sources know the members of the multicast 321 session, which gives the sources the means to e.g. reject certain 322 members or count the traffic going to certain members quite easily. 323 Not only a source, but also a border router is able to determine how 324 many times a packet will be duplicated in its domain. It becomes 325 also more easy to restrict the number of senders or the bandwidth per 326 sender. 328 7) Heterogeneous receivers. Besides the list of destinations, the 329 packet can also contain a list of DiffServ bytes. While traditional 330 multicast protocols have to create separate groups for each service 331 class, CLM incorporates the possibility of having receivers with 332 different service requirements within one multicast session. 334 8) Policy routing via BGP. No need for a specific multicast policy 335 routing protocol (extension). 337 9) Unicast traffic engineering can be applied, no need for multicast 338 traffic engineering. 340 However, CLM has a number of disadvantages as well: 342 1) Overhead. Each packet contains all remaining destinations, but 343 the total amount of data is still much less than for the unicast 344 (payload is only sent once). A method to compress the list of 345 destination addresses might be useful (section 7). 347 2) More complex header processing. Each destination in the packet 348 needs a routing table lookup. So a CLM packet with n destinations 349 requires the same number of routing table lookups as n unicast 350 headers. Additionally, a different header has to be constructed per 351 next hop. Remark however that: 353 a) Since CLM will typically be used for super-sparse sessions, there 354 will be a limited number of branching points, compared to non- 355 branching points. By using a simple caching mechanism (see section 356 6) in these non-branching points, the classical forwarding method can 357 be used and therefore the same performance achieved. 359 b) Among the non-branching points, a lot of them will contain only 360 one destination. In these cases normal unicast forwarding is 361 applied. 363 c) When the packet enters a region of the network where link 364 bandwidth is not an issue anymore, the packet can be prematurely 365 cloned. This avoids more complex processing downstream (section 5). 367 d) The forwarding in the branching points can also be enhanced by a 368 caching mechanism (section 6). 370 e) By using a hierarchical encoding of the list of destinations in 371 combination with the aggregation in the forwarding tables the 372 forwarding can be accelerated (section 7). 374 3) Multi-access networks. Since e.g. Ethernet does not support CLM, 375 this multi-access network will carry duplicate packets, one for each 376 next hop. 378 4. Working modes 380 The preceding sections mainly focused on the data plane, this section 381 will focus on the control plane of CLM. CLM is mainly applicable to 382 super-sparse multicast sessions. Besides this, we also describe how 383 CLM can be used as an interdomain multicast routing protocol, 384 connecting e.g. Simple Multicast or PIM-SM domains. 386 4.1 CLM as an end-to-end multicast routing solution 388 If CLM is used end-to-end, it is especially useful for super-sparse 389 sessions, e.g. video conferences. 391 In the current Internet three approaches to establish multipoint-to- 392 multipoint sessions can be identified: 394 - Internet Relay Chat (IRC) [OIKA]. In this approach a set of 395 servers keeps track of the created channels and the members of these 396 channels. The servers are also responsible for emulating the mp2mp 397 data delivery, which relies on a unicast forwarding. 399 - Current IP Multicast Group Establishment (IGMP, Multicast Protocol, 400 Multicast Address Allocation). In this approach the creation of the 401 group, mainly the multicast address allocation, is the responsibility 402 of a set of servers, while the member state is distributed over the 403 network. The data delivery is distributed over the network and 404 relies on a multicast forwarding. 406 - Session Initiation Protocol (SIP) [HAND]. A host takes the 407 initiative to set up a session. With the assistance of a SIP server 408 a session is created. The session state is kept in the hosts. Data 409 delivery can be achieved by several mechanisms: meshed unicast, 410 bridged or multicast. Note that for the establishment of multicast 411 delivery, a multicast protocol and communication with Multicast 412 Address Allocation Servers (MAAS) are still required. 414 Both CLM and SIP address super-sparse mp2mp sessions. It turns out 415 that CLM (a very flexible data plane mechanism) can be easily 416 integrated with SIP (a very flexible control plane protocol). When 417 an application decides to use CLM forwarding it does not affect its 418 interface to the SIP agent: it can use the same SIP messages as it 419 would use when it opted for meshed unicast forwarding. 421 4.2. CLM as an interdomain multicast routing protocol 422 4.2.1. Simple Multicast 424 Simple Multicast provides a tunnel mechanism. This tunnel is used 425 either to cross non Simple Multicast domains or to limit the 426 multicast forwarding state in parts of the network. When the tunnel 427 is used for the latter purpose, the bandwidth saving of multicast is 428 lost in these parts of the network, i.e. parallel tunnels for the 429 same group can exist on a specific link (Figure 2). Assume ERi are 430 Simple Multicast Exit Routers and BRi are Backbone Routers in which 431 one wants to avoid multicast forwarding state. S is a sender to the 432 group and Ri are receivers. For this topology Simple Multicast will 433 construct a first tunnel from ER1 to ER2 and a second tunnel from ER1 434 to ER3, yielding duplicate traffic on the link ER1-BR1. 436 +--------BR2--------ER2------R1 437 | 438 | 439 S------ER1------BR1-------BR3--------ER3------R2 441 Figure 2 443 If the backbone routers are CLM routers the duplicate traffic can be 444 avoided without building multicast state. The interworking is easy 445 since ER1 knows the endpoints of both tunnels: it can send the 446 multicast packet in CLM mode by putting ER2 and ER3 as destinations 447 in the packet, thereby creating a point-to-multipoint tunnel. 449 4.2.2. PIM-SM 451 With MSDP [FARI] the Rendezvous Points (RPs) of different PIM-SM 452 domains discover which RPs have sources for a certain group in their 453 domain. Similarly, a Multicast Receiver Distribution Protocol (MRDP) 454 can be created. MRDP allows RPs to discover which RPs have receivers 455 for a certain group in their domain. If MRDP is running and an RP 456 has a source for a group, it can send the data in a CLM mode to the 457 RPs which have receivers for this group. 459 4.3. Summary 461 The working modes of CLM and other mp2mp communication mechanisms are 462 summarized in Table 1. 464 | control plane | data plane 465 + -----------+-------------+--------------- 466 | session | member | forwarding 467 | creation | state | 468 ----------+------------+-------------+--------------- 469 IRC | servers | servers | servers (UC) 470 multicast | servers | network | network (MC) 471 SIP/CLM |host/server | hosts | network (CLM) 472 SM/CLM | / |exit router | network (CLM) 473 MRDP/CLM | / | RP | network (CLM) 475 Table 1 477 5. Premature Cloning 479 A router can decide to prematurely clone a CLM packet, i.e. duplicate 480 a CLM packet before its actual branching point. This early cloning 481 facilitates a less complex forwarding in all downstream routers. 483 An operator's border router can e.g. prematurely clone the CLM 484 packets that would normally branch in the operator's domain. Or an 485 edge router can prematurely clone CLM packets to multiple unicast 486 packets (when CLM was only used to bridge the local loop). 488 6. Caching 490 The increased forwarding complexity is the main problem of CLM: 491 packet headers have to be processed at wirespeed. It was already 492 mentioned that in major parts of the tree the normal unicast 493 forwarding can be applied (from the moment there is only one 494 destination address left in the packet). 496 A method for further enhancing the forwarding is building a cache for 497 the highest bandwidth sources. If the source supports caching it 498 will put a non-zero number in the cache field of the IP option or in 499 the CLM header: the Receiver Update Notification (RUN). Each time 500 the set of destinations changes the source will indicate this to the 501 downstream routers by changing the RUN. The cache will contain 502 entries for (S, RUN). If the router receives a high bandwidth flow 503 with a new (S, RUN) it will create a new cache entry. Unused cache 504 entries will time out. 506 A possible optimization is that the source increments the RUN value 507 by 1 if the list of receivers changes. In that way the router can 508 immediately remove the entry (S, RUN) and replace it by an (S, RUN+1) 509 entry. When the RUN value reaches its maximum value the clearing of 510 the cache entry still relies on a the expiration of a timer. 512 Note that a source can send to multiple sessions. In this case the 513 source has to partition its RUN space amongst these sessions. 515 Maintaining a cache may seem contradictory to the main characteristic 516 of CLM (avoid state in the router), but it is important to note that 517 each router can independently decide to create a cache or not. The 518 router itself can make the tradeoff between memory and processing 519 time. 521 There are two ways of keeping a cache: 523 1) Each (S, RUN) entry has a list of next hops with the associated 524 outgoing IP option or CLM header (or list of destinations). 526 2) Only (S, RUN) which have one next-hop (still multiple 527 destinations) are cached. These packets do not have to change their 528 IP option or CLM header, so the latter information should not be kept 529 in the cache. 531 Both ways of applying a cache can be used in parallel. 533 7. Address list encoding 535 In this section the Hierarchical Address List Encoding method (HALE) 536 is described which possibly allows to reduce the packet overhead or 537 to increase the forwarding capacity. Given a list of IP addresses, 538 the method iteratively separates the common prefixes of the list of 539 IP addresses. 541 To illustrate HALE, consider the multicast tree in Figure 3. The 542 source S1 wants to deliver the same information to destinations D1 543 (ABCD), D2 (ABCE) and D3 (AFGH). For simplicity we will assume in 544 this example that the separation of common bits is only executed on 545 byte boundaries. The addresses of D1 and D2 have ABC in common, so 546 it can be written as the compound address ABC{D,E}. The address of 547 D3 and the compound address ABC{D,E} have A in common, yielding a new 548 compound address A{BC{D,E},FGH}. 550 D1 551 / 552 /ABCD 553 A{BC{D,E},FGH} ABC{D,E} / ABCE 554 S1-------------------R1------------R2----------D2 555 \ 556 \AFGH 557 \ AFGH 558 R3---------------D3 560 ABCD | 561 > ABC{D,E} | 562 ABCE | | 563 > A{BC{D,E},FGH} 564 AFGH | 566 Figure 3 568 HALE, combined with the aggregation in the routing tables, allows to 569 save on lookup cycles. 571 More details on HALE and how the forwarding benefits from this 572 encoding can be found in Appendix A. 574 8. IP Protocol extensions 576 8.1. IPv4 578 In IPv4 two approaches can be followed to include the list of 579 destination addresses. Either one adds a new IPv4 option or one adds 580 an extra header between the network and the transport layer. 582 Since the IPv4 option field is limited to 40 bytes (of which 4 bytes 583 are used for the option type field) only 10 (9 in the option and 1 in 584 the destination field of the IP header) destination addresses can be 585 included. If the number of receivers is larger than 10 multiple 586 packets can be sent. Although for a different purpose, [AGUI] and 587 [GRAF] already proposed an IPv4 option to carry multiple 588 destinations. We propose the new IP option depicted in Figure 4. 590 0 1 2 3 591 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 592 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 593 |1 0 0| TYPE | LENGTH |D| ENC | RUN | 594 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 595 | (Encoded) List of DS Bytes and Addresses | 596 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 598 Figure 4 600 TYPE = number for this IPv4 option 602 LENGTH = total length of the option in bytes 604 D = if this bit is set the packet will contain a (encoded) DS-byte 605 for each destination. 607 ENC (3 bits) = encoding method used on the list of DS bytes and 608 destination addresses. Following encoding methods are defined: 609 0 = no encoding 610 1 = hierarchical address list encoding (see section 7) 612 RUN (12 bits) = Receiver Update Notification (see section 6). If the 613 sender does not support the caching mechanism, it has to set RUN to 614 zero. 616 Figure 5. shows the 'List of DS Bytes and Addresses' in case the D- 617 bit is set and ENC = 0. Remember that the first destination and DS 618 byte are placed in the normal IP header. 620 0 1 2 3 621 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 622 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 623 | destination address 2 | 624 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 625 | . . . | 626 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 627 | destination address N | 628 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 629 | DS byte 2 | DS byte 3 | ... | 630 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 631 | | DS byte N | padding | 632 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 634 Figure 5 636 The 'List of DS Bytes and Addresses' encoding in case the D-bit is 637 cleared and ENC = 1 is explained in Appendix A.3. 639 Instead of using the IP option field one could add an extra header 640 between the network and the transport layer. This header is depicted 641 in Figure 6. The IP header will carry the protocol number PROTO_CLM. 643 0 1 2 3 644 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 645 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 646 |VERSION|UNUSED | PROT ID | LENGTH | 647 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 648 | CHECKSUM |D| ENC | RUN | 649 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 650 | (Encoded) List of DS Bytes and Addresses | 651 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 653 Figure 6 655 VERSION = CLM version number 657 PROT ID = specifies the protocol on the transport layer 659 LENGTH = length in bytes of the CLM header. 661 CHECKSUM = it is not clear yet whether a checksum is needed (ffs). 662 If only one bit is wrong it can still be useful to forward the packet 663 to N-1 correct destinations and 1 incorrect destination. On the 664 other hand when the header info is used to install a cache (see 665 section 6) one can not allow that packets are permanently forwarded 666 wrongly. One approach could be to provide a checksum per 667 destination. 669 The other fields were described earlier. 671 8.2. IPv6 673 Since IPv6 allows more flexibility in adding options (e.g. no 674 limitation on the size), there is no limitation in terms of encoding 675 on the number of destinations that can be put in a packet. However, 676 since a packet can only be sent after all the destinations have been 677 processed, packets with a lot of addresses will experience a lot of 678 delay and can delay other packets as well if no preemptive scheduler 679 is used. 681 For IPv6 the overhead will be larger since the addresses are longer. 682 Note however that IPv6 probably allows an encoding with better 683 compression because of the geographical/provider distribution of 684 addresses. Moreover if CLM is used as an interdomain multicast 685 mechanism only the locator part of the address needs to be 686 considered. 688 9. Security Considerations 690 Since a packet contains every destination, it is much more easy to 691 restrict multicast sessions to certain receivers. It also allows 692 ISPs to check, when a packet enters their network, how much resources 693 this packet packet will consume in their network. 695 In the end-to-end mode it is also easy to restrict the number of 696 senders or to restrict/monitor the bandwidth of a sender. 698 10. Acknowledgements 700 The authors would like to thank Emmanuel Desmet, Hans De Neve and 701 Miroslav Vrana for the fruitful discussions and/or their thorough 702 revision of this document. 704 A Hierarchical Address List Encoding (HALE) 706 A.1. Compound addresses 708 A list of addresses can be compressed into a compound address by 709 writing common prefixes only once, followed by a list of their 710 suffixes. 712 We used following syntax to represent compound addresses: 714 ::= prefix "{" "}" 715 ::= [] 716 ::= [ ","] 717 ::= | 718 ::= [] 719 ::= [A-Z] in our example, one bit in practice 720 (can also be a nibble or octet) 722 Let's take the following list of addresses as an example: 724 ABCD, ABCE, AFGH 726 The addresses all have a common prefix A, so we can write A once 727 followed by the list of suffixes BCD, BCE and FGH. i.e. 729 A { BCD, BCE, FGH } 731 Two of these suffixes share a common prefix BC, so we obtain: 733 A { BC { D, E }, FGH } 735 A.2. Processing of a compound address 737 Following pseudo code parses a compound address and issues a minimum 738 amount of lookup() calls to a routing table engine. We assume the 739 lookup takes a symbol (e.g. one bit) as argument and returns a pointer 740 to it's internal (e.g. tree) structure which can be passed to a next 741 lookup. The parser maintains a stack of such indices. We assume that a 742 meta symbol also denotes the number of non-meta symbols that follow (see 743 encoding in A.3.). 745 index=routing_table_root; /* routing table entry point */ 746 skip=0; /* flag used to skip over irrelevant 747 * parts of the compound address */ 748 getch(meta); /* get first meta symbol. Only the 749 * length is used */ 750 while(1) { 751 len=LEN(meta); /* number of non-meta symbols that 752 * follow */ 753 for (i=0; i