Internet Draft Matthew Cheng Document: John Lee Category: Informational Mario Joa-Ng Telcordia Technologies, Inc. December 2000 Hierarchical Level-based IP Multicast (HLIM) Status of this Memo This document is only intended to provide information for the Internet community. It does not aim to specify an Internet standard. This document is an Internet-Draft and is submitted to IETF pursuant to a copyright agreement executed by the parties and is not submitted in conformance with Section 10.3.1(1) and 10.3.1(7) of RFC 2026. In other respects this document is submitted in conformance with Section 10 of RFC 2026. 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. (c)2000 Telcordia Technologies, Inc. Abstract This document proposes and describes a new IP multicast routing protocol, called "Hierarchical Level-based IP Multicast" (HLIM). It is designed for a hierarchical IP network and leverages the hierarchical structure to provide efficient IP multicasting. It is originally designed for tactical networks in battlefields but some of its functions could be applied to commercial networks as well. Besides the basic support for multicast in static environments, HLIM supports host mobility (movements of IP multicast hosts) and network mobility (movements of IP multicast routers with/without hosts). Since HLIM is designed for harsh environments, reliability and survivability functions are also built into HLIM. Unlike other existing IP multicasting schemes, HLIM can provide a shared and Telcordia Technologies Expires June 2001 [Page 1] Internet Draft HLIM December 2000 shortest-path multicast tree without using a concentration point like a core or rendezvous point. The shortest paths between multicast sources and receivers can still be maintained after a host or network movement. HLIM also allows better control of multicast session establishments by requiring both sources and receivers to "join" a multicast group before they can send or receive any multicast packets. 1. Introduction Existing multicasting schemes are basically differentiated by how a tree (called "spanning tree" or "multicast tree") is set up to forward multicast packets from a sender to the receivers within a multicast group. Such schemes can be classified into two main categories: source-based tree (e.g., distance vector multicast routing protocol (DVMRP), multicast open shortest path first (MOSPF), and protocol independent multicast-dense mode (PIM-DM) [1]-[3]) and shared tree (e.g., core based tree (CBT) and protocol independent multicast-sparse mode (PIM-DM) [4]-[6]). In the source-based tree approach, a multicast tree is created from each sender to all the receivers of a multicast group. This approach maintains the shortest paths but is less scalable, especially when there are many sources sending to the same multicast group. The shared tree approach mitigates the scalability problem by establishing a single multicast tree shared by all sources and receivers of a group. A tree rooted at a known concentration point (such as a core in CBT or a rendezvous point in PIM-SM) is created to all the receivers of a group. The sources send their packets to the root, which then disseminates the packets to the receivers. The drawback, however, becomes apparent when optimal routing is emphasized because the shared tree scheme provides the shortest path only between the root and receivers, not between a source and receivers. In addition, this approach requires complex mechanisms to advertise the addresses of the roots to every multicast host. In addition to these shortcomings, existing IP multicasting schemes have no explicit provision for host and network mobility since the schemes have been mainly derived for fixed IP networks. Recently, some ideas for supporting host mobility have been proposed. The basic idea is to extend the current IP multicasting schemes to adapt to mobile environments with the help of mobile IP [7],[8]. However, this extended approach cannot completely resolve the mobility problems incurred by the movements of multicasting hosts. For example, in the source-based approach, the shortest path between a sender and receivers would not be maintained as the sender moves. To date, the network mobility issue has been addressed only rarely. Therefore, a new IP multicasting scheme that can support both host and network Telcordia Technologies Expires June 2001 [Page 2] Internet Draft HLIM December 2000 mobility efficiently and reliably is highly desirable. Our multicasting protocol design, HLIM, can overcome the shortcomings of the conventional IP multicasting schemes and also support both host and network mobility. HLIM assumes that the IP multicast routers are arranged hierarchically as in tactical networks in battlefields. Each IP multicast router is assigned a level number corresponding to its level in the hierarchy. In addition to the conventional group identifier, a HLIM multicast address carries a scope information, which defines the highest and lowest levels in the hierarchy that a multicast packet can be forwarded to. HLIM establishes a multicast tree along the shortest paths from the sources to the receivers. It is also shared by all the sources and receivers of the same group. HLIM requires both sources and receivers to "join" a multicast group before they can send or receive multicast packets. This allows better control of multicast session establishments. As a source or receiver moves, any ongoing multicast session involved is maintained by extending the tree to the new locations of the host. When a network of routers and hosts move, all the ongoing multicast sessions in the network are maintained. Moreover, only the parent router of the mobile network is aware of the movement and invokes appropriate operations. The movement is transparent to all other routers and hosts inside the mobile network. It should be noted that the resulting tree after a host or network movement is still shortest- path and shared. The mobility functions only apply to "ongoing" sessions. A mobile host or network with no session established does not need to do anything. When the mobile host or a host in the mobile network wants to participate a group at the new location, the baseline functions are invoked to join the group within the scope of the new location. There is no concept of "home" and "foreign" networks used in Mobile IP since we assume the users are always interested in "local" information. Although HLIM is designed for hierarchical tactical networks, it could be applied to any other commercial networks arranged in a hierarchical manner. It could also be extended to an arbitrary network with the help of a clustering protocol to form a logical hierarchy. For example, the MMWN (multimedia support for mobile wireless networks) protocol discussed in [9] can be used to establish a logical hierarchical network in an ad-hoc network before applying HLIM to the ad-hoc network. 2. Tactical Network ARCHITECTURE A tactical IP network is a multi-level hierarchical mobile network where IP routers are hierarchically connected as shown in Fig. 1 Telcordia Technologies Expires June 2001 [Page 3] Internet Draft HLIM December 2000 [10]. Both IP hosts and routers are mobile in the network. The highest level is the brigade level (level 4) and the lowest level is the platoon level (level 1). An IP router at one level (e.g., brigade) interconnects directly with multiple (e.g., 3 to 5) IP routers at the next lower level (e.g., battalion). We refer to such a direct interconnection between one higher-level and multiple lower- level IP routers as a "core" tactical IP subnet. The tactical IP network can be pictured as an integration of the "core" subnets in a hierarchical manner. Fig. 1. Tactical IP Network. Fig. 2 illustrates a core tactical IP subnet with local subnet attached at each router. The router at the higher level is labeled H1, while the four routers at the lower level are labeled L1 - L4. Each router (except those located at the lowest or highest level) has up to three interfaces: local interface (L_IF), down interface (D_IF), and up interface (U_IF). A router uses its L_IF to handle traffic from and to its local subnet, D_IF for its descendant routers, and U_IF for its ascendant router and its adjacent routers at the same level. In each subnet (core or local), some wireless multiple access technology with broadcast/multicast capabilities (e.g., wireless LAN) is used to interconnect the IP hosts and/or routers. If the wireless multiple access technology has no broadcast/multicast capabilities (e.g., TDMA or CDMA), emulation for such capabilities may be required (e.g., multiple unicast transmissions). Fig. 2. Three possible interfaces in tactical IP subnets. Though only one router is shown in a local subnet (or at the higher level in a core subnet) in the previous figures, it is possible to have more than one IP router to handle IP traffic between the local subnet and the ascendant/descendant routers as shown in Fig. 3. In unicast, this would not produce any duplicate messages because one preferred IP router among them is selected by the unicast routing protocol. However in multicasting, if a designated IP router is not assigned in advance, unnecessary duplicate multicast traffic may result. To avoid this situation, the HLIM protocol elects only one of the routers to handle the multicast traffic. The elected router is denoted as a hierarchical designated router (HDR). The HDR which handles multicast traffic for its local subnet is referred as a local HDR. The HDR which handles multicast traffic flowing between core subnets of adjacent levels is referred as a global HDR. The other non- HDR routers within a subnet ignore any multicast control or data packets received. Note that the other non-HDR routers may serve as Telcordia Technologies Expires June 2001 [Page 4] Internet Draft HLIM December 2000 backups for the elected HDRs, in case that a HDR moves away, has a malfunction, or is destroyed. Fig. 3. Concept of hierarchical designated routers (HDR). 3. The BASIC Concept of HLIM The HLIM protocol provides optimal and efficient IP multicasting in a hierarchical IP network by taking advantage of the hierarchical structure. HLIM demonstrates the benefits of both a source-based algorithm (providing the shortest multicasting paths) and a shared tree algorithm (providing one shared tree per group for efficient utilization of network resources). The basic ideas of HLIM are: to assign a hierarchical level for each IP router, to create scope regions bounded by two hierarchical levels (one for the highest level and the other for the lowest level that a multicast packet for a group can reach), and to include this scope information in a multicast group address. Each multicast packet carries its own scope information that indicates how far it should traverse, and each IP router determines whether or not it should discard a multicast packet received by comparing its own level with the scope levels specified in the packet. In addition to packet forwarding, HLIM includes mechanisms to establish a multicast tree for a multicast session and maintain such a tree dynamically against host mobility, network mobility and network failure. Reliability of the control messages is also taken into account throughout the HLIM design. 3.1 Hierarchical Levels of Routers Each router has its own hierarchical level. If there are a total of N hierarchical levels in the whole network, routers at the highest level are assigned to level N and routers at the lowest level are labeled as level 1. 3.2 Scope regions A HLIM scope region is uniquely identified by a scope boundary, SB(L,H), and the root identity of the region, "root ID" (RID). The SB(L,H) is comprised of two hierarchical levels, where L sets the lower boundary and H sets the upper boundary that a multicast packet generated within the region can reach. The RID for a given SB(L,H) is the identity of the HDR at level H+1 in that region (denoted as HDR(H+1)). It can be some identifier assigned to the root HDR of the region (which should be unique among all HDRs at the same level of the hierarchical IP network), or the IP address of the HDR. Telcordia Technologies Expires June 2001 [Page 5] Internet Draft HLIM December 2000 Fig. 4 shows some possible HLIM scope regions. Note that there is no RID for SB(L=1, 2, 3 or 4, H=4). In this case, null is used as the RID in the group address. Multicast packets associated with, say SB(2,3), are not allowed to move beyond the HDRs at level 3 (e.g., battalion level) and below the HDRs at level 2 (e.g., company level) in normal cases. The packets will be forwarded beyond the region only when a mobile user who has already established a multicast session at its original location moves outside the scope region and is willing to continue that multicast session. As shown in the figure, a scope region is defined in a way that the multicast packets from any host within a scope region are delivered to any other host within the same scope region without traversing other scope regions. Each HDR should keep a list of the IDs of its ascendant HDRs (e.g., a HDR(2) keeps the IDs of HDR(3) and HDR(4)). Such list is used by the HDR to determine the appropriate HLIM operation when a mobile host/network moves to this HDR and wants to maintain its on-going multicast sessions. Fig. 4 HLIM scope regions 3.3 HLIM Multicast Address A complete HLIM group address is comprised of the scope boundary (SB(L,H)), the root ID (RID) of the scope region, and the application ID (APL_ID) identifying a specific multicast application/service. It is denoted as G(L,H,RID,APL_ID) in this document. Any multicast packet will carry this complete HLIM group address and the routers will forward the packets only within the specified scope region. In IPv4, the destination address field in the IP header is not long enough to carry all the HLIM address information. The SB(L,H) and APL_ID can be placed as the 28-bit group ID in an IP class D address. For example, to support a hierarchical network of 4 levels, only 4 bits are required for the scope boundary and there are still 24 bits remaining for the APL_ID. The HLIM scope will work independently of the TTL (Time To Live) field in the IP header. The RID can be the IP address of the root HDR (i.e., the HDR right above the highest level of the scope region) or some other ID assigned. If some other IDs are used, they need to be unique among the routers at the same level and require more administration and management efforts. Currently, we consider to use the IP address as the RID and define a new IP option to carry the RID in the IP header. In IPv6, we can put the complete HLIM group address into the IPv6 destination address field using the unicast address prefix as the RID. Note that the RID is needed because HLIM allows the same APL_ID and SB(L,H) to be reused at different places in the hierarchical IP network (so that the same type of applications/services with the same Telcordia Technologies Expires June 2001 [Page 6] Internet Draft HLIM December 2000 scope can be identified by the same number no matter where the applications/services are delivered) and supports mobile hosts. As long as a host remains in the scope region where a multicast session is started, the packets to/from the host will not interfere with the packets bearing the same SB(L,H) and APL_ID information at another place. However, when the host moves outside that scope region, the packets to/from the host will interfere with the packets carrying the same SB(L,H) and APL_ID information at the new place if the RID is not included. 4. HLIM BASELINE Functions New IGMP messages, such as IGMP_RID_Request, IGMP_RID_Reply, IGMP_M_Report, IGMP_M_Reply, IGMP_Hello and IGMP_Flush, are added into the current IGMP protocol [11] to support the new features in HLIM. Other existing IGMP messages are modified to carry the new multicast group address defined in HLIM and handle both multicast sources and receivers. The baseline functions in HLIM for "fixed" hosts and routers are described in this section. These are the operations for a mobile host to start a new multicast session. The HLIM and IGMP operations to handle host and router mobility (i.e., handover of on-going multicast sessions) and network survivability are described later. To facilitate the explanation of the HLIM operations, we assume a HDR is elected to be both a local and global HDR. 4.1 Local Host Joining a Group When a multicast application is started at a receiver host at level k, the host will obtain the scope boundary (denoted as SB(L,H)) and application identity (denoted as APL_ID) information of the multicast session being joined from the application. The application may obtain such information through some advertising mechanisms such as SAP (session announcement protocol), SDP (session description protocol), or web. Once the host obtains the SB(L,H) and APL_ID for the multicast session, it will join the multicast session by sending an IGMP_RID_Request to its parent HDR. After the HDR completes the HLIM regular receiver join process, it sends an IGMP_RID_Reply with the RID of the scope region back to the host. When a multicast application is started at a source host, the same procedure is followed except that the host indicates it is a source instead of a receiver and the HDR invokes the HLIM source join operation instead of the receiver join operation. Similar to the existing IGMP, a HDR periodically issues an IGMP_Query message to its local subnet, and the local hosts (sources and receivers) respond to the query by sending IGMP_Report. Note that the operations for establishing a multicast tree is now initiated by IGMP_RID_Request/IGMP_RID_Reply, instead of IGMP_Report. IGMP_Report is now used to maintain but not Telcordia Technologies Expires June 2001 [Page 7] Internet Draft HLIM December 2000 create a multicast session, and is applied to both sources and receivers. The detailed procedure is described below: 1. When a host at level k wants to start a multicast session, it first asks its parent HDR (HDR(k)) for the RID for the session by sending a IGMP_RID_Request[SB(L,H), APL_ID, R] if it is a receiver, or IGMP_RID_Request[SB(L,H), APL_ID, S] if it is a source, to its local subnet. 2. Upon receiving a IGMP_RID_Request(R/S), the HDR(k) determines whether the requesting host is located at the right scope region or not. 3. If L<=k<=H (i.e., the host is within the scope requested), the HDR(k) - finds the RID from its HDR list, - invokes the regular receiver or source join operation (HLIM_Join(R/S)), and then - replies to the host with an IGMP_RID_Reply[GA, R/S], where GA is the HLIM group address and comprised of SB(L,H), APL_ID, and RID. Note that the regular join operation is initiated by IGMP_RID_Request(R/S), not by IGMP_Report as in the existing IGMP paradigm. In HLIM, IGMP_Report is used only for maintaining a local group membership. 4. Otherwise (i.e., the host is outside the scope requested), the HDR(k) ignores the IGMP_RID_Request(R/S). 5. Once the host gets an IGMP_RID_Reply(R/S), it records the GA in its receiver or source GA list. When it receives an IGMP_Query later, it issues IGMP_Report(R/S) with the GA in response to the IGMP_Query. 6. If the host is a source, it sets up the host forwarding cache for the GA after receiving the IGMP_RID_Reply(S). This cache is used to insert the RID as an IP option in the IP header of outgoing multicast packets and is transparent to the applications. 4.2 Establishing the HLIM Multicast Tree Once a HDR receives an IGMP_RID_Request from a multicast receiver or source (distinguished by a flag inside the message) and the host is within the scope requested, it invokes the HLIM_Join(R) operation for receiver and HLIM_Join(S) operation for source to establish the multicast tree. Note that the HLIM control messages are multicast to a well-known "all-HDR" multicast address with IP TTL of 1. The detailed procedure is described below: 1. When the HDR(k) receives the IGMP_RID_Request(R/S) and the host is Telcordia Technologies Expires June 2001 [Page 8] Internet Draft HLIM December 2000 within the scope requested, it initiates the regular join operation by sending HLIM_Join(R) for a receiver, or HLIM_Join(S) for a source, to its parent HDR (HDR(k+1)) via its U_IF. 2. When the HDR(k+1) receives a HLIM_Join(R/S), it checks the followings: - If it is outside the scope region (k > H or k < L or RID != HDR(H+1)) or the message is received from its U_IF (i.e., from a peer, not child, HDR), it ignores the message. - Otherwise, if it is an on-tree HDR (i.e., with an existing receiver/source forwarding cache for the group), it issues a HLIM_ACK(R/S) back to its child HDR(k) via its D_IF. - Otherwise, if it is located at the highest level of the scope region (i.e., k=H), it sets up a "confirmed" forwarding cache for the group and sends a HLIM_ACK(R/S) back to its child HDR(k) via its D_IF. - Otherwise, it sets up a "transient" forwarding cache for the group and relays the HLIM_Join(R/S) to its parent HDR (HDR(k+2)) via its U_IF. 3. The HDR(k+2) repeats the last step. Eventually, the HLIM_Join(R/S) message reaches an on-tree HDR or the highest HDR for the GA, and then a HLIM_ACK(R/S) is returned. 4. When a HDR receives a HLIM_ACK(R/S) massage, it will check the followings: - If it has a "transient" forwarding cache for the GA specified in the HLIM_ACK(R/S) message and receives the message from the U_IF, it switches the "transient" forwarding cache to the "confirmed" forwarding cache and becomes an on-tree HDR for the group. It then forwards the message to the D_IF. - Otherwise, the message is ignored. 5. Eventually, the HDR(k) receives a HLIM_ACK(R/S) message and establishes the "confirmed" forwarding cache for the group. It then sends an IGMP_RID_Reply with the RID back to the host. Fig. 4-1 shows examples of the HLIM receiver join operation. The IGMP_RID_Request from the invalid receiver is discarded since the receiver is located outside of the scope region. The join message from the receiver 1 is forwarded up to the highest HDR on the scope region, HDR(4), and this HDR issues a HLIM_ACK down to the HDR to which the receiver is attaching. On the other hand, the join message from the receiver 2 traverses only up to the HDR(3) which is an on- tree HDR and a HLIM_ACK is returned by this on-tree HDR. The operations are the same for a source except that the messages are marked "S" instead of "R". Telcordia Technologies Expires June 2001 [Page 9] Internet Draft HLIM December 2000 Fig. 4-1 HLIM operations for a receiver joining a group 4.3 Forwarding Multicast Packets When a HDR receives a multicast packet (denoted as MP[G(L,H,APL_ID,RID), S]), it simply forwards the packet to the outgoing interfaces indicated in the "confirmed" forwarding cache for the addressed group (if any), except the incoming interface of the packet. If the cache does not exist, the packet is discarded. 5. HLIM Mobility Functions The basic concept to support mobility in HLIM is to figure out whether a mobile node (host or network) has moved within or outside the original scope region of an on-going multicast session. If the mobile node has moved within the scope region, the baseline operations described in the previous section are applied. If the mobile node has moved outside the scope region, the mobility operations are invoked. The main idea for the mobility operations is to extend the established multicast tree for a mobile host or network through a binding point (BPT). A BPT is the HDR that provides linkage between the original scope region and the new location of a mobile node through the shortest path. It is located at the bottom of the original scope region for the mobile node which has moved beneath the scope region. It is the root of the original scope region if the mobile node has moved outside (but not below) the scope region. Through the BPT, a mobile node outside its original scope region can continue to receive or send multicast packets from the sources or to the receivers in the same multicast session. It should be noted that all the multicast packets are still delivered to/from the new location of the mobile node through the shortest path. Two examples of BPTs are shown Fig. 5-1. Fig. 5-1 Example BPTs for mobile nodes Each HDR keeps a list of all its ascendant HDRs (referred as HDR list) and updates its HDR list whenever any of its ascendant HDRs is changed. If a HDR moves to a new location, it will get a new HDR list. When the movement of a mobile host (or network) engaged in a multicast session is detected, the new parent HDR of the mobile host or the root of the mobile network will determine the movement type (i.e., inside or outside the scope region) with respect to its on- going multicast sessions. For example, the determination of movement type for the mobile host 1 and the mobile network shown in Fig. 5-1 takes place at HDR'(1) and HDRn(2), respectively. Similar to Mobile IP, mobility detection mechanism is built into HLIM. This is to eliminate the dependence of HLIM on other protocols (e.g., the lower layers, or Mobile IP). However, if other mobility detection mechanism Telcordia Technologies Expires June 2001 [Page 10] Internet Draft HLIM December 2000 is available, HLIM could interact with the other scheme (e.g., the radio layer) instead to provide a more efficient mobility detection. 5.1 Forwarding Caches in HDR In order to forward multicast packets and support mobility, each HDR maintains R_MFC (multicast forwarding cache for receivers) and S_MFC (multicast forwarding cache for sources) lists. The followings are possible entries in the forwarding cache lists. In the R_MFC list: For R_MFC located within the scope region of the multicast group, {GA, R, Out_IF[L_IF]}, {GA, R, Out_IF[D_IF]}, {GA, R, Out_IF[L_IF;D_IF]} For R_MFC located outside the scope region of the multicast group, {GA, MR, Out_IF[L_IF]}, {GA, MR, Out_IF[D_IF]}, {GA, MR, Out_IF[L_IF;D_IF]}, {GA, MR, Out_IF[U_IF]}, {GA, MR, Out_IF[L_IF;U_IF]}. In the S_MFC list: For S_MFC located within the scope region of the multicast group, {GA, S, Out_IF[D_IF]}. For S_MFC located outside the scope region of the multicast group, {GA, MS, Out_IF[D_IF]}, {GA, MS, Out_IF[U_IF]}. GA is a HLIM group address which contains SB(L,H), APL_ID, and RID. R/S/MR/MS indicates the type of the cache: R for receiver-created cache located within the scope region of the multicast group, S for source-created cache located within the scope region of the multicast group, MR for receiver-created cache located outside the scope region of the multicast group, and MS for source-created cache located outside the scope region of the multicast group. In software implementation, a flag will be used in the cache to differentiate between source and receiver. Whether a cache is located inside or outside a scope region will be determined by a HDR by comparing the RID in its cache and the HDR(H+1)'s ID in its HDR list when the cache is processed by an operation, rather than using a flag. If the two IDs are the same and k is between L and H, the cache is inside the scope region; otherwise, it is outside the scope region. In the rest of the document, we will also use these notations (R/S/MR/MS) to refer to receivers or sources inside or outside the scope region. Out_IF[L_IF/D_IF/U_IF] indicates the outgoing interface(s) that a multicast packet of the GA should be forwarded to. 5.2 HLIM Host Mobility Telcordia Technologies Expires June 2001 [Page 11] Internet Draft HLIM December 2000 Hosts in the hierarchical IP network are allowed to move to anywhere in the network. Note that the "original" scope region refers to the scope region in which a multicast group is started by a mobile host through the HLIM baseline operations. New messages added into the current IGMP protocol to handle host mobility explicitly are IGMP_M_Report, IGMP_M_Reply and IGMP_Hello. 5.2.1 Host Mobility Detection The IGMP_Hello message is used to detect host mobility. A HDR periodically sends IGMP_Hello to its local subnet at the rate of 1 message per 1 to 5 seconds (the rate can be adaptive to the degree of mobility). Note that IGMP_Hello and IGMP_Query are independent. The transmission rate of the former message is higher and its size is smaller for efficiency. The IGMP_Hello message informs local hosts of the change of their parent HDRs. If a host does not receive the IGMP_Hello from its current parent HDR for a certain period (one or more transmission periods of the IGMP_Hello) but receives an IGMP_Hello from another HDR, it considers itself attached to the other HDR. This could happen when a host moves and affiliates to a new HDR at a new location, or when a new HDR is elected. Once a host detects its mobility through the IGMP_Hello message, it issues an IGMP_M_Report(R/S) message (R for receiver and S for source) to its new parent HDR for every multicast session it has. 5.2.2 IGMP Operations for a Mobile Host When a mobile host engaged in a multicast session detects its movement to a new location at level k, the following procedure will be invoked: 1. The mobile host issues an IGMP_M_Report[GA, R/S] message to its new parent HDR(k) at the new location, where GA is G[L,H,RID,APL_ID]. 2. Upon receiving the IGMP_M_Report, the HDR(k) finds out whether the mobile host moved within or outside the original scope region by the following comparisons: - H = N (where N is the number of levels in the hierarchy) and k L - H < N and L <= k <= H and RID = HDR(H+1) in the HDR list If one of these conditions satisfies, the HDR(k) determines that the mobile host has moved within the original scope region. Otherwise, the mobile host has moved out of the original scope region. 3. If the HDR(k) has already a membership record for the requested GA, it returns an IGMP_M_Reply[GA, R/S] to the host. Otherwise, it invokes the HLIM regular join operation by sending a HLIM_Join[GA, R/S] to its U_IF if the host moved within the original scope region, or starts the mobile join operation by sending a HLIM_M_Join[GA, R/S] toward the RID. After completing the join procedure and tree Telcordia Technologies Expires June 2001 [Page 12] Internet Draft HLIM December 2000 adjustment, the HDR(k) sends an IGMP_M_Reply[GA, R/S] back to the mobile host. 5.2.3 Adjusting the HLIM Tree for a Mobile Host The new HDR to which a source or receiver has moved invokes the mobile join operation by sending a HLIM_M_Join(R/S) toward the RID of the affected multicast session. On the way toward the RID, if the message reaches an on-tree HDR outside the scope region or the BPT, a HLIM_M_ACK(R/S) message is returned and the multicast tree will be extended along the path. The procedure is described below: 1. When the new HDR receives and accepts an IGMP_M_Report(R/S) from its local subnet and has no existing member for the requested GA, it adds the GA into its membership database. It then looks up the unicast routing table to find out the outgoing interface toward the RID. If an IGMP_M_Report(R) is received, the HDR sets up a "transient" forwarding cache with L_IF set in the Out_IF. If an IGMP_M_Report(S) is received, the HDR sets up a "transient" forwarding cache with the outgoing interface toward the RID set in the Out_IF. The HDR then sends a HLIM_M_Join(R/S) message toward the RID. Note that the HLIM_M_Join(R/S) message is sent in multicast so that all HDRs in the subnet attached to the outgoing interface will receive it. 2. When a HDR receives a HLIM_M_Join(R/S) message, it determines if it is the BPT for the mobility. If its own address = RID or the address of its ascendant HDR(H+1) = RID and its level = L, it is the BPT and then go to step 4. Otherwise, proceed to step 3. 3. If a HDR is not the BPT, it first determines the outgoing interface toward the RID from the unicast routing table. If the outgoing interface is the same as the incoming interface of the HLIM_M_Join(R/S) message, the HDR discards the message. Otherwise, it processes the message as follows: - If the HDR is on-tree for the group (i.e., it already has the receiver/source forwarding cache that the received HLIM_M_Join(R/S) tries to set up), it stops forwarding the HLIM_M_Join(R/S) and replies with a HLIM_M_ACK(R/S) message to the incoming interface of the HLIM_M_Join. - Otherwise, the HDR sets up a "transient" forwarding cache for the group with the incoming interface of the HLIM_M_Join (for receiver) or the outgoing interface toward the RID (for source) set in the Out_IF. It then forwards the HLIM_M_Join(R/S) to the outgoing interface toward the RID. 4. When the BPT receives the HLIM_M_Join(R/S) message: - If the level of the BPT = L (i.e., at the bottom of the scope region) and the message is received from the D_IF, it returns a Telcordia Technologies Expires June 2001 [Page 13] Internet Draft HLIM December 2000 HLIM_M_ACK(R/S) to the D_IF. If it is not yet an on-tree HDR for the group, it sets up a "transient" forwarding cache with the D_IF set in the Out_IF and issues a regular HLIM_Join(R/S) message to its U_IF, which is then processed as in the regular case. - If the BPT = RID and the message is received from the U_IF, it returns a HLIM_M_ACK(R/S) to the U_IF. If the required receiver/source forwarding cache does not exist, it sets up a "confirmed" forwarding cache for the group with the U_IF (for receiver) or D_IF (for source) set in the Out_IF. - Otherwise, the message is ignored. 5. When a HDR receives a HLIM_M_ACK(R/S) for a group, if it has the corresponding "transient" forwarding cache and the message is received from the outgoing interface toward the RID, it switches the cache to a "confirmed" cache and forwards the HLIM_M_ACK(R/S) to the Out_IF in the cache for receiver, or to the interface opposite to the Out_IF in the cache for source. Otherwise, the message is ignored. 6. Eventually, the new HDR receives a HLIM_M_ACK(R/S) from the outgoing interface toward the RID. It then switches the "transient" forwarding cache for the group into the "confirmed" state and returns a IGMP_M_Reply to the mobile host. Some example operations for host mobility are shown in Fig. 5-2. Since mh1 has moved within the scope region, only the regular join operations are invoked. Since mh2 and mh3 have moved out of the scope region, the mobile join operations are performed between the new HDR serving mh2 and the BPT_L, and between the new HDR serving mh3 and the BPT_H. The prune operation is not shown in the figure. Fig. 5-2 Join operations for a mobile host after movement Fig. 5-3 depicts how multicast packets are forwarded from mobile sources and to mobile receivers after their movements. Fig. 5-3 Example multicast forwarding for mobile sources and receivers After the source or receiver moves away, the previous parent HDR at the old location will invoke the prune operation if no other sources or receivers of the affected multicast sessions exist in its local subnet. The prune operation eliminates unnecessary branches of the multicast trees. The details of the prune operation will be described later. 5.3 HLIM Network Mobility We assume that a network movement in the hierarchical IP network is Telcordia Technologies Expires June 2001 [Page 14] Internet Draft HLIM December 2000 allowed only within the same level. A router at level k can only move to the same level at another branch of the hierarchy. It can move with all of its descendant networks (including its local subnet), its local subnet only, or alone. Our design goal is to hide any network mobility from the hosts or routers within the moving network. In other words, no operations are required from the hosts or routers inside the moving network. Only the "topmost" router interacts with the outside of the moving network to hand over any on-going multicast sessions to the new location. Only the movement of an on-tree HDR (i.e., the HDR with one or more forwarding caches established by HLIM_Join or HLIM_M_Join) will invoke mobility operations to hand over all the on-going multicast sessions through that router. 5.3.1 Network Mobility Detection A child HDR detects its own mobility and a new parent HDR through periodic HLIM_Parent_Hello messages. A parent HDR periodically multicasts the HLIM_Parent_Hello message to its child HDRs. If a child HDR has not received the HLIM_Parent_Hello from its current parent for a certain number of the message period and receives the message from a new parent HDR, it considers itself moved to the new parent. It then exchanges HLIM_HDR_List_Solict and HLIM_HDR_List_Update with the new parent HDR to obtain the HDR list at the new location. If it has ongoing multicast sessions, it invokes the appropriate network mobility operations to extend the multicast trees. When a child HDR attaches to a parent HDR, the parent keeps a record of the new child. When a parent HDR receives a HLIM_HDR_List_Solicit or HLIM_Child_Hello (whichever comes first) from a new child HDR, it adds the new child's address into its children list. Each child HDR periodically multicasts a HLIM_Child_Hello message to its parent HDR and a parent HDR detects a child moved away through the periodic HLIM_Child_Hello messages. If a parent HDR has not received the HLIM_Child_Hello from a child HDR for a certain number of the message period, it considers the child has moved to another location and invokes the appropriate network mobility operations to prune the unnecessary branches of the multicast trees. 5.3.2 Network Mobility Operations When a network moves to a new location, the root HDR updates its HDR list at the new location through the HLIM_HDR_List_Solicit and HLIM_HDR_List_Update operations. It then forwards the updated HDR list to its descendent HDRs through the HLIM_HDR_List_Update operation. It also determines the movement type of each on-going multicast session it has by the comparison described for the host mobility operation. Once the movement types are determined, the root HDR invokes appropriate operations for every entry in its R_MFC and S_MFC lists. Telcordia Technologies Expires June 2001 [Page 15] Internet Draft HLIM December 2000 - For entries with (R:D_IF), (S:U_IF), (MR:D_IF), or (MS:U_IF) for a GA, the regular or mobile join operation should be invoked because a regular/mobile source/receiver for the GA is located inside the moving network, thus the multicast tree of the GA needs to be extended to/from the moving network. The following join operations are invoked: - HLIM_Join(R) for (R:D_IF) - HLIM_Join(S) for (S:U_IF) - HLIM_M_Join(R) for (MR:D_IF) - HLIM_M_Join(S) for (MS:U_IF) All the join messages mentioned above are sent toward the RID of the GA and are processed as in the baseline and host mobility cases. - For entries with (MR:U_IF) or (MS:D_IF) for a GA, which imply that the moving network contains the RID of the GA, HLIM_Net_Join(R) or HLIM_Net_Join(S) operation is invoked. These network join messages are sent toward the old parent HDR at the old location. The operations are described later. At the old location, once the movement of a child HDR is detected, the old parent HDR initiates the HLIM_Compare(M) operation to its D_IF (i.e., into its lower core subnet) for the group addresses whose RIDs are not located inside the moving network. Through the operation, the old parent HDR finds out the unmatched forwarding caches that are no longer needed. It then removes the caches and invokes the appropriate prune operation to its U_IF: - HLIM_Prune(R) for (R:D_IF) - HLIM_Prune(S) for (S:U_IF) - HLIM_M_Prune(R) for (MR:D_IF) - HLIM_M_Prune(S) for (MS:U_IF) All the prune operations mentioned above are sent toward the RID. Note that the unwanted caches of the group addresses whose RIDs are located inside the moving network are removed by the HLIM_Net_Join(R/S) operation instead. 5.4 HDR List Update Operations As mentioned earlier, after a HDR moves to a new location, it will obtain a new HDR list from its new parent HDR through the HLIM_HDR_List_Solicit and HLIM_HDR_List_Update operations. It will then update its own HDR list and forward the list to its descendant HDRs through the HLIM_HDR_List_Update operation. The procedure is described below: 1. After a HDR moves to a new parent HDR, it sends a HLIM_HDR_List_Solicit message to the new parent HDR through its U_IF and then waits for a HLIM_HDR_List_Update message from the parent HDR. Telcordia Technologies Expires June 2001 [Page 16] Internet Draft HLIM December 2000 2. When the parent HDR receives the HLIM_HDR_List_Solicit message from its D_IF, it checks if the message is sent from a new child HDR, and if so, adds the new child's address into its children list. It then sends back a HLIM_HDR_List_Update message including its HDR list and its own address. 3. When a HDR receives a HLIM_HDR_List_Update message from its parent HDR, it will update its own HDR list. If it has child HDRs attached to its D_IF, it sends a HLIM_HDR_List_Update including its HDR list and its own address to the child HDRs. 5.5 HLIM Compare Operations for Mobility - HLIM_COMPARE(M) The HLIM compare for mobility operations are used by the parent and child HDRs at the old location of a moving network to remove any unwanted branches of the multicast trees affected by the movement. 1. When the parent HDR at the old location detects the movement of one of its child HDRs, it sends a HLIM_Compare(M) message to its child HDRs through its D_IF (i.e., toward its lower core subnet). It sets a Compare_Repeat_Timer during which the HLIM_Compare_Reply(M) messages from its child HDRs will be collected. A HLIM_Compare(M) message contains the inbound GAs for sources and outbound GAs for receivers at the HDR. "Inbound GAs" here refer to the group addresses of the forwarding caches with D_IF as an Out_IF (packets of the groups are sent "into" the core subnet through the D_IF). Similarly, "outbound GAs" refer to the group addresses of the forwarding caches with L_IF or U_IF as an Out_IF (packets of the groups are sent "out" of the core subnet through the L_IF and U_IF). 2. When a child HDR receives a HLIM_Compare(M) from its parent HDR from its U_IF, it sets two timers: a Compare_RandTimer which is a random timer (its maximum value should be less than the Compare_Repeat_Timer mentioned above) to wait before sending a HLIM_Compare_Reply(M), and a Compare_Timer (its value should be longer than the maximum time for the parent HDR to finish all the retransmissions of the HLIM_Compare(M)) during which the HLIM_Compare_Reply(M) messages from its neighboring HDRs will be collected. A HLIM_Compare_Reply(M) is multicast and contains the inbound GAs for sources and outbound GAs for receivers. "Inbound GAs" here refer to the group addresses of the forwarding caches with U_IF as an Out_IF (packets of the group addresses are sent "into" the core subnet through the U_IF). Similarly, "outbound GAs" refer to the group addresses of the forwarding caches with L_IF or D_IF as an Out_IF (packets of the group addresses are sent "out" of the core subnet through the L_IF and D_IF). 3. When the Compare_Repeat_Timer expires, the parent HDR checks if it Telcordia Technologies Expires June 2001 [Page 17] Internet Draft HLIM December 2000 has received the reply from all of its child HDRs. If not, it retransmits the HLIM_Compare(M) message and starts the Compare_Repeat_Timer again. This operation is repeated until the maximum number of trials. The repeated transmissions are to increase the reliability of this operation. 4. When a child HDR has its Compare_Timer expire or the parent HDR receives replies from all of its children or finishes the maximum number of HLIM_Compare(M) transmissions, the HDR will perform the following comparison: - The HDR compares its own outbound GAs for sources and the inbound GAs for sources in all the HLIM_Compare_Reply(M) messages received. It deletes the caches of its outbound GAs with no matching inbound GAs and then invokes an appropriate prune operation to its U_IF. - The HDR compares its own inbound GAs for receivers and the outbound GAs for receivers in all the HLIM_Compare_Reply(M) messages received. It deletes the caches of its inbound GAs with no matching outbound GAs and then invokes an appropriate prune operation to its U_IF. 5.6 HLIM Prune Operations The following events result in an invocation of a prune operation at a HDR: - when a local source moves away or leaves a multicast group, - when the R_MFC for a GA is deleted (e.g., after a multicast receiver moves away or leaves the multicast group), - when an unmatched GA is found by the HLIM_Compare(M) operation (e.g., after a network movement). 5.6.1 HLIM_Prune(S) and HLIM_M_Prune(S) 1. When a GA is registered in the source group membership list in a HDR, a prune timer is set for the GA. The timer is refreshed by IGMP_Report, which is sent in response to the periodic IGMP_Query. 2. If the prune timer expires, the HDR (e.g., HDR1 in Fig. 5-4 and Fig. 5-5) deletes the GA from the membership list and is ready to prune the associating outgoing interface (D_IF or U_IF) for the GA listed in the S_MFC. 3. It sets a prune timer (Prune_Expire_Timer) for the outgoing interface and issues a number ( 2) of source prune messages (HLIM_Prune(S) or HLIM_M_Prune(S)) to the interface opposite to the listed outgoing interface (one after another separated by a certain time interval). For instance, the message is sent to D_IF if U_IF is listed in S_MFC. The repeated transmissions of the source prune message are to increase the reliability of the message especially in a harsh environment. 4. When the prune timer expires, if no prune reply Telcordia Technologies Expires June 2001 [Page 18] Internet Draft HLIM December 2000 (HLIM_Prune_Reply(S) or HLIM_M_Prune_Reply(S)) arrives from the interface to which the source prune message has been sent, the S_MFC is deleted and a source prune message is issued through the outgoing interface of the cache just deleted (i.e., toward the RID of the GA). Otherwise, it keeps the S_MFC. 5. When a HDR receives a source prune message, it checks whether the GA is listed in its S_MFC list or not. If the GA is not listed, it (e.g., HDR4 in Fig. 5-5) will discard the prune message. If the GA is listed, it will compare the Out_IF of the GA listed in the S_MFC with the incoming interface of the prune message received. - If the listed Out_IF is the same as the incoming interface, the HDR (e.g., HDR4 in Fig. 5-4, HDR2, HDR5 in Fig. 5-5) sets a prune reply random timer and then returns a prune reply (HLIM_Prune_Reply(S) or HLIM_M_Prune_Reply(S)) when the random timer expires. If it receives a prune reply message while the random timer is running, it stops the timer. - If the listed Out_IF is not the same as the incoming interface, the HDR (e.g., HDR3 in Fig. 5-5) checks if there is a member of the GA in its source membership list. - If yes, it ignores the source prune message received. - Otherwise, it sets a prune timer on the S_MFC for the GA and waits for a prune reply. If it doesn't receive a prune reply before the prune timer expires, it deletes the S_MFC and sends a number of source prune messages through the outgoing interface of the deleted cache (i.e., toward the RID of the GA). If it receives a prune reply before the prune timer expires, it keeps the S_MFC. If it receives the same source prune message again while the timer is running, it ignores the message. This operation proceeds to the HDR(H) for HLIM_Prune(S) and the RID for HLIM_M_Prune(S). Note that the total time needed to transmit all the prune messages should be shorter than the prune timer, and the interval between two consecutive prune messages should be longer than the maximum value of the prune reply random timer. The following two figures show some examples of the source prune operation and the operational details are presented as well. In these examples, the prune messages are assumed to be sent twice. Fig. 5-4 First example of Source Prune Operation Once HDR1 detects no source for a GA on its local subnet, it sets two timers, a prune timer and a prune tramsission timer, and a prune- reply counter. The prune timer is set to prune the outgoing interface listed in its S_MRF (i.e., U_IF) and the prune transmission timer is Telcordia Technologies Expires June 2001 [Page 19] Internet Draft HLIM December 2000 set for issuing the second prune message. The prune reply counter counts the number of received prune-reply messages. The HDR sends the first prune message to the D_IF. As the prune transmission timer expires, it sends the second prune message. When HDR4 receives the first prune message through its U_IF which is the same as that listed in its S_MFC for the GA, it sets a prune random timer first and then sends a prune reply message after the random timer expires. It does the same for the second prune message received. The counter on HDR1 keeps counting the number of the received prune reply messages until its prune timer expries. When the prune timer expires, HDR1 checks the number indicated in the counter. If the number is greater than 0, HDR1 keeps the S_MFC. Fig. 5-5 Second example of Source Prune Operation In the case of Fig. 5-5, HDR1 first sends out the prune messages through its D_IF as described in the previous example. Since HDR1 doesn't receive any prune reply message, the prune reply counter at HDR1 is zero. It then deletes the S_MFC for the GA and sends the first prune message through the outgoing interface of the deleted cache. Once HDR2 and HDR5 receives a prune message, each of them sets a prune reply random timer since both of them have S_MFC for the GA with the outgoing interface the same as the incoming interface of the prune message received. As one of the timers expires while the other one is still running, a prune reply message is sent out by the HDR with the expired timer (e.g., HDR5). When the other HDR with a running timer (e.g., HDR2) receives the prune reply message, it will suppress its prune reply message by stopping its timer. When HDR3 receives a prune message from HDR1, it sets a prune timer and prune reply counter, and waits for prune reply messages. If it receives a prune reply message from either HDR2 and HDR5, it will increment the counter. In this case, it will receive two prune reply messages, each one from HDR2 and HDR5, unless the messages are lost due to bad wireless channel condition during the transmission. Since the number on the counter (2) is greater than 0, it keeps the S_MFC for the GA. If it receives the second prune message from HDR1 while its prune timer is running (which has been initiated by the first prune message), it will discard the second prune message. 5.6.2 HLIM_Prune(R) and HLIM_M_Prune(R) 1. When a GA is recorded in the receiver group membership list in a Telcordia Technologies Expires June 2001 [Page 20] Internet Draft HLIM December 2000 HDR, a prune timer is set for the GA. If the prune timer expires, the HDR deletes the GA from the membership list and the L_IF from the Out_IF list of the R_MFC. The timer is refreshed by IGMP_Report, which is sent in response to the periodic IGMP_Query. 2. When the Out_IF list of the R_MFC for a GA becomes empty, the HDR (e.g., HDR1 in Fig. 5-6) deletes the R_MFC and sends a receiver prune message (HLIM_Prune(R) or HLIM_M_Prune(R)) toward the RID of the GA. The receiver prune message can be sent multiple times ( 2) to increase the reliability of the message in a harsh environment. 3. Upon receiving a receiver prune message, a HDR finds a match for the GA in its R_MFC list. 4. If it finds a match, it compares the incoming interface of the prune message with the Out_IFs listed in its R_MFC of the GA. - If it has an Out_IF which is the same as the incoming interface, it (e.g., HDR2, HDR4 in Fig. 5-6) sets a prune timer for that Out_IF and a prune reply counter, and waits for a prune reply message (HLIM_Prune_Reply(R) or HLIM_M_Prune_Reply(R)). - As the HDR receives a prune reply message(s) before the prune timer expires, it increments the counter. When the prune timer expires, it checks the counter and it will keep the Out_IF if the number in the counter is greater than 0. If it receives the same receiver prune message again while the timer is running, it ignores the message. - If it doesn't receive any prune reply before the prune timer expires (i.e., the number in the counter is zero), it deletes the Out_IF and checks whether the Out_IF list for the GA is empty or not (since L_IF may still be listed). If the list is empty, it removes the R_MFC and sends a receiver prune message through the interface opposite to the deleted interface (i.e., toward the RID). - If the Out_IF list of the R_MFC includes the L_IF or the interface opposite to the incoming interface, it (e.g., HDR3 in Fig. 5-6) sets a prune reply random timer and returns a prune reply message (HLIM_Prune_Reply(R) or HLIM_M_Prune_Reply(R)) if the timer expires. If it receives a prune reply message from the incoming interface of the prune message before the timer expires, it stops the timer. This operation proceeds to the HDR(H) for HLIM_Prune(R) and the RID for HLIM_M_Prune(R). The following figure shows an example of the receiver prune operation, assuming the prune message is sent twice. Fig. 5-6 Receiver Prune Operation Once HDR1 finds that the R_MFC for a GA is empty, it deletes the Telcordia Technologies Expires June 2001 [Page 21] Internet Draft HLIM December 2000 cache and issues the first receiver prune message toward the RID (i.e., via the U_IF) and sets a prune transmission timer for sending the second prune message. If HDR2 receives a prune message, it sets a prune timer for the Out_IF (i.e., D_IF) listed in the R_MFC and a prune reply counter for counting incoming prune reply messages. As the prune timer expires, HDR2 checks the number in the counter. In this case, the number is zero since no prune reply message is received. Thus, HDR2 deletes the Out_IF and the R_MFC, and sends the first prune message to its U_IF and sets a prune transmission timer as the HDR1 did. Upon receiving a prune message, HDR3 sets a prune random timer since the incoming interface of the prune message is opposite to the Out_IF listed in its R_MFC for the GA. It responds a prune reply message when the prune random timer expires. In this case, it responds twice since it receives two prune messages from HDR2. When HDR4 receives a prune message from HDR2, it sets a prune timer and a prune reply counter since the incoming interface of the prune message is the same as the Out_IF listed in its R_MFC for the GA. Whenever HDR4 receives a prune reply message, it increments the counter. In this case, the number on the counter (2) is greater than 0 when the prune timer expires. Thus, it keeps the Out_IF in its R_MFC. 5.7 Network Join Operations: HLIM_Net_Join(R/S) The network join operation is used to handle a special case of network mobility in which the moving network contains the RID of an on-going multicast session. It is invoked by the root HDR of the moving network when the root HDR has the forwarding cache of (MR:U_IF) or (MS:D_IF). A HLIM_Net_Join(R/S) message is forwarded toward the old parent HDR at the old location and processed by the HDRs on the path to the old parent. The other HDRs (i.e., HDRs not on the path) will discard the message. 1. The root HDR sets the forwarding cache with U_IF for MR or D_IF for MS as outgoing interface to the transient state and sends a HLIM_Net_Join[GA, R/S] toward the old parent HDR. 2. When a HDR on the shortest path between the new location and the old parent HDR receives the HLIM_Net_Join message (i.e., the incoming interface of the message is opposite to the outgoing interface toward the old parent HDR), it checks if it has a R_MFC (if HLIM_Net_Join(R) is received) or S_MFC (if HLIM_Net_Join(S) is received) for the GA. - If the corresponding MFC is not found, the HDR will create a transient forwarding cache for the GA and relay the message toward the old parent as in the mobile join operation. The direction of the Telcordia Technologies Expires June 2001 [Page 22] Internet Draft HLIM December 2000 outgoing interface set in the forwarding cache is opposite to the mobile join operation: the outgoing interface for a HLIM_Net_Join[GA, R] message is listed as an Out_IF in the R_MFC for the GA and the incoming interface for a HLIM_Net_Join[GA, S] is listed as an Out_IF in the S_MFC for the GA. - Otherwise, it compares the incoming interface of the message with the Out_IF listed in its MFC. Note that L_IF is excluded in this comparison. For a HLIM_Net_Join[GA, R], - If the incoming interface is opposite to the listed Out_IF, the HDR ignores the message. - Otherwise, the listed Out_IF is switched to a "transient deleted" state and a new transient R_MFC pointing to the opposite interface is set. The HDR then forwards the HLIM_Net_Join toward the old parent HDR. For a HLIM_Net_Join[GA, S], - If the incoming interface and the listed Out_IF are the same, the HDR ignores the message. - Otherwise, the listed Out_IF is switched to a "transient deleted" state and a new transient R_MFC pointing to the opposite interface is set. The HDR then forwards the HLIM_Net_Join toward the old parent HDR. 3. The HLIM_Net_Join operation will proceed to the old parent HDR at the old location. When the old parent receives a HLIM_Net_Join[GA, R/S] from its U_IF, it sets up a confirmed forwarding cache for the GA pointing to the incoming interface (for source) or the interface opposite to the incoming interface (for receiver), and deletes the old cache. It then returns a HLIM_Net_Join_ACK toward the root HDR of the moving network and invokes the HLIM_Compare(M) operation to its D_IF. 4. When a HDR with a transient MFC for the GA receives a HLIM_Net_Join_ACK from the right interface (i.e., the outgoing interface toward the old parent HDR), it switches the MFC into a confirmed state and deletes the transient deleted cache. It then forwards the HLIM_Net_Join_ACK toward the root HDR of the moving network. Examples of the HLIM_Net_Join operation are presented below to help explain how the operation works. Fig. 5-7 Multicast Tree for HLIM_Net_Join Operation before Network Movement (Example 1) In the diagram shown above, two receivers have moved out of the scope region and continue to receive multicast packets of the session from Telcordia Technologies Expires June 2001 [Page 23] Internet Draft HLIM December 2000 the RID. The multicast tree of the session is represented by the arrows of U_IF, D_IF and L_IF. Fig. 5-8 HLIM_Net_Join(R) Operation after Network Movement (Example 1) In this first example, the network containing the RID of a GA (illustrated as the big circle in the figure) moves from the parent HDR at the old location to the new parent HDR, HDR2, at the new location. In the course of the HLIM_Net_Join(R) operation, each HDR proceeds as follows: Root HDR at a new location: - Once it detects its movement to a new location and finds a R_MFC with (MR:U_IF), it issues a HLIM_Net_Join[GA, R] toward the old parent HDR. HDR2 and HDR3: - Upon receiving a HLIM_Net_Join[GA, R], since it has the forwarding cache for the GA, it compares the incoming interface of the message with the Out_IF listed in the R_MFC (i.e., D_IF). - Because they are the same (i.e., both are D_IF), the listed Out_IF (D_IF) is switched to the "transient deleted" state. - Since it is on the path toward the old parent HDR, it sets up a transient forwarding cache, (MR:U_IF), for GA and relays the HLIM_Net_Join[GA, R] message toward the old parent HDR. - If it receives a HLIM_Net_Join_ACK , it will switch the forwarding cache with the transient state to the confirmed state and remove the forwarding cache with the "transient deleted" state. HDR5: - Since it has the forwarding cache for the GA, it compares the incoming interface of the message with the Out_IF listed in the R_MFC (i.e., U_IF). Because they are the same (i.e., both are U_IF), the listed Out_IF (U_IF) is switched to the "transient deleted" state. - It sets up a transient forwarding cache, (MR:D_IF), for GA and relays the HLIM_Net_Join[GA, R] message toward the old parent HDR. - When it receives a HLIM_Net_Join_ACK, it will switch the forwarding cache with the transient state to a confirmed state and remove the forwarding cache with the "transient deleted" state. Parent HDR: - Since it has the forwarding cache for the GA, it compares the incoming interface of the message with the Out_IF listed in its R_MFC (i.e., U_IF). Because they are the same (i.e., both are U_IF), the listed Out_IF (U_IF) is deleted. - It sets up the confirmed Out_IF of the GA opposite to the incoming Telcordia Technologies Expires June 2001 [Page 24] Internet Draft HLIM December 2000 interface of the message and sends a HLIM_Net_Join_ACK to the incoming interface. - It invokes the HLIM_Compare(M) operation. HDR1, HDR4, HDR21 and HDR22 ignore the HLIM_Net_Join/HLIM_Net_Join_ACK messages received. The diagram below shows the adjusted multicast tree resulted from the HLIM_Net_Join(R) operation. As we can see, shortest path multicasting is preserved after the network movement. The Out_IF (D_IF) listed in HDR5 and Parent HDR will be deleted through the HLIM_Compare(M) and HLIM_M_Prune operations at the end since they are not needed. Fig. 5-9 Resultant Multicast Tree after the HLIM_Net_Join(R) Operation (Example 1) The next two diagrams show another example of the HLIM_Net_Join(R) operation. The same logic and operations described in the previous example are applied. Fig. 5-10 HLIM_Net_Join(R) Operation after Network Movement (Example 2) Fig. 5-11 Resultant Multicast Tree after the HLIM_Net_Join(R) Operation (Example 2) The diagrams below show the examples for the HLIM_Net_Join(S) operation. The HLIM_Net_Join(S) operation is very similar to the HLIM_Net_Join(R), except that the logic of setting up forwarding caches and the comparison between the incoming interface of the HLIM_Net_Join message and the Out_IF listed in the S_MFC is reversed. Fig. 5-12 Multicast Tree for HLIM_Net_Join(S) Operation before Network Movement (Example 1) Fig. 5-13 HLIM_Net_Join(S) Operation after Network Movement (Example 1) Fig. 5-14 Resultant Multicast Tree after the HLIM_Net_Join(S) Operation (Example 1) Telcordia Technologies Expires June 2001 [Page 25] Internet Draft HLIM December 2000 Fig. 5-15 HLIM_Net_Join(S) Operation after Network Movement (Example 2) Fig. 5-16 Resultant Multicast Tree after the HLIM_Net_Join(S) Operation (Example 2) 6. HLIM Survivability Functions As described earlier, there may be more than one router in a subnet (local or core) for backup purpose. A HDR will be elected to handle all HLIM/IGMP control messages and forward multicast traffic. The HDR election is done through the IGMP_Hello message in a local subnet and the HLIM_Parent_Hello message in a core subnet. When the elected HDR moves away, malfunctions or is destroyed, a new HDR will be elected again among the backup routers and then recover the multicast forwarding caches and membership information in the previous HDR by some local operations. 6.1 HLIM Election Process Though the current IGMP specification defines a finite state machine for the IGMP_Query that could be used for election, the procedure would switch the status of a router back and forth between "elected" and "not elected" due to message loss, timing difference or new router coming. We therefore define a different finite state machine to make the election process more stable. The process at a HLIM router is described below with reference to the state diagram shown: 1. When a HLIM router is initialized, it sets its timer (T1) to d, where d is a random value between 0 and HoldTime and moves to the idle state. 2. If the HLIM router gets a HLIM_Parent_Hello[pref] through its D_IF before T1 expires and the pref is lower than its own pref (or if the pref is equal to its own pref but the source IP address is lower than its own IP address), it resets its timer (T1) to one or more PeriodTime + d and moves back to the idle state. 3. If T1 expires, the HLIM router sends a HLIM_Parent_Hello[pref] into the core subnet via its D_IF, and sets its timer (T2) to HoldTime and its counter (N) to 1. The pref is the preference value of the HLIM router. A lower pref value indicates that the router is more preferred to be a HDR. A HLIM_Parent_Hello[pref] is multicast to all the other HLIM routers in the same core subnet. The router then moves to the transient state. 4. If the HLIM router gets a HLIM_Parent_Hello[pref] through its D_IF Telcordia Technologies Expires June 2001 [Page 26] Internet Draft HLIM December 2000 before T2 expires and the pref is lower than its own pref (or if the pref is equal to its own pref but the source IP address is lower than its own IP address), it sets its timer (T1) to one or more PeriodTime + d and moves back to the idle state. 5. If T2 expires and N is below a threshold (which is set to allow the HDR to send the HLIM_Parent_Hello multiple times before becoming elected in case the message is lost), the HLIM router sends out the HLIM_Parent_Hello[pref] again, increments its counter (N), and restart its timer (T2) to HoldTime. 6. If T2 expires and N reaches the threshold, the HLIM router will: - Assume itself to be elected, set its pref to zero, and move to the elected state. - Send a HLIM_Parent_Hello[0] to its D_IF. - Reset its timer (T3) to PeriodTime. 7. When T3 expires, the HLIM router sends the HLIM_Parent_Hello[0] to its D_IF again and restarts its timer (T3) to PeriodTime. Figure 6-1. State Diagram of HLIM election process If the elected HDR keeps sending the periodic HLIM_Parent_Hello[0] message, the backup routers will refresh its timer and remain in the idle state (transition 2). If the elected HDR has moved away, malfunctioned, or been destroyed, no periodic HLIM_Parent_Hello[0] message will be received and the timer (T1) of one of the backup routers will eventually expire first and then send out a HLIM_Parent_Hello[pref] (transition 3). The election of a local HDR is elected similarly using the IGMP_Hello message. After a new HDR is elected, it will perform the followings: 1. Similar to a network mobility case, the newly elected HDR exchanges HLIM_HDR_List_Solicit and HLIM_HDR_List_Update with its parent HDR to obtain the HDR list of its ascendant HDRs, updates the list, and forwards it in a HLIM_HDR_List_Update to its descendant HDRs. 2. It then invokes the HLIM compare for election (HLIM_Compare(E)) operations as described below to recover the caches originally in the previous HDR. The local membership will be recovered by the IGMP_Report or IGMP_M_Report sent by the local hosts after the new HDR is elected. 6.2 HLIM Compare Operations for Election - HLIM_Compare(E) 1. When a new HDR is elected, it issues a HLIM_Compare(E) message to both its U_IF (i.e., toward its upper core subnet) and D_IF (i.e., Telcordia Technologies Expires June 2001 [Page 27] Internet Draft HLIM December 2000 toward its lower core subnet). The transmission of the HLIM_Compare(E) message will be repeated after a certain time interval (Compare_Repeat_Timer) for a number of times ( 1) to increase the reliability of this operation. 2. When a HDR receives a HLIM_Compare(E) from an interface (U_IF or D_IF), it sets two timers: a Compare_RandTimer which is a random timer (its maximum value should be less than the Compare_Repeat_Timer mentioned above) to wait before sending a HLIM_Compare_Reply(E), and a Compare_Timer (its value should be longer than the maximum time for the new HDR to finish all the retransmissions of the HLIM_Compare(E)) during which the HLIM_Compare_Reply(E) messages from its neighboring HDRs will be collected. A HLIM_Compare_Reply(E) is multicast and contains the inbound GAs for receivers and outbound GAs for sources. Inbound GAs refer to those GAs whose caches have the incoming interface of the HLIM_Compare(E) as an outgoing interface. Outbound GAs refer to those GAs whose caches have an outgoing interface opposite to the incoming interface of the HLIM_Compare(E). 3. When a HDR has its Compare_Timer expire, the HDR will perform the following comparison: - The HDR compares its own outbound GAs for receivers and the inbound GAs for receivers in all the HLIM_Compare_Reply(E) messages received. It invokes HLIM_Join(R) (if the HDR is inside the scope region of the GA) or HLIM_M_Join(R) (if the HDR is outside the scope region of the GA). - The HDR compares its own inbound GAs for sources and the outbound GAs for sources in all the HLIM_Compare_Reply(E) messages received. It invokes HLIM_Join(S) (if the HDR is inside the scope region of the GA) or HLIM_M_Join(S) (if the HDR is outside the scope region of the GA). 4. If the new HDR replaces the RID of the GA of an on-going multicast session, it will invoke the HLIM_Flush and IGMP_Flush operations to update the forwarding caches of the established multicast tree. The HLIM_Flush is sent through the whole multicast tree to update the caches with the affected RID. - The new HDR elected will send a HLIM_Flush[old RID, new RID] to any D_IF and U_IF listed in the affected caches in its R_MFC and S_MFC lists, and an IGMP_Flush[old RID, new RID] to the L_IF if it is listed in the caches. - When a HDR receives a HLIM_Flush, it will check if it has any forwarding caches with the old RID. - If matches are found, it will update the caches with the new RID. It will then forward the HLIM_Flush to the Out_IF (U_IF or D_IF) indicated in the caches, except the incoming interface of the message, and IGMP_Flush to the L_IF if it is listed in the caches. Telcordia Technologies Expires June 2001 [Page 28] Internet Draft HLIM December 2000 - Otherwise, it will ignore the message. - When a host receives an IGMP_Flush, it will update its own records for any active multicast sessions of the old RID. Note that the new HDR elected may send the HLIM_Flush and IGMP_Flush for several times in case there is any message loss. 7. HLIM Reliability Considerations Throughout the design of the HLIM protocol design, control message reliability has always been taken into account. Reliability measures are built into the design. Three main schemes are used to handle control message loss and increase reliability at the HLIM protocol level. Additional reliability can be provided by the lower layers (such as forward error correction, automatic repeat request, etc.) but they are outside the scope of the HLIM design. The three reliability schemes used in HLIM are described below: Periodic transmission - Some of the HLIM/IGMP messages are transmitted periodically, or sent in response to periodic messages. If they are lost, another one will always be sent at the next period or in response to the next periodic message. Acknowledgment and retransmission - Two-way handshake is applied to some of the HLIM/IGMP messages. If the acknowledgment of a protocol message is not received by the message originator within a timeout period (i.e., either the message or the acknowledgment is lost), the message, and thus the acknowledgment, will be retransmitted until the maximum number of trials (the maximum number is chosen according to the target operating environments). Multiple transmissions - In some cases, two-way handshake is difficult to implement. Multiple transmissions will be used instead. A protocol message will be sent consecutively for multiple times (the number of transmissions is chosen according to the target operating environments). Some reply messages may be sent in response to these protocol messages. Such a reply message will be returned for each of the repeated messages received. In the case that a message/reply is lost, there are other chances for the target recipient to receive the message/reply. The following table lists the reliability scheme used for each control message. Table 1 The Methods Applied for Increasing Reliability in HLIM Operations HLIM Control Operations Methods of Reliable Transport Telcordia Technologies Expires June 2001 [Page 29] Internet Draft HLIM December 2000 for Control Message Regular Membership Periodic transmission Operation - IGMP_Query - IGMP_Report Mobile Membership Operation Acknowledgment and - IGMP_M_Report retransmission - IGMP_M_Reply RID Retrieval Operation Acknowledgment and - IGMP_RID_Request retransmission - IGMP_RID_Reply Host Mobility Detection Periodic transmission - IGMP_Hello RID Update Operation (in Multiple transmissions local) - IGMP_Flush Join Operation Acknowledgment and - HLIM_Join retransmission - HLIM_ACK - HLIM_M_Join - HLIM_M_ACK Network Mobility Detection Periodic transmission - HLIM_Parent_Hello - HLIM_Child_Hello HDR List Update Operation Acknowledgment and (solicited) retransmission - HLIM_HDR_List_Solicit - HLIM_HDR_List_Update HDR List Update Operation Multiple transmissions (unsolicited) - HLIM_HDR_List_Update HLIM_Compare(E) Operation Multiple transmissions - HLIM_Compare(E) - HLIM_Compare_Reply(E) HLIM_Compare(M) Operation Acknowledgment and - HLIM_Compare(M) retransmission - HLIM_Compare_Reply(M) Telcordia Technologies Expires June 2001 [Page 30] Internet Draft HLIM December 2000 Prune Operation Multiple transmissions - HLIM_Prune - HLIM_Prune_Reply - HLIM_M_Prune - HLIM_M_Prune_Reply Network Join Operation Acknowledgment and - HLIM_Net_Join retransmission - HLIM_Net_Join_ACK RID Update Operation (in Multiple transmissions global) - HLIM_Flush 8. Security Considerations Security issues are not discussed in this document. 9. Acknowledgements The work on HLIM was funded by the U.S. Army CECOM under the contract DAAB07-98-C-D007. The authors would also like to thank Dr. Charles Graff and Mr. Michael Bereschinsky (of U.S. Army CECOM) for their continued support and active involvement in this work. 10. Intellectual Property Considerations Telcordia Technologies, Inc. may seek patent or other intellectual property protection for some of the technologies specified in this document. If any standards arising from this disclosure are or become protected by one or more patents assigned to Telcordia Technologies, Telcordia Technologies, Inc. intends to disclose those technologies and license them on reasonable and non-discriminatory terms. Future revisions of this draft may contain additional information on intellectual property protection sought or received. 11. Authors' Addresses Matthew Cheng Telcordia Technologies 331 Newman Springs Road Red Bank, NJ 07701-5699 Phone: (732) 758-2897 Email: mcheng@telcordia.com Telcordia Technologies Expires June 2001 [Page 31] Internet Draft HLIM December 2000 John Lee Telcordia Technologies 331 Newman Springs Road Red Bank, NJ 07701-5699 Phone: (732) 758-2896 Email: jolee@research.telcordia.com Mario Joa-Ng Telcordia Technologies 331 Newman Springs Road Red Bank, NJ 07701-5699 Phone: (732) 758-3377 Email: mjoang@research.telcordia.com 12. References 1. T. Pusateri, "Distance Vector Multicast Routing Protocol", Internet Draft. ftp://ftp.isi.edu/internet-drafts/draft-ietf-idmr- dvmrp-v3-08.txt, Feb. 1999. 2. J. Moy, "Multicast Extensions to OSPF", RFC 1584, March 1994. 3. S. Dearing, et. al., "Protocol Independent Multicast Version 2, Dense Mode Specification," Internet Draft, ftp://ftp.isi.edu/internt- drafts/draft-ietf-pimv2-dm-0.txt, Nov. 1998. 4. D. Estrin, et. al., "Protocol Independent Multicast-Sparse Mode (PIM-SM) : Protocol Specification", RFC 2362, June 1998. 5. A. Ballardie, "Core Based Trees (CBT) Multicast Routing Architecture", RFC 2201, September 1997. 6. A. Ballardie, "Core Based Trees (CBT version2) Multicast Routing - Protocol Specification," RFC 2189, Sep. 1997. 7. G. Xylomenos and G. C. Pdyzos, "IP Multicast for Mobile Hosts", IEEE Comm. Mag., Jan. 1997. 8. C. E. Perkins, "Mobile IP Design Principles and Practices", Addison Wesley, 1998. 9. R. Ramanathan and M. Steenstrup. "Hierarchically-organized, multi- hop mobile wireless networks for quality-of-service support", ACM Mobile Networks & Applications (MONET), June 1998. 10. C. Graff, "Future Network Architecture for Tactical Army Networks", IEEE talk, Viewgraphs available from Telcordia Technologies Expires June 2001 [Page 32] Internet Draft HLIM December 2000 graff@doim6.monmouth.army.mil. 11. W. Fenner, "Internet Group Management Protocol, version 2 (IGMPv2)," RFC 2236, Nov. 1997. Telcordia Technologies Expires June 2001 [Page 33]