111-local-traffic-priority.txt 7.5 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153
  1. Filename: 111-local-traffic-priority.txt
  2. Title: Prioritizing local traffic over relayed traffic
  3. Version: $Revision$
  4. Last-Modified: $Date$
  5. Author: Roger Dingledine
  6. Created: 14-Mar-2007
  7. Status: Closed
  8. Implemented-In: 0.2.0.x
  9. Overview:
  10. We describe some ways to let Tor users operate as a relay and enforce
  11. rate limiting for relayed traffic without impacting their locally
  12. initiated traffic.
  13. Motivation:
  14. Right now we encourage people who use Tor as a client to configure it
  15. as a relay too ("just click the button in Vidalia"). Most of these users
  16. are on asymmetric links, meaning they have a lot more download capacity
  17. than upload capacity. But if they enable rate limiting too, suddenly
  18. they're limited to the same download capacity as upload capacity. And
  19. they have to enable rate limiting, or their upstream pipe gets filled
  20. up, starts dropping packets, and now their net connection doesn't work
  21. even for non-Tor stuff. So they end up turning off the relaying part
  22. so they can use Tor (and other applications) again.
  23. So far this hasn't mattered that much: most of our fast relays are
  24. being operated only in relay mode, so the rate limiting makes sense
  25. for them. But if we want to be able to attract many more relays in
  26. the future, we need to let ordinary users act as relays too.
  27. Further, as we begin to deploy the blocking-resistance design and we
  28. rely on ordinary users to click the "Tor for Freedom" button, this
  29. limitation will become a serious stumbling block to getting volunteers
  30. to act as bridges.
  31. The problem:
  32. Tor implements its rate limiting on the 'read' side by only reading
  33. a certain number of bytes from the network in each second. If it has
  34. emptied its token bucket, it doesn't read any more from the network;
  35. eventually TCP notices and stalls until we resume reading. But if we
  36. want to have two classes of service, we can't know what class a given
  37. incoming cell will be until we look at it, at which point we've already
  38. read it.
  39. Some options:
  40. Option 1: read when our token bucket is full enough, and if it turns
  41. out that what we read was local traffic, then add the tokens back into
  42. the token bucket. This will work when local traffic load alternates
  43. with relayed traffic load; but it's a poor option in general, because
  44. when we're receiving both local and relayed traffic, there are plenty
  45. of cases where we'll end up with an empty token bucket, and then we're
  46. back where we were before.
  47. More generally, notice that our problem is easy when a given TCP
  48. connection either has entirely local circuits or entirely relayed
  49. circuits. In fact, even if they are both present, if one class is
  50. entirely idle (none of its circuits have sent or received in the past
  51. N seconds), we can ignore that class until it wakes up again. So it
  52. only gets complex when a single connection contains active circuits
  53. of both classes.
  54. Next, notice that local traffic uses only the entry guards, whereas
  55. relayed traffic likely doesn't. So if we're a bridge handling just
  56. a few users, the expected number of overlapping connections would be
  57. almost zero, and even if we're a full relay the number of overlapping
  58. connections will be quite small.
  59. Option 2: build separate TCP connections for local traffic and for
  60. relayed traffic. In practice this will actually only require a few
  61. extra TCP connections: we would only need redundant TCP connections
  62. to at most the number of entry guards in use.
  63. However, this approach has some drawbacks. First, if the remote side
  64. wants to extend a circuit to you, how does it know which TCP connection
  65. to send it on? We would need some extra scheme to label some connections
  66. "client-only" during construction. Perhaps we could do this by seeing
  67. whether any circuit was made via CREATE_FAST; but this still opens
  68. up a race condition where the other side sends a create request
  69. immediately. The only ways I can imagine to avoid the race entirely
  70. are to specify our preference in the VERSIONS cell, or to add some
  71. sort of "nope, not this connection, why don't you try another rather
  72. than failing" response to create cells, or to forbid create cells on
  73. connections that you didn't initiate and on which you haven't seen
  74. any circuit creation requests yet -- this last one would lead to a bit
  75. more connection bloat but doesn't seem so bad. And we already accept
  76. this race for the case where directory authorities establish new TCP
  77. connections periodically to check reachability, and then hope to hang
  78. up on them soon after. (In any case this issue is moot for bridges,
  79. since each destination will be one-way with respect to extend requests:
  80. either receiving extend requests from bridge users or sending extend
  81. requests to the Tor server, never both.)
  82. The second problem with option 2 is that using two TCP connections
  83. reveals that there are two classes of traffic (and probably quickly
  84. reveals which is which, based on throughput). Now, it's unclear whether
  85. this information is already available to the other relay -- he would
  86. easily be able to tell that some circuits are fast and some are rate
  87. limited, after all -- but it would be nice to not add even more ways to
  88. leak that information. Also, it's less clear that an external observer
  89. already has this information if the circuits are all bundled together,
  90. and for this case it's worth trying to protect it.
  91. Option 3: tell the other side about our rate limiting rules. When we
  92. establish the TCP connection, specify the different policy classes we
  93. have configured. Each time we extend a circuit, specify which policy
  94. class that circuit should be part of. Then hope the other side obeys
  95. our wishes. (If he doesn't, hang up on him.) Besides the design and
  96. coordination hassles involved in this approach, there's a big problem:
  97. our rate limiting classes apply to all our connections, not just
  98. pairwise connections. How does one server we're connected to know how
  99. much of our bucket has already been spent by another? I could imagine
  100. a complex and inefficient "ok, now you can send me those two more cells
  101. that you've got queued" protocol. I'm not sure how else we could do it.
  102. (Gosh. How could UDP designs possibly be compatible with rate limiting
  103. with multiple bucket sizes?)
  104. Option 4: put both classes of circuits over a single connection, and
  105. keep track of the last time we read or wrote a high-priority cell. If
  106. it's been less than N seconds, give the whole connection high priority,
  107. else give the whole connection low priority.
  108. Option 5: put both classes of circuits over a single connection, and
  109. play a complex juggling game by periodically telling the remote side
  110. what rate limits to set for that connection, so you end up giving
  111. priority to the right connections but still stick to roughly your
  112. intended bandwidthrate and relaybandwidthrate.
  113. Option 6: ?
  114. Prognosis:
  115. Nick really didn't like option 2 because of the partitioning questions.
  116. I've put option 4 into place as of Tor 0.2.0.3-alpha.
  117. In terms of implementation, it will be easy: just add a time_t to
  118. or_connection_t that specifies client_used (used by the initiator
  119. of the connection to rate limit it differently depending on how
  120. recently the time_t was reset). We currently update client_used
  121. in three places:
  122. - command_process_relay_cell() when we receive a relay cell for
  123. an origin circuit.
  124. - relay_send_command_from_edge() when we send a relay cell for
  125. an origin circuit.
  126. - circuit_deliver_create_cell() when send a create cell.
  127. We could probably remove the third case and it would still work,
  128. but hey.