Getting from A to B in a given network

This is a guide to designing the DSR guide.

Assume we know the network topology—what nodes there are and which pairs are linked. If we have tolls on each link then we can plot a minimal toll path thru a network. If tolls fluctuate then we may want several paths thru the network from A to B. In ignorance of link tolls what minimum toll paths are possible?

We define a Gpath as any sequence of nodes beginning at A and ending at B such that adjacent nodes are linked. Since tolls are all positive we can eliminate any Gpath with duplicate nodes since there is another Gpath with lower total tolls, even in ignorance of the real tolls. I can’t think of any other Gpaths to eliminate. A path is hereby a sequence of unique nodes beginning at A and ending at B, with linked adjacent nodes.

Cloud

The next two paragraphs are plain wrong. I leave them for now because lattices may still be a practical abstraction.

In practice this set will be far too large, but I want to understand it mathematically. I think that it is clear that there is a lattice of the nodes with A at the bottom and B at the top such that any path is a chain in the lattice. A chain in a lattice on N is a subset of N which is totally ordered by PO and is not a proper subset of any other totally ordered subset of N.

For what its worth for any finite PO there is a unique subset of PO whose transitive closure is PO. For our network case this would consist of the list of all the links that could possibly be in a path from A to B and is probably the best way to describe the PO over a wire. This list somehow identifies the nodes at the link ends, or at least the outgoing interface numbers.

Such a list would be far too big for a guide to send a client even for massive jobs. I like the idea of sending a subset of nodes with link information and recent observed tolls thereon.

Algorithms

Here is a simplistic algorithm for a highly connected network. Select a set of recent times for which there are records of reported tolls for most links. I am imagining perhaps 10 recent times. For proposed paths this will result in 10 tolls, one for each of the recent times. Call these 10 numbers the toll vector. Begin to grow a sphere about both endpoints. By ‘sphere’ I mean a connected neighborhood whose ‘distance’ from the center is less that some radius. The radius grows as the set grows. The ‘distance’ is some minimax function of the 10 components of the toll vector components. The toll vectors are known for nodes in the sphere. Surprisingly soon the spheres will intersect and total paths become known. This is very vague.

The sphere solution is poor when the monopolist is involved. The ad-hoc solution for the guide is easy to provide but they must be discovered.

The guide is very much a broker and deals with many producers and many consumers of network function. I presume he charges both. An agent that plans to move a lot of data may consult two guides and the proposed format of path sets is easily merged. The agent can quickly judge the brokers as it moves data.

Divide and Conquer

Of course a guide may specialize in a super neighborhood with quick access to all the links therein. He can consult a specialist who specializes in knowing who (by hashed public key) is in what super neighborhoods. Collaboration between guides is straight forward.

The POTS Way

Here is a tried and true scheme. In the 1920’s AT&T developed a hierarchy with about 6 levels. To place a call within the United States the caller went up the hierarchy until the callee was in the same sub-tree. The call was then routed via the root node of the sub-tree. I think that hierarchy was only recently retired. In DSR hierarchies would not be monopolies. A hierarchy is, in effect, a spanning tree.