commit 85a545e66a8ba85d512e30b955c28c1b90e915ea
Author: Karsten Loesing <karsten.loesing(a)gmx.net>
Date: Sun Oct 30 07:11:56 2011 +0100
Add bridge stability report draft (#4255).
---
task-4255/.gitignore | 11 +
task-4255/README | 29 ++
task-4255/SimulateBridgeStability.java | 770 ++++++++++++++++++++++++++++++++
task-4255/report.bib | 26 ++
task-4255/report.tex | 414 +++++++++++++++++
task-4255/stability.R | 220 +++++++++
task-4255/stale-bridge-tarballs.csv | 760 +++++++++++++++++++++++++++++++
7 files changed, 2230 insertions(+), 0 deletions(-)
diff --git a/task-4255/.gitignore b/task-4255/.gitignore
new file mode 100644
index 0000000..4251d3d
--- /dev/null
+++ b/task-4255/.gitignore
@@ -0,0 +1,11 @@
+*.pdf
+*.log
+stability.csv
+stable-fingerprints-and-addresses
+*.class
+*.aux
+*.bbl
+*.blg
+bridge-statuses/
+future-stability/
+
diff --git a/task-4255/README b/task-4255/README
new file mode 100644
index 0000000..7ff10c9
--- /dev/null
+++ b/task-4255/README
@@ -0,0 +1,29 @@
+Extract sanitized bridge network statuses (not server descriptors or
+extra-info descriptors) to bridge-statuses/, e.g.
+bridge-statuses/bridge-descriptors-2010-01/statuses/. Leaving server or
+extra-info descriptors in the directory may lead to errors or at least
+delay the evaluation significantly.
+
+Compile the Java class:
+
+ $ javac SimulateBridgeStability.java
+
+Run the Java class:
+
+ $ java SimulateBridgeStability
+
+Before re-running, delete the following files/directories to re-generate
+them:
+
+ - stable-fingerprints-and-addresses
+ - future-stability/
+ - stability.csv
+
+Plot the results:
+
+ $ R --slave -f stability.R
+
+Compile the report:
+
+ $ pdflatex report.tex
+
diff --git a/task-4255/SimulateBridgeStability.java b/task-4255/SimulateBridgeStability.java
new file mode 100644
index 0000000..6deb318
--- /dev/null
+++ b/task-4255/SimulateBridgeStability.java
@@ -0,0 +1,770 @@
+import java.io.*;
+import java.text.*;
+import java.util.*;
+
+/**
+ * Simulate different requirements for stable bridges that BridgeDB can
+ * use to include at least one such stable bridge in its responses to
+ * bridge users.
+ *
+ * The two bridge stability metrics used here are weighted mean time
+ * between address changes (WMTBAC) and weighted fractional uptime (WFU).
+ * Different requirements based on these two metrics are simulated by
+ * comparing the time on same address (TOSA) and weighted fractional
+ * uptime in the future (WFU).
+ */
+public class SimulateBridgeStability {
+
+ /* Bridge history entry for the third step. Once we teach BridgeDB
+ * how to keep track of bridge stability, it's going to keep records
+ * similar to this one. */
+ private static class BridgeHistoryElement {
+ /* Weighted uptime in seconds that is used for WFU calculation. */
+ public long weightedUptime;
+ /* Weighted time in seconds that is used for WFU calculation. */
+ public long weightedTime;
+ /* Weighted run length of previously used addresses or ports in
+ * seconds. */
+ public double weightedRunLength;
+ /* Total run weights of previously used addresses or ports. */
+ public double totalRunWeights;
+ /* Currently known address. */
+ public String address;
+ /* Month string (YYYY-MM) that was used as input to the bridge
+ * descriptor sanitizer. */
+ public String month;
+ /* Currently known port. */
+ public int port;
+ /* Timestamp in milliseconds when this bridge was last seen with a
+ * different address or port. When adding a history entry, this
+ * timestamp is initialized with the publication time of the previous
+ * status. */
+ public long lastSeenWithDifferentAddressAndPort;
+ /* Timestamp in milliseconds when this bridge was last seen with this
+ * address and port. */
+ public long lastSeenWithThisAddressAndPort;
+ }
+
+ /* Run the analysis in three steps:
+ *
+ * In the first step, we parse sanitized bridge network statuses from
+ * first to last to determine stable addresses that have changed by the
+ * sanitizing process only. In the second step, we parse statuses from
+ * last to first to calculate TOSA and future WFU, and write future
+ * stability metrics to disk as one file per network status in
+ * future-stability/$filename. In the third step, we parse the statuses
+ * again from first to last, calculate past stability metrics for all
+ * bridges, select stable bridges, look up future stability of these
+ * bridges, and write results to stability.csv.
+ */
+ public static void main(String[] args) throws Exception {
+
+ /* Measure how long this execution takes. */
+ long started = System.currentTimeMillis();
+
+ /* Prepare timestamp parsing. */
+ SimpleDateFormat isoFormat = new SimpleDateFormat(
+ "yyyy-MM-dd HH:mm:ss");
+ isoFormat.setTimeZone(TimeZone.getTimeZone("UTC"));
+ SimpleDateFormat statusFileNameFormat = new SimpleDateFormat(
+ "yyyyMMdd-HHmmss");
+ statusFileNameFormat.setTimeZone(TimeZone.getTimeZone("UTC"));
+ SimpleDateFormat futureStabilityFileNameFormat = new SimpleDateFormat(
+ "yyyy-MM-dd-HH-mm-ss");
+ futureStabilityFileNameFormat.setTimeZone(TimeZone.getTimeZone(
+ "UTC"));
+
+ /* Define analysis interval. */
+ String analyzeFrom = "2010-07-01 00:00:00",
+ analyzeTo = "2011-06-30 23:00:00";
+ long analyzeFromMillis = isoFormat.parse(analyzeFrom).getTime(),
+ analyzeToMillis = isoFormat.parse(analyzeTo).getTime();
+
+ /* Scan existing status files. */
+ SortedSet<File> allStatuses = new TreeSet<File>();
+ Stack<File> files = new Stack<File>();
+ files.add(new File("bridge-statuses"));
+ while (!files.isEmpty()) {
+ File file = files.pop();
+ if (file.isDirectory()) {
+ files.addAll(Arrays.asList(file.listFiles()));
+ } else {
+ if (file.getName().endsWith(
+ "-4A0CCD2DDC7995083D73F5D667100C8A5831F16D")) {
+ allStatuses.add(file);
+ }
+ }
+ }
+ System.out.println("Scanning " + allStatuses.size() + " bridge "
+ + "network statuses.");
+
+ /* Parse statuses in forward order to detect stable fingerprint/
+ * address combinations to correct some of the IP address changes from
+ * one month to the next. */
+ SortedSet<String> stableFingerprintsAndAddresses =
+ new TreeSet<String>();
+ File stableFingerprintsAndAddressesFile =
+ new File("stable-fingerprints-and-addresses");
+ if (stableFingerprintsAndAddressesFile.exists()) {
+ System.out.println("Reading stable fingerprints and addresses from "
+ + "disk...");
+ BufferedReader br = new BufferedReader(new FileReader(
+ stableFingerprintsAndAddressesFile));
+ String line;
+ while ((line = br.readLine()) != null) {
+ stableFingerprintsAndAddresses.add(line);
+ }
+ br.close();
+ } else {
+ System.out.println("Parsing bridge network statuses and writing "
+ + "stable fingerprints and addresses to disk...");
+ Map<String, Long> firstSeenFingerprintAndAddress =
+ new HashMap<String, Long>();
+ for (File status : allStatuses) {
+ Set<String> fingerprints = new HashSet<String>();
+ BufferedReader br = new BufferedReader(new FileReader(status));
+ String line, rLine = null;
+ while ((line = br.readLine()) != null) {
+ if (line.startsWith("r ")) {
+ String[] parts = line.split(" ");
+ if (parts.length < 8) {
+ System.out.println("Illegal line '" + rLine + "' in "
+ + status + ". Skipping status.");
+ break;
+ }
+ String fingerprint = parts[2];
+ String address = parts[6];
+ String fingerprintAndAddress = fingerprint + " " + address;
+ if (stableFingerprintsAndAddresses.contains(
+ fingerprintAndAddress)) {
+ continue;
+ } else {
+ String date = parts[4];
+ String time = parts[5];
+ long published = isoFormat.parse(date + " " + time).
+ getTime();
+ if (!firstSeenFingerprintAndAddress.containsKey(
+ fingerprintAndAddress)) {
+ firstSeenFingerprintAndAddress.put(fingerprintAndAddress,
+ published);
+ } else if (published - firstSeenFingerprintAndAddress.get(
+ fingerprintAndAddress) > 36L * 60L * 60L * 1000L) {
+ stableFingerprintsAndAddresses.add(
+ fingerprintAndAddress);
+ }
+ }
+ }
+ }
+ br.close();
+ }
+ BufferedWriter bw = new BufferedWriter(new FileWriter(
+ stableFingerprintsAndAddressesFile));
+ for (String stableFingerprintAndAddress :
+ stableFingerprintsAndAddresses) {
+ bw.write(stableFingerprintAndAddress + "\n");
+ }
+ bw.close();
+ }
+ System.out.println("We know about "
+ + stableFingerprintsAndAddresses.size() + " stable fingerprints "
+ + "and addresses.");
+
+ /* Now parse statuses in reverse direction to calculate time until
+ * next address change and weighted fractional uptime for all bridges.
+ * Whenever we find a bridge published in a month for the first time,
+ * we look if we identified the bridge fingerprint and address (either
+ * new or old) as stable before. If we did, ignore this address
+ * change. */
+ File futureStabilityDirectory = new File("future-stability");
+ if (futureStabilityDirectory.exists()) {
+ System.out.println("Not overwriting files in "
+ + futureStabilityDirectory.getAbsolutePath());
+ } else {
+
+ /* Track weighted uptime and total weighted time in a long[2]. */
+ SortedMap<String, long[]> wfuHistory =
+ new TreeMap<String, long[]>();
+
+ /* Track timestamps of next address changes in a long. */
+ SortedMap<String, Long> nacHistory = new TreeMap<String, Long>();
+
+ /* Store the last known r lines by fingerprint to be able to decide
+ * whether a bridge has changed its IP address. */
+ Map<String, String> lastKnownRLines = new HashMap<String, String>();
+
+ /* Parse bridge network statuses in reverse order. */
+ SortedSet<File> allStatusesReverseOrder =
+ new TreeSet<File>(Collections.reverseOrder());
+ allStatusesReverseOrder.addAll(allStatuses);
+ long nextWeightingInterval = -1L, lastStatusPublicationMillis = -1L;
+ for (File status : allStatusesReverseOrder) {
+
+ /* Parse status publication time from file name. */
+ long statusPublicationMillis = statusFileNameFormat.parse(
+ status.getName().substring(0, "yyyyMMdd-HHmmss".length())).
+ getTime();
+
+ /* We're just looking at the first status outside the analysis
+ * interval. Stop parsing here. */
+ if (statusPublicationMillis < analyzeFromMillis) {
+ break;
+ }
+
+ /* Calculate the seconds since the last parsed status. If this is
+ * the first status or we haven't seen a status for more than 60
+ * minutes, assume 60 minutes. */
+ long secondsSinceLastStatusPublication =
+ lastStatusPublicationMillis < 0L ||
+ lastStatusPublicationMillis - statusPublicationMillis
+ > 60L * 60L * 1000L ? 60L * 60L
+ : (lastStatusPublicationMillis - statusPublicationMillis)
+ / 1000L;
+ lastStatusPublicationMillis = statusPublicationMillis;
+
+ /* Before parsing the next bridge network status, see if 12 hours
+ * have passed since we last discounted wfu history values. If
+ * so, discount variables for all known bridges by factor 0.95 (or
+ * 19/20 since these are long integers) and remove those bridges
+ * with a weighted fractional uptime below 1/10000 from the
+ * history. */
+ long weightingInterval = statusPublicationMillis
+ / (12L * 60L * 60L * 1000L);
+ if (nextWeightingInterval < 0L) {
+ nextWeightingInterval = weightingInterval;
+ }
+ while (weightingInterval < nextWeightingInterval) {
+ Set<String> bridgesToRemove = 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) {
+ bridgesToRemove.add(e.getKey());
+ }
+ }
+ for (String fingerprint : bridgesToRemove) {
+ wfuHistory.remove(fingerprint);
+ }
+ nextWeightingInterval -= 1L;
+ }
+
+ /* Increment total weighted time for all bridges by seconds
+ * since the last status was published. */
+ for (long[] w : wfuHistory.values()) {
+ w[1] += secondsSinceLastStatusPublication;
+ }
+
+ /* If the status falls within our analysis interval, write future
+ * WFUs and TOSAs for all running bridges to disk. */
+ BufferedWriter bw = null;
+ if (statusPublicationMillis <= analyzeToMillis) {
+ File futureStabilityFile = new File("future-stability",
+ futureStabilityFileNameFormat.format(
+ statusPublicationMillis));
+ futureStabilityFile.getParentFile().mkdirs();
+ bw = new BufferedWriter(new FileWriter(futureStabilityFile));
+ }
+
+
+ /* Parse r lines of all bridges with the Running flag from the
+ * current bridge network status. */
+ BufferedReader br = new BufferedReader(new FileReader(status));
+ String line, rLine = null;
+ SortedMap<String, String> runningBridges =
+ new TreeMap<String, String>();
+ 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 < 8) {
+ System.out.println("Illegal line '" + rLine + "' in "
+ + status + ". Skipping line.");
+ continue;
+ }
+ String fingerprint = parts[2];
+ runningBridges.put(fingerprint, rLine);
+ }
+ }
+ br.close();
+
+ /* If this status doesn't contain a single bridge with the Running
+ * flag, ignore it. This is a problem with the bridge authority
+ * and doesn't mean we should consider all bridges as down. */
+ if (runningBridges.isEmpty()) {
+ continue;
+ }
+
+ /* Find out if a bridge changed its IP address or port. */
+ for (Map.Entry<String, String> e : runningBridges.entrySet()) {
+ String fingerprint = e.getKey();
+ String brLine = e.getValue();
+ String[] brParts = brLine.split(" ");
+
+ /* Increment weighted uptime by seconds since last status
+ * publication time. */
+ if (!wfuHistory.containsKey(fingerprint)) {
+ wfuHistory.put(fingerprint, new long[] {
+ secondsSinceLastStatusPublication,
+ secondsSinceLastStatusPublication });
+ } else {
+ wfuHistory.get(fingerprint)[0] +=
+ secondsSinceLastStatusPublication;
+ }
+
+ /* Check for address or port change. */
+ String address = brParts[6];
+ String port = brParts[7];
+ boolean sameAddressAndPort = false;
+ if (lastKnownRLines.containsKey(fingerprint)) {
+ String[] lastKnownRLineParts =
+ lastKnownRLines.get(fingerprint).split(" ");
+ String lastAddress = lastKnownRLineParts[6];
+ String lastPort = lastKnownRLineParts[7];
+ if (!port.equals(lastPort)) {
+ /* The port changed. It doesn't matter whether the
+ * address changed or not. */
+ } else if (address.equals(lastAddress)) {
+ /* The bridge's address and port are still the same. */
+ sameAddressAndPort = true;
+ } else {
+ String month = brParts[4].substring(0, "yyyy-MM".length());
+ String lastMonth = lastKnownRLineParts[4].substring(0,
+ "yyyy-MM".length());
+ if (!lastMonth.equals(month) &&
+ stableFingerprintsAndAddresses.contains(
+ fingerprint + " " + address) &&
+ stableFingerprintsAndAddresses.contains(
+ fingerprint + " " + lastAddress)) {
+ /* The last time we saw this bridge was in a different
+ * month. This bridge was seen with both addresses in
+ * intervals of 36 hours or more. Consider this
+ * address change an artifact from the sanitizing
+ * process. */
+ sameAddressAndPort = true;
+ } else {
+ /* Either the month did not change or the address or
+ * port did change. */
+ }
+ }
+ } else {
+ /* We're seeing this bridge for the first time. */
+ }
+ if (!sameAddressAndPort) {
+ nacHistory.put(fingerprint, statusPublicationMillis);
+ }
+ lastKnownRLines.put(fingerprint, brLine);
+
+ /* Write WFU and TOSA to disk. */
+ if (bw != null) {
+ long[] wfu = wfuHistory.get(fingerprint);
+ long tosa = (nacHistory.get(fingerprint)
+ - statusPublicationMillis) / 1000L;
+ bw.write(fingerprint + " " + tosa + " "
+ + ((10000L * wfu[0]) / wfu[1]) + " " + "\n");
+ }
+ }
+ br.close();
+ if (bw != null) {
+ bw.close();
+ }
+ }
+ }
+
+ /* Finally, parse statuses in forward order to calculate weighted mean
+ * time between address change (WMTBAC) and weighted fractional uptime
+ * (WFU) and simulate how stable bridges meeting given requirements
+ * are. */
+ File stabilityFile = new File("stability.csv");
+ if (stabilityFile.exists()) {
+ System.out.println("Not overwriting output file "
+ + stabilityFile.getAbsolutePath());
+ } else {
+
+ /* Run the simulation for the following WFU and WMTBAC
+ * percentiles: */
+ List<Integer> wfuPercentiles = new ArrayList<Integer>();
+ for (int l : new int[] { 0, 30, 40, 50, 60, 70 }) {
+ wfuPercentiles.add(l);
+ }
+ List<Integer> wmtbacPercentiles = new ArrayList<Integer>();
+ for (int l : new int[] { 0, 30, 40, 50, 60, 70 }) {
+ wmtbacPercentiles.add(l);
+ }
+
+ /* Add column headers to output file. */
+ SortedSet<String> columns = new TreeSet<String>();
+ columns.add("running");
+ columns.add("minwta");
+ columns.add("minwtb");
+ for (int wfuPercentile : wfuPercentiles) {
+ columns.add("minwfua" + wfuPercentile + "wfu");
+ columns.add("minwfub" + wfuPercentile + "wfu");
+ for (int wmtbacPercentile : wmtbacPercentiles) {
+ String simulation = wfuPercentile + "wfu" + wmtbacPercentile
+ + "wmtbac";
+ columns.add("stablebridge" + simulation);
+ columns.add("perc15wfu" + simulation);
+ columns.add("perc10wfu" + simulation);
+ columns.add("perc5wfu" + simulation);
+ columns.add("perc15tosa" + simulation);
+ columns.add("perc10tosa" + simulation);
+ columns.add("perc5tosa" + simulation);
+ }
+ }
+ for (int wmtbacPercentile : wmtbacPercentiles) {
+ columns.add("minwmtbaca" + wmtbacPercentile + "wmtbac");
+ columns.add("minwmtbacb" + wmtbacPercentile + "wmtbac");
+ }
+ BufferedWriter bw = new BufferedWriter(new FileWriter(
+ stabilityFile));
+ bw.write("time");
+ for (String column : columns) {
+ bw.write("," + column);
+ }
+ bw.write("\n");
+
+ SortedMap<String, BridgeHistoryElement> history =
+ new TreeMap<String, BridgeHistoryElement>();
+
+ /* Parse previously exported network status entries again, but this
+ * time in forward order. */
+ long nextWeightingInterval = -1L, lastStatusPublicationMillis = -1L;
+ for (File status : allStatuses) {
+
+ /* Parse status publication time from file name. */
+ long statusPublicationMillis = statusFileNameFormat.parse(
+ status.getName().substring(0, "yyyyMMdd-HHmmss".length())).
+ getTime();
+
+ /* Calculate the seconds since the last parsed status. If this is
+ * the first status or we haven't seen a status for more than 60
+ * minutes, assume 60 minutes. */
+ long secondsSinceLastStatusPublication =
+ lastStatusPublicationMillis < 0L ||
+ statusPublicationMillis - lastStatusPublicationMillis
+ > 60L * 60L * 1000L ? 60L * 60L
+ : (statusPublicationMillis - lastStatusPublicationMillis)
+ / 1000L;
+
+ /* Before parsing the next bridge network status, see if 12 hours
+ * have passed since we last discounted wfu and wmtbac history
+ * values. If so, discount variables for all known bridges by
+ * factor 0.95 (or 19/20 since these are long integers) and remove
+ * those bridges with a weighted fractional uptime below 1/10000
+ * from the history. Also, discount weighted run length and total
+ * run weights for all known relays by factor 0.95. */
+ long weightingInterval = statusPublicationMillis
+ / (12L * 60L * 60L * 1000L);
+ if (nextWeightingInterval < 0L) {
+ nextWeightingInterval = weightingInterval;
+ }
+ while (weightingInterval > nextWeightingInterval) {
+ Set<String> bridgesToRemove = new HashSet<String>();
+ for (Map.Entry<String, BridgeHistoryElement> e :
+ history.entrySet()) {
+ BridgeHistoryElement historyElement = e.getValue();
+ historyElement.weightedUptime =
+ (historyElement.weightedUptime * 19L) / 20L;
+ historyElement.weightedTime =
+ (historyElement.weightedTime * 19L) / 20L;
+ if (((10000L * historyElement.weightedUptime)
+ / historyElement.weightedTime) < 1L) {
+ String fingerprint = e.getKey();
+ bridgesToRemove.add(fingerprint);
+ }
+ historyElement.weightedRunLength *= 0.95;
+ historyElement.totalRunWeights *= 0.95;
+ }
+ for (String fingerprint : bridgesToRemove) {
+ history.remove(fingerprint);
+ }
+ nextWeightingInterval += 1L;
+ }
+
+ /* Parse r lines of all bridges with the Running flag from the
+ * current bridge network status. */
+ BufferedReader br = new BufferedReader(new FileReader(status));
+ String line, rLine = null;
+ SortedMap<String, String> runningBridges =
+ new TreeMap<String, String>();
+ 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 < 8) {
+ System.out.println("Illegal line '" + rLine + "' in "
+ + status + ". Skipping line.");
+ continue;
+ }
+ String fingerprint = parts[2];
+ runningBridges.put(fingerprint, rLine);
+ }
+ }
+ br.close();
+
+ /* If this status doesn't contain a single bridge with the Running
+ * flag, ignore it. This is a problem with the bridge authority
+ * and doesn't mean we should consider all bridges as down. */
+ if (runningBridges.isEmpty()) {
+ continue;
+ }
+
+ /* Add new bridges to history or update history if it already
+ * contains a bridge. */
+ for (Map.Entry<String, String> e : runningBridges.entrySet()) {
+ String fingerprint = e.getKey();
+ String brLine = e.getValue();
+ String[] brParts = brLine.split(" ");
+ String address = brParts[6];
+ int port = Integer.parseInt(brParts[7]);
+ String month = brParts[4].substring(0, "yyyy-MM".length());
+ BridgeHistoryElement bhe = null;
+ if (!history.containsKey(fingerprint)) {
+
+ /* Add new bridge to history. */
+ bhe = new BridgeHistoryElement();
+ bhe.lastSeenWithDifferentAddressAndPort =
+ lastStatusPublicationMillis;
+ history.put(fingerprint, bhe);
+ } else {
+
+ /* Update bridge in history. */
+ bhe = history.get(fingerprint);
+
+ /* If the port changed, ... */
+ if (port != bhe.port ||
+
+ /* ... or the address changed and ... */
+ (!address.equals(bhe.address) &&
+
+ /* ... either the month is the same ... */
+ (month.equals(bhe.month) ||
+
+ /* ... or this address is not stable ... */
+ !stableFingerprintsAndAddresses.contains(
+ fingerprint + " " + address) ||
+
+ /* ... or the last address is not stable, ... */
+ !stableFingerprintsAndAddresses.contains(
+ fingerprint + " " + bhe.address)))) {
+
+ /* ... assume that the bridge changed its address or
+ * port. */
+ bhe.weightedRunLength += (double)
+ ((bhe.lastSeenWithThisAddressAndPort -
+ bhe.lastSeenWithDifferentAddressAndPort) / 1000L);
+ bhe.totalRunWeights += 1.0;
+ bhe.lastSeenWithDifferentAddressAndPort =
+ bhe.lastSeenWithThisAddressAndPort;
+ }
+ }
+
+ /* Regardless of whether the bridge is new, kept or changed
+ * its address and port, raise its WFU times and note its
+ * current address, month, and port, and that we saw it using
+ * them. */
+ bhe.weightedUptime += secondsSinceLastStatusPublication;
+ bhe.weightedTime += secondsSinceLastStatusPublication;
+ bhe.lastSeenWithThisAddressAndPort = statusPublicationMillis;
+ bhe.address = address;
+ bhe.month = month;
+ bhe.port = port;
+ }
+
+ /* Update weighted times (not uptimes) of non-running bridges. */
+ for (Map.Entry<String, BridgeHistoryElement> e :
+ history.entrySet()) {
+ String fingerprint = e.getKey();
+ if (!runningBridges.containsKey(fingerprint)) {
+ BridgeHistoryElement bhe = e.getValue();
+ bhe.weightedTime += secondsSinceLastStatusPublication;
+ }
+ }
+
+ /* Prepare writing results. */
+ Map<String, String> results = new HashMap<String, String>();
+ results.put("running", "" + runningBridges.size());
+
+ /* If we reached the analysis interval, read previously calculated
+ * future WFUs and TOSAs from disk and run the simulations. */
+ Map<String, Long> fwfus = new HashMap<String, Long>(),
+ tosas = new HashMap<String, Long>();
+ File futureStabilityFile = new File("future-stability",
+ futureStabilityFileNameFormat.format(
+ statusPublicationMillis));
+ if (statusPublicationMillis < analyzeFromMillis ||
+ statusPublicationMillis > analyzeToMillis) {
+ /* Outside of our analysis interval. Skip simulation. */
+ } else if (!futureStabilityFile.exists()) {
+ System.out.println("Could not find file "
+ + futureStabilityFile + ". Skipping simulation!");
+ } else {
+ BufferedReader fsBr = new BufferedReader(new FileReader(
+ futureStabilityFile));
+ String fsLine;
+ while ((fsLine = fsBr.readLine()) != null) {
+ String[] fsParts = fsLine.split(" ");
+ tosas.put(fsParts[0], Long.parseLong(fsParts[1]));
+ fwfus.put(fsParts[0], Long.parseLong(fsParts[2]));
+ }
+ fsBr.close();
+
+ /* Prepare calculating thresholds for selecting stable bridges
+ * in simulations. */
+ List<Long> totalWeightedTimes = new ArrayList<Long>();
+ for (String fingerprint : runningBridges.keySet()) {
+ totalWeightedTimes.add(history.get(fingerprint).weightedTime);
+ }
+ Collections.sort(totalWeightedTimes);
+ long minimumTotalWeightedTime = totalWeightedTimes.get(
+ totalWeightedTimes.size() / 8);
+ results.put("minwta", String.valueOf(minimumTotalWeightedTime));
+ if (minimumTotalWeightedTime > 8L * 24L * 60L * 60L) {
+ minimumTotalWeightedTime = 8L * 24L * 60L * 60L;
+ }
+ results.put("minwtb", String.valueOf(minimumTotalWeightedTime));
+ List<Long> weightedFractionalUptimesFamiliar =
+ new ArrayList<Long>();
+ for (String fingerprint : runningBridges.keySet()) {
+ BridgeHistoryElement bhe = history.get(fingerprint);
+ if (bhe.weightedTime >= minimumTotalWeightedTime) {
+ long weightedFractionalUptime =
+ (10000L * bhe.weightedUptime) / bhe.weightedTime;
+ weightedFractionalUptimesFamiliar.add(
+ weightedFractionalUptime);
+ }
+ }
+ Collections.sort(weightedFractionalUptimesFamiliar);
+ List<Long> wmtbacs = new ArrayList<Long>();
+ for (String fingerprint : runningBridges.keySet()) {
+ BridgeHistoryElement bhe = history.get(fingerprint);
+ double totalRunLength = bhe.weightedRunLength + (double)
+ ((bhe.lastSeenWithThisAddressAndPort -
+ bhe.lastSeenWithDifferentAddressAndPort) / 1000L);
+ double totalWeights = bhe.totalRunWeights + 1.0;
+ long wmtbac = totalWeights < 0.0001 ? 0L
+ : (long) (totalRunLength / totalWeights);
+ wmtbacs.add(wmtbac);
+ }
+ Collections.sort(wmtbacs);
+
+ /* Run simulation for the bridges in the current status for
+ * various WFU and WMTBAC percentiles. */
+ for (int wmtbacPercentile : wmtbacPercentiles) {
+ for (int wfuPercentile : wfuPercentiles) {
+ String simulation = wfuPercentile + "wfu" + wmtbacPercentile
+ + "wmtbac";
+ long minimumWeightedMeanTimeBetweenAddressChange =
+ wmtbacs.get((wmtbacPercentile * wmtbacs.size()) / 100);
+ results.put("minwmtbaca" + wmtbacPercentile + "wmtbac",
+ String.valueOf(
+ minimumWeightedMeanTimeBetweenAddressChange));
+ if (minimumWeightedMeanTimeBetweenAddressChange >
+ 30L * 24L * 60L * 60L) {
+ minimumWeightedMeanTimeBetweenAddressChange =
+ 30L * 24L * 60L * 60L;
+ }
+ results.put("minwmtbacb" + wmtbacPercentile + "wmtbac",
+ String.valueOf(
+ minimumWeightedMeanTimeBetweenAddressChange));
+ long minimumWeightedFractionalUptime =
+ weightedFractionalUptimesFamiliar.get((wfuPercentile
+ * weightedFractionalUptimesFamiliar.size()) / 100);
+ results.put("minwfua" + wfuPercentile + "wfu",
+ String.valueOf(minimumWeightedFractionalUptime));
+ if (minimumWeightedFractionalUptime > 9800) {
+ minimumWeightedFractionalUptime = 9800;
+ }
+ results.put("minwfub" + wfuPercentile + "wfu",
+ String.valueOf(minimumWeightedFractionalUptime));
+ List<Long> fwfuList = new ArrayList<Long>(),
+ tosaList = new ArrayList<Long>();
+ Set<String> selectedBridges = new HashSet<String>();
+ for (String fingerprint : runningBridges.keySet()) {
+ BridgeHistoryElement bhe = history.get(fingerprint);
+ double totalRunLength = bhe.weightedRunLength + (double)
+ ((bhe.lastSeenWithThisAddressAndPort -
+ bhe.lastSeenWithDifferentAddressAndPort) / 1000L);
+ double totalWeights = bhe.totalRunWeights + 1.0;
+ long wmtbac = totalWeights < 0.0001 ? 0L
+ : (long) (totalRunLength / totalWeights);
+ if (wmtbac < minimumWeightedMeanTimeBetweenAddressChange) {
+ continue;
+ }
+ if (wfuPercentile > 0 &&
+ bhe.weightedTime < minimumTotalWeightedTime) {
+ continue;
+ }
+ long weightedFractionalUptime =
+ (10000L * bhe.weightedUptime) / bhe.weightedTime;
+ if (weightedFractionalUptime <
+ minimumWeightedFractionalUptime) {
+ continue;
+ }
+ long fwfu = fwfus.get(fingerprint);
+ fwfuList.add(fwfu);
+ long tosa = tosas.get(fingerprint);
+ tosaList.add(tosa);
+ selectedBridges.add(fingerprint);
+ }
+ /* Calculate percentiles of future WFU and of TOSA as the
+ * simulation results. */
+ results.put("stablebridge" + simulation,
+ String.valueOf(selectedBridges.size()));
+ if (tosaList.size() > 0L) {
+ Collections.sort(tosaList);
+ results.put("perc15tosa" + simulation,
+ "" + tosaList.get((15 * tosaList.size()) / 100));
+ results.put("perc10tosa" + simulation,
+ "" + tosaList.get((10 * tosaList.size()) / 100));
+ results.put("perc5tosa" + simulation,
+ "" + tosaList.get((5 * tosaList.size()) / 100));
+ }
+ if (fwfuList.size() > 0) {
+ Collections.sort(fwfuList);
+ 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));
+ }
+ }
+ }
+ }
+
+ /* Write results, regardless of whether we ran simulations or
+ * not. */
+ SortedSet<String> missingColumns = new TreeSet<String>();
+ for (String resultColumn : results.keySet()) {
+ if (!columns.contains(resultColumn)) {
+ missingColumns.add(resultColumn);
+ }
+ }
+ if (!missingColumns.isEmpty()) {
+ System.out.println("We are missing the following columns:");
+ for (String missingColumn : missingColumns) {
+ System.out.print(" " + missingColumn);
+ }
+ System.out.println(". Ignoring.");
+ }
+ bw.write(isoFormat.format(statusPublicationMillis));
+ for (String column : columns) {
+ if (results.containsKey(column)) {
+ bw.write("," + results.get(column));
+ } else {
+ bw.write(",NA");
+ }
+ }
+ bw.write("\n");
+ lastStatusPublicationMillis = statusPublicationMillis;
+ }
+ bw.close();
+ }
+ }
+}
+
diff --git a/task-4255/report.bib b/task-4255/report.bib
new file mode 100644
index 0000000..427e27c
--- /dev/null
+++ b/task-4255/report.bib
@@ -0,0 +1,26 @@
+@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}},
+}
+
+@techreport{loesing2011analysis,
+ title = {An Analysis of {Tor} Relay Stability},
+ author = {Karsten Loesing},
+ institution = {The Tor Project},
+ year = {2011},
+ month = {June},
+ type = {Technical Report},
+ note = {\url{https://metrics.torproject.org/papers/relay-stability-2011-06-30.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-4255/report.tex b/task-4255/report.tex
new file mode 100644
index 0000000..0dfd437
--- /dev/null
+++ b/task-4255/report.tex
@@ -0,0 +1,414 @@
+\documentclass{article}
+\usepackage{url}
+\usepackage[pdftex]{graphicx}
+\usepackage{graphics}
+\usepackage{color}
+\begin{document}
+\title{An Analysis of Tor Bridge Stability\\
+{\large --- Making BridgeDB give out at least one stable bridge per
+user ---}}
+\author{Karsten Loesing\\{\tt karsten(a)torproject.org}}
+
+\maketitle
+
+\section{Introducing the instable bridges problem}
+
+As of October 2011, the Tor network consists of a few hundred thousand
+clients, 2\,400 public relays, and about 600 non-public bridge relays.
+Bridge relays (in the following: bridges) are entry points which are not
+publicly listed to prevent censors from blocking access to the Tor
+network.
+Censored users request a small number of typically three bridge addresses
+from the BridgeDB service via email or http and then connect to the Tor
+network only via these bridges.
+If all bridges that a user knows about suddenly stop working, the user
+needs to request a new set of bridge addresses from BridgeDB.
+However, BridgeDB memorizes the user's email or IP address and only gives
+out new bridges every 24 hours to slow down enumeration attempts.
+The result is that a user who is unlucky enough to receive only unreliable
+bridges from BridgeDB won't be able to connect to the Tor network for up
+to 24 hours before requesting a new set of bridges.
+
+In this report we propose that BridgeDB keeps bridge stability records,
+similar to how the directory authorities keep relay stability records, and
+includes at least one stable bridge in its responses to users.
+In fact, BridgeDB currently attempts to do this by including at least one
+bridge with the Stable flag assigned by the bridge authority in its
+results.
+This approach is broken for two reasons:
+The first reason is that the algorithm that the bridge authority uses to
+assign the Stable flag is broken to the extent that almost every bridge
+has the Stable flag assigned.
+The second reason is that the Stable flag was designed for clients to
+select relays for long-running streams, not for BridgeDB to select
+reliable entry points into the Tor network.
+A better metric for stable bridges would be based on bridge uptime and on
+the frequency of IP address changes.
+We propose such a metric and evaluate its effectiveness for selecting
+stable bridges based on archived bridge directories.
+
+\section{Defining a new bridge stability metric}
+\label{sec:defining}
+
+The directory authorities implement a few relay stability metrics to
+decide which of the relays to assign the Guard and Stable
+flag~\cite{dirspec, loesing2011analysis}.
+The requirements for stable bridges that we propose here are similar to
+the entry guard requirements.
+That is, stable bridges should have a higher fractional uptime than
+non-stable ones.
+Further, a stable bridge should be available under the same IP address and
+TCP port.
+Otherwise, bridge users who only know a bridge address won't be able to
+connect to the bridge once it changes its address or port.
+We propose the following requirements for a bridge to be considered
+stable in the style of the Guard and Stable flag definition:
+
+\label{def:bridgestability}
+\begin{quote}
+A bridge is considered stable if its \emph{Weighted Mean Time Between
+Address Change} is at least the median for known active bridges or at
+least 30~days, if it is `familiar', and if its \emph{Weighted Fractional
+Uptime} is at least the median for `familiar' active bridges or at least
+98~\%.
+A bridge is `familiar' if 1/8 of all active bridges have appeared more
+recently than it, or if it has been around for a \emph{Weighted Time} of
+8~days.
+\end{quote}
+
+This bridge stability definition contains three main requirements:
+
+\begin{itemize}
+\item The \emph{Weighted Mean Time Between Address Change (WMTBAC)}
+metric is used to track the time that a bridge typically uses the same IP
+address and TCP port.
+The (unweighted) MTBAC measures the average time between last using
+address and port $a_0$ to last using address and port $a_1$.
+This metric is weighted to put more emphasis on recent events than on past
+events.
+Therefore, past address sessions are discounted by factor $0.95$ every
+12~hours.
+The current session is not discounted, so that a WMTBAC value of 30 days
+can be reached after 30 days at the earliest.
+\item The \emph{Weighted Fractional Uptime (WFU)} metric measures the
+fraction of bridge uptime in the past.
+Similar to WMTBAC, WFU values are discounted by factor $0.95$ every
+12~hours, but in this case including the current uptime session.
+\item The \emph{Weighted Time (WT)} metric is used to calculate a bridge's
+WFU and to decide whether a bridge is around long enough to be considered
+`familiar.'
+WT is discounted similar to WMTBAC and WFU, so that a WT of 8 days can be
+reached after around 16 days at the earliest.
+\end{itemize}
+
+All three requirements consist of a dynamic part that depends on the
+stability of other bridges (e.g., ``A bridge is familiar if 1/8 of all
+active bridges have appeared more recently than it, \ldots'') and a static
+part that is independent of other bridges (e.g., ``\ldots or if it has
+been around for a Weighted Time of 8 days.'').
+The dynamic parts ensure that a certain fraction of bridges is considered
+stable even in a rather instable network.
+The static parts ensures that rather stable bridges are not excluded even
+when most other bridges in the network are stable.
+
+\section{Extending BridgeDB to track bridge stability}
+
+There are at least two code bases that could be extended to track bridge
+stability and include at least one stable bridge in BridgeDB results: the
+bridge authority and BridgeDB.
+The decision for extending either code base affects the available data
+for tracking bridge stability and is therefore discussed here.
+
+The bridge authority maintains a list of all active bridges.
+Bridges register at the bridge authority when joining the network, and the
+bridge authority periodically performs reachability tests to confirm that
+a bridge is still active.
+The bridge authority takes snapshots of the list of active bridges every
+30~minutes and copies these snapshots to BridgeDB.
+BridgeDB parses these half-hourly snapshots and gives out bridges to users
+based on the most recently known snapshot.
+
+The bridge stability history can be implemented either in the bridge
+authority code or in BridgeDB.
+On the one hand, an implementation in BridgeDB has the disadvantage that
+bridge reachability data has a resolution of 30 minutes whereas the bridge
+authority would learn about bridges joining or leaving the network
+immediately.
+On the other hand, the bridge stability information is not used by
+anything in the Tor software, but only by BridgeDB.
+Implementing this feature in BridgeDB makes more sense from a software
+architecture point of view.
+In the following we assume that BridgeDB will track bridge stability based
+on half-hourly snapshots of active bridge lists, the bridge network
+statuses.
+
+\section{Simulating bridge stability using archived data}
+
+We can analyze how BridgeDB would track bridge stability and give out
+stable bridges by using archived bridge descriptors.
+These archives contain the same descriptors that BridgeDB uses, but they
+are public and don't contain any IP addresses or sensitive pieces of
+information.
+In Section~\ref{sec:missingdata} we look at the problem of missing data
+due to either the bridge authority or BridgeDB failing and at the effect
+on tracking bridge stability.
+We then touch the topic of how bridge descriptors are sanitized and how we
+can glue them back together for our analysis in
+Section~\ref{sec:sanitizing}.
+Next, we examine typical bridge stability values as requirements for
+considering a bridge as stable in Section~\ref{sec:requirements}.
+In Section~\ref{sec:fractions} we estimate what fraction of bridges would
+be considered as stable depending on the chosen stability requirements.
+Finally, in Section~\ref{sec:selectedstability} we evaluate how effective
+different requirement combinations are for selecting stable bridges.
+Result metrics are how soon selected bridges change their address or what
+fractional uptime selected bridges have in the future.
+
+\subsection{Handling missing bridge status data}
+\label{sec:missingdata}
+
+The bridge status data that we use in this analysis and that would also be
+used by BridgeDB to track bridge stability is generated by the bridge
+authority and copied over to BridgeDB every 30~minutes.
+Figure~\ref{fig:runningbridge} shows the number of running bridges
+contained in these snapshots from July 2010 to June 2011.
+
+\begin{figure}[t]
+\includegraphics[width=\textwidth]{runningbridge.pdf}
+\caption{Median number of running bridges as reported by the bridge
+authority}
+\label{fig:runningbridge}
+\end{figure}
+
+For most of the time the number of bridges is relatively stable.
+But there are at least two irregularities, one in July 2010 and another
+one in February 2011, resulting from problems with the bridge authority or
+the data transfer to the BridgeDB host.
+Figure~\ref{fig:runningbridge-detail} shows these two intervals in more
+detail.
+
+\begin{figure}[t]
+\includegraphics[width=\textwidth]{runningbridge-detail.pdf}
+\caption{Number of Running bridges during phases when either the bridge
+authority or the BridgeDB host were broken}
+\label{fig:runningbridge-detail}
+\end{figure}
+
+The missing data from July 14 to 27, 2010 comes from BridgeDB host not
+accepting new descriptors from the bridge authority because of an
+operating system upgrade of the BridgeDB host.
+During this time, the bridge authority continued to work, but BridgeDB was
+unable to learn about new bridge descriptors from it.
+
+During the time from January 31 to February 16, 2011, the \verb+tor+
+process running the bridge authority silently died, but the script to copy
+descriptors to BridgeDB kept running.
+In this case, BridgeDB received fresh tarballs containing stale
+descriptors with a constant number of 687 relays, visualized in light
+gray.
+These stale descriptors have been excluded from the sanitized descriptors
+and the subsequent analysis.
+The bridge authority was restarted on February 16, 2011, resulting in the
+number of running bridges slowly stabilizing throughout the day.
+
+Both this analysis and a later implementation in BridgeDB need to take
+extended phases of missing or stale data into account.
+
+\subsection{Detecting address changes in sanitized descriptors}
+\label{sec:sanitizing}
+
+The bridge descriptor archives that we use in this analysis have been
+sanitized to remove all addresses and otherwise sensitive
+parts~\cite{loesing2011overview}.
+Part of this sanitizing process is that bridge IP addresses are replaced
+with keyed hashes using a fresh key every month.
+More precisely, every bridge IP address is replaced with the private IP
+address \verb+10.x.x.x+ with \verb+x.x.x+ being the 3 most significant
+bytes of \verb+SHA-256(IP address | bridge identity | secret)+.
+
+A side-effect of this sanitizing step is that a bridge's sanitized IP
+address changes at least once per month, even if the bridge's real IP
+address stays the same.
+We need to detect these artificial address changes and distinguish them
+from real IP address changes.
+
+In this analysis we use a simple heuristic to distinguish between real IP
+address changes and artifacts from the sanitizing process:
+Whenever we find that a bridge has changed its IP address from one month
+to the next, we look up how long both IP addresses were in use in either
+month.
+If both addresses were contained in bridge descriptors that were published
+at least 36~hours apart, we consider them stable IP addresses and
+attribute the apparent IP address change to the sanitizing process.
+Otherwise, we assume the bridge has really changed its IP address.
+Obviously, this simple heuristic might lead us to false conclusions in
+some cases.
+But it helps us handle cases when bridges rarely or never change their IP
+address which would otherwise suffer from monthly address changes in this
+analysis.
+
+\subsection{Examining typical stability metric values}
+\label{sec:requirements}
+
+The definition of bridge stability on page~\pageref{sec:defining} contains
+three different metrics, each of which having a dynamic and a static part.
+The dynamic parts compares the value of a bridge's stability metric to the
+whole set of running bridges.
+Only those bridges are considered as stable that exceed the median value
+(or the 12.5th percentile) of all running bridges.
+The static requirement parts are fixed values for all stability metrics
+that don't rely on the stability of other bridges.
+
+Figure~\ref{fig:requirements} visualizes the dynamic (solid lines) and
+static parts (dashed lines) of all three requirements.
+The dynamic WMTBAC requirements are higher than previously expected.
+A value of 60 means that, on average, bridges keep their IP address and
+port for 60 days.
+The dynamic values are cut off at 30 days by the static requirement which
+should be a high enough value.
+The goal here is to give blocked users a stable enough set of bridges so
+that they don't have to wait another 24~hours before receiving new ones.
+
+We can further see that the dynamic requirements are relatively stable
+over time except for the two phases of missing bridge status data.
+The first phase in July 2010 mostly affects WT, but neither WMTBAC nor
+WFU.
+The second phase in February 2011 affects all three metrics.
+We can expect the selection of stable bridges during February 2010 to be
+more random than at other times.
+
+\begin{figure}[t]
+\includegraphics[width=\textwidth]{requirements.pdf}
+\caption{Dynamic requirements for considering a bridge as stable}
+\label{fig:requirements}
+\end{figure}
+
+\subsection{Estimating fractions of bridges considered as stable}
+\label{sec:fractions}
+
+Requiring a bridge to meet or exceed either or both WMTBF or WFU metric
+results in considering only a subset of all bridges as stable.
+The first result of this analysis is to outline what fraction of bridges
+would be considered as stable if BridgeDB used either or both
+requirements.
+In theory, all parameters in the bridge stability definition on
+page~\pageref{def:bridgestability} could be adjusted to change the set of
+stable bridges or focus more on address changes or on fractional uptime.
+We're leaving the fine-tuning for future work when specifying and
+implementing the BridgeDB extension.
+
+Figure~\ref{fig:stablebridge} shows the fraction of stable bridges over
+time.
+If we only require bridges to meet or exceed the median WMTBAC or the
+fixed value of 30 days, roughly 55~\% of the bridges are considered as
+stable.
+If bridges are only required to meet or exceed the WT and WFU values,
+about $7/8 \times 1/2 = 43.75~\%$ of bridges are considered as stable.
+Requiring both WFU and WMTBAC leads to a fraction of roughly 35~\% stable
+bridges.
+
+\begin{figure}[t]
+\includegraphics[width=\textwidth]{stablebridge.pdf}
+\caption{Impact of requiring stable bridges to meet or exceed the median
+WFU and/or WMTBAC on the fraction of running bridges considered as stable}
+\label{fig:stablebridge}
+\end{figure}
+
+The fraction of 33~\% stable bridges seems appropriate if 1 out of
+3~bridges in the BridgeDB results is supposed to be a stable bridge.
+If more than 1~bridge should be a stable bridge, the requirements need to
+be lowered, so that a higher fraction of bridges is considered stable.
+Otherwise, the load on stable bridges might become too high.
+
+\subsection{Evaluating different requirements on stable bridges}
+\label{sec:selectedstability}
+
+The main purpose of this analysis is to compare the quality of certain
+requirements and requirement combinations on the stability of selected
+bridges.
+Similar to the previous section, we only compare whether or not the WMTBAC
+or WFU requirement is used, but don't change their parameters.
+
+The first result is the future uptime that we can expect from a bridge
+that we consider stable.
+We calculate future uptime similar to past uptime by weighting events in
+the near future more than those happening later.
+We are particularly interested in the almost worst-case scenario here,
+which is why we're looking at the 10th percentile weighted fractional
+uptime in the future.
+This number means that 10~\% of bridges have a weighted fractional uptime
+at most this high and 90~\% of bridges have a value at least this high.
+
+Figure~\ref{fig:fwfu-sim} visualizes the four possible combinations of
+using or not using the WMTBAC and WFU requirements.
+In this plot, the ``WFU \& WMTBAC'' and ``WFU'' lines almost entirely
+overlap, meaning that the WMTBAC requirement doesn't add anything to
+future uptime of selected bridges.
+If the WFU requirement is not used, requiring bridges to meet the WMTBAC
+requirement increases future uptime from roughly 35~\% to maybe 55~\%.
+That means that there is a slight correlation between the two metrics,
+which is plausible.
+
+\begin{figure}[t]
+\includegraphics[width=\textwidth]{fwfu-sim.pdf}
+\caption{Impact of requiring stable bridges to meet or exceed the median
+WFU and/or WMTBAC on the 10th percentile weighted fractional uptime in the
+future}
+\label{fig:fwfu-sim}
+\end{figure}
+
+The second result is the time that a selected bridge stays on the same
+address and port.
+We simply measure the time that the bridge will keep using its current
+address in days.
+Again, we look at the 10th percentile.
+90~\% of selected bridges keep their address longer than this time.
+
+Figure~\ref{fig:tosa-sim} shows for how long bridges keep their address
+and port.
+Bridges meeting both WFU and WTMBAC requirements keep their address for 2
+to 5~weeks.
+This value decreases to 1 to 3~weeks when taking away the WFU requirement,
+which is also a result of the two metrics beeing correlated.
+The bridges that only meet the WFU requirement and not the WMTBAC
+requirement change their address within the first week.
+If we don't use any requirement at all, which is what BridgeDB does today,
+10~\% of all bridges change their address within a single day.
+
+\begin{figure}[t]
+\includegraphics[width=\textwidth]{tosa-sim.pdf}
+\caption{Impact of requiring stable bridges to meet or exceed the median
+WFU and/or WMTBAC on the 10th percentile time on the same address}
+\label{fig:tosa-sim}
+\end{figure}
+
+\section{Concluding the bridge stability analysis}
+
+In this report we propose to extend BridgeDB to make it give out at least
+one stable bridge per user.
+Bridge stability can be calculated based on bridge status information over
+time, similar to how the directory authorities calculate relay stability.
+The bridge stability metric proposed here is based on a bridge's past
+uptime and the frequency of changing its address and/or port.
+Requiring at least 1 bridge of the 3 to be given out to users greatly
+reduces the worst case probability of all bridges being offline or
+changing their addresses or ports.
+The price for this increase in stability is that stable bridges will be
+given out more often than non-stable bridges and will therefore see more
+usage.
+
+We suggest to implement the described bridge stability metric in BridgeDB
+and make it configurable to tweak the requirement parameters if needed.
+Maybe it turns out to be more useful to lower the requirements for a
+bridge to become stable and give out two stable bridges per response.
+It's also possible that the requirement for a bridge to keep its address
+becomes less important in the future when bridge clients can request a
+bridge's current address from the bridge authority.
+All these scenarios can be analyzed before deploying them using archived
+data as done in this report.
+
+\bibliography{report}
+\bibliographystyle{plain}
+
+\end{document}
+
diff --git a/task-4255/stability.R b/task-4255/stability.R
new file mode 100644
index 0000000..b2cd487
--- /dev/null
+++ b/task-4255/stability.R
@@ -0,0 +1,220 @@
+library(ggplot2)
+stability <- read.csv("stability.csv", stringsAsFactors = FALSE)
+
+d <- stability[stability$time > '2010-07' & stability$time < '2011-07', ]
+d <- d[, c("time", "running")]
+d <- na.omit(d)
+d_mean <- aggregate(list(running = d$running),
+ by = list(date = as.Date(d$time)), quantile, probs = 0.5)
+d_max <- aggregate(list(running = d$running),
+ by = list(date = as.Date(d$time)), quantile, probs = 0.75)
+d_min <- aggregate(list(running = d$running),
+ by = list(date = as.Date(d$time)), quantile, probs = 0.25)
+d <- data.frame(x = d_mean$date, y = d_mean$running, ymin = d_min$running,
+ ymax = d_max$running)
+d <- rbind(d,
+ data.frame(x = as.Date(setdiff(seq(from = min(d$x, na.rm = TRUE),
+ to = max(d$x, na.rm = TRUE), by="1 day"), d$x), origin = "1970-01-01"),
+ y = NA, ymin = NA, ymax = NA))
+ggplot(d, aes(x = as.Date(x), y = y, ymin = ymin, ymax = ymax)) +
+geom_line() +
+scale_x_date(name = "", major = "3 months", minor = "1 month",
+ format = "%b %Y") +
+scale_y_continuous(name = "Running \nbridges ",
+ limits = c(0, max(d_mean$running, na.rm = TRUE))) +
+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 = "runningbridge.pdf", width = 7, height = 3, dpi = 100)
+
+pdf("runningbridge-detail.pdf", width = 7, height = 4)
+grid.newpage()
+pushViewport(viewport(layout = grid.layout(2, 1)))
+d <- stability[stability$time > '2010-07-10' &
+ stability$time < '2010-07-31', ]
+a <- ggplot(d, aes(x = as.POSIXct(time), y = running)) +
+geom_point(size = 0.75) +
+scale_x_datetime(name = "", major = "1 week", minor = "1 day",
+ format = "%b %d, %Y") +
+scale_y_continuous(name = "Running \nbridges ",
+ limits = c(0, max(d$running, na.rm = TRUE))) +
+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),
+ legend.position = "none")
+d <- stability[stability$time > '2011-01-29' &
+ stability$time < '2011-02-19', ]
+e <- read.csv("stale-bridge-tarballs.csv", stringsAsFactors = FALSE,
+ col.names = c("time"))
+d <- rbind(
+ data.frame(time = d$time, running = d$running, colour = "black"),
+ data.frame(time = e$time, running = 687, colour = "grey"))
+b <- ggplot(d, aes(x = as.POSIXct(time), y = running, colour = colour)) +
+geom_point(size = 0.75) +
+scale_x_datetime(name = "", major = "1 week", minor = "1 day",
+ format = "%b %d, %Y") +
+scale_y_continuous(name = "Running \nbridges ",
+ limits = c(0, max(d$running, na.rm = TRUE))) +
+scale_colour_manual(values = c("black", "grey60")) +
+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),
+ legend.position = "none")
+print(a, vp = viewport(layout.pos.row = 1, layout.pos.col = 1))
+print(b, vp = viewport(layout.pos.row = 2, layout.pos.col = 1))
+dev.off()
+
+d <- stability[stability$time > '2010-07' & stability$time < '2011-07', ]
+d <- d[, c("time", "minwmtbaca50wmtbac", "minwta", "minwfua50wfu")]
+d <- na.omit(d)
+d_mean <- aggregate(d[, 2:length(d)], by = list(date = as.Date(d$time)),
+ quantile, probs = 0.5)
+d_max <- aggregate(d[, 2:length(d)], by = list(date = as.Date(d$time)),
+ quantile, probs = 0.75)
+d_min <- aggregate(d[, 2:length(d)], by = list(date = as.Date(d$time)),
+ quantile, probs = 0.25)
+d <- rbind(
+ data.frame(x = d_mean$date,
+ y = d_mean$minwmtbaca50wmtbac / (24 * 60 * 60),
+ ymin = d_min$minwmtbaca50wmtbac / (24 * 60 * 60),
+ ymax = d_max$minwmtbaca50wmtbac / (24 * 60 * 60),
+ var = "Median WMTBAC"),
+ 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 perc. WT"),
+ data.frame(x = d_mean$date, y = d_mean$minwfua50wfu / 10000,
+ ymin = d_min$minwfua50wfu / 10000,
+ ymax = d_max$minwfua50wfu / 10000,
+ var = "Median WFU"))
+missing_dates <- as.Date(setdiff(seq(from = min(d$x, na.rm = TRUE),
+ to = max(d$x, na.rm = TRUE), by="1 day"), d$x), origin = "1970-01-01")
+d <- rbind(d,
+ data.frame(x = missing_dates, y = NA, ymin = NA, ymax = NA,
+ var = "Median WMTBAC"),
+ data.frame(x = missing_dates, y = NA, ymin = NA, ymax = NA,
+ var = "12.5th perc. WT"),
+ data.frame(x = missing_dates, y = NA, ymin = NA, ymax = NA,
+ var = "Median WFU"))
+e <- data.frame(
+ yintercept = c(30, 8, 0.98),
+ var = c("Median WMTBAC", "12.5th perc. WT", "Median WFU"))
+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 = "gray40",
+ linetype = 2) +
+facet_grid(var ~ ., scales = "free_y") +
+scale_x_date(name = "", major = "3 months", minor = "1 month",
+ format = "%b %Y") +
+scale_y_continuous(name = "") +
+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 = "requirements.pdf", width = 7, height = 5, dpi = 100)
+
+d <- stability[stability$time > '2010-07' & stability$time < '2011-07', ]
+d <- d[, c("time", "perc10wfu0wfu0wmtbac", "perc10wfu0wfu50wmtbac",
+ "perc10wfu50wfu0wmtbac", "perc10wfu50wfu50wmtbac")]
+d <- na.omit(d)
+d <- aggregate(d[, 2:length(d)], by = list(date = as.Date(d$time)),
+ quantile, probs = 0.5)
+d <- rbind(d,
+ data.frame(date = as.Date(setdiff(seq(from = min(d$date),
+ to = max(d$date), by="1 day"), d$date), origin = "1970-01-01"),
+ perc10wfu0wfu0wmtbac = NA, perc10wfu0wfu50wmtbac = NA,
+ perc10wfu50wfu0wmtbac = NA, perc10wfu50wfu50wmtbac = NA))
+d <- melt(d, id = "date")
+ggplot(d, aes(x = date, y = value / 10000, linetype = variable)) +
+geom_line() +
+scale_y_continuous(name = paste("10th perc. \nWFU in \n",
+ "the future ", sep = ""), formatter = "percent", limits = c(0, 1)) +
+scale_x_date(name = "", major = "3 months", minor = "1 month",
+ format = "%b %Y") +
+scale_linetype_manual(name = paste("Requirements for\nconsidering",
+ "a\nbridge as stable\n"), breaks = c("perc10wfu50wfu50wmtbac",
+ "perc10wfu50wfu0wmtbac", "perc10wfu0wfu50wmtbac",
+ "perc10wfu0wfu0wmtbac"), labels = c("WFU & WMTBAC", "WFU", "WMTBAC",
+ "None"), values = c(1, 3, 2, 4)) +
+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 = "fwfu-sim.pdf", width = 7, height = 3, dpi = 100)
+
+d <- stability[stability$time > '2010-07' & stability$time < '2011-07', ]
+d <- d[, c("time", "perc10tosa0wfu0wmtbac", "perc10tosa0wfu50wmtbac",
+ "perc10tosa50wfu0wmtbac", "perc10tosa50wfu50wmtbac")]
+d <- na.omit(d)
+d <- aggregate(d[, 2:length(d)], by = list(date = as.Date(d$time)),
+ quantile, probs = 0.5)
+d <- rbind(d,
+ data.frame(date = as.Date(setdiff(seq(from = min(d$date),
+ to = max(d$date), by="1 day"), d$date), origin = "1970-01-01"),
+ perc10tosa0wfu0wmtbac = NA, perc10tosa0wfu50wmtbac = NA,
+ perc10tosa50wfu0wmtbac = NA, perc10tosa50wfu50wmtbac = NA))
+d <- melt(d, id = "date")
+ggplot(d, aes(x = date, y = value / 86400, linetype = variable)) +
+geom_line() +
+scale_y_continuous(name = paste("10th perc. \ntime on \nthe same \n",
+ "address \nin days ", sep = ""),
+ breaks = seq(0, max(d$value / 86400, na.rm = TRUE), 7),
+ minor = seq(0, max(d$value / 86400, na.rm = TRUE), 1),
+ limits = c(0, max(d$value / 86400, na.rm = TRUE))) +
+scale_x_date(name = "", major = "3 months", minor = "1 month",
+ format = "%b %Y") +
+scale_linetype_manual(name = paste("Requirements for\nconsidering",
+ "a\nbridge as stable\n"), breaks = c("perc10tosa50wfu50wmtbac",
+ "perc10tosa0wfu50wmtbac", "perc10tosa50wfu0wmtbac",
+ "perc10tosa0wfu0wmtbac"), labels = c("WFU & WMTBAC", "WMTBAC", "WFU",
+ "None"), values = c(1, 3, 2, 4)) +
+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 = "tosa-sim.pdf", width = 7, height = 3, dpi = 100)
+
+d <- stability[stability$time > '2010-07' & stability$time < '2011-07', ]
+d <- d[, c("time", "stablebridge0wfu50wmtbac", "stablebridge50wfu0wmtbac",
+ "stablebridge50wfu50wmtbac", "running")]
+d <- na.omit(d)
+#d <- aggregate(d[, 2:length(d)], by = list(date = as.Date(d$time)),
+# quantile, probs = 0.5)
+d <- rbind(
+ data.frame(time = d$time, y = d$stablebridge0wfu50wmtbac / d$running,
+ variable = "WMTBAC"),
+ data.frame(time = d$time, y = d$stablebridge50wfu0wmtbac / d$running,
+ variable = "WFU"),
+ data.frame(time = d$time, y = d$stablebridge50wfu50wmtbac / d$running,
+ variable = "WFU & WMTBAC"))
+d <- aggregate(list(y = d$y), by = list(x = as.Date(d$time),
+ variable = d$variable), quantile, probs = 0.5)
+missing_dates <- as.Date(setdiff(seq(from = min(d$x, na.rm = TRUE),
+ to = max(d$x, na.rm = TRUE), by="1 day"), d$x), origin = "1970-01-01")
+d <- rbind(d,
+ data.frame(x = missing_dates, y = NA,
+ variable = "WMTBAC"),
+ data.frame(x = missing_dates, y = NA,
+ variable = "WFU"),
+ data.frame(x = missing_dates, y = NA,
+ variable = "WFU & WMTBAC"))
+ggplot(d, aes(x = x, y = y, linetype = variable)) +
+geom_line() +
+scale_y_continuous(name = "Fraction of \nRunning \nbridges ",
+ 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_linetype_manual(name = paste("\nRequirements for\nconsidering",
+ "a\nbridge as stable\n"), values = c(3, 2, 4)) +
+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 = "stablebridge.pdf", width = 7, height = 3, dpi = 100)
+
diff --git a/task-4255/stale-bridge-tarballs.csv b/task-4255/stale-bridge-tarballs.csv
new file mode 100644
index 0000000..ff430a4
--- /dev/null
+++ b/task-4255/stale-bridge-tarballs.csv
@@ -0,0 +1,760 @@
+2011-01-31 06:07:03
+2011-01-31 06:37:03
+2011-01-31 07:07:03
+2011-01-31 07:37:02
+2011-01-31 08:07:02
+2011-01-31 08:37:03
+2011-01-31 09:07:03
+2011-01-31 09:37:04
+2011-01-31 10:07:03
+2011-01-31 10:37:03
+2011-01-31 11:07:03
+2011-01-31 11:37:03
+2011-01-31 12:07:02
+2011-01-31 12:37:03
+2011-01-31 13:07:03
+2011-01-31 13:37:03
+2011-01-31 14:07:02
+2011-01-31 14:37:03
+2011-01-31 15:07:02
+2011-01-31 15:37:03
+2011-01-31 16:07:02
+2011-01-31 16:37:03
+2011-01-31 17:07:03
+2011-01-31 17:37:02
+2011-01-31 18:07:04
+2011-01-31 18:37:03
+2011-01-31 19:07:03
+2011-01-31 19:37:03
+2011-01-31 20:07:03
+2011-01-31 20:37:02
+2011-01-31 21:07:03
+2011-01-31 21:37:02
+2011-01-31 22:07:02
+2011-01-31 22:37:03
+2011-01-31 23:07:02
+2011-01-31 23:37:03
+2011-02-01 00:07:02
+2011-02-01 00:37:02
+2011-02-01 01:07:02
+2011-02-01 01:37:03
+2011-02-01 02:07:02
+2011-02-01 02:37:02
+2011-02-01 03:07:02
+2011-02-01 03:37:03
+2011-02-01 04:07:02
+2011-02-01 04:37:02
+2011-02-01 05:07:03
+2011-02-01 05:37:03
+2011-02-01 06:07:03
+2011-02-01 06:37:03
+2011-02-01 07:07:03
+2011-02-01 07:37:03
+2011-02-01 08:07:02
+2011-02-01 08:37:03
+2011-02-01 09:07:02
+2011-02-01 09:37:03
+2011-02-01 10:07:02
+2011-02-01 10:37:03
+2011-02-01 11:07:02
+2011-02-01 11:37:02
+2011-02-01 12:07:03
+2011-02-01 12:37:03
+2011-02-01 13:07:03
+2011-02-01 13:37:03
+2011-02-01 14:07:03
+2011-02-01 14:37:03
+2011-02-01 15:07:03
+2011-02-01 15:37:02
+2011-02-01 16:07:02
+2011-02-01 16:37:03
+2011-02-01 17:07:03
+2011-02-01 17:37:03
+2011-02-01 18:07:02
+2011-02-01 18:37:03
+2011-02-01 19:07:03
+2011-02-01 19:37:03
+2011-02-01 20:07:03
+2011-02-01 20:37:02
+2011-02-01 21:07:08
+2011-02-01 21:37:03
+2011-02-01 22:07:03
+2011-02-01 22:37:03
+2011-02-01 23:07:02
+2011-02-01 23:37:03
+2011-02-02 00:07:02
+2011-02-02 00:37:03
+2011-02-02 01:07:02
+2011-02-02 01:37:02
+2011-02-02 02:07:03
+2011-02-02 02:37:02
+2011-02-02 03:07:03
+2011-02-02 03:37:03
+2011-02-02 04:07:02
+2011-02-02 04:37:03
+2011-02-02 05:07:02
+2011-02-02 05:37:03
+2011-02-02 06:07:03
+2011-02-02 06:37:02
+2011-02-02 07:07:03
+2011-02-02 07:37:03
+2011-02-02 08:07:03
+2011-02-02 08:37:02
+2011-02-02 09:07:03
+2011-02-02 09:37:03
+2011-02-02 10:07:03
+2011-02-02 10:37:02
+2011-02-02 11:07:02
+2011-02-02 11:37:02
+2011-02-02 12:07:03
+2011-02-02 12:37:03
+2011-02-02 13:07:02
+2011-02-02 13:37:03
+2011-02-02 14:07:02
+2011-02-02 14:37:03
+2011-02-02 15:07:03
+2011-02-02 15:37:02
+2011-02-02 16:07:03
+2011-02-02 16:37:03
+2011-02-02 17:07:03
+2011-02-02 17:37:03
+2011-02-02 18:07:03
+2011-02-02 18:37:02
+2011-02-02 19:07:03
+2011-02-02 19:37:03
+2011-02-02 20:07:03
+2011-02-02 20:37:03
+2011-02-02 21:07:03
+2011-02-02 21:37:03
+2011-02-02 22:07:03
+2011-02-02 22:37:03
+2011-02-02 23:07:03
+2011-02-02 23:37:03
+2011-02-03 00:07:03
+2011-02-03 00:37:02
+2011-02-03 01:07:03
+2011-02-03 01:37:02
+2011-02-03 02:07:03
+2011-02-03 02:37:02
+2011-02-03 03:07:02
+2011-02-03 03:37:02
+2011-02-03 04:07:03
+2011-02-03 04:37:02
+2011-02-03 05:07:02
+2011-02-03 05:37:03
+2011-02-03 06:07:03
+2011-02-03 06:37:03
+2011-02-03 07:07:02
+2011-02-03 07:37:02
+2011-02-03 08:07:02
+2011-02-03 08:37:02
+2011-02-03 09:07:03
+2011-02-03 09:37:03
+2011-02-03 10:07:02
+2011-02-03 10:37:03
+2011-02-03 11:07:02
+2011-02-03 11:37:03
+2011-02-03 12:07:02
+2011-02-03 12:37:02
+2011-02-03 13:07:03
+2011-02-03 13:37:03
+2011-02-03 14:07:02
+2011-02-03 14:37:03
+2011-02-03 15:07:02
+2011-02-03 15:37:02
+2011-02-03 16:07:03
+2011-02-03 16:37:03
+2011-02-03 17:07:02
+2011-02-03 17:37:03
+2011-02-03 18:07:03
+2011-02-03 18:37:03
+2011-02-03 19:07:02
+2011-02-03 19:37:03
+2011-02-03 20:07:03
+2011-02-03 20:37:03
+2011-02-03 21:07:03
+2011-02-03 21:37:03
+2011-02-03 22:07:03
+2011-02-03 22:37:03
+2011-02-03 23:07:02
+2011-02-03 23:37:03
+2011-02-04 00:07:02
+2011-02-04 00:37:03
+2011-02-04 01:07:03
+2011-02-04 01:37:02
+2011-02-04 02:07:03
+2011-02-04 02:37:03
+2011-02-04 03:07:03
+2011-02-04 03:37:02
+2011-02-04 04:07:02
+2011-02-04 04:37:03
+2011-02-04 05:07:02
+2011-02-04 05:37:03
+2011-02-04 06:07:03
+2011-02-04 06:37:03
+2011-02-04 07:07:03
+2011-02-04 07:37:03
+2011-02-04 08:07:03
+2011-02-04 08:37:03
+2011-02-04 09:07:02
+2011-02-04 09:37:03
+2011-02-04 10:07:03
+2011-02-04 10:37:03
+2011-02-04 11:07:03
+2011-02-04 11:37:02
+2011-02-04 12:07:03
+2011-02-04 12:37:02
+2011-02-04 13:07:03
+2011-02-04 13:37:03
+2011-02-04 14:07:03
+2011-02-04 14:37:02
+2011-02-04 15:07:03
+2011-02-04 15:37:03
+2011-02-04 16:07:03
+2011-02-04 16:37:02
+2011-02-04 17:07:03
+2011-02-04 17:37:03
+2011-02-04 18:07:03
+2011-02-04 18:37:03
+2011-02-04 19:07:03
+2011-02-04 19:37:03
+2011-02-04 20:07:03
+2011-02-04 20:37:03
+2011-02-04 21:07:02
+2011-02-04 21:37:02
+2011-02-04 22:07:02
+2011-02-04 22:37:03
+2011-02-04 23:07:03
+2011-02-04 23:37:03
+2011-02-05 00:07:03
+2011-02-05 00:37:02
+2011-02-05 01:07:03
+2011-02-05 01:37:03
+2011-02-05 02:07:03
+2011-02-05 02:37:02
+2011-02-05 03:07:03
+2011-02-05 03:37:02
+2011-02-05 04:07:03
+2011-02-05 04:37:03
+2011-02-05 05:07:03
+2011-02-05 05:37:05
+2011-02-05 06:07:02
+2011-02-05 06:37:02
+2011-02-05 07:07:02
+2011-02-05 07:37:03
+2011-02-05 08:07:03
+2011-02-05 08:37:03
+2011-02-05 09:07:03
+2011-02-05 09:37:02
+2011-02-05 10:07:03
+2011-02-05 10:37:03
+2011-02-05 11:07:02
+2011-02-05 11:37:02
+2011-02-05 12:07:03
+2011-02-05 12:37:03
+2011-02-05 13:07:02
+2011-02-05 13:37:03
+2011-02-05 14:07:04
+2011-02-05 14:37:03
+2011-02-05 15:07:03
+2011-02-05 15:37:03
+2011-02-05 16:07:02
+2011-02-05 16:37:03
+2011-02-05 17:07:03
+2011-02-05 17:37:03
+2011-02-05 18:07:03
+2011-02-05 18:37:03
+2011-02-05 19:07:02
+2011-02-05 19:37:03
+2011-02-05 20:07:03
+2011-02-05 20:37:03
+2011-02-05 21:07:02
+2011-02-05 21:37:03
+2011-02-05 22:07:03
+2011-02-05 22:37:03
+2011-02-05 23:07:03
+2011-02-05 23:37:02
+2011-02-06 00:07:03
+2011-02-06 00:37:02
+2011-02-06 01:07:03
+2011-02-06 01:37:02
+2011-02-06 02:07:03
+2011-02-06 02:37:03
+2011-02-06 03:07:03
+2011-02-06 03:37:06
+2011-02-06 04:07:03
+2011-02-06 04:37:03
+2011-02-06 05:07:03
+2011-02-06 05:37:03
+2011-02-06 06:07:03
+2011-02-06 06:37:03
+2011-02-06 07:07:02
+2011-02-06 07:37:02
+2011-02-06 08:07:02
+2011-02-06 08:37:03
+2011-02-06 09:07:02
+2011-02-06 09:37:02
+2011-02-06 10:07:02
+2011-02-06 10:37:02
+2011-02-06 11:07:02
+2011-02-06 11:37:02
+2011-02-06 12:07:03
+2011-02-06 12:37:02
+2011-02-06 13:07:02
+2011-02-06 13:37:03
+2011-02-06 14:07:03
+2011-02-06 14:37:02
+2011-02-06 15:07:02
+2011-02-06 15:37:03
+2011-02-06 16:07:03
+2011-02-06 16:37:03
+2011-02-06 17:07:03
+2011-02-06 17:37:02
+2011-02-06 18:07:03
+2011-02-06 18:37:02
+2011-02-06 19:07:02
+2011-02-06 19:37:02
+2011-02-06 20:07:03
+2011-02-06 20:37:02
+2011-02-06 21:07:03
+2011-02-06 21:37:03
+2011-02-06 22:07:03
+2011-02-06 22:37:02
+2011-02-06 23:07:02
+2011-02-06 23:37:03
+2011-02-07 00:07:03
+2011-02-07 00:37:02
+2011-02-07 01:07:03
+2011-02-07 01:37:02
+2011-02-07 02:07:02
+2011-02-07 02:37:02
+2011-02-07 03:07:02
+2011-02-07 03:37:03
+2011-02-07 04:07:02
+2011-02-07 04:37:02
+2011-02-07 05:07:02
+2011-02-07 05:37:03
+2011-02-07 06:07:03
+2011-02-07 06:37:02
+2011-02-07 07:07:03
+2011-02-07 07:37:03
+2011-02-07 08:07:03
+2011-02-07 08:37:03
+2011-02-07 09:07:03
+2011-02-07 09:37:02
+2011-02-07 10:07:02
+2011-02-07 10:37:02
+2011-02-07 11:07:02
+2011-02-07 11:37:02
+2011-02-07 12:07:03
+2011-02-07 12:37:03
+2011-02-07 13:07:03
+2011-02-07 13:37:02
+2011-02-07 14:07:03
+2011-02-07 14:37:03
+2011-02-07 15:07:03
+2011-02-07 15:37:03
+2011-02-07 16:07:02
+2011-02-07 16:37:03
+2011-02-07 17:07:02
+2011-02-07 17:37:02
+2011-02-07 18:07:03
+2011-02-07 18:37:03
+2011-02-07 19:07:02
+2011-02-07 19:37:02
+2011-02-07 20:07:03
+2011-02-07 20:37:03
+2011-02-07 21:07:06
+2011-02-07 21:37:02
+2011-02-07 22:07:02
+2011-02-07 22:37:03
+2011-02-07 23:07:03
+2011-02-07 23:37:02
+2011-02-08 00:07:02
+2011-02-08 00:37:02
+2011-02-08 01:07:03
+2011-02-08 01:37:03
+2011-02-08 02:07:02
+2011-02-08 02:37:03
+2011-02-08 03:07:03
+2011-02-08 03:37:03
+2011-02-08 04:07:02
+2011-02-08 04:37:03
+2011-02-08 05:07:02
+2011-02-08 05:37:03
+2011-02-08 06:07:03
+2011-02-08 06:37:02
+2011-02-08 07:07:03
+2011-02-08 07:37:03
+2011-02-08 08:07:02
+2011-02-08 08:37:03
+2011-02-08 09:07:03
+2011-02-08 09:37:02
+2011-02-08 10:07:02
+2011-02-08 10:37:03
+2011-02-08 11:07:02
+2011-02-08 11:37:02
+2011-02-08 12:07:02
+2011-02-08 12:37:02
+2011-02-08 13:07:03
+2011-02-08 13:37:02
+2011-02-08 14:07:03
+2011-02-08 14:37:02
+2011-02-08 15:07:03
+2011-02-08 15:37:02
+2011-02-08 16:07:03
+2011-02-08 16:37:03
+2011-02-08 17:07:03
+2011-02-08 17:37:03
+2011-02-08 18:07:03
+2011-02-08 18:37:02
+2011-02-08 19:07:03
+2011-02-08 19:37:03
+2011-02-08 20:07:03
+2011-02-08 20:37:03
+2011-02-08 21:07:03
+2011-02-08 21:37:03
+2011-02-08 22:07:03
+2011-02-08 22:37:05
+2011-02-08 23:07:03
+2011-02-08 23:37:02
+2011-02-09 00:07:02
+2011-02-09 00:37:02
+2011-02-09 01:07:02
+2011-02-09 01:37:03
+2011-02-09 02:07:02
+2011-02-09 02:37:03
+2011-02-09 03:07:03
+2011-02-09 03:37:03
+2011-02-09 04:07:03
+2011-02-09 04:37:03
+2011-02-09 05:07:02
+2011-02-09 05:37:03
+2011-02-09 06:07:03
+2011-02-09 06:37:03
+2011-02-09 07:07:03
+2011-02-09 07:37:03
+2011-02-09 08:07:02
+2011-02-09 08:37:02
+2011-02-09 09:07:03
+2011-02-09 09:37:03
+2011-02-09 10:07:03
+2011-02-09 10:37:02
+2011-02-09 11:07:02
+2011-02-09 11:37:03
+2011-02-09 12:07:03
+2011-02-09 12:37:03
+2011-02-09 13:07:02
+2011-02-09 13:37:02
+2011-02-09 14:07:03
+2011-02-09 14:37:02
+2011-02-09 15:07:03
+2011-02-09 15:37:02
+2011-02-09 16:07:03
+2011-02-09 16:37:02
+2011-02-09 17:07:02
+2011-02-09 17:37:03
+2011-02-09 18:07:03
+2011-02-09 18:37:03
+2011-02-09 19:07:03
+2011-02-09 19:37:03
+2011-02-09 20:07:03
+2011-02-09 20:37:02
+2011-02-09 21:07:02
+2011-02-09 21:37:03
+2011-02-09 22:07:03
+2011-02-09 22:37:03
+2011-02-09 23:07:02
+2011-02-09 23:37:03
+2011-02-10 00:07:03
+2011-02-10 00:37:03
+2011-02-10 01:07:02
+2011-02-10 01:37:02
+2011-02-10 02:07:03
+2011-02-10 02:37:02
+2011-02-10 03:07:02
+2011-02-10 03:37:03
+2011-02-10 04:07:03
+2011-02-10 04:37:02
+2011-02-10 05:07:03
+2011-02-10 05:37:03
+2011-02-10 06:07:03
+2011-02-10 06:37:02
+2011-02-10 07:07:02
+2011-02-10 07:37:03
+2011-02-10 08:07:03
+2011-02-10 08:37:03
+2011-02-10 09:07:02
+2011-02-10 09:37:02
+2011-02-10 10:07:02
+2011-02-10 10:37:03
+2011-02-10 11:07:03
+2011-02-10 11:37:03
+2011-02-10 12:07:03
+2011-02-10 12:37:02
+2011-02-10 13:07:03
+2011-02-10 13:37:02
+2011-02-10 14:07:03
+2011-02-10 14:37:03
+2011-02-10 15:07:02
+2011-02-10 15:37:03
+2011-02-10 16:07:03
+2011-02-10 16:37:03
+2011-02-10 17:07:02
+2011-02-10 17:37:03
+2011-02-10 18:07:02
+2011-02-10 18:37:03
+2011-02-10 19:07:02
+2011-02-10 19:37:02
+2011-02-10 20:07:03
+2011-02-10 20:37:03
+2011-02-10 21:07:03
+2011-02-10 21:37:03
+2011-02-10 22:07:03
+2011-02-10 22:37:03
+2011-02-10 23:07:03
+2011-02-10 23:37:05
+2011-02-11 00:07:03
+2011-02-11 00:37:03
+2011-02-11 01:07:03
+2011-02-11 01:37:03
+2011-02-11 02:07:03
+2011-02-11 02:37:02
+2011-02-11 03:07:02
+2011-02-11 03:37:03
+2011-02-11 04:07:03
+2011-02-11 04:37:03
+2011-02-11 05:07:02
+2011-02-11 05:37:02
+2011-02-11 06:07:03
+2011-02-11 06:37:03
+2011-02-11 07:07:03
+2011-02-11 07:37:03
+2011-02-11 08:07:03
+2011-02-11 08:37:03
+2011-02-11 09:07:03
+2011-02-11 09:37:03
+2011-02-11 10:07:03
+2011-02-11 10:37:02
+2011-02-11 11:07:02
+2011-02-11 11:37:03
+2011-02-11 12:07:03
+2011-02-11 12:37:03
+2011-02-11 13:07:03
+2011-02-11 13:37:02
+2011-02-11 14:07:03
+2011-02-11 14:37:03
+2011-02-11 15:07:03
+2011-02-11 15:37:04
+2011-02-11 16:07:03
+2011-02-11 16:37:03
+2011-02-11 17:07:03
+2011-02-11 17:37:03
+2011-02-11 18:07:03
+2011-02-11 18:37:03
+2011-02-11 19:07:03
+2011-02-11 19:37:03
+2011-02-11 20:07:03
+2011-02-11 20:37:03
+2011-02-11 21:07:03
+2011-02-11 21:37:03
+2011-02-11 22:07:02
+2011-02-11 22:37:02
+2011-02-11 23:07:02
+2011-02-11 23:37:03
+2011-02-12 00:07:02
+2011-02-12 00:37:02
+2011-02-12 01:07:03
+2011-02-12 01:37:03
+2011-02-12 02:07:02
+2011-02-12 02:37:02
+2011-02-12 03:07:02
+2011-02-12 03:37:03
+2011-02-12 04:07:02
+2011-02-12 04:37:03
+2011-02-12 05:07:02
+2011-02-12 05:37:02
+2011-02-12 06:07:03
+2011-02-12 06:37:03
+2011-02-12 07:07:02
+2011-02-12 07:37:03
+2011-02-12 08:07:03
+2011-02-12 08:37:03
+2011-02-12 09:07:03
+2011-02-12 09:37:03
+2011-02-12 10:07:02
+2011-02-12 10:37:03
+2011-02-12 11:07:03
+2011-02-12 11:37:03
+2011-02-12 12:07:03
+2011-02-12 12:37:03
+2011-02-12 13:07:03
+2011-02-12 13:37:03
+2011-02-12 14:07:03
+2011-02-12 14:37:02
+2011-02-12 15:07:02
+2011-02-12 15:37:03
+2011-02-12 16:07:03
+2011-02-12 16:37:03
+2011-02-12 17:07:03
+2011-02-12 17:37:03
+2011-02-12 18:07:03
+2011-02-12 18:37:02
+2011-02-12 19:07:02
+2011-02-12 19:37:03
+2011-02-12 20:07:03
+2011-02-12 20:37:03
+2011-02-12 21:07:03
+2011-02-12 21:37:03
+2011-02-12 22:07:03
+2011-02-12 22:37:03
+2011-02-12 23:07:03
+2011-02-12 23:37:03
+2011-02-13 00:07:02
+2011-02-13 00:37:03
+2011-02-13 01:07:03
+2011-02-13 01:37:02
+2011-02-13 02:07:02
+2011-02-13 02:37:03
+2011-02-13 03:07:02
+2011-02-13 03:37:03
+2011-02-13 04:07:03
+2011-02-13 04:37:03
+2011-02-13 05:07:03
+2011-02-13 05:37:03
+2011-02-13 06:07:03
+2011-02-13 06:37:03
+2011-02-13 07:07:02
+2011-02-13 07:37:02
+2011-02-13 08:07:03
+2011-02-13 08:37:03
+2011-02-13 09:07:03
+2011-02-13 09:37:03
+2011-02-13 10:07:03
+2011-02-13 10:37:02
+2011-02-13 11:07:03
+2011-02-13 11:37:03
+2011-02-13 12:07:03
+2011-02-13 12:37:02
+2011-02-13 13:07:02
+2011-02-13 13:37:03
+2011-02-13 14:07:03
+2011-02-13 14:37:02
+2011-02-13 15:07:02
+2011-02-13 15:37:03
+2011-02-13 16:07:04
+2011-02-13 16:37:03
+2011-02-13 17:07:03
+2011-02-13 17:37:03
+2011-02-13 18:07:02
+2011-02-13 18:37:03
+2011-02-13 19:07:03
+2011-02-13 19:37:03
+2011-02-13 20:07:03
+2011-02-13 20:37:03
+2011-02-13 21:07:03
+2011-02-13 21:37:02
+2011-02-13 22:07:03
+2011-02-13 22:37:03
+2011-02-13 23:07:02
+2011-02-13 23:37:02
+2011-02-14 00:07:03
+2011-02-14 00:37:02
+2011-02-14 01:07:03
+2011-02-14 01:37:02
+2011-02-14 02:07:03
+2011-02-14 02:37:03
+2011-02-14 03:07:03
+2011-02-14 03:37:03
+2011-02-14 04:07:02
+2011-02-14 04:37:02
+2011-02-14 05:07:02
+2011-02-14 05:37:03
+2011-02-14 06:07:03
+2011-02-14 06:37:02
+2011-02-14 07:07:02
+2011-02-14 07:37:02
+2011-02-14 08:07:02
+2011-02-14 08:37:03
+2011-02-14 09:07:02
+2011-02-14 09:37:02
+2011-02-14 10:07:03
+2011-02-14 10:37:03
+2011-02-14 11:07:03
+2011-02-14 11:37:02
+2011-02-14 12:07:03
+2011-02-14 12:37:03
+2011-02-14 13:07:03
+2011-02-14 13:37:02
+2011-02-14 14:07:02
+2011-02-14 14:37:03
+2011-02-14 15:07:03
+2011-02-14 15:37:02
+2011-02-14 16:07:02
+2011-02-14 16:37:03
+2011-02-14 17:07:02
+2011-02-14 17:37:03
+2011-02-14 18:07:03
+2011-02-14 18:37:03
+2011-02-14 19:07:02
+2011-02-14 19:37:03
+2011-02-14 20:07:03
+2011-02-14 20:37:03
+2011-02-14 21:07:03
+2011-02-14 21:37:03
+2011-02-14 22:07:03
+2011-02-14 22:37:03
+2011-02-14 23:07:03
+2011-02-14 23:37:02
+2011-02-15 00:07:03
+2011-02-15 00:37:02
+2011-02-15 01:07:03
+2011-02-15 01:37:03
+2011-02-15 02:07:03
+2011-02-15 02:37:03
+2011-02-15 03:07:03
+2011-02-15 03:37:02
+2011-02-15 04:07:03
+2011-02-15 04:37:03
+2011-02-15 05:07:02
+2011-02-15 05:37:02
+2011-02-15 06:07:02
+2011-02-15 06:37:02
+2011-02-15 07:07:03
+2011-02-15 07:37:02
+2011-02-15 08:07:03
+2011-02-15 08:37:02
+2011-02-15 09:07:02
+2011-02-15 09:37:03
+2011-02-15 10:07:02
+2011-02-15 10:37:02
+2011-02-15 11:07:03
+2011-02-15 11:37:03
+2011-02-15 12:07:03
+2011-02-15 12:37:02
+2011-02-15 13:07:02
+2011-02-15 13:37:02
+2011-02-15 14:07:03
+2011-02-15 14:37:02
+2011-02-15 15:07:02
+2011-02-15 15:37:02
+2011-02-15 16:07:02
+2011-02-15 16:37:02
+2011-02-15 17:07:03
+2011-02-15 17:37:03
+2011-02-15 18:07:03
+2011-02-15 18:37:03
+2011-02-15 19:07:03
+2011-02-15 19:37:02
+2011-02-15 20:07:03
+2011-02-15 20:37:03
+2011-02-15 21:07:03
+2011-02-15 21:37:03
+2011-02-15 22:07:03
+2011-02-15 22:37:03
+2011-02-15 23:07:02
+2011-02-15 23:37:02
+2011-02-16 00:07:03
+2011-02-16 00:37:02
+2011-02-16 01:07:04
+2011-02-16 01:37:02
