tor-dev

tor-dev@lists.torproject.org

3580 discussions

Proposal 182: Credit Bucket
by Nick Mathewson 27 Jun '11

27 Jun '11

Here's a proposal by Florian and Björn about improving our queueing times. Per usual procedure, I'm sending it here as I put it in the proposals directory. Filename: 182-creditbucket.txt Title: Credit Bucket Author: Florian Tschorsch and Björn Scheuermann Created: 22 Jun 2011 Status: Draft Overview: The following proposal targets the reduction of queuing times in onion routers. In particular, we focus on the token bucket algorithm in Tor and point out that current usage unnecessarily locks cells for long time spans. We propose a non-intrusive change in Tor's design which overcomes the deficiencies. Motivation and Background: Cell statistics from the Tor network [1] reveal that cells reside in individual onion routers' cell queues for up to several seconds. These queuing times increase the end-to-end delay very significantly and are apparently the largest contributor to overall cell latency in Tor. In Tor there exist multiple token buckets on different logical levels. They all work independently. They are used to limit the up- and downstream of an onion router. All token buckets are refilled every second with a constant amount of tokens that depends on the configured bandwidth limits. For example, the so-called RelayedTokenBucket limits relay traffic only. All read data of incoming connections are bound to a dedicated read token bucket. An analogous mechanism exists for written data leaving the onion router. We were able to identify the specific usage and implementation of the token bucket algorithm as one cause for very high (and unnecessary) queuing times in an onion router. We observe that the token buckets in Tor are (surprisingly at a first glance) allowed to take on negative fill levels. This is justified by the TLS connections between onion routers where whole TLS records need to be processed. The token bucket on the incoming side (i.e., the one which determines at which rate it is allowed to read from incoming TCP connections) in particular often runs into non-negligible negative fill levels. As a consequence of this behavior, sometimes slightly more data is read than it would be admissible upon strict interpretation of the token bucket concept. However, the token bucket for limiting the outgoing rate does not take on negative fill levels equally often. Consequently, it regularly happens that somewhat more data are read on the incoming side than the outgoing token bucket allows to be written during the same cycle, even if their configured data rates are the same. The respective cells will thus not be allowed to leave the onion router immediately. They will thus necessarily be queued for at least as long as it takes until the token bucket on the outgoing side is refilled again. The refill interval currently is, as mentioned before, one second -- so, these cells are delayed for a very substantial time. In summary, one could say that the two buckets, on the incoming and outgoing side, work like a double door system and frequently lock cells for a full token bucket refill interval length. General Design: In order to overcome the described problem, we propose the following changes related to the token bucket algorithm. We observe that the token bucket on the outgoing connections with its current design is contra productive in the sense of queuing times. We therefore propose modifications to the token bucket algorithm that will eliminate the "double door effect" discussed above. Let us start from Tor's current approach: Thus, we have a regular token bucket on the reading side with a certain rate and a certain burst size. Let x denote the current amount of tokens in the bucket. On the outgoing side we need something appropriate that monitors and constrains the outgoing rate, but at the same time avoids holding back cells (cf. double door effects) whenever possible. Here we propose something that adopts the role of a token bucket, but realizes this functionality in a slightly different way. We call it a "credit bucket". Like a token bucket, the credit bucket also has a current fill level, denoted by y. However, the credit bucket is refilled in a different way. To understand how it works, let us look at the possible operations: As said, x is the fill level of a regular token bucket on the incoming side and thus gets incremented periodically according to the configured rate. No changes here. If x<=0, we are obviously not allowed to read. If x>0, we are allowed to read up to x bytes of incoming data. If k bytes are read (k<=x), then we update x and y as follows: x = x - k (1) y = y + k (2) (1) is the standard token bucket operation on the incoming side. Whenever data is admitted in, though, an additional operation is performed: (2) allocates the same number of bytes on the outgoing side, which will later on allow the same number of bytes to leave the onion router without any delays. If y + x > -M, we are allowed to write up to y + x + M bytes on the outgoing side, where M is a positive constant. M specifies a burst size for the outgoing side. M should be higher than the number of tokens that get refilled during a refill interval, we would suggest to have M in the order of a few seconds "worth" of data. Now if k bytes are written on the outgoing side, we proceed as follows: If k <= y then y = y - k In this case we use "saved" credits, previously allocated on the incoming side when incoming data has been processed. If k > y then y = 0 and x = x - (k-y) We generated additional traffic in the onion router, so that more data is to be sent than has been read (the credit is not sufficient). We therefore "steal" tokens from the token buffer on the incoming side to compensate for the additionally generated data. This will result in correspondingly less data being read on the incoming side subsequently. As a result of such an operation, the token bucket fill level x on the incoming side may become negative (but it can never fall below -M). If y + x <= -M then outgoing data will be held back. This may lead to double-door effects, but only in extreme cases where the outgoing traffic largely exceeds the incoming traffic, so that the outgoing bursts size M is exceeded. Aside from short-term bursts of configurable size (as with every token bucket), this procedure guarantees that the configured rate may never be exceeded (on the application layer, that is; as with the current implementation, an attacker may easily cause the onion router to arbitrarily exceed the limits on the lower layers). Over time, we never send more data than the configured rate: every sent byte needs a corresponding token on the incoming side; this token must either have been consumed by an incoming byte before (it then became a "credit"), or it is "stolen" from the incoming bucket to compensate for data generated within the onion router. Specific Design Changes: In the following we briefly point out the specific changes that need to be done in Tor's source code. By doing so one can see how non intrusive our modifications are. First we need to address the bucket increment and decrement operations. According to the described logic above, this should be done in the methods connection_bucket_refill and connection_buckets_decrement respectively. In particular allocating, saving and "stealing" of tokens need to be considered here. Second the rate limiting, i.e. the amount we are allowed to write (connection_bucket_write_limit) needs to be adapted in lines of the credit bucket logic. Meaning in order to avoid the here identified unnecessary queuing of cells, we need to consider the new burst parameter M. Here we also need to take non rate limited connections such as from the localhost into account. The rate limiting on the reading side remains the same. At last we need to find good values/ ratios for the parameter M such that the trade off between avoiding "double door effects" and maintaining strict rate limits work as expected. As future work and after insights about the performance gain of the here described proposal we need to find a way to implement this both using bufferevent rate limiting with libevent 2.3.x and Tor's rate limiting code. Conclusion: This proposal can be implemented with moderate effort and requires changes only at the points where currently the token bucket operations are performed. We feel that this is not the be-all and end-all solution, because it again introduces a feedback loop between the incoming and the outgoing side. We therefore still hope that we will be able to come to a both simpler and more effective design in the future. However, we believe that what we proposed here is a good compromise between avoiding double-door effects to the furthest possible extent, strictly enforcing an application-layer data rate, and keeping the extent of changes to the code small. Feedback is highly appreciated. References: [1] Karsten Loesing. Analysis of Circuit Queues in Tor. August 25, 2009. [2] https://trac.torproject.org/projects/tor/wiki/sponsors/SponsorD/June2011

1 0

Reg : using the keep alive messages
by Sambuddho Chakravarty 27 Jun '11

27 Jun '11

Hi All I read in the Tor design spec that Tor control protocol supports keepalive messages which could be used for link padding . I wonder if anyone has ever explored using them... Thanks Sambuddho

2 4

TOR control protocol timeout
by Sean Robinson 25 Jun '11

25 Jun '11

Is there a defined timeout for the TOR control protocol? How long should a control port client wait around for socket data when reading? Or writing? The only references to timeouts that I find in control-spec.txt are about circuit and stream timeouts reported back through the control port. -- Sean Robinson WiFi Radar - http://wifi-radar.berlios.de Python WiFi - http://pythonwifi.wikispot.org pymnl - http://pymnl.wikispot.org

2 4

Tor AF independence patch - first big step to Tor IPv6
by Jeroen Massar 20 Jun '11

20 Jun '11

Hi, As this is World IPv6 day, let me present the first big step to Tor IPv6: the Address Family independence Patch ;) https://unfix.org/projects/ipv6/tor/tor-af-independent.diff it is diff against a recent git checkout and should apply more or less cleanly. Why AF independence[1,2] and not "IPv6 patch", well, for a program to be able to support IPv6 it should first not care about IP in the first place. With Tor that is a tricky thing as it actually needs to know about IP for quite a few places. As such this patch primary function is to make most functions use toraddr_t, that way both IPv6 and IPv4 are supported. Note that a lot of functionality for supporting IPv6 (or any other IP protocol in the longer term) is already present in current versions of Tor (even unittests are present already!). Note also that this is not a 'true' AF indepencence patch as in that case we would have to swap toraddr_t with a sockaddr_storage structure, which, when recompiled, would be true AF independent. In the case though that ever a new IP-alike protocol arises and then we still use BSD style sockets, this patch should make it easy to use that new address family too, but don't hold your breath ;) The problem with that though is that at this stage that means that everywhere IPv6 can be stuck just like IPv4 while these should be separate. And to make it a bit worse, one should actually have them also properly in the packets being sent between nodes and there is no separation between exit policies etc. There is thus a lot to discuss on this subject, and one of the first things that really need to be done is ORMultiPort (proposal 118) to be able to separate IPv4 and IPv6 ports. A question there also becomes, do we want to show a Tor node as separate IPv4 and IPv6 routers, or are they to be seen as one, if it is one, we require the above ORMultiport, so that we can have multiple IP addresses and ports on a single node. As such, I suggest we have a big discussion on the flaws of my patch and how to resolve some of the remaining problems and then start moving work to the ORMultPort patch so that we can start enabling IPv6 everywhere, as then we are getting quite close. And maybe, it could be useful to have a special branch on torproject's git server for this, as it is quite a bit of patch ;) Greets, Jeroen (fuzzel on #tor-dev) [1] = http://www.kame.net/newsletter/19980604/ [2] = http://gsyc.escet.urjc.es/~eva/IPv6-web/ipv6.html

2 3

[PATCH] Allow tordnsel to build on Squeeze
by Jérémy Bobbio 20 Jun '11

20 Jun '11

Hi! Quoting IRC: <phobos> I give up on tordnsel, I'm unable to get git head to compile in squeeze Attached are 3 patches that allow tordnsel to build on a Squeeze system. I unfortunately lack a test environment to ensure that the resulting binary works fine. Haskell has proven quite trusty, though. The work needed to make it work for the next versions of GHC (7.x) is going to be an order of magnitude bigger, so it probably makes sense to get the Python implementation working until Squeeze is EOL. Cheers, -- Jérémy Bobbio .''`. lunar(a)debian.org : :Ⓐ : # apt-get install anarchism `. `'` `-

2 1

RFC: remove TorUtil.Enum
by Sean Robinson 18 Jun '11

18 Jun '11

I have been reviewing the TorCtl package and I will be submitting tickets (usually with patches) for clean-ups, fixes, etc. Before I submit a ticket for removing TorUtil.Enum, I wanted to hear from other devs. There are no users of this class within TorCtl, so Enum is now cruft. Does anyone have a problem with removing Enum? If I do not get negative feedback about this patch, I will submit it later in the week. The following patch is also attached to this message as a gzipped patch file. diff --git a/TorUtil.py b/TorUtil.py index 3163d09..1d27144 100644 --- a/TorUtil.py +++ b/TorUtil.py @@ -22,7 +22,7 @@ if sys.version_info < (2, 5): else: from hashlib import sha1 -__all__ = ["Enum", "Enum2", "Callable", "sort_list", "quote", "escape_dots", "unescape_dots", +__all__ = ["Enum2", "Callable", "sort_list", "quote", "escape_dots", "unescape_dots", "BufSock", "secret_to_key", "urandom_rng", "s2k_gen", "s2k_check", "plog", "ListenSocket", "zprob", "logfile", "loglevel", "loglevels"] @@ -127,16 +127,6 @@ def read_config(filename): loglevel = config.get('TorCtl', 'loglevel') -class Enum(object): - """ Defines an ordered dense name-to-number 1-1 mapping """ - def __init__(self, start, names): - self.nameOf = {} - idx = start - for name in names: - setattr(self,name,idx) - self.nameOf[idx] = name - idx += 1 - class Enum2(object): """ Defines an ordered sparse name-to-number 1-1 mapping """ def __init__(self, **args): -- 1.7.5.1 -- Sean Robinson WiFi Radar - http://wifi-radar.berlios.de Python WiFi - http://pythonwifi.wikispot.org pymnl - http://pymnl.wikispot.org

2 2

Looking at Bridge users oddities
by Arturo 17 Jun '11

17 Jun '11

Hi, Jake made me notice that there has been a huge spike in tor bridge users in Italy in the past week (https://metrics.torproject.org/users.html?graph=bridge-users&start=2011-02-…). This prompted me to hack up a quick little script to analyse the Tor bridge usage data and see if it is possible to draw some conclusions from some patterns that emerge in it. I don't feel like expressing a personal an opinion at this point on what this data might mean, but I think spikes in Bridge usage could be used do draw conclusions on socio-political happenings. What the script does is it basically looks for spikes in Bridge traffic by giving it a time frame and a factor for triggering the alert. As already said it's just a quick hack so don't expect it to be performing or even well written :P. A couple of neat things that came out: factor | date1 date2 1: users at date1 2: users at date2 (country code) 23.0512820513 | 2011-06-10 2011-05-29 1: 1798 2: 78 (es) 22.0707070707 | 2011-06-10 2011-06-05 1: 4370 2: 198 (it) 4.14 | 2011-06-11 2011-06-04 1: 207 2: 50 (tw) 5.13333333333 | 2011-06-11 2011-06-05 1: 231 2: 45 (ar) 5.42857142857 | 2011-06-11 2011-06-05 1: 836 2: 154 (br) 4.38181818182 | 2011-06-11 2011-06-01 1: 241 2: 55 (il) 16.5208333333 | 2011-02-15 2011-01-18 1: 48 2: 793 (de) 15.4285714286 | 2010-08-23 2010-07-26 1: 648 2: 42 (au) 13.7916666667 | 2011-03-11 2011-02-15 1: 1655 2: 120 (sa) A one liner to get some interesting stats: python bridge-user-alert.py -f 4 | sort -g Hope somebody finds this little research useful, Cheers, Art.

1 0

Re: [tor-dev] license question
by Ted Smith 16 Jun '11

16 Jun '11

On Thu, 2011-06-16 at 16:51 +0200, Frederic Bor wrote: > Hello, > > > Im currently implementing transparent proxying for tor with Layered Service > Provider feature on windows. Microsoft provides a sample to demonstrate how > to implement an empty LSP (this is a lot of work, even to do nothing). This > sample is distributed under the license attached in this email. I have been > advised on #tor-dev to ask here about its compatibility with 3-clause BSD. > > It seems compatible to me but the following restriction may be a problem in > an open source context: > > "You may not [...] modify or distribute the source code of any Distributable > Code so that any part of it becomes subject to an Excluded License. An > Excluded License is one that requires, as a condition of use, modification > or distribution, that: > - the code be disclosed or distributed in source code form, or > - others have the right to modify it." > > The wording "requires, as a condition of use, modification or distribution" > seems to allow to use the sample in tor, since there is no such requirement > in 3-clause BSD. > > Does this seem right to you? You might want to ask licensing(a)fsf.org -- that looks like a clause designed to exclude copyleft licenses, so they'd probably know about it and what effects it would have on non-copyleft licenses.

1 0

license question
by Frederic Bor 16 Jun '11

16 Jun '11

Hello, Im currently implementing transparent proxying for tor with Layered Service Provider feature on windows. Microsoft provides a sample to demonstrate how to implement an empty LSP (this is a lot of work, even to do nothing). This sample is distributed under the license attached in this email. I have been advised on #tor-dev to ask here about its compatibility with 3-clause BSD. It seems compatible to me but the following restriction may be a problem in an open source context: "You may not [...] modify or distribute the source code of any Distributable Code so that any part of it becomes subject to an Excluded License. An Excluded License is one that requires, as a condition of use, modification or distribution, that: - the code be disclosed or distributed in source code form, or - others have the right to modify it." The wording "requires, as a condition of use, modification or distribution" seems to allow to use the sample in tor, since there is no such requirement in 3-clause BSD. Does this seem right to you? Cheers, Frederic

1 0

Thoughts on simplified packaging
by Andrew Lewman 15 Jun '11

15 Jun '11

As I talk to more and more people, they are confused by all of the different software packages we offer. From the simple, "I just want to be a relay, why is this so hard?" to "I just want to safely get to the BBC, I don't care about configuration and such. Can't you just make it a simple download and have it work by default?" I've written down my thoughts at https://svn.torproject.org/svn/projects/roadmaps/proposed-package-roadmap.t…. I'm looking for your thoughts and feedback. The goal is to simplify what we produce and make it easy for people to get the software and configuration they want. -- Andrew pgp 0x74ED336B

4 3

Jump to page:

2024

2023

2022

2021

2020

2019

2018

2017

2016

2015

2014

2013

2012

2011

tor-dev