Abstract
We consider portable software implementations of hash tables with timeouts. The context is a high volume stream of keyed items. When a new item arrives, we want to know if has been seen recently in terms of a fixed lifespan. This problem has numerous applications as a front-end for Internet traffic processing where the key could be a selection of fields from the header of a packet, e.g., tracing packets through networks, aggregation of netflows from routers, and helping firewalls reuse decisions from recent packets with the same key. We propose time-reversed linear probing tables to deal with timeouts. In experiments, compared with tumbling windows and lazy deletions, our time-reversed tables typically gains at least 25% in speed while using only half the space. The cost per item approaches that of a single random memory access. Our new scheme is cleaner to implement than previous schemes, and also more versatile, e.g., it is trivial to allow different items to have different lifespans; something not possible with tumbling windows. Adding this to the improved time and space efficiency, makes time-reversed linear probing a canonical first choice for hash tables with time-outs.
| Originalsprog | Engelsk |
|---|---|
| Titel | 2011 Proceedings IEEE INFOCOM |
| Antal sider | 5 |
| Forlag | IEEE |
| Publikationsdato | 2011 |
| Sider | 166-170 |
| ISBN (Trykt) | 978-1-4244-9919-9 |
| DOI | |
| Status | Udgivet - 2011 |
| Udgivet eksternt | Ja |
| Begivenhed | The 30th IEEE International Conference on Computer Communications - Shanghai , Kina Varighed: 10 apr. 2011 → 15 apr. 2011 Konferencens nummer: 30 |
Konference
| Konference | The 30th IEEE International Conference on Computer Communications |
|---|---|
| Nummer | 30 |
| Land/Område | Kina |
| By | Shanghai |
| Periode | 10/04/2011 → 15/04/2011 |