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.
| Original language | English |
|---|---|
| Title of host publication | 2011 Proceedings IEEE INFOCOM |
| Number of pages | 5 |
| Publisher | IEEE |
| Publication date | 2011 |
| Pages | 166-170 |
| ISBN (Print) | 978-1-4244-9919-9 |
| DOIs | |
| Publication status | Published - 2011 |
| Externally published | Yes |
| Event | The 30th IEEE International Conference on Computer Communications - Shanghai , China Duration: 10 Apr 2011 → 15 Apr 2011 Conference number: 30 |
Conference
| Conference | The 30th IEEE International Conference on Computer Communications |
|---|---|
| Number | 30 |
| Country/Territory | China |
| City | Shanghai |
| Period | 10/04/2011 → 15/04/2011 |