INTERNET DRAFT Jae-Hoon Jeong Expires: December 2002 Jung-Soo Park ETRI June, 2002 Unicast Routing based Multicast Routing Protocol for Mobile Ad Hoc Networks (UMR) Status of this Memo This document is an Internet-Draft and is in full conformance with all provisions of Section 10 of RFC 2026 except that the right to produce derivative works is not granted. 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 document describes a protocol for multicast in mobile ad-hoc networks - named Unicast Routing based Multicast Routing Protocol for Mobile Ad Hoc Networks (UMR). The protocol uses a new scheme for mobile ad-hoc network that has dynamic topology without managing multicast tree and depending on simple flooding. It is the multicast routing protocol that works in use of unicast routing protocol. Any ad-hoc unicast routing protocol can be used. Table of Contents Jeong, Park Expires December 2002 [Page 1] INTERNET-DRAFT Unicast Routing based Multicast Routing June 2002 Status of this Memo Abstract 1. Introduction 2. Assumptions 3. Terminology 4. UMR Overview 5. Encoding of UMR header 5.1 UMR header 5.2 UMR Messages 6. Protocol Operations 6.1 Registration of Multicast Group Member 6.2 Registration of Multicast Group Source 6.3 Leave of Multicast Group Member 6.4 Leave of Multicast Group Source 7. Implementation Considerations 8. IANA Considerations 9. Security Considerations 10. References Authors' Addresses 1. Introduction UMR, the protocol specified in this document is designed to provide multicast functionality without managing multicast tree and with the minimum control information and the routing information provided by ad-hoc unicast routing in mobile ad-hoc networks. It utilizes the unicast routing to update the information for multicast routing. Any ad-hoc unicast routing that is based on table-driven or on-demand method can be used. It can provide the efficient multicasting in mobile ad-hoc network that changes its network topology very frequently because of not using multicast tree and using only unicast routing. It eliminates the per session signaling and per session state information of tree-based multicast schemes [MAODV]. It also maximizes the utilization of bandwidth because it doesn't depend on simple flooding [SIMPLE]. This allows UMR to support very large numbers of multicast sessions in ad-hoc network. It adopts the concept of Xcast and Xcast+ to deliver the multicast data packet to multicast group members [XCAST, XCAST+]. 2. Assumptions We assume that all mobile nodes wishing to communicate with other nodes within the mobile ad-hoc network are willing to participate fully in the protocols of the network. In particular, each node participating in the network should also be willing to forward packets for other nodes in the network. We also assume that all mobile nodes run the same ad-hoc unicast Jeong, Park Expires December 2002 [Page 2] INTERNET-DRAFT Unicast Routing based Multicast Routing June 2002 routing as is either table-driven or on-demand. Packets may be lost or corrupted in transmission on the wireless network. A node receiving a corrupted packet can detect the error and discard the packet. 3. 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 [RFC2119]. New terms are defined below: Mobile Node (MN) The mobile node that is host and plays a role of router. Multicast Member The table for multicasting that is used by Table (MMT) multicast source node per multicast group. The fields consists of group-member, next-hop, hop-count and status. Multicast Source The table for multicasting that is used by Table (MST) multicast group member node per multicast group. The fields consists of group-source, next-hop, hop-count and status. 4. UMR Overview In the traditional multicast model, Host Group Model, the multicast packet is identified by a multicast address of all group members. But, in UMR, the multicast source node keeps track of the destinations in the multicast group that it wants to send packets to. The source node encodes the list of multicast group members in the UMR header, and then sends an adjacent MN the multicast data packet. Each intermediate MN that plays a role of router along the way towards to all the destinations in the list of UMR header parses the header, partitions the destinations based on each destination's next hop, and forwards a packet with an appropriate new UMR header to each of the next hops. For example, let's assume that multicast source SRC_1 is trying to send a multicast packet to all the members of multicast group G that have already been registered in SRC_1 - from RCV_1 to RCV_6 - in Figure 1 below: Jeong, Park Expires December 2002 [Page 3] INTERNET-DRAFT Unicast Routing based Multicast Routing June 2002 RT_3 ---- RCV_1 RCV_2 / / / / SRC_1----- RT_1 ---- RT_2 ---- RT_4 ---- RT_5 --- RCV_3 \ \ \ \ RT_6 ---- RCV_5 RCV_4 \ \ RCV_6 where SRC : Source, RT : Router & RCV : Receiver Figure 1. Example of multicast packet delivery in UMR The delivery of a multicast packet is accomplished as follows: SRC_1 sends a UMR multicast packet with the list of destinations in its UMR header to the first router, RT_1. As we ignore the details, the multicast packet that SRC_1 sends to RT_1 looks like this: [src = SRC_1 | dest = RCV_1 RCV_2 RCV_3 RCV_4 RCV_5 RCV_6 | group=G | payload] When RT_1 receives this packet, it needs to properly process the UMR header. The processing that each transit MN does on receiving the UMR multicast packet is performed as the following steps: Step 1. Lookup of unicast routing table for determining the next hop for each of the destinations listed in the multicast packet. Step 2. Partition of the set of destinations based on their next hops. Step 3. Copy of the multicast packet for each different next hop. Step 4. Modification of the list of destinations in each of the copies so that the list in each copy includes just the destinations that ought to be routed through each corresponding next hop. Step 5. Transmission of the modified copies of the multicast packet on to the next hops. By the above procedure, when RT_2 receives the multicast packet, it will send one copy of the packet to next hop RT_3 with a UMR list of {RCV_1}, send one copy of the packet to next hop RT_4 with a UMR list of {RCV_2 RCV_3 RCV_4}, and send one copy of the packet to next hop RT_6 with a UMR list of {RCV_5 RCV_6}. Jeong, Park Expires December 2002 [Page 4] INTERNET-DRAFT Unicast Routing based Multicast Routing June 2002 When RT_3 receives a UMR multicast packet destined to RCV_1, RT_3 converts the UMR multicast packet into a standard multicast packet and multicasts the packet to multicast group G [XCAST+]. Because RCV_1 has joined multicast group G, it can receive the packet. With the similar way, the rest of multicast group members - RCV_2, RCV_3, RCV_4, RCV_5 & RCV_6 - can receive the multicast packet from SRC_1. Note that when network topology changes, the routing for UMR multicasting will automatically adapt to the new topology since the path that a UMR multicast packet takes to each multicast group member always follows the ad-hoc unicast routing for each destination. 5. Encoding of UMR header The source address field of the IP header contains the address of the UMR sender. The destination address field contains the All- UMR-Routers address that is to have a fixed value. Every UMR MN joins this multicast group to receive any UMR multicast packet. The protocol field contains the UMR protocol number, PROTO_UMR, that is to have a fixed value. The list of destinations that are multicast group members will be encoded in a separate header. The UMR header is contained between the IP header and the transport layer header as follows: [IP header | UMR header | transport header | payload ] Note that since the UMR header is included to the data portion of the IP datagram, if the multicast source node wishes to avoid IP fragmentation, it must take the size of the UMR header into account. We consider IPv4 currently. 5.1 UMR header The UMR header is depicted in Figure 2. It consists of two parts: a fixed part (first 16 octets) and a variable length part that is specified by the fixed part. Jeong, Park Expires December 2002 [Page 5] INTERNET-DRAFT Unicast Routing based Multicast Routing June 2002 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| Type | Code | Num_of_Address| Reserve | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Group_Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Sequence_Number | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Next_Protocol | Length | Checksum | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | List_of_Addresses | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Figure 2. UMR header Version 4-bit UMR version number. This document describes version 1. Type 8-bit UMR message type. This field identifies UMR packet. Code 4-bit unsigned integer. This supplements Type field to represent the status information or the return value. Num_of_Address 8-bit unsigned integer. This field indicates the number of addresses that are contained in the following field, List of Addresses. Reserve 8-bit reserved field. Group_Address 32-bit multicast group address. Sequence_Number 32-bit unsigned integer. This field is used to identify duplicate packet. Each MN maintains its own squence number for this field. Next_Protocol 8-bit unsigned integer. This field indicates the protocol of the following header Length 8-bit unsigned integer. This field indicates the length of the UMR header in 4-octet words. Checksum 16-bit checksum. This field is the checksum on the UMR header only. This is verified and recomputed at each point that the UMR header is processed. The checksum field is the 16-bit one's complement of the one's complement sum of all the bytes in the header. List_of_Addresses The list of addresses. Each address size is four Jeong, Park Expires December 2002 [Page 6] INTERNET-DRAFT Unicast Routing based Multicast Routing June 2002 octets. 5.2 UMR Messages The kinds of UMR packet are two; (a) Data packet and (b) Control packet. UMR Data packet is the packet that contains the multicast data sent by source node. UMR Control packet is the packet that contains the multicast- related control information such as join and leave. The Type field of UMR header identifies the kind of UMR packet. The values of Type field are as follows; 1 UMR_DATA UMR Data packet. 2 UMR_CONTROL_MEMBER_REGISTRATION UMR Control packet for registering a multicast group member in any multicast group source. 3 UMR_CONTROL_MEMBER_LEAVE UMR Control packet for informing all the multicast group sources of leaving the multicast group. 4 UMR_CONTROL_SOURCE_REGISTRATION UMR Control packet for registering a multicast group source in any multicast group member. 5 UMR_CONTROL_SOUCE_LEAVE UMR Control packet for informing all the multicast group members of the stop of sending multicast data. The Code field of UMR header provides more detailed control information. The values of Code field are as follows; 1 CODE_REQUEST UMR Control packet that requests the operation indicated by Type field. 2 CODE_ACK UMR Control packet that acknowledges the result of the requested operation. 3 ERROR UMR Control packet that informs the other party of Jeong, Park Expires December 2002 [Page 7] INTERNET-DRAFT Unicast Routing based Multicast Routing June 2002 the occurrence of an error. At this time, the field Num_of_Address contains the value of detailed error. 6. Protocol Operations UMR can work after ad-hoc unicast routing is set up. 6.1 Registration of Multicast Group Member When a wanted multicast group member joins multicast group, it broadcasts a UMR control packet indicating the registration of multicast group member. The destination field of IP header contains 255.255.255.255 for broadcasting. The Type field of UMR header contains UMR_CONTROL_MEMBER_REGISTRATION. The Code field of UMR header contains CODE_REQUEST. The control packet is distributed towards any multicast group source. Note that any intermediate MN doesn't broadcast the packet that has broadcast just before. Each MN identifies the duplicate packet with the Sequence_Number field of UMR header. When a multicast group source receives the packet, the following procedure is performed. Step 1. Registration of multicast group member in MMT. The source registers the IP address of the multicast group member in the group-member field of MMT and fills the other fields of MMT such as next-hop, hop-count and status with the unicast routing table. next-hop is the next hop towards the group member. hop-count is the distance from source to group member by the number of hops. status indicates the connectivity status for group member in unicast routing. The connected status is represented as 1 and disconnected status is represented as 0. Of course, by the change of unicast routing, the other fields of MMT except group-member are changed appropriately. Step 2. Acknowledgement of the registration packet. Source makes a UMR Control packet for acknowledging the completion of the registration and sends it to the group member in unicast. The Type field of UMR header contains the same as that of the registration packet. The Code field contains CODE_ACK. The List_of_Addresses field contains the IP address of the source. When the group member receives the acknowledgement packet for registration, it registers the IP address of the source in the Jeong, Park Expires December 2002 [Page 8] INTERNET-DRAFT Unicast Routing based Multicast Routing June 2002 group-source field of MST. The other fields of MST are filled appropriately with the unicast routing table. 6.2 Registration of Multicast Group Source Before a new multicast group sender sends multicast data packets, it broadcasts a control packet indicating the registration of multicast group source. The destination field of IP header contains 255.255.255.255 for broadcasting. The Type field of UMR header contains UMR_CONTROL_SOURCE_REGISTRATION. The Code field of UMR header contains CODE_REQUEST. The control packet is distributed towards any multicast group member. When a multicast group member receives the packet, the following procedure is performed. Step 1. Registration of multicast group source in MST. The member registers the IP address of the multicast group source in the group-source field of MST and fills the other fields of MST such as next-hop, hop-count and status with the unicast routing table. next-hop is the next hop towards the group member. hop-count is the distance from group member to source by the number of hops. status indicates the connectivity status for source in unicast routing. The connected status is represented as 1 and disconnected status is represented as 0. Of course, by the change of unicast routing, the other fields of MST except group-source are changed appropriately. Step 2. Acknowledgement of the registration packet. Member makes a UMR Control packet for acknowledging the completion of the registration and sends it to the group source in unicast. The Type field of UMR header contains the same as that of the registration packet. The Code field contains CODE_ACK. The List_of_Addresses field contains the IP address of the member. When the group source receives the acknowledgement packet for registration, it registers the IP address of the member in the group-member field of MMT. The other fields of MMT are filled appropriately with the unicast routing table. 6.3 Leave of Multicast Group Member When a multicast group member leaves multicast group, it multicasts a control packet indicating the leave of multicast group member. The destination field of IP header contains All-UMR-Routers address Jeong, Park Expires December 2002 [Page 9] INTERNET-DRAFT Unicast Routing based Multicast Routing June 2002 with the list of addresses of multicast group sources in the UMR header that are stored in MST. The Type field of UMR header contains UMR_CONTROL_MEMBER_LEAVE. The Code field of UMR header contains CODE_REQUEST. When the packet arrives in the just previous MN of a multicast group member, unlike a UMR multicast data packet of which the Type field of UMR header contains UMR_DATA, the packet isn't converted to a standard multicast packet and is converted to UMR unicast packet(s) of which the destination field of IP header is the address selected from the list of addresses contained in the List_of_Addresses field of UMR header. When a multicast group source receives the packet, the following procedure is performed. Step 1. Deletion of multicast group member in MMT. The source deletes the entry in MMT that corresponds to the IP address of the group member. Step 2. Acknowledgement of the leave packet. Source makes a UMR Control packet for acknowledging the completion of the leave and sends it to the group member in unicast. The Type field of UMR header contains the same as that of the leave packet. The Code field contains CODE_ACK. The List_of_Addresses field contains the IP address of the source. When the group member receives the acknowledgement packet for leave, it deletes the entry in MST that corresponds to the IP address of the source. 6.4 Leave of Multicast Group Source When a multicast group source stops sending multicast data, it multicasts a control packet indicating the leave of multicast group source. The destination field of IP header contains All-UMR-Routers address with the list of addresses of multicast group members in the UMR header that are stored in MMT. The Type field of UMR header contains UMR_CONTROL_SOURCE_LEAVE.The Code field of UMR header contains CODE_REQUEST. When the packet arrives in the just previous MN of a multicast group member, the packet is processed in the same way as Leave of Multicast Group Member. When a multicast group member receives the packet, the following procedure is performed. Jeong, Park Expires December 2002 [Page 10] INTERNET-DRAFT Unicast Routing based Multicast Routing June 2002 Step 1. Deletion of multicast group source in MST. The member deletes the entry in MST that corresponds to the IP address of the group source. Step 2. Acknowledgement of the leave packet. Member makes a UMR Control packet for acknowledging the completion of the leave and sends it to the group source in unicast. The Type field of UMR header contains the same as that of the leave packet. The Code field contains CODE_ACK. The List_of_Addresses field contains the IP address of the member. When the group source receives the acknowledgement packet for leave, it deletes the entry in MMT that corresponds to the IP address of the member. When the source becomes to receive the acknowledgement from all the group members in MMT, it removes MMT. 7. Implementation Considerations We should consider the checksum calculation in UDP and ICMP. We should also consider the process of IGMP messages in order to use the current multicast applications without modification. 8. IANA Considerations All-UMR-Routers address and UMR protocol number should be defined by IANA. 9. Security Considerations Security issues related to the representative ad-hoc unicast routing protocols such as AODV and DSR apply to the protocol described here [AODV, DSR]. 10. References [RFC2119] S. Bradner, "Key words for use in RFCs to Indicate Requirement Levels", RFC 2119, March 1997. [MAODV] Elizabeth M. Royer and Charles E. Perkins, "Multicast Ad hoc On-Demand Distance Vector (MAODV) Routing", I-D draft-ietf-manet-maodv-00, July 2000. [SIMPLE] Jorjeta G. Jetcheva et al., "A Simple Protocol for Multicast and Broadcast in Mobile Ad Hoc Networks", I-D draft-ietf-manet-simple-mcast-01, July 2001. [XCAST] R. Boivie et al., "Explicit Multicast (Xcast) Basic Specification", I-D draft-ooms-xcast-basic-spec-02, October 2001. [XCAST+] Myung-Ki Shin, Yong-Jin Kim and Sang-Ha Kim, "Explicit Jeong, Park Expires December 2002 [Page 11] INTERNET-DRAFT Unicast Routing based Multicast Routing June 2002 Multicast Extension (Xcast+) Supporting Receiver Initiated Join", I-D draft-shin-xcast-receiver-join-01, March 2002. [AODV] Charles E. Perkins, Elizabeth M. Royer and Samir R. Das, "Ad hoc On-Demand Distance Vector (AODV) Routing", I-D draft-ietf-manet-aodv-10, January 2002. [DSR] David B. Johnson et al., "The Dynamic Source Routing Protocol for Mobile Ad Hoc Networks (DSR)", I-D draft-ietf-manet-dsr-07.txt, February 2002. Authors' Addresses Jae-Hoon Jeong ETRI / PEC 161 Gajong-Dong, Yusong-Gu Daejon 305-350 Korea Phone: +82 42 860 1664 EMail: paul@etri.re.kr Jung-Soo Park ETRI / PEC 161 Gajong-Dong, Yusong-Gu Daejon 305-350 Korea Phone: +82 42 860 6514 EMail: pjs@etri.re.kr Expiration date: December 2002 Jeong, Park Expires December 2002 [Page 12]