Optimal skampling for the flow size distribution
- Publication Type:
- Journal Article
- Citation:
- IEEE Transactions on Information Theory, 2015, 61 (6), pp. 3075 - 3099
- Issue Date:
- 2015-06-01
Closed Access
| Filename | Description | Size | |||
|---|---|---|---|---|---|
| 07078893.pdf | Published Version | 2.08 MB |
Copyright Clearance Process
- Recently Added
- In Progress
- Closed Access
This item is closed access and not available.
© 1963-2012 IEEE. We introduce a new method of data collection for flow size estimation, the optimized flow sampling sketch, which combines the optimal properties of flow sampling with the computational advantages of a counter array sketch. Using Fisher information as a definitive basis of comparison, we show that the statistical efficiency of the method is within a constant factor of that of flow sampling, which is known to be optimal but which cannot be implemented without a flow table, which has higher memory and computational costs. In the process, we derive new results on the Fisher information theoretic and variance properties of the counter array sketch, proving that an overloaded sketch actually destroys information. We revisit the 'eviction sketch' of Ribeiro et al. using the Fisher information framework. We show that its performance is much higher than previously supposed, and we define a new method, the optimized eviction sketch, which has very high efficiency. We compare these methods against each other and a third skampling method, sketch guided sampling, theoretically, on models and on data.
Please use this identifier to cite or link to this item: