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.

Yu E. Sun;河 黄;Chaoyi Ma;式刚 陈;Yang Du;Qingjun Xiao

2020-7

Traffic measurement is key to many network management tasks such as performance monitoring and cyber-security. Its aim is to inspect the packet stream passing through a network device, classify them into flows according to the header fields, and obtain statistics about the flows. For processing big streaming data in size-limited SRAM of line cards, many space-sublinear algorithms have been proposed, such as CountMin and CountSketch. However, most of them are designed for specific measurement tasks. Implementing multiple independent sketches places burden for online operations of a network device. It is highly desired to design a universal sketch that not only tracks individual large flows (called heavy hitters) but also reports overall traffic distribution statistics (called moments). The prior work UnivMon successfully tackled this ambitious quest. However, it incurs large and variable per-packet processing overhead, which may result in a significant throughput bottleneck in high-rate packet streaming, given that each packet requires 65 hashes and 64 memory accesses on average and many times of that in the worst case. To address this performance issue, we need to fundamentally redesign the solution architecture from hierarchical sampling to new progressive sampling and from CountSketch to new ActiveCM+, which ensure that per-packet overhead is a small constant (4 hash and 4 memory accesses) in the worst case, making it much more suitable for online operations, especially for pipeline implementation. The new design also makes effort to reduce memory footprint or equivalently improve measurement accuracy under the same memory. Our experiments show that our solution incurs just one sixteenth per-packet overhead of UnivMon, while improving measurement accuracy by three times under the same memory.

Qingjun Xiao;Zhiying Tang;式刚 陈

2020-7

This chapter studies the problem of periodically and automatically estimating the number of RFID tags. In a large RFID systems, active tags are likely to use due to their longer transmission distance. However, these battery-powered tags need to be recharged when they run out of energy. Recharging tens of thousands of tags is a laborious operation. Moreover, sometimes tagged products may be stacked up, which makes tags not easily accessible. To prolong the lifetime of tags and reduce the frequency of battery recharge, all functions that involve large-scale transmission by many tags should be energy-efficient. This chapter focuses on designing energy-efficient protocols for the estimation problems in large-scale RFID systems.

Yan Qiao;式刚 陈;Tao Li

2013

Routing is a process of finding a network path from a source node to a destination node. The execution time and the memory requirement of a routing algorithm increase with the size of the network. In order to deal with the scalability problem, large networks are often structured hierarchically by grouping nodes into different domains. The internal topology of each domain is then aggregated into a simple topology that reflects the cost of routing across that domain. This process is called topology aggregation. For delay-bandwidth sensitive networks, traditional approaches represent the property of each link in the aggregated topology as a delay-bandwidth pair, which corresponds to a point on the delay-bandwidth plane. Since each link after aggregation may be the abstraction of many physical paths, a single delay-bandwidth pair results in significant information loss. The major contribution of this paper is a novel quality-of-service (QoS) parameter representation with a new aggregation algorithm and a QoS-aware routing protocol. Our QoS representation captures the state information about the network with much greater accuracy than the existing algorithms. Our simulation results show that the new approach achieves very good performance in terms of delay deviation, success ratio, and crankback ratio.

King Shan Lui;Klara Nahrstedt;式刚 陈

IEEE/ACM Transactions on Networking

2004-2

A firewall's complexity is known to increase with the size of its rule set. Empirical studies show that as the rule set grows larger, the number of configuration errors on a firewall increases sharply, while the performance of the firewall degrades. When designing a security-sensitive network, it is critical to construct the network topology and its routing structure carefully in order to reduce the firewall rule sets, which helps lower the chance of security loopholes and prevent performance bottleneck. This paper studies the problems of how to place the firewalls in a topology during network design and how to construct the routing tables during operation such that the maximum firewall rule set can be minimized. These problems have not been studied adequately despite their importance. We have two major contributions. First, we prove that the problems are NP-complete. Second, we propose a heuristic solution and demonstrate the effectiveness of the algorithm by simulations. The results show that the proposed algorithm reduces the maximum firewall rule set by 2-5 times when comparing with other algorithms.

Myungkeun Yoon;式刚 陈;Zhan Zhang

IEEE Transactions on Computers

2010

For many practical applications, it is a fundamental problem to estimate the flow cardinalities over big network data consisting of numerous flows especially a large quantity of mouse flows mixed with a small number of elephant flows, whose cardinalities follow a power-law distribution. Traditionally the research on this problem focused on using a small amount of memory to estimate each flow's cardinality from a large range up to 10⁹ . However, although the memory needed for each individual flow has been greatly compressed, when there is an extremely large number of flows, the overall memory demand can still be very high, exceeding the availability under some important scenarios, such as implementing online measurement modules in network processors using only on-chip cache memory. In this paper, instead of allocating a separated data structure called estimator for each flow, we take a different path by viewing all the flows together as a whole: Each flow is allocated with a virtual estimator, and these virtual estimators share a common memory space. We discover that sharing at the multi-bit register level is superior than sharing at the bit level. We propose a unified framework of virtual estimators that allows us to apply the idea of sharing to an array of cardinality estimation solutions, e.g., HyperLogLog and PCSA, achieving far better memory efficiency than the best existing work. Our experiment shows that the new solution can work in a tight memory space of less than 1 bit per flow or even one tenth of a bit per flow a quest that has never been realized before.

Qingjun Xiao;式刚 陈;You Zhou;Min Chen;Junzhou Luo;Tengli Li;Yibei Ling

IEEE/ACM Transactions on Networking

2017-12

Zhiyong Xu;Laurence T. Yang;Alex Zhaoyu Liu;Shu Ching Chen;Wasfi G. Al-Khatib;Ramazan S. Aygun;Liwu Chang;Han Chieh Chao;Ing Ray Chen;式刚 陈;Xiaowen Chu;John Sum;Mieso Denko;Zongming Fei;Xubin He;Yiming Hu;Tao Jiang;James B.D. Joshi;Ismail Khalil Ibrahim;Yan Luo;Geyong Min;Aaron J. Quigley;Mei Ling Shyu;Sabin Tabirca;Tsutomu Terada;Guojun Wang;Jun Wang;Qing Yang;Xiaochuan Yi;Chengcui Zhang;Chi Zhang;Yingwu Zhu

Proceedings - IEEE International Conference on Sensor Networks, Ubiquitous, and Trustworthy Computing

2006

The future Internet is expected to support multi-cast applications with quality of service (QoS) requirements. To facilitate this, QoS multicast routing protocols are pivotal in enabling new receivers to join a multicast group. However, current routing protocols are either too restrictive in their search for a feasible path between a new receiver and the multicast tree, or burden the network with excessive overhead. We propose QMRP, a new QoS-aware Multicast Routing Protocol. QMRP achieves scalability by significantly reducing the communication overhead of constructing a multicast tree, yet it retains a high chance of success. This is achieved by switching between single-path routing and multiple-path routing according to the current network conditions. The high level design of QMRP makes it operable on top of any unicast routing algorithm in both intra-domain and inter-domain. Its responsiveness is improved by using a termination mechanism which detects the failure as well as the success of routing without the use of timeout. In addition, QMRP always constructs loop-free multicast trees.

式刚 陈;Klara Nahrstedt;Yuval Shavitt

Proceedings - IEEE INFOCOM

2000

Persistent spread measurement is to count the number of distinct elements that persist in each network flow for predefined time periods. It has many practical applications, including detecting long-Term stealthy network activities in the background of normal-user activities, such as stealthy DDoS attack, stealthy network scan, or faked network trend, which cannot be detected by traditional flow cardinality measurement. With big network data, one challenge is to measure the persistent spreads of a massive number of flows without incurring too much memory overhead as such measurement may be performed at the line speed by network processors with fast but small on-chip memory. We propose a highly compact Virtual Intersection HyperLogLog (VI-HLL) architecture for this purpose. It achieves far better memory efficiency than the best prior work of V-Bitmap, and in the meantime drastically extends the measurement range. Theoretical analysis and extensive experiments demonstrate that VI-HLL provides good measurement accuracy even in very tight memory space of less than 1 bit per flow.

You Zhou;Yian Zhou;Min Chen;式刚 陈

2017-6-5

Radio frequency identification (RFID) technologies are widely used in many applications. The widespread use of tags in traditional ways of deployment raises a privacy concern: They make their carriers track able. This paper studies the problem of anonymous authentication. Due to resource constraints of low-cost tags, we develop a new technique to generate dynamic tokens for anonymous authentication by following an asymmetric design principle that pushes most complexity to more powerful RFID readers. Instead of implementing complicated cryptographic hash functions, our authentication protocol only requires tags to perform several simple hardware-efficient operations such as bitwise XOR, one-bit left circular shift and bit flip. Moreover, our protocol reduces the communication overhead and online computation overhead to O(1) per authentication for both tags and readers, which compares favorably with the prior art.

Min Chen;式刚 陈

2015-7-22