[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]

[tor-commits] [bridgedb/master] 5482 - Add BridgeHistory record class



commit afa94abf08fdb3989f8054859f2f239d060b10f8
Author: aagbsn <aagbsn@xxxxxxxx>
Date:   Mon Oct 29 09:14:01 2012 -0700

    5482 - Add BridgeHistory record class
    
    Adds a new table BridgeHistory and accompanying record class to
    help bridgedb track bridge stability over time.
---
 lib/bridgedb/Stability.py |  229 +++++++++++++++++++++++++++++++++++++++++++++
 1 files changed, 229 insertions(+), 0 deletions(-)

diff --git a/lib/bridgedb/Stability.py b/lib/bridgedb/Stability.py
new file mode 100644
index 0000000..0c2a288
--- /dev/null
+++ b/lib/bridgedb/Stability.py
@@ -0,0 +1,229 @@
+"""
+This module provides functionality for tracking bridge stability metrics, using
+the model introduced in [1] and implemented in [2].
+
+[1] Karsten Loesing, An Analysis of Tor Bridge Stability. Technical Report.
+The Tor Project, October 2011.
+https://metrics.torproject.org/papers/bridge-stability-2011-10-31.pdf
+
+[2] https://gitweb.torproject.org/metrics-tasks/task-4255/SimulateBridgeStability.java
+"""
+import logging
+import bridgedb.Storage
+
+# tunables 
+weighting_factor = long(19)/long(20)
+discountIntervalMillis = long(60*60*12*1000)
+
+class BridgeHistory(object):
+    """ Record Class that tracks a single Bridge
+    The fields stored are:
+
+    fingerprint, ip, port, weightedUptime, weightedTime, weightedRunLength,
+    totalRunWeights, lastSeenWithDifferentAddressAndPort,
+    lastSeenWithThisAddressAndPort, lastDiscountedHistoryValues.
+
+    fingerprint         The Bridge Fingerprint (unicode)
+    ip                  The Bridge IP (unicode)
+    port                The Bridge orport (integer)
+
+    weightedUptime      Weighted uptime in seconds (long int)
+    weightedTime        Weighted time in seconds (long int)
+    weightedRunLength   Weighted run length of previous addresses or ports in
+                        seconds. (long int)
+    totalRunWeights     Total run weights of previously used addresses or
+                        ports. (float)
+
+    lastSeenWithDifferentAddressAndPort
+        Timestamp in milliseconds when this
+        bridge was last seen with a different address or port. (long int)
+
+    lastSeenWithThisAddressAndPort
+        Timestamp in milliseconds when this bridge was last seen
+        with this address and port. (long int)
+
+    lastDiscountedHistoryValues:
+        Timestamp in milliseconds when this bridge was last discounted. (long int)
+    """
+    def __init__(self, fingerprint, ip, port,
+            weightedUptime, weightedTime, weightedRunLength, totalRunWeights,
+            lastSeenWithDifferentAddressAndPort, lastSeenWithThisAddressAndPort,
+            lastDiscountedHistoryValues=None):
+        self.fingerprint = fingerprint
+        self.ip = ip 
+        self.port = port
+        self.weightedUptime = long(weightedUptime)
+        self.weightedTime = long(weightedTime)
+        self.weightedRunLength = float(weightedRunLength)
+        self.totalRunWeights = float(totalRunWeights)
+        self.lastSeenWithDifferentAddressAndPort = \
+                long(lastSeenWithDifferentAddressAndPort)
+        self.lastSeenWithThisAddressAndPort = long(lastSeenWithThisAddressAndPort)
+        if lastDiscountedHistoryValues:
+            self.lastDiscountedHistoryValues = long(lastDiscountedHistoryValues)
+        else:
+            self.lastDiscountedHistoryValues = long(lastSeenWithThisAddressAndPort)
+
+    def discountWeightedFractionalUptimeAndWeightedTime(self, discountUntilMillis):
+        """ discount weighted times """
+        rounds = self.numDiscountRounds(discountUntilMillis)
+        if rounds > 0:
+            discount = lambda x: (weighting_factor**rounds)*x
+            self.weightedUptime = discount(self.weightedUptime)
+            self.weightedTime = discount(self.weightedTime)
+            self.weightedRunLength = discount(self.weightedRunLength)
+            self.totalRunWeights = discount(self.totalRunWeights)
+
+            self.lastDiscountedHistoryValues += discountIntervalMillis * rounds
+        return rounds
+
+    def numDiscountRounds(self, discountUntilMillis):
+        """ return the number of rounds of discounting needed to bring this
+        history element current """
+              
+        result = discountUntilMillis - self.lastDiscountedHistoryValues
+        result = int(result/discountIntervalMillis)
+        return max(result,0)
+
+    @property
+    def weightedFractionalUptime(self):
+        """Weighted Fractional Uptime"""
+        return long(10000) * self.weightedUptime / self.weightedTime
+
+    @property
+    def tosa(self):
+        """the Time On Same Address (TOSA)"""
+        return ( self.lastSeenWithThisAddressAndPort - \
+                    self.lastSeenWithDifferentAddressAndPort ) / 1000
+
+    @property
+    def familiar(self):
+        """
+        A bridge is 'familiar' if 1/8 of all active bridges have appeared
+        more recently than it, or if it has been around for a Weighted Time of 8 days.
+        """
+        # if this bridge has been around longer than 8 days
+        if self.weightedTime >= long(8 * 24 * 60 * 60):
+            return True
+
+        # return True if self.weightedTime is greater than the weightedTime
+        # of the > bottom 1/8 all bridges, sorted by weightedTime
+        db = bridgedb.Storage.getDB()
+        allWeightedTimes = [ bh.weightedTime for bh in db.getAllBridgeHistory()]
+        numBridges = len(allWeightedTimes)
+        logging.debug("Got %d weightedTimes", numBridges)
+        allWeightedTimes.sort(lambda x,y: cmp(x.weightedTime, y.weightedTime))
+        if self.weighedTime > allWeighedTimes[numBridges/8].weightedTime:
+            return True
+        return False
+
+    @property
+    def wmtbac(self):
+        """Weighted Mean Time Between Address Change"""
+        totalRunLength = self.weightedRunLength + \
+                ((self.lastSeenWithThisAddressAndPort -
+                self.lastSeenWithDifferentAddressAndPort) / long(1000))
+
+        totalWeights = self.totalRunWeights + 1.0
+        if totalWeights <  0.0001: return long(0)
+        assert(isinstance(long,totalRunLength))
+        assert(isinstance(long,totalWeights))
+        return totalRunlength / totalWeights
+
+def addOrUpdateBridgeHistory(bridge, timestamp):
+    db = bridgedb.Storage.getDB()
+    bhe = db.getBridgeHistory(bridge.fingerprint)
+    if not bhe:
+        # This is the first status, assume 60 minutes.
+        secondsSinceLastStatusPublication = long(60*60)
+        lastSeenWithDifferentAddressAndPort = timestamp * long(1000)
+        lastSeenWithThisAddressAndPort = timestamp * long(1000)
+    
+        bhe = BridgeHistory(
+                bridge.fingerprint, bridge.ip, bridge.orport, 
+                0,#weightedUptime
+                0,#weightedTime
+                0,#weightedRunLength
+                0,# totalRunWeights
+                lastSeenWithDifferentAddressAndPort, # first timestamnp
+                lastSeenWithThisAddressAndPort
+                )
+    
+    # Calculate the seconds since the last parsed status.  If this is
+    # the first status or we haven't seen a status for more than 60
+    # minutes, assume 60 minutes.
+    statusPublicationMillis = long(timestamp * 1000)
+    if (statusPublicationMillis - bhe.lastSeenWithThisAddressAndPort) > 60*60*1000:
+        secondsSinceLastStatusPublication = long(60*60)
+    # otherwise, roll with it
+    else:
+        secondsSinceLastStatusPublication = \
+                (statusPublicationMillis - bhe.lastSeenWithThisAddressAndPort)/1000
+    if statusPublicationMillis - bhe.lastSeenWithThisAddressAndPort < 0:
+        # old descriptor, bail
+        logging.warn("Received old descriptor for bridge %s with timestamp %d",
+                bhe.fingerprint, statusPublicationMillis/1000)
+        return bhe
+    
+    # iterate over all known bridges and apply weighting factor
+    discountAndPruneBridgeHistories(statusPublicationMillis)
+    
+    # add or update the descriptor in history
+    db.updateIntoBridgeHistory(bhe)
+    bhe = None
+    
+    # Increment total weighted time for all bridges by seconds since the last
+    # status was published. Note, capped at 1 hour
+    for bh in db.getAllBridgeHistory():
+        bh.weightedTime += secondsSinceLastStatusPublication
+        db.updateIntoBridgeHistory(bh)
+
+    # For Running Bridges only:
+    # compare the stored history against the descriptor and see if the
+    # bridge has changed its address or port
+    bhe = db.getBridgeHistory(bridge.fingerprint)
+    if not bridge.running:
+        log.notice("%s is not running" % bridge.fingerprint)
+        return bhe
+
+    # Parse the descriptor and see if the address or port changed
+    # If so, store the weighted run time
+    if bridge.orport != bhe.port or bridge.ip != bhe.ip:
+        bhe.totalRunWeights += 1.0;
+        bhe.weightedRunLength += bhe.tosa
+        bhe.lastSeenWithDifferentAddressAndPort =\
+                bhe.lastSeenWithThisAddressAndPort
+
+    # Regardless of whether the bridge is new, kept or changed
+    # its address and port, raise its WFU times and note its
+    # current address and port, and that we saw it using them.
+    bhe.weightedUptime += secondsSinceLastStatusPublication
+    bhe.lastSeenWithThisAddressAndPort = statusPublicationMillis
+
+    bhe.ip = str(bridge.ip)
+    bhe.port = bridge.orport
+    return db.updateIntoBridgeHistory(bhe)
+
+def discountAndPruneBridgeHistories(discountUntilMillis):
+    db = bridgedb.Storage.getDB()
+    bhToRemove = []
+    # Just check the first item to see if we're anywhere close yet
+    sample = None
+    for y in db.getAllBridgeHistory():
+        sample = y
+        break
+    if not sample: return 0
+
+    if discountUntilMillis - sample.lastDiscountedHistoryValues < discountIntervalMillis:
+        return 0
+    for bh in db.getAllBridgeHistory():
+        # discount previous values by factor of 0.95 every 12 hours
+        bh.discountWeightedFractionalUptimeAndWeightedTime(discountUntilMillis)
+
+        if (bh.weightedTime != 0 and (bh.weightedUptime * 10000 / bh.weightedTime) < 1):
+            bhToRemove.append(k)
+        else:
+            db.updateIntoBridgeHistory(bh)
+
+    # prune items
+    for k in bhToRemove: db.delBridgeHistory(k)



_______________________________________________
tor-commits mailing list
tor-commits@xxxxxxxxxxxxxxxxxxxx
https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-commits