Network traffic measurement is indispensable for many network management tasks. Time-series traffic pattern detection extends the benefits of traditional single-period flow measurement by revealing dynamic flow behaviors, but also yields higher complexity. When multiple patterns must be monitored simultaneously, building a separate sketch for each pattern is prohibitive since programmable switches typically allow only one resource-intensive sketch. In this paper, we propose PatternSketch, which enables general and dynamically reconfigurable time-series pattern detection within a single sketch. PatternSketch unifies the detection of diverse patterns with a Pattern Automaton and decomposes the pattern detection process into two phases in the data plane, while allowing operators to reconfigure the active set of monitoring patterns at runtime without taking the switch offline. Our implementation on an Intel Tofino switch demonstrates that PatternSketch can operate at line rate, detecting multiple patterns concurrently while using only tens of kilobytes of SRAM. This significantly reduces both computational and storage resource consumption compared to deploying multiple, pattern-specific sketches. Evaluations on four real-world datasets show that the hardware version of PatternSketch maintains over 90% F1 scores while simultaneously detecting six time-series patterns (three representative and three newly proposed) with as little as 200KB of memory.

Key-value data streams are widely spread in modern information systems. This paper delves into the inner features of individual keys and introduces a new measurement task called Core Composition Estimation for Frequent Keys (CCEFK). CCEFK aims to identify the most significant values associated with an item's key, which can be fully applied to a wide range of real-world scenarios. To address this quite challenging, multidimensional CCEFK mission, we propose PieSketch, a novel sketch-based algorithm that supports three types of queries related to CCEFK. PieSketch employs a three-level data structure and a two-staged insertion algorithm to process the keys and values of data streams separately and sequentially, achieving fine-grained data summarization for both. Through some rigorous theoretical analysis, we prove that PieSketch can achieve a good performance guarantee with low time and space complexity. We further present three optimizations to enhance PieSketch comprehensively: Sector Morphing addresses the diversity in value distribution among different keys with a dynamically adjusting strategy, significantly improving memory efficiency; Early Filtration ensures PieSketch's stability in extreme conditions; SIMD Acceleration speeds up PieSketch for data processing. We finally conducted extensive experiments on four real-world datasets to evaluate PieSketch's excellent performance. The results show that PieSketch significantly outperforms state-of-the-art techniques, achieving$23.67\times$,$88.41\times$, and$15.80\times$better accuracy on three types of queries, respectively, and demonstrating 1.84 times higher insertion throughput on average. All our codes are publicly available on GitHubhttps://github.com/NeoAnderson-20/PieSketch-source.

Identifying the hierarchical heavy hitters (HHHs), i.e., the frequent aggregated flows based on common IP prefixes, is a vital task in network traffic measurement and security. Existing methods typically employ dynamic trie structures to track numerous prefixes or utilize multiple separate sketch instances, one for each hierarchical level, to capture HHHs across different levels, while both approaches suffer from low memory efficiency and limited compatibility with programmable switches. In this paper, we introduce two novel HHH detection solutions, respectively, Hierarchical Heavy Detector (HHD) and the Compressed Hierarchical Heavy Detector (CHHD), to achieve high memory efficiency and enhanced hardware compatibility. The key idea of HHD is to design a shared bucket array structure to identify and record HHHs from all hierarchical levels, which avoids the memory wastage of maintaining separate sketches to achieve high memory efficiency and allows feasible deployment of both byte-hierarchy and bit-hierarchy HHH detection on programmable switches using minimal processing stage resources. Additionally, HHD utilizes a sampling-based update strategy to effectively balance packet processing speed and detection accuracy. Furthermore, we present the CHHD, which enhances HHH detection in bit hierarchies through a more compact cell structure, which allows for compressing several ancestor and descendant prefixes within a single cell, further boosting memory efficiency and accuracy. We have implemented HHD and CHHD on a P4-based programmable switch with limited switch resources. Experimental results based on real-world Internet traces demonstrate that HHD and CHHD outperform the state-of-the-art by achieving up to 56 percentage points higher detection precision and 2.6× higher throughput.

Current web applications like social networks and video streaming have been generating magnificent traffic volume, along with intensive traffic dynamics, raising challenges to the fundamental infrastructure of web, i.e., datacenters. However, the traditional electric-based architectures are behind the curve due to the fixed topology and the demand-oblivious nature, failing to guarantee the performance of web applications. Motivated by the new traffic pattern, the reconfigurable technologies, like optical circuit switches (OCSes), are a promising choice to further improve throughput by dynamically adjusting connections when facing traffic dynamics. Currently, static and dynamic updating are two main methods for reconfiguring OCSes. Though static methods can acquire a solution with approximation ratio, it takes long running time and recourse. As comparison, dynamic updating can efficiently acquire a solution, yet existing solutions may degrade along with updates. This paper presents Talbot to further improve throughput with both approximation guarantee and low updating time/recourse. We formulate the throughput maximization problem as a fully dynamic k-weight limited matching problem which is$\mathcal{N} \mathcal{P}$-hard, and we further propose an approximation algorithm based on level and lazy update scheme. To evaluate Talbot, simulations are conducted with both real-world and synthetic datasets. Compared with state-of-the-art works, we show the superior performance of Talbot.

Approximate membership query data structures (i.e., filters) have ubiquitous applications in database and data mining. Cuckoo filters are emerging as the alternative to Bloom filters because they support deletions and usually have higher operation throughput and space efficiency. However, their designs are confined to a single-threaded execution paradigm and consequently cannot fully exploit the parallel processing capabilities of modern hardware. This paper presents PipeFilter, a faster and more space-efficient filter that harnesses pipeline parallelism for superior performance. PipeFilter re-architects the Cuckoo filter by partitioning its data structure into several sub-filters, each providing a candidate position for every item. This allows the filter operations, including insertion, lookup, and deletion, to be naturally distributed across several pipeline stages, each overseeing one of the sub-filters, which can further be implemented through multi-threaded execution or pipeline stages of programmable hardware to achieve significantly higher throughput. Meanwhile, PipeFilter excels for single-threaded execution thanks to a combination of unique design features, includingblock design,path prophet,round robin, andSIMD optimization, such that it achieves superior performance than the SOTAs even when running with a single core. PipeFilter also has a competitive advantage in space utilization because it permits each item to explore more candidate positions. We implement and optimize PipeFilter on four platforms (single-core CPU, multi-core CPU, FPGA, and P4 ASIC). Experimental results demonstrate that PipeFilter surpasses all baseline methods on four platforms. When running with a single core, it showcases a notable 15%$\sim$57% improvement in operation throughput and a high load factor exceeding 99%. When parallel processing on other platforms, PipeFilter achieves 7$\times \sim 800\times$higher throughput than single-threaded execution.

Network traffic measurement is crucial for the effective management of data center networks. Collaborative measurement solutions distribute measurement tasks to switches based on flow-level or packet-level granularity to alleviate the measurement load on each switch. However, flow-level solutions often experience severe imbalances in measurement overhead between switches measuring large or small flows, and face scalability challenges due to the costly optimization of collaborative plans. Additionally, packet-level solutions do not adequately reduce hash collisions in sketches and fail to significantly enhance measurement accuracy. In this article, we present the Lightweight Two-level Collaborative Measurement (LTCM) that synergies flow-level and packet-level strategy to optimize measurement load balancing, reduce overall measurement overhead, and enhance measurement accuracy. We first design a Lightweight Flow-level Measurement (FCM) framework that balances the number of flows measured by each switch, incorporating a novel interval-matching technique that significantly lowers the computational costs of collaborative strategies. Based on FCM, LTCM implements our measurement load balancing strategy selector at ingress switches to detect flows whose number of packets entering the network exceeds a given threshold and evenly distribute their subsequent packets across all switches for measurement. To further improve measurement accuracy and speed, we design a two-layer collaborative sketch that reduces hash collisions between large and small flows. We implement LTCM on a Tofino-based programmable switch. Experimental results based on real Internet traces show that LTCM achieves highly efficient flow-level and packet-level measurement load balancing, improving accuracy by up to 96.6% and throughput by up to 112.79%. All related implementations are open-sourced. 1

Traffic measurement provides essential information for various network services. Burst is a common phenomenon in high-speed network streams, which manifests as a surge in the number of incoming packets in a flow. We propose a new definition named across-period burst, considering the change not in two adjacent time windows but in two groups of windows with time continuity. The across-period burst definition can better capture the continuous changes of flows in high-speed networks. To achieve real-time burst detection with high accuracy and low memory consumption, we propose a novel sketch named BurstDetector, which consists of two stages. Stage 1 excludes those flows that will not become burst flows, while Stage 2 accurately records the information of the potential burst flows and carries out across-period burst detections at the end of every time window. We further propose an optimization called Hierarchical Cell, which can improve the memory utilization of BurstDetector. In addition, we analyze the estimation accuracy and time complexity of BurstDetector. Extensive experiments based on real-world datasets show that our BurstDetector can achieve at least 2.8 times as much detection accuracy and processing throughput as some existing algorithms.

This paper studies a new but important pattern for items in data streams, called promising items. The promising items mean that the frequencies of an item in multiple continuous time windows show an upward trend overall, while a slight decrease in some of these windows is allowed. Many practical applications can benefit from the property of promising items, e.g., detecting potential hot events or news in social networks, preventing network congestion in communication channels, and monitoring latent attacks in computer networks. To accurately find promising items in data streams in real-time under limited memory space, we propose a novel structure named Scout Sketch, which consists of Filter and Finder. Filter is devised based on the Bloom filter to eliminate the ungratified items with less memory overload; Finder records some necessary information about the potential items and detects the promising items at the end of each time window, where we propose some tailor-made detection operations. We also analyze the theoretical performance of Scout Sketch. Finally, we conducted extensive experiments based on four real-world datasets. The experimental results show that the F1 Score and throughput of Scout Sketch are about 2.02 and 5.61 times that of the compared solutions, respectively.

Periodicity and fluctuation are two crucial characteristics of data streams. This paper investigates a novel data stream pattern called periodic spread changer (PSC flow for short), which refers to the heavy change in the spread of a flow occurring with fixed time intervals. Effectively identifying such flows is essential for many real-world applications, such as anomaly detection and network monitoring. To achieve precise real-time detection of these flows under limited memory resources, we propose a novel structure named PSC Sketch. PSC Sketch firstly performs the spread estimation by removing duplicate data items and filters out those non-potential flows with small spreads. During the measurement period, PSC Sketch detects the spread changers, calculates the time intervals between adjacent heavy changes, and reports the top-k periodic spread changers. Extensive experiments based on four real-world datasets demonstrate that, compared to competing algorithms, PSC Sketch achieves an average of 16.80 times lower average absolute error, 44.93% higher accuracy, and 1.83 times higher throughput.

Mobile crowdsensing (MC), an excellent solution to large-scale spatiotemporal data sensing problems, has recently received lots of attention from both industry and academia. In the MC system, any requester can acquire the sensing data for his points of interest (PoIs) by offering some payments to attract a group of mobile users capable of completing these PoI-related sensing tasks. However, the current MC work neglected three vital factors, more or less. First, they assume that these distributed users are mutually independent in MC, ignoring the social effects. Actually, the sensing data collected by one user may be corroborated by others’ sensing data, so-called information corroboration. Second, all rational and selfish users are inclined to gather to perform these tasks due to information corroboration. Meanwhile, they may be strategic about their participation levels to maximize profits. However, more similar sensing data will undoubtedly lower the information value, so any user has a tradeoff between gather and scatter. Third, although mobile users can obtain some payments, privacy issues may still prevent them from participating in MC. In this article, we propose a secure blockchain-assisted socially-aware MC framework by adopting the smart contract technique of Ethereum. For this framework, we further devise a two-stage Stackelberg game model to assist the requester (i.e., the leader in the game) in properly pricing each PoI-related sensing task, so that mobile users (i.e., the followers in the game) can exactly select their tasks and determine their participation levels. To analyze the game equilibrium, we extend the traditional Hessian matrix method to a multidimension case involving the multiuser multitask hyperspace setting. We conduct extensive experiments to prove the equilibrium and effectiveness of the proposed solution. We also implement a prototype and deploy the smart contract to an official Ethereum test network to demonstrate the practicability of the proposed framework.

Data stream processing holds great potential value in lots of practical application scenarios. This paper studies two new but important patterns for items in data streams, called promising and damping items. The promising items mean that the frequencies of an item in multiple continuous time windows show an upward trend overall, while a slight decrease in some of these windows is allowed. In contrast to promising items exhibiting an increasing trend, the definition of damping items indicates a decreasing trend. Many applications can benefit from the property of promising or damping items, e.g., monitoring latent attacks in computer networks, pre-adjusting bandwidth allocation in communication channels, detecting potential hot events/news, or finding topics that gradually lose momentum in social networks. We first introduce how to accurately find promising items in data streams in real-time under limited memory space. To this end, we propose a novel structure named Scout Sketch, which consists of Filter and Finder. Filter is devised based on the Bloom filter to eliminate the ungratified items with less memory overload; Finder records some necessary information about the potential items and detects the promising items at the end of each time window, where we propose some tailor-made detection operations. We then enhance Scout Sketch (called Scout Sketch+) to adaptively detect both types of promising and damping items simultaneously. Finally, we conducted extensive experiments on four real-world datasets, which show that the F1 Score and throughput of Scout Sketch(+) are about 2.02 and 5.61 times that of the compared solutions. All source codes are available at Github (https://github.com/Aoohhh/ScoutSketch).

Cardinality estimation is a fundamental problem with diverse practical applications. HyperLogLog (HLL) has become a standard in practice because it offers good memory efficiency, constant update time, and mergeability. Some recent work achieved better memory efficiency, but typically at the cost of impractical update time or losing mergeability, making them incompatible with applications like network-wide traffic measurement. This work presents SpikeSketch, a better cardinality estimator that reduces memory usage of HLL by 37% without sacrificing other crucial metrics. We adopt a bucket-based data structure to promise constant update time, design a smoothed log4ranking and a spike coding scheme to compress cardinality observables into buckets, and propose a lightweight mergeable lossy compression to balance memory usage, information loss, and mergeability. Then we derive an unbiased estimator for recovering cardinality from the lossy-compressed sketch. Theoretical and empirical results show that SpikeSketch can work as a drop-in replacement for HLL because it achieves a near-optimal MVP (memory-variance-product) of 4.08 (37% smaller than HLL) with constant update time and mergeability. Its memory efficiency even defeats ACPC and HLLL, the state-of-the-art lossless-compressed sketches using linear-time compression to reduce memory usage.

Multi-Armed Bandit (MAB) that solves the sequential decision-making to the prior-unknown settings has been extensively studied and adopted in various applications such as online recommendation, transmission rate allocation, etc. Although some recent work has investigated the multi-agent MAB model, they supposed that agents share their bandit information based on social networks but neglected the incentives and arm-pulling budget for heterogeneous agents. In this paper, we propose a transaction-based multi-agent MAB framework, where agents can trade their bandit experience with each other to improve their total individual rewards. Agents not only face the dilemma between exploitation and exploration, but also decide to post a suitable price for their bandit experience. Meanwhile, as a buyer, the agent accepts another agent whose experience will help her the most, according to the posted price and her risk-tolerance level. The key challenge lies in that the arm-pulling and experience-trading decisions affect each other. To this end, we design the transaction-based upper confidence bound to estimate the prior-unknown rewards of arms, based on which the agents pull arms or trade their experience. We prove the regret bound of the proposed algorithm for each independent agent and conduct extensive experiments to verify the performance of our solution.

Accurate and fast per-flow size traffic measurement is fundamental to some network applications, e.g., load balancing, anomaly detection, traffic engineering, especially in face of the processing and memory constraints of switches. Sketch, a compact data structure, can output high-fidelity approximate perflow statistics. However, most existing sketches such as Count-Min are trapped in the dilemma between a large counting range and memory waste, due to the highly skewed characteristics of traffic size distribution. In this paper, we propose an adaptive counter-splicing-based sketch for per-flow size measurement. Specifically, we first allocate a small number of bits for each counter to handle mouse flows, and then splice several basic counters on the same layer to satisfy the counting range requirement for elephant flows. Extensive experiments based on real-world datasets CAIDA show that our proposed sketch can achieve better estimation performance in per-flow size estimation, flow size distribution, entropy estimation, heavy hitter detection, and heavy change detection, compared to several existing algorithms.

Heavy-hitter detection is a fundamental task in network traffic measurement and security. Existing work faces the dilemma of suffering dynamic and imbalanced traffic characteristics or lowering the detection efficiency and flexibility. In this paper, we propose a flexible sketch called SwitchSketch that embraces dynamic and skewed traffic for efficient and accurate heavy-hitter detection. The key idea of SwitchSketch is allowing the sketch to dynamically switch among different modes and take full use of each bit of the memory. We present an encoding-based switching scheme together with a flexible bucket structure to jointly achieve this goal by using a combination of design features, including variable-length cells, shrunk counters, embedded metadata, and switchable modes. We further implement SwitchSketch on the NetFPGA-1G-CML board. Experimental results based on real Internet traces show that SwitchSketch achieves a high Fβ-Score of threshold-t detection (consistently higher than 0.938) and over 99% precision rate of top-k detection under a tight memory size (e.g., 100KB). Besides, it outperforms the state-of-the-art by reducing the ARE by 30.77%\sim99.96%. All related implementations are open-sourced.

Per-flow traffic measurement in the high-speed network plays an important role in many practical applications. Due to the limited on-chip memory and the mismatch between off-chip memory speed and line rate, sampling-based methods select and forward a part of flow traffic to off-chip memory, which complements sketch-based solutions in estimation accuracy and online query support. However, most current work uses the same sampling probability for all flows, leading to the waste in storage and communication resources. In practice, different flows often require different sampling rates to meet the same accuracy constraint. This paper presents self-adaptive sampling, a framework to sample each flow with a probability adapted to flow size/spread. Then we propose three algorithms, SAS-LC, SAS-LOG, and SAS-HYB. SAS-LC and SAS-LOG are geared towards per-flow spread estimation and per-flow size estimation by using different compression functions. SAS-HYB combines the advantages of SAS-LC and SAS-LOG, showing higher efficiency when both small flows and large flows are interested. We implement our estimators in hardware using NetFPGA. Experimental results based on real Internet traces show that, compared to the state-of-the-art in per-flow spread estimation, SAS-LC can save around 10% on-chip space and reduce up to 40% communication cost for large flows. In per-flow size estimation, SAS-LOG can save 40% on-chip space and reduce up to 96% communication costs for large flows. Moreover, SAS-HYB’s on-chip memory usage will not be larger than SAS-LC or SAS-LOG and can save up to 19% on-chip space than SAS-LOG when both small flows and large flows are interested.

Blockchain came to prominence as the distributed ledger underneath Bitcoin, which protects the transaction histories in a fully-connected, peer-to-peer network. The blockchain mining process requires high computing power to solve a Proof-of-Work (PoW) puzzle, which is hard to implement on users’ mobile devices. So these miners may leverage the edge/cloud service providers (ESPs/CSP) to calculate the PoW puzzle. The existing edge-assisted blockchain networks assumed that all ESPs have a uniform propagation delay, which is unrealistic. In this article, we consider a more practical scene where ESPs locate in diverse positions of the blockchain network, which causes different propagation delays when supporting the computation of the PoW puzzle. Additionally, these ESPs connect to a remote CSP for resource scheduling when the computing tasks exceed their maximum capacity. The blockchain mining process generally involves complicated competition and games among CSP, ESPs, and miners. Each service provider focuses on how to determine his resource price so that he can maximize his utility. According to the set resource price, each miner concentrates on scheduling his resource requests for each ESP to maximize individual personal utility, which depends on ESPs’ resource price and propagation delays. We first model such a resource pricing and scheduling problem as a three-stage multi-leader multi-follower Stackelberg game and aim at finding the Stackelberg equilibrium. Then, we analyze the subgame optimization problem in each stage and propose an iterative algorithm based on backward induction to achieve the Nash equilibrium of the Stackelberg game. Finally, extensive simulations are conducted to verify the significant performance of the proposed solution.

As the popularity of mobile devices continues to increase, Mobile Crowdsensing (MC), a scalable and efficient data collection method, has received widespread attention. Although lots of effort has been devoted to studying the task assignment or worker recruitment in MC, most of them focus on how to maximize the profit from the perspective of the platform while ignoring rational individual workers' entitlement. We creatively start from the worker's perspective to find the task selection strategy to maximize the worker's profit. In this paper, the problem of unknown task selection is modeled as a Multi-Armed Bandit (MAB), on which three types of additional constraints are considered. The first constraint is the device budget. Workers choose and conduct tasks before it is exhausted. The second constraint is the personal preference regarding the traveling cost. The third constraint is the balance requirement of the MC platform, which has regulations on the tasks' execution rounds. In addition to the dilemma between exploration and exploitation in the classical MAB, we have to face the tradeoff between the reward and all the constraints above. To this end, we first adopt the epoch-style algorithm to reduce the number of switches between any two sensing tasks and further build new algorithms to deal with different constraints. The traveling cost and platform balance are involved in the task index computation as a penalty. We conduct extensive simulations based on real-world traces to verify the significant performance of our proposed algorithms.

Detecting heavy hitters that constitute the majority of network traffic is a critical task in network measurement. However, the highly skewed network traffic and the size-limited on-chip memory pose great challenges for heavy-hitter detection. The prior arts either use sketches to track all flows or maintain a fix-sized tracking list for recording elephant flows, resulting in limited detection precision or time-consuming tracking list exchanges. This paper presents HeavyTracker, an efficient algorithm that detects heavy hitters based on a count-with-threshold strategy. A two-dimensional tracker unit array is employed in our design to capture the heavy hitters, where each flow is randomly mapped to one unit in all rows. The tracker unit is designed to accept many flows and precisely report the largest two with frequencies that reach a predefined threshold. This design eliminates the frequent and time-consuming exchanges for maintaining the tracking list, allowing us to use a hash table to track the reported elephant flows. Experimental results based on real Internet traces show that HeavyTracker achieves a high $\mathbf{F}_{\beta}$-Score of threshold-t detection (0.97) and over 99% precision of top-k detection under a tight memory size. Besides, it reduces the frequency estimation error by 97.4% compared to the state-of-the-art.

Per-flow spread measurement in high-speed networks can provide indispensable information to many practical applications. However, it is challenging to measure millions of flows at line speed because on-chip memory modules cannot simultaneously provide large capacity and large bandwidth. The prior studies address this mismatch by entirely using on-chip compact data structures or utilizing off-chip space to assist limited on-chip memory. Nevertheless, their on-chip data structures record massive transient elements, each of which only appears in a short time interval in a long-period measurement task, and thus waste significant on-chip space. This paper presents short-term memory sampling, a novel spread estimator that samples new elements while only holding elements for short periods. Our estimator can work with tiny on-chip space and provide accurate estimations for online queries. The key of our design is a short-term memory duplicate filter that reports new elements and filters duplicates effectively while allowing incoming elements to override the stale elements to reduce on-chip memory usage. We implement our approach on a NetFPGA-equipped prototype. Experimental results based on real Internet traces show that, compared to the state-of-the-art, short-term memory sampling reduces up to 99% of on-chip memory usage when providing the same probabilistic assurance on spread-estimation error.

Per-flow size measurement is a fundamental problem in network engineering and plays a pivotal role in many practical applications. Constrained by on-chip memory resources and packet processing speed, most existing solutions use compact data structures (i.e., sketches) to perform the line-speed measurement. However, sketches share the record units (bits/counters) among flows, inevitably introducing noises to each flow’s measurement result. Although they adopt an average denoising strategy to remove noises from the raw estimations, the accuracy for medium flows is still lacking. This paper complements the prior art and presents a novel per-flow size measurement method, Adaptive Denoising (ADN), which can provide more accurate estimates for online and offline queries. For an online query, we use the collected flow records for real-time estimation. For an offline query, we model the propagation of noises based on the optimization algorithm to produce flow size estimation with much better accuracy. Experimental results based on real Internet traffic traces show that our measurement solutions outperform the state-of-the-art approaches and reduce the mean absolute error by around one order of magnitude under the same on-chip memory usage.

Intelligent vehicular cyber-physical systems can perform automatic traffic measurement, which provides critical information for transportation engineering. However, one of the biggest challenges in traffic measurement is to protect the vehicles’ location and trajectory privacy, which may be revealed from the recorded traffic data. Prior studies in traffic measurement only offer heuristic privacy protection but lack a precisely defined privacy model. This article proposes an efficient traffic estimator with differential privacy protection. In our design, each road-side unit communicates with the passing vehicles and records their presence in a privacy-preserving data structure. By performing probabilistic analysis on the anonymized records, the proposed method can precisely estimate the number of common vehicles passed by multiple given locations during the given measurement period. Through theoretical analysis, we prove that the proposed method can protect the trajectory privacy of the vehicles with$\epsilon$-differential privacy even when the point privacy has been leaked. We also evaluated our traffic estimator based on a real-world transportation traffic dataset. The evaluation results demonstrate that the proposed estimator can achieve high estimation accuracy and high-level privacy protection through controllable tradeoffs.

Mobile crowdsensing, through which a requester can coordinate a crowd of workers to complete some sensing tasks, has attracted significant attention recently. In this paper, we focus on the unknown worker recruitment problem in mobile crowdsensing, where workers’ sensing qualities are unknown a priori. We consider the scenario of recruiting workers to complete some continuous sensing tasks. The whole process is divided into multiple rounds. In each round, every task may be covered by more than one recruited workers, but its completion quality only depends on these workers’ maximum sensing quality. Each recruited worker will incur a cost and each task is attached a weight to indicate its importance. Our objective is to determine a recruiting strategy to maximize the total weighted completion quality under a limited budget. We model such unknown worker recruitment process as anovel combinatorial multi-armed bandit(CMAB) problem, and propose an unknown worker recruitment algorithm based on the modified upper confidence bound (UCB). Moreover, we extend the problem to the case where the workers’ costs are also unknown and design the corresponding algorithm. We analyze the regret bounds of the two proposed algorithms through rigorous proofs. In addition, we also study the unknown worker recruitment problem with fairness constraints. Here, the term “fairness” means that the platform must guarantee a minimum selection fraction for each registered worker, so that the platform can avoid the scenario where some workers are over-recruited but some others might be under-recruited. For this problem, we devise a fairness-aware unknown worker recruitment algorithm. Finally, we demonstrate the performance of the proposed algorithms through extensive simulations on real-world traces

With the rapid development of the Internet of Things (IoT), massive high-speed data streams are produced every moment, making accurate size estimation a challenging task. Many sketches have been proposed to summarize real-time high-speed data streams and provide per-flow size estimations. However, sketches have to share the memory units to fit in limited on-chip space, inevitably introducing noises to all flows and resulting in over-estimation problems. Prior work adopts an average denoising strategy to remove the same noise from raw sketch estimations. However, they overlook that the noise distribution is highly skewed, leading to inaccurate results for most flows. This paper proposes an efficient Adaptive Noise Correction (ANC) framework, which analyzes the noise of each flow on a case-by-case basis and provides accurate size estimations. The key of our design is to build an ML model to predict a weight coefficient that indicates the noises in raw estimations, which is conducted for each flow by analyzing the neighbor flows whose memory units overlap with the given flow. Then we introduce a novel Probabilistic Cold Filter to block the tiny flows and assist in noise correction. Experimental results based on real Internet traces show that our framework can effectively remove the noises for different sketches, showing better estimation accuracy than the state-of-the-art.

Online anomalous taxi trajectory detection, which identifies anomalies from ongoing taxi trajectories, has become an important and fundamental concern in many real-world applications. Most of the existing studies define the anomalous trajectories as the ones deviating from the majority of routes or showing abnormal driving time and distance at the same time. However, due to the complexity of road conditions and the variety of passenger preferences, those methods have large false-positive rates, i.e., reporting many normal routes as anomalies. A high false-positive rate is harmful since false alarms will 1) bring unnecessary panic to passengers, 2) cause fiscally punishments to normal drivers, and 3) wastes human resource to deal with drivers' complaints. To this end, this paper proposes an online anomalous trajectory detection method, namely multidimensional criteria based anomalous trajectory (MCAT), to identify anomalous trajectories online. It judges anomalies by considering multidimensional criteria (similarity, time, distance) at the same time, reducing the false positives without sacrificing false negative rates. We evaluate the proposed method based on the real-world taxi data collected from Shanghai, China. The experimental results demonstrate that our method can outperform state-of-the-art methods in terms of accuracy, false-negative rate, and false-positive rate.

Per-flow traffic measurement in the high-speed network plays an important role in many practical applications. Due to the limited on-chip memory and the mismatch between off-chip memory speed and line rate, sampling-based methods select and forward a part of flow traffic to off-chip memory, complementing sketch-based solutions in estimation accuracy and online query support. However, most current work uses the same sampling probability for all flows, overlooking that the sampling rates different flows require to meet the same accuracy constraint are different. It leads to a waste in storage and communication resources. In this paper, we present self-adaptive sampling, a framework to sample each flow with a probability adapted to flow size/spread. Then we propose two algorithms, SAS-LC and SAS-LOG, which are geared towards per-flow spread estimation and per-flow size estimation by using different compression functions. Experimental results based on real Internet traces show that, when compared to NDS in per-flow spread estimation, SAS-LC can save around 10% on-chip space and reduce up to 40% communication cost for large flows. Moreover, SAS-LOG can save 40% on-chip space and reduce up to 96% communication cost for large flows than NDS in per-flow size estimation.

Crowdsourcing is a widely adopted way for various labor-intensive tasks. One of the core problems in crowdsourcing systems is how to assign tasks to most suitable workers for better results, which heavily relies on the accurate profiling of each worker's reliability for different topics of tasks. Many previous work have studied worker reliability for either explicit topics represented by task descriptions or latent topics for categorical tasks. In this work, we aim to accurately estimate more fine-grained worker reliability for latent topics in numerical tasks, so as to further improve the result quality. We propose a bayesian probabilistic model named Gaussian Latent Topic Model(GLTM) to mine the latent topics of numerical tasks based on workers' behaviors and to estimate workers' topic-level reliability. By utilizing the GLTM, we propose a truth inference algorithm named TI-GLTM to accurately infer the tasks' truth and topics simultaneously and dynamically update workers' topic-level reliability. We also design an online task assignment mechanism called MRA-GLTM, which assigns appropriate tasks to workers with the Maximum Reduced Ambiguity principle. The experiment results show our algorithms can achieve significantly lower MAE and MSE than that of the state-of-the-art approaches.

Currently, the blockchain, as a key enabling technology of digital currency, has attracted lots of attention from both industry and academia. The blockchain mining process requires high computing power to solve a Proof-of-Work (PoW) puzzle, which is hard to implement on users’ mobile devices. So these miners may leverage the resources of the edge/cloud service providers (ESPs/CSP) to calculate the PoW puzzle. The existing edge-assisted blockchain networks simply assumed that all ESPs have a uniform propagation delay, which is not realistic. In this paper, we consider a more practical scene where ESPs with distributed geographic locations have diverse propagation delays when supporting the computation of the PoW puzzle. Additionally, the blockchain mining process generally involves the complicated competition and game among these ESPs and miners. Each ESP focuses on how to determine his resource price and to select the requests from the miners, so that he can maximize his utility. According to the set resource price, each miner concentrates on scheduling his resource requests for each ESP to maximize his individual utility which depends on ESPs’ resource price and propagation delays. We model such a resource pricing and scheduling problem as a multi-leader multi-follower Stackelberg game and aim at finding the joint maximization of the utilities of each ESP and each individual miner. We prove the existence and uniqueness of the Stackelberg equilibrium (SE) and meanwhile propose an algorithm to achieve the corresponding SE. Finally, extensive simulations are conducted to verify the significant performance of the proposed solution.

Per-flow spread measurement in high-speed networks has many practical applications. It is a more difficult problem than the traditional per-flow size measurement. Most prior work is based on sketches, focusing on reducing their space requirements in order to fit in on-chip cache memory. This design allows the measurement to be performed at the line rate, but it suffers from expensive computation for spread queries (unsuitable for online operations) and large errors in spread estimation for small flows. This paper complements the prior art with a new spread estimator design based on an on-chip/off-chip model. By storing traffic statistics in off-chip memory, our new design faces a key technical challenge to design an efficient online module of non-duplicate sampling that cuts down the off-chip memory access. We first propose a two-stage solution for non-duplicate sampling, which is efficient but cannot handle well a sampling probability that is either too small or too big. We then address this limitation through a three-stage solution that is more space-efficient. Our analysis shows that the proposed spread estimator is highly configurable for a variety of probabilistic performance guarantees. We implement our spread estimator in hardware using FPGA. The experiment results based on real Internet traffic traces show that our estimator produces spread estimation with much better accuracy than the prior art, reducing the mean relative (absolute) error by about one order of magnitude. Moreover, it increases the query throughput by around three orders of magnitude, making it suitable for supporting online queries in real time.

Per-flow spread measurement in high-speed networks has many practical applications. It is a more difficult problem than the traditional per-flow size measurement. Most prior work is based on sketches, focusing on reducing their space requirements in order to fit in on-chip cache memory. This design allows measurement to be performed at the line rate, but it has to accept tradeoff with expensive computation for spread queries (unsuitable for online operations) and large errors in spread estimation for small flows. This paper complements the prior art with a new spread estimator design based on an on-chip/off-chip model which is common in practice. The new estimator supports online queries in real time and produces spread estimation with much better accuracy. By storing traffic data in off-chip memory, our new design faces a key technical challenge of efficient non-duplicate sampling. We propose a two-stage solution with on-chip/off-chip data structures and algorithms, which are not only efficient but also highly configurable for a variety of probabilistic performance guarantees. The experiment results based on real Internet traffic traces show that our estimator reduces the mean relative and absolute error by around one order of magnitude, and achieves both space-efficiency and accuracy-efficiency in flow classification for small flows compared to the prior art.

This paper concentrates on the issue of detecting persistent elements of anomalous flows in a distributed monitoring system, which has many applications in detecting cyber-attacks, forecasting influenza, analyzing search keywords, and etc. However, only a few studies consider the anomalous flow detection problem in distributed systems. Meanwhile, most of the existing studies on persistent element detection problem in distributed systems assume that there is only one flow in the data stream, which is not always true in practice. In this paper, we combine the problems of anomalous flow detection and persistent elements finding, and propose an efficient mechanism to find the t-persistent elements of p-anomalous flows from element sets of numerous flows in the monitors of a distributed system, where t and p are system parameters that can be defined based on the application requirement. We adopt tight data structures such as bitmap and bloom filter to record the elements of different flows and filter out the elements that not in the t-persistent element set, which can help us reduce the communication overhead between monitors and the controller. We also give an analysis of how to get the optimal settings of these tight data structures that can minimize the total communication overhead. The experiment results based on real network traces show that the proposed mechanism achieves 76.1% and 69.2% reduction in communication overhead in comparison with a straightforward solution and a state-of-the-art solution based on coding cuckoo filter, respectively.

With the proliferation of mobile devices, mobile crowd sensing (MCS) has emerged as a new data collection paradigm, which allows the crowd to act as sensors and contribute their observations about entities. Unfortunately, users with varied skills and motivations may provide conflicting information for the same entity. Existing work solves this problem by estimating user reliability and inferring the correct observations (i.e., truths). However, these methods assume that users' expertise degrees are dependent on the truths, but ignore the finer clusters that exist even in the entities with the same truths. To capture users' fine-grained reliability on different entity clusters, we propose a novel Bayesian co-clustering truth discovery model for the task of observation aggregation. This model enables us to produce a more precise estimation while taking into account the entity clusters and the user clusters. Experiments on four real-world datasets reveal that our method outperforms the state-of-the-art approaches in terms of accuracy and F1-score.

Crowdsensing is a promising sensing paradigm to efficiently collect and monitor the physical world by using the embedded sensors in mobile devices. However, the observations (sensory data) submitted by mobile device users may not be reliable. For the same sensing task, users with different reliabilities may submit conflicting information. Thus, we need to estimate the truth based on the submitted observations. Temporal and spatial correlations among tasks are widely observed in crowdsensing applications. However, most of the existing truth discovery mechanisms assume that the tasks are independent, which is not suitable for all crowdsensing applications. To solve this problem, we propose an efficient truth discovery mechanism for crowdsensing tasks with temporal and spatial correlations. To improve the reliability of the estimated truth, we first filter the outliers based on the temporal correlations among tasks, then estimate the truth based on the weighted observations, and finally refine the estimated truth based on the spatial correlations among tasks. Our experiments on a real transportation dataset show the efficiency of the proposed mechanism.

Real-time road condition monitoring, especially of severe road damage, is critical for driving safety. In this work, we propose a crowdsensing-based pothole detection and measurement system, called CPDM, which can accurately measure the depth and length of detected potholes in urban roads. CPDM learns road surface information by collecting the sensor data from the smartphones belonging to the passing drivers and passengers. The proposed system can detect potholes by observing the vibration signal when the vehicle passes over the pothole, learn the vehicle parameters by fitting the underdamping vibration signal with stochastic gradient descent, and estimate the depth and length of the pothole. We have implemented a prototype system to prove the efficiency and adaptability of the proposed CPDM. The experimental results based on real traces show that CPDM has a high detection accuracy at different vehicle speeds.

Taxi recommender systems have remarkably benefited the taxi business by providing a sequence of pick-up points to reduce the passenger waiting time or the taxi cruising time. In reality, taxi drivers may have their preferred destination regions to avoid traffic jams or to execute arranged pickup orders. However, no prior work managed to maximize the profit of drivers and satisfy the requirements for destination regions at the same time. To tackle this challenge, we propose a PROfit Maximization recommendatIon SystEm (PROMISE) based on the inter-regional probability. In this paper, we first divide the city map into sub-regions and compute the mobility probability of passengers among pick-up points and sub-regions, namely inter-regional mobile probability. Then, we propose an efficient Driving Route Suggestion (DRS) algorithm based on inter-regional probability, which can maximize the profit of taxi drivers with designated destination regions. The experimental results based on the taxi traces collected from Shanghai, China, validate the effectiveness of the proposed recommender system.

Forecasting taxi demand is of great significance to the intelligent transportation systems in a smart city. Traditional demand prediction methods mostly considered about inter-regional traffic, events, activities, and weather, while they overlooked the influence of other travel modes, such as metro. In this paper, we propose a Deep Taxi-Metro Spatial-Temporal Network framework, namely TMST-Net, to model the spatiotemporal relationships between the taxi demand and the metro crowd flows. In detail, we apply residual neural networks to model temporal (current, day, and week) properties of the taxi demand in each area. For each feature, we apply residual convolutional units to handle the spatial properties of taxi demand. Likewise, we apply the same method to model the metro crowd flows. TMST-Net learns to assign different weights between taxi and metro by aggregating the output of the three residual neural networks and the external factors to forecast the final taxi demand for each area in the next timestamp. Experimental results on real taxi trajectory and the automatic fare collection (AFC) data in Shanghai show that our approach outperforms the state-of-the-art methods.

Crowdsourcing has shown its efficiency in obtaining information by harnessing the intelligence of a large crowd of human workers. It is essential to employ incentive mechanisms, typically auction, to motivate workers and collect sufficient data, since performing crowdsourcing tasks will always consume considerable resources, e.g., CPU or battery resource. To this end, we focus on the problem of heterogeneous task allocation with budget constraint in the crowdsourcing systems and propose a truthful auction mechanism which can maximize the profit of the task requester. In this paper, we first prove the NP-hardness of the studied problem and design a near-optimal task allocation mechanism with partial enumeration which can maximize the profit of the requester. Then, we judiciously design a bid-independent payment calculation mechanism to ensure the truthfulness of the participants. Finally, we prove that the proposed crowdsourcing task auction mechanism can achieve truthfulness and individual rationality. The extensive simulation results also corroborate with our theoretical analysis.

With the advent of virtualization technologies, cloud computing resource allocation issue plays an important role. However, the existing studies have not fully considered the heterogeneous demands from different cloud tenants. To tackle this, we design a more flexible cloud resource allocation mechanism which can maximize the profit of the cloud provider and support three general types of resource requirements from the cloud tenants. In this work, the jobs from tenants will bid for the usage of VMs in 3 types: 1) fixed time intervals, 2) time window intervals and 3) Time window slice intervals. We proved that the proposed approximation allocation mechanism has an approximation factor which approaches 1.58 when cmcloses to infinity.