idnits 2.17.1 draft-mjsraman-rtgwg-inter-as-psp-protect-02.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- No issues found here. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (January 29, 2013) is 4104 days in the past. Is this intentional? -- Found something which looks like a code comment -- if you have code sections in the document, please surround them with '' and '' lines. Checking references for intended status: None ---------------------------------------------------------------------------- -- Looks like a reference, but probably isn't: 'RFC2119' on line 217 Summary: 0 errors (**), 0 flaws (~~), 1 warning (==), 3 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 RTGWG Working Group Shankar Raman 3 Internet-Draft Balaji Venkat Venkataswami 4 Intended Status: Experimental RFC Gaurav Raina 5 Expires: August 2, 2013 Vasan Srini 6 IIT, Madras 7 January 29, 2013 9 Constructing inter-AS power shortest protection TE-LSPs using BGP 10 draft-mjsraman-rtgwg-inter-as-psp-protect-02 12 Abstract 14 In this paper, we propose a framework to build protection / backup 15 paths for power shortest primary inter-AS TE-LSPs. The primary path 16 is built within a framework to reduce the aggregate power consumption 17 of the Internet using a collaborative approach between Autonomous 18 Systems (AS). We identify the low-power paths among the AS and then 19 use Traffic Engineering (TE) techniques to route the packets along 20 the paths. Such low-power paths can be identified by using the 21 consumed-power-to-available-bandwidth (PWR) ratio as an additional 22 constraint in the Constrained Shortest Path First (CSPF) algorithm. 23 For re-routing the data traffic through these low-power paths, the 24 Inter-AS Traffic Engineered Label Switched Path (TE-LSP) that spans 25 multiple AS can be used. 27 Once the primary paths have been built we use the same techniques to 28 build backup power shortest paths in a similar manner except by 29 excluding the nodes (ASes) and links (between these ASes) that are 30 present in the primary path. This way the backup path does not 31 traverse any of the ASes or links between these ASes of the primary 32 path so constructed. 34 Extensions to the Border Gateway Protocol (BGP) can be used to 35 disseminate the PWR ratio metric among the AS thereby creating a 36 collaborative approach to reduce the power consumption. Since 37 calculating the low-power paths can be computationally intensive, a 38 graph-labeling heuristic is also proposed. This heuristic reduces the 39 computational complexity but may provide a sub-optimal low-power 40 path. The feasibility of our approaches is illustrated by applying 41 our algorithm to a subset of the Internet. The techniques proposed in 42 this paper for the Inter-AS power reduction require minimal 43 modifications to the existing features of the Internet. The proposed 44 techniques can be extended to other levels of Internet hierarchy, 45 such as Intra-AS paths, through suitable modifications. 47 Status of this Memo 49 This Internet-Draft is submitted to IETF in full conformance with the 50 provisions of BCP 78 and BCP 79. 52 Internet-Drafts are working documents of the Internet Engineering 53 Task Force (IETF), its areas, and its working groups. Note that 54 other groups may also distribute working documents as 55 Internet-Drafts. 57 Internet-Drafts are draft documents valid for a maximum of six months 58 and may be updated, replaced, or obsoleted by other documents at any 59 time. It is inappropriate to use Internet-Drafts as reference 60 material or to cite them other than as "work in progress." 62 The list of current Internet-Drafts can be accessed at 63 http://www.ietf.org/1id-abstracts.html 65 The list of Internet-Draft Shadow Directories can be accessed at 66 http://www.ietf.org/shadow.html 68 Copyright and License Notice 70 Copyright (c) 2012 IETF Trust and the persons identified as the 71 document authors. All rights reserved. 73 This document is subject to BCP 78 and the IETF Trust's Legal 74 Provisions Relating to IETF Documents 75 (http://trustee.ietf.org/license-info) in effect on the date of 76 publication of this document. Please review these documents 77 carefully, as they describe your rights and restrictions with respect 78 to this document. Code Components extracted from this document must 79 include Simplified BSD License text as described in Section 4.e of 80 the Trust Legal Provisions and are provided without warranty as 81 described in the Simplified BSD License. 83 Table of Contents 85 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 4 86 1.1 Low-power routers and switches . . . . . . . . . . . . . . . 4 87 1.2 Power reduction using routing and traffic engineering . . . 4 88 1.1 Terminology . . . . . . . . . . . . . . . . . . . . . . . . 5 89 2. Methodology . . . . . . . . . . . . . . . . . . . . . . . . . 6 90 2.1 Pre-requisites for the Proposed Method . . . . . . . . . . . 6 91 2.1.1 Constructing network topology using BGP strands . . . . 6 92 2.1.2 PWR ratio calculation . . . . . . . . . . . . . . . . . 7 93 2.1.2.1 Earlier method of computing numerator of PWR 94 ratio. . . . . . . . . . . . . . . . . . . . . . . . 9 95 2.1.3 Explicit routing using TE-LSPs . . . . . . . . . . . . . 10 96 2.2 LOW-POWER PATHS . . . . . . . . . . . . . . . . . . . . . . 11 97 2.2.0.1 Algorithm 1 ASBR low-power path algorithm . . . . . 12 98 2.2.0.2 Algorithm 2 PCE low-power path algorithm . . . . . . 12 99 2.2.1 Illustration . . . . . . . . . . . . . . . . . . . . . . 12 100 2.2.1.1 Backup path construction . . . . . . . . . . . . . . 13 101 2.2.3 Equivalence class with total ordering . . . . . . . . . 14 102 2.2.3.1 Algorithm 3 PCE low-power path algorithm with 103 graph labeling . . . . . . . . . . . . . . . . . . . 15 104 2.2.4 Illustration of graph labeling . . . . . . . . . . . . . 16 105 2.2.5 Moving traffic when the primary path fails . . . . . . . 17 106 2.3 Implementation notes and Discussion . . . . . . . . . . . . 17 107 2.4 Applicability within ASes within a single Admin Domain . . . 20 108 2.4.1 PWR_SESSION . . . . . . . . . . . . . . . . . . . . . . 20 109 2.5 Conclusion and Future Work . . . . . . . . . . . . . . . . . 21 110 2.5.1 Link and node disjoint Backup paths and power 111 constraints . . . . . . . . . . . . . . . . . . . . . . 21 112 2.6 Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 24 113 3 Security Considerations . . . . . . . . . . . . . . . . . . . . 25 114 4 IANA Considerations . . . . . . . . . . . . . . . . . . . . . . 25 115 5 References . . . . . . . . . . . . . . . . . . . . . . . . . . 25 116 5.1 Normative References . . . . . . . . . . . . . . . . . . . 25 117 5.2 Informative References . . . . . . . . . . . . . . . . . . 25 118 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 26 120 1 Introduction 122 Estimates of power consumption for the Internet predict a 300% 123 increase, as access speeds increase from 10 Mbps to 100 Mbps [3], 124 [8]. Access speeds are likely to increase as new video, voice and 125 gaming devices get added to the Internet. Various approaches have 126 been proposed to reduce the power consumption of the Internet such as 127 designing low-power routers and switches, and optimizing the network 128 topology using traffic engineering methods [2]. 130 1.1 Low-power routers and switches 132 Low-power router and switch design aim at reducing the power consumed 133 by hardware architectural components such as transmission link, 134 lookup tables and memory. In [4] it is shown that the router's link 135 power consumption can vary by 20 Watts between idle and traffic 136 scenarios. Hence the authors suggest having more line cards and 137 running them to capacity: operating the router at full throughput 138 will lead to less power per bit, and hence larger packet lengths will 139 consume lower power. The two important components in routers that 140 have received attention for high power consumption are buffers and 141 TCAMs. Buffers are built using dynamic RAM (DRAM) or static RAM 142 (SRAM). SRAMs are limited in size and consume more power, but have 143 low access times. Guido [1] states that a 40Gb/s line card would 144 require more than 300 SRAM chips and consume 2:5kW. DRAM access times 145 prevent them from being used on high speed line cards. Sometimes the 146 buffering of packets in DRAM is done at the back end, while SRAM is 147 used at the front end for fast data access. But these schemes cannot 148 scale with increasing line speeds. Some variants of TCAMs have been 149 proposed for increasing line speeds and for reduced power consumption 150 [7]. 152 1.2 Power reduction using routing and traffic engineering 154 At the Internet level, creating a topology that allows route 155 adaptation, capacity scaling and power-aware service rate tuning, 156 will reduce power consumption. In [8] the author has proposed a 157 technique to traffic engineer the data packets in such a way that the 158 link capacity between routers is optimized. Links which are not 159 utilized are moved to the idle state. Power consumption can be 160 reduced by trading off performance related measures like latency. For 161 example, power savings while switching from 1 Gbps to 100 Mbps is 162 approximately 4 W and from 100 Mbps to 10 Mbps around 0:1 Watts. 163 Hence instead of operating at 1 Gbps the link speed could be reduced 164 to a lower bandwidth under certain conditions for reduced power 165 consumption. 167 Multi layer traffic engineering based methods make use of parameters 168 such as resource usage, bandwidth, throughput and QoS measures, for 169 power reduction. In [6] an approach for reducing Intra-AS power 170 consumption for optical networks that uses Djikstra's shortest path 171 algorithm is proposed. The input to this method assumes the existence 172 of a network topology using which an auxiliary graph is constructed. 173 Power optimization is done on the auxiliary graph and traffic is 174 routed through the low-power links. However, the algorithm expects 175 the topology to be available for getting the auxiliary graph. This 176 topology is easy to obtain for Intra-AS scenario, but not for Inter- 177 AS cases. In our approach, we propose a collaborative approach by AS 178 in power reduction and also methods to construct backup power paths 179 for the primary paths so constructed. The core of the Internet at the 180 Inter-AS level, uses the Multi-Protocol Label Switching (MPLS) 181 technology. MPLS label switched paths that traverse multiple AS carry 182 traffic from a head-end to a tail-end. The AS use the Border Gateway 183 Protocol (BGP) for exchanging routing and topology related 184 information. One of the attributes of BGP namely, AS-PATH-INFO is 185 used to derive the topology of the Internet at the AS level. The CSPF 186 algorithm is run on this AS level topology with the consumed-power- 187 to-available-bandwidth (PWR) ratio as a constraint, to determine the 188 low-power path from the head-end to the tail-end. The PWR ratio can 189 be exchanged among the collaborating AS using BGP. Explicit routing 190 can be achieved between the head-end and the tail-end through the 191 low-power paths connecting the AS using the Inter-AS Traffic 192 Engineered Label Switched Path (TE-LSP) that span multiple AS. 194 Calculation of such low-power paths can be computationally intensive 195 and hence certain heuristics may be needed to reduce the computation 196 time. A graph-labeling heuristic is proposed to reduce the 197 computation time, which may lead to sub-optimal low-power paths. We 198 illustrate our approaches by applying it to a subset of the Internet 199 topology. We then indicate how backup paths can be constructed by 200 avoiding links and nodes in the primary path using both the brute 201 force method and graph-labeling method. 203 The rest of the paper is organized as follows: In Section 2, we 204 discuss in detail the pre-requisites for the algorithm. Section 2.2 205 introduces the proposed technique which uses the CSPF algorithm to 206 calculate the low-power primary and backup paths. We also show that 207 by using a graph-labeling technique, we can reduce the computational 208 complexity of the low-power path algorithm, but may obtain a sub- 209 optimal low-power path. In Section 2.3, we discuss the implementation 210 issues. We present our conclusion and future work in Section 2.4. 212 1.1 Terminology 214 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 215 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 216 document are to be interpreted as described in RFC 2119 [RFC2119]. 218 2. Methodology 220 2.1 Pre-requisites for the Proposed Method 222 In this section we discuss the pre-requisites for the implementation 223 of the proposed scheme. 225 2.1.1 Constructing network topology using BGP strands 227 The Inter-AS topology can be modeled as a directed graph G = (V; E; 228 f) where the vertices (V) are mapped to AS and the edges (E) map the 229 link that connect the neighboring AS. The direction (f) on the edge, 230 represents the data flow from the head-end to the tail-end AS. To 231 obtain the Inter-AS topology, the approach proposed in [5] is used. 232 In this approach, it is shown that a sub-graph of the Internet 233 topology, can be obtained by collecting several prefix updates in 234 BGP. This is illustrated in Figure 1 which shows the different graph 235 strands of AS that are recorded from the BGP packets. Each vertex in 236 this graph is assigned a weight according to the consumed-power-to- 237 available-bandwidth (PWR) ratio of the AS, as seen by an Autonomous 238 System Border Router (ASBR) that acts as an entry point to the AS. 239 Figure 2 shows the strands merged together to form the topology sub- 240 graph. In this figure, the weight of the vertices are mapped to the 241 ingress edges. A reference AS level topology derived from 100 strands 242 of AS-PATH-INFO received by an AS in the Internet is presented in 243 Figure 3 in [9]. 245 0.2 0.05 0.1 246 (A) ----> (B) ----> (D) 248 0.1 0.03 0.2 249 (D) ----> (G) ----> (H) 251 0.03 0.5 0.3 252 (G) ----> (E) ----> (X) 254 0.5 0.5 0.5 0.1 255 (C) ----> (B) ----> (H) ----> (X) 257 0.05 0.5 0.3 258 (B) ----> (E) ----> (X) 260 Figure 1: Different strands obtained from BGP updates, where vertices 261 A,B,C,D and G represent the head-end AS. D,H and X form the tail-end 262 AS. The vertex weights refer to the PWR ratio of the AS, and the 263 direction of the link shows the next AS hop. 265 0.5 266 (C) +----------------+ 267 0.5| / | 268 | / | 269 0.05 V/ 0.1 0.03 0.2 V 270 (A)--->(B)--->(D)--->(G)--->(H) 271 | | | 272 | 0.5| | 0.1 273 | V V 274 +----------->(E)--->(X) 275 0.5 0.3 277 Figure 2:Combining the strands to get the topology of the Internet. 278 The PWR ratio is mapped to the the ingress link of the ASBR and not 279 to the AS. 281 2.1.2 PWR ratio calculation 283 In the topology sub-graph, each AS is expected to share its PWR 284 ratio. In order to calculate this ratio we need to calculate the 285 consumed power in the AS and the maximum bandwidth available with an 286 ASBR. 288 In this proposal each AS is expected to share its PWR ratio from as 289 many ASBRs (Autonomous System Border Routers) that it has. 290 Intuitively in order to calculate this ratio we need to calculate the 291 consumed power representative of the AS and the maximum bandwidth 292 available with an ASBR on its egress links into the AS. The entry 293 point to the AS is through the ASBRs that advertise the prefixes 294 reachable through the AS. Hence the numerator of the PWR ratio is 295 calculated for the AS at each ingress ASBR. We first obtain the 296 summation of power consumed at the Provider (P) and the Provider Edge 297 (PE) routers within an AS. The numerator of the PWR ratio is 298 calculated by summing up the consumed power of all the routers to be 299 taken into account and then dividing this sum by the number of 300 routers. A more intuitive approach would be to use a weighted average 301 method by assigning routers to categories and having appropriate co- 302 efficients for each of these categories, thus arriving at a weighted 303 average which is more accurate. One of these alternatives can be used 304 to arrive at the numerator of the PWR ratio. Yet another alternative 305 would have been to sum up the total consumed power of all routers in 306 the AS and represent that as the numerator of the PWR ratio. 308 This average consumed power is divided by the maximum bandwidth 309 available at each of the ASBR's egress link. This step is necessary 310 as the requested bandwidth for any path from the head-end to the 311 tail-end using the ASBR is limited by the bandwidth available in the 312 ASBR's egress links. The highest available bandwidth amongst the 313 egress links of the ASBR is used as the denominator in the PWR ratio 314 computation. If the entry point to the AS is through a different ASBR 315 then the PWR ratio assigned to the ingress link of the ASBR might 316 vary. Hence, an head-end AS might see different PWR ratios for an 317 intermediate AS, if the intermediate AS has different ASBRs as its 318 entry point. 320 The PWR ratio must be computed and disbursed much ahead of time 321 before the Inter-AS TE-LSP explicit path or route is computed using 322 the CSPF algorithm. The correctness of this ratio is of importance to 323 compute the Inter-AS TE-LSP route through the green AS. If the entry 324 point to the AS is through a different ASBR then the PWR ratio 325 assigned to the ingress link of the ASBR might vary. Hence, an head- 326 end AS might see different PWR ratios for an intermediate AS, if the 327 intermediate AS has different ASBRs as its entry point. 329 We now illustrate the PWR ratio calculation. Consider an AS X which 330 is one of the AS in the vicinity of another AS Y . Let this ASBR of X 331 have 3 egress links into X denoted as E(1), E(2) and E(3), and 2 332 ingress links labeled I(1) and I(2). We now calculate the PWR ratio 333 for I(1) and I(2). Assume that the routers in X have average consumed 334 power of 200K Watts per hour. From figure 4 we can calculate the PWR 335 ratio for I(1) and I(2) as 200K Watts / (60 * 60 * 1.5 Gigb = 3.7037 336 * (10 raised to -8) We could scale this to 0.37087 by multiplying 337 with a base value of 10 raised to the 7th power. 339 .__________________ 340 ( 341 ( E(1) 342 \ ( +--------->(Core router) 343 \ +-------+ / 1Gb 344 +------>| |/ E(2) 345 200KW / (60*60*1.5Gb) | ASBR |------------>(Core router) 346 +------>| of |\ 1Gb 347 / | AS 100| \ 348 / +-------+ \ E(3) 349 ( +-------->(Core router) 350 ( 1.5Gb 351 .__________________ 353 Figure 4:Calculation of PWR ratio by an ASBR associated with an AS. 354 The I represents ingress links and E represents egress links. 200KW 355 is the average consumed power in the AS. 1.5Gb is the maximum 356 available bandwidth of the egress link in an ASBR. 358 Note that this ratio is actually a mapping function that is defined 359 for each of the ingress links of the ASBR associated with an AS. For 360 the head-end AS this mapping function does not exist as there is no 361 ingress link. The PWR ratio can then be advertised to the other 362 neighboring AS using the control plane through BGP extensions. BGP 363 ensures that the information is percolated to other AS beyond the 364 immediate neighbors. On receipt of these power metrics to the AS at 365 the far-ends of the Internet, the overall AS level PWR ratio based 366 Internet topology can be constructed. This view of the Internet is 367 available with each of the routers without using any other complex 368 discovery mechanism. Some sample link weights shown in Figure 2 is 369 obtained by using such a mapping function on the ingress links. 371 2.1.2.1 Earlier method of computing numerator of PWR ratio. 373 Earlier in the previous versions of this document in order to 374 calculate this PWR ratio we needed to calculate the available power 375 and the maximum bandwidth available with an ASBR. The entry point to 376 the AS is through ASBRs that advertise the prefixes reachable through 377 the AS. Hence, the numerator of the PWR ratio is calculated for the 378 AS at each ingress ASBR. We first obtained the summation of power 379 consumed at the major Provider (P) and Provider Edge (PE) routers 380 within an AS. The average available power is obtained by subtracting 381 the consumed power from the maximum power rating and summing the 382 values for all the routers and then dividing the result by the number 383 of routers. As an alternative, one could use a weighted average for 384 more accuracy depending on the category of the router advertising the 385 consumed power. Yet another alternative is to take the average or sum 386 of the maximum power rating of all the routers within an AS without 387 taking into account the consumed power. One of these alternatives was 388 chosen to calculate the numerator of the PWR ratio. 390 Intuition however drives us towards consumed power as a better 391 numerator since the lesser the power consumed the lesser the 392 numerator and hence lesser the ratio if enough bandwidth is available 393 at the ingress ASBR. The amount of consumed power per bit of 394 information ought to be low for the shortest path to work out 395 properly. One more aspect is that lesser the power consumed per 396 available bit of bandwidth it could be a sign that routers are more 397 optimal in their power consumption as they take on more traffic. This 398 is a very crucial point to be considered. 400 2.1.3 Explicit routing using TE-LSPs 402 We assume that the head-end and the tail-end may reside in different 403 AS and the path is along multiple intervening AS. The way to generate 404 this path is by using Traffic Engineered Label Switched Paths (TE- 405 LSPs). TE-LSPs can influence the exact path (at the AS level) that 406 the traffic will pass through. This path can then be realized by 407 providing these set of low-power consuming AS to a protocol like 408 Resource Reservation Protocol (RSVP). RSVP-TE then creates TE-LSPs or 409 tunnels, using its label assigning procedure. The routers use these 410 low-power paths created by the explicit routing method rather than 411 using the conventional shortest path to the destination. By this way, 412 we can influence exclusion of a number of high power AS on the way 413 from the head-end to the tail-end AS. For example, the dotted line in 414 Figure 5 represents the explicit route that is chosen by making use 415 of such TE-LSPs from head-end AS A to the tail-end AS X. Note that if 416 number of hop was the metric used by CSPF, then the route chosen is 417 the path with 3 hops. 419 0.5 420 (C) +----------------+ 421 0.5| / | 422 | / | 423 0.05 V/ 0.1 0.03 0.2 V 424 (A)...>(B)...>(D)...>(G)...>(H) 425 | | . 426 | 0.5| . 0.1 427 | V V 428 +----------->(E)--->(X) 429 0.5 0.3 431 Figure 5:Low-power path is represented by the dotted lines. This low- 432 power path has a longer number of hops than the conventional shortest 433 path. 435 2.2 LOW-POWER PATHS 437 In this section we present the low-power path algorithm. The 438 algorithm consists of two sub-algorithms: the first algorithm is 439 executed by all the ASBRs in the network and the second by all the 440 Path Computation Elements (PCEs) in their respective AS. The 441 algorithms for the ASBRs and PCEs are given as Algorithm 1, 2 and 3. 443 2.2.0.1 Algorithm 1 ASBR low-power path algorithm 445 Require: Weighted Topology Graph T=(AS, E, f) 447 1: Begin 448 2: if ROUTER == ASBR then 449 3: /* As part of IGP-TE */ 450 4: Trigger exchange of available bandwidth on bandwidth change, 451 to the AS internal neighbors; 452 5: BEGIN PARALLEL PROCESS 1 453 6: while PWR ratio changes do 454 7: Assign the PWR ratio to the Ingress links; 455 8: Exchange the PWR ratio with its external neighbors; 456 9: Exchange the PWR ratio with AS's (internal) ASBRs; 457 10: end while 458 11: END PARALLEL PROCESS 1 459 ,br 12: BEGIN PARALLEL PROCESS 2 460 13: while RSVP packets arrive do 461 14: Send and Receive TE-LSP reservations in the explicit path; 462 15: Update routing table with labels for TE-LSP; 463 16: end while 464 17: END PARALLEL PROCESS 2 465 18: end if 466 19: End 468 2.2.0.2 Algorithm 2 PCE low-power path algorithm 469 Require: Weighted Topology Graph T=(AS, E, f) 470 Require: Source and Destination for Inter-AS TE LSP with sufficient 471 bandwidth 472 1: Begin 473 2: if ROUTER == PCE then 474 3: Calculate the shortest paths from the head-end to the 475 tail-end using CSPF with PWR ratio as the metric; 476 4: if no path available then 477 5: Signal error; 478 6: end if 479 7: if path exists then 480 8: Send explicit path to head-end to construct path; 481 9: end if 482 10: Continue passively listening to BGP updates to update 483 T=(AS, E, f); 484 11: end if 485 12: End 487 2.2.1 Illustration 489 We now illustrate the proposed technique with a simple example. 491 Consider the AS level topology sub-graph shown in Figure 5 492 constructed using the strands shown in Figure 1. The PWR ratio 493 calculated at an ASBR which represents the metric for the AS is 494 assigned to the ingress link. For example, AS H has two edges coming 495 into it: one from B and the other from G. Note that the power metrics 496 for the two strands are different as G to H is lower than that of B 497 to H. This means that the lower power metric into H is better if the 498 path from G to H is chosen rather than the one from B to H. This is 499 illustrated in the Figure 5 using dotted lines. To construct a path 500 with A as the head-end AS and X as the tail-end AS, from the AS level 501 topology we see that the path A, B, H, X and A, B, E, X have the 502 shortest number of hops. However by using CSPF with the PWR ratio 503 metric as the constraint, we see that the path A, B, D, G, H, X is 504 power efficient. The routing choice will however be based on the 505 reservation of the bandwidth on this path. Given that available 506 bandwidth exists to setup a TE-LSP, the explicit path A, B, D, G, H, 507 X is chosen. The Resource Reservation Protocol (RSVP) adheres to its 508 usual operation and tries to setup a path. If bandwidth is not 509 available in the low-power path thus calculated, then we may fall 510 back to other paths like A, B, H, X or A, B, E, X provided there is 511 available bandwidth in these paths. The low-power path algorithm 512 given as Algorithm 2 is executed by the PCE. Algorithm 1 prepares the 513 topology and feeds it as input to the PCE as a weighted topology 514 graph. Using the CSPF algorithm to calculate a route from a source to 515 destination could be time consuming for a large networks. But the 516 topology is dynamically updated and hence the computation of the 517 shortest paths can be triggered based on need. We later give a 518 heuristic method based on graph-labeling that reduces the computation 519 time but could trade-off the optimal low-power path. 521 2.2.1.1 Backup path construction 523 Assume there is a requirement to construct one or more backup paths 524 that excludes all nodes and links in the primary path as constructed 525 above. That is none of the nodes and links in the primary path 526 constructed should be present in the backup path to be constructed. 528 This is only possible to the extent possible since there may not be 529 available paths that are completely disjoint node and link wise from 530 the primary path previously constructed. In that case only the 531 minimum of the originally used links and nodes in the primary path 532 should be included in the backup path. That is if it is not possible 533 to construct a completely node and link disjoint path for the backup 534 path, then only the necessary nodes and links from the primary path 535 should be included in the backup path. 537 In the below figure the path from A to X was constructed with the 538 primary path going through A,B,D,G,H and X. For the backup path there 539 exist no other path power shortest wise other than A,B,E,X. If we 540 were to think of the next Power shortest path through A,B,H,X it 541 includes A->B and H->X which are members of the primary path as well. 542 Though the A,B,H and X path have shorter power than the A,B,E,X path 543 the number of links included from the primary path for the former are 544 2 while the latter has only one. This would advice us to choose the 545 latter since it has only one link and nodes (A->B) that coincide with 546 the primary path. Here the * dotted line shows the backup path 547 computed. 549 It is possible to request for more than one backup path to be 550 constructed and section 2.2.3 would provide a better time complexity 551 algorithm to do the same. Even for the first backup path the 552 equivalence class heuristic would be a better choice. 554 0.5 555 (C) +----------------+ 556 0.5| / | 557 | / | 558 0.05 V/ 0.1 0.03 0.2 V 559 (A)...>(B)...>(D)...>(G)...>(H) 560 * | . 561 * 0.5| . 0.1 562 * V V 563 +***********>(E)***>(X) 564 0.5 0.3 566 2.2.3 Equivalence class with total ordering 568 The heuristic is based on avoiding high PWR ratios. The approach 569 partitions the weighted links into equivalence classes based on a 570 range of PWR values. For each partition a labeling is applied such 571 that each link in the partition has the same label. A total ordering 572 relationship is then defined on the equivalence class. The heuristic 573 then starts including partitions with minimum label value iteratively 574 until we get a connected component, which includes the head-end and 575 tail-end AS. We apply the CSPF algorithm with the weights as label 576 values on this sub-graph to obtain the low-power path. The modified 577 algorithm which uses this scheme is given in Algorithm 3. It should 578 be noted that this algorithm could provide sub-optimal power paths as 579 the intermediate steps carry incomplete Internet topology 580 information. 582 2.2.3.1 Algorithm 3 PCE low-power path algorithm with graph labeling 583 Require: Weighted Topology Graph T=(AS, E, f) 584 Require: Source and Destination for Inter-AS TE LSP with 585 sufficient bandwidth 586 1: Begin 587 2: if ROUTER == PCE then 588 3: Group the links into N partitions with a label for 589 each partition depending on the PWR ratio 590 4: Sort the labels in ascending order. 591 5: repeat 592 6: Include the links that have the least label value; 593 7: Remove the partition with this label; 594 8: until there is a path from the head-end to tail-end AS 595 9: Calculate the low-power path using labels from the 596 head-end to the tail-end using CSPF ; 597 10: if no path available then 598 11: Signal error; 599 12: end if 600 13: if path exists then 601 14: Send explicit path to head-end to construct path; 602 15: end if 603 15.1 if backup path needs to be constructed then 604 15.2 Repeat 3 to 15 after excluding the links and nodes in 605 15.3 the primary path constructed, and by including next 606 15.3.1 available label grade if necessary. 607 15.4 end if 608 15.5 if no path exists then add the least power links and 609 15.6 nodes in the primary path back into the graph and repeat 610 15.7 the process. 611 15.8 end if 612 16: Continue passively listening to BGP updates to 613 update T=(AS, E); 614 17: end if 615 18: End 616 +------(1245)-----+ 617 / G / \G 618 / / Y \ 619 V / Y \ 620 (1339) + (6785)<------(1377)----+ 621 | | | / | 622 | G | G | + G V R 623 | | V V (2485) 624 V | (1006) (3426)--+ | 625 (34234) | Y | G | | | R 626 | | V V | V 627 | G | (11229) (4563) | (5677) 628 V | Y | | V | R 629 (23411) | V Y +-->(7786)<-+ 630 | +-->(1485)<--------/ | 631 | Y | | R 632 | V V 633 | (15467) (8298) 634 | G G | | R 635 | | | 636 | V V 637 +--------->(16578)<-------(9732) 639 Figure 6:Application of the graph-labeling heuristic. We consider 3 640 labels "G" < "Y" < "R". Using algorithm 3 the "G" path from the head- 641 end AS 1245 to the tail-end AS 16578 is chosen in the first 642 iteration. 644 2.2.4 Illustration of graph labeling 646 We briefly illustrate the graph-labeling algorithm using Figure 6. In 647 this diagram we have categorized the links into three partitions 648 based on the PWR ratio. PWR ratio less than 0:1 are labeled as G, 649 between 0:1 to 0:3 are labeled as Y and the rest as R. The total 650 ordering is defined as G < Y < R, where the G links have low PWR 651 ratios than the Y links. The path could be established through the AS 652 that have G as the ingress link; the path being 1245, 1339, 34234, 653 23411 and 16578. 655 Once the primary path is constructed then the backup paths may be 656 constructed by excluding to the maximum extent possible the nodes 657 (ASes) and the links (links between ASes) of the primary path from 658 the backup paths so constructed. The links and nodes of the primary 659 path are excluded first. The graph heuristic algorithm is run again. 660 If the path is not available the least power consuming links in the 661 primary path are added back and the construction method repeated 662 again and again till a backup path is constructed. 664 +------(1245)-----+ 665 / G / \G 666 / / Y(*) \ 667 V / Y \ 668 (1339) + (6785)<------(1377)----+ 669 | | | / | 670 | G | G | + G V R 671 | | V V (2485) 672 V | (1006) (3426)--+ | 673 (34234) | Y | G | | | R 674 | | V V | V 675 | G | (11229) (4563) | (5677) 676 V | Y | | V | R 677 (23411) | V Y +-->(7786)<-+ 678 | +-->(1485)<--------/ | 679 | (*)Y | | R 680 | V V 681 | (15467) (8298) 682 | G (*)G | | R 683 | | | 684 | V V 685 +--------->(16578)<-------(9732) 687 In the example given above there exist no paths that are GREEN all 688 the way for a backup path as it is in the primary path. So we choose 689 the links having YELLOW as the next category to be included. So the 690 backup path would be from 1245, 1485, 15467 and 16578. This is best 691 secondary / backup path with shortest number of hops that can be 692 constructed with a combination of the GREEN and YELLOW category 693 links. The path is marked by (*) against the label for better 694 illustration. 696 It is possible that more than one backup path may be required to be 697 constructed. In that case the process is repeated (through 698 iterations) to construct the required number of backup paths. 700 2.2.5 Moving traffic when the primary path fails 702 The regular methods of switching traffic from the primary path to the 703 backup path is followed when the primary path fails. This is subject 704 to the regular methods proposed by other documents in MPLS-TE in the 705 ietf. 707 2.3 Implementation notes and Discussion 709 In this section we present some notes on feasibility of 710 implementation of our scheme in a live network. First, the requested 711 bandwidth should be available on the low-power path, but the CSPF 712 algorithm is run with multiple constraints, one of which is the 713 bandwidth requirement for the flows to be transported through the TE- 714 LSP. The PWR ratio can then be applied to the available paths thus 715 computing the low-power paths. Second, as we are using traffic 716 engineering with link state routing protocols, there is a reliable 717 flooding process that are triggered when updates about the change in 718 characteristic arise. We propose addition of some attributes with no 719 change to the protocol implementation. There may be a time lag when 720 the far ends of the Internet receive the attribute and the time it 721 originated. This however cannot be avoided as with other attributes 722 and metrics. 724 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 725 +-------------------------------------------------------------+ 726 | Owning 32 bit Autonomous System Number | 727 +-------------------------------------------------------------+ 728 | Other 32 bit Autonomous System Number | 729 +-------------------------------------------------------------+ 730 | PWR Ratio for the AS | 731 +-------------------------------------------------------------+ 732 | Advertising ASBR's IP router ID | 733 +-------------------------------------------------------------+ 734 | Peer ASBR's IP router ID | 735 +-------------------------------------------------------------+ 736 | 64 bit sequence number for restarts, aging | 737 | and comparison of current PWR Ratio. | 738 +-------------------------------------------------------------+ 740 Figure 7: Proposed PDU format with an added attribute for AS-PATH- 741 POWER-METRIC 743 The additions to the above Attribute have been added to optimize and 744 correctly correlate the connecting ASes and the inter-AS links among 745 them. For the traffic direction into the Advertising AS the above 746 information will be easier to correlate than the previous version 747 which did not advertise the peer AS which had the ingress links into 748 the advertising Router. 750 In MPLS-TE when the TE metrics are modified, there is a reliable 751 flooding process within an Interior Gateway Protocol (IGP). Such 752 triggered updates apply to the PWR ratio as well. The proposed PWR 753 ratio is advertised to the neighboring AS and the information 754 percolated to all the AS, in a AS-PATH-POWER-METRIC attribute. This 755 attribute can be implemented as shown in Figure 7. The frequency of 756 the updates for this attribute should be fixed to avoid network 757 flooding. 759 The AS-PATH-POWER-METRIC for each ASBR is calculated, and advertised 760 as the PWR ratio for the AS. This AS-PATH-POWER-METRIC is filled into 761 the appropriate transitive non-discretionary attribute and inserted 762 into a unique vector for a set of prefixes advertised from the AS. 763 Such advertised prefixes may have originated from the AS or be the 764 transit prefixes. The filled vector is sent to the ASBR of the 765 neighboring AS and the information propagates to all the ASBRs. If 766 the elements denoting AS in a vector of AS-PATH-INFO is not the same 767 as the ones that need to be advertised in a AS-PATH-POWER-METRIC, 768 then a suitable subset of AS-PATH-POWER-METRIC is identified and sent 769 in the BGP updates. A vector of size 1 also can be employed if the AS 770 in question is the only one for which PWR ratio has changed in the 771 originating AS. The collation can be done depending on availability 772 of such metrics and their mapping to a valid AS-PATH-INFO metric. 774 The power consumed by each router may fluctuate over short time 775 intervals. In order to dampen these fluctuations which can cause 776 unnecessary updates, power can be measured when falling within 777 intervals of suitable size (say a range of values). This is as 778 opposed to measuring power as a discrete quantity. This method of 779 power measurement reduces the frequency of triggered updates from the 780 routers due to power change. 782 0.1 0.2 0.1 783 (A) ---> (B) ---> (D) 785 0.1 0.2 0.02 0.2 786 (A) ---> (C) ---> (E) ---> (D) 788 0.1 0.2 789 (D) ---> (X) 791 Figure 8: Example of strands where more than one PWR ratio is 792 advertised by "D" 794 0.2 0.1 0.2 795 (A).....>(B).....>(D).....>(X) 796 | ^ 797 |0.2 0.02 | 0.2 798 +--->(C)-------->(E) 800 Figure 9:Choice of low-power path derived using the algorithm which 801 uses lower value of the ingress link but through the same AS 803 A use case of multiple ASBRs advertising differing PWR ratio shows 804 that an AS may be seen as green through one ingress link and not 805 through the other. Consider the case of multiple ASBRs that belong to 806 the same AS, advertising PWR ratios that differ. This could lead to 807 power values that belong to different classes of ratios with many 808 intervening classes in between. These advertised PWR ratios could 809 lead to one ASBR being preferred over the other thus taking a 810 different path from head-end to tail-end. This also entails that 811 there may be multiple paths to the AS through these different ASBRs. 813 Consider Figure 8 which shows a set of strands that derive a topology 814 as in Figure 9. Here D is reachable via two paths but the PWR ratios 815 differ. This illustrates the case where the better metric wins out. 816 The average power consumed would not have an effect but the bandwidth 817 available on these ASBR egress links would definitely influence the 818 path. 820 2.4 Applicability within ASes within a single Admin Domain 822 As per [draft-ietf-idr-aigp] there are deployments in which a single 823 administration runs a network which has been sub-divided into 824 multiple, contiguous ASes, each running BGP. There are several 825 reasons why a single administrative domain may be broken into several 826 ASes (which, in this case, are not really "autonomous".) It may be 827 that the existing IGPs do not scale well in the particular 828 environment; it may be that a more generalized topology is desired 829 than could be obtained by use of a single IGP domain; it may be that 830 a more finely grained routing policy is desired than can be supported 831 by an IGP. In such deployments, it can be useful to allow BGP to 832 make its routing decisions based on the IGP metric, so that BGP 833 chooses the "shortest" path between two nodes, even if the nodes are 834 in two different ASes within that same administrative domain. The 835 authors refer to the set of ASes in a common administrative domain as 836 an "AIGP Administrative Domain". 838 A combination of the AIGP administrative metric and the graph 839 heuristic algorithm could be combined to arrive at a set of a 840 suitable number k power-shortest paths and then use a tie-break 841 amongst such k power-shortest-paths with the least AIGP metric. This 842 is provided the set of ASes where the decision is being made all fall 843 under a AIGP Administrative domain. This provides a trade-off of 844 power shortest paths and least number of hops (link wise) to get from 845 source to destination across these ASes. 847 2.4.1 PWR_SESSION 849 An implementation that supports the PWR attribute CAN support a per- 850 session configuration item, PWR_SESSION, that indicates whether the 851 PWR attribute is enabled or disabled for use on that session. 853 - The default value of PWR_SESSION, for EBGP sessions, between 854 providers (distinct operators) CAN be "disabled". 856 - The default value of PWR_SESSION, for IBGP and confederation- 857 EBGP sessions, MUST be "enabled." 859 The PWR attribute MUST NOT be sent on any BGP session for which 860 PWR_SESSION is disabled. 862 If an PWR attribute is received on a BGP session for which 863 PWR_SESSION is disabled, the attribute MUST be treated exactly as if 864 it were an unrecognized transitive attribute. That is, " The 865 handling of an unrecognized optional attribute is determined by the 866 setting of the Transitive bit in the attribute flags octet. Paths 867 with unrecognized transitive optional attributes SHOULD be accepted. 868 If a path with an unrecognized transitive optional attribute is 869 accepted and passed to other BGP peers, then the unrecognized 870 transitive optional attribute of that path MUST be passed, along with 871 the path, to other BGP peers with the Partial bit in the Attribute 872 Flags octet set to 1. If a path with a recognized, transitive 873 optional attribute is accepted and passed along to other BGP peers 874 and the Partial bit in the Attribute Flags octet is set to 1 by some 875 previous AS, it MUST NOT be set back to 0 by the current AS". 877 This helps in confining the distribution of the attribute and use in 878 calculation of the power shortest paths only amongst ASes that have 879 trust relationships with other ASes. Of course, this includes and 880 promotes the use of PWR attribute within a AIGP administrative 881 domain. 883 2.5 Conclusion and Future Work 885 In this paper, we proposed a scheme for reducing the power 886 consumption of the Internet using collaborative effort between AS. 887 The topology of the Internet is represented using a graph model and 888 derived using the strands obtained from the AS-PATH attribute of the 889 BGP updates. CSPF algorithm is run on this topology by using the PWR 890 ratio as a constraint. The PWR ratio is advertised through the 891 ingress links of the ASBRs associated with AS using BGP updates. The 892 CSPF algorithm finds out the low-power consuming AS that can route 893 data packets from a head-end to a tail-end. Explicit routing is 894 handled through the use of TE-LSPs. This entails adopting routes by 895 choosing entry points to an AS that give energy saving paths. Since 896 using CSPF can be time consuming a heuristic algorithm to derive the 897 low-power paths using graph-labeling was proposed. Our work 898 complements the current schemes for reducing power consumption within 899 a router such as switching off or bringing to power-idle-state 900 certain select components within the forwarding and lookup 901 mechanisms. 903 2.5.1 Link and node disjoint Backup paths and power constraints 904 This document in particular stresses the need for building protection 905 and backup paths for primary paths in such a way that both primary 906 and backup paths (either in a 1:1 or 1:N manner) are derived based on 907 the power constraints that are specified in the CSPF algorithm. It is 908 important to note that network operators may require a backup path 909 which is as power conservative as the primary one. Or even to the 910 extent that all backup paths have power constraints. Also it is 911 important that backup paths are completely node and link dis-joint 912 with respect to the primary path. In case of failure in the primary 913 path nodes the backup path would satisfy the same power constraints 914 and also avoid the nodes and links which have failed in the primary 915 completely. However if completely disjoint paths are not available a 916 suitable heuristic to include only those necessary nodes and links 917 from the primary path should be taken. Then these backup paths become 918 partially disjoint to the minimal extent possible. 920 This Power shortest Path calculation can be taken care of a Path 921 Computation Element (PCE) unit that could be either be a process 922 running on a linecard on a ASBR, or even a core router or an offline 923 engine that is passively listening to the BGP updates within the AS 924 without spitting out any routes of its own. The PCE architecture has 925 already been proposed in the ietf and even has a separate working 926 group for itself. These offline or linecard engines are currently 927 being sold in the market by the networking majors and other companies 928 that develop hardware and software for the PCE. All the PCE needs to 929 do is to accept configuration and passively listen to BGP updates 930 from various peers or even be a client for a route reflector, thus 932 a) Accepting these BGP updates 934 b) Extracting the AS PATH information from these updates 936 c) Then constructing the inter-AS topology 938 d) Apply the PWR metric that comes along in these BGP updates to the 939 edges of the graph 941 e) Then compute the power shortest path as required by the 942 configuration. 944 Normally the ASes have SLA agreements between each other to carry X 945 amount of traffic from say a provider A. If the AS representing the 946 ISP then advertises fake figures to carry more traffic than is 947 mandated by the SLA agreement with other providers, then it is to 948 that ISPs detriment since by advertising a better PWR ratio it 949 invites more traffic through it thus getting paid less and carrying 950 more traffic. This is not in the best interest of the ISP. This is so 951 because in the final analysis the Power Shortest Path computed would 952 include it regardless of the amount of traffic to be carried thus 953 causing it to invite more traffic through it than it has accepted, 954 even much more than its capacity. Hence it would be advisable for 955 that ISP to advertise proper PWR ratios and NOT on the lower side of 956 the spectrum. If it advertises HIGHER PWR ratios it would not be 957 chosen, and hence that could be a policy measure NOT to accept any 958 traffic at all since its capacity may be filled up with existing 959 traffic. So advertising on the LOWER side would lead to lesser amount 960 of benefit with respect to dollar per bit transported, and on the 961 HIGHER side would be to exclude it from carrying any traffic that 962 wanted to use the Power Shortest Path. 964 We also propose that there be a governing body in the IETF or outside 965 it or sponsored by the IETF to verify the power ratios advertised are 966 indeed valid or approximately closer to the actual consumption. A 967 link up for each ISP with a power application level gateway to ensure 968 proper ratios are advertised could be mandated amongst at least the 969 co-operating ISPs (ASes). 971 The points on which this proposal by us innovates is as follows. 973 a) There has been no effort prior to this to build an inter-AS 974 topology with a weighted graph based on a PWR ratio. On this point it 975 breaks a new path that would lead to inter-AS co-operation that 976 contributes to power reduction overall in the internet. The paper 977 suggested for OSPF by [10] deals with intra-Autonomous-system 978 scenario rather than an inter-AS one. It is also to be noted that the 979 IGP such as OSPF / IS-IS or any other link-state protocol for that 980 matter is expected to capture the energy consumption of each router 981 within the Autonomous system as in paper [10] to help get a hold on 982 the overall average within the AS, or even sum up the total of all 983 the power consumption within the AS with such intra-AS IGP LSA. This 984 contributes to the PWR ratio proposed in our idea. Thus the intra-AS 985 metric contributes to the PWR ratio. [10] proposal deals with 986 primarily paths setup within an AS and not inter-AS paths. Thus the 987 fundamental problem it solves is different while the problem we solve 988 relates to the inter-AS paths which run across ASes from a head-end 989 AS to a tail-end one. 991 b) The other aspect of innovation is to use BGP as the piggyback 992 protocol upon which this scheme stands. There has been no effort 993 earlier to approach the internet power reduction problem with BGP as 994 the mode of transport of the energy ratios and coupling it with the 995 inter-AS topology built with AS-PATH-INFO information. 997 The above 2 are key aspects of innovation. 999 When links and switches are gated or put into low-power state within 1000 an AS, the power-consumption automatically drops at the aggregate 1001 level, as a result of which the PWR ratio would be a lower figure 1002 advertised through BGP and thus this AS would attract more Power 1003 Shortest Path traffic through it. Thus the links within the AS and 1004 the switches within it would function more optimally if it had more 1005 traffic that went along paths that were originally put in low-power 1006 state thus utilizing the paths more effectively, when attracting PSP 1007 traffic. 1009 There exist MIBs today that have object identifier for power consumed 1010 in a router. Maybe all the related components within it may NOT be 1011 listed with regards to power consumed. But the overall power consumed 1012 by the Router / Switch is gettable. Once it is advertised in a opaque 1013 Link-State-Advertisement say in the form of a TLV and the LSAs are 1014 flooded through the network in an AS, all routers get a uniform 1015 picture of which router consumes what power. This method already 1016 exists for Traffic engineering Database LSAs that are advertised as 1017 LSAs for the purpose of traffic engineering within an AS. We are 1018 merely piggybacking on this capability to calculate the PWR ratio at 1019 the ASBR which amongst others is yet another Router / Switch of the 1020 AS. 1022 Our future work includes looking into computing low-power paths 1023 within AS as well. Further it can be noted that the proposed 1024 algorithms might lead to increased latency as the number of hops 1025 increase, which could be critical for time sensitive applications. 1026 Since the PWR ratio could vary dynamically with traffic, the impact 1027 of traffic on the algorithm would also be of interest. 1029 2.6 Acknowledgements 1031 Shankar Raman would like to acknowledge the support by BT Public 1032 Limited (UK) under the BT IITM PhD Fellowship award. Balaji Venkat 1033 and Gaurav Raina would like to acknowledge the UK EPSRC Digital 1034 Economy Programme and the Government of India Department of Science 1035 and Technology (DST) for funding given to the IU-ATC. Vasan would 1036 like to thank Prof.Kamakoti in the Department of Computer Science and 1037 engineering for his support. 1039 3 Security Considerations 1041 No specific security considerations apart from the usual 1042 considerations with respect to authenticating BGP messages / updates 1043 from BGP neighbors is necessary for this scheme. 1045 4 IANA Considerations 1047 A new optional transitive non-discretionary attribute needs to be 1048 provided by IANA for carrying the PWR ratio across the Internet in 1049 the specified format in BGP. 1051 5 References 1053 5.1 Normative References 1055 5.2 Informative References 1057 REFERENCES 1059 [1] G. Appenzeller, Sizing router buffers, Doctoral 1060 Thesis, Department of Electrical Engineering, Stanford 1061 University, 2005. 1063 [2] A. P. Bianzino, C. Chaudet, D. Rossi and J. L. 1064 Rougier, A survey of green networking research, IEEE 1065 Communications and Surveys Tutorials, preprint. 1067 [3] J. Baliga, K. Hinton and R. S. Tucker, Energy 1068 consumption of the internet, Proc. of joint international 1069 conference on optical internet, June 2007, pp. 1-3. 1071 [4] J. Chabarek, J. Sommers, P. Barford, C. Estan, D. 1072 Tsiang and S. Wright, Power awareness in network design 1073 and routing, Proc. of the IEEE INFOCOM 2008, April 2008, 1074 pp. 457-465. 1076 [5] B. Venkat et.al, Constructing disjoint and partially 1077 disjoint InterAS TE-LSPs, USPTO Patent 7751318, Cisco 1078 Systems, 2010. 1080 [6] M. Xia et. al., Greening the optical backbone network: 1081 A traffic engineering approach, IEEE ICC Proceedings, May 1082 2010, pp. 1-5. 1084 [7] W. Lu and S. Sahni, Low-power TCAMs for very large 1085 forwarding tables, IEEE/ACM Transactions on Computer 1086 Networks, June 2010, vol. 18, no. 3, pp. 948-959. 1088 [8] B. Zhang, Routing Area Open Meeting, Proceedings of 1089 the IETF 81, Quebec, Canada, July 2011. 1091 [9] M.J.S Raman, V.Balaji Venkat, G.Raina, Reducing Power 1092 consumption using the Border Gateway Protocol, IARIA 1093 conferences ENERGY 2012. 1095 [10] A.Cianfrani et al., An OSPF enhancement for energy 1096 saving in IP Networks, IEEE INFOCOM 2011 Workshop on Green 1097 Communications and Networking 1099 [draft-ietf-idr-aigp] P. Mohapatra et.al, The Accumulated 1100 IGP metric attribute for BGP, 1101 https://datatracker.ietf.org/doc/draft-ietf-idr-aigp/, 1102 November 2012. 1104 Authors' Addresses 1106 Shankar Raman 1107 Department of Computer Science and Engineering 1108 IIT Madras, 1109 Chennai - 600036 1110 TamilNadu, 1111 India. 1113 EMail: mjsraman@cse.iitm.ac.in 1115 Balaji Venkat Venkataswami 1116 Department of Electrical Engineering, 1117 IIT Madras, 1118 Chennai - 600036, 1119 TamilNadu, 1120 India. 1122 EMail: balajivenkat299@gmail.com 1123 Prof.Gaurav Raina 1124 Department of Electrical Engineering, 1125 IIT Madras, 1126 Chennai - 600036, 1127 TamilNadu, 1128 India. 1130 EMail: gaurav@ee.iitm.ac.in 1132 Vasan Srini 1133 Department of Computer Science and Engineering 1134 IIT Madras, 1135 Chennai - 600036, 1136 TamilNadu, 1137 India. 1139 Email: vasan.vs@gmail.com