idnits 2.17.1 draft-atwood-pim-sm-rp-02.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** Cannot find the required boilerplate sections (Copyright, IPR, etc.) in this document. Expected boilerplate is as follows today (2024-04-24) according to https://trustee.ietf.org/license-info : IETF Trust Legal Provisions of 28-dec-2009, Section 6.a: This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79. IETF Trust Legal Provisions of 28-dec-2009, Section 6.b(i), paragraph 2: Copyright (c) 2024 IETF Trust and the persons identified as the document authors. All rights reserved. IETF Trust Legal Provisions of 28-dec-2009, Section 6.b(i), paragraph 3: This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (https://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- == 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. Miscellaneous warnings: ---------------------------------------------------------------------------- -- 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 27, 2002) is 7972 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) == Missing Reference: '0' is mentioned on line 286, but not defined -- Possible downref: Non-RFC (?) normative reference: ref. '1' -- Possible downref: Normative reference to a draft: ref. '2' ** Obsolete normative reference: RFC 2362 (ref. '3') (Obsoleted by RFC 4601, RFC 5059) == Outdated reference: A later version (-12) exists of draft-ietf-pim-sm-v2-new-05 == Outdated reference: A later version (-12) exists of draft-ietf-pim-sm-bsr-02 -- Possible downref: Non-RFC (?) normative reference: ref. '6' Summary: 4 errors (**), 0 flaws (~~), 4 warnings (==), 5 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 PIM Working Group J. William Atwood 3 Internet-Draft Ritesh Mukherjee 4 Expires: December 27, 2002 Department of Computer Science 5 Concordia University 6 June 27, 2002 8 RP Relocation in PIM-SM Multicast 9 draft-atwood-pim-sm-rp-02.txt 11 Status of this Memo 13 This document is an Internet-Draft and is in full conformance with 14 all provisions in 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 Internet- 19 Drafts. 21 Internet-Drafts are draft documents valid for a maximum of six 22 months and may be updated, replaced, or obsoleted by other documents 23 at any time. It is inappropriate to use Internet-Drafts as 24 reference material or to cite them other than as "work in progress." 26 The list of current Internet-Drafts can be accessed at 27 http://www.ietf.org/ietf/1id-abstracts.txt 28 The list of Internet-Draft Shadow Directories can be accessed at 29 http://www.ietf.org/shadow.html. 31 This Internet-Draft will expire on December 27, 2002. 33 Abstract 35 The Protocol Independent Multicast-Sparse Mode (PIM-SM) protocol 36 uses a core-based tree to forward multicast datagrams to members of 37 a multicast group. Currently there is no method for relocating the 38 core or Rendezvous Point (RP) for a group. Administratively chosen 39 RP's lead to low performance as the sources and receivers in the 40 multicast group join and leave the group. 42 This draft presents a mechanism for dynamically relocating the RP to 43 a position that minimizes the tree cost and improves performance. 45 1. Introduction 47 The current method of choosing the RP for a multicast group is by 48 administratively selecting a position in the network depending upon 49 the expected source and receiver locations. However, with the 50 variety of today's high bandwidth applications being used, it is 51 impossible for an administrator to "guess" where the sources and 52 receivers are most likely to be [1]. 54 To improve network performance, reduce tree costs and reduce delay, 55 it is necessary for the RP to be dependent on the sources and 56 receivers in the multicast group at any point in time. With sources 57 and receivers joining and leaving groups an RP has to be dynamically 58 relocated to maintain network efficiency and reduce delays. This 59 draft is an alternate proposal to the one made by Lin, et. al. [2]. 61 2. Motivation and Objectives 63 Sparse mode PIM (PIM-SM) [3,4] uses a center specific tree 64 construction. The distribution center of PIM-SM is called a 65 Rendezvous Point (RP). PIM tree construction revolves around the 66 selection of the RP. All senders for the group must register with 67 the RP. Receivers requesting to join the group set up the path from 68 themselves to the RP. Thus the location of the RP decides the 69 efficiency of the multicast tree. From the user's point of view, 70 efficiency would mean minimizing end-to-end delay. The network would 71 prefer to minimize the tree cost and be able to reduce congestion. 72 The shared tree routed at the RP does not optimize the delivery path 73 through the network. If the RP is located far from the participants, 74 a longer packet delay is experienced and excessive resources are 75 consumed. If an RP is selected for a set of participants that later 76 changes drastically, the RP location will severely affect the 77 quality of the tree for new participants. 79 In each domain there is an elected BSR (Bootstrap Router) [5], which 80 collects candidate RP information and broadcasts it hop-by-hop to 81 all the routers. Routers that can act as RP's periodically unicast 82 Candidate-RP-advertisement messages (C-RP-Advs) which contain group 83 prefixes for which the candidacy is advertised to the BSR. The BSR 84 then includes a set of these Candidate-RPs (the RP-Set), along with 85 the corresponding group prefixes, in Bootstrap messages it 86 periodically originates. 88 PIM-SM has the ability to switch to source-specific trees for high 89 data rate sources. This increases the number of states to be stored 90 in the router from O(G) to O(S x G) where S is the number of sources 91 and G is the number of multicast groups. With a large number of 92 groups and sources this space requirement can become a limiting 93 factor. Thus dynamic relocation of the RP represents a more 94 attractive solution. For this the following two steps are necessary: 96 1. Determining if a better location exists for the RP for the 97 multicast group. 99 2. Relocating the RP to the new location without losing any data. 101 The entire path from the sender(s) to the receivers has two 102 components: an (inverse) tree from the sources to the RP, and the 103 shared distribution tree from the RP to the receivers. The optimal 104 location for the RP would be influenced by the entire set of 105 participants (senders and receivers). However, in the case of PIM- 106 SM, the set of senders is known to the RP, but the set of receivers 107 is not. Also, given the way PIM-SM operates, it is likely that 108 locating the RP near the "center" of the set of senders will be more 109 useful than being concerned with the entire tree. We will call the 110 set of paths constructed from the senders to the RP the "gathering 111 tree". 113 Finding a better location for the RP resolves into two related 114 problems: deciding which potential sites to consider as candidates, 115 and evaluating the cost of the gathering tree centered on that site. 117 Ideally, we would want the RP to be located in the vicinity of the 118 senders to the multicast group. But there is not enough information 119 to proceed with such a calculation. Another method [2] would be to 120 use the RP-set broadcast by the BSR in the bootstrap message. But 121 this RP-set is too small and unlikely to contain the address of the 122 best RP for the multicast group. An algorithm that considers all the 123 potential routers would be best suited for calculating the best RP. 125 3. New RP Calculation 127 Assume RPold is the current RP of G; we propose an RP relocation 128 mechanism that relocates the RP to RPnew. It should clearly be noted 129 that this relocation is done only when there is a significant 130 improvement in tree cost. The relocation comes into effect after a 131 certain time period and when there are changes in the group 132 membership. 134 To determine the position of RPnew, RPold uses the topology 135 information available to it from the Interior Gateway Protocol (such 136 as OSPF (Open Short Path First), which has the required information 137 in the Link State Database). We begin by describing two functions 138 that will help in deciding if the RP should be moved to a new 139 location or not. [These functions have been taken from [6] with 140 slight modifications. The paper [6] contains other algorithms for 141 calculating the best RP and they may be used instead of the one 142 mentioned here.] 144 1. The function cost_calculate(root) uses the estimation function 145 [6] to calculate the cost of a tree at a given root: 147 Let S be the set of sources for the multicast group, u a 148 source in S, root the supplied root to the algorithm and 149 d(a,b) the distance from a to b. Given the fact that there 150 are no shared links (because the data flow from each sender 151 is independent of the data flow from all other senders), and 152 under the assumption that all sources send with approximately 153 the same rates, the tree cost is the sum of the member 154 distances. Thus, 156 Est. Cost = sum d(root,u) 158 2. The function why_move() follows the following algorithm: 160 1. Initialize a variable i equal to 0 and an array RPmove[] of 161 size 5 equal to NULL. Assign to RPmove[0] the value RPold. 163 2. Call cost_calculate with RPmove[0] as the root. Store the cost 164 in a variable currcost and the visited node in a list 165 dontrepeat[]. 167 3. Call cost_calculate with all of the neighboring unvisited 168 nodes of RPmove[0] as the root. Store the lowest cost in a 169 variable lowestcost, the lowest cost node in a variable RPlow 170 and add the visited nodes to the list dontrepeat[]. 172 4. If lowestcost is lower than currcost then assign lowestcost to 173 currcost else goto step 6. 175 5. Shift all the values of the array RPmove[] to the next 176 location (i.e., assign RPmove[1] := RPmove[0] and so on till 177 RPmove[4] := RPmove[3]). Assign RPmove[0] with the value RPlow 178 and goto step 3. 180 6. If RPmove[0] is different from RPold and the estimated cost of 181 the tree with RP at RPold is greater than lowercost by more 182 than the threshold, then return RPmove[] else make all values 183 of RPmove equal to NULL and return RPmove[]. 185 The value of the variable threshold used in the algorithm is a 186 predefined value set by the network administrator. Thus calling the 187 function why_move() returns RPmove[]. If RPmove[0] is NULL then the 188 RP should not be relocated. If RPmove[0] is not equal to NULL then 189 the RP should be relocated. This leaves us with the problem of 190 dynamically switching from RPold to RPnew[0]. 192 4. RP Relocation 194 Figure 1 shows the outline of the relocation algorithm. When the 195 relocation timer has expired and there is a change in the group 196 membership the present tree cost is calculated. The tree cost with 197 the RP at the best position is calculated. 199 ---------------------------------------------------- 200 RELOCATE(G) 201 set_of_sources S 202 begin 203 while(1) do 204 reloc_var = -1 205 if (tr expired and S changed) 206 RPnew[] = why_move() 207 While (reloc_var != 0) do 208 if (RPnew[0] != NULL) 209 reloc_var = 1 210 gen_move_join(RPold, RPnew[0], G) 211 gen_move_RP(RPold, RPnew[0], G) 212 else 213 reloc_var = 0 214 endif 215 endwhile 216 endif 217 endwhile 218 end 220 tr - relocation timer 221 ---------------------------------------------------- 222 Figure 1: Relocation 224 If RPnew[0] is not NULL then the RP has to be relocated. For this a 225 MOVE_JOIN message is sent to RPnew[0] and Move_RP message is sent to 226 the BSR. The variable reloc_var keeps track of the number of 227 bootstrap messages received with the RP-set for the multicast group 228 unchanged after the relocation has started. 230 RPnew[0] can ignore all the messages if it is not an RP-capable 231 router or is configured not to act as RP for any group. If RPnew[0] 232 is RP-capable then it does the following: 234 On receiving the MOVE_JOIN message RPnew[0] assumes the role of RP 235 for group G. When it receives an encapsulated message from RPold it 236 sends the message out on the multicast tree. When it receives a 237 message from a source it sends the message out on the multicast tree 238 and encapsulates and sends this to RPold. On receiving the Move_RP 239 message if the BSR does not find RPnew[0] in the local pool of 240 candidate RPs it assumes that RPnew[0] is not RP-capable and ignores 241 the message otherwise it does the following: 243 1. To exclude the current members of the RP-set from being the RP 244 for the group, the BSR can do one of the following: 246 i) It changes the priority of RPnew[0] for that group to 247 the minimum value of priority in that group (i.e. 248 maximum priority) and increases the priorities of all 249 other candidates for that group by 1; or 251 ii) It can only include the address of RPnew[0] in the RP- 252 set being broadcast in the bootstrap message and leave 253 out all the remaining candidates. 255 2. The BSR then sends out its bootstrap message. 257 The routers on receiving this bootstrap message join the group at 258 RPnew[0]. While this transition is taking place RPold continues to 259 act as the RP for the group. The MOVE_JOIN message sent to RPnew[0] 260 ensures that RPold receives packets from RPnew[0] during the 261 transition. When RPold receives a message from a source it continues 262 to send to the group and also encapsulates and sends the packet to 263 RPnew[0]. On receiving a bootstrap message RPold checks the 264 reloc_var. If the reloc_var for the group is greater than 0 and the 265 RP-set for the group is unchanged, then it increases the value of 266 reloc_var by 1. 268 Once all the members have pruned off from RPold, the tree to RPold 269 is torn down. RPold then sends a MOVE_OVER message to RPnew[0] and 270 resets the reloc_var to zero. The state is then killed and the tree 271 is now set up at RPnew[0]. On receiving the MOVE_OVER message 272 RPnew[0] stops sending encapsulated messages to RPold. This method 273 of RP relocation ensures no loss of messages during the transition. 275 If RPold gets three bootstrap messages from the BSR with the same 276 RP-set then the value of reloc_var will be four. If the value of 277 reloc_var reaches four then RPold assumes that RPnew[0] is not RP- 278 capable. It then checks the value of RPnew[1]. If RPnew[1] is NULL 279 then it assumes that none of the other nodes can serve as RP for the 280 multicast group so it sets the reloc_var to zero and continues to 281 serve as RP for the multicast group. RPold will also stop sending 282 encapsulated packets to RPnew[0]. If RPnew[1] is not NULL it shifts 283 the value of the array to the previous locations (i.e., RPnew[0] := 284 RPnew[1] and so on until RPnew[3] := RPnew[4] and finally RPnew[4] 285 is assigned NULL). It then tries to relocate to the new value of 286 RPnew[0], that is, the next best position where the RP of the 287 multicast group should be located. 289 5. Control Messages 291 5.1 MOVE_JOIN 293 This message is used to tell RPnew that it should act as the new RP 294 for the multicast group G and should send any messages during the 295 transition period to RPold. The IP address is set to the address of 296 RPold and the destination address is set to RPnew. The IP TTL of the 297 packet is the system's normal unicast TTL. 299 0 1 2 3 300 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 301 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 302 |PIM Ver| Type | Reserved | Checksum | 303 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 304 | Encoded-Multicast-Group-Address | 305 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 307 PIM Ver 308 PIM Version number is 2. 310 Type 311 9 = Move_Join 313 Reserved 314 Set to zero on transmission. Ignored upon receipt. 316 Checksum 317 The checksum is a standard IP checksum. 319 Encoded-Multicast-Group-Address 320 The encoded multicast group address for the group G whose RP 321 has to be relocated. 323 5.2 MOVE_RP 325 This message is used to tell the Bootstrap router that the RP for 326 the group should be shifted from RPold to RPnew. The IP address is 327 set to the address of the RPold and the destination address is set 328 to the address of the BSR. The IP TTL of the packet is the system's 329 normal unicast TTL. 331 0 1 2 3 332 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 333 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 334 |PIM Ver| Type | Reserved | Checksum | 335 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 336 | Encoded-Multicast-Group-Address | 337 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 338 | Encoded-RPnew-Address | 339 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 341 PIM Ver 342 PIM Version number is 2. 344 Type 345 10 = Move_RP 347 Reserved 348 Set to zero on transmission. Ignored upon receipt. 350 Checksum 351 The checksum is a standard IP checksum. 353 Encoded-Multicast-Group-Address 354 The encoded multicast group address for the group G whose RP 355 has to be relocated. 357 Encoded-RPnew-Address 358 The encoded address of the router to which the RP should be 359 relocated. 361 5.3 MOVE_OVER 363 This message is used to tell RPnew that all the members of group G 364 have left the multicast tree at RPold so there is no need to send 365 any more messages to RPold. The IP address is set to the address of 366 RPold and the destination address is set to RPnew. The IP TTL of the 367 packet is the system's normal unicast TTL. 369 0 1 2 3 370 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 371 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 372 |PIM Ver| Type | Reserved | Checksum | 373 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 374 | Encoded-Multicast-Group-Address | 375 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 377 PIM Ver 378 PIM Version number is 2. 380 Type 381 11 = Move_Over 383 Reserved 384 Set to zero on transmission. Ignored upon receipt. 386 Checksum 387 The checksum is a standard IP checksum. 389 Encoded-Multicast-Group-Address 390 The encoded multicast group address for the group G whose RP 391 has to be relocated. 393 6. Summary 395 This draft proposes a dynamic mechanism for relocating RP in the 396 PIM-SM multicast routing protocol. The original RP may not be the 397 ideal RP for the group and this method of relocating to an 398 appropriate position will help reduce delay and improve network 399 performance. 401 7. Security Considerations 403 All the control messages may use IPsec to address security concerns. 405 8. References 407 [1] Robert Voigt, Robert Barton, Shridhar Shukla, "A Tool for 408 configuring Multicast Data Distribution over Global Networks", April 409 1995 411 [2] Ying-Dar Lin, Nai-Bin Hsu, Ren-Hung Hwang, "RP relocation 412 extension to PIM-SM multicast routing", Internet Draft, Work in 413 progress, draft-ydlin-pim-sm-rp-01.txt 415 [3] D. Estrin, D. Farinacci, A. Helmy, D. Thaler, S. Deering, M. 416 Handley, V. Jacobson, C. Liu, P. Sharma, L. Wei, "PIM-SM Protocol 417 Specification", RFC 2362, June 1998 419 [4] Bill Fenner, Mark Handley, Hugh Holbrook, Isidor Kouvelas, 420 "PIM-SM, Protocol Specification", Internet Draft, Work in progress, 421 draft-ietf-pim-sm-v2-new-05.ps 423 [5] Bill Fenner, Mark Handley, David Thaler, "BSR mechanism for 424 PIM-SM", Internet Draft, Work in progress, draft-ietf-pim-sm-bsr- 425 02.ps 427 [6] David G. Thaler, Chinya V. Ravichankar, "Distributed Center 428 Location Algorithms", IEEE Journal of Selected Areas in 429 Communications, April 1997 431 Authors' Addresses 433 J. William Atwood 434 Department of Computer Science 435 1455 de Maisonneuve Blvd. West 436 Montreal, Quebec, H3G 1M8 437 Canada 438 Phone: +1 514 848 3046 439 Email: bill@cs.concordia.ca 440 URL: http://www.cs.concordia.ca/~faculty/bill/ 442 Ritesh Mukherjee 443 Department of Computer Science 444 1455 de Maisonneuve Blvd. West 445 Montreal, Quebec, H3G 1M8 446 Canada 448 Phone: +1 514 989 4530 449 Email: mukherj@cs.concordia.ca 450 URL: http://www.cs.concordia.ca/~grad/mukherj