This paper proposes a backup computing and transmission capacity allocation model for virtual networks that minimizes the required backup computing capacity under multiple facility node failures. The proposed model adopts the probabilistic protection, where the probability that the protection fails due to insufficient capacity is restricted not to be greater than a given survivability parameter, by using robust optimization. The conventional model allocates the backup computing capacity by considering the probabilistic protection but allocates the transmission capacity for all backup paths dedicatedly. The proposed model allocates the backup transmission capacity only for the failure patterns that are considered under the probabilistic protection guarantee; the probabilistic protection is considered for both computing and transmission capacity allocation. Reducing the required backup transmission capacity can also reduce the required backup computing capacity, since more feasible solutions for backup computing capacity allocation can exist. We introduce a heuristic algorithm to solve the backup computing and transmission capacity allocation problem. Numerical results show that the proposed model reduces the required backup transmission capacity and enhances the feasibility of allocating virtual networks compared with the conventional model. We also observe that reducing the required backup transmission capacity can lead to reducing the required backup computing capacity.

Middleboxes work as software which runs on a general-purpose server by adopting network function virtualization. The unavailability of middlebox is a key metric. The previous study considers allocating backup servers to middleboxes to reduce the unavailability. While it adopts shared protection to save backup capacity, resource sharing has not been sufficiently explored as each middlebox can only use one backup server. This paper presents a backup allocation model in which a function can be protected by two backup servers and a backup server can protect multiple functions under a shared protection strategy to minimize the maximum unavailability among functions. We use Markov chain to analyze the state transitions and make equilibrium-state equations. By solving them, we obtain the probability of each state of the allocation and compute an unavailability of function. We introduce two algorithms to examine the proposed model; one of them uses the performance bound of the maximum unavailability which is analyzed in this paper. Numerical results show that the proposed model reduces the maximum unavailability by 9.5–51.2% compared to a baseline model that allocates one backup server for each middlebox in our examined cases.

This article proposes an optimization model for the network service (NS) mapping and scheduling problem with uncertain processing time in network function virtualization. We model processing time uncertainty through the$\Gamma$-robustness approach, which provides different degrees of robustness against processing time uncertainty. We formulate the problem with the objective to minimize the worst-case makespan over the given uncertainty set. We show the NP-hardness of considered problem. A heuristic that divides the problem into subproblems is presented to tackle it. For the subproblem in which mapping and scheduling decisions are given, we develop an algorithm with polynomial time complexity to calculate the worst-case makespan over the uncertainty set, which has a better scalability than the corresponding mixed integer linear programming (MILP) problem and obtains the same worst-case makespan with the MILP problem. The numerical results show that the proposed model outperforms the conventional model with deterministic parameters in terms of worst-case makespan.

Network function virtualization enables to deploy network services more flexibly with virtual network functions (VNFs). A service provider needs to allocate the required VNFs to hosts, with satisfying different requirements on service delay. It is challenging for service providers to deploy services as efficiently as possible. The previous work has addressed this challenge by studying that multiple services share a VNF instance whose computing capacity is fixed; different VNF instances do not share their computing resources. More efficiency is expected with sharing resources among different VNF instances. This paper proposes a service deployment model for network function virtualization to minimize the deployment cost with capacity sharing and priority queuing. In the proposed model, VNF instances on the same host share the computing capacity in the host by VNF resizing during runtime. In addition, the priority queuing system is applied to each host. We formulate the proposed model as an optimization problem to minimize the service deployment cost. We develop a solution strategy named FlexSize to solve it heuristically in practical time. We evaluate the proposed model with a baseline which does not share the computing capacity among VNF instances in the host. The numerical results show that the proposed model reduces the service deployment cost compared with the baseline.

Network function virtualization enables service providers to flexibly deploy network services. The existing works mainly focus on function placement and capacity allocation without exploring traffic scheduling for service deployment, by adopting a first-in-first-out policy. It introduces inefficiency considering that different services vary in the delay requirements. This paper proposes a service deployment model with priority queuing for both traffic processing and transmission to minimize the deployment cost with satisfying the service delay constraints. We analyze the problem including proving its NP-hardness and the convexity of a subproblem. Based on the analysis, we develop a reinforcement learning-based approach to address the problem in a decomposition manner with a polynomial-time complexity in each episode. Several specific designs are introduced to fit the learning-based approach to the considered deployment problem with priority queueing. The numerical results show that the introduced approach achieves an objective value comparable to the optimal one obtained by brute force search with a computation time$10^{3}$times shorter. Compared to a conventional model with the first-in-first-out policy, the proposed model reduces the deployment cost by adopting a more flexible queueing policy.

In a cloud, protection through backup of virtual machines contained in physical machines (PMs) reduces damage to users due to failure of PMs, such as hardware malfunctions. However, from a resource cost perspective, it is necessary to reduce the amount of capacity for backup while limiting the probability of unsuccessful protection. Existing studies suggest the method of sharing backup capacity among primary resources, but the amount of capacity reduction required to protect is limited. This paper proposes a backup resource allocation model with two-stage probabilistic protection to minimize the total required backup capacity for multiple simultaneous failures of PMs. In probabilistic protection, backup resources are allocated so that the probability of backup failure does not exceed a given survivability parameter which represents the acceptable probability of backup failure. Probabilistic protection which achieves efficient sharing of backup capacity enables flexible allocation and reduces the required backup capacity. In order to increase the flexibility of backup capacity allocation, the proposed model extends the probabilistic protection to two stages. By dividing the protection into two stages, the weight of probability between stages can be adjusted, enabling more effective capacity sharing. Since it is uncertain which primary PMs fail, we apply robust optimization to the probabilistic protection. By using a table that takes into account the survivability parameter and the failure probability of PMs, the proposed model is formulated as a mixed integer linear programming problem. We prove the NP-hardness of considered problem. A heuristic is introduced to solve the optimization problem. The proposed model can reduce the total required backup capacity compared to the models with dedicated protection and one-stage probabilistic protection. The model can also provide protection in a range of survivability parameters that the model with one-stage probabilistic protection cannot satisfy.

This paper proposes a preventive priority setting model to minimize the worst-case maximum utilization ratio against multiple controller failures in software defined networks. For a set of controllers able to manage a switch, we introduce a priority for each controller to become the main controller that controls the switch. Once the existing main controller fails, the survived controller which has the highest priority works as the main controller. This reassignment is automatically obtained according to the priority setting decided at the network operation start time. In this way, the proposed model provides a prompt recovery with reducing the network instability due to unnecessary controller reassignment. We formulate the proposed model in two different forms, which are an integer linear programming formulation and a min-max formulation. We prove that the considered problem is NP-hard. A basic heuristic is introduced based on the min-max formulation. Its two extensions are further developed considering the accuracy and the computation time in practical computation. Numerical results reveal that, compared to two baselines that sacrifice certain network stability to achieve a more flexible reassignment, the proposed model reduces the network instability by 27% and 52% in average, respectively, with obtaining the comparable maximum utilization ratio.

This paper proposes a robust function deployment model against uncertain recovery time with satisfying an expected recovery time guarantee in a cost-efficient manner. We consider that each node fails with a workload-dependent failure probability, which is a non-decreasing function that reveals the empirical relationship between the workload and the failure probability. The preventively deployed backup resources can recover an unavailable function hosted by a failed node in a period of time, which is related to the backup strategies and failure and recovery scenarios. We introduce an uncertainty set that considers the upper and lower bounds of the recovery time of a function by each node that protects it and the upper bound of the average recovery time among nodes. The robust optimization technique is applied to handle the worst case of expected recovery time satisfying a time guarantee under an uncertain recovery time. With this technique, the model is formulated as a mixed integer linear programming problem. The numerical results reveal that the proposed model saves the deployment cost on average 24% compared to a baseline that uses the deterministic recovery time in our tested cases.

This paper proposes an availability-aware service provisioning model with backup sub-chain-enabled sharing in network function virtualization to minimize the deployment cost. A sub-chain consists of a set of ordered VNFs that corresponds to a part of or the whole function chain of a service. Different from a conventional model in which a backup sub-chain is dedicated to protecting a primary sub-chain of one service, the proposed model allows the backup sub-chain sharing among services to reduce the deployment cost. Due to the complexity of the investigated problem, a heuristic is designed to tackle it. The numerical results show that the proposed model achieves lower deployment cost with satisfying the availability requirement than the conventional one.

Network operators can operate services in a flexible way with virtual network functions thanks to the network function virtualization technology. Flow partition allows aggregated traffic to be split into multiple parts, which increases the flexibility. This paper proposes a service deployment model with flow partition to minimize the total deployment cost with meeting service time delay requirements. A virtual network function of a service is allowed to have several instances, each of which hosts a part of flows and can be shared among different services, to reduce the initial and proportional cost. We provide the mathematical formulation for the proposed model. A heuristic algorithm is introduced to solve the original problem in practical time by decomposing it into several steps; each step handles a convex problem. The numerical results reveal that the proposed model saves the total deployment cost compared to the conventional one. It improves the maximum admissible traffic scale by 23% in average in our examined cases.

Multi-access edge computing (MEC) enables users to exploit the resources of cloud computing at a base station (BS) in proximity to the users where an MEC server is hosted. While we have advantage of being able to communicate with low latency and small network load in MEC networks, the resources in BSes are limited. One challenge is where to provide users with services from to make efficient use of resources. Furthermore, to enhance the reliability of MEC system, the case that a BS fails needs to be considered. This paper proposes a service placement and user assignment model with preventive start-time optimization against a single BS failure in MEC networks. The proposed model preventively determines the service placement and user assignment in each BS failure pattern to minimize the worst-case penalty which is the largest penalty among all failure patterns. We formulate the proposed model as an integer linear programming problem. We introduce two algorithms, one is the greedy algorithm with allocation upgrade and the other is with allocation upgrade and preemption, to solve the problem. The results show that the introduced algorithms obtain a solution with the smaller worst-case penalty than the benchmark in a practical time.

Middleboxes work as software which runs on a general-purpose server by adopting a network function virtualization. The unavailability of middlebox is a key metric. The previous study considers allocating backup servers to middleboxes to reduce the unavailability. While it adopts shared protection to save backup capacity, resource sharing has not been sufficiently explored as each middlebox can only use one backup server. This paper presents a backup allocation model in which a function can be protected by two backup servers and a backup server can protect multiple functions under a shared protection strategy to minimize the maximum unavailability among functions. We use Markov chains to analyze the state transitions and make equilibrium-state equations. By solving them, we obtain the probability of each state of the allocation and compute an unavailability of function. We introduce two algorithms to examine the proposed model; one of them uses the performance bound of the maximum unavailability which is analyzed in this paper. Numerical results show that the proposed model reduces the maximum unavailability by 13.9-51.2% compared to a baseline model that allocates one backup server for each middlebox in our examined cases.

This paper proposes a backup resource allocation model with two-stage probabilistic protection to minimize the total required backup capacity for multiple simultaneous failures of physical machines (PMs). Probabilistic protection ensures that the probability that the PM used for backup fails to backup due to lack of computing capacity does not exceed a given survivability parameter. The proposed model protects the primary virtual machines by allocating computing capacity to backup PMs with probabilistic protection. Since it is uncertain which primary PMs fail, we apply robust optimization to the probabilistic protection. By using a table that takes into account the survivability parameter and the failure probability of PMs, this proposed model is formulated as a mixed integer linear programming problem. The proposed model extends the probabilistic protection to two stages; the VMs that fail to be protected in the first stage are protected in the second stage to achieve the probabilistic protection with the final survivability parameter. This model can reduce the total required backup capacity compared to the conventional model with one-stage probabilistic protection.

This paper proposes an optimization model to derive a resilient virtual network function (VNF) allocation aiming to maximize the number of accepted requests with considering VNF diversity and ensuring the requirements of node fault tolerances in a dynamic scenario, where the requests have random requirements, arriving and releasing time. The model considers fault tolerance assurance and satisfies the service requirements under different error patterns. The allocation provided by the proposed model ensures the required amount of processing ability in the situation that there are several failed nodes. The node fault tolerance can be set variously for different requirements of services. The proposed model selects and instantiates suitable replicas from the pools of replicas, and then determines the locations of these replicas instances. We develop a reinforcement learning approach for solving the proposed model including the design of the learning environment and the reward shaping. The numerical results show that the proposed model increases the number of accepted requests with ensuring the resiliency of the functions compared with baseline models in the examined cases, where the allocation of a request can be determined in tens of milliseconds.

This article proposes a primary and backup resource allocation model that provides a probabilistic protection guarantee for virtual machines against multiple failures of physical machines in a cloud provider to minimize the required total capacity. A physical machine allocates both primary and backup computing resources for virtual machines. When any failure occurs, the survived physical machines with preplanned backup resources recover the virtual machines on the failed physical machines and take over the workloads. The probability that the protection provided by a physical machine does not succeed is guaranteed within a given number. Providing the probabilistic protection can reduce the required backup capacity by allowing backup resource sharing, but it leads to a nonlinear programing problem in a general-capacity case against multiple failures. We apply robust optimization with extensive mathematical operations to formulate the primary and backup resource allocation problem as a mixed integer linear programming problem, where capacity fragmentation is suppressed. We prove the NP-hardness of considered problem. A heuristic is introduced to solve the optimization problem. The results reveal that the proposed model saves about one-third of the total capacity in our examined cases; it outperforms the conventional models in terms of both blocking probability and resource utilization.

This paper proposes a survivable virtual network embedding model over elastic optical networks considering shared protection against any single substrate node or link failure. A virtual network request is embedded in the substrate network with allocating the primary and backup resources which are node-disjoint. Modulation selection and spectrum allocation with constraints from elastic optical networks are considered in the embedding procedure. We consider the backup computing and transmission resource sharing to reduce the required backup resources. We formulate the proposed model as an integer linear programming problem to minimize the rejection ratio for a given set of virtual network requests. We introduce a greedy-based approach that promotes resource sharing to handle the larger-size problem in a practical time. In order to further improve the performance on the objective value, a deep reinforcement learning-based approach with polynomial time complexity in each episode is developed to solve the problem in multiple stages. We design a dedicated learning agent for each stage considering the problem property. We analyze the usages of different approaches based on performance evaluation. The numerical results show that, compared to a conventional model that adopts dedicated protection, the proposed model with shared protection reduces the rejection ratio by 15% on average in our examined cases.

This paper proposes a sub-chain-enabled coordinated protection model for the availability-guaranteed service function chain (SFC) provisioning, which considers the availability of each component to constitute an SFC, including links and VNFs. Unlike conventional protection models providing certain protection for the whole chain, the proposed model configures sub-chains for each SFC and provides proper protection for each sub-chain to achieve the required availability in a cost efficient way. We formulate the proposed model as an optimization problem to minimize the deployment cost. A game approach is presented to tackle the problem. The numerical results show that the proposed model outperforms the conventional ones in terms of deployment cost; the game approach has scalability of tackling the proposed model as the problem size increases.

This paper proposes an optimization model to derive a primary and backup resource allocation considering a workload-dependent failure probability to minimize the maximum expected unavailable time (MEUT). The workload-dependent failure probability is a non-decreasing function which reveals the relationship between the workload and the failure probability. The proposed model adopts hot backup and cold backup strategies to provide protection. The cold backup strategy is a protection strategy, in which the requested loads of backup resources are not activated before failures occur to reduce resource utilization with the cost of longer recovery time. The hot backup strategy is a protection strategy, in which the backup resources are activated and synchronized with the primary resources to recover promptly with the cost of higher workload. We formulate the optimization problem as a mixed integer linear programming (MILP) problem. We prove that MEUT of the proposed model is equal to the smaller value between the two MEUTs obtained by applying only hot backup and cold backup strategies with the same total requested load. A heuristic algorithm inspired by the water-filling algorithm is developed with the proved theorem. The numerical results show that the proposed model suppresses MEUT compared with the conventional model which does not consider the workload-dependent failure probability. The developed heuristic algorithm is approximately 105times faster than the MILP approach with 10−2performance penalty on MEUT.

Fault tolerance and load balancing are two key roles in resource allocation against failures. This paper proposes a primary and backup resource allocation model with preventive recovery priority setting to minimize a weighted value of unavailable probability (W-UP) against multiple failures. W-UP considers the probability of unsuccessful recovery and the maximum unavailable probability after recovery among physical nodes. We consider that each node fails with a workload-dependent failure probability; each failure pattern occurs with a probability. The workload-dependent failure probability is a non-decreasing function revealing an empirical relationship between the workload and the failure probability for each physical node. We introduce a recovery strategy to handle the workload variation which is determined at the operation start time and can be applied for each failure pattern. Once a failure pattern occurs, the recoveries are operated according to the priority setting to promptly recover the functions hosted by failed nodes. We also discuss an approach to obtain unsuccessful recovery probability with considering the maximum number of arbitrary recoverable functions by a set of available nodes without the priority setting. We formulate the optimization problem as a mixed integer linear programming (MILP) problem. We develop a heuristic algorithm to solve larger size problems in a practical time. The developed heuristic algorithm is approximately 729 times faster than the MILP approach with 1.6% performance penalty on W-UP. The numerical results observe that the proposed model reduces W-UP compared with baselines.

This paper proposes a service deployment model for network function virtualization to minimize the deployment cost with capacity sharing and priority queuing. A service provider needs to allocate the the required virtual network functions (VNFs) to hosts, with satisfying different requirements on service delay. In the previous work, it has been studied that multiple services share a VNF instance whose computing capacity is fixed; different VNF instances do not share their computing resources. In the proposed model, VNF instances on the same host share the computing capacity in the host by VNF resizing during runtime. In addition, the priority queuing system is applied to each host. We formulate the proposed model as an optimization problem to minimize the service deployment cost. We develop a solution strategy named FlexSize to solve it heuristically in practical time. We evaluate the proposed model with a baseline which does not share the computing capacity among VNF instances in the host. The numerical results show that the proposed model reduces the service deployment cost compared with the baseline.

This paper proposes a backup resource allocation model for virtual network functions (VNFs) to minimize the total required backup computing capacity with considering the service delay. If random failures occur to primary hosts, the VNFs in failed hosts are recovered by backup hosts, where the allocation is determined in advance. We introduce the probabilistic protection, where the probability that the protection provided by a backup host fails is limited within a given value; it allows backup resource sharing to reduce the total required computing capacity. The previous work formulated the backup resource allocation problem without considering the service delay as a mixed integer linear programming (MILP) problem by adopting the robust optimization. We consider the delay of services, which consists of networking delay between hosts and processing delay in each requested VNF. The probability that the total delay of a service exceeds its threshold is constrained within a given value. To solve the problem with the delay constraint, we introduce an algorithm with two methods to make the MILP problem be aware of the service delay. The results observe that, compared to the baseline, the proposed model can reduce the total required backup capacity of computing resource.

This paper proposes an optimization model to derive the resilient virtual network function allocation in service function chains aiming to reduce the recovery time during the migrations from the primary functions to backup functions. We consider k-fault-tolerance assurance and satisfy the service requirements under different error patterns in this model. The allocation provided by the proposed model ensures that the processing ability satisfies the requirements even though there are k failed nodes in the network. Diversity splits a single VNF into a pool of replicas with different specifications. The diversity of both primary and backup functions are considered. Redundancy is used for recovering the failed functions. We formulate the proposed model as a mixed integer linear programming problem to select suitable replicas from the pools of replicas and decide the locations of these replicas for both primary and backup functions. The objective of the proposed model is to minimize the sum of the maximum recovery time among functions under all possible failure patterns which have k node failures. The numerical results show that the proposed model reduces the recovery times of VNFs with ensuring the resiliency of the functions compared with baseline models in the examined cases. We give some methods to improve the maximum resiliency at last.

Network function virtualization enables service providers to flexibly provision services with virtual network functions. Traffic uncertainty typically exists in a network, which can degrade the performance of a virtual network function. This paper proposes a robust virtual network function deployment model against the traffic uncertainty to minimize the total deployment cost with satisfying the service delay constraint. A virtual network function instance is allowed to be shared by different services to reduce the initial and proportional costs. We describe the traffic uncertainty from different aspects with considering the characteristics in the context of network function virtualization. We formulate the robust deployment problem as a mixed integer second-order cone programming problem. A heuristic algorithm is introduced to solve the problem polynomially by decomposing the original problem to several convex problems. The numerical results reveal that the proposed model saves the deployment cost in average 27% compared to a baseline that uses the deterministic traffic arrival rate, in our examined scenarios.

Resource allocation and management is a key role in network function virtualization to improve the reliability of network services. Kubernetes is a system to deploy and manage the virtual network functions automatically. Existing tools in Kubernetes does not provide a resource type to define the backup Pods. It does not provide automatic resource management based on the user requests for the backup Pods, either. This paper designs and implements a custom resource and the corresponding controller in Kubernetes to manage the primary and backup resources of network functions. The custom resource is a set of Pods with different types, which includes primary, hot backup, and cold backup Pods. The controller manages the set of Pods and maintains the current state of the different types of Pods to keep the current state consistent with the desired state of each type of Pod. Demonstration validates that the controller automatically manage the primary and backups resources correctly.

Diversity in network function virtualization is to use a group of thin replicas to provide the network services under the required processing ability. Redundancy is to provide a certain number of replicas against function failures and improve network reliability. Kubernetes is a system to deploy and manage virtual network functions automatically. Existing tools in Kubernetes do not provide a resource type to provide required functions jointly considering VNF diversity and redundancy. This paper designs and implements a custom resource and the corresponding controller in Kubernetes to manage the VNF diversity and redundancy jointly. The controller selects suitable replicas from a pool of replica templates to satisfy the required processing ability with the minimum required number of replicas and converts the backup functions to the primary functions when the primary functions cannot provide the required ability. Demonstration validates that the controller automatically manages the resources correctly, improves the resource utilization, and increases the number of acceptable requests.

Network function virtualization provides an efficient and flexible way to implement network functions deployed in middleboxes as software running on commodity servers. However, it brings challenges for network management, one of which is how to manage the unavailability of middleboxes. This article proposes an unavailability-aware backup allocation model with the shared protection to minimize the maximum unavailability among functions. The shared protection allows multiple functions to share the backup resources, which leads to a complicated recovery mechanism and makes unavailability estimation difficult. We develop an analytical approach based on the queueing theory to compute the middlebox unavailability for a given backup allocation. The heterogeneous failure, repair, recovery, and waiting procedures of functions and backup servers, which lead to several different states for each function and for the whole system, are considered in the queueing approach. We analyze the performance bounds for a given solution and for the optimal objective value. Based on the developed analytical approach and the performance bounds, we introduce two heuristics to solve the backup allocation problem. The results reveal that, compared to a baseline model, the proposed unavailability-aware model reduces the maximum unavailability 16% in average in our examined scenarios.

This paper proposes a backup computing and transmission resource allocation model for virtual networks with providing a probabilistic protection against multiple facility node failures. The proposed model aims to find the allocation to minimize the required backup computing capacity, which guarantees the probability that the protection fails due to insufficient reserved backup computing capacity within a given value. The previous study only considers the backup computing resource allocation for virtual nodes regardless of the network aspects. In this paper, backup transmission resource allocation is incorporated, where the required backup transmission capacity can affect the required backup computing capacity. We analyze backup transmission resource sharing in the case of multiple facility node failures to compute the minimum required backup transmission capacity. A heuristic algorithm is introduced to solve the problem; especially, several techniques based on graph theory are developed to handle the problem with full backup transmission resource sharing. The result observes that the proposed model outperforms a baseline with dedicated protection for computing resource. Furthermore, the application scenarios for the proposed model with different degrees of backup transmission resource sharing are analyzed. With our analyses, a network operator can set an appropriate degree of backup transmission resource sharing based on practical requirements.

This paper proposes a main and secondary controller assignment model against multiple controller failures in software defined networks considering latency between switches and controllers. The survivability guarantee of each switch is satisfied by assigning a set of controllers, where one of them works as the main controller to control the switch. Given assigned controllers, we introduce a policy-based approach to automatically specify the main controllers in each failure pattern, which leads to a lightweight configuration on a switch. We define the average-case expected latency, the worst-case expected latency, and the expected number of switches within a latency bound, as three objectives to be optimized in three different problems. We prove that a low latency first policy achieves the optimal objective for each considered problem. We formulate the proposed controller assignment model with different goals as three mixed integer linear programming problems. We prove the NP-completeness for all the three problems. A greedy algorithm with polynomial time complexity is developed; we show that it provides a 1/2-approximation for the case without the survivability guarantee constraint. The numerical results observe that the proposed model obtains the optimal objective value with the computation time about$10^{2}$times shorter than that of a baseline that introduces decision variables to determine the main controllers.

This article proposes a network design model to minimize the worst-case network congestion against multiple link failures, where open shortest path first link weights are determined at the beginning of network operation. In the proposed model, which is called the preventive start-time optimization model against multiple link failures (PSO-M), the number of multiple link failure patterns to support is restricted by introducing a probabilistic constraint calledprobabilistic guarantee. If the total probability of non-connected failure patterns does not exceed a specified probability, PSO-M provides a feasible solution of link weights. Otherwise, no feasible solution can be obtained. We introduce an extended model of PSO-M, called PSO-M with link reinforcement (PSO-MLR), where links are reinforced under a budget constraint. Link reinforcement in PSO-MLR has two purposes: maintaining network connectivity and reducing the worst-case congestion ratio. Numerical results show that PSO-M offers lower worst-case congestion ratios than the start-time optimization model, where link weights are obtained against the non-failure pattern assuming that multiple link failures are possible. The superiority of PSO-M strengthens as the average node degree of the network increases. Given a fixed budget, PSO-MLR allows the worst-case congestion ratio to be varied within a specific range. PSO-MLR can support a part of non-connected failure patterns to determine link weights, and so is a valuable enhancement of PSO-M.

This paper proposes a robust optimization model for probabilistic protection with multiple types of resources to minimize the required backup capacity for each type of resource against multiple random failures of physical machines in a cloud provider. If random failures occur, the required capacities for virtual machines are allocated to the preplanned backup physical machines, which are determined in advance. Probabilistic protection restricts the probability that the workload caused by failures exceeds the backup capacity by a given survivability parameter. We introduce three survivability parameters for central processing unit (CPU), memory, and the entire cloud provider considering both CPU and memory. By using the relationship between the three survivability parameters, the proposed model guarantees probabilistic protection for each resource, CPU and memory, and the entire cloud provider. By adopting the robust optimization technique, we formulate the proposed model as a multi-objective mixed integer linear programming problem. To deal with the multi-objective optimization problem, we apply the lexicographic weighted Tchebycheff method with which a Pareto optimal solution is obtained. We show that our proposed model reduces the average value between the backup capacity ratios of CPU and memory compared with the conventional model. A multi-objective simulated annealing (MOSA) and nondominated sorting genetic algorithm II (NSGA-II) are adopted to solve larger size problems. By using them, approximate solutions are obtained for larger size problems. In addition, we find that NSGA-II searches for solutions more effectively than MOSA, in our backup capacity allocation problem.

The availability schedule provides information on whether each network node is available at each time slot. The service interruptions caused by node unavailability marked in availability schedule can be suppressed if the functions are allocated according to the availability schedule. However, the given availability schedule may have gaps with the actual one and influence the VNF allocation. This paper proposes a robust optimization model to allocate virtual network functions (VNFs) in service function chains (SFCs) for time slots in sequence aiming to maximize the continuous available time of SFCs in a network with uncertain availability schedules by suppressing the interruptions caused by node unavailability marked in availability schedule and function reallocation. We formulate the problem as a mixed integer linear programming (MILP) problem over the given uncertainty set of the start time slot and period of unavailability on each node in the availability schedule. For solving the model in a practical time in a relative large size of network, we develop a heuristic algorithm. The numerical results show that the proposed model outperforms the baseline models under different levels of robustness in terms of the worst-case minimum number of the longest continuous available time slot in each SFC. The heuristic algorithm reduces the computation time with limited performance loss compared with the MILP approach. In the discussion, we introduce a constraint condition for the maintenance ability, which reduces the size of uncertainty set, and an extension for supporting more than one unavailability periods in the availability schedule on each node.

A suitable virtual network function (VNF) placement considering a node availability schedule extends service continuous serviceable time by suppressing service interruptions caused by function reallocation and node unavailabilities. However, function placement cannot avoid service interruptions caused by node unavailabilities. This paper proposes a primary and backup VNF placement model to avoid service interruptions caused by node unavailabilities by using backup functions. The considered backup functions have a period of startup time for preparation before they can be used and the number of them is limited. The proposed model is formulated as an integer linear programming problem to place the primary and backup VNFs based on the availability schedule at continuous time slots. We aim to maximize the minimum number of continuously available time slots in all service function chains (SFCs) over the deterministic availability schedule. We obverse that the proposed model considering the limited number of backup functions outperforms baseline models in terms of the minimum number of longest continuous available time slots in all SFCs. We introduce an algorithm to estimate the number of key unavailabilities at each time slot, which can find the unavailable nodes which are the bottlenecks to increase the service continuous available time at each time slot.

This paper proposes an optimization model to derive the virtual network function (VNF) allocation of time slots in sequence aiming to maximize the continuous available time of service function chains (SFCs) in a network. The proposed model suppresses service interruptions otherwise created by the unavailability of virtual machines (VMs) and the reallocation of VNFs. The proposed model computes VNF allocation in a series of time slots based on a VM availability schedule, which provides information on the availability of each VM in each time slot. We formulate the proposed model as an integer linear programming (ILP) problem with the goal of maximizing the minimum number of longest continuous available time slots in each SFC. We prove that the decision version of the VNF allocation problem (VNFA) is NP-complete. As the size of ILP problem increases, the problem is difficult to solve in a practical time. We develop a heuristic algorithm to solve the VNFA problem. Numerical results show that the proposed model improves the continuous available time of SFCs compared with existing models, which partially consider VM unavailability or VNF reallocation. We observe that the proposed model together with a consideration of routing reduces the path length of requests. The developed heuristic algorithm is faster than the ILP approach with a limited performance penalty.

This paper proposes a multiple backup resource allocation model with a workload-dependent failure probability to minimize the maximum expected unavailable time (MEUT) under a protection priority policy. The workload-dependent failure probability is a non-decreasing function which reveals the relationship between the workload and the failure probability. The proposed model adopts hot backup and cold backup strategies to provide protection. For protection of each function with multiple backup resources, it is required to adopt a suitable priority policy to determine the expected unavailable time. We analyze the superiority of the protection priority policy for multiple backup resources in the proposed model; we provide the theorems that clarify the influence of policies on MEUT. We formulate the optimization problem as a mixed integer linear programming (MILP) problem. We provide a lower bound of the optimal objective value in the proposed model. We prove that the decision version of the multiple resource allocation problem in the proposed model is NP-complete. A heuristic algorithm inspired by the water-filling algorithm is developed with providing an upper bound of the expected unavailable time obtained by the algorithm. The numerical results show that the proposed model reduces MEUT compared to baselines. The priority policy adopted in the proposed model suppresses MEUT compared with other priority policies. The developed heuristic algorithm is approximately 106times faster than the MILP approach with 10-4performance penalty on MEUT.

This paper proposes a multiple backup resource allocation model with a workload-dependent failure probability to minimize the maximum expected unavailable time (MEUT) under a protection priority policy. The workload-dependent failure probability is a monotonically increasing function which reveals the relationship between computing workload and failure probability. The proposed model adopts hot backup and cold backup strategies to provide protection. The cold backup strategy is a protection strategy, in which the requested loads of backup resources are not processed as active workloads before failures occur to reduce resource utilization with the cost of long recover time. The hot backup strategy is a protection strategy, in which the backup resources execute at the same time with functions to recover promptly with the cost of high workload. For protection of each function with multiple backup resources, it is required to adopt a suitable priority policy to determine the expected unavailable time. We analyze the superiority of the protection priority policy for multiple backup resources in the proposed model and provide the theorems that clarify the influence of policies on MEUT. The numerical results show that the proposed model reduces MEUT compared with the single backup model in which each function is protected by only one server without protection priority of servers. The priority policy adopted in the proposed model specifying that the server which adopts the hot backup strategy has higher priority than that with the cold backup strategy for multiple backup resources suppresses MEUT compared with other priority policies.

This paper presents two strategies to obtain an assignment of backup servers to network functions of middleboxes when each backup server can recover a half of the functions which it protects at the same time. In the previous work, there are approaches to obtain an assignment only when each backup server protects two functions and recovers one of them at the same time. Therefore, we present two strategies to expand the cases where an assignment can be obtained by utilizing the previous approaches. The basic ideas of our two strategies are dividing each server into a set of small servers that protects two functions and recovers one of them at the same time, obtaining an assignment with them, and combining them. In the process of obtaining an assignment with our presented two strategies, there is a constraint to avoid impairing the capabilities of backup servers. Our two strategies incorporate this constraint before and after obtaining an assignment with the divided small servers, respectively. We define six survival probabilities regarding our two strategies and analyze their relationships. Then, we derive two theorems to consider when our strategy can obtain an assignment that satisfies the constraint. Based on the theorems, we analyze properties of our strategies and the relationship between the different survival probabilities. Numerical results show that one of our strategies provides the higher survival probability than the other one for all the settings that we examine.

This paper proposes a distributed server allocation model with the preventive start-time optimization against a single server failure. The proposed model preventively determines the assignment of servers to users under each failure pattern to minimize the largest maximum delay among all failure patterns. We formulate the proposed model as an integer linear programming problem. We prove the NP-completeness for the considered problem. The numerical results reveal that the proposed model reduces the largest maximum delay compared to one baseline; it avoids instability caused by the unnecessary disconnection, which frequently occurs in the other baseline.

This paper proposes a preventive priority setting model to handle load balancing against multiple controller failures in software defined networks. For each switch, a set of controllers can control it, where only one master controller controls the switch and others are slave controllers. We introduce a priority for each controller to become the master controller. At any time, the controller which does not fail and has the highest priority works as the master controller. Once the existing master controller fails, the assignment of new master controller is automatically obtained according to the priority setting to promptly recover the control. The priority set is decided at the network operation start time to minimize the maximum utilization ratio among controllers in the worst-case of failure patterns. We formulate the proposed model in two different forms, which are an integer linear programming formulation and a min-max formulation. We prove that the preventive priority setting problem is NP-hard. A heuristic algorithm is introduced based on the min-max formulation. The numerical results reveal that the proposed model obtains the maximum utilization ratio comparable to those obtained by two baselines; it provides a faster recovery compared to one baseline and reduces the instability of network operation compared to the other.

Network function virtualization paradigm enables us to implement network functions provided in middleboxes as softwares which run on commodity servers. This paper proposes an unavailability-aware backup allocation model with shared protection for middleboxes with comprehensively considering the failure, repair, and recovery behaviors of functions and backup servers. Multiple functions can share the backup resources on the backup server. The proposed model aims to find the assignment of backup servers to functions to minimize the maximum unavailability among functions. The multiple situations of failure, repair, and recovery of functions and backup servers lead to several different states for each function. The unavailability of function is estimated through analyzing all states that a function can be in. To compute the unavailability of middlebox for a given backup allocation, an analytical approach is developed based on the queueing theory. With the analytical approach, we introduce a simulated annealing heuristic to solve the backup allocation problem. The results reveal that, compared to a baseline model, the proposed unavailability-aware model reduces the maximum unavailability 11% in average in our examined scenarios.

A virtual network function allocation model to maximize continuous available time of service function chains was introduced in our previous work. The performance of this model needs to be evaluated on network devices. It is time-consuming and costly to deploy functions with real network devices. Existing simulation tools require powerful computation capability, which limits the usable cases. We implement a network service header based service function chain application which can be cooperated with the model. Demonstration validates that the application allocates functions by using the allocation from the model automatically and runs service function chains correctly.

This paper proposes an optimization model for the network service mapping and scheduling problem with uncertain processing time. We model processing time uncertainty through Γ-robustness approach, which provides different degrees of robustness against processing time uncertainty. We formulate the problem with the objective to minimize the worst-case makespan over the given uncertainty set. A heuristic is presented to tackle the problem. The numerical results show that the proposed model outperforms the conventional model with deterministic parameters in terms of worst-case makespan.

This paper proposes a backup network design scheme that can determine backup link capacity in practical time. The proposed scheme suppresses the required backup link capacity while providing a guaranteed level of recovery against multiple independent link failures. The conventional scheme is based on robust optimization and suffers from the problem of overestimating the backup link capacity. The proposed scheme addresses the overestimation problem by computing the probabilistic distribution function of required backup link capacity in polynomial time. We formulate the backup network design problem with the proposed scheme as a mixed integer linear programming problem to minimize the total required backup link capacity. We prove that the decision version of backup network design problem is NP-complete. Given that network size will continue to increase, we introduce a heuristic approach of simulated annealing to solve the same problem. Numerical results show that the proposed scheme requires less total backup link capacity than the conventional scheme based on robust optimization.

Network function virtualization enables network operators to implement network functions in a software-oriented manner and makes network services (NSes) provisioning much simpler. This paper proposes an optimization model to schedule delay sensitive NSes with deadlines allowing resource sharing and preemption. Unlike conventional NS scheduling models with static resource allocation for virtualized network function (VNF) instances, the proposed model ensures that VNF instances deployed on the same node share computation resources of the node and are able to scale up/down to change their process rate at runtime. NSes mapped to the same VNF instance of the same node share computation resources of the VNF instance and are able to be processed in parallel by the VNF instance. Preemption is allowed, which means that rescheduling the order of NS processing at runtime is possible and the process duration of each function of an NS is allowed to be discrete. We formulate the proposed model as an integer linear programming problem to maximize the number of admissible NSes. Due to the complexity of the problem, we develop a genetic algorithm to solve it efficiently. We evaluate the proposed model with conventional models in the static and dynamic scenarios. The numerical results show that the proposed model outperforms conventional models in terms of acceptance ratio in both static and dynamic scenarios.

This paper presents three approaches to solve the problem of finding the optimal backup resource assignment which maximizes the survival probability of network functions of middleboxes. In the previous work, no mathematical model to solve this problem is provided, so we formulate the problem as a mixed-integer linear programming (MILP) problem as the first approach. Formulating this MILP problem includes some special steps, which are not considered in the previous work. The MILP problem is not always solved in a practical time when the problem size becomes large. Then, we develop two heuristic approaches by replacing the objective of the original MILP problem relying on the idea of balancing the failure probabilities of functions of connected components. Numerical results show that our two developed heuristic approaches improve the survival probability from a conventional heuristic algorithm in some cases and reduce computation time compared to obtaining the optimal solution. Furthermore, one of our developed heuristic approaches provides exactly the optimal solution with shorter computation time compared to the time solving the original MILP problem in a special case.

The performance of packet processing applications is dependent on memory accesses speed of network systems. Table lookup requires fast memory accesses and is one of the most common processes in various packet processing applications, which can be a dominant performance bottleneck. Therefore, in Network Function Virtualization (NFV)-aware environment, on-chip fast cache memories of a CPU of general-purpose hardware become critical to achieve high performance packet processing over tens of Gbps. In addition, multiple types of applications and complex applications are executed in the same system simultaneously in carrier network systems, which require the capacity of cache memories as well. In this paper, we propose a packet processing architecture that utilizes interleaved 3 Dimensional (3D)-stacked Dynamic Random Access Memory (DRAM) devices as off-chip Last Level Cache (LLC) in addition to several levels of dedicated cache memories of each CPU core. Entries of a lookup table are distributed in every bank and vaults to utilize both bank interleaving and vault-level memory access parallelism. Frequently accessed entries in 3D-stacked DRAM are also cached in dedicated on-chip cache memories of each CPU core. The evaluation results show that the proposed architecture reduces the memory access latency by 57 % and increases the throughput by 100 % with reducing blocking probability about 10 % compared to the conventional architecture with common on-chip LLC. These results indicate that 3D-stacked DRAM can be practical as off-chip LLC in parallel packet processing running on multiple CPU cores simultaneously.

This paper proposes an optimization model to schedule network services (NSes) in virtual networks with resource sharing and preemption. Inefficient NS scheduling can severely degrade the acceptance ratio of arriving NSes of the network. Conventional NS scheduling models do not consider sharing computational resources of a node among different virtual network function (VNF) instances deployed on this node. In the proposed model, NSes mapped to the same VNF instance on the same node share computational resources of the VNF instance, and VNF instances deployed on the same node share computational resources of the node. The proposed model allows preemption, which means that rescheduling the process order of NSes in runtime is possible and the process duration of each function of an NS is allowed to be discrete. We formulate the proposed model as an integer linear programming problem to maximize the number of admissible NSes. The numerical results show that the proposed model outperforms conventional models in terms of the acceptance ratio of arriving NSes.

This paper proposes a master and slave controller assignment model against multiple controller failures in software defined network with considering propagation latency between switches and controllers. In our model, a controller can be assigned to multiple switches, and the survivability of each switch is guaranteed to a certain degree by assigning multiple controllers to it. We define the average-case expected propagation latency, the worst-case expected propagation latency, and the expected number of switches within a propagation latency bound, as three different objectives to be optimized, which lead to three different problems, in this paper. We formulate the proposed master and slave controller assignment model with different goals as three mixed integer linear programming problems. Results show that the optimal assignments vary for different problems. A greedy algorithm with polynomial time complexity is introduced to solve the same optimization problems. We evaluate the performance of introduced greedy algorithm compared with the optimal value in one of the problems, which minimizes the average-case propagation latency. The numerical results reveal that the computational time of running the greedy algorithm to obtain a solution is about 10-3times compared to that of solving the mixed integer linear programming problem; the obtained objective value is about 1.00324 times of the optimal value in average in our examined scenarios.

The lightpath provisioning time or releasing time is adversely affected by the time that optical amplifiers require to adjust to a newly added or terminated signal power. This shortcoming is particularly true with multi-core erbium-doped amplifiers (EDFAs), as multi-core transient-suppressed EDFAs are unavailable at the current time. This paper proposes a fiber span power management scheme based on dummy wavelength signals that are used to shorten the lightpath provisioning and releasing times in multi-core fiber networks. With the shorter time of lightpath provisioning and releasing procedures, the total time that is required to reserve wavelengths in the system is decreased, which means that network resources are used more efficiently. As a result, the blocking performance and average waiting time in the system are improved. To evaluate the performance of the proposed scheme, this paper introduces both analytical model and simulation study. In the introduced model, the ratio of the number of activating and activated dummy wavelengths to the number of dummy wavelengths in each span is considered in the range between 0 and 1. The analysis reveals that the performance of the proposed scheme depends on α, which is the ratio of the number of dummy wavelengths to the number of dummy and lightpath wavelengths in each span, and there exists a point of α where the blocking probability becomes minimum. We further observe that the proposed scheme outperforms the conventional approaches in terms of blocking probability and average waiting time, as traffic loads increase. Finally, we provide the direction on how our introduced model can be considered for a network with multi-span routes.

Network function virtualization paradigm enables us to implement network functions provided in middleboxes as softwares that run on commodity servers. This paper proposes a backup resource allocation model for middleboxes with considering both failure probabilities of network functions and backup servers. A backup server can protect several functions; a function can have multiple backup servers. We take the importance of functions into account by defining a weighted unavailability for each function. We aim to find an assignment of backup servers to functions, where the worst weighted unavailability is minimized. We formulate the proposed backup resource allocation model as a mixed integer linear programming problem. We prove that the backup resource allocation problem for middlebox with importance is NP-complete. We develop three heuristic algorithms with polynomial time complexity to solve the problem. We analyze the approximation performances of different heuristic algorithms with providing several lower and upper bounds. We present the competitive evaluation in terms of deviation and computation time among the results obtained by running the heuristic algorithms and by solving the mixed integer linear programming problem. The results show the pros and cons of different approaches. With our analyses, a network operator can choose an appropriate approach according to the requirements in specific application scenarios.

This work proposes a defragmentation scheme using reroutable backup paths in toggled-based quasi 1+1 path protected elastic optical networks to enhance the efficiency of defragmentation and suppress the fragmentation effect. The proposed scheme allows both reallocation of spectrum slots of backup paths and rerouting of backup paths. By using the path exchanging approach in the proposed scheme, the primary paths become the backup path while the backup path becomes the primary path. This allows to utilize the advantages of defragmentation in both primary and backup paths. Considering rerouting and path exchanging, we present to the key idea to formulate the proposed scheme as an integer linear programming (ILP) problem. A heuristic algorithm is introduced to solve the problem for large networks, when ILP is not tractable. For a dynamic traffic scenario, an approach that suppresses the fragmentation considering rerouting and path exchanging operations is presented. The numerical results indicate that the blocking probability using the proposed scheme is suppressed compared to the conventional scheme.

This paper shows how to design, within practical time constraints, a backup network that suppresses the required resources while providing a guaranteed level of recovery against multiple link failures. The conventional scheme based on robust optimization has the problem of overestimating the backup link capacity. The backup network design scheme proposed herein computes the probabilistic distribution function of required backup link capacity in polynomial time, and so addresses the optimization problem of minimizing the total backup network capacity. For large networks, we introduce the heuristic approach of simulated annealing that adopts our approach to computing backup link capacity. Numerical analyses show that the proposed scheme requires less total backup network capacity than the conventional scheme based on robust optimization.

This paper proposes a backup resource allocation model that provides a probabilistic protection for primary physical machines in a cloud provider to minimize the required total capacity. When any random failure occurs, workloads are transferred to preplanned and dedicated backup physical machines for prompt recovery. In the proposed model, a probabilistic protection guarantee is introduced to prevent the cloud provider from capacity overbooking. We apply robust optimization in our model to formulate the backup resource allocation problem as an integer linear programming problem. A simulated annealing heuristic is adopted to solve the same optimization problem when the cloud provider is large. Finally, the results reveal that the required backup capacity depends on the reliability of primary physical machines. Specifically, the more the resources in primary physical machines share backup capacity when the failure probabilities of primary physical machines are sufficiently small, the less capacity is required for backup resource allocation.

Emergence of new network services such as Internet of Things (IoT) and edge computing accelerates the increase of traffic volume, the number of connected devices and the diversity of communication. Next generation carrier network infrastructure should be much more scalable and adaptive to rapid increase and divergence of network demand with much lower cost. More virtualization-aware, flexible and inexpensive system based on general-purpose hardware is necessary to transform traditional carrier network into more adaptive, next generation network. In this paper, we propose a carrier-scale packet processing system which utilizes 3 Dimensional (3D)-stacked Dynamic Random Access Memory (DRAM) device. The proposed system augments memory access concurrency by leveraging vault-level parallelism and bank interleaving of 3D-stacked DRAM. The system uses hash-function-based distributor of memory requests to each set of vault and bank which accommodates a portion of original carrier-scale huge tables. We introduce an analytical model for the system. The evaluation result shows that our proposed system can achieve more than 100 Gbps in carrier-scale packet processing where main memory accesses are inevitable since tiny CPU cache memory is insufficient to accommodate huge tables. Our analytical model is independent of specification of a particular device, which can be applied to any DRAM systems.

The paper proposes a real-time tracking algorithm for a moving object with mobile robot based on vision using adaptive color matching and Kalman filter. The adaptive color matching can limit the region containing moving object on vision image plane. It can adjust color matching threshold to reduce the influence of lighting variations in the scene. Kalman filter is used as our prediction module to calculate motion vectors of moving object in the robot coordinate system. A view window containing the position of moving object estimated by Kalman filter is determined on image plane to reduce the image processing area. Color matching threshold can adjust itself adaptively in view window, which is used as an updating module. Experimental results show that the algorithm can adapt to lighting variations and has good tracking precision. It can also be implemented in real time.