INTERNET DRAFT Ali Boudani, Bernard Cousin Expires: April 2005 IRISA-France October 2004 Simple Explicit Multicast (SEM) Status of this Memo By submitting this Internet-Draft, I certify that any applicable patent or other IPR claims of which I am aware have been disclosed, or will be disclosed, and any of which I become aware will be disclosed, in accordance with RFC 3668." Internet Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and working groups. Note that other groups may also distribute working documents as Internet-Drafts. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsolete by other documents at anytime. It is inappropriate to use Internet Drafts as reference material or to cite them other than as "work in progress." The list of current Internet-Drafts can be accessed at http://www.ietf.org/ietf/1id-abstracts.txt. The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html. Abstract In this document, we propose a new multicast protocol called SEM (Simple Explicit Multicast) or simple Xcast. This protocol uses an efficient method to construct the multicast tree and deliver multicast packets. In order to construct the multicast tree, this protocol uses the same mechanism as Xcast+. For the delivery of multicast packets it uses the mechanism of branching routers similar to the mechanism used in REUNITE I and REUNITE II. Table of Contents: 1. Introduction 1.1 Terminology 2. SEM Overview 3. Control Plane in SEM 3.1 Receiver Considerations 3.2 Router Considerations 3.3 Sender Considerations 4. SEM messages 4.1 Encoding for SEM BRANCH messages 4.2 PREVIOUS_BRANCH 5. Packet format in SEM 6. comparison between ISM, SSM, Xcast, Xcast+, REUNITEII and SEM 6.1 Differences between Xcast+, REUNITE and SEM 6.2 Cost Analysis of ISM, SSM, Xcast, Xcast+, REUNITE and SEM 6.3 Limitations of Xcast protocol Boudani & Cousin [Page 1] INTERNET-DRAFT Simple Explicit Multicast (SEM) October 2004 7. Applicability and Other Considerations 8. Acknowledgments 9. Appendices 9.1 Appendix I: Explicit Multicast Using MPLS 9.2 Appendix II: Manager Router to Construct The Multicast Tree References 1. Introduction Recently several multicast mechanisms were proposed that scale better with the number of multicast sessions than traditional multicast does[5]. Explicit Multicast (Xcast)[1] is a newly proposed multicast scheme to support a very large number of small multicast groups. Xcast+ [2] is an enhanced scheme for the support of receiver initiated join in explicit multicast which complements the existing Xcast. This is achieved by adding an IGMP join at receiver side and sending the join request through source-specific join to the sender, and then by explicitly encoding the list of addresses of the multicast routers, instead of receiver addresses. Xcast+ encoding of the destination list in IPv4 and IPv6 are the same as Xcast. Whereas Xcast can support a very large number of small multicast groups, Xcast+ can support a very large number of medium size multicast groups. In all the newly proposed protocols the source knows the addresses of all the destinations before sending packets. We think that when having medium group size the header processing in every router for all packets traveling from the source to the destinations is very expensive. This document describes a new protocol called Simple Explicit Multicast (SEM) which is an efficient method to construct and forward multicast packets. In order to construct the multicast tree, it uses the same mechanism of Xcast+. Instead, for multicast packets delivery, it uses the branching routers mechanism similar to that used in REUNITE II[4]. Packets will be travel from a branching router to another following the tree that have been constructed by a control plane that uses the Xcast+ mechanism. Using SEM will result in the following benefits : - From the viewpoint of receivers, procedures in the control plane are the same to existing ISM and SSM[7, 8] schemes. Therefore, SEM receivers do not need to use additional control to join in SEM session. This means that the control plane of SEM is compatible with the existing ISM and SSM. A receiver that is an IGMP capable host does not need to be a SEM capable host. - There can be an increase of the number of receivers, which means Simple Xcast can support larger size number of members compared to that of existing Xcast and Xcast+. Comparing with Xcast and Xcast+, the packet header Boudani & Cousin [Page 2] INTERNET-DRAFT Simple Explicit Multicast (SEM) October 2004 processing in SEM is minimized and thus, SEM can support larger size number of members. - Similar to ALM (Application Level Multicast) and Overlay Multicast schemes, SEM supports both multicast and unicast, where multicast is used in sub-net and unicast is used between branching routers. Therefore, this will result in a more efficient and scalable mechanism that allow to increase the number of receivers in a sub-net. - When the scalability in ISM schemes is considered, one of the main issues may be complexity of multicast tree construction between multicast routers on Internet backbone. Because SEM uses the multicast scheme in a sub-net level only (the use of the multicast address is so simple in all other cases) , deployment and management are easy and simple, even if multicast scheme is used. - This protocol facilitates the use of MPLS to ensure multicast traffic engineering.(see appendix I) Note - SEM means the support of receiver initiated IGMP join and leave messages, the use of encoded address of the multicast routers in messages used for constructing the multicast tree, and the use of a new message containing the next and the previous hop branching router addresses. Previous hop branching router is the router that has sent the message. 1.1. Terminology The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in RFC 2119. In addition, this document frequently uses the following terms: ISM Internet Standard Multicast SEM Simple Explicit Multicast SSM Source Specific Multicast Xcast Explicit Multicast Xcast+ Explicit Multicast extension Standard multicast address Multicast address which is used in ISM and SSM Source-specific join A join to be sent to sender from mulicast sub-net router It does not mean the source-specific join of PIM-SSM 2. SEM Overview In SEM, a receiver (like in Xcast+) initiates IGMP join message Boudani & Cousin [Page 3] INTERNET-DRAFT Simple Explicit Multicast (SEM) October 2004 (Current version of IGMP, IGMPv3[9] can support join of (S, G)). When a multicast router receives the request, it sends source- specific join to the sender. The sender keeps track of the addresses of routers that send source-specific join messages in the multicast session. The sender encodes the list of router addresses in a BRANCH message. The role of the BRANCH message is to determine routers acting as branching routers in the multicast tree. Branching router in SEM mean a router where a packet arrive in an interface and should be forward to multiple interfaces (according to the next hop toward the destination routers). The sender router parses the header, partitions the destinations based on each destination's next hop, and send the BRANCH message to each of the next hops. These procedures comply with the data plane for existing Xcast+ (encoding the addresses of multicast routers in the data packets, instead of addresses of receivers). For example, suppose that B, C, D, E, F and G are trying to receive packets distributed from A in Figure 1 below: B / R4 -- C / D / / A --- R1 --- R2 --- R3 R8 -- E \ / \ \ / F R5 --- R6 --- R7 \ \ R9 -- G Figure 1 This is accomplished as follows: B, C, D, E, F and G initiate IGMP join. When R4, R8 and R9 receive the IGMP request, they send source-specific join to A. A sends a BRANCH message with the list of multicast routers (R4, R8 and R9) in its SEM header to the first router, R1. SEM encoding of the destination list in IPv4 and IPv6 are the same as Xcast+. The BRANCH message is encoded like following: [IP header | SEM header] where IP header contains the source address S and the group address G and SEM header contains the list of all destination routers and the address of the previous hop branching router. Therefore, ignoring details, the BRANCH message that A sends to Boudani & Cousin [Page 4] INTERNET-DRAFT Simple Explicit Multicast (SEM) October 2004 R1 looks like following: [ src = A | group address = G | dest = R4 R8 R9 | previous hop branching router] (note that previous hop branching router initial value is the source address S itself). When R1 receives this packet, it needs to properly process the SEM header of BRANCH message. The processing that a router does on receiving one of these BRANCH messages is as follow: At each router in the path to the destinations, the router checks if it is a branching router for the group (it is a branching router if there are different next hops for the destinations encoded in SEM header of BRANCH message). If all destinations have the same next hop then the router is not a branching node and no further action is taken and the same BRANCH message is forwarded to the unique next hop that has been calculated. If it is not the case and there are multiple next hops for the destinations, then an entry is created at the router indicating that the router is a branching router. The entry created at the router contains the source address, the multicast address for the group and the list of unicast addresses for next hop branching routers(the list is empty at the beginning). Then the router should send the BRANCH message to each of the next hop branching routers. The same analysis is repeated at each branching router. When a router discovers that it is a branching router (it discovers that because an entry will be created), it replaces the previous hop branching router field in the BRANCH message with its proper address before re-sending the BRANCH message. It also sends a PREVIOUS_BRANCH message to the router that its address figure in previous hop branching router field in the BRANCH message. The PREVIOUS_BRANCH message received by the previous hop branching router will update the null list at the corresponding entry (S,G) with the address of the next hop branching router (it can be extracted from IP header of the message). If an address to a next hop branching router already exists at the entry then the list should be simply updated and the new address should be added. (for an optimization issue, the PREVIOUS_BRANCH message will not be generated if there is no changing in the corresponding entry). At the end of this operation, we will obtain a path to each destination router using the next hop branching router addresses. A BRANCH message is sent periodically to ensure the maintenance of the tree. A timer is associated with the group entry at the source. If a new join message arrived, then a new BRANCH message should be sent and the timer is set to zero. It should be noted that another method is to send a BRANCH message containing only the router who sent the last join Boudani & Cousin [Page 5] INTERNET-DRAFT Simple Explicit Multicast (SEM) October 2004 message. In that case, the entries in the branching routers may not change. The result of this tree maintenance is that in each branching router an entry corresponding to each group exist. this entry contains the previous and the next hop branching router for that router. When the source wants to send a packet to a group, the G entry is examined. The packet is forwarded directly to the next hop branching routers in the G entry. The packet is unicast to the next hop branching router with a payload containing the G address(see section 5). When the subsequent branching routers receive the packet, the same operation is repeated. So if the router receiving the packet is not the next hop branching router for that packet then it forwards the packet in unicast to the specific next hop branching router. When the packet arrives at the router in the destination field, (to its next hop branching router), it will be then replicated and sent to each router the next ho branching routers (their addresses figure in the G entry). When the packet arrives to the last destination routers, then packet destination field should be replaced with the G address to ensure that it will be delivered through multicast to all receivers in the sub-net. When a router discovers that there is no receivers, for a group in its directly connected sub-net, who wants to receive packets from the the source S, it will send a leave message toward the source for the group. A new BRANCH message is generated. For the use of MPLS : a previous hop branching router in each entry can be added. The construction of MPLS LSP should be deduced from the entries. This is FFS. 3. Control Plane in SEM In SEM, a standard multicast address is used to identify a multicast session. A sender creates and advertises a multicast session with standard multicast address. In order to identify SEM session easily, compared with ISM sessions, special multicast address range (e.g., similar with the SSM address range, 232/8) can be used. And thus, advertisement method using web pages will be useful. These allocations of SEM multicast addresses and the advertisement method of SEM multicast session are outside the scope of this document. Figure 2 describes the whole control plane for SEM. +-----------+ Receiver Boudani & Cousin [Page 6] INTERNET-DRAFT Simple Explicit Multicast (SEM) October 2004 | IGMPv3 app| Source Discovery --------------------------------------------------------------- | IGMPv3 | IGMPv3 Host Reporting +-----------+ | source-specific host report (S, G) | -------------------------------------------------------------- v +-----------+ SEM Capable Router | IGMPv3 | IGMPv3 Querier -------------------------------------------------------------- | Unicast | Unicast Routing +-----------+ | source-specific join (S, G) ... and | source-specific leave (S, G) | v +-----------+ SEM Capable Sender | Unicast | +-----------+ Figure 2 Control plane for SEM 3.1. Receiver Considerations In SEM, like Xcast+, receivers send IGMP join (or leave) to their multicast router in their sub-net they in order to receive SEM packets, and then the join requests are sent through source- specific join to the sender. It is necessary for receivers to know the address of the sender. Current version of IGMP, IGMPv3 can support source discovery and source- specific host membership report. In addition, IGMPv3 leave operation is also applicable to leave a multicast session dynamically. That is, SEM receivers don't need to use additional control to join or to leave a SEM session. A receiver that is an IGMPv3 capable host does not require modifications to be an SEM capable host. So,this requirement for receivers can be easily achieved. 3.2. Router Considerations In SEM, the router that receives the source-specific IGMP host membership report (S, G) sends source-specific join (S, G) to the sender. Unlike source-specific join of PIM-SSM, the join message is sent to the sender directly with unicast address using unicast routing,so intermediate routers don't need to keep the state information of the multicast session (S, G). The sender obtains the addresses of multicast routers that receive source-specific IGMP host membership report for multicast session Boudani & Cousin [Page 7] INTERNET-DRAFT Simple Explicit Multicast (SEM) October 2004 (S, G) from the source-specific joins of SEM. Of course, SEM scheme is extended from Xcast+ and REUNITE II, so all routers on the unicast path between multicast senders and receivers MUST be a SEM capable router to process and forward SEM packets. Each SEM router should be capable to process BRANCH and PREVIOUS_BRANCH messages. It should also be capable to create and update group entries. 3.3. Sender Considerations In SEM, when a sender receives a source-specific join (S, G), it encodes SEM header of the BRANCH message including addresses of routers that have sent source-specific join (S, G). These router addresses are extracted from source addresses of the source-specific join (S, G) packets. Encoding method is very similar to that described in Xcast+. Unlike receivers, a sender MUST be SEM capable host. Also when the sender transmits a packet to a group G, the destination of the packet is the corresponding G entry next hop routers. It should be noted that the sender keep the information about the group in an entry that contain the group address and the addresses of all destinations. 4. SEM messages 4.1. BRANCH message When the sender receives join messages, the sender explicitly encodes the list of addresses of the multicast routers that have received source-specific IGMP host membership report in a BRANCH message. The source address field of the IP header contains the address of the sender. The destination address field carries the standard multicast address. The list of destinations will be encoded in a separate header. the SEM header contains also the previous hop branching router field (with initial value the source address S). The IP header will carry the protocol number PROTO_SEM. Like Xcast+, however, sender explicitly encodes the list of addresses of the multicast routers that have sent source- specific join message in SEM header. 4.2. PREVIOUS_BRANCH message The PREVIOUS_BRANCH is a SEM message sent by a branching router to its previous hop branching router. It is used to inform the the previous hop branching router about the the next hop Boudani & Cousin [Page 8] INTERNET-DRAFT Simple Explicit Multicast (SEM) October 2004 branching router.(the next hop branching router router is the one who sent the message). When receiving this message the entry corresponding to the group with G address is modified. The entry is updated with the address of the next hop branching router. This message contain the IP header (the source is the router it self and the destination is the previous branch router). The SEM header of the message contains only the G address. 5. SEM Packet format Each SEM packet is as follow: [ IP header | Group address | Transport header | Payload ] The IP header contains the source address and the destination address of the next hop branch router. Join and leave messages could be normal SSM join and leave messages. Thus, in order to not make confusion between SSM and SEM, an interval of addresses could specified to be used only with SEM protocol. 6. comparison between ISM, SSM, Xcast, Xcast+, REUNITEII and SEM 6.1. Differences between Xcast+, REUNITE and SEM The major difference between Xcast+ and SEM is that Xcast+ encodes the list of destinations in each packet while SEM uses this mechanism only with the BRANCH message. In both protocols the packet will follow the unicast path between the sender and the destination but in SEM the packet will follow a unicast path between branching routers. This seems a good solution in order to optimize the header processing in every router. REUNITE II uses branching routers also like SEM but there are some differences between the two protocols. SEM uses a multicast address to identify a group of destinations. The sender will be able to provide statistics about the destinations. In REUNITE the sender will not be aware about the receivers. It knows only about the first receiver if the next hop router for all receivers is the same. In REUNITE, when the first router that already joined a group want to leave the group, the tree maintenance will be very complex. In comparison there are larger number of control messages with REUNITE than SEM. In REUNITE, once the tree is constructed, the packets will follow an explicit path from the sender to all destinations. It is not the case with SEM, where the packets should follow only the unicast paths from a branching router to another. The join message in SEM is not periodic like in REUNITE. Note Boudani & Cousin [Page 9] INTERNET-DRAFT Simple Explicit Multicast (SEM) October 2004 that if routing is asymmetric, even subsequent refresh join messages can trigger BRANCH messages in REUNITE. That is not the case in SEM. Finally, since SEM uses the multicast addresses, The control plane of SEM is compatible with the existing ISM and SSM. The Join and leave latency still a major problem with SEM. While Xcast did not specify any control plane it suggested that using SIP protocol[6] can be integrated as a flexible control plane protocol. Xcast+ has introduced the IGMP model and Source specific join and leave for the receiving routers. We used the same join and leave messages in SEM. Note that if routing is asymmetric, the same limitations figure with REUNITE also. This limitations figure because we think that the source should be always aware about the unicast address for every destination. By this way the leave and join messages should reach the source and not only the multicast tree. 6.2. Cost Analysis of ISM, SSM, Xcast, Xcast+, REUNITEII and SEM Costs of ISM, SSM, Xcast, Xcast+, REUNITE II and SEM schemes can be summarized as described in Table 1. As a result of analysis, while SEM has some control plane overhead compared to Xcast and Xcast+, its cost of packet header processing is minimized. While REUNITE has some advantages, it has a higher protocol complexity and larger number of control messages. 6.3 Limitations of Xcast protocol Two major limitations to the Xcast (Xcast+) protocol are: 1- When a receiver leaves the group, it sends an IGMP leave message to the source S. S eliminates the receiver address and further packets will not be sent to this receiver. Meanwhile all packets sent (during the transition period) by the source with the list containing the receiver address will be received by the receiver which will drop it. SEM resolves this problem since further packets contains only the branching nodes addresses. 2- Xcast packets can not be fragmented: If a router need to fragment an Xcast packet, Data may be loosed since fragmented Xcast packets may be not treated by subsequent (or the router itself) as Xcast packets. SEM does not need to fragment packets, since it will be treated exactly as TCP or UDP packets. But routers may need to fragment the branch message. This issue is left for further study (see appendix II). 7. Applicability and Other Considerations The application areas for SEM include conferences, multi-player Boudani & Cousin [Page 10] INTERNET-DRAFT Simple Explicit Multicast (SEM) October 2004 games, collaborative working, etc., in light of the number of members, however, SEM is very efficient and more scalable and simple than other protocols. Table 1 Cost Analysis of ISM, SSM, Xcast and Xcast+ +----------------------+-----+-----+-----+------+-----+---+ | | ISM | SSM |Xcast|Xcast+|REUN.|SEM| +----------------------+-----+-----+-----+------+-----+---+ | Multicast | h | m | n | m | l | m | | Address Allocation | | | | | | | +----------------------+-----+-----+-----+------+-----+---+ | Multicast Routing | h | h/m | l | l | l | l | | State Management | | | | | | | +----------------------+-----+-----+-----+------+-----+---+ | Control | h | h/m | n | m | m | l | | Overhead | | | | | | | +----------------------+-----+-----+-----+------+-----+---| | Overhead by Increase | l | l | h | l | l | l | | of Receivers | | | | | | | +----------------------+-----+-----+-----+------+-----+---+ | Extra Header | 1 | l | h | h/m | n | l | | Processing Overhead | | | | | | | +----------------------+-----+-----+-----+------+-----+---+ | Deployment | h | m | l | l | l | l | | | | | | | | | +----------------------+-----+-----+-----+------+-----+---+ | Join and Leave | | | | | | | | Latency | m | l | h | h | m | h | +----------------------+-----+-----+-----+------+-----+---+ h: high m : medium l : low or none n : not applicable 8. Acknowledgments The SEM protocol draws on a variety of prior work on alternative approaches to IP multicast, including the Xcast[1], Xcast+[2], REUNITE[3,4,5]. 9. Appendices 9.1 Appendix I: Explicit Multicast Using MPLS It is quite clear that having a previous hop and next hop in each branching routers all the path from a sender to the destinations will be the first step to MPLS multicast traffic engineering. Once the tree is constructed, the sender will know the egress routers and also the receivers will know about the ingress router (witch is the sender). When a multicast packet arrives at the root of an MPLS multicast Boudani & Cousin [Page 11] INTERNET-DRAFT Simple Explicit Multicast (SEM) October 2004 tree (the sender), an MPLS label is imposed to the packet. Then at the subsequent hops, the LSR looks up the forwarding table with the incoming label, finds out all the downstream routers and corresponding outgoing labels, makes the duplications, and forwards them to the downstream routers with the outgoing labels. The branching routers should act as the LSRs for the MPLS domain. It should be noted that we are not supposing that MPLS will be introduced just to serve multicasting. We are supposing that MPLS will be widely used for unicast and thus it will be normal, since it will exist anyway, to be used for multicast routing at the same networks. 9.2 Appendix II: Manager Router to Construct The Multicast Tree In [10], we proposed a novel approach to construct multicast trees in MPLS networks. We used a special router called NIMS (Network Information Manager System) as a core router that receive join and leave messages from all destinations. This NIMS will calculate the multicast tree and then send branch messages to branching node routers. MPLS tunnels will be use for multicast traffic between branching node routers. The NIMS scheme could be used also in SEM. All join and leave messages could be sent to the NIMS and then this router will calculate the tree and determine the multicast branching node routers. This procedure permanently used to keep the tree maintenance. References [1] R. Boivie et al., Explicit Multicast (Xcast) Basic Specification, , 2000. [2] M. Shin et al., Explicit Multicast (Xcast+) Supporting Initiated Join, , 2001 [3] I. Stoica, et al., "REUNITE: A recursive Unicast Approach to Multicast", http://www.ieee-infocom.org/2000/papers/613.ps. [4] I. Stoica and al., REUNITE: A Recursive Unicast Approach to Multicast, Tech. Rep., Carnegie Mellon University, Dec. 1999, http://www.cs.cmu.edu/~hzhang/multicast/ [5] D. Ooms, Taxonomy of xcast/sgm proposals, , 2000 [6] B. Van Doorselaer et al., SIP for the establishment of xcast-based multiparty conferences, , 2000 [7] H. Holbrook and B. Cain, Source-Specific Multicast for IP, , 2000 [8] S. Bhattacharyya et al., A Framework for Source-Specific IP Multicast Deployment, , 2000 [9] H. Holbrook and B. Cain, Using IGMPv3 for Source Specific Multicast, , 2000 [10] A. Boudani and B. Cousin, An effective Solution for Multicast Scalability: The MPLS Multicast Tree (MMT),, 2001 Authors Addresses Ali Boudani IRISA/INRIA Rennes Campus Universitaire de Beaulieu Avenue du General Leclerc 35042 Rennes France Phone : (33) 02 99 84 25 37 Fax : (33) 02 99 84 25 29 E-mail : aboudani@irisa.fr Bernard Cousin IRISA/INRIA Rennes Campus Universitaire de Beaulieu Avenue du General Leclerc 35042 Rennes France Phone : (33) 02 99 84 73 33 Fax : (33) 02 99 84 71 71 E-mail : bcousin@irisa.fr Copyright Statement Copyright (C) The Internet Society (2004). This document is subject to the rights, licenses and restrictions contained in BCP 78, and except as set forth therein, the authors retain all their rights." "This document and the information contained herein are provided on an "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE." Expiration Date: April 2005