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.

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.

We investigate the achievable performance gain that network coding (NC) when combined with successive interference cancellation (SIC) brings to a multihop wireless network. While SIC enables concurrent receptions from multiple transmitters, NC reduces the transmission time-slot overhead, and each of these techniques has shown independently great benefits in improving the network performance. We present a cross-layer formulation for the joint routing and scheduling problem in a wireless network with NC (with opportunistic listening) and SIC capabilities. We use the realistic signal-to-interference-plus-noise ratio (SINR) interference model. To solve this combinatorially complex nonlinear problem, we decompose it (using column generation) to two linear subproblems--namely opportunistic NC aware routing and scheduling subproblems. Our scheduling subproblem consists of activating noninterfering NC components, rather than links, which do not interfere with each other and will be used to route the traffic. We further extend our design to consider a multi-rate multihop wireless network with interference cancellation capabilities. We use numerical evaluation to present the achieved performance gain and compare our work to three other models: a base model with no NC and SIC, a model with only NC, and a model with only SIC capabilities. The numerical results show that our proposed method (both with and without variable transmission rate selection) achieves performance gains that range between moderate and significant for the various considered scenarios. Such improvements are attributed to the joint capabilities of SIC and NC in effectively controlling the interference and improving the spatial reuse.

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.

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 provide protection in mesh packet transport networks positions Ethernet as a prominent competitor to conventional SONET/SDH and as the technology of choice for carrier networks. Higher service availability, however, in ERP has been challenged by the issue of network partitioning and contention for shared capacity caused by concurrent failures. In this paper, we show that in a network designed to withstand single-link failure, the service availability, in the presence of double link failures, depends on the designed ERP scheme, i.e., the RPL placement as well as the selection of ring hierarchy. Therefore, we present a study for characterizing service outages and propose a design method which strikes a balance between capacity requirement and service availability (i.e., the number of service outages resulting from concurrent failures). We observe that through effective design, remarkable reduction in service outages is obtained at a modest increase in capacity deployment.

The recent Ethernet Ring Protection (ERP) method brings new challenges into the design of next generation Ethernet carrier networks. This letter addresses one of the design challenges that may confront a network operator in its migration to provide ERP capabilities over an existing network. The objective of the design is to properly allocate network resources to maximize the service provider's revenue given the per-link deployed capacity. We formulate this problem of resource allocation as an optimization model with the objective of maximizing the network flow using the well-known max-min approach. Our proposed model ensures fairness among the admissible flows and the design of a proper protection plan to survive against any single link failure. Numerical results show that the proposed design approach can increase the overall network flow by up to 44.7% in comparison to an arbitrarily designed ERP network while it allocates bandwidth 29.3% more fairly among the sessions.

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.

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

In this paper, we study the performance of multi-hop wireless networks when both proper interference control and effective spatial reuse are jointly considered. For the former, we assume nodes endowed with Successive Interference Cancellation (SIC) capabilities at the physical layer and for the latter, we advocate joint link scheduling and power allocation. We study the achievable performance of such networks through a cross-layer design framework. We formulate the joint problem of routing, link scheduling and power allocation as a mixed integer non-linear program (MINLP) and we use column generation (CG) to decompose and linearize it, and hence, solve it. Our numerical results show that when SIC and power control are combined, around 75% performance improvement in dense networks may be achieved in comparison with a network that does not incorporate any advanced interference management techniques.

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 has been challenged by the issue of network partitioning caused by concurrent failures. In this paper, we show that in a network designed to withstand only single failure situations, the service availability in the presence of dual failures is affected by the design method, i.e., the RPL placement as well as the selection of ring hierarchy. Therefore, we present a study for characterizing service outages and propose a design method which strikes a balance between capacity requirement and service availability (i.e., the number of service outages resulting from concurrent failures). We observe that by properly selecting the RPL positions and the ring hierarchies, remarkable reduction in service outages is obtained (hence higher service availability in the presence of dual failures) at a modest increase in capacity deployment. Numerical results show that our design approach can reduce the number of service outages as much as 39.1% with only 6.9% additional investment in capacity deployment.

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 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.

International audience; This work introduces a new shared segment protection scheme that ensures both node and link protection in an efficient manner in terms of cost and bandwidth, while taking full advantage of the optical hop endpoints of the primary logical hops (induced by the routing) without adding extra ones for protection. As opposed to the link or path protection schemes, the segment protection scheme has been less studied although it offers an interesting compromise between those two protection schemes, attempting to encompass all their advantages. We investigate two different Shared Segment Protection (SSP) schemes: Basic Shared Segment Protection (BSSP) and Shared Segment Protection with segment Overlap (SSPO), and propose a design of 100\% single segment protections. In SSPO, we study the extra protection capabilities, node failure and dual link failure survivability, offered by the single 100\% single segment protection. For both BSSP and SSPO schemes, we propose two novel efficient ILP formulations, based on a column generation mathematical modeling. While (SSPO) offers the advantage over (BSSP) to ensure both node and link protection, it is not necessarily much more costly. Indeed, depending on the network topology and the traffic instances, it can be shown that none of the two SSP schemes dominates the other one. Therefore, the SSPO protection scheme should be favored as it offers more protection, i.e., it adds the node protection to the link protection at the expense of a minor additional cost.

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 flexible design approach of protection plans in survivable WDM networks by using protection structures with no predefined shapes in order to maximize the protected working capacity in an end-to-end basis. Previous design approaches of survivable WDM based on Protected Working Capacity Envelope (PWCE) have looked at the optimization problem of maximizing the protected capacity on a link basis, independently of the source and destination nodes of the potential traffic. Moreover, those approaches have only investigated the design problem with pre-configured protection cycles (p-cycles).

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.

We investigate the dimensioning of 3G wireless networks with a CDMA2000 radio interface technology. These networks offer a range of multimedia services that require different end-to-end QoS. In order to meet this QoS, dimensioning of a 3G network must include an handshake between the radio and the core networks and therefore involve the three networks (radio, core, access). In this paper we primarily address the problem of optimizing the base station locations and the core network link capacity with different multimedia traffic scenarios and different QoS and GoS requirements. The dimensioning problem is formulated as a mixed integer program (MIP) problem and solved by a tabu search (TS) algorithm that relies on the signal to noise plus interference ratio (SNIR) to guide its search strategy. In order to improve the efficiency of the tabu search, we study extensively various of its key features: (i) search intensification through dynamic tabu lists and aspiration criteria; (ii) search diversification through restarts using new base station locations. We next conduct experiments with the resulting tabu search (TS) on quite large instances. The MIP formulation can be used to evaluate the quality of those solutions. It is then showed that the TS solutions are almost optimal on small instances and requires much less resources than the approximated solutions obtained with the MIP formulations, even for larger instances.

This paper investigates design methods of protection schemes in survivable WDM networks using the path protection p-trail in order to provide better capacity efficiency by eliminating the rigidness of the protection structure of the well-accepted protection scheme, the failure independent path protection (FIPP) pre-configured protection cycle (p-cycle). The flexibility in the protection structure yields lower cost in terms of spare capacity allocation while maintaining the high speed of protection switching. We develop two design approaches, the fully pre-cross-connected path protection trail (fpp-trail) and the partially pre-cross-connected path protection trail (ppp-trail), based on the degree of pre-cross-connectivity of the protection structure. In order to obtain optimally designed trails, we develop an optimization model based on a large-scale optimization technique, namely, column generation. Numerical results show that fpp-trails significantly improve the spare capacity efficiency compared to the FIPP p-cycle, and ppp-trails strike a balance between capacity redundancy and recovery delay. We observe that ppp-trails can achieve as low capacity redundancy as shared backup path protection (SBPP), while the recovery delay is kept lower than in SBPP and slightly higher than FIPP p-cycles by using selective signaling through a control plane that is aware of the location of the cross-connects that are not pre-configured in advance.

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.