KK-ESGTMPPS-05

Lukas Kencl, Nils Kammenhuber. Efficient Statistics Gathering from Tree-Search Methods in Packet Processing Systems. In Proceedings of the 2005 IEEE International Conference in Communications (ICC 2005), (Location: Seoul, Korea), Volume 3, Pages 1483-1489, 2005.

Download [help]

Download paper: Doi page

Download paper: Postscript (ps)

Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

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.

Keyword

[ Ae ]

BibTex Reference

@InProceedings{KK-ESGTMPPS-05,
   Author = {Kencl, Lukas and Kammenhuber, Nils},
   Title = {Efficient Statistics Gathering from Tree-Search Methods in Packet Processing Systems},
   BookTitle = {Proceedings of the 2005 IEEE International Conference in Communications (ICC 2005)},
   Volume = {3},
   Pages = {1483--1489},
   Location = {Seoul, Korea},
   Year = {2005}
}

EndNote Reference [help]

Get EndNote Reference (.ref)

It has been automatically generated using the bib2html program.