Submodular maximization is an important building block for developing algorithms in many areas such as machine learning and data mining. Due to the NP-hardness of the problem, analysis of submodular maximization algorithms typically provides pessimistic worst-case approximation factors only. It is not easy to evaluate how close a produced solution is to an optimal one for a given problem instance. In this paper, we develop new data-dependent upper bounds for submodular maximization with a knapsack constraint. We theoretically prove that they dominate the optimal solution and empirically demonstrate their advantages in certifying how close to optimal a solution is through experiments with real-world datasets.

The rise of LLMs has driven demand for private serverless deployments, characterized by moderate-sized models and infrequent requests. While existing serverless solutions follow exclusive GPU allocation, we take a step back to explore modern platforms and find that: Emerging CPU architectures with built-in accelerators are capable of serving LLMs but remain underutilized, and both CPUs and GPUs can accommodate multiple LLMs simultaneously. We propose SLINFER, a resource-efficient serverless inference scheme tailored for small- to mid-sized LLMs that enables elastic and on-demand sharing across heterogeneous hardware. SLINFER tackles three fundamental challenges: (1) precise, fine-grained compute resource allocation at token-level to handle fluctuating computational demands; (2) a coordinated and forward-looking memory scaling mechanism to detect out-ofmemory hazards and reduce operational overhead; and (3) a dual approach that consolidates fragmented instances through proactive preemption and reactive bin-packing. Experimental results on 4 32-core CPUs and 4 A100 GPUs show that SLINFER improves serving capacity by 47% - 62% through sharing, while further leveraging CPUs boosts this to 86% - 154%.

The online caching problem aims to minimize cache misses when serving a sequence of requests under a limited cache size. While naive learning-augmented caching algorithms achieve ideal $1$-consistency, they lack robustness guarantees. Existing robustification methods either sacrifice $1$-consistency or introduce excessive computational overhead. In this paper, we introduce Guard, a lightweight robustification framework that enhances the robustness of a broad class of learning-augmented caching algorithms to $2H_{k-1} + 2$, while preserving their $1$-consistency. Guard achieves the current best-known trade-off between consistency and robustness, with only $\mathcal{O}(1)$ additional per-request overhead, thereby maintaining the original time complexity of the base algorithm. Extensive experiments across multiple real-world datasets and prediction models validate the effectiveness of Guard in practice.

This article introduces a multiview 3-D microscopic profilometry system equipped with tilted cameras adhering to the Scheimpflug condition and a vertically aligned projector. It utilizes a novel 3-D cross-ratio invariant (3D-CRI) model that offers inherent self-correction, enhanced global consistency, and computational efficiency. The inherent self-correction mitigates optical contaminations like multiple reflections by using deviations from the epipolar line for optimal candidate selection. The model is also designed as spatial lines to associate the approximate linear error distribution across depths, thereby facilitating its further correction (e.g., proposed embedded linear compensation method to address data inconsistency among various binocular projector-camera setups). Additionally, the model simplifies computational demands by directly correlating phase differences to spatial coordinates. Furthermore, a conversion method from the triangular stereo to the 3D-CRI model is developed, avoiding the complex per-pixel calibration. The experiments are conducted to verify robustness, globally consistent accuracy, and speed performance. The experimental results validate that the system is robust to multiple reflections by testing on the printed circuit boards with dense components. The global consistency is also verified by the experiments with better quantitative metrics within the whole measurement range over ten times the depth of field. In particular, the quantitative metrics of theZ-axis are halved. The speed performance shows that our method is the fastest among competing techniques.

This paper addresses the data-locality-aware task assignment and scheduling problem for distributed job executions. Our goal is to minimize job completion times without prior knowledge of future job arrivals. We propose an Optimal Balanced Task Assignment algorithm (OBTA), which achieves minimal job completion times while significantly reducing computational overhead through efficient narrowing of the solution search space. To balance performance and efficiency, we extend the approximate Water-Filling (WF) algorithm, providing a rigorous proof that its approximation factor equals the number of task groups in a job. We also introduce a novel heuristic, Replica-Deletion (RD), which outperforms WF by leveraging global optimization techniques. To further enhance scheduling efficiency, we incorporate job ordering strategies based on a shortest-estimated-time-first policy, reducing average job completion times across workloads. Extensive trace-driven evaluations validate the effectiveness and scalability of the proposed algorithms.

Multi-Agent Pathfinding (MAPF) is the problem of finding plans for multiple agents such that every agent moves from its start location to its goal location without collisions. If unexpected events delay some agents during plan execution, it may not be possible for the agents to continue following their plans without causing any collision. We define and solve a T-robust MAPF problem that seeks plans that can be followed even if some delays occur, under the generalized MAPFR setting with continuous time notions. The proposed approach is complete and provides provably optimal solutions. We also develop an exact method for collision detection among agents that can be delayed. We experimentally evaluate our proposed approach in terms of efficiency and plan cost.

In this paper, we study an online cost optimization problem for distributed data access. The goal of this problem is to dynamically create and delete data copies in a multi-server distributed system as time goes, in order to minimize the total storage and network cost of serving access requests. We propose an online algorithm with randomized storage periods of data copies in the servers, and derive an optimal probability density function of storage periods, which makes the algorithm achieve a competitive ratio of $1 + \frac{{\sqrt 2 }}{2}$. An example is presented to show that the competitive analysis of our algorithm is tight. Experimental evaluations using real data access traces demonstrate that our algorithm outperforms the best known deterministic algorithm.

In this paper, we study learning-augmented algorithms for the Bahncard problem. The Bahncard problem is a generalization of the ski-rental problem, where a traveler needs to irrevocably and repeatedly decide between a cheap short-term solution and an expensive long-term one with an unknown future. Even though the problem is canonical, only a primal-dual-based learning-augmented algorithm was explicitly designed for it. We develop a new learning-augmented algorithm, named PFSUM, that incorporates both history and short-term future to improve online decision making. We derive the competitive ratio of PFSUM as a function of the prediction error and conduct extensive experiments to show that PFSUM outperforms the primal-dual-based algorithm.

In real-world multi-agent applications, unexpected conditions can break the assumptions made in path planning and degrade the effectiveness of path execution. This paper studies robust and effective execution of multi-agent path plans under uncertainty. To guarantee conflict-freeness and deadlock-freeness, we define a feasibility problem to check whether the remaining portion of a path plan can be successfully executed. We prove that the problem is NP-complete and propose a feasibility test algorithm. We further develop algorithms to coordinate the agents online and have as many of them as possible moving concurrently to maximize the effectiveness of execution. We experimentally demonstrate the path execution effectiveness and computational efficiency of our algorithms.

We study a flexible job scheduling problem. A set of jobs is released over time, each with a starting deadline and a processing length. The jobs are to be started by an online scheduler no later than their starting deadlines and will run nonpreemptively. The objective is to minimize the span -- the time duration for which at least one job is running. We present a new lower bound of 4 on the competitiveness of any online algorithm. We also establish tight competitiveness bounds in the learning-augmented setting of the problem.

MinUsageTime DBP is a variant of the Dynamic Bin Packing (DBP) problem that seeks to minimize the accumulated length of time for which bins are used in packing a sequence of items. This paper studies the MinUsageTime DBP problem with predictions about item durations. We establish tight competitiveness bounds over the entire spectrum of prediction errors.

This paper studies an online replication problem for distributed data access. The goal is to dynamically create and delete data copies in a multi-server system as time passes to minimize the total storage and network cost of serving access requests. We study the problem in the emergent learning-augmented setting, assuming simple binary predictions about inter-request times at individual servers. We develop an online algorithm and prove that it is (5+α/3)-consistent (competitiveness under perfect predictions) and (1+1/α)-robust (competitiveness under terrible predictions), where α◰(0, 1] is a hyper-parameter representing the level of distrust in the predictions. We also study the impact of mispredictions on the competitive ratio of the proposed algorithm and adapt it to achieve a bounded robustness while retaining its consistency. We further establish a lower bound of 3/2 on the consistency of any deterministic learning-augmented algorithm. Experimental evaluations are carried out to evaluate our algorithms using real data access traces.

This work concerns evolutionary approaches to black-box noisy optimization where the problem is accessed via noisy function evaluations. An evolution strategy (ES) algorithm is proposed, which uses a Gaussian distribution to guide the search and requires only the comparisons among solutions. The new method achieves the similar convergence rate as finite-difference based gradient methods on non-convex landscapes, while being adaptive in the sense that the convergence is ensured with any initial step-size. We further improve the method with a variance adaptation mechanisms that alleviates the need for hyper-parameter tunning and an asynchronous parallelization implementation that enables linear speedup. The persistent monitoring task is chosen as an application to investigate the effectiveness of the proposed method. The task is to schedule a team of agents to minimize the uncertainties of some targets in a changing environment defined on a grid map. We show in the single-agent case that the task can be cast into a sequence of pathfinding subproblems of which the sequential order can be modeled as a Markov decision procedure and solved by the proposed ES method. In the multi-agent case, we show that solving the single-agent subproblems using the ES method in a round-robin way can provide collision-free solutions. Numerical studies demonstrate the reduction in convergence time and the robustness against complicated environments relative to several existing evolutionary algorithms and zeroth-order gradient methods.

With rapidly growing sizes of online social networks, computational challenges arise in analyzing the diffusion process over networks. Sampling methods are commonly used to study the cascade effect and estimate users' influence. In this paper, we propose a brand-new sampling method, called 2-hop+ sampling for quickly and accurately estimating the cascade size generated by a set of seed users under the independent cascade model. Our method generates only samples with at least one 2-hop live path from the source to reduce the number of samples. We further enhance the sampling efficiency of our method by a SkipEdge technique. Moreover, we improve the generalized stopping rule algorithm to obtain an (,)-estimate of the mean of random variables with fewer samples needed. Extensive experiments with real-world datasets show that our techniques can significantly improve the estimation efficiency compared to the state-of-the-art methods.

It is common for big data applications to run across multiple datacenters or machine clusters because the data inputs are distributed over different locations. This paper studies a job scheduling problem for distributed job execution in which the data inputs to jobs may be replicated across multiple locations so that each task of a job can be executed at any one of these locations. To schedule the jobs, we need to determine the processing locations for the tasks of each job and the execution order of the tasks at each location. We focus on the objective of minimizing the average job response time. We first design a task assignment algorithm to balance the task allocation among various locations. We then further develop integrated solutions that conduct task assignment and scheduling together. We experimentally evaluate our algorithms using real job traces. The results show that our algorithms can significantly reduce the job response times compared to a baseline that allocates each task to a fixed location for processing.

Thanks to billions of users in online social networks (OSNs), viral marketing becomes one of the most effective promotion channels for various new products or campaigns. Influence maximization is a classic problem in viral marketing, which has been extensively studied in the past two decades. Existing algorithms for influence maximization, however, mostly focus on single machine processing. To address the influence maximization problem on a massive scale, we design distributed algorithms via a cluster of machines, which can effectively speed up the computation while maintaining the state-of-the-art (1 -1/e-c)-approximation guarantee. Our distributed algorithms consist of two building blocks: (i) distributed reverse influence sampling, and (ii) element-distributed maximum coverage. We carry out extensive experiments on real datasets with millions of nodes and billions of edges to demonstrate the scalability of our distributed algorithms for both influence maximization and maximum coverage. In particular, our distributed algorithms accelerate the state-of-the-art IMM algorithm by 31x-56x times using a machine with 64 cores.

We study a generalized busy-time scheduling model on heterogeneous machines. The input to the model includes a set of jobs and a set of machine types. Each job has a size and a time interval during which it should be processed. Each job is to be placed on a machine for execution. Different types of machines have distinct capacities and cost rates. The total size of the jobs running on a machine must always be kept within the machine's capacity, giving rise to placement restrictions for jobs of various sizes among the machine types. Each machine used is charged according to the time duration in which it is busy, i.e., it is processing jobs. The objective is to schedule the jobs into machines to minimize the total cost of all the machines used. We develop an$O(1)$-approximation algorithm in the offline setting and an$O(\mu)$-competitive algorithm in the online setting (where$\mu$is the max/min job length ratio), both of which are asymptotically optimal. This article significantly improves the analysis of the algorithms over our preliminary work.

We consider two combinatorial optimization problems, named Generalized Skyline Interval Coloring (GSIC) and Dynamic Geometric Bin Packing (DGBP). The input to both problems is a set of interval jobs, with each job specified by a horizontal active time interval and a vertical size. For GSIC, each job is to be allocated a vertical interval of the specified size in the range [0, +∞). For any two jobs with overlapping active intervals, their vertical intervals must not overlap. The instantaneous cost of an allocation at any time is defined as the highest point allocated to the active jobs. The target is to minimize the accumulated cost over time. For DGBP, each job is to be assigned to a machine of capacity g and be allocated a vertical interval of the specified size in the range [0, g). For any two jobs with overlapping active intervals, if they are assigned to the same machine, their vertical intervals must not overlap. The target is to minimize the total machine busy time, where the busy time of a machine is the time duration in which there is at least one active job in the machine. We develop O(1)-approximation algorithms for both problems in the offline setting and asymptotically optimal algorithms in the non-clairvoyant and clairvoyant online settings.

We study the multi-agent pickup and delivery problem with task deadlines, where a team of agents execute tasks with individual deadlines to maximize the number of tasks completed by their deadlines. We take an integrated approach that assigns and plans one task at a time taking into account the agent states resulting from all the previous task assignments and path planning. We define metrics to effectively determine which agent ought to execute a given task and which task is most worth assignment next. We leverage the bounding technique to greatly improve the computational efficiency.

This paper studies a generalized busy-time scheduling model on heterogeneous machines. The input to the model includes a set of jobs and a set of machine types. Each job has a size and a time interval during which it should be processed. Each job is to be placed on a machine for execution. Different types of machines have distinct capacities and cost rates. The total size of the jobs running on a machine must always be kept within the machine's capacity, giving rise to placement restrictions for jobs of various sizes among the machine types. Each machine used is charged according to the time duration in which it is busy, i.e., it is processing jobs. The objective is to schedule the jobs onto machines to minimize the total cost of all the machines used. We develop an O(1)-approximation algorithm in the offline setting and an O(μ)-competitive algorithm in the online setting (where μ is the max/min job length ratio), both of which are asymptotically optimal.

Online Social Network (OSN) providers usually conduct advertising campaigns by inserting social ads into promoted posts. Whenever a user engages in a promoted ad, she may further propagate the promoted ad to her followers recursively and the propagation process is known as the word-of-mouth effect. In order to spread the promotion cascade widely and efficiently, the OSN provider often tends to select the influencers, who normally have large audiences over the social network, to initiate the advertising campaign. This marketing model, also termed as influencer marketing, has been gaining increasing traction and investment and is rapidly becoming one of the most widely-used channels in digital marketing. In this paper, we formulate the problem for the OSN provider to derive the influence contributions of influencers given the campaign result, considering the viral propagation of the ads, namely influence contribution allocation (ICA) . We make a connection between ICA and the concept of Shapley value in cooperative game theory to reveal the rationale behind ICA. A naive method to obtain the solution to ICA is to enumerate all possible cascades delivering the campaign result, resulting in an exponential number of potential cascades, which is computationally intractable. Moreover, generating a cascade producing the exact campaign result is non-trivial. Facing the challenges, we develop an exact solution in linear time under the linear threshold (LT) model, and devise a fully polynomial-time randomized approximation scheme (FPRAS) under the independent cascade (IC) model. Specifically, under the IC model, we propose an efficient approach to estimate the expected influence contribution in probabilistic graphs modeling OSNs by designing a scalable sampling method with provable accuracy guarantees. We conduct extensive experiments and show that our algorithms yield solutions with remarkably higher quality over several baselines and improve the sampling efficiency significantly.

Cloud gaming has been very popular recently, but providing satisfactory gaming experiences to players at a modest cost is still challenging. Colocating several games onto one server could improve server utilization. However, prior work regarding colocating games either ignores the performance interference between games or uses simple performance model to charaterize it, which may make inefficient game colocation decisions and cause QoS violations. In this article, we address the resource allocation issues for colocating games in cloud gaming. We first propose a novel machine learning-based performance model, which is able to capture the complex relationship among the performance interference, the contention features of colocated games and resource partition. Guided by the performance model, we then propose efficient and effective algorithms for two resource allocation scenarios in cloud gaming. We evaluate the proposed solutions through extensive experiments using a large number of real popular games. The results show that our performance model is able to identify whether a colocated game satisfies QoS requirement within an average error of 5 percent, which significantly outperforms the alternatives. Our resource allocation algorithms are able to increase the resource utilization by up to 60 percent compared to the state-of-the-art solutions.

We study a busy-time scheduling problem on heterogeneous machines (BSHM) which is motivated by server acquisition and task dispatching in cloud computing. The input of BSHM is a set of interval jobs, each specified by a size, an arrival time and a departure time. When a job arrives, it must be placed onto a machine immediately. The execution of a job cannot be interrupted until it departs. At any time, the total size of the jobs running on a machine cannot exceed the machine's capacity. m different types of machines are available and abundant machines are provided for each type. A type-i machine has a capacity giand is charged at a cost rate riwhen busy (running jobs). The target of BSHM is to schedule the given set of jobs onto machines with the minimum accumulated cost. Suppose the machine types are sorted by their capacities so that g1g2≤ ⋯ ≤ gm. We first consider two typical cases of BSHM. In BSHM-DEC, ri/gi≥ ri+1/gi+1holds for each i. In BSHM-INC, ri/gi≤ ri+1/gi+1holds for each i. For each case, we propose a O(1)-approximation algorithm in the offline setting and a O(μ)-competitive algorithm in the nonclairvoyant online setting. Finally, we discuss how the scheduling strategies developed for these two cases can be combined to deal with the general BSHM problem.

Nearest neighbor search is a fundamental problem in computer vision and machine learning. The straightforward solution, linear scan, is both computationally and memory intensive in large scale high-dimensional cases, hence is not preferable in practice. Therefore, there have been a lot of interests in algorithms that perform approximate nearest neighbor (ANN) search. In this paper, we propose a novel addition-based vector quantization algorithm, Asymmetric Mapping Quantization (AMQ), to efficiently conduct ANN search. Unlike existing addition-based quantization methods that suffer from handling the problem caused by the norm of database vector, we map the query vector and database vector using different mapping functions to transform the computation of L-2 distance to inner product similarity, thus do not need to evaluate the norm of database vector. Moreover, we further propose Distributed Asymmetric Mapping Quantization (DAMQ) to enable AMQ to work on very large dataset by distributed learning. Extensive experiments on approximate nearest neighbor search and image retrieval validate the merits of the proposed AMQ and DAMQ.

Influential nodes with rich connections in online social networks (OSNs) are of great values to initiate marketing campaigns. However, the potential influence spread that can be generated by these influential nodes is hidden behind the structures of OSNs, which are often held by OSN providers and unavailable to advertisers for privacy concerns. A social advertising model known as influencer marketing is to have OSN providers offer and price candidate nodes for advertisers to purchase for seeding marketing campaigns. In this setting, a reasonable price profile for the candidate nodes should effectively reflect the expected influence gain they can bring in a marketing campaign. In this paper, we study the problem of pricing the influential nodes based on their expected influence spread to help advertisers select the initiators of marketing campaigns without the knowledge of OSN structures. We design a function characterizing the divergence between the price and the expected influence of the initiator sets. We formulate the problem to minimize the divergence and derive an optimal price profile. An advanced algorithm is developed to estimate the price profile with accuracy guarantees. Experiments with real OSN datasets show that our pricing algorithm can significantly outperform other baselines.

We study an online fault-tolerant bin packing problem that models reliable resource allocation. In this problem, each item is replicated and has f + 1 replicas including one primary and f standbys. The packing of items is required to tolerate up to f faulty bins, i.e., to guarantee that at least one correct replica of each item is available regardless of which f bins turn to be faulty. Any feasible packing algorithm must satisfy an exclusion constraint and a space constraint. The exclusion constraint is generalized from the fault tolerance requirement and the space constraint comes from the capacity planning. The target of bin packing is to minimize the number of bins used. We first derive a lower bound on the number of bins needed by any feasible packing algorithm. We then study three heuristic algorithms named mirroring, shifting and mixing under a particular setting where all items have the same size. The mirroring algorithm has a low utilization of the bin capacity. Compared with the mirroring algorithm, the shifting algorithm requires fewer bins. However, in online packing, the process of opening bins by the shifting algorithm is not smooth. It turns out that even for packing a few items, the shifting algorithm needs to quickly open a large number of bins. The mixing algorithm adopts a dual average strategy to gradually open new bins for incoming items. We prove that the mixing algorithm is feasible and show that it balances the number of bins used and the process of opening bins. Finally, to pack items with different sizes, we extend the mirroring algorithm by adopting the First-Fit strategy and extend both the shifting and mixing algorithms by involving the harmonic strategy. The asymptotic competitive ratios of the three extended algorithms are analyzed respectively.

We study an interval job scheduling problem in distributed systems. We are given a set of interval jobs, with each job specified by a size, an arrival time and a processing length. Once a job arrives, it must be placed on a machine immediately and run for a period of its processing length without interruption. The homogeneous machines to run jobs have the same capacity limits such that at anytime, the total size of the jobs running on any machine cannot exceed its capacity. Launching each machine incurs a fixed cost. After launch, a machine is charged a constant cost per time unit until it is terminated. The problem targets to minimize the total cost incurred by the machines for processing the given set of interval jobs. We focus on the algorithmic aspects of the problem in this article. For the special case where all the jobs have a unit size equal to the machine capacity, we propose an optimal offline algorithm and an optimal 2-competitive online algorithm. For the general case where jobs can have arbitrary sizes, we establish a non-trivial lower bound on the optimal solution. Based on this lower bound, we propose a 5-approximation algorithm in the offline setting. In the non-clairvoyant online setting, we design a O(μ)-competitive Modified First-Fit algorithm which is near optimal (μ is the max/min job processing length ratio). In the clairvoyant online setting, we propose an asymptotically optimal O(√log μ)-competitive algorithm based on our Modified First-Fit strategy.

Cloud gaming has been very popular recently, but providing satisfactory gaming experiences to players at a modest cost is still challenging. Colocating several games onto one server could improve server utilization. To enable efficient colocations while providing Quality of Service (QoS) guarantees, a precise quantification of performance interference among colocated games is required. However, achieving such precise interference prediction is very challenging for games due to the complexity introduced by the contention on many shared resources across CPU and GPU. Moreover, the distinctive properties of cloud gaming require that the prediction model should be constructed beforehand and the prediction should be made instantaneously at request arrivals, which further increases the difficulty. The existing solutions are either not applicable or not effective due to many limitations. In this paper, we present GAugur, a novel methodology that enables highly accurate prediction of the performance interference among games arbitrarily colocated. By leveraging machine learning technologies, GAugur is able to capture the complex relationship between the interference and the contention features of colocated games. We evaluate GAugur through extensive experiments using a large number of real popular games. The results show that GAugur is able to identify whether a colocated game satisfies QoS requirement within an average error of 5%, and is able to quantify the performance degradation of a colocated game within an average error of 7.9%, which significantly outperforms the alternatives. Moreover, GAugur incurs an offline profiling cost linear to the number of games, and negligible overhead for online prediction. We apply GAugur to guiding efficient game colocations for cloud gaming. Experimental results show that GAugur is able to increase the resource utilization by 20% to 60%, and improve the overall performance by up to 15%, compared to the state-of-the-art solutions.

In modern data intensive computing, it is increasingly common for jobs to be executed in a distributed fashion across multiple machine clusters or datacenters to take advantage of data locality. This paper studies fair resource allocation among jobs requiring distributed execution. We extend conventional max-min fairness for resource allocation in a single machine or machine cluster to distributed job execution over multiple sites and define Aggregate Max-min Fairness (AMF) which requires the aggregate resource allocation across all sites to be max-min fair. We show that AMF satisfies the properties of Pareto efficiency, envy-freeness and strategy-proofness, but it does not necessarily satisfy the sharing incentive property. We propose an enhanced version of AMF to guarantee the sharing incentive property. We present algorithms to compute AMF allocations and propose an add-on to optimize the job completion times under AMF. Experimental results show that compared with a baseline which simply requires the resource allocation at each site to be max-min fair, AMF performs significantly better in balancing resource allocation and in job completion time, particularly when the workload distribution of jobs among sites is highly skewed.

As a dual problem of influence maximization, the seed minimization problem asks for the minimum number of seed nodes to influence a required number η of users in a given social network G. Existing algorithms for seed minimization mostly consider the non-adaptive setting, where all seed nodes are selected in one batch without observing how they may influence other users. In this paper, we study seed minimization in the adaptive setting, where the seed nodes are selected in several batches, such that the choice of a batch may exploit information about the actual influence of the previous batches. We propose a novel algorithm, ASTI, which addresses the adaptive seed minimization problem in $O\Big(\fracη \cdot (m+n) \varepsilon^2 łn n \Big)$ expected time and offers an approximation guarantee of $\frac(łn η+1)^2 (1 - (1-1/b)^b) (1-1/e)(1-\varepsilon) $ in expectation, where η is the targeted number of influenced nodes, b is size of each seed node batch, and $\varepsilon \in (0, 1)$ is a user-specified parameter. To the best of our knowledge, ASTI is the first algorithm that provides such an approximation guarantee without incurring prohibitive computation overhead. With extensive experiments on a variety of datasets, we demonstrate the effectiveness and efficiency of ASTI over competing methods.

Workflow is a common model to represent large computations composed of dependent tasks. Most existing workflow scheduling algorithms use computing resources in a non-multiprogrammed way, by which only one task can run on a service (machine) at a time. In this paper, we study a new workflow scheduling model on heterogeneous Infrastructure-as-a-Service (IaaS) platforms, which allows multiple tasks to run concurrently on a virtual machine (VM) according to their multi-resource demand s. First, we propose a list-scheduling framework for the new multiprogrammed cloud resource model. In the order of a priority list, this framework gradually appoints tasks the best placements found on both existing and new VMs on the platform. Different task prioritization and placement comparison methods can be employed for different scheduling objectives. To fully exploit the heterogeneity of IaaS platforms, the VMs can be scaled up during the scheduling process. Then, we propose a deadline-constrained workflow scheduling algorithm (called DyDL) based on this framework to optimize the cost of workflow execution . This algorithm prioritizes tasks by their latest start times and appoints tasks the placements which can meet their latest start times and incur the minimal cost increases . Experimental results show that DyDL can achieve significantly better schedules in most test cases compared to several existing deadline-constrained workflow scheduling algorithms .

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.

We consider a scheduling problem for running jobs on machines rented from the cloud. Cloud service providers such as Amazon EC2 and Google Cloud offer machines to rent on demand, and charge the rental usage by a specific interval of time, say at an hourly rate. This pricing model creates an interesting optimization problem called Interval Scheduling with Discrete Charging Units (ISDCU) which assigns jobs to run on the machines with the objective of minimizing the rental cost. In this paper, we study the problem of ISDCU where each machine can process a maximum of g jobs simultaneously. We focus on interval jobs where each job must be assigned to a machine upon its arrival and run for a required processing length. We show that ISDCU is NP-hard even for the case of g = 1. We also show that no deterministic online algorithm can achieve a competitive ratio better than max{2, g} in the non-clairvoyant setting, and better than max{3/2, g} in the clairvoyant setting. Lastly, we develop and analyze several online algorithms, most of which achieve a competitive ratio of O(g).

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 that the index shard replication strategy could have a significant impact on the resource utilization of machines. In this paper, we investigate the index shard replication problem with the goal of improving the resource utilization of machines in search engine datacenters. We formulate the problem as a variant of the Multi-Dimensional Vector Bin Packing Problem and propose several strategies to approximate the optimal solution. The proposed strategies are evaluated by extensive experiments using data from real commercial search engines. The results demonstrate the effectiveness of the proposed strategies. Our work also yields many insights about the impact of different input properties on the performance and the key factors that each strategy is sensitive to. We believe that this paper will provide valuable guidance to the choice of the index shard replication strategy in practice.

Online Social Networks (OSNs) attract billions of users to share information and communicate where viral marketing has emerged as a new way to promote the sales of products. An OSN provider is often hired by an advertiser to conduct viral marketing campaigns. The OSN provider generates revenue from the commission paid by the advertiser which is determined by the spread of its product information. Meanwhile, to propagate influence, the activities performed by users such as viewing video ads normally induce diffusion cost to the OSN provider. In this paper, we aim to find a seed set to optimize a new profit metric that combines the benefit of influence spread with the cost of influence propagation for the OSN provider. Under many diffusion models, our profit metric is the difference between two submodular functions which is challenging to optimize as it is neither submodular nor monotone. We design a general two-phase framework to select seeds for profit maximization and develop several bounds to measure the quality of the seed set constructed. Experimental results with real OSN datasets show that our approach can achieve high approximation guarantees and significantly outperform the baseline algorithms, including state-of-the-art influence maximization algorithms.

Influence maximization is a classic and extensively studied problem with important applications in viral marketing. Existing algorithms for influence maximization, however, mostly focus on offline processing, in the sense that they do not provide any output to the user until the final answer is derived, and that the user is not allowed to terminate the algorithm early to trade the quality of solution for efficiency. Such lack of interactiveness and flexibility leads to poor user experience, especially when the algorithm incurs long running time.

Summary We introduce the papers submitted to the special issue of Computation, Concurrency: Practice and Experience on parallel and distributed algorithms.

Summary The continually increasing energy consumption represents a critical issue in modern heterogeneous computing systems. With the aid of dynamic voltage frequency scaling (DVFS), task scheduling is considered an effective software‐based technique for reducing the total energy consumption and minimizing the overall schedule length (makespan). A natural solution is to reclaim the slack time in a given time‐efficient schedule, which is also referred to as a “two‐pass” method or a “rescheduling” method. A number of studies have focused on slack reclamation to achieve energy reductions through heuristics; although, these methods offer suboptimal solutions. In this article, the rescheduling optimization problem is formulated as a linear program for minimizing an energy objective function subject to precedence and deadline constraints implied in the given schedule. Two types of decision variables, ie, frequency duty factors and task intervals, are defined to set up the linear model. Consequently, an optimal solution to the problem can be provided in a straightforward manner by a linear programming solver, which suggests that such a rescheduling problem belongs to the P (polynomial time) class. The experimental results show the effectiveness of the proposed approach and demonstrate that the performance is superior to that of other competitive algorithms in terms of both energy saving and runtime efficiency.

Given a social network G , the influence maximization (IM) problem seeks a set S of k seed nodes in G to maximize the expected number of nodes activated via an influence cascade starting from S. Although a lot of algorithms have been proposed for IM, most of them only work under the non-adaptive setting, i.e., when all k seed nodes are selected before we observe how they influence other users. In this paper, we study the adaptive IM problem, where we select the k seed nodes in batches of equal size b , such that the choice of the i -th batch can be made after the influence results of the first i - 1 batches are observed. We propose the first practical algorithms for adaptive IM with an approximation guarantee of 1 − exp(ξ − 1) for b = 1 and 1 − exp(ξ − 1 + 1/ e ) for b > 1, where ξ is any number in (0, 1). Our approach is based on a novel AdaptGreedy framework instantiated by non-adaptive IM algorithms, and its performance can be substantially improved if the non-adaptive IM algorithm has a small expected approximation error. However, no current non-adaptive IM algorithms provide such a desired property. Therefore, we further propose a non-adaptive IM algorithm called EPIC, which not only has the same worst-case performance bounds with that of the state-of-the-art non-adaptive IM algorithms, but also has a reduced expected approximation error. We also provide a theoretical analysis to quantify the performance gain brought by instantiating AdaptGreedy using EPIC, compared with a naive approach using the existing IM algorithms. Finally, we use real social networks to evaluate the performance of our approach through extensive experiments, and the experimental experiments strongly corroborate the superiorities of our approach.

Information can be disseminated widely and rapidly through Online Social Networks (OSNs) with “word-of-mouth” effects. Viral marketing is such a typical application in which new products or commercial activities are advertised by some seed users in OSNs to other users in a cascading manner. The selection of initial seed users yields a tradeoff between the expense and reward of viral marketing. In this paper, we define a general profit metric that naturally combines the benefit of influence spread with the cost of seed selection in viral marketing. We carry out a comprehensive study on finding a set of seed nodes to maximize the profit of viral marketing. We show that the profit metric is significantly different from the influence metric in that it is no longer monotone. This characteristic differentiates the profit maximization problem from the traditional influence maximization problem. We develop new seed selection algorithms for profit maximization with strong approximation guarantees. We also derive several upper bounds to benchmark the practical performance of an algorithm on any specific problem instance. Experimental evaluations with real OSN datasets demonstrate the effectiveness of our algorithms and techniques.

Advances in cloud computing and GPU virtualization are allowing the game industry to move into a cloud gaming era. In this paper, we consider multiplayer cloud gaming (MCG), which is the natural integration of multiplayer online gaming and cloud gaming paradigms. With MCG, a game server and a set of rendering servers for the players need to be located and launched in the clouds for each game session. We formulate an MCG server allocation problem with the objective of minimizing the total server rental and bandwidth cost charged by the cloud to support an MCG session. The MCG server allocation problem is hard to solve optimally. We propose several efficient heuristics to address the problem and carry out theoretical analysis for the proposed hill-climbing algorithm. We conduct extensive experiments using real Internet latency and cloud pricing datasets to evaluate the effectiveness of our proposed algorithms as well as several alternatives. Experimental results show that our best algorithm can achieve near-optimal cost under real-time latency constraints.

Social media users are generating data on an unprecedented scale. Distributed storage systems are often used to cope with explosive data growth. Data partitioning and replication are two interrelated data placement issues affecting the interserver traffic caused by user-initiated read and write operations in distributed storage systems. This paper investigates how to minimize the interserver traffic among a cluster of social media servers through joint data partitioning and replication optimization. We formally define the problem and study its hardness. We then propose a traffic-optimized partitioning and replication (TOPR) method to continuously adapt data placement according to various dynamics. Evaluations with real Twitter and LiveJournal social graphs show that TOPR not only reduces the interserver traffic significantly but also saves much storage cost of replication compared to state-of-the-art methods. We also benchmark TOPR against the offline optimum by a binary linear program.

Cloud gaming has gained significant popularity recently due to many important benefits such as removal of device constraints, instant-on, and cross-platform. The properties of intensive resource demands and dynamic workloads make cloud gaming appropriate to be supported by an elastic cloud platform. Facing a large user population, a fundamental problem is how to provide satisfactory cloud gaming service at modest cost. We observe that the software storage cost could be substantial compared to the server running cost in cloud gaming using elastic cloud resources. Therefore, in this article, we address the server provisioning problem for cloud gaming to optimize both the server running cost and the software storage cost. We find that the distribution of game software among servers and the selection of server types both trigger tradeoffs between the software storage cost and the server running cost in cloud gaming. We formulate the problem with a stochastic model and employ queueing theory to conduct a solid theoretical analysis of the system behaviors under different request dispatching policies. We then propose several classes of algorithms to approximate the optimal solution. The proposed algorithms are evaluated by extensive experiments using real-world parameters. The results show that the proposed Ordered and Genetic algorithms are computationally efficient, nearly cost-optimal, and highly robust to dynamic changes.

Influence Maximization is an extensively-studied problem that targets at selecting a set of initial seed nodes in the Online Social Networks (OSNs) to spread the influence as widely as possible. However, it remains an open challenge to design fast and accurate algorithms to find solutions in large-scale OSNs. Prior Monte-Carlo-simulation-based methods are slow and not scalable, while other heuristic algorithms do not have any theoretical guarantee and they have been shown to produce poor solutions for quite some cases. In this paper, we propose hop-based algorithms that can easily scale to millions of nodes and billions of edges. Unlike previous heuristics, our proposed hop-based approaches can provide certain theoretical guarantees. Experimental evaluations with real OSN datasets demonstrate the efficiency and effectiveness of our algorithms.

Regular diurnal patterns are often seen in the workloads of cloud-based online applications. This kind of non-stationary workloads changes the processing demands over time. To run application services with minimum costs, the number of cloud instances can be dynamically adjusted according to the workload variations. Recently, a new type of scheduled instances has emerged in the Infrastructure-as-a-Service market to facilitate such configurations. Scheduled instances can be reserved based on a recurring schedule and they offer price discounts. Meanwhile, cloud vendors require minimum scheduled durations to avoid the overhead of frequently launching and terminating cloud instances. Coupled with traditional on-demand and reserved instances, it becomes more complicated for users to find the optimal combination of these three pricing options to minimize their monetary costs. For the new scheduled instances, not only the number of instances but also their start and stop times have to be decided. In this paper, we develop a fast and effective strategy to solve this problem. Based on the hourly workload distributions, we first compute the optimal number of instances to acquire for each pricing option. Then, we design a scheduling algorithm to arrange the scheduled instances in compliance with the restriction of their scheduled durations. Using the workloads of the LOL online game and the Wikipedia Mobile service as two case studies, the efficacy of our strategy is demonstrated.

Cloud gaming has gained significant popularity recently due to many important benefits such as removal of device constraints, instant-on and cross-platform, etc. The properties of intensive resource demands and dynamic workloads make cloud gaming appropriate to be supported by an elastic cloud platform. Facing a large user population, a fundamental problem is how to provide satisfactory cloud gaming service at modest cost. We observe that software maintenance cost could be substantial compared to server running cost in cloud gaming. In this paper, we address the server provisioning problem for cloud gaming to optimize both server running cost and software maintenance cost. We find that the distribution of game softwares among servers triggers a trade-off between the software maintenance cost and server running cost. We formulate the problem with a stochastic model and employ queueing theories to conduct solid theoretical analysis. We then propose several classes of algorithms to approximate the optimal solution. The proposed algorithms are evaluated by extensive experiments using real-world parameters. The results show that the proposed algorithms are computationally efficient, nearly cost-optimal and highly robust to dynamic changes.

We consider an online fault-tolerant bin packing problem that models the reliable resource allocation in cloud-based systems. In this problem, any feasible packing algorithm must satisfy an exclusion constraint and a space constraint. The exclusion constraint is generalized from the fault-tolerance requirement and the space constraint comes from the capacity planning. The target of bin packing is to minimize the number of bins used. We first derive a lower bound on the number of bins needed by any feasible packing algorithm. Then we study two heuristic algorithms mirroring and shifting. The mirroring algorithm has a low utilization of the bin capacity. Compared with the mirroring algorithm, the shifting algorithm requires fewer numbers of bins. However, in online packing, the process of opening bins by the shifting algorithm is not smooth. It turns out that even for packing a few items, the shifting algorithm needs to quickly open a large number of bins. We therefore propose a new heuristic algorithm named mixing which can gradually open new bins for incoming items. We prove that the mixing algorithm is feasible and show that it balances the number of bins used and the process of opening bins.

In this paper, we study an online Flexible Job Scheduling (FJS) problem. The input of the problem is a set of jobs, each having an arrival time, a starting deadline and a processing length. Each job has to be started by the scheduler between its arrival and its starting deadline. Once started, the job runs for a period of the processing length without interruption. The target is to minimize the span of all the jobs --- the time duration in which at least one job is running. We study online FJS under both the non-clairvoyant and clairvoyant settings. In the non-clairvoyant setting, the processing length of each job is not known for scheduling purposes. We first establish a lower bound of μ on the competitive ratio of any deterministic online scheduler, where μ is the max/min job processing length ratio. Then, we propose two O(μ)-competitive schedulers: Batch and Batch+. The Batch+ scheduler is proved to have a tight competitive ratio of (μ+1). In the clairvoyant setting, the processing length of each job is known at its arrival and can be used for scheduling purposes. We establish a lower bound of (√5+1)/2 on the competitive ratio of any deterministic online scheduler, and propose two O(1)-competitive schedulers: Classify-by-Duration Batch+ and Profit. The Profit scheduler can achieve a competitive ratio of 4+2√2. Our work lays the foundation for extending several online job scheduling problems in cloud and energy-efficient computing to jobs that have laxity in starting.

Cloud-based systems often face the problem of dispatching a stream of jobs to run on cloud servers in an online manner. Each job has a size that defines the resource demand for running the job. Each job is assigned to run on a cloud server upon its arrival and the job departs after it completes. The departure time of a job, however, is not known at the time of its arrival. Each cloud server has a fixed resource capacity and the total resource demand of all the jobs running on a server cannot exceed its capacity at all times. The objective of job dispatching is to minimize the total cost of the servers used, where the cost of renting each cloud server is proportional to its running hours by “pay-as-you-go” billing. The above job dispatching problem can be modeled as a variant of the dynamic bin packing (DBP) problem known as MinUsageTime DBP. In this paper, we study the competitiveness bounds of MinUsageTime DBP. We establish an improved lower bound on the competitive ratio of Any Fit family of packing algorithms, and a new upper bound of μ + 3 on the competitive ratio of the commonly used First Fit packing algorithm, where μ is the max/min job duration ratio. Our result significantly reduces the gap between the upper and lower bounds for the MinUsageTime DBP problem to a constant value independent of μ, and shows that First Fit packing is near optimal for MinUsageTime DBP.

Distributed interactive computing allows participants at different locations to interact with each other in real time. In this paper, we study the interaction times of continuous Distributed Interactive Applications (DIAs) in which the application states change due to not only user-initiated operations but also time passing. Given the clients and servers of a continuous DIA, its interaction time is directly affected by how the clients are assigned to the servers as well as the simulation time settings of the servers. We formulate the Minimum Interaction Time (MIT) problem as a combinatorial problem of these two tuning knobs and prove that it is NP-hard. We then approximate the problem by fixing the client assignment or the simulation time offsets among the servers. When the client assignment is fixed, we show that finding the minimum achievable interaction time can be reduced to a weighted bipartite matching problem. We further show that this approach establishes a tight approximation factor of 3 to the MIT problem if each client is assigned to its nearest server. When the simulation time offsets among the servers are fixed, we show that finding the minimum achievable interaction time is still NP-hard. This approach can approximate the MIT problem by a factor within 2 if the simulation times of all servers are synchronized. A mix of the above two approaches better approximates the MIT problem within a factor of 5/3. We further conduct experimental evaluation of these approaches with three real Internet latency datasets.

Information can be disseminated widely and rapidly through Online Social Networks (OSNs) with “word-of-mouth” effects. Viral marketing is such a typical application in which new products or commercial activities are advertised by some seed users in OSNs to other users in a cascading manner. The budget allocation for seed selection reflects a tradeoff between the expense and reward of viral marketing. In this paper, we define a general profit metric that naturally combines the benefit of influence spread with the cost of seed selection in viral marketing to eliminate the need for presetting the budget for seed selection. We carry out a comprehensive study on finding a set of seed nodes to maximize the profit of viral marketing. We show that the profit metric is significantly different from the influence metric in that it is no longer monotone. As a result, from the computability perspective, the problem of profit maximization is much more challenging than that of influence maximization. We develop new seed selection algorithms for profit maximization with strong approximation guarantees. Experimental evaluations with real OSN datasets demonstrate the effectiveness of our algorithms.

Cloud-based systems often face the problem of dispatching a stream of jobs to run on cloud servers in an online manner. Each job has a size that defines the resource demand for running the job. Each job is assigned to run on a cloud server upon its arrival and the job departs after it completes. The departure time of a job, however, is not known at the time of its arrival. Each cloud server has a fixed resource capacity and the total resource demand of all the jobs running on a server cannot exceed its capacity at all times. The objective of job dispatching is to minimize the total cost of the servers used, where the cost of renting each cloud server is proportional to its running hours by "pay-as-you-go" billing. The above job dispatching problem can be modeled as a variant of the Dynamic Bin Packing (DBP) problem known as MinUsageTime DBP. In this paper, we develop new approaches to the competitive analysis of the commonly used First Fit packing algorithm for the MinUsageTime DBP problem, and establish a new upper bound of μ+4 on the competitive ratio of First Fit packing, where μ is the ratio of the maximum job duration to the minimum job duration. Our result significantly reduces the gap between the upper and lower bounds for the MinUsageTime DBP problem to a constant value independent of μ, and shows that First Fit packing is near optimal for MinUsageTime DBP.

Advances in cloud computing and GPU virtualization are allowing the game industry to move into a cloud gaming era. While shifting standalone video games to the cloud gaming mode is straightforward, adapting multiplayer online games to the cloud gaming paradigm faces unique challenges. In this paper, we consider multiplayer cloud gaming (MCG), which is the natural integration of multiplayer online gaming and cloud gaming paradigms. We formulate an MCG server allocation problem with the objective of minimizing the total server rental and bandwidth cost charged by the cloud to support an MCG session. We propose several efficient heuristics to address the MCG server allocation problem which is hard to solve optimally. We conduct extensive experiments using real Internet latency and cloud pricing data to evaluate the effectiveness of our proposed algorithms as well as several alternatives. Experimental results show that our best algorithm can achieve near-optimal cost under real-time latency constraints.

Hardware evolution has been one of the driving factors for the redesign of database systems. Recently, approximate storage emerges in the area of computer architecture. It trades off precision for better performance and/or energy consumption. Previous studies have demonstrated the benefits of approximate storage for applications that are tolerant to imprecision such as image processing. However, it is still an open question whether and how approximate storage can be used for applications that do not expose such intrinsic tolerance. In this paper, we study one of the most basic operations in database--sorting on a hybrid storage system with both precise storage and approximate storage. Particularly, we start with a study of three common sorting algorithms on approximate storage. Experimental results show that a 95% sorted sequence can be obtained with up to 40% reduction in total write latencies. Thus, we propose an approx-refine execution mechanism to improve the performance of sorting algorithms on the hybrid storage system to produce precise results. Our optimization gains the performance benefits by offloading the sorting operation to approximate storage, followed by an efficient refinement to resolve the unsortedness on the output of the approximate storage. Our experiments show that our approx-refine can reduce the total memory access time by up to 11%. These studies shed light on the potential of approximate hardware for improving the performance of applications that require precise results.

The MinUsageTime Dynamic Bin Packing (DBP) problem targets at minimizing the accumulated usage time of all the bins in the packing process. It models the server acquisition and job scheduling issues in many cloud-based systems. Earlier work has studied MinUsageTime DBP in the non-clairvoyant setting where the departure time of each item is not known at the time of its arrival. In this paper, we investigate MinUsageTime DBP in the clairvoyant setting where the departure time of each item is known for packing purposes. We study both the offline and online versions of Clairvoyant MinUsageTime DBP. We present two approximation algorithms for the offline problem, including a 5-approximation Duration Descending First Fit algorithm and a 4-approximation Dual Coloring algorithm. For the online problem, we establish a lower bound of 1+√5/2 on the competitive ratio of any online packing algorithm. We propose two strategies of item classification for online packing, including a classify-by-departure-time strategy and a classify-by-duration strategy. We analyze the competitiveness of these strategies when they are applied to the classical First Fit packing algorithm. It is shown that both strategies can substantially reduce the competitive ratio for Clairvoyant MinUsageTime DBP compared to the original First Fit algorithm.

Modern DRAM architectures allow a number of low-power states on individual memory ranks for advanced power management. Many previous studies have taken advantage of demotions on low-power states for energy saving. However, most of the demotion schemes are statically performed on a limited number of pre-selected low-power states, and are suboptimal for different workloads and memory architectures. Even worse, the idle periods are often too short for effective power state transitions, especially for memory intensive applications. Wrong decisions on power state transition incur significant energy and delay penalties. In this paper, we propose a novel memory system design named RAMZzz with rank-aware energy saving optimizations including dynamic page migrations and adaptive demotions. Specifically, we group the pages with similar access locality into the same rank with dynamic page migrations. Ranks have their hotness: hot ranks are kept busy for high utilization and cold ranks can have more lengthy idle periods for power state transitions. We further develop adaptive state demotions by considering all low-power states for each rank and a prediction model to estimate the power-down timeout among states. We experimentally compare our algorithm with other energy saving policies with cycle-accurate simulation. Experiments with benchmark workloads show that RAMZzz achieves significant improvement on energy-delay2 and energy consumption over other energy saving techniques.

Dynamic Bin Packing (DBP) is a variant of classical bin packing, which assumes that items may arrive and depart at arbitrary times. Existing works on DBP generally aim to minimize the maximum number of bins ever used in the packing. In this paper, we consider a new version of the DBP problem, namely, the MinTotal DBP problem which targets at minimizing the total cost of the bins used overtime. It is motivated by the request dispatching problem arising from cloud gaming systems. We analyze the competitive ratios of the modified versions of the commonly used First Fit, Best Fit, and Any Fit packing (the family of packing algorithms that open a new bin only when no currently open bin can accommodate the item to be packed) algorithms for the MinTotal DBP problem. We show that the competitive ratio of Any Fit packing cannot be better than μ + 1, where μ is the ratio of the maximum item duration to the minimum item duration. The competitive ratio of Best Fit packing is not bounded for any given μ. For First Fit packing, if all the item sizes are smaller than 1/β of the bin capacity (β> 1 is a constant), the competitive ratio has an upper bound of β/β-1·μ+3β/β-1+ 1. For the general case, the competitive ratio of First Fit packing has an upper bound of 2μ + 7. We also propose a Hybrid First Fit packing algorithm that can achieve a competitive ratio no larger than 5/4 μ + 19/4 when μ is not known and can achieve a competitive ratio no larger than μ + 5 when μ is known.

In this paper, we study the server provisioning problem for continuous Distributed Interactive Applications (DIAs) whose application states not only change because of the operations performed by participants, but also evolve along with the passing of time. We focus on finding the locations of servers for hosting continuous DIAs, with the goals of optimizing the interactivity performance while fulfilling the consistency and fairness requirements. We show that the server provisioning problem is challenging by presenting its NP-hardness and non-approximability results under several conditions. We propose two efficient server placement algorithms and analyze their approximation ratios. The approximation ratio of the proposed M-BETTER algorithm is quite close to a lower bound for any polynomial-time algorithm. We also conduct experimental evaluations to compare the proposed algorithms with several baseline server placements.

Distributed storage systems are the key infrastructures for hosting the user data of large-scale Online Social Networks (OSNs). The amount of inter-server communication is an important scalability indicator for these systems. Data partitioning and replication are two inter-related issues affecting the inter-server traffic caused by user-initiated read and write operations. This paper investigates the problem of minimizing the total inter-server traffic among a cluster of OSN servers through joint partitioning and replication optimization. We propose a Traffic-Optimized Partitioning and Replication (TOPR) method based on an analysis of how replica allocation affects the inter-server communication. Lightweight algorithms are developed to adjust partitioning and replication dynamically according to data read and write rates. Evaluations with real Facebook and Twitter social graphs show that TOPR significantly reduces the inter-server communication compared with state-of-the-art methods.

In this demonstration, we propose MASTER, a set of toolkits for cross-platform application streaming that is able to utilize elastic resources on public clouds. MASTER has many useful features. It provides full control of resource acquisition and request dispatching, requires only a browser on the client side for user interactions, and incorporates an input transformer to assist touchscreen device users to naturally interact with desktop applications that need keystroke and mouse control. MASTER also supports session concurrency (serving multiple streaming sessions on a single cloud server instance), thereby improving resource utilization and cutting the cloud bill.

Main memory (or DRAM) is one of the most significant components to the computer system's performance and energy consumption. Dynamic frequency scaling (DFS) and DRAM low-power states (Demotion) are two main-stream techniques for DRAM power management. DFS reduces the operation frequency of memory channels and DRAM devices when the memory bandwidth is under-utilized, whereas demotion transits individual memory ranks to low-power states during long idle periods. Despite that there have been fruitful research work for DFS and demotion separately, little attention has been paid to the synergy between these two techniques. To bridge this gap, this paper conducts a comprehensive study on the synergy between DFS and demotion. In particular, we leverage queuing theory to develop analytical models for the energy consumption and performance of DRAM systems with DFS and demotion. These models provide valuable insights into the synergy between DFS and demotion. We further attempt to minimize the energy consumption by considering both DFS and demotion while keeping a pre-defined performance penalty budget. To reduce the optimization complexity, we develop simple yet effective heuristics to search near-optimum DFS-demotion configurations. We experimentally compare our design with other state-of-the-art DRAM energy saving policies using detailed simulations of a large set of workloads. Experimental results show the accuracy of our analytical models and the effectiveness of our optimizations.

Increasing geographical spreads of modern distributed interactive applications (DIAs) make distributed server deployment vital for combating network latency and improving the interactivity among participants. In this paper, we investigate the server provisioning problem that concerns where to place servers for DIAs. We formulate the server provisioning problem with an objective of reducing the network latency involved in the interaction between participants. We prove that the problem is NP-hard under several scenarios. We analyze the performance of the classical k-median server placement for DIAs and propose a new greedy server provisioning heuristic for DIAs. Theoretical analysis shows that the approximation ratio of the proposed greedy algorithm is much lower than that of the k-median placement. Experiments using real Internet latency data also show that our proposed algorithm significantly outperforms the k-median and other baseline server placements.

Cloud gaming is becoming increasingly popular. The basic idea of cloud gaming is to run games on cloud servers and let players interact with games through thin clients. As the player population grows, the cloud gaming service provider needs to maintain a large number of cloud servers for running the game instances requested by the players. A primary concern of the cloud gaming service provider is the total running cost of the cloud servers. In this paper, we study the problem of how to dispatch the play requests to the cloud servers in a cloud gaming system. We show that the dispatching strategy of play requests may heavily affect the total service cost of the cloud gaming system. The play request dispatching problem can be considered as a variant of the dynamic bin packing problem. However, we show that the classical bin packing algorithms such as First Fit (FF) and Best Fit (BF) are not efficient in terms of resource usage in cloud gaming due to the diurnal workload pattern of online games. To address this issue, we propose an efficient request dispatching algorithm that assigns play requests according to the predicted ending times of game sessions. We also assess several classes of prediction algorithms and select a neural-network-based algorithm to predict the ending times of game sessions. We conduct extensive evaluations of the proposed algorithms using real traces from different types of online games. The experimental results show that the proposed dispatching algorithm with neural-network-based prediction can reduce the resource waste of the cloud servers and thus decrease the total service cost compared to the FF and BF algorithms. The reduction in the resource waste is particularly significant for match-based games such as Defense of the Ancient and World of Tank.

Infrastructure-as-a-Service (IaaS) cloud providers offer many elasticities and flexibilities for users to run their systems in the cloud. The monetary cost issues of running those systems in the cloud are hardly ignored and there is less work discussing improving the monetary efficiency of running large scale systems in dynamic cloud environments. In this paper, we focus on improving the monetary efficiency of running Hadoop systems in the dynamic public cloud. In particular, we carry out detailed study on improving the monetary efficiency by leveraging spot instances. From a cloud broker's perspective, we propose a price-aware virtual machine auto-scaling with migration algorithm to improve the monetary efficiency of running Hadoop in the cloud using spot instances. We evaluate our proposed algorithm through simulation using Amazon EC2 spot price traces and real world workload traces. Compared with other baseline algorithms, our approach can improve the monetary efficiency by up to 9.3x.

Dynamic Bin Packing (DBP) is a variant of classical bin packing, which assumes that items may arrive and depart at arbitrary times. Existing works on DBP generally aim to minimize the maximum number of bins ever used in the packing. In this paper, we consider a new version of the DBP problem, namely, the MinTotal DBP problem which targets at minimizing the total cost of the bins used over time. It is motivated by the request dispatching problem arising in cloud gaming systems. We analyze the competitive ratios of the commonly used First Fit, Best Fit, and Any Fit packing (the family of packing algorithms that open a new bin only when no currently opened bin can accommodate the item to be packed) algorithms for the MinTotal DBP problem. We show that the competitive ratio of Any Fit packing cannot be better than the max/min item interval length ratio μ. The competitive ratio of Best Fit packing is not bounded for any given μ. For First Fit packing, if all the item sizes are smaller than W⁄k (W is the bin capacity and k≥1 is a constant), it has a competitive ratio of k⁄k-1μ + 6k⁄k-1 + 1. For the general case, First Fit packing has a competitive ratio of 2μ + 13. We also propose a Modified First Fit packing algorithm that can achieve a competitive ratio of 8⁄7μ + 55⁄7 when μ is not known and can achieve a competitive ratio of μ + 8 when μ is known.

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.

Increasing geographical spreads of modern distributed interactive applications (DIAs) make distributed server deployment vital for combating network latency and improving the interactivity among participants. In this paper, we investigate the server provisioning problem that concerns where to place servers in DIAs. We formulate the server provisioning problem with an objective of reducing the network latency involved in the interaction between participants. We prove that the problem is NP-hard under any one of the following three scenarios that may be common in practice: (a) the network latency does not satisfy the triangle inequality; or (b) the choices of server locations in the network are restricted; or (c) the number of server locations to select is limited. Then, we propose an efficient greedy server provisioning heuristic, analyze its approximation ratio and give a tight example. Experiments using real Internet latency data show that our proposed algorithm significantly outperforms traditional k-median and k-center server placements.

By sharing resources among peers in peer-to-peer network, application layer multicast (ALM) has been shown an efficient way to improve the scalability and reduce the latency of communication. To deploy ALM in peer-to-peer distributed interactive applications (DIAs), the property of many-to-many communication of DIA demands multiple multicast trees to be constructed in the overlay. Therefore, how to efficiently allocate resources among multiple trees to maximize the benefit is an important and challenging issue. In this paper, we study the problem of building ALM trees with minimum total end-to-end delay to receivers in peer-to-peer DIAs with resource constraints on network bandwidth. The end-to-end delay from a sender to receivers in a multicast tree consists of the link delay as well as the packet queuing delay at intermediate peers, while the latter is often ignored or not well studied in the previous work. In this paper, we explicitly establish the relationship between the queuing delay at peers and the topology of multicast trees in peer-to-peer DIAs. Based on the relationship, the above mentioned problem is defined and we prove that it is NP-complete. We present a centralized heuristic algorithm to obtain an approximate solution. Moreover, distributed algorithms are also investigated to refine the topology in practical systems with dynamic changes. Extensive experiments were conducted by simulations to evaluate the proposed algorithms and results are reported in the paper.

An Interest Management (IM) mechanism eliminates irrelevant status updates transmitted in Distributed Virtual Environments (DVE). This paper proposes a new hierarchical IM mechanism for DVEs. The hierarchical mechanism divides the virtual world into multiple levels of cells and keeps the relationship between an entity and an Area-Of-Interest (AOI) at a particular cell level according to their relative position. As their relative position changes, the relationship level is updated accordingly. Compared with the traditional area-based and cell-based mechanisms, the proposed hierarchical mechanism significantly reduces the communication bandwidth consumption of IM and thus considerably improves the scalability of DVEs. In addition, the proposed mechanism also has much lower computation cost than the traditional mechanisms and very acceptable storage requirement for its data structures.

In this paper, we study the interaction times of continuous distributed interactive computing in which the application states change due to not only user-initiated operations but also time passing. We formulate the Minimum Interaction Time problem as a combinatorial problem of how the clients are assigned to the servers and the simulation time settings of the servers. We also outline two approaches to approximate the problem.

The network traffic pattern of continuous sensor data collection often changes constantly over time due to the exploitation of temporal and spatial data correlations as well as the nature of condition-based monitoring applications. In contrast to most existing TDMA schedules designed for a static network traffic pattern, this paper proposes a novel TDMA schedule that is capable of efficiently collecting sensor data for any network traffic pattern and is thus well suited to continuous data collection with dynamic traffic patterns. In the proposed schedule, the energy consumed by sensor nodes for any traffic pattern is very close to the minimum required by their workloads given in the traffic pattern. The schedule also allows the base station to conclude data collection as early as possible according to the traffic load, thereby reducing the latency of data collection. We present a distributed algorithm for constructing the proposed schedule. We develop a mathematical model to analyze the performance of the proposed schedule. We also conduct simulation experiments to evaluate the performance of different schedules using real-world data traces. Both the analytical and simulation results show that, compared with existing schedules that are targeted on a fixed traffic pattern, our proposed schedule significantly improves the energy efficiency and time efficiency of sensor data collection with dynamic traffic patterns.

Renewable (or green) energy, such as solar or wind, has at least partially powered data centers to reduce the environmental impact of traditional energy sources (brown energy with high carbon footprint). In this paper, we propose a holistic workload scheduling algorithm to minimize the brown energy consumption across multiple geographically distributed data centers with renewable energy sources. While green energy supply for a single data center is intermittent due to daily/seasonal effects, our workload scheduling algorithm is aware of different amounts of green energy supply and dynamically schedules the workload across data centers. The scheduling decision adapts to workload and data center cooling dynamics. Our experiments with real workload traces demonstrate that our scheduling algorithm greatly reduces brown energy consumption by up to 40% in comparison with other scheduling policies.

Recently, application service providers have been employing Infrastructure-as-a-Service (IaaS) clouds such as Amazon EC2 to scale their computing resources on-demand to adapt to dynamic workloads. Existing research has been focusing more on cloud resource scaling in batch processing, non latency-sensitive applications. In this paper, we consider the problem of revenue-cost optimization in cloud-based application service providers with stringent QoS requirements, e.g., online gaming services. We propose an integrated approach which combines resource provisioning algorithms and request scheduling disciplines. The main goal is to maximize the service provider's revenue via satisfying pre-defined QoS requirements, and at the same time, to minimize cloud resource cost. We have implemented the proposed resource provisioning algorithms and scheduling disciplines into a cloud scaling framework developed in our previous work. Extensive experiments have been conducted with a fully functional implementation and realistic workloads modeled after real traces of popular online game servers. The results demonstrated the effectiveness of our proposed approach.

Recent years have witnessed the enormous popularity of distributed interactive applications (DIAs), which allow participants that are distributed in the network to interact with each other concurrently. The rapid growth of DIAs has raised stringent requirements on providing realistic sense of interaction between participants, whose quality is heavily influenced by network latencies. Although network latencies cannot be eliminated due to geographical spreads of participants, it is possible to reduce them by a smart selection of the locations where the servers of the DIAs are placed. The locations of servers affect not only the inter-server latencies but also the latencies from participants to servers, both of which are involved in the interactions among participants. Thus, the placement of servers is an important factor to the interactivity performance of DIAs. We formulate the server placement problem, and propose to solve it by an enhanced genetic algorithm, whose genetic operators are specially designed based on the nature of the problem. Experimental results using various datasets show that our algorithm leads to appreciable improvement of the interaction quality in DIAs.

Main memory is a significant energy consumer which may contribute to over 40% of the total system power, and will become more significant for server machines with more main memory. In this paper, we propose a novel memory system design named RAMZzz with rank-aware energy saving optimizations. Specifically, we rely on a memory controller to monitor the memory access locality, and group the pages with similar access locality into the same rank. We further develop dynamic page migrations to adapt to data access patterns, and a prediction model to estimate the demotion time for accurate control on power state transitions. We experimentally compare our algorithm with other energy saving policies with cycle-accurate simulation. Experiments with benchmark workloads show that RAMZzz achieves significant improvement on energy-delay2 and energy consumption over other power saving techniques.

Distributed interactive applications (DIAs) are networked systems that allow multiple participants at different locations to interact with each other. Wide spreads of client locations in large-scale DIAs often require geographical distribution of servers to meet the latency requirements of the applications. In the distributed server architecture, the network latencies involved in the interactions between clients are directly affected by how the clients are assigned to the servers. In this paper, we focus on the problem of assigning clients to appropriate servers in DIAs to enhance their interactivity. We formulate the problem as a combinational optimization problem and prove that it is NP-complete. Then, we propose several heuristic algorithms for fast computation of good client assignments and theoretically analyze their approximation ratios. The proposed algorithms are also experimentally evaluated with real Internet latency data. The results show that the proposed algorithms are efficient and effective in reducing the interaction time between clients, and our proposed Distributed-Modify-Assignment adapts well to the dynamics of client participation and network conditions. For the special case of tree network topologies, we develop a polynomial-time algorithm to compute the optimal client assignment.

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.

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 inter-server 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 change 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 combinational optimization problem. We prove that this problem is NP-complete. Four heuristic assignment algorithms are proposed and evaluated using real Internet latency data. The experimental results show that our proposed greedy algorithm generally produces near optimal interactivity and significantly reduces the interaction time between clients compared to the intuitive algorithm that assigns each client to its nearest server.

Distributed Interactive Applications (DIAs) are networked systems that allow multiple participants to interact with one another in real time. Wide spreads of client locations in larges-cale DIAs often require geographical distribution of servers to meet the latency requirements of the applications. In the distributed server architecture, how the clients are assigned to the servers directly affects the network latency involved in the interactions between clients. This paper focuses on the client assignment problem for enhancing the interactivity performance of DIAs. We formulate the problem as a combinational optimization problem on graphs and prove that it is NP-complete. Several heuristic algorithms are proposed for fast computation of good client assignments and are experimentally evaluated. The experimental results show that the proposed greedy algorithms perform close to the optimal assignment and generally outperform the Nearest-Assignment algorithm that assigns each client to its nearest server.

The network traffic pattern of continuous sensor data collection often changes constantly over time due to the exploitation of temporal and spatial data correlations as well as the nature of condition-based monitoring applications. This paper develops a novel TDMA schedule that is capable of efficiently collecting sensor data for any network traffic pattern and is thus well suited to continuous data collection with dynamic traffic patterns. Following this schedule, the energy consumed by sensor nodes for any traffic pattern is very close to the minimum required by their workloads given in the traffic pattern. The schedule also allows the base station to conclude data collection as early as possible according to the traffic load, thereby reducing the latency of data collection. Experimental results using real-world data traces show that, compared with existing schedules that are targeted on a fixed traffic pattern, our proposed schedule significantly improves the energy efficiency and time efficiency of sensor data collection with dynamic traffic patterns.

An Interest Management (IM) mechanism eliminates irrelevant status updates transmitted in Networked Virtual Environments (NVE). However, IM itself involves both computation and communication overhead, of which the latter is the focus of this paper. Traditionally, there are area-based and cell-based IM mechanisms. This paper proposes a hybrid IM mechanism for peer-to-peer NVEs, that utilizes the cell-based mechanism to reduce Area-Of-Interest (AOI) updates in the area-based mechanism so as to reduce its communication overhead. To compare the new mechanism with the two traditional approaches, a multiplayer game scenario is simulated. The performance results show that, compared to the traditional mechanisms, the hybrid mechanism reduces the upload bandwidth consumption by more than 25.28 percent, reduces the overhead ratio from more than 67.54 percent to only 25.17 percent, and allows more than 5000 players in the Internet to join the same game with today's network upload bandwidth.

Multi-path routing is essential in wireless sensor data collection to overcome the high loss rates in wireless environments. In this paper, we propose an efficient scheduling algorithm for data collection through multi-path routing structures in wireless sensor networks. The message complexity of our proposed scheduling algorithm is O(n(Δ + 3)), where n is the number of sensor nodes in the network and Δ is the maximum node degree. The best existing scheduling algorithm for single-path routing structures has the message complexity of O(n(χ + Δ + 2)), where χ is the number of 2-hop neighbors of a sensor node. The complexity of the proposed scheduling algorithm is a significant improvement since χ is normally on the order of O(Δ2). In addition, we also develop a method for deriving a (super) lower bound on the shortest possible length of the data collection schedule generated by any algorithm. Extensive experimental results show that the proposed scheduling algorithm produces good data collection schedules with greatly reduced running time and fewer messages generated as compared to existing algorithms. The length of the data collection schedule produced by our algorithm is within 2.3 times of the lower bound estimate across a wide range of network settings.

Rings overlay is a class of multi-path routing structure for wireless sensor networks that exploits the broadcast nature of wireless communication to cope with communication failures. While the rings overlay aims to create multiple propagation paths for sensor nodes to transport data, the sensor nodes in the ring next to the base station inherently have only a single propagation path to the base station and their data remain to be transported by single path routing. In this paper, we propose and analyze an enhanced relay scheme for improving the robustness of sensor data collection through the rings overlay. The objective is to let all sensor nodes in the ring next to the base station to benefit from multi-path routing without sacrificing energy efficiency. Analytical and experimental results show that compared with the original relay scheme, the proposed enhanced relay scheme significantly improves the robustness of sensor data collection through the rings overlay.

In this paper, we investigate the construction of rings overlay in wireless sensor networks for enhancing the robustness of sensor data collection. Rings overlay is a class of multi-path routing structure that exploits the broadcast nature of wireless communication to cope with communication failures. We propose a distributed approach for constructing the rings overlay to allow sensor nodes to benefit from multi-path routing as much as possible. The proposed approach does not require sensor nodes to have global knowledge about the entire network. Experimental results show that the proposed construction approach significantly improves the robustness of sensor data collection through the rings overlay compared with a baseline greedy construction approach.

The fundamental goal of distributed virtual environments (DVEs) is to create a common and consistent presentation of the virtual world among a set of computers interconnected by a network. This paper investigates update scheduling algorithms to make efficient use of network capacity and improve consistency in DVEs. Our approach is to schedule state updates according to their potential impacts on consistency. In DVEs, the perceptions of participants are affected by both the spatial magnitude and temporal duration of inconsistency in the virtual world. Using the metric of time-space inconsistency, we analytically derive the optimal update schedules for minimizing the impact of inconsistency. Based on the analysis, we propose a number of scheduling algorithms that integrate spatial and temporal factors. These algorithms also take into consideration the effect of network delays. The algorithms can be used on top of many existing mechanisms such as dead reckoning. Experimental results show that our proposed algorithms significantly outperform the intuitive algorithms that are based on spatial or temporal factors only.

In location-based services, users with location-aware mobile devices are able to make queries about their surroundings anywhere and at any time. While this ubiquitous computing paradigm brings great convenience for information access, it also raises concerns over potential intrusion into user location privacy. To protect location privacy, one typical approach is to cloak user locations into spatial regions based on user-specified privacy requirements, and to transform location-based queries into region-based queries. In this paper, we identify and address three new issues concerning this location cloaking approach. First, we study the representation of cloaking regions and show that a circular region generally leads to a small result size for region-based queries. Second, we develop a mobility-aware location cloaking technique to resist trace analysis attacks. Two cloaking algorithms, namely MaxAccu_Cloak and MinComm_Cloak, are designed based on different performance objectives. Finally, we develop an efficient polynomial algorithm for evaluating circular-region-based kNN queries. Two query processing modes, namely bulk and progressive, are presented to return query results either all at once or in an incremental manner. Experimental results show that our proposed mobility-aware cloaking algorithms significantly improve the quality of location cloaking in terms of an entropy measure without compromising much on query latency or communication cost. Moreover, the progressive query processing mode achieves a shorter response time than the bulk mode by parallelizing the query evaluation and result transmission.

In distributed virtual environments, e.g., online gaming, collaborative designs and distributed military simulations, interactivity is one of the most important requirements. The users may notice serious degradations in quality of service when interacting in the virtual world if the response from the system is much slower than what they have experienced in real life. In this paper, we consider the problem of placing distributed servers in the network to reduce client-server communication latencies, which is termed the server placement problem. We proposed two new network-aware placement algorithms which take into account users' locations in the network and connectivity at the autonomous system level to determine good sites for servers. Extensive experiments with realistic network models showed that these new algorithms significantly outperform existing approaches that require full knowledge of network connectivity at the router-level topologies.

Communication is a primary source of energy consumption in wireless sensor networks. Due to resource constraints, the sensor nodes may not have enough energy to report every reading to the base station over a required network lifetime. This paper investigates data collection strategies in lifetime-constrained wireless sensor networks. Our objective is to maximize the accuracy of data collected by the base station over the network lifetime. Instead of sending sensor readings periodically, the relative importance of the readings is considered in data collection: the sensor nodes send data updates to the base station when the new readings differ more substantially from the previous ones. We analyze the optimal update strategy and develop adaptive update strategies for both individual and aggregate data collections. We also present two methods to cope with message losses in wireless transmission. To make full use of the energy budgets, we design an algorithm to allocate the numbers of updates allowed to be sent by the sensor nodes based on their topological relations. Experimental results using real data traces show that, compared with the periodic strategy, adaptive strategies significantly improve the accuracy of data collected by the base station.

Consistency maintenance is important to the sharing of dynamic contents in peer-to-peer (P2P) networks. The TTL-based mechanism is a natural choice for maintaining freshness in P2P content sharing. This paper investigates TTL-based consistency maintenance in unstructured P2P networks. In this approach, each replica is assigned an expiration time beyond which the replica stops serving new requests unless it is validated. While TTL-based consistency is widely explored in many client-server applications, there has been no study on TTL-based consistency in P2P networks. Our main contribution is an analytical model that studies the search performance and the freshness of P2P content sharing under TTL-based consistency. Due to the random nature of request routing, P2P networks are fundamentally different from most existing TTL-based systems in that every node with a valid replica has the potential to serve any other node. We identify and discuss the factors that affect the performance of P2P content sharing under TTL-based consistency. Our results indicate a tradeoff between search performance and freshness: the search cost decreases sublinearly with decreasing freshness of P2P content sharing. We also compare two types of unstructured P2P networks and find that clustered P2P networks improve the freshness of content sharing over flat P2P networks under TTL-based consistency.

Energy efficiency is one of the most critical issues in the design of wireless sensor networks. Observing that many sensor applications for object tracking can tolerate a certain degree of imprecision in the location data of tracked objects, this paper studies precision-constrained approximate queries that trade answer precision for energy efficiency. We develop an energy-conserving approximate storage (EASE) scheme to efficiently answer approximate location queries by keeping error-bounded imprecise location data at some designated storage node. The data impreciseness is captured by a system parameter called the approximation radius. We derive the optimal setting of the approximation radius for our storage scheme based on the mobility pattern and devise an adaptive algorithm to adjust the setting when the mobility pattern is not available a priori or is dynamically changing. Simulation experiments are conducted to validate our theoretical analysis of the optimal approximation setting. The simulation results show that the proposed EASE scheme reduces the network traffic from a conventional approach by up to 96 percent and, in most cases, prolongs the network lifetime by a factor of 2-5.

This demonstration presents iPDA, a system to support privacy-preserving data access in location-based mobile services. The iPDA system consists of three main components: 1) a mobility-aware location cloaker that cloaks the user's location with a region and transforms a location- based query to a region-based query, 2) a progressive query processor that efficiently evaluates a result superset for the location-based query and, 3) a result refiner that refines the superset to generate the exact query result for the user. We discuss in detail the architecture and functionalities of our iPDA system. In addition, a tourist information system named iGuide, as an iPDA application, is prototyped for demonstration.

Top-k monitoring is important to many wireless sensor applications. This paper exploits the semantics of top-k query and proposes an energy-efficient monitoring approach called FILA. The basic idea is to install a filter at each sensor node to suppress unnecessary sensor updates. Filter setting and query reevaluation upon updates are two fundamental issues to the correctness and efficiency of the FILA approach. We develop a query reevaluation algorithm that is capable of handling concurrent sensor updates. In particular, we present optimization techniques to reduce the probing cost. We design a skewed filter setting scheme, which aims to balance energy consumption and prolong network lifetime. Moreover, two filter update strategies, namely, eager and lazy, are proposed to favor different application scenarios. We also extend the algorithms to several variants of top-k query, that is, order-insensitive, approximate, and value monitoring. The performance of the proposed FILA approach is extensively evaluated using real data traces. The results show that FILA substantially outperforms the existing TAG-based approach and range caching approach in terms of both network lifetime and energy consumption under various network configurations.

Geographically replicating popular objects in the Internet speeds up content distribution at the cost of keeping the replicas consistent and up-to-date. The overall effectiveness of replication can be measured by the total communication cost consisting of client accesses and consistency management, both of which depend on the locations of the replicas. This paper investigates the problem of placing replicas under the widely used TTL-based consistency scheme. A polynomial-time algorithm is proposed to compute the optimal placement of a given number of replicas in a network. The new replica placement scheme is compared, using real Internet topologies and Web traces, against two existing approaches which do not consider consistency management or assume invalidation-based consistency scheme. The factors affecting their performance are identified and discussed

This paper presents a large-displacement and decoupled AYZ-flexure parallel mechanism (FPM) using typical large-displacement prismatic joints, and a nonlinear modeling method for these prismatic joints is proposed. The monolithic prismatic joints using notch hinges have large motion range of more than 1 mm, hence, the assembled XYZ-stage is large-displacement. Since the prismatic joints have small parasitic motion error and are orthogonally combined in parallel, the XYZ-stage can achieve the three decoupled translational motions. Exact stiffness and dynamics models are given using the proposed modeling method. The comparison between the proposed method and the classical pseudo-rigid-body (PRB) method is done to the example of the XYZ-stage. Finally, the experiments are conducted to verify the proposed XYZ-stage and the comparison between two methods

Top-k monitoring is important to many wireless sensor applications. This paper exploits the semantics of top-k query and proposes a novel energy-efficient monitoring approach, called FILA. The basic idea is to install a filter at each sensor node to suppress unnecessary sensor updates. The correctness of the top-k result is ensured if all sensor nodes perform updates according to their filters. We show via simulation that FILA outperforms the existing TAGbased approach by an order of magnitude.

This paper exploits the tradeoff between data quality and energy consumption to extend the lifetime of wireless sensor networks. We consider the applications that require some aggregate form of sensed data with precision guarantees. Our key idea is to differentiate the precisions of data collected from different sensor nodes to balance their energy consumption. This is achieved by partitioning the precision constraint of data aggregation and allocating error bounds to individual sensor nodes in a coordinated fashion. Three factors affecting the lifetime of sensor nodes are identified: (1) the changing pattern of sensor readings; (2) the residual energy of sensor nodes; and (3) the communication cost between the sensor nodes and the base station. We analyze the optimal precision allocation in terms of network lifetime and propose an adaptive precision allocation scheme that dynamically adjusts the error bounds of sensor nodes. Experimental results using real data traces show that the proposed scheme significantly improves network lifetime compared to existing methods.

This paper proposes an XYZ-flexure parallel mechanism (FPM) with large displacement and decoupled kinematics structure. The large-displacement FPM has large motion range more than 1 mm. Moreover, the decoupled XYZ-stage has small cross-axis error and small parasitic rotation. In this study, the typical prismatic joints are investigated, and a new large-displacement prismatic joint using notch hinges is designed. The conceptual design of the FPM is proposed by assembling these modular prismatic joints, and then the optimal design of the FPM is conducted. The analytical models of linear stiffness and dynamics are derived using pseudo-rigid-body (PRB) method. Finally, the numerical simulation using ANSYS is conducted for modal analysis to verify the analytical dynamics equation. Experiments are conducted to verify the proposed design for linear stiffness, cross-axis error and parasitic rotation

A lot of research efforts have been devoted to improving energy efficiency for wireless sensor networks by exploring distributed data storage and in-network query processing techniques. In this paper, we present a generic two-tier data storage strategy for answering precision-constrained approximate queries in a sensor network. The basic idea is to keep two versions of data in the network. A highprecision version is kept at the sensor node that captures the data while a low-precision version is maintained at the base station. We develop query processing and node refreshment strategies for various types of approximate queries under the two-tier storage. Our extensive experiments show that the two-tier storage strategy outperforms the basic centralized storage scheme by an order of magnitude in terms of network lifetime under various system configur

Access efficiency and energy conservation are two critical performance concerns in a wireless data broadcast system. We propose in this paper a novel parameterized index called the exponential index that has a linear yet distributed structure for wireless data broadcast. Based on two tuning knobs, index base and chunk size, the exponential index can be tuned to optimize the access latency with the tuning time bounded by a given limit, and vice versa. The client access algorithm for the exponential index under unreliable broadcast is described. A performance analysis of the exponential index is provided. Extensive ns-2-based simulation experiments are conducted to evaluate the performance under various link error probabilities. Simulation results show that the exponential index substantially outperforms the state-of-the-art indexes. In particular, it is more resilient to link errors and achieves more performance advantages from index caching. The results also demonstrate its great flexibility in trading access latency with tuning time.

Data broadcast is an attractive data dissemination method in mobile environments. To improve energy efficiency, existing air indexing schemes for data broadcast have focused on reducing tuning time only, i.e., the duration that a mobile client stays active in data accesses. On the other hand, existing broadcast scheduling schemes have aimed at reducing access latency through nonflat data broadcast to improve responsiveness only. Not much work has addressed the energy efficiency and responsiveness issues concurrently. This paper proposes an energy-efficient indexing scheme called MHash that optimizes tuning time and access latency in an integrated fashion. MHash reduces tuning time by means of hash-based indexing and enables nonflat data broadcast to reduce access latency. The design of hash function and the optimization of bandwidth allocation are investigated in depth to refine MHash. Experimental results show that, under skewed access distribution, MHash outperforms state-of-the-art air indexing schemes and achieves access latency close to optimal broadcast scheduling.

Expiration-based consistency management is widely used to keep replicated contents up-to-date in the Internet. The effectiveness of replication can be characterized by the communication costs of client accesses and consistency management. Both costs depend on the locations of the replicas. This paper investigates the problem of placing replicas in a network where replica consistency is managed by the expiration-based scheme. Our objective is to minimize the total cost of client accesses and consistency management. By analyzing the communication cost of recursive validations for cascaded replicas, we prove that in the optimal placement scheme, the nodes not assigned replicas induce a connected subgraph that includes the origin server. Our results are generic in that they apply to any request arrival patterns. Based on the analysis, an O(D){\hbox{-}}{\rm{time}} algorithm is proposed to compute the optimal placement of the replicas, where D is the sum of the number of descendants over all nodes in the routing tree.

On-demand broadcast is an effective wireless data dissemination technique to enhance system scalability and deal with dynamic user access patterns. With the rapid growth of time-critical information services in emerging applications, there is an increasing need for the system to support timely data dissemination. This paper investigates online scheduling algorithms for time-critical on-demand data broadcast. We propose a novel scheduling algorithm called SIN-/spl alpha/ that takes the urgency and number of outstanding requests into consideration. An efficient implementation of SIN-/spl alpha/ is presented. We also analyze the theoretical bound of request drop rate when the request arrival rate rises toward infinity. Trace-driven experiments show that SIN-/spl alpha/ significantly outperforms existing algorithms over a wide range of workloads and approaches the analytical bound at high request rates.

Energy efficiency is one of the most critical issues in the design of wireless sensor networks. Observing that many sensor applications for object tracking can tolerate a certain degree of imprecision in location data of tracked objects, this paper studies precision-constrained approximate queries that trade answer precision for energy efficiency. We develop an Energy-conserving Approximate StoragE (EASE) scheme to ef- ficiently answer approximate location queries by keeping error- bounded imprecise location data at some designated storage node. The data impreciseness is captured by a system parameter, i.e., approximation radius. We analyze the performance of EASE in terms of message complexity and derive the optimal setting of approximation radius. We show via extensive simulation experiments that, as compared to a conventional approach, the EASE scheme cuts down the network traffic by up to 96% and, in most cases, prolongs the network lifetime by a factor of 2�5. I. INTRODUCTION

The rapid growth of new information services and business-oriented applications entails the consideration of quality of service (QoS) in content distribution. This paper investigates the QoS-aware replica placement problems for responsiveness QoS requirements. We consider two classes of service models: replica-aware services and replica-blind services. In replica-aware services, the servers are aware of the locations of replicas and can therefore optimize request routing to improve responsiveness. We show that the QoS-aware placement problem for replica-aware services is NP-complete. Several heuristic algorithms for fast computation of good solutions are proposed and experimentally evaluated. In replica-blind services, the servers are not aware of the locations of replicas or even their existence. As a result, each replica only serves the requests flowing through it under some given routing strategy. We show that there exist polynomial optimal solutions to the QoS-aware placement problem for replica-blind services. Efficient algorithms are proposed to compute the optimal locations of replicas under different cost models.

Persistent connections are increasingly being used in Web retrieval due to wide adoption of HTTP/1.1 standards. With persistent connections, the request allocation algorithm used by Web clusters is often session-grained. This article studies the caching performance of Web clusters under session-grained request allocation. It is shown that although content-based algorithms considerably improve caching performance over content-blind algorithms at the request-grained level, most performance gain is offset by the allocation dependency that arises when the requests are allocated at the session-grained level. The performance loss increases with cluster size and connection holding time. An optimization problem is then formulated for improving the caching effectiveness of session-grained allocation. The problem is proven to be NP-complete. Based on a heuristic approach, a session-affinity aware algorithm is presented that makes use of the correlation between the requests in a session. The new algorithm is shown to significantly outperform the content-based algorithm under session-grained allocation. It is also shown that optimizing session-grained allocation cannot fully compensate for the performance loss caused by allocation dependency.

The rapid growth of time-critical information services and business-oriented applications is making quality of service (QoS) support increasingly important in content distribution. This paper investigates the problem of placing object replicas (e.g., web pages and images) to meet the QoS requirements of clients with the objective of minimizing the replication cost. We consider two classes of service models: replica-aware service and replica-blind service. In the replica-aware model, the servers are aware of the locations of replicas and can therefore direct requests to the nearest replica. We show that the QoS-aware placement problem for replica-aware services is NP-complete. Several heuristic algorithms for efficient computation of suboptimal solutions are proposed and experimentally evaluated. In the replica-blind model, the servers are not aware of the locations of replicas or even their existence. As a result, each replica only serves the requests flowing through it under some given routing strategy. We show that there exist polynomial optimal solutions to the QoS-aware placement problem for replica-blind services. Efficient algorithms are proposed to compute the optimal locations of replicas under different cost models.

Wireless data broadcast has received a lot of attention from industries and academia in recent years. Access efficiency and energy conservation are two critical performance concerns in a wireless data broadcast environment. To improve the efficiency of energy consumption on mobile devices, traditional disk-based indexing techniques such as B$^+$-tree have been extended to index broadcast data on a wireless channel. However, existing designs are mostly based on centralized tree structures. Most of these indexing techniques are not flexible in the sense that the trade-off between access efficiency and energy conservation is not adjustable based on application specific requirements. We propose in this paper a novel parameterized index, called the exponential index, which can be tuned to optimize the access latency with the tuning time bounded by a given limit, and vice versa. The proposed index is very efficient because it facilitates replication naturally by sharing links in multiple search trees and thus minimizes storage overhead. Experimental results show that the exponential index not only achieves better performance than the state-of-the-art indexes but also enables great flexibility in trade-offs between access latency and tuning time.

The expiration-based scheme is widely used to manage the consistency of cached and replicated contents such as Web objects. In this approach, each replica is associated with an expiration time beyond which the replica has to be validated. While the expiration-based scheme has been investigated in the context of a single replica, not much work has been done on its behaviors with respect to multiple replicas. To allow for efficient consistency management, it is desirable to organize the replicas into a distribution tree where a lower level replica seeks validation with a higher level replica when its lifetime expires. This paper investigates the construction of a distribution tree for a given set of replicas with the objective of minimizing the total communication cost of consistency management. This is formulated as an optimization problem and is proven to be NP-complete. The optimal distribution tree is identified in some special cases and several heuristic algorithms are proposed for the general problem. The performance of the heuristic algorithms is experimentally evaluated against two classical graph-theoretic algorithms of tree construction: the shortest-paths tree and the minimum spanning tree.

Dynamic Web contents are generated by running application programs on base data which often change frequently. Geographically replicating the applications that construct these contents (including the programs and the related data they access) is an effective approach to improve their access latency. To maintain the freshness of an object replica, the new version of the object either has to be fetched from remote servers or be reconstructed locally when the origin copy is updated. We present a theoretical study on geographical replication of dynamic Web contents with the objective of minimizing the consistency management costs in terms of update transfers and object reconstruction. The dependencies among dynamic objects and base data are modeled as a directed acyclic graph. We formulate the minimum cost replication problem under a flat framework of update delivery. The problem is solved by first transforming it into a minimum cut problem in a flow network. A polynomial-time algorithm is then proposed to compute the optimal replication strategy which designates where each object should be replicated and how to keep the replicas up-to-date.

Large-scale content delivery systems such as the Web often deploy multiple caches at different locations to reduce access latency and network traffic. These caches are usually organized in a cascaded fashion where requests not hitting a lower level cache are forwarded to a higher level cache. The performance of cascaded caching depends on how the cache contents are managed, including object placement and replacement schemes. We present a general analytical framework for coordinated management of cascaded caches. The object placement problem is formulated as an optimization problem and the optimal locations for caching objects are computed by a dynamic programming algorithm. Based on the framework, we propose a novel caching scheme that incorporates both object placement and replacement strategies. The proposed scheme makes caching decisions for the set of caches lying on the delivery path of a request in a coordinated fashion. Simulation experiments based on real traces from Web caches have been conducted under two different cascaded caching architectures: enroute caching and hierarchical caching. The results show that for both architectures, the proposed scheme significantly outperforms existing schemes that consider object placement or replacement at individual caches only.

Mobile location-dependent information services are gaining increasing interest in both academic and industrial communities. In these services, data values depend on their locations. Caching frequently accessed data on mobile clients can help save wireless bandwidth and improve system performance. However, since client location changes constantly, location-dependent data may become obsolete not only due to updates performed on data items but also because of client movements across the network. To the best of the authors' knowledge, previous work on cache invalidation issues focused on data updates only. This paper considers data inconsistency caused by client movements and proposes three location-dependent cache invalidation schemes. The performance for the proposed schemes is investigated by both analytical study and simulation experiments in a scenario where temporal- and location-dependent updates coexist. Both analytical and experimental results show that, in most cases, the proposed methods substantially outperform the NSI scheme, which drops the entire cache contents when hand-off is performed.

Caching is an important means to scale up the growth of the Internet. Weak consistency is a major approach used in Web caching and has been deployed in various forms. The paper investigates some properties and performance issues of an expiration-based caching system. We focus on a hierarchical caching system based on the time-to-live (TTL) expiration mechanism and present a basic model for such a system. By analyzing the intrinsic TTL timing behavior in the basic model, we derive several important performance metrics from the perspective of the caching system and end users, respectively. Our results offer some basic understanding of a hierarchical caching system based on the weak consistency paradigm.

Streaming media is expected to become one of the most popular types of Web content in the future. Due to increasing variety of client devices and the range of access speeds to the Internet, multimedia contents may be required to be transcoded to match the client's capability. With transcoding, both the network and the proxy CPU are potential bottlenecks for streaming media delivery. This paper discusses and compares various caching algorithms designed for transcoding proxies. In particular we propose a new adaptive algorithm that dynamically selects an appropriate metric for adjusting the management policy. Experimental results show that the proposed algorithm significantly outperforms those that cache only untranscoded or only transcoded objects. Moreover motivated by the characteristics of many video compression algorithms, we investigate partitioning a video object into sections based on frame type and handling them individually for proxy caching. It is found that partitioning improves performance when CPU power rather than network bandwidth is the limiting resource, particularly when the reference pattern is not highly skewed.

Web caching is an important technique for reducing Internet access latency, network traffic, and server load. This paper investigates cache management strategies for the en-route web caching environment, where caches are associated with routing nodes in the network. We propose a novel caching scheme that integrates both object placement and replacement policies and which makes caching decisions on all candidate sites in a coordinated fashion. In our scheme, cache status information along the routing path of a request is used in dynamically determining where to cache the requested object and what to replace if there is not enough space. The object placement problem is formulated as an optimization problem and the optimal locations to cache the object are obtained using a low-cost dynamic programming algorithm. Extensive simulation experiments have been performed to evaluate the proposed scheme in terms of a wide range of performance metrics. The results show that the proposed scheme significantly outperforms existing algorithms which consider either object placement or replacement at individual caches only.

Hash routing is an effective approach for coordinating a collection of Web proxies. In this paper, we present a comprehensive analytical model for hash routing which takes into consideration a number of factors: the original request distribution, the object allocation strategy, the speeds of the proxies and cache hit ratios. Based on this model, the optimal hash routing problems for static and dynamic client configurations are investigated. Two schemes, OBJ-OPT (OBJect OPTimization) and OBJ/DNS-OPT (OBJect and Domain Name Server OPTimization), are proposed to reduce the response times of Web requests. OBJ-OPT optimizes object allocation under a static client configuration, and OBJ/DNS-OPT optimizes both object and DNS allocations under a dynamic client configuration. Extensive trace-driven simulations have been conducted to evaluate the proposed schemes. The results show that they significantly outperform the intuitive scheme based only on the speeds of the proxies.

This paper investigates dynamic load balancing issues in the multidomain environment where local area networks (LANs) are interconnected by the Internet. Because of the much slower Internet communication speed and limited bandwidth, existing load balancing algorithms for LANs are unsuitable for the multidomain environment. New issues such as lag time in updating load information and network cost of transferring jobs must be addressed. To tackle these problems, the conventional least load scheduler is extended to the multidomain environment by employing a hierarchical structure, and several quick update techniques are proposed. Also, a heuristic taking both the machine load and the network cost into consideration is developed to evaluate the benefits of sending jobs to computers in different domains. A set of experiments conducted on the BALANCE testbed showed that the proposed techniques provide significant performance improvement over existing algorithms.

This paper investigates static job scheduling schemes that distribute workload in a network of computers with different speeds. Static schemes involve very low overhead and complexity compared to dynamic schemes, but can still provide significant performance improvement over the case of no load balancing. Optimization techniques are proposed for workload allocation and job dispatching. Workload allocation is modeled as a non-linear optimization problem and solved mathematically. It is shown that allocating a disproportionately high percentage of jobs to the more powerful computers improves system performance. The proposed job dispatching algorithm is an extension of the traditional round-robin scheme. The objective is to reduce burstiness in the job arrival stream to each computer The schemes are evaluated by simulation experiments. Performance results verify their effectiveness in terms of mean response time, mean response ratio, and fairness. The Optimized Round-Robin (ORR) strategy which combines both techniques outperforms other static scheduling algorithms examined.