Mobile edge computing is a new cloud computing paradigm, which makes use of small-sized edge clouds to provide real-time services to users. These mobile edge-clouds (MECs) are located in close proximity to users, thus enabling users to seamlessly access applications running on MECs. Due to the co-existence of the core (centralized) cloud, users, and one or multiple layers of MECs, an important problem is to decide where (on which computational entity) to place different components of an application. This problem, known as the application or workload placement problem, is notoriously hard, and therefore, heuristic algorithms without performance guarantees are generally employed in common practice, which may unknowingly suffer from poor performance as compared with the optimal solution. In this paper, we address the application placement problem and focus on developing algorithms with provable performance bounds. We model the user application as an application graph and the physical computing system as a physical graph, with resource demands availabilities annotated on these graphs. We first consider the placement of a linear application graph and propose an algorithm for finding its optimal solution. Using this result, we then generalize the formulation and obtain online approximation algorithms with polynomial-logarithmic (poly-log) competitive ratio for tree application graph placement. We jointly consider node and link assignment, and incorporate multiple types of computational resources at nodes.
A related problem that has emerged recently is the service chain embedding problem @cite_17 @cite_15 @cite_18 . Motivated by network function virtualization (NFV) applications, the goal is to place a linear application graph between fixed source and destination physical nodes, so that a series of operations are performed on data packets sent from the source to the destination. Within this body of work, only @cite_18 has studied the competitive ratio of online placement, which, however, does not consider link placement optimization.
@cite_15 @cite_18 @cite_17
2340581052 2481063713 2790045047 2138314086
The SDN and NFV paradigms enable novel network services which can be realized and embedded in a flexible and rapid manner. For example, SDN can be used to flexibly steer traffic from a source to a destination through a sequence of virtualized middleboxes, in order to realize so-called service chains. The service chain embedding problem consists of three tasks: admission control, finding suitable locations to allocate the virtualized middleboxes and computing corresponding routing paths. This paper considers the offline batch embedding of multiple service chains. Concretely, we consider the objectives of maximizing the profit by embedding an optimal subset of requests or minimizing the costs when all requests need to be embedded. Interestingly, while the service chain embedding problem has recently received much attention, so far, only non- polynomial time algorithms (based on integer programming) as well as heuristics (which do not provide any formal guarantees) are known. This paper presents the first polynomial time service chain approximation algorithms both for the case with admission and without admission control. Our algorithm is based on a novel extension of the classic linear programming and randomized rounding technique, which may be of independent interest. In particular, we show that our approach can also be extended to more complex service graphs, containing cycles or sub-chains, hence also providing new insights into the classic virtual network embedding problem. Recently, Network Function Virtualization (NFV) has been proposed to transform from network hardware appliances to software middleboxes. Normally, a demand needs to invoke several Virtual Network Functions (VNFs) in a particular order following the service chain along a routing path. In this paper, we study the joint problem of VNF placement and path selection to better utilize the network. We discover that the relation between the link and server usage plays a crucial role in the problem. We first propose a systematic way to elastically tune the proper link and server usage of each demand based on network conditions and demand properties. In particular, we compute a proper routing path length, and decide, for each VNF in the service chain, whether to use additional server resources or to reuse resources provided by existing servers. We then propose a chain deployment algorithm to follow the guidance of this link and server usage. Via simulations, we show that our design effectively adapts resource usage to network dynamics, and, hence, serves more demands than other heuristics. Network Function Virtualization (NFV) has revolutionized service provisioning in cloud datacenter networks. It enables the complete decoupling of Network Functions (NFs) from the physical hardware middle boxes that network operators deploy for implementing service-specific and strictly ordered NF chains. Precisely, NFV allows for dispatching NFs as instances of plain software called virtual network functions (VNFs) running on virtual machines hosted by one or more industry standard physical machines. Nevertheless, NF softwarization introduces processing vulnerability ( e.g. , failures caused by hardware or software, and so on). Since any failure of VNFs could break down an entire service chain, thus interrupting the service, the functionality of an NFV-enabled network will require a higher reliability compared with traditional networks. This paper encloses an in-depth investigation of a reliability-aware joint VNF chain placement and flow routing optimization. In order to guarantee the required reliability, an incremental approach is proposed to determine the number of required VNF backups. Through illustration, it is shown herein that the formulated single path routing model can be easily extended to support resource sharing between adjacent backup VNF instances. This paper advocates the absolute existence of a share-resource-based VNF assignment strategy that is capable of trading off all of the reliability, bandwidth, and computing resources consumption of a given service chain. A heuristic is proposed to work around the complexity of the presently formulated integer linear programming (ILP). Thorough numerical analysis and simulations are conducted in order to verify and assert the validity, correctness, and effectiveness of this proposed heuristic reflecting its ability to achieve very close results to those obtained through the resolution of the complex ILP within a negligible amount of time. Above and beyond, the proposed resource-sharing-based VNF placement scheme outperforms existing resource-sharing agnostic schemes by 15.6 and 14.7 in terms of bandwidth and CPU utilization respectively. Network Functions Virtualization (NFV) is incrementally deployed by Internet Service Providers (ISPs) in their carrier networks, by means of Virtual Network Function (VNF) chains, to address customers' demands. The motivation is the increasing manageability, reliability and performance of NFV systems, the gains in energy and space granted by virtualization, at a cost that becomes competitive with respect to legacy physical network function nodes. From a network optimization perspective, the routing of VNF chains across a carrier network implies key novelties making the VNF chain routing problem unique with respect to the state of the art: the bitrate of each demand flow can change along a VNF chain, the VNF processing latency and computing load can be a function of the demands traffic, VNFs can be shared among demands, etc. In this paper, we provide an NFV network model suitable for ISP operations. We define the generic VNF chain routing optimization problem and devise a mixed integer linear programming formulation. By extensive simulation on realistic ISP topologies, we draw conclusions on the trade-offs achievable between legacy Traffic Engineering (TE) ISP goals and novel combined TE-NFV goals.