State-of-the-art (SOTA) fact-checking systems combat misinformation by employing autonomous LLM-based agents to decompose complex claims into smaller sub-claims, verify each sub-claim individually, and aggregate the partial results to produce verdicts with justifications (explanations for the verdicts). The security of these systems is crucial, as compromised fact-checkers can amplify misinformation, but remains largely underexplored. To bridge this gap, this work introduces a novel threat model against such fact-checking systems and presents Fact2Fiction, the first poisoning attack framework targeting SOTA agentic fact-checking systems. Fact2Fiction employs LLMs to mimic the decomposition strategy and exploit system-generated justifications to craft tailored malicious evidences that compromise sub-claim verification. Extensive experiments demonstrate that Fact2Fiction achieves 8.9%-21.2% higher attack success rates than SOTA attacks across various poisoning budgets and exposes security weaknesses in existing fact-checking systems, highlighting the need for defensive countermeasures.

State-of-the-art single-agent claim verification methods struggle with complex claims that require nuanced analysis of multifaceted evidence. Inspired by real-world professional fact-checkers, we propose DebateCV, the first debate-driven claim verification framework powered by multiple LLM agents. In DebateCV, two Debaters argue opposing stances to surface subtle errors in single-agent assessments. A decisive Moderator is then required to weigh the evidential strength of conflicting arguments to deliver an accurate verdict. Yet, zero-shot Moderators are biased toward neutral judgments, and no datasets exist for training them. To bridge this gap, we propose Debate-SFT, a post-training framework that leverages synthetic data to enhance agents' ability to effectively adjudicate debates for claim verification. Results show that our methods surpass state-of-the-art non-debate approaches in both accuracy (across various evidence conditions) and justification quality.

Ride-sharing represents a sustainable transportation paradigm that is beneficial to human, society, and environment. Common ride-sharing pricing approaches determine prices for riders through optimizing one or more figures of merit, e.g., the profit or revenue. However, they overlook an important issue—fairness—which, when perceived by the riders, can critically affect their degree of satisfaction. In this work, we take the initiative to consider an intuitive and appropriate notion of individual fairness called fairness-in-hindsight for riders in ride-sharing pricing. We study the problem of online fair pricing of shared rides (which allow multiple riders to share one ride) with an aim to maximize the profit of the ride-sharing operator/platform. We design an online fair ride-sharing pricing algorithm called OnFairRP, which comprises phases oflearning, transition, and exploitation. We prove that OnFairRP has a sub-linear regret bound and can guarantee the fairness between riders. Our extensive performance evaluations using real-world data traces of ride-sharing demonstrate the advantages of OnFairRP over benchmarking schemes including commonly used methods with or without fairness guarantee.

Decentralized online convex optimization (DOCO), as a pivotal computational paradigm in machine learning, has been applied to many critical tasks. However, existing DOCO algorithms, due to their excessive emphasis on the worst-case theoretical performance, appear to be overly cautious in making decisions across all possible cases, especially in real-world applications where the worst cases actually hardly occur. Therefore, these existing approaches typically are limited in performance in practice. To avoid such pessimistic strategies, we propose to study the approach of augmenting DOCO with machine-learned predictions that can guide the decision-making process. We present an overview of the problem along with the preliminary results and outlook in this work.

Decentralized online optimization, a pivotal paradigm in machine learning, involves multiple agents making online decisions cooperatively in a decentralized network. Despite its outstanding capabilities in processing large-scale streaming data, the ubiquitous existence of malicious agents, capable of disseminating arbitrary information among their neighbors and undetectable a priori, poses a severe threat to the reliability and efficacy of existing decentralized online optimization solutions. In response to the above critical vulnerability in practice, we take the first step to properly address the threat posed by malicious agents. We propose ROOO, a novel robust decentralized online optimization algorithm, specifically designed to counteract the detrimental impact of malicious agents. Our theoretical analysis shows that the regret bound of ROOO is sub-linear, indicating that, over time, its performance progressively approximates that of an offline oracle operating with the benefit of hindsight. Empirical evaluations in two networking applications, including opportunistic channel selection and mobile crowdsensing, further validate our theoretical results and demonstrate the competitiveness of ROOO compared to several advanced baselines.

The online linear optimization paradigm is important to many real-world network applications as well as theoretical algorithmic studies. Recent studies have made attempts to augment online linear optimization with machine-learned predictions of the cost function that are meant to improve the performance of the algorithms. However, they fail to address the critical case in practical systems where the predictions can be arbitrarily bad. In this work, we take the first step to study the problem of online linear optimization with a dynamic number of arbitrarily bad machine-learned predictions per round and propose an algorithm termed OLOAP. Our theoretical analysis shows that, when the qualities of the predictions are satisfactory, OLOAP achieves a regret bound of O(logT), which circumvents the tight lower bound of Ω($\sqrt T $) for the vanilla problem of online linear optimization (i.e., the one without any predictions). Meanwhile, the regret of our algorithm is never worse than O($\sqrt T $) irrespective of the qualities of predictions. In addition, we further derive a lower bound for the regret of the studied problem, which demonstrates that OLOAP is near-optimal. We consider two important network applications and conduct extensive evaluations. Our results validate the superiority of our algorithm over state-of-the-art approaches.

Ride-hailing is a sustainable transportation paradigm where riders access door-to-door traveling services through a mobile phone application, which has attracted a colossal amount of usage. There are two major planning tasks in a ride-hailing system: 1) matching, i.e., assigning available vehicles to pick up the riders; and 2) repositioning, i.e., proactively relocating vehicles to certain locations to balance the supply and demand of ride-hailing services. Recently, many studies of ride-hailing planning that leverage machine learning techniques have emerged. In this article, we present a comprehensive overview on latest developments of machine learning-based ride-hailing planning. To offer a clear and structured review, we introduce a taxonomy into which we carefully fit the different categories of related works according to the types of their planning tasks and solution schemes, which include collective matching, distributed matching, collective repositioning, distributed repositioning, and joint matching and repositioning. We further shed light on many real-world data sets and simulators that are indispensable for empirical studies on machine learning-based ride-hailing planning strategies. At last, we propose several promising research directions for this rapidly growing research and practical field.

Wireless sensor networks (WSNs) leveraging millimeter wave (mmWave) communication for bandwidth-demanding applications is considered in this article. Despite the large bandwidth, the delivery of delay-sensitive information collected by sensors may still face significant latency due to the vulnerability to intermittent link blockage. Hence, the guarantee of low age of information (AoI) in mmWave WSNs is not straightforward. In this article, the wireless sensing and dynamic programming techniques are jointly exploited to relieve the above issue. The former tracks the human blockers and predicts the chance of link blockage; the latter optimizes the transmission of multiple sensors based on the prediction. Particularly, the long-term optimization of sampling, uplink time and power allocation policies in a sensor network can be formulated as an infinite-horizon Markov decision process (MDP) with discounted cost, where the state transition probabilities can be predicted via wireless sensing. A novel low-complexity solution framework, namely COSMO, with a guaranteed performance in the worst case, is proposed. Simulations show that compared with heuristic benchmarks, benefiting from the prediction of the link blockage, COSMO can significantly suppress the average system cost, which consists of both AoI and energy consumption.

In this paper, the joint downlink delay-aware scheduling in a large time span, where the rotation of User Equipments (UEs) may lead to significant channel variation, is investigated via a novel approximate Markov Decision Process (MDP) method. Specifically, we consider the joint downlink power allocation and receiving UE selection of a number of successive frames in a millimeter Wave (mmWave) system with quasi-static scattering clusters in the channel and rotating UEs. The propagation statistics of scattering clusters can be tracked via a learning method. Since the rotation of UEs can be detected, future channel statistics can be forecast via embedded motion sensors. Hence, the overall scheduling is formulated as a finite-horizon MDP with non-stationary predictable state transition probabilities, where the average queuing delay and probability of transmission buffer overflow are considered in the objective of scheduling optimization. A novel low-complexity solution framework with an analytical performance bound is proposed to save the efforts of value iteration. Benefiting from the forecast of system statistics, superior performance to the benchmarks is shown by numerical simulations, particularly in the suppression of buffer overflow rate. Preliminary experiments via an mmWave testbed are conducted to demonstrate the feasibility of the sensor-assisted mmWave beam alignment.

Millimeter wave (MmWave) has been regarded as a promising technology to support high-capacity communications in 5G era. However, its high-layer performance such as latency and packet drop rate in the long term highly depends on resource allocation because mmWave channel suffers significant fluctuation with rotating users due to mmWave sparse channel property and limited field-of-view (FoV) of antenna arrays. In this paper, downlink transmission scheduling considering rotation of user equipments (UE) and limited antenna FoV in an mmWave system is optimized via a novel approximate Markov decision process (MDP) method. Specifically, we consider the joint downlink UE selection and power allocation in a number of frames where future orientations of rotating UEs can be predicted via embedded motion sensors. The problem is formulated as a finite-horizon MDP with non-stationary state transition probabilities. A novel low-complexity solution framework is proposed via one iteration step over a base policy whose average future cost can be predicted with analytical expressions. It is demonstrated by simulations that compared with existing benchmarks, the proposed scheme can schedule the downlink transmission and suppress the packet drop rate efficiently in non-stationary mmWave links.

To understand different aspects of online human behaviors, e.g., the public stances toward various social and political issues, contextual target-specific stance detection has become one of the most important studies on social media. Considering the lack of appropriate data for the studies of contextual target-specific stance detection on Twitter, which is one of the most popular online social platforms worldwide, we introduce CTSDT, a new dataset that consists of a large number of annotated target-specific conversations collected from Twitter. Furthermore, we propose a new contextual target-specific stance detection model called ConMulAttn, which is the first method that can learn both the contents of the posts and the concrete relationships between the posts in a conversation. We conduct extensive evaluation using CTSDT as well as another two popular datasets, CreateDebate and ConvinceMe, for contextual target-specific stance detection. The evaluation results validate the necessity of introducing our dataset CTSDT. Besides, according to the evaluation results, our proposed model ConMulAttn can outperform the state-of-the-art contextual target-specific stance detection method by up to 25% in F1score, indicating the effectiveness and superiority of our solution. Our study has the potential to assist policymakers in utilizing conversation data from online social platforms to efficiently gain real-time insights into public stances on target topics, such as vaccination.

The freshness of information, measured as Age of Information (AoI), is critical for many applications in next-generation wireless sensor networks (WSNs). Due to its high bandwidth, millimeter wave (mmWave) communication is seen to be frequently exploited in WSNs to facilitate the deployment of bandwidth-demanding applications. However, the vulnerability of mmWave to user mobility typically results in link blockage and thus postponed real-time communications. In this paper, joint sampling and uploading scheduling in an AoI-oriented WSN working in mmWave band is considered, where a single human blocker is moving randomly and signal propagation paths may be blocked. The locations of signal reflectors and the real-time position of the blocker can be detected via wireless sensing technologies. With the knowledge of blocker motion pattern, the statistics of future wireless channels can be predicted. As a result, the AoI degradation arising from link blockage can be forecast and mitigated. Specifically, we formulate the long-term sampling, uplink transmission time and power allocation as an infinite-horizon Markov decision process (MDP) with discounted cost. Due to the curse of dimensionality, the optimal solution is infeasible. A novel low-complexity solution framework with guaranteed performance in the worst case is proposed where the forecast of link blockage is exploited in a value function approximation. Simulations show that compared with several heuristic benchmarks, our proposed policy, benefiting from the awareness of link blockage, can reduce average cost up to 49.6%.

Target-specific stance detection on social media, which aims at classifying a textual data instance such as a post or a comment into a stance class of a target issue, is an emerging opinion mining paradigm of importance. An example application would be to overcome vaccine hesitancy in combating the coronavirus pandemic. Existing stance detection strategies rely merely on the individual instances which cannot always capture the expressed stance of a given target. We address a new task called conversational stance detection (CSD) which is to infer the stance toward a given target (e.g., COVID-19 vaccination) when given a data instance and its corresponding conversation thread. To carry out the task, we first propose a benchmarking CSD dataset with annotations of stances and the structures of conversation threads among the instances, which is based on six major social media platforms in Hong Kong. To infer the desired stances from both data instances and conversation threads, we propose a model called Branch-bidirectional encoder representations from transformers (BERT) that incorporates contextual information in conversation threads. Extensive experiments on our CSD dataset show that our proposed model outperforms all the baseline models that do not make use of contextual information. Specifically, it improves the F1 score by 10.3% compared with the state-of-the-art method in the SemEval-2016 Task 6 competition. This shows the potential of incorporating rich contextual information on detecting target-specific stances on social media platforms and suggests a more practical way to construct future stance detection tasks.

Creating 3D shapes from 2D drawings is an important problem with applications in content creation for computer animation and virtual reality. We introduce a new sketch-based system, CreatureShop, that enables amateurs to create high-quality textured 3D character models from 2D drawings with ease and efficiency. CreatureShop takes an input bitmap drawing of a character (such as an animal or other creature), depicted from an arbitrary descriptive pose and viewpoint, and creates a 3D shape with plausible geometric details and textures from a small number of user annotations on the 2D drawing. Our key contributions are a novel oblique view modeling method, a set of systematic approaches for producing plausible textures on the invisible or occluded parts of the 3D character (as viewed from the direction of the input drawing), and a user-friendly interactive system. We validate our system and methods by creating numerous 3D characters from various drawings, and compare our results with related works to show the advantages of our method. We perform a user study to evaluate the usability of our system, which demonstrates that our system is a practical and efficient approach to create fully-textured 3D character models for novice users.

Job dispatching is a fundamental problem in edge computing for load balancing among multiple edge servers. When implementing an edge computing system with distributed job dispatchers in a sizable network, such as a metropolitan area network (MAN), the highly dynamic transmission latency is nonnegligible, which could lead to outdated information being shared. Moreover, the fully observed system state is beyond reach as the reception of any broadcast is time consuming. In this article, we investigate the online distributed job dispatching problem in edge computing, where multiple access points (APs) collect jobs and then dispatch each job to an edge server. The distributed dispatcher on each AP would receive partially and outdated information exchanged via periodic broadcast. Hence, we formulate the distributed job dispatching problem by leveraging the partially observable Markov decision process (POMDP) and propose a novel approximate Markov decision process (MDP) solution framework, calledDecMDP, that bypasses the huge time complexity of conventional POMDP solutions. Both analytical and semi-analytical performance lower bounds are derived for the approximate MDP solution. Furthermore, we extendDecMDPto handle a more general scenario wherea prioriknowledge of the system is absent. Finally, extensive simulations based on the Google Cluster traces show that our policy can achieve the best performance when compared with heuristic baselines, e.g., achieving 20.67% reduction in average job response time, and consistently performs well under various parameter settings.

Heterogeneous cellular networks (HetNets), where low-power low-complexity base stations (Pico-BSs) are deployed inside the coverage of macro base stations (Macro-BSs), can significantly improve the spectrum efficiency by Pico- and Macro base station collaboration. Due to cross-tier interference, joint detection of uplink signals is widely adopted so that Pico-BS can either detect the uplink signals locally or forward them to Macro-BS for processing. The latter can achieve increased throughput at the cost of additional backhaul transmission. In this paper, we study the delay-optimal uplink scheduling problem in HetNets with limited backhaul capacity. Local signal detection or joint signal detection is scheduled in a unified delay-optimal framework. Specifically, we first prove that the problem is NP-hard and then formulate it as a Markov Decision Process. We propose an efficient algorithm, calledOLIUS, that can deal with the exponentially growing state and action space. Furthermore,OLIUSis online learning-based which does not require any prior knowledge on user behavior or channel characteristics. We prove the convergence ofOLIUSand derive an upper bound on its approximation error. Extensive experiments in various scenarios show our algorithm outperforms existing methods in reducing delay and power consumption.

Today's IaaS clouds allow dynamic scaling of VMs allocated to a user, according to real-time demand of the user. There are two types of scaling: horizontal scaling (scale-out) by allocating more VM instances to the user, and vertical scaling (scale-up) by boosting resources of VMs owned by the user. It has been a daunting issue how to efficiently allocate the resources on physical servers to meet the scaling demand of users on the go, which achieves the best server utilization and user utility. An accompanying critical challenge is how to effectively charge the incremental resources, such that the economic benefits of both the cloud provider and cloud users are guaranteed. There has been online auction design dealing with dynamic VM provisioning, where the resource bids are not related to each other, failing to handle VM scaling where later bids may rely on earlier bids of the same user. As the first in the literature, this paper designs an efficient, truthful online auction for resource provisioning and pricing in the practical cases of dynamic VM scaling, where: (i) users bid for customized VMs to use in future durations, and can bid again in the following time to increase resources, indicating both scale-up and scale-out options; (ii) the cloud provider packs the demanded VMs on heterogeneous servers for energy cost minimization on the go. We carefully design resource prices maintained for each type of resource on each server to achieve threshold-based online allocation and charging, as well as a novel competitive analysis technique based on submodularity of the offline objective, to show a good competitive ratio is achieved. The efficacy of the online auction is validated through solid theoretical analysis and trace-driven simulations.

Cognitive radio networks (CRNs) have been proposed to solve the spectrum scarcity problem. One of their fundamental procedures is to construct a communication link on a common channel for the users, which is referred to asrendezvous. In reality, the capability to sense the spectrum may vary from user to user. We study distributed rendezvous for heterogeneous sensing capabilities in this paper. The licensed spectrum is divided into$n$channels,$U = \lbrace 1,2,\ldots,n\rbrace$. We denote the sensing capability of user$i$as$C_i \subseteq U$and the set of available channels (i.e., the channels not occupied by paying users) as$V_i \subseteq C_i$. Due to hardware differences, the users may have different sensing capabilities:$C_i \ne C_j$, and this is calledheterogeneous sensing capability. In this paper, we propose efficient algorithms for two scenarios: the fully available scenario where$V_i = C_i$and the partially available scenario where$V_i \subseteq C_i$. Our idea is to utilize two ‘pointers’ to traverse the sensing capability set, which sets our algorithms apart from the extant rendezvous algorithms. Considering any two neighboring users$a, b$, we propose the Traversing Pointer (TP) algorithm that guarantees rendezvous in$O(\max \lbrace |C_a|,|C_b|\rbrace \log \log n)$time slots for the fully available scenario. This result is only$O(\log \log n)$larger than the theoretical lower bound. Moreover, it removes an$O(\min \lbrace |C_a|,|C_b|\rbrace)$factor when compared to the state-of-the-art result ($O(|C_a||C_b|)$in S.-H. Wuet al.For the partially available scenario, we propose the Moving Traversing Pointers (MTP) and Prime based Moving Traversing Pointers (P-MTP) algorithms that can guarantee rendezvous within$O((\max \lbrace |V_a|,|V_b|\rbrace)^2\log \log n)$and$O(|V_a||V_b|\log \log n)$time slots respectively, where the latter one combines the pointers and a common technique of plugging in a prime number. The proposed algorithms work more efficiently than the previous best result ($O(|C_a||C_b|)$in C.-C. Wuet al.under various circumstances. We also conduct extensive simulations and the results corroborate our analyses.

Dynamicity is one of the most challenging, yet, key aspects of wireless networks. It can come in many guises, such as churn (node insertion/deletion) and node mobility. Although the study of dynamic networks has been popular in distributed computing domain, previous works considered only partial factors causing dynamicity. In this work, we propose a dynamic model that is comprehensive to include crucial dynamic factors on nodes and links. Our model defines dynamicity in terms of localized topological changes in the vicinity of each node, rather than a global view of the whole network. Obviously, a localized dynamic model suits distributed algorithm studies better than a global one. The proposed dynamic model makes use of the more realistic SINR model to describe wireless interference, instead of the oversimplified graph-based models adopted by most existing research. Under the proposed dynamic model, we develop an efficient distributed algorithm accomplishing local broadcast services in the abstract MAC layer that was first presented by Kuhnet al.[24]. Our solution paves the way for many new fast algorithms to solve high-level problems in dynamic networks, such as consensus, single-message broadcast, and multiple-message broadcast. Extensive simulation studies indicate that our algorithm exhibits good performance in realistic environments with dynamic network behaviors.

The Bulk Synchronous Parallel (BSP) paradigm is gaining tremendous importance recently due to the popularity of computations as distributed machine learning and graph computation. In a typical BSP job, multiple workers concurrently conduct iterative computations, where frequent synchronization is required. Therefore, the workers should be scheduled simultaneously and their placement on different computing devices could significantly affect the performance. Simply retrofitting a traditional scheduling discipline will likely not yield the desired performance due to the unique characteristics of BSP jobs. In this work, we deriveSPIN, a novel scheduling designed for BSP jobs with placement-sensitive execution to minimize the makespan of all jobs. We first prove the problem approximation hardness and then present howSPINsolves it with a rounding-based randomized approximation approach. Our analysis indicatesSPINachieves a good performance guarantee efficiently. Moreover,SPINis robust against misestimation of job execution time by theoretically bounding its negative impact. We implementSPINon a production-trace driven testbed with 40 GPUs. Our extensive experiments show thatSPINcan reduce the job makespan and the average job completion time by up to$3\times $and$4.68\times $, respectively.SPINalso demonstrates better robustness to execution time misestimation compared with state-of-the-art heuristic baselines.

In this paper, we investigate distributed broadcasting in dynamic networks, where the topology changes continually over time. We propose a network model that captures the dynamicity caused by both churn and mobility of nodes. In contrast to existing work on dynamic networks, our model defines the dynamicity in terms of localized topological changes in the vicinity of each node, rather than a global view of the whole network. Obviously, a local dynamic model suits distributed algorithms better than a global one. The proposed dynamic model uses the more realistic SINR model to depict wireless interference, instead of oversimplified graph-based models adopted in most existing work. We consider the fundamental communication primitive of global broadcast, which is to disseminate a message from a source node to the whole network. Specifically, we present a randomized distributed algorithm that can accomplish dynamic broadcasting in an asymptotically optimal running time of$O(D_{T})$with a high probability guarantee, under the assumption of reasonably constantdynamicity rate, where$D_{T}$is thedynamic diameter, a parameter proposed to depict the complexity of dynamic broadcasting. We believe our local dynamic model can greatly facilitate distributed algorithm studies in mobile and dynamic wireless networks.

In this paper, we study distributed algorithms to realize efficient communications under the Rayleigh-fading model. This model extends the popular deterministic SINR model using stochastic propagations to address the fading effects observed in reality. Stochastic propagations can greatly increase the difficulty of handling interference and collisions, especially in a local context without much global knowledge. We present a new technique called Inductive Coloring that can be used to schedule fast transmissions with Rayleigh-fading interference. The computation of inductive coloring takes only O(log2n) time with the proposed distributed algorithm, where n is the number of nodes in the network. We illustrate the power of inductive coloring by giving a distributed and randomized algorithm to implement the abstract MAC (absMAC) layer, which was first proposed by Kuhn et al.. With two basic time-guaranteed communication primitives, namely acknowledgement and progress, which correspond to the operations of node local broadcasts and message receptions from others, the absMAC layer decomposes the algorithm design and analysis in networks into two independent components, i.e., implementing the absMAC layer over a physical network and designing algorithms with the help of the two primitives in the absMAC layer. Thus, it sharply reduces the fussy and complicated process of algorithm design and analysis over the physical network. Our proposed algorithm implements the absMAC layer under the Rayleigh-fading model with no more than a logarithmic factor inferior to the optimal solution in terms of time complexity. The presented simulation results indicate that our algorithm performs well in realistic environments. Furthermore, we show that by making full use of our proposed absMAC layer algorithm, many network primitives such as Neighbor Discovery, Single/Multiple-Message Broadcast, and Consensus, can be efficiently implemented.

The Bulk Synchronous Parallel (BSP) paradigm is gaining tremendous importance recently because of the pop-ularity of computations such as distributed machine learning and graph computation. In a typical BSP job, multiple workers concurrently conduct iterative computations, where frequent synchronization is required. Therefore, the workers should be scheduled simultaneously and their placement on different computing devices could significantly affect the performance. Simply retrofitting a traditional scheduling discipline will likely not yield the desired performance due to the unique characteristics of BSP jobs. In this work, we derive SPIN, a novel scheduling designed for BSP jobs with placement-sensitive execution to minimize the makespan of all jobs. We first prove the problem approximation hardness and then present how SPIN solves it with a rounding-based randomized approximation approach. Our analysis indicates SPIN achieves a good performance guarantee efficiently. Moreover, SPIN is robust against misestimation of job execution time by theoretically bounding its negative impact. We implement SPIN on a production-trace driven testbed with 40 GPUs. Our extensive experiments show that SPIN can reduce the job makespan and the average job completion time by up to 3× and 4.68×, respectively. Our approach also demonstrates better robustness to execution time misestimation compared with heuristic baselines.

In this paper, we investigate online distributed job dispatching in an edge computing system residing in a Metropolitan Area Network (MAN). Specifically, job dispatchers are implemented on access points (APs) which collect jobs from mobile users and distribute each job to a server at the edge or the cloud. A signaling mechanism with periodic broadcast is introduced to facilitate cooperation among APs. The transmission latency is non-negligible in MAN, which leads to outdated information sharing among APs. Moreover, the fully-observed system state is discouraged as reception of all broadcast is time consuming. Therefore, we formulate the distributed optimization of job dispatching strategies among the APs as a Markov decision process with partial and outdated system state, i.e., partially observable Markov Decision Process (POMDP). The conventional solution for POMDP is impractical due to huge time complexity. We propose a novel low-complexity solution framework for distributed job dispatching, based on which the optimization of job dispatching policy can be decoupled via an alternative policy iteration algorithm, so that the distributed policy iteration of each AP can be made according to partial and outdated observation. A theoretical performance lower bound is proved for our approximate MDP solution. Furthermore, we conduct extensive simulations based on the Google Cluster trace. The evaluation results show that our policy can achieve as high as 20.67% reduction in average job response time compared with heuristic baselines, and our algorithm consistently performs well under various parameter settings.

On-demand resource provisioning in cloud computing provides tailor-made resource packages (typically in the form of VMs) to meet users' demands. Public clouds nowadays provide elaborated types of VMs, but have yet to offer the most flexible dynamic VM assembly, which is partly due to the lack of a mature mechanism for pricing tailor-made VMs. This work proposes an efficient randomized auction mechanism based on a novel application of smoothed analysis and randomized reduction, for dynamic VM provisioning and pricing in geo-distributed cloud data centers. To the best of our knowledge, it is the first one in literature that achieves (i) truthfulness in expectation, (ii) polynomial running time in expectation, and (iii) (1 - ε)-optimal social welfare in expectation for resource allocation, where ε can be arbitrarily close to0. Our mechanism consists of three modules: (1) an exact algorithm to solve the NP-hard social welfare maximization problem, which has polynomial run-time in expectation, (2) a perturbation-based randomized resource allocation scheme which produces an allocation solution that is (1 - ε)-optimal and (3) an auction mechanism prices the customized VMs using a randomized VCG payment, with a guarantee in truthfulness in expectation. We validate the efficacy of the mechanism through theoretical analysis and trace-driven simulations.

Rendezvous is a fundamental building block in distributed cognitive-radio networks (CRNs), in which pairs or groups of users must find a jointly available channel. Research on the rendezvous problem has focused so far on minimizing the time to rendezvous (to find a suitable channel) or on maximizing the rendezvous degree (percentage of channels on which rendezvous can take place). In this paper, we model the rendezvous problem in a more realistic way that acknowledges the fact that available channels may suffer from interference which varies from location to location as well as over time. In other words, channels are influenced by heterogeneous interference. In this setting, CRNs benefit from rendezvous methods that find a quiet channel, which supports high symbol rates and does not suffer much from dropped packets. In this paper, we propose three important rendezvous design disciplines to achieve bounded rendezvous time, full rendezvous degree, and to rendezvous on quiet channels that suffer little interference. We first present the Disjoint Relaxed Difference Set (DRDS) based rendezvous algorithm as a cornerstone, which ensures rendezvous on every channel (full rendezvous degree) in bounded time. When channels suffer from heterogeneous interference, we propose the Interference based DRDS (I-DRDS) algorithm which ensures rendezvous on channels with less interference, incorporating the interference normalization and interference mapping methods. We conduct extensive simulations to evaluate the proposed algorithms; compared with the state-of-the-art algorithms, the results show that I-DRDS has the best rendezvous performance on less interfered channels, with slightly larger rendezvous time.

This paper studies jamming-resilient distributed backbone construction in multi-hop wireless networks. Specifically, a strong adversarial jamming model is proposed that captures the general jamming phenomena suffered by wireless communications. The jamming model is based on the realistic Signal-to-Interference-plus-Noise-Ratio (SINR) interference model, and is featured by local-uniformity, unrestricted energy budget and reactivity, which covers more jamming scenarios and is much closer to reality than existing jamming models. Under the strong adversarial jamming model, we propose a randomized distributed algorithm that can construct a backbone in J(O(log n + logR)) rounds with high probability, where J(O(log n + log R)) is the number of rounds in the interval from the beginning of the algorithm execution that contains O(log n + log R) unjammed rounds for every node. This result is asymptotically optimal considering the trivial lower bound of Ω(log n) for a successful transmission even without interference and jamming.

This paper investigates distributed Dominating Set (DS) and Connected Dominating Set (CDS) construction in dynamic wireless networks under the SINR interference model. Specifically, we present a new model for dynamic networks that admits both churns (due to node arrivals/departures) and node mobility. Under this dynamic model, we propose efficient algorithms to construct a DS and a CDS with constant approximation ratios w.r.t. the corresponding minimum ones in O(log n) time with a high probability guarantee. To the best of our knowledge, these algorithms are the first known ones for DS and CDS construction in dynamic networks assuming the SINR interference model. We believe our dynamic network model can greatly facilitate distributed algorithm studies in mobile and dynamic wireless networks.

In edge-cloud computing, a set of servers (called edge servers) are deployed near the mobile devices to allow these devices to offload their jobs to and subsequently obtain their results from the edge servers with low latency. One fundamental problem in edge-cloud systems is how to dispatch and schedule the jobs so that the job response time (defined as the interval between the release of the job and the arrival of the computation result at the device) is minimized. In this paper, we propose a general model for this problem, where the jobs are generated in arbitrary order and at arbitrary times at the mobile devices and then offloaded to servers with both upload and download delays. Our goal is to minimize the total weighted response time of all the jobs. The weight is set based on how latency-sensitive the job is. We derive the first online job dispatching and scheduling algorithm in edge-clouds, called OnDisc, which is scalable in the speed augmentation model; that is, OnDisc is (1 + ε)-speed O(1/ε)-competitive for any small constant ε > 0. Moreover, OnDisc can be easily implemented in distributed systems. We also extend OnDisc with a fairness knob to incorporate the trade-off between the average job response time and the degree of fairness among jobs. Extensive simulations based on a real-world data-trace from Google show that OnDisc can reduce the total weighted response time dramatically compared with heuristic algorithms.

Efficient virtual machine (VM) management can dramatically reduce energy consumption in data centers. Existing VM management algorithms fall into two categories based on whether the VMs’ resource demands are assumed to be static or dynamic. The former category fails to maximize the resource utilization as they cannot adapt to the dynamic nature of VMs’ resource demands. Most approaches in the latter category are heuristic and lack theoretical performance guarantees. In this paper, we formulate the dynamic VM management as a large-scale Markov decision process (MDP) problem and derive an optimal solution. Our analysis of real-world data traces supports our choice of the modeling approach. However, solving the large-scale MDP problem suffers from the curse of dimensionality. Therefore, we further exploit the special structure of the problem and propose an approximate MDP-based dynamic VM management method, called MadVM. We prove the convergence of MadVM and analyze the bound of its approximation error. Moreover, we show that MadVM can be implemented in a distributed system with at most two times of the optimal migration cost. Extensive simulations based on two real-world workload traces show that MadVM achieves significant performance gains over two existing baseline approaches in power consumption, resource shortage, and the number of VM migrations. Specifically, the more intensely the resource demands fluctuate, the more MadVM outperforms.

A coflow is a collection of related parallel flows that occur typically between two stages of a multi-stage computing task in a network, such as shuffle flows in MapReduce. The coflow abstraction allows applications to convey their semantics to the network so that application-level requirements can be better satisfied. In this paper, we study the routing and scheduling of multiple coflows to minimize the total weighted coflow completion time (CCT). We first propose a rounding-based randomized approximation algorithm, called OneCoflow, for single coflow routing and scheduling. The multiple coflow problem is more challenging as coexisting coflows will compete for the same network resources, such as link bandwidth. To minimize the total weighted CCT, we derive an online multiple coflow routing and scheduling algorithm, called OMCoflow. We then derive a competitive ratio bound of our problem and prove that the competitive ratio of OMCoflow is nearly tight. To the best of our knowledge, this is the first online algorithm with theoretical performance guarantees which considers routing and scheduling simultaneously for multi-coflows. Compared with existing methods, OMCoflow runs more efficiently and avoids frequently rerouting the flows. Extensive simulations on a Facebook data trace show that OMCoflow outperforms the state-of-the-art heuristic schemes significantly (e.g., reducing the total weighted CCT by up to 41.8% and the execution time by up to 99.2% against RAPIER).

Heterogeneous cellular networks (HetNets) can significantly improve the spectrum efficiency, where low-power low-complexity base stations (Pico-BSs) are deployed inside the coverage of macro base stations (Macro-BSs). Due to cross-tier interference, joint detection of the uplink signals is widely adopted so that a Pico-BS can either detect the uplink signals locally or forward them to the Macro-BS for processing. The latter can achieve increased throughput at the cost of additional backhaul transmission. However, in existing literature the delay of the backhaul links was often neglected. In this paper, we study the delay-optimal uplink scheduling problem in HetNets with limited backhaul capacity. Local signal detection or joint signal detection is scheduled in a unified delay-optimal framework. Specifically, we first prove that the problem is NP-hard and then formulate it as a Markov Decision Process problem. We propose an efficient and effective algorithm, called OLIUS, that can deal with the exponentially growing state and action spaces. Furthermore, OLIUS is online learning based which does not require any prior statistical knowledge on user behavior or channel characteristics. We prove the convergence of OLIUS and derive an upper bound on its approximation error. Extensive experiments in various scenarios show that our algorithm outperforms existing methods in reducing delay and power consumption.

Neighbor discovery is a fundamental step in constructing wireless sensor networks and many algorithms have been proposed aiming to minimize its latency. Recent developments of intelligent devices call for new algorithms, which are subject to energy restrictions. In energy-restricted large-scale networks, a node has limited power supply and can only discover other nodes that are within its range. Additionally, the discovery process may fail if excessive communications take place in a wireless channel. These factors make neighbor discovery a very challenging task and only a few of the proposed neighbor discovery algorithms can be applied to energy-restricted large-scale networks. In this paper, we propose Alano, a nearly optimal algorithm for a large-scale network, which uses the nodes' distribution as a key input. When nodes have the same energy constraint, we modify Alano by the Relaxed Difference Set (RDS), and present a Traversing Pointer (TP) based Alano when the nodes' energy constraints are different. We compare Alano with the state-of-the-art algorithms through extensive evaluations, and the results show that Alano achieves at least 31.35% lower discovery latency and has higher performance regarding quality (discovery rate) and scalability.

Cognitive Radio Network (CRN) is a promising technique for solving the wireless spectrum scarcity problem. Rendezvous is the fundamental process of CRNs. We aim at designing faster rendezvous algorithms for CRNs. We find that local information such as user's ID and the label of an available channel is very useful for designing faster rendezvous algorithms. First, we propose the Sequence-Rotating Rendezvous (SRR) algorithm. The SRR algorithm can guarantee rendezvous for any two users i and j in (2P²+ 2P) timeslots, where P is the least prime not less than the total number of channels in the network. Second, we utilize the user's identifier (ID) to design an ID-based Rendezvous (IDR) algorithm. The IDR algorithm can guarantee rendezvous for any two users i and j in (l + 1)(P_i + 2)(P_j + 2) timeslots, where Pi and Pj are the smallest primes which are not less than the numbers of available channels of users i and j respectively. Third, we propose a Channel-Label- based Rendezvous (CLR) algorithm which can guarantee rendezvous for any two usersin ((P_i+2) (P_j+2)+PN)(⌈log_2N⌉+1) timeslots, where N is the total number of channels in the network and P_N is the least prime which is not less than N. The theoretical Maximum Time To Rendezvous (MTTRs) of the three algorithms we propose are less than those of the state-of-the-art algorithms in the corresponding categories respectively in certain scenarios. All of our algorithms can be used in multi-user scenarios. We conduct a number of experiments to compare our algorithms with state- of-the-art rendezvous algorithms in different scenarios, the results of which confirm our theoretical analysis.

A typical shuffle operation randomly partitions data on many computers, generating possibly a significant amount of network traffic which often dominates a job's completion time. This traffic is particularly pronounced in iterative distributed operations where each iteration invokes a shuffle operation. We observe that data of different iterations are related according to the transformation logic of distributed operations. If data generated by the current iteration are partitioned to the computers where they will be processed in the next iteration, unnecessary shuffle network traffic between the two iterations can be prevented. We model general iterative distributed operations as the transform-and-shuffle primitive and define a powerful notion named Confluence key dependency to precisely capture the data relations in the primitive. We further find that by binding key partitions between different iterations based on the Confluence key dependency, the shuffle network traffic can always be reduced by a predictable percentage. We implemented the Confluence system. Confluence provides a simple interface for programmers to express the Confluence key dependency, based on which Confluence automatically generates efficient key partitioning schemes. Evaluation results on diverse real-life applications show that Confluence greatly reduces the shuffle network traffic, resulting in as much as 23 percent job completion time reduction.

Network function virtualization has emerged as a promising technology to enable rapid network service composition/innovation, energy conservation and cost minimization for network operators. To optimally operate a virtualized network service, it is of key importance to optimally deploy a VNF (virtualized network function) service chain within the provisioning infrastructure (e.g., servers and the network within a cloud datacenter), and dynamically scale it in response to flow traffic changes. Most of the existing work on VNF scaling assume access to precise network bandwidth information for placement decisions, while in reality, network bandwidth typically fluctuates following an unknown pattern and an effective way to adapt to it is to do trials. In this paper, we address dynamic VNF service chain deployment and scaling by a novel combination of an online provisioning algorithm and a multi-armed bandit optimization framework, which exploits online learning of the available bandwidths to enable optimal deployment of a scaled service chain. Specifically, we adopt the online algorithm to minimize the cost for provisioning VNF instances on the go, and a bandit-based online learning algorithm to place the VNF instances which minimizes the congestion in a datacenter network. We demonstrate effectiveness of our algorithms using solid theoretical analysis and trace-driven evaluation.

While virtualization helps to enable multi-tenancy in data centers, it introduces new challenges to the resource management in traditional OSes. We find that one important design in an OS, prioritizing interactive and I/O-bound workloads, can become ineffective in a virtualized OS. Resource multiplexing between multiple tenants breaks the assumption of continuous CPU availability in physical systems and causes two types of priority inversions in virtualized OSes. In this paper, we present xBalloon, a lightweight approach to preserving I/O prioritization. It uses a balloon process in the virtualized OS to avoid priority inversion in both short-term and long-term scheduling. Experiments in a local Xen environment and Amazon EC2 show that xBalloon improves I/O performance in a recent Linux kernel by as much as 136% on network throughput, 95% on disk throughput, and 125x on network tail latency.

In edge-cloud computing, a set of edge servers are deployed near the mobile devices such that these devices can offload jobs to the servers with low latency. One fundamental and critical problem in edge-cloud systems is how to dispatch and schedule the jobs so that the job response time (defined as the interval between the release of a job and the arrival of the computation result at its device) is minimized. In this paper, we propose a general model for this problem, where the jobs are generated in arbitrary order and times at the mobile devices and offloaded to servers with both upload and download delays. Our goal is to minimize the total weighted response time over all the jobs. The weight is set based on how latency sensitive the job is. We derive the first online job dispatching and scheduling algorithm in edge-clouds, called OnDisc, which is scalable in the speed augmentation model; that is, OnDisc is (1 + ε)-speed O(1/ε)-competitive for any constant ε ϵ (0,1). Moreover, OnDisc can be easily implemented in distributed systems. Extensive simulations on a real-world data-trace from Google show that OnDisc can reduce the total weighted response time dramatically compared with heuristic algorithms.

Network Function Virtualization (NFV) represents a new paradigm of network service provisioning. NFV providers acquire cloud resources, install virtual network functions (VNFs), assemble VNF service chains for customer usage, and dynamically scale VNF deployment against input traffic fluctuations. While existing literature on VNF scaling mostly adopts a reactive approach, we target a proactive approach that is more practical given the time overhead for VNF deployment. We aim to effectively estimate upcoming traffic rates and adjust VNF deployment a priori, for flow service quality assurance and resource cost minimization. We adapt online learning techniques for predicting future service chain workloads. We further combine the online learning method with a multi-timescale online optimization algorithm for VNF scaling, through minimization of the regret due to inaccurate demand prediction and minimization of the cost incurred by sub-optimal online decisions in a joint online optimization framework. The resulting proactive online VNF provisioning algorithm achieves a good performance guarantee, as shown by both theoretical analysis and simulation under realistic settings.

Motivated by practical scenarios, we study congestion games with failures. We investigate two models. The first model is congestion games with both resource and agent failures, where each agent chooses the same number of resources with the minimum expected cost. We prove that the game is potential and hence admits at least one pure-strategy Nash equilibrium (pure-NE). We also show that the Price of Anarchy and the Price of Stability are bounded (equal to 1 in some cases). The second model is congestion games with only resource failures (CG-CRF), where resources are provided in packages, and their failures can be correlated with each other. Each agent can choose multiple packages for reliability’s sake and utilize the survived one having the minimum cost. CG-CRF is shown to be not potential. We prove that it admits at least one pure-NE by constructing one efficiently. Finally, we discuss various applications of these two games in the networking field. To the best of our knowledge, this is the first paper studying congestion games with the coexistence of resource and agent failures, and we give also the first proof of the existence of a pure-NE in congestion games with correlated package failures.

With the recent advent of network functions virtualization (NFV), enterprises and businesses are looking into network service provisioning through the service chains of virtual network functions (VNFs), instead of relying on dedicated hardware middleboxes. Accompanying this trend, an NFV market is emerging, where NFV service providers create VNF instances, assemble VNF service chains, and sell them for the use of customers, using resources (computing, bandwidth) that they own or rent from other resource suppliers. Efficient service chain provisioning and pricing mechanisms are still missing, to charge assembled service chains according to demand and the supply of resources at any time. We propose an online stochastic auction mechanism for on-demand service chain provisioning and pricing at an NFV provider. Our auction takes in buy bids for service chains from multiple customers and sell bids from various resource suppliers to supplement the NFV provider's geo-distributed resource pool, with resource occupation/contribution durations. We extend online primal-dual optimization framework for handling both buyers and sellers, with a new competitive analysis. The online mechanism maximizes the expected social welfare of the NFV ecosystem (the NFV provider, customers and resource suppliers) with a good competitive ratio as compared with the expected offline optimal social welfare, while guaranteeing truthfulness in bidding, individual rationality for both buyers and sellers, and polynomial time for computation. We evaluate our mechanism through trace-driven simulation studies, and demonstrate a close-to-offline-optimal performance in expected social welfare under realistic settings.

As it has become the norm for cloud providers to host multiple datacenters around the globe, significant demands exist for inter-datacenter data transfers in large volumes, e.g., migration of big data. A challenge arises on how to schedule the bulk data transfers at different urgency levels, in order to fully utilize the available inter-datacenter bandwidth. The Software Defined Networking (SDN) paradigm has emerged recently which decouples the control plane from the data paths, enabling potential global optimization of data routing in a network. This paper aims to design a dynamic, highly efficient bulk data transfer service in a geo-distributed datacenter system, and engineer its design and solution algorithms closely within an SDN architecture. We model data transfer demands as delay tolerant migration requests with different finishing deadlines. Thanks to the flexibility provided by SDN, we enable dynamic, optimal routing of distinct chunks within each bulk data transfer (instead of treating each transfer as an infinite flow), which can be temporarily stored at intermediate datacenters to mitigate bandwidth contention with more urgent transfers. An optimal chunk routing optimization model is formulated to solve for the best chunk transfer schedules over time. To derive the optimal schedules in an online fashion, three algorithms are discussed, namely a bandwidth-reserving algorithm, a dynamically-adjusting algorithm, and a future-demand-friendly algorithm, targeting at different levels of optimality and scalability. We build an SDN system based on the Beacon platform and OpenFlow APIs, and carefully engineer our bulk data transfer algorithms in the system. Extensive real-world experiments are carried out to compare the three algorithms as well as those from the existing literature, in terms of routing optimality, computational delay and overhead.

This paper presents the first distributed algorithm to construct a spanner for arbitrary ad hoc networks under the physical signal-to-interference-and-noise-ratio (SINR) interference model. Spanner construction is one of the most important techniques for topology control in wireless networks, which intends to find a sparse topology in which only a small number of links need to be maintained, without substantially degrading the path connecting any pair of the nodes in the network. Due to the non-local property of interference, constructing a spanner is challenging under the SINR model, especially when a local distributed algorithm is desired. We meet this challenge by proposing an efficient randomized distributed algorithm that can construct a spanner in O(log n log Γ) timeslots with a high probability, where n is the total number of nodes and Γ describes the ratio of the maximum distance to the minimum distance between nodes. The constructed spanner concurrently satisfies two most desirable properties: constant stretch and linear sparseness. Our algorithm employs a novel maximal independent set (MIS) procedure as a subroutine, which is crucial in achieving the time efficiency of spanner construction. The MIS algorithm improves the best known result of O(log2n) [33] to O(log n) and is of independent interest as the algorithm is applicable also to many other applications. We conduct simulations to verify the proposed spanner construction algorithm, and the results show that our algorithm also performs well in realistic environments.

Auction design has recently been studied for dynamic resource bundling and virtual machine (VM) provisioning in IaaS clouds, but is mostly restricted to one-shot or offline setting. This paper targets a more realistic case of online VM auction design, where: 1) cloud users bid for resources into the future to assemble customized VMs with desired occupation durations, possibly located in different data centers; 2) the cloud provider dynamically packs multiple types of resources on heterogeneous physical machines (servers) into the requested VMs; 3) the operational costs of servers are considered in resource allocation; and 4) both social welfare and the cloud provider's net profit are to be maximized over the system running span. We design truthful, polynomial time auctions to achieve social welfare maximization and/or the provider's profit maximization with good competitive ratios. Our mechanisms consist of two main modules: 1) an online primal-dual optimization framework for VM allocation to maximize the social welfare with server costs, and for revealing the payments through the dual variables to guarantee truthfulness and 2) a randomized reduction algorithm to convert the social welfare maximizing auctions to ones that provide a maximal expected profit for the provider, with competitive ratios comparable to those for social welfare. We adopt a new application of Fenchel duality in our primal-dual framework, which provides richer structures for convex programs than the commonly used Lagrangian duality, and our optimization framework is general and expressive enough to handle various convex server cost functions. The efficacy of the online auctions is validated through careful theoretical analysis and trace-driven simulation studies.

Scalable locking is a key building block for scalable multi-threaded software. Its performance is especially critical in multi-socket, multi-core machines with non-uniform memory access (NUMA). Previous schemes such as in-place locks and delegation locks only perform well under a certain level of contention, and often require non-trivial tuning for a particular configuration. Besides, in large NUMA systems, current delegation locks cannot perform satisfactorily due to lack of optimized NUMA policies. In this work, we propose SANL, a locking scheme that can deliver high performance under various contention levels by adaptively switching between in-place locks and delegation locks. To optimize the performance of delegation locks, we introduce a new NUMA policy that jointly considers node distances and server utilization when choosing lock servers. We have implemented SANL and evaluated it with four popular multi-threaded applications (Memcached, Berkeley DB, Phoenix2 and SPLASH-2), on a 40-core Intel machine and a 64-core AMD machine. The comparison results with seven other representative locking schemes show that SANL outperforms them in most contention situations. For example, in one group test, SANL is 3.7 times faster than RCL lock and 17 times faster than POSIX mutex.

Network Function Virtualization (NFV) is a promising technology that promises to significantly reduce the operational costs of network services by deploying virtualized network functions (VNFs) to commodity servers in place of dedicated hardware middleboxes. The VNFs are typically running on virtual machine instances in a cloud infrastructure, where the virtualization technology enables dynamic provisioning of VNF instances, to process the fluctuating traffic that needs to go through the network functions in a network service. In this paper, we target dynamic provisioning of enterprise network services - expressed as one or multiple service chains - in cloud datacenters, and design efficient online algorithms without requiring any information on future traffic rates. The key is to decide the number of instances of each VNF type to provision at each time, taking into consideration the server resource capacities and traffic rates between adjacent VNFs in a service chain. In the case of a single service chain, we discover an elegant structure of the problem and design an efficient randomized algorithm achieving a e/(e-1) competitive ratio. For multiple concurrent service chains, an online heuristic algorithm is proposed, which is O(1)-competitive. We demonstrate the effectiveness of our algorithms using solid theoretical analysis and trace-driven simulations.

SMP virtual machines (VMs) have been deployed extensively in clouds to host multithreaded applications. A widely known problem is that when CPUs are oversubscribed, the scheduling delays due to VM preemption give rise to many performance problems because of the impact of these delays on thread synchronization and I/O efficiency. Dynamically changing the number of virtual CPUs (vCPUs) by considering the available physical CPU (pCPU) cycles has been shown to be a promising approach. Unfortunately, there are currently no efficient mechanisms to support such vCPU-level elasticity.

YARN is a popular cluster resource management platform. It does not, however, manage the network bandwidth resources which can significantly affect the execution performance of those tasks having large volumes of data to transfer within the cluster. The shuffle phase of MapReduce jobs features many such tasks. The impact of under utilization of the network bandwidth in shuffle tasks is more pronounced if the network bandwidth capacities of the nodes in the cluster are varied.

Efficient virtual machine (VM) management can dramatically reduce energy consumption in data centers. Existing VM management algorithms fall into two categories based on whether the VMs' resource demands are assumed to be static or dynamic. The former category fails to maximize the resource utilization as they cannot adapt to the dynamic nature of VMs' resource demands. Most approaches in the latter category are heuristical and lack theoretical performance guarantees. In this work, we formulate dynamic VM management as a large-scale Markov Decision Process (MDP) problem and derive an optimal solution. Our analysis of real-world data traces supports our choice of the modeling approach. However, solving the large-scale MDP problem suffers from the curse of dimensionality. Therefore, we further exploit the special structure of the problem and propose an approximate MDP-based dynamic VM management method, called MadVM. We prove the convergence of MadVM and analyze the bound of its approximation error. Moreover, MadVM can be implemented in a distributed system, which should suit the needs of real data centers. Extensive simulations based on two real-world workload traces show that MadVM achieves significant performance gains over two existing baseline approaches in power consumption, resource shortage and the number of VM migrations. Specifically, the more intensely the resource demands fluctuate, the more MadVM outperforms.

We study distributed algorithms for achieving efficient communications in the Rayleigh-fading Model. This model extends the popular deterministic SINR model using stochastic propagation to address fading effects observed in reality. Stochastic propagation greatly increases the difficulty of dealing with interference and collisions, especially in a local context without much global knowledge. We present a new technique called Inductive Coloring that can be used to schedule fast transmissions with Rayleigh-fading interference. The computation of inductive coloring takes only O(log2n) time with the proposed distributed algorithm, where n is the number of nodes in the network. We illustrate the power of inductive coloring by giving algorithms for implementing two basic communication primitives. The first primitive is Local Broadcast (LB), which can work in a MAC layer and has been widely studied in different interference models. The proposed algorithm for LB matches the fastest one under the simpler SINR model. The second primitive is Single-Reception (SR), which is to make each node receive at least one message from its neighbors. The proposed algorithm can implement SR in O(log2n) rounds. To illustrate the versatility of the SR primitive, we use the primitive to derive efficient algorithms for information broadcast and function computations. We conduct simulations to verify all the proposed algorithms, and the results show that the algorithms also perform well in realistic environments.

Social networks have been popular platforms for information propagation. An important use case is viral marketing: given a promotion budget, an advertiser can choose some influential users as the seed set and provide them free or discounted sample products; in this way, the advertiser hopes to increase the popularity of the product in the users' friend circles by the world-of-mouth effect, and thus maximizes the number of users that information of the production can reach. There has been a body of literature studying the influence maximization problem. Nevertheless, the existing studies mostly investigate the problem on a one-off basis, assuming fixed known influence probabilities among users, or the knowledge of the exact social network topology. In practice, the social network topology and the influence probabilities are typically unknown to the advertiser, which can be varying over time, i.e., in cases of newly established, strengthened or weakened social ties. In this paper, we focus on a dynamic non-stationary social network and design a randomized algorithm, RSB, based on multi-armed bandit optimization, to maximize influence propagation over time. The algorithm produces a sequence of online decisions and calibrates its explore-exploit strategy utilizing outcomes of previous decisions. It is rigorously proven to achieve an upper-bounded regret in reward and applicable to large-scale social networks. Practical effectiveness of the algorithm is evaluated using real-world datasets, which demonstrates that our algorithm outperforms previous stationary methods under non-stationary conditions.

4G/3G Networks have been widely deployed around the world to provide high wireless bandwidth for mobile users. However, the achievable 3G/4G bandwidth is still much lower than their theoretic maximum. Signal strengths and available backhaul capacities may vary significantly at different locations and times, often leading to unsatisfactory performance. Band-width aggregation, which uses multiple interfaces concurrently for data transfer, is a readily deployable solution. Specifically, Multi-Path TCP (MPTCP) has been advocated as a promising approach for leveraging multiple source-destination paths simultaneously in the transport layer. In this paper, we investigate the efficiency of an MPTCP-based bandwidth aggregation frame-work based on extensive measurements. In particular, we evaluate the gain for bandwidth aggregation across up to 4 cellular operators' networks, with respect to factors such as time, user location, data size, aggregation proxy location and congestion control algorithm. Our measurement studies reveal that (1) bandwidth aggregation in general improves the cellular network bandwidth experienced by mobile users, but the performance gain is significant only for bandwidth-intensive delay-tolerant flows, (2) the effectiveness of aggregation depends on many network factors, including QoS of individual cellular interfaces and the location of aggregation proxy, (3) contextual factors, including the time of day and the mobility of a user, also affect the aggregation performance.

A coflow is a collection of related parallel flows that occur typically between two stages of a multi-stage compute task in a network, such as shuffle flows in MapReduce. The coflow abstraction allows applications to convey their semantics to the network so that application-level requirements (e.g., minimizing the completion time of the slowest flow) can be better satisfied. In this paper, we study the routing and scheduling of multiple coflows to minimize the average coflow completion time (CCT). We first propose a rounding-based randomized approximation algorithm, called OneCoflow, for single coflow routing and scheduling. The multiple coflow problem is more challenging as coexisting coflows will compete for the same network resources such as link bandwidths. To minimize the average CCT, we derive an online multiple coflow routing and scheduling algorithm, called OMCoflow, and prove that it has a reasonably good competitive ratio. To the best of our knowledge, this is the first online algorithm with theoretical performance guarantees which considers routing and scheduling simultaneously for multi-coflows. Compared with existing methods, OMCoflow runs more efficiently, and it avoids the problem of frequently rerouting the flows. Extensive simulations on a Facebook data trace show that OMCoflow outperforms the state-of-the-art heuristic schemes significantly (e.g., reducing the average CCT by up to 41.8% and the execution time by up to 99.2% against RAPIER [28]).

Scalable locking is a key building block for scalable multi-threaded software. Its performance is especially critical in multi-socket, multi-core machines with non-uniform memory access (NUMA). Previous schemes such as local locking and remote locking only perform well under a certain level of contention, and often require non-trivial tuning for a particular configuration. Besides, for large NUMA systems, because of unmanaged lock server's nomination, current distance-first NUMA policies cannot perform satisfactorily.

Virtual machines (VMs) are widely adopted today to provide elastic computing services in datacenters, and they still heavily rely on TCP for congestion control. VM scheduling delays due to CPU sharing can cause frequent spurious retransmit timeouts (RTOs). Using current detection methods, we find that such spurious RTOs cannot be effectively identified because of the retransmission ambiguity caused by the delayed ACK (DelACK) mechanism. Disabling DelACK would add significant CPU overhead to the VMs and thus degrade the network's performance. In this paper, we first report our practical experience about TCP's reaction to VM scheduling delays. We then provide an analysis of the problem that has two components corresponding to VM preemption on the sender side and the receiver side, respectively. Finally, we propose PVTCP, a ParaVirtualized approach to counteract the distortion of congestion information caused by the hypervisor scheduler. PVTCP is completely embedded in the guest OS and requires no modification in the hypervisor. Taking incast congestion as an example, we evaluate our solution in a 21-node testbed. The results show that PVTCP has high adaptability in virtualized environments and deals satisfactorily with the throughput collapse problem.

By sharing resources among different cloud providers, the paradigm of federated clouds exploits temporal availability of resources and geographical diversity of operational costs for efficient job service. While interoperability issues across different cloud platforms in a cloud federation have been extensively studied, fundamental questions on cloud economics remain: When and how should a cloud trade resources (e.g., virtual machines) with others, such that its net profit is maximized over the long run, while a close-to-optimal social welfare in the entire federation can also be guaranteed? To answer this question, a number of important, interrelated decisions, including job scheduling, server provisioning, and resource pricing, should be dynamically and jointly made, while the long-term profit optimality is pursued. In this work, we design efficient algorithms for intercloud virtual machine (VM) trading and scheduling in a cloud federation. For VM transactions among clouds, we design a double-auction-based mechanism that is strategy-proof, individual-rational, ex-post budget-balanced, and efficient to execute over time. Closely combined with the auction mechanism is a dynamic VM trading and scheduling algorithm, which carefully decides the true valuations of VMs in the auction, optimally schedules stochastic job arrivals with different service level agreements (SLAs) onto the VMs, and judiciously turns on and off servers based on the current electricity prices. Through rigorous analysis, we show that each individual cloud, by carrying out the dynamic algorithm in the online double auction, can achieve a time-averaged profit arbitrarily close to the offline optimum. Asymptotic optimality in social welfare is also achieved under homogeneous cloud settings. We carry out simulations to verify the effectiveness of our algorithms, and examine the achievable social welfare under heterogeneous cloud settings, as driven by the real-world Google cluster usage traces.

Auction mechanisms have recently attracted substantial attention as an efficient approach to pricing and allocating resources in cloud computing. This work, to the authors' knowledge, represents the first online combinatorial auction designed for the cloud computing paradigm, which is general and expressive enough to both: 1) optimize system efficiency across the temporal domain instead of at an isolated time point; and 2) model dynamic provisioning of heterogeneous virtual machine (VM) types in practice. The final result is an online auction framework that is truthful, computationally efficient, and guarantees a competitive ratio ≈ 3.30 in social welfare in typical scenarios. The framework consists of three main steps: 1) a tailored primal-dual algorithm that decomposes the long-term optimization into a series of independent one-shot optimization problems, with a small additive loss in competitive ratio; 2) a randomized subframework that applies primal-dual optimization for translating a centralized cooperative social welfare approximation algorithm into an auction mechanism, retaining the competitive ratio while adding truthfulness; and 3) a primal-dual algorithm for approximating the one-shot optimization with a ratio close to e. We also propose two extensions: 1) a binary search algorithm that improves the average-case performance; 2) an improvement to the online auction framework when a minimum budget spending fraction is guaranteed, which produces a better competitive ratio. The efficacy of the online auction framework is validated through theoretical analysis and trace-driven simulation studies. We are also in the hope that the framework can be instructive in auction design for other related problems.

Cloud computing increasingly leverages SMP virtual machines (VMs) to host multi-threaded applications. Interrupt balancing as a problem becomes more challenging because VMs are subject to the hypervisor's scheduling. Since the scheduling delays are typically tens of milliseconds, when they are added to one VM's interrupt delivery, they can seriously degrade the VM's I/O performance. Traditional balancing techniques are designed for dedicated environments, which cannot work well in virtualized environments because VMs are disallowed to directly control the hardware in many cases. In this paper, we present hBalance, a very simple approach to offload interrupt load balancing from SMP-VMs to the hypervisor. To accelerate the interrupt processing, our approach does not require shortening the hypervisor's scheduling time slice, but dynamically redirects interrupts from preempted virtual CPUs to running ones in a balanced manner. hBalance supports both Fully Virtualiized (FV) guests and Para-Virtualized (PV) guests, and exhibits high portability among various hypervisors. With our prototype implementation in Xen, the experimental results with both micro-level and application-level benchmarks show that hBalance significantly improves SMP-VMs' I/O performance while introduces moderate overhead.

Controlling a dynamic network is interesting and important in practical applications, which is to drive the network from any initial state to any desired state. Much research has been conducted in revealing the controllability and seeking the underlying correlations of the network. However, no existing works have considered the time needed to control the network, which we refer to as control latency. In this paper, we initiate the study of control latency of dynamic networks. First of all, we formulate the minimum control latency (MCL) problem for designing the controlling pattern with minimum number of controllers. We show that the MCL problem is NP-hard by reducing the multiprocessor scheduling problem to it. Then, we propose a greedy algorithm for designing a controlling pattern that can control the network within two times the minimum control latency. Moreover, when the control latency is bounded by a given value, we propose another constant approximation algorithm to design a controlling pattern which uses at most three times the minimum number of controllers. We conduct extensive simulations on both synthetic and real networks to corroborate our theoretic analysis.

Cognitive radio networks (CRNs) have been proposed to solve the spectrum scarcity problem. One of their fundamental procedures is to construct a communication link on a common channel for the users, which is referred as rendezvous. In reality, the capability to sense the spectrum may vary from user to user, and such users form what is known as a heterogeneous cognitive radio network (HCRN). The licensed spectrum is divided in to n channels, U = {1, 2,..., n}. We denote the capability of user i as Ci⊆ U and the set of available channels (i.e. the channels not occupied by the paying users) as Vi⊆ Ci. We study the rendezvous problem in HCRN under two circumstances: fully available spectrum (Vi= Ci) and partially available spectrum (Vi≠ Ci). For any two users a, b, we propose the Traversing Pointer (TP) algorithm that guarantees rendezvous in O(max{|Ca|,|Cb|}log log n) time slots for the fully available spectrum scenario. This result is only O (log log n) larger than our constructive lower bound. Moreover, it removes an O(min{|Ca|, |Cb|}) factor as compared to the state-of-the-art result (O(|Ca||Cb|) in [26]). For the partially available spectrum scenario, we propose the Moving Traversing Pointers (MTP) algorithm to guarantee rendezvous in O((max{|Va|, |Vb|})2log log n) time slots, which works more efficiently than the previous best result (O(|Ca||Cb|) in [25]) in various circumstances. We also conduct extensive simulations and the results corroborate our analysis.

This paper initiates the study of distributed information exchange in multi-channel wireless ad hoc networks. Information exchange is a basic operation in which each node of the network sends an information packet to other nodes within a specific distance R. Our study is motivated by the increasing presence and popularity of wireless networks and devices that operate on multiple channels. Consequently, there is a need for a better understanding of how and by how much multiple channels can improve communication. Based on the SINR interference model, we propose a multi-channel network model which incorporates certain features commonly seen in wireless ad hoc networks, including asynchrony, little non-local knowledge, limited message size, and limited power control. We then present a randomized algorithm that can accomplish information exchange in O ((Δ/F + Δlog n/P) log n + log Δ log n) timeslots with high probability, where n is the number of nodes in the network, Δ is the maximum number of nodes within the range R, F is the number of available channels and P is the maximum number of packets that can fit in a message. Our algorithm significantly surpasses the best known results in single-channel networks, achieving a Θ(F) times speedup if Δ and P are sufficiently large. We conducted empirical studies that confirmed the performance of the proposed algorithm as derived in the analysis.

On-demand resource provisioning in cloud computing provides tailor-made resource packages (typically in the form of VMs) to meet users' demands. Public clouds nowadays provide more and more elaborated types of VMs, but have yet to offer the most flexible dynamic VM assembly, which is partly due to the lack of a mature mechanism for pricing tailor-made VMs on the spot. This work proposes an efficient randomized auction mechanism based on a novel application of smoothed analysis and randomized reduction, for dynamic VM provisioning and pricing in geo-distributed cloud data centers. This auction, to the best of our knowledge, is the first one in literature that achieves (i) truthfulness in expectation, (ii) polynomial running time in expectation, and (iii) (1 − ε)-optimal social welfare in expectation for resource allocation, where e can be arbitrarily close to 0. Our mechanism consists of three modules: (1) an exact algorithm to solve the NP-hard social welfare maximization problem, which runs in polynomial time in expectation, (2) a perturbation-based randomized resource allocation scheme which produces a VM provisioning solution that is (1 − ε)-optimal and (3) an auction mechanism that applies the perturbation-based scheme for dynamic VM provisioning and prices the customized VMs using a randomized VCG payment, with a guarantee in truthfulness in expectation. We validate the efficacy of the mechanism through careful theoretical analysis and trace-driven simulations.1

Hadoop version 1 (HadoopV1) and version 2 (YARN) manage the resources in a distributed system in different ways. HadoopV1 executes MapReduce tasks in working slots that are statically configured, YARN uses a set of task containers to encapsulate its memory and CPU resources. However, neither of them considers the runtime performance of the cluster when deciding the proper number of concurrent tasks to run on each node to achieve the optimal throughput. In order to gain higher performance, the users of Hadoop usually need to use their experience to carefully configure the resources of the cluster and the resources needed by their jobs. But as the workload is typically always changing in the cluster, rarely could such a manual configuration lead to optimized performance. In this paper, we study the MapReduce job performance in HadoopV1 and YARN with different resource configurations, and model the cluster throughput in terms of the resource capacity of the cluster. We propose SMapReduce, which can dynamically manage a proper number of concurrent tasks running on each node. SMapReduce can gain the maximum job throughput by considering the thrashing phenomenon and the balancing between map and reduce tasks. Evaluation results show that SMapReduce can yield significant performance speedup comparing to both HadoopV1 and YARN for various MapReduce workloads.

Cloud-based content delivery networks (Cloud CDN) cache and deliver contents from geo-distributed cloud data centers to end users across the globe, exploiting "infinite" on-demand cloud resources to address volatile user demands. It is critically important to efficiently manage cloud resources in different locations over time, for minimization of the operational cost of the CDN provider, while delivering short response delay to user requests. Although many have studied cost-aware replica placement and request redirection in CDN systems, most are restricted to an offline or one-time setting, or resort to greedy heuristics for online operation. This work proposes an efficient online algorithm for dynamic content replication and request dispatching in cloud CDNs operating over a long time span, targeting overall cost minimization with performance guarantees. Our online algorithm consists of two main modules: (1) a regularization method from the online learning literature to convert the offline cost-minimization optimization problem into a sequence of regularized problems, each to be efficiently solvable in one time slot; (2) a randomized approach to convert the optimal fractional solutions from the regularized problems to integer solutions of the original problem, achieving a good competitive ratio. The effectiveness of our online algorithm is validated through solid theoretical analysis and trace-driven simulations.

Auction design has recently been studied for dynamic resource bundling and VM provisioning in IaaS clouds, but is mostly restricted to the one-shot or offline setting. This work targets a more realistic case of online VM auction design, where: (i) cloud users bid for resources into the future to assemble customized VMs with desired occupation durations; (ii) the cloud provider dynamically packs multiple types of resources on heterogeneous physical machines (servers) into the requested VMs; (iii) the operational costs of servers are considered in resource allocation; (iv) both social welfare and the cloud provider's net profit are to be maximized over the system running span. We design truthful, polynomial time auctions to achieve social welfare maximization and/or the provider's profit maximization with good competitive ratios. Our mechanisms consist of two main modules: (1) an online primal-dual optimization framework for VM allocation to maximize the social welfare with server costs, and for revealing the payments through the dual variables to guarantee truthfulness; and (2) a randomized reduction algorithm to convert the social welfare maximizing auctions to ones that provide a maximal expected profit for the provider, with competitive ratios comparable to those for social welfare. We adopt a new application of Fenchel duality in our primal-dual framework, which provides richer structures for convex programs than the commonly used Lagrangian duality, and our optimization framework is general and expressive enough to handle various convex server cost functions. The efficacy of the online auctions is validated through careful theoretical analysis and trace-driven simulation studies.

In Hybrid networks, which synergistically mix together wired and wireless links to achieve flexible and reliable communication, it is particularly challenging to routing selfish tasks since each task wish to finish transmission as early as possible and its decision could have impacts on the others. In this paper, we investigate the problem to route a given set of selfish tasks in hybrid networks. Under a unified cost model, the competitive behaviors of selfish players are modeled as a noncooperative game. We show the game is ordinal potential, and the existence of a pure-Nash Equilibrium (pure-NE) is therefore guaranteed. We also design a routing scheme, called Selfish Task-Driven Routing (STaR), to achieve a pure-NE. Extensive simulations show that our scheme can not only efficiently converge to an equilibrium but also outperform other source routing protocols regarding the completion time and load balancing.

Federation of geo-distributed cloud services is a trend in cloud computing that, by spanning multiple data centers at different geographical locations, can provide a cloud platform with much larger capacities. Such a geo-distributed cloud is ideal for supporting large-scale social media applications with dynamic contents and demands. Although promising, its realization presents challenges on how to efficiently store and migrate contents among different cloud sites and how to distribute user requests to the appropriate sites for timely responses at modest costs. These challenges escalate when we consider the persistently increasing contents and volatile user behaviors in a social media application. By exploiting social influences among users, this paper proposes efficient proactive algorithms for dynamic, optimal scaling of a social media application in a geo-distributed cloud. Our key contribution is an online content migration and request distribution algorithm with the following features: 1) future demand prediction by novelly characterizing social influences among the users in a simple but effective epidemic model; 2) one-shot optimal content migration and request distribution based on efficient optimization algorithms to address the predicted demand; and 3) a Δ(t)-step look-ahead mechanism to adjust the one-shot optimization results toward the offline optimum. We verify the effectiveness of our online algorithm by solid theoretical analysis, as well as thorough comparisons to ready algorithms including the ideal offline optimum, using large-scale experiments with dynamic realistic settings on Amazon Elastic Compute Cloud (EC2).

With the recent advent of cloud computing technologies, a growing number of content distribution applications are contemplating a switch to cloud-based services, for better scalability and lower cost. Two key tasks are involved for such a move: to migrate the contents to cloud storage, and to distribute the Web service load to cloud-based Web services. The main issue is to best utilize the cloud as well as the application provider's existing private cloud, to serve volatile requests with service response time guarantee at all times, while incurring the minimum operational cost. While it may not be too difficult to design a simple heuristic, proposing one with guaranteed cost optimality over a long run of the system constitutes an intimidating challenge. Employing Lyapunov optimization techniques, we design a dynamic control algorithm to optimally place contents and dispatch requests in a hybrid cloud infrastructure spanning geo-distributed data centers, which minimizes overall operational cost overtime, subject to service response time constraints. Rigorous analysis shows that the algorithm nicely bounds the response times within the preset QoS target, and guarantees that the overall cost is within a small constant gap from the optimum achieved by a T-slot lookahead mechanism with known future information. We verify the performance of our dynamic algorithm with prototype-based evaluation.

More and more enterprises have set up their own private clouds by applying virtualization to their data centers, the benefit is flexible resource supply to different internal demands. Aiming to meet the peak demand in their resource provisioning, private clouds are often under-utilized. A new paradigm has emerged that advocates leasing the spare resources to external users, when and if adequate rental prices are offered. A broker is typically employed which pools the spare resources of multiple private clouds together and leases them to serve external users' jobs. Good mechanisms have yet to be derived for the broker to set the offered prices to buy spare resources from the private clouds, and to schedule jobs on the available resources, such that the economic benefits of both the broker and the private clouds are maximized. The design of the mechanism is especially challenging when we consider the dynamic arrival of users' jobs and volatile availability of spare resources at the private clouds, while aiming at long-term profit optimality. In this paper, we model the interaction between the broker and the private clouds as a two-stage Stackelberg game. As the leader in the game, the broker decides and offers prices for renting VMs of different types from each private cloud. As a follower, each private cloud responds with the number of VMs of each type that it is willing to lease. By combining with the Stackelberg game model we design online algorithms for the broker to set the prices and schedule jobs on the private clouds, and for the private cloud to decide the numbers of VMs to lease, based on the Lyapunov optimization theory. We prove that the broker achieves a time-averaged profit that is close to the offline optimum with complete information on future job arrivals and resource availability, while each private cloud makes their best earning. The proposed online algorithm is carefully evaluated based on usage traces of Google cluster and Amazon EC2.

Cloud providers often choose to operate datacenters over a large geographic span, in order that users may be served by resources in their proximity. Due to time and spatial diversities in utility prices and operational costs, different datacenters typically have disparate charges for the same services. Cloud users are free to choose the datacenters to run their jobs, based on a joint consideration of monetary charges and quality of service. A fundamental problem with significant economic implications is how the cloud should price its datacenter resources at different locations, such that its overall profit is maximized. The challenge escalates when dynamic resource pricing is allowed and long-term profit maximization is pursued. We design an efficient online algorithm for dynamic pricing of VM resources across datacenters in a geo-distributed cloud, together with job scheduling and server provisioning in each datacenter, to maximize the profit of the cloud provider over a long run. Theoretical analysis shows that our algorithm can schedule jobs within their respective deadlines, while achieving a time-average overall profit closely approaching the offline maximum, which is computed by assuming that perfect information on future job arrivals are freely available. Empirical studies further verify the efficacy of our online profit maximizing algorithm.

Auction mechanisms have recently attracted substantial attention as an efficient approach to pricing and resource allocation in cloud computing. This work, to the authors' knowledge, represents the first online combinatorial auction designed in the cloud computing paradigm, which is general and expressive enough to both (a) optimize system efficiency across the temporal domain instead of at an isolated time point, and (b) model dynamic provisioning of heterogeneous Virtual Machine (VM) types in practice. The final result is an online auction framework that is truthful, computationally efficient, and guarantees a competitive ratio ~ e+ 1 over e-1 ~ 3.30 in social welfare in typical scenarios. The framework consists of three main steps: (1) a tailored primal-dual algorithm that decomposes the long-term optimization into a series of independent one-shot optimization problems, with an additive loss of 1 over e-1 in competitive ratio, (2) a randomized auction sub-framework that applies primal-dual optimization for translating a centralized co-operative social welfare approximation algorithm into an auction mechanism, retaining a similar approximation ratio while adding truthfulness, and (3) a primal-dual update plus dual fitting algorithm for approximating the one-shot optimization with a ratio λ close to e. The efficacy of the online auction framework is validated through theoretical analysis and trace-driven simulation studies. We are also in the hope that the framework, as well as its three independent modules, can be instructive in auction design for other related problems.

While modern datacenters are increasingly adopting virtual machines (VMs) to provide elastic cloud services, they still rely on traditional TCP for congestion control. In virtualized datacenters, TCP endpoints are separated by a virtualization layer and subject to the intervention of the hypervisor's scheduling. Most previous attempts focused on tuning the hypervisor layer to try to improve the VMs' I/O performance, and there is very little work on how a VM's guest OS may help the transport layer to adapt to the virtualized environment. In this paper, we find that VM scheduling delays can heavily contaminate RTTs as sensed by VM senders, preventing TCP from correctly learning the physical network condition. After giving an account of the source of the problem, we propose PVTCP, a ParaVirtualized TCP to counter the distorted congestion information caused by VM scheduling on the sender side. PVTCP is self-contained, requiring no modification to the hypervisor. Experiments show that PVTCP is much more effective in addressing incast congestion in virtualized datacenters than standard TCP.

Gathering information in a sensing field of interest is a fundamental task in wireless sensor networks. Current methods either use multihop forwarding to the sink via stationary nodes or use mobile sinks to traverse the sensing field. The multihop forwarding method intrinsically has the energy hole problem and the mobile sinks method has a large gathering latency due to its low mobility velocity. In addition, all the mobile sinks methods assume unlimited power supply and memory which is unrealistic in practice. In this paper, we propose a new approach for information gathering through a Mobile Aerial Sensor Network (MASN). We adopt the Hive-Drone model [5] where a centralized station (Hive) responsible for serving and recharging Micro-Aerial Vehicle (MAV) sensor nodes (Drones) is strategically placed in the sensing field. We then face the challenges of how to control the mobility of each MAV and devising interference-free scheduling for wireless transmissions that can substantially reduce the latency. We present a family of algorithms with constant memory to reduce both gathering latency, which is the duration from dispatching the MAVs to the moment when all the sensed information are gathered at the central station, and information latency, which is the duration from when some information is sensed to when it is received by the station. We also consider how to extend the single Hive to multiple Hives for monitoring an arbitrarily large area. Extensive simulation results corroborate our theoretical analysis.

The emerging federated cloud paradigm advocates sharing of resources among cloud providers, to exploit temporal availability of resources and diversity of operational costs for job serving. While extensive studies exist on enabling interoperability across different cloud platforms, a fundamental question on cloud economics remains unanswered: When and how should a cloud trade VMs with others, such that its net profit is maximized over the long run? In order to answer this question by the federation, a number of important, correlated decisions, including job scheduling, server provisioning and resource pricing, need to be dynamically made, with long-term profit optimality being a goal. In this work, we design efficient algorithms for inter-cloud resource trading and scheduling in a federation of geo-distributed clouds. For VM trading among clouds, we apply a double auction-based mechanism that is strategy proof, individual rational, and ex-post budget balanced. Coupling with the auction mechanism is an efficient, dynamic resource trading and scheduling algorithm, which carefully decides the true valuations of VMs in the auction, optimally schedules stochastic job arrivals with different SLAs onto the VMs, and judiciously turns on and off servers based on the current electricity prices. Through rigorous analysis, we show that each individual cloud, by carrying out our dynamic algorithm, can achieve a time-averaged profit arbitrarily close to the offline optimum.

In a cognitive radio system, licensed primary users can lease idle spectrum to secondary users for monetary remuneration. Secondary users acquire available spectrum for their data delivery needs, with the goal of achieving high throughput and low spectrum charges. Maximizing such a net utility (throughput utility minus spectrum cost) is a central problem faced by a multihop secondary network. Optimal decision making is challenging, since it involves multiple data flows, cross-layer coordination, and economic constraints (budgets of sources). The picture is further complicated by the inter-play between secondary data communication and primary spectrum leasing mechanisms. This work is the first to investigate the full spectrum of socially optimal secondary user communication. We design a social welfare maximization framework for multi-session multi-hop secondary data dissemination based on Lyapunov optimization techniques. A salient feature of the framework is that it takes any given primary user mechanism as input, and produces correspondingly a dynamic, distributed rate control, routing, and spectrum allocation and pricing protocol that can achieve longterm maximization of the overall system utility. Through rigorous theoretical analysis, we prove that our online protocol can achieve a social welfare that is arbitrarily close to the offline optimum, with only finite buffer space requirement at each secondary user, and guarantee of no buffer overflow. Empirical studies are conducted to examine the performance of the protocol.

Multiple-message broadcast is a generalization of the traditional broadcast problem. It is to disseminate k distinct (1 ≤ k ≤ n) messages stored at k arbitrary nodes to the entire network with the fewest timeslots. In this paper, we study this basic communication primitive in unstructured wireless networks under the physical interference model (also known as the SINR model). The unstructured wireless network assumes unknown network topology, no collision detection and asynchronous communications. Our proposed randomized distributed algorithm can accomplish multiple-message broadcast in O((D + k) log n + log2n) timeslots with high probability, where D is the network diameter and n is the number of nodes in the network. To our best knowledge, this work is the first one to consider distributively implementing multiple-message broadcasting in unstructured wireless networks under a global interference model, which may shed some light on how to efficiently solve in general a “global” problem in a “local” fashion with “global” interference constraints in asynchronous wireless ad hoc networks. Apart from the algorithm, we also show an Ω(D+k+log n) lower bound for randomized distributed multiple message broadcast algorithms under the assumed network model.

Cloud computing, rapidly emerging as a new computation paradigm, provides agile and scalable resource access in a utility-like fashion, especially for the processing of big data. An important open issue here is how to efficiently move the data, from different geographical locations over time, into a cloud for effective processing. The de facto approach of hard drive shipping is not flexible, nor secure. This work studies timely, cost-minimizing upload of massive, dynamically-generated, geodispersed data into the cloud, for processing using a MapReducelike framework. Targeting at a cloud encompassing disparate data centers, we model a cost-minimizing data migration problem, and propose two online algorithms, for optimizing at any given time the choice of the data center for data aggregation and processing, as well as the routes for transmitting data there. The first is an online lazy migration (OLM) algorithm achieving a competitive ratio of as low as 2.55, under typical system settings. The second is a randomized fixed horizon control (RFHC) algorithm achieving a competitive ratio of 1+ 1/l+λ κ/λ with a lookahead window of l, where κ and λ are system parameters of similar magnitude.

MapReduce has become the dominant programming model for processing massive amounts of data on cloud platforms. More and more enterprises are now utilizing hybrid clouds, consisting of private infrastructure owned by themselves and public clouds such as Amazon EC2, to process their spiky MapReduce workloads, which fully utilize their own on-premise resources while outsourcing the tasks only when needed. With disparate workloads of different MapReduce tasks, an efficient scheduling mechanism is in need to enable efficient utilization of the on-premise resources and to minimize the task outsourcing cost, while meeting the task completion time requirements as well. In this paper, a fine-grained model is described to characterize the scheduling of heterogeneous MapReduce workloads, and an online algorithm is proposed for joint task admission control into the private cloud, task outsourcing to the public cloud, and VM allocation to execute the admitted tasks on the private cloud, such that the time-averaged task outsourcing cost is minimized over the long run. The online algorithm features preemptive scheduling of the tasks, where a task executed partially on the on-premise infrastructure can be paused and scheduled to run later. It also achieves desirable properties such as meeting a pre-set task admission ratio and bounding the worst-case task completion time, as proven by our rigorous theoretical analysis.

Rendezvous is a fundamental process in Cognitive Radio Networks, through which a user establishes a link to communicate with a neighbor on a common channel. Most previous solutions use either a central controller or a Common Control Channel (CCC) to simplify the problem, which are inflexible and vulnerable to faults and attacks. Some blind rendezvous algorithms have been proposed that rely on no centralization. Channel Hopping (CH) is a representative technique used in blind rendezvous, with which each user hops among the available channels according to a pre-defined sequence. However, no existing algorithms can work efficiently for both symmetric (both parties have the same set of channels) and asymmetric users. In this paper, we introduce a new notion called Disjoint Relaxed Difference Set (DRDS) and present a linear time constant approximation algorithm for its construction. Then based on the DRDS, we propose a distributed asynchronous algorithm that can achieve and guarantee fast rendezvous for both symmetric and asymmetric users. We also derive a lower bound for any algorithm using the CH technique. This lower bound shows that our proposed DRDS based distributed rendezvous algorithm is nearly optimal. Extensive simulation results corroborate our theoretical analysis.

Cloud computing, rapidly emerging as a new computation paradigm, provides agile and scalable resource access in a utility-like fashion, especially for the processing of big data. An important open issue here is to efficiently move the data, from different geographical locations over time, into a cloud for effective processing. The de facto approach of hard drive shipping is not flexible or secure. This work studies timely, cost-minimizing upload of massive, dynamically-generated, geo-dispersed data into the cloud, for processing using a MapReduce-like framework. Targeting at a cloud encompassing disparate data centers, we model a cost-minimizing data migration problem, and propose two online algorithms: an online lazy migration (OLM) algorithm and a randomized fixed horizon control (RFHC) algorithm , for optimizing at any given time the choice of the data center for data aggregation and processing, as well as the routes for transmitting data there. Careful comparisons among these online and offline algorithms in realistic settings are conducted through extensive experiments, which demonstrate close-to-offline-optimum performance of the online algorithms.

The rapidly increasing power of personal mobile devices (smartphones, tablets, etc.) is providing much richer contents and social interactions to users on the move. This trend however is throttled by the limited battery lifetime of mobile devices and unstable wireless connectivity, making the highest possible quality of service experienced by mobile users not feasible. The recent cloud computing technology, with its rich resources to compensate for the limitations of mobile devices and connections, can potentially provide an ideal platform to support the desired mobile services. Tough challenges arise on how to effectively exploit cloud resources to facilitate mobile services, especially those with stringent interaction delay requirements. In this paper, we propose the design of a Cloud-based, novel Mobile sOcial tV system (CloudMoV). The system effectively utilizes both PaaS (Platform-as-a-Service) and IaaS (Infrastructure-as-a-Service) cloud services to offer the living-room experience of video watching to a group of disparate mobile users who can interact socially while sharing the video. To guarantee good streaming quality as experienced by the mobile users with time-varying wireless connectivity, we employ a surrogate for each user in the IaaS cloud for video downloading and social exchanges on behalf of the user. The surrogate performs efficient stream transcoding that matches the current connectivity quality of the mobile user. Given the battery life as a key performance bottleneck, we advocate the use of burst transmission from the surrogates to the mobile users, and carefully decide the burst size which can lead to high energy efficiency and streaming quality. Social interactions among the users, in terms of spontaneous textual exchanges, are effectively achieved by efficient designs of data storage with BigTable and dynamic handling of large volumes of concurrent messages in a typical PaaS cloud. These various designs for flexible transcoding capabilities, battery efficiency of mobile devices and spontaneous social interactivity together provide an ideal platform for mobile social TV services. We have implemented CloudMoV on Amazon EC2 and Google App Engine and verified its superior performance based on real-world experiments.

Minimizing latency and energy consumption is the prime objective of the design of data aggregation in battery-powered wireless networks. A tradeoff exists between the aggregation latency and the energy consumption, which has been widely studied under the protocol interference model. There has been, however, no investigation of the tradeoff under the physical interference model that is known to capture more accurately the characteristics of wireless interferences. When coupled with the technique of successive interference cancellation, by which a receiver may recover signals from multiple simultaneous senders, the model can lead to much reduced latency but increased energy usage. In this paper, we investigate the latency-energy tradeoff for data aggregation in wireless sensor networks under the physical interference model and using successive interference cancellation. We present theoretical lower bounds on both latency and energy as well as their tradeoff, and give an efficient approximation algorithm that can achieve the asymptotical optimum in both aggregation latency and latency-energy tradeoff. We show that our algorithm can significantly reduce the aggregation latency, for which the energy consumption is kept at its lowest possible level.

The unstructured multi-hop radio network model, with asynchronous wake-up, no collision detection and little knowledge on the network topology, is proposed for capturing the particularly harsh characteristics of initially deployed wireless adhoc and sensor networks. In this paper, assuming such a practical model, we study a fundamental problem of both theoretical and practical interests--the local broadcasting problem. Given a set of nodes V where each node wants to broadcast a message to all its neighbors that are within a certain local broadcasting range R, the problem is to schedule all these requests in the fewest timeslots. By adopting the physical interference mode land without any knowledge on neighborhood, we give a new randomized distributed approximation algorithm for the local broadcasting problem with approximation ratio O (log n) where nis the number of nodes. This distributed approximation algorithm improves the state-of-the-art result in [22] by a logarithmic factor.

Multicast supporting non-uniform receiving rates is an effective means of data dissemination to receivers with diversified bandwidth availability. Designing efficient rate control, routing and capacity allocation to achieve optimal multirate multicast has been a difficult problem in fixed wireline networks, let alone wireless networks with random channel fading and volatile node mobility. The challenge escalates if we consider also the selfishness of users who prefer to relay data for others with strong social ties. Such social selfishness of users is a new constraint in network protocol design. Its impact on efficient multicast in wireless networks has yet to be explored especially when multiple receiving rates are allowed. In this paper, we design an efficient, social-aware multirate multicast scheme that can maximize the overall utility of socially selfish users in a wireless network, and its distributed implementation. We model social preferences of users as differentiated costs for packet relay, which are weighted by the strength of social tie between the relay and the destination. Stochastic Lyapunov optimization techniques are utilized to design optimal scheduling of multicast transmissions, which are combined with multi-resolution coding and random linear network coding. With rigorous theoretical analysis, we study the optimality, stability, and complexity of our algorithm, as well as the impact of social preferences. Empirical studies further confirm the superiority of our algorithm under different social selfishness patterns.

The recent advent of cloud computing technologies has enabled agile and scalable resource access for a variety of applications. Content distribution services are a major category of popular Internet applications. A growing number of content providers are contemplating a switch to cloud-based services, for better scalability and lower cost. Two key tasks are involved for such a move: to migrate their contents to cloud storage, and to distribute their web service load to cloud-based web services. The main challenge is to make the best use of the cloud as well as their existing on-premise server infrastructure, to serve volatile content requests with service response time guarantee at all times, while incurring the minimum operational cost. Employing Lyapunov optimization techniques, we present an optimization framework for dynamic, cost-minimizing migration of content distribution services into a hybrid cloud infrastructure that spans geographically distributed data centers. A dynamic control algorithm is designed, which optimally places contents and dispatches requests in different data centers to minimize overall operational cost over time, subject to service response time constraints. Rigorous analysis shows that the algorithm nicely bounds the response times within the preset QoS target in cases of arbitrary request arrival patterns, and guarantees that the overall cost is within a small constant gap from the optimum achieved by a T-slot lookahead mechanism with known information into the future.

Federation of geo-distributed cloud services is a trend in cloud computing which, by spanning multiple data centers at different geographical locations, can provide a cloud platform with much larger capacities. Such a geo-distributed cloud is ideal for supporting large-scale social media streaming applications (e.g., YouTube-like sites) with dynamic contents and demands, owing to its abundant on-demand storage/bandwidth capacities and geographical proximity to different groups of users. Although promising, its realization presents challenges on how to efficiently store and migrate contents among different cloud sites (i.e. data centers), and to distribute user requests to the appropriate sites for timely responses at modest costs. These challenges escalate when we consider the persistently increasing contents and volatile user behaviors in a social media application. By exploiting social influences among users, this paper proposes efficient proactive algorithms for dynamic, optimal scaling of a social media application in a geo-distributed cloud. Our key contribution is an online content migration and request distribution algorithm with the following features: (1) future demand prediction by novelly characterizing social influences among the users in a simple but effective epidemic model; (2) oneshot optimal content migration and request distribution based on efficient optimization algorithms to address the predicted demand, and (3) a Δ(t)-step look-ahead mechanism to adjust the one-shot optimization results towards the offline optimum. We verify the effectiveness of our algorithm using solid theoretical analysis, as well as large-scale experiments under dynamic realistic settings on a home-built cloud platform.

Real-world large-scale Peer-to-Peer (P2P) Video-on-Demand (VoD) streaming applications face more design challenges as compared to P2P live streaming, due to higher peer dynamics and less buffer overlap. The situation is further complicated when we consider the selfish nature of peers, who in general wish to download more and upload less, unless otherwise motivated. Taking a new perspective of distributed dynamic auctions, we design efficient P2P VoD streaming algorithms with simultaneous consideration of peer incentives and streaming optimality. In our solution, media block exchanges among peers are carried out through local auctions, in which budget-constrained peers bid for desired blocks from their neighbors, which in turn deliver blocks to the winning bidders and collect revenue. With strategic design of a discriminative second price auction with seller reservation, a supplying peer has full incentive to maximally contribute its bandwidth to increase its budget; requesting peers are also motivated to bid in such a way that optimal media block scheduling is achieved effectively in a fully decentralized fashion. Applying techniques from convex optimization and mechanism design, we prove (a) the incentive compatibility at the selling and buying peers, and (b) the optimality of the induced media block scheduling in terms of social welfare maximization. Large-scale empirical studies are conducted to investigate the behavior of the proposed auction mechanisms in dynamic P2P VoD systems based on real-world settings.

We present a new image search and ranking algorithm for retrieving unannotated images by collaboratively mining online search results which consist of online image and text search results. The online image search results are leveraged as reference examples to perform content-based image search over unannotated images. The online text search results are utilized to estimate the reference images' relevance to the search query. The key feature of our method is its capability to deal with unreliable online image search results through jointly mining visual and textual aspects of online search results. Through such collaborative mining, our algorithm infers the relevance of an online search result image to a text query. Once we obtain the estimate of query relevance score for each online image search result, we can selectively use query specific online search result images as reference examples for retrieving and ranking unannotated images. We tested our algorithm both on the standard public image datasets and several modestly sized personal photo collections. We also compared our method with two well-known peer methods. The results indicate that our algorithm is superior to existing content-based image search algorithms for retrieving and ranking unannotated images.

Internet-based cloud computing is a new computing paradigm aiming to provide agile and scalable resource access in a utility-like fashion. Other than being an ideal platform for computation-intensive tasks, clouds are believed to be also suitable to support large-scale applications with periods of flash crowds by providing elastic amounts of bandwidth and other resources on the fly. The fundamental question is how to configure the cloud utility to meet the highly dynamic demands of such applications at a modest cost. In this paper, we address this practical issue with solid theoretical analysis and efficient algorithm design using Video on Demand (VoD) as the example application. Having intensive bandwidth and storage demands in real time, VoD applications are purportedly ideal candidates to be supported on a cloud platform, where the on-demand resource supply of the cloud meets the dynamic demands of the VoD applications. We introduce a queueing network based model to characterize the viewing behaviors of users in a multichannel VoD application, and derive the server capacities needed to support smooth playback in the channels for two popular streaming models: client-server and P2P. We then propose a dynamic cloud resource provisioning algorithm which, using the derived capacities and instantaneous network statistics as inputs, can effectively support VoD streaming with low cloud utilization cost. Our analysis and algorithm design are verified and extensively evaluated using large-scale experiments under dynamic realistic settings on a home-built cloud platform.

We propose a personalized re-ranking algorithm through mining user dwell times derived from a user’s previously online reading or browsing activities. We acquire document level user dwell times via a customized web browser, from which we then infer concept word level user dwell times in order to understand a user’s personal interest. According to the estimated concept word level user dwell times, our algorithm can estimate a user’s potential dwell time over a new document, based on which personalized webpage re-ranking can be carried out. We compare the rankings produced by our algorithm with rankings generated by popular commercial search engines and a recently proposed personalized

We propose a new personalized document summarization method that observes a user's personal reading preferences. These preferences are inferred from the user's reading behaviors, including facial expressions, gaze positions, and reading durations that were captured during the user's past reading activities. We compare the performance of our algorithm with that of a few peer algorithms and software packages. The results of our comparative study show that our algorithm can produce more superior personalized document summaries than all the other methods in that the summaries generated by our algorithm can better satisfy a user's personal preferences.

In cognitive radio networks, the occupation patterns of the primary users can be very dynamic, which makes optimization (e.g., utility maximization) of data dissemination among secondary users difficult. Even under the assumption that all secondary users are fully collaborative, the optimization requires cross-layer decision making which is challenging. The challenge escalates if users are socially selfish, who prefer to relay data only to those other users with whom there are social ties. Such social selfishness of users translates into new constraints on network protocol design. There has been no study so far on the impact of social selfishness on data dissemination in cognitive radio networks. In this paper, we consider social selfishness of secondary users, and propose the design of a joint end-to-end rate control, routing, and channel allocation protocol which can maximize the overall throughput utility of multi-session unicast in cognitive radio networks. We give a distributed implementation of the protocol. Based on a Lyapunov optimization framework, we address social preferences of users using differentiated buffer sizes and relay rates for different data sessions, and apply back-pressure based transmission scheduling to achieve guaranteed utility optimality. A unique contribution of our Lyapunov optimization is that only a finite-sized buffer is required at each user node, which sets our design apart from other designs in existing literature where they assume infinite buffers. We investigate the the optimality of our protocol and the impact of user social selfishness using both theoretical analysis and extensive simulations.

We propose a new method for personalized webpage recommendation. The method is capable of inferring a user's personal reading interest distribution according to implicit user feedbacks coming from the user's past online reading activities. With the inferred user reading interest distribution, we can recommend webpages in a search result set to a user in a personalized way. Our method is featured by its novel approach to observe the facial expressions and gaze positions of a user during the user's online reading activities as two types of implicit user feedbacks for estimating the user's reading interest distribution. To capture these implicit user feedbacks, we use an ordinary web camera and a customized web browser in the setup. The setup allows us to measure the distribution of the reading time a user spends in his or her reading activities over materials of different contents. With all the captured information, our method then estimates a user's reading interest distribution by finding correlations between the implicit feedbacks of a user with the contents of the read materials. Given the estimated user reading interest distribution, our algorithm can further predict the user's potential reading interest in any new webpage. Consequently, our algorithm can produce a personalized webpage recommendation for all the result webpages in an online search session. We compared the performance of our method with that of several mainstream commercial search engines as well as a recent personalized webpage ranking algorithm. The comparison results clearly show the superiority of our new method for personalized webpage recommendation.

We introduce several novel word features for keyword extraction and headline generation. These new word features are derived according to the background knowledge of a document as supplied by Wikipedia. Given a document, to acquire its background knowledge from Wikipedia, we first generate a query for searching the Wikipedia corpus based on the key facts present in the document. We then use the query to find articles in the Wikipedia corpus that are closely related to the contents of the document. With the Wikipedia search result article set, we extract the inlink, outlink, category and infobox information in each article to derive a set of novel word features which reflect the document's background knowledge. These newly introduced word features offer valuable indications on individual words' importance in the input document. They serve as nice complements to the traditional word features derivable from explicit information of a document. In addition, we also introduce a word-document fitness feature to charcterize the influence of a document's genre on the keyword extraction and headline generation process. We study the effectiveness of these novel word features for keyword extraction and headline generation by experiments and have obtained very encouraging results.

The recent surge of large-scale peer-to-peer (P2P) applications has brought huge amounts of P2P traffic, which significantly changes the Internet traffic pattern and increases the traffic-relay cost at the Internet Service Providers (ISPs). To alleviate the stress on networks, localized peer selection has been proposed that advocates neighbor selection within the same network (AS or ISP) to reduce the cross-ISP traffic. Nevertheless, localized peer selection may potentially lead to the downgrade of downloading speed at the peers, rendering a non-negligible tradeoff between the downloading performance and traffic localization in the P2P system. Aiming at effective peer selection strategies that achieve any desired Pareto optimum in face of the tradeoff, in this paper, we characterize the performance and locality tradeoff as a multi-objective b-matching optimization problem. In particular, we first present a generic maximum weight b-matching model that characterizes the tit-for-tat in BitTorrent-like peer selection. We then introduce multiple optimization objectives into the model, which effectively characterize the performance and locality tradeoff using simultaneous objectives to optimize. We also design fully distributed peer selection algorithms that can effectively achieve any desired Pareto optimum of the global multi-objective optimization, that represents a desired tradeoff point between performance and locality in the entire system. Our models and algorithms are supported by rigorous analysis and extensive simulations.

Minimum-Latency Aggregation Scheduling (MLAS) is a problem of fundamental importance in wireless sensor networks. There however has been very little effort spent on designing algorithms to achieve sufficiently fast data aggregation under the physical interference model which is a more realistic model than traditional protocol interference model. In particular, a distributed solution to the problem under the physical interference model is challenging because of the need for global-scale information to compute the cumulative interference at any individual node. In this paper, we propose a distributed algorithm that solves the MLAS problem under the physical interference model in networks of arbitrary topology in O(K) time slots, where K is the logarithm of the ratio between the lengths of the longest and shortest links in the network. We also give a centralized algorithm to serve as a benchmark for comparison purposes, which aggregates data from all sources in O(log3n) time slots (where n is the total number of nodes). This is the current best algorithm for the problem in the literature. The distributed algorithm partitions the network into cells according to the value K, thus obviating the need for global information. The centralized algorithm strategically combines our aggregation tree construction algorithm with the non-linear power assignment strategy in [9]. We prove the correctness and efficiency of our algorithms, and conduct empirical studies under realistic settings to validate our analytical results.

We propose an optimal web content provider recommendation algorithm based on mining QoS (quality of service) information of the Internet. The QoS refers principally to the network bandwidth and waiting time (for a connection to be established). For contents replicated over multiple sites, our algorithm recommends a list of webpages having the desired content and ranked according to their QoSs for any specific user. The recommendation is generated through a data mining procedure based on known QoSs of connections between pairs of computers. Our user QoS mining procedure incrementally constructs a neural network group for QoS prediction based on clustering over the prediction errors. An accompanying decision tree algorithm is then used to select the most appropriate neural network among the neural network group to predict the QoS for a particular user connection. Based on our proposed recommendation algorithm, we have implemented a user-oriented search engine which can identify similar web content providers and make a ranked recommendation based on the prediction over the QoS experienced by individual users. Experiment results have verified that our QoS-based personal web content provider ranking algorithm can indeed produce a recommendation that improves the QoS experienced by individual users.

We propose a new document summarization algorithm which is personalized. The key idea is to rely on the attention (reading) time of individual users spent on single words in a document as the essential clue. The prediction of user attention over every word in a document is based on the user's attention during his previous reads, which is acquired via a vision-based commodity eye-tracking mechanism. Once the user's attentions over a small collection of words are known, our algorithm can predict the user's attention over every word in the document through word semantics analysis. Our algorithm then summarizes the document according to user attention on every individual word in the document. With our algorithm, we have developed a document summarization prototype system. Experiment results produced by our algorithm are compared with the ones manually summarized by users as well as by commercial summarization software, which clearly demonstrates the advantages of our new algorithm for user-oriented document summarization.

A fundamental challenge in peer-to-peer (P2P) Video-on-Demand (VoD) streaming is to quickly locate new supplying peers whenever a VCR command is issued, in order to achieve smooth viewing experiences. For most existing commercial systems which resort to tracking servers for such neighbor discovery, the increasing scale of P2P VoD systems has brought heavy load onto the dedicated servers. To avoid overloading the servers and achieve instant neighbor discovery over the self-organizing P2P overlay, we design a novel method of organizing peers watching the same video, that constitutes a light-weighted indexing structure to support efficient streaming and fast neighbor discovery at the same time. InstantLeap achieves an O(1) neighbor discovery efficiency upon any playback "leaps" across the media stream in streaming overlays of any sizes, with a low messaging cost for the overlay maintenance. We support our design with rigorous analysis and extensive simulations.

We introduce a new visual search interface for search engines. The interface is a user-friendly and informative graphical front-end for organizing and presenting search results in the form of topic groups. Such a semantics-oriented search result presentation is in contrast with conventional search interfaces which present search results according to the physical structures of the information. Given a user query, our interface first retrieves relevant online materials via a third-party search engine. And then we analyze the semantics of search results to detect latent topics in the result set. Once the topics are detected, we map the search result pages into topic clusters. According to the topic clustering result, we divide the available screen space for our visual interface into multiple topic displaying regions, one for each topic. For each topic's displaying region, we summarize the information contained in the search results under the corresponding topic so that only key messages will be displayed. With this new visual search interface, users are conveyed the key information in the search results expediently. With the key information, users can navigate to the final, desired results with less effort and time than conventional searching. Supplementary materials for this paper are available at http://www.cs.hku.hk/~songhua/visualsearch/.

Abstract We propose a visualization based approach for digital signature authentication. Using our method, the speed and pressure aspects of a digital signature process can be clearly and intuitively conveyed to the user for digital signature authentication. Our design takes into account both the expressiveness and aesthetics of the derived visual patterns. With the visual aid provided by our method, digital signatures can be authenticated with better accuracy than using existing methods—even novices can examine the authenticity of a digital signature in most situations using our method. To validate the effectiveness of our method, we conducted a comprehensive user study which confirms positively the advantages of our approach. Our method can be employed as a new security enhancement measure for a range of business and legal applications in reality which involve digital signature authorization and authentication.

We study the load rebalancing problem in a heterogeneous grid environment that supports process migration. Given an initial assignment of tasks to machines, the problem consists of finding a process reassignment that achieves a desired better level of load balance with minimum reassignment (process migration) cost. Most previous algorithms for related problems aim mainly at improving the balance level (or makespan) with no explicit concern for the reassignment cost. We propose a heuristic which is based on local search and several optimizing techniques which include the guided local search strategy and the multi-level local search. The searching integrates both the change of workload and the migration cost introduced by a process movement into the movement selection, and enables a good tradeoff between low-cost movements and the improving balance level. Evaluations show that the proposed heuristic can find a solution with much lower migration cost for achieving the same balance level than previous greedy or local search algorithms for a range of problem cases.

The ever increasing number of processors used in parallel computers is making fault tolerance support in large-scale parallel systems more and more important. We discuss the inadequacies of existing system-level checkpointing solutions for message-passing applications as the system scales up. We analyze the coordination cost and blocking behavior of two current MPI implementations with checkpointing support. A group-based solution combining coordinated checkpointing and message logging is then proposed. Experiment results demonstrate its better performance and scalability than LAM/MPI and MPICH-VCL. To assist group formation, a method to analyze the communication behaviors of the application is proposed.

We propose a lightweight process migration mechanism and an adaptive memory prefetching scheme called AMPoM (adaptive memory prefetching in openMosix), whose goal is to reduce the migration freeze time in openMosix while ensuring the execution efficiency of migrants. To minimize the freeze time, our system transfers only a few pages to the destination node during process migration. After the migration, AMPoM analyzes the spatial locality of memory access and iteratively prefetches memory pages from remote to hide the latency of inter-node page faults. AMPoM adopts a unique algorithm to decide which and how many pages to prefetch. It tends to prefetch more aggressively when a sequential access pattern is developed, when the paging rate of the process is high or when the network is busy. This advanced strategy makes AMPoM highly adaptive to different application behaviors and system dynamics. The HPC Challenge benchmark results show that AMPoM can avoid 98% of migration freeze time while preventing 85-99% of page fault requests after the migration. Compared to openMosix which does not have remote page fault, AMPoM induces a modest overhead of 0-5% additional runtime. When the working set of a migrant is small, AMPoM outperforms openMosix considerably due to the reduced amount of data transfer. These results indicate that by exploiting memory access locality and prefetching, process migration can be a lightweight operation with little software overhead in remote paging.

Traditional audio retrieval systems deal principally with audio clips having text descriptions. To retrieve unannotated audio clips is cumbersome because of the immaturity of content-based analysis and retrieval techniques. In this paper, we propose a two-stage audio retrieval method, consisting of a first stage of text-based retrieval and a second stage of content-based retrieval. This new retrieval method can be employed to retrieve audio clips from an audio collection having only partial text annotations, which is true of many online audio datasets. We have developed a prototype audio retrieval system based on our algorithm and carefully evaluated its performance. The results demonstrate the effectiveness of our new audio retrieval method. Our method can be generalized and applied to other kinds of non-textual data such as images and videos.

We present an algorithmic system capable of automatically generating a music slide show given a piece of music with lyrics. Different from previous approaches, our method generates slide shows using personal photos which are without annotation. We introduce a novel algorithm to infer the relevance of personal photos to the lyrics, based on which personal photos are optimally selected to match the music. The proposed system first detects the keyframes of the input music. For each music keyframe, it optimally selects an image from the personal photo collection via our image content analysis procedure. Once the keyframe images have been selected, the in-between frames are then generated via an image morphing process. Experiment results have shown that our method can successfully generate music slide shows which follow the rhythms of the music and at the same time match the lyrics.

We propose a new recommendation algorithm for online documents, images and videos, which is personalized. Our idea is to rely on the attention time of individual users captured through commodity eye-tracking as the essential clue. The prediction of user interest over a certain online item (a document, image or video) is based on the user's attention time acquired using vision-based commodity eye-tracking during his previous reading, browsing or video watching sessions over the same type of online materials. After acquiring a user's attention times over a collection of online materials, our algorithm can predict the user's probable attention time over a new online item through data mining. Based on our proposed algorithm, we have developed a new online content recommender system for documents, images and videos. The recommendation results produced by our algorithm are evaluated by comparing with those manually labeled by users as well as by commercial search engines including Google (Web) Search, Google Image Search and YouTube. © 2008 ACM.

Abstract To imitate personal handwritings is non‐trivial. In this paper, we attempt to address the challenging problem of automatic handwriting facsimile. We focus on Chinese calligraphic writings due to their rich variation in style, high artistic values and also the fact that they are among the most difficult candidates for the problem. We first analyze the structures and shapes of the constituent components, i.e., strokes and radicals, of characters in sample calligraphic writings by the same writer. To generate calligraphic writing in the style of the writer, we facsimile the individual character elements as well as the layout relationships used to compose the character, both in the writer's personal writing style. To test our algorithm, we compare our facsimileing results of Chinese calligraphic writings with the original writings. Our results are found to be acceptable for most cases, some of which are difficult to differentiate from the real ones. More results and supplementary materials are provided in our project website at http://www.cs.hku.hk/~songhua/facsimile/ .

We introduce a new memory management system, STEMA, which can improve the execution time of Java programs. STEMA detects prolific types on-the-fly and co-locates their objects in a special memory space which supports reuse of memory. We argue and show that memory reuse and co-location of prolific objects can result in improved cache locality, reduced memory fragmentation, reduced GC time, and faster object allocation. We evaluate STEMA using 16 benchmarks. Experimental results show that STEMA performs 2.7%, 4.0%, and 8.2% on average better than MarkSweep, CopyMS, and SemiSpace.

Evolutionary algorithms have been used since the mid-eighties to solve complex single and multi-objective optimization problems. More recently the swarm intelligent approaches such as particle swarm optimization and ant colony optimization have been successfully used for multi objective optimization. This paper proposes a new approach based on the generic generalized particle model (GE-GPM) for computing in parallel approximate efficient solutions for the distribution problem with multiple objectives. Unlike the swarm optimization approaches, GE-GPM is inspired by physical models of particle dynamics. We use mathemati cal formulations to describe or predict the properties and evolution of different states of the particles. In particular, according to “differential equation theory”, we develop ef ficient optimization techniques for multi-objective problems. We also adopt methods of classical mechanics to tackle the problem of modeling the interaction among the particles. We show that GE-GPM, being inspired by classical mechanics, enables feasible multi-objective optimization in very large scales. The GE-GPM approach has a low computational complexity, which is crucial for the functioning of large-scale distribution problems. kw|Evolutionary algorithm (EA) kw|multi-objective optimization kw|swarm intelligence kw|generic generalized particle model (GE-GPM) kw|kinematics and dynamics

In application-level high bandwidth multicast (HBM), physical links can be shared by multiple long-lived unicast flows. We identify several data transfer patterns which can cause suboptimal bandwidth usage of narrow links and which have not been clearly identified in previous solutions for application-level HBM. We propose a distributed solution to avoid these problematic patterns, with which end systems are coordinated and each is responsible to forward a bounded amount of data. Consequently, the outgoing traffic of each end system is balanced and limited. It avoids congestion due to merging unicast flows, which increases the utilization of the narrow links. Receivers that are close by topologically request their data in a disjoint and coordinated fashion, which leads to much reduced duplicated data at the narrow links. Simulation results show that our solution can achieve higher throughputs at the receivers, which is due to more efficient utilization of the narrow links' bandwidth, than mesh-based or multiple-tree approaches.

Abstract We propose a generic pigment model suitable for digital painting in a wide range of genres including traditional Chinese painting and water‐based painting. The model embodies a simulation of the pigment‐water solution and its interaction with the brush and the paper at the level of pigment particles; such a level of detail is needed for achieving highly intricate effects by the artist. The simulation covers pigment diffusion and sorption processes at the paper surface, and aspects of pigment particle deposition on the paper. We follow rules and formulations from quantitative studies of adsorption and diffusion processes in surface chemistry and the textile industry. The result is a pigment model that spans a continuum from the very wet to the very dry brush stroke effects. We also propose a new pigment mixing method based on machine learning techniques to emulate pigment mixing in real life as well as to support the creation of new artificial pigments. To experiment with the proposed model, we embedded the model in a sophisticated digital brush system. The combined system exhibits interactive speed on a modest PC platform. http://www.cs.hku.hk/~songhua/pigment provides supplementary materials for this paper.

Achieving IP handoff with a short latency and minimal packet loss is essential for mobile devices that roam across IP subnets. Many existing solutions require changes to be made to the network or transport layer, and they tend to suffer from long handoff latency in either soft or hard hand-off scenario, or both; and some are difficult to deploy in practice. We propose a new protocol, called the adaptive multipath protocol, to achieve efficient IP handoff. Based on link-layer signal strength measurements, two different schemes are used to handle soft and hard handoff respectively. Seamless IP handoff is achieved by using multiple transport layer connections on top of persistent link-layer connectivity during soft handoff. To achieve low hand-off latency during hard handoff, a set of distributed sessions repositories (SRs), which are independent of the end hosts, are employed. Simulation results clearly support our claims. In particular, the latency for hard handoff is found to be as low as 50% of that of Fast handoff.

Recently Moscibroda and Wattenhofer came up with the notion of scheduling complexity to capture the minimum amount of time to successfully schedule all the transmission requests under the physical SINR model. Their algorithm featuring a non-linear power assignment can schedule strongly connected transmissions in narrowband networks with O(log4 n) timeslots. In this paper, we first generalize this result to ultra-wideband networks. We show the strong connectivity scheduling complexity in UWB networks to be O(log (n/m)∙log3 n), where m is the processing gain. Secondly, we show that both of these polylogarithmic scheduling complexity results are gained at the expense of exponential energy complexity with lower bound ω(n∙2n). We also prove the upper bound of the energy complexity in narrowband networks to beO(n2∙2nα), and for UWB networks, this upper bound can be reduced by a processing gain factor.On the other hand, we show that improving the scheduling complexity through arbitrary power control has its limitations, and that different power assignment strategies have different impacts on the protocol interference models, which was often neglected in the design of wireless scheduling algorithms. Compared with narrowband networks, although the effect of aggregate interferences in UWB networks is greatly reduced, we demonstrate that the constant and linear power assignments in UWB networks are still inefficient in the worst case with respect to the scheduling complexity (Ω(n/m), which suggests there is a need for a better arbitrary power assignment.Our analyses shed new light on the design of the power assignment scheme and the performance analysis of the wireless scheduling algorithms. In energy-constrained wireless networks, a tradeoff between the scheduling complexity and energy complexity is a practical consideration. Our results in this paper can be directly applied to other spread-spectrum networks including DS-CDMA and FH-CDMA.

Abstract Grid computing unifies distributed resources via its support for the creation and use of virtual organizations (VOs), where a VO represents a collection of distributed resources to be accessed through predefined resource sharing and coordination policies. We consider a special type of mobile processes, named Grid travelers, which can travel across boundaries of VOs for the detection of resource availability, to negotiate for the approval of access privileges and to conduct remote execution. A new security infrastructure named G‐PASS is proposed to guarantee the validity and integrity of the travelers and the critical security knowledge they collect while traveling, especially while crossing some VOs. G‐PASS borrows the idea of passport and custom, as well as the procedures for people's travel in real life, to provide role‐based delegation mapping and access control. We demonstrate the power and feasibility of G‐PASS with a simulated mobile agent environment and a distributed ray‐tracing application running on multiple VOs. Various security overheads coming from migration decisions and actual agent or process migration are reported. G‐PASS can be installed with Grid Security Infrastructure (GSI) as the base, which makes it compatible with the existing Grid middleware. Copyright © 2006 John Wiley & Sons, Ltd.

Abstract The Grid is a new type of resource sharing infrastructure. Due to software and hardware limitations, the service that a certain Grid can offer is finite, and so is the number of users it can accommodate. If the number of users is too small, much of the planned resources would be wasted. On the other hand, excessive loading due to too many users could substantially reduce the benefit enjoyed by each user and also the efficiency of the Grid service. Therefore, there are two main problems for Grid design. (1) How many users should the Grid serve so that each user can receive the maximum benefit? (2) To a certain group of users, how much resources should be invested so that the construction and maintenance of the Grid become viable? Based on the economic theory of clubs, this paper gives a quantitative analysis of the quasi‐optimal number of users and amount of each resource by regarding Grid services and resources as club goods. Based on our assumptions on the system model, we deduce two preliminary results and verify them by experiments using GridFTP. These two results allow the users to run randomized algorithms to achieve better system performance. Copyright © 2006 John Wiley & Sons, Ltd.

Content adaptation is a crucial step in making desktop-oriented Web resources available to mobile, small device users. In this paper, we propose a decision engine comprising a content analysis module and a negotiation module to serve as the core of a content adaptation architecture. The content analysis module parses a structured Web document originally intended for the desktop into small sections and transforms the document into a form that is best suited for rendering in a constrained mobile device. The transformation also provides the user with the best content value in an adapted Web page while preserving content integrity. With the transformed document, the negotiation module selects the best rendering parameters to be used in the synthesis of an optimal adapted version of the content. The decisions made are based on the user's preference and QoS considerations. We have built a prototype to demonstrate the viability of our approach.

We study the p-median problem which is one of the classical problems in location theory. For p = 2 and on a two-dimensional mesh, we give an O(m/sup 2/ + q log q)-time approximation algorithm for solving the problem with worst-case ratio 1.5 + /spl delta/ on the communication cost, where m is the number of rows of the mesh containing demand points, n the number of columns containing demand points, m /spl ges/ n,q the number of demand points, and /spl delta/ is some positive constant which can be as small as needed.

Information resources on their own present only the information they contain. The relationship between the resources and the users is usually neglected. By exploiting the relationship between the user and information resources in the form of context, which is established when the user accesses or acquires these resources, can help create smart mobile appliances. The metadata contained in a context is not merely data about data, but represents how the user and the information resource are related, which helps searching, provides clues to find related information resources, and facilitates information sharing with minimum manual effort. An electronic business name cards application is implemented to demonstrate the applicability of the idea.

In the light of the increasingly serious I/O bottleneck problem, the paper puts forward a method named RAID-M (RAID Matrix) to build high performance mass storage from cheap PC components based on the idea of multi-channel I/O and parallel access. Theoretical analyses prove that different RAID-M configurations vary their performance, space utilization and reliability, meeting various application goals. Experiments show that both the sequential read performance and sequential write performance of a RAID-M prototype machine have broken through the limitation of 32 bit/33 MHz PCI bus. Copyright by Science in China Press 2005.

The design of user friendly and expressive virtual brush systems for interactive digital painting and calligraphy has attracted a lot of attention and effort in both computer graphics and human-computer interaction circles for a long time. Providing a digital environment for paper-less artwork creation is not only challenging in terms of algorithmic design, but also promising for its potential market values. This paper proposes a novel algorithmic framework for interactive digital painting and calligraphy based a novel virtual hairy brush model. The algorithms in the kernel of our simulation framework are built upon solid modeling techniques. Implementing the algorithms, we have developed a virtual hairy brush prototype system with which end users can interactively produce high-quality digital paintings and calligraphic artwork. (The latest progress of our virtual brush project is reported at the website "http://www.cs.hku.hk/~songhua/e-brush/".) Copyright by Science in China Press 2005.

Applying a cache coherence protocol capable of adapting to memory access patterns is a viable approach to improving the performance of software distributed shared memory. In this paper, we present an approach of postmortem memory access pattern analysis and visualization, which has been applied to our design of a global object space for a distributed Java Virtual Machine. The tool not only can enhance our understanding of the access patterns inherent in an application but can also help us to evaluate the effectiveness of an adaptive protocol used in the design of the global object space.

Software DSM provides good programmability for cluster computing, but its performance and limited shared memory space for large applications hinder its popularity. This paper introduces LOTS, a C++ runtime library supporting a large shared object space. With its dynamic memory mapping mechanism, LOTS can map more objects, lazily from the local disk to the virtual memory during access, leaving only a trace of control information for each object in the local process space. To our knowledge, LOTS is the first pure runtime software DSM supporting a shared object space larger than the local process space. Our testing shows that LOTS can utilize all the free hard disk space available to support hundreds of gigabytes of shared objects with a small overhead. The scope consistency memory model and a mixed coherence protocol allow LOTS to achieve better scalability with respect to problem size and cluster size.

Home migration is used to tackle the home assignment problem in home-based software distributed shared memory systems. We propose an adaptive home migration protocol to optimize the single-writer pattern which occurs frequently in distributed applications. Our approach is unique in its use of a per-object threshold which is continuously adjusted to facilitate home migration decisions. This adaptive threshold is monotonously decreasing with increased likelihood that a particular object exhibits a lasting single-writer pattern. The threshold is tuned according to the feedback of previous home migration decisions at runtime. We implement this adaptive home migration protocol in a distributed Java virtual machine that supports truly parallel execution of multithreaded Java applications on clusters. The analysis and the experiments show that our home migration protocol demonstrates both the sensitivity to the lasting single-writer pattern and the robustness against the transient single-writer pattern. In the latter case, the protocol inhibits home migration in order to reduce the home redirection overhead.

A distributed JVM on a cluster can provide a high-performance platform for running multithreaded Java applications transparently. Efficient scheduling of Java threads among cluster nodes in a distributed JVM is desired for maintaining a balanced system workload so that the application can achieve maximum speedup. We present a transparent thread migration system that is able to support high-performance native execution of multi-threaded Java programs. To achieve migration transparency, we perform dynamic native code instrumentation inside the JIT compiler. The mechanism has been successfully implemented and integrated in JESSICA2, a JIT-enabled distributed JVM, to enable automatic thread distribution and dynamic load balancing in a cluster environment. We discuss issues related to supporting transparent Java thread migration in a JIT-enabled distributed JVM, and compare our solution with previous approaches that use static bytecode instrumentation and JVMDI. We also propose optimizations including dynamic register patching and pseudo-inlining that can reduce the runtime overhead incurred in a migration act. We use measured experimental results to show that our system is efficient and lightweight.

Pervasive computing has attracted a lot of attention in recent years. There are now proxy servers that are specially designed for pervasive computing. To enable content viewing in small devices, different kinds of content adaptation techniques have been used (such as distillation and transcoding) to adapt Web contents in content-rich servers to resource-constrained devices. Adaptation of Web contents has been widely discussed, but little attention was paid to the adaptation of services (or service code), which is equally important for computing anytime, anywhere, and on any device. We present an approach to adaptation of service code which is proxy-based and context-aware, called "functionality adaptation". The main difficulty of such an adaptation is to estimate the resource usage required for an execution, which varies with the input size and is available only at run-time. We propose a conservative solution. A simple prototype has been implemented to evaluate our adaptation approach.

Abstract This paper proposes a novel algorithmic framework for an advanced virtual brush to be used in interactive digitalpainting. The framework comprises the following components: a geometry model of the brush using a hierarchicalrepresentation that leads to substantial savings in every step of the painting process; fast online brush motionsimulation assisted by offline calibration that guarantees an accurate and stable simulation of the brush's dynamicbehavior; a new pigment model based on a diffusion process of random molecules that considers delicateand complex pigment behavior at dipping time as well as during painting; and a user‐adaptation component thatenables the system to cater for the personal painting habits of different users. A prototype system has been implementedbased on this framework. Compared with other virtual brushes, this new system is designed to presenta realistic brush in the sense that the system accurately and stably simulates the complex painting functionalityof a running brush, and therefore is capable of creating high‐quality digital paintings with minute aesthetic detailsthat can rival the real artwork. The advanced features also give rise to a high degree of expressiveness ofthe virtual brush that the user can comfortably manipulate. http://www.csis.hku.hk/songhuale‐brush/ providessupplementary materials for this paper. Categories and Subject Descriptors (according to ACM CCS): I.3.6 [Methodology and Techniques]: Interactiontechniques; I.3.5 [Computational Geometry and Object Modeling]: Physically based modeling; I.3.4 [GraphicsUtilities]: Paint systems;

Abstract Clustering provides a viable approach to building scalable Web systems with increased computing power and abundant storage space for data and contents. In this paper, we present a pure‐Java‐based parallel Web server system, p‐Jigsaw, which operates on a cluster and uses the technique of cooperative caching to achieve high performance. We introduce the design of an in‐memory cache layer, called Global Object Space (GOS), for dynamic caching of frequently requested Web objects. The GOS provides a unified view of cluster‐wide memory resources for achieving location‐transparent Web object accesses. The GOS relies on cooperative caching to minimize disk accesses. A requested Web object can be fetched from a server node's local cache or a peer node's local cache, with the disk serving only as the last resort. A prototype system based on the W3C Jigsaw server has been implemented on a 16‐node PC cluster. Three cluster‐aware cache replacement algorithms were tested and evaluated. The benchmark results show good speedups with a real‐life access log, proving that cooperative caching can have significant positive impacts on the performance of cluster‐based parallel Web servers. Copyright © 2003 John Wiley & Sons, Ltd.

We address the challenges of building a good content adaptation service for mobile devices and propose a decision engine that is user-centric with QoS awareness, which can automatically negotiate for the appropriate adaptation decision to use in the synthesis of an optimal adapted version. The QoS-sensitive approach complements the lossy nature of the transcoding operations. The decision engine will look for the best trade off among various parameters in order to reduce the loss of quality in various domains. Quantitative methods are suggested to measure the QoS of the content versions in various quality domains. Based on the particular user perception and other contextual information on the client capability, the network connection, and the requested content, the proposed negotiation algorithm will determine a content version with a good aggregate score. We have built a prototype document adaptation system for PDF documents to demonstrate the viability of our approach.

Several Java bindings to the Message Passing Interface (MPI) software have been developed for high-performance parallel Java-based computing with message-passing in the past. None of them however addressed the issue of supporting transparent Java process migration for achieving dynamic load distribution and balancing. This paper presents a middleware, called M-JavaMPI, that runs on top of the standard JVM to support transparent Java process migration and communication redirection. The middleware allows Java processes to freely and transparently migrate between machines to achieve load balancing, and migrated processes can continue communication with other processes using MPI. The method we use to achieve process migration is to capture execution context and restoring the execution context at the Java bytecode level using the Java Virtual Machine Debugger Interface (JVMDI). Post-migration interprocess communication is enabled via a Restorable Java-MPI API. Tests using a 16-node cluster have Shown that our mechanism yields considerable performance gain through migration.

Cluster-based web server is a popular solution to meet the demand of the ever-growing web traffic. However existing approaches suffer from several limitations to achieve this. Dispatcher-based systems either can achieve only coarse-grained load balancing or would introduce heavy load to the dispatcher Mechanisms like cooperative caching consume much network resources when transferring large cache objects. In this paper, we present a new network support mechanism, called Socket Cloning (SC), in which an opened socket can be migrated efficiently between cluster nodes. With SC, the processing of HTTP requests can be moved to the node that has a cached copy of the requested document, thus bypassing any object transfer between peer servers. A prototype has been implemented and tests show that SC incurs less overhead than all the mentioned approaches. In trace-driven benchmark tests, our system outperforms these approaches by more than 30% with a cluster of twelve web server nodes.

A distributed Java Virtual Machine (DJVM) spanning multiple cluster nodes can provide a true parallel execution environment for multi-threaded Java applications. Most existing DJVMs suffer from the slow Java execution in interpretive mode and thus may not be efficient enough for solving computation-intensive problems. We present JESSICA2, a new DJVM running in JIT compilation mode that can execute multi-threaded Java applications transparently on clusters. JESSICA2 provides a single system image (SSI) illusion to Java applications via an embedded global object space (GOS) layer. It implements a cluster-aware Java execution engine that supports transparent Java thread migration for achieving dynamic load balancing. We discuss the issues of supporting transparent Java thread migration in a JIT compilation environment and propose several lightweight solutions. An adaptive migrating-home protocol used in the implementation of the GOS is introduced. The system has been implemented on x86-based Linux clusters and significant performance improvements over the previous JESSICA system have been observed.

We propose a decision engine with QoS awareness that can automatically negotiate for the appropriate adaptation strategies to be used to produce an optimal adapted version. The QoS-sensitive approach complements the lossy nature of the transcoding operations. The decision engine will look for the best tradeoff among various parameters in order to reduce the loss of quality, in various domains. Quantitative methods are suggested to measure the QoS of the content versions. Based on the particular user perception of these quality domains and other context information on the client capability, the proposed negotiation algorithm will determine a content version with a good aggregate score. We study factors such as processing overhead and the optimization accuracy of the algorithm, and their tradeoff. We built a prototype document adaptation system for PDF documents to demonstrate the viability of our approach.

We present the design of a global object space in a distributed Java Virtual Machine that supports parallel execution of a multi-threaded Java program on a cluster of computers. The global object space virtualizes a single Java object heap across machine boundaries to facilitate transparent object accesses. Based on the object connectivity information that is available at runtime, the object reachable from threads at different nodes, called a distributed-shared object, are detected With the detection of distributed-shared objects, we can alleviate overheads in maintaining the memory consistency within the global object space. Several runtime optimization methods have been incorporated in the global object space design, including an object home migration method that reallocates the home of a distributed-shared object, synchronized method migration that allows the remote execution of a synchronized method at the home node of its synchronized object, and object pushing that uses the object connectivity information to improve access locality.

How documents of a Web site are replicated and where they are placed among the server nodes have an important bearing on balance of load in a geographically distributed Web server (DWS) system. The traffic generated due to movements of documents at runtime could also affect the performance of the DWS system. In this paper, we prove that minimizing such traffic is NP-hard. We propose a new document distribution scheme that periodically performs partial replication of a site's documents at selected server locations to maintain load balancing. Several approximation algorithms are used in it to minimize traffic generated. The simulation results show that this scheme can achieve better load balancing than a dynamic scheme, while the internal traffic it causes has a negligible effect on the system's performance.

We propose a method that can find the optimal tradeoff point between transcoding overhead (CPU cost) and storage needed for the various pre-processed content variants (I/O cost). The method selectively pre-adapts a subset of content variants and leaves the generation of the residue to dynamic content adaptation with this pre-adapted subset as an input. We prove bounds regarding the optimality of the algorithm employed. The proposed model creates a collaborative environment across the components of client, proxy and server, based on which we study the distribution of adaptation complexity across these components. We use simulation to verify the projected benefits. The method has been successfully implemented in a trial PDF document content adaptation system.

We present the detailed modeling of the hairy brush used typically in Chinese calligraphy. The complex model, which includes also a model for the ink and the paper, covers the various stages of the brush going through a calligraphy process. The model relies on the concept of writing primitives, which are the smallest units of hair clusters, to reduce the load on the simulation. Each such primitive is constructed through the general sweeping operation in CAD and described by a NURBS surface. The writing primitives dynamically adjust themselves during the virtual writing process, leaving an imprint on the virtual paper as they move. The behavior of the brush is an aggregation of the behavior of all the writing primitives. A software system based on the model has been built and tested. Samples of imitation artwork from using the system were obtained and found to be nearly indistinguishable from the real artwork. Categories and Subject Descriptors (according to ACM CCS): I.3.6 [Methodology and Techniques]: Interaction techniques I.3.5 [Computational Geometry and Object Modeling]: Physically based modeling I.3.4 [Graphics Utilities]: Paint systems

Gossiping is a communication problem in which each node has a unique message (token) to be transmitted to every other node. The nodes exchange their tokens by means of packets. A solution to the problem is judged by how many rounds of packet sending are required. In this paper, we consider a version of the problem in which small-sized packets (each carrying exactly one token) are used, the links (edges) of the network are half-duplex (only one packet can flow through a link at a time), and the nodes are all-port (a node's incident edges can all be active at the same time). This is also known as the H* model. We study the model on a 2D square mesh and on a 2D square torus. An improved, asymptotically optimal algorithm for the mesh and an optimal algorithm for the torus are presented.

Clustering provides a viable approach to building a scalable Web server system. Many existing cluster-based Web servers, however, do not fully utilize the underlying features of the cluster environment, and most parallel web servers are designed for homogeneous clusters. In this paper, we present a pure-Java-implemented parallel Web server that can run on heterogeneous clusters. The core of the proposed system is an application-level “global object space”, which is an integration of the available physical memory of the cluster nodes for storing frequently requested objects. The global object space provides a unified view of cluster-wide memory resources, and allows transparent accesses to cached objects. Using a technique known as cooperative caching, a requested Web object can be fetched from a node’s local memory cache or a peer node’s memory cache to avoid hot spots and excessive disk operations. A preliminary prototype system has been implemented by modifying the W3C’s Jigsaw Web server. We obtained good speedups in the benchmark tests, indicating that clustering with cooperative caching can greatly improve the performance of a Web server system. 1.

Data reduction is a fundamental operation of parallel computing. We derive lower bounds on communication latency for global data reduction and multiple global data reduction on reconfigurable tori. We present optimal global data reduction algorithms and multiple global data reduction algorithms on reconfigurable tori of any dimension. The formal reduction algorithms we give can make reduction and broadcast operations easy to implement.

A fault-tolerant wormhole routing algorithm using multiphase minimal routing paths for mesh networks is proposed in this paper. When routing messages come in contact with a fault region, they always select a local shortest path around the fault-region in clockwise or counter clockwise direction. The proposed algorithm can tolerate convex fault-connected regions with four virtual channels per physical channel regardless of how processors of different f-polygons overlap. The fault regions divide each routing path into multiple minimal routing paths-a multiphase minimal routing path. The performance of multiphase minimal routing vs. minimal routing is compared by simulation.

We present an adaptive fault-tolerant wormhole routing algorithm for 2D meshes. The main feature is that with the algorithm, a normal routing message, when blocked by some faulty processes would detour along the f-polygons around the fault region. The proposed algorithm can tolerate convex faults with only three virtual channels per physical channel regardless of the overlapping of f-polygons of different fault regions. The proposed algorithm is deadlock-free.

Preparata and Vuillemin proposed the cube-connected cycles (CCC) in 1981, and in the same paper gave an asymptotically-optimal layout scheme for the CCC. While all the known optimal layouts of the CCC, including the Preparata–Vuillemin layout, have long wires, we give a new layout scheme which has no long wires while keeping the asymptotically-optimal area. Hence, we can conclude that the CCC can be laid out optimally (within a constant factor) both in area and in wire length. We also show how large a constant-factor blow-up in area is needed in order not to produce any long wire in the layout.

We study the p-median problem which is one the classical problems in location theory. For p = 2 and on a two-dimensional mesh, we give an O(mn 2 p)-time algorithm for solving the problem, where, assuming that m n, m is the number of rows of the mesh containing demand points, n the number of columns containing demand points, and p the number of demand points. 1 Introduction The mesh (and its variant, the torus) is a popular topology for processor interconnection in parallel computers. It has practical advantages such as low degree and perfectly compact layout when compared to other well-known topologies, for example the hypercube. A notable example of parallel computers based on the mesh topology is the iWarp system [4]. Dally has shown that low-dimensional networks have lower latency and higher hot-spot throughput than high-dimensional networks [2]. In this paper, we study the problem of finding a 2-median set in a two-dimensional mesh. The p-median problem is a well-known problem ...

F.P. Preparata and J. Vuillemin (1981) proposed the cube-connected cycles (CCC) and its compact layout. We give a new layout of the CCC which uses less than half the area of the Preparata-Vuillemin layout. We also give a lower bound on the layout area of the CCC. The area of the new layout deviates from this bound by a small constant factor. If we "unfold" the cycles in the CCC, the resulting structure can be laid out in optimal area.

Interval routing is a space-efficient method for point-to-point networks. It is based on labeling the edges of a network with intervals of vertex numbers (called interval labels). An M-label scheme allows up to M labels to be attached on an edge. For arbitrary graphs of size m, n the number of vertices, the problem is to determine the minimum RP necessary for achieving optimality in the length of the longest routing path. The longest routing path resulted from a labeling is an important indicator of the performance of any algorithm that runs on the network. We prove that there exists a graph with D=/spl Omega/(n/sup 1/3/) such that if M/spl les/n/18D-O(/spl radic/n/D) the longest path is no shorter than D+/spl Theta/(D//spl radic/M). As a result, for any M-label 1RS, if the longest path is to be shorter than D+/spl Theta/(D//spl radic/M), at least M=/spl Theta/(n/D) labels per edge would be necessary.

Interval routing is a space-efficient routing method for computer networks. The method is said to be optimal if it can generate optimal routing paths for any source-destination node pair. A path is optimal if it is a shortest path between the two nodes involved. A seminal result in the area, however, has pointed out that ‘the interval routing algorithm cannot be optimal in networks with arbitrary topology’. The statement is correct but the lower bound on the longest routing path that was derived is not. We give the counterproof in this paper and the corrected bound.

F.P. Preparata and J. Vuillemin (1981) proposed the cube connected cycles (CCC) and in the same paper, gave an asymptotically optimal layout scheme for the CCC. We give a new layout scheme for the CCC which requires less than half of the area of the Preparata-Vuillemin layout. We also give a non trivial lower bound on the layout area of the CCC. There is a constant factor of 2 between the new layout and the lower bound. We conjecture that the new layout is optimal (minimal).

In this paper we present a decentralized remapping method for data parallel applications on distributed memory multiprocessors. The method uses a generalized dimension exchange (GDE) algorithm periodically during the execution of an application to balance (remap) the system's workload. We implemented this remapping method in parallel WaTor simulations and parallel image thinning applications, and found it to be effective in reducing the computation time. The average performance gain is about 20% in the WaTor simulation of a 256 × 256 ocean grid on 16 processors, and up to 8% in the thinning of a typical image of size 128 × 128 on eight processors. The performance gains due to remapping in the image thinning case are reasonably substantial given the fact that the application by its very nature does not necessarily favor remapping. We also implemented this remapping method, using up to 32 processors, for partitioning and re-partitioning of grids in computational fluid dynamics. It was found that the GDE-based parallel refinement policy, coupled with simple geometric strategies, produces partitions that are comparable in quality to those from the best serial algorithms. © 1997 John Wiley & Sons, Ltd.

Interval routing is a space-efficient routing method for point-to-point communication networks. The method has drawn considerable attention in recent years because of its being incorporated into the design of a commercially available routing chip. The method is based on proper labeling of edges of the graph with intervals. An optimal labeling would result in routing of messages through the shortest paths. Optimal labelings have existed for regular as well as some of the common topologies, but not for arbitrary graphs. In fact, it has already been shown that it is impossible to find optimal labelings for arbitrary graphs. In this paper, we prove a 7 D/4 - 1 lower bound for interval routing in arbitrary graphs, where D is the diameter—i.e., the best any interval labeling scheme could do is to produce a longest path having a length of at least 7 D/4 - 1. © 1997 John Wiley & Sons, Inc.

For original paper see Vadapalli and Srimani, ibid., vol. 7, no. 1, p 26-32, 1996, where the authors have proposed a new family of Cayley graph interconnection networks of constant degree four. Our comments show that their proposed graph is not new but is the same as the wrap-around butterfly graph. The structural kinship of the proposed graph with the de Bruijn graph is also discussed.

The hypercube as a parallel interconnection network has been studied by many for tens of years due to its many merits. However, its increasing node degree is an obvious weakness. Some networks such as the Cube-Connected Circle and the DeBruijn Network have been proposed to overcome the increasing degree of the hypercube. In this paper, we present a new cost-effective network which outperforms the cube network. It can overcome the increasing degree of the cube network while keeping the advantages of the cube network such as logarithmic diameter, easy routing, optimal fault tolerance, and suitability for the ASCEND/DESCEND class of parallel problems. Furthermore, the proposed network achieves the logarithmic diameter with a very small constant node degree, 3 or 4.

Midimew networks are mesh-connected networks derived from a subset of degree-4 circulant graphs. They have minimum diameter and average distance among all degree-4 circulant graphs, and are better than some of the most common topologies for parallel computers in terms of various cost measures. Among the many midimew networks, the rectangular ones appear to be most suitable for practical implementation. Unfortunately, with the normal way of laying out these networks on a 2D plane, long cross wires that grow with the size of the network exist. In this paper, we propose ways to lay out rectangular midimew networks in a 2D grid so that the length of the longest wire is at most a small constant. We prove that these constants are optimal under the assumption that rows and columns are moved as a whole during the layout process.

We propose a simple algorithm which is based on edge-coloring of system graphs for termination detection of loosely synchronous computations. The proposed algorithm is fully symmetric in that all processors run syntactically identical code and can detect global termination at the same time. Under the 1-port communication model, the algorithm is optimal in terms of termination delay, the difference between the time when a global termination occurs and the time it is detected, in a number of structures-chain, ring of even number of nodes, k-ary n-cube and k-ary n-mesh of low degree, where k is even; and near-optimal for other cases. The optimality analysis is based on results from a related problem, periodic gossiping in edge-colored graphs. This algorithm has been applied to some practical cases in which the overhead due to its execution is found to be insignificant.

Abstract With nearest‐neighbor load‐balancing algorithms, a processor makes balancing decisions based on localized workload information and manages workload migrations within its neighborhood. The paper compares a couple of fairly well‐known nearest‐neighbor algorithms,the dimension‐exchange(DE) andthe diffusion(DF) methods and their several variants—the average dimension‐exchange (ADE), optimally tuned dimension‐exchange (ODE), local average diffusion (ADF) and optimally tuned diffusion (ODF). The measures of interest are their efficiency in driving any initial workload distribution to a uniform distribution and their ability in controlling the growth of the variance among the processors' workloads. The comparison is made with respect to both one‐port and all‐port communication architectures and in consideration of various implementation strategies including synchronous/asynchronous invocation policies and static/dynamic random workload behaviors. It turns out that the dimension‐exchange method outperforms the diffusion method in the one‐port communication model. In particular, the ODE algorithm is best suited for statically synchronous implementations of a load‐balancing process regardless of its underlying communication models. The strength of the diffusion method is in asynchronous implementations in the all‐port communication model; the ODF algorithm performs best in that case. The underlying communication networks considered assume the most popular topologies, the mesh and the torus and their special cases: the hypercube and thek‐aryn‐cube.