more optimization options and nicer plots (which only work if you convert and compile pylab/matplotlib by hand right now).
diff --git a/sim.py b/sim.py
--- a/sim.py
+++ b/sim.py
@@ -243,7 +243,7 @@ def checkjump(target, prev, net):
return True
def checkswitch(target, prev, net):
- """Check if we should jump to the target.
+ """Check if we should switch positions with the target.
:param targetdeviation: deviation of the link distribution at the
target from a small world distribution."""
@@ -252,6 +252,23 @@ def checkswitch(target, prev, net):
switchwithtarget(target, prev, net)
return True
+def checkswitchalways(target, prev, net):
+ """Always switch positions with the target.
+
+ :param targetdeviation: deviation of the link distribution at the
+ target from a small world distribution."""
+ switchwithtarget(target, prev, net)
+ return True
+
+def checkswitchonesided(target, prev, net):
+ """Always switch positions with the target.
+
+ :param targetdeviation: deviation of the link distribution at the
+ target from a small world distribution."""
+ if hasbetterlinks(target, prev, net):
+ switchwithtarget(target, prev, net)
+ return True
+
def checkjumphalf(target, prev, net):
"""Check if we should jump halfway to the target.
@@ -267,6 +284,35 @@ def checkjumphalf(target, prev, net):
jumptotarget(target, prev, net)
return True
+def checkjumpratio(target, prev, net, ratio):
+ """Check if we should jump to the given ratio between prev and
+ target.
+
+ :param targetdeviation: deviation of the link distribution at the
+ target from a small world distribution."""
+ conns = net[prev][:]
+ target = prev * (1-ratio) + target * ratio
+ old = distances(prev, conns)
+ new = distances(target, conns)
+ newdev = deviationfromsmallworld(new)
+ olddev = deviationfromsmallworld(old)
+ if sum(newdev) < sum(olddev):
+ jumptotarget(target, prev, net)
+ return True
+
+def checkjumpgolden(target, prev, net, small=False):
+ """Check if we should jump the small or large golden ratio
+ (√5-1)/2 to the target (small=closer to the prev, not small=closer
+ to the target).
+
+ :param targetdeviation: deviation of the link distribution at the
+ target from a small world distribution."""
+ golden = (math.sqrt(5)-1)/2.0
+ if small:
+ return checkjumpratio(target, prev, net, 1-golden)
+ else:
+ return checkjumpratio(target, prev, net, golden)
+
def checkconnect(target, prev, net):
"""Check if we should connect to the target.
@@ -350,7 +396,7 @@ def checkreplacelongest(target, prev, ne
disconnectfromtarget(tokillconn, prev, net)
return True
-def checkfold(target, prev, net, probability=0.2, strategy="jumphalf"):
+def checkfold(target, prev, net, probability=0.07, strategy="jumphalf"):
"""switch to the target location with some probability"""
if random() > probability:
return
@@ -358,8 +404,16 @@ def checkfold(target, prev, net, probabi
return checkjump(target, prev, net)
if strategy == "switch":
return checkswitch(target, prev, net)
+ if strategy == "switchalways":
+ return checkswitchalways(target, prev, net)
+ if strategy == "switchonesided":
+ return checkswitchonesided(target, prev, net)
if strategy == "jumphalf":
return checkjumphalf(target, prev, net)
+ if strategy == "jumpgolden":
+ return checkjumpgolden(target, prev, net)
+ if strategy == "jumpgoldensmall":
+ return checkjumpgolden(target, prev, net, small=True)
if strategy == "connect":
return checkconnect(target, prev, net)
if strategy == "replacebest":
@@ -405,11 +459,11 @@ def linklengths(net):
def parse_args():
from argparse import ArgumentParser
parser = ArgumentParser(description="Simulate Freenet network optimization.")
- parser.add_argument("--strategy", help="The optimization strategy: jump switch jumphalf connect replacebest replacelongest connectsimple", default="jumphalf")
+ parser.add_argument("--strategy", help="The optimization strategy: switch switchalways switchonesided jump jumphalf jumpgolden jumpgoldensmall connect connectsimple replacebest replacelongest", default="jumphalf")
parser.add_argument("--size", help="The size of the network.", default=1000, type=int)
parser.add_argument("--connections", help="The mean number of connections per node.", default=20, type=int)
parser.add_argument("--maxhtl", help="The maximum length of routes to be successful.", default=20, type=int)
- parser.add_argument("--steps", help="The maximum number of modelsteps.", default=120, type=int)
+ parser.add_argument("--steps", help="The maximum number of modelsteps.", default=60, type=int)
parser.add_argument("--perstep", help="The number of requests to run per step.", default=100, type=int)
parser.add_argument("-o", "--output", help="Filename of the pylab plot.", default="plot.png")
return parser.parse_args()
@@ -417,17 +471,17 @@ def parse_args():
if __name__ == "__main__":
args = parse_args()
nodes = randomnodes(args.size)
- basenet = generatesmallworldunclean(nodes, args.connections)
lensnapshots = {}
foldperstep = args.perstep
- for run in range(2):
- if not run:
- net = deepcopy(basenet)
+ runs = ["ideal", "flat"]
+ for run in runs:
+ if run == "ideal":
+ net = generatesmallworldunclean(nodes, args.connections)
else:
net = generateflat(nodes, args.connections)
lensnapshots[(run,0)] = linklengths(net), [0]
- print (np.mean(lensnapshots[(0,0)][0]))
- print("===", "run", run, "===")
+ print (np.mean(lensnapshots[(run,0)][0]))
+ print("===", run, "===")
routelengths = fold(net, 20)
linklens = linklengths(net)
print (np.mean(linklens), np.mean(routelengths), "±", np.std(routelengths), "succ", len([r for r in routelengths if r < 20])/len(routelengths), min(routelengths), max(routelengths), sum(deviationfromsmallworld(linklens, numbins=10)))
@@ -445,10 +499,11 @@ if __name__ == "__main__":
run, i = key
linklen, routelen = val
# only plot one in 10 results
- if i % 10:
+ if i % 10 and i != 1:
continue
- pl.hist(linklen, 10000, cumulative=True, normed=True, histtype='step', label=str(run) + ", " + str(i*foldperstep) + ", " + str(np.mean(routelen)))
+ succ = len([r for r in routelen if r < 20])/len(routelen)
+ pl.hist(linklen, 10000, cumulative=True, normed=True, histtype='step', label=str(run) + ", " + "{:.2f}".format(i*foldperstep) + ", len: " + "{:.2f}".format(np.mean(routelen)) + ", succ: " + "{:.2f}".format(succ))
pl.semilogx()
- pl.legend(loc="best")
+ pl.legend(loc="upper left")
+ pl.title(str(args.size) + " nodes, " + str(args.connections) + " connections per node, optimized with strategy " + args.strategy)
pl.savefig(args.output)
-