Distributed object location service

This describes a location service, which is a distributed service that maps an identifier of a remote object to the location (on the Internet) of that object.

The location service is basically a big virtual tree managed by a distributed set of computers across the Internet. An identifier to a remote object consists, virtually, of a path down that tree from the root to a leaf, and that leaf has a service which can return the location of that object. In practise, optimisations (described below as replicated branches) are used to prevent performance bottlenecks.

So for example, say the identifier of a remote object is 5A-F6-A1-02 in hexidecimal. This means "From the root, branch 5A, then branch F6, then branch A1, then the leaf at 02".

The root, each branch and each leaf is stored on one or more computers. Each branch knows where its subbranches and/or leaves are and it knows the location of it's parents (there my be multiple physical parents hosting copies of the same branch data). So to resolve the identifier above, the computer making the request would first ask the root, who would redirect the asker to branch 5A. Branch 5A would redirect the asker to branch F6, and so forth. Branches are actually distributed objects themselves and can replicate across hosting computers using a simple replication algorithm such as the one described below in "Branch replication".

Each branch could be managed on multiple computers for redundancy and scalability.

Self-optimising network

The location service would likely be hosted on a self-optimising network. A self-optimising network is a network of remotely accessible objects that link to each other. Those links change over time as more optimal configurations are found.

This type of network could be used for broadcasting information, or hosting a distributed object or service such as the location service above.

Each object could be called a "node". Each object stores a "main link" to another node, and also stores a list of other nodes which are reachable in 2 hops along the network along its main link. Each object finds these other nodes by simply asking the object on the other end of its "main link" for all other "main links" that are being made to that other object.

Periodically, an object may discover that it's main link is less optimal than a link that could be made to another one of the nodes it knows about. If so:

1. That object informs the object at the other end of the main link that it is disconnecting.
2. The object then attempts to make a new "main link" connection to the new object.
3. The object then informs all of it's children that it's "main link" has changed, so that the children can update their "other nodes" lists.

By periodically changing main links to more optimal ones, the network will trend towards matching the topography of the underlying network (the Internet). Nodes that are on the same LAN should, in theory, eventually discover each other.

The "optimality" heuristic of a link could be derived from a number of statistics:

• How many actual hops (i.e. using ICMP like traceroute does) a TCP connection (a "link") is.
• The latency of that connection.
• The bandwidth of that connection.
• The diameter of the self-optimising network (you don't want it getting too wide).

The above location service would be hosted on a self-optimising network like this:

• One of the nodes in the network would be the root node and the self-optimising network would then form a tree along the links.
• Clients would connect to their physically nearest node (possibly found using a similar algorithm to the self-optimising one, or by simply becoming part of the tree themselves). Requests for object locations would be made through that node.
• The location requests would percolate up through the tree (as far as needed) and back down again (if needed). Note that branches of the tree and the root node could be replicated on other nodes on the self-optimising tree, perhaps even locally, so that requests don't necessarily all filter through a bottleneck.
• The result is returned.
•  If many requests for data from the same branch is made, a local or near-by replica of that branch could be made.

Branch Replication

A branch is a replicated object. It is hosted across multiple computers. This is one way of replicating a branch:

• A branch has a "version number". Every time the branch is modified (by adding or removing replicas), that "version number" changes.
• Nodes which connect to that branch (i.e. clients, parent nodes and replicas) hold a reference to that branch. Contained in that reference is the version number of the branch and a list (perhaps a subset) of computers that the branch is hosted on.
• When a replica is added or removed, or a branch is moved, the version number is changed and all other replicas are notified (note that some synchronisation is needed to prevent concurrent modifications).
• Every time a reference to a branch is used, that version number is passed with the request. The reply from the branch includes whether or not that reference is current (using the version number).  If the reference is out of date, it is replaced with a new one.
• If a reference becomes so out of date that none of the computer references in it are valid, a request should percolate up the tree from the client's local branch to the root asking for a newer reference. If a copy of a more recent reference still can't be found, the original branch should still be able to be found from the root.