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]