[Nsi-wg] Regarding Pathfinding and Topology

[Jerry Sobieski]

Regarding Path Finding:

If we go back to [technology agnostic] basics of graphs and path 
finding, a "topology" is fundamentally a database of vertices and 
edges.   A vertex is considered to be "adjacent" to another vertex if 
there is an edge directly connecting the two vertices.
Path Finding is the exercise of constructing an ordered list of vertices 
beginning with the starting vertex and ending with the terminating 
vertex, and consisting of a set of intermediate vertices each of which 
is adjacent in the topology to the preceding vertex in the path list.

There are some basic assumptions in the above definition of "path" that 
we need to be explicit about.

First, we need to keep in mind that paths do not just magically appear.  
We need to analyze the topology to construct a path.  We start by 
placing the Start point onto our [empty] path list.   Then we build up 
the path by examining adjacencies.   Since the next element in the path 
must be adjacent to its predecessor, this forms a constraint on 
selecting the next element in the path list: It must be adjacent to the 
Start point.

But there may be *several* ( j ) vertices that are adjacent to the start 
point.  They all represent equal possibilities.   So we need to 
construct now "j" separate paths - each with the Start, and each with a 
different one of the j adjacent elements.   So now we have to explore 
each of the j possible paths for their adjacencies to add the third 
element.  And so on.  For a large highly connected graph, the possible 
number of paths explodes.    We need additional constraints to prune 
this tree...

So what if adjacency was not the only constraint?   What if we added a 
constraint called "color" and said find a Blue path.   We can check each 
adjacent vertex to see if it is Blue and prune all paths who's 
adjacencies are not Blue.   So now we have a set of partially built 
Paths whose elements are adjacent, and Blue.   We can continue this 
constraint based search of the resources based upon these two 
constraints.  At each stage if a path has no Blue adjacency (besides the 
preceding node) we can prune it.    At some stage the last constraint 
will be met - the next adjacent element will the Finish point and we 
have "found a path".

When we finally analyze all of our potential paths for these 
constraints, we may find that we have actually found *multiple* 
acceptable Blue paths.  Which one shall we choose?   Well, we only 
needed one, and since all the paths meet the constraints, it does not 
matter which we choose.  Any will do as far as the initial (user) 
constraints are concerned.   Note: These paths are not all the 
same...the paths may differ significantly in, say, the number of hops.   
But since this aspect (number of hops) was not a constraint on the 
initial path selection, then it does not matter now and the final 
constraint can actually be anything that identifies a single path, e.g. 
a random choice.  From the PF perspective all of these paths have met 
the constraints and are acceptable.

We can continue to discuss possible PF algorithms and issues, but its 
important to take stock now, and note some basic observations about this 
above example.   We need to expose rather subtle assumptions.

---> Another assumption: _/*Each vertex could be traversed in any 
direction.*/_  I.e. from any adjacency to any other adjacency.   What if 
for some reason there were limits on the vertex that would only allow 
paths to traverse the vertex in certain ingress/egress pairs?  How would 
this be expressed to the PF agent(s)?  What if every vertex had some 
nuance that imposed some random but invariant quirk on the transit 
function of the vertex?  How would we represent these nuances so that a 
PF could evaluate any node in the topology as to its useability in the path?

--->A basic assumption: _/*The topology was static.*/_   It did not 
change while we selected the path.   Were it to change, other vertices 
or edges (adjacencies) might have appeared that would create alternate 
paths.  Or some vertices or edges might have disappeared that now 
invalidate some of our resulting paths.  TIme varying availability 
causes much problems in large scale PF.

---> Another assumption: _/*Resources were not consumed*/_.  We did not 
consider if a vertex was "used up" or no longer available.   I.e. what 
if we said that a vertex can only be traversed once?  or a fixed number 
of times.  Closer to home: What if we had a bandwidth constraint?  An 
otherwise conforming vertex may not be useable because it ran out of 
internal resource...I.e. for some reason and at some point in time, a 
vertex is no longer available.   How do you know?

---> Another assumption: _/*There is only one path finder operating on 
the topology*/_.  What if there are two (or more) pathfinders 
constructing paths simultaneously.???   This is highly relevant to our 
current NSI issues.   We need to assume there will be more than one 
global pathfinder and these will need to interact cooperatively if we 
want to maintain a reliable system.   Combined with consumable 
resources, we have a *real* big problem.   Every time we insert a new 
element on one of those k potential paths, the PF needs to make sure 
that vertex reflects the use of the resource.   What if there were 100 
PFs running?  1000 PFs?  10000?   What if the each pathfinder was 
constructing a k-SPF trees with k=10, or 100, or 1000?   How does the 
number and complexity of the search algorithm affect scalability?

---> Another assumption: _/*There was one generic well behaved PF. */_ 
I.e. What if one PF implemented a greedy algorithm - e.g. I will go grab 
all the resources I can and then I will release those I deem unnecessary 
for this path.  If different PF algorithms are implemented, how could 
this affect the distributed system?   Do we need to specify the 
appropriate algorithm?

---> Another assumption. _/*There is one global topology database*/_ 
that holds all that is known of the topology.  And all path finder(s) 
have access to this information.  Given time varying state, how do we 
know if a resources are still available on any node?


Enough for now.   Please try to think about the implications of the 
issues outlined above.   We need to sort through these to arrive at a 
workable long term approach to PF and Topology.
tinfo/nsi-wg

Thanks for reading...
Jerry
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.ogf.org/pipermail/nsi-wg/attachments/20111210/189f2780/attachment.html