User login

Weekly Report

26

Jun

2014

I've mostly been writing lately, but I have been fixing some bugs in my network tests as well. And in the process I have started getting some results back.

So it turns out that in a network of 1000 nodes to connect each pair of nodes with two paths you end up creating lot of paths. And when you are writing in python so you arent worrying about destroying your data structures, then try to do 1000 iterations with 3 different algorithms, you use a heck of a lot of memory.

So my week has been spent adding proper memory management as well as things like turning lists into generators and trying to reuse objects and splitting my tests up so they can be run as separate processes to try to reduce that footprint.

In the process I discovered a few bugs, like occasional infinite paths as well as some others that seem to only be common on huge networks which is a nuisance to debug since it takes several minutes to run the algorithms on a huge network.

Anyway, while doing this I have started to get some results back and they are kinda cool. So my three approaches I am testing are: 1. Building two minimally overlapping paths between each pair of points. 2. Building two minimally overlapping paths in such a way that it guarantees that you will never have more than two flows to each destination. 3. Building one path, but at each hop having an alternative path that you can use if the next link is broken.

And it turns out that by far the most efficient method is 3, even though this can require 4 flows per switch per destination. The thing is that you only need those flows on transit hops. Because you dont build the full secondary path you end up with far fewer transit hops. But even cooler is that method 1 is actually more efficient than method 2. Because it builds shorter paths, even though each node can have a whole bunch of paths to a destination (and in the worst case it does end up costing more) on average the shorter paths mean fewer total flows.

26

Jun

2014

Just to clarify--because I

Just to clarify--because I didnt explain this well I think---the backup path in 3 goes only as far as some other node in the network that is closer to the destination, from there it piggy backs on that nodes default path. So you end up using very few paths.