Home > Published Issues > 2012 > Volume 7, No. 1, January 2012 >

Low-Overhead Dynamic Sampling for Redundant Traffic Elimination

Department of Computer Science University of Calgary 2500 University Drive NW, Calgary, AB, Canada T2N 1N4

Abstract—Protocol-independent redundant traffic elimination (RTE) is an "on the fly" method for detecting and removing redundant chunks of data from network-layer packets traversing a constrained link or path. Efficient algorithms are needed to sample data chunks and detect redundancy, so that RTE does not hinder network throughput. A recently proposed static algorithm samples chunks based on highly-redundant trigger bytes observed in data content. While this algorithm is fast, it requires pre¬computed traffic information for the configuration of its static parameters, and it tends to either under-sample (reducing byte savings) or over-sample (increasing processing cost) on heterogeneous traffic. We propose a dynamic sampling algorithm for redundant content detection. Our algorithm is adaptive and self-configuring, and can precisely match the specified sampling rate. Furthermore, it offers byte savings comparable to the static algorithm, with very low additional processing overhead.

Index Terms --Algorithm, Sampling, Redundancy, Detection, Elimination, Performance, Network, Traffic

Cite:Emir Halepovic, Carey Williamson, and Majid Ghaderi, "Low-Overhead Dynamic Sampling for Redundant Traffic Elimination," Journal of Communications, vol. 7, no.1, pp.28-38, 2012. Doi: 10.4304/jcm.7.1.28-38