INTERNET DRAFT D. Ooms <draft-ooms-cl-multicast-02.txt> Alcatel W. Livens Colt Telecom O. Paridaens ULB April, 2000 Expires October, 2000 Connectionless Multicast 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. Abstract This draft proposes a new mechanism for multipoint-to-multipoint (mp2mp) communication in IP networks, namely Connectionless Multicast (CLM). Instead of a group address, a list of member addresses is encoded in the data packets. The traditional Host Group Model [DEER] for IP multicast requires a globally unique address for each session. To support this model, multicast routing protocols create state per group in the routers. Like any connection oriented protocol, it suffers from scalability problems in backbone networks where the number of groups to be maintained can be huge. CLM does not have this problem, and additionally has some other advantages. Its limitation lies in the Ooms, et al. Expires October 2000 [Page 1]
Internet Draft draft-ooms-cl-multicast-02.txt April 2000 number of members per multicast session, not in the number of sessions. CLM will not replace the traditional multicast model. CLM offers an alternative for mp2mp communication in the cases that traditional multicast becomes expensive. The pros and cons of CLM are described and suggestions are made to alleviate the disadvantages. Furthermore different modes of operation are described: an end-to-end mode in close conjunction with SIP (Session Initiation Protocol [HAND]), as well as an interworking mode with PIM-SM and Simple Multicast. Both IPv4 and IPv6 are considered. Table of Contents 1. Introduction 2. The cost of the traditional multicast model 3. Description 4. Working modes 4.1 CLM as an end-to-end multicast routing solution 4.2. CLM as an interdomain multicast routing protocol 4.2.1. Simple Multicast 4.2.2. PIM-SM 4.3. Summary 5. Premature Cloning 6. Caching 6.1. Principle 6.2. Caching and Unicast Reroutes 6.2.1. Intra-node 6.2.2. Inter-node 7. Address list encoding 8. IP Protocol extensions 8.1. IPv4 8.2. IPv4 Alternative 8.3. IPv6 9. Gradual Deployment 10. Security Considerations 11. Acknowledgements A Hierarchical Address List Encoding A.1. Compound addresses A.2. Processing of a compound address A.3. Compound address encoding example Table of Abbreviations CLM ConnectionLess Multicast HALE Hierarchical Address List Encoding Ooms, et al. Expires October 2000 [Page 2]
Internet Draft draft-ooms-cl-multicast-02.txt April 2000 IRC Internet Relay Chat mp2mp multipoint-to-multipoint PIM-SM Protocol Independent Multicast Sparse Mode RUN Receiver Update Notification SM Simple Multicast Changes - added picture of 'cost of multicast' (2) - small changes to advantages section (3) - small changes to disadvantages section (3) - RUN moved from option to destination address field (6.1) - added section on caching and unicast reroutes (6.2) - new option format: introduction of bitmap, P-bit, A-bit and U-bit (8.1) - added seperate section on gradual deployment (9) - added paragraph on IPsec compatibility (10) 1. Introduction The main goal of multicast is to avoid duplicate information flowing over the same link. By using traditional multicast instead of unicast, bandwidth consumption decreases while the state and signalling per session increases. Apart from these two dimensions, we identify a third one: the header processing per packet. This three dimensional space is depicted in Figure 1. Ooms, et al. Expires October 2000 [Page 3]
Internet Draft draft-ooms-cl-multicast-02.txt April 2000 state&signaling per session in router ^ | | .... B | .... . | .... . | .... . | .... . +------------------..---> processing . / .... C per packet . / ..... in router . / ..... . / ..... ./ ..... /A.... / / link bandwidth Figure 1 A first method to deliver identical information from a source to n destinations is to unicast the information n times (A in Figure 1). A second method, the traditional multicast model (B in Figure 1) sends the information only once to a multicast address. In the third alternative (CLM), which is the subject of this draft, the information is sent only once, but the packet contains a list of destinations (point C). For a detailed description of CLM we refer to section 3. The three points A, B and C define a plane (indicated with dots in Figure 1): a plane of conservation of misery. All three approaches have disadvantages. The link bandwidth is a scarce resource, especially in access networks. State&signaling/session encounters limitations when the number of sessions becomes large and an increased processing/packet is cumbersome for high link speeds. Traditional multicast can move a little bit along the line A-B by switching between source and shared trees. However, this flexibility is very limited. Thus state&signaling/session is, amongst others (see section 2) a cost for the traditional multicast model. Also pure CLM encounters limitations (processing/packet), but the nice and differentiating feature of CLM is that it gives the router the choice to make its own tradeoffs. CLM has three mechanisms built Ooms, et al. Expires October 2000 [Page 4]
Internet Draft draft-ooms-cl-multicast-02.txt April 2000 in (caching, premature cloning and optimized address list encoding) that allows the router to move in this plane of conservation of misery, according to its own needs, which could be e.g. its location in the network. Caching allows a router to move from C to B, while premature cloning allows a shift from C to A. It is often argumented that it is not worthwhile to use multicast for mp2mp communication with a limited number of members, and use unicast instead. This is definitely untrue as following example illustrates: assume n residential users set up a video conference. For e.g. xDSL, GPRS or cable modem access technologies a host has no problem receiving n-1 basic 100kb/s video flows, but the host is not able to send its own video data n-1 times at this rate. Because of the limited and often asymmetric access capacity, some type of multicast is mandatory. In CLM, a host sends a packet with the addresses of the other n-1 members. The first router beyond the access link can probably process the packets in pure CLM mode since the link speed is relatively small here. Further in the network, where link speeds increase, routers can decide to maintain a cache entry for this session. Once arrived in a backbone network, where bandwidth is plentiful, the CLM packets could be prematurely cloned into multiple unicast packets to avoid the heavy header processing in the core routers. A simple but important application of CLM lies in bridging the access link for mp2mp communication. The host sends the CLM packet with the list of unicast addresses and the first router prematurely clones the CLM packet to multiple normal unicast packets. We believe that the flexibility of CLM to adapt to specific network conditions makes CLM an excellent multicast forwarding mechanism in the heterogeneous internetworks, as we currently know them. 2. The cost of the traditional multicast model The characteristics of the traditional IP multicast model are determined by its two components: the Host Group model [DEER] and a Multicast Routing Protocol. Both components add to the difference in nature between unicast and multicast. In the Host Group model, a group of hosts is identified by a multicast group address, which is used both for subscriptions and forwarding. This model has two main costs: - Multicast address allocation: The creator of a multicast group must Ooms, et al. Expires October 2000 [Page 5]
Internet Draft draft-ooms-cl-multicast-02.txt April 2000 allocate a multicast address which is unique in its scope (scope will often be global). This issue is being addressed by the Malloc working group, which is proposing a set of Multicast Address Allocation Servers (MAAS) and three protocols (MASC, AAP, MADCAP). - Destination unawareness: When a multicast packet arrives in a router, the router can determine the next hops for the packet, but knows nothing about the ultimate destinations of the packet, nor about how many times the packet will be duplicated later on in the network. This complicates the security, accounting and policy functions. In addition to the Host Group model, a routing algorithm is required to maintain the member state and the delivery tree. This can be done using a (truncated) broadcast algorithm or a multicast algorithm [DEER]. Since the former consumes too much bandwidth by unnecessarily forwarding packets to some routers, only the multicast algorithms are considered. These multicast routing protocols have the following costs: - Connection state: The multicast routing protocols exchange messages that create state for each multicast group or (source, group) in all the routers that are part of the point-to-multipoint tree. This can be viewed as a kind of signaling that creates multicast connection state, possibly yielding huge multicast forwarding tables. The name Connectionless Multicast refers to the elimination of this connection state. - Source advertisement mechanism: Multicast routing protocols provide a mechanism by which members get 'connected' to the sources for a certain group without knowing the sources themselves. In sparse-mode protocols (CBT, PIM-SM), this is achieved by having a core node, which needs to be advertised in the complete domain. On the other hand, in dense-mode protocols (PIM-DM, DVMRP) this is achieved by a "flood and prune" mechanism. Both approaches raise additional scalability issues. The cost of multicast address allocation, destination unawareness and the above scalability issues lead to a search for other multicast schemes. Recently, several changes to the Host Group Model were proposed to address these drawbacks: - Simple Multicast [PERL] uses the couple of core and multicast addresses as the group identifier. In this way core advertisement and multicast address allocation can be avoided. - In Express [HOLB], a multicast channel is identified by source and multicast addresses. Thus address allocation is not required and Ooms, et al. Expires October 2000 [Page 6]
Internet Draft draft-ooms-cl-multicast-02.txt April 2000 since there is no core, there is no core advertisement either. Creating a multicast session with multiple changing sources is implemented by using a session manager and a set of multicast channels. - In Source-Specific Multicast [HOLB2] a host joins a specific source. This approach avoids multicast address allocation as well as the need for an interdomain routing protocol. Note that all three approaches still create state&signaling per multicast session in each on-tree node. Figure 2 depicts the above costs as a function of the number of members in the group. All the costs have a hyperbolic behavior. cost of the current multicast model per member ^ | costly| OK | <-----|-----> | . | | .. | | ..|.. | | ......... | | ........ +---------------------------> | number of members v alternative=clm Figure 2 The current multicast model becomes expensive for its members if the groups are small. Small groups are typical for conferencing, gaming and collaborative applications. This is a class of applications for which CLM wants to offer an alternative. 3. Description In the Host Group Model the packet carries a multicast address as a logical identifier of all group members. In Connectionless Multicast (CLM) the packet carries all the IP addresses of the multicast session members (in the context of CLM the term 'multicast session' will be used instead of 'multicast group' to avoid the strong association of multicast group with multicast group address in traditional IP multicast). In each router the next hop for each destination is determined based Ooms, et al. Expires October 2000 [Page 7]
Internet Draft draft-ooms-cl-multicast-02.txt April 2000 on the unicast routing table. In this way for every distinct next hop the new list of destinations is determined. When there is only one destination left the CLM packet could turn into a normal unicast packet, which can be unicasted along the remainder of the route. Although not restricted to this type of multicast session, the most beneficial application of CLM is for sessions with a limited number of members (super-sparse sessions). For sessions with a large number of members (broadcast applications), CLM can be used as an interdomain multicast routing mechanism between a limited number of domains which run either PIM-SM or Simple Multicast. So, CLM will not replace the traditional multicast model, but offers an alternative for mp2mp communication where traditional multicast becomes expensive. In practice, traditional multicast routing protocols impose limitations on the number of groups and the size of the network in which they are deployed. For CLM these limitations do not exist. CLM has the following advantages: 1) No multicast address allocation required. 2) Routers do not have to maintain state per session (or per source- session). 3) No need for multicast routing protocols (nor intra- nor interdomain). CLM completely relies on the unicast routing table. 4) No core node, so no single point of failure. 5) No symmetrical paths required. Traditional multicast routing protocols create non-shortest-path trees if the paths are not symmetrical (symmetrical = the shortest path from A to B is the same as the shortest path from B to A). It is expected that more and more paths in the Internet will be asymmetrical due to traffic engineering and more policy routing, thus deviating more and more from optimal network usage. 4) Automatic reaction to unicast reroutes. CLM will react immediately to unicast route changes. In traditional multicast routing protocols a communication between the unicast and the multicast routing protocol needs to be established. In many implementations this is on a polling basis, yielding a slower reaction to e.g. link failures. Ooms, et al. Expires October 2000 [Page 8]
Internet Draft draft-ooms-cl-multicast-02.txt April 2000 5) Easy security and accounting. In contrast with the Host Group Model, in CLM all the sources know the members of the multicast session, which gives the sources the means to e.g. reject certain members or count the traffic going to certain members quite easily. Not only a source, but also a border router is able to determine how many times a packet will be duplicated in its domain. It becomes also more easy to restrict the number of senders or the bandwidth per sender. 6) Heterogeneous receivers. Besides the list of destinations, the packet can also contain a list of DiffServ bytes. While traditional multicast protocols have to create separate groups for each service class, CLM incorporates the possibility of having receivers with different service requirements within one multicast session. 7) CLM packets can make use of traffic engineered unicast paths. 8) More simple implementation of reliable protocols on top of CLM, because CLM can easily address a subset of the original list of destinations to do a retransmission. 9) Easy transition phase (section 9). However, CLM has a number of disadvantages as well: 1) Overhead. Each packet contains all remaining destinations, but the total amount of data is still much less than for unicast (payload is only sent once). A method to compress the list of destination addresses might be useful (section 7). 2) More complex header processing. Each destination in the packet needs a routing table lookup. So a CLM packet with n destinations requires the same number of routing table lookups as n unicast headers. Additionally, a different header has to be constructed per next hop. Remark however that: a) Since CLM will typically be used for super-sparse sessions, there will be a limited number of branching points, compared to non- branching points. Only in a branching point new headers need to be constructed. b) The header construction is a very simple operation: overwriting a 1-byte bitmap. c) Among the non-branching points, a lot of them will contain only one destination. In these cases normal unicast forwarding can be applied. Ooms, et al. Expires October 2000 [Page 9]
Internet Draft draft-ooms-cl-multicast-02.txt April 2000 d) By using a hierarchical encoding of the list of destinations in combination with the aggregation in the forwarding tables the forwarding can be accelerated (section 7). e) When the packet enters a region of the network where link bandwidth is not an issue anymore, the packet can be prematurely cloned. This avoids more complex processing downstream (section 5). f) The forwarding can also be enhanced by a caching mechanism (section 6). This caching allows the same forwarding behavior as current multicast. 3) Multi-access networks. Currently Ethernet does not support CLM. This means that one has to send a packet for each next-hop in a multi-access network. 4) CLM only works with a limited number of receivers. 4. Working modes The preceding sections mainly focused on the data plane, this section will focus on the control plane of CLM. CLM is mainly applicable to super-sparse multicast sessions. Besides this, we also describe how CLM can be used as an interdomain multicast routing protocol, connecting e.g. Simple Multicast or PIM-SM domains. 4.1 CLM as an end-to-end multicast routing solution If CLM is used end-to-end, it is especially useful for super-sparse sessions, e.g. conferencing, multi-party gaming, etc... In the current Internet three approaches to establish multipoint-to- multipoint sessions can be identified: - Internet Relay Chat (IRC) [OIKA]. In this approach a set of servers keeps track of the created channels and the members of these channels. The servers are also responsible for emulating the mp2mp data delivery, which relies on unicast forwarding. - Current IP Multicast Group Establishment (IGMP, Multicast Protocol, Multicast Address Allocation). In this approach the creation of the group, mainly the multicast address allocation, is the responsibility of a set of servers, while the member state is distributed over the network. The data delivery is distributed over the network and relies on multicast forwarding. - Session Initiation Protocol (SIP) [HAND]. A host takes the Ooms, et al. Expires October 2000 [Page 10]
Internet Draft draft-ooms-cl-multicast-02.txt April 2000 initiative to set up a session. With the assistance of a SIP server a session is created. The session state is kept in the hosts. Data delivery can be achieved by several mechanisms: meshed unicast, bridged or multicast. Note that for the establishment of multicast delivery, a multicast protocol and communication with Multicast Address Allocation Servers (MAAS) are still required. Both CLM and SIP address super-sparse mp2mp sessions. It turns out that CLM (a very flexible data plane mechanism) can be easily integrated with SIP (a very flexible control plane protocol). When an application decides to use CLM forwarding it does not affect its interface to the SIP agent: it can use the same SIP messages as it would use when it opted for meshed unicast forwarding. 4.2. CLM as an interdomain multicast routing protocol 4.2.1. Simple Multicast Simple Multicast provides a tunnel mechanism. This tunnel is used either to cross non Simple Multicast domains or to limit the multicast forwarding state in parts of the network. When the tunnel is used for the latter purpose, the bandwidth saving of multicast is lost in these parts of the network, i.e. parallel tunnels for the same group can exist on a specific link (Figure 3). Assume ERi are Simple Multicast Exit Routers and BRi are Backbone Routers in which one wants to avoid multicast forwarding state. S is a sender to the group and Ri are receivers. For this topology Simple Multicast will construct a first tunnel from ER1 to ER2 and a second tunnel from ER1 to ER3, yielding duplicate traffic on the link ER1-BR1. +--------BR2--------ER2------R1 | | S------ER1------BR1-------BR3--------ER3------R2 Figure 3 If the backbone routers are CLM routers the duplicate traffic can be avoided without building multicast state. The interworking is easy since ER1 knows the endpoints of both tunnels: it can send the multicast packet in CLM mode by putting ER2 and ER3 as destinations in the packet, thereby creating a point-to-multipoint tunnel. 4.2.2. PIM-SM Ooms, et al. Expires October 2000 [Page 11]
Internet Draft draft-ooms-cl-multicast-02.txt April 2000 With MSDP [FARI] the Rendezvous Points (RPs) of different PIM-SM domains discover which RPs have sources for a certain group in their domain. Similarly, a Multicast Receiver Distribution Protocol (MRDP) can be created. MRDP allows RPs to discover which RPs have receivers for a certain group in their domain. If MRDP is running and an RP has a source for a group, it can send the data in a CLM mode to the RPs which have receivers for this group. 4.3. Summary The working modes of CLM and other mp2mp communication mechanisms are summarized in Table 1. | control plane | data plane + -----------+-------------+--------------- | session | member | forwarding | creation | state | ----------+------------+-------------+--------------- IRC | servers | servers | servers (UC) multicast | servers | network | network (MC) SIP/CLM |host/server | hosts | network (CLM/UC) SM/CLM | / |exit router | network (CLM/UC) MRDP/CLM | / | RP | network (CLM/UC) Table 1 5. Premature Cloning A router can decide to prematurely clone a CLM packet, i.e. duplicate a CLM packet before its actual branching point and reduce it to a normal unicast packet. This early cloning facilitates a less complex forwarding in all downstream routers. An operator's border router can e.g. prematurely clone the CLM packets that would normally branch in the operator's domain. Or an edge router can prematurely clone CLM packets to multiple unicast packets (when CLM was only used to bridge the access link). The transformation of a CLM packet to a normal unicast packet (Premature Cloning or a CLM packet with only one destination left) requires a recalculation of the transport layer checksum (UDP and TCP checksums are calculated over the pseudo header which includes the destination address field). Note that this does not require a complete recalculation of the checksum, only a delta calculation: Ooms, et al. Expires October 2000 [Page 12]
Internet Draft draft-ooms-cl-multicast-02.txt April 2000 Checksum' = ~ (~Checksum + ~daH + ~daL + daH'+ daL') In which "'" indicates the new values, "da" the destaination address and "H" and "L" respectively the higher and lower 16 bit. 6. Caching The increased forwarding complexity is the main challenge for CLM: packet headers have to be processed at wirespeed. It was already mentioned that in major parts of the tree the normal unicast forwarding can be applied (from the moment there is only one destination address left in the packet). A method for further enhancing the forwarding is building a cache for the highest bandwidth sources. 6.1. Principle If the source supports caching it will put a number in the destination address field of the IP header: the Receiver Update Notification (RUN). Each time the set of destinations changes the source will indicate this to the downstream routers by changing the RUN. The cache will contain entries for (S, RUN). If the router receives a high bandwidth flow with a new (S, RUN) it can create a new cache entry. Unused cache entries will time out. A possible optimization is that the source increments the RUN value by 1 if the list of receivers changes. In that way the router can immediately remove the entry (S, RUN) and replace it by an (S, RUN+1) entry. When the RUN value reaches its maximum value the clearing of the cache entry still relies on the expiration of a timer. Note that a source can send to multiple sessions. In this case the source has to partition its RUN space amongst these sessions. It could be beneficial to split the 32-bit RUN number in two parts: one session identifier and one real Receiver Update Notification). Maintaining a cache may seem contradictory to the main characteristic of CLM (avoid state in the router), but it is important to note that each router can independently decide to create a cache or not. The router itself can make the tradeoff between memory and processing time. There are two ways of keeping a cache: 1) Each (S, RUN) entry has a list of next hops with the associated list of destinations. Note that this list of destinations can be a simple bitmap. When a bitmap is used it is required that the sender Ooms, et al. Expires October 2000 [Page 13]
Internet Draft draft-ooms-cl-multicast-02.txt April 2000 always lists the addresses in the same order. It could be useful to have a standardized order for this (e.g. always in increasing order). 2) Only (S, RUN) which have one next-hop (still multiple destinations) are cached. These packets do not have to change their list of destinations, so the latter information should not be kept in the cache. Both ways of applying a cache can be used in parallel. In a previous version of CLM, RUN was located in the IP option. It was moved to the destination address field to avoid UDP checksum recalculation and to allow to apply IPsec to CLM packets. For RUN a subrange of the multicast address space could be reserved. If the sender does not support the caching mechanism, it has to set RUN to a reserved value NO_SENDER_CACHE_SUPPORT (e.g. 233.0.0.0=0xe9000000). 6.2. Caching and Unicast Reroutes When a unicast route changes the CLM caches need to be updated because they still forward according to the old unicast topology. This adaptation requires two components: 1) Intra-node: Communication between the unicast routing and the CLM cache in the node where the unicast route changes. 2) Inter-node: A downstream signaling to notify the downstream caches of a unicast route change. 6.2.1. Intra-node The cache can adapt to the route change by one of following mechanisms: - Flush the complete CLM cache when a unicast reroute occurs. - Loop through the complete CLM cache to check which CLM cache entries are affected by the unicast reroute. This mechanism is computational intensive. - Each unicast route entry keeps a list of pointers to associated CLM cache entries. This mechanism consumes extra memory. - For every CLM packet one could do a route look-up for one destination. In this way the cache is updated every N packets (assume N destinations). The advantage is that the load is Ooms, et al. Expires October 2000 [Page 14]
Internet Draft draft-ooms-cl-multicast-02.txt April 2000 distributed in time, the cost being that some receivers will loose some packets. 6.2.2. Inter-node Three mechanisms can be thought of: - One could increment the RUN value on the outgoing interfaces for which the list of destinations has changed. This has the disadvantage that one needs to store a RUN per outgoing interface and do a transport layer checksum recalculation in nodes where the RUN changes. - One could send a number of packets with a special RUN value (UPDATE_DOWNSTREAM_CACHE) on the outgoing interfaces for which the list of destinations has changed. Downstream routers receiving a packet with this RUN value have to update their CLM cache. The disadvantage is that one does know how many packets to send to be sure the downstream caches are updated. When the RUN is split in two parts (see above) the updating can be limited to the affected session. - A more elegant way is to quickly compare the bitmap in the packet with the bitmaps in the CLM cache. If the bitmap in the packet equals the ORed bitmaps of the outgoing interfaces of the CLM cache nothing must be done. If a bit has changed following actions have to be performed: 1->0 (destination less): clear the bit in the bitmap of the outgoing interface 0->1 (additional destination): do a unicast route look-up 7. Address list encoding In this section the Hierarchical Address List Encoding method (HALE) is described which possibly allows to reduce the packet overhead or to increase the forwarding capacity. Given a list of IP addresses, the method iteratively separates the common prefixes of the list of IP addresses. To illustrate HALE, consider the multicast tree in Figure 4. The source S1 wants to deliver the same information to destinations D1 (ABCD), D2 (ABCE) and D3 (AFGH). For simplicity we will assume in this example that the separation of common bits is only executed on byte boundaries. The addresses of D1 and D2 have ABC in common, so it can be written as the compound address ABC{D,E}. The address of D3 and the compound address ABC{D,E} have A in common, yielding a new Ooms, et al. Expires October 2000 [Page 15]
Internet Draft draft-ooms-cl-multicast-02.txt April 2000 compound address A{BC{D,E},FGH}. D1 / /ABCD A{BC{D,E},FGH} ABC{D,E} / ABCE S1-------------------R1------------R2----------D2 \ \AFGH \ AFGH R3---------------D3 ABCD | > ABC{D,E} | ABCE | | > A{BC{D,E},FGH} AFGH | Figure 4 HALE, combined with the aggregation in the routing tables, allows to save on lookup cycles. More details on HALE and how the forwarding benefits from this encoding can be found in Appendix A. 8. IP Protocol extensions 8.1. IPv4 In IPv4 two approaches can be followed to include the list of destination addresses. Either one adds a new IPv4 option or one adds an extra header between the network and the transport layer. Since the IPv4 option field is limited to 40 bytes (of which 4 bytes are used for the option type field) only 9 destination addresses can be included. Since this is the real maximum (in the abscence of other options or other information per destination) we will limit the number of destinations to 8 to allow the bitmap to fit in 1 byte. If the number of receivers is larger than 8 multiple packets can be sent. Although for a different purpose, [AGUI] and [GRAF] already proposed an IPv4 option to carry multiple destinations. We propose the new IP option depicted in Figure 5. Ooms, et al. Expires October 2000 [Page 16]
Internet Draft draft-ooms-cl-multicast-02.txt April 2000 0 1 2 3 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |1 0 0| TYPE | LENGTH |A|U|RES|P|D|ENC| BITMAP | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | (Encoded) List of Ports, DS Bytes and Addresses | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 0 1 2 3 Figure 5 TYPE = number for this IPv4 option LENGTH = total length of the option in bytes A = anonymity bit: if this bit is set the destination addresses for which the bit in the bitmap is zero have to be overwritten by zero (receiver shouldn't know all other receivers). U = unicast transformation bit: if this bit is set a router is allowed to reduce the CLM packet to a unicast packet when there is only one destination left. RES = Reserved. P = port bit: if this bit is set the packet will contain a (encoded) port for each destination. D = DSCP bit: if this bit is set the packet will contain a (encoded) DS-byte for each destination. ENC (2 bits) = encoding method used on the list of ports, DS bytes and destination addresses. Following encoding methods are defined: (P,D,ENC) (0,0,00) = no encoding: flat list of destination addresses (0,0,01) = hierarchical address list encoding (Appendix A.3) (0,1,00) = no encoding and DSCP per destination (Figure 6) BITMAP = every destination has a corresponding bit in the bitmap to indicate whether the destination is still valid on this branch. The least significant bit corresponds to the first destination. Figure 6. shows the 'List of Ports, DS Bytes and Addresses' in case (P,D,ENC) = (0,1,00). Ooms, et al. Expires October 2000 [Page 17]
Internet Draft draft-ooms-cl-multicast-02.txt April 2000 0 1 2 3 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | destination address 1 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | . . . | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | destination address N | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | DS byte 1 | DS byte 2 | ... | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | DS byte N | padding | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Figure 6 8.2. IPv4 Alternative Instead of using the IP option field one could add an extra header between the network and the transport layer. This header is depicted in Figure 7. The IP header will carry the protocol number PROTO_CLM. 0 1 2 3 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |VERSION|UNUSED | PROT ID | LENGTH | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | CHECKSUM |A|U|RES|P|D|ENC| RESERVED | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | BITMAP | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | (Encoded) List of Ports, DS Bytes and Addresses | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Figure 7 VERSION = CLM version number PROT ID = specifies the protocol on the transport layer LENGTH = length in bytes of the CLM header. CHECKSUM = it is not clear yet whether a checksum is needed (ffs). If only one bit is wrong it can still be useful to forward the packet to N-1 correct destinations and 1 incorrect destination. On the other hand when the header info is used to install a cache (see section 6) one can not allow that packets are permanently forwarded Ooms, et al. Expires October 2000 [Page 18]
Internet Draft draft-ooms-cl-multicast-02.txt April 2000 wrongly. One approach could be to provide a checksum per destination. The other fields were described earlier. 8.3. IPv6 Since IPv6 allows more flexibility in adding options (e.g. no limitation on the size), there is no limitation in terms of encoding on the number of destinations that can be put in a packet. However, since a packet can only be sent after all the destinations have been processed, packets with a lot of addresses will experience a larger delay. For IPv6 the overhead will be larger since the addresses are longer. Note however that IPv6 probably allows an encoding with better compression because of the geographical/provider distribution of addresses. Moreover if CLM is used as an interdomain multicast mechanism only the locator part of the address needs to be considered. 9. Gradual Deployment At least two schemes for gradual introduction of CLM can be thougth of: 1) CLM-capable routers can be interconnected by tunnels (MBone approach). 2) a router could discover which neighbours are not CLM-capable and will prematurely clone CLM packets directed to these neighbours. A mechanism (protocol/protocol extension) to discover CLM capability of a neighbour is ffs. Note: Following rules apply to routers that do not understand CLM packets: - A router that does not know the CLM option: packets with unrecognized options must be passed through unchanged ([BAKE]). - A router will not send ICMP errors for packets with a multicast address in the destination address field ([BAKE]). 10. Security Considerations Since a packet contains every destination, it is much more easy to restrict multicast sessions to certain receivers. It also allows ISPs to check, when a packet enters their network, how much resources Ooms, et al. Expires October 2000 [Page 19]
Internet Draft draft-ooms-cl-multicast-02.txt April 2000 this packet packet will consume in their network. In the end-to-end mode it is also easy to restrict the number of senders or to restrict/monitor the bandwidth of a sender. IPsec can be applied to CLM packets in order to provide various security services. We hereby suggest a (non exhaustive) list of possible scenarios for applying IPsec (ie. AH or ESP) to CLM packets. If the list of destinations resides in the IPv4 option, one can provide source authentication and end-to-end packet integrity by applying AH in transport mode and defining the IPv4 option as a mutable field ([KENT]). Obviously, the drawback is that an attacker could maliciously modify the values in the IPv4 option (eg. destination addresses, bit fields, bit map, ...). Considering that only the bitmap field is subject to modifications in the IPv4 option, one could extend the integrity protection onto the other fields by splitting the IPv4 option into two separate options : one for the bitmap and one for the other fields. The bitmap option is then defined as a mutable field while the second option is defined as non-mutable. The other fields can then be protected with IPsec. Data confidentiality could also be provided with the use of IPsec ESP, which can be combined with AH to protect the packet header as discussed above. Note that CLM packets on which IPsec has been applied cannot be transformed into unicast packets (hence their 'U' bit must be cleared by the sender). If the list of destinations is protected by IPsec, anonymity cannot be provided either (hence the 'A' bit must be cleared by the sender). In order to make use of IPsec, an SA must be agreed upon between the participants using some automatic method such as IKE or manual configuration. In its current state, IKE cannot be used to set up such a single SA between multiple parties, hence manual configuration would be required. 11. Acknowledgements The authors would like to thank Olivier Paridaens, Emmanuel Desmet, Hans De Neve and Miroslav Vrana for the fruitful discussions and/or their thorough revision of this document. Some of the changes in this version of the draft were inspired by fruitful discussions with Yuji Imai and Rick Boivie. Ooms, et al. Expires October 2000 [Page 20]
Internet Draft draft-ooms-cl-multicast-02.txt April 2000 A Hierarchical Address List Encoding (HALE) A.1. Compound addresses A list of addresses can be compressed into a compound address by writing common prefixes only once, followed by a list of their suffixes. We used following syntax to represent compound addresses: <compound_address> ::= prefix "{" <suffix_list> "}" <prefix> ::= [<address_fragment>] <suffix_list> ::= [<suffix_list> ","] <suffix> <suffix> ::= <compound_address> | <address_fragment> <address_fragment> ::= [<address_fragment>] <symbol> <symbol> ::= [A-Z] in our example, one bit in practice (can also be a nibble or octet) Let's take the following list of addresses as an example: ABCD, ABCE, AFGH The addresses all have a common prefix A, so we can write A once followed by the list of suffixes BCD, BCE and FGH. i.e. A { BCD, BCE, FGH } Two of these suffixes share a common prefix BC, so we obtain: A { BC { D, E }, FGH } A.2. Processing of a compound address Following pseudo code parses a compound address and issues a minimum amount of lookup() calls to a routing table engine. We assume the lookup takes a symbol (e.g. one bit) as argument and returns a pointer to it's internal (e.g. tree) structure which can be passed to a next lookup. The parser maintains a stack of such indices. We assume that a meta symbol also denotes the number of non-meta symbols that follow (see encoding in A.3.). index=routing_table_root; /* routing table entry point */ skip=0; /* flag used to skip over irrelevant * parts of the compound address */ getch(meta); /* get first meta symbol. Only the * length is used */ while(1) { Ooms, et al. Expires October 2000 [Page 21]
Internet Draft draft-ooms-cl-multicast-02.txt April 2000 len=LEN(meta); /* number of non-meta symbols that * follow */ for (i=0; i<len; i++) { /* parse len symbols as * address_fragment */ getch(symbol); /* read next symbol from the compound * address */ if (!skip) { lookup(symbol, &index); /* search in the routing table, using * symbol, starting from index, storing * the resulting location back in index */ if (IS_LEAF(index)) { /* the next-hop is determined */ forward(index); /* forward packet to this nexthop */ skip=stack_pointer; /* skip to end of this suffix */ } } } getch(meta); /* get next meta symbol */ if (IS_OPEN_BRACKET(meta)) push(index); /* push index on the stack */ if (skip==stack_pointer) skip=0; /* we've skipped the list_element */ if (IS_CLOSE_BRACKET(meta)) pop(index); /* pop index from the stack */ if (IS_COMMA(meta) && skip) index=stack_pointer; /* take the index on top of the stack */ } A.3. Compound address encoding example Below is a possible encoding scheme for a compound address which limits the amount of overhead. CLM option: Ooms, et al. Expires October 2000 [Page 22]
Internet Draft draft-ooms-cl-multicast-02.txt April 2000 0 1 2 3 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |1 0 0| TYPE | LENGTH |A|U|RES|P|D|ENC| BITMAP | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | NUM META | meta symbols ... | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | meta symbols + padding | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | address_fragments, not byte aligned | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ NUM META = number of meta symbols Meta symbol: 0 1 2 3 4 5 6 7 +-+-+-+-+-+-+-+-+ |X|sym| length | +-+-+-+-+-+-+-+-+ X = unused sym = meta symbol 00 = open bracket 01 = close bracket 10 = comma 11 = close bracket followed by comma length = number of bits of the address_fragment (symbol) following this meta symbol. References [AGUI] L. Aguilar, "Datagram Routing for Internet Multicasting", Sigcomm84, March 1984. [BAKE] F. Baker, "Requirements for IP Version 4 Routers", RFC1812, June 1995. [DEER] S. Deering, "Multicast Routing in a datagram internetwork", PhD thesis, December 1991. [FARI] D. Farinacci, "Multicast Source Discovery Protocol", draft- farinacci-msdp-00.txt, June 1998. Ooms, et al. Expires October 2000 [Page 23]
Internet Draft draft-ooms-cl-multicast-02.txt April 2000 [GRAF] C. Graff, "IPv4 Option for Sender Directed Multi-Destination Delivery", RFC1770, March 1995. [HAND] M. Handley, H. Schulzrinne, E. Schooler, J, Rosenberg, "SIP: Session Initiation Protocol", RFC2543, March 1999. [HOLB] H. Holbrook, "Express Multicast: Making Multicast Economically Viable". [HOL2] H. Holbrook, B. Cain, "Source-Specific Multicast for IP", draft-holbrook-ssm-00.txt, March 2000. [KENT] S. Kent, R. Atkinson, "Security Architecture for the Internet Protocol", RFC2401, November 1998. [OIKA] J. Oikarinen, D. Reed, "Internet Relay Chat Protocol", RFC1459, May 1993. [PERL] R. Perlman, "Simple Multicast: A design for Simple, Low-overhead Multicast", draft-perlman-simple-multicast-02.txt, February 1999. Authors Addresses Dirk Ooms Alcatel Corporate Research Center Fr. Wellesplein 1, 2018 Antwerpen, Belgium. Phone : 32 3 2404732 Fax : 32 3 2409879 E-mail: Dirk.Ooms@alcatel.be Wim Livens Colt Telecom Zweefvliegtuigstraat 10, 1130 Brussel, Belgium. Phone : 32 2 7901705 Fax : 32 2 7901711 E-mail: WLivens@colt-telecom.be Olivier Paridaens Universite Libre de Bruxelles, Service Telematique et Communication Bd du Triomphe, CP 230, 1050 Brussels, Belgium. Phone : 32 2 6505703 Fax : 32 2 6293816 E-mail: paridaens@helios.iihe.ac.be Ooms, et al. Expires October 2000 [Page 24]