DiProber: Estimating Relays Capacities in Underloaded Anonymous Communication Networks

Tor is a widely used anonymous communication network that routes and anonymizes users' internet traffic through thousands of relays. To create a path, Tor authorities estimate relay capacities based on the bandwidth of observation probes assigned to each relay. These estimates are used to generate a probability distribution over relays for incoming users to choose from. However, the currently implemented estimation algorithm generates inaccurate estimates, resulting in underutilization of the network and unfair distribution of capacities between users. To address this, we propose DiProber, a new algorithm that uses two probes per relay and maximum likelihood to more accurately estimate relay capacities. Our new technique works particularly well in underutilized networks where users have low demand on the Tor network.