[or-cvs] r18816: {projects} add in the first discussion about round-robin and rate limit (projects/performance)

[arma@xxxxxxxx]

Author: arma
Date: 2009-03-08 23:34:12 -0400 (Sun, 08 Mar 2009)
New Revision: 18816

Added:
   projects/performance/extensiontimes.pdf
Modified:
   projects/performance/performance.tex
Log:
add in the first discussion about round-robin and rate limiting,
plus karsten's extension-times graph


Added: projects/performance/extensiontimes.pdf
===================================================================
(Binary files differ)


Property changes on: projects/performance/extensiontimes.pdf
___________________________________________________________________
Added: svn:mime-type
   + application/pdf

Modified: projects/performance/performance.tex
===================================================================
--- projects/performance/performance.tex	2009-03-09 02:46:18 UTC (rev 18815)
+++ projects/performance/performance.tex	2009-03-09 03:34:12 UTC (rev 18816)
@@ -171,9 +171,9 @@
 currently working on fixing bugs in OpenSSL's implementation of DTLS along
 with other core libraries that we'd need to use if we go this direction.
 
-{\bf Impact}: High
+{\bf Impact}: High.
 
-{\bf Effort}: High effort to get all the pieces in place
+{\bf Effort}: High effort to get all the pieces in place.
 
 {\bf Risk}: High risk that it would need further work to get right.
 
@@ -233,31 +233,8 @@
 
 %\subsection{Priority for circuit control cells, e.g. circuit creation}
 
-\subsection{Our round-robin and rate limiting is too granular}
 
-we refill our token buckets once a second. this causes irregular humps
-in the network traffic.
-[insert karsten's graph here]
 
-if we spread things out better, then we could reduce latency by
-perhaps multiple seconds. or none. it really depends how full the
-buffers are.
-
-also, let's say we have 15 connections that want attention
-and we have n tokens for the second to divide up among them
-and each act of writing onto the connection incurs overhead from tls header
-if we do it on a per-second, we can write more onto a given conn, because we
-have more of n to divvy up
-if we do it every 100ms, we only have n/10 to divvy up, so if we're trying
-to round robin fairly, everybody gets a tinier amount
-in fact, if n is small, and we can't really write less than 512 bytes per
-go, we're going to have to get smarter about randomly picking a conn to use,
-or skipping ones we fed last time, or something. or some will starve
-entirely.
-(right now, i think some starve entirely if you have more than n conns and
-you rate limit to n cells per second)
-
-
 \section{Some users add way too much load}
 \label{sec:too-much-load}
 
@@ -277,6 +254,7 @@
 for better latency and worse throughput.
 
 \subsection{Squeeze over-active circuits}
+\label{sec:squeeze}
 
 The Tor 0.2.0.x release included this change:
 \begin{verbatim}
@@ -797,6 +775,76 @@
 
 \section{Better handling of high/variable latency and failures}
 
+\subsection{Our round-robin and rate limiting is too granular}
+
+Tor's rate limiting uses a token bucket approach to enforce a long-term
+average rate of incoming and outgoing bytes, while still permitting
+short-term bursts above the allowed bandwidth. Each token represents
+permission to send another byte onto the network (or read from the
+network). Every second new tokens are added, up to some cap (the
+\emph{bucket size}).
+
+So Tor relays that have cells buffered waiting to go out onto the network
+will wait until the new second arrives, and then deliver as many cells
+as they can. In practice, this behavior results in traffic `bumps'
+at the beginning of each second, with little network traffic the rest
+of the time. Mike and Karsten have been collecting data from circuit
+extension times (how long it takes to establish each hop of a circuit);
+the bumps are easily seen in \prettyref{fig:extension-times}.
+
+\begin{figure}
+\includegraphics[width=\textwidth]{extensiontimes}
+\caption{Number of seconds it takes to establish each hop of a 3-hop
+circuit. The higher density of samples around 2s, 3s, etc indicate that
+Tor's rate limiting is introducing extra delay into the responses.}
+\label{fig:extension-times}
+\end{figure}
+
+Our original theory was that one-second granularity should be sufficient:
+cells will go out as quickly as possible while the bucket still has
+tokens for that second, and once it's empty there's nothing we can do
+but wait until the next second for permission to send more cells.
+
+We should explore refilling the buckets more often than once a second,
+for three reasons. First, we'll get a better intuition about how full
+the buffers really are: if we spread things out better, then we could
+reduce latency by perhaps multiple seconds. Second, spikes-and-silence is
+not friendly for TCP, so averaging the flows ourselves might mean much
+smoother network performance. Third, sub-second precision will give us
+more flexibility in our priority strategies from \prettyref{sec:squeeze}.
+
+On the other hand, we don't want to go too far: cells are 512 bytes,
+so it isn't useful to think in units smaller than that. Also, every
+network write operation carries with it overhead from the TLS record,
+the TCP header, and the IP packet header. Finally, network transmission
+unit (MTU) sizes vary, but if we could use a larger packet on the wire,
+then we're not being as efficient as we could be.
+
+%also, let's say we have 15 connections that want attention
+%and we have n tokens for the second to divide up among them
+%and each act of writing onto the connection incurs overhead from tls header
+%if we do it on a per-second, we can write more onto a given conn, because we
+%have more of n to divvy up
+%if we do it every 100ms, we only have n/10 to divvy up, so if we're trying
+%to round robin fairly, everybody gets a tinier amount
+%in fact, if n is small, and we can't really write less than 512 bytes per
+%go, we're going to have to get smarter about randomly picking a conn to use,
+%or skipping ones we fed last time, or something. or some will starve
+%entirely.
+%(right now, i think some starve entirely if you have more than n conns and
+%you rate limit to n cells per second)
+
+{\bf Impact}: Low-Medium.
+
+{\bf Effort}: Medium.
+
+{\bf Risk}: Low, unless we add in bad feedback effects and don't notice.
+
+{\bf Plan}: We should continue collecting metrics to get better
+intuition here. While we're designing priority stategies for
+\prettyref{sec:squeeze}, we should keep the option of higher-resolution
+rate-limiting in mind.
+
 \subsection{The switch to Polipo: prefetching, pipelining, etc}
 \subsection{better timeouts for giving up on circuits and trying a new one}
 \subsection{when a circuit has too many streams on it, move to a new one}