Internetworking Over NBMA Yasser Seif INTERNET-DRAFT Hani Harb October 1998 Multicast Manager (MCM): A Multipoint-to-Multipoint Multicasting Protocol for ATM Status of this Memo This document is an Internet-Draft. 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.'' To learn the current status of any Internet-Draft, please check the ``1id-abstracts.txt'' listing contained in the Internet-Drafts Shadow Directories on ftp.ietf.org (US East Coast), nic.nordu.net (Europe), ftp.isi.edu (US West Coast), or munnari.oz.au (Pacific Rim). Abstract This document describes MCM, a protocol for controlling a shared ATM multicast tree supporting Mutipoint-to-Multipoint communication. The protocol guarantees that there is no cell interleaving at any group receiver. No cell buffering inside the network is required, and all cell forwarding is performed at the ATM layer. 1. Introduction Multicasting is the process whereby a source host or protocol entity sends a packet to multiple destinations simultaneously using a single, local 'transmit' operation. Unicasting and Broadcasting may be considered to be special cases of Multicasting (with the packet delivered to one destination, or 'all' destinations, respectively). Expires May 1999 [Page 1] INTERNET-DRAFT MCM October 1998 Asynchronous Transfer Mode (ATM) is a connection-oriented non- broadcast multiple access (NBMA) technology which is increasingly being used for local and wide area networking. A Virtual Circuit (VC) has to be established between participating hosts on an ATM network before transfer of data can take place. Unicast communication is over a point-to-point (unidirectional or bidirectional) VC. The ATM Forum's signalling specifications UNI 3.0/3.1 do not provide the multicast address abstraction. Multicatsing is supported through point-to-multipoint unidirectional VCs. The key limitation is that the sender must have prior knowledge of each intended recipient, and explicitly establish a VC with itself as the root node and the recipients as the leaf nodes. The absence of ATM multicast address presents a problem of mapping a layer 3 multicast address to the corresponding set of ATM addresses. The ATM working group of the Internet Engineering Task Force (IETF) has proposed the Multicast Address Resolution Server (MARS) protocol as a solution to this problem [1]. The fundamental limitations of the MARS are: O Only point-to-multipoint, unidirectional VCs may be established. O Only the root (source) node of a given VC may add or remove leaf nodes. O The source or server needs to know which receivers are listening to which multicast group. This incurs a management overhead leading to scalability problems for very large multicast groups. One of the main problems to be solved is the cell interleaving problem which is defined as the ability of the receiver in a multicast group to distinguish cells coming from different concurrent senders. Potential solutions to the cell interleaving problem with AAL5 have been discussed in [8]. The development of traffic management schemes for multipoint-to- multipoint connections is still under study. Several proposal have been introduced such as SEAM [SEAM], and SMART [SMART], but more extensive studies must be conducted to provide multicast services over ATM networks. The remainder of this document is organized as follows. Section 2 discusses the motivation for multipoint-to-multipoint connection as a scalable multicast architecture. Section 3 gives an overview of the MCM protocol and examines several proposed schemes such as MCS [1,9,10], SEAM[6,7] , SMART[11]. Section 4 discusses the MCM protocol, Section 5 gives the MCM protocol specifications. Section 6 concludes this document. 2. The Research Motivations The fundamental goal of our proposal is to have a single shared tree between all senders and receivers of a group. A shared tree Expires May 1999 [Page 2] INTERNET-DRAFT MCM October 1998 architecture offers an improvement in scalability over source based tree architectures by a factor of number of active sources. Other advantages may be gained by using a single shared tree as has been discussed in [5,9]. First, Group membership changes decrease the generated level of signaling load. This is especially beneficial for large groups with several senders, when the group is highly dynamic, or when the links between the switch and the cluster members are error-prone. This allows group of members to be temporarily dropped from the multicast group. Second, more than one group of members may be added in one step, initiated by the core. In contrast, a scheme using per-sender trees can not permit this where either each sender has to setup a tree to all the receivers, which means that the set of receivers has to be communicated with the senders, or the receivers join the sender tree of all the senders, which means that, in turn, the receivers need to know the set of senders. This gives us better performance due to rapid setup of centrally controlled groups. Third, Using a single shared tree results in allocating a single VC per link for the entire group. This results in "traffic concentration", which is an advantage in terms of manageability. The major disadvantage of shared tree is the delays that are potentially higher than in the case of shortest-path sender-based trees. 3. Overview of the MCM scheme The core concept in MCM is introduced as the concept of the 'core' in CBT [2,3], where is defined as the root of the tree to be set up. The core does not have to know the leaf nodes of the tree, but it must keep track of current senders (senders that actually have data to send at current time). The core does not work as a Multicast Server (MCS), where each sender must forward its packets to the server, and the server, in turn, reforwards it to the group members. But, the core acts a manager that controls the multiaccess to the shared tree and the core also schedules among senders when several senders simultaneously request access to the shared tree. No extra buffering is needed in the ATM switch as proposed by SEAM architecture [6,7]. 3.1. MCM Versus MCS Multicast Server (MCS) was proposed by the IETF [1] as a mechanism to support multicasting over UNI 3.0/3.1 ATM based networks. A detailed design and implementation of MCS, and a mechanism for using multiple MCSs per group for providing fault tolerance was discussed in [9,10]. The MCS acts as a proxy server which multicasts data received from a source to the group members in the cluster. All multicast sources must establish a point-to-point VC with the MCS in order to send the data to the MCS. The MCS then forwards the data over a point-to-multipoint VC that it maintains to group members in the cluster. The main advantage of MCM over MCS is that the MCS reassembles AAL_SDUs arriving on all the incoming VCs, and then queues them for transmission on its single outgoing point-to-multipoint VC. However in MCM no reassembly is required to be done at the core, and no buffers is Expires May 1999 [Page 3] INTERNET-DRAFT MCM October 1998 required to queue the data from different senders. 3.2. MCM versus SEAM An architecture for Scalable and Efficient ATM Multipoint-to- Multipoint Communication (SEAM) was introduced in [6,7]. In SEAM, a single VC is used for a multicast group consisting of multiple senders and multiple receivers. A technique called "Cut- Through forwarding" was proposed in which switches perform cut- through forwarding complete packets at a time, while buffering incoming packets from other input ports until EOP cell has been forwarded. Both MCM and SEAM use the concept of the core of the shared multicast tree. However the main advantage of MCM over SEAM is that no extra buffering is required at the ATM switch, also all data forwarding are performed in the ATM layer of the sender in the multicast group. 3.3. MCM versus SMART A Shared Many-to-Many Multicast Protocol for ATM (SMART) [11] can be viewed as a completely distributed protocol for controlling the access over the shared multicast tree, it uses the resource management cells RMs as special control messages (GRANT messages and REQUEST messages) to control the link access. These message are associated with each VC connection. In SMART a sender can possibly gain access to the multicast tree. One solution to this is to select the next sender in a round-robin bases. This requires that the protocol maintains a list at each member of all active ports with a pending request that were not yet granted access to the shared tree. SMART exhibits a high overhead resulting from the large number of control messages exchanged before sending data, However MCM which can be viewed as a centralized protocol for controlling the multiaccess to the shared multicast exchanges a relatively very small number of messages before sending data. The existence of a central controller guarantees that all senders can have the same chance to access the shared tree, special senders in the multicast tree may be prioritized. MCM has a single point of failure inherent in using a single core, this problem may be solved by using multiple cores per shared tree. 4. MCM Proposal This section discusses the proposed scheme while a detailed architecture and protocol specification is introduced in the next section 4.1. MCM Control Messages The MCM defines many control messages as it follows. Expires May 1999 [Page 4] INTERNET-DRAFT MCM October 1998 0 MCM_REQUEST: sent by a member of the multicasting group to the core to request the access to the shared tree. The core then appends this member to the sender's list. 0 MCM_SEND_ALL: sent by the core to specified member granting it an absolute access to the shared tree, so allowing this member to transmit all of its data packets over the shared tree. 0 MCM_SEND: sent by the core to specified member allowing it to transmit only a single packet over the shared tree. 0 MCM_PAUSE: sent by the core to the current sender (a member that currently has the right to access the multicast tree) forcing this sender to stop forwarding its data after completing the current packet. 0 MCM_ACK: sent by the current sender to the core to notify the core that it has completed forwarding a data packet. The core then transmits the access to the shared tree to another sender. also sent by the core to a requested member to notify it that its MCM_REQUEST message have been received and processed at the core. 0 MCM_EOD: sent by the current sender to the core to notify the core that it has no more data to transmit over the shared tree. The core then removes that sender from its sender's list. 4.2. Data Forwarding When a member of the multicasting group (S1) has data packets to transmit over the shared tree, this member first establishes a point-to-point (MCMVC) bidirectional VC (if it does not exist) with the core to be used as a control VC that enables both the member and the core to exchange the MCM control messages. This implies that all the group members must have a previous knowledge of the ATM address of the core of their group. After establishing that VC, the member transmits a MCM_REQUEST message to the core through that VC. The core responds to this request by adding this sender to the sender's list (a simple list that enables the core to keep track of the whole senders that currently requested access to the shared tree), the core also attemps to send MCM_ACK to that member to notify it its request is successfully received and processed at the core. Assume that the sender's list contains only the sender (S1), so the core attempts to transmit a MCM_SEND_ALL message to (S1) through the MCMVC. Upon receiving the MCM_SEND_ALL, (S1) attempts to transmit all its data packets through the shared tree. (S1) keeps the access to the shared tree until there is no packets to transmit, at this time (S1) sends MCM_EOD message to the core to be removed from the senders list. (S1) may also set up an idle timer to release the point-to-point VC established with the core if not used for a configurable period of time. If another member (S2) has data packets to transmit over the shared Expires May 1999 [Page 5] INTERNET-DRAFT MCM October 1998 tree, it also establishes its own point-to-point VC with the core, and then it sends a MCM_REQUEST message to the core. The core then appends (S2) to the sender's list, sends MCM_ACK to the S2, and starts a scheduling procedure between the current senders (S1, S2 in this case). Assuming, (S2) is given the privilege according the applied priority-based scheduling policy, (S2) gets the access to send all its data packets as long as there is no higher priority member requesting sending. If (S1) and (S2) have the same priority, they alternate sending their data packets. If this is the case, the core sends MCM_PAUSE message to (S1). Upon receiving the pause message, (S1) completes sending the current packet, stops forwarding more packets and sends a MCM_ACK message to the core. The core then sends a MCM_SEND message to (S2). (S2) now gains the access to the shared tree and starts forwarding a single data packet then transmits a MCM_ACK message to the core. The core gives the access to (S1) by sending MCM_SEND to (S1), which, in turn, transmits a single packet over the shared tree followed by a MCM_ACK on the control VC to the core, and so on. 4.3. Scheduling among multiple senders In MCM the core keeps track of all senders that have requested the access to the shared tree. The core schedules among multiple senders in a round robin basis allowing each sender to transmit only a single data packet. Priority system may be applied where a priority value may be assigned to each member when it is joined a group. A member requesting access to the shared tree has to pass this value to the core within the MCM_REQUEST message. The core can also allow a sender to transmit more than one packet by including the number of packets that the sender will transmit in the MCM_SEND message. 5. MCM Protocol Specifications 5.1. Establishing The MCMVC As discussed above The ATM address of the core must be known to all members of the multicast group. When a group member has data to transmit over the shared tree, it must gain the access to the shared tree before attempting to transmit its data cells. First it will attempt to establish a point-to-point bidirectional VC called MCMVC with the core. All MCM control messages exchanged between that member and the core are then carried over the MCMVC. If the group member fails to establish the MCMVC with the core, it should wait a random period of time between 1 and 10 seconds before attempting to reconnect with the core. Note: In this document, we assume a single core per shared tree. However, Having multiple cores per tree will eliminate the single point of failure. The possibility of having multiple cores per tree is for further study. 5.2. MCM_REQUEST Processing MCM_REQUEST is the mechanism by which a group member requests the Expires May 1999 [Page 6] INTERNET-DRAFT MCM October 1998 access to the shared tree. 5.2.1. Sending MCM_REQUEST The MCM_REQUEST is sent by a group member to the core over the MCMVC to request the access to the shared tree. This member then starts a timer and waits for a MCM_ACK from the core. 5.2.2. Receiving MCM_REQUEST Upon Receiving MCM_REQUEST at the core, it will attempt to add this member to its sender's list, a simple table which used to keep track of all group members that have been requested the access to the shared tree. Then the core attempts to transmit a MCM_ACK over its MCMVC to notify that member that its request is successfully received and processed at the core. 5.2.3. Retransmission of MCM_REQUEST The group member needs to retransmit MCM_REQUEST at regular intervals when it doesn't receive a response from the core. This interval should be no shorter than 5 seconds, and a default of 10 seconds is recommended. A maximum of 5 retransmissions is permitted before a failure is logged. 5.3. MCM_SEND Processing MCM_SEND is the mechanism by which the core gives the right to access the shared tree to an inactive sender causing this sender to be the current active sender. 5.3.1 Sending MCM_SEND In MCM proposal the core should keep track of all group members requesting the access to the shared multicast tree. The core is responsible for scheduling among those members using a packet basis. After the current sender completes sending its data packet, it sends a MCM_ACK to the core, the core then transmits a MCM_SEND to the next member in the sender's list giving it the access over the shared tree. 5.3.2 Receiving MCM_SEND Upon receiving the MCM_SEND message, this group member becomes the current sender and starts forwarding a data packet over the shared tree, followed by MCM_ACK to the core over the MCMVC. If that member has no more data to transmit over the shared tree, it should transmit a MCM_EOD to the core instead of MCM_ACK. 5.4. MCM_SEND_ALL Processing MCM_SEND_ALL is used by the core to give a group member an absolute access to the shared tree. Expires May 1999 [Page 7] INTERNET-DRAFT MCM October 1998 5.4.1. Sending MCM_SEND_ALL MCM_SEND_ALL is sent to a group member when it is the only entry in the sender's list. 5.4.2. Receiving MCM_SEND_ALL Upon receiving MCM_SEND_ALL at the group member, this member has the full access to the shared tree, and starts forwarding its data packets over the shared tree. 5.5. MCM_PAUSE Processing The core sends MCM_PAUSE to the current active sender that has an absolute access to the shared tree forcing it to stop data forwarding. 5.5.1. Sending MCM_PAUSE The core uses the MCM_PAUSE message to schedule among different group senders. Consider the case that there is only an active sender in the group, this sender is giving an absolute access to the shared tree. Upon receiving a new request at the core, the core will attempt to send MCM_PAUSE message to the current sender, waits for a MCM_ACK From that sender and then pass the access to the new sender by sending it a MCM_SEND. 5.5.2. Receiving MCM_PAUSE MCM_PAUSE will be received at the current sender who has an absolute access to the shared tree forcing it to stop data forwarding after completing the current packet. The sender then transmits MCM_ACK to the core over the MCMVC. If this packet is the last packet the sender will transmit MCM_EOD instead of MCM_ACK. 5.6. MCM_ACK Processing This message may be sent or received by either a group member or the core. The meaning of MCM_ACK is different in each case. 5.6.1. Sending MCM_ACK MCM_ACK is sent by the current sender to the core to notify the core that it has stopped forwarding more data over the shared tree. MCM_ACK also is sent by the core to a group member to notify that member that its request to access the shared tree had been successfully received and processed by the core. 5.6.2. Receiving MCM_ACK If MCM_ACK is received at the core, this means that the current sender has stopped forwarding more data and the core will attempt to transmit MCM_SEND message to the next sender in the sender's list. Expires May 1999 [Page 8] INTERNET-DRAFT MCM October 1998 If MCM_ACK is received at a group member, this means that its request had been successfully received and processed by the core. This member then will attempt to end its timer, wait for the MCM_SEND or MCM_SEND_ALL to start sending its data over the shared tree. 5.7. MCM_EOD Processing Is a control message used by the current sender to notify the core that this sender has no more data to transmit over the shared tree. 5.7.1. Sending MCM_EOD The current sender will attempt to send MCM_EOD to the core when the sender has no more data to transmit over the shared tree. The sender will also starts an idle timer associated with the MCMVC to be removed if not used for a period of time , in the MARS model [1], 20 minutes were recommended. 5.7.2. Receiving MCM_EOD Upon receiving MCM_EOD at the core, the current sender will be removed from the sender's list, and the core will transmit the access to the shared tree to the next sender in the sender's list. 6. Conclusion and Future Work A new scheme was proposed, Multicast Manager (MCM), which manages the multi-access to the shared multicast tree. MCM guarantees that only one sender is allowed to transmit its data packets over the shared tree at a time, and thus it performs a very simple traffic management function. MCM also prohibits cell interleaving at any receiver. MCM schedules among several group senders in a data packet basis. 7. References [1] G. Armitage. Support for multicast over UNI 3.0/3.1 based ATM networks. Request for Comments 2022, November 1996. [2] A. Ballardie. Core Based Trees (CBT) Multicast Routing Architecture. Request for Comments 2201, September 1997. [3] A. Ballardie. Core Based Trees (CBT version 2) Multicast Routing; Protocol Specification. Request for Comments 2189, September 1997. [4] ATM User Network Interface (UNI) Signalling Specification Version 4.0. ATM Forum Specifications /af-sig-0061.000, ATM Forum, July 1996. [5] ATM Forum. ATM User-Network Interface Specification Version 3.0. Englewood Cliffs, NJ: Prentice Hall, September 1993. Expires May 1999 [Page 9] INTERNET-DRAFT MCM October 1998 [6] M. Grossglauser and K. K. Ramakrishnan, SEAM: Scalable and Efficient ATM Multipoint-to-Multipoint Communication [Extended Abstract], Proc. 6h Intl. Workshop on Network and Operating System Support (NOSSDAV '96), Zushi, Japan, April 1996. [7] M. Grossglauser and K. K. Ramakrishnan, SEAM: Architecture for Scalable and Efficient ATM Multipoint-to-Multipoint Communication, 15th International Teletraffic Congress (ITC), Washington DC, USA, June 1997. [8] Sonia Fahmy, Raj Jain, Shivkumar Kalyanaraman, Rohit Goyal, Bobby Vandalore and Xiangrong Cai, ``A Survey of Protocols and Open Issues in ATM Multipoint Communications", OSU Technical Report, August 21, 1997, http://www.cis.ohio-state.edu / ~jain /papers /mcast.htm". [9] Talpade, R., Ammar, M. H., Multicast Server Architectures for Supporting IP Multicast over ATM, in Proceedings of the 7th IFIP Conference on High Performance Networking, April 1997. [10] Talpade, R., Ammar, M. H., Multicast Server Architectures for MARS-based ATM multicasting. Request for Comments 2149, May 1997. [11] Eric Gauther, Jean-Yves Le Boudec, and Philippe Oechslin. Shared many-to-many ATM reservations. In Proceedings of IEEE ATM'96 Workshop, San Fransisco, August 1996. Authors' Information: Yasser Seif Systems & Computer Dept. Al-AZHAR University CAIRO E-MAIL: yasser_seif@usa.net Prof. Hani Harb Systems & Computer Dept. Al-AZHAR University CAIRO E-MAIL: harb@frcu.eun.eg Expires May 1999 [Page 10]