idnits 2.17.1 draft-blazevic-dcm-mobility-01.txt: ** The Abstract section seems to be numbered Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** Looks like you're using RFC 2026 boilerplate. This must be updated to follow RFC 3978/3979, as updated by RFC 4748. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- ** Missing expiration date. The document expiration date should appear on the first and last page. ** The document is more than 15 pages and seems to lack a Table of Contents. == No 'Intended status' indicated for this document; assuming Proposed Standard Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack an IANA Considerations section. (See Section 2.2 of https://www.ietf.org/id-info/checklist for how to handle the case when there are no actions for IANA.) ** The document seems to lack separate sections for Informative/Normative References. All references will be assumed normative when checking for downward references. ** There are 26 instances of too long lines in the document, the longest one being 6 characters in excess of 72. ** The abstract seems to contain references ([2], [1]), which it shouldn't. Please replace those with straight textual mentions of the documents in question. Miscellaneous warnings: ---------------------------------------------------------------------------- == Line 6 has weird spacing: '...or many small...' == Line 7 has weird spacing: '...groups with a...' -- The document seems to lack a disclaimer for pre-RFC5378 work, but may have content which was first submitted before 10 November 2008. If you have contacted all the original authors and they are all willing to grant the BCP78 rights to the IETF Trust, then this is fine, and you can ignore this comment. If not, you may need to add the pre-RFC5378 disclaimer. (See the Legal Provisions document at https://trustee.ietf.org/license-info for more information.) -- The document date (June 2000) is 8714 days in the past. Is this intentional? Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) ** Downref: Normative reference to an Historic RFC: RFC 2201 (ref. '1') ** Obsolete normative reference: RFC 2117 (ref. '2') (Obsoleted by RFC 2362) -- Possible downref: Non-RFC (?) normative reference: ref. '3' -- Possible downref: Non-RFC (?) normative reference: ref. '4' -- Possible downref: Non-RFC (?) normative reference: ref. '5' -- Possible downref: Non-RFC (?) normative reference: ref. '7' ** Obsolete normative reference: RFC 2002 (ref. '6') (Obsoleted by RFC 3220) ** Obsolete normative reference: RFC 2543 (ref. '8') (Obsoleted by RFC 3261, RFC 3262, RFC 3263, RFC 3264, RFC 3265) -- Possible downref: Non-RFC (?) normative reference: ref. '9' -- Possible downref: Non-RFC (?) normative reference: ref. '10' -- Possible downref: Non-RFC (?) normative reference: ref. '11' -- Possible downref: Non-RFC (?) normative reference: ref. '12' Summary: 12 errors (**), 0 flaws (~~), 3 warnings (==), 10 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 1 INTERNET-DRAFT Ljubica Blazevic 2 Jean-Yves Le Boudec 3 EPFL-ICA,Switzerland 4 June 2000 6 Distributed Core Multicast (DCM): a routing protocol for many small 7 groups with application to mobile IP telephony 9 11 Status of this Memo 13 This document is an Internet-Draft and is in full conformance 14 with all provisions of Section 10 of RFC2026. 16 Internet-Drafts are working documents of the Internet Engineering 17 Task Force (IETF), its areas, and its working groups. Note that 18 other groups may also distribute working documents as 19 Internet-Drafts. 21 Internet-Drafts are draft documents valid for a maximum of six 22 months and may be updated, replaced, or obsoleted by other 23 documents at any time. It is inappropriate to use Internet- 24 Drafts as reference material or to cite them other than as 25 "work in progress." 27 The list of current Internet-Drafts can be accessed at 28 http://www.ietf.org/ietf/1id-abstracts.txt 30 The list of Internet-Draft Shadow Directories can be accessed at 31 http://www.ietf.org/shadow.html. 33 1. Abstract 35 This document specifies a multicast routing protocol called 36 Distributed Core Multicast (DCM). It is intended for use within a 37 large single Internet domain network with a very large number of 38 multicast groups with a small number of receivers. Such a case 39 occurs, for example, when multicast addresses are allocated to mobile 40 hosts, as a mechanism to manage Internet host mobility. For such 41 networks, existing dense or sparse mode multicast routing algorithms 42 do not scale well with the number of multicast groups. DCM is based 43 on an extension of the centre-based tree approach [1], [2]. It uses 44 several core routers, called Distributed Core Routers (DCRs) and a 45 special protocol between them. DCM aims: (1) to avoid multicast group 46 state information in backbone routers, (2) to avoid triangular 47 routing across expensive backbone links, (3) to scale well with the 48 number of multicast groups. We analyse how DCM can be used to route 49 packets to mobile hosts in cellular IP telephony, where each mobile 50 host is assigned a multicast address in every domain it visits. The 51 benefits of multicasting-based approach to route packets to mobile 52 hosts are low latency and no disruption during handover. 54 2. Introduction 56 This document describes a multicast routing protocol called 57 Distributed Core Multicast (DCM). DCM is designed to provide low 58 overhead delivery of multicast data in a large single domain network 59 for a very large number of small groups. This occurs when the number 60 of multicast groups is very large (for example, greater than a 61 million), the number of receivers per multicast group is very small 62 (for example, less than five) and each host is a potential sender to 63 a multicast group. In this document, we present how DCM can be used 64 in cellular IP telephony. Each mobile host is assigned a multicast 65 address in every domain it visits. DCM is then used to route packets 66 to mobile hosts that are distributed within a large Internet domain. 67 MSP-IP (Mobility support using Multicasting in IP)[3] proposes a 68 generic architecture to support host mobility in the Internet by 69 using multicasting as the mechanism to route packets to the mobile 70 hosts. The routing protocol used in this architecture is out of scope 71 of MSP-IP. 73 DCM is an extension of an existing multicast routing protocol that 74 scales better than other existing protocols when applied to support 75 mobile hosts. Recent sparse mode multicast routing protocols, such as 76 the protocol independent multicast (PIM-SM) [2] and the core-based 77 trees (CBT) [1], build a single delivery tree per multicast group 78 that is shared by all senders in the group. This tree is rooted at a 79 single centre router called "core" in CBT, and "rendezvous point" 80 (RP) in PIM-SM. Both centre-based routing protocols have the 81 following potential shortcomings: traffic for the multicast group is 82 concentrated on the links along the shared tree, mainly near the core 83 router; finding an optimal centre for a group is a NP-complete 84 problem and requires the knowledge of the whole network topology [4]. 85 Current approaches typically use either an administrative selection 86 of centres or a simple heuristics [5]. Data distribution through a 87 single centre router could cause non optimal distribution of traffic 88 in the case of a bad positioning of the centre router with respect to 89 senders and receivers. This problem is known as a triangular routing 90 problem. 92 DCM is based on an extension of the centre-based tree approach and is 93 designed for the efficient and scalable delivery of multicast data 94 under the assumptions that are satisfied when multicast is used to 95 support mobile hosts (large number of multicast groups, a few 96 receivers per group and a potentially large number of senders to a 97 multicast group). We consider a network model that consists of 98 several areas connected via the backbone area (see Figure 1). The 99 issues addressed by DCM are: (1): to avoid multicast group state 100 information in backbone routers, (2): to avoid triangular routing 101 across expensive backbone links and (3) to scale well with the number 102 of multicast groups. 104 The benefits of using the multicasting-based approach to route 105 packets to the mobile hosts are low latency and no disruption during 106 handover. When a visiting host arrives into the new domain it is 107 assigned a temporary multicast address that it keeps as long as it 108 stays in the same domain. The base station of the current cell where 109 the mobile lies is responsible for joining the multicast tree on 110 behalf of the mobile. Mobile hosts communicate with base stations 111 over wireless links. Neighbouring base stations that anticipate the 112 arrival of the mobile can initiate its group membership registration. 113 Thus, a multicast group assigned to a mobile host has a few 114 recipients. When the mobile host moves in the new cell, it continues 115 to receive packets without disruption. DCM is particularly well 116 suited to route packets to mobile hosts since the size of its 117 multicast group is small. 119 Mobile IP [6] proposal is intended to support macro-level mobility 120 and relatively slow moving hosts. Mobile IP requires that after each 121 migration of the mobile host its possibly distant home agent is 122 informed about the mobile host's current location. In an environment 123 with highly mobile hosts, Mobile IP is no longer a good solution. The 124 Cellular IP proposal [7] separates local mobility from wide area 125 mobility. It proposes a new mobility management within a Cellular IP 126 network. Cellular IP can interact with Mobile IP to support wide area 127 mobility, that is, mobility between Cellular IP networks. A Cellular 128 IP network consists primarily of base stations that keep distributed 129 data bases with location information referring to a mobile host. Base 130 stations use this information to route packets to the mobile host 131 while it is in a Cellular IP Network. 133 Our approach, DCM, can be used for a new mobility management approach 134 within a large single domain network based on multicasting. DCM is 135 not an alternative to Mobile IP [6] since DCM is not a solution to 136 wide-area mobility. In contrast, DCM can be used as an alternative to 137 Cellular IP within a single domain network. In this document we 138 describe how DCM can be in used in conjunction with the Session 139 Initiation Protocol (SIP)[8] to support terminal mobility in cellular 140 IP Telephony (IPtel). In [9] it is proposed to introduce minor 141 changes in SIP to support terminal mobility in IPtel. We expect a 142 solution based on DCM to be more scalable, in particular in the 143 management of fast or small scale mobility. DCM, when used with SIP, 144 is a scalable solution, able to manage a handover of mobile hosts 145 with minimal disturbance. 147 2.1 Distributed Core Multicast (DCM) Protocol Overview 149 We consider a network model that consists of several areas 151 connected via the backbone area. We introduce an architecture that 152 is based on several core routers per multicast group, called 153 Distributed Core Routers (DCRs). 155 - The DCRs in each area are located at the edge of the backbone. 156 The DCRs act as backbone access points for the data sent by 157 senders inside their area to receivers outside this area. A 158 DCR also forwards the multicast data received from the 159 backbone to receivers in the area it belongs to. When a host 160 wants to join the multicast group M, it sends a join message. 161 This join message is propagated hop-by-hop to the DCR inside 162 its area that serves the multicast group. Conversely, when a 163 sender has data to send to the multicast group, it will send 164 the data encapsulated to the DCR assigned to the multicast 165 group. 166 - The Membership Distribution Protocol (MDP) runs between the 167 DCRs serving the same range of multicast addresses. It is 168 fully distributed. MDP enables the DCRs to learn about other 169 DCRs that have group members. 170 - The distribution of data uses a special mechanism between the 171 DCRs in the backbone area, and the trees rooted at the DCRs 172 towards members of the group in the other areas. We propose a 173 special mechanism for data distribution between the DCRs, 174 which does not require that non-DCR backbone routers perform 175 multicast routing. 177 With the introduction of the DCRs close to any sender and 178 receivers, converging traffic is not sent to a single centre 179 router in the network. Data sent from a sender to a group within 180 the same area is not forwarded to the backbone. Our approach 181 alleviates the triangular routing problem common to all 182 centre-based trees, and unlike PIM-SM, is suitable for groups with 183 many sporadic senders. 185 ++++++++ 186 + + 187 + + 188 + Area D + 189 + + 190 + + 191 + + 192 ++++++++++ +-+----+-+ 193 + Area A + |DCR X4 | 194 + + + ---+----+ ++++++++++ 195 + + + + + + 196 + (3) + + BACKBONE + + + 197 + A2<<----- +------+ + + +--------+ (1) + 198 + |DCR X1|+ <-----+ +--- +| DCR X3 | <<------C1 + 199 + A1 ---->> +------+ + | | + +--------+ + 200 + (1) + + (2)| (2)| + + + 201 + + + | v + + Area C + 202 + + +---+----+ ++++++++++++ 203 +++++++++++ |DCR X2 | 204 +-+---+--+ 205 + ^ + 206 + ^ + 207 + | + 208 + |(1) + 209 + | + 210 + B1 + 211 + + 212 + Area B1 + 213 + + 214 +++++++ 216 Figure 1: Model of a large single domain network and an overview 217 of data distribution with DCM. We show one multicast group M and 218 DCRs X1, X2, X3 and X4 that serve a range to which M belongs to. 219 Step (1): Senders A1, B1 and C1 send data to the corresponding 220 DCRs inside their areas. Step (2): DCRs distribute the multicast 221 data across the backbone area to DCR X1 that needs it. Step (3): 222 X1 sends data to the local receivers in its area (in this example 223 this is A2. 225 2.2 Terminology 227 - DCR. A DCR (Distributed Core Router) is an backbone access 228 point for the data sent to multicast address by senders inside 229 the same area to members outside the area. A DCR also forwards 230 the multicast data received from the backbone to receivers in 231 the area it belongs to. 232 - DCR serves the multicast address m. A DCR is said to serve the 233 multicast address m when it is dynamically elected among all 234 the candidate DCRs in the area to act as an access point for 235 address m (see Section 3.1). 236 - Labelled DCR. A DCR is labelled with the multicast address m 237 if the DCR serves m and there are receivers for m in its area. 238 A labelled DCR is root of a distribution subtree inside its 239 area for m (see Section 3.2). 240 - Source DCR. A source DCR for the multicast group m is the DCR 241 that receives encapsulated multicast data for m by some source 242 inside its area (see Section 3.3). 243 - Range. A range is the partition of the set of multicast 244 addresses into group of addresses. A DCR can serve several 245 ranges of multicast addresses (see Section 3.1). 246 - MDP(Membership Distribution Protocol). MDP is used for the 247 source DCR in one area to learn about labelled DCRs in other 248 areas. MDP is run between DCRs in different areas that serve 249 the same range of multicast addresses (see Section 3.4). 250 - MDP control multicast address. An MDP control multicast 251 address is used for exchanging MDP control messages between 252 DCRs that serve the same range of multicast addresses. There 253 is one MDP control multicast address per range of multicast 254 addresses(see Section 3.4). 255 - STH(Shortest Tunnel Heuristic). STH is used by the source DCR 256 to compute the multicast data distribution tree in the 257 backbone. The edges of this tree are tunnels between DCRs. 258 (see Appendix) 260 3. Distributed Core Multicast (DCM) Protocol Functional Description 262 In this section, we describe the various elements of DCM. Those are: 264 - addressing issues; 265 - how hosts join the multicast group; 266 - how senders send to a multicast group; 267 - how membership information is distributed among DCRs; 268 - how multicast data is distributed among DCRs; 269 - how multicast data is forwarded from DCR to members of the group 270 inside its area. 272 3.1 Addressing Issues 274 In each area there are several routers that are configured to act 275 as candidate DCRs. The identities of the candidate DCRs are known 276 to all routers within an area by means of an intra-area bootstrap 277 protocol [10]. This is similar to PIM-SM with the difference that 278 the bootstrap protocol is constrained within an area. This entails 279 a periodic distribution of the set of reachable candidate DCRs to 280 all routers within an area. 282 Routers use a common hash function to map a multicast group 283 address to one router from the set of candidate DCRs. For a 284 particular group address M, we use the hash function to determine 285 the DCR that serves*M. 287 * A DCR is said to serve the multicast group address M when it 288 is dynamically elected among all the candidate DCRs in the 289 area to act as an access point for address M 291 The used hash function is h(r(M),DCR_i). Function r(M) takes as 292 input a multicast group address and returns the range of the 293 multicast group, while DCR_i is the unicast IP address of the DCR. 294 The target DCR_i is then chosen as the candidate DCR with the 295 highest value of h(r(M),DCR_j)) among all j in {1,...,J} where J 296 is the number of candidate DCRs in an area: 298 h(r(M),DCR_i)=max { h(r(M),DCR_j),j=1,..,J } 300 One possible example of the function that gives the range is: 302 r(M)=M&B, where B is a bit mask. 304 We do not present here the hash function theory. For more 305 information see [11], [10] and [12]. The benefits of using hashing 306 to map a multicast group to DCR are the following: 308 - We achieve minimal disruption of groups when there is change 309 in the candidate DCR set. This means that we have to do a 310 small number of re-mappings of multicast groups when there is 311 a change in the candidate DCR set. See [11] for more 312 explanations. 313 - We apply the hash function h(.,.) as defined by the Highest 314 Random Weight (HRW) [12] algorithm. This function ensures load 315 balancing between candidate DCRs. This is very important, 316 because no single DCR serves more multicast groups than any 317 other DCR inside the same area. We achieve, by this property, 318 that when the number of candidate DCRs increases, the load on 319 each DCR decreases. 321 All routers in all non-backbone areas should apply the same 322 functions h(.,.), r(.). 324 Each candidate DCR is aware of all the ranges of multicast 325 addresses for which it is elected to be a DCR in its area. There 326 is a function m(r(M)) that maps the range of the multicast group 327 address M to another multicast address for control purposes. A DCR 328 joins a control multicast address that corresponds to a range of 329 multicast addresses that it serves. This multicast address is used 330 by DCRs in different areas that serve the same range of multicast 331 addresses to exchange control information. 333 3.2 How hosts join the multicast group 335 When a host is interested in joining the multicast group M, it 336 issues an IGMP[13] join message. A multicast router on its LAN, 337 known as the designated router (DR), receives the IGMP join 338 message. The DR determines the DCR inside its area that serves M, 339 as described in Section 3.1. 341 The process of establishing the group shared tree is like in 342 PIM-SM [2]. The DR sends a JOIN message towards the determined 343 DCR. Sending a JOIN message forces any off-tree routers on the 344 path to the DCR to forward a JOIN message and join the tree. Each 345 router on the way to the DCR keeps a forwarding state for M. When 346 a JOIN message reaches the DCR, this DCR becomes labelled with the 347 multicast group M. In this way, the delivery subtree, for the 348 receivers of the multicast group M in an area, is established. The 349 subtree is maintained by periodically refreshing the state 350 information for M in the routers (like in PIM-SM, this is done by 351 periodically sending JOIN messages). 353 Like in PIM-SM, when the DR discovers that there are no longer any 354 receivers for M, it sends a PRUNE message towards the nearest DCR 355 to disconnect from the shared distribution tree. 357 3.3 How senders send to a multicast group 359 The sending host originates native multicast data, for the 360 multicast group M, that is received by the designated router (DR) 361 on its LAN. The DR determines the DCR within its area that serves 362 M. We call this DCR the source DCR. The DR encapsulates the 363 multicast data packet (IP-in-IP) and sends it with a destination 364 address equal to the address of the source DCR. The source DCR 365 receives the encapsulated multicast data. This is similar to 366 PIM-SM where the DR sends encapsulated multicast data to the RP 367 corresponding to the multicast group. 369 3.4 How membership information is distributed among DCRs 371 The Membership Distribution Protocol (MDP) is used by DCRs in 372 different areas to exchange control information. As is explained 373 in Section 3.1, within each non-backbone area, for each range of 374 multicast addresses there is one DCR serving that range. DCRs in 375 different areas that serve the same range of multicast addresses 376 are members of the same MDP control multicast group. This group is 377 defined by a MDP control multicast address used for exchanging 378 control information. A DCR joins as many MDP control multicast 379 groups as the number of ranges of multicast addresses it serves. 380 There are as many MDP control multicast groups as there are 381 possible ranges of multicast addresses. We do not propose a 382 specific protocol for maintaining the multicast tree for the MDP 383 multicast group. This can be done by means of an existing 384 multicast routing protocol (e.g CBT). 386 DCRs that are members of the same MDP control multicast group 387 exchange the following control information: 389 - periodical keep-alive messages. 391 - unicast distance information. Each DCR sends, to the 392 corresponding MDP control multicast group, information about 393 the unicast distance from itself to other DCRs that it has 394 learned to serve the same range of multicast addresses. This 395 information comes from existing unicast routing tables and it 396 is used for the distribution of multicast data among the DCRs. 398 - multicast group information. A DCR, which is labelled with the 399 multicast group M, informs DCRs in other areas responsible for 400 M that it has receivers for M. In this way, every DCR keeps a 401 record of every other DCR that has at least one member for a 402 multicast address from the range that the DCR serves. A DCR 403 should notify all other DCRs when it becomes labelled with a 404 new multicast group or no longer labelled with a multicast 405 group. 407 MDP uses its MDP control multicast addresses and performs flooding 408 inside the groups defined by those addresses. An alternative 409 approach would be to use MDP servers. This approach leads to a 410 more scalable, but also a more complex solution. This approach is 411 not studied in detail in this document. 413 3.5 How multicast data is distributed among DCRs 415 The multicast data for the group M is distributed from a source 416 DCR to all DCRs that are labelled with M. Since we assume that the 417 number of receivers per multicast group is not large, there are 418 only a few labelled routers per multicast group. Our goal is to 419 perform multicast data distribution in the backbone in such a way 420 that backbone routers keep a minimal state information while at 421 the same time backbone bandwidth is used efficiently. We propose a 422 solution that can be applied in the Internet today. It uses 423 point-to-point tunnels to perform data distribution among DCRs. 424 With this solution, non-DCR backbone routers do not keep any state 425 information related to the distribution of the multicast data in 426 the backbone. 428 Point-to-Point Tunnels 430 The DCR that serves the multicast group M keeps the following 431 information: (1) a set V of DCRs that serve the same range to 432 which M belongs; (2) information about unicast distances 433 between each pair of DCRs from V; (3) the set L of labelled 434 DCRs for M. The DCR obtains this information by exchanging the 435 MDP control messages with DCRs in other areas. In this way, we 436 present the virtual network of DCRs that serve the same range 437 of multicast group addresses by means of an undirected complete 438 graph G=(V,E). V is defined above, while the set of edges E are 439 tunnels between each pair of DCRs in V. Each edge is associated 440 with a cost value that is equal to an inter-DCR unicast 441 distance. 443 The source DCR, called S, calculates the optimal tree that 444 spans the labelled DCRs. In other words, S finds the subtree 445 T=(V_T,E_T) of G that spans the set of nodes L such that 447 cost(T)=sum cost(e) is minimised. 448 e in E_T 450 We recognise this problem as the Steiner tree problem. Instead 451 of finding the exact solution, that is a NP-complete problem, 452 we introduce a simple heuristic called Shortest Tunnel 453 Heuristic (STH). The description of STH is given in the 454 Appendix at the end of this document. 456 ++++++++ 457 + + 458 + Area D + 459 + + 460 + + 461 + + 462 ++++++++++ +-+----+-+ 463 + + |DCR X4 | 464 + + + ---+----+ ++++++++++ 465 + + + | + + + 466 + + + (1)| + + + 467 + +------+ + | + +--------+ + 468 + |DCR X1|+ <-----+ | +---> +| DCR X3 | + 469 + +------+ + (2)| | |(3) + +--------+ + 470 + + + | | | + + + 471 + + + | V | + + Area C + 472 + Area A + +---+----+ ++++++++++++ 473 +++++++++++ |DCR X2 | 474 +-+---+--+ 475 + + 476 At 1: + + 477 +-----+-----+---------+++ + + 478 |sa=X4|da=X2|opt=X1;X3|++ + + 479 +-----+-----+---------+++ + + 480 + Area B + 481 At 2: +++++++++ 482 +-----+-----+++ 483 |sa=X2|da=X1|++ 484 +-----+-----+++ sa: source address 485 At 3: da: destination address 486 +-----+-----+++ opt: end-to-end option 487 |sa=X2|da=X3|++ +++ 488 +-----+-----+++ |++ : encapsulated multicast data packet 489 +++ 491 Figure 2: Figure presents an example of inter-DCR multicast 492 data distribution by using point-to-point tunnels. The source 493 DCR is X4 and labelled DCRs are X1 and X3. X4 calculates the 494 distribution tunnel tree to X1 and X3 by applying the STH 495 heuristic presented in the Appendix. Assume that the result of 496 STH gives the distribution tunnel tree consisting of edges 497 X4-X2, X2-X1 and X2-X3. Then X4 sends the encapsulated 498 multicast data packet to X2. In the end-to-end option field of 499 the packet, a distribution list is contained. X2 sends two 500 copies of multicast data: one to X1 and the other to X3. On 501 this figure are also presented packet formats at various points 502 (points 1, 2 and 3) on the way from X4 to X1 and X3. 504 The source DCR applies STH to determine the distribution tunnel 505 tree from itself to the list of labelled DCRs for the multicast 506 group. The source DCR puts inter-DCR distribution information 507 in the form of an explicit distribution list in the end-to-end 508 option field of the packet header. Under the assumption that 509 there is a small number of receivers per multicast group, the 510 number of labelled DCRs for a group is also small. Thus, an 511 explicit distribution list that completely describes the 512 distribution tunnel tree is not expected to be long. 514 When a DCR receives a packet from another DCR, it reads from 515 the distribution list whether it should make a copy of the 516 multicast data and of the identities of the DCRs where it 517 should send multicast data by tunneling. Labelled DCRs deliver 518 data to local receivers in the corresponding area. An example 519 that shows how multicast data is distributed among DCRs is 520 presented in Figure 2. 522 3.6 How multicast data is forwarded from DCR to members of the group 523 inside its area 525 A DCR receives encapsulated multicast data packets either from a 526 source that is within its area, or from a DCR in another area. A 527 DCR checks if it is labelled with the multicast group that 528 corresponds to the received packet, i.e whether there are members 529 of the multicast group in its area. If this is the case, a DCR 530 forwards the multicast packet along the distribution subtree that 531 is already established for the multicast group (as is described in 532 Section 3.2). 534 4. DCM and cellular IP telephony 536 In this section we present how DCM can be used to route packets to 537 mobile hosts in cellular IP telephony (IPtel). We assume that the 538 Session Initiation Protocol (SIP)[8] is used to establish, modify and 539 terminate IPtel calls. Here we describe how DCM can be used in 540 conjunction with SIP to support terminal mobility. Terminal mobility 541 is the ability to maintain a communication when a host is moving from 542 one location to another during the call. 544 The owner of the mobile host is identified by its SIP URL address. A 545 SIP server in the mobile host's home domain can be identified from 546 this address. When the mobile host moves into the new domain it is 547 assigned a temporary multicast address that it keeps as long as it 548 stays in the same domain. How a multicast address is assigned to a 549 mobile host is out of scope of this document. Then the mobile 550 registers with a SIP server in its home domain in order to be found. 552 During the registration process, the mobile host sends to its home 553 SIP server the anycast address of its current domain and its assigned 554 multicast address. In each domain there are border routers that are 555 configured with the domain anycast address and are responsible for 556 accepting and forwarding packets for the mobile hosts that are in the 557 domain. The domain anycast address is a reserved unicast address. 558 Border routers configured with the anycast address recognise the 559 anycast address as one of their logical interfaces. The routing of 560 packets to the anycast address is done by standard unicast routing 561 mechanisms. 563 A caller that wants to establish a call with the mobile host has the 564 knowledge of the mobile host's SIP URL address. Then, a caller 565 contacts a SIP server in the mobile host's home domain for the mobile 566 host's current location. A SIP server acts in the redirect mode and 567 returns to the caller information about the anycast address of the 568 mobile host's current domain and its assigned multicast address. A 569 caller sends to the mobile host a SIP INVITE message. If the caller 570 is also mobile, it informs the callee about its domain's anycast 571 address and its assigned multicast address. 573 When the sender to the mobile host and the mobile host are in the 574 same domain, packets for the mobile host are destined to the mobile 575 host's multicast address and are routed by DCM. This is done as 576 explained in Section 3. 578 If the sender and the mobile host are in different domains, multicast 579 packets to the mobile host should first reach the domain where the 580 mobile lies. We distinguish two cases to achieve this depending on 581 the used version of the IP protocol. 583 In the case of IPv6, a source sends a packet to the mobile host by 584 using a loose source routing option. A source sets the destination 585 field of the packet header to the multicast address assigned to the 586 mobile host and the IPv6 routing header is set to the mobile host's 587 domain router anycast address. A packet is routed to the nearest 588 border router in the mobile host's domain that is configured with the 589 anycast address. The next address to be visited is the multicast 590 address assigned to the mobile host. DCM is used to route packets 591 from the border router to the mobile host. 593 In the case of IPv4, the sender sends multicast packets for the 594 mobile host encapsulated (IP-in-IP) to the anycast address of the 595 mobile host's current domain. The nearest border router that is 596 configured with the anycast address decapsulates the multicast packet 597 and, as in the case of IPv6, a packet is forwarded to the mobile host 598 by using DCM. 600 As explained in Section 3.1, for the mobile host's assigned multicast 601 address, within each area, there exists a DCR that serves that 602 multicast address. Those DCRs are responsible for forwarding packets 603 to the mobile hosts within a domain. As said before, the DCRs run the 604 MDP control protocol and are members of a MDP control multicast group 605 for exchanging MDP control information. 607 A multicast router in the mobile host's cell initiates a joining the 608 multicast group assigned to the mobile host. Typically this router 609 coexists with the base station in the cell. As described in Section 610 3.2 the JOIN message is propagated to the DCR inside the area that 611 serves the mobile host's multicast address. Then, the DCR sends to 612 the MDP control multicast group a MDP control message when the mobile 613 host is registered. 615 + + + + + + + 616 + + 617 + Area D + 618 + + + + + + + + + + 619 + + + + 620 + + + 621 + + +-+---+-+ 622 Area A + |DCR X4 | 623 + + +---+---+ 624 + + + + + + + + + + 625 + join + + + + + 626 +----------> +-------+ (4) +------+ (3) +------+ + 627 + (1)/ |DCR X1 | <-------------|DCR X3| <---|Sender| + 628 / (2)+--> +-------+ +------+ +------+ + 629 + / / + + + + + 630 +-+-+ join/ + + + + Area C + 631 + |BS1| / + +-------+ + + + + + + 632 +-+-+ +-+-+ + |DCR X2 | 633 + ^ |BS2| + +-+---+-+ 634 _| +---+ + + + 635 + | + + + 636 V + + + 637 + +-+-+ + + Area B + 638 |MH | + + + + + + + 639 + +-+-+ + 640 + + + + + + + 642 Figure 3: The mobile host (MH) is assigned multicast address M. Four 643 DCRs, X1, X2, X3 and X4 serve M. Step (1): Base station BS1 sends a 644 join message for M towards X1. X1 informs X2, X3 and X4 that it has a 645 member for M. Step (2): Advance registration for M in a neighbouring 646 cell is done by BS2. Step(3): The sender sends a packet to multicast 647 group M. Step (4): The packet gets delivered through the backbone to 648 X1. Step (5): X1 receives encapsulated multicast data packet. From X1 649 data is forwarded to BS1 and BS2. MH receives data from BS1. 651 In order to reduce packet latency and losses during a handover, 652 advance registration can be performed. The goal is that when a mobile 653 host moves to a new cell, the base station in the new cell should 654 already started receiving data for the mobile host. The mobile host 655 continues to receive the data without disruption. There are several 656 ways to perform this: 658 - A base station that anticipates the arrival of a mobile host 659 initiates joining the multicast address assigned to the mobile 660 host. This is illustrated in one example in Figure 3. The 661 mechanism by which the base station anticipates the arrival of 662 the mobile host is out of the scope of this document. 664 - In the case where bandwidth is not expensive on the wired 665 network, all neighbouring base stations can start receiving data 666 destined to a mobile host. This guarantees that there would be no 667 latency and packet losses during a handover. 669 A packet for the mobile host reaches all base stations that joined 670 the multicast group assigned to the mobile host. At the same time the 671 mobile host receives data only from a base station in its current 672 cell. A base station that receives a packet on behalf of the mobile 673 host that is not present in its cell can either discard a packet or 674 buffer it for a certain interval of time (e.g. 10ms). Further 675 research is needed to determine what is the best approach. 677 Here we describe in more details how advance registration is 678 performed. At its current cell, the mobile host receives data along 679 the distribution subtree that is established for the mobile host's 680 multicast address. This tree is rooted at the DCR and maintained with 681 periodical sending of join messages. Now, suppose that the base 682 station in the neighbouring cell anticipates arrival of the mobile 683 host. It begins a joining process for the multicast group assigned to 684 the mobile host. This process is terminated when a JOIN message 685 reaches a router that is already on the distribution tree. When the 686 cells are close to each other, joining is terminated at the lowest 687 branching point in the distribution tree. This ensures that the 688 neighbouring base station quickly becomes a part of the multicast 689 distribution tree with low overhead. The neighbouring base station 690 can start joining the multicast group assigned to the mobile host 691 after the mobile host leaves its previous cell. Routers on the 692 distribution tree keep forwarding information for a given time, even 693 if the previous base station stops refreshing the tree because the 694 mobile host leaves its cell. As before, if the base stations are 695 close to each other, the multicast distribution tree for the new base 696 station can be established in a short period of time that makes 697 handover efficient. 699 5. Security Considerations 701 Currently, DCM does not specify any special security measures. As in 702 any routing protocols, however, there are a number of potential 703 security attacks possible. The use of authentication on all packets 704 (i.e. IPSec authentication headers) is recommended to avoid such 705 attacks. 707 6. Open Issues 709 Since DCM is intra-domain routing protocol it is left for future work 710 to examine interoperability of DCM with other inter-domain routing 711 protocols. In this document we do not address the problems of using 712 multicast routing to support end-to-end unicast communication. These 713 problems are related to protocols such as: TCP, ICMP, IGMP, ARP. A 714 simple solution to this problem could be to have a special range of 715 unicast addresses that are routed as multicast addresses. In this 716 way, packets destined to the mobile host are routed by using a 717 multicast mechanism. Conversely, at the end systems, these packets 718 are considered as unicast packets and standard unicast mechanisms are 719 applied. 721 Appendix 723 Shortest Tunnel Heuristic (STH) 725 STH consists of two phases. In the first phase a greedy tree is 726 built by adding one by one the nodes that are closest to the tree 727 under construction, and then removing unnecessary nodes. The 728 second phase is further improving the tree established so far. The 729 definitions of V, G, L and T are given in Section 3.5. STH is as 730 follows: 732 Phase 1: Build a greedy tree 734 - Step 1: Begin with a subtree T of G consisting of the singe 735 node S. k=1. 737 - Step 2: if k=n then goto Step 4. n is the number of nodes in 738 set V. 739 - Step 3: Determine a node z_(k+1) in V, z_(k+1) not in T 740 closest to T (ties are broken arbitrarily). Add the node 741 z_(k+1) to T. k=k+1. Goto Step 2. 742 - Step 4: Remove from T non-labelled DCRs of degree* 1 and 743 degree 2** (one at a time). 745 * Degree of a node in a graph is the number of edges incident 746 with a node 748 ** A node of degree 2 is removed by its two edges being 749 replaced by a single edge (tunnel) connecting the two nodes 750 adjacent to the node being removed. The source DCR is never 751 removed from a graph. 753 Phase 2: Improve a greedy tree 755 STH can be further improved by two additional steps: 757 - Step 5: Determine a minimum spanning tree for the subnetwork 758 of G induced by the nodes in T (after the step 4). 759 - Step 6: Remove from the minimum spanning tree non-labelled 760 DCRs of degree 1 and 2 (one at a time). The resulting tree is 761 the (suboptimal) solution. 763 7. References 765 [1] A. Ballardie. Core Based Trees (CBT) Multicast Routing 766 Architecture. RFC 2201, September 1997. 768 [2] D. Estrin et.all. Protocol Independent Multicast-Sparse Mode 769 (PIM-SM): Protocol Specification. RFC 2117, June 1997. 771 [3] Jayanth Mysore and Vaduvur Bharghavan. A New 772 Multicasting-based Architecture for Internet Host Mobility. In 773 The Third Annual ACM/IEEE International Conference on Mobile 774 Computing and Networking (MobiCom'97). 776 [4] Liming Wei and Deborah Estrin. The Trade-offs of Multicast 777 Trees and Algorithms. In Proc.of the 1994 International 778 Conference on Computer Communications and Networks, San 779 Francisco, CA, USA, September 1994. 781 [5] David G. Thaler and Chinya V. Ravishankar. Distributed 782 Center-Location Algorithms. IEEE JSAC, 15(3), April 1997. 784 [7] Andras G. Valko. Cellular IP: A New Approach to Internet Host 785 Mobility. ACM SIGCOMM Computer Communicastion Review, January 786 1999. 788 [6] C. Perkins. IP Mobility Support, Network Working Group. RFC 789 2002, October 1996. 791 [8] M. Handley and H. Schulzrinne et. all. SIP: Session Initiation 792 Protocol. RFC 2543, 1999. 794 [9] E. Wedlund and H. Schulzrinne. Mobility support using SIP. In 795 Proc. of ACM/IEEE International Conference on Wireless and Mobile 796 Multimedia (WoWMoM'99), Seattle, Washington, August 1999. 798 [10] Deborah Estrin, Mark Handley, Ahmed Helmy, Polly Huang, and 799 David Thaler. A Dynamic Mechanism for Rendezvous-based Multicast 800 Routing. In Proc. of IEEE INFOCOM'99, New York, USA, March 1999. 802 [11] Vinod Valloppillil and Keith W. Ross. Cache Array Routing 803 Protocol v1.0. INTERNET-DRAFT, 1998. 805 [12] D. G. Thaler and C. V. Ravishankar. Using Name-Based Mappings 806 to Increase Hit Rates. IEEE/ACM Transactions on Networking, 807 6(1), February 1998. 809 [13] W. Fenner. Internet Group Management Protocol, Version 2. RFC 810 2236, November 1997. 812 8. Author's address 814 Ljubica Blazevic 815 Jean-Yves Le Boudec 816 Institute for computer Communications and Applications 817 Swiss Federal Institute of Technology (EPFL) 818 CH-1015 Lausanne 819 Switzerland 820 email: Ljubica.Blazevic, leboudec@epfl.ch