Bergamini, AndreaKencl, Lukas2005-04-062005-04-062005-04-06200510.1007/11422778_42https://infoscience.epfl.ch/handle/20.500.14299/212681WOS:0002301139000427025In this work we present a novel concept of augmenting a search tree in a packet-processing system with an dditional data structure, a Network of Shortcuts, in order to adapt the search to current input traffic patterns and significantly speed-up the frequently traversed search-tree paths. The method utilizes node statistics gathered from the tree and periodically adjusts the shortcut positions. After an overview of tree-search methods used in networking tasks such as lookup or classification, and a discussion of the impact of typical traffic characteristics, we argue that adding a small number of direct links, or shortcuts, to the few frequently traversed paths can significantly improve performance, at a very low cost. We present a shortcut-placement heuristic, compare our method to a standard caching mechanism and show how the use of different levels of aggregation in a search tree enables to achieve similar results with much fewer entries.Packet classificationadaptive methodstext::conference output::conference proceedings::conference paper