This paper proposes a defragmentation scheme using reroutable backup paths in toggled-based quasi 1+1 path protected elastic optical networks (EONs) to improve the efficiency of defragmentation and suppress the fragmentation effect. The proposed scheme can reallocate spectrum slots of backup paths and reroute of backup paths. The path exchange function of the proposed scheme makes the primary paths become the backup state while the backup paths become the primary. This allows utilization of the advantages of defragmentation in both primary and backup paths. We formulate a static spectrum reallocation problem with rerouting (SSRR) in the toggled-based quasi 1+1 path protected EON as an integer linear programming (ILP) problem. The decision version of SSRR is proven to be an NP-complete problem. A heuristic algorithm is introduced to solve the problem for large networks networks where the ILP problem is not tractable. For a dynamic traffic scenario, an approach that suppresses the fragmentation considering rerouting and path exchanging operations is presented. We evaluate the performances of the proposed scheme by comparing it to the conventional scheme in terms of dependencies on node degree, processing time of network operations and interval time between scheduled defragmentations. The numerical results obtained from the performance evaluation indicate that the proposed scheme increases the traffic admissibility compared to the conventional scheme.

This paper presents a distributed server allocation model with preventive start-time optimization against a single server failure. The presented 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 (ILP) problem. We prove the NP-completeness of the considered problem. As the number of users and that of servers increase, the size of ILP problem increases; the computation time to solve the ILP problem becomes excessively large. We develop a heuristic approach that applies simulated annealing and the ILP approach in a hybrid manner to obtain the solution. Numerical results reveal that the developed heuristic approach reduces the computation time by 26% compared to the ILP approach while increasing the largest maximum delay by just 3.4% in average. It reduces the largest maximum delay compared with the start-time optimization model; it avoids the instability caused by the unnecessary disconnection permitted by the run-time optimization model.

This paper proposes a migration model for distributed server allocation. In distributed server allocation, each user is assigned to a server to minimize the communication delay. In the conventional model, a user cannot migrate to another server to avoid instability. We develop a model where each user can migrate to another server while receiving services. We formulate the proposed model as an integer linear programming problem. We prove that the considered problem is NP-complete. We introduce a heuristic algorithm. Numerical result shows that the proposed model reduces the average communication delay by 59% compared to the conventional model at most.

This paper proposes a robust optimization model for probabilistic protection under uncertain capacity demands to minimize the total required capacity against multiple simultaneous failures of physical machines. The proposed model determines both primary and backup virtual machine allocations simultaneously under the probabilistic protection guarantee. To express the uncertainty of capacity demands, we introduce an uncertainty set that considers the upper bound of the total demand and the upper and lower bounds of each demand. The robust optimization technique is applied to the optimization model to deal with two uncertainties: failure event and capacity demand. With this technique, the model is formulated as a mixed integer linear programming (MILP) problem. To solve larger sized problems, a simulated annealing (SA) heuristic is introduced. In SA, we obtain the capacity demands by solving maximum flow problems. Numerical results show that our proposed model reduces the total required capacity compared with the conventional model by determining both primary and backup virtual machine allocations simultaneously. We also compare the results of MILP, SA, and a baseline greedy algorithm. For a larger sized problem, we obtain approximate solutions in a practical time by using SA and the greedy algorithm.

With the network function virtualization technology, a middlebox can be deployed as software on commercial servers rather than on dedicated physical servers. A backup server is necessary to ensure the normal operation of the middlebox. The workload can affect the failure rate of backup server; the impact of workload-dependent failure rate on backup server allocation considering unavailability has not been extensively studied. This paper proposes a shared backup allocation model of middlebox with consideration of the workload-dependent failure rate of backup server. Backup resources on a backup server can be assigned to multiple functions. We observe that a function has four possible states and analyze the state transitions within the system. Through the queuing approach, we compute the probability of each function being available or unavailable for a certain assignment, and obtain the unavailability of each function. The proposed model is designed to find an assignment that minimizes the maximum unavailability among functions. We develop a simulated annealing algorithm to solve this problem. We evaluate and compare the performances of proposed and baseline models under different experimental conditions. Based on the results, we observe that, compared to the baseline model, the proposed model reduces the maximum unavailability by an average of 29% in our examined cases.

This paper introduces a deep reinforcement learning approach to solve the virtual network function scheduling problem in dynamic scenarios. We formulate an integer linear programming model for the problem in static scenarios. In dynamic scenarios, we define the state, action, and reward to form the learning approach. The learning agents are applied with the asynchronous advantage actor-critic algorithm. We assign a master agent and several worker agents to each network function virtualization node in the problem. The worker agents work in parallel to help the master agent make decision. We compare the introduced approach with existing approaches by applying them in simulated environments. The existing approaches include three greedy approaches, a simulated annealing approach, and an integer linear programming approach. The numerical results show that the introduced deep reinforcement learning approach improves the performance by 6-27% in our examined cases.

This paper proposes a backup resource allocation model for virtual network functions (VNFs) to minimize the total allocated computing capacity for backup with considering the service delay. If failures occur to primary hosts, the VNFs in failed hosts are recovered by backup hosts whose allocation is pre-determined. We introduce probabilistic protection, where the probability that the protection by a backup host fails is limited within a given value; it allows backup resource sharing to reduce the total allocated computing capacity. The previous work does not consider the service delay constraint in the backup resource allocation problem. The proposed model considers that the probability that the service delay, which consists of networking delay between hosts and processing delay in each VNF, exceeds its threshold is constrained within a given value. We introduce a basic algorithm to solve our formulated delay-constraint optimization problem. In a problem with the size that cannot be solved within an acceptable computation time limit by the basic algorithm, we develop a simulated annealing algorithm incorporating Yen's algorithm to handle the delay constraint heuristically. We observe that both algorithms in the proposed model reduce the total allocated computing capacity by up to 56.3% compared to a baseline; the simulated annealing algorithm can get feasible solutions in problems where the basic algorithm cannot.

This paper proposes two algorithms, namely Server-User Matching (SUM) algorithm and Extended Server-User Matching (ESUM) algorithm, for the distributed server allocation problem. The server allocation problem is to determine the matching between servers and users to minimize the maximum delay, which is the maximum time to complete user synchronization. We analyze the computational time complexity. We prove that the SUM algorithm obtains the optimal solutions in polynomial time for the special case that all server-server delay values are the same and constant. We provide the upper and lower bounds when the SUM algorithm is applied to the general server allocation problem. We show that the ESUM algorithm is a fixed-parameter tractable algorithm that can attain the optimal solution for the server allocation problem parameterized by the number of servers. Numerical results show that the computation time of ESUM follows the analyzed complexity while the ESUM algorithm outperforms the approach of integer linear programming solved by our examined solver.

This paper presents an analytical model that yields the unavailability of a network function when each backup server can protect two functions and can recover one of them. Previous work describes a model to deal with the case that each function can be protected only by one server. In our model, we allow each function to be protected by multiple servers to ensure function availability. This requires us to know the feasible states of a connected component and its state transitions. By adopting the divide-and-conquer method, we enumerate the feasible states of a connected component. We then classify its state transitions. Based on the obtained feasible states and the classification of the state transitions, we enumerate the feasible states incoming to and outgoing from a general state, the transfer rates, and the conditions. With those informations, we generate multiple equations about the state transitions. Finally, by solving them, we obtain the probabilities that a connected component is in each state and calculate the unavailability of a function. Numerical results show that the average unavailability of a function is reduced by 18% and 5.7% in our two examined cases by allowing each function to be protected by multiple servers.

This paper presents robust optimization models for minimizing the required backup capacity while providing probabilistic protection against multiple simultaneous failures of physical machines under uncertain virtual machine capacities in a cloud provider. If random failures occur, the required capacities for virtual machines are allocated to the dedicated backup physical machines, which are determined in advance. We consider two uncertainties: failure event and virtual machine capacity. By adopting a robust optimization technique, we formulate six mixed integer linear programming problems. Numerical results show that for a small size problem, our presented models are applicable to the case that virtual machine capacities are uncertain, and by using these models, we can obtain the optimal solution of the allocation of virtual machines under the uncertainty. A simulated annealing heuristic is presented to solve large size problems. By using this heuristic, an approximate solution is obtained for a large size problem.

The performance of packet processing applications is dependent on the memory access speed of network systems. Table lookup requires fast memory access 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 environments, on-chip fast cache memories of a CPU of general-purpose hardware become critical to achieve high performance packet processing speeds of over tens of Gbps. Also, multiple types of applications and complex applications are executed in the same system simultaneously in carrier network systems, which require adequate cache memory capacities 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 vault to utilize both bank interleaving and vault-level memory parallelism. Frequently accessed entries in 3D-stacked DRAM are also cached in on-chip dedicated 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% while reducing the blocking probability but about 10% compared to the architecture with shared on-chip LLC. These results indicate that 3D-stacked DRAM can be practical as off-chip LLC in parallel packet processing systems.