Multi-layer modem reclamation systems and methods

Modem reclamation systems and methods for optimizing optical modem use in a network include determining costs and capacity range for Lx adjacencies in the network based on Lx information and L0 information, wherein Lx is a digital layer with routed traffic and L0 is a media layer with optical modems that are reclaimed when their utilization is reduced in the digital layer; determining an order of Lx connection moves that minimizes the costs of the Lx adjacencies, to reclaim or minimize the optical modem use; and performing the Lx connection moves based on the order and updating the Lx adjacencies.

FIELD OF THE DISCLOSURE

The present disclosure generally relates to networking systems and methods. More particularly, the present disclosure relates to multi-layer optical modem reclamation systems and methods.

BACKGROUND OF THE DISCLOSURE

Optical networks are experiencing every growing capacity and, in part, addressing this growth with advanced optical modems supporting high capacity through advanced modulation formats, optical impairment mitigation through electrical domain processing, and the like. Simply put, optical modems are a costly component in optical networks, and it would be advantageous to optimize their usage. Conventional techniques for bandwidth reclamation focus on the release of stranded capacity in a single layer. From a terminology perspective, networks can be logically grouped into Layers, such as the OSI stack, with Layer 0 as a photonic layer, Layer 1 as a Time Division Multiplexing (TDM) layer, Layer 2/3 as a packet, and the like. In operation, optical modems (Modulator/Demodulator) are carrying traffic spanning each of these layers. Conventional techniques utilize control plane functionality in each technological layer, and optimization is therefore limited and focused on that particular technological layer. There is a need for a unified, multi-layer process which can be used for modem reclamation where the modems are carrying multi-layer traffic. Note, the multi-layer modem reclamation problem cannot be solved at each layer individually as each modem carries multi-layer traffic and changes in one layer impact other layers.

BRIEF SUMMARY OF THE DISCLOSURE

In an exemplary embodiment, a modem reclamation method, implemented by one or more controllers, for optimizing optical modem use in a network includes determining costs and capacity range for Lxadjacencies in the network based on Lxinformation and L0information, wherein Lxis one or more digital layers with routed traffic that is ultimately carried over L0, and L0is a media layer with optical modems that are reclaimed when their utilization is reduced in the digital layers; determining an order of Lxconnection moves that minimizes the costs of the Lxadjacencies, to reclaim or minimize the optical modem use; and performing the Lxconnection moves based on the order and updating the Lxadjacencies. The modem reclamation method can further include performing one of i) repeating the determining steps and the performing step and ii) reclaiming one or more optical modems subsequent to the Lxconnection moves, responsive to whether stopping criteria is met. The modem reclamation method can further include, subsequent to the Lxconnection moves, disabling the optical modems with no Lxadjacencies thereon. The capacity range for the Lxadjacencies can be determined based on an order in which the optical modems are disabled and links with disabled modems have their associated capacity range decreased accordingly. The optical modems can be disabled based on an optimization technique. The optimization technique can include one of a heuristically calculated merit of removing each modem, Lagrangian decomposition, and Bender's decomposition. The costs for the Lxadjacencies can be based on one or more of i) where modems are disabled, ii) utilization of the Lxadjacencies and (iii) network policy. The method can be implemented in one or more of a Lxcontroller, a L0controller, and an inter-layer controller, wherein when the method is implemented by multiple controllers, each of the multiple controllers is adapted to communicate to one another. The Lxcan be the digital layer including one or more of Time Division Multiplexing (TDM) and packet layer traffic and L0can be a Dense Wave Division Multiplexing (DWDM) layer, and wherein the Lxadjacencies are optimized to minimize optical modem usage in the DWDM layer.

In another exemplary embodiment, a modem reclamation system for optimizing optical modem use in a network includes circuitry adapted to determine costs and capacity range for Lxadjacencies in the network based on Lxinformation and L0information, wherein Lxis one or more digital layers with routed traffic that is ultimately carried over L0, and L0is a media layer with optical modems that are reclaimed when their utilization is reduced in the digital layers; circuitry adapted to determine an order of Lxconnection moves that minimizes the costs of the Lxadjacencies, to reclaim or minimize the optical modem use; and circuitry adapted to cause the Lxconnection moves based on the order and updating the Lxadjacencies. The modem reclamation system can further include circuitry adapted to perform one of i) cause repetition the determine costs and capacity range, the determine the order and the Lxconnection moves and ii) cause reclamation of one or more optical modems subsequent to the Lxconnection moves, responsive to whether stopping criteria is met. The modem reclamation system can further include circuitry adapted to, subsequent to the Lxconnection moves, causes disablement of the optical modems with no Lxadjacencies thereon. The capacity range for the Lxadjacencies can be determined based on an order in which the optical modems are disabled and links with disabled modems have their associated capacity range decreased accordingly. The optical modems can be disabled based on an optimization technique. The optimization technique can include one of a heuristically calculated merit of removing each modem, Lagrangian decomposition, and Bender's decomposition. The costs for the Lxadjacencies can be based on one or more of i) where modems are disabled, ii) utilization of the Lxadjacencies and (iii) network policy. The Lxcan be the digital layer including one or more of Time Division Multiplexing (TDM) and packet layer traffic and L0can be a Dense Wave Division Multiplexing (DWDM) layer, and wherein the Lxadjacencies are optimized to minimize optical modem usage in the DWDM layer.

In a further exemplary embodiment, a system of controllers includes at least one Lxcontroller; at least one L0controller; and an inter-layer controller, wherein the at least one Lxcontroller, the at least one L0controller, and the inter-layer controller are configured to determine costs and capacity range for Lxadjacencies in the network based on Lxinformation and L0information, wherein Lxis one or more digital layers with routed traffic that is ultimately carried over L0, and L0is a media layer with optical modems that are reclaimed when their utilization is reduced in the digital layers; determine an order of Lxconnection moves that minimizes the costs of the Lxadjacencies, to reclaim or minimize the optical modem use; and cause the Lxconnection moves based on the order and updating the Lxadjacencies. The Lxcan be the digital layer including one or more of Time Division Multiplexing (TDM) and packet layer traffic and L0can be a Dense Wave Division Multiplexing (DWDM) layer, and wherein the Lxadjacencies are optimized to minimize optical modem usage in the DWDM layer. The at least one Lxcontroller, the at least one L0controller, and the inter-layer controller can be in one of a monolithic configuration, a hierarchical configuration, and a distributed configuration.

DETAILED DESCRIPTION OF THE DISCLOSURE

Again, in various exemplary embodiments, multi-layer optical modem reclamation systems and methods are described. Modem reclamation is the process by which network traffic is re-routed to release optical modems for future traffic. Note, optical modems can also be referred to as transceivers, transponders, or the like. This process can be formalized as a mathematical optimization problem which minimizes the number of modems to support existing network traffic. The optimization is searching for a set of modems that can be turned off while the existing network traffic is still supported. Using mathematical optimization theory, the optimization is decomposed according to network layers, which allows for derivation of optimization algorithms. Two decompositions are presented, each of which leads to a different optimization algorithm. Advantageously, the systems and methods reclaim the modems into a free modem pool, while still carrying the current network traffic. The systems and methods can be distributed over multiple layer controllers as well as with Software Defined Networking (SDN). The systems and methods generally have two main parts: first weights are found for adjacencies in the upper layer based on information in the upper and lower layers; second the traffic in the upper is shifted to minimize the total running cost, using the adjacency weights. After the traffic is shifted, modems can be reclaimed. The approach is based on optimization theory, and embodiments are shown that lead to the maximum number of reclaimed modems.

The systems and methods use combined information related to a multiple layer network to achieve better modem reclamation then what is possible with a portioned network layer network view. The systems and methods can be implemented in a single centralized multi-layer controller, or implemented across multiple single-layer controllers that are interacting with one another. Various embodiments in the disclosure show how the weights can be found and how the method can be implemented across multiple layer controllers with only partial knowledge of resource availability and usage in other layers.

Modem reclamation is a part of many other network optimization processes, such as, for example, network resource optimization, network reconfiguration when traffic patterns change, handling of unexpected traffic changes in emergency situations, etc. For these scenarios, it is advantageous to either carry existing traffic with fewer modems and redeploy surplus modems for unanticipated new traffic or anticipated future traffic. Application of the systems and methods provides network build outs that are deferred, and the network is less expensive to operate. Again, the systems and methods solve modem reclamation by considering multiple layers simultaneously, span multiple network layers controlled by separate network controllers, etc. The foregoing descriptions include multiple exemplary embodiments for various sub-processes, which indicate a full reclamation process. Analytics can be used to forecast traffic patterns, which can be used with the systems and methods.

Referring toFIG. 1, in an exemplary embodiment, a network diagram illustrates a multi-layer, multi-domain network10for use with the multi-layer optical modem reclamation systems and methods. Those of ordinary skill in the art will appreciate the network10is presented for illustration purposes and the systems and methods described herein contemplate other implementations as well, in other multi-layer optical networks. The network10includes four logical groupings—a network-as-a-service (NaaS)12, a network operator14, network clients16, and remote services18. The network-as-a-service12can include two optical networks20a,20b, a switched network22, and a management plane24. The optical networks20a,20bcan include network elements26, such as Reconfigurable Optical Add/Drop Multiplexers (ROADM), DWDM terminals, optical amplifiers, and the like. The optical networks20a,20bcan also include a control or management plane or the like through a Path Computation Element (PCE)28and an optical network controller30. In an exemplary embodiment, the optical networks20a,20bcan provide wavelength connectivity and TDM such as Optical Transport Network (OTN). That is, the optical networks20a,20bcan provide Layer 0 (photonic) and/or Layer 1 (TDM) connectivity. Note, the optical modems that are reclaimed herein are located in the network elements26.

The switched network22can include switches32which are interconnected to one another via the optical networks20a,20b. In an exemplary embodiment, the switches32can provide packet connectivity such as through Ethernet, Multiprotocol Label Switching (MPLS), Internet Protocol (IP), and the like. Thus, the switched network22can provide Layer 2/3 packet connectivity. The switched network22can include a packet network controller34with an associated PCE36as well. Note, the network elements26can also be Packet-Optical Transport Systems (POTS), integrating L0/L1/L2. Of course, various other exemplary embodiments are contemplated with the network10providing an illustration of a multi-layer, multi-domain network. Note, multi-domain is shown, e.g., based on the two separate optical networks20a,20b, in different domains with separate optical network controllers30. There may also be multiple domains in the switched network22as well.

In operation, for example, the network-as-a-service12provides connectivity for a network service38between the network clients16and the remote services18, such as a data center40. The network service38utilizes hardware resources on the network elements26and the switches32including optical modems in the optical networks20a,20b. The network service38is a physical path in the network-as-a-service12, denoted as a solid line. The network10includes various virtual adjacencies between the controllers30,34and the management plane24. In an exemplary embodiment, the management plane24is an SDN management plane, and the controllers30,34can be SDN controllers. The management plane24can include various SDN applications to realize and orchestrate the modem reclamation systems and method described herein.

The management plane24can include a topology database (DB)42, a service database (DB)44, a Customer Relationship Management System (CRMS)46, and a network service orchestrator50and an associated PCE52. Note, the various components42,44,46,50can be realized as a server with associated software executed thereon. The topology database42maintain virtual adjacencies with the controllers30,34and the associated PCEs28,36for receiving and maintaining inventory, network status, topology, and the like. The topology database42can also maintain a virtual adjacency with the network service orchestrator50and the associated PCE52for providing the inventory, network status, topology, and the like. The service database44can include information about currently active network services38, customers using them, and past service requests. This information in the service database44can be used to forecast and predict network demand. The CRMS46can include software to track customer requests, services, billing and may present a view of the network services38to the customers and negotiate prices with the customer. The CRMS46is typically closely coupled, or even implemented as part of business Support Systems (BSS) or Operations Support Systems (OSS). The network clients16can interface to the CRMS46via a service portal54. The network operator14can receive alarms and the like via the topology database42through a network portal56.

The network service orchestrator50is configured to receive requests for the network services38and to dispatch them to various layers and domains through the network10. Each layer or domain may have its own PCE28,34which calculates a path across that layer. For example, Layer 0 has its own controller30independent of other layers. At the time a service request is made, various PCEs28,34may not have good information about where future traffic may reside. This results in stranded bandwidth in multiple layers. Thus, this disclosure deals with modem reclamation.

Modem Reclamation

Modern optical networks, such as the network10, provide mechanisms to provide on-demand network services using multiple data plane layers and corresponding network layer or domain controllers. Network service demands are served instantaneously in their order of arrival, without the knowledge of potential future demands. Serving network service demands without the knowledge of future demands may lead to an inefficient network resource usage: “stranded” capacity on under-utilized optical modems. Since optical modems are an expensive part of the network to upgrade, it is necessary to provide a reclamation process, which shifts capacity across layers and enables the release of under-utilized modems into the pool of available modems. To get the biggest benefit, the reclamation process should be done by considering multiple network layers simultaneously.

The modem reclamation process can be used in multiple network optimization procedures as a way of increasing network efficiency and deferring of network build-outs. First, for network resource optimization, the modem reclamation produces traffic grooming, which defers adding new equipment to the network10and decreases network operating costs (e.g., energy usage). For dealing with traffic shifts, the modem reclamation produces more efficient modem usage, thus freeing-up modems for anticipated future traffic. For dealing with unanticipated emergency situations, the modem reclamation results in more efficient modem usage, allowing for modems to be redeployed for the handling of unanticipated increases in network traffic. For dealing with fragmented optical spectrum, which prevents formation of “super” channels, the modem reclamation can be used to release spectrum where the super channel would reside. In all of the aforementioned scenarios, it is advantageous to carry existing traffic with fewer modems and if necessary to redeploy surplus modems.

Referring toFIGS. 2-7, in an exemplary embodiment, network diagrams illustrate an exemplary implementation of modem reclamation in a network60including optical network elements26E,26F,26G,26H and switches32A,32B,32C,32D. Again the optical network elements26E,26F,26G,26H can be ROADMs with modems interconnected via optical fibers62. The switches32A,32B,32C,32D connect to the optical network elements26E,26F,26G,26H via the optical fibers62and to one another through virtual adjacencies64formed via the optical network elements26E,26F,26G,26H. The modem reclamation problem in this example can be defined as how to provide services between the switches32A,32B,32C,32D with a minimum amount of modems in the optical network elements26E,26F,26G,26H.

First, inFIG. 3, a demand66comes in for a service between the switches32A,32B; a path68is found between the switch32A, the optical network elements26G,26E, and the switch32B. The path68is lit up via modems as light70; the demand66is provisioned as a Lxconnection. Lxis used as an example herein, for L1, but this can be L1, L2or L3. InFIG. 4, next a new demand72comes in for a service between the switches32A,32D; a path74is found between the switch32A, the optical network element26E, and the switch32D. The path74is lit up via modems as light76; the demand72is provisioned as a Lxconnection. InFIG. 5, next a new demand78comes in for a service between the switches32B,32C; a path80is found between the switch32B, the optical network element26F, and the switch32C. The path80is lit up via modems as light82; the demand78is provisioned as a Lxconnection. InFIG. 5, next a new demand84comes in for a service between the switches32C,32D; a path86is found between the switch32B, the optical network element26H, and the switch32C. The path86is lit up via modems as light88; the demand84is provisioned as a Lxconnection.

FIG. 7illustrates all of the light70,76,82,88provisioned by modems inFIGS. 3-6. After all the demands66,72,78,84are connected, the network60has virtual adjacencies A→B, B→C, C→D, A→D. So, a Lxpath exists from A→D (A→B→C→D). For example, the demand72, serviced by the light76, can be rerouted on a path90, and the light76can be turned off, and the associated modems can be reclaimed and put in a pool of free modems.

Layer-Disjoint Network View

As the network10becomes more complex, the layer controllers30,34may be introduced do enable information hiding and scalability. One classification of controllers is into digital and media channel controllers (e.g., ITU-T G.872 “Architecture of optical transport networks” (10/12), the contents of which are incorporated by reference). The digital layer (e.g., OPU, ODU, OTU) can be referred to as Lxand media layers as L0(Optical Transmission Section (OTSiA)). The general assumption is that modems are in direct correspondence with OTSiA. L0has the controller30responsible for managing its resources (modems, spectrum, fibers, power). The L0controller30provides physical adjacencies to its client layers (e.g., Lx). Routing, by the L0controller30, is done to provide light paths required for its client layers, e.g., the light70,76,82,88. Any layer (e.g., L1, L2or L3) with the routing of end-to-end flows can be a client layer to L0.

A Layer-disjoint path computation is inefficient. Each layer is making sure that it is using resources for its best fit, in isolation of other layers. Upper layers may switch their traffic (aggregate/split) to fit available lower layer resources thus stranding lower layer resources. Lower layers may not be aware of where the resources should be allocated without the knowledge of upper layer needs. On-demand path computation is inefficient. Resources are assigned with the instantaneous knowledge of network usage. Some links may be saturated early if the path computation is too greedy, resulting in stranded resources which are not usable for future connections. Networks are expected to end up with stranded resources over time. Specifically, modems may be underutilized, which is very costly, inefficient, etc. It is important to run a modem reclamation process in the network that releases modems which are underutilized.

Controller Configurations

A modem reclamation process can occasionally be run to release modems not required to carry existing traffic. The process may be triggered by a number of events, such as scheduled network maintenance, forecast or detected blocking of service requests, etc. The process may be run in several network places, such as distributed across several network layer controllers (e.g., the controllers30,34), centrally in common network controller (e.g., the network service orchestrator50), a combination thereof, etc.

Referring toFIG. 8, in an exemplary embodiment, a block diagram illustrates exemplary controller configurations for the network10,60and for implementing the modem reclamation systems and methods. There are three exemplary controller configurations, namely a monolithic configuration100, a hierarchical configuration102, and a distributed configuration104. The modem reclamation systems and methods spans across multiple layers of the optical protocol stack; thus, there are multiple ways to implement multi-layer controllers in the network. In the monolithic configuration100, control of both layers is in a single controller (Joint Lx,L0controller110). In the hierarchical configuration102, the controllers30,34can use an intermediate layer to interact, such as through an inter-layer controller112(e.g., the network service orchestrator50). In the distributed configuration104, the controllers30,34interact directly with each other.

The modem reclamation process can be used with each of the configurations100,102,104. The hierarchical configuration102is shown inFIG. 1. The distributed configuration104can be obtained by embedding the inter-layer controller112in each layer controller30,34and sharing information between the embedded inter-layer controllers. The monolithic configuration100is obtained by bundling three controllers in the hierarchical architecture.

Only Lxlayer controller knows about end-to-end traffic demands and Lxrouting. The Lxcontroller can be thought of as the traffic engineering/routing controller. Only L0knows about modems, their rates, reach, etc. L0may only present a bundled view of available capacity to its client layers (e.g., without showing how the capacity is provided by modems). The information shared between the layers is maintained by the inter-layer controller112, such as required/granted capacity on Lxadjacencies, the cost of using Lxadjacencies, shared-risk link groups for Lxadjacencies. Note that the inter-layer controller112can be absorbed by either layer since the Lxcontroller needs to track the information about Lxadjacencies such as available capacity and the L0controller also needs to track information about Lxadjacencies such as used capacity.

Inter-Layer Modem Reclamation Process

Referring toFIG. 9, in an exemplary embodiment, a flowchart illustrates an inter-layer modem reclamation process150. The modem reclamation process150works across multiple layers to reclaim the maximum number of optical modems in the network10,60. The modem reclamation process150is derived from a mathematical multi-layer optimization modeling the minimization of the number of modems required to support the existing network traffic, which is described in additional detail herein. The modem reclamation process150solves the optimization in a way that is particularly amiable to the networking setting. First, it can be implemented to span controllers in multiple network layers, such as through the controller configurations100,102,104. Typically, layer controllers are loosely coupled, and they may be configured in a hierarchal topology (with an inter-layer controller) or in a vertical peer-to-peer topology (e.g. daisy chain of layers). The modem reclamation process150works for any controller configuration. Second, the modem reclamation process150produces a list of incremental network changes, which is required operationally for minimal disturbance to each connection.

To reclaim optical modems, modem utilization is reduced to a low value or zero. In the media layer, i.e., the optical layer, the optical modems carry a signal that has some maximum information rate of the clients it serves. Utilization refers to the amount of client information that is sent relative to the maximum rate possible over the optical signal. InFIG. 9, Lxrefers to one or more digital layers and L0refers to the media layer (optical). The digital layer may be packet-based (e.g., IP or Ethernet), TDM-based (e.g., OTN based), or a combination of multiple switching technologies. A Lxadjacency refers to a logical connection between packet switches/routers or OTN switches in the digital layer, which may be implemented using one or more optical modems sending information over paths in the fiber network. In the digital layer, packet or OTN traffic is routed over paths consisting of Lxvirtual adjacencies. To reduce utilization, connections are moved in the digital layers to free up the optical modems. For example, a move can include removing an ODU3 link (from an OTU4 server layer) by moving Ethernet traffic off of the ODU3 link.

The modem reclamation process150starts (step152) works in iterations, wherein each iteration some of the traffic are moved to the digital layer to make it possible to reclaim a modem in the media layer. The key part of the modem reclamation process150are two computational steps154,156, which ensure good performance. The modem reclamation process150includes determining costs and capacity ranges for Lxadjacencies (step154). Step154uses knowledge exposed by both layers to calculate the set of Lxadjacency weights used by the Lxto re-route traffic. Based on optimization theory, there are several ways to calculate the weights, each with a different level of optimality and complexity. This is explained in additional detail herein. There are many versions of the modem reclamation process150depending on how steps154,156are implemented, namely Heuristic/Greedy, Lagrangian dual decomposition, Bender's decomposition, etc.

The modem reclamation process150includes determining the order of Lxconnection moves that minimize Lxcosts (step156). Based on the weights calculated in step154, this step156reroutes the connections in Lxso that total Lxcost is minimized. This procedure can be implemented using optimization theory (described in additional detail herein) or using a connection ordering heuristic. Once the order is determined (step156), the modem reclamation process150includes moving Lxconnections (step158). Note, the connection moves may be skipped if capacity targets are not met, according to the policy set for the modem reclamation process150. Lxconnections are optionally moved if the target capacities are not met, in a given iteration. The connections are moved if the target capacities are met. But if the capacities are met, the connections may not be moved, and the current modem is skipped.

After step158, the modem reclamation process150includes updating Lxadjacency usage and releasing L0capacity (step160). That is, databases are updated to reflect the new network usage. Updating of Lxadjacency capacity ensures that L0capacity is not increased in an iteration. The modem reclamation process150includes checking if stopping criteria are met (step162), and if not, the modem reclamation process150continues to step154, with the new network usage, and if so, the modem reclamation process150reclaims unused modems (step164). Stopping criteria may depend on various techniques. Exemplary stopping criteria may include stop when at least n modems are released, stop when network costs fit certain criteria, stop when utilization of all modems is above some threshold, stop when nothing changes between iterations (i.e., no connection are moved, no modems are released), multiple criteria are met at the same time (e.g., least number of modems and no modems are moved), etc.

Described herein, three exemplary techniques are described to determine the costs of Lx adjacencies. The first technique calculates the Lxadjacency costs using a modem ranking heuristic, which first choses target modems to be turned off based on heuristically calculated merit of removing the modem. For example, modems with low utilization may be turned off first. The weights for Lxrouting are set to route the traffic away from the modems targeted for reclamation. The second technique to calculate the Lxadjacency costs is based on solving a Lagrangian dual of the mathematical optimization minimizing the number of modems in the network (primal problem). The second technique adjusts Lxlink costs so that the objective value of the Lagrangian dual function increases in each iteration. The adjustment is based on the information from both layers. This update can be implemented in a hierarchical controller, or through an information exchange between the layer controllers. The connections in Lxare moved until the value of the Lagrangian dual is close to the optimum value of the primal problem. At this point, the modems that can be turned off are turned off.

The third technique to calculate the Lxadjacency costs is based on primal decomposition with Bender's approach. In the Bender's decomposition, the process for selecting modems is separate and enumerates all possible sets of active modems and tests if the traffic can be shifted and still be carried by each set. Optimization theory is used to eliminate branches of the enumeration and speed up the process the search for the minimum cost active modem set. The modem reclamation process150can be split into several layer components. Generally speaking, the selection of modems can be done by the L0controller30and determining of the Lxweights can be done by either the Lxcontroller34or the inter-layer controller112. The weights on the Lxadjacency are broadcast to all layer controllers. The approach of using virtual adjacency weights to communicate between the layers in the resource reclamation can also be extended to support more than two layers.

Again, the modem reclamation process150reroutes network traffic to release optical modems for future traffic. This modem reclamation process150can be formalized as a mathematical optimization problem. The optimization is searching for a set of modems that can be turned off while the existing network traffic is still supported. Using mathematical optimization theory, the optimization is decomposed according to network layers, which allows for derivation of optimization algorithms. Two decompositions are presented, each of which leads to a different optimization algorithm.

Network Optimization Minimizing the Number of Modems

An optimization solving the modem reclamation problem (1) is shown below with the notation listed in Table 1.

The optimization takes as input paths for each layer in the network. Loosely speaking, the two layers correspond to a digital layer of the optical network stack (Lx) and the media layer of the optical network stack (L0). At the start of the optimization, there is a Lxadjacency for each pair of nodes that carry Lxtraffic. It is possible that more than one Lxadjacency exists for a pair of vertices. Lxpaths are calculated on the Lxtopology graph, which is defined by Lxadjacencies. For optimum results the set of Lx, pathsis the set of all paths in the Lxtopology. In practice, some of the paths are available from the current routing in the network and the rest are calculated while the optimization is solved numerically using the iterative column generation technique. Lxadjacencies are mapped onto L0paths(modem pairs), which are pre-established over the fiber topology.

TABLE 1NotationInputs to the optimizationSet of known LxdemandskAn Lxdemand, k ∈DkLxcapacity required for demand k ∈(known, or forecast)Set of Lxadjacencies, defining virtual topologyGraph corresponding to topology formed be LxadjacenciesSet of L0paths, traversing the fiber topologyNotation used for Lxtraffic engineeringeA Lxadjacency, e ∈Set of Lxpaths (calculated on)kSet of Lxpaths used by demand k on the virtualtopology;k= {pk} if thedemands are not load-balanced across multiple pathsxpAmount of Lxdemand assigned to path pyeCapacity required by Lxadjacency, e ∈CeCost of using Lxadjacency, e ∈eSet of Lxpathse⊂ktraversing Lxadjacency e ∈Notation used for L0traffic engineeringlA fiber path, l ∈zlCapacity available on fiber path (Bits/sec), l ∈eSet of L0paths carrying the capacity of Lxadjacency eRlModem rate used on path lClCost of using the modem on path l

The optimization finds the best values for three types of variables: xp, which corresponds to the capacity required for Lxconnections, ye, which corresponds to the capacity available on Lxadjacencies, and zl, which corresponds to the capacity provided by L0paths.

Various parts of the optimization are:

The objective function (1a) minimizes the cost of modems and the cost of Lxtopology. Assume, without any loss of generality, that modems are index by cost Ci≤Cjif i<j. Note that if only some modems need to be removed from the network (e.g. for the purposes of defragmenting the spectrum), the weights on those modems can be made positive numbers, while the weights on other modems can be made 0.

Constraints (1b) ensure that Lxdemands are satisfied, ensuring the capacity allocated for Lxconnection k is equal to or exceeds the traffic demand (Dk). The constraint exists for each demand; the summation is over Lxpaths taken by the traffic associated with a demand.

Constraints (1c) ensure that Lxadjacencies have sufficient capacity to carry traffic allocated to Lxpaths. The constraint exists for each Lxadjacency (e) and the summation is over Lxpaths that traverse that adjacency (e).

Constraints (1e) ensure that the capacity allocated for a Lxadjacency is supported by the underlying optical layer path. The summation in constraint (1d) is over L0paths (e) used by the adjacency associated with a demand.

Constraints (1c) ensure that the Lxadjacencies and optical layer paths conform to optical transport network (OTN) standard container sizes and the optical layer constraints. One way that constraint can be expressed is with:
ye∈{K1,K2, . . . ,Km} e∈(2)
where K1, K2, . . . , Kmare container sizes. These constraints may also include limits on the values of capacity available in Lxadjacencies
Le≤ye≤Uee∈(3)
where Leis the lower bound on the capacity of yeand Ueis the upper bound on the capacity of ye.

Constraints (if) ensure that the L0rates correspond to modems on and off states.

Optimization (1) is one example of how this optimization can be formulated. Different formulation options for the optimization, which modify the objective function, or some of the constraints, are also possible. Note that the optimization (1) is an example of an integer programming problem. This type of optimization can be solved using standard integer programming approaches such as branch-and-bound (e.g., A. M. Geoffrion and R. E. Marsten, “Integer Programming Algorithms: A Framework and State-of-the-Art Survey,”Management Science, vol. 18, no. 9, pp. 465-491, 1972). However, solving the optimization in a multi-layer network setting requires specialized algorithms, which are not readily obvious and are presented in the rest of this document.

The optimization can be solved with what is known as the Bender's decomposition algorithm (e.g., J. Benders, “Partitioning procedures for solving mixed-variables programming problems,”Numerische Mathematik, no. 4, pp. 238-252, 1962) through manipulation of constraints (1f). Solving the problem using this decomposition is especially well-suited for a layered solution approach. Bender's decomposition searches for a solution of the space of modem rates zl. This can be written out as an optimization

The process to solve the optimization (1) using Bender's decomposition can be derived using the decomposed optimization (4). The process works in stages. Each stage corresponds to all network states which have the same number of active modems. Use k to denote the number of active modems in the network. A network state is denoted with Sk(j)⊆{where k is the number of active modems in the state and j is the index of the state; there are Nkstates having the same number of active modems k, indexed with j=1, . . . , Nk. The cost of a state is given by

The process also keeps track of modems that must be active in a network state Sk(j), Bk(j). The set Bk(j) is used to avoid checking modems once it is known that they must be on.

In each stage, the process goes through the list of possible modem states and tries to turn all of the modems off in each state. Each time a modem is discovered that can be turned off, a new state with fewer modems is created for the next stage. This way all possible and valid network states can be examined.

The process can be formally stated as follows:1. Start with Sn(1)=, Bn(1)={ }, CLB=C(Sn(1)), N1=1.2. For each stage k<N, going backwards do the followinga. For each set of active modems in the stage Sk(j), j=1, . . . , Nkb. Set jk←1c. For each active modem l∈Sk(j) and not in Bk(j) with cost C(Sk(j)−l)>CUB, check whether Sk(j)−l can support the given traffici. If Sk(j)−l cannot support traffic add l to Bk(j)ii. If Sk(j)−l can support traffic create Sk-1(jk) and increment jkd. Set

CUB=max⁢⁢{CUB,⁢∑l∈ℒ⁢ClRl⁢⁢zl+⁢maxλe≥0,e∈ɛ⁢min{xp,ye}∈𝒩⁢∑e∈ɛ⁢Ce⁢⁢ye+⁢∑e∈ɛ⁢λe(⁢ye-⁢∑l∈ℒe⁢zl⁢⁢)⁢}(5)e. Set Bk-1(jk) to Bk(j) for all jk

Step 1 initializes the sets. Step 2 examines all of the states in the stage and possibly creates new states. Step 2.c tries turning off each active modem in a state to see if that's possible. Two outcomes are possible (2.c.i), the modem cannot be turned off, in which case the modem must remain on in all subsequent stages, (2.c.ii) the modem can be turned off, in which case a new set of active modems is created and appended to the next stage. CUBis the upper bound on the solution, so it can be used to bypass checking modems whose turning off does not decrease the cost enough. The upper bound is obtained using the Lagrangian dual on the constraints involving zl:

The search can be further speeded up by using the Lagrangian dual. The inner maximization indicates which modems should be added to the pool of modems that should stay active. At the optimum of the inner maximization of the Lagrangian dual, λe≥0. For λe>0, it must be true that ye=zl. So, all modems forming adjacency yefor which dual Lagrangian variables are λe>0 can be added to Bk(j).

Modem Reclamation Process Based on Bender's Decomposition

Referring toFIG. 10, in an exemplary embodiment, a flowchart illustrates a modem reclamation process200based on Bender's decomposition of the optimization. Logical separation is shown for which steps are performed by the Lxcontroller34, the inter-layer controller112, and the L0controller30. Of course, other controller implementations are also contemplated. The modem reclamation process200starts (step202). Similar to steps154,156in the modem reclamation process150, the modem reclamation process200includes updating bandwidth available on adjacencies (step204), determining the cost of Lxadjacencies (step206), determining order of Lx connection moves that minimizes total Lx cost (step208), updating Lx adjacency usage and releasing L0capacity (step212), checking if stopping criteria is met (step214), and if so, reclaiming unused modems (step216), and if not, selecting potential modems to remove (step218) and returning to step204. In an exemplary embodiment, the Lxcontroller34performs steps208,210, the inter-layer controller112performs steps204,206,212,214, and the L0controller30performs steps216,218.

Step218determines the next modem to remove, which keeps track of valid network states and tries to turn a modem off. At step218, a list of active modems is available, which corresponds to Sk(j). Bender's decomposition algorithm can then be run from that starting point for as many steps as necessary to obtain the next mode to remove. Once the modem is removed, the connections can be moved to minimize the cost of the optimization (1) with fixed values in constraint (1f). Note, this optimization can be solved using shortest path algorithm using the column generation method. The modem reclamation process200can use dual variables from that optimization to determine the order of connection moves. Using the dual values in shortest path routing ensures that after the connections are moved the cost of the optimization is minimized.

Referring toFIG. 11, in an exemplary embodiment, a flowchart illustrates another modem reclamation process220based on Bender's decomposition of the optimization. Again, logical separation is shown for which steps are performed by the Lxcontroller34, the inter-layer controller112, and the L0controller30. The modem reclamation process220starts (step222). The modem reclamation process220includes determining Lxadjacency capacity bounds (step224), updating bandwidth available on adjacencies (step226), determining cost of Lxadjacencies (step228), determining order of Lxconnection moves that minimizes total Lxcost (step230), moving Lxconnections (step232), updating Lxadjacency usage and releasing L0capacity (step234), checking if stopping criteria is met (step263), and if so, reclaiming unused modems (step238), and if not, selecting potential modems to remove (step240) and returning to step226. In an exemplary embodiment, the Lxcontroller34performs steps224,230,232, the inter-layer controller112performs steps226,228,234,236, and the L0controller30performs steps240,238.

Bender's decomposition_enumerates all possible modem states (on or off) and for each combination of the states and tries to fit traffic in the network. However, the number of enumerated modem states can be decreased by careful selection of the next modem to examine. The selection process tracks which modems have been examined. The selection process tracks which modems do not need to be examined based on mathematical properties of the modem reclamation optimization. Some modems can be disregarded from consideration by examining Lxtraffic to find the minimum required capacity required on each Lxadjacency.

Lagrangian Decomposition

Another way to solve the optimization is by using Lagrangian decomposition. Optimization (1) can be de-layered by removing the joint layer constraints (1d) using Lagrangian theory. To start, relax the constraints (1f) and allow zlto take any value in the interval 0≤zl≤Rl. The Lagrangian cost function for the problem can be obtained by transferring the constraints (1e) into the objective function to obtain the Lagrangian for the optimization problem:

D⁡({λe}e∈ɛ)=min{xp,ye}∈𝒩𝒩⁡({Rl}l∈ℒ)ye∈𝒞0≤zl≤Rl⁢{∑e∈ɛ⁢Ce⁢⁢ye+∑l∈ℒe⁢ClRl⁢⁢zl+∑e∈ɛ⁢λe⁢(⁢ye-⁢∑l∈ℒe⁢zl⁢)⁢},(6)
where({) is the set of valid Lxresource allocations on routes when all modems are on. It is an elementary convex optimization theory result that there is a set of λethat maximize the Lagrangian and that the maximum of the Lagrangian is equal to the minimum of the optimization (1):

The separability of the objective function allows a decomposition of the problem since the sets over which the minimum is defined are disjoint:

The dual problem can be used to solve the optimization with the sub-gradient descent. It is common knowledge from optimization theory that the vector

{y^e-⁢z^l}e∈ɛ
is a sub-gradient of). The following sub-gradient algorithm can then be used to arrive at the optimal solution of the dual problem (7):1. Initialize λe(0)←0 for each e∈2. In each iteration k do the followinga. Find {{circumflex over (x)}p,ŷe}∈that minimize

min0≤zl≤Rl⁢{∑l∈ℒ⁢(ClRl-λl)⁢⁢zl}(9)c. Find the next set of Lagrangian optimizers λe(k+1)

λe⁡(k+1)←max⁢{0,λe⁡(k)+sk(y^e-∑l∈ℒe⁢z^l)}(10)d. Go to next iteration if not sufficiently optimal
∥D({λe(k−)−D({(k−1))∥>ε  (11)for sufficiently small ε.

If it is desirable to pack Lxconnections into L0containers, λl=λein (9) can be replaced with λl=λe+kϵ, where k is the index of the L0 container on the adjacency and ϵ is a small positive number. The dual-based mathematical algorithm can be used to derive a heuristic algorithm for solving the problem. Even though the Lagrangian based process solves the relaxed optimization problem exactly, it is still a heuristic in the sense of the main optimization (1). To get an integer solution, the real values obtained by the algorithm are rounded to integers based on a heuristically set threshold.

Heuristic Process Based on the Lagrangian Dual Descent

Referring toFIG. 12, in an exemplary embodiment, a flowchart illustrates a modem reclamation process250for a heuristic process based on Lagrangian dual descent. Logical separation is shown for which steps are performed by the Lxcontroller34, the inter-layer controller112, and the L0controller30. Of course, other controller implementations are also contemplated.

The modem reclamation process250starts (step252). Similar to steps154,156in the modem reclamation process150, the modem reclamation process200includes determining the cost of Lxadjacencies (step254), determining order of Lx connection moves that minimizes total Lx cost (step256), moving the Lxconnections (step258), updating Lxadjacency usage and releasing L0capacity (step260), checking if stopping criteria is met (step262), and if so, reclaiming unused or lightly used modems (step264), and if not, determining potential L0modem resource assignment (step266) and returning to step254. In an exemplary embodiment, the Lxcontroller34performs steps256,258, the inter-layer controller112performs steps254,260,262and the L0controller30performs steps264,266. The first three steps “Determine potential Lxconnection layout”, “Determine potential L0modem selection”, and “Determine Lxadjacency costs” correspond respectively to equations (8), (9), and (10).

Since the sub-gradient is not necessarily an ascent direction for the dual function, the modem reclamation process250can be improved. The modem reclamation process250can be derived using the so-called sub-gradient bundle calculation (D. Li and X. Sun, Nonlinear integer programming, Springer Science+Business Media, LLC, 2006). The process has two main phases.

The first phase of the process finds a dual ascent guaranteed to increase the value of the dual function. The process terminates when the dual and primal objectives are “close” enough. A test criteria like the one in (11) may be used to establish terminating criteria. After the Lagrangian process terminates a separate procedure goes through and rounds down the modems which are considered to have close to 0 utilization. The second phase of the process removes one or more of the modems from the network. First, a list of connection moves is found using the link costs determined in the first phase. One way to find this list is to solve the optimization (8) using column generation. Modems with the utilization of 0. The next step moves the connections from those modems to free them up. The rate of modems with 0 remaining capacity is then set to Rl=0. The capacity is fixed for the remainder of the algorithm run.

Referring toFIG. 13, in an exemplary embodiment, a flowchart illustrates a modem reclamation process300for another heuristic process based on Lagrangian decomposition with reduced connection churn. Again, logical separation is shown for which steps are performed by the Lxcontroller34, the inter-layer controller112, and the L0controller30. Of course, other controller implementations are also contemplated.

The modem reclamation process300starts (step302). The modem reclamation process300includes determining costs for Lxadjacencies (step304) and simultaneously determining potential Lxconnection layout (step306) and determining potential L0modem resource assignment (step308). After steps306,308, the modem reclamation process300checks if adjacency costs increase dual objective (step310), and if not, returns to step304and if so, the modem reclamation process300includes determining order of Lxconnection moves that minimizes total Lxcost (step312), moving Lxconnections (step314), updating Lxadjacency usage and release L0capacity (step316), checking if stopping criteria is met (step318), and if so, reclaiming unused or lightly used modems (step320), and if not, returning to step304. In an exemplary embodiment, the Lxcontroller34performs steps306,312,314, the inter-layer controller112performs steps304,310,316,318and the L0controller30performs steps308,320.

In the Lagrangian decomposition, determining of Lxlayout may take advantage of finding lower bound for Lxadjacency capacities (described herein). Lxadjacency costs are calculated from bandwidth assignment to modems (determined by L0) and bandwidth assignment to adjacencies (determined by Lx). Each of the steps can be mapped to distributed Lagrangian optimization. Adjacency weights are used in Lxand L0calculations. Several iterations are done before any connections are moved to ensure that connection moves are not wasted. L0optimization requires rounding of the modem bandwidth assignments, which is an NP-complete problem. Rounding algorithm is used based on the reclamation algorithm for unused and lightly used modems. The stopping criteria can be based on the difference between the dual cost and the primal costs. L0costs primary costs can be reported by L0, by adding up the cost of each modem (not visible to the inter-layer controller). Lxcosts are known at the inter-layer controller from the adjacency costs and the loading of adjacencies.

Bounds on LxAdjacency Capacities

Referring toFIG. 14, in an exemplary embodiment, a flowchart illustrates a process400of finding a lower bound on Lxcapacities. The complexity of the search for modems that can be turned off can be reduced by finding the modems that must stay on after the optimization in order to support the existing network traffic. This search can be done in the step in the various processes above that determines the bounds on Lxcapacities. One way to do the search is to use the relaxed version of the optimization and search for lower limits on Lxadjacency capacities yefor which it is impossible to route the traffic. Note that the upper limit on the capacity of yeis given by

The process400finds the lower bound and includes selecting first Lxadjacency (step402), recording current available capacity as lower bound for adjacency (step408), checking if the traffic can be routed (step406), and if so, decreasing available capacity for adjacency (step408) and returning to step404, and if not, checking if this is the last adjacency (step410), and if so, the process400is done (step412), and if not, proceeding to the next adjacency (step414) and returning to step404.

The process400examines the capacity of each Lxadjacency yein iterations starting at the upper bound Ueand decrementing by it by small integer δ in each iteration. In each iteration, the process400checks if it is possible to re-route the traffic with the relaxed version of optimization (1) where the modem variables are allowed to take real values (0≤zl≤Rl). If re-route is not possible, the process400stops examining the adjacency and a lower bound on the required capacity Ueis found. After all the links are re-examined, the original problem can be enhanced with the upper and lower bounds for each virtual adjacency
Le≤ye≤Ue.

Generally speaking, a lower bound like that speeds up calculations since it limits the number of possibilities that should be examined. More specifically, the lower bound allows fixing some of the modems at a rate required to support that minimum required bandwidth and, therefore, it removes the number of modems that should be examined by the Bender's procedure.

Heuristic Reclamation of Unused and Lightly Used Modems

Referring toFIG. 15, in an exemplary embodiment, a flowchart illustrates a heuristic reclamation process500for unused and lightly used modems. Again, logical separation is shown for which steps are performed by the Lxcontroller34, the inter-layer controller112, and the L0controller30. Of course, other controller implementations are also contemplated. The heuristic reclamation process500starts (step502). The heuristic reclamation process500includes setting Lxadjacency capacity bounds, Lxlink costs to zero (step504), determining an amount of capacity required to release a modem on each adjacency (step506), calculating a merit function for each adjacency (step508), setting cost of adjacency with least merit to 1 and target capacity to release modem (step510), determining a list of connection moves minimizing network cost (step512), moving Lxconnections if capacity target met (step514), updating Lxadjacency usage and releasing L0capacity (step516), checking if stopping criteria is met (step518), and if so, reclaiming unused or lightly used modems (step520), and if not, returning to step506. In an exemplary embodiment, the Lxcontroller34performs steps512,514, the inter-layer controller112performs steps504,508,510,516,518, and the L0controller30performs steps506,520.

The heuristic reclamation process500keeps reclaiming modems most likely not required in the network until no more modems can be removed. L0determines the state of utilization of the modems and passes information to the inter-layer controller112. Information can be about a single modem or a list of modems (i.e., capacity used, utilization). The inter-layer controller112calculates a merit function for each adjacency, based on the modem situation. The merit function is designed so that adjacencies with the most under-utilized modems are selected of adjacencies with well-utilized modems. The merit can be utilization as well as utilization plus a random number (e.g., from a normal distribution) to mimic simulated annealing. The results of the merit function are used to assign the costs to adjacency for traffic engineering purposes. Assigning a cost of 1 to the adjacency with the lowest merit ensures traffic is removed from that adjacency during the iteration. Lxconnections are optionally moved if the target capacities are not met. The connections are moved if the target capacities are met. But if the capacities are met, the connections may not be moved, and the current modem is skipped.

Hierarchical Modem Reclamation Through Shared Link Costs

Referring toFIG. 16, in an exemplary embodiment, a flowchart illustrates a hierarchical modem reclamation process552through shared link costs adjustment over three layers. Again, logical separation is shown for which steps are performed by a L1controller34A (e.g., TDM), a L2controller34B (e.g., packet), the inter-layer controller112, and the L0controller30. Of course, other controller implementations are also contemplated. The hierarchical modem reclamation process552includes determining costs and capacity range for L1adjacencies (step552), determining order of L2connection moves that minimizes total L2cost (step554), moving L2connections (step556), releasing L1capacity (step558), determining costs and capacity range for L1adjacencies (step560), determining order of L1connection moves that minimizes total L1cost (step562), moving L1connections (step564), releasing L0capacity (step566), and reclaiming modems with utilization of 0 (step568). In an exemplary embodiment, the L1controller34A performs steps562,564, the L2controller34B performs steps554,556, the inter-layer controller112performs steps552,558,560,566, and the L0controller30performs step568.

Recursive Network Service Orchestration with Hierarchical Path Computation

Referring toFIG. 17, in an exemplary embodiment, a flowchart illustrates a recursive network service orchestration process600with hierarchical path computation. In an exemplary embodiment, the recursive network service orchestration process600can be implemented by the network services orchestrator50. The network service orchestration process600includes initiating a service request for a top layer path (step602), receiving a layer-specific service request (step604), and checking if there is a path with sufficient resources for the request (step606), and if so, allocating resources for the service (step608) and returning service confirmation (step610). If there are not sufficient resources (step606), the network service orchestration process600includes determining required adjacencies (step612), requesting lower layer service for each new adjacency (step614), and checking if lower layer resources are available (step616). If there are lower layer resources available (step616), the network service orchestration process600goes to step608, and if not, the network service orchestration process600includes rejecting the service (step618).

Finding the Minimum Cost Network Layout

Lxrequires the processes to move connections onto paths that minimize the total network cost. Other embodiments presented here are based on optimization theory. For example, solving the traffic engineering optimization using column generation. Either approach can be extended to implement operational extras, such as connections may not be allowed to be moved, the connection may be required to have hot standby protection, connections may have shared restoration based protection, and connections may have Quality of Service (QoS) restrictions such as maximum latency.

Inter-Layer Communications for Modem Allocation on Adjacencies with Insufficient Capacity

Referring toFIG. 18, in an exemplary embodiment, a flowchart illustrates a process700for inter-layer communications for modem allocation on adjacencies with insufficient capacity. Again, logical separation is shown for which steps are performed by the Lxcontroller34, the inter-layer controller112, and the L0controller30. Of course, other controller implementations are also contemplated. The process700includes determining adjacencies with insufficient capacity (step702), requesting capacity increase for adjacencies with insufficient capacity (step704), requesting L0capacity (step706), finding L0modems and fiber path (step708), checking if modems are available, and the path exists (step710), and if not, rejecting the L0 capacity request (step712), rejecting the increase adjacency capacity request (step714), and returning to step702. If modems are available, and the path exists (step710), the process700includes instantiating modems and route (step716), confirming L0capacity request (step718), allocating L0capacity for adjacencies (step720), confirming capacity availability for adjacency (step722), waiting for confirmation (step724), and checking if required Lxcapacity is available (step726), and if not, returning to step724and if so, routing the Lxrequest (step728). In an exemplary embodiment, the Lxcontroller34performs steps702,704,724,726,728, the inter-layer controller112performs steps706,714,720,722, and the L0controller30performs steps708,710,712,716,718.

Creating Adjacencies with Additional Lower Layer Resources

Referring toFIG. 19, in an exemplary embodiment, a flowchart illustrates a process800for creating adjacencies with additional lower layer resources. The process800includes determining potential virtual adjacencies (step802), setting to zero the cost of existing sufficient adjacencies (step804), setting a positive cost of potential new adjacencies (step806), finding a path using existing and potential adjacencies (step808), for each new virtual adjacency (step810), and requesting a lower layer path to connect the adjacency (step812).

If an upper layer cannot provide resources to support requested capacity, it may request new resources from lower layers. Ideally, the newly added lower layer resources complement the existing resources and are added incrementally to maximize the efficiency of used lower layer resources. From the upper layers point of view, a lower layer provides virtual links (adjacencies) between upper layer switching points. If the upper layer does not have full visibility into the lower layer, it needs to request set up of virtual adjacencies from the lower layer.

New adjacencies can be found with shortest path algorithm. To prevent the proliferation of lower layer resources, the upper layer puts a cost to new link creation and uses the shortest path to find new adjacencies. Potential adjacencies are determined from existing adjacencies, and currently inexistent adjacencies through the knowledge of possible adjacencies (i.e. the existence of fiber paths). If a path is found in the graph with all adjacencies known, new virtual adjacencies are the potential adjacencies with positive costs. Each new adjacency represents a new path that should be setup in the lower layer.

Finding a Path in the Lowest Layer (L0)

The lowest layer in the protocol stack provides direct links through the fiber network. These links are in the form of wavelengths connecting switching points, ROADMs, amplifiers, plug-in units, etc. A request for a new wavelength implies that there is a service request coming from one of the upper layers for which the capacity of the existing wavelengths is insufficient. An established wavelength(s) may indeed exist, but it may not have sufficient capacity. A fiber path exists, but no wavelength is established on the path.

When a request for additional L0capacity arrives, the controller in the layer has several options, such as, create a new wavelength to connect the requested points, increase the available capacity on an existing wavelength, if there is one already connecting the requested points, create a new wavelength with higher capacity, transfer existing traffic on it, and release the modem and the wavelength, etc.

When a request for removing L0capacity arrives, the controller has several options including i) do nothing at the time of request, but clean up unused capacity later, ii) if the requested capacity is the only capacity on a wavelength, delete the wavelength, iii) if the requested capacity is not the only capacity on a wavelength, reduce the capacity available on the wavelength, iv) if the requested capacity is not the only capacity on a wavelength, reduce the capacity of the wavelength.

Dedicated Protection

The optimization can be extended to include traffic protection by using a pair of paths for each demand, instead of single paths as in (1). Suppose that each working path in p∈khas a corresponding protection path p′. The two paths can be chosen by finding a shortest cycle instead of shortest path. The optimization can then have two variables for each path pair xpand xp′, corresponding to working and protection bandwidths. The constraints (1c) are updated to reflect the capacity of the restoration bandwidth

⁢xp+∑p′∈𝒫e⁢xp′-ye≤0,e∈ɛ.
Constraints are also added to ensure that working and protection traffics are the same
xp=xp′,p∈k.
Mesh Restoration

The optimization can be enhanced by adding restoration of Lxtraffic in case of individual link failures. We introduce new variables xp(e), corresponding to capacity allocated on path p to route some of the traffic that was previously carried on failed Lxadjacency e. The protection paths are chosen so that diversity requirements are met, by for example ensuring that the protection path does not traverse any of the links in the same shared-link risk group (SRLG) as the failed link. Traffic carried with xp(e)does not carry any of the traffic that was originally on e. To ensure that the traffic can be carried under the failure of each link, in addition to working traffic constraints (1b), we add the following constraints to the optimization

∑p∈𝒫k⁢xp+∑p∈𝒫k⁢xp(e)-∑p∈𝒫e⁢xp≥Dk,e∈ɛ,
which ensure that traffic carried on link e is carried even in the link fails. The second summation adds the restoration traffic, while the third summation removes the failed traffic. Also the available capacity constraints (1c) should be able support both the working and protection traffic

Shared mesh restoration can be added with a following, alternative, set of constraints

∑p∈𝒫e⁢xp+maxef∈ɛ⁢\⁢e⁢{∑p∈𝒫e⁢xp(ef)}-ye≤0,e∈ɛ,
which can be written as two sets of constraints for linear programming with the help of variables wecorresponding the amount of mesh protected traffic traversing link e

Adding the protection and working traffic constraints to the optimization makes a difference inside the algorithms in the step that determines which connections to move in Lx. This can be changed transparently without changing the general outlines any of the algorithms.

Exemplary Controller

Referring toFIG. 20, in an exemplary embodiment, a block diagram illustrates a server900, which can be used to realize various aspects of the modem reclamation systems and methods. In an exemplary embodiment, one or more servers900can form the various controllers described herein. The server900can be a digital computer that, in terms of hardware architecture, generally includes a processor902, input/output (I/O) interfaces904, a network interface906, a data store908, and memory910. It should be appreciated by those of ordinary skill in the art thatFIG. 20depicts the server900in an oversimplified manner, and a practical embodiment may include additional components and suitably configured processing logic to support known or conventional operating features that are not described in detail herein. The components (902,904,906,908, and910) are communicatively coupled via a local interface912. The local interface912can be, for example, but not limited to, one or more buses or other wired or wireless connections, as is known in the art. The local interface912can have additional elements, which are omitted for simplicity, such as controllers, buffers (caches), drivers, repeaters, and receivers, among many others, to enable communications. Further, the local interface912can include address, control, and/or data connections to enable appropriate communications among the aforementioned components.

The processor902is a hardware device for executing software instructions. The processor902can be any custom made or commercially available processor, a central processing unit (CPU), an auxiliary processor among several processors associated with the server900, a semiconductor-based microprocessor (in the form of a microchip or chip set), or generally any device for executing software instructions. When the server900is in operation, the processor902is configured to execute software stored within the memory910, to communicate data to and from the memory910, and to generally control operations of the server900pursuant to the software instructions. The I/O interfaces904can be used to receive user input from and/or for providing system output to one or more devices or components. User input can be provided via, for example, a keyboard, touchpad, and/or a mouse. System output can be provided via a display device and a printer (not shown). I/O interfaces904can include, for example, a serial port, a parallel port, a small computer system interface (SCSI), a serial ATA (SATA), a fibre channel, Infiniband, iSCSI, a PCI Express interface (PCI-x), an infrared (IR) interface, a radio frequency (RF) interface, and/or a universal serial bus (USB) interface.

The network interface906can be used to enable the server900to communicate on a network, such as in the networks10,60, etc. The network interface906can include, for example, an Ethernet card or adapter (e.g., 10BaseT, Fast Ethernet, Gigabit Ethernet, 10 GbE) or a wireless local area network (WLAN) card or adapter (e.g., 802.11a/b/g/n). The network interface906can include address, control, and/or data connections to enable appropriate communications on the network. A data store908can be used to store data. The data store908can include any of volatile memory elements (e.g., random access memory (RAM, such as DRAM, SRAM, SDRAM, and the like)), nonvolatile memory elements (e.g., ROM, hard drive, tape, CDROM, and the like), and combinations thereof. Moreover, the data store908can incorporate electronic, magnetic, optical, and/or other types of storage media. In one example, the data store908can be located internal to the server900such as, for example, an internal hard drive connected to the local interface912in the server900. Additionally, in another embodiment, the data store908can be located external to the server900such as, for example, an external hard drive connected to the I/O interfaces904(e.g., SCSI or USB connection). In a further embodiment, the data store908can be connected to the server900through a network, such as, for example, a network attached file server.

The memory910can include any of volatile memory elements (e.g., random access memory (RAM, such as DRAM, SRAM, SDRAM, etc.)), nonvolatile memory elements (e.g., ROM, hard drive, tape, CDROM, etc.), and combinations thereof. Moreover, the memory910can incorporate electronic, magnetic, optical, and/or other types of storage media. Note that the memory910can have a distributed architecture, where various components are situated remotely from one another, but can be accessed by the processor902. The software in memory910can include one or more software programs, each of which includes an ordered listing of executable instructions for implementing logical functions. The software in the memory910includes a suitable operating system (O/S)914and one or more programs916. The operating system914essentially controls the execution of other computer programs, such as the one or more programs916, and provides scheduling, input-output control, file and data management, memory management, and communication control and related services. The one or more programs916may be configured to implement the various processes, algorithms, methods, techniques, etc. described herein.

SDN Management Plane

Referring toFIG. 21, in an exemplary embodiment, a block diagram illustrates functional components of an SDN environment1000, in which the modem reclamation systems and methods can operate. The SDN environment1000includes a programmable infrastructure layer1102, a control layer1104, and an application layer1106. The layers1104,1106can be implemented on a server or the like such as illustrated inFIG. 20and the functional components can be implemented in software executed on the server. The programmable infrastructure layer1102includes network devices such as the network elements26and the switches32and is communicatively coupled to the control layer1104via an interface1110such as OpenFlow, for example. The control layer1104facilitates communication between the application layer1106and the network elements26and the switches32in programmable infrastructure layer1102. The control layer1104includes SDN control software1112with a plurality of network services1114. The control layer1104provides SDN functionality to manage network services through abstraction of lower level functionality. The application layer1106communicates with the control layer1104through various Application Programming Interfaces (APIs)1116. The application layer1106provides end user connectivity to the SDN environment1000such as software modules and/or functions responsible for creating the desired path and flow connections on the physical network through various business applications1118. In an exemplary embodiment, the systems and methods described herein are implemented as one of the business applications1118on an SDN controller and/or on a separate server900.