Adaptive Random Sampling for Load Change Detection

Abstract

Timely detection of changes in traffic is critical for initiating appropriate traffic engineering mechanisms.Accurate measurement of traffic is an essential step towards change detection and traffic engineering.However, precise traffic measurement involves inspecting every packet traversing a link, resulting in significant overhead, particularly on routers with high speed links. Sampling techniques for traffic estimation are proposed as a way to limit themeasurement overhead. Since the efficacy of changedetection depends on the accuracy of trafficestimation, it is necessary to control error inestimation due to sampling. In this paper, we address the problem of bounding sampling error within a pre-specified tolerance level. We derive a relationship between the number of samples, theaccuracy of estimation and the squared coefficient ofvariation of packet size distribution. Based on thisrelationship, we propose an adaptive random samplingtechnique that determines the minimum samplingprobability adaptively according to traffic dynamics.Using real network traffic traces, we show that theproposed adaptive random sampling technique indeedproduces the desired accuracy, while also yieldingsignificant reduction in the amount of trafficsamples. We also investigate the impact of samplingerrors on the performance of load change detection.