skip to main content


Title: 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
NSF-PAR ID:
10082134
Author(s) / Creator(s):
; ; ;
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
  1. 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
  2. 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
  3. 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
  4. A key concept of software-defined networking (SDN) is separation of the control and data plane. This idea provides several benefits, including fine-grained network control and monitoring, and the ability to deploy new services in a limited scope. Unfortunately, it is often cost-prohibitive for enterprises (and universities in particular) to upgrade their existing networks to wholly SDN-capable networks all at once. A compromise solution is to deploy SDN capabilities incrementally in the network. The challenge then is to take full advantage of SDN-based services throughout the network, in an integrated fashion rather than in a few "islands" of SDN support. At the University of Kentucky, SDN has been integrated into the campus network for several years. In this paper, we describe two aspects of this challenge, along with our solution approaches. One is the general reluctance of campus network administrations to allow novel or experimental (SDN-based) services in the production network. The other is how to extend such services throughout the legacy part of the network. For the former, we lay out a set of principles designed to ensure that the production service is not harmed. For the latter, we use policy based routing and a graph database to extend our previously-described VIP Lanes service. Our simulation results in a campus-like topology testbed show that we can provide a host with custom path service even if it is connected to a legacy router. 
    more » « less
  5. Summary

    Design flaws and vulnerabilities inherent to network protocols, devices, and services make Distributed Denial of Service (DDoS) a persisting threat in the cyberspace, despite decades of research efforts in the area. The historical vertical integration of traditional IP networks limited the solution space, forcing researchers to tweak network protocols while maintaining global compatibility and proper service to legitimate flows. The advent of Software‐Defined Networking (SDN) and advances in Programmable Data Planes (PDP) changed the state of affairs and brought novel possibilities to deal with such attacks. In summary, the ability of bringing together network intelligence to a control plane, and offloading flow processing tasks to the forwarding plane, opened up interesting opportunities for network security researchers unlike ever. In this article, we dive into recent research that relies on SDN and PDP to detect, mitigate, and prevent DDoS attacks. Our literature review takes into account the SDN layered view as defined in RFC7426 and focuses on the data, control, and application planes. We follow a systematic methodology to capture related articles and organize them into a taxonomy of DDoS defense mechanisms focusing on three facets:activity level,deployment location, andcooperation degree. From the analysis of existing work, we also highlight key research gaps that may foster future research in the field.

     
    more » « less