Filename: 341-better-oos.md Title: A better algorithm for out-of-sockets eviction Author: Nick Mathewson Created: 25 July 2022 Status: Open
Our existing algorithm for handling an out-of-sockets condition needs
improvement. It only handles sockets used for OR connections, and
prioritizes those with more circuits. Because of these weaknesses, the
algorithm is trivial to circumvent, and it’s disabled by default with
Here we propose a new algorithm for choosing which connections to close
when we’re out of sockets. In summary, the new algorithm works by
deciding which kinds of connections we have “too many” of, and then by
closing excess connections of each kind. The algorithm for selecting
connections of each kind is different.
We want to keep a healthy mix of connections running; favoring one kind
of connection over another gives the attacker a fine way to starve the
disfavored connections by making a bunch of the favored kind.
The correct mix of connections depends on the type of service we are
providing. Everywhere except authorities, for example, inbound
directory connections are perfectly fine to close, since nothing in our
protocol actually generates them.
In general, we would prefer to close DirPort connections, then Exit
connections, then OR connections.
The priority with which to close connections is different depending on
the connection type. “Age of connection” or “number of circuits” may be
a fine metric for how truly used an OR connection is, but for a DirPort
connection, high age is suspicious.
Define a “candidate” connection as one that has a socket, and is either
an exit stream, an inbound directory stream, or an OR connection.
(Note that OR connections can be from clients, relays, or bridges. Note
that ordinary relays should not get directory streams that use sockets,
since clients always use
BEGIN_DIR to create tunneled directory
In all of the following, treat subtraction as saturating at zero. In
other words, when you see “A - B” below, read it as “MAX(A-B, 0)”.
When we are find that we are low on sockets, we pick a number of sockets
that we want to close according to our existing algorithm. (That is, we
try to close 1/4 of our maximum sockets if we have reached our upper
limit, or 1/10 of our maximum sockets if we have encountered a failure
from socket(2).) Call this
Then we decide which sockets to target based on this algorithm.
Consider the total number of sockets used for exit streams
N_EXIT), the total number used for inbound directory streams
N_DIR), and the total number used for OR connections (
(In these calculations, we exclude connections that are already
marked to be closed.) Call the total
N_CONN = N_DIR + N_OR + N_EXIT. Define
N_RETAIN = N_CONN - N_CLOSE.
Compute how many connections of each type are “in excess”. First,
calculate our target proportions:
- If we are an authority, let
T_DIR= 1. Otherwise set
T_DIR = 0.1.
- If we are an exit or we are running an onion service, let
T_EXIT = 2. Otherwise let
T_EXIT = 0.1.
TODO: Should those numbers be consensus parameters?
These numbers define the relative proportions of connections that
we would be willing to retain retain in our final mix. Compute a
number of excess connections of each type by calculating.
T_TOTAL = T_OR + T_DIR + T_EXIT. EXCESS_DIR = N_DIR - N_RETAIN * (T_DIR / T_TOTAL) EXCESS_EXIT = N_EXIT - N_RETAIN * (T_EXIT / T_TOTAL) EXCESS_OR = N_OR - N_RETAIN * (T_OR / T_TOTAL)
- Finally, divide N_CLOSE among the different types of excess
connections, assigning first to excess directory connections, then
excess exit connections, and finally to excess OR connections.
CLOSE_DIR = MIN(EXCESS_DIR, N_CLOSE) N_CLOSE := N_CLOSE - CLOSE_DIR CLOSE_EXIT = MIN(EXCESS_EXIT, N_CLOSE) N_CLOSE := N_CLOSE - CLOSE_EXIT CLOSE_OR = MIN(EXCESS_OR, N_CLOSE)
We will try to close
CLOSE_DIR directory connections,
exit connections, and
CLOSE_OR OR connections.
We want to close a certain number of directory connections. To select
our targets, we sort first by the number of directory connections from
a similar address (see “similar address” below) and then by their age,
preferring to close the oldest ones first.
This approach defeats “many requests from the same address” and “Open
a connection and hold it open, and do so from many addresses”. It
doesn’t do such a great job with defeating “open and close frequently
and do so on many addresses.”
Note that fallback directories do not typically use sockets for
handling directory connections: theirs are usually created with
We want to close a certain number of exit connections. To do this, we
pick an exit connection at random, then close its circuit along with
all the other exit connections on the same circuit. Then we repeat
until we have closed at least our target number of exit connections.
This approach probabilistically favors closing circuits with a large
number of sockets open, regardless of how long those sockets have been
open. This defeats the easiest way of opening a large number of exit
streams (“open them all on once circuit”) without making the
counter-approach (“open each exit stream on a its own circuit”) much
We want to close a certain number of OR connections, to clients, bridges, or
To do this, we first close OR connections with zero circuits. Then we
close all OR connections but the most recent 2 from each “similar
address”. Then we close OR connections at random from among those not
to a recognized relay in the latest directory. Finally, we close OR
connections at random.
We used to unconditionally prefer to close connections with fewer
circuits. That’s trivial for an adversary to circumvent, though: they
can just open a bunch of circuits on their bogus OR connections, and
force us to preferentially close circuits from real clients, bridges,
Note that some connections that seem like client connections (“not
from relays in the latest directory”) are actually those created by
We define two connections as having a similar address if they are in the
same IPv4 /30, or if they are in the same IPv6 /90.
This proposal was inspired by a set of OOS improvements from