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 6 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: 2 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.

Tao Li;式刚 陈;Yibei Ling

2011

Efficient estimation of tag population in RFID systems has many important applications. In this paper, we present a new problem called differential cardinality estimation, which tracks the population changes in a dynamic RFID system where tags are frequently moved in and out. In particular, we want to provide quick estimation on (1) the number of new tags that are moved in and (2) the number of old tags that are moved out, between any two consecutive scans of the system. We show that the traditional cardinality estimators cannot be applied here, and the tag identification protocols are too expensive if the estimation needs to be performed frequently in order to support real-time monitoring. This paper presents the first efficient solution for the problem of differential cardinality estimation. The solution is based on a novel differential estimation framework, and is named zero differential estimator. We show that this estimator can be configured to meet any pre-set accuracy requirement, with a probabilistic error bound that can be made arbitrarily small.

Qingjun Xiao;Bin Xiao;式刚 陈

2013

RFID tags have many important applications in automated warehouse management. One example is to monitor a set of tags and detect whether some tags are missing the objects to which the missing tags are attached are likely to be missing, too, due to theft or administrative error. Prior research on this problem has primarily focused on efficient protocols that reduce the execution time in order to avoid disruption of normal inventory operations. This paper makes several new advances. First, we observe that the existing protocol is far from being optimal in terms of execution time. We are able to cut the execution time to a fraction of what is currently needed. Second, we study the missing-tag detection problem from a new energy perspective, which is very important when battery-powered active tags are used. The new insight provides flexibility for the practitioners to meet their energy and time requirements.

Wen Luo;式刚 陈;Tao Li;Shiping Chen

2011

Traditional radio frequency identification (RFID) technologies allow tags to communicate with a reader but not among themselves. By enabling peer-to-peer communications among nearby tags, the emerging networked tags make a fundamental enhancement to today's RFID systems. This new capability supports a series of system-level functions in previously infeasible scenarios where the readers cannot cover all tags due to cost or physical limitations. This paper makes the first attempt to design a new communication model that is specifically tailored to efficient implementation of system-level functions in networked tag systems, in terms of energy cost and execution time. Instead of exploiting complex mechanisms for collision detection and resolution, we propose a collision-resistant communication model (CCM) that embraces the collision in tag communications and utilizes it to merge the data from different sources in a benign way. Two fundamental applications: RFID estimation and missing-tag detection, are presented to illustrate how CCM assists efficient system-level operations in networked tag systems. Simulation results show that the system-level applications through CCM are able to reduce the energy cost and execution time by one order of magnitude, compared with the ID-collection based solution.

Jia Liu;Youlin Zhang;式刚 陈;Min Chen;Lijun Chen

2019-7

The future Internet is expected to support multicast 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 acalability 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 intradomain and interdomain. 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

IEEE Journal on Selected Areas in Communications

2000-12

Computing constrained shortest paths is fundamental to some important network functions such as QoS routing, which is to find the cheapest path that satisfies certain constraints. In particular, finding the cheapest delay-constrained path is critical for real-time data flows such as voice calls. Because it is NP-complete, much research has been designing heuristic algorithms that solve the ε-approximation of the problem with an adjustable accuracy. A common approach is to discretize (i.e., scale and round) the link delay or link cost, which transforms the original problem to a simpler one solvable in polynomial time. The efficiency of the algorithms directly relates to the magnitude of the errors introduced during discretization. In this paper, we propose two techniques that reduce the discretization errors, which allows faster algorithms to be designed. Reducing the overhead of the costly computation for constrained shortest paths is practically important for the design of a high-throughput QoS router, which is limited by both processing power and memory space. Our simulations show that the new algorithms reduce the execution time by an order of magnitude on power-law topologies with 1000 nodes. The reduction in memory space is similar. When there are multiple constraints, the improvement is more dramatic.

式刚 陈;Meongchul Song;Sartaj Sahni

2004

Radio frequency identification (RFID) technology has many applications in inventory management, supply chain, product tracking, transportation, and logistics. One research issue of practical importance is to search for a particular group of tags in a large-scale RFID system. Time efficiency is a crucial factor that must be considered when designing a tag search protocol to ensure its execution will not interfere with other normal inventory operations. In this paper, we design a new technique called filtering vector, which can significantly reduce transmission overhead during search process, thereby shortening search time. Based on this technique, we propose an iterative tag search protocol. In each round, we filter out some tags and eventually terminate the search process when the search result meets the accuracy requirement. Furthermore, we extend our protocol to work under noisy channel. The simulation results demonstrate that our protocol performs much better than the best existing work.

Min Chen;Wen Luo;Zhen Mo;式刚 陈;玉光 方

IEEE/ACM Transactions on Networking

2016-4

Software-defined networks facilitate automatic poli- cy enforcement with dynamic routing of flows through a sequence of middleboxes that offer the required network functions. As a result, network policy enforcement based on middleboxes, which is tedious and error-prone to perform in traditional IP networks, is greatly simplified. However, TCAM-based flow tables in SDN are small and energy-demanding, which limits the scalability of policy enforcement. This paper proposes a hybrid SDN-label switching scheme that combines TCAM- based switching (in SDN) at the network edge with label switching in the network core to provide scalable policy enforcement without compromising per-flow management capability. A linear optimization is proposed to balance workloads among the middleboxes. We demonstrate on OMNET++ that our proposed solution incurs much smaller processing/communication overhead and achieves better load-balancing when comparing with the prior art.

Olufemi Odegbile;式刚 陈;Youlin Zhang

2019-12

In an ad hoc network, all communication is done over wireless media, typically by radio through the air, without the help of wired base stations. Since direct communication is allowed only between adjacent nodes, distant nodes communicate over multiple hops. The quality-of-service (QoS) routing in an ad hoc network is difficult because the network topology may change constantly, and the available state information for routing is inherently imprecise. In this paper, we propose a distributed QoS routing scheme that selects a network path with sufficient resources to satisfy a certain delay (or bandwidth) requirement in a dynamic multihop mobile environment. The proposed algorithms work with imprecise state information. Multiple paths are searched in parallel to find the most qualified one. Fault-tolerance techniques are brought in for the maintenance of the routing paths when the nodes move, join, or leave the network. Our algorithms consider not only the QoS requirement, but also the cost optimality of the routing path to improve the overall network performance. Extensive simulations show that high call-admission ratio and low-cost paths are achieved with modest routing overhead. The algorithms can tolerate a high degree of information imprecision.

式刚 陈;Klara Nahrstedt

IEEE Journal on Selected Areas in Communications

1999-8

Many Internet multicast applications such as teleconferencing and remote diagnosis have Qualiry-of-Service (QoS) requirements. It is a challenging task to build QoS constrained multicast trees with high performance, high success ratio, low overhead, and low system requirements. This paper presents a new scalable QoS multicast routing protocol (SoMR) that has very small communication overhead and requires no state outside the multicast tree. SoMR achieves the favorable tradeoff between routing performance and overhead by carefully selecting the network sub-graph in which it conducts the search for a path that can support the QoS requirement, and by auto-tuning the selection according to the current network conditions. Its early-warning mechanism helps to detect and route around the real bottlenecks in the network, which increases the chance of finding feasible paths for additive QoS requirements. SoMR minimizes the system requirements; it relies only on the local state stored at each router. The routing operations are completely decentralized.

式刚 陈;Yuval Shavitt

Conference Record - International Conference on Communications

2004