Proposal 328: Make Relays Report When They Are Overloaded
Greetings, Attached is a proposal from Mike Perry and I. Merge requsest is here: https://gitlab.torproject.org/tpo/core/torspec/-/merge_requests/22 Cheers! David -- uSxMMaJozH7GAo7qjzhVUm5FDynPYtBfOeZcLS88XeU=
On Mon, Dec 07, 2020 at 03:06:43PM -0500, David Goulet wrote:
Greetings,
Attached is a proposal from Mike Perry and I. Merge requsest is here:
https://gitlab.torproject.org/tpo/core/torspec/-/merge_requests/22
Cheers! David
Nice! Is there a way to distinguish "not overloaded" from "does not support this extension"? (Ideally in a better way than checking the tor release version number and inferring when support was added?) -- Ian Goldberg Canada Research Chair in Privacy Enhancing Technologies Professor, Cheriton School of Computer Science University of Waterloo
On 07 Dec (15:36:53), Ian Goldberg wrote:
On Mon, Dec 07, 2020 at 03:06:43PM -0500, David Goulet wrote:
Greetings,
Attached is a proposal from Mike Perry and I. Merge requsest is here:
https://gitlab.torproject.org/tpo/core/torspec/-/merge_requests/22
Cheers! David
Nice!
Is there a way to distinguish "not overloaded" from "does not support this extension"? (Ideally in a better way than checking the tor release version number and inferring when support was added?)
Gooood point. So in theory, we have protocol version[1] in order to differentiate relays but I do not believe such a change would be a wise thing to use a new "Desc=" since tor will just ignore the unknown fields. The other reason for that is that "tor functionalities" as in to function properly won't depend on that descriptor field so it is a bit a stretch to justify this as a new protocol version :S ... So yeah, either one looks at the tor version or "you don't see it, not overloaded" which is ofc a lie until the entire network migrates. We expect our sbws (bandwidth scanner tool) to be the main customer for this. Cheers! David [1] https://gitweb.torproject.org/torspec.git/tree/tor-spec.txt#n2073 -- eWhbmX7lAl8F3ismKUL2eOiPlbv5U/7klKILIHs/590=
On Wed, Dec 09, 2020 at 10:09:51AM -0500, David Goulet wrote:
On 07 Dec (15:36:53), Ian Goldberg wrote:
On Mon, Dec 07, 2020 at 03:06:43PM -0500, David Goulet wrote:
Greetings,
Attached is a proposal from Mike Perry and I. Merge requsest is here:
https://gitlab.torproject.org/tpo/core/torspec/-/merge_requests/22
Cheers! David
Nice!
Is there a way to distinguish "not overloaded" from "does not support this extension"? (Ideally in a better way than checking the tor release version number and inferring when support was added?)
Gooood point.
So in theory, we have protocol version[1] in order to differentiate relays but I do not believe such a change would be a wise thing to use a new "Desc=" since tor will just ignore the unknown fields.
The other reason for that is that "tor functionalities" as in to function properly won't depend on that descriptor field so it is a bit a stretch to justify this as a new protocol version :S ...
So yeah, either one looks at the tor version or "you don't see it, not overloaded" which is ofc a lie until the entire network migrates.
What if, once a day or 72 hours or something, a relay explicitly outputs "not overloaded" if they're not?
We expect our sbws (bandwidth scanner tool) to be the main customer for this.
I know at least one research group that would be very interested in these stats as well. :-) -- Ian Goldberg Canada Research Chair in Privacy Enhancing Technologies Professor, Cheriton School of Computer Science University of Waterloo
On Wed, Dec 9, 2020 at 10:10 AM David Goulet <dgoulet@torproject.org> wrote:
On 07 Dec (15:36:53), Ian Goldberg wrote:
On Mon, Dec 07, 2020 at 03:06:43PM -0500, David Goulet wrote:
Greetings,
Attached is a proposal from Mike Perry and I. Merge requsest is here:
https://gitlab.torproject.org/tpo/core/torspec/-/merge_requests/22
Cheers! David
Nice!
Is there a way to distinguish "not overloaded" from "does not support this extension"? (Ideally in a better way than checking the tor release version number and inferring when support was added?)
Gooood point.
So in theory, we have protocol version[1] in order to differentiate relays but I do not believe such a change would be a wise thing to use a new "Desc=" since tor will just ignore the unknown fields.
The other reason for that is that "tor functionalities" as in to function properly won't depend on that descriptor field so it is a bit a stretch to justify this as a new protocol version :S ...
So yeah, either one looks at the tor version or "you don't see it, not overloaded" which is ofc a lie until the entire network migrates. We expect our sbws (bandwidth scanner tool) to be the main customer for this.
We could add a new element to this proposal, something like "I will tell you about overload information", or "I am not overloaded" or something like that? peace, -- Nick
On 12/7/20 14:06, David Goulet wrote:
Greetings,
Attached is a proposal from Mike Perry and I. Merge requsest is here:
https://gitlab.torproject.org/tpo/core/torspec/-/merge_requests/22
Disclaimer - As someone not very familiar with how tor load balancing works today, I might not be the target audience for this proposal :) Maybe it's putting the cart before the horse, but it might be helpful to have a more concrete proposal for how this data will be used, which in turn will help evaluate whether this is the right data to collect. e.g. naively I might assume the idea is to have some kind of exponential backoff for overloaded relays; but since the proposal is for the overload events to be recorded at hour-granularity, would that result in a relay getting overloaded at the top of every hour, and then under-utilized for the rest of the hour?
Cheers! David
_______________________________________________ tor-dev mailing list tor-dev@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
On 09 Dec (11:36:09), Jim Newsome wrote:
On 12/7/20 14:06, David Goulet wrote:
Greetings,
Attached is a proposal from Mike Perry and I. Merge requsest is here:
https://gitlab.torproject.org/tpo/core/torspec/-/merge_requests/22
Disclaimer - As someone not very familiar with how tor load balancing works today, I might not be the target audience for this proposal :)
Maybe it's putting the cart before the horse, but it might be helpful to have a more concrete proposal for how this data will be used, which in turn will help evaluate whether this is the right data to collect.
e.g. naively I might assume the idea is to have some kind of exponential backoff for overloaded relays; but since the proposal is for the overload events to be recorded at hour-granularity, would that result in a relay getting overloaded at the top of every hour, and then under-utilized for the rest of the hour?
Right so there are currently ideas circulating around on how to use that data properly. The likely short-term proposal is sbws (bw scanner) that will use that as a simple signal to backoff on the amount of bw given, as you stated. Thus your question is right on the nail there about "why we have this proposal without a concrete proposal on how to use it" :). The answer I can give you is that we've thought on how for a relay to tell the world, in a safe way, that it is suffocating. There are few places in the tor we can actually notice (at the moment) performance problems. And so we took them all (more might come over time), and mashed them into a single line "overload reached". And we did that before anything else because for the network to migrate to support that feature, we are talking a good 2-4 years minimum once the feature is stable thus we have to get this out soon if we hope to be useful in the foreseeable future. Onto your next question about the hour problem. So yes, you are correct that the timeframe between informing the world I'm not overloaded anymore and the world noticing, you might get under-utilized but you might also get "just utilized enough". All in all, we are stuck with a network that "morphs" every hour (new consensus) but actually, bandwidth scanners take much longer to scan the entire network (in the realms of days) thus it is actually much more than an hour of being under-utilized :S. So there will always be that gap where we will backoff from a relay and then we might have backed off too much until the scanner notices it and then give you a bit more. But over time, as the backoff happens and the bw scanner makes correction, they should reach an equilibrium where the scanner finds the value that is just enough for you to not advertise overload anymore or in other words finding the sweet spot. That is likely to require time and the relay to be maxi stable as in 99% uptime and not too CPU/network fluctuations. But also, as we backoff from overloaded relays, we will send traffic to potentially under-utilized relays and so we hope that yes it will be a bumpy road at first but after some days/weeks, network should stabilize and we should actually see very few "overload-reached" after that point (except for operators running 1000 other things on the relay machine eating the resources randomly :). This does highlight also the massive importance of stable relays on the network so its load balancing can adjust and converge to an equilibrium without having to re-adjust because 1000 relays on pi4 went down for the night :). Hope this answers your question! Cheers! David -- rYGibKHpj9tyuXQTgiocxhuz2G/n9dYwDlcqA1Ao9Vk=
On 12/11/20 08:04, David Goulet wrote:
we are talking a good 2-4 years minimum once the feature is stable thus we have to get this out soon if we hope to be useful in the foreseeable future.
Right - the slow feedback cycle of deploying between deploying new logging and trying to use it is all the more reason to plan ahead to try to ensure the data will actually be suitable for the intended use :). Granted, we can presumably at least *start* trying to prototype usage of the data sooner than 2-4 years, but it'll probably still be some months before any useful data starts arriving, right?
Onto your next question about the hour problem. So yes, you are correct that the timeframe between informing the world I'm not overloaded anymore and the world noticing, you might get under-utilized but you might also get "just utilized enough".
All in all, we are stuck with a network that "morphs" every hour (new consensus) but actually, bandwidth scanners take much longer to scan the entire network (in the realms of days) thus it is actually much more than an hour of being under-utilized :S.
So there will always be that gap where we will backoff from a relay and then we might have backed off too much until the scanner notices it and then give you a bit more. But over time, as the backoff happens and the bw scanner makes correction, they should reach an equilibrium where the scanner finds the value that is just enough for you to not advertise overload anymore or in other words finding the sweet spot.
That is likely to require time and the relay to be maxi stable as in 99% uptime and not too CPU/network fluctuations.
But also, as we backoff from overloaded relays, we will send traffic to potentially under-utilized relays and so we hope that yes it will be a bumpy road at first but after some days/weeks, network should stabilize and we should actually see very few "overload-reached" after that point (except for operators running 1000 other things on the relay machine eating the resources randomly :).
Thanks for the explanation! IIUC the new consensus computed every hour includes weights based on the latest data from the bandwidth scanners, and an individual relay is only scanned once every x days? In the proposal, maybe it'd be enough to briefly explain the choices of parameters and any relevant tradeoffs - one hour for granularity, 72 hours for history, (any others?). It might also be helpful to have a strawman example of how the data could be used in the congestion control algorithm, with some discussion like the above ^, though I could also see that potentially getting too far from the core of the proposal. Btw, maybe it's worth explicitly explaining how the data *won't* be useful for attackers? I'd assumed (possibly incorrectly) that the history wasn't being kept at a finer granularity to avoid being able to correlate events across relays, and from there perhaps be able to infer something about individual circuit paths. If that sort of attack is worth worrying about, should relays also suppress reporting events for the current partial hour to avoid an attacker being able to probe the metrics port to find out if an overload just happened?
Hope this answers your question!
Very helpful, thanks!
David Goulet <dgoulet@torproject.org> writes:
Greetings,
Attached is a proposal from Mike Perry and I. Merge requsest is here:
https://gitlab.torproject.org/tpo/core/torspec/-/merge_requests/22
Hello all, while working on this proposal I had to change it slightly to add a few more metrics and also to simplify some engineering issues that we would encounter. You can find the changes here: https://gitlab.torproject.org/asn/torspec/-/commit/b57743b9764bd8e6ef8de689d... Mike, based on your comments in the #40222 ticket, I would appreciate comments on the way the DNS issues will be reported. David argued that they should not be part of the "overload-general" line because they are not an overload and it's not the fault of the network in any way. This is why we added them as separate lines. Furthermore, David suggested we turn them into a threshold "only report if 25% of the total requests have timed out" instead of "only report if at least one time out has occured" since that would be more useful. We also decided to simplify the 'overload-ratelimits' line to make it easier to implement (learning whether it was a burst or rate overload in Tor seems to be quite hard, so we decided to merge these two events). Cheers!
On 3/2/21 6:01 PM, George Kadianakis wrote:
David Goulet <dgoulet@torproject.org> writes:
Greetings,
Attached is a proposal from Mike Perry and I. Merge requsest is here:
https://gitlab.torproject.org/tpo/core/torspec/-/merge_requests/22
Hello all,
while working on this proposal I had to change it slightly to add a few more metrics and also to simplify some engineering issues that we would encounter. You can find the changes here: https://gitlab.torproject.org/asn/torspec/-/commit/b57743b9764bd8e6ef8de689d...
Mike, based on your comments in the #40222 ticket, I would appreciate comments on the way the DNS issues will be reported. David argued that they should not be part of the "overload-general" line because they are not an overload and it's not the fault of the network in any way. This is why we added them as separate lines. Furthermore, David suggested we turn them into a threshold "only report if 25% of the total requests have timed out" instead of "only report if at least one time out has occured" since that would be more useful.
I'm confused by this confusion. There's pretty clear precedent for treating packet drops as a sign of network capacity overload. We've also seen it experimentally specifically with respect to DNS, during Rob's experiment. We discussed this on Monday. However, I agree there's a chance that a single packet drop can be spurious, and/or could be due to ephemeral overload as TCP congestion causes. But 25% is waaaaaaaaaay too high. Even 1% is high IMO, but is more reasonable. We should ask some exits what they see now. The fact that our DNS scanners are not currently seeing this at all, and the issue appeared only for the exact duration of Rob's experiment, suggests that DNS packets drops are extremely rare in healthy network conditions. Furthermore, revealing the specific type of overload condition increases the ability for the adversary to use this information for various attacks. I'd rather it be combined in all cases, so that the specific cause is not visible. In all cases, the reaction of our systems should be the same: direct less load to relays with this line. If we need to dig, that's what MetricsPort is for. In fact, this DNS packet drop signal may be particularly useful in traffic analysis attacks. Its reporting, and likely all of this overload reporting, should probably be delayed until something like the top of the hour after it happens. We may even want this delay to be a consensus parameter. Something like "Report only after N minutes", or "Report only N minute windows", perhaps?
We also decided to simplify the 'overload-ratelimits' line to make it easier to implement (learning whether it was a burst or rate overload in Tor seems to be quite hard, so we decided to merge these two events).
Ok, this makes sense. -- Mike Perry
Mike Perry:
On 3/2/21 6:01 PM, George Kadianakis wrote:
David Goulet <dgoulet@torproject.org> writes:
Greetings,
Attached is a proposal from Mike Perry and I. Merge requsest is here:
https://gitlab.torproject.org/tpo/core/torspec/-/merge_requests/22
Hello all,
while working on this proposal I had to change it slightly to add a few more metrics and also to simplify some engineering issues that we would encounter. You can find the changes here: https://gitlab.torproject.org/asn/torspec/-/commit/b57743b9764bd8e6ef8de689d...
Mike, based on your comments in the #40222 ticket, I would appreciate comments on the way the DNS issues will be reported. David argued that they should not be part of the "overload-general" line because they are not an overload and it's not the fault of the network in any way. This is why we added them as separate lines. Furthermore, David suggested we turn them into a threshold "only report if 25% of the total requests have timed out" instead of "only report if at least one time out has occured" since that would be more useful.
I'm confused by this confusion. There's pretty clear precedent for treating packet drops as a sign of network capacity overload. We've also seen it experimentally specifically with respect to DNS, during Rob's experiment. We discussed this on Monday.
However, I agree there's a chance that a single packet drop can be spurious, and/or could be due to ephemeral overload as TCP congestion causes. But 25% is waaaaaaaaaay too high. Even 1% is high IMO, but is more reasonable. We should ask some exits what they see now. The fact that our DNS scanners are not currently seeing this at all, and the issue appeared only for the exact duration of Rob's experiment, suggests that DNS packets drops are extremely rare in healthy network conditions.
Furthermore, revealing the specific type of overload condition increases the ability for the adversary to use this information for various attacks. I'd rather it be combined in all cases, so that the specific cause is not visible. In all cases, the reaction of our systems should be the same: direct less load to relays with this line. If we need to dig, that's what MetricsPort is for.
+1
In fact, this DNS packet drop signal may be particularly useful in traffic analysis attacks. Its reporting, and likely all of this overload reporting, should probably be delayed until something like the top of the hour after it happens. We may even want this delay to be a consensus parameter. Something like "Report only after N minutes", or "Report only N minute windows", perhaps?
That's a good idea, thanks. I am not sure we really need a consensus parameter for that but some delay, which makes sure the DNS packet drop does not aid in traffic analysis, seems indeed to be a smart idea. Georg
We also decided to simplify the 'overload-ratelimits' line to make it easier to implement (learning whether it was a burst or rate overload in Tor seems to be quite hard, so we decided to merge these two events).
Ok, this makes sense.
On 02 Mar (20:58:43), Mike Perry wrote:
On 3/2/21 6:01 PM, George Kadianakis wrote:
David Goulet <dgoulet@torproject.org> writes:
Greetings,
Attached is a proposal from Mike Perry and I. Merge requsest is here:
https://gitlab.torproject.org/tpo/core/torspec/-/merge_requests/22
Hello all,
while working on this proposal I had to change it slightly to add a few more metrics and also to simplify some engineering issues that we would encounter. You can find the changes here: https://gitlab.torproject.org/asn/torspec/-/commit/b57743b9764bd8e6ef8de689d...
Mike, based on your comments in the #40222 ticket, I would appreciate comments on the way the DNS issues will be reported. David argued that they should not be part of the "overload-general" line because they are not an overload and it's not the fault of the network in any way. This is why we added them as separate lines. Furthermore, David suggested we turn them into a threshold "only report if 25% of the total requests have timed out" instead of "only report if at least one time out has occured" since that would be more useful.
I'm confused by this confusion. There's pretty clear precedent for treating packet drops as a sign of network capacity overload. We've also seen it experimentally specifically with respect to DNS, during Rob's experiment. We discussed this on Monday.
However, I agree there's a chance that a single packet drop can be spurious, and/or could be due to ephemeral overload as TCP congestion causes. But 25% is waaaaaaaaaay too high. Even 1% is high IMO, but is more reasonable. We should ask some exits what they see now. The fact that our DNS scanners are not currently seeing this at all, and the issue appeared only for the exact duration of Rob's experiment, suggests that DNS packets drops are extremely rare in healthy network conditions.
Ok, likely 25% is way too high indeed. The idea behind this was simply that a network hiccup or a temporary faulty DNS server would not move away traffic from the Exit for a 72h period (reminder that the "overload-general" sticks for 72h in the extrainfo once hit).
Furthermore, revealing the specific type of overload condition increases the ability for the adversary to use this information for various attacks. I'd rather it be combined in all cases, so that the specific cause is not visible. In all cases, the reaction of our systems should be the same: direct less load to relays with this line. If we need to dig, that's what MetricsPort is for.
In fact, this DNS packet drop signal may be particularly useful in traffic analysis attacks. Its reporting, and likely all of this overload reporting, should probably be delayed until something like the top of the hour after it happens. We may even want this delay to be a consensus parameter. Something like "Report only after N minutes", or "Report only N minute windows", perhaps?
Yes definitely and I would even add a random component in this so not all relays will report an overload in a predictable timeframe and thus "if the line appear, I know it was hit N hours ago" type of calculation. Cheers! David -- QlSpNB+aSzOYvM3E0etjbW84Wyx4/7PrwKfWOtmEgE0=
On 3/3/21 1:14 PM, David Goulet wrote:
On 02 Mar (20:58:43), Mike Perry wrote:
On 3/2/21 6:01 PM, George Kadianakis wrote:
David Goulet <dgoulet@torproject.org> writes:
Greetings,
Attached is a proposal from Mike Perry and I. Merge requsest is here:
https://gitlab.torproject.org/tpo/core/torspec/-/merge_requests/22
Hello all,
while working on this proposal I had to change it slightly to add a few more metrics and also to simplify some engineering issues that we would encounter. You can find the changes here: https://gitlab.torproject.org/asn/torspec/-/commit/b57743b9764bd8e6ef8de689d...
Mike, based on your comments in the #40222 ticket, I would appreciate comments on the way the DNS issues will be reported. David argued that they should not be part of the "overload-general" line because they are not an overload and it's not the fault of the network in any way. This is why we added them as separate lines. Furthermore, David suggested we turn them into a threshold "only report if 25% of the total requests have timed out" instead of "only report if at least one time out has occured" since that would be more useful.
I'm confused by this confusion. There's pretty clear precedent for treating packet drops as a sign of network capacity overload. We've also seen it experimentally specifically with respect to DNS, during Rob's experiment. We discussed this on Monday.
However, I agree there's a chance that a single packet drop can be spurious, and/or could be due to ephemeral overload as TCP congestion causes. But 25% is waaaaaaaaaay too high. Even 1% is high IMO, but is more reasonable. We should ask some exits what they see now. The fact that our DNS scanners are not currently seeing this at all, and the issue appeared only for the exact duration of Rob's experiment, suggests that DNS packets drops are extremely rare in healthy network conditions.
Ok, likely 25% is way too high indeed.
The idea behind this was simply that a network hiccup or a temporary faulty DNS server would not move away traffic from the Exit for a 72h period (reminder that the "overload-general" sticks for 72h in the extrainfo once hit).
Yes, it sticks for 72 hours because sbws does not store descriptors. However, the timestamp should *not* update unless the overload condition occurs again. In this way, we can defer the logic to if the overload signal is "fresh" vs "stale" to sbws, rather than have it on relays. This also suggests we want to put some kind of counter in there, like "number of times this has been listed in the past 72 hours" as well. That way we can also defer the heuristics to respond to temporary hiccup vs persistent overload to sbws, too, without needing to bake too of this logic into relays (which are a PITA to upgrade and may end up running different versions of this). George also said you guys felt pressure to rush for the 0.4.6 merge deadline on this. I would suggest that we not try to bang this out in a week, but instead try to address these issues with a bit more thought. If we miss 0.4.6, it's not the end of the world. Plus this week is shaping up to be pure madness anyway, in other areas.
Furthermore, revealing the specific type of overload condition increases the ability for the adversary to use this information for various attacks. I'd rather it be combined in all cases, so that the specific cause is not visible. In all cases, the reaction of our systems should be the same: direct less load to relays with this line. If we need to dig, that's what MetricsPort is for.
In fact, this DNS packet drop signal may be particularly useful in traffic analysis attacks. Its reporting, and likely all of this overload reporting, should probably be delayed until something like the top of the hour after it happens. We may even want this delay to be a consensus parameter. Something like "Report only after N minutes", or "Report only N minute windows", perhaps?
Yes definitely and I would even add a random component in this so not all relays will report an overload in a predictable timeframe and thus "if the line appear, I know it was hit N hours ago" type of calculation.
Nice. Wrt what Georg said, the reason for consensus parameter(s) is also for agility in the face of uncertainty of potential attacks and how much they may be helped by a particular response time/fuzz factor. Who can say if Ian's excitement was performance research, or new attack papers (kidding Ian, but you know how it goes :). -- Mike Perry
participants (7)
-
David Goulet -
Georg Koppen -
George Kadianakis -
Ian Goldberg -
Jim Newsome -
Mike Perry -
Nick Mathewson