Internet DRAFT - draft-mjsraman-pce-power-replic

draft-mjsraman-pce-power-replic



 



PCE Working Group                                          Shankar Raman
Internet-Draft                                Balaji Venkat Venkataswami
Intended Status: Experimental RFC                           Gaurav Raina
Expires: August 2013                                          IIT Madras
                                                       February 18, 2013


          Constructing power optimal P2MP TE-LSPs within an AS
                   draft-mjsraman-pce-power-replic-02


Abstract

   Power consumption in multicast replication operations is an area of
   concern and choosing suitable replication points that can decrease
   power consumption overall assumes importance. Multicast replication
   capacity is an attribute of every line card of major routers and
   multi-layer switches that support multicast in the core of an
   Internet Service Provider (ISP) or an enterprise network.  

   Currently multicast replication points on Point-to-Multipoint Traffic
   Engineering Label-Switched-Paths (P2MP TE-LSPs) consume power while
   delivering multiple output streams of data from a given input stream.
   The multicast distribution trees are constructed without any regard
   for a proper placement of the replication points and consequent
   optimal power consumption at these points. 

   This results in overloading certain routers while under-utilizing
   others. An optimal usage of these replication resources could
   substantially reduce power consumption on these routers. In this
   paper, we propose a mechanism by which P2MP TE-LSPs are constructed
   for carrying multicast traffic across multiple areas within a given
   AS. We propose that these LSPs be built by using the advertisements
   of the power-replication capacity ratio advertised by fine grained
   components such as multicast capable line-cards of routers and multi-
   layer switches deployed within an AS. 


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.

 


Shankar Raman et.al.      Expires August 2013                   [Page 1]

INTERNET DRAFT    Constructing Power Optimal P2MP-LSPs February 18, 2013


   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/1id-abstracts.html

   The list of Internet-Draft Shadow Directories can be accessed at
   http://www.ietf.org/shadow.html


Copyright and License Notice

   Copyright (c) 2013 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
   (http://trustee.ietf.org/license-info) in effect on the date of
   publication of this document. Please review these documents
   carefully, as they describe your rights and restrictions with respect
   to this document. Code Components extracted from this document must
   include Simplified BSD License text as described in Section 4.e of
   the Trust Legal Provisions and are provided without warranty as
   described in the Simplified BSD License.



Table of Contents

   1  Introduction  . . . . . . . . . . . . . . . . . . . . . . . . .  3
     1.1  Terminology . . . . . . . . . . . . . . . . . . . . . . . .  3
   2.  Methodology of the proposal  . . . . . . . . . . . . . . . . .  4
     2.1 Discussion of this scheme  . . . . . . . . . . . . . . . . .  6
     2.2 Power to available multicast replication capacity ratio in
         a TLV  . . . . . . . . . . . . . . . . . . . . . . . . . . .  8
   3 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
   3  Security Considerations . . . . . . . . . . . . . . . . . . . . 11
   4  IANA Considerations . . . . . . . . . . . . . . . . . . . . . . 11
   5  References  . . . . . . . . . . . . . . . . . . . . . . . . . . 11
     5.1  Normative References  . . . . . . . . . . . . . . . . . . . 11
     5.2  Informative References  . . . . . . . . . . . . . . . . . . 11
   Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 12




 


Shankar Raman et.al.      Expires August 2013                   [Page 2]

INTERNET DRAFT    Constructing Power Optimal P2MP-LSPs February 18, 2013


1  Introduction

   Multicast traffic across multiple areas within a given AS, may be
   carried using P2MP TE-LSPs. The traffic may be carried from a ingress
   Provider Edge (PE) router to several egress PEs, example in a
   multicast Virtual Private Network (MVPN) case. The autonomous system 
   (AS) may comprise of multiple areas involving a backbone area and
   several non-backbone areas connected to each other through the
   backbone. If several such multicast streams are to be carried in the
   AS, it would be most useful to have such P2MP TE-LSPs constructed
   such that they have optimal power to available replication capacity
   ratios on the routers' linecards that they traverse from source to
   destinations. The intent is to provide a solution whereby several
   such P2MP TE-LSPs can be laid out in such a way that the set of
   routers that replicate multicast traffic traversed by the P2MP TE-
   LSPs are most optimal in the utilization of the power provided to
   them given that there is sufficient replication capacity available.
   This we believe would essentially lead to a equilibrium of power to
   available replication capacity ratios amongst all routers in the
   topology which in turn would optimize and reduce the overall ratios
   for the AS.

   Each router and its respective linecards deployed in the AS have an
   advertised capability for replication. Most multi-layer switches and
   routers from vendors advertise in their respective data sheets a
   certain capability for replication for each type of linecard
   deployable on the box.  Replication consumes power and delivers
   multiple streams of data from a given input stream. It is status quo
   that P2MP (Point-to-Multipoint) Label Switched Paths are constructed
   without taking into account the power to available replication
   capacity ratios of such routers thus overloading certain routers
   while underutilizing the others. An optimal usage of these resources
   could reduce power consumption on these routers / multi-layer
   switches. This equilibrium could be arrived at by using a capability
   to advertize from each router a Traffic Engineering Database Link
   State Advertisement (TED-LSA) that carries the power to available
   replication capacity ratio of each of the said router's line cards,
   depending on the current utilization of its replication capacity and
   power consumption.

   This paper is organized as follows; In section 2, we deal with the
   scheme that we propose. In section 2.1, we discuss some examples of
   the scheme at work, and in section 3 we conclude with future areas of
   study that may be useful to undertake.

1.1  Terminology

   The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
 


Shankar Raman et.al.      Expires August 2013                   [Page 3]

INTERNET DRAFT    Constructing Power Optimal P2MP-LSPs February 18, 2013


   "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
   document are to be interpreted as described in RFC 2119 [RFC2119].


2.  Methodology of the proposal


   The key metric under consideration is the power consumed DIVIDED BY
   available replication capacity on each of the linecards of a router
   in the AS, which is eligible to be used as a node atop which
   multicast traffic can be carried. Once an advertisement about the
   said metric has been sent in the regular flooding process in Link
   State routing protocols such as OSPF-TE or ISIS-TE, it would be
   possible for a head-end router for a P2MP TE-LSP to compute the TE-
   LSP through the AS from the ingress PE to all egress PEs of that
   multicast stream  in such a way that the power to available
   replication capacity ratios at the replication points are minimal on
   that path. The Constrained Shortest Path First (CSPF) algorithm could
   be modified to compute the least cost power to available replication
   capacity ratio path and thus cause an equilibrium shift to be caused.
   This path would be supplied to the RSVP-TE component of the head-end
   and that would set up the path with appropriate labels. Once RSVP-TE
   establishes the path and traffic is carried across it, the reduced
   replication capacity of the routers in the P2MP TE-LSP path would be
   re-advertised again, which in turn would be useful for computation of
   the other paths from the instance that the replication capacity
   changed on these routers.

   Assume that the following router topology in the vicinity of the
   sender / senders is computed.

                   +----------------+
                  /                 V
                 /         +----> (R2) ------> (R3)<--(RcvrB)
                /         /                      \         |
               /         /                        \ +------+
              /         /                          \V
         (source/s)--->(R1)------> (R5) ------>  (R4)<-(RcvrA)
                        \                         /\       /
                         \             ----------+  \     /
                          \           /              \   /
                         (R6)----> (R7) --------> (R8)<-+

   Figure 1:  Topology within a given AS with coloring for Power-
   replication ratios



 


Shankar Raman et.al.      Expires August 2013                   [Page 4]

INTERNET DRAFT    Constructing Power Optimal P2MP-LSPs February 18, 2013


   In the above diagram you can see that the source/sources are
   connected using a multi homed connections to the same ISP through
   Routers R1 nd R2. Similarly there are two Receiver sites RcvrA and
   RcvrB that are multihomed to TWO Routers RcvrB to R3 and R4 and for
   RcvrA to R4 and R8 respectively.

                   +----------------+
                  /                 V
                 /         +----> (R2) ------> (R3)<--(RcvrB)
                /         /                      \         |
               /         /                        \ +------+
              /         /                          \V
         (source/s)...>(R1)------> (R5) ------>  (R4)<-(RcvrA)
                        .                         .\       /
                         .             ...........  \     /
                          .           .              \   /
                         (R6)....> (R7) ........> (R8)<-+

   Legend  : dotted lines represent path computed.

   Figure 2:  Instantiating an optimal power consuming distribution tree

   Given that the path calculation engine at the head-end R1 is given
   this topology and along with other TED-LSA packets the current power
   to available replication capacity ratios are advertised through the
   IGP-TE extensions to the head-end R1, the paths with the least power
   to available replication capacity ratios are computed and the paths
   setup from head-end PEs to the tail-end PEs where the recievers are
   connected. It is to be noted that the ratios computed for power to
   available replication capacity on the topology are examined and the
   replication points are setup on those routers that have the least
   power to available replication capacity ratio. If branching points
   are not required at certain points, these are anyways placed on least
   cost power ratio routers that are the next best location to setup a
   non-branching point. 

   Assume the following path is computed as per the least power to
   available replication capacity ratios. Paths are computed through R6,
   R7, R8, R4, and say the multicast stream occupies 4GB of traffic
   along this tree so constructed and the available capacity of these
   routers reduces to 6GB assuming all of them have a base capacity of
   10GB. Subsequent paths constructed would have to take into account
   the newly computed power to current replication capacity ratio in the
   topology and construct new P2MP TE-LSPs for multicast streams yet to
   come.

   Assume another 6GB worth of traffic is loaded onto this topology in
   terms of a multicast stream / multiple streams then the new path
 


Shankar Raman et.al.      Expires August 2013                   [Page 5]

INTERNET DRAFT    Constructing Power Optimal P2MP-LSPs February 18, 2013


   computed for these new streams would possibly utilize the same path
   as computed before. If the old streams reduce the replication
   capacity to an extent such that routers through which they pass can
   no longer be used since these routers' power to available replication
   capacity has become poor when compared to other paths then a
   different path may be computed from the ingress PE to the egress PEs
   in such a way as to avoid those routers which have such poor ratios.

   For example, assume R6, R7, R8 and R4 have exhausted their capacity,
   or guzzle more power as a result of them carrying the 4GB stream that
   was originally placed atop them. then a different path would be
   chosen as follows. The path followed as shown in the Figure is R2,R3
   and R4. Given that R4 is the only choice since it has connectivity to
   both Receivers, in this case the branch point is placed atop R3, one
   branch to get to RcvrB and the other to get to RcvrA through R4.
   Policy decisions could guide the placement in case of a tie. Here the
   the only choice has been to drive the end replication to RcvrA
   through R4 and RcvrB through R3 owing to topology constraints. 

   It is to be noted that the power consumed by the linecard is divided
   by the available replication capacity to arrive at a ratio and that
   ratio is assigned as a weight to all of the links ingressing on that
   linecard. It is possible that one might take a weighted average by
   dividing a weighted co-efficient sum by the weighted sum of ingress
   links on a linecard and the metrics so assigned be used as the metric
   for calculation.

                   ..................
                  .                 V
                 .         +----> (R2)........> (R3)<--(RcvrB)
                .         /                      .         |
               .         /                        . +------+
              .         /                          .V
         (source/s)--->(R1)-------> (R5) -------> (R4)<-(RcvrA)
                        \                         /\       /
                         \             ----------+  \     /
                          \           /              \   /
                         (R6)-----> (R7) ------->  (R8)<+

   Legend  : dotted lines represent path computed.

   Figure 3:  Instantiating a subsequent optimal power consuming
   distribution tree

2.1 Discussion of this scheme 

    It is to be noted that our scheme applies to centralized schemes of
   path calculations. What is being calculated is a tree of nodes that
 


Shankar Raman et.al.      Expires August 2013                   [Page 6]

INTERNET DRAFT    Constructing Power Optimal P2MP-LSPs February 18, 2013


   form a P2MP tree where each node can conceptualized as a router (read
   also multi-layer switches) and each edge the link connecting one or
   more ports on a line card to another linecard on a downstream router
   to carry multicast traffic from a source located at the head end
   ingress router to several receiver nodes connected to egress routers.
   We will call this calculated tree as a P2MP tree. The tree is
   calculated by the PCE in the head end / ingress router through which
   sources connect. The PCE calculates the intra-AS P2MP path (the
   literal P2MP TE-LSP within the AS) within that AS. 

   The calculated power to available replication capacity ratio is
   assigned to each of the ingress links on a linecard on a router en-
   route to egress links through which the multicast stream is
   replicated on the same router. Thus all ingress links to a router
   through a linecard are assigned the same metric as the power ratio so
   calculated. The egress links would in continuity connect to a unicast
   tunnel or another branch-point in the tunnel towards the receivers
   which are represented as the egress routers. The egress routers would
   in turn be replication points or direct connections to the actual
   receivers.  This method could be applied for multicast traffic to be
   transported through MVPNs. The method of egress routers' discovery is
   left to existing mechanisms. The primary input to the invention
   proposed is an ingress router and their respective egress routers.
   The other input to the construction of P2MP tree is the router level
   topology with the metrics for the power to available replication
   capacity ratio.

   It is to be noted that this CSPF calculation can be hastened in terms
   of time complexity by dividing the weights into equivalence classes.
   First we divide the nodes into graph colored nodes with the least
   ratio nodes marked as green as shown in the figure and given that
   there exists a path that is all green from source to egress PEs, one
   of such paths is chosen. If after coloring the nodes a path which is
   disconnected exists, we incrementally add the next best colored nodes
   to the graph to see if we a get a connected path from source to
   egresses. These steps are repeated until we find a connected path.
   This will hasten the algorithm to a conclusion rather than use a
   brute force method which may take inordinate amount of time. R4 being
   used in the 6GB case is an example of this. Because of topology
   restrictions the R4 node had to be chosen inspite of the fact that it
   is not green after carrying the 4GB stream.

   Routers may have step levels in which they increase power consumption
   when they additively are loaded with more large bandwidth consuming
   multicast streams. Calibrating these levels may be useful for
   implementing this scheme. It is possible that such calibrated
   thresholds can be used for advertising the power to available
   replication capacity ratios in the IGP-TE advertisements. This would
 


Shankar Raman et.al.      Expires August 2013                   [Page 7]

INTERNET DRAFT    Constructing Power Optimal P2MP-LSPs February 18, 2013


   be useful for bringing down the frequency of updates or
   advertisements from a line-card about its ratios. When power
   consumption meanders within a certain given interval these ratios
   need not be readvertised even if further multicast streams are added
   to it. The incentive is to recognize a linecard that does not
   drastically change power consumption even if large bandwidth streams
   are added onto it for replication and thus give it credit for its
   power optimal functioning. If a router tends to consume the highest
   level of power even when carrying low amounts of multicast streams
   and replicating them on its line card, it would automatically have a
   poor ratio when compared to a router that efficiently uses power when
   considering the replication capacity being used. The best case would
   be a low power consuming line-card or a router filled with such line
   cards that does not leave its power interval no matter how much ever
   replication capacity is sought to be used on it. But that would be an
   ideal condition but it is definitely an idealistic scenario towards
   which the router manufacturers should look at. 

   It is possible that several multicast streams may be aggregated onto
   a single P2MP-TE-LSP representing the given multicast tree that
   encompasses the union of all the egress PEs of the several multicast
   streams. The Ingress PE router is however common for all the
   multicast streams so covered. Aggregation of these several multicast
   streams from a given Ingress PE to several egress PEs is a common
   occurrence to save the amount of state in the core of the network. By
   aggregating these streams onto a single P2MP tree, it is possible to
   amortize the cost of replication amongst a particular set of ingress
   linecards / ports on those line cards while taking into account the
   current power consumption and replication capacity available at the
   time of computing the P2MP TE-LSP.

   The dynamic nature of the multicast tree and the egress PEs that join
   into it and leave it based on whether there are multicast listeners
   in that VPN site attached to the said egress PE/ PEs,  makes it
   important to position the replication points in such a way that there
   is maximum leverage on optimization in the ratios overall for the AS
   which are computed. When aggregating multiple multicast streams over
   a single P2MP TE-LSP it is important to keep this in mind.

   So the key point is to aggregate multiple streams with a set
   theoretical approach in mind so that there is maximum overlap of
   egress PEs for these streams and position these streams atop a P2MP
   TE-LSP in such a way that ratios are most optimal for that set of
   streams (with the overall AS power consumption in mind).

2.2 Power to available multicast replication capacity ratio in a TLV

   As per [RFC3630] the Link TLV can be used to carry this power to
 


Shankar Raman et.al.      Expires August 2013                   [Page 8]

INTERNET DRAFT    Constructing Power Optimal P2MP-LSPs February 18, 2013


   available multicast replication capacity ratio with an additional
   sub-TLV of the link TLV. The sub-type number 10 is recommended to be
   defined for this purpose.

   [RFC 3630] states in section 2.2.1 and we QUOTE ...

   2.2.1  Link TLV

   The Link TLV describes a single link.  It is constructed of a set of
   sub-TLVs.  There are no ordering requirements for the sub-TLVs.

   Only one Link TLV shall be carried in each LSA, allowing for fine
   granularity changes in topology.

   The Link TLV is type 2, and the length is variable.

   The following sub-TLVs of the Link TLV are defined:

         1 - Link type (1 octet)
         2 - Link ID (4 octets)
         3 - Local interface IP address (4 octets)
         4 - Remote interface IP address (4 octets)
         5 - Traffic engineering metric (4 octets)
         6 - Maximum bandwidth (4 octets)
         7 - Maximum reservable bandwidth (4 octets)
         8 - Unreserved bandwidth (32 octets)
         9 - Administrative group (4 octets)
        10 - Power-to-Multicast-replication-capacity (4 octets)

   This memo defines sub-Types 1 through 9.  See the IANA Considerations
   in [RFC3630] section for allocation of new sub-Types.

   The Link Type and Link ID sub-TLVs are mandatory, i.e., must appear
   exactly once.  All other sub-TLVs defined here may occur at most
   once.  These restrictions need not apply to future sub-TLVs.
   Unrecognized sub-TLVs are ignored.

   Various values below use the (32 bit) IEEE Floating Point format. For
   quick reference, this format is as follows:

   0                   1                   2                   3
   0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |S|    Exponent   |                  Fraction                   |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

   S is the sign, Exponent is the exponent base 2 in "excess 127"
   notation, and Fraction is the mantissa - 1, with an implied binary
 


Shankar Raman et.al.      Expires August 2013                   [Page 9]

INTERNET DRAFT    Constructing Power Optimal P2MP-LSPs February 18, 2013


   point in front of it.  Thus, the above represents the value:

   (-1)**(S) * 2**(Exponent-127) * (1 + Fraction)

   It is proposed that we use the Power-to-multicast-replication-
   capacity ratio as a 32 bit IEEE floating Point format field for the
   purpose of this document.


3 Conclusion

   Here we propose a scheme that takes into account the power to
   available replication capacity ratios as weights for the edges and
   compute a low cost power path for multicast replication. This scheme
   could be extended to inter-AS multicast streams or to inter-AS
   multicast streams where the multicast stream is sought to be carried
   over multiple ASes. This is an area of future study which would be
   most conducive in terms of bringing about optimal power usage and
   thus incentivising vendors to manufacture low power consuming
   equipment. Compelled to bring about radical change in the thinking
   relating to power consumption vendors manufacturing networking
   equipment will drive down power consumption since the scheme proposed
   chooses or gives priority to low power guzzling linecards.

























 


Shankar Raman et.al.      Expires August 2013                  [Page 10]

INTERNET DRAFT    Constructing Power Optimal P2MP-LSPs February 18, 2013


3  Security Considerations

   The security considerations for this proposal are the same as any NEW
   opaque LSA introduced in an IGP like OSPF, IS-IS.


4  IANA Considerations

   IANA would need to assign a NEW opaque LSA type to carry power and
   multicast replication capacity such that this information can be
   carried in the TE-LSAs within an AS.


5  References

5.1  Normative References


5.2  Informative References


              [1] G. Appenzeller, Sizing router buffers, Doctoral
              Thesis, Department of Electrical Engineering, Stanford
              University, 2005.  

              [2] A. P. Bianzino, C. Chaudet, D. Rossi and J. L.
              Rougier, A survey of green networking research, IEEE
              Communications and Surveys Tutorials, preprint.

              [3] J. Baliga, K. Hinton and R. S. Tucker, Energy
              consumption of the internet, Proc. of joint international
              conference on optical internet, June 2007, pp. 1993.

              [4] J. Chabarek, J. Sommers, P. Barford, C. Estan, D.
              Tsiang and S. Wright, Power awareness in network design
              and routing, Proc. of the IEEE INFOCOM 2008, April 2008,
              pp. 457-465.

              [5] M. Xia et. al., Greening the optical backbone network:
              A traffic engineering approach, IEEE ICC Proceedings, May
              2010, pp. 1995.

              [6] W. Lu and S. Sahni, Low-power TCAMs for very large
              forwarding tables, IEEE/ACM Transactions on Computer
              Networks, June 2010, vol. 18, no. 3, pp. 948-959.

              [7] B. Zhang, Routing Area Open Meeting, Proceedings of
              the IETF 81, Quebec, Canada, July 2011.
 


Shankar Raman et.al.      Expires August 2013                  [Page 11]

INTERNET DRAFT    Constructing Power Optimal P2MP-LSPs February 18, 2013


Authors' Addresses



   Shankar Raman
   Department of Computer Science and Engineering
   IIT Madras
   Chennai - 600036
   TamilNadu
   India

   EMail: mjsraman@cse.iitm.ac.in



   Balaji Venkat Venkataswami
   Department of Electrical Engineering
   IIT Madras
   Chennai - 600036
   TamilNadu
   India

   EMail: balajivenkat299@gmail.com



   Prof.Gaurav Raina
   Department of Electrical Engineering
   IIT Madras
   Chennai - 600036
   TamilNadu
   India

   EMail: gaurav@ee.iitm.ac.in

















Shankar Raman et.al.      Expires August 2013                  [Page 12]