Service function chaining (SFC), consisting of a sequence of
virtual network functions (VNFs) (i.e., firewalls and load balancers), is
an effective service provision technique in modern data center networks.
By requiring cloud user traffic to traverse the VNFs in order, SFC im-
proves the security and performance of the cloud user applications. In
this paper, we study how to place an SFC inside a data center to mini-
mize the network traffic of the virtual machine (VM) communication. We
take a cooperative multi-agent reinforcement learning approach, wherein
multiple agents collaboratively figure out the traffic-efficient route for the
VM communication.
Underlying the SFC placement is a fundamental graph-theoretical prob-
lem called the k-stroll problem. Given a weighted graph G(V, E), two
nodes s, t ∈ V , and an integer k, the k-stroll problem is to find the
shortest path from s to t that visits at least k other nodes in the graph.
Our work is the first to take a multi-agent learning approach to solve k-
stroll problem. We compare our learning algorithm with an optimal and
exhaustive algorithm and an existing dynamic programming(DP)-based
heuristic algorithm. We show that our learning algorithm, although lack-
ing the complete knowledge of the network assumed by existing research,
delivers comparable or even better VM communication time while taking
two orders of magnitude of less execution time.
more »
« less
Shortest Path and Maximum Flow Problems Under Service Function Chaining Constraints
With the advent of Network Function Virtualization (NFV), Physical Network Functions (PNFs) are gradually being replaced by Virtual Network Functions (VNFs) that are hosted on general purpose servers. Depending on the call flows for specific services, the packets need to pass through an ordered set of network functions (physical or virtual) called Service Function Chains (SFC) before reaching the destination. Conceivably for the next few years during this transition, these networks would have a mix of PNFs and VNFs, which brings an interesting mix of network problems that are studied in this paper: (1) How to find an SFC-constrained shortest path between any pair of nodes? (2) What is the achievable SFC-constrained maximum flow? (3) How to place the VNFs such that the cost (the number of nodes to be virtualized) is minimized, while the maximum flow of the original network can still be achieved even under the SFC constraint? In this work, we will try to address such emerging questions. First, for the SFC-constrained shortest path problem, we propose a transformation of the network graph to minimize the computational
complexity of subsequent applications of any shortest path algorithm. Second, we formulate the SFC-constrained maximum flow problem as a fractional multicommodity flow problem, and develop a combinatorial algorithm for a special case of practical
interest. Third, we prove that the VNFs placement problem is NP-hard and present an alternative Integer Linear Programming (ILP) formulation. Finally, we conduct simulations to elucidate our theoretical results.
more »
« less
- Award ID(s):
- 1717108
- NSF-PAR ID:
- 10073233
- Date Published:
- Journal Name:
- IEEE INFOCOM 2018 - IEEE Conference on Computer Communications
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
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%.more » « less
-
Virtual network services that span multiple data centers are important to support emerging data-intensive applications in fields such as bioinformatics and retail analytics. Successful virtual network service composition and maintenance requires flexible and scalable ‘constrained shortest path management’ both in the management plane for virtual network embedding (VNE) or network function virtualization service chaining (NFV-SC), as well as in the data plane for traffic engineering (TE). In this paper, we show analytically and empirically that leveraging constrained shortest paths within recent VNE, NFV-SC and TE algorithms can lead to network utilization gains (of up to 50%) and higher energy efficiency. The management of complex VNE, NFV-SC and TE algorithms can be, however, intractable for large scale substrate networks due to the NP-hardness of the constrained shortest path problem. To address such scalability challenges, we propose a novel, exact constrained shortest path algorithm viz.‘, Neighborhoods Method’ (NM). Our NM uses novel search space reduction techniques and has a theoretical quadratic speed-up making it practically faster (by an order of magnitude) than recent branch-and-bound exhaustive search solutions. Finally, we detail our NM-based SDN controller implementation in a real-world testbed to further validate practical NM benefits for virtual network services.more » « less
-
Abstract—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.more » « less
-
null (Ed.)Virtual Network Functions (VNFs) are software implementation of middleboxes (MBs) (e.g., firewalls) that provide performance and security guarantees for virtual machine (VM) cloud applications. In this paper we study a new flow migration problem in VNF-enabled cloud data centers where the traffic rates of VM flows are constantly changing. Our goal is to minimize the total network traffic (therefore optimizing the network resources such as bandwidth and energy) while considering that VNFs have limited processing capability. We formulate the flow migration problem and design two efficient benefit-based greedy algorithms. The simulations show that our algorithms are effective in reducing the network traffic as well as in achieving load balance among VNFs. In particular, our flow migration algorithms can reduce upto 15% network traffic compared to the case without flow migration.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- The DOI is not currently available.
