[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]
[or-cvs] r11061: Introduced probabilistic path selection from a network-model (torflow/trunk)
Author: renner
Date: 2007-08-08 07:58:13 -0400 (Wed, 08 Aug 2007)
New Revision: 11061
Modified:
torflow/trunk/op-addon.py
Log:
Introduced probabilistic path selection from a network-model
unsing a ranking computed from expected RTTs and minimum
advertised bandwidth of routers in a path.
Modified: torflow/trunk/op-addon.py
===================================================================
--- torflow/trunk/op-addon.py 2007-08-08 05:50:31 UTC (rev 11060)
+++ torflow/trunk/op-addon.py 2007-08-08 11:58:13 UTC (rev 11061)
@@ -25,6 +25,10 @@
# Set the version
VERSION = "0.0.01-alpha"
+# Path to data-directory
+DATADIR = "data/op-addon/"
+# Our IP-address
+IP = None
# Try to get the config-file from the commandline
if len(sys.argv) == 1:
@@ -46,11 +50,13 @@
sys.exit(0)
# Sections
-HOST_PORT = "HostPort"
-CIRC_MANAGEMENT = "CircuitManagement"
-NODE_SELECTION = "NodeSelection"
-GEOIP = "GeoIP"
+HOST_PORT = "HOST_PORT"
+CIRC_MANAGEMENT = "CIRC_MANAGEMENT"
+NODE_SELECTION = "NODE_SELECTION"
+GEOIP = "GEOIP"
+TESTING = "TESTING"
RTT = "RTT"
+MODEL = "MODEL"
# Measure the circuits
measure_circs = config.getboolean(RTT, "measure_circs")
@@ -62,35 +68,33 @@
# Choose randomly from a set of hosts/ports?
ping_dummy_host = config.get(RTT, "ping_dummy_host")
ping_dummy_port = config.getint(RTT, "ping_dummy_port")
-
# Sleep interval between working loads in sec
initial_interval = config.getfloat(RTT, "initial_interval")
- sleep_interval = config.getfloat(RTT, "sleep_interval")
- # Close a circ after n timeouts or avg measured slownesses
+ frequency = config.getfloat(RTT, "frequency")
+ # Close a circ after n timeouts
timeout_limit = config.getint(RTT, "timeout_limit")
- # Close a circ after n measured slownesses
- slowness_limit = config.getint(RTT, "slowness_limit")
- # Close circs slower & create only circs faster than this
- slow = config.getfloat(RTT, "slow")
-
+
# Set to True if we want to measure partial circuits
# This also enables circuit creation from the model
- measure_partial_circs = config.getboolean(RTT, "measure_partial_circs")
- if measure_partial_circs:
- import networkx
+ network_model = config.getboolean(MODEL, "network_model")
+ if network_model:
+ import networkx
+ # RTT-threshhold when creating circs from the model
+ max_rtt = config.getfloat(MODEL, "max_rtt")
# Minimum number of proposals to choose from
- min_proposals = config.getint(RTT, "min_proposals")
+ min_proposals = config.getint(MODEL, "min_proposals")
# Min ratio of traditionally created circs
# ensures growing of the explored subnet
- min_ratio = config.getfloat(RTT, "min_ratio")
+ min_ratio = config.getfloat(MODEL, "min_ratio")
# Testing mode: Collect latencies of circuits and links in the
- # network. Close circuits after num_tests measures and involve
+ # network. Close circuits after num_xx_tests measures and involve
# a FileHandler to write data to a file
- testing_mode = config.getboolean(RTT, "testing_mode")
- if testing_mode:
- num_tests = config.getint(RTT, "num_tests")
- num_records = config.getint(RTT, "num_records")
+ TESTING_MODE = config.getboolean(TESTING, "testing_mode")
+ if TESTING_MODE:
+ # TODO: num_bw_tests = config.getint(TESTING, "num_bw_tests")
+ num_rtt_tests = config.getint(TESTING, "num_rtt_tests")
+ num_records = config.getint(TESTING, "num_records")
def get_geoip_config():
""" Read the geoip-configuration from the config-file """
@@ -127,9 +131,6 @@
use_guards = config.getboolean(NODE_SELECTION, "use_guards"),
geoip_config = get_geoip_config())
-# Path to directory where to store files
-data_dir = "data/op-addon/"
-
## Connection #################################################################
class Connection(TorCtl.Connection):
@@ -196,10 +197,31 @@
def get_median(self):
""" Return the median of the values """
if len(self.values) > 0:
- self.values.sort()
- return self.values[(len(self.values)-1)/2]
+ values = copy.copy(self.values)
+ values.sort()
+ return values[(len(values)-1)/2]
else: return 0.0
+## CircuitBuildingStats #######################################################
+
+class CircuitBuildingStats(Stats):
+ """ Create an instance of this and gather overall circuit stats """
+ def __init__(self):
+ Stats.__init__(self)
+ self.failures_buildup = 0 # Failures during buildup
+ self.failures_established = 0 # Failures on established
+
+ def to_string(self):
+ """ Create a string for writing to a file """
+ s = "Successful circuit buildups: "
+ s += str(len(self.values)) + " records, median=" + str(self.median)
+ s += " s, avg=" + str(self.mean) + " s"
+ s += ", dev=" + str(self.dev) + " s (min=" + str(self.min)
+ s += " s, max=" + str(self.max) + " s)\n"
+ s += "Failures during circuit-buildups: " + str(self.failures_buildup) + "\n"
+ s += "Failures on established circuits: " + str(self.failures_established)
+ return s
+
## FileHandler ################################################################
class FileHandler:
@@ -229,17 +251,16 @@
def __init__(self):
PathSupport.Circuit.__init__(self)
# RTT stuff
- self.part_rtts = {} # dict of partial rtts, pathlen 3: 1-2-None
- self.current_rtt = None # double (sec): current value
- self.stats = Stats() # stats about total RTT contains history
+ self.part_rtts = {} # Dict of partial rtts, pathlen 3: 1-2-None
+ self.current_rtt = None # Double (sec): current value
+ self.stats = Stats() # Stats about total RTT contains history
# Counters and flags
- self.age = 0 # age in rounds
- self.timeout_counter = 0 # timeout limit
- self.slowness_counter = 0 # slowness limit
- self.rtt_created = False # if this was created from the model
+ self.age = 0 # Age in rounds
+ self.timeout_counter = 0 # Timeout limit
+ self.rtt_created = False # Created from the model
def add_rtt(self, rtt):
- """ Add a new value and refresh the stats """
+ """ Add a new value and refresh stats and current """
# Set current
if self.current_rtt == None:
self.current_rtt = rtt
@@ -269,26 +290,8 @@
""" Stream class extended to hop """
def __init__(self, sid, host, port, kind):
PathSupport.Stream.__init__(self, sid, host, port, kind)
- self.hop = None # save hop if this is a ping, hop=None is complete circ
+ self.hop = None # Save hop if this is a ping, hop=None is complete circ
-## CircuitBuildingStats #######################################################
-
-class CircuitBuildingStats(Stats):
- """ Create an instance of this and gather overall circuit stats """
- def __init__(self):
- Stats.__init__(self)
- self.failures = 0 # count failures
-
- def to_string(self):
- """ Create a string for writing to a file """
- s = "Successful circuit buildups: "
- s += str(len(self.values)) + " records, median=" + str(self.median)
- s += " s, avg=" + str(self.mean) + " s"
- s += ", dev=" + str(self.dev) + " s (min=" + str(self.min)
- s += " s, max=" + str(self.max) + " s)\n"
- s += "Circuits that failed during buildup: " + str(self.failures)
- return s
-
## NetworkModel ###############################################################
class LinkInfo:
@@ -316,10 +319,12 @@
def __init__(self, links, path):
# This is a list of LinkInfo objects
self.links = links
- # Also save the path for passing to build_circuit, cut off ROOT here
+ # Cut off ROOT here
self.path = path[1:len(path)]
- # Compute the expected RTT (from current value?)
+ # Compute the expected RTT
self.rtt = reduce(lambda x,y: x + y.current_rtt, self.links, 0.0)
+ self.min_bw = 0 # Minimum bw of routers in the path
+ self.ranking_index = None # Score computed from bw and RTT
def to_string(self):
""" Create a string for printing out information """
@@ -329,29 +334,35 @@
return s + "--> " + str(self.rtt) + " sec"
class NetworkModel:
- """ This class is used to record measured RTTs for single links in a model
+ """ This class is used to record measured RTTs of single links in a model
of the 'currently explored subnet' (undirected graph) """
- def __init__(self, logfile=None):
- """ Constructor: pass the root of all our circuits """
- self.pickle_path = "data/op-addon/network-model.pickle"
- self.logfile = logfile # Optional logfile
+ def __init__(self, routers):
+ """ Constructor: pass the root of all circuits """
+ self.pickle_path = DATADIR + "network-model.pickle"
+ self.logfile = None # FileHandler(DATADIR + "proposals")
+ # For generating proposals
self.proposals = [] # Current list of circ-proposals
- self.prefixes = {} # Prefixes for DFS
- try:
+ self.prefixes = {} # Prefixes for DFS
+ self.routers = routers # Link to the router-list
+ self.target_host = None
+ self.target_port = None
+ self.max_rtt = 0
+ try:
self.graph = self.load_graph()
- self.find_all_proposals()
- self.print_info()
+ self.up_to_date = False
except:
plog("INFO", "Could not load a model, creating a new one ..")
self.graph = networkx.XGraph(name="Explored Tor Subnet")
self.graph.add_node(None)
+ self.up_to_date = True
+ self.print_info()
plog("INFO", "NetworkModel initiated")
def save_graph(self):
""" Write the graph to a binary file """
start = time.time()
networkx.write_gpickle(self.graph, self.pickle_path)
- plog("INFO", "Saved graph to '" + self.pickle_path +
+ plog("INFO", "Saved network-model to '" + self.pickle_path +
"' in " + str(time.time()-start) + " sec")
def load_graph(self):
@@ -359,14 +370,14 @@
graph = networkx.read_gpickle(self.pickle_path)
plog("INFO", "Loaded graph from '" + self.pickle_path + "'")
return graph
-
+
def add_link(self, src, dest, rtt):
- """ Add link to the graph given src, dest (routers) & rtt (LinkInfo) """
+ """ Add link to the graph given src, dest (router-ids) & RTT (LinkInfo) """
self.graph.add_edge(src, dest, LinkInfo(src, dest, rtt))
-
+
def add_circuit(self, c):
- """ Check if we can compute RTTs of single links for circuit c and store
- these in the model """
+ """ Check if we can compute RTTs of single links for a circuit
+ and store these in the model """
# Get the length
path_len = len(c.path)
# Go through the path
@@ -381,7 +392,6 @@
link_rtt = c.part_rtts[i+1] - c.part_rtts[i]
if link_rtt > 0:
plog("INFO", "Computed link-RTT " + str(i) + ": " + str(link_rtt))
- # Save to NetworkModel
self.add_link(c.path[i-1].idhex, c.path[i].idhex, link_rtt)
else:
plog("WARN", "Negative link-RTT " + str(i) + ": " + str(link_rtt))
@@ -391,102 +401,126 @@
link_rtt = c.part_rtts[None] - c.part_rtts[i]
if link_rtt > 0:
plog("INFO", "Computed link-RTT " + str(i) + ": " + str(link_rtt))
- # Save to NetworkModel
self.add_link(c.path[i-1].idhex, c.path[i].idhex, link_rtt)
else:
plog("WARN", "Negative link-RTT " + str(i) + ": " + str(link_rtt))
+ self.up_to_date = False
- def get_link_info(self, path):
- """ From a path given as list of routers, return link-infos """
- links = []
- for i in xrange(0, len(path)-1):
- # TODO: Check if edge exists
- links.append(self.graph.get_edge(path[i], path[i+1]))
- return links
+ def delete_node(self, idhex):
+ """ Delete a router from the model """
+ if idhex in self.graph:
+ # Delete links first
+ edges = self.graph.edge_boundary(idhex)
+ for e in edges:
+ self.graph.delete_edge(e)
+ # Then remove the node
+ self.graph.delete_node(idhex)
+ plog("INFO", "Deleted node with ID " + idhex + " from the model")
+ self.up_to_date = False
- def find_all_proposals(self):
- """ Call visit on the root-node """
+ def update(self):
+ """ Update model with a given list of routers """
+ nodes = self.graph.nodes()
+ for id in nodes:
+ if not id in self.routers:
+ if id:
+ plog("INFO", "Router with id " + id +
+ " is not known, deleting node ..")
+ self.delete_node(id)
+ plog("INFO", "Updated model with current router-list")
+
+ def set_target(self, host, port, max_rtt=0):
+ """ Change the target for generating paths """
+ if self.target_host != host or self.target_port != port\
+ or self.max_rtt != max_rtt:
+ self.target_host = host
+ self.target_port = port
+ self.max_rtt = max_rtt
+ self.up_to_date = False
+
+ def generate_proposals(self):
+ """ Call visit() on the root-node """
+ self.update()
# Reset list of proposals and prefixes for DFS
self.proposals = []
self.prefixes.clear()
start = time.time()
# Start the search
self.visit(None, [])
- # Sort proposals for their RTTs
- sort_list(self.proposals, lambda x: x.rtt)
- plog("INFO", "Finding " + str(len(self.proposals)) +
- " proposals and sorting them took us " +
- str(time.time()-start) + " seconds")
+ self.up_to_date = True
+ plog("INFO", "Generating " + str(len(self.proposals)) +
+ " proposals took us " + str(time.time()-start) +
+ " seconds [max_rtt=" + str(self.max_rtt) + "]")
+ def get_link_info(self, path):
+ """ From a path given as list of ids, return link-infos """
+ links = []
+ for i in xrange(0, len(path)-1):
+ links.append(self.graph.get_edge(path[i], path[i+1]))
+ return links
+
def visit(self, node, path, i=1):
""" Recursive Depth-First-Search: Maybe use some existing methods """
if node not in path:
path.append(node)
# Root -- Exit
if len(path) == 4:
- # We found a possible circuit: add to the proposals
- self.proposals.append(PathProposal(self.get_link_info(path), path))
+ # This could be an option
+ if "Exit" in self.routers[node].flags:
+ if self.routers[node].will_exit_to(self.target_host, self.target_port):
+ p = PathProposal(self.get_link_info(path), path)
+ if self.max_rtt > 0:
+ if p.rtt <= self.max_rtt:
+ self.proposals.append(p)
+ else: self.proposals.append(p)
else:
self.prefixes[i] = path
- # G is also a dict
+ # The graph is also a dict
for n in self.graph[node]:
if n not in self.prefixes[i]:
self.visit(n, copy.copy(self.prefixes[i]), i+1)
- def get_proposals(self, n):
- """ Return all proposals having rtt <= n seconds """
- ret = []
- for p in self.proposals:
- if p.rtt <= n:
- ret.append(p)
- plog("INFO", "Found " + str(len(ret)) +
- " path proposals having RTT <= " + str(n) + " sec")
- return ret
-
def print_info(self):
""" Create a string holding info and the proposals for printing """
out = str(self.graph.info())
for p in self.proposals:
- out += "\nPath Proposal: " + p.to_string()
+ out += "\nProposal: " + p.to_string()
# Only print them out if there are not too much
- if len(self.proposals) < 100:
+ if len(self.proposals) > 50:
+ plog("INFO", "Currently " + str(len(self.proposals)) +
+ " proposals! Not printing them out ..")
+ else:
print(out)
- else:
- plog("INFO", "More than 100 proposals!")
- print(self.graph.info())
- # But log all of them to the file if it exists
+ # Log all of them to the file if it exists
if self.logfile: self.logfile.write(out)
## PingHandler ################################################################
class PingHandler(PathSupport.StreamHandler):
""" This class extends the general StreamHandler to handle ping-requests """
- def __init__(self, c, selmgr, num_circs, RouterClass, partial=False):
- # Anything ping-related
+ def __init__(self, c, selmgr, num_circs, RouterClass, use_model=False):
+ # Loggers for recording statistics
+ self.circ_stats = CircuitBuildingStats() # record setup-durations
+ self.stats_logger = FileHandler(DATADIR + "circ-setup-stats")
+ self.setup_logger = None # FileHandler(DATADIR + "circ-setup-durations")
+ if TESTING_MODE:
+ self.latency_logger = FileHandler(DATADIR + "mean-latencies")
+
+ # Queue containing circs to be tested
self.ping_queue = Queue.Queue() # (circ_id, hop)-pairs
- self.start_times = {} # dict (circ_id, hop):start_time
-
- # Handle global testing_mode
- if testing_mode:
- self.latency_logger = FileHandler(data_dir + "mean-latencies")
- # Additional stuff for measuring single links
- self.partial_circs = partial
- if self.partial_circs:
- self.model_logger = FileHandler(data_dir + "proposals")
- self.model = NetworkModel(self.model_logger)
-
- # Stuff for recording statistics
- self.circ_stats = CircuitBuildingStats() # record setup-durations
- self.stats_logger = FileHandler(data_dir + "circ-setup-stats")
- self.setup_logger = FileHandler(data_dir + "circ-setup-durations")
+ if use_model:
+ PathSupport.StreamHandler.__init__(self, c, selmgr, 0, RouterClass)
+ self.model = NetworkModel(self.routers)
+ self.num_circuits = num_circs
+ self.check_circuit_pool()
+ else:
+ self.model = None
+ PathSupport.StreamHandler.__init__(self, c, selmgr, num_circs, RouterClass)
- # Init the StreamHandler
- PathSupport.StreamHandler.__init__(self, c, selmgr, num_circs, RouterClass)
-
# Sorted circuit list
- self.sorted_circs = [] # list of circs sorted by current RTT
- # Start the Pinger that triggers the connections
+ self.sorted_circs = []
+ # Start the Pinger
self.pinger = Pinger(self)
self.pinger.setDaemon(True)
self.pinger.start()
@@ -507,19 +541,31 @@
plog("INFO", "We have " + str(len(circs)) + " circuits:")
for c in circs:
print("+ " + c.to_string())
+
+ def log_circuit(self, circ):
+ """ Only called in TESTING_MODE when tests are finished for writing
+ any interesting values to a file before closing a circ """
+ self.latency_logger.append(str(circ.setup_duration) + "\t" +
+ "\t" + str(circ.stats.mean))
+ line_count = self.latency_logger.get_line_count()
+ if line_count >= num_records:
+ plog("INFO", "Enough records, exiting. (line_count = " +
+ str(line_count) + ")")
+ # TODO: How to kill the main thread from here?
+ sys.exit(1)
def enqueue_pings(self):
""" schedule_immediate from pinger before triggering the initial ping """
print("")
self.refresh_sorted_list()
- # XXX: Check if there are any, else let the Pinger wait?
+ # TODO: Check if there are any circs, else let the Pinger wait?
circs = self.circuits.values()
for c in circs:
if c.built:
# Get id of c
id = c.circ_id
- if self.partial_circs:
- # If partial measurings wanted: get length
+ if self.model:
+ # Enqueue every hop
path_len = len(c.path)
for i in xrange(1, path_len):
self.ping_queue.put((id, i))
@@ -528,12 +574,6 @@
self.ping_queue.put((id, None))
plog("DEBUG", "Enqueued circuit " + str(id) + " hop None")
- def established(self, circ_list):
- """ Check if there is at least one circuit established """
- for c in circ_list:
- if c.built:
- return True
-
def attach_ping(self, stream):
""" Attach a ping stream to its circuit """
if self.ping_queue.empty():
@@ -541,13 +581,9 @@
plog("INFO", "Queue is empty --> round has finished, closing stream "
+ str(stream.strm_id))
self.close_stream(stream.strm_id, 5)
- # Clear start_times
- self.start_times.clear()
- # Call the rest from here?
- self.print_circuits(self.sorted_circs)
- if self.partial_circs:
- # Print out the model
- self.model.find_all_proposals()
+ # Print information
+ self.print_circuits(self.sorted_circs)
+ if self.model:
self.model.print_info()
# Enqueue again all circs
self.enqueue_pings()
@@ -580,61 +616,37 @@
" :" + str(e.args))
self.attach_ping(stream)
- def log_circuit(self, circ):
- """ To be called when num_tests is reached for writing
- any interesting values to a file before closing circ """
- self.latency_logger.append(str(circ.stats.median) + "\t" +
- str(circ.stats.mean) + "\t" + str(circ.setup_duration))
- line_count = self.latency_logger.get_line_count()
- if line_count >= num_records:
- plog("INFO", "Enough records, exiting. (line_count = " +
- str(line_count) + ")")
- # XXX: How to kill the parent thread from here?
- sys.exit(1)
-
def record_ping(self, s):
""" Record a ping from a stream event (DETACHED or CLOSED) """
# No timeout, this is a successful ping: measure here
hop = self.streams[s.strm_id].hop
- # Compute RTT using arrived_at
- rtt = s.arrived_at - self.start_times[(s.circ_id, hop)]
+ rtt = s.arrived_at-self.streams[s.strm_id].attached_at
plog("INFO", "Measured RTT: " + str(rtt) + " sec")
# Save RTT to circuit
self.circuits[s.circ_id].part_rtts[hop] = rtt
-
if hop == None:
# This is a total circuit measuring
self.circuits[s.circ_id].add_rtt(rtt)
plog("DEBUG", "Added RTT to history: " +
str(self.circuits[s.circ_id].stats.values))
- # TESTING_MODE: close if num_tests is reached
- if testing_mode:
- if self.circuits[s.circ_id].age == num_tests:
+ # TESTING_MODE: close if num_rtt_tests is reached
+ if TESTING_MODE:
+ if self.circuits[s.circ_id].age == num_rtt_tests:
plog("DEBUG", "Closing circ " + str(s.circ_id) +
- ": num_tests is reached")
+ ": num_rtt_tests is reached")
# Save stats to a file for generating plots etc.
- if self.partial_circs:
+ if self.model:
if self.circuits[s.circ_id].rtt_created:
- # TODO: Do we want to check if this circuit is *really* new?
self.log_circuit(self.circuits[s.circ_id])
else:
self.log_circuit(self.circuits[s.circ_id])
# Close the circuit
self.close_circuit(s.circ_id)
- # Close if slow-max is reached on current RTTs
- if self.circuits[s.circ_id].current_rtt >= slow:
- self.circuits[s.circ_id].slowness_counter += 1
- if slowness_limit > 0:
- if self.circuits[s.circ_id].slowness_counter >= slowness_limit:
- if not self.circuits[s.circ_id].closed:
- plog("DEBUG", "Slow-max (" + str(slowness_limit) +
- ") is reached --> closing circuit " + str(s.circ_id))
- self.close_circuit(s.circ_id)
# Resort only if this is for the complete circ
self.refresh_sorted_list()
- if self.partial_circs == True:
+ if self.model:
# Add the links of this circuit to the model
self.model.add_circuit(self.circuits[s.circ_id])
@@ -661,14 +673,13 @@
# SENTCONNECT
elif s.status == "SENTCONNECT":
- # Measure here, means save arrived_at in the dict
- self.start_times[(s.circ_id, self.streams[s.strm_id].hop)] = s.arrived_at
+ # Measure here, means set attached_at on the stream
+ self.streams[s.strm_id].attached_at = s.arrived_at
# DETACHED
elif s.status == "DETACHED":
if (s.reason == "TIMEOUT"):
self.circuits[s.circ_id].timeout_counter += 1
- self.circuits[s.circ_id].slowness_counter += 1
plog("DEBUG", str(self.circuits[s.circ_id].timeout_counter) +
" timeout(s) on circuit " + str(s.circ_id))
if timeout_limit > 0:
@@ -685,8 +696,8 @@
# Close the stream
self.close_stream(s.strm_id, 5)
- # CLOSED + END is also ping, some routers send it when measuring 1-hop
- # better measure on FAILED?
+ # CLOSED + END is also ping, some routers send it when measuring
+ # latency to a single hop, better measure on FAILED?
elif s.status == "CLOSED":
if s.reason == "END":
# Only record
@@ -700,40 +711,183 @@
# Catch FAILED/CLOSED now since circ will be removed
elif c.status == "FAILED" or c.status == "CLOSED":
circ = self.circuits[c.circ_id]
- # Do logging and statistics
- # TODO: Log failures on built circuits
+ # Setup a message for logging
+ message = ["FAILED"]
+ if c.reason: message.append("REASON=" + c.reason)
+ if c.remote_reason: message.append("REMOTE_REASON=" + c.remote_reason)
if not circ.built:
- message = ["FAILED"]
- if c.reason: message.append("REASON=" + c.reason)
- if c.remote_reason: message.append("REMOTE_REASON=" + c.remote_reason)
- self.setup_logger.append(" ".join(message) + ": " +
- str(circ.extend_times))
+ if self.setup_logger:
+ self.setup_logger.append(" ".join(message) + ": " +
+ str(circ.extend_times))
# Increase counter and write circ_stats to file
- if self.partial_circs:
+ if self.model:
if circ.rtt_created:
- self.circ_stats.failures += 1
+ self.circ_stats.failures_buildup += 1
self.stats_logger.write(self.circ_stats.to_string())
else:
- self.circ_stats.failures += 1
+ self.circ_stats.failures_buildup += 1
self.stats_logger.write(self.circ_stats.to_string())
-
+ elif not c.reason == "REQUESTED":
+ # Increase *other* counter and write stats to file
+ if self.model:
+ if circ.rtt_created:
+ self.circ_stats.failures_established += 1
+ self.stats_logger.write(self.circ_stats.to_string())
+ else:
+ self.circ_stats.failures_established += 1
+ self.stats_logger.write(self.circ_stats.to_string())
+
# Call the underlying method in any case
PathSupport.CircuitHandler.circ_status_event(self, c)
- self.refresh_sorted_list()
-
+
+ if c.status == "FAILED" or c.status == "CLOSED":
+ self.refresh_sorted_list()
# Log something on BUILT
if c.status == "BUILT":
circ = self.circuits[c.circ_id]
- self.setup_logger.append(str(circ.extend_times))
+ if self.setup_logger:
+ self.setup_logger.append(str(circ.extend_times))
# Add duration to circ_stats and write file
- if self.partial_circs:
+ if self.model:
if circ.rtt_created:
self.circ_stats.add_value(circ.setup_duration)
self.stats_logger.write(self.circ_stats.to_string())
else:
self.circ_stats.add_value(circ.setup_duration)
self.stats_logger.write(self.circ_stats.to_string())
+ self.refresh_sorted_list()
+
+ def build_circuit(self, host, port):
+ """ Override from CircuitHandler to support circuit-creation from model """
+ if self.model:
+ circ = None
+ # This is to ensure expansion of the model:
+ # Check ratio if we would add circ from model
+ trad = self.get_trad_circs()
+ ratio = trad/(len(self.circuits.values())+1.)
+ plog("DEBUG","Expected Ratio = " + str(ratio) +
+ " >= " + str(min_ratio) + " ?")
+ if ratio >= min_ratio:
+ if self.create_circ_from_model(host, port):
+ return
+ plog("INFO", "Not enough proposals [min_proposals=" + str(min_proposals) + "]")
+
+ # Create a circuit with the backup-method
+ plog("DEBUG", "Creating circuit with the backup-method")
+ PathSupport.CircuitHandler.build_circuit(self, host, port)
+ # Path selection from the model =============================================
+ def create_circ_from_model(self, host, port):
+ # Set the target
+ self.model.set_target(host, port, max_rtt)
+ if not self.model.up_to_date:
+ self.model.generate_proposals()
+ # Get the proposals and compute ranking
+ proposals = self.model.proposals
+ if len(proposals) >= min_proposals:
+ self.update_ranking(proposals)
+ # As long as there are enough
+ while len(proposals) >= min_proposals:
+
+ # Uniform:
+ # choice = random.choice(proposals)
+
+ # Fastest First:
+ # proposals = sort_list(proposals, lambda x: x.rtt)
+ # choice = proposals[0]
+
+ # Probabilistic:
+ choice = self.weighted_selection(proposals, lambda x: x.ranking_index)
+
+ # Convert ids to routers
+ r_path = self.keys_to_routers(choice.path)
+ if r_path and self.path_is_ok(r_path, host, port):
+ plog("INFO", "Chosen proposal: " + choice.to_string())
+ try:
+ circ = self.c.build_circuit_from_path(r_path)
+ circ.rtt_created = True
+ self.circuits[circ.circ_id] = circ
+ plog("INFO", "Created circ from model: " + str(circ.circ_id))
+ return True
+ except TorCtl.ErrorReply, e:
+ plog("NOTICE", "Error building circuit: " + str(e.args))
+ else:
+ proposals.remove(choice)
+
+ def weighted_selection(self, proposals, weight):
+ """ Select a proposal in a probabilistic way """
+ choice = None
+ # Compute the sum of weights
+ sum = 0
+ for p in proposals:
+ sum += weight(p)
+ plog("DEBUG", "Sum of all weights is " + str(sum))
+ # Choose a random number from [0,sum-1]
+ i = random.randint(0, sum-1)
+ plog("DEBUG", "Chosen random number is " + str(i))
+ # Go through the proposals and subtract
+ for p in proposals:
+ i -= weight(p)
+ if i < 0:
+ choice = p
+ plog("DEBUG", "Chosen path with ranking " +
+ str(weight(choice)))
+ return choice
+
+ def update_ranking(self, proposals):
+ """ Compute a ranking for each path-proposal using
+ measured RTTs and bandwidth from the descriptors """
+ start = time.time()
+ # Set min_bw to proposals
+ for p in proposals:
+ # Get the routers
+ r_path = self.keys_to_routers(p.path)
+ if r_path:
+ # Find min(bw_i)
+ bw = []
+ for r in r_path:
+ bw.append(r.bw)
+ p.min_bw = min(bw)
+ else:
+ proposals.remove(p)
+ plog("DEBUG", "Could not find the routers, removed ..")
+ # High bandwidths get high scores
+ sort_list(proposals, lambda x: x.min_bw)
+ plog("DEBUG", "MIN_BWs of proposals between: " + str(proposals[0].min_bw) +
+ " and " + str(proposals[len(proposals)-1].min_bw))
+ i = 1
+ for p in proposals:
+ p.bw_score = i
+ i += 1
+ # Low Latencies get high scores
+ sort_list(proposals, lambda x: x.rtt)
+ plog("DEBUG", "RTTs of proposals between: " + str(proposals[0].rtt) +
+ " and " + str(proposals[len(proposals)-1].rtt))
+ i = len(proposals)
+ for p in proposals:
+ p.rtt_score = i
+ i -= 1
+ # Compute weights from both of the values
+ for p in proposals:
+ # Calculate total score
+ # TODO: Weight these scores
+ total_score = p.rtt_score + p.bw_score
+ p.ranking_index = total_score
+ sort_list(proposals, lambda x: x.ranking_index)
+ plog("DEBUG", "Ranking indices of proposals between: " +
+ str(proposals[0].ranking_index) + " and " +
+ str(proposals[len(proposals)-1].ranking_index))
+ plog("INFO", "Updating ranking indices of proposals took " +
+ str(time.time()-start) + " sec")
+
+ # Helper functions ==========================================================
+ def established(self, circ_list):
+ """ Check if there is at least one circuit established """
+ # XXX: Currently NOT used
+ for c in circ_list:
+ if c.built:
+ return True
+
def get_trad_circs(self):
""" Count the circuits with rtt_created == False """
trad_circs = 0
@@ -742,86 +896,33 @@
trad_circs += 1
return trad_circs
- def path_is_ok(self, path):
- """ Check if we currently do not have (TODO: had?) a circuit
- with the given path (= Routers) """
+ def path_is_ok(self, path, host, port):
+ """ Check if there is currently a circuit with the given path (Routers) """
for c in self.circuits.values():
if c.path == path:
plog("ERROR", "Proposed circuit already exists")
return False
- # Additionally check if this path can exit
- if not path[len(path)-1].will_exit_to("255.255.255.255", 80):
- plog("ERROR", "Proposed circuit would not exit")
- return False
return True
def keys_to_routers(self, keys):
- """ See if we know the routers spec. by keys and return them """
+ """ See if we know the routers specified by keys and return them """
routers = []
- for k in keys:
- if k in self.routers:
- routers.append(self.routers[k])
+ for id in keys:
+ if id in self.routers:
+ routers.append(self.routers[id])
else:
- plog("WARN", "We do not know about a router having ID " + k)
- return
+ plog("INFO", "We do not know about a router having ID " + id)
+ try:
+ self.model.delete_node(id)
+ except:
+ plog("ERROR", "Could not delete router with ID " + id)
if len(routers) == len(keys):
return routers
- def probabilistic_selection(self, proposals):
- """ Select a proposal in a probabilistic way """
- # TODO:
- # Compute the sum of all expected RTTs
- # Choose a random number from range(0,sum)
- # Go through the proposals and subtract
- pass
+ def unknown_event(self, event):
+ # XXX: There are new events not yet recognized by our classes
+ plog("DEBUG", "UNKNOWN EVENT: " + str(event))
- def build_idle_circuit(self):
- """ Override from CircuitHandler to support circuit-creation from model """
- if self.partial_circs:
- circ = None
- # This is to ensure expansion of the explored subnet
- # Check if ratio would be ok when adding new rtt_created circ
- trad = float(self.get_trad_circs())
- ratio = trad/(len(self.circuits.values())+1)
- plog("DEBUG","Expected Ratio = " + str(ratio) +
- " >= " + str(min_ratio) + " ?")
- if ratio >= min_ratio:
- # Get the proposals RTT <= slow
- proposals = self.model.get_proposals(slow)
- # Check if we have >= min_proposals
- if len(proposals) >= min_proposals:
- proposals = sort_list(proposals, lambda x: x.rtt)
- # Check them out
- while len(proposals) >= 1:
-
- # Random choice
- choice = random.choice(proposals)
- # Choose the fastest
- #choice = proposals[0]
-
- # Convert the chosen ids to routers
- r_path = self.keys_to_routers(choice.path)
- if r_path:
- # Check if we already have a circ with this path
- if self.path_is_ok(r_path):
- plog("INFO", "Chosen proposal: " + choice.to_string())
- try:
- circ = self.c.build_circuit_from_path(r_path)
- circ.rtt_created = True
- self.circuits[circ.circ_id] = circ
- return
- except TorCtl.ErrorReply, e:
- plog("NOTICE", "Error building circuit: " + str(e.args))
- else:
- # Remove this proposals
- proposals.remove(choice)
- else:
- plog("WARN", "keys_to_routers() did not work!")
-
- # Build a circuit with the standard method
- plog("DEBUG", "Falling back to normal path selection")
- PathSupport.CircuitHandler.build_idle_circuit(self)
-
## Pinger #####################################################################
class Pinger(threading.Thread):
@@ -836,7 +937,7 @@
self.handler.schedule_immediate(lambda x: x.enqueue_pings())
while self.isAlive():
self.ping()
- time.sleep(sleep_interval)
+ time.sleep(frequency)
# No "try .. except .. finally .." in Python < 2.5 !
def ping(self):
@@ -865,19 +966,20 @@
def setup_location(conn):
""" Setup a router object representing this proxy """
- global path_config
- ip = None
+ #global path_config
+ global IP
try:
# Try to determine our IP
info = conn.get_info("address")
- ip = info["address"]
+ IP = info["address"]
# Get the country_code
- country_code = GeoIPSupport.get_country(ip)
- plog("INFO", "Our IP address is " + str(ip) + " [" + str(country_code) + "]")
+ country_code = GeoIPSupport.get_country(IP)
+ plog("INFO", "Our IP address is " + str(IP) + " [" + str(country_code) + "]")
except:
- plog("ERROR", "Could not get our IP and country")
+ plog("WARN", "Could not get our IP and country")
return False
- # path_config.entry_country = router.country_code
+ # Here we could set the current entry-country
+ # path_config.entry_country = country_code
return True
def configure(conn):
@@ -895,6 +997,7 @@
# Connect to Tor process
conn = connect(config.get(HOST_PORT, "control_host"),
config.getint(HOST_PORT, "control_port"))
+ # TODO: Give password here
conn.authenticate()
#conn.debug(file("control.log", "w"))
except socket.error, e:
@@ -908,26 +1011,25 @@
num_circs = config.getint(CIRC_MANAGEMENT, "idle_circuits")
# Set an EventHandler to the connection
if measure_circs:
- # We measure latencies
- if measure_partial_circs:
+ if network_model:
handler = PingHandler(conn, __selmgr, num_circs,
GeoIPSupport.GeoIPRouter, True)
else:
- handler = PingHandler(conn, __selmgr, num_circs, GeoIPSupport.GeoIPRouter)
+ handler = PingHandler(conn, __selmgr, num_circs, GeoIPSupport.GeoIPRouter)
else:
# No pings, only a StreamHandler
handler = PathSupport.StreamHandler(conn, __selmgr, num_circs,
GeoIPSupport.GeoIPRouter)
conn.set_event_handler(handler)
# Go to sleep to be able to get killed from the commandline
- # TODO: Do this only if _not_ in testing_mode?
+ # TODO: Do this only if *not* in testing_mode?
try:
while True:
time.sleep(60)
except KeyboardInterrupt:
# XXX: Schedule this
if measure_circs:
- if measure_partial_circs:
+ if network_model:
handler.model.save_graph()
# Stop other threads?
cleanup(conn)
@@ -941,5 +1043,5 @@
conn.close()
if __name__ == '__main__':
- plog("INFO", "This is OP-Addon v" + VERSION)
+ plog("INFO", "OP-Addon v" + VERSION)
startup(sys.argv)