Multiresolution Priority Queues

TL;DR

The paper introduces multiresolution priority queues (MR-PQs), which relax total priority ordering by discretizing the priority space into resolution groups to improve performance. It gives algorithms and complexity bounds, then shows an implementation in the Bro network monitor that reduces the priority-queue bottleneck.

Key findings

• MR-PQ trades a controllable amount of priority resolution for speed: it guarantees ordering only across resolution groups, not within a group.
• Worst-case insert cost is reduced from \(O(\log n)\) for a binary heap priority queue to \(O(\log r)\) for the binary-tree-based MR-PQ, where \(n\) is the number of elements and \(r\) is the number of resolution groups; the base MR-PQ has worst-case insert \(O(r)\) and amortized insert \(O(1)\) when the table is highly populated. Peek, extract-min, and arbitrary extract are \(O(1)\).
• In Bro, the binary-heap priority queue’s `PriorityQueue::BubbleDown` was the top profiled function at 6.5% of total processing cost, while the priority queue implementation was 105 lines of C++ out of 333,930 lines of C/C++ code (0.03%).
• Replacing Bro’s timer manager with the sliding MR-PQ took 144 lines of C++ and improved cache performance, instructions per cycle, packet drop rate, total network events generated, and total files processed across traffic rates from 2 Gbps to 10 Gbps.

Methods

• The paper formally defines the MR-PQ invariant, gives pseudocode for insert, peek, extract, extract-min, lookup-table repair, and a sliding-priority variant, and proves correctness and complexity via lemmas.
• It also proposes a binary-tree-based variant, BT-MR-PQ, to reduce worst-case insert from \(O(r)\) to \(O(\log r)\).
• For evaluation, the authors implement the sliding MR-PQ in Bro, an event-driven network analytics application, and benchmark it against Bro’s default binary heap priority queue using a traffic dataset mixing real corporate-network traces from New York and synthetically generated Ixia traffic; tests run from 2 Gbps to 10 Gbps on two Intel Xeon E5-2670 processors at 2.50 GHz, 20 physical cores, 25.6 MB L3 cache per processor, and 4 x 10 Gbps interfaces.

Limitations

• The paper states that MR-PQ does not guarantee total ordering within a priority resolution group; larger \(p_\Delta\) improves performance but makes the priority space more granular.
• The base MR-PQ has worst-case insert \(O(r)\), and the paper leaves study of implications for graph algorithms to future work.
• Evident from the text: the empirical evaluation is limited to one application, Bro, and one traffic dataset; the referenced figures report improvements but the text does not give exact numerical values for most of them.