Change search
ReferencesLink to record
Permanent link

Direct link
TRASH: A dynamic LC-trie and hash data structure
KTH, School of Computer Science and Communication (CSC), Numerical Analysis and Computer Science, NADA.
2007 (English)In: 2007 IEEE Workshop on High Performance Switching and Routing, HPSR, 2007, 76-81 p.Conference paper (Refereed)
Abstract [en]

A dynamic LC-trie is currently used in the Linux kernel to implement address lookup in the IP routing table [1], [2]. The main virtue of this data structure is that it supports both fast address lookups and frequent updates of the table. Also, it has an efficient memory management scheme and supports multiprocessor architectures using the RCU locking mechanism. The structure scales nicely: the expected number of memory accesses for one lookup is O(log log n), where n is the number of entries in the lookup table. In particular, the time does not depend on the length of the keys, 32-bit IPv4 addresses and 128-bit addresses does not make a difference in this respect. In this article we introduce TRASH, a combination of a dynamic LC-trie and a hash function. TRASH is a general purpose data structure supporting fast lookup, insert and delete operations for arbitrarily long bit strings. TRASH enhances the level-compression part of the LC-trie by prepending a header to each key. The header is a hash value based on the complete key. The extended keys will behave like uniformly distributed data and hence the average and maximum depth is typically very small, in practice less than 1.5 and 5, respectively. We have implemented the scheme in the Linux kernel as a replacement for the dst cache (IPv4) and performed a full scale test on a production router using 128-bit flow-based lookups. The Linux implementation of TRASH inherits the efficient RCU locking mechanism from the dynamic LC-trie implementation. In particular, the lookup time increases only marginally for longer keys and TRASH is highly insensitive to different types of data. The performance figures are very promising and the cache mechanism could easily be extended to serve as a unified lookup for fast socket lookup, flow logging, connection tracking and stateful networking in general.

Place, publisher, year, edition, pages
2007. 76-81 p.
Keyword [en]
Computer operating systems, Data communication systems, Data structures, Diffractive optical elements, File organization, Functions, High performance liquid chromatography, Internet protocols, Keys (for locks), Mechanisms, Well logging
National Category
Computer and Information Science
URN: urn:nbn:se:kth:diva-155272DOI: 10.1109/HPSR.2007.4281239ScopusID: 2-s2.0-47649111102ISBN: 1424412064ISBN: 978-142441206-8OAI: diva2:761067
2007 IEEE Workshop on High Performance Switching and Routing, HPSR, 30 May 2007 through 1 June 2007, Brooklyn, NY, United States

QC 20141105

Available from: 2014-11-05 Created: 2014-11-04 Last updated: 2014-11-05Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Nilsson, Stefan
By organisation
Numerical Analysis and Computer Science, NADA
Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 8 hits
ReferencesLink to record
Permanent link

Direct link