Adaptive Data Structures for Networking Systems

Introduction

Many networking tasks, such as for example packet classification or IP lookup, require a large database to be searched at stringent time constraints. Typically, the search techniques use data structures optimized for the worst case traffic patterns, and thus potentially grossly sub-optimal for the actual traffic patterns. We ask ourselves the following question: if we were able to determine the current traversal pattern, how could we optimize the data structure for this pattern, at run-time? Two significant challenges can be identified in this problem statement: data structure monitoring and data structure adaptation.



Initially, we have concentrated on the widely used tree-based search techniques. To address the first challenge, we study algorithms for efficiently gathering statistics about hit frequencies on the nodes of a search tree in a packet processing system. For the second challenge, to adapt the search to current input traffic patterns and speed-up the frequently traversed search-tree paths, we develop methods that augment the search structure with an additional data structure, a Network of Shortcuts (NoS).



Have a look at the poster summarizing the project.

Watch the NoS method in action! (requires Macromedia Flash Player)

Watch the video of our NoS prototype, augmenting the Linux ptree tree-based filtering method from Washington University at St. Louis, mitigating a DoS-attack on a video stream!

Publications

Lukas Kencl, Christian Schwarzer
"Traffic Adaptive Packet Filtering of Denial of Service Attacks"
Proceedings of the Second International IEEE Workshop on Autonomic Communications and Computing ACC 2006, Niagara-Falls, NY, USA, June 2006.
[Abstract] [ Full document ]

Nils Kammenhuber, Lukas Kencl
"Efficient Statistics Gathering from Tree-Search Methods in Packet Processing Systems"
Proceedings of IEEE ICC 2005, Seoul, Korea, May 2005.
[ Abstract] [ Full document ]

Andrea Bergamini, Lukas Kencl
"Network of Shortcuts: An Adaptive Data Structure for Tree-based Search Methods"
Proceedings of IFIP Networking 2005, Waterloo, Canada, May 2005.
[ Abstract] [ Full document ]

People

Lukas Kencl	Ashish Gupta
Christian Schwarzer	Andrea Bergamini	Nils Kammenhuber