Research On Scalability And Related Key Algorithms For Network Measurement Based On Packet Sampling

The main purpose of network passive measurement is measuring and estimating the characteristic of network flows. On the high speed network, it is very difficult for monitoring applications to process every packet. Data reduction is an indispensable component of today's network measurement and monitoring and the sampling is the most general data reduction method. Many preceding researches have focused on the flow sampling techniques. Because all those approaches require the classification of packets into flows before or during the sampling process, they benefit only a kind of characteristic of network flows and lose scalability. On the other hand, the flow sampling techniques require more computation resource and memory resource. So the packet sampling is currently the majority of packet selection method using by many business requirement. To improve the scalability problem, this paper focus on the algorithms to estimate the characteristic of flows with the use of the network protocol information in the sampling packet. The main contributions are as follows:1) The flow size distribution is an important metric in the network traffic engineering and monitoring, and it has received some attention in recent years. The preceding research has proved that using the network protocol information in the sampling packet can improve the flow size distribution estimation. Based on the preceding research, this paper introduces an algorithm using both SYN flag and sequence numbers (ALL-PS+SYN+SEQ) and compares it with the other four flow size distribution estimation algorithms using SYN flag information and TCP sequence numbers. To access those algorithms accuracy, we calculate the mean squared error (the C-R bound) using the Fisher information metric. The result of the C-R bound and the experiments demonstrate that the ALL-PS+SYN+SEQ algorithm is the best method.2) Many applications require fine grained estimates of smaller flow sizes, and require coarse grained estimates of larger flow sizes within a certain scope. We present a non-uniform grained estimator for the flow size distribution. The estimation algorithm leads to a speedup in the computation, and provides more accuracy for coarse grained estimates of larger flow sizes.3) There are a number of network applications which are focus on the flow size distribution of a particular subpopulations. In this paper, we propose an algorithm for estimating arbitrary subpopulation flow size distribution using TCP protocol information from random sampling data. Experiments are conducted with the real network traces. Results show that the proposed method improves the accuracy of flow size distribution estimation of subpopulations and restores the original character of flow size distribution.4) The ?ow byte sizes is an important metric for network measurement. Previous work on estimating the flow size distribution (in bytes) has been focus on improving sampling technique to increase measurement accuracy. In this paper, we present an algorithm of flow byte sizes estimation based on random packet sampling. Our algorithm first obtains a Maximum Likelihood Estimator of flow length using the TCP protocol information. After that the estimation of the ?ow byte sizes is accomplished through a linear regression model that relies on the ?ow length information previously obtained. Experimental results show that our approach is effective enough to capture the network traffic characteristics.5) The portscan is most popular anomaly in the network and TRW is most representative algorithm for the portscan detection. Previous works have shown that packet sampling thins traffic flows and impacts anomaly detection. The success ratio Rs and the false negative ratio Rf+ of TRW initially increases for low sampling intervals before dropping off for high sampling intervals as the traffic is increasingly thinned. Based on previous works, we design a improved TRW using TCP protocol information in the sampling packet. Experimental results show that using the algorithm the false negative ratio Rf+ drops off while the success ratio Rs does not change.