Search

The Internet of Things (IoT) technology provisions unprecedented opportunities to evolve the interconnection among human beings. However, the latency brought by unstable wireless networks and computation failures caused by limited resources on IoT devices prevents users from experiencing high efficiency and seamless user experience. To address these shortcomings, the integrated Mobile Edge Computing (MEC) with remote clouds is a promising platform to enable delay-sensitive service provisioning for IoT applications, where edge-clouds (cloudlets) are co-located with wireless access points in the proximity of IoT devices. Thus, computation-intensive and sensing data from IoT devices can be offloaded to the MEC network immediately for processing, and the service response latency can be significantly reduced. In this paper, we first formulate two novel optimization problems for delay-sensitive IoT applications, i.e., the total utility maximization problems under both static and dynamic offloading task request settings, with the aim to maximize the accumulative user satisfaction on the use of the services provided by the MEC, and show the NP-hardness of the defined problems. We then devise efficient approximation and online algorithms with provable performance guarantees for the problems in a special case where the bandwidth capacity constraint is negligible. We also develop efficient heuristic algorithms for the problems with the bandwidth capacity constraint. We finally evaluate the performance of the proposed algorithms through experimental simulations. Experimental results demonstrate that the proposed algorithms are promising in reducing service delays and enhancing user satisfaction, and the proposed algorithms outperform their counterparts by at least 10.8 percent. [ABSTRACT FROM AUTHOR]

The explosive growth of mobile devices promotes the prosperity of novel mobile applications, which can be realized by service offloading with the assistance of edge computing servers. However, due to limited computation and storage capabilities of a single server, long service latency hinders the continuous development of service offloading in mobile networks. By supporting multi-server cooperation, Pervasive Edge Computing (PEC) is promising to enable service migration in highly dynamic mobile networks. With the objective of maximizing the system utility, we formulate the optimization problem by jointly considering the constraints of server storage capability and service execution latency. To enable dynamic service placement, we first utilize Lyapunov optimization method to decompose the long-term optimization problem into a series of instant optimization problems. Then, a sample average approximation-based stochastic algorithm is proposed to approximate the future expected system utility. Afterwards, a distributed Markov approximation algorithm is utilized to determine the service placement configurations. Through theoretical analysis, the time complexity of our proposed algorithm is linear to the number of users, and the backlog queue of PEC servers is stable. Performance evaluations are conducted based on both synthetic and real trace-driven scenarios, with numerical results demonstrating the effectiveness of our proposed algorithm from various aspects. [ABSTRACT FROM AUTHOR]

With the rapid growth of the Web scale, large scale search engines have to set up a huge number of machines to place the index files of the Web contents. The index files are normally divided into smaller index shards which are often replicated so that queries can be processed in parallel. We observe from real systems that the index shard replication strategy could have a significant impact on the resource usage. In this paper, we investigate the index shard replication problem with the goal of minimizing the resource usage in search engine datacenters. We consider both the offline version and online version of the problem, and formulate the problems as non-linear integer programming problems. We propose several heuristic algorithms to approximate the optimal solution. The proposed algorithms are evaluated by extensive experiments using both synthetic data and real data from commercial search engines. The results demonstrate the effectiveness of the proposed algorithms. Our work also yields many insights about the impact of different input properties on the performance of each algorithm. We believe that this paper will provide valuable guidance to the design of the index shard replication strategy in practice. [ABSTRACT FROM AUTHOR]

Enterprise users at different geographic locations generate large-volume data that is stored at different geographic datacenters. These users may also perform big data analytics on the stored data to identify valuable information in order to make strategic decisions. However, it is well known that performing big data analytics on data in geographical-located datacenters usually is time-consuming and costly. In some delay-sensitive applications, the query result may become useless if answering a query takes too long time. Instead, sometimes users may only be interested in timely approximate rather than exact query results. When such approximate query evaluation is the case, applications must sacrifice timeliness to get more accurate evaluation results or tolerate evaluation result with a guaranteed error bound obtained from analyzing the samples of the data to meet their stringent timeline. In this paper, we study quality-of-service (QoS)-aware data replication and placement for approximate query evaluation of big data analytics in a distributed cloud, where the original (source) data of a query is distributed at different geo-distributed datacenters. We focus on the problems of placing data samples of the source data at some strategic datacenters to meet stringent query delay requirements of users, by exploring a non-trivial trade-off between the cost of query evaluation and the error bound of the evaluation result. We first propose an approximation algorithm with a provable approximation ratio for a single approximate query. We then develop an efficient heuristic algorithm for evaluating a set of approximate queries with the aim to minimize the evaluation cost while meeting the delay requirements of these queries. We finally demonstrate the effectiveness and efficiency of the proposed algorithms through both experimental simulations and implementations in a real test-bed, real datasets are employed. Experimental results show that the proposed algorithms are promising. [ABSTRACT FROM AUTHOR]

The Internet is a gigantic distributed system where the end-to-end (E2E) quality-of-service (QoS) plays an important role. Yet the current inter-domain routing protocol, namely, the Border Gateway Protocol (BGP), cannot provide E2E QoS guarantees. The main reason is that an autonomous system (AS) can only receive guarantees from its first-hop ASes via service level agreements (SLAs). But beyond the first-hop, QoS along the path from a source AS to a destination AS is not within the source AS's control regime. This makes it difficult to provide high quality-of-experience services to many Internet users even when many content providers are willing to pay for such high quality E2E guarantees. In this paper, we investigate the feasibility of providing high QoS-guaranteed E2E transit services by utilizing a (small) set of ASes/IXPs to serve as “brokers” to provide supervision, control and resource negotiation. Finding an optimal set of ASes as brokers can be formulated as a Maximum Coverage with $B-$ dominating path Guarantee (MCBG) problem, and we show that it is in fact NP-hard. To address this problem, we design a $(\frac{1{-}e^{-\!1}}{2}){-}$ approximation algorithm and also an efficient heuristic algorithm when additional constraints (e.g., the path length) are considered. We further analyze the APX-hardness of the MCBG problem to reveal the existence of the best approximation ratio. Based on the current Internet topology, we demonstrate that it is indeed feasible to provide high QoS guarantees for most E2E connections with only a small broker set: with only 0.19, 1.9 or 6.8 percent ASes/IXPs serving as brokers, 53.13, 85.41 or 99.29 percent of all global E2E connections can receive high QoS-guaranteed services. Finally, we provide an economic model to study the behaviours of ASes when cooperating our brokerage scheme with the BGP protocol, and show that there are incentives to form and maintain such a brokerage coalition. [ABSTRACT FROM AUTHOR]

The problem of scheduling malleable tasks with precedence constraints is one of the most important strongly $\mathcal {NP}$ -hard problems, given $m$ identical processors and $n$ tasks. A malleable task is one that runs in parallel on a varying number of processors. In addition, the processing sequences of tasks are constrained by the precedence constraints. The goal is to find a feasible schedule that minimizes the makespan (maximum completion time). This article presents an iterative method for improving the performance ratio of scheduling malleable tasks. The proposed algorithm achieves an approximation ratio of 4.4841 after 2 iterations. This improves the so far best-known factor of 4.7306 due to Jansen and Zhang. For a large number of iterations ( $>100$ ), the approximation ratio of the proposed algorithm is tends toward $2+\sqrt{2}\approx 3.4143$ . [ABSTRACT FROM AUTHOR]

Mobile micro-clouds are promising for enabling performance-critical cloud applications. However, one challenge therein is the dynamics at the network edge. In this paper, we study how to place service instances to cope with these dynamics, where multiple users and service instances coexist in the system. Our goal is to find the optimal placement (configuration) of instances to minimize the average cost over time, leveraging the ability of predicting future cost parameters with known accuracy. We first propose an offline algorithm that solves for the optimal configuration in a specific look-ahead time-window. Then, we propose an online approximation algorithm with polynomial time-complexity to find the placement in real-time whenever an instance arrives. We analytically show that the online algorithm is $O(1)$ -competitive for a broad family of cost functions. Afterwards, the impact of prediction errors is considered and a method for finding the optimal look-ahead window size is proposed, which minimizes an upper bound of the average actual cost. The effectiveness of the proposed approach is evaluated by simulations with both synthetic and real-world (San Francisco taxi) user-mobility traces. The theoretical methodology used in this paper can potentially be applied to a larger class of dynamic resource allocation problems. [ABSTRACT FROM PUBLISHER]

Mobile cloud computing is emerging as a main ubiquitous computing platform to provide rich cloud resources for various applications of mobile devices. Although most existing studies in mobile cloud computing focus on energy savings of mobile devices by offloading computing-intensive jobs from mobile devices to remote clouds, the access delays between mobile users and remote clouds usually are long and sometimes unbearable. Cloudlet as a new technology is capable to bridge this gap, and can enhance the performance of mobile devices significantly while meeting the crisp response time requirements of mobile users. In this paper, we study the cloudlet placement problem in a large-scale Wireless Metropolitan Area Network (WMAN) consisting of many wireless Access Points (APs). We first formulate the problem as a novel capacitated cloudlet placement problem that places $K$ cloudlets to some strategic locations in the WMAN with the objective to minimize the average access delay between mobile users and the cloudlets serving the users. We then propose an exact solution to the problem by formulating it as an Integer Linear Programming (ILP). Due to the poor scalability of the ILP, we instead propose an efficient heuristic for the problem. For a special case of the problem where all cloudlets have identical computing capacities, we devise novel approximation algorithms with guaranteed approximation ratios. We also devise an online algorithm for dynamically allocating user requests to different cloudlets, if the $K$ cloudlets have already been placed. We finally evaluate the performance of the proposed algorithms through experimental simulations. Simulation results demonstrate that the proposed algorithms are promising and scalable. [ABSTRACT FROM AUTHOR]

In high-end data processing systems, such as databases, the execution concurrency level rises continuously since the introduction of multicore processors. This happens both on premises and in the cloud. For these systems, a buffer pool management of high scalability plays an important role on overall system performance. The scalability of buffer pool management is largely determined by its data replacement algorithm, which is a major component in the buffer pool management. It can seriously degrade the scalability if not designed and implemented properly. The root cause is its use of lock-protected data structures that incurs high contention with concurrent accesses. A common practice is to modify the replacement algorithm to reduce the contention on the lock(s), such as approximating the LRU replacement with the CLOCK algorithm or partitioning the data structures and using distributed locks. Unfortunately, the modification usually compromises the algorithm's hit ratio, a major performance goal. It may also involve significant effort on overhauling the original algorithm design and implementation. This paper provides a general solution to improve the scalability of a buffer pool management using any replacement algorithms for the data processing systems on physical on-premises machines and virtual machines in the cloud. Instead of making a difficult trade-off between the high hit ratio of a replacement algorithm and the low lock contention of its approximation, we design a system framework, called BP-Wrapper, that eliminates almost all lock contention without requiring any changes to an existing algorithm. In BP-Wrapper, we use a dynamic batching technique and a prefetching technique to reduce lock contention and to retain high hit ratio. The implementation of BP-Wrapper in PostgreSQL adds only about 300 lines of C code. It can increase the throughput by up to two folds compared with the replacement algorithms with lock contention when running TPC-C-like and TPC-W-like workloads. [ABSTRACT FROM AUTHOR]

Peer to peer (P2P) systems have moved from application specific architectures to a generic service oriented design philosophy. This raised interesting problems in connection with providing useful P2P middleware services capable of dealing with resource assignment and management in a large-scale, heterogeneous and unreliable environment. The slicing problem consists of partitioning a P2P network into $k$ groups (slices) of a given portion of the network nodes that share similar resource values. As the network is large and dynamic this partitioning is continuously updated without any node knowing the network size. In this paper, we propose the first algorithm to solve the slicing problem. We introduce the metric of slice disorder and show that the existing ordering algorithm cannot nullify this disorder. We propose a new algorithm that speeds up the existing ordering algorithm but that suffers from the same inaccuracy. Then, we propose another algorithm based on ranking that is provably convergent under reasonable assumptions. In particular, we notice experimentally that ordering algorithms suffer from resource-correlated churn while the ranking algorithm can cope with it. These algorithms are proved viable theoretically and experimentally. [ABSTRACT FROM PUBLISHER]

Cloud providers provision their heterogeneous resources such as CPUs, memory, and storage in the form of virtual machine (VM) instances which are then allocated to the users. One of the major challenges faced by the cloud providers is to allocate and provision these resources such that their profit is maximized, and the resources are utilized efficiently. Recently, cloud providers have introduced auction-based models which allow users to submit bids for their requested VMs. We address the problem of autonomic VM provisioning and allocation for the auction-based model considering multiple types of resources by designing an approximation mechanism. In addition, the mechanism determines the payment the users have to pay for using the allocated resources. This problem is computationally intractable, and our proposed mechanism is by far the strongest approximation result that can be achieved for this problem. We show that the proposed approximation mechanism is a polynomial-time approximation scheme (PTAS). Furthermore, our proposed mechanism drives the system into an equilibrium in which the users do not have incentives to manipulate the system by untruthfully reporting their VM bundle requests and valuations. We perform extensive experiments using real workload traces in order to investigate the performance of the proposed mechanism. [ABSTRACT FROM AUTHOR]

Infrastructure-as-a-Service clouds offer diverse pricing options, including on-demand and reserved instances with various discounts to attract different cloud users. A practical problem facing cloud users is how to minimize their costs by choosing among different pricing options based on their own demands. In this paper, we propose a new cloud brokerage service that reserves a large pool of instances from cloud providers and serves users with price discounts. The broker optimally exploits both pricing benefits of long-term instance reservations and multiplexing gains. We propose dynamic strategies for the broker to make instance reservations with the objective of minimizing its service cost. These strategies leverage dynamic programming and approximation algorithms to rapidly handle large volumes of demand. Our extensive simulations driven by large-scale Google cluster-usage traces have shown that significant price discounts can be realized via the broker. [ABSTRACT FROM PUBLISHER]

The optimal placement of service facilities largely determines the capability of a data network to efficiently support its users' service demands. As centralized solutions over large-scale distributed environments are extremely expensive, inefficient or even infeasible, distributed approaches that rely on partial topology and demand information are the only credible approaches to the service placement problem, even at the expense of non-guaranteed optimality. In this paper, we propose a distributed service migration heuristic that iteratively solves instances of the 1-median problem pushing progressively the service to more cost-effective locations. Key to our algorithm is a traffic-aware centrality metric, called weighted conditional betweenness centrality (wCBC), that captures the ability of a node to act as service demand concentrator and is employed in both selecting the nodes and setting their weights for the 1-median problem instance. The assessment of our heuristic proceeds in two steps. First, assuming (ideal) knowledge of the invoked wCBC metric, we carry out a proof-of-concept study that demonstrates the effectiveness of the heuristic over synthetic and real-world topologies as well as its advantages against comparable local-search-like migration schemes. Next, we devise practical protocol implementations that approximate the heuristic using local measurements of transit traffic and preserve the excellent accuracy and fast convergence properties of the algorithm for different routing policies. Our solution applies to a broad range of networking scenarios, and is very relevant to the emerging trends for in-network storage and involvement of the end-user in the creation and distribution of lightweight (autonomic) service facilities. [ABSTRACT FROM AUTHOR]

Parallel and concurrent structures are widely used both as standalone components and as building blocks of larger systems. Efficient models of parallelism and concurrency are therefore necessary to understand the impact of parallelism in system performance. These models become more critical with the proliferation of adaptive systems that require solving a large number of performance models in a short amount of time to facilitate configuration decisions dynamically. This paper presents efficient response time approximations for parallel constructs modeled as fork and join queues. These approximations can be used by practitioners and performance engineers to quickly compare the performance of contending configurations. The contributions over previous work are twofold. First, this paper considers heterogeneous multiclass fork and join open and closed queuing networks. Second, the paper also presents models for fork and join where each class of jobs might fork to different queues in a probabilistic manner. [ABSTRACT FROM AUTHOR]

Interactivity is a primary performance measure for distributed interactive applications (DIAs) that enable participants at different locations to interact with each other in real time. Wide geographical spreads of participants in large-scale DIAs necessitate distributed deployment of servers to improve interactivity. In a distributed server architecture, the interactivity performance depends on not only client-to-server network latencies but also interserver network latencies, as well as synchronization delays to meet the consistency and fairness requirements of DIAs. All of these factors are directly affected by how the clients are assigned to the servers. In this paper, we investigate the problem of effectively assigning clients to servers for maximizing the interactivity of DIAs. We focus on continuous DIAs that changes their states not only in response to user operations but also due to the passing of time. We analyze the minimum achievable interaction time for DIAs to preserve consistency and provide fairness among clients, and formulate the client assignment problem as a combinatorial optimization problem. We prove that this problem is NP-complete. Three heuristic assignment algorithms are proposed and their approximation ratios are theoretically analyzed. The performance of the algorithms is also experimentally evaluated using real Internet latency data. The experimental results show that our proposed Greedy Assignment and Distributed-Modify Assignment algorithms generally produce near optimal interactivity and significantly reduce the interaction time between clients compared to the intuitive algorithm that assigns each client to its nearest server. [ABSTRACT FROM AUTHOR]

Dynamic consolidation of virtual machines (VMs) is an effective way to improve the utilization of resources and energy efficiency in cloud data centers. Determining when it is best to reallocate VMs from an overloaded host is an aspect of dynamic VM consolidation that directly influences the resource utilization and quality of service (QoS) delivered by the system. The influence on the QoS is explained by the fact that server overloads cause resource shortages and performance degradation of applications. Current solutions to the problem of host overload detection are generally heuristic based, or rely on statistical analysis of historical data. The limitations of these approaches are that they lead to suboptimal results and do not allow explicit specification of a QoS goal. We propose a novel approach that for any known stationary workload and a given state configuration optimally solves the problem of host overload detection by maximizing the mean intermigration time under the specified QoS goal based on a Markov chain model. We heuristically adapt the algorithm to handle unknown nonstationary workloads using the Multisize Sliding Window workload estimation technique. Through simulations with workload traces from more than a thousand PlanetLab VMs, we show that our approach outperforms the best benchmark algorithm and provides approximately 88 percent of the performance of the optimal offline algorithm. [ABSTRACT FROM AUTHOR]

The multiple longest common subsequence (MLCS) problem, which is related to the measurement of sequence similarity, is one of the fundamental problems in many fields. As an NP-hard problem, finding a good approximate solution within a reasonable time is important for solving large-size problems in practice. In this paper, we present a new progressive algorithm, Pro-MLCS, based on the dominant point approach. Pro-MLCS can find an approximate solution quickly and then progressively generate better solutions until obtaining the optimal one. Pro-MLCS employs three new techniques: 1) a new heuristic function for prioritizing candidate points; 2) a novel $(d)$-index-tree data structure for efficient computation of dominant points; and 3) a new pruning method using an upper bound function and approximate solutions. Experimental results show that Pro-MLCS can obtain the first approximate solution almost instantly and needs only a very small fraction, e.g., 3 percent, of the entire running time to get the optimal solution. Compared to existing state-of-the-art algorithms, Pro-MLCS can find better solutions in much shorter time, one to two orders of magnitude faster. In addition, two parallel versions of Pro-MLCS are developed: DPro-MLCS for distributed memory architecture and DSDPro-MLCS for hierarchical distributed shared memory architecture. Both parallel algorithms can efficiently utilize parallel computing resources and achieve nearly linear speedups. They also have a desirable progressiveness property—finding better solutions in shorter time when given more hardware resources. [ABSTRACT FROM AUTHOR]

With the advent of smartphone technology, it has become possible to conceive of entirely new classes of applications. Social swarming, in which users armed with smartphones are directed by a central director to report on events in the physical world, has several real-world applications: search and rescue, coordinated fire-fighting, and the DARPA balloon hunt challenge. In this paper, we focus on the following problem: how does the director optimize the selection of reporters to deliver credible corroborating information about an event. We first propose a model, based on common notions of believability, about the credibility of information. We then cast the problem posed above as a discrete optimization problem, prove hardness results, introduce optimal centralized solutions, and design an approximate solution amenable to decentralized implementation whose performance is about 20 percent off, on average, from the optimal (on real-world data sets derived from Google News) while being three orders of magnitude more computationally efficient. More interesting, a time-averaged version of the problem is amenable to a novel stochastic utility optimization formulation, and can be solved optimally, while in some cases yielding decentralized solutions. To our knowledge, we are the first to propose and explore the problem of extracting credible information from a network of smartphones. [ABSTRACT FROM PUBLISHER]

Aggregation operations are important in WSN applications. Since large numbers of applications only require approximate aggregation results rather than the exact ones, some approximate aggregation algorithms have been proposed to save energy. However, the error bounds of these algorithms are fixed and it is impossible to adjust the error bounds automatically, so they cannot meet the requirement of arbitrary precision required by various users. Thus, a uniform sampling-based algorithm was proposed by the authors of this paper to satisfy arbitrary precision requirement. Unfortunately, this uniform sampling-based algorithm is only suitable for static sensor networks. To overcome the shortcoming of the uniform sampling-based algorithm, this paper proposes four Bernoulli sampling-based and distributed approximate aggregation algorithms to process the snapshot and continuous aggregation queries in dynamic sensor networks. Theoretical analysis and experimental results show that the proposed algorithms have high performance in terms of accuracy and energy consumption. [ABSTRACT FROM AUTHOR]

Maintaining interactivity is one of the key challenges in distributed virtual environments (DVEs). In this paper, we consider a new problem, termed the interactivity-constrained server provisioning problem, whose goal is to minimize the number of distributed servers needed to achieve a prespecified level of interactivity. We identify and formulate two variants of this new problem and show that they are both NP-hard via reductions to the set covering problem. We then propose several computationally efficient approximation algorithms for solving the problem. The main algorithms exploit dependencies among distributed servers to make provisioning decisions. We conduct extensive experiments to evaluate the performance of the proposed algorithms. Specifically, we use both static Internet latency data available from prior measurements and topology generators, as well as the most recent, dynamic latency data collected via our own large-scale deployment of a DVE performance monitoring system over PlanetLab. The results show that the newly proposed algorithms that take into account interserver dependencies significantly outperform the well-established set covering algorithm for both problem variants. [ABSTRACT FROM PUBLISHER]

Topology control is one vital factor to a wireless network's efficiency. A Connected Dominating Set (CDS) can be a useful basis of a backbone topology construction. In this paper, a special CDS, named \alpha Minimum rOuting Cost CDS (\alpha-MOC-CDS), will be studied to improve the performance of CDS based broadcasting and routing. In this paper, we prove that construction of a minimum \alpha-MOC-CDS is NP-hard in a general graph and we propose a heuristic algorithm for construction of \alpha-MOC-CDS. [ABSTRACT FROM AUTHOR]

In Chip Multiprocessors (CMPs) architecture, it is common that multiple cores share some on-chip cache. The sharing may cause cache thrashing and contention among co-running jobs. Job co-scheduling is an approach to tackling the problem by assigning jobs to cores appropriately so that the contention and consequent performance degradations are minimized. Job co-scheduling includes two tasks: the estimation of co-run performance, and the determination of suitable co-schedules. Most existing studies in job co-scheduling have concentrated on the first task but relies on simple techniques (e.g., trying different schedules) for the second. This paper presents a systematic exploration to the second task. The paper uncovers the computational complexity of the determination of optimal job co-schedules, proving its NP-completeness. It introduces a set of algorithms, based on graph theory and Integer/Linear Programming, for computing optimal co-schedules or their lower bounds in scenarios with or without job migrations. For complex cases, it empirically demonstrates the feasibility for approximating the optimal effectively by proposing several heuristics-based algorithms. These discoveries may facilitate the assessment of job co-schedulers by providing necessary baselines, as well as shed insights to the development of co-scheduling algorithms in practical systems. [ABSTRACT FROM AUTHOR]

When a sensor network is deployed in the field it is typically required to support multiple simultaneous missions, which may start and finish at different times. Schemes that match sensor resources to mission demands thus become necessary. In this paper, we consider new sensor-assignment problems motivated by frugality, i.e., the conservation of resources, for both static and dynamic settings. In the most general setting, the problems we study are NP-hard even to approximate, and so we focus on heuristic algorithms that perform well in practice. In the static setting, we propose a greedy centralized solution and a more sophisticated solution that uses the Generalized Assignment Problem model and can be implemented in a distributed fashion. In what we call the dynamic setting, missions arrive over time and have different durations. For this setting, we give heuristic algorithms in which available sensors propose to nearby missions as they arrive. We find that the overall performance can be significantly improved if available sensors sometimes refuse to offer utility to missions they could help, making this decision based on the value of the mission, the sensor's remaining energy, and (if known) the remaining target lifetime of the network. Finally, we evaluate our solutions through simulations. [ABSTRACT FROM PUBLISHER]