Abstract:
In optical networks new links are added between nodes over time to satisfy the increasing traffic demands of the network. Existing links are normally not changed, resulting in a network that does not have the lowest energy consumption. A method provides a way to reduce the energy consumption of the overall network while supporting the required traffic demands at all times. The network includes a multiple source nodes, and multiple destination nodes. The network is represented by a graph of nodes connected by edges, wherein each node represents an optical network element and each edge represents a path connecting two optical network elements. Each edge is labeled with a demand. The non-bridge edge with a lowest demand is removed from the graph, and the lowest demand is added to the non-bridge edge with a highest demand. These steps are repeated until a termination condition is reached.

Description:
FIELD OF THE INVENTION 
     This invention relates generally to optical networks, and more particularly to reoptimizing the links in an optical network in an energy efficient manner. 
     BACKGROUND OF THE INVENTION 
     Optical networks continue to grow at a high rate, driven by the increase in the size of the Internet. As they grow their energy consumption increases, so that the combined energy consumption of the data network has become a significant fraction of the total energy consumption of a country. For example, Telecom Italia&#39;s network consumed over 2 TWh in 2005, which is approximately 1% of the total Italian energy demand. It is therefore important to find methods to reduce the energy consumption of optical networks. 
     Optical networks are not fully planned and constructed at one time, but have a tendency to grow by adding new links to increase capacity, with minimal modification to the current links in order to minimize disruption. It is known that in the Optical Transport Network (OTN) larger Optical Data Units (ODUs) can be transported and switched using much lower energy than smaller ODUs. Therefore, optical links with large amounts of traffic consume less energy per bit than links with a smaller amount of traffic. This means that over time the energy efficiency of the optical network will move away from an optimum, even if the original design had close-to-optimum energy consumption. 
     It is possible to reduce the energy consumption of the network by changing the network topology, either in part or in total, as links are added or removed. However, this would be costly because it would involve changing network equipment, and disruptive because network operation would be interrupted. In most cases it is important to minimize the disruption in the traffic by only changing links that have the most significant impact to energy consumption. We teach a method to reduce network energy consumption with a minimal amount of traffic redistribution. 
     SUMMARY OF THE INVENTION 
     Embodiments of the invention provide methods to reoptimize an optical network in order to improve its overall energy consumption. The embodiments determine changes to the network that provide a good improvement in energy efficiency with only a small number of changes, by favoring large bundles of traffic on links in the network. In this way the energy efficiency can be improved significantly with minimal disruption to current traffic. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  is a graph of energy and derivative of energy as a function of data rate; 
         FIG. 2  is a schematic of the graph of network connections between fifteen nodes with example traffic demands; 
         FIG. 3  is a schematic of example edge demands in the network of  FIG. 2 ; 
         FIG. 4  is a flow diagram of a method to reoptimize energy efficiency of the network according to embodiments of the invention; 
         FIG. 5  is a schematic of the network graph after the first step of the method; 
         FIG. 6  is a schematic of the network graph after the second step of the method; 
         FIG. 7  is a schematic of the network graph after the third step of the method; 
         FIG. 8  is a schematic of the network graph after the method is complete; 
     
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT 
     In general, the energy consumption of the network is dominated by the switching and routing functions. An ODU Cross-Connect (XC) has reduced energy consumption per bit compared to a Layer 3 (L3) router, Ethernet Switch or SONET/SDH XC. In addition, larger ODU sizes require less energy to switch and transport than smaller ODU sizes. The ODU sizes are not continuously adjustable; rather the currently defined sizes are 1.25 Gbps (ODU0), 2.5 Gbps (ODU1), 10 Gbps (ODU2), 40 Gbps (ODU3), and 100 Gbps (ODU4). However, for illustration of the methods we assume that the energy consumption E S  as a function of data rate R is a continuous concave function with diminishing slope, as shown in  FIG. 1 . Specifically for the values presented we assume that E S (R)=2*sqrt(R). Note that every link has a maximum capacity. 
     Because E S  is a concave function with diminishing slope, the marginal energy consumption, E′ S  (where the symbol E S ′ denotes the derivative of E S ), will be a continuously reducing function. Thus, for the values presented we assume that E′ S (R)=1/sqrt(R). 
     We now consider the example network shown in  FIG. 2  including fifteen nodes, labeled  1 ,  2 , . . .  15 , and optical links, which are denoted by the lines connecting the nodes. The nodes represent optical network element, e.g., routers, switches, and cross-connects. In general, the energy consumption of the network is dominated by the switching and routing functions. An ODU Cross-Connect (XC) has reduced energy consumption per bit compared to a Layer 3 (L3) router, Ethernet Switch or SONET/SDH XC. In addition, larger ODU sizes require less energy to switch and transport than smaller ODU sizes. The optical link between two adjacent nodes is termed an “edge.” We define a “path” as a sequence of connected edges linking two nodes. The traffic demand between a source node and a given destination node j is termed the “demand,” denoted by D(i, j). 
     To illustrate the energy reduction method, we assume the network in  FIG. 2  with a single source node i=1 with fourteen destination nodes j, 2, . . . 15. The demand D(1, j), is given by the values next to the nodes. For example, the demand D(1, 3) is equal to 22 units of traffic, D(1, 3) is equal to 12 units of traffic and D(1, 4) is equal to 8 units of traffic. 
     In the general case there may be more than one path linking two nodes and so the demand is be shared across each path. If there are M paths defined between nodes i and j, the traffic demand for path k (where k=1, . . . , M) is termed the “path demand” and is denoted by PD(i,j,k). Note that the demand is equal to the sum of the path demands, that is D(i,j)=Σ 1   M PD(i,j,k). As there are many source and destination nodes, a given edge has traffic associated with a number of different paths. The traffic demand on an edge is termed the “edge demand.” 
     As described by way of example below, the edge demand on any particular link, (i,j), is a function of the total demand between all sources and destinations and the number of paths between sources that contain the edge (i,j). The capacity of each edge to carry any portion of the demand can initially be allocate so that the basic constraints are satisfied, i.e., all demands are satisfied and no edge is allocated more demand than its capacity. Thus, the demand can be allocated in a number of ways. We assume edge demands as shown in  FIG. 3 , and we describe, how given a new allocation that lowers the energy consumption can be found for the initial edge demand allocation. 
     For most nodes, there are multiple possible paths through the network to get from node j to node  1  to satisfy the demand. For example, from node  11  there is one possible path to node  1  using nodes using nodes  11               8             6             5             4             2             1  (amongst other options), where “         ” indicates an edge. Note that edges can be unidirectional, bidirectional with different edge demands in each direction, or bidirectional with equal edge demands in each direction. Bidirectional edges with equal edge demands are shown for simplicity.
     In  FIG. 3 , for the purposes of illustration we assume that the demand from node  1  to node N, (N=2, 3, . . . , 15) is supported by only one path, except for  1               7  and  1             5 , whose demand is split amongst 3 paths each. The demands are split over the following paths:  1             7  demand, split into paths  1             3             7 ,  1             2             4             5             7  and  1             8             6             5             7  with path demands  1 ,  2  and  2  respectively (total of 5, which is the  1             7  demand), and  1             5  demand, split into paths  1             3             7             5 ,  1             2             4             5            and  1             8             6             5  with paths demands  7 ,  12  and  4  respectively (total of 23, which is the  1             5  demand). The total energy consumed by the network using the assumptions provided earlier is the sum of all the edge energies given by 2√{square root over (edge demand)}. In this case, the total energy consumed is 163.2 units of energy.
       FIG. 4  shows a method for improving energy efficiency in an optical network while satisfying all the demands at each step according to the embodiments of the invention. The steps of the method, and any other processes described herein can be performed in a processor connected to memory and input/output interfaces as known in the art. 
     First, we construct  410  a graph representing network. The network include node connected by edges. The edges are associated traffic demands between the nodes. 
     We identify and exclude  420  bridge edges in the network using the graph, where a “bridge edge” is an edge, if removed, results in an unconnected network. This can be performed using a known procedure. 
     Next, we identify and remove  430  which of the remaining edges has a highest marginal energy (lowest demand). This edge is removed from the network and the lowest demand is added  330  to the edge with the lowest marginal energy that meets the following conditions: supports the required demand, and does not exceed the capacity of any given edge in the altered network 
     If two or more edges have the same lowest marginal energy, then one is selected arbitrarily. 
     We now check  450  to see if all remaining edges in the network are bridge edges and if yes, terminate  455 . If no, check  460  if a maximum number of allowed iterations has been exceeded and if yes, terminate  465 . If not, then repeat beginning at step  420 . 
       FIG. 5  shows the network graph at steps  420  and  430 . The bridge edges determined in step  420  are illustrated by the dashed lines. The edge identified to have the highest marginal energy (lowest demand) in step  430  is edge  5               6   510 .
       FIG. 6  shows the network graph at steps  430  and  440 . The  5               6  edge is removed from the network and the removed edge demand ( 6 ) is added to the edges  5             4 ,  4             2 ,  2             1  because the lowest marginal energy edge supporting paths which use node  5  is the  5             4  edge. It is also removed from the  6             8  and  8             1  edges because it is no longer needed to support paths using those nodes. Because not all edges are bridge edges the method will continue. In the next iteration the edge  610  to be removed is  3             7 .
       FIG. 7  shows the network graph after step  420  and  430  of the second iteration. The edges  710  and  720  have been identified as bridge edges and removed from consideration. The  3               7  edge has also been removed and its demand added to the other edges as described previously. At this stage all the edges are bridge edges and so the method terminates.
       FIG. 8  shows the network graph after the method has completed. The total energy is computed as before for the new network and found to be 154.2, a saving of (163.2−154.2)/163.2=5.5% in this example. 
     For multiple-source multiple-destination, the algorithm is analogous to the single-source case. The edge demand is found as before, but considering all demands between the N nodes, D(1, j) rather than just the demands from a root node, D(1, j) in the example presented. The bridge edges are removed and the edge with the highest marginal energy that supports the two conditions described is found. This edge is then removed and its edge demand is redistributed over the other edges for each of the paths that are supported by this edge. This procedure continues as before until the maximum number of iterations is reached, or there are no more bridge edges. 
     Extension to Other Protocols 
     The prior descriptions dealt only with OTN, but it is important to note that the same algorithms can be applied to other protocols, including those transported by OTN. As an example, consider Label Switched Paths (LSPs) in MPLS (Multi-Label Protocol Switching). LSPs can be carried by OTN and may be quasi-static in nature. As such, they may be reoptimized so that they are carried by higher rate ODUs so freeing up lower rate ODUs and improving energy efficiency. This uses the same algorithm as described. 
     Although the invention has been described by way of examples of preferred embodiments, it is to be understood that various other adaptations and modifications may be made within the spirit and scope of the invention. Therefore, it is the object of the appended claims to cover all such variations and modifications as come within the true spirit and scope of the invention.