000033746 001__ 33746
000033746 005__ 20180318102520.0
000033746 02470 $$2DAR$$a7025
000033746 02470 $$2ISI$$a000230113900042
000033746 037__ $$aCONF
000033746 245__ $$aNetwork of Shortcuts: An Adaptive Data Structure for Tree-Based Search Methods
000033746 269__ $$a2005
000033746 260__ $$c2005
000033746 336__ $$aConference Papers
000033746 520__ $$aIn 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.
000033746 6531_ $$aPacket classification
000033746 6531_ $$aadaptive methods
000033746 700__ $$0241388$$aBergamini, Andrea$$g168683
000033746 700__ $$aKencl, Lukas
000033746 7112_ $$aNetworking 2005$$cWaterloo (Canada)
000033746 773__ $$q523-535$$tNetworking 2005
000033746 8564_ $$s403951$$uhttps://infoscience.epfl.ch/record/33746/files/bergaminiK05.pdf$$zn/a
000033746 909CO $$ooai:infoscience.tind.io:33746$$pconf$$pIC
000033746 909C0 $$0252614$$pLCA$$xUS00024
000033746 909C0 $$0252453$$pLCA2$$xU10427
000033746 937__ $$aLCA-CONF-2005-013
000033746 970__ $$a776/LCA
000033746 973__ $$aEPFL$$sPUBLISHED
000033746 980__ $$aCONF