Never been KIST: Tor's congestion management blossoms with Kernel-informed socket transport
Rob Jansen, John Geddes, Chris Wacek, Micah Sherr, Paul F. Syverson · 2014
Tor’s growing popularity and user diversity has re-sulted in network performance problems that are not well understood. A large body of work has attempted to solve these problems without a complete understand-ing of where congestion occurs in Tor. In this paper, we first study congestion in Tor at individual relays as well as along the entire end-to-end Tor path and find that congestion occurs almost exclusively in egress ker-nel socket buffers. We then analyze Tor’s socket interac-tions and discover two major issues affecting congestion: Tor writes sockets sequentially, and Tor writes as much as possible to each socket. We thus design, implement, and test KIST: a new socket management algorithm that uses real-time kernel information to dynamically com-pute the amount to write to each socket while consider-ing all writable circuits when scheduling new cells. We find that, in the medians, KIST reduces circuit conges-tion by over 30 percent, reduces network latency by 18 percent, and increases network throughput by nearly 10 percent. We analyze the security of KIST and find an ac-ceptable performance and security trade-off, as it does not significantly affect the outcome of well-known la-tency and throughput attacks. While our focus is Tor, our techniques and observations should help analyze and improve overlay and application performance, both for security applications and in general. 1