idnits 2.17.1 draft-komolafe-mpls-te-p2mp-scaling-analysis-04.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- == The page length should not exceed 58 lines per page, but there was 1 longer page, the longest (page 31) being 62 lines == It seems as if not all pages are separated by form feeds - found 0 form feeds but 34 pages Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** There are 2 instances of too long lines in the document, the longest one being 3 characters in excess of 72. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year == Line 1014 has weird spacing: '... sib sibli...' -- Couldn't find a document date in the document -- date freshness check skipped. Checking references for intended status: Informational ---------------------------------------------------------------------------- No issues found here. Summary: 1 error (**), 0 flaws (~~), 4 warnings (==), 1 comment (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 1 Network Working Group O. Komolafe 2 Internet-Draft Cisco Systems 3 Intended Status: Informational A. Farrel 4 Created: August 25, 2010 Old Dog Consulting 5 Expires: February 25, 2011 D. King 6 Old Dog Consulting 8 An Analysis of Scaling Issues for Point-to-Multipoint 9 Label Switched Paths in MPLS-TE Core Networks 11 draft-komolafe-mpls-te-p2mp-scaling-analysis-04.txt 13 Status of this Memo 15 This Internet-Draft is submitted to IETF in full conformance with 16 the provisions of BCP 78 and BCP 79. 18 Internet-Drafts are working documents of the Internet Engineering 19 Task Force (IETF), its areas, and its working groups. Note that 20 other groups may also distribute working documents as Internet- 21 Drafts. 23 Internet-Drafts are draft documents valid for a maximum of six months 24 and may be updated, replaced, or obsoleted by other documents at any 25 time. It is inappropriate to use Internet-Drafts as reference 26 material or to cite them other than as "work in progress." 28 The list of current Internet-Drafts can be accessed at 29 http://www.ietf.org/ietf/1id-abstracts.txt. 31 The list of Internet-Draft Shadow Directories can be accessed at 32 http://www.ietf.org/shadow.html. 34 Abstract 36 Traffic engineered Multiprotocol Label Switching (MPLS-TE) is 37 deployed in providers' core networks, and the scaling properties 38 have been analyzed to show how much control state must be maintained 39 to support a full mesh of edge-to-edge point-to-point (P2P) Label 40 Switched Paths (LSPs) in various network topologies and with several 41 different scaling techniques. 43 Point-to-multipoint (P2MP) MPLS-TE LSPs are very interesting to 44 service providers as a means to provide multicast services (such as 45 TV distribution, or multicast VPN connectivity) across core MPLS 46 networks. P2MP LSPs have different scaling properties than P2P LSPs, 47 and service providers need to understand whether existing protocols 48 and implementations can support the network sizes and service levels 49 that they are planning in their P2MP MPLS-TE networks. 51 This document presents an analysis of the scaling properties MPLS-TE 52 core networks that support P2MP LSPs. 54 Contents 56 1. Introduction ................................................... 3 57 1.1 Overview ...................................................... 3 58 1.2 Definitions and Glossary of Notation .......................... 5 59 1.3. Network Topologies ........................................... 5 60 1.4. Relationship Probabilities ................................... 6 61 2. Issues of Concern for Scaling .................................. 7 62 3. A New Method for Calculations for Point-to-Point LSPs .......... 8 63 3.1. Number of LSPs Traversing a P(1) Node ........................ 8 64 3.2. Number of LSPs Traversing a P(2) Node ....................... 10 65 4. Analysis of a P2MP LSP with Two Destinations .................. 12 66 4.1. Closest Destination is a Sibling of the Source .............. 12 67 4.2. Closest Destination is a First Cousin of the Source ......... 14 68 4.3. Closest Destination is a Second Cousin of the Source ........ 15 69 4.4. The Average Number of State Segments at P(1) and P(2) LSRs .. 16 70 4.5. Generic Formula for Number of State Segments at P(1) and 71 P(2) LSRs ................................................... 19 72 5. Three PEs in Receiving Set of P2MP LSPs ....................... 22 73 6. Any Number of PEs in the Receiving Set of a P2MP LSP .......... 25 74 7. Exemplar Numeric Results ...................................... 27 75 7.1. Impact of Varying Topological Properties of the Network ..... 27 76 7.2. Impact of Varying the Number of PEs in the Receiving Set .... 28 77 8. Conclusions and Open Issues ................................... 30 78 9. Management Considerations ..................................... 31 79 10. Security Considerations ...................................... 31 80 11. Recommendations .............................................. 31 81 12. IANA Considerations .......................................... 31 82 13. Acknowledgements ............................................. 31 83 14. References ................................................... 31 84 14.1. Informative References ..................................... 31 85 15. Authors' Addresses ........................................... 32 86 16. Intellectual Property Consideration .......................... 32 87 17. Disclaimer of Validity ....................................... 33 88 18. Full Copyright Statement ..................................... 33 90 1. Introduction 92 Network operators and service providers are examining scaling issues 93 as they look to deploy ever-larger traffic engineered Multiprotocol 94 Label Switching (MPLS-TE) networks. Concerns have been raised about 95 the number of Label Switched Paths (LSPs) that need to be supported 96 at the edge and at the core of the network. The impact on control 97 plane and management plane resources threatens to outweigh the 98 benefits and popularity of MPLS-TE, while the physical limitations of 99 the routers may constrain the deployment options. These issues and 100 concerns are examined in [RFC5439] for networks carrying point-to- 101 point (P2P) LSPs. 103 Point-to-multipoint (P2MP) MPLS-TE LSPs are very interesting to 104 service providers as a means to provide multicast services (such as 105 TV distribution, or multicast VPN connectivity) across core MPLS 106 networks. The MPLS-TE and Generalized MPLS (GMPLS) signaling 107 ([RFC3209] and [RFC3473]) has been extended to support the control 108 plane establishment of P2MP LSPs [RFC4875]. P2MP LSPs have different 109 scaling properties than P2P LSPs, and service providers need to 110 understand whether existing protocols and implementations can support 111 the network sizes and service levels that they are planning in their 112 P2MP MPLS-TE networks. 114 This document presents an analysis of the scaling properties MPLS-TE 115 core networks that support P2MP LSPs. 117 1.1 Overview 119 Point-to-multipoint LSPs can be considered as a set of point-to-point 120 fragments that are joined together to form a tree. The tree is rooted 121 at the source, and has a number of leaves (destinations). Each P2P 122 fragment runs between the source and a branch, between a pair of 123 branches, or between a branch and a leaf (in the extreme case, a 124 fragment may also run directly between the root and a branch). 126 The scaling benefit of a P2MP LSP comes in the fact that only one 127 copy of the data for a set of leaves downstream of a particular 128 branch is transmitted to that branch. This means that only one set of 129 resources (for example, buffers) is consumed on the path upstream of 130 the branch, leaving room for other LSPs to traverse the same path. 132 In the control plane there are savings, too. At each branch node, it 133 is necessary to hold only one piece of upstream control plane state, 134 and one piece of state for each downstream fragment. This compares 135 with the P2P equivalent where it would be necessary to hold as much 136 upstream state as downstream state. 138 Note that this is a slight simplification. P2MP control plane state 139 must identify all downstream leaves and may contain certain leaf- 140 specific information such as the paths to those leaves), and this 141 information must be present in the upstream control plane state. 142 Nevertheless, the reduction in quantity of state information is 143 significant, and the effort required within the protocol 144 implementation to maintain the state information is reduced exactly 145 as described. 147 Thus, in order to quantify the scaling properties of P2MP LSPs in a 148 network, we count control plane state per interface. That is, at any 149 given node on the path of a P2MP tree we count the number of the 150 node's interfaces that participate in the LSP. At the source, this is 151 always one. At a branch node it is (1 + n) where there is just one 152 upstream interface and n downstream interfaces. At a leaf we consider 153 just one upstream interface. (Note that the special case of a bud 154 node [RFC4875] that is a leaf but that also has downstream neighbors 155 in the LSP is not considered in this document. This is a feature of 156 the snowflake topology that is used as the model as described in 157 Section 1.3.) 159 The approach adopted in this document is to derive some formulae 160 based on the probabilistic measure of where a node lies in the 161 network, and what role it plays in the P2MP LSP. Furthermore, in 162 order to simplify the equations that are derived, certain 163 approximations are introduced - although these are believed to 164 diminish in significance as the size of the network grows. This 165 method is verified by applying it to P2P LSPs and comparing the 166 results with those algorithms derived in [RFC5439]. As described 167 in Section 8, although this mechanism seems to deliver reasonable 168 results and agrees with the P2P formulae of [RFC5439], the 169 mathematical model needs further validation. Similarly, it would be 170 valuable to attempt to quantify the approximations in the model. 172 This document is designed to help service providers discover whether 173 existing protocols and implementations can support the network sizes 174 that they are planning. To do this, it presents an analysis of some 175 of the scaling concerns for MPLS-TE core networks, and examines the 176 value of two techniques for improving scaling. This should motivate 177 the development of appropriate deployment techniques and protocol 178 extensions to enable the application of MPLS-TE in large networks. 180 This version of this document is limited to the analysis of P2MP LSPs 181 in the artificially symmetric snowflake network, and the comparison 182 of the results with those for P2P LSPs. The document does not address 183 any scaling techniques such as hierarchical LSPs [RFC4206] (whether 184 P2P or P2MP), nor does it look at protection mechanisms such as Fast 185 Re-route (FRR) [RFC4090]. These features and their applicability to 186 other generic network topologies are for future study. 188 1.2 Definitions and Glossary of Notation 190 This document applies consistent notation to define various 191 parameters of the networks that are analyzed. These terms are defined 192 as they are introduced though-out the document, but are grouped 193 together here for quick reference. Refer to the full definitions in 194 the text for detailed explanations. 196 Where possible, these terms are kept consistent with those used in 197 [RFC5439]. 199 n A network level. n = 1 is the core of the network. 200 P(n) A node at level n in the network. 201 S(n) The number of nodes at level n, i.e., the number of P(n) nodes. 202 L(n) The number of LSPs traversing a P(n) node. 203 X(n) The number of LSP segment states maintained by a P(n) node, 204 i.e., X(n) = 2*L(n) for P2P LSPs. 205 x(n) A single LSP segment state maintained by a P(n) node; i.e., 206 X(n) = SUM[x(n)] 207 M(n) The number of P(n+1) nodes subtended to a P(n) node. 208 N The number of destination PEs for each P2MP LSP; i.e. the size 209 of the receiving set is N. 211 Sibling nodes: PEs subtended to the same P(n). 213 First cousin nodes: PEs subtended to the same P(n-1) but different 214 P(n). 216 Second cousin nodes: PEs attached to different P(n-1) nodes. 218 C(init): The cost in terms of x(n) of setting up a P2MP LSP from a 219 source to the closest PE in the receiving set. 221 C(inc): The incremental cost in terms of x(n) of having a subsequent 222 PE in the receiving set. 224 1.3. Network Topologies 226 At this stage, analysis is limited to the snowflake topology defined 227 in [RFC5439]. In this type of network, only the very core of the 228 network is meshed. The edges of the network are formed as trees 229 rooted in the core. 231 Thus, the snowflake topology is based on a hierarchy of connectivity 232 within the core network. PEs are not directly interconnected, but 233 have connectivity to exactly one P(n) (dual homing is not considered 234 at this stage). Each P(n) is connected to precisely one P(n-1) and to 235 no other P(n) node. There is one exception: the P(1) nodes are 236 assumed to be connected in a full mesh. Figure 1 shows an example 237 snowflake topology. 239 PEa PE PE PE PEc PE PE PE PE PE 240 \ | \ | / \ | / | / 241 \| \|/ \|/ |/ 242 PEb--P(2) P(2) P(2) P(2)--PE 243 \ | | / 244 PE \ | | / PE 245 \ \| |/ / 246 PE-P(2)---P(1)-----P(1)---P(2)-PE 247 / |\ /| \ 248 PE | \ / | PE 249 | \/ | 250 | /\ | 251 PE | / \ | PE 252 \ |/ \| / 253 PE-P(2)---P(1)-----P(1)---P(2)-PE 254 / /| |\ \ 255 PE / | | \ PE 256 / | | \ 257 PE--P(2) P(2) P(2) P(2)--PE 258 /| /|\ /|\ |\ 259 / | / | \ / | \ | \ 260 PE PE PE PE PE PE PE PE PE PEd 262 Figure 1 : A Snowflake Network 264 In Figure 1, the PEs marked PEa and PEb are siblings (subtended to 265 the same P(n) - n=2 in this network). The PEs marked PEa and PEc are 266 first cousins (subtended to the same P(n-1) but to different P(n)s). 267 The PEs marked PEa and PEd are second cousins (subtended to different 268 P(n-1) nodes). 270 Throughout this document, a snowflake network with 3 levels (i.e., 271 there are P(1), P(2) and PE Label Switching Routers (LSRs)) is 272 considered. However, the methodology employed may be easily applied 273 to networks with a greater number of levels. 275 1.4. Relationship Probabilities 277 In a snowflake network with 3 levels, consider a given PE: there are 278 a total of S(1)*M(1)*M(2) - 1 other PEs, of which M(2) - 1 are 279 siblings. Hence, the probability of another PE chosen at random being 280 a sibling is: 282 Prob(sibling) = (M(2) - 1) / (S(1)*M(1)*M(2) - 1) 284 Similarly: 286 Prob(first cousin) = (M(2)*(M(1) - 1)) / (S(1)*M(1)*M(2) - 1) 288 And: 290 Prob(second cousin) = M(1)*M(2)*(S(1) - 1) / (S(1)*M(1)*M(2) - 1) 292 2. Issues of Concern for Scaling 294 Issues of concern for scaling are discussed in detail in [RFC5439] 295 and translate to P2MP LSPs. The issues directly affect the number of 296 LSPs that an LSR can support, and therefore may limit the number of 297 LSPs and hence customer services that can be supported by a network. 299 The issues may be summarized as follows. 301 - LSP State 303 LSP state is the data (information) that must be stored at an LSR 304 in order to maintain an LSP. This is mainly information used by the 305 control plane protocols and grows in direct proportion to the 306 number of LSPs. Since the memory capacity of an LSR is limited, 307 there is a related limit placed on the number LSPs that can be 308 supported. 310 - Processing Overhead 312 The number of LSPs passing through an LSR may impact the processing 313 speed for each LSP. For example, control block search times can 314 increase with the number of control blocks to be searched. Thus, 315 since CPU power is constrained in any LSR, there may be a practical 316 limit to the number of LSPs that can be supported. 318 - RSVP-TE Implications 320 RSVP-TE is a soft-state protocol which means that protocol messages 321 (refresh messages) must be regularly exchanged between signaling 322 neighbors in order to maintain the state for each LSP that runs 323 between the neighbors. Observations of existing implementations 324 indicate that there may be a threshold of around 50,000 P2P LSPs 325 above which an LSR struggles to achieve sufficient processing to 326 maintain LSP state. No observational figures are available for P2MP 327 LSPs, but similar behavior may be expected. Various techniques 328 including refresh reduction [RFC2961], increasing the refresh 329 interval, use of the RSVP-TE Hello message [RFC3209], and the use 330 of GMPLS extensions [RFC3473] (such as the use of [RFC2961] message 331 acknowledgements on all messages) can improve the situation 332 markedly. 334 - Management 336 Another practical concern for the scalability of large MPLS-TE 337 networks is the ability to manage the network. This may be 338 constrained by the available tools, the practicality of managing 339 large numbers of LSPs, and the management protocols in use. 341 All of these consideration limit the number of LSPs supported within 342 the network and at any particular LSR. 344 3. A New Method for Calculations for Point-to-Point LSPs 346 3.1. Number of LSPs Traversing a P(1) Node 348 To calculate the number of LSPs seen by each P(1) LSR, consider the 349 case when each PE establishes a single P2P LSP to a destination PE 350 chosen at random. Zero, one, or two P(1) LSRs will be traversed 351 depending on whether the destination is a sibling, first cousin, or 352 second cousin respectively. Hence it may be said that each P(1) LSR 353 traversed will either be: 355 - an ingress P(1) LSR: such a node is the only P(1) LSR traversed if 356 the destination is a first cousin and the first P(1) LSR traversed 357 if the destination is a second cousin. Hence, each P1 LSR will be 358 an ingress P(1) LSR for each of the M(1)*M(2) subtended PEs that 359 establishes an LSP destined for a PE that is not a sibling, the 360 probability of which is 1 - Prob(sibling). 362 or 364 - an egress P(1) LSR: such a node is the second P(1) LSR traversed as 365 a result of the destination being a second cousin. Essentially, an 366 egress P(1) LSR handles the LSPs destined for subtended PEs 367 originating from second cousin PEs. There is a total of 368 M(1)*M(2)*(S(1) - 1) source PEs which are second cousin nodes to 369 the subtended PEs and the possibility of each of these establishing 370 an LSP to one of the subtended PEs is 371 Prob(second cousin) / (S(1) - 1). 373 Figure 2 illustrates examples of ingress P(1) and egress P(1) nodes. 374 The figure shows three exemplar LSPs from a common source to three 375 distinct destinations (d, d1, and d2). d is a sibling of the source, 376 d1 is a first cousin of the source, and d2 is a second cousin of the 377 source. In these LSPs there is one ingress P(1) (marked as iP(1)) and 378 one egress P(1) (marked as eP(1)). 380 PE d PE PE PE PE PE PE PE PE 381 \ | \ | / \ | / | / 382 \| \|/ \|/ |/ 383 Source--P(2) P(2) P(2) P(2)--PE 384 \ | | / 385 PE \ | | / PE 386 \ \| |/ / 387 PE-P(2)---iP(1)---eP(1)---P(2)-PE 388 / |\ /| \ 389 d1 | \ / | d2 390 | \/ | 391 | /\ | 393 Figure 2 : Illustration of Ingress and Egress P(1) Nodes 395 Table 1 summarizes the probability of each P(1) LSR being an ingress 396 P(1) or an egress P(1), and shows the frequency with which it may 397 fulfill that role. 399 Role | Prob(role) | Frequency 400 | | 401 -------------+--------------------------------+---------------------- 402 | | 403 Ingress P(1) | 1 - Prob(sibling) | M(1)*M(2) 404 | | 405 -------------+--------------------------------+---------------------- 406 | | 407 Egress P(1) | Prob(second cousin)/(S(1) - 1) | M(1)*M(2)*(S(1) - 1)) 408 | | 410 Table 1 : Probability and Frequency of Fulfilling a P(1) Role 412 Each P(1) LSR will be both an ingress and egress LSR depending on the 413 relative location of the source and destination PEs. Therefore, l(1), 414 the number of LSPs seen by a P(1) LSR if every PE were to establish 415 an LSP to a randomly selected PE is: 417 l(1) = M(1)*M(2)*(1 - Prob(sibling)) + 418 M(1)*M(2)*(S(1) - 1) * Prob(second cousin)/(S(1) - 1) 419 = M(1)*M(2)*(1 - Prob(sibling)) + 420 M(1)*M(2) * Prob(second cousin) 421 = M(1)*M(2) * (1 - ( (M(2) - 1) / (S(1)*M(1)*M(2) - 1) + 422 M(1)*M(2) * (M(1)*M(2)*(S(1) - 1) / (S(1)*M(1)*M(2) - 1)) 423 = M(1)*M(2) * 424 (2*S(1)*M(1)*M(2) - M(2) - M(1)*M(2)) / (S(1)*M(1)*M(2) - 1) 425 = M(1)*M(2) * (2*S(PE) - M(2) - M(1)*M(2)) / (S(PE) - 1) 427 Lastly, l(1) is obtained when each PE establishes a single LSP to a 428 randomly chosen destination. L(1) refers to when LSPs are established 429 to S(PE) - 1 destinations and so: 431 L(1) = M(1)*M(2)*(2*S(PE) - M(2) - M(1)*M(2)) 433 This result is consistent with the result shown in section 5.1 of 434 [RFC5439]. 436 3.2. Number of LSPs Traversing a P(2) Node 438 Again, assuming each source PE establishes a single P2P LSP to a 439 randomly chosen destination PE, the manner in which the P(2) LSRs 440 will be traversed by LSPs is described below, illustrated in 441 Figure 3, and summarized in Table 2. 443 - An ingress P2 LSR is traversed when one of the subtended PEs 444 establishes an LSP. There are M2 subtended PEs and the probability 445 of each PE establishing an LSP that traverses the given P(2) node 446 is 1. 448 - A first cousin egress P(2) LSR handles the LSP whenever it is 449 established by one of the first cousin PEs and destined for one of 450 the subtended PEs. There are M(2)*(M(1) - 1) first cousins and the 451 probability of each of these establishing an LSP to a PE subtended 452 to any given P(2) node is Prob(first cousin) / (M(1) - 1). 454 - A second cousin egress P(2) LSR handles the LSP whenever it is 455 established by one of the second cousin PEs and destined for one of 456 the subtended PEs. The number of the former is M(1)*M(2)*(S(1) - 1) 457 and the probability of the latter is 458 Prob(second cousin) / M(1)*(S(1) - 1). 460 Figure 3 shows examples of ingress and egress P(2) nodes. There are 461 three exemplar LSPs from a single source to three destinations (d, 462 d1, and d2). d is a sibling of the source, d1 is a first cousin 463 of the source, and d2 is a second cousin of the source. The ingress 464 P(2) node is marked iP(2). There are two egress P(2) nodes; one is a 465 first cousin egress P(2) (marked e1P(2) on the figure), and one is a 466 second cousin egress P(2) (marked e2P(2)). 468 PE d PE PE PE PE PE PE PE PE 469 \ | \ | / \ | / | / 470 \| \|/ \|/ |/ 471 Source--iP(2) P(2) P(2) P(2)--PE 472 \ | | / 473 PE \ | | / PE 474 \ \| |/ / 475 PE-e1P(2)--P(1)-----P(1)---e2P(2)-PE 476 / |\ /| \ 477 d1 | \ / | d2 478 | \/ | 479 | /\ | 481 Figure 3 : Example of Ingress and Egress P(2) Nodes 483 Role | Prob(role) | Frequency 484 | | 485 --------------+-------------------------------+---------------------- 486 | | 487 Ingress P(2) | 1 | M(2) 488 | | 489 --------------+-------------------------------+---------------------- 490 | | 491 Egress first | Prob(first cousin)/(M(1) - 1) | M(2)*(M(1) - 1)) 492 cousin P(2) | | 493 | | 494 --------------+-------------------------------+---------------------- 495 | | 496 Egress second | Prob(second cousin) / | M(1)*M(2)*(S(1) - 1)) 497 cousin P(2) | (M(1)*(S(1) - 1)) | 498 | | 500 Table 2 : Probability and Frequency of Fulfilling a P(2) Role 502 Therefore, l(2), the number of LSPs seen by a P(2) LSR if every PE 503 were to establish an LSP to a randomly selected PE is: 505 l(2) = M(2) + M(2)(M(1) - 1)*(Prob(first cousin) / (M(1) - 1) ) + 506 M(1)*M(2)(S(1) - 1)*(Prob(second cousin)/(M(1)*(S(1) - 1)) ) 507 = M(2) + M(2)*Prob(first cousin) + M(2)*Prob(second cousin) 508 = ( M(2) / (S(1)*M(1)*M(2) - 1) ) * 509 ( S(1)*M(1)*M(2) - 1 + M(1)*M(2) - M(2) + 510 S(1)*M(1)*M(2) - M(1)*M(2) ) 511 = (M(2) / (S(1)*M(1)*M(2) - 1)) * (2*S(1)*M(1)*M(2) - M(2) - 1) 512 = M(2) * (2*S(PE) - M(2) - 1) / (S(PE) - 1) 514 Therefore: 516 L(2) = M(2) * (2*S(PE) - M(2) - 1) 518 This result is also consistent with the conclusion reached in section 519 5.1 of [RFC5439]. We can, therefore, assume that this approach is 520 viable P2P MPLS-TE LSPs. The next sections extend this approach to 521 P2MP LSPs. 523 4. Analysis of a P2MP LSP with Two Destinations 525 Consider a P2MP LSP with a set of receiving nodes (destinations) 526 called d1 and d2. If we count the number of hops from the source to 527 each destination, we are able to designate d1 as the closer to the 528 source, and d2 as being equidistant or further from the source. 530 According to our definitions, d1 must be a sibling, a first cousin, 531 or a second cousin of the source. We consider these three 532 possibilities in turn. 534 4.1. Closest Destination is a Sibling of the Source 536 The probability that d1 is a sibling of the source is 538 Prob(sibling) = (M(2) - 1) / (S(1)*M(1)*M(2) - 1) 540 The cost associated with this possibility is that each P(2) LSR holds 541 two state segments (one corresponding to the input interface and one 542 for the output interface), giving C(init) = 2*x(2). 544 The incremental cost of reaching d2, C(inc), is dependent on its 545 relative location to d1. As shown in Figure 4, there are three 546 distinct possibilities: 548 - d2 is a sibling of d1 (and so also a sibling of the source) 550 Excluding the source and d1, there is a total of 551 S(1)*M(1)*M(2) - 2 PEs of which M(2) - 2 are siblings of d1 and the 552 source. Thus, for d2 the probability of being a sibling is: 554 Prob(sibling) = (M(2) - 2) / (S(1)*M(1)*M(2) - 2) 556 Replication must occur at the P(2) LSR for the P2MP LSP to reach d2 557 and so the incremental cost is an extra state segment at the P(2) 558 LSR, thus C(inc) = x(2). 560 - d2 is a first cousin of d1 (and the source) 562 The probability that d2 is a first cousin of the source is 564 Prob(first cousin) = (M(2)*(M(1) - 1)) / (S(1)*M(1)*M(2) - 2) 566 Replication occurs at the first P(2) LSR, giving an extra state 567 segment there, x(2). Since d2 is a first cousin, only a single P(1) 568 is traversed, requiring that LSR to support two state segments, 569 yielding 2*x(1). Lastly, the P(2) LSR to which d2 is attached must 570 be traversed by the LSP, leading to that LSR supporting two state 571 segments, giving 2*x(1). Aggregating, we arrive at: 573 C(inc) = x(2) + 2*x(1) + 2*x(2) 575 - d2 is a second cousin of d1 (and the source) 577 The probability that d2 is a second cousin of the source is 579 Prob(second cousin) = (M(1)*M(2)*(S(1) - 1)) / (S(1)*M(1)*M(2) - 2) 581 The only difference with the previous scenario is that d2 being a 582 second cousin requires the LSP to traverse an extra P(1) LSR, 583 giving C(inc) = x(2) +2*x(1) +2*x(1) + 2*x(2) 585 In Figure 4 we show a source and the nearest destination, d1. d1 is a 586 sibling of the source. Three possible locations for d2 are 587 considered: d2a is a sibling of d1 (and of the source), d2b is a 588 first cousin of d1 (and of the source), d2c is a second cousin of d1 589 (and of the source). 591 d1 d2a PE PE PE PE PE PE PE PE 592 \ | \ | / \ | / | / 593 \| \|/ \|/ |/ 594 Source--P(2) P(2) P(2) P(2)--PE 595 \ | | / 596 PE \ | | / PE 597 \ \| |/ / 598 PE-e1P(2)--P(1)-----P(1)---e2P(2)-PE 599 / |\ /| \ 600 d2b | \ / | d2c 601 | \/ | 602 | /\ | 604 Figure 4 : d1 is a Sibling of the Source, Yielding Three 605 Possibilities for the Location of d2 607 4.2. Closest Destination is a First Cousin of the Source 609 The probability that d1 is a first cousin of the source is: 611 Prob(first cousin) = M(2)*(M(1) - 1) / (S(1)*M(1)*M(2) - 1) 613 The associated initial cost is: 615 C(init) = 2*x(2) + 2*x(1) + 2*x(2). 617 Given the requirement that d1 is equidistant or closer to the source 618 than d2, d2 cannot be a sibling of the source. This leaves the 619 following possibilities, also illustrated in Figure 5: 621 - d2 is a sibling of d1 (and a first cousin of the source) 623 Prob(sibling) = (M(2) - 1) / (S(1)*M(1)*M(2) - 2) 625 C(inc) = x(2) 627 - d2 is a first cousin of d1 (and of the source) 629 Prob(first cousin) = M(2)*(M(1) - 2) / (S(1)*M(1)*M(2) - 2) 631 C(inc) = x(1) + 2*x(2) 633 - d2 is a second cousin of d1 (and of the source) 635 Prob(second cousin) = M(1)*M(2)*(S(1) - 1) / (S(1)*M(1)*M(2) - 2) 637 C(inc) = x(1) + 2*x(1) + 2*x(2) 639 In Figure 5 we show a source and the nearest destination, d1. d1 is a 640 first cousin of the source. Three possible locations for d2 are 641 considered: d2a is a sibling of d1, d2b is a first cousin of d1, d2c 642 is a second cousin of d1. 644 PE PE PE PE d2b PE PE PE PE PE 645 \ | \ | / \ | / | / 646 \| \|/ \|/ |/ 647 Source--P(2) P(2) P(2) P(2)--PE 648 \ | | / 649 PE \ | | / PE 650 \ \| |/ / 651 d1-e1P(2)--P(1)-----P(1)---e2P(2)-PE 652 / |\ /| \ 653 d2a | \ / | d2c 654 | \/ | 655 | /\ | 657 Figure 5 : d1 is a First Cousin of the Source, Yielding Three 658 Possibilities for the Location of d2 660 4.3. Closest Destination is a Second Cousin of the Source 662 The probability that d1 is a second cousin of the source is: 664 Prob(second cousin) = M(1)*M(2)*(S(1) - 1) / (S(1)*M(1)*M(2) - 1) 666 The associated initial cost is: 668 C(init) = 2*x(2) + 2*x(1) + 2*x(1) + 2*x(2) 670 Given the requirement that d1 is equidistant or closer to the source 671 than d2, d2 cannot be a sibling or a first cousin of the source. This 672 leaves the following possibilities, also illustrated in Figure 6: 674 - d2 is a sibling of d1 (and a second cousin of the source) 676 Prob(sibling) = (M(2) - 1) / (S(1)*M(1)*M(2) - 2) 678 C(inc) = x(2) 680 - d2 is a first cousin of d1 (and a second cousin of the source) 682 Prob(first cousin) = M(2)*(M(1) - 1) / (S(1)*M(1)*M(2) - 2) 684 C(inc) = x(1) + 2*x(2) 686 - d2 is a second cousin of d1 (and of the source) 688 Prob(second cousin) = M(1)*M(2)*(S(1) - 2) / (S(1)*M(1)*M(2) - 2) 690 C(inc) = x(1) + 2*x(1) + 2*x(2) 692 In Figure 6 we show a source and the nearest destination, d1. d1 is a 693 second cousin of the source. Three possible locations for d2 are 694 considered: d2a is a sibling of d1, d2b is a first cousin of d1, d2c 695 is a second cousin of d1. 697 PE PE PE PE PE PE PE d2b PE PE 698 \ | \ | / \ | / | / 699 \| \|/ \|/ |/ 700 Source--P(2) P(2) P(2) P(2)--PE 701 \ | | / 702 PE \ | | / d2a 703 \ \| |/ / 704 PE-P(2)---P(1)-----P(1)---P(2)-PE 705 / |\ /| \ 706 PE | \ / | d1 707 | \/ | 708 | /\ | 709 PE | / \ | PE 710 \ |/ \| / 711 PE-P(2)---P(1)-----P(1)---P(2)-PE 712 / /| |\ \ 713 PE / | | \ PE 714 / | | \ 715 PE--P(2) P(2) P(2) P(2)--PE 716 /| /|\ /|\ |\ 717 / | / | \ / | \ | \ 718 d2c PE PE PE PE PE PE PE PE PE 720 Figure 6 : d1 is a Second Cousin of the Source, Yielding Three 721 Possibilities for the Location of d2 723 4.4. The Average Number of State Segments at P(1) and P(2) LSRs 725 Having discussed the nine different permutations of establishing a 726 P2MP LSP from a given PE to two destination PEs in a three-level 727 snowflake topology, the next step is to explore the scalability of 728 this configuration by computing the number of LSP state segments that 729 must be handled by the P(1) and P(2) LSRs. To compute this value, the 730 cost associated with each permutation, obtained by summing C(inc) and 731 C(init) appropriately, has to be weighted by the corresponding 732 probability and the overall cost aggregated. Table 3 gives the nine 733 permutations, the associated costs in terms of state segments that 734 must be managed at P(1) and P(2) nodes and the exact and approximate 735 probabilities of the particular LSP being established. 737 In Table 3, the following three probabilities must be recalled: 739 Prob(sibling) = (M(2) - 1) / (S(1)*M(1)*M(2) - 1) 741 Prob(first cousin) = M(2)*(M(1) - 1) / (S(1)*M(1)*M(2) - 1) 743 Prob(second cousin) = M(1)*M(2)*(S(1) - 1) / (S(1)*M(1)*M(2) - 1) 745 For the sake of fitting the table on the page, the equations for the 746 exact probabilities for d2 positions are numbered I through VI and 747 are listed after the table. 749 d1 | d2 |LSR state 750 -------------------------+--------------------------------+ segments 751 Position | Exact | Position |Exact|Approx |----+---- 752 wrt src |probability |wrt d1 |prob |probability |P(1)|P(2) 753 ---------+---------------+----------+-----+---------------+----+---- 754 sibling |Prob(sibling) |Sibling | I |Prob(sibling) | 0 | 3 755 sibling |Prob(sibling) |1st cousin| II |Prob(1stcousin)| 2 | 5 756 sibling |Prob(sibling) |2nd cousin| III |Prob(2ndcousin)| 4 | 5 757 1stcousin|Prob(1stcousin)|Sibling | IV |Prob(sibling) | 2 | 5 758 1stcousin|Prob(1stcousin)|1st cousin| V |Prob(1stcousin)| 3 | 6 759 1stcousin|Prob(1stcousin)|2nd cousin| III |Prob(2ndcousin)| 5 | 6 760 2ndcousin|Prob(2ndcousin)|Sibling | IV |Prob(sibling) | 4 | 5 761 2ndcousin|Prob(2ndcousin)|1st cousin| II |Prob(1stcousin)| 5 | 6 762 2ndcousin|Prob(2ndcousin)|2nd cousin| VI |Prob(2ndcousin)| 7 | 6 764 Equations: 765 I (M(2) - 2) / (S(1)*M(1)*M(2) - 2) 766 II M(2)*(M(1) - 1) / (S(1)*M(1)*M(2) - 2) 767 III M(1)*M(2)*(S(1) - 1) / (S(1)*M(1)*M(2) - 2) 768 IV (M(2) - 1) / (S(1)*M(1)*M(2) - 2) 769 V M(2)*(M(1)-2) / (S(1)*M(1)*M(2) - 2) 770 VI M(1)*M(2)*(S(1) - 2) / (S(1)*M(1)M(2) - 2) 772 Table 3 : Summary of Probabilities and Cost of 773 Establishing P2MP LSP To Two PEs 775 The approximate probabilities essentially assume the probabilities of 776 d2 being in a certain location are independent of the location of d1, 777 which is evidently not the case. However, such an approximation is 778 attractive as it simplifies the equations significantly (a fact more 779 important as the size of the receiving set grows). Furthermore, 780 comparing the approximate and exact probabilities suggest that the 781 approximate probabilities are not unreasonable, and actually would be 782 expected to be close the exact probabilities for large networks 783 (i.e., large values of M(1), M(2), and S(1) should reduce the 784 discrepancy). 786 Therefore, approximate probabilities are used in the remainder of 787 this document. In consequence, the total approximate number of state 788 segments at P(1) and P(2) LSRs, X(1) and X(2) respectively, may be 789 calculated as follows: 791 X1 = 2*Prob(sibling)*Prob(first cousin) + 792 4*Prob(sibling)*Prob(second cousin) + 793 2*Prob(first cousin)*Prob(sibling) + 794 3*Prob(first cousin)**2 + 795 5*Prob(first cousin)*Prob(second cousin) + 796 4*Prob(second cousin)*Prob(sibling) + 797 5*Prob(second cousin)*Prob(first cousin) + 798 7*Prob(second cousin)**2 800 = 4*Prob(sibling)*Prob(first cousin) + 801 8*Prob(sibling)*Prob(second cousin) + 802 3*Prob(first cousin)**2 + 803 10*Prob(first cousin)*Prob(second cousin) + 804 7*Prob(second cousin)**2 806 X2 = 3*Prob(sibling)**2 + 807 5*Prob(sibling)*Prob(first cousin) + 808 5*Prob(sibling)*Prob(second cousin) + 809 5*Prob(first cousin)*Prob(sibling) + 810 6*Prob(first cousin)**2 + 811 6*Prob(first cousin)*P(second cousin) + 812 5*Prob(second cousin)*Prob(sibling) + 813 6*Prob(second cousin)*P(first cousin) + 814 6*Prob(second cousin)**2 816 = 3*Prob(sibling)**2 + 817 10*Prob(sibling)*Prob(first cousin) + 818 10*Prob(sibling)*Prob(second cousin) + 819 6*Prob(first cousin)**2 + 820 12*Prob(first cousin)*Prob(second cousin) + 821 6*Prob(second cousin)**2 823 These two equations give the number of state segments that must be 824 handled by the P(1) and P(2) LSRs respectively if a source sets up a 825 P2MP LSP to any 2 PEs. The values for Prob(sibling), 826 Prob(first cousin), and Prob(second cousin) from Section 1.4 may be 827 substituted into the equations allowing X(1) and X(2) to be expressed 828 in terms of the topological properties of the network. Furthermore, 829 the two equations for X(1) and X(2) correspond to the establishment 830 of a single P2MP LSP, and so the equations must be appropriately 831 scaled to handle more than one P2MP LSP. For example, the results 832 should be multiplied by S(PE) to reflect every PE establishing an 833 LSP. 835 Lastly, the equations for X(1) and X(2) give the total number of 836 state segments handled by all P(1) and P(2) LSRs in the network and 837 so must be divided by the number of each type of LSR to obtain the 838 average values. Intuitively, the symmetry in the snowflake network 839 suggests that there will be little variance around the average value 840 provided each PE establishes an equal number of LSPs and the 841 destinations are chosen from an identical statistical distribution. 843 4.5. Generic Formula for Number of State Segments at P(1) and P(2) LSRs 845 Let D be the set of possible locations for a given destination in a 846 P2MP LSP and so: 848 D = {sibling, first cousin, second cousin} 850 Let D1 and D2 be members of D. Using the patterns which may be 851 observed in Table 3, generic formulae for X(1) and X(2) may be 852 computed. 854 X1 = SUM [ SUM [Prob(d1 = D1)*Prob(d2 = D2)*(fa(D1) + fb(D1, D2))] ] 855 D1 D2 857 where 859 fa(D1) = 0 if D1 is sibling 860 2 if D1 is first cousin 861 4 if D1 is second cousin 863 fb(D1, D2) = 0 if D2 is sibling 864 1 if D1 is not sibling AND D2 is first cousin 865 2 if D1 is sibling AND D2 is first cousin 866 3 if D1 is not sibling AND D2 is second cousin 867 4 if D1 is sibling AND D2 is second cousin 869 This equation for X(1) basically says that to compute the number of 870 state segments at the P(1) LSR, iterate over all possible relative 871 locations for the PEs in the receiving set and, for each permutation, 872 calculate the product of the probability of that permutation 873 occurring (i.e., Prob(d1 = D1)*P(d2 = D2)) and the associated cost 874 (i.e., (fa(D1)+fb(D1, D2)). Summing the products over all the 875 permutations give the desired metric. 877 fa(D1) describes the number of state segments that must be handled by 878 P(1) LSRs due to the location of the first PE in the receiving set, 879 d1. No state segments are handled by any P(1) LSR if d1 is a sibling 880 of the source. In this case, the LSP does not need to traverse any 881 P(1) LSR to reach d1, but rather reaches it via the P(2) LSR to which 882 d1 and the source are both attached. If d1 is a first cousin of the 883 source, the LSP reaches it via the P(1) LSRs to which they are both 884 subtended and so two state segments must be handled by the P(1) LSR. 885 Four state segments are handled by P(1) LSRs when d1 is a second 886 cousin of the source due to the requirement for the LSP to traverse 887 two P(1) LSRs. 889 fb(D1, D2) describes the incremental cost associated with any 890 replication necessary for the P2MP LSP to reach the second PE in the 891 receiving set, d2. If d2 is a sibling of d1, then no state segments 892 need be handled by any of the P(1) LSRs. On the other hand, if d2 is 893 a first cousin of d1, then one or two additional state segments must 894 be handled by the P(1) LSRs, depending on whether or not d1 is a 895 sibling of the source. If d1 is a sibling, then replication must 896 occur at the first P(2) LSP and, since the LSP is destined for a 897 first cousin, only a single P(1) LSR is traversed and so two state 898 segments must be supported by the P(1) LSRs. When d1 is not a 899 sibling, then it is either a first or second cousin of the source and 900 so replication must occur at the first or second P(1) LSR 901 respectively, with an additional state segment being necessary at 902 that P(1) LSRs to reach d2. Lastly, if d2 is a second cousin of d1 903 and d1 is a sibling of the source, replication occurs at the first 904 P(2) LSP and, since two P(1) LSRs must be traversed to reach a second 905 cousin, four state segments must be handled by P(1) LSRs. If d2 is a 906 second cousin of d1, and d1 is not a sibling of the source, 907 replication occurs at the first P(1) LSR and, since the LSP must 908 traverse a second P(1) LSR, gives a total of three state segments. 910 Similarly, for the number of state segments handled by the P(2) LSRs: 912 X(2) = SUM [ SUM [ Prob(d1=D1)*Prob(d2=D2)*(fc(D1) + fd(D1, D2))]] 913 D1 D2 915 where 917 fc(D1) = 2 if D1 is sibling 918 4 otherwise 920 fd(D1, D2) = 1 if D2 is sibling 921 2 if D1 is not sibling AND D2 is not sibling 922 3 if D1 is sibling AND D2 is not sibling 924 fc(D1) simply states that the first PE in the receiving set, d1, 925 requires two state segments to be supported at P(2) LSRs when it is a 926 sibling of the source, and four states when it is not; two at each of 927 the two P(2) LSR that must be traversed in this case. 929 According to fd(D1, D2), when the second PE in the receiving set, d2, 930 is a sibling of d1 it results in a single additional state segment 931 being supported at the P(2) LSR, due to the replication that must 932 occur there. If d1 is neither a sibling of the source nor d2, then 933 replication must occur at a P(1) LSR and so reaching d2 adds two 934 extra state segments at P(2) LSRs, corresponding to traversing the 935 second P(2) LSR. If d1 is a sibling of the source but d2 is not, then 936 replication occurs at the first P(2) LSR and, given the requirement 937 to traverse a second P(2) LSR, produces a total of three state 938 segments being supported by the P(2) LSRs. 940 These two equations for X(1) and X(2) may be readily expanded to 941 obtain the results given in Section 4.4 and have the advantage of 942 being more easily adaptable as the size of the receiving set 943 increases, an advantage exploited in the remainder of this document. 945 Furthermore, these two equations may be adapted to consider the cost 946 of establishing a P2P LSP, and so used to validate the equations 947 against the results set out in [RFC5439]. For a P2P LSP, there is no 948 d2, thus it may be said that: 950 X(1:p2p) = 2*Prob(first cousin) + 4*Prob(second cousin) 952 This gives the total mean number of state segments at all the P(1) 953 LSRs when a single P2P LSP is established. The values for 954 Prob(first cousin) and Prob(second cousin) from Section 1.4 may be 955 substituted into the equation. To obtain the result matching Section 956 3.1 and [RFC5439], we must multiply by S(PE) - 1 (since each source 957 establishes an LSP to every other PE), multiply by S(PE) (since there 958 are S(PE) sources), divide by 2 (since the number of state segments 959 is twice the number of LSPs seen by the LSR for P2P LSPs), and divide 960 by S(1) (since there are S(1) P(1) LSRs). This looks as follows: 962 L1 = S(PE)*(S(PE)-1) * 963 (2*Prob(first cousin) + 4*Prob(second cousin)) / 2*S(1) 964 = S(PE)*(S(PE) - 1) * 965 (2*M(2)(M(1) - 1) / (S(1)*M(1)*M(2) - 1) + 966 4*M(1)*M(2)*(S(1) - 1) / (S(1)*M(1)*M(2) - 1) ) / 2*S(1) 967 = 2*S(1)*M(1)*M(2)*(S(1)*M(1)*M(2) - 1) * 968 (M(2)*(M(1) - 1) + 2*M(1)*M(2)*(S(1) - 1)) / 969 2*S(1)*(S(1)*M(1)*M(2) - 1) 970 = M(1)*M(2)*(2*S(PE) - M(2) - M(1)*M(2)) 972 Similarly: 974 X(2:p2p) = 2*Prob(sibling) + 4*(1 - Prob(sibling)) 975 = 2*(2 - Prob(sibling)) 977 This gives the total mean number of state segments at all P(2) LSRs 978 when a single P2P LSP is established. This result should be 979 multiplied by S(PE) - 1 (since each source establishes an LSP to 980 every other PE), multiplied by S(PE) (since there are S(PE) sources), 981 divided by 2 (since the number of state segments is twice the number 982 of LSPs seen by the LSR for P2P LSPs), and divided by S(1)*M(1) 983 (since there are S1M1 P2 LSRs) to give the same result as found in 984 Section 3.1 and [RFC5439]. This is achieved as follows: 986 L2 = S(PE)*(S(PE) - 1)* 987 2*(2 - Prob(sibling)) / 2*S(1)*M(1) 988 = S(PE)*(S(PE) - 1)* 989 2*(2 - (M(2) - 1)/(S(1)*M(1)*M(2) - 1)) / 2*S(1)*M(1) 990 = 2*S(1)*M(1)*M(2)*(S(1)*M(1)*M(2) - 1) * 991 (2*(S(1)*M(1)*M(2) - 1) - M(2) + 1) / 992 2*S(1)*M(1)*(S(1)*M(1)*M(2) - 1) 993 = M(2)*(2*S(PE) - M(2) - 1) 995 5. Three PEs in Receiving Set of P2MP LSPs 997 The three nodes in the receiving set are d1, d2, and d3. Once again, 998 d1 is the closest to the source, followed by d2, and lastly d3. Table 999 4 summarizes all the different ways the P2MP LSP may be established 1000 and the respective number of state segments that must be supported by 1001 P(1) and P(2) LSRs. 1003 In reading Table 4, recall that: 1005 Prob(sibling) = (M(2) - 1) / (S(1)*M(1)*M(2) - 1) 1007 Prob(first cousin) = M(2)*(M(1) - 1) / (S(1)*M(1)*M(2) - 1) 1009 P(second cousin) = M(1)*M(2)*(S(1) - 1) / (S(1)*M(1)*M(2) - 1) 1011 In order to fit this table on the page, it is necessary to adopt some 1012 additional notation conventions as follows. 1014 sib sibling 1015 1c first cousin 1016 2c second cousin 1017 p(x) Prob(x) 1019 Additionally, the equations for exact probabilities are represented 1020 by the roman numerals I-XV and are listed separately. 1022 d1 | d2 | d3 |LSR state 1023 -----------+------------------+-------------------+ segments 1024 Psn |Exact |Psn |Exact|Approx |Psn |Exact |Approx |----+---- 1025 wrt |prob |wrt |prob |prob |wrt |prob |prob |P(1)|P(2) 1026 src | |d1 | | |d2 | | | | 1027 ----+------+----+-----+-------+----+------+-------+----+---- 1028 sib |p(sib)|sib | I |p(sib) |sib | VII |p(sib) | 0 | 4 1029 sib |p(sib)|sib | I |p(sib) |1c | VIII |p(1c) | 2 | 6 1030 sib |p(sib)|sib | I |p(sib) |2c | IX |p(2c) | 4 | 6 1031 sib |p(sib)|1c | II |p(1c) |sib | XI |p(sib) | 2 | 6 1032 sib |p(sib)|1c | II |p(1c) |1c | X |p(1c) | 3 | 7 1033 sib |p(sib)|1c | II |p(1c) |2c | IX |p(2c) | 5 | 7 1034 sib |p(sib)|2c | III |p(2c) |sib | XI |p(sib) | 4 | 6 1035 sib |p(sib)|2c | III |p(2c) |1c | VIII |p(1c) | 5 | 7 1036 sib |p(sib)|2c | III |p(2c) |2c | XII |p(2c) | 7 | 7 1037 1c |p(1c) |sib | IV |p(sib) |sib | XIII |p(sib) | 2 | 5 1038 1c |p(1c) |sib | IV |p(sib) |1c | X |p(1c) | 3 | 7 1039 1c |p(1c) |sib | IV |p(sib) |2c | IX |p(2c) | 5 | 7 1040 1c |p(1c) |1c | V |p(1c) |sib | XI |p(sib) | 3 | 7 1041 1c |p(1c) |1c | V |p(1c) |1c | XIV |p(1c) | 4 | 8 1042 1c |p(1c) |1c | V |p(1c) |2c | IX |p(2c) | 6 | 8 1043 1c |p(1c) |2c | III |p(2c) |sib | XI |p(sib) | 5 | 7 1044 1c |p(1c) |2c | III |p(2c) |1c | VIII |p(1c) | 6 | 8 1045 1c |p(1c) |2c | III |p(2c) |2c | XII |p(2c) | 8 | 8 1046 2c |p(2c) |sib | IV |p(sib) |sib | XIII |p(sib) | 4 | 6 1047 2c |p(2c) |sib | IV |p(sib) |1c | X |p(1c) | 5 | 7 1048 2c |p(2c) |sib | IV |p(sib) |2c | XII |p(2c) | 7 | 7 1049 2c |p(2c) |1c | II |p(1c) |sib | XI |p(sib) | 5 | 7 1050 2c |p(2c) |1c | II |p(1c) |1c | X |p(1c) | 6 | 8 1051 2c |p(2c) |1c | II |p(1c) |2c | XII |p(2c) | 8 | 8 1052 2c |p(2c) |2c | VI |p(2c) |sib | XI |p(sib) | 7 | 7 1053 2c |p(2c) |2c | VI |p(2c) |1c | VIII |p(1c) | 8 | 8 1054 2c |p(2c) |2c | VI |p(2c) |2c | XV |p(2c) | 10 | 8 1056 Table 4 : Summary of Probabilities and Cost of Establishing 1057 a P2MP LSP to Three PEs 1059 Equations: 1060 I (M(2) - 2) / (S(1)*M(1)*M(2) - 2) 1061 II M(2)*(M(1) - 1) / (S(1)*M(1)*M(2) - 2) 1062 III M(1)*M(2)*(S(1) - 1) / (S(1)*M(1)*M(2) - 2) 1063 IV (M(2) - 1) / (S(1)*M(1)*M(2) - 2) 1064 V M(2)*(M(1) - 2) / (S(1)*M(1)*M(2) - 2) 1065 VI M(1)*M(2)*(S(1) - 2) / (S(1)*M(1)*M(2) - 2) 1066 VII (M(2) - 3) / (S(1)*M(1)*M(2) - 3) 1067 VIII M(2)*(M(1) - 1) / (S(1)*M(1)*M(2) - 3) 1068 IX M(1)*M(2)*(S(1) - 1) / (S(1)*M(1)*M(2) - 3) 1069 X M(2)*(M(1) - 2) / (S(1)*M(1)*M(2) - 3) 1070 XI (M(2) - 1) / (S(1)*M(1)*M(2) - 3) 1071 XII M(1)*M(2)*(S(1) - 2) / (S(1)*M(1)*M(2) - 3) 1072 XIII (M(2) - 2) / (S(1)*M(1)*M(2) - 3) 1073 XIV M(2)*(M(1) - 3) / (S(1)*M(1)*M(2) - 2) 1074 XV M(1)*M(2)*(S(1) - 3) / (S(1)*M(1)*M(2) - 3) 1076 Using a similar approach to that used in Section 4.5, the approximate 1077 number of state segments that must be handled by P(1) and P(2) LSRs 1078 may be readily computed. 1080 Again, Let D be the set of possible locations for a given destination 1081 in a P2MP LSP and so 1083 D = {sibling, first cousin, second cousin} 1085 Using the patterns which may be observed in Table 4, generic formula 1086 for X(1) and X(2) may be computed as follows. 1088 X(1) = SUM [ 1089 D1 1090 SUM [ 1091 D2 1092 SUM [ Prob(d1=D1)*Prob(d2=D2)*Prob(d3=D3) * 1093 D3 (fe(D1) + ff(D1, D2) + fg(D1, D2, D3))]]] 1095 where 1097 fe(D1) = 0 if D1 is sibling 1098 2 if D1 is a first cousin 1099 4 if D1 is a second cousin 1101 ff(D1, D2) = 0 if D2 is sibling 1102 1 if D1 is not a sibling AND D2 is a first cousin 1103 2 if D1 is a sibling AND D2 is a first cousin 1104 3 if D1 is not a sibling AND D2 is a second cousin 1105 4 if D1 is a sibling AND D2 is a second cousin 1107 fg(D1, D2, D3) = 0 if D3 is sibling 1108 1 if (D1 OR D2 is not sibling) AND 1109 D3 is first cousin 1110 2 if D1 is sibling AND 1111 D2 is sibling AND 1112 D3 is first cousin 1113 3 if (D1 is not sibling OR D2 is not sibling) AND 1114 D3 is second cousin 1115 4 if D1 is sibling AND 1116 D2 is sibling AND 1117 D3 is a second cousin 1119 Similarly, for the number of state segments handled by the P(2) LSRs: 1121 X(2) = SUM [ 1122 D1 1123 SUM [ 1124 D2 1125 SUM [ Prob(d=D1) * Prob(d2=D2) * Prob(d3=D3) * 1126 D3 (fh(D1) + fi(D1, D2) + fj(D1, D2, D3)) ]]] 1128 where 1130 fh(D1) = 2 if D1 is sibling 1131 4 otherwise 1133 fi(D1, D2) = 1 if D2 is sibling 1134 2 if D1 is not sibling AND D2 is not sibling 1135 3 if D1 is sibling AND D2 is not sibling 1137 fj(D1, D2, D3) = 1 if D3 is sibling 1138 2 if (D1 is not sibling OR D2 is not sibling) AND 1139 D3 is not sibling 1140 3 if D1 is sibling AND 1141 D2 is sibling AND 1142 D3 is not sibling 1144 It can be readily seen that there are similarities between the 1145 equations here and those for X(1) and X(2) in Section 4.5. The main 1146 difference is that, in the former equations, when considering the 1147 incremental cost of reaching the third PE in the receiving set, d3, 1148 the relative position of all the previous PEs in the receiving set 1149 must be taken into consideration. These similarities will be 1150 exploited to allow generic equations for the mean number of state 1151 segments that must be supported at P(1) and P(2) LSRs as a function 1152 of the receiving set size in Section 6. 1154 6. Any Number of PEs in the Receiving Set of a P2MP LSP 1156 Sections 4 and 5 have shown the scalability parameters for a single 1157 P2MP LSP from a source PE to two and three PEs, respectively. It did 1158 this by estimating the average number of state segments that must be 1159 maintained by P(1) and P(2) LSRs. This section extends these findings 1160 by considering the case where there are an arbitrary number of PEs, 1161 N, which are receivers for the LSP. 1163 Comparing our two equations for X(1) (Sections 4.5 and 5) we can 1164 deduce a generic equation about the mean number of state segments 1165 that must be supported at the P(1) LSR when there are N PEs in the 1166 receiving set for the P2MP LSP: 1168 X(1) = SUM [ ... SUM [ Prob(d1=D1)*...*Prob(dN=DN)* 1169 D1 DN (fa(D1)+fb(D1,D2)+...+fb(D1,...,DN))]...] 1171 where 1173 fa(D1) = 0 if D1 is sibling 1174 2 if D1 is first cousin 1175 4 if D1 is second cousin 1177 fb(D1,D2,...Dj) = 0 if Dj is sibling 1178 1 if any of D1, D2 ... Dj-1 is not sibling AND 1179 Dj is first cousin 1180 2 if all of D1, D2 ... Dj-1 are sibling AND 1181 Dj is first cousin 1182 3 if any of D1, D2 ... Dj-1 is not sibling AND 1183 Dj is second cousin 1184 4 if all of D1, D2 ... Dj-1 are sibling AND 1185 Dj is second cousin 1187 Similarly, for the number of state segments handled by the P2 LSRs, 1189 X(2) = SUM [ ... SUM [ Prob(d1=D1)*...*Prob(dN=DN)* 1190 D1 DN (fc(D1)+fd(D1,D2)+...+fd(D1,...,DN))]...] 1192 where 1194 fc(D1) = 2 if d1 is sibling 1195 4 otherwise 1197 fd(D1,D2,...Dj) = 1 if Dj is sibling 1198 2 if any of D1, D2 ... Dj-1 is not sibling AND 1199 Dj is not sibling 1200 3 if all of D1, D2 ... Dj-1 are sibling AND 1201 Dj is not sibling 1203 These two equations for X(1) and X(2) give the values of the 1204 approximate mean number of state segments that must be supported by 1205 P(1) and P(2) LSRs when a P2MP LSP is set up from a single source to 1206 N destination PEa. These equations are used to obtain exemplar 1207 numerical results in Section 7. 1209 7. Exemplar Numeric Results 1211 7.1. Impact of Varying Topological Properties of the Network 1213 We can substitute the probabilities that a given PE is a sibling, 1214 first cousin, or second cousin (given by the equations in Section 1215 1.4) into the equations in Section 6 so that the number of state 1216 segments that must be supported by P(1) and P(2) LSRs, X(1) and X(2), 1217 can be computed as functions of the topological properties of the 1218 snowflake topology, M1, M2, and S1. This allows the impact of varying 1219 these topology parameters on the scalability to be investigated. 1221 A simple snowflake topology with M1, M2, and S1 all initially equal 1222 to 4 was considered. A P2MP LSP from every PE to 3 other randomly 1223 chosen PEs was established. Each one of M1, M2, and S1 was 1224 individually varied from 4 to 20 (with the other two parameters kept 1225 equal to 4) to allow the impact of varying each of these parameters 1226 individually to be shown in isolation. Table 5 shows the results. 1228 M(1) | M(2) | S(1) | X(1) | X(2) 1229 -----+------+------+-----------+-------------- 1230 4 | 4 | 4 | 134.855 | 31.428125 1231 4 | 4 | 6 | 143.326 | 31.62091667 1232 4 | 4 | 8 | 147.527 | 31.7165625 1233 4 | 4 | 10 | 150.038 | 31.7735 1234 4 | 4 | 12 | 151.707 | 31.81145833 1235 4 | 4 | 14 | 152.897 | 31.83857143 1236 4 | 4 | 16 | 153.788 | 31.85875 1237 4 | 4 | 18 | 154.481 | 31.87458333 1238 4 | 4 | 20 | 155.034 | 31.887125 1239 4 | 4 | 4 | 134.855 | 31.428125 1240 4 | 6 | 4 | 201.344 | 47.05175 1241 4 | 8 | 4 | 267.837 | 62.675625 1242 4 | 10 | 4 | 334.332 | 78.3 1243 4 | 12 | 4 | 400.829 | 93.924375 1244 4 | 14 | 4 | 467.325 | 109.54875 1245 4 | 16 | 4 | 533.822 | 125.173125 1246 4 | 18 | 4 | 600.32 | 140.7975 1247 4 | 20 | 4 | 666.817 | 156.421875 1248 4 | 4 | 4 | 134.855 | 31.428125 1249 6 | 4 | 4 | 202.862 | 31.62091667 1250 8 | 4 | 4 | 270.866 | 31.7165625 1251 10 | 4 | 4 | 338.868 | 31.7735 1252 12 | 4 | 4 | 406.869 | 31.81145833 1253 14 | 4 | 4 | 474.87 | 31.83857143 1254 16 | 4 | 4 | 542.87 | 31.85875 1255 18 | 4 | 4 | 610.871 | 31.87458333 1256 20 | 4 | 4 | 678.871 | 31.887125 1258 Table 5 : Impact of Varying Topological Properties of a Network 1260 Table 5 shows that, typically, a greater number of average state 1261 segments must be supported by P(1) LSRs than P2 LSRs. This finding is 1262 unsurprising given that the topology of the snowflake network means 1263 it would be expected that a greater number of LSPs are concentrated 1264 in the core. 1266 It may be seen from Table 5 that increasing M(1) or M(2) leads to a 1267 linear increase in the number of state segments that must be handled 1268 at P(1) LSRs. This observation may be explained by realizing that 1269 increasing M(1) or M(2) (equivalently) increases the number of PEs 1270 subtended to each P(1) LSR and so more LSPs will be expected to be 1271 handled by this LSR. In contrast, increasing S1 increases the number 1272 of P1 LSRs but since the number of PEs subtended to each P(1) LSR 1273 remains unchanged (since M(1) and M(2) are unvaried in this case), 1274 the mean number of state segments remain relatively constant. 1276 Varying either M(1) or S(1) does not alter the number of PEs 1277 subtended to each P(2) LSR and so the mean number of state segments 1278 that must be handled by P(2) LSRs remains relatively unchanged. In 1279 contrast, increasing M(2) directly increases the number of PEs 1280 attached to each P(2) LSR and thus increases the number of state 1281 segments that such LSRs must handle accordingly. 1283 7.2. Impact of Varying the Number of PEs in the Receiving Set 1285 The impact of varying the size of receiving set, N, when the 1286 topological properties of the network are kept constant is considered 1287 in this section. A simple snowflake topology in which M(1), M(2), and 1288 S(1) are all equal to 12, and in which N is varied from 1 to 10 is 1289 considered. Table 6 records the number of state segments that must be 1290 handled at P(1) and P(2) LSRs when the P2MP LSP is set up. 1292 For comparison, Table 6 also presents the results of establishing a 1293 corresponding set of P2P LSPs, allowing any benefits obtained by 1294 using P2MP LSPs instead of P2P to be quantified. The cost of 1295 establishing N P2P LSPs to the PEs in the receiving set was 1296 calculated by multiplying the cost of establishing a P2P LSP given 1297 in the equations for P2P LSPs in Section 4.5 by S(PE) * N since there 1298 are SPE sources of N P2P LSPs. 1300 Table 6 shows that, again, there is are more LSPs handled by P(1) 1301 LSRs than P(2) LSRs. Also, as would be expected, increasing the size 1302 of the receiving set increases the amount of state that must be 1303 supported by LSRs. 1305 Number of PEs | P2P X(1) | P2P X(2) | P2MP X(1) | P2MP X(2) 1306 --------------+----------+--------------+-----------+-------------- 1307 1 | 550.318 | 47.84715278 | 550.318 | 47.84715278 1308 2 | 1100.636 | 95.69430556 | 958.465 | 71.84652778 1309 3 | 1650.954 | 143.5414583 | 1365.71 | 95.77083333 1310 4 | 2201.272 | 191.3886111 | 1772.94 | 119.6944444 1311 5 | 2751.59 | 239.2357639 | 2180.18 | 143.6180556 1312 6 | 3301.908 | 287.0829167 | 2587.41 | 167.5416667 1313 7 | 3852.226 | 334.9300695 | 2994.65 | 191.4652778 1314 8 | 4402.544 | 382.7772222 | 3401.89 | 215.3881944 1315 9 | 4952.862 | 430.624375 | 3809.12 | 239.3118056 1316 10 | 5503.18 | 478.4715278 | 4216.36 | 263.2354167 1318 Table 6 : Impact of Varying the Number of PEs in the Receiving Set 1319 When P2P or P2MP LSPs are Used 1321 Using P2MP LSPs leads to LSRs having to support less state than if 1322 P2P LSPs are used. The relative reduction in the amount of state that 1323 must be supported by LSRs when P2MP LSPs instead of P2P LSPs are used 1324 is illustrated in Table 7. It can be seen that the relative reduction 1325 obtained by using P2MP LSPs initially rises with the size of the 1326 receiving set, before levelling off at around 24% and 45% for P(1) and 1327 P(2) LSRs respectively. It is perhaps surprising that using multicast 1328 does not achieve greater performance improvement; this finding may be 1329 explained by realizing that the approximations made in assuming the 1330 position of a subsequent PE in a receiving set is independent of the 1331 position of the preceding PEs means that the P2MP results presented 1332 here are close to the worst-case results. Basically, in a topology 1333 with M(1) = M(2) = S(1) = 12, Prob(second cousin) = 92% and so the 1334 worst-case P2MP LSPs in which all the destinations are second cousins 1335 (and so there are N replications at the first P1 LSR) is 1336 statistically the most likely scenario. Consequently, using multicast 1337 reduces the state predominantly only on the path from the PE to the 1338 first P(1) LSR, via the first P(2) LSR. On the other hand, had 1339 positions of preceding PEs in the receiving set been taken into 1340 consideration, the possibility of a given PE being a second cousin 1341 will diminish with the number of PEs in the receiving set which are 1342 already second cousins and so the probability of establishing the 1343 worst-case P2MP LSP will be lower. 1345 Number of PEs | Percentage Reduction Using P2MP LSPs 1346 | Compared to P2P LSPs 1347 | 1348 | X(1) | X(2) 1349 --------------+-------------------+-------------------- 1350 1 | 0 | 4.64442E-09 1351 2 | 12.91716789 | 24.92079089 1352 3 | 17.2775256 | 33.28001928 1353 4 | 19.45838588 | 37.45999632 1354 5 | 20.76653862 | 39.96798254 1355 6 | 21.6389433 | 41.63997336 1356 7 | 22.26182991 | 42.83425251 1357 8 | 22.72899487 | 43.7301433 1358 9 | 23.0925473 | 44.42678598 1359 10 | 23.38320753 | 44.98410012 1361 Table 7 : Reduction in the Number of State Segments at LSRs Obtained 1362 by Establishing P2MP LSPs Instead of P2P LSPs 1364 8. Conclusions and Open Issues 1366 A framework for investigating the scalability of P2MP MPLS-TE 1367 deployments by estimating the amount of state that must be handled by 1368 different types of LSRs in a snowflake network has been developed. 1369 The approach works by exhaustively aggregating the sum of the product 1370 of the cost and probabilities of all the different P2MP LSPs 1371 configurations. 1373 Open issues include: 1375 - Validating the mathematical model further. 1377 Successful validation against the results in [RFC5439] using two 1378 different approaches is encouraging, but these are for P2P variants 1379 of the model. It will be useful to attempt to sanity-check the 1380 results for the P2MP equations produce, perhaps using simulation. 1382 - Quantifying/removing approximations in mathematical model 1384 The approximation that the position of a subsequent PE in a 1385 receiving set is independent of the position of the preceding PEs 1386 should be investigated further and, ideally, removed. Getting rid 1387 of this approximation will complicate the mathematics more but is 1388 potentially worthwhile as it will make the results more accurate 1389 and remove the requirement that N < S(1) , M(1), and M(2). 1390 (Essentially, the goal should be to use the exact probabilities, 1391 for example, in Table 4). Doing so may be possible by exploiting 1392 patterns in the probabilities. 1394 9. Management Considerations 1396 Management of networks with large numbers of MPLS-TE LSPs pose a 1397 number of challenging network management problems. Some of these 1398 issues are indentified and discussed within the relevant sections of 1399 this document. Additional discussion of network management 1400 considerations will be included in future versions of the 1401 document. 1403 10. Security Considerations 1405 Security considerations for MPLS can be found in [MPLS-SEC]. 1407 Increasing the number of LSPs in a network to the point that the 1408 network is unmanageable or fails to operate constitutes as 1409 serious security risk. 1411 11. Recommendations 1413 The authors would like to expand the analysis and validate the 1414 mathematical models used in this study. Next steps are outlined in 1415 section 8 (Conclusions and Open Issues) of this document. This 1416 document does not make any specific recommendation at this time. 1418 12. IANA Considerations 1420 This document makes no requests for IANA action. 1422 13. Acknowledgements 1424 The authors are grateful to Thomas Morin for his comments and 1425 Julie Morrison for useful discussions regarding the math. 1427 14. References 1429 14.1. Informative References 1431 [RFC2961] Berger, L., Gan, D., Swallow, G., Pan, P., Tommasi, F., 1432 and S. Molendini, "RSVP Refresh Overhead Reduction 1433 Extensions", RFC 2961, April 2001. 1435 [RFC3209] Awduche, D., Berger, L., Gan, D., Li, T., Srinivasan, V., 1436 and G. Swallow, "RSVP-TE: Extensions to RSVP for LSP 1437 Tunnels", RFC 3209, December 2001. 1439 [RFC3473] Berger, L., et al., Editor, "Generalized Multi-Protocol 1440 Label Switching (GMPLS) Signaling Resource ReserVation 1441 Protocol-Traffic Engineering (RSVP-TE) Extensions", 1442 RFC 3473, January 2003. 1444 [RFC4090] P. Pan, G. Swallow, A. Atlas (Editors), "Fast Reroute 1445 Extensions to RSVP-TE for LSP Tunnels", RFC 4090, May 1446 2005. 1448 [RFC4206] Kompella, K. and Y. Rekhter, "Label Switched Paths (LSP) 1449 Hierarchy with Generalized Multi-Protocol Label 1450 Switching (GMPLS) Traffic Engineering (TE)", RFC 4206, 1451 October 2005. 1453 [RFC4875] Aggarwal, R., Papadimitriou, D., and Yasukawa, S., 1454 "Extensions to Resource Reservation Protocol - Traffic 1455 Engineering (RSVP-TE) for Point-to-Multipoint TE Label 1456 Switched Paths (LSPs)", RFC 4875, May 2007. 1458 [RFC5439] Yasukawa, S., Farrel, A., and Komolafe, O., "An Analysis 1459 of Scaling Issues in MPLS-TE Core Networks", RFC 5439, 1460 February 2009. 1462 [MPLS-SEC] Fang, L. (Ed.), "Security Framework for MPLS and GMPLS 1463 Networks", draft-ietf-mpls-mpls-and-gmpls-security- 1464 framework, work in progress. 1466 15. Authors' Addresses 1468 Olufemi Komolafe 1469 Cisco Systems 1470 96 Commercial Street 1471 Edinburgh 1472 EH6 6LX 1473 United Kingdom 1474 EMail: femi@cisco.com 1476 Adrian Farrel 1477 Old Dog Consulting 1478 EMail: adrian@olddog.co.uk 1480 Daniel King 1481 Old Dog Consulting 1482 EMail: daniel@olddog.co.uk 1484 16. Intellectual Property Consideration 1486 The IETF Trust takes no position regarding the validity or scope of 1487 any Intellectual Property Rights or other rights that might be 1488 claimed to pertain to the implementation or use of the technology 1489 described in any IETF Document or the extent to which any license 1490 under such rights might or might not be available; nor does it 1491 represent that it has made any independent effort to identify any 1492 such rights. 1494 Copies of Intellectual Property disclosures made to the IETF 1495 Secretariat and any assurances of licenses to be made available, or 1496 the result of an attempt made to obtain a general license or 1497 permission for the use of such proprietary rights by implementers or 1498 users of this specification can be obtained from the IETF on-line IPR 1499 repository at http://www.ietf.org/ipr 1501 The IETF invites any interested party to bring to its attention any 1502 copyrights, patents or patent applications, or other proprietary 1503 rights that may cover technology that may be required to implement 1504 any standard or specification contained in an IETF Document. Please 1505 address the information to the IETF at ietf-ipr@ietf.org. 1507 The definitive version of an IETF Document is that published by, or 1508 under the auspices of, the IETF. Versions of IETF Documents that are 1509 published by third parties, including those that are translated into 1510 other languages, should not be considered to be definitive versions 1511 of IETF Documents. The definitive version of these Legal Provisions 1512 is that published by, or under the auspices of, the IETF. Versions of 1513 these Legal Provisions that are published by third parties, including 1514 those that are translated into other languages, should not be 1515 considered to be definitive versions of these Legal Provisions. 1517 For the avoidance of doubt, each Contributor to the IETF Standards 1518 Process licenses each Contribution that he or she makes as part of 1519 the IETF Standards Process to the IETF Trust pursuant to the 1520 provisions of RFC 5378. No language to the contrary, or terms, 1521 conditions or rights that differ from or are inconsistent with the 1522 rights and licenses granted under RFC 5378, shall have any effect and 1523 shall be null and void, whether published or posted by such 1524 Contributor, or included with or in such Contribution. 1526 17. Disclaimer of Validity 1528 All IETF Documents and the information contained therein are provided 1529 on an "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE 1530 REPRESENTS OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY, THE 1531 IETF TRUST AND THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL 1532 WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY 1533 WARRANTY THAT THE USE OF THE INFORMATION THEREIN WILL NOT INFRINGE 1534 ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS 1535 FOR A PARTICULAR PURPOSE. 1537 18. Full Copyright Statement 1539 Copyright (c) 2009 IETF Trust and the persons identified as the 1540 document authors. All rights reserved. 1542 This document is subject to BCP 78 and the IETF Trust's Legal Provisions 1543 Relating to IETF Documents (http://trustee.ietf.org/license-info) 1544 in effect on the date of publication of this document. Please 1545 review these documents carefully, as they describe your rights and 1546 restrictions with respect to this document.