[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]

Re: Refactored or_connection_t buffers into cell queues.

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

WFQ (weighted fair queueing)
	(could be rather roughly summarized as round-robin queuing)

FIFO w/ 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.

W. Stevens,  TCP Slow Start, Congestion Avoidance, Fast Retransmit, and
	Fast Recovery Algorithms, RFC2001

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.

[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."