[Nsi-wg] Topology properties for NSI - a minimalistic approach

[John Vollbrecht]

I like this  - 

As far as I can tell it is exactly right, and I learned what a directed graph is.

Thanks

John

On Feb 10, 2010, at 8:09 PM, Evangelos Chaniotakis wrote:

> Hi all.
> 
> Here is my take on the topology issue:
> - We SHOULD describe the topology properties that we think we will need for pathfinding.
> - We SHOULD NOT assign too many semantics to the topology elements.
> - We MUST NOT design a new topology schema.
> 
> Now for the things that I think are absolutely required properties for any topology:
> 
> 1. The topology is a directed simple graph.
> Note: Directed graph means each edge is an arrow with a start vertex and an end vertex. Simple graph means there are no parallel edges i.e. going the same direction between the same two vertices.
> (I am on the fence for the "simple" requirement; do we need to make the topology a multigraph for some reason?)
> 
> 2. We are allowed to separate the topology into mutually exclusive subgraphs. I will use Jerry's term "Network Domain" for these subgraphs.
> Note: A subgraph is an arbitrary set of vertices and edges. It may consist of only edges, only vertices, or a mix thereof. A Network Domain is not necessarily a connected graph. (i.e. there is not necessarily a path between any two of its vertices).
> 
> 3. The union of all Network Domains MUST equal (cover) the entire topology.
> Rephrased: a given vertex or edge MUST belong to exactly one Network Domain.
> 
> 4. A vertex belonging to a Network Domain MAY be connected to a vertex belonging to another Network Domain. In that case, that vertex for NSI purposes will be classified as a "Service Termination Point".
> 
> 5. Edges and vertices MAY be annotated with attributes and metrics: i.e. framing, capacity, cost, etc.
> Note: We MUST NOT specify those - this is a job for NML. But we SHOULD specify what we think we will need from these attributes.
> 
> 6. Each vertex and edge MUST BE addressable through a globally unique identifier.
> 
> 
> Note that in the above there are very few hard requirements for the topology graph - it can be as rich or as simple as necessary.
> 
> I have intentionally avoided assigned any names (such as "node", "port", "link", "point" etc) to the edges and vertices of the topology graph.
> 
> Finally, I think that the above requirements are enough to satisfy the needs of pathfinding. Can anyone think of any further requirements? Or is there a way we relax these even more somehow?
> 
> 
> 
> Here are a couple of examples of graphs (attached also in .graffle). I will work on more complex ones if needed but really, they will be pretty much equivalent to the graphs on Jerry's slides.
> 
> <topo-examples.pdf>
> 
> 
> 
> 
> <topo-examples.graffle>_______________________________________________
> nsi-wg mailing list
> nsi-wg at ogf.org
> http://www.ogf.org/mailman/listinfo/nsi-wg