Service function chaining (SFC), consisting of a sequence of virtual network functions (VNFs), is the de-facto service provisioning mechanism in VNF-enabled data centers (VDCs). However, for the SFC, the dynamic and diverse virtual machine (VM) traffic must traverse a sequence of VNFs possibly installed at different locations at VDCs, resulting in prolonged network delay, redundant network traffic, and large consumption of cloud resources (e.g., bandwidth and energy). Such adverse effects of the SFC, which we refer to as SFC traffic storm, significantly impede its efficiency and practical implementation.In this paper, we solve the SFC traffic storm problem by proposing AggVNF, a framework wherein the VNFs of an SFC are implemented into one aggregate VNF while multiple instances of aggregate VNFs are available in the VDC. AggVNF adaptively allocates and migrates aggregate VNFs to optimize cloud resources in dynamic VDCs while achieving the load balance of VNFs. At the core of the AggVNF are two graph-theoretical problems that have not been adequately studied. We solve both problems by proposing optimal, approximate, and heuristic algorithms. Using real traffic patterns in Facebook data centers, we show that a) our VNF allocation algorithms yield traffic costs 56.3% smaller than the latest research using the SFC design, b) our VNF migration algorithms yield 84.2% less traffic than the latest research using the SFC design, and c) VNF migration is an effective technique in mitigating dynamic traffic in VDCs, reducing the total traffic cost by up to 24.8%.

We study a new variation of the Traveling Salesman Problem (TSP) called the Budget-Constrained Traveling Salesman Problem (BC-TSP). BC-TSP is inspired by a few emerging network applications, such as robotic sensor networks. We design a prize-driven multi-agent reinforcement learning (MARL) framework to solve the BC-TSP. The main novelty of the framework, named P-MARL, is that it makes a connection between the prize maximization in BC-TSP and the cumulative reward maximization in reinforcement learning (RL) to design a more efficient MARL algorithm. In particular, P-MARL integrates the prizes available at nodes into the reward model of the MARL to guide the cooperative effort of multiple learning agents. Via extensive simulations using synthetic data of state capital cities of the U.S., we show that a) the P-MARL outperforms the existing prize-oblivious MARL work by collecting 28.8 % of more prizes under the same budget constraints, b) it takes two orders of magnitudes of shorter training time than the state-of-the-art deep reinforcement learning-based approach while collecting 45.3 % more prizes under the same budgets, and c) P-MARL collects prizes at least 91.9% of optimal obtained by the Integer Linear Programming (ILP) under different network parameters.

Prize-Collecting Traveling Salesman Problem (PC-TSP) is a new variation of TSP and is defined as follows. Given a weighted complete graph$G(V, E)$where node$i\in V$has an available prize of$p_{i}$, and two nodes$s, t\in V$, the goal of the traveling salesman is to find a route from$s$to$t$such that the sum of the prizes of all the nodes visited along the route reaches a pre-set quota while the distance along the route is minimized. In this paper, we propose a multi-agent reinforcement learning (MARL) framework for the PC-TSP. Our novel observation is that prize-collecting in PC-TSP is intrinsically related to cumulative reward maximization in reinforcement learning (RL). By integrating the prizes in PC-TSP into the reward model in RL, we design an efficient and effective MARL algorithm to solve the PC-TSP. Via extensive simulations under different network and RL parameters, we show that our learning algorithm delivers an average of 65.6% of less traveling distance compared to one existing handcrafted greedy algorithm. When changing the number of agents$m$from 1 to 5, our algorithm reduces the prize-collecting learning time by up to 66.9%, demonstrating the effectiveness of multi-agent collaboration in reducing the prize-collecting learning time in PC-TSP.

Virtual Network Functions (VNFs) are software implementation of middleboxes (MBs) (e.g., firewalls and proxy servers) that provide performance and security guarantees for virtual machine (VM) cloud applications. In this paper, we study a new VM flow migration problem for dynamic VNF-enabled cloud data centers (VDCs). The goal is to migrate the VM flows in the dynamic VDCs to minimize the total network traffic while load-balancing VNFs with limited processing capabilities. We refer to the problem as FMDV: flow migration in dynamic VDCs. We propose an optimal and efficient minimum cost flow-based flow migration algorithm and two benefit-based efficient heuristic algorithms to solve the FMDV. Via extensive simulations, we show that our algorithms are effective in mitigating dynamic cloud traffic while achieving load balance among VNFs. In particular, all our algorithms reduce dynamic network traffic in all cases and our optimal algorithm always achieves the best traffic-mitigation effect, reducing the network traffic by up to 28% compared to the case without flow migration.

In this paper we study a new algorithmic problem that maximizes the throughput of virtual machine (VM) communication in bandwidth-constrained data centers. Given a set of VM pairs with different bandwidth demands that are already placed inside cloud data centers, we study how to allocate the network bandwidth to the VM pairs to accommodate maximum number of VM communication while considering that cloud data centers have limited bandwidths. We refer to this throughput maximization problem as VMB. Due to the massive growth of cloud communication traffic in recent years and that service providers attempt to accommodate as many VM applications as possible in order to maximize their profits, VMB is an important problem to study. First we prove that VMB is NP-hard. Then we propose a suite of algorithms to solve VMB. In particular, we propose an approximation algorithm that achieves approximation ratio of$1 /\left(2 \cdot\left\lceil\frac{B}{b}\right\rceil \cdot\vert E\vert^{1 /\left(\left\lceil\frac{B}{b}\right\rceil+1\right)}+1\right)$, where$\vert E\vert$is the number of edges in the data center network,$B$is the average bandwidth capacity on edges, and$b$is the average bandwidth demand of each request. We show through simulations that our algorithms are effective in accommodating large number of VM communications under different network parameters. In particular, our approximation algorithm accommodates more than 60% of total VM communications, and up to 38% more VM pairs compared to existing research.

Virtual machine (VM) replication is an effective technique in cloud data centers to achieve fault-tolerance, load-balance, and quick-responsiveness to user requests. In this paper we study a new fault-tolerant VM placement problem referred to as FT-VMP. Given that different VM has different fault-tolerance requirement (i.e., difference VM requires different number of replica copies) and compatibility requirement (i.e., some VMs and their replicas cannot be placed into some physical machines (PMs) due to software or platform incompatibility), FT-VMP studies how to place VM replica copies inside cloud data centers in order to minimize the number of PMs storing VM replicas, under the constraints that i) for fault-tolerant purpose, replica copies of the same VM cannot be placed inside the same PM and ii) each PM has a limited amount of storage capacity. We first prove that FT-VMP is NP-hard. We then design an integer linear programming (ILP)-based algorithm to solve it optimally. As ILP takes time to compute thus is not suitable for large scale cloud data centers, we design a suite of efficient and scalable heuristic fault-tolerant VM placement algorithms. We show that a) ILP-based algorithm outperforms the state-of-the-art VM replica placement in a wide range of network dynamics and b) that all our fault-tolerant VM placement algorithms are able to turn off significant number of PMs to save energy in cloud data centers. In particular, we show that our algorithms can consolidate (i.e., turn off) around 100 PMs in a small data center of 256 PMs and 700 PMs in a large data center of 1028PMs.