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.

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.

The military tactical logistics planning problem addresses the issue of distributing heterogeneous commodities (e.g., food, medical supplies, construction material, ammunition, etc.) to forward operating bases in a theatre of operations using a combination of heterogeneous transportation assets such as logistics trucks and tactical helicopters. Minimizing the logistics operating cost while satisfying the operational demands under time and security constraints is of high importance for the Canadian Armed Forces. In this study, a logistics planning model is developed to explore the trade-offs between the effectiveness and efficiency in military tactical logistics distribution. A mathematical optimization algorithm based on Column-and-Cut generation techniques is developed to find the fleet mix and size of transportation assets to meet different Quality-of-Support (QoS) parameters. This paper presents details of a new column generation decomposition approach and a solution algorithm along with an application example to demonstrate the methodology. Extensive computational results are presented in order to measure the degree of efficiency and scalability of the proposed approach, and to analyze the trade-offs between: (1) delivery time and operating cost; (2) security and operating cost.

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.

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.