Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userAn Approximation Algorithm for Path Computation and Function Placement in SDNs
56
0
0.0
(
0
)
Added by
Guy Even
Publication date
2016
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We consider the task of computing (combined) function mapping and routing for requests in Software-Defined Networks (SDNs). Function mapping refers to the assignment of nodes in the substrate network to various processing stages that requests must undergo. Routing refers to the assignment of a path in the substrate network that begins in a source node of the request, traverses the nodes that are assigned functions for this request, and ends in a destination of the request. The algorithm either rejects a request or completely serves a request, and its goal is to maximize the sum of the benefits of the served requests. The solution must abide edge and vertex capacities. We follow the framework suggested by Even for the specification of the processing requirements and routing of requests via processing-and-routing graphs (PR-graphs). In this framework, each request has a demand, a benefit, and PR-graph. Our main result is a randomized approximation algorithm for path computation and function placement with the following guarantee. Let $m$ denote the number of links in the substrate network, $eps$ denote a parameter such that $0< eps <1$, and $opt_f$ denote the maximum benefit that can be attained by a fractional solution (one in which requests may be partly served and flow may be split along multiple paths). Let $cmin$ denote the minimum edge capacity, and let $dmax$ denote the maximum demand. Let $Deltamax$ denote an upper bound on the number of processing stages a request undergoes. If $cmin/(Deltamaxcdotdmax)=Omega((log m)/eps^2)$, then with probability at least $1-frac{1}{m}-textit{exp}(-Omega(eps^2cdot opt_f /(bmax cdot dmax)))$, the algorithm computes a $(1-eps)$-approximate solution.
rate research
Read More
SDN controllers must be periodically modified to add features, improve performance, and fix bugs, but current techniques for implementing dynamic updates are inadequate. Simply halting old controllers and bringing up new ones can cause state to be lost, which often leads to incorrect behavior-e.g., if the state represents hosts blacklisted by a firewall, then traffic that should be blocked may be allowed to pass through. Techniques based on record and replay can reconstruct state automatically, but they are expensive to deploy and can lead to incorrect behavior. Problematic scenarios are especially likely to arise in distributed controllers and with semantics-altering updates. This paper presents a new approach to implementing dynamic controller updates based on explicit state transfer. Instead of attempting to infer state changes automatically-an approach that is expensive and fundamentally incomplete-our framework gives programmers effective tools for implementing correct updates that avoid major disruptions. We develop primitives that enable programmers to directly (and easily, in most cases) initialize the new controllers state as a function of old state and we design protocols that ensure consistent behavior during the transition. We also present a prototype implementation called Morpheus, and evaluate its effectiveness on representative case studies.
Software Defined Networking and Network Function Virtualization are two paradigms that offer flexible software-based network management. Service providers are instantiating Virtualized Network Functions - e.g., firewalls, DPIs, gateways - to highly facilitate the deployment and reconfiguration of network services with reduced time-to-value. They employ Service Function Chaining technologies to dynamically reconfigure network paths traversing physical and virtual network functions. Providing a cost-efficient virtual function deployment over the network for a set of service chains is a key technical challenge for service providers, and this problem has recently caught much attention from both Industry and Academia. In this paper, we propose a formulation of this problem as an Integer Linear Program that allows one to find the best feasible paths and virtual function placement for a set of services with respect to a total financial cost, while taking into account the (total or partial) order constraints for Service Function Chains of each service and other constraints such as end-to-end latency, anti-affinity rules between network functions on the same physical node and resource limitations in terms of network and processing capacities. Furthermore, we propose a heuristic algorithm based on a linear relaxation of the problem that performs close to optimum for large scale instances.
One of the strongest techniques available for showing lower bounds on quantum communication complexity is the logarithm of the approximation rank of the communication matrix--the minimum rank of a matrix which is entrywise close to the communication matrix. This technique has two main drawbacks: it is difficult to compute, and it is not known to lower bound quantum communication complexity with entanglement. Linial and Shraibman recently introduced a norm, called gamma_2^{alpha}, to quantum communication complexity, showing that it can be used to lower bound communication with entanglement. Here the parameter alpha is a measure of approximation which is related to the allowable error probability of the protocol. This bound can be written as a semidefinite program and gives bounds at least as large as many techniques in the literature, although it is smaller than the corresponding alpha-approximation rank, rk_alpha. We show that in fact log gamma_2^{alpha}(A)$ and log rk_{alpha}(A)$ agree up to small factors. As corollaries we obtain a constant factor polynomial time approximation algorithm to the logarithm of approximate rank, and that the logarithm of approximation rank is a lower bound for quantum communication complexity with entanglement.
Network Functions Virtualization (NFV) allows implantation of network functions to be independent of dedicated hardware devices. Any series of services can be represented by a service function chain which contains a set of virtualized network functions in a specified order. From the perspective of network performance optimization, the challenges of deploying service chain in network is twofold: 1) the location of placing virtualized network functions and resources allocation scheme; and 2) routing policy for traffic flow among different instances of network function. This article introduces service function chain related optimization problems, summarizes the optimization motivation and mainstream algorithm of virtualized network functions deployment and traffic routing. We hope it can help readers to learn about the current research progress and make further innovation in this field.
With the constant increase in demand for data connectivity, network service providers are faced with the task of reducing their capital and operational expenses while ensuring continual improvements to network performance. Although Network Function Virtualization (NFV) has been identified as a solution, several challenges must be addressed to ensure its feasibility. In this paper, we present a machine learning-based solution to the Virtual Network Function (VNF) placement problem. This paper proposes the Depth-Optimized Delay-Aware Tree (DO-DAT) model by using the particle swarm optimization technique to optimize decision tree hyper-parameters. Using the Evolved Packet Core (EPC) as a use case, we evaluate the performance of the model and compare it to a previously proposed model and a heuristic placement strategy.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
