Efficient statistical measurement methods in wired and wireless systems

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. We observe that in many measurement functions, statistical methods play important roles in system designing, model building, formula deriving, and error analyzing. In this dissertation, we first propose several novel online measurement functions in high-speed networks. We then notice that statistical methods for measurement problems are generic in many network systems. They can be also applied to wireless systems such as RFID (radio frequency identification) systems, which have been gaining popularity for inventory control, object tracking, and supply chain management in warehouses, retail stores, hospitals, etc. The second part of the dissertation studies the RFID estimation problem and designs two probabilistic algorithms for it. 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, which is fast but expensive. Because many other essential routing/security/performance functions may also run from SRAM, it is expected that the amount of high-speed memory allocated for the module will be small. Hence, it is critical to make the measurement module's data structure as compact as possible. The first work of this dissertation focuses on a particularly challenging problem, the measurement of per-flow information in high-speed networks. 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 best existing methods 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. Our second work studies the scan detection problem, which is one of the most fundamental functions in intrusion detection systems. We propose an efficient scan detection scheme based on dynamic bit sharing, which incorporates probabilistic sampling and bit sharing for compact information storage. We design a maximum likelihood estimation method to extract per-source information from the shared bits in order to determine the scanners. Our new scheme ensures that the false positive/false negative ratios are bounded with high probability. Moreover, given an arbitrary set of bounds, we develop a systematic approach to determine the optimal system parameters that minimize the amount of memory needed to meet the bounds. Experiments based on a real Internet traffic trace demonstrate that the proposed scan detection scheme reduces memory consumption by three to twenty times when comparing with the best existing work.