Network of Shortcuts: An Adaptive Data Structure for Tree-Based Search Methods

In 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.

Published in:
Networking 2005, 523-535
Presented at:
Networking 2005, Waterloo (Canada)
Other identifiers:

Note: The status of this file is: Anyone

 Record created 2005-04-06, last modified 2020-10-25

Download fulltext

Rate this document:

Rate this document:
(Not yet reviewed)