[Tech] how does swapping work?

[Michael Rogers]

Pete Heist wrote:
> I'm looking for a basic explanation of how the swapping of the locations of
> two nodes works (details aside, as it seems the implementation may still be
> in flux?)

Each node has a routing location, which is a number between 0 and 1 
representing a point on the perimeter of a circle. For efficient 
routing, the distance between neighbouring nodes' routing locations 
should be minimised. The swapping algorithm tries to find a globally 
efficient solution to this problem using only local information, by 
swapping the locations of nodes without changing their connections.

* Each node periodically uses a random walk to select a partner and 
decides whether to swap locations with it.

* If swapping would reduce the product of the partners' distances to 
their neighbours, they swap.

* If swapping would increase the product of the partners' distances to 
their neighbours, they swap with a probability that decreases with the 
increase in distance.

The last part prevents the algorithm from getting stuck in suboptimal 
solutions.

Oskar's paper has all the details: 
http://www.math.chalmers.se/~ossa/swroute.pdf

Cheers,
Michael