- tor-commits - lists.torproject.org

[arm/master] Support logging of arm events.
by atagar＠torproject.org 04 Jul '11

04 Jul '11

commit d5556ad4ce0c43d0aca1b287ad59c3a90bd923c5 Author: Kamran Riaz Khan <krkhan(a)inspirated.com> Date: Mon Jun 20 16:55:05 2011 +0500 Support logging of arm events. --- src/gui/__init__.py | 2 +- src/gui/arm.xml | 8 +------ src/gui/controller.py | 14 +++++++----- src/gui/logPanel.py | 56 +++++++++++++++++++++++++++++++++++++++++++++++++ 4 files changed, 66 insertions(+), 14 deletions(-) diff --git a/src/gui/__init__.py b/src/gui/__init__.py index f461b3e..b700273 100644 --- a/src/gui/__init__.py +++ b/src/gui/__init__.py @@ -2,5 +2,5 @@ Panels, popups, and handlers comprising the arm user interface. """ -__all__ = ["controller"] +__all__ = ["controller", "logPanel"] diff --git a/src/gui/arm.xml b/src/gui/arm.xml index 11f5c63..8cbb924 100644 --- a/src/gui/arm.xml +++ b/src/gui/arm.xml @@ -692,11 +692,5 @@ each direction. (Default: 0) </property> </object> </child> </object> - <object class="GtkTextBuffer" id="textbuffer_log"> - <property name="text" translatable="yes">16:09:20 [NOTICE] Bootstrapped 90%: Establishing a Tor circuit. -16:09:23 [NOTICE] Tor has successfully opened a circuit. Looks like client functionality is working. -16:09:23 [NOTICE] Tor has successfully opened a circuit. Looks like client functionality is working. -16:09:24 [NOTICE] Bootstrapped 100%: Done. -</property> - </object> + <object class="GtkTextBuffer" id="textbuffer_log"/> </interface> diff --git a/src/gui/controller.py b/src/gui/controller.py index 4da82c9..8f27df4 100644 --- a/src/gui/controller.py +++ b/src/gui/controller.py @@ -1,7 +1,8 @@ import gobject import gtk -from util import torTools +from util import log, torTools +from gui import logPanel from gui.graphing import bandwidthStats gobject.threads_init() @@ -17,14 +18,15 @@ class GuiController: self.bwStats = bandwidthStats.BandwidthStats(self.builder) self.bwStats.pack_widgets() + self.logPanel = logPanel.LogPanel(self.builder) + self.logPanel.pack_widgets() + + log.log(log.DEBUG, "Hello World!") + log.log(log.ERR, "Hello Again!") + def run(self): window = self.builder.get_object('window_main') - textbuffer = self.builder.get_object('textbuffer_log') - conn = torTools.getConn() - torPid = conn.getMyPid() - textbuffer.set_text("Tor pid: %s" % torPid) - window.show_all() gtk.main() diff --git a/src/gui/logPanel.py b/src/gui/logPanel.py new file mode 100644 index 0000000..174ed64 --- /dev/null +++ b/src/gui/logPanel.py @@ -0,0 +1,56 @@ +""" +Base class for implementing graphing functionality. +""" + +import random +import sys + +from collections import deque + +import gobject +import gtk + +from TorCtl import TorCtl +from util import log, uiTools, torTools + +from cli.logPanel import RUNLEVEL_EVENT_COLOR, LogEntry + +class LogPanel: + def __init__(self, builder): + self.builder = builder + + self.msgLog = deque() + + log.LOG_LOCK.acquire() + try: + armRunlevels = [log.DEBUG, log.INFO, log.NOTICE, log.WARN, log.ERR] + log.addListeners(armRunlevels, self._register_arm_event) + finally: + log.LOG_LOCK.release() + + textbuffer = self.builder.get_object('textbuffer_log') + + for color in RUNLEVEL_EVENT_COLOR.values(): + textbuffer.create_tag(color, foreground=color) + + gobject.timeout_add(1000, self.print_log) + + def print_log(self): + textbuffer = self.builder.get_object('textbuffer_log') + start, end = textbuffer.get_bounds() + textbuffer.delete(start, end) + + for entry in self.msgLog: + iter = textbuffer.get_iter_at_mark(textbuffer.get_insert()) + textbuffer.insert_with_tags_by_name(iter, entry.getDisplayMessage() + "\n", entry.color) + + def register_event(self, event): + self.msgLog.appendleft(event) + + def pack_widgets(self): + pass + + def _register_arm_event(self, level, msg, eventTime): + eventColor = RUNLEVEL_EVENT_COLOR[level] + self.register_event(LogEntry(eventTime, "ARM_%s" % level, msg, eventColor)) +

1 0

[arm/master] Use a tree view for prettifying log entries.
by atagar＠torproject.org 04 Jul '11

04 Jul '11

commit c9ac18befb91178fdcd4fb86c9fcbd503396c889 Author: Kamran Riaz Khan <krkhan(a)inspirated.com> Date: Mon Jun 20 18:14:30 2011 +0500 Use a tree view for prettifying log entries. (In future, this can prove to be helpful by being sortable.) --- src/gui/arm.xml | 52 +++++++++++++++++++++++++++++++++++++++++++++++++- src/gui/logPanel.py | 21 +++++++------------ 2 files changed, 58 insertions(+), 15 deletions(-) diff --git a/src/gui/arm.xml b/src/gui/arm.xml index 8cbb924..f067542 100644 --- a/src/gui/arm.xml +++ b/src/gui/arm.xml @@ -134,6 +134,18 @@ </row> </data> </object> + <object class="GtkListStore" id="liststore_log"> + <columns> +  + <column type="gchararray"/> +  + <column type="gchararray"/> +  + <column type="gchararray"/> +  + <column type="gchararray"/> + </columns> + </object> <object class="GtkWindow" id="window_main"> <property name="title" translatable="yes">arm</property> <property name="default_width">640</property> @@ -672,10 +684,46 @@ each direction. (Default: 0) </property> <property name="hscrollbar_policy">automatic</property> <property name="vscrollbar_policy">automatic</property> <child> - <object class="GtkTextView" id="textview_log"> + <object class="GtkTreeView" id="treeview_log"> <property name="visible">True</property> <property name="can_focus">True</property> - <property name="buffer">textbuffer_log</property> + <property name="model">liststore_log</property> + <child> + <object class="GtkTreeViewColumn" id="treeviewcolumn_log_timestamp"> + <property name="title">Time</property> + <child> + <object class="GtkCellRendererText" id="cellrenderertext_log_timestamp"/> + <attributes> + <attribute name="foreground">3</attribute> + <attribute name="markup">0</attribute> + </attributes> + </child> + </object> + </child> + <child> + <object class="GtkTreeViewColumn" id="treeviewcolumn_log_type"> + <property name="title">Type</property> + <child> + <object class="GtkCellRendererText" id="cellrenderertext_log_type"/> + <attributes> + <attribute name="foreground">3</attribute> + <attribute name="markup">1</attribute> + </attributes> + </child> + </object> + </child> + <child> + <object class="GtkTreeViewColumn" id="treeviewcolumn_msg"> + <property name="title">Message</property> + <child> + <object class="GtkCellRendererText" id="cellrenderertext_log_msg"/> + <attributes> + <attribute name="foreground">3</attribute> + <attribute name="markup">2</attribute> + </attributes> + </child> + </object> + </child> </object> </child> </object> diff --git a/src/gui/logPanel.py b/src/gui/logPanel.py index 174ed64..bacc6f2 100644 --- a/src/gui/logPanel.py +++ b/src/gui/logPanel.py @@ -4,6 +4,7 @@ Base class for implementing graphing functionality. import random import sys +import time from collections import deque @@ -28,24 +29,18 @@ class LogPanel: finally: log.LOG_LOCK.release() - textbuffer = self.builder.get_object('textbuffer_log') - - for color in RUNLEVEL_EVENT_COLOR.values(): - textbuffer.create_tag(color, foreground=color) - - gobject.timeout_add(1000, self.print_log) - - def print_log(self): - textbuffer = self.builder.get_object('textbuffer_log') - start, end = textbuffer.get_bounds() - textbuffer.delete(start, end) + def fill_log(self): + liststore = self.builder.get_object('liststore_log') + liststore.clear() for entry in self.msgLog: - iter = textbuffer.get_iter_at_mark(textbuffer.get_insert()) - textbuffer.insert_with_tags_by_name(iter, entry.getDisplayMessage() + "\n", entry.color) + timeLabel = time.strftime('%H:%M:%S', time.localtime(entry.timestamp)) + row = (timeLabel, entry.type, entry.msg, entry.color) + liststore.append(row) def register_event(self, event): self.msgLog.appendleft(event) + self.fill_log() def pack_widgets(self): pass

1 0

[arm/master] Allow user to sort log entries in preferred order.
by atagar＠torproject.org 04 Jul '11

04 Jul '11

commit e5ae0d0a95b2739e3e1ec281eeab4f76d779087a Author: Kamran Riaz Khan <krkhan(a)inspirated.com> Date: Tue Jun 21 16:38:18 2011 +0500 Allow user to sort log entries in preferred order. --- src/gui/arm.xml | 18 +++++++++++------- src/gui/controller.py | 11 +++++++++-- src/gui/logPanel.py | 13 +++++++++++-- 3 files changed, 31 insertions(+), 11 deletions(-) diff --git a/src/gui/arm.xml b/src/gui/arm.xml index f067542..1e3681c 100644 --- a/src/gui/arm.xml +++ b/src/gui/arm.xml @@ -136,6 +136,8 @@ </object> <object class="GtkListStore" id="liststore_log"> <columns> +  + <column type="gulong"/>  <column type="gchararray"/>  @@ -691,11 +693,14 @@ each direction. (Default: 0) </property> <child> <object class="GtkTreeViewColumn" id="treeviewcolumn_log_timestamp"> <property name="title">Time</property> + <property name="sort_indicator">True</property> + <property name="sort_order">descending</property> + <property name="sort_column_id">1</property> <child> <object class="GtkCellRendererText" id="cellrenderertext_log_timestamp"/> <attributes> - <attribute name="foreground">3</attribute> - <attribute name="markup">0</attribute> + <attribute name="foreground">4</attribute> + <attribute name="markup">1</attribute> </attributes> </child> </object> @@ -706,8 +711,8 @@ each direction. (Default: 0) </property> <child> <object class="GtkCellRendererText" id="cellrenderertext_log_type"/> <attributes> - <attribute name="foreground">3</attribute> - <attribute name="markup">1</attribute> + <attribute name="foreground">4</attribute> + <attribute name="markup">2</attribute> </attributes> </child> </object> @@ -718,8 +723,8 @@ each direction. (Default: 0) </property> <child> <object class="GtkCellRendererText" id="cellrenderertext_log_msg"/> <attributes> - <attribute name="foreground">3</attribute> - <attribute name="markup">2</attribute> + <attribute name="foreground">4</attribute> + <attribute name="markup">3</attribute> </attributes> </child> </object> @@ -740,5 +745,4 @@ each direction. (Default: 0) </property> </object> </child> </object> - <object class="GtkTextBuffer" id="textbuffer_log"/> </interface> diff --git a/src/gui/controller.py b/src/gui/controller.py index 8f27df4..c5c8767 100644 --- a/src/gui/controller.py +++ b/src/gui/controller.py @@ -1,6 +1,9 @@ import gobject import gtk +import thread +import time + from util import log, torTools from gui import logPanel from gui.graphing import bandwidthStats @@ -21,8 +24,12 @@ class GuiController: self.logPanel = logPanel.LogPanel(self.builder) self.logPanel.pack_widgets() - log.log(log.DEBUG, "Hello World!") - log.log(log.ERR, "Hello Again!") + def random_entries(): + while True: + log.log(log.DEBUG, "Hello World at %s" % time.asctime(time.localtime())) + time.sleep(5) + + thread.start_new_thread(random_entries, ()) def run(self): window = self.builder.get_object('window_main') diff --git a/src/gui/logPanel.py b/src/gui/logPanel.py index bacc6f2..7197178 100644 --- a/src/gui/logPanel.py +++ b/src/gui/logPanel.py @@ -35,7 +35,7 @@ class LogPanel: for entry in self.msgLog: timeLabel = time.strftime('%H:%M:%S', time.localtime(entry.timestamp)) - row = (timeLabel, entry.type, entry.msg, entry.color) + row = (long(entry.timestamp), timeLabel, entry.type, entry.msg, entry.color) liststore.append(row) def register_event(self, event): @@ -43,7 +43,16 @@ class LogPanel: self.fill_log() def pack_widgets(self): - pass + liststore = self.builder.get_object('liststore_log') + + liststore.set_sort_func(1, self._compare_rows) + liststore.set_sort_column_id(1, gtk.SORT_DESCENDING) + + def _compare_rows(self, treemodel, iter1, iter2, data=None): + timestamp_raw1 = treemodel.get(iter1, 0) + timestamp_raw2 = treemodel.get(iter2, 0) + + return cmp(timestamp_raw1, timestamp_raw2) def _register_arm_event(self, level, msg, eventTime): eventColor = RUNLEVEL_EVENT_COLOR[level]

1 0

[arm/master] Connect a TorEventObserver instance with LogPanel.
by atagar＠torproject.org 04 Jul '11

04 Jul '11

commit 4ea211ffc54b4c32b9d7cc90e4b395523145484b Author: Kamran Riaz Khan <krkhan(a)inspirated.com> Date: Wed Jun 22 01:15:50 2011 +0500 Connect a TorEventObserver instance with LogPanel. --- src/gui/controller.py | 7 +------ src/gui/logPanel.py | 13 ++++++------- 2 files changed, 7 insertions(+), 13 deletions(-) diff --git a/src/gui/controller.py b/src/gui/controller.py index c5c8767..090cc31 100644 --- a/src/gui/controller.py +++ b/src/gui/controller.py @@ -24,12 +24,7 @@ class GuiController: self.logPanel = logPanel.LogPanel(self.builder) self.logPanel.pack_widgets() - def random_entries(): - while True: - log.log(log.DEBUG, "Hello World at %s" % time.asctime(time.localtime())) - time.sleep(5) - - thread.start_new_thread(random_entries, ()) + log.log(log.DEBUG, "Hello world!") def run(self): window = self.builder.get_object('window_main') diff --git a/src/gui/logPanel.py b/src/gui/logPanel.py index 7197178..78b218a 100644 --- a/src/gui/logPanel.py +++ b/src/gui/logPanel.py @@ -14,7 +14,7 @@ import gtk from TorCtl import TorCtl from util import log, uiTools, torTools -from cli.logPanel import RUNLEVEL_EVENT_COLOR, LogEntry +from cli.logPanel import RUNLEVEL_EVENT_COLOR, LogEntry, TorEventObserver class LogPanel: def __init__(self, builder): @@ -22,12 +22,11 @@ class LogPanel: self.msgLog = deque() - log.LOG_LOCK.acquire() - try: - armRunlevels = [log.DEBUG, log.INFO, log.NOTICE, log.WARN, log.ERR] - log.addListeners(armRunlevels, self._register_arm_event) - finally: - log.LOG_LOCK.release() + armRunlevels = [log.DEBUG, log.INFO, log.NOTICE, log.WARN, log.ERR] + log.addListeners(armRunlevels, self._register_arm_event) + + conn = torTools.getConn() + conn.addEventListener(TorEventObserver(self.register_event)) def fill_log(self): liststore = self.builder.get_object('liststore_log')

1 0

[arm/master] Migrate CLI code for fetching backlogs as well as TorCtl events.
by atagar＠torproject.org 04 Jul '11

04 Jul '11

commit 7b6d513582ab48619c3ee27bd1baabbfb9b9e9f8 Author: Kamran Riaz Khan <krkhan(a)inspirated.com> Date: Sat Jun 25 14:58:34 2011 +0500 Migrate CLI code for fetching backlogs as well as TorCtl events. --- src/gui/logPanel.py | 56 ++++++++++++++++++++++++++++++++++++++++++-------- 1 files changed, 47 insertions(+), 9 deletions(-) diff --git a/src/gui/logPanel.py b/src/gui/logPanel.py index 78b218a..ab8eb4d 100644 --- a/src/gui/logPanel.py +++ b/src/gui/logPanel.py @@ -14,19 +14,59 @@ import gtk from TorCtl import TorCtl from util import log, uiTools, torTools -from cli.logPanel import RUNLEVEL_EVENT_COLOR, LogEntry, TorEventObserver +from cli.logPanel import (expandEvents, setEventListening, getLogFileEntries, + LogEntry, TorEventObserver, + DEFAULT_CONFIG, RUNLEVEL_EVENT_COLOR) + +STARTUP_EVENTS = 'N3' class LogPanel: def __init__(self, builder): self.builder = builder + self._config = dict(DEFAULT_CONFIG) self.msgLog = deque() + self.loggedEvents = setEventListening(expandEvents(STARTUP_EVENTS)) + + torEventBacklog = deque() + if self._config["features.log.prepopulate"]: + setRunlevels = list(set.intersection(set(self.loggedEvents), set(log.Runlevel.values()))) + readLimit = self._config["features.log.prepopulateReadLimit"] + addLimit = self._config["cache.logPanel.size"] + torEventBacklog = deque(getLogFileEntries(setRunlevels, readLimit, addLimit, self._config)) armRunlevels = [log.DEBUG, log.INFO, log.NOTICE, log.WARN, log.ERR] log.addListeners(armRunlevels, self._register_arm_event) + setRunlevels = [] + for i in range(len(armRunlevels)): + if "ARM_" + log.Runlevel.values()[i] in self.loggedEvents: + setRunlevels.append(armRunlevels[i]) + + armEventBacklog = deque() + for level, msg, eventTime in log._getEntries(setRunlevels): + armEventEntry = LogEntry(eventTime, "ARM_" + level, msg, RUNLEVEL_EVENT_COLOR[level]) + armEventBacklog.appendleft(armEventEntry) + + while armEventBacklog or torEventBacklog: + if not armEventBacklog: + self.msgLog.append(torEventBacklog.popleft()) + elif not torEventBacklog: + self.msgLog.append(armEventBacklog.popleft()) + elif armEventBacklog[0].timestamp < torEventBacklog[0].timestamp: + self.msgLog.append(torEventBacklog.popleft()) + else: + self.msgLog.append(armEventBacklog.popleft()) + conn = torTools.getConn() conn.addEventListener(TorEventObserver(self.register_event)) + conn.addTorCtlListener(self._register_torctl_event) + + def pack_widgets(self): + liststore = self.builder.get_object('liststore_log') + + liststore.set_sort_func(1, self._compare_rows) + liststore.set_sort_column_id(1, gtk.SORT_DESCENDING) def fill_log(self): liststore = self.builder.get_object('liststore_log') @@ -41,11 +81,13 @@ class LogPanel: self.msgLog.appendleft(event) self.fill_log() - def pack_widgets(self): - liststore = self.builder.get_object('liststore_log') + def _register_arm_event(self, level, msg, eventTime): + eventColor = RUNLEVEL_EVENT_COLOR[level] + self.register_event(LogEntry(eventTime, "ARM_%s" % level, msg, eventColor)) - liststore.set_sort_func(1, self._compare_rows) - liststore.set_sort_column_id(1, gtk.SORT_DESCENDING) + def _register_torctl_event(self, level, msg): + eventColor = RUNLEVEL_EVENT_COLOR[level] + self.register_event(LogEntry(time.time(), "TORCTL_%s" % level, msg, eventColor)) def _compare_rows(self, treemodel, iter1, iter2, data=None): timestamp_raw1 = treemodel.get(iter1, 0) @@ -53,7 +95,3 @@ class LogPanel: return cmp(timestamp_raw1, timestamp_raw2) - def _register_arm_event(self, level, msg, eventTime): - eventColor = RUNLEVEL_EVENT_COLOR[level] - self.register_event(LogEntry(eventTime, "ARM_%s" % level, msg, eventColor)) -

1 0

[arm/master] Remove debug log statement and update log panel regularly via gobject.
by atagar＠torproject.org 04 Jul '11

04 Jul '11

commit 01529c340943a2b82cb6b98902e38cd10b4fcb86 Author: Kamran Riaz Khan <krkhan(a)inspirated.com> Date: Sat Jun 25 15:06:55 2011 +0500 Remove debug log statement and update log panel regularly via gobject. --- src/gui/controller.py | 2 -- src/gui/logPanel.py | 5 ++++- 2 files changed, 4 insertions(+), 3 deletions(-) diff --git a/src/gui/controller.py b/src/gui/controller.py index 090cc31..1c173af 100644 --- a/src/gui/controller.py +++ b/src/gui/controller.py @@ -24,8 +24,6 @@ class GuiController: self.logPanel = logPanel.LogPanel(self.builder) self.logPanel.pack_widgets() - log.log(log.DEBUG, "Hello world!") - def run(self): window = self.builder.get_object('window_main') diff --git a/src/gui/logPanel.py b/src/gui/logPanel.py index ab8eb4d..0a00137 100644 --- a/src/gui/logPanel.py +++ b/src/gui/logPanel.py @@ -62,6 +62,8 @@ class LogPanel: conn.addEventListener(TorEventObserver(self.register_event)) conn.addTorCtlListener(self._register_torctl_event) + gobject.timeout_add(1000, self.fill_log) + def pack_widgets(self): liststore = self.builder.get_object('liststore_log') @@ -77,9 +79,10 @@ class LogPanel: row = (long(entry.timestamp), timeLabel, entry.type, entry.msg, entry.color) liststore.append(row) + return True + def register_event(self, event): self.msgLog.appendleft(event) - self.fill_log() def _register_arm_event(self, level, msg, eventTime): eventColor = RUNLEVEL_EVENT_COLOR[level]

1 0

[metrics-tasks/master] Describe the simulations in more detail.
by karsten＠torproject.org 04 Jul '11

04 Jul '11

commit 2308929611063d6a5fb97348a564b952e8e39f90 Author: Karsten Loesing <karsten.loesing(a)gmx.net> Date: Mon May 30 12:49:06 2011 +0200 Describe the simulations in more detail. --- task-2911/README | 95 +++++++++++++++++++- .../wfu-sim/SimulateWeightedFractionalUptime.java | 4 + 2 files changed, 97 insertions(+), 2 deletions(-) diff --git a/task-2911/README b/task-2911/README index bcefa2d..686de7a 100644 --- a/task-2911/README +++ b/task-2911/README @@ -4,7 +4,76 @@ Tech report: An Analysis of Tor Relay Stability Simulation of MTBF requirements ------------------------------- -Change to the MTBF simulation directory: +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/ @@ -63,7 +132,29 @@ directory to include it in the report: Simulation of WFU requirements ------------------------------ -Change to the WFU simulation directory: +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. + +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/ diff --git a/task-2911/wfu-sim/SimulateWeightedFractionalUptime.java b/task-2911/wfu-sim/SimulateWeightedFractionalUptime.java index 6a2d7a9..d803057 100644 --- a/task-2911/wfu-sim/SimulateWeightedFractionalUptime.java +++ b/task-2911/wfu-sim/SimulateWeightedFractionalUptime.java @@ -114,6 +114,10 @@ public class SimulateWeightedFractionalUptime { /* 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 });

1 0

[metrics-tasks/master] Merge branch 'task-2911'
by karsten＠torproject.org 04 Jul '11

04 Jul '11

commit f47735e2714a76af3d5c49f1687bdcf9dde0a802 Merge: 4d17699 88926c8 Author: Karsten Loesing <karsten.loesing(a)gmx.net> Date: Mon Jul 4 09:45:13 2011 +0200 Merge branch 'task-2911' task-2911/.gitignore | 9 + task-2911/README | 143 ++++++ task-2911/SimulateStableGuard.java | 842 ++++++++++++++++++++++++++++++++++++ task-2911/report.bib | 31 ++ task-2911/report.tex | 534 +++++++++++++++++++++++ task-2911/stability.R | 301 +++++++++++++ 6 files changed, 1860 insertions(+), 0 deletions(-)

1 0

[metrics-tasks/master] Update relay stability tech report sources.
by karsten＠torproject.org 04 Jul '11

04 Jul '11

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) -

1 0

[metrics-tasks/master] Add simulation code and LaTeX sources of #2911 draft.
by karsten＠torproject.org 04 Jul '11

04 Jul '11

commit cff86510fd86e73a2f66f21ac8b47068d187d972 Author: Karsten Loesing <karsten.loesing(a)gmx.net> Date: Mon May 30 11:16:10 2011 +0200 Add simulation code and LaTeX sources of #2911 draft. --- task-2911/.gitignore | 9 + task-2911/README | 105 ++++++ .../mtbf-sim/SimulateMeanTimeBetweenFailure.java | 351 ++++++++++++++++++++ task-2911/mtbf-sim/mtbf-sim.R | 73 ++++ task-2911/report.tex | 295 ++++++++++++++++ .../wfu-sim/SimulateWeightedFractionalUptime.java | 314 +++++++++++++++++ task-2911/wfu-sim/wfu-sim.R | 57 ++++ 7 files changed, 1204 insertions(+), 0 deletions(-) diff --git a/task-2911/.gitignore b/task-2911/.gitignore new file mode 100644 index 0000000..d2480c1 --- /dev/null +++ b/task-2911/.gitignore @@ -0,0 +1,9 @@ +*.class +mtbf-sim/tunf/ +wfu-sim/fwfu/ +wfu-sim/consensuses/ +*.csv +*.aux +*.log +*.pdf + diff --git a/task-2911/README b/task-2911/README new file mode 100644 index 0000000..bcefa2d --- /dev/null +++ b/task-2911/README @@ -0,0 +1,105 @@ +Tech report: An Analysis of Tor Relay Stability +=============================================== + +Simulation of MTBF requirements +------------------------------- + +Change 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: + + 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 + 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 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 ../ + + +Simulation of WFU requirements +------------------------------ + +Change 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: + + $ pdflatex report.tex + diff --git a/task-2911/mtbf-sim/SimulateMeanTimeBetweenFailure.java b/task-2911/mtbf-sim/SimulateMeanTimeBetweenFailure.java new file mode 100644 index 0000000..cd73f82 --- /dev/null +++ b/task-2911/mtbf-sim/SimulateMeanTimeBetweenFailure.java @@ -0,0 +1,351 @@ +/** + * 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 new file mode 100644 index 0000000..a630406 --- /dev/null +++ b/task-2911/mtbf-sim/mtbf-sim.R @@ -0,0 +1,73 @@ +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.tex b/task-2911/report.tex new file mode 100644 index 0000000..4dc6ab9 --- /dev/null +++ b/task-2911/report.tex @@ -0,0 +1,295 @@ +\documentclass{article} +\usepackage{url} +\usepackage[pdftex]{graphicx} +\usepackage{graphics} +\usepackage{color} +\begin{document} +\title{An Analysis of Tor Relay Stability\\(DRAFT)} +\author{Karsten Loesing\\{\tt karsten(a)torproject.org}} + +\maketitle + +\section{Introduction} + +The Tor network consists of 2,200 relays and 600 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} +\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. +\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. +\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 +\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.} + +\section{Choosing relays for long-lived streams} +\label{sec:mtbf-sim} + +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. +If only a single relay in the circuit fails, the stream collapses and a +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 +until next failure}. +When running a simulation we determine the time until 10~\% of the +``stable'' relays have failed. +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. + +\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} +\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} +} + +\section{Picking stable entry guards} + +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 +weeks. +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)}. +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. +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. + +\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} +\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. +} + +\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. + +\end{document} + diff --git a/task-2911/wfu-sim/SimulateWeightedFractionalUptime.java b/task-2911/wfu-sim/SimulateWeightedFractionalUptime.java new file mode 100644 index 0000000..6a2d7a9 --- /dev/null +++ b/task-2911/wfu-sim/SimulateWeightedFractionalUptime.java @@ -0,0 +1,314 @@ +/** + * 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. */ + 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 new file mode 100644 index 0000000..149ce6d --- /dev/null +++ b/task-2911/wfu-sim/wfu-sim.R @@ -0,0 +1,57 @@ +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) +

1 0