Nils Kammenhuber's Publications

Efficient Statistics Gathering from Tree-Search Methods in Packet Processing Systems
Citation key	KK-ESGTMPPS-05
Author	Kencl, Lukas and Kammenhuber, Nils
Title of Book	Proceedings of the 2005 IEEE International Conference in Communications (ICC 2005)
Pages	1483–1489
Year	2005
ISBN	0-7803-8938-7
DOI	http://dx.doi.org/10.1109/ICC.2005.1494592
Location	Seoul, Korea
Volume	3
Publisher	IEEE
Abstract	We present a novel algorithm for efficiently gathering statistics about the hit frequencies on the nodes of a search tree in a packet processing system, under limiting space constraints. The Expand and Collapse (EaC) algorithm is a heuristic that periodically adjusts the subset of nodes of the search tree at which statistics are gathered, in order to use the limited space available to collect statistics in preference from the currently most heavily-hit nodes in the search tree. We prove convergence and good node-hit coverage of the algorithm and validate its performance on a set of simulated data. The information collected can be useful for a variety of reasons, such as inferring traffic properties, discovering failures and attacks or dynamically optimizing the search method itself for locality patterns in the oncoming traffic. Index TermsResource allocation, network architecture, traffic monitoring and management, adaptive networks.