Mobile edge computing (MEC) has emerged as a promising technology that offers resource-intensive yet delay-sensitive applications from the edge of mobile networks. With the emergence of complicated and resource-hungry mobile applications, offloading user tasks to cloudlets of nearby mobile edge-cloud networks is becoming an important approach to leverage the processing capability of mobile devices, reduce mobile device energy consumptions, and improve experiences of mobile users. In this article we first study the provisioning of virtualized network function (VNF) services for user requests in an MEC network, where each user request has a demanded data packet rate with a specified network function service requirement, and different user requests need different services that are represented by virtualized network functions instantiated in cloudlets. We aim to maximize the number of user request admissions while minimizing their admission cost, where the request admission cost consists of the computing cost on instantiations of requested VNF instances and the data packet traffic processing of requests in their VNF instances, and the communication cost of routing data packet traffic of requests between users and the cloudlets hosting their requested VNF instances. We study the joint VNF instance deployment and user requests assignment in MEC, by explicitly exploring a non-trivial usage tradeoff between different types of resources. To this end, we first formulate the cost minimization problem that admits all requests by assuming that there is sufficient computing resource in MEC to accommodate the requested VNF instances of all requests, for which we formulate an Integer Linear Programming solution and two efficient heuristic algorithms. We then deal with the problem under the computing resource constraint. We term this problem as the throughput maximization problem by admitting as many as requests, subject to computing resource capacity on each cloudlet, for which we formulate an ILP solution when the problem size is small; otherwise, we devise efficient algorithms for it. We finally evaluate the performance of the proposed algorithms through experimental simulations. Experimental results demonstrate that the proposed algorithms are promising. To the best of our knowledge, we are the first to explicitly explore the usage tradeoff between computing and communication resources in the admissions of user requests in MEC through introducing a novel load factor concept to minimize the request admission cost and maximize the network throughput.

Network Function Virtualization (NFV) has attracted significant attention from both industry and academia as an important paradigm change in network service provisioning. Most existing studies on admissions of NFV-enabled requests focused on deploying dedicated Virtualized Network Function (VNF) instances to serve each individual request without exploring the sharing of VNF instances among multiple user requests. However, with ever-growing demands of user services, exclusive usages of VNF instances in most networks drastically degrade the network performance and largely under-utilize the VNF instance resources. In this paper, we jointly explore two different VNF instance scaling techniques, horizontal scaling and vertical scaling techniques, to improve the network throughput while minimizing the operational cost of the network, where horizontal scaling that migrates some existing VNF instances from their current locations to new locations to allow the VNF instances to be shared by multiple requests to reduce the resource consumption and operational cost of the network, and vertical scaling that instantiates new VNF instances to meet the demands of new request admissions if existing VNF instances sharing becomes more expensive or the end-to-end delay requirements of currently executing requests will be violated. We first propose a unified framework of maximizing the network throughput, by admitting as many as NFV-enabled requests while meeting the end-to-end delay requirements of the admitted requests. We then provide an Integer Linear Programming (ILP) solution for the problem when the problem size is small. Otherwise, we devise an efficient algorithm through a non-trivial reduction that reduces the problem to the minimum-weight feedback arc set problem and the generalized assignment problem (GAP). We finally conduct experiments to evaluate the performance of the proposed algorithm. Experimental results demonstrate that the proposed algorithm outperforms a baseline algorithm and achieves a performance on a par with its optimal ILP solution.

With advances in wireless communication technology, more and more people depend heavily on portable mobile devices for business, entertainments and social interactions. This poses a great challenge of building a seamless application experience across different computing platforms. A key issue is the resource limitations of mobile devices due to their portable size, however this can be overcome by offloading computation-intensive tasks from the mobile devices to clusters of nearby computers called cloudlets through wireless access points. As increasing numbers of people access the Internet via mobile devices, it is reasonable to envision in the near future that cloudlet services will be available for the public through easily accessible public wireless metropolitan area networks (WMANs). However, the outdated notion of treating cloudlets as isolated data-centers-in-boxes must be discarded as there are clear benefits to connecting multiple cloudlets together to form a network. In this paper we investigate how to balance the workload among cloudlets in an WMAN to optimize mobile application performance. We first introduce a novel system model to capture the response time delays of offloaded tasks and formulate an optimization problem with the aim to minimize the maximum response time of all offloaded tasks. We then propose two algorithms for the problem: one is a fast heuristic, and another is a distributed genetic algorithm that is capable of delivering a more accurate solution compared with the first algorithm, but at the expense of a much longer running time. We finally evaluate the performance of the proposed algorithms in realistic simulation environments. The experimental results demonstrate the significant potential of the proposed algorithms in reducing the user task response time, maximizing user experience.

Along with Network Function Virtualization (NFV), Mobile Edge Computing (MEC) is becoming a new computing paradigm that enables accommodating innovative applications and services with stringent response delay and resource requirements, including autonomous vehicles and augmented reality. Provisioning reliable network services for users is the top priority of most network service providers, as unreliable services or severe service failures can result in tremendous losses of users, particularly for their mission-critical applications. In this paper, we study reliability-aware VNF instances provisioning in an MEC, where different users request different network services with different reliability requirements through paying their requested services with the aim to maximize the network throughput. To this end, we first formulate a novel reliability-aware VNF instance placement problem by provisioning primary and secondary VNF instances at different cloudlets in MEC for each user while meeting the specified reliability requirement of the user request. We then show that the problem is NP-hard and formulate an Integer Linear Programming (ILP) solution. Due to the NP-hardness of the problem, we instead devise an approximation algorithm with a logarithmic approximation ratio for the problem. Moreover, we also consider two special cases of the problem. For one special case where each request only requests one primary and one secondary VNF instances, the problem is still NP-hard, and we devise a constant approximation algorithm for it. For another special case where different VNFs have the same amounts of computing resource demands, we show that it is polynomial-time solvable by developing a dynamic programming solution for it. We finally evaluate the performance of the proposed algorithms through experimental simulations. Experimental results demonstrate that the proposed algorithms are promising, and the empirical results of the algorithms outperform their analytical counterparts as theoretical estimations usually are very conservative.

The Mobile Edge-Cloud (MEC) network has emerged as a promising networking paradigm to address the conflict between increasing computing-intensive applications and resource-constrained mobile Internet-of-Thing (IoT) devices with portable size and storage. In MEC environments, Virtualized Network Functions (VNFs) are deployed for provisioning network services to users to reduce the service cost on top of dedicated hardware infrastructures. However, VNFs may suffer from failures and malfunctions while network service providers have to guarantee continuously reliable services to their consumers to meet the ever-growing service demands of users, thereby securing their revenues for the service. In this article, we focus on reliable VNF service provisioning in MECs, by placing primary and backup VNF instances to cloudlets in an MEC network to meet the service reliability requirements of users. We first formulate a novel VNF service reliability problem with the aim to maximize the revenue collected by admitting as many as user requests while meeting their different reliability requirements, assuming that requests arrive into the system one by one without the knowledge of future arrivals, and the admission or rejection decision must be made immediately. We then develop two efficient online algorithms for the problem under two different backup schemes: the on-site (local) and off-site (remote) schemes, by adopting the primal-dual updating technique. Both algorithms achieve provable competitive ratios with bounded moderate resource capacity violations. We finally evaluate the proposed algorithms through experimental simulations. Experimental results demonstrate that the proposed algorithms are promising, compared with existing baseline algorithms.

Mobile Edge Computing (MEC) has emerged as a promising paradigm to address the conflict between increasing computing-intensive applications and resource-constrained mobile Internet-of-Thing (IoT) devices with portable size and storage. In MEC environments, Virtualized Network Functions (VNFs) are deployed for provisioning network services to users to reduce the service cost on top of dedicated hardware infrastructures. However, VNFs may suffer from failures and malfunctions while network service providers have to guarantee continuously reliable services to their users to meet ever-growing service demands of the users. In this paper, we focus on reliable VNF service provisioning in MECs, by provisioning primary and backup VNF instances in order to meet the reliability requirements of mobile users. We first formulate a novel VNF service reliability problem with the aim to maximize the revenue collected by admitting as many as user requests while meeting individual user service reliability requirements. We then develop two efficient on-line scheduling algorithms for the problem under two different backup schemes: on-site (local) and off-site (remote) schemes, by adopting the primal and dual updating technique. Particularly for the on-site scheme, the proposed on-line algorithm achieves a provable competitive ratio with bounded moderate resource violations. We finally evaluate the proposed algorithms through experimental simulations. The experimental results demonstrate that the proposed algorithms are promising, compared with existing baseline algorithms.

Multicasting is a fundamental functionality of many network applications, including online conferencing, event monitoring, video streaming, and so on. To ensure reliable, secure, and scalable multicasting, a service chain that consists of network functions (e.g., firewalls, intrusion detection systems, and transcoders) usually is associated with each multicast request. We refer to such a multicast request with service chain requirement as an network function virtualization (NFV)-enabled multicast request. In this paper, we study NFV-enabled multicasting in a software-defined network (SDN) with an aim to maximize network throughput while minimizing the implementation cost of admitted NFV-enabled multicast requests, subject to network resource capacity, where the implementation cost of a request consists of its computing resource consumption cost in servers and its network bandwidth consumption cost when routing and processing its data packets in the network. To this end, we first formulate two NFV-enabled multicasting problems with and without resource capacity constraints and one online NFV-enabled multicasting problem. We then devise two approximation algorithms with an approximation ratio of $2M$ for the NFV-enabled multicasting problems with and without resource capacity constraints, if the number of servers for implementing the service chain of each request is no greater than a constant $M$ (≥1). We also study dynamic admissions of NFV-enabled multicast requests without the knowledge of future request arrivals with the objective to maximize the network throughput, for which we propose an efficient heuristic, and for the special case of dynamic request admissions, we devise an online algorithm with a competitive ratio of $O(\log n)$ for it when $M=1$ , where $n$ is the number of nodes in the network. We finally evaluate the performance of the proposed algorithms through experimental simulations. Experimental results demonstrate that the proposed algorithms are promising and outperform existing heuristics.

Pushing the cloud frontier to the network edge close to mobile users has attracted tremendous interest not only from cloud operators but also from network service providers. In particular, the deployment of cloudlets in metropolitan area networks enables network service providers to provide low-latency services to mobile users through implementing their specified virtualized network functions (VNFs) while meeting their Quality-of-Service (QoS) requirements. In this paper, we formulate a novel task offloading problem in a mobile edge-cloud network, where each offloading task requests a specified network function with a tolerable delay. We aim to maximize the number of requests admitted while minimizing the operational cost of admitted requests within a finite time horizon, through either sharing existing VNF instances or creating new VNF instances in cloudlets. We first show that the problem is NP-hard, and then devise an efficient online algorithm for the problem by reducing it to a series of minimum weight maximum matching problems. Considering dynamic changes of task offloading request patterns over time, we further develop an effective prediction mechanism for new VNF instance creations and idle VNF instance releases to further lower the operational cost of the network service provider. Also, we devise an online algorithm with a competitive ratio for a special case of the problem where the delay requirements of requests are negligible. We finally evaluate the performance of the proposed algorithms through experimental simulations. Experimental results indicate that the proposed algorithms are promising.

Network Function Virtualization (NFV) and Software-Defined Networking (SDN) have been envisioned an essential milestone in the evolution of communication networks. Their integration provides a more flexible and easier manageable software-based network environment that induces high expectations for reducing capital expenditures (CAPEX) and operational costs (OPEX) of network service providers. They also introduce technical challenges. One such challenge is to manage the placement of VNFs and to steer the data traffic of each NFV-enabled request through its specified network functions. In this paper, we opportunistically adopt the flexibility and cost-efficiency of VNF and SDN for NFV-enabled request admissions in SDNs and formulate profit maximization problems for static and dynamic NFV-enabled request admissions. We first provide an integer linear programming (ILP) solution to the problem in the static version if the problem size is small; otherwise, we devise a fast approximation algorithm with a provable approximation ratio for the static request admissions. We then propose an efficient online algorithm for dynamic request admissions, by leveraging VNF instance migrations and idle VNF releases back to the system. We finally evaluate the performance of the proposed algorithms through experimental simulations. Simulation results demonstrate that the proposed algorithms are very promising.

Network Function Virtualization (NFV) has attracted significant attentions from both industry and academia as an important paradigm change in network service provisioning. Most existing studies on NFV dealt with admissions of user requests through deploying Virtualized Network Function (VNF) instances for individual user requests, without considering sharing VNF instances among multiple user requests to provide better network services and improve network throughput. In this paper, we study the network throughput maximization problem by adopting two different VNF instance scalings: (i) horizontal scaling by migrating existing VNF instances from their current locations to new locations; and (ii) vertical scaling by instantiating more VNF instances if needed. Specifically, we first propose a unified framework that jointly considers both vertical and horizontal scalings to maximize the network throughput, by admitting as many requests as possible while meeting their resource demands and end-to-end transmission delay requirements. We then devise an efficient heuristic algorithm for the problem. We finally conduct experiments to evaluate the performance of the proposed algorithm. Experimental results demonstrate that the proposed algorithm outperforms a baseline algorithm.

Data transfer in contemporary networks usually is associated with strict policy enforcement for data transfer security and system performance purposes. Such a policy is represented by a service chain consisting of a sequence of network functions such as firewalls, intrusion detection systems, transcoders, etc. Due to the high cost and inflexibility of managing hardware-based network functions, network function virtualization (NFV) has emerged as a promising technology to meet the stringent requirement imposed on the service chain of each data transfer request in a low-cost and flexible way. In this paper, we study policy-aware unicast request admissions with and without end-to-end delay constraints in a software defined network. We aim to minimize the operational cost of admitting a single request in terms of both computing resource consumption for implementing the NFVs in the service chain and bandwidth resource consumption for routing its data traffic, or maximize the network throughput for a sequence of requests without the knowledge of future request arrivals. We first formulate four novel optimization problems and provide a generic optimization framework for the problems. We then develop efficient algorithms for the admission of a single NFV-enabled request with and without the end-to-end delay constraint, where NFV-enabled requests are defined as the requests with policy enforcement requirements. We also devise online algorithms with a guaranteed performance for dynamic admissions of requests without the knowledge of future arrivals. In particular, we provide the very first online algorithm with a provable competitive ratio for the problem without the end-to-end delay requirement. We finally evaluate the performance of the proposed algorithms through experimental simulations. Experimental results show that the proposed algorithms are promising and outperform existing heuristics.

Data transfers in contemporary networks depend upon network functions for ensuring data security and system performance. These policies are represented by a service chain that consists of different network functions such as firewalls, Intrusion Detection Systems (IDSs), transcoders, etc. Network Function Virtualization (NFV) has emerged as a promising technology to meet the stringent requirement imposed on the service chain. In this paper, we study NFV-enabled unicasting in SDNs with and without end-to-end delay constraints. We aim to maximize the network throughput for a sequence of NFV-enabled unicast requests without the knowledge of future arrivals. We first formulate the problems as novel optimization problems in terms of both computing and bandwidth resource consumptions, and provide a generic optimization framework. We then develop an online algorithm with guaranteed performance without the delay requirement and a heuristic with the delay requirement. We finally evaluate the performance of the proposed algorithms through experimental simulations. The results of the experimental simulations show that the proposed algorithms are promising.

Software-defined networking (SDN) is a promising technique that has reshaped the landscape of network management. By providing simplified, cost-effective management, SDN has been envisioned as the next-generation network paradigm. However, due to economic, organizational, and technical challenges, replacing all conventional switches in current operational networks by SDN-enabled switches is impractical in the short term. It thus is desirable to deploy SDN-enabled switches into existing networks incrementally, and such a network consisting of SDN-enabled switches and conventional switches is referred to as a hybrid SDN network. The incremental deployment of SDN-enabled switches is challenging because the number of conventional switches that can be replaced is typically limited, due to budget constraints or operational network stability concerns, yet the impact of the deployment should be maximized. In this paper, we deal with the SDN-enabled switch placement problem with the aim to maximize system performance, given $K$ switches to be replaced, for which we first propose heuristics by replacing conventional switches one by one iteratively. We then devise scalable algorithms that replace multiple switches, instead of a single switch, in each iteration. We finally evaluate the performance of the proposed algorithms based on real and synthetic network topologies. Experimental results demonstrate that the proposed algorithms are promising and exhibiting high scalability.

Multicasting is a fundamental functionality of networks for many applications including online conferencing, event monitoring, video streaming, and system monitoring in data centers. To ensure multicasting reliable, secure and scalable, a service chain consisting of network functions (e.g., firewalls, Intrusion Detection Systems (IDSs), and transcoders) usually is associated with each multicast request. Such a multicast request is referred to as an NFV-enabled multicast request. In this paper we study NFV-enabled multicasting in a Software-Defined Network (SDN) with the aims to minimize the implementation cost of each NFV-enabled multicast request or maximize the network throughput for a sequence of NFV-enabled requests, subject to network resource capacity constraints. We first formulate novel NFV-enabled multicasting and online NFV-enabled multicasting problems. We then devise the very first approximation algorithm with an approximation ratio of 2K for the NFV-enabled multicasting problem if the number of servers for implementing the network functions of each request is no more than a constant K (1). We also study dynamic admissions of NFV-enabled multicast requests without the knowledge of future request arrivals with the objective to maximize the network throughput, for which we propose an online algorithm with a competitive ratio of O(log n) when K = 1, where n is the number of nodes in the network. We finally evaluate the performance of the proposed algorithms through experimental simulations. Experimental results demonstrate that the proposed algorithms outperform other existing heuristics.

Today's computer networks rely on a wide spectrum of specialized middleboxes to improve network security and performance. A promising emerging technique to implementing traditional middleboxes is the consolidated middlebox technique, which implements the middleboxes as software in virtual machines in software-defined networks (SDNs), offering economical, and simplified management for middleboxes. This however poses a great challenge, that is, how to find a cost-optimal routing path for each user request such that the data traffic of the request will pass through the middleboxes in their orders in the service chain of the request, with the objective to maximize the network throughput, subject to various resource capacity constraints in SDNs. In this paper, we study the network throughput maximization problem in an SDN under two different scenarios: one is the snapshot scenario where a set of requests at one time slot is given, we aim to admit as many requests in the set as possible to maximize the network throughput; another is the online scenario in which requests arrive one by one without the knowledge of future arrivals. Given a finite time horizon consisting of T equal time slots, the system must respond to the arrived requests in the beginning of each time slot, by either admitting or rejecting the requests, depending on the resource availabilities in the network. For the snapshot scenario, we first formulate an integer linear program (ILP) solution, we then devise two heuristics that strive for fine tradeoffs between the quality of a solution and the running time of obtaining the solution. For the online scenario, we show how to extend the proposed algorithms for the snapshot scenario to solve the online scenario. We finally evaluate the performance of the proposed algorithms through experimental simulations, based on both real and synthetic network topologies. Experimental results demonstrate that the proposed algorithms admit more requests than the baseline algorithm and the quality of the solutions delivered by heuristics is comparable to the exact solution by the ILP in most cases.

Software-Defined Networking (SDN) has emerged as the paradigm of the next-generation networking through separating the data control plane from the data plane. The forwarding routing table at each of its switch nodes is usually implemented by expensive and power-hungry Ternary Content Addressable Memory (TCAM) that only has limited number of entries, and the bandwidth at each of its links is bounded too. Under this new network architecture, providing a quality service to users by admitting user requests to meet their resource demands is challenging, and very little attention has ever been paid in this regard. In this paper, we will study online unicast and multicast request admissions in SDNs with the aim to maximize the network throughput under both critical network resources and user bandwidth demand constraints, for which we first propose a novel model to characterize the usage costs of node and link resources. We then devise efficient online algorithms for unicast and multicast requests. We also analyze the competitive ratios of the proposed online algorithms, which are O(log n) and O(Kϵlog n) for unicasting and multicasting, respectively, where n is the network size, K is the maximum number of members in a multicast request, and ϵ is a constant with 0 <; e ≤ 1. We finally evaluate the proposed algorithms empirically through simulations. The simulation results demonstrate that the proposed algorithms are very promising.

With advances in wireless communication technology, more and more people depend heavily on portable mobile devices for businesses, entertainments and social interactions. Although such portable mobile devices can offer various promising applications, their computing resources remain limited due to their portable size. This however can be overcome by remotely executing computation-intensive tasks on clusters of near by computers known as cloudlets. As increasing numbers of people access the Internet via mobile devices, it is reasonable to envision in the near future that cloudlet services will be available for the public through easily accessible public wireless metropolitan area networks (WMANs). However, the outdated notion of treating cloudlets as isolated data-centers-in-a-box must be discarded as there are clear benefits to connecting multiple cloudlets together to form a network. In this paper we investigate how to balance the workload between multiple cloudlets in a network to optimize mobile application performance. We first introduce a system model to capture the response times of offloaded tasks, and formulate a novel optimization problem, that is to find an optimal redirection of tasks between cloudlets such that the maximum of the average response times of tasks at cloudlets is minimized. We then propose a fast, scalable algorithm for the problem. We finally evaluate the performance of the proposed algorithm through experimental simulations. The experimental results demonstrate the significant potential of the proposed algorithm in reducing the response times of tasks.

Today's computer networks rely on a wide spectrum of specialized middleboxes to improve their security and performance. Traditional middleboxes that are implemented by dedicated hardware are expensive and hard to manage. A promising technique of consolidated middleboxes - implementing traditional middleboxes in Virtual Machines (VMs) - offers economical yet simplified management of middleboxes in Software-Defined Networks (SDNs). However there are still challenges to realizing user routing requests with network function enforcement (a sequence of middleboxes) while maximizing the network throughput, due to various resource constraints on SDNs, such as forwarding table capacity at each switch, bandwidth resource capacity at each link, and computing resource capacity at each server (Physical Machine). In this paper, we study the problem of maximizing the network throughput of an SDN by admitting as many user requests as possible, where each user request has both bandwidth and computing resource demands to implement its network functions (consolidated middleboxes). We first formulate the problem as a novel network throughput maximization problem. We then provide an Integer Linear Program (ILP) solution for it if the problem size is small, otherwise, we devise two heuristics that strive for the fine tradeoff between the accuracy of solutions and the running times of achieving the solutions. We finally evaluate the performance of the proposed algorithms by simulations, based on real and synthetic network topologies. Experimental results demonstrate that the proposed algorithms are very promising.