Refactored or_connection_t buffers into cell queues.

[Cat Okita]

On Tue, 27 Mar 2007, Nick Mathewson wrote:
> Implementation issues:

Nick suggested that I post to or-dev, rather than throwing things at him
in irc:

> 1) I've also done a patch to stop reading on edge connections when the
>   circuit gets too full, and start reading on the edge connections
>   again when the circuit gets emptier.
>
>   [Maybe we should aim to read from edge connections at constant
>   rates rather than stopping and starting like this.  That will be
>   harder, but will probably give better TCP performance.]

The stopping and starting that you're describing seems like a recipe
for performance issues.

Although the standard mechanisms for queue management[0] would typically
be one of FIFO w/tail-drop, some sort of weighted fair queuing, or RED,
the need to not drop cells at all means that any of the above would be
potentially problematic.

RED (Random Early Detection) queue management
 	http://www.icir.org/floyd/red.html

WFQ (weighted fair queueing)
 	http://en.wikipedia.org/wiki/Weighted_fair_queuing
 	(could be rather roughly summarized as round-robin queuing)

FIFO w/ tail drop
 	http://en.wikipedia.org/wiki/Tail_drop
 	(basically drops newly arrived packets until the queue is free again)

Perhaps implementing something like the standard Van Jacobson backoff 
mechanisms used in TCP for congestion avoidance might be useful.

V. Jacobson, Congestion Avoidance and Control, ACM SIGCOMM '88, August 1988.
 	http://www-nrg.ee.lbl.gov/papers/congavoid.pdf

W. Stevens,  TCP Slow Start, Congestion Avoidance, Fast Retransmit, and
 	Fast Recovery Algorithms, RFC2001
 	http://ietf.org/rfc/rfc2001.txt

IIRC, TCP/IP Illustrated V1/V2 have more specific information (unfortunately
I seem to have done something unhelpful with my copies, and thus can't
be more usefully direct).

> 6) Cells are about to become the most heavily allocated and freed
>   structures in Tor.  This is probably going to incur some malloc
>   overhead, especially on platforms where malloc() sucks.  Since
>   cells are fixed-size, this arguably calls for arena allocation.

Somehow cells always reminds me of ATM - looking at queue management
certainly doesn't hinder that impression.

cheers!
[0] Not that queue management and QoS aren't their own set of black magic
==========================================================================
"A cat spends her life conflicted between a deep, passionate and profound
desire for fish and an equally deep, passionate and profound desire to
avoid getting wet.  This is the defining metaphor of my life right now."