In the GPSdancer network logic, each computer is connected with \(\log_2{N}\) other computers (\(N\) being the network size) which are found by toggling the individual bits of the unique node number of each computer. This allows efficient accumulation of information by means of the square dance algorithm.

In this process, information that originates in one individual computer in the network ends up at every other computer in the network, and each computer receives the accumulated information of all others. However, sometimes it may be necessary for a single computer to send information to just one specific other computer, rather than to all of them. This is for instance useful during the ambiguity resolution process, in which two CORS stations that form double differences need to exchange single-difference residuals for common-view satellites.

Efficient point-to-point communication can be done in the existing GPSdancer square dance network - without needing new connections - by means of a simple routing logic, that will be explained using the Figure below.

Suppose that GPSdancer network node with number 369 wants to send some data to node number 604. The transmitting node (number 369) compares its binary representation (0x101110001) with that of the target node (604 = 0x1001011100), starting at the least significant bit. 

Because in this case the least significant bits of the source and target node are different, node 369 toggles this bit - making it identical to the bit value in the target node - and finds the number 368. In the square dance process, this is one of the network nodes to which node 369 is permanently connected, because "368" differs only in one bit from "369". This means that node 369 can send the data to node 368 immediately, with the instruction that this data should be routed to target node number 604.

Node 368 receives the data, and also compares its least significant bits with those of the target node. The two least significant bits of "368" and "604" are the same, but the third is not. So, node 368 toggles this third bit - to make it identical to the same bit in the target node number - and finds a new node number, 372. This is one of the nodes to which it has a permanent communication channel (only one bit different), so it sends the data to node 372 with the instruction to forward it to target node number 604.

It will be clear how each node that receives the data along the route simply applies this same logic of comparing its least significant bits with the target node number, toggling the first bit that is different, and sending the data onwards to a network neighbour that has at least one more bit in common with the target node. Sooner or later all bits are the same, namely when the target has been reached.

There are \(\log_2{N}\) bits in the node numbers, so that data can be routed to any arbitrary other node in the network within at most \(\log_2{N}\) communication hops. For small amounts of data this routing over existing connections is much faster (especially on 10 Gbit/s connections between cloud servers) than opening and closing a temporary connection from source to target. Also, it minimizes the number of required network connections per node, which is a security advantage.

Project details

Ultimate Browsers SupportThe GPS Dancer project started in 2007 as a voluntary project of a working group of the International Association of Geodesy.

Read more ...

Square dance algorithm

Great Docs and SupportThe GPS Dancer system was named after its "square dance" exchange algorithm. Of course, it also wants to to make the GPS reference frame denser.

Read more...

Here, there be pirates

The Dancer on-line network became immune against internet connection problems by leaving the US marines, and becoming a pirate.

Read more ...

Go to top