Search

Middleboxes have gained popularity due to the significant value-added services these network elements provide to traffic flows, in terms of enhanced performance and security. Policy-aware traffic flows usually need to traverse multiple middleboxes in a predefined order to satisfy their associated policy, also known as Service Function Chaining . Typically, Middleboxes run on specialized hardware, which make them highly inflexible to handle the unpredictable and fluctuating-nature of traffic, and contribute to significant capital and operational expenditures (Cap-ex and Op-ex) to provision, accommodate, and maintain them. Network Function Virtualization is a promising technology with the potential to tackle the aforementioned limitations of hardware middleboxes. Yet, NFV is still in its infancy, and there exists several technical challenges that need to be addressed, among which, the Virtual Network Function assignment problem tops the list. The VNF assignment problem stems from the newly gained flexibility in instantiating VNFs (on-demand) anywhere in the network. Subsequently, network providers must decide on the optimal placement of VNF instances which maximizes the number of admitted policy-aware traffic flows across their network. Existing work consists of Integer Linear Program (ILP) models, which are fairly unscalable, or heuristic-based approaches with no guarantee on the quality of the obtained solutions. This work proposes a novel Logic-Based Benders Decomposition (LBBD) based approach to solve the VNF assignment problem. It consists of decomposing the problem into two subproblems: a master and a subproblem; and at every iteration constructive Benders cuts are introduced to the master to tighten its search space. We compared the LBBD approach against the ILP and a heuristic method, and we show that our approach achieves the optimal solution (as opposed to heuristic-based methods) 700 times faster than the ILP.

Multi-access edge computing (MEC) has recently emerged as a novel paradigm to facilitate access to advanced computing capabilities at the edge of the network, in close proximity to end devices, thereby enabling a rich variety of latency sensitive services demanded by various emerging industry verticals. Internet-of-Things (IoT) devices, being highly ubiquitous and connected, can offload their computational tasks to be processed by applications hosted on the MEC servers due to their limited battery, computing, and storage capacities. Such IoT applications providing services to offloaded tasks of IoT devices are hosted on edge servers with limited computing capabilities. Given the heterogeneity in the requirements of the offloaded tasks (different computing requirements, latency, and so on) and limited MEC capabilities, we jointly decide on the task offloading (tasks to application assignment) and scheduling (order of executing them), which yields a challenging problem of combinatorial nature. Furthermore, we jointly decide on the computing resource allocation for the hosted applications, and we refer this problem as the Dynamic Task Offloading and Scheduling problem, encompassing the three subproblems mentioned earlier. We mathematically formulate this problem, and owing to its complexity, we design a novel thoughtful decomposition based on the technique of the Logic-Based Benders Decomposition. This technique solves a relaxed master, with fewer constraints, and a subproblem, whose resolution allows the generation of cuts which will, iteratively, guide the master to tighten its search space. Ultimately, both the master and the sub-problem will converge to yield the optimal solution. We show that this technique offers several order of magnitude (more than 140 times) improvements in the run time for the studied instances. One other advantage of this method is its capability of providing solutions with performance guarantees. Finally, we use this method to highlight the insightful performance trends for different vertical industries as a function of multiple system parameters with a focus on the delay-sensitive use cases.

Middleboxes (i.e., firewall, cache, proxy, etc.) are hardware appliances designed to enforce security and performance policies. Being an integral part of today’s cloud and enterprise networks, these middleboxes are expensive, hard to manage and to maintain. Network function virtualization has emerged as a promising technology that replaces these hardware appliances by software ones known as virtual network functions (VNFs). Unlike hardware middleboxes, VNFs can be instantiated and deployed on virtual machines running on commodity servers which ensures their flexibility, manageability, cost-efficiency, and reduce their time-to-market. However, efficiently processing services through an ordered chain of VNFs, called service function chaining (SFC), is not trivial. It requires solving three inter-related sub-problems; the network functions (NFs) mapping sub-problem, the traffic routing sub-problem and the service scheduling sub-problem. This paper first highlights the existing interplay between the three sub-problems and then presents a formulation of the SFC scheduling (SFCS) which exploits interactions between NFs mapping onto VNFs, service scheduling and traffic routing. Given the complexity of the SFCS problem, we present a novel primal–dual decomposition using column generation that solves exactly a relaxed version of the problem and can serve as a benchmark approach. We enhance our solution methodology with a diversification technique to help improve the quality of the obtained solutions. We evaluate numerically our method and show that it can attain optimal solutions substantially faster. Finally, we present several engineering insights for improving the network performance.

This paper considers the problem of jointly constructing and scheduling forwarding trees in a wireless sensor network, each to collect measurements from a group of sensor nodes at a single sink node. The goal is to construct such trees that gather measurements in the most energy efficient manner and with minimal gathering latency. We assume transmissions (carrying measurements) on wireless links interfere with one another, and thus, appropriate link scheduling is required to manage interference. We refer to this problem as forwarding tree construction and scheduling (FTCS). Each tree may be constructed independently, and then, its links are scheduled. However, when all trees are combined together, the shortest and energy efficient schedule may not be guaranteed. Furthermore, a large number of possible forwarding trees for each group of sensors may be considered. Both problems of enumerating forwarding trees and scheduling links for those trees are hard combinatorial problems. This is compounded by the fact that the two problems must be solved jointly, to guarantee the selection of the best forwarding trees that, when their links are scheduled, guarantee a shortest energy efficient schedule. After highlighting the complexity of the FTCS problem, we present a novel primal-dual decomposition method using column generation. We also highlight several challenges we faced when solving the decomposed problem and present efficient techniques for mitigating those challenges. One major advantage of this paper is that it can serve as a benchmark for evaluating the performance of any low complexity method for solving the FTCS problem for larger network instances, where no known exact solutions can be found.

Ethernet Ring Protection (ERP) switching has emerged to provide sub-50 ms of restoration times, allowing Ethernet technologies to expand beyond enterprises to next generation metro and backbone networks, providing much needed services to interconnect for instance dispersed and high-bandwidth data centers. This paper considers the problem of efficiently designing and planning an Ethernet-based metro network with ERP protection method. While previous recent work has addressed such design problem, none has considered the capabilities of exploiting multiple ERP instances, leaving behind some advantages that network providers could tap into to provide their customers with desirable quality of service support. Resource planning in ERP-based Ethernet network is, however, a complex problem due to the challenges associated with the logical link block selection as well as ring hierarchy selection. ERP instances add, however, another dimension of combinatorial complexity, making the design problem completely intractable. To address this issue, we resort to large scale optimization tools and present a novel primal-dual decomposition of the original problem using column generation. We show that our method is very scalable and obtain several design insights on various representative network instances.

Ethernet Ring Protection (ERP) has recently emerged to provide protection switching for Ethernet ring topologies with sub-50 ms failover capabilities. In addition to Ethernet's cost-effectiveness and simplicity, ERP's promise to also provide protection in mesh packet transport networks positions Ethernet as a prominent competitor to conventional SONET/SDH and the technology of choice for carrier networks. Higher service availability, however, in ERP mesh networks has been challenged by the issue of network partitioning and the contention for protection resources which may be caused by concurrent failures. In this paper, we show that in a mesh network designed to withstand only single failure situations, network services usually suffer from two outage categories subject to concurrent dual-link failures. We address the problem of minimal capacity network design to provide high service availability against concurrent dual-link failures. We cast this combinatorially complex design problem as an optimization one and show that higher service availability can be achieved by proper RPL (Ring Protection Link) placement and ring hierarchy selection. The objective is to maximize the network flow under any dual-link failure scenario. Our design achieves minimal capacity allocation that minimizes the number of service outages (up to 37%) therefore achieving higher service availability. Numerical evaluation and comparative study show that the joint desgin approach of the ILP model provisions 8% less capacity than the sequential two-step approach to achieve similar service availability.

In this paper, we develop a design methodology of survivable Wavelength Division Multiplexing (WDM) networks based on pre-configured protection structures (p-structures) to support multiple classes of Quality-of-Protection (QoP). We elaborate a generic mathematical optimization method that could be used to provide n QoP levels R"i (i=1,...,n) provided that the network topology is (n+1)-connected. The added value of the p-structure approach is studied through the analysis of the required protection capacity to efficiently meet the needs of the supported n QoP levels. Furthermore, the protection capabilities and shapes of the protection building blocks of the p-structure and p-cycle schemes are compared to each others in order to gain an insight into how the flexibility of the p-structure scheme helps in meeting the requirements of multiple QoP levels. The computation results show that, depending on the network connectivity, up to 150% of protection capacity can be saved if p-structures are used rather than p-cycles. The analysis of the shapes of the optimal p-structures shows that, depending on the targeted QoP levels, the optimal mix of p-structures is very often composed of large and small structures with high and low protection capabilities, respectively.

This paper introduces a combinatorial problem arising from real-world business requirements as part of resource allocation in Cloud Management. In particular, we focus on the allocation of a set of heterogeneous resources serving multiple tenants with different service level agreements. There exist certain business rules that govern the application stemming from privacy, performance, and capacity requirements. We show how to formulate the problem as constrained optimization and then solve it efficiently using Artificial Intelligence based constraint propagation. Our approach stands out as a high-level, declarative solution that is efficient and easy to maintain and update.

This paper considers the problem of jointly constructing and scheduling forwarding trees in a wireless sensor network, each for a group of sensor nodes, to collect measurements at a single sink node. The goal is to construct such trees which gather measurements in the most energy efficient manner and minimal gathering latency. We assume transmissions (carrying measurements) on wireless links interfere with one another, and thus appropriate link scheduling is required to overcome interference. We refer to this problem as Forwarding Tree Construction and Scheduling (FTCS). Each tree may be constructed independently and then its links are scheduled. However, when all trees are combined together, the shortest and energy efficient schedule may not be guaranteed. Further, a large number of possible forwarding trees for each group of sensors may be considered. Both problems of enumerating forwarding trees and scheduling links for those trees are hard combinatorial problems. This is compounded by the fact that the two problems must be solved jointly, to guarantee the selection of best forwarding trees which, when their links are scheduled, guarantee a shortest energy efficient schedule. After highlighting the complexity of the FTCS problem, we present a novel primal-dual decomposition method using column generation. We also highlight several challenges we faced when solving the decomposed problem and present efficient techniques for mitigating those challenges. One major advantage of our work is that it can serve as a benchmark for evaluating the performance of any low complexity method for solving the FTCS problem for larger network instances where no known exact solutions can be found.

This paper investigates design methods of protection schemes in survivable WDM networks that use preconfigured protection structures (p-structures) in order to provide different quality-of-recovery (QoR) classes within 100% resilient single-link protection schemes. QoR differentiation is a practical and effective approach in order to strike different balances among protection cost, recovery delay, and management complexity. Based on the degree of pre-cross connectivity of the protection structures, we develop three design approaches of shared protection capacity schemes based on the following: 1) fully pre-cross-connected p-structures (fp-structures); 2) partially pre-cross-connected p-structures (pp-structures); and 3) dynamically reconfigured p -structures (dp -structures). In order to identify the optimal combinations of protection structures to meet the requirements of the three QoR classes, we use a column generation (CG) model that we solve using large-scale optimization techniques. Our CG decomposition approach is based on the separation processes of the design and selection of the protection structures. In the design process of the protection structures, the shape and protection capability of each p-structure is decided dynamically during the selection process depending on the network topology and the targeted QoR parameters. Extensive experiments are carried out on several data instances with different design constraints in order to measure the protection capacity cost and the recovery delay for the three QoR classes.

The protected working capacity envelope (PWCE) concept was proposed by Grover (2004) in order to simplify network operations and management in survivable wavelength division multiplexing (WDM) networks. In this paper, we focus on the design of PCWE and investigate a new design method based on column generation (CG) for designing survivable WDM networks based on p-cycle PWCE. Proposed design algorithms for PWCE and p-cycle proceed in two steps: A first step where a large (sometimes huge) number of cycles is enumerated followed by a second step where the selection of the most promising p-cycles is made with the help of combinatorial optimization tools. In this paper, we develop a new (single-step) method based on large scale optimization tools, that is, CG techniques, where the generation of cycles is dynamic and embedded within the optimization process. The key advantage of CG techniques is that no a priori cycle enumeration step is required ahead of the optimization process: The generation of the relevant cycles, only one or few at a time, is embedded in the optimization process. We conducted intensive computational experiments to compare the performances of our CG algorithms with four other algorithms in the literature. The different algorithms were compared with regard to several design metrics and running time. Results obtained in the experiments on five different network instances show that the CG-based algorithm outperforms by far all proposed algorithms in the literature, both with respect to the scalability (much smaller computing times for large network instances) and also with respect to the quality of the solutions.

Network survivability is a key design issue for optical transport mesh networks. Various survivability schemes have been introduced among which p-cycle has (and continues) attracted quite a lot of attention because of its fast and efficient protection capabilities. The concept of p-cycle has been generalized to pre-cross-connected trails, or p-trails, by exploiting the fact that providing pre-cross-connected protection paths and obtaining fast restoration do not necessarily require a cyclic structure as in p-cycles. In this paper, we investigate the benefits and sharing capabilities of p-trails and observe that non-simple p-trails and p-cycles can be built from merging simple trails. We derive two ILP models for survivable network design using p-trails. Our first design model is a simple ILP whose optimal solution relies on the exhaustive enumeration of all simple trails in the network. We observe that the size of our ILP model, and therefore the computation time, become prohibitively large making the model unpractical for larger network instances. Therefore, to overcome this scalability issue, we develop an enhanced model for this complex optimization problem using the column generation (CG) decomposition technique. Our developed design approach is shown to be very scalable, as opposed to other prior p-trail design methods; further, we show that p-trails are more efficient than p-cycles in terms of protection resource redundancy in the network.

We propose a novel protection approach for the design of link-protection schemes in survivable Wavelength Division Multiplexing mesh networks by merging the well-known p-cycle- and p-tree-protection structures. So doing, we aim at gathering the advantages of p-cycles in terms of protection capabilities, and of p-trees in terms of protection flexibilities (local re-routing, scalability) in a single protection scheme. As opposed to existing protection schemes based on protection structures with a pre-defined shape, the building blocks of the new scheme are protection structures with unrestricted shapes. Thus, they allow more flexibility in provisioning spare capacity, and provide higher capacity efficiency when compared to the shaped-protection schemes that have been proposed so far. In order to cope with the size of the solution space which includes all the possible protection structures, we propose an efficient and scalable optimization technique in large-scale systems named column generation (CG). In our CG-based optimization approach, the shape of a candidate protection structure is dynamically decided during the optimization process according to a link spare capacity budget. Experimental results on different network instances show that the protection plan resulting from the merging of p-cycle and p-tree structures is, on average, ~15% less capacity redundant and ~15% more reliable than the pure p-cycle one. It also requires, on average, ~30% less protection structures. In addition, those structures provide backup paths ~30% smaller than those of the p-cycle-based scheme.

This paper presents a Constraint Programming (CP)-based application for dynamic cache distribution in Oracle Coherence In-Memory Data Grid (IMDG). A re-sizable decomposition method using CP is developed to ensure high availability through incremental optimization of load distribution and data replication. The application highlights the flexibility and efficiency that the CP technology offers for (1) concisely capturing the multiple dynamic aspects and complex constraints of the Oracle Coherence IMDG cache distribution problem; and (2) solving large-scale problem instances in a dynamic cloud environment. Extensive computational results are presented to assess the scalability and efficiency of the proposed solution.

Ethernet Ring Protection (ERP) switching has emerged to provide sub-50ms of restoration times, allowing Ethernet technologies to expand beyond enterprises to Next Generation Metro and Backbone networks, providing much needed services to interconnect dispersed data centers. This paper considers the problem of efficiently designing and planning an Ethernet based metro network with ERP protection method. While previous recent work has addressed such design problem, none has considered the capabilities of exploiting multiple ERP instances, leaving behind some advantages that network providers could tap into to providing their customers with desirable quality of service support. Resource planning in ERP based Ethernet networks is however a complex problem due to the challenges associated with the logical link block selection as well as ring hierarchy selection. ERP instances add however another dimension of combinatorial complexity, making the design problem completely intractable. To address this issue, we resort to large scale optimization tools and present a novel primal-dual decomposition of the original problem using column generation. We show that our method is very scalable and obtain several design insights on various representative network instances.

While many have advocated for the use of Virtual Local Area Networks (VLANs) as a way to provide scalable traffic management, finding the optimal traffic split (mapping) among VLANs to achieve load balancing has turned out to be a very challenging and combinatorially complex problem to solve. This paper considers the traffic engineering problem in data center networks by studying the joint problem of finding spanning trees for VLANs and optimally selecting the most promising spanning trees to map the traffic flows onto. We mathematically model this problem using Integer Linear Program (ILP) techniques and follow a primal-dual decomposition approach, using column generation, to solve exactly a relaxed mapping version of the problem, as well we present approximate solutions to the original problem. We show through numerical evaluations an outstanding scalability of the decomposed version of the problem and we use our results to study the performance of traffic engineering protocols developed in recent literature for data center networks. NPRP 5-137-2-045 grant from the Qatar National Research Fund (a member of the Qatar Foundation). Scopus

Ethernet Ring Protection (ERP) has recently emerged to provide protection switching for Ethernet ring topologies with sub-50 ms failover capabilities. ERP's promise to also provide protection in multi-ring mesh packet transport networks will position Ethernet as a serious competitor to conventional SONET/SDH and the technology of choice for carrier networks. Operating ERP in multi-ring mesh networks however comes with unique challenges. This paper presents an optimal ERP capacity design formulation by jointly solving the problem of routing, RPL placement, and ring hierarchy selection. When prior work relied on exhaustive enumeration, our current design is formulated as an integer linear program (ILP) which is shown to be both more capacity and computationally efficient.

Given the relatively low costs associated with its deployment and its capacity to deliver last mile wireless broadband access, WiMAX and LTE are the current technologies of choice to effectively meet the increasing demand for high bandwidth services and applications. In the literature, several pseudo scheduling algorithms, which are very often time-independent, have been proposed to optimize the scheduling horizon without taking care of the sequencing of packets within the scheduling period. In this paper, we develop an optimization model having in mind to perform "true" scheduling, not only optimizing the scheduling horizon but taking into account the allocation of resources over a given time window. We propose a two-step solution scheme. The first step relies on a model, which chooses among a set of possible configurations (a set of transmitting links over a predetermined period of time slots) with end-to-end transmissions. The second step consists in a time ordering of those configurations, in order to complete the scheduling process. In our experiments, we compare our solution scheme with one of those so-called "scheduling" in order to investigate how the throughput varies depending on whether we use pseudo=scheduling vs. "true" scheduling. The results show how explicitly considering nodal buffers can make a meaningful difference on the forms of scheduling, depending on the assumptions on the buffer sizes.

Survivability is a key issue in the design of optical mesh networks. Various survivability schemes have been introduced among which p-cycle has been attracting quite a lot of attention because of its fast and efficient protection capability. The concept of p-cycle was later generalized to pre-cross-connected trails or p-trails, by noting to the fact that providing pre-cross-connected protection paths and obtaining fast restoration does not require a cyclic structure. In this paper, we investigate the capability of p-trails in protecting traffic demands in a mesh-based survivable network. By taking the sharing capability of p-trails into account, we introduce optimization models to verify the remarkable efficiency of p-trails. We derive two ILP models for survivable network design using p-trails. In our first model, the optimal solution is obtained from a candidate set constructed by exhaustive enumeration of all simple trails. We observe that the size of our ILP model, and therefore the computation time, become prohibitively large making the model unpractical for larger network instances. Therefore, to overcome this scalability issue, we develop a better model for this complex optimization problem using a primal-dual decomposition of the original problem based on the column generation (CG) optimization method. Our developed design approach is shown to be very scalable, as opposed to other prior p-trail design methods; further, we show that p-trails are more efficient than p-cycles in terms of resource redundancy in the network.

Survivability is an essential feature in the design of WDM mesh networks for continuous service delivery in the case of failures. Segment p-cycles (also known as flow p-cycles) offer an interesting protection approach with a good trade-off between protection capacity cost and recovery speed.

In today optical WDM networks, capacity expansion is performed by the addition of transport blades (e.g., transceivers) at end nodes of optical fibers. It allows the multiplexing of optical channels (wavelengths) with different granularities. In this paper, we propose a new ILP-based design approach of survivable WDM multi-granularity segment p-cycle where the objective is to minimize the cost of spare equipment at switching nodes in order to provide 100% single link failure protection. We use column generation (CG) optimization techniques, an efficient large scale optimization tool, in order to integrate, in an on-line fashion, the p-cycles generated during the optimization process. We, therefore, avoid a time and space costly prior enumeration of the candidate p-cycles. Extensive experiments are conducted to compare the proposed nodal equipment cost optimized design of segment p-cycles with the classical link spare capacity optimization approach. Numerical results show that the protection design corresponding to spare node equipment optimization is more effective than the one based on link spare capacity.

The emerging next generation optical transport WDM networks, with reconfigurable optical switches, offer a promising solution to the ever-increasing demand for high bandwidth and flexible connectivity. In order to meet the needs of such a demand, the trend in current backbone and access network development is moving toward a unified solution that will support different classes of service such as voice, data, and a large range of multimedia applications. However, those applications come with different qualities of service (i.e., bandwidth, reliability, and availability) depending on their requirements and on how much the users are willing to pay for the services. In the design of protection schemes in survivable WDM networks, there is a trade-off to be set between the capacity efficiency and the quality of service parameters. Differentiation of the provided quality of service can help in finding an appropriate trade-off between network cost and quality of service, for both service providers and customers. In this paper, we propose different network design optimization models in order to optimize two Quality of Service (QoS) protection parameters: Protection capacity sharing and recovery delay. We use shared protection schemes based on preconfigured structures that are pre-cross connected ahead of failures, and that are dynamically reconfigured in case of a failure. The resulting optimization models are solved using large scale optimization tools in order to ensure scalable solutions. Comparisons are conducted on different network and traffic instances, and a thorough analysis is made, exploring the added values of pre-cross connected protections structures on protection QoS.

We propose a new design scheme of resilient Wavelength Division Multiplexing (WDM) networks by extending and reshaping pre-configured protection tree (p-tree) structures. The resulting protection scheme relies on optimized pre-cross connected structures that span all previously proposed protection patterns. p-Tree-based protection schemes offer the advantages of scalability, local restoration capabilities, and failure impact restriction, but at the same time suffer from capacity inefficiency. While keeping these advantages, we propose an extension (reshaping) of the p-tree protection pattern that imposes no restriction on the shapes of the protection building blocks. Not only the resulting protection scheme remains scalable and highly flexible, but it also leads to pre-configured protection structures that improve much further on capacity efficiency and recovery delay. We establish some new integer linear programming models, and use a large scale optimization tool, named column generation (CG) to solve them. Our CG-based solution method is highly scalable as it does not require an a priori explicit enumeration of the protection structures, but an efficient dynamic enumeration of only the most promising ones. Comparison are made with three other protection schemes, i.e, simple and non-simple p-cycles (fully pre-cross connected structures) as well as p-trees. Results show a clear advantage of the proposed extended-tree scheme with respect to flexibility, capacity efficiency, and restoration delay.

We propose a new way to design a Protected Working Capacity Envelope (PWCE) in survivable WDM networks by using pre-configured protection structures with unrestricted shapes (arbitrary shape patterns). So far, the pre-configured cycle (p-cycle) structure is the only building block that has been used in the design of PWCEs. In this paper, we do not impose any restriction on the shapes of the protection building blocks, rather, we search for p-structures in the network that favor the protection efficiency (reliability, redundancy) and recovery delay (local recovery). In order to cope with the large solution space, we use an efficient large scale optimization technique that relies on Column Generation (CG) where only globally most promising p-structures are enumerated on the fly during the optimization process. We compare the capacity efficiency, the reliability, and the average length of the backup paths of our PWCE design approach with the p-cycle based one. The results show that a design based on unrestricted p-structure patterns is ∼ 10% less capacity redundant, ∼ 15% more reliable, and allow recovery along shorter backup paths compared to the p-cycle based scheme.

We propose a new design approach of survivable WDM networks using simple and non-simple p-cycles-based protected working capacity envelope (PWCE). We investigate the added-value of the non-simple p-cycles over simple p-cycle protection method in terms of capacity efficiency and reliability. As opposed to the prevalent two-step design approach where an explicit enumeration of all/set of p-cycles step is performed ahead of an optimization step, we develop a new optimization approach using a large scale optimization tool named column generation technique, where only few globally optimal cycles are generated dynamically during the optimization process. We conduct performance evaluation experiments on various network topologies, using different metrics in order to measure the added- value of the non-simple p-cycles over simple p-cycles in the design of survivable WDM networks based on PWCE. It is shown that depending on the network topologies, and in particular of their connectivity, significant protection improvement can be achieved when using non simple p-cycles.

Ethernet ring protection (ERP) has recently emerged to provide protection switching for Ethernet ring topologies with sub-50-ms failover capabilities. ERP's promise to also provide protection in multi-ring mesh packet transport networks will position Ethernet as a serious competitor to conventional synchronous optical networking (SONET)/synchronous digital hierarchy (SDH) and the technology of choice for carrier networks. Operating ERP in multi-ring mesh networks, however, comes with unique challenges. This paper reveals some limitations of prior work which relied on exhaustive enumeration and proposes some modifications to overcome these subtle limitations. We also present an optimal ERP design formulation by jointly solving the problem of ring protection link placement and ring hierarchy selection whose objective is to minimize the overall capacity requirement. Our design approach is formulated as an integer linear program, which is shown to provide optimal capacity provisioning and be computationally scalable.