HTTP/1.1 200 OK Date: Mon, 08 Apr 2002 22:53:47 GMT Server: Apache/1.3.20 (Unix) Last-Modified: Thu, 24 Jun 1999 15:11:16 GMT ETag: "2e79e3-b375-37724a94" Accept-Ranges: bytes Content-Length: 45941 Connection: close Content-Type: text/plain INTERNET-DRAFT Ljubica Blazevic Jean-Yves Le Boudec EPFL-ICA,Switzerland June 1999 Distributed Core Multicast (DCM): a routing protocol for many small groups with application to mobile IP telephony Status of this Memo This document is an Internet-Draft and is in full conformance with all provisions of Section 10 of RFC2026. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet-Drafts. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet- Drafts as reference material or to cite them other than as "work in progress." The list of current Internet-Drafts can be accessed at http://www.ietf.org/ietf/1id-abstracts.txt The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html. 1. Abstract This document specifies a multicast routing protocol called Distributed Core Multicast (DCM). It is intended for use within a large single Internet domain network with a very large number of multicast groups with a small number of receivers. Such a case occurs, for example, when multicast addresses are allocated to mobile hosts, as a mechanism to manage Internet host mobility. For such networks, existing dense or sparse mode multicast routing algorithms do not scale well with the number of multicast groups. DCM is based on an extension of the centre-based tree approach [1], [2]. It uses several core routers, called Distributed Core Routers (DCRs) and a special protocol between them. DCM aims: (1) to avoid multicast group state information in backbone routers, (2) to avoid triangular routing across expensive backbone links, (3) to scale well with the number of multicast groups. We analyse how DCM can be used to route packets to mobile hosts in cellular IP telephony, where each mobile Blazevic, Le Boudec Expires 12/99 [Page 1] INTERNET-DRAFT draft-blazevic-dcm-mobility-00.txt June 1999 host is assigned a multicast address in every domain it visits. The benefits of multicasting-based approach to route packets to mobile hosts are low latency and no disruption during handover. 2. Introduction This document describes a multicast routing protocol called Distributed Core Multicast (DCM). DCM is designed to provide low overhead delivery of multicast data in a large single domain network for a very large number of small groups. This occurs when the number of multicast groups is very large (for example, greater than a million), the number of receivers per multicast group is very small (for example, less than five) and each host is a potential sender to a multicast group. In this document, we present how DCM can be used in cellular IP telephony. Each mobile host is assigned a multicast address in every domain it visits. DCM is then used to route packets to mobile hosts that are distributed within a large Internet domain. MSP-IP (Mobility support using Multicasting in IP)[3] proposes a generic architecture to support host mobility in the Internet by using multicasting as the mechanism to route packets to the mobile hosts. The routing protocol used in this architecture is out of scope of MSP-IP. DCM is an extension of an existing multicast routing protocol that scales better than other existing protocols when applied to support mobile hosts. Recent sparse mode multicast routing protocols, such as the protocol independent multicast (PIM-SM) [2] and the core-based trees (CBT) [1], build a single delivery tree per multicast group that is shared by all senders in the group. This tree is rooted at a single centre router called "core" in CBT, and "rendezvous point" (RP) in PIM-SM. Both centre-based routing protocols have the following potential shortcomings: traffic for the multicast group is concentrated on the links along the shared tree, mainly near the core router; finding an optimal centre for a group is a NP-complete problem and requires the knowledge of the whole network topology [4]. Current approaches typically use either an administrative selection of centres or a simple heuristics [5]. Data distribution through a single centre router could cause non optimal distribution of traffic in the case of a bad positioning of the centre router with respect to senders and receivers. This problem is known as a triangular routing problem. DCM is based on an extension of the centre-based tree approach and is designed for the efficient and scalable delivery of multicast data under the assumptions that are satisfied when multicast is used to support mobile hosts (large number of multicast groups, a few receivers per group and a potentially large number of senders to a multicast group). We consider a network model that consists of several areas connected via the backbone area (see Figure 1). The Blazevic, Le Boudec Expires 12/99 [Page 2] INTERNET-DRAFT draft-blazevic-dcm-mobility-00.txt June 1999 issues addressed by DCM are: (1): to avoid multicast group state information in backbone routers, (2): to avoid triangular routing across expensive backbone links and (3) to scale well with the number of multicast groups. The benefits of using the multicasting-based approach to route packets to the mobile hosts are low latency and no disruption during handover. When a visiting host arrives into the new domain it is assigned a temporary multicast address that it keeps as long as it stays in the same domain. The base station of the current cell where the mobile lies is responsible for joining the multicast tree on behalf of the mobile. Mobile hosts communicate with base stations over wireless links. Neighbouring base stations that anticipate the arrival of the mobile can initiate its group membership registration. Thus, a multicast group assigned to a mobile host has a few recipients. When the mobile host moves in the new cell, it continues to receive packets without disruption. DCM is particularly well suited to route packets to mobile hosts since the size of its multicast group is small. Mobile IP [6] proposal is intended to support macro-level mobility and relatively slow moving hosts. Mobile IP requires that after each migration of the mobile host its possibly distant home agent is informed about the mobile host's current location. In an environment with highly mobile hosts, Mobile IP is no longer a good solution. The Cellular IP proposal [7] separates local mobility from wide area mobility. It proposes a new mobility management within a Cellular IP network. Cellular IP can interact with Mobile IP to support wide area mobility, that is, mobility between Cellular IP networks. A Cellular IP network consists primarily of base stations that keep distributed data bases with location information referring to a mobile host. Base stations use this information to route packets to the mobile host while it is in a Cellular IP Network. Our approach, DCM, can be used for a new mobility management approach within a large single domain network based on multicasting. DCM is not an alternative to Mobile IP [6] since DCM is not a solution to wide-area mobility. In contrast, DCM can be used as an alternative to Cellular IP within a single domain network. In this document we describe how DCM can be in used in conjunction with the Session Initiation Protocol (SIP)[8] to support terminal mobility in cellular IP Telephony (IPtel). In [9] it is proposed to introduce minor changes in SIP to support terminal mobility in IPtel. We expect a solution based on DCM to be more scalable, in particular in the management of fast or small scale mobility. DCM, when used with SIP, is a scalable solution, able to manage a handover of mobile hosts with minimal disturbance. 2.1 Distributed Core Multicast (DCM) Protocol Overview We consider a network model that consists of several areas Blazevic, Le Boudec Expires 12/99 [Page 3] INTERNET-DRAFT draft-blazevic-dcm-mobility-00.txt June 1999 connected via the backbone area. We introduce an architecture that is based on several core routers per multicast group, called Distributed Core Routers (DCRs). - The DCRs in each area are located at the edge of the backbone. The DCRs act as backbone access points for the data sent by senders inside their area to receivers outside this area. A DCR also forwards the multicast data received from the backbone to receivers in the area it belongs to. When a host wants to join the multicast group M, it sends a join message. This join message is propagated hop-by-hop to the DCR inside its area that serves the multicast group. Conversely, when a sender has data to send to the multicast group, it will send the data encapsulated to the DCR assigned to the multicast group. - The Membership Distribution Protocol (MDP) runs between the DCRs serving the same range of multicast addresses. It is fully distributed. MDP enables the DCRs to learn about other DCRs that have group members. - The distribution of data uses a special mechanism between the DCRs in the backbone area, and the trees rooted at the DCRs towards members of the group in the other areas. We propose a special mechanism for data distribution between the DCRs, which does not require that non-DCR backbone routers perform multicast routing. With the introduction of the DCRs close to any sender and receivers, converging traffic is not sent to a single centre router in the network. Data sent from a sender to a group within the same area is not forwarded to the backbone. Our approach alleviates the triangular routing problem common to all centre-based trees, and unlike PIM-SM, is suitable for groups with many sporadic senders. ++++++++ + + + + + Area D + + + + + + + ++++++++++ +-+----+-+ + Area A + |DCR X4 | + + + ---+----+ ++++++++++ + + + + + + + (3) + + BACKBONE + + + + A2<<----- +------+ + + +--------+ (1) + + |DCR X1|+ <-----+ +--- +| DCR X3 | <<------C1 + + A1 ---->> +------+ + | | + +--------+ + + (1) + + (2)| (2)| + + + + + + | v + + Area C + + + +---+----+ ++++++++++++ Blazevic, Le Boudec Expires 12/99 [Page 4] INTERNET-DRAFT draft-blazevic-dcm-mobility-00.txt June 1999 +++++++++++ |DCR X2 | +-+---+--+ + ^ + + ^ + + | + + |(1) + + | + + B1 + + + + Area B1 + + + +++++++ Figure 1: Model of a large single domain network and an overview of data distribution with DCM. We show one multicast group M and DCRs X1, X2, X3 and X4 that serve a range to which M belongs to. Step (1): Senders A1, B1 and C1 send data to the corresponding DCRs inside their areas. Step (2): DCRs distribute the multicast data across the backbone area to DCR X1 that needs it. Step (3): X1 sends data to the local receivers in its area (in this example this is A2. 2.2 Terminology - DCR. A DCR (Distributed Core Router) is an backbone access point for the data sent to multicast address by senders inside the same area to members outside the area. A DCR also forwards the multicast data received from the backbone to receivers in the area it belongs to. - DCR serves the multicast address m. A DCR is said to serve the multicast address m when it is dynamically elected among all the candidate DCRs in the area to act as an access point for address m (see Section 3.1). - Labelled DCR. A DCR is labelled with the multicast address m if the DCR serves m and there are receivers for m in its area. A labelled DCR is root of a distribution subtree inside its area for m (see Section 3.2). - Source DCR. A source DCR for the multicast group m is the DCR that receives encapsulated multicast data for m by some source inside its area (see Section 3.3). - Range. A range is the partition of the set of multicast addresses into group of addresses. A DCR can serve several ranges of multicast addresses (see Section 3.1). - MDP(Membership Distribution Protocol). MDP is used for the source DCR in one area to learn about labelled DCRs in other areas. MDP is run between DCRs in different areas that serve the same range of multicast addresses (see Section 3.4). - MDP control multicast address. An MDP control multicast address is used for exchanging MDP control messages between DCRs that serve the same range of multicast addresses. There Blazevic, Le Boudec Expires 12/99 [Page 5] INTERNET-DRAFT draft-blazevic-dcm-mobility-00.txt June 1999 is one MDP control multicast address per range of multicast addresses(see Section 3.4). - STH(Shortest Tunnel Heuristic). STH is used by the source DCR to compute the multicast data distribution tree in the backbone. The edges of this tree are tunnels between DCRs. (see Appendix) 3. Distributed Core Multicast (DCM) Protocol Functional Description In this section, we describe the various elements of DCM. Those are: - addressing issues; - how hosts join the multicast group; - how senders send to a multicast group; - how membership information is distributed among DCRs; - how multicast data is distributed among DCRs; - how multicast data is forwarded from DCR to members of the group inside its area. 3.1 Addressing Issues In each area there are several routers that are configured to act as candidate DCRs. The identities of the candidate DCRs are known to all routers within an area by means of an intra-area bootstrap protocol [10]. This is similar to PIM-SM with the difference that the bootstrap protocol is constrained within an area. This entails a periodic distribution of the set of reachable candidate DCRs to all routers within an area. Routers use a common hash function to map a multicast group address to one router from the set of candidate DCRs. For a particular group address M, we use the hash function to determine the DCR that serves*M. * A DCR is said to serve the multicast group address M when it is dynamically elected among all the candidate DCRs in the area to act as an access point for address M The used hash function is h(r(M),DCR_i). Function r(M) takes as input a multicast group address and returns the range of the multicast group, while DCR_i is the unicast IP address of the DCR. The target DCR_i is then chosen as the candidate DCR with the highest value of h(r(M),DCR_j)) among all j in {1,...,J} where J is the number of candidate DCRs in an area: h(r(M),DCR_i)=max { h(r(M),DCR_j),j=1,..,J } One possible example of the function that gives the range is: Blazevic, Le Boudec Expires 12/99 [Page 6] INTERNET-DRAFT draft-blazevic-dcm-mobility-00.txt June 1999 r(M)=M&B, where B is a bit mask. We do not present here the hash function theory. For more information see [11], [10] and [12]. The benefits of using hashing to map a multicast group to DCR are the following: - We achieve minimal disruption of groups when there is change in the candidate DCR set. This means that we have to do a small number of re-mappings of multicast groups when there is a change in the candidate DCR set. See [11] for more explanations. - We apply the hash function h(.,.) as defined by the Highest Random Weight (HRW) [12] algorithm. This function ensures load balancing between candidate DCRs. This is very important, because no single DCR serves more multicast groups than any other DCR inside the same area. We achieve, by this property, that when the number of candidate DCRs increases, the load on each DCR decreases. All routers in all non-backbone areas should apply the same functions h(.,.), r(.). Each candidate DCR is aware of all the ranges of multicast addresses for which it is elected to be a DCR in its area. There is a function m(r(M)) that maps the range of the multicast group address M to another multicast address for control purposes. A DCR joins a control multicast address that corresponds to a range of multicast addresses that it serves. This multicast address is used by DCRs in different areas that serve the same range of multicast addresses to exchange control information. 3.2 How hosts join the multicast group When a host is interested in joining the multicast group M, it issues an IGMP[13] join message. A multicast router on its LAN, known as the designated router (DR), receives the IGMP join message. The DR determines the DCR inside its area that serves M, as described in Section 3.1. The process of establishing the group shared tree is like in PIM-SM [2]. The DR sends a JOIN message towards the determined DCR. Sending a JOIN message forces any off-tree routers on the path to the DCR to forward a JOIN message and join the tree. Each router on the way to the DCR keeps a forwarding state for M. When a JOIN message reaches the DCR, this DCR becomes labelled with the multicast group M. In this way, the delivery subtree, for the receivers of the multicast group M in an area, is established. The subtree is maintained by periodically refreshing the state information for M in the routers (like in PIM-SM, this is done by periodically sending JOIN messages). Blazevic, Le Boudec Expires 12/99 [Page 7] INTERNET-DRAFT draft-blazevic-dcm-mobility-00.txt June 1999 Like in PIM-SM, when the DR discovers that there are no longer any receivers for M, it sends a PRUNE message towards the nearest DCR to disconnect from the shared distribution tree. 3.3 How senders send to a multicast group The sending host originates native multicast data, for the multicast group M, that is received by the designated router (DR) on its LAN. The DR determines the DCR within its area that serves M. We call this DCR the source DCR. The DR encapsulates the multicast data packet (IP-in-IP) and sends it with a destination address equal to the address of the source DCR. The source DCR receives the encapsulated multicast data. This is similar to PIM-SM where the DR sends encapsulated multicast data to the RP corresponding to the multicast group. 3.4 How membership information is distributed among DCRs The Membership Distribution Protocol (MDP) is used by DCRs in different areas to exchange control information. As is explained in Section 3.1, within each non-backbone area, for each range of multicast addresses there is one DCR serving that range. DCRs in different areas that serve the same range of multicast addresses are members of the same MDP control multicast group. This group is defined by a MDP control multicast address used for exchanging control information. A DCR joins as many MDP control multicast groups as the number of ranges of multicast addresses it serves. There are as many MDP control multicast groups as there are possible ranges of multicast addresses. We do not propose a specific protocol for maintaining the multicast tree for the MDP multicast group. This can be done by means of an existing multicast routing protocol (e.g CBT). DCRs that are members of the same MDP control multicast group exchange the following control information: - periodical keep-alive messages. - unicast distance information. Each DCR sends, to the corresponding MDP control multicast group, information about the unicast distance from itself to other DCRs that it has learned to serve the same range of multicast addresses. This information comes from existing unicast routing tables and it is used for the distribution of multicast data among the DCRs. - multicast group information. A DCR, which is labelled with the multicast group M, informs DCRs in other areas responsible for M that it has receivers for M. In this way, every DCR keeps a record of every other DCR that has at least one member for a multicast address from the range that the DCR serves. A DCR Blazevic, Le Boudec Expires 12/99 [Page 8] INTERNET-DRAFT draft-blazevic-dcm-mobility-00.txt June 1999 should notify all other DCRs when it becomes labelled with a new multicast group or no longer labelled with a multicast group. MDP uses its MDP control multicast addresses and performs flooding inside the groups defined by those addresses. An alternative approach would be to use MDP servers. This approach leads to a more scalable, but also a more complex solution. This approach is not studied in detail in this document. 3.5 How multicast data is distributed among DCRs The multicast data for the group M is distributed from a source DCR to all DCRs that are labelled with M. Since we assume that the number of receivers per multicast group is not large, there are only a few labelled routers per multicast group. Our goal is to perform multicast data distribution in the backbone in such a way that backbone routers keep a minimal state information while at the same time backbone bandwidth is used efficiently. We propose a solution that can be applied in the Internet today. It uses point-to-point tunnels to perform data distribution among DCRs. With this solution, non-DCR backbone routers do not keep any state information related to the distribution of the multicast data in the backbone. Point-to-Point Tunnels The DCR that serves the multicast group M keeps the following information: (1) a set V of DCRs that serve the same range to which M belongs; (2) information about unicast distances between each pair of DCRs from V; (3) the set L of labelled DCRs for M. The DCR obtains this information by exchanging the MDP control messages with DCRs in other areas. In this way, we present the virtual network of DCRs that serve the same range of multicast group addresses by means of an undirected complete graph G=(V,E). V is defined above, while the set of edges E are tunnels between each pair of DCRs in V. Each edge is associated with a cost value that is equal to an inter-DCR unicast distance. The source DCR, called S, calculates the optimal tree that spans the labelled DCRs. In other words, S finds the subtree T=(V_T,E_T) of G that spans the set of nodes L such that cost(T)=sum cost(e) is minimised. e in E_T We recognise this problem as the Steiner tree problem. Instead Blazevic, Le Boudec Expires 12/99 [Page 9] INTERNET-DRAFT draft-blazevic-dcm-mobility-00.txt June 1999 of finding the exact solution, that is a NP-complete problem, we introduce a simple heuristic called Shortest Tunnel Heuristic (STH). The description of STH is given in the Appendix at the end of this document. ++++++++ + + + Area D + + + + + + + ++++++++++ +-+----+-+ + + |DCR X4 | + + + ---+----+ ++++++++++ + + + | + + + + + + (1)| + + + + +------+ + | + +--------+ + + |DCR X1|+ <-----+ | +---> +| DCR X3 | + + +------+ + (2)| | |(3) + +--------+ + + + + | | | + + + + + + | V | + + Area C + + Area A + +---+----+ ++++++++++++ +++++++++++ |DCR X2 | +-+---+--+ + + At 1: + + +-----+-----+---------+++ + + |sa=X4|da=X2|opt=X1;X3|++ + + +-----+-----+---------+++ + + + Area B + At 2: +++++++++ +-----+-----+++ |sa=X2|da=X1|++ +-----+-----+++ sa: source address At 3: da: destination address +-----+-----+++ opt: end-to-end option |sa=X2|da=X3|++ +++ +-----+-----+++ |++ : encapsulated multicast data packet +++ Figure 2: Figure presents an example of inter-DCR multicast data distribution by using point-to-point tunnels. The source DCR is X4 and labelled DCRs are X1 and X3. X4 calculates the distribution tunnel tree to X1 and X3 by applying the STH heuristic presented in the Appendix. Assume that the result of STH gives the distribution tunnel tree consisting of edges X4-X2, X2-X1 and X2-X3. Then X4 sends the encapsulated multicast data packet to X2. In the end-to-end option field of the packet, a distribution list is contained. X2 sends two copies of multicast data: one to X1 and the other to X3. On Blazevic, Le Boudec Expires 12/99 [Page 10] INTERNET-DRAFT draft-blazevic-dcm-mobility-00.txt June 1999 this figure are also presented packet formats at various points (points 1, 2 and 3) on the way from X4 to X1 and X3. The source DCR applies STH to determine the distribution tunnel tree from itself to the list of labelled DCRs for the multicast group. The source DCR puts inter-DCR distribution information in the form of an explicit distribution list in the end-to-end option field of the packet header. Under the assumption that there is a small number of receivers per multicast group, the number of labelled DCRs for a group is also small. Thus, an explicit distribution list that completely describes the distribution tunnel tree is not expected to be long. When a DCR receives a packet from another DCR, it reads from the distribution list whether it should make a copy of the multicast data and of the identities of the DCRs where it should send multicast data by tunneling. Labelled DCRs deliver data to local receivers in the corresponding area. An example that shows how multicast data is distributed among DCRs is presented in Figure 2. 3.6 How multicast data is forwarded from DCR to members of the group inside its area A DCR receives encapsulated multicast data packets either from a source that is within its area, or from a DCR in another area. A DCR checks if it is labelled with the multicast group that corresponds to the received packet, i.e whether there are members of the multicast group in its area. If this is the case, a DCR forwards the multicast packet along the distribution subtree that is already established for the multicast group (as is described in Section 3.2). 4. DCM and cellular IP telephony In this section we present how DCM can be used to route packets to mobile hosts in cellular IP telephony (IPtel). We assume that the Session Initiation Protocol (SIP)[8] is used to establish, modify and terminate IPtel calls. Here we describe how DCM can be used in conjunction with SIP to support terminal mobility. Terminal mobility is the ability to maintain a communication when a host is moving from one location to another during the call. The owner of the mobile host is identified by its SIP URL address. A SIP server in the mobile host's home domain can be identified from this address. When the mobile host moves into the new domain it is assigned a temporary multicast address that it keeps as long as it stays in the same domain. How a multicast address is assigned to a mobile host is out of scope of this document. Then the mobile registers with a SIP server in its home domain in order to be found. Blazevic, Le Boudec Expires 12/99 [Page 11] INTERNET-DRAFT draft-blazevic-dcm-mobility-00.txt June 1999 During the registration process, the mobile host sends to its home SIP server the anycast address of its current domain and its assigned multicast address. In each domain there are border routers that are configured with the domain anycast address and are responsible for accepting and forwarding packets for the mobile hosts that are in the domain. The domain anycast address is a reserved unicast address. Border routers configured with the anycast address recognise the anycast address as one of their logical interfaces. The routing of packets to the anycast address is done by standard unicast routing mechanisms. A caller that wants to establish a call with the mobile host has the knowledge of the mobile host's SIP URL address. Then, a caller contacts a SIP server in the mobile host's home domain for the mobile host's current location. A SIP server acts in the redirect mode and returns to the caller information about the anycast address of the mobile host's current domain and its assigned multicast address. A caller sends to the mobile host a SIP INVITE message. If the caller is also mobile, it informs the callee about its domain's anycast address and its assigned multicast address. When the sender to the mobile host and the mobile host are in the same domain, packets for the mobile host are destined to the mobile host's multicast address and are routed by DCM. This is done as explained in Section 3. If the sender and the mobile host are in different domains, multicast packets to the mobile host should first reach the domain where the mobile lies. We distinguish two cases to achieve this depending on the used version of the IP protocol. In the case of IPv6, a source sends a packet to the mobile host by using a loose source routing option. A source sets the destination field of the packet header to the multicast address assigned to the mobile host and the IPv6 routing header is set to the mobile host's domain router anycast address. A packet is routed to the nearest border router in the mobile host's domain that is configured with the anycast address. The next address to be visited is the multicast address assigned to the mobile host. DCM is used to route packets from the border router to the mobile host. In the case of IPv4, the sender sends multicast packets for the mobile host encapsulated (IP-in-IP) to the anycast address of the mobile host's current domain. The nearest border router that is configured with the anycast address decapsulates the multicast packet and, as in the case of IPv6, a packet is forwarded to the mobile host by using DCM. As explained in Section 3.1, for the mobile host's assigned multicast address, within each area, there exists a DCR that serves that multicast address. Those DCRs are responsible for forwarding packets to the mobile hosts within a domain. As said before, the DCRs run the Blazevic, Le Boudec Expires 12/99 [Page 12] INTERNET-DRAFT draft-blazevic-dcm-mobility-00.txt June 1999 MDP control protocol and are members of a MDP control multicast group for exchanging MDP control information. A multicast router in the mobile host's cell initiates a joining the multicast group assigned to the mobile host. Typically this router coexists with the base station in the cell. As described in Section 3.2 the JOIN message is propagated to the DCR inside the area that serves the mobile host's multicast address. Then, the DCR sends to the MDP control multicast group a MDP control message when the mobile host is registered. + + + + + + + + + + Area D + + + + + + + + + + + + + + + + + + + + +-+---+-+ Area A + |DCR X4 | + + +---+---+ + + + + + + + + + + + join + + + + + +----------> +-------+ (4) +------+ (3) +------+ + + (1)/ |DCR X1 | <-------------|DCR X3| <---|Sender| + / (2)+--> +-------+ +------+ +------+ + + / / + + + + + +-+-+ join/ + + + + Area C + + |BS1| / + +-------+ + + + + + + +-+-+ +-+-+ + |DCR X2 | + ^ |BS2| + +-+---+-+ _| +---+ + + + + | + + + V + + + + +-+-+ + + Area B + |MH | + + + + + + + + +-+-+ + + + + + + + + Figure 3: The mobile host (MH) is assigned multicast address M. Four DCRs, X1, X2, X3 and X4 serve M. Step (1): Base station BS1 sends a join message for M towards X1. X1 informs X2, X3 and X4 that it has a member for M. Step (2): Advance registration for M in a neighbouring cell is done by BS2. Step(3): The sender sends a packet to multicast group M. Step (4): The packet gets delivered through the backbone to X1. Step (5): X1 receives encapsulated multicast data packet. From X1 data is forwarded to BS1 and BS2. MH receives data from BS1. In order to reduce packet latency and losses during a handover, advance registration can be performed. The goal is that when a mobile host moves to a new cell, the base station in the new cell should Blazevic, Le Boudec Expires 12/99 [Page 13] INTERNET-DRAFT draft-blazevic-dcm-mobility-00.txt June 1999 already started receiving data for the mobile host. The mobile host continues to receive the data without disruption. There are several ways to perform this: - A base station that anticipates the arrival of a mobile host initiates joining the multicast address assigned to the mobile host. This is illustrated in one example in Figure 3. The mechanism by which the base station anticipates the arrival of the mobile host is out of the scope of this document. - In the case where bandwidth is not expensive on the wired network, all neighbouring base stations can start receiving data destined to a mobile host. This guarantees that there would be no latency and packet losses during a handover. A packet for the mobile host reaches all base stations that joined the multicast group assigned to the mobile host. At the same time the mobile host receives data only from a base station in its current cell. A base station that receives a packet on behalf of the mobile host that is not present in its cell can either discard a packet or buffer it for a certain interval of time (e.g. 10ms). Further research is needed to determine what is the best approach. Here we describe in more details how advance registration is performed. At its current cell, the mobile host receives data along the distribution subtree that is established for the mobile host's multicast address. This tree is rooted at the DCR and maintained with periodical sending of join messages. Now, suppose that the base station in the neighbouring cell anticipates arrival of the mobile host. It begins a joining process for the multicast group assigned to the mobile host. This process is terminated when a JOIN message reaches a router that is already on the distribution tree. When the cells are close to each other, joining is terminated at the lowest branching point in the distribution tree. This ensures that the neighbouring base station quickly becomes a part of the multicast distribution tree with low overhead. The neighbouring base station can start joining the multicast group assigned to the mobile host after the mobile host leaves its previous cell. Routers on the distribution tree keep forwarding information for a given time, even if the previous base station stops refreshing the tree because the mobile host leaves its cell. As before, if the base stations are close to each other, the multicast distribution tree for the new base station can be established in a short period of time that makes handover efficient. 5. Security Considerations Currently, DCM does not specify any special security measures. As in any routing protocols, however, there are a number of potential Blazevic, Le Boudec Expires 12/99 [Page 14] INTERNET-DRAFT draft-blazevic-dcm-mobility-00.txt June 1999 security attacks possible. The use of authentication on all packets (i.e. IPSec authentication headers) is recommended to avoid such attacks. 6. Open Issues Since DCM is intra-domain routing protocol it is left for future work to examine interoperability of DCM with other inter-domain routing protocols. In this document we do not address the problems of using multicast routing to support end-to-end unicast communication. These problems are related to protocols such as: TCP, ICMP, IGMP, ARP. A simple solution to this problem could be to have a special range of unicast addresses that are routed as multicast addresses. In this way, packets destined to the mobile host are routed by using a multicast mechanism. Conversely, at the end systems, these packets are considered as unicast packets and standard unicast mechanisms are applied. Appendix Shortest Tunnel Heuristic (STH) STH consists of two phases. In the first phase a greedy tree is built by adding one by one the nodes that are closest to the tree under construction, and then removing unnecessary nodes. The second phase is further improving the tree established so far. The definitions of V, G, L and T are given in Section 3.5. STH is as follows: Phase 1: Build a greedy tree - Step 1: Begin with a subtree T of G consisting of the singe node S. k=1. - Step 2: if k=n then goto Step 4. n is the number of nodes in set V. - Step 3: Determine a node z_(k+1) in V, z_(k+1) not in T closest to T (ties are broken arbitrarily). Add the node z_(k+1) to T. k=k+1. Goto Step 2. - Step 4: Remove from T non-labelled DCRs of degree* 1 and degree 2** (one at a time). * Degree of a node in a graph is the number of edges incident with a node ** A node of degree 2 is removed by its two edges being replaced by a single edge (tunnel) connecting the two nodes adjacent to the node being removed. The source DCR is never removed from a graph. Blazevic, Le Boudec Expires 12/99 [Page 15] INTERNET-DRAFT draft-blazevic-dcm-mobility-00.txt June 1999 Phase 2: Improve a greedy tree STH can be further improved by two additional steps: - Step 5: Determine a minimum spanning tree for the subnetwork of G induced by the nodes in T (after the step 4). - Step 6: Remove from the minimum spanning tree non-labelled DCRs of degree 1 and 2 (one at a time). The resulting tree is the (suboptimal) solution. 7. References [1] A. Ballardie. Core Based Trees (CBT) Multicast Routing Architecture. RFC 2201, September 1997. [2] D. Estrin et.all. Protocol Independent Multicast-Sparse Mode (PIM-SM): Protocol Specification. RFC 2117, June 1997. [3] Jayanth Mysore and Vaduvur Bharghavan. A New Multicasting-based Architecture for Internet Host Mobility. In The Third Annual ACM/IEEE International Conference on Mobile Computing and Networking (MobiCom'97). [4] Liming Wei and Deborah Estrin. The Trade-offs of Multicast Trees and Algorithms. In Proc.of the 1994 International Conference on Computer Communications and Networks, San Francisco, CA, USA, September 1994. [5] David G. Thaler and Chinya V. Ravishankar. Distributed Center-Location Algorithms. IEEE JSAC, 15(3), April 1997. [7] Andras G. Valko. Cellular IP: A New Approach to Internet Host Mobility. ACM SIGCOMM Computer Communicastion Review, January 1999. [6] C. Perkins. IP Mobility Support, Network Working Group. RFC 2002, October 1996. [8] M. Handley and H. Schulzrinne et. all. SIP: Session Initiation Protocol. RFC 2543, 1999. [9] E. Wedlund and H. Schulzrinne. Mobility support using SIP. In Proc. of ACM/IEEE International Conference on Wireless and Mobile Multimedia (WoWMoM'99), Seattle, Washington, August 1999. [10] Deborah Estrin, Mark Handley, Ahmed Helmy, Polly Huang, and David Thaler. A Dynamic Mechanism for Rendezvous-based Multicast Routing. In Proc. of IEEE INFOCOM'99, New York, USA, March 1999. [11] Vinod Valloppillil and Keith W. Ross. Cache Array Routing Protocol v1.0. INTERNET-DRAFT, 1998. Blazevic, Le Boudec Expires 12/99 [Page 16] INTERNET-DRAFT draft-blazevic-dcm-mobility-00.txt June 1999 [12] D. G. Thaler and C. V. Ravishankar. Using Name-Based Mappings to Increase Hit Rates. IEEE/ACM Transactions on Networking, 6(1), February 1998. [13] W. Fenner. Internet Group Management Protocol, Version 2. RFC 2236, November 1997. 8. Author's address Ljubica Blazevic Jean-Yves Le Boudec Institute for computer Communications and Applications Swiss Federal Institute of Technology (EPFL) CH-1015 Lausanne Switzerland email: Ljubica.Blazevic, leboudec@epfl.ch Blazevic, Le Boudec Expires 12/99 [Page 17]