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

Cloud Computing is becoming a mainstream paradigm, as organizations, large and small, begin to harness its benefits. This novel technology brings new challenges, mostly in the protocols that govern its underlying infrastructure. Traffic engineering in cloud data centers is one of these challenges that has attracted attention from the research community, particularly since the legacy protocols employed in data centers offer limited and unscalable traffic management. Many advocated for the use of VLANs as a way to provide scalable traffic management, however, finding the optimal traffic split between VLANs is the well known NP-Complete VLAN assignment problem. The size of the search space of the VLAN assignment problem is huge, even for small size networks. This paper introduce a novel decomposition approach to solve the VLAN mapping problem in cloud data centers through column generation. Column generation is an effective technique that is proven to reach optimality by exploring only a small subset of the search space. We introduce both an exact and a semi-heuristic decomposition with the objective to achieve load balancing by minimizing the maximum link load in the network. Our numerical results have shown that our approach explores less than 1% of the available search space, with an optimality gap of at most 4%. We have also compared and assessed the performance of our decomposition model and state of the art protocols in traffic engineering. This comparative analysis proves that our model attains encouraging gain over its peers.

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

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.

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.

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.

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.

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

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