commit e538547dfc2973d7bd99e2d927a1d87be5230704 Author: Mike Perry mikeperry-git@fscked.org Date: Fri Jun 24 13:32:37 2011 -0700

Implement ratio ranking support. --- PathSupport.py | 36 ++++++++++++++++++++++++++++++++---- TorCtl.py | 16 ++++++++++++++++ 2 files changed, 48 insertions(+), 4 deletions(-)

diff --git a/PathSupport.py b/PathSupport.py index 4e9ad6d..d4ffbdd 100644 --- a/PathSupport.py +++ b/PathSupport.py @@ -229,6 +229,27 @@ class PercentileRestriction(NodeRestriction): def __str__(self): return self.__class__.__name__+"("+str(self.pct_skip)+","+str(self.pct_fast)+")"

+class RatioPercentileRestriction(NodeRestriction): + """Restriction to cut out a percentile slice of the network by ratio of + consensus bw to descriptor bw.""" + def __init__(self, pct_skip, pct_fast, r_list): + """Constructor. Sets up the restriction such that routers in the + 'pct_skip' to 'pct_fast' percentile of bandwidth rankings are + returned from the sorted list 'r_list'""" + self.pct_fast = pct_fast + self.pct_skip = pct_skip + self.sorted_r = r_list + + def r_is_ok(self, r): + "Returns true if r is in the percentile boundaries (by rank)" + if r.ratio_rank < len(self.sorted_r)*self.pct_skip/100: return False + elif r.ratio_rank > len(self.sorted_r)*self.pct_fast/100: return False + + return True + + def __str__(self): + return self.__class__.__name__+"("+str(self.pct_skip)+","+str(self.pct_fast)+")" + class UptimeRestriction(NodeRestriction): """Restriction to filter out routers with uptimes < min_uptime or > max_uptime""" @@ -1008,7 +1029,8 @@ class SelectionManager(BaseSelectionManager): def __init__(self, pathlen, order_exits, percent_fast, percent_skip, min_bw, use_all_exits, uniform, use_exit, use_guards,geoip_config=None, - restrict_guards=False, extra_node_rstr=None, exit_ports=None): + restrict_guards=False, extra_node_rstr=None, exit_ports=None, + order_by_ratio=False): BaseSelectionManager.__init__(self) self.__ordered_exit_gen = None self.pathlen = pathlen @@ -1026,6 +1048,7 @@ class SelectionManager(BaseSelectionManager): self.consensus = None self.exit_ports = exit_ports self.extra_node_rstr=extra_node_rstr + self.order_by_ratio = order_by_ratio

def reconfigure(self, consensus=None): try: @@ -1063,17 +1086,22 @@ class SelectionManager(BaseSelectionManager): nonentry_skip = self.percent_skip nonentry_fast = self.percent_fast

+ if self.order_by_ratio: + PctRstr = RatioPercentileRestriction + else: + PctRstr = PercentileRestriction + # XXX: sometimes we want the ability to do uniform scans # without the conserve exit restrictions.. entry_rstr = NodeRestrictionList( - [PercentileRestriction(self.percent_skip, self.percent_fast, sorted_r), + [PctRstr(self.percent_skip, self.percent_fast, sorted_r), OrNodeRestriction( [FlagsRestriction(["BadExit"]), ConserveExitsRestriction(self.exit_ports)]), FlagsRestriction(entry_flags, [])] ) mid_rstr = NodeRestrictionList( - [PercentileRestriction(nonentry_skip, nonentry_fast, sorted_r), + [PctRstr(nonentry_skip, nonentry_fast, sorted_r), OrNodeRestriction( [FlagsRestriction(["BadExit"]), ConserveExitsRestriction(self.exit_ports)]), @@ -1090,7 +1118,7 @@ class SelectionManager(BaseSelectionManager): [FlagsRestriction(["Running","Fast"], ["BadExit"])]) else: self.exit_rstr = NodeRestrictionList( - [PercentileRestriction(nonentry_skip, nonentry_fast, sorted_r), + [PctRstr(nonentry_skip, nonentry_fast, sorted_r), FlagsRestriction(["Running","Fast"], ["BadExit"])])

if self.extra_node_rstr: diff --git a/TorCtl.py b/TorCtl.py index ac49574..f0cf5c5 100755 --- a/TorCtl.py +++ b/TorCtl.py @@ -460,6 +460,7 @@ class Router: self.version = RouterVersion(version) self.os = os self.list_rank = 0 # position in a sorted list of routers. + self.ratio_rank = 0 # position in a ratio-sorted list of routers self.uptime = uptime self.published = published self.refcount = 0 # How many open circs are we currently in? @@ -1709,6 +1710,11 @@ class ConsensusTracker(EventHandler): self.sorted_r.sort(lambda x, y: cmp(y.bw, x.bw)) for i in xrange(len(self.sorted_r)): self.sorted_r[i].list_rank = i

+ ratio_r = copy.copy(self.sorted_r) + ratio_r.sort(lambda x, y: cmp(float(y.bw)/y.desc_bw, + float(x.bw)/x.desc_bw)) + for i in xrange(len(ratio_r)): ratio_r[i].ratio_rank = i + # XXX: Verification only. Can be removed. self._sanity_check(self.sorted_r)

@@ -1792,6 +1798,11 @@ class ConsensusTracker(EventHandler): self.sorted_r = filter(lambda r: not r.down, self.routers.itervalues()) self.sorted_r.sort(lambda x, y: cmp(y.bw, x.bw)) for i in xrange(len(self.sorted_r)): self.sorted_r[i].list_rank = i + + ratio_r = copy.copy(self.sorted_r) + ratio_r.sort(lambda x, y: cmp(float(y.bw)/y.desc_bw, + float(x.bw)/x.desc_bw)) + for i in xrange(len(ratio_r)): ratio_r[i].ratio_rank = i plog("DEBUG", str(time.time()-d.arrived_at)+ " Read " + str(len(d.idlist)) +" ND => "+str(len(self.sorted_r))+" routers. Update: "+str(update)) # XXX: Verification only. Can be removed. @@ -1821,6 +1832,11 @@ class ConsensusTracker(EventHandler): self.sorted_r = filter(lambda r: not r.down, self.routers.itervalues()) self.sorted_r.sort(lambda x, y: cmp(y.bw, x.bw)) for i in xrange(len(self.sorted_r)): self.sorted_r[i].list_rank = i + + ratio_r = copy.copy(self.sorted_r) + ratio_r.sort(lambda x, y: cmp(float(y.bw)/y.desc_bw, + float(x.bw)/x.desc_bw)) + for i in xrange(len(ratio_r)): ratio_r[i].ratio_rank = i self._sanity_check(self.sorted_r)

def current_consensus(self):