Root cause analysis (RCA) of network device failures is critical to cloud reliability. While monitoring can identify which device has failed, diagnosing why remains a slow, manual process, increasing the risk of recurring failures and cascading service disruptions. Existing automated methods are inadequate: traditional methods lack precision, while prior machine learning (ML) and large language model (LLM) approaches are often too coarse-grained, require heavy manual configuration, or fail to produce verifiable reasoning essential for operator trust. This paper presents AIDA, the first system to deliver automated, fine-grained RCA of network device failures, deployed at scale in Alibaba Cloud's production network. AIDA's contributions include: (1) fine-tuning an LLM with reinforcement learning to distill expert logic into interpretable reasoning chains; (2) synthesizing these chains into an evolving knowledge graph (KG) to support retrieval-augmented generation (RAG); and (3) employing RAG-driven multi-step inference wherein the LLM is sequentially guided by the KG to construct robust, verifiable reasoning. Deployed for over a year, AIDA has achieved 95.4% precision with interpretable output and reduced the median RCA time from 72.6 hours to 1.6 minutes. Notably, it curtails the 90th-percentile diagnosis latency from 329.9 hours to 19.4 hours.

3D lane detection has become a critical component in the perception task of autonomous vehicles. Unlike 2D lane detection, which operates in the image plane, 3D lane detection estimates the spatial layout of lanes in real-world coordinates, enabling fine-grained localization, map construction, and planning. However, the task remains challenging due to depth ambiguity, sensor limitations, and diverse road conditions. Existing surveys mostly focus on 2D or organize 3D lane detection by sensor modality, lacking a systematic treatment of algorithmic designs. In this paper, we present a comprehensive survey of deep learning-based 3D lane detection methods. We introduce a dual-axis taxonomy that jointly considers modeling paradigms and representation spaces. Based on this framework, we categorize existing methods into four primary paradigms: geometry-based, end-to-end, query-based, and implicit field-based. We analyze how each paradigm interacts with spatial representations such as image, BEV, 3D, and topological spaces. For each category, we review representative frameworks, architectural principles, and performance trade-offs. We also provide an extensive summary of public datasets, evaluation metrics, and state-of-the-art results across multiple benchmarks. Finally, we identify current limitations and outline future research directions toward robust, scalable, and interpretable 3D lane detection.

The rapid proliferation of edge computing infrastructure has significantly accelerated the adoption of edge-native applications, ranging from autonomous vehicles to augmented reality and real-time analytics. Microservice, renowned for its lightweight, loosely coupled, and modular architecture, has emerged as the de-facto standard for developing edge native applications. However, the resource scarcity and heterogeneity, coupled with request dynamics in edge environments, pose substantial challenges for effective microservice orchestration. To address these challenges, we propose MicroEdge, an online optimization framework designed for cost-efficient microservice orchestration in edge-native environments. MicroEdge employs a multi-level optimization approach by strategically coordinating four key dimensions: microservice placement, layer placement, layer pulling, and user request scheduling. The framework confronts two fundamental challenges in solving this joint optimization problem: (1) the time-coupled nature of long-term holistic cost minimization, and (2) the NP-hardness of the underlying problem. MicroEdge tackles these dual challenges by integrating a regularization method for online algorithm design and a dependent rounding technique for approximation algorithm design. Both rigorous theoretical analysis and extensive simulations driven by realistic Alibaba microservice workload traces validate the efficacy of MicroEdge.

In recent years, the frequency and severity of network attacks have increased significantly, posing serious threats to network security. Network topology information is often exploited by attackers to identify critical bottlenecks, which are prime targets for attacks. Typically, attackers probe the network topology using network tomography or traceroute. Network tomography, compared to traditional methods like traceroute, offers greater flexibility and is more challenging to detect. These characteristics make it a preferred technique for attackers. In response, network operators seek to implement topology obfuscation strategies that expose a deliberately designed fake topology to mislead attackers. However, existing obfuscation techniques against network tomography have primarily focused on protecting tree-like topologies and have been insufficient in concealing bottleneck nodes and links. To this end, we propose TopoFaker, a novel topology obfuscation system designed to protect general network topologies while effectively concealing bottleneck nodes and links. TopoFaker consists of three main components: a topology generator that creates secure fake topologies, a policy deployer that ensures attackers perceive only the obfuscated topology, and obfuscation nodes that implement proactive delay policies in the data plane. Experimental evaluations on real-world network topologies demonstrate that TopoFaker effectively enhances network security by obscuring bottleneck nodes and links, achieving a 73.99% reduction in maximum degree centrality and a 79.48% reduction in maximum edge connectivity. Furthermore, TopoFaker reduces the average proactive delay time by 50.82%, minimizing the negative impact on normal packets misclassified due to the classifier’s false alarms. TopoFaker outperforms existing mechanisms by achieving a runtime of under one minute and reducing memory allocation by four orders of magnitude on large-scale problems.

As resource-intensive and latency-sensitive applications continue to expand, the integration of unmanned aerial vehicles (UAVs) with mobile edge computing (MEC) has emerged as a viable solution, offering flexible, on-demand services for mobile users (MUs) without reliance on terrestrial infrastructure. The adoption of non-orthogonal multiple access (NOMA) further reduces latency by allowing MUs to offload tasks simultaneously over a single subchannel. However, many existing offloading methods do not explicitly incorporate a priority-based task scheduling mechanism and instead optimize task execution based on system constraints such as latency or energy consumption. To bridge this gap, we propose a QoS-oriented task offloading scheme that systematically optimizes task scheduling. We formulate an average system utility maximization problem that jointly optimizes UAVs’ 3D trajectories, MU association, task offloading ratios, and resource allocation. The optimization problem is inherently complex due to its non-convex nature and multiple constraints. To address this, we first employ Lagrange duality to decouple constraints, reducing computational complexity. Subsequently, we propose a novel improved soft actor-critic (ISAC) algorithm, which incorporates a perturbation term into the loss function to guide the training process away from local minima and toward globally optimal solutions. Through extensive simulation, we demonstrate that the ISAC algorithm guarantees convergence and significantly outperforms benchmark methods on offloading transmission rates, task completion rates, and overall system utility.

A pronounced imbalance in GPU resources exists on campus, where some laboratories own underutilized servers while others lack the compute needed for AI research. GPU sharing can alleviate this disparity, while existing platforms typically rely on centralized oversight and persistent allocation models, conflicting with the voluntary and autonomous nature of academic resource ownership. We present GPUnion, a campus-scale GPU sharing platform enabling voluntary participation while preserving full provider autonomy. GPUnion incorporates three core mechanisms: i) container-based task dispatching and execution, ii) resource provider-first architecture, and iii) resilient execution featuring automatic checkpointing and migration. Case studies across multiple campus scenarios demonstrate 30% more GPU utilization improvement, 40% increase in interactive sessions, and 94% successful workload migration during provider departures.

The prominent paradigm of federated learning (FL) is increasingly being applied to emerging and cross-silo applications, particularly with edge computing systems serving as pivotal agents. However, this shift also renders FL training more energy and carbon intensive. To this end, we propose GreenFL, a carbon-aware FL training framework designed to systematically navigate the trade-offs between carbon emission, training accuracy, and training efficiency. GreenFL employs a hybrid training strategy that combines inter-group asynchronous training and intra-group synchronous training to mitigate the straggler effect caused by inefficient participants. In the overall design of the framework, we promote the participation of edge computing nodes with abundant renewable energy sources and implement strategic participant selection to balance carbon emissions and training accuracy. We prove the solvability of optimizing the selection strategy and provide an online greed-based solution based on penalty values and bipartite greedy algorithms. Through extensive data-driven experiments, we demonstrate that GreenFL can significantly improve the carbon efficiency of the entire FL procedure, while maintaining or exceeding state-of-the-art levels of training accuracy and efficiency.

Non-independent and identically distributed (Non-IID) data across edge clients have long posed significant challenges to federated learning (FL) training. Prior works have proposed various methods to mitigate this statistical heterogeneity. While these methods can achieve good theoretical performance, they may lead to the over-correction problem, which degrades model performance and even causes failures in model convergence. In this paper, we provide the first investigation into the hidden over-correction phenomenon brought by the uniform model correction coefficients across clients adopted by the existing methods. To address this problem, we propose TACO, a novel algorithm that addresses the non-IID nature of clients’ data by implementing fine-grained, client-specific gradient correction and model aggregation, steering local models towards a more accurate global optimum. Moreover, we verify that leading FL algorithms generally have better model accuracy in terms of communication rounds rather than wall-clock time, resulting from their extra computation overhead imposed on clients. To enhance the training efficiency, TACO deploys a lightweight model correction and tailored aggregation approach that requires minimum computation overhead and no extra information beyond the synchronized model parameters. To validate TACO’s effectiveness, we present the first FL convergence analysis that reveals the root cause of over-correction. Extensive experiments across various datasets confirm TACO’s superior and stable performance in practice.

Inertial navigation enables self-contained localization using only Inertial Measurement Units (IMUs), making it widely applicable in various domains such as navigation, augmented reality, and robotics. However, existing methods suffer from drift accumulation due to the sensor noise and difficulty capturing long-range temporal dependencies, limiting their robustness and accuracy. To address these challenges, we propose DiffusionIMU, a novel diffusion-based framework for inertial navigation. DiffusionIMU enhances direct velocity regression from IMU data through an iterative generative denoising process, progressively refining motion state estimation. It integrates the noise-adaptive feature modulation for sensor variability handling, the feature alignment mechanism for representation consistency, and the diffusion-based temporal modeling to decrease accumulated drift. Experiments show that DiffusionIMU consistently outperforms existing methods, demonstrating superior generalization to unseen users while alleviating the impact of the sensor noise.

In the erasure-coded storage systems, multiple related blocks have to be retrieved from other surviving nodes to repair a failed block. This incurs significant communication overhead with the surging scale of distributed storage systems. To mitigate the bandwidth bottleneck, in-network repair (INR) has emerged as a promising transport paradigm, which migrates the aggregation operations from the repair node to the programmable hardware, such as Intel Tofino switches. However, due to the limited on-chip memory size of these switches, the INR can degrade to the most primitive incast-type transmission, leading to massive traffic volume and hindered repair throughput. While we notice that, there are spare CPU cores in the storage servers that can be leveraged as alternative computing resources. With this intuition, we propose SINA, a Server-assisted In-Network repair Acceleration framework in this paper, which leverages the spare servers to assist aggregation operations when the programming switches' memory size is scarce for failure repair. We formulate this problem by adjusting the aggregation modes across the involved racks and solve this NP-hard problem using the Gurobi optimization solver. For all we know, this is the first work exploring spare servers for assisting the memory-scarce INR in erasure-coded storage systems. We have implemented SINA on an FPGA-based prototype system, and the experimental results show that SINA can ensure fault tolerance and accelerate failure repair by$5.0 \times$compared to the conventional methods.

The rapid growth of artificial intelligence (AI), particularly in computer vision (CV), necessitates distributed computing for efficient model training. Existing benchmarks often lack adaptability to emerging scenarios or focus on limited applications. To address these gaps, this paper studies a case on a comprehensive benchmark suite for distributed AI training systems. We classifies AI tasks into four categories, LargeScale, Moderate Complexity, High Load, and High-Performance, based on single-load computation and load concurrency, with representative models evaluated on Ray and DeepSpeed across diverse hardware. The experiments reveal fragmented framework performance. DeepSpeed excels in stability and efficiency for Large-Scale and Moderate Complexity tasks, leveraging advanced memory optimization. Ray outperforms in High Load and High-Performance tasks due to its dynamic resource scheduling but shows greater variability. These results highlight the need for task-specific framework selection tailored to hardware and performance requirements. We provides valuable insights for optimizing distributed AI training and bridges limitations in current benchmarks. Future work aims to expand task categories and framework support to align with the evolving demands of distributed AI systems.

Efficient set representation and membership testing are important in high-speed network measurement. Fast insertions, space efficiency, fast query, and low false positive rate are the core requirements of traffic measurement, but existing solutions, such as hash tables and Bloom filters(BFs), cannot satisfy these requirements simultaneously. The state-of-the-art cuckoo filter and its variants(CFs) rely on the random eviction relocation strategy to resolve hash collisions, improving space utilization while reducing false positives and maintaining high query efficiency. However, CFs suffer a critical challenge in practical applications: insertion could trigger multiple evictions when all candidate buckets for an element are saturated, leading to insertion performance degradation, especially when space utilization exceeds 0.8. To solve the above problem, we propose a novel relocation strategy based on a random graph model, called the local minimum strategy. Our core idea is to use the implicit meaning of the number of evictions in each bucket as an indication to minimize the relocation of elements. We theoretically and experimentally prove that the eviction threshold for each bucket is$O(\log m)$, where$m$is the number of buckets. The threshold establishes the bounds for the probability of a successful insertion. The experimental results show that, the local minimum strategy significantly reduces the number of relocations by 67 %, as well as increasing the insertion throughput by more than 10 %.

The rapid development of unmanned aerial vehicle (UAV) technology and mobile edge computing (MEC) has created new opportunities for efficient data processing and transmission. UAV-assisted MEC enables data transmission from UAVs to a base station (BS) equipped with MEC capabilities. However, ensuring the security of these transmissions is a concern, especially when UAVs operate in open airspace. In this paper, we introduce a coordinated multi-point (CoMP) offloading model aimed at enhancing the secure transmission performance of the network. The airspace is divided into several equal-sized hexagonal cells, with multiple UAVs collaborating to offload data to a BS with MEC. During this process, the locations of potential eavesdroppers are randomized as they attempt to intercept the data transmitted by the UAVs. Based on this model, we first derive the success communication probability (SCP) for a typical BS and an eavesdropper using stochastic geometry. We then introduce the concept of secure transmission rate, precisely the average secrecy rate (ASR). Further, we characterize the ASR in the presence of random eavesdroppers. Finally, we analyze the effects of various parameters on transmission performance. The results of our simulations closely align with our numerical findings, confirming the accuracy of our analysis. Notably, the ASR of the proposed system is nearly four times higher than that of an offloading model without cooperation. Moreover, compared to a user-centric offloading model with CoMP, the ASR increases by 5.37 %, enhancing system performance and reducing search overheads.

As mobile device usage and data traffic increase, the demand for faster data processing becomes crucial. Mobile edge computing (MEC) meets this need by placing servers at the network’s edge for real-time computing. However, fixed terrestrial MEC servers struggle with scalability, limiting their effectiveness. Integrating unmanned aerial vehicles (UAV) with MEC technology offers a promising solution, enhancing communication efficiency and service quality. This paper proposes a joint communication and computation offloading model for coordinated multi-point (CoMP) UAV-assisted MEC networks utilizing hexagonal cell partitioning. Within each cell, a cluster of UAVs, each equipped with its own MEC server and connected to a central server via a reliable backhaul, collaborates to serve terrestrial user equipment. To analyze this system, we develop a unified analytical framework integrating stochastic geometry and queuing theory. Furthermore, we define the success probability of edge computing (SPEC) metric to quantitatively evaluate communication reliability and computational efficiency. Finally, we explore the effects of critical parameters on network performance. Simulation results closely match the theoretical predictions, confirming our proposed model’s validity and our analysis’s accuracy. Notably, our proposed model demonstrates an improvement in SPEC of approximately 57.24% over non-CoMP model and 24.97% over the user-centric CoMP model.

Data-driven inertial navigation is crucial for mobile computing applications, such as navigation, augmented reality, and robotics. It typically depends on a trained velocity regression network (VRN) to estimate velocities from inertial measurement unit (IMU) data, enabling position determination through integration. However, using prior velocity information for feature representation in inertial navigation remains underexplored. This work introduces a framework called velocity auto-encoder for inertial navigation (VANE-IN), which employs a Teacher-Student scheme to enhance VRN performance by encoding the velocity. Specifically, a velocity auto-encoder (VANE) is proposed as a student model to distill prior velocity insights from the training dataset, which is then guided by the VRN acting as the teacher model. Additionally, an attention mechanism is introduced to fuse these insights into the features of the VRN. To this end, the VANE-IN achieves a state-of-the-art position accuracy on the RoNIN benchmarks. Our experimental results demonstrate that the VANE-IN achieves approximately 5% performance improvements over existing methods regarding position accuracy.

Edge computing is an emerging paradigm poised to process a substantial portion of latency-sensitive and computation-intensive tasks through edge service providers (ESPs). However, these ESPs typically operate independently and locally to serve their registered users. When processing burst tasks, the ESPs have to either scale up their respective capacities by introducing additional hardware or compromise user experience by rejecting some user requests, leading to high commercial investment or service degradation. Inspired by the promise of the win-win situation for ESPs and users, we envision a novel task offloading strategy that realizes the following rationales simultaneously: 1) collaborative service, 2) rapid response, and 3) sustainable profitability, while the existing methods fail to achieve them at one shot. To this end, we report CoEdge, a collaborative architecture for efficient task offloading among multiple ESPs in the edge network, aiming at simultaneously minimizing service delay for users and enhancing service profit for ESPs. To achieve this, CoEdge employs a central optimizer to implement a two-stage strategy that determines the task scheduling and service pricing hierarchically. We then formulate these problems and prove their NP-hardness. Additionally, we also propose efficient approximate algorithms to accommodate large-scale computing scenarios with low complexity. Experimental results using real-world datasets demonstrate that our CoEdge can significantly reduce service delay by 2.87x to 4.15x for users and considerably increase service profit by 32% for ESPs.

Currently, deduplication techniques are utilized to minimize the space overhead by deleting redundant data blocks across large-scale servers in data centers. However, such a process exacerbates the fragmentation of data blocks, causing more cross-server file retrievals with plummeting retrieval throughput. Some attempts prefer better file retrieval performance by confining all blocks of a file to one single server, resulting in non-trivial space consumption for more replicated blocks across servers. An ideal network storage system, in effect, should take both the deduplication and retrieval performance into account by implementing reasonable assignment of the detected unique blocks. Such a fine-grained assignment requires an accurate and comprehensive abstraction of the files, blocks, and the file-block affiliation relationships. To achieve this, we innovatively design the weighted hypergraph to profile the multivariate data correlations. With this delicate abstraction in place, we propose HyperPart, which elegantly transforms this complex block allocation problem into a hypergraph partition problem. For more general scenarios with dynamic file updates, we further propose a two-phase incremental hypergraph repartition scheme, which mitigates the performance degradation with minimal migration volume. We implement a prototype system of HyperPart, and the experiment results validate that it saves around 50% of the storage space and improves the retrieval throughput by approximately 30% of state-of-the-art methods under the balance constraints.

Location-based mobile services, while improving user daily life, also raise significant privacy concerns in the sharing of location data. These trajectories indicate users’ traveling behavioural traces with rich semantics derived from open-source information. Behavioral-semantic analysis reveals users’ travelling motivations and underlying behavioral patterns. It contributes to attackers launching inferential attacks for behavior prediction, identity identification, or other privacy invasions, even when the location data is protected. It remains open to the issues of behavioral-semantic privacy-risk quantification and privacy-protection evaluation. This paper aims to reveal such semantic privacy risks of user behaviors arising from the publication of location trajectories in mobile scenarios. We formalize user semantic-mobility process to analyze his underlying behavior patterns. Then, we design semantic inference algorithms conditional on the released trajectory to reason about the observation-based likelihood of the user’s actual staying and transfer behaviours and behavioural-trace tracking. Extensive experiments with real-world data demonstrate their performance on inference accuracy and semantic similarity, offering a quantification criterion for deploying mobile privacy protection.

As an ambitious training paradigm, federated learning has garnered increasing attention in recent years, which enables collaborative training of a global model without accessing users’ private data. However, due to the simultaneous and constant model updates gathering from massive distributed clients, the central server generally becomes a performance bottleneck. Additionally, the stateful aggregation (retaining all the updates from each client) conducted by the central server further poses potential threats to privacy, since it may recover the raw data based on such model updates inversely. The state-of-the-art methodologies, however, fail to address these two problems concurrently and efficiently. To this end, we propose GAIN, a secure aggregation acceleration service for federated learning. At its core, GAIN leverages programmable switches deployed at the edge network to aggregate model updates in a stateless manner before transmitting them to the central server. Consequently, GAIN can accelerate the transmission and aggregation of model updates while eliminating the chance of recovering private data. We evaluate the performance of GAIN through FPGA-based experiments and large-scale simulations. The results show that GAIN can effectively reduce bandwidth overhead and achieve up to 4.11× training throughput acceleration while prioritizing privacy protection.

Large Language Models (LLMs) have demonstrated remarkable capabilities, leading to a significant increase in user demand for LLM services. However, cloud-based LLM services often suffer from high latency, unstable responsiveness, and privacy concerns. Therefore, multiple LLMs are usually deployed at the network edge to boost real-time responsiveness and protect data privacy, particularly for many emerging smart mobile and IoT applications. Given the varying response quality and latency of LLM services, a critical issue is how to route user requests from mobile and IoT devices to an appropriate LLM service (i.e., edge LLM expert) to ensure acceptable quality-of-service (QoS). Existing routing algorithms fail to simultaneously address the heterogeneity of LLM services, the interference among requests, and the dynamic workloads necessary for maintaining long-term stable QoS. To meet these challenges, in this paper we propose a novel deep reinforcement learning (DRL)-based QoS-aware LLM routing framework for sustained high-quality LLM services. Due to the dynamic nature of the global state, we propose a dynamic state abstraction technique to compactly represent global state features with a heterogeneous graph attention network (HAN). Additionally, we introduce an action impact estimator and a tailored reward function to guide the DRL agent in maximizing QoS and preventing latency violations. Extensive experiments on both Poisson and real-world workloads demonstrate that our proposed algorithm significantly improves average QoS and computing resource efficiency compared to existing baselines.

Transformer-based models have unlocked a plethora of powerful intelligent applications at the edge, such as voice assistant in smart home. Traditional deployment approaches offload the inference workloads to the remote cloud server, which would induce substantial pressure on the backbone network as well as raise users' privacy concerns. To address that, in-situ inference has been recently recognized for edge intelligence, but it still confronts significant challenges stemming from the conflict between intensive workloads and limited on-device computing resources. In this paper, we leverage our observation that many edge environments usually comprise a rich set of accompanying trusted edge devices with idle resources and proposeGalaxy+, a collaborative edge AI system that breaks the resource walls across heterogeneous edge devices for efficient Transformer inference acceleration.Galaxy+introduces a novel hybrid model parallelism to orchestrate collaborative inference, along with a heterogeneity and memory-aware parallelism planning for fully exploiting the resource potential. To mitigate the impact of tensor synchronizations on inference latency under bandwidth-constrained edge environments,Galaxy+devises a tile-based fine-grained overlapping of communication and computation. Furthermore, a fault-tolerant re-scheduling mechanism is developed to address device-level resource dynamics, ensuring stable and low-latency inference. Extensive evaluation based on prototype implementation demonstrates thatGalaxy+remarkably outperforms state-of-the-art approaches under various edge environment setups, achieving a$1.2\times$to$4.24\times$end-to-end latency reduction. Besides,Galaxy+can adapt to device-level resource dynamics, swiftly rescheduling and restoring inference in the presence of unexpected straggler devices.

Many network attacks, like link flooding attacks (LFAs), heavily rely on network topology information. Therefore, network topology obfuscation has been applied to counteract network topology inference and prevent topology information leakage. One effective way is to scheme a fake topology intentionally for attackers to map out. Focusing on reducing the similarity between the real and fake topologies, however, existing methods cannot promise that critical information of the network, such as critical nodes and links, is well hidden. To this end, we propose a new topology obfuscation mechanism, namely ChameleonNet, to protect the critical topology information of a given network. Specifically, ChameleonNet achieves topology obfuscation through a two-stage operation: 1) generating fake topology and 2) deploying fake topology. Our experiments on three real-world and two large-scale generated network topologies demonstrate that ChameleonNet can effectively reduce similarity between inferred and real topologies by 31%-37% and reliably hide critical topology information in terms of multiple statistical metrics.

Edge storage systems have drawn many efforts to extend the storage and service capabilities of cloud data centers. A pivotal aspect lies in the data-sharing mechanism, which integrates geographically dispersed weak edge servers into an efficient storage system. It enables users to launch data operations at any server and retrieve the desired data across the distributed system. However, it remains open to meeting the increasing demand for similarity retrieval across edge servers. The intrinsic reason is that the existing solutions can only return an exact data match for a query while more general edge applications require the data similar to a query input from any server. To fill this gap, this paper pioneers the similarity edge data sharing mechanism, a new paradigm to support high-dimensional similarity search at network edges. First, through deeply thinking about the nature of similarity data sharing, we propose the problem of Optimal Indexing and formulate it as the optimal transport problem from the data space to the network space. On this basis, we propose Prophet, the first known architecture for similarity data indexing at the edge. We first divide the feature space of data into plenty of subareas, then project both subareas and edge servers into a virtual space where the distance between any two points can reflect not only data similarity but also network latency. When any edge server submits a request for data insert, delete, or query, it computes the data feature and the virtual coordinate; and then iteratively forwards the request via greedy routing based on the forwarding tables and the virtual coordinates. By Prophet, similar high-dimensional features would be stored by a common server or several nearby servers. Compared with distributed hash tables in P2P networks, Prophet requires to visit logarithmic servers for a data request and reduces the network latency from the logarithmic to the constant level of the server number. Evaluation results indicate that Prophet achieves the comparable retrieval accuracy and significantly shortens the query latency compared with centralized schemes, while the load balancing performance is nearly optimal.

The performance of distributed applications has long been hindered by network communication, which has emerged as a significant bottleneck. At the core of this issue, the many-to-one incast transfer stands out as one of the primary culprits. Existing works typically decompose the transmission into multiple concurrent sub-processes and utilize servers to aggregate relevant traffic, thus avoiding the incast transfer. However, limited by their theoretical bounds, these methods can only obtain limited performance improvement. In this paper, we discover that leveraging network devices for aggregating incast traffic proves highly effective in surpassing such limitations, while the advent of programmable switches further makes this envision practical. Based on this, we propose GISA as a solution for providing network acceleration across diverse distributed applications. GISA offers generic and uniform interfaces to various applications along with a switch resource sharing mechanism and policy for concurrent tasks. It also ensures correct and reliable transport while minimizing overhead through a low-overhead routing mechanism. Our FPGA-based prototype demonstrates that GISA can achieve line-rate processing when performing data aggregation with minor traffic overhead. Additionally, it supports a wide range of concurrent applications with little development effort.

Graphlets are small, connected, and non-isomorphic induced subgraphs that describe the topological structure of a graph. Counting graphlets is a fundamental task in graph mining and social network analysis. It has numerous applications in many fields, including dense subgraph discovery, anomaly detection, etc. Most existing work assumes a static graph. However, graphs are dynamic in the real world, which can be described as graph streams. Counting graphlets in graph streams is a challenge due to the streaming nature of the input. While there have been several studies on counting graphlets in graph streams, these works are limited to simple graphlets like triangles and butterflies. In this paper, we propose SGES algorithm to estimate more complex graphlets in graph streams. In SGES, we first propose an unbiased sampling strategy to maintain fixed-size sampled edges, which in turn allows us to unbiasedly estimate the number of subgraphs and then count graphlets based on the combinational relationship between the number of subgraphs and the number of graphlets. Extensive experiments over large real-world graph streams prove that our algorithm can obtain accurate estimation values of graphlet counts with high throughput.

In federated learning, sending the trained models (instead of raw data) from clients to the central server can surely decrease the volume of exchanged data and preserve data privacy to some extent. However, the central server can still be a system bottleneck due to the simultaneous and constant model gathering from massive distributed clients. Besides, the central server conducts stateful aggregation (retaining all the updates from each client), making it a potential threat to privacy, since it may recover the raw data based on such model updates inversely. The state-of-the-art methodologies, however, fail to address these two problems concurrently. To this end, we propose GAIN, a secure aggregation acceleration service for federated learning. At its core, GAIN aggregates the model updates at the programmable ingress switches in a stateless manner (storing the aggregated model parameters from the clients temporarily rather than permanently) before proceeding to the central server. Consequently, GAIN can accelerate the transmission and aggregation of model parameters while eliminating the chance of data recovery. We implemented a prototype of GAIN on an FPGA-based testbed to validate its performance. The results demonstrate that GAIN can achieve up to 4.11x speedup in training throughput and reduce up to 86.5% of traffic overhead. Furthermore, through theoretical analysis, we illustrate that GAIN can achieve even more substantial performance gains with a larger number of clients while guaranteeing privacy protection.

In recent years, the integration of federated learning and deep learning technologies has become increasingly prevalent in privacy-preserved scenarios, such as smart health applications and automatic financial support. However, the inherent robustness issue in deep learning poses potential risks to federated learning systems when subjected to various attack methods. These attacks can inflict damage during the training and testing phases, perturbing models and inputs. To enhance the robustness of existing federated learning systems, we propose a novel framework called RobFL. This framework incorporates a unique feature learning module - feature center separation learning - that is specifically designed to increase the margins between different classes in the feature space, thereby augmenting the difficulty of attacks employing imperceptible perturbations on inputs. Furthermore, we design a malicious center detection method to detect malicious clients and mitigate their adverse impact. Extensive experiments substantiate the robustness of our proposed framework, RobFL, demonstrating its resilience against both evasion attacks and poisoning attacks.

The geographically distributed edge servers can naturally draw power from nearby renewable energy (RE) generators. Complemented by the dynamic scheduling of energy storage batteries, edge service providers (ESPs) can thus build low- or even zero-carbon edge computing systems. Nevertheless, the distributed and heterogeneous nature of edge computing systems, as well as the limited information sharing among ESPs, leads to a more complex battery planning problem than that in cloud computing. The unpredictability of RE resources further complicates the problem, making conventional model-based approaches ineffective. To this end, we propose a multi-agent deep reinforcement learning (MADRL) approach for the independent decision making of individual ESPs. Particularly, MADRL takes privacy into account by ensuring that no sensitive information is disclosed among ESPs. For better model training, we further customize the invalid action masking and develop action transformation techniques based on segmented linear optimization. Extensive experiments demonstrate that, with our proposed approach, the overall carbon emission of edge computing systems can be significantly reduced (by over 60%) while maintaining acceptable operation costs in battery scheduling.

Measurements for the quality of end-to-end network services (QoS) are crucial to ensure stability, reliability, and user experience for distributed edge clouds. Measuring all QoS data brings significant costs. Existing QoS measurement methods attempt to use sparse measured QoS data to estimate unmeasured QoS data. But they suffer from limited estimation accuracy when facing QoS data with high sparsity or significant volatility. Moreover, they also consume high sampling and training costs during continuously online measurements. Our preliminary analysis reveals that end-to-end QoS is strongly temporal-spatial related. It inspires us to leverage partially measured QoS data to impute temporal-spatial-related unmeasured QoS data for reducing measurement costs. To predict unmeasured QoS data precisely with low computational costs, we propose a novel QoS Measurement framework based on Residual Graph Neural Network (QM-RGNN), which inputs QoS data as a graph and outputs the prediction of unmeasured QoS data. It consists of three core components: 1) an encoder-decoder model QM-GNN with GCN as the encoder and MLP as the decoder is devised for efficient QoS prediction, and a residual module is introduced in QM-GNN to tackle highly sparse and volatile QoS data; 2) a dynamic adaptive sample ratio is proposed to reduce the sampling costs; 3) an online learning pattern is designed to reduce continuous training costs. Experiments on two real-world industrial edge cloud datasets demonstrate the superiority of QM-RGNN in QoS measurement. It obtains at least a 37.5% reduction of relative RMSE between ground-truth and predicted QoS data with up to 90% training cost reduction and 22.7% sampling cost reduction.

Federated learning (FL) is a collaborative machine learning approach that enables multiple clients to train models without sharing their private data. With the rise of deep learning, large-scale models have garnered significant attention due to their exceptional performance. However, a key challenge in FL is the limitation imposed by clients with constrained computational and communication resources, which hampers the deployment of these large models. The Mixture of Experts (MoE) architecture addresses this challenge with its sparse activation property, which reduces computational workload and communication demands during inference and updates. Additionally, MoE facilitates better personalization by allowing each expert to specialize in different subsets of the data distribution. To alleviate the communication burdens between the server and clients, we propose FedMoE-DA, a new FL model training framework that leverages the MoE architecture and incorporates a novel domain-aware, fine-grained aggregation strategy to enhance the robustness, personalizability, and communication efficiency simultaneously. Specifically, the correlation between both intra-client expert models and inter-client data heterogeneity is exploited. Moreover, we utilize peer-to-peer (P2P) communication between clients for selective expert model synchronization, thus significantly reducing the server-client transmissions. Experiments demonstrate that our FedMoE-DA achieves excellent performance while reducing the communication pressure on the server.

Electric vehicles (EVs), which have become one of the most important commuting vehicles in the world, heavily depend on the support of robust and efficient grids. Many researchers focus on optimizing the charging of EVs by the grid. However, they overlook the emergency charging when the large-scale grid fails. Inspired by the DC-2-DC technology, EVs can achieve vehicle-2-vehicle (V2V) energy sharing between each other, which inspires us to study leveraging the significant number of electric buses (e-buses) as effective and cost-efficient standby energy to charge low-power EVs when a large-scale grid outage occurs, whereas the feasibility, scheduling algorithm, and performance of e-bus-based V2V energy sharing remain open questions. With this in mind, we first reveal that it is feasible for e-buses to serve as effective standby power for low-power EVs, after careful analysis of real-world data. Then, we conduct a data-driven estimation of the energy consumption to determine the volume of the V2V shared energy for large-scale EVs. Accordingly, we formulate the e-bus-based V2V energy sharing problem, whose two objectives are to maximize the total number of the sufficiently charged EVs and to minimize the distance of these EVs moving to the e-bus for charging. The first objective is to charge more low-power EVs with the limited energy volume of the e-buses and the second objective is to reduce the range anxiety of the low-power EV drivers. Observing that existing algorithm is time-consuming or inefficient, which cannot be applied for the problem instance with a large number of e-buses and EVs, we design a low-complexity approximation algorithm for the problem. Both theoretical analysis and comprehensive data-driven evaluation demonstrate that the proposed algorithm, 1) significantly optimizes the optimization objectives by 23.6% and 15.8% on average, and up to 34.8% and 34.0% in extreme cases, compared with the existing approximation algorithm and 2) achieves over$100\times $execution speed improvement compared to the linear programming (LP)-based algorithm and evolutionary learning (EL) algorithms. The results demonstrate that the proposed algorithm achieves a better overall performance and makes it a promising solution for large-scale problem instances.

Crowdsensing-based mobile Internet, while facilitating users’ daily life, also raises privacy concerns because of sharing user location trajectories. Combining with open-source network information, these trajectories reveal the semantics of users’ social behaviors in their travels, thus indicating their behavioral traces. Based on such social mobilities, attackers can explore users’ potential behavioral patterns and launch powerful behavioral-semantic inferential attacks for behavior prediction, identity identification, and threatening users’ location-related mobile privacy. Even through privacy protection, the released similar anonymous semantics may still bring significant privacy gains to such attacks. To the best of our knowledge, there is still no effective technique to counter such attacks and protect user behavioral semantics in mobile Internet services. To this end, this article proposes a posterior behavioral-semantic privacy-preserving solution, BSPri, by simulating the inferential attacks to eliminate the privacy risks associated with released traces. Specifically, we represent the logical association between semantic attributes and propose a similar semantic clustering and ranking method. Then, we formalize the user social-mobility stochastic process to characterize the privacy risks arising from the attacker’s observation of the released trajectory, and define a observation-based posterior privacy authentication criteria to filter anonymous semantics further. Finally, we generate synthetic trajectories with similar anonymity semantics, which bring attackers insignificant privacy gain, for users to participate in applications. Extensive experiments with the real-world data set demonstrate that our BSPri achieves an effective privacy-preserving performance, i.e., rigorous posterior-privacy constraint with limited data-availability loss, such as, distance 752 m$(47$-m closer, compared with our previous work MSP), direction deviation$39.5^{\circ }~(11.5^{\circ }$smaller), and semantic similarity$43.4\%~(8.4\%$closer).

While facilitating user daily lives, the booming development of mobile Internet services raises their privacy concerns because of the need to share travel trajectories. Due to the differences in access patterns and sensitive location attributes, behavioral semantics of user travel suffer from different degrees of leakage risks and have personalized privacy requirements. Semantic mobility-aware personalized privacy protection is still an open research issue in mobile scenarios. To this end, we propose a differentially semantic-generalized behavioral trajectory (DSG-BTra) for achieving privacy-preserving mobile Internet services. Specifically, we first explore the underlying behavioral patterns by formalizing user social mobility. Then, we evaluate the differential privacy sensitivity of user behavior to indicate the risks it faces. Finally, we generalize the behavioral semantics with a sensitivity-quantified strength and generate a DSG-BTra for the user to participate in mobile services. Extensive experiments with real-world data sets demonstrate DSG-BTra achieves flexible balance between privacy protection and application QoS, e.g., reducing the inference probability to 0.18–0.26 with a semantic similarity of 0.3–0.5.

The novel IoT-based data sensing and service mode promotes the booming development of crowdsensing-based mobile communication services (MCSs). MCS facilitates people’s daily lives by providing appropriate services according to the user’s mobile travels. These traveling trajectories, combined with open-source network information, reveal multimodal semantic information implicit in user mobility. Mining these mobile semantics contributes to understanding user mobility more sufficiently. It covers a wide spectrum of applications in mobile scenarios. For service providers, it improves the quality of their services. For mobile users, it helps to design a more rigorous privacy-preserving mechanism. For third-party platforms, such mobility analysis enhances their data management, analysis, and reusage. It has always been an open research issue in mobile computing. We are motivated to conduct a complete and comprehensive survey on semantic mining within the scope of MCS, forming a complete overview of mobile semantic perception. Specifically, we first review existing research works on feature selection. We classify them into five categories, depending on their representation forms. Then, we summarize the research on mobile semantic perception and cluster them to be three groups according to the digging depth of the represented semantics. To complete the overview, we also review the applications of learning algorithms and discuss the open opportunities and challenges for future works.

Service Function Chaining (SFC) dynamically links multiple Virtual Network Functions (VNFs) to provide flexible and scalable network services for network entities and users. Implementing SFCs at the network edge provides instant VNF service yet is confined by the limited edge resources. Existing strategies suggest either to deploy new VNFs for diverse service provision or to deploy more installed VNFs for reliable service provision. However, these one-sided optimizations fail to realize comprehensive improvements in the network service quality. To this end, the motivation of this paper is to consider a more comprehensive SFC deployment plan to provide more efficient network services. In this paper, we propose DeepSFC, an online SFC deployment scheme at network edge. Our DeepSFC considers the impact of resource allocations and deployment locations on the average latency of overall service requests. It realizes an elegant trade-off between the diversity and the availability of SFCs by adopting the Deep Reinforcement Learning (DRL) method. To be specific, we first determine the type and number of VNFs that need to be deployed. Thereafter, we optimize the deployment locations of these chosen VNFs in the service chain, considering the impact of dynamic bandwidth in the real network. For more general scenarios wherein users’ service requirements change or the deployed server crashes, we further relocate the VNF deployment with the joint consideration of performance degradation and migration cost. Evaluation results show that DeepSFC outperforms its competitors in various experimental settings and responds the requests with lower average latency.

Blockchain, as an emerging technology, has gained widespread research in academia and industry due to its decentralization and traceability. As an important form of blockchain, consortium chains are often applied in the Internet of Things (IoT) to ensure the authenticity and reliability of data. Within consortium chains, the practical Byzantine fault tolerance (PBFT) method is a key technology for ensuring the data consistency. It plays a central role in enhancing the system performance, security, and scalability. However, with the increase in the number of user nodes and the diversification of application scenarios, PBFT faces significant challenges in maintaining performance and security, particularly due to the increased communication overhead, longer consensus latency (CL), and risks of malicious attacks on the leader node. To overcome these challenges, this article proposes a new blockchain consensus mechanism, namely the reputation awareness randomization consensus mechanism in the blockchain systems (RARCs). This mechanism first builds an evaluation model for the nodes, dividing them into ordinary nodes and candidate nodes through the reputation assessment. Second, it constructs a consensus node selection strategy to select the high-quality consensus nodes from the candidate nodes. Finally, RARC establishes a leader node randomization selection mechanism, increasing the unpredictability of the leader node and reducing the probability of the malicious attacks. Through the theoretical analysis and simulation experiments, we demonstrate that the RARC can significantly reduce the CL, enhance the throughput, and increase the unpredictability of the leader node, thereby improving the performance and security of the blockchain systems.

Random number generation is essential for applications in simulation, numerical analysis, and data encryption. The ubiquitous presence of system-on-chip (SoC) field-programmable gate array (FPGA) embedded devices in critical sectors necessitates robust random number generators (RNGs) that operate within these specialized environments. Traditional RNGs in GNU/Linux systems derive entropy from peripheral hardware events, which are scarce in SoC FPGA platforms lacking standard PC peripherals. Addressing this challenge, this paper proposes a novel random number generator named NDSTRNG that leverages the unique hardware structure of the SoC FPGA and the inherent randomness of GNU/Linux. The proposed generator employs a non-deterministic sampling model to circumvent reliance on various peripherals while ensuring unbiased output via a linear feedback shift register (LFSR)-based post-processing method. We implement this random number generator in SoC FPGA GNU/Linux using minimal FPGA resources and only one Linux task for sampling. NDSTRNG achieved a throughput exceeding 700 Kbps. Moreover, the entropy source of the generator is evaluated using NIST SP 800-90B, while the quality of the generated random numbers is assessed through ENT, NIST SP 800-22, and DIEHARDER. The results confirm that NDSTRNG meets the stringent criteria for both high-quality and high-speed random number generation, making it suitable for deployment in communication, defense, and medical domains where reliable RNGs are indispensable.

Pre-copy-based Virtual Machine (VM) live migration seamlessly migrates the running VM to the target physical server by pre-copying memory pages and realizing updates through loop iterations. This method, which has high reliability and robustness, can effectively achieve load balancing and reduce energy consumption. It is widely used in the industry to manage server cluster resources. However, it also involves many problems, such as many dirty memory pages resulting from repeated transmission and convergence failure of iterative transmission. Hence, pre-copy live migration cannot efficiently allocate server cluster resources. To resolve these problems, a VM pre-copy live migration technology based on the similarity of dirty memory pages is proposed in this paper. The access priority of historical dirty memory pages was determined by calculating the similarity weight based on the Hamming distance. A priority-based delay transmission scheme for high dirty pages and low dirty pages was used to decrease the frequent transmission of high dirty memory pages, increase the convergence speed of the live-migration iterative copy process, and reduce the overall migration time of VMs. A comparative analysis of experimental results based on six dimensions showed that the proposed method achieved better migration efficiency than the conventional live migration strategy.

The emergence of next-generation latency-critical applications places strict requirements on network latency and stability. Edge cloud, an instantiated paradigm for edge computing, is gaining more and more attention due to its benefits of low latency. In this work, we make an in-depth investigation into the network QoS, especially end-to-end latency, at both spatial and temporal dimensions on a nationwide edge computing platform. Through the measurements, we collect a multi-variable large-scale real-world dataset on latency. We then quantify how the spatial-temporal factors affect the end-to-end latency, and verify the predictability of end-to-end latency. The results reveal the limitation of centralized clouds and illustrate how could edge clouds provide low and stable latency. Our results also point out that existing edge clouds merely increase the density of servers and ignore spatial-temporal factors, so they still suffer from high latency and fluctuations. Based on a quantified latency impact factor, we have proposed several optimization strategies for edge cloud latency and validated their effectiveness. We also propose a robust prototype edge cloud model based on lessons we learn from the measurement and evaluate its performance in the production environment. Evaluation result shows that edge clouds achieve 84.1% latency reduction with 0.5 ms latency fluctuation and 73.3% QoS improvement compared with the centralized clouds.

Geo-distributed edge data centers (EDCs) are expected to handle a large portion of tasks offloaded from cloud data centers for various emerging edge services. However, the high energy consumption and cost add a huge burden to edge service providers (ESPs). This presents a unique challenge as traditional energy-saving strategies applicable in cloud data centers fail to apply to EDCs, given the latency-sensitive nature of edge services. In response, we put forward an innovative electric vehicle (EV)-assisted edge computing architecture that leverages idle computing resources and stored energy of EVs. Our design aims to decrease energy expenditures for ESPs by choosing EVs with more economical service costs to handle a portion of the edge services during critical periods. We construct an energy cost-aware workload offloading model and discretize the original model into multiple small-scale solvable forms in both temporal and spatial dimensions. Furthermore, we reconfigure the Kuhn-Munkres algorithm to produce an online joint matching solution to counter QoS decline, generating a mutually advantageous situation for ESPs and EV participants. Upon experimentation with real-world traces, our design demonstrates a significant reduction in total energy cost (up to 31%) and offers considerable incentives for EV participants.

The rapid advancement of autonomous driving technologies has brought the significance of Autonomous Emergency Braking (AEB) systems, which are paramount in mitigating collision risk and elevating road safety by preemptively applying brakes when a potential collision is detected. Within the core mechanisms of AEB systems, the Time-to-Collision (TTC) estimation plays a pivotal role, in quantitatively determining the criticality and timing for initiating braking interventions. However, existing TTC estimation approaches exhibit sensitivity to diverse driving scenarios, compromising the performance of AEB systems, especially in instantaneous situations. To address these issues, this paper presents DTTCNet, a novel supervised deep learning model for TTC estimation that leverages multi-scale transformer architectures and multi-task losses, thereby enhancing precision and boosting system performance. The DTTCNet first extracts spatiotemporal features from raw sensor data and utilizes a supervised training strategy. The multi-scale transformer architecture effectively captures variations across different scales, while the multi-task loss function optimizes the network training performance. Our experimental results on a challenging dataset demonstrate that DTTCNet achieves approximately 20% performance improvements over existing methods in terms of accuracy. This signifies a promising approach to augmenting the safety of autonomous driving systems with the integration of aftermarket mobile devices (e.g., Mobileye and Bosch products).

Traditional network functions are typically implemented using specialized hardware appliances, which are expensive and difficult to upgrade. Network Function Virtualization (NFV) offers an effective approach to address these challenges by implementing comparable functionalities on commercial servers through software-based virtualization. In NFV, a sequence of Virtual Network Functions (VNFs) is orchestrated to form a Service Function Chain (SFC) that provides flexible network services. However, scheduling SFCs with multiple resource constraints to achieve high reliability poses a critical challenge. Existing approaches often assume offline scheduling and overlook the dynamic nature of heterogeneous resource loads across regions. Moreover, they primarily focus on individual VNFs rather than considering the cross-region scheduling of the entire SFC, which can result in increased transmission delay. In this paper, we investigate the problem of service function chain scheduling across multiple regions (SFCS-MR) with deadline constraints, aiming to maximize the success rate of requests. We formulate this problem as an Integer Linear Programming (ILP) model and prove its NP-hardness. To address this problem effectively, we propose a two-stage algorithm that determines whether an SFC requires cross-region scheduling and selects the suitable regions for its execution. Through extensive experimental evaluations, we demonstrate that our cross-region SFC scheduling solution can achieve a maximum improvement of 32.42% in the overall request success rate compared to benchmarks.

Each flow usually needs to traverse a specific service function chain (SFC), which is composed of multiple network functions implemented through virtualization technology or hardware, before reaching their destinations. All network functions are deployed across commodity nodes inside a network environment. Each flow needs to change its default routing path to visit the corresponding SFC correctly. These changed routing paths will cause network load imbalance. Therefore, an intelligent routing planning method is needed to balance the traffic load while satisfying various SFC requirements of different flows. In this paper, we propose to leverage SRv6, a new routing technology, to centrally plan the routing path for each flow with any SFC request. We then present a general model of the SFC planning problem (SFCP), planning flows’ routing paths to minimize the maximum link utilization of the network, and prove that the problem is NP-hard. For this reason, we transform the SFCP problem into a graph theory optimization problem and propose SFCPlanner, an online SFC planning method based on deep reinforcement learning. Moreover, we design the node mask and incremental training mechanisms to make SFCPlanner achieve better performance. The experiment results show that our SFCPlanner can solve the SFCP problem in large-scale networks more precisely. It can reduce the maximum link utilization by 32% compared with the benchmark algorithm while ensuring each flow traverses the correct SFC.

Edge storage promises to be crucial for edge computing infrastructure, which enables users to access data within a low delay from widespread storage nodes at the network edge. The key challenge is how to integrate massive geographically distributed weak edge nodes to form an efficient storage system, enabling users to launch data operations from any node or retrieve the desired data across the entire distributed system. To address this data-sharing problem, researchers from both the traditional peer-to-peer (P2P) overlay networking and emerging edge computing fields have proposed some decentralized indexing mechanisms. However, existing studies lack insightful descriptions and analyses about the nature of the data-sharing problem at the network edge. It motivates us to rethink the edge data-sharing framework and provide the problem reformulation for analyzing the limitations of existing schemes. We reveal that the existing data-sharing schemes fail in complex network topologies which can be regarded as high-dimensional network spaces beyond the representation of low-dimensional Euclidean spaces or other existing hash spaces. A better space abstraction is an urgent need to alleviate the performance degradation due to the dimensional mismatch between network spaces and virtual spaces. To fill this gap, this paper proposes the Kautz metric space, a novel space abstraction extended from Kautz graphs, where the coordinates and the metric are defined as Kautz strings and Kautz distances (i.e., the shortest distances in undirected Kautz graphs), respectively. We design a dynamic programming algorithm to directly compute the Kautz distances. Then, we propose KMSharing, an efficient edge data-sharing scheme: both nodes and data are represented in a Kautz metric space, where the Kautz distance of any two Kautz strings reflects the network delay of the corresponding nodes. The workflow of KMSharing consists of three core components: the virtual address allocation represents edge nodes in the Kautz metric space; the data-to-node mapping ensures the uniqueness of target nodes; and forwarding table construction ensures the data delivery. Theoretical analyses confirm that KMSharing ideally achieves$\mathcal {O}\left ({{ \tau }}\right)$network delays,$\mathcal {O}\left ({{ \log N }}\right)$overlay hops, and$\mathcal {O}\left ({{ 1 }}\right)$forwarding entries in an N-node edge system with the network radius$\tau $, while the successive ensuring data delivery. Its worst-case network delay$\mathcal {O}\left ({{ \tau \log N }}\right)$is also much better than${\mathcal {O}\left ({{ \tau N^{\alpha } }}\right)},\alpha \mathrm {\in }(0,1)$, the worst case of the baselines using Euclidean spaces. Evaluation on various network topologies also shows that our KMSharing effectively reduces network delays and indexing costs than existing data-sharing schemes.

To repair a failed block in the erasure-coded storage system, multiple related blocks have to be retrieved from other storage nodes across the network. Such a process can lead to significant incast-type repair traffics and delays. The existing efforts mainly try to schedule the transmission of the requested blocks across different storage nodes to avoid network congestion. At their cores, they utilize part of the involved hosts to rely on or aggregate the file blocks from others. While we notice that, the programmability and capability of today’s network devices (i.e., routers and switches) bring a great opportunity to further speed up the repair progress by aggregating the file blocks with such devices. By mitigating the aggregation operations from the network edges to network cores, it is possible to save more time and bandwidth. With this intuition, we propose Paint, a parallelized in-network aggregation framework for failure repair. Paint utilizes programmable switches to aggregate relevant data and improves the repair performance by implementing multiple parallelized repair pipelines. We propose a series of novel and time-friendly algorithms to construct the routing paths for Paint and design the Aggregation Control Protocol to implement Paint in production clusters. For all we know, this is the first work to explore and implement parallelized in-network repair with programmable switches. The extensive experiments on the prototype system and real-world datasets indicate that Paint can significantly improve repair performance while effectively reducing bandwidth overhead.

In this article, we investigate the edge cache deployment for high definition (HD) urban map provisioning, which is an essential building block for future autonomous driving. Given a deployment budget, we first formulate a satisfied downloading request maximization (SDRM) problem to obtain the deployment locations and customized cache sizes. The SDRM problem is unsolvable directly as the urban transportation traffic is highly dynamic and future traffic conditions are unknown in advance. Based on data analytics of the vehicular GPS trace, we propose an architecture named CoDe , built on which we transform and address the SDRM problem. The reference implementation of CoDe is respectively developed based on the insights from two urban-scale carpool GPS traces. The novelty and contributions of CoDe lie in its three-layer design. Particularly, at data feeding layer, we make use of two urban 60-day GPS traces involving respectively 37,801 and 17,517 vehicles, to extract the analytics samples. At mobility characterization layer, we conduct extensive data analytics on traffic mobility in terms of their distribution, correlation, and variation, to mine the crucial traffic mobility patterns for strategy customization. At cache deployment layer, we propose the K -order subgraph for each block to record the moving statistics within its K -order neighborhood, and transform the SDRM problem accordingly. Then, the R oute we I ght ba S ed gr E edy ( RISE ) algorithm is devised for the problem, which can deliver the deployment decisions. Extensive data-driven experiments are carried out to demonstrate the superior performance of CoDe in terms of request hit ratio and caching resource utility.

Air-to-ground (A2G) networks, using unmanned aerial vehicles (UAVs) as base stations to serve terrestrial user equipments (UEs), are promising for extending the spatial coverage capability in future communication systems. Coordinated transmission among multiple UAVs significantly improves network coverage and throughput compared to a single UAV transmission. However, implementing coordinated multi-point (CoMP) transmission for UAV mobility requires complex cooperation procedures, regardless of the handoff mechanism involved. This paper designs a novel CoMP transmission strategy that enables terrestrial UEs to achieve reliable and seamless connections with mobile UAVs. Specifically, a computationally efficient CoMP transmission method based on the theory of Poisson-Delaunay triangulation is developed, where an efficient subdivision search strategy for a CoMP UAV set is designed to minimize search overhead by a divide-and-conquer approach. For concrete performance evaluation, the cooperative handoff probability of the typical UE is analyzed, and the coverage probability with handoffs is derived. Simulation results demonstrate that the proposed scheme outperforms the conventional Voronoi scheme with the nearest serving UAV regarding coverage probabilities with handoffs. Moreover, each UE has a fixed and unique serving UAV set to avoid real-time dynamic UAV searching and achieve effective load balancing, significantly reducing system resource costs and enhancing network coverage performance.

With the advent of network function virtualization (NFV) and mobile edge computing (MEC), outsourcing network functions (NFs, i.e., firewall) to the MEC is becoming popular among network service providers. Notably, NF outsourcing raises an essential security concern about whether these outsourced NFs and associated service function chains (SFCs) are correctly implemented according to enterprises’ specifications. In particular, SFC with parallel VNFs, which take advantage of parallelism, have been conducted to reduce the traffic delay of traditional sequential SFC, called the hybrid SFC in this paper. Nevertheless, how to ensure correct behaviors and discover runtime mistakes for hybrid SFC remains an open problem.In this paper, we propose vHSFC, a verification scheme for hybrid SFC, enabling enterprises to verify the correctness of SFC enforcement in real-time. vHSFC achieves its goal with a lightweight verified routing protocol, which detects various hybrid SFC violations and attacks, i.e., packet modification, incompliant forwarding path, etc. To demonstrate the feasibility and performance of vHSFC, we have implemented the prototype on top of several containers and conducted extensive experiments with real traffic. The experimental results show that our vHSFC can continuously ensure proper enforcement and discover unexpected violations while incurring sensible overhead.

A frequency bursting pattern (FBP) in temporal graphs represents some interaction behavior that accumulates its frequency at the fastest rate. Mining FBPs is essential to early warning of emergencies. However, existing studies on frequency-based pattern mining in graphs do not consider the temporal information and bursting features of a subgraph pattern. As a result, they may not provide effective and efficient mining algorithms for FBP discovery. In this paper, we study the problem of discovering top-k FBPs in temporal graphs. We present a novel model, referred to as maximal (m, θ)-bursting pattern, to describe FBPs in a temporal graph, which is a subgraph with a size larger than m that accumulates its frequency at the fastest rate during a time interval of length no less than θ. A naive solution for top-k FBPs discovery is to use the best-first search algorithm, where the burstiness threshold changes as more patterns are mined. However, this method will result in huge search space since we need to check every possible time interval for a candidate pattern in the temporal graph. To tackle this problem, we devise an online top-k framework in which k candidate results are maintained from the initial timestamp to the end in the temporal graph. Under the new framework, we further conceive two optimization strategies by exploiting incremental subgraph matching and Evolutionary Game Theory to boost the performance. Extensive experiment results on five real temporal graphs show that our algorithm has higher efficiency, effectiveness and scalability.

Edge computing is migrating services from remote clouds to the network edge, where a vast amount of data is also flowing into edge nodes. In this context, the Edge Data-Sharing System (EDSS) enhances service quality by enabling edge nodes to cooperate. However, the EDSS is suitable for precise search and faces the existing high overhead when many users retrieve similar data. To solve the obstacle, this paper proposes a similarity-based edge storage system, SESS, which leverages the software-defined edge network to realize efficient storage and retrieval of similarity data. We first design RealminHash, a core module of SESS, for efficient signature and and index for each data. Then, SESS calculates the storage strategy based on the similarity between data. Importantly, SESS adjusts this strategy using periodic network information to ensure load balancing. Experimental results demonstrate that SESS realizes the nearest-neighbor storage while maintaining load balancing. SESS outperforms the well-known k-means and spectral clustering methods in terms of accuracy and latency and supports millisecond similar queries.

Storing files at the network edge has become a new paradigm of storage systems, which is promising to mitigate network congestion and reduce file retrieval latency. However, the traditional file storage scheme cannot effectively meet the requirements of rapid indexing and load balance when applied directly to the edge. Moreover, due to the dynamic nature of the edge environment where edge servers can join or leave at will, it is necessary for the storage scheme to adjust with minimal disruption. In this paper, we propose EdgeAnchor, a novel edge storage strategy that is composed of the two-layer hash mappings. The first layer, file-to-bucket mapping, adopts the pseudo-deletion algorithm to deal with the variations in file size, while the second layer utilizes the multiple bucket-to-server mapping to adapt to the heterogeneity in the servers’ storage capacities. Furthermore, EdgeAnchor constructs a list of deleted or added working sets for each bucket and creates a dictionary for the mappings between buckets and edge servers. In the manner, EdgeAnchor ensures a rapid file index and balances server load at the dynamic network edge. We also attach the mathematical analyses to EdgeAnchor, which theoretically proves its logarithmic complexity of hash operations and memory accesses. The experiments conducted on real-world datasets demonstrate that EdgeAnchor achieves the file index throughput twice as high as that of Consistent Hashing, under the constraints of load balance. Additionally, it ensures a low and stable data migration volume, when adding or removing edge servers consecutively.

The emergence of next-generation latency-critical applications places strict requirements on network latency and stability. Edge cloud, an instantiated paradigm for edge computing, is gaining more and more attention due to its benefits of low latency. In this work, we make an in-depth investigation into the network QoS, especially end-to-end latency, at both spatial and temporal dimensions on a nationwide edge computing platform. Through the measurements, we collect a multi-variable large-scale real-world dataset on latency. We then quantify how the spatial-temporal factors affect the end-to-end latency, and verified the predictability of end-to-end latency. The results reveal the limitation of centralized clouds and illustrate how could edge clouds provide low and stable latency. Our results also point out that existing edge clouds merely increase the density of servers and ignore spatial-temporal factors, so they still suffer from high latency and fluctuations. Based on the observations, we propose a robust prototype edge cloud model based on lessons we learn from the measurement and evaluate its performance in the production environment. The further evaluation result shows that edge clouds achieve 84.1% latency reduction with 0.5ms latency fluctuation and 73.3% QoS improvement compared with the centralized clouds.

Mobile edge computing emerges as a new paradigm to provide low-latency network services in the close proximity to users. Based on the network function virtualization (NFV) technology, network services can be flexibly provisioned as service function chain (SFC) deployed at edge servers. In some scenarios, such as the vehicular or UAV-assisted edge computing, the network topology varies rapidly due to the mobile edge servers, which changes the routing path between adjacent VNFs in an SFC. Migrating SFC to adapt to the frequent topology change can reduce the SFC latency, and improve the quality of users’ experience. However, frequent SFC migration will unavoidably increase the operation cost. In this paper, to optimize the system performance in a cost-efficient manner, we study the SFC migration problem in dynamic networks with a long-term cost budget constraint. We then propose the Topology-aware Min-latency SFC Migration (TMSM) method to strike a desirable balance between the SFC latency and the migration cost. Specifically, we first apply the Lyapunov optimization to decompose the long-term optimization problem into a series of real-time optimization sub-problems. Since the decomposed problem is still NP-hard, a Markov approximation based heuristic is proposed to seek a near-optimal solution for each sub-problem. Compared with the rerouting-only strategy, which does not migrate any VNF, our TMSM reduces the latency by at least 21% on average in each time slot. Extensive evaluations show that the proposed algorithm achieves a better tradeoff between the SFC latency and migration cost than the baselines.

Edge computing (EC) is a distributed computing paradigm that brings computation and data storage closer to the data sources. With the rapid development of EC, offloading scientific computing and data processing tasks from end devices to edge nodes (ENs) can satisfy these tasks’ requirements. However, a single EN with limited computing capacity is usually insufficient to handle these tasks. Hence, using a coalition structure (CS) of many ENs to handle multiple concurrent tasks in an EC environment becomes a feasible scheme. Still, many existing methods cannot be used directly in this scenario because of enormous CS solution space, low search speed, long-running time, poor optimal solution quality, etc. In response, we propose an arbitrary discrete political optimizer (ADPO) algorithm with a discrete recent-past position updating strategy to explore the potential CS space. Unlike other heuristic algorithms, ADPO further improves the better solutions by interacting with each other in the parliamentary affairs phase. After that, we formulate an integer programming (IP) optimization model to alleviate the low search speed or long time consuming. Finally, extensive experiments demonstrate that ADPO is superior to the existing heuristic algorithm. In addition, the IP model excels in exiting algorithms at the running time (milliseconds level) and resource occupied ratio.

Abstract With the rapid development of information technologies, multi-source heterogeneous data has become an open problem, and the data is usually modeled as graphs since the graph structure is able to encode complex relationships among entities. However, in practical applications, such as network security analysis and public opinion analysis over social networks, the structure and the content of graph data are constantly evolving. Therefore, the ability to continuously monitor and detect interesting patterns on massive and dynamic graphs in real-time is crucial for many applications. Recently, a large group of excellent research works has also emerged. Nevertheless, these studies focus on different updates of graphs and apply different subgraph matching algorithms; thus, it is desirable to review these works comprehensively and give a thorough overview. In this paper, we systematically investigate the existing continuous subgraph matching techniques from the aspects of key techniques, representative algorithms, and performance evaluation. Furthermore, the typical applications and challenges of continuous subgraph matching over dynamic graphs, as well as the future development trends, are summarized and prospected.

For the efficient analysis of geo-distributed datasets, cloud providers implement data-parallel jobs across geo-distributed sites (e.g., datacenters and edge clusters), which are generally interconnected by wide-area network links. However, current state-of-the-art geo-distributed data analytic methods fail to make full use of the available network and computing resources. The main reason is that such geo-distributed methods must wait for bottleneck sites to complete the corresponding transmission and computation in each phase. Furthermore, such geo-distributed methods may be impractical to the network bandwidth dynamicity and diverse job parallelism. To this end, we propose a Simultaneous Data Transfer and Processing (SDTP) mechanism to accelerate wide-area data analytics, with the joint consideration of network bandwidth dynamics and job parallelism. In the SDTP, a site can execute the computation, provided that it obtains the required input data. As a result, the input data loading, map, shuffle, and reduce phases at each site need not wait for the completion of the previous phases of other sites. We further improve the SDTP method by offering more accurate time estimation and generalizing the mechanism to dynamic situations. The trace-driven results demonstrate that SDTP can improve the wide-area analytic job response time by 19% to 72% compared to other methods.

Mobile edge computing is a new paradigm in which the computing and storage resources are placed at the edge of the Internet. Data placement and retrieval are fundamental services of mobile edge computing when a network of edge clouds collaboratively provide data services. These services require short-latency and low-overhead implementation in network and computing devices and load balance on edge clouds. However existing methods such as distributed hash tables (DHTs) are not enough to achieve efficient data placement and retrieval services for cooperative edge clouds. This article presents GRED, a novel data placement and retrieval service for mobile edge computing, which is efficient in not only the load balance but also routing path lengths and forwarding table sizes. GRED utilizes the programmable switches to support a virtual-space based DHT with only one overlay hop. Data location can be easily implemented on top of the GRED by associating a virtual position with each data by hashing, and storing the data at the edge server connected to the switch whose position is the nearest to the position of the data in the virtual space. We implement GRED in a P4 prototype, which provides a simple and efficient solution. Results from theoretical analysis, simulations, and experiments show that GRED can efficiently balance the load of edge clouds, and can fast answer data queries due to its low routing stretch.

With the widespread use of Internet of Things (IoT) devices and the arrival of the 5G era, edge computing has become an attractive paradigm to serve end-users and provide better QoS. Many efforts have been paid to provision some merging public network services at the network edge. We reveal that it is very common that specific users call for private and isolated edge services to preserve data privacy and enable other security intentions. However, it still remains open to fulfill such kind of mixed requests in edge computing. In this article, we propose a cooperative edge computing framework, i.e., HyEdge, to offer both public and private edge services systematically. To fully exploit the benefits of this novel framework, we define the problem of optimal request scheduling over a given placement solution of hybrid edge servers to minimize the response delay. This problem is further modeled as a mixed integer non-linear programming problem (MINLP), which is typically NP-hard. Accordingly, we propose the partition-based optimization method, which can efficiently solve this NP-hard problem via the problem decomposition and the branch and bound strategies. We finally conduct extensive evaluations with a real-world dataset to measure the performance of our method. The results indicate that the proposed method achieves elegant performance with low computation complexity.

The Device-as-a-service (DaaS) Internet of Things (IoT) business model enables distributed IoT devices to sell collected data to other devices, paving the way for machine-to-machine (M2M) economy applications. Cryptocurrencies are widely used by various IoT devices to undertake the main settlement and payment task in the M2M economy. However, the cryptocurrency market, which lacks effective supervision, has fluctuated wildly in the past few years. These fluctuations are breeding grounds for arbitrage in IoT data trading. Therefore, a practical cryptocurrency market supervision framework is very imperative in the process of IoT data trading to ensure that the trading is completed safely and fairly. The difficulty stems from how to combine these unlabeled daily trading data with supervision strategies to punish abnormal users, who disrupt the data trading market in IoT. In this article, we propose a closed-loop hybrid supervision framework based on the unsupervised anomaly detection to solve this problem. The core is to design the multi-modal unsupervised anomaly detection methods on trading prices to identify malicious users. We then design a dedicated control strategy with three levels to defend against various abnormal behaviors, according to the detection results. Furthermore, to guarantee the reliability of this framework, we evaluate the detection rate, accuracy, precision, and time consumption of single-modal and multi-modal detection methods and the contrast algorithm Adaptive KDE [ 19 ]. Finally, an effective prototype framework for supervising is established. The extensive evaluations prove that our supervision framework greatly reduces IoT data trading risks and losses.

This article proposes a novel Reverse Auction-based Computation Offloading and Resource Allocation Mechanism, named RACORAM for the mobile Cloud-Edge computing. The basic idea is that the Cloud Service Center (CSC) recruits edge server owners to replace it to accommodate offloaded computation from nearby resource-constraint Mobile Devices (MDs). In RACORAM, the reverse auction is used to stimulate edge server owners to participate in the offloading process, and the reverse auction-based computation offloading and resource allocation problem is formulated as a Mixed Integer Nonlinear Programming (MINLP) problem, aiming to minimize the cost of the CSC. The original problem is decomposed into an equivalent master problem and subproblem, and low-complexity algorithms are proposed to solve the related optimization problems. Specifically, a Constrained Gradient Descent Allocation Method (CGDAM) is first proposed to determine the computation resource allocation strategy, and then a Greedy Randomized Adaptive Search Procedure based Winning Bid Scheduling Method (GWBSM) is proposed to determine the computation offloading strategy. Meanwhile, the CSC's payment determination for the winning edge server owners is also presented. Simulations are conducted to evaluate the performance of RACORAM, and the results show that RACORAM is very close to the optimal method with significantly reduced computational complexity, and greatly outperforms the other baseline methods in terms of the CSC's cost under different scenarios.

Set query is a fundamental problem in computer systems. Plenty of applications rely on the query results of membership, association, and multiplicity. A traditional method that addresses such a fundamental problem is derived from Bloom filter. However, such methods may fail to support element deletion, require additional filters or apriori knowledge, making them unamenable to a high-performance implementation for dynamic set representation and query. In this paper, we envision a novel sketch framework that is multi-functional, non-parametric, space efficient, and deletable. As far as we know, none of the existing designs can guarantee such features simultaneously. To this end, we present a general shifting framework to represent auxiliary information (such as multiplicity, association) with the offset. Thereafter, we specify such design philosophy for a hash table horizontally at the slot level, as well as vertically at the bucket level. Theoretical and experimental results jointly demonstrate that our design works exceptionally well with three types of set queries under small memory.

In Network Function Virtualization (NFV), a series of Virtual Network Functions (VNFs) organized in a specific order (called Service Function Chain, SFC) could offer an end-to-end network service for a network flow. Recently, with the new results of the exploration of VNF parallelism, hybrid SFC (SFC contains parallel VNFs) is proposed to reduce the SFC execution delay. However, it remains challenging and open to optimally embed multiple hybrid SFCs into the network. In this paper, we target at the optimal embedding problem of multiple hybrid SFCs with the purpose of minimizing the cost in an online scenario. Specifically, we propose SFT-Box, an online approach that can respond to hybrid SFC embedding requests in real-time. SFT-Box is designed to i) transform SFCs from the traditional sequential form to a standardized hierarchical Service Function Tree (SFT) form, ii) calculate and store the low-cost sub-solutions of embedding common SFTs, and iii) provide prompt solution response based on stored sub-solutions. To the best of our knowledge, this is the first work to address the online optimal embedding problem of multiple hybrid SFCs. With extensive evaluations, we demonstrate that, compared with the benchmark methods, SFT-Box can achieve up to 30% cost-saving and at least$22\times $latency reduction in enabling real-time response.

Sketches are widely deployed to represent network flows to support complex flow analysis. Typical sketches usually employ hash functions to map elements into a hash table or bit array. Such sketches still suffer from potential weaknesses upon throughput, flexibility, and functionality. To this end, we propose Ark filter, a novel sketch that stores the element information with either of two candidate buckets indexed by the quotient or remainder between the fingerprint and filter length. In this way, no further hash calculations are required for future queries or reallocations. We further extend the Ark filter to enable capacity elasticity and more functionalities (such as frequency estimation and top-$k$query). Comprehensive experiments demonstrate that, compared with Cuckoo filter, Ark filter has$2.08\times$,$1.34\times$, and$1.68\times$throughput of deletion, insertion, and hybrid query, respectively; compared with Quotient filter, Ark filter has$4.55\times$,$1.74\times$, and$22.12\times$throughput of deletion, insertion, and hybrid query, respectively; compared with Bloom filter, Ark filter has$2.55\times$and$2.11\times$throughput of insertion and hybrid query, respectively.

With the advent of Network Function Virtualization (NFV) and Mobile Edge Computing (MEC), outsourcing network functions (NFs) to the MEC is becoming popular among network service providers (NSPs), since it brings the scalability and flexibility for NF deployment and maintenance. Each user’s request will go through a service function chain (SFC), which consists of several virtual network functions (VNFs, software substitutions for traditional hardware-based middleboxes) in a specific order, and then get a response. Unlike conventional hardware-based middleboxes, VNFs are not very reliable due to potential software faults and host malfunctions. Thus, a sensible way is to add redundancy for the primary VNFs of an SFC to enhance its availability. Nevertheless, which MEC node to place each VNF, and how many backup instances are enough to ensure the availability requirement of each SFC? These issues have not yet been resolved. In this article, we present the availability-aware provision of SFC (APoS) in the MEC environment with the primary goal of maximizing the number of served requests while meeting the requirements and reliability expectations of SFCs. For the APoS, we have primarily addressed the following two fundamental challenges: (i) First, how to efficiently map these primary and backup VNFs to meet the availability requirements of SFCs? At this point, we formulate it as an integer nonlinear programming (INLP) under the limitation of each MEC node’s resources. This issue is NP-hard, and a novel binary N-back search method is proposed to derive the optimal solution for the primary and backup VNFs mapping; (ii) Second, how can we reduce the latency for users to access their desired SFCs? Then, we investigate how to minimize the average delay for all requests in each time slot. To solve this problem, we design an online service switching (OSS) method, which jointly considers the queuing delay, communication delay, and switching delay. It achieves the optimal solution with a theoretical guarantee. Finally, we evaluate the proposed methods with real-world datasets. The results demonstrate that, compared with the benchmarks, our practices can achieve approximately 20% request acceptance gain and up to 30% delay reduction, on average.

The traditional migration methods are confronted with formidable challenges when data deduplication technologies are incorporated. First, the deduplication creates data-sharing dependencies in the stored files; breaking such dependencies in migration may attach extra space overhead. Second, the redundancy elimination makes the storage system reserves only one copy for each storage file, and heightens the risk of data unavailability. The existing methods fail to tackle them in one shot. To this end, we propose Jingwei, an efficient and adaptive data migration strategy for deduplicated storage systems. To be specific, Jingwei tries to minimize the extra space cost in migration for space efficiency. Meanwhile, Jingwei realizes the service adaptability by encouraging replicas of hot files to spread out their data access requirements. We first model such a problem as an integer linear programming (ILP) and solve it with a commercial solver when only one empty migration target server is allowed. We then extend this problem to a scenario wherein multiple non-empty target servers are available for migration. We solve it by effective heuristic algorithms based on the Bloom Filter-based data sketches. The Jingwei strategy can suffer from performance degradation when the heat degree varies significantly. Therefore, we further present incremental adjustment strategies for the two scenarios, which adjust the number of block replicas and their locations in an incremental manner. The mathematical analyses and trace-driven experiments show the effectiveness of our Jingwei strategy. To be specific, Jingwei fortifies the file replicas by 25% with only 5.7% of the extra storage space, compared with the latest “Goseed” method. With the small extra space cost, the file retrieval throughput of Jingwei can reach up to 333.5 Mbps, which is 12.3% higher than that of the Random method.

Placing popular data at the network edge helps reduce the retrieval latency, but it also brings challenges to the limited edge storage space. Currently, using available yet not necessarily reliable edge resources is common sense for edge space expansion, while deploying deduplication storage strategies is a general method for better space utilization. However, a contradiction arises when jointly implementing data deduplication with unreliable edge resources. On the one hand, the deduplication policy stipulates that any data chunk can be stored exactly once; on the other hand, the use of unreliable resources imposes that data should be backed up for the seek of file availability. To resolve such contradiction, we propose MEAN, a deduplication-enabled storage system using unreliable resources at the network edge. The core idea of MEAN is to place similar files together for better deduplication and maintain replicas of popular files for higher reliability. We first formulate this problem and prove its NP-hardness, then provide efficient heuristics based on similarity-aware hierarchical clustering. Three different reliability scenarios are comprehensively considered to develop our algorithms. We also implement a prototype system and evaluate the performance of MEAN with a real-world dataset. The results show that MEAN can fortify the file hit ratio under unreliable environments by 77% while reducing the file retrieval delay up to 71%, compared with the state-of-the-art approach.

RDF stream processing (RSP) has become a vibrant area of research in the Semantic Web community, which guarantees interoperability and opens up important applications. There have been efforts to extend RDF data and SPARQL query for representing streaming information and continuous querying functionalities. However, existing solutions will incur significant low throughput due to the recomputation of the results from scratch as the window slides. In this paper, we propose a novel graph-based framework, referred as IncTreeRDF, towards continuous SPARQL query evaluation over RDF data streams. Under the framework, the RDF data streams are modeled as streaming graphs; the SPARQL queries are translated into graph patterns and evaluated via continuous sub-graph pattern-matching over streaming RDF graphs. IncTreeRDF employs a query-centric auxiliary data structure called TStore to store some intermediate results, which supports fast incremental maintenance. Based on TStore, we can not only avoid re-computing matches of the query but also prune invalid updates. Besides, we define matching-free update, in which subgraph matching calculation can be avoided under this scenario. Extensive experimental results show that IncTreeRDF significantly outperforms existing competitors.

The modern network is equipped with many service functions to acquire high-quality service. The emergence of network function virtualization (NFV) provides a convenient way to accomplish the network services in the form of virtual network function (VNF) and also makes the scheduling solution of VNFs flexible. The VNFs can be deployed on commodity servers as software processes. Besides, multiple VNFs are chained in a specified order as a service function chain (SFC) to serve a given flow, increasing the scheduling difficulty to minimize the average flow completion time. In this paper, we study the problem of scheduling multiple SFCs with the constraint of different resource limitations in various commodity servers. This problem is typically formulated as an Integer Linear Programming (ILP) problem, which is NP-hard. To well tackle this problem, we propose a deep reinforcement learning (DRL) approach. It involves multi-step decision making, which can be naturally transformed into a DRL problem. We design specific reward and state representations for such a multi-resource scheduling problem. We also consider how to use DRL to handle online requests of SFCs. The experiment results demonstrate that the DRL approach can significantly reduce the average completion time of a set of SFC and achieves a cost saving of 39.94% against the benchmark method.

The traditional migration methods are confronted with formidable challenges when data deduplication technologies are incorporated. Firstly, the deduplication creates data-sharing dependencies in the stored files; breaking such dependencies in migration would attach extra space overhead. Secondly, the redundancy elimination heightens the risk of data unavailability during server crashes. The existing methods fail to tackle them at one shot. To this end, we propose Jingwei, an efficient and adaptable data migration strategy for deduplicated storage systems. To be specific, Jingwei tries to minimize the extra space cost in migration for space efficiency. Meanwhile, Jingwei realizes the service adaptability by encouraging replicas of hot data to spread out their data access requirements. We first model such a problem as an integer linear programming (ILP) and solve it with a commercial solver when only one empty migration target server is allowed. We then extend this problem to a scenario wherein multiple non-empty target servers are available for migration. We solve it by effective heuristic algorithms based on the Bloom Filter-based data sketches. Trace-driven experiments show that Jingwei fortifies the file replicas by 25%, while only 5.7% of the extra storage space is occupied compared with the latest "Goseed" method.

Data centers usually employ scale-out network topologies to provide sufficient network bandwidth for applications. The traditional equal-cost multi-path (ECMP) routing method is proposed to tackle the serious load imbalance problem across all links. However, it does not achieve the desired performance and still incurs low network throughput. Consequently, researchers recently redesigned some load balancing mechanisms for data center networks (DCNs) from different design dimensions. However, it remains open to systematically measure and evaluate their performance in various settings. It is impractical for evaluators to implement or simulate involved load balancing mechanisms. In this paper, we propose a unified framework, UFLB, which can well model and emulate representative load balancing mechanisms for data center networks in a lightweight way. This framework has overcome three significant challenges: model traffic distribution in the symmetry as well as asymmetry data center networks, characterize mainstream load balancing methods, and systematically combine them with high accuracy. We evaluate the effectiveness of our model under not only general settings of data center networks but also some special settings, such as various link failures and asymmetric topologies. The results indicate that the deviation rate of UFLB is within 15% against the implementation of load balancing mechanisms, such as ECMP, CONGA, DRILL, HERMES, PRESTO, in NS2, while it can be several orders of magnitude faster.

Edge computing emerges as a new paradigm to provide low-latency network services in close proximity to end users. Based on the network function virtualization (NFV) technology, network services can be flexibly and scalably provisioned as virtual network function (VNF) chains deployed at edge servers. With such advantages, both the industry and research communities have done extensive studies on deploying VNF chains at network edge. The existing works mainly take an ideal assumption that the network is totally safe and there are no malicious users. Therefore, they leverage all available resources to serve their users. However, such an assumption is impractical in real networks. Security services, such as firewall, deep packet detection, intrusion detection, are always required for production networks. The existing service deployment methods fail to consider the co-existence of security services and functionality services. In this paper, we present the topic of joint deployment of both security and functionality services, wherein the security services are responsible to check the data flows before being processed by the functionality services. To solve this problem, we propose the Secure Deployment Pattern, which aims to simultaneously satisfy the security protection and QoS requirements at network edge. It divides the services into two kinds, i.e., the user-oriented functionality services, and the service provider-oriented security services. In this case, it is very challenging to jointly deploy the security services and functional services with respect to the resource and latency constraints. We formulate this problem as an integer programming model, and propose the heuristic algorithms to solve it. As far as we know, this paper is the first step, which targets at a proper orchestration of security and functionality services in edge computing. Extensive evaluations show that the proposed algorithms are effective and efficient, in terms of the execution time and the average number of served requests.

Owing to the advancement of the Internet of Things (IoT) and 5G mobile technologies, various IoT devices produce massive data, which is usually transferred to nearby sites, such as edge nodes or datacenters. Many large-scale IoT applications need to analyze the data distributed across multiple sites to obtain final results. A dominant challenge of this type of data analytics is the heterogeneities of resource capacities across geo-distributed sites. In this article, we find that the resource capacity as well as the resource price differ among sites, and the price heterogeneity has a significant impact on geo-distributed IoT data analytics. Thus, each geo-distributed IoT data analytics job prefers to minimize the job execution cost while guaranteeing its deadline requirement under the resource constraints of involved sites. Specifically, we propose to jointly consider the resource heterogeneities of both capacity and price, and minimize the cost of each job before its deadline. We characterize this optimization problem as a quadratically constrained quadratic programming problem. To tackle such an NP-hard problem, we propose the minimize the job completion cost before a given deadline (MCGL) method, which calculates a task placement solution by the gradient adjustment strategy according to the remarkable negative correlation relationship between job completion time and job completion cost of geo-distributed IoT data analytics job. The task placement strategy can optimize resource cost with respect to the deadline requirement of any geo-distributed data analytics job. The trace-driven evaluations indicate that MCGL significantly reduces the total cost compared with existing methods; moreover, they satisfy the deadline constraints simultaneously.

Mobile-edge computing (MEC) is booming in recent years, as it is expected to fulfill the growing low-latency requirements of offloaded applications on large amounts of end devices. To ensure more applications finish before their deadlines, it is crucial to optimize the assignment of applications among various edge servers and the scheduling in a specific server, both of which have attracted widespread attention. As applications tend to become more complicated, each application may contain multiple interdependent tasks. We find that dependency in applications is another essential factor that would greatly impact the application’s time consumption. Unfortunately, no prior study has given a comprehensive consideration involving all three factors, leading to a severe waste of computing and network resources, thus delays application processing. In this article, we model the dependencies among all tasks of an application as a directed acyclic graph (DAG) and jointly optimize the application assigning and scheduling problems to facilitate the execution of each application. To solve this NP-hard problem, we design a novel method namedDaas. It first estimates the priority of each task and then effectively tackles the application assigning and scheduling problem based on this attribute in an online manner. Extensive evaluations show thatDaasperforms well in various experimental settings, enabling 20% more applications to meet their deadlines compared with the other baselines.

Video streaming service is one of the most important IoT applications/services at the mobile end. To provide better services and earn more customers, the mobile video service providers have paid considerable attention to enhance end users’ Quality of Experience (QoE) in video streaming. As an important aspect of the mobile device, however, the battery power and its impacts on the mobile services were seldom concerned. According to our survey over 2000+ mobile users, the low battery power of mobile phones could cause the user to give up watching videos. To quantify the relationship between the battery power and user’s video abandoning probability (VAP), we first extract the VAP model from the collected survey data, leveraging a reversed accumulative histogram approach. Then, referring to the quantified VAP model, we presentEdgeSaver, an edge-assisted video transmission framework, which aims at maintaining a sustainable overall user retention rate for the service providers by reducing the power consumption of video playback at the mobile ends. Particularly, as the core component ofEdgeSaver, a low-power video scheduler is designed to strategically select user groups, such that the most profitable outcome can be achieved under the constraints of limited edge resources. With extensive experiments using a real-world data set, we demonstrate thatEdgeSavercan help the mobile video service provider improve the user retention rate by up to 30% and increase the average user viewing time by 20%.

The user demands to delay-sensitive applications have put forward new requirements for the mobile networks. Edge caching as a promising way is proposed to enhance the Quality of Service (QoS) for end users at the network edge. Given the widely distributed edge nodes, the content providers (CPs) usually prefer to integrate them with cooperative caching services, by forming a cache coalition. Although such a coalition could be beneficial as a whole, it neglects the profits of individual members, which is one major concern in forming the coalition itself. Besides, due to the poor scalability, the conventional cooperation scheme, which only considers fixed edge nodes, cannot adapt to the spatial and temporal imbalance of user requests. In this article, we tackle the problems of coalition establishment and profit allocation among the coalition members. Particularly, by adopting both fixed edge nodes and mobile vehicles as caching nodes, we propose a hybrid service provisioning framework and cooperative service caching and workload scheduling methods. To maximize the profits in managing the caching resources in the established coalition, we devise an optimization model with a mixed-integer programming (MIP), in which the QoS requirements of end users and caching capacities of each coalition member are also considered as constraints. In addition, based on the Hedonic game theory, we propose a dynamic coalition algorithm to guide each member to join or leave the coalition at each time slot out of its own profits. The experimental results demonstrate that compared to the cases only considering fixed caching nodes, our hybrid caching scheme can improve: 1) the overall profit of the coalition by 53% and 2) the average profit of individual participants by 42%, respectively.

Vehicular cloud computing (VCC) has been widely utilized to enhance traffic management and road safety both in the static and dynamic scenarios. In VCC, the onboard resources of involved smart vehicles (SVs) would be integrated as a resource pool and collaboratively accommodate various computation tasks. In this system, SVs in a section of the road can be grouped as a vehicular cloud to complete the detection job, e.g., collecting and preprocessing the road data. Then, an SV will be selected to aggregate all SVs’ detection results in the road section and upload the results to the remote monitoring platform via base stations (BSs). However, due to the high dynamics of vehicular mobility and the poor coverage of BSs in some areas, this vision is challenging to achieve. In this article, we propose a collaborative road detection system and schedule the detection task to different SVs in the road section. Specifically, 1) we model the collaborative detection process and formulate it as a task scheduling problem to minimize the response time, which is NP-hard. An adaptive location-aware scheduling scheme is proposed for task scheduling and 2) as there are road sections without coverage of any BS, therefore we have to utilize the SVs on the opposite lane to transmit the aggregation result in these road sections. Accordingly, an uploading strategy is proposed to decide to upload the feedback through SVs on the opposite lane or in the coverage area of the next BS. Extensive experiments show that our scheme can significantly reduce the response time overall and is close to the optimal solution.

In the era of cloud computing, network services are deployed on geographically distributed cloud platforms, which results in a large amount of inter-datacenter traffic. Multi-tier pricing schemes are widely adopted by cloud service providers (CSPs) to charge cloud users for inter-datacenter transmission services. To avoid a severe penalty associated with missing a deadline, cloud users are prone to selecting a sufficiently high service level. However, they are usually unaware of the total traffic volume before accessing the network; hence, a high transmission cost is introduced. In this paper, we propose an online cost-efficient transmission scheme for cloud users with information-agnostic traffic. The basic idea is to split a long-term transmission request into a series of short-term ones. In this scheme, we take into account the CSP’s countermeasures, and model the interactions between the cloud users and the CSP as a Stackelberg game. We show that the optimal number of short-term requests and the associated transmission service levels can be determined with an online algorithm based on Lyapunov optimization. The experimental results reveal that the CSP and the cloud users can achieve a win-win outcome, whereby the transmission cost of cloud users can be reduced by 59 percent.

As the development of new generation mobile communication technology, the mobile core network also needs to be upgraded by new network technologies, e.g., software defined networking (SDN) and network function virtualization (NFV). With NFV, virtual network functions (VNFs) can be deployed on commodity devices to support various network function requirements and attain system's flexibility and elasticity in network edge. Meanwhile, a set of selected VNFs are usually chained as a service function chain (SFC) to serve a given flow in a specified order. Since the devices have heterogeneous execution environments and the VNFs have various requirements, one fundamental challenge is how to embed SFC for each flow on the shared NFV infrastructure (NFVI) with the goal of minimizing the flow completion time. Furthermore, multiple flows always compete for resources of those devices hosting SFCs. In this general setting, there is an urgent need to study efficient scheduling mechanism to minimize the total completion time of all flows. In this paper, by jointly considering VNF placement and flow scheduling, we first formulate this problem as an integer programming problem, and further prove that it is NP-hard in general case. We then design a PDG method to find the optimal solution in single flow case and an LRD method to achieve a high-quality feasible solution in multiple flows case. The extensive experiment results indicate that our LRD method can reduce the total completion time of all flows by 22.04, 60.99 and 39.95, percent against three compared methods, respectively.

Unsupervised Domain Adaptation (UDA) aims at learning a classifier for an unlabeled target domain by transferring knowledge from a labeled source domain with a related but different distribution. The strategy of aligning the two domains in latent feature space via metric discrepancy or adversarial learning has achieved considerable progress. However, these existing approaches mainly focus on adapting the entire image and ignore the bottleneck that occurs when forced adaptation of uninformative domain-specific variations undermines the effectiveness of learned features. To address this problem, we propose a novel component called Informative Feature Disentanglement (IFD), which is equipped with the adversarial network or the metric discrepancy model, respectively. Accordingly, the new network architectures, named IFDAN and IFDMN, enable informative feature refinement before the adaptation. The proposed IFD is designed to disentangle informative features from the uninformative domain-specific variations, which are produced by a Variational Autoencoder (VAE) with lateral connections from the encoder to the decoder. We cooperatively apply the IFD to conduct supervised disentanglement for the source domain and unsupervised disentanglement for the target domain. In this way, informative features are disentangled from the domain-specific details before the adaptation. Extensive experimental results on three gold-standard domain adaptation datasets, e.g., Office31, Office-Home and VisDA-C, demonstrate the effectiveness of the proposed IFDAN and IFDMN models for UDA.

Many organizations nowadays have multiple sites at different geographic locations. Typically, transmitting massive data among these sites relies on the interconnection service offered by ISPs. Segment Routing over IPv6 (SRv6) is a new simple and flexible source routing solution which could be leveraged to enhance interconnection services. Compared to traditional technologies, e.g., physical leased lines and MPLS-VPN, SRv6 can easily enable quick-launched interconnection services and significantly benefit from traffic engineering with SRv6-TE. To parse the SRv6 packet headers, however, hardware support and upgrade are needed for the conventional routers of ISP. In this paper, we study the problem of SRv6 incremental deployment to provide a more balanced interconnection service from a traffic engineering view. We formally formulate the problem as an SRID problem with integer programming. After transforming the SRID problem into a graph model, we propose two greedy methods considering short-term and long-term impacts with reinforcement learning, namely GSI and GLI. The experiment results using a public dataset demonstrate that both GSI and GLI can significantly reduce the maximum link utilization, where GLI achieves a saving of 59.1% against the default method.

Edge computing promises a dramatic reduction in the network latency and the traffic volume, where many edge servers are placed at the edge of the Internet. Furthermore, those edge servers cache data to provide services for edge users. The data sharing among those edge servers can effectively shorten the latency to retrieve the data and further reduce the network bandwidth consumption. The key challenge is to construct an efficient data indexing mechanism no matter how the data is cached in the edge network. Although this is essential, it is still an open problem. Moreover, existing methods such as the centralized indexing and the DHT indexing in other fields fail to meet the performance demand of edge computing. This paper presents a COordinate-based INdexing (COIN) mechanism for the data sharing in edge computing. COIN maintains a virtual space where switches and data indexes are associated with their coordinates. Then, COIN distributes data indexes to indexing edge servers based on those coordinates. The COIN is effective because any query request from an edge server can be responded when the data has been stored in the edge network. More importantly, COIN is efficient in both routing path lengths and forwarding table sizes for publishing/querying data indexes. We implement COIN in a P4 prototype. Experimental results show that COIN uses 59% shorter path length and 30% less forwarding table entries to retrieve data indexes compared to using Chord, a well-known DHT solution.

Edge computing responds to users’ requests with low latency by storing the relevant files at the network edge. Various data deduplication technologies are currently employed at edge to eliminate redundant data chunks for space saving. However, the lookup for the global huge-volume fingerprint indexes imposed by detecting redundancies can significantly degrade the data processing performance. Besides, we envision a novel file storage strategy that realizes the following rationales simultaneously: 1) space efficiency, 2) access efficiency, and 3) load balance, while the existing methods fail to achieve them at one shot. To this end, we report LOFS, a Lightweight Online File Storage strategy, which aims at eliminating redundancies through maximizing the probability of successful data deduplication, while realizing the three design rationales simultaneously. LOFS leverages a lightweight three-layer hash mapping scheme to solve this problem with constant-time complexity. To be specific, LOFS employs the Bloom filter to generate a sketch for each file, and thereafter feeds the sketches to the Locality Sensitivity hash (LSH) such that similar files are likely to be projected nearby in LSH tablespace. At last, LOFS assigns the files to real-world edge servers with the joint consideration of the LSH load distribution and the edge server capacity. Trace-driven experiments show that LOFS closely tracks the global deduplication ratio and generates a relatively low load std compared with the comparison methods.

Many hardware-based security middleboxes have been deployed in the networks to defend against different threats. However, these hardware middleboxes are hard to upgrade or migrate. The emergence of network functions virtualization (NFV), which realizes various security functions in the form of virtual network functions (VNFs), brings many benefits to network security. To improve the security level further, several VNFs are coordinated in a pre-defined order to form service function chains (SFCs). It is expected that the SFCs are embedded properly with low cost, including the VNF setup cost and the flow routing cost. In this paper, we find that when an SFC is required by multiple flows for the identical network security threats, the total cost could be reduced by embedding an aggregated service function tree (ASFT) instead of multiple independent SFCs. We formally characterize the integer programming model of this problem and prove that it is NP-hard. Then we propose a performance-guaranteed approximation algorithm and prove that the algorithm could find the optimal solution in a special case. Extensive experiments indicate that our method can reduce the total cost by$22.0\%$and$24.1\%$against two compared algorithms, respectively.

We consider cyber security as one of the most significant technical challenges in current times. One of the main tasks is to detect anomalous patterns in the network streams as soon as they appear. In order to solve the above problem, previous propositions use statistical or machine learning-based methods to detect anomalous patterns in the network streams. However, these solutions incur significant low efficiency and precision due to the frequent recomputation of the results from scratch and unreasonable assumptions. In graph theory, dense subgraphs can be used to model the anomalous patterns if we abstract the network streams as a dynamic graph. This motivates us to explore dense subgraph discovery under the scenario where the network is updating. In this paper, we propose a graph-based framework, referred to as SAD, towards continuous dense subgraph discovery over network streams. In specific, we design an auxiliary data structure that is a concise representation of intermediate results, and its execution model allows a fast incremental maintenance strategy. In this way, we can detect anomalous patterns in the network streams in near real-time. Experiments demonstrate that SAD can not only get a higher accuracy of 90.2% but also faster than $11.4\times$ times compared to the state-of-the-art anomaly detection algorithms.

Cuckoo filter (CF) and its variants are emerging as replacements of Bloom filters in various networking and distributed systems to support efficient set representation and membership testing. Cuckoo filters store item fingerprints directly with two candidate buckets and a reallocation scheme is implemented to mitigate the bucket overflow problem for higher space utilization. Such a reallocation scheme, once triggered, however, can be time-consuming. This shortcoming makes the existing CFs not applicable for insertion-intensive scenarios such as online applications wherein the items join and leave frequently. To this end, in this paper, we propose the Vertical Cuckoo filter (VCF) which extends the standard Cuckoo filter by providing more candidate buckets to each item. Another challenging issue with such a design is how to ensure that the candidate buckets can be indexed by each other such that no additional hash computation and item access are necessary during fingerprint reallocation. Therefore, we present the vertical hashing, which indexes the candidate buckets with the fingerprint and given bitmasks. We further generalize and improve the VCF by realizing$k$(≥ 4) candidate buckets and avoiding unnecessary computation. The comprehensive experiments indicate that VCF outperforms its same kinds in terms of space utilization and insertion throughput, with a slight compromise of lookup speed.

Existing Internet routing protocols much focus on providing interconnection service for independent autonomous systems (ASes) rather than end-to-end low latency transmission. Nowadays, a growing number of applications and platforms have high requirements for low latency. However, developing new routing protocols in the wide area network that provides low latency routing service is very challenging, and remains an open problem due to the obstacles of compatibility, feasibility, scalability and efficiency. On the other hand, the ignorance of latency performance results in triangle inequality violations (TIV). In this paper, we leverage TIV and a new routing technology, SRv6, to build a new distributed routing protocol, SRv6 underlay federation (SRUF), which aims to provide low-latency routing services in network core. We design a novel method to find alternative paths with lower latency between any pair of ASes in SRUF. This method can achieve high scalability as it incurs only$O(n)$bandwidth overhead in each member of SRUF. SRv6 is then employed to steer the flows along the selected indirect low-latency paths, while keeping compatibility to legacy routing systems. The experimental results with realworld datasets demonstrate that SRUF can effectively reduce the average end-to-end delay by 5.4% ~ 58.9%.

Cuckoo filter (CF), Bloom filter (BF) and their variants are space-efficient probabilistic data structures for approximate set membership queries. However, their data synopsis would inevitably become unusable when there are a number of member updates on the set; while updates are not uncommon for the real-world data streaming applications such as duplicate item detection, malicious URL checking, and caching applications. It has been shown that some variants of BF can be adaptive to stream applications. However, current extensions of BF structures generally incur unstable performance or intolerant membership testing errors. In this paper, we aim to design a data synopsis for membership testing on data streams with stable performance and tolerant query errors. To this end, we propose Stable Cuckoo Filters (SCF), which take a fine-grained manner to evict the stale elements and store those more recent ones. SCF absorbs the design philosophy from several unsuccessful designs. Specifically, SCFs take elegant update operations to embed time information with insertion operation and carefully evict the stale elements. We show that a tight upper bound of the expected false positive rate (FPR) remains asymptotically constant over the insertion of new members. The query error for recent elements of SCF (FNR) is related to the characteristics of the input data stream and query workloads. Extensive experiments on the real-world and synthetic datasets show that our designs are more stable than the existing variants of BF and realize 7 x smaller false errors and up to 3 x throughput.

The advanced persistent threat (APT) is a stealthy cyber attack perpetrated by a group that gains unauthorized access to a computer network and remains undiscovered to steal specific data and resources. Fast detection and defense of APT attacks are critical tasks in cyber security. Previous works use simple feature extraction and classification methods to distinguish APT information flow from the normal one. However, APT attacks are latent, with very little flow and mixed in many normal information flows. Moreover, APT attacks can adjust their behavior according to the environment, making it challenging to be discovered and extract features. Meanwhile, dynamic information flow tracking (DIFT) is a tool for tracking information flow, which can also adjust the marking strategy according to the environment and is often used to track and detect APT information flow. On the other hand, game theory is a mathematical model that expresses the game of two or more parties. Therefore, this motivates us to model a game theory to solve the above challenge. In this paper, to solve the above obstacles, we propose an intelligent game theory framework named DPS, which models the strategic interaction between APTs and DIFT and aims to get a high reward for DIFT. Our proposed DPS framework utilizes deep reinforcement learning to find the Nash equilibrium. The game model is a nonzero-sum, average reward stochastic game. Specifically, we design a subgraph pruning strategy and deep Q-network to guide the player in exploring new strategies in the information flow graph. Finally, we implement our framework to compute an optimal defender strategy to defend cyber security. Based on 2 real-world datasets, the experiment results demonstrate that the DPS framework can delay APT intrusions under equilibrium in 3 epochs and get a better reward than the Uniform policy.

The mobile network operators are upgrading their network facilities and shifting to the 5G era at an unprecedented pace. The huge operating expense (OPEX), mainly the energy consumption cost, has become the major concern of the operators. In this work, we investigate the energy cost-saving potential by transforming the backup batteries of base stations (BSs) to a distributed battery energy storage system (BESS). Specifically, to minimize the total energy cost, we model the distributed BESS discharge/charge scheduling as an optimization problem by incorporating comprehensive practical considerations. Then, considering the dynamic BS power demands in practice, we propose a deep reinforcement learning (DRL) based approach to make BESS scheduling decisions in real-time. The experiments using real-world BS deployment and traffic load data demonstrate that with our DRL-based BESS scheduling, the peak power demand charge of BSs can be reduced by up to 26.59%, and the yearly OPEX saving for 2,282 5G BSs could reach up to US$185,000.

Mobile Edge Computing (MEC) is a promising cloud-network convergence paradigm which provides computational resources close to end devices at the network edge. There exist multiple Edge Infrastructure Providers (EIPs) in MEC which independently manage edges and provide services to customers. Due to the exponentially increasing data generated by end devices, it is almost impossible for a single EIP to accommodate offloaded data. Moreover, when considering that multiple EIPs provide services through federation, an urgent challenge is how to ensure the sustainability of federation. Most of the existing work improves the service provision capabilities of MEC by optimizing service placement without considering the existence of multiple EIPs. In this paper, we design the horizontal collaboration of edge federation, which integrates all edges of all EIPs. First, we model the service placement problem as a programming problem, towards the goal of maximizing social welfare. Then, we propose two dynamic pricing methods for EIPs to determine typical price for customers and insourcing price for other EIPs. The evaluation results based on two real-world data sets demonstrate that our proposed service placement model can increase the total gain of EIPs by up to 24.5% with a decrease of 35.5% in total delay.

To enable fast content delivery for delay-sensitive applications, large content providers build edge servers, Points of Presence (PoPs), and datacenters around the world. They are networked together as an integrated infrastructure via a private wide-area network (WAN), named content delivery network (CDN). To deliver quality services in the CDN, there are two critical decisions that should be properly made: 1) making assignments of PoP and datacenter for user requests, and 2) selecting routing paths from PoP to datacenter. However, with both the network variability and CDN environment complexity, it is challenging to achieve satisfying decisions. In this paper, we propose DeepDelivery, an adaptive deep reinforcement learning approach to intelligently make assignments and routing decisions in real time. Essentially, DeepDelivery adopts the Markov decision process (MDP) model to capture the dynamics of network variation, and the objective is to jointly maximize the infrastructure utilization of providers and minimize the total latency of end users. We conduct extensive trace-driven evaluations spanning various environment dynamics with both real-world and synthetic trace data. The result demonstrates that DeepDelivery can outperform the state-of-the-art scheme by 21.89% higher utilization and 11.27% lower end-to-end latency on average.

In this article, we investigate the worker (i.e., vehicle) selection problem in vehicle-based crowdsourcing (VBC), where vehicles in a specific area are recruited by the crowdsourcing platform to collect geographical information in real driving scenarios for autonomous driving. Given a limited recruitment budget, we formulate a cumulative platform utility maximization problem (CMP) to obtain the optimal worker set. The CMP is unsolvable directly as the platform has no prior information of workers at the initial stage (also known as “cold start”) and the cost of collecting all workers' information is prohibitive. To solve the problem, we first conduct a comprehensive data analytics on two real-world vehicle traces and obtain two crucial observations: 1) trajectory of individual vehicle is highly uncertain that it is difficult to make accurate prediction and 2) the overall distribution of vehicular trajectory penetration (measured by collection quantity and coverage) has a diurnal pattern and varies with weekly periodicity. Inspired by the insights, we propose the performance transfer-based online worker selection (POSE) scheme, which works independently from trajectory prediction with two components, i.e., transfer learning-based performance estimation and online worker selection (OWS). Based on the diurnal pattern, the former component collects a short-period trajectory penetration data of vehicles for model fitting, which can output a specific numerical distribution. With the fitting model, we can identify and select vehicles with high trajectory penetration at the initial stage to cope with the “cold start” problem. Then, we map the worker selection problem into a multiarmed bandit problem and develop upper confidence bound-based approach to solve it. Extensive trace-driven simulations are carried out and the results demonstrate the efficiency of POSE in terms of cumulative platform utility.

Blockchain-powered edge computing (BEC) is a promising extension to strengthen the security and the trustworthiness among collaborative edge clouds for delivering computation-intensive and delay-sensitive services in the environments of IoT and 5G. A fundamental challenge is how to respond to the maximum number of IoT requests at the network edge instead of the remote cloud. Although some work has been done to consider service provisioning and request scheduling in collaborative edge clouds, they assume that a single service is used to respond to each request. This assumption, however, is not practical to meet the demand of emerging IoT applications. In reality, the request needs to call a set of services with a chain-based structure. To tackle this challenge, in this article, we first propose a chain-based service request model for emerging IoT applications and further study the joint service provisioning and request scheduling problem for chain-based service requests at the network edge. We characterize this problem as an integer linear programming (ILP) model and prove the NP-hardness of this joint optimization problem. Furthermore, we prove that the related problem is of approximate submodularity with an approximation ratio guarantee. Finally, a novel two-stage optimization (TSO) scheme is proposed, and the results of extensive experiments show the efficiency and the effectiveness of the TSO scheme.

Designing efficient and secure mutual authentication and key agreement (MAAKA) protocols for Internet of Medical Things (IoMT) has been shown to be challenging, mainly due to the different security and privacy requirements in complex settings. Existing schemes generally are subject to a number of limitations, ranging from performance to security issues. In this article, we introduce a provably secure and lightweight MAAKA (PSL-MAAKA) protocol for fully public channels in IoMT. First, the proposed scheme is lightweight since the major operations in the stage of authentication and key agreement are hash operation and XOR operation, respectively. Second, this article proves the security of the presented protocol taking the advantage of the random oracle model. Next, this article gives that security requirements in IoMT could be satisfied through our presented MAAKA protocol. Finally, we demonstrate that it enjoys optimal performance than other competing schemes, in terms of communication overhead, computation overhead, and storage overhead.

Synthesizing a fake trajectory with consistent lifestyle and meaningful mobility as the actual one is the most popular way to protect the location privacy in trajectory sharing. Recent location privacy preservation shows a strong personalized requirement from the mobile semantics between users and locations. However, the existing techniques cannot fully satisfy such personalized requirements, resulting in either overprotection or underprotection. It remains open to characterize and quantify the personalized requirement for location privacy preservation. In this article, we propose a mobile semantic-aware privacy model, named MSP. Specifically, we first characterize a new kind of user-related mobile semantic on-location set by constructing a hierarchical semantic tree, according to the user’s roles at locations. Then, a dedicated approach is proposed to evaluate the location’s privacy sensitivity and integrate it into the user-related mobile semantic. Finally, an adaptive privacy-preserving mechanism, MSP, is developed, fully considering the personalized requirement from both the user and the location. With this model in place, mobile semantic-aware synthetic trajectories are constructed adaptively. Extensive experiments with a real-world data set demonstrate that our MSP model can achieve an effective and flexible balance between the personalized privacy preservation and the data availability of synthetic trajectories.

The emergence of edge computing can effectively tackle the problem of large transmission delays caused by the long-distance between user devices and remote cloud servers. Users can offload tasks to the nearby edge servers to perform computations, so as to minimize the average task response time through effective task dispatching and scheduling methods. However: 1) in the task dispatching phase, the dynamic features of network conditions and server loads make it difficult for the offloaded tasks to select the optimal edge server and 2) in the task scheduling phase, each edge server may face a large number of offloading tasks to schedule, resulting in long average task response time, or even severe task starvation. In this article, we propose an online task dispatching and fair scheduling method OTDS to tackle the above two challenges, which combines online learning (OL) and deep reinforcement learning (DRL) techniques. Specifically, using an OL approach, OTDS performs real-time estimating of network conditions and server loads, and then dynamically assigns tasks to the optimal edge servers accordingly. Meanwhile, at each edge server, by combing the round-robin mechanism with DRL, OTDS is able to allocate appropriate resources to each task according to its time sensitivity and achieve high efficiency and fairness in task scheduling. Evaluation results show that our online method can dynamically allocate network resources and computing resources to those offloaded tasks according to their time-sensitive requirements. Thus, OTDS outperforms the existing methods in terms of the efficiency and fairness on task dispatching and scheduling by significantly reducing the average task response time.

The proliferation of various mobile devices equipped with cameras results in an exponential growth of the amount of images. Recent advances in the deep learning with convolutional neural networks (CNN) have made CNN feature extraction become an effective way to process these images. However, it is still a challenging task to deploy the CNN model on the mobile sensors, which are typically resource-constrained in terms of the storage space, the computing capacity, and the battery life. Although cloud computing has become a popular solution, data security and response latency are always the key issues. Therefore, in this paper, we propose a novel lightweight framework for privacy-preserving CNN feature extraction for mobile sensing based on edge computing. To get the most out of the benefits of CNN with limited physical resources on the mobile sensors, we design a series of secure interaction protocols and utilize two edge servers to collaboratively perform the CNN feature extraction. The proposed scheme allows us to significantly reduce the latency and the overhead of the end devices while preserving privacy. Through theoretical analysis and empirical experiments, we demonstrate the security, effectiveness, and efficiency of our scheme.

Due to the rapid development of indoor location-based services, automatically deriving an indoor semantic floorplan becomes a highly promising technique for ubiquitous applications. To make an indoor semantic floorplan fully practical, it is essential to handle the dynamics of semantic information. Despite several methods proposed for automatic construction and semantic labeling of indoor floorplans, this problem has not been well studied and remains open. In this article, we present a system called SiFi to provide accurate and automatic self-updating service. It updates semantics with instant videos acquired by mobile devices in indoor scenes. First, a crowdsourced-based task model is designed to attract users to contribute semantic-rich videos. Second, we use the maximum likelihood estimation method to solve the text inferring problem as the sequential relationship of texts provides additional geometrical constraints. Finally, we formulate the semantic update as an inference problem to accurately label semantics at correct locations on the indoor floorplans. Extensive experiments have been conducted across 9 weeks in a shopping mall with more than 250 stores. Experimental results show that SiFi achieves 84.5% accuracy of semantic update.

Unsupervised Domain Adaptation (UDA) aims to learn a classifier for the unlabeled target domain by leveraging knowledge from a labeled source domain with a different but related distribution. Many existing approaches typically learn a domain-invariant representation space by directly matching the marginal distributions of the two domains. However, they ignore exploring the underlying discriminative features of the target data and align the cross-domain discriminative features, which may lead to suboptimal performance. To tackle these two issues simultaneously, this paper presents a Joint Clustering and Discriminative Feature Alignment (JCDFA) approach for UDA, which is capable of naturally unifying the mining of discriminative features and the alignment of class-discriminative features into one single framework. Specifically, in order to mine the intrinsic discriminative information of the unlabeled target data, JCDFA jointly learns a shared encoding representation for two tasks: supervised classification of labeled source data, and discriminative clustering of unlabeled target data, where the classification of the source domain can guide the clustering learning of the target domain to locate the object category. We then conduct the cross-domain discriminative feature alignment by separately optimizing two new metrics: 1) an extended supervised contrastive learning, i.e., semi-supervised contrastive learning 2) an extended Maximum Mean Discrepancy (MMD), i.e., conditional MMD, explicitly minimizing the intra-class dispersion and maximizing the inter-class compactness. When these two procedures, i.e., discriminative features mining and alignment are integrated into one framework, they tend to benefit from each other to enhance the final performance from a cooperative learning perspective. Experiments are conducted on four real-world benchmarks (e.g., Office-31, ImageCLEF-DA, Office-Home and VisDA-C). All the results demonstrate that our JCDFA can obtain remarkable margins over state-of-the-art domain adaptation methods. Comprehensive ablation studies also verify the importance of each key component of our proposed algorithm and the effectiveness of combining two learning strategies into a framework.

City-wide package delivery becomes popular due to the dramatic rise of online shopping. In order to speed up the package delivery process without increasing the delivery cost, a promising system has been proposed, which leverages the crowdsourced taxis. Many efforts have been done on this novel system in recent literature. However, a fundamental problem still remains open, i.e., measuring the maximum capacity of taxi-based logistics at the urban scale. In this paper, we first propose an accurate and efficient measurement mechanism to tackle this problem in the Non-stop package delivery method. The basic idea is to construct a spatial-temporal graph according to the passenger demands and calculate the maximum urban capacity by combining the results of several carefully designed max-flow problems. Then, we expand our measurement mechanism to be used in other taxi-based package delivery methods after a few adaptations, including the One-hop method and the Stop-and-wait method. At last, we evaluate our measurement mechanism and compare the maximum urban capacity of various package delivery methods with a real-world dataset from an online taxi-taking platform.

Simultaneous clustering and optimization (SCO) has recently drawn much attention due to its wide range of practical applications. Many methods have been previously proposed to solve this problem and obtain the optimal model. However, when a dataset evolves over time, those existing methods have to update the model frequently to guarantee accuracy; such updating is computationally infeasible. In this paper, we propose a new formulation of SCO to handle evolving datasets. Specifically, we propose a new variant of the alternating direction method of multipliers (ADMM) to solve this problem efficiently. The guarantee of model accuracy is analyzed theoretically for two specific tasks: ridge regression and convex clustering. Extensive empirical studies confirm the effectiveness of our method.

The emergence of large-scale dynamic sets in networked and distributed applications attaches stringent requirements to approximate set representation. The existing data structures (including Bloom filter, Cuckoo filter, and their variants) preserve a tight dependency between the cells or buckets for an element and the lengths of the filters. This dependency, however, degrades the capacity elasticity, space efficiency and design flexibility of these data structures when representing dynamic sets. In this paper, we first propose the Index-Independent Cuckoo filter (I2CF), a probabilistic data structure that decouples the dependency between the length of the filter and the indices of buckets which store the information of elements. At its core, an I2CF maintains a consistent hash ring to assign buckets to the elements and generalizes the Cuckoo filter by providing optional${k}$candidate buckets to each element. By adding and removing buckets adaptively, I2CF supports the bucket-level capacity alteration for dynamic set representation. Moreover, in case of a sudden increase or decrease of set cardinality, we further organize multiple I2CFs as a Consistent Cuckoo filter (CCF) to provide the filter-level capacity elasticity. By adding untapped I2CFs or merging under-utilized I2CFs, CCF is capable of resizing its capacity instantly. The trace-driven experiments indicate that CCF outperforms its alternatives and realizes our design rationales for dynamic set representation simultaneously, at the cost of a little higher complexity.

The hierarchical mobile edge computing satisfies the stringent latency requirements of data access and processing for emerging edge applications. The data location service is a basic function to provide data storage and retrieval to enable these applications. However, it still lacks research of a scalable and low-latency data location service in the environment. The existing solutions, such as DNS and DHT, fail to meet the requirement of those latency-sensitive applications. Therefore, in this article, we present a low-latency hybrid data-sharing framework, HDS. The HDS divides the data location service into two parts: intra-region and inter-region. More precisely, we design a data sharing protocol called Cuckoo Summary to achieve fast data localization in intra-region. Furthermore, for the inter-region data sharing, we develop a geographic routing based scheme to achieve efficient data localization with only one overlay hop. The advantages of HDS include short response latency, low implementation overhead, and few false positives. We implement the HDS framework based on a P4 prototype. The experimental results show that, compared to the state-of-the-art solutions, our design achieves 50.21% shorter lookup paths and 92.75% fewer false positives.

Edge computing (EC) is a promising paradigm for providing ultra-low latency experience for IoT applications at the network edge, through pre-caching required services in fixed edge nodes. However, the supply-demand mismatch can arise while meeting the peak period of some specific service requests. The mismatch between capacity provision and user demands can be fatal to the delay-sensitive user requests of emerging IoT applications and will be further exacerbated due to the long service provisioning cycle. To tackle this problem, we propose the mobile-assisted edge computing framework to improve the QoS of fixed edge nodes by exploiting mobile edge nodes. Furthermore, we devise a CRI (Credible, Reciprocal, and Incentive) auction mechanism to stimulate mobile edge nodes to participate in the services for user requests. The advantages of our mobile-assisted edge computing framework include higher task completion rate, profit maximization, and computational efficiency. Meanwhile, the theoretical analysis and experimental results guarantee the desirable economic properties of our CRI auction mechanism.

Multi-party set reconciliation is a key component in distributed and networking systems. It naturally contains two dimensions, i.e., set representation and reconciliation protocol. However, existing sketch data structures are insufficient to satisfy the new needs brought by the multi-party scenario simultaneously, including space-efficiency, mergeability, and completeness. The current reconciliation protocols, on the other hand, fail to achieve the global optimization of communication cost. To this end, in this article, we propose the marked cuckoo filter (MCF), a data structure for representing set members. Grounded on MCF, we implement the MCFsyn protocol to reconcile multiple sets. MCFsyn aggregates and distributes sets information represented by MCFs along with an underlying minimum spanning tree among the participants. The participants then identify the different elements by traversing the overall MCF which contains the information of all elements in the union set. For the identified missing elements, MCFsyn helps the participants to choose the optimal senders to fetch with the minimum communication cost. Comprehensive evaluations indicate that MCFsyn significantly outperforms existing alternatives in terms of both reconciliation accuracy and communication cost.

A large number of servers are interconnected using a specific datacenter network to deliver the infrastructure as a service (IaaS). Multicast can jointly utilize the network resources and further reduce the consumption of network bandwidth more than individual unicast. The source of a multicast service, however, does not need to be in a specific location as long as certain constraints are satisfied. This means the multicast can have uncertain sources, which could reduce the network resource consumption more than a traditional multicast service and further improve the quality of service. In this paper, we propose a novel reliable multicast service with uncertain sources named ReMUS. The goal is to minimize the sum of the transfer cost and the recovery cost, although finding such a ReMUS is very challenging. Thus, we design a source-based multicast method to solve this problem by exploiting the flexibility of sources when no recovery nodes exist in the network. Furthermore, we design a general multicast method to jointly exploit the benefits of uncertain sources and recovery nodes to minimize the total cost of ReMUS. We conduct extensive evaluations under Internet2 and datacenter networks. The results indicate that our methods can efficiently realize the reliable and scalable multicast with uncertain sources, irrespective of the settings of networks and multicasts. To the best of our knowledge, we are the first to study the reliable multicast service under uncertain sources.

Abstract Nowadays, the scale of various graphs soars rapidly, which imposes a serious challenge to develop processing and analytic algorithms. Among them, graph pattern matching is the one of the most primitive tasks that find a wide spectrum of applications, the performance of which is yet often affected by the size and dynamicity of graphs. In order to handle large dynamic graphs, incremental pattern matching is proposed to avoid re-computing matches of patterns over the entire data graph, hence reducing the matching time and improving the overall execution performance. Due to the complexity of the problem, little work has been reported so far to solve the problem, and most of them only solve the graph pattern matching problem under the scenario of the data graph varying alone. In this article, we are devoted to a more complicated but very practical graph pattern matching problem, continuous matching of evolving patterns over dynamic graph data, and the investigation presents a novel algorithm for continuously pattern matching along with changes of both pattern graph and data graph. Specifically, we propose a concise representation of partial matching solutions, which can help to avoid re-computing matches of the pattern and speed up subsequent matching process. In order to enable the updates of data graph and pattern graph, we propose an incremental maintenance strategy, to efficiently maintain the intermediate results. Moreover, we conceive an effective model for estimating step-wise cost of pattern evaluation to drive the matching process. Extensive experiments verify the superiority of .

\emphSeasonal periodicity is a frequent phenomenon for social interactions in temporal networks. A key property of this behavior is that it exhibits periodicity for multiple particular periods in temporal networks. Mining such seasonal-periodic patterns is significant since it can indicate interesting relationships between the individuals involved in the interactions. Unfortunately, most previous studies for periodic pattern mining ignore the seasonal feature. This motivates us to explore mining seasonal-periodic subgraphs, and the investigation presents a novel model, called maximal σ-periodic $ømega$-seasonal k-subgraph. It represents a subgraph with size larger than k and that appears at least σ times periodically in at least $ømega$ particular periods on the temporal graph. Since seasonal-periodic patterns do not satisfy the anti-monotonic property, we propose a weak version of support measure with an anti-monotonic property to reduce the search space efficiently. Then, we present an effective mining algorithm to seek all maximal σ-periodic $ømega$-seasonal k-subgraphs. Experimental results on real-life datasets show the effectiveness and efficiency of our approach.

The pervasive low-battery anxiety (LBA) among modern mobile users has caused negative impacts on users' emotion and health, and such anxiety may directly lead to loss of customers in power-hungry applications, e.g., video streaming. Despite its importance, LBA has not been thoroughly investigated due to the difficulty in quantitatively measuring LBA. To fill the gap, we present a quantitative model to measure the LBA among mobile users and design a tailored mechanism to alleviate it via display energy saving in video streaming. In specific, we first conduct a large-scale user survey among 2000+ mobile users and strategically extract an empirical LBA model that captures the variation of user's anxiety degree along with the battery power draining. Then, by exploiting the emerging edge computing paradigm, we propose LPVS, a novel solution for low-power video streaming service at the network edge. It aims to minimize the LBA of mobile users, by integrating the extracted LBA model with the energy-saving image/video content transforming techniques. The emulation results using real-world video watching traces demonstrate that, LPVS can effectively alleviate mobile users' LBA and prolong the low-battery users' video watching time (i.e., customer retention) by 39%.

Edge computing has become the de facto method for delay-sensitive applications, in which the computation and storage resources are placed at the edge of network. The main responsibility of edge computing is to carry data from the Cloud downlinks and terminal uplinks, and organize these data well on the edge side. This is the basis for subsequent analysis and processing of data. Therefore, this brings about a question as to how those data should be organized on the edge and how to store and retrieve them. In response to this demand, some methods have been proposed to solve the related problems of how to build data storage and retrieval services on the edge side. Those methods propose three different solutions: structured, unstructured, and hybrid schemes. However, the data storage and retrieval services for the heterogeneous edge environment is still lack of research. It is still not considered an important design test load balancing when the data is stored on the edge side. In this paper, we design and implement w-strategy, a load balance approach that implements the appropriate load balance among the heterogeneous edge nodes by using the weighted Voronoi diagram. Our solution utilizes the software defined networking paradigm to support a virtual-space based distributed hash tables (DHTs) to distribute data. Evaluation results show that w-strategy achieves better load balancing among the heterogeneous edge nodes compared to the existing methods, GRED and Chord. And, the w-strategy improves the average underutilization of the resources by 20%.

Edge computing satisfies the stringent latency requirements of data access and processing for applications running on edge devices. The data location service is a key function to provide data storage and retrieval to enable these applications. However, it still lacks research of a scalable and low-latency data location service in mobile edge computing. Meanwhile, the existing solutions, such as DNS and DHT, fail to meet the low latency requirement of mobile edge computing. This paper presents a low-latency hybrid data-sharing framework, HDS, in which the data location service is divided into two parts: intra-region and inter-region. In the intra-region part, we design a data sharing protocol called Cuckoo Summary to achieve fast data localization. In the inter-region part, we develop a geographic routing based scheme to achieve efficient data localization with only one overlay hop. The advantages of HDS include short response latency, low implementation overhead, and few false positives. We implement our HDS framework based on a P4 prototype. The experimental results show that, compared to the state-of-the-art solutions, our design achieves 50.21% shorter lookup paths and 92.75% fewer false positives.

The proliferation of mobile computing has prompted Pedestrian Dead Reckoning (PDR) to be one of the most attractive and promising indoor localization techniques for ubiquitous applications. The existing PDR approaches either suffer position drifts caused by accumulative errors or are sensitive to various users. This paper presents ARPDR, an accurate and robust PDR approach to improve the accuracy and robustness of indoor localization methods. Particularly, we propose a novel step counting algorithm based on motion models by deeply exploiting inertial sensor data. We then combine step counting with adaptive thresholding to personalize the PDR system for different users. Furthermore, we propose a novel stride-heading model with a deep neural network to predict stride lengths and walking orientations, thus the displacement errors are significantly reduced. Extensive experiments on public datasets demonstrate that ARPDR outperforms the state-of-the-art PDR methods.

Vehicular cloud computing (VCC) has been utilized to enhance traffic management and road safety. By connecting with base stations (BSes), VCC can provide the information of real-time dynamics for smart vehicles (SVs). However, the area outside the coverage of BSes will be the blind areas, where SVs cannot obtain the real-time safety guarantee, especially on the highway. In this article, we utilize unmanned aerial vehicles (UAVs) to assist the communication between SVs and BSes to solve the above problem. In particular, we study the interdependency task scheduling for the highway driving environment detection, where SVs, BSes, and UAVs collect the environmental data, schedule tasks, and feedback results cooperatively. There are two main problems in this scenario: 1) the scheduling within the coverage of BSes and 2) the rescheduling between the coverage of BSes. We model both the processes as constrained numerical optimization problems aiming to minimize the request-response time. To this end, we propose a systematical scheduling scheme named Teso, which consists of two stages: 1) designed approximation algorithm for scheduling and 2) offloading algorithm for rescheduling. Extensive experiments show that Teso can significantly reduce the response time overall and improve the system stability.

The edge storage is a promising paradigm to support the Internet of Things (IoT) data storage, and is more efficient than the cloud storage in terms of the bandwidth overhead, the response latency, and so on. However, existing edge storage models cannot offer the security-aware data robustness and the adaptable data sharing among many uncertain users, due to the limitations of the utilized fault-tolerant storage technologies and the access control methods. In this article, we propose a secure and trust-oriented edge storage model, which would efficiently tackle the aforementioned two challenging issues in the IoT environment. More precisely, we first propose a robust and secure edge storage (RoSES) model using the totally local reconstruction code (TLRC) method presented in this article. It can achieve data robustness, high security, and lightweight computation at end devices. We further propose a trust-oriented data access (TODA) strategy for our RoSES model, which supports a wide and adaptable range of legitimate data accesses from uncertain requesters for IoT data sharing. We conduct extensive comparison and simulations to evaluate the performance of our new edge storage models. The results show that our model can efficiently realize the data storage, data recovery, and data sharing at the network edge, saving about 35% of storage cost and 76% degraded read latency. Besides, the data leakage probability is significantly reduced during the data storage and sharing processes.

Due to the high complexity of artificial intelligence (AI) algorithms, performing the AI tasks on the resource-limited Internet-of-Things (IoT) devices has been proved to be inadvisable. Edge computing provides an effective computing paradigm for executing AI tasks, where large numbers of AI tasks can be offloaded to the edge servers. Most of the existing works focus on achieving efficient computing offload through improving the Quality of Service (QoS), such as reducing the average server-side delay. However, we show that those efforts are inefficient due to the heterogeneous impact of delays on users' Quality of Experience (QoE). Inspired by the observations, in this article, we reconsider the scheduling method from an orthometric perspective, i.e., improving the QoE by designing a QoE-aware service-enhancement strategy for edge AI applications. Besides, multiple AI algorithms are utilized in our service model to execute the same type of tasks concurrently, thus meeting users' heterogeneity requirements of accuracy and delays. Specifically, for the online arriving AI tasks, we optimize the task allocation and scheduling strategy according to the QoE sensitivity of each task. The model can be formulated as the mixed-integer nonlinear programming problem, which is known to be NP-hard. Hence, we then propose an efficient two-phase scheduling strategy for this problem. The results of comprehensive emulations validate that our model can effectively improve the average QoE of users and achieve a higher task completion ratio.

City-wide package delivery has become popular due to the dramatic rise of online shopping. It places a tremendous burden on the traditional logistics industry, which relies on dedicated couriers and is labor-intensive. Leveraging the ridesharing systems is a promising alternative, yet existing solutions are limited to one-hop ridesharing or need consignment warehouses as relays. In this paper, we propose a new package delivery scheme which takes advantage of multi-hop ridesharing and is entirely consignment free. Specifically, a package is assigned to a taxi which is guided to deliver the package all along to its destination while transporting successive passengers. We tackle it with a two-phase solution, named PPtaxi. In the first phase, we use the Multivariate Gaussian distribution and Bayesian inference to predict the passenger orders. In the second phase, both the computation efficiency and solution effectiveness are considered to plan package delivery routes. We evaluate PPtaxi with a real-world dataset from an online taxi-taking platform and compare it with multiple benchmarks. The results show that the successful delivery rate of packages with our solution can reach 95 percent on average during the daytime, and is at most 46.9 percent higher than those of the benchmarks.

Changes in network state are a common source of instability in networks. An update event typically involves multiple flows that compete for network resources at the cost of rescheduling and migrating some existing flows. Previous network updating schemes tackle such flows independently, rather than as the entity of an update event. They only optimize the flow-level metrics for the flows involved in an update event. In this paper, we present an event-level abstraction of network update that groups flows of an update event and schedules them together to minimize the event completion time (ECT). We then study the scheduling problem of multiple update events for achieving high scheduling efficiency and preserving fairness. The designed least migration traffic first (LMTF) method schedules all update events in the FIFO order, but it avoids head-of-line blocking by randomly fine-tuning the queue order of some events. It can considerably reduce the update cost, the average, and tail ECTs of update events. In addition, we design a general parallel-LMTF (P-LMTF) method to guarantee fairness and further improve scheduling efficiency among update events. This improves the LMTF method by opportunistically updating multiple events simultaneously. The comprehensive evaluation results indicate that the average ECT of our approach is up to 10× faster than the flow-level scheduling method for network update events, and its tail ECT is up to 6× faster. Our P-LMTF method incurs a 75% reduction in the average ECT compared with FIFO when the network utilization exceeds 70%, and it achieves a 42% reduction in tail ECT.

Edge computing is a promising computing paradigm by pushing the cloud service to the network edge. To this end, edge infrastructure providers (EIPs) need to bring computation and storage resources to the network edge and allow edge service providers (ESPs) to provision latency-critical services for end users. Currently, EIPs prefer to establish a series of private edge-computing environments to serve specific requirements of users. This kind of resource provisioning mechanism severely limits the development and spread of edge computing in serving diverse user requirements. In this paper, we propose an integrated resource provisioning model, namededge federation, to seamlessly realize the resource cooperation and service provisioning across standalone edge computing providers and clouds. To efficiently schedule and utilize the resources across multiple EIPs, we systematically characterize the provisioning process as a large-scale linear programming (LP) problem and transform it into an easily solved form. Accordingly, we design a dynamic algorithm to tackle the varying service demands from users. We conduct extensive experiments over the base station networks in Toronto. Compared with the fixed contract model and multihoming model, edge federation can reduce the overall costs of EIPs by 23.3% to 24.5%, and 15.5% to 16.3%, respectively.

Large-scale datacenters are the key infrastructures of cloud computing. Inside a datacenter, a large number of servers are interconnected using a specific datacenter network to deliver the infrastructure as a service (IaaS) for tenants. To realize novel cloud applications like the network virtualization and network isolation among tenants, the principle of software-defined network (SDN) has been applied to datacenters. In the setting, multiple distributed controllers are deployed to offer a control plane over the entire datacenter to efficiently manage the network usage. Despite such efforts, cloud datacenters, however, still lack a scalable and resilient control plane. Consequently, this paper systematically studies the coverage problem of controllers, which means to cover all network devices using the least number of controllers. More precisely, we tackle this essential problem from three aspects, including the minimal coverage, the minimal fault-tolerant coverage, and the minimal communication overhead among controllers. After modelling and analyzing such three problems, we design efficient approaches to approximate the optimal solution, respectively. Extensive evaluation results indicate that our approaches can significantly save the number of required controllers, improve the fault-tolerant capability of the control plane and reduce the communication overhead of state synchronization among controllers. The design methodologies proposed in this paper can be applied to cloud datacenters with other networking structures after minimal modifications.

Set reconciliation is a common and fundamental task in distributed systems. In many cases, given set A on $Host_A$ and set B on $Host_B$, applications need to identify those elements that appear in set A but not in set B, and vice versa. However, existing methods incur unsatisfactory space utilization and non-trivial false positives and false negatives. In this paper, we present a novel reconciliation method based on Cuckoo filter (CF). After exchanging the CFs each of which represents a set of elements, we query the local elements against the received CF to determine the elements that only belong to the local host and should be transmitted to the other host. The evaluation results indicate that the CF-based reconciliation method outperforms existing methods significantly.

An evolving pattern graph is defined by an initial pattern graph and a graph update stream consisting of edge insertions and deletions. Identifying and monitoring evolving graph patterns in the data graph is important in various application domains such as Cyberthreats surveillance. This motivates us to explore matching patterns with evolvement, and the investigation presents a novel algorithm \incepg for continuously matching of evolving patterns. Specially, we propose a concise representation \Index of partial matching solutions, and its execution model allows fast incremental maintenance. We also conceive an effective model for estimating step-wise cost of pattern evaluation to drive the matching process. Extensive experiments verify the superiority of \incepg.

Vehicle-based crowdsourcing is expected to be an economic yet efficient solution to build and maintain an accurate, fine-grained, and up-to-date environment map (i.e., high-definition map) for autonomous vehicles, which is an essential building block for safe and intelligent autonomous driving. However, how to select crowdsourcing workers with performance maximization is prudent and quite challenging since vehicles are highly dynamic and have unpredictable routes. In this paper, we study the worker selection problem for crowdsourced on-route map collection where the trade- off between the real-time worker exploration and exploitation is the main focus. Specifically, by adopting the multi-armed bandit model, we formulate a cumulative platform utility maximization problem. To solve this problem, we propose an Online Worker Selection (OWS) scheme, to learn drivers' performance and make worker selection decisions in real time. Essentially, two key designs are integrated in OWS: 1) performance transfer. If a new driver joins the crowdsourcing, we will initialize the new driver's performance based on the knowledge transferred from the existing drivers' records; and 2) marginal utility. Particularly, we carefully incorporate the platform utility to embody the marginal effect, i.e., repeated coverage by multiple vehicles on a certain road will undermine the utility. Based on the real-world vehicular GPS trace, we conduct extensive trace- driven simulations, and results demonstrate that our scheme can effectively obtain high-quality environment map, with on average 40.5% crowdsourcing utility gain over other benchmark schemes.

Edge computing is a new paradigm in which the computing and storage resources are placed at the edge of the Internet. Data placement and retrieval are fundamental services of edge computing when a network of edge servers collaboratively provide data storage. These services require short-latency and low-overhead implementation in network devices and load balance on edge servers. However existing methods such as distributed hash tables (DHTs) are not able to achieve efficient data placement and retrieval services in the edge computing environment. This paper presents GRED, an efficient data placement and retrieval service for edge computing, which is efficient in not only the load balance but also routing path lengths and forwarding table sizes. GRED utilizes the software-defined networking paradigm to support a virtual-space based DHT with only one overlay hop. We implement GRED in a P4 prototype. Experimental results show that GRED uses <; 30% routing path lengths and achieves better load balance among edge servers compared to using Chord, a well-known DHT solution.

The mission of set reconciliation (also called set synchronization) is to identify those elements which appear only in exactly one of two given sets. In this paper, we extend the set reconciliation problem into three design rationales: (i) multiset support; (ii) near 100% reconciliation accuracy; (iii) communication-friendly and time-saving. Prior reconciliation methods fail to realize the three rationales simultaneously. To this end, we redesign Trie and Fenwick Tree (FT), to near-accurately represent and reconcile two types of multisets that we refer to as unsorted and sorted multisets, respectively. Comprehensive evaluations are conducted to quantify the performance of our proposals. The trace-driven evaluations demonstrate that Trie and FT achieve near-accurate multiset reconciliation, with 4.31 and 2.96 times faster than the CBF-based method, respectively.

In datacenter networks, flows need to complete as quickly as possible because the flow completion time (FCT) directly impacts user experience, and thus revenue. Link failures can have a significant impact on short latency-sensitive flows because they increase their FCTs by several fold. Existing link failure management techniques cannot keep the FCTs low under link failures because they cannot completely eliminate packet loss during such failures. We observe that to completely mask the effect of packet loss and the resulting long recovery latency, the network has to be responsible for packet loss recovery instead of relying on end-to-end recovery. To this end, we propose Shared Queue Ring (SQR), an on-switch mechanism that completely eliminates packet loss during link failures by diverting the affected flows seamlessly to alternative paths. We implemented SQR on a Barefoot Tofino switch using the P4 programming language. Our evaluation on a hardware testbed shows that SQR can completely mask link failures and reduce tail FCT by up to 4 orders of magnitude for latency-sensitive workloads.

The emergence of large-scale dynamic sets in networking applications attaches stringent requirements to approximate set representation. The existing data structures (including Bloom filter, Cuckoo filter, and their variants) preserve a tight dependency between the cells or buckets for an element and the lengths of the filters. This dependency, however, degrades the capacity elasticity, space efficiency and design flexibility of these data structures when representing dynamic sets. In this paper, we first propose the Index-Independent Cuckoo filter (I2CF), a probabilistic data structure that decouples the dependency between the length of the filter and the indices of buckets which store the information of elements. At its core, an I2CF maintains a consistent hash ring to assign buckets to the elements and generalizes the Cuckoo filter by providing optional k candidate buckets to each element. By adding and removing buckets adaptively, I2CF supports the bucket-level capacity alteration for dynamic set representation. Moreover, in case of a sudden increase or decrease of set cardinality, we further organize multiple I2CFs as a Consistent Cuckoo filter (CCF) to provide the filter-level capacity elasticity. By adding untapped I2CFs or merging under-utilized I2CFs, CCF is capable of resizing its capacity instantly. The trace-driven experiments indicate that CCF outperforms its alternatives and realizes our design rationales for dynamic set representation simultaneously, at the cost of a little higher complexity.

Edge computing promises a dramatic reduction in the network latency and the traffic volume, where many edge servers are placed at the edge of the Internet. Furthermore, these edge servers cache data to provide services for edge users. The data sharing among edge servers can effectively shorten the latency to retrieve the data and further reduce the network bandwidth consumption. The key challenge is to construct an efficient data indexing mechanism no matter how the data is cached in the edge network. Although this is essential, it is still an open problem. Moreover, existing methods such as the centralized indexing and the DHT indexing in other fields fail to meet the performance demand of edge computing. This paper presents a COordinate-based INdexing (COIN) mechanism for the data sharing in edge computing. COIN maintains a virtual space where the switches and the data indexes are associated with the coordinates. Then, COIN distributes data indexes to indexing edge servers based on those coordinates. The COIN is effective because any query request from an edge server can be responded when the data has been stored in the edge network. More importantly, COIN is efficient in both routing path lengths and forwarding table sizes for publishing/querying the data indexes. We implement COIN in a P4 prototype. Experimental results show that COIN uses 59% shorter path length and 30% less forwarding table entries to retrieve the data index compared to using Chord, a well-known DHT solution.

As more and more applications are deployed in data centers, they rely on high performance data center networks (DCNs) to meet users' increasing quality of the experience (QoE) requirements. Hence, minimizing the average flow completion time (FCT) has been one of the most important goals for DCNs. However, existing traffic scheduling methods assume either prior knowledge of flows (i.e., sizes and deadlines) or symmetric topologies (i.e., Fat-Tree or Bcube). In practice, it is difficult to obtain the information of flows. Moreover, even with symmetric topology design, the DCNs will become asymmetric due to the inevitable link failure and congestion. In this case, it is a great challenge to minimize the average FCT in DCNs. In this paper, we propose a flowlet based information-agnostic traffic scheduling mechanism. The key idea of our method is leveraging multiple priority queues in switches to demote the priority of flows dynamically on the flowlet level. More specifically, the priority of a flow will be demoted according to the number of flowlets it has sent, which follows the shortest job first discipline. We formulate the average FCT minimization problem as a nonlinear Sum-of-Ratios problem and design two heuristic methods to derive the sub-optimal demotion thresholds. Experiment results show that our method can reduce the average FCT by up to 15.35% with a realistic workload, as compared to the state-of-the-art traffic scheduling methods.

A data-parallel job is characterized as a directed acyclic graph (DAG) which usually consists of multiple computation stages and across-stage data transfers. However, classical DAG scheduling strategies like the critical path method ignore other stages off the main path and do not give specific consideration of data locality, transfer costs, etc. In practice, complicated DAGs include multiple paths which overlap with each other. The intersection of different paths in a DAG job forms an important synchronization. The synchronization significantly impacts the job completion time and however, no known scheduling methods are designed to speed up the completion time of the synchronization especially when complicated DAGs involve nested and hierarchical synchronizations. To the end, we propose a new abstraction, named branch, which is referred to a disjoint path in DAGs, and design a branch scheduling method to decrease the average job completion time of multiple data-parallel jobs. The branch scheduling method leverages the urgency of branches to speed up the synchronization of multiple parallel branches. We have implemented the BS method on Apache Spark and conducted prototype-based experiments. Compared with Spark FIFO and the shortest-job-first with the critical path methods, results show that the branch scheduling method achieves around 10-15% reduction in the average job completion time.

Summary In the erasure coding storage system, it is necessary to extract multiple data blocks from other remaining storage nodes to a new node when a storage node fails, which repairs the failed data block satisfactorily. However, this would incur the incast problem at this new node. The existing solutions for the repair process in the incast problem mainly rely on path planning and resource allocation. Although these solutions improve the performance of repairing the failed data blocks, they still waste a large amount of storage and bandwidth resources unavoidably. In this paper, we propose the incast problem to be resolved economically via the in‐network aggregation. Specifically, we assume that the switches in data centers have certain data processing capabilities and can aggregate data flows efficiently. Thereafter, we propose a set of in‐network methods to repair a failed data block in the erasure coding storage systems, taking the fat‐tree data center as an example. Thus, the incast problem can be solved effectively during the data transmission process. Compared with the prior methods, our approach effectively avoids the overhead of extra path computing, as well as significantly reduces the link cost of repairing data blocks, while promising similar or faster repair speed.

The demand for package delivery services is extremely huge every day, because of the rapid development on online retailers. This leads to huge traffic congestion, resource consumption, and environmental pollution (e.g., carbon emission). However, the urban public transport system offers a large amount of under-utilized capacity outside the peak hours. In this paper, we present the city-wide package distribution problem using crowdsourced public transportation systems (CPTSs). That is, packages are delivered by carefully utilizing the considerable amount of idle capacity of the CPTS. Specifically, given a number of packages and the timetable of available CPTS trips, we optimize the package delivering scheme by determining the four identified states of any package at any time slot (waiting, riding, rewaiting, and being unloaded). The delivering scheme can be modeled as an instance of the multicommodity flow problem, and formulated by the integer linear programming techniques. We then propose an efficient heuristic solution for this NP-hard problem. Finally, this paper is validated via comprehensive emulations with a real bus transportation network.

Usually, a data flow needs to traverse a series of network functions, which is called a service function chain (SFC), before reaching its destination. The emergence of network function virtualization (NFV) makes the embedding solution of the SFC flexible as far as the deployment location is concerned. When providers embed the SFC into a substrate network, they will hope to minimize the setup cost of the SFC and link connection cost toward clients. For unicast, since there is one path connecting the source node to the destination node, all functions of the SFC are just needed to be deployed along the path. However, when embedding the SFC for a multicast task, the topology of the SFC may change because the function deployment locations have impacts on the traffic delivery cost. Thus, a service function tree (SFT) may be a better choice. Given the huge space of SFT embedding solutions, however, it is extremely hard to find the optimal one such that the total traffic delivery cost is minimized. In this paper, we tackle the optimal SFT embedding problem in the NFV enabled multicast task. Specifically, we formally define the problem and formulate it with an integer linear programming (ILP), which turns out to be NP-hard. Then, a two-stage method is proposed to deal with the problem with an approximation ratio of$1+\rho $, where$\rho $is the best approximation ratio of Steiner tree and can be as small as 1.39. With extensive experimental evaluations, we demonstrate that by applying our SFT embedding solution, the delivery cost of multicast traffic can be reduced by 22.05% at most against three benchmarks.

The emerging deployment of large-scale cloud applications incurs significant inter-datacenter traffic, which makes the scarce wide-area bandwidth across data centers become the performance bottleneck. To achieve the desirable network performance, bandwidth guarantee should be provided for the resulting inter-datacenter traffic. However, the existing bandwidth allocation methods mainly focus on intra-datacenter traffic, and cannot achieve the cost-minimizing bandwidth guarantee for inter-datacenter traffic. In this paper, we focus on the bandwidth guarantee problem for inter-datacenter traffic and present a novel bandwidth allocation model. Our model can ensure the bandwidth guarantee, minimize the resulting network cost, and efficiently avoid the potential traffic overload on low cost links. To solve the large-scale optimization problem in our model, we are motivated to develop a distributed algorithm by blending the advantages of alternating direction method of multipliers (ADMM) and the auxiliary variable method. Specifically, we efficiently decompose the optimization problem into many small sub-problems, which are allowed to be processed in a large-scale computing environment, where each server solves a few small sub-problems. We further present a theoretically proved globally, asymptotically stable algorithm to solve these sub-problems. Extensive evaluation results demonstrate that our bandwidth allocation method can effectively realize the bandwidth guarantee for inter-datacenter traffic with reduced network cost and outperforms the prior method PS-L. In particular, the total network cost is reduced by 59.57 percent on average.

Uncertainty is intrinsic to a wide spectrum of real-life applications, which inevitably applies to graph data. Representative uncertain graphs are seen in bio-informatics, social networks, etc. This paper motivates the problem of frequent subgraph mining on single uncertain graphs, and investigates two different - probabilistic and expected - semantics in terms of support definitions. First, we present an enumeration-evaluation algorithm to solve the problem under probabilistic semantics. By showing the support computation under probabilistic semantics is #P-complete, we develop an approximation algorithm with accuracy guarantee for efficient problem-solving. To enhance the solution, we devise computation sharing techniques to achieve better mining performance. Afterwards, the algorithm is extended in a similar flavor to handle the problem under expected semantics, where checkpoint-based pruning and validation techniques are integrated. Experiment results on real-life datasets confirm the practical usability of the mining algorithms.

The mission of set reconciliation (also called set synchronization) is to identify those elements which appear only in exactly one of two given sets. In this paper, we extend the set reconciliation problem into three design rationales: (i) multiset support; (ii) near 100 percent reconciliation accuracy; and (iii) communication-friendly and time-saving. These three rationales, if realized, will lead to unprecedented benefits for the set reconciliation paradigm. Generally, prior reconciliation methods are mainly designed for simple sets and thus remain inapplicable for multisets. Methods based on probabilistic data structures, e.g., the Counting Bloom Filter (CBF), support efficient representation, and multiplicity queries. Based on these probabilistic data structures, approximate multiset reconciliation can be enabled. However, they often cannot achieve a statisfying accuracy, due to potential hash collisions. The reconciliations enabled by logs or lists incur high time-complexity and communication overhead. Therefore, existing reconciliation methods, fail to realize the three rationales simultaneously. To this end, we redesign Trie and Fenwick Tree (FT), to near-accurately represent and reconcile two types of multisets that we refer to as unsorted and sorted multisets, respectively. Moreover, to further reduce the communication overhead during the reconciliation process, we design a partial transmission strategy when exchanging two Tries or FTs. Comprehensive evaluations are conducted to quantify the performance of our proposals. The trace-driven evaluations demonstrate that Trie and FT achieve near-accurate multiset reconciliation, with 4.31 and 2.96 times faster than the CBF-based method, respectively. The simulations based on synthetic datasets further indicate that our proposals outperform the CBF-based method in terms of accuracy and communication overhead at most time.

In data centers, a lot of cluster computing applications follow the coflow working pattern. That is, a collection of flows between two groups of machines is semantically related. On the other hand, network function virtualization sufficiently improves the performance of data center networks. It however complicates the network environment by introducing many multi-function middleboxes each with multiple resources. Coflows encounter extremely different processing delays under diverse network functions. Prior coflow scheduling schemes are insufficient to guarantee the coflow completion time in the multi-resource environment. In this paper, we propose, model, and analyze the coflow scheduling problem in the multi-resource environment. We present a dedicated method, data rate guarantee for coflow (DRGC), to guarantee the data rate requirements of coflows in this situation. DRGC prioritizes the coflow scheduling sequence, assigns precise data rates for coflows, and deploys a packet scheduling algorithm at middleboxes to guarantee their transmissions. In our experiments, DRGC efficiently guarantees the completion times of coflows and supports 15% more workload, compared with other scheduling schemes.

The content delivery network (CDN) intensively uses cache to push the content close to end users. Over both traditional Internet architecture and emerging cloud-based framework, cache allocation has been the core problem that any CDN operator needs to address. As the first step for cache deployment, CDN operators need to discover or estimate the distribution of user requests in different geographic areas. This step results in a statistical spatial model for the user requests, which is used as the key input to solve the optimal cache deployment problem. More often than not, the temporal information in user requests is omitted to simplify the CDN design. In this paper, we disclose that the spatial request model alone may not lead to truly optimal cache deployment and revisit the problem by taking the dynamic traffic demands into consideration. Specifically, we model the time-varying traffic demands and formulate the distributed cache deployment optimization problem with an integer linear program (ILP). To solve the problem efficiently, we transform the ILP problem into a scalable form and propose a greedy diagram to tackle it. Via experiments over the North American ISPs points of presence (PoPs) network, our new solution outperforms traditional CDN design method and saves the overall delivery cost by 16% to 20%. We also study the impact of various traffic demand patterns to the CDN design cost, via experiments with both real-world traffic demand patterns and extensive synthetic trace data.

The design of distributed control plane is an essential part of SDN. While there is an urgent need for verifying the control plane, little, however, is known about how to validate that the control plane offers assurable performance, especially across various failures. Such validation is hard due to two fundamental challenges. First, the number of potential failure scenarios could be exponential or even non-enumerable. Second, it is still an open problem to model the performance change when the control plane employs different failure recovery strategies. In this paper, we first characterize the validation of the distributed control plane as a robust optimization problem and further propose a robust validation framework to verify whether a control plane provides assurable performance across various failure scenarios and multiple failure recovery strategies. Then, we prove that identifying an optimal recovery strategy is NP-hard after developing an optimization model of failure recovery. Accordingly, we design two efficient failure recovery strategies, which can well approximate the optimal strategy and further exhibit good performance against potential failures. Furthermore, we design the capacity augmentation scheme when the control plane fails to accommodate the worst failure scenario even with the optimal failure recovery strategy. We have conducted extensive evaluations based on an SDN test bed and large-scale simulations over real network topologies. The evaluation results show the efficiency and effectiveness of the proposed validation framework.

A mobile crowdsensing (MCS) platform motivates employing participants from the crowd to complete sensing tasks. A crucial problem is to maximize the profit of the platform, i.e., the charge of a sensing task minus the payments to participants that execute the task. In this article, we improve the profit via the data reconstruction method, which brings new challenges, because it is hard to predict the reconstruction quality due to the dynamic features and mobility of participants. In particular, two Profit-driven Online Participant Selection (POPS) problems under different situations are studied in our work: (1) for S-POPS, the sensing cost of the different parts within the target area is the Same. Two mechanisms are designed to tackle this problem, including the ProSC and ProSC+. An exponential-based quality estimation method and a repetitive cross-validation algorithm are combined in the former mechanism, and the spatial distribution of selected participants are further discussed in the latter mechanism; (2) for V-POPS, the sensing cost of different parts within the target area is Various, which makes it the NP-hard problem. A heuristic mechanism called ProSCx is proposed to solve this problem, where the searching space is narrowed and both the participant quantity and distribution are optimized in each slot. Finally, we conduct comprehensive evaluations based on the real-world datasets. The experimental results demonstrate that our proposed mechanisms are more effective and efficient than baselines, selecting the participants with a larger profit for the platform.

The rapid development of mobile computing has prompted indoor navigation to be one of the most attractive and promising applications. Conventional designs of indoor navigation systems depend on either infrastructures or indoor floor maps. This article presents CloudNavi, a ubiquitous indoor navigation solution, which relies on the point clouds acquired by the 3D camera embedded in a mobile device. Particularly, CloudNavi first efficiently infers the walking trace of each user from captured point clouds and inertial data. Many shared walking traces and associated point clouds are combined to generate the point cloud traces, which are then used to generate a 3D path-map. Accordingly, CloudNavi can accurately estimate the location of a user by fusing point clouds and inertial data using a particle filter algorithm and then guiding the user to its destination from its current location. Extensive experiments are conducted on office building and shopping mall datasets. Experimental results indicate that CloudNavi exhibits outstanding navigation performance in both office buildings and shopping malls and obtains around 34% improvement compared with the state-of-the-art method.

The topology of a network may change inevitably, due to dynamic behaviors of nodes and links, and failures of hardware and software. Many protocols and applications must be aware of the up-to-date topology of the underlying network. This triggers the topology calibration problem, which means to deduce those different nodes and links between two topologies. The Bloom filter and its variants are efficient to represent and calibrate two general sets. They, however, fail to represent all links and nodes in a topology simultaneously, and thus remain inapplicable to the topology calibration problem. In this paper, we design the graph filter, a novel space-efficient data structure to record not only the node set but also the link set of any given topology. Accordingly, given two topologies we aim to represent them via two respective graph filters, and thereafter deduce those different links in an invertible manner. To this end, we design three essential operations for graph filter, i.e., encoding, subtracting and decoding. Although such operations are sufficient to solve the topology calibration problem, two challenging issues still remain open. First, the XOR traps which occur with low probability at the encoding stage may result in a few miscalculations at the decoding stage. Thus, we propose another augmented decoding algorithm to lessen the impact of XOR traps via terminating illegal decodings. Second, several different links may form cycles in the worst case; hence, we further design a cycle destruction algorithm to make such different links decodable. We implement the graph filter and the associated topology calibration method. Comprehensive evaluations indicate that our method finishes the topology calibration task efficiently with high probability, incurs the least space overhead, and supports invertible decoding reasonably.

The cloud datacenter network is consistently undergoing changing, due to a variety of topology and traffic updates, such as the VM migrations. Given an update event, prior methods focus on finding a sequence of lossless transitions from an initial network state to an end network state. They, however, suffer frequent and global search of the feasible end network states. This incurs non-trivial computation overhead and decision-making delay, especially in large-scale networks. Moreover, in each round of transition, prior methods usually cause the cascaded migrations of existing flows; hence, significantly disrupt production services in IaaS data centers. To tackle such severe issues, we present a simple update mechanism to minimize the amount of flow migrations during the congestion-free network update. The basic idea is to replace performing the sequence of global transitions of network states with local reschedule of involved flows, caused by an update event. We first model all involved flows due to an update event as a set of new flows, and then propose a heuristic method Lupdate. It motivates to locally schedule each new flow into the shortest path, at the cost of causing the extra migration of at most one existing flow if needed. To minimize the amount of migrated traffic, the migrated flow should be as small as possible. To further improve the success rate, we propose an enhanced method Lupdate-S. It shares the similar design of Lupdate, but permits to migrate multiple necessary flows on the shortest path allocated to each new flow. We conduct large-scale trace-driven evaluations under widely used Fat-Tree and ER data centers. The experimental results indicate that our methods can realize congestion-free network with as less amount of traffic migration as possible even when the link utilization of a majority of links is very high. The amount of traffic migration caused by our Ludpate method is 1.2 times and 1.12 times of the optimal result in the Fat-Tree and ER random networks, respectively.

In network traffic engineering, multicast is designed to deliver the same content from a single source to a group of destinations. Recently, NFV enabled multicast has been developed by deploying virtual network functions (VNFs) over the target network. To fulfill the multicast task with a service function chain (SFC) requirement, a service function tree (SFT) embedded in the shared multicast tree has to be built. Given the huge space of SFT embedding solutions, however, it is extremely hard to find the optimal one such that the total traffic delivery cost is minimized. In this paper, we tackle the optimal SFT embedding problem in NFV enabled multicast task. Specifically, we formally define the problem and formulate it with an integer linear programming (ILP), which turns out to be NP-hard. Then, a two-stage algorithm is proposed to deal with the problem with an approximation ratio of 1+p, where p is the best approximation ratio of Steiner tree and can be as small as 1.39. With extensive experimental evaluations, we demonstrate that by applying our SFT embedding solution, the cost saving of multicast traffic delivery can be up to 22.41%, compared with the random SFT embedding strategy.

The demand for package delivery services is extremely huge every day, because of the rapid development on online retailers. This leads to huge traffic congestion, resource consumption and environmental pollution (e.g. carbon emission). However, the urban public transport system offers a large amount of under-utilized capacity outside the peak hours. In this paper, we present the City-wide Package Distribution problem using Crowdsourced Public Transportation Systems (CPTS). That is, packages are delivered by carefully utilizing the considerable amount of idle capacity of the CPTS. Specifically, given a number of packages and the timetable of available CPTS trips, we optimize the package delivering scheme by determining the four identified states of any package at any time slot (waiting, riding, re-waiting and being unloaded). The delivering scheme can be modeled as an instance of the multi-commodity flow problem, and formulated by the Mixed Integer LinearProgramming techniques. We then propose an efficient heuristic solution for this NP-hard problem. Finally, our work is validated via comprehensive emulations with a real bus transportation network.

In data centers, files are stored with the method of erasure code or replication to guarantee data reliability. However, both of the methods are not communication-friendly. An erasure coding system spends vast time to extract k data blocks across the racks during the decoding process. The transmission time contributes up to 94% of the total decoding time. In a multi-replica system, the frequent data writing and updating also lead to non-trivial bandwidth overhead. In this paper, we consider server-centric data centers (such as BCube), in which any pair of nodes are interconnected with multiple parallel paths. In such data centers, the transmissions for file storage can be significantly speed up by utilizing the parallel paths concurrently. With this insight, we first define the disjoint node in BCube. Based on this definition, we design the node-disjoint storage strategy (NDSS)and the nested node-disjoint storage strategy (N-NDSS)to improve the transmission between distributed storage nodes. Comprehensive simulations show the performance of our strategies in both erasure coding system and multi-replica system.

Network Function Virtualization (NFV) is an emerging technology, which enables service agility, flexibility and cost reduction by replacing traditional hardware middleboxes with Virtual Network Functions (VNFs) running on general-purpose servers. Service Function Chain (SFC) constitutes an end-to-end service by organizing a series of VNFs in a specific order. Particularly, hybrid SFC (SFC with parallel VNFs) is proposed to much reduce the traffic delay in sequential SFCs. Nevertheless, how to strategically select VNF instances and links in hybrid SFC embedding remains an open problem. In this paper, we target at the cost minimization and address the optimal hybrid SFC embedding problem. Specifically, we first develop a novel abstraction model for the hybrid SFC with Directed Acyclic Graph (DAG), which helps convert diverse hybrid SFCs to the standardized DAG-SFC form. Then, we formulate the optimal DAG-SFC embedding problem as an integer optimization model and propose a greedy method (called BBE) to solve the NP-hard problem. MBBE method is developed upon BBE method to further cut down the computation complexity in model solving. Extensive simulation results demonstrate the effectiveness of our approach for cost reduction in hybrid SFC embedding.

A mobile crowdsensing (MCS) platform motivates to employ participants from the crowd to complete sensing tasks. A crucial problem is to maximize the profit of the platform, i.e., the charge of a sensing task minus the payments to participants that execute the task. Recently, the appearance of data reconstruction method makes it possible to improve the platform's profit with a limited amount of sensing results in Compressive MCS (CMCS). However, It is of great challenge to the maximal profit for the CMCS platform, since it is hard to predict the reconstruction quality due to the dynamic features and mobility of participants. In response to such challenges, we propose two profit-driven online participant selection mechanisms for the given task model and participant model. In ProSC, the sub-profit in each slot is maximized during the sensing period of a task, by combing a statistical-based quality prediction method and a repetitive cross-validation algorithm. In ProSC+, we jointly optimize the number of required participants and their spatial distribution to further improve the converging property. Finally, we conduct comprehensive evaluations, the results indicate the effectiveness and efficiency of our mechanisms.

To enable the network softwarization, network function virtualization (NFV) and software defined networking (SDN) are integrated to jointly manage and utilize the network resource and virtualized network functions (VNFs). For a network flow resulting from any NFV application, an associated switch would send a routing request to the controller in SDN. The controller then generates and configures a routing path to dynamically steer the flow across appropriate VNFs or service function chains. This process, however, exhibits a skew distribution of response latency with a long tail. Cutting the long-tail latency of response is critical to enable the network softwarization, yet difficult to achieve due to many factors, such as the limited capacities and the load imbalance among controllers. In this paper, we reveal that such flow requests still experience the long-tail response latency, even using the up-to-date controller-to-switch assignment mechanism. To tackle this essential problem, we first propose a light-weight and load-aware switch-to-controller selection scheme to cut the long-tail response latency under the simple scenario of homogeneous controllers, and then design a general delay-aware switch-to-controller selection scheme to fundamentally cut the long-tail response latency for the more complicated heterogeneous controller scenario with performance fluctuations. The comprehensive evaluations indicate that our two new switch-to-controller selection schemes can significantly reduce the long-tail latency and provide higher system throughput.

Indoor semantic floorplan is important for a range of location based service (LBS) applications, attracting many research efforts in several years. In many cases, the out-of-date indoor semantic floorplans would gradually deteriorate and even break down the LBS performance. Thus, it is important to automatically update changed semantics of indoor floorplans caused by environmental variation. However, few research has been focused on the continuous semantic updating problem. This paper presents SISE as a mobile crowdsourcing system that uses a new abstraction for indoor general entities and their semantics, enGraph, to automatically update changed semantics of indoor floorplans using images and inertial data. We first propose efficient methods to generate enGraph. Thus, an image can be associated with an indoor semantic floorplan. Accordingly, we formulate the enGraph matching problem and then propose a quality-based maximum common subgraph matching algorithm so that entities extracted from an image can be corresponded to entities in the indoor semantic floorplan. Furthermore, we propose a quadrant comparison algorithm and a region shrink based localization algorithm to detect and localize changed entities. Thus, the new semantics can be labeled and out-of-date semantics can be removed. Extensive experiments have been conducted on real and synthetic data. Experimental results show that 80 percent of out-of-date semantics of indoor general entities can be updated by SISE.

Inefficient bandwidth sharing in a datacenter network, between different application frameworks, e.g., MapReduce and Spark, can lead to inelastic and skewed usage of link bandwidth and increased completion times for the applications. Existing work, however, either solely focuses on managing computation and storage resources or controlling only sending/receiving rate at hosts. In this paper, we present CoMan, a solution that provides global in-network bandwidth management in multiplexed data centers, with two goals: improving bandwidth utilization and reducing application completion time. CoMan first designs a novel abstraction of virtual link groups (VLGs) to establish a shared bandwidth resource pool. Based on this pool, CoMan implements a three-level bandwidth allocation model, which enables elastic bandwidth sharing among computing frameworks as well as guarantees network performance for the applications. CoMan further improves the bandwidth utilization by devising a VLG dependency graph and solves an optimization problem to guide the path selection using a 32-approximation algorithm. We conduct comprehensive trace-driven simulations as well as small-scale testbed experiments to evaluate the performance of CoMan. Extensive simulation results show that CoMan improves the bandwidth utilization and speeds up the application completion time by up to 2.83× and 6.68×, respectively, compared to the ECMP + ElasticSwitch solution. Our implementation also verifies that CoMan can realistically speed up the application completion times by 2.32× on average.

Increasing number of Internet-scale applications, such as video streaming, incur huge amount of wide area traffic. Such traffic over the unreliable Internet without bandwidth guarantee suffers unpredictable network performance. This result, however, is unappealing to the application providers. Fortunately, Internet giants like Google and Microsoft are increasingly deploying their private wide area networks (WANs) to connect their global datacenters. Such high-speed private WANs are reliable, and can provide predictable network performance. In this paper, we propose a new type of service-inter-datacenter network as a service (iDaaS), where traditional application providers can reserve bandwidth from those Internet giants to guarantee their wide area traffic. Specifically, we design a bandwidth trading market among multiple iDaaS providers and application providers, and concentrate on the essentialbandwidth pricingproblem. The involved challenging issue is that the bandwidth price of each iDaaS provider is not only influenced by other iDaaS providers, but also affected by the application providers. To address this issue, we characterize the interaction between iDaaS providers and application providers using a Stackelberg game model, and analyze the existence and uniqueness of the equilibrium. We further present an efficient bandwidth pricing algorithm by blending the advantage of a geometrical Nash bargaining solution and the demand segmentation method. For comparison, we present two bandwidth reservation algorithms, where each iDaaS provider's bandwidth is reserved in a weighted fair manner and a max-min fair manner, respectively. Finally, we conduct comprehensive trace-driven experiments. The evaluation results show that our proposed algorithms not only ensure the revenue of iDaaS providers, but also provide bandwidth guarantee for application providers with lower bandwidth price per unit.

The modular datacenter networks (MDCN) comprise inter- and intra-container networks. Although it simplifies the construction and maintenance of mega-datacenters, interconnecting hundreds of containers and supporting online data-intensive services is still challenging. In this paper, we present meGautz, which is the first inter-container network that isolates inter- and intra-container traffic, and it has the following advantages. First, meGautz offers uniform high capacity among servers in the different containers, and balances loads at the container, switch, and server levels. Second, it achieves traffic isolation and allocates bandwidth evenly. Therefore, even under an all-to-all traffic pattern, the inter- and intra-container networks can deal with their own flows without interfering with each other, and both can gain high throughput. meGautz hence improves the performance of both the entire MDCN and individual servers, for there is no performance loss caused by resource competition. Third, meGautz is the first to achieve as graceful performance degradation as computation and storage do. Results from theoretical analysis and experiments demonstrate that meGautz is a high-capacity, fault-tolerant, and traffic isolated inter-container network.

The emerging deployment of geographically distributed data centers (DCs) incurs a significant amount of data transfers over the Internet. Such transfers are typically charged by Internet Service Providers (ISPs) with the widely adopted q-th percentile charging model. In such charging model, the time slots with top 100-q percent of data transmission do not affect the total transmission cost, and can be viewed as free. This brings the opportunity to optimize the scheduling of inter-DC transfers to minimize the entire transmission cost. However, very little work has been done to exploit those free time slots for scheduling inter-DC transfers. The crux is that existing work either lacks a mechanism to accumulate traffic to free time slots, or inevitably relies on prior knowledge of traffic arrival patterns. In this paper, we attempt to exploit those free time slots by leveraging diverse time-sensitivities among inter-DC transfers, so as to reduce or even minimize the transmission cost. Specifically, we advocate that a simple principle should be followed: more traffic peaks should be scheduled in free time slots, while less traffic differentiation should be maintained among the remaining time slots. To this end, we take advantage of the Lyapunov optimization techniques to design a pricing-aware control framework. This framework efficiently makes online decisions for inter-DC transfers without requiring a prior knowledge of traffic arrivals. To verify our proposed framework, we conduct small-scale testbed implementation. The results show that our framework can realistically reduce the transmission cost by up to 19.38%.

Changes of network state are a common source of instability in networks. An update event typically involves multiple flows that compete for network resources at the cost of rescheduling and migrating some existing flows. Previous network updating schemes tackle such flows independently, rather than as the entity of an update event. They only optimize the flow-level metrics for the flows involved in an update event. In this paper, we present an event-level abstraction of network update which groups flows of an update event and schedules them together to minimize the event completion time (ECT). We then study the scheduling problem of multiple update events for achieving high scheduling efficiency and preserving fairness. The designed least migration traffic first (LMTF) method schedules all update events in the FIFO order, but avoids head-of-line blocking by randomly fine-tuning the queue order of some events. It can considerably reduce the update cost, the average, and tail ECTs of all update events. In addition, we design a general parallel-LMTF (P-LMTF) method to guarantee fairness and further improve scheduling efficiency among update events. It improves the LMTF method by opportunistically updating multiple events simultaneously. The comprehensive evaluation results indicate that the average ECT of our approach is up to 10× faster than the flow-level scheduling method for network update events, and its tail ECT is up to 6x faster. Our P-LMTF method incurs 75% reduction in the average ECT compared with FIFO when the network utilization exceeds 70%, and it achieves a 42% reduction in tail ECT.

The Visible Light Communication (VLC) has the potential to provide dense and fast connectivity at low cost. In this paper, we propose WSWDC, a novel VLC enabled wireless small-world data center. It employs VLC links to achieve a fully wireless data center network (DCN) across racks for the first time. The using of VLC links eliminates hierarchical switches and inter-rack cables, and thus reducing hardware investment, as well as maintenance cost. More precisely, to simplify the configuration and control operations, we propose three DCN design rationales: (1) fully-wireless, all inter-rack links are wireless; (2) easy-deployable, it is not necessary to change the existing infrastructure inside data center; (3) plug-and-play, no extra centralized control operations are required. Previous proposals, however, cannot achieve the three rationales simultaneously. To this end, we first use regular VLC links to interconnect racks as a regular grid DCN. To further exploiting the benefits of VLC links, a few random VLC links are carefully introduced to update the wireless grid DCN as a wireless small-world DCN. To avoid the potential interference among VLC links, we deploy VLC transceivers at different height on the top of each rack. In this way, VLC links would not interfere with others at each height level. Moreover, we design a greedy but efficient routing method for any pair of racks using their identifiers as inputs. Comprehensive evaluation results indicate that our WSWDC exhibits good network performance.

Multicast can efficiently reduce the consumption of network resources by jointly serving multiple destinations with a single source node along a Steiner tree. Nowadays many applications employ a given replica system to improve the service quality; hence, each file and its replicas are usually distributed among multiple servers. In this setting, uncertain multicast is proposed as a novel and general model of multicast transfer. That is, a multicast group offers multiple source nodes instead of a single one. As a result, the multicast routing usually forms a forest, consisting of multiple isolated trees. In this paper, we focus on characterizing and constructing the minimum cost forest (D-MCF) for any uncertain multicast, which satisfies the constraint of end-to-end delay, between any pair of source and destination in the resulting forest at the same time. Prior methods for building a minimum cost forest for an uncertain multicast remain inapplicable to this new problem. Accordingly, we first show an observation about the D-MCF problem and formalize it as an Integer Programming model. We then prove that D-MCF is a NP-hard problem and accordingly design two efficient algorithms, the partition algorithm (PA) and the combination algorithm (CA), to approximate the optimal solution. PA first divides uncertain multicast into several deterministic multicast groups and then combines those routing trees for deterministic multicast. In contrast, CA combines each feasible unicast path for each destinations. Analyses and evaluations indicate that our two methods can produce more desired routing forest than prior method regardless of the delay bound. Also, our PA method can achieve better balance between the performance and time consumption than our CA method. The evaluation results show that PA can reduce 49.02% total cost at the cost of incurring extra 12.59% time consumption, significantly outperforming the CA method.

In multi-tenant shared clouds, applications of different tenants compete for the shared network and thus suffer significant unpredictability of performance. The progress is an essential metric to measure the overall data transfer rate of a tenant and to indicate how fast a tenant can complete data transfer. Most previous work of network allocation or schedule focus on achieving the tradeoff among the fairness, performance, and efficiency. They, however, often do not make each tenant achieve noticeable progress. In this paper, we motivate to maximize tenant's progress by using information about the underlying network and traffic patterns of tenants' applications. To illustrate the feasibility of maximizing progress, we develop a network sharing framework for multi-tenant datacenter, by exploiting the benefits of careful placement of tenant's applications. Furthermore, the tenants' progress and network utilization would be further improved without impacting performance isolation, if the bandwidth demand of each application can be rescheduled. Our evaluation results show that our method provides higher tenant progress and better tenant-level performance than HUG.

The topology of data centers changes dynamically due to link malpositions, hardware failures or software crushes. However, many topology enabled protocols or applications must know the current topology of data center precisely, which triggers the topology calibration problem. Topology calibration needs to deduce the different nodes and links between two given topologies effectively. Based on the existing method, deriving the different nodes is relatively simple, since they can be uniquely identified by their IP or MAC addresses. On the contrary, picking the different links from the massive links can be costly. Therefore, we envision a method to locate the different links with respect to the following rationales: 1) efficient, the caused storage cost or communication overhead should be low; 2) without priori knowledge, there is no support information, thus the different links should be decoded inversely. However, the existing strategies based on Bloom filter, Hash table, or Search trees fail to achieve the two rationales simultaneously. Thus, we propose graph filter, a space-efficient data structure to represent and deduce the different links in an invertible manner. To this end, the associated encoding, subtracting and decoding algorithms are proposed. The simulations highlight the strength of graph filter reasonably.

Software-Define Datacenter networks (SDDCs) are constantly changing due to various network update events. A set of involved flows of each update event should be migrated to the feasible paths without congestion. To tackle a single update event, prior methods find and execute a migration sequence so as to transform the initial traffic distribution to the final traffic distribution. However, when handling a queue of multiple update events, the head-of-line blocking problem always appears and considerably lower the efficiency of network update. To tackle this problem, we employ the idea of delay updating which schedules other queued events instead of the blocked head-event, aiming to break the blocking state and provide updating opportunities for other events. We formulate this problem as an optimization problem and propose partial delay updating (PDU) strategy. PDU tackles the queued update events based on their arrival order to preserve the fairness. Moreover, it prefers to just delay those blocked flows, lacking enough bandwidth resources, instead of all flows in the head-event. The evaluation results show that our delay updating strategy achieves 60%–80% reduction in average completion time of update events, compared to FIFO scheduling strategy, in four types of flow size.

Multicast can jointly utilize the network resources when delivering the same content to a set of destinations; hence, it can effectively reduce the consumption of network resources more than individual unicast. The source of a multicast, however, does not need to be in a specific location as long as certain constraints are satisfied. This means the multicast can have uncertain sources, which could reduce the network bandwidth consumption more than a traditional multicast. Meanwhile, a reliable multicast becomes crucial in providing reliable services for many important applications. However, a prior minimal cost forest (MCF) for such a new multicast is not designed to support reliable transmissions. In this paper, we propose a novel reliable multicast routing with uncertain sources named ReMUS. To the best of our knowledge, we are the first to study the reliable multicast under uncertain sources. The goal is to minimize the sum of the transfer cost and the recovery cost, although finding such a ReMUS is very challenging. Thus, we design a sourcebased multicast method to solve this problem by exploiting the flexibility of uncertain sources when no recovery nodes exist in the network. Furthermore, we design a general multicast method to jointly exploit the benefits of uncertain sources and recovery nodes to minimize the total cost of ReMUS. We conduct extensive evaluations based on the real topology of Internet2. The results indicate that our methods can efficiently realize the reliable and bandwidth-efficient multicast with uncertain sources, irrespective of the settings of networks and multicasts.

Summary This paper investigates the selfish load balancing problem in mobile distributed crowdsourcing networks. Conventional methods heavily relied on cooperation among users to achieve balanced resource utilization in a platform‐centric view. In achieving fairly low communication and computational overhead, this work leverages the d‐choice method based on Ball and Bin theory for effective balancing under limited information and the Proportional Allocation scheme for selfish load balancing, maintaining good load balancing property among selfish users. Even with limited information, the balancing performance could be improved significantly. Moreover, theoretical analysis has been presented in convergence property. Extensive evaluations have been made to show that Chance‐Choice outperforms several existing algorithms. Typically, comparing with Proportional Allocation scheme, it could decrease the load gap between the maximum and the minimal in system by 50% to 80% and reduce the overhead complexity from O(n) to O(1) comparing with the Max‐weight Best Response algorithm, where n denotes the number of mobile users in a crowdsourcing system. Copyright © 2017 John Wiley & Sons, Ltd.

Summary Multicast performs better than unicast in delivering the same content from a fixed single source to a set of destinations. Many efforts have been made to optimize such kind of deterministic multicast, such as minimizing the transmission cost of each multicast session. In practice, it is not necessary that the source of each multicast session has to be in a specific location, as long as certain constraints are satisfied. Accordingly, applications usually meet a novel multicast with uncertain sources, ie, uncertain multicast. That is, multiple nodes have the responsibility to act as the root node of a multicast session. Prior proposals have addressed an uncertain multicast by constructing the minimum cost forest. However, it is still unknown how to efficiently share the network resources, when a set of uncertain multicast occupies the network simultaneously. To tackle such a challenging issue, we present the packing problem of uncertain multicasts (MPU) to minimize the total transmission cost, under the constraint of link capacity. We prove that the MPU problem is NP‐hard. An intrinsic solution is constructing the minimum cost forest for each uncertain multicast individually. This method, however, is inefficient and may be infeasible because of the constraint of link capacity. Thus, we design 2 dedicated greedy methods, named priority‐based and adjusting congested link, to approximate the optimal solution. The comprehensive results indicate that both of our 2 methods can find a feasible solution for the MPU problem. Moreover, given a set of uncertain multicasts, the adjusting congested link method can generate a desired transmission structure for each uncertain multicast and achieve the least total cost when packing them.

Set synchronization is an essential job for distributed applications. In many cases, given two sets A and B, applications need to identify those elements that appear in set A but not in set B, and vice versa. Bloom filter, a spaceefficient data structure for representing a set and supporting membership queries, has been employed as a lightweight method to realize set synchronization with a low false positive probability. Unfortunately, bloom filters and their variants can only be applied to simple sets rather than more general multisets, which allow elements to appear multiple times. In this paper, we first examine the potential of addressing the multiset synchronization problem based on two existing variants of the bloom filters: the IBF and the counting bloom filter (CBF). We then design a novel data structure, invertible CBF (ICBF), which represents a multiset using a vector of cells. Each cell contains two fields, id and count, which record the identifiers and number of elements mapped into them, respectively. Given two multisets, based on the encoding results, the ICBF can execute the dedicated subtracting and decoding operations to recognize the different elements and differences in the multiplicities of elements between the two multisets. We conduct comprehensive experiments to evaluate and compare the three dedicated multiset synchronization approaches proposed in this paper. The evaluation results indicate that the ICBF-based approach outperforms the other two approaches in terms of synchronization accuracy, timeconsumption, and communication overhead.

The proliferation of mobile computing has prompted navigation to be one of the most attractive and promising applications. Conventional designs of navigation systems mainly focus on either indoor or outdoor navigation. However, people have a strong need for navigation from a large open indoor environment to an outdoor destination in real life. This article presents IONavi, a joint navigation solution, which can enable passengers to easily deploy indoor-outdoor navigation service for subway transportation systems in a crowdsourcing way. Any self-motivated passenger records and shares individual walking traces from a location inside a subway station to an uncertain outdoor destination within a given range, such as one kilometer. IONavi further extracts navigation traces from shared individual traces, each of which is not necessary to be accurate. A subsequent following user achieves indoor-outdoor navigation services by tracking a recommended navigation trace. Extensive experiments are conducted on a subway transportation system. The experimental results indicate that IONavi exhibits outstanding navigation performance from an uncertain location inside a subway station to an outdoor destination. Although IONavi is to enable indoor-outdoor navigation for subway transportation systems, the basic idea can naturally be extended to joint navigation from other open indoor environments to outdoor environments.

Many data-intensive applications like MapReduce are network-bound in data centers, due to transfer massive amount of flows across successive processing stages. Data flows in such an incast or shuffle transfer are highly correlated and aggregated at the receiver side. Prior work aims to aggregate correlated flows of each transfer, during the transmission phase as early as possible, so as to directly lower down the network traffic. However, many applications do not constrain the flows' endpoints of each transfer as long as certain constraints are satisfied. Such uncertain transfers bring new opportunities and challenges to lower down the network traffic than prior deterministic transfers. In this paper, we focus on aggregating an uncertain incast transfer and minimizing the amount of caused network traffic. Prior approaches, relying on deterministic incast transfers, remain inapplicable. This paper makes the first step towards the study of aggregating uncertain incast transfer. We propose efficient approaches from two aspects, i.e., the initialization of uncertain senders and the incast tree building. We first design two initialization methods to pick the best deterministic senders for an uncertain incast transfer, so as to form the least number of disjoint sender groups. Thus, flows from each group would be aggregated as one flow on a common one-hop neighbor, irrespective of the location of a picked receiver. Accordingly, we propose the interstage-based and intrastage-based incast tree building methods to exploit the benefits of our initialization methods. We provide evidence to show that our approach can achieve the benefits of in-network aggregation for any uncertain incast transfer. Moreover, an uncertain incast transfer significantly outperforms any related deterministic one, in terms of the reduced network traffic and the saved network resources.

Recent results have made a promising case for offering oversubscribed wired data center networks (DCN) with extreme costs. Inter-rack wireless networks are drawing intensive attention to augment such wired DCNs with a few wireless links. Inspired by the promise of easy deployment and plug-and-play, we present VLCcube, a novel inter-rack wireless solution that extends the design of wireless DCN into three further dimensions: (1) all inter-rack links are wireless; (2) there is no imposition of any infrastructure-level alteration on wired production data centers; and (3) it should be plug-and-play, without any need of additional mechanical or electronic control operations. This vision, if realized, will lead to increased flexibility, reduced reconstructing cost, simplified configuration and usage, and outstanding compatibility with existing wired DCNs. Previous proposals, however, are opposed to the last two design rationales. To achieve this vision, the proposed VLCcube augments Fat-Tree, a representative DCN in production data centers, by organizing all racks into a wireless Torus structure via the emerging visible light links. We further present the topology design, hybrid routing, and flow scheduling schemes for VLCcube. Extensive evaluations indicate that VLCcube outperforms Fat-Tree significantly under the existing ECMP flow scheduling scheme, irrespective of the undergoing traffic pattern. Moreover, the performance of VLCcube can be significantly promoted by our congestion-aware flow scheduling scheme. More precisely, compared to ECMP, our flow scheduling scheme makes VLCcube achieve$\times 1.50$throughput under batched flows,$\mathrm{\times}2.21$and$\times 2.59$throughput under two different kinds of online flows.

Multicast is designed to jointly deliver content from a single source to a set of destinations. It can efficiently save the bandwidth consumption and reduce the load on the source. The appearance of SDN provides opportunities to deploy flexible protocols, including multicast and its variants. However, in many important applications, it is not necessary that the source of a multicast transfer has to be in specific location as long as certain constraints are satisfied. Such facts bring a novel multicast with uncertain sources, abbreviated as uncertain multicast. It brings new opportunities and challenges to reduce the bandwidth consumption. In this paper, we focus on the uncertain multicast and construct a forest with the minimum cost (MCF), to enable that each destination reaches to one and only one source. Prior approaches, relying on traditional multicast, remain inapplicable to the MCF problem. Therefore, we propose two (2+ε)-approximation methods, named P-MCF and E-MCF, which can be deployed in SDN controllers. We conduct experiments on our SDN testbed together with large-scale simulations under the random SDN network. All manifest that our MCF approach always occupies less network links and incurs less network cost for an uncertain multicast than the traditional Steiner minimum tree (SMT) of any related multicast, irrespective of the used network topology and the setting of multicast transmissions.

In data centers, a lot of cluster computing applications follow a coflow pattern. On the other hand, network function virtualization (NFV) sufficiently improves the performance of the data center network. However, coflows encounter extremely different processing delays under diverse network functions. Traditional coflow scheduling schemes become insufficient in this situation. Based on the observation that the benefit of coflows is closely related to the data rates of flows, we propose DRGC (Data Rate Guarantee for Coflow) to guarantee the data rate requirements of coflows in the NFV environment. We prioritize the scheduling sequence of coflows, precisely allocate data rates for individual flows, and design an efficient scheduling algorithm. DRGC maintains the desired data rates of coflows with higher priorities at middleboxes and leaves more scheduling opportunities to the ones with lower priorities. In the large-scale trace-driven experiment, DRGC efficiently guarantees the data rate requirements of coflows and supports more 15% workload, compared with other scheduling schemes.

Data sharing among multiple sampling tasks significantly reduces energy consumption and communication cost in low-power wireless sensor networks (WSNs). Conventional proposals have already scheduled the discrete point sampling tasks to decrease the amount of sampled data. However, less effort has been expended for applications that generate continuous interval sampling tasks. Moreover, most pioneering work limits its view to schedule sampling intervals of tasks on a single sensor node and neglects the process of task allocation in WSNs. Therefore, the gained efforts in prior work cannot benefit a large-scale WSN because the performance of a scheduling method is sensitive to the strategy of task allocation. Broadening the scope to an entire network, this article is the first work to maximize data sharing among continuous interval sampling tasks by jointly optimizing task allocation and scheduling of sampling intervals in WSNs. First, we formalize the joint optimization problem and prove it NP-hard. Second, we present the COMBINE operation, which is the crucial ingredient of our solution. COMBINE is a 2-factor approximate algorithm for maximizing data sharing among overlapping tasks. Furthermore, our heuristic named CATS is proposed. CATS is 2-factor approximate algorithm for jointly allocating tasks and scheduling sampling intervals so as to maximize data sharing in the entire network. Extensive empirical study is conducted on a testbed of 50 sensor nodes to evaluate the effectiveness of our methods. In addition, the scalability of our methods is verified by utilizing TOSSIM, a widely used simulation tool. The experimental results indicate that our methods successfully reduce the volume of sampled data and decrease energy consumption significantly.

The proliferation of mobile computing has prompted navigation to be one of the most attractive and promising applications. Conventional designs of navigation systems mainly focus either indoor or outdoor navigation. However, people have a strong need for navigation from a large open indoor environment to an outdoor destination in real life. In this poster, we present a joint navigation system, named ioNavi. It can enable passengers to easily deploy indoor-outdoor navigation service for subway transportation systems in a crowdsourcing way, without comprehensive indoor localization systems. Any self-motivated passenger records and shares its individual walking trace and associated rich set of sensor readings, from a location inside a subway station to an uncertain outdoor destination within a given range, such as one kilometer. ioNavi further extracts navigation traces from shared individual traces, each of which is not necessary to be accurate and useful. A subsequent following user achieves indoor-outdoor navigation services by tracking a recommended navigation trace.

Summary Large‐scale online services and distributed execution engines (i.e., MapReduce and Dryad) generate large volumes of traffic in data center networks. As a consequence, significant congestion can occur in the data center network. To the best of our knowledge, most existing approaches either focus on local congestion‐aware mechanisms, which have only a poor ability to handle asymmetry or use explicit congestion notification packets, which are difficult to implement directly in switch hardware. These methods are insufficient to solve the congestion problem. In this paper, we focus on a congestion‐free routing strategy, resorting to the global view of the data center network in a software‐defined networking controller. Specifically, a timeslot allocation was first conducted for the coming packets, and then the corresponding routing paths were computed for each packet. In view of the efficiency, the timeslot allocation algorithm follows a heuristic pattern, and the path selection is modeled as a bin‐packing problem. Simulation results showed that the congestion‐free routing strategy proposed here performs well in throughput, queuing, and end‐to‐end round‐trip time. Copyright © 2015 John Wiley & Sons, Ltd.

Large-scale data centers are the key infrastructures for hosting and running a variety of applications. Besides traditional L2/L3 devices, middleboxes are widely deployed in data centers and perform many important functions, e.g., the intrusion detection and firewall. Middleboxes are equipped with multiple kinds of resources, such as CPU and memory. Data flows undergoing different functions have heterogeneous processing time requirements on diverse resources. Researchers are in a dilemma as to how to provide fair service for flows and efficiently utilize those scarce resources. To address this problem, we propose a novel packet scheduling method, active time fairness queuing (ATFQ), for multi-resource environments. Prior packet scheduling methods usually focus on pursuing the fairness among flows, resulting in enormous waste of those scarce resources. ATFQ overcomes this essentially by redefining the fairness and can maximize the resource utilization with the guarantee of fairness. We conduct extensive simulations to evaluate the performance of ATFQ. The evaluation results demonstrate that flows get better service in many aspects under ATFQ. Meanwhile, the resource utilization rises up by about 10% than the traditional DRFQ, which is one of the mainstream involved methods.

Distributed computing systems like MapReduce in data centers transfer massive amount of data across successive processing stages. Such shuffle transfers contribute most of the network traffic and make the network bandwidth become a bottleneck. In many commonly used workloads, data flows in such a transfer are highly correlated and aggregated at the receiver side. To lower down the network traffic and efficiently use the available network bandwidth, we propose to push the aggregation computation into the network and parallelize the shuffle and reduce phases. In this paper, we first examine the gain and feasibility of the in-network aggregation with BCube, a novel server-centric networking structure for future data centers. To exploit such a gain, we model the in-network aggregation problem that is NP-hard in BCube. We propose two approximate methods for building the efficient IRS-based incast aggregation tree and SRS-based shuffle aggregation subgraph, solely based on the labels of their members and the data center topology. We further design scalable forwarding schemes based on Bloom filters to implement in-network aggregation over massive concurrent shuffle transfers. Based on a prototype and large-scale simulations, we demonstrate that our approaches can significantly decrease the amount of network traffic and save the data center resources. Our approaches for BCube can be adapted to other servercentric network structures for future data centers after minimal modifications.

Localization is an enabling technique for many sensor network applications. Real-world deployments demonstrate that, in practice, a network is not always entirely localizable, leaving a certain number of theoretically nonlocalizable nodes. Previous studies mainly focus on how to tune network settings to make a network localizable. However, the existing methods are considered to be coarse-grained, since they equally deal with localizable and nonlocalizable nodes. Ignoring localizability induces unnecessary adjustments and accompanying costs. In this study, we propose a fine-grained approach, localizability-aided localization (LAL), which basically consists of three phases: node localizability testing, structure analysis, and network adjustment. LAL triggers a single round adjustment, after which some popular localization methods can be successfully carried out. Being aware of node localizability, all network adjustments made by LAL are purposefully selected. Experiment and simulation results show that LAL effectively guides the adjustment while makes it efficient in terms of the number of added edges and affected nodes.

Gradient-based routing using Bloom filters is an effective mechanism to enable data-centric queries in multihop networks. A node compressively describes its data items as a Bloom filter, which is then diffused away to the other nodes with information decay. The Bloom filters form an information potential that eventually navigates queries to the source node by ascending the potential field. The existing designs of Bloom filters, however, have critical limitations with respect to the feasibility of gradient-based routing. The compressed routing entries appear to be noisy. Noise in unrelated routing entries is very likely to equal to even outweigh information in right routing entries, thus blinding a query to its desired destination. This work addresses the root cause of the mismatch between the ideal and the practical performance of gradient-based routing using Bloom filters. We first investigate the impact of decaying model on the effectiveness of routing entries, and then evaluate the negative impact of noise on routing decisions. Based on such analytical results, we derive the necessary and sufficient condition of feasible gradient-based routing using Bloom filters. Accordingly, we propose a receiver-oriented design of Bloom filters, called Wader, which satisfies the necessary and sufficient condition. The evaluation results demonstrate that Wader guarantees the correctness and efficiency of gradient-based routing with high probability.

Network has been widely reported as a bottleneck of data center applications. However, current researches of congestion control are unaware of multiple resources consuming and decrease all flows when congestion, ignoring some involved flows may not be the faults. In this paper, we propose a novel multi-resources aware congestion control framework MRTCP to provide a fine-grain control on flows when congestions appear. MRTCP exploits a multi-tuple vector model to measure multi-resources provision and consumption, and develops a novel metric RB (Resource Balance) to denote the heterogeneous amounts of resources employed by each flow. It analyzes which resources are being the bottlenecks that lead to congestions, calculates the responsibility of each flow to this congestion, and then adjusts their sending rates respectively. Our experiment results demonstrate that MRTCP is able to optimize network multi-resources utilization and improve network throughput without adding obvious packets delays.

A fundamental goal of data center networking is to efficiently interconnect a large number of servers with the low equipment cost. Several server-centric network structures for data centers have been proposed. They, however, are not truly expandable and suffer a low degree of regularity and symmetry. Inspired by the commodity servers in today's data centers that come with dual port, we consider how to build expandable and cost-effective structures without expensive high-end switches and additional hardware on servers except the two NIC ports. In this paper, two such network structures, called HCN and BCN, are designed, both of which are of server degree 2. We also develop the low overhead and robust routing mechanisms for HCN and BCN. Although the server degree is only 2, HCN can be expanded very easily to encompass hundreds of thousands servers with the low diameter and high bisection width. Additionally, HCN offers a high degree of regularity, scalability, and symmetry, which conform to the modular designs of data centers. BCN is the largest known network structure for data centers with the server degree 2 and network diameter 7. Furthermore, BCN has many attractive features, including the low diameter, high bisection width, large number of node-disjoint paths for the one-to-one traffic, and good fault-tolerant ability. Mathematical analysis and comprehensive simulations show that HCN and BCN possess excellent topological properties and are viable network structures for data centers.

In this paper, we study the set reconciliation problem, in which each member of a node pair has a set of objects and seeks to deliver its unique objects to the other member. How could each node compute the set difference, however, is challenging in the set reconciliation problem. To address such an issue, we propose a lightweight but efficient method that only requires the pair of nodes to represent objects using a counting Bloom filter (CBF) of size $(O(d))$ and exchange with each other, where $(d)$ denotes the total size of the set differences. A receiving node then subtracts the received CBF from its local one via minus operation proposed in this paper. The resultant CBF can approximately represent the union of the set differences and thus the set difference to each node can be identified after querying the resultant CBF. In this paper, we propose a novel estimator through which each node can accurately estimate not only the value of $(d)$ but also the size of the set difference to each node. Such an estimation result can be used to optimize the parameter setting of the CBF to achieve less false positives and false negatives. Comprehensive analysis and evaluation demonstrates that our method is more efficient than prior BF-based methods in terms of achieving the same accuracy with less communication cost. Moreover, our reconciliating method needs no prior context logs and it is very useful in networking and distributed applications.

Multiple-Input-Multiple-Output (MIMO) has great potential for enhancing the throughput of multihop wireless networks via spatial multiplexing or spatial reuse. Spatial reuse with Stream Control (SC) provides a considerable improvement of the network throughput over spatial multiplexing. The gain of spatial reuse, however, is still not fully exploited. There exist large numbers of additional data streams, which could be transmitted concurrently with those data streams scheduled by stream control at certain time slots and vicinities. In this paper, we address the issue of MIMO link scheduling to maximize the gain of spatial reuse and thus network throughput. We propose a Receiver-Oriented Interference Suppression model (ROIS), based on which we design both centralized and distributed link scheduling algorithms to fully exploit the gain of spatial reuse in multihop MIMO networks. Further, we address the traffic-aware link scheduling problem by injecting nonuniform traffic load into the network. Through theoretical analysis and comprehensive performance evaluation, we achieve the following results: 1) link scheduling based on ROIS achieves significant higher network throughput than that based on stream control, with any interference range, number of antennas, and average hop length of data flows. 2) The traffic-aware scheduling is enticingly complementary to the link scheduling based on ROIS model. Accordingly, the two scheduling schemes can be combined to further enhance the network throughput.

Recent work has demonstrated that path diversity is an effective way to improve the end-to-end performance of network applications. For every node pair in a full-mesh network with $(n)$ nodes, this paper presents a family of new approaches that efficiently identify an acceptable indirect path that has a similar to or even better performance than the direct path, hence considerably scaling the network at the cost of low per-node traffic overhead. In prior techniques, every node frequently incurs $(O(n^{1.5}))$ traffic overhead to probe the links from itself to all other nodes and to broadcast its probing results to a small set of nodes. In contrast, in our approaches, each node measures its links to only $(O(\sqrt{n}))$ other nodes and transmits the measuring results to $(O(\sqrt{n}))$ other nodes, where the two node sets of size $(O(\sqrt{n}))$ are determined by the partial sampling schemes presented in this paper. Mathematical analyses and trace-driven simulations show that our approaches dramatically reduce the per-node traffic overhead to $(O (n))$ while maintaining an acceptable backup path for each node pair with high probability. More precisely, our approaches, which are based on enhanced and rotational partial sampling schemes, are capable of increasing said probability to about 65 and 85 percent, respectively. For many network applications, this is sufficiently high such that the increased scalability outweighs such a drawback. In addition, it is not desirable to identify an outstanding backup path for every node pair in reality, due to the variable link quality.

Multichannel accessing is a basic and important function in wireless sensor networks, where intelligent and low-cost methods are needed for energy-efficient spectrum utilization. Unfortunately, for energy constrained nodes, methods from cognitive radio technologies are not applicable in WSN multichannel systems due to computation and communication overhead, as well as extremely large energy consumptions. In this work, we propose a spectrum learning and utilizing paradigm, where sensor nodes can sense, probe, access and switch among channels automatically without prior knowledge. Under this basic and important learning method, we present a two-stage learning and utilization algorithm, which constitutes of two interleaving parts: `transmitting while learning' and `learning while transmitting'. Building these two parts is a non-trivial work, which need efficient channel learning and utilizing scheme working together seamlessly. In the first `transmitting while learning' stage, we propose the `non-call-back' policy and leverage the Lagrangian method for the additional energy cost considerations. Under this heuristic policy, an improved version for the traditional Gittins Index model is provided. After that, the heuristic algorithm is proved `2-approximate' to the optimal result. Furthermore, leveraging the channel correlations, the learning complexity is reduced from O(T) stages to O(log T) stages, where T is the number of time slots for channel learning. Secondly, we make a structural analysis on the `learning while transmitting' stage, leveraging the 2-dimensional optimal stopping theory. Notably, we use the a 16-node TelosB sensor network and an 8-node USRP network for performance evaluation. The USRP nodes are playing as interfering and monitoring nodes for controllable network states design, making network performance evaluation convincible. The proposed algorithm is designed in real implementations with experimental results, showing the efficiency of the proposed scheme.

SUMMARY Several novel data center network structures have been proposed to improve the topological properties of data centers. A common characteristic of these structures is that they are designed for supporting general applications and services. Consequently, these structures do not match well with the specific requirements of some dedicated applications. In this paper, we propose a hyper‐fat‐tree network (HFN): a novel data center structure for MapReduce, a well‐known distributed data processing application. HFN possesses the advanced characteristics of BCube as well as fat‐tree structures and naturally supports MapReduce. We then address several challenging issues that face HFN in supporting MapReduce. Mathematical analysis and comprehensive evaluation show that HFN possesses excellent properties and is indeed a viable structure for MapReduce in practice. Copyright © 2011 John Wiley & Sons, Ltd.

As the energy consumption of multi-core systems becomes increasingly prominent, it's a challenge to design an energy-efficient real-time scheduling algorithm in multi-core systems for reducing the system energy consumption while guaranteeing the feasibility of real-time tasks. In this paper, we focus on multi-core processors, with the global Dynamic Voltage Frequency Scaling (DVFS) and Dynamic Power Management (DPM) technologies. In this setting, we propose an energy-efficient real-time scheduling algorithm, the Time Local remaining execution plane based Dynamic Voltage Frequency Scaling (TL-DVFS). TL-DVFS utilizes the concept of Time Local remaining execution (TL) plane to dynamically scale the voltage and frequency of a processor at the initial time of each TL plane as well as at the release time of a sporadic task in each TL plane. Consequently, TL-DVFS can obtain a reasonable tradeoff between the real-time constraint and the energy-saving while realizing the optimal feasibility of sporadic tasks. Mathematical analysis and extensive simulations demonstrate that TL-DVFS always saves more energy than existing algorithms, especially in the case of high workloads, and guarantees the optimal feasibility of sporadic tasks at the same time.

In order to improve scalability and to reduce the maintenance overhead for structured peer-to-peer (P2P) networks, researchers have proposed architectures based on several interconnection networks with a fixed-degree and a logarithmical diameter. Among existing fixed-degree interconnection networks, the Kautz digraph has many distinctive topological properties compared to others. It, however, requires that the number of peers have the some given values, determined by peer degree and network diameter. In practice, we cannot guarantee how many peers will join a P2P network at a given time, since a P2P network is typically dynamic with peers frequently entering and leaving. To address such an issue, we propose the balanced Kautz tree and Kautz ring structures. We further design a novel structured P2P system, called BAKE, based on the two structures that has the logarithmical diameter and constant degree, even the number of peers is an arbitrary value. By keeping a total ordering of peers and employing a robust locality-preserved resource placement strategy, resources that are similar in a single or multidimensional attributes space are stored on the same peer or neighboring peers. Through analysis and simulation, we show that BAKE achieves the optimal diameter and as good a connectivity as the Kautz digraph does (almost achieves the Moore bound), and supports the exact as well as the range queries efficiently. Indeed, the structures of balanced Kautz tree and Kautz ring we propose can also be applied to other interconnection networks after minimal modifications, for example, the de Bruijn digraph.

As the energy consumption of embedded multiprocessor systems becomes increasingly prominent, the real-time energy-efficient scheduling in multiprocessor systems becomes an urgent problem to reduce the system energy consumption while meeting real-time constraints. For a multiprocessor with independent DVFS and DPM at each processor, this paper proposes an energy-efficient real-time scheduling algorithm named LRE-DVFS-EACH, based on LRE-TL which is an optimal real-time scheduling algorithm for sporadic tasks. LRE-DVFS-EACH utilizes the concept of TL plane and the idea of fluid scheduling to dynamically scale the voltage and frequency of processors at the initial time of each TL plane as well as the release time of a sporadic task in each TL plane. Consequently, LRE-DVFS-EACH can obtain a reasonable tradeoff between the real-time constraints and the energy saving. LRE-DVFS-EACH is also adaptive to the change of workload caused by the dynamic release of sporadic tasks, which can obtain more energy savings. The experimental results show that compared with existing algorithms, LRE-DVFS-EACH can not only guarantee the optimal feasibility of sporadic tasks, but also achieve more energy savings in all cases, especially in the case of high workloads.

Localization is an enabling technique for many sensor and ad-hoc network applications. Real-world deployments demonstrate that, in practice, a network is not always entirely localizable, leaving a certain number of theoretically non-localizable nodes. Previous studies mainly focus on how to tune network settings to make a network localizable; however, they are considered to be coarse-grained, since they equally deal with localizable and non-localizable nodes. Ignoring localizability induces unnecessary adjustments and accompanying costs. In this study, we propose a fine-grained approach, Localizability-aided Localization (LAL), which basically consists of three phases: node localizability testing, component tree construction, and network adjustment. LAL triggers a single round adjustment, after which some popular localization methods can be successfully carried out. Being aware of node localizability, all adjustments made by LAL are purposefully selected. Simulation results show that LAL effectively guides the adjustment.

A fundamental challenge in data centers is how to design networking structures for efficiently interconnecting a large number of servers. Several server-centric structures have been proposed, but are not truly expansible and suffer low degree of regularity and symmetry. To address this issue, we propose two novel structures called HCN and BCN, which utilize hierarchical compound graphs to interconnect large population of servers each with two ports only. They own two topological advantages, i.e., the expansibility and equal degree. In addition, HCN offers high degree of regularity, scalability and symmetry, which well conform to the modular design of data centers. Moreover, a BCN of level one in each dimension involves more servers than FiConn with server degree 2 and diameter 7, and is large enough for a single data center. Mathematical analysis and comprehensive simulations show that BCN possesses excellent topology properties and is a viable network structure for data centers.

We consider deterministic feasibility and time complexity of two fundamental tasks in distributed computing: consensus and mutual exclusion. Processes have different labels and communicate through a multiple access channel. The adversary wakes up some processes in possibly different rounds. In any round, every awake process either listens or transmits. The message of a process i is heard by all other awake processes, if i is the only process to transmit in a given round. If more than one process transmits simultaneously, there is a collision and no message is heard. We consider three characteristics that may or may not exist in the channel: collision detection (listening processes can distinguish collision from silence), the availability of a global clock showing the round number, and the knowledge of the number n of all processes. If none of the above three characteristics is available in the channel, we prove that consensus and mutual exclusion are infeasible; if at least one of them is available, both tasks are feasible, and we study their time complexity. Collision detection is shown to cause an exponential gap in complexity: if it is available, both tasks can be performed in time logarithmic in n, which is optimal, and without collision detection both tasks require linear time. We then investigate both consensus and mutual exclusion in the absence of collision detection, but under alternative presence of the two other features. With global clock, we give an algorithm whose time complexity linearly depends on n and on the wake-up time, and an algorithm whose complexity does not depend on the wake-up time and differs from the linear lower bound only by a factor O(\log^2 n). If n is known, we also show an algorithm whose complexity differs from the linear lower bound only by a factor O(\log^2 n).

Target tracking plays a critical role in the applications of wireless sensor networks. In this paper, we propose a target tracking algorithm based on Bayesian estimation, the key steps involved in the algorithm include target detection based on a probabilistic model, preliminary localization using the two-stage target locating algorithm, further prediction adopting Bayesian estimation. Simulation results show that our simple and effective algorithm can accurately track the target and save much energy during the tracking process of a moving target.

With an increasing use of services sustaining the resources which people need has become more important. In this paper, we propose an effective reservation method, called “BPSR” (Business Process Service Reservation), which aims for the process reservation which to the best of our knowledge has not been studied before. In particular we address for major jobs: service differentiation; service reservation; process reservation and QoS Control. We also describe a flexible policy-based reservation method which aims to increase the success rate of reservation and utilization of service resources. Experimental analysis shows that the BPSR reservation system achieves better results than other reservation methods.

Bloom filter is effective, space-efficient data structure for concisely representing a data set and supporting approximate membership queries. Traditionally, researchers often believe that it is possible that a Bloom filter returns a false positive, but it will never return a false negative under well-behaved operations. By investigating the mainstream variants, however, we observe that a Bloom filter does return false negatives in many scenarios. In this work, we show that the undetectable incorrect deletion of false positive items and detectable incorrect deletion of multiaddress items are two general causes of false negative in a Bloom filter. We then measure the potential and exposed false negatives theoretically and practically. Inspired by the fact that the potential false negatives are usually not fully exposed, we propose a novel Bloom filter scheme, which increases the ratio of bits set to a value larger than one without decreasing the ratio of bits set to zero. Mathematical analysis and comprehensive experiments show that this design can reduce the number of exposed false negatives as well as decrease the likelihood of false positives. To the best of our knowledge, this is the first work dealing with both the false positive and false negative problems of Bloom filter systematically when supporting standard usages of item insertion, query, and deletion operations.

A Bloom filter is an effective, space-efficient data structure for concisely representing a set, and supporting approximate membership queries. Traditionally, the Bloom filter and its variants just focus on how to represent a static set and decrease the false positive probability to a sufficiently low level. By investigating mainstream applications based on the Bloom filter, we reveal that dynamic data sets are more common and important than static sets. However, existing variants of the Bloom filter cannot support dynamic data sets well. To address this issue, we propose dynamic Bloom filters to represent dynamic sets, as well as static sets and design necessary item insertion, membership query, item deletion, and filter union algorithms. The dynamic Bloom filter can control the false positive probability at a low level by expanding its capacity as the set cardinality increases. Through comprehensive mathematical analysis, we show that the dynamic Bloom filter uses less expected memory than the Bloom filter when representing dynamic sets with an upper bound on set cardinality, and also that the dynamic Bloom filter is more stable than the Bloom filter due to infrequent reconstruction when addressing dynamic sets without an upper bound on set cardinality. Moreover, the analysis results hold in stand-alone applications, as well as distributed applications.

There is a growing need for enabling reprogramming in a working sensor network. We prefer to meet the requirements remotely instead of collecting all deployed sensors. Identifying the version difference of data items, having the same key, could significantly reduce the communication overhead, because only those out-of-date items should be updated at each sensor. Previous protocols need to exchange multiple messages to identify a version difference between two items with the same key. In this paper, we propose a reliable and energy efficient data dissemination protocol (BDP) with less propagation delay. BDP uses Bloom filters to identify a version difference between two items with the same key, and find the new one between two items having the same key but different versions. Through comprehensive simulations, we show that BDP outperforms previous work in terms of energy cost and propagation delay of updating new items with high reliability

In order to improve scalability and reduce maintenance overhead for structured peer-to-peer systems, researchers design optimal architectures with constant degree and logarithmical diameter. The expected topologies, however, require the number of peers to be some given values determined by the average degree and the diameter. Hence, existing designs fail to address the issue due to the fact that (1) we cannot guarantee how many peers to join a P2P system at a given time, and (2) a P2P system is typically dynamic with peers frequently coming and leaving. In this work, we propose BAKE scheme based on balanced Kautz tree structure withlogdnin diameter and constant degree even the number of peers is an arbitrary value. Resources that are similar in single or multi-dimensional attributes space are stored on a same peer or neighboring peers. Through formal analysis and comprehensive simulations, we show that BAKE achieves optimal diameter and good connectivity as the Kautz digraph does. Indeed, the concepts of balanced Kautz tree introduced in this work can also be extended and applied to other interconnection networks after minimal modifications, for example, de Bruijn digraph.

The topological properties of peer-to-peer overlay networks are critical factors that dominate the performance of these systems. Several non-constant and constant degree interconnection networks have been used as topologies of many peer-to-peer networks. One of these has many desirable properties: the Kautz digraph. Unlike interconnection networks, peer-to-peer networks need a topology with an arbitrary size and degree, but the complete Kautz digraph does not possess these properties. In this paper, we propose Moore: the first effective and practical peer-to-peer network based on the incomplete Kautz digraph withO(logdN) diameter and constant degree under a dynamic environment. The diameter and average routing path length are [logd(N) - logd(1 + 1/d)] and logdN, respectively, and are shorter than that of CAN, butterfly, and cube-connected-cycle. They are close to that of complete de Bruijn and Kautz digraphs. The message cost of node joining and departing operations are at most 2.5dlogdNand (2.5d+ 1) logdN, and onlydand 2dnodes need to update their routing tables. Moore can achieve optimal diameter, high performance, good connectivity and low congestion evaluated by formal proofs and simulations.

Abstract — A bloom filter is a simple, space-efficient, randomized data structure for concisely representing a static data set, in order to support approximate membership queries. It has great potential for distributed applications where systems need to share information about what resources they have. The space efficiency is achieved at the cost of a small probability of false positive in membership queries. However, for many applications the space savings and short locating time consistently outweigh this drawback. In this paper, we introduce dynamic bloom filters (DBF) to support concise representation and approximate membership queries of dynamic sets, and study the false positive probability and union algebra operations. We prove that DBF can control the false positive probability at a low level by adjusting the number of standard bloom filters used according to the actual size of current dynamic set. The space complexity is also acceptable if the actual size of dynamic set does not deviate too much from the predefined threshold. Furthermore, we present multidimension dynamic bloom filters (MDDBF) to support concise representation and approximate membership queries of dynamic sets in multiple attribute dimensions, and study the false positive probability and union algebra operations through mathematic analysis and experimentation. We also explore the optimization approach and three network applications of bloom filters, namely bloom joins, informed search, and global index implementation. Our simulation shows that informed search based on bloom filters can obtain higher recall and success rate of query than the blind search protocol.

As the increasing development of application technology and infrastructure, many kinds of application and resources can be encapsulated as Web service and its variations, and service-oriented computing become research hot. But, we believe service-oriented computing should establish on virtualized service rather than concrete service instance directly. In this paper, we present formalized model of virtualized service and service instance, and define the concept of service virtualization. Then, we propose the implementation solution of virtualized service-oriented application from perspective of global and local instantiation process.