Hi Mike,
My apologies. I thought this later email from 14th April had the latest version of the proposal: https://lists.torproject.org/pipermail/tor-dev/2020-April/014225.html
In short, we let the queue grow at a faster rate than we serve, and we trim it occasionally.
What is the benefit of this approach rather than discarding low priority requests right away in the top-half handler?
Note that a priority queue is typically implemented as a heap, which does not support efficient trimming.
However, it still has the following potential issues: A) AES will bottleneck us at ~100Mbit-300Mbit at #2 in top-half above B) Extra mainloop() iterations for INTRO2s may be expensive (or not?)
I don't think AES is the main concern here. Each introduction request is 512 bytes (AFAIK), so with a PoW verification performance of 2000 requests per second, the top-half handler will bottleneck at ~1 MB/s.
Are there other reasons to do stochastic sampling over a priority queue, given this top-half and bottom-half design?
After thinking about it more, I would recommend starting with a simple priority queue as proposed. More complex solutions can be implemented later if field testing finds issues.
T.