Network Working Group O. Komolafe Internet-Draft Cisco Systems Intended Status: Informational A. Farrel Created: August 27, 2009 Old Dog Consulting Expires: February 27, 2010 D. King Old Dog Consulting An Analysis of Scaling Issues for Point-to-Multipoint Label Switched Paths in MPLS-TE Core Networks draft-komolafe-mpls-te-p2mp-scaling-analysis-02.txt Status of this Memo This Internet-Draft is submitted to IETF in full conformance with the provisions of BCP 78 and BCP 79. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet- Drafts. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress." The list of current Internet-Drafts can be accessed at http://www.ietf.org/ietf/1id-abstracts.txt. The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html. Abstract Traffic engineered Multiprotocol Label Switching (MPLS-TE) is deployed in providers' core networks, and the scaling properties have been analyzed to show how much control state must be maintained to support a full mesh of edge-to-edge point-to-point (P2P) Label Switched Paths (LSPs) in various network topologies and with several different scaling techniques. Point-to-multipoint (P2MP) MPLS-TE LSPs are very interesting to service providers as a means to provide multicast services (such as TV distribution, or multicast VPN connectivity) across core MPLS networks. P2MP LSPs have different scaling properties than P2P LSPs, and service providers need to understand whether existing protocols and implementations can support the network sizes and service levels that they are planning in their P2MP MPLS-TE networks. This document presents an analysis of the scaling properties MPLS-TE core networks that support P2MP LSPs. Komolafe, Farrel, and King [Page 1] draft-komolafe-mpls-te-p2mp-scaling-analysis-02.txt August 2009 Contents 1. Introduction ................................................... 3 1.1 Overview ...................................................... 3 1.2 Definitions and Glossary of Notation .......................... 5 1.3. Network Topologies ........................................... 5 1.4. Relationship Probabilities ................................... 6 2. Issues of Concern for Scaling .................................. 7 3. A New Method for Calculations for Point-to-Point LSPs .......... 8 3.1. Number of LSPs Traversing a P(1) Node ........................ 8 3.2. Number of LSPs Traversing a P(2) Node ....................... 10 4. Analysis of a P2MP LSP with Two Destinations .................. 12 4.1. Closest Destination is a Sibling of the Source .............. 12 4.2. Closest Destination is a First Cousin of the Source ......... 14 4.3. Closest Destination is a Second Cousin of the Source ........ 15 4.4. The Average Number of State Segments at P(1) and P(2) LSRs .. 16 4.5. Generic Formula for Number of State Segments at P(1) and P(2) LSRs ................................................... 19 5. Three PEs in Receiving Set of P2MP LSPs ....................... 22 6. Any Number of PEs in the Receiving Set of a P2MP LSP .......... 25 7. Exemplar Numeric Results ...................................... 27 7.1. Impact of Varying Topological Properties of the Network ..... 27 7.2. Impact of Varying the Number of PEs in the Receiving Set .... 28 8. Conclusions and Open Issues ................................... 30 9. Management Considerations ..................................... 31 10. Security Considerations ...................................... 31 11. Recommendations .............................................. 31 12. IANA Considerations .......................................... 31 13. Acknowledgements ............................................. 31 14. References ................................................... 31 14.1. Informative References ..................................... 31 15. Authors' Addresses ........................................... 32 16. Intellectual Property Consideration .......................... 32 17. Disclaimer of Validity ....................................... 33 18. Full Copyright Statement ..................................... 33 Komolafe, Farrel, and King [Page 2] draft-komolafe-mpls-te-p2mp-scaling-analysis-02.txt August 2009 1. Introduction Network operators and service providers are examining scaling issues as they look to deploy ever-larger traffic engineered Multiprotocol Label Switching (MPLS-TE) networks. Concerns have been raised about the number of Label Switched Paths (LSPs) that need to be supported at the edge and at the core of the network. The impact on control plane and management plane resources threatens to outweigh the benefits and popularity of MPLS-TE, while the physical limitations of the routers may constrain the deployment options. These issues and concerns are examined in [RFC5439] for networks carrying point-to- point (P2P) LSPs. Point-to-multipoint (P2MP) MPLS-TE LSPs are very interesting to service providers as a means to provide multicast services (such as TV distribution, or multicast VPN connectivity) across core MPLS networks. The MPLS-TE and Generalized MPLS (GMPLS) signaling ([RFC3209] and [RFC3473]) has been extended to support the control plane establishment of P2MP LSPs [RFC4875]. P2MP LSPs have different scaling properties than P2P LSPs, and service providers need to understand whether existing protocols and implementations can support the network sizes and service levels that they are planning in their P2MP MPLS-TE networks. This document presents an analysis of the scaling properties MPLS-TE core networks that support P2MP LSPs. 1.1 Overview Point-to-multipoint LSPs can be considered as a set of point-to-point fragments that are joined together to form a tree. The tree is rooted at the source, and has a number of leaves (destinations). Each P2P fragment runs between the source and a branch, between a pair of branches, or between a branch and a leaf (in the extreme case, a fragment may also run directly between the root and a branch). The scaling benefit of a P2MP LSP comes in the fact that only one copy of the data for a set of leaves downstream of a particular branch is transmitted to that branch. This means that only one set of resources (for example, buffers) is consumed on the path upstream of the branch, leaving room for other LSPs to traverse the same path. In the control plane there are savings, too. At each branch node, it is necessary to hold only one piece of upstream control plane state, and one piece of state for each downstream fragment. This compares with the P2P equivalent where it would be necessary to hold as much upstream state as downstream state. Komolafe, Farrel, and King [Page 3] draft-komolafe-mpls-te-p2mp-scaling-analysis-02.txt August 2009 Note that this is a slight simplification. P2MP control plane state must identify all downstream leaves and may contain certain leaf- specific information such as the paths to those leaves), and this information must be present in the upstream control plane state. Nevertheless, the reduction in quantity of state information is significant, and the effort required within the protocol implementation to maintain the state information is reduced exactly as described. Thus, in order to quantify the scaling properties of P2MP LSPs in a network, we count control plane state per interface. That is, at any given node on the path of a P2MP tree we count the number of the node's interfaces that participate in the LSP. At the source, this is always one. At a branch node it is (1 + n) where there is just one upstream interface and n downstream interfaces. At a leaf we consider just one upstream interface. (Note that the special case of a bud node [RFC4875] that is a leaf but that also has downstream neighbors in the LSP is not considered in this document. This is a feature of the snowflake topology that is used as the model as described in Section 1.3.) The approach adopted in this document is to derive some formulae based on the probabilistic measure of where a node lies in the network, and what role it plays in the P2MP LSP. Furthermore, in order to simplify the equations that are derived, certain approximations are introduced - although these are believed to diminish in significance as the size of the network grows. This method is verified by applying it to P2P LSPs and comparing the results with those algorithms derived in [RFC5439]. As described in Section 8, although this mechanism seems to deliver reasonable results and agrees with the P2P formulae of [RFC5439], the mathematical model needs further validation. Similarly, it would be valuable to attempt to quantify the approximations in the model. This document is designed to help service providers discover whether existing protocols and implementations can support the network sizes that they are planning. To do this, it presents an analysis of some of the scaling concerns for MPLS-TE core networks, and examines the value of two techniques for improving scaling. This should motivate the development of appropriate deployment techniques and protocol extensions to enable the application of MPLS-TE in large networks. This version of this document is limited to the analysis of P2MP LSPs in the artificially symmetric snowflake network, and the comparison of the results with those for P2P LSPs. The document does not address any scaling techniques such as hierarchical LSPs [RFC4206] (whether P2P or P2MP), nor does it look at protection mechanisms such as Fast Re-route (FRR) [RFC4090]. These features and their applicability to other generic network topologies are for future study. Komolafe, Farrel, and King [Page 4] draft-komolafe-mpls-te-p2mp-scaling-analysis-02.txt August 2009 1.2 Definitions and Glossary of Notation This document applies consistent notation to define various parameters of the networks that are analyzed. These terms are defined as they are introduced though-out the document, but are grouped together here for quick reference. Refer to the full definitions in the text for detailed explanations. Where possible, these terms are kept consistent with those used in [RFC5439]. n A network level. n = 1 is the core of the network. P(n) A node at level n in the network. S(n) The number of nodes at level n, i.e., the number of P(n) nodes. L(n) The number of LSPs traversing a P(n) node. X(n) The number of LSP segment states maintained by a P(n) node, i.e., X(n) = 2*L(n) for P2P LSPs. x(n) A single LSP segment state maintained by a P(n) node; i.e., X(n) = SUM[x(n)] M(n) The number of P(n+1) nodes subtended to a P(n) node. N The number of destination PEs for each P2MP LSP; i.e. the size of the receiving set is N. Sibling nodes: PEs subtended to the same P(n). First cousin nodes: PEs subtended to the same P(n-1) but different P(n). Second cousin nodes: PEs attached to different P(n-1) nodes. C(init): The cost in terms of x(n) of setting up a P2MP LSP from a source to the closest PE in the receiving set. C(inc): The incremental cost in terms of x(n) of having a subsequent PE in the receiving set. 1.3. Network Topologies At this stage, analysis is limited to the snowflake topology defined in [RFC5439]. In this type of network, only the very core of the network is meshed. The edges of the network are formed as trees rooted in the core. Thus, the snowflake topology is based on a hierarchy of connectivity within the core network. PEs are not directly interconnected, but have connectivity to exactly one P(n) (dual homing is not considered at this stage). Each P(n) is connected to precisely one P(n-1) and to no other P(n) node. There is one exception: the P(1) nodes are Komolafe, Farrel, and King [Page 5] draft-komolafe-mpls-te-p2mp-scaling-analysis-02.txt August 2009 assumed to be connected in a full mesh. Figure 1 shows an example snowflake topology. PEa PE PE PE PEc PE PE PE PE PE \ | \ | / \ | / | / \| \|/ \|/ |/ PEb--P(2) P(2) P(2) P(2)--PE \ | | / PE \ | | / PE \ \| |/ / PE-P(2)---P(1)-----P(1)---P(2)-PE / |\ /| \ PE | \ / | PE | \/ | | /\ | PE | / \ | PE \ |/ \| / PE-P(2)---P(1)-----P(1)---P(2)-PE / /| |\ \ PE / | | \ PE / | | \ PE--P(2) P(2) P(2) P(2)--PE /| /|\ /|\ |\ / | / | \ / | \ | \ PE PE PE PE PE PE PE PE PE PEd Figure 1 : A Snowflake Network In Figure 1, the PEs marked PEa and PEb are siblings (subtended to the same P(n) - n=2 in this network). The PEs marked PEa and PEc are first cousins (subtended to the same P(n-1) but to different P(n)s). The PEs marked PEa and PEd are second cousins (subtended to different P(n-1) nodes). Throughout this document, a snowflake network with 3 levels (i.e., there are P(1), P(2) and PE Label Switching Routers (LSRs)) is considered. However, the methodology employed may be easily applied to networks with a greater number of levels. 1.4. Relationship Probabilities In a snowflake network with 3 levels, consider a given PE: there are a total of S(1)*M(1)*M(2) - 1 other PEs, of which M(2) - 1 are siblings. Hence, the probability of another PE chosen at random being a sibling is: Prob(sibling) = (M(2) - 1) / (S(1)*M(1)*M(2) - 1) Komolafe, Farrel, and King [Page 6] draft-komolafe-mpls-te-p2mp-scaling-analysis-02.txt August 2009 Similarly: Prob(first cousin) = (M(2)*(M(1) - 1)) / (S(1)*M(1)*M(2) - 1) And: Prob(second cousin) = M(1)*M(2)*(S(1) - 1) / (S(1)*M(1)*M(2) - 1) 2. Issues of Concern for Scaling Issues of concern for scaling are discussed in detail in [RFC5439] and translate to P2MP LSPs. The issues directly affect the number of LSPs that an LSR can support, and therefore may limit the number of LSPs and hence customer services that can be supported by a network. The issues may be summarized as follows. - LSP State LSP state is the data (information) that must be stored at an LSR in order to maintain an LSP. This is mainly information used by the control plane protocols and grows in direct proportion to the number of LSPs. Since the memory capacity of an LSR is limited, there is a related limit placed on the number LSPs that can be supported. - Processing Overhead The number of LSPs passing through an LSR may impact the processing speed for each LSP. For example, control block search times can increase with the number of control blocks to be searched. Thus, since CPU power is constrained in any LSR, there may be a practical limit to the number of LSPs that can be supported. - RSVP-TE Implications RSVP-TE is a soft-state protocol which means that protocol messages (refresh messages) must be regularly exchanged between signaling neighbors in order to maintain the state for each LSP that runs between the neighbors. Observations of existing implementations indicate that there may be a threshold of around 50,000 P2P LSPs above which an LSR struggles to achieve sufficient processing to maintain LSP state. No observational figures are available for P2MP LSPs, but similar behavior may be expected. Various techniques including refresh reduction [RFC2961], increasing the refresh interval, use of the RSVP-TE Hello message [RFC3209], and the use of GMPLS extensions [RFC3473] (such as the use of [RFC2961] message acknowledgements on all messages) can improve the situation markedly. Komolafe, Farrel, and King [Page 7] draft-komolafe-mpls-te-p2mp-scaling-analysis-02.txt August 2009 - Management Another practical concern for the scalability of large MPLS-TE networks is the ability to manage the network. This may be constrained by the available tools, the practicality of managing large numbers of LSPs, and the management protocols in use. All of these consideration limit the number of LSPs supported within the network and at any particular LSR. 3. A New Method for Calculations for Point-to-Point LSPs 3.1. Number of LSPs Traversing a P(1) Node To calculate the number of LSPs seen by each P(1) LSR, consider the case when each PE establishes a single P2P LSP to a destination PE chosen at random. Zero, one, or two P(1) LSRs will be traversed depending on whether the destination is a sibling, first cousin, or second cousin respectively. Hence it may be said that each P(1) LSR traversed will either be: - an ingress P(1) LSR: such a node is the only P(1) LSR traversed if the destination is a first cousin and the first P(1) LSR traversed if the destination is a second cousin. Hence, each P1 LSR will be an ingress P(1) LSR for each of the M(1)*M(2) subtended PEs that establishes an LSP destined for a PE that is not a sibling, the probability of which is 1 - Prob(sibling). or - an egress P(1) LSR: such a node is the second P(1) LSR traversed as a result of the destination being a second cousin. Essentially, an egress P(1) LSR handles the LSPs destined for subtended PEs originating from second cousin PEs. There is a total of M(1)*M(2)*(S(1) - 1) source PEs which are second cousin nodes to the subtended PEs and the possibility of each of these establishing an LSP to one of the subtended PEs is Prob(second cousin) / (S(1) - 1). Figure 2 illustrates examples of ingress P(1) and egress P(1) nodes. The figure shows three exemplar LSPs from a common source to three distinct destinations (d, d1, and d2). d is a sibling of the source, d1 is a first cousin of the source, and d2 is a second cousin of the source. In these LSPs there is one ingress P(1) (marked as iP(1)) and one egress P(1) (marked as eP(1)). Komolafe, Farrel, and King [Page 8] draft-komolafe-mpls-te-p2mp-scaling-analysis-02.txt August 2009 PE d PE PE PE PE PE PE PE PE \ | \ | / \ | / | / \| \|/ \|/ |/ Source--P(2) P(2) P(2) P(2)--PE \ | | / PE \ | | / PE \ \| |/ / PE-P(2)---iP(1)---eP(1)---P(2)-PE / |\ /| \ d1 | \ / | d2 | \/ | | /\ | Figure 2 : Illustration of Ingress and Egress P(1) Nodes Table 1 summarizes the probability of each P(1) LSR being an ingress P(1) or an egress P(1), and shows the frequency with which it may fulfill that role. Role | Prob(role) | Frequency | | -------------+--------------------------------+---------------------- | | Ingress P(1) | 1 - Prob(sibling) | M(1)*M(2) | | -------------+--------------------------------+---------------------- | | Egress P(1) | Prob(second cousin)/(S(1) - 1) | M(1)*M(2)*(S(1) - 1)) | | Table 1 : Probability and Frequency of Fulfilling a P(1) Role Each P(1) LSR will be both an ingress and egress LSR depending on the relative location of the source and destination PEs. Therefore, l(1), the number of LSPs seen by a P(1) LSR if every PE were to establish an LSP to a randomly selected PE is: l(1) = M(1)*M(2)*(1 - Prob(sibling)) + M(1)*M(2)*(S(1) - 1) * Prob(second cousin)/(S(1) - 1) = M(1)*M(2)*(1 - Prob(sibling)) + M(1)*M(2) * Prob(second cousin) = M(1)*M(2) * (1 - ( (M(2) - 1) / (S(1)*M(1)*M(2) - 1) + M(1)*M(2) * (M(1)*M(2)*(S(1) - 1) / (S(1)*M(1)*M(2) - 1)) = M(1)*M(2) * (2*S(1)*M(1)*M(2) - M(2) - M(1)*M(2)) / (S(1)*M(1)*M(2) - 1) = M(1)*M(2) * (2*S(PE) - M(2) - M(1)*M(2)) / (S(PE) - 1) Komolafe, Farrel, and King [Page 9] draft-komolafe-mpls-te-p2mp-scaling-analysis-02.txt August 2009 Lastly, l(1) is obtained when each PE establishes a single LSP to a randomly chosen destination. L(1) refers to when LSPs are established to S(PE) - 1 destinations and so: L(1) = M(1)*M(2)*(2*S(PE) - M(2) - M(1)*M(2)) This result is consistent with the result shown in section 5.1 of [RFC5439]. 3.2. Number of LSPs Traversing a P(2) Node Again, assuming each source PE establishes a single P2P LSP to a randomly chosen destination PE, the manner in which the P(2) LSRs will be traversed by LSPs is described below, illustrated in Figure 3, and summarized in Table 2. - An ingress P2 LSR is traversed when one of the subtended PEs establishes an LSP. There are M2 subtended PEs and the probability of each PE establishing an LSP that traverses the given P(2) node is 1. - A first cousin egress P(2) LSR handles the LSP whenever it is established by one of the first cousin PEs and destined for one of the subtended PEs. There are M(2)*(M(1) - 1) first cousins and the probability of each of these establishing an LSP to a PE subtended to any given P(2) node is Prob(first cousin) / (M(1) - 1). - A second cousin egress P(2) LSR handles the LSP whenever it is established by one of the second cousin PEs and destined for one of the subtended PEs. The number of the former is M(1)*M(2)*(S(1) - 1) and the probability of the latter is Prob(second cousin) / M(1)*(S(1) - 1). Figure 3 shows examples of ingress and egress P(2) nodes. There are three exemplar LSPs from a single source to three destinations (d, d1, and d2). d is a sibling of the source, d1 is a first cousin of the source, and d2 is a second cousin of the source. The ingress P(2) node is marked iP(2). There are two egress P(2) nodes; one is a first cousin egress P(2) (marked e1P(2) on the figure), and one is a second cousin egress P(2) (marked e2P(2)). Komolafe, Farrel, and King [Page 10] draft-komolafe-mpls-te-p2mp-scaling-analysis-02.txt August 2009 PE d PE PE PE PE PE PE PE PE \ | \ | / \ | / | / \| \|/ \|/ |/ Source--iP(2) P(2) P(2) P(2)--PE \ | | / PE \ | | / PE \ \| |/ / PE-e1P(2)--P(1)-----P(1)---e2P(2)-PE / |\ /| \ d1 | \ / | d2 | \/ | | /\ | Figure 3 : Example of Ingress and Egress P(2) Nodes Role | Prob(role) | Frequency | | --------------+-------------------------------+---------------------- | | Ingress P(2) | 1 | M(2) | | --------------+-------------------------------+---------------------- | | Egress first | Prob(first cousin)/(M(1) - 1) | M(2)*(M(1) - 1)) cousin P(2) | | | | --------------+-------------------------------+---------------------- | | Egress second | Prob(second cousin) / | M(1)*M(2)*(S(1) - 1)) cousin P(2) | (M(1)*(S(1) - 1)) | | | Table 2 : Probability and Frequency of Fulfilling a P(2) Role Therefore, l(2), the number of LSPs seen by a P(2) LSR if every PE were to establish an LSP to a randomly selected PE is: l(2) = M(2) + M(2)(M(1) - 1)*(Prob(first cousin) / (M(1) - 1) ) + M(1)*M(2)(S(1) - 1)*(Prob(second cousin)/(M(1)*(S(1) - 1)) ) = M(2) + M(2)*Prob(first cousin) + M(2)*Prob(second cousin) = ( M(2) / (S(1)*M(1)*M(2) - 1) ) * ( S(1)*M(1)*M(2) - 1 + M(1)*M(2) - M(2) + S(1)*M(1)*M(2) - M(1)*M(2) ) = (M(2) / (S(1)*M(1)*M(2) - 1)) * (2*S(1)*M(1)*M(2) - M(2) - 1) = M(2) * (2*S(PE) - M(2) - 1) / (S(PE) - 1) Komolafe, Farrel, and King [Page 11] draft-komolafe-mpls-te-p2mp-scaling-analysis-02.txt August 2009 Therefore: L(2) = M(2) * (2*S(PE) - M(2) - 1) This result is also consistent with the conclusion reached in section 5.1 of [RFC5439]. We can, therefore, assume that this approach is viable P2P MPLS-TE LSPs. The next sections extend this approach to P2MP LSPs. 4. Analysis of a P2MP LSP with Two Destinations Consider a P2MP LSP with a set of receiving nodes (destinations) called d1 and d2. If we count the number of hops from the source to each destination, we are able to designate d1 as the closer to the source, and d2 as being equidistant or further from the source. According to our definitions, d1 must be a sibling, a first cousin, or a second cousin of the source. We consider these three possibilities in turn. 4.1. Closest Destination is a Sibling of the Source The probability that d1 is a sibling of the source is Prob(sibling) = (M(2) - 1) / (S(1)*M(1)*M(2) - 1) The cost associated with this possibility is that each P(2) LSR holds two state segments (one corresponding to the input interface and one for the output interface), giving C(init) = 2*x(2). The incremental cost of reaching d2, C(inc), is dependent on its relative location to d1. As shown in Figure 4, there are three distinct possibilities: - d2 is a sibling of d1 (and so also a sibling of the source) Excluding the source and d1, there is a total of S(1)*M(1)*M(2) - 2 PEs of which M(2) - 2 are siblings of d1 and the source. Thus, for d2 the probability of being a sibling is: Prob(sibling) = (M(2) - 2) / (S(1)*M(1)*M(2) - 2) Replication must occur at the P(2) LSR for the P2MP LSP to reach d2 and so the incremental cost is an extra state segment at the P(2) LSR, thus C(inc) = x(2). Komolafe, Farrel, and King [Page 12] draft-komolafe-mpls-te-p2mp-scaling-analysis-02.txt August 2009 - d2 is a first cousin of d1 (and the source) The probability that d2 is a first cousin of the source is Prob(first cousin) = (M(2)*(M(1) - 1)) / (S(1)*M(1)*M(2) - 2) Replication occurs at the first P(2) LSR, giving an extra state segment there, x(2). Since d2 is a first cousin, only a single P(1) is traversed, requiring that LSR to support two state segments, yielding 2*x(1). Lastly, the P(2) LSR to which d2 is attached must be traversed by the LSP, leading to that LSR supporting two state segments, giving 2*x(1). Aggregating, we arrive at: C(inc) = x(2) + 2*x(1) + 2*x(2) - d2 is a second cousin of d1 (and the source) The probability that d2 is a second cousin of the source is Prob(second cousin) = (M(1)*M(2)*(S(1) - 1)) / (S(1)*M(1)*M(2) - 2) The only difference with the previous scenario is that d2 being a second cousin requires the LSP to traverse an extra P(1) LSR, giving C(inc) = x(2) +2*x(1) +2*x(1) + 2*x(2) In Figure 4 we show a source and the nearest destination, d1. d1 is a sibling of the source. Three possible locations for d2 are considered: d2a is a sibling of d1 (and of the source), d2b is a first cousin of d1 (and of the source), d2c is a second cousin of d1 (and of the source). d1 d2a PE PE PE PE PE PE PE PE \ | \ | / \ | / | / \| \|/ \|/ |/ Source--P(2) P(2) P(2) P(2)--PE \ | | / PE \ | | / PE \ \| |/ / PE-e1P(2)--P(1)-----P(1)---e2P(2)-PE / |\ /| \ d2b | \ / | d2c | \/ | | /\ | Figure 4 : d1 is a Sibling of the Source, Yielding Three Possibilities for the Location of d2 Komolafe, Farrel, and King [Page 13] draft-komolafe-mpls-te-p2mp-scaling-analysis-02.txt August 2009 4.2. Closest Destination is a First Cousin of the Source The probability that d1 is a first cousin of the source is: Prob(first cousin) = M(2)*(M(1) - 1) / (S(1)*M(1)*M(2) - 1) The associated initial cost is: C(init) = 2*x(2) + 2*x(1) + 2*x(2). Given the requirement that d1 is equidistant or closer to the source than d2, d2 cannot be a sibling of the source. This leaves the following possibilities, also illustrated in Figure 5: - d2 is a sibling of d1 (and a first cousin of the source) Prob(sibling) = (M(2) - 1) / (S(1)*M(1)*M(2) - 2) C(inc) = x(2) - d2 is a first cousin of d1 (and of the source) Prob(first cousin) = M(2)*(M(1) - 2) / (S(1)*M(1)*M(2) - 2) C(inc) = x(1) + 2*x(2) - d2 is a second cousin of d1 (and of the source) Prob(second cousin) = M(1)*M(2)*(S(1) - 1) / (S(1)*M(1)*M(2) - 2) C(inc) = x(1) + 2*x(1) + 2*x(2) In Figure 5 we show a source and the nearest destination, d1. d1 is a first cousin of the source. Three possible locations for d2 are considered: d2a is a sibling of d1, d2b is a first cousin of d1, d2c is a second cousin of d1. Komolafe, Farrel, and King [Page 14] draft-komolafe-mpls-te-p2mp-scaling-analysis-02.txt August 2009 PE PE PE PE d2b PE PE PE PE PE \ | \ | / \ | / | / \| \|/ \|/ |/ Source--P(2) P(2) P(2) P(2)--PE \ | | / PE \ | | / PE \ \| |/ / d1-e1P(2)--P(1)-----P(1)---e2P(2)-PE / |\ /| \ d2a | \ / | d2c | \/ | | /\ | Figure 5 : d1 is a First Cousin of the Source, Yielding Three Possibilities for the Location of d2 4.3. Closest Destination is a Second Cousin of the Source The probability that d1 is a second cousin of the source is: Prob(second cousin) = M(1)*M(2)*(S(1) - 1) / (S(1)*M(1)*M(2) - 1) The associated initial cost is: C(init) = 2*x(2) + 2*x(1) + 2*x(1) + 2*x(2) Given the requirement that d1 is equidistant or closer to the source than d2, d2 cannot be a sibling or a first cousin of the source. This leaves the following possibilities, also illustrated in Figure 6: - d2 is a sibling of d1 (and a second cousin of the source) Prob(sibling) = (M(2) - 1) / (S(1)*M(1)*M(2) - 2) C(inc) = x(2) - d2 is a first cousin of d1 (and a second cousin of the source) Prob(first cousin) = M(2)*(M(1) - 1) / (S(1)*M(1)*M(2) - 2) C(inc) = x(1) + 2*x(2) - d2 is a second cousin of d1 (and of the source) Prob(second cousin) = M(1)*M(2)*(S(1) - 2) / (S(1)*M(1)*M(2) - 2) C(inc) = x(1) + 2*x(1) + 2*x(2) Komolafe, Farrel, and King [Page 15] draft-komolafe-mpls-te-p2mp-scaling-analysis-02.txt August 2009 In Figure 6 we show a source and the nearest destination, d1. d1 is a second cousin of the source. Three possible locations for d2 are considered: d2a is a sibling of d1, d2b is a first cousin of d1, d2c is a second cousin of d1. PE PE PE PE PE PE PE d2b PE PE \ | \ | / \ | / | / \| \|/ \|/ |/ Source--P(2) P(2) P(2) P(2)--PE \ | | / PE \ | | / d2a \ \| |/ / PE-P(2)---P(1)-----P(1)---P(2)-PE / |\ /| \ PE | \ / | d1 | \/ | | /\ | PE | / \ | PE \ |/ \| / PE-P(2)---P(1)-----P(1)---P(2)-PE / /| |\ \ PE / | | \ PE / | | \ PE--P(2) P(2) P(2) P(2)--PE /| /|\ /|\ |\ / | / | \ / | \ | \ d2c PE PE PE PE PE PE PE PE PE Figure 6 : d1 is a Second Cousin of the Source, Yielding Three Possibilities for the Location of d2 4.4. The Average Number of State Segments at P(1) and P(2) LSRs Having discussed the nine different permutations of establishing a P2MP LSP from a given PE to two destination PEs in a three-level snowflake topology, the next step is to explore the scalability of this configuration by computing the number of LSP state segments that must be handled by the P(1) and P(2) LSRs. To compute this value, the cost associated with each permutation, obtained by summing C(inc) and C(init) appropriately, has to be weighted by the corresponding probability and the overall cost aggregated. Table 3 gives the nine permutations, the associated costs in terms of state segments that must be managed at P(1) and P(2) nodes and the exact and approximate probabilities of the particular LSP being established. Komolafe, Farrel, and King [Page 16] draft-komolafe-mpls-te-p2mp-scaling-analysis-02.txt August 2009 In Table 3, the following three probabilities must be recalled: Prob(sibling) = (M(2) - 1) / (S(1)*M(1)*M(2) - 1) Prob(first cousin) = M(2)*(M(1) - 1) / (S(1)*M(1)*M(2) - 1) Prob(second cousin) = M(1)*M(2)*(S(1) - 1) / (S(1)*M(1)*M(2) - 1) For the sake of fitting the table on the page, the equations for the exact probabilities for d2 positions are numbered I through VI and are listed after the table. d1 | d2 |LSR state -------------------------+--------------------------------+ segments Position | Exact | Position |Exact|Approx |----+---- wrt src |probability |wrt d1 |prob |probability |P(1)|P(2) ---------+---------------+----------+-----+---------------+----+---- sibling |Prob(sibling) |Sibling | I |Prob(sibling) | 0 | 3 sibling |Prob(sibling) |1st cousin| II |Prob(1stcousin)| 2 | 5 sibling |Prob(sibling) |2nd cousin| III |Prob(2ndcousin)| 4 | 5 1stcousin|Prob(1stcousin)|Sibling | IV |Prob(sibling) | 2 | 5 1stcousin|Prob(1stcousin)|1st cousin| V |Prob(1stcousin)| 3 | 6 1stcousin|Prob(1stcousin)|2nd cousin| III |Prob(2ndcousin)| 5 | 6 2ndcousin|Prob(2ndcousin)|Sibling | IV |Prob(sibling) | 4 | 5 2ndcousin|Prob(2ndcousin)|1st cousin| II |Prob(1stcousin)| 5 | 6 2ndcousin|Prob(2ndcousin)|2nd cousin| VI |Prob(2ndcousin)| 7 | 6 Equations: I (M(2) - 2) / (S(1)*M(1)*M(2) - 2) II M(2)*(M(1) - 1) / (S(1)*M(1)*M(2) - 2) III M(1)*M(2)*(S(1) - 1) / (S(1)*M(1)*M(2) - 2) IV (M(2) - 1) / (S(1)*M(1)*M(2) - 2) V M(2)*(M(1)-2) / (S(1)*M(1)*M(2) - 2) VI M(1)*M(2)*(S(1) - 2) / (S(1)*M(1)M(2) - 2) Table 3 : Summary of Probabilities and Cost of Establishing P2MP LSP To Two PEs The approximate probabilities essentially assume the probabilities of d2 being in a certain location are independent of the location of d1, which is evidently not the case. However, such an approximation is attractive as it simplifies the equations significantly (a fact more important as the size of the receiving set grows). Furthermore, comparing the approximate and exact probabilities suggest that the approximate probabilities are not unreasonable, and actually would be expected to be close the exact probabilities for large networks (i.e., large values of M(1), M(2), and S(1) should reduce the discrepancy). Komolafe, Farrel, and King [Page 17] draft-komolafe-mpls-te-p2mp-scaling-analysis-02.txt August 2009 Therefore, approximate probabilities are used in the remainder of this document. In consequence, the total approximate number of state segments at P(1) and P(2) LSRs, X(1) and X(2) respectively, may be calculated as follows: X1 = 2*Prob(sibling)*Prob(first cousin) + 4*Prob(sibling)*Prob(second cousin) + 2*Prob(first cousin)*Prob(sibling) + 3*Prob(first cousin)**2 + 5*Prob(first cousin)*Prob(second cousin) + 4*Prob(second cousin)*Prob(sibling) + 5*Prob(second cousin)*Prob(first cousin) + 7*Prob(second cousin)**2 = 4*Prob(sibling)*Prob(first cousin) + 8*Prob(sibling)*Prob(second cousin) + 3*Prob(first cousin)**2 + 10*Prob(first cousin)*Prob(second cousin) + 7*Prob(second cousin)**2 X2 = 3*Prob(sibling)**2 + 5*Prob(sibling)*Prob(first cousin) + 5*Prob(sibling)*Prob(second cousin) + 5*Prob(first cousin)*Prob(sibling) + 6*Prob(first cousin)**2 + 6*Prob(first cousin)*P(second cousin) + 5*Prob(second cousin)*Prob(sibling) + 6*Prob(second cousin)*P(first cousin) + 6*Prob(second cousin)**2 = 3*Prob(sibling)**2 + 10*Prob(sibling)*Prob(first cousin) + 10*Prob(sibling)*Prob(second cousin) + 6*Prob(first cousin)**2 + 12*Prob(first cousin)*Prob(second cousin) + 6*Prob(second cousin)**2 These two equations give the number of state segments that must be handled by the P(1) and P(2) LSRs respectively if a source sets up a P2MP LSP to any 2 PEs. The values for Prob(sibling), Prob(first cousin), and Prob(second cousin) from Section 1.4 may be substituted into the equations allowing X(1) and X(2) to be expressed in terms of the topological properties of the network. Furthermore, the two equations for X(1) and X(2) correspond to the establishment of a single P2MP LSP, and so the equations must be appropriately scaled to handle more than one P2MP LSP. For example, the results should be multiplied by S(PE) to reflect every PE establishing an LSP. Komolafe, Farrel, and King [Page 18] draft-komolafe-mpls-te-p2mp-scaling-analysis-02.txt August 2009 Lastly, the equations for X(1) and X(2) give the total number of state segments handled by all P(1) and P(2) LSRs in the network and so must be divided by the number of each type of LSR to obtain the average values. Intuitively, the symmetry in the snowflake network suggests that there will be little variance around the average value provided each PE establishes an equal number of LSPs and the destinations are chosen from an identical statistical distribution. 4.5. Generic Formula for Number of State Segments at P(1) and P(2) LSRs Let D be the set of possible locations for a given destination in a P2MP LSP and so: D = {sibling, first cousin, second cousin} Let D1 and D2 be members of D. Using the patterns which may be observed in Table 3, generic formulae for X(1) and X(2) may be computed. X1 = SUM [ SUM [Prob(d1 = D1)*Prob(d2 = D2)*(fa(D1) + fb(D1, D2))] ] D1 D2 where fa(D1) = 0 if D1 is sibling 2 if D1 is first cousin 4 if D1 is second cousin fb(D1, D2) = 0 if D2 is sibling 1 if D1 is not sibling AND D2 is first cousin 2 if D1 is sibling AND D2 is first cousin 3 if D1 is not sibling AND D2 is second cousin 4 if D1 is sibling AND D2 is second cousin This equation for X(1) basically says that to compute the number of state segments at the P(1) LSR, iterate over all possible relative locations for the PEs in the receiving set and, for each permutation, calculate the product of the probability of that permutation occurring (i.e., Prob(d1 = D1)*P(d2 = D2)) and the associated cost (i.e., (fa(D1)+fb(D1, D2)). Summing the products over all the permutations give the desired metric. fa(D1) describes the number of state segments that must be handled by P(1) LSRs due to the location of the first PE in the receiving set, d1. No state segments are handled by any P(1) LSR if d1 is a sibling of the source. In this case, the LSP does not need to traverse any P(1) LSR to reach d1, but rather reaches it via the P(2) LSR to which d1 and the source are both attached. If d1 is a first cousin of the Komolafe, Farrel, and King [Page 19] draft-komolafe-mpls-te-p2mp-scaling-analysis-02.txt August 2009 source, the LSP reaches it via the P(1) LSRs to which they are both subtended and so two state segments must be handled by the P(1) LSR. Four state segments are handled by P(1) LSRs when d1 is a second cousin of the source due to the requirement for the LSP to traverse two P(1) LSRs. fb(D1, D2) describes the incremental cost associated with any replication necessary for the P2MP LSP to reach the second PE in the receiving set, d2. If d2 is a sibling of d1, then no state segments need be handled by any of the P(1) LSRs. On the other hand, if d2 is a first cousin of d1, then one or two additional state segments must be handled by the P(1) LSRs, depending on whether or not d1 is a sibling of the source. If d1 is a sibling, then replication must occur at the first P(2) LSP and, since the LSP is destined for a first cousin, only a single P(1) LSR is traversed and so two state segments must be supported by the P(1) LSRs. When d1 is not a sibling, then it is either a first or second cousin of the source and so replication must occur at the first or second P(1) LSR respectively, with an additional state segment being necessary at that P(1) LSRs to reach d2. Lastly, if d2 is a second cousin of d1 and d1 is a sibling of the source, replication occurs at the first P(2) LSP and, since two P(1) LSRs must be traversed to reach a second cousin, four state segments must be handled by P(1) LSRs. If d2 is a second cousin of d1, and d1 is not a sibling of the source, replication occurs at the first P(1) LSR and, since the LSP must traverse a second P(1) LSR, gives a total of three state segments. Similarly, for the number of state segments handled by the P(2) LSRs: X(2) = SUM [ SUM [ Prob(d1=D1)*Prob(d2=D2)*(fc(D1) + fd(D1, D2))]] D1 D2 where fc(D1) = 2 if D1 is sibling 4 otherwise fd(D1, D2) = 1 if D2 is sibling 2 if D1 is not sibling AND D2 is not sibling 3 if D1 is sibling AND D2 is not sibling fc(D1) simply states that the first PE in the receiving set, d1, requires two state segments to be supported at P(2) LSRs when it is a sibling of the source, and four states when it is not; two at each of the two P(2) LSR that must be traversed in this case. According to fd(D1, D2), when the second PE in the receiving set, d2, is a sibling of d1 it results in a single additional state segment Komolafe, Farrel, and King [Page 20] draft-komolafe-mpls-te-p2mp-scaling-analysis-02.txt August 2009 being supported at the P(2) LSR, due to the replication that must occur there. If d1 is neither a sibling of the source nor d2, then replication must occur at a P(1) LSR and so reaching d2 adds two extra state segments at P(2) LSRs, corresponding to traversing the second P(2) LSR. If d1 is a sibling of the source but d2 is not, then replication occurs at the first P(2) LSR and, given the requirement to traverse a second P(2) LSR, produces a total of three state segments being supported by the P(2) LSRs. These two equations for X(1) and X(2) may be readily expanded to obtain the results given in Section 4.4 and have the advantage of being more easily adaptable as the size of the receiving set increases, an advantage exploited in the remainder of this document. Furthermore, these two equations may be adapted to consider the cost of establishing a P2P LSP, and so used to validate the equations against the results set out in [RFC5439]. For a P2P LSP, there is no d2, thus it may be said that: X(1:p2p) = 2*Prob(first cousin) + 4*Prob(second cousin) This gives the total mean number of state segments at all the P(1) LSRs when a single P2P LSP is established. The values for Prob(first cousin) and Prob(second cousin) from Section 1.4 may be substituted into the equation. To obtain the result matching Section 3.1 and [RFC5439], we must multiply by S(PE) - 1 (since each source establishes an LSP to every other PE), multiply by S(PE) (since there are S(PE) sources), divide by 2 (since the number of state segments is twice the number of LSPs seen by the LSR for P2P LSPs), and divide by S(1) (since there are S(1) P(1) LSRs). This looks as follows: L1 = S(PE)*(S(PE)-1) * (2*Prob(first cousin) + 4*Prob(second cousin)) / 2*S(1) = S(PE)*(S(PE) - 1) * (2*M(2)(M(1) - 1) / (S(1)*M(1)*M(2) - 1) + 4*M(1)*M(2)*(S(1) - 1) / (S(1)*M(1)*M(2) - 1) ) / 2*S(1) = 2*S(1)*M(1)*M(2)*(S(1)*M(1)*M(2) - 1) * (M(2)*(M(1) - 1) + 2*M(1)*M(2)*(S(1) - 1)) / 2*S(1)*(S(1)*M(1)*M(2) - 1) = M(1)*M(2)*(2*S(PE) - M(2) - M(1)*M(2)) Similarly: X(2:p2p) = 2*Prob(sibling) + 4*(1 - Prob(sibling)) = 2*(2 - Prob(sibling)) Komolafe, Farrel, and King [Page 21] draft-komolafe-mpls-te-p2mp-scaling-analysis-02.txt August 2009 This gives the total mean number of state segments at all P(2) LSRs when a single P2P LSP is established. This result should be multiplied by S(PE) - 1 (since each source establishes an LSP to every other PE), multiplied by S(PE) (since there are S(PE) sources), divided by 2 (since the number of state segments is twice the number of LSPs seen by the LSR for P2P LSPs), and divided by S(1)*M(1) (since there are S1M1 P2 LSRs) to give the same result as found in Section 3.1 and [RFC5439]. This is achieved as follows: L2 = S(PE)*(S(PE) - 1)* 2*(2 - Prob(sibling)) / 2*S(1)*M(1) = S(PE)*(S(PE) - 1)* 2*(2 - (M(2) - 1)/(S(1)*M(1)*M(2) - 1)) / 2*S(1)*M(1) = 2*S(1)*M(1)*M(2)*(S(1)*M(1)*M(2) - 1) * (2*(S(1)*M(1)*M(2) - 1) - M(2) + 1) / 2*S(1)*M(1)*(S(1)*M(1)*M(2) - 1) = M(2)*(2*S(PE) - M(2) - 1) 5. Three PEs in Receiving Set of P2MP LSPs The three nodes in the receiving set are d1, d2, and d3. Once again, d1 is the closest to the source, followed by d2, and lastly d3. Table 4 summarizes all the different ways the P2MP LSP may be established and the respective number of state segments that must be supported by P(1) and P(2) LSRs. In reading Table 4, recall that: Prob(sibling) = (M(2) - 1) / (S(1)*M(1)*M(2) - 1) Prob(first cousin) = M(2)*(M(1) - 1) / (S(1)*M(1)*M(2) - 1) P(second cousin) = M(1)*M(2)*(S(1) - 1) / (S(1)*M(1)*M(2) - 1) In order to fit this table on the page, it is necessary to adopt some additional notation conventions as follows. sib sibling 1c first cousin 2c second cousin p(x) Prob(x) Additionally, the equations for exact probabilities are represented by the roman numerals I-XV and are listed separately. Komolafe, Farrel, and King [Page 22] draft-komolafe-mpls-te-p2mp-scaling-analysis-02.txt August 2009 d1 | d2 | d3 |LSR state -----------+------------------+-------------------+ segments Psn |Exact |Psn |Exact|Approx |Psn |Exact |Approx |----+---- wrt |prob |wrt |prob |prob |wrt |prob |prob |P(1)|P(2) src | |d1 | | |d2 | | | | ----+------+----+-----+-------+----+------+-------+----+---- sib |p(sib)|sib | I |p(sib) |sib | VII |p(sib) | 0 | 4 sib |p(sib)|sib | I |p(sib) |1c | VIII |p(1c) | 2 | 6 sib |p(sib)|sib | I |p(sib) |2c | IX |p(2c) | 4 | 6 sib |p(sib)|1c | II |p(1c) |sib | XI |p(sib) | 2 | 6 sib |p(sib)|1c | II |p(1c) |1c | X |p(1c) | 3 | 7 sib |p(sib)|1c | II |p(1c) |2c | IX |p(2c) | 5 | 7 sib |p(sib)|2c | III |p(2c) |sib | XI |p(sib) | 4 | 6 sib |p(sib)|2c | III |p(2c) |1c | VIII |p(1c) | 5 | 7 sib |p(sib)|2c | III |p(2c) |2c | XII |p(2c) | 7 | 7 1c |p(1c) |sib | IV |p(sib) |sib | XIII |p(sib) | 2 | 5 1c |p(1c) |sib | IV |p(sib) |1c | X |p(1c) | 3 | 7 1c |p(1c) |sib | IV |p(sib) |2c | IX |p(2c) | 5 | 7 1c |p(1c) |1c | V |p(1c) |sib | XI |p(sib) | 3 | 7 1c |p(1c) |1c | V |p(1c) |1c | XIV |p(1c) | 4 | 8 1c |p(1c) |1c | V |p(1c) |2c | IX |p(2c) | 6 | 8 1c |p(1c) |2c | III |p(2c) |sib | XI |p(sib) | 5 | 7 1c |p(1c) |2c | III |p(2c) |1c | VIII |p(1c) | 6 | 8 1c |p(1c) |2c | III |p(2c) |2c | XII |p(2c) | 8 | 8 2c |p(2c) |sib | IV |p(sib) |sib | XIII |p(sib) | 4 | 6 2c |p(2c) |sib | IV |p(sib) |1c | X |p(1c) | 5 | 7 2c |p(2c) |sib | IV |p(sib) |2c | XII |p(2c) | 7 | 7 2c |p(2c) |1c | II |p(1c) |sib | XI |p(sib) | 5 | 7 2c |p(2c) |1c | II |p(1c) |1c | X |p(1c) | 6 | 8 2c |p(2c) |1c | II |p(1c) |2c | XII |p(2c) | 8 | 8 2c |p(2c) |2c | VI |p(2c) |sib | XI |p(sib) | 7 | 7 2c |p(2c) |2c | VI |p(2c) |1c | VIII |p(1c) | 8 | 8 2c |p(2c) |2c | VI |p(2c) |2c | XV |p(2c) | 10 | 8 Table 4 : Summary of Probabilities and Cost of Establishing a P2MP LSP to Three PEs Equations: I (M(2) - 2) / (S(1)*M(1)*M(2) - 2) II M(2)*(M(1) - 1) / (S(1)*M(1)*M(2) - 2) III M(1)*M(2)*(S(1) - 1) / (S(1)*M(1)*M(2) - 2) IV (M(2) - 1) / (S(1)*M(1)*M(2) - 2) V M(2)*(M(1) - 2) / (S(1)*M(1)*M(2) - 2) VI M(1)*M(2)*(S(1) - 2) / (S(1)*M(1)*M(2) - 2) VII (M(2) - 3) / (S(1)*M(1)*M(2) - 3) VIII M(2)*(M(1) - 1) / (S(1)*M(1)*M(2) - 3) IX M(1)*M(2)*(S(1) - 1) / (S(1)*M(1)*M(2) - 3) X M(2)*(M(1) - 2) / (S(1)*M(1)*M(2) - 3) Komolafe, Farrel, and King [Page 23] draft-komolafe-mpls-te-p2mp-scaling-analysis-02.txt August 2009 XI (M(2) - 1) / (S(1)*M(1)*M(2) - 3) XII M(1)*M(2)*(S(1) - 2) / (S(1)*M(1)*M(2) - 3) XIII (M(2) - 2) / (S(1)*M(1)*M(2) - 3) XIV M(2)*(M(1) - 3) / (S(1)*M(1)*M(2) - 2) XV M(1)*M(2)*(S(1) - 3) / (S(1)*M(1)*M(2) - 3) Using a similar approach to that used in Section 4.5, the approximate number of state segments that must be handled by P(1) and P(2) LSRs may be readily computed. Again, Let D be the set of possible locations for a given destination in a P2MP LSP and so D = {sibling, first cousin, second cousin} Using the patterns which may be observed in Table 4, generic formula for X(1) and X(2) may be computed as follows. X(1) = SUM [ D1 SUM [ D2 SUM [ Prob(d1=D1)*Prob(d2=D2)*Prob(d3=D3) * D3 (fe(D1) + ff(D1, D2) + fg(D1, D2, D3))]]] where fe(D1) = 0 if D1 is sibling 2 if D1 is a first cousin 4 if D1 is a second cousin ff(D1, D2) = 0 if D2 is sibling 1 if D1 is not a sibling AND D2 is a first cousin 2 if D1 is a sibling AND D2 is a first cousin 3 if D1 is not a sibling AND D2 is a second cousin 4 if D1 is a sibling AND D2 is a second cousin fg(D1, D2, D3) = 0 if D3 is sibling 1 if (D1 OR D2 is not sibling) AND D3 is first cousin 2 if D1 is sibling AND D2 is sibling AND D3 is first cousin 3 if (D1 is not sibling OR D2 is not sibling) AND D3 is second cousin 4 if D1 is sibling AND D2 is sibling AND D3 is a second cousin Komolafe, Farrel, and King [Page 24] draft-komolafe-mpls-te-p2mp-scaling-analysis-02.txt August 2009 Similarly, for the number of state segments handled by the P(2) LSRs: X(2) = SUM [ D1 SUM [ D2 SUM [ Prob(d=D1) * Prob(d2=D2) * Prob(d3=D3) * D3 (fh(D1) + fi(D1, D2) + fj(D1, D2, D3)) ]]] where fh(D1) = 2 if D1 is sibling 4 otherwise fi(D1, D2) = 1 if D2 is sibling 2 if D1 is not sibling AND D2 is not sibling 3 if D1 is sibling AND D2 is not sibling fj(D1, D2, D3) = 1 if D3 is sibling 2 if (D1 is not sibling OR D2 is not sibling) AND D3 is not sibling 3 if D1 is sibling AND D2 is sibling AND D3 is not sibling It can be readily seen that there are similarities between the equations here and those for X(1) and X(2) in Section 4.5. The main difference is that, in the former equations, when considering the incremental cost of reaching the third PE in the receiving set, d3, the relative position of all the previous PEs in the receiving set must be taken into consideration. These similarities will be exploited to allow generic equations for the mean number of state segments that must be supported at P(1) and P(2) LSRs as a function of the receiving set size in Section 6. 6. Any Number of PEs in the Receiving Set of a P2MP LSP Sections 4 and 5 have shown the scalability parameters for a single P2MP LSP from a source PE to two and three PEs, respectively. It did this by estimating the average number of state segments that must be maintained by P(1) and P(2) LSRs. This section extends these findings by considering the case where there are an arbitrary number of PEs, N, which are receivers for the LSP. Comparing our two equations for X(1) (Sections 4.5 and 5) we can deduce a generic equation about the mean number of state segments that must be supported at the P(1) LSR when there are N PEs in the receiving set for the P2MP LSP: Komolafe, Farrel, and King [Page 25] draft-komolafe-mpls-te-p2mp-scaling-analysis-02.txt August 2009 X(1) = SUM [ ... SUM [ Prob(d1=D1)*...*Prob(dN=DN)* D1 DN (fa(D1)+fb(D1,D2)+...+fb(D1,...,DN))]...] where fa(D1) = 0 if D1 is sibling 2 if D1 is first cousin 4 if D1 is second cousin fb(D1,D2,...Dj) = 0 if Dj is sibling 1 if any of D1, D2 ... Dj-1 is not sibling AND Dj is first cousin 2 if all of D1, D2 ... Dj-1 are sibling AND Dj is first cousin 3 if any of D1, D2 ... Dj-1 is not sibling AND Dj is second cousin 4 if all of D1, D2 ... Dj-1 are sibling AND Dj is second cousin Similarly, for the number of state segments handled by the P2 LSRs, X(2) = SUM [ ... SUM [ Prob(d1=D1)*...*Prob(dN=DN)* D1 DN (fc(D1)+fd(D1,D2)+...+fd(D1,...,DN))]...] where fc(D1) = 2 if d1 is sibling 4 otherwise fd(D1,D2,...Dj) = 1 if Dj is sibling 2 if any of D1, D2 ... Dj-1 is not sibling AND Dj is not sibling 3 if all of D1, D2 ... Dj-1 are sibling AND Dj is not sibling These two equations for X(1) and X(2) give the values of the approximate mean number of state segments that must be supported by P(1) and P(2) LSRs when a P2MP LSP is set up from a single source to N destination PEa. These equations are used to obtain exemplar numerical results in Section 7. Komolafe, Farrel, and King [Page 26] draft-komolafe-mpls-te-p2mp-scaling-analysis-02.txt August 2009 7. Exemplar Numeric Results 7.1. Impact of Varying Topological Properties of the Network We can substitute the probabilities that a given PE is a sibling, first cousin, or second cousin (given by the equations in Section 1.4) into the equations in Section 6 so that the number of state segments that must be supported by P(1) and P(2) LSRs, X(1) and X(2), can be computed as functions of the topological properties of the snowflake topology, M1, M2, and S1. This allows the impact of varying these topology parameters on the scalability to be investigated. A simple snowflake topology with M1, M2, and S1 all initially equal to 4 was considered. A P2MP LSP from every PE to 3 other randomly chosen PEs was established. Each one of M1, M2, and S1 was individually varied from 4 to 20 (with the other two parameters kept equal to 4) to allow the impact of varying each of these parameters individually to be shown in isolation. Table 5 shows the results. M(1) | M(2) | S(1) | X(1) | X(2) -----+------+------+-----------+-------------- 4 | 4 | 4 | 134.855 | 31.428125 4 | 4 | 6 | 143.326 | 31.62091667 4 | 4 | 8 | 147.527 | 31.7165625 4 | 4 | 10 | 150.038 | 31.7735 4 | 4 | 12 | 151.707 | 31.81145833 4 | 4 | 14 | 152.897 | 31.83857143 4 | 4 | 16 | 153.788 | 31.85875 4 | 4 | 18 | 154.481 | 31.87458333 4 | 4 | 20 | 155.034 | 31.887125 4 | 4 | 4 | 134.855 | 31.428125 4 | 6 | 4 | 201.344 | 47.05175 4 | 8 | 4 | 267.837 | 62.675625 4 | 10 | 4 | 334.332 | 78.3 4 | 12 | 4 | 400.829 | 93.924375 4 | 14 | 4 | 467.325 | 109.54875 4 | 16 | 4 | 533.822 | 125.173125 4 | 18 | 4 | 600.32 | 140.7975 4 | 20 | 4 | 666.817 | 156.421875 4 | 4 | 4 | 134.855 | 31.428125 6 | 4 | 4 | 202.862 | 31.62091667 8 | 4 | 4 | 270.866 | 31.7165625 10 | 4 | 4 | 338.868 | 31.7735 12 | 4 | 4 | 406.869 | 31.81145833 14 | 4 | 4 | 474.87 | 31.83857143 16 | 4 | 4 | 542.87 | 31.85875 18 | 4 | 4 | 610.871 | 31.87458333 20 | 4 | 4 | 678.871 | 31.887125 Table 5 : Impact of Varying Topological Properties of a Network Komolafe, Farrel, and King [Page 27] draft-komolafe-mpls-te-p2mp-scaling-analysis-02.txt August 2009 Table 5 shows that, typically, a greater number of average state segments must be supported by P(1) LSRs than P2 LSRs. This finding is unsurprising given that the topology of the snowflake network means it would be expected that a greater number of LSPs are concentrated in the core. It may be seen from Table 5 that increasing M(1) or M(2) leads to a linear increase in the number of state segments that must be handled at P(1) LSRs. This observation may be explained by realizing that increasing M(1) or M(2) (equivalently) increases the number of PEs subtended to each P(1) LSR and so more LSPs will be expected to be handled by this LSR. In contrast, increasing S1 increases the number of P1 LSRs but since the number of PEs subtended to each P(1) LSR remains unchanged (since M(1) and M(2) are unvaried in this case), the mean number of state segments remain relatively constant. Varying either M(1) or S(1) does not alter the number of PEs subtended to each P(2) LSR and so the mean number of state segments that must be handled by P(2) LSRs remains relatively unchanged. In contrast, increasing M(2) directly increases the number of PEs attached to each P(2) LSR and thus increases the number of state segments that such LSRs must handle accordingly. 7.2. Impact of Varying the Number of PEs in the Receiving Set The impact of varying the size of receiving set, N, when the topological properties of the network are kept constant is considered in this section. A simple snowflake topology in which M(1), M(2), and S(1) are all equal to 12, and in which N is varied from 1 to 10 is considered. Table 6 records the number of state segments that must be handled at P(1) and P(2) LSRs when the P2MP LSP is set up. For comparison, Table 6 also presents the results of establishing a corresponding set of P2P LSPs, allowing any benefits obtained by using P2MP LSPs instead of P2P to be quantified. The cost of establishing N P2P LSPs to the PEs in the receiving set was calculated by multiplying the cost of establishing a P2P LSP given in the equations for P2P LSPs in Section 4.5 by S(PE) * N since there are SPE sources of N P2P LSPs. Table 6 shows that, again, there is are more LSPs handled by P(1) LSRs than P(2) LSRs. Also, as would be expected, increasing the size of the receiving set increases the amount of state that must be supported by LSRs. Komolafe, Farrel, and King [Page 28] draft-komolafe-mpls-te-p2mp-scaling-analysis-02.txt August 2009 Number of PEs | P2P X(1) | P2P X(2) | P2MP X(1) | P2MP X(2) --------------+----------+--------------+-----------+-------------- 1 | 550.318 | 47.84715278 | 550.318 | 47.84715278 2 | 1100.636 | 95.69430556 | 958.465 | 71.84652778 3 | 1650.954 | 143.5414583 | 1365.71 | 95.77083333 4 | 2201.272 | 191.3886111 | 1772.94 | 119.6944444 5 | 2751.59 | 239.2357639 | 2180.18 | 143.6180556 6 | 3301.908 | 287.0829167 | 2587.41 | 167.5416667 7 | 3852.226 | 334.9300695 | 2994.65 | 191.4652778 8 | 4402.544 | 382.7772222 | 3401.89 | 215.3881944 9 | 4952.862 | 430.624375 | 3809.12 | 239.3118056 10 | 5503.18 | 478.4715278 | 4216.36 | 263.2354167 Table 6 : Impact of Varying the Number of PEs in the Receiving Set When P2P or P2MP LSPs are Used Using P2MP LSPs leads to LSRs having to support less state than if P2P LSPs are used. The relative reduction in the amount of state that must be supported by LSRs when P2MP LSPs instead of P2P LSPs are used is illustrated in Table 7. It can be seen that the relative reduction obtained by using P2MP LSPs initially rises with the size of the receiving set, before levelling off at around 24% and 45% for P(1) and P(2) LSRs respectively. It is perhaps surprising that using multicast does not achieve greater performance improvement; this finding may be explained by realizing that the approximations made in assuming the position of a subsequent PE in a receiving set is independent of the position of the preceding PEs means that the P2MP results presented here are close to the worst-case results. Basically, in a topology with M(1) = M(2) = S(1) = 12, Prob(second cousin) = 92% and so the worst-case P2MP LSPs in which all the destinations are second cousins (and so there are N replications at the first P1 LSR) is statistically the most likely scenario. Consequently, using multicast reduces the state predominantly only on the path from the PE to the first P(1) LSR, via the first P(2) LSR. On the other hand, had positions of preceding PEs in the receiving set been taken into consideration, the possibility of a given PE being a second cousin will diminish with the number of PEs in the receiving set which are already second cousins and so the probability of establishing the worst-case P2MP LSP will be lower. Komolafe, Farrel, and King [Page 29] draft-komolafe-mpls-te-p2mp-scaling-analysis-02.txt August 2009 Number of PEs | Percentage Reduction Using P2MP LSPs | Compared to P2P LSPs | | X(1) | X(2) --------------+-------------------+-------------------- 1 | 0 | 4.64442E-09 2 | 12.91716789 | 24.92079089 3 | 17.2775256 | 33.28001928 4 | 19.45838588 | 37.45999632 5 | 20.76653862 | 39.96798254 6 | 21.6389433 | 41.63997336 7 | 22.26182991 | 42.83425251 8 | 22.72899487 | 43.7301433 9 | 23.0925473 | 44.42678598 10 | 23.38320753 | 44.98410012 Table 7 : Reduction in the Number of State Segments at LSRs Obtained by Establishing P2MP LSPs Instead of P2P LSPs 8. Conclusions and Open Issues A framework for investigating the scalability of P2MP MPLS-TE deployments by estimating the amount of state that must be handled by different types of LSRs in a snowflake network has been developed. The approach works by exhaustively aggregating the sum of the product of the cost and probabilities of all the different P2MP LSPs configurations. Open issues include: - Validating the mathematical model further. Successful validation against the results in [RFC5439] using two different approaches is encouraging, but these are for P2P variants of the model. It will be useful to attempt to sanity-check the results for the P2MP equations produce, perhaps using simulation. - Quantifying/removing approximations in mathematical model The approximation that the position of a subsequent PE in a receiving set is independent of the position of the preceding PEs should be investigated further and, ideally, removed. Getting rid of this approximation will complicate the mathematics more but is potentially worthwhile as it will make the results more accurate and remove the requirement that N < S(1) , M(1), and M(2). (Essentially, the goal should be to use the exact probabilities, for example, in Table 4). Doing so may be possible by exploiting patterns in the probabilities. Komolafe, Farrel, and King [Page 30] draft-komolafe-mpls-te-p2mp-scaling-analysis-02.txt August 2009 9. Management Considerations Management of networks with large numbers of MPLS-TE LSPs pose a number of challenging network management problems. Some of these issues are indentified and discussed within the relevant sections of this document. Additional discussion of network management considerations will be included in future versions of the document. 10. Security Considerations Security considerations for MPLS can be found in [MPLS-SEC]. Increasing the number of LSPs in a network to the point that the network is unmanageable or fails to operate constitutes as serious security risk. 11. Recommendations The authors would like to expand the analysis and validate the mathematical models used in this study. Next steps are outlined in section 8 (Conclusions and Open Issues) of this document. This document does not make any specific recommendation at this time. 12. IANA Considerations This document makes no requests for IANA action. 13. Acknowledgements The authors are grateful to Thomas Morin for his comments and Julie Morrison for useful discussions regarding the math. 14. References 14.1. Informative References [RFC2961] Berger, L., Gan, D., Swallow, G., Pan, P., Tommasi, F., and S. Molendini, "RSVP Refresh Overhead Reduction Extensions", RFC 2961, April 2001. [RFC3209] Awduche, D., Berger, L., Gan, D., Li, T., Srinivasan, V., and G. Swallow, "RSVP-TE: Extensions to RSVP for LSP Tunnels", RFC 3209, December 2001. [RFC3473] Berger, L., et al., Editor, "Generalized Multi-Protocol Label Switching (GMPLS) Signaling Resource ReserVation Protocol-Traffic Engineering (RSVP-TE) Extensions", RFC 3473, January 2003. [RFC4090] P. Pan, G. Swallow, A. Atlas (Editors), "Fast Reroute Extensions to RSVP-TE for LSP Tunnels", RFC 4090, May 2005. Komolafe, Farrel, and King [Page 31] draft-komolafe-mpls-te-p2mp-scaling-analysis-02.txt August 2009 [RFC4206] Kompella, K. and Y. Rekhter, "Label Switched Paths (LSP) Hierarchy with Generalized Multi-Protocol Label Switching (GMPLS) Traffic Engineering (TE)", RFC 4206, October 2005. [RFC4875] Aggarwal, R., Papadimitriou, D., and Yasukawa, S., "Extensions to Resource Reservation Protocol - Traffic Engineering (RSVP-TE) for Point-to-Multipoint TE Label Switched Paths (LSPs)", RFC 4875, May 2007. [RFC5439] Yasukawa, S., Farrel, A., and Komolafe, O., "An Analysis of Scaling Issues in MPLS-TE Core Networks", RFC 5439, February 2009. [MPLS-SEC] Fang, L. (Ed.), "Security Framework for MPLS and GMPLS Networks", draft-ietf-mpls-mpls-and-gmpls-security- framework, work in progress. 15. Authors' Addresses Olufemi Komolafe Cisco Systems 96 Commercial Street Edinburgh EH6 6LX United Kingdom EMail: femi@cisco.com Adrian Farrel Old Dog Consulting EMail: adrian@olddog.co.uk Daniel King Old Dog Consulting EMail: daniel@olddog.co.uk 16. Intellectual Property Consideration The IETF Trust takes no position regarding the validity or scope of any Intellectual Property Rights or other rights that might be claimed to pertain to the implementation or use of the technology described in any IETF Document or the extent to which any license under such rights might or might not be available; nor does it represent that it has made any independent effort to identify any such rights. Copies of Intellectual Property disclosures made to the IETF Secretariat and any assurances of licenses to be made available, or Komolafe, Farrel, and King [Page 32] draft-komolafe-mpls-te-p2mp-scaling-analysis-02.txt August 2009 the result of an attempt made to obtain a general license or permission for the use of such proprietary rights by implementers or users of this specification can be obtained from the IETF on-line IPR repository at http://www.ietf.org/ipr The IETF invites any interested party to bring to its attention any copyrights, patents or patent applications, or other proprietary rights that may cover technology that may be required to implement any standard or specification contained in an IETF Document. Please address the information to the IETF at ietf-ipr@ietf.org. The definitive version of an IETF Document is that published by, or under the auspices of, the IETF. Versions of IETF Documents that are published by third parties, including those that are translated into other languages, should not be considered to be definitive versions of IETF Documents. The definitive version of these Legal Provisions is that published by, or under the auspices of, the IETF. Versions of these Legal Provisions that are published by third parties, including those that are translated into other languages, should not be considered to be definitive versions of these Legal Provisions. For the avoidance of doubt, each Contributor to the IETF Standards Process licenses each Contribution that he or she makes as part of the IETF Standards Process to the IETF Trust pursuant to the provisions of RFC 5378. No language to the contrary, or terms, conditions or rights that differ from or are inconsistent with the rights and licenses granted under RFC 5378, shall have any effect and shall be null and void, whether published or posted by such Contributor, or included with or in such Contribution. 17. Disclaimer of Validity All IETF Documents and the information contained therein are provided on an "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY, THE IETF TRUST AND THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION THEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. 18. Full Copyright Statement Copyright (c) 2009 IETF Trust and the persons identified as the document authors. All rights reserved. This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents in effect on the date of Komolafe, Farrel, and King [Page 33] draft-komolafe-mpls-te-p2mp-scaling-analysis-02.txt August 2009 publication of this document (http://trustee.ietf.org/license-info). Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Komolafe, Farrel, and King [Page 34]