commit 23f0121a659c520de35865da61a6080e30fed04d Author: Karsten Loesing <karsten.loesing@gmx.net> Date: Wed Jul 25 20:23:11 2012 +0200 Add exit probability based on advertised bw (#6443). --- task-6443/cumulated-weights.R | 9 ++- task-6443/run.sh | 3 + .../src/CalculatePathSelectionProbabilities.java | 93 +++++++++++++------- 3 files changed, 71 insertions(+), 34 deletions(-) diff --git a/task-6443/cumulated-weights.R b/task-6443/cumulated-weights.R index c324acb..811564b 100755 --- a/task-6443/cumulated-weights.R +++ b/task-6443/cumulated-weights.R @@ -3,7 +3,9 @@ require(scales) require(reshape) cw <- read.csv("cumulated-weights.csv", stringsAsFactors = FALSE) -v <- sort(as.POSIXlt(unique(cw$validafter), tz = "UTC"), +v <- cw +v <- v[v$weight_type == "consensus weights", c(1, 3, 4)] +v <- sort(as.POSIXlt(unique(v$validafter), tz = "UTC"), decreasing = TRUE) now <- week <- month <- threemonths <- year <- v[1] week$mday <- week$mday - 7 @@ -32,6 +34,7 @@ opts(title = paste("Probability of selecting one of the top-x relays for", ggsave("exit-probability-cdf-a.png", width = 8, height = 5, dpi = 100) c <- cw +c <- c[c$weight_type == "consensus weights", c(1, 3, 4)] c <- c[c$top_relays %in% c(1, 2, 5, 10, 20, 50), ] c <- aggregate(list(total_exit_probability = c$total_exit_probability), by = list(date = as.Date(cut.Date(as.Date(c$validafter, @@ -48,7 +51,9 @@ opts(title = paste("Probability of selecting one of the top-x relays for", "the exit position\n"), legend.position = "bottom") ggsave("exit-probability-cdf-b.png", width = 8, height = 5, dpi = 100) -i <- read.csv("inverse-cumulated-weights.csv", stringsAsFactors = FALSE) +iw <- read.csv("inverse-cumulated-weights.csv", stringsAsFactors = FALSE) +i <- iw +i <- i[i$weight_type == "consensus weights", c(1, 3, 4)] i <- i[i$total_exit_probability %in% factor(c(0.3, 0.4, 0.5, 0.6, 0.7)), ] i <- aggregate(list(top_relays = i$top_relays), by = list(date = as.Date(cut.Date(as.Date(i$validafter, diff --git a/task-6443/run.sh b/task-6443/run.sh new file mode 100755 index 0000000..8ea016e --- /dev/null +++ b/task-6443/run.sh @@ -0,0 +1,3 @@ +#!/bin/bash +javac -d bin -cp lib/descriptor.jar src/CalculatePathSelectionProbabilities.java && java -cp bin:lib/descriptor.jar:lib/commons-codec-1.6.jar:lib/commons-compress-1.4.1.jar CalculatePathSelectionProbabilities + diff --git a/task-6443/src/CalculatePathSelectionProbabilities.java b/task-6443/src/CalculatePathSelectionProbabilities.java index 67bb200..f819d3e 100644 --- a/task-6443/src/CalculatePathSelectionProbabilities.java +++ b/task-6443/src/CalculatePathSelectionProbabilities.java @@ -4,7 +4,6 @@ import java.io.FileWriter; import java.text.SimpleDateFormat; import java.util.ArrayList; import java.util.Arrays; -import java.util.Collections; import java.util.HashMap; import java.util.Iterator; import java.util.List; @@ -24,8 +23,8 @@ import org.torproject.descriptor.RelayNetworkStatusConsensus; import org.torproject.descriptor.ServerDescriptor; /* - * Calculate five path-selection probabilities for relays based on - * consensus weights and advertised bandwidths: + * Calculate path-selection probabilities for relays based on consensus + * weights and advertised bandwidths: * * - advertised_bandwidth_fraction: Relative advertised bandwidth of * this relay compared to the total advertised bandwidth in the @@ -54,6 +53,10 @@ import org.torproject.descriptor.ServerDescriptor; * weights, relay flags, directory ports, and bandwidth weights in the * consensus. Path selection depends on more factors, so that this * probability can only be an approximation. + * + * - exit_probability_advbw: Probability of this relay to be selected for + * the exit position under the assumption that clients would use + * advertised bandwidth for path selection. */ public class CalculatePathSelectionProbabilities { public static void main(String[] args) throws Exception { @@ -99,14 +102,17 @@ public class CalculatePathSelectionProbabilities { bw = new BufferedWriter(new FileWriter("weights.csv")); bw.write("validafter,fingerprint,advertised_bandwidth_fraction," + "consensus_weight_fraction,guard_probability," - + "middle_probability,exit_probability\n"); + + "middle_probability,exit_probability," + + "exit_probability_advbw\n"); } BufferedWriter bw2 = new BufferedWriter(new FileWriter( "cumulated-weights.csv")); - bw2.write("validafter,top_relays,total_exit_probability\n"); + bw2.write("validafter,weight_type,top_relays," + + "total_exit_probability\n"); BufferedWriter bw3 = new BufferedWriter(new FileWriter( "inverse-cumulated-weights.csv")); - bw3.write("validafter,total_exit_probability,top_relays\n"); + bw3.write("validafter,weight_type,total_exit_probability," + + "top_relays\n"); while (descriptorFiles.hasNext()) { DescriptorFile descriptorFile = descriptorFiles.next(); for (Descriptor descriptor : descriptorFile.getDescriptors()) { @@ -155,12 +161,14 @@ public class CalculatePathSelectionProbabilities { consensusWeights = new TreeMap<String, Double>(), guardWeights = new TreeMap<String, Double>(), middleWeights = new TreeMap<String, Double>(), - exitWeights = new TreeMap<String, Double>(); + exitWeights = new TreeMap<String, Double>(), + exitWeightsAdvBw = new TreeMap<String, Double>(); double totalAdvertisedBandwidth = 0.0; double totalConsensusWeight = 0.0; double totalGuardWeight = 0.0; double totalMiddleWeight = 0.0; double totalExitWeight = 0.0; + double totalExitWeightAdvBw = 0.0; for (NetworkStatusEntry relay : consensus.getStatusEntries().values()) { String fingerprint = relay.getFingerprint(); @@ -183,6 +191,7 @@ public class CalculatePathSelectionProbabilities { double guardWeight = (double) relay.getBandwidth(); double middleWeight = (double) relay.getBandwidth(); double exitWeight = (double) relay.getBandwidth(); + double exitWeightAdvBw = advertisedBandwidth; /* Case 1: relay has both Guard and Exit flag and could be * selected for either guard, middle, or exit position. Apply @@ -191,6 +200,7 @@ public class CalculatePathSelectionProbabilities { guardWeight *= wgd; middleWeight *= wmd; exitWeight *= wed; + exitWeightAdvBw *= wed; /* Case 2: relay only has the Guard flag, not the Exit flag. * While, in theory, the relay could also be picked for the exit @@ -203,6 +213,7 @@ public class CalculatePathSelectionProbabilities { guardWeight *= wgg; middleWeight *= wmg; exitWeight = 0.0; + exitWeightAdvBw = 0.0; /* Case 3: relay only has the Exit flag, not the Guard flag. It * cannot be picked for the guard position, so set Wge to 0. @@ -211,6 +222,7 @@ public class CalculatePathSelectionProbabilities { guardWeight = 0.0; middleWeight *= wme; exitWeight *= wee; + exitWeightAdvBw *= wee; /* Case 4: relay has neither Exit nor Guard flag. Similar to * case 2, this relay *could* have a weird exit policy and be @@ -221,6 +233,7 @@ public class CalculatePathSelectionProbabilities { guardWeight = 0.0; middleWeight *= wmm; exitWeight = 0.0; + exitWeightAdvBw = 0.0; } /* Store calculated weights and update totals. */ @@ -229,11 +242,13 @@ public class CalculatePathSelectionProbabilities { guardWeights.put(fingerprint, guardWeight); middleWeights.put(fingerprint, middleWeight); exitWeights.put(fingerprint, exitWeight); + exitWeightsAdvBw.put(fingerprint, exitWeightAdvBw); totalAdvertisedBandwidth += advertisedBandwidth; totalConsensusWeight += consensusWeight; totalGuardWeight += guardWeight; totalMiddleWeight += middleWeight; totalExitWeight += exitWeight; + totalExitWeightAdvBw += exitWeightAdvBw; } /* Write calculated path-selection probabilities to the output @@ -242,7 +257,8 @@ public class CalculatePathSelectionProbabilities { for (NetworkStatusEntry relay : consensus.getStatusEntries().values()) { String fingerprint = relay.getFingerprint(); - bw.write(String.format("%s,%s,%.9f,%.9f,%.9f,%.9f,%.9f%n", + bw.write(String.format("%s,%s,%.9f,%.9f,%.9f,%.9f,%.9f," + + "%.9f%n", validAfter, fingerprint, advertisedBandwidths.get(fingerprint) @@ -250,35 +266,48 @@ public class CalculatePathSelectionProbabilities { consensusWeights.get(fingerprint) / totalConsensusWeight, guardWeights.get(fingerprint) / totalGuardWeight, middleWeights.get(fingerprint) / totalMiddleWeight, - exitWeights.get(fingerprint) / totalExitWeight)); + exitWeights.get(fingerprint) / totalExitWeight, + exitWeightsAdvBw.get(fingerprint) + / totalExitWeightAdvBw)); } } /* Write exit probabilities for top-x relays to the second and * third output files. */ - List<Double> sortedExitWeights = new ArrayList<Double>( - exitWeights.values()); - Collections.sort(sortedExitWeights); - Collections.reverse(sortedExitWeights); - int topRelays = 0; - double totalExitProbability = 0.0; - List<Double> inverseProbabilities = new ArrayList<Double>( - Arrays.asList(new Double[] { 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, - 0.7, 0.8, 0.9 })); - for (double exitWeight : sortedExitWeights) { - topRelays++; - totalExitProbability += exitWeight / totalExitWeight; - if (topRelays <= 50) { - bw2.write(String.format("%s,%d,%.9f%n", validAfter, topRelays, - totalExitProbability)); - } - while (!inverseProbabilities.isEmpty() && - totalExitProbability > inverseProbabilities.get(0)) { - bw3.write(String.format("%s,%.1f,%d%n", validAfter, - inverseProbabilities.remove(0), topRelays)); - } - if (inverseProbabilities.isEmpty() && topRelays > 50) { - break; + String[] weightTypes = new String[] { "consensus weights", + "advertised bandwidth" }; + Double[][] sortedExitWeightsArray = new Double[][] { + exitWeights.values().toArray(new Double[exitWeights.size()]), + exitWeightsAdvBw.values().toArray( + new Double[exitWeightsAdvBw.size()]) }; + double[] totalWeights = new double[] { totalExitWeight, + totalExitWeightAdvBw }; + for (int i = 0; i < weightTypes.length; i++) { + String weightType = weightTypes[i]; + Double[] sortedExitWeights = sortedExitWeightsArray[i]; + double totalWeight = totalWeights[i]; + Arrays.sort(sortedExitWeights); + int topRelays = 0; + double totalExitProbability = 0.0; + List<Double> inverseProbabilities = new ArrayList<Double>( + Arrays.asList(new Double[] { 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, + 0.7, 0.8, 0.9 })); + for (int j = sortedExitWeights.length - 1; j >= 0; j--) { + double exitWeight = sortedExitWeights[j]; + topRelays++; + totalExitProbability += exitWeight / totalWeight; + if (topRelays <= 50) { + bw2.write(String.format("%s,%s,%d,%.9f%n", validAfter, + weightType, topRelays, totalExitProbability)); + } + while (!inverseProbabilities.isEmpty() && + totalExitProbability > inverseProbabilities.get(0)) { + bw3.write(String.format("%s,%s,%.1f,%d%n", validAfter, + weightType, inverseProbabilities.remove(0), topRelays)); + } + if (inverseProbabilities.isEmpty() && topRelays > 50) { + break; + } } } }