Internet DRAFT - draft-hummel-mpls-n-square-investigations
draft-hummel-mpls-n-square-investigations
MPLS Working Group Heinrich Hummel,
Internet Draft Bernd Hoffmann
Expiration Date: December 2002 Siemens AG
June 2002
O(n**2) Investigations
draft-hummel-mpls-n-square-investigations-00.txt
Status of this Memo
This document is an Internet-Draft and is in full conformance with
all provisions of Section 10 of RFC2026.
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.
For potential updates to the above required-text see:
http://www.ietf.org/ietf/1id-guidelines.txt
Abstract
The O(n**2) problem is a well-known problem which occurs when overlay
network models are used, e.g. for building vpns. This draft compares
four different methods as to accomplish an effective full mesh
connectivity and shows precisely the amount of resource consumption
in each case - i.e. the consumption of states and labels.
Hummel June 2002 [Page 1]
O(n**2) Investigations Exp. Dec. 2002
1 Introduction and conclusion
The O(n**2) problem is a well-known problem which occurs when overlay
network models are used, e.g. for building VPNs. This draft compares
four different methods, (1),(2),(3)and (4), as to accomplish an
effective full mesh connectivity and shows PRECISELY the amount of
resource consumption in each case. Hereby the precise numbers of
consumed states and labels will be determined which is important
particularly when p2p LSPs and mp2p LSPs are to be compared.
Methods (1) and (2) can be applied based on existing MPLS-signalling.
Methods (3) and (4) need hierarchical LSPs (H-LSPs) and are described
/ propagated in [1] resp. [2].
Indeed, H-LSPs should not only be established manually by traffic
engineers, and advertised by routing protocols (see [3] where H-LSPs
are called FA-LSPs), but should also be established based on
signalling. It is hard to understand why a deeper nested label (in
the label stack) must never be signalled by means of a LABEL-TLV/
Label-object!
There are further (heavy) arguments in favor of signalled H-LSPs in
[1] and [2]. This draft however is focussed on providing resource
consumption figures - gained from a randomly shaped but huge sample
network. The essential findings: Yes, it becomes obvious that plain
merging LSPs do not overcome the O(n**2)-problem: The number of
states/labels in case of merging LSPs (method (2) )is not at all the
square root of the number of states/labels as consumed by p2p LSPs
(method (1) ).
Whereas hierarchical LSPs will overcome the O(n**2)-problem for the
core network. However they do not come for free. The price has to be
paid at the PEs. This price however can be substantially reduced by
merging H-LSPs.
2 Methods to establish an effective full mesh connectivity among n PEs
Arbitrarily meshed networks with N nodes and M links are investigated
on top of which n<N nodes (here called PEs) are to be interconnected
by means of MPLS-LSPs such that an effective full mesh connectivity
will be accomplished.
2.1 Method (1): Full mesh of p2p LSPs
Deploy a full mesh of n* (n-1) uni-directional p2p LSPs from any
PE to any PE.
Hummel June 2002 [Page 2]
O(n**2) Investigations Exp. Dec. 2002
2.2 Method (2): Full mesh by merging LSPs
Deploy O(n) mp2p merging LSPs which carry traffic from n-1 ingress
PEs to the remaining other egress PE. Each PE is n-1 times ingress
and once egress.
2.3 Method (3): Partial mesh of p2p LSPs + p2p H-LSPs
Deploy n-1 pairs of mutually inverse directed p2p LSPs which form a
contiguous partial mesh of tunnels between all n PEs.
Hereby two PEs are either neighbor-PEs if there is a pair of mutually
inverse directed LSPs between them, or are non-neighbor-PEs
otherwise.
Also deploy n(n-1)-2(n-1) = (n-1)(n-2) Hierarchical p2p LSPs (H-LSP)
between each non-neighboring pair of PEs. Hereby each p2p H-LSP is a
sequence of at least two "elementary" LSPs, concatenated by label-
switching at the endpoint nodes of these elementary LSPs. see [1].
H-LSPs shall be completely invisible to the core network (LABEL-
REQUEST and LABEL-MAPPING for establishing the H-LSPs shall be
forwarded by means of tunnels from PE to PE and shall not be seen by
any P-router). See [1].
2.4 Method (4): Partial mesh of p2p LSP + merging H-LSPs
Deploy n-1 pairs of mutually inverse directed p2p LSPs which form a
contiguous partial mesh of tunnels between all n PEs - just like in
method (3).
Also deploy O(n) mp2p H-LSPs. Hereby each mp2p H-LSP is a tree of
elementary LSPs, directed from n-1 ingress-PEs towards the remaining
other egress-PE. See [2].
3 Network with 200 PEs
In a sample network with 500 nodes (PEs, Ps) and 800 links there are
n=200 PEs to be interconnected by some full mesh MPLS tunneling
system. We determine the required amount of states /labels in this
section.
Note that no label is ever consumed/assigned by the ingress PE (with
respect to each hop the label is assigned by the downstream router).
Also note that no label (other than IPv4_EXPLICIT_NULL) is ever
consumed /assigned by the egress PE.
Hummel June 2002 [Page 3]
O(n**2) Investigations Exp. Dec. 2002
The currently available C++ -program only knows to count the number
of hops per tree and the number of hops adjacent to the root of that
tree. It can also sum up these numbers for a set of trees.
Therefore,it allows to determine the number of labels (=number of
NHLFEs) taken from the label spaces of the transit nodes inside the
trees. Unfortunately it does not determine the number of transit
nodes per tree,i.e. it does not determine the equally-sized number of
control states.
If you are only interested in the ultimate summary you may skip the
rest of this section 3 :-)
Method (1): Full mesh of p2p LSPs
Number of p2p LSP: 39 800 = n(n-1)
Number of router hops: 533 836 = x = counted
Number of states at ingress/egress-PEs: 79 600 = 2n(n-1)
Number of states/consumed labels at P-routers: 494 036 = x - n(n-1)
Method (2): Full mesh by merging LSPs
Number of mp2p LSP: 503 = z = counted
Number of router hops: 78 360 = y = counted
Number of states at ingress/egress-PEs: 40 000 = n**2
Number of consumed labels at P-routers: 77 857 = y - z
Method (3): Partial mesh of p2p LSPs + p2p H-LSPs
Part 1): Deploy n-1 pairs of mutually inverse elementary LSPs which form a
contiguous partial tunnel mesh between the n=100 PEs.
Number of elementary LSPs: 398 = 2(n-1)
Number of router hops: 802 = 2a; a= 401= counted
Elementary LSPs which form the partial tunnel mesh:
Number of states at ingress/egress-PEs: 796 = 4(n-1)
Number of states/consumed labels at P-routers: 404 = 2a - 2(n-1)
Hummel June 2002 [Page 4]
O(n**2) Investigations Exp. Dec. 2002
Part 2):
Additionally deploy n*(n-1) - 2*(n-1)= (n-1)*(n-2)= p2p H-LSPs
between the non-neighboring PEs in this partial tunnel mesh.
H-LSPs between non-neighboring PEs:
Number of p2p H-LSPs: 39 402 = (n-1)(n-2)
Number of PE-PE hops: 727 346 = b = counted 727 744 -2(n-1)
Number of states at ingress/egress-PEs: 78 804 = 2(n-1)(n-2)
Number of states/consumed labels
at transit PE-routers: 687 944 = b -(n-1)(n-2)
Method (4): Partial mesh of p2p LSP + merging H-LSPs
Part 1) : like part 1) of method (3).
Part 2) : Additionally deploy mp2p H-LSPs towards all (=n) egress-PEs.
Number of mp2p H-LSPs: 398 = d = counted, is by chance = 2(n-1)
Number of PE-PE hops: 39 800 = c = counted but had to become = n(n-1)
Number of states at ingress/egress-PEs: 40 000 = n**2
(note: this covers all PEs because each transit-PE is also ingress-PE !)
Number of consumed labels at transit PEs: 39 402 = c - d
4 Summary table
Evaluation overview - How many states /labels are consumed?
| Method | Method | Method | Method |
| (1) | (2) | (3) | (4) |
-----------------------------+---------+---------+---------+----------|
Elementary LSPs: | | | | |
States at ingress/egress PEs | 79 600 | 40 000 | 796 | 796 |
Labels at P- routers | 494 036 | 77 857 | 404 | 404 |
-----------------------------+---------+---------+---------+----------|
Hierarchical LSPs: | | | | |
States at ingress/egress PEs | 0 | 0 | 78 804 | 40 000 |
Labels at transit PE-routers | 0 | 0 |687 944 | 39 402 |
-----------------------------+---------+---------+---------+----------|
Please observe the immense savings at the P- routers in case method
(3) or (4) is used! Indeed, method (3) and method (4) solve the
Hummel June 2002 [Page 5]
O(n**2) Investigations Exp. Dec. 2002
O(n**2)-problem for the P-routers. These savings are specially
important because the core network may have to support many vpns.
Note that the PEs have to pay a price for these gains in the core:
Note that by using method (3) a much bigger price is to be paid than
by using method (4).
Conclusion:
The savings are worth the (minimal) efforts which are required for
method (3) and (4) and which are outlined in [1] and [2]
respectively.
5 References
[1] H.Hummel,J.Grimminger (Siemens AG):
Hierarchical LSP
draft-hummel-mpls-hierarchical-lsp-01.txt
[2] H.Hummel,J.Grimminger (Siemens AG):
Partially meshed base tunnels plus hierarchical mp2p tunnel sequence LSPs
draft-hummel-ppvpn-mp2p-tunnel-sequencing-00.txt
[3] K.Kompella (Juniper Networks): LSP Hierarchy with Generalized MPLS TE,
draft-ietf-mpls-lsp-hierarchy-04.txt
6 Authors' Addresses
Heinrich Hummel
Siemens AG
Hofmannstrasse 51
81379 Munich, Germany
Tel: +49 89 722 32057
Email: heinrich.hummel@icn.siemens.de
Bernd Hoffmann
Siemens AG
Hofmannstrasse 51
81379 Munich, Germany
Tel.+49 89 722 41530
Email: Bernd.Hoffmann@icn.siemens.de
Full Copyright Statement
"Copyright (C) The Internet Society (March 2000). All Rights
Reserved. This document and translations of it may be copied and
furnished to others, and derivative works that comment on or
otherwise explain it or assist in its implmentation may be prepared,
copied, published and distributed, in whole or in part, without
Hummel June 2002 [Page 6]
O(n**2) Investigations Exp. Dec. 2002
restriction of any kind, provided that the above copyright notice and
this paragraph are included on all such copies and derivative works.
However, this document itself may not be modified in any way, such as
by removing the copyright notice or references to the Internet
Society or other Internet organizations, except as needed for the
purpose of developing Internet standards in which case the procedures
for copyrights defined in the Internet Standards process must be
followed, or as required to translate it into languages other than
English.
The limited permissions granted above are perpetual and will not be
revoked by the Internet Society or its successors or assigns.
Hummel June 2002 [Page 7]
