Continual forgetting task aims to continuously remove multiple target knowledge subsets from pre-trained models while maintaining the integrity of remaining knowledge. Existing methods suffer from both incomplete forgetting of target knowledge and unintended forgetting of indistinguishable remaining knowledge. To address these challenges, we propose the forgetting knowledge localization and isolation for continual forgetting in pre-trained vision models which precisely forgets target knowledge while reducing over-forgetting of remaining knowledge. To achieve precise forgetting, we first propose the forgetting knowledge layer localization to explore layers in the model which are more related to forgetting knowledge. Then, we design the forgetting knowledge parameter isolation to isolate the parameters sensitive to forgetting knowledge in these selected layers, mitigating over-forgetting of remaining knowledge. Finally, we fine-tune these isolated parameters and freeze the remaining parameters to achieve efficient forgetting while maintaining high performance on retained datasets. Extensive experimental results demonstrate that our method achieves superior performance over state-of-the-art methods across multiple continual forgetting tasks.

The multiple-unicast conjecture asserts that network coding offers no throughput advantage over routing in undirected networks. Its validity is known to imply fundamental lower bounds in computational complexity. We propose a Session Interaction Framework that reduces the conjecture to a central equivalence: the conjecture holds universally if and only if every irreducible core is independent. This result transforms the global feasibility problem into a two-stage process. First, to make the reduction phase tractable, we provide simplified sufficient conditions for session dominance, offering geometric criteria to iteratively simplify complex session sets. Second, for the remaining "irreducible core," we propose a Session Decoupling Theorem, reducing the conjecture's validity for a session set to its independent subsets. Topologically, we prove that sessions separated by high-cost cuts or cut-vertices are guaranteed to be independent. By integrating these reduction and decomposition mechanisms, our framework offers a systematic methodology to verify the conjecture across general network topologies.

Salient object detection (SOD) aims to mimic human visual perception by identifying the most eye-catching objects within a scene, and has remained a popular research topic for many years. The introduction of thermal (T) images offers additional information for challenging scenarios such as those with low light and complex backgrounds, and thus enhance performance when combined with RGB images. In this paper, we have, to the best of our ability, conducted the first comprehensive survey of dual-modality RGB-T SOD. We summarize and categorize published RGB-T SOD models, emphasizing their characteristics and features. Important components of these models are classified and elaborated, such as feature extraction, modality fusion, and loss function design. Following this, we analyze existing RGB-T SOD datasets and evaluation metrics. We evaluate a selection of representative SOD models using unified protocols and statistical analysis. We also present comparative experiments on the impact of the choice of loss function and the usage of datasets on performance. Finally, we consider several key issues and potential solutions in RGB-T SOD research, revealing promising directions for future efforts. We hope this survey will offer an effective way to understand the current state of the technology and, more importantly, stimulate discussion within the community.

Network coding (NC) has proven to offer significant benefits in long-distance and broadcast transmissions, enhancing both throughput and energy efficiency. Recent studies have incorporated partial packet recovery (PPR) into packet-level NC, using syndromes from coded packets to correct bit errors and thereby reduce completion delay. Motivated by recent breakthroughs in deep learning, this paper introduces a novel neural networkbased decoding framework for packet-level NC, referred to as Learned-PPR. The proposed framework incorporates a Bilateral Efficient Self-Attention Network (Bi-ESANet) architecture, which leverages a bilateral network structure to effectively capture both inter- and intra-packet information. Furthermore, we introduce an ESA module to mitigate the GPU memory overhead compared with traditional Transformer attention modules. To handle rateless NC, we propose a “rateless masking” training strategy that enables efficient decoding of rateless codes within the Bi-ESANet framework. Simulation results across various transmission scenarios demonstrate that the proposed approach significantly outperforms existing PPR schemes, achieving lower completion delay. Specifically, compared to existing methods, the proposed approach reduces completion delay by more than 25%. However, the introduced framework incurs higher computational complexity due to the integration of the Bi-ESANet architecture.

Artificial Intelligence-Generated Content (AIGC) has been gaining significant traction for automatic generation of diverse content. Due to the GPU-intensive generation process and the high costs associated with purchasing and operating GPUs, users often prefer to submit requests to a nearby edge cloud, maintained by an AIGC cloud service provider. Efficiently scheduling AIGC requests in the edge cloud faces non-trivial challenges. First, AIGC requests emphasize the quality of generated content, yet conventional scheduling algorithms often overlook this aspect. Second, when the volume of incoming requests exceeds the capacity of the cloud, the AIGC service provider needs to select appropriate requests to execute, which is further complicated by the online arrival pattern of requests and the constraints imposed by request deadlines. Third, users dynamically submit multiple requests at different times. To manage costs, each user operates within a pre-allocated budget for a given time period. For the AIGC cloud service provider, it is highly non-trivial to identify valuable requests and judiciously balance different user budgets. To tackle the above challenges, we target the online AIGC request scheduling problem with the new objective of maximizing the overall content generation quality. We first conduct real experiments to establish the quality model between inference steps and the quality of generated content. Then, based on this quality model, we formulate the problem into an integer linear program, which is proven NP-hard. Under a primal-dual framework, we carefully design the update of multiple dual variables, to flexibly control the consumption of edge resources and user budgets. We rigorously analyze the performance of the proposed algorithm and prove a theoretical performance guarantee on its competitive ratio. Extensive real-world trace-driven experiments manifest that our proposed method improves the state-of-the-art by up to 25.3% in overall content generation quality.

Vision Transformers (ViTs) have experienced significant progress and are quantized for deployment in resource-constrained applications. Quantized models are vulnerable to targeted bit-flip attacks (BFAs). A targeted BFA prepares a trigger and a corresponding Trojan/backdoor, inserting the latter (with RowHammer bit flipping) into a victim model, to mislead its classification on samples containing the trigger. Existing targeted BFAs on quantized ViTs are limited in that: (1) they require numerous bit-flips, and (2) the separation between flipped bits is below 4 KB, making attacks infeasible with RowHammer in real-world scenarios. We propose a new and practical targeted attack Flip-S against quantized ViTs. The core insight is that in quantized models, a scale factor change ripples through a batch of model weights. Consequently, flipping bits in scale factors, rather than solely in model weights, enables more cost-effective attacks. We design a Scale-Factor-Search (SFS) algorithm to identify critical bits in scale factors for flipping, and adopt a mutual exclusion strategy to guarantee a 4 KB separation between flips. We evaluate Flip-S on CIFAR-10 and ImageNet datasets across five ViT architectures and two quantization levels. Results show that Flip-S achieves attack success rate (ASR) exceeding 90.0% on all models with 50 bits flipped, outperforming baselines with ASR typically below 80.0%. Furthermore, compared to the SOTA, Flip-S reduces the number of required bit-flips by 8×-20× while reaching equal or higher ASR. Our source code is publicly available1.

Campus networks constitute an important component of today's Internet. Service resources in campus networks have different security protection requirements, while campus users have different access requirements for these resources. Monotonous security access control rules inevitably lead to substantial waste of network bandwidth and service resources. In this work, we divide resources within a campus network into regions. Based on the list of resources that users are permitted to access and predefined attributes indicating resource importance, hierarchical and multi-grained access control flow tables are issued to access switches through OpenFlow, taking a Software-Defined Networking (SDN) approach. It enables precise user access control to specific resources. Furthermore, a hierarchical Multi-granularity Flow Authorization Tag Access Control (HMFAT) system for multifunctional modules is designed. Extensive experiments have demonstrated that HMFAT can authenticate new hosts within 1.217 ms and mitigate malicious traffic attacks such as source address spoofing and identity tampering. It exhibits a higher level of security and agility than existing SDNbased authentication systems.

Distributed large model training is intensively time and resource consuming. Failures during the long training period are often inevitable, and can incur substantial recovery costs. Checkpointing has been the standard fault tolerance approach, which periodically stores the latest model states at remote persistent storage. This process can be time-consuming due to limited network bandwidth, and adversely affects training throughput. In-memory checkpointing addresses this issue by saving checkpoint data into host memory instead of remote storage. However, host memory is non-persistent, and may not provide sufficient resilience in case of machine failure. We propose ECCheck, a novel in-memory checkpoint system that employs erasure coding to enhance fault tolerance in distributed deep neural network training. ECCheck advocates serialization-free encoding and decoding in model checkpointing. Several techniques are proposed to minimize computation and communication overhead incurred by erasure coding. Extensive experiments demonstrate that ECCheck achieves superior fault tolerance compared to state-of-the-art solutions, while maintaining high checkpointing frequency, low checkpointing stalls, and fast recovery from failures.

The multiple-unicast network coding conjecture states that network coding is equivalent to routing for multiple unicast sessions in an undirected network. Despite its seemingly simple and intuitive nature, this conjecture has remained unresolved since its introduction over two decades ago [1], [2], and stands as a well-known open problem in the field of network coding. Recent advances in theoretical computer science further reveal its connection to fundamental open problems in complexity lower bounds. In this work, we address the conjecture from the perspective of space information flow, a paradigm that studies information transmission in geometric spaces [3] [5], aiming to minimize the bandwidth-distance product (network volume) while meeting communication demands between terminals. Our main result demonstrates that network coding is indeed equivalent to routing in$l_{p}^{n}$spaces for$1 \leq p \leq 2$. Specifically, we provide: (1) a proof of the case$1 \leq p<2$, and (2) a new proof of the case$p=2$. This result partially verifies the original conjecture, while suggesting a possible direction for an eventual proof of the conjecture.

In this work, we introduce a new framework of linear network coding (LNC) schemes called two-dimensional (2D) vector LNC, which subsumes conventional (1D) vector LNC as a special case. The new framework models every data unit as an$L_{1} \times L_{2}$matrix, enabling a new encoding dimension so that data units can be coded along both row and column dimensions. Compared with (1D) vector LNC of block length$L_{1} L_{2}, L_{1} \times L_{2}$2D vector LNC not only reduces the size of local encoding kernels from$L_{1} L_{2} \times L_{1} L_{2}$to$L_{1} \times L_{1}$and$L_{2} \times L_{2}$, but also exhibits greater scalability in the selection of local encoding kernels. In addition, we prove an equivalence between the linear solvability of$L_{1} \times L_{2}$2D vector LNC and (1D) vector LNC of block length$L_{1} L_{2}$. Under the framework of 2D vector LNC, we further formulate 2D circular-shift-based LNC. For distinct odd primes$L_{1}$and$L_{2}$, we prove that a network has a (1D) circular-shift-based linear solution of block length$\left(L_{1}-1\right)\left(L_{2}-1\right)$if and only if it has an$\left(L_{1}-1\right) \times\left(L_{2}-1\right)$2D circular-shift-based linear solution. We also demonstrate through an explicit example that, compared with a (1D) circular-shift-based linear solution of block length 8, a$2 \times 4$2D circular-shift-based linear solution requires 23 % fewer XORs in the coding process at intermediate nodes and 13 % fewer XORs in the decoding process.

Matrix representation of the finite field GF(pm) represents elements in GF(pm) by m × m matrices over GF(p) so that the arithmetic of GF(pm) can be interpreted as the arithmetic among matrices over GF(p). It is a commonly used method to transform a (scalar) linear operation over GF(pm) into a vector linear operation over GF(p)m, and has been practically adopted by several coding libraries to implement maximum distance separable (MDS) codes over GF(pm). Previous construction of matrix representation of GF(pm) stems from the companion matrix of an irreducible polynomial over GF(p). In this paper, we introduce a new approach to construct matrix representation denoted by $\mathcal{B}$ based on the cyclic permutation matrix C, and prove the isomorphism between $\mathcal{B}$ and GF(pm). As every matrix in B can be expressed in the form of Gf (C)H with carefully designed matrices G and H over GF(p) and a polynomial f(x) over GF(p), we further show that the maximum number of nonzero terms in f(x) can be potentially reduced from m. By utilizing this property, we demonstrate that the computational complexity of the linear coding process based on matrix representation $\mathcal{B}$ can be reduced compared with the one based on standard matrix representation, and the reduction rate is up to 13.47% among the instances illustrated in this paper.

Most well-known constructions of (N,n,d) maximum rank distance (MRD) codes rely on the arithmetic of ${\mathbb{F}_{{q^N}}}$, whose increasing computational complexity with larger N hinders parameter selection and practical implementation. In this work, based on circular-shift operations, we present an efficient construction of (J,n,d) MRD codes over ${\mathbb{F}_q}$ with n ≤ mL, where q is prime, L is a positive integer satisfying gcd(q,L) = 1, mLdenotes the multiplicative order of q modulo L and J equals to the Euler’s totient function of L. The proposed construction is performed entirely over ${\mathbb{F}_q}$ and avoids the arithmetic of ${\mathbb{F}_{{q^J}}}$. We prove that under some parameter settings, the constructed MRD codes are equivalent to a generalization of Gabidulin codes obtained by summing and concatenating several (mL,n,d) Gabidulin codes. In this sense, the constructed MRD codes differ from conventional Gabidulin codes. In the special case J = mL, we prove that every (mL,n,d) circular-shift-based MRD code coincides with an (mL,n,d) Gabidulin code. Last, when q = 2, L is prime and n ≤ mL, it is analyzed that generating a codeword of the proposed (L −1, n,d) MRD codes requires O(nkL) XOR operations, while generating a codeword of (L −1, n,d) Gabidulin codes, based on customary construction, requires O(nkL2) XOR operations.

We study edge computing networks with heterogeneous processors (CPUs, GPUs, FPGAs) integrated into selected routers to enable in-network computing via IPv6-SRv6. This supports application-defined compute-and-forward operations, especially for video streaming tasks like replication, encoding, and transcoding at the edge. To manage limited compute and bandwidth resources, we model the system as an online social welfare maximization problem. Our solution includes: (1) a compact exponential algorithm transforming algebraic constraints into geometric ones; (2) a primal-dual approach using multiround auctions; and (3) a dual oracle leveraging network coding for multicast optimization. Simulations show a 61.2% improvement in social welfare over benchmarks, validating efficient, infrastructure-compatible resource coordination under dynamic workloads.

We are witnessing more real-time network applications that demand high transmission reliability and low delay, for meeting desired Quality of Experience (QoE). Forward Error Correction (FEC) is widely employed to combat packet loss, but its effectiveness depends on accurate packet loss rate prediction. Existing forecasting models exhibit limitations in handling multiperiodicity and complex variations, particularly in terms of trend prediction consistency and forecasting conservativeness, leading to suboptimal performance of FEC strategies. To address these challenges, we propose FitFEC, a Multi-Scale Dynamic Adjustment Transformer that enhances packet loss prediction and optimizes FEC strategies. FitFEC integrates Adaptive Frequency Analysis for capturing periodic components, Trend-Detail Decomposition Transformer for improving trend accuracy, and Dynamic Prediction Adjustment to control prediction aggressiveness. Furthermore, we implement an FEC scheme based on QUIC to further enhance transmission efficiency. Extensive empirical studies demonstrate that FitFEC improves trend prediction accuracy, reduces retransmission rates, and reduces transmission latency, ultimately enhancing network performance and user experience.

Dynamic resource partitioning in multi-UAV (unmanned aerial vehicle) networks enables flexible, task-oriented allocation of resources. Existing approaches pose scalability challenges in jointly optimizing multi-type tasks while satisfying operational constraints. Traditional heuristic and integer programming-based solutions fail to coordinate heterogeneous task allocation, UAV deadline constraints, and hierarchical bandwidth quotas, leading to suboptimal welfare in dynamic environments. In this work, we investigate the problem of quality of service (QoS)-aware resource allocation in UAV networks, with the objective of maximizing social welfare. We design an online primal-dual algorithm to dynamically assign UAVs to tasks based on marginal prices. Our reformulated integer program captures UAV travel constraints, bidding prices, and task-specific bandwidth quotas alongside shared resource capacities. A complementary slackness-based dual framework guides real-time decision making on task acceptance and resource usage, with duality analysis establishing a 1-to-1 correspondence between dual solutions and primal allocations. Experimental results demonstrate 15 % welfare improvement compared to static allocation baselines.

AIGC-as-a-Service (AaaS) enables diverse and high-quality content creation. Due to the computational intensity and high costs of model inference, efficiently scheduling generation requests is non-trivial for AIGC Service Providers (ASPs). A judicious balance is required between generation quality, limited resources, and service delay, while coping with online arrivals and operational constraints. Existing scheduling systems often neglect the quality metrics of generated content, and fail to deploy the latest architecture in model inference. To address these challenges, we introduce a distributed diffusion framework that reduces resource consumption by sharing inference steps across different inference tasks. On this basis, we establish a quality model using the refined CLIP Score, and formulate the scheduling problem as a mixed-integer nonlinear program. We first develop a prompt similarity-based algorithm to determine the number of shared inference steps within each request group. Adopting a primal-dual framework, we then design an online algorithm to dynamically manage request admission and scheduling, maximizing social welfare of the AIGC ecosystem while ensuring generation quality. Extensive real-world trace-driven experiments demonstrate that our approach improves social welfare by up to 38.2% compared to the state-of-the-art method.

In maritime navigation, vessels require internet access for communication and entertainment, typically provided by terrestrial-based stations via relay. For routes that are difficult to cover from the shore, long-endurance Unmanned Aerial Vehicles (UAVs) can be deployed to accompany ships and offer Internet connection. However, existing systems consider Internet Service Provider (ISP) competition only, and do not incorporate it into the users' resource selection process. Furthermore, user competition is limited due to the time slot allocation method. To address these limitations, we propose an effective Online Maritime Double Auction Mechanism (OMDAM) aimed at maximizing social welfare of the maritime network. We introduce an online algorithm,$A_{online}$, to solve the online social welfare maximization problem, with an inner algorithm,$A_{core}$, handling the selection of Internet accessing devices and task allocation between users and ISPs. Theoretical analysis demonstrates that our mechanism ensures budget balance, individual rationality, and economic efficiency. Simulation results show a performance improvement of up to 17% in social welfare compared to prior art.

We study resource allocation and task scheduling for mobile artificial intelligence generated content (AIGC) in a three-layer cloud-edge-device network. Escalating industry demand for computational resources presents significant challenges in resource allocation and optimization, particularly for edge-side AIGC, which faces high computational costs and requires advanced techniques for efficient model deployment on mobile devices. Optimal resource allocation in mobile AIGC networks is naturally formulated into a 0-1 ILP, which is proven NP-hard. We reformulate the problem into both its Comp-Exp and dual forms. Then, we design an online auction framework online AIGC task scheduling (OATS) to optimize decisions on instances and time schedules, maximizing social welfare for the AIGC ecosystem. Our analysis demonstrates that OATS achieves high social welfare through appropriate bid acceptance and resource allocation. Simulation results corroborate the theoretical analysis, showcasing the efficacy of our online algorithms.

Row-Diagonal-Parity (RDP) codes and EVENODD codes are classical systematic array codes and most attention in the literature has been on the generalization of RDP codes. In this work, as generalization of not only RDP codes but also EVENODD codes, we present new construction of$\phi (L)$-dimensional$(k+r, k)$systematic array codes with$r \leq 4$, where L is an odd integer and$\phi (L)$represents the Euler’s totient function of L. We explicitly characterize sufficient conditions on the selection of L to make the codes maximum distance separable (MDS). Compared with EVENODD codes and RDP codes, the largest k that can be supported by the new codes is nearly doubled, and the asymptotic encoding complexity of the new codes is same, that is, asymptotically approaches r XORs per original data bit with increasing L and k. Moreover, for prime L,$r = 2$and$k = 2L-3$, the new code exactly achieves the optimal encoding complexity. For the case$r = 4$, the largest k that can be supported by the new codes is larger than the recently proposed so-called Variants of Extended Shortened Independent-Parity (V-ESIP) systematic array code in a number of code dimension selections, and meanwhile, the obtained explicit conditions on L to guarantee the MDS property of the new codes also apply to classical EVENODD codes and RDP codes, but are more general than well known explicit ones in the literature. The decoding process of the new array codes is also discussed. In particular, the$r\times r$block inverse matrix involved in decoding is explicitly characterized, which applies to all MDS array codes generalized from RDP or EVENODD codes in the literature.

Video compression artifacts arise from quantization applied in the frequency domain. Video quality enhancement aims to reduce such compression artifacts and reconstruct a visually pleasant result. While existing methods effectively reduce artifacts in the spatial domain, they often overlook the rich frequency domain information, especially in addressing multi-scale compression artifacts. This work introduces a frequency-domain upsampling strategy within a multi-scale framework, specifically designed to focus on high-frequency details rather than simply blending neighboring pixels during the upsampling process. Our proposed hierarchical frequency-based upsampling and refinement neural network (HFUR) consists of two modules: implicit frequency upsampling (ImpFreqUp) and hierarchical and iterative refinement (HIR). ImpFreqUp exploits the DCT-domain prior derived through an implicit DCT transform, and accurately reconstructs the DCT-domain signal via a coarse-to-fine transfer. Additionally, HIR is introduced to facilitate cross-collaboration and information compensation between the scales, further refining the feature maps and promoting the visual quality of the final output. We demonstrate the effectiveness of the proposed modules via ablation experiments and visualized results. Experimental results demonstrate that HFUR outperforms the state-of-the-art methods up to 0.13dB/0.17dB on both constant bit rate and constant QP modes. The code is available athttps://github.com/zqqqyu/HFUR.

Outdoor billboard advertising has proven effective for commercial promotions, attracting potential customers, and boosting product sales. Auction serves as a popular method for leasing billboard usage rights, enabling a seller to rent billboards to winning users for predefined periods according to their bids. An effective auction algorithm is of great significance to maximize the efficiency of the billboard ecosystem. In contrast to a rich literature on Internet advertising auctions, well-crafted algorithms tailored for outdoor billboard auctions remain rare. In this work, we investigate the problem of outdoor billboard auctions, in the practical setting where bids are received and processed on the fly. Our goal is to maximize social welfare, namely the total benefits of auction participants, including the billboard service provider and the bidding users. To this end, we first formulate the billboard social welfare maximization problem into an Integer Linear Problem (ILP), and then reformulate the ILP into a compact form with a reduced size of constraints (at the cost of involving exponentially many primal variables), based on which we derive the dual problem. Furthermore, we design a dual oracle to handle the exponentially many dual constraints, avoiding exhaustive enumeration. We present a primal-dual online algorithm with an incentive-compatible pricing mechanism. Theoretical analysis proves the individual rationality, incentive compatibility, and computational efficiency of our online algorithm. Extensive experimental results show that the online algorithm is both effective and efficient, and achieves a good competitive ratio.

Large language models (LLMs) have demonstrated remarkable capabilities and have been extensively deployed across various domains, including recommender systems. Prior research has employed specialized prompts to leverage the in-context learning capabilities of LLMs for recommendation purposes. More recent studies have utilized instruction tuning techniques to align LLMs with human preferences, promising more effective recommendations. However, existing methods suffer from several limitations. The full potential of LLMs is not fully elicited due to low-quality tuning data and the overlooked integration of conventional recommender signals. Furthermore, LLMs may generate inconsistent responses for different ranking tasks in the recommendation, potentially leading to unreliable results. In this article, we introduce Ranker for top- k Recommendations (RecRanker), tailored for instruction tuning LLMs to serve as the Ranker for top- k Recommendations. Specifically, we introduce importance-aware sampling, clustering-based sampling, and penalty for repetitive sampling for sampling high-quality, representative, and diverse training data. To enhance the prompt, we introduce a position shifting strategy to mitigate position bias and augment the prompt with auxiliary information from conventional recommendation models, thereby enriching the contextual understanding of the LLM. Subsequently, we utilize the sampled data to assemble an instruction-tuning dataset with the augmented prompts comprising three distinct ranking tasks: pointwise, pairwise, and listwise rankings. We further propose a hybrid ranking method to enhance the model performance by ensembling these ranking tasks. Our empirical evaluations demonstrate the effectiveness of our proposed RecRanker in both direct and sequential recommendation scenarios. 1

In times when ground infrastructure can be disrupted by conflicts or natural events, the use of Unmanned Aerial Vehicle (UAV) trajectories for network services has become a crucial backup plan. Yet, many current methods don't fully optimize how UAVs are scheduled or allocate resources, resulting in less effective service. Our research aims to enhance social welfare by optimizing UAV scheduling and trajectory planning. To tackle this challenging problem, we first set up a non-convex linear programming issue and then restructure it into both its exponential and dual forms. We introduce a two-part solution. The$A_{OST}$algorithm manages task bids and UAV resource allocation, considering factors like bid values, resources, and task needs. It ranks tasks based on the value they bring. Next, the$A_{dual}$algorithm refines decisions on tasks and UAV planning by weighing task costs against benefits. Our analysis shows our method reaches a balance that boosts social welfare, ensuring the best task and resource decisions. Tests back up these claims, showing improvement in network service, and proving our method's practical value in maximizing social welfare during disruptions.

Fine-tuning pre-trained models with task-specific data can produce customized models effective for downstream tasks. However, operating large-scale such fine-tuning tasks in real time in the data center faces non-trivial challenges, including unpredictable task arrival and system environment dynamics, complex deadline-driven fine-tuning scheduling, and intertwined task pricing and cost management. In this paper, targeting the popular Low-Rank Adaptation (LoRA) fine-tuning technique, we present the design and study of a novel auction-based mechanism to jointly schedule and price LoRA tasks in an online manner. We first model the social welfare maximization problem as an integer program for the fine-tuning service provider, capturing all the aforementioned challenges. Then, to solve this NP-hard problem online, we equivalently reformulate this original problem into a schedule selection problem, where each schedule corresponds to a concrete pre-specified operation plan over time for a task. We can thus design a polynomial-time online approximation algorithm via the online primal-dual method to determine the schedule, and with the dual variables, also determine the pricing for each admitted task. We rigorously prove the competitiveness of our online approach against the offline optimum, and prove the economic properties of truthfulness and individual rationality regarding pricing. Finally, we conduct extensive experiments and have validated the substantial advantages of our approach compared to existing methods.

This work explores a Personalized Federated Learning (PFL) system with a central server, multiple edges and clients. Edges contain significant data distribution diversity and data scarcity. We design an auction-based online algorithm for dynamically selecting clients, who are motivated to connect with edges for model serving and participate in training for rewards. Our auction focuses on bids for model service usage, yet incorporates a reward mechanism to compute social welfare. This approach fosters enhanced collaboration between clients and edges. Through extensive simulation, we demonstrate that our algorithm substantially improves the usage of model serving requests from clients, showing an increase in social welfare with a low competitive ratio. The personalized models benefit from clients’ computational contributions and diverse datasets, while outperforming conventional FL frameworks in model accuracy. Our contributions offer a scalable, practical solution to PFL challenges, ensuring improved model performance and client engagement in a data-sensitive, reward-driven context.

Scheduling generative-AI jobs in the edge computing environment faces multiple non-trivial challenges, including the Directed Acyclic Graph (DAG) dependency among tasks, the intrinsic intertwinement between task scheduling and model selection, and the dynamic unpredictable arrival of job DAGs. In this work, we capture all such challenges and formulate a non-linear integer program to optimize the long-term profit of the generative-AI service provider, i.e., service revenue of the admitted jobs minus system costs of executing the tasks contained in such job DAGs. This problem is NP-hard even in the offline setting. To solve it, we first reformulate it into an equivalent schedule selection problem using generated schedules to tackle complex constraints. Then, we design a new online scheduling method through the online primal-dual technique. Experimental results confirm that our approach can increase the total service profit by up to 41.2% compared to existing algorithms.

Forward Error Correction (FEC) is the preferred method for recovering lost packets in time-sensitive applications. The key for FEC to recover lost packets successfully is whether the number of redundant packets is sufficient. Due to imperfect loss prediction algorithms, existing FEC schemes, which set the number of redundant packets according to the prediction results, make transport service providers likely to fall into the awkward situation of either failing to recover lost packets or wasting a large amount of bandwidth. In this work, we propose P-FEC, an FEC scheme that can take SLA into consideration and empirically achieve the targeted decoding success rate while minimizing bandwidth waste. P-FEC combines intra- and inter-generation coding to balance decoding success rate and bandwidth waste, in which intra-generation provides quick but conservative recovery and inter-generation coding provides delayed but more efficient loss recovery services. We future profile the loss prediction errors to derive cumulative distribution functions of the errors for diverse network conditions, and then determine the parameters of intra- and inter-generation coding according to these distribution functions. The real-world transmission experiments empirically demonstrate that P-FEC can achieve the targeted decoding success rate while its bandwidth waste is only 1%-16% of the FEC with the code rate that can theoretically guarantee the target success rate. Furthermore, P-FEC can work well with computation light-weighted prediction algorithms although these algorithms have low accuracy, which makes it extremely useful for the transmission environment with limited computing resources.

Current data centers rely on failure protection mechanisms to ensure data reliability. However, recent research indicates that failures within the same node or rack are common in data centers that use flash-based solid-state drives (SSDs) as the primary storage medium. Such correlated failures bring challenges for traditional protection mechanisms to achieve high reliability and repair performance. To this end, we propose a product erasure code (PECode) that encodes data blocks in multiple stripes cooperatively to generate intrastripe and interstripe parity blocks. Then, we design a multistripe cooperative repair algorithm (MSCRepair). MSCRepair first creates the failure distribution matrix (FDM) to represent the distribution of failure blocks in nodes and racks, and then conducts FDM-guided repair to minimize cross-rack traffic upon correlated failures. We prove that MSCRepair achieves the least cross-rack repair traffic at the cost of a longer repair time. We further propose a correlated failure repair scheduling algorithm for MSCRepair, which reduces the repair time by balancing the load and delivering data from links with higher bandwidths. We evaluate MSCRepair through both large-scale simulations and real experiments. In the mise-en-scene of its state-of-the-art alternatives, MSCRepair stands out by reducing up to 19.6%–49.9% of cross-rack traffic, while simultaneously reducing 16.2%–51.4% of recovery time of correlated failures.

Erasure coding is a storage-efficient redundancy scheme for modern key–value (KV) stores, storing stripes of data and parity chunks in multiple nodes. To accommodate the highly skewed and time-varying nature of the workload, KV stores require erasure code that dynamically optimizes its parameters, known as redundancy converting. Stretched Reed–Solomon (SRS) and elastic Reed–Solomon (ERS) codes represent promising candidates for meeting such requirements. However, both SRS and ERS are limited to RS$(d,r)\to $RS$(d^{\prime },r^{\prime })$converting, where$d^{\prime }>d,r^{\prime }=r$, failing to fully meet actual needs. This work presents an advanced ERS code (AERS code), which builds upon flexible encoding matrices and placement strategies, serving different types of redundancy converting, and minimizing converting traffic. We further prove that the AERS code is an optimal redundancy converting solution that achieves the theoretical lower bound on data traffic during redundancy converting while guaranteeing node-level fault tolerance. We evaluate the AERS code through both mathematical analysis and experiments. In the mise-en-scène of its state-of-the-art alternatives, AERS stands out by reducing network traffic up to 50%–85.7% while accelerating redundancy converting.

This work studies video transcoding and multicast in an edge computing network (ECN), where routers are furnished with computing resources. For example, the recent IPv6-SRv6 paradigm enables programmable networking that works in concert with such hardware innovations, provisioning application-defined route selection and realizing compute&forward functionalities. A prominent class of user applications in ECN is video streaming. Edge routers may replicate and transcode video streams while delivering them toward end users for customized services, up to node processing and link transmission capacities. We design an auction-based online optimization framework DOP, which comprises of three components: 1) video access management; 2) dynamic price function design; and 3) transcoding multicast tree (TMT) optimization. We formulate the online social welfare maximization problem, and design an efficient primal-dual framework that simultaneously makes video transcoding, multicast routing, and resource pricing decisions. Through rigorous theoretical analysis, we prove DOP guarantees truthfulness and achieves a good competition ratio. Extensive simulations further verify that social welfare increases by about 12.9%, in comparison to benchmark algorithms.

Hierarchical federated learning (HFL) has recently emerged as a more practical machine learning (ML) paradigm, which enables edge servers (ESs) in close proximity to conduct partial model aggregation. Despite its utility, local training and model aggregation incur considerable computation and communication time. client selection (CS) has proven effective for minimizing latency. However, CS faces the following challenges in hierarchical federated learning (HFL). First, the accessible clients, computation resources and network bandwidth are time-varying and unpredictable. Second, certain dynamics can only be observed after the decisions are made. Third, multiple ESs face different unknown clients, increasing the difficulty of selecting clients in an online manner. Finally, resource usage may be excessively violated during the training process. Existing HFL researches are insufficient to tackle these challenges. This work proposes a multi- ESs CS framework (MCS), which is based on multiarmed bandit (MAB) technique. MCS aims to reduce the cumulative computation and communication time, using two algorithms: 1) an online learning-based CS algorithm (OCA) makes the CS decisions for each ES, based on empirical learning results; and 2) a randomized rounding algorithm (RRA) converts fractional decisions obtained by OCA into binary solutions. Theoretically, MCS can enjoy the sublinear regret and violation compared to the optimal strategy. Practically, extensive experiments on real-world data sets demonstrate the empirical superiority of MCS over multiple state-of-the-art algorithms in minimizing cumulative latency.

Large-scale distributed machine learning (ML) systems involve extensive and costly computational resources. Pricing and scheduling, as two promising techniques for resource management, have garnered significant attention. However, existing job pricing and scheduling algorithms in cloud computing either charge fixed resource fees based on known job runtime or implement dynamic price setting with job preemption, unsuitable for distributed ML systems with high uncertainties and switching cost. First, whether the resources of a distributed ML job are placed together or not results in different job runtime. Second, various time-varying factors, including job arrival rates and competitors’ pricing, affect resource prices. Third, frequent price changes for the same resource can easily lead to system instability, ultimately jeopardizing user satisfaction. Addressing these uncertainties is challenging. This article introducesAPOS, an adaptive pricing and online scheduling framework, aiming at maximizing the operator’s overall revenue.APOSincorporates two innovations: 1) Intelligent Pricing: We represent each price using a feature vector that encapsulates relevant factors. Subsequently, based on the linear upper confidence bound (UCB) techniques, we establish relationships between price features and two revenue-associated elements: a) job arrival rates and b) resource consumption rates. To ensure system stability, we introduce batch pricing to reduce the frequency of resource price updates and 2) Online Scheduling: We strive to compute a nonpreemptive schedule that balances job utility with corresponding resource cost. We rigorously prove thatAPOSachieves truthfulness, individual rationality, system stability, and sublinear regret in polynomial time. Finally, extensive trace-driven simulations confirm thatAPOSoutperforms four state-of-the-art baselines, yielding a minimum of 23.3% improvement in total operator revenue.

Machine learning (ML) based static malware detectors are widely deployed, but vulnerable to adversarial attacks. Unlike images or texts, tiny modifications to malware samples would significantly compromise their functionality. Consequently, existing attacks against images or texts will be significantly restricted when being deployed on malware detectors. In this work, we propose a hard-label black-box attack MPass against ML-based detectors. MPass employs a problem-space explainability method to locate critical positions of malware, applies adversarial modifications to such positions, and utilizes a runtime recovery technique to preserve the functionality. Experiments show MPass outperforms existing solutions and bypasses both state-of-the-art offline models and commercial ML-based antivirus products.

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.

To save cost, companies usually train machine learning (ML) models on a shared multi-tenant system. In this cooperative environment, one of the fundamental challenges is how to distribute resources fairly among tenants such that each tenant is satisfied. A satisfactory allocation policy needs to meet the following properties. First, the performance of each tenant in the shared cluster is at least the same as that in its exclusive cluster partition. Second, no tenant can get more benefits by lying about its demands. Third, tenants cannot use the idle resources of others for free. Moreover, the resource allocation for ML workloads should avoid costly migration overhead. To this end, we propose a three-layer scheduling framework Astraea: i) a batch scheduling framework groups unprocessed jobs into multiple batches; ii) a round-by-round algorithm enables tenants to reserve their share of resources and schedule jobs in a non-preemptive manner; iii) one-round algorithm based on primal-dual approach and posted pricing framework, which encourages tenants to report truthful demands. Astraea is proven to achieve performance guarantee and some desirable properties of sharing, including sharing incentive, strategy-proofness and gain-as-you-contribute fairness. Extensive trace-driven simulations show Astraea advances in both fairness and cluster efficiency compared to three state-of-the-art baselines.

Distributed machine learning (ML) has played a key role in today's proliferation of AI services. A typical model of distributed ML is to partition training datasets over multiple worker nodes to update model parameters in parallel, adopting aparameter serverorAllReducearchitecture. ML training jobs are typically resource elastic, completed using various time lengths with different resource configurations. A fundamental problem in a distributed ML cluster is how to explore the demand elasticity of ML jobs and schedule them with different resource configurations, such that the utilization of resources is maximized and average job completion time is minimized. To address it, we propose an online scheduling algorithm to decide the execution time window, the number and the type of concurrent workers and parameter servers for each job upon its arrival, with a goal of minimizing the weighted average completion time. Our online algorithm consists of (i) an online scheduling framework that groups unprocessed ML training jobs into a batch iteratively, and (ii) a batch scheduling algorithm that configures each ML job to maximize the total weight of scheduled jobs in the current iteration. Our online algorithm guarantees a good parameterized competitive ratio with polynomial time complexity. Extensive evaluations using real-world data demonstrate that it outperforms state-of-the-art schedulers in today's AI cloud systems.

Federated learning (FL) has emerged as a new paradigm that enables distributed mobile devices to learn a global model collaboratively. Since mobile devices (a.k.a, clients) exhibit diversity in model training quality, client selection (CS) becomes critical for efficient FL. CS faces the following challenges: First, the client’s availability, the training data volumes, and the network connection status are time-varying and cannot be easily predicted. Second, clients for training and the number of local iterations would seriously affect the model accuracy. Thus, selecting a subset of available clients and controlling local iterations should guarantee model quality. Third, renting clients for model training needs cost. It is necessary to dynamically administrate the use of the long-term budget without knowledge of future inputs. To this end, we propose a federated edge learning (FedL) framework, which can select appropriate clients and control the number of training iterations in real-time. FedL aims to reduce the completion time while reaching the desired model convergence and satisfying the long-term budget for renting clients. FedL consists of two algorithms: i) the online learning algorithm makes CS and iteration decisions according to historic learning results; ii) the online rounding algorithm translates fractional decisions derived by the online learning algorithm into integers to satisfy feasibility constraints. Rigorous mathematical proof reveals that dynamic regret and dynamic fit have sub-linear upper-bounds with time for a given budget. Extensive experiments based on realistic datasets suggest that FedL outperforms multiple state-of-the-art algorithms. In particular, FedL reduces at least 38% completion time compared with others.

As a new paradigm, edge caching is deemed an effective alternative by fetching contents at the network edge. However, designing an efficient caching mechanism is challenging. First, the content library is a dynamic set rather than a static set. Second, the content may be prevalent in different small base stations (SBSs), resulting in different rewards. Thus, the above reasons require each SBS could learn its caching decisions in a multi-SBSs network. Existing reinforcement learning algorithms either fail to consider the non-stationary environment or do not provide any performance guarantee. Thus, previous algorithms work well no longer. This work proposes a multi-agent multi-armed bandit caching framework, MAMAB-C, which navigates SBSs to cache contents in a distributed manner. Specifically, we formulate the multi-SBSs caching optimization problem as an online integer linear program (ILP) and convert it into a multi-agent multi-armed bandit (MAMAB) problem with resource constraints. MAMAB-C can realize the sub-linear metric property and significantly outperform multiple state-of-the-art algorithms.

It is important to test convolutional neural networks (CNNs) to identify defects (e.g. error-inducing inputs) before deploying them in security-sensitive scenarios. Although existing white-box testing methods can effectively test CNN models with high neuron coverage, they are not applicable to privacy-sensitive scenarios where full knowledge of target CNN models is lacking. In this work, we propose a novel Black-box Efficient Testing (BET) method for CNN models. The core insight of BET is that CNNs are generally prone to be affected by continuous perturbations. Thus, by generating such continuous perturbations in a black-box manner, we design a tunable objective function to guide our testing process for thoroughly exploring defects in different decision boundaries of the target CNN models. We further design an efficiency-centric policy to find more error-inducing inputs within a fixed query budget. We conduct extensive evaluations with three well-known datasets and five popular CNN structures. The results show that BET significantly outperforms existing white-box and black-box testing methods considering the effective error-inducing inputs found in a fixed query/inference budget. We further show that the error-inducing inputs found by BET can be used to fine-tune the target model, improving its accuracy by up to 3%.

Clustered Federated Learning (FL) addresses heterogeneous objectives from different client groups, by capturing the intrinsic relationship between data distributions of clients. This work aims to minimize the completion time of clustered FL training while guaranteeing convergence, given the following challenges. First, clients’ data distributions are not static since their interests are usually time-varying. Obsolete data may incur training failures, requiring detection of distribution changes at runtime. Second, even with the same distribution, client datasets may have different contributions to model accuracy. Besides, the training data typically arrive at clients dynamically, which brings uncertainties to assessing the quality of client data. Third, the execution environments of clients and networks are often unstable and stochastic, leading to uncertainties in calculating computation and communication time. Given the above challenges, we propose Acct with two innovations: i) change detection: we first model the time-varying interests of clients as piecewise stationary based on practical observations, then apply generalized likelihood ratio detectors to FL for detecting changes in client distributions; ii) client selection: we adopt the multi-armed bandit (MAB) technique to account for the uncertainties in measuring data quality, computation and communication time. Based on the upper confidence bound (UCB) method, we construct a novel “double UCB” policy to adaptively select clients with high data quality and low computation and communication overhead. We rigorously prove the convergence of Acct and sub-linear regret regarding the proposed client selection policy. Finally, we implement Acct using PyTorch and conduct experiments showing that Acct reduces the completion time by almost 18.2% compared with three state-of-the-art FL frameworks.

Recent advances in 5G and edge computing enable rapid development and deployment of edge-cloud systems, which are ideal for delay-sensitive machine learning (ML) applications such as autonomous driving and smart city. Distributed ML jobs often need to train a large model with enormous datasets, which can only be handled by deploying a distributed set of workers in an edge-cloud system. One common approach is to employ a parameter server (PS) architecture, in which training is carried out at multiple workers, while PSs are used for aggregation and model updates. In this architecture, one of the fundamental challenges is how to dispatch ML jobs to workers and PSs such that the average job completion time (JCT) can be minimized. In this work, we propose a novel online preemptive scheduling framework to decide the location and the execution time window of concurrent workers and PSs upon each job arrival. Specifically, our proposed scheduling framework consists of: i) a job dispatching and scheduling algorithm that assigns each ML job to workers and decides the schedule to train each data chunk; ii) a PS assignment algorithm that determines the placement of PS. We prove theoretically that our proposed algorithm is$D_{max}(1+1/\epsilon)$-competitive with$(1 + \epsilon)$-speed augmentation, where$D_{max}$is the maximal number of data chunks in any job. Extensive testbed experiments and trace-driven simulations show that our algorithm can reduce the average JCT by up to 30% compared with state-of-the-art baselines.

As the next-generation wireless networks thrive, full-duplex and relay techniques are combined to improve the network performance. Random linear network coding (RLNC) is another popular technique to enhance the efficiency and reliability of wireless communications. In this paper, in order to explore the potential of RLNC in full-duplex relay networks, we investigate two fundamental perfect RLNC schemes and theoretically analyze their completion delay performance. The first scheme is a straightforward application of conventional perfect RLNC studied in wireless broadcast, so it involves no additional process at the relay. Its performance serves as an upper bound for all perfect RLNC schemes. The other scheme allows sufficiently large buffer and unconstrained linear coding at the relay. It attains the optimal performance and serves as a lower bound for all RLNC schemes. For both schemes, closed-form formulae to characterize the expected completion delay at a single receiver as well as for the whole system are derived. Numerical results are also demonstrated to validate the theoretical characterizations, and compare the two fundamental schemes with the existing one.

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.

Energy conservation of large data centers for high performance computing workloads, such as deep learning with Big Data, is of critical significance, where cutting down a few percent of electricity translates into million-dollar savings. This work studies energy conservation on emerging CPU-GPU hybrid clusters through dynamic voltage and frequency scaling (DVFS). We aim at minimizing the total energy consumption of processing a batch of offline tasks or a sequence of real-time tasks under deadline constraints. We derive a fast and accurate analytical model to compute the appropriate voltage/frequency setting for each task, and assign multiple tasks to the cluster with heuristic scheduling algorithms. In particular, our model stresses the nonlinear relationship between task execution time and processor speed for GPU-accelerated applications, for more accurately capturing real-world GPU energy consumption. In performance evaluation driven by real-world power measurement traces, our scheduling algorithm shows comparable energy savings to the theoretical upper bound. With a GPU scaling interval where analytically at most 36% of energy can be saved, we record 33-35% of energy savings. Our results are applicable to energy management on modern heterogeneous clusters.

To infer the structure of a diffusion network from observed diffusion results, existing approaches customarily assume that observed data are complete and contain the final infection status of each node, as well as precise timestamps of node infections. Due to high cost and uncertainties in the monitoring of node infections, exact timestamps are often unavailable in practice, and even the final infection statuses of nodes are sometimes missing. In this work, we study how to carry out diffusion network inference without infection timestamps, using only partial observations of the final infection statuses of nodes. To this end, we iteratively infer the structure of the target diffusion network with observed data and imputed values for missing data, and learn the most likely infection transmission probabilities between nodes w.r.t. current inferred structure, which then help us update the imputation of missing data in turn. Extensive experimental results on both synthetic and real-world networks show that our approach can properly handle missing data and accurately uncover diffusion network structures.

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.

Distributed machine learning with multiple concurrent workers has been widely adopted to train large deep neural networks (DNNs). Parameter synchronization is a key component in each iteration of distributed training, where workers exchange locally computed gradients through an AllReduce operation or parameter servers, for global parameter updates. Parameter synchronization often constitutes a significant portion of the training time; minimizing the communication time contributes substantially to DNN training speed-up. Standard ring-based AllReduce or PS architecture work efficiently mostly with homogeneous inter-worker connectivity. However, available bandwidth among workers in real-world clusters is often heterogeneous, due to different hardware configurations, switching topologies, and contention with concurrent jobs. This work investigates the best parameter synchronization topology and schedule among workers for most expedited communication in distributed DNN training. We show that the optimal parameter synchronization topology should be comprised of trees with different workers as roots, each for aggregating or broadcasting a partition of gradients/parameters. We identify near-optimal forest packing to maximally utilize available bandwidth and overlap aggregation and broadcast stages to minimize communication time. We provide theoretical analysis of the performance bound, and show that our scheme outperforms state-of-the-art parameter synchronization schemes by up to 18.3 times with extensive evaluation under various settings.

By establishing a single parity check relationship between convolutional codewords, a concatenated code, termed single parity check convolutional code (SPC-CC), is proposed. By jointly en/decoding the SPC and CC, as well as carefully allocating redundant information between the pair, we can improve BER more promptly during iterative decoding. Each codeword in SPC-CC consists of only one SISO decoder, which generates one extrinsic information. The key is to simulate another using extrinsic information from other decoders. Then iteratively feed back extrinsic information to each other in a manner similar to a Turbo engine. We design en/decoding scheme of the SPC-CC, and then analyze its performance and complexity. Simulation results show that SPC-CC can effectively improve communication reliability with a moderate complexity. In addition, thanks to SPC code, SPC-CC can correct packet erasures due to fading or interference.

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

Memory maximum-distance-separable (mMDS) sliding window codes are a type of erasure codes with high erasure-correction capability and low decoding delay. In this paper, we study two types of systematic mMDS sliding window codes over erasure channels, i.e., scalar codes defined over a finite field GF(2L), and vector codes defined over a vector space GF(2)L. We first devise an efficient heuristic algorithm to produce an mMDS sliding window scalar code over relatively small GF(2L). Then, we investigate a special class of mMDS sliding window vector codes whose encoding/decoding are achieved by basic circular-shift and bit-wise XOR operations, and propose a general method to generate such mMDS vector codes. Our complexity analysis shows that the proposed vector codes yield much lower encoding/decoding complexity than the scalar codes. The theoretical and numerical results also demonstrate that mMDS sliding window codes dominate MDS block codes in terms of decoding delay and erasure-correction capability.

Modern generative models are usually designed to match target distributions directly in the data space, where the intrinsic dimension of data can be much lower than the ambient dimension. We argue that this discrepancy may contribute to the difficulties in training generative models. We therefore propose to map both the generated and target distributions to the latent space using the encoder of a standard autoencoder, and train the generator (or decoder) to match the target distribution in the latent space. Specifically, we enforce the consistency in both the data space and the latent space with theoretically justified data and latent reconstruction losses. The resulting generative model, which we call a perceptual generative autoencoder (PGA), is then trained with a maximum likelihood or variational autoencoder (VAE) objective. With maximum likelihood, PGAs generalize the idea of reversible generative models to unrestricted neural network architectures and arbitrary number of latent dimensions. When combined with VAEs, PGAs substantially improve over the baseline VAEs in terms of sample quality. Compared to other autoencoder-based generative models using simple priors, PGAs achieve state-of-the-art FID scores on CIFAR-10 and CelebA.

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.

Distributed machine learning (ML) has played a key role in today's proliferation of AI services. A typical model of distributed ML is to partition training datasets over multiple worker nodes to update model parameters in parallel, adopting a parameter server architecture. ML training jobs are typically resource elastic, completed using various time lengths with different resource configurations. A fundamental problem in a distributed ML cluster is how to explore the demand elasticity of ML jobs and schedule them with different resource configurations, such that the utilization of resources is maximized and average job completion time is minimized. To address it, we propose an online scheduling algorithm to decide the execution time window, the number and the type of concurrent workers and parameter servers for each job upon its arrival, with a goal of minimizing the weighted average completion time. Our online algorithm consists of (i) an online scheduling framework that groups unprocessed ML training jobs into a batch iteratively, and (ii) a batch scheduling algorithm that configures each ML job to maximize the total weight of scheduled jobs in the current iteration. Our online algorithm guarantees a good parameterized competitive ratio with polynomial time complexity. Extensive evaluations using real-world data demonstrate that it outperforms state-of-the-art schedulers in today's AI cloud systems.

As the performance gap between processors and storage devices keeps increasing, I/O performance becomes a critical bottleneck of modern high-performance computing systems. In this paper, we propose a pattern-directed and layout-aware data replication design, named PDLA, to improve the performance of parallel I/O systems. PDLA includes an HDD-based scheme H-PDLA and an SSD-based scheme S-PDLA. For applications with relatively low I/O concurrency, H-PDLA identifies access patterns of applications and makes a reorganized data replica for each access pattern on HDD-based servers with an optimized data layout. Moreover, to accommodate applications with high I/O concurrency, S-PDLA replicates critical access patterns that can bring performance benefits on SSD-based servers or on HDD-based and SSD-based servers. We have implemented the proposed replication scheme under MPICH2 library on top of OrangeFS file system. Experimental results show that H-PDLA can significantly improve the original parallel I/O system performance and demonstrate the advantages of S-PDLA over H-PDLA.

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

Geo-distributed machine learning (ML) often uses large geo-dispersed data collections produced over time to train global models, without consolidating the data to a central site. In the parameter server architecture, “workers” and “parameter servers” for a geo-distributed ML job should be strategically deployed and adjusted on the fly, to allow easy access to the datasets and fast exchange of the model parameters at anytime. Despite many cloud platforms now provide volume discounts to encourage the usage of their ML resources, different geo-distributed ML jobs that run in the clouds often rent cloud resources separately and respectively, thus rarely enjoying the benefit of discounts. We study an ML broker service that aggregates geo-distributed ML jobs into cloud data centers for volume discounts via dynamic online placement and scaling of workers and parameter servers in individual jobs for long-term cost minimization. To decide the number and the placement of workers and parameter servers, we propose an efficient online algorithm which first decomposes the online problem into a series of one-shot optimization problems solvable at each individual time slot by the technique of regularization, and afterwards round the fractional decisions to the integer ones via a carefully-designed dependent rounding method. We prove a parameterized-constant competitive ratio for our online algorithm as the theoretical performance analysis, and also conduct extensive simulation studies to exhibit its close-to-offline-optimum practical performance in realistic settings.

Datacenter demand response is envisioned as a promising tool for mitigating operational stability issues faced by smart grids. It enables significant potentials in peak load reduction and facilitates the incorporation of distributed generation. Monetary refund from the smart grid can also alleviate the cloud's burden in escalating electricity cost. However, the current demand response paradigm is inefficient towards incentivizing a cloud service provider (CSP) that operates geo-distributed datacenters. To incentivize CSP participation, this work presents an auction mechanism that enables smart grids to voluntarily submit bids to the CSP to procure diverse amounts of demand response with different payments. To maximize the social welfare of the auction, the CSP that acts as the auctioneer needs to solve the winner determination problem at large-scale. By applying the proximal Jacobian alternating direction method of multipliers, we propose a distributed algorithm for each datacenter to solve a small-scale problem in a parallel fashion. Desirable properties of the proposed auction, such as social welfare maximization and truthfulness are achieved through Vickrey-Clarke-Groves (VCG) payment. Through extensive evaluations based on real datacenter workload traces and IEEE 14-bus test systems, we demonstrate that our incentive mechanism constitutes a win-win mechanism for both the geo-distributed cloud and the smart grid.

This paper proposes an online algorithm for energy storage management in networked microgrids (MGs) with co-generation based on the concept of quality-of-service in electricity (QoSE). The concept of networked MG with distributed renewable energy supply and co-generation makes power supply smarter for electricity/heat using, which has advantages of increasing power supply efficiency and reliability by coordinately scheduling the power supply in a networked way. The demands include quality usage of electricity load and heat. The networked MG central controller aims to minimize the operation cost and guarantee the outage probability of quality usage, i.e., QoSE, by scheduling electricity among renewable energy sources, energy storage systems, co-generation, and external utility market. We formulate the problem as a stochastic programming problem with QoSE and battery capacity constraints. By introducing the QoSE virtual queues and energy storage virtual queues, we transform the original problem into a problem that is applicable to employ the Lyapunov optimization technique. The proposed algorithm is an online algorithm with low complexity for practical implementation, and also provides several deterministic performance bounds. We perform extensive simulations to demonstrate the effectiveness of the proposed algorithm, which exhibits significant efficiency on operation cost reduction compared with an alternative benchmark solution.

Geo-distributed virtual network function (VNF) chaining has been useful, such as in network slicing in 5G networks and for network traffic processing in the WAN. Agile scaling of the VNF chains according to real-time traffic rates is the key in network function virtualization. Designing efficient scaling algorithms is challenging, especially for geo-distributed chains, where bandwidth costs and latencies incurred by the WAN traffic are important but difficult to handle in making scaling decisions. Existing studies have largely resorted to optimization algorithms in scaling design. Aiming at better decisions empowered by in-depth learning from experiences, this paper proposes a deep learning-based framework for scaling of the geo-distributed VNF chains, exploring inherent pattern of traffic variation and good deployment strategies over time. We novelly combine a recurrent neural network as the traffic model for predicting upcoming flow rates and a deep reinforcement learning (DRL) agent for making chain placement decisions. We adopt the experience replay technique based on the actor-critic DRL algorithm to optimize the learning results. Trace-driven simulation shows that with limited offline training, our learning framework adapts quickly to traffic dynamics online and achieves lower system costs, compared to the existing representative algorithms.

Containers represent an agile alternative to virtual machines (VMs), for providing cloud computing services. Containers are more flexible and lightweight, and can be easily instrumented. Enterprise users often create clusters of inter-connected containers to provision complex services. Compared to traditional cloud services, key challenges in container cluster (CC) provisioning lie in the optimal placement of containers while considering inter-container traffic in a CC. The challenge further escalates, when CCs are provisioned in an online fashion. We propose an online algorithm to address the above challenges, aiming to maximize the aggregate value of all served clusters. We first study a one-shot CC placement problem. Leveraging techniques of exhaustive sampling and ST rounding, we design an efficient one-shot algorithm to determine the placement scheme of a given CC. We then propose a primal-dual online placement scheme that employs the one-shot algorithm as a building block to make decisions upon the arrival of each CC request. Through both theoretical analysis and trace-driven simulations, we verify that the online placement algorithm is computationally efficient and achieves a good competitive ratio.

Small-cell architecture is widely adopted by cellular network operators to increase spectral spatial efficiency. However, this approach suffers from low spectrum temporal efficiency. When a cell becomes smaller and covers fewer users, its total traffic fluctuates significantly due to insufficient traffic aggregation and exhibits a large “peak-to-mean” ratio. As operators customarily provision spectrum for peak traffic, large traffic temporal fluctuation inevitably leads to low spectrum temporal efficiency. To address this issue, in this paper, we advocate device-to-device (D2D) load-balancing as a useful mechanism. The idea is to shift traffic from a congested cell to its adjacent under-utilized cells by leveraging inter-cell D2D communication, so that the traffic can be served without using extra spectrum, effectively improving the spectrum temporal efficiency. We provide theoretical modeling and analysis to characterize the benefit of D2D load balancing, in terms of total spectrum requirements and the corresponding cost, in terms of incurred D2D traffic overhead. We carry out empirical evaluations based on real-world 4G data traces and show that D2D load balancing can reduce the spectrum requirement by 25% as compared to the standard scenario without D2D load balancing, at the expense of negligible 0.7% D2D traffic overhead.

Circular-shift linear network coding (LNC) is a class of vector LNC with low encoding and decoding complexities, and with local encoding kernels chosen from cyclic permutation matrices. When L is a prime with primitive root 2, it was recently shown that a scalar linear solution over GF(2L-1) induces an L-dimensional circular-shift linear solution at rate (L-1)/L. In this paper, we prove that for arbitrary odd L, every scalar linear solution over GF(2mL), where mL refers to the multiplicative order of 2 modulo L, can induce an L-dimensional circular-shift linear solution at a certain rate. Based on the generalized connection, we further prove that for such L with mL beyond a threshold, every multicast network has an L-dimensional circular-shift linear solution at rate φ(L)/L, where φ(L) is the Euler's totient function of L. An efficient algorithm for constructing such a solution is designed. Finally, we prove that every multicast network is asymptotically circular-shift linearly solvable.

We study a class of linear network coding (LNC) schemes, called circular-shift LNC, whose encoding operations consist of only circular-shifts and bit-wise additions. Formulated as a special vector linear code over GF(2), an L-dimensional circular-shift linear code of degree δ restricts its local encoding kernels to be the summation of at most δ cyclic permutation matrices of size L. We show that on a general network, for a certain block length L, every scalar linear solution over GF(2L-1) can induce an L-dimensional circular-shift linear solution with 1-bit redundancy per-edge transmission. Consequently, specific to a multicast network, such a circular-shift linear solution of an arbitrary degree δ can be efficiently constructed, which has an interesting complexity tradeoff between encoding and decoding with different choices of δ. By further proving that circular-shift LNC is insufficient to achieve the exact capacity of certain multicast networks, we show the optimality of the efficiently constructed circular-shift linear solution in the sense that its 1-bit redundancy is inevitable. Finally, both theoretical and numerical analysis imply that with increasing L, a randomly constructed circular-shift linear code has linear solvability behavior comparable to a randomly constructed permutation-based linear code, but has shorter overheads.

The provisioning of cloud computing services typically incurs huge electricity costs. Utilization maximization of the cloud resources and efficient resource pricing have been key factors determining a cloud provider's revenue. On the other hand, dynamic CPU speed scaling has been widely supported by modern operating systems and hypervisors as an efficient technique for CPU energy saving, potentially useful for cutting down provider's electricity bill. In this paper, we propose an online mechanism for resource allocation and pricing on a cloud platform, which enables dynamic CPU speed scaling for achieving the best job execution efficiency. Using a novel compact infinite optimization technique and the primal-dual online algorithm design framework, our online mechanism achieves computational efficiency, truthfulness, and near-optimal social welfare during the long run of the cloud system. Trace-driven simulation studies further demonstrate good performance of our mechanism in realistic settings.

Nowadays large-scale distributed machine learning systems have been deployed to support various analytics and intelligence services in IT firms. To train a large dataset and derive the prediction/inference model, e.g., a deep neural network, multiple workers are run in parallel to train partitions of the input dataset, and update shared model parameters. In a shared cluster handling multiple training jobs, a fundamental issue is how to efficiently schedule jobs and set the number of concurrent workers to run for each job, such that server resources are maximally utilized and model training can be completed in time. Targeting a distributed machine learning system using the parameter server framework, w e design an online algorithm for scheduling the arriving jobs and deciding the adjusted numbers of concurrent workers and parameter servers for each job over its course, to maximize overall utility of all jobs, contingent on their completion times. Our online algorithm design utilizes a primal-dual framework coupled with efficient dual subroutines, achieving good long-term performance guarantees with polynomial time complexity. Practical effectiveness of the online algorithm is evaluated using trace-driven simulation and testbed experiments, which demonstrate its outperformance as compared to commonly adopted scheduling algorithms in today's cloud systems.

With the advent of cloud container technology, enterprises develop applications through microservices, breaking monolithic software into a suite of small services whose instances run independently in containers. User requests are served by a series of microservices forming a chain, and the chains often share microservices. Existing load balancing strategies either incur significant networking overhead or ignore the competition for shared microservices across chains. Furthermore, typical load balancing solutions leverage a hybrid technique by combining HTTP with message queue to support microservice communications, bringing additional operational complexity. To address these challenges, we propose a chain-oriented load balancing algorithm (COLBA) based solely on message queues, which balances load based on microservice requirements of chains to minimize response time. We model the load balancing problem as a non-cooperative game, and leverage Nash bargaining to coordinate microservice allocation across chains. Employing convex optimization with rounding, we efficiently solve the problem that is proven NP-hard. Extensive trace-driven simulations demonstrate that COLBA reduces the overall average response time at least by 13% compared with existing load balancing strategies.

State-of-the-art cloud platforms adopt pay-as-you-go pricing, where users pay for the resources on demand according to occupation time. Simple and intuitive as it is, such a pricing scheme is a mismatch for new workloads today such as large-scale machine learning, whose completion time is hard to estimate beforehand. To supplement existing cloud pricing schemes, we propose an occupation-oblivious online pricing mechanism for cloud jobs without pre-specified time duration and for users who prefer a pre-determined cost for job execution. Our strategy posts unit resource prices upon user arrival and decides a fixed charge for completing the user's job, without the need to know how long the job is to occupy the requested resources. At the core of our design is a novel multi-armed bandit based online learning algorithm for estimating unknown input by exploration and exploitation of past resource sales, and deciding resource prices to maximize profit of the cloud provider in an online setting. Our online learning algorithm achieves a low regret sublinear with the time horizon, in terms of overall provider profit, compared with an omniscient benchmark. We also conduct trace-driven simulations to verify efficacy of the algorithm in real-world settings.

Circular-shift linear network coding (LNC) is a class of vector LNC with low encoding and decoding complexities, with local encoding kernels chosen from cyclic permutation matrices. When L is a prime with primitive root 2, it was recently shown that a scalar linear solution over GF(2L-1) induces an Ldimensional circular-shift linear solution at rate (L-1)/L. In this work, we prove that for an arbitrary odd L, every scalar linear solution over GF(2(m)L), where mLrefers to the multiplicative order of 2 modulo L, can induce an L-dimensional circularshift linear solution at a certain rate. Based on the generalized connection, we further prove that every multicast network has an L-dimensional circular-shift linear solution at rate φ(L)/L, where φ(L) is the Euler's totient function of L and (m)Lis beyond a threshold. Stemming from this, we last prove that every multicast network is asymptotically circular-shift linearly solvable.

Multiplicative noise, including dropout, is widely used to regularize deep neural networks (DNNs), and is shown to be effective in a wide range of architectures and tasks. From an information perspective, we consider injecting multiplicative noise into a DNN as training the network to solve the task with noisy information pathways, which leads to the observation that multiplicative noise tends to increase the correlation between features, so as to increase the signal-to-noise ratio of information pathways. However, high feature correlation is undesirable, as it increases redundancy in representations. In this work, we propose non-correlating multiplicative noise (NCMN), which exploits batch normalization to remove the correlation effect in a simple yet effective way. We show that NCMN significantly improves the performance of standard multiplicative noise on image classification tasks, providing a better alternative to dropout for batch-normalized networks. Additionally, we present a unified view of NCMN and shake-shake regularization, which explains the performance gain of the latter.

Recent studies in cloud resource allocation and pricing have focused on computing and storage resources but not network bandwidth. Cloud users nowadays customarily deploy services across multiple geo-distributed datacenters, with significant inter-datacenter traffic generated, paid by cloud providers to ISPs. An effective bandwidth allocation and charging mechanism is needed between the cloud provider and the cloud users. Existing volume based static charging schemes lack market efficiency. This work presents the first dynamic pricing mechanism for inter-data-center on-demand bandwidth, via a Shapley value based auction. Our auction is expressive enough to accept bids as a flat bandwidth rate plus a time duration, or a data volume with a transfer deadline. We start with an offline auction, design an optimal end-to-end traffic scheduling approach, and exploit the Shapley value in computing payments. Our auction is truthful, individual rational, budget balanced and approximately efficient in social welfare. An online version of the auction follows, where decisions are made instantly upon the arrival of each user's realtime transmission demand. We propose an efficient online traffic scheduling algorithm, and approximate the offline Shapley value based payments on the fly. We validate our mechanism design with solid theoretical analysis, as well as trace-driven simulation studies.

The multiple-unicast conjecture in network coding states that for multiple unicast sessions in an undirected network, network coding has no advantage over routing in improving the throughput or saving bandwidth. In this paper, we propose a reduction method to study the multiple-unicast conjecture, and prove the conjecture for a new class of networks that are characterized by relations between cut-sets and source-receiver paths. This class subsumes all the known types of networks with non-zero max-flow min-cut gaps but zero coding advantage. Combining this result with a computer-aided search, we derive as a corollary that network coding is unnecessary in networks with up to six coding nodes. We also prove the multiple-unicast conjecture for almost all unit-link-length networks with up to three sessions and seven nodes.

Effective incentive mechanisms are invaluable in mobile crowd sensing, for stimulating participation of smartphone users. Online auction mechanisms represent a natural solution for such sensing task allocation. Departing from existing studies that focus on an isolated system round, we optimize social cost across the system lifespan, while considering location constraints and capacity constraints when assigning sensing tasks to users. The winner determination problem (WDP) at each round is NP-hard even without inter-round coupling imposed by user capacity constraints. We first propose a truthful one-round auction, comprising of an approximation algorithm for solving the one-round WDP and a payment scheme for computing remuneration to winners. We then propose an online algorithm framework that employs the one-round auction as a building block towards a flexible mechanism that makes on-spot decisions upon dynamically arriving bids. Through both theoretical analysis and trace-driven simulations, we demonstrate that our online auction is truthful, individually rational, computationally efficient, and achieves a good competitive ratio.

Compared with traditional virtual machines, cloud containers are more flexible and lightweight, emerging as the new norm of cloud resource provisioning. We exploit this new algorithm design space, and propose scheduling frameworks for cloud container services. Our offline and online schedulers permit partial execution, and allow a job to specify its job deadline, desired cloud containers, and inter-container dependence relations. We leverage the following classic and new techniques in our scheduling algorithm design. First, we apply the compact-exponential technique to express and handle nonconventional scheduling constraints. Second, we adopt the primal-dual framework that determines the primal solution based on its dual constraints in both the offline and online algorithms. The offline scheduling algorithm includes a new separation oracle to separate violated dual constraints, and works in concert with the randomized rounding technique to provide a near-optimal solution. The online scheduling algorithm leverages the online primal-dual framework with a learning-based scheme for obtaining dual solutions. Both theoretical analysis and trace-driven simulations validate that our scheduling frameworks are computationally efficient and achieve close-to-optimal aggregate job valuation.

Matrix factorization is a popular approach to solving matrix estimation problems based on partial observations. Existing matrix factorization is based on least squares and aims to yield a low-rank matrix to interpret the conditional sample means given the observations. However, in many real applications with skewed and extreme data, least squares cannot explain their central tendency or tail distributions, yielding undesired estimates. In this paper, we propose expectile matrix factorization by introducing asymmetric least squares, a key concept in expectile regression analysis, into the matrix factorization framework. We propose an efficient algorithm to solve the new problem based on alternating minimization and quadratic programming. We prove that our algorithm converges to a global optimum and exactly recovers the true underlying low-rank matrices when noise is zero. For synthetic data with skewed noise and a real-world dataset containing web service response times, the proposed scheme achieves lower recovery errors than the existing matrix factorization method based on least squares in a wide range of settings.

Network function virtualization (NFV) represents the latest technology advancement in network service provisioning. Traditional hardware middleboxes are replaced by software programs running on industry standard servers and virtual machines, for service agility, flexibility, and cost reduction. NFV users are provisioned with service chains composed of virtual network functions (VNFs). A fundamental problem in NFV service chain provisioning is to satisfy user demands with minimum system-wide cost. We jointly consider two types of cost in this work: nodal resource cost and link delay cost, and formulate the service chain provisioning problem using nonlinear optimization. Through the method of auxiliary variables, we transform the optimization problem into its separable form, and then apply the alternating direction method of multipliers (ADMM) to design scalable and fully distributed solutions. Through simulation studies, we verify the convergence and efficacy of our distributed algorithm design.

Network coding is a fundamental tool that enables higher network capacity and lower complexity in routing algorithms, by encouraging the mixing of information flows in the middle of a network. Implementing network coding in the core Internet is subject to practical concerns, since Internet routers are often overwhelmed by packet forwarding tasks, leaving little processing capacity for coding operations. Inspired by the recent paradigm of network function virtualization, we propose implementing network coding as a new network function, and deploying such coding functions in geo-distributed cloud data centers, to practically enable network coding on the Internet. We target multicast sessions (including unicast flows as special cases), strategically deploy relay nodes (network coding functions) in selected data centers between senders and receivers, and embrace high bandwidth efficiency brought by network coding with dynamic coding function deployment. We design and implement the network coding function on typical virtual machines, featuring efficient packet processing. We propose an efficient algorithm for coding function deployment, scaling in and out, in the presence of system dynamics. Real-world implementation on Amazon EC2 and Linode demonstrates significant throughput improvement and higher robustness of multicast via coding functions as well as efficiency of the dynamic deployment and scaling algorithm.

Conserving the energy consumption of large data centers is of critical significance, where a few percent in consumption reduction translates into millions-dollar savings. This work studies energy conservation on emerging CPU-GPU hybrid clusters through dynamic voltage and frequency scaling (DVFS). We aim at minimizing the total energy consumption of processing a sequence of real-time tasks under deadline constraints. We compute the appropriate voltage/frequency setting for each task through mathematical optimization, and assign multiple tasks to the cluster with heuristic scheduling algorithms. In performance evaluation driven by real-world power measurement traces, our scheduling algorithm shows comparable energy savings to the theoretical upper bound. With a GPU scaling interval where analytically at most 38% of energy can be saved, we record 30-36% of energy savings. Our results are applicable to energy management on modern heterogeneous clusters. In particular, our model stresses the nonlinear relationship between task execution time and processor speed for GPU-accelerated applications, for more accurately capturing real-world GPU energy consumption.

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

We study the problem of personalized Quality of Service (QoS) estimation for web services. State-of-the-art methods use matrix factorization or collaborative prediction to estimate web service response times and throughput for each user based on partial measurements collected from past invocations. We point out that in reality, both the response times and through-put of web services follow highly skewed distributions. In this case, the conditional mean QoS estimates generated by traditional matrix completion approaches can be heavily biased toward a few outliers, leading to poor web service recommendation performance. In this paper, we propose the Quantile Matrix Factorization (QMF) technique for web service recommendation by introducing quantile regression into the matrix factorization framework. We propose a novel and efficient algorithm based on Iterative Reweighted Least Squares (IRLS) to solve the QMF problem involving a non-smooth objective function. We further extend the proposed QMF approach to take into account user and service side attributes. Extensive evaluation based on a large-scale QoS dataset has shown that our schemes significantly outperform various state-of-the-art web service QoS estimation schemes in terms of personalized recommendation performance.

Virtualized datacenter networks have been deployed in production platforms, e.g., Amazon VPC and VMware's NVP, to offer the flexibility of network management to enterprise-level clients. A common characteristic of these platforms is that they adopt software switches, such as Open vSwitch (OvS), instead of hardware switches to transfer data between VMs. Although group communication is common in enterprise applications, the unique characteristics of software switches have posed new challenges to the design of multicast protocols. How logical multicast can be optimally performed with software switches is still not well understood. In this paper, we observe that unlike hardware switches, the per-stream output rate in a software switch critically depends on the packet processing overhead of flow cloning. We study the optimal OvS multicast topology with or without the help of additional dedicated software switches called service nodes, and formulate the throughput maximization as a new class of degree-supervised combinatorial graph problems due to the presence of flow cloning costs. We propose a lineartime optimal solution that translates into simple forwarding rules installed at each software switch. Through emulation-based OvS profiling and extensive simulation results, we demonstrate that our proposed logical multicast solutions can significantly improve session throughput with the ability to handle load balancing and latency issues, as compared to the state-of-the-art in the literature.

We study a class of linear network coding (LNC) schemes, called circular-shift LNC, whose encoding operations at intermediate nodes consist of only circular-shifts and bitwise addition (XOR). Departing from existing literature, we systematically formulate circular-shift LNC as a special type of vector LNC, where the local encoding kernels of an L-dimensional circular-shift linear code of degree δ are summation of at most δ cyclic-permutation matrices of size L. Under this framework, an intrinsic connection between scalar LNC and circular-shift LNC is established. In consequence, for some block lengths L, an (L - 1, L)-fractional circular-shift linear solution of arbitrary degree δ can be efficiently constructed on a multicast network. With different δ, the constructed solution has an interesting encoding-decoding complexity tradeoff, and when δ = (L - 1)/2, it requires fewer binary operations for both encoding and decoding processes compared with scalar LNC. While the constructed (L - 1, L)-fractional solution has one-bit redundancy per edge transmission, we show that this is inevitable, and that circular-shift LNC is insufficient to achieve the exact capacity of multicast networks.

Propagation delay has an important impact on system performance in long-distance wireless networks. While there is not much attention paid to taking the advantage of the differential propagation delays. In this paper, we propose a cross-layer delay-aware random access (DARA) for applying for time slots to transmit data in long-distance wireless networks. Based on Irregular Repetition Slotted ALOHA (IRSA), DARA takes propagation delay into consideration and makes a better time slot selection strategy. Simulation results show that DARA could achieve 30% improvement at most compared to IRSA in respect to the rate of successful decoding. Meanwhile, we try to optimize the rate of successful decoding with minimal cost, but find it is hard to formulate the relationship among the number of mobile hosts M, the number of slots N and the rate of successful decoding. At last, curve-fitting is utilized to get an approximative result.

Dynamic spectrum allocation has been proven as a promising solution to the spectrum scarcity problem. Auctions represent a natural allocation mechanism that generates a monetary remuneration for primary users. We study approximate revenue-maximizing spectrum auctions in a prior-free setting, when information on user valuations on channels is unavailable. A two-phase auction framework is presented. In Phase 1, a strategyproof mechanism computes a subset of users with an interference-free spectrum allocation, such that the potential revenue to be gained in the second phase is maximized. A carefully tailored payment scheme ensures truthful bidding at this stage. The selected users advance into Phase 2, where eventual auction winners are computed through a recursive random partitioning and revenue extraction procedure. While no strategyproof auction can achieve absolute optimal revenue in the prior-free setting, our random partition auction is both truthful in expectation and achieves the best known ratio 13 of the optimal revenue.

The device-to-device load balancing (D2D-LB) paradigm has been advocated in recent small-cell architecture design for cellular networks. The idea is to exploit inter-cell D2D communication and dynamically relay traffic of a busy cell to adjacent under-utilized cells to improve spectrum temporal efficiency, addressing a fundamental drawback of small-cell architecture. Technical challenges of D2D-LB have been studied in previous works. The potential of D2D-LB, however, cannot be fully realized without providing proper incentive mechanism for device participation. In this paper, we address this economical challenge using an online procurement auction framework. In our design, multiple sellers (devices) submit bids to participate in D2D-LB and the auctioneer (cellular service provider) evaluates all the bids and decides to purchase a subset of them to fulfill load balancing requirement with the minimum social cost. Different from similar auction design studies for cellular offloading, battery limit of relaying devices imposes a time-coupled capacity constraint that turns the underlying problem into a challenging multi-slot one. Furthermore, the dynamics in the input to the multi-slot auction problem emphasize the need for online algorithm design. We first tackle the single-slot version of the problem, show that it is NP-hard, and design a polynomial-time offline algorithm with a small approximation ratio. Building upon the single-slot results, we design an online algorithm for the multi-slot problem with sound competitive ratio. Our auction algorithm design ensures that truthful bidding is a dominant strategy for devices. Extensive experiments using real-world traces demonstrate that our proposed solution achieves near offline-optimum and reduces the cost by 45% compared with an alternative heuristic.

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

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

In the recent paradigm of cloud radio access networks (C-RAN), signal processing functions at the base stations (BSs) are virtualized and migrated into a mobile cloud that maintains a pool of virtual BS (VBS) instances. Remote radio heads and antennae at the BSs are connected to the VBS pool by fronthaul fiber links. Mobile operators may lease resources from the tower company who owns the C-RAN infrastructure. We study auction mechanisms for efficiently sharing C-RAN resources among mobile operators. Leveraging randomized rounding, we design an offline C-RAN auction mechanism that can achieve truthfulness and near-optimal social welfare. For the more realistic setting of online bid arrival, we design an online algorithm that executes in polynomial time and achieves a competitive ratio of $(1-\epsilon )$ . A tailored fractional Vickrey-Clarke-Groves mechanism works in concert with the online algorithm to elicit truthful bids. Extensive simulation studies verify the efficacy of our C-RAN auction mechanisms.

Device to Device communication enables the deployment of mobile cloudlets in LTE-advanced networks. The distributed nature of mobile users and dynamic task arrivals makes it challenging to schedule tasks fairly among multiple devices. Leveraging the idea of software defined networking, we propose a software defined cooperative offloading model (SDCOM), where the SDCOM controller is deployed at the PDN gateway and schedules tasks in a centralized manner to save the energy of mobile devices and reduce the traffic on access links. We formulate the minimum-energy task scheduling problem as a 0-1 knapsack problem and prove its NP-hardness. To compute the optimal solution as a benchmark, we design the conditioned optimal algorithm based on the aggregated analysis of energy consumption. The greedy algorithm with a polynominal-time complexity is proposed to solve large-scale problems efficiently. To address the problem without predicting future information on task arrivals, we further design an online task scheduling algorithm (OTS). It can minimize the energy consumption arbitrarily close to the optimal solution by appropriately setting the tradeoff coefficient. Moreover, we extend OTS to design a proportional fair online task scheduling algorithm to achieve the fair energy consumption among mobile devices. Extensive trace-based simulations demonstrate the effectiveness of SDCOM for a variety of typical mobile devices and applications.

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

This paper studies the cloud market for computing jobs with completion deadlines, and designs efficient online auctions for cloud resource provisioning. A cloud user bids for future cloud resources to execute its job. Each bid includes: 1) a utility, reflecting the amount that the user is willing to pay for executing its job and 2) a soft deadline, specifying the preferred finish time of the job, as well as a penalty function that characterizes the cost of violating the deadline. We target cloud job auctions that executes in an online fashion, runs in polynomial time, provides truthfulness guarantee, and achieves optimal social welfare for the cloud ecosystem. Towards these goals, we leverage the following classic and new auction design techniques. First, we adapt the posted pricing auction framework for eliciting truthful online bids. Second, we address the challenge posed by soft deadline constraints through a new technique of compact exponential-size LPs coupled with dual separation oracles. Third, we develop efficient social welfare approximation algorithms using the classic primal-dual framework based on both LP duals and Fenchel duals. Empirical studies driven by real-world traces verify the efficacy of our online auction design.

Network latency prediction is important for server selection and quality-of-service estimation in real-time applications on the Internet. Traditional network latency prediction schemes attempt to estimate the latencies between all pairs of nodes in a network based on sampled round-trip times, through either Euclidean embedding or matrix factorization. However, these schemes become less effective in terms of estimating the latencies of personal devices, due to unstable and time-varying network conditions, triangle inequality violation and the unknown ranks of latency matrices. In this paper, we propose a matrix completion approach to network latency estimation. Specifically, we propose a new class of low-rank matrix completion algorithms, which predicts the missing entries in an extracted “network feature matrix” by iteratively minimizing a weighted Schatten-p norm to approximate the rank. Simulations on true low-rank matrices show that our new algorithm achieves better and more robust performance than multiple state-of-the-art matrix completion algorithms in the presence of noise. We further enhance latency estimation based on multiple “frames” of latency matrices measured in the past, and extend the proposed matrix completion scheme to the case of 3-D tensor completion. Extensive performance evaluations driven by real-world latency measurements collected from the Seattle platform show that our proposed approaches significantly outperform various state-of-the-art network latency estimation techniques, especially for networks that contain personal devices.

It is common for cloud users to require clusters of inter-connected virtual machines (VMs) in a geo-distributed IaaS cloud, to run their services. Compared to isolated VMs, key challenges on dynamic virtual cluster (VC) provisioning (computation + communication resources) lie in two folds: (1) optimal placement of VCs and inter-VM traffic routing involve NP-hard problems, which are non-trivial to solve offline, not to mention if an online efficient algorithm is sought; (2) an efficient pricing mechanism is missing, which charges a market-driven price for each VC as a whole upon request, while maximizing system efficiency or provider revenue over the entire span. This paper proposes efficient online auction mechanisms to address the above challenges. We first design SWMOA, a novel online algorithm for dynamic VC provisioning and pricing, achieving truthfulness, individual rationality, computation efficiency, and (1 + 2 log μ)-competitiveness in social welfare, where m is related to the problem size. Next, applying a randomized reduction technique, we convert the social welfare maximizing auction into a revenue maximizing online auction, PRMOA, achieving O(log μ)-competitiveness in provider revenue, as well as truthfulness, individual rationality and computation efficiency. We investigate auction design in different cases of resource cost functions in the system. We validate the efficacy of the mechanisms through solid theoretical analysis and trace-driven simulations.

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

Dynamic adaptive streaming over HTTP (DASH) has emerged as a popular Internet video service, constituting a growing fraction of LTE network traffic today. We identify the root causes of DASH performance problems in bit-ate stability, energy consumption of User Equipment (UE) and efficiency of bandwidth utilization, from both the users' and network operators' perspectives. Unlike the existing researches that separately studied two important performance metrics in DASH, i.e., Quality of Experience (QoE) and UEs' energy consumption. We propose an energy-aware DASH delivery framework over LTE networks (EDASH), jointly optimizing the network throughput, users' QoE and UEs' energy efficiency. We formulate the bandwidth allocation problem as a nonlinear integer program, and design the EDASH Online Allocation algorithm (EOA). EOA assigns bandwidth based on channel conditions and buffer occupancy of UEs to achieve efficient video delivery among multiple users. Furthermore, we present the detailed design and implementation of EDASH using Apache HTTP server and Android smartphones. Both simulation and experiment results reveal that our scheme can improve the network throughput while striking a better balance between users' QoE and UEs' energy consumption.

A wide range of cloud computing jobs are delay tolerant up to a predefined deadline. Existing IaaS services offer either high cost and high fulfillment ratio or low cost without fulfillment ratio guarantee, where the fulfillment ratio is the ratio of job execution time to the time between job submission and completion. Neither of the services represents a cost-effective way to exploit job elasticity. This work proposes flexible instance, a cloud service where user-specified service fulfillment ratio, as a new pricing factor, is guaranteed by the provider to meet deadlines. Job elasticity is exploited by the provider to enhance resource utilization, by regulating demand fluctuation through computation arbitrage across the temporal domain. We leverage a two-stage pricing framework to agilely adapt cloud resource price to the demand-supply dynamics. The first stage uses an online strategy to reserve resources for each cloud user to guarantee its specified fulfillment ratio. We set the price of resources dynamically according to resource utilization, with a pricing curve O(ln p)-competitive to the optimal fixed-price offline strategy in provider revenue. The second stage allows cloud users to submit a small budget to compete for extra service fulfillment ratio for execution speedup. A Nash bargaining framework is explored to achieve fairness, resource efficiency, and revenue maximization simultaneously. Extensive simulations driven by real-world traces show that flexible instance can reduce user cost for job execution while increasing provider revenue.

Auction mechanisms have recently been studied as an efficient approach for dynamic resource allocation in a cloud market. Existing mechanisms are mostly limited to the offline setting or execute jobs in continuous time slots. This work focuses on a practical case of online auction design, where users bid for future cloud resources for executing their batch processing jobs with hard deadline constraints. We design an online primal-dual auction framework for Virtual Machine (VM) allocation with social welfare maximization, which is truthful, computationally efficient, and guarantees a small competitive ratio. We leverage the framework of post price auctions to design our online primal-dual algorithm, where a bid is accepted if its expected execution cost in future time slots is smaller than its bidding price. We interpret the dual variables as marginal prices per unit of resource, and iteratively update it according to the allocated amount of resource. Theoretical analysis and trace-driven simulation studies validate the efficacy of the online auction framework, including both its computational efficiency and economic efficiency.

Network Function Virtualization (NFV) is emerging as a new paradigm for providing elastic network functions through flexible virtual network function (VNF) instances executed on virtualized computing platforms exemplified by cloud datacenters. In the new NFV market, well defined VNF instances each realize an atomic function that can be chained to meet user demands in practice. This work studies the dynamic market mechanism design for the transaction of VNF service chains in the NFV market, to help relinquish the full power of NFV. Combining the techniques of primal-dual approximation algorithm design with Myerson's characterization of truthful mechanisms, we design a VNF chain auction that runs efficiently in polynomial time, guarantees truthfulness, and achieves near-optimal social welfare in the NFV eco-system. Extensive simulation studies verify the efficacy of our auction mechanism.

It is common for cloud users to require clusters of inter-connected virtual machines (VMs) in a geo-distributed IaaS cloud, to run their services. Compared to isolated VMs, key challenges on dynamic virtual cluster (VC) provisioning (computation + communication resources) lie in two folds: (1) optimal placement of VCs and inter-VM traffic routing involve NP-hard problems, which are non-trivial to solve offline, not to mention if an online efficient algorithm is sought; (2) an efficient pricing mechanism is missing, which charges a market-driven price for each VC as a whole upon request, while maximizing system efficiency or provider revenue over the entire span. This paper proposes efficient online auction mechanisms to address the above challenges. We first design SWMOA, a novel online algorithm for dynamic VC provisioning and pricing, achieving truthfulness, individual rationality, computation efficiency, and (1 + 2 log μ)-competitiveness in social welfare, where μ is related to the problem size. Next, applying a randomized reduction technique, we convert the social welfare maximizing auction into a revenue maximizing online auction, PRMOA, achieving O(log μ)-competitiveness in provider revenue, as well as truthfulness, individual rationality and computation efficiency. We validate the efficacy of the mechanisms through solid theoretical analysis and trace-driven simulations.

The multiple-unicast conjecture in network coding states that for multiple unicast sessions in an undirected network, network coding has no advantage over routing in improving the throughput or saving bandwidth. In this work, we propose a reduction method to study the multiple-unicast conjecture, and prove the conjecture for a new class of networks that are characterized by relations between cut-sets and source-receiver paths. This class subsumes the two known types of networks with non-zero max-flow min-cut gaps. Further combing this result with a computer-aided search, we derive as a corollary that network coding is unnecessary in networks with up to 6 nodes. We also prove the multiple-unicast conjecture for almost all unit-link-length networks with up to 3 sessions and 7 nodes.

Data centers with high yet elastic energy demand are ideal candidates for participation in demand response programs. This paper studies emergency demand response (EDR) at multi-tenant colocation data centers (colocations). While the colocation has no direct control over tenants' servers, we design online mechanisms to incentivize and coordinate tenants' energy reduction. Our mechanism is online in nature, aiming to maximize not only social welfare but also tenant utility. Our main proposal is a truthful incentive auction that provides tenants with monetary remuneration for EDR energy reduction, minimizing social cost, which combines seamlessly with an online primal-dual framework for each tenant to schedule their delay-tolerant workloads. The online optimization at each tenant targets its utility maximization, concurrently reporting valuation functions for the tenant to participate in the auction. Our online algorithms achieve long-term performance guarantees in both tenants' utility and social welfare maximization, while fulfilling the EDR requirement with minimal diesel generation. We validate the efficiency of our algorithms through both the theoretical analysis and real-world trace-driven simulations.

Datacenter demand response is a promising approach for mitigating operational instability faced by smart grids. It enables significant potentials in peak load shedding and facilitates the incorporation of distributed generation and intermittent energy sources. This paper considers two key aspects toward real-time electricity pricing for eliciting demand response: 1) two-way electricity flow between smart grids and large datacenters with hybrid green generation capabilities and 2) the geo-distributed nature of large cloud systems, and hence the potential competition among smart grids that serve different datacenters of the cloud. We propose a pricing scheme tailored for geo-distributed green datacenters, from a multi-leader (smart grids) single-follower (cloud) game point of view. At the cloud side, in quest for scalability, robustness, and performance, the energy cost minimization problem is solved in a distributed manner, based on the technique of alternating direction method of multipliers. At the smart grid side, a practical equilibrium of the multi-leader single-follower pricing game is desired. To this end, we employ the technique of equilibrium problem with equilibrium constraints and exact linearization, to accurately transform the multi-leader single-follower pricing game, which is non-convex into a mixed integer linear system that can be readily solved. The effectiveness of the proposed solutions is evaluated based on the real datacenter workload traces and the IEEE 14-bus test systems with real generation and demand data.

Vector linear network coding (LNC) is a generalization of the conventional scalar LNC, such that the data unit transmitted on every edge is an L-dimensional vector of data symbols over a base field GF(q). Vector LNC enriches the choices of coding operations at intermediate nodes, and there is a popular conjecture on the benefit of vector LNC over scalar LNC in terms of alphabet size of data units: there exist (singlesource) multicast networks that are vector linearly solvable of dimension L over GF(q) but not scalar linearly solvable over any field of size q' qL. This paper introduces a systematic way to construct such multicast networks, and subsequently establish explicit instances to affirm the positive answer of this conjecture for infinitely many alphabet sizes pL with respect to an arbitrary prime p. On the other hand, this paper also presents explicit instances with the special property that they do not have a vector linear solution of dimension L over GF(2) but have scalar linear solutions over GF(q') for someq'L, where q' can be odd or even. This discovery also unveils that over a given base field, a multicast network that has a vector linear solution of dimension L does not necessarily have a vector linear solution of dimension L' > L.

For a (single-source) multicast network, the size of a base field is the most known and studied algebraic identity that is involved in characterizing its linear solvability over the base field. In this paper, we design a new class N of multicast networks and obtain an explicit formula for the linear solvability of these networks, which involves the associated coset numbers of a multiplicative subgroup in a base field. The concise formula turns out to be the first that matches the topological structure of a multicast network and algebraic identities of a field other than size. It further facilitates us to unveil infinitely many new multicast networks linearly solvable over GF(q) but not over GF(q') with q2k) but not over GF(22k+1) and 2) for arbitrary distinct primes p and p', there are infinitely many k and k' such that an instance in N can be found linearly solvable over GF(pk) but not over GF(p'k') with pkk'.

Many distributed interactive multimedia applications, such as live video conferencing and video sharing, require each participating client to transmit its captured video stream to other clients via relay servers. We consider connecting multiple clients through multiple relay servers and study the server selection problem from a dense pool of content delivery network edge locations and datacenters to reduce the end-to-end delays between clients. To achieve scalability in the presence of a large number of candidate servers, we formulate server selection as a geometric problem in a delay space instead of in a graph, which turns out to be an extension of the well-known Euclidean k-median problem. We propose practical approximation schemes when using only one or two servers with theoretical worst-case guarantees as well as fast heuristics when using k servers. We demonstrate the benefit of our optimized multiserver selection schemes through extensive evaluation based on real-world traces collected from the PlanetLab and Seattle platforms, containing personal mobile devices as well as real network experiments based on a prototype implementation.

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

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

Recent years witness the proliferation of Infrastructure-as-a-Service (IaaS) cloud services, which provide on-demand resources (CPU, RAM, disk) in the form of virtual machines (VMs) for hosting applications/services of third parties. Given the state-of-the-art IaaS offerings, it is still a problem of fundamental importance how the Application Service Providers (ASPs) should rent VMs from the clouds to serve their application needs, in order to minimize the cost while meeting their job demands over a long run. Cloud providers offer different pricing options to meet computing requirements of a variety of applications. However, the challenge facing an ASP is how these pricing options can be dynamically combined to serve arbitrary demands at the optimal cost. In this paper, we propose an online VM purchasing algorithm based on the Lyapunov optimization technique, for minimizing the long-term-averaged VM rental cost of an ASP with time-varying and delay-tolerant workloads, while bounding the maximum response delay of its jobs. In stark contrast with the existing studies, the proposed algorithm enables an ASP to optimally decide the amount of reserved, on-demand and spot instances to purchase simultaneously. Rigorous analysis shows that our algorithm can achieve a time-averaged resource cost close to the offline optimum. Trace-driven simulations further verify the efficacy of our algorithm.

This work studies how to minimize communication cost for placing Virtual Machines (VMs) in a modular data center. We consider a number of cooperative VMs implementing the same job, with known inter-VM communication patterns. The modular data center has a two-layer network structure, where computing pods constitute basic building blocks and are connected by a core network. At the core network layer, we design spectral clustering algorithms to partition VMs into computing pods, minimizing inter-pod communication cost. We then further apply an SDP relaxation approach to decide the VM placement within each computing pod, targeting both load balancing among physical servers and inter-server communication cost minimization. Extensive simulations are conducted to validate the efficacy of the proposed hierarchical VM placement scheme.

The emerging cloud computing technologies enable a cloud platform to provide diverse cloud services to its service subscribers. By federating different services within and across cloud boundaries, cloud service developers can provision new, composite cloud services in the marketplace of apps and services on a cloud platform. Complete and accurate service QoS information is important for service recommendation and service pricing. However, measuring the entire QoS matrix for all user-service pairs incurs a tremendous overhead and is practically infeasible. This work designs efficient algorithms for recovering the complete QoS matrix from partial measurements, exploiting the low rank feature of the matrix. Our solution applies tools from differential geometry for transforming rank-constrained matrix optimization in a flat space into an unconstrained geometric optimization in a smooth manifold. Besides QoS matrix completion, future QoS matrix prediction based on manifold algorithms is also studied in this work, for the first time in the literature.

In the literature of network coding, vector linear network coding (LNC) is a generalization of the conventional scalar LNC, such that the data unit transmitted on every edge is an L-dimensional vector of data symbols over a base field GF(q). A scalar linear code over GF(q) is simply a vector linear code of dimension 1 over GF(q), and a general network has a scalar linear solution over GF(qL) only if it has a vector linear solution of dimension L over GF(q). Though vector LNC is more powerful in enabling a higher coding diversity, this work will present explicit multicast networks, for the first time in the literature, with the special property that they do not have a vector linear solution of dimension L over GF(2) but have scalar linear solutions over GF(q'), for some q'L. This reveals the fact that although vector LNC can outperform scalar LNC in terms of yielding a solution for a general network, scalar LNC can also outperform vector LNC of dimension larger than 1 in terms of using a smaller alphabet to yield a solution for a multicast network.

Spectrum auctions are efficient mechanisms for licensed users to relinquish their under-utilized spectrum to secondary links for monetary remuneration. Truthfulness and social welfare maximization are two natural goals in such auctions, but cannot be achieved simultaneously with polynomial-time complexity by existing methods, even in a static network with fixed parameters. The challenge escalates in practical systems with QoS requirements and volatile traffic demands for secondary communication. Online, dynamic decisions are required for rate control, channel evaluation/bidding, and packet dropping at each secondary link, as well as for winner determination and pricing at the primary user. This work proposes an online spectrum auction framework with cross-layer decision making and randomized winner determination on the fly. The framework is truthful-in-expectation, and achieves close-to-offline-optimal time-averaged social welfare and individual utilities with polynomial time complexity. A new method is introduced for online channel evaluation in a stochastic setting. Simulation studies further verify the efficacy of the proposed auction in practical scenarios.

With an increasing popularity of real-time applications, such as live chat and gaming, latency prediction between personal devices including mobile devices becomes an important problem. Traditional approaches recover all-pair latencies in a network from sampled measurements using either Euclidean embedding or matrix factorization. However, these approaches targeting static or mean network latency prediction are insufficient to predict personal device latencies, due to unstable and time-varying network conditions, triangle inequality violation and unknown rank of latency matrices. In this paper, by analyzing latency measurements from the Seattle platform, we propose new methods for both static latency estimation as well as the dynamic estimation problem given 3D latency matrices sampled over time. We propose a distance-feature decomposition algorithm that can decompose latency matrices into a distance component and a network feature component, and further leverage the structured pattern inherent in the 3D sampled data to increase estimation accuracy. Extensive evaluations driven by real-world traces show that our proposed approaches significantly outperform various state-of-the-art latency prediction techniques.

Data centers are key participants in demand response programs, including emergency demand response (EDR), where the grid coordinates large electricity consumers for demand reduction in emergency situations to prevent major economic losses. While existing literature concentrates on owner-operated data centers, this work studies EDR in multi-tenant colocation data centers where servers are owned and managed by individual tenants. EDR in colocation data centers is significantly more challenging, due to lack of incentives to reduce energy consumption by tenants who control their servers and are typically on fixed power contracts with the colocation operator. Consequently, to achieve demand reduction goals set by the EDR program, the operator has to rely on the highly expensive and/or environmentally-unfriendly on-site energy backup/generation. To reduce cost and environmental impact, an efficient incentive mechanism is therefore in need, motivating tenants' voluntary energy reduction in case of EDR. This work proposes a novel incentive mechanism, Truth-DR, which leverages a reverse auction to provide monetary remuneration to tenants according to their agreed energy reduction. Truth-DR is computationally efficient, truthful, and achieves 2-approximation in colocation-wide social cost. Trace-driven simulations verify the efficacy of the proposed auction mechanism.

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

Latest developments in cloud computing technologies have enabled a plethora of cloud based data storage services. Cloud storage service providers are facing significant bandwidth cost as the user population scales. Such bandwidth cost can be substantially slashed by exploring a hybrid cloud storage architecture that takes advantage of under-utilized storage and network resources at storage clients. A critical component in the new hybrid cloud storage architecture is an economic mechanism that incentivizes clients to contribute their local resources, while at the same time minimizes the provider's cost for pooling those resources. This work studies online procurement auction mechanisms towards these goals. The online nature of the auction is in line with asynchronous user request arrivals in practice. After carefully characterizing truthfulness conditions under the online procurement auction paradigm, we prove that truthfulness can be guaranteed by a price-based allocation rule and payment rule. Our truthfulness characterization actually converts the mechanism design problem into an online algorithm design problem, with a marginal pricing function for resources as variables set by cloud storage service providers for online procurement auction. We derive the marginal pricing function for the online algorithm. We also prove the competitive ratio of the social cost of our algorithm against that of the offline VCG mechanism and of the resource pooling cost of our algorithm against that of the offline optimal auction. Simulation studies driven by real-world traces are conducted to show the efficacy of our online auction mechanism.

Datacenter demand response is envisioned as a promising tool for mitigating operational stability issues faced by smart grids. It enables significant potentials in peak load reduction and facilitates the incorporation of distributed generation. Monetary refund from the smart grid can also alleviate the cloud's burden in escalating electricity cost. However, the current demand response paradigm is inefficient towards incentivizing a cloud that runs over geo-distributed datacenters. Leveraging auction theory, this work presents an efficient incentive mechanism to elicit demand response from geo-distributed clouds. To determine the winning bids and their corresponding payments, the cloud that acts as the auctioneer needs to solve a set of winner determination problems that are highly challenging. By integrating techniques from the Gibbs sampling method and the alternating direction method of multipliers, we propose a decentralized algorithm for each datacenter to make autonomous decisions on winning bid selection and workload management, striking a balance among the economic efficiency, truthfulness and the computational efficiency. Through extensive trace-driven evaluations, we demonstrate that our incentive mechanism constitutes a win-win mechanism for both the geo-distributed cloud and the smart grid.

The quintessential problem in a smart grid is the matching between power supply and demand - a perfect balance across the temporal domain, for the stable operation of the power network. Recent studies have revealed the critical role of electricity storage devices, as exemplified by rechargeable batteries and plug-in electric vehicles (PEVs), in helping achieve the balance through power arbitrage. Such potential from batteries and PEVs can not be fully realized without an appropriate economic mechanism that incentivizes energy discharging at times when supply is tight. This work aims at a systematic study of such demand response problem in storage-assisted smart grids through a well-designed online procurement auction mechanism. The long-term social welfare maximization problem is naturally formulated into a linear integer program. We first apply a primal-dual optimization algorithm to decompose the online auction design problem into a series of one-round auction design problems, achieving a small loss in competitive ratio. For the one round auction, we show that social welfare maximization is still NP-hard, and design a primal-dual approximation algorithm that works in concert with the decomposition algorithm. The end result is a truthful power procurement auction that is online, truthful, and 2-competitive in typical scenarios.

Vector linear network coding (LNC) is a generalization of the conventional scalar LNC, such that the data unit transmitted on every edge is an L-dimensional vector of data symbols over a base field GF(q). There are classical exemplifying multi-source networks that have simple vector linear solutions but no scalar linear solutions over any field. For (single-source) multicast networks, a popular conjecture characterizes the following benefit of vector LNC over scalar LNC in terms of alphabet size of data units: there exist multicast networks that are vector linearly solvable of dimension L over GF(q) but not scalar linearly solvable over any field of size q' ≤ qL. This paper introduces a general method to construct such a network, and subsequently constructs the first examples to affirm the positive answer of this conjecture. Moreover, among these exemplifying networks vector linearly solvable of dimension L over GF(q), there are instances with the additional property that even for some extremely large q' > qL, they are still not scalar linearly solvable over GF(q').

Reducing servers' power usage in data centers upon utility's request has been emerging as a valuable demand response resource for enhancing power grid's efficiency and reliability, especially during emergency events (e.g., extreme weather) that result in electricity production shortage and put the grid in jeopardy. Nonetheless, for demand response in multi-tenant colocation data centers, operators may have to leverage expensive and environmentally-unfriendly diesel generation, because individual tenants manage their own servers' power usage without coordination and are typically charged by data center operators based on fixed power contracts that provide no incentives for demand response. This paper focuses on emergency demand response (EDR) and proposes an auction-based incentive mechanism, called FairDR, that incentivizes and coordinates tenants' energy reduction through financial rewards for enabling cost-effective and low-carbon EDR in colocation data center. FairDR decides tenants' energy reduction online without knowing a priori the future energy reduction requirements. It is proved that FairDR ensures tenants' truthfulness in the auction process, attains a bounded overall cost saving compared to the offline optimum which knows all the demands, and guarantees fairness (i.e., similar rewards are offered if tenants reduce the same amount of energy) that is largely absent in the existing auction mechanisms. Finally, trace-driven simulations are performed to validate our analysis and demonstrate that FairDR outperforms the existing mechanisms by improving fairness and achieving a good cost saving that is comparable to the offline optimum.

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

Small-cell architecture is widely adopted by cellular network operators to increase network capacity. By reducing the size of cells, operators can pack more (low-power) base stations in an area to better serve the growing demands, without causing extra interference. However, this approach suffers from low spectrum temporal efficiency. When a cell becomes smaller and covers fewer users, its total traffic fluctuates significantly due to insufficient traffic aggregation and exhibiting a large "peak to-mean" ratio. As operators customarily provision spectrum for peak traffic, large traffic temporal fluctuation inevitably leads to low spectrum temporal efficiency. In this work, we first carryout a case-study based on real-world 3G data traffic traces and confirm that 90% of the cells in a metropolitan district are less than 40% utilized. Our study also reveals that peak traffic of adjacent cells are highly asynchronous. Motivated by these observations, we advocate device-to-device (D2D) load-balancing as a useful mechanism to address the fundamental drawback of small-cell architecture. The idea is to shift traffic from a congested cell to its adjacent under-utilized cells by leveraging inter-cell D2D communication, so that the traffic can be served without using extra spectrum, effectively improving the spectrum temporal efficiency. We provide theoretical modeling and analysis to characterize the benefit of D2D load balancing, in terms of sum peak traffic reduction of individual cells. We also derive the corresponding cost, in terms of incurred D2D traffic overhead. We carry out empirical evaluations based on real-world 3G data traces to gauge the benefit and cost of D2D load balancing under practical settings. The results show that D2D load balancing can reduce the sum peak traffic of individual cells by 35% as compared to the standard scenario without D2D load balancing, at the expense of 45% D2D traffic overhead.

Mobile multicast has been deployed in telecommunication networks for information dissemination applications such as IPTV and video conferencing. Recent studies of mobile multicast focused on fast handover protocols, and algorithms for multicast tree management have witnessed little improvement over the years. Shortest path trees represent the status quo of multicast topology in real-world systems. Steiner trees were investigated extensively in the theory community and are known to be bandwidth efficient, but come with an associated complexity. Recent developments in the Software Defined Networking (SDN) paradigm have shed light on implementing more sophisticated protocols for better routing performance. We propose an SDN-based design to combat the complexity vs. Performance dilemma in mobile multicast. We construct low-cost Steiner trees for multicastin a mobile network, employing an SDN controller for coordinating tree construction and morphing. Highlights of our design include a set of efficient online algorithms for tree adjustment when nodes arrive and depart on the fly, and an SDN rule update framework based on constraints expressed by boolean logic to ensure loop free rule updates. The algorithms are proven to achieve a constant competitive ratio against the offline optimal Steiner tree, with an amortized constant number of edge swaps per adjustment. Mininet-based implementation and evaluation further validate the efficacy of our design.

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

This work studies the online electricity cost minimization problem at a co-location data center. A co-location data center serves multiple tenants who rent the physical infrastructure within the data center to run their respective cloud computing services. Consequently, the co-location operator has no direct control over power consumption of its tenants, and an efficient mechanism is desired for eliciting desirable consumption patterns from the co-location tenants. Electricity billing faced by a data center is nowadays based on both the total volume consumed and the peak consumption rate. This leads to an interesting new combinatorial optimization structure on the electricity cost optimization problem, which also exhibits an online nature due to the definition of peak consumption. We model and solve the problem through two approaches: the pricing approach and the auction approach. For the former, we design an offline 2-approximation algorithm as well as an online algorithm with a small competitive ratio in most practical settings. For the latter, we design an efficient (2+c)-competitive online algorithm, where c is a system dependent parameter close to 1.49, and then convert it into an efficient mechanism that executes in an online fashion, runs in polynomial time, and guarantees truthful bidding and (2+2c)-competitive in social cost.

Datacenter demand response is envisioned as a promising approach for mitigating operational instability faced by smart grids. It enables significant potentials in peak load shedding and facilitates the incorporation of distributed generation and intermittent energy sources. This work considers two key aspects towards realtime electricity pricing for eliciting demand response: (i) Two-way electricity flow between smart grids and large datacenters with hybrid green generation capabilities. (ii) The geo-distributed nature of large cloud systems, and hence the potential competition among smart grids that serve different datacenters of the cloud. We propose a pricing scheme tailored for geo-distributed green datacenters, from a multi-leader single-follower game point of view. At the cloud side, in quest for performance, scalability and robustness, the energy cost is minimized in a distributed manner, based on the technique of alternating direction of multipliers (ADMM). At the smart grid side, a practical equilibrium of the pricing game is desired. To this end, we employ mathematical programming with equilibrium constraints (MPEC), equilibrium problem with equilibrium constraints (EPEC) and exact linearization, to transform the multi-leader single-follower pricing game into a mixed integer linear program (MILP) that can be readily solved. The effectiveness of the proposed solutions is evaluated based on trace-driven simulations.

This work studies the online electricity cost minimization problem at a co-location data center, which serves multiple tenants who rent the physical infrastructure within the data center to run their respective cloud computing services. The co-location operator has no direct control over power consumption of its tenants, and an efficient mechanism is desired for eliciting desirable consumption patterns from the tenants. Electricity billing faced by a data center is nowadays based on both the total volume consumed and the peak consumption rate. This leads to an interesting new combinatorial optimization structure on the electricity cost optimization problem, which also exhibits an online nature due to the definition of peak consumption. We model and solve the problem through two approaches: the pricing approach and the auction approach, and design online algorithms with small competitive ratios.

The smart grid is a modern power grid that achieves high efficiency and robustness through sophisticated information and communications technology. Demand response has great potential in helping balance demand and supply in a smart grid, cutting generation cost and carbon footprint, and improving system stability. Auctions represent a natural and efficient approach for carrying out demand response between the power grid and large electricity users, microgrids, and electricity storage devices. This work explores the modeling and design space of demand response auctions, targeting expressive power, truthful information revelation, computational efficiency, and economic efficiency. We present a randomized auction that explores the underlying problem structure of demand response, and prove that it is truthful, runs in polynomial time, and achieves (1 + ϵ)-optimal social cost for an arbitrarily small constant ϵ. The key technique lies in the marriage of smoothed analysis and randomized reduction, which makes its debut in this work among literature on mechanism design, and can be applied to problems where social welfare optimization is NP-hard but admits a smoothed polynomial-time algorithm.

In an acyclic multicast network, it is well known that a linear network coding solution over GF(q) exists when q is sufficiently large. In particular, for each prime power q no smaller than the number of receivers, a linear solution over GF(q) can be efficiently constructed. In this paper, we reveal that a linear solution over a given finite field does not necessarily imply the existence of a linear solution over all larger finite fields. In particular, we prove by construction that: 1) for every ω ≥ 3, there is a multicast network with source outdegree ω linearly solvable over GF(7) but not over GF(8), and another multicast network linearly solvable over GF(16) but not over GF(17); 2) there is a multicast network linearly solvable over GF(5) but not over such GF(q) that q > 5 is a Mersenne prime plus 1, which can be extremely large; 3) a multicast network linearly solvable over GF(qm1) and over GF(qm2) is not necessarily linearly solvable over GF(qm1+m2); and 4) there exists a class of multicast networks with a set T of receivers such that the minimum field size qminfor a linear solution over GF(qmin) is lower bounded by O(√|T|), but not every larger field than GF(qmin) suffices to yield a linear solution. The insight brought from this paper is that not only the field size but also the order of subgroups in the multiplicative group of a finite field affects the linear solvability of a multicast network.

Opportunistic wireless channel access granted to non-licensed users through auctions represents a promising approach for effectively distributing and utilizing the scarce wireless spectrum. A limitation of existing spectrum auction designs lies in the over-simplifying assumption that every non-licensed secondary user is a single node or single-hop network. For the first time in the literature, we propose to model non-licensed users as secondary networks (SNs), each of which comprises of a multihop network with end-to-end routing demands. We use simple examples to show that such auctions among SNs differ drastically from simple auctions among single-hop users, and previous solutions suffer from local, per-hop decision making. We first design a simple, heuristic auction that takes inter-SN interference into consideration and is truthful. We then design a randomized auction framework based on primal-dual linear optimization, which is automatically truthful and achieves a social welfare approximation ratio that matches one achieved by cooperative optimization assuming truthful bids for free. The framework relieves a spectrum auction designer from worrying about truthfulness of the auction, so that he or she can focus on social welfare maximization while assuming truthful bids for free.

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

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

In a cloud market, the cloud provider provisions heterogeneous virtual machine (VM) instances from its resource pool, for allocation to cloud users. Auction-based allocations are efficient in assigning VMs to users who value them the most. Existing auction design often overlooks the heterogeneity of VMs, and does not consider dynamic, demand-driven VM provisioning. Moreover, the classic VCG auction leads to unsatisfactory seller revenues and vulnerability to a strategic bidding behavior known as shill bidding. This work presents a new type of core-selecting VM auctions, which are combinatorial auctions that always select bidder charges from the core of the price vector space, with guaranteed economic efficiency under truthful bidding. These auctions represent a comprehensive three-phase mechanism that instructs the cloud provider to judiciously assemble, allocate, and price VM bundles. They are proof against shills, can improve seller revenue over existing auction mechanisms, and can be tailored to maximize truthfulness.

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

Space Information Flow (SIF) is a new research paradigm that studies network coding in a geometric space, which is different with Network Information Flow (NIF) that studies network coding in a graph. One of the key open problems at the core of SIF is to design an algorithm that computes optimal SIF solutions. A new heuristic SIF algorithm based on non-uniform recursive space partitioning is proposed in this work, for computing SIF for any density distribution of given terminal nodes in 2-D Euclidean space. Simulation results show that the new algorithm has low computational complexity and converges to optimal solutions promptly.

Network coding encourages the mixing of information flows at intermediate nodes of a network for enhanced network capacity, especially for one-to-many multicast applications. A fundamental problem in multicast network coding is to construct a feasible solution such that encoding and decoding are performed over a finite field of size as small as possible. Coding operations over very small finite fields (e.g., F2) enable low computational complexity in theory and ease of implementation in practice. In this work, we propose a new approach based on matroid theory to study multicast network coding and its minimum field size requirements. Applying this new approach that translates multicast networks into matroids, we derive the first upper-bounds on the field size requirement based on the number of relay nodes in the network, and make new progresses along the direction of proving that coding over very small fields (F2and F3) suffices for multicast network coding in planar networks.

In a cognitive radio network, selfish secondary users may not voluntarily contribute to desired cooperative sensing. We design the first fully distributed scheme to incentivize participation of nodes in cooperative sensing, by connecting sensing and spectrum allocation, and offering incentive from latter to the former. Secondary users that are more active and report more accurate sensing values will be given higher reputation values, which results in lower prices in the spectrum allocation phase. Theoretical analysis and simulation results indicate that the proposed method effectively incentivizes sensing participation, and rewards truthful and accurate reporting. Our proposed system is fully distributed and does not rely on a central authority, and so is more applicable in dynamic cognitive radio networks in practice. We also show how to improve the robustness of reputation when malicious nodes report spurious reputation.

This work studies resource allocation in a cloud market through the auction of Virtual Machine (VM) instances. It generalizes the existing literature by introducing combinatorial auctions of heterogeneous VMs, and models dynamic VM provisioning. Social welfare maximization under dynamic resource provisioning is proven NP-hard, and modeled with a linear integer program. An efficient α-approximation algorithm is designed, with α ~ 2.72 in typical scenarios. We then employ this algorithm as a building block for designing a randomized combinatorial auction that is computationally efficient, truthful in expectation, and guarantees the same social welfare approximation factor α. A key technique in the design is to utilize a pair of tailored primal and dual LPs for exploiting the underlying packing structure of the social welfare maximization problem, to decompose its fractional solution into a convex combination of integral solutions. Empirical studies driven by Google Cluster traces verify the efficacy of the randomized auction.

This work studies how to minimize the bandwidth cost for uploading deferral big data to a cloud computing platform, for processing by a MapReduce framework, assuming the Internet service provider (ISP) adopts the MAX contract pricing scheme. We first analyze the single ISP case and then generalize to the MapReduce framework over a cloud platform. In the former, we design a Heuristic Smoothing algorithm whose worst-case competitive ratio is proved to fall between 2−1/(D+1) and 2(1 − 1/e), where D is the maximum tolerable delay. In the latter, we employ the Heuristic Smoothing algorithm as a building block, and design an efficient distributed randomized online algorithm, achieving a constant expected competitive ratio. The Heuristic Smoothing algorithm is shown to outperform the best known algorithm in the literature through both theoretical analysis and empirical studies. The efficacy of the randomized online algorithm is also verified through simulation studies.

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

In an acyclic multicast network, it is well known that a linear network coding solution over GF(q) exists when q is sufficiently large. In particular, for each prime power q no smaller than the number of receivers, a linear solution over GF(q) can be efficiently constructed. In this work, we reveal that a linear solution over a given finite field does not necessarily imply the existence of a linear solution over all larger finite fields. Specifically, we prove by construction that: (i) For every source dimension no smaller than 3, there is a multicast network linearly solvable over GF(7) but not over GF(8), and there is another multicast network linearly solvable over GF(16) but not over GF(17); (ii) There is a multicast network linearly solvable over GF(5) but not over such GF(q) that q > 5 is a Mersenne prime plus 1, which can be extremely large.

We study online cloud resource auctions where users can arrive anytime and bid for heterogeneous types of virtual machines (VMs) assembled and provisioned on the fly. The proposed auction mechanism RSMOA, to the authors' knowledge, represents the first truthful online mechanism that timely responds to incoming users' demands and makes dynamic resource provisioning and allocation decisions, while guaranteeing efficiency in both the provider's revenue and system social welfare. RSMOA consists of two components: (1) an online mechanism that computes resource allocation and users' payments based on a global, non-decreasing pricing curve, and guarantees truthfulness; (2) a judiciously designed pricing curve, which is derived from a threat-based strategy and guarantees a competitive ratio O(ln(p)) in both system social welfare and the provider's revenue, as compared to the celebrated offline Vickrey-Clarke-Groves (VCG) auction. Here p is the ratio between the upper and lower bounds of users' marginal valuation of a type of resource. The efficacy of RSMOA is validated through extensive theoretical analysis and trace-driven simulation studies.

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

This work studies electricity markets between power grids and microgrids, an emerging paradigm of electric power generation and supply. It is among the first that addresses the economic challenges arising from such grid integration, and represents the first power auction mechanism design that explicitly handles the Unit Commitment Problem (UCP), a key challenge in power grid optimization previously investigated only for centralized cooperative algorithms. The proposed solution leverages a recent result in theoretical computer science that can decompose an optimal fractional (infeasible) solution to NP-hard problems into a convex combination of integral (feasible) solutions. The end result includes randomized power auctions that are (approximately) truthful and computationally efficient, and achieve small approximation ratios for grid-wide social welfare under UCP constraints and temporal demand correlations. Both power markets with grid-to-microgrid and microgrid-to-grid energy sales are studied, with an auction designed for each, under the same randomized power auction framework. Trace driven simulations are conducted to verify the efficacy of the two proposed inter-grid power auctions.

In a secondary spectrum market, the utility of a secondary user often depends on not only whether it wins, but also which channels it wins. Combinatorial auctions are a natural fit here to allow secondary users to bid for combinations of channels. In this context, the VCG mechanism constitutes a generic auction that uniquely guarantees both truthfulness and efficiency. There also exists related auction design that relaxes efficiency due to perceived complexity issues, and focuses on truthfulness. Starting with new empirical evidences on the complexity issue, we propose to design core-selecting auctions instead, which resolve VCG's vulnerability to collusion and shill bidding, and improve seller revenue. While the VCG type of auctions are unique in guaranteeing both efficiency and truthfulness, we prove that our core-selecting auctions are unique in guaranteeing both efficiency and shill-proofness, and always outperform VCG auctions in terms of seller revenue generated. Employing linear programming and quadratic programming techniques, we design two payment rules for minimizing the incentives of bidders to deviate from truth telling.

Network coding encourages information flow mixing in a network. It helps increase the throughput and reduce the cost of data transmission, especially for one-to-many multicast applications. An interesting problem is to understand and quantify the coding advantage and cost advantage, i.e., the potential benefits of network coding, as compared to routing, in terms of increasing throughput and reducing transmission cost, respectively. Two classic network models were considered in previous studies: directed networks and undirected networks. This work further focuses on two types of parameterized networks, including bidirected networks and hyper-networks, generalizing the directed and the undirected network models, respectively. We prove upper- and lower-bounds on multicast coding advantage and cost advantage in these models.

The multiple-unicast network coding conjecture states that for multiple unicast sessions in an undirected network, network coding is equivalent to routing. Simple and intuitive as it appears, the conjecture has remained open since its proposal in 2004, and is now a well-known unsolved problem in the field of network coding. Based on a recently proposed tool of space information flow, we present a geometric framework for analyzing the multiple-unicast conjecture. The framework consists of four major steps, in which the conjecture is transformed from its throughput version to cost version, from the graph domain to the space domain, and then from high dimension to 1-D, where it is to be eventually proved. We apply the geometric framework to derive unified proofs to known results of the conjecture, as well as new results previously unknown. A possible proof to the conjecture based on this framework is outlined.

Network coding encourages information coding across a communication network. While the necessity, benefit and complexity of network coding are sensitive to the underlying graph structure of a network, existing theory on network coding often treats the network topology as a black box, focusing on algebraic or information theoretic aspects of the problem. This paper aims at an in-depth examination of the relation between algebraic coding and network topologies. We mathematically establish a series of results along the direction of: if network coding is necessary/beneficial, or if a particular finite field is required for coding, then the network must have a corresponding hidden structure embedded in its underlying topology, and such embedding is computationally efficient to verify. Specifically, we first formulate a meta-conjecture, the NC-minor conjecture, that articulates such a connection between graph theory and network coding, in the language of graph minors. We next prove that the NC-minor conjecture for multicasting two information flows is almost equivalent to the Hadwiger conjecture, which connects graph minors with graph coloring. Such equivalence implies the existence of K4, K5, K6, and KO(q/log q) minors, for networks that require F3, F4, F5, and Fqto multicast two flows, respectively. We finally prove that, for the general case of multicasting arbitrary number of flows, network coding can make a difference from routing only if the network contains a K4minor, and this minor containment result is tight. Practical implications of the above results are discussed.

Cognitive radio techniques represent an emerging approach for mitigating the spectrum scarcity problem in wireless communications. Cooperative sensing is an effective solution to improve sensing accuracy and robustness in the presence of fading and shadowing that make individual sensing less reliable. However, when an adversary can corrupt some nodes in the network, the effectiveness of cooperative sensing may degrade dramatically. We design the first fully distributed security scheme ReDiSen to counter attacks in cooperative sensing. We apply reputation generated from exchanged sensing results as an aid to restrict the impact of the malicious behaviours. Both theoretical analysis and simulation results indicate that ReDiSen provides an effective countermeasure against security attacks by enabling secondary users to obtain more accurate cooperative sensing results in adversarial environments. ReDiSen does not rely on a central authority, nor a common control channel, and is therefore more applicable in dynamic cognitive radio networks.

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

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

Network Coding encourages information coding across a communication network. While the necessity, benefit and complexity of network coding are sensitive to the underlying graph structure of a network, existing theory on network coding often treats the network topology as a black box, focusing on algebraic or information theoretic aspects of the problem. This work aims at an in-depth examination of the relation between algebraic coding and network topologies. We mathematically establish a series of results along the direction of: if network coding is necessary/beneficial, or if a particular finite field is required for coding, then the network must have a corresponding hidden structure embedded in its underlying topology, and such embedding is computationally efficient to verify. Specifically, we first formulate a meta-conjecture, the NC-Minor Conjecture, that articulates such a connection between graph theory and network coding, in the language of graph minors. We next prove that the NC-Minor Conjecture is almost equivalent to the Hadwiger Conjecture, which connects graph minors with graph coloring. Such equivalence implies the existence of K4, K5, K6, and KO(q/ log q)minors, for networks requiring F3, F4, F5and Fq, respectively. We finally prove that network coding can make a difference from routing only if the network contains a K4minor, and this minor containment result is tight. Practical implications of the above results are discussed.

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

In a secondary spectrum market, the utility of a secondary user often depends on not only whether it wins, but also which channels it wins. Combinatorial auctions are a natural fit here to allow secondary users to bid for combinations of channels. In this context, the VCG mechanism constitutes a generic auction that uniquely guarantees both truthfulness and efficiency, but it is vulnerable to shill bidding and generates low revenue. In this paper, without compromising efficiency, we propose to design core-selecting auctions instead, which resolves VCG's vulnerability and improves seller revenue. We prove that in a secondary spectrum market, the revenue gleaned from a core-selecting auction is at least that of the VCG mechanism, and shills are not profitable to bidders. Employing linear programming and quadratic programming techniques, we design two payment rules suitable for our core-selecting auction, which aim to minimize the incentives of bidders to deviate from truthful-telling. Our extensive simulation results show that the revenues can be largely increased due to spectrum sharing.

Matroidal networks play a fundamental role in proving theoretical results on the limits of network coding. This can be explained by the underlying connections between network coding and matroid theory, both of which build upon the fundamental concept of independence. Two existing methods are known in the network coding literature for constructing networks from a matroid. The method due to Dougherty et al. [5] is high in time complexity but can create relatively simple network structures from a given matroid. Another method due to El Rouayheb et al. [3] is low in time complexity, but results in rather complex network structures. This work studies the design of matroidal networks from uniform matroids, targetting both low time complexity and minimum network sizes. Our construction is based on the new technique of dependence deduction, which may serve as a promising direction for constructing general matroidal networks. Some of our constructions lead to new networks for understanding network coding in terms of base field requirement.

Broadcasting systems such as P2P streaming systems represent important network applications that support up to millions of online users. An efficient broadcasting mechanism is at the core of the system design. Despite substantial efforts on developing efficient broadcasting algorithms, the following important question remains open: How to achieve the maximum broadcast rate in a distributed manner with each user maintaining information queues only for its direct neighbors? In this work, we first derive an innovative formulation of the problem over acyclic overlay networks with arbitrary underlay capacity constraints. Then, based on the formulation, we develop a distributed algorithm to achieve the maximum broadcast rate and every user only maintains one queue per-neighbor. Due to its lightweight nature, our algorithm scales very well with the network size and remains robust against high system dynamics. Finally, by conducting simulations we validate the optimality of our algorithm under different network capacity models. Simulation results further indicate that the convergence time of our algorithm grows linearly with the network size, which suggests an interesting direction for future investigation.

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

Dynamic spectrum access by non-licensed users has emerged as a promising solution to address the bandwidth scarcity challenge. In a secondary spectrum market, primary users lease chunks of unused spectrum to secondary users. Auctions perform as one of the natural mechanisms for allocating the spectrum, generating an economic incentive for the licensed user to relinquish channels. Existing spectrum auction designs, while taking externality introduced by interference into account, fail to consider the potential mobility of secondary users, which leads to another dimension of externality: mobile communication motivates a secondary user to exclusively occupy a channel, i.e., forbidding channel reuse in its mobility region. In this work, we design two expressive auctions for mobility support, by introducing two-dimensional bids that reject a secondary user's willingness to pay for exclusive and non-exclusive channel usage, for the single-channel and multiple-channel scenarios, respectively. In the outcome of our 2D auctions, a channel is either monopolized or simultaneously reused without interference, whereas a secondary user can be mobile or is regulated to be static. We prove the existence of desirable equilibria in both auctions, where 1/10 and c/7(1+c) of optimal social welfare are guaranteed to be recoverable, respectively (c is the number of channels).

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

We apply signal alignment (SA), a wireless communication technique that enables physical layer network coding (PNC) in multi-input multi-output (MIMO) wireless networks. Through calculated precoding, SA contracts the perceived signal space at a node to match its receive capability, and hence facilitates the demodulation of linearly combined data packets. PNC coupled with SA (PNC-SA) has the potential of fully exploiting the precoding space at the senders, and can better utilize the spatial diversity of a MIMO network for higher system degrees-of-freedom (DoF). PNC-SA adopts the idea of `demodulating a linear combination' from PNC. The design of PNC-SA is also inspired by recent advances in IA, though SA aligns signals not interferences. We study the optimal precoding and power allocation problem of PNC-SA, for SNR (singal-to-noise-ratio) maximization at the receiver. The mapping from SNR to BER is then analyzed, revealing that the DoF gain of PNC-SA does not come with a sacrifice in BER. We then design a general PNC-SA algorithm in larger systems, and demonstrate general applications of PNC-SA, and show via network level simulations that it can substantially increase the throughput of unicast and multicast sessions, by opening previously unexplored solution spaces in multi-hop MIMO routing.

NanoNets are networks of nanomachines at extremely small dimensions, on the order of nanometers or micrometers. Recent advances in physics and engineering have made basic computing and communication feasible on nanomachines, and NanoNets are envisioned as an important emerging technology with broad future applications. Traditional networking solutions require significant modifications for application in NanoNets. In this paper, we focus on routing algorithm design in NanoNets. Based on the salient features of a NanoNet, including low node cost and very low available power, we propose a new routing paradigm for multi-hop data transmission in NanoNets. Our design, termed {\em Buddy Routing (BR)}, is enabled by latest advancements in physical layer network coding, and argues for pair-to-pair data forwarding in place of traditional node-to-node data forwarding. Through both analysis and simulations, we compare BR with point-to-point routing, in terms of raw throughput, error rate, energy efficiency, and protocol overhead, and show the advantages of BR in NanoNets.

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

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

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

Network coding is a technique that allows information flows to be encoded while routed across a data network. It was shown that network coding helps increase the throughput and reduce the cost of data transmission, especially for one-to-many multicast applications. An important direction in network coding research is to understand and quantify the coding advantage and cost advantage, i.e., the potential benefits of network coding, as compared to routing, in terms of increasing throughput and reducing transmission cost, respectively. Two classic network models were considered in previous studies of coding advantage: directed networks and undirected networks. The study of coding advantage in this work further focuses on two types of parameterized networks, including bidirected networks and hyper-networks, which generalizes the directed and the undirected network models, respectively. With proper parameter setting, more realistic modeling of networks in practice can be achieved. We prove upper-bounds and lower-bounds on the coding advantage for multicast in these models. Some of our bounds are new and unknown before, some improve upon previously proven bounds, and some answer open questions in the literature.

Opportunistic wireless channel access by non-licensed users has emerged as a promising solution for addressing the bandwidth scarcity challenge. Auctions represent a natural mechanism for allocating the spectrum, generating an economic incentive for the licensed user to relinquish channels. A severe limitation of existing spectrum auction designs lies in the over-simplifying assumption that every non-licensed user is a single-node or single-link secondary user. While such an assumption makes the auction design easier, it does not capture practical scenarios where users have multihop routing demands. For the first time in the literature, we propose to model non-licensed users as secondary networks (SNs), each of which comprises of a multihop network with end-to-end routing demands. We aim to design truthful auctions for allocating channels to SNs in a coordinated fashion that maximizes social welfare of the system. We use simple examples to show that such auctions among SNs differ drastically from simple auctions among single-hop users, and previous solutions suffer severely from local, per-hop decision making. We first design a simple, heuristic auction that takes inter-SN interference into consideration, and is truthful. We then design a randomized auction based on primal-dual linear optimization, with a proven performance guarantee for approaching optimal social welfare. A key technique in our solution is to decompose a linear program (LP) solution for channel assignment into a set of integer program (IP) solutions, then applying a pair of tailored primal and dual LPs for computing probabilities of choosing each IP solution. We prove the truthfulness and performance bound of our solution, and verify its effectiveness through simulation studies.

The multiple unicast network coding conjecture states that for multiple unicast in an undirected network, network coding is equivalent to routing. Simple and intuitive as it appears, the conjecture has remained open since its proposal in 2004 [1], [2], and is now a well-known unsolved problem in the field of network coding. In this work, we provide a proof to the conjecture in its space/geometric version. Space information flow is a new paradigm being proposed [3], [4]. It studies the transmission of information in a geometric space, where information flows are free to propagate along any trajectories, and may be encoded wherever they meet. The goal is to minimize a natural bandwidth-distance sum-product (network volume), while sustaining end-to-end unicast and multicast communication demands among terminals at known coordinates. The conjecture is true in networks only if it is true in space. Our main result is that network coding is indeed equivalent to routing in the space model. Besides its own merit, this partially verifies the original conjecture, and further leads to a geometric framework [5] for a hopeful proof to the conjecture.

Space information flow is a new field of research recently proposed by Li and Wu [1], [2]. It studies the transmission of information in a geometric space, where information flows can be routed along any trajectories, and can be encoded wherever they meet. The goal is to satisfy given end-to-end unicast/multicast throughput demands, while minimizing a natural bandwidth-distance sum-product (network volume). Space information flow models the design of a blueprint for a minimum-cost network. We study the multicast version of the space information flow problem, in Euclidean spaces. We present a simple example that demonstrates the design of an information network is indeed different from that of a transportation network. We discuss properties of optimal multicast network embedding, prove that network coding does not make a difference in the basic case of 1-to-2 multicast, and prove upper-bounds on the number of relay nodes required in an optimal acyclic multicast network.

One highly-scalable approach to content delivery is to harness the upload bandwidth of the clients. Peer-assisted content delivery systems have been shown to effectively offload the servers of popular files, as the request rates of popular content enable the formation of self-sustaining torrents, where the entire content of the file is available among the peers themselves. However, for less popular files, these systems are less helpful in offloading servers. With a long tail of mildly popular content, with a high aggregate demand, a large fraction of the file requests must still be handled by servers. In this paper, we present the design, implementation, and evaluation of a dynamic file bundling system, where peers are requested to download content which they may not otherwise download in order to “inflate” the popularity of less popular files. Our system introduces the idea of a super bundle, which consists of a large catalogue of files. From this catalogue, smaller bundles, consisting of a small set of files, can dynamically be assigned to individual users. The system can dynamically adjust the number of downloaders of each file and thus enables the popularity inflation to be optimized according to current file popularities and the desired tradeoff between download times and server resource usage. The system is evaluated on PlanetLab.

Barrier coverage problems in sensor networks involve detecting intruders that attempt to cross a region of interest. In this paper, we formulate the k-connect barrier count problem for Mixed Sensor Networks (MSNs). The k-connect barrier count problem is to find the maximum number of barriers in an arbitrary MSN where at most k distinct mobile sensors can be used to construct any given virtual edge used in a barrier. We present the solution for the k-connect barrier count problem for k ∈ {0, 1, 2} via Integer Linear Programming. Using simulation results, we show that as k increases, the density of sensors required to achieve barrier coverage decreases. The results quantitatively demonstrate the benefits of mobile sensors.

SUMMARY Homomorphic hash functions play a key role in securing distributed systems that use coding techniques such as erasure coding and network coding. The computational complexity of homomorphic hash functions remains a main challenge. In this paper, we present a massively parallel solution, named Tsunami, by exploiting the widely available many‐core graphic processing units (GPUs). Tsunami includes the following optimization techniques to achieve the highest ever hashing throughput: (1) using Montgomery multiplication and precomputation to speed up modular exponentiations; (2) using a clean implementation of Montgomery multiplication in order to decrease the demand of registers and shared memory and increase the utilization ratio of GPU processing cores; (3) using our own assembly code to implement the 32‐bit integer multiplication, which outperforms the assembly codes generated by the native compiler by 20%; and (4) exploiting memory alignment and constant memory on GPUs to improve the efficiency of memory access. Integrating the above techniques, our Tsunami achieves a significant improvement over existing results. Specifically, the hashing throughput achieved by Tsunami on a GTX295 GPU (NVIDIA, Santa Clara, CA, US) is about 33 times that of the existing solution on a quad‐core CPU. We also show that the hashing throughput grows almost linearly with the number of GPU cores. Copyright © 2011 John Wiley & Sons, Ltd.

We refer to network coding schemes in which information flows propagate along a combination network topology as combination network coding (CNC). CNC and its variations are the first network coding schemes studied in the literature, and so far still represent arguably the most important class of known structures where network coding is nontrivial. Our main goal in this paper is to seek a thorough understanding on the advantage of CNC in undirected networks, by proving a tight bound on its potential both in improving multicast throughput (the coding advantage) and in reducing multicast cost under a linear link flow cost model (the cost advantage). We prepare three results towards this goal. First, we show that the cost advantage of CNC is upper-bounded by 9/8 under the uniform link cost setting. Second, we show that achieving a larger cost advantage is impossible by considering an arbitrary instead of uniform link cost configuration. Third, we show that in a given network topology, for any form of network coding, the coding advantage under arbitrary link capacity configurations is always upper-bounded by the cost advantage under arbitrary link cost configurations. Combining the three results together, we conclude that the potential for CNC to improve throughput and to reduce routing cost are both upper-bounded by a factor of 9/8. The bound is tight since it is achieved in specific networks. This result can be viewed as a natural step towards improving the bound of 2 proved for the coding advantage of general multicast network coding.

The usage of network resources by content providers is commonly governed by Service-Level Agreements (SLA) between the content provider and the network service provider. Resource usage exceeding the limits specified in the SLA incurs the content provider additional charges, usually at a higher cost. Hence, the content provider's goal is to provision adequate resources in the SLA based on forecasts of future demand. We study capacity purchasing strategies when the content provider employs network coded multicast as the media delivery mechanism, with uncertainty in its future customer set explicitly taken into consideration. The latter requires the content provider to make capacity provisioning decisions based on market predictions and historical customer usage patterns. The probabilistic element suggests a stochastic optimization approach. We model this problem as a two-stage stochastic optimization problem with recourse. Such optimizations are #P-hard to solve directly, and we design two approximation algorithms for them. The first is a heuristic algorithm that exploits properties unique to network coding, so that only polynomial-time operations are needed. It performs well in general scenarios, but the gap from the optimal solution is not bounded by any constant in the worst case. This motivates our second approach, a sampling algorithm partly inspired from the work of Gupta et al. [2004a]. We employ techniques from duality theory in linear optimization to prove that the sampling algorithm provides a 3-approximation to the stochastic multicast problem. We conduct extensive simulations to illustrate the efficacy of both algorithms, and show that the performance of both is usually within 10% of the optimal solution in practice.

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

This paper studies the bottleneck link capacity under the Gaussian channel model in strongly connected random wireless ad hoc networks, withnnodes independently and uniformly distributed in a unit square. We assume that each node is equipped with two transceivers (one for transmission and one for reception) and allow all nodes to transmit simultaneously. We draw lower and upper bounds, in terms of bottleneck link capacity, for homogeneous networks (all nodes have the same transmission power level) and propose an energy-efficient power assignment algorithm (CBPA) for heterogeneous networks (nodes may have different power levels), with a provable bottleneck link capacity guarantee of Ω(Blog(1+1/√nlog2n)), whereBis the channel bandwidth. In addition, we develop a distributed implementation of CBPA withO(n2) message complexity and provide extensive simulation results.

In computer networks, multicast models a class of data dissemination applications, where a common data item is routed to multiple receivers simultaneously. The routing of multicast flows across the network may incur a cost, and such a cost is to be recovered from payments by receivers who enjoy the multicast service. In reality, a group of potential multicast receivers exist at different network locations. Each receiver has a valuation for receiving the multicast service, but such valuation is private information known to itself. A multicast scheme asks each potential receiver to report her valuation, then decides which subset of potential receivers to serve, how to route the multicast flow to them, and how much to charge each of them. A multicast scheme is stragegyproof if no receiver has incentive to lie about her true valuation. It is further group strategyproof if no group of colluding receivers has incentive to lie. We study multicast schemes that target group strategyproofness, in both directed and undirected networks. Our main results reveal that under group strategyproofness, a compromise is necessary in either routing optimality or budget balance. We also design multicast schemes that pursue maximum budget balance while guaranteeing group stragetyproofness and routing optimality.

Private P2P communities, as known as "BitTorrent Darknets" or "Private Trackers (PTs)", have received much attention in the research community recently. The downloading performance in PTs with high Seeder-to-Leecher Ratio (SLR) is much better than in public P2P communities because PTs deploy auxiliary Share Ratio Enhancement (SRE) mechanism. Nevertheless, though high SLR can benefit leechers, it will result in "Poor Downloading Motivation" problem to members who want to increase their share ratio in order to safely survive. This problem may discourage PT members' activity. To improve sustainability of PTs, we adopt Predator-Prey model in ecology to analysis high SLR phenomenon, study the optimal stable SLR range to PTs and solve the above problem. Experiments verify our model and provide insight to study PTs.

Dynamic spectrum allocation has proven promising for mitigating the spectrum scarcity problem. In this model, primary users lease chunks of under-utilized spectrum to secondary users, on a short-term basis. Primary users may need financial motivations to share spectrum, since they assume costs in obtaining spectrum licenses. Auctions are a natural revenue generating mechanism to apply. Recent design on spectrum auctions make the strong assumption that the primary user knows the probability distribution of user valuations. We study revenue-maximizing spectrum auctions in the more realistic prior-free setting, when information on user valuations is unavailable. A two-phase auction framework is constructed. In phase one, we design a strategyproof mechanism that computes a subset of users with an interference-free spectrum allocation, such that the potential revenue in the second phase is maximized. A tailored payment scheme ensures truthful bidding at this stage. The selected users then participate in phase two, where we design a randomized competitive auction and prove its strategyproofness through the argument of bid independence. Employing probabilistic techniques, we prove that our auction generates a revenue that is at least 1/3 of the optimal revenue, improving the best known ratio of 1/4 proven for similar settings.

Secondary spectrum access is emerging as a promising approach for mitigating the spectrum scarcity in wireless networks. Coordinated spectrum access for secondary users can be achieved using periodic spectrum auctions. Recent studies on such auction design mostly neglect the repeating nature of such auctions, and focus on greedily maximizing social welfare. Such auctions can cause subsets of users to experience starvation in the long run, reducing their incentive to continue participating in the auction. It is desirable to increase the diversity of users allocated spectrum in each auction round, so that a trade-off between social welfare and fairness is maintained. We study truthful mechanisms towards this objective, for both local and global fairness criteria. For local fairness, we introduce randomization into the auction design, such that each user is guaranteed a minimum probability of being assigned spectrum. Computing an optimal, interference-free spectrum allocation is NP-Hard; we present an approximate solution, and tailor a payment scheme to guarantee truthful bidding is a dominant strategy for all secondary users. For global fairness, we adopt the classic max-min fairness criterion. We tailor another auction by applying linear programming techniques for striking the balance between social welfare and max-min fairness, and for finding feasible channel allocations. In particular, a pair of primal and dual linear programs are utilized to guide the probabilistic selection of feasible allocations towards a desired tradeoff in expectation.

Peer-assisted content delivery systems can provide scalable download service for popular files. For mildly popular content, however, these systems are less helpful in offloading servers as the request rate for less popular files may not enable formation of self-sustaining torrents (where the entire content of the file is available among the peers themselves). As there typically is a long tail of mildly popular content, with a high aggregate demand, a large fraction of the file requests must still be handled by servers, and is not off-loadable to peers. Bundling approaches have been proposed where peers are requested to download content which they may not otherwise be interested in order to ``inflate'' the popularity of less popular files. We present the design and implementation of a dynamic bundling system, in which a large number of files may be bundled to form a super bundle. From this super bundle, smaller individual bundles, consisting of a small set of files, can dynamically be assigned to individual users. Our system has the capability to dynamically adjust the number of downloaders of each file, thus allowing popularity inflation to be optimized according to current file popularities.

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

Beamforming is a signal processing technique which is aimed at focusing the transmission energy in the desired direction through the use of antenna arrays and phase alignment. In this paper we explore the benefits of using distributed antenna beamforming in multi-hop sensor wireless networks. The major challenge in using distributed beamforming in ad hoc wireless networks is that the relative disposition of wireless devices cannot be controlled with high precision as required by antenna arrays. We develop several optimization techniques for antenna radiation pattern generation in multi-hop ad hoc settings and analyze their effectiveness through simulations. In particular, we propose an optimization scheme for single hop beampattern generation and then show how to utilize it in a multi-hop environment.

We propose signal alignment (SA), a new wireless communication technique that enables physical layer network coding (PNC) in multi-input multi-output (MIMO) wireless networks. Through calculated preceding, SA contracts the perceived signal space at a node to match its receive diversity, and hence facilitates the demodulation of linearly combined data packets. PNC coupled with SA (PNC-SA) has the potential of fully exploiting the preceding space at the senders, and can better utilize the spatial diversity of a MIMO network for higher transmission rates, outperforming existing techniques including MIMO or PNC alone, interference alignment (IA) and interference alignment and cancellation (IAC). PNC-SA adopts the seminal idea of 'demodulate a linear combination' from PNC. The design of PNC-SA is also inspired by recent advances in IA, though SA aligns signals not interferences. We study the optimal preceding and power allocation problem of PNC-SA, for SNR maximization at the receiver. The mapping from SNR to BER is then analyzed, revealing that the throughput gain of PNC-SA does not come with a sacrifice in BER. We finally demonstrate general applications of PNC-SA, and show via network level simulations that it can substantially increase the throughput of unicast and multicast sessions, by opening previously unexplored solution spaces in multi-hop MIMO routing.

According to the Gaussian channel model, the throughput of a wireless link (u, v) is B log(l + S/N) bps, where B is the channel bandwidth and S/N is the signal to noise ratio. Wireless links which are scheduled simultaneously add to the noise levels of each other and cause the overall network capacity to decrease. In this paper we consider a wireless ad hoc network with unicast or multicast routing and simultaneously transmitting nodes along the route. Our major goal is to increase the capacity of the unicast/multicast sessions when all the wireless links are scheduled simultaneously. In addition, we try to minimize the number of active nodes involved in the unicast/multicast session for the purpose of energy efficiency. We assume that all the nodes share the same transmission range if activated and propose several node activation schemes with provable asymptotic bounds on the capacity and energy efficiency of the induced communication graph. We verify our results by simulations.

Recent advances in network coding research dramatically changed the underlying structure of optimal multicast routing algorithms and made them efficiently computable. While most such algorithm design assumes a single file/layer being multicast, layered coding introduces new challenges into the paradigm due to its cumulative decoding nature. Layered coding is designed to handle heterogeneity in receiver capacities, and a node may decode layer k only if it successfully receives all layers in 1.. k . We show that recently proposed optimization models for layered multicast do not correctly address this challenge. We argue that in order to achieve the absolute maximum throughput (or minimum cost), it is necessary to decouple the application-layer throughput from network-layer throughput. In particular, a node should be able to receive a nonconsecutive layer or a partial layer even if it cannot decode and utilize it (e.g., for playback in media streaming applications). The rationale is that nodes at critical network locations need to receive data just for helping other peers. We present a mathematical programming model that addresses these challenges and achieves absolute optimal performance. Simulation results show considerable throughput gain (cost reduction) compared with previous models, in a broad range of network scenarios. We then provide a formal proof that the layered multicast problem is NP-complete. We design a randomized rounding algorithm to approximate the optimal layered multicast, and show the efficacy of our technique using simulations. We then proceed to further generalize our model by studying the optimal progression of layer sizes. We show that such optimization is nonconvex, and apply a simulated annealing algorithm to solve it, with flexible trade-off between solution quality and running time. We verify the effectiveness of the new model and the simulated annealing algorithm through extensive simulations, and point out insights on the connection between optimal layer size progression and node capacity distribution.

Abstract-We study the dissemination of common information from a source to multiple nodes within a multihop wireless network, where nodes are equipped with uniform omnidirectional antennas and have a fixed cost per packet transmission. While many nodes may be interested in the dissemination service, their valuation or utility for such a service is usually private information. A desirable routing and charging mechanism encourages truthful utility reports from the nodes. We provide both negative and positive results toward such mechanism design. We show that in order to achieve the group strategyproof property, a compromise in routing optimality or budget-balance is inevitable. In particular, the fraction of optimal routing cost that can be recovered through node charges cannot be significantly higher than 1/2. To answer the question whether constant-ratio cost recovery is possible, we further apply a primal-dual schema to simultaneously build a routing solution and a cost-sharing scheme, and prove that the resulting mechanism is group strategyproof and guarantees 1/4-approximate cost recovery against an optimal routing scheme.

Wireless spectrum is a regulated resource, whose control and usage is regulated by government agencies. The allocation of spectrum to interested parties is usually conducted through auctions, and are an important source of income for these regulatory agencies. However, previous spectrum auction design fail to take into consideration the effect of interference, which can adversely affect the truthfulness of an auction. In this paper, we explicitly consider interference effects, and design truthful auctions for maximizing social welfare. Since the spectrum allocation problem is NP-Hard, we first show how to compute an approximate spectrum allocation scheme that is within a constant factor of the optimal solution, under certain simplifying assumptions on the interference graph. We then proceed to make this scheme strategyproof by tailoring a payment scheme based on the idea of minimum bids. A naive method to compute such a payment scheme requires O(n) iterations of the spectrum allocation algorithm, where n is the number of bidders. We show how to reduce the complexity to O(1) iterations instead. We conclude by discussing possible directions for future research in this area.

Existing routing protocols for Wireless Mesh Networks (WMNs) are generally optimized with statistical link measures, while not addressing on the intrinsic uncertainty of wireless links. We show evidence that, with the transient link uncertainties at PHY and MAC layers, a pseudo-deterministic routing protocol that relies on average or historic statistics can hardly explore the full potentials of a multi-hop wireless mesh. We study optimal WMN routing using probing-based online anypath forwarding, with explicit consideration of transient link uncertainties. We show the underlying connection between WMN routing and the classic Canadian Traveller Problem (CTP) [1]. Inspired by a stochastic recoverable version of CTP (SRCTP), we develop a practical SRCTP-based online routing algorithm under link uncertainties. We study how dynamic next hop selection can be done with low cost, and derive a systematic selection order for minimizing transmission delay. We conduct simulation studies to verify the effectiveness of the SRCTP algorithms under diverse network configurations. In particular, compared to deterministic routing, reduction of end-to-end delay (51.15∼73.02%) and improvement on packet delivery ratio (99.76%) are observed.

BitTorrent-like swarming technologies are very effective for popular content, but less so for the `long tail' of files with disparate popularities, which do not have sufficiently many peers to enable efficient collaboration. Performance degradations are especially pronounced in swarms with reduced file availability. Static bundling groups files into a single data content. It requires no modification to the BitTorrent client, and has been shown to improve availability of unpopular files in BitTorrent swarms. However, as peers are forced to download undesired file pieces, download times increase, especially for peers downloading popular files. We propose to use Stochastic Games and Markov Decision Process (MDP) to model and analyze optimal peer strategies, in a selfish and a cooperative setting respectively, for a BitTorrent-like system with multiple files. Each peer wishes to download a subset of the files, and we allow peers to dynamically decide whether to collaborate with peers targeting a different set of files or not, given the current system state. The Stochastic Game and MPD models take into account both piece availability and average download times, and allow us to study if and when downloading unwanted content can be beneficial. We use dynamic programming to solve the two models, contrast the level of collaboration observed in the selfish and the cooperative settings, and propose an enhanced piece selection mechanism for BitTorrent-like systems with dynamic download decision making. We demonstrate the effectiveness of dynamic file piece selection through both simulations and experiments using a modified BitTorrent client.

This paper studies the problem of topology control in random wireless ad hoc networks through power assignment for n nodes uniformly distributed in a unit square. We require that the network is strongly connected and look to maximize the minimum throughput (or capacity) link in the case that all the nodes transmit simultaneously. According to the Gaussian channel model, the throughput of a wireless link (u, v) is B log(1 + S/N) bps, where B is the channel bandwidth and S/N is the channel bandwidth. We distinguish between two types of power assignments: homogeneous (all nodes have the same power level) and heterogeneous (nodes may have different power levels) cases. For the homogeneous case we give lower and upper bounds on the minimum capacity link. In the heterogeneous case we develop an energy efficient power assignment algorithm which achieves a minimum throughput of Ω(B log(1 + 1/√n log2n)) and also discuss how to implement this algorithm in a distributed fashion. Finally, we present some simulation results. To the best of our knowledge, these are the first provable bounds for capacity in wireless networks, when nodes are allowed to transmit simultaneously.

The effort dedicated to the ultimate goal of designing an architectural framework for tactical mobile ad hoc networks (MANETs) has long been hindered by the excessive control overhead of routing protocols to maintain a full view of the network topology. This paper explores the viability of adopting network coding as a means of improving reliable data delivery while lowering control overhead in large scale MANETs. Simulation results show that the proposed protocol, Network Coded STORM, achieves in excess of 95% packet delivery ratio and reduces the overall overhead by more than 50% in scalability experiments.

The usage of network resources by content providers is commonly governed by service level agreements (SLA) between the content provider and the network service provider. Resource usage exceeding the limits specified in the SLA incurs the content provider additional charges, usually at a higher cost. Hence, the content provider's goal is to provision adequate resources in the SLA based on forecasts of future demand. We study capacity purchasing strategies in this setting when the content provider employs network coded multicast as the data delivery mechanism. We model this problem as a two-stage stochastic optimization problem with recourse, and we design two approximation algorithms to solve such problems. The first is a heuristic that exploits properties unique to network coding. It performs well in general scenarios, but may be unbounded with respect to the optimal solution in the worst case. This motivates our second approach, a sampling algorithm partly inspired from the work of Gupta et al. (2004). We employ techniques from duality theory in linear optimization to prove that sampling provides a 3-approximate solution to the stochastic multicast problem. We conduct simulations to illustrate the efficacy of both algorithms, and show that the performance of both is usually within 10% of the optimal solution in practice.

Shadow price and Vickrey price are two classic metrics that can be applied to measure the relative importance of links in a communication network. Each metric has been extensively investigated and enjoys important applications. We study the underlying connections between these two metrics with seemingly different definitions, under a general mathematical model of multipath multi-session multicast routing. We show that Vickrey prices provide upper-bounds for shadow prices in general, and the fine granularity version of Vickrey price, unit Vickrey price, equals exactly the maximum shadow price. We further design an efficient algorithm that computes all-link max/min shadow prices and unit Vickrey prices simultaneously, for unicast routing, reducing the complexity of a straightforward algorithm by an order of O(|E|).

Recent advances in wireless technology have made it increasingly feasible to equip wireless nodes with multiple radios, thereby allowing each radio to exploit channel diversity in the form of orthogonal, non-overlapping transmission spectrums. Multi-channel operation mitigates interference, but at the same time raises new challenges for network optimization, in terms of judicious channel assignment for efficient bandwidth utilization. While previous research mostly studies optimizing channel assignment for unicast, we focus instead on multicast, which is an efficient mechanism for one-to-many data dissemination. We derive a model for optimal multicast in multi-channel multi-radio wireless networks under the assumption that channel assignment is static. Our model employs network coding as the multicast mechanism of choice, and exploits the broadcast nature of omnidirectional antennas for efficient bandwidth utilization. Based on the model derived, we formulate optimal multicast as a linear integer program. Two accompanying solutions are proposed: a greedy channel assignment scheme and an improved iterative scheme inspired by primal-dual algorithm design. The effectiveness of the two schemes are empirically examined through simulation studies, and are compared to results obtained from solving the integer program as well as its linear programming relaxation. Finally, we present an alternate model for optimal multicast under the assumption that transmission frequencies are not fixed divisions of the usable spectrum.

Recent research in network coding shows that, joint consideration of both coding and routing strategies may lead to higher information transmission rates than routing only. A fundamental question in the field of network coding is: how large can the throughput improvement due to network coding be? In this paper, we prove that in undirected networks, the ratio of achievable multicast throughput with network coding to that without network coding is bounded by a constant ratio of2, i.e., network coding can at most double the throughput. This result holds for any undirected network topology, any link capacity configuration, any multicast group size, and any source information rate. This constant bound2represents the tightest bound that has been proved so far in general undirected settings, and is to be contrasted with the unbounded potential of network coding in improving multicast throughput in directed networks.

Realizing on-demand media streaming in a peer-to-peer (P2P) fashion is more challenging than in the case of live media streaming, since only peers with close-by media play progresses may help each other in obtaining the media content. The situation is further complicated if we wish to pursue low aggregated link cost in the transmission. In this paper, we present a new algorithmic perspective toward on-demand P2P streaming protocol design. While previous approaches employ streaming trees or passive neighbor reconciliation for media content distribution, we instead coordinate the streaming session as an auction where each peer participates locally by bidding for and selling media flows encoded with network coding. We show that this auction approach is promising in achieving low-cost on-demand streaming in a scalable fashion. It is amenable to asynchronous, distributed, and lightweight implementations, and is flexible to provide support for random-seek and pause functionalities. Through extensive simulation studies, we verify the effectiveness and performance of the proposed auction approach, focusing on the optimality in overall streaming cost, the convergence speed, and the communication overhead.

We study multicast in a noncooperative environment where information flows selfishly route themselves through the cheapest paths available. The main challenge is to enforce such selfish multicast flows to stabilize at a socially optimal operating point incurring minimum total edge cost, through appropriate cost allocation and other economic measures, with replicable and encodable properties of information flows considered. We show that known cost allocation schemes are not sufficient. We provide a shadow-price-based cost allocation for networks without capacity limits and show that it enforces minimum-cost multicast. This improves previous result where a 2-approximate multicast flow is enforced. For capacitated networks, computing cost allocation by ignoring edge capacities will not yield correct results. We show that an edge tax scheme can be combined with a cost allocation to strictly enforce optimal multicast flows in this more realistic case. If taxes are not desirable, they can be returned to flows while maintaining weak enforcement of the optimal flow. We relate the taxes to VCG payment schemes and discuss an efficient primal-dual algorithm that simultaneously computes the taxes, the cost allocation, and the optimal multicast flow, with potential of fully distributed implementations.

In the routing and cost sharing of multicast towards a group of potential receivers, cross-monotonicity is a property that states a user's payment can only be smaller when serviced in a larger set. Being cross-monotonic has been shown to be the key in achieving group-strategyproofness. We study multicast schemes that target optimal flow routing, cross-monotonic cost sharing, and budget balance. We show that no multicast scheme can satisfy these three properties simultaneously, and resort to approximate budget balance instead. We derive both positive and negative results that complement each other for directed and undirected networks. We show that in directed networks, no cross-monotonic scheme can recover a constant fraction of optimal multicast cost. We provide a simple scheme that does achieve 1/k-budget-balance, where k is the number of receivers. Using a probabilistic method rooted in random graph theory, we prove an upper-bound of 2/radic(k) for the budget balance ratio. For undirected networks, we derive a constant upper-bound of 1/2 instead. We further apply a smooth dual growing technique to design a cross- monotonic scheme that recovers k+1/2kzeta of optimal multicast cost in undirected networks, where zeta is a network-dependent parameter close to 1. This is almost tight against the upper-bound |. We finally present a two-stage linear optimization model that pursues maximum budget balance in any given specific network, with trade-off in complexity. Optimization results in various network configurations confirm the theoretically established bounds.

Conventional video consists of a single sequence of video frames. During a client's playback period, frames are viewed sequentially from some specified starting point. The fixed frame ordering of conventional video enables efficient scheduled broadcast delivery, as well as efficient near on-demand delivery to large numbers of concurrent clients through use of periodic broadcast protocols in which the video file is segmented and transmitted on multiple channels. This paper considers the problem of devising scalable protocols for near on-demand delivery of "nonlinear" media files whose content may have a tree or graph, rather than linear, structure. Such media allows personalization of the media playback according to individual client preferences. We formulate a mathematical model for determination of the optimal periodic broadcast protocol for nonlinear media with piecewise-linear structures. Our objective function allows differing weights to be placed on the startup delays required for differing paths through the media. Studying a number of simple nonlinear structures we provide insight into the characteristics of the optimal solution. For cases in which the cost of solving the optimization model is prohibitive, we propose and evaluate an efficient approximation algorithm.

Periodic broadcast protocols enable efficient streaming of highly popular media files to large numbers of concurrent clients. Most previous periodic broadcast protocols, however, assume that all clients can receive at the same rate, and also assume that reception bandwidth is not time-varying. In this article, we first develop a new periodic broadcast protocol, Optimized Heterogeneous Periodic Broadcast (OHPB), that can be optimized for a given population of clients with heterogeneous reception bandwidths and quality-of-service requirements. The OHPB protocol utilizes an optimized segment size progression determined by solving a linear optimization model that takes as input the client population characteristics and an objective function such as mean client startup delay. We then develop a generalization of the OHPB linear optimization model that allows optimal server bandwidth allocation among multiple concurrent OHPB broadcasts, wherein each media file and its clients may have different characteristics. Finally, we propose complementary client protocols employing work-ahead buffering of data during playback, so as to enable more uniform playback quality when the reception bandwidth is time-varying.

In peer-to-peer (P2P) live streaming applications such as IPTV, it is natural to accommodate multiple coexisting streaming overlays, corresponding to channels of programming. In the case of multiple overlays, it is a challenging task to design an appropriate bandwidth allocation protocol, such that these overlays efficiently share the available upload bandwidth on peers, media content is efficiently distributed to achieve the required streaming rate, as well as the streaming costs are minimized. In this paper, we seek to design simple, effective, and decentralized strategies to resolve conflicts among coexisting streaming overlays in their bandwidth competition and combine such strategies with network-coding-based media distribution to achieve efficient multioverlay streaming. Since such strategies of conflict are game theoretic in nature, we characterize them as a decentralized collection of dynamic auction games, in which downstream peers bid for upload bandwidth at the upstream peers for the delivery of coded media blocks. With extensive theoretical analysis and performance evaluation, we show that these local games converge to an optimal topology for each overlay in realistic asynchronous environments. Together with network-coding-based media dissemination, these streaming overlays adapt to peer dynamics, fairly share peer upload bandwidth to achieve satisfactory streaming rates, and can be prioritized.

Wireless spectrum is a scare resource, while media streaming usually requires high end-to-end bandwidth. Media streaming in wireless ad hoc networks is therefore a particularly challenging problem, especially for the case of streaming to multiple receivers. In this paper, we design linear optimization models for computing a high-bandwidth routing strategy for media multicast in wireless networks, which targets near-optimal throughput, given constraints including network topology, radio capacity, and link contention. We study both the directional antenna and omni-directional antenna cases and point out their connections. We also combine the classic forward error correction techniques with the novel network coding techniques to provide error control in a timely fashion. Simulation results show that our solutions indeed achieve high streaming rates, and prompt error recovery under a wide range of link failure patterns.

This paper presents a traffic characterization study of the popular video sharing service, YouTube. Over a three month period we observed almost 25 million transactions between users on an edge network and YouTube, including more than 600,000 video downloads. We also monitored the globally popular videos over this period of time.

We study multicast in a non-cooperative environment where information flows selfishly route themselves through the cheapest paths available. The main challenge is to enforce such selfish multicast flows to stabilize at a socially optimal operating point incurring minimum total edge cost, through appropriate cost allocation and other economic measures, with replicable and encodable properties of information flows considered. We show that known cost allocation schemes are not sufficient. We provide a shadow-price based cost allocation for networks without capacity limits, and show it enforces minimum-cost multicast. This improves previous result where a 2-approximate multicast flow is enforced. For capacitied networks, computing cost allocation by ignoring edge capacities will not yield correct results. We show that an edge tax scheme can be combined with a cost allocation to strictly enforce optimal multicast flows in this more realistic case. If taxes are not desirable, they can be returned to flows while maintaining weak enforcement of the optimal flow. We relate the taxes to VCG payment schemes and discuss an efficient primal-dual algorithm that simultaneously computes the taxes, the cost allocation, and the optimal multicast flow.

Periodic broadcast protocols enable the efficient streaming of highly popular media files to large numbers of concurrent clients. Most previous periodic broadcast protocols, however, assume that all clients can receive at the same rate, and also assume that available bandwidth is not time-varying. In this paper, we first develop a new periodic broadcast protocol, Optimized Heterogeneous Periodic Broadcast (OHPB), that can be optimized for a given population of clients with heterogeneous reception bandwidths and quality-of-service requirements. The OHPB protocol utilizes an optimized segment size progression determined by solving a linear optimization model that takes as input the client population characteristics and an objective function such as mean client startup delay. We then propose complementary client protocols employing work-ahead buffering of data during playback, so as to enable more uniform playback quality when the available bandwidth is time-varying.

Realizing on-demand media streaming in a Peer-to-Peer (P2P) fashion is more challenging than in the case of live media streaming, since only peers with close-by media play progresses may help each other in obtaining the media content. The situation is further complicated if we wish to pursue low link cost in the transmission. In this paper, we present a new algorithmic perspective towards on-demand P2P streaming protocol design. While previous approaches employ streaming trees or passive neighbour reconciliation for media content distribution, we instead coordinate the streaming session as an auction where each peer participates locally by bidding for and selling media flows encoded with network coding. We show that this auction approach is promising in achieving low-cost on-demand streaming in a scalable fashion. It is amenable to asynchronous, distributed, and light-weight implementations, and is flexible enough to provide support for random-seek and pause functionalities.

The optimal and distributed provisioning of high throughput in mesh networks is known as a fundamental but hard problem. The situation is exacerbated in a wireless setting due to the interference among local wireless transmissions. In this paper, we propose a cross-layer optimization framework for throughput maximization in wireless mesh networks, in which the data routing problem and the wireless medium contention problem are jointly optimized for multihop multicast. We show that the throughput maximization problem can be decomposed into two subproblems: a data routing subproblem at the network layer, and a power control subproblem at the physical layer with a set of Lagrangian dual variables coordinating interlayer coupling. Various effective solutions are discussed for each subproblem. We emphasize the network coding technique for multicast routing and a game theoretic method for interference management, for which efficient and distributed solutions are derived and illustrated. Finally, we show that the proposed framework can be extended to take into account physical-layer wireless multicast in mesh networks

The transmission of information within a data network is constrained by the network topology and link capacities. In this paper, we study the fundamental upper bound of information dissemination rates with these constraints in undirected networks, given the unique replicable and encodable properties of information flows. Based on recent advances in network coding and classical modeling techniques in flow networks, we provide a natural linear programming formulation of the maximum multicast rate problem. By applying Lagrangian relaxation on the primal and the dual linear programs (LPs), respectively, we derive a) a necessary and sufficient condition characterizing multicast rate feasibility, and b) an efficient and distributed subgradient algorithm for computing the maximum multicast rate. We also extend our discussions to multiple communication sessions, as well as to overlay and ad hoc network models. Both our theoretical and simulation results conclude that, network coding may not be instrumental to achieve better maximum multicast rates in most cases; rather, it facilitates the design of significantly more efficient algorithms to achieve such optimality.

The transmission of information within a data network is constrained by network topology and link capacities. In this paper, we study the fundamental upper bound of information multicast rates with these constraints, given the unique replicable and encodable property of information flows. Based on recent information theory advances in coded multicast rates, we are able to formulate the maximum multicast rate problem as a linear network optimization problem, assuming the general undirected network model. We then proceed to apply Lagrangian relaxation techniques to obtain (1) a necessary and sufficient condition for multicast rate feasibility, and (2) a subgradient solution for computing the maximum rate and the optimal routing strategy to achieve it. The condition we give is a generalization of the well-known conditions for the unicast and broadcast cases. Our subgradient solution takes advantage of the underlying network flow structure of the problem, and therefore outperforms general linear programming solving techniques. It also admits a natural intuitive interpretation, and is amenable to fully distributed implementations.

With the constraints of network topologies and link capacities, achieving the optimal end-to-end throughput in data networks has been known as a fundamental but computationally hard problem. In this paper, we seek efficient solutions to the problem of achieving optimal throughput in data networks, with single or multiple unicast, multicast and broadcast sessions. Although previous approaches lead to solving NP-complete problems, we show the surprising result that, facilitated by the recent advances of network coding, computing the strategies to achieve the optimal end-to-end throughput can be performed in polynomial time. This result holds for one or more communication sessions, as well as in the overlay network model. Supported by empirical studies, we present the surprising observation that in most topologies, applying network coding may not improve the achievable optimal throughput; rather, it facilitates the design of significantly more efficient algorithms to achieve such optimality.

One of the main characteristics of wireless ad hoc networks is their node-centric broadcast nature of communication, leading to interferences and spatial contention between adjacent wireless links. Due to such interferences, pessimistic concerns have been recently raised with respect to the decreasing network capacity in wireless ad hoc networks when the number of nodes scales to several orders of magnitude higher. In this paper, we argue that in all cases of end-to-end data communications - including one-to-k unicast and multicast data dissemination as well as k-to-one data aggregation - the maximum achievable end-to-end data throughput (measured on the sources) heavily depends on the strategy of arranging the topology of transmission between sources and destinations, as well as possible per-node operations such as coding. An optimal strategy achieves better end-to-end throughput than an arbitrary one. We present theoretical studies and critical insights with respect to how these strategies may be designed so that end-to-end throughput may be increased.

Existing research work towards the composition of complex federated services has assumed that service requests and deliveries flow through a particular service path or tree. Here, we extend such a service model to a directed acyclic graph, allowing services to be delivered via parallel paths and interleaved with each other. Such an assumption of the service flow model has apparently introduced complexities towards the development of a distributed algorithm to federate existing services, as well as the provisioning of the required quality in the most resource-efficient fashion. To this end, we propose sFlow, a fully distributed algorithm to be executed on all service nodes, such that the federated service flow graph is resource efficient, performs well, and meets the demands of service consumers.

Article iFlow: Middleware-assisted Rendezvous-based Information Access for Mobile Ad Hoc Applications Authors: Zongpeng Li View Profile , Baochun Li View Profile , Dongyan Xu View Profile , Xin Zhou View Profile Authors Info & Claims MobiSys '03: Proceedings of the 1st international conference on Mobile systems, applications and servicesMay 2003Pages 71–84https://doi.org/10.1145/1066116.1189039Published:05 May 2003Publication History 6citation167DownloadsMetricsTotal Citations6Total Downloads167Last 12 Months1Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access