problems with the aci range too small?

[Roger Dingledine <arma@mit.edu>]

The 'aci' is the identifier to tell an onion router which circuit we're
talking about. A given cell going along the network has an aci to indicate
the context for that cell. That's how we multiplex many circuits over
a single connection.

The aci is two bytes. In effect, it's even smaller than that: when onion
router A is opening a new circuit to B, it compares the IPs (and if IPs
are equal, then compares ports) and decides whether to write in the upper
or lower byte of the aci. This mechanism stops race conditions such as
where each side starts a new circuit to the other, happens to pick the
same aci, and thinks they're talking about one circuit when there are
really two.

However, it also means that each way between A and B can handle at most
256 circuits (512 if you count both ways). That's not all that many.
Further, so far I've reused Mat's algorithm for choosing an aci: "pick
a random one, see if it's used, if so try again." When most of the 256
are used, this process can take quite a while to find an unused one.

So I'd like to know what the constraints are on aci's. It doesn't seem
like they need to be random, since we're not trying to hide them from
anybody, and since it seems we need to trust the other guy to generate
an aci 'well' anyway.

Here's my first alternate design: keep aci at 16 bits, but use only the
first bit to declare which direction the aci is for. Then we've got 32k
possible circuits each way rather than 256.

Then as a bonus, rather than picking them randomly from the range (though
that's probably fine since we're unlikely to collide with 32k of them),
we can do a process similar to picking new process id's: we increment
the aci we're going to use each time we make a circuit, and every so
often we have to skip one since it's still 'alive' from the last cycle
through the aci space.

Paul, can you briefly describe the original plan for how to make this
work? It'd be good to know if the above design is better or worse.

Thanks,
--Roger