An official website of the United States government
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
A Constrained Shortest Path Scheme for Virtual Network Service Management
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
- Award ID(s):
- 1647084
- PAR ID:
- 10082134
- Date Published:
- Journal Name:
- IEEE Transactions on Network and Service Management
- ISSN:
- 2373-7379
- Page Range / eLocation ID:
- 1 to 1
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Network function virtualization (NFV) offers the potential for both enhancing service delivery flexibility and reducing overall costs by virtualizing network functions that are traditionally implemented in dedicated hardware. However, the flexibility of NFV comes with considerable compromises since virtual machine carried functions could introduce significant performance overhead. In this paper, we present a novel high-performance framework called HYPER, which combines programmable hardware infrastructure and traditional software infrastructure in NFV to achieve both high performance and flexibility for supporting virtualized network functions (VNFs). In HYPER, we design a mediator layer to hide underlying infrastructure heterogeneity from the NFV orchestrator to simplify VNF management. In addition, we design a SLA-aware service chaining algorithm in HYPER to leverage the benefits of the hybrid infrastructure to fulfill both functional and performance requirements from service subscribers (or tenants). To optimize resource utilization efficiency, we also introduce a performance-aware VNF placement algorithm in HYPER, which accommodates both resource and performance requirements in placing VNFs. We implement HYPER in a testbed based on OpenStack and ONetCard. Experimental results show that HYPER reduces the forwarding latency of a service chain by 40% to 67% compared with data plane development kit -based implementation, while maintaining the flexibility of VNF management.more » « less
-
Given a transportation network, a source node s, a destination node t , and the number of maximum possible turnings b , the Turn-Constrained Shortest Path (TCSP) problem is to find the route that minimizes the travel distance and meets the turn-constraint. The TCSP problem is important for societal applications such as shipping and logistics, emergency route planning, and traffic management services. We propose novel approaches for TCSP to meet the turn-constraint while minimizing the travel distance for the vehicle route. Experiments using real-world datasets demonstrated that the proposed algorithms can minimize the travel distance and meet the turn-constraint; furthermore, it has comparable solution quality to the unconstrained shortest path and significantly reduces the computational cost.more » « less
-
A virtual firewall based on Network Function Virtualization (NFV) with Software Defined Networking (SDN) provides high scalability and flexibility for low-cost monitoring of legacy networks by dynamically deploying virtual network appliances rather than traditional hardware-based appliances. However, full utilization of virtual firewalls requires efficient management of computer virtualization resources and on-demand placement of virtual firewalls by steering traffic to the correct routing path using an SDN controller. In this paper, we design P4Guard, a software-based configurable firewall based on a high-level domain-specific language to specify packet processing logic using P4. P4Guard is a protocol-independent and platform-agnostic software-based firewall that can be incorporated into software switches that is highly usable and deployable. We evaluate the efficiency of P4Guard in processing traffic, compared to our previous virtual firewall in NFV.more » « less
-
Singhal, A.; Vaidya, J. (Ed.)By virtualizing proprietary hardware networking devices, Network Functions Virtualization (NFV) allows agile and cost-effective deployment of diverse network services for multiple tenants on top of the same physical infrastructure. As NFV relies on virtualization, and as an NFV stack typically involves several levels of abstraction and multiple co-resident tenants, this new technology also unavoidably leads to new security threats. In this paper, we take the first step toward modeling and mitigating security threats unique to NFV. Specifically, we model both cross-layer and co-residency attacks on the NFV stack. Additionally, we mitigate such threats through optimizing the virtual machine (VM) placement with respect to given constraints. The simulation results demonstrate the effectiveness of our solution.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1109/TNSM.2018.2865204
