 1/draftietfmplstescalinganalysis02.txt 20080619 12:12:31.000000000 +0200
+++ 2/draftietfmplstescalinganalysis03.txt 20080619 12:12:31.000000000 +0200
@@ 1,21 +1,21 @@
Network Working Group S. Yasukawa
InternetDraft NTT
Intended Status: Informational A. Farrel
Created: April 24, 2008 Old Dog Consulting
Expires: October 24, 2008 O. Komolafe
+Created: June 19, 2008 Old Dog Consulting
+Expires: December 19, 2008 O. Komolafe
Cisco Systems
An Analysis of Scaling Issues in MPLSTE Core Networks
 draftietfmplstescalinganalysis02.txt
+ draftietfmplstescalinganalysis03.txt
Status of this Memo
By submitting this InternetDraft, each author represents that any
applicable patent or other IPR claims of which he or she is aware
have been or will be disclosed, and any of which he or she becomes
aware will be disclosed, in accordance with Section 6 of BCP 79.
InternetDrafts are working documents of the Internet Engineering
Task Force (IETF), its areas, and its working groups. Note that other
@@ 56,42 +56,42 @@
2. Issues of Concern for Scaling ................................. 5
2.1 LSP State ................................................... 5
2.2 Processing Overhead .......................................... 5
2.3 RSVPTE Implications ......................................... 6
2.4 Management ................................................... 7
3. Network Topologies ............................................ 7
3.1 The Snowflake Network Topology ............................... 8
3.2 The Ladder Network Topology .................................. 10
3.3 Commercial Drivers for Selected Configurations ............... 12
3.4 Other Network Topologies ..................................... 13
 4. Required Network Sizes ........................................ 13
+ 4. Required Network Sizes ........................................ 14
4.1 Practical Numbers ............................................ 14
5. Scaling in Flat Networks ...................................... 14
 5.1 Snowflake Networks ........................................... 14
+ 5.1 Snowflake Networks ........................................... 15
5.2 Ladder Networks .............................................. 16
6. Scaling Snowflake Networks with Forwarding Adjacencies ........ 19
 6.1 Two Layer Hierarchy .......................................... 19
 6.1.1 Tuning the Network Topology to Suit the Two Layer Hierarchy 20
+ 6.1 Two Layer Hierarchy .......................................... 20
+ 6.1.1 Tuning the Network Topology to Suit the Two Layer Hierarchy 21
6.2 Alternative Two Layer Hierarchy .............................. 21
6.3 Three Layer Hierarchy ........................................ 22
6.4 Issues with Hierarchical LSPs ............................... 23
7. Scaling Ladder Networks with Forwarding Adjacencies............ 24
7.1 Two Layer Hierarchy .......................................... 24
7.2 Three Layer Hierarchy ........................................ 25
7.3 Issues with Hierarchical LSPs ................................ 26
8. Scaling Improvements Through MultipointtoPoint LSPs ......... 26
8.1 Overview of MP2P LSPs ........................................ 27
8.2 LSP State: A Better Measure of Scalability ................... 27
8.3 Scaling Improvements for Snowflake Networks .................. 28
 8.3.1 Comparison with Other Scenarios ............................ 30
 8.4 Scaling Improvements for Ladder Networks ..................... 31
 8.4.1 Comparison with Other Scenarios ............................ 32
+ 8.3.1 Comparison with Other Scenarios ............................ 29
+ 8.4 Scaling Improvements for Ladder Networks ..................... 30
+ 8.4.1 Comparison with Other Scenarios ............................ 31
8.4.2 LSP State Compared with LSP Numbers ........................ 33
8.5 Issues with MP2P LSPs ........................................ 33
9. Combined Models ............................................... 34
10. An Alternate Solution ........................................ 35
10.1 Pros and Cons of the Alternate Solution ..................... 36
11. Management Considerations .................................... 37
12. Security Considerations ...................................... 37
13. Recommendations .............................................. 38
14. IANA Considerations .......................................... 38
15. Acknowledgements ............................................. 38
@@ 186,66 +186,71 @@
1.2 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 thoughout the document, but are grouped
together here for quick reference. Refer to the full definitions in
the text for detailed explanations.
n A network level. n = 1 is the core of the network.
+ See section 3, for more details of the definition of a level.
P(n) A node at level n in the network.
S(n) The number of nodes at level n. That is, the number of P(n)
nodes.
L(n) The number of LSPs seen by a P(n) node.
X(n) The number of LSP segment states held by a P(n) node.
M(n) The number of P(n+1) nodes subtended to a P(n) node.
 R The number of rungs in a ladder network.
+ R The number of rungs in a ladder network.
E The number of edge nodes (PEs) subtended below (directly or
indirectly) a spar node in a ladder network.
+ K The costeffectiveness of the network expressed in terms of
+ the ratio of the number of PEs to the number of network nodes.
2. Issues of Concern for Scaling
This section presents some of the issues associated with the support
of LSPs at an LSR or within the network. These issues may mean that
there is a limit to the number LSPs that can be supported.
2.1 LSP State
LSP state is the data (information) that must be stored at an LSR in
order to maintain an LSP. Here we refer to the information that is
necessary to maintain forwarding plane state and the additional
information required when LSPs are established through control
plane protocols. While the size of the LSP state is implementation
dependent, it is clear that any implementation will require some data
in order to maintain LSP state.
 Thus LSP state becomes a scaling concern because as the number of
+ Thus LSP state becomes a scaling concern because, as the number of
LSPs at an LSR increases, so the amount of memory required to
maintain the LSPs increases in direct proportion. Since the memory
capacity of an LSR is limited, there is a related limit placed on the
number LSPs that can be supported.
Note that techniques to reduce the memory requirements (such as data
compression) may serve to increase the number of LSPs that can be
supported, but this will only achieve a moderate multiplier and may
significantly decrease the ability to process the state rapidly.
In this document we define X(n) as "The number of LSP segment states
held by a P(n) node." This definition observes that an LSR at the end
of an LSP only has to maintain state in one direction (i.e., into the
network), while a transit LSR must maintain state in both directions
(i.e., toward both ends of the LSP). Furthermore, in multipointto
point (MP2P) LSPs (see Section 8) a transit LSR may need to maintain
LSP state for one downstream segment (toward the destination) and
 multiple upstream segments (from multiple sources).
+ multiple upstream segments (from multiple sources). That is, we
+ define LSP segment state as the state necessary to maintain an LSP in
+ one direction to one adjacent node.
2.2 Processing Overhead
Depending largely on implementation issues, 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, and even excellent implementations
cannot completely mitigate this fact. Thus, since CPU power is
constrained in any LSR, there may be a practical limit to the number
of LSPs that can be supported.
@@ 369,22 +374,23 @@
/  \
/  \
/  \
PE PE PE
Figure 1 : PE to P Node Connectivity
The relationship between Pnodes is also structured in a hierarchical
way. Thus, as shown in Figure 2, multiple Pnodes at one level are
connected to a Pnode at a higher level. We number the levels such
 that level 1 is the top level and level (n) is immediately above
 level (n+1), and we denote a Pnode at level n as a P(n).
+ that level 1 is the top level (top in our figure, and nearest to the
+ core of the network) and level (n) is immediately above level (n+1),
+ and we denote a Pnode at level n as a P(n).
As with PEs, there is no direct connectivity between P(n+1) nodes.
Again, dual homing of P(n+1) nodes to multiple P(n) nodes is not
considered in this document although it may be a valuable addition
to a network configuration.
P(n)
/\
/  \
/  \
@@ 505,21 +511,23 @@
From these restrictions we are able to quantify a ladder network as
follows:
R  The number of rungs. That is, the number of sparnodes on
each spar.
S(1)  The number of sparnodes in the network. S(1)=2*R.
E  The number of subtended edge nodes (PEs) to each sparnode.
The number of rungs may vary considerably. A number less than 3 is
 unlikely, and a number greater than 100 seems improbable.
+ unlikely (since that would not be a significantly connected network),
+ and a number greater than 100 seems improbable (because that would
+ represent a very long, thin network).
E can be treated as for the snowflake network. That is, we can
consider a number of levels of attachment from P(1) nodes which are
the sparnodes, through P(i) down to P(n) which are the PEs.
Practically, we need to only consider n=2 (PEs attached direct to the
sparnodes) and n=3 (one level of Pnodes between the PEs and the
sparnodes).
Let M(i) be the ratio of P(i) nodes to P(i1) nodes, i.e. the
connectivity between levels of Pnode as defined for the snowflake
@@ 639,22 +649,22 @@
An important question for this evaluation and analysis is the size of
the network that operators require. How many PEs are required? What
ratio of P to PE is acceptable. How many ports do devices have for
physical connectivity? What type of MPLSTE connectivity between PEs
is required?
Although presentation of figures for desired network sizes must be
treated with caution because history shows that networks grow beyond
all projections, it is useful to set some acceptable lower bounds.
 That is, we can state that we already know that networks will be at
 least of a certain size.
+ That is, we can state that we are interested in networks of at least
+ a certain size.
The most important features are:
 The network should have at least 1000 PEs.
 Each pair of PEs should be connected by at least one LSP in each
direction.
4.1 Practical Numbers
In practice, reasonable target numbers are as follows.
@@ 903,44 +915,42 @@
S(PE)*(S(PE)  1) which is 1039380 and 3998000 respectively.
6. Scaling Snowflake Networks with Forwarding Adjacencies
One of the purposes of LSP hierarchies [RFC4206] is to improve the
scaling properties of MPLSTE networks. LSP tunnels (sometimes known
as Forwarding Adjacencies (FAs)) may be established to provide
connectivity over the core of the network and multiple edgetoedge
LSPs may be tunneled down a single FA LSP.
 In our network it is natural to consider a mesh of FA LSPs between
 all core nodes at the same level. We consider two possibilities here.
 In the first all P(2) nodes are connected to all other P(2) nodes,
+ In our network we consider a mesh of FA LSPs between all core nodes
+ at the same level. We consider two possibilities here. In the first
+ all P(2) nodes are connected to all other P(2) nodes by LSP tunnels,
and the PEtoPE LSPs are tunneled across the core of the network. In
 the second, an extra layer of hierarchy is introduced by connecting
 all P(1) nodes in a mesh and tunneling the P(2)toP(2) tunnels
 through these.
+ the second, an extra layer of LSP hierarchy is introduced by
+ connecting all P(1) nodes in an LSP mesh and tunneling the P(2)to
+ P(2) tunnels through these.
6.1 Two Layer Hierarchy
In this hierarchy model, the P(2) nodes are connected by a mesh of
tunnels. This means that the P(1) nodes do not see the PEtoPE LSPs.
It remains the case that:

L(PE) = 2*(S(PE)  1)
L(2) is slightly increased. It can be computed as the sum of all LSPs
for all attached PEs including the LSPs between the attached PE (this
figure is unchanged from Section 5.1: i.e. M(2)*(2*S(PE)  M(2)  1))
plus the number of FA LSPs providing a mesh to the other P(2) nodes.
Since the number of P(2) nodes is S(2), each P(2) node sees
2*(S(2)  1) FA LSPs. Thus:

L(2) = M(2)*(2*S(PE)  M(2)  1) + 2*(S(2)  1)
L(1), however, is significantly reduced and can be computed as the
sum of the number of FA LSPs to and from each attached P(2) to each
other P(2) in the network, including (but counting only once) the FA
LSPs between attached P(2) nodes. In fact, the problem is identical
to the L(2) computation in Section 5.1. So:
L(1) = M(1)*(2*S(2)  M(1)  1)
@@ 967,26 +977,27 @@
+++
A  L(2)  39580  39678
 L(1)  356000  890
+++
B  L(2)  79580  79778
 L(1)  756000  1890
6.1.1 Tuning the Network Topology to Suit the Two Layer Hierarchy
Clearly we can reduce L(2) by selecting appropriate values of S(1),
 M(1), and M(2). We can do this pretty much with immunity, since no
 change will affect L(PE), and since a large percentage increase in
+ M(1), and M(2). We can do this without negative consequences, since
+ no change will affect L(PE), and since a large percentage increase in
L(1) is sustainable because L(1) is now so small.
Observe that:
L(2) = M(2)*(2*S(PE)  M(2)  1) + 2*(S(2)  1)
+
where S(PE) = S(1)*M(1)*M(2) and S(2) = S(1)*M(1). So L(2) scales
with M(2)^2 and we can have the most impact by reducing M(2) while
keeping S(PE) constant.
For example, with S(1) = 10, M(1) = 10, and M(2) = 10, we see:
S(PE) = 1000
S(2) = 100
L(PE) = 1998
L(2) = 20088
L(1) = 1890
@@ 1236,21 +1248,21 @@
7.3 Issues with Hierarchical LSPs
The same issues exist for hierarchical LSPs as described in Section
6.4. Although dramatic improvements can be made to the scaling
numbers for the number of LSPs at core nodes, this can only be done
at the cost of configuring P(2) to P(2) tunnels. The mesh of P(1)
tunnels is not enough.
But the sheer number of P(2) to P(2) tunnels that must be configured
 is a management nightmare that can only be eased by using a
+ is a significant management burden that can only be eased by using a
technique like automesh [RFC4972].
It is significant, however, that the scaling problem at the P(2)
nodes cannot be improved by using tunnels, and the only solution to
ease this in the hierarchical approach would be to institute another
layer of hierarchy (that is, P(3) nodes) between the P(2) nodes and
the PEs. This is, of course, a significant expense.
8. Scaling Improvements Through MultipointtoPoint LSPs
@@ 1844,22 +1856,23 @@
occur if the alternate solution described in Section 10 was
adopted.
14. IANA Considerations
This document makes no requests for IANA action.
15. Acknowledgements
The authors are grateful to JeanLouis Le Roux for discussions and
 review input. Thanks to Ben NivenJenkins, JP Vasseur, and Loa
 Andersson for their comments.
+ review input. Thanks to Ben NivenJenkins, JP Vasseur, Loa Andersson,
+ and Anders Gavler for their comments. Thanks to Dave Allen for useful
+ discussion of the maths.
16. Intellectual Property Consideration
The IETF 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
this 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. Information
on the procedures with respect to rights in RFC documents can be