commit 88926c8b0295e5de584b87cc241a71fc45526878
Author: Karsten Loesing <karsten.loesing(a)gmx.net>
Date: Mon Jul 4 09:34:20 2011 +0200
Update relay stability tech report sources.
---
task-2911/.gitignore | 6 +-
task-2911/README | 297 +++----
task-2911/SimulateStableGuard.java | 842 ++++++++++++++++++++
.../mtbf-sim/SimulateMeanTimeBetweenFailure.java | 351 --------
task-2911/mtbf-sim/mtbf-sim.R | 73 --
task-2911/report.bib | 31 +
task-2911/report.tex | 673 +++++++++++-----
task-2911/stability.R | 301 +++++++
.../wfu-sim/SimulateWeightedFractionalUptime.java | 318 --------
task-2911/wfu-sim/wfu-sim.R | 57 --
10 files changed, 1755 insertions(+), 1194 deletions(-)
diff --git a/task-2911/.gitignore b/task-2911/.gitignore
index d2480c1..23b4a67 100644
--- a/task-2911/.gitignore
+++ b/task-2911/.gitignore
@@ -1,9 +1,9 @@
*.class
-mtbf-sim/tunf/
-wfu-sim/fwfu/
-wfu-sim/consensuses/
*.csv
*.aux
*.log
+*.bbl
+*.blg
*.pdf
+future-stability/
diff --git a/task-2911/README b/task-2911/README
index 686de7a..e2ae1d0 100644
--- a/task-2911/README
+++ b/task-2911/README
@@ -1,196 +1,143 @@
Tech report: An Analysis of Tor Relay Stability
===============================================
-Simulation of MTBF requirements
--------------------------------
-
-When simulating MTBF requirements, we parse status entries and server
-descriptor parts. For every data point we care about the valid-after time
-of the consensus, the relay fingerprint, and whether the relay had an
-uptime of 3599 seconds or less when the consensus was published. The last
-part is important to detect cases when a relay was contained in two
-subsequent consensuses, but was restarted in the intervening time. We
-rely on the uptime as reported in the server descriptor and decide whether
-the relay was restarted by calculating whether the following condition
-holds:
-
- restarted == valid-after - published + uptime < 3600
-
-In the first simulation step we parse the data in reverse order from last
-consensus to first. In this step we only care about time until next
-failure.
-
-For every relay we see in a consensus we look up whether we also saw it in
-the subsequently published consensus (that we parsed before). If we did
-not see the relay before, we add it to our history with a time until
-failure of 0 seconds. If we did see the relay, we add the seconds elapsed
-between the two consensuses to the relay's time until next failure in our
-history. We then write the times until next failure from our history to
-disk for the second simulation step below. Before processing the next
-consensus we remove all relays that have not been running in this
-consensus or that have been restarted before this consensus from our
-history.
-
-In the second simulation step we parse the data again, but in forward
-order from first to last consensus. This time we're interested in the
-mean time between failure for all running relays.
-
-We keep a history of three variables per relay to calculate its MTBF:
-weighted run length, total run weights, and current run length. The first
-two variables are used to track past uptime sessions whereas the third
-variable tracks the current uptime session if a relay is currently
-running.
-
-For every relay seen in a consensus we distinguish four cases:
-
- 1) the relay is still running,
- 2) the relay is still running but has been restarted,
- 3) the relay has been newly started in this consensus, and
- 4) the relay has left or failed in this consensus.
-
-In case 1 we add the seconds elapsed since the last consensus to the
-relay's current run length.
-
-In case 2 we add the current run length to the weighted run length,
-increment the total run weights by 1, and re-initialize the current run
-length with the seconds elapsed since the last consensus.
-
-In case 3 we initialize the current run length with the seconds elapsed
-since the last consensus.
-
-In case 4 we add the current run length to the weighted run length,
-increment the total run weights by 1, and set the current run length to 0.
-
-Once we're done with processing a consensus, we calculate MTBFs for all
-running relays.
-
- weighted run length + current run length
- MTBF = ----------------------------------------
- total run weights + 1
-
-We sort relays by MTBF in descending order, create subsets containing the
-30%, 40%, ..., 70% relays with highest MTBF, and look up mean time until
-failure for these relays. We then write the mean value, 85th, 90th, and
-95th percentile to disk as simulation results.
-
-To run the simulation, start by changing to the MTBF simulation directory:
-
- $ cd mtbf-sim/
-
-Export status entries and server descriptor parts from the metrics
-database, once in reverse and once in forward order. Note that each file
-will be 2.2G large for roughly 2.5 years of data. Plan for a buffer of at
-least 4 months before and after the interval to investigate:
-
+We developed a simulator for the tech report "An Analysis of Tor Relay
+Stability" that varies the requirements for assigning Stable and Guard
+flags to relays and evaluates how useful these assignments are. In this
+README we describe how to use the simulator to re-run and possibly modify
+our analysis.
+
+First, download the comma-separated value file containing extracted status
+entries and server descriptors parts from the metrics database. The file
+is called running-relays-reverse.csv and contains lines like the
+following:
+
+ 2011-06-30 23:00:00,0089102aa16208d991dc36efafd5cf13b35aa707,
+ f,f,f,193581,1148763136
+
+The columns are:
+
+ - consensus valid-after time
+ - relay fingerprint
+ - whether the relay was restarted in the last hour (t/f)
+ - whether the relay got the Stable flag assigned (t/f)
+ - whether the relay got the Guard flag assigned (t/f)
+ - advertised bandwidth in bytes per day
+ - written bytes per day
+
+If you don't have this file or want to generate your own file, you can
+export status entries and server descriptor parts from the metrics
+database. Be sure to plan for a buffer of at least 4 months (better: 6
+months) before and after the interval to investigate. The psql commands
+and SELECT statement for extracting these data are as follows:
+
+ tordir=> \f ','
+ tordir=> \a
+ tordir=> \t
tordir=> \o running-relays-reverse.csv
tordir=> SELECT statusentry.validafter,
statusentry.fingerprint,
CASE WHEN descriptor.uptime IS NULL THEN FALSE ELSE
statusentry.validafter - descriptor.published +
descriptor.uptime * '1 second'::INTERVAL <
- '01:00:00'::INTERVAL END AS restarted
+ '01:00:00'::INTERVAL END AS restarted,
+ statusentry.isstable,
+ statusentry.isguard,
+ LEAST(descriptor.bandwidthavg, descriptor.bandwidthobserved)
+ AS bwadvertised,
+ bwhist.written_sum AS writtensum
FROM statusentry
LEFT JOIN descriptor
ON statusentry.descriptor = descriptor.descriptor
+ LEFT JOIN bwhist
+ ON DATE(statusentry.validafter) = bwhist.date
+ AND statusentry.fingerprint = bwhist.fingerprint
WHERE statusentry.isrunning
- AND statusentry.validafter >= '2009-01-01 00:00:00'
+ AND statusentry.validafter >= '2010-01-01 00:00:00'
+ AND statusentry.validafter < '2011-07-01 00:00:00'
ORDER BY statusentry.validafter DESC, statusentry.fingerprint;
tordir=> \o
- tordir=> \o running-relays-forward.csv
- tordir=> SELECT statusentry.validafter,
- statusentry.fingerprint,
- CASE WHEN descriptor.uptime IS NULL THEN FALSE ELSE
- statusentry.validafter - descriptor.published +
- descriptor.uptime * '1 second'::INTERVAL <
- '01:00:00'::INTERVAL END AS restarted
- FROM statusentry
- LEFT JOIN descriptor
- ON statusentry.descriptor = descriptor.descriptor
- WHERE statusentry.isrunning
- AND statusentry.validafter >= '2009-01-01 00:00:00'
- ORDER BY statusentry.validafter, statusentry.fingerprint;
- tordir=> \o
-
-Run the simulation consisting of a reverse and a forward run. The results
-of the reverse run will be stored to the tunf/ directory and will be
-re-used in subsequent simulations. Delete the tunf/ directory to repeat
-the reverse run, too.
-
- $ javac SimulateMeanTimeBetweenFailure.java
- $ java SimulateMeanTimeBetweenFailure
-
-Plot the results:
-
- $ R --slave -f mtbf-sim.R
-
-Once you're satisfied with the result, copy the graph to the parent
-directory to include it in the report:
-
- $ cp mtbf-sim.pdf ../
-
+ tordir=> \q
-Simulation of WFU requirements
-------------------------------
+The simulator needs to parse the file in forward and in reverse direction.
+The easiest way to implement this is to reverse the file using tac:
-In the first simulation step we parse consensuses in reverse order to
-calculate future WFU for every relay and for every published consensus.
-We keep a relay history with two values for each relay: weighted uptime
-and total weighted time.
+ $ tac running-relays-reverse.csv > running-relays-foward.csv
-When parsing a consensus, we add 3600 seconds to the weighted uptime
-variable of every running relay and 3600 seconds to the total weighted
-time of all relays in our history. We then write future WFUs for all
-known relays to disk by dividing weighted uptime by total weighted time.
-
-Every 12 hours, we multiply the weighted uptimes and total weighted times
-of all relays in our history by 0.95. If the quotiend of the two
-variables drops below 0.0001, we remove a relay from our history.
-
-In the second simulation step we parse the consensuses again, but in
-forward order. The history and WFU calculation is exactly the same as in
-the first simulation step.
-
-After calculating WFUs for all relays in the history, we look up the
-future WFUs for all relays meeting certain past WFU requirements and
-calculate their mean value, 85th, 90th, and 95th percentile.
-
-To run the simulation, start by changing to the WFU simulation directory:
-
- $ cd wfu-sim/
-
-Create a consensuses/ directory and put the consensus files of the
-interval to investigate plus 4+ months before and 4+ months after in it:
-
- $ mkdir consensuses/
- $ ln -s $extracted/consensuses-20* .
-
-Run the simulation that first parses consensuses from last to first and
-then from first to last. The results from the reverse direction will be
-stored in the fwfu/ directory and re-used in subsequent simulations.
-Delete the fwfu/ directory to re-run both simulation parts.
-
- $ javac SimulateWeightedFractionalUptime.java
- $ java SimulateWeightedFractionalUptime
-
-Plot the results:
-
- $ R --slave -f wfu-sim.R
-
-Copy the graph to the parent directory to include it in the report:
-
- $ cp wfu-sim.pdf ../
-
-
-Compiling the report
---------------------
-
-Copy the generated graphs to the base directory, unless you have done so
-before:
-
- $ cp mtbf-sim/mtbf-sim.pdf .
- $ cp wfu-sim/wfu-sim.pdf .
-
-Compile the report:
+Run the simulation consisting of a reverse and a forward run. The results
+of the reverse run will be stored to the future-stability/ directory and
+will be re-used in subsequent simulations. Delete or move away the
+future-stability/ directory to repeat the reverse run, too. The execution
+can take 20--30 minutes or even more depending on your hardware.
+
+ $ javac SimulateStableGuard.java
+ $ java SimulateStableGuard
+
+The result is a file stability.csv that contains the following columns:
+
+- time: consensus valid-after time
+- excladvbw, exclwfu, exclwt: the number of relays that did not get the
+ Guard flag assigned in the simulation which got it from the directory
+ authorities; excladvbw did not get it because of the advertised
+ bandwidth requirement, exclwfu because of the WFU requirement, and
+ exclwt because of the weighted time requirement; it's quite possible
+ that a relay did not get the Guard flag for more than one reason
+- familiar: absolute number of `familiar' relays
+- guard: absolute number of relays with the Guard flag as assigned by the
+ directory authorities
+- guardYYwfuZZadvbw: absolute number of relays with the Guard flag as
+ assigned in the simulation when using YY as the WFU percentile and ZZ as
+ the advertised bandwidth percentile
+- guardintersect, guardobserved, guardsimulated: number of relays that got
+ the Guard flag both by the directory authorities and by the simulator or
+ that only got it by one of them
+- minadvbwaZZadvbw: Minimum advertised bandwidth when using ZZ as the
+ advertised bandwidth percentile, before cutting it down to 250 KiB/s
+- minadvbwbZZadvbw: Minimum advertised bandwidth when using ZZ as the
+ advertised bandwidth percentile, after cutting it down to 250 KiB/s
+- minwfuaYYwfu: Minimum WFU when using YY as the WFU percentile, before
+ cutting it down to 0.98
+- minwfubYYwfu: Minimum WFU when using YY as the WFU percentile, after
+ cutting it down to 0.98
+- minwmtbfaXX: Minimum WMTBF when using XX as the WMTBF percentile, before
+ cutting it down to 5 days
+- minwmtbfbXX: Minimum WMTBF when using XX as the WMTBF percentile, after
+ cutting it down to 5 days
+- minwta: Minimum weighted time before cutting it down to 8 days
+- minwtb: Minimum weighted time after cutting it down to 8 days
+- mtunfXX: Mean time until next failure when using XX as the WMTBF
+ percentile
+- mwfu: Mean WFU of relays that got the Guard flag assigned by the
+ directory authorities
+- mwfuYYwfuZZadvbw: Mean WFU when using YY as the WFU percentile and ZZ as
+ the advertised bandwidth percentile
+- percWWfwb: WW-th percentile of future weighted bandwidth of relays that
+ got the Guard flag assigned by the directory authorities
+- percWWfwbYYwfuZZadvbw: WW-th percentile of future weighted bandwidth
+ when using YY as the WFU percentile and ZZ as the advertised bandwidth
+ percentile
+- percWWtunf: WW-th percentile of time until next failure of relays that
+ got the Stable flag assigned by the directory authorities
+- percWWtunfXX: WW-th percentile of time until next failure when using XX
+ as the WMTBF percentile
+- percWWwfu: WW-th percentile of WFU of relays that got the Guard flag
+ assigned by the directory authorities
+- percWWwfuYYwfuZZadvbw: WW-th percentile of WFU when using YY as the WFU
+ percentile and ZZ as the advertised bandwidth percentile
+- running: absolute number of running relays
+- stable: absolute number of relays with the Stable flag as assigned by the
+ directory authorities
+- stableXX: absolute number of relays with the Stable flag as assigned in
+ the simulation when using XX as WMTBF percentile
+- stableintersect, stableobserved, stablesimulated: number of relays that
+ got the Stable flag both by the directory authorities and by the
+ simulator or that only got it by one of them
+
+Plot the graphs for the tech report:
+
+ $ R --slave -f stability.R
+
+Compile the tech report:
$ pdflatex report.tex
diff --git a/task-2911/SimulateStableGuard.java b/task-2911/SimulateStableGuard.java
new file mode 100644
index 0000000..1edbcc3
--- /dev/null
+++ b/task-2911/SimulateStableGuard.java
@@ -0,0 +1,842 @@
+/**
+ * Simulate variation of WMTBF, WFU, and advertised bandwidth requirements
+ * on Stable and Guard flag assignment. In a first step, parse network
+ * status consensus entries from last to first, calculate future stability
+ * metrics for all running relays, and write them to disk as one file per
+ * network status in future-stability/$filename. (Skip this step if there
+ * is already a future-stability/ directory.) In a second step, parse the
+ * network statuse consensus entries again, but this time from first to
+ * last, calculate past stability metrics for all relays, assign relay
+ * flags to relays, look up future stability of these relays, and write
+ * results to stability.csv to disk.
+ *
+ * Please see the README for more information! */
+import java.io.*;
+import java.text.*;
+import java.util.*;
+public class SimulateStableGuard {
+ public static void main(String[] args) throws Exception {
+
+ /* Define analysis interval. */
+ String analyzeFrom = "2010-07-01 00:00:00",
+ analyzeTo = "2010-12-31 23:00:00";
+
+ /* Decide whether we need to do the reverse run, or if we can use
+ * previous results. */
+ if (!new File("future-stability").exists()) {
+
+ /* Track weighted uptime and total weighted time in a long[2]. */
+ SortedMap<String, long[]> wfuHistory =
+ new TreeMap<String, long[]>();
+
+ /* Track time until next failure in seconds in a long. */
+ SortedMap<String, Long> tunfHistory = new TreeMap<String, Long>();
+
+ /* Track weighted written bytes and total weighted time in a
+ * long[2]. */
+ SortedMap<String, long[]> wbHistory = new TreeMap<String, long[]>();
+
+ /* Parse previously exported network status entries in reverse
+ * order. */
+ SimpleDateFormat formatter = new SimpleDateFormat(
+ "yyyy-MM-dd-HH-mm-ss");
+ formatter.setTimeZone(TimeZone.getTimeZone("UTC"));
+ SimpleDateFormat isoFormatter = new SimpleDateFormat(
+ "yyyy-MM-dd HH:mm:ss");
+ isoFormatter.setTimeZone(TimeZone.getTimeZone("UTC"));
+ Map<String, String> runningRelays = new HashMap<String, String>();
+ BufferedReader br = new BufferedReader(new FileReader(
+ "running-relays-reverse.csv"));
+ String line, lastValidAfter = null, lastButOneValidAfter = null;
+ long nextWeightingInterval = -1L;
+ while ((line = br.readLine()) != null) {
+ if (!line.startsWith("20")) {
+ continue;
+ }
+ String[] parts = line.split(",");
+ String validAfter = parts[0];
+ if (lastValidAfter != null &&
+ !lastValidAfter.equals(validAfter)) {
+
+ /* We just parsed the very first consensus. There's nothing to
+ * do here. */
+ if (lastButOneValidAfter == null) {
+ runningRelays.clear();
+ lastButOneValidAfter = lastValidAfter;
+ continue;
+ }
+
+ /* We just parsed the first consensus outside the analysis
+ * interval. Stop parsing here. */
+ if (lastValidAfter.compareTo(analyzeFrom) < 0) {
+ break;
+ }
+
+ /* We just parsed all lines of a consensus. First, see if 12
+ * hours have passed since we last discounted wfu and wb history
+ * values. If so, discount variables for all known relays by
+ * factor 0.95 (or 19/20 since these are long integers) and
+ * remove those relays with a weighted fractional uptime below
+ * 1/10000 from the history. */
+ long lastValidAfterMillis = isoFormatter.parse(lastValidAfter).
+ getTime();
+ long secondsSinceLastValidAfter =
+ (isoFormatter.parse(lastButOneValidAfter).getTime()
+ - lastValidAfterMillis) / 1000L;
+ long weightingInterval = lastValidAfterMillis
+ / (12L * 60L * 60L * 1000L);
+ if (nextWeightingInterval < 0L) {
+ nextWeightingInterval = weightingInterval;
+ }
+ while (weightingInterval < nextWeightingInterval) {
+ Set<String> relaysToRemove = new HashSet<String>();
+ for (Map.Entry<String, long[]> e : wfuHistory.entrySet()) {
+ long[] w = e.getValue();
+ w[0] *= 19L;
+ w[0] /= 20L;
+ w[1] *= 19L;
+ w[1] /= 20L;
+ if (((10000L * w[0]) / w[1]) < 1L) {
+ relaysToRemove.add(e.getKey());
+ }
+ }
+ for (String fingerprint : relaysToRemove) {
+ wfuHistory.remove(fingerprint);
+ }
+ relaysToRemove.clear();
+ for (Map.Entry<String, long[]> e : wbHistory.entrySet()) {
+ long[] w = e.getValue();
+ w[0] *= 19L;
+ w[0] /= 20L;
+ w[1] *= 19L;
+ w[1] /= 20L;
+ if (w[1] < 1L) {
+ relaysToRemove.add(e.getKey());
+ }
+ }
+ for (String fingerprint : relaysToRemove) {
+ wbHistory.remove(fingerprint);
+ }
+ nextWeightingInterval -= 1L;
+ }
+
+ /* Increment weighted written bytes and total weighted time for
+ * all running relays. */
+ for (Map.Entry<String, String> runningRelay :
+ runningRelays.entrySet()) {
+ String fingerprint = runningRelay.getKey();
+ String[] relayParts = runningRelay.getValue().split(",");
+ long writtenSum = relayParts.length < 7 ? 0 :
+ Long.parseLong(relayParts[6]);
+ long[] w = wbHistory.containsKey(fingerprint) ?
+ wbHistory.get(fingerprint) : new long[2];
+ w[0] += writtenSum * secondsSinceLastValidAfter /
+ (24L * 60L * 60L);
+ w[1] += secondsSinceLastValidAfter;
+ wbHistory.put(fingerprint, w);
+ }
+
+ /* Increment weighted uptime for all running relays that have
+ * not been restarted by seconds since last valid-after time. */
+ for (Map.Entry<String, String> runningRelay :
+ runningRelays.entrySet()) {
+ String fingerprint = runningRelay.getKey();
+ boolean restarted = runningRelay.getValue().
+ split(",")[2].equals("t");
+ long seconds = restarted ? 0 : secondsSinceLastValidAfter;
+ if (!wfuHistory.containsKey(fingerprint)) {
+ wfuHistory.put(fingerprint, new long[] { seconds, 0L });
+ } else {
+ wfuHistory.get(fingerprint)[0] += seconds;
+ }
+ }
+
+ /* Increment total weighted time for all relays by seconds since
+ * last valid-after time. */
+ for (long[] w : wfuHistory.values()) {
+ w[1] += secondsSinceLastValidAfter;
+ }
+
+ /* Iterate over our time until next failure history first and
+ * see if these relays have been running in the considered
+ * consensus. Remember changes to our history and modify it
+ * below to avoid concurrent modification errors. */
+ Set<String> removeFromHistory = new HashSet<String>(),
+ foundInHistory = new HashSet<String>();
+ Map<String, Long> addToHistory = new HashMap<String, Long>();
+ for (Map.Entry<String, Long> e : tunfHistory.entrySet()) {
+ String fingerprint = e.getKey();
+ if (runningRelays.containsKey(fingerprint)) {
+
+ /* This relay has been running, so update our history. */
+ boolean restarted = runningRelays.get(fingerprint).
+ split(",")[2].equals("t");
+ if (restarted) {
+ removeFromHistory.add(fingerprint);
+ } else {
+ addToHistory.put(fingerprint, secondsSinceLastValidAfter
+ + e.getValue());
+ }
+ foundInHistory.add(fingerprint);
+ } else {
+
+ /* This relay has not been running, so remove it from our
+ * history. */
+ removeFromHistory.add(fingerprint);
+ }
+ }
+
+ /* Update our history for real now. We couldn't do this above,
+ * or we'd have modified the set we've been iterating over. */
+ for (String f : removeFromHistory) {
+ tunfHistory.remove(f);
+ }
+ for (Map.Entry<String, Long> e : addToHistory.entrySet()) {
+ tunfHistory.put(e.getKey(), e.getValue());
+ }
+
+ /* Iterate over the relays that we found in the consensus, but
+ * that we didn't have in our history. */
+ for (Map.Entry<String, String> e : runningRelays.entrySet()) {
+ String fingerprint = e.getKey();
+ if (!foundInHistory.contains(fingerprint)) {
+ boolean restarted = e.getValue().split(",")[2].equals("t");
+ if (!restarted) {
+ tunfHistory.put(fingerprint, 0L);
+ }
+ }
+ }
+
+ /* If the consensus falls within our analysis interval, write
+ * future WFUs, TUNFs, and WBs for all known relays to disk. */
+ if (lastValidAfter.compareTo(analyzeFrom) >= 0) {
+ File futureStabilityFile = new File("future-stability",
+ formatter.format(lastValidAfterMillis));
+ futureStabilityFile.getParentFile().mkdirs();
+ BufferedWriter bw = new BufferedWriter(new FileWriter(
+ futureStabilityFile));
+ for (String fingerprint : runningRelays.keySet()) {
+ long[] wfu = wfuHistory.get(fingerprint);
+ long tunf = tunfHistory.containsKey(fingerprint) ?
+ tunfHistory.get(fingerprint) : 0;
+ long[] wb = wbHistory.get(fingerprint);
+ bw.write(fingerprint + " " + tunf + " "
+ + ((10000L * wfu[0]) / wfu[1]) + " "
+ + (wb[0] / wb[1]) + "\n");
+ }
+ bw.close();
+ }
+
+ /* Prepare for next consensus. */
+ runningRelays.clear();
+ lastButOneValidAfter = lastValidAfter;
+ }
+
+ /* Add the running relay lines to a map that we parse once we have
+ * all lines of a consensus. */
+ String fingerprint = parts[1];
+ runningRelays.put(fingerprint, line);
+ lastValidAfter = validAfter;
+ }
+ }
+
+ /* Run the Guard simulation for the following WFU and advertised
+ * bandwidth percentiles: */
+ List<Integer> wfuPercentiles = new ArrayList<Integer>();
+ for (int l : new int[] { 30, 40, 50, 60, 70 }) {
+ wfuPercentiles.add(l);
+ }
+ List<Integer> advBwPercentiles = new ArrayList<Integer>();
+ for (int l : new int[] { 30, 40, 50, 60, 70 }) {
+ advBwPercentiles.add(l);
+ }
+
+ /* Run the Stable simulation for the following WMTBF percentiles: */
+ List<Integer> wmtbfPercentiles = new ArrayList<Integer>();
+ for (int l : new int[] { 30, 40, 50, 60, 70 }) {
+ wmtbfPercentiles.add(l);
+ }
+
+ /* Add column headers to output file. */
+ SortedSet<String> columns = new TreeSet<String>();
+ columns.addAll(new ArrayList<String>(Arrays.asList(("running,"
+ + "guard,mwfu,perc15wfu,perc10wfu,perc5wfu,"
+ + "guardintersect,guardobserved,guardsimulated,"
+ + "minwta,minwtb,familiar,"
+ + "perc1fwb,perc2fwb,perc5fwb,perc10fwb,"
+ + "exclwt,exclwfu,excladvbw").split(","))));
+ for (int wfuPercentile : wfuPercentiles) {
+ for (int advBwPercentile : advBwPercentiles) {
+ String simulation = wfuPercentile + "wfu" + advBwPercentile
+ + "advbw";
+ columns.add("minwfua" + wfuPercentile + "wfu");
+ columns.add("minwfub" + wfuPercentile + "wfu");
+ columns.add("minadvbwa" + advBwPercentile + "advbw");
+ columns.add("minadvbwb" + advBwPercentile + "advbw");
+ columns.add("guard" + simulation);
+ columns.add("mwfu" + simulation);
+ columns.add("perc15wfu" + simulation);
+ columns.add("perc10wfu" + simulation);
+ columns.add("perc5wfu" + simulation);
+ columns.add("perc1fwb" + simulation);
+ columns.add("perc2fwb" + simulation);
+ columns.add("perc5fwb" + simulation);
+ columns.add("perc10fwb" + simulation);
+ }
+ }
+ columns.addAll(new ArrayList<String>(Arrays.asList(("stable,"
+ + "perc25tunf,perc20tunf,perc15tunf,perc10tunf,perc5tunf,"
+ + "stableintersect,stableobserved,stablesimulated").split(","))));
+ for (int wmtbfPercentile : wmtbfPercentiles) {
+ columns.add("minwmtbfa" + wmtbfPercentile);
+ columns.add("minwmtbfb" + wmtbfPercentile);
+ columns.add("stable" + wmtbfPercentile);
+ columns.add("mtunf" + wmtbfPercentile);
+ columns.add("perc25tunf" + wmtbfPercentile);
+ columns.add("perc20tunf" + wmtbfPercentile);
+ columns.add("perc15tunf" + wmtbfPercentile);
+ columns.add("perc10tunf" + wmtbfPercentile);
+ columns.add("perc5tunf" + wmtbfPercentile);
+ }
+ BufferedWriter bw = new BufferedWriter(new FileWriter(
+ "stability.csv"));
+ bw.write("time");
+ for (String column : columns) {
+ bw.write("," + column);
+ }
+ bw.write("\n");
+
+ /* Track weighted uptime and total weighted time in a long[2]. */
+ SortedMap<String, long[]> wfuHistory = new TreeMap<String, long[]>();
+
+ /* Track weighted run length, total run weights, and current run
+ * length in a double[3]. */
+ SortedMap<String, double[]> mtbfHistory =
+ new TreeMap<String, double[]>();
+
+ /* Parse previously exported network status entries again, but this
+ * time in forward order. */
+ SimpleDateFormat formatter = new SimpleDateFormat(
+ "yyyy-MM-dd-HH-mm-ss");
+ formatter.setTimeZone(TimeZone.getTimeZone("UTC"));
+ SimpleDateFormat isoFormatter = new SimpleDateFormat(
+ "yyyy-MM-dd HH:mm:ss");
+ isoFormatter.setTimeZone(TimeZone.getTimeZone("UTC"));
+ Map<String, String> runningRelays = new HashMap<String, String>();
+ Set<String> guardRelays = new HashSet<String>(),
+ stableRelays = new HashSet<String>();
+ BufferedReader br = new BufferedReader(new FileReader(
+ "running-relays-forward.csv"));
+ String line, lastValidAfter = null, firstValidAfter = null,
+ lastButOneValidAfter = null;
+ long nextWeightingInterval = -1L;
+ while ((line = br.readLine()) != null) {
+ if (!line.startsWith("20")) {
+ continue;
+ }
+ String[] parts = line.split(",");
+ String validAfter = parts[0];
+ if (firstValidAfter == null) {
+ firstValidAfter = validAfter;
+ }
+ if (lastValidAfter != null &&
+ !lastValidAfter.equals(validAfter)) {
+
+ /* We just parsed the very first consensus. There's nothing to
+ * do here. */
+ if (lastButOneValidAfter == null) {
+ runningRelays.clear();
+ guardRelays.clear();
+ stableRelays.clear();
+ lastButOneValidAfter = lastValidAfter;
+ continue;
+ }
+
+ /* We just parsed the first consensus outside the analysis
+ * interval. Stop analysis here. */
+ if (lastValidAfter.compareTo(analyzeTo) > 0) {
+ break;
+ }
+
+ /* We just parsed all lines of a consensus. First, see if 12
+ * hours have passed since we last discounted uptimes and total
+ * times. If so, discount both variables for all known relays by
+ * factor 0.95 (or 19/20 since these are long integers) and remove
+ * those relays with a weighted fractional uptime below 1/10000.
+ * Also, discount weighted run length and total run weights for
+ * all known relays by factor 0.95. */
+ long lastValidAfterMillis = isoFormatter.parse(lastValidAfter).
+ getTime();
+ long secondsSinceLastValidAfter = (lastValidAfterMillis
+ - isoFormatter.parse(lastButOneValidAfter).getTime()) / 1000L;
+ long weightingInterval = lastValidAfterMillis
+ / (12L * 60L * 60L * 1000L);
+ if (nextWeightingInterval < 0L) {
+ nextWeightingInterval = weightingInterval;
+ }
+ while (weightingInterval > nextWeightingInterval) {
+ Set<String> relaysToRemove = new HashSet<String>();
+ for (Map.Entry<String, long[]> e : wfuHistory.entrySet()) {
+ long[] w = e.getValue();
+ w[0] *= 19L;
+ w[0] /= 20L;
+ w[1] *= 19L;
+ w[1] /= 20L;
+ if (((10000L * w[0]) / w[1]) < 1L) {
+ relaysToRemove.add(e.getKey());
+ }
+ }
+ for (String fingerprint : relaysToRemove) {
+ wfuHistory.remove(fingerprint);
+ }
+ for (Map.Entry<String, double[]> e : mtbfHistory.entrySet()) {
+ double[] w = e.getValue();
+ w[0] *= 0.95;
+ w[1] *= 0.95;
+ }
+ nextWeightingInterval += 1L;
+ }
+
+ /* Increment weighted uptime for all running relays that have not
+ * been restarted by seconds since last valid-after time. */
+ for (Map.Entry<String, String> runningRelay :
+ runningRelays.entrySet()) {
+ String fingerprint = runningRelay.getKey();
+ boolean restarted = runningRelay.getValue().
+ split(",")[2].equals("t");
+ long seconds = restarted ? 0 : secondsSinceLastValidAfter;
+ if (!wfuHistory.containsKey(fingerprint)) {
+ wfuHistory.put(fingerprint, new long[] { seconds, 0L });
+ } else {
+ wfuHistory.get(fingerprint)[0] += seconds;
+ }
+ }
+
+ /* Increment total weighted time for all relays by seconds since
+ * last valid-after time. */
+ for (long[] w : wfuHistory.values()) {
+ w[1] += secondsSinceLastValidAfter;
+ }
+
+ /* Update MTBF history for running relays. Start by iterating
+ * over all relays in the history, see if they're running now and
+ * whether they have been restarted. Distinguish four cases for
+ * relays in the history: 1) still running, 2) still running but
+ * restarted, 3) started in this consensus, 4) stopped in this
+ * consensus. */
+ Set<String> updatedRelays = new HashSet<String>();
+ for (Map.Entry<String, double[]> e : mtbfHistory.entrySet()) {
+ String fingerprint = e.getKey();
+ double[] w = e.getValue();
+ if (runningRelays.containsKey(fingerprint)) {
+ if (w[2] > 0.1) {
+ if (!runningRelays.get(fingerprint).split(",")[2].
+ equals("t")) {
+
+ /* Case 1) still running: */
+ w[2] += (double) secondsSinceLastValidAfter;
+ } else {
+
+ /* Case 2) still running but restarted: */
+ w[0] += w[2];
+ w[1] += 1.0;
+ w[2] = (double) secondsSinceLastValidAfter;
+ }
+ } else {
+
+ /* Case 3) started in this consensus: */
+ w[2] = (double) secondsSinceLastValidAfter;
+ }
+
+ /* Mark relay as already processed, or we'd add it to the
+ * history as a new relay below. */
+ updatedRelays.add(fingerprint);
+ } else if (w[2] > 0.1) {
+
+ /* Case 4) stopped in this consensus: */
+ w[0] += w[2];
+ w[1] += 1.0;
+ w[2] = 0.0;
+ }
+ }
+
+ /* Iterate over the set of currently running relays and add those
+ * that we haven't processed above to our history. */
+ for (String fingerprint : runningRelays.keySet()) {
+ if (!updatedRelays.contains(fingerprint)) {
+ updatedRelays.add(fingerprint);
+ mtbfHistory.put(fingerprint, new double[] { 0.0, 0.0,
+ (double) secondsSinceLastValidAfter });
+ }
+ }
+
+ /* Read previously calculated future WFUs, TUNFs, and WBs from
+ * disk. */
+ Map<String, Long> fwfus = new HashMap<String, Long>(),
+ tunfs = new HashMap<String, Long>(),
+ fwbs = new HashMap<String, Long>();
+ File futureStabilityFile = new File("future-stability",
+ formatter.format(lastValidAfterMillis));
+ if (!futureStabilityFile.exists()) {
+ if (!lastValidAfter.equals(firstValidAfter) &&
+ lastValidAfter.compareTo(analyzeFrom) >= 0) {
+ System.out.println("Could not find file "
+ + futureStabilityFile + ". Skipping simulation!");
+ }
+ } else if (lastValidAfter.compareTo(analyzeFrom) >= 0) {
+ BufferedReader fsBr = new BufferedReader(new FileReader(
+ futureStabilityFile));
+ String fsLine;
+ while ((fsLine = fsBr.readLine()) != null) {
+ String[] fsParts = fsLine.split(" ");
+ tunfs.put(fsParts[0], Long.parseLong(fsParts[1]));
+ fwfus.put(fsParts[0], Long.parseLong(fsParts[2]));
+ fwbs.put(fsParts[0], Long.parseLong(fsParts[3]));
+ }
+ fsBr.close();
+
+ /* Prepare writing results. */
+ Map<String, String> results = new HashMap<String, String>();
+ results.put("running", "" + runningRelays.size());
+ results.put("guard", "" + guardRelays.size());
+ results.put("stable", "" + stableRelays.size());
+
+ /* Look up future WFUs and calculate advertised bandwidth
+ * percentiles of relays that actually got the Guard flag
+ * assigned. */
+ long totalFwfu = 0L, totalFwb = 0L;
+ List<Long> fwfuList = new ArrayList<Long>();
+ for (String fingerprint : guardRelays) {
+ long fwfu = fwfus.get(fingerprint);
+ totalFwfu += fwfu;
+ fwfuList.add(fwfu);
+ }
+ Collections.sort(fwfuList);
+ results.put("mwfu", "" + (totalFwfu / guardRelays.size()));
+ results.put("perc15wfu", ""
+ + fwfuList.get((15 * fwfuList.size()) / 100));
+ results.put("perc10wfu", ""
+ + fwfuList.get((10 * fwfuList.size()) / 100));
+ results.put("perc5wfu", ""
+ + fwfuList.get((5 * fwfuList.size()) / 100));
+ List<Long> fwbList = new ArrayList<Long>();
+ for (String fingerprint : guardRelays) {
+ long fwb = fwbs.get(fingerprint);
+ totalFwb += fwb;
+ fwbList.add(fwb);
+ }
+ if (fwbList.size() > 20) {
+ Collections.sort(fwbList);
+ results.put("perc1fwb", "" + fwbList.get(
+ fwbList.size() / 100));
+ results.put("perc2fwb", "" + fwbList.get(
+ fwbList.size() / 50));
+ results.put("perc5fwb", "" + fwbList.get(
+ fwbList.size() / 20));
+ results.put("perc10fwb", "" + fwbList.get(
+ fwbList.size() / 10));
+ }
+
+ /* Prepare calculating thresholds for assigning the Guard flag
+ * in simulations. */
+ List<Long> advertisedBandwidths = new ArrayList<Long>(),
+ totalWeightedTimes = new ArrayList<Long>();
+ for (Map.Entry<String, String> e : runningRelays.entrySet()) {
+ String[] relayParts = e.getValue().split(",");
+ long advertisedBandwidth = relayParts[5].length() == 0 ? 0 :
+ Long.parseLong(relayParts[5]);
+ advertisedBandwidths.add(advertisedBandwidth);
+ totalWeightedTimes.add(wfuHistory.get(e.getKey())[1]);
+ }
+ Collections.sort(advertisedBandwidths);
+ Collections.sort(totalWeightedTimes);
+ long minimumTotalWeightedTime = totalWeightedTimes.get((
+ 1 * totalWeightedTimes.size()) / 8);
+ results.put("minwta", "" + minimumTotalWeightedTime);
+ if (minimumTotalWeightedTime > 8L * 24L * 60L * 60L) {
+ minimumTotalWeightedTime = 8L * 24L * 60L * 60L;
+ }
+ results.put("minwtb", "" + minimumTotalWeightedTime);
+ List<Long> weightedFractionalUptimesFamiliar =
+ new ArrayList<Long>();
+ for (Map.Entry<String, String> e : runningRelays.entrySet()) {
+ long[] wfuHistoryEntry = wfuHistory.get(e.getKey());
+ long totalWeightedTime = wfuHistoryEntry[1];
+ if (totalWeightedTime >= minimumTotalWeightedTime) {
+ long weightedFractionalUptime =
+ (10000L * wfuHistoryEntry[0]) / wfuHistoryEntry[1];
+ weightedFractionalUptimesFamiliar.add(
+ weightedFractionalUptime);
+ }
+ }
+ Collections.sort(weightedFractionalUptimesFamiliar);
+ results.put("familiar",
+ "" + weightedFractionalUptimesFamiliar.size());
+
+ /* Run Guard simulation for the relays in the current consensus
+ * for various WFU percentiles. */
+ for (int wfuPercentile : wfuPercentiles) {
+ for (int advBwPercentile : advBwPercentiles) {
+ String simulation = wfuPercentile + "wfu" + advBwPercentile
+ + "advbw";
+ long minimumAdvertisedBandwidth = advertisedBandwidths.get(
+ (advBwPercentile * advertisedBandwidths.size()) / 100);
+ results.put("minadvbwa" + advBwPercentile + "advbw",
+ "" + minimumAdvertisedBandwidth);
+ if (minimumAdvertisedBandwidth > 250L * 1024L) {
+ minimumAdvertisedBandwidth = 250L * 1024L;
+ }
+ results.put("minadvbwb" + advBwPercentile + "advbw",
+ "" + minimumAdvertisedBandwidth);
+ long minimumWeightedFractionalUptime =
+ weightedFractionalUptimesFamiliar.get((wfuPercentile
+ * weightedFractionalUptimesFamiliar.size()) / 100);
+ results.put("minwfua" + wfuPercentile + "wfu",
+ "" + minimumWeightedFractionalUptime);
+ if (minimumWeightedFractionalUptime > 9800) {
+ minimumWeightedFractionalUptime = 9800;
+ }
+ results.put("minwfub" + wfuPercentile + "wfu",
+ "" + minimumWeightedFractionalUptime);
+ totalFwfu = 0L;
+ totalFwb = 0L;
+ fwfuList.clear();
+ fwbList.clear();
+ Set<String> selectedRelays = new HashSet<String>();
+ int excladvbw = 0, exclwt = 0, exclwfu = 0;
+ for (String relay : runningRelays.values()) {
+ boolean notEnoughAdvertisedBandwidth = false,
+ notEnoughTotalWeightedTime = false,
+ notEnoughWeightedFractionalUptime = false,
+ selected = true;
+ String[] relayParts = relay.split(",");
+ long advertisedBandwidth = relayParts[5].length() == 0 ?
+ 0 : Long.parseLong(relayParts[5]);
+ if (advertisedBandwidth < minimumAdvertisedBandwidth) {
+ notEnoughAdvertisedBandwidth = true;
+ selected = false;
+ }
+ String fingerprint = relayParts[1];
+ long[] wfuHistoryEntry = wfuHistory.get(fingerprint);
+ long totalWeightedTime = wfuHistoryEntry[1];
+ if (totalWeightedTime < minimumTotalWeightedTime) {
+ notEnoughTotalWeightedTime = true;
+ selected = false;
+ }
+ long weightedFractionalUptime =
+ (10000L * wfuHistoryEntry[0]) / wfuHistoryEntry[1];
+ if (weightedFractionalUptime <
+ minimumWeightedFractionalUptime) {
+ notEnoughWeightedFractionalUptime = true;
+ selected = false;
+ }
+ if (selected) {
+ long fwfu = fwfus.get(fingerprint);
+ totalFwfu += fwfu;
+ fwfuList.add(fwfu);
+ long fwb = fwbs.get(fingerprint);
+ totalFwb += fwb;
+ fwbList.add(fwb);
+ selectedRelays.add(fingerprint);
+ } else if (guardRelays.contains(fingerprint)) {
+ if (notEnoughWeightedFractionalUptime) {
+ exclwfu++;
+ }
+ if (notEnoughTotalWeightedTime) {
+ exclwt++;
+ }
+ if (notEnoughAdvertisedBandwidth) {
+ excladvbw++;
+ }
+ }
+ }
+
+ /* Calculate percentiles of future WFU and of advertised
+ * bandwidth as the simulation results. */
+ results.put("guard" + simulation,
+ "" + selectedRelays.size());
+ if (fwfuList.size() > 0) {
+ Collections.sort(fwfuList);
+ results.put("mwfu" + simulation,
+ "" + (totalFwfu / fwfuList.size()));
+ results.put("perc15wfu" + simulation,
+ "" + fwfuList.get((15 * fwfuList.size()) / 100));
+ results.put("perc10wfu" + simulation,
+ "" + fwfuList.get((10 * fwfuList.size()) / 100));
+ results.put("perc5wfu" + simulation,
+ "" + fwfuList.get((5 * fwfuList.size()) / 100));
+ }
+ if (fwbList.size() > 20) {
+ Collections.sort(fwbList);
+ results.put("perc1fwb" + simulation,
+ "" + fwbList.get(fwbList.size() / 100));
+ results.put("perc2fwb" + simulation,
+ "" + fwbList.get(fwbList.size() / 50));
+ results.put("perc5fwb" + simulation,
+ "" + fwbList.get(fwbList.size() / 20));
+ results.put("perc10fwb" + simulation,
+ "" + fwbList.get(fwbList.size() / 10));
+ }
+
+ /* If this is the simulation using default values, compare
+ * selected Guard relays with observed Guard relays. */
+ if (wfuPercentile == 50 && advBwPercentile == 50) {
+ Set<String> intersection = new HashSet<String>();
+ intersection.addAll(guardRelays);
+ intersection.retainAll(selectedRelays);
+ Set<String> observedOnly = new HashSet<String>();
+ observedOnly.addAll(guardRelays);
+ observedOnly.removeAll(selectedRelays);
+ Set<String> simulatedOnly = new HashSet<String>();
+ simulatedOnly.addAll(selectedRelays);
+ simulatedOnly.removeAll(guardRelays);
+ results.put("guardintersect", "" + intersection.size());
+ results.put("guardobserved", "" + observedOnly.size());
+ results.put("guardsimulated", "" + simulatedOnly.size());
+ results.put("exclwt", "" + exclwt);
+ results.put("exclwfu", "" + exclwfu);
+ results.put("excladvbw", "" + excladvbw);
+ }
+ }
+ }
+
+ /* Look up TUNFs of relays that actually got the Stable flag
+ * assigned. */
+ long totalTunf = 0L;
+ List<Long> tunfList = new ArrayList<Long>();
+ for (String fingerprint : stableRelays) {
+ long tunf = tunfs.get(fingerprint);
+ totalTunf += tunf;
+ tunfList.add(tunf);
+ }
+ Collections.sort(tunfList);
+ results.put("perc25tunf", ""
+ + tunfList.get((25 * tunfList.size()) / 100));
+ results.put("perc20tunf", ""
+ + tunfList.get((20 * tunfList.size()) / 100));
+ results.put("perc15tunf", ""
+ + tunfList.get((15 * tunfList.size()) / 100));
+ results.put("perc10tunf", ""
+ + tunfList.get((10 * tunfList.size()) / 100));
+ results.put("perc5tunf", ""
+ + tunfList.get((5 * tunfList.size()) / 100));
+
+ /* Prepare calculating thresholds for assigning the Stable flag
+ * in simulations. */
+ List<Long> wmtbfs = new ArrayList<Long>();
+ for (String fingerprint : runningRelays.keySet()) {
+ double[] w = mtbfHistory.get(fingerprint);
+ double totalRunLength = w[0] + w[2];
+ double totalWeights = w[1] + (w[2] > 0.1 ? 1.0 : 0.0);
+ long wmtbf = totalWeights < 0.0001 ? 0
+ : (long) (totalRunLength / totalWeights);
+ wmtbfs.add(wmtbf);
+ }
+ Collections.sort(wmtbfs);
+
+ /* Run Stable simulation for the relays in the current consensus
+ * for various WMTBF percentiles. */
+ for (int wmtbfPercentile : wmtbfPercentiles) {
+ long minimumWeightedMeanTimeBetweenFailure =
+ wmtbfs.get((wmtbfPercentile * wmtbfs.size()) / 100);
+ results.put("minwmtbfa" + wmtbfPercentile,
+ "" + minimumWeightedMeanTimeBetweenFailure);
+ if (minimumWeightedMeanTimeBetweenFailure >
+ 5L * 24L * 60L * 60L) {
+ minimumWeightedMeanTimeBetweenFailure =
+ 5L * 24L * 60L * 60L;
+ }
+ results.put("minwmtbfb" + wmtbfPercentile,
+ "" + minimumWeightedMeanTimeBetweenFailure);
+ totalTunf = 0L;
+ tunfList.clear();
+ Set<String> selectedRelays = new HashSet<String>();
+ for (String fingerprint : runningRelays.keySet()) {
+ double[] w = mtbfHistory.get(fingerprint);
+ double totalRunLength = w[0] + w[2];
+ double totalWeights = w[1] + (w[2] > 0.1 ? 1.0 : 0.0);
+ long wmtbf = totalWeights < 0.0001 ? 0
+ : (long) (totalRunLength / totalWeights);
+ if (wmtbf < minimumWeightedMeanTimeBetweenFailure) {
+ continue;
+ }
+ long tunf = tunfs.get(fingerprint);
+ totalTunf += tunf;
+ tunfList.add(tunf);
+ selectedRelays.add(fingerprint);
+ }
+ results.put("stable" + wmtbfPercentile, "" + tunfList.size());
+ if (tunfList.size() > 0L) {
+ Collections.sort(tunfList);
+ results.put("mtunf" + wmtbfPercentile,
+ "" + (totalTunf / tunfList.size()));
+ results.put("perc25tunf"
+ + wmtbfPercentile,
+ "" + tunfList.get((25 * tunfList.size()) / 100));
+ results.put("perc20tunf"
+ + wmtbfPercentile,
+ "" + tunfList.get((20 * tunfList.size()) / 100));
+ results.put("perc15tunf"
+ + wmtbfPercentile,
+ "" + tunfList.get((15 * tunfList.size()) / 100));
+ results.put("perc10tunf"
+ + wmtbfPercentile,
+ "" + tunfList.get((10 * tunfList.size()) / 100));
+ results.put("perc5tunf"
+ + wmtbfPercentile,
+ "" + tunfList.get((5 * tunfList.size()) / 100));
+ }
+
+ /* If this is the simulation using default values, compare
+ * selected Stable relays with observed Stable relays. */
+ if (wmtbfPercentile == 50) {
+ Set<String> intersection = new HashSet<String>();
+ intersection.addAll(stableRelays);
+ intersection.retainAll(selectedRelays);
+ Set<String> observedOnly = new HashSet<String>();
+ observedOnly.addAll(stableRelays);
+ observedOnly.removeAll(selectedRelays);
+ Set<String> simulatedOnly = new HashSet<String>();
+ simulatedOnly.addAll(selectedRelays);
+ simulatedOnly.removeAll(stableRelays);
+ results.put("stableintersect", "" + intersection.size());
+ results.put("stableobserved", "" + observedOnly.size());
+ results.put("stablesimulated", "" + simulatedOnly.size());
+ }
+ }
+
+ /* Write results. */
+ bw.write(lastValidAfter);
+ for (String column : columns) {
+ if (results.containsKey(column)) {
+ bw.write("," + results.get(column));
+ } else {
+ bw.write(",NA");
+ }
+ }
+ bw.write("\n");
+ }
+
+ /* We're done with this consensus. Prepare for the next. */
+ runningRelays.clear();
+ guardRelays.clear();
+ stableRelays.clear();
+ lastButOneValidAfter = lastValidAfter;
+ }
+
+ /* Add the running relay lines to a map that we parse once we have
+ * all lines of a consensus. */
+ String fingerprint = parts[1];
+ runningRelays.put(fingerprint, line);
+ if (parts[3].equals("t")) {
+ stableRelays.add(fingerprint);
+ }
+ if (parts[4].equals("t")) {
+ guardRelays.add(fingerprint);
+ }
+ lastValidAfter = validAfter;
+ }
+ bw.close();
+ }
+}
+
diff --git a/task-2911/mtbf-sim/SimulateMeanTimeBetweenFailure.java b/task-2911/mtbf-sim/SimulateMeanTimeBetweenFailure.java
deleted file mode 100644
index cd73f82..0000000
--- a/task-2911/mtbf-sim/SimulateMeanTimeBetweenFailure.java
+++ /dev/null
@@ -1,351 +0,0 @@
-/**
- * Simulate variation of mean time between failure on Stable relays. The
- * simulation is based on the previously generated SQL results containing
- * network status entries and parts of server descriptors. In a first
- * step, parse the SQL results that are in descending order to calculate
- * time until next failure for all relays and write them to disk as one
- * file per network status in tunf/$filename. (Skip this step if there is
- * already a tunf/ directory.) In a second step, parse the network
- * statuses again, but this time from first to last, calculate mean times
- * between failure for all relays, form relay subsets based on minimal
- * MTBF, look up what the time until next failure would be for a subset,
- * and write results to mtbf-sim.csv to disk. */
-import java.io.*;
-import java.text.*;
-import java.util.*;
-public class SimulateMeanTimeBetweenFailure {
- public static void main(String[] args) throws Exception {
-
- /* Measure how long this execution takes. */
- long started = System.currentTimeMillis();
-
- /* Decide whether we need to do the reverse run, or if we can use
- * previous results. */
- if (!new File("tunf").exists()) {
-
- /* For each relay as identified by its hex encoded fingerprint,
- * track time until next failure in seconds in a long. */
- SortedMap<String, Long> knownRelays = new TreeMap<String, Long>();
-
- /* Parse previously exported network status entries in reverse
- * order. */
- SimpleDateFormat formatter = new SimpleDateFormat(
- "yyyy-MM-dd-HH-mm-ss");
- formatter.setTimeZone(TimeZone.getTimeZone("UTC"));
- SimpleDateFormat isoFormatter = new SimpleDateFormat(
- "yyyy-MM-dd HH:mm:ss");
- isoFormatter.setTimeZone(TimeZone.getTimeZone("UTC"));
- Map<String, String> runningRelays = new HashMap<String, String>();
- BufferedReader br = new BufferedReader(new FileReader(
- "running-relays-reverse.csv"));
- String line, lastValidAfter = null, lastButOneValidAfter = null;
- while ((line = br.readLine()) != null) {
- if (!line.startsWith("20")) {
- continue;
- }
- String[] parts = line.split(",");
- String validAfter = parts[0];
- if (lastValidAfter != null &&
- !lastValidAfter.equals(validAfter)) {
-
- /* We just parsed all lines of a consensus. Let's write times
- * until next failure to disk for all running relays and update
- * our internal history. */
- if (lastButOneValidAfter == null) {
- lastButOneValidAfter = lastValidAfter;
- }
- long lastValidAfterMillis = isoFormatter.parse(lastValidAfter).
- getTime();
- File tunfFile = new File("tunf",
- formatter.format(lastValidAfterMillis));
- tunfFile.getParentFile().mkdirs();
- BufferedWriter bw = new BufferedWriter(new FileWriter(
- tunfFile));
- long secondsSinceLastValidAfter =
- (isoFormatter.parse(lastButOneValidAfter).getTime()
- - lastValidAfterMillis) / 1000L;
-
- /* Iterate over our history first and see if these relays have
- * been running in the considered consensus. Remember changes
- * to our history and modify it below to avoid concurrent
- * modification errors. */
- Set<String> removeFromHistory = new HashSet<String>();
- Map<String, Long> addToHistory = new HashMap<String, Long>();
- for (Map.Entry<String, Long> e : knownRelays.entrySet()) {
- String fingerprint = e.getKey();
- if (runningRelays.containsKey(fingerprint)) {
-
- /* This relay has been running, so write it to the output
- * file and update our history. */
- long hoursUntilFailure = e.getValue();
- bw.write(fingerprint + "," + (secondsSinceLastValidAfter
- + hoursUntilFailure) + "\n");
- boolean restarted = runningRelays.get(fingerprint).
- split(",")[2].equals("t");
- if (restarted) {
- removeFromHistory.add(fingerprint);
- } else {
- addToHistory.put(fingerprint, secondsSinceLastValidAfter
- + hoursUntilFailure);
- }
- runningRelays.remove(fingerprint);
- } else {
-
- /* This relay has not been running, so remove it from our
- * history. */
- removeFromHistory.add(fingerprint);
- }
- }
-
- /* Update our history for real now. We couldn't do this above,
- * or we'd have modified the set we've been iterating over. */
- for (String f : removeFromHistory) {
- knownRelays.remove(f);
- }
- for (Map.Entry<String, Long> e : addToHistory.entrySet()) {
- knownRelays.put(e.getKey(), e.getValue());
- }
-
- /* Iterate over the relays that we found in the consensus, but
- * that we didn't have in our history. */
- for (Map.Entry<String, String> e : runningRelays.entrySet()) {
- String fingerprint = e.getKey();
- bw.write(fingerprint + ",0\n");
- boolean restarted = e.getValue().split(",")[2].equals("t");
- if (!restarted) {
- knownRelays.put(fingerprint, 0L);
- }
- }
- bw.close();
-
- /* Prepare for next consensus. */
- runningRelays = new HashMap<String, String>();
- lastButOneValidAfter = lastValidAfter;
- }
-
- /* Add the running relay lines to a map that we parse once we have
- * all lines of a consensus. */
- String fingerprint = parts[1];
- runningRelays.put(fingerprint, line);
- lastValidAfter = validAfter;
- }
- }
-
- /* Run the simulation for the following WMTBF percentiles: */
- List<Long> requiredWMTBFs = new ArrayList<Long>();
- for (long l : new long[] { 20, 30, 40, 50, 60, 70, 80 }) {
- requiredWMTBFs.add(l);
- }
- Collections.sort(requiredWMTBFs);
- BufferedWriter bw = new BufferedWriter(new FileWriter(
- "mtbf-sim.csv"));
- bw.write("time");
- for (long requiredWMTBF : requiredWMTBFs) {
- bw.write(",mtunf" + requiredWMTBF + ",perc75tunf" + requiredWMTBF
- + ",perc80tunf" + requiredWMTBF + ",perc85tunf" + requiredWMTBF
- + ",perc90tunf" + requiredWMTBF + ",perc95tunf" + requiredWMTBF
- + ",wmtbf" + requiredWMTBF);
- }
- bw.write("\n");
-
- /* For each relay as identified by its base-64 encoded fingerprint,
- * track weighted run length, total run weights, and current run
- * length in a double[3]. */
- SortedMap<String, double[]> knownRelays =
- new TreeMap<String, double[]>();
-
- /* Parse previously exported network status entries again, but this
- * time in forward order. */
- SimpleDateFormat formatter = new SimpleDateFormat(
- "yyyy-MM-dd-HH-mm-ss");
- formatter.setTimeZone(TimeZone.getTimeZone("UTC"));
- SimpleDateFormat isoFormatter = new SimpleDateFormat(
- "yyyy-MM-dd HH:mm:ss");
- isoFormatter.setTimeZone(TimeZone.getTimeZone("UTC"));
- Map<String, String> runningRelays = new HashMap<String, String>(),
- lastRunningRelays = new HashMap<String, String>();
- BufferedReader br = new BufferedReader(new FileReader(
- "running-relays-forward.csv"));
- String line, lastValidAfter = null, firstValidAfter = null;
- long nextWeightingInterval = -1L;
- while ((line = br.readLine()) != null) {
- if (!line.startsWith("20")) {
- continue;
- }
- String[] parts = line.split(",");
- String validAfter = parts[0];
- if (firstValidAfter == null) {
- firstValidAfter = validAfter;
- }
- if (lastValidAfter != null &&
- !lastValidAfter.equals(validAfter)) {
-
- /* We just parsed all lines of a consensus. First, see if 12
- * hours have passed since we last discounted weighted run lengths
- * and total run weights. If so, discount both variables for all
- * known relays by factor 0.95 (or 19/20 since these are long
- * integers) and remove those relays with a total run weight below
- * 1/10000. */
- long lastValidAfterMillis = isoFormatter.parse(lastValidAfter).
- getTime();
- long validAfterMillis = isoFormatter.parse(validAfter).getTime();
- long weightingInterval = validAfterMillis
- / (12L * 60L * 60L * 1000L);
- if (nextWeightingInterval < 0L) {
- nextWeightingInterval = weightingInterval;
- }
- while (weightingInterval > nextWeightingInterval) {
- Set<String> relaysToRemove = new HashSet<String>();
- for (Map.Entry<String, double[]> e : knownRelays.entrySet()) {
- double[] w = e.getValue();
- w[0] *= 0.95;
- w[1] *= 0.95;
- }
- for (String fingerprint : relaysToRemove) {
- knownRelays.remove(fingerprint);
- }
- nextWeightingInterval += 1L;
- }
-
- /* Update history for running relays. Start by iterating over all
- * relays in the history, see if they're running now and whether
- * they have been restarted. Distinguish four cases for relays in
- * the history: 1) still running, 2) still running but restarted,
- * 3) started in this consensus, 4) stopped in this consensus. */
- double secondsSinceLastValidAfter =
- (double) ((validAfterMillis - lastValidAfterMillis) / 1000L);
- Set<String> updatedRelays = new HashSet<String>();
- for (Map.Entry<String, double[]> e : knownRelays.entrySet()) {
- String fingerprint = e.getKey();
- double[] w = e.getValue();
- if (runningRelays.containsKey(fingerprint)) {
- if (w[2] > 0.1) {
- if (!runningRelays.get(fingerprint).split(",")[2].
- equals("t")) {
-
- /* Case 1) still running: */
- w[2] += secondsSinceLastValidAfter;
- } else {
-
- /* Case 2) still running but restarted: */
- w[0] += w[2];
- w[1] += 1.0;
- w[2] = secondsSinceLastValidAfter;
- }
- } else {
-
- /* Case 3) started in this consensus: */
- w[2] = secondsSinceLastValidAfter;
- }
-
- /* Mark relay as already processed, or we'd add it to the
- * history as a new relay below. */
- updatedRelays.add(fingerprint);
- } else if (w[2] > 0.1) {
-
- /* Case 4) stopped in this consensus: */
- w[0] += w[2];
- w[1] += 1.0;
- w[2] = 0.0;
- }
- }
-
- /* Iterate over the set of currently running relays and add those
- * that we haven't processed above to our history. */
- for (String fingerprint : runningRelays.keySet()) {
- if (!updatedRelays.contains(fingerprint)) {
- updatedRelays.add(fingerprint);
- knownRelays.put(fingerprint, new double[] { 0.0, 0.0,
- secondsSinceLastValidAfter });
- }
- }
-
- /* Calculate WMTBFs for all running relays and put them in a list
- * that we can sort by WMTBF in descending order. */
- List<String> wmtbfs = new ArrayList<String>();
- for (String fingerprint : runningRelays.keySet()) {
- double[] w = knownRelays.get(fingerprint);
- double totalRunLength = w[0] + w[2];
- double totalWeights = w[1] + (w[2] > 0.1 ? 1.0 : 0.0);
- long wmtbf = totalWeights < 0.0001 ? 0
- : (long) (totalRunLength / totalWeights);
- wmtbfs.add(String.format("%012d %s", wmtbf, fingerprint));
- }
- Collections.sort(wmtbfs, Collections.reverseOrder());
-
- /* Read previously calculated TUNFs from disk. */
- Map<String, Long> tunfs = new HashMap<String, Long>();
- File tunfFile = new File("tunf",
- formatter.format(lastValidAfterMillis));
- if (!tunfFile.exists()) {
- if (!lastValidAfter.equals(firstValidAfter)) {
- System.out.println("Could not find file " + tunfFile
- + ". Skipping simulation!");
- }
- } else {
- BufferedReader tunfBr = new BufferedReader(new FileReader(
- tunfFile));
- String tunfLine;
- while ((tunfLine = tunfBr.readLine()) != null) {
- String[] tunfParts = tunfLine.split(",");
- tunfs.put(tunfParts[0], Long.parseLong(tunfParts[1]));
- }
- tunfBr.close();
-
- /* Run the simulation for the relays in the current consensus
- * for various required WFUs. */
- bw.write(isoFormatter.format(lastValidAfterMillis));
- long totalRelays = (long) wmtbfs.size(), selectedRelays = 0L,
- totalTunf = 0L, minimalWmtbf = 0L;
- int simulationIndex = 0;
- List<Long> tunfList = new ArrayList<Long>();
- for (String relay : wmtbfs) {
- while (simulationIndex < requiredWMTBFs.size() &&
- selectedRelays * 100L > totalRelays
- * requiredWMTBFs.get(simulationIndex)) {
- if (selectedRelays == 0L) {
- bw.write(",NA,NA,NA,NA,NA,NA");
- } else {
- Collections.sort(tunfList, Collections.reverseOrder());
- long perc75 = tunfList.get((75 * tunfList.size()) / 100);
- long perc80 = tunfList.get((80 * tunfList.size()) / 100);
- long perc85 = tunfList.get((85 * tunfList.size()) / 100);
- long perc90 = tunfList.get((90 * tunfList.size()) / 100);
- long perc95 = tunfList.get((95 * tunfList.size()) / 100);
- bw.write("," + (totalTunf / selectedRelays) + "," + perc75
- + "," + perc80 + "," + perc85 + "," + perc90 + ","
- + perc95);
- }
- bw.write("," + minimalWmtbf);
- simulationIndex++;
- }
- String[] wmtbfParts = relay.split(" ");
- minimalWmtbf = Long.parseLong(wmtbfParts[0]);
- String fingerprint = wmtbfParts[1];
- long tunf = tunfs.get(fingerprint);
- totalTunf += tunf;
- tunfList.add(tunf);
- selectedRelays += 1L;
- }
- bw.write("\n");
- }
-
- /* We're done with this consensus. Prepare for the next. */
- lastRunningRelays = runningRelays;
- runningRelays = new HashMap<String, String>();
- }
-
- /* Add the running relay lines to a map that we parse once we have
- * all lines of a consensus. */
- String fingerprint = parts[1];
- runningRelays.put(fingerprint, line);
- lastValidAfter = validAfter;
- }
- bw.close();
-
- /* Print how long this execution took and exit. */
- System.out.println("Execution took " + ((System.currentTimeMillis()
- - started) / (60L * 1000L)) + " minutes.");
- }
-}
-
diff --git a/task-2911/mtbf-sim/mtbf-sim.R b/task-2911/mtbf-sim/mtbf-sim.R
deleted file mode 100644
index a630406..0000000
--- a/task-2911/mtbf-sim/mtbf-sim.R
+++ /dev/null
@@ -1,73 +0,0 @@
-library(ggplot2)
-
-data <- read.csv("mtbf-sim.csv", stringsAsFactors = FALSE)
-d <- data[data$time >= '2010' & data$time < '2011', ]
-d <- aggregate(d[, 2:length(d)], by = list(date = as.Date(d$time)), mean)
-d <- rbind(
- data.frame(x = d$wmtbf30, y = d$perc90tunf30, sim = "30 %"),
- data.frame(x = d$wmtbf40, y = d$perc90tunf40, sim = "40 %"),
- data.frame(x = d$wmtbf50, y = d$perc90tunf50, sim = "50 % (default)"),
- data.frame(x = d$wmtbf60, y = d$perc90tunf60, sim = "60 %"),
- data.frame(x = d$wmtbf70, y = d$perc90tunf70, sim = "70 %"))
-ggplot(d, aes(x = x / (24 * 60 * 60), y = y / (60 * 60))) +
-facet_wrap(~ sim) +
-geom_path() +
-scale_x_continuous("\nRequired WMTBF in days",
- breaks = seq(0, max(d$x, na.rm = TRUE) / (24 * 60 * 60), 7),
- minor = seq(0, max(d$x, na.rm = TRUE) / (24 * 60 * 60), 1)) +
-scale_y_continuous(paste("Time in hours until 10 % of relays\nor ",
- "27.1 % of streams have failed\n", sep = ""),
- breaks = seq(0, max(d$y, na.rm = TRUE) / (60 * 60), 24))
-ggsave(filename = "mtbf-sim.pdf", width = 8, height = 5, dpi = 100)
-
-## Commented out, because this graph is meaningless in b/w. The graph
-## above contains the same data, but can be printed in b/w.
-#data <- read.csv("mtbf-sim.csv", stringsAsFactors = FALSE)
-#d <- data[data$time >= '2010' & data$time < '2011', ]
-#d <- aggregate(d[, 2:length(d)], by = list(date = as.Date(d$time)), mean)
-#d <- rbind(
-# data.frame(x = d$wmtbf70, y = d$perc90tunf70, sim = "70 %"),
-# data.frame(x = d$wmtbf60, y = d$perc90tunf60, sim = "60 %"),
-# data.frame(x = d$wmtbf50, y = d$perc90tunf50, sim = "50 % (default)"),
-# data.frame(x = d$wmtbf40, y = d$perc90tunf40, sim = "40 %"),
-# data.frame(x = d$wmtbf30, y = d$perc90tunf30, sim = "30 %"))
-#ggplot(d, aes(x = x / (24 * 60 * 60), y = y / (60 * 60),
-# colour = sim)) +
-#geom_path() +
-#scale_x_continuous("\nRequired WMTBF in days",
-# breaks = seq(0, max(d$x, na.rm = TRUE) / (24 * 60 * 60), 7),
-# minor = seq(0, max(d$x, na.rm = TRUE) / (24 * 60 * 60), 1)) +
-#scale_y_continuous(paste("Time until \n10 % of relays or \n",
-# "27.1 % of streams \nhave failed \nin hours ", sep = ""),
-# breaks = seq(0, max(d$y, na.rm = TRUE) / (60 * 60), 24)) +
-#scale_colour_hue("Fraction of relays\nby highest WMTBF",
-# breaks = c("30 %", "40 %", "50 % (default)", "60 %", "70 %")) +
-#opts(axis.title.x = theme_text(size = 12 * 0.8, face = "bold",
-# hjust = 0.5),
-# axis.title.y = theme_text(size = 12 * 0.8, face = "bold", vjust = 0.5,
-# hjust = 1))
-#ggsave(filename = "mtbf-sim.pdf", width = 8, height = 5, dpi = 100)
-
-## Commented out, because focusing on the development over time is the
-## wrong thing here.
-#simulations <- paste("mtunf", c(20, 30, 40, 50, 60, 70, 80),
-# sep = "")
-#d <- data[data$time >= '2010' & data$time < '2011',
-# c("time", simulations)]
-#d <- aggregate(d[, 2:length(d)], by = list(date = as.Date(d$time)), mean)
-#d <- melt(d, id.vars = 1)
-#ggplot(d, aes(x = date, y = value / (24 * 60 * 60), colour = variable)) +
-#geom_line() +
-#scale_x_date("", major = "3 months", minor = "1 month",
-# format = "%b %Y") +
-#scale_y_continuous(paste("Mean time \nuntil next \nfailure \n",
-# "in days \n", sep = ""),
-# limits = c(0, max(d$value, na.rm = TRUE) / (24 * 60 * 60))) +
-#scale_colour_hue(paste("Percentile\nhighest\nweighted mean\n",
-# "time between\nfailures", sep = ""), breaks = simulations,
-# labels = paste(substr(simulations, 6, 9),
-# ifelse(simulations == "mtunf50", "(default)", ""))) +
-#opts(axis.title.y = theme_text(size = 12 * 0.8, face = "bold",
-# vjust = 0.5, hjust = 1))
-#ggsave(filename = "mtbf-sim1.pdf", width = 8, height = 5, dpi = 100)
-
diff --git a/task-2911/report.bib b/task-2911/report.bib
new file mode 100644
index 0000000..63ab260
--- /dev/null
+++ b/task-2911/report.bib
@@ -0,0 +1,31 @@
+@misc{proposal146,
+ author = {Nick Mathewson},
+ title = {Add new flag to reflect long-term stability},
+ note = {\url{https://gitweb.torproject.org/torspec.git/blob_plain/HEAD:/proposals/146-long-term-stability.txt}},
+}
+
+@misc{dirspec,
+ author = {Roger Dingledine and Nick Mathewson},
+ title = {Tor directory protocol, version 3},
+ note = {\url{https://gitweb.torproject.org/tor.git/blob_plain/HEAD:/doc/spec/dir-spec.txt}},
+}
+
+@phdthesis{loesing2009thesis,
+ title = {Privacy-enhancing Technologies for Private Services},
+ author = {Karsten Loesing},
+ school = {University of Bamberg},
+ year = {2009},
+ month = {May},
+ note = {\url{http://www.opus-bayern.de/uni-bamberg/volltexte/2009/183/pdf/loesingopusneu.pdf}},
+}
+
+@techreport{loesing2011overview,
+ title = {Overview of Statistical Data in the {Tor} Network},
+ author = {Karsten Loesing},
+ institution = {The Tor Project},
+ year = {2011},
+ month = {March},
+ type = {Technical Report},
+ note = {\url{https://metrics.torproject.org/papers/data-2011-03-14.pdf}},
+}
+
diff --git a/task-2911/report.tex b/task-2911/report.tex
index 4dc6ab9..96fe38f 100644
--- a/task-2911/report.tex
+++ b/task-2911/report.tex
@@ -4,74 +4,291 @@
\usepackage{graphics}
\usepackage{color}
\begin{document}
-\title{An Analysis of Tor Relay Stability\\(DRAFT)}
+\title{An Analysis of Tor Relay Stability}
\author{Karsten Loesing\\{\tt karsten(a)torproject.org}}
+\date{June 30, 2011}
\maketitle
\section{Introduction}
-The Tor network consists of 2,200 relays and 600 bridges run by
+The Tor network consists of around 2,000 relays and 500 bridges run by
volunteers, some of which are on dedicated servers and some on laptops or
mobile devices.
-% TODO Look up more recent relay and bridge numbers. -KL
Obviously, we can expect the relays run on dedicated servers to be more
``stable'' than those on mobile phones.
But it is difficult to draw a line between stable and unstable relays.
In most cases it depends on the context which relays count as stable:
-\begin{itemize}
+\begin{enumerate}
\item A stable relay that is supposed to be part of a circuit for a
\emph{long-running stream} should not go offline during the next day.
+If only 1 of typically 3 relays in a circuit goes away, the stream
+collapses and must be rebuilt.
\item A stable relay that clients pick as \emph{entry guard} doesn't have
to be running continuously, but should be online most of the time in the
upcoming weeks.
+In addition to being stable, an entry guard should have reasonable
+bandwidth capacity in order not to slow down clients.
\item A stable relay that acts as \emph{hidden-service directory} should
be part of a relay subset that mostly overlaps with the subsets 1, 2, or
even 3 hours in the future.
That means that the relays in this set should be stable, but also that not
-too many new relays should join the set of stable relays at once.
-\item A stable relay that clients use in a \emph{fallback consensus} that
-is already a few days or even weeks old should still be available on the
-same IP address and port.\footnote{See also proposal 146.}
-Such a relay doesn't necessarily have to run without interruption, though.
-% TODO Correctly cite proposal 146 here. -KL
+too many new relays should join the set at once.
+\item A stable relay that clients use in a \emph{fallback consensus}
+\cite{proposal146} that is already a few days or even weeks old should
+still be available on the same IP address and port, but
+doesn't necessarily have to run without interruption.
\item A stable \emph{bridge relay} should be running on the same IP
-address a few days after a client learns about the bridge, but again,
-doesn't have to run continuously.
-\end{itemize}
-
-All these stability notions have in common that some relays or bridges are
-better suited for the described contexts than others.
-In this analysis we will look at various relay stability metrics to find
-the best suited set of relays for each context.
-The idea of this report is to use the results to optimize how the
-directory authorities assign relay flags that clients use to make path
-select decisions.
-
-For every context, we try to simulate what requirements based on past
-observations would have resulted in what relay stabilities in the near
-future.
-Generally, we'd expect that stricter requirements lead to higher
-stability.
-But every prediction contains a certain amount of randomness, so that we
-cannot tighten the requirements arbitrarily.
-Further, we want to ensure that the subset of relays identified as stable
-does not become too small.
-The reason is that there should be some diversity, so that not a few
-operators can aim at running most relays used in a given context.
-In some cases, the stable relays also need to provide sufficient bandwidth
-to the network in order not to become a performance bottleneck.
-We are going into more details about the requirements when looking into
-the separate analyses in the sections below.
-
-The analysis data and tools are available on the Tor metrics website at
-\url{https://metrics.torproject.org/}.\footnote{Or rather, will be made
-available.}
+address a few days after a client learns about the bridge and should be
+available most of the time in the upcoming weeks.
+\end{enumerate}
+
+The Tor directory authorities measure relay stability for the first three
+contexts listed above and assign the Stable, Guard, and HSDir flags that
+clients use to select relays.
+Figure~\ref{fig:relayflags} shows the number of relays with relay flags
+assigned between July and December 2010 which will be our analysis
+interval.
+
+\begin{figure}[t]
+\includegraphics[width=\textwidth]{relayflags.pdf}
+\caption{Number of relays with relay flags Running, Stable, and Guard
+assigned by the directory authorities between July and December 2010}
+\label{fig:relayflags}
+\end{figure}
+
+In this analysis, we use a simulator to resemble how the directory
+authorities assign the Stable and Guard relay flags.
+This simulator uses archived directory data to decide when a relay was
+running and when it failed or was restarted.
+We further use this simulator to calculate future stability metrics that
+help us evaluate the quality of a given relay flag assignment.
+We modify the input parameters to Tor's stability metrics to see whether
+we can improve how the directory authorities should assign relay flags.
+The analysis data and simulator used in this report are available on the
+Tor metrics website at \url{https://metrics.torproject.org/}.
+
+\section{Requirements for Stable and Guard flags}
+
+The requirements for assigning the Stable and the Guard flags are defined
+in the Tor directory protocol specification \cite{dirspec}.
+These definitions are revised here to better reflect what is implemented
+in the code:
+
+\begin{quote}
+``A router is `Stable' if it is active, and either its Weighted MTBF is at
+least the median for known active routers or its Weighted MTBF corresponds
+to at least [5] days.
+[...]
+A router is a possible `Guard' [if it is `familiar',] if its
+Weighted Fractional
+Uptime is at least the median for `familiar' active routers [or its
+Weighted Fractional Uptime is at least 98~\%], and if
+its [advertised] bandwidth is at least median [of all active routers] or
+at least 250KB/s.
+[...]
+A node is `familiar' if 1/8 of all active nodes have appeared more
+recently than it, or it has been around for [a weighted time of 8 days].''
+\end{quote}
+
+These definitions entail four requirements for assigning relay flags, one
+for the Stable flag and three for the Guard flag:
+\begin{description}
+\item[Weighted Mean Time Between Failure (WMTBF):]
+The WMTBF metric is used to track the length of continuous uptime sessions
+over time.
+The (unweighted) MTBF part measures the average uptime between a relay
+showing up in the network and either leaving or failing.
+In the weighted form of this metric, which is used here, past sessions
+are discounted by factor $0.95$ every $12$~hours.
+Current uptime sessions are not discounted, so that a WMTBF value of
+5~days can be reached after 5~days at the earliest.
+\item[Weighted Fractional Uptime (WFU):] The WFU metric measures the
+fraction of uptime of a relay in the past.
+Similar to WMTBF, WFU values are discounted by factor $0.95$ every
+$12$~hours, but in this case including the current uptime session.
+\item[Weighted Time:] The Weighted Time metric is used to calculate a
+relay's WFU and to decide whether a relay is around long enough to be
+considered `familiar.'
+The Weighted Time is discounted similar to WMTBF and WFU, so that a
+Weighted Time of 8 days can be reached after around 16 days at the
+earliest.
+\item[Advertised Bandwidth:] The Advertised Bandwidth of a relay is the
+minimum of its configured average bandwidth rate and the maximum observed
+bandwidth over any ten second period in the past day.
+It should be noted that the advertised bandwidth is self-reported by
+relays and has been misused in the past to attract more traffic than a
+relay should see.
+In theory, using the advertised bandwidth value has become discouraged
+for anything critical.
+\end{description}
+
+All four requirements have in common that they consist of a dynamic part
+that relies on the current network situation (e.g., median of all WMTBF
+values for the Stable flag) and a static part that is independent
+of other relays (e.g., WMTBF value of 5 days or higher).
+The dynamic part ensures that a certain fraction of relays get the
+Stable and Guard flags assigned even in a rather unstable network.
+The static part ensures that rather stable (or fast) relays are not denied
+the flags even when most of the other relays in the network are highly
+stable (or very fast).
+
+\section{Obtaining data for relay stability analysis}
+
+The internal data that the directory authorities use to decide whether a
+relay should get the Stable or Guard flag assigned is not publicly
+available.
+Instead, we rely on the network status consensuses and server descriptors
+that are archived and publicly available since October
+2007.
+The network status consensuses tell us which relays were available with a
+granularity of 1~hour, and the server descriptors help us figure out
+whether a relay was restarted in the 1~hour before being listed in a
+network status.
+We further learn whether a relay got the Stable and/or Guard flag assigned
+and what bandwidth it advertised and actually used for relaying data at a
+given time.
+In detail, we obtain the following data for this analysis:
+
+\begin{description}
+\item[Valid-after time:] The time when a network status consensus was
+published.
+\item[Fingerprint:] A relay's unique public key fingerprint.
+\item[Restarted:] Was a relay restarted within the last hour before the
+valid-after time based on its self-reported uptime?
+\item[Stable:] Did the directory authorities assign the Stable flag to a
+relay?
+\item[Guard:] Did the directory authorities assign the Guard flag to a
+relay?
+\item[Advertised bandwidth:] A relay's self-reported advertised bandwidth.
+\item[Bandwidth history:] How many bytes did the relay write on a given
+day?
+\end{description}
+
+The choice for using these archived data instead of, e.g., trying to
+obtain the internal relay stability data that the directory authorities
+use has a few advantages and disadvantes.
+The main disadvantage is that our data has a granularity of one hour and
+can only detect a single failure or restart within this hour.
+It's unclear which effect this lack of detail has on less stable relays.
+
+But there are a few advantages of using the archived network data:
+We have a few years of data available that we can use for the analysis.
+If we started obtaining original stability data from the directory
+authorities, we'd have to wait a few months before conducting this
+analysis.
+Also, it's still unclear whether the Tor code that assigns relay flags is
+correct, so it makes sense to use a different data basis.
+Finally, we need the directory archives anyway to evaluate how stable or
+fast a relay turned out to be after being selected.
+
+\section{Simulating current Stable/Guard assignments}
+
+The first step before varying the requirements for assigning relay flags
+is to run a simulation with the current default requirements.
+Only if we manage to come up with similar results as the directory
+authorities, we can hope that our suggested parameter changes will have
+similar effects in the real Tor network.
+
+Figure~\ref{fig:default-reqs} shows the fractions of relays that got the
+Stable and Guard flags assigned by the directory
+authorities (``observed'' lines) and in our simulation with default
+requirements (``simulated'' lines).
+Ideally, the observed lines should match the simulated lines.
+The two Guard lines overlap for about half of the observed time interval
+and the difference is always below 5~\% of running relays, which seems to
+be acceptable.
+The fraction of Guard relays in the simulation is rather stable at 28~\%
+whereas the observed fraction goes up to 33~\% for three months.
+The observed Stable line seems to be systematically 5 to 10~\% higher than
+the simulated line.
+
+\begin{figure}[t]
+\includegraphics[width=\textwidth]{default-reqs.pdf}
+\caption{Fraction of relays that got the Stable and Guard flag assigned by
+the directory authorities and in our simulation with default requirements}
+\label{fig:default-reqs}
+\end{figure}
+
+We first investigate the differences by looking in how far the sets of
+observed and simulated sets overlap.
+After all, it could be that our simulated 30~\% of Guard relays are a
+completely different subset of relays than the observed 30~\%.
+Figure~\ref{fig:diff-sim-obs} shows the absolute number of relays in the
+intersection and the sets of only observed or only simulated relays.
+This graph shows that the majority of relay assignments overlap for both
+flags.
+The sets of Stable relays that are only found in the simulation is rather
+small with around 50 relays.
+Compared to that, there are between 100 and 200 relays on average that got
+the Stable flag assigned by the directory authorities but which did not
+qualify for that flag in the simulation.
+The situation of assigned Guard flags is somewhat different.
+In July and August 2010, there are about 50 relays in the only-observed
+and only-simulated sets.
+From September 2010 on, there are hardly any relays in the only-simulated
+set, but the number of relays in the only-observed set goes up to nearly
+100.
+
+\begin{figure}[t]
+\includegraphics[width=\textwidth]{diff-sim-obs.pdf}
+\caption{Number of relays that got the Stable and Guard flag assigned by
+both the directory authorities and by our simulator or by just one of
+them}
+\label{fig:diff-sim-obs}
+\end{figure}
+
+Before accepting these deviations as a given, we take a quick look at the
+actual requirements to learn whether the dynamic or the static part of
+requirements was more relevant.
+Figure~\ref{fig:requirements} shows the dynamic parts as daily means (dark
+gray lines) and daily min-max ranges (light gray ribbons) as well as the
+static parts (dashed lines).
+The dashed lines act as a limit here: if a dynamic requirement based on
+the other relays exceeds the dashed line, the requirement is cut to the
+fixed value and the fraction of relays meeting the requirement increases.
+Whenever the dynamic requirement remains below the dashed line, the
+fraction of relays that get flags assigned should remain more or less the
+same.
+For example, the top left graph indicates that it's quite possible that
+more than 50~\% of relays got the Stable flag assigned from July
+to November, but that this fraction should have dropped to 50~\% in
+December 2010.
+However, this was not the case.
+The graph also indicates that the 250 KiB/s limit was never reached, so
+that relays were always selected based on the comparison to the advertised
+bandwidth of the other relays.
+
+\begin{figure}
+\includegraphics[width=\textwidth]{requirements.pdf}
+\caption{Simulated requirements for assigning the Stable and Guard flags}
+\label{fig:requirements}
+\end{figure}
+
+Possible reasons for deviation of simulation and actual assignments by the
+directory authorities are:
+
+\begin{enumerate}
+\item The simulator code may contain bugs.
+\item Our data with a granularity of 1~hour lack the details for detecting
+restarts and failures and thereby make it hard to observe uptime sessions
+correctly.
+\item The directory authorities have slightly different views on the
+network which then get mixed in the voting process.
+\item The implementation of relay history on the directory authorities may
+contain bugs.
+\end{enumerate}
+
+For the remainder of this analysis we will assume that the simulated
+number of Stable relays is 5 to 10~\% lower than in reality and that the
+simulation of Guard is more or less accurate.
\section{Choosing relays for long-lived streams}
\label{sec:mtbf-sim}
+After learning that our simulation of relay stability is at least not
+totally off, we want to take a closer look at the Stable flag.
Whenever clients request Tor to open a long-lived stream, Tor should try
to pick only those relays for the circuit that are not likely to disappear
shortly after.
@@ -80,65 +297,81 @@ new circuit needs to be built.
Depending on how well the application handles connection failures this may
impact usability significantly.
-In order to declare some relays as more useful for long-lived streams, the
-directory authorities track uptime sessions of all relays over time.
-Based on this history, they calculate the \emph{weighted mean time between
-failure (WMTBF)} for each relay.
-The MTBF part simply measures the average uptime between a relay showing
-up in the Tor network and either leaving or failing.
-In the weighted form of this metric, which is used here, older sessions
-are weighted to count less.
-The directory authorities assign the \texttt{Stable} flag to the 50~\% of
-relays with the highest WMTBF.
-
-In this simulation we want to find out how useful the WMTBF metric is for
-predicting future stability and how stability would be affected when
-declaring more or less than 50~\% of the relays as stable.
-The metric we chose for evaluating how stable a relay is is the \emph{time
+The WMTBF metric as the requirement for assigning the Stable flag has
+already been discussed above.
+Now we want to find out how useful WMTBF is to predict which relays are
+not likely to leave or crash in the near future.
+In order to evaluate future relay stability we measure the \emph{time
until next failure}.
-When running a simulation we determine the time until 10~\% of the
-``stable'' relays have failed.
+There is no need to measure more than the current uptime session length,
+and hence there is no need to weight measurements.
+For a given set of relays with the Stable flag we determine the 10th
+percentile of time until next failure.
+This is the time when 10~\% of relays have failed and 90~\% are still
+running.
Under the (grossly simplified) assumption that relays are chosen
uniformly, $1 - 0.9^3 = 27.1~\%$ of streams using relays from this set
-would have failed up to this point.
+would have been interrupted up to this point.
+
+The default requirement is that a relay's WMTBF is at least the median for
+known relays or at least 5 days.
+We simulate times until next failure for the 30th, 40th, 50th, 60th, and
+70th percentiles of WMTBF values in the network while leaving the fixed
+5-day constant unchanged.
+We also look up times until next failure for the set of Stable relays that
+got their flags from the directory authorities.
+Figure~\ref{fig:wmtbf-tunf-sim} shows the results.
+The artificial steps come from our limitation to measure time until next
+failure in more detail than in full hours.
+The further right a line is the higher is the time until next failure for
+the considered consensuses from July to December 2010.
\begin{figure}[t]
-\includegraphics[width=\textwidth]{mtbf-sim.pdf}
-\caption{Impact of assigning the \texttt{Stable} flag to a given fraction
-of relays on the actual required WMTBF ($x$ axis) and on the time
-until 10~\% of relays or 27.1~\% of streams have failed ($y$ axis)}
-\label{fig:mtbf-sim}
+\includegraphics[width=\textwidth]{wmtbf-tunf-sim.pdf}
+\caption{Impact of changing the WMTBF percentile requirement for assigning
+the Stable flag on the expected time until next failure}
+\label{fig:wmtbf-tunf-sim}
\end{figure}
-Figure~\ref{fig:mtbf-sim} shows the analysis results for assigning the
-\texttt{Stable} flag to fractions of relays between 30~\% and 70~\% in a
-path plot.
-This path plot shows the effect of choosing a different fraction of
-relays on the actual required WMTBF value on the $x$ axis and on the
-resulting time until 10~\% of relays have failed on the $y$ axis.
-Two data points adjacent in time are connected by a line, forming a path.
-
-The results indicate a somewhat linear relation between required WMTBF and
-time until failure, which is as expected.
-The time until 10~\% of relays have failed in the default case of having
-50~\% stable relays is somewhere between 12 and 48 hours.
-If the directory authorities assigned the \texttt{Stable} flag to 60~\% or
-even 70~\% of all relays, this time would go down to on average 24 or 12
-hours.
-Reducing the set to only 40~\% or 30\% of relays would increase the time
-until failure to 36 or even 48 hours on average.
-
-\subsubsection*{Next steps}
-
-{\it
-\begin{itemize}
-\item What's the desired stability goal here?
-\item What other requirements (bandwidth) should go into the simulation?
-\end{itemize}
-}
+The first finding that comes to mind is that the observed line is much
+farther left than the simulated 50th percentile line.
+In theory, both lines use the 50th percentile as requirement and should
+therefore have similar results.
+However, since the directory authorities assign the Stable flag to almost
+60~\% of all relays, it's likely that their overall stability is lower
+than the stability of the most stable 50~\% of all relays.
+It's unclear why observed results are even worse than those from the
+simulated 40th percentile.
+It might be that the directory authorities don't just assign the
+Stable flag to too many relays, but also to the wrong relays.
+
+Apart from that, the graph shows the large influence of different WMTBF
+percentiles on relay stability.
+If we lowered the requirement to the 30th WMTBF percentile, thus assigning
+the Stable flag to at least 70~\% of all relays, the 10th percentile of
+time until next failure would be reached after 6 to 24 hours in most
+cases.
+The 40th and 50th percentile requirements move this point to 12 to 36 and
+18 to 54 hours, respectively.
+If we changed the requirement to the 60th WMTBF percentile, this point
+would only be reached after 24 to 60 hours.
+The 70th percentile requirement is not even shown in the graph, because
+this requirement is so high that the fixed 5-day constant applies in most
+cases here, making the dynamic percentile requirement meaningless.
+
+As an intermediate conclusion, we could improve relay stability a lot by
+raising the WMTBF percentile requirement a bit.
+A good next step might be to find out why the directory authorities assign
+the Stable flag to 55 to 60~\% of all relays and not 50~\%.
+Of course, a higher requirement would result in fewer relays with the
+Stable flag.
+But having 40~\% of relays with that flag should still provide for enough
+diversity.
\section{Picking stable entry guards}
+The second flag that we're going to analyze in more detail is the
+Guard flag.
Clients pick a set of entry guards as fixed entry points into the Tor
network.
Optimally, clients should be able to stick with their choice for a few
@@ -147,149 +380,155 @@ While it is not required for all their entry guards to be running all the
time, at least a subset of them should be running, or the client needs to
pick a new set.
-Tor's metric for deciding which relays are stable enough to be entry
-guards is \emph{weighted fractional uptime (WFU)}.
+As discussed above, Tor's primary metric for deciding which relays are
+stable enough to be entry guards is \emph{weighted fractional uptime
+(WFU)}.
WFU measures the fraction of uptime of a relay in the past with older
observations weighted to count less.
The assumption is that a relay that was available most of the time in the
past will also be available most of the time in the future.
-In a first analysis we simulate the effect of varying the requirements for
-becoming an entry guard on the average relay stability in the future.
+In a first analysis we simulate the effect of varying the percentile
+requirements for becoming an entry guard on the relay stability in the
+future.
We measure future stability by using the same WFU metric, but for uptime
in the future.
We similarly weight observations farther in the future less than
observations in the near future.
-We then simulate different pre-defined required WFUs between $90~\%$ and
-$99.9~\%$ and calculate what the mean future WFUs would be.
+The rationale is that a high fractional uptime in the next few days is
+slightly more important than in a month.
+For a given set of relays we measure the 10th percentile of WFU in the
+future as an indication of relay stability.
+The result is that 10~\% of relays will have a lower uptime than this
+value and 90~\% of relays will have a higher uptime.
+
+Figure~\ref{fig:wfu-wfu-sim} shows the 10th percentile of WFU for simulations
+using the 30th, 40th, 50th, and 60th WFU percentile as requirement for
+assigning the Guard flag.
+This graph also shows the future WFU of relays that got their Guard flag
+assigned by the directory authorities.
+Here, the simulation using the default 50th percentile is much closer to
+the flags assigned by the directory authorities than in the case of the
+Stable flag.
+Unsurprisingly, the 30th percentile requirement has the worst stability,
+because it includes up to 70\% of all relays, minus the non-familiar ones
+and those that don't meet the bandwidth requirement.
+Relay stability increases for raising the WFU requirement to the 40th,
+50th, and 60th percentile, but in most cases the outcome is an uptime of
+more than 85~\% or even more than 90~\%.
+Under the assumption that a client needs only one or two working guards at
+a time and can pick a new set of guards easily, these stabilities seem to
+be sufficiently high.
+
+\begin{figure}[t]
+\includegraphics[width=\textwidth]{wfu-wfu-sim.pdf}
+\caption{Impact of changing the WFU percentile requirement for assigning
+the Guard flag on WFU in the future}
+\label{fig:wfu-wfu-sim}
+\end{figure}
+
+\section{Selecting high-bandwidth entry guards}
+
+A second question regarding Guard flag assignments is whether we can raise
+the advertised bandwidth requirement to end up with faster entry guards.
+The fixed set of entry guards determines to a certain extent what overall
+performance the client can expect.
+If a client is unlucky and picks only slow guards, the overall Tor
+performance can be bad, in particular because clients don't drop slow
+guards, but only failing ones.
+
+We introduce a new metric to evaluate how much bandwidth capacity a relay
+will provide in the future: the \emph{weighted bandwidth}.
+This metric is not based on a relay's advertised bandwidth, but on the
+actual written bytes as reported by the relay.
+Again, we're more interested in the bandwidth in the near future, so we
+discount observations 12 hours further in the future by factor 0.95.
+
+Figure~\ref{fig:advbw-wb-sim} shows the effect of changing the advertised
+bandwidth requirement from the 50th percentile to the 40th, 60th, or even
+70th percentile on the 10th percentile of weighted bandwidth.
+Similar to the graphs above, 10~\% of relays have a lower weighted
+bandwidth and 90~\% have a higher weighted bandwidth.
+Here, the observed 50th percentile is almost identical to the simulated
+50th percentile.
+The graph shows that raising the requirement to the 60th percentile of
+advertised bandwidth would shift this percentile line by roughly 10 KiB/s
+to the right.
+The 70th percentile would ensure that 90~\% of the selected
+Guard relays have a weighted bandwidth of at least between 60 and
+170~KiB/s depending on the current network situation.
\begin{figure}[t]
-\includegraphics[width=\textwidth]{wfu-sim.pdf}
-\caption{Impact of different required WFU on the mean empirical future WFU
-and fraction of potential entry guards}
-\label{fig:wfu-sim}
+\includegraphics[width=\textwidth]{advbw-wb-sim.pdf}
+\caption{Impact of changing the advertised bandwidth percentile for
+assigning the Guard flag on bandwidth capacity in the future}
+\label{fig:advbw-wb-sim}
\end{figure}
-Figure~\ref{fig:wfu-sim} shows the analysis results in a path plot similar
-to the one in Section~\ref{sec:mtbf-sim}.
-This path plot shows the effect of varying the WFU requirement, displayed
-as different line colors, on the fraction of relays meeting this
-requirement on the $x$ axis and on the WFU in the future on the $y$ axis.
-Two data points adjacent in time are connected by a line, forming a path.
-
-In this graph we can see that the majority of data points for the default
-required WFU of 98~\% falls in a future WFU range of 94~\% to 96\% with
-the smallest WFU being no less than 89~\%.
-In most cases, the fraction of relays meeting the default WFU requirement
-is between 40~\% and 50~\%.
-
-If the WFU requirement is relaxed to 95~\% or even 90~\%, the WFU in the
-future decreases slightly towards around 94~\% to 95~\% for most cases.
-At first sight it may seem surprising that a past WFU of 90~\% leads to
-a future WFU of 94~\%, but it makes sense, because the past WFU is a
-required minimum whereas the future WFU is a mean value of all relays
-meeting the requirement.
-Another effect of relaxing the required WFU is that the fraction of relays
-meeting the requirement increases from 50~\% to almost 66~\%.
-
-Interestingly, when tightening the requirement to a WFU value of 99~\% or
-even 99.9~\%, the future WFU does not increase significantly, if at all.
-To the contrary, the future WFU of relays meeting the 99.9~\% requirement
-drops to a range of 91~\% to 94~\% for quite a while.
-A likely explanation for this effect is that the fraction of relays
-meeting these high requirements is only 15~\%.
-While these 15~\% of relays may have had a very high uptime in the past,
-failure of only a few of these relays ruin the WFU metric in the future.
-
-A cautious conclusion of this analysis could be that, if the goal is to
-increase the number of \texttt{Guard} relays, reducing the required WFU to
-95~\% or even 90~\% wouldn't impact relay stability by too much.
-Conversely, increasing the required WFU beyond the current value of 98~\%
-doesn't make much sense and might even negatively affect relay stability.
-
-\subsubsection*{Next steps}
-
-{\it
-\begin{itemize}
-\item Tor penalizes relays that change their IP address or port by ending
-the running uptime session and starting a new uptime session. This
-reduces both WFU and MTBF. The simulation doesn't take this into account
-yet. Should it?
-\item Add the bandwidth requirements to the simulation. The current
-simulation doesn't make any assumptions about relay bandwidth when
-assigning \texttt{Guard} flags. Which bandwidth value would we use here?
-\item Add another graph similar to Figure~\ref{fig:wfu-sim}, but replace
-the ``Fraction of relays meeting WFU requirement'' on the \emph{x} axis
-with the ``Fraction of \emph{bandwidth} of relays meeting WFU
-requirement.''
-After all, we're interested in having enough bandwidth capacity for the
-entry guard position, not (only) in having enough distinct relays.
-Which bandwidth value would we use here?
-\item Roger suggests to come up with a better metric than ``WFU since we
-first saw a relay.''
-He says ``it seems wrong to make something that we saw earlier have a
-worse WFU than something we saw later, even if they've had identical
-uptimes in that second period.''
-What would be good candidate metrics?
-\item Ponder finding another metric than WFU for future observations. In
-particular, with the current WFU parameters of $0.95$ and $12$ hours, the
-WFU reaches up to 4 months into the future. It seems useful to weight
-uptime in the near future higher than uptime in the farther future, but
-maybe we should use parameters to limit the interval to $1$ or $2$ months.
-\end{itemize}
-}
-
-\section{Forming stable hidden-service directory sets}
-
-{\it
-In this section we should evaluate the current requirements for getting
-the \texttt{HSDir} flag.
-Also, what happened to the number of relays with the \texttt{HSDir} flag
-in August 2010?
-}
-
-\section{Selecting stable relays for a fallback consensus}
-
-{\it
-Is the concept of a fallback consensus still worth considering?
-If so, we should analyze how to identify those relays that are most likely
-to be around and reachable under the same IP address.
-The result of this analysis could lead to adding a new \texttt{Longterm}
-(or \texttt{Fallback}?) flag as suggested in proposal 146.
-% TODO Correctly cite proposal 146 here. -KL
-Maybe the analysis of bridges on stable IP addresses should come first,
-though.
-}
-
-\section{Distributing bridges with stable IP addresses}
-
-{\it
-A possible outcome of this analysis could be to add a new flag
-\texttt{StableAddress} (similar to the \texttt{Longterm} flag from the
-previous section) to bridge network statuses and to change BridgeDB to
-include at least one bridge with this flag in its results.
-One of the challenges of this analysis will be to connect sanitized bridge
-descriptors from two months with each other.
-The sanitized IP addresses of two bridges in two months do not match,
-because we're using a new secret key as input to the hash function every
-month.
-We might be able to correlate the descriptors of running bridges via their
-descriptor publication times or bridge statistics.
-But if that fails, we'll have to run the analysis with only 1 month of
-data at a time.
-}
+Of course, raising the advertised bandwidth requirement for becoming a
+guard node results in having fewer possible guard nodes.
+Figure~\ref{fig:advbw-frac-relays-sim} shows the effect of raising the
+advertised bandwidth requirement from the 50th to the 60th or 70th
+percentile.
+The 60th percentile requirement would reduce the fraction of relays with
+the Guard flag from 28~\% to around 25~\%, and the 70th percentile even to
+a value below 20~\%.
+There's a clear trade-off here between raising the bandwidth capacity of
+entry guards and having fewer guards to distribute one third of the
+network load to.
+Having fewer than 20~\% of all relays being possible Guard nodes is
+probably not enough and will generate new performance problems.
+
+\begin{figure}[t]
+\includegraphics[width=\textwidth]{advbw-frac-relays-sim.pdf}
+\caption{Influence of changing the advertised bandwidth percentile on the
+fraction of relays getting the Guard flag assigned}
+\label{fig:advbw-frac-relays-sim}
+\end{figure}
\section{Discussion and future work}
-The approach taken in this analysis was to select relays that are most
-stable in a given context based on their history.
-A different angle to obtain higher relay stability might be to identify
-what properties of a relay have a positive or negative impact on its
-stability.
-For example, relays running a given operating system or given Tor software
-version might have a higher stability than others.
-Possible consequences could be to facilitate setting up relays on a given
-operating system or to improve the upgrade process of the Tor software.
+In this report we used a simulator to evaluate Tor's relay stability
+metrics for assigning Stable and Guard flags to relays.
+We introduced three metrics to evaluate how stable or fast a set of relays
+is that got the Stable or Guard flag assigned.
+Our simulator uses the same algorithms to decide whether a relay is stable
+as the directory authorities and can be parameterized to analyze different
+requirements.
+We could further add new algorithms to the simulator and see what subsets
+of Stable and Guard relays that would produce.
+
+Using our simulator we found that the fraction of relays with the Stable
+flag in the current network is higher than it probably should be.
+We also learned that the WFU requirements for assigning the Guard flag are
+quite reasonable and lead to stable guards.
+But we might consider raising the advertised bandwidth requirement a bit
+to have higher-bandwidth guard nodes.
+Medium-term, we should get rid of a requirement that is based on the
+self-reported advertised bandwidth.
+
+Possible next steps are to review the Tor source code for assigning flags
+and compare the internal relay stability data from the directory
+authorities to simulated values.
+It would be interesting to know why the directory authorities assign the
+Stable flag so generously.
+Also, it would be interesting to compare the internal stability data from
+multiple directory authorities to see in how far they agree.
+Another possible next step might be to turn the four requirement
+percentiles (WMTBF, WFU, Weighted Time, and Advertises Bandwidth) into
+consensus parameters to be able to test parameter changes in the real
+network.
+
+We also left the analysis of relay stability for hidden-service
+directories, fallback consensuses, and bridge relays as future work.
+Possible starting points are an earlier analysis of hidden-service
+directory stability \cite{loesing2009thesis}, the Tor proposal
+describing fallback consensuses \cite{proposal146}, and a tech report
+explaining how bridge descriptors are sanitized to make them publicly
+available \cite{loesing2011overview}.
+
+\bibliography{report}
+\bibliographystyle{plain}
\end{document}
diff --git a/task-2911/stability.R b/task-2911/stability.R
new file mode 100644
index 0000000..5b40d67
--- /dev/null
+++ b/task-2911/stability.R
@@ -0,0 +1,301 @@
+library(ggplot2)
+data <- read.csv("stability.csv", stringsAsFactors = FALSE)
+
+d <- data
+d <- aggregate(d[, 2:length(d)], by = list(date = as.Date(d$time)),
+ mean)
+d <- rbind(
+ data.frame(date = d$date, value = d$running,
+ variable = "Running"),
+ data.frame(date = d$date, value = d$stable,
+ variable = "Running + Stable"),
+ data.frame(date = d$date, value = d$guard,
+ variable = "Running + Guard"))
+ggplot(d, aes(x = as.Date(date), y = value, colour = variable)) +
+geom_line(size = 0.7) +
+scale_x_date("", major = "3 months", minor = "1 month",
+ format = "%b %Y") +
+scale_y_continuous("Number \nof relays ",
+ limits = c(0, max(d$value, na.rm = TRUE))) +
+scale_colour_manual(name = "Assigned relay flags\n",
+ values = c("Running" = "black", "Running + Stable" = "grey45",
+ "Running + HSDir" = "grey", "Running + Guard" = "grey70")) +
+opts(axis.title.y = theme_text(size = 12 * 0.8, face = "bold",
+ vjust = 0.5, hjust = 1))
+ggsave(filename = "relayflags.pdf", width = 8, height = 4, dpi = 100)
+
+d <- data
+d <- aggregate(d[, 2:length(d)], by = list(date = as.Date(d$time)),
+ mean)
+d <- rbind(
+ data.frame(x = d$date, y = d$stable / d$running,
+ variable = "Stable (observed)"),
+ data.frame(x = d$date, y = d$stable50 / d$running,
+ variable = "Stable (simulated)"),
+ data.frame(x = d$date, y = d$guard / d$running,
+ variable = "Guard (observed)"),
+ data.frame(x = d$date, y = d$guard50wfu50advbw / d$running,
+ variable = "Guard (simulated)"))
+d[d$x >= '2010-06-26' & d$x <= '2010-06-28', "y"] <- NA
+d[d$x >= '2010-01-25' & d$x <= '2010-01-26', "y"] <- NA
+ggplot(d, aes(x = x, y = y, colour = variable, linetype = variable)) +
+geom_line() +
+scale_y_continuous(name = "Fraction of \nRunning relays ",
+ formatter = "percent", limits = c(0, max(d$y, na.rm = TRUE))) +
+scale_x_date(name = "", major = "3 months", minor = "1 month",
+ format = "%b %Y") +
+scale_colour_manual(name = "Assigned relay flags\n",
+ values = c("Stable (observed)" = "grey50",
+ "Stable (simulated)" = "grey50",
+ "Guard (observed)" = "black",
+ "Guard (simulated)" = "black")) +
+scale_linetype_manual(name = "Assigned relay flags\n",
+ values = c(3, 1, 3, 1)) +
+opts(axis.title.x = theme_text(size = 12 * 0.8, face = "bold",
+ hjust = 0.5),
+ axis.title.y = theme_text(size = 12 * 0.8, face = "bold", vjust = 0.5,
+ hjust = 1))
+ggsave(filename = "default-reqs.pdf", width = 8, height = 4, dpi = 100)
+
+d <- data
+d <- aggregate(d[, 2:length(d)], by = list(date = as.Date(d$time)),
+ mean)
+d <- rbind(
+ data.frame(x = d$date, y = d$stableintersect,
+ variable = "simulated and observed", flag = "Stable"),
+ data.frame(x = d$date, y = d$stableobserved,
+ variable = "only observed", flag = "Stable"),
+ data.frame(x = d$date, y = d$stablesimulated,
+ variable = "only simulated", flag = "Stable"),
+ data.frame(x = d$date, y = d$guardintersect,
+ variable = "simulated and observed", flag = "Guard"),
+ data.frame(x = d$date, y = d$guardobserved,
+ variable = "only observed", flag = "Guard"),
+ data.frame(x = d$date, y = d$guardsimulated,
+ variable = "only simulated", flag = "Guard"),
+ data.frame(x = NA, y = 0, variable = "only simulated", flag = "Stable"),
+ data.frame(x = NA, y = 0, variable = "only simulated", flag = "Guard"))
+ggplot(d, aes(x = x, y = y, linetype = variable)) +
+geom_line() +
+facet_grid(flag ~ ., scale = "free_y") +
+scale_y_continuous(name = "Number \nof relays ") +
+scale_x_date(name = "", major = "3 months", minor = "1 month",
+ format = "%b %Y") +
+scale_linetype_manual(name = "", values = c(4, 3, 1)) +
+opts(axis.title.x = theme_text(size = 12 * 0.8, face = "bold",
+ hjust = 0.5),
+ axis.title.y = theme_text(size = 12 * 0.8, face = "bold", vjust = 0.5,
+ hjust = 1))
+ggsave(filename = "diff-sim-obs.pdf", width = 8, height = 4, dpi = 100)
+
+d <- data
+d_mean <- aggregate(d[, 2:length(d)], by = list(date = as.Date(d$time)),
+ mean)
+d_max <- aggregate(d[, 2:length(d)], by = list(date = as.Date(d$time)),
+ max)
+d_min <- aggregate(d[, 2:length(d)], by = list(date = as.Date(d$time)),
+ min)
+d <- rbind(
+ data.frame(x = d_mean$date, y = d_mean$minwmtbfa50 / (24 * 60 * 60),
+ ymin = d_min$minwmtbfa50 / (24 * 60 * 60),
+ ymax = d_max$minwmtbfa50 / (24 * 60 * 60),
+ var = "Median Weighted Mean Time Between Failure"),
+ data.frame(x = d_mean$date, y = d_mean$minwta / (24 * 60 * 60),
+ ymin = d_min$minwta / (24 * 60 * 60),
+ ymax = d_max$minwta / (24 * 60 * 60),
+ var = "12.5th percentile Weighted Time Known"),
+ data.frame(x = d_mean$date, y = d_mean$minwfua50wfu / 10000,
+ ymin = d_min$minwfua50wfu / 10000,
+ ymax = d_max$minwfua50wfu / 10000,
+ var = "Median Weighted Fractional Uptime"),
+ data.frame(x = d_mean$date, y = d_mean$minadvbwa50advbw / 1024,
+ ymin = d_min$minadvbwa50advbw / 1024,
+ ymax = d_max$minadvbwa50advbw / 1024,
+ var = "Median Advertised Bandwidth"))
+e <- data.frame(
+ yintercept = c(5, 8, 0.98, 250),
+ var = c("Median Weighted Mean Time Between Failure",
+ "12.5th percentile Weighted Time Known",
+ "Median Weighted Fractional Uptime",
+ "Median Advertised Bandwidth"))
+ggplot(d, aes(x = as.Date(x), y = y, ymin = ymin, ymax = ymax)) +
+geom_line(colour = "grey30") +
+geom_ribbon(alpha = 0.3) +
+geom_hline(data = e, aes(yintercept = yintercept), colour = "gray30",
+ linetype = 2) +
+facet_wrap(~ var, scales = "free_y") +
+scale_x_date(name = "", major = "3 months", minor = "1 month",
+ format = "%b %Y") +
+scale_y_continuous(name = "")
+ggsave(filename = "requirements.pdf", width = 8, height = 5, dpi = 100)
+
+d <- data
+d <- d[d$time < '2010-06-26 00:00:00' | d$time > '2010-06-28 23:00:00', ]
+d <- d[d$time < '2010-01-25 00:00:00' | d$time > '2010-01-26 23:00:00', ]
+d <- rbind(
+ data.frame(x = sort(d$perc10tunf30) / (60 * 60),
+ y = 1:length(d$perc10tunf30) / length(d$perc10tunf30),
+ sim = "30th (simulated)"),
+ data.frame(x = sort(d$perc10tunf) / (60 * 60),
+ y = 1:length(d$perc10tunf) / length(d$perc10tunf),
+ sim = "50th (observed)"),
+ data.frame(x = sort(d$perc10tunf40) / (60 * 60),
+ y = 1:length(d$perc10tunf40) / length(d$perc10tunf40),
+ sim = "40th (simulated)"),
+ data.frame(x = sort(d$perc10tunf50) / (60 * 60),
+ y = 1:length(d$perc10tunf50) / length(d$perc10tunf50),
+ sim = "50th (simulated)"),
+ data.frame(x = sort(d$perc10tunf60) / (60 * 60),
+ y = 1:length(d$perc10tunf60) / length(d$perc10tunf60),
+ sim = "60th (simulated)"))
+ggplot(d, aes(x = x, y = y, colour = sim, linetype = sim)) +
+geom_line() +
+scale_x_continuous(name = paste("\n10th percentile of time until next",
+ "failure in hours"),
+ breaks = seq(0, max(d$x, na.rm = TRUE), 24),
+ minor = seq(0, max(d$x, na.rm = TRUE), 6),
+ limits = c(0, max(d$x, na.rm = TRUE))) +
+scale_y_continuous(name = paste("Cumulative fraction \nof",
+ "consensuses \nfrom July to \nDecember 2010 "),
+ formatter = "percent", limits = c(0, 1)) +
+scale_colour_manual(name = paste("WMTBF percentile\nfor",
+ "assigning\nStable flag\n"),
+ values = c("60th (simulated)" = "black",
+ "50th (simulated)" = "grey45", "50th (observed)" = "black",
+ "40th (simulated)" = "grey60", "30th (simulated)" = "grey80")) +
+scale_linetype_manual(name = paste("WMTBF percentile\nfor",
+ "assigning\nStable flag\n"),
+ values = c(1, 3, 1, 1, 1)) +
+opts(plot.title = theme_text(size = 14 * 0.8, face = "bold"),
+ axis.title.x = theme_text(size = 12 * 0.8, face = "bold",
+ hjust = 0.5),
+ axis.title.y = theme_text(size = 12 * 0.8, face = "bold", vjust = 0.5,
+ hjust = 1))
+ggsave(filename = "wmtbf-tunf-sim.pdf", width = 8, height = 4, dpi = 100)
+
+d <- data
+d <- d[d$time < '2010-06-26 00:00:00' | d$time > '2010-06-28 23:00:00', ]
+d <- d[d$time < '2010-01-25 00:00:00' | d$time > '2010-01-26 23:00:00', ]
+d <- rbind(
+ data.frame(x = sort(d$perc10wfu30wfu50advbw) / 10000,
+ y = 1:length(d$perc10wfu30wfu50advbw) /
+ length(d$perc10wfu30wfu50advbw),
+ sim = "30th (simulated)"),
+ data.frame(x = sort(d$perc10wfu40wfu50advbw) / 10000,
+ y = 1:length(d$perc10wfu40wfu50advbw) /
+ length(d$perc10wfu40wfu50advbw),
+ sim = "40th (simulated)"),
+ data.frame(x = sort(d$perc10wfu) / 10000,
+ y = 1:length(d$perc10wfu) / length(d$perc10wfu),
+ sim = "50th (observed)"),
+ data.frame(x = sort(d$perc10wfu50wfu50advbw) / 10000,
+ y = 1:length(d$perc10wfu50wfu50advbw) /
+ length(d$perc10wfu50wfu50advbw),
+ sim = "50th (simulated)"),
+ data.frame(x = sort(d$perc10wfu60wfu50advbw) / 10000,
+ y = 1:length(d$perc10wfu60wfu50advbw) /
+ length(d$perc10wfu60wfu50advbw),
+ sim = "60th (simulated)"))
+ggplot(d, aes(x = x, y = y, colour = sim, linetype = sim)) +
+geom_line() +
+scale_x_continuous(name = "\n10th percentile of WFU in the future",
+ formatter = "percent") +
+scale_y_continuous(name = paste("Cumulative fraction \nof",
+ "consensuses \nfrom July to \nDecember 2010 "),
+ formatter = "percent", limits = c(0, 1)) +
+scale_colour_manual(name = paste("WFU percentile\nfor",
+ "assigning\nGuard flag\n"),
+ values = c("60th (simulated)" = "black",
+ "50th (simulated)" = "grey45", "50th (observed)" = "black",
+ "40th (simulated)" = "grey60", "30th (simulated)" = "grey80")) +
+scale_linetype_manual(name = paste("WFU percentile\nfor",
+ "assigning\nGuard flag\n"),
+ values = c(1, 1, 3, 1, 1)) +
+opts(plot.title = theme_text(size = 14 * 0.8, face = "bold"),
+ axis.title.x = theme_text(size = 12 * 0.8, face = "bold",
+ hjust = 0.5),
+ axis.title.y = theme_text(size = 12 * 0.8, face = "bold", vjust = 0.5,
+ hjust = 1))
+ggsave(filename = "wfu-wfu-sim.pdf", width = 8, height = 4, dpi = 100)
+
+d <- data
+d <- rbind(
+ data.frame(x = sort(d$perc10fwb50wfu40advbw),
+ y = 1:length(d$perc10fwb50wfu40advbw) /
+ length(d$perc10fwb50wfu40advbw),
+ sim = "40th (simulated)"),
+ data.frame(x = sort(d$perc10fwb50wfu50advbw),
+ y = 1:length(d$perc10fwb50wfu50advbw) /
+ length(d$perc10fwb50wfu50advbw),
+ sim = "50th (simulated)"),
+ data.frame(x = sort(d$perc10fwb),
+ y = 1:length(d$perc10fwb) /
+ length(d$perc10fwb),
+ sim = "50th (observed)"),
+ data.frame(x = sort(d$perc10fwb50wfu60advbw),
+ y = 1:length(d$perc10fwb50wfu60advbw) /
+ length(d$perc10fwb50wfu60advbw),
+ sim = "60th (simulated)"),
+ data.frame(x = sort(d$perc10fwb50wfu70advbw),
+ y = 1:length(d$perc10fwb50wfu70advbw) /
+ length(d$perc10fwb50wfu70advbw),
+ sim = "70th (simulated)"))
+ggplot(d, aes(x = x / 1024, y = y, linetype = sim, colour = sim)) +
+geom_line() +
+scale_x_continuous(name = paste("\n10th percentile of weighted bandwidth",
+ "in KiB/s in the future")) +
+scale_y_continuous(name = paste("Cumulative fraction \nof",
+ "consensuses \nfrom July to \nDecember 2010 "),
+ formatter = "percent", limits = c(0, 1)) +
+scale_colour_manual(name = paste("Advertised\nbandwidth\npercentile\nfor",
+ "assigning\nGuard flag\n"),
+ values = c(
+ "40th (simulated)" = "grey80",
+ "50th (observed)" = "black",
+ "50th (simulated)" = "grey60",
+ "60th (simulated)" = "grey45",
+ "70th (simulated)" = "black")) +
+scale_linetype_manual(name = paste("Advertised\nbandwidth\n",
+ "percentile\nfor assigning\nGuard flag\n", sep = ""),
+ values = c(1, 1, 3, 1, 1)) +
+opts(axis.title.x = theme_text(size = 12 * 0.8, face = "bold",
+ hjust = 0.5),
+ axis.title.y = theme_text(size = 12 * 0.8, face = "bold", vjust = 0.5,
+ hjust = 1))
+ggsave(filename = "advbw-wb-sim.pdf", width = 8, height = 4, dpi = 100)
+
+d <- data
+d <- aggregate(d[, 2:length(d)], by = list(date = as.Date(d$time)),
+ mean)
+d <- rbind(
+ data.frame(x = d$date, y = d$guard / d$running,
+ variable = "50th (observed)"),
+ data.frame(x = d$date, y = d$guard50wfu50advbw / d$running,
+ variable = "50th (simulated)"),
+ data.frame(x = d$date, y = d$guard50wfu60advbw / d$running,
+ variable = "60th (simulated)"),
+ data.frame(x = d$date, y = d$guard50wfu70advbw / d$running,
+ variable = "70th (simulated)"))
+ggplot(d, aes(x = x, y = y, colour = variable, linetype = variable)) +
+geom_line() +
+scale_y_continuous(name = "Fraction of \nRunning relays ",
+ formatter = "percent", limits = c(0, max(d$y, na.rm = TRUE))) +
+scale_x_date(name = "", major = "3 months", minor = "1 month",
+ format = "%b %Y") +
+scale_colour_manual(name = paste("Advertised\nbandwidth\npercentile\nfor",
+ "assigning\nGuard flag\n"),
+ values = c(
+ "50th (observed)" = "black",
+ "50th (simulated)" = "grey60",
+ "60th (simulated)" = "grey45",
+ "70th (simulated)" = "black")) +
+scale_linetype_manual(name = paste("Advertised\nbandwidth\npercentile\nfor",
+ "assigning\nGuard flag\n"),
+ values = c(3, 1, 1, 1)) +
+opts(axis.title.x = theme_text(size = 12 * 0.8, face = "bold",
+ hjust = 0.5),
+ axis.title.y = theme_text(size = 12 * 0.8, face = "bold", vjust = 0.5,
+ hjust = 1))
+ggsave(filename = "advbw-frac-relays-sim.pdf", width = 8, height = 4,
+ dpi = 100)
+
diff --git a/task-2911/wfu-sim/SimulateWeightedFractionalUptime.java b/task-2911/wfu-sim/SimulateWeightedFractionalUptime.java
deleted file mode 100644
index d803057..0000000
--- a/task-2911/wfu-sim/SimulateWeightedFractionalUptime.java
+++ /dev/null
@@ -1,318 +0,0 @@
-/**
- * Simulate variation of weighted fractional uptime on Guard relays. In
- * a first step, parse network status consensus in consensuses/ from last
- * to first, calculate future weighted fractional uptimes for all relays,
- * and write them to disk as one file per network status in
- * fwfu/$filename. (Skip this step if there is already a fwfu/
- * directory.) In a second step, parse the network statuse consensus
- * again, but this time from first to last, calculate past weighted
- * fractional uptimes for all relays, form relay subsets based on minimal
- * WFU, look up what the mean future WFU would be for a subset, and write
- * results to wfu-sim.csv to disk. */
-import java.io.*;
-import java.text.*;
-import java.util.*;
-public class SimulateWeightedFractionalUptime {
- public static void main(String[] args) throws Exception {
-
- /* Measure how long this execution takes. */
- long started = System.currentTimeMillis();
-
- /* Decide whether we need to do the reverse run, or if we can use
- * previous results. */
- if (!new File("fwfu").exists()) {
-
- /* Scan existing consensus files and sort them in reverse order. */
- SortedSet<File> allConsensuses =
- new TreeSet<File>(Collections.reverseOrder());
- Stack<File> files = new Stack<File>();
- files.add(new File("consensuses"));
- while (!files.isEmpty()) {
- File file = files.pop();
- if (file.isDirectory()) {
- files.addAll(Arrays.asList(file.listFiles()));
- } else {
- if (file.getName().endsWith("-consensus")) {
- allConsensuses.add(file);
- }
- }
- }
-
- /* For each relay as identified by its base-64 encoded fingerprint,
- * track weighted uptime and total weighted time in a long[2]. */
- SortedMap<String, long[]> knownRelays =
- new TreeMap<String, long[]>();
-
- /* Parse all consensuses in reverse order. */
- SimpleDateFormat formatter = new SimpleDateFormat(
- "yyyy-MM-dd-HH-mm-ss");
- formatter.setTimeZone(TimeZone.getTimeZone("UTC"));
- long nextWeightingInterval = formatter.parse(allConsensuses.first().
- getName().substring(0, "yyyy-MM-dd-HH-mm-ss".length())).
- getTime() / (12L * 60L * 60L * 1000L);
- for (File consensus : allConsensuses) {
-
- /* Every 12 hours, weight both uptime and total time of all known
- * relays with 0.95 (or 19/20 since these are long integers) and
- * remove all with a weighted fractional uptime below 1/10000. */
- long validAfter = formatter.parse(consensus.getName().substring(0,
- "yyyy-MM-dd-HH-mm-ss".length())).getTime();
- long weightingInterval = validAfter / (12L * 60L * 60L * 1000L);
- while (weightingInterval < nextWeightingInterval) {
- Set<String> relaysToRemove = new HashSet<String>();
- for (Map.Entry<String, long[]> e : knownRelays.entrySet()) {
- long[] w = e.getValue();
- w[0] *= 19L;
- w[0] /= 20L;
- w[1] *= 19L;
- w[1] /= 20L;
- if (((10000L * w[0]) / w[1]) < 1L) {
- relaysToRemove.add(e.getKey());
- }
- }
- for (String fingerprint : relaysToRemove) {
- knownRelays.remove(fingerprint);
- }
- nextWeightingInterval -= 1L;
- }
-
- /* Parse all fingerprints of Running relays from the consensus. */
- Set<String> fingerprints = new HashSet<String>();
- BufferedReader br = new BufferedReader(new FileReader(consensus));
- String line, rLine = null;
- boolean reachedEnd = false;
- while ((line = br.readLine()) != null) {
- if (line.startsWith("r ")) {
- rLine = line;
- } else if (line.startsWith("s ") && line.contains(" Running")) {
- String[] parts = rLine.split(" ");
- if (parts.length < 3) {
- System.out.println("Illegal line '" + rLine + "' in "
- + consensus + ". Skipping consensus.");
- continue;
- } else {
- String fingerprint = parts[2];
- if (fingerprint.length() !=
- "AAAAAAAAAAAAAAAAAAAAAAAAAAA".length()) {
- System.out.println("Illegal line '" + rLine + "' in "
- + consensus + ". Skipping consensus.");
- continue;
- }
- fingerprints.add(fingerprint);
- }
- } else if (line.startsWith("directory-signature ")) {
- reachedEnd = true;
- break;
- }
- }
- br.close();
- if (!reachedEnd) {
- System.out.println("Did not reach the consensus end of "
- + consensus + ". Skipping consensus.");
- continue;
- }
-
- /* Increment weighted uptime for all running relays by 3600
- * seconds. */
- /* TODO 3600 seconds is only correct if we're not missing a
- * consensus. We could be more precise here, but it will probably
- * not affect results significantly, if at all. The same applies
- * to the 3600 seconds constants below. */
- for (String fingerprint : fingerprints) {
- if (!knownRelays.containsKey(fingerprint)) {
- knownRelays.put(fingerprint, new long[] { 3600L, 0L });
- } else {
- knownRelays.get(fingerprint)[0] += 3600L;
- }
- }
-
- /* Increment total weighted time for all relays by 3600 seconds. */
- for (long[] w : knownRelays.values()) {
- w[1] += 3600L;
- }
-
- /* Write future WFUs for all known relays to disk. */
- File fwfuFile = new File("fwfu", consensus.getName());
- fwfuFile.getParentFile().mkdirs();
- BufferedWriter bw = new BufferedWriter(new FileWriter(fwfuFile));
- for (Map.Entry<String, long[]> e : knownRelays.entrySet()) {
- bw.write(e.getKey() + " "
- + ((10000L * e.getValue()[0]) / e.getValue()[1]) + "\n");
- }
- bw.close();
- }
- }
-
- /* Run the simulation for the following WFU/10000 values: */
- long[] requiredWFUs = new long[] { 9000, 9100, 9200, 9300, 9400, 9500,
- 9600, 9700, 9750, 9800, 9850, 9900, 9950, 9975, 9990, 9999 };
- BufferedWriter bw = new BufferedWriter(new FileWriter("wfu-sim.csv"));
- bw.write("time");
- for (long requiredWFU : requiredWFUs) {
- bw.write(",wfu" + requiredWFU + ",perc85wfu" + requiredWFU
- + ",perc90wfu" + requiredWFU + ",perc95wfu" + requiredWFU
- + ",guards" + requiredWFU);
- }
- bw.write("\n");
-
- /* Scan existing consensus files and sort them in forward order. */
- SortedSet<File> allConsensuses = new TreeSet<File>();
- Stack<File> files = new Stack<File>();
- files.add(new File("consensuses"));
- while (!files.isEmpty()) {
- File file = files.pop();
- if (file.isDirectory()) {
- files.addAll(Arrays.asList(file.listFiles()));
- } else {
- if (file.getName().endsWith("-consensus")) {
- allConsensuses.add(file);
- }
- }
- }
-
- /* For each relay as identified by its base-64 encoded fingerprint,
- * track weighted uptime and total weighted time in a long[2]. */
- SortedMap<String, long[]> knownRelays = new TreeMap<String, long[]>();
-
- /* Parse all consensuses in forward order. */
- SimpleDateFormat formatter = new SimpleDateFormat(
- "yyyy-MM-dd-HH-mm-ss");
- formatter.setTimeZone(TimeZone.getTimeZone("UTC"));
- SimpleDateFormat isoFormatter = new SimpleDateFormat(
- "yyyy-MM-dd HH:mm:ss");
- isoFormatter.setTimeZone(TimeZone.getTimeZone("UTC"));
- long nextWeightingInterval = formatter.parse(allConsensuses.first().
- getName().substring(0, "yyyy-MM-dd-HH-mm-ss".length())).getTime()
- / (12L * 60L * 60L * 1000L);
- for (File consensus : allConsensuses) {
-
- /* Every 12 hours, weight both uptime and total time of all known
- * relays with 0.95 (or 19/20 since these are long integers) and
- * remove all with a weighted fractional uptime below 1/10000. */
- long validAfter = formatter.parse(consensus.getName().substring(0,
- "yyyy-MM-dd-HH-mm-ss".length())).getTime();
- long weightingInterval = validAfter / (12L * 60L * 60L * 1000L);
- while (weightingInterval > nextWeightingInterval) {
- Set<String> relaysToRemove = new HashSet<String>();
- for (Map.Entry<String, long[]> e : knownRelays.entrySet()) {
- long[] w = e.getValue();
- w[0] *= 19L;
- w[0] /= 20L;
- w[1] *= 19L;
- w[1] /= 20L;
- if (((10000L * w[0]) / w[1]) < 1L) {
- relaysToRemove.add(e.getKey());
- }
- }
- for (String fingerprint : relaysToRemove) {
- knownRelays.remove(fingerprint);
- }
- nextWeightingInterval += 1L;
- }
-
- /* Parse all fingerprints of Running relays from the consensus. */
- Set<String> fingerprints = new HashSet<String>();
- BufferedReader br = new BufferedReader(new FileReader(consensus));
- String line, rLine = null;
- boolean reachedEnd = false;
- while ((line = br.readLine()) != null) {
- if (line.startsWith("r ")) {
- rLine = line;
- } else if (line.startsWith("s ") && line.contains(" Running")) {
- String[] parts = rLine.split(" ");
- if (parts.length < 3) {
- System.out.println("Illegal line '" + rLine + "' in "
- + consensus + ". Skipping consensus.");
- continue;
- } else {
- String fingerprint = parts[2];
- if (fingerprint.length() !=
- "AAAAAAAAAAAAAAAAAAAAAAAAAAA".length()) {
- System.out.println("Illegal line '" + rLine + "' in "
- + consensus + ". Skipping consensus.");
- continue;
- }
- fingerprints.add(fingerprint);
- }
- } else if (line.startsWith("directory-signature ")) {
- reachedEnd = true;
- break;
- }
- }
- br.close();
- if (!reachedEnd) {
- System.out.println("Did not reach the consensus end of "
- + consensus + ". Skipping consensus.");
- continue;
- }
-
- /* Increment weighted uptime for all running relays by 3600
- * seconds. */
- for (String fingerprint : fingerprints) {
- if (!knownRelays.containsKey(fingerprint)) {
- knownRelays.put(fingerprint, new long[] { 3600L, 0L });
- } else {
- knownRelays.get(fingerprint)[0] += 3600L;
- }
- }
-
- /* Increment total weighted time for all relays by 3600 seconds. */
- for (long[] w : knownRelays.values()) {
- w[1] += 3600L;
- }
-
- /* Read previously calculated future WFUs from disk. */
- Map<String, Long> fwfus = new HashMap<String, Long>();
- File fwfuFile = new File("fwfu", consensus.getName());
- if (!fwfuFile.exists()) {
- System.out.println("Could not find file " + fwfuFile
- + ". Exiting!");
- System.exit(1);
- }
- br = new BufferedReader(new FileReader(fwfuFile));
- while ((line = br.readLine()) != null) {
- String[] parts = line.split(" ");
- fwfus.put(parts[0], Long.parseLong(parts[1]));
- }
-
- /* Run the simulation for the relays in the current consensus for
- * various required WFUs. */
- bw.write(isoFormatter.format(validAfter));
- for (long requiredWFU : requiredWFUs) {
- long selectedRelays = 0L,
- totalRelays = (long) fingerprints.size(), totalFwfu = 0L;
- List<Long> fwfuList = new ArrayList<Long>();
- for (String fingerprint : fingerprints) {
- long[] pwfu = knownRelays.get(fingerprint);
- long wfu = (10000L * pwfu[0]) / pwfu[1];
- if (wfu >= requiredWFU) {
- selectedRelays += 1L;
- if (fwfus.containsKey(fingerprint)) {
- long fwfu = fwfus.get(fingerprint);
- totalFwfu += fwfu;
- fwfuList.add(fwfu);
- }
- }
- }
- if (selectedRelays == 0L) {
- bw.write(",NA,NA,NA,NA");
- } else {
- Collections.sort(fwfuList, Collections.reverseOrder());
- long perc85 = fwfuList.get((85 * fwfuList.size()) / 100);
- long perc90 = fwfuList.get((90 * fwfuList.size()) / 100);
- long perc95 = fwfuList.get((95 * fwfuList.size()) / 100);
- bw.write("," + (totalFwfu / selectedRelays) + "," + perc85
- + "," + perc90 + "," + perc95);
- }
- bw.write("," + (10000L * selectedRelays / totalRelays));
- }
- bw.write("\n");
- }
- bw.close();
-
- /* Print how long this execution took and exit. */
- System.out.println("Execution took " + ((System.currentTimeMillis()
- - started) / (60L * 1000L)) + " minutes.");
- }
-}
-
diff --git a/task-2911/wfu-sim/wfu-sim.R b/task-2911/wfu-sim/wfu-sim.R
deleted file mode 100644
index 149ce6d..0000000
--- a/task-2911/wfu-sim/wfu-sim.R
+++ /dev/null
@@ -1,57 +0,0 @@
-library(ggplot2)
-data <- read.csv("wfu-sim.csv", stringsAsFactors = FALSE)
-
-d <- data[data$time >= '2010' & data$time < '2011', ]
-d <- aggregate(d[, 2:length(d)], by = list(date = as.Date(d$time)), mean)
-d <- rbind(
- data.frame(x = d$guards9000, y = d$wfu9000, sim = "90 %"),
- data.frame(x = d$guards9500, y = d$wfu9500, sim = "95 %"),
- data.frame(x = d$guards9800, y = d$wfu9800, sim = "98 % (default)"),
- data.frame(x = d$guards9900, y = d$wfu9900, sim = "99 %"),
- data.frame(x = d$guards9990, y = d$wfu9990, sim = "99.9 %"))
-ggplot(d, aes(x = x / 10000.0, y = y / 10000.0)) +
-geom_path() +
-facet_wrap(~ sim) +
-scale_x_continuous("\nFraction of relays meeting WFU requirement",
- formatter = "percent") +
-scale_y_continuous("Mean WFU in the future\n", formatter = "percent")
-ggsave(filename = "wfu-sim.pdf", width = 8, height = 5, dpi = 100)
-
-## Commented out, because graph is meaningless in b/w.
-#d <- data[data$time >= '2010' & data$time < '2011', ]
-#d <- aggregate(d[, 2:length(d)], by = list(date = as.Date(d$time)), mean)
-#d <- rbind(
-# data.frame(x = d$guards9000, y = d$wfu9000, sim = "90 %"),
-# data.frame(x = d$guards9500, y = d$wfu9500, sim = "95 %"),
-# data.frame(x = d$guards9800, y = d$wfu9800, sim = "98 % (default)"),
-# data.frame(x = d$guards9900, y = d$wfu9900, sim = "99 %"),
-# data.frame(x = d$guards9990, y = d$wfu9990, sim = "99.9 %"))
-#ggplot(d, aes(x = x / 10000.0, y = y / 10000.0, colour = sim)) +
-#geom_path() +
-#scale_x_continuous("\nFraction of relays meeting WFU requirement",
-# formatter = "percent") +#, trans = "reverse") +
-#scale_y_continuous("Mean WFU \nin the future ",
-# formatter = "percent") +
-#scale_colour_hue("Required WFU") +
-#opts(axis.title.x = theme_text(size = 12 * 0.8, face = "bold",
-# hjust = 0.5),
-# axis.title.y = theme_text(size = 12 * 0.8, face = "bold", vjust = 0.5,
-# hjust = 1))
-#ggsave(filename = "wfu-sim.pdf", width = 8, height = 5, dpi = 100)
-
-## Commented out, because the time plot is not as useful as expected.
-#simulations <- paste("wfu", rev(c(9000, 9200, 9400, 9600, 9800)),
-# sep = "")
-#d <- data[data$time >= '2010' & data$time < '2011',
-# c("time", simulations)]
-#d <- aggregate(d[, 2:length(d)], by = list(date = as.Date(d$time)), mean)
-#d <- melt(d, id.vars = 1)
-#ggplot(d, aes(x = date, y = value / 10000.0, colour = variable)) +
-#geom_line() +
-#scale_x_date("", major = "3 months", minor = "1 month",
-# format = "%b %Y") +
-#scale_y_continuous("Empirical future WFU\n", formatter = "percent") +
-#scale_colour_hue("Required past WFU\n", breaks = simulations,
-# labels = paste(as.numeric(substr(simulations, 4, 9)) / 100.0, "%"))
-#ggsave(filename = "wfu-sim-time.pdf", width = 8, height = 5, dpi = 100)
-
