Traffic measurement provides critical information for network management, resource allocation, traffic engineering, and attack detection. Most prior art has been geared towards specific application needs with specific performance objectives. To support diverse requirements with efficient and future-proof implementation, this paper takes a new approach to establish common frameworks, each for a family of traffic measurement solutions that share the same implementation structure, providing a high level of generality, for both size and spread measurements and for all flows. The designs support many options of performance-overhead tradeoff with as few as one memory update per packet and as little space as several bits per flow on average. Such a family-based approach will unify implementation by removing redundancy from different measurement tasks and support reconfigurability in a plug-n-play manner. We demonstrate the connection and difference in the design of these traffic measurement families and perform experimental comparisons on hardware/software platforms to find their tradeoff, which provide practical guidance for which solutions to use under given performance goals.

You Zhou;Youlin Zhang;Chaoyi Ma;式刚 陈;Olufemi O. Odegbile

Performance Evaluation Review

2020-7-8

Ahstract-Per-flow traffic measurement is a fundamental problem in the era of big network data, and has been widely used in many applications, including capacity planning, anomaly detection, load balancing, traffic engineering, etc. In order to keep up with the line speed of modern network devices (e.g., routers), per-flow measurement online module is often implemented by using on-chip cache memory (such as SRAM) to minimize per-packet processing time, but on-chip SRAM is expensive and limited in size, which poses a major challenge for traffic measurement. In response, much recent research is geared towards designing highly compact data structures for approximate estimation that can provide probabilistic guarantees for per-flow measurement. The state of art, called Counter Tree (CT), requires at least 2 bits per flow in memory consumption and more than 2 memory accesses per packet in processing time. In this paper, we propose a novel design of a highly compact and efficient counter architecture, called Virtual Active Counter estimation (VAC), which achieves faster processing speed (slightly more than 1 memory access per packet on average) and provides more accurate measurement results than CT under the same allocated memory. Moreover, VAC can perform well even with a very tight memory space (less than 1 bit per flow or even one fifth of a bit per flow). Theoretical analysis and experiments based on real network traces demonstrate the superior performance of VAC.

You Zhou;Yian Zhou;式刚 陈;Youlin Zhang

2018-10-8

This paper explores a new type of congestion pricing that differentiates users with respect to their travel characteristics or attributes, and charges them different amounts of toll accordingly. The scheme can reduce the financial burden of travelers or lead to more substantial reduction of congestion. Given that the scheme requires tracking vehicles, an incentive program is designed to mitigate travelers' privacy concerns and entice them to voluntarily disclose their location information.

Mahmood Zangui;Yafeng Yin;Siriphong Lawphongpanich;式刚 陈

Transportation Research Part C: Emerging Technologies

2013-11

Traffic measurement provides critical real-world data for service providers and network administrators to perform capacity planning, accounting and billing, anomaly detection, and service provision. One of the greatest challenges in designing an online measurement module is to minimize the per-packet processing time in order to keep up with the line speed of the modern routers. To meet this challenge, we should minimize the number of memory accesses per packet and implement the measurement module in the on-die SRAM. The small size of SRAM requires extremely compact data structures to be designed for storing per-flow information. The best existing work, called counter braids, requires more than 4 bits per flow and performs six or more memory accesses per packet. In this paper, we design a fast and compact measurement function that estimates the sizes of all flows. It achieves the optimal processing speed: two memory accesses per packet. In addition, it provides reasonable measurement accuracy in a tight space where the counter braids no longer work. Our design is based on a new data encoding/decoding scheme, called randomized counter sharing. This scheme allows us to mix per-flow information together in storage for compactness and, at the decoding time, separate the information of each flow through statistical removal of the error introduced during information mixing from other flows. The effectiveness of our online per-flow measurement approach is analyzed and confirmed through extensive experiments based on real network traffic traces. We also propose several methods to increase the estimation range of flow sizes.

Tao Li;式刚 陈;Yibei Ling

IEEE/ACM Transactions on Networking

2012

Detecting spreaders can help an intrusion detection system identify potential attackers. The existing work can only detect aggressive spreaders that scan a large number of distinct addresses in a short period of time. However, stealthy spreaders may perform scanning deliberately at a low rate. We observe that these spreaders can easily evade the detection because their small traffic footprint will be covered by the large amount of background normal traffic that frequently flushes any spreader information out of the intrusion detection system's memory. We propose a new streaming scheme to detect stealthy spreaders that are invisible to the current systems. The new scheme stores information about normal traffic within a limited portion of the allocated memory, so that it will not interfere with spreaders' information stored elsewhere in the memory. The proposed scheme is light weight; it can detect invisible spreaders in highspeed networks while residing in SRAM. Through experiments using real Internet traffic traces, we demonstrate that our new scheme detects invisible spreaders efficiently while keeping both false-positives (normal sources misclassified as spreaders) and false-negatives (spreaders misclassified as normal sources) to low level.

Myung Keun Yoon;式刚 陈

2008

Per-flow traffic measurement, which is to count the number of packets for each active flow during a certain measurement period, has many applications in traffic engineering, classification of routing distribution or network usage pattern, service provision, anomaly detection, and network forensics. In order to keep up with the high throughput of modern routers or switches, the online module for per-flow traffic measurement should use high-bandwidth SRAM that allows fast memory accesses. Due to limited SRAM space, exact counting, which requires to keep a counter for each flow, does not scale to large networks consisting of numerous flows. Some recent work takes a different approach to estimate the flow sizes using counter architectures that can fit into tight SRAM. However, existing counter architectures have limitations, either still requiring considerable SRAM space or having a small estimation range. In this paper, we design a scalable counter architecture called Counter Tree, which leverages a 2-D counter sharing scheme to achieve far better memory efficiency and in the meantime extend estimation range significantly. Furthermore, we improve the performance of Counter Tree by adding a status bit to each counter. Extensive experiments with real network traces demonstrate that our counter architecture can produce accurate estimates for flows of all sizes under very tight memory space.

Min Chen;式刚 陈;Zhiping Cai

IEEE/ACM Transactions on Networking

2017-4

Radio-frequency identification (RFID) technology has been widely adopted by real-world industries. This paper presents a new application for distributively deployed RFID systems, wherein a user chooses multiple tag sets at will from different spatial or temporal domains, and then connects them by set operators (union, intersection and relative complement) to form a set expression. The user is allowed to query for the cardinality of an arbitrary set expression, which is called the joint property of multiple sets. We focus on the problem of estimating the joint property with bounded error, which has many potential applications. One of them is to allow users to check the number of tags in an arbitrary tag flow passing through a distributed RFID system. For this problem, we propose a solution with a novel design that supports versatile snapshot construction: Given the snapshots of multiple tag sets, although their lengths may be very different, our formulas can estimate their joint properties, with an accuracy that can be arbitrarily set. For the proposed estimator, we formally analyze its bias and variance, and also the optimal settings of protocol parameters to minimize the time cost of taking a snapshot of a tag set. The simulation results show that, under predefined accuracy requirement, our solution can reduce time cost by multiple folds as compared with existing works named DiffEstm and CCF, which require all tag sets must be encoded into snapshots with an equal length.

Qingjun Xiao;式刚 陈;Min Chen

2016-7-5

The grouping problem in RFID systems is to efficiently group all tags according to a given partition such that tags in the same group will have the same group ID. Unlike previous research on unicast transmission from a reader to a tag, grouping provides a fundamental mechanism for efficient multicast transmissions and aggregate queries in large RFID-enabled applications. A message can be transmitted to a group of m tags simultaneously in multicast, which improves the efficiency by m times when comparing with unicast. This paper studies this practically important but not yet thoroughly investigated grouping problem in large RFID system. We start with a straightforward solution called the Enhanced Polling Grouping (EPG) protocol. We then propose a time-efficient Filter Grouping (FIG) protocol that uses Bloom filters to remove the costly ID transmissions. We point out the limitation of the Bloom-filter based solution due to its intrinsic false positive problem, which leads to our final ConCurrent Grouping (CCG) protocol. With a drastically different design, CCG is able to outperform FIG by exploiting collisions to inform multiple tags of their group ID simultaneously and by removing any wasteful slots in its frame-based execution. We further enhance CCG to make it perform better with very large groups. Simulation results demonstrate that our best protocol CCG can reduce the execution time by a factor of 11 when comparing with a baseline polling protocol.

Jia Liu;Min Chen;Bin Xiao;Feng Zhu;式刚 陈;Lijun Chen

IEEE/ACM Transactions on Networking

2016-10

Radio-frequency identification (RFID) technologies have been widely used in inventory management, object tracking and supply chain management. One of the fundamental system functions is called cardinality estimation, which is to estimate the number of tags in a covered area. We extend the research of this function in two directions. First, we perform joint cardinality estimation among tags that appear at different geographical locations and at different times. Moreover, we collect category-level information, which is more significant in practical scenarios where we need to monitor the tagged objects of many different types. Second, we require anonymity in the process of information gathering in order to preserve the privacy of the tagged objects. These capabilities will enable new applications such as tracking how products are moved in a large, distributed supply network. We propose a novel protocol design to meet the requirements of anonymous category-level joint estimation over multiple tag sets. We formally analyze the performance of our estimator and determine the optimal system parameters. Extensive simulations show that the proposed protocol can efficiently obtain accurate category-level estimation, while preserving tags' anonymity.

Youlin Zhang;式刚 陈;You Zhou;玉光 方

2018-10-8

RFID technology has been widely adopted for real-world applications, such as warehouse management, logistic control, and object tracking. This paper focuses on a new angle of applying RFID technology-monitoring the temporal change of a tag set in a certain region, which is called churn estimation. This problem is to provide quick estimations on the number of new tags that have entered a monitored region, and the number of pre-existing tags that have departed from the region, within a predefined time interval. The traditional cardinality estimator for a single tag set cannot be applied here, and the conventional tag identification protocol that collects all tag IDs takes too much time, especially when the churn estimation needs to perform frequently to support real-time monitoring. This paper will take a new solution path, in which a reader periodically scans the tag set in a region to collect their compressed aggregate information in the form of empty/singleton/collision time slots. This protocol can reduce the time cost of attaining pre-set accuracy by at least 35%, when comparing with a previous work that uses only the information of idle/busy slots. Such a dramatic improvement is due to our awareness of collision slot state and the full utilization of slot state changes. Our proposed churn estimator, as shown by the extensive analysis and simulation studies, can be configured to meet any pre-set accuracy requirement with a statistical error bound that can be made arbitrarily small.

Qingjun Xiao;Bin Xiao;式刚 陈;Jiming Chen

IEEE/ACM Transactions on Networking

2017-2