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