Prompt-based offline methods are commonly used to optimize large language model (LLM) responses, but evaluating these responses is computationally intensive and often fails to accommodate diverse response styles. This study introduces a novel online evaluation framework that employs a multi-agent conversational bandit model to select optimal responses while aligning with user preferences dynamically. To tackle challenges such as high-dimensional features, large response sets, adaptive conversational needs, and multi-device access, we propose MACO, Multi-Agent Conversational Online Learning, which comprises two key components: (1) MACO-A: Executed by local agents, it employs an online elimination mechanism to filter out low-quality responses. (2) MACO-S: Executed by the cloud server, it adaptively adjusts selection strategies based on aggregated preference data. An adaptive preference mechanism triggers asynchronous conversations to enhance alignment efficiency. Theoretical analysis demonstrates that MACO achieves near-optimal regret bounds, matching state-of-the-art performance in various degenerate cases. Extensive experiments utilizing Google and OpenAI text embedding models on the real-world datasets with different response styles, combined with Llama and GPT-4o, show that MACO consistently outperforms baseline methods by at least 8.29% across varying response set sizes and numbers of agents.

Large language models (LLMs) exhibit diverse response behaviors, costs, and strengths, making it challenging to select the most suitable LLM for a given user query. We study the problem of adaptive multi-LLM selection in an online setting, where the learner interacts with users through multi-step query refinement and must choose LLMs sequentially without access to offline datasets or model internals. A key challenge arises from unstructured context evolution: the prompt dynamically changes in response to previous model outputs via a black-box process, which cannot be simulated, modeled, or learned. To address this, we propose the first contextual bandit framework for sequential LLM selection under unstructured prompt dynamics. We formalize a notion of myopic regret and develop a LinUCB-based algorithm that provably achieves sublinear regret without relying on future context prediction. We further introduce budget-aware and positionally-aware (favoring early-stage satisfaction) extensions to accommodate variable query costs and user preferences for early high-quality responses. Our algorithms are theoretically grounded and require no offline fine-tuning or dataset-specific training. Experiments on diverse benchmarks demonstrate that our methods outperform existing LLM routing strategies in both accuracy and cost-efficiency, validating the power of contextual bandits for real-time, adaptive LLM selection.

Jiahang Sun, Zhiyong Wang, Runhan Yang, Chenjun Xiao, John C.s. Lui, Zhongxiang Dai. Proceedings of the 64th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). 2026.

Vector data trading is essential for cross-domain learning with vector databases, yet it remains largely unexplored. We study this problem under online learning, where sellers face uncertain retrieval costs and buyers provide stochastic feedback to posted prices. Three main challenges arise: (1) heterogeneous and partial feedback in configuration learning, (2) variable and complex feedback in pricing learning, and (3) inherent coupling between configuration and pricing decisions. We propose a hierarchical bandit framework that jointly optimizes retrieval configurations and pricing. Stage I employs contextual clustering with confidence-based exploration to learn effective configurations with logarithmic regret. Stage II adopts interval-based price selection with local Taylor approximation to estimate buyer responses and achieve sublinear regret. We establish theoretical guarantees with polynomial time complexity and validate the framework on four real-world datasets, demonstrating consistent improvements in cumulative reward and regret reduction compared with existing methods.

Large Language Models (LLMs) are revolutionizing how users interact with information systems, yet their high inference cost poses serious scalability and sustainability challenges. Caching inference responses, allowing them to be retrieved without another forward pass through the LLM, has emerged as one possible solution. Traditional exact-match caching, however, overlooks the semantic similarity between queries, leading to unnecessary recomputation. Semantic caching addresses this by retrieving responses based on semantic similarity, but introduces a fundamentally different cache eviction problem: one must account for mismatch costs between incoming queries and cached responses. Moreover, key system parameters, such as query arrival probabilities and serving costs, are often unknown and must be learned over time. Existing semantic caching methods are largely ad-hoc, lacking theoretical foundations and unable to adapt to real-world uncertainty. In this paper, we present a principled, learning-based framework for semantic cache eviction under unknown query and cost distributions. We formulate both offline optimization and online learning variants of the problem, and develop provably efficient algorithms with state-of-the-art guarantees. We also evaluate our framework on a synthetic dataset, showing that our proposed algorithms perform matching or superior performance compared with baselines.

Proximity graphs are the state-of-the-art solution for approximate nearest neighbor (ANN) search, supporting applications such as Web search and retrieval-augmented generation (RAG). Sustaining long-term performance requires adaptive pruning as data and query workloads evolve. However, existing approaches are largely static and uniform. Adaptive pruning faces three key challenges: temporal drift in data and query distributions, spatial heterogeneity across graph regions, and costly feedback due to graph-level evaluations. We present BANCO, a bandit-based framework for adaptive proximity graph pruning. BANCO unifies diverse pruning strategies within a common decision space and optimizes them via a drift-aware batched bandit algorithm. It addresses temporal drift through drift-aware updates, captures spatial heterogeneity using contextual features for region-specific pruning, and reduces evaluation costs through batched feedback aggregation. We establish a dynamic regret bound with sublinear loss and polynomial computational complexity. Extensive experiments on four real-world datasets demonstrate that BANCO helps maintain long-term ANN search efficiency and accuracy under evolving data and workloads.

Multi-behavior Session Based Recommendations (MBSBRs) have achieved remarkable results due to considering behavioral heterogeneity in sessions. Yet most existing works only consider binary or continuous behavior dependencies and aim to predict the next item under the target behavior, neglecting users' inherent behavior habits, resulting in learning inaccurate intentions. To tackle the above issues, we propose a novelBehaviorHabits Enhanced Intention Learning framework forSessionBasedRecommendation (BHSBR). Specifically, we focus on the next item recommendation and design a global item transition graph to learn the behavior-aware semantic relationships between items, in order to mine the underlying similarity between items beyond the session. In addition, we construct a hypergraph to extract the diverse behavior habits of users and break through the limitations of temporal relationships in the session. Compared to the existing works, our behavior habit learning method learns behavior dependencies at the user level, which could capture the user's more accurate long-term intentions and reduce the impact of noise behaviors. Extensive experiments on three datasets demonstrate that the performance of our proposedBHSBRis superior to SOTA. Further ablation experiments fully illustrate the effectiveness of our various modules.

In the bigdata era, data trading significantly enhances data-driven decision-making by facilitating data sharing. Streaming data from sources such as mobile devices and social media platforms creates new opportunities and challenges for data trading. Traditional data trading methods, designed for one time queries over static data base snapshots, neglect the growing need for trading continuous queries over streaming data. If applied directly to continuous queries, existing methods often result in repeated and imprecise charges that reduce the seller's profit, as they do not consider computation sharing during continuous query execution. To address these challenges, we propose CQ Trade, the first mechanism for continuous query based data trading, which incorporates computation sharing in query execution and integrates seamlessly with existing trading mechanisms. Our contributions are threefold: (1) we provide a theoretical analysis of prevalent computation-sharing techniques, including costmodeling and closed-form computation-sharing strategy derivation; (2) we formulate a general optimization problem to maximize the seller's profit, adaptable to various computation-sharing techniques; (3) we identify that our op timization problem merges vector bin packing and multidimensional knapsack challenges, and we tackle this complexity with a tailored branch-and-price algorithm that decomposes the problem in to a master problem and multiple sub-problems, achieving a globally optimal solution. Evaluation shows CQ Trade improve strading success rate by 12.8% and increases seller profit by 28.7% compared to traditional methods.

Session-based recommendation (SBR) systems have increasingly focused on hypergraph-based approaches due to their potent capability in capturing high-order item relationships. Typically, existing approaches rely on sequential item relations to manually construct fixed hypergraphs. However, this methodology neglects the multiple relations inherent in the original sequences, thereby impeding the hypergraph’s precision in discerning user preferences. Furthermore, the rigidity of fixed hypergraph structures tends to emphasize explicit relationships, ignoring the latent implicit patterns. In light of this, we present a novel Multi-relation enhanced Dynamic HyperGraph (MDHG) learning framework for session-based recommendation, to model intricate and variable item relations. Initially, we establish three distinct relation graphs which capture separate user behavior patterns to extract personalized interest preferences under differentiated intentions. Subsequently, we propose an enhanced dynamic hypergraph paradigm that adaptively generates hypergraph structures based on prior relation graph, thereby reinforcing and unveiling implicit connectivity relations in a layer-aware manner. Finally, to mitigate the noise among diverse relations, we introduce the maximum mutual information auxiliary task and employ the attention mechanism as a cross-relation aggregator. Extensive experiments on various real-world datasets verify the superiority of our MDHG model. Our code is publicly available at https://github.com/Qin-lab-code/MDHG .

Conversational Recommender Systems (CRSs) interact with users through natural language to provide recommendations and generate responses. Due to limited information in conversation, existing works utilize KGs or reviews to improve CRS. Despite achievements, they overlook co-occurrence relations which have shown effectiveness in collaborative filtering systems. In this work, we first propose a novel framework named CoCRS , aiming to incorporate Co-occurrences into the Review-based Conversation Recommendation Systems . In CoCRS, we mine co-occurrences from two aspects: (1) item and entity , (2) user and item . For the first one, we extract entities from redundant review texts by KG and construct a relation-aware item-entity heterogeneous graph. In the second aspect, we analyze review sentiments and construct a sentiment-aware user-item bipartite graph. We encode two graphs to obtain user and entity embeddings. Since users in CRS are anonymous, we generate a virtual similar user representation to match reviews with users. Besides, we capture time-aware preference representation from two-time dimensions. Finally, we generate word-level user representation with word-oriented KG and model user preference by integrating the above representations. Extensive experiments demonstrate that CoCRS outperforms baselines and the cold-start experiment highlights its robustness. The Large Language Model (LLM) experiment illustrates the significant role of co-occurrence relationships in LLM-based CRS. Our code are available at https://github.com/Qin-lab-code/CoCRS .

In recent years, deep neural networks (DNNs) have been extensively utilized to provide vehicular intelligent services. Given the limited computing capabilities of vehicles, collaborative vehicle-edge DNN inference has emerged as a promising approach. This method partitions the DNN, then distributes parts to the vehicle or the edge,e.g.,roadside unit (RSU), for sequential inferences. However, determining the optimal DNN partition is challenging due to the uneven load distribution of DNN models and varying road traffic conditions. Moreover, vehicle movement can cause loss of inference results if vehicles leave the RSU signal coverage. To this end, we propose a novel online learning-based collaborative DNN Inference frameworkMCI.MCIutilizes multiple RSUs to assist vehicles with sequential inference and ensure reliable data transmission. To reduce learning cost,MCIdesigns a trajectory prediction to analyze vehicle context before making decisions. Then,MCIcombines the classical EXP4 and LinUCB algorithms to learn system dynamics and make effective scheduling decisions. We prove thatMCIachieves a sublinear regret bound of$O(T^{3/4} \sqrt {\log T})$. Extensive experimental results show thatMCIreduces latency by up to 68% and has a lower failure rate, compared to state-of-the-art algorithms.

Combinatorial multi-armed bandit (CMAB) is a fundamental online learning framework that can optimize cumulative rewards in networked systems under uncertainty. Real-world applications like content delivery and channel allocation often feature binary base arm rewards and nonlinear total reward functions. This paper introduces combinatorial logistic bandits (CLogB), a contextual CMAB framework with the base arm reward modeled as a nonlinear logistic function of the context, and the feedback is governed by a general arm-triggering process. We study CLogB with smooth reward functions, covering applications such as online content delivery, online multi-LLM selection, and dynamic channel allocation. Our first algorithm, CLogUCB, uses a variance-agnostic exploration bonus and achieves a regret bound of Õ(d√κKT), where d is the feature dimension, κ reflects logistic model nonlinearity,Kis the maximum number of triggered arms, and Õ ignores logarithmic factors. This improves on prior results by Õ (√κ). We further propose VA-CLogUCB, a variance-adaptive enhancement achieving regret bounds of Õ(d√KT) under standard smoothness conditions and Õ (d√T) under stronger variance conditions, removing dependence on K. For time-invariant feature maps, we enhance computational efficiency by avoiding nonconvex optimization while maintaining Õ(d√T) regret. Experiments on synthetic and real-world datasets validate the superior performance of our algorithms, demonstrating their effectiveness and scalability for real-world networked systems.

A quantum switch is one of the most fundamental network elements for connecting different quantum devices. In this paper, we explore the “optimal entanglement policy” of a quantum switch under a scenario where the stored and entangled qubits in the quantum switch may undergo a decoherence process. Finding an optimal entanglement policy is important as it enables a quantum switch to make a judicious basis measurement based on the number of existing link-level entanglements to maximize the “weighted throughput”. We use a Markov decision process framework to model the dynamics of the quantum switch, and theoretically reveal a threshold-based relationship between bipartite and tripartite policies under a very general class of weight functions with a weight parameter β. We further extend our analysis to uncover athreshold-based structure of optimal policies. In particular, the optimal policy for the quantum switch is a bipartite or tripartite policy when β is below a threshold β∗Bor above a threshold β∗T, respectively. When β∗B∗T, the optimal policy becomes a “threshold-based and state-dependent entanglement policy”. We also extend the work to allow a mixture of bipartite and tripartite policies by introducing a state-dependent mixed action. We theoretically show threshold-related relationships between mixed and bipartite/tripartite policies. Moreover, we extend this analysis to study optimal policies and characterize the threshold-based structure when the mixed action is considered. We carry out extensive numerical experiments to confirm that the optimal entanglement policy has such structural property when the mixed action is considered or not.

We study online decision-making problems in network applications using the framework of contextual combinatorial multi-armed bandits (C2MAB). Although bandit methods provide a natural solution, two key challenges arise in practice: corruption in feedback and heterogeneity across clients. Corruption may stem from adversarial behaviors or system anomalies, leading to biased reward estimations, while heterogeneity reflects differences in clients’ environments such as computation capabilities or network conditions. To address these challenges, we formulate the C2MAB under corruption (C2MAB-C) problem and extend it to the setting with heterogeneous environmental parameters. We then propose two novel algorithms, namely CW-C2UCB, which leverages confidence-weighted estimations to mitigate corruption effects, and CW-C2CLUB, which further integrates an online clustering mechanism to adaptively group tasks based on shared structure. We derive tight theoretical regret bounds for both algorithms under various corruption models showing that our upper bounds match the established lower bounds up to logarithmic factors. Empirical results on three real-world applications, content delivery networks, client selection in federated learning, and VR video streaming, demonstrate that our proposed algorithms significantly outperform existing baselines, achieving lower regret and stronger resilience in adversarial environments.

Multiplicative Weight Update (MWU) is an online learning meta-algorithm that has been widely used in sequential decision-making problems. The key idea of MWU is to maintain a distribution as the selection probability allocation to the alternative actions. MWU has been independently rediscovered and investigated in many studies. This paper will revisit MWU from the perspective of fair resource allocation. Specifically, we focus on a well-known fairness concept called weighted alpha-fairness, which was introduced by Mo and Walrand in network bandwidth allocation. We first unveil that MWU inherently adopts the weighted alpha-fair probability allocation in each slot. The fairness level equals to the inverse of the step-size parameter in MWU, and the weight assigned to each action decays exponentially in relation to its accumulated cost. This insight suggests that the use of appropriate weighted-alpha fair allocations for action-taking probability can indeed perform as well as the offline optimal allocation in the long-term. Motivated by this insight, we further investigate whether one could solve more general online resource allocation problems (not limited to the one addressed by MWU) by carefully constructing the weighted-alpha fair allocation for each time slot. To this end, we propose a weighted alpha-fair online allocation framework that carefully constructs the merit-based weights and the increasing fairness levels. Under our proposed framework, the allocation outcome in each time slot satisfies the weighted alpha-fairness principal, and the allocation outcomes also perform asymptotically as well as the offline optimal outcome. We demonstrate how this framework functions in two networking applications. In size-based traffic scheduling, our framework enables the network switches to prioritize short flows and avoid flow starvation without the prior flow size information. In file caching, our framework outperforms several state-of-the-art caching policies up to 21% in terms of cache-hit-ratio.

As users request their preferred metaversal media, e.g., 360-degree video, user requests tracked by metaverse content providers (MCPs) pose significant privacy leakage risks. Unfortunately, existing privacy-enhancing techniques are largely ineffective in protecting user privacy for metaversal content requests since these requests cannot be easily altered or concealed by users and must remain visible to MCPs to ensure accurate content delivery. To safeguard user privacy in metaverse multimedia services (MMS), one practical approach is pre-fetching multimedia content (e.g., short videos, video patches in 360$^\circ$videos) that is not directly related to users' interests, thereby preventing MCPs from accurately inferring user preferences. However, plain pre-fetching strategies encounter a critical trade-off between privacy protection and edge caching performance given that MCPs often rely on edges for distributing metaverse content. In this paper, we propose acache-friendly and privacy-awarecontent pre-fetching(CRACE) algorithm for user devices (UDs) along with a complementary caching algorithm for edge caches (ECs). CRACE effectively mitigates privacy leakage in metaverse content requests while minimally impacting caching performance. Specifically, we introduce a novel privacy model to guide pre-fetching decisions and formulate a Stackelberg game to analyze strategic interactions between UDs and ECs. We derive optimal strategies that maximize their respective utilities and demonstrate the existence and uniqueness of the Stackelberg equilibrium. Extensive experiments conducted with real-world data demonstrate that CRACE significantly enhances privacy protection, reducing privacy disclosure by up to 59.03% compared to baseline algorithms, with negligible impact on the edge caching performance.

This paper studies the problem of solving the system of nonlinear equations. We propose the Gram-reduced Levenberg--Marquardt method, which reuses the Gram matrix. Our method has a global convergence guarantee without relying on any step of line-search or solving sub-problems. We show that our method takes a smaller computational complexity than existing Levenberg--Marquardt methods to find the stationary point of the square norm of the equations. We also show that the proposed method enjoys a local superlinear convergence rate under the non-degenerate assumption. Experiments are conducted on real-world applications in scientific computing and machine learning, which validate the efficiency of our method.

Best arm identification (BAI) is a key problem in stochastic multi-armed bandits, where K arms each has an associated reward distribution, and the objective is to minimize the number of queries needed to identify the best arm with high confidence. In this paper, we explore BAI using quantum oracles. For the case where each query probes only one arm (m=1), we devise a quantum algorithm with a query complexity upper bound of O((K/Delta)log(1/delta)), where delta is the confidence parameter and Delta is the reward gap between best and second best arms. This improves on the classical bound by a factor of 1/Delta. For the general case where a single query can probe m arms (1

We investigate the non-stationary stochastic linear bandit problem where the reward distribution evolves each round. Existing algorithms characterize the non-stationarity by the total variation budget $B_K$, which is the summation of the change of the consecutive feature vectors of the linear bandits over $K$ rounds. However, such a quantity only measures the non-stationarity with respect to the expectation of the reward distribution, which makes existing algorithms sub-optimal under the general non-stationary distribution setting. In this work, we propose algorithms that utilize the variance of the reward distribution as well as the $B_K$, and show that they can achieve tighter regret upper bounds. Specifically, we introduce two novel algorithms: Restarted Weighted$\text{OFUL}^+$ and Restarted $\text{SAVE}^+$. These algorithms address cases where the variance information of the rewards is known and unknown, respectively. Notably, when the total variance $V_K$ is much smaller than $K$, our algorithms outperform previous state-of-the-art results on non-stationary stochastic linear bandits under different settings. Experimental evaluations further validate the superior performance of our proposed algorithms over existing works.

Data trading significantly enhances data utility by enabling data sharing across diverse applications. Despite being crucial for real-time analytics and online machine learning, trading continuous queries with streaming data output remains largely unexplored. The inherent characteristics of trading continuous queries pose distinctive technical challenges in scheduling query execution. First, the streaming nature demands online scheduling under information uncertainty, where data utilities and execution costs vary unpredictably during query execution. Second, the intrinsic NP-hardness of the optimization problem, coupled with repeated invocation requirements, necessitates efficient algorithmic solutions to address computational complexity. We present OSTOR, the first online scheduling framework for trading continuous queries. OSTOR aims to maximize social welfare, defined as the difference between buyers' obtained utilities and sellers' execution costs, while achieving both theoretical guarantees and practical efficiency. To handle the information uncertainty, we present a primary-dual decomposition method that transforms the online scheduling problem into multiple one-round integer programming problems, enabling adaptive decision-making that only needs current system information. To address the computational complexity, we design an adaptive dual descent (ADD) algorithm that iteratively optimizes dual variables, achieving a bounded constant approximation ratio in polynomial time. We further enhance OSTOR through structureaware greedy optimization strategies with provable performance guarantees. Extensive experiments demonstrate that OSTOR substantially improves social welfare and reduces query execution costs on both real-world and synthetic datasets, compared to existing data trading methods.

The contextual multi-armed bandit (MAB) problem is crucial in sequential decision-making. A line of research, known as online clustering of bandits, extends contextual MAB by grouping similar users into clusters, utilizing shared features to improve learning efficiency. However, existing algorithms, which rely on the upper confidence bound (UCB) strategy, struggle to gather adequate statistical information to accurately identify unknown user clusters. As a result, their theoretical analyses require several strong assumptions about the "diversity" of contexts generated by the environment, leading to impractical settings, complicated analyses, and poor practical performance. Removing these assumptions has been a long-standing open problem in the clustering of bandits literature. In this work, we provide two partial solutions. First, we introduce an additional exploration phase to accelerate the identification of clusters. We integrate this general strategy into both graph-based and set-based algorithms and propose two new algorithms, UniCLUB and UniSCLUB. Remarkably, our algorithms require substantially weaker assumptions and simpler theoretical analyses while achieving superior cumulative regret compared to previous studies. Second, inspired by the smoothed analysis framework, we propose a more practical setting that eliminates the requirement for i.i.d. context generation used in previous studies, thus enhancing the performance of existing algorithms for online clustering of bandits. Extensive evaluations on both synthetic and real-world datasets demonstrate that our proposed algorithms outperform existing approaches.

A rich line of recent works studies how participants in matching markets learn their unknown preferences through iterative interactions with each other. The two sides of participants in the market can be respectively formulated as players and arms in the bandit problem. To ensure market stability, the objective is to minimize the stable regret of each player. Though existing works provide significant theoretical upper bounds for players' stable regret, the results heavily rely on the assumption that each participant has a strict preference ranking. However, in real applications, multiple candidates (e.g., workers in the labor market and students in school admission) usually demonstrate comparable performance levels, making it challenging for participants (e.g., employers and schools) to differentiate and rank their preferences. To deal with the potential indifferent preferences, we propose an adaptive exploration algorithm based on arm-guided Gale-Shapley (AE-AGS). We show that its stable regret is of order $O(NK \log T / \Delta^2)$, where $N$ is the number of players, $K$ the number of arms, $T$ the total time horizon, and $\Delta$ the minimum non-zero preference gap. Extensive experiments demonstrate the algorithm's effectiveness in handling such complex situations and its consistent superiority over baselines.

This paper investigates stochastic multi-armed bandit algorithms that are robust to adversarial attacks, where an attacker can first observe the learner's action and *then* alter their reward observation. We study two cases of this model, with or without the knowledge of an attack budget $C$, defined as an upper bound of the summation of the difference between the actual and altered rewards. For both cases, we devise two types of algorithms with regret bounds having additive or multiplicative $C$ dependence terms. For the known attack budget case, we prove our algorithms achieve the regret bound of ${O}((K/\Delta)\log T + KC)$ and $\tilde{O}(\sqrt{KTC})$ for the additive and multiplicative $C$ terms, respectively, where $K$ is the number of arms, $T$ is the time horizon, $\Delta$ is the gap between the expected rewards of the optimal arm and the second-best arm, and $\tilde{O}$ hides the logarithmic factors. For the unknown case, we prove our algorithms achieve the regret bound of $\tilde{O}(\sqrt{KT} + KC^2)$ and $\tilde{O}(KC\sqrt{T})$ for the additive and multiplicative $C$ terms, respectively. In addition to these upper bound results, we provide several lower bounds showing the tightness of our bounds and the optimality of our algorithms. These results delineate an intrinsic separation between the bandits with attacks and corruption models.

Learning a transition model via Maximum Likelihood Estimation (MLE) followed by planning inside the learned model is perhaps the most standard and simplest Model-based Reinforcement Learning (RL) framework. In this work, we show that such a simple Model-based RL scheme, when equipped with optimistic and pessimistic planning procedures, achieves strong regret and sample complexity bounds in online and offline RL settings. Particularly, we demonstrate that under the conditions where the trajectory-wise reward is normalized between zero and one and the transition is time-homogenous, it achieves nearly horizon-free and second-order bounds.

The combinatorial multi-armed bandit (CMAB) is a fundamental sequential decision-making framework, extensively studied over the past decade. However, existing work primarily focuses on the online setting, overlooking the substantial costs of online interactions and the readily available offline datasets. To overcome these limitations, we introduce Off-CMAB, the first offline learning framework for CMAB. Central to our framework is the combinatorial lower confidence bound (CLCB) algorithm, which combines pessimistic reward estimations with combinatorial solvers. To characterize the quality of offline datasets, we propose two novel data coverage conditions and prove that, under these conditions, CLCB achieves a near-optimal suboptimality gap, matching the theoretical lower bound up to a logarithmic factor. We validate Off-CMAB through practical applications, including learning to rank, large language model (LLM) caching, and social influence maximization, showing its ability to handle nonlinear reward functions, general feedback models, and out-of-distribution action samples that excludes optimal or even feasible actions. Extensive experiments on synthetic and real-world datasets further highlight the superior performance of CLCB.

In this work, we design quantum algorithms that are more efficient than classical algorithms to solve time-dependent and finite-horizon Markov Decision Processes (MDPs) in two distinct settings: (1) In the exact dynamics setting, where the agent has full knowledge of the environment’s dynamics (i.e., transition probabilities), we prove that our Quantum Value Iteration (QVI) algorithm QVI-1 achieves a quadratic speedup in the size of the action space $(A)$ compared with the classical value iteration algorithm for computing the optimal policy ($\pi^{\ast}$) and the optimal V-value function ($V_{0}^{\ast}$). Furthermore, our algorithm QVI-2 provides an additional speedup in the size of the state space $(S)$ when obtaining near-optimal policies and V-value functions. Both QVI-1 and QVI-2 achieve quantum query complexities that provably improve upon classical lower bounds, particularly in their dependences on $S$ and $A$. (2) In the generative model setting, where samples from the environment are accessible in quantum superposition, we prove that our algorithms QVI-3 and QVI-4 achieve improvements in sample complexity over the state-of-the-art (SOTA) classical algorithm in terms of $A$, estimation error $(\epsilon)$, and time horizon $(H)$. More importantly, we prove quantum lower bounds to show that QVI-3 and QVI-4 are asymptotically optimal, up to logarithmic factors, assuming a constant time horizon.

The contextual multi-armed bandit (MAB) is a widely used framework for problems requiring sequential decision-making under uncertainty, such as recommendation systems. In applications involving a large number of users, the performance of contextual MAB can be significantly improved by facilitating collaboration among multiple users. This has been achieved by the clustering of bandits (CB) methods, which adaptively group the users into different clusters and achieve collaboration by allowing the users in the same cluster to share data. However, classical CB algorithms typically rely on numerical reward feedback, which may not be practical in certain real-world applications. For instance, in recommendation systems, it is more realistic and reliable to solicit preference feedback between pairs of recommended items rather than absolute rewards. To address this limitation, we introduce the first "clustering of dueling bandit algorithms" to enable collaborative decision-making based on preference feedback. We propose two novel algorithms: (1) Clustering of Linear Dueling Bandits (COLDB) which models the user reward functions as linear functions of the context vectors, and (2) Clustering of Neural Dueling Bandits (CONDB) which uses a neural network to model complex, non-linear user reward functions. Both algorithms are supported by rigorous theoretical analyses, demonstrating that user collaboration leads to improved regret bounds. Extensive empirical evaluations on synthetic and real-world datasets further validate the effectiveness of our methods, establishing their potential in real-world applications involving multiple users with preference-based feedback.

For question-answering (QA) tasks, in-context learning (ICL) enables language models (LMs) to generate responses without modifying their parameters by leveraging examples provided in the input. However, the effectiveness of ICL heavily depends on the availability of high-quality examples, which are often scarce due to data privacy constraints, annotation costs, and distribution disparities. A natural solution is to utilize examples stored on client devices, but existing approaches either require transmitting model parameters—incurring significant communication overhead—or fail to fully exploit local datasets, limiting their effectiveness. To address these challenges, we propose Federated In-Context Learning (Fed-ICL), a general framework that enhances ICL through an iterative, collaborative process. Fed-ICL progressively refines responses by leveraging multi-round interactions between clients and a central server, improving answer quality without the need to transmit model parameters. We establish theoretical guarantees for the convergence of Fed-ICL and conduct extensive experiments on standard QA benchmarks, demonstrating that our proposed approach achieves strong performance while maintaining low communication costs.

In this work, we study offline reinforcement learning (RL) with zero-shot generalization property (ZSG), where the agent has access to an offline dataset including experiences from different environments, and the goal of the agent is to train a policy over the training environments which performs well on test environments without further interaction. Existing work showed that classical offline RL fails to generalize to new, unseen environments. We propose pessimistic empirical risk minimization (PERM) and pessimistic proximal policy optimization (PPPO), which leverage pessimistic policy evaluation to guide policy learning and enhance generalization. We show that both PERM and PPPO are capable of finding a near-optimal policy with ZSG. Our result serves as a first step in understanding the foundation of the generalization phenomenon in offline reinforcement learning.

This paper investigates the fusion of absolute (reward) and relative (dueling) feedback in stochastic bandits, where both feedback types are gathered in each decision round. We derive a regret lower bound, demonstrating that an efficient algorithm may incur only the smaller among the reward and dueling-based regret for each individual arm. We propose two fusion approaches: (1) a simple elimination fusion algorithm that leverages both feedback types to explore all arms and unifies collected information by sharing a common candidate arm set, and (2) a decomposition fusion algorithm that selects the more effective feedback to explore the corresponding arms and randomly assigns one feedback type for exploration and the other for exploitation in each round. The elimination fusion experiences a suboptimal multiplicative term of the number of arms in regret due to the intrinsic suboptimality of dueling elimination. In contrast, the decomposition fusion achieves regret matching the lower bound up to a constant under a common assumption. Extensive experiments confirm the efficacy of our algorithms and theoretical results.

Co-branding has become a vital strategy for businesses aiming to expand market reach within recommendation systems. However, identifying effective cross-industry partnerships remains challenging due to resource imbalances, uncertain brand willingness, and ever-changing market conditions. In this paper, we provide the first systematic study of this problem and propose a unified online-offline framework to enable co-branding recommendations. Our approach begins by constructing a bipartite graph linking ''initiating'' and ''target'' brands to quantify co-branding probabilities and assess market benefits. During the online learning phase, we dynamically update the graph in response to market feedback, while striking a balance between exploring new collaborations for long-term gains and exploiting established partnerships for immediate benefits. To address the high initial co-branding costs, our framework mitigates redundant exploration, thereby enhancing short-term performance while ensuring sustainable strategic growth. In the offline optimization phase, our framework consolidates the interests of multiple sub-brands under the same parent brand to maximize overall returns, avoid excessive investment in single sub-brands, and reduce unnecessary costs associated with over-prioritizing a single sub-brand. We present a theoretical analysis of our approach, establishing a highly nontrivial sublinear regret bound for online learning in the complex co-branding problem, and enhancing the approximation guarantee for the NP-hard offline budget allocation optimization. Experiments on both synthetic and real-world co-branding datasets demonstrate the practical effectiveness of our framework, with at least 12% improvement.

Sequential recommendation (SR) is widely deployed in e-commerce platforms, streaming services, etc., revealing significant potential to enhance user experience. The core of SR lies in exploring the sequential relationships in historical user-item interactions. However, existing methods often overlook two critical factors: irregular user interests between interactions and highly uneven item distributions over time. The former factor implies that actual user preferences are not always continuous, and long-term historical interactions may not be relevant to current purchasing behavior. Therefore, relying only on these historical interactions for recommendations may result in a lack of user interest at the target time. The latter factor, characterized by peaks and valleys in interaction frequency, may result from seasonal trends, special events, or promotions. These externally driven distributions may not align with individual user interests, leading to inaccurate recommendations. To address these deficiencies, we propose TGODE to both enhance and capture the long-term historical interactions. Specifically, we first construct the user time graph and item evolution graph, which utilize user personalized preferences and global item distribution information, respectively. To tackle the temporal sparsity caused by irregular user interactions, we design a time-guided diffusion generator to automatically obtain an augmented time-aware user graph. Additionally, we devise a user interest truncation factor to efficiently identify sparse time intervals and achieve balanced preference inference. After that, the augmented user graph and item graph are fed into a generalized graph neural ordinary differential equation (ODE) to align with the evolution of user preferences and item distributions. This allows two patterns of information evolution to be matched over time. Experimental results demonstrate that TGODE outperforms baseline methods across five datasets, with improvements ranging from 10% to 46%. The code is available at https://github.com/Qin-lab-code/TGODE.

Conversational recommender systems proactively query users with relevant ''key terms'' and leverage the feedback to elicit users' preferences for personalized recommendations. Conversational contextual bandits, a prevalent approach in this domain, aim to optimize preference learning by balancing exploitation and exploration. However, several limitations hinder their effectiveness in real-world scenarios. First, existing algorithms employ key term selection strategies with insufficient exploration, often failing to thoroughly probe users' preferences and resulting in suboptimal preference estimation. Second, current algorithms typically rely on deterministic rules to initiate conversations, causing unnecessary interactions when preferences are well-understood and missed opportunities when preferences are uncertain. To address these limitations, we propose three novel algorithms: CLiSK, CLiME, and CLiSK-ME. CLiSK introduces smoothed key term contexts to enhance exploration in preference learning, CLiME adaptively initiates conversations based on preference uncertainty, and CLiSK-ME integrates both techniques. We theoretically prove that all three algorithms achieve a tighter regret upper bound of O (√dTlogT) with respect to the time horizon T, improving upon existing methods. Additionally, we provide a matching lower bound Ω(√dT) for conversational bandits, demonstrating that our algorithms are nearly minimax optimal. Extensive evaluations on both synthetic and real-world datasets show that our approaches achieve at least a 14.6% improvement in cumulative regret.

This paper investigates convex-concave minimax optimization problems where only the function value access is allowed. We introduce a class of Hessian-aware quantum zeroth-order methods that can find the $\epsilon$-saddle point within $\tilde{\mathcal{O}}(d^{2/3}\epsilon^{-2/3})$ function value oracle calls. This represents an improvement of $d^{1/3}\epsilon^{-1/3}$ over the $\mathcal{O}(d\epsilon^{-1})$ upper bound of classical zeroth-order methods, where $d$ denotes the problem dimension. We extend these results to $\mu$-strongly-convex $\mu$-strongly-concave minimax problems using a restart strategy, and show a speedup of $d^{1/3}\mu^{-1/3}$ compared to classical zeroth-order methods. The acceleration achieved by our methods stems from the construction of efficient quantum estimators for the Hessian and the subsequent design of efficient Hessian-aware algorithms. In addition, we apply such ideas to non-convex optimization, leading to a reduction in the query complexity compared to classical methods.

Evolving graph processing has become a critical component in various applications and is gaining increasing attention. However, existing evolving graph systems suffer from cache contention and workload imbalance between threads, which leads to poor scalability and performance degradation on modern multi-core computers.

Large language models (LLMs) demonstrate remarkable capabilities but face substantial serving costs due to their high memory demands, with the key-value (KV) cache being a primary bottleneck. State-of-the-art KV cache compression techniques, such as quantization and pruning, apply uniform treatment to both keys and values, and discard unimportant tokens entirely, overlooking the fine-grained distinctions in the significance of individual KV cache components. To address such limitations, we introduce DiffKV, a novel framework for efficient KV cache compression that exploits three levels of differentiation in the KV cache: (1) the differing impact of keys and values on attention computation, (2) the varying importance of tokens, and (3) the diverse dynamic sparsity patterns across attention heads. These levels of differentiation introduce irregular memory usage patterns across different requests and attention heads, posing significant scalability challenges for memory management. To address these challenges, DiffKV proposes an on-GPU memory manager that compacts fragmented free memory list into contiguous regions in parallel, effectively translating sparsity in the KV cache into performance gains. We evaluate DiffKV on several mainstream LLMs, including the emerging thinking models that generate extended chains of thought. DiffKV is able to compress the KV cache by 2.7× to 5.7× with near-lossless accuracy on complex workloads requiring sophisticated reasoning and long-generation capabilities, and enhances throughput by 1.9× to 5.4×.

In conversational recommender systems, interactively presenting queries and leveraging user feedback are crucial for efficiently estimating user preferences and improving recommendation quality. Selecting optimal queries in these systems is a significant challenge that has been extensively studied as a sequential decision problem. The expected value of information (EVOI), which computes the expected reward improvement, provides a principled criterion for query selection. However, it is computationally expensive and lacks theoretical performance guarantees. Conversely, conversational bandits offer provable regret upper bounds, but their query selection strategies yield only marginal regret improvements over non-conversational approaches. To address these limitations, we integrate EVOI within the conversational bandit framework by proposing a new conversational mechanism featuring two key techniques: (1) gradient-based EVOI, which replaces the complex Bayesian updates in conventional EVOI with efficient stochastic gradient descent, significantly reducing computational complexity and facilitating theoretical analysis; and (2) smoothed key term contexts, which enhance exploration by adding random perturbations to uncover more specific user preferences. Our approach applies to both Bayesian (Thompson Sampling) and frequentist (UCB) variants of conversational bandits. We introduce two new algorithms, ConTS-EVOI and ConUCB-EVOI, and rigorously prove that they achieve substantially tighter regret bounds, with both algorithms offering a √d improvement in their dependence on the time horizon T, where d is the dimension of the feature space. Extensive evaluations on synthetic and real-world datasets validate the effectiveness of our methods.

Edge computing has become a key technology to enable various Internet of Things (IoT) applications. We envision that in the future, edge computing systems will be platforms like crowdsourcing websites where IoT application providers can offload their tasks to the platform and pay it via the edge computing services, and the platform needs to seek appropriate edge servers (ESs) for executing tasks. To ensure ESs participate and provide good performance, i.e., to meet the stringent QoS requirement of IoT applications, the platform needs to properly reward them for computing services. In this paper, we consider the scenario where both the platform and ESs are self-interested entities, and focus on the setting that the payment made by application providers is ex-ante. We formulate a joint revenue maximization, resource allocation and task offloading optimization problem, and tackle it with a Stackelberg game formulation. A centralized algorithm based on Bayesian Optimization is proposed to solve the game. Moreover, we consider a practical setting where the platform is unable to collect full information when application providers and ESs may refuse to provide their sensitive information. To this end, we develop a decentralized solution based on neural network optimization together with a privacy-preserving information exchange protocol. We evaluate both mechanisms through numerical studies, and results indicate they are effective as compared to representative baselines.

Abstract Unbalanced dimensions are crucial characteristics in various minimax optimization problems, such as few-shot learning (Cortes and Mohri in Adv Neural Inf Process Syst 16, 2003; Ying et al. in Adv Neural Inf Process Syst 29, 2016) and fairness-aware machine learning (Lowd and Meek, in: Proceedings of the eleventh ACM SIGKDD international conference on knowledge discovery in data mining, 2005; Zhang et al., in: Proceedings of the 2018 AAAI/ACM conference on AI, ethics, and society, 2018). In this paper, we propose a communication-efficient second-order method named (Partially Approximate Newton methods for Distributed minimAx) to solve problems with unbalanced dimensions. requires almost the same per-iteration communication cost as the first-order methods by utilizing the special problem structure in its design for data exchange between the client and server. More importantly, it exhibits a superior linear-quadratic convergence rate and significantly reduces the total number of communication rounds through the efficient use of second-order information. We also develop based on the framework of , which further reduces the computation cost of the latter one by performing sketching operations on each client. Through comprehensive theoretical analysis and empirical evaluations, we demonstrate the superior performance of the proposed methods compared to existing state-of-the-art methods.

This paper proposes a replacement algorithm for file caching in mobile edge computing (MEC) networks. While there are numerous schemes for file replacement, it remains a challenge to achieve good, robust, and predictable performance simultaneously. To address this challenge, we introduce a general scheme called Incremental Least-Recently-Used (iLRU), which builds on the classic Least-Recently-Used (LRU) algorithm. iLRU initially caches only a “portion” of the file upon the first request and incrementally caches more when there are more requests for the file. In this regard, the request frequency can be inferred from the cached size without incurring additional overhead, where a larger cached size represents a higher request frequency. We derive the theoretical hit ratio of iLRU based on the Time-to-Live (TTL) analysis. With the Time-to-Live (TTL) analysis, we can theoretically derive the hit ratio and properties of iLRU and notably show that iLRU allocates more cache space to popular files, resulting in a higher hit ratio than LRU. Simulation results demonstrate the superior performance of iLRU and validate the accuracy of the theoretical hit ratio. Furthermore, we conduct simulations over various real-world traces to show that iLRU outperforms existing schemes across various real-world traces, defenestrating the robustness of iLRU.

Entanglement distribution via probabilistic entanglement swapping across a quantum repeater chain connecting two quantum nodes is a challenging problem. The difficulty lies in the exponential number of possible swapping structures within the repeater chain, necessitating efficient search algorithms, especially as the chain length increases. In this paper, we first explore the algorithmic design to facilitate the search for the optimal swapping structure along a repeater chain, aiming to maximize the entanglement distribution rate. Second, we examine the computational complexities of various algorithms and find that prior approaches exhibit excessively high complexities. Thus, we propose an efficient dynamic programming-based algorithm, FastHED, that leverages heuristics to expedite the search for the optimal swapping structure. Our theoretical analysis reveals that the upper bound of the proposed algorithm’s computational complexity is$O(n(\log n)^{3})$(more precisely,$O(n(\log n)^{2} \log \log n)$when$n\le 2^{29}$), a significant improvement over the existing algorithm with a complexity of$O(n^{2} \log n)$, where n denotes the repeater chain’s length. Additionally, we design a best-first framework to evaluate the performance of different algorithms. Numerical results show that our algorithm achieves a higher average entanglement distribution rate than existing algorithms.

The Probabilistic Maximum Coverage (PMC) problem plays a pivotal role in modeling various network applications, such as mobile crowdsensing, which involves selecting nodes within a graph that probabilistically cover other nodes. Our study focuses on PMC within the framework of online learning, termed the PMC bandit, where the network parameters are initially unknown. In this scenario, the decision-maker is tasked with learning these parameters to maximize the cumulative rewards from covered nodes. Despite prior research on the PMC bandit, we propose a novel variant, dynamic PMC-G bandit, which extends the semi-bandit feedback model to represent applications more accurately. To tackle the complexities of the time-varying combinatorial arm set rather than traditional static, we enhance the Combinatorial Upper Confidence Bound (CUCB) algorithms by developing two innovative variance-aware strategies: the Variance-Adaptive Combinatorial Upper Confidence Bound (VACUCB) for probabilistically triggered arms, and the Action-Based Combinatorial Upper Confidence Bound (ABCUCB) for self-reliant arms, i.e., independent arms with probabilistically triggered outcomes. Based on variance-aware properties, our contributions notably reduce the dependence on the number of nodes$K$selected per round, demonstrating that: (i) VACUCB effectively minimizes the regret associated with the triggered arms, enhancing the CUCB by a factor of$\tilde{O}(K)$; (ii) ABCUCB further diminishes the dependence on$K$in the leading term. Empirical results from synthetic and real-world datasets confirm that our proposed algorithms outperform current benchmarks in three network applications.

Distributed graph analysis usually partitions a large graph into multiple small-sized subgraphs and distributes them into a cluster of machines for computing. Therefore, graph partitioning plays a crucial role in distributed graph analysis. However, the widely used existing graph partitioning schemes balance only in one dimension (number of edges or vertices) or incur a large number of edge cuts, so they degrade the performance of distributed graph analysis. In this article, we propose a novel graph partition scheme BPart and two enhanced algorithms BPart-C and BPart-S to achieve a balanced partition for both vertices and edges, and also reduce the number of edge cuts. Besides, we also propose a neighbor-aware caching scheme to further reduce the number of edge cuts so as to improve the efficiency of distributed graph analysis. Our experimental results show that BPart-C and BPart-S can achieve a better balance in both dimensions (the number of vertices and edges), and meanwhile reducing the number of edge cuts, compared to multiple existing graph partitioning algorithms, i.e., Chunk-V, Chunk-E, Fennel, and Hash. We also integrate these partitioning algorithms into two popular distributed graph systems, KnightKing and Gemini, to validate their impact on graph analysis efficiency. Results show that both BPart-C and BPart-S can significantly reduce the total running time of various graph applications by up to 60% and 70%, respectively. In addition, the neighbor-aware caching scheme can further improve the performance by up to 24%.

Reposting plays an essential role in boosting visibility on online social networks (OSNs). In this paper, we study the problem of designing “reposting service” in an OSN to incentivize “transactions” between requesters (users who seek to enhance visibility) and suppliers (users who are willing to repost if certain incentives are given), and maximize the welfare increase accumulated through a given time horizon. We formulate a mathematical model for reposting which captures various factors like click-through rates (CTRs), requesters’ valuations and suppliers’ costs. We formulate the problem of maximizing the welfare increase via judiciously assigning suppliers to requesters from two aspects: (a) “user-centric” and (b) “platform-centric”. The user-centric aspect deals with situations where requesters and suppliers collaborate and share valuations and costs. To address the challenge of unknown CTRs, we propose an online learning protocol and achieve a sub-linear regret. The platform-centric aspect corresponds to the scenario where users keep their valuations or costs private. To address the challenges of unknown CTRs, valuations and costs, we design an “explore-then-commit” online protocol. We prove the truthfulness of the proposed online protocol, and we also prove that this protocol has a sub-linear regret. Lastly, we conduct extensive experiments on six public datasets to evaluate the effectiveness and scalability of the proposed protocols.

We study the problem of federated contextual combinatorial cascading bandits, where agents collaborate under the coordination of a central server to provide tailored recommendations to users. Existing works consider either a synchronous framework, necessitating full agent participation and global synchronization, or assume user homogeneity with identical behaviors. We overcome these limitations by considering (1) federated agents operating in an asynchronous communication paradigm, where no mandatory synchronization is required and all agents communicate independently with the server, (2) heterogeneous user behaviors, where users can be stratified into latent user clusters, each exhibiting distinct preferences. For this setting, we propose a UCB-type algorithm with delicate communication protocols. Through theoretical analysis, we give sub-linear regret bounds on par with those achieved in the synchronous framework, while incurring only logarithmic communication costs. Empirical evaluation on synthetic and real-world datasets validates our algorithm's superior performance in terms of regrets and communication costs.

We study the stochastic combinatorial semi-bandit problem with unrestricted feedback delays under merit-based fairness constraints. This is motivated by applications such as crowdsourcing, and online advertising, where immediate feedback is not immediately available and fairness among different choices (or arms) is crucial. We consider two types of unrestricted feedback delays: reward-independent delays where the feedback delays are independent of the rewards, and reward-dependent delays where the feedback delays are correlated with the rewards. Furthermore, we introduce merit-based fairness constraints to ensure a fair selection of the arms. We define the reward regret and the fairness regret and present new bandit algorithms to select arms under unrestricted feedback delays based on their merits. We prove that our algorithms all achieve sublinear expected reward regret and expected fairness regret, with a dependence on the quantiles of the delay distribution. We also conduct extensive experiments using synthetic and real-world data and show that our algorithms can fairly select arms with different feedback delays.

In the era of big data, data trading significantly enhances data-driven technologies by facilitating data sharing. Despite the clear advantages often experienced by data users when incorporating multiple sources, the topic of multi-source data trading remains largely unexplored. This paper designs a novel data trading framework, which enables multi-source data trading through multi-source cooperation. The proposed framework aims to improve data usage efficiency and increase seller revenue. In particular, we model data sellers’ cooperative decisions through the Nash bargaining framework and systematically outline the interactions between sellers and buyers as a two-stage Stackelberg game. A key contribution of this work is the consideration of coupling among diverse data products, which is essential but often overlooked in prior studies. We properly classify data’s utility into endogenous and relational categories to disentangle the coupling. Despite the inherent non-convex nature of the optimization problem, we methodically derive the closed-form optimal solutions by decomposing the problem into several subproblems. Interestingly, we reveal that, under our proposed framework, sellers’ revenue initially remains steady with the increase of product coupling level, but begins to rise once the level exceeds a certain threshold due to the substitute effect. Finally, experimental results show that our proposed framework can improve the seller’s profit by up to 46.32% compared to traditional data trading methods in the current data market.

We introduce a novel framework of combinatorial multi-armed bandits (CMAB) with multivariant and probabilistically triggering arms (CMAB-MT), where the outcome of each arm is a $d$-dimensional multivariant random variable and the feedback follows a general arm triggering process. Compared with existing CMAB works, CMAB-MT not only enhances the modeling power but also allows improved results by leveraging distinct statistical properties for multivariant random variables. For CMAB-MT, we propose a general 1-norm multivariant and triggering probability-modulated smoothness condition, and an optimistic CUCB-MT algorithm built upon this condition. Our framework can include many important problems as applications, such as episodic reinforcement learning (RL) and probabilistic maximum coverage for goods distribution, all of which meet the above smoothness condition and achieve matching or improved regret bounds compared to existing works. Through our new framework, we build the first connection between the episodic RL and CMAB literature, by offering a new angle to solve the episodic RL through the lens of CMAB, which may encourage more interactions between these two important directions.

We explore whether quantum advantages can be found for the zeroth-order feedback online exp-concave optimization problem, which is also known as bandit exp-concave optimization with multi-point feedback. We present quantum online quasi-Newton methods to tackle the problem and show that there exists quantum advantages for such problems. Our method approximates the Hessian by quantum estimated inexact gradient and can achieve $O(n\log T)$ regret with $O(1)$ queries at each round, where $n$ is the dimension of the decision set and $T$ is the total decision rounds. Such regret improves the optimal classical algorithm by a factor of $T^{2/3}$.

Probabilistic maximum coverage (PMC) is an important framework that can model many network applications, including mobile crowdsensing, content delivery, and task repli¬cation. In PMC, an operator chooses nodes in a graph that can probabilistically cover other nodes, aiming to maximize the total rewards from the covered nodes. To tackle the challenge of unknown parameters in network environments, PMC are studied under the online learning context, i.e., the PMC bandit. However, existing PMC bandits lack context-awareness and fail to exploit valuable contextual information, limiting their efficiency and adaptability in dynamic environments. To address this limitation, we propose a novel context-aware PMC bandit model (C-PMC). C-PMC employs a linear structure to model the mean outcome of each arm, effectively incorporating contextual information and enhancing its applicability to large-scale network systems. Then we design a variance-adaptive contextual combinatorial upper confidence bound algorithm (VAC2UCB), which utilizes second-order statistics, specifically variance, to re-weight feedback data and estimate unknown parameters. Our theoretical analysis shows that C-PMC achieves a regret of $\tilde O(d\sqrt {|\mathcal{V}|T} )$, independent of the number of edges $|\mathcal{E}|$ and action size K. Finally, we conduct experiments on synthetic and real-world datasets, showing the superior performance of VAC2UCB in context-aware mobile crowdsensing and user-targeted content delivery applications.

Large-scale quantum networks with thousands of nodes require topology-oblivious routing protocols to realize. Most existing quantum network routing protocols only consider the intra-domain scenario, where all nodes belong to a single party with complete topology knowledge. However, like the classical Internet, quantum Internet will likely be provided by multiple quantum Internet Service Providers (qISPs). In this paper, we consider the inter-domain scenario, where the network consists of multiple subnetworks owned by mutually untrusted parties without centralized control. Under this setting, previously proposed quantum entanglement routing policies, which rely on the network topology knowledge, are no longer applicable. We propose a Quantum Border Gateway Protocol (QBGP) for efficiently routing entanglement across qISP boundaries. To guarantee high-quality information transmission, we propose an algorithm named online top-K path selection. This algorithm utilizes the information gain introduced in this paper to adaptively decide on measurement parameters, allowing for the selection of high-fidelity paths and accurate fidelity estimates, while minimizing costs. Additionally, we implement a quantum network simulator and evaluate our protocol and algorithm. Our evaluation shows that QBGP effectively distributes entanglement across different qISPs, and our path selection algorithm increases the network performance by selecting high-fidelity paths with much lower resource consumption than other methods.

Reliable transmission of fragile quantum information requires one to efficiently select and utilize high-fidelity links among multiple noisy quantum links. However, the fidelity, a quality metric of quantum links, is unknown a priori. Uniformly estimating the fidelity of all links can be expensive, especially in networks with numerous links. To address this challenge, we formulate the link selection and fidelity estimation problem as a best arm identification problem and propose an algorithm named LinkSelFiE. The algorithm efficiently identifies the optimal link from a set of quantum links and provides an accurate fidelity estimate of that link with low quantum resource consumption. LinkSelFiE estimates link fidelity based on the feedback of a vanilla network benchmarking subroutine, and adaptively eliminates inferior links throughout the whole fidelity estimation process. This elimination leverages a novel confidence interval derived in this paper for the estimates from the subroutine, which theoretically guarantees that LinkSelFiE outputs the optimal link correctly with high confidence. We also establish a provable upper bound of cost complexity for LinkSelFiE. Moreover, we perform extensive simulations under various scenarios to corroborate that LinkSelFiE outperforms other existing methods in terms of both identifying the optimal link and reducing quantum resource consumption.

In Federated Learning (FL) paradigm, a parameter server (PS) concurrently communicates with distributed participating clients for model collection, update aggregation, and model distribution over multiple rounds, without touching private data owned by individual clients. FL is appealing in preserving data privacy; yet the communication between the PS and scattered clients can be a severe bottleneck. Model compression algorithms, such as quantization and sparsification, have been suggested but they generally assume a fixed code length, which does not reflect the heterogeneity and variability of model updates. In this paper, through both analysis and experiments, we show strong evidences that variable-length is beneficial for compression in FL. We accordingly present Fed-CVLC (Federated Learning Compression with Variable-Length Codes), which fine-tunes the code length in response of the dynamics of model updates. We develop optimal tuning strategy that minimizes the loss function (equivalent to maximizing the model utility) subject to the budget for communication. We further demonstrate that Fed-CVLC is indeed a general compression design that bridges quantization and sparsification, with greater flexibility. Extensive experiments have been conducted with public datasets to demonstrate that Fed-CVLC remarkably outperforms state-of-the-art baselines, improving model utility by 1.50%-5.44%, or shrinking communication traffic by 16.67%-41.61%.

Optimizing network protocols is crucial for improving application performance. Recent research works use multi-armed bandit (MAB) online learning methods to address network optimization problems, aiming to improve cumulative payoffs such as network throughput. However, existing MAB frameworks are ineffective since they inherently assume the network environment is static, or they have high complexity in detecting environmental changes. In this work, we advocate using lightweight "network-assist" techniques together with online learning to optimize network protocols, and show it can effectively detect environmental changes and maximize network performance. Furthermore, optimizing network protocols often face two types of decision (or arm) spaces: discrete and continuous choices, while most prior MAB models only handle discrete settings. This paper proposes a framework capable of managing both spaces. To our best knowledge, we are the first to develop an MAB framework that incorporates network-assist signals in handling dynamic environments, while considering the distinct characteristics of discrete and continuous arm spaces. Our framework can achieve optimality by showing its sub-linear regret bound, matching the state-of-the-art results in several degenerate cases. We also illustrate how to apply our framework to two network applications: (1) wireless network channel selection, and (2) rate-based TCP congestion control. We demonstrate the merits of our algorithms via both numerical simulations and packet-level experiments.

The rapid evolution of multimedia and computer vision technologies requires adaptive visual model deployment strategies to effectively handle diverse tasks and varying environments. This work introduces AxiomVision, a novel framework that can guarantee accuracy by leveraging edge computing to dynamically select the most efficient visual models for video analytics under diverse scenarios. Utilizing a tiered edge-cloud architecture, AxiomVision enables the deployment of a broad spectrum of visual models, from lightweight to complex DNNs, that can be tailored to specific scenarios while considering camera source impacts. In addition, AxiomVision provides three core innovations: (1) a dynamic visual model selection mechanism utilizing continual online learning, (2) an efficient online method that efficiently takes into account the influence of the camera's perspective, and (3) a topology-driven grouping approach that accelerates the model selection process. With rigorous theoretical guarantees, these advancements provide a scalable and effective solution for visual tasks inherent to multimedia systems, such as object detection, classification, and counting. Empirically, AxiomVision achieves a 25.7% improvement in accuracy.

Multi-armed bandits (MAB) is an online learning and decisionmaking model under uncertainty. Instead of maximizing the expected utility (or reward) in a classical MAB setting, the variance of the utility should be considered when making risk-aware decisions. In this paper, we propose a risk-aware multi-agent MAB (MAMAB) model, which considers both the "independent" and "correlated" risk when multiple agents make arm-pulling decisions. Specifically, the system includes a platform that owns a number of tasks (or arms) awaiting a group of agents to accomplish. We show how to calculate the arm-pulling strategy of agents with potentially different eligible arm sets under a Nash equilibrium point. From the perspective of the platform, each arm has its maximal capacity to accommodate arm-pulling agents. We design the platform's optimal payment algorithms for its risk-aware revenue maximization (a regret minimization) under both independent and correlated risks. We prove that our algorithms achieve the sub-linear regret under independent risks when the platform can or cannot differentiate the utility on each arm. We also prove that our algorithm achieves the sublinear regret under correlated risks. We also carry out experiments to quantify the merits of our algorithms for various networking applications, such as crowdsourcing and edge computing.

Large language models have shown an impressive societal impact owing to their excellent understanding and logical reasoning skills. However, such strong ability relies on a huge amount of computing resources, which makes it difficult to deploy LLMs on computing resource-constrained platforms. Currently, LLMs process each token equivalently, but we argue that not every word is equally important. Some words should not be allocated excessive computing resources, particularly for dispensable terms in simple questions. In this paper, we propose a novel dynamic inference paradigm for LLMs, namely D-LLMs, which adaptively allocate computing resources in token processing. We design a dynamic decision module for each transformer layer that decides whether a network unit should be executed or skipped. Moreover, we tackle the issue of adapting D-LLMs to real-world applications, specifically concerning the missing KV-cache when layers are skipped. To overcome this, we propose a simple yet effective eviction policy to exclude the skipped layers from subsequent attention calculations. The eviction policy not only enables D-LLMs to be compatible with prevalent applications but also reduces considerable storage resources. Experimentally, D-LLMs show superior performance, in terms of computational cost and KV storage utilization. It can reduce up to 45\% computational cost and KV storage on Q\&A, summarization, and math solving tasks, 50\% on commonsense reasoning tasks.

This paper considers the problem for finding the $(\delta,\epsilon)$-Goldstein stationary point of Lipschitz continuous objective, which is a rich function class to cover a great number of important applications. We construct a novel zeroth-order quantum estimator for the gradient of the smoothed surrogate. Based on such estimator, we propose a novel quantum algorithm that achieves a query complexity of $\tilde{\mathcal{O}}(d^{3/2}\delta^{-1}\epsilon^{-3})$ on the stochastic function value oracle, where $d$ is the dimension of the problem. We also enhance the query complexity to $\tilde{\mathcal{O}}(d^{3/2}\delta^{-1}\epsilon^{-7/3})$ by introducing a variance reduction variant. Our findings demonstrate the clear advantages of utilizing quantum techniques for non-convex non-smooth optimization, as they outperform the optimal classical methods on the dependency of $\epsilon$ by a factor of $\epsilon^{-2/3}$.

Federated learning (FL) is an emerging distributed machine learning (ML) paradigm in the Artificial Intelligence of Things (AIoT). FL enables AIoT devices to collaboratively train an ML model on the network edge, while protecting data privacy and solving the problem of isolated data islands. Contemporary FL is typically realized through the model aggregation of locally trained models and the model dissemination of a globally averaged model; such a procedure iteratively proceeds until a predefined convergence criterion is met. However, FL necessitates frequent information exchanges between AIoT devices and a parameter server, which inevitably induces tremendous communication costs. Therefore, this article proposes a new design for efficient one-shot FL for AIoT systems, so that the model aggregation and dissemination can be completed within a single communication round. To this end, we leverage optimal transport (OT) theory to design the coupled model averaging (CODE) algorithm to fuse the model weights of the neural networks (NNs) on AIoT devices. The CODE algorithm initially performs OT-based layer-by-layer model averaging (MA) over two NNs to form a fused NN, which will then be averaged with another NN. The CODE algorithm progressively determines a pair of NNs, and continues until all NNs have been examined to achieve one-shot FL. In addition, we provide a detailed convergence analysis for the proposed solution. Our simulation results show that the proposed solution outperforms other one-shot MA mechanisms under various parameter settings.

In the domain of conversational recommendation systems (CRSs), the development of recommenders capable of eliciting user preferences through conversation has marked a significant advancement. These systems have been enhanced by incorporating conversational key-terms related to items, which streamline the recommendation process by reducing the extensive exploration that traditional interactive recommenders necessitate. Despite these advancements, CRSs still face significant challenges. The vast number of users and the difficulty in accurately capturing preferences lead to persistent inaccuracies, even when direct user interactions are employed to refine the understanding of user preferences. To tackle these challenges, we propose two innovative bandit algorithms: RCLUMB (Robust Clustering of Misspecified Bandits) and RSCLUMB (Robust Set-based Clustering of Misspecified Bandits). These algorithms employ dynamic graphs and evolving cluster sets, respectively, to represent the changing structure of user preferences, thus leveraging collaborative user preferences to accelerate the learning process. Our algorithms are designed to be resilient against errors in preference modeling and the resulting inaccuracies in clustering. We rigorously analyze the performance of our algorithms and establish regret upper bounds of$O(\epsilon _*T\sqrt{md\log T} + d\sqrt{mT}\log T)$under milder assumptions than previous works, matching the state-of-the-art results in several degenerate cases. Through extensive experiments on synthetic and real-world datasets, our algorithms demonstrate superior performance over existing algorithms.

Conversational recommendation systems (CRSs) are increasingly prevalent, but they are susceptible to the influence of corrupted user behaviors, such as deceptive click ratings. These behaviors can skew the recommendation process, resulting in suboptimal results. Traditional bandit algorithms, which are typically oriented to single users, do not capitalize on implicit social connections between users, which could otherwise enhance learning efficiency. Furthermore, they cannot identify corrupted users in a real-time, multi-user environment. In this paper, we propose a novel bandit problem, Online Learning and Detecting Corrupted Users (OLDCU), to learn and utilize unknown user relations from disrupted behaviors to speed up learning and detect corrupted users in an online setting. This problem is non-trivial due to the dynamic nature of user behaviors and the difficulty of online detection. To robustly learn and leverage the unknown relations among potentially corrupted users, we propose a novel bandit algorithm RCLUB-WCU, incorporating a conversational mechanism. This algorithm is designed to handle the complexities of disrupted behaviors and to make accurate user relation inferences. To detect corrupted users with bandit feedback, we further devise a novel online detection algorithm, OCCUD, which is based on RCLUB-WCU’s inferred user relations and designed to adapt over time. We prove a sub-linear regret bound for RCLUB-WCU, demonstrating its efficiency. We also analyze the detection accuracy of OCCUD, showing its effectiveness in identifying corrupted users. Through extensive experiments, we validate the performance of our methods. Our results show that RCLUB-WCU and OCCUD outperform previous bandit algorithms and achieve high corrupted user detection accuracy, providing robust and efficient solutions in the field of CRSs.

Door lock is regarded as a critical line of defending the privacy and security of personal areas. However, for inner doors in environments like factories, existing locking mechanisms can be poor in user-friendliness and high in cost. For instance, mechanical locks require carrying keys that inevitably compromise user experiences, while smart locks always require non-trivial sensors. Therefore, inner doors urgently require a lightweight unlocking scheme that can properly balance user-friendliness, cost, and security. To this end, we propose HandKey as a keyless unlocking scheme to supplement existing lock systems. HandKey relies on two principles: the simplicity of hand knocking doors and the uniqueness of vibration triggered by the knocking force. In other words, a door and a hand knocking it jointly form a unique physical system that generates hand-dependent and user-specific vibration signatures uniquely representing a user identity. In designing HandKey, we first analyze the vibration mechanism behind it and the impacts of gestures and door materials on vibration signatures. Then we innovatively construct a signal processing and deep learning-based pipeline to extract signatures robust to variable knocking behaviors for representing user identity. Finally, we implement a HandKey prototype and use extensive evaluation to demonstrate its security and effectiveness.

To provide reliable and elastic Multi-access edge computing services, one feasible solution is to federate geographically proximate edge servers to form a logically centralized resource pool. Optimization of such systems, however, becomes challenging. In this paper, we study the problem of maximizing users’ QoE in a MEC-based network, through jointly optimizing service caching, resource allocation and task offloading decisions. We formulate a mixed-integer nonlinear programming (MINLP) problem for the task and establish its NP-hardness. To tackle it efficiently, we propose a novel two-stage algorithmic solution based on approximation and decomposition theory. The proposed algorithm achieves high system performance while at the same time, ensures all constraints from different layers are satisfied. Meanwhile, the structure of the algorithm also fits the multi-layer optimizing feature, making it suitable to be implemented at different layers. In addition, we propose a distributed and online version of our mechanism with very limited information exchange between MEC servers, and further demonstrate how the cost of service switches from real MEC systems can be incorporated into our framework. We evaluate our mechanisms through simulations with both synthetic and real-world traces, and results indicate they are effective as compared to representative baseline algorithms.

Vehicular edge computing (VEC) provides an effective task offloading paradigm by pushing cloud resources to the vehicular network edges, e.g., road side units (RSUs). However, overloaded RSUs are likely to occur especially in urban aggregation areas, possibly leading to greatly compromised offloading performance. Inspired by this, this article explores this situation by introducing an unmanned aerial vehicle (UAV) to address the VEC overload problem. Specifically, we formulate a novel online UAV-assisted vehicular task offloading problem to minimize vehicular task delay under the long-term UAV energy constraint. To solve the formulated problem, we first decouple the long-term energy constraint based on the Lyapunov optimization technique. In this way, the problem can be solved in a real-time manner without requiring future information. Then, we construct a Markov chain based on Markov approximation optimization to find out the close-to-optimal UAV-assisted offloading strategies. Furthermore, we derive a mathematical analysis to rigorously demonstrate the offloading performance of the proposed algorithm. Additionally, the simulation results show that the proposed method outperforms the baselines by significantly reducing the vehicular task delay constrained by the long-term UAV energy budget under various system parameters, such as the energy budget and computation workloads.

Unsourced multiple access (UMA) is a novel approach to support a large number of devices in a massive Machine-Type Communication (mMTC) system. UMA enables devices to concurrently encode their data using the same codebook to transmit without being individually identified, resulting in reduced signaling and computational overhead at the base station. Hybrid-domain non-orthogonal multiple access (NOMA), which combines power-domain NOMA with code-domain NOMA, is another technique that enhances the spectral efficiency of mMTC. While the study of hybrid-domain NOMA has been conducted, its integration with UMA has not been thoroughly investigated. Considering that mMTC traffic primarily consists of sporadic short packets in the uplink direction, employing a fully distributed mMTC multiple access protocol can substantially decrease signaling overhead and latency. In this work, a multi-armed bandits (MAB) paradigm is adopted to create a distributed power selection policy for devices that using UMA. Particularly, an MAB algorithm called Thompson Sampling (TS) is used to allow mMTC devices to minimize the transmission power without violating the minimum receiving signal-to-noise constraint needed to correctly decode the UMA codewords back to the original messages. A mean-field modeling technique is used to approximate the learned policies. The knowledge gained from the approximated policies can be transferred to new devices by initializing their prior distribution, which is called Mean-field Transfer Thompson Sampling (MFTTS). Simulations show that the mean-field approximation is indeed accurate and effective. Interestingly, MFTTS performs better than TS without knowledge transfer as well as other distributed power allocation methods.

The emergence of edge intelligence has made smart IoT services (e.g.,video/audio surveillance, autonomous driving and smart city) a reality. To ensure the quality of service, edge service providers train unbiased models of distributed machine learning jobs over the local datasets collected by edge networks, and usually adopt the parameter server (PS) architecture. However, the training ofunbiased distributed learning(UDL) depends on geo-distributed data and edge resources, bringing a new challenge for service providers: how to effectively schedule and price UDL jobs such that the long-term system utility (i.e.,social welfare) can be maximized. In this paper, we propose an online auction-based scheduling algorithmEris, which determines the data workload, the number and the placement of concurrent workers and PSs for each arriving UDL job, and dynamically prices limited edge resources based on current resource consumption.Erisapplies a primal-dual framework which calls an efficient dual subroutine to schedule UDL jobs, achieving a good competitive ratio and pseudo-polynomial time complexity. To evaluate the effectiveness ofEris, we implement both a testbed and a large-scaled simulator. The results demonstrate thatErisoutperforms and achieves up to 44% more social welfare compared to state-of-the-art algorithms in today's cloud system.

The pursuit of high-quality artificial intelligence generated contents (AIGC) with fast response has prompted the evolution of natural language processing (NLP) services, notably those enabled at the edge (i.e., edge NLP). For concreteness, we study distributed inference for next-word prediction which is a prevalent edge NLP service for mobile keyboards on user devices. Accordingly, we optimize coupled metrics,i.e., maximize prediction click-through rate (CTR) for improved quality-of-service (QoS), minimize user impatience for enhanced quality-of-experience (QoE), and keep energy consumption within budget for sustainability. Moreover, we consider the real-world setting where there is no prior knowledge of heterogeneous NLP models' prediction accuracy. Via an integration of online learning and online control, we propose a novel distributed inference algorithm for online next-word prediction with user impatience (DONUT) to estimate models' prediction accuracy and balance the trade-offs among coupled metrics. Our theoretical analysis reveals that DONUT achieves sub-linear regret (loss of CTR), ensures bounded user impatience, and maintains within-budget energy consumption. Through numerical simulations, we not only establish DONUT's superior performance over other baseline methods, but also demonstrate its adaptability to various settings.

Queueing models serve as important building blocks in many networking applications such as task scheduling in mobile edge computing nodes, traffic scheduling in networks, congestion control in Internet, etc. However, queueing theory often needs to make strong assumptions about the arrival process or service rewards at each queue. In addition, fairness in serving workload among all queues is of great importance in many applications. In this paper, we address how to optimize resource allocation among multiple queues with a fairness guarantee and without any a priori knowledge of these queues’ parameters. To characterize queues with unknown parameters and the fairness requirement, we formulate an online learning model with a varying and continuous action space, as well as a nonlinear utility objective. We design an online learning algorithm to tackle the problem. We prove that our algorithm has a regret upper bound of$O(\sqrt{T}\log T)$and our model has a regret lower bound of$\Omega (\sqrt{T})$, where$T$stands for the number of decision rounds. The asymptotic closeness of upper and lower bounds guarantees their near tightness and our algorithm's near optimality. We discuss our model's real-world applications in mobile edge computing, wireless networks, and crowdsourcing, and conduct simulations to validate our algorithm's effectiveness.

Mobile edge computing facilitates users to offload computation tasks to edge servers for meeting their stringent delay requirements. Previous works mainly explore task offloading when system-side information is given (e.g., server processing speed, cellular data rate), or centralized offloading under system uncertainty. But both generally fall short of handling task placement involving many coexisting users in an uncertain environment. In this paper, we develop amulti-useroffloading framework consideringunknown yet stochasticsystem-side information to enable adecentralized user-initiatedservice placement under overlapping server coverage. Specifically, we formulate the dynamic task placement as an online multi-user multi-armed bandit process, and propose a decentralized epoch based offloading (DEBO) to optimize user rewards which are subjected under network delay. We consider both cases without and with neighboring edge feedback once users’ tasks are processed, where the latter incorporates system-side information sharing among edge servers for an enhanced task placement. For both cases, we show that DEBO can gradually deduce the optimal user-server assignment during dynamic offloading, thereby achieving aclose-to-optimalservice performance andtight$O(\log _{2}\!\!T)$regret. Moreover, we generalize DEBO to various common scenarios such as unknown reward gap, dynamic entering or leaving of clients, and fair reward distribution, while further exploring when users’ offloaded tasks requireheterogeneouscomputing resources. Particularly, we accomplish a sub-linear regret for each of these instances. Real measurements based evaluations corroborate the superiority of our offloading schemes over state-of-the-art approaches in optimizing delay-sensitive rewards.

Traffic engineering (TE) is one of the most critical issues in networking, as it enables efficient and reliable network operations. With the advent of Machine Learning (ML) techniques, many ML-based TE methods have emerged in recent years, especially those employing Deep Neural Networks for future traffic prediction to enhance the performance of traditional approaches. However, current methods suffer from two major issues. Firstly, most prior works only solve the TE problem based on short-term traffic prediction, neglecting the network traffic dynamics over an extended time period. This oversight results in high network disturbance when numerous traffic flows need to be rerouted to adapt to traffic changes. Secondly, although traffic prediction models rely on historical traffic data to perform future prediction, ML-based TE studies often ignore the high overhead for network traffic monitoring. To address these issues, we propose a traffic prediction-based routing algorithm in which the routing rules can be applied to multiple time-steps without requiring changes, ultimately leading to reduced network disturbance. We employ the segment routing (SR) technique as the routing algorithm and formulate the multi-time-step segment routing method that incorporates future traffic prediction. To address the high monitoring overhead, we present an approach that combines partial traffic prediction and compressive sensing techniques to estimate unmeasured data. Through extensive experiments on real backbone network traffic datasets, we demonstrate that our proposal can achieve more than 80% of the optimal performance in reducing maximum link utilization while significantly reducing the number of routing changes and traffic monitoring cost.

MPTCP provides the basic multipath support for network applications to deliver high throughput and robust communication. However, the original MPTCP is designed with limited extensibility. Various research works have tried to extend MPTCP to attain better performance or richer functionalities. These existing approaches either modify the kernel implementation of MPTCP, which involve considerable engineering efforts and may accidentally introduce safety issues, or control MPTCP via userspace tools, which suffer from restricted functionality support. To address this issue, we propose eMPTCP, an easy-to-use framework to fully extend MPTCP without safety risks. Internally, eMPTCP has a modular and pluggable model which allows operators to specify a comprehensive MPTCP extension as a chain of sub-policies. eMPTCP further enforces the policies through packet header manipulations. To ensure safety, eMPTCP is implemented using eBPF. Despite the stringent constraints of eBPF, we show that it is possible to implement an elaborated framework for a fully extensible MPTCP. Through verifying MPTCP in a number of real-world cases and extensive experiments, we show that eMPTCP is able to support a wide range of MPTCP extensions, while the overhead of eMPTCP operations in the kernel is in the scale of nanosecond, and the extra processing time accounts for only about 0.63% of flows’ transmission time.

Mobile edge computing (MEC) facilitates computation offloading to edge server and task processing via device-to-device (D2D) collaboration. Existing works mainly focus on centralized network-assisted offloading solutions, which are unscalable to collaborations among massive users. In this paper, we propose a joint framework of decentralized D2D collaboration and task offloading for MEC systems with large populations. Specifically, we utilize the power of two choices for D2D collaboration, which enables users to assist each other in a decentralized manner. Due to short-range D2D communication and user movements, we formulate a mean field model on a finite-degree and dynamic graph to analyze the collaboration state evolution. We derive the existence, uniqueness and convergence of the state stationary point to provide a tractable collaboration performance. Complementing this D2D collaboration, we further build a Stackelberg game to model users’ task offloading, where the provider, managing many servers, is the leader to determine service prices, while users are followers to make offloading decisions. By embedding Stackelberg game into Lyapunov optimization, we develop an online offloading and pricing scheme, which can optimize servers’ service utility or fairness, and users’ system cost simultaneously. Extensive evaluations show that D2D collaboration can mitigate users’ workloads by 73.8% and fair pricing can promote servers’ utility fairness by 15.87%.

Influence maximization (IM) is the fundamental problem in many real world applications such as viral marketing, political campaign, and network monitoring. Although extensively studied, most studies on IM assume that social influence is static and they cannot handle the dynamic influence challenge in reality, i.e., a user’s influence is varying over time. To address this challenge, we formulate a novel influencer tracking problem over a social activity stream. In order to keep the solutions up-to-date and forget outdated data in the stream smoothly, we propose a probabilistic-decaying social activity stream (PDSAS) model that enforces each social activity in the stream participating in the analysis with a probability decaying over time. Built on the PDSAS model, we propose a family of streaming optimization algorithms to solve the influencer tracking problem. SIEVE PAIT can identify influencers from a special kind of probabilistic addition-only social activity streams with high efficiency, and guarantees an$(1/2-\epsilon)$approximation ratio. BASIC IT leverages SIEVE PAIT as a building block to identify influencers from general PDSASs, and also guarantees an$(1/2-\epsilon)$approximation ratio. HIST IT improves the efficiency of BASIC IT, and still guarantees an$(1/4-\epsilon)$approximation ratio. Experiments on real data show that our methods can find high quality solutions with much less computational costs than baselines.

Conversational contextual bandits elicit user preferences by occasionally querying for explicit feedback on key-terms to accelerate learning. However, there are aspects of existing approaches which limit their performance. First, information gained from key-term-level conversations and arm-level recommendations is not appropriately incorporated to speed up learning. Second, it is important to ask explorative key-terms to quickly elicit the user's potential interests in various domains to accelerate the convergence of user preference estimation, which has never been considered in existing works. To tackle these issues, we first propose ``ConLinUCB", a general framework for conversational bandits with better information incorporation, combining arm-level and key-term-level feedback to estimate user preference in one step at each time. Based on this framework, we further design two bandit algorithms with explorative key-term selection strategies, ConLinUCB-BS and ConLinUCB-MCR. We prove tighter regret upper bounds of our proposed algorithms. Particularly, ConLinUCB-BS achieves a better regret bound than the previous result. Extensive experiments on synthetic and real-world data show significant advantages of our algorithms in learning accuracy (up to 54% improvement) and computational efficiency (up to 72% improvement), compared to the classic ConUCB algorithm, showing the potential benefit to recommender systems.

This paper studies a cooperative multi-agent multi-armed stochastic bandit problem where agents operate asynchronously – agent pull times and rates are unknown, irregular, and heterogeneous – and face the same instance of a K-armed bandit problem. Agents can share reward information to speed up the learning process at additional communication costs. We propose ODC, an on-demand communication protocol that tailors the communication of each pair of agents based on their empirical pull times. ODC is efficient when the pull times of agents are highly heterogeneous, and its communication complexity depends on the empirical pull times of agents. ODC is a generic protocol that can be integrated into most cooperative bandit algorithms without degrading their performance. We then incorporate ODC into the natural extensions of UCB and AAE algorithms and propose two communication-efficient cooperative algorithms. Our analysis shows that both algorithms are near-optimal in regret.

With diverse functionalities and advanced platform applications, Internet of Things (IoT) devices extensively interact with each other, and these interactions govern the legitimate device state transitions. At the same time, attackers can easily manipulate these devices, and it is difficult to detect covert device control. In this work, we propose the device interaction graph, which uses device interactions to profile normal device behavior. We also formalize two types of device anomalies, and present an anomaly detection system CausalIoT. It can automatically construct the graph and validate runtime device events. For any violation of interaction executions, CausalIoT further checks whether it can trigger unexpected interaction executions and tracks the affected devices.1 Compared with existing methods, CausalIoT achieves the highest detection accuracy for abnormal device state transitions (95.2% precision and 96.8% recall). Moreover, we are the first to detect unexpected interaction executions, and CausalIoT successfully reports 91.9% anomaly chains on real-world testbeds.

Link speed in datacenter networks (DCNs) keeps growing rapidly, inducing an increasingly large portion of network flows to become short flows which can be finished within one round-trip time (RTT). This phenomenon makes many existing congestion control schemes ineffective because they iteratively adjust the sending rate based on the latest congestion feedback in multiple rounds. We find that the representative DCQCN scheme for RDMA exhibits substantial performance degradation when there are many short flows, and this is specially true in High Performance Computing (HPC) scenarios where most of Message Passing Interface (MPI) messages are small. In this paper, we propose a data-driven rate control framework which can learn from long-term online data about past rate control decisions via a lightweight online learning technique named Multi-Armed Bandit (MAB) which has a provable performance guarantee. Utilizing the framework, we devise a rate control scheme named Dolce-RC, which dynamically controls the rate increase and reduction by learning from online data. We implement Dolce-RC in commodity smart NICs, and show via testbed experiments and large-scale simulations that compared to DCQCN, Dolce-RC reduces average completion time of MPI messages by up to 68%, while not requiring any modification to switches.

As a fundamental tool for graph analysis, random walk receives extensive attention in both industry and academia. For computing massive random walks, recent works show that GPUs provide a good option to accelerate the performance. However, due to the limited memory space of modern GPUs, it is infeasible to have both the graph data and walk index fully reside in GPU memory when running large-scale random walks. Thus, it necessitates an out-of-GPU-memory design, but this inevitably induces large amounts of CPU-GPU data transmission traffic and thus hinders the overall performance. In this paper, we develop LightTraffic, which optimizes the data transmission between CPU and GPU memory under the constraint of GPU memory capacity with various system designs, including a memory-efficient scheme for partition-based management and multiple scheduling techniques. LightTraffic is a fully out-of-GPU-memory design, so it supports running large-scale random walks on GPUs. Experiments on our prototype show that LightTraffic outperforms various state-of-the-art CPU-based in-memory systems which also support large-scale random walks. For example, compared to the CPU-based systems FlashMob and ThunderRW, which are highly optimized for random walks, LightTraffic achieves 1.7−5.0× and 1.4 − 12.8× performance speedup, respectively. It also achieves up to an order of magnitude speedup when compared to the GPU-based system Subway which also supports large-scale random walks with an out-of-GPU-memory design for graph data.

We study contextual combinatorial bandits with probabilistically triggered arms (C$^2$MAB-T) under a variety of smoothness conditions that capture a wide range of applications, such as contextual cascading bandits and contextual influence maximization bandits. Under the triggering probability modulated (TPM) condition, we devise the C$^2$-UCB-T algorithm and propose a novel analysis that achieves an $\tilde{O}(d\sqrt{KT})$ regret bound, removing a potentially exponentially large factor $O(1/p_{\min})$, where $d$ is the dimension of contexts, $p_{\min}$ is the minimum positive probability that any arm can be triggered, and batch-size $K$ is the maximum number of arms that can be triggered per round. Under the variance modulated (VM) or triggering probability and variance modulated (TPVM) conditions, we propose a new variance-adaptive algorithm VAC$^2$-UCB and derive a regret bound $\tilde{O}(d\sqrt{T})$, which is independent of the batch-size $K$. As a valuable by-product, our analysis technique and variance-adaptive algorithm can be applied to the CMAB-T and C$^2$MAB setting, improving existing results there as well. We also include experiments that demonstrate the improved performance of our algorithms compared with benchmark algorithms on synthetic and real-world datasets.

In traditional machine learning, it is trivial to conduct model evaluation since all data samples are managed centrally by a server. However, model evaluation becomes a challenging problem in federated learning (FL), which is called federated evaluation in this work. This is because clients do not expose their original data to preserve data privacy. Federated evaluation plays a vital role in client selection, incentive mechanism design, malicious attack detection, etc. In this paper, we provide the first comprehensive survey of existing federated evaluation methods. Moreover, we explore various applications of federated evaluation for enhancing FL performance and finally present future research directions by envisioning some challenges.

Probabilistic maximum coverage (PMC) is an important problem that can model many network applications, including mobile crowdsensing, network content delivery, and dynamic channel allocation, where an operator chooses nodes in a graph that can probabilistically cover other nodes. In this paper, we study PMC under the online learning context: the PMC bandit. For PMC bandit where network parameters are not known a priori, the decision maker needs to learn the unknown parameters and the goal is to maximize the total rewards from the covered nodes. Though PMC bandit has been studied previously, the existing model and its corresponding algorithm can be significantly improved. First, we propose the PMC-G bandit whose feedback model generalizes existing semi-bandit feedback, allowing PMC bandit to model applications like online content delivery and online dynamic channel allocation. Next, we improve the existing combinatorial upper confidence bound (CUCB) algorithm by introducing the variance-adaptive algorithm, i.e., the VA-CUCB algorithm. We prove that VA-CUCB can achieve strictly better regret bounds, which improves CUCB by a factor of $\tilde O(K)$, where K is the number of nodes selected in each round. Finally, experiments show our superior performance compared with benchmark algorithms on synthetic and real-world datasets.

We propose a communication and computation efficient second-order method for distributed optimization. For each iteration, our method only requires O (d) communication complexity, where d is the problem dimension. We also provide theoretical analysis to show the proposed method has the similar convergence rate as the classical second-order optimization algorithms. Concretely, our method can find (∈, √dLe,)-second-order stationary points for nonconvex problem by O (√dL,∈-3/2) iterations, where L is the Lipschitz constant of Hessian. Moreover, it enjoys a local superlinear convergence under the strongly-convex assumption. Experiments on both convex and nonconvex problems show that our proposed method performs significantly better than baselines.

This paper studies quasi-Newton methods for solving nonlinear equations. We propose block variants of both good and bad Broyden's methods, which enjoy explicit local superlinear convergence rates. Our block good Broyden's method has faster condition-number-free convergence rate than existing Broyden's methods because it takes the advantage of multiple rank modification on the Jacobian estimator. On the other hand, our block bad Broyden's method directly estimates the inverse of the Jacobian provably, which reduces the computational cost of the iteration. Our theoretical results provide some new insights on why good Broyden's method outperforms bad Broyden's method in most of the cases. The empirical results also demonstrate the superiority of our methods and validate our theoretical analysis.

We study the multi-fidelity multi-armed bandit ($\texttt{MF-MAB}$), an extension of the canonical multi-armed bandit (MAB) problem. $\texttt{MF-MAB}$ allows each arm to be pulled with different costs (fidelities) and observation accuracy. We study both the best arm identification with fixed confidence ($\texttt{BAI}$) and the regret minimization objectives. For $\texttt{BAI}$, we present (a) a cost complexity lower bound, (b) an algorithmic framework with two alternative fidelity selection procedures, and (c) both procedures' cost complexity upper bounds. From both cost complexity bounds of $\texttt{MF-MAB}$, one can recover the standard sample complexity bounds of the classic (single-fidelity) MAB. For regret minimization of $\texttt{MF-MAB}$, we propose a new regret definition, prove its problem-independent regret lower bound $\Omega(K^{1/3}\Lambda^{2/3})$ and problem-dependent lower bound $\Omega(K\log \Lambda)$, where $K$ is the number of arms and $\Lambda$ is the decision budget in terms of cost, and devise an elimination-based algorithm whose worst-cost regret upper bound matches its corresponding lower bound up to some logarithmic terms and, whose problem-dependent bound matches its corresponding lower bound in terms of $\Lambda$.

The contextual linear bandit is an important online learning problem where given arm features, a learning agent selects an arm at each round to maximize the cumulative rewards in the long run. A line of works, called the clustering of bandits (CB), utilize the collaborative effect over user preferences and have shown significant improvements over classic linear bandit algorithms. However, existing CB algorithms require well-specified linear user models and can fail when this critical assumption does not hold. Whether robust CB algorithms can be designed for more practical scenarios with misspecified user models remains an open problem. In this paper, we are the first to present the important problem of clustering of bandits with misspecified user models (CBMUM), where the expected rewards in user models can be perturbed away from perfect linear models. We devise two robust CB algorithms, RCLUMB and RSCLUMB (representing the learned clustering structure with dynamic graph and sets, respectively), that can accommodate the inaccurate user preference estimations and erroneous clustering caused by model misspecifications. We prove regret upper bounds of $O(\epsilon_*T\sqrt{md\log T} + d\sqrt{mT}\log T)$ for our algorithms under milder assumptions than previous CB works, which match the lower bound asymptotically in $T$ up to logarithmic factors, and also match the state-of-the-art results in several degenerate cases. Our regret analysis is novel and different from the typical proof flow of previous CB works. The techniques in proving the regret caused by misclustering users are quite general and may be of independent interest. Experiments on both synthetic and real-world data show our outperformance over previous algorithms.

In real-world online web systems, multiple users usually arrive sequentially into the system. For applications like click fraud and fake reviews, some users can maliciously perform corrupted (disrupted) behaviors to trick the system. Therefore, it is crucial to design efficient online learning algorithms to robustly learn from potentially corrupted user behaviors and accurately identify the corrupted users in an online manner. Existing works propose bandit algorithms robust to adversarial corruption. However, these algorithms are designed for a single user, and cannot leverage the implicit social relations among multiple users for more efficient learning. Moreover, none of them consider how to detect corrupted users online in the multiple-user scenario. In this paper, we present an important online learning problem named LOCUD to learn and utilize unknown user relations from disrupted behaviors to speed up learning, and identify the corrupted users in an online setting. To robustly learn and utilize the unknown relations among potentially corrupted users, we propose a novel bandit algorithm RCLUB-WCU. To detect the corrupted users, we devise a novel online detection algorithm OCCUD based on RCLUB-WCU's inferred user relations. We prove a regret upper bound for RCLUB-WCU, which asymptotically matches the lower bound with respect to $T$ up to logarithmic factors, and matches the state-of-the-art results in degenerate cases. We also give a theoretical guarantee for the detection accuracy of OCCUD. With extensive experiments, our methods achieve superior performance over previous bandit algorithms and high corrupted user detection accuracy.

Off-policy learning, referring to the procedure of policy optimization with access only to logged feedback data, has shown importance in various important real-world applications, such as search engines and recommender systems. While the ground-truth logging policy is usually unknown, previous work simply takes its estimated value for the off-policy learning, ignoring the negative impact from both high bias and high variance resulted from such an estimator. And these impact is often magnified on samples with small and inaccurately estimated logging probabilities. The contribution of this work is to explicitly model the uncertainty in the estimated logging policy, and propose an Uncertainty-aware Inverse Propensity Score estimator (UIPS) for improved off-policy learning, with a theoretical convergence guarantee. Experiment results on the synthetic and real-world recommendation datasets demonstrate that UIPS significantly improves the quality of the discovered policy, when compared against an extensive list of state-of-the-art baselines.

This paper studies a cooperative multi-agent bandit scenario in which the rewards observed by agents are heterogeneous—one agent’s meat can be another agent’s poison. Specifically, the total reward observed by each agent is the sum of two values: an arm-specific reward, capturing the intrinsic value of the arm, and a privately-known agent-specific reward, which captures the personal preference/limitations of the agent. This heterogeneity in total reward leads to different local optimal arms for agents but creates an opportunity for \textit{free exploration} in a cooperative setting—an agent can freely explore its local optimal arm with no regret and share this free observation with some other agents who would suffer regrets if they pull this arm since the arm is not optimal for them. We first characterize a regret lower bound that captures free exploration, i.e., arms that can be freely explored have no contribution to the regret lower bound. Then, we present a cooperative bandit algorithm that takes advantage of free exploration and achieves a near-optimal regret upper bound which tightly matches the regret lower bound up to a constant factor. Lastly, we run numerical simulations to compare our algorithm with various baselines without free exploration.

Template mining is one of the foundational tasks to support log analysis, which supports the diagnosis and troubleshooting of large scale Web applications. This paper develops a human-in-the-loop template mining framework to support interactive log analysis, which is highly desirable in real-world diagnosis or troubleshooting of Web applications but yet previous template mining algorithms fail to support it. We formulate three types of light-weight user feedback and based on them we design three atomic human-in-the-loop template mining algorithms. We derive mild conditions under which the outputs of our proposed algorithms are provably correct. We also derive upper bounds on the computational complexity and query complexity of each algorithm. We demonstrate the versatility of our proposed algorithms by combining them to improve the template mining accuracy of five representative algorithms over sixteen widely used benchmark datasets.

Voice assistants support contactless smart device control and thus act as a holy grail of human–computer interaction. However, recent studies reveal that an adversary can manipulate devices by vicious voice commands. This security risk is caused by only executing one-time liveness detection and lacking safeguard modules after service activation. Therefore, identifying speaker type (i.e., human articulators or loudspeakers) is critical in protecting voice-driven services during an entire interaction session. In this article, we propose a continuous voice liveness detection approach LiveProbe, leveraging unique energy response patterns in frequency bands induced by distinct voice generation mechanisms. The rationality behind LiveProbe is presented in two aspects: human articulator reshapes initial voices by exquisitely coordinated movements of vocal organs, which act as band-pass filters generating unique energy responses; nevertheless, the internal modules of loudspeakers are position fixed and cannot reproduce this response characteristic. To that end, we first work on voice generation mechanisms behind two-type speakers that cause spectrum differences. Then, we elaborately construct signal processing and deep-learning modules to extract liveness features. Especially, our approach does not interfere with normal voice interaction and need not to carry customized sensors. The experiment presents its effectiveness against potential attacks with a false acceptance rate of 0.51%.

Heart disease has now become a very common and impactful disease, which can actually be easily avoided if treatment is intervened at an early stage. Thus, daily monitoring of heart health has become increasingly important. Existing mobile heart monitoring systems are mainly based on seismocardiography (SCG) or photoplethysmography (PPG). However, these methods suffer from inconvenience and additional equipment requirements, preventing people from monitoring their hearts in any place at any time. Inspired by our observation of the correlation between pupil size and heart rate variability (HRV), we consider using the pupillary response when a user unlocks his/her phone using facial recognition to infer the user’s HRV during this time, thus enabling heart monitoring. To this end, we propose a computer vision-based mobile HRV monitoring framework-PupilHeart, designed with a mobile terminal and a server side. On the mobile terminal, PupilHeart collects pupil size change information from users when unlocking their phones through the front-facing camera. Then, the raw pupil size data is preprocessed on the server side. Specifically, PupilHeart uses a 1-D convolutional neural network (1-D CNN) to identify time series features associated with HRV. In addition, PupilHeart trains a recurrent neural network (RNN) with three hidden layers to model pupil and HRV. Employing this model, PupilHeart infers users’ HRV to obtain their heart condition each time they unlock their phones. We prototype PupilHeart and conduct both experiments and field studies to fully evaluate effectiveness of PupilHeart by recruiting 60 volunteers. The overall results show that PupilHeart can accurately predict the user’s HRV.

Nowadays distributed machine learning (ML) jobs usually adopt a parameter server (PS) framework to train models over large-scale datasets. Such ML job deploys hundreds of concurrent workers, and model parameter updates are exchanged frequently between workers and PSs. Current practice is that workers and PSs may be placed on different physical servers, bringing uncertainty in jobs’ runtime. Existing cloud pricing policy often charges a fixed price according to the job’s runtime. Although this pricing strategy is simple to implement, such pricing mechanism is not suitable for distributed ML jobs whose runtime is stochastic and can only be estimated according to its placement after job admission. To supplement existing cloud pricing schemes, we design a dynamic pricing and placement algorithm, DPS, for distributed ML jobs. DPS aims to maximize the cloud service provider’s profit, which dynamically calculates unit resource price upon a job’s arrival, and determines job’s placement to minimize its runtime if offered price is accepted to users. Our design exploits the multi-armed bandit (MAB) technique to learn unknown information based on past sales. DPS balances the exploration and exploitation stage, and selects the best price based on the reward which is related to job runtime. Our learning-based algorithm can increase the provider’s profit by 200%, and achieves a sub-linear regret with both the time horizon and the total job number, compared to benchmark pricing schemes. Extensive evaluations using real-world data also validates the efficacy of DPS.

Large pages are widely supported in modern hardware and OSes to reduce the overhead of TLB misses. However, memory deduplication can be inefficient with large pages, leading to low memory utilization. To simultaneously enjoy the benefits of high performance by accessing memory with large pages (e.g., 2 MB pages) and high deduplication rate by managing memory with base pages (e.g., 4 KB pages), we proposeSmartMemoryDeduplciation (SmartMD), which is an adaptive and efficient memory management scheme via mixed pages. Specifically, we propose lightweight schemes to periodically monitor pages’ access frequency and repetition rate, and present an adaptive conversion scheme to selectively split or reconstruct large pages. We further optimize SmartMD by developing SmartMD$^{+}$, which dynamically adjusts the page scanning cycle by monitoring the TLB miss cost, and reconstructs the split large pages in an on-demand way so as to reduce the CPU overhead of SmartMD. We further implement a prototype system and conduct extensive experiments with various workloads under different system settings. Experiment results show that SmartMD and SmartMD$^{+}$can simultaneously achieve high access performance similar to systems using large pages, and achieve a deduplication rate similar to that applying aggressive deduplication scheme (i.e., KSM) on base pages.

In clouds and data centers, GPU servers with multiple GPUs are widely deployed. Current state-of-the-art GPU scheduling policies are “static” in assigning applications to different GPUs. These policies usually ignore the dynamics of the GPU utilization and are often inaccurate in estimating resource demand before assigning/running applications, so there is a large opportunity to further balance the loads and improve GPU utilization. Based on CUDA (Compute Unified Device Architecture), we develop a runtime system called DCUDA which supports“dynamic”scheduling of running applications between multiple GPUs. In particular, DCUDA takes into consideration multidimensional resources, including computing cores, memory usage, and energy consumption. It first provides a real-time and lightweight method to accurately monitor the resource demand of applications and GPU utilization. Furthermore, it provides a universal migration facility to migrate“running applications”between GPUs with negligible overhead. More importantly, DCUDA transparently supports all CUDA applications without changing their source code. Experiments with our prototype system show that DCUDA can reduce 78.3% of overloaded time of GPUs on average. As a result, for different workloads consisting of a wide range of applications we studied, DCUDA can reduce the average execution time of general applications by up to 42.1%, and even up to 67% for memory-intensive tasks. Besides, DCUDA also reduces 13.3% of energy in light-load scenarios.

Detecting fake accounts (sybils) in online social networks (OSNs) is vital to protect OSN operators and their users from various malicious activities. Typical graph-based sybil detection (a mainstream methodology) assumes that sybils can make friends with only a limited (or small) number of honest users. However, recent evidences showed that this assumption does not hold in real-world OSNs, leading to low detection accuracy. To address this challenge, we explore users’ activities to assist sybil detection. The intuition is that honest users are much more selective in choosing who to interact with than to befriend with. We first develop thesocial and activity network(SAN), a two-layer hyper-graph that unifies users’ friendships and their activities, to fully utilize users’ activities. We also propose a more practical sybil attack model, where sybils can launch both friendship attacks and activity attacks. We then design Sybil_SAN to detect sybils via coupling three random walk-based algorithms on the SAN, and prove the convergence of Sybil_SAN. We develop an efficient iterative algorithm to compute the detection metric for Sybil_SAN, and derive the number of rounds needed to guarantee the convergence. We use“matrix perturbation theory”to bound the detection error when sybils launch many friendship attacks and activity attacks. Extensive experiments on both synthetic and real-world datasets show that Sybil_SAN is highly robust against sybil attacks, and can detect sybils accurately under practical scenarios, where current state-of-art sybil defenses have low accuracy. Lastly, we present two extensions of Sybil_SAN to further improve its accuracy.

Mobile edge computing (MEC) and device-to-device (D2D) offloading are two promising paradigms in the industrial Internet of Things (IIoT). In this article, we investigate task co-offloading, where computing-intensive industrial tasks can be offloaded to MEC servers via cellular links or nearby IIoT devices via D2D links. This co-offloading delivers small computation delay while avoiding network congestion. However, erratic movements, the selfish nature of devices and incomplete offloading information bring inherent challenges. Motivated by these, we propose a co-offloading framework, integrating migration cost and offloading willingness, in D2D-assisted MEC networks. Then, we investigate a learning-based task co-offloading algorithm, with the goal of minimal system cost (i.e., task delay and migration cost). The proposed algorithm enables IIoT devices to observe and learn the system cost from candidate edge nodes, thereby selecting the optimal edge node without requiring complete offloading information. Furthermore, we conduct simulations to verify the proposed co-offloading algorithm.

In enterprise management systems (EMS), augmented Intelligence of Things (AIoT) devices generate delay-sensitive and energy-intensive tasks for learning analytics, articulate clarifications, and immersive experiences. To guarantee effective task processing, in this work, we present a cloud-assisted fog computing framework with task offloading and service caching. In the framework, tasks make offloading decisions to determine local processing, fog processing, and cloud processing with the goal of minimal task delay and energy consumption, conditioned on dynamic service caching. To this end, we first propose a distributed task offloading algorithm based on noncooperative game theory. Then, we adopt the 0–1 knapsack method to realize dynamic service caching. At last, we adjust the offloading decisions for the tasks offloaded to the fog server but without caching service support. In addition, we conduct extensive experiments and the results validate the effectiveness of our proposed algorithms.

Random walk is widely applied to sample large-scale graphs due to its simplicity of implementation and solid theoretical foundations of bias analysis. However, its computational efficiency is heavily limited by theslow convergencerate (a.k.a. long burn-in period). To address this issue, we propose a common neighbor aware random walk framework called CNARW, which leverages weighted walking by differentiating the next-hop candidate nodes to speed up the convergence. Specifically, CNARW takes into consideration the common neighbors between previously visited nodes and next-hop candidate nodes in each walking step. Based on CNARW, we further develop two efficient “unbiased sampling” schemes, and we also design two variant algorithms which can reduce sampling cost and speed up the convergence. Experimental results on real-world network datasets show that our approach converges remarkably faster than the state-of-the-art random walk sampling algorithms; and to achieve the same estimation accuracy, our approach reduces the query cost significantly. Last, we use two case studies to demonstrate the effectiveness of our sampling framework in solving large-scale graph analysis tasks.

Random walk sampling is often used to conduct statistical estimation over graphs. This paper develops an algorithmic framework to reduce the mean square error of such statistical estimation. Our algorithmic framework is inspired by that the mean square error can be decomposed into a sum of the bias and variance of the estimator. More specifically, we apply the bootstrapping technique to design a bias reduction algorithm. Our bias reduction algorithm only utilizes a small number of valid sub-samples, which can reduce more bias of the estimator but may increase the variance of the estimator significantly. We use multiple parallel random walks to reduce this variance such that it can be reduced to arbitrarily small by deploying a sufficient number of random walks. We provide theoretical guarantees and computational complexity analysis of our proposed bias reduction algorithms. Also, the proposed bias reduction algorithm is generic and can be applied to optimize a large class of random walk sampling algorithms. Extensive experiments on four public datasets confirm the effectiveness and computational efficiency of our proposed algorithmic framework under the mean square metric and beyond.

There have been studies that consider optimizing applications in an online learning context using multi-armed bandit models. However, existing frameworks are problematic as they only consider finding the optimal decisions to minimize the regret, but neglect the constraints (or guarantee) requirements that may be excessively violated. In this paper, we formulate the stochastic constrained multi-armed bandit model with either ‘`time-varying’' or ‘`stochastic’' multi-level rewards for network application optimizations with guarantee by taking both regret and violation into consideration. Alongside this model, we design two constrained multi-armed bandit policies, Learning with Guarantee with time-Varying rewards (LG-V) and Learning with Guarantee with Stochastic rewards (LG-S), with provable sub-linear regret and violation bounds. Moreover, we illustrate how our policies can be applied to several emerging network application optimizations, namely, opportunistic multichannel selection, data-guaranteed mobile crowdsensing, and stability-guaranteed crowdsourced transcoding. To show the effectiveness of LG-V and LG-S in optimizing these applications with different requirements, we also conduct extensive simulations by comparing both LG-V and LG-S with existing state-of-the-art policies. We also show the impact of parameter variations, namely, the variations of the guarantee threshold and the number of selected arms, on the regrets and violations of LG-V and LG-S.

Multi-access edge computing promises satisfactory user experience by offloading tasks to the MEC server deployed at the network edge. However, since the MEC server is often resource-limited as compared to the cloud infrastructure, how to efficiently utilize its resources for system performance optimization becomes a challenge. In this paper, we study this problem with the aim at maximizing user's QoE through jointly optimizing service selection, computation resource allocation and task offloading decision, which is less studied in existing literature. We formulate a mixed-integer nonlinear programming problem (MINLP) for the task and propose a utility-based approach together with a low-complexity resource-efficiency based heuristic to address the problem. We consider realistic settings, where centralized solutions may not apply and an optimal mechanism needs to adapt as system operates. A distributed algorithm based on the Lagrangian-dual based decomposition theory is proposed, and we prove all sub-problems derived can be efficiently solved. In line with the current VM technology, we develop a cost-aware online algorithm that explicitly incorporates the cost of service switches into service selection and resource allocation. We evaluate our mechanism through both synthetic and trace-driven simulations, and results indicate they are effective as compared to representative baseline algorithms.

To provide fast and accurate risk evaluation on network rare threats, importance sampling (IS) is widely used in the rare threat simulation; however, it becomes costly to deal withmany rare threatssimultaneously. For example, a rare threat can be the failure to provide quality-of-service (QoS) guarantees to a critical network flow. Considering network providers often need to deal with many critical flows (i.e., rare threats) simultaneously, if using IS, network providers have to simulate each rare threat with its customized importance distribution individually. To reduce such simulation cost, we propose an efficient mixture importance distribution to simulate multiple rare threats, and then formulate a mixture importance sampling optimization problem (MISO) to select the optimal mixture. We first show that it is challenging to locate the optimal mixture for the “search direction” is computationally expensive to evaluate. We then formulate an online learning (OL) framework to estimate the “search direction” and learn the optimal mixture from simulation samples of threats. And our OL framework has a “zero learning cost” as the samples generated in the learn phase can be reused to provide accurate estimation on the rare threats. We develop two multi-armed bandit OL algorithms so as to: (1) Minimize the sum of estimation variances with a regret of$(\ln T)^2 {/} T$; and (2) Minimize the simulation cost with a regret of$\sqrt{\ln T {/} T}$, where$T$denotes the number of simulation samples. We demonstrate the versatility of our method on different network applications. When compared with the uniform mixture IS, our method reduces cost measures (i.e., sum of estimation variances and simulation cost) by as high as 61.6 percent in the Internet backbone network scenario.

Federated Learning (FL) is a new distributed machine learning (ML) approach which enables thousands of mobile devices to collaboratively train artificial intelligence (AI) models using local data without compromising user privacy. Although FL represents a promising computing paradigm, such training process can not be fully realized without an appropriate economic mechanism that incentivizes the participation of heterogeneous clients. This work targets social cost minimization, and studies the incentive mechanism design in FL through a procurement auction. Different from existing literature, we consider a practical scenario of FL where clients are selected and scheduled at different global iterations to guarantee the completion of the FL job, and capture the distinct feature of FL that the number of global iterations is determined by the local accuracy of all participants to balance between computation and communication. Our auction framework$A_{FL}$first decomposes the social cost minimization problem into a series of winner determination problems (WDPs) based on the number of global iterations. To solve each WDP,$A_{FL}$invokes a greedy algorithm to determine the winners, and a payment algorithm for computing remuneration to winners. Finally,$A_{FL}$returns the best solution among all WDPs. We carried out theoretical analysis to prove that$A_{FL}$is truthful, individual rational, computationally efficient, and achieves a near-optimal social cost. We further extend our model to consider multiple FL jobs with corresponding budgets and propose another efficient algorithm$A_{FL-M}$to solve the extended problem. We conduct large-scale simulations based on the real-world data and testbed experiments by adopting FL frameworks FAVOR and CoCoA. Simulation and experiment results show that both$A_{FL}$and$A_{FL-M}$can reduce the social cost by up to 55% compared with state-of-the-art algorithms.

In device to device (D2D) aided mobile edge computing (MEC) networks, by implementing content caching and D2D links, the edge server and nearby mobile devices can provide task offloading platforms. For parallel tasks, proper decisions on content caching and task offloading help reduce delay and energy consumption. However, what is often ignored in the previous works is the joint optimization of parallel task offloading and content caching. In this paper, we aim to find optimal content caching and parallel task offloading strategies, so as to minimize task delay and energy consumption. The minimization problem is formulated as a multi-objective optimization problem, concerning both content caching and parallel task offloading. The content caching is formulated as an integer knapsack problem (IKP). To solve the IKP problem, an enhanced Binary Particle Swarm Optimization algorithm is proposed. The parallel task offloading problem is formulated as a constrained multi-objective optimization problem, an improved multi-objective bat algorithm is proposed to address the problem. Experimental results show that our algorithm can decrease delay and energy cost by at most 45% and 56%, respectively. In addition, the parallel task offloading ratio remains over 91% even with large number of mobile devices (MDs).

Worker reliability estimation is a fundamental problem in crowdsensing applications. This paper proposes a robust feedback rating approach to estimate worker reliability explicitly. In this approach, the requester provides a feedback rating to reflect the quality of the sensor data submitted by each worker. The aggregation of each worker's historical feedback ratings serves as a reliability estimate. The challenges are:(1) Feedback ratings are subjected to noise; (2) Workers’ cognitive bias in task selection leads to sensor data quality variations.We develop a mathematical model to quantify rating noise from requesters and the degree of cognitive bias of workers in task selection. We derive sufficient conditions, under which the aggregate rating is asymptotically accurate in estimating worker reliability, via stochastic approximation techniques. These conditions identify a class of asymptotically accurate rating aggregation rules for crowdsensing applications. We further derive the minimum number of ratings needed to guarantee a given reliability estimation accuracy, via martingale theory. Via extensive experiments: (1) We reveal fundamental understandings on how various factors such as rating noise influence the minimum number of ratings needed to achieve certain accuracy; (2) We show that our feedback rating approach improves air quality index estimation accuracy by as high as 50 percent over the a typical baseline algorithm.

Multi-access edge computing (MEC) enables extreme low-latency AI services, such as Augmented Reality (AR) and Virtual Reality (VR), by deploying cloudlets in locations close to users. Meanwhile, a 5G hierarchical service market is emerging with both large-scale and small-scale network service providers competing for both computing and network bandwidth resources of an infrastructure provider. In this paper, we investigate the problem of caching services originally deployed in remote clouds to cloudlets in an MEC network in a hierarchical service market. For the service caching problem, we first propose a novel approximation-restricted framework that guarantees the stability of the 5G service market. Under the proposed framework, we first propose an approximation algorithm with a provable approximation ratio for the problem with non-selfish network service providers. We then design an efficient Stackelberg congestion game with selfish network service providers, and analyze the Price of Anarchy (PoA) of the proposed Stackelberg congestion game to measure the efficiency loss of the game due to selfishness of network service providers. Considering that the request rate of each service may not be given in advance, we study the service caching problem with the uncertainlity of request rates, and propose an approximation algorithm and a Stackelberg game via leveraging the randomized rounding technique. We finally evaluate the performance of the proposed algorithms and mechanisms by both simulations and implementations in a real test-bed. Results show that the performance of our proposed mechanisms achieve around 9.2% less cost than those of existing approaches.

Contextual bandit is a popular sequential decision-making framework to balance the exploration and exploitation tradeoff in many applications such as recommender systems, search engines, etc. Motivated by two important factors in real-world applications: 1) latent contexts (or features) often exist and 2) feedbacks often have humans in the loop leading to human biases, we formulate a generalized contextual bandit framework with latent contexts. Our proposed framework includes a two-layer probabilistic interpretable model for the feedbacks from human with latent features. We design a GCL-PS algorithm for the proposed framework, which utilizes posterior sampling to balance the exploration and exploitation tradeoff. We prove a sublinear regret upper bound for GCL-PS, and prove a lower bound for the proposed bandit framework revealing insights on the optimality of GCL-PS. To further improve the computational efficiency of GCL-PS, we propose a Markov Chain Monte Carlo (MCMC) algorithm to generate approximate samples, resulting in our GCL-PSMC algorithm. We not only prove a sublinear Bayesian regret upper bound for our GCL-PSMC algorithm, but also reveal insights into the tradeoff between computational efficiency and sequential decision accuracy. Finally, we apply the proposed framework to hotel recommendations and news article recommendations, and show its superior performance over a variety of baselines via experiments on two public datasets.

Remote Direct Memory Access (RDMA) suffers from unfairness issues and performance degradation when multiple applications share RDMA network resources. Hence, an efficient resource scheduling mechanism is urged to optimally allocates RDMA resources among applications. However, traditional Network Utility Maximization (NUM) based solutions are inadequate for RDMA due to three challenges: 1) The standard NUM-oriented algorithm cannot deal with coupling variables introduced by multiple dependent RDMA operations; 2) The stringent constraint of RDMA on-board resources complicates the standard NUM by bringing extra optimization dimensions; 3) Naively applying traditional algorithms for NUM suffers from scalability issues in solving a large-scale RDMA resource scheduling problem. In this paper, we present how to optimally share the RDMA resources in large-scale data center networks with a distributed manner. First, we propose Distributed RDMA NUM (DRUM) to model the RDMA resource scheduling problem as a new variation of the NUM problem. Second, we present distributed algorithms to efficiently solve the large-scale, interdependent RDMA resource sharing problem for different RDMA use cases. Through theoretical analysis, the convergence and parallelism of proposed algorithms are guaranteed. Finally, we implement the algorithms as a kernel-level indirection module in the real-world RDMA environment, so as to provide end-to-end resource sharing and performance guarantee. Through extensive evaluations by large-scale simulations and testbed experiments, we show that our method significantly improves applications’ performance under resource contention, achieving$1.7-3.1\times $higher throughput, and in a dynamic context, the largest performance improvement reaches 98.1% and 64.1% in terms of latency and throughput, respectively.

Edge computing provides a platform facilitating edge servers to contribute to computation offloading while economizing their resources. Traditional offloading solutions are mostly centralized, which are unscalable for large-scale edge computing networks due to complex interactions among many edge servers. Meanwhile, dynamic pricing for an operator is equally, if not more, important to accommodate users’ time-varying demands for computing services. In this paper, we develop a decentralized online optimization framework to jointly minimize the server’s cost of workload scheduling while maximizing the operator’s utility of service pricing. Specifically, we employ the mean field game to model the collective scheduling behavior of all edge servers, thereby enabling optimal decision making only based on the server’s local information. Considering the service price in practice is not adjusted as frequently as the scheduling process, we establish a two-timescale optimization framework, where workload scheduling at a small timescale is tightly embedded into service pricing at a large timescale. Using mean field approximation, we derive the closed-form expression for the minimum scheduling cost, and the approximation error is$O\left ({\frac {1}{\sqrt {M}}}\right)$which declines as the number of edge servers$M$increases. By characterizing the influence of workload scheduling on dynamic pricing, we transform the complex service utility maximization into a succinct but equivalent problem, and thus we can make use of Lyapunov optimization to determine the optimal price over time. Extensive evaluations validate the effectiveness and optimality of our scheduling and pricing schemes.

The Shapley value is a cornerstone in cooperative game theory and has been widely applied in networking, data science, etc. The classical Shapley value assumes that each player has an equal preference to cooperate with each other. Since the cooperation preference is an important factor of a variety of networking applications, we first generalize the classical Shapley value to allow general degree of the cooperation preference. In particular, we develop mathematical models to solicit two types of cooperation preferences, i.e., (1) group-wise preferences and (2) pair-wise preferences, and extend the classical Shapley value to capture this feature. Our second contribution is tackling the intrinsic computational challenge because even for the classical Shapley value, it is computationally expensive to evaluate. We design computationally efficient randomized algorithms with theoretical guarantees to fully cover the computational space of our generalized Shapley value. We also extend our models and algorithms to divide payoffs for multiple coalitions with dynamic preferences. We demonstrate the versatility of our framework by applying it to divide the revenue among ISPs in deploying new Internet architectures, as well as to divide the reward among workers in crowdsourcing systems.

Communication scheduling is crucial to accelerate the training of large deep learning models, in which the transmission order of layer-wise deep neural network (DNN) tensors is determined for a better computation-communication overlap. Prior approaches adopt user-level tensor partitioning to enhance the priority scheduling with finer granularity. However, a startup time slot inserted before every tensor partition will neutralize this scheduling gain. Tuning hyper-parameters for tensor partitioning is difficult, especially when the network bandwidth is shared or time-varying in multi-tenant clusters. In this article, we propose Mercury, a simple transport layer scheduler that moves the priority scheduling to the transport layer at the packet granularity. The packets with the highest priority in the Mercury buffer will be transmitted first. Mercury achieves the near-optimal overlapping between communication and computation. It also leverages the immediate aggregation at the transport layer to enable the full overlapping of gradient push and pull. We implement Mercury in MXNet and conduct comprehensive experiments on five popular DNN models in various environments. Mercury can well adapt to dynamic communication and computation resources. Experiments show that Mercury accelerates the training by up to 130% compared to the classical PS architecture, and 104% compared to state-of-the-art tensor partitioning methods.

Online influence maximization has attracted much attention as a way to maximize influence spread through a social network while learning the values of unknown network parameters. Most previous works focus on single-item diffusion. In this paper, we introduce a new Online Competitive Influence Maximization (OCIM) problem, where two competing items (e.g., products, news stories) propagate in the same network and influence probabilities on edges are unknown. We adopt a combinatorial multi-armed bandit (CMAB) framework for OCIM, but unlike the non-competitive setting, the important monotonicity property (influence spread increases when influence probabilities on edges increase) no longer holds due to the competitive nature of propagation, which brings a significant new challenge to the problem. We provide a nontrivial proof showing that the Triggering Probability Modulated (TPM) condition for CMAB still holds in OCIM, which is instrumental for our proposed algorithms OCIM-TS and OCIM-OFU to achieve sublinear Bayesian and frequentist regret, respectively. We also design an OCIM-ETC algorithm that requires less feedback and easier offline computation, at the expense of a worse frequentist regret bound. Experimental evaluations demonstrate the effectiveness of our algorithms.

Federated learning (FL) has been widely regarded as a promising distributed machine learning technology that utilizes on-device computation while protecting clients' data privacy. To adapt FL to wireless networks, the over-the-air (OTA) computation, which employs the superposition nature of wireless waveforms, can prevent excessive consumption of the communication resources. However, energy harvesting technology can overcome the energy limitation of clients to realize durable computation. Despite the existing works devoted to OTA FL from various aspects, they mostly neglect jointly performing client selection and energy management for energy harvesting devices. In this paper, we investigate the combined problem of client selection and energy management for OTA FL and formulate it as a nonlinear integer programming (NIP) problem to minimize the optimality gap. To solve the NIP problem, we propose a client selection scheme that jointly considers channel state information, residual battery capacities, and dataset size. Our simulation results show that the proposed solution outperforms other comparison schemes within various parameter settings.

We generalize the multiple-play multi-armed bandits (MP-MAB) problem with a shareable arms setting, in which several plays can share the same arm. Furthermore, each shareable arm has a finite reward capacity and a “per-load” reward distribution, both of which are unknown to the learner. The reward from a shareable arm is load-dependent, which is the “per-load” reward multiplying either the number of plays pulling the arm, or its reward capacity when the number of plays exceeds the capacity limit. When the “per-load” reward follows a Gaussian distribution, we prove a sample complexity lower bound of learning the capacity from load-dependent rewards and also a regret lower bound of this new MP-MAB problem. We devise a capacity estimator whose sample complexity upper bound matches the lower bound in terms of reward means and capacities. We also propose an online learning algorithm to address the problem and prove its regret upper bound. This regret upper bound’s first term is the same as regret lower bound’s, and its second and third terms also evidently correspond to lower bound’s. Extensive experiments validate our algorithm’s performance and also its gain in 5G & 4G base station selection.

MPTCP provides the basic multipath support for network applications to deliver high throughput and robust communication. However, the original MPTCP is designed with limited extensibility. Various research works have tried to extend MPTCP to attain better performance or richer functionalities. These existing approaches either modify the kernel implementation of MPTCP, which involve considerable engineering efforts and may accidentally introduce security issues, or control MPTCP via user-space tools, which suffer from restricted functionality support. To address this issue, we propose eMPTCP, an easy-to-use framework to fully extend MPTCP without security risks. Internally, eMPTCP has a modular and pluggable model which allows operators to specify a comprehensive MPTCP extension as a chain of sub-policies. eMPTCP further enforces the policies through packet header manipulations. To ensure safety, eMPTCP is implemented using eBPF. Despite the stringent constraints of eBPF, we show that it is possible to implement an elaborated framework for a fully extensible MPTCP. Through verifying MPTCP in a number of real-world cases and extensive experiments, we show that eMPTCP is able to support a wide range of MPTCP extensions, while the overhead of eMPTCP operations in the kernel is in the scale of nanosecond, and the extra processing time accounts for only about 0.63% of flows' transmission time.

Reposting plays an essential role in visibility boosting in online social networks (OSNs). In this paper, we study the problem of designing “reposting service” in an OSN to incentivize “transactions” between requesters (users who seek to enhance visibility) and suppliers (users who are willing to repost if certain incentives are given), and maximize the welfare increase accumulated through a given time horizon. We formulate a mathematical model for reposting which captures various factors like click through rates (CTRs), requesters' valuations and suppliers' costs. We formulate the problem of maximizing the welfare increase via judiciously assigning suppliers to requesters from two aspects: (a) “user-centric” and (b) “platform-centric”. The user-centric aspect deals with the situation where requesters and suppliers would collaborate and share valuations and costs. To address the challenge of unknown CTRs, we propose an online learning protocol and achieve a sub-linear regret. The platform-centric aspect corresponds to the scenario where users keep their valuations or costs private. To address the challenges of unknown CTR, valuations and costs, we design an “explore-then-commit” online protocol which can be proved to be truthful. Lastly, we conduct extensive experiments to evaluate the efficiency and effectiveness of the proposed protocols.

Distributed graph systems often leverage a cluster of machines by partitioning a large graph into multiple small-size subgraphs. Thus, graph partition usually has a significant impact on the performance of distributed graph systems. However, existing widely used partition schemes in practical graph systems can realize a good balance only in one dimension, e.g., either the number of vertices or the number of edges, and they may also incur lots of edge cuts. To address the problem, we develop BPart, which adopts a two-phase partition scheme to realize two-dimensional balance for both vertices and edges. Its core idea is to first partition the original graph into more small pieces than the cluster scale, and combine the partition to realize desired properties, then selectively combine the small pieces to construct larger subgraphs to generate two-dimensional balanced partition. We implement BPart into two open-source distributed graph systems, Gemini [58] and KnightKing [57]. Results show that BPart realizes good balance in both dimensions, and also significantly reduces the number of edge cuts. As a result, BPart reduces the total running time of various graph applications by 5% - 70%, compared to multiple existing partition schemes, e.g., Chunk-V, Chunk-E, Fennel, and Hash.

Multi-player multi-armed bandits (MMAB) study how decentralized players cooperatively play the same multi-armed bandit so as to maximize their total cumulative rewards. Existing MMAB models mostly assume when more than one player pulls the same arm, they either have a collision and obtain zero rewards or have no collision and gain independent rewards, both of which are usually too restrictive in practical scenarios. In this paper, we propose an MMAB with shareable resources as an extension of the collision and non-collision settings. Each shareable arm has finite shareable resources and a “per-load” reward random variable, both of which are unknown to players. The reward from a shareable arm is equal to the “per-load” reward multiplied by the minimum between the number of players pulling the arm and the arm’s maximal shareable resources. We consider two types of feedback: sharing demand information (SDI) and sharing demand awareness (SDA), each of which provides different signals of resource sharing. We design the DPE-SDI and SIC-SDA algorithms to address the shareable arm problem under these two cases of feedback respectively and prove that both algorithms have logarithmic regrets that are tight in the number of rounds. We conduct simulations to validate both algorithms’ performance and show their utilities in wireless networking and edge computing.

Mobile edge computing facilitates users to offload computation tasks to edge servers for meeting their stringent delay requirements. Previous works mainly explore task offloading when system-side information is given (e.g., server processing speed, cellular data rate), or centralized offloading under system uncertainty. But both generally fall short of handling task placement involving many coexisting users in a dynamic and uncertain environment. In this paper, we develop a multi-user offloading framework considering unknown yet stochastic system-side information to enable a decentralized user-initiated service placement. Specifically, we formulate the dynamic task placement as an online multi-user multi-armed bandit process, and propose a decentralized epoch based offloading (DEBO) to optimize user rewards which are subject to the network delay. We show that DEBO can deduce the optimal user-server assignment, thereby achieving a close-to-optimal service performance and tight O(log T ) offloading regret. Moreover, we generalize DEBO to various common scenarios such as unknown reward gap, dynamic entering or leaving of clients, and fair reward distribution, while further exploring when users’ offloaded tasks require heterogeneous computing resources. Particularly, we accomplish a sub-linear regret for each of these instances. Real measurements based evaluations corroborate the superiority of our offloading schemes over state-of-the-art approaches in optimizing delay-sensitive rewards.

This paper tackles a multi-agent bandit setting where M agents cooperate together to solve the same instance of a K-armed stochastic bandit problem. The agents are heterogeneous: each agent has limited access to a local subset of arms and the agents are asynchronous with different gaps between decision-making rounds. The goal for each agent is to find its optimal local arm, and agents can cooperate by sharing their observations with others. While cooperation between agents improves the performance of learning, it comes with an additional complexity of communication between agents. For this heterogeneous multi-agent setting, we propose two learning algorithms, CO-UCB and CO-AAE. We prove that both algorithms achieve order-optimal regret, which is $O\left({{\sum _{i:{{\bar \Delta }_i} > 0}}\log T/{{\tilde \Delta }_i}}\right)$, where ${\tilde \Delta _i}$ is the minimum suboptimality gap between the reward mean of arm i and any local optimal arm. In addition, a careful selection of the valuable information for cooperation, CO-AAE achieves a low communication complexity of O(log T). Last, numerical experiments verify the efficiency of both algorithms.

There is a growing trend that network applications not only require higher throughput, but also impose stricter delay requirements. The current Internet congestion control, which is driven by active queue management (AQM) algorithms interacting with the Transmission Control Protocol (TCP), has been playing an important role in supporting network applications. However, it still exhibits many open issues. Most of AQM algorithms only deploy a single-queue structure that cannot differentiate flows and easily leads to unfairness. Moreover, the parameter settings of AQM are often static, making them difficult to adapt to the dynamic network environments. In this paper, we propose a general framework for designing "self-tuning" queue management (SQM), which is adaptive to the changing environments and provides fair congestion control among flows. We first present a general architecture of SQM with fair queueing and propose a general fluid model to analyze it. To adapt to the stochastic environments, we formulate a stochastic network utility maximization (SNUM) problem, and utilize online convex optimization (OCO) and control theory to develop a distributed SQM algorithm which can self-tune different queue weights and control parameters. Numerical and packet-level simulation results show that our SQM algorithm significantly improves queueing delay and fairness among flows.

This paper studies the strongly-convex-strongly-concave minimax optimization with unbalanced dimensionality. Such problems contain several popular applications in data science such as few shot learning and fairness-aware machine learning task. The design of conventional iterative algorithm for minimax optimization typically focuses on reducing the total number of oracle calls, which ignores the unbalanced computational cost for accessing the information from two different variables in minimax. We propose a novel second-order optimization algorithm, called Partial-Quasi-Newton (PQN) method, which takes the advantage of unbalanced structure in the problem to establish the Hessian estimate efficiently. We theoretically prove our PQN method converges to the saddle point faster than existing minimax optimization algorithms. The numerical experiments on real-world applications show the proposed PQN performs significantly better than the state-of-the-art methods.

The classic utility maximization framework studies the fairness-efficiency tradeoff in various resource allocation problems (e.g., bandwidth allocation). The weighted alpha-fair utility is a common utilitarian metric. However, this classic framework cannot tackle those allocation problems with the online decision-making requirement (e.g., caching capacity allocation under unknown requests). Existing studies on these online allocation problems largely follow the online learning approaches, thus inevitably overlook the allocation fairness. In this paper, we propose a novel utility maximization framework accommodating the online setting. The major challenge of designing this framework lies in the tight coupling between the desirable fairness guarantee and the unknown allocation efficiency. To tackle this, we integrate the weighted alpha-fair utility with the learning rationale, by properly devising the merit-based weights and the increasing fairness levels. Under our proposed framework, the utility-maximizing allocation in each time slot is weighted alpha-fair. Our framework also performs asymptotically as well as the offline optimal/efficient outcome. We demonstrate how this framework functions in two networking applications. In size-based scheduling, it enables network switches to prioritize short flows and avoid flow starvation without the prior flow size information. In file caching, our framework outperforms several state-of-the-art caching policies up to 21% in terms of cache-hit-ratio.

In this paper, we study the combinatorial semi-bandits (CMAB) and focus on reducing the dependency of the batch-size $K$ in the regret bound, where $K$ is the total number of arms that can be pulled or triggered in each round. First, for the setting of CMAB with probabilistically triggered arms (CMAB-T), we discover a novel (directional) triggering probability and variance modulated (TPVM) condition that can replace the previously-used smoothness condition for various applications, such as cascading bandits, online network exploration and online influence maximization. Under this new condition, we propose a BCUCB-T algorithm with variance-aware confidence intervals and conduct regret analysis which reduces the $O(K)$ factor to $O(\log K)$ or $O(\log^2 K)$ in the regret bound, significantly improving the regret bounds for the above applications. Second, for the setting of non-triggering CMAB with independent arms, we propose a SESCB algorithm which leverages on the non-triggering version of the TPVM condition and completely removes the dependency on $K$ in the leading regret. As a valuable by-product, the regret analysis used in this paper can improve several existing results by a factor of $O(\log K)$. Finally, experimental evaluations show our superior performance compared with benchmark algorithms in different applications.

Internet of Things (IoT) services are gaining increasing popularity, and IoT devices are widely deployed at many smart homes. Among all the IoT communication protocols, Zigbee is a dominant one used by billions of devices and customers. However, the design of Zigbee has not been carefully evaluated and could be exploited by attackers. In this paper, we focus on Zigbee’s network rejoin procedure, which aims to allow devices to automatically recover their network status when they accidentally go offline. We develop an automated verification tool Verejoin to perform a systematic study on the rejoin procedure. Using this tool, we not only confirm a well-known design flaw, but also reveal two undiscovered design flaws. Moreover, we construct four proof-of-concept (PoC) attacks to exploit these design flaws. These vulnerabilities create new attack surfaces for attackers to manipulate Zigbee devices, and the damage of these vulnerabilities ranges from denial of service to device hijacking. We further design a Zigbee testing tool ZigHomer to confirm these vulnerabilities in real-world devices. Using ZigHomer, we conduct thorough evaluations of off-the-shelf Zigbee devices from leading IoT vendors, and the evaluation result shows the prevalence and severity of these vulnerabilities. Finally, we reported our findings to related parties, and they all acknowledged the significant security impact. We further collaborate with Zigbee Alliance to amend the Zigbee specification, and successfully addressed our reported vulnerabilities.

Contextual multi-armed bandit (MAB) is an important sequential decision-making problem in recommendation systems. A line of works, called the clustering of bandits (CLUB), utilize the collaborative effect over users and dramatically improve the recommendation quality. Owing to the increasing application scale and public concerns about privacy, there is a growing demand to keep user data decentralized and push bandit learning to the local server side. Existing CLUB algorithms, however, are designed under the centralized setting where data are available at a central server. We focus on studying the federated online clustering of bandit (FCLUB) problem, which aims to minimize the total regret while satisfying privacy and communication considerations. We design a new phase-based scheme for cluster detection and a novel asynchronous communication protocol for cooperative bandit learning for this problem. To protect users’ privacy, previous differential privacy (DP) definitions are not very suitable, and we propose a new DP notion that acts on the user cluster level. We provide rigorous proofs to show that our algorithm simultaneously achieves (clustered) DP, sublinear communication complexity and sublinear regret. Finally, experimental evaluations show our superior performance compared with benchmark algorithms.

Distributed access control is a crucial component for massive machine type communication (mMTC). In this communication scenario, centralized resource allocation is not scalable because resource configurations have to be sent frequently from the base station to a massive number of devices. We investigate distributed reinforcement learning for resource selection without relying on centralized control. Another important feature of mMTC is the sporadic and dynamic change of traffic. Existing studies on distributed access control assume that traffic load is static or they are able to gradually adapt to the dynamic traffic. We minimize the adaptation period by training TinyQMIX, which is a lightweight multi-agent deep reinforcement learning model, to learn a distributed wireless resource selection policy under various traffic patterns before deployment. Therefore, the trained agents are able to quickly adapt to dynamic traffic and provide low access delay. Numerical results are presented to support our claims.

As mobile shopping has gradually become the mainstream shopping mode, recommendation systems are gaining an increasingly wide adoption. Existing recommendation systems are mainly based on explicit and implicit user behaviors. However, these user behaviors may not directly indicate users’ inner feelings, causing erroneous user preference estimation and thus leading to inaccurate recommendations. Inspired by our key observation on the correlation between pupil size and users’ inner feelings, we consider using the change of pupil size when browsing to model users’ preferences, so as to achieve targeted recommendations. To this end, we propose PupilRec as a computer-vision-based recommendation framework involving a mobile terminal and a server side. On the mobile terminal, PupilRec collects users’ pupil size change information through the front camera of smartphones; it then preprocesses the raw pupil size data before transmitting them to the server. On the server side, PupilRec utilizes the Tsfresh package and Random Forest algorithm to figure out the key time-series features directly implying user preferences. PupilRec then trains a neural network to fit a user preference model. Using this model, PupilRec predicts user preference to obtain a user–product matrix and further simplifies it by singular value decomposition. Finally, the real-time recommendation is achieved by a collaborative filtering module that retrieves recommended contents to users smartphones. We prototype PupilRec and conduct both experiments and field studies to comprehensively evaluate the effectiveness of PupilRec by recruiting 67 volunteers. The overall results show that PupilRec can accurately estimate users’ preference and can recommend products users interested in.

The efficiency of a large-scale edge computing system primarily depends on three aspects: i) edge server provision, ii) task migration, and iii) computing resource configuration. In this paper, we study the dynamic resource configuration for hybrid edge server provision under two decentralized task migration schemes. We formulate the dynamic resource configuration as an online cost minimization problem, aiming to jointly minimize performance degradation and operation expenditure. Due to the stochastic nature, it is an online learning problem with partial feedback. To address it, we derive a deterministic mean field model to approximate the stochastic edge computing system. We show that the mean field model provides the increasingly accurate full feedback as the system scales. We then propose a learning policy based on the mean field model, and show that our proposed policy performs asymptotically as well as the offline optimal configuration. We provide two ways of setting the policy parameters, which achieve a constant competitive ratio (under certain mild conditions) and a sub-linear regret, respectively. Numerical results show that the mean field model significantly improves the convergence speed. Moreover, our proposed policy under the decentralized task migration schemes considerably reduces the operating cost (by 23%) and incurs little communication overhead.

Contextual bandit serves as an invaluable tool to balance theexploration vs. exploitationtradeoff in various applications such as online recommendation. In many applications,heterogeneous information networks(HINs) provide rich side information for contextual bandits, such as different types of attributes and relationships among users and items. In this article, we propose the first HIN-assisted contextual bandit framework, which utilizes a given HIN to assist contextual bandit learning. The proposed framework uses meta-paths in HIN to extract rich relations among users and items for the contextual bandit. The main challenge is how to leverage these relations, since users’ preference over items, the target of our online learning, are closely related to users’ preference over meta-paths. However, it is unknown which meta-path a user prefers more. Thus, both preferences are needed to be learned in an online fashion with exploration vs. exploitation tradeoff balanced. We propose the HIN-assisted upper confidence bound (HUCB) algorithm to address such a challenge. For each meta-path, the HUCB algorithm employs an independent base bandit algorithm to handle online item recommendations by leveraging the relationship captured in this meta-path. A bandit master is then employed to learn users’ preference over meta-paths to dynamically combine base bandit algorithms with a balance of exploration vs. exploitation tradeoff. We theoretically prove that the HUCB algorithm can achieve similar performance compared with the optimal algorithm where each user is served according to his true preference over meta-paths (assuming the optimal algorithm knows the preference). Moreover, we prove that the HUCB algorithm benefits from leveraging HIN in achieving a smaller regret upper bound than the baseline algorithm without leveraging HIN. Experimental results on a synthetic dataset, as well as real datasets from LastFM and Yelp demonstrate the fast learning speed of the HUCB algorithm.

In the past few years, many companies are considering “social recommendation” for their businesses, e.g., firms are offering rewards to customers who recommend the firms’ products/services in online social networks (OSNs). However, the pros and cons of such social recommendation scheme are still unclear. Thus, it is difficult for firms to design rewarding schemes, and for OSN platforms to design regulating policies. By analyzing real data from Weixin and Yelp, we first identify key factors that affect the spreading of products/services in OSNs. These findings enable us to develop an accurate (i.e., with a high validation accuracy) mathematical model on social recommendations. Our model captures how users decide whether to recommend an item, which is a key factor but often ignored by previous social recommendation models such as the “Independent Cascade model”. We also design algorithms to infer model parameters. Using our model, we uncover conditions when social recommendation improves a firm’s profit and users’ utilities, as well as when it cannot improve the profit or hurts users’ utilities. These conditions help the design of both rewarding schemes and regulating policies. Moreover, we extend our model to a dynamic setting, so that a firm can improve its profit by dynamically optimizing its rewarding schemes.

Understanding mobile data traffic and forecasting future traffic trend is beneficial to wireless carriers and service providers who need to perform resource allocation and energy saving management. However, predicting wireless traffic accurately at large-scale and fine-granularity is particularly challenging due to the following two factors: the spatial correlations between the network units (i.e., a cell tower or an access point) introduced by user arbitrary movements, and the time-evolving nature of user movements which frequently changes with time. In this paper, we use a time-evolving graph to formulate the time-evolving nature of user movements, and propose a model Graph-based Temporal Convolutional Network (GTCN) to predict the future traffic of each network unit in a wireless network. GTCN can bring significant benefits to two aspects. (1) GTCN can effectively learn intra- and inter-time spatial correlations between network units in a time-evolving graph through a node aggregation method. (2) GTCN can efficiently model the temporal dynamics of the mobile traffic trend from different network units through a temporal convolutional layer. Experimental results on two real-world datasets demonstrate the efficiency and efficacy of our method. Compared with state-of-the-art methods, the improvement of the prediction performance of our GTCN is 3.2 to 10.2 percent for different prediction horizons. GTCN also achieves 8.4× faster on prediction time.

Small cells are deployed in 5G networks to complement the macro cells for improving coverage and capacity. Small cells and edge computing are natural partners which can improve users’ experience. Small cell nodes (SCNs) equipped with edge servers can support emerging computing services, such as virtual reality which impose low-latency and precise contextual requirements. With the proliferation of wireless devices, there is an increasing demand for offloading tasks to SCNs. Given limited computation and communication resources, the fundamental problem for a small cell network is how to select computing tasks to maximize effective rewards in an uncertain and stochastic environment. To this end, we propose an online learning framework, LFSC, which has the performance guarantee to guide task offloading in a small cell network. LFSC balances between reward and constraint violations, and it consists of three subroutines: i) a randomized algorithm which calculates selection probability of each task based on task weights; ii) a greedy assignment algorithm which cooperatively allocates tasks among different SCNs based on the selection probability; iii) an update algorithm which exploits the multi-armed bandit (MAB) technique to update task weights according to the feedback. Our theoretical analysis shows that both the regret and violations metrics of LFSC have the sub-linear property. Extensive simulation studies based on real world data confirm that LFSC achieves a close-to-optimal reward with low violations, and outperforms many state-of-the-art algorithms.

How to generate more revenues is crucial to cloud providers. Evidences from the Amazon cloud system indicate that "dynamic pricing" would be more profitable than "static pricing." The challenges are: How to set the price in real-time so to maximize revenues? How to estimate the price dependent demand so to optimize the pricing decision? We first design a discrete-time based dynamic pricing scheme and formulate a Markov decision process to characterize the evolving dynamics of the price-dependent demand. We formulate a revenue maximization framework to determine the optimal price and theoretically characterize the "structure" of the optimal revenue and optimal price. We apply the Q -learning to infer the optimal price from historical transaction data and derive sufficient conditions on the model to guarantee its convergence to the optimal price, but it converges slowly. To speed up the convergence, we incorporate the structure of the optimal revenue that we obtained earlier, leading to the VpQ-learning ( Q -learning with value projection) algorithm. We derive sufficient conditions, under which the VpQ-learning algorithm converges to the optimal policy. Experiments on a real-world dataset show that the VpQ-learning algorithm outperforms a variety of baselines, i.e., improves the revenue by as high as 50% over the Q -learning, speedy Q -learning, and adaptive real-time dynamic programming (ARTDP), and by as high as 20% over the fixed pricing scheme.

With the popularization of Internet of Things (IoT) devices in smart home and industry fields, a huge number of IoT devices are connected to the Internet. However, what devices are connected to a network may not be known by the Internet Service Provider (ISP), since many IoT devices are placed within small networks (e.g., home networks) and are hidden behind network address translation (NAT). Without pinpointing IoT devices in a network, it is unlikely for the ISP to appropriately configure security policies and effectively manage the network. Additionally, inferring fine-grained user interactions of IoT devices is also an interesting yet unresolved problem. In this paper, we design an efficient and scalable system via spatial-temporal traffic fingerprinting from an ISP’s perspective in consideration of practical issues like learning-testing asymmetry. Our system can accurately identify typical IoT devices in a network, with the additional capability of identifying what devices are hidden behind NAT and the number of each type of device that share the same IP address. Our system can also detect user interactions and meanwhile identify their (concurrent) number through a multi-output regression model. Through extensive evaluation, we demonstrate that the system can generally identify IoT devices with an F1-Score above 0.999, and estimate the number of the same type of IoT device behind NAT with an average error below 5%. By studying 29 user interactions of 7 devices, we show that our system is promising in detecting user interactions.

Truth discovery is an effective paradigm which could reveal the truth from crowdsouced data with conflicts, enabling data-driven decision-making systems to make quick and smart decisions. The increasing privacy concern promotes users to perturb or encrypt their private data before outsourcing, which poses significant challenges for truth discovery. Although several privacy-preserving truth discovery mechanisms have been proposed, none of them take personal privacy expectation into consideration. In this work, we propose a novel personalized privacy-preserving truth discovery (PPPTD) framework over crowdsourced data streams to achieve timely and accurate truth discovery while guaranteeing the protection of individual privacy. The key challenges of PPPTD lie in improving the accuracy of truth estimation from the perturbed streaming data with personalized protection level. To address these challenges, we first develop a personalized budget initialization mechanism to quantify each user’s privacy protection requirement, and allocate personalized privacy budgets to users according to their privacy requirements. Then we propose a deviation-aware weighted aggregation method to improve the accuracy of truth discovery from streaming data with varying degrees of perturbation. In order to achieve privacy-utility tradeoff, we further propose an influence-aware adaptive budget adjustment mechanism that adaptively re-allocates privacy budgets to users based on the evolution of their influence in the weighted aggregation. We prove that PPPTD can achieve$\epsilon $-differential privacy over the whole data generated by users and satisfy individual personalized privacy requirements. Extensive experiments on two real-world datasets demonstrate the effectiveness of PPPTD.

The scheduling policy installed on switches of datacenters plays a significant role on congestion control. Shortest-Remaining-Processing-Time (SRPT) achieves the near-optimal average message completion time (MCT) in various scenarios, but is difficult to deploy as viewed by the industry. The reasons are two-fold: 1) many commodity switches only provide FIFO queues, and 2) the information of remaining message size is not available. Recently, the idea of emulating SRPT using only a few FIFO queues and the original message size has been coined as the approximate and deployable SRPT (ADS) design. In this paper, we provide the first theoretical study on the optimal ADS design. Specifically, we first characterize a wide range of feasible ADS scheduling policies via a unified framework, and then derive the steady-state MCT, slowdown, and impoliteness in the M/G/1 setting. Hence we formulate the optimal ADS design as a non-linear combinatorial optimization problem, which aims to minimize the average MCT given the available FIFO queues. We also take into account the proportional fairness and temporal fairness constraints based on the maximal slowdown and impoliteness, respectively. The optimal ADS design problem is NP-hard in general, and does not exhibit monotonicity or sub-modularity. We leverage its decomposable structure and devise an efficient algorithm to solve the optimal ADS policy. We carry out extensive flow-level simulations and packet-level experiments to evaluate the proposed optimal ADS design. Results show that the optimal ADS policy installed on eight FIFO queues is capable of emulating the true SRPT.

Traditional graph systems mainly use the iteration-based model, which iteratively loads graph blocks into memory for analysis so as to reduce random I/Os. However, this iteration-based model limits the efficiency and scalability of running random walk, which is a fundamental technique to analyze large graphs. In this article, we first propose a state-aware I/O model to improve the I/O efficiency of running random walk, then we develop a block-centric indexing and buffering scheme for managing walk data, and leverage an asynchronous walk updating strategy to improve random walk efficiency. We implement an I/O-efficient graph system, GraphWalker , which is efficient to handle very large disk-resident graphs and also scalable to run tens of billions of random walks with only a single commodity machine. Experiments show that GraphWalker can achieve more than an order of magnitude speedup when compared with DrunkardMob, which is tailored for random walks based on the classical graph system GraphChi, as well as two state-of-the-art single-machine graph systems, Graphene and GraFSoft. Furthermore, when compared with the most recent distributed system KnightKing, GraphWalker still achieves comparable performance with only a single machine, thereby making it a more cost-effective alternative.

In online social networks (OSNs), users may want to enhance their social visibility, as it can make their contents, i.e., opinions, videos, pictures, etc., attract attention from more users. Motivated by this, we propose a mechanism, where the OSN operator provides a "social visibility boosting service" to incentivize "transactions" between requesters (users who seek to enhance their social visibility via adding new "neighbors") and suppliers (users who are willing to be added as a new "neighbor" of any requester when certain "rewards" is provided). We design a posted pricing scheme for the OSN provider to charge the requesters who use such boosting service, and reward the suppliers who contribute to such boosting service. The OSN operator keeps a fraction of the payment from requesters and distributes the remaining part to participating suppliers "fairly" via a scheme based on the Shapley value. The objective of the OSN provider is to select the price and supplier set to maximize the revenue under the budget constraint of requesters. We first show that the revenue maximization problem is not simpler than an NP-hard problem. We then decompose it into two subroutines, prove the hardness of each sub-routine, and eventually design computationally efficient approximation algorithms to solve the revenue maximization problem. We conduct extensive experiments to evaluate our proposed algorithms.

Safe system programming is often a crucial requirement due to its critical role in system software engineering. Conventional low-level programming languages such as C and assembly are efficient, but their inherent unsafe nature makes it undesirable for security-critical scenarios. Recently, Rust has become a promising alternative for safe system-level programming. While giving programmers fine-grained hardware control, its strong type system enforces many security properties including memory safety. However, Rust's security guarantee is not a silver bullet. Runtime crashes and memory-safety errors still harass Rust developers, causing damaging exploitable vulnerabilities, as reported by numerous studies.

Federated Learning (FL) is a new distributed machine learning (ML) approach which enables thousands of mobile devices to collaboratively train artificial intelligence (AI) models using local data without compromising user privacy. Although FL represents a promising computing paradigm, such training process can not be fully realized without an appropriate economic mechanism that incentivizes the participation of heterogeneous clients. This work targets social cost minimization, and studies the incentive mechanism design in FL through a procurement auction. Different from existing literature, we consider a practical scenario of FL where clients are selected and scheduled at different global iterations to guarantee the completion of the FL job, and capture the distinct feature of FL that the number of global iterations is determined by the local accuracy of all participants to balance between computation and communication. Our auction framework$A_{FL}$first decomposes the social cost minimization problem into a series of winner determination problems (WDPs) based on the number of global iterations. Then to solve each WDP,$A_{FL}$invokes a greedy algorithm to determine the winners, and a payment algorithm for computing remuneration to winners. Finally,$A_{FL}$returns the best solution among all WDPs. Theoretical analysis proves that$A_{FL}$is truthful, individual rational, computationally efficient, and achieves a near-optimal social cost. We further conduct large-scale simulation studies based on the real-world data. Simulation results show that$A_{FL}$can reduce the social cost by up to 75% compared with state-of-the-art algorithms.

Graphs are commonly used in various applications such as online social networks (OSNs), E-commerce systems and social recommender systems. Random walk sampling is often used to conduct statistical estimation over such graphs. This paper develops an algorithmic framework to reduce the mean square error of such statistical estimation. Our algorithmic framework is inspired by that the mean square error can be decomposed into a sum of the bias and variance of the estimator. More specifically, we apply the bootstrapping technique to design a bias reduction algorithm. A new feature of this bias reduction algorithm is that it allows the variance to increase whenever the bias can be further reduced. The increased variance may lead to a large mean square error of the estimator. We use multiple parallel random walks to reduce this variance such that it can be reduced to arbitrarily small by deploying a sufficient number of random walks. Our algorithmic framework enables one to attain different trade-offs between the sample complexity (i.e., number of parallel random walks) and the mean square error of the statistical estimation. Also, the proposed bias reduction algorithm is generic and can be applied to optimize a large class of random walk sampling algorithms. To demonstrate the versatility of the framework, we apply it to optimize the Metropolis random walk and simple random walk sampling. Extensive experiments confirm the effectiveness and efficiency of our proposed algorithmic framework.

Contextual bandit serves as an invaluable tool to balance the exploration vs. exploitation trade-off in various applications like online recommendation. In many applications, heterogeneous information network (HIN) can be derived to provide rich side information for contextual bandits, such as different types of attributes and relationships among users and items. In this paper, we propose the first HIN-assisted contextual bandit framework, which utilizes a given HIN to assist contextual bandit learning. The proposed framework uses meta-paths in HIN to extract rich relations among users and items for the contextual bandit. The main challenge is how to leverage these relations, since users' preference over items, the target of our online learning, are closely related to users' preference over meta-paths, however it is unknown which meta-path a user prefers more. We propose the HUCB algorithm to address such a challenge. For each meta-path, the HUCB algorithm employs an independent base bandit algorithm to handle online item recommendation by leveraging the relationship captured in this meta-path. The bandit master is then employed to learn users' preference over meta-paths to dynamically combine base bandit algorithms with a balance of exploration-exploitation trade-off. Experimental results on real datasets from LastFM and Yelp demonstrate the efficacy of the HUCB algorithm.

Online social network (OSN) is an ideal venue to enhance one's visibility. This paper considers how a user (called requester) in an OSN selects a small number of available users and invites them as new friends/followers so as to maximize his "social visibility". More importantly, the requester has to do this under the anonymity setting, which means he is not allowed to know the neighborhood information of these available users in the OSN. In this paper, we first develop a mathematical model to quantify the social visibility and formulate the problem of visibility maximization with anonymity guarantee, abbreviated as "VisMAX-A". Then we design an algorithmic framework named as "AdaExp", which adaptively expands the requester's visibility in multiple rounds. In each round of the expansion, AdaExp uses a query oracle with anonymity guarantee to select only one available user. By using probabilistic data structures like the k-minimum values (KMV) sketch, we design an efficient query oracle with anonymity guarantees. We also conduct experiments on real-world social networks and validate the effectiveness of our algorithms.

Multi-layered network exploration (MuLaNE) problem is an important problem abstracted from many applications. In MuLaNE, there are multiple network layers where each node has an importance weight and each layer is explored by a random walk. The MuLaNE task is to allocate total random walk budget $B$ into each network layer so that the total weights of the unique nodes visited by random walks are maximized. We systematically study this problem from offline optimization to online learning. For the offline optimization setting where the network structure and node weights are known, we provide greedy based constant-ratio approximation algorithms for overlapping networks, and greedy or dynamic-programming based optimal solutions for non-overlapping networks. For the online learning setting, neither the network structure nor the node weights are known initially. We adapt the combinatorial multi-armed bandit framework and design algorithms to learn random walk related parameters and node weights while optimizing the budget allocation in multiple rounds, and prove that they achieve logarithmic regret bounds. Finally, we conduct experiments on a real-world social network dataset to validate our theoretical results.

Mobile edge computing (MEC) facilitates computation offloading to edge server, as well as task processing via device-to-device (D2D) collaboration. Existing works mainly focus on centralized network-assisted offloading solutions, which are unscalable to scenarios involving collaboration among massive users. In this paper, we propose a joint framework of decentralized D2D collaboration and efficient task offloading for a large-population MEC system. Specifically, we utilize the power of two choices for D2D collaboration, which enables users to beneficially assist each other in a decentralized manner. Due to short-range D2D communication and user movements, we formulate a mean field model on a finite-degree and dynamic graph to analyze the state evolution of D2D collaboration. We derive the existence, uniqueness and convergence of the state stationary point so as to provide a tractable collaboration performance. Complementing this D2D collaboration, we further build a Stackelberg game to model users’ task offloading, where edge server is the leader to determine a service price, while users are followers to make offloading decisions. By embedding the Stackelberg game into Lyapunov optimization, we develop an online offloading and pricing scheme, which could optimize server’s service utility and users’ system cost simultaneously. Extensive evaluations show that our D2D collaboration can mitigate users’ workloads by 73.8% and task offloading can achieve high energy efficiency.

The scheduling policy installed on switches of datacenters plays a significant role on congestion control. Shortest-Remaining-Processing-Time (SRPT) achieves the near-optimal average message completion time (MCT) in various scenarios, but is difficult to deploy as viewed by the industry. The reasons are two-fold: 1) many commodity switches only provide FIFO queues, and 2) the information of remaining message size is not available. Recently, the idea of emulating SRPT using only a few FIFO queues and the original message size has been coined as the approximate and deployable SRPT (ADS) design. In this paper, we provide the first theoretical study on ADS design. Specifically, we first characterize a wide range of feasible ADS scheduling policies via a unified framework, and then derive the steady-state MCT and slowdown in the M/G/1 setting. We formulate the optimal ADS design as a non-linear combinatorial optimization problem, which aims to minimize the average MCT given the available FIFO queues. To prevent the starvation of long messages, we also take into account the fairness condition based on the steady-state slowdown. The optimal ADS design problem is NP-hard in general, and does not exhibit monotonicity or sub-modularity. We leverage its decomposable structure and devise an efficient algorithm to solve the optimal ADS policy. Numerical results based on the realistic heavy-tail message size distribution show that the optimal ADS policy installed on eight FIFO queues is capable of emulating the true SRPT in terms of MCT and slowdown.

The performance of an edge computing system primarily depends on the edge server provision mode, the task migration scheme, and the computing resource configuration. This paper studies how to perform dynamic resource configuration for hybrid edge server provision under two decentralized task migration schemes. We formulate the dynamic resource configuration as a multi-period online cost minimization problem, aiming to jointly minimize the performance degradation (i.e., execution latency) and the operation expenditure. Due to the stochastic nature, one can only observe the system performance for the currently installed configuration, which is also known as the partial feedback. To overcome this challenge, we derive a deterministic mean field model to approximate the large-scale stochastic edge computing system. We then propose an online mean field aided resource configuration policy, and show that the proposed policy performs asymptotically as good as the offline optimal configuration. Numerical results show that the mean field model can significantly improve the convergence speed in the online resource configuration problem. Moreover, our proposed policy under the two decentralized task migration schemes considerably reduces the operating cost (by 23%) and incurs little communication overhead.

This paper studies a cooperative multi-armed bandit problem with $M$ agents cooperating together to solve the same instance of a $K$-armed stochastic bandit problem with the goal of maximizing the cumulative reward of agents. The agents are heterogeneous in (i) their limited access to a local subset of arms; and (ii) their decision-making rounds, i.e., agents are asynchronous with different decision-making gaps. The goal is to find the global optimal arm and agents are able to pull any arm, however, they observe the reward only when the selected arm is local.The challenge is a tradeoff for agents between pulling a local arm with the possibility of observing the feedback, or relying on the observations of other agents that might occur at different rates. Naive extensions of traditional algorithms lead to an arbitrarily poor regret as a function of aggregate action frequency of any $\textit{suboptimal}$ arm located in slow agents. We resolve this issue by proposing a novel two-stage learning algorithm, called $\texttt{CO-LCB}$ algorithm, whose regret is a function of aggregate action frequency of agents containing the $\textit{optimal}$ arm. We also show that the regret of $\texttt{CO-LCB}$ matches the regret lower bound up to a small factor.

A fundamental question for companies with large amount of logged data is: How to use such logged data together with incoming streaming data to make good decisions? Many companies currently make decisions via online A/B tests, but wrong decisions during testing hurt users’ experiences and cause irreversible damage. A typical alternative is offline causal inference, which analyzes logged data alone to make decisions. However, these decisions are not adaptive to the new incoming data, and so a wrong decision will continuously hurt users’ experiences. To overcome the aforementioned limitations, we propose a framework to unify offline causal inference algorithms (e.g., weighting, matching) and online learning algorithms (e.g., UCB, LinUCB). We propose novel algorithms and derive bounds on the decision accuracy via the notion of “regret”. We derive the first upper regret bound for forest-based online bandit algorithms. Experiments on two real datasets show that our algorithms outperform other algorithms that use only logged data or online feedbacks, or algorithms that do not use the data properly.

Mobile edge computing becomes a promising technology to mitigate the latency of various cloud services. In addition, network function virtualization (NFV) has been shown a great potential in reducing the operational cost of cloud services while enhancing the flexibility of virtual network function deployments, by implementing dedicated hardware network functions as pieces of software in generic servers. Recently, the GPU acceleration has been investigated to speed up flow processing in virtual network functions (VNFs), by leveraging the parallelism of GPUs. VNFs that need accelerations prefer to stay at cloudlets (locations) equipped with GPUs. However, little attention has been paid for the VNF placement that takes into account GPU-affinity in cloudlets of mobile edge clouds. In this paper, we consider the affinity-aware throughput maximization problem in a mobile edge cloud via leveraging the parallelism on GPUs for user requests with VNF requirements. We consider two types of affinities in the VNF placement: Thesoft-affinitythat allows VNFs to be executed by either CPUs or GPUs in cloudlets; and thehard-affinitythat only allows VNFs to be placed to the GPUs of a specified set of cloudlets. We formulate two corresponding VNF placement problems in a mobile edge cloud. Specifically, we first propose an exact solution to the soft-affinity throughput maximization problem by formulating an Integer Linear Program (ILP). We then propose an efficient algorithm for the problem, by proposing a randomized algorithm with a provable approximation ratio for the hard-affinity-aware throughput maximization problem and extending the proposed approximation algorithm to the soft-affinity throughput maximization problem. Furthermore, assuming that user requests arrive into the mobile edge cloud one by one without the knowledge of future arrivals, we devise an online algorithm with a good competitive ratio for this dynamic hard-affinity-aware throughput maximization problem. Finally, we evaluate the performance of the proposed algorithms, through simulations and implementations in a real test-bed. Experimental results show that the performance of the proposed algorithms outperform their existing counterparts and achieve higher throughput.

Cache optimization, i.e., determining the optimal content placement and routing paths, is essential for obtaining high performance of cache-enabled networks. This paper studies the problem of optimizing system throughput and content delivery cost over cache networks with lossy links (i.e., ICN-based wireless IoT systems), where content is divided into packet-level chunks, and packets may be lost in transmission. We first propose a new performance metric - the expected overall content routing cost for satisfied requests (RCS), for better characterizing content delivery cost under packet losses. RCS at the same time possesses the attractive mathematical property of super-modularity. We then formulate an optimization problem for the task through jointly optimizing content caching and request routing, and analyze it under fixed-routing scenario. The formulated problem is NP-hard and we prove it is reducible to the one of minimizing content routing cost without packet losses. We establish rules for the reduction, and leverage existing efficient algorithm to solve the problem. We also propose a potential-based online algorithm that is simple and adaptive to traffic changes and packet losses. The effectiveness of our mechanism is validated through extensive simulations over a wide array of network topologies.

Finding the set of most influential users in online social networks (OSNs) to trigger the largest influence cascade is meaningful, e.g., companies may leverage the “word-of-mouth” effect to trigger a large cascade of purchases by offering free samples/discounts to those most influential users. This task is usually modeled as an influence maximization problem, and it has been widely studied in the past decade. However, considering that users in OSNs may participate in various online activities, e.g., joining discussion groups and commenting on same pages or products, influence diffusion through online activities becomes even more significant. In this article, we study the impact of online activities by formulating social-activity networks which contain both users and online activities, and thus induce two types of weighted edges, i.e., edges between users and edges between users and activities. To address the computation challenge, we define an influence centrality via random walks, and use the Monte Carlo framework to efficiently estimate the centrality. Furthermore, we develop a greedy-based algorithm with novel optimizations to find the most influential users for node recommendation. Experiments on real-world datasets show that our approach is very computationally efficient under different influence models, and also achieves larger influence spread by considering online activities.

Online product rating systems have become an indispensable component for numerous web services such as Amazon, eBay, Google Play Store, and TripAdvisor. One functionality of such systems is to uncover the product quality via product ratings (or reviews) contributed by consumers. However, a well-known psychological phenomenon called “ message-based persuasion ” lead to “ biased ” product ratings in a cascading manner (we call this the persuasion cascade ). This article investigates: (1) How does the persuasion cascade influence the product quality estimation accuracy? (2) Given a real-world product rating dataset, how to infer the persuasion cascade and analyze it to draw practical insights? We first develop a mathematical model to capture key factors of a persuasion cascade. We formulate a high-order Markov chain to characterize the opinion dynamics of a persuasion cascade and prove the convergence of opinions. We further bound the product quality estimation error for a class of rating aggregation rules including the averaging scoring rule, via the matrix perturbation theory and the Chernoff bound. We also design a maximum likelihood algorithm to infer parameters of the persuasion cascade. We conduct experiments on both synthetic data and real-world data from Amazon and TripAdvisor. Experiment results show that our inference algorithm has a high accuracy. Furthermore, persuasion cascades notably exist, but the average scoring rule has a small product quality estimation error under practical scenarios.

Estimating set similarity and detecting highly similar sets are fundamental problems in areas such as databases and machine learning. MinHash is a well-known technique for approximating Jaccard similarity of sets and has been successfully used for many applications. Its two compressed versions, b-bit MinHash and Odd Sketch, can significantly reduce the memory usage of the MinHash, especially for estimating high similarities (i.e., similarities around 1). Although MinHash can be applied to static sets as well as streaming sets, of which elements are given in a streaming fashion, unfortunately, b-bit MinHash and Odd Sketch fail to deal with streaming data. To solve this problem, we previously designed a memory-efficient sketch method, MaxLogHash, to accurately estimate Jaccard similarities in streaming sets. Compared with MinHash, our method uses smaller sized registers (each register consists of less than 7 bits) to build a compact sketch for each set. In this paper, we further develop a faster method, MaxLogOPH++. Compared with MaxLogHash, MaxLogOPH++ reduces the time complexity for updating each coming element from O(k) with a small additional memory. We conduct experiments on a variety of datasets, and experimental results demonstrate the efficiency and effectiveness of our methods.

For NFV systems, the key design space includes the function chaining for network requests and the resource scheduling for servers. The problem is challenging since NFV systems usually require multiple (often conflicting) design objectives and the computational efficiency of real-time decision making with limited information. Furthermore, the benefits of predictive scheduling to NFV systems still remain unexplored. In this article, we propose POSCARS, an efficient predictive and online service chaining and resource scheduling scheme that achieves tunable trade-offs among various system metrics with stability guarantee. Through a careful choice of granularity in system modeling, we acquire a better understanding of the trade-offs in our design space. By a non-trivial transformation, we decouple the complex optimization problem into a series of online sub-problems to achieve the optimality with only limited information. By employing randomized load balancing techniques, we propose three variants of POSCARS to reduce the overheads of decision making. Theoretical analysis and simulations show that POSCARS and its variants require only mild-value of future information to achieve near-optimal system cost with an ultra-low request response time.

Mobile edge computing (MEC) is emerging as an enabling technology of low-latency network services, such as Augmented Reality (AR) and Virtual Reality (VR), by deploying cloudlets in locations close to users. In MEC networks, telcooperators can place their services to cloudlets, such that the service accessing delay of users is minimized. In this paper, we investigate a fundamental problem of caching services that are originally deployed in remote clouds to cloudlets in an MEC network within the proximity of users. Specifically, we focus on the service caching problem in a two-tiered MEC network with both remote clouds and cloudlets that are close to users, in which multiple network service providers competing computing and bandwidth resources. This setting is significantly different from existing studies that focused on offloading user tasks from mobile devices to cloudlets in MEC networks that typically do not consider a service market with multiple network service providers. For the service caching problem in a two-tiered MEC network, we propose a novel approximation-restricted framework that guarantees the stableness of the service market. Under the proposed framework, an approximation algorithm with an approximation ratio for the problem with non-selfish players and an efficient, stable Stackelberg congestion game with selfish players have been proposed. We also analyze the Price of Anarchy (PoA) of the proposed Stackelberg congestion game to measure the efficiency of the proposed game degrades due to selfish behavior of network service providers. We finally evaluate the performance of our mechanism on both simulated environments and a real test-bed. Results show that the performance of our proposed mechanism is promising.

Mining from a big graph those subgraphs that satisfy certain conditions is useful in many applications such as community detection and subgraph matching. These problems have a high time complexity, but existing systems to scale them are all IO-bound in execution. We propose the first truly CPU-bound distributed framework called G-thinker that adopts a user-friendly subgraph-centric vertex-pulling API for writing distributed subgraph mining algorithms. To utilize all CPU cores of a cluster, G-thinker features (1) a highly-concurrent vertex cache for parallel task access and (2) a lightweight task scheduling approach that ensures high task throughput. These designs well overlap communication with computation to minimize the CPU idle time. Extensive experiments demonstrate that G-thinker achieves orders of magnitude speedup compared even with the fastest existing subgraph-centric system, and it scales well to much larger and denser real network data. G-thinker is open-sourced at http://bit.ly/gthinker with detailed documentation.

The sheer scale of big data causes the information overload issue and there is an urgent need for tools that can draw valuable insights from massive data. This paper investigates the core items tracking (CIT) problem where the goal is to continuously track representative items, called core items, in a data stream so to best represent/summarize the stream. In order to simultaneously satisfy the recency and continuity requirements, we consider CIT over probabilistic-decaying streams where items in the stream are forgotten gradually in a probabilistic manner. We first introduce an algorithm, called PNDCIT, to find core items in a special kind of probabilistic non-decaying streams. Furthermore, using PNDCIT as a building block, we design two novel algorithms, namely PDCIT and PDCIT+, to maintain core items over probabilistic-decaying streams with constant approximation ratios. Finally, extensive experiments on real data demonstrate that PDCIT+ achieves a speedup of up to one order of magnitude over a batch algorithm while providing solutions with comparable quality.

Small cells are deployed in 5G networks to complement the macro cells for improving coverage and capacity. Small cells and edge computing are natural partners which can improve users’ experience. Small cell nodes (SCNs) equipped with edge servers can support emerging computing services such as virtual reality which impose low-latency and precise contextual requirements. With the proliferation of wireless devices, there is an increasing demand for offloading tasks to SCNs. Given limited computation and communication resources, the fundamental problem for a small cell network is how to select computing tasks to maximize effective rewards in an uncertain and stochastic environment. To this end, we propose an online learning framework, LFSC, which has the performance guarantee to guide task offloading in a small cell network. LFSC balances between reward and constraint violations, and it consists of three subroutines: i) a randomized algorithm which calculates selection probability of each task based on task weights; ii) a greedy assignment algorithm which cooperatively allocates tasks among different SCNs based on the selection probability; iii) an update algorithm which exploits the multi-armed bandit (MAB) technique to update task weights according to the feedback. Our theoretical analysis shows that both the regret and violations metrics of LFSC have the sub-linear property. Extensive simulation studies based on real world data confirm that LFSC achieves a close-to-optimal reward with low violations, and outperforms many state-of-the-art algorithms.

Importance sampling (IS) is widely used in rare event simulation, but it is costly to deal with many rare events simultaneously. For example, a rare event can be the failure to provide the quality-of-service guarantee for a critical network flow. Since network providers often need to deal with many critical flows (i.e., rare events) simultaneously, if using IS, providers have to simulate each rare event with its customized importance distribution individually. To reduce such cost, we propose an efficient mixture importance distribution for multiple rare events, and formulate the mixture importance sampling optimization problem (MISOP) to select the optimal mixture. We first show that the "search direction" of mixture is computationally expensive to evaluate, making it challenging to locate the optimal mixture. We then formulate a " zero learning cost " online learning framework to estimate the "search direction", and learn the optimal mixture from simulation samples of events. We develop two multi-armed bandit online learning algorithms to: (1) Minimize the sum of estimation variances with a regret of (ln T)2/T; (2) Minimize the simulation cost with a regret of √ln T/T , where T denotes the number of simulation samples. We demonstrate our method on a realistic network and show that it can reduce the cost measures (i.e., sum of estimation variances and simulation cost) by as high as 61.6% compared with the uniform mixture IS.

With the popularization of Internet of Things (IoT) devices in smart home and industry fields, a huge number of IoT devices are connected to the Internet. However, what devices are connected to a network may not be known by the Internet Service Provider (ISP), since many IoT devices are placed within small networks (e.g., home networks) and are hidden behind network address translation (NAT). Without pinpointing IoT devices in a network, it is unlikely for the ISP to appropriately configure security policies and effectively manage the network. In this paper, we design an efficient and scalable system via spatial-temporal traffic fingerprinting. Our system can accurately identify typical IoT devices in a network, with the additional capability of identifying what devices are hidden behind NAT and how many they are. Through extensive evaluation, we demonstrate that the system can generally identify IoT devices with an F-Score above 0.999, and estimate the number of the same type of IoT device behind NAT with an average error below 5%. We also perform small-scale (labor-intensive) experiments to show that our system is promising in detecting user-IoT interactions.

Remote Direct Memory Access (RDMA) suffers from unfairness issues and performance degradation when multiple applications share RDMA network resources. Hence, an efficient resource scheduling mechanism is urged to optimally allocates RDMA resources among applications. However, traditional Network Utility Maximization (NUM) based solutions are inadequate for RDMA due to three challenges: 1) The standard NUM-oriented algorithm cannot deal with coupling variables introduced by multiple dependent RDMA operations; 2) The stringent constraint of RDMA on-board resources complicates the standard NUM by bringing extra optimization dimensions; 3) Naively applying traditional algorithms for NUM suffers from scalability and convergence issues in solving a large-scale RDMA resource scheduling problem.

We study the online restless bandit problem, where the state of each arm evolves according to a Markov chain, and the reward of pulling an arm depends on both the pulled arm and the current state of the corresponding Markov chain. In this paper, we propose Restless-UCB, a learning policy that follows the explore-then-commit framework. In Restless-UCB, we present a novel method to construct offline instances, which only requires $O(N)$ time-complexity ($N$ is the number of arms) and is exponentially better than the complexity of existing learning policy. We also prove that Restless-UCB achieves a regret upper bound of $\tilde{O}((N+M^3)T^{2\over 3})$, where $M$ is the Markov chain state space size and $T$ is the time horizon. Compared to existing algorithms, our result eliminates the exponential factor (in $M,N$) in the regret upper bound, due to a novel exploitation of the sparsity in transitions in general restless bandit problems. As a result, our analysis technique can also be adopted to tighten the regret bounds of existing algorithms. Finally, we conduct experiments based on real-world dataset, to compare the Restless-UCB policy with state-of-the-art benchmarks. Our results show that Restless-UCB outperforms existing algorithms in regret, and significantly reduces the running time.

This paper studies adversarial bandits with corruptions. In the basic adversarial bandit setting, the reward of arms is predetermined by an adversary who is oblivious to the learner’s policy. In this paper, we consider an extended setting in which an attacker sits in-between the environment and the learner, and is endowed with a limited budget to corrupt the reward of the selected arm. We have two main results. First, we derive a lower bound on the regret of any bandit algorithm that is aware of the budget of the attacker. Also, for budget-agnostic algorithms, we characterize an impossibility result demonstrating that even when the attacker has a sublinear budget, i.e., a budget growing sublinearly with time horizon T, they fail to achieve a sublinear regret. Second, we propose ExpRb, a bandit algorithm that incorporates a biased estimator and a robustness parameter to deal with corruption. We characterize the regret of ExpRb as a function of the corruption budget and show that for the case of a known corruption budget, the regret of ExpRb is tight.

Contextual bandit algorithms provide principled online learning solutions to balance the exploitation-exploration trade-off in various applications such as recommender systems. However, the learning speed of the traditional contextual bandit algorithms is often slow due to the need for extensive exploration. This poses a critical issue in applications like recommender systems, since users may need to provide feedbacks on a lot of uninterested items. To accelerate the learning speed, we generalize contextual bandit to conversational contextual bandit. Conversational contextual bandit leverages not only behavioral feedbacks on arms (e.g., articles in news recommendation), but also occasional conversational feedbacks on key-terms from the user. Here, a key-term can relate to a subset of arms, for example, a category of articles in news recommendation. We then design the Conversational UCB algorithm (ConUCB) to address two challenges in conversational contextual bandit: (1) which key-terms to select to conduct conversation, (2) how to leverage conversational feedbacks to accelerate the speed of bandit learning. We theoretically prove that ConUCB can achieve a smaller regret upper bound than the traditional contextual bandit algorithm LinUCB, which implies a faster learning speed. Experiments on synthetic data, as well as real datasets from Yelp and Toutiao, demonstrate the efficacy of the ConUCB algorithm.

This Special Section aims at providing a platform for sharing the state-of-the-art research and development on end-edge-cloud orchestration and publishing original research and peer-reviewed articles targeted to all readers of IEEE Transactions on Industrial Informatics. The content of the special issue focus on several topics that are recently concerned in the community, including the architectures and implementations, communication and networking protocols, computation offloading strategies, advanced machine learning and data analytical methods, performance modeling and optimization, and other enabling technologies for end-edge-cloud orchestrated systems and its industrial applications.

“Unbiasedness,” which is an important property to ensure that users’ ratings indeed reflect their true evaluations of products, is vital both in shaping consumer purchase decisions and providing reliable recommendations in online rating systems. Recent experimental studies showed that distortions from historical ratings would ruin the unbiasedness of subsequent ratings. How to “discover” historical distortions in each single rating (or at the micro-level), and perform the “debiasing operations” are our main objective. Using 42M real customer ratings, we first show that users either “assimilate” or “contrast” to historical ratings under different scenarios, which can be further explained by a well-known psychological argument: the “Assimilate-Contrast” theory. This motivates us to propose the Historical Influence Aware Latent Factor Model (HIALF), the “first” model for real rating systems to capture and mitigate historical distortions in each single rating. HIALF allows us to study the influence patterns of historical ratings from a modelling perspective, which perfectly matches the assimilation and contrast effects observed in experiments. Moreover, HIALF achieves significant improvements in predicting subsequent ratings and characterizing relationships in ratings. It also contributes to better recommendations, wiser consumer purchase decisions, and deeper understanding of historical distortions in both honest rating and misbehaving rating settings.

Ethereum, a blockchain, supports its own cryptocurrency named Ether and smart contracts. Although more than 8M smart contracts have been deployed on Ethereum, little is known about the characteristics of its users, smart contracts, and the relationships among them. We conduct the first systematic study on Ethereum by leveraging graph analysis to characterize three major activities on Ethereum, namely money transfer, smart contract creation, and smart contract invocation. We collect all transaction data, construct three graphs from the data to characterize major activities via graph analysis, and discover new insights. Moreover, we address three security issues based on graphs.

Feedback-based reputation systems are widely deployed in E-commerce systems. Evidence shows that earning a reputable label (for sellers of such systems) may take a substantial amount of time, and this implies a reduction of profit. We propose to enhance sellers’ reputation via price discounts. However, the challenges are as follows: (1) The demands from buyers depend on both the discount and reputation, and (2) the demands are unknown to the seller. To address these challenges, we first formulate a profit maximization problem via a semi-Markov decision process to explore the optimal tradeoffs in selecting price discounts. We prove the monotonicity of the optimal profit and optimal discount. Based on the monotonicity, we design a Q-learning with forward projection (QLFP) algorithm, which infers the optimal discount from historical transaction data. We prove that the QLFP algorithm convergences to the optimal policy. We conduct trace-driven simulations using a dataset from eBay to evaluate the QLFP algorithm. Evaluation results show that QLFP improves the profit by as high as 50% over both Q-learning and Speedy Q-learning. The QLFP algorithm also improves both the reputation and profit by as high as two times over the scheme of not providing any price discount.

Emerging new applications demand the current Internet to provide new functionalities. Although many future Internet architectures and protocols have been proposed to fulfill such needs, ISPs have been reluctant to deploy many of these architectures. We believe technical issues are not the main reasons as many of these new proposals are technically sound. In this paper, we take an economic perspective and seek to answer: Why do most new Internet architectures fail to be deployed? How can the deployability of a new architecture be enhanced? We develop a game-theoretic model to characterize the outcome of an architecture's deployment through the equilibrium of ISPs' decisions. This model enables us to: (1) analyze several key factors of the deployability of a new architecture such as the number of critical ISPs and the change of routing path; (2) explain the deploying outcomes of some previously proposed architectures/protocols such as IPv6, DiffServ, CDN, etc., and shed light on the “Internet flattening phenomenon”; (3) predict the deployability of a new architecture such as NDN, and compare its deployability with competing architectures. Our study suggests that the difficulty to deploy a new Internet architecture comes from the “coordination” of distributed ISPs. Finally, we design a mechanism to enhance the deployability of new architectures.

Capacity planning and sales projection are essential tasks for network operators. This work aims to help network providers to carry out network capacity planning and sales projection by answering: Given topology and capacity, whether the network can serve current flow demands with high probabilities? We name such probability as the “flow availability”, and present the flow availability estimation (FAVE) problem with generalizing the classical network connectivity based and maximum flow based reliability estimations. To quickly estimate flow availabilities, we utilize correlations among link and flow failures to figure out the importance of roles played by different links in flow failures (i.e., flow demands could not be satisfied). And we design three sequential importance sampling (SIS) estimation methods, which are: (1) Accurate and efficient: They achieve a bounded or even vanishing relative error with linear computational complexities. Hence they can provide more accurate estimations in less simulation time. (2) Robust and scalable: They maintain such estimation efficiencies even if only a partial SEED set information is available, or when the FAVE problem is extended to the multiple flows case. When applying to a realistic backbone network, our method can reduce the flow availability estimation cost by 900 and 130 times compared with MC and baseline IS methods; and also facilitate capacity planning and sales projection by providing better flow availability guarantees, compared with traditional methods.

Online reputation systems serve as core building blocks in various Internet services such as E-commerce (e.g., eBay) and crowdsourcing (e.g., oDesk). The flaws and deficiencies of real-world online reputation systems have been reported extensively. Users who are frustrated about the system will eventually abandon such service. However, there is no systematic and formal studies which examine such deficiencies. This paper presents the first attempt, which develops a novel data analytical framework to uncover online reputation system deficiencies from data. We develop two novel measures to quantify the efficiency of online reputation systems: (1) ramp up time of a new service provider, (2) long term profit gains for a service provider. We present a new data analytical framework to evaluate these two measures from data. We show that inherent preferences or personal biases in expressing feedbacks (or ratings) cause the computational infeasibility in evaluating the ramp up time and the long term profit gains from data. We develop two computationally efficient randomized algorithms with theoretical performance guarantees to address this computational challenge. We apply our methodology to analyze real-life datasets (from eBay, Google Helpouts, Amazon and TripAdvisor). We extensively validate our model and we uncover the deficiencies of online reputation systems. Our experimental results uncovers insights on why Google Helpouts was eventually shut down in April 2015 and why eBay is losing some sellers heavily.

Device drivers on Linux-powered embedded or IoT systems execute in kernel space thus must be fully trusted. Any fault in drivers may significantly impact the whole system. However, third-party embedded hardware manufacturers usually ship their proprietary device drivers with their embedded devices. These out-of-tree device drivers are generally of poor quality because of a lack of code audit. In this paper, we propose a new approach that helps third-party developers to improve the reliability and safety of device drivers without modifying the kernel: Rewriting device drivers in a memory-safe programming language called Rust. Rust's rigorous language model assists the device driver developers to detect many security issues at compile time. We designed a framework to help developers to quickly build device drivers in Rust. We also utilized Rust's security features to provide several useful infrastructures for developers so that they can easily handle kernel memory allocation and concurrency management, at the same time, some common bugs (e.g. use-after-free) can be alleviated. We demonstrate the generality of our framework by implementing a real-world device driver on Raspberry Pi 3, and our evaluation shows that device drivers generated by our framework have acceptable binary size for canonical embedded systems and the runtime overhead is negligible.

Online product rating systems have become an indispensable component for numerous web services such as Amazon, eBay, Google play store and TripAdvisor. One functionality of such systems is to uncover the product quality via product ratings (or reviews) contributed by consumers. However, a well-known psychological phenomenon called “messagebased persuasion” lead to “biased” product ratings in a cascading manner (we call this the persuasion cascade). This paper investigates: (1) How does the persuasion cascade influence the product quality estimation accuracy? (2) Given a real-world product rating dataset, how to infer the persuasion cascade and analyze it to draw practical insights? We first develop a mathematical model to capture key factors of a persuasion cascade. We formulate a high-order Markov chain to characterize the opinion dynamics of a persuasion cascade and prove the convergence of opinions. We further bound the product quality estimation error for a class of rating aggregation rules including the averaging scoring rule, via the matrix perturbation theory and the Chernoff bound. We also design a maximum likelihood algorithm to infer parameters of the persuasion cascade. We conduct experiments on the data from Amazon and TripAdvisor, and show that persuasion cascades notably exist, but the average scoring rule has a small product quality estimation error under practical scenarios.

Feedback-based reputation systems are widely deployed in E-commerce systems. Evidences showed that earning a reputable label (for sellers of such systems) may take a substantial amount of time and this implies a reduction of profit. We propose to enhance sellers’ reputation via price discounts. However, the challenges are: (1) The demands from buyers depend on both the discount and reputation; (2) The demands are unknown to the seller. To address these challenges, we first formulate a profit maximization problem via a semiMarkov decision process (SMDP) to explore the optimal trade-offs in selecting price discounts. We prove the monotonicity of the optimal profit and optimal discount. Based on the monotonicity, we design a QLFP (Q-learning with forward projection) algorithm, which infers the optimal discount from historical transaction data. We conduct experiments on a dataset from to show that our QLFP algorithm improves the profit by as high as 50% over both the classical Q-learning and speedy Q-learning algorithm. Our QLFP algorithm also improves the profit by as high as four times over the case of not providing any price discount.

Cardinality constrained submodular function maximization, which aims to select a subset of size at most k to maximize a monotone submodular utility function, is the key in many data mining and machine learning applications such as data summarization and maximum coverage problems. When data is given as a stream, streaming submodular optimization (SSO) techniques are desired. Existing SSO techniques can only apply to insertion-only streams where each element has an infinite lifespan, and sliding-window streams where each element has a same lifespan (i.e., window size). However, elements in some data streams may have arbitrary different lifespans, and this requires addressing SSO over streams with inhomogeneous-decays (SSO-ID). This work formulates the SSO-ID problem and presents three algorithms: BASIC-STREAMING is a basic streaming algorithm that achieves an (1/2 − ɛ) approximation factor; HISTAPPROX improves the efficiency significantly and achieves an (1/3 − ɛ) approximation factor; HISTSTREAMING is a streaming version of HISTAPPROX and uses heuristics to further improve the efficiency. Experiments conducted on real data demonstrate that HISTSTREAMING can find high quality solutions and is up to two orders of magnitude faster than the naive GREEDY algorithm.

In clouds and data centers, GPU servers which consist of multiple GPUs are widely deployed. Current state-of-the-art GPU scheduling algorithm are "static" in assigning applications to different GPUs. These algorithms usually ignore the dynamics of the GPU utilization and are often inaccurate in estimating resource demand before assigning/running applications, so there is a large opportunity to further load balance and to improve GPU utilization. Based on CUDA (Compute Unified Device Architecture), we develop a runtime system called DCUDA which supports "dynamic" scheduling of running applications between multiple GPUs. In particular, DCUDA provides a realtime and lightweight method to accurately monitor the resource demand of applications and GPU utilization. Furthermore, it provides a universal migration facility to migrate "running applications" between GPUs with negligible overhead. More importantly, DCUDA transparently supports all CUDA applications without changing their source codes. Experiments with our prototype system show that DCUDA can reduce 78.3% of overloaded time of GPUs on average. As a result, for different workloads consisting of a wide range applications we studied, DCUDA can reduce the average execution time of applications by up to 42.1%. Furthermore, DCUDA also reduces 13.3% energy in the light load scenario.

Docker containers are widely deployed to provide lightweight virtualization, and they have many desirable features such as ease of deployment and near bare-metal performance. However, both the performance and cache efficiency of containers are still limited by their storage drivers due to the coarse-grained copy-on-write operations, and the large amount of redundancy in both I/O requests and page cache. To improve I/O performance and cache efficiency of containers, we develop HP-Mapper, a high performance storage driver for Docker containers. HP-Mapper provides a two-level mapping strategy to support fine-grained copy-on-write with low overhead, and an efficient interception method to reduce redundant I/Os. Furthermore, it uses a novel cache management mechanism to reduce duplicate cached data. Experiment results with our prototype system show that HP-Mapper significantly reduces copy-on-write latency due to its finer-grained copy-on-write scheme. Moreover, HP-Mapper can also reduce 65.4% cache usage on average due to elimination of duplicated data. As a result, HP-Mapper improves the throughput of real-world workloads by up to 39.4%, and improves the startup speed of containers by 2.0x.

Random walk is widely applied to sample large-scale graphs due to its simplicity of implementation and solid theoretical foundations of bias analysis. However, its computational efficiency is heavily limited by the slow convergence rate (a.k.a. long burn-in period). To address this issue, we propose a common neighbor aware random walk framework called CNARW, which leverages weighted walking by differentiating the next-hop candidate nodes to speed up the convergence. Specifically, CNARW takes into consideration the common neighbors between previously visited nodes and next-hop candidate nodes in each walking step. Based on CNARW, we further develop two efficient "unbiased sampling" schemes. Experimental results on real-world network datasets show that our approach converges remarkably faster than the state-of-the-art random walk sampling algorithms. Furthermore, to achieve the same estimation accuracy, our approach reduces the query cost (a measure of sampling budget) significantly. Lastly, we also use two case studies to demonstrate the effectiveness of our sampling framework in solving large-scale graph analysis tasks.

Identifying influential nodes that can jointly trigger the maximum influence spread in networks is a fundamental problem in many applications such as viral marketing, online advertising, and disease control. Most existing studies assume that social influence is static and they fail to capture the dynamics of influence in reality. In this work, we address the dynamic influence challenge by designing efficient streaming methods that can identify influential nodes from highly dynamic node interaction streams. We first propose a general time-decaying dynamic interaction network (TDN) model to model node interaction streams with the ability to smoothly discard outdated data. Based on the TDN model, we design three algorithms, i.e., SieveADN, BasicReduction and HistApprox. SieveADN identifies influential nodes from a special kind of TDNs with efficiency. BasicReduction uses SieveADN as a basic building block to identify influential nodes from general TDNs. HistApprox significantly improves the efficiency of BasicReduction. More importantly, we theoretically show that all three algorithms enjoy constant factor approximation guarantees. Experiments conducted on various real interaction datasets demonstrate that our approach finds near-optimal solutions with speed at least 5 to 15 times faster than baseline methods.

Firms are now considering to offer rewards to customers who recommend the firms' products/services in online social networks (OSN). However, the pros and cons of such social recommendation scheme are still unclear. Thus, it is difficult for firms to design rewarding schemes. Via empirical analysis of data, we first identify key factors that affect the spreading of a firm's product in OSNs. These findings enable us to develop an accurate (i.e., with a high validation accuracy) mathematical model on social recommendations. In particular, our model captures how users decide whether to recommend an item, which is a key factor but often ignored by previous social recommendation models such as the "Independent Cascade model". We also design algorithms to infer model parameters. Using these parameters in our model, we uncover conditions when social recommendation can (or cannot) improves a firm's profit. These conditions help a firm to design rewarding schemes. Finally, we extend our model to an online setting and design reinforcement learning algorithms for a firm to dynamically optimize its rewarding schemes.

This paper focuses on helping network providers to carry out network capacity planning and sales projection by answering the question: For a given topology and capacity, whether the network can serve current flow demands with high probabilities? We name such probability as “ flow availability” and present the -flow availability estimation (FAVE) problem, which is a generalisation of network connectivity or maximum flow reliability estimations. Realistic networks are often large and dynamic, so flow availabilities cannot be evaluated analytically and simulation is often used. However, naive Monte Carlo (MC) or importance sampling (IS) techniques take an excessive amount of time. To quickly estimate flow availabilities, we utilize the correlations among link and flow failures to figure out the importance of roles played by different links in flow failures, and design three “sequential importance sampling” (SIS) methods which achieve “bounded or even vanishing relative error” with linear computational complexities. When applying to a realistic network, our method reduces the flow availability estimation cost by 900 and 130 times compared with MC and baseline IS methods, respectively. Our method can also facilitate capacity planning by providing better flow availability guarantees, compared with traditional methods.

Estimating set similarity and detecting highly similar sets are fundamental problems in areas such as databases, machine learning, and information retrieval. MinHash is a well-known technique for approximating Jaccard similarity of sets and has been successfully used for many applications such as similarity search and large scale learning. Its two compressed versions, b-bit MinHash and Odd Sketch, can significantly reduce the memory usage of the original MinHash method, especially for estimating high similarities (i.e., similarities around 1). Although MinHash can be applied to static sets as well as streaming sets, of which elements are given in a streaming fashion and cardinality is unknown or even infinite, unfortunately, b-bit MinHash and Odd Sketch fail to deal with streaming data. To solve this problem, we design a memory efficient sketch method, MaxLogHash, to accurately estimate Jaccard similarities in streaming sets. Compared to MinHash, our method uses smaller sized registers (each register consists of less than 7 bits) to build a compact sketch for each set. We also provide a simple yet accurate estimator for inferring Jaccard similarity from MaxLogHash sketches. In addition, we derive formulas for bounding the estimation error and determine the smallest necessary memory usage (i.e., the number of registers used for a MaxLogHash sketch) for the desired accuracy. We conduct experiments on a variety of datasets, and experimental results show that our method MaxLogHash is about 5 times more memory efficient than MinHash with the same accuracy and computational cost for estimating high similarities.

Many computationally expensive problems are solved by a divide-and-conquer algorithm: a problem over a big dataset can be recursively divided into independent tasks over smaller subsets of the dataset. We present a distributed general-purpose framework called T-thinker which effectively utilizes the CPU cores in a cluster by properly decomposing an expensive problem into smaller independent tasks for parallel computation. T-thinker well overlaps CPU processing with network communication, and its superior performance is verified over a re-engineered graph mining system G-thinker available at http://cs.uab.edu/yanda/gthinker/.

Recently exploring locally connected subgraphs (also known as motifs or graphlets) of complex networks attracts a lot of attention. Previous work made the strong assumption that the graph topology of interest is known in advance. In practice, sometimes researchers have to deal with the situation where the graph topology is unknown because it is expensive to collect and store all topological information. Hence, typically what is available to researchers is only a snapshot of the graph, i.e., a subgraph of the graph. Crawling methods such as breadth first sampling can be used to generate the snapshot. However, these methods fail to sample a streaming graph represented as a high speed stream of edges. Therefore, graph mining applications such as network traffic monitoring usually use random edge sampling (i.e., sample each edge with a fixed probability) to collect edges and generate a sampled graph, which we call a “ RESampled graph”. Clearly, a RESampled graph's motif statistics may be quite different from those of the original graph. To resolve this, we propose a framework Minfer, which takes the given RESampled graph and accurately infers the underlying graph's motif statistics. Experiments using large scale datasets show the accuracy and efficiency of our method.

Various differentiated pricing schemes have been proposed for the Internet market. Aiming at replacing the traditional single-class pricing for better welfare, yet, researchers have shown that existing schemes can bring only marginal profit gain for the ISPs. In this article, we point out that a proper form of differentiated pricing for the Internet should not only consider congestion, but more importantly, it should provide application specific treatment to data delivery. Formally, we propose an “application-driven pricing” approach, where an ISP offers a number of service classes in terms of a guaranteed quality of service and announces a unit usage price for each class, and content providers are free to choose which class to use depending on the requirement of their applications. Unlike previous studies, we point out that the revenue gain of multi-class pricing under our scheme can be significant. This is because we capture important aspects of application heterogeneity and take the quality of service and price as control knobs. We identify key factors that impact the revenue gain and reveal fundamental understandings on when and why an application-driven multi-class pricing can significantly increase the revenue of ISPs.

In recent years, we have witnessed a growing trend for online service companies to offer “bundling sales” to increase revenue. Bundling sale means that a company groups a set of products/services and charges this bundle at a fixed price, which is usually less than the total price of individual items in the bundle. In this work, our aim is to understand the underlying dynamics of bundling, particularly what is the optimal bundling sale strategy and under what situations it will be more attractive than the separate sales. We focus on online service markets that exhibit network effects . We formulate mathematical models to capture the interactions between buyers and sellers, analyze the market equilibrium and its stability, and provide an optimization framework to determine the optimal sale strategy for a service provider. We analyze the impact of various factors on the profitability of bundling, including the network effects, operating costs, and variance and correlation of customers’ valuations toward these services. We show that bundling is more profitable when the variance of customers’ valuations and the operational cost of the services are small. In addition, a positive network effect and a negative correlation among customers’ valuation on services increase the profitability of bundling, whereas the heterogeneity of services and the asymmetry of operating costs reduce its advantage.

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

Despite recent efforts in counting 3-node and 4-node graphlets, little attention has been paid to characterizing 5-node graphlets. In this paper, we develop a computationally efficient sampling method to estimate 5-node graphlet counts. We not only provide a fast sampling method and unbiased estimators of graphlet counts, but also derive simple yet exact formulas for the variances of the estimators which are of great value in practice-the variances can be used to bound the estimates' errors and determine the smallest necessary sampling budget for a desired accuracy. We conduct experiments on a variety of real-world datasets, and the results show that our method is several orders of magnitude faster than the state-of-the-art methods with the same accuracy.

Emerging new applications demand the current Internet to provide new functionalities. Although many future Internet architectures and protocols have been proposed to fulfill such needs, ISPs have been reluctant to deploy these architectures. We believe technical issues are not the main reasons as many of these new proposals are technically sound. In this paper, we take an economic perspective and seek to answer: Why most new Internet architectures failed to be deployed? What makes a new architecture easier to deploy? We develop a game-theoretic model to characterize the outcome of an architecture's deployment through the equilibrium of ISP's decisions. We also use our model to explain the deploying outcomes of IPv6, DiffServ, CDN, etc., and the "Internet flattening phenomenon". Furthermore, one can use our model to predict the deployability of new architectures such as NDN, XIA, and compare the deployability of competing architectures. Our study also suggests that the architectures which try to make a fresh start may have a low deployability, unless they have efficient incremental deployment mechanisms or one introduces a centralized coordinator to help the deployment.

Detecting fake accounts (sybils) in online social networks (OSNs) is vital to protect OSN operators and their users from various malicious activities. Typical graph-based sybil detection (a mainstream methodology) assumes that sybils can make friends with only a limited (or small) number of honest users. However, recent evidences showed that this assumption does not hold in real-world OSNs, leading to low detection accuracy. To address this challenge, we explore users' activities to assist sybil detection. The intuition is that honest users are much more selective in choosing who to interact with than to befriend with. We first develop the social and activity network (SAN), a two-layer hyper-graph that unifies users' friendships and their activities, to fully utilize users' activities. We also propose a more practical sybil attack model, where sybils can launch both friendship attacks and activity attacks. We then design Sybil SAN to detect sybils via coupling three random walk-based algorithms on the SAN, and prove the convergence of Sybil SAN. We develop an efficient iterative algorithm to compute the detection metric for Sybil SAN, and derive the number of rounds needed to guarantee the convergence. We use "matrix perturbation theory" to bound the detection error when sybils launch many friendship attacks and activity attacks. Extensive experiments on both synthetic and real-world datasets show that Sybil SAN is highly robust against sybil attacks, and can detect sybils accurately under practical scenarios, where current state-of-art sybil defenses have low accuracy.

The web link selection problem is to select a small subset of web links from a large web link pool, and to place the selected links on a web page that can only accommodate a limited number of links, e.g., advertisements, recommendations, or news feeds. Despite the long concerned click-through rate which reflects the attractiveness of the link itself, revenue can only be obtained from user actions after clicks, e.g., purchasing after being directed to the product pages by recommendation links. Thus, web links have an intrinsic multi-level feedback structure. With this observation, we consider the context-free web link selection problem, where the objective is to maximize revenue while ensuring that the attractiveness is no less than a preset threshold. The key challenge of the problem is that each link's multi-level feedbacks are stochastic, and unobservable unless the link is selected. We model this problem with a constrained stochastic multi-armed bandit formulation, and design an efficient link selection algorithm, called Constrained Upper Confidence Bound algorithm (Con-UCB). We prove O(sqrt(T ln(T))) bounds on both regret and violation of the attractiveness constraint. We also conduct extensive experiments on three real-world datasets, and show that Con-UCB outperforms state-of-the-art context-free bandit algorithms concerning the multi-level feedback structure.

The unbiasedness of online product ratings, an important property to ensure that users’ ratings indeed reflect their true evaluations to products, is vital both in shaping consumer purchase decisions and providing reliable recommendations. Recent experimental studies showed that distortions from historical ratings would ruin the unbiasedness of subsequent ratings. How to “discover” the distortions from historical ratings in each single rating (or at the micro-level), and perform the “debiasing operations” in real rating systems are the main objectives of this work. Using 42 million real customer ratings, we first show that users either “assimilate” or “contrast” to historical ratings under different scenarios: users conform to historical ratings if historical ratings are not far from the product quality (assimilation), while users deviate from historical ratings if historical ratings are significantly different from the product quality (contrast). This phenomenon can be explained by the well-known psychological argument: the “Assimilate-Contrast” theory. However, none of the existing works on modeling historical ratings’ influence have taken this into account, and this motivates us to propose the Histori- cal Influence Aware Latent Factor Model (HIALF), the first model for real rating systems to capture and mitigate historical distortions in each single rating. HIALF also allows us to study the influence patterns of historical ratings from a modeling perspective, and it perfectly matches the assimilation and contrast effects we previously observed. Also, HIALF achieves significant improvements in predicting subsequent ratings, and accurately predicts the relationships revealed in previous empirical measurements on real ratings. Finally, we show that HIALF can contribute to better recommendations by decoupling users’ real preference from distorted ratings, and reveal the intrinsic product quality for wiser consumer purchase decisions.

Network application optimization is essential for improving the performance of the application as well as its user experience. The network application parameters are crucial in making proper decisions for network application optimizations. However, many works are impractical by assuming a priori knowledge of the parameters which are usually unknown and need to be estimated. There have been studies that consider optimizing network application in an online learning context using multi-armed bandit models. However, existing frameworks are problematic as they only consider to find the optimal decisions to minimize the regret, but neglect the constraints (or guarantee) requirements which may be excessively violated. In this paper, we propose a novel online learning framework for network application optimizations with guarantee. To the best of our knowledge, we are the first to formulate the stochastic constrained multi-armed bandit model with time-varying “multi-level rewards” by taking both “regret” and “violation” into consideration. We are also the first to design a constrained bandit policy, Learning with Minimum Guarantee (LMG), with provable sub-linear regret and violation bounds. We illustrate how our framework can be applied to several emerging network application optimizations, namely, (1) opportunistic multichannel selection, (2) data-guaranteed crowdsensing, and (3) stability-guaranteed crowdsourced transcoding. To show the effectiveness of LMG in optimizing these applications with different minimum requirements, we also conduct extensive simulations by comparing LMG with existing state-of-the-art policies.

A switching/forwarding fabric with high-bandwidth one-to-one and low-bandwidth many-to-many data forwarding can be achieved by combing electronic packet switches (EPS) and optical circuit switches (OCS). This hybrid solution scales well but it is not suitable for cloud computing/datacenter applications, which typically rely on one-to-many and many-to-one communications. Recently, composite-path switching (cp-switching), which adds paths between EPS and ocs is introduced to deal with this skewed traffic pattern. The state-of-the-art scheduling algorithm for CP-switches reduces, by heuristics, a CP-switching problem with one composite path to a hybrid switching problem without the composite path, and leverages existing scheduling techniques to tackle the latter problem. Unfortunately, the approach provides neither performance guarantee nor the support for multiple composite paths. In this paper, we systematically study the shortest time CP-switch scheduling problem with multiple composite paths and show that the problem can be expressed as an optimization problem with sparsity constraints. An LP-based algorithm is derived accordingly which supports multiple composite paths and more importantly, it provides performance guarantee. Simulations demonstrate that adding more composite paths can help shorten the schedule, and our approach outperforms existing methods by 30% to 70%.

Network function virtualization (NFV) can significantly reduce the operation cost and speed up the deployment for network services to markets. Under NFV, a network service is composed by a chain of ordered virtual functions, or we call a "network function chain." A fundamental question is when given a number of network function chains, on which servers should we place these functions and how should we form a chain on these functions? This is challenging due to the intricate dependency relationship of functions and the intrinsic complex nature of the optimization. In this paper, we formulate the function placement and chaining problem as an integer optimization, where each variable is an indicator whether one service chain can be deployed on a configuration (or a possible function placement of a service chain). While this problem is generally NP-hard, our contribution is to show that it can be mapped to an exponential number of min-cost flow problems. Instead of solving all the min-cost problems, one can select a small number of mapped min-cost problems, which are likely to have a low cost. To achieve this, we relax the integer problem into a fractional linear problem, and theoretically prove that the fractional solutions possess some desirable properties, i.e., the number and the utilization of selected configurations can be upper and lower bounded, respectively. Based on such properties, we determine some "good" configurations selected from the fractional solution and determine the mapped min-cost flow problem, and this helps us to develop efficient algorithms for network function placement and chaining. Via extensive simulations, we show that our algorithms significantly outperform state-of-art algorithms and achieve near-optimal performance.

We introduce the community exploration problem that has various real-world applications such as online advertising. In the problem, an explorer allocates limited budget to explore communities so as to maximize the number of members he could meet. We provide a systematic study of the community exploration problem, from offline optimization to online learning. For the offline setting where the sizes of communities are known, we prove that the greedy methods for both of non-adaptive exploration and adaptive exploration are optimal. For the online setting where the sizes of communities are not known and need to be learned from the multi-round explorations, we propose an ``upper confidence'' like algorithm that achieves the logarithmic regret bounds. By combining the feedback from different rounds, we can achieve a constant regret bound.

Recently, there is a growing emphasis on device-to-device (D2D) communication, which is the key component of the Internet-of-Things ecosystem. D2D communication can operate on the licensed spectrum of cellular networks so as to improve the spectrum utilization. In this paper, we focus on the resource allocation problem for general multihop D2D communication and introduce users' mobility into D2D communication underlaying cellular networks. Maximizing the total end-to-end data rate involves complex tasks, such as resource allocation and routing. By leveraging on the square tessellation technique, we propose an efficient square-division-based resource allocation scheme. Furthermore, we design a relay-assisted D2D communication protocol that addresses the challenges in enabling multihop D2D communications, namely, spectrum resource allocation, users' mobility, and relay incentive. Through extensive simulations, we show that our relay-assisted D2D communication protocol improves the system throughput up to 55% and the user access rate up to four times in typical scenarios, as compared with state-of-the-art schemes.

Typical analysis of content caching algorithms using the metric of steady state hit probability under a stationary request process does not account for performance loss under a variable request arrival process. In this paper, we instead conceptualize caching algorithms as complexity-limited online distribution learning algorithms and use this vantage point to study their adaptability from two perspectives: 1) the accuracy of learning a fixed popularity distribution and 2) the speed of learning items' popularity. In order to attain this goal, we compute the distance between the stationary distributions of several popular algorithms with that of a genie-aided algorithm that has the knowledge of the true popularity ranking, which we use as a measure of learning accuracy. We then characterize the mixing time of each algorithm, i.e., the time needed to attain the stationary distribution, which we use as a measure of learning efficiency. We merge both the above-mentioned measures to obtain the “learning error” representing both how quickly and how accurately an algorithm learns the optimal caching distribution and use this to determine the trade-off between these two objectives of many popular caching algorithms. Informed by the results of our analysis, we propose a novel hybrid algorithm, adaptive-least recently used, that learns both faster and better the changes in the popularity. We show numerically that it also outperforms all other candidate algorithms when confronted with either a dynamically changing synthetic request process or using real world traces.

The majority of influence maximization (IM) studies focus on targeting influential seeders to trigger substantial information spread in social networks. Motivated by the observation that incentives could “boost” users so that they are more likely to be influenced by friends, we consider a new and complementary k-boosting problem which aims at finding k users to boost so as to trigger a maximized “boosted” influence spread. The k-boosting problem is different from the IM problem, because boosted users behave differently from seeders. Boosted users are initially uninfluenced, and we only increase their probability to be influenced. This paper also complements the IM studies, because we focus on triggering a larger influence spread on the basis of given seeders. Both the NP-hardness of the problem and the nonsubmodularity of the objective function pose challenges to the k-boosting problem. To tackle the problem on general graphs, we devise two efficient algorithms with the data-dependent approximation ratio. To tackle the problem on bidirected trees, we present an efficient greedy algorithm and a dynamic programming that is a fully polynomial-time approximation scheme. Experiments using real social networks and synthetic bidirected trees verify the efficiency and effectiveness of the proposed algorithms. In particular, on general graphs, boosting solutions returned by our algorithms achieves boosts of influence that are up to several times higher than those achieved by boosting intuitive solutions with no approximation guarantee. We also explore the “budget allocation” problem experimentally, demonstrating the benefits of allocating the budget to both seeders and boosted users.

Counting subgraphs is a fundamental analysis task for online social networks (OSNs). Given the sheer size and restricted access of OSN, efficient computation of subgraph counts is highly challenging. Although a number of algorithms have been proposed to estimate the relative counts of subgraphs in OSNs with restricted access, there are only few works which try to solve a more general problem, i.e., counting subgraph frequencies. In this article, we propose an efficient random walk-based framework to estimate the subgraph counts. Our framework generates samples by leveraging consecutive steps of the random walk as well as by observing neighbors of visited nodes. Using the importance sampling technique, we derive unbiased estimators of the subgraph counts. To make better use of the degree information of visited nodes, we also design improved estimators, which increases the accuracy of the estimation with no additional cost. We conduct extensive experimental evaluation on real-world OSNs to confirm our theoretical claims. The experiment results show that our estimators are unbiased, accurate, efficient, and better than the state-of-the-art algorithms. For the Weibo graph with more than 58 million nodes, our method produces estimate of triangle count with an error less than 5% using only 20,000 sampled nodes. Detailed comparison with the state-of-the-art methods demonstrates that our algorithm is 2--10 times more accurate.

Reputation systems have become an indispensable component of modern E-commerce systems, as they help buyers make informed decisions in choosing trustworthy sellers. To attract buyers and increase the transaction volume, sellers need to earn reasonably high reputation scores. This process usually takes a substantial amount of time. To accelerate this process, sellers can provide price discounts to attract users, but the underlying difficulty is that sellers have no prior knowledge on buyers’ preferences over price discounts. In this article, we develop an online algorithm to infer the optimal discount rate from data. We first formulate an optimization framework to select the optimal discount rate given buyers’ discount preferences, which is a tradeoff between the short-term profit and the ramp-up time (for reputation). We then derive the closed-form optimal discount rate, which gives us key insights in applying a stochastic bandits framework to infer the optimal discount rate from the transaction data with regret upper bounds. We show that the computational complexity of evaluating the performance metrics is infeasibly high, and therefore, we develop efficient randomized algorithms with guaranteed performance to approximate them. Finally, we conduct experiments on a dataset crawled from eBay. Experimental results show that our framework can trade 60% of the short-term profit for reducing the ramp-up time by 40%. This reduction in the ramp-up time can increase the long-term profit of a seller by at least 20%.

Counting 3-, 4-, and 5-node graphlets in graphs is important for graph mining applications such as discovering abnormal/ evolution patterns in social and biology networks. In addition, it is recently widely used for computing similarities between graphs and graph classification applications such as protein function prediction and malware detection. However, it is challenging to compute these graphlet counts for a large graph or a large set of graphs due to the combinatorial nature of the problem. Despite recent efforts in counting 3-node and 4-node graphlets, little attention has been paid to characterizing 5-node graphlets. In this paper, we develop a computationally efficient sampling method to estimate 5-node graphlet counts. We not only provide a fast sampling method and unbiased estimators of graphlet counts, but also derive simple yet exact formulas for the variances of the estimators which are of great value in practice-the variances can be used to bound the estimates' errors and determine the smallest necessary sampling budget for a desired accuracy. We conduct experiments on a variety of real-world datasets, and the results show that our method is several orders of magnitude faster than the state-of-the-art methods with the same accuracy.

Mining the characteristics of information spreading in networks is crucial in communication studies, network security management, epidemic investigations, etc. Previous works are restrictive because they mainly focused on the information source detection using either a single observation, or multiple but independent observations of the underlying network while assuming a homogeneous information spreading rate. We conduct a theoretical and experimental study on information spreading, and propose a new and novel estimation framework to estimate 1) information spreading rates, 2) start time of the information source, and 3) the location of information source by utilizing multiple sequential and dependent snapshots where information can spread at heterogeneous rates. Our framework generalizes the current state-of-the-art rumor centrality [1] and the union rumor centrality [2]. Furthermore, we allow heterogeneous information spreading rates at different branches of a network. Our framework provides conditional maximum likelihood estimators for the above three metrics and is more accurate than rumor centrality and Jordan center in both synthetic networks and real-world networks. Applying our framework to the Twitter's retweet networks, we can accurately determine who made the initial tweet and at what time the tweet was sent. Furthermore, we also validate that the rates of information spreading are indeed heterogeneous among different parts of a retweet network.

Indoor localization plays an important role as the basis for a variety of mobile applications, such as navigating, tracking, and monitoring in indoor environments. However, many such systems cause potential privacy leakage in data transmission between mobile users and the localization server (LS). Unfortunately, there has been little research done on privacy issue, and the existing privacy-preserving solutions are algorithm-driven, each designed for specific localization algorithms, which hinders their wide-scale adoption. Furthermore, they mainly focus on users' location privacy, while the LS's data privacy cannot be guaranteed. In this paper, we propose a Privacy-Preserving Paradigm-driven framework for indoor LOCalization (P3-LOC). P3-LOC takes the advantage that most indoor localization systems share a common two-stage localization paradigm: information measurement and location estimation. Based on this, P3-LOC carefully perturbs and cloaks the transmitted data in these two stages and employs specially designed “k -anonymity” and “differential privacy” techniques to achieve the provable privacy preservation. The key advantage is that P3-LOC does not rely on any prior knowledge of the underlying localization algorithms, and it guarantees both users' location privacy and the LS's data privacy. Our extensive experiments from the measured data have validated that P3-LOC provides privacy preservation for general indoor localization techniques. In addition, P3-LOC is comparable with the state-of-the-art algorithm-driven techniques in terms of localization error, computation, and communication overhead.

Macrotasking crowdsourcing systems like Elance and Fiverr serve as efficient platforms for requesters to outsource challenging and innovative tasks that require special skills to workers. It is widely practiced in such systems that requesters reward workers based on requesters' assessment on solution quality. The challenge is that requesters' assessment may not be accurate to reflect the intrinsic quality of a solution due to human factors like personal preferences or biases. In this work, we consider answering the following questions: How to design a mechanism to incentivize workers provide high quality solutions in the presence of such human factors? How to formally study the impact of human factors on workers' financial incentive to participate? We design a mechanism to incentivize workers to provide high-quality contributions, which is robust to human factors. Our incentive mechanism consists of a “task bundling scheme” and a “rating system”, which reward workers based on requesters' rating on the solution quality. We propose a probabilistic model to capture human factors, and quantify their impact on the incentive mechanism. We formulate an optimization framework to select appropriate rating system parameters, which can be viewed as a tradeoff between “system efficiency”, i.e., the total number of tasks can be solved given a fixed reward budget, and the “rating system complexity”, which determines the human cognitive cost and time in expressing ratings. We also formulate an optimization framework to select appropriate bundling size, which can tradeoff system efficiency against service delay (i.e., the waiting time to form a task bundle). Finally, we conduct experiments on a dataset from Elance. Experimental results show that our incentive mechanism achieves at least 99.95 percent of the theoretical maximum system efficiency with a service delay of at most 2.3639 hours. Furthermore, we discover that the rating system in Elance is too complex, and it should be simplified to a binary rating system (i.e., two rating points).

Counting small connected subgraph patterns called graphlets is emerging as a powerful tool for exploring topological structure of networks and for analysis of roles of individual nodes. Graphlets have numerous applications ranging from biology to network science. Computing graphlet counts for "dynamic graphs" is highly challenging due to the streaming nature of the input, sheer size of the graphs, and superlinear time complexity of the problem. Few practical results are known under the massive streaming graphs setting. In this work, we propose a "unified framework" to estimate the graphlet counts of the whole graph as well as the graphlet counts of individual nodes under the streaming graph setting. Our framework subsumes previous methods and provides more flexible and accurate estimation of the graphlet counts. We propose a general unbiased estimator which can be applied to any k-node graphlets. Furthermore, efficient implementation is provided for the 3, 4-node graphlets. We perform detailed empirical study on real-world graphs, and show that our framework produces estimation of graphlet count for streaming graphs with 1.7 to 170.8 times smaller error compared with other state-of-the-art methods. Our framework also achieves high accuracy on the estimation of graphlets for each individual node which previous works could not achieve.

The current inter-domain routing protocol, namely, the Border Gateway Protocol (BGP), cannot provide end-to-end (E2E) quality-of-service (QoS) guarantees. The main reason is that an autonomous system (AS) can only receive guarantees from its first hop ASes via service level agreements (SLAs). But beyond the first hop, QoS along the path from source to destination AS is not within the source AS's control regime. In this paper, we investigate the feasibility of providing high QoS-guaranteed E2E transit services by utilizing a (small) set of ASes/IXPs to serve as "brokers" to provide supervision, control and resource negotiation. Finding an optimal set of ASes as brokers can be formulated as a Maximum Coverage with B-dominating path Guarantee (MCBG) problem, which we prove to be NP-hard. To address this problem, we design a (1-e-1/4)-approximation algorithm and also an efficient heuristic algorithm when considering additional constraints (e.g., path length). Based on the current Internet topology, we discover a "3540-alliance" subset (accounting only 6.8%) of 52,079 ASes/IXPs, which can provide high QoS guarantees for 99.29% E2E connections.

Compared with executing Network Functions (NFs) on dedicated hardwares, the recent trend of Network Function Virtualization (NFV) holds the promise for operators to flexibly deploy software-based NFs on commodity servers. However, virtual NFs (VNFs) are normally "chained" together to provide a specific network service. Thus, an efficient scheme is needed to place the VNF chains across the network and effectively schedule requests to service instances, which can maximize the average resource utilization of each node in service and simultaneously minimize the average response latency of each request. To this end, we formulate first VNF chains placement problem as a variant of bin-packing problem, which is NP-hard, and we model request scheduling problem based on the key concepts from open Jackson network. To jointly optimize the performance of NFV, we propose a priority-driven weighted algorithm to improve resource utilization and a heuristic algorithm to reduce response latency. Through extensive trace-driven simulations, we show that our methods can indeed enhance performance in diverse scenarios. In particular, we can improve the average resource utilization by 33.4% and can reduce the average total latency by 19.9% as compared with the state-of-the-art methods.

The majority of influence maximization (IM) studies focus on targeting influential seeders to trigger substantial information spread in social networks. In this paper, we consider a new and complementary problem of how to further increase the influence spread of given seeders. Our study is motivated by the observation that direct incentives could "boost" users so that they are more likely to be influenced by friends. We study the k-boosting problem which aims to find k users to boost so that the final "boosted" influence spread is maximized. The k-boosting problem is different from the IM problem because boosted users behave differently from seeders: boosted users are initially uninfluenced and we only increase their probability to be influenced. Our work also complements the IM studies because we focus on triggering larger influence spread on the basis of given seeders. Both the NP-hardness of the problem and the non-submodularity of the objective function pose challenges to the k-boosting problem. To tackle the problem, we devise two efficient algorithms with the data-dependent approximation ratio. We conduct extensive experiments using real social networks demonstrating the efficiency and effectiveness of our proposed algorithms. We show that boosting solutions returned by our algorithms achieves boosts of influence that are up to several times higher than those achieved by boosting solutions returned by intuitive baselines, which have no guarantee of solution quality. We also explore the "budget allocation" problem in our experiments. Compared with targeting seeders with all budget, larger influence spread is achieved when we allocation the budget to both seeders and boosted users. This also shows that our study complements the IM studies.

Selecting the right web links for a website is important because appropriate links not only can provide high attractiveness but can also increase the website's revenue. In this work, we first show that web links have an intrinsic multi-level feedback structure. For example, consider a 2-level feedback web link: the 1st level feedback provides the Click-Through Rate (CTR) and the 2nd level feedback provides the potential revenue, which collectively produce the compound 2-level revenue. We consider the context-free links selection problem of selecting links for a homepage so as to maximize the total compound 2-level revenue while keeping the total 1st level feedback above a preset threshold. We further generalize the problem to links with n (n ≥ 2)-level feedback structure. The key challenge is that the links' multi-level feedback structures are unobservable unless the links are selected on the homepage. To our best knowledge, we are the first to model the links selection problem as a constrained multi-armed bandit problem and design an effective links selection algorithm by learning the links' multi-level structure with provable sub-linear regret and violation bounds. We uncover the multi-level feedback structures of web links in two real-world datasets. We also conduct extensive experiments on the datasets to compare our proposed LExp algorithm with two state-of-the-art context-free bandit algorithms and demonstrate that LExp algorithm is the most effective in links selection while satisfying the constraint.

Product bundling is widely adopted for information goods and online services because it can increase profit for companies. For example, cable companies often bundle Internet access and video streaming services together. However, it is challenging to obtain an optimal bundling strategy, not only because it is computationally expensive, but also that customers’ private information (e.g., valuations for products) is needed for the decision, and we need to infer it from accessible datasets. As customers’ purchasing data are getting richer due to the popularity of online shopping, doors are open for us to infer this information. This paper aims to address: (1) How to infer customers’ valuations from the purchasing data? (2) How to determine the optimal product bundle to maximize the profit? We first formulate a profit maximization framework to select the optimal bundle set. We show that finding the optimal bundle set is NPhard. We then identify key factors that impact the profitability of product bundling. These findings give us insights to develop a computationally efficient algorithm to approximate the optimal product bundle with a provable performance guarantee. To obtain the input of the bundling algorithm, we infer the distribution of customers’ valuations from their purchasing data, based on which we run our bundling algorithm and conduct experiments on an Amazon co-purchasing dataset. We extensively evaluate the accuracy of our inference and the bundling algorithm. Our results reveal conditions under which bundling is highly profitable and provide insights to guide the deployment of product bundling.

The unbiasedness of online product ratings, an important property to ensure that users' ratings indeed reflect their true evaluations to products, is vital both in shaping consumer purchase decisions and providing reliable recommendations. Recent experimental studies showed that distortions from historical ratings would ruin the unbiasedness of subsequent ratings. How to "discover" the distortions from historical ratings in each single rating (or at the micro-level), and perform the "debiasing operations" in real rating systems are the main objectives of this work.

Redundant array of independent disk (RAID) offers a good option to provide device-level fault tolerance for solid-state drives (SSDs). However, parity update with either read-modify-write or read-reconstruct-write may introduce a lot of extra I/Os and thus significantly degrades SSD RAID performance. To reduce the parity update cost, elastic striping chooses to reconstruct new stripes with only the newly updated data chunks instead of directly updating parity chunks. However, it necessitates an RAID-level garbage collection (GC) process, which may incur a very high cost due to the mixture of hot and cold data chunks. To address this problem, we follow the idea of elastic striping and propose a workload-aware scheme (WAS) to reduce the RAID-level GC cost so as to improve the performance and endurance of SSD RAID. In particular, we first develop a novel lightweight hot data identification scheme which requires only a very small computation time and memory cost, then propose a hotness-aware elastic striping approach to separately write data chunks with different hotness to different regions in SSD RAID. To evaluate the effectiveness and efficiency of our WAS, we implement a prototype system on RAID-5 and RAID-6 arrays composed of commercial SSDs. Experimental results show that compared to original elastic striping, our scheme reduces 30.0%-70.6% (and 23.9%-63.2%) of chunk writes under the RAID-5 (and RAID-6) settings, and also reduces the average response time by 60.9%-79.3% (and 56.8%-80.9%) for RAID-5 (and RAID-6), respectively. Besides, our scheme also improves the endurance and reliability of SSD RAID compared to original elastic striping.

Android, the most popular mobile OS, has around 78% of the mobile market share. Due to its popularity, it attracts many malware attacks. In fact, people have discovered around 1 million new malware samples per quarter, and it was reported that over 98% of these new malware samples are in fact “derivatives” (or variants) from existing malware families. In this paper, we first show that runtime behaviors of malware's core functionalities are in fact similar within a malware family. Hence, we propose a framework to combine “runtime behavior” with “static structures” to detect malware variants. We present the design and implementation of Monet, which has a client and a backend server module. The client module is a lightweight, in-device app for behavior monitoring and signature generation, and we realize this using two novel interception techniques. The backend server is responsible for large scale malware detection. We collect 3723 malware samples and top 500 benign apps to carry out extensive experiments of detecting malware variants and defending against malware transformation. Our experiments show that Monet can achieve around 99% accuracy in detecting malware variants. Furthermore, it can defend against ten different obfuscation and transformation techniques, while only incurs around 7% performance overhead and about 3% battery overhead. More importantly, Monet will automatically alert users with intrusion details so to prevent further malicious behaviors.

Datacenter networks suffer unpredictable performance due to a lack of application level bandwidth guarantees. A lot of attention has been drawn to solve this problem such as how to provide bandwidth guarantees for virtualized machines (VMs), proportional bandwidth share among tenants, and high network utilization under peak traffic. However, existing solutions fail to cope with highly dynamic traffic in datacenter networks. In this paper, we propose eBA, an efficient solution to bandwidth allocation that provides end-to-end bandwidth guarantee for VMs under large numbers of short flows and massive bursty traffic in datacenters. eBA leverages a novel distributed VM-to-VM rate control algorithm based on the logistic model under the control-theoretic framework. eBA's implementation requires no changes to hardware or applications and can be deployed in standard protocol stack. The theoretical analysis and the experimental results show that eBA not only guarantees the bandwidth for VMs, but also provides fast convergence to efficiency and fairness, as well as smooth response to bursty traffic.

Mobile operating systems like Android failed to provide sufficient protection on personal data, and privacy leakage becomes a major concern. To understand the security risks and privacy leakage, analysts have to carry out data-flow analysis. In 2014, Android upgraded with a fundamentally new design known as Android RunTime (ART) environment in Android 5.0. ART adopts ahead-of-time compilation strategy and replaces previous virtual-machine-based Dalvik. Unfortunately, many data-flow analysis systems like TaintDroid were designed for the legacy Dalvik environment. This makes data-flow analysis of new apps and malware infeasible. We design a multi-level information-flow tracking system for the new Android system called TaintART. TaintART employs a multi-level taint analysis technique to minimize the taint tag storage. Therefore, taint tags can be stored in processor registers to provide efficient taint propagation operations. We also customize the ART compiler to maximize performance gains of the ahead-of-time compilation optimizations. Based on the general design of TaintART, we also implement a multi-level privacy enforcement to prevent sensitive data leakage. We demonstrate that TaintART only incurs less than 15% overheads on a CPU-bound microbenchmark and negligible overhead on built-in or third-party applications. Compared to legacy Dalvik environment in Android 4.4, TaintART achieves about 99.7% faster performance for Java runtime benchmark.

Most methods for Personalized PageRank (PPR) precompute and store all accurate PPR vectors, and at query time, return the ones of interest directly. However, the storage and computation of all accurate PPR vectors can be prohibitive for large graphs, especially in caching them in memory for real-time online querying. In this paper, we propose a distributed framework that strikes a better balance between offline indexing and online querying. The offline indexing attains a fingerprint of the PPR vector of each vertex by performing billions of ``short'' random walks in parallel across a cluster of machines. We prove that our indexing method has an exponential convergence, achieving the same precision with previous methods using a much smaller number of random walks. At query time, the new PPR vector is composed by a linear combination of related fingerprints, in a highly efficient vertex-centric decomposition manner. Interestingly, the resulting PPR vector is much more accurate than its offline counterpart because it actually uses more random walks in its estimation. More importantly, we show that such decomposition for a batch of queries can be very efficiently processed using a shared decomposition. Our implementation, PowerWalk, takes advantage of advanced distributed graph engines and it outperforms the state-of-the-art algorithms by orders of magnitude. Particularly, it responses to tens of thousands of queries on graphs with billions of edges in just a few seconds.

Characterizing motif (i.e., locally connected sub-graph patterns) statistics is important for understanding complex networks such as online social networks and communication networks. Previous work made the strong assumption that the graph topology of interest is known in advance. In practice, sometimes researchers have to deal with the situation where the graph topology is unknown because it is expensive to collect and store all topological and meta information. Hence, typically what is available to researchers is only a snapshot of the graph, i.e., a subgraph of the graph. Crawling methods such as breadth first sampling can be used to generate the snapshot. However, these methods fail to sample a streaming graph represented as a high speed stream of edges. Therefore, graph mining applications such as network traffic monitoring use random edge sampling (i.e., sample each edge with a fixed probability) to collect edges and generate a sampled graph, which we called a “RESampled graph”. Clearly, a RESampled graph's motif statistics may be quite different from those of the underlying original graph. To resolve this, we propose a framework and implement a system called Minfer, which takes the given RESampled graph and accurately infers the underlying graph's motif statistics. We also apply Fisher information to bound the errors of our estimates. Experiments using large scale datasets show the accuracy and efficiency of our method.

Counting subgraphs is a fundamental analysis task for online social networks (OSNs). Given the sheer size and restricted access of online social network data, efficient computation of subgraph counts is highly challenging. Although a number of algorithms have been proposed to estimate the relative counts of subgraphs in OSNs with restricted access, there are only few works which try to solve a more general problem, i.e., counting subgraph frequencies. In this paper, we propose an efficient random walk-based framework to estimate the subgraph counts. Our framework generates samples by leveraging consecutive steps of the random walk as well as by observing neighbors of visited nodes. Using the importance sampling technique, we derive unbiased estimators of the subgraph counts. To make better use of the degree information of visited nodes, we also design an improved estimator, which increases the efficiency of the estimate at no additional cost. We conduct extensive experimental evaluation on real-world OSNs to confirm our theoretical claims. The experiment results show that our estimators are unbiased, accurate, efficient and better than the state-of-the-art algorithm. For the Weibo graph with more than 58 million nodes, our method produces estimate of triangle count with an error less than 5% using only 20 thousands sampled nodes. Detailed comparison with the state-of-the-art method demonstrates that our algorithm is 4 to 5 times more accurate.

Many graphs in real-world applications, such as telecommunications networks, social-interaction graphs and co-authorship graphs, contain temporal information. However, existing graph mining algorithms fail to exploit these temporal information and the resulting subgraph patterns do not contain any temporal attribute. In this paper, we study the problem of mining a set of diversified temporal subgraph patterns from a temporal graph, where each subgraph is associated with the time interval that the pattern spans. This problem motivates important applications such as finding social trends in social networks, or detecting temporal hotspots in telecommunications networks. We propose a divide-and-conquer algorithm along with effective pruning techniques, and our approach runs 2 to 3 orders of magnitude faster than a baseline algorithm and obtains high-quality temporal subgraph patterns in real temporal graphs.

In recent years, there is an increasing demand of big memory systems so to perform large scale data analytics. Since DRAM memories are expensive, some researchers are suggesting to use other memory systems such as non-volatile memory (NVM) technology to build large-memory computing systems. However, whether the NVM technology can be a viable alternative (either economically and technically) to DRAM remains an open question. To answer this question, it is important to consider how to design a memory system from a "system perspective",that is, incorporating different performance characteristics andprice ratios from hybrid memory devices. This paper presents an analytical model of a "hybrid page cache system" so to understand the diverse design space and performance impact of a hybrid cache system. We consider (1) various architectural choices, (2) design strategies, and (3) configuration of different memory devices. Using this model, we provide guidelines on how to design hybrid page cache to reach a good trade-off between high system throughput (in I/O per sec or IOPS) and fast cache reactivity which is defined by the time to fill the cache. We also show how one can configure the DRAM capacity and NVM capacity under a fixed budget. We pick PCM as an example for NVM and conduct numerical analysis. Our analysis indicates that incorporating PCM in a page cache system significantly improves the system performance, and it also shows larger benefit to allocate more PCM in page cache in some cases. Besides, for the common setting of performance-price ratio of PCM, "flat architecture" offers as a better choice, but "layered architecture" outperforms if PCM write performance can be significantly improved in the future.

We develop an optimization framework to trade short-term profits for reputation (i.e., reducing ramp-up time). We apply the stochastic bandits framework to design an online discounting mechanism which infers the optimal discount from a seller's historical transaction data. We conduct experiments on an eBay's dataset and show that our online discounting mechanism can trade 60% of the shortterm profits for reducing the ramp-up time by 40%.

Graphlets are induced subgraph patterns and have been frequently applied to characterize the local topology structures of graphs across various domains, e.g., online social networks (OSNs) and biological networks. Discovering and computing graphlet statistics are highly challenging. First, the massive size of real-world graphs makes the exact computation of graphlets extremely expensive. Secondly, the graph topology may not be readily available so one has to resort to web crawling using the available application programming interfaces (APIs). In this work, we propose a general and novel framework to estimate graphlet statistics of " any size. " Our framework is based on collecting samples through consecutive steps of random walks. We derive an analytical bound on the sample size (via the Chernoff-Hoeffding technique) to guarantee the convergence of our unbiased estimator. To further improve the accuracy, we introduce two novel optimization techniques to reduce the lower bound on the sample size. Experimental evaluations demonstrate that our methods outperform the state-of-the-art method up to an order of magnitude both in terms of accuracy and time cost.

Pioneered by Google's Pregel, many distributed systems have been developed for large-scale graph analytics. These systems employ a user-friendly "think like a vertex" programming model, and exhibit good scalability for tasks where the majority of graph vertices participate in computation. However, the design of these systems can seriously under-utilize the resources in a cluster for processing light-workload graph queries, where only a small fraction of vertices need to be accessed. In this work, we develop a new open-source system, called Quegel , for querying big graphs. Quegel treats queries as first-class citizens in its design: users only need to specify the Pregel-like algorithm for a generic query, and Quegel processes light-workload graph queries on demand, using a novel superstep-sharing execution model to effectively utilize the cluster resources. Quegel further provides a convenient interface for constructing graph indexes, which significantly improve query performance but are not supported by existing graph-parallel systems. Our experiments verified that Quegel is highly efficient in answering various types of graph queries and is up to orders of magnitude faster than existing systems.

Solid-state drives (SSDs) have been widely deployed in desktops and data centers. However, SSDs suffer from bit errors, and the bit error rate is time dependent since it increases as an SSD wears down. Traditional storage systems mainly use parity-based RAID to provide reliability guarantees by striping redundancy across multiple devices, but the effectiveness of traditional RAID schemes in SSDs remains debatable. In particular, an open problem is how different parity distributions over multiple devices influence the reliability of an SSD RAID array. That is, should we evenly distribute patsaverties as suggested by conventional wisdom, or unevenly distribute parties as recently proposed for SSD RAID? To address this fundamental problem, we propose the first analytical model to quantify the reliability dynamics of an SSD RAID array as it ages. Specifically, we develop a “non-homogeneous” continuous time Markov chain model, and derive the transient reliability solution. We validate our model via trace-driven simulation and conduct numerical analysis to analyze the reliability dynamics of SSD RAID arrays subject to different parity distributions, error rates, and SSD array configurations. Our model enables system practitioners to decide the appropriate parity distribution based on their reliability requirements.

It is often crucial for manufacturers to decide what products to produce so that they can increase their market share in an increasingly fierce market. To decide which products to produce, manufacturers need to analyze the consumers’ requirements and how consumers make their purchase decisions so that the new products will be competitive in the market. In this paper, we first present a general distance-based product adoption model to capture consumers’ purchase behavior. Using this model, various distance metrics can be used to describe different real life purchase behavior. We then provide a learning algorithm to decide which set of distance metrics one should use when we are given some accessible historical purchase data. Based on the product adoption model, we formalize the k most marketable products (or k- MMP ) selection problem and formally prove that the problem is NP-hard . To tackle this problem, we propose an efficient greedy-based approximation algorithm with a provable solution guarantee. Using submodularity analysis, we prove that our approximation algorithm can achieve at least 63% of the optimal solution. We apply our algorithm on both synthetic datasets and real-world datasets (TripAdvisor.com), and show that our algorithm can easily achieve five or more orders of speedup over the exhaustive search and achieve about 96% of the optimal solution on average. Our experiments also demonstrate the robustness of our distance metric learning method, and illustrate how one can adopt it to improve the accuracy of product selection.

Recent studies show that disk-based graph computation systems on just a single PC can be as highly competitive as cluster-based systems on large-scale problems. Inspired by this remarkable progress, we develop VENUS, a disk-based graph computation system which is able to handle billion-scale graphs efficiently on a commodity PC. VENUS adopts a novel computing architecture that features vertex-centric “streamlined” processing-the graph is sequentially loaded and an update function is executed for each vertex in parallel on the fly. VENUS deliberately avoids loading batch edge data by separating read-only structure data from mutable vertex data on disk, and minimizes random IOs by caching vertex data in the main memory whenever possible. The streamlined processing is realized with efficient sequential scan over massive structure data and fast feeding the update function for a large number of vertices. Extensive evaluation on large real-world and synthetic graphs has demonstrated the efficiency of VENUS. For example, to run the PageRank algorithm on a Twitter graph of 42 million vertices and 1.4 billion edges, Spark needs 8.1 minutes with 50 machines and GraphChi spends 13 minutes using high-speed SSD, while VENUS only takes 5 minutes on one machine with an ordinary hard disk.

With wide application of virtualization technology, tenants are able to access isolated cloud services by renting the shared resources in Infrastructure-as-a-Service (IaaS) datacenters. Unlike resources such as CPU and memory, datacenter network, which relies on traditional transport-layer protocols, suffers unfairness due to a lack of virtual machine (VM)-level bandwidth guarantees. In this paper, we model the datacenter bandwidth allocation as a cooperative game, toward VM-based fairness across the datacenter with two main objectives: 1) guarantee bandwidth for VMs based on their base bandwidth requirements, and 2) share residual bandwidth in proportion to the weights of VMs. Through a bargaining game approach, we propose a bandwidth allocation algorithm, Falloc, to achieve the asymmetric Nash bargaining solution (NBS) in datacenter networks, which exactly meets our objectives. The cooperative structure of the algorithm is exploited to develop an online algorithm for practical real-world implementation. We validate Falloc with experiments under diverse scenarios and show that by adapting to different network requirements of VMs, Falloc can achieve fairness among VMs and balance the tradeoff between bandwidth guarantee and proportional bandwidth sharing. Our large-scale trace-driven simulations verify that Falloc achieves high utilization while maintaining fairness among VMs in datacenters.

In this paper, we propose a highly efficient scheme, SLICE (a scalable and low stretch routing scheme), enabling greedy routing for wireless sensor networks (WSNs) deployed in complex-connected 3-D settings, whose topologies are often theoretically modeled as high genus 3-D WSNs. Compared to previous 3-D greedy embedding techniques, SLICE improves both the robustness and applicability. 1) It achieves a smaller distance distortion and a lower routing stretch with guaranteed delivery. While it follows the basic idea to embed the surface network to a planar topology to enable greedy routing, the embedding method proposed in SLICE is novel. We first slice the surface network to a genus-0 open surface with exactly one boundary. Then, to achieve a lower distance distortion, we purposely propose a variation of the Ricci flow algorithm, by which this open surface is flattened not to a planar annulus, but to a planar convex polygon, resulting in a lower routing stretch. 2) This is the first work, to the best of our knowledge, that enables greedy routing in high genus 3-D WSNs with general topologies. SLICE not only works for high genus 3-D surface WSNs, but also can be easily adapted to more general cases: high genus 3-D surface networks with holes, and high genus 3-D volume networks. For a high genus 3-D surface network with holes, SLICE embeds it to a planar convex polygon with circular holes, where our proposed greedy routing variation can be applied. For a high genus 3-D volume network, SLICE embeds the inner nodes to a height structure attached to the convex polygon, and a variation of greedy routing scheme with guaranteed delivery is proposed in this structure. The effectiveness of SLICE is validated by extensive simulations.

In wireless sensor networks (WSNs), a space filling curve (SFC) refers to a path passing through all nodes in the network, with each node visited at least once. By enforcing a linear order of the sensor nodes through an SFC, many applications in WSNs concerning serial operations on both sensor nodes and sensor data can be performed, with examples including serial data fusion and path planning of mobile nodes. Although a few studies have made efforts to find such SFCs in WSNs, they primarily target 2D planar or 3D surface settings and cannot be directly applied to 3D volumetric WSNs due to considerably more complex geometric features and topology shapes that the 3D volumetric settings introduce. This article presents BLOW-UP, a distributed, scalable, and connectivity-based algorithm to construct an SFC for a 3D volumetric WSN (or alternatively to linearize the 3D volumetric network). The main idea of BLOW-UP is to decompose the given 3D volumetric network into a series of connected and closed layers, and the nodes are traversed layer by layer, incrementally from the innermost to the outermost, yielding an SFC covering the entire network, provably at least once and at most a constant number of times. To the best of our knowledge, BLOW-UP is the first algorithm that realizes linearization in 3D volumetric WSNs. It does not require advance knowledge of location or distance information. It is also scalable with a nearly constant per-node storage cost and message cost. Extensive simulations under various networks demonstrate its effectiveness on nodes’ covered times, coverage rate, and covering speed.

Point-to-point shortest distance queries are fundamental to large graph analytics. Motivated by the need for low-latency distance queries in large-scale "dynamic" graphs, we consider the problem of answering exact shortest distance queries on disk-resident scale-free dynamic graphs. Our query processing uses the canonical labeling method, which is a special 2-hop distance labeling for fast distance queries. In this paper, we propose two I/O efficient algorithms to update the canonical labeling. To the best of our knowledge, our proposed methods are the first practical disk-based methods to "incrementally update" the canonical labeling on dynamic graphs. We also show how to answer distance queries on the latest network based on outdated labels and new edges. Extensive experiments demonstrate the efficiency of our methods. Our update methods are an order of magnitude faster than reconstructing the canonical labeling. When the number of new edges is small, say less than 1% of the previous number of edges, our query algorithm based on outdated labels provides exact shortest distance and the query time is comparable to other query algorithms using latest labels.

Compared with Android, the conventional wisdom is that iOS is more secure. However, both jailbroken and non-jailbroken iOS devices have number of vulnerabilities. For iOS, apps need to interact with the underlying system using Application Programming Interfaces (APIs). Some of these APIs remain undocumented and Apple forbids apps in App Store from using them. These APIs, also known as "private APIs", provide powerful features to developers and yet they may have serious security consequences if misused. Furthermore, apps which use private APIs can bypass the App Store and use the "Apple's Enterprise/Developer Certificates" for distribution. This poses a significant threat to the iOS ecosystem. So far, there is no formal study to understand these apps and how private APIs are being encapsulated. We call these iOS apps which distribute to the public using enterprise certificates as "enpublic" apps. In this paper, we present the design and implementation of iAnalytics, which can automatically analyze "enpublic" apps' private API usages and vulnerabilities. Using iAnalytics, we crawled and analyzed 1,408 enpublic iOS apps. We discovered that: 844 (60%) out of the 1408 apps do use private APIs, 14 (1%) apps contain URL scheme vulnerabilities, 901 (64%) enpublic apps transport sensitive information through unencrypted channel or store the information in plaintext on the phone. In addition, we summarized 25 private APIs which are crucial and security sensitive on iOS 6/7/8, and we have filed one CVE (Common Vulnerabilities and Exposures) for iOS devices.

We present a novel insurance mechanism consisting of an insurance protocol and a transaction mechanism to reduce new seller ramp up time in eBay-like reputation mechanisms. We conduct experiments on an eBay's dataset and show that our insurance mechanism reduces ramp up time by 90%.

Recent studies show that disk-based graph computation on just a single PC can be as highly competitive as cluster-based computing systems on large-scale problems. Inspired by this remarkable progress, we develop VENUS, a disk-based graph computation system which is able to handle billion-scale problems efficiently on a commodity PC. VENUS adopts a novel computing architecture that features vertex-centric “streamlined” processing - the graph is sequentially loaded and the update functions are executed in parallel on the fly. VENUS deliberately avoids loading batch edge data by separating read-only structure data from mutable vertex data on disk. Furthermore, it minimizes random IOs by caching vertex data in main memory. The streamlined processing is realized with efficient sequential scan over massive structure data and fast feeding a large number of update functions. Extensive evaluation on large real-world and synthetic graphs has demonstrated the efficiency of VENUS. For example, VENUS takes just 8 minutes with hard disk for PageRank on the Twitter graph with 1.5 billion edges. In contrast, Spark takes 8.1 minutes with 50 machines and 100 CPUs, and GraphChi takes 13 minutes using fast SSD drive.

Random walk-based graph sampling methods have become increasingly popular and important for characterizing large-scale complex networks. While powerful, they are known to exhibit problems when the graph is loosely connected, which slows down the convergence of a random walk and can result in poor estimation accuracy. In this work, we observe that many graphs under study, called target graphs, usually do not exist in isolation. In many situations, a target graph is often related to an auxiliary graph and an affiliation graph, and the target graph becomes better connected when viewed from these three graphs as a whole, or what we called a hybrid social-affiliation network. This viewpoint brings extra benefits to the graph sampling framework, e.g., when directly sampling a target graph is difficult or inefficient, we can efficiently sample it with the assistance of auxiliary and affiliation graphs. We propose three sampling methods on such a hybrid social-affiliation network to estimate target graph characteristics, and conduct extensive experiments on both synthetic and real datasets, to demonstrate the effectiveness of these new sampling methods.

Online reputation systems serve as core building blocks in various Internet services such as E-commerce (e.g. eBay) and crowdsourcing (e.g., oDesk). The flaws of real-world online reputation systems were reported extensively. Users who are frustrated about the system will eventually abandon such service. However, no formal studies have explored such flaws. This paper presents the first attempt, which develops a novel data analytical framework to uncover online reputation system deficiencies from data. We develop a novel measure to quantify the efficiency of online reputation systems, i.e., ramp up time of a new service provider. We first show that inherent preferences or personal biases in assigning feedbacks (or ratings) cause the computational infeasibility in evaluating online reputation systems from data. We develop a computationally efficient randomized algorithm with theoretical performance guarantees to address this computational challenge. We apply our methodology to real-life datasets (from eBay and Google Helpouts), we discover that the ramp up time in eBay and Google Helpouts are around 791 and 1,327 days respectively. Around 78.7% sellers have ramped up in eBay and only 1.5% workers have ramped up in Google Helpouts. This small fraction and the long ramp up time (1,327 days) explain why Google Helpouts was eventually shut down in April 2015.

Nowadays, online crowdsourcing services are quite common such as Amazon Mechanical Turk and Google Helpouts. For such online services, it is important to attract "workers" to provide high-quality solutions to the "tasks" outsourced by "requesters". We present a unified study of incentive and reputation mechanisms for online crowdsourcing systems. We first design an mechanism to incentivize workers provide their maximum effort, which allows multiple workers to solve a task, splits the reward among workers based on requester evaluations of the solution quality. We design a reputation mechanism, which ensures that low-skilled workers do not provide low-quality solutions by tracking workers' historical contributions, and penalizing those workers having poor reputation. We show that our incentive and reputation mechanisms are robust against human biases in solution quality evaluation.

Repackaged malware and phishing malware consist 86% [35] of all Android malware, and they significantly affect the Android ecosystem. Previous work use disassembled Dalvik bytecode and hashing approaches to detect repackaged malware, but these approaches are vulnerable to obfuscation attacks and they demand large computational resources on mobile devices. In this work, we propose a novel methodology which uses the layout resources within an app to detect apps which are "visually similar", a common characteristic in repackaged apps and phishing malware. To detect visually similar apps, we design and implement DroidEagle which consists of two sub-systems: RepoEagle and HostEagle. RepoEagle is to perform large scale detection on apps repositories (e.g., apps markets), and HostEagle is a lightweight mobile app which can help users to quickly detect visually similar Android app upon download. We demonstrate the high accuracy and efficiency of DroidEagle: Within 3 hours RepoEagle can detect 1298 visually similar apps from 99 626 apps in a repository. In less than one second, HostEagle can help an Android user to determine whether a downloaded mobile app is a repackaged apps or a phishing malware. This is the first work which provides both speed and scalability in discovering repackaged apps and phishing malware in Android system.

Solid-state drives (SSDs) necessitate garbage collection (GC) to erase data blocks and reclaim the space of invalidated data, and GC inevitably introduces additional writes due to data relocation. The performance of GC, which is quantified by cleaning cost or write amplification, is critical to the overall performance of SSDs. However, characterizing GC performance is complicated by the general implementations of GC algorithms and the complex data locality characteristics of real-world workloads. This paper presents a general analytical study to characterize the performance impact of data locality on a general family of GC algorithms. We develop probabilistic models to address two fundamental issues: (1) What is the impact of data locality on the performance of locality-oblivious GC? (2) How can data locality be leveraged to improve the performance in locality-aware GC? We further conduct extensive trace-driven simulations on real-world workloads to validate the findings of our models.

Despite its popularity, SimRank is computationally costly, in both time and space. In particular, its recursive nature poses a great challenge in using modern distributed computing power, and also prevents querying similarities individually. Existing solutions suffer greatly from these practical issues. In this paper, we break such dependency for maximum efficiency possible. Our method consists of offline and online phases. In offline phase, a length- n indexing vector is derived by solving a linear system in parallel. At online query time, the similarities are computed instantly from the index vector. Throughout, the Monte Carlo method is used to maximally reduce time and space. Our algorithm, called CloudWalker, is highly parallelizable, with only linear time and space. Remarkably, it responses to both single-pair and single-source queries in constant time. CloudWalker is orders of magnitude more efficient and scalable than existing solutions for large-scale problems. Implemented on Spark with 10 machines and tested on the web-scale clue-web graph with 1 billion nodes and 43 billion edges, it takes 110 hours for offline indexing, 64 seconds for a single-pair query, and 188 seconds for a single-source query. To the best of our knowledge, our work is the first to report results on clue-web, which is 10x larger than the largest graph ever reported for SimRank computation.

Many mobile applications require frequent wireless transmissions between the content provider and mobile devices, consuming much energy in mobile devices. Motivated by the popularity of prefetch-friendly or delay-tolerant apps (e.g., social networking, app updates, cloud storage), we design and implement an application-layer transmission protocol, AppATP, which leverages cloud computing to manage data transmissions for mobile apps, transferring data to and from mobile devices in an energy efficient manner. Measurements show that significantly amount of energy is consumed by mobile devices during poor connectivity. Based on this observation, AppATP adaptively seizes periods of good bandwidth condition to prefetch frequently used data with minimum energy consumption, while deferring delay-tolerant data during poor network connectivity. Using the stochastic control framework, AppATP only relies on the current network information and data queue sizes to make an online decision on transmission scheduling, and performs well under unpredictable wireless network conditions. We implement AppATP on Samsung Note 2 smartphones and Amazon EC2. Results from both trace-driven simulations and extensive real-world experiments show that AppATP can be applied to a variety of application scenarios while achieving 30-50 percent energy savings for mobile devices.

Characterizing user pair relationships is important for applications such as friend recommendation and interest targeting in online social networks (OSNs). Due to the large-scale nature of such networks, it is infeasible to enumerate all user pairs and thus sampling is used. In this article, we show that it is a great challenge for OSN service providers to characterize user pair relationships, even when they possess the complete graph topology. The reason is that when sampling techniques (i.e., uniform vertex sampling (UVS) and random walk (RW)) are naively applied, they can introduce large biases, particularly for estimating similarity distribution of user pairs with constraints like existence of mutual neighbors, which is important for applications such as identifying network homophily. Estimating statistics of user pairs is more challenging in the absence of the complete topology information, as an unbiased sampling technique like UVS is usually not allowed and exploring the OSN graph topology is expensive. To address these challenges, we present unbiased sampling methods to characterize user pair properties based on UVS and RW techniques. We carry out an evaluation of our methods to show their accuracy and efficiency. Finally, we apply our methods to three OSNs—Foursquare, Douban, and Xiami—and discover that significant homophily is present in these networks.

Many Web services like Amazon, Epinions, and TripAdvisor provide historical product ratings so that users can evaluate the quality of products. Product ratings are important because they affect how well a product will be adopted by the market. The challenge is that we only have partial information on these ratings: each user assigns ratings to only a small subset of products. Under this partial information setting, we explore a number of fundamental questions. What is the minimum number of ratings a product needs so that one can make a reliable evaluation of its quality? How may users’ misbehavior, such as cheating in product rating, affect the evaluation result? To answer these questions, we present a probabilistic model to capture various important factors (e.g., rating aggregation rules, rating behavior) that may influence the product quality assessment under the partial information setting. We derive the minimum number of ratings needed to produce a reliable indicator on the quality of a product. We extend our model to accommodate users’ misbehavior in product rating. We derive the maximum fraction of misbehaving users that a rating aggregation rule can tolerate and the minimum number of ratings needed to compensate. We carry out experiments using both synthetic and real-world data (from Amazon and TripAdvisor). We not only validate our model but also show that the “average rating rule” produces more reliable and robust product quality assessments than the “majority rating rule” and the “median rating rule” in aggregating product ratings. Last, we perform experiments on two movie rating datasets (from Flixster and Netflix) to demonstrate how to apply our framework to improve the applications of recommender systems.

The evolution of the Internet has manifested itself in many ways: the traffic characteristics, the interconnection topologies, and the business relationships among the autonomous components. It is important to understand why (and how) this evolution came about, and how the interplay of these dynamics may affect future evolution and services. We propose a network-aware, macroscopic model that captures the characteristics and interactions of the application and network providers, and show how it leads to a market equilibrium of the ecosystem. By analyzing the driving forces and the dynamics of the market equilibrium, we obtain some fundamental understandings of the cause and effect of the Internet evolution, which explain why some historical and recent evolutions have happened. Furthermore, by projecting the likely future evolutions, our model can help application and network providers to make informed business decisions so as to succeed in this competitive ecosystem.

Android has a dominating share in the mobile market and there is a significant rise of mobile malware targeting Android devices. Android malware accounted for 97% of all mobile threats in 2013 [26]. To protect smartphones and prevent privacy leakage, companies have implemented various host-based intrusion prevention systems (HIPS) on their Android devices. In this paper, we first analyze the implementations, strengths and weaknesses of three popular HIPS architectures. We demonstrate a severe loophole and weakness of an existing popular HIPS product in which hackers can readily exploit. Then we present a design and implementation of a secure and extensible HIPS platform---"Patronus." Patronus not only provides intrusion prevention without the need to modify the Android system, it can also dynamically detect existing malware based on runtime information. We propose a two-phase dynamic detection algorithm for detecting running malware. Our experiments show that Patronus can prevent the intrusive behaviors efficiently and detect malware accurately with a very low performance overhead and power consumption.

Android mobile devices are enjoying a lion's market share in smartphones and mobile devices. This also attracts malware writers to target the Android platform. Recently, we have discovered a new Android malware distribution channel: releasing malicious firmwares with pre-installed malware to the wild. This poses significant risk since users of mobile devices cannot change the content of the malicious firmwares. Furthermore, pre-installed applications have " more permissions" (i.e., silent installation) than other legitimate mobile apps, so they can download more malware or access users' confidential information. To understand and address this new form of malware distribution channel, we design and implement "DroidRay": a security evaluation system for customized Android firmwares. DroidRay uses both static and dynamic analyses to evaluate the firmware security on both the application and system levels. To understand the impact of this new malware distribution channel, we analyze 250 Android firmwares and 24,009 pre-installed applications. We reveal how the malicious firmware and pre-installed malware are injected, and discovered 1,947 (8.1%) pre-installed applications have signature vulnerability and 19 (7.6%) firmwares contain pre-installed malware. In addition, 142 (56.8%) firmwares have the default signature vulnerability, five (2.0%) firmwares contain malicious hosts file, at most 40 (16.0%) firmwares have the native level privilege escalation vulnerability and at least 249 (99.6%) firmwares have the Java level privilege escalation vulnerability. Lastly, we investigate a real-world case of a pre-installed zero-day malware known as CEPlugnew, which involves 348,018 infected Android smartphones, and we show its degree and geographical penetration. This shows the significance of this new malware distribution channel, and DroidRay is an effective tool to combat this new form of malware spreading.

Many long-running network analytics applications impose a high-throughput and high reliability requirements on stream processing systems. However, previous stream processing systems cannot sustain high-speed traffic at the core router level. Furthermore, their fault-tolerant schemes cannot provide strong consistency which is essential for network analytics. In this paper, we present the design and implementation of SAND, a fault-tolerant distributed stream processing system for network analytics. SAND is designed to operate under high-speed network traffic, and it uses a novel check pointing protocol which can perform failure recovery based on upstream backup and check pointing. We prove our fault-tolerant scheme provides strong consistency even under multiple node failure. We implement several real-world network analytics applications on SAND, evaluate their performance using network traffic captured from commercial cellular core networks, and demonstrate that SAND can sustain high-speed network traffic and that our fault-tolerant scheme is efficient.

These keynote discusses the following: Big Data Science and Social Networks - Accelerating Insights and Building Value; Sampling Theory of Large Networks; Mining Online Social Networks: Opportunities and Privacy Issues.

In online learning, a player chooses actions to play and receives reward and feedback from the environment with the goal of maximizing her reward over time. In this paper, we propose the model of combinatorial partial monitoring games with linear feedback, a model which simultaneously addresses limited feedback, infinite outcome space of the environment and exponentially large action space of the player. We present the Global Confidence Bound (GCB) algorithm, which integrates ideas from both combinatorial multi-armed bandits and finite partial monitoring games to handle all the above issues. GCB only requires feedback on a small set of actions and achieves O(T^\frac23\log T) distribution-independent regret and O(\log T) distribution-dependent regret (the latter assuming unique optimal action), where T is the total time steps played. Moreover, the regret bounds only depend linearly on \log |X| rather than |X|, where X is the action space. GCB isolates offline optimization tasks from online learning and avoids explicit enumeration of all actions in the online learning part. We demonstrate that our model and algorithm can be applied to a crowdsourcing application leading to both an efficient learning algorithm and low regret, and argue that they can be applied to a wide range of combinatorial applications constrained with limited feedback.

Datacenter networks suffer unpredictable performance due to a lack of application level bandwidth guarantees. A lot of attentions have been drawn to solve this problem such as how to provide bandwidth guarantees for Virtualized Machines (VMs), proportional bandwidth share among tenants, and high network utilization under peak traffic. However, existing solutions fail to cope with highly dynamic traffic in datacenter networks. In this paper, we consider the effects of large numbers of short flows and massive bursty traffic in the datacenter, and design a novel distributed rate allocation algorithm based on the Logistic model under the control-theoretic framework. The theoretical analysis and experimental results using OpenFlow show that our algorithm not only guarantees the bandwidth for VMs, but also provides fast convergence to efficiency and fairness, and smooth response to bursty traffic.

In recent years, we have witnessed a growing trend for online service companies to offer “bundling sales” to increase revenue. Bundling sale means that a company groups a set of its products/services and charges this bundle at a fixed price, which is usually less than the total price of individual items. In this paper, our goal is to understand the underlying dynamics of bundling, in particular, what is the optimal bundling sale strategy and under what situations it will be more attractive than the separate sales. We focus on online service markets that exhibit network effect. We provide mathematical models to capture the interactions between buyers and sellers, analyze the market equilibrium and its stability, and formulate an optimization framework to determine the optimal sale strategy for the service provider. We analyze the impact of the key factors, including the network effects and operating costs, on the profitability of bundling. We show that bundling is more profitable than separate sale in most cases; however, the heterogeneity of services and the asymmetry of operating costs reduce the advantage of bundling. These findings provide important insights in designing proper sale strategies for online services.

Android, being an open source smartphone operating system, enjoys a large community of developers who create new mobile services and applications. However, it also attracts malware writers to exploit Android devices in order to distribute malicious apps in the wild. In fact, Android malware are becoming more sophisticated and they use advanced “dynamic loading” techniques like Java reflection or native code execution to bypass security detection. To detect dynamic loading, one has to use dynamic analysis. Currently, there are only a handful of Android dynamic analysis tools available, and they all have shortcomings in detecting dynamic loading. The aim of this paper is to design and implement a dynamic analysis system which allows analysts to perform systematic analysis of dynamic payloads with malicious behaviors. We propose “DroidTrace”, a ptrace based dynamic analysis system with forward execution capability. Our system uses ptrace to monitor selected system calls of the target process which is running the dynamic payloads, and classifies the payloads behaviors through the system call sequence, e.g., behaviors such as file access, network connection, inter-process communication and even privilege escalation. Also, DroidTrace performs “physical modification” to trigger different dynamic loading behaviors within an app. Using DroidTrace, we carry out a large scale analysis on 36,170 dynamic payloads in 50,000 apps and 294 malware in 10 families (four of them are zero-day) with various dynamic loading behaviors.

It is often crucial for manufacturers to decide what products to produce so that they can increase their market share in an increasingly fierce market. To decide which products to produce, manufacturers need to analyze the consumers' requirements and how consumers make their purchase decisions so that the new products will be competitive in the market. In this paper, we first present a general distance-based product adoption model to capture consumers' purchase behavior. Using this model, various distance metrics can be used to describe different real life purchase behavior. We then provide a learning algorithm to decide which set of distance metrics one should use when we are given some historical purchase data. Based on the product adoption model, we formalize the k most marketable products (or k-MMP) selection problem and formally prove that the problem is NP-hard. To tackle this problem, we propose an efficient greedy-based approximation algorithm with a provable solution guarantee. Using submodularity analysis, we prove that our approximation algorithm can achieve at least 63% of the optimal solution. We apply our algorithm on both synthetic datasets and real-world datasets (TripAdvisor.com), and show that our algorithm can easily achieve five or more orders of speedup over the exhaustive search and achieve about 96% of the optimal solution on average. Our experiments also show the significant impact of different distance metrics on the results, and how proper distance metrics can improve the accuracy of product selection.

Crowd sourcing systems like Yahoo! Answers, Amazon Mechanical Turk, and Google Helpouts, etc., have seen an increasing prevalence in the past few years. The participation of users, high quality solutions, and a fair rating system are critical to the revenue of a crowd sourcing system. In this paper, we design a class of simple but effective incentive mechanisms to attract users participating, and providing high quality solutions. Our incentive mechanism consists of a task bundling scheme and a rating system, and pay workers according to solution ratings from requesters. We also propose a probabilistic model to capture various human factors like biases in rating, and we quantify its impact on the incentive mechanism, which is shown to be highly robust. We develop a model to characterize the design space of a class of commonly used rating systems - threshold based rating systems. We quantify the impact of such rating systems and the bundling scheme on the incentive mechanism.

Given the globalized economy, how to process the heterogeneous web data so to extract customers' purchase behavior is crucial to manufacturers who want to enter or sustain in a competitive market. To maximize the sales, manufacturers not only need to decide what products to produce so to meet diverse customers' requirements, but at the same time, compete with competitors' products. In this paper, we present a general framework for the following product selection problems: (1) k-BSP problem, which is for a manufacturer to enter a competitive market, and (2) k-BBP problem, which is for a manufacturer to sustain in a competitive market. We propose several product adoption models to describe the complex purchase behavior of customers, and formally show that these problems are NP-hard in general. To tackle these problems, we propose computationally efficient greedy-based approximation algorithms. Based on the submodularity analysis, we prove that our algorithms can guarantee a (1--1/e)-approximation ratio as compared to the optimal solutions. We perform large scale data analysis to show the efficiency and accuracy of our framework. In our experiments, we observe 1,300 to 250,000 times speedup as compared to the exhaustive algorithms, and our solutions can achieve on average 96% of solution quality as compared to the optimal solutions. Finally, we apply our algorithms on web dataset to show the impact of customers' different purchase behavior on the results of product selection.

In modern parallel storage systems (e.g., cloud storage and data centers), it is important to provide data availability guarantees against disk (or storage node) failures via redundancy coding schemes. One coding scheme is X-code, which is double-fault tolerant while achieving the optimal update complexity. When a disk/node fails, recovery must be carried out to reduce the possibility of data unavailability. We propose an X-code-based optimal recovery scheme called minimum-disk-read-recovery (MDRR), which minimizes the number of disk reads for single-disk failure recovery. We make several contributions. First, we show that MDRR provides optimal single-disk failure recovery and reduces about 25 percent of disk reads compared to the conventional recovery approach. Second, we prove that any optimal recovery scheme for X-code cannot balance disk reads among different disks within a single stripe in general cases. Third, we propose an efficient logical encoding scheme that issues balanced disk read in a group of stripes for any recovery algorithm (including the MDRR scheme). Finally, we implement our proposed recovery schemes and conduct extensive testbed experiments in a networked storage system prototype. Experiments indicate that MDRR reduces around 20 percent of recovery time of the conventional approach, showing that our theoretical findings are applicable in practice.

Viral marketing is becoming important due to the popularity of online social networks (OSNs). Companies may provide incentives (e.g., via free samples of a product) to a small group of users in an OSN, and these users provide recommendations to their friends, which eventually increases the overall sales of a given product. Nevertheless, this also opens a door for malicious behaviors: dishonest users may intentionally give misleading recommendations to their friends so as to distort the normal sales distribution. In this paper, we propose a detection framework to identify dishonest users in the OSNs. In particular, we present a set of fully distributed and randomized algorithms, and also quantify the performance of the algorithms by deriving probability of false positive, probability of false negative, and the distribution of number of detection rounds. Extensive simulations are also carried out to illustrate the impact of misleading recommendations and the effectiveness of our detection algorithms. The methodology we present here will enhance the security level of viral marketing in the OSNs.

Exploring statistics of locally connected subgraph patterns (also known as network motifs) has helped researchers better understand the structure and function of biological and Online Social Networks (OSNs). Nowadays, the massive size of some critical networks—often stored in already overloaded relational databases—effectively limits the rate at which nodes and edges can be explored, making it a challenge to accurately discover subgraph statistics. In this work, we propose sampling methods to accurately estimate subgraph statistics from as few queried nodes as possible. We present sampling algorithms that efficiently and accurately estimate subgraph properties of massive networks. Our algorithms require no precomputation or complete network topology information. At the same time, we provide theoretical guarantees of convergence. We perform experiments using widely known datasets and show that, for the same accuracy, our algorithms require an order of magnitude less queries (samples) than the current state-of-the-art algorithms.

Peer-to-peer (P2P) systems rely on peers' cooperation to provide a more robust and scalable service as compared to the traditional client-server architecture. However, the peers might be selfish in nature-they would like to receive services from others, but would not like to contribute their own resources by default. To conquer this problem, proper incentive schemes are needed so as to stimulate the peers' contributions. In particular, in P2P video-on-demand (VoD) systems, peers need to distributively cache the proper videos so as to mutually upload and help each other to acquire the required data. Content providers of P2P-VoD services want to incentivize peers to do so and alleviate the workload of the content server. In this paper, we design a practical mechanism to incentivize distributed caching in such systems, under which the peers are rewarded based on the popularity of the video they cache. We characterize the impact of this incentive scheme on peers' caching behaviors. In particular, we formulate an optimization framework to decide the optimal reward price for each video so as to keep enough replicas and minimize the content provider's operational cost. We first derive close form solutions in an asymptotic system, and then extend our results to be adaptive to various practical issues. Via extensive simulations, we validate the effectiveness and efficiency of our incentive scheme.

Content-Centric Network (CCN) provides a cleanslate design for the Internet, where content becomes the primitive of communications. In CCN, routers are equipped with content stores, which act as caches for frequently requested content. This design enables the Internet to provide content distribution services without any application-layer support. On the other hand, as caches are integrated into routers, the overall performance of CCN will be influenced by the caching efficiency. This paper studies the performance issues of caches in CCN, with the aim to gain some understanding on how caches should be designed to maintain a high performance in a cost-efficient way. Specifically, we use a two-dimensional discrete-time Markov chain to model the two-layer cache hierarchy formed by CCN routers, and develop an efficient algorithm to calculate the hit ratios of these caches. Simulations validate the accuracy of our modeling method, and convey some understanding on cache design in CCN.

Characterizing user pair relationships is important for applications such as friend recommendation and interest targeting in online social networks (OSNs). Due to the large scale nature of such networks, it is infeasible to enumerate all user pairs and so sampling is used. In this paper, we show that it is a great challenge even for OSN service providers to characterize user pair relationships even when they possess the complete graph topology. The reason is that when sampling techniques (i.e., uniform vertex sampling (UVS) and random walk (RW)) are naively applied, they can introduce large biases, in particular, for estimating similarity distribution of user pairs with constraints such as existence of mutual neighbors, which is important for applications such as identifying network homophily. Estimating statistics of user pairs is more challenging in the absence of the complete topology information, since an unbiased sampling technique such as UVS is usually not allowed, and exploring the OSN graph topology is expensive. To address these challenges, we present asymptotically unbiased sampling methods to characterize user pair properties based on UVS and RW techniques respectively. We carry out an evaluation of our methods to show their accuracy and efficiency. Finally, we apply our methods to two Chinese OSNs, Doudan and Xiami, and discover significant homophily is present in these two networks.

With wide application of virtualization technology, tenants are able to access isolated cloud services by renting the shared resources in datacenters. Unlike resources such as CPU and memory, datacenter network, which relies on traditional transport-layer protocols, suffers unfairness due to a lack of VM-level network isolation. In this paper, we propose Falloc, a new bandwidth allocation protocol, towards VM-based fairness across the datacenter with two main objectives: (i) guarantee bandwidth for VMs based on their base bandwidth requirements, and (ii) share residual bandwidth in proportion to weights of VMs. To design Falloc, we model the datacenter bandwidth allocation as a bargaining game and propose a distributed algorithm to achieve the asymmetric Nash bargaining solution (NBS). We apply the theory to practice by implementing Falloc with OpenFlow in experiments under diversed scenarios, which shows that Falloc can achieve fairness by adapting to different network requirements of VMs, and balance the tradeoff between bandwidth guarantee and proportional bandwidth share. By carrying out large scale trace-driven simulations using real-world Mapreduce workload, we show that Falloc achieves high utilization and maintains fairness among VMs in datacenters.

In current IaaS datacenters, tenants are suffering unfairness since the network bandwidth is shared in a besteffort manner. To achieve predictable network performance for rented virtual machines (VMs), cloud providers should guarantee minimum bandwidth for VMs or allocate the network bandwidth in a fairness fashion at VM-level. At the same time, the network should be efficiently utilized in order to maximize cloud providers' revenue. In this paper, we model the bandwidth sharing problem as a Nash bargaining game, and propose the allocation principles by defining a tunable base bandwidth for each VM. Specifically, we guarantee bandwidth for those VMs with lower network rates than their base bandwidth, while maintaining fairness among other VMs with higher network rates than their base bandwidth. Based on rigorous cooperative game-theoretic approaches, we design a distributed algorithm to achieve efficient and fair bandwidth allocation corresponding to the Nash bargaining solution (NBS). With simulations under typical scenarios, we show that our strategy can meet the two desirable requirements towards predictable performance for tenants as well as high utilization for providers. And by tuning the base bandwidth, our solution can enable cloud providers to flexibly balance the tradeoff between minimum guarantees and fair sharing of datacenter networks.

Recently, data center carbon emission has become an emerging concern for the cloud service providers. Previous works are limited on cutting down the power consumption of the data centers to defuse such a concern. In this paper, we show how the spatial and temporal variabilities of the electricity carbon footprint can be fully exploited to further green the cloud running on top of geographically distributed data centers. We jointly consider the electricity cost, service level agreement (SLA) requirement, and emission reduction budget. To navigate such a three-way tradeoff, we take advantage of Lyapunov optimization techniques to design and analyze a carbon-aware control framework, which makes online decisions on geographical load balancing, capacity right-sizing, and server speed scaling. Results from rigorous mathematical analyses and real-world trace-driven empirical evaluation demonstrate its effectiveness in both minimizing electricity cost and reducing carbon emission.

Solid state drives (SSDs) have seen wide deployment in mobiles, desktops,and data centers due to their high I/O performance and low energy consumption. As SSDs write data out-of-place, garbage collection (GC) is required to erase and reclaim space with invalid data. However, GC poses additional writes that hinder the I/O performance, while SSD blocks can only endure a finite number of erasures. Thus, there is a performance-durability tradeoff on the design space of GC. To characterize the optimal tradeoff, this paper formulates an analytical model that explores the full optimal design space of any GC algorithm. We first present a stochastic Markov chain model that captures the I/O dynamics of large-scale SSDs, and adapt the mean-field approach to derive the asymptotic steady-state performance. We further prove the model convergence and generalize the model for all types of workload. Inspired by this model, we propose a randomized greedy algorithm (RGA) that can operate along the optimal tradeoff curve with a tunable parameter. Using trace-driven simulation on DiskSim with SSD add-ons, we demonstrate how RGA can be parameterized to realize the performance-durability tradeoff.

Solid-state drives (SSDs) have been widely deployed in desktops and data centers. However, SSDs suffer from bit errors, and the bit error rate is time dependent since it increases as an SSD wears down. Traditional storage systems mainly use parity-based RAID to provide reliability guarantees by striping redundancy across multiple devices, but the effectiveness of RAID in SSDs remains debatable as parity updates aggravate the wearing and bit error rates of SSDs. In particular, an open problem is that how different parity distributions over multiple devices, such as the even distribution suggested by conventional wisdom, or uneven distributions proposed in recent RAID schemes for SSDs, may influence the reliability of an SSD RAID array. To address this fundamental problem, we propose the first analytical model to quantify the reliability dynamics of an SSD RAID array. Specifically, we develop a "non-homogeneous" continuous time Markov chain model, and derive the transient reliability solution. We validate our model via trace-driven simulations and conduct numerical analysis to provide insights into the reliability dynamics of SSD RAID arrays under different parity distributions and subject to different bit error rates and array configurations. Designers can use our model to decide the appropriate parity distribution based on their reliability requirements.

The evolution of the Internet has manifested itself in many ways: the traffic characteristics, the interconnection topologies and the business relationships among the autonomous components. It is important to understand why (and how) this evolution came about, and how the interplay of these dynamics may affect future evolution and services. We propose a network aware, macroscopic model that captures the characteristics and interactions of the application and network providers, and show how it leads to a market equilibrium of the ecosystem. By analyzing the driving forces and the dynamics of the market equilibrium, we obtain some fundamental understandings of the cause and effect of the Internet evolution, which explain why some historical and recent evolutions have happened. Furthermore, by projecting the likely future evolutions, our model can help application and network providers to make informed business decisions so as to succeed in this competitive ecosystem.

Epidemic attack is a severe security problem in network-coding-enabled wireless mesh networks (WMNs). Malicious nodes can easily launch such form of attack to create an epidemic spreading of polluted packets and deplete network resources. The contribution of this work is to address such security problem. We allow the presence of "smartâ attackers, i.e., they can pretend to be legitimate nodes to probabilistically transmit valid packets so as to reduce the chance of being detected. We also address the case where attackers cooperatively inject polluted packets. We employ the time-based checksum and batch verification to determine the existence of polluted packets, then propose a set of fully "distributedâ and "randomizedâ detection algorithms so that each legitimate node in a WMN can identify its malicious neighbors and purge them for future communication. We provide formal analysis to quantify the performance of the algorithms. Furthermore, simulation and system prototyping are carried out to validate the theoretic analysis and show the effectiveness and efficiency of the detection algorithms.

Given the popularity of smartphones and mobile devices, mobile botnets are becoming an emerging threat to users and network operators. We propose a new form of cloud-based push-styled mobile botnets that exploits today's push notification services as a means of command dissemination. To motivate its practicality, we present a new command and control (C&C) channel using Google's Cloud to Device Messaging (C2DM) service, and develop a C2DM botnet specifically for the Android platform. We present strategies to enhance its scalability to large botnet coverage and its resilience against service disruption. We prototype a C2DM botnet, and perform evaluation to show that the C2DM botnet is stealthy in generating heartbeat and command traffic, resource-efficient in bandwidth and power consumptions, and controllable in quickly delivering a command to all bots. We also discuss how one may deploy a C2DM botnet, and demonstrate its feasibility in launching an SMS-Spam-and-Click attack. Lastly, we discuss how to generalize the design to other platforms, such as iOS or Window-based systems, and recommend possible defense methods. Given the wide adoption of push notification services, we believe that this type of mobile botnets requires special attention from our community.

Practical wireless network coding (e.g., COPE) is a promising technique that can enhance the throughput of wireless networks. However, such a technique also bears a serious security drawback: it breaks the current privacy-preserving protocols (e.g., Onion Routing), since their operations conflict each other. As user privacy in wireless networks is highly valued nowadays, a new privacy-preserving scheme that can function with wireless network coding becomes indispensable. To address such a challenge, we apply the idea of cooperative networking and design a novel anonymity scheme named ANOC, which can function in network-coding-based wireless mesh networks. ANOC is built upon the classic Onion Routing protocol, and resolves its conflict with network coding by introducing efficient cooperation among relay nodes. Using ANOC, we can perform network coding to achieve a higher throughput, while still preserving user privacy in wireless mesh networks. We formally show how ANOC achieves the property of relationship anonymity, and conduct extensive experiments via nsclick to demonstrates its feasibility and efficiency when integrated with network coding.

Content distribution via network coding has received a lot of attention lately. However, direct application of network coding may be insecure. In particular, attackers can inject "bogus” data to corrupt the content distribution process so as to hinder the information dispersal or even deplete the network resource. Therefore, content verification is an important and practical issue when network coding is employed. When random linear network coding is used, it is infeasible for the source of the content to sign all the data, and hence, the traditional "hash-and-sign” methods are no longer applicable. Recently, a new on-the-fly verification technique has been proposed by Krohn et al. (IEEE S&P '04), which employs a classical homomorphic hash function. However, this technique is difficult to be applied to network coding because of high computational and communication overhead. We explore this issue further by carefully analyzing different types of overhead, and propose methods to help reducing both the computational and communication cost, and provide provable security at the same time.

We can now outsource data backups off-site to third-party cloud storage services so as to reduce data management costs. However, we must provide security guarantees for the outsourced data, which is now maintained by third parties. We design and implement FADE, a secure overlay cloud storage system that achieves fine-grained, policy-based access control and file assured deletion. It associates outsourced files with file access policies, and assuredly deletes files to make them unrecoverable to anyone upon revocations of file access policies. To achieve such security goals, FADE is built upon a set of cryptographic key operations that are self-maintained by a quorum of key managers that are independent of third-party clouds. In particular, FADE acts as an overlay system that works seamlessly atop today's cloud storage services. We implement a proof-of-concept prototype of FADE atop Amazon S3, one of today's cloud storage services. We conduct extensive empirical studies, and demonstrate that FADE provides security protection for outsourced data, while introducing only minimal performance and monetary cost overhead. Our work provides insights of how to incorporate value-added security features into today's cloud storage services.

We consider the following advertisement problem in online social networks (OSNs). Given a fixed advertisement investment, e.g., a number of free samples that can be given away to a small number of users, a company needs to determine the probability that users in the OSN will eventually purchase the product. In this paper, we model OSNs as scale-free graphs (either with or without high clustering coefficient). We employ various influence mechanisms that govern the influence spreading in such large-scale OSNs and use the local mean field (LMF) technique to analyze these online social networks wherein states of nodes can be changed by various influence mechanisms. We extend our model for advertising with multiple rating levels. Extensive simulations are carried out to validate our models, which can provide insight on designing efficient advertising strategies in online social networks.

In peer-to-peer (P2P) networks, incentive protocol is used to encourage cooperation among end-nodes so as to deliver a scalable and robust service. However, the design and analysis of incentive protocols have been ad hoc and heuristic at best. The objective of this paper is to provide a simple yet general framework to analyze and design incentive protocols. We consider a class of incentive protocols that can learn and adapt to other end-nodes' strategies. Based on our analytical framework, one can evaluate the expected performance gain and, more importantly, the system robustness of a given incentive protocol. To illustrate the framework, we present two adaptive learning models and three incentive policies and show the conditions in which the P2P networks may collapse and the conditions in which the P2P networks can guarantee a high degree of cooperation. We also show the connection between evaluating incentive protocol and evolutionary game theory so one can easily identify robustness characteristics of a given policy. Using our framework, one can gain the understanding on the price of altruism and system stability, as well as the correctness of the adaptive incentive policy.

P2P-Video-on-Demand (P2P-VoD) is a popular Internet service which aims to provide a scalable and high-quality service to users. At the same time, content providers of P2P-VoD services also need to make sure that the service is operated with a manageable operating cost. Given the volume-based charging model by ISPs, P2P-VoD content providers would like to reduce peers' access to the content server so as to reduce the operating cost. In this paper, we address an important open problem: what is the “optimal replication ratio” in a P2P-VoD system such that peers will receive service from each other and at the same time, reduce the access to the content server? We address two fundamental issues: 1) what is the optimal replication ratio of a movie if we know its popularity, and 2) how to achieve these optimal ratios in a distributed and dynamic fashion. We first formally show how movie popularities can impact server's workload, and formulate the video replication as an optimization problem. We show that the conventional wisdom of using the proportional replication strategy is “suboptimal,” and expand the design space to both “passive replacement policy” and “active push policy” to achieve the optimal replication ratios. We consider practical implementation issues, evaluate the performance of P2P-VoD systems and show how to greatly reduce server's workload and improve streaming quality via our distributed algorithms.

Viral marketing is becoming important due to the popularity of online social networks (OSNs) and the fact that many users have integrated OSNs into their daily activities, e.g., they provide recommendations to their friends on the products they purchased, or they make decision based on received recommendations. Nevertheless, this also opens door for "shill attack": dishonest users may give wrong recommendations so as to distort the normal sales distribution. In this paper, we propose a detection mechanism to discover these dishonest users in OSNs. In particular, we present two fully distributed algorithms to detect attackers in both (1) the baseline shill attack and (2) the intelligent shill attack. We quantify the performance of our algorithms by deriving the probability of false positive, probability of false negative and distribution function of time needed to detect these dishonest users. Extensive simulations are carried to illustrate the impact of shill attack and the effectiveness of our detection algorithms. The methodology we present here will enhance the security level of viral marketing in OSNs.

Pollution attack is a severe security problem in network-coding enabled wireless mesh networks (WMNs). Under such form of attack, malicious nodes can easily create an epidemic spreading of polluted packets to deplete network resources. We address this security problem even when the attackers are "intelligent" in the sense that they may pretend to be legitimate nodes to probabilistically transmit valid packets so as to reduce the chance of being detected. We use the batch verification technique to determine the existence of polluted packets, and propose fully "distributed" and "randomized" detection algorithms to identify the attackers who inject polluted packets, and purge them for future communication. Formal analysis is provided to quantify performance measures of the algorithms, e.g., probability of false positive and probability of false negative, as well as the probability distribution of time needed to identify all malicious nodes. Simulation and system prototype are carried out to show the effectiveness and efficiency of the detection algorithms.

Content providers of P2P-Video-on-Demand (P2P-VoD) services aim to provide a high quality, scalable service to users, and at the same time, operate the system with a manageable operating cost. Given the volume-based charging model by ISPs, it is to the best interest of the P2P-VoD content providers to reduce peers' access to the content server so as to reduce the operating cost. In this paper, we address an important open problem: what is the “optimal replication ratio” in a P2P-VoD system such that peers will receive service from each other and at the same time, reduce the traffic to the content server. We address two fundamental problems: (1) what is the optimal replication ratio of a movie given its popularity, and (2) how to achieve the optimal ratios in a distributed and dynamic fashion. We formally show how movie popularities can impact server's workload, and formulate the video replication as an optimization problem. We show that the conventional wisdom of using the proportional replication strategy is non-optimal, and expand the design space to both passive replacement policy and active push policy to achieve the optimal replication ratios. We consider practical implementation issues, evaluate the performance of P2P-VoD systems and show that our algorithms can greatly reduce server's workload and improve streaming quality.

As P2P multimedia streaming service is becoming more popular, it is important for P2P-VoD content providers to protect their servers identity. In this paper, we first show that it is possible to launch an "identity attack": exposing and identifying servers of peer-to-peer video-on-demand (P2P-VoD) systems. The conventional wisdom of the P2P-VoD providers is that identity attack is very difficult because peers cannot distinguish between regular peers and servers in the P2P streaming process. We are the first to show that it is otherwise, and present an efficient and systematic methodology to perform P2P-VoD servers detection. Furthermore, we present an analytical framework to quantify the probability that an endhost is indeed a P2P-VoD server. In the second part of this paper, we present a novel architecture that can hide the identity and provide anonymity protection for servers in P2P-VoD systems. To quantify the protective capability of this architecture, we use the "fundamental matrix theory" to show the high complexity of discovering all protective nodes so as to disrupt the P2P-VoD service. We not only validate the model via extensive simulation, but also implement this protective architecture on PlanetLab and carry out measurements to reveal its robustness against identity attack.

Incentive mechanisms are often needed in wireless mesh networks (WMNs) so as to encourage nodes to relay or forward packets for other nodes. However, there is a lack of understanding on the interactions between the incentive mechanisms and the underlying routing protocols, and whether the network can sustain such traffic workload in the long run. In this paper, we propose a general mathematical framework via stochastic difference equations to model the interaction of incentive mechanisms and routing protocols. A credit evolution model is provided. Based on it, we study the expected credit variation of each node and use the Gini's coefficient to quantify the credit disparity among nodes. We also introduce the concept of differentiated pricing in the incentive mechanism to achieve credit equality among nodes so the WMN is more robust to sustain the traffic workloads.

Internet service providers (ISPs) depend on one another to provide global network services. However, the profit-seeking nature of the ISPs leads to selfish behaviors that result in inefficiencies and disputes in the network. This concern is at the heart of the “network neutrality” debate, which also asks for an appropriate compensation structure that satisfies all types of ISPs. Our previous work showed in a general network model that the Shapley value has several desirable properties, and that if applied as the profit model, selfish ISPs would yield globally optimal routing and interconnecting decisions. In this paper, we use a more detailed and realistic network model with three classes of ISPs: content, transit, and eyeball. This additional detail enables us to delve much deeper into the implications of a Shapley settlement mechanism. We derive closed-form Shapley values for more structured ISP topologies and develop a dynamic programming procedure to compute the Shapley values under more diverse Internet topologies. We also identify the implications on the bilateral compensation between ISPs and the pricing structures for differentiated services. In practice, these results provide guidelines for solving disputes between ISPs and for establishing regulatory protocols for differentiated services and the industry.

Peer-to-peer (P2P) streaming tries to achieve scalability (like P2P file distribution) and at the same time meet real-time playback requirements. It is a challenging problem still not well understood. In this paper, we describe a simple stochastic model that can be used to compare different downloading strategies to random peer selection. Based on this model, we study the tradeoffs between supported peer population, buffer size, and playback continuity. We first study two simple strategies: Rarest First (RF) and Greedy. The former is a well-known strategy for P2P file sharing that gives good scalability by trying to propagate the chunks of a file to as many peers as quickly as possible. The latter is an intuitively reasonable strategy to get urgent chunks first to maximize playback continuity from a peer's local perspective. Yet in reality, both scalability and urgency should be taken care of. With this insight, we propose a Mixed strategy that achieves the best of both worlds. Furthermore, the Mixed strategy comes with an adaptive algorithm that can adapt its buffer setting to dynamic peer population. We validate our analytical model with simulation. Finally, we also discuss the modeling assumptions and the model's sensitivity to different parameters and show that our model is robust.

The current parallel storage systems use thousands of inexpensive disks to meet the storage requirement of applications. Data redundancy and/or coding are used to enhance data availability, for instance, Row-diagonal parity (RDP) and EVENODD codes, which are widely used in RAID-6 storage systems, provide data availability with up to two disk failures . To reduce the probability of data unavailability, whenever a single disk fails, disk recovery will be carried out. We find that the conventional recovery schemes of RDP and EVENODD codes for a single failed disk only use one parity disk. However, there are two parity disks in the system, and both can be used for single disk failure recovery. In this article, we propose a hybrid recovery approach that uses both parities for single disk failure recovery, and we design efficient recovery schemes for RDP code (RDOR-RDP) and EVENODD code (RDOR-EVENODD). Our recovery scheme has the following attractive properties: (1) “ read optimality ” in the sense that our scheme issues the smallest number of disk reads to recover a single failed disk and it reduces approximately 1/4 of disk reads compared with conventional schemes; (2) “ load balancing property ” in that all surviving disks will be subjected to the same (or almost the same) amount of additional workload in rebuilding the failed disk. We carry out performance evaluation to quantify the merits of RDOR-RDP and RDOR-EVENODD on some widely used disks with DiskSim. The offline experimental results show that RDOR-RDP and RDOR-EVENODD outperform the conventional recovery schemes of RDP and EVENODD codes in terms of total recovery time and recovery workload on individual surviving disk. However, the improvements are less than the theoretical value (approximately 25%), as RDOR-RDP and RDOR-EVENODD change the disk access pattern from purely sequential to a more random one compared with their conventional schemes.

Modern storage systems use thousands of inexpensive disks to meet the storage requirement of applications. To enhance the data availability, some form of redundancy is used. For example, conventional RAID-5 systems provide data availability for single disk failure only, while recent advanced coding techniques such as row-diagonal parity (RDP) can provide data availability with up to two disk failures. To reduce the probability of data unavailability, whenever a single disk fails, disk recovery (or rebuild) will be carried out. We show that conventional recovery scheme of RDP code for a single disk failure is inefficient and suboptimal. In this paper, we propose an optimal and efficient disk recovery scheme, Row-Diagonal Optimal Recovery (RDOR), for single disk failure of RDP code that has the following properties: (1) it is read optimal in the sense that it issues the smallest number of disk reads to recover the failed disk; (2) it has the load balancing property that all surviving disks will be subjected to the same amount of additional workload in rebuilding the failed disk. We carefully explore the design state space and theoretically show the optimality of RDOR. We carry out performance evaluation to quantify the merits of RDOR on some widely used disks.

Recently, there has been a growing interest of using network coding to improve the performance of wireless networks, for example, authors of proposed the practical wireless network coding system called COPE, which demonstrated the throughput gain achieved by network coding. However, COPE has two fundamental limitations: (1) the coding opportunity is crucially dependent on the established routes and (2) the coding structure in COPE is limited within a two-hop region only. The aim of this paper is to overcome these limitations. In particular, we propose DCAR, the distributed coding-aware routing mechanism which enables: (1) the discovery for available paths between a given source and destination and (2) the detection for potential network coding opportunities over much wider network region. One interesting result is that DCAR has the capability to discover high throughput paths with coding opportunities, while conventional wireless network routing protocols fail to do so. In addition, DCAR can detect coding opportunities on the entire path, thus eliminating the ¿two-hop¿ coding limitation in COPE. We also propose a novel routing metric called coding-aware routing metric (CRM) which facilitates the performance comparison between ¿coding-possible¿ and "coding-impossible¿ paths. We implement the DCAR system in ns-2 and carry out extensive evaluation. We show that when comparing to the coding mechanism in, DCAR can achieve much higher throughput gain.

Network coding is an attracting technology that has been shown to be able to improve the throughput of wireless networks. However, there still lacks fundamental understanding on how network coding works under realistic scenarios. In this paper, we examine the performance of a recently proposed network coding system under a realistic wireless physical layer and practical random access mechanisms. We propose a key performance measure called “encoding number”-the number of packets that can be encoded via network coding in each transmission. We provide an upper bound on the encoding number for the general coding topology, and derive the average encoding number and system throughput for a general class of random access mechanisms. Based on the practical coding system, we also derive a tighter upper bound on the throughput gain for a general wireless network. Our results are of fundamental value for coding-related MAC/Routing protocol design and analysis.

Within the current Internet, autonomous ISPs implement bilateral agreements, with each ISP establishing agreements that suit its own local objective to maximize its profit. Peering agreements based on local views and bilateral settlements, while expedient, encourage selfish routing strategies and discriminatory interconnections. From a more global perspective, such settlements reduce aggregate profits, limit the stability of routes, and discourage potentially useful peering/connectivity arrangements, thereby unnecessarily balkanizing the Internet. We show that if the distribution of profits is enforced at a global level, then there exist profit-sharing mechanisms derived from the coalition games concept ofShapley valueand its extensions that will encourage these selfish ISPs who seek to maximize their own profits to converge to a Nash equilibrium. We show that these profit-sharing schemes exhibit several fairness properties that support the argument that this distribution of profits is desirable. In addition, at the Nash equilibrium point, the routing and connecting/peering strategies maximize aggregate network profits and encourage ISP connectivity so as to limit balkanization.

In the past few years, P2P file distribution applications (e.g., BitTorrent) are becoming so popular that they are the dominating source of Internet traffic. This creates significant problems to Internet Service Providers (ISPs), not only because of the added complexity in traffic engineering, but the increase of traffic, in particular on the cross-ISP links, implies congestion and a higher operating cost. In this paper, we consider an ISP-friendly file distribution protocol which uses the “exploiting-the-locality principle” (ELP) to reduce the cross-ISP traffic. To show its benefit, we derive an upper and lower bound of cross-ISP traffic for the protocols which rely on ELP and show that the cross-ISP traffic can be reduced significantly when the number of peers within an ISP increases. To carry out realistic study, we design and implement our ISP-friendly protocol (which is compatible with the current BitTorrent protocol) and carry out large scale experiments on PlanetLab to measure the reduction of the cross ISP-traffic and the file downloading time. More important, we also show how the proposed ISP-friendly protocol can handle the “black-hole” security attack. This paper sheds light on the merits and design direction of ISP-friendly content distribution protocols.

In this paper, we explore the "clustering" phenomenon in BT-like systems. A high clustering implies peers have a high tendency to exchange information with peers of the similar bandwidth type. We first show the clustering does exist in BT-like systems. Although high clustering is desirable for file sharing application, it may not be appropriate for multimedia streaming applications. We provide analytical models to calculate the clustering index and illustrate how one can control the clustering index for different P2P applications.

Incentive protocols play a crucial role to encourage cooperation among nodes in networking applications. The aim of this paper is to provide a general analytical framework to analyze and design a large family of incentive protocols. We consider a class of incentive protocols wherein peers can distributively learn and adapt their actions. Using our analytical framework, one can evaluate the expected performance gain and system robustness of a given incentive protocol. To illustrate the framework, we present three incentive policies and two learning (or adaptive) models. We show under what conditions the network may collapse (e.g., no cooperation in the system) or the incentive protocol can guarantee a high degree of cooperation. In particular, we formally show the connection between evaluating incentive protocols and evolutionary game theory so to identify robustness characteristics of an incentive policy.

Data-driven P2P streaming systems can potentially provide good playback rate to a large number of viewers. One important design problem in such P2P systems is to determine the optimal chunk selection policy that provides high continuity playback under the server's upload capacity constraint. We present a general and unified mathematical framework to analyze a large class of chunk selection policies. The analytical framework is asymptotically exact when the number of viewers is large. More importantly, we provide some interesting observations on the optimal chunk selection policy: it is of shaped and becomesmore greedy as the upload capacity of the server increases. This insight helps content providers to deploy large scale streaming systems with a QoS-guarantee under a given cost constraint.

Recent works show conflicting results: network capacity may increase or decrease with higher transmission power under different scenarios. In this work, we want to understand this paradox. Specifically, we address the following questions: (1)Theoretically, should we increase or decrease transmission power to maximize network capacity? (2) Theoretically, how much network capacity gain can we achieve by power control? (3) Under realistic situations, how do power control, link scheduling and routing interact with each other? Under which scenarios can we expect a large capacity gain by using higher transmission power? To answer these questions, firstly, we prove that the optimal network capacity is a non-decreasing function of transmission power. Secondly, we prove that the optimal network capacity can be increased unlimitedly by higher transmission power in some network configurations. However, when nodes are distributed uniformly, the gain of optimal network capacity by higher transmission power is upper-bounded by a positive constant. Thirdly, we discuss why network capacity may increase or decrease with higher transmission power under different scenarios using carrier sensing and the minimum hop-count routing. Extensive simulations verify our analysis.

Abstract Stream control (SC) has recently attracted attentions in the research of multiple input multiple output (MIMO) wireless networks as a potential way to improve network capacity. However, inappropriate use of SC may significantly degrade network capacity as well. In this paper, we provide the first formal study on SC scheduling in MIMO wireless mesh networks (WMNs). We derive the theoretical upper bound on network capacity gain of SC scheduling. We also provide an efficient scheduling algorithm and show that its achieved network capacity gain is close to its theoretical upper bound. Moreover, we point out the poor performance of a previous SC scheduling algorithm SCMA under the general settings of WMNs. This formal characterization provides a deeper understanding of steam control scheduling in MIMO WMNs. Copyright © 2008 John Wiley & Sons, Ltd.

Internet service providers (ISPs) depend on one another to provide global network services. However, the profit-seeking nature of the ISPs leads to selfish behaviors that result in inefficiencies and disputes in the network. This concern is at the heart of the "network neutrality" debate, which also asks for an appropriate compensation structure that satisfies all types of ISPs. Our previous work showed in a general network model that the Shapley value has several desirable properties, and that if applied as the revenue model, selfish ISPs would yield globally optimal routing and interconnecting decisions.

The practical network coding system proposed in (S. Katti et al., 2006) has two fundamental limitations: 1) the coding opportunity is crucially dependent on the established routes; 2) the coding structure is limited within a two-hop region. To overcome these limitations, we propose DCAR, the first distributed coding-aware routing mechanism which combines (a) the discovery for available paths between a given source and destination, and (b) the detection for potential network coding opportunities. DCAR has the potential to find high throughput paths with coding opportunities while conventional routing fails to do so. In addition, DCAR can detect coding opportunities on the entire path, thus eliminating the "two-hop" coding limitation in (S. Katti et al., 2006). We also propose a novel routing metric called "CRM" (coding-aware routing metric) which facilitates the comparison between coding-possible and coding-impossible paths. We implement the DCAR system in NS-2 and conduct extensive evaluation, which shows that DCAR achieves 7% to 20% throughput gain over the coding system in [1].

While the practical coding scheme has been shown to be able to improve throughput of wireless networks, there still lacks fundamental understanding on how the coding scheme works under realistic settings, namely, when it operates on a realistic physical layer and the medium access is controlled by some random access methods. In this paper, we provide a formal analysis on the performance of the practical coding scheme under such realistic settings. The key performance measure is the encoding number, i.e., the number of packets that can be encoded by a coding node in each transmission. We provide an upper bound on the encoding number for the general coding topology, and derive the average encoding number and system throughput for a general class of random access mechanisms. Based on the practical coding scheme, we also derive a tighter upper bound on the throughput gain for a general wireless network. Our results can be particularly useful for coding-related MAC/Routing protocol design and analysis.

Accurate identification of network applications is important to many network activities. Traditional port-based technique has become much less effective since many new applications no longer use well-known port numbers. In this paper, we propose a novel profile-based approach to identify traffic flows belonging to the target application. In contrast to classifying traffic based on statistics of individual flows in previous studies, we build behavioral profiles of the target application, which describe dominant patterns of the application. Based on the behavioral profiles, a two-level matching is used in identifying new traffic. We first determine if a host participates in the application by comparing its behavior with the profiles. Subsequently, for each flow of the host we compare if it matches with the patterns in the profiles to determine which flows belong to this application. We demonstrate the effectiveness of our method on campus traffic traces. Our results show that one can identify the popular P2P applications with very high accuracy.

P2P file downloading and streaming have already become very popular Internet applications. These systems dramatically reduce the server loading, and provide a platform for scalable content distribution, as long as there is interest for the content. P2P-based video-on-demand (P2P-VoD) is a new challenge for the P2P technology. Unlike streaming live content, P2P-VoD has less synchrony in the users sharing video content, therefore it is much more difficult to alleviate the server loading and at the same time maintaining the streaming performance. To compensate, a small storage is contributed by every peer, and new mechanisms for coordinating content replication, content discovery, and peer scheduling are carefully designed. In this paper, we describe and discuss the challenges and the architectural design issues of a large-scale P2P-VoD system based on the experiences of a real system deployed by PPLive. The system is also designed and instrumented with monitoring capability to measure both system and component specific performance metrics (for design improvements) as well as user satisfaction. After analyzing a large amount of collected data, we present a number of results on user behavior, various system performance metrics, including user satisfaction, and discuss what we observe based on the system design. The study of a real life system provides valuable insights for the future development of P2P-VoD technology.

In this work, we seek to understand the interaction between different tiers of ISPs. The lower tier ISPs can transmit traffic to each other, either by purchasing the service from higher tier ISPs, or by setting "private peering links" between themselves. Higher tier ISPs cannot charge the transit service at will since there is competition among higher tier ISPs. We model the interaction of these ISPs via a game theoretic approach. We study the issues of (a) impact of private peering relationship among the lower tier ISPs, (b) under a competitive market, how can the higher tier ISPs perform resource allocation and revenue maximization, (c) conditions wherein higher tier ISPs are willing to perform network upgrade, in particular, when we scale up the network. Our mathematical framework provides insights on the interaction among ISPs and shows these ISPs can still gain profits as they upgrade the network infrastructures.

The probabilistic packet marking (PPM) algorithm is a promising way to discover the Internet map or an attack graph that the attack packets traversed during a distributed denial-of-service attack. However, the PPM algorithm is not perfect, as its termination condition is not well defined in the literature. More importantly, without a proper termination condition, the attack graph constructed by the PPM algorithm would be wrong. In this work, we provide a precise termination condition for the PPM algorithm and name the new algorithm the rectified PPM (RPPM) algorithm. The most significant merit of the RPPM algorithm is that when the algorithm terminates, the algorithm guarantees that the constructed attack graph is correct, with a specified level of confidence. We carry out simulations on the RPPM algorithm and show that the RPPM algorithm can guarantee the correctness of the constructed attack graph under 1) different probabilities that a router marks the attack packets and 2) different structures of the network graph. The RPPM algorithm provides an autonomous way for the original PPM algorithm to determine its termination, and it is a promising means of enhancing the reliability of the PPM algorithm.

Network entities cooperating together can improve system performance of media streaming. In this paper, we address the “ incentive issue ” of a cooperative proxy caching system and how to motivate each proxy to provide cache space to the system. To encourage proxies to participate, we propose a “ revenue-rewarding scheme ” to credit the cooperative proxies according to the resources they contribute. A game-theoretic model is used to analyze the interactions among proxies under the revenue-rewarding scheme. We propose two cooperative game settings that lead to optimal situations. In particular, (1) We propose a distributed incentive framework for peers to participate in resource contribution for media streaming; (2) Proxies are encouraged to cooperate under the revenue-rewarding scheme; (3) Profit and social welfare are maximized in these cooperative games; and (4) Cost-effective resource allocation is achieved in these cooperative games. Large scale simulation is carried out to validate and verify the merits of our proposed incentive schemes.

The Internet is a hierarchical architecture comprising heterogeneous entities of privately owned infrastructures, where higher level Internet service providers (ISPs) supply connectivity to the local ISPs and charge the local ISPs for the transit services. One of the challenging problems facing service providers today is how the profitability can be increased while maintaining good service qualities as the network scales up. In this work, we seek to understand the fundamental issues on the "interplay" (or interaction) between ISPs at different tiers. Although the local ISPs (which we term peers) can communicate with each other by purchasing the connectivity from transit ISPs, there stands an opportunity for them to set up private peering relationships. Under this competitive framework, we explore the issues on 1) the impact of peering relationship; 2) resource distribution; 3) revenue maximization; and 4) condition for network upgrade. First, a generalized model is presented to characterize the behaviors of peers and the transit ISP, in which their economic interests are reflected. We study how a peer can distributively determine its optimal peering strategy. Furthermore, we show how a transit ISP is able to utilize the available information to infer its optimal pricing strategy, under which a revenue maximization is achieved. Two distributed algorithms are proposed to help ISPs to provide a fair and efficient bandwidth allocation to peers, avoiding a resource monopolization of the market. Last, we investigate the above issues in a "many-peers region," that is, when we scale up the network. We provide insightful evidence to show that the ISPs can still gain profits as they upgrade the network infrastructures. Extensive simulations are carried out to support our theoretical claims.

Within the current Internet, autonomous ISPs implement bilateral agreements, with each ISP establishing agreements that suit its own local objective to maximize its profit. Peering agreements based on local views and bilateral settlements, while expedient, encourage selfish routing strategies and discriminatory interconnections. From a more global perspective, such settlements reduce aggregate profits, limit the stability of routes, and discourage potentially useful peering/connectivity arrangements, thereby unnecessarily balkanizing the Internet. We show that if the distribution of profits is enforced at a global level, then there exist profit-sharing mechanisms derived from the coalition games concept of Shapley value and its extensions that will encourage these selfish ISPs who seek to maximize their own profits to converge to a Nash equilibrium. We show that these profit sharing schemes exhibit several fairness properties that support the argument that this distribution of profits is desirable. In addition, at the Nash equilibrium point, the routing and connecting/peering strategies maximize aggregate network profits, encourage ISP connectivity so as to limit balkanization.

Network coding has been shown to be able to improve the throughput of wireless networks. The authors have established fundamental understanding on how the coding scheme works under a realistic physical layer and practical link-scheduling algorithms. In the future, they aim at a complete system solution to incorporate network coding into the MAC and routing protocols, which can achieve higher efficiency in using potential coding opportunities and provide higher throughput. The results can serve as the prototype for future design of wireless networks embracing the network coding technology.

P2P streaming tries to achieve scalability (like P2P file distribution) and at the same time meet real-time playback requirements. It is a challenging problem still not well understood. In this paper, we describe a simple stochastic model that can be used to compare different data-driven downloading strategies based on two performance metrics: continuity (probability of continuous playback), and startup latency (expected time to start playback). We first study two simple strategies: rarest first and greedy. The former is a well-known strategy for P2P file sharing that gives good scalability, whereas the latter an intuitively reasonable strategy to optimize continuity and startup latency from a single peer's viewpoint. Greedy, while achieving low startup latency, fares poorly in continuity by failing to maximize P2P sharing; whereas rarest first is the opposite. This highlights the trade-off between startup latency and continuity, and how system scalability improves continuity. Based on this insight, we propose a mixed strategy that can be used to achieve the best of both worlds. Our algorithm dynamically adapts to the peer population size to ensure scalability; at the same time, it reserves part of a peer's effort to the immediate playback requirements to ensure low startup latency.

There is an increasing number of group-based multimedia applications over the Internet, for example, voice conference or multi-player games. For these applications, it is often necessary to select a strategy to distribute the multimedia streams or mixing the multimedia stream data so as to provide better quality of service (QoS) guarantees. However, there is no appropriate metrics to evaluate the QoS of a group multimedia session, despite abundant literature on how to evaluate the QoS for two-party communication (e.g. MOS, E-Model). In this paper, we propose a new measure which is called the group mean opinion score (GMOS). To leverage on existing work, our definition of GMOS is based on two-party MOS, hence, it can be estimated via measurement of network parameters and fitting these data into the E-Model. We conduct large scale experiments using the latest SKYPE conference software. We first calibrate the GMOS based on the subjective scores of our experiments, then for individual conference sessions, we check whether our approach can pick a server configuration strategy to achieve the best GMOS. The study shows our proposed methodology is very promising and the potential of applying to other group-based applications.

Distributed wireless mesh network technology is ready for public deployment in the near future. However, without an incentive system, one should not assume that private self-interested wireless nodes would participate in such a public network and cooperate in the packet forwarding service. This paper studies the use of pricing as an incentive mechanism for stimulating participation and collaboration in public wireless mesh networks. Our focus is on the "economic behavior" of the network nodes-the pricing and purchasing strategies of the access point, wireless relaying nodes, and clients. We use a "game-theoretic approach" to analyze their interactions from one-hop to multihop networks and when the network has an unlimited or limited channel capacity. The important results that we show are that the access point and relaying wireless nodes will adopt a simple yet optimal fixed-rate pricing strategy in a multihop network with an unlimited capacity. However, the access price grows quickly with the hop distance between a client and the access point, which may limit the "scalability" of the wireless mesh network. In case where the network has limited capacity, the optimal strategy for the access point is to vary the access charge and even interrupt service to connecting clients. To this end, we focus on the access point adopting a non-self-enforcing but more practical "fixed-rate noninterrupted service" model and propose an algorithm based on the Markovian decision theory to devise the optimal pricing strategy. Results show that the scalability of a network with limited capacity is upper bounded by one with an unlimited capacity. We believe that this work will shed light on the deployment and pricing issues of distributed public wireless mesh networks.

AS Path Prepending (ASPP) is a popular method for the inter-AS inbound traffic engineering, which is known to be more difficult than the outbound traffic engineering. Although the ASPP approach has been extensively practised by many ASes, it is surprising that there still lacks a systematic study of this approach and the basic understanding of its effectiveness. In this paper, we introduce the concept, applicability and potential instability problem of the ASPP approach. Some guidelines are given as the first step to study the method to avoid instability problem. Finally, we study the dynamic prepending behavior of ISPs and show a real-world pathologic case of prepending instability based on our measurement study of RouteViews data.

Public-access networks need to handle persistent congestion and overload caused by high bandwidth aggregates that may occur during times of flooding-based DDoS attacks or flash crowds. The often unpredictable nature of these two activities can severely degrade server performance. Legitimate user requests also suffer considerably when traffic from many different sources aggregates inside the network and causes congestion. This paper studies a family of algorithms that "proactively" protect a server from overload by installing rate throttles in a set of upstream routers. Based on an optimal control setting, we propose algorithms that achieve throttling in a distributed and fair manner by taking important performance metrics into consideration, such as minimizing overall load variations. Using ns-2 simulations, we show that our proposed algorithms 1) are highly adaptive by avoiding unnecessary parameter configuration, 2) provide max-min fairness for any number of throttling routers, 3) respond very quickly to network changes, 4) are extremely robust against extrinsic factors beyond the system control, and 5) are stable under given delay bounds.

Jeff.Yan @ ncl.ac.uk Abstract — Massively multiplayer game holds a huge market in the digital entertainment industry. Companies invest heavily in the game and graphics development since a successful online game can attract million of users, and this translates to a huge investment payoff. However, multiplayer online game is also subjected to various forms of hacks and cheats. Hackers can alter the graphic rendering to reveal information otherwise be hidden in a normal game, or cheaters can use software robot to play the game automatically and gain an unfair advantage. Currently, some popular online games release software patches or incorporate anti-cheating software to detect known cheats. This not only creates deployment difficulty but new cheats will still be able to breach the normal game logic until software patches are available. Moreover, the anti-cheating software themselves are also vulnerable to hacks. In this paper, we propose a scalable and efficient method to detect whether a player is cheating or not. The methodology is based on the dynamic Bayesian network approach. The detection framework relies solely on the game states and runs in the game server only. Therefore it is invulnerable to hacks and it is a much more deployable solution. To demonstrate the effectiveness of the propose method, we implement a prototype multiplayer game system and to detect whether a player is using the “aiming robot ” for cheating or not. Experiments show that not only we can effectively detect cheaters, but the false positive rate is extremely low. We believe the proposed methodology and the prototype system provide a first step toward a systematic study of cheating detection and security research in the area of online multiplayer games. I.

In this paper, we propose to model the dynamics of BitTorrent (BT) P2P file sharing systems using the stochastic differential equation method. Unlike previous approach, our method can capture more realistic network environment and peers behavior. Closed-form solutions of various performance measures such as the average number of downloaders, seeders, the system throughput and file downloading time are derived. We also validate our mathematical results via simulation and show that not only our mathematical model can closely track the dynamics of BT-like systems, but the model has a much higher accuracy than previous proposed methods. Also, many important properties can be derived from the close-form solution such as performance scalability, sensitivity of the measurements to various system parameters. We believe the proposed method can provide better understanding in the design and analysis of BT-like P2P systems.

This paper studies the use of pricing as an incentive mechanism to encourage private, self-interested nodes to participate in a public wireless mesh network and cooperate in the packet forwarding service. Our focus is on the "economic behavior" of the network nodes the pricing and purchasing strategies of the access point, wireless relaying nodes, and clients. We use a "game theoretic approach" to analyze their interactions from one-hop to multihop network and when the network has an unlimited or limited channel capacity. We show that the access point and relaying wireless nodes will adopt a simple, yet optimal, fixed-rate pricing strategy in a multi-hop network with an unlimited capacity. Yet, the fixed-rate pricing strategy fails to be optimal in the limited capacity case. To this end, we focus on the access point adopting a more practical "fixedrate, non-interrupted service" model and propose an algorithm based on the Markovian decision theory to devise the optimal pricing strategy.

The Internet is a hierarchical architecture comprising heterogeneous entities of privately owned infrastructures, where higher level Internet service providers (ISPs) supply connectivity to the local ISPs and charge the local ISPs for the transit services. One of the challenging problems facing service providers today is how to increase the profitability while maintaining good service qualities. In this work, we seek to understand the fundamental issues on the "interplay" (or interaction) between ISPs at different tiers. While the local ISPs (which we term peers) can communicate with each other by purchasing the connectivity from transit ISPs, there stands an opportunity for them to set up private peering relationships. Under this competitive framework, we explore the issues on (a) impact of peering relationship, (b) resource distribution and (c) revenue maximization. Firstly, a generalized model is presented to characterize the behaviors of peers and the transit ISP, in which their economic interests are reflected. We study how a peer can distributively determine its optimal peering strategy. Furthermore, we show how a transit ISP is able to utilize the available information to infer its optimal pricing strategy, under which a revenue maximization is achieved. A distributed algorithm is proposed to help ISPs to provide a fair and efficient bandwidth allocation to peers, avoiding a resource monopolization of the market. Extensive simulations are carried out to support our claims.

The BitTorrent (BT) file sharing protocol is popular due to its scalability property and the incentive mechanism to reduce free-riding. However, in designing such P2P file sharing protocols, there is a fundamental "tussle" between keeping peers, specially the more resourceful ones, in the system for as long as possible to help the system achieve better performance and allowing peers finish their download as quickly as possible. The current BT protocol represents only "one" possible implementation in this whole design spectrum. In this paper, we characterize the "complete" design space of BT-like protocols. We use fairness index to measure the fairness that incorporates the contribution peers make. We show that there is a wide range of design choices, ranging from optimizing the performance of file download, to optimizing the fairness measure. More importantly, we show that there is a simple and easily implementable design knob which can be used to choose a particular operating point in the design space. We then discuss different algorithms (centralized versus distributed) in realizing the design knob. We also carry out performance evaluation to quantify the merits and properties of the BT-like file sharing protocols.

File distribution via network coding has received a lot of attention lately. However, direct application of network coding may have security problems. In particular, attackers can inject "faked" packets into the file distribution process to slow down the information dispersal or even deplete the network resource. Therefore, content verification is an important and practical issue when network coding is employed. When network coding is used, it is infeasible for the source of the content to provide all the hash values or signatures required for verification, and hence the traditional "hash-and-sign" methods are no longer applicable. Recently, a new on-the-fly verification technique is proposed by Krohn et al. for rateless erasure codes. However, their scheme requires a large number of hash values to be distributed in advance, and all of them are needed to verify even for a single packet. We propose a new batch delivery and verification scheme that is similar to the classical scenario where the authentication information of a message is embedded with the message and is sufficient for the verification purpose. We investigate how our technique can be applied when random linear network coding is employed, and show that both the computational and the bandwidth overhead can be greatly reduced by using a variant of the random network coding. We further show by simulation that this variant is sufficiently effective in practice.

In this paper, we present the mathematical analysis of two important performance measures for a BitTorrent (BT) like P2P file sharing system, namely, average file downloading time and file availability. For the file downloading time, we develop a model using the "stochastic differential equation" approach, which can capture the system more accurately than some previous approach and can capture various network settings and peers behavior. We study the steady-state behavior and obtain the closed-form solutions for performance measures which allow us to carry sensitivity analysis on various performance measures for various system parameters. We then extend this model to consider multiclass peers wherein some peers are behind firewalls which may impede the uploading service. We also present the mathematical model to study the file availability of a BT-like system. The model helps us gain the understanding of why the "rarest-first" chunk selection policy is used in today's BT protocol. We propose a novel chunk selection algorithm to enhance the overall system file availability. Extensive simulations are carried to validate our analysis

Admission control has been shown to be a preferred alternative to TCP-friendly congestion control for inelastic flows in heterogeneous networks shared by elastic and inelastic traffic [1]. However, it is possible for an inelastic flow to adopt different level of aggressiveness in implementing the admission control. How these different levels of aggressiveness affect the system performance remains an open issue. In this paper, we evaluate a full spectrum of (abstract) admission control algorithms in terms of their aggressiveness towards elastic flows. A totally aggressive version would admit an inelastic flow even if this means elastic flows' fair bandwidth share is reduced to close to zero. In the other extreme, a TCP-friendly version would only admit an inelastic flow if its desired rate is no higher than what the elastic flows will receive after its arrival. We show that the performance of inelastic flows is asymptotically insensitive to their aggressiveness without strong assumptions about flow file size or holding time distributions. This makes a strong case for adopting a less aggressive, yet TCP-friendly admission control in a heterogeneous network. Extensive simulations are carried out to validate the performance, stability and asymptotic behavior the the proposed TCP-friendly admission control policy.

The connectivity between millions of nodes on the Internet is provided by the interconnection of many ISPs' networks. These ISPs, in their decisions to peer with each other, define a set of transit relationships. These transit relationships are the primary factors that dictate how traffic flows through the Internet. BGP-based inter-domain routing that implements these transit relationships can be considered economically efficient. The advent of peer-to-peer (P2P) applications and overlay networks, however, changes the rules by providing traffic routing favoring the applications' needs. This can lead to reduced economic efficiency and upset the ISPs' business model. In this paper, we propose simple models to represent P2P traffic demand, peering and routing in a market place of two competing ISPs to illustrate this tussle of the Internet. Based on these models, we also propose and investigate alternative peering and provisioning strategies available to the ISPs and analyze their effectiveness

Flow-level traffic measurement is required for a wide range of applications including accounting, network planning and security management. A key design challenge is how to gracefully deal with traffic surges that exhaust the resources (memory, export bandwidth or CPU) of the flow monitor. A standard solution is to do sampling (look at one out of every n packets). This is implemented in Cisco’s Netflow, a popular platform. Setting the sampling rate according to the normal traffic, however, cannot avoid overrunning available memory for flow records during abnormal situations, such as when there is a DoS attack or other security breaches. Currently available countermeasures have their own problems: (1) reject new flows when the cache is full - some legitimate new flows will not be counted; (2) export not-terminated flows to make room for new ones - this will exhaust the export bandwidth; (3) adapt the sampling rate to traffic rate - this will reduce the overall accuracy of accounting, including legitimate flows. In this paper, we propose a new counter-measure to deal with abnormal traffic conditions - adaptive flow aggregation. Often the reason for abnormal traffic conditions is due to security attacks. Fortunately, such attacks usually have some common patterns. For example, packets of DoS attacks have the same destination IP address, while traffic for worm spreading has the same source IP address. Our flow monitoring algorithm identifies these traffic clusters in real-time and aggregates these large amount of short flows into a few flows.

Distributed denial-of-service attack is one of the most pressing security problems that the Internet community needs to address. Two major requirements for effective traceback are (i) to quickly and accurately locate potential attackers and (ii) to filter attack packets so that a host can resume the normal service to legitimate clients. Most of the existing IP traceback techniques focus on tracking the location of attackers after-the-fact. In this work, we provide an efficient methodology for locating potential attackers who employ the flood-based attack. We propose a distributed algorithm so that a set of routers can correctly (in a distributed sense) gather statistics in a coordinated fashion and that a victim site can deduce the local traffic intensities of all these participating routers. We prove the correctness of our distributed algorithm, and given the collected statistics, we provide a method for the victim site to locate attackers who sent out dominating flows of packets. The proposed distributed traceback methodology can also complement and leverage on the existing ICMP traceback so that a more efficient and accurate traceback can be obtained. We carry out simulations to illustrate that the proposed methodology can locate the attackers in a short period of time. Moreover, the applications as well as the limitations of the proposed methodology are covered. We believe this work also provides the theoretical foundation on how to correctly and accurately perform distributed measurement and traffic estimation on the Internet.

We propose a Probabilistic Preemptive Burst Segmentation (PPBS) scheduling scheme to provide priority classes with different Quality-of-service (QoS) requirements in WDM Optical Burst Switching (OBS) networks. The PPBS scheme enables high priority bursts to preempt and segment low priority bursts in a probabilistic fashion. The PPBS scheme achieves 100% isolation among priority classes, and burst loss probabilities can be controlled by tunable parameters. Our PPBS queueing model also implicitly enables us to obtain several results related to the Erlang's loss function which may be useful in the role of this function arising in some areas of queueing theory, as well as characterizing a loss rate region that work conserving burst scheduling techniques can achieve. As an application to providing service differentiation, we show how the PPBS scheme can minimize the total sum of loss rates and achieve proportional loss differentiation. Finally, we also demonstrate the effectiveness of the PPBS scheme empirically using realistic Internet traffic model, e.g., long range dependent traffic model.